tools/quake3/q3map2/light_ydnar.c

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