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