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/tr_local.h"
31
32 #include "tools/compilers/dmap/dmap.h"
33
34 /*
35
36 given a set of faces that are clipped to the required frustum
37
38 make 2D projection for each vertex
39
40 for each edge
41 add edge, generating new points at each edge intersection
42
43 ?add all additional edges to make a full triangulation
44
45 make full triangulation
46
47 for each triangle
48 find midpoint
49 find original triangle with midpoint closest to view
50 annotate triangle with that data
51 project all vertexes to that plane
52 output the triangle as a front cap
53
54 snap all vertexes
55 make a back plane projection for all vertexes
56
57 for each edge
58 if one side doesn't have a triangle
59 make a sil edge to back plane projection
60 continue
61 if triangles on both sides have two verts in common
62 continue
63 make a sil edge from one triangle to the other
64
65
66
67
68 classify triangles on common planes, so they can be optimized
69
70 what about interpenetrating triangles???
71
72 a perfect shadow volume will have every edge exactly matched with
73 an opposite, and no two triangles covering the same area on either
74 the back projection or a silhouette edge.
75
76 Optimizing the triangles on the projected plane can give a significant
77 improvement, but the quadratic time nature of the optimization process
78 probably makes it untenable.
79
80 There exists some small room for further triangle count optimizations of the volumes
81 by collapsing internal surface geometry in some cases, or allowing original triangles
82 to extend outside the exactly light frustum without being clipped, but it probably
83 isn't worth it.
84
85 Triangle count optimizations at the expense of a slight fill rate cost
86 may be apropriate in some cases.
87
88
89 Perform the complete clipping on all triangles
90 for each vertex
91 project onto the apropriate plane and mark plane bit as in use
92 for each triangle
93 if points project onto different planes, clip
94 */
95
96
97 typedef struct {
98 idVec3 v[3];
99 idVec3 edge[3]; // positive side is inside the triangle
100 glIndex_t index[3];
101 idPlane plane; // positive side is forward for the triangle, which is away from the light
102 int planeNum; // from original triangle, not calculated from the clipped verts
103 } shadowTri_t;
104
105 static const int MAX_SHADOW_TRIS = 32768;
106
107 static shadowTri_t outputTris[MAX_SHADOW_TRIS];
108 static int numOutputTris;
109
110 typedef struct shadowOptEdge_s {
111 glIndex_t index[2];
112 struct shadowOptEdge_s *nextEdge;
113 } shadowOptEdge_t;
114
115 static const int MAX_SIL_EDGES = MAX_SHADOW_TRIS*3;
116 static shadowOptEdge_t silEdges[MAX_SIL_EDGES];
117 static int numSilEdges;
118
119 typedef struct silQuad_s {
120 int nearV[2];
121 int farV[2]; // will always be a projection of near[]
122 struct silQuad_s *nextQuad;
123 } silQuad_t;
124
125 static const int MAX_SIL_QUADS = MAX_SHADOW_TRIS*3;
126 static silQuad_t silQuads[MAX_SIL_QUADS];
127 static int numSilQuads;
128
129
130 typedef struct {
131 idVec3 normal; // all sil planes go through the projection origin
132 shadowOptEdge_t *edges;
133 silQuad_t *fragmentedQuads;
134 } silPlane_t;
135
136 static float EDGE_PLANE_EPSILON = 0.1f;
137 static float UNIQUE_EPSILON = 0.1f;
138
139 static int numSilPlanes;
140 static silPlane_t *silPlanes;
141
142 // the uniqued verts are still in projection centered space, not global space
143 static int numUniqued;
144 static int numUniquedBeforeProjection;
145 static int maxUniqued;
146 static idVec3 *uniqued;
147
148 static optimizedShadow_t ret;
149 static int maxRetIndexes;
150
151 static int FindUniqueVert( idVec3 &v );
152
153 //=====================================================================================
154
155 /*
156 =================
157 CreateEdgesForTri
158 =================
159 */
CreateEdgesForTri(shadowTri_t * tri)160 static void CreateEdgesForTri( shadowTri_t *tri ) {
161 for ( int j = 0 ; j < 3 ; j++ ) {
162 idVec3 &v1 = tri->v[j];
163 idVec3 &v2 = tri->v[(j+1)%3];
164
165 tri->edge[j].Cross( v2, v1 );
166 tri->edge[j].Normalize();
167 }
168 }
169
170
171 static const float EDGE_EPSILON = 0.1f;
172
TriOutsideTri(const shadowTri_t * a,const shadowTri_t * b)173 static bool TriOutsideTri( const shadowTri_t *a, const shadowTri_t *b ) {
174 #if 0
175 if ( a->v[0] * b->edge[0] <= EDGE_EPSILON
176 && a->v[1] * b->edge[0] <= EDGE_EPSILON
177 && a->v[2] * b->edge[0] <= EDGE_EPSILON ) {
178 return true;
179 }
180 if ( a->v[0] * b->edge[1] <= EDGE_EPSILON
181 && a->v[1] * b->edge[1] <= EDGE_EPSILON
182 && a->v[2] * b->edge[1] <= EDGE_EPSILON ) {
183 return true;
184 }
185 if ( a->v[0] * b->edge[2] <= EDGE_EPSILON
186 && a->v[1] * b->edge[2] <= EDGE_EPSILON
187 && a->v[2] * b->edge[2] <= EDGE_EPSILON ) {
188 return true;
189 }
190 #else
191 for ( int i = 0 ; i < 3 ; i++ ) {
192 int j;
193 for ( j = 0 ; j < 3 ; j++ ) {
194 float d = a->v[j] * b->edge[i];
195 if ( d > EDGE_EPSILON ) {
196 break;
197 }
198 }
199 if ( j == 3 ) {
200 return true;
201 }
202 }
203 #endif
204 return false;
205 }
206
TriBehindTri(const shadowTri_t * a,const shadowTri_t * b)207 static bool TriBehindTri( const shadowTri_t *a, const shadowTri_t *b ) {
208 float d;
209
210 d = b->plane.Distance( a->v[0] );
211 if ( d > 0 ) {
212 return true;
213 }
214 d = b->plane.Distance( a->v[1] );
215 if ( d > 0 ) {
216 return true;
217 }
218 d = b->plane.Distance( a->v[2] );
219 if ( d > 0 ) {
220 return true;
221 }
222
223 return false;
224 }
225
226 /*
227 ===================
228 ClipTriangle_r
229 ===================
230 */
231 static int c_removedFragments;
ClipTriangle_r(const shadowTri_t * tri,int startTri,int skipTri,int numTris,const shadowTri_t * tris)232 static void ClipTriangle_r( const shadowTri_t *tri, int startTri, int skipTri, int numTris, const shadowTri_t *tris ) {
233 // create edge planes for this triangle
234
235 // compare against all the other triangles
236 for ( int i = startTri ; i < numTris ; i++ ) {
237 if ( i == skipTri ) {
238 continue;
239 }
240 const shadowTri_t *other = &tris[i];
241
242 if ( TriOutsideTri( tri, other ) ) {
243 continue;
244 }
245 if ( TriOutsideTri( other, tri ) ) {
246 continue;
247 }
248 // they overlap to some degree
249
250 // if other is behind tri, it doesn't clip it
251 if ( !TriBehindTri( tri, other ) ) {
252 continue;
253 }
254
255 // clip it
256 idWinding *w = new idWinding( tri->v, 3 );
257
258 for ( int j = 0 ; j < 4 && w ; j++ ) {
259 idWinding *front, *back;
260
261 // keep any portion in front of other's plane
262 if ( j == 0 ) {
263 w->Split( other->plane, ON_EPSILON, &front, &back );
264 } else {
265 w->Split( idPlane( other->edge[j-1], 0.0f ), ON_EPSILON, &front, &back );
266 }
267 if ( back ) {
268 // recursively clip these triangles to all subsequent triangles
269 for ( int k = 2 ; k < back->GetNumPoints() ; k++ ) {
270 shadowTri_t fragment = *tri;
271
272 fragment.v[0] = (*back)[0].ToVec3();
273 fragment.v[1] = (*back)[k-1].ToVec3();
274 fragment.v[2] = (*back)[k].ToVec3();
275 CreateEdgesForTri( &fragment );
276 ClipTriangle_r( &fragment, i + 1, skipTri, numTris, tris );
277 }
278 delete back;
279 }
280
281 delete w;
282 w = front;
283 }
284 if ( w ) {
285 delete w;
286 }
287
288 c_removedFragments++;
289 // any fragments will have been added recursively
290 return;
291 }
292
293 // this fragment is frontmost, so add it to the output list
294 if ( numOutputTris == MAX_SHADOW_TRIS ) {
295 common->Error( "numOutputTris == MAX_SHADOW_TRIS" );
296 }
297
298 outputTris[numOutputTris] = *tri;
299 numOutputTris++;
300 }
301
302
303 /*
304 ====================
305 ClipOccluders
306
307 Generates outputTris by clipping all the triangles against each other,
308 retaining only those closest to the projectionOrigin
309 ====================
310 */
ClipOccluders(idVec4 * verts,glIndex_t * indexes,int numIndexes,idVec3 projectionOrigin)311 static void ClipOccluders( idVec4 *verts, glIndex_t *indexes, int numIndexes,
312 idVec3 projectionOrigin ) {
313 int numTris = numIndexes / 3;
314 int i;
315 shadowTri_t *tris = (shadowTri_t *)_alloca( numTris * sizeof( *tris ) );
316 shadowTri_t *tri;
317
318 common->Printf( "ClipOccluders: %i triangles\n", numTris );
319
320 for ( i = 0 ; i < numTris ; i++ ) {
321 tri = &tris[i];
322
323 // the indexes are in reversed order from tr_stencilshadow
324 tri->v[0] = verts[indexes[i*3+2]].ToVec3() - projectionOrigin;
325 tri->v[1] = verts[indexes[i*3+1]].ToVec3() - projectionOrigin;
326 tri->v[2] = verts[indexes[i*3+0]].ToVec3() - projectionOrigin;
327
328 idVec3 d1 = tri->v[1] - tri->v[0];
329 idVec3 d2 = tri->v[2] - tri->v[0];
330
331 tri->plane.ToVec4().ToVec3().Cross( d2, d1 );
332 tri->plane.ToVec4().ToVec3().Normalize();
333 tri->plane[3] = - ( tri->v[0] * tri->plane.ToVec4().ToVec3() );
334
335 // get the plane number before any clipping
336 // we should avoid polluting the regular dmap planes with these
337 // that are offset from the light origin...
338 tri->planeNum = FindFloatPlane( tri->plane );
339
340 CreateEdgesForTri( tri );
341 }
342
343 // clear our output buffer
344 numOutputTris = 0;
345
346 // for each triangle, clip against all other triangles
347 int numRemoved = 0;
348 int numComplete = 0;
349 int numFragmented = 0;
350
351 for ( i = 0 ; i < numTris ; i++ ) {
352 int oldOutput = numOutputTris;
353 c_removedFragments = 0;
354 ClipTriangle_r( &tris[i], 0, i, numTris, tris );
355 if ( numOutputTris == oldOutput ) {
356 numRemoved++; // completely unused
357 } else if ( c_removedFragments == 0 ) {
358 // the entire triangle is visible
359 numComplete++;
360 shadowTri_t *out = &outputTris[oldOutput];
361 *out = tris[i];
362 numOutputTris = oldOutput+1;
363 } else {
364 numFragmented++;
365 // we made at least one fragment
366
367 // if we are at the low optimization level, just use a single
368 // triangle if it produced any fragments
369 if ( dmapGlobals.shadowOptLevel == SO_CULL_OCCLUDED ) {
370 shadowTri_t *out = &outputTris[oldOutput];
371 *out = tris[i];
372 numOutputTris = oldOutput+1;
373 }
374 }
375 }
376 common->Printf( "%i triangles completely invisible\n", numRemoved );
377 common->Printf( "%i triangles completely visible\n", numComplete );
378 common->Printf( "%i triangles fragmented\n", numFragmented );
379 common->Printf( "%i shadowing fragments before optimization\n", numOutputTris );
380 }
381
382 //=====================================================================================
383
384 /*
385 ================
386 OptimizeOutputTris
387 ================
388 */
OptimizeOutputTris(void)389 static void OptimizeOutputTris( void ) {
390 int i;
391
392 // optimize the clipped surfaces
393 optimizeGroup_t *optGroups = NULL;
394 optimizeGroup_t *checkGroup;
395
396 for ( i = 0 ; i < numOutputTris ; i++ ) {
397 shadowTri_t *tri = &outputTris[i];
398
399 int planeNum = tri->planeNum;
400
401 // add it to an optimize group
402 for ( checkGroup = optGroups ; checkGroup ; checkGroup = checkGroup->nextGroup ) {
403 if ( checkGroup->planeNum == planeNum ) {
404 break;
405 }
406 }
407 if ( !checkGroup ) {
408 // create a new optGroup
409 checkGroup = (optimizeGroup_t *)Mem_ClearedAlloc( sizeof( *checkGroup ) );
410 checkGroup->planeNum = planeNum;
411 checkGroup->nextGroup = optGroups;
412 optGroups = checkGroup;
413 }
414
415 // create a mapTri for the optGroup
416 mapTri_t *mtri = (mapTri_t *)Mem_ClearedAlloc( sizeof( *mtri ) );
417 mtri->v[0].xyz = tri->v[0];
418 mtri->v[1].xyz = tri->v[1];
419 mtri->v[2].xyz = tri->v[2];
420 mtri->next = checkGroup->triList;
421 checkGroup->triList = mtri;
422 }
423
424 OptimizeGroupList( optGroups );
425
426 numOutputTris = 0;
427 for ( checkGroup = optGroups ; checkGroup ; checkGroup = checkGroup->nextGroup ) {
428 for ( mapTri_t *mtri = checkGroup->triList ; mtri ; mtri = mtri->next ) {
429 shadowTri_t *tri = &outputTris[numOutputTris];
430 numOutputTris++;
431 tri->v[0] = mtri->v[0].xyz;
432 tri->v[1] = mtri->v[1].xyz;
433 tri->v[2] = mtri->v[2].xyz;
434 }
435 }
436 FreeOptimizeGroupList( optGroups );
437 }
438
439 //==================================================================================
440
EdgeSort(const void * a,const void * b)441 static int EdgeSort( const void *a, const void *b ) {
442 if ( *(unsigned *)a < *(unsigned *)b ) {
443 return -1;
444 }
445 if ( *(unsigned *)a > *(unsigned *)b ) {
446 return 1;
447 }
448 return 0;
449 }
450
451 /*
452 =====================
453 GenerateSilEdges
454
455 Output tris must be tjunction fixed and vertex uniqued
456 A edge that is not exactly matched is a silhouette edge
457 We could skip this and rely completely on the matched quad removal
458 for all sil edges, but this will avoid the bulk of the checks.
459 =====================
460 */
GenerateSilEdges(void)461 static void GenerateSilEdges( void ) {
462 int i, j;
463
464 unsigned *edges = (unsigned *)_alloca( (numOutputTris*3+1)*sizeof(*edges) );
465 int numEdges = 0;
466
467 numSilEdges = 0;
468
469 for ( i = 0 ; i < numOutputTris ; i++ ) {
470 int a = outputTris[i].index[0];
471 int b = outputTris[i].index[1];
472 int c = outputTris[i].index[2];
473 if ( a == b || a == c || b == c ) {
474 continue; // degenerate
475 }
476
477 for ( j = 0 ; j < 3 ; j++ ) {
478 int v1, v2;
479
480 v1 = outputTris[i].index[j];
481 v2 = outputTris[i].index[(j+1)%3];
482 if ( v1 == v2 ) {
483 continue; // degenerate
484 }
485 if ( v1 > v2 ) {
486 edges[numEdges] = ( v1 << 16 ) | ( v2 << 1 );
487 } else {
488 edges[numEdges] = ( v2 << 16 ) | ( v1 << 1 ) | 1;
489 }
490 numEdges++;
491 }
492 }
493
494 qsort( edges, numEdges, sizeof( edges[0] ), EdgeSort );
495 edges[numEdges] = -1; // force the last to make an edge if no matched to previous
496
497 for ( i = 0 ; i < numEdges ; i++ ) {
498 if ( ( edges[i] ^ edges[i+1] ) == 1 ) {
499 // skip the next one, because we matched and
500 // removed both
501 i++;
502 continue;
503 }
504 // this is an unmatched edge, so we need to generate a sil plane
505 int v1, v2;
506 if ( edges[i] & 1 ) {
507 v2 = edges[i] >> 16;
508 v1 = ( edges[i] >> 1 ) & 0x7fff;
509 } else {
510 v1 = edges[i] >> 16;
511 v2 = ( edges[i] >> 1 ) & 0x7fff;
512 }
513
514 if ( numSilEdges == MAX_SIL_EDGES ) {
515 common->Error( "numSilEdges == MAX_SIL_EDGES" );
516 }
517 silEdges[numSilEdges].index[0] = v1;
518 silEdges[numSilEdges].index[1] = v2;
519 numSilEdges++;
520 }
521 }
522
523 //==================================================================================
524
525 /*
526 =====================
527 GenerateSilPlanes
528
529 Groups the silEdges into common planes
530 =====================
531 */
GenerateSilPlanes(void)532 void GenerateSilPlanes( void ) {
533 numSilPlanes = 0;
534 silPlanes = (silPlane_t *)Mem_Alloc( sizeof( *silPlanes ) * numSilEdges );
535
536 // identify the silPlanes
537 numSilPlanes = 0;
538 for ( int i = 0 ; i < numSilEdges ; i++ ) {
539 if ( silEdges[i].index[0] == silEdges[i].index[1] ) {
540 continue; // degenerate
541 }
542
543 idVec3 &v1 = uniqued[silEdges[i].index[0]];
544 idVec3 &v2 = uniqued[silEdges[i].index[1]];
545
546 // search for an existing plane
547 int j;
548 for ( j = 0 ; j < numSilPlanes ; j++ ) {
549 float d = v1 * silPlanes[j].normal;
550 float d2 = v2 * silPlanes[j].normal;
551
552 if ( fabs( d ) < EDGE_PLANE_EPSILON
553 && fabs( d2 ) < EDGE_PLANE_EPSILON ) {
554 silEdges[i].nextEdge = silPlanes[j].edges;
555 silPlanes[j].edges = &silEdges[i];
556 break;
557 }
558 }
559
560 if ( j == numSilPlanes ) {
561 // create a new silPlane
562 silPlanes[j].normal.Cross( v2, v1 );
563 silPlanes[j].normal.Normalize();
564 silEdges[i].nextEdge = NULL;
565 silPlanes[j].edges = &silEdges[i];
566 silPlanes[j].fragmentedQuads = NULL;
567 numSilPlanes++;
568 }
569 }
570 }
571
572 //==================================================================================
573
574 /*
575 =============
576 SaveQuad
577 =============
578 */
SaveQuad(silPlane_t * silPlane,silQuad_t & quad)579 static void SaveQuad( silPlane_t *silPlane, silQuad_t &quad ) {
580 // this fragment is a final fragment
581 if ( numSilQuads == MAX_SIL_QUADS ) {
582 common->Error( "numSilQuads == MAX_SIL_QUADS" );
583 }
584 silQuads[numSilQuads] = quad;
585 silQuads[numSilQuads].nextQuad = silPlane->fragmentedQuads;
586 silPlane->fragmentedQuads = &silQuads[numSilQuads];
587 numSilQuads++;
588 }
589
590
591 /*
592 ===================
593 FragmentSilQuad
594
595 Clip quads, or reconstruct?
596 Generate them T-junction free, or require another pass of fix-tjunc?
597 Call optimizer on a per-sil-plane basis?
598 will this ever introduce tjunctions with the front faces?
599 removal of planes can allow the rear projection to be farther optimized
600
601 For quad clipping
602 PlaneThroughEdge
603
604 quad clipping introduces new vertexes
605
606 Cannot just fragment edges, must emit full indexes
607
608 what is the bounds on max indexes?
609 the worst case is that all edges but one carve an existing edge in the middle,
610 giving twice the input number of indexes (I think)
611
612 can we avoid knowing about projected positions and still optimize?
613
614 Fragment all edges first
615 Introduces T-junctions
616 create additional silEdges, linked to silPlanes
617
618 In theory, we should never have more than one edge clipping a given
619 fragment, but it is more robust if we check them all
620 ===================
621 */
FragmentSilQuad(silQuad_t quad,silPlane_t * silPlane,shadowOptEdge_t * startEdge,shadowOptEdge_t * skipEdge)622 static void FragmentSilQuad( silQuad_t quad, silPlane_t *silPlane,
623 shadowOptEdge_t *startEdge, shadowOptEdge_t *skipEdge ) {
624 if ( quad.nearV[0] == quad.nearV[1] ) {
625 return;
626 }
627
628 for ( shadowOptEdge_t *check = startEdge ; check ; check = check->nextEdge ) {
629 if ( check == skipEdge ) {
630 // don't clip against self
631 continue;
632 }
633
634 if ( check->index[0] == check->index[1] ) {
635 continue;
636 }
637
638 // make planes through both points of check
639 for ( int i = 0 ; i < 2 ; i++ ) {
640 idVec3 plane;
641
642 plane.Cross( uniqued[check->index[i]], silPlane->normal );
643 plane.Normalize();
644
645 if ( plane.Length() < 0.9 ) {
646 continue;
647 }
648
649 // if the other point on check isn't on the negative side of the plane,
650 // flip the plane
651 if ( uniqued[check->index[!i]] * plane > 0 ) {
652 plane = -plane;
653 }
654
655 float d1 = uniqued[quad.nearV[0]] * plane;
656 float d2 = uniqued[quad.nearV[1]] * plane;
657
658 float d3 = uniqued[quad.farV[0]] * plane;
659 float d4 = uniqued[quad.farV[1]] * plane;
660
661 // it is better to conservatively NOT split the quad, which, at worst,
662 // will leave some extra overdraw
663
664 // if the plane divides the incoming edge, split it and recurse
665 // with the outside fraction before continuing with the inside fraction
666 if ( ( d1 > EDGE_PLANE_EPSILON && d3 > EDGE_PLANE_EPSILON && d2 < -EDGE_PLANE_EPSILON && d4 < -EDGE_PLANE_EPSILON )
667 || ( d2 > EDGE_PLANE_EPSILON && d4 > EDGE_PLANE_EPSILON && d1 < -EDGE_PLANE_EPSILON && d3 < -EDGE_PLANE_EPSILON ) ) {
668 float f = d1 / ( d1 - d2 );
669 float f2 = d3 / ( d3 - d4 );
670 f = f2;
671 if ( f <= 0.0001 || f >= 0.9999 ) {
672 common->Error( "Bad silQuad fraction" );
673 }
674
675 // finding uniques may be causing problems here
676 idVec3 nearMid = (1-f) * uniqued[quad.nearV[0]] + f * uniqued[quad.nearV[1]];
677 int nearMidIndex = FindUniqueVert( nearMid );
678 idVec3 farMid = (1-f) * uniqued[quad.farV[0]] + f * uniqued[quad.farV[1]];
679 int farMidIndex = FindUniqueVert( farMid );
680
681 silQuad_t clipped = quad;
682
683 if ( d1 > EDGE_PLANE_EPSILON ) {
684 clipped.nearV[1] = nearMidIndex;
685 clipped.farV[1] = farMidIndex;
686 FragmentSilQuad( clipped, silPlane, check->nextEdge, skipEdge );
687 quad.nearV[0] = nearMidIndex;
688 quad.farV[0] = farMidIndex;
689 } else {
690 clipped.nearV[0] = nearMidIndex;
691 clipped.farV[0] = farMidIndex;
692 FragmentSilQuad( clipped, silPlane, check->nextEdge, skipEdge );
693 quad.nearV[1] = nearMidIndex;
694 quad.farV[1] = farMidIndex;
695 }
696 }
697 }
698
699 // make a plane through the line of check
700 idPlane separate;
701
702 idVec3 dir = uniqued[check->index[1]] - uniqued[check->index[0]];
703 separate.Normal().Cross( dir, silPlane->normal );
704 separate.Normal().Normalize();
705 separate.ToVec4()[3] = -(uniqued[check->index[1]] * separate.Normal());
706
707 // this may miss a needed separation when the quad would be
708 // clipped into a triangle and a quad
709 float d1 = separate.Distance( uniqued[quad.nearV[0]] );
710 float d2 = separate.Distance( uniqued[quad.farV[0]] );
711
712 if ( ( d1 < EDGE_PLANE_EPSILON && d2 < EDGE_PLANE_EPSILON )
713 || ( d1 > -EDGE_PLANE_EPSILON && d2 > -EDGE_PLANE_EPSILON ) ) {
714 continue;
715 }
716
717 // split the quad at this plane
718 float f = d1 / ( d1 - d2 );
719 idVec3 mid0 = (1-f) * uniqued[quad.nearV[0]] + f * uniqued[quad.farV[0]];
720 int mid0Index = FindUniqueVert( mid0 );
721
722 d1 = separate.Distance( uniqued[quad.nearV[1]] );
723 d2 = separate.Distance( uniqued[quad.farV[1]] );
724 f = d1 / ( d1 - d2 );
725 if ( f < 0 || f > 1 ) {
726 continue;
727 }
728
729 idVec3 mid1 = (1-f) * uniqued[quad.nearV[1]] + f * uniqued[quad.farV[1]];
730 int mid1Index = FindUniqueVert( mid1 );
731
732 silQuad_t clipped = quad;
733
734 clipped.nearV[0] = mid0Index;
735 clipped.nearV[1] = mid1Index;
736 FragmentSilQuad( clipped, silPlane, check->nextEdge, skipEdge );
737 quad.farV[0] = mid0Index;
738 quad.farV[1] = mid1Index;
739 }
740
741 SaveQuad( silPlane, quad );
742 }
743
744
745 /*
746 ===============
747 FragmentSilQuads
748 ===============
749 */
FragmentSilQuads(void)750 static void FragmentSilQuads( void ) {
751 // group the edges into common planes
752 GenerateSilPlanes();
753
754 numSilQuads = 0;
755
756 // fragment overlapping edges
757 for ( int i = 0 ; i < numSilPlanes ; i++ ) {
758 silPlane_t *sil = &silPlanes[i];
759
760 for ( shadowOptEdge_t *e1 = sil->edges ; e1 ; e1 = e1->nextEdge ) {
761 silQuad_t quad;
762
763 quad.nearV[0] = e1->index[0];
764 quad.nearV[1] = e1->index[1];
765 if ( e1->index[0] == e1->index[1] ) {
766 common->Error( "FragmentSilQuads: degenerate edge" );
767 }
768 quad.farV[0] = e1->index[0] + numUniquedBeforeProjection;
769 quad.farV[1] = e1->index[1] + numUniquedBeforeProjection;
770 FragmentSilQuad( quad, sil, sil->edges, e1 );
771 }
772 }
773 }
774
775 //=======================================================================
776
777 /*
778 =====================
779 EmitFragmentedSilQuads
780
781 =====================
782 */
EmitFragmentedSilQuads(void)783 static void EmitFragmentedSilQuads( void ) {
784 int i, j, k;
785 mapTri_t *mtri;
786
787 for ( i = 0 ; i < numSilPlanes ; i++ ) {
788 silPlane_t *sil = &silPlanes[i];
789
790 // prepare for optimizing the sil quads on each side of the sil plane
791 optimizeGroup_t groups[2];
792 memset( &groups, 0, sizeof( groups ) );
793 idPlane planes[2];
794 planes[0].Normal() = sil->normal;
795 planes[0][3] = 0;
796 planes[1] = -planes[0];
797 groups[0].planeNum = FindFloatPlane( planes[0] );
798 groups[1].planeNum = FindFloatPlane( planes[1] );
799
800 // emit the quads that aren't matched
801 for ( silQuad_t *f1 = sil->fragmentedQuads ; f1 ; f1 = f1->nextQuad ) {
802 silQuad_t *f2;
803 for ( f2 = sil->fragmentedQuads ; f2 ; f2 = f2->nextQuad ) {
804 if ( f2 == f1 ) {
805 continue;
806 }
807 // in theory, this is sufficient, but we might
808 // have some cases of tripple+ matching, or unclipped rear projections
809 if ( f1->nearV[0] == f2->nearV[1] && f1->nearV[1] == f2->nearV[0] ) {
810 break;
811 }
812 }
813 // if we went through all the quads without finding a match, emit the quad
814 if ( !f2 ) {
815 optimizeGroup_t *gr;
816 idVec3 v1, v2, normal;
817
818 mtri = (mapTri_t *)Mem_ClearedAlloc( sizeof( *mtri ) );
819 mtri->v[0].xyz = uniqued[f1->nearV[0]];
820 mtri->v[1].xyz = uniqued[f1->nearV[1]];
821 mtri->v[2].xyz = uniqued[f1->farV[1]];
822
823 v1 = mtri->v[1].xyz - mtri->v[0].xyz;
824 v2 = mtri->v[2].xyz - mtri->v[0].xyz;
825 normal.Cross( v2, v1 );
826
827 if ( normal * planes[0].Normal() > 0 ) {
828 gr = &groups[0];
829 } else {
830 gr = &groups[1];
831 }
832
833 mtri->next = gr->triList;
834 gr->triList = mtri;
835
836 mtri = (mapTri_t *)Mem_ClearedAlloc( sizeof( *mtri ) );
837 mtri->v[0].xyz = uniqued[f1->farV[0]];
838 mtri->v[1].xyz = uniqued[f1->nearV[0]];
839 mtri->v[2].xyz = uniqued[f1->farV[1]];
840
841 mtri->next = gr->triList;
842 gr->triList = mtri;
843
844 #if 0
845 // emit a sil quad all the way to the projection plane
846 int index = ret.totalIndexes;
847 if ( index + 6 > maxRetIndexes ) {
848 common->Error( "maxRetIndexes exceeded" );
849 }
850 ret.indexes[index+0] = f1->nearV[0];
851 ret.indexes[index+1] = f1->nearV[1];
852 ret.indexes[index+2] = f1->farV[1];
853 ret.indexes[index+3] = f1->farV[0];
854 ret.indexes[index+4] = f1->nearV[0];
855 ret.indexes[index+5] = f1->farV[1];
856 ret.totalIndexes += 6;
857 #endif
858 }
859 }
860
861
862 // optimize
863 for ( j = 0 ; j < 2 ; j++ ) {
864 if ( !groups[j].triList ) {
865 continue;
866 }
867 if ( dmapGlobals.shadowOptLevel == SO_SIL_OPTIMIZE ) {
868 OptimizeGroupList( &groups[j] );
869 }
870 // add as indexes
871 for ( mtri = groups[j].triList ; mtri ; mtri = mtri->next ) {
872 for ( k = 0 ; k < 3 ; k++ ) {
873 if ( ret.totalIndexes == maxRetIndexes ) {
874 common->Error( "maxRetIndexes exceeded" );
875 }
876 ret.indexes[ret.totalIndexes] = FindUniqueVert( mtri->v[k].xyz );
877 ret.totalIndexes++;
878 }
879 }
880 FreeTriList( groups[j].triList );
881 }
882 }
883
884 // we don't need the silPlane grouping anymore
885 Mem_Free( silPlanes );
886 }
887
888 /*
889 =================
890 EmitUnoptimizedSilEdges
891 =================
892 */
EmitUnoptimizedSilEdges(void)893 static void EmitUnoptimizedSilEdges( void ) {
894 int i;
895
896 for ( i = 0 ; i < numSilEdges ; i++ ) {
897 int v1 = silEdges[i].index[0];
898 int v2 = silEdges[i].index[1];
899 int index = ret.totalIndexes;
900 ret.indexes[index+0] = v1;
901 ret.indexes[index+1] = v2;
902 ret.indexes[index+2] = v2+numUniquedBeforeProjection;
903 ret.indexes[index+3] = v1+numUniquedBeforeProjection;
904 ret.indexes[index+4] = v1;
905 ret.indexes[index+5] = v2+numUniquedBeforeProjection;
906 ret.totalIndexes += 6;
907 }
908 }
909
910 //==================================================================================
911
912 /*
913 ================
914 FindUniqueVert
915 ================
916 */
FindUniqueVert(idVec3 & v)917 static int FindUniqueVert( idVec3 &v ) {
918 int k;
919
920 for ( k = 0 ; k < numUniqued ; k++ ) {
921 idVec3 &check = uniqued[k];
922 if ( fabs( v[0] - check[0] ) < UNIQUE_EPSILON
923 && fabs( v[1] - check[1] ) < UNIQUE_EPSILON
924 && fabs( v[2] - check[2] ) < UNIQUE_EPSILON ) {
925 return k;
926 }
927 }
928 if ( numUniqued == maxUniqued ) {
929 common->Error( "FindUniqueVert: numUniqued == maxUniqued" );
930 }
931 uniqued[numUniqued] = v;
932 numUniqued++;
933
934 return k;
935 }
936
937 /*
938 ===================
939 UniqueVerts
940
941 Snaps all triangle verts together, setting tri->index[]
942 and generating numUniqued and uniqued.
943 These are still in projection-centered space, not global space
944 ===================
945 */
UniqueVerts(void)946 static void UniqueVerts( void ) {
947 int i, j;
948
949 // we may add to uniqued later when splitting sil edges, so leave
950 // some extra room
951 maxUniqued = 100000; // numOutputTris * 10 + 1000;
952 uniqued = (idVec3 *)Mem_Alloc( sizeof( *uniqued ) * maxUniqued );
953 numUniqued = 0;
954
955 for ( i = 0 ; i < numOutputTris ; i++ ) {
956 for ( j = 0 ; j < 3 ; j++ ) {
957 outputTris[i].index[j] = FindUniqueVert( outputTris[i].v[j] );
958 }
959 }
960 }
961
962 /*
963 ======================
964 ProjectUniqued
965 ======================
966 */
ProjectUniqued(idVec3 projectionOrigin,idPlane projectionPlane)967 static void ProjectUniqued( idVec3 projectionOrigin, idPlane projectionPlane ) {
968 // calculate the projection
969 idVec4 mat[4];
970
971 R_LightProjectionMatrix( projectionOrigin, projectionPlane, mat );
972
973 if ( numUniqued * 2 > maxUniqued ) {
974 common->Error( "ProjectUniqued: numUniqued * 2 > maxUniqued" );
975 }
976
977 // this is goofy going back and forth between the spaces,
978 // but I don't want to change R_LightProjectionMatrix righ tnow...
979 for ( int i = 0 ; i < numUniqued ; i++ ) {
980 // put the vert back in global space, instead of light centered space
981 idVec3 in = uniqued[i] + projectionOrigin;
982
983 // project to far plane
984 float w, oow;
985 idVec3 out;
986
987 w = in * mat[3].ToVec3() + mat[3][3];
988
989 oow = 1.0 / w;
990 out.x = ( in * mat[0].ToVec3() + mat[0][3] ) * oow;
991 out.y = ( in * mat[1].ToVec3() + mat[1][3] ) * oow;
992 out.z = ( in * mat[2].ToVec3() + mat[2][3] ) * oow;
993
994 uniqued[numUniqued+i] = out - projectionOrigin;
995 }
996 numUniqued *= 2;
997 }
998
999 /*
1000 ====================
1001 SuperOptimizeOccluders
1002
1003 This is the callback from the renderer shadow generation routine, after
1004 verts have been culled against individual frustums of point lights
1005
1006 ====================
1007 */
SuperOptimizeOccluders(idVec4 * verts,glIndex_t * indexes,int numIndexes,idPlane projectionPlane,idVec3 projectionOrigin)1008 optimizedShadow_t SuperOptimizeOccluders( idVec4 *verts, glIndex_t *indexes, int numIndexes,
1009 idPlane projectionPlane, idVec3 projectionOrigin )
1010 {
1011 memset( &ret, 0, sizeof( ret ) );
1012
1013 // generate outputTris, removing fragments that are occluded by closer fragments
1014 ClipOccluders( verts, indexes, numIndexes, projectionOrigin );
1015
1016 if ( dmapGlobals.shadowOptLevel >= SO_CULL_OCCLUDED ) {
1017 OptimizeOutputTris();
1018 }
1019
1020 // match up common verts
1021 UniqueVerts();
1022
1023 // now that we have uniqued the vertexes, we can find unmatched
1024 // edges, which are silhouette planes
1025 GenerateSilEdges();
1026
1027 // generate the projected verts
1028 numUniquedBeforeProjection = numUniqued;
1029 ProjectUniqued( projectionOrigin, projectionPlane );
1030
1031 // fragment the sil edges where the overlap,
1032 // possibly generating some additional unique verts
1033 if ( dmapGlobals.shadowOptLevel >= SO_CLIP_SILS ) {
1034 FragmentSilQuads();
1035 }
1036
1037 // indexes for face and projection caps
1038 ret.numFrontCapIndexes = numOutputTris * 3;
1039 ret.numRearCapIndexes = numOutputTris * 3;
1040 if ( dmapGlobals.shadowOptLevel >= SO_CLIP_SILS ) {
1041 ret.numSilPlaneIndexes = numSilQuads * 12; // this is the worst case with clipping
1042 } else {
1043 ret.numSilPlaneIndexes = numSilEdges * 6; // this is the worst case with clipping
1044 }
1045
1046 ret.totalIndexes = 0;
1047
1048 maxRetIndexes = ret.numFrontCapIndexes + ret.numRearCapIndexes + ret.numSilPlaneIndexes;
1049
1050 ret.indexes = (glIndex_t *)Mem_Alloc( maxRetIndexes * sizeof( ret.indexes[0] ) );
1051 for ( int i = 0 ; i < numOutputTris ; i++ ) {
1052 // flip the indexes so the surface triangle faces outside the shadow volume
1053 ret.indexes[i*3+0] = outputTris[i].index[2];
1054 ret.indexes[i*3+1] = outputTris[i].index[1];
1055 ret.indexes[i*3+2] = outputTris[i].index[0];
1056
1057 ret.indexes[(numOutputTris+i)*3+0] = numUniquedBeforeProjection + outputTris[i].index[0];
1058 ret.indexes[(numOutputTris+i)*3+1] = numUniquedBeforeProjection + outputTris[i].index[1];
1059 ret.indexes[(numOutputTris+i)*3+2] = numUniquedBeforeProjection + outputTris[i].index[2];
1060 }
1061 // emit the sil planes
1062 ret.totalIndexes = ret.numFrontCapIndexes + ret.numRearCapIndexes;
1063
1064 if ( dmapGlobals.shadowOptLevel >= SO_CLIP_SILS ) {
1065 // re-optimize the sil planes, cutting
1066 EmitFragmentedSilQuads();
1067 } else {
1068 // indexes for silhouette edges
1069 EmitUnoptimizedSilEdges();
1070 }
1071
1072 // we have all the verts now
1073 // create twice the uniqued verts
1074 ret.numVerts = numUniqued;
1075 ret.verts = (idVec3 *)Mem_Alloc( ret.numVerts * sizeof( ret.verts[0] ) );
1076 for ( int i = 0 ; i < numUniqued ; i++ ) {
1077 // put the vert back in global space, instead of light centered space
1078 ret.verts[i] = uniqued[i] + projectionOrigin;
1079 }
1080
1081 // set the final index count
1082 ret.numSilPlaneIndexes = ret.totalIndexes - (ret.numFrontCapIndexes + ret.numRearCapIndexes);
1083
1084 // free out local data
1085 Mem_Free( uniqued );
1086
1087 return ret;
1088 }
1089
1090 /*
1091 =================
1092 RemoveDegenerateTriangles
1093 =================
1094 */
RemoveDegenerateTriangles(srfTriangles_t * tri)1095 static void RemoveDegenerateTriangles( srfTriangles_t *tri ) {
1096 int c_removed;
1097 int i;
1098 int a, b, c;
1099
1100 // check for completely degenerate triangles
1101 c_removed = 0;
1102 for ( i = 0 ; i < tri->numIndexes ; i+=3 ) {
1103 a = tri->indexes[i];
1104 b = tri->indexes[i+1];
1105 c = tri->indexes[i+2];
1106 if ( a == b || a == c || b == c ) {
1107 c_removed++;
1108 memmove( tri->indexes + i, tri->indexes + i + 3, ( tri->numIndexes - i - 3 ) * sizeof( tri->indexes[0] ) );
1109 tri->numIndexes -= 3;
1110 if ( i < tri->numShadowIndexesNoCaps ) {
1111 tri->numShadowIndexesNoCaps -= 3;
1112 }
1113 if ( i < tri->numShadowIndexesNoFrontCaps ) {
1114 tri->numShadowIndexesNoFrontCaps -= 3;
1115 }
1116 i -= 3;
1117 }
1118 }
1119
1120 // this doesn't free the memory used by the unused verts
1121
1122 if ( c_removed ) {
1123 common->Printf( "removed %i degenerate triangles from shadow\n", c_removed );
1124 }
1125 }
1126
1127 /*
1128 ====================
1129 CleanupOptimizedShadowTris
1130
1131 Uniques all verts across the frustums
1132 removes matched sil quads at frustum seams
1133 removes degenerate tris
1134 ====================
1135 */
CleanupOptimizedShadowTris(srfTriangles_t * tri)1136 void CleanupOptimizedShadowTris( srfTriangles_t *tri ) {
1137 int i;
1138
1139 // unique all the verts
1140 maxUniqued = tri->numVerts;
1141 uniqued = (idVec3 *)_alloca( sizeof( *uniqued ) * maxUniqued );
1142 numUniqued = 0;
1143
1144 glIndex_t *remap = (glIndex_t *)_alloca( sizeof( *remap ) * tri->numVerts );
1145
1146 for ( i = 0 ; i < tri->numIndexes ; i++ ) {
1147 if ( tri->indexes[i] > tri->numVerts || tri->indexes[i] < 0 ) {
1148 common->Error( "CleanupOptimizedShadowTris: index out of range" );
1149 }
1150 }
1151
1152 for ( i = 0 ; i < tri->numVerts ; i++ ) {
1153 remap[i] = FindUniqueVert( tri->shadowVertexes[i].xyz.ToVec3() );
1154 }
1155 tri->numVerts = numUniqued;
1156 for ( i = 0 ; i < tri->numVerts ; i++ ) {
1157 tri->shadowVertexes[i].xyz.ToVec3() = uniqued[i];
1158 tri->shadowVertexes[i].xyz[3] = 1;
1159 }
1160
1161 for ( i = 0 ; i < tri->numIndexes ; i++ ) {
1162 tri->indexes[i] = remap[tri->indexes[i]];
1163 }
1164
1165 // remove matched quads
1166 int numSilIndexes = tri->numShadowIndexesNoCaps;
1167 for ( int i = 0 ; i < numSilIndexes ; i+=6 ) {
1168 int j;
1169 for ( j = i+6 ; j < numSilIndexes ; j+=6 ) {
1170 // if there is a reversed quad match, we can throw both of them out
1171 // this is not a robust check, it relies on the exact ordering of
1172 // quad indexes
1173 if ( tri->indexes[i+0] == tri->indexes[j+1]
1174 && tri->indexes[i+1] == tri->indexes[j+0]
1175 && tri->indexes[i+2] == tri->indexes[j+3]
1176 && tri->indexes[i+3] == tri->indexes[j+5]
1177 && tri->indexes[i+4] == tri->indexes[j+1]
1178 && tri->indexes[i+5] == tri->indexes[j+3] ) {
1179 break;
1180 }
1181 }
1182 if ( j == numSilIndexes ) {
1183 continue;
1184 }
1185 int k;
1186 // remove first quad
1187 for ( k = i+6 ; k < j ; k++ ) {
1188 tri->indexes[k-6] = tri->indexes[k];
1189 }
1190 // remove second quad
1191 for ( k = j+6 ; k < tri->numIndexes ; k++ ) {
1192 tri->indexes[k-12] = tri->indexes[k];
1193 }
1194 numSilIndexes -= 12;
1195 i -= 6;
1196 }
1197
1198 int removed = tri->numShadowIndexesNoCaps - numSilIndexes;
1199
1200 tri->numIndexes -= removed;
1201 tri->numShadowIndexesNoCaps -= removed;
1202 tri->numShadowIndexesNoFrontCaps -= removed;
1203
1204 // remove degenerates after we have removed quads, so the double
1205 // triangle pairing isn't disturbed
1206 RemoveDegenerateTriangles( tri );
1207 }
1208
1209 /*
1210 ========================
1211 CreateLightShadow
1212
1213 This is called from dmap in util/surface.cpp
1214 shadowerGroups should be exactly clipped to the light frustum before calling.
1215 shadowerGroups is optimized by this function, but the contents can be freed, because the returned
1216 lightShadow_t list is a further culling and optimization of the data.
1217 ========================
1218 */
CreateLightShadow(optimizeGroup_t * shadowerGroups,const mapLight_t * light)1219 srfTriangles_t *CreateLightShadow( optimizeGroup_t *shadowerGroups, const mapLight_t *light ) {;
1220
1221 common->Printf( "----- CreateLightShadow %p -----\n", light );
1222
1223 // optimize all the groups
1224 OptimizeGroupList( shadowerGroups );
1225
1226 // combine all the triangles into one list
1227 mapTri_t *combined;
1228
1229 combined = NULL;
1230 for ( optimizeGroup_t *group = shadowerGroups ; group ; group = group->nextGroup ) {
1231 combined = MergeTriLists( combined, CopyTriList( group->triList ) );
1232 }
1233
1234 if ( !combined ) {
1235 return NULL;
1236 }
1237
1238 // find uniqued vertexes
1239 srfTriangles_t *occluders = ShareMapTriVerts( combined );
1240
1241 FreeTriList( combined );
1242
1243 // find silhouette information for the triSurf
1244 R_CleanupTriangles( occluders, false, true, false );
1245
1246 // let the renderer build the shadow volume normally
1247 idRenderEntityLocal space;
1248
1249 space.modelMatrix[0] = 1;
1250 space.modelMatrix[5] = 1;
1251 space.modelMatrix[10] = 1;
1252 space.modelMatrix[15] = 1;
1253
1254 srfCullInfo_t cullInfo;
1255 memset( &cullInfo, 0, sizeof( cullInfo ) );
1256
1257 // call the normal shadow creation, but with the superOptimize flag set, which will
1258 // call back to SuperOptimizeOccluders after clipping the triangles to each frustum
1259 srfTriangles_t *shadowTris;
1260 if ( dmapGlobals.shadowOptLevel == SO_MERGE_SURFACES ) {
1261 shadowTris = R_CreateShadowVolume( &space, occluders, &light->def, SG_STATIC, cullInfo );
1262 } else {
1263 shadowTris = R_CreateShadowVolume( &space, occluders, &light->def, SG_OFFLINE, cullInfo );
1264 }
1265 R_FreeStaticTriSurf( occluders );
1266
1267 R_FreeInteractionCullInfo( cullInfo );
1268
1269 if ( shadowTris ) {
1270 dmapGlobals.totalShadowTriangles += shadowTris->numIndexes / 3;
1271 dmapGlobals.totalShadowVerts += shadowTris->numVerts / 3;
1272 }
1273
1274 return shadowTris;
1275 }
1276