tr_world.c (15062B)
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 "tr_local.h" 23 24 25 26 /* 27 ================= 28 R_CullTriSurf 29 30 Returns true if the grid is completely culled away. 31 Also sets the clipped hint bit in tess 32 ================= 33 */ 34 static qboolean R_CullTriSurf( srfTriangles_t *cv ) { 35 int boxCull; 36 37 boxCull = R_CullLocalBox( cv->bounds ); 38 39 if ( boxCull == CULL_OUT ) { 40 return qtrue; 41 } 42 return qfalse; 43 } 44 45 /* 46 ================= 47 R_CullGrid 48 49 Returns true if the grid is completely culled away. 50 Also sets the clipped hint bit in tess 51 ================= 52 */ 53 static qboolean R_CullGrid( srfGridMesh_t *cv ) { 54 int boxCull; 55 int sphereCull; 56 57 if ( r_nocurves->integer ) { 58 return qtrue; 59 } 60 61 if ( tr.currentEntityNum != ENTITYNUM_WORLD ) { 62 sphereCull = R_CullLocalPointAndRadius( cv->localOrigin, cv->meshRadius ); 63 } else { 64 sphereCull = R_CullPointAndRadius( cv->localOrigin, cv->meshRadius ); 65 } 66 boxCull = CULL_OUT; 67 68 // check for trivial reject 69 if ( sphereCull == CULL_OUT ) 70 { 71 tr.pc.c_sphere_cull_patch_out++; 72 return qtrue; 73 } 74 // check bounding box if necessary 75 else if ( sphereCull == CULL_CLIP ) 76 { 77 tr.pc.c_sphere_cull_patch_clip++; 78 79 boxCull = R_CullLocalBox( cv->meshBounds ); 80 81 if ( boxCull == CULL_OUT ) 82 { 83 tr.pc.c_box_cull_patch_out++; 84 return qtrue; 85 } 86 else if ( boxCull == CULL_IN ) 87 { 88 tr.pc.c_box_cull_patch_in++; 89 } 90 else 91 { 92 tr.pc.c_box_cull_patch_clip++; 93 } 94 } 95 else 96 { 97 tr.pc.c_sphere_cull_patch_in++; 98 } 99 100 return qfalse; 101 } 102 103 104 /* 105 ================ 106 R_CullSurface 107 108 Tries to back face cull surfaces before they are lighted or 109 added to the sorting list. 110 111 This will also allow mirrors on both sides of a model without recursion. 112 ================ 113 */ 114 static qboolean R_CullSurface( surfaceType_t *surface, shader_t *shader ) { 115 srfSurfaceFace_t *sface; 116 float d; 117 118 if ( r_nocull->integer ) { 119 return qfalse; 120 } 121 122 if ( *surface == SF_GRID ) { 123 return R_CullGrid( (srfGridMesh_t *)surface ); 124 } 125 126 if ( *surface == SF_TRIANGLES ) { 127 return R_CullTriSurf( (srfTriangles_t *)surface ); 128 } 129 130 if ( *surface != SF_FACE ) { 131 return qfalse; 132 } 133 134 if ( shader->cullType == CT_TWO_SIDED ) { 135 return qfalse; 136 } 137 138 // face culling 139 if ( !r_facePlaneCull->integer ) { 140 return qfalse; 141 } 142 143 sface = ( srfSurfaceFace_t * ) surface; 144 d = DotProduct (tr.or.viewOrigin, sface->plane.normal); 145 146 // don't cull exactly on the plane, because there are levels of rounding 147 // through the BSP, ICD, and hardware that may cause pixel gaps if an 148 // epsilon isn't allowed here 149 if ( shader->cullType == CT_FRONT_SIDED ) { 150 if ( d < sface->plane.dist - 8 ) { 151 return qtrue; 152 } 153 } else { 154 if ( d > sface->plane.dist + 8 ) { 155 return qtrue; 156 } 157 } 158 159 return qfalse; 160 } 161 162 163 static int R_DlightFace( srfSurfaceFace_t *face, int dlightBits ) { 164 float d; 165 int i; 166 dlight_t *dl; 167 168 for ( i = 0 ; i < tr.refdef.num_dlights ; i++ ) { 169 if ( ! ( dlightBits & ( 1 << i ) ) ) { 170 continue; 171 } 172 dl = &tr.refdef.dlights[i]; 173 d = DotProduct( dl->origin, face->plane.normal ) - face->plane.dist; 174 if ( d < -dl->radius || d > dl->radius ) { 175 // dlight doesn't reach the plane 176 dlightBits &= ~( 1 << i ); 177 } 178 } 179 180 if ( !dlightBits ) { 181 tr.pc.c_dlightSurfacesCulled++; 182 } 183 184 face->dlightBits[ tr.smpFrame ] = dlightBits; 185 return dlightBits; 186 } 187 188 static int R_DlightGrid( srfGridMesh_t *grid, int dlightBits ) { 189 int i; 190 dlight_t *dl; 191 192 for ( i = 0 ; i < tr.refdef.num_dlights ; i++ ) { 193 if ( ! ( dlightBits & ( 1 << i ) ) ) { 194 continue; 195 } 196 dl = &tr.refdef.dlights[i]; 197 if ( dl->origin[0] - dl->radius > grid->meshBounds[1][0] 198 || dl->origin[0] + dl->radius < grid->meshBounds[0][0] 199 || dl->origin[1] - dl->radius > grid->meshBounds[1][1] 200 || dl->origin[1] + dl->radius < grid->meshBounds[0][1] 201 || dl->origin[2] - dl->radius > grid->meshBounds[1][2] 202 || dl->origin[2] + dl->radius < grid->meshBounds[0][2] ) { 203 // dlight doesn't reach the bounds 204 dlightBits &= ~( 1 << i ); 205 } 206 } 207 208 if ( !dlightBits ) { 209 tr.pc.c_dlightSurfacesCulled++; 210 } 211 212 grid->dlightBits[ tr.smpFrame ] = dlightBits; 213 return dlightBits; 214 } 215 216 217 static int R_DlightTrisurf( srfTriangles_t *surf, int dlightBits ) { 218 // FIXME: more dlight culling to trisurfs... 219 surf->dlightBits[ tr.smpFrame ] = dlightBits; 220 return dlightBits; 221 #if 0 222 int i; 223 dlight_t *dl; 224 225 for ( i = 0 ; i < tr.refdef.num_dlights ; i++ ) { 226 if ( ! ( dlightBits & ( 1 << i ) ) ) { 227 continue; 228 } 229 dl = &tr.refdef.dlights[i]; 230 if ( dl->origin[0] - dl->radius > grid->meshBounds[1][0] 231 || dl->origin[0] + dl->radius < grid->meshBounds[0][0] 232 || dl->origin[1] - dl->radius > grid->meshBounds[1][1] 233 || dl->origin[1] + dl->radius < grid->meshBounds[0][1] 234 || dl->origin[2] - dl->radius > grid->meshBounds[1][2] 235 || dl->origin[2] + dl->radius < grid->meshBounds[0][2] ) { 236 // dlight doesn't reach the bounds 237 dlightBits &= ~( 1 << i ); 238 } 239 } 240 241 if ( !dlightBits ) { 242 tr.pc.c_dlightSurfacesCulled++; 243 } 244 245 grid->dlightBits[ tr.smpFrame ] = dlightBits; 246 return dlightBits; 247 #endif 248 } 249 250 /* 251 ==================== 252 R_DlightSurface 253 254 The given surface is going to be drawn, and it touches a leaf 255 that is touched by one or more dlights, so try to throw out 256 more dlights if possible. 257 ==================== 258 */ 259 static int R_DlightSurface( msurface_t *surf, int dlightBits ) { 260 if ( *surf->data == SF_FACE ) { 261 dlightBits = R_DlightFace( (srfSurfaceFace_t *)surf->data, dlightBits ); 262 } else if ( *surf->data == SF_GRID ) { 263 dlightBits = R_DlightGrid( (srfGridMesh_t *)surf->data, dlightBits ); 264 } else if ( *surf->data == SF_TRIANGLES ) { 265 dlightBits = R_DlightTrisurf( (srfTriangles_t *)surf->data, dlightBits ); 266 } else { 267 dlightBits = 0; 268 } 269 270 if ( dlightBits ) { 271 tr.pc.c_dlightSurfaces++; 272 } 273 274 return dlightBits; 275 } 276 277 278 279 /* 280 ====================== 281 R_AddWorldSurface 282 ====================== 283 */ 284 static void R_AddWorldSurface( msurface_t *surf, int dlightBits ) { 285 if ( surf->viewCount == tr.viewCount ) { 286 return; // already in this view 287 } 288 289 surf->viewCount = tr.viewCount; 290 // FIXME: bmodel fog? 291 292 // try to cull before dlighting or adding 293 if ( R_CullSurface( surf->data, surf->shader ) ) { 294 return; 295 } 296 297 // check for dlighting 298 if ( dlightBits ) { 299 dlightBits = R_DlightSurface( surf, dlightBits ); 300 dlightBits = ( dlightBits != 0 ); 301 } 302 303 R_AddDrawSurf( surf->data, surf->shader, surf->fogIndex, dlightBits ); 304 } 305 306 /* 307 ============================================================= 308 309 BRUSH MODELS 310 311 ============================================================= 312 */ 313 314 /* 315 ================= 316 R_AddBrushModelSurfaces 317 ================= 318 */ 319 void R_AddBrushModelSurfaces ( trRefEntity_t *ent ) { 320 bmodel_t *bmodel; 321 int clip; 322 model_t *pModel; 323 int i; 324 325 pModel = R_GetModelByHandle( ent->e.hModel ); 326 327 bmodel = pModel->bmodel; 328 329 clip = R_CullLocalBox( bmodel->bounds ); 330 if ( clip == CULL_OUT ) { 331 return; 332 } 333 334 R_DlightBmodel( bmodel ); 335 336 for ( i = 0 ; i < bmodel->numSurfaces ; i++ ) { 337 R_AddWorldSurface( bmodel->firstSurface + i, tr.currentEntity->needDlights ); 338 } 339 } 340 341 342 /* 343 ============================================================= 344 345 WORLD MODEL 346 347 ============================================================= 348 */ 349 350 351 /* 352 ================ 353 R_RecursiveWorldNode 354 ================ 355 */ 356 static void R_RecursiveWorldNode( mnode_t *node, int planeBits, int dlightBits ) { 357 358 do { 359 int newDlights[2]; 360 361 // if the node wasn't marked as potentially visible, exit 362 if (node->visframe != tr.visCount) { 363 return; 364 } 365 366 // if the bounding volume is outside the frustum, nothing 367 // inside can be visible OPTIMIZE: don't do this all the way to leafs? 368 369 if ( !r_nocull->integer ) { 370 int r; 371 372 if ( planeBits & 1 ) { 373 r = BoxOnPlaneSide(node->mins, node->maxs, &tr.viewParms.frustum[0]); 374 if (r == 2) { 375 return; // culled 376 } 377 if ( r == 1 ) { 378 planeBits &= ~1; // all descendants will also be in front 379 } 380 } 381 382 if ( planeBits & 2 ) { 383 r = BoxOnPlaneSide(node->mins, node->maxs, &tr.viewParms.frustum[1]); 384 if (r == 2) { 385 return; // culled 386 } 387 if ( r == 1 ) { 388 planeBits &= ~2; // all descendants will also be in front 389 } 390 } 391 392 if ( planeBits & 4 ) { 393 r = BoxOnPlaneSide(node->mins, node->maxs, &tr.viewParms.frustum[2]); 394 if (r == 2) { 395 return; // culled 396 } 397 if ( r == 1 ) { 398 planeBits &= ~4; // all descendants will also be in front 399 } 400 } 401 402 if ( planeBits & 8 ) { 403 r = BoxOnPlaneSide(node->mins, node->maxs, &tr.viewParms.frustum[3]); 404 if (r == 2) { 405 return; // culled 406 } 407 if ( r == 1 ) { 408 planeBits &= ~8; // all descendants will also be in front 409 } 410 } 411 412 } 413 414 if ( node->contents != -1 ) { 415 break; 416 } 417 418 // node is just a decision point, so go down both sides 419 // since we don't care about sort orders, just go positive to negative 420 421 // determine which dlights are needed 422 newDlights[0] = 0; 423 newDlights[1] = 0; 424 if ( dlightBits ) { 425 int i; 426 427 for ( i = 0 ; i < tr.refdef.num_dlights ; i++ ) { 428 dlight_t *dl; 429 float dist; 430 431 if ( dlightBits & ( 1 << i ) ) { 432 dl = &tr.refdef.dlights[i]; 433 dist = DotProduct( dl->origin, node->plane->normal ) - node->plane->dist; 434 435 if ( dist > -dl->radius ) { 436 newDlights[0] |= ( 1 << i ); 437 } 438 if ( dist < dl->radius ) { 439 newDlights[1] |= ( 1 << i ); 440 } 441 } 442 } 443 } 444 445 // recurse down the children, front side first 446 R_RecursiveWorldNode (node->children[0], planeBits, newDlights[0] ); 447 448 // tail recurse 449 node = node->children[1]; 450 dlightBits = newDlights[1]; 451 } while ( 1 ); 452 453 { 454 // leaf node, so add mark surfaces 455 int c; 456 msurface_t *surf, **mark; 457 458 tr.pc.c_leafs++; 459 460 // add to z buffer bounds 461 if ( node->mins[0] < tr.viewParms.visBounds[0][0] ) { 462 tr.viewParms.visBounds[0][0] = node->mins[0]; 463 } 464 if ( node->mins[1] < tr.viewParms.visBounds[0][1] ) { 465 tr.viewParms.visBounds[0][1] = node->mins[1]; 466 } 467 if ( node->mins[2] < tr.viewParms.visBounds[0][2] ) { 468 tr.viewParms.visBounds[0][2] = node->mins[2]; 469 } 470 471 if ( node->maxs[0] > tr.viewParms.visBounds[1][0] ) { 472 tr.viewParms.visBounds[1][0] = node->maxs[0]; 473 } 474 if ( node->maxs[1] > tr.viewParms.visBounds[1][1] ) { 475 tr.viewParms.visBounds[1][1] = node->maxs[1]; 476 } 477 if ( node->maxs[2] > tr.viewParms.visBounds[1][2] ) { 478 tr.viewParms.visBounds[1][2] = node->maxs[2]; 479 } 480 481 // add the individual surfaces 482 mark = node->firstmarksurface; 483 c = node->nummarksurfaces; 484 while (c--) { 485 // the surface may have already been added if it 486 // spans multiple leafs 487 surf = *mark; 488 R_AddWorldSurface( surf, dlightBits ); 489 mark++; 490 } 491 } 492 493 } 494 495 496 /* 497 =============== 498 R_PointInLeaf 499 =============== 500 */ 501 static mnode_t *R_PointInLeaf( const vec3_t p ) { 502 mnode_t *node; 503 float d; 504 cplane_t *plane; 505 506 if ( !tr.world ) { 507 ri.Error (ERR_DROP, "R_PointInLeaf: bad model"); 508 } 509 510 node = tr.world->nodes; 511 while( 1 ) { 512 if (node->contents != -1) { 513 break; 514 } 515 plane = node->plane; 516 d = DotProduct (p,plane->normal) - plane->dist; 517 if (d > 0) { 518 node = node->children[0]; 519 } else { 520 node = node->children[1]; 521 } 522 } 523 524 return node; 525 } 526 527 /* 528 ============== 529 R_ClusterPVS 530 ============== 531 */ 532 static const byte *R_ClusterPVS (int cluster) { 533 if (!tr.world || !tr.world->vis || cluster < 0 || cluster >= tr.world->numClusters ) { 534 return tr.world->novis; 535 } 536 537 return tr.world->vis + cluster * tr.world->clusterBytes; 538 } 539 540 /* 541 ================= 542 R_inPVS 543 ================= 544 */ 545 qboolean R_inPVS( const vec3_t p1, const vec3_t p2 ) { 546 mnode_t *leaf; 547 byte *vis; 548 549 leaf = R_PointInLeaf( p1 ); 550 vis = CM_ClusterPVS( leaf->cluster ); 551 leaf = R_PointInLeaf( p2 ); 552 553 if ( !(vis[leaf->cluster>>3] & (1<<(leaf->cluster&7))) ) { 554 return qfalse; 555 } 556 return qtrue; 557 } 558 559 /* 560 =============== 561 R_MarkLeaves 562 563 Mark the leaves and nodes that are in the PVS for the current 564 cluster 565 =============== 566 */ 567 static void R_MarkLeaves (void) { 568 const byte *vis; 569 mnode_t *leaf, *parent; 570 int i; 571 int cluster; 572 573 // lockpvs lets designers walk around to determine the 574 // extent of the current pvs 575 if ( r_lockpvs->integer ) { 576 return; 577 } 578 579 // current viewcluster 580 leaf = R_PointInLeaf( tr.viewParms.pvsOrigin ); 581 cluster = leaf->cluster; 582 583 // if the cluster is the same and the area visibility matrix 584 // hasn't changed, we don't need to mark everything again 585 586 // if r_showcluster was just turned on, remark everything 587 if ( tr.viewCluster == cluster && !tr.refdef.areamaskModified 588 && !r_showcluster->modified ) { 589 return; 590 } 591 592 if ( r_showcluster->modified || r_showcluster->integer ) { 593 r_showcluster->modified = qfalse; 594 if ( r_showcluster->integer ) { 595 ri.Printf( PRINT_ALL, "cluster:%i area:%i\n", cluster, leaf->area ); 596 } 597 } 598 599 tr.visCount++; 600 tr.viewCluster = cluster; 601 602 if ( r_novis->integer || tr.viewCluster == -1 ) { 603 for (i=0 ; i<tr.world->numnodes ; i++) { 604 if (tr.world->nodes[i].contents != CONTENTS_SOLID) { 605 tr.world->nodes[i].visframe = tr.visCount; 606 } 607 } 608 return; 609 } 610 611 vis = R_ClusterPVS (tr.viewCluster); 612 613 for (i=0,leaf=tr.world->nodes ; i<tr.world->numnodes ; i++, leaf++) { 614 cluster = leaf->cluster; 615 if ( cluster < 0 || cluster >= tr.world->numClusters ) { 616 continue; 617 } 618 619 // check general pvs 620 if ( !(vis[cluster>>3] & (1<<(cluster&7))) ) { 621 continue; 622 } 623 624 // check for door connection 625 if ( (tr.refdef.areamask[leaf->area>>3] & (1<<(leaf->area&7)) ) ) { 626 continue; // not visible 627 } 628 629 parent = leaf; 630 do { 631 if (parent->visframe == tr.visCount) 632 break; 633 parent->visframe = tr.visCount; 634 parent = parent->parent; 635 } while (parent); 636 } 637 } 638 639 640 /* 641 ============= 642 R_AddWorldSurfaces 643 ============= 644 */ 645 void R_AddWorldSurfaces (void) { 646 if ( !r_drawworld->integer ) { 647 return; 648 } 649 650 if ( tr.refdef.rdflags & RDF_NOWORLDMODEL ) { 651 return; 652 } 653 654 tr.currentEntityNum = ENTITYNUM_WORLD; 655 tr.shiftedEntityNum = tr.currentEntityNum << QSORT_ENTITYNUM_SHIFT; 656 657 // determine which leaves are in the PVS / areamask 658 R_MarkLeaves (); 659 660 // clear out the visible min/max 661 ClearBounds( tr.viewParms.visBounds[0], tr.viewParms.visBounds[1] ); 662 663 // perform frustum culling and add all the potentially visible surfaces 664 if ( tr.refdef.num_dlights > 32 ) { 665 tr.refdef.num_dlights = 32 ; 666 } 667 R_RecursiveWorldNode( tr.world->nodes, 15, ( 1 << tr.refdef.num_dlights ) - 1 ); 668 }