tools/quake3/q3map2/light_ydnar.c

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