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