tools/quake3/q3map2/light_ydnar.c

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