tools/quake3/q3map2/light_ydnar.c

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