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