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 #if 0
2067                                         ////////// 27's temp hack for testing edge clipping ////
2068                                         if( origin[0]==0 && origin[1]==0 && origin[2]==0 )
2069                                         {
2070                                                 lightLuxel[ 1 ] = 255;
2071                                                 lightLuxel[ 3 ] = 1.0f;
2072                                                 totalLighted++;
2073                                         }
2074                                         else
2075 #endif
2076                                         {
2077                                                 /* set contribution count */
2078                                                 lightLuxel[ 3 ] = 1.0f;
2079
2080                                                 /* setup trace */
2081                                                 trace.cluster = *cluster;
2082                                                 VectorCopy( origin, trace.origin );
2083                                                 VectorCopy( normal, trace.normal );
2084
2085                                                 /* get light for this sample */
2086                                                 LightContributionToSample( &trace );
2087                                                 VectorCopy( trace.color, lightLuxel );
2088
2089                                                 /* add to count */
2090                                                 if( trace.color[ 0 ] || trace.color[ 1 ] || trace.color[ 2 ] )
2091                                                         totalLighted++;
2092                                         }
2093
2094                                         /* add to light direction map (fixme: use luxel normal as starting point for deluxel?) */
2095                                         if( deluxemap )
2096                                         {
2097                                                 /* color to grayscale (photoshop rgb weighting) */
2098                                                 brightness = trace.color[ 0 ] * 0.3f + trace.color[ 1 ] * 0.59f + trace.color[ 2 ] * 0.11f;
2099                                                 brightness *= (1.0 / 255.0);
2100                                                 VectorScale( trace.direction, brightness, trace.direction );
2101                                                 VectorAdd( deluxel, trace.direction, deluxel );
2102                                         }
2103                                 }
2104                         }
2105
2106                         /* don't even bother with everything else if nothing was lit */
2107                         if( totalLighted == 0 )
2108                                 continue;
2109
2110                         /* determine filter radius */
2111                         filterRadius = lm->filterRadius > trace.light->filterRadius
2112                                 ? lm->filterRadius
2113                                 : trace.light->filterRadius;
2114                         if( filterRadius < 0.0f )
2115                                 filterRadius = 0.0f;
2116
2117                         /* set luxel filter radius */
2118                         luxelFilterRadius = superSample * filterRadius / lm->sampleSize;
2119                         if( luxelFilterRadius == 0 && (filterRadius > 0.0f || filter) )
2120                                 luxelFilterRadius = 1;
2121
2122                         /* secondary pass, adaptive supersampling (fixme: use a contrast function to determine if subsampling is necessary) */
2123                         /* 2003-09-27: changed it so filtering disamples supersampling, as it would waste time */
2124                         if( lightSamples > 1 && luxelFilterRadius == 0 )
2125                         {
2126                                 /* walk luxels */
2127                                 for( y = 0; y < (lm->sh - 1); y++ )
2128                                 {
2129                                         for( x = 0; x < (lm->sw - 1); x++ )
2130                                         {
2131                                                 /* setup */
2132                                                 mapped = 0;
2133                                                 lighted = 0;
2134                                                 VectorClear( total );
2135
2136                                                 /* test 2x2 stamp */
2137                                                 for( t = 0; t < 4; t++ )
2138                                                 {
2139                                                         /* set sample coords */
2140                                                         sx = x + tests[ t ][ 0 ];
2141                                                         sy = y + tests[ t ][ 1 ];
2142
2143                                                         /* get cluster */
2144                                                         cluster = SUPER_CLUSTER( sx, sy );
2145                                                         if( *cluster < 0 )
2146                                                                 continue;
2147                                                         mapped++;
2148
2149                                                         /* get luxel */
2150                                                         lightLuxel = LIGHT_LUXEL( sx, sy );
2151                                                         VectorAdd( total, lightLuxel, total );
2152                                                         if( (lightLuxel[ 0 ] + lightLuxel[ 1 ] + lightLuxel[ 2 ]) > 0.0f )
2153                                                                 lighted++;
2154                                                 }
2155
2156                                                 /* if total color is under a certain amount, then don't bother subsampling */
2157                                                 if( total[ 0 ] <= 4.0f && total[ 1 ] <= 4.0f && total[ 2 ] <= 4.0f )
2158                                                         continue;
2159
2160                                                 /* if all 4 pixels are either in shadow or light, then don't subsample */
2161                                                 if( lighted != 0 && lighted != mapped )
2162                                                 {
2163                                                         for( t = 0; t < 4; t++ )
2164                                                         {
2165                                                                 /* set sample coords */
2166                                                                 sx = x + tests[ t ][ 0 ];
2167                                                                 sy = y + tests[ t ][ 1 ];
2168
2169                                                                 /* get luxel */
2170                                                                 cluster = SUPER_CLUSTER( sx, sy );
2171                                                                 if( *cluster < 0 )
2172                                                                         continue;
2173                                                                 lightLuxel = LIGHT_LUXEL( sx, sy );
2174                                                                 origin = SUPER_ORIGIN( sx, sy );
2175
2176                                                                 /* only subsample shadowed luxels */
2177                                                                 //%     if( (lightLuxel[ 0 ] + lightLuxel[ 1 ] + lightLuxel[ 2 ]) <= 0.0f )
2178                                                                 //%             continue;
2179
2180                                                                 /* subsample it */
2181                                                                 SubsampleRawLuxel_r( lm, &trace, origin, sx, sy, 0.25f, lightLuxel );
2182
2183                                                                 /* debug code to colorize subsampled areas to yellow */
2184                                                                 //%     luxel = SUPER_LUXEL( lightmapNum, sx, sy );
2185                                                                 //%     VectorSet( luxel, 255, 204, 0 );
2186                                                         }
2187                                                 }
2188                                         }
2189                                 }
2190                         }
2191
2192                         /* tertiary pass, apply dirt map (ambient occlusion) */
2193                         if( 0 && dirty )
2194                         {
2195                                 /* walk luxels */
2196                                 for( y = 0; y < lm->sh; y++ )
2197                                 {
2198                                         for( x = 0; x < lm->sw; x++ )
2199                                         {
2200                                                 /* get cluster  */
2201                                                 cluster = SUPER_CLUSTER( x, y );
2202                                                 if( *cluster < 0 )
2203                                                         continue;
2204
2205                                                 /* get particulars */
2206                                                 lightLuxel = LIGHT_LUXEL( x, y );
2207                                                 dirt = SUPER_DIRT( x, y );
2208
2209                                                 /* scale light value */
2210                                                 VectorScale( lightLuxel, *dirt, lightLuxel );
2211                                         }
2212                                 }
2213                         }
2214
2215                         /* allocate sampling lightmap storage */
2216                         if( lm->superLuxels[ lightmapNum ] == NULL )
2217                         {
2218                                 /* allocate sampling lightmap storage */
2219                                 size = lm->sw * lm->sh * SUPER_LUXEL_SIZE * sizeof( float );
2220                                 lm->superLuxels[ lightmapNum ] = safe_malloc( size );
2221                                 memset( lm->superLuxels[ lightmapNum ], 0, size );
2222                         }
2223
2224                         /* set style */
2225                         if( lightmapNum > 0 )
2226                         {
2227                                 lm->styles[ lightmapNum ] = trace.light->style;
2228                                 //%     Sys_Printf( "Surface %6d has lightstyle %d\n", rawLightmapNum, trace.light->style );
2229                         }
2230
2231                         /* copy to permanent luxels */
2232                         for( y = 0; y < lm->sh; y++ )
2233                         {
2234                                 for( x = 0; x < lm->sw; x++ )
2235                                 {
2236                                         /* get cluster and origin */
2237                                         cluster = SUPER_CLUSTER( x, y );
2238                                         if( *cluster < 0 )
2239                                                 continue;
2240                                         origin = SUPER_ORIGIN( x, y );
2241
2242                                         /* filter? */
2243                                         if( luxelFilterRadius )
2244                                         {
2245                                                 /* setup */
2246                                                 VectorClear( averageColor );
2247                                                 samples = 0.0f;
2248
2249                                                 /* cheaper distance-based filtering */
2250                                                 for( sy = (y - luxelFilterRadius); sy <= (y + luxelFilterRadius); sy++ )
2251                                                 {
2252                                                         if( sy < 0 || sy >= lm->sh )
2253                                                                 continue;
2254
2255                                                         for( sx = (x - luxelFilterRadius); sx <= (x + luxelFilterRadius); sx++ )
2256                                                         {
2257                                                                 if( sx < 0 || sx >= lm->sw )
2258                                                                         continue;
2259
2260                                                                 /* get particulars */
2261                                                                 cluster = SUPER_CLUSTER( sx, sy );
2262                                                                 if( *cluster < 0 )
2263                                                                         continue;
2264                                                                 lightLuxel = LIGHT_LUXEL( sx, sy );
2265
2266                                                                 /* create weight */
2267                                                                 weight = (abs( sx - x ) == luxelFilterRadius ? 0.5f : 1.0f);
2268                                                                 weight *= (abs( sy - y ) == luxelFilterRadius ? 0.5f : 1.0f);
2269
2270                                                                 /* scale luxel by filter weight */
2271                                                                 VectorScale( lightLuxel, weight, color );
2272                                                                 VectorAdd( averageColor, color, averageColor );
2273                                                                 samples += weight;
2274                                                         }
2275                                                 }
2276
2277                                                 /* any samples? */
2278                                                 if( samples <= 0.0f     )
2279                                                         continue;
2280
2281                                                 /* scale into luxel */
2282                                                 luxel = SUPER_LUXEL( lightmapNum, x, y );
2283                                                 luxel[ 3 ] = 1.0f;
2284
2285                                                 /* handle negative light */
2286                                                 if( trace.light->flags & LIGHT_NEGATIVE )
2287                                                 {
2288                                                         luxel[ 0 ] -= averageColor[ 0 ] / samples;
2289                                                         luxel[ 1 ] -= averageColor[ 1 ] / samples;
2290                                                         luxel[ 2 ] -= averageColor[ 2 ] / samples;
2291                                                 }
2292
2293                                                 /* handle normal light */
2294                                                 else
2295                                                 {
2296                                                         luxel[ 0 ] += averageColor[ 0 ] / samples;
2297                                                         luxel[ 1 ] += averageColor[ 1 ] / samples;
2298                                                         luxel[ 2 ] += averageColor[ 2 ] / samples;
2299                                                 }
2300                                         }
2301
2302                                         /* single sample */
2303                                         else
2304                                         {
2305                                                 /* get particulars */
2306                                                 lightLuxel = LIGHT_LUXEL( x, y );
2307                                                 luxel = SUPER_LUXEL( lightmapNum, x, y );
2308
2309                                                 /* handle negative light */
2310                                                 if( trace.light->flags & LIGHT_NEGATIVE )
2311                                                         VectorScale( averageColor, -1.0f, averageColor );
2312
2313                                                 /* add color */
2314                                                 luxel[ 3 ] = 1.0f;
2315
2316                                                 /* handle negative light */
2317                                                 if( trace.light->flags & LIGHT_NEGATIVE )
2318                                                         VectorSubtract( luxel, lightLuxel, luxel );
2319
2320                                                 /* handle normal light */
2321                                                 else
2322                                                         VectorAdd( luxel, lightLuxel, luxel );
2323                                         }
2324                                 }
2325                         }
2326                 }
2327
2328                 /* free temporary luxels */
2329                 if( lightLuxels != stackLightLuxels )
2330                         free( lightLuxels );
2331         }
2332
2333         /* free light list */
2334         FreeTraceLights( &trace );
2335
2336         /*      -----------------------------------------------------------------
2337                 floodlight pass
2338                 ----------------------------------------------------------------- */
2339
2340         if( floodlighty )
2341         {
2342                 /* walk lightmaps */
2343                 for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
2344                 {
2345                         /* early out */
2346                         if( lm->superLuxels[ lightmapNum ] == NULL )
2347                                 continue;
2348
2349                         /* apply floodlight to each luxel */
2350                         for( y = 0; y < lm->sh; y++ )
2351                         {
2352                                 for( x = 0; x < lm->sw; x++ )
2353                                 {
2354                                         /* get cluster */
2355                                         cluster = SUPER_CLUSTER( x, y );
2356                                         //%     if( *cluster < 0 )
2357                                         //%             continue;
2358
2359                                         /* get particulars */
2360                                         luxel = SUPER_LUXEL( lightmapNum, x, y );
2361                                         floodlight = SUPER_FLOODLIGHT( x, y );
2362
2363                                         flood[0]=floodlightRGB[0]*floodlightIntensity;
2364                                         flood[1]=floodlightRGB[1]*floodlightIntensity;
2365                                         flood[2]=floodlightRGB[2]*floodlightIntensity;
2366
2367                                         /* scale light value */
2368                                         VectorScale( flood, *floodlight, flood );
2369                                         luxel[0]+=flood[0];
2370                                         luxel[1]+=flood[1];
2371                                         luxel[2]+=flood[2];
2372
2373                                         if (luxel[3]==0) luxel[3]=1;
2374                                 }
2375                         }
2376                 }
2377         }
2378
2379         if (debugnormals)
2380         {
2381                 for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
2382                 {
2383                         /* early out */
2384                         if( lm->superLuxels[ lightmapNum ] == NULL )
2385                                 continue;
2386
2387                         for( y = 0; y < lm->sh; y++ )
2388                         {
2389                                 for( x = 0; x < lm->sw; x++ )
2390                                 {
2391                                         /* get cluster */
2392                                         cluster = SUPER_CLUSTER( x, y );
2393                                         //%     if( *cluster < 0 )
2394                                         //%             continue;
2395
2396                                         /* get particulars */
2397                                         luxel = SUPER_LUXEL( lightmapNum, x, y );
2398                                         normal = SUPER_NORMAL (  x, y );
2399
2400                                         luxel[0]=(normal[0]*127)+127;
2401                                         luxel[1]=(normal[1]*127)+127;
2402                                         luxel[2]=(normal[2]*127)+127;
2403                                 }
2404                         }
2405                 }
2406         }
2407
2408         /*      -----------------------------------------------------------------
2409                 dirt pass
2410                 ----------------------------------------------------------------- */
2411
2412         if( dirty )
2413         {
2414                 /* walk lightmaps */
2415                 for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
2416                 {
2417                         /* early out */
2418                         if( lm->superLuxels[ lightmapNum ] == NULL )
2419                                 continue;
2420
2421                         /* apply dirt to each luxel */
2422                         for( y = 0; y < lm->sh; y++ )
2423                         {
2424                                 for( x = 0; x < lm->sw; x++ )
2425                                 {
2426                                         /* get cluster */
2427                                         cluster = SUPER_CLUSTER( x, y );
2428                                         //%     if( *cluster < 0 )
2429                                         //%             continue;
2430
2431                                         /* get particulars */
2432                                         luxel = SUPER_LUXEL( lightmapNum, x, y );
2433                                         dirt = SUPER_DIRT( x, y );
2434
2435                                         /* apply dirt */
2436                                         VectorScale( luxel, *dirt, luxel );
2437
2438                                         /* debugging */
2439                                         if( dirtDebug )
2440                                                 VectorSet( luxel, *dirt * 255.0f, *dirt * 255.0f, *dirt * 255.0f );
2441                                 }
2442                         }
2443                 }
2444         }
2445
2446         /* -----------------------------------------------------------------
2447            filter pass
2448            ----------------------------------------------------------------- */
2449
2450         /* walk lightmaps */
2451         for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
2452         {
2453                 /* early out */
2454                 if( lm->superLuxels[ lightmapNum ] == NULL )
2455                         continue;
2456
2457                 /* average occluded luxels from neighbors */
2458                 for( y = 0; y < lm->sh; y++ )
2459                 {
2460                         for( x = 0; x < lm->sw; x++ )
2461                         {
2462                                 /* get particulars */
2463                                 cluster = SUPER_CLUSTER( x, y );
2464                                 luxel = SUPER_LUXEL( lightmapNum, x, y );
2465                                 deluxel = SUPER_DELUXEL( x, y );
2466                                 normal = SUPER_NORMAL( x, y );
2467
2468                                 /* determine if filtering is necessary */
2469                                 filterColor = qfalse;
2470                                 filterDir = qfalse;
2471                                 if( *cluster < 0 ||
2472                                         (lm->splotchFix && (luxel[ 0 ] <= ambientColor[ 0 ] || luxel[ 1 ] <= ambientColor[ 1 ] || luxel[ 2 ] <= ambientColor[ 2 ])) )
2473                                         filterColor = qtrue;
2474                                 if( deluxemap && lightmapNum == 0 && (*cluster < 0 || filter) )
2475                                         filterDir = qtrue;
2476
2477                                 if( !filterColor && !filterDir )
2478                                         continue;
2479
2480                                 /* choose seed amount */
2481                                 VectorClear( averageColor );
2482                                 VectorClear( averageDir );
2483                                 samples = 0.0f;
2484
2485                                 /* walk 3x3 matrix */
2486                                 for( sy = (y - 1); sy <= (y + 1); sy++ )
2487                                 {
2488                                         if( sy < 0 || sy >= lm->sh )
2489                                                 continue;
2490
2491                                         for( sx = (x - 1); sx <= (x + 1); sx++ )
2492                                         {
2493                                                 if( sx < 0 || sx >= lm->sw || (sx == x && sy == y) )
2494                                                         continue;
2495
2496                                                 /* get neighbor's particulars */
2497                                                 cluster2 = SUPER_CLUSTER( sx, sy );
2498                                                 luxel2 = SUPER_LUXEL( lightmapNum, sx, sy );
2499                                                 deluxel2 = SUPER_DELUXEL( sx, sy );
2500
2501                                                 /* ignore unmapped/unlit luxels */
2502                                                 if( *cluster2 < 0 || luxel2[ 3 ] == 0.0f ||
2503                                                         (lm->splotchFix && VectorCompare( luxel2, ambientColor )) )
2504                                                         continue;
2505
2506                                                 /* add its distinctiveness to our own */
2507                                                 VectorAdd( averageColor, luxel2, averageColor );
2508                                                 samples += luxel2[ 3 ];
2509                                                 if( filterDir )
2510                                                         VectorAdd( averageDir, deluxel2, averageDir );
2511                                         }
2512                                 }
2513
2514                                 /* fall through */
2515                                 if( samples <= 0.0f )
2516                                         continue;
2517
2518                                 /* dark lightmap seams */
2519                                 if( dark )
2520                                 {
2521                                         if( lightmapNum == 0 )
2522                                                 VectorMA( averageColor, 2.0f, ambientColor, averageColor );
2523                                         samples += 2.0f;
2524                                 }
2525
2526                                 /* average it */
2527                                 if( filterColor )
2528                                 {
2529                                         VectorDivide( averageColor, samples, luxel );
2530                                         luxel[ 3 ] = 1.0f;
2531                                 }
2532                                 if( filterDir )
2533                                         VectorDivide( averageDir, samples, deluxel );
2534
2535                                 /* set cluster to -3 */
2536                                 if( *cluster < 0 )
2537                                         *cluster = CLUSTER_FLOODED;
2538                         }
2539                 }
2540         }
2541 }
2542
2543
2544
2545 /*
2546 IlluminateVertexes()
2547 light the surface vertexes
2548 */
2549
2550 #define VERTEX_NUDGE    4.0f
2551
2552 void IlluminateVertexes( int num )
2553 {
2554         int                                     i, x, y, z, x1, y1, z1, sx, sy, radius, maxRadius, *cluster;
2555         int                                     lightmapNum, numAvg;
2556         float                           samples, *vertLuxel, *radVertLuxel, *luxel, dirt;
2557         vec3_t                          origin, temp, temp2, colors[ MAX_LIGHTMAPS ], avgColors[ MAX_LIGHTMAPS ];
2558         bspDrawSurface_t        *ds;
2559         surfaceInfo_t           *info;
2560         rawLightmap_t           *lm;
2561         bspDrawVert_t           *verts;
2562         trace_t                         trace;
2563
2564
2565         /* get surface, info, and raw lightmap */
2566         ds = &bspDrawSurfaces[ num ];
2567         info = &surfaceInfos[ num ];
2568         lm = info->lm;
2569
2570         /* -----------------------------------------------------------------
2571            illuminate the vertexes
2572            ----------------------------------------------------------------- */
2573
2574         /* calculate vertex lighting for surfaces without lightmaps */
2575         if( lm == NULL || cpmaHack )
2576         {
2577                 /* setup trace */
2578                 trace.testOcclusion = (cpmaHack && lm != NULL) ? qfalse : !noTrace;
2579                 trace.forceSunlight = info->si->forceSunlight;
2580                 trace.recvShadows = info->recvShadows;
2581                 trace.numSurfaces = 1;
2582                 trace.surfaces = &num;
2583                 trace.inhibitRadius = DEFAULT_INHIBIT_RADIUS;
2584
2585                 /* twosided lighting */
2586                 trace.twoSided = info->si->twoSided;
2587
2588                 /* make light list for this surface */
2589                 CreateTraceLightsForSurface( num, &trace );
2590
2591                 /* setup */
2592                 verts = yDrawVerts + ds->firstVert;
2593                 numAvg = 0;
2594                 memset( avgColors, 0, sizeof( avgColors ) );
2595
2596                 /* walk the surface verts */
2597                 for( i = 0; i < ds->numVerts; i++ )
2598                 {
2599                         /* get vertex luxel */
2600                         radVertLuxel = RAD_VERTEX_LUXEL( 0, ds->firstVert + i );
2601
2602                         /* color the luxel with raw lightmap num? */
2603                         if( debugSurfaces )
2604                                 VectorCopy( debugColors[ num % 12 ], radVertLuxel );
2605
2606                         /* color the luxel with luxel origin? */
2607                         else if( debugOrigin )
2608                         {
2609                                 VectorSubtract( info->maxs, info->mins, temp );
2610                                 VectorScale( temp, (1.0f / 255.0f), temp );
2611                                 VectorSubtract( origin, lm->mins, temp2 );
2612                                 radVertLuxel[ 0 ] = info->mins[ 0 ] + (temp[ 0 ] * temp2[ 0 ]);
2613                                 radVertLuxel[ 1 ] = info->mins[ 1 ] + (temp[ 1 ] * temp2[ 1 ]);
2614                                 radVertLuxel[ 2 ] = info->mins[ 2 ] + (temp[ 2 ] * temp2[ 2 ]);
2615                         }
2616
2617                         /* color the luxel with the normal */
2618                         else if( normalmap )
2619                         {
2620                                 radVertLuxel[ 0 ] = (verts[ i ].normal[ 0 ] + 1.0f) * 127.5f;
2621                                 radVertLuxel[ 1 ] = (verts[ i ].normal[ 1 ] + 1.0f) * 127.5f;
2622                                 radVertLuxel[ 2 ] = (verts[ i ].normal[ 2 ] + 1.0f) * 127.5f;
2623                         }
2624
2625                         /* illuminate the vertex */
2626                         else
2627                         {
2628                                 /* clear vertex luxel */
2629                                 VectorSet( radVertLuxel, -1.0f, -1.0f, -1.0f );
2630
2631                                 /* try at initial origin */
2632                                 trace.cluster = ClusterForPointExtFilter( verts[ i ].xyz, VERTEX_EPSILON, info->numSurfaceClusters, &surfaceClusters[ info->firstSurfaceCluster ] );
2633                                 if( trace.cluster >= 0 )
2634                                 {
2635                                         /* setup trace */
2636                                         VectorCopy( verts[ i ].xyz, trace.origin );
2637                                         VectorCopy( verts[ i ].normal, trace.normal );
2638
2639                                         /* r7 dirt */
2640                                         if( dirty )
2641                                                 dirt = DirtForSample( &trace );
2642                                         else
2643                                                 dirt = 1.0f;
2644
2645                                         /* trace */
2646                                         LightingAtSample( &trace, ds->vertexStyles, colors );
2647
2648                                         /* store */
2649                                         for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
2650                                         {
2651                                                 /* r7 dirt */
2652                                                 VectorScale( colors[ lightmapNum ], dirt, colors[ lightmapNum ] );
2653
2654                                                 /* store */
2655                                                 radVertLuxel = RAD_VERTEX_LUXEL( lightmapNum, ds->firstVert + i );
2656                                                 VectorCopy( colors[ lightmapNum ], radVertLuxel );
2657                                                 VectorAdd( avgColors[ lightmapNum ], colors[ lightmapNum ], colors[ lightmapNum ] );
2658                                         }
2659                                 }
2660
2661                                 /* is this sample bright enough? */
2662                                 radVertLuxel = RAD_VERTEX_LUXEL( 0, ds->firstVert + i );
2663                                 if( radVertLuxel[ 0 ] <= ambientColor[ 0 ] &&
2664                                         radVertLuxel[ 1 ] <= ambientColor[ 1 ] &&
2665                                         radVertLuxel[ 2 ] <= ambientColor[ 2 ] )
2666                                 {
2667                                         /* nudge the sample point around a bit */
2668                                         for( x = 0; x < 4; x++ )
2669                                         {
2670                                                 /* two's complement 0, 1, -1, 2, -2, etc */
2671                                                 x1 = ((x >> 1) ^ (x & 1 ? -1 : 0)) + (x & 1);
2672
2673                                                 for( y = 0; y < 4; y++ )
2674                                                 {
2675                                                         y1 = ((y >> 1) ^ (y & 1 ? -1 : 0)) + (y & 1);
2676
2677                                                         for( z = 0; z < 4; z++ )
2678                                                         {
2679                                                                 z1 = ((z >> 1) ^ (z & 1 ? -1 : 0)) + (z & 1);
2680
2681                                                                 /* nudge origin */
2682                                                                 trace.origin[ 0 ] = verts[ i ].xyz[ 0 ] + (VERTEX_NUDGE * x1);
2683                                                                 trace.origin[ 1 ] = verts[ i ].xyz[ 1 ] + (VERTEX_NUDGE * y1);
2684                                                                 trace.origin[ 2 ] = verts[ i ].xyz[ 2 ] + (VERTEX_NUDGE * z1);
2685
2686                                                                 /* try at nudged origin */
2687                                                                 trace.cluster = ClusterForPointExtFilter( origin, VERTEX_EPSILON, info->numSurfaceClusters, &surfaceClusters[ info->firstSurfaceCluster ] );
2688                                                                 if( trace.cluster < 0 )
2689                                                                         continue;
2690
2691                                                                 /* trace */
2692                                                                 LightingAtSample( &trace, ds->vertexStyles, colors );
2693
2694                                                                 /* store */
2695                                                                 for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
2696                                                                 {
2697                                                                         /* r7 dirt */
2698                                                                         VectorScale( colors[ lightmapNum ], dirt, colors[ lightmapNum ] );
2699
2700                                                                         /* store */
2701                                                                         radVertLuxel = RAD_VERTEX_LUXEL( lightmapNum, ds->firstVert + i );
2702                                                                         VectorCopy( colors[ lightmapNum ], radVertLuxel );
2703                                                                 }
2704
2705                                                                 /* bright enough? */
2706                                                                 radVertLuxel = RAD_VERTEX_LUXEL( 0, ds->firstVert + i );
2707                                                                 if( radVertLuxel[ 0 ] > ambientColor[ 0 ] ||
2708                                                                         radVertLuxel[ 1 ] > ambientColor[ 1 ] ||
2709                                                                         radVertLuxel[ 2 ] > ambientColor[ 2 ] )
2710                                                                         x = y = z = 1000;
2711                                                         }
2712                                                 }
2713                                         }
2714                                 }
2715
2716                                 /* add to average? */
2717                                 radVertLuxel = RAD_VERTEX_LUXEL( 0, ds->firstVert + i );
2718                                 if( radVertLuxel[ 0 ] > ambientColor[ 0 ] ||
2719                                         radVertLuxel[ 1 ] > ambientColor[ 1 ] ||
2720                                         radVertLuxel[ 2 ] > ambientColor[ 2 ] )
2721                                 {
2722                                         numAvg++;
2723                                         for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
2724                                         {
2725                                                 radVertLuxel = RAD_VERTEX_LUXEL( lightmapNum, ds->firstVert + i );
2726                                                 VectorAdd( avgColors[ lightmapNum ], radVertLuxel, avgColors[ lightmapNum ] );
2727                                         }
2728                                 }
2729                         }
2730
2731                         /* another happy customer */
2732                         numVertsIlluminated++;
2733                 }
2734
2735                 /* set average color */
2736                 if( numAvg > 0 )
2737                 {
2738                         for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
2739                                 VectorScale( avgColors[ lightmapNum ], (1.0f / numAvg), avgColors[ lightmapNum ] );
2740                 }
2741                 else
2742                 {
2743                         VectorCopy( ambientColor, avgColors[ 0 ] );
2744                 }
2745
2746                 /* clean up and store vertex color */
2747                 for( i = 0; i < ds->numVerts; i++ )
2748                 {
2749                         /* get vertex luxel */
2750                         radVertLuxel = RAD_VERTEX_LUXEL( 0, ds->firstVert + i );
2751
2752                         /* store average in occluded vertexes */
2753                         if( radVertLuxel[ 0 ] < 0.0f )
2754                         {
2755                                 for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
2756                                 {
2757                                         radVertLuxel = RAD_VERTEX_LUXEL( lightmapNum, ds->firstVert + i );
2758                                         VectorCopy( avgColors[ lightmapNum ], radVertLuxel );
2759
2760                                         /* debug code */
2761                                         //%     VectorSet( radVertLuxel, 255.0f, 0.0f, 0.0f );
2762                                 }
2763                         }
2764
2765                         /* store it */
2766                         for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
2767                         {
2768                                 /* get luxels */
2769                                 vertLuxel = VERTEX_LUXEL( lightmapNum, ds->firstVert + i );
2770                                 radVertLuxel = RAD_VERTEX_LUXEL( lightmapNum, ds->firstVert + i );
2771
2772                                 /* store */
2773                                 if( bouncing || bounce == 0 || !bounceOnly )
2774                                         VectorAdd( vertLuxel, radVertLuxel, vertLuxel );
2775                                 if( !info->si->noVertexLight )
2776                                         ColorToBytes( vertLuxel, verts[ i ].color[ lightmapNum ], info->si->vertexScale );
2777                         }
2778                 }
2779
2780                 /* free light list */
2781                 FreeTraceLights( &trace );
2782
2783                 /* return to sender */
2784                 return;
2785         }
2786
2787         /* -----------------------------------------------------------------
2788            reconstitute vertex lighting from the luxels
2789            ----------------------------------------------------------------- */
2790
2791         /* set styles from lightmap */
2792         for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
2793                 ds->vertexStyles[ lightmapNum ] = lm->styles[ lightmapNum ];
2794
2795         /* get max search radius */
2796         maxRadius = lm->sw;
2797         maxRadius = maxRadius > lm->sh ? maxRadius : lm->sh;
2798
2799         /* walk the surface verts */
2800         verts = yDrawVerts + ds->firstVert;
2801         for( i = 0; i < ds->numVerts; i++ )
2802         {
2803                 /* do each lightmap */
2804                 for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
2805                 {
2806                         /* early out */
2807                         if( lm->superLuxels[ lightmapNum ] == NULL )
2808                                 continue;
2809
2810                         /* get luxel coords */
2811                         x = verts[ i ].lightmap[ lightmapNum ][ 0 ];
2812                         y = verts[ i ].lightmap[ lightmapNum ][ 1 ];
2813                         if( x < 0 )
2814                                 x = 0;
2815                         else if( x >= lm->sw )
2816                                 x = lm->sw - 1;
2817                         if( y < 0 )
2818                                 y = 0;
2819                         else if( y >= lm->sh )
2820                                 y = lm->sh - 1;
2821
2822                         /* get vertex luxels */
2823                         vertLuxel = VERTEX_LUXEL( lightmapNum, ds->firstVert + i );
2824                         radVertLuxel = RAD_VERTEX_LUXEL( lightmapNum, ds->firstVert + i );
2825
2826                         /* color the luxel with the normal? */
2827                         if( normalmap )
2828                         {
2829                                 radVertLuxel[ 0 ] = (verts[ i ].normal[ 0 ] + 1.0f) * 127.5f;
2830                                 radVertLuxel[ 1 ] = (verts[ i ].normal[ 1 ] + 1.0f) * 127.5f;
2831                                 radVertLuxel[ 2 ] = (verts[ i ].normal[ 2 ] + 1.0f) * 127.5f;
2832                         }
2833
2834                         /* color the luxel with surface num? */
2835                         else if( debugSurfaces )
2836                                 VectorCopy( debugColors[ num % 12 ], radVertLuxel );
2837
2838                         /* divine color from the superluxels */
2839                         else
2840                         {
2841                                 /* increasing radius */
2842                                 VectorClear( radVertLuxel );
2843                                 samples = 0.0f;
2844                                 for( radius = 0; radius < maxRadius && samples <= 0.0f; radius++ )
2845                                 {
2846                                         /* sample within radius */
2847                                         for( sy = (y - radius); sy <= (y + radius); sy++ )
2848                                         {
2849                                                 if( sy < 0 || sy >= lm->sh )
2850                                                         continue;
2851
2852                                                 for( sx = (x - radius); sx <= (x + radius); sx++ )
2853                                                 {
2854                                                         if( sx < 0 || sx >= lm->sw )
2855                                                                 continue;
2856
2857                                                         /* get luxel particulars */
2858                                                         luxel = SUPER_LUXEL( lightmapNum, sx, sy );
2859                                                         cluster = SUPER_CLUSTER( sx, sy );
2860                                                         if( *cluster < 0 )
2861                                                                 continue;
2862
2863                                                         /* testing: must be brigher than ambient color */
2864                                                         //%     if( luxel[ 0 ] <= ambientColor[ 0 ] || luxel[ 1 ] <= ambientColor[ 1 ] || luxel[ 2 ] <= ambientColor[ 2 ] )
2865                                                         //%             continue;
2866
2867                                                         /* add its distinctiveness to our own */
2868                                                         VectorAdd( radVertLuxel, luxel, radVertLuxel );
2869                                                         samples += luxel[ 3 ];
2870                                                 }
2871                                         }
2872                                 }
2873
2874                                 /* any color? */
2875                                 if( samples > 0.0f )
2876                                         VectorDivide( radVertLuxel, samples, radVertLuxel );
2877                                 else
2878                                         VectorCopy( ambientColor, radVertLuxel );
2879                         }
2880
2881                         /* store into floating point storage */
2882                         VectorAdd( vertLuxel, radVertLuxel, vertLuxel );
2883                         numVertsIlluminated++;
2884
2885                         /* store into bytes (for vertex approximation) */
2886                         if( !info->si->noVertexLight )
2887                                 ColorToBytes( vertLuxel, verts[ i ].color[ lightmapNum ], 1.0f );
2888                 }
2889         }
2890 }
2891
2892
2893
2894 /* -------------------------------------------------------------------------------
2895
2896 light optimization (-fast)
2897
2898 creates a list of lights that will affect a surface and stores it in tw
2899 this is to optimize surface lighting by culling out as many of the
2900 lights in the world as possible from further calculation
2901
2902 ------------------------------------------------------------------------------- */
2903
2904 /*
2905 SetupBrushes()
2906 determines opaque brushes in the world and find sky shaders for sunlight calculations
2907 */
2908
2909 void SetupBrushes( void )
2910 {
2911         int                             i, j, b, compileFlags;
2912         qboolean                inside;
2913         bspBrush_t              *brush;
2914         bspBrushSide_t  *side;
2915         bspShader_t             *shader;
2916         shaderInfo_t    *si;
2917
2918
2919         /* note it */
2920         Sys_FPrintf( SYS_VRB, "--- SetupBrushes ---\n" );
2921
2922         /* allocate */
2923         if( opaqueBrushes == NULL )
2924                 opaqueBrushes = safe_malloc( numBSPBrushes / 8 + 1 );
2925
2926         /* clear */
2927         memset( opaqueBrushes, 0, numBSPBrushes / 8 + 1 );
2928         numOpaqueBrushes = 0;
2929
2930         /* walk the list of worldspawn brushes */
2931         for( i = 0; i < bspModels[ 0 ].numBSPBrushes; i++ )
2932         {
2933                 /* get brush */
2934                 b = bspModels[ 0 ].firstBSPBrush + i;
2935                 brush = &bspBrushes[ b ];
2936
2937                 /* check all sides */
2938                 inside = qtrue;
2939                 compileFlags = 0;
2940                 for( j = 0; j < brush->numSides && inside; j++ )
2941                 {
2942                         /* do bsp shader calculations */
2943                         side = &bspBrushSides[ brush->firstSide + j ];
2944                         shader = &bspShaders[ side->shaderNum ];
2945
2946                         /* get shader info */
2947                         si = ShaderInfoForShader( shader->shader );
2948                         if( si == NULL )
2949                                 continue;
2950
2951                         /* or together compile flags */
2952                         compileFlags |= si->compileFlags;
2953                 }
2954
2955                 /* determine if this brush is opaque to light */
2956                 if( !(compileFlags & C_TRANSLUCENT) )
2957                 {
2958                         opaqueBrushes[ b >> 3 ] |= (1 << (b & 7));
2959                         numOpaqueBrushes++;
2960                         maxOpaqueBrush = i;
2961                 }
2962         }
2963
2964         /* emit some statistics */
2965         Sys_FPrintf( SYS_VRB, "%9d opaque brushes\n", numOpaqueBrushes );
2966 }
2967
2968
2969
2970 /*
2971 ClusterVisible()
2972 determines if two clusters are visible to each other using the PVS
2973 */
2974
2975 qboolean ClusterVisible( int a, int b )
2976 {
2977         int                     portalClusters, leafBytes;
2978         byte            *pvs;
2979
2980
2981         /* dummy check */
2982         if( a < 0 || b < 0 )
2983                 return qfalse;
2984
2985         /* early out */
2986         if( a == b )
2987                 return qtrue;
2988
2989         /* not vised? */
2990         if( numBSPVisBytes <=8 )
2991                 return qtrue;
2992
2993         /* get pvs data */
2994         portalClusters = ((int *) bspVisBytes)[ 0 ];
2995         leafBytes = ((int*) bspVisBytes)[ 1 ];
2996         pvs = bspVisBytes + VIS_HEADER_SIZE + (a * leafBytes);
2997
2998         /* check */
2999         if( (pvs[ b >> 3 ] & (1 << (b & 7))) )
3000                 return qtrue;
3001         return qfalse;
3002 }
3003
3004
3005
3006 /*
3007 PointInLeafNum_r()
3008 borrowed from vlight.c
3009 */
3010
3011 int     PointInLeafNum_r( vec3_t point, int nodenum )
3012 {
3013         int                     leafnum;
3014         vec_t           dist;
3015         bspNode_t               *node;
3016         bspPlane_t      *plane;
3017
3018
3019         while( nodenum >= 0 )
3020         {
3021                 node = &bspNodes[ nodenum ];
3022                 plane = &bspPlanes[ node->planeNum ];
3023                 dist = DotProduct( point, plane->normal ) - plane->dist;
3024                 if( dist > 0.1 )
3025                         nodenum = node->children[ 0 ];
3026                 else if( dist < -0.1 )
3027                         nodenum = node->children[ 1 ];
3028                 else
3029                 {
3030                         leafnum = PointInLeafNum_r( point, node->children[ 0 ] );
3031                         if( bspLeafs[ leafnum ].cluster != -1 )
3032                                 return leafnum;
3033                         nodenum = node->children[ 1 ];
3034                 }
3035         }
3036
3037         leafnum = -nodenum - 1;
3038         return leafnum;
3039 }
3040
3041
3042
3043 /*
3044 PointInLeafnum()
3045 borrowed from vlight.c
3046 */
3047
3048 int     PointInLeafNum( vec3_t point )
3049 {
3050         return PointInLeafNum_r( point, 0 );
3051 }
3052
3053
3054
3055 /*
3056 ClusterVisibleToPoint() - ydnar
3057 returns qtrue if point can "see" cluster
3058 */
3059
3060 qboolean ClusterVisibleToPoint( vec3_t point, int cluster )
3061 {
3062         int             pointCluster;
3063
3064
3065         /* get leafNum for point */
3066         pointCluster = ClusterForPoint( point );
3067         if( pointCluster < 0 )
3068                 return qfalse;
3069
3070         /* check pvs */
3071         return ClusterVisible( pointCluster, cluster );
3072 }
3073
3074
3075
3076 /*
3077 ClusterForPoint() - ydnar
3078 returns the pvs cluster for point
3079 */
3080
3081 int ClusterForPoint( vec3_t point )
3082 {
3083         int             leafNum;
3084
3085
3086         /* get leafNum for point */
3087         leafNum = PointInLeafNum( point );
3088         if( leafNum < 0 )
3089                 return -1;
3090
3091         /* return the cluster */
3092         return bspLeafs[ leafNum ].cluster;
3093 }
3094
3095
3096
3097 /*
3098 ClusterForPointExt() - ydnar
3099 also takes brushes into account for occlusion testing
3100 */
3101
3102 int ClusterForPointExt( vec3_t point, float epsilon )
3103 {
3104         int                             i, j, b, leafNum, cluster;
3105         float                   dot;
3106         qboolean                inside;
3107         int                             *brushes, numBSPBrushes;
3108         bspLeaf_t               *leaf;
3109         bspBrush_t              *brush;
3110         bspPlane_t              *plane;
3111
3112
3113         /* get leaf for point */
3114         leafNum = PointInLeafNum( point );
3115         if( leafNum < 0 )
3116                 return -1;
3117         leaf = &bspLeafs[ leafNum ];
3118
3119         /* get the cluster */
3120         cluster = leaf->cluster;
3121         if( cluster < 0 )
3122                 return -1;
3123
3124         /* transparent leaf, so check point against all brushes in the leaf */
3125         brushes = &bspLeafBrushes[ leaf->firstBSPLeafBrush ];
3126         numBSPBrushes = leaf->numBSPLeafBrushes;
3127         for( i = 0; i < numBSPBrushes; i++ )
3128         {
3129                 /* get parts */
3130                 b = brushes[ i ];
3131                 if( b > maxOpaqueBrush )
3132                         continue;
3133                 brush = &bspBrushes[ b ];
3134                 if( !(opaqueBrushes[ b >> 3 ] & (1 << (b & 7))) )
3135                         continue;
3136
3137                 /* check point against all planes */
3138                 inside = qtrue;
3139                 for( j = 0; j < brush->numSides && inside; j++ )
3140                 {
3141                         plane = &bspPlanes[ bspBrushSides[ brush->firstSide + j ].planeNum ];
3142                         dot = DotProduct( point, plane->normal );
3143                         dot -= plane->dist;
3144                         if( dot > epsilon )
3145                                 inside = qfalse;
3146                 }
3147
3148                 /* if inside, return bogus cluster */
3149                 if( inside )
3150                         return -1 - b;
3151         }
3152
3153         /* if the point made it this far, it's not inside any opaque brushes */
3154         return cluster;
3155 }
3156
3157
3158
3159 /*
3160 ClusterForPointExtFilter() - ydnar
3161 adds cluster checking against a list of known valid clusters
3162 */
3163
3164 int ClusterForPointExtFilter( vec3_t point, float epsilon, int numClusters, int *clusters )
3165 {
3166         int             i, cluster;
3167
3168
3169         /* get cluster for point */
3170         cluster = ClusterForPointExt( point, epsilon );
3171
3172         /* check if filtering is necessary */
3173         if( cluster < 0 || numClusters <= 0 || clusters == NULL )
3174                 return cluster;
3175
3176         /* filter */
3177         for( i = 0; i < numClusters; i++ )
3178         {
3179                 if( cluster == clusters[ i ] || ClusterVisible( cluster, clusters[ i ] ) )
3180                         return cluster;
3181         }
3182
3183         /* failed */
3184         return -1;
3185 }
3186
3187
3188
3189 /*
3190 ShaderForPointInLeaf() - ydnar
3191 checks a point against all brushes in a leaf, returning the shader of the brush
3192 also sets the cumulative surface and content flags for the brush hit
3193 */
3194
3195 int ShaderForPointInLeaf( vec3_t point, int leafNum, float epsilon, int wantContentFlags, int wantSurfaceFlags, int *contentFlags, int *surfaceFlags )
3196 {
3197         int                             i, j;
3198         float                   dot;
3199         qboolean                inside;
3200         int                             *brushes, numBSPBrushes;
3201         bspLeaf_t                       *leaf;
3202         bspBrush_t              *brush;
3203         bspBrushSide_t  *side;
3204         bspPlane_t              *plane;
3205         bspShader_t             *shader;
3206         int                             allSurfaceFlags, allContentFlags;
3207
3208
3209         /* clear things out first */
3210         *surfaceFlags = 0;
3211         *contentFlags = 0;
3212
3213         /* get leaf */
3214         if( leafNum < 0 )
3215                 return -1;
3216         leaf = &bspLeafs[ leafNum ];
3217
3218         /* transparent leaf, so check point against all brushes in the leaf */
3219         brushes = &bspLeafBrushes[ leaf->firstBSPLeafBrush ];
3220         numBSPBrushes = leaf->numBSPLeafBrushes;
3221         for( i = 0; i < numBSPBrushes; i++ )
3222         {
3223                 /* get parts */
3224                 brush = &bspBrushes[ brushes[ i ] ];
3225
3226                 /* check point against all planes */
3227                 inside = qtrue;
3228                 allSurfaceFlags = 0;
3229                 allContentFlags = 0;
3230                 for( j = 0; j < brush->numSides && inside; j++ )
3231                 {
3232                         side = &bspBrushSides[ brush->firstSide + j ];
3233                         plane = &bspPlanes[ side->planeNum ];
3234                         dot = DotProduct( point, plane->normal );
3235                         dot -= plane->dist;
3236                         if( dot > epsilon )
3237                                 inside = qfalse;
3238                         else
3239                         {
3240                                 shader = &bspShaders[ side->shaderNum ];
3241                                 allSurfaceFlags |= shader->surfaceFlags;
3242                                 allContentFlags |= shader->contentFlags;
3243                         }
3244                 }
3245
3246                 /* handle if inside */
3247                 if( inside )
3248                 {
3249                         /* if there are desired flags, check for same and continue if they aren't matched */
3250                         if( wantContentFlags && !(wantContentFlags & allContentFlags) )
3251                                 continue;
3252                         if( wantSurfaceFlags && !(wantSurfaceFlags & allSurfaceFlags) )
3253                                 continue;
3254
3255                         /* store the cumulative flags and return the brush shader (which is mostly useless) */
3256                         *surfaceFlags = allSurfaceFlags;
3257                         *contentFlags = allContentFlags;
3258                         return brush->shaderNum;
3259                 }
3260         }
3261
3262         /* if the point made it this far, it's not inside any brushes */
3263         return -1;
3264 }
3265
3266
3267
3268 /*
3269 ChopBounds()
3270 chops a bounding box by the plane defined by origin and normal
3271 returns qfalse if the bounds is entirely clipped away
3272
3273 this is not exactly the fastest way to do this...
3274 */
3275
3276 qboolean ChopBounds( vec3_t mins, vec3_t maxs, vec3_t origin, vec3_t normal )
3277 {
3278         /* FIXME: rewrite this so it doesn't use bloody brushes */
3279         return qtrue;
3280 }
3281
3282
3283
3284 /*
3285 SetupEnvelopes()
3286 calculates each light's effective envelope,
3287 taking into account brightness, type, and pvs.
3288 */
3289
3290 #define LIGHT_EPSILON   0.125f
3291 #define LIGHT_NUDGE             2.0f
3292
3293 void SetupEnvelopes( qboolean forGrid, qboolean fastFlag )
3294 {
3295         int                     i, x, y, z, x1, y1, z1;
3296         light_t         *light, *light2, **owner;
3297         bspLeaf_t       *leaf;
3298         vec3_t          origin, dir, mins, maxs, nullVector = { 0, 0, 0 };
3299         float           radius, intensity;
3300         light_t         *buckets[ 256 ];
3301
3302
3303         /* early out for weird cases where there are no lights */
3304         if( lights == NULL )
3305                 return;
3306
3307         /* note it */
3308         Sys_FPrintf( SYS_VRB, "--- SetupEnvelopes%s ---\n", fastFlag ? " (fast)" : "" );
3309
3310         /* count lights */
3311         numLights = 0;
3312         numCulledLights = 0;
3313         owner = &lights;
3314         while( *owner != NULL )
3315         {
3316                 /* get light */
3317                 light = *owner;
3318
3319                 /* handle negative lights */
3320                 if( light->photons < 0.0f || light->add < 0.0f )
3321                 {
3322                         light->photons *= -1.0f;
3323                         light->add *= -1.0f;
3324                         light->flags |= LIGHT_NEGATIVE;
3325                 }
3326
3327                 /* sunlight? */
3328                 if( light->type == EMIT_SUN )
3329                 {
3330                         /* special cased */
3331                         light->cluster = 0;
3332                         light->envelope = MAX_WORLD_COORD * 8.0f;
3333                         VectorSet( light->mins, MIN_WORLD_COORD * 8.0f, MIN_WORLD_COORD * 8.0f, MIN_WORLD_COORD * 8.0f );
3334                         VectorSet( light->maxs, MAX_WORLD_COORD * 8.0f, MAX_WORLD_COORD * 8.0f, MAX_WORLD_COORD * 8.0f );
3335                 }
3336
3337                 /* everything else */
3338                 else
3339                 {
3340                         /* get pvs cluster for light */
3341                         light->cluster = ClusterForPointExt( light->origin, LIGHT_EPSILON );
3342
3343                         /* invalid cluster? */
3344                         if( light->cluster < 0 )
3345                         {
3346                                 /* nudge the sample point around a bit */
3347                                 for( x = 0; x < 4; x++ )
3348                                 {
3349                                         /* two's complement 0, 1, -1, 2, -2, etc */
3350                                         x1 = ((x >> 1) ^ (x & 1 ? -1 : 0)) + (x & 1);
3351
3352                                         for( y = 0; y < 4; y++ )
3353                                         {
3354                                                 y1 = ((y >> 1) ^ (y & 1 ? -1 : 0)) + (y & 1);
3355
3356                                                 for( z = 0; z < 4; z++ )
3357                                                 {
3358                                                         z1 = ((z >> 1) ^ (z & 1 ? -1 : 0)) + (z & 1);
3359
3360                                                         /* nudge origin */
3361                                                         origin[ 0 ] = light->origin[ 0 ] + (LIGHT_NUDGE * x1);
3362                                                         origin[ 1 ] = light->origin[ 1 ] + (LIGHT_NUDGE * y1);
3363                                                         origin[ 2 ] = light->origin[ 2 ] + (LIGHT_NUDGE * z1);
3364
3365                                                         /* try at nudged origin */
3366                                                         light->cluster = ClusterForPointExt( origin, LIGHT_EPSILON );
3367                                                         if( light->cluster < 0 )
3368                                                                 continue;
3369
3370                                                         /* set origin */
3371                                                         VectorCopy( origin, light->origin );
3372                                                 }
3373                                         }
3374                                 }
3375                         }
3376
3377                         /* only calculate for lights in pvs and outside of opaque brushes */
3378                         if( light->cluster >= 0 )
3379                         {
3380                                 /* set light fast flag */
3381                                 if( fastFlag )
3382                                         light->flags |= LIGHT_FAST_TEMP;
3383                                 else
3384                                         light->flags &= ~LIGHT_FAST_TEMP;
3385                                 if( light->si && light->si->noFast )
3386                                         light->flags &= ~(LIGHT_FAST | LIGHT_FAST_TEMP);
3387
3388                                 /* clear light envelope */
3389                                 light->envelope = 0;
3390
3391                                 /* handle area lights */
3392                                 if( exactPointToPolygon && light->type == EMIT_AREA && light->w != NULL )
3393                                 {
3394                                         /* ugly hack to calculate extent for area lights, but only done once */
3395                                         VectorScale( light->normal, -1.0f, dir );
3396                                         for( radius = 100.0f; radius < 130000.0f && light->envelope == 0; radius += 10.0f )
3397                                         {
3398                                                 float   factor;
3399
3400                                                 VectorMA( light->origin, radius, light->normal, origin );
3401                                                 factor = PointToPolygonFormFactor( origin, dir, light->w );
3402                                                 if( factor < 0.0f )
3403                                                         factor *= -1.0f;
3404                                                 if( (factor * light->add) <= light->falloffTolerance )
3405                                                         light->envelope = radius;
3406                                         }
3407
3408                                         /* check for fast mode */
3409                                         if( !(light->flags & LIGHT_FAST) && !(light->flags & LIGHT_FAST_TEMP) )
3410                                                 light->envelope = MAX_WORLD_COORD * 8.0f;
3411                                 }
3412                                 else
3413                                 {
3414                                         radius = 0.0f;
3415                                         intensity = light->photons;
3416                                 }
3417
3418                                 /* other calcs */
3419                                 if( light->envelope <= 0.0f )
3420                                 {
3421                                         /* solve distance for non-distance lights */
3422                                         if( !(light->flags & LIGHT_ATTEN_DISTANCE) )
3423                                                 light->envelope = MAX_WORLD_COORD * 8.0f;
3424
3425                                         /* solve distance for linear lights */
3426                                         else if( (light->flags & LIGHT_ATTEN_LINEAR ) )
3427                                                 //% light->envelope = ((intensity / light->falloffTolerance) * linearScale - 1 + radius) / light->fade;
3428                                                 light->envelope = ((intensity * linearScale) - light->falloffTolerance) / light->fade;
3429
3430                                                 /*
3431                                                 add = angle * light->photons * linearScale - (dist * light->fade);
3432                                                 T = (light->photons * linearScale) - (dist * light->fade);
3433                                                 T + (dist * light->fade) = (light->photons * linearScale);
3434                                                 dist * light->fade = (light->photons * linearScale) - T;
3435                                                 dist = ((light->photons * linearScale) - T) / light->fade;
3436                                                 */
3437
3438                                         /* solve for inverse square falloff */
3439                                         else
3440                                                 light->envelope = sqrt( intensity / light->falloffTolerance ) + radius;
3441
3442                                                 /*
3443                                                 add = light->photons / (dist * dist);
3444                                                 T = light->photons / (dist * dist);
3445                                                 T * (dist * dist) = light->photons;
3446                                                 dist = sqrt( light->photons / T );
3447                                                 */
3448                                 }
3449
3450                                 /* chop radius against pvs */
3451                                 {
3452                                         /* clear bounds */
3453                                         ClearBounds( mins, maxs );
3454
3455                                         /* check all leaves */
3456                                         for( i = 0; i < numBSPLeafs; i++ )
3457                                         {
3458                                                 /* get test leaf */
3459                                                 leaf = &bspLeafs[ i ];
3460
3461                                                 /* in pvs? */
3462                                                 if( leaf->cluster < 0 )
3463                                                         continue;
3464                                                 if( ClusterVisible( light->cluster, leaf->cluster ) == qfalse ) /* ydnar: thanks Arnout for exposing my stupid error (this never failed before) */
3465                                                         continue;
3466
3467                                                 /* add this leafs bbox to the bounds */
3468                                                 VectorCopy( leaf->mins, origin );
3469                                                 AddPointToBounds( origin, mins, maxs );
3470                                                 VectorCopy( leaf->maxs, origin );
3471                                                 AddPointToBounds( origin, mins, maxs );
3472                                         }
3473
3474                                         /* test to see if bounds encompass light */
3475                                         for( i = 0; i < 3; i++ )
3476                                         {
3477                                                 if( mins[ i ] > light->origin[ i ] || maxs[ i ] < light->origin[ i ] )
3478                                                 {
3479                                                         //% Sys_Printf( "WARNING: Light PVS bounds (%.0f, %.0f, %.0f) -> (%.0f, %.0f, %.0f)\ndo not encompass light %d (%f, %f, %f)\n",
3480                                                         //%     mins[ 0 ], mins[ 1 ], mins[ 2 ],
3481                                                         //%     maxs[ 0 ], maxs[ 1 ], maxs[ 2 ],
3482                                                         //%     numLights, light->origin[ 0 ], light->origin[ 1 ], light->origin[ 2 ] );
3483                                                         AddPointToBounds( light->origin, mins, maxs );
3484                                                 }
3485                                         }
3486
3487                                         /* chop the bounds by a plane for area lights and spotlights */
3488                                         if( light->type == EMIT_AREA || light->type == EMIT_SPOT )
3489                                                 ChopBounds( mins, maxs, light->origin, light->normal );
3490
3491                                         /* copy bounds */
3492                                         VectorCopy( mins, light->mins );
3493                                         VectorCopy( maxs, light->maxs );
3494
3495                                         /* reflect bounds around light origin */
3496                                         //%     VectorMA( light->origin, -1.0f, origin, origin );
3497                                         VectorScale( light->origin, 2, origin );
3498                                         VectorSubtract( origin, maxs, origin );
3499                                         AddPointToBounds( origin, mins, maxs );
3500                                         //%     VectorMA( light->origin, -1.0f, mins, origin );
3501                                         VectorScale( light->origin, 2, origin );
3502                                         VectorSubtract( origin, mins, origin );
3503                                         AddPointToBounds( origin, mins, maxs );
3504
3505                                         /* calculate spherical bounds */
3506                                         VectorSubtract( maxs, light->origin, dir );
3507                                         radius = (float) VectorLength( dir );
3508
3509                                         /* if this radius is smaller than the envelope, then set the envelope to it */
3510                                         if( radius < light->envelope )
3511                                         {
3512                                                 light->envelope = radius;
3513                                                 //%     Sys_FPrintf( SYS_VRB, "PVS Cull (%d): culled\n", numLights );
3514                                         }
3515                                         //%     else
3516                                         //%             Sys_FPrintf( SYS_VRB, "PVS Cull (%d): failed (%8.0f > %8.0f)\n", numLights, radius, light->envelope );
3517                                 }
3518
3519                                 /* add grid/surface only check */
3520                                 if( forGrid )
3521                                 {
3522                                         if( !(light->flags & LIGHT_GRID) )
3523                                                 light->envelope = 0.0f;
3524                                 }
3525                                 else
3526                                 {
3527                                         if( !(light->flags & LIGHT_SURFACES) )
3528                                                 light->envelope = 0.0f;
3529                                 }
3530                         }
3531
3532                         /* culled? */
3533                         if( light->cluster < 0 || light->envelope <= 0.0f )
3534                         {
3535                                 /* debug code */
3536                                 //%     Sys_Printf( "Culling light: Cluster: %d Envelope: %f\n", light->cluster, light->envelope );
3537
3538                                 /* delete the light */
3539                                 numCulledLights++;
3540                                 *owner = light->next;
3541                                 if( light->w != NULL )
3542                                         free( light->w );
3543                                 free( light );
3544                                 continue;
3545                         }
3546                 }
3547
3548                 /* square envelope */
3549                 light->envelope2 = (light->envelope * light->envelope);
3550
3551                 /* increment light count */
3552                 numLights++;
3553
3554                 /* set next light */
3555                 owner = &((**owner).next);
3556         }
3557
3558         /* bucket sort lights by style */
3559         memset( buckets, 0, sizeof( buckets ) );
3560         light2 = NULL;
3561         for( light = lights; light != NULL; light = light2 )
3562         {
3563                 /* get next light */
3564                 light2 = light->next;
3565
3566                 /* filter into correct bucket */
3567                 light->next = buckets[ light->style ];
3568                 buckets[ light->style ] = light;
3569
3570                 /* if any styled light is present, automatically set nocollapse */
3571                 if( light->style != LS_NORMAL )
3572                         noCollapse = qtrue;
3573         }
3574
3575         /* filter back into light list */
3576         lights = NULL;
3577         for( i = 255; i >= 0; i-- )
3578         {
3579                 light2 = NULL;
3580                 for( light = buckets[ i ]; light != NULL; light = light2 )
3581                 {
3582                         light2 = light->next;
3583                         light->next = lights;
3584                         lights = light;
3585                 }
3586         }
3587
3588         /* emit some statistics */
3589         Sys_Printf( "%9d total lights\n", numLights );
3590         Sys_Printf( "%9d culled lights\n", numCulledLights );
3591 }
3592
3593
3594
3595 /*
3596 CreateTraceLightsForBounds()
3597 creates a list of lights that affect the given bounding box and pvs clusters (bsp leaves)
3598 */
3599
3600 void CreateTraceLightsForBounds( vec3_t mins, vec3_t maxs, vec3_t normal, int numClusters, int *clusters, int flags, trace_t *trace )
3601 {
3602         int                     i;
3603         light_t         *light;
3604         vec3_t          origin, dir, nullVector = { 0.0f, 0.0f, 0.0f };
3605         float           radius, dist, length;
3606
3607
3608         /* potential pre-setup  */
3609         if( numLights == 0 )
3610                 SetupEnvelopes( qfalse, fast );
3611
3612         /* debug code */
3613         //% 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 ] );
3614
3615         /* allocate the light list */
3616         trace->lights = safe_malloc( sizeof( light_t* ) * (numLights + 1) );
3617         trace->numLights = 0;
3618
3619         /* calculate spherical bounds */
3620         VectorAdd( mins, maxs, origin );
3621         VectorScale( origin, 0.5f, origin );
3622         VectorSubtract( maxs, origin, dir );
3623         radius = (float) VectorLength( dir );
3624
3625         /* get length of normal vector */
3626         if( normal != NULL )
3627                 length = VectorLength( normal );
3628         else
3629         {
3630                 normal = nullVector;
3631                 length = 0;
3632         }
3633
3634         /* test each light and see if it reaches the sphere */
3635         /* note: the attenuation code MUST match LightingAtSample() */
3636         for( light = lights; light; light = light->next )
3637         {
3638                 /* check zero sized envelope */
3639                 if( light->envelope <= 0 )
3640                 {
3641                         lightsEnvelopeCulled++;
3642                         continue;
3643                 }
3644
3645                 /* check flags */
3646                 if( !(light->flags & flags) )
3647                         continue;
3648
3649                 /* sunlight skips all this nonsense */
3650                 if( light->type != EMIT_SUN )
3651                 {
3652                         /* sun only? */
3653                         if( sunOnly )
3654                                 continue;
3655
3656                         /* check against pvs cluster */
3657                         if( numClusters > 0 && clusters != NULL )
3658                         {
3659                                 for( i = 0; i < numClusters; i++ )
3660                                 {
3661                                         if( ClusterVisible( light->cluster, clusters[ i ] ) )
3662                                                 break;
3663                                 }
3664
3665                                 /* fixme! */
3666                                 if( i == numClusters )
3667                                 {
3668                                         lightsClusterCulled++;
3669                                         continue;
3670                                 }
3671                         }
3672
3673                         /* if the light's bounding sphere intersects with the bounding sphere then this light needs to be tested */
3674                         VectorSubtract( light->origin, origin, dir );
3675                         dist = VectorLength( dir );
3676                         dist -= light->envelope;
3677                         dist -= radius;
3678                         if( dist > 0 )
3679                         {
3680                                 lightsEnvelopeCulled++;
3681                                 continue;
3682                         }
3683
3684                         /* check bounding box against light's pvs envelope (note: this code never eliminated any lights, so disabling it) */
3685                         #if 0
3686                         skip = qfalse;
3687                         for( i = 0; i < 3; i++ )
3688                         {
3689                                 if( mins[ i ] > light->maxs[ i ] || maxs[ i ] < light->mins[ i ] )
3690                                         skip = qtrue;
3691                         }
3692                         if( skip )
3693                         {
3694                                 lightsBoundsCulled++;
3695                                 continue;
3696                         }
3697                         #endif
3698                 }
3699
3700                 /* planar surfaces (except twosided surfaces) have a couple more checks */
3701                 if( length > 0.0f && trace->twoSided == qfalse )
3702                 {
3703                         /* lights coplanar with a surface won't light it */
3704                         if( !(light->flags & LIGHT_TWOSIDED) && DotProduct( light->normal, normal ) > 0.999f )
3705                         {
3706                                 lightsPlaneCulled++;
3707                                 continue;
3708                         }
3709
3710                         /* check to see if light is behind the plane */
3711                         if( DotProduct( light->origin, normal ) - DotProduct( origin, normal ) < -1.0f )
3712                         {
3713                                 lightsPlaneCulled++;
3714                                 continue;
3715                         }
3716                 }
3717
3718                 /* add this light */
3719                 trace->lights[ trace->numLights++ ] = light;
3720         }
3721
3722         /* make last night null */
3723         trace->lights[ trace->numLights ] = NULL;
3724 }
3725
3726
3727
3728 void FreeTraceLights( trace_t *trace )
3729 {
3730         if( trace->lights != NULL )
3731                 free( trace->lights );
3732 }
3733
3734
3735
3736 /*
3737 CreateTraceLightsForSurface()
3738 creates a list of lights that can potentially affect a drawsurface
3739 */
3740
3741 void CreateTraceLightsForSurface( int num, trace_t *trace )
3742 {
3743         int                                     i;
3744         vec3_t                          mins, maxs, normal;
3745         bspDrawVert_t           *dv;
3746         bspDrawSurface_t        *ds;
3747         surfaceInfo_t           *info;
3748
3749
3750         /* dummy check */
3751         if( num < 0 )
3752                 return;
3753
3754         /* get drawsurface and info */
3755         ds = &bspDrawSurfaces[ num ];
3756         info = &surfaceInfos[ num ];
3757
3758         /* get the mins/maxs for the dsurf */
3759         ClearBounds( mins, maxs );
3760         VectorCopy( bspDrawVerts[ ds->firstVert ].normal, normal );
3761         for( i = 0; i < ds->numVerts; i++ )
3762         {
3763                 dv = &yDrawVerts[ ds->firstVert + i ];
3764                 AddPointToBounds( dv->xyz, mins, maxs );
3765                 if( !VectorCompare( dv->normal, normal ) )
3766                         VectorClear( normal );
3767         }
3768
3769         /* create the lights for the bounding box */
3770         CreateTraceLightsForBounds( mins, maxs, normal, info->numSurfaceClusters, &surfaceClusters[ info->firstSurfaceCluster ], LIGHT_SURFACES, trace );
3771 }
3772
3773 /////////////////////////////////////////////////////////////
3774
3775 #define FLOODLIGHT_CONE_ANGLE                   88      /* degrees */
3776 #define FLOODLIGHT_NUM_ANGLE_STEPS              16
3777 #define FLOODLIGHT_NUM_ELEVATION_STEPS  4
3778 #define FLOODLIGHT_NUM_VECTORS                  (FLOODLIGHT_NUM_ANGLE_STEPS * FLOODLIGHT_NUM_ELEVATION_STEPS)
3779
3780 static vec3_t   floodVectors[ FLOODLIGHT_NUM_VECTORS ];
3781 static int              numFloodVectors = 0;
3782
3783 void SetupFloodLight( void )
3784 {
3785         int             i, j;
3786         float   angle, elevation, angleStep, elevationStep;
3787         const char      *value;
3788         double v1,v2,v3,v4,v5;
3789
3790         /* note it */
3791         Sys_FPrintf( SYS_VRB, "--- SetupFloodLight ---\n" );
3792
3793         /* calculate angular steps */
3794         angleStep = DEG2RAD( 360.0f / FLOODLIGHT_NUM_ANGLE_STEPS );
3795         elevationStep = DEG2RAD( FLOODLIGHT_CONE_ANGLE / FLOODLIGHT_NUM_ELEVATION_STEPS );
3796
3797         /* iterate angle */
3798         angle = 0.0f;
3799         for( i = 0, angle = 0.0f; i < FLOODLIGHT_NUM_ANGLE_STEPS; i++, angle += angleStep )
3800         {
3801                 /* iterate elevation */
3802                 for( j = 0, elevation = elevationStep * 0.5f; j < FLOODLIGHT_NUM_ELEVATION_STEPS; j++, elevation += elevationStep )
3803                 {
3804                         floodVectors[ numFloodVectors ][ 0 ] = sin( elevation ) * cos( angle );
3805                         floodVectors[ numFloodVectors ][ 1 ] = sin( elevation ) * sin( angle );
3806                         floodVectors[ numFloodVectors ][ 2 ] = cos( elevation );
3807                         numFloodVectors++;
3808                 }
3809         }
3810
3811         /* emit some statistics */
3812         Sys_FPrintf( SYS_VRB, "%9d numFloodVectors\n", numFloodVectors );
3813
3814       /* floodlight */
3815         value = ValueForKey( &entities[ 0 ], "_floodlight" );
3816
3817         if( value[ 0 ] != '\0' )
3818         {
3819                 v1=v2=v3=0;
3820                 v4=floodlightDistance;
3821                 v5=floodlightIntensity;
3822
3823                 sscanf( value, "%lf %lf %lf %lf %lf", &v1, &v2, &v3, &v4, &v5);
3824
3825                 floodlightRGB[0]=v1;
3826                 floodlightRGB[1]=v2;
3827                 floodlightRGB[2]=v3;
3828
3829                 if (VectorLength(floodlightRGB)==0)
3830                 {
3831                         VectorSet(floodlightRGB,240,240,255);
3832                 }
3833
3834                 if (v4<1) v4=1024;
3835                 if (v5<1) v5=128;
3836
3837                 floodlightDistance=v4;
3838                 floodlightIntensity=v5;
3839
3840                 floodlighty = qtrue;
3841                 Sys_Printf( "FloodLighting enabled via worldspawn _floodlight key.\n" );
3842         }
3843         else
3844         {
3845                 VectorSet(floodlightRGB,240,240,255);
3846                 //floodlighty = qtrue;
3847                 //Sys_Printf( "FloodLighting enabled via worldspawn _floodlight key.\n" );
3848         }
3849         VectorNormalize(floodlightRGB,floodlightRGB);
3850 }
3851
3852 //27 - lighttracer style ambient occlusion light hack.
3853 //Kudos to the dirtmapping author for most of this source.
3854 void FloodLightRawLightmap( int rawLightmapNum )
3855 {
3856         int                                     i, x, y, sx, sy, *cluster;
3857         float                           *origin, *normal, *floodlight, *floodlight2, average, samples;
3858         rawLightmap_t           *lm;
3859         surfaceInfo_t           *info;
3860         trace_t                         trace;
3861
3862         /* bail if this number exceeds the number of raw lightmaps */
3863         if( rawLightmapNum >= numRawLightmaps )
3864                 return;
3865
3866         /* get lightmap */
3867         lm = &rawLightmaps[ rawLightmapNum ];
3868
3869         memset(&trace,0,sizeof(trace_t));
3870         /* setup trace */
3871         trace.testOcclusion = qtrue;
3872         trace.forceSunlight = qfalse;
3873         trace.twoSided = qtrue;
3874         trace.recvShadows = lm->recvShadows;
3875         trace.numSurfaces = lm->numLightSurfaces;
3876         trace.surfaces = &lightSurfaces[ lm->firstLightSurface ];
3877         trace.inhibitRadius = DEFAULT_INHIBIT_RADIUS;
3878         trace.testAll = qfalse;
3879         trace.distance = 1024;
3880
3881         /* twosided lighting (may or may not be a good idea for lightmapped stuff) */
3882         //trace.twoSided = qfalse;
3883         for( i = 0; i < trace.numSurfaces; i++ )
3884         {
3885                 /* get surface */
3886                 info = &surfaceInfos[ trace.surfaces[ i ] ];
3887
3888                 /* check twosidedness */
3889                 if( info->si->twoSided )
3890                 {
3891                         trace.twoSided = qtrue;
3892                         break;
3893                 }
3894         }
3895
3896         /* gather dirt */
3897         for( y = 0; y < lm->sh; y++ )
3898         {
3899                 for( x = 0; x < lm->sw; x++ )
3900                 {
3901                         /* get luxel */
3902                         cluster = SUPER_CLUSTER( x, y );
3903                         origin = SUPER_ORIGIN( x, y );
3904                         normal = SUPER_NORMAL( x, y );
3905                         floodlight = SUPER_FLOODLIGHT( x, y );
3906
3907                         /* set default dirt */
3908                         *floodlight = 0.0f;
3909
3910                         /* only look at mapped luxels */
3911                         if( *cluster < 0 )
3912                                 continue;
3913
3914                         /* copy to trace */
3915                         trace.cluster = *cluster;
3916                         VectorCopy( origin, trace.origin );
3917                         VectorCopy( normal, trace.normal );
3918
3919
3920
3921                         /* get dirt */
3922                         *floodlight = FloodLightForSample( &trace );
3923                 }
3924         }
3925
3926         /* testing no filtering */
3927         return;
3928
3929         /* filter "dirt" */
3930         for( y = 0; y < lm->sh; y++ )
3931         {
3932                 for( x = 0; x < lm->sw; x++ )
3933                 {
3934                         /* get luxel */
3935                         cluster = SUPER_CLUSTER( x, y );
3936                         floodlight = SUPER_FLOODLIGHT( x, y );
3937
3938                         /* filter dirt by adjacency to unmapped luxels */
3939                         average = *floodlight;
3940                         samples = 1.0f;
3941                         for( sy = (y - 1); sy <= (y + 1); sy++ )
3942                         {
3943                                 if( sy < 0 || sy >= lm->sh )
3944                                         continue;
3945
3946                                 for( sx = (x - 1); sx <= (x + 1); sx++ )
3947                                 {
3948                                         if( sx < 0 || sx >= lm->sw || (sx == x && sy == y) )
3949                                                 continue;
3950
3951                                         /* get neighboring luxel */
3952                                         cluster = SUPER_CLUSTER( sx, sy );
3953                                         floodlight2 = SUPER_FLOODLIGHT( sx, sy );
3954                                         if( *cluster < 0 || *floodlight2 <= 0.0f )
3955                                                 continue;
3956
3957                                         /* add it */
3958                                         average += *floodlight2;
3959                                         samples += 1.0f;
3960                                 }
3961
3962                                 /* bail */
3963                                 if( samples <= 0.0f )
3964                                         break;
3965                         }
3966
3967                         /* bail */
3968                         if( samples <= 0.0f )
3969                                 continue;
3970
3971                         /* scale dirt */
3972                         *floodlight = average / samples;
3973                 }
3974         }
3975 }
3976
3977 /*
3978 FloodLightForSample()
3979 calculates floodlight value for a given sample
3980 once again, kudos to the dirtmapping coder
3981 */
3982 float FloodLightForSample( trace_t *trace )
3983 {
3984         int             i;
3985         float   d;
3986         float   contribution;
3987         int     sub = 0;
3988         float   gatherLight, outLight;
3989         vec3_t  normal, worldUp, myUp, myRt, direction, displacement;
3990         float   dd;
3991         int     vecs = 0;
3992
3993         gatherLight=0;
3994         /* dummy check */
3995         //if( !dirty )
3996         //      return 1.0f;
3997         if( trace == NULL || trace->cluster < 0 )
3998                 return 0.0f;
3999
4000
4001         /* setup */
4002         dd = floodlightDistance;
4003         VectorCopy( trace->normal, normal );
4004
4005         /* check if the normal is aligned to the world-up */
4006         if( normal[ 0 ] == 0.0f && normal[ 1 ] == 0.0f )
4007         {
4008                 if( normal[ 2 ] == 1.0f )
4009                 {
4010                         VectorSet( myRt, 1.0f, 0.0f, 0.0f );
4011                         VectorSet( myUp, 0.0f, 1.0f, 0.0f );
4012                 }
4013                 else if( normal[ 2 ] == -1.0f )
4014                 {
4015                         VectorSet( myRt, -1.0f, 0.0f, 0.0f );
4016                         VectorSet( myUp,  0.0f, 1.0f, 0.0f );
4017                 }
4018         }
4019         else
4020         {
4021                 VectorSet( worldUp, 0.0f, 0.0f, 1.0f );
4022                 CrossProduct( normal, worldUp, myRt );
4023                 VectorNormalize( myRt, myRt );
4024                 CrossProduct( myRt, normal, myUp );
4025                 VectorNormalize( myUp, myUp );
4026         }
4027
4028         /* iterate through ordered vectors */
4029         for( i = 0; i < numFloodVectors; i++ )
4030         {
4031                 if (floodlight_lowquality==qtrue)
4032         {
4033                         if (rand()%10 != 0 ) continue;
4034                 }
4035
4036                 vecs++;
4037
4038                 /* transform vector into tangent space */
4039                 direction[ 0 ] = myRt[ 0 ] * floodVectors[ i ][ 0 ] + myUp[ 0 ] * floodVectors[ i ][ 1 ] + normal[ 0 ] * floodVectors[ i ][ 2 ];
4040                 direction[ 1 ] = myRt[ 1 ] * floodVectors[ i ][ 0 ] + myUp[ 1 ] * floodVectors[ i ][ 1 ] + normal[ 1 ] * floodVectors[ i ][ 2 ];
4041                 direction[ 2 ] = myRt[ 2 ] * floodVectors[ i ][ 0 ] + myUp[ 2 ] * floodVectors[ i ][ 1 ] + normal[ 2 ] * floodVectors[ i ][ 2 ];
4042
4043                 /* set endpoint */
4044                 VectorMA( trace->origin, dd, direction, trace->end );
4045
4046                 //VectorMA( trace->origin, 1, direction, trace->origin );
4047
4048                 SetupTrace( trace );
4049                 /* trace */
4050                 TraceLine( trace );
4051                 contribution=1;
4052
4053                 if (trace->compileFlags & C_SKY )
4054                 {
4055                         contribution=1.0f;
4056                 }
4057                 else if ( trace->opaque )
4058                 {
4059                         VectorSubtract( trace->hit, trace->origin, displacement );
4060                         d=VectorLength( displacement );
4061
4062                         // d=trace->distance;
4063                         //if (d>256) gatherDirt+=1;
4064                         contribution=d/dd;
4065                         if (contribution>1) contribution=1.0f;
4066
4067                         //gatherDirt += 1.0f - ooDepth * VectorLength( displacement );
4068                 }
4069
4070                 gatherLight+=contribution;
4071         }
4072
4073         /* early out */
4074         if( gatherLight <= 0.0f )
4075                 return 0.0f;
4076
4077         sub=vecs;
4078
4079         if (sub<1) sub=1;
4080         gatherLight/=(sub);
4081
4082         outLight=gatherLight;
4083         if( outLight > 1.0f )
4084                 outLight = 1.0f;
4085
4086         /* return to sender */
4087         return outLight;
4088 }
4089