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