tools/quake3/q3map2/light_ydnar.c

   1 /* -------------------------------------------------------------------------------
   2
   3 Copyright (C) 1999-2007 id Software, Inc. and contributors.
   4 For a list of contributors, see the accompanying CONTRIBUTORS file.
   5
   6 This file is part of GtkRadiant.
   7
   8 GtkRadiant is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 2 of the License, or
  11 (at your option) any later version.
  12
  13 GtkRadiant is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GtkRadiant; if not, write to the Free Software
  20 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  21
  22 ----------------------------------------------------------------------------------
  23
  24 This code has been altered significantly from its original form, to support
  25 several games based on the Quake III Arena engine, in the form of "Q3Map2."
  26
  27 ------------------------------------------------------------------------------- */
  28
  29
  30
  31 /* marker */
  32 #define LIGHT_YDNAR_C
  33
  34
  35
  36 /* dependencies */
  37 #include "q3map2.h"
  38
  39
  40
  41
  42 /*
  43 ColorToBytes()
  44 ydnar: moved to here 2001-02-04
  45 */
  46
  47 void ColorToBytes( const float *color, byte *colorBytes, float scale )
  48 {
  49         int             i;
  50         float   max, gamma;
  51         vec3_t  sample;
  52
  53
  54         /* ydnar: scaling necessary for simulating r_overbrightBits on external lightmaps */
  55         if( scale <= 0.0f )
  56                 scale = 1.0f;
  57
  58         /* make a local copy */
  59         VectorScale( color, scale, sample );
  60
  61         /* muck with it */
  62         gamma = 1.0f / lightmapGamma;
  63         for( i = 0; i < 3; i++ )
  64         {
  65                 /* handle negative light */
  66                 if( sample[ i ] < 0.0f )
  67                 {
  68                         sample[ i ] = 0.0f;
  69                         continue;
  70                 }
  71
  72                 /* gamma */
  73                 sample[ i ] = pow( sample[ i ] / 255.0f, gamma ) * 255.0f;
  74         }
  75
  76         /* clamp with color normalization */
  77         max = sample[ 0 ];
  78         if( sample[ 1 ] > max )
  79                 max = sample[ 1 ];
  80         if( sample[ 2 ] > max )
  81                 max = sample[ 2 ];
  82         if( max > 255.0f )
  83                 VectorScale( sample, (255.0f / max), sample );
  84
  85         /* compensate for ingame overbrighting/bitshifting */
  86         VectorScale( sample, (1.0f / lightmapCompensate), sample );
  87
  88         /* store it off */
  89         colorBytes[ 0 ] = sample[ 0 ];
  90         colorBytes[ 1 ] = sample[ 1 ];
  91         colorBytes[ 2 ] = sample[ 2 ];
  92 }
  93
  94
  95
  96 /* -------------------------------------------------------------------------------
  97
  98 this section deals with phong shading (normal interpolation across brush faces)
  99
 100 ------------------------------------------------------------------------------- */
 101
 102 /*
 103 SmoothNormals()
 104 smooths together coincident vertex normals across the bsp
 105 */
 106
 107 #define MAX_SAMPLES                             256
 108 #define THETA_EPSILON                   0.000001
 109 #define EQUAL_NORMAL_EPSILON    0.01
 110
 111 void SmoothNormals( void )
 112 {
 113         int                                     i, j, k, f, cs, numVerts, numVotes, fOld, start;
 114         float                           shadeAngle, defaultShadeAngle, maxShadeAngle, dot, testAngle;
 115         bspDrawSurface_t        *ds;
 116         shaderInfo_t            *si;
 117         float                           *shadeAngles;
 118         byte                            *smoothed;
 119         vec3_t                          average, diff;
 120         int                                     indexes[ MAX_SAMPLES ];
 121         vec3_t                          votes[ MAX_SAMPLES ];
 122
 123
 124         /* allocate shade angle table */
 125         shadeAngles = safe_malloc( numBSPDrawVerts * sizeof( float ) );
 126         memset( shadeAngles, 0, numBSPDrawVerts * sizeof( float ) );
 127
 128         /* allocate smoothed table */
 129         cs = (numBSPDrawVerts / 8) + 1;
 130         smoothed = safe_malloc( cs );
 131         memset( smoothed, 0, cs );
 132
 133         /* set default shade angle */
 134         defaultShadeAngle = DEG2RAD( shadeAngleDegrees );
 135         maxShadeAngle = 0;
 136
 137         /* run through every surface and flag verts belonging to non-lightmapped surfaces
 138            and set per-vertex smoothing angle */
 139         for( i = 0; i < numBSPDrawSurfaces; i++ )
 140         {
 141                 /* get drawsurf */
 142                 ds = &bspDrawSurfaces[ i ];
 143
 144                 /* get shader for shade angle */
 145                 si = surfaceInfos[ i ].si;
 146                 if( si->shadeAngleDegrees )
 147                         shadeAngle = DEG2RAD( si->shadeAngleDegrees );
 148                 else
 149                         shadeAngle = defaultShadeAngle;
 150                 if( shadeAngle > maxShadeAngle )
 151                         maxShadeAngle = shadeAngle;
 152
 153                 /* flag its verts */
 154                 for( j = 0; j < ds->numVerts; j++ )
 155                 {
 156                         f = ds->firstVert + j;
 157                         shadeAngles[ f ] = shadeAngle;
 158                         if( ds->surfaceType == MST_TRIANGLE_SOUP )
 159                                 smoothed[ f >> 3 ] |= (1 << (f & 7));
 160                 }
 161
 162                 /* ydnar: optional force-to-trisoup */
 163                 if( trisoup && ds->surfaceType == MST_PLANAR )
 164                 {
 165                         ds->surfaceType = MST_TRIANGLE_SOUP;
 166                         ds->lightmapNum[ 0 ] = -3;
 167                 }
 168         }
 169
 170         /* bail if no surfaces have a shade angle */
 171         if( maxShadeAngle == 0 )
 172         {
 173                 free( shadeAngles );
 174                 free( smoothed );
 175                 return;
 176         }
 177
 178         /* init pacifier */
 179         fOld = -1;
 180         start = I_FloatTime();
 181
 182         /* go through the list of vertexes */
 183         for( i = 0; i < numBSPDrawVerts; i++ )
 184         {
 185                 /* print pacifier */
 186                 f = 10 * i / numBSPDrawVerts;
 187                 if( f != fOld )
 188                 {
 189                         fOld = f;
 190                         Sys_Printf( "%i...", f );
 191                 }
 192
 193                 /* already smoothed? */
 194                 if( smoothed[ i >> 3 ] & (1 << (i & 7)) )
 195                         continue;
 196
 197                 /* clear */
 198                 VectorClear( average );
 199                 numVerts = 0;
 200                 numVotes = 0;
 201
 202                 /* build a table of coincident vertexes */
 203                 for( j = i; j < numBSPDrawVerts && numVerts < MAX_SAMPLES; j++ )
 204                 {
 205                         /* already smoothed? */
 206                         if( smoothed[ j >> 3 ] & (1 << (j & 7)) )
 207                                 continue;
 208
 209                         /* test vertexes */
 210                         if( VectorCompare( yDrawVerts[ i ].xyz, yDrawVerts[ j ].xyz ) == qfalse )
 211                                 continue;
 212
 213                         /* use smallest shade angle */
 214                         shadeAngle = (shadeAngles[ i ] < shadeAngles[ j ] ? shadeAngles[ i ] : shadeAngles[ j ]);
 215
 216                         /* check shade angle */
 217                         dot = DotProduct( bspDrawVerts[ i ].normal, bspDrawVerts[ j ].normal );
 218                         if( dot > 1.0 )
 219                                 dot = 1.0;
 220                         else if( dot < -1.0 )
 221                                 dot = -1.0;
 222                         testAngle = acos( dot ) + THETA_EPSILON;
 223                         if( testAngle >= shadeAngle )
 224                         {
 225                                 //Sys_Printf( "F(%3.3f >= %3.3f) ", RAD2DEG( testAngle ), RAD2DEG( shadeAngle ) );
 226                                 continue;
 227                         }
 228                         //Sys_Printf( "P(%3.3f < %3.3f) ", RAD2DEG( testAngle ), RAD2DEG( shadeAngle ) );
 229
 230                         /* add to the list */
 231                         indexes[ numVerts++ ] = j;
 232
 233                         /* flag vertex */
 234                         smoothed[ j >> 3 ] |= (1 << (j & 7));
 235
 236                         /* see if this normal has already been voted */
 237                         for( k = 0; k < numVotes; k++ )
 238                         {
 239                                 VectorSubtract( bspDrawVerts[ j ].normal, votes[ k ], diff );
 240                                 if( fabs( diff[ 0 ] ) < EQUAL_NORMAL_EPSILON &&
 241                                         fabs( diff[ 1 ] ) < EQUAL_NORMAL_EPSILON &&
 242                                         fabs( diff[ 2 ] ) < EQUAL_NORMAL_EPSILON )
 243                                         break;
 244                         }
 245
 246                         /* add a new vote? */
 247                         if( k == numVotes && numVotes < MAX_SAMPLES )
 248                         {
 249                                 VectorAdd( average, bspDrawVerts[ j ].normal, average );
 250                                 VectorCopy( bspDrawVerts[ j ].normal, votes[ numVotes ] );
 251                                 numVotes++;
 252                         }
 253                 }
 254
 255                 /* don't average for less than 2 verts */
 256                 if( numVerts < 2 )
 257                         continue;
 258
 259                 /* average normal */
 260                 if( VectorNormalize( average, average ) > 0 )
 261                 {
 262                         /* smooth */
 263                         for( j = 0; j < numVerts; j++ )
 264                                 VectorCopy( average, yDrawVerts[ indexes[ j ] ].normal );
 265                 }
 266         }
 267
 268         /* free the tables */
 269         free( shadeAngles );
 270         free( smoothed );
 271
 272         /* print time */
 273         Sys_Printf( " (%i)\n", (int) (I_FloatTime() - start) );
 274 }
 275
 276
 277
 278 /* -------------------------------------------------------------------------------
 279
 280 this section deals with phong shaded lightmap tracing
 281
 282 ------------------------------------------------------------------------------- */
 283
 284 /* 9th rewrite (recursive subdivision of a lightmap triangle) */
 285
 286 /*
 287 CalcTangentVectors()
 288 calculates the st tangent vectors for normalmapping
 289 */
 290
 291 static qboolean CalcTangentVectors( int numVerts, bspDrawVert_t **dv, vec3_t *stv, vec3_t *ttv )
 292 {
 293         int                     i;
 294         float           bb, s, t;
 295         vec3_t          bary;
 296
 297
 298         /* calculate barycentric basis for the triangle */
 299         bb = (dv[ 1 ]->st[ 0 ] - dv[ 0 ]->st[ 0 ]) * (dv[ 2 ]->st[ 1 ] - dv[ 0 ]->st[ 1 ]) - (dv[ 2 ]->st[ 0 ] - dv[ 0 ]->st[ 0 ]) * (dv[ 1 ]->st[ 1 ] - dv[ 0 ]->st[ 1 ]);
 300         if( fabs( bb ) < 0.00000001f )
 301                 return qfalse;
 302
 303         /* do each vertex */
 304         for( i = 0; i < numVerts; i++ )
 305         {
 306                 /* calculate s tangent vector */
 307                 s = dv[ i ]->st[ 0 ] + 10.0f;
 308                 t = dv[ i ]->st[ 1 ];
 309                 bary[ 0 ] = ((dv[ 1 ]->st[ 0 ] - s) * (dv[ 2 ]->st[ 1 ] - t) - (dv[ 2 ]->st[ 0 ] - s) * (dv[ 1 ]->st[ 1 ] - t)) / bb;
 310                 bary[ 1 ] = ((dv[ 2 ]->st[ 0 ] - s) * (dv[ 0 ]->st[ 1 ] - t) - (dv[ 0 ]->st[ 0 ] - s) * (dv[ 2 ]->st[ 1 ] - t)) / bb;
 311                 bary[ 2 ] = ((dv[ 0 ]->st[ 0 ] - s) * (dv[ 1 ]->st[ 1 ] - t) - (dv[ 1 ]->st[ 0 ] - s) * (dv[ 0 ]->st[ 1 ] - t)) / bb;
 312
 313                 stv[ i ][ 0 ] = bary[ 0 ] * dv[ 0 ]->xyz[ 0 ] + bary[ 1 ] * dv[ 1 ]->xyz[ 0 ] + bary[ 2 ] * dv[ 2 ]->xyz[ 0 ];
 314                 stv[ i ][ 1 ] = bary[ 0 ] * dv[ 0 ]->xyz[ 1 ] + bary[ 1 ] * dv[ 1 ]->xyz[ 1 ] + bary[ 2 ] * dv[ 2 ]->xyz[ 1 ];
 315                 stv[ i ][ 2 ] = bary[ 0 ] * dv[ 0 ]->xyz[ 2 ] + bary[ 1 ] * dv[ 1 ]->xyz[ 2 ] + bary[ 2 ] * dv[ 2 ]->xyz[ 2 ];
 316
 317                 VectorSubtract( stv[ i ], dv[ i ]->xyz, stv[ i ] );
 318                 VectorNormalize( stv[ i ], stv[ i ] );
 319
 320                 /* calculate t tangent vector */
 321                 s = dv[ i ]->st[ 0 ];
 322                 t = dv[ i ]->st[ 1 ] + 10.0f;
 323                 bary[ 0 ] = ((dv[ 1 ]->st[ 0 ] - s) * (dv[ 2 ]->st[ 1 ] - t) - (dv[ 2 ]->st[ 0 ] - s) * (dv[ 1 ]->st[ 1 ] - t)) / bb;
 324                 bary[ 1 ] = ((dv[ 2 ]->st[ 0 ] - s) * (dv[ 0 ]->st[ 1 ] - t) - (dv[ 0 ]->st[ 0 ] - s) * (dv[ 2 ]->st[ 1 ] - t)) / bb;
 325                 bary[ 2 ] = ((dv[ 0 ]->st[ 0 ] - s) * (dv[ 1 ]->st[ 1 ] - t) - (dv[ 1 ]->st[ 0 ] - s) * (dv[ 0 ]->st[ 1 ] - t)) / bb;
 326
 327                 ttv[ i ][ 0 ] = bary[ 0 ] * dv[ 0 ]->xyz[ 0 ] + bary[ 1 ] * dv[ 1 ]->xyz[ 0 ] + bary[ 2 ] * dv[ 2 ]->xyz[ 0 ];
 328                 ttv[ i ][ 1 ] = bary[ 0 ] * dv[ 0 ]->xyz[ 1 ] + bary[ 1 ] * dv[ 1 ]->xyz[ 1 ] + bary[ 2 ] * dv[ 2 ]->xyz[ 1 ];
 329                 ttv[ i ][ 2 ] = bary[ 0 ] * dv[ 0 ]->xyz[ 2 ] + bary[ 1 ] * dv[ 1 ]->xyz[ 2 ] + bary[ 2 ] * dv[ 2 ]->xyz[ 2 ];
 330
 331                 VectorSubtract( ttv[ i ], dv[ i ]->xyz, ttv[ i ] );
 332                 VectorNormalize( ttv[ i ], ttv[ i ] );
 333
 334                 /* debug code */
 335                 //%     Sys_FPrintf( SYS_VRB, "%d S: (%f %f %f) T: (%f %f %f)\n", i,
 336                 //%             stv[ i ][ 0 ], stv[ i ][ 1 ], stv[ i ][ 2 ], ttv[ i ][ 0 ], ttv[ i ][ 1 ], ttv[ i ][ 2 ] );
 337         }
 338
 339         /* return to caller */
 340         return qtrue;
 341 }
 342
 343
 344
 345
 346 /*
 347 PerturbNormal()
 348 perterbs the normal by the shader's normalmap in tangent space
 349 */
 350
 351 static void PerturbNormal( bspDrawVert_t *dv, shaderInfo_t *si, vec3_t pNormal, vec3_t stv[ 3 ], vec3_t ttv[ 3 ] )
 352 {
 353         int                     i;
 354         vec4_t          bump;
 355
 356
 357         /* passthrough */
 358         VectorCopy( dv->normal, pNormal );
 359
 360         /* sample normalmap */
 361         if( RadSampleImage( si->normalImage->pixels, si->normalImage->width, si->normalImage->height, dv->st, bump ) == qfalse )
 362                 return;
 363
 364         /* remap sampled normal from [0,255] to [-1,-1] */
 365         for( i = 0; i < 3; i++ )
 366                 bump[ i ] = (bump[ i ] - 127.0f) * (1.0f / 127.5f);
 367
 368         /* scale tangent vectors and add to original normal */
 369         VectorMA( dv->normal, bump[ 0 ], stv[ 0 ], pNormal );
 370         VectorMA( pNormal, bump[ 1 ], ttv[ 0 ], pNormal );
 371         VectorMA( pNormal, bump[ 2 ], dv->normal, pNormal );
 372
 373         /* renormalize and return */
 374         VectorNormalize( pNormal, pNormal );
 375 }
 376
 377
 378
 379 /*
 380 MapSingleLuxel()
 381 maps a luxel for triangle bv at
 382 */
 383
 384 #define NUDGE                   0.5f
 385 #define BOGUS_NUDGE             -99999.0f
 386
 387 static int MapSingleLuxel( rawLightmap_t *lm, surfaceInfo_t *info, bspDrawVert_t *dv, vec4_t plane, float pass, vec3_t stv[ 3 ], vec3_t ttv[ 3 ] )
 388 {
 389         int                             i, x, y, numClusters, *clusters, pointCluster, *cluster;
 390         float                   *luxel, *origin, *normal, d, lightmapSampleOffset;
 391         shaderInfo_t    *si;
 392         vec3_t                  pNormal;
 393         vec3_t                  vecs[ 3 ];
 394         vec3_t                  nudged;
 395         float                   *nudge;
 396         static float    nudges[][ 2 ] =
 397                                         {
 398                                                 //%{ 0, 0 },            /* try center first */
 399                                                 { -NUDGE, 0 },          /* left */
 400                                                 { NUDGE, 0 },           /* right */
 401                                                 { 0, NUDGE },           /* up */
 402                                                 { 0, -NUDGE },          /* down */
 403                                                 { -NUDGE, NUDGE },      /* left/up */
 404                                                 { NUDGE, -NUDGE },      /* right/down */
 405                                                 { NUDGE, NUDGE },       /* right/up */
 406                                                 { -NUDGE, -NUDGE },     /* left/down */
 407                                                 { BOGUS_NUDGE, BOGUS_NUDGE }
 408                                         };
 409
 410
 411         /* find luxel xy coords (fixme: subtract 0.5?) */
 412         x = dv->lightmap[ 0 ][ 0 ];
 413         y = dv->lightmap[ 0 ][ 1 ];
 414         if( x < 0 )
 415                 x = 0;
 416         else if( x >= lm->sw )
 417                 x = lm->sw - 1;
 418         if( y < 0 )
 419                 y = 0;
 420         else if( y >= lm->sh )
 421                 y = lm->sh - 1;
 422
 423         /* set shader and cluster list */
 424         if( info != NULL )
 425         {
 426                 si = info->si;
 427                 numClusters = info->numSurfaceClusters;
 428                 clusters = &surfaceClusters[ info->firstSurfaceCluster ];
 429         }
 430         else
 431         {
 432                 si = NULL;
 433                 numClusters = 0;
 434                 clusters = NULL;
 435         }
 436
 437         /* get luxel, origin, cluster, and normal */
 438         luxel = SUPER_LUXEL( 0, x, y );
 439         origin = SUPER_ORIGIN( x, y );
 440         normal = SUPER_NORMAL( x, y );
 441         cluster = SUPER_CLUSTER( x, y );
 442
 443         /* don't attempt to remap occluded luxels for planar surfaces */
 444         if( (*cluster) == CLUSTER_OCCLUDED && lm->plane != NULL )
 445                 return (*cluster);
 446
 447         /* only average the normal for premapped luxels */
 448         else if( (*cluster) >= 0 )
 449         {
 450                 /* do bumpmap calculations */
 451                 if( stv != NULL )
 452                         PerturbNormal( dv, si, pNormal, stv, ttv );
 453                 else
 454                         VectorCopy( dv->normal, pNormal );
 455
 456                 /* add the additional normal data */
 457                 VectorAdd( normal, pNormal, normal );
 458                 luxel[ 3 ] += 1.0f;
 459                 return (*cluster);
 460         }
 461
 462         /* otherwise, unmapped luxels (*cluster == CLUSTER_UNMAPPED) will have their full attributes calculated */
 463
 464         /* get origin */
 465
 466         /* axial lightmap projection */
 467         if( lm->vecs != NULL )
 468         {
 469                 /* calculate an origin for the sample from the lightmap vectors */
 470                 VectorCopy( lm->origin, origin );
 471                 for( i = 0; i < 3; i++ )
 472                 {
 473                         /* add unless it's the axis, which is taken care of later */
 474                         if( i == lm->axisNum )
 475                                 continue;
 476                         origin[ i ] += (x * lm->vecs[ 0 ][ i ]) + (y * lm->vecs[ 1 ][ i ]);
 477                 }
 478
 479                 /* project the origin onto the plane */
 480                 d = DotProduct( origin, plane ) - plane[ 3 ];
 481                 d /= plane[ lm->axisNum ];
 482                 origin[ lm->axisNum ] -= d;
 483         }
 484
 485         /* non axial lightmap projection (explicit xyz) */
 486         else
 487                 VectorCopy( dv->xyz, origin );
 488
 489         /* planar surfaces have precalculated lightmap vectors for nudging */
 490         if( lm->plane != NULL )
 491         {
 492                 VectorCopy( lm->vecs[ 0 ], vecs[ 0 ] );
 493                 VectorCopy( lm->vecs[ 1 ], vecs[ 1 ] );
 494                 VectorCopy( lm->plane, vecs[ 2 ] );
 495         }
 496
 497         /* non-planar surfaces must calculate them */
 498         else
 499         {
 500                 if( plane != NULL )
 501                         VectorCopy( plane, vecs[ 2 ] );
 502                 else
 503                         VectorCopy( dv->normal, vecs[ 2 ] );
 504                 MakeNormalVectors( vecs[ 2 ], vecs[ 0 ], vecs[ 1 ] );
 505         }
 506
 507         /* push the origin off the surface a bit */
 508         if( si != NULL )
 509                 lightmapSampleOffset = si->lightmapSampleOffset;
 510         else
 511                 lightmapSampleOffset = DEFAULT_LIGHTMAP_SAMPLE_OFFSET;
 512         if( lm->axisNum < 0 )
 513                 VectorMA( origin, lightmapSampleOffset, vecs[ 2 ], origin );
 514         else if( vecs[ 2 ][ lm->axisNum ] < 0.0f )
 515                 origin[ lm->axisNum ] -= lightmapSampleOffset;
 516         else
 517                 origin[ lm->axisNum ] += lightmapSampleOffset;
 518
 519         /* get cluster */
 520         pointCluster = ClusterForPointExtFilter( origin, LUXEL_EPSILON, numClusters, clusters );
 521
 522         /* another retarded hack, storing nudge count in luxel[ 1 ] */
 523         luxel[ 1 ] = 0.0f;
 524
 525         /* point in solid? (except in dark mode) */
 526         if( pointCluster < 0 && dark == qfalse )
 527         {
 528                 /* nudge the the location around */
 529                 nudge = nudges[ 0 ];
 530                 while( nudge[ 0 ] > BOGUS_NUDGE && pointCluster < 0 )
 531                 {
 532                         /* nudge the vector around a bit */
 533                         for( i = 0; i < 3; i++ )
 534                         {
 535                                 /* set nudged point*/
 536                                 nudged[ i ] = origin[ i ] + (nudge[ 0 ] * vecs[ 0 ][ i ]) + (nudge[ 1 ] * vecs[ 1 ][ i ]);
 537                         }
 538                         nudge += 2;
 539
 540                         /* get pvs cluster */
 541                         pointCluster = ClusterForPointExtFilter( nudged, LUXEL_EPSILON, numClusters, clusters ); //% + 0.625 );
 542                         if( pointCluster >= 0 )
 543                                 VectorCopy( nudged, origin );
 544                         luxel[ 1 ] += 1.0f;
 545                 }
 546         }
 547
 548         /* as a last resort, if still in solid, try drawvert origin offset by normal (except in dark mode) */
 549         if( pointCluster < 0 && si != NULL && dark == qfalse )
 550         {
 551                 VectorMA( dv->xyz, lightmapSampleOffset, dv->normal, nudged );
 552                 pointCluster = ClusterForPointExtFilter( nudged, LUXEL_EPSILON, numClusters, clusters );
 553                 if( pointCluster >= 0 )
 554                         VectorCopy( nudged, origin );
 555                 luxel[ 1 ] += 1.0f;
 556         }
 557
 558         /* valid? */
 559         if( pointCluster < 0 )
 560         {
 561                 (*cluster) = CLUSTER_OCCLUDED;
 562                 VectorClear( origin );
 563                 VectorClear( normal );
 564                 numLuxelsOccluded++;
 565                 return (*cluster);
 566         }
 567
 568         /* debug code */
 569         //%     Sys_Printf( "%f %f %f\n", origin[ 0 ], origin[ 1 ], origin[ 2 ] );
 570
 571         /* do bumpmap calculations */
 572         if( stv )
 573                 PerturbNormal( dv, si, pNormal, stv, ttv );
 574         else
 575                 VectorCopy( dv->normal, pNormal );
 576
 577         /* store the cluster and normal */
 578         (*cluster) = pointCluster;
 579         VectorCopy( pNormal, normal );
 580
 581         /* store explicit mapping pass and implicit mapping pass */
 582         luxel[ 0 ] = pass;
 583         luxel[ 3 ] = 1.0f;
 584
 585         /* add to count */
 586         numLuxelsMapped++;
 587
 588         /* return ok */
 589         return (*cluster);
 590 }
 591
 592
 593
 594 /*
 595 MapTriangle_r()
 596 recursively subdivides a triangle until its edges are shorter
 597 than the distance between two luxels (thanks jc :)
 598 */
 599
 600 static void MapTriangle_r( rawLightmap_t *lm, surfaceInfo_t *info, bspDrawVert_t *dv[ 3 ], vec4_t plane, vec3_t stv[ 3 ], vec3_t ttv[ 3 ] )
 601 {
 602         bspDrawVert_t   mid, *dv2[ 3 ];
 603         int                             max;
 604
 605
 606         /* map the vertexes */
 607         #if 0
 608         MapSingleLuxel( lm, info, dv[ 0 ], plane, 1, stv, ttv );
 609         MapSingleLuxel( lm, info, dv[ 1 ], plane, 1, stv, ttv );
 610         MapSingleLuxel( lm, info, dv[ 2 ], plane, 1, stv, ttv );
 611         #endif
 612
 613         /* subdivide calc */
 614         {
 615                 int                     i;
 616                 float           *a, *b, dx, dy, dist, maxDist;
 617
 618
 619                 /* find the longest edge and split it */
 620                 max = -1;
 621                 maxDist = 0;
 622                 for( i = 0; i < 3; i++ )
 623                 {
 624                         /* get verts */
 625                         a = dv[ i ]->lightmap[ 0 ];
 626                         b = dv[ (i + 1) % 3 ]->lightmap[ 0 ];
 627
 628                         /* get dists */
 629                         dx = a[ 0 ] - b[ 0 ];
 630                         dy = a[ 1 ] - b[ 1 ];
 631                         dist = (dx * dx) + (dy * dy);   //% sqrt( (dx * dx) + (dy * dy) );
 632
 633                         /* longer? */
 634                         if( dist > maxDist )
 635                         {
 636                                 maxDist = dist;
 637                                 max = i;
 638                         }
 639                 }
 640
 641                 /* try to early out */
 642                 if( max < 0 || maxDist <= subdivideThreshold )  /* ydnar: was i < 0 instead of max < 0 (?) */
 643                         return;
 644         }
 645
 646         /* split the longest edge and map it */
 647         LerpDrawVert( dv[ max ], dv[ (max + 1) % 3 ], &mid );
 648         MapSingleLuxel( lm, info, &mid, plane, 1, stv, ttv );
 649
 650         /* push the point up a little bit to account for fp creep (fixme: revisit this) */
 651         //%     VectorMA( mid.xyz, 2.0f, mid.normal, mid.xyz );
 652
 653         /* recurse to first triangle */
 654         VectorCopy( dv, dv2 );
 655         dv2[ max ] = &mid;
 656         MapTriangle_r( lm, info, dv2, plane, stv, ttv );
 657
 658         /* recurse to second triangle */
 659         VectorCopy( dv, dv2 );
 660         dv2[ (max + 1) % 3 ] = &mid;
 661         MapTriangle_r( lm, info, dv2, plane, stv, ttv );
 662 }
 663
 664
 665
 666 /*
 667 MapTriangle()
 668 seed function for MapTriangle_r()
 669 requires a cw ordered triangle
 670 */
 671
 672 static qboolean MapTriangle( rawLightmap_t *lm, surfaceInfo_t *info, bspDrawVert_t *dv[ 3 ], qboolean mapNonAxial )
 673 {
 674         int                             i;
 675         vec4_t                  plane;
 676         vec3_t                  *stv, *ttv, stvStatic[ 3 ], ttvStatic[ 3 ];
 677
 678
 679         /* get plane if possible */
 680         if( lm->plane != NULL )
 681         {
 682                 VectorCopy( lm->plane, plane );
 683                 plane[ 3 ] = lm->plane[ 3 ];
 684         }
 685
 686         /* otherwise make one from the points */
 687         else if( PlaneFromPoints( plane, dv[ 0 ]->xyz, dv[ 1 ]->xyz, dv[ 2 ]->xyz ) == qfalse )
 688                 return qfalse;
 689
 690         /* check to see if we need to calculate texture->world tangent vectors */
 691         if( info->si->normalImage != NULL && CalcTangentVectors( 3, dv, stvStatic, ttvStatic ) )
 692         {
 693                 stv = stvStatic;
 694                 ttv = ttvStatic;
 695         }
 696         else
 697         {
 698                 stv = NULL;
 699                 ttv = NULL;
 700         }
 701
 702         /* map the vertexes */
 703         MapSingleLuxel( lm, info, dv[ 0 ], plane, 1, stv, ttv );
 704         MapSingleLuxel( lm, info, dv[ 1 ], plane, 1, stv, ttv );
 705         MapSingleLuxel( lm, info, dv[ 2 ], plane, 1, stv, ttv );
 706
 707         /* 2002-11-20: prefer axial triangle edges */
 708         if( mapNonAxial )
 709         {
 710                 /* subdivide the triangle */
 711                 MapTriangle_r( lm, info, dv, plane, stv, ttv );
 712                 return qtrue;
 713         }
 714
 715         for( i = 0; i < 3; i++ )
 716         {
 717                 float                   *a, *b;
 718                 bspDrawVert_t   *dv2[ 3 ];
 719
 720
 721                 /* get verts */
 722                 a = dv[ i ]->lightmap[ 0 ];
 723                 b = dv[ (i + 1) % 3 ]->lightmap[ 0 ];
 724
 725                 /* make degenerate triangles for mapping edges */
 726                 if( fabs( a[ 0 ] - b[ 0 ] ) < 0.01f || fabs( a[ 1 ] - b[ 1 ] ) < 0.01f )
 727                 {
 728                         dv2[ 0 ] = dv[ i ];
 729                         dv2[ 1 ] = dv[ (i + 1) % 3 ];
 730                         dv2[ 2 ] = dv[ (i + 1) % 3 ];
 731
 732                         /* map the degenerate triangle */
 733                         MapTriangle_r( lm, info, dv2, plane, stv, ttv );
 734                 }
 735         }
 736
 737         return qtrue;
 738 }
 739
 740
 741
 742 /*
 743 MapQuad_r()
 744 recursively subdivides a quad until its edges are shorter
 745 than the distance between two luxels
 746 */
 747
 748 static void MapQuad_r( rawLightmap_t *lm, surfaceInfo_t *info, bspDrawVert_t *dv[ 4 ], vec4_t plane, vec3_t stv[ 4 ], vec3_t ttv[ 4 ] )
 749 {
 750         bspDrawVert_t   mid[ 2 ], *dv2[ 4 ];
 751         int                             max;
 752
 753
 754         /* subdivide calc */
 755         {
 756                 int                     i;
 757                 float           *a, *b, dx, dy, dist, maxDist;
 758
 759
 760                 /* find the longest edge and split it */
 761                 max = -1;
 762                 maxDist = 0;
 763                 for( i = 0; i < 4; i++ )
 764                 {
 765                         /* get verts */
 766                         a = dv[ i ]->lightmap[ 0 ];
 767                         b = dv[ (i + 1) % 4 ]->lightmap[ 0 ];
 768
 769                         /* get dists */
 770                         dx = a[ 0 ] - b[ 0 ];
 771                         dy = a[ 1 ] - b[ 1 ];
 772                         dist = (dx * dx) + (dy * dy);   //% sqrt( (dx * dx) + (dy * dy) );
 773
 774                         /* longer? */
 775                         if( dist > maxDist )
 776                         {
 777                                 maxDist = dist;
 778                                 max = i;
 779                         }
 780                 }
 781
 782                 /* try to early out */
 783                 if( max < 0 || maxDist <= subdivideThreshold )
 784                         return;
 785         }
 786
 787         /* we only care about even/odd edges */
 788         max &= 1;
 789
 790         /* split the longest edges */
 791         LerpDrawVert( dv[ max ], dv[ (max + 1) % 4 ], &mid[ 0 ] );
 792         LerpDrawVert( dv[ max + 2 ], dv[ (max + 3) % 4 ], &mid[ 1 ] );
 793
 794         /* map the vertexes */
 795         MapSingleLuxel( lm, info, &mid[ 0 ], plane, 1, stv, ttv );
 796         MapSingleLuxel( lm, info, &mid[ 1 ], plane, 1, stv, ttv );
 797
 798         /* 0 and 2 */
 799         if( max == 0 )
 800         {
 801                 /* recurse to first quad */
 802                 dv2[ 0 ] = dv[ 0 ];
 803                 dv2[ 1 ] = &mid[ 0 ];
 804                 dv2[ 2 ] = &mid[ 1 ];
 805                 dv2[ 3 ] = dv[ 3 ];
 806                 MapQuad_r( lm, info, dv2, plane, stv, ttv );
 807
 808                 /* recurse to second quad */
 809                 dv2[ 0 ] = &mid[ 0 ];
 810                 dv2[ 1 ] = dv[ 1 ];
 811                 dv2[ 2 ] = dv[ 2 ];
 812                 dv2[ 3 ] = &mid[ 1 ];
 813                 MapQuad_r( lm, info, dv2, plane, stv, ttv );
 814         }
 815
 816         /* 1 and 3 */
 817         else
 818         {
 819                 /* recurse to first quad */
 820                 dv2[ 0 ] = dv[ 0 ];
 821                 dv2[ 1 ] = dv[ 1 ];
 822                 dv2[ 2 ] = &mid[ 0 ];
 823                 dv2[ 3 ] = &mid[ 1 ];
 824                 MapQuad_r( lm, info, dv2, plane, stv, ttv );
 825
 826                 /* recurse to second quad */
 827                 dv2[ 0 ] = &mid[ 1 ];
 828                 dv2[ 1 ] = &mid[ 0 ];
 829                 dv2[ 2 ] = dv[ 2 ];
 830                 dv2[ 3 ] = dv[ 3 ];
 831                 MapQuad_r( lm, info, dv2, plane, stv, ttv );
 832         }
 833 }
 834
 835
 836
 837 /*
 838 MapQuad()
 839 seed function for MapQuad_r()
 840 requires a cw ordered triangle quad
 841 */
 842
 843 #define QUAD_PLANAR_EPSILON             0.5f
 844
 845 static qboolean MapQuad( rawLightmap_t *lm, surfaceInfo_t *info, bspDrawVert_t *dv[ 4 ] )
 846 {
 847         float                   dist;
 848         vec4_t                  plane;
 849         vec3_t                  *stv, *ttv, stvStatic[ 4 ], ttvStatic[ 4 ];
 850
 851
 852         /* get plane if possible */
 853         if( lm->plane != NULL )
 854         {
 855                 VectorCopy( lm->plane, plane );
 856                 plane[ 3 ] = lm->plane[ 3 ];
 857         }
 858
 859         /* otherwise make one from the points */
 860         else if( PlaneFromPoints( plane, dv[ 0 ]->xyz, dv[ 1 ]->xyz, dv[ 2 ]->xyz ) == qfalse )
 861                 return qfalse;
 862
 863         /* 4th point must fall on the plane */
 864         dist = DotProduct( plane, dv[ 3 ]->xyz ) - plane[ 3 ];
 865         if( fabs( dist ) > QUAD_PLANAR_EPSILON )
 866                 return qfalse;
 867
 868         /* check to see if we need to calculate texture->world tangent vectors */
 869         if( info->si->normalImage != NULL && CalcTangentVectors( 4, dv, stvStatic, ttvStatic ) )
 870         {
 871                 stv = stvStatic;
 872                 ttv = ttvStatic;
 873         }
 874         else
 875         {
 876                 stv = NULL;
 877                 ttv = NULL;
 878         }
 879
 880         /* map the vertexes */
 881         MapSingleLuxel( lm, info, dv[ 0 ], plane, 1, stv, ttv );
 882         MapSingleLuxel( lm, info, dv[ 1 ], plane, 1, stv, ttv );
 883         MapSingleLuxel( lm, info, dv[ 2 ], plane, 1, stv, ttv );
 884         MapSingleLuxel( lm, info, dv[ 3 ], plane, 1, stv, ttv );
 885
 886         /* subdivide the quad */
 887         MapQuad_r( lm, info, dv, plane, stv, ttv );
 888         return qtrue;
 889 }
 890
 891
 892
 893 /*
 894 MapRawLightmap()
 895 maps the locations, normals, and pvs clusters for a raw lightmap
 896 */
 897
 898 #define VectorDivide( in, d, out )      VectorScale( in, (1.0f / (d)), out )    //%     (out)[ 0 ] = (in)[ 0 ] / (d), (out)[ 1 ] = (in)[ 1 ] / (d), (out)[ 2 ] = (in)[ 2 ] / (d)
 899
 900 void MapRawLightmap( int rawLightmapNum )
 901 {
 902         int                                     n, num, i, x, y, sx, sy, pw[ 5 ], r, *cluster, mapNonAxial;
 903         float                           *luxel, *origin, *normal, samples, radius, pass;
 904         rawLightmap_t           *lm;
 905         bspDrawSurface_t        *ds;
 906         surfaceInfo_t           *info;
 907         mesh_t                          src, *subdivided, *mesh;
 908         bspDrawVert_t           *verts, *dv[ 4 ], fake;
 909
 910
 911         /* bail if this number exceeds the number of raw lightmaps */
 912         if( rawLightmapNum >= numRawLightmaps )
 913                 return;
 914
 915         /* get lightmap */
 916         lm = &rawLightmaps[ rawLightmapNum ];
 917
 918         /* -----------------------------------------------------------------
 919            map referenced surfaces onto the raw lightmap
 920            ----------------------------------------------------------------- */
 921
 922         /* walk the list of surfaces on this raw lightmap */
 923         for( n = 0; n < lm->numLightSurfaces; n++ )
 924         {
 925                 /* with > 1 surface per raw lightmap, clear occluded */
 926                 if( n > 0 )
 927                 {
 928                         for( y = 0; y < lm->sh; y++ )
 929                         {
 930                                 for( x = 0; x < lm->sw; x++ )
 931                                 {
 932                                         /* get cluster */
 933                                         cluster = SUPER_CLUSTER( x, y );
 934                                         if( *cluster < 0 )
 935                                                 *cluster = CLUSTER_UNMAPPED;
 936                                 }
 937                         }
 938                 }
 939
 940                 /* get surface */
 941                 num = lightSurfaces[ lm->firstLightSurface + n ];
 942                 ds = &bspDrawSurfaces[ num ];
 943                 info = &surfaceInfos[ num ];
 944
 945                 /* bail if no lightmap to calculate */
 946                 if( info->lm != lm )
 947                 {
 948                         Sys_Printf( "!" );
 949                         continue;
 950                 }
 951
 952                 /* map the surface onto the lightmap origin/cluster/normal buffers */
 953                 switch( ds->surfaceType )
 954                 {
 955                         case MST_PLANAR:
 956                                 /* get verts */
 957                                 verts = yDrawVerts + ds->firstVert;
 958
 959                                 /* map the triangles */
 960                                 for( mapNonAxial = 0; mapNonAxial < 2; mapNonAxial++ )
 961                                 {
 962                                         for( i = 0; i < ds->numIndexes; i += 3 )
 963                                         {
 964                                                 dv[ 0 ] = &verts[ bspDrawIndexes[ ds->firstIndex + i ] ];
 965                                                 dv[ 1 ] = &verts[ bspDrawIndexes[ ds->firstIndex + i + 1 ] ];
 966                                                 dv[ 2 ] = &verts[ bspDrawIndexes[ ds->firstIndex + i + 2 ] ];
 967                                                 MapTriangle( lm, info, dv, mapNonAxial );
 968                                         }
 969                                 }
 970                                 break;
 971
 972                         case MST_PATCH:
 973                                 /* make a mesh from the drawsurf */
 974                                 src.width = ds->patchWidth;
 975                                 src.height = ds->patchHeight;
 976                                 src.verts = &yDrawVerts[ ds->firstVert ];
 977                                 //%     subdivided = SubdivideMesh( src, 8, 512 );
 978                                 subdivided = SubdivideMesh2( src, info->patchIterations );
 979
 980                                 /* fit it to the curve and remove colinear verts on rows/columns */
 981                                 PutMeshOnCurve( *subdivided );
 982                                 mesh = RemoveLinearMeshColumnsRows( subdivided );
 983                                 FreeMesh( subdivided );
 984
 985                                 /* get verts */
 986                                 verts = mesh->verts;
 987
 988                                 /* debug code */
 989                                 #if 0
 990                                         if( lm->plane )
 991                                         {
 992                                                 Sys_Printf( "Planar patch: [%1.3f %1.3f %1.3f] [%1.3f %1.3f %1.3f] [%1.3f %1.3f %1.3f]\n",
 993                                                         lm->plane[ 0 ], lm->plane[ 1 ], lm->plane[ 2 ],
 994                                                         lm->vecs[ 0 ][ 0 ], lm->vecs[ 0 ][ 1 ], lm->vecs[ 0 ][ 2 ],
 995                                                         lm->vecs[ 1 ][ 0 ], lm->vecs[ 1 ][ 1 ], lm->vecs[ 1 ][ 2 ] );
 996                                         }
 997                                 #endif
 998
 999                                 /* map the mesh quads */
1000                                 #if 0
1001
1002                                 for( mapNonAxial = 0; mapNonAxial < 2; mapNonAxial++ )
1003                                 {
1004                                         for( y = 0; y < (mesh->height - 1); y++ )
1005                                         {
1006                                                 for( x = 0; x < (mesh->width - 1); x++ )
1007                                                 {
1008                                                         /* set indexes */
1009                                                         pw[ 0 ] = x + (y * mesh->width);
1010                                                         pw[ 1 ] = x + ((y + 1) * mesh->width);
1011                                                         pw[ 2 ] = x + 1 + ((y + 1) * mesh->width);
1012                                                         pw[ 3 ] = x + 1 + (y * mesh->width);
1013                                                         pw[ 4 ] = x + (y * mesh->width);        /* same as pw[ 0 ] */
1014
1015                                                         /* set radix */
1016                                                         r = (x + y) & 1;
1017
1018                                                         /* get drawverts and map first triangle */
1019                                                         dv[ 0 ] = &verts[ pw[ r + 0 ] ];
1020                                                         dv[ 1 ] = &verts[ pw[ r + 1 ] ];
1021                                                         dv[ 2 ] = &verts[ pw[ r + 2 ] ];
1022                                                         MapTriangle( lm, info, dv, mapNonAxial );
1023
1024                                                         /* get drawverts and map second triangle */
1025                                                         dv[ 0 ] = &verts[ pw[ r + 0 ] ];
1026                                                         dv[ 1 ] = &verts[ pw[ r + 2 ] ];
1027                                                         dv[ 2 ] = &verts[ pw[ r + 3 ] ];
1028                                                         MapTriangle( lm, info, dv, mapNonAxial );
1029                                                 }
1030                                         }
1031                                 }
1032
1033                                 #else
1034
1035                                 for( y = 0; y < (mesh->height - 1); y++ )
1036                                 {
1037                                         for( x = 0; x < (mesh->width - 1); x++ )
1038                                         {
1039                                                 /* set indexes */
1040                                                 pw[ 0 ] = x + (y * mesh->width);
1041                                                 pw[ 1 ] = x + ((y + 1) * mesh->width);
1042                                                 pw[ 2 ] = x + 1 + ((y + 1) * mesh->width);
1043                                                 pw[ 3 ] = x + 1 + (y * mesh->width);
1044                                                 pw[ 4 ] = pw[ 0 ];
1045
1046                                                 /* set radix */
1047                                                 r = (x + y) & 1;
1048
1049                                                 /* attempt to map quad first */
1050                                                 dv[ 0 ] = &verts[ pw[ r + 0 ] ];
1051                                                 dv[ 1 ] = &verts[ pw[ r + 1 ] ];
1052                                                 dv[ 2 ] = &verts[ pw[ r + 2 ] ];
1053                                                 dv[ 3 ] = &verts[ pw[ r + 3 ] ];
1054                                                 if( MapQuad( lm, info, dv ) )
1055                                                         continue;
1056
1057                                                 /* get drawverts and map first triangle */
1058                                                 MapTriangle( lm, info, dv, mapNonAxial );
1059
1060                                                 /* get drawverts and map second triangle */
1061                                                 dv[ 1 ] = &verts[ pw[ r + 2 ] ];
1062                                                 dv[ 2 ] = &verts[ pw[ r + 3 ] ];
1063                                                 MapTriangle( lm, info, dv, mapNonAxial );
1064                                         }
1065                                 }
1066
1067                                 #endif
1068
1069                                 /* free the mesh */
1070                                 FreeMesh( mesh );
1071                                 break;
1072
1073                         default:
1074                                 break;
1075                 }
1076         }
1077
1078         /* -----------------------------------------------------------------
1079            average and clean up luxel normals
1080            ----------------------------------------------------------------- */
1081
1082         /* walk the luxels */
1083         for( y = 0; y < lm->sh; y++ )
1084         {
1085                 for( x = 0; x < lm->sw; x++ )
1086                 {
1087                         /* get luxel */
1088                         luxel = SUPER_LUXEL( 0, x, y );
1089                         normal = SUPER_NORMAL( x, y );
1090                         cluster = SUPER_CLUSTER( x, y );
1091
1092                         /* only look at mapped luxels */
1093                         if( *cluster < 0 )
1094                                 continue;
1095
1096                         /* the normal data could be the sum of multiple samples */
1097                         if( luxel[ 3 ] > 1.0f )
1098                                 VectorNormalize( normal, normal );
1099
1100                         /* mark this luxel as having only one normal */
1101                         luxel[ 3 ] = 1.0f;
1102                 }
1103         }
1104
1105         /* non-planar surfaces stop here */
1106         if( lm->plane == NULL )
1107                 return;
1108
1109         /* -----------------------------------------------------------------
1110            map occluded or unuxed luxels
1111            ----------------------------------------------------------------- */
1112
1113         /* walk the luxels */
1114         radius = floor( superSample / 2 );
1115         radius = radius > 0 ? radius : 1.0f;
1116         radius += 1.0f;
1117         for( pass = 2.0f; pass <= radius; pass += 1.0f )
1118         {
1119                 for( y = 0; y < lm->sh; y++ )
1120                 {
1121                         for( x = 0; x < lm->sw; x++ )
1122                         {
1123                                 /* get luxel */
1124                                 luxel = SUPER_LUXEL( 0, x, y );
1125                                 normal = SUPER_NORMAL( x, y );
1126                                 cluster = SUPER_CLUSTER( x, y );
1127
1128                                 /* only look at unmapped luxels */
1129                                 if( *cluster != CLUSTER_UNMAPPED )
1130                                         continue;
1131
1132                                 /* divine a normal and origin from neighboring luxels */
1133                                 VectorClear( fake.xyz );
1134                                 VectorClear( fake.normal );
1135                                 fake.lightmap[ 0 ][ 0 ] = x;    //% 0.0001 + x;
1136                                 fake.lightmap[ 0 ][ 1 ] = y;    //% 0.0001 + y;
1137                                 samples = 0.0f;
1138                                 for( sy = (y - 1); sy <= (y + 1); sy++ )
1139                                 {
1140                                         if( sy < 0 || sy >= lm->sh )
1141                                                 continue;
1142
1143                                         for( sx = (x - 1); sx <= (x + 1); sx++ )
1144                                         {
1145                                                 if( sx < 0 || sx >= lm->sw || (sx == x && sy == y) )
1146                                                         continue;
1147
1148                                                 /* get neighboring luxel */
1149                                                 luxel = SUPER_LUXEL( 0, sx, sy );
1150                                                 origin = SUPER_ORIGIN( sx, sy );
1151                                                 normal = SUPER_NORMAL( sx, sy );
1152                                                 cluster = SUPER_CLUSTER( sx, sy );
1153
1154                                                 /* only consider luxels mapped in previous passes */
1155                                                 if( *cluster < 0 || luxel[ 0 ] >= pass )
1156                                                         continue;
1157
1158                                                 /* add its distinctiveness to our own */
1159                                                 VectorAdd( fake.xyz, origin, fake.xyz );
1160                                                 VectorAdd( fake.normal, normal, fake.normal );
1161                                                 samples += luxel[ 3 ];
1162                                         }
1163                                 }
1164
1165                                 /* any samples? */
1166                                 if( samples == 0.0f )
1167                                         continue;
1168
1169                                 /* average */
1170                                 VectorDivide( fake.xyz, samples, fake.xyz );
1171                                 //%     VectorDivide( fake.normal, samples, fake.normal );
1172                                 if( VectorNormalize( fake.normal, fake.normal ) == 0.0f )
1173                                         continue;
1174
1175                                 /* map the fake vert */
1176                                 MapSingleLuxel( lm, NULL, &fake, lm->plane, pass, NULL, NULL );
1177                         }
1178                 }
1179         }
1180
1181         /* -----------------------------------------------------------------
1182            average and clean up luxel normals
1183            ----------------------------------------------------------------- */
1184
1185         /* walk the luxels */
1186         for( y = 0; y < lm->sh; y++ )
1187         {
1188                 for( x = 0; x < lm->sw; x++ )
1189                 {
1190                         /* get luxel */
1191                         luxel = SUPER_LUXEL( 0, x, y );
1192                         normal = SUPER_NORMAL( x, y );
1193                         cluster = SUPER_CLUSTER( x, y );
1194
1195                         /* only look at mapped luxels */
1196                         if( *cluster < 0 )
1197                                 continue;
1198
1199                         /* the normal data could be the sum of multiple samples */
1200                         if( luxel[ 3 ] > 1.0f )
1201                                 VectorNormalize( normal, normal );
1202
1203                         /* mark this luxel as having only one normal */
1204                         luxel[ 3 ] = 1.0f;
1205                 }
1206         }
1207
1208         /* debug code */
1209         #if 0
1210                 Sys_Printf( "\n" );
1211                 for( y = 0; y < lm->sh; y++ )
1212                 {
1213                         for( x = 0; x < lm->sw; x++ )
1214                         {
1215                                 vec3_t  mins, maxs;
1216
1217
1218                                 cluster = SUPER_CLUSTER( x, y );
1219                                 origin = SUPER_ORIGIN( x, y );
1220                                 normal = SUPER_NORMAL( x, y );
1221                                 luxel = SUPER_LUXEL( x, y );
1222
1223                                 if( *cluster < 0 )
1224                                         continue;
1225
1226                                 /* check if within the bounding boxes of all surfaces referenced */
1227                                 ClearBounds( mins, maxs );
1228                                 for( n = 0; n < lm->numLightSurfaces; n++ )
1229                                 {
1230                                         int TOL;
1231                                         info = &surfaceInfos[ lightSurfaces[ lm->firstLightSurface + n ] ];
1232                                         TOL = info->sampleSize + 2;
1233                                         AddPointToBounds( info->mins, mins, maxs );
1234                                         AddPointToBounds( info->maxs, mins, maxs );
1235                                         if( origin[ 0 ] > (info->mins[ 0 ] - TOL) && origin[ 0 ] < (info->maxs[ 0 ] + TOL) &&
1236                                                 origin[ 1 ] > (info->mins[ 1 ] - TOL) && origin[ 1 ] < (info->maxs[ 1 ] + TOL) &&
1237                                                 origin[ 2 ] > (info->mins[ 2 ] - TOL) && origin[ 2 ] < (info->maxs[ 2 ] + TOL) )
1238                                                 break;
1239                                 }
1240
1241                                 /* inside? */
1242                                 if( n < lm->numLightSurfaces )
1243                                         continue;
1244
1245                                 /* report bogus origin */
1246                                 Sys_Printf( "%6d [%2d,%2d] (%4d): XYZ(%+4.1f %+4.1f %+4.1f) LO(%+4.1f %+4.1f %+4.1f) HI(%+4.1f %+4.1f %+4.1f) <%3.0f>\n",
1247                                         rawLightmapNum, x, y, *cluster,
1248                                         origin[ 0 ], origin[ 1 ], origin[ 2 ],
1249                                         mins[ 0 ], mins[ 1 ], mins[ 2 ],
1250                                         maxs[ 0 ], maxs[ 1 ], maxs[ 2 ],
1251                                         luxel[ 3 ] );
1252                         }
1253                 }
1254         #endif
1255 }
1256
1257
1258
1259 /*
1260 SetupDirt()
1261 sets up dirtmap (ambient occlusion)
1262 */
1263
1264 #define DIRT_CONE_ANGLE                         88      /* degrees */
1265 #define DIRT_NUM_ANGLE_STEPS            16
1266 #define DIRT_NUM_ELEVATION_STEPS        3
1267 #define DIRT_NUM_VECTORS                        (DIRT_NUM_ANGLE_STEPS * DIRT_NUM_ELEVATION_STEPS)
1268
1269 static vec3_t           dirtVectors[ DIRT_NUM_VECTORS ];
1270 static int                      numDirtVectors = 0;
1271
1272 void SetupDirt( void )
1273 {
1274         int             i, j;
1275         float   angle, elevation, angleStep, elevationStep;
1276
1277
1278         /* note it */
1279         Sys_FPrintf( SYS_VRB, "--- SetupDirt ---\n" );
1280
1281         /* calculate angular steps */
1282         angleStep = DEG2RAD( 360.0f / DIRT_NUM_ANGLE_STEPS );
1283         elevationStep = DEG2RAD( DIRT_CONE_ANGLE / DIRT_NUM_ELEVATION_STEPS );
1284
1285         /* iterate angle */
1286         angle = 0.0f;
1287         for( i = 0, angle = 0.0f; i < DIRT_NUM_ANGLE_STEPS; i++, angle += angleStep )
1288         {
1289                 /* iterate elevation */
1290                 for( j = 0, elevation = elevationStep * 0.5f; j < DIRT_NUM_ELEVATION_STEPS; j++, elevation += elevationStep )
1291                 {
1292                         dirtVectors[ numDirtVectors ][ 0 ] = sin( elevation ) * cos( angle );
1293                         dirtVectors[ numDirtVectors ][ 1 ] = sin( elevation ) * sin( angle );
1294                         dirtVectors[ numDirtVectors ][ 2 ] = cos( elevation );
1295                         numDirtVectors++;
1296                 }
1297         }
1298
1299         /* emit some statistics */
1300         Sys_FPrintf( SYS_VRB, "%9d dirtmap vectors\n", numDirtVectors );
1301 }
1302
1303
1304 /*
1305 DirtForSample()
1306 calculates dirt value for a given sample
1307 */
1308
1309 float DirtForSample( trace_t *trace )
1310 {
1311         int             i;
1312         float   gatherDirt, outDirt, angle, elevation, ooDepth;
1313         vec3_t  normal, worldUp, myUp, myRt, temp, direction, displacement;
1314
1315
1316         /* dummy check */
1317         if( !dirty )
1318                 return 1.0f;
1319         if( trace == NULL || trace->cluster < 0 )
1320                 return 0.0f;
1321
1322         /* setup */
1323         gatherDirt = 0.0f;
1324         ooDepth = 1.0f / dirtDepth;
1325         VectorCopy( trace->normal, normal );
1326
1327         /* check if the normal is aligned to the world-up */
1328         if( normal[ 0 ] == 0.0f && normal[ 1 ] == 0.0f )
1329         {
1330                 if( normal[ 2 ] == 1.0f )
1331                 {
1332                         VectorSet( myRt, 1.0f, 0.0f, 0.0f );
1333                         VectorSet( myUp, 0.0f, 1.0f, 0.0f );
1334                 }
1335                 else if( normal[ 2 ] == -1.0f )
1336                 {
1337                         VectorSet( myRt, -1.0f, 0.0f, 0.0f );
1338                         VectorSet( myUp,  0.0f, 1.0f, 0.0f );
1339                 }
1340         }
1341         else
1342         {
1343                 VectorSet( worldUp, 0.0f, 0.0f, 1.0f );
1344                 CrossProduct( normal, worldUp, myRt );
1345                 VectorNormalize( myRt, myRt );
1346                 CrossProduct( myRt, normal, myUp );
1347                 VectorNormalize( myUp, myUp );
1348         }
1349
1350         /* 1 = random mode, 0 (well everything else) = non-random mode */
1351         if( dirtMode == 1 )
1352         {
1353                 /* iterate */
1354                 for( i = 0; i < numDirtVectors; i++ )
1355                 {
1356                         /* get random vector */
1357                         angle = Random() * DEG2RAD( 360.0f );
1358                         elevation = Random() * DEG2RAD( DIRT_CONE_ANGLE );
1359                         temp[ 0 ] = cos( angle ) * sin( elevation );
1360                         temp[ 1 ] = sin( angle ) * sin( elevation );
1361                         temp[ 2 ] = cos( elevation );
1362
1363                         /* transform into tangent space */
1364                         direction[ 0 ] = myRt[ 0 ] * temp[ 0 ] + myUp[ 0 ] * temp[ 1 ] + normal[ 0 ] * temp[ 2 ];
1365                         direction[ 1 ] = myRt[ 1 ] * temp[ 0 ] + myUp[ 1 ] * temp[ 1 ] + normal[ 1 ] * temp[ 2 ];
1366                         direction[ 2 ] = myRt[ 2 ] * temp[ 0 ] + myUp[ 2 ] * temp[ 1 ] + normal[ 2 ] * temp[ 2 ];
1367
1368                         /* set endpoint */
1369                         VectorMA( trace->origin, dirtDepth, direction, trace->end );
1370                         SetupTrace( trace );
1371
1372                         /* trace */
1373                         TraceLine( trace );
1374                         if( trace->opaque )
1375                         {
1376                                 VectorSubtract( trace->hit, trace->origin, displacement );
1377                                 gatherDirt += 1.0f - ooDepth * VectorLength( displacement );
1378                         }
1379                 }
1380         }
1381         else
1382         {
1383                 /* iterate through ordered vectors */
1384                 for( i = 0; i < numDirtVectors; i++ )
1385                 {
1386                         /* transform vector into tangent space */
1387                         direction[ 0 ] = myRt[ 0 ] * dirtVectors[ i ][ 0 ] + myUp[ 0 ] * dirtVectors[ i ][ 1 ] + normal[ 0 ] * dirtVectors[ i ][ 2 ];
1388                         direction[ 1 ] = myRt[ 1 ] * dirtVectors[ i ][ 0 ] + myUp[ 1 ] * dirtVectors[ i ][ 1 ] + normal[ 1 ] * dirtVectors[ i ][ 2 ];
1389                         direction[ 2 ] = myRt[ 2 ] * dirtVectors[ i ][ 0 ] + myUp[ 2 ] * dirtVectors[ i ][ 1 ] + normal[ 2 ] * dirtVectors[ i ][ 2 ];
1390
1391                         /* set endpoint */
1392                         VectorMA( trace->origin, dirtDepth, direction, trace->end );
1393                         SetupTrace( trace );
1394
1395                         /* trace */
1396                         TraceLine( trace );
1397                         if( trace->opaque )
1398                         {
1399                                 VectorSubtract( trace->hit, trace->origin, displacement );
1400                                 gatherDirt += 1.0f - ooDepth * VectorLength( displacement );
1401                         }
1402                 }
1403         }
1404
1405         /* direct ray */
1406         VectorMA( trace->origin, dirtDepth, normal, trace->end );
1407         SetupTrace( trace );
1408
1409         /* trace */
1410         TraceLine( trace );
1411         if( trace->opaque )
1412         {
1413                 VectorSubtract( trace->hit, trace->origin, displacement );
1414                 gatherDirt += 1.0f - ooDepth * VectorLength( displacement );
1415         }
1416
1417         /* early out */
1418         if( gatherDirt <= 0.0f )
1419                 return 1.0f;
1420
1421         /* apply gain (does this even do much? heh) */
1422         outDirt = pow( gatherDirt / (numDirtVectors + 1), dirtGain );
1423         if( outDirt > 1.0f )
1424                 outDirt = 1.0f;
1425
1426         /* apply scale */
1427         outDirt *= dirtScale;
1428         if( outDirt > 1.0f )
1429                 outDirt = 1.0f;
1430
1431         /* return to sender */
1432         return 1.0f - outDirt;
1433 }
1434
1435
1436
1437 /*
1438 DirtyRawLightmap()
1439 calculates dirty fraction for each luxel
1440 */
1441
1442 void DirtyRawLightmap( int rawLightmapNum )
1443 {
1444         int                                     i, x, y, sx, sy, *cluster;
1445         float                           *origin, *normal, *dirt, *dirt2, average, samples;
1446         rawLightmap_t           *lm;
1447         surfaceInfo_t           *info;
1448         trace_t                         trace;
1449
1450
1451         /* bail if this number exceeds the number of raw lightmaps */
1452         if( rawLightmapNum >= numRawLightmaps )
1453                 return;
1454
1455         /* get lightmap */
1456         lm = &rawLightmaps[ rawLightmapNum ];
1457
1458         /* setup trace */
1459         trace.testOcclusion = qtrue;
1460         trace.forceSunlight = qfalse;
1461         trace.recvShadows = lm->recvShadows;
1462         trace.numSurfaces = lm->numLightSurfaces;
1463         trace.surfaces = &lightSurfaces[ lm->firstLightSurface ];
1464         trace.inhibitRadius = DEFAULT_INHIBIT_RADIUS;
1465         trace.testAll = qfalse;
1466
1467         /* twosided lighting (may or may not be a good idea for lightmapped stuff) */
1468         trace.twoSided = qfalse;
1469         for( i = 0; i < trace.numSurfaces; i++ )
1470         {
1471                 /* get surface */
1472                 info = &surfaceInfos[ trace.surfaces[ i ] ];
1473
1474                 /* check twosidedness */
1475                 if( info->si->twoSided )
1476                 {
1477                         trace.twoSided = qtrue;
1478                         break;
1479                 }
1480         }
1481
1482         /* gather dirt */
1483         for( y = 0; y < lm->sh; y++ )
1484         {
1485                 for( x = 0; x < lm->sw; x++ )
1486                 {
1487                         /* get luxel */
1488                         cluster = SUPER_CLUSTER( x, y );
1489                         origin = SUPER_ORIGIN( x, y );
1490                         normal = SUPER_NORMAL( x, y );
1491                         dirt = SUPER_DIRT( x, y );
1492
1493                         /* set default dirt */
1494                         *dirt = 0.0f;
1495
1496                         /* only look at mapped luxels */
1497                         if( *cluster < 0 )
1498                                 continue;
1499
1500                         /* copy to trace */
1501                         trace.cluster = *cluster;
1502                         VectorCopy( origin, trace.origin );
1503                         VectorCopy( normal, trace.normal );
1504
1505                         /* get dirt */
1506                         *dirt = DirtForSample( &trace );
1507                 }
1508         }
1509
1510         /* testing no filtering */
1511         //%     return;
1512
1513         /* filter dirt */
1514         for( y = 0; y < lm->sh; y++ )
1515         {
1516                 for( x = 0; x < lm->sw; x++ )
1517                 {
1518                         /* get luxel */
1519                         cluster = SUPER_CLUSTER( x, y );
1520                         dirt = SUPER_DIRT( x, y );
1521
1522                         /* filter dirt by adjacency to unmapped luxels */
1523                         average = *dirt;
1524                         samples = 1.0f;
1525                         for( sy = (y - 1); sy <= (y + 1); sy++ )
1526                         {
1527                                 if( sy < 0 || sy >= lm->sh )
1528                                         continue;
1529
1530                                 for( sx = (x - 1); sx <= (x + 1); sx++ )
1531                                 {
1532                                         if( sx < 0 || sx >= lm->sw || (sx == x && sy == y) )
1533                                                 continue;
1534
1535                                         /* get neighboring luxel */
1536                                         cluster = SUPER_CLUSTER( sx, sy );
1537                                         dirt2 = SUPER_DIRT( sx, sy );
1538                                         if( *cluster < 0 || *dirt2 <= 0.0f )
1539                                                 continue;
1540
1541                                         /* add it */
1542                                         average += *dirt2;
1543                                         samples += 1.0f;
1544                                 }
1545
1546                                 /* bail */
1547                                 if( samples <= 0.0f )
1548                                         break;
1549                         }
1550
1551                         /* bail */
1552                         if( samples <= 0.0f )
1553                                 continue;
1554
1555                         /* scale dirt */
1556                         *dirt = average / samples;
1557                 }
1558         }
1559 }
1560
1561
1562
1563 /*
1564 SubmapRawLuxel()
1565 calculates the pvs cluster, origin, normal of a sub-luxel
1566 */
1567
1568 static qboolean SubmapRawLuxel( rawLightmap_t *lm, int x, int y, float bx, float by, int *sampleCluster, vec3_t sampleOrigin, vec3_t sampleNormal )
1569 {
1570         int                     i, *cluster, *cluster2;
1571         float           *origin, *origin2, *normal;     //%     , *normal2;
1572         vec3_t          originVecs[ 2 ];                        //%     , normalVecs[ 2 ];
1573
1574
1575         /* calulate x vector */
1576         if( (x < (lm->sw - 1) && bx >= 0.0f) || (x == 0 && bx <= 0.0f) )
1577         {
1578                 cluster = SUPER_CLUSTER( x, y );
1579                 origin = SUPER_ORIGIN( x, y );
1580                 //%     normal = SUPER_NORMAL( x, y );
1581                 cluster2 = SUPER_CLUSTER( x + 1, y );
1582                 origin2 = *cluster2 < 0 ? SUPER_ORIGIN( x, y ) : SUPER_ORIGIN( x + 1, y );
1583                 //%     normal2 = *cluster2 < 0 ? SUPER_NORMAL( x, y ) : SUPER_NORMAL( x + 1, y );
1584         }
1585         else if( (x > 0 && bx <= 0.0f) || (x == (lm->sw - 1) && bx >= 0.0f) )
1586         {
1587                 cluster = SUPER_CLUSTER( x - 1, y );
1588                 origin = *cluster < 0 ? SUPER_ORIGIN( x, y ) : SUPER_ORIGIN( x - 1, y );
1589                 //%     normal = *cluster < 0 ? SUPER_NORMAL( x, y ) : SUPER_NORMAL( x - 1, y );
1590                 cluster2 = SUPER_CLUSTER( x, y );
1591                 origin2 = SUPER_ORIGIN( x, y );
1592                 //%     normal2 = SUPER_NORMAL( x, y );
1593         }
1594         else
1595                 Sys_Printf( "WARNING: Spurious lightmap S vector\n" );
1596
1597         VectorSubtract( origin2, origin, originVecs[ 0 ] );
1598         //%     VectorSubtract( normal2, normal, normalVecs[ 0 ] );
1599
1600         /* calulate y vector */
1601         if( (y < (lm->sh - 1) && bx >= 0.0f) || (y == 0 && bx <= 0.0f) )
1602         {
1603                 cluster = SUPER_CLUSTER( x, y );
1604                 origin = SUPER_ORIGIN( x, y );
1605                 //%     normal = SUPER_NORMAL( x, y );
1606                 cluster2 = SUPER_CLUSTER( x, y + 1 );
1607                 origin2 = *cluster2 < 0 ? SUPER_ORIGIN( x, y ) : SUPER_ORIGIN( x, y + 1 );
1608                 //%     normal2 = *cluster2 < 0 ? SUPER_NORMAL( x, y ) : SUPER_NORMAL( x, y + 1 );
1609         }
1610         else if( (y > 0 && bx <= 0.0f) || (y == (lm->sh - 1) && bx >= 0.0f) )
1611         {
1612                 cluster = SUPER_CLUSTER( x, y - 1 );
1613                 origin = *cluster < 0 ? SUPER_ORIGIN( x, y ) : SUPER_ORIGIN( x, y - 1 );
1614                 //%     normal = *cluster < 0 ? SUPER_NORMAL( x, y ) : SUPER_NORMAL( x, y - 1 );
1615                 cluster2 = SUPER_CLUSTER( x, y );
1616                 origin2 = SUPER_ORIGIN( x, y );
1617                 //%     normal2 = SUPER_NORMAL( x, y );
1618         }
1619         else
1620                 Sys_Printf( "WARNING: Spurious lightmap T vector\n" );
1621
1622         VectorSubtract( origin2, origin, originVecs[ 1 ] );
1623         //%     VectorSubtract( normal2, normal, normalVecs[ 1 ] );
1624
1625         /* calculate new origin */
1626         //%     VectorMA( origin, bx, originVecs[ 0 ], sampleOrigin );
1627         //%     VectorMA( sampleOrigin, by, originVecs[ 1 ], sampleOrigin );
1628         for( i = 0; i < 3; i++ )
1629                 sampleOrigin[ i ] = sampleOrigin[ i ] + (bx * originVecs[ 0 ][ i ]) + (by * originVecs[ 1 ][ i ]);
1630
1631         /* get cluster */
1632         *sampleCluster = ClusterForPointExtFilter( sampleOrigin, (LUXEL_EPSILON * 2), lm->numLightClusters, lm->lightClusters );
1633         if( *sampleCluster < 0 )
1634                 return qfalse;
1635
1636         /* calculate new normal */
1637         //%     VectorMA( normal, bx, normalVecs[ 0 ], sampleNormal );
1638         //%     VectorMA( sampleNormal, by, normalVecs[ 1 ], sampleNormal );
1639         //%     if( VectorNormalize( sampleNormal, sampleNormal ) <= 0.0f )
1640         //%             return qfalse;
1641         normal = SUPER_NORMAL( x, y );
1642         VectorCopy( normal, sampleNormal );
1643
1644         /* return ok */
1645         return qtrue;
1646 }
1647
1648
1649 /*
1650 SubsampleRawLuxel_r()
1651 recursively subsamples a luxel until its color gradient is low enough or subsampling limit is reached
1652 */
1653
1654 static void SubsampleRawLuxel_r( rawLightmap_t *lm, trace_t *trace, vec3_t sampleOrigin, int x, int y, float bias, float *lightLuxel )
1655 {
1656         int                     b, samples, mapped, lighted;
1657         int                     cluster[ 4 ];
1658         vec4_t          luxel[ 4 ];
1659         vec3_t          origin[ 4 ], normal[ 4 ];
1660         float           biasDirs[ 4 ][ 2 ] = { { -1.0f, -1.0f }, { 1.0f, -1.0f }, { -1.0f, 1.0f }, { 1.0f, 1.0f } };
1661         vec3_t          color, total;
1662
1663
1664         /* limit check */
1665         if( lightLuxel[ 3 ] >= lightSamples )
1666                 return;
1667
1668         /* setup */
1669         VectorClear( total );
1670         mapped = 0;
1671         lighted = 0;
1672
1673         /* make 2x2 subsample stamp */
1674         for( b = 0; b < 4; b++ )
1675         {
1676                 /* set origin */
1677                 VectorCopy( sampleOrigin, origin[ b ] );
1678
1679                 /* calculate position */
1680                 if( !SubmapRawLuxel( lm, x, y, (bias * biasDirs[ b ][ 0 ]), (bias * biasDirs[ b ][ 1 ]), &cluster[ b ], origin[ b ], normal[ b ] ) )
1681                 {
1682                         cluster[ b ] = -1;
1683                         continue;
1684                 }
1685                 mapped++;
1686
1687                 /* increment sample count */
1688                 luxel[ b ][ 3 ] = lightLuxel[ 3 ] + 1.0f;
1689
1690                 /* setup trace */
1691                 trace->cluster = *cluster;
1692                 VectorCopy( origin[ b ], trace->origin );
1693                 VectorCopy( normal[ b ], trace->normal );
1694
1695                 /* sample light */
1696
1697                 LightContributionToSample( trace );
1698
1699                 /* add to totals (fixme: make contrast function) */
1700                 VectorCopy( trace->color, luxel[ b ] );
1701                 VectorAdd( total, trace->color, total );
1702                 if( (luxel[ b ][ 0 ] + luxel[ b ][ 1 ] + luxel[ b ][ 2 ]) > 0.0f )
1703                         lighted++;
1704         }
1705
1706         /* subsample further? */
1707         if( (lightLuxel[ 3 ] + 1.0f) < lightSamples &&
1708                 (total[ 0 ] > 4.0f || total[ 1 ] > 4.0f || total[ 2 ] > 4.0f) &&
1709                 lighted != 0 && lighted != mapped )
1710         {
1711                 for( b = 0; b < 4; b++ )
1712                 {
1713                         if( cluster[ b ] < 0 )
1714                                 continue;
1715                         SubsampleRawLuxel_r( lm, trace, origin[ b ], x, y, (bias * 0.25f), luxel[ b ] );
1716                 }
1717         }
1718
1719         /* average */
1720         //%     VectorClear( color );
1721         //%     samples = 0;
1722         VectorCopy( lightLuxel, color );
1723         samples = 1;
1724         for( b = 0; b < 4; b++ )
1725         {
1726                 if( cluster[ b ] < 0 )
1727                         continue;
1728                 VectorAdd( color, luxel[ b ], color );
1729                 samples++;
1730         }
1731
1732         /* add to luxel */
1733         if( samples > 0 )
1734         {
1735                 /* average */
1736                 color[ 0 ] /= samples;
1737                 color[ 1 ] /= samples;
1738                 color[ 2 ] /= samples;
1739
1740                 /* add to color */
1741                 VectorCopy( color, lightLuxel );
1742                 lightLuxel[ 3 ] += 1.0f;
1743         }
1744 }
1745
1746
1747
1748 /*
1749 IlluminateRawLightmap()
1750 illuminates the luxels
1751 */
1752
1753 #define STACK_LL_SIZE                   (SUPER_LUXEL_SIZE * 64 * 64)
1754 #define LIGHT_LUXEL( x, y )             (lightLuxels + ((((y) * lm->sw) + (x)) * SUPER_LUXEL_SIZE))
1755
1756 void IlluminateRawLightmap( int rawLightmapNum )
1757 {
1758         int                                     i, t, x, y, sx, sy, size, llSize, luxelFilterRadius, lightmapNum;
1759         int                                     *cluster, *cluster2, mapped, lighted, totalLighted;
1760         rawLightmap_t           *lm;
1761         surfaceInfo_t           *info;
1762         qboolean                        filterColor, filterDir;
1763         float                           brightness;
1764         float                           *origin, *normal, *dirt, *luxel, *luxel2, *deluxel, *deluxel2;
1765         float                           *lightLuxels, *lightLuxel, samples, filterRadius, weight;
1766         vec3_t                          color, averageColor, averageDir, total, temp, temp2;
1767         float                           tests[ 4 ][ 2 ] = { { 0.0f, 0 }, { 1, 0 }, { 0, 1 }, { 1, 1 } };
1768         trace_t                         trace;
1769         float                           stackLightLuxels[ STACK_LL_SIZE ];
1770
1771
1772         /* bail if this number exceeds the number of raw lightmaps */
1773         if( rawLightmapNum >= numRawLightmaps )
1774                 return;
1775
1776         /* get lightmap */
1777         lm = &rawLightmaps[ rawLightmapNum ];
1778
1779         /* setup trace */
1780         trace.testOcclusion = !noTrace;
1781         trace.forceSunlight = qfalse;
1782         trace.recvShadows = lm->recvShadows;
1783         trace.numSurfaces = lm->numLightSurfaces;
1784         trace.surfaces = &lightSurfaces[ lm->firstLightSurface ];
1785         trace.inhibitRadius = DEFAULT_INHIBIT_RADIUS;
1786
1787         /* twosided lighting (may or may not be a good idea for lightmapped stuff) */
1788         trace.twoSided = qfalse;
1789         for( i = 0; i < trace.numSurfaces; i++ )
1790         {
1791                 /* get surface */
1792                 info = &surfaceInfos[ trace.surfaces[ i ] ];
1793
1794                 /* check twosidedness */
1795                 if( info->si->twoSided )
1796                 {
1797                         trace.twoSided = qtrue;
1798                         break;
1799                 }
1800         }
1801
1802         /* create a culled light list for this raw lightmap */
1803         CreateTraceLightsForBounds( lm->mins, lm->maxs, lm->plane, lm->numLightClusters, lm->lightClusters, LIGHT_SURFACES, &trace );
1804
1805         /* -----------------------------------------------------------------
1806            fill pass
1807            ----------------------------------------------------------------- */
1808
1809         /* set counts */
1810         numLuxelsIlluminated += (lm->sw * lm->sh);
1811
1812         /* test debugging state */
1813         if( debugSurfaces || debugAxis || debugCluster || debugOrigin || dirtDebug || normalmap )
1814         {
1815                 /* debug fill the luxels */
1816                 for( y = 0; y < lm->sh; y++ )
1817                 {
1818                         for( x = 0; x < lm->sw; x++ )
1819                         {
1820                                 /* get cluster */
1821                                 cluster = SUPER_CLUSTER( x, y );
1822
1823                                 /* only fill mapped luxels */
1824                                 if( *cluster < 0 )
1825                                         continue;
1826
1827                                 /* get particulars */
1828                                 luxel = SUPER_LUXEL( 0, x, y );
1829                                 origin = SUPER_ORIGIN( x, y );
1830                                 normal = SUPER_NORMAL( x, y );
1831
1832                                 /* color the luxel with raw lightmap num? */
1833                                 if( debugSurfaces )
1834                                         VectorCopy( debugColors[ rawLightmapNum % 12 ], luxel );
1835
1836                                 /* color the luxel with lightmap axis? */
1837                                 else if( debugAxis )
1838                                 {
1839                                         luxel[ 0 ] = (lm->axis[ 0 ] + 1.0f) * 127.5f;
1840                                         luxel[ 1 ] = (lm->axis[ 1 ] + 1.0f) * 127.5f;
1841                                         luxel[ 2 ] = (lm->axis[ 2 ] + 1.0f) * 127.5f;
1842                                 }
1843
1844                                 /* color the luxel with luxel cluster? */
1845                                 else if( debugCluster )
1846                                         VectorCopy( debugColors[ *cluster % 12 ], luxel );
1847
1848                                 /* color the luxel with luxel origin? */
1849                                 else if( debugOrigin )
1850                                 {
1851                                         VectorSubtract( lm->maxs, lm->mins, temp );
1852                                         VectorScale( temp, (1.0f / 255.0f), temp );
1853                                         VectorSubtract( origin, lm->mins, temp2 );
1854                                         luxel[ 0 ] = lm->mins[ 0 ] + (temp[ 0 ] * temp2[ 0 ]);
1855                                         luxel[ 1 ] = lm->mins[ 1 ] + (temp[ 1 ] * temp2[ 1 ]);
1856                                         luxel[ 2 ] = lm->mins[ 2 ] + (temp[ 2 ] * temp2[ 2 ]);
1857                                 }
1858
1859                                 /* color the luxel with the normal */
1860                                 else if( normalmap )
1861                                 {
1862                                         luxel[ 0 ] = (normal[ 0 ] + 1.0f) * 127.5f;
1863                                         luxel[ 1 ] = (normal[ 1 ] + 1.0f) * 127.5f;
1864                                         luxel[ 2 ] = (normal[ 2 ] + 1.0f) * 127.5f;
1865                                 }
1866
1867                                 /* otherwise clear it */
1868                                 else
1869                                         VectorClear( luxel );
1870
1871                                 /* add to counts */
1872                                 luxel[ 3 ] = 1.0f;
1873                         }
1874                 }
1875         }
1876         else
1877         {
1878                 /* allocate temporary per-light luxel storage */
1879                 llSize = lm->sw * lm->sh * SUPER_LUXEL_SIZE * sizeof( float );
1880                 if( llSize <= (STACK_LL_SIZE * sizeof( float )) )
1881                         lightLuxels = stackLightLuxels;
1882                 else
1883                         lightLuxels = safe_malloc( llSize );
1884
1885                 /* clear luxels */
1886                 //%     memset( lm->superLuxels[ 0 ], 0, llSize );
1887
1888                 /* set ambient color */
1889                 for( y = 0; y < lm->sh; y++ )
1890                 {
1891                         for( x = 0; x < lm->sw; x++ )
1892                         {
1893                                 /* get cluster */
1894                                 cluster = SUPER_CLUSTER( x, y );
1895                                 luxel = SUPER_LUXEL( 0, x, y );
1896                                 normal = SUPER_NORMAL( x, y );
1897                                 deluxel = SUPER_DELUXEL( x, y );
1898
1899                                 /* blacken unmapped clusters */
1900                                 if( *cluster < 0 )
1901                                         VectorClear( luxel );
1902
1903                                 /* set ambient */
1904                                 else
1905                                 {
1906                                         VectorCopy( ambientColor, luxel );
1907                                         if( deluxemap )
1908                                                 VectorScale( normal, 0.00390625f, deluxel );
1909                                         luxel[ 3 ] = 1.0f;
1910                                 }
1911                         }
1912                 }
1913
1914                 /* clear styled lightmaps */
1915                 size = lm->sw * lm->sh * SUPER_LUXEL_SIZE * sizeof( float );
1916                 for( lightmapNum = 1; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
1917                 {
1918                         if( lm->superLuxels[ lightmapNum ] != NULL )
1919                                 memset( lm->superLuxels[ lightmapNum ], 0, size );
1920                 }
1921
1922                 /* debugging code */
1923                 //%     if( trace.numLights <= 0 )
1924                 //%             Sys_Printf( "Lightmap %9d: 0 lights, axis: %.2f, %.2f, %.2f\n", rawLightmapNum, lm->axis[ 0 ], lm->axis[ 1 ], lm->axis[ 2 ] );
1925
1926                 /* walk light list */
1927                 for( i = 0; i < trace.numLights; i++ )
1928                 {
1929                         /* setup trace */
1930                         trace.light = trace.lights[ i ];
1931
1932                         /* style check */
1933                         for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
1934                         {
1935                                 if( lm->styles[ lightmapNum ] == trace.light->style ||
1936                                         lm->styles[ lightmapNum ] == LS_NONE )
1937                                         break;
1938                         }
1939
1940                         /* max of MAX_LIGHTMAPS (4) styles allowed to hit a surface/lightmap */
1941                         if( lightmapNum >= MAX_LIGHTMAPS )
1942                         {
1943                                 Sys_Printf( "WARNING: Hit per-surface style limit (%d)\n", MAX_LIGHTMAPS );
1944                                 continue;
1945                         }
1946
1947                         /* setup */
1948                         memset( lightLuxels, 0, llSize );
1949                         totalLighted = 0;
1950
1951                         /* initial pass, one sample per luxel */
1952                         for( y = 0; y < lm->sh; y++ )
1953                         {
1954                                 for( x = 0; x < lm->sw; x++ )
1955                                 {
1956                                         /* get cluster */
1957                                         cluster = SUPER_CLUSTER( x, y );
1958                                         if( *cluster < 0 )
1959                                                 continue;
1960
1961                                         /* get particulars */
1962                                         lightLuxel = LIGHT_LUXEL( x, y );
1963                                         deluxel = SUPER_DELUXEL( x, y );
1964                                         origin = SUPER_ORIGIN( x, y );
1965                                         normal = SUPER_NORMAL( x, y );
1966
1967                                         /* set contribution count */
1968                                         lightLuxel[ 3 ] = 1.0f;
1969
1970                                         /* setup trace */
1971                                         trace.cluster = *cluster;
1972                                         VectorCopy( origin, trace.origin );
1973                                         VectorCopy( normal, trace.normal );
1974
1975                                         /* get light for this sample */
1976                                         LightContributionToSample( &trace );
1977                                         VectorCopy( trace.color, lightLuxel );
1978
1979                                         /* add to count */
1980                                         if( trace.color[ 0 ] || trace.color[ 1 ] || trace.color[ 2 ] )
1981                                                 totalLighted++;
1982
1983                                         /* add to light direction map (fixme: use luxel normal as starting point for deluxel?) */
1984                                         if( deluxemap )
1985                                         {
1986                                                 /* color to grayscale (photoshop rgb weighting) */
1987                                                 brightness = trace.color[ 0 ] * 0.3f + trace.color[ 1 ] * 0.59f + trace.color[ 2 ] * 0.11f;
1988                                                 brightness *= (1.0 / 255.0);
1989                                                 VectorScale( trace.direction, brightness, trace.direction );
1990                                                 VectorAdd( deluxel, trace.direction, deluxel );
1991                                         }
1992                                 }
1993                         }
1994
1995                         /* don't even bother with everything else if nothing was lit */
1996                         if( totalLighted == 0 )
1997                                 continue;
1998
1999                         /* determine filter radius */
2000                         filterRadius = lm->filterRadius > trace.light->filterRadius
2001                                 ? lm->filterRadius
2002                                 : trace.light->filterRadius;
2003                         if( filterRadius < 0.0f )
2004                                 filterRadius = 0.0f;
2005
2006                         /* set luxel filter radius */
2007                         luxelFilterRadius = superSample * filterRadius / lm->sampleSize;
2008                         if( luxelFilterRadius == 0 && (filterRadius > 0.0f || filter) )
2009                                 luxelFilterRadius = 1;
2010
2011                         /* secondary pass, adaptive supersampling (fixme: use a contrast function to determine if subsampling is necessary) */
2012                         /* 2003-09-27: changed it so filtering disamples supersampling, as it would waste time */
2013                         if( lightSamples > 1 && luxelFilterRadius == 0 )
2014                         {
2015                                 /* walk luxels */
2016                                 for( y = 0; y < (lm->sh - 1); y++ )
2017                                 {
2018                                         for( x = 0; x < (lm->sw - 1); x++ )
2019                                         {
2020                                                 /* setup */
2021                                                 mapped = 0;
2022                                                 lighted = 0;
2023                                                 VectorClear( total );
2024
2025                                                 /* test 2x2 stamp */
2026                                                 for( t = 0; t < 4; t++ )
2027                                                 {
2028                                                         /* set sample coords */
2029                                                         sx = x + tests[ t ][ 0 ];
2030                                                         sy = y + tests[ t ][ 1 ];
2031
2032                                                         /* get cluster */
2033                                                         cluster = SUPER_CLUSTER( sx, sy );
2034                                                         if( *cluster < 0 )
2035                                                                 continue;
2036                                                         mapped++;
2037
2038                                                         /* get luxel */
2039                                                         lightLuxel = LIGHT_LUXEL( sx, sy );
2040                                                         VectorAdd( total, lightLuxel, total );
2041                                                         if( (lightLuxel[ 0 ] + lightLuxel[ 1 ] + lightLuxel[ 2 ]) > 0.0f )
2042                                                                 lighted++;
2043                                                 }
2044
2045                                                 /* if total color is under a certain amount, then don't bother subsampling */
2046                                                 if( total[ 0 ] <= 4.0f && total[ 1 ] <= 4.0f && total[ 2 ] <= 4.0f )
2047                                                         continue;
2048
2049                                                 /* if all 4 pixels are either in shadow or light, then don't subsample */
2050                                                 if( lighted != 0 && lighted != mapped )
2051                                                 {
2052                                                         for( t = 0; t < 4; t++ )
2053                                                         {
2054                                                                 /* set sample coords */
2055                                                                 sx = x + tests[ t ][ 0 ];
2056                                                                 sy = y + tests[ t ][ 1 ];
2057
2058                                                                 /* get luxel */
2059                                                                 cluster = SUPER_CLUSTER( sx, sy );
2060                                                                 if( *cluster < 0 )
2061                                                                         continue;
2062                                                                 lightLuxel = LIGHT_LUXEL( sx, sy );
2063                                                                 origin = SUPER_ORIGIN( sx, sy );
2064
2065                                                                 /* only subsample shadowed luxels */
2066                                                                 //%     if( (lightLuxel[ 0 ] + lightLuxel[ 1 ] + lightLuxel[ 2 ]) <= 0.0f )
2067                                                                 //%             continue;
2068
2069                                                                 /* subsample it */
2070                                                                 SubsampleRawLuxel_r( lm, &trace, origin, sx, sy, 0.25f, lightLuxel );
2071
2072                                                                 /* debug code to colorize subsampled areas to yellow */
2073                                                                 //%     luxel = SUPER_LUXEL( lightmapNum, sx, sy );
2074                                                                 //%     VectorSet( luxel, 255, 204, 0 );
2075                                                         }
2076                                                 }
2077                                         }
2078                                 }
2079                         }
2080
2081                         /* tertiary pass, apply dirt map (ambient occlusion) */
2082                         if( 0 && dirty )
2083                         {
2084                                 /* walk luxels */
2085                                 for( y = 0; y < lm->sh; y++ )
2086                                 {
2087                                         for( x = 0; x < lm->sw; x++ )
2088                                         {
2089                                                 /* get cluster  */
2090                                                 cluster = SUPER_CLUSTER( x, y );
2091                                                 if( *cluster < 0 )
2092                                                         continue;
2093
2094                                                 /* get particulars */
2095                                                 lightLuxel = LIGHT_LUXEL( x, y );
2096                                                 dirt = SUPER_DIRT( x, y );
2097
2098                                                 /* scale light value */
2099                                                 VectorScale( lightLuxel, *dirt, lightLuxel );
2100                                         }
2101                                 }
2102                         }
2103
2104                         /* allocate sampling lightmap storage */
2105                         if( lm->superLuxels[ lightmapNum ] == NULL )
2106                         {
2107                                 /* allocate sampling lightmap storage */
2108                                 size = lm->sw * lm->sh * SUPER_LUXEL_SIZE * sizeof( float );
2109                                 lm->superLuxels[ lightmapNum ] = safe_malloc( size );
2110                                 memset( lm->superLuxels[ lightmapNum ], 0, size );
2111                         }
2112
2113                         /* set style */
2114                         if( lightmapNum > 0 )
2115                         {
2116                                 lm->styles[ lightmapNum ] = trace.light->style;
2117                                 //%     Sys_Printf( "Surface %6d has lightstyle %d\n", rawLightmapNum, trace.light->style );
2118                         }
2119
2120                         /* copy to permanent luxels */
2121                         for( y = 0; y < lm->sh; y++ )
2122                         {
2123                                 for( x = 0; x < lm->sw; x++ )
2124                                 {
2125                                         /* get cluster and origin */
2126                                         cluster = SUPER_CLUSTER( x, y );
2127                                         if( *cluster < 0 )
2128                                                 continue;
2129                                         origin = SUPER_ORIGIN( x, y );
2130
2131                                         /* filter? */
2132                                         if( luxelFilterRadius )
2133                                         {
2134                                                 /* setup */
2135                                                 VectorClear( averageColor );
2136                                                 samples = 0.0f;
2137
2138                                                 /* cheaper distance-based filtering */
2139                                                 for( sy = (y - luxelFilterRadius); sy <= (y + luxelFilterRadius); sy++ )
2140                                                 {
2141                                                         if( sy < 0 || sy >= lm->sh )
2142                                                                 continue;
2143
2144                                                         for( sx = (x - luxelFilterRadius); sx <= (x + luxelFilterRadius); sx++ )
2145                                                         {
2146                                                                 if( sx < 0 || sx >= lm->sw )
2147                                                                         continue;
2148
2149                                                                 /* get particulars */
2150                                                                 cluster = SUPER_CLUSTER( sx, sy );
2151                                                                 if( *cluster < 0 )
2152                                                                         continue;
2153                                                                 lightLuxel = LIGHT_LUXEL( sx, sy );
2154
2155                                                                 /* create weight */
2156                                                                 weight = (abs( sx - x ) == luxelFilterRadius ? 0.5f : 1.0f);
2157                                                                 weight *= (abs( sy - y ) == luxelFilterRadius ? 0.5f : 1.0f);
2158
2159                                                                 /* scale luxel by filter weight */
2160                                                                 VectorScale( lightLuxel, weight, color );
2161                                                                 VectorAdd( averageColor, color, averageColor );
2162                                                                 samples += weight;
2163                                                         }
2164                                                 }
2165
2166                                                 /* any samples? */
2167                                                 if( samples <= 0.0f     )
2168                                                         continue;
2169
2170                                                 /* scale into luxel */
2171                                                 luxel = SUPER_LUXEL( lightmapNum, x, y );
2172                                                 luxel[ 3 ] = 1.0f;
2173
2174                                                 /* handle negative light */
2175                                                 if( trace.light->flags & LIGHT_NEGATIVE )
2176                                                 {
2177                                                         luxel[ 0 ] -= averageColor[ 0 ] / samples;
2178                                                         luxel[ 1 ] -= averageColor[ 1 ] / samples;
2179                                                         luxel[ 2 ] -= averageColor[ 2 ] / samples;
2180                                                 }
2181
2182                                                 /* handle normal light */
2183                                                 else
2184                                                 {
2185                                                         luxel[ 0 ] += averageColor[ 0 ] / samples;
2186                                                         luxel[ 1 ] += averageColor[ 1 ] / samples;
2187                                                         luxel[ 2 ] += averageColor[ 2 ] / samples;
2188                                                 }
2189                                         }
2190
2191                                         /* single sample */
2192                                         else
2193                                         {
2194                                                 /* get particulars */
2195                                                 lightLuxel = LIGHT_LUXEL( x, y );
2196                                                 luxel = SUPER_LUXEL( lightmapNum, x, y );
2197
2198                                                 /* handle negative light */
2199                                                 if( trace.light->flags & LIGHT_NEGATIVE )
2200                                                         VectorScale( averageColor, -1.0f, averageColor );
2201
2202                                                 /* add color */
2203                                                 luxel[ 3 ] = 1.0f;
2204
2205                                                 /* handle negative light */
2206                                                 if( trace.light->flags & LIGHT_NEGATIVE )
2207                                                         VectorSubtract( luxel, lightLuxel, luxel );
2208
2209                                                 /* handle normal light */
2210                                                 else
2211                                                         VectorAdd( luxel, lightLuxel, luxel );
2212                                         }
2213                                 }
2214                         }
2215                 }
2216
2217                 /* free temporary luxels */
2218                 if( lightLuxels != stackLightLuxels )
2219                         free( lightLuxels );
2220         }
2221
2222         /* free light list */
2223         FreeTraceLights( &trace );
2224
2225         /*      -----------------------------------------------------------------
2226                 dirt pass
2227                 ----------------------------------------------------------------- */
2228
2229         if( dirty )
2230         {
2231                 /* walk lightmaps */
2232                 for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
2233                 {
2234                         /* early out */
2235                         if( lm->superLuxels[ lightmapNum ] == NULL )
2236                                 continue;
2237
2238                         /* apply dirt to each luxel */
2239                         for( y = 0; y < lm->sh; y++ )
2240                         {
2241                                 for( x = 0; x < lm->sw; x++ )
2242                                 {
2243                                         /* get cluster */
2244                                         cluster = SUPER_CLUSTER( x, y );
2245                                         //%     if( *cluster < 0 )
2246                                         //%             continue;
2247
2248                                         /* get particulars */
2249                                         luxel = SUPER_LUXEL( lightmapNum, x, y );
2250                                         dirt = SUPER_DIRT( x, y );
2251
2252                                         /* apply dirt */
2253                                         VectorScale( luxel, *dirt, luxel );
2254
2255                                         /* debugging */
2256                                         if( dirtDebug )
2257                                                 VectorSet( luxel, *dirt * 255.0f, *dirt * 255.0f, *dirt * 255.0f );
2258                                 }
2259                         }
2260                 }
2261         }
2262
2263         /* -----------------------------------------------------------------
2264            filter pass
2265            ----------------------------------------------------------------- */
2266
2267         /* walk lightmaps */
2268         for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
2269         {
2270                 /* early out */
2271                 if( lm->superLuxels[ lightmapNum ] == NULL )
2272                         continue;
2273
2274                 /* average occluded luxels from neighbors */
2275                 for( y = 0; y < lm->sh; y++ )
2276                 {
2277                         for( x = 0; x < lm->sw; x++ )
2278                         {
2279                                 /* get particulars */
2280                                 cluster = SUPER_CLUSTER( x, y );
2281                                 luxel = SUPER_LUXEL( lightmapNum, x, y );
2282                                 deluxel = SUPER_DELUXEL( x, y );
2283                                 normal = SUPER_NORMAL( x, y );
2284
2285                                 /* determine if filtering is necessary */
2286                                 filterColor = qfalse;
2287                                 filterDir = qfalse;
2288                                 if( *cluster < 0 ||
2289                                         (lm->splotchFix && (luxel[ 0 ] <= ambientColor[ 0 ] || luxel[ 1 ] <= ambientColor[ 1 ] || luxel[ 2 ] <= ambientColor[ 2 ])) )
2290                                         filterColor = qtrue;
2291                                 if( deluxemap && lightmapNum == 0 && (*cluster < 0 || filter) )
2292                                         filterDir = qtrue;
2293
2294                                 if( !filterColor && !filterDir )
2295                                         continue;
2296
2297                                 /* choose seed amount */
2298                                 VectorClear( averageColor );
2299                                 VectorClear( averageDir );
2300                                 samples = 0.0f;
2301
2302                                 /* walk 3x3 matrix */
2303                                 for( sy = (y - 1); sy <= (y + 1); sy++ )
2304                                 {
2305                                         if( sy < 0 || sy >= lm->sh )
2306                                                 continue;
2307
2308                                         for( sx = (x - 1); sx <= (x + 1); sx++ )
2309                                         {
2310                                                 if( sx < 0 || sx >= lm->sw || (sx == x && sy == y) )
2311                                                         continue;
2312
2313                                                 /* get neighbor's particulars */
2314                                                 cluster2 = SUPER_CLUSTER( sx, sy );
2315                                                 luxel2 = SUPER_LUXEL( lightmapNum, sx, sy );
2316                                                 deluxel2 = SUPER_DELUXEL( sx, sy );
2317
2318                                                 /* ignore unmapped/unlit luxels */
2319                                                 if( *cluster2 < 0 || luxel2[ 3 ] == 0.0f ||
2320                                                         (lm->splotchFix && VectorCompare( luxel2, ambientColor )) )
2321                                                         continue;
2322
2323                                                 /* add its distinctiveness to our own */
2324                                                 VectorAdd( averageColor, luxel2, averageColor );
2325                                                 samples += luxel2[ 3 ];
2326                                                 if( filterDir )
2327                                                         VectorAdd( averageDir, deluxel2, averageDir );
2328                                         }
2329                                 }
2330
2331                                 /* fall through */
2332                                 if( samples <= 0.0f )
2333                                         continue;
2334
2335                                 /* dark lightmap seams */
2336                                 if( dark )
2337                                 {
2338                                         if( lightmapNum == 0 )
2339                                                 VectorMA( averageColor, 2.0f, ambientColor, averageColor );
2340                                         samples += 2.0f;
2341                                 }
2342
2343                                 /* average it */
2344                                 if( filterColor )
2345                                 {
2346                                         VectorDivide( averageColor, samples, luxel );
2347                                         luxel[ 3 ] = 1.0f;
2348                                 }
2349                                 if( filterDir )
2350                                         VectorDivide( averageDir, samples, deluxel );
2351
2352                                 /* set cluster to -3 */
2353                                 if( *cluster < 0 )
2354                                         *cluster = CLUSTER_FLOODED;
2355                         }
2356                 }
2357         }
2358 }
2359
2360
2361
2362 /*
2363 IlluminateVertexes()
2364 light the surface vertexes
2365 */
2366
2367 #define VERTEX_NUDGE    4.0f
2368
2369 void IlluminateVertexes( int num )
2370 {
2371         int                                     i, x, y, z, x1, y1, z1, sx, sy, radius, maxRadius, *cluster;
2372         int                                     lightmapNum, numAvg;
2373         float                           samples, *vertLuxel, *radVertLuxel, *luxel, dirt;
2374         vec3_t                          origin, temp, temp2, colors[ MAX_LIGHTMAPS ], avgColors[ MAX_LIGHTMAPS ];
2375         bspDrawSurface_t        *ds;
2376         surfaceInfo_t           *info;
2377         rawLightmap_t           *lm;
2378         bspDrawVert_t           *verts;
2379         trace_t                         trace;
2380
2381
2382         /* get surface, info, and raw lightmap */
2383         ds = &bspDrawSurfaces[ num ];
2384         info = &surfaceInfos[ num ];
2385         lm = info->lm;
2386
2387         /* -----------------------------------------------------------------
2388            illuminate the vertexes
2389            ----------------------------------------------------------------- */
2390
2391         /* calculate vertex lighting for surfaces without lightmaps */
2392         if( lm == NULL || cpmaHack )
2393         {
2394                 /* setup trace */
2395                 trace.testOcclusion = (cpmaHack && lm != NULL) ? qfalse : !noTrace;
2396                 trace.forceSunlight = info->si->forceSunlight;
2397                 trace.recvShadows = info->recvShadows;
2398                 trace.numSurfaces = 1;
2399                 trace.surfaces = &num;
2400                 trace.inhibitRadius = DEFAULT_INHIBIT_RADIUS;
2401
2402                 /* twosided lighting */
2403                 trace.twoSided = info->si->twoSided;
2404
2405                 /* make light list for this surface */
2406                 CreateTraceLightsForSurface( num, &trace );
2407
2408                 /* setup */
2409                 verts = yDrawVerts + ds->firstVert;
2410                 numAvg = 0;
2411                 memset( avgColors, 0, sizeof( avgColors ) );
2412
2413                 /* walk the surface verts */
2414                 for( i = 0; i < ds->numVerts; i++ )
2415                 {
2416                         /* get vertex luxel */
2417                         radVertLuxel = RAD_VERTEX_LUXEL( 0, ds->firstVert + i );
2418
2419                         /* color the luxel with raw lightmap num? */
2420                         if( debugSurfaces )
2421                                 VectorCopy( debugColors[ num % 12 ], radVertLuxel );
2422
2423                         /* color the luxel with luxel origin? */
2424                         else if( debugOrigin )
2425                         {
2426                                 VectorSubtract( info->maxs, info->mins, temp );
2427                                 VectorScale( temp, (1.0f / 255.0f), temp );
2428                                 VectorSubtract( origin, lm->mins, temp2 );
2429                                 radVertLuxel[ 0 ] = info->mins[ 0 ] + (temp[ 0 ] * temp2[ 0 ]);
2430                                 radVertLuxel[ 1 ] = info->mins[ 1 ] + (temp[ 1 ] * temp2[ 1 ]);
2431                                 radVertLuxel[ 2 ] = info->mins[ 2 ] + (temp[ 2 ] * temp2[ 2 ]);
2432                         }
2433
2434                         /* color the luxel with the normal */
2435                         else if( normalmap )
2436                         {
2437                                 radVertLuxel[ 0 ] = (verts[ i ].normal[ 0 ] + 1.0f) * 127.5f;
2438                                 radVertLuxel[ 1 ] = (verts[ i ].normal[ 1 ] + 1.0f) * 127.5f;
2439                                 radVertLuxel[ 2 ] = (verts[ i ].normal[ 2 ] + 1.0f) * 127.5f;
2440                         }
2441
2442                         /* illuminate the vertex */
2443                         else
2444                         {
2445                                 /* clear vertex luxel */
2446                                 VectorSet( radVertLuxel, -1.0f, -1.0f, -1.0f );
2447
2448                                 /* try at initial origin */
2449                                 trace.cluster = ClusterForPointExtFilter( verts[ i ].xyz, VERTEX_EPSILON, info->numSurfaceClusters, &surfaceClusters[ info->firstSurfaceCluster ] );
2450                                 if( trace.cluster >= 0 )
2451                                 {
2452                                         /* setup trace */
2453                                         VectorCopy( verts[ i ].xyz, trace.origin );
2454                                         VectorCopy( verts[ i ].normal, trace.normal );
2455
2456                                         /* r7 dirt */
2457                                         if( dirty )
2458                                                 dirt = DirtForSample( &trace );
2459                                         else
2460                                                 dirt = 1.0f;
2461
2462                                         /* trace */
2463                                         LightingAtSample( &trace, ds->vertexStyles, colors );
2464
2465                                         /* store */
2466                                         for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
2467                                         {
2468                                                 /* r7 dirt */
2469                                                 VectorScale( colors[ lightmapNum ], dirt, colors[ lightmapNum ] );
2470
2471                                                 /* store */
2472                                                 radVertLuxel = RAD_VERTEX_LUXEL( lightmapNum, ds->firstVert + i );
2473                                                 VectorCopy( colors[ lightmapNum ], radVertLuxel );
2474                                                 VectorAdd( avgColors[ lightmapNum ], colors[ lightmapNum ], colors[ lightmapNum ] );
2475                                         }
2476                                 }
2477
2478                                 /* is this sample bright enough? */
2479                                 radVertLuxel = RAD_VERTEX_LUXEL( 0, ds->firstVert + i );
2480                                 if( radVertLuxel[ 0 ] <= ambientColor[ 0 ] &&
2481                                         radVertLuxel[ 1 ] <= ambientColor[ 1 ] &&
2482                                         radVertLuxel[ 2 ] <= ambientColor[ 2 ] )
2483                                 {
2484                                         /* nudge the sample point around a bit */
2485                                         for( x = 0; x < 4; x++ )
2486                                         {
2487                                                 /* two's complement 0, 1, -1, 2, -2, etc */
2488                                                 x1 = ((x >> 1) ^ (x & 1 ? -1 : 0)) + (x & 1);
2489
2490                                                 for( y = 0; y < 4; y++ )
2491                                                 {
2492                                                         y1 = ((y >> 1) ^ (y & 1 ? -1 : 0)) + (y & 1);
2493
2494                                                         for( z = 0; z < 4; z++ )
2495                                                         {
2496                                                                 z1 = ((z >> 1) ^ (z & 1 ? -1 : 0)) + (z & 1);
2497
2498                                                                 /* nudge origin */
2499                                                                 trace.origin[ 0 ] = verts[ i ].xyz[ 0 ] + (VERTEX_NUDGE * x1);
2500                                                                 trace.origin[ 1 ] = verts[ i ].xyz[ 1 ] + (VERTEX_NUDGE * y1);
2501                                                                 trace.origin[ 2 ] = verts[ i ].xyz[ 2 ] + (VERTEX_NUDGE * z1);
2502
2503                                                                 /* try at nudged origin */
2504                                                                 trace.cluster = ClusterForPointExtFilter( origin, VERTEX_EPSILON, info->numSurfaceClusters, &surfaceClusters[ info->firstSurfaceCluster ] );
2505                                                                 if( trace.cluster < 0 )
2506                                                                         continue;
2507
2508                                                                 /* trace */
2509                                                                 LightingAtSample( &trace, ds->vertexStyles, colors );
2510
2511                                                                 /* store */
2512                                                                 for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
2513                                                                 {
2514                                                                         /* r7 dirt */
2515                                                                         VectorScale( colors[ lightmapNum ], dirt, colors[ lightmapNum ] );
2516
2517                                                                         /* store */
2518                                                                         radVertLuxel = RAD_VERTEX_LUXEL( lightmapNum, ds->firstVert + i );
2519                                                                         VectorCopy( colors[ lightmapNum ], radVertLuxel );
2520                                                                 }
2521
2522                                                                 /* bright enough? */
2523                                                                 radVertLuxel = RAD_VERTEX_LUXEL( 0, ds->firstVert + i );
2524                                                                 if( radVertLuxel[ 0 ] > ambientColor[ 0 ] ||
2525                                                                         radVertLuxel[ 1 ] > ambientColor[ 1 ] ||
2526                                                                         radVertLuxel[ 2 ] > ambientColor[ 2 ] )
2527                                                                         x = y = z = 1000;
2528                                                         }
2529                                                 }
2530                                         }
2531                                 }
2532
2533                                 /* add to average? */
2534                                 radVertLuxel = RAD_VERTEX_LUXEL( 0, ds->firstVert + i );
2535                                 if( radVertLuxel[ 0 ] > ambientColor[ 0 ] ||
2536                                         radVertLuxel[ 1 ] > ambientColor[ 1 ] ||
2537                                         radVertLuxel[ 2 ] > ambientColor[ 2 ] )
2538                                 {
2539                                         numAvg++;
2540                                         for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
2541                                         {
2542                                                 radVertLuxel = RAD_VERTEX_LUXEL( lightmapNum, ds->firstVert + i );
2543                                                 VectorAdd( avgColors[ lightmapNum ], radVertLuxel, avgColors[ lightmapNum ] );
2544                                         }
2545                                 }
2546                         }
2547
2548                         /* another happy customer */
2549                         numVertsIlluminated++;
2550                 }
2551
2552                 /* set average color */
2553                 if( numAvg > 0 )
2554                 {
2555                         for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
2556                                 VectorScale( avgColors[ lightmapNum ], (1.0f / numAvg), avgColors[ lightmapNum ] );
2557                 }
2558                 else
2559                 {
2560                         VectorCopy( ambientColor, avgColors[ 0 ] );
2561                 }
2562
2563                 /* clean up and store vertex color */
2564                 for( i = 0; i < ds->numVerts; i++ )
2565                 {
2566                         /* get vertex luxel */
2567                         radVertLuxel = RAD_VERTEX_LUXEL( 0, ds->firstVert + i );
2568
2569                         /* store average in occluded vertexes */
2570                         if( radVertLuxel[ 0 ] < 0.0f )
2571                         {
2572                                 for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
2573                                 {
2574                                         radVertLuxel = RAD_VERTEX_LUXEL( lightmapNum, ds->firstVert + i );
2575                                         VectorCopy( avgColors[ lightmapNum ], radVertLuxel );
2576
2577                                         /* debug code */
2578                                         //%     VectorSet( radVertLuxel, 255.0f, 0.0f, 0.0f );
2579                                 }
2580                         }
2581
2582                         /* store it */
2583                         for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
2584                         {
2585                                 /* get luxels */
2586                                 vertLuxel = VERTEX_LUXEL( lightmapNum, ds->firstVert + i );
2587                                 radVertLuxel = RAD_VERTEX_LUXEL( lightmapNum, ds->firstVert + i );
2588
2589                                 /* store */
2590                                 if( bouncing || bounce == 0 || !bounceOnly )
2591                                         VectorAdd( vertLuxel, radVertLuxel, vertLuxel );
2592                                 if( !info->si->noVertexLight )
2593                                         ColorToBytes( vertLuxel, verts[ i ].color[ lightmapNum ], info->si->vertexScale );
2594                         }
2595                 }
2596
2597                 /* free light list */
2598                 FreeTraceLights( &trace );
2599
2600                 /* return to sender */
2601                 return;
2602         }
2603
2604         /* -----------------------------------------------------------------
2605            reconstitute vertex lighting from the luxels
2606            ----------------------------------------------------------------- */
2607
2608         /* set styles from lightmap */
2609         for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
2610                 ds->vertexStyles[ lightmapNum ] = lm->styles[ lightmapNum ];
2611
2612         /* get max search radius */
2613         maxRadius = lm->sw;
2614         maxRadius = maxRadius > lm->sh ? maxRadius : lm->sh;
2615
2616         /* walk the surface verts */
2617         verts = yDrawVerts + ds->firstVert;
2618         for( i = 0; i < ds->numVerts; i++ )
2619         {
2620                 /* do each lightmap */
2621                 for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
2622                 {
2623                         /* early out */
2624                         if( lm->superLuxels[ lightmapNum ] == NULL )
2625                                 continue;
2626
2627                         /* get luxel coords */
2628                         x = verts[ i ].lightmap[ lightmapNum ][ 0 ];
2629                         y = verts[ i ].lightmap[ lightmapNum ][ 1 ];
2630                         if( x < 0 )
2631                                 x = 0;
2632                         else if( x >= lm->sw )
2633                                 x = lm->sw - 1;
2634                         if( y < 0 )
2635                                 y = 0;
2636                         else if( y >= lm->sh )
2637                                 y = lm->sh - 1;
2638
2639                         /* get vertex luxels */
2640                         vertLuxel = VERTEX_LUXEL( lightmapNum, ds->firstVert + i );
2641                         radVertLuxel = RAD_VERTEX_LUXEL( lightmapNum, ds->firstVert + i );
2642
2643                         /* color the luxel with the normal? */
2644                         if( normalmap )
2645                         {
2646                                 radVertLuxel[ 0 ] = (verts[ i ].normal[ 0 ] + 1.0f) * 127.5f;
2647                                 radVertLuxel[ 1 ] = (verts[ i ].normal[ 1 ] + 1.0f) * 127.5f;
2648                                 radVertLuxel[ 2 ] = (verts[ i ].normal[ 2 ] + 1.0f) * 127.5f;
2649                         }
2650
2651                         /* color the luxel with surface num? */
2652                         else if( debugSurfaces )
2653                                 VectorCopy( debugColors[ num % 12 ], radVertLuxel );
2654
2655                         /* divine color from the superluxels */
2656                         else
2657                         {
2658                                 /* increasing radius */
2659                                 VectorClear( radVertLuxel );
2660                                 samples = 0.0f;
2661                                 for( radius = 0; radius < maxRadius && samples <= 0.0f; radius++ )
2662                                 {
2663                                         /* sample within radius */
2664                                         for( sy = (y - radius); sy <= (y + radius); sy++ )
2665                                         {
2666                                                 if( sy < 0 || sy >= lm->sh )
2667                                                         continue;
2668
2669                                                 for( sx = (x - radius); sx <= (x + radius); sx++ )
2670                                                 {
2671                                                         if( sx < 0 || sx >= lm->sw )
2672                                                                 continue;
2673
2674                                                         /* get luxel particulars */
2675                                                         luxel = SUPER_LUXEL( lightmapNum, sx, sy );
2676                                                         cluster = SUPER_CLUSTER( sx, sy );
2677                                                         if( *cluster < 0 )
2678                                                                 continue;
2679
2680                                                         /* testing: must be brigher than ambient color */
2681                                                         //%     if( luxel[ 0 ] <= ambientColor[ 0 ] || luxel[ 1 ] <= ambientColor[ 1 ] || luxel[ 2 ] <= ambientColor[ 2 ] )
2682                                                         //%             continue;
2683
2684                                                         /* add its distinctiveness to our own */
2685                                                         VectorAdd( radVertLuxel, luxel, radVertLuxel );
2686                                                         samples += luxel[ 3 ];
2687                                                 }
2688                                         }
2689                                 }
2690
2691                                 /* any color? */
2692                                 if( samples > 0.0f )
2693                                         VectorDivide( radVertLuxel, samples, radVertLuxel );
2694                                 else
2695                                         VectorCopy( ambientColor, radVertLuxel );
2696                         }
2697
2698                         /* store into floating point storage */
2699                         VectorAdd( vertLuxel, radVertLuxel, vertLuxel );
2700                         numVertsIlluminated++;
2701
2702                         /* store into bytes (for vertex approximation) */
2703                         if( !info->si->noVertexLight )
2704                                 ColorToBytes( vertLuxel, verts[ i ].color[ lightmapNum ], 1.0f );
2705                 }
2706         }
2707 }
2708
2709
2710
2711 /* -------------------------------------------------------------------------------
2712
2713 light optimization (-fast)
2714
2715 creates a list of lights that will affect a surface and stores it in tw
2716 this is to optimize surface lighting by culling out as many of the
2717 lights in the world as possible from further calculation
2718
2719 ------------------------------------------------------------------------------- */
2720
2721 /*
2722 SetupBrushes()
2723 determines opaque brushes in the world and find sky shaders for sunlight calculations
2724 */
2725
2726 void SetupBrushes( void )
2727 {
2728         int                             i, j, b, compileFlags;
2729         qboolean                inside;
2730         bspBrush_t              *brush;
2731         bspBrushSide_t  *side;
2732         bspShader_t             *shader;
2733         shaderInfo_t    *si;
2734
2735
2736         /* note it */
2737         Sys_FPrintf( SYS_VRB, "--- SetupBrushes ---\n" );
2738
2739         /* allocate */
2740         if( opaqueBrushes == NULL )
2741                 opaqueBrushes = safe_malloc( numBSPBrushes / 8 + 1 );
2742
2743         /* clear */
2744         memset( opaqueBrushes, 0, numBSPBrushes / 8 + 1 );
2745         numOpaqueBrushes = 0;
2746
2747         /* walk the list of worldspawn brushes */
2748         for( i = 0; i < bspModels[ 0 ].numBSPBrushes; i++ )
2749         {
2750                 /* get brush */
2751                 b = bspModels[ 0 ].firstBSPBrush + i;
2752                 brush = &bspBrushes[ b ];
2753
2754                 /* check all sides */
2755                 inside = qtrue;
2756                 compileFlags = 0;
2757                 for( j = 0; j < brush->numSides && inside; j++ )
2758                 {
2759                         /* do bsp shader calculations */
2760                         side = &bspBrushSides[ brush->firstSide + j ];
2761                         shader = &bspShaders[ side->shaderNum ];
2762
2763                         /* get shader info */
2764                         si = ShaderInfoForShader( shader->shader );
2765                         if( si == NULL )
2766                                 continue;
2767
2768                         /* or together compile flags */
2769                         compileFlags |= si->compileFlags;
2770                 }
2771
2772                 /* determine if this brush is opaque to light */
2773                 if( !(compileFlags & C_TRANSLUCENT) )
2774                 {
2775                         opaqueBrushes[ b >> 3 ] |= (1 << (b & 7));
2776                         numOpaqueBrushes++;
2777                         maxOpaqueBrush = i;
2778                 }
2779         }
2780
2781         /* emit some statistics */
2782         Sys_FPrintf( SYS_VRB, "%9d opaque brushes\n", numOpaqueBrushes );
2783 }
2784
2785
2786
2787 /*
2788 ClusterVisible()
2789 determines if two clusters are visible to each other using the PVS
2790 */
2791
2792 qboolean ClusterVisible( int a, int b )
2793 {
2794         int                     portalClusters, leafBytes;
2795         byte            *pvs;
2796
2797
2798         /* dummy check */
2799         if( a < 0 || b < 0 )
2800                 return qfalse;
2801
2802         /* early out */
2803         if( a == b )
2804                 return qtrue;
2805
2806         /* not vised? */
2807         if( numBSPVisBytes <=8 )
2808                 return qtrue;
2809
2810         /* get pvs data */
2811         portalClusters = ((int *) bspVisBytes)[ 0 ];
2812         leafBytes = ((int*) bspVisBytes)[ 1 ];
2813         pvs = bspVisBytes + VIS_HEADER_SIZE + (a * leafBytes);
2814
2815         /* check */
2816         if( (pvs[ b >> 3 ] & (1 << (b & 7))) )
2817                 return qtrue;
2818         return qfalse;
2819 }
2820
2821
2822
2823 /*
2824 PointInLeafNum_r()
2825 borrowed from vlight.c
2826 */
2827
2828 int     PointInLeafNum_r( vec3_t point, int nodenum )
2829 {
2830         int                     leafnum;
2831         vec_t           dist;
2832         bspNode_t               *node;
2833         bspPlane_t      *plane;
2834
2835
2836         while( nodenum >= 0 )
2837         {
2838                 node = &bspNodes[ nodenum ];
2839                 plane = &bspPlanes[ node->planeNum ];
2840                 dist = DotProduct( point, plane->normal ) - plane->dist;
2841                 if( dist > 0.1 )
2842                         nodenum = node->children[ 0 ];
2843                 else if( dist < -0.1 )
2844                         nodenum = node->children[ 1 ];
2845                 else
2846                 {
2847                         leafnum = PointInLeafNum_r( point, node->children[ 0 ] );
2848                         if( bspLeafs[ leafnum ].cluster != -1 )
2849                                 return leafnum;
2850                         nodenum = node->children[ 1 ];
2851                 }
2852         }
2853
2854         leafnum = -nodenum - 1;
2855         return leafnum;
2856 }
2857
2858
2859
2860 /*
2861 PointInLeafnum()
2862 borrowed from vlight.c
2863 */
2864
2865 int     PointInLeafNum( vec3_t point )
2866 {
2867         return PointInLeafNum_r( point, 0 );
2868 }
2869
2870
2871
2872 /*
2873 ClusterVisibleToPoint() - ydnar
2874 returns qtrue if point can "see" cluster
2875 */
2876
2877 qboolean ClusterVisibleToPoint( vec3_t point, int cluster )
2878 {
2879         int             pointCluster;
2880
2881
2882         /* get leafNum for point */
2883         pointCluster = ClusterForPoint( point );
2884         if( pointCluster < 0 )
2885                 return qfalse;
2886
2887         /* check pvs */
2888         return ClusterVisible( pointCluster, cluster );
2889 }
2890
2891
2892
2893 /*
2894 ClusterForPoint() - ydnar
2895 returns the pvs cluster for point
2896 */
2897
2898 int ClusterForPoint( vec3_t point )
2899 {
2900         int             leafNum;
2901
2902
2903         /* get leafNum for point */
2904         leafNum = PointInLeafNum( point );
2905         if( leafNum < 0 )
2906                 return -1;
2907
2908         /* return the cluster */
2909         return bspLeafs[ leafNum ].cluster;
2910 }
2911
2912
2913
2914 /*
2915 ClusterForPointExt() - ydnar
2916 also takes brushes into account for occlusion testing
2917 */
2918
2919 int ClusterForPointExt( vec3_t point, float epsilon )
2920 {
2921         int                             i, j, b, leafNum, cluster;
2922         float                   dot;
2923         qboolean                inside;
2924         int                             *brushes, numBSPBrushes;
2925         bspLeaf_t               *leaf;
2926         bspBrush_t              *brush;
2927         bspPlane_t              *plane;
2928
2929
2930         /* get leaf for point */
2931         leafNum = PointInLeafNum( point );
2932         if( leafNum < 0 )
2933                 return -1;
2934         leaf = &bspLeafs[ leafNum ];
2935
2936         /* get the cluster */
2937         cluster = leaf->cluster;
2938         if( cluster < 0 )
2939                 return -1;
2940
2941         /* transparent leaf, so check point against all brushes in the leaf */
2942         brushes = &bspLeafBrushes[ leaf->firstBSPLeafBrush ];
2943         numBSPBrushes = leaf->numBSPLeafBrushes;
2944         for( i = 0; i < numBSPBrushes; i++ )
2945         {
2946                 /* get parts */
2947                 b = brushes[ i ];
2948                 if( b > maxOpaqueBrush )
2949                         continue;
2950                 brush = &bspBrushes[ b ];
2951                 if( !(opaqueBrushes[ b >> 3 ] & (1 << (b & 7))) )
2952                         continue;
2953
2954                 /* check point against all planes */
2955                 inside = qtrue;
2956                 for( j = 0; j < brush->numSides && inside; j++ )
2957                 {
2958                         plane = &bspPlanes[ bspBrushSides[ brush->firstSide + j ].planeNum ];
2959                         dot = DotProduct( point, plane->normal );
2960                         dot -= plane->dist;
2961                         if( dot > epsilon )
2962                                 inside = qfalse;
2963                 }
2964
2965                 /* if inside, return bogus cluster */
2966                 if( inside )
2967                         return -1 - b;
2968         }
2969
2970         /* if the point made it this far, it's not inside any opaque brushes */
2971         return cluster;
2972 }
2973
2974
2975
2976 /*
2977 ClusterForPointExtFilter() - ydnar
2978 adds cluster checking against a list of known valid clusters
2979 */
2980
2981 int ClusterForPointExtFilter( vec3_t point, float epsilon, int numClusters, int *clusters )
2982 {
2983         int             i, cluster;
2984
2985
2986         /* get cluster for point */
2987         cluster = ClusterForPointExt( point, epsilon );
2988
2989         /* check if filtering is necessary */
2990         if( cluster < 0 || numClusters <= 0 || clusters == NULL )
2991                 return cluster;
2992
2993         /* filter */
2994         for( i = 0; i < numClusters; i++ )
2995         {
2996                 if( cluster == clusters[ i ] || ClusterVisible( cluster, clusters[ i ] ) )
2997                         return cluster;
2998         }
2999
3000         /* failed */
3001         return -1;
3002 }
3003
3004
3005
3006 /*
3007 ShaderForPointInLeaf() - ydnar
3008 checks a point against all brushes in a leaf, returning the shader of the brush
3009 also sets the cumulative surface and content flags for the brush hit
3010 */
3011
3012 int ShaderForPointInLeaf( vec3_t point, int leafNum, float epsilon, int wantContentFlags, int wantSurfaceFlags, int *contentFlags, int *surfaceFlags )
3013 {
3014         int                             i, j;
3015         float                   dot;
3016         qboolean                inside;
3017         int                             *brushes, numBSPBrushes;
3018         bspLeaf_t                       *leaf;
3019         bspBrush_t              *brush;
3020         bspBrushSide_t  *side;
3021         bspPlane_t              *plane;
3022         bspShader_t             *shader;
3023         int                             allSurfaceFlags, allContentFlags;
3024
3025
3026         /* clear things out first */
3027         *surfaceFlags = 0;
3028         *contentFlags = 0;
3029
3030         /* get leaf */
3031         if( leafNum < 0 )
3032                 return -1;
3033         leaf = &bspLeafs[ leafNum ];
3034
3035         /* transparent leaf, so check point against all brushes in the leaf */
3036         brushes = &bspLeafBrushes[ leaf->firstBSPLeafBrush ];
3037         numBSPBrushes = leaf->numBSPLeafBrushes;
3038         for( i = 0; i < numBSPBrushes; i++ )
3039         {
3040                 /* get parts */
3041                 brush = &bspBrushes[ brushes[ i ] ];
3042
3043                 /* check point against all planes */
3044                 inside = qtrue;
3045                 allSurfaceFlags = 0;
3046                 allContentFlags = 0;
3047                 for( j = 0; j < brush->numSides && inside; j++ )
3048                 {
3049                         side = &bspBrushSides[ brush->firstSide + j ];
3050                         plane = &bspPlanes[ side->planeNum ];
3051                         dot = DotProduct( point, plane->normal );
3052                         dot -= plane->dist;
3053                         if( dot > epsilon )
3054                                 inside = qfalse;
3055                         else
3056                         {
3057                                 shader = &bspShaders[ side->shaderNum ];
3058                                 allSurfaceFlags |= shader->surfaceFlags;
3059                                 allContentFlags |= shader->contentFlags;
3060                         }
3061                 }
3062
3063                 /* handle if inside */
3064                 if( inside )
3065                 {
3066                         /* if there are desired flags, check for same and continue if they aren't matched */
3067                         if( wantContentFlags && !(wantContentFlags & allContentFlags) )
3068                                 continue;
3069                         if( wantSurfaceFlags && !(wantSurfaceFlags & allSurfaceFlags) )
3070                                 continue;
3071
3072                         /* store the cumulative flags and return the brush shader (which is mostly useless) */
3073                         *surfaceFlags = allSurfaceFlags;
3074                         *contentFlags = allContentFlags;
3075                         return brush->shaderNum;
3076                 }
3077         }
3078
3079         /* if the point made it this far, it's not inside any brushes */
3080         return -1;
3081 }
3082
3083
3084
3085 /*
3086 ChopBounds()
3087 chops a bounding box by the plane defined by origin and normal
3088 returns qfalse if the bounds is entirely clipped away
3089
3090 this is not exactly the fastest way to do this...
3091 */
3092
3093 qboolean ChopBounds( vec3_t mins, vec3_t maxs, vec3_t origin, vec3_t normal )
3094 {
3095         /* FIXME: rewrite this so it doesn't use bloody brushes */
3096         return qtrue;
3097 }
3098
3099
3100
3101 /*
3102 SetupEnvelopes()
3103 calculates each light's effective envelope,
3104 taking into account brightness, type, and pvs.
3105 */
3106
3107 #define LIGHT_EPSILON   0.125f
3108 #define LIGHT_NUDGE             2.0f
3109
3110 void SetupEnvelopes( qboolean forGrid, qboolean fastFlag )
3111 {
3112         int                     i, x, y, z, x1, y1, z1;
3113         light_t         *light, *light2, **owner;
3114         bspLeaf_t       *leaf;
3115         vec3_t          origin, dir, mins, maxs, nullVector = { 0, 0, 0 };
3116         float           radius, intensity;
3117         light_t         *buckets[ 256 ];
3118
3119
3120         /* early out for weird cases where there are no lights */
3121         if( lights == NULL )
3122                 return;
3123
3124         /* note it */
3125         Sys_FPrintf( SYS_VRB, "--- SetupEnvelopes%s ---\n", fastFlag ? " (fast)" : "" );
3126
3127         /* count lights */
3128         numLights = 0;
3129         numCulledLights = 0;
3130         owner = &lights;
3131         while( *owner != NULL )
3132         {
3133                 /* get light */
3134                 light = *owner;
3135
3136                 /* handle negative lights */
3137                 if( light->photons < 0.0f || light->add < 0.0f )
3138                 {
3139                         light->photons *= -1.0f;
3140                         light->add *= -1.0f;
3141                         light->flags |= LIGHT_NEGATIVE;
3142                 }
3143
3144                 /* sunlight? */
3145                 if( light->type == EMIT_SUN )
3146                 {
3147                         /* special cased */
3148                         light->cluster = 0;
3149                         light->envelope = MAX_WORLD_COORD * 8.0f;
3150                         VectorSet( light->mins, MIN_WORLD_COORD * 8.0f, MIN_WORLD_COORD * 8.0f, MIN_WORLD_COORD * 8.0f );
3151                         VectorSet( light->maxs, MAX_WORLD_COORD * 8.0f, MAX_WORLD_COORD * 8.0f, MAX_WORLD_COORD * 8.0f );
3152                 }
3153
3154                 /* everything else */
3155                 else
3156                 {
3157                         /* get pvs cluster for light */
3158                         light->cluster = ClusterForPointExt( light->origin, LIGHT_EPSILON );
3159
3160                         /* invalid cluster? */
3161                         if( light->cluster < 0 )
3162                         {
3163                                 /* nudge the sample point around a bit */
3164                                 for( x = 0; x < 4; x++ )
3165                                 {
3166                                         /* two's complement 0, 1, -1, 2, -2, etc */
3167                                         x1 = ((x >> 1) ^ (x & 1 ? -1 : 0)) + (x & 1);
3168
3169                                         for( y = 0; y < 4; y++ )
3170                                         {
3171                                                 y1 = ((y >> 1) ^ (y & 1 ? -1 : 0)) + (y & 1);
3172
3173                                                 for( z = 0; z < 4; z++ )
3174                                                 {
3175                                                         z1 = ((z >> 1) ^ (z & 1 ? -1 : 0)) + (z & 1);
3176
3177                                                         /* nudge origin */
3178                                                         origin[ 0 ] = light->origin[ 0 ] + (LIGHT_NUDGE * x1);
3179                                                         origin[ 1 ] = light->origin[ 1 ] + (LIGHT_NUDGE * y1);
3180                                                         origin[ 2 ] = light->origin[ 2 ] + (LIGHT_NUDGE * z1);
3181
3182                                                         /* try at nudged origin */
3183                                                         light->cluster = ClusterForPointExt( origin, LIGHT_EPSILON );
3184                                                         if( light->cluster < 0 )
3185                                                                 continue;
3186
3187                                                         /* set origin */
3188                                                         VectorCopy( origin, light->origin );
3189                                                 }
3190                                         }
3191                                 }
3192                         }
3193
3194                         /* only calculate for lights in pvs and outside of opaque brushes */
3195                         if( light->cluster >= 0 )
3196                         {
3197                                 /* set light fast flag */
3198                                 if( fastFlag )
3199                                         light->flags |= LIGHT_FAST_TEMP;
3200                                 else
3201                                         light->flags &= ~LIGHT_FAST_TEMP;
3202                                 if( light->si && light->si->noFast )
3203                                         light->flags &= ~(LIGHT_FAST | LIGHT_FAST_TEMP);
3204
3205                                 /* clear light envelope */
3206                                 light->envelope = 0;
3207
3208                                 /* handle area lights */
3209                                 if( exactPointToPolygon && light->type == EMIT_AREA && light->w != NULL )
3210                                 {
3211                                         /* ugly hack to calculate extent for area lights, but only done once */
3212                                         VectorScale( light->normal, -1.0f, dir );
3213                                         for( radius = 100.0f; radius < 130000.0f && light->envelope == 0; radius += 10.0f )
3214                                         {
3215                                                 float   factor;
3216
3217                                                 VectorMA( light->origin, radius, light->normal, origin );
3218                                                 factor = PointToPolygonFormFactor( origin, dir, light->w );
3219                                                 if( factor < 0.0f )
3220                                                         factor *= -1.0f;
3221                                                 if( (factor * light->add) <= light->falloffTolerance )
3222                                                         light->envelope = radius;
3223                                         }
3224
3225                                         /* check for fast mode */
3226                                         if( !(light->flags & LIGHT_FAST) && !(light->flags & LIGHT_FAST_TEMP) )
3227                                                 light->envelope = MAX_WORLD_COORD * 8.0f;
3228                                 }
3229                                 else
3230                                 {
3231                                         radius = 0.0f;
3232                                         intensity = light->photons;
3233                                 }
3234
3235                                 /* other calcs */
3236                                 if( light->envelope <= 0.0f )
3237                                 {
3238                                         /* solve distance for non-distance lights */
3239                                         if( !(light->flags & LIGHT_ATTEN_DISTANCE) )
3240                                                 light->envelope = MAX_WORLD_COORD * 8.0f;
3241
3242                                         /* solve distance for linear lights */
3243                                         else if( (light->flags & LIGHT_ATTEN_LINEAR ) )
3244                                                 //% light->envelope = ((intensity / light->falloffTolerance) * linearScale - 1 + radius) / light->fade;
3245                                                 light->envelope = ((intensity * linearScale) - light->falloffTolerance) / light->fade;
3246
3247                                                 /*
3248                                                 add = angle * light->photons * linearScale - (dist * light->fade);
3249                                                 T = (light->photons * linearScale) - (dist * light->fade);
3250                                                 T + (dist * light->fade) = (light->photons * linearScale);
3251                                                 dist * light->fade = (light->photons * linearScale) - T;
3252                                                 dist = ((light->photons * linearScale) - T) / light->fade;
3253                                                 */
3254
3255                                         /* solve for inverse square falloff */
3256                                         else
3257                                                 light->envelope = sqrt( intensity / light->falloffTolerance ) + radius;
3258
3259                                                 /*
3260                                                 add = light->photons / (dist * dist);
3261                                                 T = light->photons / (dist * dist);
3262                                                 T * (dist * dist) = light->photons;
3263                                                 dist = sqrt( light->photons / T );
3264                                                 */
3265                                 }
3266
3267                                 /* chop radius against pvs */
3268                                 {
3269                                         /* clear bounds */
3270                                         ClearBounds( mins, maxs );
3271
3272                                         /* check all leaves */
3273                                         for( i = 0; i < numBSPLeafs; i++ )
3274                                         {
3275                                                 /* get test leaf */
3276                                                 leaf = &bspLeafs[ i ];
3277
3278                                                 /* in pvs? */
3279                                                 if( leaf->cluster < 0 )
3280                                                         continue;
3281                                                 if( ClusterVisible( light->cluster, leaf->cluster ) == qfalse ) /* ydnar: thanks Arnout for exposing my stupid error (this never failed before) */
3282                                                         continue;
3283
3284                                                 /* add this leafs bbox to the bounds */
3285                                                 VectorCopy( leaf->mins, origin );
3286                                                 AddPointToBounds( origin, mins, maxs );
3287                                                 VectorCopy( leaf->maxs, origin );
3288                                                 AddPointToBounds( origin, mins, maxs );
3289                                         }
3290
3291                                         /* test to see if bounds encompass light */
3292                                         for( i = 0; i < 3; i++ )
3293                                         {
3294                                                 if( mins[ i ] > light->origin[ i ] || maxs[ i ] < light->origin[ i ] )
3295                                                 {
3296                                                         //% Sys_Printf( "WARNING: Light PVS bounds (%.0f, %.0f, %.0f) -> (%.0f, %.0f, %.0f)\ndo not encompass light %d (%f, %f, %f)\n",
3297                                                         //%     mins[ 0 ], mins[ 1 ], mins[ 2 ],
3298                                                         //%     maxs[ 0 ], maxs[ 1 ], maxs[ 2 ],
3299                                                         //%     numLights, light->origin[ 0 ], light->origin[ 1 ], light->origin[ 2 ] );
3300                                                         AddPointToBounds( light->origin, mins, maxs );
3301                                                 }
3302                                         }
3303
3304                                         /* chop the bounds by a plane for area lights and spotlights */
3305                                         if( light->type == EMIT_AREA || light->type == EMIT_SPOT )
3306                                                 ChopBounds( mins, maxs, light->origin, light->normal );
3307
3308                                         /* copy bounds */
3309                                         VectorCopy( mins, light->mins );
3310                                         VectorCopy( maxs, light->maxs );
3311
3312                                         /* reflect bounds around light origin */
3313                                         //%     VectorMA( light->origin, -1.0f, origin, origin );
3314                                         VectorScale( light->origin, 2, origin );
3315                                         VectorSubtract( origin, maxs, origin );
3316                                         AddPointToBounds( origin, mins, maxs );
3317                                         //%     VectorMA( light->origin, -1.0f, mins, origin );
3318                                         VectorScale( light->origin, 2, origin );
3319                                         VectorSubtract( origin, mins, origin );
3320                                         AddPointToBounds( origin, mins, maxs );
3321
3322                                         /* calculate spherical bounds */
3323                                         VectorSubtract( maxs, light->origin, dir );
3324                                         radius = (float) VectorLength( dir );
3325
3326                                         /* if this radius is smaller than the envelope, then set the envelope to it */
3327                                         if( radius < light->envelope )
3328                                         {
3329                                                 light->envelope = radius;
3330                                                 //%     Sys_FPrintf( SYS_VRB, "PVS Cull (%d): culled\n", numLights );
3331                                         }
3332                                         //%     else
3333                                         //%             Sys_FPrintf( SYS_VRB, "PVS Cull (%d): failed (%8.0f > %8.0f)\n", numLights, radius, light->envelope );
3334                                 }
3335
3336                                 /* add grid/surface only check */
3337                                 if( forGrid )
3338                                 {
3339                                         if( !(light->flags & LIGHT_GRID) )
3340                                                 light->envelope = 0.0f;
3341                                 }
3342                                 else
3343                                 {
3344                                         if( !(light->flags & LIGHT_SURFACES) )
3345                                                 light->envelope = 0.0f;
3346                                 }
3347                         }
3348
3349                         /* culled? */
3350                         if( light->cluster < 0 || light->envelope <= 0.0f )
3351                         {
3352                                 /* debug code */
3353                                 //%     Sys_Printf( "Culling light: Cluster: %d Envelope: %f\n", light->cluster, light->envelope );
3354
3355                                 /* delete the light */
3356                                 numCulledLights++;
3357                                 *owner = light->next;
3358                                 if( light->w != NULL )
3359                                         free( light->w );
3360                                 free( light );
3361                                 continue;
3362                         }
3363                 }
3364
3365                 /* square envelope */
3366                 light->envelope2 = (light->envelope * light->envelope);
3367
3368                 /* increment light count */
3369                 numLights++;
3370
3371                 /* set next light */
3372                 owner = &((**owner).next);
3373         }
3374
3375         /* bucket sort lights by style */
3376         memset( buckets, 0, sizeof( buckets ) );
3377         light2 = NULL;
3378         for( light = lights; light != NULL; light = light2 )
3379         {
3380                 /* get next light */
3381                 light2 = light->next;
3382
3383                 /* filter into correct bucket */
3384                 light->next = buckets[ light->style ];
3385                 buckets[ light->style ] = light;
3386
3387                 /* if any styled light is present, automatically set nocollapse */
3388                 if( light->style != LS_NORMAL )
3389                         noCollapse = qtrue;
3390         }
3391
3392         /* filter back into light list */
3393         lights = NULL;
3394         for( i = 255; i >= 0; i-- )
3395         {
3396                 light2 = NULL;
3397                 for( light = buckets[ i ]; light != NULL; light = light2 )
3398                 {
3399                         light2 = light->next;
3400                         light->next = lights;
3401                         lights = light;
3402                 }
3403         }
3404
3405         /* emit some statistics */
3406         Sys_Printf( "%9d total lights\n", numLights );
3407         Sys_Printf( "%9d culled lights\n", numCulledLights );
3408 }
3409
3410
3411
3412 /*
3413 CreateTraceLightsForBounds()
3414 creates a list of lights that affect the given bounding box and pvs clusters (bsp leaves)
3415 */
3416
3417 void CreateTraceLightsForBounds( vec3_t mins, vec3_t maxs, vec3_t normal, int numClusters, int *clusters, int flags, trace_t *trace )
3418 {
3419         int                     i;
3420         light_t         *light;
3421         vec3_t          origin, dir, nullVector = { 0.0f, 0.0f, 0.0f };
3422         float           radius, dist, length;
3423
3424
3425         /* potential pre-setup  */
3426         if( numLights == 0 )
3427                 SetupEnvelopes( qfalse, fast );
3428
3429         /* debug code */
3430         //% Sys_Printf( "CTWLFB: (%4.1f %4.1f %4.1f) (%4.1f %4.1f %4.1f)\n", mins[ 0 ], mins[ 1 ], mins[ 2 ], maxs[ 0 ], maxs[ 1 ], maxs[ 2 ] );
3431
3432         /* allocate the light list */
3433         trace->lights = safe_malloc( sizeof( light_t* ) * (numLights + 1) );
3434         trace->numLights = 0;
3435
3436         /* calculate spherical bounds */
3437         VectorAdd( mins, maxs, origin );
3438         VectorScale( origin, 0.5f, origin );
3439         VectorSubtract( maxs, origin, dir );
3440         radius = (float) VectorLength( dir );
3441
3442         /* get length of normal vector */
3443         if( normal != NULL )
3444                 length = VectorLength( normal );
3445         else
3446         {
3447                 normal = nullVector;
3448                 length = 0;
3449         }
3450
3451         /* test each light and see if it reaches the sphere */
3452         /* note: the attenuation code MUST match LightingAtSample() */
3453         for( light = lights; light; light = light->next )
3454         {
3455                 /* check zero sized envelope */
3456                 if( light->envelope <= 0 )
3457                 {
3458                         lightsEnvelopeCulled++;
3459                         continue;
3460                 }
3461
3462                 /* check flags */
3463                 if( !(light->flags & flags) )
3464                         continue;
3465
3466                 /* sunlight skips all this nonsense */
3467                 if( light->type != EMIT_SUN )
3468                 {
3469                         /* sun only? */
3470                         if( sunOnly )
3471                                 continue;
3472
3473                         /* check against pvs cluster */
3474                         if( numClusters > 0 && clusters != NULL )
3475                         {
3476                                 for( i = 0; i < numClusters; i++ )
3477                                 {
3478                                         if( ClusterVisible( light->cluster, clusters[ i ] ) )
3479                                                 break;
3480                                 }
3481
3482                                 /* fixme! */
3483                                 if( i == numClusters )
3484                                 {
3485                                         lightsClusterCulled++;
3486                                         continue;
3487                                 }
3488                         }
3489
3490                         /* if the light's bounding sphere intersects with the bounding sphere then this light needs to be tested */
3491                         VectorSubtract( light->origin, origin, dir );
3492                         dist = VectorLength( dir );
3493                         dist -= light->envelope;
3494                         dist -= radius;
3495                         if( dist > 0 )
3496                         {
3497                                 lightsEnvelopeCulled++;
3498                                 continue;
3499                         }
3500
3501                         /* check bounding box against light's pvs envelope (note: this code never eliminated any lights, so disabling it) */
3502                         #if 0
3503                         skip = qfalse;
3504                         for( i = 0; i < 3; i++ )
3505                         {
3506                                 if( mins[ i ] > light->maxs[ i ] || maxs[ i ] < light->mins[ i ] )
3507                                         skip = qtrue;
3508                         }
3509                         if( skip )
3510                         {
3511                                 lightsBoundsCulled++;
3512                                 continue;
3513                         }
3514                         #endif
3515                 }
3516
3517                 /* planar surfaces (except twosided surfaces) have a couple more checks */
3518                 if( length > 0.0f && trace->twoSided == qfalse )
3519                 {
3520                         /* lights coplanar with a surface won't light it */
3521                         if( !(light->flags & LIGHT_TWOSIDED) && DotProduct( light->normal, normal ) > 0.999f )
3522                         {
3523                                 lightsPlaneCulled++;
3524                                 continue;
3525                         }
3526
3527                         /* check to see if light is behind the plane */
3528                         if( DotProduct( light->origin, normal ) - DotProduct( origin, normal ) < -1.0f )
3529                         {
3530                                 lightsPlaneCulled++;
3531                                 continue;
3532                         }
3533                 }
3534
3535                 /* add this light */
3536                 trace->lights[ trace->numLights++ ] = light;
3537         }
3538
3539         /* make last night null */
3540         trace->lights[ trace->numLights ] = NULL;
3541 }
3542
3543
3544
3545 void FreeTraceLights( trace_t *trace )
3546 {
3547         if( trace->lights != NULL )
3548                 free( trace->lights );
3549 }
3550
3551
3552
3553 /*
3554 CreateTraceLightsForSurface()
3555 creates a list of lights that can potentially affect a drawsurface
3556 */
3557
3558 void CreateTraceLightsForSurface( int num, trace_t *trace )
3559 {
3560         int                                     i;
3561         vec3_t                          mins, maxs, normal;
3562         bspDrawVert_t           *dv;
3563         bspDrawSurface_t        *ds;
3564         surfaceInfo_t           *info;
3565
3566
3567         /* dummy check */
3568         if( num < 0 )
3569                 return;
3570
3571         /* get drawsurface and info */
3572         ds = &bspDrawSurfaces[ num ];
3573         info = &surfaceInfos[ num ];
3574
3575         /* get the mins/maxs for the dsurf */
3576         ClearBounds( mins, maxs );
3577         VectorCopy( bspDrawVerts[ ds->firstVert ].normal, normal );
3578         for( i = 0; i < ds->numVerts; i++ )
3579         {
3580                 dv = &yDrawVerts[ ds->firstVert + i ];
3581                 AddPointToBounds( dv->xyz, mins, maxs );
3582                 if( !VectorCompare( dv->normal, normal ) )
3583                         VectorClear( normal );
3584         }
3585
3586         /* create the lights for the bounding box */
3587         CreateTraceLightsForBounds( mins, maxs, normal, info->numSurfaceClusters, &surfaceClusters[ info->firstSurfaceCluster ], LIGHT_SURFACES, trace );
3588 }
3589
3590
3591
3592
3593