1 /*
2 ===========================================================================
3
4 Doom 3 GPL Source Code
5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
6
7 This file is part of the Doom 3 GPL Source Code ("Doom 3 Source Code").
8
9 Doom 3 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 Doom 3 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 Doom 3 Source Code. If not, see <http://www.gnu.org/licenses/>.
21
22 In addition, the Doom 3 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 Doom 3 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 "sys/platform.h"
30 #include "renderer/ModelManager.h"
31
32 #include "tools/compilers/dmap/dmap.h"
33
34 #define TEXTURE_OFFSET_EQUAL_EPSILON 0.005
35 #define TEXTURE_VECTOR_EQUAL_EPSILON 0.001
36
37 /*
38 ===============
39 AddTriListToArea
40
41 The triList is appended to the apropriate optimzeGroup_t,
42 creating a new one if needed.
43 The entire list is assumed to come from the same planar primitive
44 ===============
45 */
AddTriListToArea(uEntity_t * e,mapTri_t * triList,int planeNum,int areaNum,textureVectors_t * texVec)46 static void AddTriListToArea( uEntity_t *e, mapTri_t *triList, int planeNum, int areaNum, textureVectors_t *texVec ) {
47 uArea_t *area;
48 optimizeGroup_t *group;
49 int i, j;
50
51 if ( !triList ) {
52 return;
53 }
54
55 area = &e->areas[areaNum];
56 for ( group = area->groups ; group ; group = group->nextGroup ) {
57 if ( group->material == triList->material
58 && group->planeNum == planeNum
59 && group->mergeGroup == triList->mergeGroup ) {
60 // check the texture vectors
61 for ( i = 0 ; i < 2 ; i++ ) {
62 for ( j = 0 ; j < 3 ; j++ ) {
63 if ( idMath::Fabs( texVec->v[i][j] - group->texVec.v[i][j] ) > TEXTURE_VECTOR_EQUAL_EPSILON ) {
64 break;
65 }
66 }
67 if ( j != 3 ) {
68 break;
69 }
70 if ( idMath::Fabs( texVec->v[i][3] - group->texVec.v[i][3] ) > TEXTURE_OFFSET_EQUAL_EPSILON ) {
71 break;
72 }
73 }
74 if ( i == 2 ) {
75 break; // exact match
76 } else {
77 // different texture offsets
78 i = 1; // just for debugger breakpoint
79 }
80 }
81 }
82
83 if ( !group ) {
84 group = (optimizeGroup_t *)Mem_Alloc( sizeof( *group ) );
85 memset( group, 0, sizeof( *group ) );
86 group->planeNum = planeNum;
87 group->mergeGroup = triList->mergeGroup;
88 group->material = triList->material;
89 group->nextGroup = area->groups;
90 group->texVec = *texVec;
91 area->groups = group;
92 }
93
94 group->triList = MergeTriLists( group->triList, triList );
95 }
96
97 /*
98 ===================
99 TexVecForTri
100 ===================
101 */
TexVecForTri(textureVectors_t * texVec,mapTri_t * tri)102 static void TexVecForTri( textureVectors_t *texVec, mapTri_t *tri ) {
103 float area, inva;
104 idVec3 temp;
105 idVec5 d0, d1;
106 idDrawVert *a, *b, *c;
107
108 a = &tri->v[0];
109 b = &tri->v[1];
110 c = &tri->v[2];
111
112 d0[0] = b->xyz[0] - a->xyz[0];
113 d0[1] = b->xyz[1] - a->xyz[1];
114 d0[2] = b->xyz[2] - a->xyz[2];
115 d0[3] = b->st[0] - a->st[0];
116 d0[4] = b->st[1] - a->st[1];
117
118 d1[0] = c->xyz[0] - a->xyz[0];
119 d1[1] = c->xyz[1] - a->xyz[1];
120 d1[2] = c->xyz[2] - a->xyz[2];
121 d1[3] = c->st[0] - a->st[0];
122 d1[4] = c->st[1] - a->st[1];
123
124 area = d0[3] * d1[4] - d0[4] * d1[3];
125 inva = 1.0 / area;
126
127 temp[0] = (d0[0] * d1[4] - d0[4] * d1[0]) * inva;
128 temp[1] = (d0[1] * d1[4] - d0[4] * d1[1]) * inva;
129 temp[2] = (d0[2] * d1[4] - d0[4] * d1[2]) * inva;
130 temp.Normalize();
131 texVec->v[0].ToVec3() = temp;
132 texVec->v[0][3] = tri->v[0].xyz * texVec->v[0].ToVec3() - tri->v[0].st[0];
133
134 temp[0] = (d0[3] * d1[0] - d0[0] * d1[3]) * inva;
135 temp[1] = (d0[3] * d1[1] - d0[1] * d1[3]) * inva;
136 temp[2] = (d0[3] * d1[2] - d0[2] * d1[3]) * inva;
137 temp.Normalize();
138 texVec->v[1].ToVec3() = temp;
139 texVec->v[1][3] = tri->v[0].xyz * texVec->v[0].ToVec3() - tri->v[0].st[1];
140 }
141
142
143 /*
144 =================
145 TriListForSide
146 =================
147 */
148 //#define SNAP_FLOAT_TO_INT 8
149 #define SNAP_FLOAT_TO_INT 256
150 #define SNAP_INT_TO_FLOAT (1.0/SNAP_FLOAT_TO_INT)
151
TriListForSide(const side_t * s,const idWinding * w)152 mapTri_t *TriListForSide( const side_t *s, const idWinding *w ) {
153 int i, j;
154 idDrawVert *dv;
155 mapTri_t *tri, *triList;
156 const idVec3 *vec;
157 const idMaterial *si;
158
159 si = s->material;
160
161 // skip any generated faces
162 if ( !si ) {
163 return NULL;
164 }
165
166 // don't create faces for non-visible sides
167 if ( !si->SurfaceCastsShadow() && !si->IsDrawn() ) {
168 return NULL;
169 }
170
171 if ( 1 ) {
172 // triangle fan using only the outer verts
173 // this gives the minimum triangle count,
174 // but may have some very distended triangles
175 triList = NULL;
176 for ( i = 2 ; i < w->GetNumPoints() ; i++ ) {
177 tri = AllocTri();
178 tri->material = si;
179 tri->next = triList;
180 triList = tri;
181
182 for ( j = 0 ; j < 3 ; j++ ) {
183 if ( j == 0 ) {
184 vec = &((*w)[0]).ToVec3();
185 } else if ( j == 1 ) {
186 vec = &((*w)[i-1]).ToVec3();
187 } else {
188 vec = &((*w)[i]).ToVec3();
189 }
190
191 dv = tri->v + j;
192 #if 0
193 // round the xyz to a given precision
194 for ( k = 0 ; k < 3 ; k++ ) {
195 dv->xyz[k] = SNAP_INT_TO_FLOAT * floor( vec[k] * SNAP_FLOAT_TO_INT + 0.5 );
196 }
197 #else
198 VectorCopy( *vec, dv->xyz );
199 #endif
200
201 // calculate texture s/t from brush primitive texture matrix
202 dv->st[0] = DotProduct( dv->xyz, s->texVec.v[0] ) + s->texVec.v[0][3];
203 dv->st[1] = DotProduct( dv->xyz, s->texVec.v[1] ) + s->texVec.v[1][3];
204
205 // copy normal
206 dv->normal = dmapGlobals.mapPlanes[s->planenum].Normal();
207 if ( dv->normal.Length() < 0.9 || dv->normal.Length() > 1.1 ) {
208 common->Error( "Bad normal in TriListForSide" );
209 }
210 }
211 }
212 } else {
213 // triangle fan from central point, more verts and tris, but less distended
214 // I use this when debugging some tjunction problems
215 triList = NULL;
216 for ( i = 0 ; i < w->GetNumPoints() ; i++ ) {
217 idVec3 midPoint;
218
219 tri = AllocTri();
220 tri->material = si;
221 tri->next = triList;
222 triList = tri;
223
224 for ( j = 0 ; j < 3 ; j++ ) {
225 if ( j == 0 ) {
226 vec = &midPoint;
227 midPoint = w->GetCenter();
228 } else if ( j == 1 ) {
229 vec = &((*w)[i]).ToVec3();
230 } else {
231 vec = &((*w)[(i+1)%w->GetNumPoints()]).ToVec3();
232 }
233
234 dv = tri->v + j;
235
236 VectorCopy( *vec, dv->xyz );
237
238 // calculate texture s/t from brush primitive texture matrix
239 dv->st[0] = DotProduct( dv->xyz, s->texVec.v[0] ) + s->texVec.v[0][3];
240 dv->st[1] = DotProduct( dv->xyz, s->texVec.v[1] ) + s->texVec.v[1][3];
241
242 // copy normal
243 dv->normal = dmapGlobals.mapPlanes[s->planenum].Normal();
244 if ( dv->normal.Length() < 0.9f || dv->normal.Length() > 1.1f ) {
245 common->Error( "Bad normal in TriListForSide" );
246 }
247 }
248 }
249 }
250
251 // set merge groups if needed, to prevent multiple sides from being
252 // merged into a single surface in the case of gui shaders, mirrors, and autosprites
253 if ( s->material->IsDiscrete() ) {
254 for ( tri = triList ; tri ; tri = tri->next ) {
255 tri->mergeGroup = (void *)s;
256 }
257 }
258
259 return triList;
260 }
261
262 //=================================================================================
263
264 /*
265 ====================
266 ClipSideByTree_r
267
268 Adds non-opaque leaf fragments to the convex hull
269 ====================
270 */
ClipSideByTree_r(idWinding * w,side_t * side,node_t * node)271 static void ClipSideByTree_r( idWinding *w, side_t *side, node_t *node ) {
272 idWinding *front, *back;
273
274 if ( !w ) {
275 return;
276 }
277
278 if ( node->planenum != PLANENUM_LEAF ) {
279 if ( side->planenum == node->planenum ) {
280 ClipSideByTree_r( w, side, node->children[0] );
281 return;
282 }
283 if ( side->planenum == ( node->planenum ^ 1) ) {
284 ClipSideByTree_r( w, side, node->children[1] );
285 return;
286 }
287
288 w->Split( dmapGlobals.mapPlanes[ node->planenum ], ON_EPSILON, &front, &back );
289 delete w;
290
291 ClipSideByTree_r( front, side, node->children[0] );
292 ClipSideByTree_r( back, side, node->children[1] );
293
294 return;
295 }
296
297 // if opaque leaf, don't add
298 if ( !node->opaque ) {
299 if ( !side->visibleHull ) {
300 side->visibleHull = w->Copy();
301 }
302 else {
303 side->visibleHull->AddToConvexHull( w, dmapGlobals.mapPlanes[ side->planenum ].Normal() );
304 }
305 }
306
307 delete w;
308 return;
309 }
310
311
312 /*
313 =====================
314 ClipSidesByTree
315
316 Creates side->visibleHull for all visible sides
317
318 The visible hull for a side will consist of the convex hull of
319 all points in non-opaque clusters, which allows overlaps
320 to be trimmed off automatically.
321 =====================
322 */
ClipSidesByTree(uEntity_t * e)323 void ClipSidesByTree( uEntity_t *e ) {
324 uBrush_t *b;
325 int i;
326 idWinding *w;
327 side_t *side;
328 primitive_t *prim;
329
330 common->Printf( "----- ClipSidesByTree -----\n");
331
332 for ( prim = e->primitives ; prim ; prim = prim->next ) {
333 b = prim->brush;
334 if ( !b ) {
335 // FIXME: other primitives!
336 continue;
337 }
338 for ( i = 0 ; i < b->numsides ; i++ ) {
339 side = &b->sides[i];
340 if ( !side->winding) {
341 continue;
342 }
343 w = side->winding->Copy();
344 side->visibleHull = NULL;
345 ClipSideByTree_r( w, side, e->tree->headnode );
346 // for debugging, we can choose to use the entire original side
347 // but we skip this if the side was completely clipped away
348 if ( side->visibleHull && dmapGlobals.noClipSides ) {
349 delete side->visibleHull;
350 side->visibleHull = side->winding->Copy();
351 }
352 }
353 }
354 }
355
356
357
358 //=================================================================================
359
360 /*
361 ====================
362 ClipTriIntoTree_r
363
364 This is used for adding curve triangles
365 The winding will be freed before it returns
366 ====================
367 */
ClipTriIntoTree_r(idWinding * w,mapTri_t * originalTri,uEntity_t * e,node_t * node)368 void ClipTriIntoTree_r( idWinding *w, mapTri_t *originalTri, uEntity_t *e, node_t *node ) {
369 idWinding *front, *back;
370
371 if ( !w ) {
372 return;
373 }
374
375 if ( node->planenum != PLANENUM_LEAF ) {
376 w->Split( dmapGlobals.mapPlanes[ node->planenum ], ON_EPSILON, &front, &back );
377 delete w;
378
379 ClipTriIntoTree_r( front, originalTri, e, node->children[0] );
380 ClipTriIntoTree_r( back, originalTri, e, node->children[1] );
381
382 return;
383 }
384
385 // if opaque leaf, don't add
386 if ( !node->opaque && node->area >= 0 ) {
387 mapTri_t *list;
388 int planeNum;
389 idPlane plane;
390 textureVectors_t texVec;
391
392 list = WindingToTriList( w, originalTri );
393
394 PlaneForTri( originalTri, plane );
395 planeNum = FindFloatPlane( plane );
396
397 TexVecForTri( &texVec, originalTri );
398
399 AddTriListToArea( e, list, planeNum, node->area, &texVec );
400 }
401
402 delete w;
403 return;
404 }
405
406
407
408 //=============================================================
409
410 /*
411 ====================
412 CheckWindingInAreas_r
413
414 Returns the area number that the winding is in, or
415 -2 if it crosses multiple areas.
416
417 ====================
418 */
CheckWindingInAreas_r(const idWinding * w,node_t * node)419 static int CheckWindingInAreas_r( const idWinding *w, node_t *node ) {
420 idWinding *front, *back;
421
422 if ( !w ) {
423 return -1;
424 }
425
426 if ( node->planenum != PLANENUM_LEAF ) {
427 int a1, a2;
428 #if 0
429 if ( side->planenum == node->planenum ) {
430 return CheckWindingInAreas_r( w, node->children[0] );
431 }
432 if ( side->planenum == ( node->planenum ^ 1) ) {
433 return CheckWindingInAreas_r( w, node->children[1] );
434 }
435 #endif
436 w->Split( dmapGlobals.mapPlanes[ node->planenum ], ON_EPSILON, &front, &back );
437
438 a1 = CheckWindingInAreas_r( front, node->children[0] );
439 delete front;
440 a2 = CheckWindingInAreas_r( back, node->children[1] );
441 delete back;
442
443 if ( a1 == -2 || a2 == -2 ) {
444 return -2; // different
445 }
446 if ( a1 == -1 ) {
447 return a2; // one solid
448 }
449 if ( a2 == -1 ) {
450 return a1; // one solid
451 }
452
453 if ( a1 != a2 ) {
454 return -2; // cross areas
455 }
456 return a1;
457 }
458
459 return node->area;
460 }
461
462
463
464 /*
465 ====================
466 PutWindingIntoAreas_r
467
468 Clips a winding down into the bsp tree, then converts
469 the fragments to triangles and adds them to the area lists
470 ====================
471 */
PutWindingIntoAreas_r(uEntity_t * e,const idWinding * w,side_t * side,node_t * node)472 static void PutWindingIntoAreas_r( uEntity_t *e, const idWinding *w, side_t *side, node_t *node ) {
473 idWinding *front, *back;
474 int area;
475
476 if ( !w ) {
477 return;
478 }
479
480 if ( node->planenum != PLANENUM_LEAF ) {
481 if ( side->planenum == node->planenum ) {
482 PutWindingIntoAreas_r( e, w, side, node->children[0] );
483 return;
484 }
485 if ( side->planenum == ( node->planenum ^ 1) ) {
486 PutWindingIntoAreas_r( e, w, side, node->children[1] );
487 return;
488 }
489
490 // see if we need to split it
491 // adding the "noFragment" flag to big surfaces like sky boxes
492 // will avoid potentially dicing them up into tons of triangles
493 // that take forever to optimize back together
494 if ( !dmapGlobals.fullCarve || side->material->NoFragment() ) {
495 area = CheckWindingInAreas_r( w, node );
496 if ( area >= 0 ) {
497 mapTri_t *tri;
498
499 // put in single area
500 tri = TriListForSide( side, w );
501 AddTriListToArea( e, tri, side->planenum, area, &side->texVec );
502 return;
503 }
504 }
505
506 w->Split( dmapGlobals.mapPlanes[ node->planenum ], ON_EPSILON, &front, &back );
507
508 PutWindingIntoAreas_r( e, front, side, node->children[0] );
509 if ( front ) {
510 delete front;
511 }
512
513 PutWindingIntoAreas_r( e, back, side, node->children[1] );
514 if ( back ) {
515 delete back;
516 }
517
518 return;
519 }
520
521 // if opaque leaf, don't add
522 if ( node->area >= 0 && !node->opaque ) {
523 mapTri_t *tri;
524
525 tri = TriListForSide( side, w );
526 AddTriListToArea( e, tri, side->planenum, node->area, &side->texVec );
527 }
528 }
529
530 /*
531 ==================
532 AddMapTriToAreas
533
534 Used for curves and inlined models
535 ==================
536 */
AddMapTriToAreas(mapTri_t * tri,uEntity_t * e)537 void AddMapTriToAreas( mapTri_t *tri, uEntity_t *e ) {
538 int area;
539 idWinding *w;
540
541 // skip degenerate triangles from pinched curves
542 if ( MapTriArea( tri ) <= 0 ) {
543 return;
544 }
545
546 if ( dmapGlobals.fullCarve ) {
547 // always fragment into areas
548 w = WindingForTri( tri );
549 ClipTriIntoTree_r( w, tri, e, e->tree->headnode );
550 return;
551 }
552
553 w = WindingForTri( tri );
554 area = CheckWindingInAreas_r( w, e->tree->headnode );
555 delete w;
556 if ( area == -1 ) {
557 return;
558 }
559 if ( area >= 0 ) {
560 mapTri_t *newTri;
561 idPlane plane;
562 int planeNum;
563 textureVectors_t texVec;
564
565 // put in single area
566 newTri = CopyMapTri( tri );
567 newTri->next = NULL;
568
569 PlaneForTri( tri, plane );
570 planeNum = FindFloatPlane( plane );
571
572 TexVecForTri( &texVec, newTri );
573
574 AddTriListToArea( e, newTri, planeNum, area, &texVec );
575 } else {
576 // fragment into areas
577 w = WindingForTri( tri );
578 ClipTriIntoTree_r( w, tri, e, e->tree->headnode );
579 }
580 }
581
582 /*
583 =====================
584 PutPrimitivesInAreas
585
586 =====================
587 */
PutPrimitivesInAreas(uEntity_t * e)588 void PutPrimitivesInAreas( uEntity_t *e ) {
589 uBrush_t *b;
590 int i;
591 side_t *side;
592 primitive_t *prim;
593 mapTri_t *tri;
594
595 common->Printf( "----- PutPrimitivesInAreas -----\n");
596
597 // allocate space for surface chains for each area
598 e->areas = (uArea_t *)Mem_Alloc( e->numAreas * sizeof( e->areas[0] ) );
599 memset( e->areas, 0, e->numAreas * sizeof( e->areas[0] ) );
600
601 // for each primitive, clip it to the non-solid leafs
602 // and divide it into different areas
603 for ( prim = e->primitives ; prim ; prim = prim->next ) {
604 b = prim->brush;
605
606 if ( !b ) {
607 // add curve triangles
608 for ( tri = prim->tris ; tri ; tri = tri->next ) {
609 AddMapTriToAreas( tri, e );
610 }
611 continue;
612 }
613
614 // clip in brush sides
615 for ( i = 0 ; i < b->numsides ; i++ ) {
616 side = &b->sides[i];
617 if ( !side->visibleHull ) {
618 continue;
619 }
620 PutWindingIntoAreas_r( e, side->visibleHull, side, e->tree->headnode );
621 }
622 }
623
624
625 // optionally inline some of the func_static models
626 if ( dmapGlobals.entityNum == 0 ) {
627 bool inlineAll = dmapGlobals.uEntities[0].mapEntity->epairs.GetBool( "inlineAllStatics" );
628
629 for ( int eNum = 1 ; eNum < dmapGlobals.num_entities ; eNum++ ) {
630 uEntity_t *entity = &dmapGlobals.uEntities[eNum];
631 const char *className = entity->mapEntity->epairs.GetString( "classname" );
632 if ( idStr::Icmp( className, "func_static" ) ) {
633 continue;
634 }
635 if ( !entity->mapEntity->epairs.GetBool( "inline" ) && !inlineAll ) {
636 continue;
637 }
638 const char *modelName = entity->mapEntity->epairs.GetString( "model" );
639 if ( !modelName ) {
640 continue;
641 }
642 idRenderModel *model = renderModelManager->FindModel( modelName );
643
644 common->Printf( "inlining %s.\n", entity->mapEntity->epairs.GetString( "name" ) );
645
646 idMat3 axis;
647 // get the rotation matrix in either full form, or single angle form
648 if ( !entity->mapEntity->epairs.GetMatrix( "rotation", "1 0 0 0 1 0 0 0 1", axis ) ) {
649 float angle = entity->mapEntity->epairs.GetFloat( "angle" );
650 if ( angle != 0.0f ) {
651 axis = idAngles( 0.0f, angle, 0.0f ).ToMat3();
652 } else {
653 axis.Identity();
654 }
655 }
656
657 idVec3 origin = entity->mapEntity->epairs.GetVector( "origin" );
658
659 for ( i = 0 ; i < model->NumSurfaces() ; i++ ) {
660 const modelSurface_t *surface = model->Surface( i );
661 const srfTriangles_t *tri = surface->geometry;
662
663 mapTri_t mapTri;
664 memset( &mapTri, 0, sizeof( mapTri ) );
665 mapTri.material = surface->shader;
666 // don't let discretes (autosprites, etc) merge together
667 if ( mapTri.material->IsDiscrete() ) {
668 mapTri.mergeGroup = (void *)surface;
669 }
670 for ( int j = 0 ; j < tri->numIndexes ; j += 3 ) {
671 for ( int k = 0 ; k < 3 ; k++ ) {
672 idVec3 v = tri->verts[tri->indexes[j+k]].xyz;
673
674 mapTri.v[k].xyz = v * axis + origin;
675
676 mapTri.v[k].normal = tri->verts[tri->indexes[j+k]].normal * axis;
677 mapTri.v[k].st = tri->verts[tri->indexes[j+k]].st;
678 }
679 AddMapTriToAreas( &mapTri, e );
680 }
681 }
682 }
683 }
684 }
685
686 //============================================================================
687
688 /*
689 =================
690 ClipTriByLight
691
692 Carves a triangle by the frustom planes of a light, producing
693 a (possibly empty) list of triangles on the inside and outside.
694
695 The original triangle is not modified.
696
697 If no clipping is required, the result will be a copy of the original.
698
699 If clipping was required, the outside fragments will be planar clips, which
700 will benefit from re-optimization.
701 =================
702 */
ClipTriByLight(const mapLight_t * light,const mapTri_t * tri,mapTri_t ** in,mapTri_t ** out)703 static void ClipTriByLight( const mapLight_t *light, const mapTri_t *tri,
704 mapTri_t **in, mapTri_t **out ) {
705 idWinding *inside, *oldInside;
706 idWinding *outside[6];
707 bool hasOutside;
708 int i;
709
710 *in = NULL;
711 *out = NULL;
712
713 // clip this winding to the light
714 inside = WindingForTri( tri );
715 hasOutside = false;
716 for ( i = 0 ; i < 6 ; i++ ) {
717 oldInside = inside;
718 if ( oldInside ) {
719 oldInside->Split( light->def.frustum[i], 0, &outside[i], &inside );
720 delete oldInside;
721 }
722 else {
723 outside[i] = NULL;
724 }
725 if ( outside[i] ) {
726 hasOutside = true;
727 }
728 }
729
730 if ( !inside ) {
731 // the entire winding is outside this light
732
733 // free the clipped fragments
734 for ( i = 0 ; i < 6 ; i++ ) {
735 if ( outside[i] ) {
736 delete outside[i];
737 }
738 }
739
740 *out = CopyMapTri( tri );
741 (*out)->next = NULL;
742
743 return;
744 }
745
746 if ( !hasOutside ) {
747 // the entire winding is inside this light
748
749 // free the inside copy
750 delete inside;
751
752 *in = CopyMapTri( tri );
753 (*in)->next = NULL;
754
755 return;
756 }
757
758 // the winding is split
759 *in = WindingToTriList( inside, tri );
760 delete inside;
761
762 // combine all the outside fragments
763 for ( i = 0 ; i < 6 ; i++ ) {
764 if ( outside[i] ) {
765 mapTri_t *list;
766
767 list = WindingToTriList( outside[i], tri );
768 delete outside[i];
769 *out = MergeTriLists( *out, list );
770 }
771 }
772 }
773
774 /*
775 =================
776 BoundOptimizeGroup
777 =================
778 */
BoundOptimizeGroup(optimizeGroup_t * group)779 static void BoundOptimizeGroup( optimizeGroup_t *group ) {
780 group->bounds.Clear();
781 for ( mapTri_t *tri = group->triList ; tri ; tri = tri->next ) {
782 group->bounds.AddPoint( tri->v[0].xyz );
783 group->bounds.AddPoint( tri->v[1].xyz );
784 group->bounds.AddPoint( tri->v[2].xyz );
785 }
786 }
787
788 /*
789 ====================
790 BuildLightShadows
791
792 Build the beam tree and shadow volume surface for a light
793 ====================
794 */
BuildLightShadows(uEntity_t * e,mapLight_t * light)795 static void BuildLightShadows( uEntity_t *e, mapLight_t *light ) {
796 int i;
797 optimizeGroup_t *group;
798 mapTri_t *tri;
799 mapTri_t *shadowers;
800 optimizeGroup_t *shadowerGroups;
801 idVec3 lightOrigin;
802 bool hasPerforatedSurface = false;
803
804 //
805 // build a group list of all the triangles that will contribute to
806 // the optimized shadow volume, leaving the original triangles alone
807 //
808
809
810 // shadowers will contain all the triangles that will contribute to the
811 // shadow volume
812 shadowerGroups = NULL;
813 lightOrigin = light->def.globalLightOrigin;
814
815 // if the light is no-shadows, don't add any surfaces
816 // to the beam tree at all
817 if ( !light->def.parms.noShadows
818 && light->def.lightShader->LightCastsShadows() ) {
819 for ( i = 0 ; i < e->numAreas ; i++ ) {
820 for ( group = e->areas[i].groups ; group ; group = group->nextGroup ) {
821 // if the surface doesn't cast shadows, skip it
822 if ( !group->material->SurfaceCastsShadow() ) {
823 continue;
824 }
825
826 // if the group doesn't face away from the light, it
827 // won't contribute to the shadow volume
828 if ( dmapGlobals.mapPlanes[ group->planeNum ].Distance( lightOrigin ) > 0 ) {
829 continue;
830 }
831
832 // if the group bounds doesn't intersect the light bounds,
833 // skip it
834 if ( !group->bounds.IntersectsBounds( light->def.frustumTris->bounds ) ) {
835 continue;
836 }
837
838 // build up a list of the triangle fragments inside the
839 // light frustum
840 shadowers = NULL;
841 for ( tri = group->triList ; tri ; tri = tri->next ) {
842 mapTri_t *in, *out;
843
844 // clip it to the light frustum
845 ClipTriByLight( light, tri, &in, &out );
846 FreeTriList( out );
847 shadowers = MergeTriLists( shadowers, in );
848 }
849
850 // if we didn't get any out of this group, we don't
851 // need to create a new group in the shadower list
852 if ( !shadowers ) {
853 continue;
854 }
855
856 // find a group in shadowerGroups to add these to
857 // we will ignore everything but planenum, and we
858 // can merge across areas
859 optimizeGroup_t *check;
860
861 for ( check = shadowerGroups ; check ; check = check->nextGroup ) {
862 if ( check->planeNum == group->planeNum ) {
863 break;
864 }
865 }
866 if ( !check ) {
867 check = (optimizeGroup_t *)Mem_Alloc( sizeof( *check ) );
868 *check = *group;
869 check->triList = NULL;
870 check->nextGroup = shadowerGroups;
871 shadowerGroups = check;
872 }
873
874 // if any surface is a shadow-casting perforated or translucent surface, we
875 // can't use the face removal optimizations because we can see through
876 // some of the faces
877 if ( group->material->Coverage() != MC_OPAQUE ) {
878 hasPerforatedSurface = true;
879 }
880
881 check->triList = MergeTriLists( check->triList, shadowers );
882 }
883 }
884 }
885
886 // take the shadower group list and create a beam tree and shadow volume
887 light->shadowTris = CreateLightShadow( shadowerGroups, light );
888
889 if ( light->shadowTris && hasPerforatedSurface ) {
890 // can't ever remove front faces, because we can see through some of them
891 light->shadowTris->numShadowIndexesNoCaps = light->shadowTris->numShadowIndexesNoFrontCaps =
892 light->shadowTris->numIndexes;
893 }
894
895 // we don't need the original shadower triangles for anything else
896 FreeOptimizeGroupList( shadowerGroups );
897 }
898
899
900 /*
901 ====================
902 CarveGroupsByLight
903
904 Divide each group into an inside group and an outside group, based
905 on which fragments are illuminated by the light's beam tree
906 ====================
907 */
CarveGroupsByLight(uEntity_t * e,mapLight_t * light)908 static void CarveGroupsByLight( uEntity_t *e, mapLight_t *light ) {
909 int i;
910 optimizeGroup_t *group, *newGroup, *carvedGroups, *nextGroup;
911 mapTri_t *tri, *inside, *outside;
912 uArea_t *area;
913
914 for ( i = 0 ; i < e->numAreas ; i++ ) {
915 area = &e->areas[i];
916 carvedGroups = NULL;
917
918 // we will be either freeing or reassigning the groups as we go
919 for ( group = area->groups ; group ; group = nextGroup ) {
920 nextGroup = group->nextGroup;
921 // if the surface doesn't get lit, don't carve it up
922 if ( ( light->def.lightShader->IsFogLight() && !group->material->ReceivesFog() )
923 || ( !light->def.lightShader->IsFogLight() && !group->material->ReceivesLighting() )
924 || !group->bounds.IntersectsBounds( light->def.frustumTris->bounds ) ) {
925
926 group->nextGroup = carvedGroups;
927 carvedGroups = group;
928 continue;
929 }
930
931 if ( group->numGroupLights == MAX_GROUP_LIGHTS ) {
932 common->Error( "MAX_GROUP_LIGHTS around %f %f %f",
933 group->triList->v[0].xyz[0], group->triList->v[0].xyz[1], group->triList->v[0].xyz[2] );
934 }
935
936 // if the group doesn't face the light,
937 // it won't get carved at all
938 if ( !light->def.lightShader->LightEffectsBackSides() &&
939 !group->material->ReceivesLightingOnBackSides() &&
940 dmapGlobals.mapPlanes[ group->planeNum ].Distance( light->def.parms.origin ) <= 0 ) {
941
942 group->nextGroup = carvedGroups;
943 carvedGroups = group;
944 continue;
945 }
946
947 // split into lists for hit-by-light, and not-hit-by-light
948 inside = NULL;
949 outside = NULL;
950
951 for ( tri = group->triList ; tri ; tri = tri->next ) {
952 mapTri_t *in, *out;
953
954 ClipTriByLight( light, tri, &in, &out );
955 inside = MergeTriLists( inside, in );
956 outside = MergeTriLists( outside, out );
957 }
958
959 if ( inside ) {
960 newGroup = (optimizeGroup_t *)Mem_Alloc( sizeof( *newGroup ) );
961 *newGroup = *group;
962 newGroup->groupLights[newGroup->numGroupLights] = light;
963 newGroup->numGroupLights++;
964 newGroup->triList = inside;
965 newGroup->nextGroup = carvedGroups;
966 carvedGroups = newGroup;
967 }
968
969 if ( outside ) {
970 newGroup = (optimizeGroup_t *)Mem_Alloc( sizeof( *newGroup ) );
971 *newGroup = *group;
972 newGroup->triList = outside;
973 newGroup->nextGroup = carvedGroups;
974 carvedGroups = newGroup;
975 }
976
977 // free the original
978 group->nextGroup = NULL;
979 FreeOptimizeGroupList( group );
980 }
981
982 // replace this area's group list with the new one
983 area->groups = carvedGroups;
984 }
985 }
986
987 /*
988 =====================
989 Prelight
990
991 Break optimize groups up into additional groups at light boundaries, so
992 optimization won't cross light bounds
993 =====================
994 */
Prelight(uEntity_t * e)995 void Prelight( uEntity_t *e ) {
996 int i;
997 int start, end;
998 mapLight_t *light;
999
1000 // don't prelight anything but the world entity
1001 if ( dmapGlobals.entityNum != 0 ) {
1002 return;
1003 }
1004
1005 if ( dmapGlobals.shadowOptLevel > 0 ) {
1006 common->Printf( "----- BuildLightShadows -----\n" );
1007 start = Sys_Milliseconds();
1008
1009 // calc bounds for all the groups to speed things up
1010 for ( i = 0 ; i < e->numAreas ; i++ ) {
1011 uArea_t *area = &e->areas[i];
1012
1013 for ( optimizeGroup_t *group = area->groups ; group ; group = group->nextGroup ) {
1014 BoundOptimizeGroup( group );
1015 }
1016 }
1017
1018 for ( i = 0 ; i < dmapGlobals.mapLights.Num() ; i++ ) {
1019 light = dmapGlobals.mapLights[i];
1020 BuildLightShadows( e, light );
1021 }
1022
1023 end = Sys_Milliseconds();
1024 common->Printf( "%5.1f seconds for BuildLightShadows\n", ( end - start ) / 1000.0 );
1025 }
1026
1027
1028 if ( !dmapGlobals.noLightCarve ) {
1029 common->Printf( "----- CarveGroupsByLight -----\n" );
1030 start = Sys_Milliseconds();
1031 // now subdivide the optimize groups into additional groups for
1032 // each light that illuminates them
1033 for ( i = 0 ; i < dmapGlobals.mapLights.Num() ; i++ ) {
1034 light = dmapGlobals.mapLights[i];
1035 CarveGroupsByLight( e, light );
1036 }
1037
1038 end = Sys_Milliseconds();
1039 common->Printf( "%5.1f seconds for CarveGroupsByLight\n", ( end - start ) / 1000.0 );
1040 }
1041
1042 }
1043