doom3-gpl
Doom 3 GPL source release
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
tr_stencilshadow.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 "tr_local.h"
33 
34 // tr_stencilShadow.c -- creaton of stencil shadow volumes
35 
36 /*
37 
38  Should we split shadow volume surfaces when they exceed max verts
39  or max indexes?
40 
41  a problem is that the number of vertexes needed for the
42  shadow volume will be twice the number in the original,
43  and possibly up to 8/3 when near plane clipped.
44 
45  The maximum index count is 7x when not clipped and all
46  triangles are completely discrete. Near plane clipping
47  can increase this to 10x.
48 
49  The maximum expansions are always with discrete triangles.
50  Meshes of triangles will result in less index expansion because
51  there will be less silhouette edges, although it will always be
52  greater than the source if a cap is present.
53 
54  can't just project onto a plane if some surface points are
55  behind the light.
56 
57  The cases when a face is edge on to a light is robustly handled
58  with closed volumes, because only a single one of it's neighbors
59  will pass the edge test. It may be an issue with non-closed models.
60 
61  It is crucial that the shadow volumes be completely enclosed.
62  The triangles identified as shadow sources will be projected
63  directly onto the light far plane.
64  The sil edges must be handled carefully.
65  A partially clipped explicit sil edge will still generate a sil
66  edge.
67  EVERY new edge generated by clipping the triangles to the view
68  will generate a sil edge.
69 
70  If a triangle has no points inside the frustum, it is completely
71  culled away. If a sil edge is either in or on the frustum, it is
72  added.
73  If a triangle has no points outside the frustum, it does not
74  need to be clipped.
75 
76 
77 
78  USING THE STENCIL BUFFER FOR SHADOWING
79 
80  basic triangle property
81 
82  view plane inside shadow volume problem
83 
84  quad triangulation issue
85 
86  issues with silhouette optimizations
87 
88  the shapes of shadow projections are poor for sphere or box culling
89 
90  the gouraud shading problem
91 
92 
93  // epsilon culling rules:
94 
95 // the positive side of the frustum is inside
96 d = tri->verts[i].xyz * frustum[j].Normal() + frustum[j][3];
97 if ( d < LIGHT_CLIP_EPSILON ) {
98  pointCull[i] |= ( 1 << j );
99 }
100 if ( d > -LIGHT_CLIP_EPSILON ) {
101  pointCull[i] |= ( 1 << (6+j) );
102 }
103 
104 If a low order bit is set, the point is on or outside the plane
105 If a high order bit is set, the point is on or inside the plane
106 If a low order bit is clear, the point is inside the plane (definately positive)
107 If a high order bit is clear, the point is outside the plane (definately negative)
108 
109 
110 */
111 
112 #define TRIANGLE_CULLED(p1,p2,p3) ( pointCull[p1] & pointCull[p2] & pointCull[p3] & 0x3f )
113 
114 //#define TRIANGLE_CLIPPED(p1,p2,p3) ( ( pointCull[p1] | pointCull[p2] | pointCull[p3] ) & 0xfc0 )
115 #define TRIANGLE_CLIPPED(p1,p2,p3) ( ( ( pointCull[p1] & pointCull[p2] & pointCull[p3] ) & 0xfc0 ) != 0xfc0 )
116 
117 // an edge that is on the plane is NOT culled
118 #define EDGE_CULLED(p1,p2) ( ( pointCull[p1] ^ 0xfc0 ) & ( pointCull[p2] ^ 0xfc0 ) & 0xfc0 )
119 
120 #define EDGE_CLIPPED(p1,p2) ( ( pointCull[p1] & pointCull[p2] & 0xfc0 ) != 0xfc0 )
121 
122 // a point that is on the plane is NOT culled
123 //#define POINT_CULLED(p1) ( ( pointCull[p1] ^ 0xfc0 ) & 0xfc0 )
124 #define POINT_CULLED(p1) ( ( pointCull[p1] & 0xfc0 ) != 0xfc0 )
125 
126 //#define LIGHT_CLIP_EPSILON 0.001f
127 #define LIGHT_CLIP_EPSILON 0.1f
128 
129 #define MAX_CLIP_SIL_EDGES 2048
130 static int numClipSilEdges;
131 static int clipSilEdges[MAX_CLIP_SIL_EDGES][2];
132 
133 // facing will be 0 if forward facing, 1 if backwards facing
134 // grabbed with alloca
135 static byte *globalFacing;
136 
137 // faceCastsShadow will be 1 if the face is in the projection
138 // and facing the apropriate direction
139 static byte *faceCastsShadow;
140 
141 static int *remap;
142 
143 #define MAX_SHADOW_INDEXES 0x18000
144 #define MAX_SHADOW_VERTS 0x18000
145 static int numShadowIndexes;
146 static glIndex_t shadowIndexes[MAX_SHADOW_INDEXES];
147 static int numShadowVerts;
148 static idVec4 shadowVerts[MAX_SHADOW_VERTS];
149 static bool overflowed;
150 
152  {
153  idPlane( 1,0,0,0 ),
154  idPlane( 1,1,0,0 ),
155  idPlane( 1,-1,0,0 ),
156  idPlane( 1,0,1,0 ),
157  idPlane( 1,0,-1,0 ),
158  idPlane( -1,0,0,0 ),
159  },
160  {
161  idPlane( -1,0,0,0 ),
162  idPlane( -1,1,0,0 ),
163  idPlane( -1,-1,0,0 ),
164  idPlane( -1,0,1,0 ),
165  idPlane( -1,0,-1,0 ),
166  idPlane( 1,0,0,0 ),
167  },
168 
169  {
170  idPlane( 0,1,0,0 ),
171  idPlane( 0,1,1,0 ),
172  idPlane( 0,1,-1,0 ),
173  idPlane( 1,1,0,0 ),
174  idPlane( -1,1,0,0 ),
175  idPlane( 0,-1,0,0 ),
176  },
177  {
178  idPlane( 0,-1,0,0 ),
179  idPlane( 0,-1,1,0 ),
180  idPlane( 0,-1,-1,0 ),
181  idPlane( 1,-1,0,0 ),
182  idPlane( -1,-1,0,0 ),
183  idPlane( 0,1,0,0 ),
184  },
185 
186  {
187  idPlane( 0,0,1,0 ),
188  idPlane( 1,0,1,0 ),
189  idPlane( -1,0,1,0 ),
190  idPlane( 0,1,1,0 ),
191  idPlane( 0,-1,1,0 ),
192  idPlane( 0,0,-1,0 ),
193  },
194  {
195  idPlane( 0,0,-1,0 ),
196  idPlane( 1,0,-1,0 ),
197  idPlane( -1,0,-1,0 ),
198  idPlane( 0,1,-1,0 ),
199  idPlane( 0,-1,-1,0 ),
200  idPlane( 0,0,1,0 ),
201  },
202 };
203 
205 
206 static bool callOptimizer; // call the preprocessor optimizer after clipping occluders
207 
208 typedef struct {
211  int silStart;
212  int end;
213 } indexRef_t;
214 static indexRef_t indexRef[6];
215 static int indexFrustumNumber; // which shadow generating side of a light the indexRef is for
216 
217 /*
218 ===============
219 PointsOrdered
220 
221 To make sure the triangulations of the sil edges is consistant,
222 we need to be able to order two points. We don't care about how
223 they compare with any other points, just that when the same two
224 points are passed in (in either order), they will always specify
225 the same one as leading.
226 
227 Currently we need to have separate faces in different surfaces
228 order the same way, so we must look at the actual coordinates.
229 If surfaces are ever guaranteed to not have to edge match with
230 other surfaces, we could just compare indexes.
231 ===============
232 */
233 static bool PointsOrdered( const idVec3 &a, const idVec3 &b ) {
234  float i, j;
235 
236  // vectors that wind up getting an equal hash value will
237  // potentially cause a misorder, which can show as a couple
238  // crack pixels in a shadow
239 
240  // scale by some odd numbers so -8, 8, 8 will not be equal
241  // to 8, -8, 8
242 
243  // in the very rare case that these might be equal, all that would
244  // happen is an oportunity for a tiny rasterization shadow crack
245  i = a[0] + a[1]*127 + a[2]*1023;
246  j = b[0] + b[1]*127 + b[2]*1023;
247 
248  return (bool)(i < j);
249 }
250 
251 /*
252 ====================
253 R_LightProjectionMatrix
254 
255 ====================
256 */
257 void R_LightProjectionMatrix( const idVec3 &origin, const idPlane &rearPlane, idVec4 mat[4] ) {
258  idVec4 lv;
259  float lg;
260 
261  // calculate the homogenious light vector
262  lv.x = origin.x;
263  lv.y = origin.y;
264  lv.z = origin.z;
265  lv.w = 1;
266 
267  lg = rearPlane.ToVec4() * lv;
268 
269  // outer product
270  mat[0][0] = lg -rearPlane[0] * lv[0];
271  mat[0][1] = -rearPlane[1] * lv[0];
272  mat[0][2] = -rearPlane[2] * lv[0];
273  mat[0][3] = -rearPlane[3] * lv[0];
274 
275  mat[1][0] = -rearPlane[0] * lv[1];
276  mat[1][1] = lg -rearPlane[1] * lv[1];
277  mat[1][2] = -rearPlane[2] * lv[1];
278  mat[1][3] = -rearPlane[3] * lv[1];
279 
280  mat[2][0] = -rearPlane[0] * lv[2];
281  mat[2][1] = -rearPlane[1] * lv[2];
282  mat[2][2] = lg -rearPlane[2] * lv[2];
283  mat[2][3] = -rearPlane[3] * lv[2];
284 
285  mat[3][0] = -rearPlane[0] * lv[3];
286  mat[3][1] = -rearPlane[1] * lv[3];
287  mat[3][2] = -rearPlane[2] * lv[3];
288  mat[3][3] = lg -rearPlane[3] * lv[3];
289 }
290 
291 /*
292 ===================
293 R_ProjectPointsToFarPlane
294 
295 make a projected copy of the even verts into the odd spots
296 that is on the far light clip plane
297 ===================
298 */
299 static void R_ProjectPointsToFarPlane( const idRenderEntityLocal *ent, const idRenderLightLocal *light,
300  const idPlane &lightPlaneLocal,
301  int firstShadowVert, int numShadowVerts ) {
302  idVec3 lv;
303  idVec4 mat[4];
304  int i;
305  idVec4 *in;
306 
308  R_LightProjectionMatrix( lv, lightPlaneLocal, mat );
309 
310 #if 1
311  // make a projected copy of the even verts into the odd spots
312  in = &shadowVerts[firstShadowVert];
313  for ( i = firstShadowVert ; i < numShadowVerts ; i+= 2, in += 2 ) {
314  float w, oow;
315 
316  in[0].w = 1;
317 
318  w = in->ToVec3() * mat[3].ToVec3() + mat[3][3];
319  if ( w == 0 ) {
320  in[1] = in[0];
321  continue;
322  }
323 
324  oow = 1.0 / w;
325  in[1].x = ( in->ToVec3() * mat[0].ToVec3() + mat[0][3] ) * oow;
326  in[1].y = ( in->ToVec3() * mat[1].ToVec3() + mat[1][3] ) * oow;
327  in[1].z = ( in->ToVec3() * mat[2].ToVec3() + mat[2][3] ) * oow;
328  in[1].w = 1;
329  }
330 
331 #else
332  // messing with W seems to cause some depth precision problems
333 
334  // make a projected copy of the even verts into the odd spots
335  in = &shadowVerts[firstShadowVert];
336  for ( i = firstShadowVert ; i < numShadowVerts ; i+= 2, in += 2 ) {
337  in[0].w = 1;
338  in[1].x = *in * mat[0].ToVec3() + mat[0][3];
339  in[1].y = *in * mat[1].ToVec3() + mat[1][3];
340  in[1].z = *in * mat[2].ToVec3() + mat[2][3];
341  in[1].w = *in * mat[3].ToVec3() + mat[3][3];
342  }
343 #endif
344 }
345 
346 
347 
348 #define MAX_CLIPPED_POINTS 20
349 typedef struct {
350  int numVerts;
351  idVec3 verts[MAX_CLIPPED_POINTS];
352  int edgeFlags[MAX_CLIPPED_POINTS];
353 } clipTri_t;
354 
355 /*
356 =============
357 R_ChopWinding
358 
359 Clips a triangle from one buffer to another, setting edge flags
360 The returned buffer may be the same as inNum if no clipping is done
361 If entirely clipped away, clipTris[returned].numVerts == 0
362 
363 I have some worries about edge flag cases when polygons are clipped
364 multiple times near the epsilon.
365 =============
366 */
367 static int R_ChopWinding( clipTri_t clipTris[2], int inNum, const idPlane &plane ) {
368  clipTri_t *in, *out;
369  float dists[MAX_CLIPPED_POINTS];
370  int sides[MAX_CLIPPED_POINTS];
371  int counts[3];
372  float dot;
373  int i, j;
374  idVec3 *p1, *p2;
375  idVec3 mid;
376 
377  in = &clipTris[inNum];
378  out = &clipTris[inNum^1];
379  counts[0] = counts[1] = counts[2] = 0;
380 
381  // determine sides for each point
382  for ( i = 0 ; i < in->numVerts ; i++ ) {
383  dot = plane.Distance( in->verts[i] );
384  dists[i] = dot;
385  if ( dot < -LIGHT_CLIP_EPSILON ) {
386  sides[i] = SIDE_BACK;
387  } else if ( dot > LIGHT_CLIP_EPSILON ) {
388  sides[i] = SIDE_FRONT;
389  } else {
390  sides[i] = SIDE_ON;
391  }
392  counts[sides[i]]++;
393  }
394 
395  // if none in front, it is completely clipped away
396  if ( !counts[SIDE_FRONT] ) {
397  in->numVerts = 0;
398  return inNum;
399  }
400  if ( !counts[SIDE_BACK] ) {
401  return inNum; // inout stays the same
402  }
403 
404  // avoid wrapping checks by duplicating first value to end
405  sides[i] = sides[0];
406  dists[i] = dists[0];
407  in->verts[in->numVerts] = in->verts[0];
408  in->edgeFlags[in->numVerts] = in->edgeFlags[0];
409 
410  out->numVerts = 0;
411  for ( i = 0 ; i < in->numVerts ; i++ ) {
412  p1 = &in->verts[i];
413 
414  if ( sides[i] != SIDE_BACK ) {
415  out->verts[out->numVerts] = *p1;
416  if ( sides[i] == SIDE_ON && sides[i+1] == SIDE_BACK ) {
417  out->edgeFlags[out->numVerts] = 1;
418  } else {
419  out->edgeFlags[out->numVerts] = in->edgeFlags[i];
420  }
421  out->numVerts++;
422  }
423 
424  if ( (sides[i] == SIDE_FRONT && sides[i+1] == SIDE_BACK)
425  || (sides[i] == SIDE_BACK && sides[i+1] == SIDE_FRONT) ) {
426  // generate a split point
427  p2 = &in->verts[i+1];
428 
429  dot = dists[i] / (dists[i]-dists[i+1]);
430  for ( j=0 ; j<3 ; j++ ) {
431  mid[j] = (*p1)[j] + dot*((*p2)[j]-(*p1)[j]);
432  }
433 
434  out->verts[out->numVerts] = mid;
435 
436  // set the edge flag
437  if ( sides[i+1] != SIDE_FRONT ) {
438  out->edgeFlags[out->numVerts] = 1;
439  } else {
440  out->edgeFlags[out->numVerts] = in->edgeFlags[i];
441  }
442 
443  out->numVerts++;
444  }
445  }
446 
447  return inNum ^ 1;
448 }
449 
450 /*
451 ===================
452 R_ClipTriangleToLight
453 
454 Returns false if nothing is left after clipping
455 ===================
456 */
457 static bool R_ClipTriangleToLight( const idVec3 &a, const idVec3 &b, const idVec3 &c, int planeBits,
458  const idPlane frustum[6] ) {
459  int i;
460  int base;
461  clipTri_t pingPong[2], *ct;
462  int p;
463 
464  pingPong[0].numVerts = 3;
465  pingPong[0].edgeFlags[0] = 0;
466  pingPong[0].edgeFlags[1] = 0;
467  pingPong[0].edgeFlags[2] = 0;
468  pingPong[0].verts[0] = a;
469  pingPong[0].verts[1] = b;
470  pingPong[0].verts[2] = c;
471 
472  p = 0;
473  for ( i = 0 ; i < 6 ; i++ ) {
474  if ( planeBits & ( 1 << i ) ) {
475  p = R_ChopWinding( pingPong, p, frustum[i] );
476  if ( pingPong[p].numVerts < 1 ) {
477  return false;
478  }
479  }
480  }
481  ct = &pingPong[p];
482 
483  // copy the clipped points out to shadowVerts
484  if ( numShadowVerts + ct->numVerts * 2 > MAX_SHADOW_VERTS ) {
485  overflowed = true;
486  return false;
487  }
488 
489  base = numShadowVerts;
490  for ( i = 0 ; i < ct->numVerts ; i++ ) {
491  shadowVerts[ base + i*2 ].ToVec3() = ct->verts[i];
492  }
493  numShadowVerts += ct->numVerts * 2;
494 
495  if ( numShadowIndexes + 3 * ( ct->numVerts - 2 ) > MAX_SHADOW_INDEXES ) {
496  overflowed = true;
497  return false;
498  }
499 
500  for ( i = 2 ; i < ct->numVerts ; i++ ) {
501  shadowIndexes[numShadowIndexes++] = base + i * 2;
502  shadowIndexes[numShadowIndexes++] = base + ( i - 1 ) * 2;
503  shadowIndexes[numShadowIndexes++] = base;
504  }
505 
506  // any edges that were created by the clipping process will
507  // have a silhouette quad created for it, because it is one
508  // of the exterior bounds of the shadow volume
509  for ( i = 0 ; i < ct->numVerts ; i++ ) {
510  if ( ct->edgeFlags[i] ) {
511  if ( numClipSilEdges == MAX_CLIP_SIL_EDGES ) {
512  break;
513  }
514  clipSilEdges[ numClipSilEdges ][0] = base + i * 2;
515  if ( i == ct->numVerts - 1 ) {
516  clipSilEdges[ numClipSilEdges ][1] = base;
517  } else {
518  clipSilEdges[ numClipSilEdges ][1] = base + ( i + 1 ) * 2;
519  }
520  numClipSilEdges++;
521  }
522  }
523 
524  return true;
525 }
526 
527 /*
528 ===================
529 R_ClipLineToLight
530 
531 If neither point is clearly behind the clipping
532 plane, the edge will be passed unmodified. A sil edge that
533 is on a border plane must be drawn.
534 
535 If one point is clearly clipped by the plane and the
536 other point is on the plane, it will be completely removed.
537 ===================
538 */
539 static bool R_ClipLineToLight( const idVec3 &a, const idVec3 &b, const idPlane frustum[4],
540  idVec3 &p1, idVec3 &p2 ) {
541  float *clip;
542  int j;
543  float d1, d2;
544  float f;
545 
546  p1 = a;
547  p2 = b;
548 
549  // clip it
550  for ( j = 0 ; j < 6 ; j++ ) {
551  d1 = frustum[j].Distance( p1 );
552  d2 = frustum[j].Distance( p2 );
553 
554  // if both on or in front, not clipped to this plane
555  if ( d1 > -LIGHT_CLIP_EPSILON && d2 > -LIGHT_CLIP_EPSILON ) {
556  continue;
557  }
558 
559  // if one is behind and the other isn't clearly in front, the edge is clipped off
560  if ( d1 <= -LIGHT_CLIP_EPSILON && d2 < LIGHT_CLIP_EPSILON ) {
561  return false;
562  }
563  if ( d2 <= -LIGHT_CLIP_EPSILON && d1 < LIGHT_CLIP_EPSILON ) {
564  return false;
565  }
566 
567  // clip it, keeping the negative side
568  if ( d1 < 0 ) {
569  clip = p1.ToFloatPtr();
570  } else {
571  clip = p2.ToFloatPtr();
572  }
573 
574 #if 0
575  if ( idMath::Fabs(d1 - d2) < 0.001 ) {
576  d2 = d1 - 0.1;
577  }
578 #endif
579 
580  f = d1 / ( d1 - d2 );
581  clip[0] = p1[0] + f * ( p2[0] - p1[0] );
582  clip[1] = p1[1] + f * ( p2[1] - p1[1] );
583  clip[2] = p1[2] + f * ( p2[2] - p1[2] );
584  }
585 
586  return true; // retain a fragment
587 }
588 
589 
590 /*
591 ==================
592 R_AddClipSilEdges
593 
594 Add sil edges for each triangle clipped to the side of
595 the frustum.
596 
597 Only done for simple projected lights, not point lights.
598 ==================
599 */
600 static void R_AddClipSilEdges( void ) {
601  int v1, v2;
602  int v1_back, v2_back;
603  int i;
604 
605  // don't allow it to overflow
606  if ( numShadowIndexes + numClipSilEdges * 6 > MAX_SHADOW_INDEXES ) {
607  overflowed = true;
608  return;
609  }
610 
611  for ( i = 0 ; i < numClipSilEdges ; i++ ) {
612  v1 = clipSilEdges[i][0];
613  v2 = clipSilEdges[i][1];
614  v1_back = v1 + 1;
615  v2_back = v2 + 1;
616  if ( PointsOrdered( shadowVerts[ v1 ].ToVec3(), shadowVerts[ v2 ].ToVec3() ) ) {
617  shadowIndexes[numShadowIndexes++] = v1;
618  shadowIndexes[numShadowIndexes++] = v2;
619  shadowIndexes[numShadowIndexes++] = v1_back;
620  shadowIndexes[numShadowIndexes++] = v2;
621  shadowIndexes[numShadowIndexes++] = v2_back;
622  shadowIndexes[numShadowIndexes++] = v1_back;
623  } else {
624  shadowIndexes[numShadowIndexes++] = v1;
625  shadowIndexes[numShadowIndexes++] = v2;
626  shadowIndexes[numShadowIndexes++] = v2_back;
627  shadowIndexes[numShadowIndexes++] = v1;
628  shadowIndexes[numShadowIndexes++] = v2_back;
629  shadowIndexes[numShadowIndexes++] = v1_back;
630  }
631  }
632 }
633 
634 /*
635 =================
636 R_AddSilEdges
637 
638 Add quads from the front points to the projected points
639 for each silhouette edge in the light
640 =================
641 */
642 static void R_AddSilEdges( const srfTriangles_t *tri, unsigned short *pointCull, const idPlane frustum[6] ) {
643  int v1, v2;
644  int i;
645  silEdge_t *sil;
646  int numPlanes;
647 
648  numPlanes = tri->numIndexes / 3;
649 
650  // add sil edges for any true silhouette boundaries on the surface
651  for ( i = 0 ; i < tri->numSilEdges ; i++ ) {
652  sil = tri->silEdges + i;
653  if ( sil->p1 < 0 || sil->p1 > numPlanes || sil->p2 < 0 || sil->p2 > numPlanes ) {
654  common->Error( "Bad sil planes" );
655  }
656 
657  // an edge will be a silhouette edge if the face on one side
658  // casts a shadow, but the face on the other side doesn't.
659  // "casts a shadow" means that it has some surface in the projection,
660  // not just that it has the correct facing direction
661  // This will cause edges that are exactly on the frustum plane
662  // to be considered sil edges if the face inside casts a shadow.
663  if ( !( faceCastsShadow[ sil->p1 ] ^ faceCastsShadow[ sil->p2 ] ) ) {
664  continue;
665  }
666 
667  // if the edge is completely off the negative side of
668  // a frustum plane, don't add it at all. This can still
669  // happen even if the face is visible and casting a shadow
670  // if it is partially clipped
671  if ( EDGE_CULLED( sil->v1, sil->v2 ) ) {
672  continue;
673  }
674 
675  // see if the edge needs to be clipped
676  if ( EDGE_CLIPPED( sil->v1, sil->v2 ) ) {
677  if ( numShadowVerts + 4 > MAX_SHADOW_VERTS ) {
678  overflowed = true;
679  return;
680  }
681  v1 = numShadowVerts;
682  v2 = v1 + 2;
683  if ( !R_ClipLineToLight( tri->verts[ sil->v1 ].xyz, tri->verts[ sil->v2 ].xyz,
684  frustum, shadowVerts[v1].ToVec3(), shadowVerts[v2].ToVec3() ) ) {
685  continue; // clipped away
686  }
687 
688  numShadowVerts += 4;
689  } else {
690  // use the entire edge
691  v1 = remap[ sil->v1 ];
692  v2 = remap[ sil->v2 ];
693  if ( v1 < 0 || v2 < 0 ) {
694  common->Error( "R_AddSilEdges: bad remap[]" );
695  }
696  }
697 
698  // don't overflow
699  if ( numShadowIndexes + 6 > MAX_SHADOW_INDEXES ) {
700  overflowed = true;
701  return;
702  }
703 
704  // we need to choose the correct way of triangulating the silhouette quad
705  // consistantly between any two points, no matter which order they are specified.
706  // If this wasn't done, slight rasterization cracks would show in the shadow
707  // volume when two sil edges were exactly coincident
708  if ( faceCastsShadow[ sil->p2 ] ) {
709  if ( PointsOrdered( shadowVerts[ v1 ].ToVec3(), shadowVerts[ v2 ].ToVec3() ) ) {
710  shadowIndexes[numShadowIndexes++] = v1;
711  shadowIndexes[numShadowIndexes++] = v1+1;
712  shadowIndexes[numShadowIndexes++] = v2;
713  shadowIndexes[numShadowIndexes++] = v2;
714  shadowIndexes[numShadowIndexes++] = v1+1;
715  shadowIndexes[numShadowIndexes++] = v2+1;
716  } else {
717  shadowIndexes[numShadowIndexes++] = v1;
718  shadowIndexes[numShadowIndexes++] = v2+1;
719  shadowIndexes[numShadowIndexes++] = v2;
720  shadowIndexes[numShadowIndexes++] = v1;
721  shadowIndexes[numShadowIndexes++] = v1+1;
722  shadowIndexes[numShadowIndexes++] = v2+1;
723  }
724  } else {
725  if ( PointsOrdered( shadowVerts[ v1 ].ToVec3(), shadowVerts[ v2 ].ToVec3() ) ) {
726  shadowIndexes[numShadowIndexes++] = v1;
727  shadowIndexes[numShadowIndexes++] = v2;
728  shadowIndexes[numShadowIndexes++] = v1+1;
729  shadowIndexes[numShadowIndexes++] = v2;
730  shadowIndexes[numShadowIndexes++] = v2+1;
731  shadowIndexes[numShadowIndexes++] = v1+1;
732  } else {
733  shadowIndexes[numShadowIndexes++] = v1;
734  shadowIndexes[numShadowIndexes++] = v2;
735  shadowIndexes[numShadowIndexes++] = v2+1;
736  shadowIndexes[numShadowIndexes++] = v1;
737  shadowIndexes[numShadowIndexes++] = v2+1;
738  shadowIndexes[numShadowIndexes++] = v1+1;
739  }
740  }
741  }
742 }
743 
744 /*
745 ================
746 R_CalcPointCull
747 
748 Also inits the remap[] array to all -1
749 ================
750 */
751 static void R_CalcPointCull( const srfTriangles_t *tri, const idPlane frustum[6], unsigned short *pointCull ) {
752  int i;
753  int frontBits;
754  float *planeSide;
755  byte *side1, *side2;
756 
757  SIMDProcessor->Memset( remap, -1, tri->numVerts * sizeof( remap[0] ) );
758 
759  for ( frontBits = 0, i = 0; i < 6; i++ ) {
760  // get front bits for the whole surface
761  if ( tri->bounds.PlaneDistance( frustum[i] ) >= LIGHT_CLIP_EPSILON ) {
762  frontBits |= 1<<(i+6);
763  }
764  }
765 
766  // initialize point cull
767  for ( i = 0; i < tri->numVerts; i++ ) {
768  pointCull[i] = frontBits;
769  }
770 
771  // if the surface is not completely inside the light frustum
772  if ( frontBits == ( ( ( 1 << 6 ) - 1 ) ) << 6 ) {
773  return;
774  }
775 
776  planeSide = (float *) _alloca16( tri->numVerts * sizeof( float ) );
777  side1 = (byte *) _alloca16( tri->numVerts * sizeof( byte ) );
778  side2 = (byte *) _alloca16( tri->numVerts * sizeof( byte ) );
779  SIMDProcessor->Memset( side1, 0, tri->numVerts * sizeof( byte ) );
780  SIMDProcessor->Memset( side2, 0, tri->numVerts * sizeof( byte ) );
781 
782  for ( i = 0; i < 6; i++ ) {
783 
784  if ( frontBits & (1<<(i+6)) ) {
785  continue;
786  }
787 
788  SIMDProcessor->Dot( planeSide, frustum[i], tri->verts, tri->numVerts );
789  SIMDProcessor->CmpLT( side1, i, planeSide, LIGHT_CLIP_EPSILON, tri->numVerts );
790  SIMDProcessor->CmpGT( side2, i, planeSide, -LIGHT_CLIP_EPSILON, tri->numVerts );
791  }
792  for ( i = 0; i < tri->numVerts; i++ ) {
793  pointCull[i] |= side1[i] | (side2[i] << 6);
794  }
795 }
796 
797 /*
798 =================
799 R_CreateShadowVolumeInFrustum
800 
801 Adds new verts and indexes to the shadow volume.
802 
803 If the frustum completely defines the projected light,
804 makeClippedPlanes should be true, which will cause sil quads to
805 be added along all clipped edges.
806 
807 If the frustum is just part of a point light, clipped planes don't
808 need to be added.
809 =================
810 */
811 static void R_CreateShadowVolumeInFrustum( const idRenderEntityLocal *ent,
812  const srfTriangles_t *tri,
813  const idRenderLightLocal *light,
814  const idVec3 lightOrigin,
815  const idPlane frustum[6],
816  const idPlane &farPlane,
817  bool makeClippedPlanes ) {
818  int i;
819  int numTris;
820  unsigned short *pointCull;
821  int numCapIndexes;
822  int firstShadowIndex;
823  int firstShadowVert;
824  int cullBits;
825 
826  pointCull = (unsigned short *)_alloca16( tri->numVerts * sizeof( pointCull[0] ) );
827 
828  // test the vertexes for inside the light frustum, which will allow
829  // us to completely cull away some triangles from consideration.
830  R_CalcPointCull( tri, frustum, pointCull );
831 
832  // this may not be the first frustum added to the volume
833  firstShadowIndex = numShadowIndexes;
834  firstShadowVert = numShadowVerts;
835 
836  // decide which triangles front shadow volumes, clipping as needed
837  numClipSilEdges = 0;
838  numTris = tri->numIndexes / 3;
839  for ( i = 0 ; i < numTris ; i++ ) {
840  int i1, i2, i3;
841 
842  faceCastsShadow[i] = 0; // until shown otherwise
843 
844  // if it isn't facing the right way, don't add it
845  // to the shadow volume
846  if ( globalFacing[i] ) {
847  continue;
848  }
849 
850  i1 = tri->silIndexes[ i*3 + 0 ];
851  i2 = tri->silIndexes[ i*3 + 1 ];
852  i3 = tri->silIndexes[ i*3 + 2 ];
853 
854  // if all the verts are off one side of the frustum,
855  // don't add any of them
856  if ( TRIANGLE_CULLED( i1, i2, i3 ) ) {
857  continue;
858  }
859 
860  // make sure the verts that are not on the negative sides
861  // of the frustum are copied over.
862  // we need to get the original verts even from clipped triangles
863  // so the edges reference correctly, because an edge may be unclipped
864  // even when a triangle is clipped.
865  if ( numShadowVerts + 6 > MAX_SHADOW_VERTS ) {
866  overflowed = true;
867  return;
868  }
869 
870  if ( !POINT_CULLED(i1) && remap[i1] == -1 ) {
871  remap[i1] = numShadowVerts;
872  shadowVerts[ numShadowVerts ].ToVec3() = tri->verts[i1].xyz;
873  numShadowVerts+=2;
874  }
875  if ( !POINT_CULLED(i2) && remap[i2] == -1 ) {
876  remap[i2] = numShadowVerts;
877  shadowVerts[ numShadowVerts ].ToVec3() = tri->verts[i2].xyz;
878  numShadowVerts+=2;
879  }
880  if ( !POINT_CULLED(i3) && remap[i3] == -1 ) {
881  remap[i3] = numShadowVerts;
882  shadowVerts[ numShadowVerts ].ToVec3() = tri->verts[i3].xyz;
883  numShadowVerts+=2;
884  }
885 
886  // clip the triangle if any points are on the negative sides
887  if ( TRIANGLE_CLIPPED( i1, i2, i3 ) ) {
888  cullBits = ( ( pointCull[ i1 ] ^ 0xfc0 ) | ( pointCull[ i2 ] ^ 0xfc0 ) | ( pointCull[ i3 ] ^ 0xfc0 ) ) >> 6;
889  // this will also define clip edges that will become
890  // silhouette planes
891  if ( R_ClipTriangleToLight( tri->verts[i1].xyz, tri->verts[i2].xyz,
892  tri->verts[i3].xyz, cullBits, frustum ) ) {
893  faceCastsShadow[i] = 1;
894  }
895  } else {
896  // instead of overflowing or drawing a streamer shadow, don't draw a shadow at all
897  if ( numShadowIndexes + 3 > MAX_SHADOW_INDEXES ) {
898  overflowed = true;
899  return;
900  }
901  if ( remap[i1] == -1 || remap[i2] == -1 || remap[i3] == -1 ) {
902  common->Error( "R_CreateShadowVolumeInFrustum: bad remap[]" );
903  }
904  shadowIndexes[numShadowIndexes++] = remap[i3];
905  shadowIndexes[numShadowIndexes++] = remap[i2];
906  shadowIndexes[numShadowIndexes++] = remap[i1];
907  faceCastsShadow[i] = 1;
908  }
909  }
910 
911  // add indexes for the back caps, which will just be reversals of the
912  // front caps using the back vertexes
913  numCapIndexes = numShadowIndexes - firstShadowIndex;
914 
915  // if no faces have been defined for the shadow volume,
916  // there won't be anything at all
917  if ( numCapIndexes == 0 ) {
918  return;
919  }
920 
921  //--------------- off-line processing ------------------
922 
923  // if we are running from dmap, perform the (very) expensive shadow optimizations
924  // to remove internal sil edges and optimize the caps
925  if ( callOptimizer ) {
926  optimizedShadow_t opt;
927 
928  // project all of the vertexes to the shadow plane, generating
929  // an equal number of back vertexes
930 // R_ProjectPointsToFarPlane( ent, light, farPlane, firstShadowVert, numShadowVerts );
931 
932  opt = SuperOptimizeOccluders( shadowVerts, shadowIndexes + firstShadowIndex, numCapIndexes, farPlane, lightOrigin );
933 
934  // pull off the non-optimized data
935  numShadowIndexes = firstShadowIndex;
936  numShadowVerts = firstShadowVert;
937 
938  // add the optimized data
939  if ( numShadowIndexes + opt.totalIndexes > MAX_SHADOW_INDEXES
940  || numShadowVerts + opt.numVerts > MAX_SHADOW_VERTS ) {
941  overflowed = true;
942  common->Printf( "WARNING: overflowed MAX_SHADOW tables, shadow discarded\n" );
943  Mem_Free( opt.verts );
944  Mem_Free( opt.indexes );
945  return;
946  }
947 
948  for ( i = 0 ; i < opt.numVerts ; i++ ) {
949  shadowVerts[numShadowVerts+i][0] = opt.verts[i][0];
950  shadowVerts[numShadowVerts+i][1] = opt.verts[i][1];
951  shadowVerts[numShadowVerts+i][2] = opt.verts[i][2];
952  shadowVerts[numShadowVerts+i][3] = 1;
953  }
954  for ( i = 0 ; i < opt.totalIndexes ; i++ ) {
955  int index = opt.indexes[i];
956  if ( index < 0 || index > opt.numVerts ) {
957  common->Error( "optimized shadow index out of range" );
958  }
959  shadowIndexes[numShadowIndexes+i] = index + numShadowVerts;
960  }
961 
962  numShadowVerts += opt.numVerts;
963  numShadowIndexes += opt.totalIndexes;
964 
965  // note the index distribution so we can sort all the caps after all the sils
966  indexRef[indexFrustumNumber].frontCapStart = firstShadowIndex;
967  indexRef[indexFrustumNumber].rearCapStart = firstShadowIndex+opt.numFrontCapIndexes;
968  indexRef[indexFrustumNumber].silStart = firstShadowIndex+opt.numFrontCapIndexes+opt.numRearCapIndexes;
969  indexRef[indexFrustumNumber].end = numShadowIndexes;
970  indexFrustumNumber++;
971 
972  Mem_Free( opt.verts );
973  Mem_Free( opt.indexes );
974  return;
975  }
976 
977  //--------------- real-time processing ------------------
978 
979  // the dangling edge "face" is never considered to cast a shadow,
980  // so any face with dangling edges that casts a shadow will have
981  // it's dangling sil edge trigger a sil plane
982  faceCastsShadow[numTris] = 0;
983 
984  // instead of overflowing or drawing a streamer shadow, don't draw a shadow at all
985  // if we ran out of space
986  if ( numShadowIndexes + numCapIndexes > MAX_SHADOW_INDEXES ) {
987  overflowed = true;
988  return;
989  }
990  for ( i = 0 ; i < numCapIndexes ; i += 3 ) {
991  shadowIndexes[ numShadowIndexes + i + 0 ] = shadowIndexes[ firstShadowIndex + i + 2 ] + 1;
992  shadowIndexes[ numShadowIndexes + i + 1 ] = shadowIndexes[ firstShadowIndex + i + 1 ] + 1;
993  shadowIndexes[ numShadowIndexes + i + 2 ] = shadowIndexes[ firstShadowIndex + i + 0 ] + 1;
994  }
995  numShadowIndexes += numCapIndexes;
996 
997 c_caps += numCapIndexes * 2;
998 
999 int preSilIndexes = numShadowIndexes;
1000 
1001  // if any triangles were clipped, we will have a list of edges
1002  // on the frustum which must now become sil edges
1003  if ( makeClippedPlanes ) {
1004  R_AddClipSilEdges();
1005  }
1006 
1007  // any edges that are a transition between a shadowing and
1008  // non-shadowing triangle will cast a silhouette edge
1009  R_AddSilEdges( tri, pointCull, frustum );
1010 
1011 c_sils += numShadowIndexes - preSilIndexes;
1012 
1013  // project all of the vertexes to the shadow plane, generating
1014  // an equal number of back vertexes
1015  R_ProjectPointsToFarPlane( ent, light, farPlane, firstShadowVert, numShadowVerts );
1016 
1017  // note the index distribution so we can sort all the caps after all the sils
1018  indexRef[indexFrustumNumber].frontCapStart = firstShadowIndex;
1019  indexRef[indexFrustumNumber].rearCapStart = firstShadowIndex+numCapIndexes;
1020  indexRef[indexFrustumNumber].silStart = preSilIndexes;
1021  indexRef[indexFrustumNumber].end = numShadowIndexes;
1022  indexFrustumNumber++;
1023 }
1024 
1025 /*
1026 ===================
1027 R_MakeShadowFrustums
1028 
1029 Called at definition derivation time
1030 ===================
1031 */
1033  int i, j;
1034 
1035  if ( light->parms.pointLight ) {
1036 #if 0
1037  idVec3 adjustedRadius;
1038 
1039  // increase the light radius to cover any origin offsets.
1040  // this will cause some shadows to extend out of the exact light
1041  // volume, but is simpler than adjusting all the frustums
1042  adjustedRadius[0] = light->parms.lightRadius[0] + idMath::Fabs( light->parms.lightCenter[0] );
1043  adjustedRadius[1] = light->parms.lightRadius[1] + idMath::Fabs( light->parms.lightCenter[1] );
1044  adjustedRadius[2] = light->parms.lightRadius[2] + idMath::Fabs( light->parms.lightCenter[2] );
1045 
1046  light->numShadowFrustums = 0;
1047  // a point light has to project against six planes
1048  for ( i = 0 ; i < 6 ; i++ ) {
1049  shadowFrustum_t *frust = &light->shadowFrustums[ light->numShadowFrustums ];
1050 
1051  frust->numPlanes = 6;
1052  frust->makeClippedPlanes = false;
1053  for ( j = 0 ; j < 6 ; j++ ) {
1054  idPlane &plane = frust->planes[j];
1055  plane[0] = pointLightFrustums[i][j][0] / adjustedRadius[0];
1056  plane[1] = pointLightFrustums[i][j][1] / adjustedRadius[1];
1057  plane[2] = pointLightFrustums[i][j][2] / adjustedRadius[2];
1058  plane.Normalize();
1059  plane[3] = -( plane.Normal() * light->globalLightOrigin );
1060  if ( j == 5 ) {
1061  plane[3] += adjustedRadius[i>>1];
1062  }
1063  }
1064 
1065  light->numShadowFrustums++;
1066  }
1067 #else
1068  // exact projection,taking into account asymetric frustums when
1069  // globalLightOrigin isn't centered
1070 
1071  static int faceCorners[6][4] = {
1072  { 7, 5, 1, 3 }, // positive X side
1073  { 4, 6, 2, 0 }, // negative X side
1074  { 6, 7, 3, 2 }, // positive Y side
1075  { 5, 4, 0, 1 }, // negative Y side
1076  { 6, 4, 5, 7 }, // positive Z side
1077  { 3, 1, 0, 2 } // negative Z side
1078  };
1079  static int faceEdgeAdjacent[6][4] = {
1080  { 4, 4, 2, 2 }, // positive X side
1081  { 7, 7, 1, 1 }, // negative X side
1082  { 5, 5, 0, 0 }, // positive Y side
1083  { 6, 6, 3, 3 }, // negative Y side
1084  { 0, 0, 3, 3 }, // positive Z side
1085  { 5, 5, 6, 6 } // negative Z side
1086  };
1087 
1088  bool centerOutside = false;
1089 
1090  // if the light center of projection is outside the light bounds,
1091  // we will need to build the planes a little differently
1092  if ( fabs( light->parms.lightCenter[0] ) > light->parms.lightRadius[0]
1093  || fabs( light->parms.lightCenter[1] ) > light->parms.lightRadius[1]
1094  || fabs( light->parms.lightCenter[2] ) > light->parms.lightRadius[2] ) {
1095  centerOutside = true;
1096  }
1097 
1098  // make the corners
1099  idVec3 corners[8];
1100 
1101  for ( i = 0 ; i < 8 ; i++ ) {
1102  idVec3 temp;
1103  for ( j = 0 ; j < 3 ; j++ ) {
1104  if ( i & ( 1 << j ) ) {
1105  temp[j] = light->parms.lightRadius[j];
1106  } else {
1107  temp[j] = -light->parms.lightRadius[j];
1108  }
1109  }
1110 
1111  // transform to global space
1112  corners[i] = light->parms.origin + light->parms.axis * temp;
1113  }
1114 
1115  light->numShadowFrustums = 0;
1116  for ( int side = 0 ; side < 6 ; side++ ) {
1117  shadowFrustum_t *frust = &light->shadowFrustums[ light->numShadowFrustums ];
1118  idVec3 &p1 = corners[faceCorners[side][0]];
1119  idVec3 &p2 = corners[faceCorners[side][1]];
1120  idVec3 &p3 = corners[faceCorners[side][2]];
1121  idPlane backPlane;
1122 
1123  // plane will have positive side inward
1124  backPlane.FromPoints( p1, p2, p3 );
1125 
1126  // if center of projection is on the wrong side, skip
1127  float d = backPlane.Distance( light->globalLightOrigin );
1128  if ( d < 0 ) {
1129  continue;
1130  }
1131 
1132  frust->numPlanes = 6;
1133  frust->planes[5] = backPlane;
1134  frust->planes[4] = backPlane; // we don't really need the extra plane
1135 
1136  // make planes with positive side facing inwards in light local coordinates
1137  for ( int edge = 0 ; edge < 4 ; edge++ ) {
1138  idVec3 &p1 = corners[faceCorners[side][edge]];
1139  idVec3 &p2 = corners[faceCorners[side][(edge+1)&3]];
1140 
1141  // create a plane that goes through the center of projection
1142  frust->planes[edge].FromPoints( p2, p1, light->globalLightOrigin );
1143 
1144  // see if we should use an adjacent plane instead
1145  if ( centerOutside ) {
1146  idVec3 &p3 = corners[faceEdgeAdjacent[side][edge]];
1147  idPlane sidePlane;
1148 
1149  sidePlane.FromPoints( p2, p1, p3 );
1150  d = sidePlane.Distance( light->globalLightOrigin );
1151  if ( d < 0 ) {
1152  // use this plane instead of the edged plane
1153  frust->planes[edge] = sidePlane;
1154  }
1155  // we can't guarantee a neighbor, so add sill planes at edge
1156  light->shadowFrustums[ light->numShadowFrustums ].makeClippedPlanes = true;
1157  }
1158  }
1159  light->numShadowFrustums++;
1160  }
1161 
1162 #endif
1163  return;
1164  }
1165 
1166  // projected light
1167 
1168  light->numShadowFrustums = 1;
1169  shadowFrustum_t *frust = &light->shadowFrustums[ 0 ];
1170 
1171  // flip and transform the frustum planes so the positive side faces
1172  // inward in local coordinates
1173 
1174  // it is important to clip against even the near clip plane, because
1175  // many projected lights that are faking area lights will have their
1176  // origin behind solid surfaces.
1177  for ( i = 0 ; i < 6 ; i++ ) {
1178  idPlane &plane = frust->planes[i];
1179 
1180  plane.SetNormal( -light->frustum[i].Normal() );
1181  plane.SetDist( -light->frustum[i].Dist() );
1182  }
1183 
1184  frust->numPlanes = 6;
1185 
1186  frust->makeClippedPlanes = true;
1187  // projected lights don't have shared frustums, so any clipped edges
1188  // right on the planes must have a sil plane created for them
1189 }
1190 
1191 /*
1192 =================
1193 R_CreateShadowVolume
1194 
1195 The returned surface will have a valid bounds and radius for culling.
1196 
1197 Triangles are clipped to the light frustum before projecting.
1198 
1199 A single triangle can clip to as many as 7 vertexes, so
1200 the worst case expansion is 2*(numindexes/3)*7 verts when counting both
1201 the front and back caps, although it will usually only be a modest
1202 increase in vertexes for closed modesl
1203 
1204 The worst case index count is much larger, when the 7 vertex clipped triangle
1205 needs 15 indexes for the front, 15 for the back, and 42 (a quad on seven sides)
1206 for the sides, for a total of 72 indexes from the original 3. Ouch.
1207 
1208 NULL may be returned if the surface doesn't create a shadow volume at all,
1209 as with a single face that the light is behind.
1210 
1211 If an edge is within an epsilon of the border of the volume, it must be treated
1212 as if it is clipped for triangles, generating a new sil edge, and act
1213 as if it was culled for edges, because the sil edge will have been
1214 generated by the triangle irregardless of if it actually was a sil edge.
1215 =================
1216 */
1218  const srfTriangles_t *tri, const idRenderLightLocal *light,
1219  shadowGen_t optimize, srfCullInfo_t &cullInfo ) {
1220  int i, j;
1221  idVec3 lightOrigin;
1222  srfTriangles_t *newTri;
1223  int capPlaneBits;
1224 
1225  if ( !r_shadows.GetBool() ) {
1226  return NULL;
1227  }
1228 
1229  if ( tri->numSilEdges == 0 || tri->numIndexes == 0 || tri->numVerts == 0 ) {
1230  return NULL;
1231  }
1232 
1233  if ( tri->numIndexes < 0 ) {
1234  common->Error( "R_CreateShadowVolume: tri->numIndexes = %i", tri->numIndexes );
1235  }
1236 
1237  if ( tri->numVerts < 0 ) {
1238  common->Error( "R_CreateShadowVolume: tri->numVerts = %i", tri->numVerts );
1239  }
1240 
1242 
1243  // use the fast infinite projection in dynamic situations, which
1244  // trades somewhat more overdraw and no cap optimizations for
1245  // a very simple generation process
1246  if ( optimize == SG_DYNAMIC && r_useTurboShadow.GetBool() ) {
1248  return R_CreateVertexProgramTurboShadowVolume( ent, tri, light, cullInfo );
1249  } else {
1250  return R_CreateTurboShadowVolume( ent, tri, light, cullInfo );
1251  }
1252  }
1253 
1254  R_CalcInteractionFacing( ent, tri, light, cullInfo );
1255 
1256  int numFaces = tri->numIndexes / 3;
1257  int allFront = 1;
1258  for ( i = 0; i < numFaces && allFront; i++ ) {
1259  allFront &= cullInfo.facing[i];
1260  }
1261  if ( allFront ) {
1262  // if no faces are the right direction, don't make a shadow at all
1263  return NULL;
1264  }
1265 
1266  // clear the shadow volume
1267  numShadowIndexes = 0;
1268  numShadowVerts = 0;
1269  overflowed = false;
1270  indexFrustumNumber = 0;
1271  capPlaneBits = 0;
1272  callOptimizer = (optimize == SG_OFFLINE);
1273 
1274  // the facing information will be the same for all six projections
1275  // from a point light, as well as for any directed lights
1276  globalFacing = cullInfo.facing;
1277  faceCastsShadow = (byte *)_alloca16( tri->numIndexes / 3 + 1 ); // + 1 for fake dangling edge face
1278  remap = (int *)_alloca16( tri->numVerts * sizeof( remap[0] ) );
1279 
1280  R_GlobalPointToLocal( ent->modelMatrix, light->globalLightOrigin, lightOrigin );
1281 
1282  // run through all the shadow frustums, which is one for a projected light,
1283  // and usually six for a point light, but point lights with centers outside
1284  // the box may have less
1285  for ( int frustumNum = 0 ; frustumNum < light->numShadowFrustums ; frustumNum++ ) {
1286  const shadowFrustum_t *frust = &light->shadowFrustums[frustumNum];
1287  ALIGN16( idPlane frustum[6] );
1288 
1289  // transform the planes into entity space
1290  // we could share and reverse some of the planes between frustums for a minor
1291  // speed increase
1292 
1293  // the cull test is redundant for a single shadow frustum projected light, because
1294  // the surface has already been checked against the main light frustums
1295 
1296  for ( j = 0 ; j < frust->numPlanes ; j++ ) {
1297  R_GlobalPlaneToLocal( ent->modelMatrix, frust->planes[j], frustum[j] );
1298 
1299  // try to cull the entire surface against this frustum
1300  float d = tri->bounds.PlaneDistance( frustum[j] );
1301  if ( d < -LIGHT_CLIP_EPSILON ) {
1302  break;
1303  }
1304  }
1305  if ( j != frust->numPlanes ) {
1306  continue;
1307  }
1308  // we need to check all the triangles
1309  int oldFrustumNumber = indexFrustumNumber;
1310 
1311  R_CreateShadowVolumeInFrustum( ent, tri, light, lightOrigin, frustum, frustum[5], frust->makeClippedPlanes );
1312 
1313  // if we couldn't make a complete shadow volume, it is better to
1314  // not draw one at all, avoiding streamer problems
1315  if ( overflowed ) {
1316  return NULL;
1317  }
1318 
1319  if ( indexFrustumNumber != oldFrustumNumber ) {
1320  // note that we have caps projected against this frustum,
1321  // which may allow us to skip drawing the caps if all projected
1322  // planes face away from the viewer and the viewer is outside the light volume
1323  capPlaneBits |= 1<<frustumNum;
1324  }
1325  }
1326 
1327  // if no faces have been defined for the shadow volume,
1328  // there won't be anything at all
1329  if ( numShadowIndexes == 0 ) {
1330  return NULL;
1331  }
1332 
1333  // this should have been prevented by the overflowed flag, so if it ever happens,
1334  // it is a code error
1335  if ( numShadowVerts > MAX_SHADOW_VERTS || numShadowIndexes > MAX_SHADOW_INDEXES ) {
1336  common->FatalError( "Shadow volume exceeded allocation" );
1337  }
1338 
1339  // allocate a new surface for the shadow volume
1340  newTri = R_AllocStaticTriSurf();
1341 
1342  // we might consider setting this, but it would only help for
1343  // large lights that are partially off screen
1344  newTri->bounds.Clear();
1345 
1346  // copy off the verts and indexes
1347  newTri->numVerts = numShadowVerts;
1348  newTri->numIndexes = numShadowIndexes;
1349 
1350  // the shadow verts will go into a main memory buffer as well as a vertex
1351  // cache buffer, so they can be copied back if they are purged
1352  R_AllocStaticTriSurfShadowVerts( newTri, newTri->numVerts );
1353  SIMDProcessor->Memcpy( newTri->shadowVertexes, shadowVerts, newTri->numVerts * sizeof( newTri->shadowVertexes[0] ) );
1354 
1355  R_AllocStaticTriSurfIndexes( newTri, newTri->numIndexes );
1356 
1357  if ( 1 /* sortCapIndexes */ ) {
1358  newTri->shadowCapPlaneBits = capPlaneBits;
1359 
1360  // copy the sil indexes first
1361  newTri->numShadowIndexesNoCaps = 0;
1362  for ( i = 0 ; i < indexFrustumNumber ; i++ ) {
1363  int c = indexRef[i].end - indexRef[i].silStart;
1365  shadowIndexes+indexRef[i].silStart, c * sizeof( newTri->indexes[0] ) );
1366  newTri->numShadowIndexesNoCaps += c;
1367  }
1368  // copy rear cap indexes next
1370  for ( i = 0 ; i < indexFrustumNumber ; i++ ) {
1371  int c = indexRef[i].silStart - indexRef[i].rearCapStart;
1373  shadowIndexes+indexRef[i].rearCapStart, c * sizeof( newTri->indexes[0] ) );
1374  newTri->numShadowIndexesNoFrontCaps += c;
1375  }
1376  // copy front cap indexes last
1377  newTri->numIndexes = newTri->numShadowIndexesNoFrontCaps;
1378  for ( i = 0 ; i < indexFrustumNumber ; i++ ) {
1379  int c = indexRef[i].rearCapStart - indexRef[i].frontCapStart;
1380  SIMDProcessor->Memcpy( newTri->indexes+newTri->numIndexes,
1381  shadowIndexes+indexRef[i].frontCapStart, c * sizeof( newTri->indexes[0] ) );
1382  newTri->numIndexes += c;
1383  }
1384 
1385  } else {
1386  newTri->shadowCapPlaneBits = 63; // we don't have optimized index lists
1387  SIMDProcessor->Memcpy( newTri->indexes, shadowIndexes, newTri->numIndexes * sizeof( newTri->indexes[0] ) );
1388  }
1389 
1390  if ( optimize == SG_OFFLINE ) {
1391  CleanupOptimizedShadowTris( newTri );
1392  }
1393 
1394  return newTri;
1395 }
shadowGen_t
Definition: tr_local.h:1399
int numShadowIndexesNoFrontCaps
Definition: Model.h:119
int shadowCapPlaneBits
Definition: Model.h:122
glIndex_t p1
Definition: Model.h:64
#define POINT_CULLED(p1)
byte * facing
Definition: Interaction.h:51
idPlane pointLightFrustums[6][6]
void CleanupOptimizedShadowTris(srfTriangles_t *tri)
idVec3 lightCenter
Definition: RenderWorld.h:179
bool FromPoints(const idVec3 &p1, const idVec3 &p2, const idVec3 &p3, bool fixDegenerate=true)
Definition: Plane.h:279
const idVec3 & Normal(void) const
Definition: Plane.h:239
idPlane frustum[6]
Definition: tr_local.h:219
glIndex_t * silIndexes
Definition: Model.h:104
int numVerts
Definition: Model.h:98
bool makeClippedPlanes
Definition: tr_local.h:133
#define MAX_CLIP_SIL_EDGES
float y
Definition: Vector.h:811
int c_sils
void R_CalcInteractionFacing(const idRenderEntityLocal *ent, const srfTriangles_t *tri, const idRenderLightLocal *light, srfCullInfo_t &cullInfo)
Definition: Interaction.cpp:55
#define SIDE_BACK
Definition: Plane.h:48
idCVar r_useShadowVertexProgram("r_useShadowVertexProgram","1", CVAR_RENDERER|CVAR_BOOL,"do the shadow projection in the vertex program on capable cards")
const float * ToFloatPtr(void) const
Definition: Vector.h:719
float Distance(const idVec3 &v) const
Definition: Plane.h:324
#define MAX_CLIPPED_POINTS
idVec3 xyz
Definition: DrawVert.h:42
float z
Definition: Vector.h:812
float z
Definition: Vector.h:320
srfTriangles_t * R_CreateVertexProgramTurboShadowVolume(const idRenderEntityLocal *ent, const srfTriangles_t *tri, const idRenderLightLocal *light, srfCullInfo_t &cullInfo)
renderLight_t parms
Definition: tr_local.h:191
const idVec4 & ToVec4(void) const
Definition: Plane.h:375
Definition: Vector.h:316
performanceCounters_t pc
Definition: tr_local.h:788
glIndex_t p2
Definition: Model.h:64
silEdge_t * silEdges
Definition: Model.h:113
idCVar r_shadows("r_shadows","1", CVAR_RENDERER|CVAR_BOOL|CVAR_ARCHIVE,"enable shadows")
float modelMatrix[16]
Definition: tr_local.h:253
void Clear(void)
Definition: Bounds.h:201
srfTriangles_t * R_AllocStaticTriSurf(void)
Definition: tr_trisurf.cpp:523
virtual void VPCALL Memset(void *dst, const int val, const int count)=0
void SetNormal(const idVec3 &normal)
Definition: Plane.h:233
float x
Definition: Vector.h:318
int i
Definition: process.py:33
#define TRIANGLE_CULLED(p1, p2, p3)
#define MAX_SHADOW_VERTS
shadowFrustum_t shadowFrustums[6]
Definition: tr_local.h:224
int edgeFlags[MAX_CLIPPED_POINTS]
idVec3 verts[MAX_CLIPPED_POINTS]
int numSilEdges
Definition: Model.h:112
idVec3 * verts
Definition: tr_local.h:1442
GLfloat GLfloat GLfloat v2
Definition: glext.h:3608
glIndex_t v2
Definition: Model.h:65
bool backEndRendererHasVertexPrograms
Definition: tr_local.h:763
virtual void VPCALL CmpLT(byte *dst, const float *src0, const float constant, const int count)=0
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
idVec3 lightRadius
Definition: RenderWorld.h:178
void SetDist(const float dist)
Definition: Plane.h:275
#define EDGE_CULLED(p1, p2)
idBounds bounds
Definition: Model.h:87
static float Fabs(float f)
Definition: Math.h:779
idCommon * common
Definition: Common.cpp:206
void R_MakeShadowFrustums(idRenderLightLocal *light)
float PlaneDistance(const idPlane &plane) const
Definition: Bounds.cpp:83
int c_caps
#define NULL
Definition: Lib.h:88
int glIndex_t
Definition: Model.h:52
float y
Definition: Vector.h:319
#define EDGE_CLIPPED(p1, p2)
virtual void virtual void FatalError(const char *fmt,...) id_attribute((format(printf
void R_LightProjectionMatrix(const idVec3 &origin, const idPlane &rearPlane, idVec4 mat[4])
Definition: Plane.h:71
virtual void VPCALL Dot(float *dst, const idVec3 &constant, const idVec3 *src, const int count)=0
float w
Definition: Vector.h:813
void R_AllocStaticTriSurfShadowVerts(srfTriangles_t *tri, int numVerts)
Definition: tr_trisurf.cpp:575
void Mem_Free(void *ptr)
Definition: Heap.cpp:1087
shadowCache_t * shadowVertexes
Definition: Model.h:127
GLubyte GLubyte GLubyte a
Definition: glext.h:4662
virtual void Printf(const char *fmt,...) id_attribute((format(printf
float Normalize(bool fixDegenerate=true)
Definition: Plane.h:247
#define MAX_SHADOW_INDEXES
GLfloat GLfloat v1
Definition: glext.h:3607
virtual void VPCALL Memcpy(void *dst, const void *src, const int count)=0
GLubyte GLubyte b
Definition: glext.h:4662
idPlane planes[6]
Definition: tr_local.h:127
int numShadowIndexesNoCaps
Definition: Model.h:120
idCVar r_useTurboShadow("r_useTurboShadow","1", CVAR_RENDERER|CVAR_BOOL,"use the infinite projection with W technique for dynamic shadows")
void R_GlobalPointToLocal(const float modelMatrix[16], const idVec3 &in, idVec3 &out)
Definition: tr_main.cpp:522
#define SIDE_ON
Definition: Plane.h:49
glIndex_t * indexes
Definition: tr_local.h:1444
bool GetBool(void) const
Definition: CVarSystem.h:142
#define TRIANGLE_CLIPPED(p1, p2, p3)
tuple f
Definition: idal.py:89
GLint GLint i2
Definition: qgl.h:261
glIndex_t v1
Definition: Model.h:65
GLuint in
Definition: glext.h:5388
srfTriangles_t * R_CreateTurboShadowVolume(const idRenderEntityLocal *ent, const srfTriangles_t *tri, const idRenderLightLocal *light, srfCullInfo_t &cullInfo)
unsigned char byte
Definition: Lib.h:75
optimizedShadow_t SuperOptimizeOccluders(idVec4 *verts, glIndex_t *indexes, int numIndexes, idPlane projectionPlane, idVec3 projectionOrigin)
GLint i1
Definition: qgl.h:261
glIndex_t * indexes
Definition: Model.h:102
idRenderSystemLocal tr
const idVec3 & ToVec3(void) const
Definition: Vector.h:1043
virtual void VPCALL CmpGT(byte *dst, const float *src0, const float constant, const int count)=0
void R_AllocStaticTriSurfIndexes(srfTriangles_t *tri, int numIndexes)
Definition: tr_trisurf.cpp:565
GLint j
Definition: qgl.h:264
float dot(float a[], float b[])
Definition: Model_lwo.cpp:3883
int numIndexes
Definition: Model.h:101
#define LIGHT_CLIP_EPSILON
virtual void Error(const char *fmt,...) id_attribute((format(printf
GLfloat GLfloat p
Definition: glext.h:4674
srfTriangles_t * R_CreateShadowVolume(const idRenderEntityLocal *ent, const srfTriangles_t *tri, const idRenderLightLocal *light, shadowGen_t optimize, srfCullInfo_t &cullInfo)
#define SIDE_FRONT
Definition: Plane.h:47
float x
Definition: Vector.h:810
void R_GlobalPlaneToLocal(const float modelMatrix[16], const idPlane &in, idPlane &out)
Definition: tr_main.cpp:547
float Dist(void) const
Definition: Plane.h:271
idDrawVert * verts
Definition: Model.h:99
idVec3 globalLightOrigin
Definition: tr_local.h:216
idSIMDProcessor * SIMDProcessor
Definition: Simd.cpp:43