neo/renderer/tr_stencilshadow.cpp

   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
 151 idPlane pointLightFrustums[6][6] = {
 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
 204 int     c_caps, c_sils;
 205
 206 static bool     callOptimizer;                  // call the preprocessor optimizer after clipping occluders
 207
 208 typedef struct {
 209         int             frontCapStart;
 210         int             rearCapStart;
 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
 307         R_GlobalPointToLocal( ent->modelMatrix, light->globalLightOrigin, lv );
 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 */
1032 void R_MakeShadowFrustums( idRenderLightLocal *light ) {
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 */
1217 srfTriangles_t *R_CreateShadowVolume( const idRenderEntityLocal *ent,
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
1241         tr.pc.c_createShadowVolumes++;
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() ) {
1247                 if ( tr.backEndRendererHasVertexPrograms && r_useShadowVertexProgram.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;
1364                         SIMDProcessor->Memcpy( newTri->indexes+newTri->numShadowIndexesNoCaps,
1365                                                                         shadowIndexes+indexRef[i].silStart, c * sizeof( newTri->indexes[0] ) );
1366                         newTri->numShadowIndexesNoCaps += c;
1367                 }
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;
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 }