2 Copyright (C) 1999-2007 id Software, Inc. and contributors.
3 For a list of contributors, see the accompanying CONTRIBUTORS file.
5 This file is part of GtkRadiant.
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.
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.
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
21 ----------------------------------------------------------------------------------
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."
26 ------------------------------------------------------------------------------- */
43 ydnar: moved to here 2001-02-04
46 void ColorToBytes( const float *color, byte *colorBytes, float scale )
52 /* ydnar: scaling necessary for simulating r_overbrightBits on external lightmaps */
56 /* make a local copy */
57 VectorScale( color, scale, sample );
59 /* handle negative light */
60 if( sample[ 0 ] < 0.0f )
62 if( sample[ 1 ] < 0.0f )
64 if( sample[ 2 ] < 0.0f )
67 /* clamp with color normalization */
69 if( sample[ 1 ] > max )
71 if( sample[ 2 ] > max )
74 VectorScale( sample, (255.0f / max), sample );
77 colorBytes[ 0 ] = sample[ 0 ];
78 colorBytes[ 1 ] = sample[ 1 ];
79 colorBytes[ 2 ] = sample[ 2 ];
84 /* -------------------------------------------------------------------------------
86 this section deals with phong shading (normal interpolation across brush faces)
88 ------------------------------------------------------------------------------- */
92 smooths together coincident vertex normals across the bsp
95 #define MAX_SAMPLES 256
96 #define THETA_EPSILON 0.000001
97 #define EQUAL_NORMAL_EPSILON 0.01
99 void SmoothNormals( void )
101 int i, j, k, f, cs, numVerts, numVotes, fOld, start;
102 float shadeAngle, defaultShadeAngle, maxShadeAngle, dot, testAngle;
103 bspDrawSurface_t *ds;
107 vec3_t average, diff;
108 int indexes[ MAX_SAMPLES ];
109 vec3_t votes[ MAX_SAMPLES ];
112 /* allocate shade angle table */
113 shadeAngles = safe_malloc( numBSPDrawVerts * sizeof( float ) );
114 memset( shadeAngles, 0, numBSPDrawVerts * sizeof( float ) );
116 /* allocate smoothed table */
117 cs = (numBSPDrawVerts / 8) + 1;
118 smoothed = safe_malloc( cs );
119 memset( smoothed, 0, cs );
121 /* set default shade angle */
122 defaultShadeAngle = DEG2RAD( shadeAngleDegrees );
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++ )
130 ds = &bspDrawSurfaces[ i ];
132 /* get shader for shade angle */
133 si = surfaceInfos[ i ].si;
134 if( si->shadeAngleDegrees )
135 shadeAngle = DEG2RAD( si->shadeAngleDegrees );
137 shadeAngle = defaultShadeAngle;
138 if( shadeAngle > maxShadeAngle )
139 maxShadeAngle = shadeAngle;
142 for( j = 0; j < ds->numVerts; j++ )
144 f = ds->firstVert + j;
145 shadeAngles[ f ] = shadeAngle;
146 if( ds->surfaceType == MST_TRIANGLE_SOUP )
147 smoothed[ f >> 3 ] |= (1 << (f & 7));
150 /* ydnar: optional force-to-trisoup */
151 if( trisoup && ds->surfaceType == MST_PLANAR )
153 ds->surfaceType = MST_TRIANGLE_SOUP;
154 ds->lightmapNum[ 0 ] = -3;
158 /* bail if no surfaces have a shade angle */
159 if( maxShadeAngle == 0 )
168 start = I_FloatTime();
170 /* go through the list of vertexes */
171 for( i = 0; i < numBSPDrawVerts; i++ )
174 f = 10 * i / numBSPDrawVerts;
178 Sys_Printf( "%i...", f );
181 /* already smoothed? */
182 if( smoothed[ i >> 3 ] & (1 << (i & 7)) )
186 VectorClear( average );
190 /* build a table of coincident vertexes */
191 for( j = i; j < numBSPDrawVerts && numVerts < MAX_SAMPLES; j++ )
193 /* already smoothed? */
194 if( smoothed[ j >> 3 ] & (1 << (j & 7)) )
198 if( VectorCompare( yDrawVerts[ i ].xyz, yDrawVerts[ j ].xyz ) == qfalse )
201 /* use smallest shade angle */
202 shadeAngle = (shadeAngles[ i ] < shadeAngles[ j ] ? shadeAngles[ i ] : shadeAngles[ j ]);
204 /* check shade angle */
205 dot = DotProduct( bspDrawVerts[ i ].normal, bspDrawVerts[ j ].normal );
208 else if( dot < -1.0 )
210 testAngle = acos( dot ) + THETA_EPSILON;
211 if( testAngle >= shadeAngle )
213 //Sys_Printf( "F(%3.3f >= %3.3f) ", RAD2DEG( testAngle ), RAD2DEG( shadeAngle ) );
216 //Sys_Printf( "P(%3.3f < %3.3f) ", RAD2DEG( testAngle ), RAD2DEG( shadeAngle ) );
218 /* add to the list */
219 indexes[ numVerts++ ] = j;
222 smoothed[ j >> 3 ] |= (1 << (j & 7));
224 /* see if this normal has already been voted */
225 for( k = 0; k < numVotes; k++ )
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 )
234 /* add a new vote? */
235 if( k == numVotes && numVotes < MAX_SAMPLES )
237 VectorAdd( average, bspDrawVerts[ j ].normal, average );
238 VectorCopy( bspDrawVerts[ j ].normal, votes[ numVotes ] );
243 /* don't average for less than 2 verts */
248 if( VectorNormalize( average, average ) > 0 )
251 for( j = 0; j < numVerts; j++ )
252 VectorCopy( average, yDrawVerts[ indexes[ j ] ].normal );
256 /* free the tables */
261 Sys_Printf( " (%i)\n", (int) (I_FloatTime() - start) );
266 /* -------------------------------------------------------------------------------
268 this section deals with phong shaded lightmap tracing
270 ------------------------------------------------------------------------------- */
272 /* 9th rewrite (recursive subdivision of a lightmap triangle) */
276 calculates the st tangent vectors for normalmapping
279 static qboolean CalcTangentVectors( int numVerts, bspDrawVert_t **dv, vec3_t *stv, vec3_t *ttv )
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 )
292 for( i = 0; i < numVerts; i++ )
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;
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 ];
305 VectorSubtract( stv[ i ], dv[ i ]->xyz, stv[ i ] );
306 VectorNormalize( stv[ i ], stv[ i ] );
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;
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 ];
319 VectorSubtract( ttv[ i ], dv[ i ]->xyz, ttv[ i ] );
320 VectorNormalize( ttv[ i ], ttv[ i ] );
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 ] );
327 /* return to caller */
336 perterbs the normal by the shader's normalmap in tangent space
339 static void PerturbNormal( bspDrawVert_t *dv, shaderInfo_t *si, vec3_t pNormal, vec3_t stv[ 3 ], vec3_t ttv[ 3 ] )
346 VectorCopy( dv->normal, pNormal );
348 /* sample normalmap */
349 if( RadSampleImage( si->normalImage->pixels, si->normalImage->width, si->normalImage->height, dv->st, bump ) == qfalse )
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);
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 );
361 /* renormalize and return */
362 VectorNormalize( pNormal, pNormal );
369 maps a luxel for triangle bv at
373 #define BOGUS_NUDGE -99999.0f
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 ] )
377 int i, x, y, numClusters, *clusters, pointCluster, *cluster;
378 float *luxel, *origin, *normal, d, lightmapSampleOffset;
384 static float nudges[][ 2 ] =
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 }
399 /* find luxel xy coords (fixme: subtract 0.5?) */
400 x = dv->lightmap[ 0 ][ 0 ];
401 y = dv->lightmap[ 0 ][ 1 ];
404 else if( x >= lm->sw )
408 else if( y >= lm->sh )
411 /* set shader and cluster list */
415 numClusters = info->numSurfaceClusters;
416 clusters = &surfaceClusters[ info->firstSurfaceCluster ];
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 );
431 /* don't attempt to remap occluded luxels for planar surfaces */
432 if( (*cluster) == CLUSTER_OCCLUDED && lm->plane != NULL )
435 /* only average the normal for premapped luxels */
436 else if( (*cluster) >= 0 )
438 /* do bumpmap calculations */
440 PerturbNormal( dv, si, pNormal, stv, ttv );
442 VectorCopy( dv->normal, pNormal );
444 /* add the additional normal data */
445 VectorAdd( normal, pNormal, normal );
450 /* otherwise, unmapped luxels (*cluster == CLUSTER_UNMAPPED) will have their full attributes calculated */
454 /* axial lightmap projection */
455 if( lm->vecs != NULL )
457 /* calculate an origin for the sample from the lightmap vectors */
458 VectorCopy( lm->origin, origin );
459 for( i = 0; i < 3; i++ )
461 /* add unless it's the axis, which is taken care of later */
462 if( i == lm->axisNum )
464 origin[ i ] += (x * lm->vecs[ 0 ][ i ]) + (y * lm->vecs[ 1 ][ i ]);
467 /* project the origin onto the plane */
468 d = DotProduct( origin, plane ) - plane[ 3 ];
469 d /= plane[ lm->axisNum ];
470 origin[ lm->axisNum ] -= d;
473 /* non axial lightmap projection (explicit xyz) */
475 VectorCopy( dv->xyz, origin );
477 /* planar surfaces have precalculated lightmap vectors for nudging */
478 if( lm->plane != NULL )
480 VectorCopy( lm->vecs[ 0 ], vecs[ 0 ] );
481 VectorCopy( lm->vecs[ 1 ], vecs[ 1 ] );
482 VectorCopy( lm->plane, vecs[ 2 ] );
485 /* non-planar surfaces must calculate them */
489 VectorCopy( plane, vecs[ 2 ] );
491 VectorCopy( dv->normal, vecs[ 2 ] );
492 MakeNormalVectors( vecs[ 2 ], vecs[ 0 ], vecs[ 1 ] );
495 /* push the origin off the surface a bit */
497 lightmapSampleOffset = si->lightmapSampleOffset;
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;
505 origin[ lm->axisNum ] += lightmapSampleOffset;
508 pointCluster = ClusterForPointExtFilter( origin, LUXEL_EPSILON, numClusters, clusters );
510 /* another retarded hack, storing nudge count in luxel[ 1 ] */
513 /* point in solid? */
514 if( pointCluster < 0 )
516 /* nudge the the location around */
518 while( nudge[ 0 ] > BOGUS_NUDGE && pointCluster < 0 )
520 /* nudge the vector around a bit */
521 for( i = 0; i < 3; i++ )
523 /* set nudged point*/
524 nudged[ i ] = origin[ i ] + (nudge[ 0 ] * vecs[ 0 ][ i ]) + (nudge[ 1 ] * vecs[ 1 ][ i ]);
528 /* get pvs cluster */
529 pointCluster = ClusterForPointExtFilter( nudged, LUXEL_EPSILON, numClusters, clusters ); //% + 0.625 );
530 if( pointCluster >= 0 )
531 VectorCopy( nudged, origin );
536 /* as a last resort, if still in solid, try drawvert origin offset by normal */
537 if( pointCluster < 0 && si != NULL )
539 VectorMA( dv->xyz, lightmapSampleOffset, dv->normal, nudged );
540 pointCluster = ClusterForPointExtFilter( nudged, LUXEL_EPSILON, numClusters, clusters );
541 if( pointCluster >= 0 )
542 VectorCopy( nudged, origin );
547 if( pointCluster < 0 )
549 (*cluster) = CLUSTER_OCCLUDED;
550 VectorClear( origin );
551 VectorClear( normal );
557 //% Sys_Printf( "%f %f %f\n", origin[ 0 ], origin[ 1 ], origin[ 2 ] );
559 /* do bumpmap calculations */
561 PerturbNormal( dv, si, pNormal, stv, ttv );
563 VectorCopy( dv->normal, pNormal );
565 /* store the cluster and normal */
566 (*cluster) = pointCluster;
567 VectorCopy( pNormal, normal );
569 /* store explicit mapping pass and implicit mapping pass */
584 recursively subdivides a triangle until its edges are shorter
585 than the distance between two luxels (thanks jc :)
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 ] )
590 bspDrawVert_t mid, *dv2[ 3 ];
594 /* map the vertexes */
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 );
604 float *a, *b, dx, dy, dist, maxDist;
607 /* find the longest edge and split it */
610 for( i = 0; i < 3; i++ )
613 a = dv[ i ]->lightmap[ 0 ];
614 b = dv[ (i + 1) % 3 ]->lightmap[ 0 ];
617 dx = a[ 0 ] - b[ 0 ];
618 dy = a[ 1 ] - b[ 1 ];
619 dist = (dx * dx) + (dy * dy); //% sqrt( (dx * dx) + (dy * dy) );
629 /* try to early out */
630 if( max < 0 || maxDist <= subdivideThreshold ) /* ydnar: was i < 0 instead of max < 0 (?) */
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 );
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 );
641 /* recurse to first triangle */
642 VectorCopy( dv, dv2 );
644 MapTriangle_r( lm, info, dv2, plane, stv, ttv );
646 /* recurse to second triangle */
647 VectorCopy( dv, dv2 );
648 dv2[ (max + 1) % 3 ] = ∣
649 MapTriangle_r( lm, info, dv2, plane, stv, ttv );
656 seed function for MapTriangle_r()
657 requires a cw ordered triangle
660 static qboolean MapTriangle( rawLightmap_t *lm, surfaceInfo_t *info, bspDrawVert_t *dv[ 3 ], qboolean mapNonAxial )
664 vec3_t *stv, *ttv, stvStatic[ 3 ], ttvStatic[ 3 ];
667 /* get plane if possible */
668 if( lm->plane != NULL )
670 VectorCopy( lm->plane, plane );
671 plane[ 3 ] = lm->plane[ 3 ];
674 /* otherwise make one from the points */
675 else if( PlaneFromPoints( plane, dv[ 0 ]->xyz, dv[ 1 ]->xyz, dv[ 2 ]->xyz ) == qfalse )
678 /* check to see if we need to calculate texture->world tangent vectors */
679 if( info->si->normalImage != NULL && CalcTangentVectors( 3, dv, stvStatic, ttvStatic ) )
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 );
695 /* 2002-11-20: prefer axial triangle edges */
698 /* subdivide the triangle */
699 MapTriangle_r( lm, info, dv, plane, stv, ttv );
703 for( i = 0; i < 3; i++ )
706 bspDrawVert_t *dv2[ 3 ];
710 a = dv[ i ]->lightmap[ 0 ];
711 b = dv[ (i + 1) % 3 ]->lightmap[ 0 ];
713 /* make degenerate triangles for mapping edges */
714 if( fabs( a[ 0 ] - b[ 0 ] ) < 0.01f || fabs( a[ 1 ] - b[ 1 ] ) < 0.01f )
717 dv2[ 1 ] = dv[ (i + 1) % 3 ];
718 dv2[ 2 ] = dv[ (i + 1) % 3 ];
720 /* map the degenerate triangle */
721 MapTriangle_r( lm, info, dv2, plane, stv, ttv );
732 recursively subdivides a quad until its edges are shorter
733 than the distance between two luxels
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 ] )
738 bspDrawVert_t mid[ 2 ], *dv2[ 4 ];
745 float *a, *b, dx, dy, dist, maxDist;
748 /* find the longest edge and split it */
751 for( i = 0; i < 4; i++ )
754 a = dv[ i ]->lightmap[ 0 ];
755 b = dv[ (i + 1) % 4 ]->lightmap[ 0 ];
758 dx = a[ 0 ] - b[ 0 ];
759 dy = a[ 1 ] - b[ 1 ];
760 dist = (dx * dx) + (dy * dy); //% sqrt( (dx * dx) + (dy * dy) );
770 /* try to early out */
771 if( max < 0 || maxDist <= subdivideThreshold )
775 /* we only care about even/odd edges */
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 ] );
782 /* map the vertexes */
783 MapSingleLuxel( lm, info, &mid[ 0 ], plane, 1, stv, ttv );
784 MapSingleLuxel( lm, info, &mid[ 1 ], plane, 1, stv, ttv );
789 /* recurse to first quad */
791 dv2[ 1 ] = &mid[ 0 ];
792 dv2[ 2 ] = &mid[ 1 ];
794 MapQuad_r( lm, info, dv2, plane, stv, ttv );
796 /* recurse to second quad */
797 dv2[ 0 ] = &mid[ 0 ];
800 dv2[ 3 ] = &mid[ 1 ];
801 MapQuad_r( lm, info, dv2, plane, stv, ttv );
807 /* recurse to first quad */
810 dv2[ 2 ] = &mid[ 0 ];
811 dv2[ 3 ] = &mid[ 1 ];
812 MapQuad_r( lm, info, dv2, plane, stv, ttv );
814 /* recurse to second quad */
815 dv2[ 0 ] = &mid[ 1 ];
816 dv2[ 1 ] = &mid[ 0 ];
819 MapQuad_r( lm, info, dv2, plane, stv, ttv );
827 seed function for MapQuad_r()
828 requires a cw ordered triangle quad
831 #define QUAD_PLANAR_EPSILON 0.5f
833 static qboolean MapQuad( rawLightmap_t *lm, surfaceInfo_t *info, bspDrawVert_t *dv[ 4 ] )
837 vec3_t *stv, *ttv, stvStatic[ 4 ], ttvStatic[ 4 ];
840 /* get plane if possible */
841 if( lm->plane != NULL )
843 VectorCopy( lm->plane, plane );
844 plane[ 3 ] = lm->plane[ 3 ];
847 /* otherwise make one from the points */
848 else if( PlaneFromPoints( plane, dv[ 0 ]->xyz, dv[ 1 ]->xyz, dv[ 2 ]->xyz ) == qfalse )
851 /* 4th point must fall on the plane */
852 dist = DotProduct( plane, dv[ 3 ]->xyz ) - plane[ 3 ];
853 if( fabs( dist ) > QUAD_PLANAR_EPSILON )
856 /* check to see if we need to calculate texture->world tangent vectors */
857 if( info->si->normalImage != NULL && CalcTangentVectors( 4, dv, stvStatic, ttvStatic ) )
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 );
874 /* subdivide the quad */
875 MapQuad_r( lm, info, dv, plane, stv, ttv );
883 maps the locations, normals, and pvs clusters for a raw lightmap
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)
888 void MapRawLightmap( int rawLightmapNum )
890 int n, num, i, x, y, sx, sy, pw[ 5 ], r, *cluster, mapNonAxial;
891 float *luxel, *origin, *normal, samples, radius, pass;
893 bspDrawSurface_t *ds;
895 mesh_t src, *subdivided, *mesh;
896 bspDrawVert_t *verts, *dv[ 4 ], fake;
899 /* bail if this number exceeds the number of raw lightmaps */
900 if( rawLightmapNum >= numRawLightmaps )
904 lm = &rawLightmaps[ rawLightmapNum ];
906 /* -----------------------------------------------------------------
907 map referenced surfaces onto the raw lightmap
908 ----------------------------------------------------------------- */
910 /* walk the list of surfaces on this raw lightmap */
911 for( n = 0; n < lm->numLightSurfaces; n++ )
913 /* with > 1 surface per raw lightmap, clear occluded */
916 for( y = 0; y < lm->sh; y++ )
918 for( x = 0; x < lm->sw; x++ )
921 cluster = SUPER_CLUSTER( x, y );
923 *cluster = CLUSTER_UNMAPPED;
929 num = lightSurfaces[ lm->firstLightSurface + n ];
930 ds = &bspDrawSurfaces[ num ];
931 info = &surfaceInfos[ num ];
933 /* bail if no lightmap to calculate */
940 /* map the surface onto the lightmap origin/cluster/normal buffers */
941 switch( ds->surfaceType )
945 verts = yDrawVerts + ds->firstVert;
947 /* map the triangles */
948 for( mapNonAxial = 0; mapNonAxial < 2; mapNonAxial++ )
950 for( i = 0; i < ds->numIndexes; i += 3 )
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 );
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 );
968 /* fit it to the curve and remove colinear verts on rows/columns */
969 PutMeshOnCurve( *subdivided );
970 mesh = RemoveLinearMeshColumnsRows( subdivided );
971 FreeMesh( subdivided );
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 ] );
987 /* map the mesh quads */
990 for( mapNonAxial = 0; mapNonAxial < 2; mapNonAxial++ )
992 for( y = 0; y < (mesh->height - 1); y++ )
994 for( x = 0; x < (mesh->width - 1); x++ )
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 ] */
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 );
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 );
1023 for( y = 0; y < (mesh->height - 1); y++ )
1025 for( x = 0; x < (mesh->width - 1); x++ )
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);
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 ) )
1045 /* get drawverts and map first triangle */
1046 MapTriangle( lm, info, dv, mapNonAxial );
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 );
1066 /* -----------------------------------------------------------------
1067 average and clean up luxel normals
1068 ----------------------------------------------------------------- */
1070 /* walk the luxels */
1071 for( y = 0; y < lm->sh; y++ )
1073 for( x = 0; x < lm->sw; x++ )
1076 luxel = SUPER_LUXEL( 0, x, y );
1077 normal = SUPER_NORMAL( x, y );
1078 cluster = SUPER_CLUSTER( x, y );
1080 /* only look at mapped luxels */
1084 /* the normal data could be the sum of multiple samples */
1085 if( luxel[ 3 ] > 1.0f )
1086 VectorNormalize( normal, normal );
1088 /* mark this luxel as having only one normal */
1093 /* non-planar surfaces stop here */
1094 if( lm->plane == NULL )
1097 /* -----------------------------------------------------------------
1098 map occluded or unuxed luxels
1099 ----------------------------------------------------------------- */
1101 /* walk the luxels */
1102 radius = floor( superSample / 2 );
1103 radius = radius > 0 ? radius : 1.0f;
1105 for( pass = 2.0f; pass <= radius; pass += 1.0f )
1107 for( y = 0; y < lm->sh; y++ )
1109 for( x = 0; x < lm->sw; x++ )
1112 luxel = SUPER_LUXEL( 0, x, y );
1113 normal = SUPER_NORMAL( x, y );
1114 cluster = SUPER_CLUSTER( x, y );
1116 /* only look at unmapped luxels */
1117 if( *cluster != CLUSTER_UNMAPPED )
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;
1126 for( sy = (y - 1); sy <= (y + 1); sy++ )
1128 if( sy < 0 || sy >= lm->sh )
1131 for( sx = (x - 1); sx <= (x + 1); sx++ )
1133 if( sx < 0 || sx >= lm->sw || (sx == x && sy == y) )
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 );
1142 /* only consider luxels mapped in previous passes */
1143 if( *cluster < 0 || luxel[ 0 ] >= pass )
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 ];
1154 if( samples == 0.0f )
1158 VectorDivide( fake.xyz, samples, fake.xyz );
1159 //% VectorDivide( fake.normal, samples, fake.normal );
1160 if( VectorNormalize( fake.normal, fake.normal ) == 0.0f )
1163 /* map the fake vert */
1164 MapSingleLuxel( lm, NULL, &fake, lm->plane, pass, NULL, NULL );
1169 /* -----------------------------------------------------------------
1170 average and clean up luxel normals
1171 ----------------------------------------------------------------- */
1173 /* walk the luxels */
1174 for( y = 0; y < lm->sh; y++ )
1176 for( x = 0; x < lm->sw; x++ )
1179 luxel = SUPER_LUXEL( 0, x, y );
1180 normal = SUPER_NORMAL( x, y );
1181 cluster = SUPER_CLUSTER( x, y );
1183 /* only look at mapped luxels */
1187 /* the normal data could be the sum of multiple samples */
1188 if( luxel[ 3 ] > 1.0f )
1189 VectorNormalize( normal, normal );
1191 /* mark this luxel as having only one normal */
1199 for( y = 0; y < lm->sh; y++ )
1201 for( x = 0; x < lm->sw; x++ )
1206 cluster = SUPER_CLUSTER( x, y );
1207 origin = SUPER_ORIGIN( x, y );
1208 normal = SUPER_NORMAL( x, y );
1209 luxel = SUPER_LUXEL( x, y );
1214 /* check if within the bounding boxes of all surfaces referenced */
1215 ClearBounds( mins, maxs );
1216 for( n = 0; n < lm->numLightSurfaces; n++ )
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) )
1230 if( n < lm->numLightSurfaces )
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 ],
1249 calculates the pvs cluster, origin, normal of a sub-luxel
1252 static qboolean SubmapRawLuxel( rawLightmap_t *lm, int x, int y, float bx, float by, int *sampleCluster, vec3_t sampleOrigin, vec3_t sampleNormal )
1254 int i, *cluster, *cluster2;
1255 float *origin, *origin2, *normal; //% , *normal2;
1256 vec3_t originVecs[ 2 ]; //% , normalVecs[ 2 ];
1259 /* calulate x vector */
1260 if( (x < (lm->sw - 1) && bx >= 0.0f) || (x == 0 && bx <= 0.0f) )
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 );
1269 else if( (x > 0 && bx <= 0.0f) || (x == (lm->sw - 1) && bx >= 0.0f) )
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 );
1279 Sys_Printf( "WARNING: Spurious lightmap S vector\n" );
1281 VectorSubtract( origin2, origin, originVecs[ 0 ] );
1282 //% VectorSubtract( normal2, normal, normalVecs[ 0 ] );
1284 /* calulate y vector */
1285 if( (y < (lm->sh - 1) && bx >= 0.0f) || (y == 0 && bx <= 0.0f) )
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 );
1294 else if( (y > 0 && bx <= 0.0f) || (y == (lm->sh - 1) && bx >= 0.0f) )
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 );
1304 Sys_Printf( "WARNING: Spurious lightmap T vector\n" );
1306 VectorSubtract( origin2, origin, originVecs[ 1 ] );
1307 //% VectorSubtract( normal2, normal, normalVecs[ 1 ] );
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 ]);
1316 *sampleCluster = ClusterForPointExtFilter( sampleOrigin, (LUXEL_EPSILON * 2), lm->numLightClusters, lm->lightClusters );
1317 if( *sampleCluster < 0 )
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 )
1325 normal = SUPER_NORMAL( x, y );
1326 VectorCopy( normal, sampleNormal );
1334 SubsampleRawLuxel_r()
1335 recursively subsamples a luxel until its color gradient is low enough or subsampling limit is reached
1338 void SubsampleRawLuxel_r( rawLightmap_t *lm, trace_t *trace, vec3_t sampleOrigin, int x, int y, float bias, float *lightLuxel )
1340 int b, samples, mapped, lighted;
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;
1349 if( lightLuxel[ 3 ] >= lightSamples )
1353 VectorClear( total );
1357 /* make 2x2 subsample stamp */
1358 for( b = 0; b < 4; b++ )
1361 VectorCopy( sampleOrigin, origin[ b ] );
1363 /* calculate position */
1364 if( !SubmapRawLuxel( lm, x, y, (bias * biasDirs[ b ][ 0 ]), (bias * biasDirs[ b ][ 1 ]), &cluster[ b ], origin[ b ], normal[ b ] ) )
1371 /* increment sample count */
1372 luxel[ b ][ 3 ] = lightLuxel[ 3 ] + 1.0f;
1375 trace->cluster = *cluster;
1376 VectorCopy( origin[ b ], trace->origin );
1377 VectorCopy( normal[ b ], trace->normal );
1380 //% LightContributionToSample( light, cluster[ b ], origin[ b ], normal[ b ], luxel[ b ], qtrue, qfalse, lm->numLightSurfaces, &lightSurfaces[ lm->firstLightSurface ] );
1381 LightContributionToSample( trace );
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 )
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 )
1395 for( b = 0; b < 4; b++ )
1397 if( cluster[ b ] < 0 )
1399 SubsampleRawLuxel_r( lm, trace, origin[ b ], x, y, (bias * 0.25f), luxel[ b ] );
1404 //% VectorClear( color );
1406 VectorCopy( lightLuxel, color );
1408 for( b = 0; b < 4; b++ )
1410 if( cluster[ b ] < 0 )
1412 VectorAdd( color, luxel[ b ], color );
1420 color[ 0 ] /= samples;
1421 color[ 1 ] /= samples;
1422 color[ 2 ] /= samples;
1425 VectorCopy( color, lightLuxel );
1426 lightLuxel[ 3 ] += 1.0f;
1433 IlluminateRawLightmap()
1434 illuminates the luxels
1437 #define LIGHT_LUXEL( x, y ) (lightLuxels + ((((y) * lm->sw) + (x)) * SUPER_LUXEL_SIZE))
1439 void IlluminateRawLightmap( int rawLightmapNum )
1441 int i, t, x, y, sx, sy, size, llSize, luxelFilterRadius, lightmapNum;
1442 int *cluster, *cluster2, mapped, lighted, totalLighted;
1444 surfaceInfo_t *info;
1445 qboolean filterColor, filterDir;
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 } };
1454 /* bail if this number exceeds the number of raw lightmaps */
1455 if( rawLightmapNum >= numRawLightmaps )
1459 lm = &rawLightmaps[ rawLightmapNum ];
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;
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++ )
1474 info = &surfaceInfos[ trace.surfaces[ i ] ];
1476 /* check twosidedness */
1477 if( info->si->twoSided )
1479 trace.twoSided = qtrue;
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 );
1487 /* -----------------------------------------------------------------
1489 ----------------------------------------------------------------- */
1491 /* test debugging state */
1492 if( debugSurfaces || debugAxis || debugCluster || debugOrigin || normalmap )
1494 /* debug fill the luxels */
1495 for( y = 0; y < lm->sh; y++ )
1497 for( x = 0; x < lm->sw; x++ )
1500 cluster = SUPER_CLUSTER( x, y );
1502 /* only fill mapped luxels */
1506 /* get particulars */
1507 luxel = SUPER_LUXEL( 0, x, y );
1508 origin = SUPER_ORIGIN( x, y );
1509 normal = SUPER_NORMAL( x, y );
1511 /* color the luxel with raw lightmap num? */
1513 VectorCopy( debugColors[ rawLightmapNum % 12 ], luxel );
1515 /* color the luxel with lightmap axis? */
1516 else if( debugAxis )
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;
1523 /* color the luxel with luxel cluster? */
1524 else if( debugCluster )
1525 VectorCopy( debugColors[ *cluster % 12 ], luxel );
1527 /* color the luxel with luxel origin? */
1528 else if( debugOrigin )
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 ]);
1538 /* color the luxel with the normal */
1539 else if( normalmap )
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;
1547 numLuxelsIlluminated++;
1554 /* allocate temporary per-light luxel storage */
1555 llSize = lm->sw * lm->sh * SUPER_LUXEL_SIZE * sizeof( float );
1556 lightLuxels = safe_malloc( llSize );
1559 //% memset( lm->superLuxels[ 0 ], 0, llSize );
1561 /* set ambient color */
1562 for( y = 0; y < lm->sh; y++ )
1564 for( x = 0; x < lm->sw; x++ )
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 );
1572 /* blacken unmapped clusters */
1574 VectorClear( luxel );
1579 VectorCopy( ambientColor, luxel );
1581 VectorScale( normal, 0.00390625f, deluxel );
1587 /* clear styled lightmaps */
1588 size = lm->sw * lm->sh * SUPER_LUXEL_SIZE * sizeof( float );
1589 for( lightmapNum = 1; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
1591 if( lm->superLuxels[ lightmapNum ] != NULL )
1592 memset( lm->superLuxels[ lightmapNum ], 0, size );
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 ] );
1599 /* walk light list */
1600 for( i = 0; i < trace.numLights; i++ )
1603 trace.light = trace.lights[ i ];
1606 for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
1608 if( lm->styles[ lightmapNum ] == trace.light->style ||
1609 lm->styles[ lightmapNum ] == LS_NONE )
1613 /* max of MAX_LIGHTMAPS (4) styles allowed to hit a surface/lightmap */
1614 if( lightmapNum >= MAX_LIGHTMAPS )
1616 Sys_Printf( "WARNING: Hit per-surface style limit (%d)\n", MAX_LIGHTMAPS );
1621 memset( lightLuxels, 0, llSize );
1624 /* initial pass, one sample per luxel */
1625 for( y = 0; y < lm->sh; y++ )
1627 for( x = 0; x < lm->sw; x++ )
1630 cluster = SUPER_CLUSTER( x, y );
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 );
1640 /* set contribution count */
1641 lightLuxel[ 3 ] = 1.0f;
1644 trace.cluster = *cluster;
1645 VectorCopy( origin, trace.origin );
1646 VectorCopy( normal, trace.normal );
1648 /* get light for this sample */
1649 LightContributionToSample( &trace );
1650 VectorCopy( trace.color, lightLuxel );
1653 if( trace.color[ 0 ] || trace.color[ 1 ] || trace.color[ 2 ] )
1656 /* add to light direction map (fixme: use luxel normal as starting point for deluxel?) */
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 );
1668 /* don't even bother with everything else if nothing was lit */
1669 if( totalLighted == 0 )
1672 /* determine filter radius */
1673 filterRadius = lm->filterRadius > trace.light->filterRadius
1675 : trace.light->filterRadius;
1676 if( filterRadius < 0.0f )
1677 filterRadius = 0.0f;
1679 /* set luxel filter radius */
1680 luxelFilterRadius = superSample * filterRadius / lm->sampleSize;
1681 if( luxelFilterRadius == 0 && (filterRadius > 0.0f || filter) )
1682 luxelFilterRadius = 1;
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 )
1689 for( y = 0; y < (lm->sh - 1); y++ )
1691 for( x = 0; x < (lm->sw - 1); x++ )
1696 VectorClear( total );
1698 /* test 2x2 stamp */
1699 for( t = 0; t < 4; t++ )
1701 /* set sample coords */
1702 sx = x + tests[ t ][ 0 ];
1703 sy = y + tests[ t ][ 1 ];
1706 cluster = SUPER_CLUSTER( sx, sy );
1712 lightLuxel = LIGHT_LUXEL( sx, sy );
1713 VectorAdd( total, lightLuxel, total );
1714 if( (lightLuxel[ 0 ] + lightLuxel[ 1 ] + lightLuxel[ 2 ]) > 0.0f )
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 )
1722 /* if all 4 pixels are either in shadow or light, then don't subsample */
1723 if( lighted != 0 && lighted != mapped )
1725 for( t = 0; t < 4; t++ )
1727 /* set sample coords */
1728 sx = x + tests[ t ][ 0 ];
1729 sy = y + tests[ t ][ 1 ];
1732 cluster = SUPER_CLUSTER( sx, sy );
1735 lightLuxel = LIGHT_LUXEL( sx, sy );
1736 origin = SUPER_ORIGIN( sx, sy );
1738 /* only subsample shadowed luxels */
1739 //% if( (lightLuxel[ 0 ] + lightLuxel[ 1 ] + lightLuxel[ 2 ]) <= 0.0f )
1743 SubsampleRawLuxel_r( lm, &trace, origin, sx, sy, 0.25f, lightLuxel );
1745 /* debug code to colorize subsampled areas to yellow */
1746 //% luxel = SUPER_LUXEL( lightmapNum, sx, sy );
1747 //% VectorSet( luxel, 255, 204, 0 );
1754 /* allocate sampling lightmap storage */
1755 if( lm->superLuxels[ lightmapNum ] == NULL )
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 );
1764 if( lightmapNum > 0 )
1766 lm->styles[ lightmapNum ] = trace.light->style;
1767 //% Sys_Printf( "Surface %6d has lightstyle %d\n", rawLightmapNum, trace.light->style );
1770 /* copy to permanent luxels */
1771 for( y = 0; y < lm->sh; y++ )
1773 for( x = 0; x < lm->sw; x++ )
1775 /* get cluster and origin */
1776 cluster = SUPER_CLUSTER( x, y );
1779 origin = SUPER_ORIGIN( x, y );
1782 if( luxelFilterRadius )
1785 VectorClear( averageColor );
1788 /* cheaper distance-based filtering */
1789 for( sy = (y - luxelFilterRadius); sy <= (y + luxelFilterRadius); sy++ )
1791 if( sy < 0 || sy >= lm->sh )
1794 for( sx = (x - luxelFilterRadius); sx <= (x + luxelFilterRadius); sx++ )
1796 if( sx < 0 || sx >= lm->sw )
1799 /* get particulars */
1800 cluster = SUPER_CLUSTER( sx, sy );
1803 lightLuxel = LIGHT_LUXEL( sx, sy );
1806 weight = (abs( sx - x ) == luxelFilterRadius ? 0.5f : 1.0f);
1807 weight *= (abs( sy - y ) == luxelFilterRadius ? 0.5f : 1.0f);
1809 /* scale luxel by filter weight */
1810 VectorScale( lightLuxel, weight, color );
1811 VectorAdd( averageColor, color, averageColor );
1817 if( samples <= 0.0f )
1820 /* scale into luxel */
1821 luxel = SUPER_LUXEL( lightmapNum, x, y );
1824 /* handle negative light */
1825 if( trace.light->flags & LIGHT_NEGATIVE )
1827 luxel[ 0 ] -= averageColor[ 0 ] / samples;
1828 luxel[ 1 ] -= averageColor[ 1 ] / samples;
1829 luxel[ 2 ] -= averageColor[ 2 ] / samples;
1832 /* handle normal light */
1835 luxel[ 0 ] += averageColor[ 0 ] / samples;
1836 luxel[ 1 ] += averageColor[ 1 ] / samples;
1837 luxel[ 2 ] += averageColor[ 2 ] / samples;
1844 /* get particulars */
1845 lightLuxel = LIGHT_LUXEL( x, y );
1846 luxel = SUPER_LUXEL( lightmapNum, x, y );
1848 /* handle negative light */
1849 if( trace.light->flags & LIGHT_NEGATIVE )
1850 VectorScale( averageColor, -1.0f, averageColor );
1855 /* handle negative light */
1856 if( trace.light->flags & LIGHT_NEGATIVE )
1857 VectorSubtract( luxel, lightLuxel, luxel );
1859 /* handle normal light */
1861 VectorAdd( luxel, lightLuxel, luxel );
1867 /* free temporary luxels */
1868 free( lightLuxels );
1871 /* free light list */
1872 FreeTraceLights( &trace );
1874 /* -----------------------------------------------------------------
1876 ----------------------------------------------------------------- */
1878 /* walk lightmaps */
1879 for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
1882 if( lm->superLuxels[ lightmapNum ] == NULL )
1885 /* average occluded luxels from neighbors */
1886 for( y = 0; y < lm->sh; y++ )
1888 for( x = 0; x < lm->sw; x++ )
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 );
1896 /* determine if filtering is necessary */
1897 filterColor = qfalse;
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) )
1905 if( !filterColor && !filterDir )
1908 /* choose seed amount */
1909 VectorClear( averageColor );
1910 VectorClear( averageDir );
1913 /* walk 3x3 matrix */
1914 for( sy = (y - 1); sy <= (y + 1); sy++ )
1916 if( sy < 0 || sy >= lm->sh )
1919 for( sx = (x - 1); sx <= (x + 1); sx++ )
1921 if( sx < 0 || sx >= lm->sw || (sx == x && sy == y) )
1924 /* get neighbor's particulars */
1925 cluster2 = SUPER_CLUSTER( sx, sy );
1926 luxel2 = SUPER_LUXEL( lightmapNum, sx, sy );
1927 deluxel2 = SUPER_DELUXEL( sx, sy );
1929 /* ignore unmapped/unlit luxels */
1930 if( *cluster2 < 0 || luxel2[ 3 ] == 0.0f ||
1931 (lm->splotchFix && VectorCompare( luxel2, ambientColor )) )
1934 /* add its distinctiveness to our own */
1935 VectorAdd( averageColor, luxel2, averageColor );
1936 samples += luxel2[ 3 ];
1938 VectorAdd( averageDir, deluxel2, averageDir );
1943 if( samples == 0.0f )
1949 VectorDivide( averageColor, samples, luxel );
1953 VectorDivide( averageDir, samples, deluxel );
1955 /* set cluster to -3 */
1957 *cluster = CLUSTER_FLOODED;
1966 IlluminateVertexes()
1967 light the surface vertexes
1970 #define VERTEX_NUDGE 2.0f
1972 void IlluminateVertexes( int num )
1974 int i, x, y, z, x1, y1, z1, sx, sy, radius, maxRadius, *cluster;
1976 float samples, *vertLuxel, *radVertLuxel, *luxel;
1977 vec3_t origin, temp, temp2, colors[ MAX_LIGHTMAPS ];
1978 bspDrawSurface_t *ds;
1979 surfaceInfo_t *info;
1981 bspDrawVert_t *verts;
1986 if( noVertexLighting )
1989 /* get surface, info, and raw lightmap */
1990 ds = &bspDrawSurfaces[ num ];
1991 info = &surfaceInfos[ num ];
1994 /* -----------------------------------------------------------------
1995 illuminate the vertexes
1996 ----------------------------------------------------------------- */
1998 /* calculate vertex lighting for surfaces without lightmaps */
2002 trace.testOcclusion = !noTrace;
2003 trace.forceSunlight = info->si->forceSunlight;
2004 trace.recvShadows = info->recvShadows;
2005 trace.numSurfaces = 1;
2006 trace.surfaces = #
2007 trace.inhibitRadius = DEFAULT_INHIBIT_RADIUS;
2009 /* twosided lighting */
2010 trace.twoSided = info->si->twoSided;
2012 /* make light list for this surface */
2013 CreateTraceLightsForSurface( num, &trace );
2015 /* walk the surface verts */
2016 verts = yDrawVerts + ds->firstVert;
2017 for( i = 0; i < ds->numVerts; i++ )
2019 /* get vertex luxel */
2020 radVertLuxel = RAD_VERTEX_LUXEL( 0, ds->firstVert + i );
2022 /* color the luxel with raw lightmap num? */
2024 VectorCopy( debugColors[ num % 12 ], radVertLuxel );
2026 /* color the luxel with luxel origin? */
2027 else if( debugOrigin )
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 ]);
2037 /* color the luxel with the normal */
2038 else if( normalmap )
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;
2045 /* illuminate the vertex */
2048 /* clear vertex luxel */
2049 VectorCopy( ambientColor, radVertLuxel );
2051 /* try at initial origin */
2052 trace.cluster = ClusterForPointExtFilter( verts[ i ].xyz, VERTEX_EPSILON, info->numSurfaceClusters, &surfaceClusters[ info->firstSurfaceCluster ] );
2053 if( trace.cluster >= 0 )
2056 VectorCopy( verts[ i ].xyz, trace.origin );
2057 VectorCopy( verts[ i ].normal, trace.normal );
2060 LightingAtSample( &trace, ds->vertexStyles, colors );
2063 for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
2065 radVertLuxel = RAD_VERTEX_LUXEL( lightmapNum, ds->firstVert + i );
2066 VectorCopy( colors[ lightmapNum ], radVertLuxel );
2070 /* is this sample bright enough? */
2071 if( radVertLuxel[ 0 ] <= ambientColor[ 0 ] &&
2072 radVertLuxel[ 1 ] <= ambientColor[ 1 ] &&
2073 radVertLuxel[ 2 ] <= ambientColor[ 2 ] )
2075 /* nudge the sample point around a bit */
2076 for( x = 0; x < 4; x++ )
2078 /* two's complement 0, 1, -1, 2, -2, etc */
2079 x1 = ((x >> 1) ^ (x & 1 ? -1 : 0)) + (x & 1);
2081 for( y = 0; y < 4; y++ )
2083 y1 = ((y >> 1) ^ (y & 1 ? -1 : 0)) + (y & 1);
2085 for( z = 0; z < 4; z++ )
2087 z1 = ((z >> 1) ^ (z & 1 ? -1 : 0)) + (z & 1);
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);
2094 /* try at nudged origin */
2095 trace.cluster = ClusterForPointExtFilter( origin, VERTEX_EPSILON, info->numSurfaceClusters, &surfaceClusters[ info->firstSurfaceCluster ] );
2096 if( trace.cluster < 0 )
2100 LightingAtSample( &trace, ds->vertexStyles, colors );
2103 for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
2105 radVertLuxel = RAD_VERTEX_LUXEL( lightmapNum, ds->firstVert + i );
2106 VectorCopy( colors[ lightmapNum ], radVertLuxel );
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 ] )
2121 /* another happy customer */
2122 numVertsIlluminated++;
2125 for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
2128 vertLuxel = VERTEX_LUXEL( lightmapNum, ds->firstVert + i );
2129 radVertLuxel = RAD_VERTEX_LUXEL( lightmapNum, ds->firstVert + i );
2132 if( bouncing || bounce == 0 || !bounceOnly )
2133 VectorAdd( vertLuxel, radVertLuxel, vertLuxel );
2134 ColorToBytes( vertLuxel, verts[ i ].color[ lightmapNum ], info->si->vertexScale );
2138 /* free light list */
2139 FreeTraceLights( &trace );
2141 /* return to sender */
2145 /* -----------------------------------------------------------------
2146 reconstitute vertex lighting from the luxels
2147 ----------------------------------------------------------------- */
2149 /* set styles from lightmap */
2150 for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
2151 ds->vertexStyles[ lightmapNum ] = lm->styles[ lightmapNum ];
2153 /* get max search radius */
2155 maxRadius = maxRadius > lm->sh ? maxRadius : lm->sh;
2157 /* walk the surface verts */
2158 verts = yDrawVerts + ds->firstVert;
2159 for( i = 0; i < ds->numVerts; i++ )
2161 /* do each lightmap */
2162 for( lightmapNum = 0; lightmapNum < MAX_LIGHTMAPS; lightmapNum++ )
2165 if( lm->superLuxels[ lightmapNum ] == NULL )
2168 /* get luxel coords */
2169 x = verts[ i ].lightmap[ lightmapNum ][ 0 ];
2170 y = verts[ i ].lightmap[ lightmapNum ][ 1 ];
2173 else if( x >= lm->sw )
2177 else if( y >= lm->sh )
2180 /* get vertex luxels */
2181 vertLuxel = VERTEX_LUXEL( lightmapNum, ds->firstVert + i );
2182 radVertLuxel = RAD_VERTEX_LUXEL( lightmapNum, ds->firstVert + i );
2184 /* color the luxel with the normal? */
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;
2192 /* color the luxel with surface num? */
2193 else if( debugSurfaces )
2194 VectorCopy( debugColors[ num % 12 ], radVertLuxel );
2196 /* divine color from the superluxels */
2199 /* increasing radius */
2200 VectorClear( radVertLuxel );
2202 for( radius = 0; radius < maxRadius && samples <= 0.0f; radius++ )
2204 /* sample within radius */
2205 for( sy = (y - radius); sy <= (y + radius); sy++ )
2207 if( sy < 0 || sy >= lm->sh )
2210 for( sx = (x - radius); sx <= (x + radius); sx++ )
2212 if( sx < 0 || sx >= lm->sw )
2215 /* get luxel particulars */
2216 luxel = SUPER_LUXEL( lightmapNum, sx, sy );
2217 cluster = SUPER_CLUSTER( sx, sy );
2221 /* testing: must be brigher than ambient color */
2222 //% if( luxel[ 0 ] <= ambientColor[ 0 ] || luxel[ 1 ] <= ambientColor[ 1 ] || luxel[ 2 ] <= ambientColor[ 2 ] )
2225 /* add its distinctiveness to our own */
2226 VectorAdd( radVertLuxel, luxel, radVertLuxel );
2227 samples += luxel[ 3 ];
2233 if( samples > 0.0f )
2234 VectorDivide( radVertLuxel, samples, radVertLuxel );
2236 VectorCopy( ambientColor, radVertLuxel );
2239 /* store into floating point storage */
2240 VectorAdd( vertLuxel, radVertLuxel, vertLuxel );
2241 numVertsIlluminated++;
2243 /* store into bytes (for vertex approximation) */
2244 ColorToBytes( vertLuxel, verts[ i ].color[ lightmapNum ], 1.0f );
2251 /* -------------------------------------------------------------------------------
2253 light optimization (-fast)
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
2259 ------------------------------------------------------------------------------- */
2263 determines opaque brushes in the world and find sky shaders for sunlight calculations
2266 void SetupBrushes( void )
2268 int i, j, b, compileFlags;
2271 bspBrushSide_t *side;
2272 bspShader_t *shader;
2277 Sys_FPrintf( SYS_VRB, "--- SetupBrushes ---\n" );
2280 if( opaqueBrushes == NULL )
2281 opaqueBrushes = safe_malloc( numBSPBrushes / 8 + 1 );
2284 memset( opaqueBrushes, 0, numBSPBrushes / 8 + 1 );
2285 numOpaqueBrushes = 0;
2287 /* walk the list of worldspawn brushes */
2288 for( i = 0; i < bspModels[ 0 ].numBSPBrushes; i++ )
2291 b = bspModels[ 0 ].firstBSPBrush + i;
2292 brush = &bspBrushes[ b ];
2294 /* check all sides */
2297 for( j = 0; j < brush->numSides && inside; j++ )
2299 /* do bsp shader calculations */
2300 side = &bspBrushSides[ brush->firstSide + j ];
2301 shader = &bspShaders[ side->shaderNum ];
2303 /* get shader info */
2304 si = ShaderInfoForShader( shader->shader );
2308 /* or together compile flags */
2309 compileFlags |= si->compileFlags;
2312 /* determine if this brush is opaque to light */
2313 if( !(compileFlags & C_TRANSLUCENT) )
2315 opaqueBrushes[ b >> 3 ] |= (1 << (b & 7));
2321 /* emit some statistics */
2322 Sys_FPrintf( SYS_VRB, "%9d opaque brushes\n", numOpaqueBrushes );
2329 determines if two clusters are visible to each other using the PVS
2332 qboolean ClusterVisible( int a, int b )
2334 int portalClusters, leafBytes;
2339 if( a < 0 || b < 0 )
2347 if( numBSPVisBytes <=8 )
2351 portalClusters = ((int *) bspVisBytes)[ 0 ];
2352 leafBytes = ((int*) bspVisBytes)[ 1 ];
2353 pvs = bspVisBytes + VIS_HEADER_SIZE + (a * leafBytes);
2356 if( (pvs[ b >> 3 ] & (1 << (b & 7))) )
2365 borrowed from vlight.c
2368 int PointInLeafNum_r( vec3_t point, int nodenum )
2376 while( nodenum >= 0 )
2378 node = &bspNodes[ nodenum ];
2379 plane = &bspPlanes[ node->planeNum ];
2380 dist = DotProduct( point, plane->normal ) - plane->dist;
2382 nodenum = node->children[ 0 ];
2383 else if( dist < -0.1 )
2384 nodenum = node->children[ 1 ];
2387 leafnum = PointInLeafNum_r( point, node->children[ 0 ] );
2388 if( bspLeafs[ leafnum ].cluster != -1 )
2390 nodenum = node->children[ 1 ];
2394 leafnum = -nodenum - 1;
2402 borrowed from vlight.c
2405 int PointInLeafNum( vec3_t point )
2407 return PointInLeafNum_r( point, 0 );
2413 ClusterVisibleToPoint() - ydnar
2414 returns qtrue if point can "see" cluster
2417 qboolean ClusterVisibleToPoint( vec3_t point, int cluster )
2422 /* get leafNum for point */
2423 pointCluster = ClusterForPoint( point );
2424 if( pointCluster < 0 )
2428 return ClusterVisible( pointCluster, cluster );
2434 ClusterForPoint() - ydnar
2435 returns the pvs cluster for point
2438 int ClusterForPoint( vec3_t point )
2443 /* get leafNum for point */
2444 leafNum = PointInLeafNum( point );
2448 /* return the cluster */
2449 return bspLeafs[ leafNum ].cluster;
2455 ClusterForPointExt() - ydnar
2456 also takes brushes into account for occlusion testing
2459 int ClusterForPointExt( vec3_t point, float epsilon )
2461 int i, j, b, leafNum, cluster;
2464 int *brushes, numBSPBrushes;
2470 /* get leaf for point */
2471 leafNum = PointInLeafNum( point );
2474 leaf = &bspLeafs[ leafNum ];
2476 /* get the cluster */
2477 cluster = leaf->cluster;
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++ )
2488 if( b > maxOpaqueBrush )
2490 brush = &bspBrushes[ b ];
2491 if( !(opaqueBrushes[ b >> 3 ] & (1 << (b & 7))) )
2494 /* check point against all planes */
2496 for( j = 0; j < brush->numSides && inside; j++ )
2498 plane = &bspPlanes[ bspBrushSides[ brush->firstSide + j ].planeNum ];
2499 dot = DotProduct( point, plane->normal );
2505 /* if inside, return bogus cluster */
2510 /* if the point made it this far, it's not inside any opaque brushes */
2517 ClusterForPointExtFilter() - ydnar
2518 adds cluster checking against a list of known valid clusters
2521 int ClusterForPointExtFilter( vec3_t point, float epsilon, int numClusters, int *clusters )
2526 /* get cluster for point */
2527 cluster = ClusterForPointExt( point, epsilon );
2529 /* check if filtering is necessary */
2530 if( cluster < 0 || numClusters <= 0 || clusters == NULL )
2534 for( i = 0; i < numClusters; i++ )
2536 if( cluster == clusters[ i ] || ClusterVisible( cluster, clusters[ i ] ) )
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
2552 int ShaderForPointInLeaf( vec3_t point, int leafNum, float epsilon, int wantContentFlags, int wantSurfaceFlags, int *contentFlags, int *surfaceFlags )
2557 int *brushes, numBSPBrushes;
2560 bspBrushSide_t *side;
2562 bspShader_t *shader;
2563 int allSurfaceFlags, allContentFlags;
2566 /* clear things out first */
2573 leaf = &bspLeafs[ leafNum ];
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++ )
2581 brush = &bspBrushes[ brushes[ i ] ];
2583 /* check point against all planes */
2585 allSurfaceFlags = 0;
2586 allContentFlags = 0;
2587 for( j = 0; j < brush->numSides && inside; j++ )
2589 side = &bspBrushSides[ brush->firstSide + j ];
2590 plane = &bspPlanes[ side->planeNum ];
2591 dot = DotProduct( point, plane->normal );
2597 shader = &bspShaders[ side->shaderNum ];
2598 allSurfaceFlags |= shader->surfaceFlags;
2599 allContentFlags |= shader->contentFlags;
2603 /* handle if inside */
2606 /* if there are desired flags, check for same and continue if they aren't matched */
2607 if( wantContentFlags && !(wantContentFlags & allContentFlags) )
2609 if( wantSurfaceFlags && !(wantSurfaceFlags & allSurfaceFlags) )
2612 /* store the cumulative flags and return the brush shader (which is mostly useless) */
2613 *surfaceFlags = allSurfaceFlags;
2614 *contentFlags = allContentFlags;
2615 return brush->shaderNum;
2619 /* if the point made it this far, it's not inside any brushes */
2627 chops a bounding box by the plane defined by origin and normal
2628 returns qfalse if the bounds is entirely clipped away
2630 this is not exactly the fastest way to do this...
2633 qboolean ChopBounds( vec3_t mins, vec3_t maxs, vec3_t origin, vec3_t normal )
2635 /* FIXME: rewrite this so it doesn't use bloody brushes */
2643 calculates each light's effective envelope,
2644 taking into account brightness, type, and pvs.
2647 #define LIGHT_EPSILON 0.125f
2648 #define LIGHT_NUDGE 2.0f
2650 void SetupEnvelopes( qboolean forGrid, qboolean fastFlag )
2652 int i, x, y, z, x1, y1, z1;
2653 light_t *light, *light2, **owner;
2655 vec3_t origin, dir, mins, maxs, nullVector = { 0, 0, 0 };
2656 float radius, intensity;
2657 light_t *buckets[ 256 ];
2660 /* early out for weird cases where there are no lights */
2661 if( lights == NULL )
2665 Sys_FPrintf( SYS_VRB, "--- SetupEnvelopes%s ---\n", fastFlag ? " (fast)" : "" );
2669 numCulledLights = 0;
2671 while( *owner != NULL )
2676 /* handle negative lights */
2677 if( light->photons < 0.0f || light->add < 0.0f )
2679 light->photons *= -1.0f;
2680 light->add *= -1.0f;
2681 light->flags |= LIGHT_NEGATIVE;
2685 if( light->type == EMIT_SUN )
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 );
2694 /* everything else */
2697 /* get pvs cluster for light */
2698 light->cluster = ClusterForPointExt( light->origin, LIGHT_EPSILON );
2700 /* invalid cluster? */
2701 if( light->cluster < 0 )
2703 /* nudge the sample point around a bit */
2704 for( x = 0; x < 4; x++ )
2706 /* two's complement 0, 1, -1, 2, -2, etc */
2707 x1 = ((x >> 1) ^ (x & 1 ? -1 : 0)) + (x & 1);
2709 for( y = 0; y < 4; y++ )
2711 y1 = ((y >> 1) ^ (y & 1 ? -1 : 0)) + (y & 1);
2713 for( z = 0; z < 4; z++ )
2715 z1 = ((z >> 1) ^ (z & 1 ? -1 : 0)) + (z & 1);
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);
2722 /* try at nudged origin */
2723 light->cluster = ClusterForPointExt( origin, LIGHT_EPSILON );
2724 if( light->cluster < 0 )
2728 VectorCopy( origin, light->origin );
2734 /* only calculate for lights in pvs and outside of opaque brushes */
2735 if( light->cluster >= 0 )
2737 /* set light fast flag */
2739 light->flags |= LIGHT_FAST_TEMP;
2741 light->flags &= ~LIGHT_FAST_TEMP;
2742 if( light->si && light->si->noFast )
2743 light->flags &= ~(LIGHT_FAST | LIGHT_FAST_TEMP);
2745 /* clear light envelope */
2746 light->envelope = 0;
2748 /* handle area lights */
2749 if( exactPointToPolygon && light->type == EMIT_AREA && light->w != NULL )
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 )
2757 VectorMA( light->origin, radius, light->normal, origin );
2758 factor = PointToPolygonFormFactor( origin, dir, light->w );
2761 if( (factor * light->add) <= light->falloffTolerance )
2762 light->envelope = radius;
2765 /* check for fast mode */
2766 if( !(light->flags & LIGHT_FAST) && !(light->flags & LIGHT_FAST_TEMP) )
2767 light->envelope = MAX_WORLD_COORD * 8.0f;
2772 intensity = light->photons;
2776 if( light->envelope <= 0.0f )
2778 /* solve distance for non-distance lights */
2779 if( !(light->flags & LIGHT_ATTEN_DISTANCE) )
2780 light->envelope = MAX_WORLD_COORD * 8.0f;
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;
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;
2795 /* solve for inverse square falloff */
2797 light->envelope = sqrt( intensity / light->falloffTolerance ) + radius;
2800 add = light->photons / (dist * dist);
2801 T = light->photons / (dist * dist);
2802 T * (dist * dist) = light->photons;
2803 dist = sqrt( light->photons / T );
2807 /* chop radius against pvs */
2810 ClearBounds( mins, maxs );
2812 /* check all leaves */
2813 for( i = 0; i < numBSPLeafs; i++ )
2816 leaf = &bspLeafs[ i ];
2819 if( leaf->cluster < 0 )
2821 if( ClusterVisible( light->cluster, leaf->cluster ) == qfalse ) /* ydnar: thanks Arnout for exposing my stupid error (this never failed before) */
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 );
2831 /* test to see if bounds encompass light */
2832 for( i = 0; i < 3; i++ )
2834 if( mins[ i ] > light->origin[ i ] || maxs[ i ] < light->origin[ i ] )
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 );
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 );
2849 VectorCopy( mins, light->mins );
2850 VectorCopy( maxs, light->maxs );
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 );
2862 /* calculate spherical bounds */
2863 VectorSubtract( maxs, light->origin, dir );
2864 radius = (float) VectorLength( dir );
2866 /* if this radius is smaller than the envelope, then set the envelope to it */
2867 if( radius < light->envelope )
2869 light->envelope = radius;
2870 //% Sys_FPrintf( SYS_VRB, "PVS Cull (%d): culled\n", numLights );
2873 //% Sys_FPrintf( SYS_VRB, "PVS Cull (%d): failed (%8.0f > %8.0f)\n", numLights, radius, light->envelope );
2876 /* add grid/surface only check */
2879 if( !(light->flags & LIGHT_GRID) )
2880 light->envelope = 0.0f;
2884 if( !(light->flags & LIGHT_SURFACES) )
2885 light->envelope = 0.0f;
2890 if( light->cluster < 0 || light->envelope <= 0.0f )
2893 //% Sys_Printf( "Culling light: Cluster: %d Envelope: %f\n", light->cluster, light->envelope );
2895 /* delete the light */
2897 *owner = light->next;
2898 if( light->w != NULL )
2905 /* square envelope */
2906 light->envelope2 = (light->envelope * light->envelope);
2908 /* increment light count */
2911 /* set next light */
2912 owner = &((**owner).next);
2915 /* bucket sort lights by style */
2916 memset( buckets, 0, sizeof( buckets ) );
2918 for( light = lights; light != NULL; light = light2 )
2920 /* get next light */
2921 light2 = light->next;
2923 /* filter into correct bucket */
2924 light->next = buckets[ light->style ];
2925 buckets[ light->style ] = light;
2928 /* filter back into light list */
2930 for( i = 255; i >= 0; i-- )
2933 for( light = buckets[ i ]; light != NULL; light = light2 )
2935 light2 = light->next;
2936 light->next = lights;
2941 /* emit some statistics */
2942 Sys_Printf( "%9d total lights\n", numLights );
2943 Sys_Printf( "%9d culled lights\n", numCulledLights );
2949 CreateTraceLightsForBounds()
2950 creates a list of lights that affect the given bounding box and pvs clusters (bsp leaves)
2953 void CreateTraceLightsForBounds( vec3_t mins, vec3_t maxs, vec3_t normal, int numClusters, int *clusters, int flags, trace_t *trace )
2957 vec3_t origin, dir, nullVector = { 0.0f, 0.0f, 0.0f };
2958 float radius, dist, length;
2961 /* potential pre-setup */
2962 if( numLights == 0 )
2963 SetupEnvelopes( qfalse, fast );
2966 //% Sys_Printf( "CTWLFB: (%4.1f %4.1f %4.1f) (%4.1f %4.1f %4.1f)\n", mins[ 0 ], mins[ 1 ], mins[ 2 ], maxs[ 0 ], maxs[ 1 ], maxs[ 2 ] );
2968 /* allocate the light list */
2969 trace->lights = safe_malloc( sizeof( light_t* ) * (numLights + 1) );
2970 trace->numLights = 0;
2972 /* calculate spherical bounds */
2973 VectorAdd( mins, maxs, origin );
2974 VectorScale( origin, 0.5f, origin );
2975 VectorSubtract( maxs, origin, dir );
2976 radius = (float) VectorLength( dir );
2978 /* get length of normal vector */
2979 if( normal != NULL )
2980 length = VectorLength( normal );
2983 normal = nullVector;
2987 /* test each light and see if it reaches the sphere */
2988 /* note: the attenuation code MUST match LightingAtSample() */
2989 for( light = lights; light; light = light->next )
2991 /* check zero sized envelope */
2992 if( light->envelope <= 0 )
2994 lightsEnvelopeCulled++;
2999 if( !(light->flags & flags) )
3002 /* sunlight skips all this nonsense */
3003 if( light->type != EMIT_SUN )
3009 /* check against pvs cluster */
3010 if( numClusters > 0 && clusters != NULL )
3012 for( i = 0; i < numClusters; i++ )
3014 if( ClusterVisible( light->cluster, clusters[ i ] ) )
3019 if( i == numClusters )
3021 lightsClusterCulled++;
3026 /* if the light's bounding sphere intersects with the bounding sphere then this light needs to be tested */
3027 VectorSubtract( light->origin, origin, dir );
3028 dist = VectorLength( dir );
3029 dist -= light->envelope;
3033 lightsEnvelopeCulled++;
3037 /* check bounding box against light's pvs envelope (note: this code never eliminated any lights, so disabling it) */
3040 for( i = 0; i < 3; i++ )
3042 if( mins[ i ] > light->maxs[ i ] || maxs[ i ] < light->mins[ i ] )
3047 lightsBoundsCulled++;
3053 /* planar surfaces (except twosided surfaces) have a couple more checks */
3054 if( length > 0.0f && trace->twoSided == qfalse )
3056 /* lights coplanar with a surface won't light it */
3057 if( !(light->flags & LIGHT_TWOSIDED) && DotProduct( light->normal, normal ) > 0.999f )
3059 lightsPlaneCulled++;
3063 /* check to see if light is behind the plane */
3064 if( DotProduct( light->origin, normal ) - DotProduct( origin, normal ) < -1.0f )
3066 lightsPlaneCulled++;
3071 /* add this light */
3072 trace->lights[ trace->numLights++ ] = light;
3075 /* make last night null */
3076 trace->lights[ trace->numLights ] = NULL;
3081 void FreeTraceLights( trace_t *trace )
3083 if( trace->lights != NULL )
3084 free( trace->lights );
3090 CreateTraceLightsForSurface()
3091 creates a list of lights that can potentially affect a drawsurface
3094 void CreateTraceLightsForSurface( int num, trace_t *trace )
3097 vec3_t mins, maxs, normal;
3099 bspDrawSurface_t *ds;
3100 surfaceInfo_t *info;
3107 /* get drawsurface and info */
3108 ds = &bspDrawSurfaces[ num ];
3109 info = &surfaceInfos[ num ];
3111 /* get the mins/maxs for the dsurf */
3112 ClearBounds( mins, maxs );
3113 VectorCopy( bspDrawVerts[ ds->firstVert ].normal, normal );
3114 for( i = 0; i < ds->numVerts; i++ )
3116 dv = &yDrawVerts[ ds->firstVert + i ];
3117 AddPointToBounds( dv->xyz, mins, maxs );
3118 if( !VectorCompare( dv->normal, normal ) )
3119 VectorClear( normal );
3122 /* create the lights for the bounding box */
3123 CreateTraceLightsForBounds( mins, maxs, normal, info->numSurfaceClusters, &surfaceClusters[ info->firstSurfaceCluster ], LIGHT_SURFACES, trace );