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