1 /*
2 ===========================================================================
3
4 Return to Castle Wolfenstein multiplayer 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 multiplayer GPL Source Code (RTCW MP Source Code).
8
9 RTCW MP 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 MP 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 MP Source Code. If not, see <http://www.gnu.org/licenses/>.
21
22 In addition, the RTCW MP 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 MP 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,shader_t * shader,int dlightBits)283 static void R_AddWorldSurface( msurface_t *surf, shader_t *shader, 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, 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 R_AddDrawSurf( surf->data, shader, surf->fogIndex, dlightBits );
303 }
304
305 /*
306 =============================================================
307
308 BRUSH MODELS
309
310 =============================================================
311 */
312
313 //----(SA) added
314
315 /*
316 =================
317 R_BmodelFogNum
318
319 See if a sprite is inside a fog volume
320 Return positive with /any part/ of the brush falling within a fog volume
321 =================
322 */
R_BmodelFogNum(trRefEntity_t * re,bmodel_t * bmodel)323 int R_BmodelFogNum( trRefEntity_t *re, bmodel_t *bmodel ) {
324 int i, j;
325 fog_t *fog;
326
327 for ( i = 1 ; i < tr.world->numfogs ; i++ ) {
328 fog = &tr.world->fogs[i];
329 for ( j = 0 ; j < 3 ; j++ ) {
330 if ( re->e.origin[j] + bmodel->bounds[0][j] > fog->bounds[1][j] ) {
331 break;
332 }
333 if ( re->e.origin[j] + bmodel->bounds[0][j] < fog->bounds[0][j] ) {
334 break;
335 }
336 }
337 if ( j == 3 ) {
338 return i;
339 }
340 for ( j = 0 ; j < 3 ; j++ ) {
341 if ( re->e.origin[j] + bmodel->bounds[1][j] > fog->bounds[1][j] ) {
342 break;
343 }
344 if ( bmodel->bounds[1][j] < fog->bounds[0][j] ) {
345 break;
346 }
347 }
348 if ( j == 3 ) {
349 return i;
350 }
351 }
352
353 return 0;
354 }
355
356 //----(SA) done
357
358
359 /*
360 =================
361 R_AddBrushModelSurfaces
362 =================
363 */
R_AddBrushModelSurfaces(trRefEntity_t * ent)364 void R_AddBrushModelSurfaces( trRefEntity_t *ent ) {
365 bmodel_t *bmodel;
366 int clip;
367 model_t *pModel;
368 int i;
369 int fognum;
370
371 pModel = R_GetModelByHandle( ent->e.hModel );
372
373 bmodel = pModel->bmodel;
374
375 clip = R_CullLocalBox( bmodel->bounds );
376 if ( clip == CULL_OUT ) {
377 return;
378 }
379
380 R_SetupEntityLighting( &tr.refdef, ent );
381 R_DlightBmodel( bmodel );
382
383 //----(SA) modified
384 // determine if in fog
385 fognum = R_BmodelFogNum( ent, bmodel );
386
387 for ( i = 0 ; i < bmodel->numSurfaces ; i++ ) {
388 ( bmodel->firstSurface + i )->fogIndex = fognum;
389 // Arnout: custom shader support for brushmodels
390 if ( ent->e.customShader ) {
391 R_AddWorldSurface( bmodel->firstSurface + i, R_GetShaderByHandle( ent->e.customShader ), tr.currentEntity->needDlights );
392 } else {
393 R_AddWorldSurface( bmodel->firstSurface + i, ( ( msurface_t * )( bmodel->firstSurface + i ) )->shader, tr.currentEntity->needDlights );
394 }
395 }
396 //----(SA) end
397 }
398
399
400 /*
401 =============================================================
402
403 WORLD MODEL
404
405 =============================================================
406 */
407
408
409 /*
410 ================
411 R_RecursiveWorldNode
412 ================
413 */
R_RecursiveWorldNode(mnode_t * node,unsigned int planeBits,unsigned int dlightBits)414 static void R_RecursiveWorldNode( mnode_t *node, unsigned int planeBits, unsigned int dlightBits ) {
415
416 do {
417 unsigned int newDlights[2];
418
419 // if the node wasn't marked as potentially visible, exit
420 if ( node->visframe != tr.visCount ) {
421 return;
422 }
423
424 // if the bounding volume is outside the frustum, nothing
425 // inside can be visible OPTIMIZE: don't do this all the way to leafs?
426
427 if ( !r_nocull->integer ) {
428 int r;
429
430 if ( planeBits & 1 ) {
431 r = BoxOnPlaneSide( node->mins, node->maxs, &tr.viewParms.frustum[0] );
432 if ( r == 2 ) {
433 return; // culled
434 }
435 if ( r == 1 ) {
436 planeBits &= ~1; // all descendants will also be in front
437 }
438 }
439
440 if ( planeBits & 2 ) {
441 r = BoxOnPlaneSide( node->mins, node->maxs, &tr.viewParms.frustum[1] );
442 if ( r == 2 ) {
443 return; // culled
444 }
445 if ( r == 1 ) {
446 planeBits &= ~2; // all descendants will also be in front
447 }
448 }
449
450 if ( planeBits & 4 ) {
451 r = BoxOnPlaneSide( node->mins, node->maxs, &tr.viewParms.frustum[2] );
452 if ( r == 2 ) {
453 return; // culled
454 }
455 if ( r == 1 ) {
456 planeBits &= ~4; // all descendants will also be in front
457 }
458 }
459
460 if ( planeBits & 8 ) {
461 r = BoxOnPlaneSide( node->mins, node->maxs, &tr.viewParms.frustum[3] );
462 if ( r == 2 ) {
463 return; // culled
464 }
465 if ( r == 1 ) {
466 planeBits &= ~8; // all descendants will also be in front
467 }
468 }
469
470 }
471
472 if ( node->contents != -1 ) {
473 break;
474 }
475
476 // node is just a decision point, so go down both sides
477 // since we don't care about sort orders, just go positive to negative
478 // determine which dlights are needed
479 newDlights[0] = 0;
480 newDlights[1] = 0;
481
482 if ( dlightBits )
483 {
484 int i;
485
486 for ( i = 0 ; i < tr.refdef.num_dlights ; i++ ) {
487 dlight_t *dl;
488 float dist;
489
490 if ( dlightBits & ( 1 << i ) ) {
491 dl = &tr.refdef.dlights[i];
492 dist = DotProduct( dl->origin, node->plane->normal ) - node->plane->dist;
493
494 if ( dist > -dl->radius ) {
495 newDlights[0] |= ( 1 << i );
496 }
497 if ( dist < dl->radius ) {
498 newDlights[1] |= ( 1 << i );
499 }
500 }
501 }
502 }
503
504 // recurse down the children, front side first
505 R_RecursiveWorldNode( node->children[0], planeBits, newDlights[0] );
506
507 // tail recurse
508 node = node->children[1];
509 dlightBits = newDlights[1];
510 } while ( 1 );
511
512 {
513 // leaf node, so add mark surfaces
514 int c;
515 msurface_t *surf, **mark;
516
517 // RF, hack, dlight elimination above is unreliable
518 dlightBits = 0xffffffff;
519
520 tr.pc.c_leafs++;
521
522 // add to z buffer bounds
523 if ( node->mins[0] < tr.viewParms.visBounds[0][0] ) {
524 tr.viewParms.visBounds[0][0] = node->mins[0];
525 }
526 if ( node->mins[1] < tr.viewParms.visBounds[0][1] ) {
527 tr.viewParms.visBounds[0][1] = node->mins[1];
528 }
529 if ( node->mins[2] < tr.viewParms.visBounds[0][2] ) {
530 tr.viewParms.visBounds[0][2] = node->mins[2];
531 }
532
533 if ( node->maxs[0] > tr.viewParms.visBounds[1][0] ) {
534 tr.viewParms.visBounds[1][0] = node->maxs[0];
535 }
536 if ( node->maxs[1] > tr.viewParms.visBounds[1][1] ) {
537 tr.viewParms.visBounds[1][1] = node->maxs[1];
538 }
539 if ( node->maxs[2] > tr.viewParms.visBounds[1][2] ) {
540 tr.viewParms.visBounds[1][2] = node->maxs[2];
541 }
542
543 // add the individual surfaces
544 mark = node->firstmarksurface;
545 c = node->nummarksurfaces;
546 while ( c-- ) {
547 // the surface may have already been added if it
548 // spans multiple leafs
549 surf = *mark;
550 R_AddWorldSurface( surf, surf->shader, dlightBits );
551 mark++;
552 }
553 }
554
555 }
556
557
558 /*
559 ===============
560 R_PointInLeaf
561 ===============
562 */
R_PointInLeaf(vec3_t p)563 static mnode_t *R_PointInLeaf( vec3_t p ) {
564 mnode_t *node;
565 float d;
566 cplane_t *plane;
567
568 if ( !tr.world ) {
569 ri.Error( ERR_DROP, "R_PointInLeaf: bad model" );
570 }
571
572 node = tr.world->nodes;
573 while ( 1 ) {
574 if ( node->contents != -1 ) {
575 break;
576 }
577 plane = node->plane;
578 d = DotProduct( p,plane->normal ) - plane->dist;
579 if ( d > 0 ) {
580 node = node->children[0];
581 } else {
582 node = node->children[1];
583 }
584 }
585
586 return node;
587 }
588
589 /*
590 ==============
591 R_ClusterPVS
592 ==============
593 */
R_ClusterPVS(int cluster)594 static const byte *R_ClusterPVS( int cluster ) {
595 if ( !tr.world->vis || cluster < 0 || cluster >= tr.world->numClusters ) {
596 return tr.world->novis;
597 }
598
599 return tr.world->vis + cluster * tr.world->clusterBytes;
600 }
601
602
603
604 /*
605 ===============
606 R_MarkLeaves
607
608 Mark the leaves and nodes that are in the PVS for the current
609 cluster
610 ===============
611 */
R_MarkLeaves(void)612 static void R_MarkLeaves( void ) {
613 const byte *vis;
614 mnode_t *leaf, *parent;
615 int i;
616 int cluster;
617
618 // lockpvs lets designers walk around to determine the
619 // extent of the current pvs
620 if ( r_lockpvs->integer ) {
621 return;
622 }
623
624 // current viewcluster
625 leaf = R_PointInLeaf( tr.viewParms.pvsOrigin );
626 cluster = leaf->cluster;
627
628 // if the cluster is the same and the area visibility matrix
629 // hasn't changed, we don't need to mark everything again
630
631 // if r_showcluster was just turned on, remark everything
632 if ( tr.viewCluster == cluster && !tr.refdef.areamaskModified
633 && !r_showcluster->modified ) {
634 return;
635 }
636
637 if ( r_showcluster->modified || r_showcluster->integer ) {
638 r_showcluster->modified = qfalse;
639 if ( r_showcluster->integer ) {
640 ri.Printf( PRINT_ALL, "cluster:%i area:%i\n", cluster, leaf->area );
641 }
642 }
643
644 tr.visCount++;
645 tr.viewCluster = cluster;
646
647 if ( r_novis->integer || tr.viewCluster == -1 ) {
648 for ( i = 0 ; i < tr.world->numnodes ; i++ ) {
649 if ( tr.world->nodes[i].contents != CONTENTS_SOLID ) {
650 tr.world->nodes[i].visframe = tr.visCount;
651 }
652 }
653 return;
654 }
655
656 vis = R_ClusterPVS( tr.viewCluster );
657
658 for ( i = 0,leaf = tr.world->nodes ; i < tr.world->numnodes ; i++, leaf++ ) {
659 cluster = leaf->cluster;
660 if ( cluster < 0 || cluster >= tr.world->numClusters ) {
661 continue;
662 }
663
664 // check general pvs
665 if ( !( vis[cluster >> 3] & ( 1 << ( cluster & 7 ) ) ) ) {
666 continue;
667 }
668
669 // check for door connection
670 if ( ( tr.refdef.areamask[leaf->area >> 3] & ( 1 << ( leaf->area & 7 ) ) ) ) {
671 continue; // not visible
672 }
673
674 parent = leaf;
675 do {
676 if ( parent->visframe == tr.visCount ) {
677 break;
678 }
679 parent->visframe = tr.visCount;
680 parent = parent->parent;
681 } while ( parent );
682 }
683 }
684
685
686 /*
687 =============
688 R_AddWorldSurfaces
689 =============
690 */
R_AddWorldSurfaces(void)691 void R_AddWorldSurfaces( void ) {
692 if ( !r_drawworld->integer ) {
693 return;
694 }
695
696 if ( tr.refdef.rdflags & RDF_NOWORLDMODEL ) {
697 return;
698 }
699
700 tr.currentEntityNum = REFENTITYNUM_WORLD;
701 tr.shiftedEntityNum = tr.currentEntityNum << QSORT_REFENTITYNUM_SHIFT;
702
703 // determine which leaves are in the PVS / areamask
704 R_MarkLeaves();
705
706 // clear out the visible min/max
707 ClearBounds( tr.viewParms.visBounds[0], tr.viewParms.visBounds[1] );
708
709 // perform frustum culling and add all the potentially visible surfaces
710 if ( tr.refdef.num_dlights > MAX_DLIGHTS ) {
711 tr.refdef.num_dlights = MAX_DLIGHTS ;
712 }
713 R_RecursiveWorldNode( tr.world->nodes, 15, ( 1ULL << tr.refdef.num_dlights ) - 1 );
714 }
715