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