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