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 Quake III Arena source code; 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 */
R_CullTriSurf(srfTriangles_t * cv)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 */
R_CullGrid(srfGridMesh_t * cv)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 */
R_CullSurface(surfaceType_t * surface,shader_t * shader)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
R_DlightFace(srfSurfaceFace_t * face,int dlightBits)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
R_DlightGrid(srfGridMesh_t * grid,int dlightBits)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
R_DlightTrisurf(srfTriangles_t * surf,int dlightBits)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 */
R_DlightSurface(msurface_t * surf,int dlightBits)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 */
R_AddWorldSurface(msurface_t * surf,int dlightBits)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 */
R_AddBrushModelSurfaces(trRefEntity_t * ent)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 */
R_RecursiveWorldNode(mnode_t * node,int planeBits,int dlightBits)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 */
R_PointInLeaf(const vec3_t p)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 */
R_ClusterPVS(int cluster)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 */
R_inPVS(const vec3_t p1,const vec3_t p2)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 */
R_MarkLeaves(void)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 */
R_AddWorldSurfaces(void)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 }
669