2 ===========================================================================
5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
7 This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).
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.
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.
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/>.
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.
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.
26 ===========================================================================
29 #include "../idlib/precompiled.h"
34 // tr_stencilShadow.c -- creaton of stencil shadow volumes
38 Should we split shadow volume surfaces when they exceed max verts
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.
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.
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.
54 can't just project onto a plane if some surface points are
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.
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
67 EVERY new edge generated by clipping the triangles to the view
68 will generate a sil edge.
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
73 If a triangle has no points outside the frustum, it does not
78 USING THE STENCIL BUFFER FOR SHADOWING
80 basic triangle property
82 view plane inside shadow volume problem
84 quad triangulation issue
86 issues with silhouette optimizations
88 the shapes of shadow projections are poor for sphere or box culling
90 the gouraud shading problem
93 // epsilon culling rules:
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 );
100 if ( d > -LIGHT_CLIP_EPSILON ) {
101 pointCull[i] |= ( 1 << (6+j) );
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)
112 #define TRIANGLE_CULLED(p1,p2,p3) ( pointCull[p1] & pointCull[p2] & pointCull[p3] & 0x3f )
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 )
117 // an edge that is on the plane is NOT culled
118 #define EDGE_CULLED(p1,p2) ( ( pointCull[p1] ^ 0xfc0 ) & ( pointCull[p2] ^ 0xfc0 ) & 0xfc0 )
120 #define EDGE_CLIPPED(p1,p2) ( ( pointCull[p1] & pointCull[p2] & 0xfc0 ) != 0xfc0 )
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 )
126 //#define LIGHT_CLIP_EPSILON 0.001f
127 #define LIGHT_CLIP_EPSILON 0.1f
129 #define MAX_CLIP_SIL_EDGES 2048
130 static int numClipSilEdges;
131 static int clipSilEdges[MAX_CLIP_SIL_EDGES][2];
133 // facing will be 0 if forward facing, 1 if backwards facing
134 // grabbed with alloca
135 static byte *globalFacing;
137 // faceCastsShadow will be 1 if the face is in the projection
138 // and facing the apropriate direction
139 static byte *faceCastsShadow;
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;
151 idPlane pointLightFrustums[6][6] = {
163 idPlane( -1,-1,0,0 ),
165 idPlane( -1,0,-1,0 ),
180 idPlane( 0,-1,-1,0 ),
182 idPlane( -1,-1,0,0 ),
197 idPlane( -1,0,-1,0 ),
199 idPlane( 0,-1,-1,0 ),
206 static bool callOptimizer; // call the preprocessor optimizer after clipping occluders
214 static indexRef_t indexRef[6];
215 static int indexFrustumNumber; // which shadow generating side of a light the indexRef is for
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.
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.
233 static bool PointsOrdered( const idVec3 &a, const idVec3 &b ) {
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
240 // scale by some odd numbers so -8, 8, 8 will not be equal
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;
248 return (bool)(i < j);
253 R_LightProjectionMatrix
257 void R_LightProjectionMatrix( const idVec3 &origin, const idPlane &rearPlane, idVec4 mat[4] ) {
261 // calculate the homogenious light vector
267 lg = rearPlane.ToVec4() * lv;
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];
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];
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];
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];
293 R_ProjectPointsToFarPlane
295 make a projected copy of the even verts into the odd spots
296 that is on the far light clip plane
299 static void R_ProjectPointsToFarPlane( const idRenderEntityLocal *ent, const idRenderLightLocal *light,
300 const idPlane &lightPlaneLocal,
301 int firstShadowVert, int numShadowVerts ) {
307 R_GlobalPointToLocal( ent->modelMatrix, light->globalLightOrigin, lv );
308 R_LightProjectionMatrix( lv, lightPlaneLocal, mat );
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 ) {
318 w = in->ToVec3() * mat[3].ToVec3() + mat[3][3];
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;
332 // messing with W seems to cause some depth precision problems
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 ) {
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];
348 #define MAX_CLIPPED_POINTS 20
351 idVec3 verts[MAX_CLIPPED_POINTS];
352 int edgeFlags[MAX_CLIPPED_POINTS];
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
363 I have some worries about edge flag cases when polygons are clipped
364 multiple times near the epsilon.
367 static int R_ChopWinding( clipTri_t clipTris[2], int inNum, const idPlane &plane ) {
369 float dists[MAX_CLIPPED_POINTS];
370 int sides[MAX_CLIPPED_POINTS];
377 in = &clipTris[inNum];
378 out = &clipTris[inNum^1];
379 counts[0] = counts[1] = counts[2] = 0;
381 // determine sides for each point
382 for ( i = 0 ; i < in->numVerts ; i++ ) {
383 dot = plane.Distance( in->verts[i] );
385 if ( dot < -LIGHT_CLIP_EPSILON ) {
386 sides[i] = SIDE_BACK;
387 } else if ( dot > LIGHT_CLIP_EPSILON ) {
388 sides[i] = SIDE_FRONT;
395 // if none in front, it is completely clipped away
396 if ( !counts[SIDE_FRONT] ) {
400 if ( !counts[SIDE_BACK] ) {
401 return inNum; // inout stays the same
404 // avoid wrapping checks by duplicating first value to end
407 in->verts[in->numVerts] = in->verts[0];
408 in->edgeFlags[in->numVerts] = in->edgeFlags[0];
411 for ( i = 0 ; i < in->numVerts ; i++ ) {
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;
419 out->edgeFlags[out->numVerts] = in->edgeFlags[i];
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];
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]);
434 out->verts[out->numVerts] = mid;
437 if ( sides[i+1] != SIDE_FRONT ) {
438 out->edgeFlags[out->numVerts] = 1;
440 out->edgeFlags[out->numVerts] = in->edgeFlags[i];
452 R_ClipTriangleToLight
454 Returns false if nothing is left after clipping
457 static bool R_ClipTriangleToLight( const idVec3 &a, const idVec3 &b, const idVec3 &c, int planeBits,
458 const idPlane frustum[6] ) {
461 clipTri_t pingPong[2], *ct;
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;
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 ) {
483 // copy the clipped points out to shadowVerts
484 if ( numShadowVerts + ct->numVerts * 2 > MAX_SHADOW_VERTS ) {
489 base = numShadowVerts;
490 for ( i = 0 ; i < ct->numVerts ; i++ ) {
491 shadowVerts[ base + i*2 ].ToVec3() = ct->verts[i];
493 numShadowVerts += ct->numVerts * 2;
495 if ( numShadowIndexes + 3 * ( ct->numVerts - 2 ) > MAX_SHADOW_INDEXES ) {
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;
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 ) {
514 clipSilEdges[ numClipSilEdges ][0] = base + i * 2;
515 if ( i == ct->numVerts - 1 ) {
516 clipSilEdges[ numClipSilEdges ][1] = base;
518 clipSilEdges[ numClipSilEdges ][1] = base + ( i + 1 ) * 2;
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.
535 If one point is clearly clipped by the plane and the
536 other point is on the plane, it will be completely removed.
539 static bool R_ClipLineToLight( const idVec3 &a, const idVec3 &b, const idPlane frustum[4],
540 idVec3 &p1, idVec3 &p2 ) {
550 for ( j = 0 ; j < 6 ; j++ ) {
551 d1 = frustum[j].Distance( p1 );
552 d2 = frustum[j].Distance( p2 );
554 // if both on or in front, not clipped to this plane
555 if ( d1 > -LIGHT_CLIP_EPSILON && d2 > -LIGHT_CLIP_EPSILON ) {
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 ) {
563 if ( d2 <= -LIGHT_CLIP_EPSILON && d1 < LIGHT_CLIP_EPSILON ) {
567 // clip it, keeping the negative side
569 clip = p1.ToFloatPtr();
571 clip = p2.ToFloatPtr();
575 if ( idMath::Fabs(d1 - d2) < 0.001 ) {
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] );
586 return true; // retain a fragment
594 Add sil edges for each triangle clipped to the side of
597 Only done for simple projected lights, not point lights.
600 static void R_AddClipSilEdges( void ) {
602 int v1_back, v2_back;
605 // don't allow it to overflow
606 if ( numShadowIndexes + numClipSilEdges * 6 > MAX_SHADOW_INDEXES ) {
611 for ( i = 0 ; i < numClipSilEdges ; i++ ) {
612 v1 = clipSilEdges[i][0];
613 v2 = clipSilEdges[i][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;
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;
638 Add quads from the front points to the projected points
639 for each silhouette edge in the light
642 static void R_AddSilEdges( const srfTriangles_t *tri, unsigned short *pointCull, const idPlane frustum[6] ) {
648 numPlanes = tri->numIndexes / 3;
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" );
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 ] ) ) {
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 ) ) {
675 // see if the edge needs to be clipped
676 if ( EDGE_CLIPPED( sil->v1, sil->v2 ) ) {
677 if ( numShadowVerts + 4 > MAX_SHADOW_VERTS ) {
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
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[]" );
699 if ( numShadowIndexes + 6 > MAX_SHADOW_INDEXES ) {
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;
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;
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;
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;
748 Also inits the remap[] array to all -1
751 static void R_CalcPointCull( const srfTriangles_t *tri, const idPlane frustum[6], unsigned short *pointCull ) {
757 SIMDProcessor->Memset( remap, -1, tri->numVerts * sizeof( remap[0] ) );
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);
766 // initialize point cull
767 for ( i = 0; i < tri->numVerts; i++ ) {
768 pointCull[i] = frontBits;
771 // if the surface is not completely inside the light frustum
772 if ( frontBits == ( ( ( 1 << 6 ) - 1 ) ) << 6 ) {
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 ) );
782 for ( i = 0; i < 6; i++ ) {
784 if ( frontBits & (1<<(i+6)) ) {
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 );
792 for ( i = 0; i < tri->numVerts; i++ ) {
793 pointCull[i] |= side1[i] | (side2[i] << 6);
799 R_CreateShadowVolumeInFrustum
801 Adds new verts and indexes to the shadow volume.
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.
807 If the frustum is just part of a point light, clipped planes don't
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 ) {
820 unsigned short *pointCull;
822 int firstShadowIndex;
826 pointCull = (unsigned short *)_alloca16( tri->numVerts * sizeof( pointCull[0] ) );
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 );
832 // this may not be the first frustum added to the volume
833 firstShadowIndex = numShadowIndexes;
834 firstShadowVert = numShadowVerts;
836 // decide which triangles front shadow volumes, clipping as needed
838 numTris = tri->numIndexes / 3;
839 for ( i = 0 ; i < numTris ; i++ ) {
842 faceCastsShadow[i] = 0; // until shown otherwise
844 // if it isn't facing the right way, don't add it
845 // to the shadow volume
846 if ( globalFacing[i] ) {
850 i1 = tri->silIndexes[ i*3 + 0 ];
851 i2 = tri->silIndexes[ i*3 + 1 ];
852 i3 = tri->silIndexes[ i*3 + 2 ];
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 ) ) {
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 ) {
870 if ( !POINT_CULLED(i1) && remap[i1] == -1 ) {
871 remap[i1] = numShadowVerts;
872 shadowVerts[ numShadowVerts ].ToVec3() = tri->verts[i1].xyz;
875 if ( !POINT_CULLED(i2) && remap[i2] == -1 ) {
876 remap[i2] = numShadowVerts;
877 shadowVerts[ numShadowVerts ].ToVec3() = tri->verts[i2].xyz;
880 if ( !POINT_CULLED(i3) && remap[i3] == -1 ) {
881 remap[i3] = numShadowVerts;
882 shadowVerts[ numShadowVerts ].ToVec3() = tri->verts[i3].xyz;
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
891 if ( R_ClipTriangleToLight( tri->verts[i1].xyz, tri->verts[i2].xyz,
892 tri->verts[i3].xyz, cullBits, frustum ) ) {
893 faceCastsShadow[i] = 1;
896 // instead of overflowing or drawing a streamer shadow, don't draw a shadow at all
897 if ( numShadowIndexes + 3 > MAX_SHADOW_INDEXES ) {
901 if ( remap[i1] == -1 || remap[i2] == -1 || remap[i3] == -1 ) {
902 common->Error( "R_CreateShadowVolumeInFrustum: bad remap[]" );
904 shadowIndexes[numShadowIndexes++] = remap[i3];
905 shadowIndexes[numShadowIndexes++] = remap[i2];
906 shadowIndexes[numShadowIndexes++] = remap[i1];
907 faceCastsShadow[i] = 1;
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;
915 // if no faces have been defined for the shadow volume,
916 // there won't be anything at all
917 if ( numCapIndexes == 0 ) {
921 //--------------- off-line processing ------------------
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;
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 );
932 opt = SuperOptimizeOccluders( shadowVerts, shadowIndexes + firstShadowIndex, numCapIndexes, farPlane, lightOrigin );
934 // pull off the non-optimized data
935 numShadowIndexes = firstShadowIndex;
936 numShadowVerts = firstShadowVert;
938 // add the optimized data
939 if ( numShadowIndexes + opt.totalIndexes > MAX_SHADOW_INDEXES
940 || numShadowVerts + opt.numVerts > MAX_SHADOW_VERTS ) {
942 common->Printf( "WARNING: overflowed MAX_SHADOW tables, shadow discarded\n" );
943 Mem_Free( opt.verts );
944 Mem_Free( opt.indexes );
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;
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" );
959 shadowIndexes[numShadowIndexes+i] = index + numShadowVerts;
962 numShadowVerts += opt.numVerts;
963 numShadowIndexes += opt.totalIndexes;
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++;
972 Mem_Free( opt.verts );
973 Mem_Free( opt.indexes );
977 //--------------- real-time processing ------------------
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;
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 ) {
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;
995 numShadowIndexes += numCapIndexes;
997 c_caps += numCapIndexes * 2;
999 int preSilIndexes = numShadowIndexes;
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();
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 );
1011 c_sils += numShadowIndexes - preSilIndexes;
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 );
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++;
1027 R_MakeShadowFrustums
1029 Called at definition derivation time
1032 void R_MakeShadowFrustums( idRenderLightLocal *light ) {
1035 if ( light->parms.pointLight ) {
1037 idVec3 adjustedRadius;
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] );
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 ];
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];
1059 plane[3] = -( plane.Normal() * light->globalLightOrigin );
1061 plane[3] += adjustedRadius[i>>1];
1065 light->numShadowFrustums++;
1068 // exact projection,taking into account asymetric frustums when
1069 // globalLightOrigin isn't centered
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
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
1088 bool centerOutside = false;
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;
1101 for ( i = 0 ; i < 8 ; i++ ) {
1103 for ( j = 0 ; j < 3 ; j++ ) {
1104 if ( i & ( 1 << j ) ) {
1105 temp[j] = light->parms.lightRadius[j];
1107 temp[j] = -light->parms.lightRadius[j];
1111 // transform to global space
1112 corners[i] = light->parms.origin + light->parms.axis * temp;
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]];
1123 // plane will have positive side inward
1124 backPlane.FromPoints( p1, p2, p3 );
1126 // if center of projection is on the wrong side, skip
1127 float d = backPlane.Distance( light->globalLightOrigin );
1132 frust->numPlanes = 6;
1133 frust->planes[5] = backPlane;
1134 frust->planes[4] = backPlane; // we don't really need the extra plane
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]];
1141 // create a plane that goes through the center of projection
1142 frust->planes[edge].FromPoints( p2, p1, light->globalLightOrigin );
1144 // see if we should use an adjacent plane instead
1145 if ( centerOutside ) {
1146 idVec3 &p3 = corners[faceEdgeAdjacent[side][edge]];
1149 sidePlane.FromPoints( p2, p1, p3 );
1150 d = sidePlane.Distance( light->globalLightOrigin );
1152 // use this plane instead of the edged plane
1153 frust->planes[edge] = sidePlane;
1155 // we can't guarantee a neighbor, so add sill planes at edge
1156 light->shadowFrustums[ light->numShadowFrustums ].makeClippedPlanes = true;
1159 light->numShadowFrustums++;
1168 light->numShadowFrustums = 1;
1169 shadowFrustum_t *frust = &light->shadowFrustums[ 0 ];
1171 // flip and transform the frustum planes so the positive side faces
1172 // inward in local coordinates
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];
1180 plane.SetNormal( -light->frustum[i].Normal() );
1181 plane.SetDist( -light->frustum[i].Dist() );
1184 frust->numPlanes = 6;
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
1193 R_CreateShadowVolume
1195 The returned surface will have a valid bounds and radius for culling.
1197 Triangles are clipped to the light frustum before projecting.
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
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.
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.
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.
1217 srfTriangles_t *R_CreateShadowVolume( const idRenderEntityLocal *ent,
1218 const srfTriangles_t *tri, const idRenderLightLocal *light,
1219 shadowGen_t optimize, srfCullInfo_t &cullInfo ) {
1222 srfTriangles_t *newTri;
1225 if ( !r_shadows.GetBool() ) {
1229 if ( tri->numSilEdges == 0 || tri->numIndexes == 0 || tri->numVerts == 0 ) {
1233 if ( tri->numIndexes < 0 ) {
1234 common->Error( "R_CreateShadowVolume: tri->numIndexes = %i", tri->numIndexes );
1237 if ( tri->numVerts < 0 ) {
1238 common->Error( "R_CreateShadowVolume: tri->numVerts = %i", tri->numVerts );
1241 tr.pc.c_createShadowVolumes++;
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() ) {
1247 if ( tr.backEndRendererHasVertexPrograms && r_useShadowVertexProgram.GetBool() ) {
1248 return R_CreateVertexProgramTurboShadowVolume( ent, tri, light, cullInfo );
1250 return R_CreateTurboShadowVolume( ent, tri, light, cullInfo );
1254 R_CalcInteractionFacing( ent, tri, light, cullInfo );
1256 int numFaces = tri->numIndexes / 3;
1258 for ( i = 0; i < numFaces && allFront; i++ ) {
1259 allFront &= cullInfo.facing[i];
1262 // if no faces are the right direction, don't make a shadow at all
1266 // clear the shadow volume
1267 numShadowIndexes = 0;
1270 indexFrustumNumber = 0;
1272 callOptimizer = (optimize == SG_OFFLINE);
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] ) );
1280 R_GlobalPointToLocal( ent->modelMatrix, light->globalLightOrigin, lightOrigin );
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] );
1289 // transform the planes into entity space
1290 // we could share and reverse some of the planes between frustums for a minor
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
1296 for ( j = 0 ; j < frust->numPlanes ; j++ ) {
1297 R_GlobalPlaneToLocal( ent->modelMatrix, frust->planes[j], frustum[j] );
1299 // try to cull the entire surface against this frustum
1300 float d = tri->bounds.PlaneDistance( frustum[j] );
1301 if ( d < -LIGHT_CLIP_EPSILON ) {
1305 if ( j != frust->numPlanes ) {
1308 // we need to check all the triangles
1309 int oldFrustumNumber = indexFrustumNumber;
1311 R_CreateShadowVolumeInFrustum( ent, tri, light, lightOrigin, frustum, frustum[5], frust->makeClippedPlanes );
1313 // if we couldn't make a complete shadow volume, it is better to
1314 // not draw one at all, avoiding streamer problems
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;
1327 // if no faces have been defined for the shadow volume,
1328 // there won't be anything at all
1329 if ( numShadowIndexes == 0 ) {
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" );
1339 // allocate a new surface for the shadow volume
1340 newTri = R_AllocStaticTriSurf();
1342 // we might consider setting this, but it would only help for
1343 // large lights that are partially off screen
1344 newTri->bounds.Clear();
1346 // copy off the verts and indexes
1347 newTri->numVerts = numShadowVerts;
1348 newTri->numIndexes = numShadowIndexes;
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] ) );
1355 R_AllocStaticTriSurfIndexes( newTri, newTri->numIndexes );
1357 if ( 1 /* sortCapIndexes */ ) {
1358 newTri->shadowCapPlaneBits = capPlaneBits;
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;
1364 SIMDProcessor->Memcpy( newTri->indexes+newTri->numShadowIndexesNoCaps,
1365 shadowIndexes+indexRef[i].silStart, c * sizeof( newTri->indexes[0] ) );
1366 newTri->numShadowIndexesNoCaps += c;
1368 // copy rear cap indexes next
1369 newTri->numShadowIndexesNoFrontCaps = newTri->numShadowIndexesNoCaps;
1370 for ( i = 0 ; i < indexFrustumNumber ; i++ ) {
1371 int c = indexRef[i].silStart - indexRef[i].rearCapStart;
1372 SIMDProcessor->Memcpy( newTri->indexes+newTri->numShadowIndexesNoFrontCaps,
1373 shadowIndexes+indexRef[i].rearCapStart, c * sizeof( newTri->indexes[0] ) );
1374 newTri->numShadowIndexesNoFrontCaps += c;
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;
1386 newTri->shadowCapPlaneBits = 63; // we don't have optimized index lists
1387 SIMDProcessor->Memcpy( newTri->indexes, shadowIndexes, newTri->numIndexes * sizeof( newTri->indexes[0] ) );
1390 if ( optimize == SG_OFFLINE ) {
1391 CleanupOptimizedShadowTris( newTri );