light_trace.c (22314B)
1 /* 2 =========================================================================== 3 Copyright (C) 1999-2005 Id Software, Inc. 4 5 This file is part of Quake III Arena source code. 6 7 Quake III Arena source code is free software; you can redistribute it 8 and/or modify it under the terms of the GNU General Public License as 9 published by the Free Software Foundation; either version 2 of the License, 10 or (at your option) any later version. 11 12 Quake III Arena source code is distributed in the hope that it will be 13 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with Foobar; if not, write to the Free Software 19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 20 =========================================================================== 21 */ 22 #include "light.h" 23 24 25 26 #define CURVE_FACET_ERROR 8 27 28 int c_totalTrace; 29 int c_cullTrace, c_testTrace; 30 int c_testFacets; 31 32 surfaceTest_t *surfaceTest[MAX_MAP_DRAW_SURFS]; 33 34 /* 35 ===================== 36 CM_GenerateBoundaryForPoints 37 ===================== 38 */ 39 void CM_GenerateBoundaryForPoints( float boundary[4], float plane[4], vec3_t a, vec3_t b ) { 40 vec3_t d1; 41 42 // amke a perpendicular vector to the edge and the surface 43 VectorSubtract( b, a, d1 ); 44 CrossProduct( plane, d1, boundary ); 45 VectorNormalize( boundary, boundary ); 46 boundary[3] = DotProduct( a, boundary ); 47 } 48 49 /* 50 ===================== 51 TextureMatrixFromPoints 52 ===================== 53 */ 54 void TextureMatrixFromPoints( cFacet_t *f, drawVert_t *a, drawVert_t *b, drawVert_t *c ) { 55 int i, j; 56 float t; 57 float m[3][4]; 58 float s; 59 60 // This is an incredibly stupid way of solving a three variable equation 61 for ( i = 0 ; i < 2 ; i++ ) { 62 63 m[0][0] = a->xyz[0]; 64 m[0][1] = a->xyz[1]; 65 m[0][2] = a->xyz[2]; 66 m[0][3] = a->st[i]; 67 68 m[1][0] = b->xyz[0]; 69 m[1][1] = b->xyz[1]; 70 m[1][2] = b->xyz[2]; 71 m[1][3] = b->st[i]; 72 73 m[2][0] = c->xyz[0]; 74 m[2][1] = c->xyz[1]; 75 m[2][2] = c->xyz[2]; 76 m[2][3] = c->st[i]; 77 78 if ( fabs(m[1][0]) > fabs(m[0][0]) && fabs(m[1][0]) > fabs(m[2][0]) ) { 79 for ( j = 0 ; j < 4 ; j ++ ) { 80 t = m[0][j]; 81 m[0][j] = m[1][j]; 82 m[1][j] = t; 83 } 84 } else if ( fabs(m[2][0]) > fabs(m[0][0]) && fabs(m[2][0]) > fabs(m[1][0]) ) { 85 for ( j = 0 ; j < 4 ; j ++ ) { 86 t = m[0][j]; 87 m[0][j] = m[2][j]; 88 m[2][j] = t; 89 } 90 } 91 92 s = 1.0 / m[0][0]; 93 m[0][0] *= s; 94 m[0][1] *= s; 95 m[0][2] *= s; 96 m[0][3] *= s; 97 98 s = m[1][0]; 99 m[1][0] -= m[0][0] * s; 100 m[1][1] -= m[0][1] * s; 101 m[1][2] -= m[0][2] * s; 102 m[1][3] -= m[0][3] * s; 103 104 s = m[2][0]; 105 m[2][0] -= m[0][0] * s; 106 m[2][1] -= m[0][1] * s; 107 m[2][2] -= m[0][2] * s; 108 m[2][3] -= m[0][3] * s; 109 110 if ( fabs(m[2][1]) > fabs(m[1][1]) ) { 111 for ( j = 0 ; j < 4 ; j ++ ) { 112 t = m[1][j]; 113 m[1][j] = m[2][j]; 114 m[2][j] = t; 115 } 116 } 117 118 s = 1.0 / m[1][1]; 119 m[1][0] *= s; 120 m[1][1] *= s; 121 m[1][2] *= s; 122 m[1][3] *= s; 123 124 s = m[2][1]; 125 m[2][0] -= m[1][0] * s; 126 m[2][1] -= m[1][1] * s; 127 m[2][2] -= m[1][2] * s; 128 m[2][3] -= m[1][3] * s; 129 130 s = 1.0 / m[2][2]; 131 m[2][0] *= s; 132 m[2][1] *= s; 133 m[2][2] *= s; 134 m[2][3] *= s; 135 136 f->textureMatrix[i][2] = m[2][3]; 137 f->textureMatrix[i][1] = m[1][3] - f->textureMatrix[i][2] * m[1][2]; 138 f->textureMatrix[i][0] = m[0][3] - f->textureMatrix[i][2] * m[0][2] - f->textureMatrix[i][1] * m[0][1]; 139 140 f->textureMatrix[i][3] = 0; 141 /* 142 s = fabs( DotProduct( a->xyz, f->textureMatrix[i] ) - a->st[i] ); 143 if ( s > 0.01 ) { 144 Error( "Bad textureMatrix" ); 145 } 146 s = fabs( DotProduct( b->xyz, f->textureMatrix[i] ) - b->st[i] ); 147 if ( s > 0.01 ) { 148 Error( "Bad textureMatrix" ); 149 } 150 s = fabs( DotProduct( c->xyz, f->textureMatrix[i] ) - c->st[i] ); 151 if ( s > 0.01 ) { 152 Error( "Bad textureMatrix" ); 153 } 154 */ 155 } 156 } 157 158 /* 159 ===================== 160 CM_GenerateFacetFor3Points 161 ===================== 162 */ 163 qboolean CM_GenerateFacetFor3Points( cFacet_t *f, drawVert_t *a, drawVert_t *b, drawVert_t *c ) { 164 // if we can't generate a valid plane for the points, ignore the facet 165 if ( !PlaneFromPoints( f->surface, a->xyz, b->xyz, c->xyz ) ) { 166 f->numBoundaries = 0; 167 return qfalse; 168 } 169 170 // make boundaries 171 f->numBoundaries = 3; 172 173 CM_GenerateBoundaryForPoints( f->boundaries[0], f->surface, a->xyz, b->xyz ); 174 CM_GenerateBoundaryForPoints( f->boundaries[1], f->surface, b->xyz, c->xyz ); 175 CM_GenerateBoundaryForPoints( f->boundaries[2], f->surface, c->xyz, a->xyz ); 176 177 VectorCopy( a->xyz, f->points[0] ); 178 VectorCopy( b->xyz, f->points[1] ); 179 VectorCopy( c->xyz, f->points[2] ); 180 181 TextureMatrixFromPoints( f, a, b, c ); 182 183 return qtrue; 184 } 185 186 /* 187 ===================== 188 CM_GenerateFacetFor4Points 189 190 Attempts to use four points as a planar quad 191 ===================== 192 */ 193 #define PLANAR_EPSILON 0.1 194 qboolean CM_GenerateFacetFor4Points( cFacet_t *f, drawVert_t *a, drawVert_t *b, drawVert_t *c, drawVert_t *d ) { 195 float dist; 196 int i; 197 vec4_t plane; 198 199 // if we can't generate a valid plane for the points, ignore the facet 200 if ( !PlaneFromPoints( f->surface, a->xyz, b->xyz, c->xyz ) ) { 201 f->numBoundaries = 0; 202 return qfalse; 203 } 204 205 // if the fourth point is also on the plane, we can make a quad facet 206 dist = DotProduct( d->xyz, f->surface ) - f->surface[3]; 207 if ( fabs( dist ) > PLANAR_EPSILON ) { 208 f->numBoundaries = 0; 209 return qfalse; 210 } 211 212 // make boundaries 213 f->numBoundaries = 4; 214 215 CM_GenerateBoundaryForPoints( f->boundaries[0], f->surface, a->xyz, b->xyz ); 216 CM_GenerateBoundaryForPoints( f->boundaries[1], f->surface, b->xyz, c->xyz ); 217 CM_GenerateBoundaryForPoints( f->boundaries[2], f->surface, c->xyz, d->xyz ); 218 CM_GenerateBoundaryForPoints( f->boundaries[3], f->surface, d->xyz, a->xyz ); 219 220 VectorCopy( a->xyz, f->points[0] ); 221 VectorCopy( b->xyz, f->points[1] ); 222 VectorCopy( c->xyz, f->points[2] ); 223 VectorCopy( d->xyz, f->points[3] ); 224 225 for (i = 1; i < 4; i++) 226 { 227 if ( !PlaneFromPoints( plane, f->points[i], f->points[(i+1) % 4], f->points[(i+2) % 4]) ) { 228 f->numBoundaries = 0; 229 return qfalse; 230 } 231 232 if (DotProduct(f->surface, plane) < 0.9) { 233 f->numBoundaries = 0; 234 return qfalse; 235 } 236 } 237 238 TextureMatrixFromPoints( f, a, b, c ); 239 240 return qtrue; 241 } 242 243 244 245 246 /* 247 =============== 248 SphereFromBounds 249 =============== 250 */ 251 void SphereFromBounds( vec3_t mins, vec3_t maxs, vec3_t origin, float *radius ) { 252 vec3_t temp; 253 254 VectorAdd( mins, maxs, origin ); 255 VectorScale( origin, 0.5, origin ); 256 VectorSubtract( maxs, origin, temp ); 257 *radius = VectorLength( temp ); 258 } 259 260 261 /* 262 ==================== 263 FacetsForTriangleSurface 264 ==================== 265 */ 266 void FacetsForTriangleSurface( dsurface_t *dsurf, shaderInfo_t *si, surfaceTest_t *test ) { 267 int i; 268 drawVert_t *v1, *v2, *v3, *v4; 269 int count; 270 int i1, i2, i3, i4, i5, i6; 271 272 test->patch = qfalse; 273 test->numFacets = dsurf->numIndexes / 3; 274 test->facets = malloc( sizeof( test->facets[0] ) * test->numFacets ); 275 test->shader = si; 276 277 count = 0; 278 for ( i = 0 ; i < test->numFacets ; i++ ) { 279 i1 = drawIndexes[ dsurf->firstIndex + i*3 ]; 280 i2 = drawIndexes[ dsurf->firstIndex + i*3 + 1 ]; 281 i3 = drawIndexes[ dsurf->firstIndex + i*3 + 2 ]; 282 283 v1 = &drawVerts[ dsurf->firstVert + i1 ]; 284 v2 = &drawVerts[ dsurf->firstVert + i2 ]; 285 v3 = &drawVerts[ dsurf->firstVert + i3 ]; 286 287 // try and make a quad out of two triangles 288 if ( i != test->numFacets - 1 ) { 289 i4 = drawIndexes[ dsurf->firstIndex + i*3 + 3 ]; 290 i5 = drawIndexes[ dsurf->firstIndex + i*3 + 4 ]; 291 i6 = drawIndexes[ dsurf->firstIndex + i*3 + 5 ]; 292 if ( i4 == i3 && i5 == i2 ) { 293 v4 = &drawVerts[ dsurf->firstVert + i6 ]; 294 if ( CM_GenerateFacetFor4Points( &test->facets[count], v1, v2, v4, v3 ) ) { 295 count++; 296 i++; // skip next tri 297 continue; 298 } 299 } 300 } 301 302 if (CM_GenerateFacetFor3Points( &test->facets[count], v1, v2, v3 )) 303 count++; 304 } 305 306 // we may have turned some pairs into quads 307 test->numFacets = count; 308 } 309 310 /* 311 ==================== 312 FacetsForPatch 313 ==================== 314 */ 315 void FacetsForPatch( dsurface_t *dsurf, shaderInfo_t *si, surfaceTest_t *test ) { 316 int i, j; 317 drawVert_t *v1, *v2, *v3, *v4; 318 int count; 319 mesh_t srcMesh, *subdivided, *mesh; 320 321 srcMesh.width = dsurf->patchWidth; 322 srcMesh.height = dsurf->patchHeight; 323 srcMesh.verts = &drawVerts[ dsurf->firstVert ]; 324 325 //subdivided = SubdivideMesh( mesh, CURVE_FACET_ERROR, 9999 ); 326 mesh = SubdivideMesh( srcMesh, 8, 999 ); 327 PutMeshOnCurve( *mesh ); 328 MakeMeshNormals( *mesh ); 329 330 subdivided = RemoveLinearMeshColumnsRows( mesh ); 331 FreeMesh(mesh); 332 333 test->patch = qtrue; 334 test->numFacets = ( subdivided->width - 1 ) * ( subdivided->height - 1 ) * 2; 335 test->facets = malloc( sizeof( test->facets[0] ) * test->numFacets ); 336 test->shader = si; 337 338 count = 0; 339 for ( i = 0 ; i < subdivided->width - 1 ; i++ ) { 340 for ( j = 0 ; j < subdivided->height - 1 ; j++ ) { 341 342 v1 = subdivided->verts + j * subdivided->width + i; 343 v2 = v1 + 1; 344 v3 = v1 + subdivided->width + 1; 345 v4 = v1 + subdivided->width; 346 347 if ( CM_GenerateFacetFor4Points( &test->facets[count], v1, v4, v3, v2 ) ) { 348 count++; 349 } else { 350 if (CM_GenerateFacetFor3Points( &test->facets[count], v1, v4, v3 )) 351 count++; 352 if (CM_GenerateFacetFor3Points( &test->facets[count], v1, v3, v2 )) 353 count++; 354 } 355 } 356 } 357 test->numFacets = count; 358 FreeMesh(subdivided); 359 } 360 361 362 /* 363 ===================== 364 InitSurfacesForTesting 365 366 Builds structures to speed the ray tracing against surfaces 367 ===================== 368 */ 369 void InitSurfacesForTesting( void ) { 370 371 int i, j; 372 dsurface_t *dsurf; 373 surfaceTest_t *test; 374 drawVert_t *dvert; 375 shaderInfo_t *si; 376 377 for ( i = 0 ; i < numDrawSurfaces ; i++ ) { 378 dsurf = &drawSurfaces[ i ]; 379 if ( !dsurf->numIndexes && !dsurf->patchWidth ) { 380 continue; 381 } 382 383 // don't make surfaces for transparent objects 384 // because we want light to pass through them 385 si = ShaderInfoForShader( dshaders[ dsurf->shaderNum].shader ); 386 if ( (si->contents & CONTENTS_TRANSLUCENT) && !(si->surfaceFlags & SURF_ALPHASHADOW) ) { 387 continue; 388 } 389 390 test = malloc( sizeof( *test ) ); 391 surfaceTest[i] = test; 392 ClearBounds( test->mins, test->maxs ); 393 394 dvert = &drawVerts[ dsurf->firstVert ]; 395 for ( j = 0 ; j < dsurf->numVerts ; j++, dvert++ ) { 396 AddPointToBounds( dvert->xyz, test->mins, test->maxs ); 397 } 398 399 SphereFromBounds( test->mins, test->maxs, test->origin, &test->radius ); 400 401 if ( dsurf->surfaceType == MST_TRIANGLE_SOUP || dsurf->surfaceType == MST_PLANAR ) { 402 FacetsForTriangleSurface( dsurf, si, test ); 403 } else if ( dsurf->surfaceType == MST_PATCH ) { 404 FacetsForPatch( dsurf, si, test ); 405 } 406 } 407 } 408 409 410 /* 411 ===================== 412 GenerateBoundaryForPoints 413 ===================== 414 */ 415 void GenerateBoundaryForPoints( float boundary[4], float plane[4], vec3_t a, vec3_t b ) { 416 vec3_t d1; 417 418 // amke a perpendicular vector to the edge and the surface 419 VectorSubtract( b, a, d1 ); 420 CrossProduct( plane, d1, boundary ); 421 VectorNormalize( boundary, boundary ); 422 boundary[3] = DotProduct( a, boundary ); 423 } 424 425 426 /* 427 ================= 428 SetFacetFilter 429 430 Given a point on a facet, determine the color filter 431 for light passing through 432 ================= 433 */ 434 void SetFacetFilter( traceWork_t *tr, shaderInfo_t *shader, cFacet_t *facet, vec3_t point ) { 435 float s, t; 436 int is, it; 437 byte *image; 438 int b; 439 440 // most surfaces are completely opaque 441 if ( !(shader->surfaceFlags & SURF_ALPHASHADOW) ) { 442 VectorClear( tr->trace->filter ); 443 return; 444 } 445 446 s = DotProduct( point, facet->textureMatrix[0] ) + facet->textureMatrix[0][3]; 447 t = DotProduct( point, facet->textureMatrix[1] ) + facet->textureMatrix[1][3]; 448 449 if ( !shader->pixels ) { 450 // assume completely solid 451 VectorClear( point ); 452 return; 453 } 454 455 s = s - floor( s ); 456 t = t - floor( t ); 457 458 is = s * shader->width; 459 it = t * shader->height; 460 461 image = shader->pixels + 4 * ( it * shader->width + is ); 462 463 // alpha filter 464 b = image[3]; 465 466 // alpha test makes this a binary option 467 b = b < 128 ? 0 : 255; 468 469 tr->trace->filter[0] = tr->trace->filter[0] * (255-b) / 255; 470 tr->trace->filter[1] = tr->trace->filter[1] * (255-b) / 255; 471 tr->trace->filter[2] = tr->trace->filter[2] * (255-b) / 255; 472 } 473 474 475 /* 476 ==================== 477 TraceAgainstFacet 478 479 Shader is needed for translucent surfaces 480 ==================== 481 */ 482 void TraceAgainstFacet( traceWork_t *tr, shaderInfo_t *shader, cFacet_t *facet ) { 483 int j; 484 float d1, d2, d, f; 485 vec3_t point; 486 float dist; 487 488 // ignore degenerate facets 489 if ( facet->numBoundaries < 3 ) { 490 return; 491 } 492 493 dist = facet->surface[3]; 494 495 // compare the trace endpoints against the facet plane 496 d1 = DotProduct( tr->start, facet->surface ) - dist; 497 if ( d1 > -1 && d1 < 1 ) { 498 return; // don't self intersect 499 } 500 d2 = DotProduct( tr->end, facet->surface ) - dist; 501 if ( d2 > -1 && d2 < 1 ) { 502 return; // don't self intersect 503 } 504 505 // calculate the intersection fraction 506 f = ( d1 - ON_EPSILON ) / ( d1 - d2 ); 507 if ( f <= 0 ) { 508 return; 509 } 510 if ( f >= tr->trace->hitFraction ) { 511 return; // we have hit something earlier 512 } 513 514 // calculate the intersection point 515 for ( j = 0 ; j < 3 ; j++ ) { 516 point[j] = tr->start[j] + f * ( tr->end[j] - tr->start[j] ); 517 } 518 519 // check the point against the facet boundaries 520 for ( j = 0 ; j < facet->numBoundaries ; j++ ) { 521 // adjust the plane distance apropriately for mins/maxs 522 dist = facet->boundaries[j][3]; 523 524 d = DotProduct( point, facet->boundaries[j] ); 525 if ( d > dist + ON_EPSILON ) { 526 break; // outside the bounds 527 } 528 } 529 530 if ( j != facet->numBoundaries ) { 531 return; // we are outside the bounds of the facet 532 } 533 534 // we hit this facet 535 536 // if this is a transparent surface, calculate filter value 537 if ( shader->surfaceFlags & SURF_ALPHASHADOW ) { 538 SetFacetFilter( tr, shader, facet, point ); 539 } else { 540 // completely opaque 541 VectorClear( tr->trace->filter ); 542 tr->trace->hitFraction = f; 543 } 544 545 // VectorCopy( facet->surface, tr->trace->plane.normal ); 546 // tr->trace->plane.dist = facet->surface[3]; 547 } 548 549 550 /* 551 =============================================================== 552 553 LINE TRACING 554 555 =============================================================== 556 */ 557 558 559 #define TRACE_ON_EPSILON 0.1 560 561 typedef struct tnode_s 562 { 563 int type; 564 vec3_t normal; 565 float dist; 566 int children[2]; 567 int planeNum; 568 } tnode_t; 569 570 #define MAX_TNODES (MAX_MAP_NODES*4) 571 tnode_t *tnodes, *tnode_p; 572 573 /* 574 ============== 575 MakeTnode 576 577 Converts the disk node structure into the efficient tracing structure 578 ============== 579 */ 580 void MakeTnode (int nodenum) 581 { 582 tnode_t *t; 583 dplane_t *plane; 584 int i; 585 dnode_t *node; 586 int leafNum; 587 588 t = tnode_p++; 589 590 node = dnodes + nodenum; 591 plane = dplanes + node->planeNum; 592 593 t->planeNum = node->planeNum; 594 t->type = PlaneTypeForNormal( plane->normal ); 595 VectorCopy (plane->normal, t->normal); 596 t->dist = plane->dist; 597 598 for (i=0 ; i<2 ; i++) 599 { 600 if (node->children[i] < 0) { 601 leafNum = -node->children[i] - 1; 602 if ( dleafs[leafNum].cluster == -1 ) { 603 // solid 604 t->children[i] = leafNum | ( 1 << 31 ) | ( 1 << 30 ); 605 } else { 606 t->children[i] = leafNum | ( 1 << 31 ); 607 } 608 } else { 609 t->children[i] = tnode_p - tnodes; 610 MakeTnode (node->children[i]); 611 } 612 } 613 614 } 615 616 /* 617 ============= 618 InitTrace 619 620 Loads the node structure out of a .bsp file to be used for light occlusion 621 ============= 622 */ 623 void InitTrace( void ) { 624 // 32 byte align the structs 625 tnodes = malloc( (MAX_TNODES+1) * sizeof(tnode_t)); 626 tnodes = (tnode_t *)(((int)tnodes + 31)&~31); 627 tnode_p = tnodes; 628 629 MakeTnode (0); 630 631 InitSurfacesForTesting(); 632 } 633 634 635 /* 636 =================== 637 PointInSolid 638 =================== 639 */ 640 qboolean PointInSolid_r( vec3_t start, int node ) { 641 tnode_t *tnode; 642 float front; 643 644 while ( !(node & (1<<31) ) ) { 645 tnode = &tnodes[node]; 646 switch (tnode->type) { 647 case PLANE_X: 648 front = start[0] - tnode->dist; 649 break; 650 case PLANE_Y: 651 front = start[1] - tnode->dist; 652 break; 653 case PLANE_Z: 654 front = start[2] - tnode->dist; 655 break; 656 default: 657 front = (start[0]*tnode->normal[0] + start[1]*tnode->normal[1] + start[2]*tnode->normal[2]) - tnode->dist; 658 break; 659 } 660 661 if ( front == 0 ) { 662 // exactly on node, must check both sides 663 return (qboolean) ( PointInSolid_r( start, tnode->children[0] ) 664 | PointInSolid_r( start, tnode->children[1] ) ); 665 } 666 667 if ( front > 0 ) { 668 node = tnode->children[0]; 669 } else { 670 node = tnode->children[1]; 671 } 672 } 673 674 if ( node & ( 1 << 30 ) ) { 675 return qtrue; 676 } 677 return qfalse; 678 } 679 680 /* 681 ============= 682 PointInSolid 683 684 ============= 685 */ 686 qboolean PointInSolid( vec3_t start ) { 687 return PointInSolid_r( start, 0 ); 688 } 689 690 691 /* 692 ============= 693 TraceLine_r 694 695 Returns qtrue if something is hit and tracing can stop 696 ============= 697 */ 698 int TraceLine_r( int node, const vec3_t start, const vec3_t stop, traceWork_t *tw ) { 699 tnode_t *tnode; 700 float front, back; 701 vec3_t mid; 702 float frac; 703 int side; 704 int r; 705 706 if (node & (1<<31)) { 707 if (node & ( 1 << 30 ) ) { 708 VectorCopy (start, tw->trace->hit); 709 tw->trace->passSolid = qtrue; 710 return qtrue; 711 } else { 712 // save the node off for more exact testing 713 if ( tw->numOpenLeafs == MAX_MAP_LEAFS ) { 714 return qfalse; 715 } 716 tw->openLeafNumbers[ tw->numOpenLeafs ] = node & ~(3 << 30); 717 tw->numOpenLeafs++; 718 return qfalse; 719 } 720 } 721 722 tnode = &tnodes[node]; 723 switch (tnode->type) { 724 case PLANE_X: 725 front = start[0] - tnode->dist; 726 back = stop[0] - tnode->dist; 727 break; 728 case PLANE_Y: 729 front = start[1] - tnode->dist; 730 back = stop[1] - tnode->dist; 731 break; 732 case PLANE_Z: 733 front = start[2] - tnode->dist; 734 back = stop[2] - tnode->dist; 735 break; 736 default: 737 front = (start[0]*tnode->normal[0] + start[1]*tnode->normal[1] + start[2]*tnode->normal[2]) - tnode->dist; 738 back = (stop[0]*tnode->normal[0] + stop[1]*tnode->normal[1] + stop[2]*tnode->normal[2]) - tnode->dist; 739 break; 740 } 741 742 if (front >= -TRACE_ON_EPSILON && back >= -TRACE_ON_EPSILON) { 743 return TraceLine_r (tnode->children[0], start, stop, tw); 744 } 745 746 if (front < TRACE_ON_EPSILON && back < TRACE_ON_EPSILON) { 747 return TraceLine_r (tnode->children[1], start, stop, tw); 748 } 749 750 side = front < 0; 751 752 frac = front / (front-back); 753 754 mid[0] = start[0] + (stop[0] - start[0])*frac; 755 mid[1] = start[1] + (stop[1] - start[1])*frac; 756 mid[2] = start[2] + (stop[2] - start[2])*frac; 757 758 r = TraceLine_r (tnode->children[side], start, mid, tw); 759 760 if (r) { 761 return r; 762 } 763 764 // trace->planeNum = tnode->planeNum; 765 return TraceLine_r (tnode->children[!side], mid, stop, tw); 766 } 767 768 //========================================================================================== 769 770 771 /* 772 ================ 773 SphereCull 774 ================ 775 */ 776 qboolean SphereCull( vec3_t start, vec3_t stop, vec3_t origin, float radius ) { 777 vec3_t v; 778 float d; 779 vec3_t dir; 780 float len; 781 vec3_t on; 782 783 VectorSubtract( stop, start, dir ); 784 len = VectorNormalize( dir, dir ); 785 786 VectorSubtract( origin, start, v ); 787 d = DotProduct( v, dir ); 788 if ( d > len + radius ) { 789 return qtrue; // too far ahead 790 } 791 if ( d < -radius ) { 792 return qtrue; // too far behind 793 } 794 VectorMA( start, d, dir, on ); 795 796 VectorSubtract( on, origin, v ); 797 798 len = VectorLength( v ); 799 800 if ( len > radius ) { 801 return qtrue; // too far to the side 802 } 803 804 return qfalse; // must be traced against 805 } 806 807 /* 808 ================ 809 TraceAgainstSurface 810 ================ 811 */ 812 void TraceAgainstSurface( traceWork_t *tw, surfaceTest_t *surf ) { 813 int i; 814 815 // if surfaces are trans 816 if ( SphereCull( tw->start, tw->end, surf->origin, surf->radius ) ) { 817 if ( numthreads == 1 ) { 818 c_cullTrace++; 819 } 820 return; 821 } 822 823 if ( numthreads == 1 ) { 824 c_testTrace++; 825 c_testFacets += surf->numFacets; 826 } 827 828 /* 829 // MrE: backface culling 830 if (!surf->patch && surf->numFacets) { 831 // if the surface does not cast an alpha shadow 832 if ( !(surf->shader->surfaceFlags & SURF_ALPHASHADOW) ) { 833 vec3_t vec; 834 VectorSubtract(tw->end, tw->start, vec); 835 if (DotProduct(vec, surf->facets->surface) > 0) 836 return; 837 } 838 } 839 */ 840 841 // test against each facet 842 for ( i = 0 ; i < surf->numFacets ; i++ ) { 843 TraceAgainstFacet( tw, surf->shader, surf->facets + i ); 844 } 845 } 846 847 /* 848 ============= 849 TraceLine 850 851 Follow the trace just through the solid leafs first, and only 852 if it passes that, trace against the objects inside the empty leafs 853 Returns qtrue if the trace hit any 854 855 traceWork_t is only a parameter to crutch up poor large local allocations on 856 winNT and macOS. It should be allocated in the worker function, but never 857 looked at. 858 859 leave testAll false if all you care about is if it hit anything at all. 860 if you need to know the exact first point of impact (for a sun trace), set 861 testAll to true 862 ============= 863 */ 864 extern qboolean patchshadows; 865 866 void TraceLine( const vec3_t start, const vec3_t stop, trace_t *trace, qboolean testAll, traceWork_t *tw ) { 867 int r; 868 int i, j; 869 dleaf_t *leaf; 870 float oldHitFrac; 871 surfaceTest_t *test; 872 int surfaceNum; 873 byte surfaceTested[MAX_MAP_DRAW_SURFS/8]; 874 ; 875 876 if ( numthreads == 1 ) { 877 c_totalTrace++; 878 } 879 880 // assume all light gets through, unless the ray crosses 881 // a translucent surface 882 trace->filter[0] = 1.0; 883 trace->filter[1] = 1.0; 884 trace->filter[2] = 1.0; 885 886 VectorCopy( start, tw->start ); 887 VectorCopy( stop, tw->end ); 888 tw->trace = trace; 889 890 tw->numOpenLeafs = 0; 891 892 trace->passSolid = qfalse; 893 trace->hitFraction = 1.0; 894 895 r = TraceLine_r( 0, start, stop, tw ); 896 897 // if we hit a solid leaf, stop without testing the leaf 898 // surfaces. Note that the plane and endpoint might not 899 // be the first solid intersection along the ray. 900 if ( r && !testAll ) { 901 return; 902 } 903 904 if ( noSurfaces ) { 905 return; 906 } 907 908 memset( surfaceTested, 0, (numDrawSurfaces+7)/8 ); 909 oldHitFrac = trace->hitFraction; 910 911 for ( i = 0 ; i < tw->numOpenLeafs ; i++ ) { 912 leaf = &dleafs[ tw->openLeafNumbers[ i ] ]; 913 for ( j = 0 ; j < leaf->numLeafSurfaces ; j++ ) { 914 surfaceNum = dleafsurfaces[ leaf->firstLeafSurface + j ]; 915 916 // make sure we don't test the same ray against a surface more than once 917 if ( surfaceTested[ surfaceNum>>3 ] & ( 1 << ( surfaceNum & 7) ) ) { 918 continue; 919 } 920 surfaceTested[ surfaceNum>>3 ] |= ( 1 << ( surfaceNum & 7 ) ); 921 922 test = surfaceTest[ surfaceNum ]; 923 if ( !test ) { 924 continue; 925 } 926 // 927 if ( !tw->patchshadows && test->patch ) { 928 continue; 929 } 930 TraceAgainstSurface( tw, test ); 931 } 932 933 // if the trace is now solid, we can't possibly hit anything closer 934 if ( trace->hitFraction < oldHitFrac ) { 935 trace->passSolid = qtrue; 936 break; 937 } 938 } 939 940 for ( i = 0 ; i < 3 ; i++ ) { 941 trace->hit[i] = start[i] + ( stop[i] - start[i] ) * trace->hitFraction; 942 } 943 } 944