/*
MakeNormalMap() - ydnar
scanline converts a triangle and interpolates its normals onto the normal map
*/

#define EXTRA_WIDTH		LIGHTMAP_WIDTH * EXTRASCALE
#define EXTRA_HEIGHT	LIGHTMAP_HEIGHT * EXTRASCALE
#define EDGE_TOLERANCE	0.05

void MakeNormalMap( drawVert_t *dv[ 3 ], int pass, int lmx, int lmy, int sw, int sh, vec3_t map[ EXTRA_WIDTH ][ EXTRA_HEIGHT ] )

{
	int			i, j, k, x, y;
	float		lmb[ 2 ], lm[ 2 ], b, t, tap, *mapped;
	vec3_t		bary, normal;
	drawVert_t	*start, *end;
	
	
	/* for each sample, calculate the barycentric coordinates within the triangle and derive a normal from that */
	lmb[ 0 ] = LIGHTMAP_WIDTH;
	lmb[ 1 ] = LIGHTMAP_HEIGHT;
	if( extra )
	{
		lmx *= 2;
		lmy *= 2;
		lmb[ 0 ] *= 2;
		lmb[ 1 ] *= 2;
	}

	/* calculate barycentric factor */
	b = (dv[ 1 ]->lightmap[ 0 ] - dv[ 0 ]->lightmap[ 0 ]) * (dv[ 2 ]->lightmap[ 1 ] - dv[ 0 ]->lightmap[ 1 ]) -
		(dv[ 2 ]->lightmap[ 0 ] - dv[ 0 ]->lightmap[ 0 ]) * (dv[ 1 ]->lightmap[ 1 ] - dv[ 0 ]->lightmap[ 1 ]);
	
	/* hit each lightmap sample */
	for( i = 0; i < sw; i++ )
	{
		for( j = 0; j < sh; j++ )
		{
			/* calc lightmap coords in the sample area */
			lm[ 0 ] = (float) (i + lmx) / lmb[ 0 ];
			lm[ 1 ] = (float) (j + lmy) / lmb[ 1 ];
			
			/*
				thanks to david watson via usenet for this tidy calculation of barycentric coords:
				b0 =  (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)
				b1 = ((x2 - x0) * (y3 - y0) - (x3 - x0) * (y2 - y0)) / b0 
				b2 = ((x3 - x0) * (y1 - y0) - (x1 - x0) * (y3 - y0)) / b0
				b3 = ((x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0)) / b0
			*/

			bary[ 0 ] = ((dv[ 1 ]->lightmap[ 0 ] - lm[ 0 ]) * (dv[ 2 ]->lightmap[ 1 ] - lm[ 1 ]) -
				(dv[ 2 ]->lightmap[ 0 ] - lm[ 0 ]) * (dv[ 1 ]->lightmap[ 1 ] - lm[ 1 ])) / b;
			bary[ 1 ] = ((dv[ 2 ]->lightmap[ 0 ] - lm[ 0 ]) * (dv[ 0 ]->lightmap[ 1 ] - lm[ 1 ]) -
				(dv[ 0 ]->lightmap[ 0 ] - lm[ 0 ]) * (dv[ 2 ]->lightmap[ 1 ] - lm[ 1 ])) / b;
			bary[ 2 ] = ((dv[ 0 ]->lightmap[ 0 ] - lm[ 0 ]) * (dv[ 1 ]->lightmap[ 1 ] - lm[ 1 ]) -
				(dv[ 1 ]->lightmap[ 0 ] - lm[ 0 ]) * (dv[ 0 ]->lightmap[ 1 ] - lm[ 1 ])) / b;
			
			/* pin to nearest edge (this is dodgy code) */
			if( pass == 1 )
			{
				for( k = 0; k < 3; k++ )
				{
					if( bary[ k ] < 0 )
					{
						bary[ (k + 1) % 3 ] += (bary[ k ] * 0.5);
						bary[ (k + 2) % 3 ] += (bary[ k ] * 0.5);
						bary[ k ] = 0;
					}
				}
				
				t = 0;
				for( k = 0; k < 3; k++ )
					t += bary[ k ];
				VectorScale( bary, (1.0 / t), bary );
			}
			
			/* toss it if bary is too far out of order */
			if( bary[ 0 ] < -EDGE_TOLERANCE || bary[ 1 ] < -EDGE_TOLERANCE || bary[ 2 ] < -EDGE_TOLERANCE )
				continue;
			
			/* debugging code */
			//Sys_Printf( "(%3d, %3d) = bary (%3.3f) (%3.3f, %3.3f, %3.3f)\n", i, j, b, bary[ 0 ], bary[ 1 ], bary[ 2 ] );
			
			/* don't store over existing sample on first pass */
			mapped = map[ i ][ j ];
			if( pass == 0 && (mapped[ 0 ] || mapped[ 1 ] || mapped[ 2 ]) )
				continue;

			/* create a normal */
			for( k = 0; k < 3; k++ )
				normal[ k ] = (bary[ 0 ] * dv[ 0 ]->normal[ k ]) + (bary[ 1 ] * dv[ 1 ]->normal[ k ]) + (bary[ 2 ] * dv[ 2 ]->normal[ k ]);
			
			/* store it */
			if( VectorNormalize( normal, normal ) )
				VectorCopy( normal, mapped );
		}
	}
	

	/* secondary pass, hit all the edge samples and explicitly set those */
	for( i = 0; i < 3; i++ )
	{
		/* get verts */
		start = dv[ i ];
		end = dv[ (i + 1) % 3 ];
		if( fabs( start->xyz[ 0 ] - end->xyz[ 0 ] ) < EQUAL_EPSILON ||
			fabs( start->xyz[ 1 ] - end->xyz[ 1 ] ) < EQUAL_EPSILON )
			continue;
		
		/* for now, use a crap sampling frequency guaranteed to hit every texel */
		tap = 1.0 / (sqrt( (sh * sh) + (sw * sw) ) * 4);
		t = 0;
		do
		{
			/* clamp t */
			if( t > 1.0 )
				t = 1.0;
			
			/* calc normal and sample position */
			normal[ 0 ] = ((1.0 - t) * start->normal[ 0 ]) + (t * end->normal[ 0 ]);
			normal[ 1 ] = ((1.0 - t) * start->normal[ 1 ]) + (t * end->normal[ 1 ]);
			normal[ 2 ] = ((1.0 - t) * start->normal[ 2 ]) + (t * end->normal[ 2 ]);
			lm[ 0 ] = ((1.0 - t) * start->lightmap[ 0 ]) + (t * end->lightmap[ 0 ]);
			lm[ 1 ] = ((1.0 - t) * start->lightmap[ 1 ]) + (t * end->lightmap[ 1 ]);
			x = (int) Q_rint( (lm[ 0 ] * lmb[ 0 ]) ) - lmx;
			y = (int) Q_rint( (lm[ 1 ] * lmb[ 1 ]) ) - lmy;
			
			/* increment t */
			t += tap;
			
			/* store new normal */
			if( x < 0 || x >= sw || y < 0 || y >= sh )
				continue;
			mapped = map[ x ][ y ];
			if( VectorNormalize( normal, normal ) )
				VectorCopy( normal, mapped );
		}
		while( t <= 1.0 );
	}
}



/*
FindBestTriangle() - ydnar
given a triangle and lightmap st coordinates, determine if the sample point lies inside better than the previous
returns qtrue if the sample point lies entirely inside of the triangle (barycentric coords all > 0)
*/

qboolean FindBestTriangle( float lm[ 2 ], drawVert_t *dv[ 3 ], drawVert_t *best[ 3 ], vec3_t bestBary )
{
	int		i;
	float	b, nadir, bestNadir;
	vec3_t	bary;


	/* calculate barycentric coordinates for this triangle */
	b = (dv[ 1 ]->lightmap[ 0 ] - dv[ 0 ]->lightmap[ 0 ]) * (dv[ 2 ]->lightmap[ 1 ] - dv[ 0 ]->lightmap[ 1 ]) -
		(dv[ 2 ]->lightmap[ 0 ] - dv[ 0 ]->lightmap[ 0 ]) * (dv[ 1 ]->lightmap[ 1 ] - dv[ 0 ]->lightmap[ 1 ]);
	bary[ 0 ] = ((dv[ 1 ]->lightmap[ 0 ] - lm[ 0 ]) * (dv[ 2 ]->lightmap[ 1 ] - lm[ 1 ]) -
		(dv[ 2 ]->lightmap[ 0 ] - lm[ 0 ]) * (dv[ 1 ]->lightmap[ 1 ] - lm[ 1 ])) / b;
	bary[ 1 ] = ((dv[ 2 ]->lightmap[ 0 ] - lm[ 0 ]) * (dv[ 0 ]->lightmap[ 1 ] - lm[ 1 ]) -
		(dv[ 0 ]->lightmap[ 0 ] - lm[ 0 ]) * (dv[ 2 ]->lightmap[ 1 ] - lm[ 1 ])) / b;
	bary[ 2 ] = ((dv[ 0 ]->lightmap[ 0 ] - lm[ 0 ]) * (dv[ 1 ]->lightmap[ 1 ] - lm[ 1 ]) -
		(dv[ 1 ]->lightmap[ 0 ] - lm[ 0 ]) * (dv[ 0 ]->lightmap[ 1 ] - lm[ 1 ])) / b;
	
	/* entirely inside the triangle? */
	if( bary[ 0 ] >= 0 && bary[ 1 ] >= 0 && bary[ 2 ] >= 0 )
	{
		/* this is best */
		VectorCopy( bary, bestBary );
		VectorCopy( dv, best );
		return qtrue;
	}
	
	/* find most negative coordinates */
	nadir = 0;
	bestNadir = 0;
	for( i = 0; i < 3; i++ )
	{
		if( bary[ i ] < nadir )
			nadir = bary[ i ];
		if( bestBary[ i ] < bestNadir )
			bestNadir = bestBary[ i ];
	}
	
	/* if the new worst-case (most negative) coordinate it greater than the previous, we have a new "best" */
	if( nadir > bestNadir )
	{
		/* this is almost best */
		VectorCopy( bary, bestBary );
		VectorCopy( dv, best );
	}
	
	/* return (outside) */
	return qfalse;
}



/*
FindSamplePoint() - ydnar
for a given surface (and potentially a subdivided mesh) and lightmap st coordinates, recover a sample location and normal
returns the pvs cluster the sample point is in, otherwise returns -1 for an occluded sample
*/

#define YDNAR_FIND_SAMPLE	/* undef this to use old code */

#define BOGUS_NUDGE		-99999
#define SEARCH_NUDGE	.125
#define NORMAL_NUDGE	1
#define SAMPLE_EPSILON2	1.0 // ((1.0 / (float) (LIGHTMAP_WIDTH * LIGHTMAP_WIDTH)) * 3)

int FindSamplePoint( dsurface_t *ds, mesh_t *subdivided, vec3_t	normalVectors[ 2 ], float lm[ 2 ], vec3_t origin, vec3_t normal )
{
	drawVert_t		*verts;
	int				width, height;
	drawVert_t		*dv[ 3 ], *best[ 3 ];
	vec3_t			bestBary, nudgedBary;
	float			total;
	int				i, j, cluster;
	qboolean		found;
	float			b, lm2[ 2 ], dist2;
	float			*nudge;
	vec3_t			nudged;
	static float	nudges[][ 2 ] =
					{
						{ 0, 0 },	/* try center first */
						{ -1, -1 },	/* row 1 */
						{ 0, -1 },
						{ 1, -1 },
						{ -1, 0 },	/* row 2 */
						{ 1, 0 },
						{ -1, 1 },	/* row 3 */
						{ 0, 1 },
						{ 1, 1 },
						{ BOGUS_NUDGE, BOGUS_NUDGE }
					};
	
	
	/* handle non-planar patches */
	if( subdivided != NULL )
	{
		verts = subdivided->verts;
		width = subdivided->width;
		height = subdivided->height;
	}
	else
	{
		verts = &yDrawVerts[ ds->firstVert ];
		width = ds->patchWidth;
		height = ds->patchHeight;
	}
	
	/* clear the "best" values */
	for( i = 0; i < 3; i++ )
	{
		best[ i ] = NULL;
		bestBary[ i ] = -99999;
	}
	
	/* switch on type */
	switch( ds->surfaceType )
	{
		case MST_PLANAR:
			/* iterate through the triangles in the face */
			found = qfalse;
			for( i = 0; i < ds->numIndexes && found == qfalse; i += 3 )
			{
				/* get drawverts and fix the triangle */
				for( j = 0; j < 3; j++ )
					dv[ j ] = &yDrawVerts[ ds->firstVert + drawIndexes[ ds->firstIndex + i + j ] ];
				found = FindBestTriangle( lm, dv, best, bestBary );
			}
			break;
		
		case MST_PATCH:
			break;	/* FIXME: get this working */
			/* iterate through the mesh quads */
			found = qfalse;
			for( i = 0; i < (width - 1) && found == qfalse; i++ )
			{
				for( j = 0; j < (width - 1) && found == qfalse; j++ )
				{
					/* get drawverts and fix first triangle */
					dv[ 0 ] = verts + j * width + i;
					dv[ 1 ] = dv[ 0 ] + width;
					dv[ 2 ] = dv[ 0 ] + width + 1;
					found = FindBestTriangle( lm, dv, best, bestBary );
					
					/* get drawverts and fix second triangle */
					dv[ 0 ] = verts + j * width + i;
					dv[ 1 ] = dv[ 0 ] + width + 1;
					dv[ 2 ] = dv[ 0 ] + 1;
					found = FindBestTriangle( lm, dv, best, bestBary );
				}
			}
			break;
		
		default:
			break;
	}
	
	/* if a suitable triangle wasn't found, then bail */
	if( best[ 0 ] == NULL )
		return -1;
	
	/* ydnar: debug code (remove me) */
	//if( found == qfalse )
	//	return -1;
	
	/* pin to nearest edge of best candidate triangle (this is dodgy code) */
	if( found == qfalse )
	{
		/* pin negative coordinates to 0 */
		for( i = 0; i < 3; i++ )
		{
			if( bestBary[ i ] < 0 )
			{
				bestBary[ (i + 1) % 3 ] += (bestBary[ i ] * 0.5);
				bestBary[ (i + 2) % 3 ] += (bestBary[ i ] * 0.5);
				bestBary[ i ] = 0;
			}
		}
		
		/* barycentric coordinates must add up to 1.0 */
		total = 0;
		for( i = 0; i < 3; i++ )
			total += bestBary[ i ];
		VectorScale( bestBary, (1.0 / total), bestBary );
	}
	
	/* given the barycentric coordinates, create an average position and normal */
	VectorClear( origin );
	VectorClear( normal );
	lm2[ 0 ] = lm2[ 1 ] = 0;
	for( i = 0; i < 3; i++ )
	{
		/* tiny optimization: don't bother adding when barycentric coordinate is zero */
		if( bestBary[ i ] > 0 )
		{
			VectorMA( origin, bestBary[ i ], best[ i ]->xyz, origin );
			VectorMA( normal, bestBary[ i ], best[ i ]->normal, normal );
			lm2[ 0 ] += bestBary[ i ] * best[ i ]->lightmap[ 0 ];
			lm2[ 1 ] += bestBary[ i ] * best[ i ]->lightmap[ 1 ];
		}
	}
	
	/* check to see if actual lightmap coords are too far from originals */
	dist2 = 0;
	for( i = 0; i < 2; i++ )
	{
		total = lm2[ i ] - lm[ i ];
		dist2 += (total * total);
	}
	if( dist2 > SAMPLE_EPSILON2 )
		return -1;
	
	/* check for bogus normal */
	if( VectorNormalize( normal, normal ) == 0 )
		return -1;
	
	/* return the cluster */
	return cluster;
}





/*
=============
TraceLtm
=============
*/

void TraceLtm( int num )
{
	dsurface_t		*ds;
	qboolean		planarPatch;
	float			lm[ 2 ];
	int				lmo[ 2 ], lms[ 2 ];
	int				i, j, k, cluster, w, h;
	int				x, y;
	int				position, numPositions;
	vec3_t			base, origin, normal;
	byte			occluded[ EXTRA_WIDTH ][ EXTRA_HEIGHT ];
	vec3_t			color[ EXTRA_WIDTH][ EXTRA_HEIGHT ];
	traceWork_t		tw;
	vec3_t			average;
	int				count;
	mesh_t			srcMesh, *mesh = NULL, *subdivided = NULL;
	shaderInfo_t	*si;
	static float	nudge[2][9] =
					{
						{ 0, -1, 0, 1, -1, 1, -1, 0, 1 },
						{ 0, -1, -1, -1, 0, 0, 1, 1, 1 }
					};
	int				sampleWidth, sampleHeight, ssize;
	vec3_t			lightmapOrigin, lightmapVecs[ 2 ];
	int				widthtable[ LIGHTMAP_WIDTH ], heighttable[ LIGHTMAP_WIDTH ];
	
	
	/* get drawsurface and shader info */
	ds = &drawSurfaces[num];
	si = ShaderInfoForShader( dshaders[ ds->shaderNum ].shader );	/* ydnar: omg this is slow */
	
	/* ydnar: get a culled light list for this surface */
	CreateTWLightsForSurface( num, &tw );
	
	/* vertex-lit triangle model */
	if ( ds->surfaceType == MST_TRIANGLE_SOUP )
	{
		VertexLighting( num, !si->noVertexShadows, si->forceSunLight, 1.0, &tw );
		FreeTWLights( &tw );	/* ydnar */
		return;
	}
	
	/* nolightmap */
	if( ds->lightmapNum == -1 )
	{
		FreeTWLights( &tw );	/* ydnar */
		return;					/* doesn't need lighting at all */
	}

	/* ydnar: 2nd time... si = ShaderInfoForShader( dshaders[ ds->shaderNum].shader ); */

	/* calculate the vertex lighting for gouraud shade mode */
	if( !novertexlighting )
		VertexLighting( num, si->vertexShadows, si->forceSunLight, si->vertexScale, &tw );
	
	/* no lightmap? */
	if( ds->lightmapNum < 0 )
	{
		FreeTWLights( &tw );	/* ydnar */
		return;					/* doesn't need lightmap lighting */
	}
	
	/* ydnar: 3 times?? si = ShaderInfoForShader( dshaders[ ds->shaderNum ].shader ); */
	
	/* get samplesize */
	ssize = samplesize;
	if( si->lightmapSampleSize )
		ssize = si->lightmapSampleSize;
	
	
	/* ydnar: get lightmap width and height */
	w = ds->lightmapWidth;
	h = ds->lightmapHeight;
	
	/* ydnar: extract samplesize from dsurf */
	if( w & 0xFFFF0000 )
	{
		ssize = (w & 0xFFFF0000) >> 16;
		w &= 0x0000FFFF;
	}
	
	/* ydnar: debug code */
	if( w > LIGHTMAP_WIDTH || h > LIGHTMAP_HEIGHT )
		Error( "Lightmap dimensions exceeded: (%d > %d || %d > %d)", w, LIGHTMAP_WIDTH, h, LIGHTMAP_HEIGHT );
	
	
	/* patchshadows? */
	if( si->patchShadows )
		tw.patchshadows = qtrue;
	else
		tw.patchshadows = patchshadows;
	
	/* ydnar: is this a planar patch? */
	planarPatch = qfalse;
	if( ds->patchWidth && ds->numIndexes == 6 )
		planarPatch = qtrue;
	
	/* ydnar: handle planar patches differently */
	#ifdef YDNAR_PATCH_LIGHTMAP_FIX
		if( ds->surfaceType == MST_PATCH && planarPatch == qfalse )
	#else
		if( ds->surfaceType == MST_PATCH )
	#endif
	{
		srcMesh.width = ds->patchWidth;
		srcMesh.height = ds->patchHeight;
		srcMesh.verts = drawVerts + ds->firstVert;
		mesh = SubdivideMesh( srcMesh, 8, 999 );
		PutMeshOnCurve( *mesh );
		#ifndef YDNAR_PATCH_LIGHTMAP_FIX
			MakeMeshNormals( *mesh );	/* ydnar: testing */
		#endif

		subdivided = RemoveLinearMeshColumnsRows( mesh );
		FreeMesh( mesh );

		mesh = SubdivideMeshQuads( subdivided, ssize, LIGHTMAP_WIDTH, widthtable, heighttable );
		if( mesh->width != w || mesh->height != h )
		{
			Error( "Mesh lightmap miscount (%d) (%d != %d || %d != %d)",
				num, mesh->width, w, mesh->height, h );
		}
		
		/* ydnar: fix this fucking leak at some point */
		if( extra )
		{
			mesh_t	*mp;

			/* chop it up for more light samples (leaking memory...) */
			mp = mesh;//CopyMesh( mesh );
			mp = LinearSubdivideMesh( mp );
			mp = TransposeMesh( mp );
			mp = LinearSubdivideMesh( mp );
			mp = TransposeMesh( mp );

			mesh = mp;
		}
	}
	
	/* handle planar patches */
	#ifdef YDNAR_PATCH_LIGHTMAP_FIX
		else if( ds->surfaceType == MST_PATCH && planarPatch == qtrue )
		{
			vec3_t	*hack = (vec3_t*) &drawIndexes[ ds->firstIndex ];
			
			
			/* get normal */
			VectorCopy( ds->lightmapVecs[ 2 ], normal );
			
			/* get lightmap origin (what an ugly hack) */
			VectorCopy( ds->lightmapOrigin, lightmapOrigin );
			VectorCopy( hack[ 0 ], lightmapVecs[ 0 ] );
			VectorCopy( hack[ 1 ], lightmapVecs[ 1 ] );
		}
	#endif
	
	/* handle brush faces */
	else
	{
		/* get normal */
		VectorCopy( ds->lightmapVecs[ 2 ], normal );
		
		/* ydnar: get lightmap origin (eliminated some redundancy) */
		VectorCopy( ds->lightmapOrigin, lightmapOrigin );
		VectorCopy( ds->lightmapVecs[ 0 ], lightmapVecs[ 0 ] );
		VectorCopy( ds->lightmapVecs[ 1 ], lightmapVecs[ 1 ] );
	}
	
	/* extra? */
	if( extra )
	{
		/* scale lightmap vectors and shift origin */
		VectorScale( lightmapVecs[ 0 ], 0.5, lightmapVecs[ 0 ] );
		VectorScale( lightmapVecs[ 1 ], 0.5, lightmapVecs[ 1 ] );
		VectorMA( lightmapOrigin, -0.5, lightmapVecs[ 0 ], lightmapOrigin );
		VectorMA( lightmapOrigin, -0.5, lightmapVecs[ 1 ], lightmapOrigin );
		
		/* scale sample size */
		sampleWidth = w * 2;
		sampleHeight = h * 2;
	}
	else
	{
		sampleWidth = w;
		sampleHeight = h;
	}
	
	/* clear colors */
	memset( color, 0, sizeof( color ) );
	
	
	/* ydnar: use colors to store a normal map for phong shading (x = pass num) */
	#ifndef YDNAR_FIND_SAMPLE
		for( x = 0; x < 2; x++ )
		{
			drawVert_t	*dv[ 3 ];
			
			
			/* handle brush faces */
			if( ds->surfaceType == MST_PLANAR )
			{
				/* scanline convert each triangle onto the color map */
				for( i = 0; i < ds->numIndexes; i += 3 )
				{
					/* make a triangle and project it */
					for( j = 0; j < 3; j++ )
						dv[ j ] = &yDrawVerts[ ds->firstVert + drawIndexes[ ds->firstIndex + i + j ] ];
					MakeNormalMap( dv, x, ds->lightmapX, ds->lightmapY, sampleWidth, sampleHeight, color );
				}
			}
		}
	#endif
	

	/* set up integer sampling bounds */
	lmo[ 0 ] = (extra ? ds->lightmapX * 2 : ds->lightmapX);
	lmo[ 1 ] = (extra ? ds->lightmapY * 2 : ds->lightmapY);
	lms[ 0 ] = (extra ? LIGHTMAP_WIDTH * 2 : LIGHTMAP_WIDTH);
	lms[ 1 ] = (extra ? LIGHTMAP_HEIGHT * 2 : LIGHTMAP_HEIGHT);
	


	/* determine which samples are occluded */
	memset( occluded, qtrue, sizeof( occluded ) );	/* fixme: default to occluded */
	for( i = 0 ; i < sampleWidth; i++ )
	{
		for( j = 0 ; j < sampleHeight; j++ )
		{




			/* ydnar: use new sample finding code */
			#ifdef YDNAR_FIND_SAMPLE
				

				/* recover lightmap coordinates */
				lm[ 0 ] = (float) (i + lmo[ 0 ]) / lms[ 0 ];
				lm[ 1 ] = (float) (j + lmo[ 1 ]) / lms[ 1 ];

				/* find a valid sample point */
				cluster = FindSamplePoint( ds, subdivided, lm, origin, normal );
				


				/* non-planar patch specific stuff */
				if( subdivided != NULL )
					VectorMA( origin, NORMAL_NUDGE, normal, origin );
					MakeNormalVectors( normal, normalVectors[ 0 ], normalVectors[ 1 ] );
				
				/* build perpendicular normal vectors if necessary */
				if( subdivided != NULL )
				
				/* now, find a location in space that isn't in a solid */
				nudge = nudges[ 0 ];
				cluster = -1;
				while( nudge[ 0 ] > BOGUS_NUDGE && cluster == -1 )
				{
					/* nudge the vector around a bit */
					for( i = 0; i < 3; i++ )
					{
						nudged[ i ] = origin[ i ] + 
							+ (nudge[ 0 ] * SEARCH_NUDGE * normalVectors[ 0 ][ i ]) 
							+ (nudge[ 1 ] * SEARCH_NUDGE * normalVectors[ 1 ][ i ]);
					}
					nudge += 2;
					
					/* get pvs cluster */
					cluster = ClusterForPoint( nudged );
				}
				
				/* copy nudged to origin */
				VectorCopy( nudged, origin );
				
				/* occluded? */
				if( cluster == -1 )
					occluded[ i ][ j ] = qtrue;
				else
				{
					/* fixme: this is bogus */
					if( subdivided != NULL )
						MakeNormalVectors( normal, lightmapVecs[ 0 ], lightmapVecs[ 1 ] );
					
					/* render normalmap instead of lighting values? */
					if( normalmap )
					{
						for( k = 0; k < 3; k++ )
							color[ i ][ j ][ k ] = normal[ k ] > 0 ? normal[ k ] * 128 : 0;
					}
					else
					{
						/* get the lighting at this sample */
						LightingAtSample( cluster, origin, normal, lightmapVecs, color[ i ][ j ], qtrue, qfalse, &tw );
						occluded[ i ][ j ] = qfalse;
					}
				}
				
				
				
				
			/* old nudge code */
			#else
				/* handle planar patches */
				#ifdef YDNAR_PATCH_LIGHTMAP_FIX
					if( ds->patchWidth && planarPatch == qfalse )
				#else
					if( ds->patchWidth )
				#endif
				{
					numPositions = 9;
					VectorCopy( mesh->verts[ j * mesh->width + i ].normal, normal );

					/* push off of the curve a bit */
					VectorMA( mesh->verts[j*mesh->width + i ].xyz, 1, normal, base );
					MakeNormalVectors( normal, lightmapVecs[ 0 ], lightmapVecs[ 1 ] );
				}
				else
				{
					numPositions = 9;
					for( k = 0 ; k < 3 ; k++ )
					{
						base[k] = lightmapOrigin[ k ] + normal[ k ]
							+ i * lightmapVecs[ 0 ][ k ] 
							+ j * lightmapVecs[ 1 ][ k ];
					}
				}
				VectorAdd( base, surfaceOrigin[ num ], base );

				/* we may need to slightly nudge the sample point if directly on a wall */
				cluster = -1;
				for( position = 0 ; position < numPositions; position++ )
				{
					/* calculate lightmap sample position */
					for ( k = 0 ; k < 3 ; k++ )
					{
						origin[ k ] = base[ k ] + 
							+ (nudge[ 0 ][ position ] / 16) * lightmapVecs[ 0 ][ k ] 
							+ (nudge[ 1 ][ position ] / 16) * lightmapVecs[ 1 ][ k ];
					}

					if( notrace )
						break;
					
					/* ydnar: changing this to get cluster num */
					cluster = ClusterForPoint( origin );
					if( cluster >= 0 )
						break;
					//%if( !PointInSolid( origin ) )
					//%	break;
				}

				/* if none of the nudges worked, this sample is occluded */
				if( position == numPositions )
				{
					occluded[ i ][ j ] = qtrue;
					if ( numthreads == 1 )
						c_occluded++;
					continue;
				}
				

				/* ydnar: sample the normal map */
				if( ds->surfaceType == MST_PLANAR )
					VectorCopy( color[ i ][ j ], normal );
				VectorClear( color[ i ][ j ] );

				/* render normalmap instead of lighting values? */
				if( normalmap )
				{
					for( k = 0; k < 3; k++ )
						color[ i ][ j ][ k ] = normal[ k ] > 0 ? normal[ k ] * 128 : 0;
				}
				else
				{
					/* get the lighting at this sample */
					LightingAtSample( cluster, origin, normal, lightmapVecs, color[ i ][ j ], qtrue, qfalse, &tw );
				}
			#endif
			
			/* ydnar: only clear occluded if color isn't black */
			if( color[ i ][ j ][ 0 ] || color[ i ][ j ][ 1 ] || color[ i ][ j ][ 2 ] )
				occluded[ i ][ j ] = qfalse;
			
			/* set occluded/visible counts */
			if( numthreads == 1 )
			{
				if( occluded[ i ][ j ] )
					c_occluded++;
				else
					c_visible++;
			}
		}
	}

	/* ydnar: took over the dump flag for emitting radiosity maps */
	//%if( dump )
	//%	PrintOccluded( occluded, sampleWidth, sampleHeight );

	/* calculate average values for occluded samples */
	for( i = 0; i < sampleWidth; i++ )
	{
		for( j = 0; j < sampleHeight; j++ )
		{
			if( !occluded[i][j] )
				continue;
			
			/* scan all surrounding samples */
			count = 0;
			VectorClear( average );
			for( x = -1 ; x <= 1; x++ )
			{
				for( y = -1; y <= 1; y++ )
				{
					if( i + x < 0 || i + x >= sampleWidth )
						continue;
					if( j + y < 0 || j + y >= sampleHeight )
						continue;
					if( occluded[i+x][j+y] )
						continue;
					count++;
					VectorAdd( color[i+x][j+y], average, average );
				}
			}
			
			if( count )
				VectorScale( average, (1.0 / count), color[i][j] );
		}
	}
	
	/* average together the values if we are extra sampling */
	if( w != sampleWidth )
	{
		for( i = 0 ; i < w; i++ )
		{
			for( j = 0 ; j < h; j++ )
			{
				for( k = 0; k < 3; k++ )
				{
					float		value, coverage;
					
					
					/* sum 4 samples */
					value = color[i*2][j*2][k] + color[i*2][j*2+1][k] +
						color[i*2+1][j*2][k] + color[i*2+1][j*2+1][k];
					coverage = 4;
					
					/* sum some more */
					if( extraWide )
					{
						/* wider than box filter */
						if( i > 0 )
						{
							value += color[i*2-1][j*2][k] + color[i*2-1][j*2+1][k];
							value += color[i*2-2][j*2][k] + color[i*2-2][j*2+1][k];
							coverage += 4;
						}
						if( i < (w - 1) )
						{
							value += color[i*2+2][j*2][k] + color[i*2+2][j*2+1][k];
							value += color[i*2+3][j*2][k] + color[i*2+3][j*2+1][k];
							coverage += 4;
						}
						if( j > 0 )
						{
							value += color[i*2][j*2-1][k] + color[i*2+1][j*2-1][k];
							value += color[i*2][j*2-2][k] + color[i*2+1][j*2-2][k];
							coverage += 4;
						}
						if( j < (h - 1) )
						{
							value += color[i*2][j*2+2][k] + color[i*2+1][j*2+2][k];
							value += color[i*2][j*2+3][k] + color[i*2+1][j*2+3][k];
							coverage += 2;
						}
					}
					
					/* average */
					color[ i ][ j ][ k ] = (value / coverage);
				}
			}
		}
	}
	
	/* optionally create a debugging border around the lightmap */
	if( lightmapBorder )
	{
		for( i = 0; i < w; i++ )
		{
			color[i][0][0] = 255;
			color[i][0][1] = 0;
			color[i][0][2] = 0;

			color[i][h-1][0] = 255;
			color[i][h-1][1] = 0;
			color[i][h-1][2] = 0;
		}
		
		for ( i = 0 ; i < h ; i++ )
		{
			color[0][i][0] = 255;
			color[0][i][1] = 0;
			color[0][i][2] = 0;

			color[w-1][i][0] = 255;
			color[w-1][i][1] = 0;
			color[w-1][i][2] = 0;
		}
	}
	
	/* clamp the colors to bytes and store off */
	for( i = 0 ; i < w; i++ )
	{
		for( j = 0 ; j < h; j++ )
		{
			byte	tb[ 3 ];
			int		ti[ 3 ];
			byte	*lb;
			
			
			k = (ds->lightmapNum * LIGHTMAP_HEIGHT + ds->lightmapY + j) 
				* LIGHTMAP_WIDTH + ds->lightmapX + i;
			
			
			/* ydnar: store off the unclamped, unnormalized color for radiosity */
			if( bounce > 0 )
				RadStoreLightmapDiffuse( ds->lightmapNum, (ds->lightmapX + i), (ds->lightmapY + j), color[ i ][ j ] );
			
			
			/* ydnar: additive for bounce */
			lb = lightBytes + (k * 3);
			ColorToBytes( color[ i ][ j ], tb );
			if( bouncing )
			{
				ti[ 0 ] = lb[ 0 ];  ti[ 0 ] += tb[ 0 ];
				ti[ 1 ] = lb[ 1 ];  ti[ 1 ] += tb[ 1 ];
				ti[ 2 ] = lb[ 2 ];  ti[ 2 ] += tb[ 2 ];
				lb[ 0 ] = ti[ 0 ] <= 255 ? ti[ 0 ] : 255;
				lb[ 1 ] = ti[ 1 ] <= 255 ? ti[ 1 ] : 255;
				lb[ 2 ] = ti[ 2 ] <= 255 ? ti[ 2 ] : 255;
			}
			else
			{
				lb[ 0 ] = tb[ 0 ];
				lb[ 1 ] = tb[ 1 ];
				lb[ 2 ] = tb[ 2 ];
			}
		}
	}
	
	/* ydnar: changed this to make sense */
	if( mesh != NULL )
		FreeMesh( mesh );
	
	/* ydnar */
	FreeTWLights( &tw );
}





/*
FindBestTriangle() - ydnar
given a triangle and lightmap st coordinates, determine if the sample point lies inside better than the previous
returns qtrue if the sample point lies entirely inside of the triangle (barycentric coords all > 0)
*/

qboolean FindBestTriangle( float lm[ 2 ], drawVert_t *dv[ 3 ], drawVert_t *best[ 3 ], vec3_t bestBary )
{
	int		i;
	float	b, nadir, bestNadir;
	vec3_t	bary;


	/* calculate barycentric coordinates for this triangle */
	b = (dv[ 1 ]->lightmap[ 0 ] - dv[ 0 ]->lightmap[ 0 ]) * (dv[ 2 ]->lightmap[ 1 ] - dv[ 0 ]->lightmap[ 1 ]) -
		(dv[ 2 ]->lightmap[ 0 ] - dv[ 0 ]->lightmap[ 0 ]) * (dv[ 1 ]->lightmap[ 1 ] - dv[ 0 ]->lightmap[ 1 ]);
	
	/* check for degenerate triangle */
	if( fabs( b ) < EQUAL_EPSILON )
		return qfalse;
	
	bary[ 0 ] = ((dv[ 1 ]->lightmap[ 0 ] - lm[ 0 ]) * (dv[ 2 ]->lightmap[ 1 ] - lm[ 1 ]) -
		(dv[ 2 ]->lightmap[ 0 ] - lm[ 0 ]) * (dv[ 1 ]->lightmap[ 1 ] - lm[ 1 ])) / b;
	bary[ 1 ] = ((dv[ 2 ]->lightmap[ 0 ] - lm[ 0 ]) * (dv[ 0 ]->lightmap[ 1 ] - lm[ 1 ]) -
		(dv[ 0 ]->lightmap[ 0 ] - lm[ 0 ]) * (dv[ 2 ]->lightmap[ 1 ] - lm[ 1 ])) / b;
	bary[ 2 ] = ((dv[ 0 ]->lightmap[ 0 ] - lm[ 0 ]) * (dv[ 1 ]->lightmap[ 1 ] - lm[ 1 ]) -
		(dv[ 1 ]->lightmap[ 0 ] - lm[ 0 ]) * (dv[ 0 ]->lightmap[ 1 ] - lm[ 1 ])) / b;
	
	/* entirely inside the triangle? */
	if( bary[ 0 ] >= 0 && bary[ 1 ] >= 0 && bary[ 2 ] >= 0 )
	{
		/* this is best */
		VectorCopy( bary, bestBary );
		VectorCopy( dv, best );
		return qtrue;
	}
	
	/* find most negative coordinates */
	nadir = 0;
	bestNadir = 0;
	for( i = 0; i < 3; i++ )
	{
		if( bary[ i ] < nadir )
			nadir = bary[ i ];
		if( bestBary[ i ] < bestNadir )
			bestNadir = bestBary[ i ];
	}
	
	/* if the new worst-case (most negative) coordinate it greater than the previous, we have a new "best" */
	if( nadir > bestNadir )
	{
		/* this is almost best */
		VectorCopy( bary, bestBary );
		VectorCopy( dv, best );
	}
	
	/* return (outside) */
	return qfalse;
}



/*
FindSamplePoint() - ydnar
for a given surface (and potentially a subdivided mesh) and lightmap st coordinates, recover a sample location and normal
returns qtrue if a sample mostly inside a triangle was found, otherwise returns qfalse
*/

#define SAMPLE_EPSILON2 ((1.0 / (float) (LIGHTMAP_WIDTH * LIGHTMAP_HEIGHT)) * 3)

qboolean FindSamplePoint( dsurface_t *ds, mesh_t *mesh, float lm[ 2 ], vec3_t origin, vec3_t normal )
{
	drawVert_t		*verts;
	int				width, height;
	drawVert_t		*dv[ 3 ], *best[ 3 ];
	vec3_t			bestBary;
	float			total;
	int				i, j;
	qboolean		found;
	float			lm2[ 2 ], dist2;
	
	
	/* non-planar patches are not handled by this function! */
	if( mesh != NULL )
	{
		verts = mesh->verts;
		width = mesh->width;
		height = mesh->height;
	}
	
	/* clear the "best" values */
	for( i = 0; i < 3; i++ )
	{
		best[ i ] = NULL;
		bestBary[ i ] = -99999;
	}
	
	/* switch on type */
	switch( ds->surfaceType )
	{
		case MST_PLANAR:
			/* iterate through the triangles in the face */
			found = qfalse;
			for( i = 0; i < ds->numIndexes && found == qfalse; i += 3 )
			{
				/* get drawverts and fix the triangle */
				for( j = 0; j < 3; j++ )
					dv[ j ] = &yDrawVerts[ ds->firstVert + drawIndexes[ ds->firstIndex + i + j ] ];
				found = FindBestTriangle( lm, dv, best, bestBary );
			}
			break;
		
		case MST_PATCH:
			/* dummy check */
			if( mesh == NULL )
				return qfalse;
			
			/* iterate through the mesh quads */
			found = qfalse;
			printf( "MST_PATCH @ %8X: [%8X] (%3d x %3d)\n", ds, verts, width, height );
			for( i = 0; i < (width - 1) && found == qfalse; i++ )
			{
				for( j = 0; j < (height - 1) && found == qfalse; j++ )
				{
					/* get drawverts and fix first triangle */
					dv[ 0 ] = verts + j * width + i;
					dv[ 1 ] = dv[ 0 ] + width;
					dv[ 2 ] = dv[ 0 ] + width + 1;
					found = FindBestTriangle( lm, dv, best, bestBary );
					
					/* get drawverts and fix second triangle */
					dv[ 0 ] = verts + j * width + i;
					dv[ 1 ] = dv[ 0 ] + width + 1;
					dv[ 2 ] = dv[ 0 ] + 1;
					found = FindBestTriangle( lm, dv, best, bestBary );
				}
			}
			break;
		
		default:
			break;
	}
	
	/* if a suitable triangle wasn't found, then bail */
	if( best[ 0 ] == NULL )
		return qfalse;
	
	/* ydnar: debug code (remove me) */
	//if( found == qfalse )
	//	return qfalse;
	
	/* pin to nearest edge of best candidate triangle (this is dodgy code) */
	if( found == qfalse )
	{
		/* pin negative coordinates to 0 */
		for( i = 0; i < 3; i++ )
		{
			if( bestBary[ i ] < 0 )
			{
				bestBary[ (i + 1) % 3 ] += (bestBary[ i ] * 0.5 * bestBary[ (i + 1) % 3 ]);
				bestBary[ (i + 2) % 3 ] += (bestBary[ i ] * 0.5 * bestBary[ (i + 2) % 3 ]);
				bestBary[ i ] = 0;
			}
		}
		
		/* barycentric coordinates must add up to 1.0 */
		total = 0;
		for( i = 0; i < 3; i++ )
			total += bestBary[ i ];
		VectorScale( bestBary, (1.0 / total), bestBary );
	}
	
	/* given the barycentric coordinates, create an average position and normal */
	VectorClear( origin );
	VectorClear( normal );
	lm2[ 0 ] = lm2[ 1 ] = 0;
	for( i = 0; i < 3; i++ )
	{
		/* tiny optimization: don't bother adding when barycentric coordinate is zero */
		if( bestBary[ i ] > 0 )
		{
			VectorMA( origin, bestBary[ i ], best[ i ]->xyz, origin );
			VectorMA( normal, bestBary[ i ], best[ i ]->normal, normal );
			lm2[ 0 ] += bestBary[ i ] * best[ i ]->lightmap[ 0 ];
			lm2[ 1 ] += bestBary[ i ] * best[ i ]->lightmap[ 1 ];
		}
	}
	
	/* check to see if actual lightmap coords are too far from originals */
	dist2 = 0;
	for( i = 0; i < 2; i++ )
	{
		total = lm2[ i ] - lm[ i ];
		dist2 += (total * total);
	}
	if( dist2 > SAMPLE_EPSILON2 )
		return qfalse;
	
	/* return ok */
	return qtrue;
}






/*
=============
TraceLtm
=============

ydnar: this function has been replaced

*/

#define EXTRA_WIDTH		LIGHTMAP_WIDTH * EXTRASCALE
#define EXTRA_HEIGHT	LIGHTMAP_HEIGHT * EXTRASCALE
#define BOGUS_NUDGE		-99999
#define SEARCH_NUDGE	.0625
#define LIGHTMAP_NUDGE	0.5
#define NORMAL_NUDGE	1.0

void TraceLtm_( int num )
{
	dsurface_t		*ds;
	qboolean		planarPatch;
	float			lm[ 2 ];
	int				lmo[ 2 ], lms[ 2 ];
	int				i, j, k, cluster, w, h;
	int				x, y;
	vec3_t			origin, normal;
	byte			occluded[ EXTRA_WIDTH ][ EXTRA_HEIGHT ];
	vec3_t			color[ EXTRA_WIDTH][ EXTRA_HEIGHT ];
	traceWork_t		tw;
	vec3_t			average;
	int				count;
	mesh_t			srcMesh, *mesh = NULL, *subdivided = NULL;
	shaderInfo_t	*si;
	int				sampleWidth, sampleHeight, ssize;
	vec3_t			lightmapOrigin, lightmapVecs[ 2 ];
	int				widthtable[ LIGHTMAP_WIDTH ], heighttable[ LIGHTMAP_WIDTH ];
	
	
	/* get drawsurface and shader info */
	ds = &drawSurfaces[num];
	si = ShaderInfoForShader( dshaders[ ds->shaderNum ].shader );	/* ydnar: omg this is slow */
	
	/* ydnar: get a culled light list for this surface */
	CreateTWLightsForSurface( num, &tw );
	
	/* vertex-lit triangle model */
	if ( ds->surfaceType == MST_TRIANGLE_SOUP )
	{
		VertexLighting( num, !si->noVertexShadows, si->forceSunLight, 1.0, &tw );
		FreeTWLights( &tw );	/* ydnar */
		return;
	}
	
	/* nolightmap */
	if( ds->lightmapNum == -1 )
	{
		FreeTWLights( &tw );	/* ydnar */
		return;					/* doesn't need lighting at all */
	}

	/* calculate the vertex lighting for gouraud shade mode */
	if( !novertexlighting )
		VertexLighting( num, si->vertexShadows, si->forceSunLight, si->vertexScale, &tw );
	
	/* no lightmap? */
	if( ds->lightmapNum < 0 )
	{
		FreeTWLights( &tw );	/* ydnar */
		return;					/* doesn't need lightmap lighting */
	}
	
	/* get samplesize */
	ssize = samplesize;
	if( si->lightmapSampleSize )
		ssize = si->lightmapSampleSize;
	
	/* ydnar: get lightmap width and height */
	w = ds->lightmapWidth;
	h = ds->lightmapHeight;
	
	/* ydnar: extract samplesize from dsurf */
	if( w & 0xFFFF0000 )
	{
		ssize = (w & 0xFFFF0000) >> 16;
		w &= 0x0000FFFF;
	}
	
	/* ydnar: debug code */
	if( w > LIGHTMAP_WIDTH || h > LIGHTMAP_HEIGHT )
		Error( "Lightmap dimensions exceeded: (%d > %d || %d > %d)", w, LIGHTMAP_WIDTH, h, LIGHTMAP_HEIGHT );
	
	/* patchshadows? */
	if( si->patchShadows )
		tw.patchshadows = qtrue;
	else
		tw.patchshadows = patchshadows;
	
	/* ydnar: is this a planar patch? */
	planarPatch = qfalse;
	if( ds->patchWidth && ds->numIndexes == 6 )
		planarPatch = qtrue;
	
	/* ydnar: handle planar patches differently */
	if( ds->surfaceType == MST_PATCH )
	{
		srcMesh.width = ds->patchWidth;
		srcMesh.height = ds->patchHeight;
		srcMesh.verts = yDrawVerts + ds->firstVert;
		mesh = SubdivideMesh( srcMesh, 8, 999 );
		PutMeshOnCurve( *mesh );
		
		subdivided = RemoveLinearMeshColumnsRows( mesh );
		FreeMesh( mesh );

		mesh = SubdivideMeshQuads( subdivided, ssize, LIGHTMAP_WIDTH, widthtable, heighttable );
		if( planarPatch == qfalse && (mesh->width != w || mesh->height != h) )
		{
			Error( "Mesh lightmap miscount (%d) (%d != %d || %d != %d)",
				num, mesh->width, w, mesh->height, h );
		}
		
		/* ydnar: fix this fucking leak at some point */
		if( extra )
		{
			mesh_t	*mp;

			/* chop it up for more light samples (leaking memory...) */
			mp = mesh;//CopyMesh( mesh );
			mp = LinearSubdivideMesh( mp );
			mp = TransposeMesh( mp );
			mp = LinearSubdivideMesh( mp );
			mp = TransposeMesh( mp );

			mesh = mp;
		}
	}
	
	/* handle planar patches */
	else if( ds->surfaceType == MST_PATCH && planarPatch == qtrue )
	{
		vec3_t	*hack = (vec3_t*) &drawIndexes[ ds->firstIndex ];
		
		
		/* get normal */
		VectorCopy( ds->lightmapVecs[ 2 ], normal );
		
		/* get lightmap origin (what an ugly hack) */
		VectorCopy( ds->lightmapOrigin, lightmapOrigin );
		VectorCopy( hack[ 0 ], lightmapVecs[ 0 ] );
		VectorCopy( hack[ 1 ], lightmapVecs[ 1 ] );
	}
	
	/* handle brush faces */
	else
	{
		/* get normal */
		VectorCopy( ds->lightmapVecs[ 2 ], normal );
		
		/* ydnar: get lightmap origin (eliminated some redundancy) */
		VectorCopy( ds->lightmapOrigin, lightmapOrigin );
		VectorCopy( ds->lightmapVecs[ 0 ], lightmapVecs[ 0 ] );
		VectorCopy( ds->lightmapVecs[ 1 ], lightmapVecs[ 1 ] );
	}
	
	/* extra? */
	if( extra )
	{
		/* scale lightmap vectors and shift origin */
		VectorScale( lightmapVecs[ 0 ], 0.5, lightmapVecs[ 0 ] );
		VectorScale( lightmapVecs[ 1 ], 0.5, lightmapVecs[ 1 ] );
		VectorMA( lightmapOrigin, -0.5, lightmapVecs[ 0 ], lightmapOrigin );
		VectorMA( lightmapOrigin, -0.5, lightmapVecs[ 1 ], lightmapOrigin );
		
		/* scale sample size */
		sampleWidth = w * 2;
		sampleHeight = h * 2;
	}
	else
	{
		sampleWidth = w;
		sampleHeight = h;
	}
	
	/* clear colors */
	memset( color, 0, sizeof( color ) );

	/* set up integer sampling bounds */
	lmo[ 0 ] = (extra ? ds->lightmapX * 2 : ds->lightmapX);
	lmo[ 1 ] = (extra ? ds->lightmapY * 2 : ds->lightmapY);
	lms[ 0 ] = (extra ? LIGHTMAP_WIDTH * 2 : LIGHTMAP_WIDTH);
	lms[ 1 ] = (extra ? LIGHTMAP_HEIGHT * 2 : LIGHTMAP_HEIGHT);

	/* determine which samples are occluded */
	memset( occluded, qtrue, sizeof( occluded ) );
	for( x = 0; x < sampleWidth; x++ )
	{
		for( y = 0; y < sampleHeight; y++ )
		{
			vec3_t			sampleOrigin, sampleNormal;
			float			*nudge;
			vec3_t			nudged;
			static float	nudges[][ 2 ] =
							{
								{ 0, 0 },	/* try center first */
								{ -1, -1 },	/* row 1 */
								{ 0, -1 },
								{ 1, -1 },
								{ -1, 0 },	/* row 2 */
								{ 1, 0 },
								{ -1, 1 },	/* row 3 */
								{ 0, 1 },
								{ 1, 1 },
								{ BOGUS_NUDGE, BOGUS_NUDGE }
							};
			
			
			/* handle patches */
			if( ds->surfaceType == MST_PATCH && planarPatch == qfalse )
			{
				VectorCopy( mesh->verts[ y * mesh->width + x ].xyz, origin );
				VectorCopy( mesh->verts[ y * mesh->width + x ].normal, normal );
				VectorMA( origin, NORMAL_NUDGE, normal, origin );
				count = 1;
			}
			else
			{
				/* make n-tap samples to recover a valid origin and normal for a given lightmap texel */
				nudge = nudges[ 0 ];
				count = 0;
				VectorClear( origin );
				VectorClear( normal );
				while( nudge[ 0 ] > BOGUS_NUDGE )
				{
					/* nudge the lightmap position around a bit */
					for( i = 0; i < 3; i++ )
					{
						lm[ 0 ] = ((float) x + lmo[ 0 ] + (LIGHTMAP_NUDGE * nudge[ 0 ])) / lms[ 0 ];
						lm[ 1 ] = ((float) y + lmo[ 1 ] + (LIGHTMAP_NUDGE * nudge[ 1 ])) / lms[ 1 ];
					}
					nudge += 2;
					
					/* recover lightmap coordinates */
					printf( "N: %8X ", nudge );
					if( FindSamplePoint( ds, mesh, lm, sampleOrigin, sampleNormal ) )
					{
						/* use the first origin only */
						if( count == 0 )
							VectorCopy( sampleOrigin, origin );
						VectorAdd( normal, sampleNormal, normal );
						count++;
					}
				}
				
				///* average the origin */
				//if( count > 0 )
				//	VectorScale( origin, (1.0 / count), origin );
				
				/* fix the normal */
				VectorNormalize( normal, normal );
			}
			
			
			/* check for valid sample */
			if( count > 0 )
			{
				/* build perpendicular vectors for patches */
				if( mesh != NULL && planarPatch == qfalse )
					MakeNormalVectors( normal, lightmapVecs[ 0 ], lightmapVecs[ 1 ] );
				
				/* find a location in space that isn't in a solid */
				nudge = nudges[ 0 ];
				cluster = -1;
				while( nudge[ 0 ] > BOGUS_NUDGE && cluster == -1 )
				{
					/* nudge the vector around a bit */
					for( i = 0; i < 3; i++ )
					{
						nudged[ i ] = origin[ i ] + 
							+ (nudge[ 0 ] * SEARCH_NUDGE * lightmapVecs[ 0 ][ i ]) 
							+ (nudge[ 1 ] * SEARCH_NUDGE * lightmapVecs[ 1 ][ i ]);
					}
					nudge += 2;
					
					/* get pvs cluster */
					cluster = ClusterForPoint( nudged );
				}
				
				/* copy nudged to origin */
				VectorCopy( nudged, origin );
				
				/* occluded? */
				if( cluster == -1 )
					occluded[ x ][ y ] = qtrue;
				else
				{
					/* render normalmap instead of lighting values? */
					if( normalmap )
					{
						for( k = 0; k < 3; k++ )
							color[ x ][ y ][ k ] = normal[ k ] > 0 ? normal[ k ] * 128 : 0;
					}
					else
					{
						/* get the lighting at this sample */
						LightingAtSample( cluster, origin, normal, lightmapVecs, color[ x ][ y ], qtrue, qfalse, &tw );
						occluded[ x ][ y ] = qfalse;
					}
				}
			}
			
			/* ydnar: only clear occluded if color isn't black */
			if( VectorCompare( color[ x ][ y ], ambientColor ) == qfalse )
				occluded[ x ][ y ] = qfalse;
			
			/* set occluded/visible counts */
			if( numthreads == 1 )
			{
				if( occluded[ x ][ y ] )
					c_occluded++;
				else
					c_visible++;
			}
		}
	}

	/* ydnar: took over the dump flag for emitting radiosity maps */
	//%if( dump )
	//%	PrintOccluded( occluded, sampleWidth, sampleHeight );

	/* calculate average values for occluded samples */
	for( i = 0; i < sampleWidth; i++ )
	{
		for( j = 0; j < sampleHeight; j++ )
		{
			if( !occluded[i][j] )
				continue;
			
			/* scan all surrounding samples */
			count = 0;
			VectorClear( average );
			for( x = -1 ; x <= 1; x++ )
			{
				for( y = -1; y <= 1; y++ )
				{
					if( i + x < 0 || i + x >= sampleWidth )
						continue;
					if( j + y < 0 || j + y >= sampleHeight )
						continue;
					if( occluded[i+x][j+y] )
						continue;
					count++;
					VectorAdd( color[i+x][j+y], average, average );
				}
			}
			
			if( count )
				VectorScale( average, (1.0 / count), color[i][j] );
		}
	}
	
	/* average together the values if we are extra sampling */
	if( w != sampleWidth )
	{
		for( i = 0 ; i < w; i++ )
		{
			for( j = 0 ; j < h; j++ )
			{
				for( k = 0; k < 3; k++ )
				{
					float		value, coverage;
					
					
					/* sum 4 samples */
					value = color[i*2][j*2][k] + color[i*2][j*2+1][k] +
						color[i*2+1][j*2][k] + color[i*2+1][j*2+1][k];
					coverage = 4;
					
					/* sum some more */
					if( extraWide )
					{
						/* wider than box filter */
						if( i > 0 )
						{
							value += color[i*2-1][j*2][k] + color[i*2-1][j*2+1][k];
							value += color[i*2-2][j*2][k] + color[i*2-2][j*2+1][k];
							coverage += 4;
						}
						if( i < (w - 1) )
						{
							value += color[i*2+2][j*2][k] + color[i*2+2][j*2+1][k];
							value += color[i*2+3][j*2][k] + color[i*2+3][j*2+1][k];
							coverage += 4;
						}
						if( j > 0 )
						{
							value += color[i*2][j*2-1][k] + color[i*2+1][j*2-1][k];
							value += color[i*2][j*2-2][k] + color[i*2+1][j*2-2][k];
							coverage += 4;
						}
						if( j < (h - 1) )
						{
							value += color[i*2][j*2+2][k] + color[i*2+1][j*2+2][k];
							value += color[i*2][j*2+3][k] + color[i*2+1][j*2+3][k];
							coverage += 2;
						}
					}
					
					/* average */
					color[ i ][ j ][ k ] = (value / coverage);
				}
			}
		}
	}
	
	/* optionally create a debugging border around the lightmap */
	if( lightmapBorder )
	{
		for( i = 0; i < w; i++ )
		{
			color[i][0][0] = 255;
			color[i][0][1] = 0;
			color[i][0][2] = 0;

			color[i][h-1][0] = 255;
			color[i][h-1][1] = 0;
			color[i][h-1][2] = 0;
		}
		
		for ( i = 0 ; i < h ; i++ )
		{
			color[0][i][0] = 255;
			color[0][i][1] = 0;
			color[0][i][2] = 0;

			color[w-1][i][0] = 255;
			color[w-1][i][1] = 0;
			color[w-1][i][2] = 0;
		}
	}
	
	/* clamp the colors to bytes and store off */
	for( i = 0 ; i < w; i++ )
	{
		for( j = 0 ; j < h; j++ )
		{
			byte	tb[ 3 ];
			int		ti[ 3 ];
			byte	*lb;
			
			
			k = (ds->lightmapNum * LIGHTMAP_HEIGHT + ds->lightmapY + j) 
				* LIGHTMAP_WIDTH + ds->lightmapX + i;
			
			
			/* ydnar: store off the unclamped, unnormalized color for radiosity */
			if( bounce > 0 )
				RadStoreLightmapDiffuse( ds->lightmapNum, (ds->lightmapX + i), (ds->lightmapY + j), color[ i ][ j ] );
			
			
			/* ydnar: additive for bounce */
			lb = lightBytes + (k * 3);
			ColorToBytes( color[ i ][ j ], tb );
			if( bouncing )
			{
				ti[ 0 ] = lb[ 0 ];  ti[ 0 ] += tb[ 0 ];
				ti[ 1 ] = lb[ 1 ];  ti[ 1 ] += tb[ 1 ];
				ti[ 2 ] = lb[ 2 ];  ti[ 2 ] += tb[ 2 ];
				lb[ 0 ] = ti[ 0 ] <= 255 ? ti[ 0 ] : 255;
				lb[ 1 ] = ti[ 1 ] <= 255 ? ti[ 1 ] : 255;
				lb[ 2 ] = ti[ 2 ] <= 255 ? ti[ 2 ] : 255;
			}
			else
			{
				lb[ 0 ] = tb[ 0 ];
				lb[ 1 ] = tb[ 1 ];
				lb[ 2 ] = tb[ 2 ];
			}
		}
	}
	
	/* ydnar: changed this to make sense */
	if( mesh != NULL )
		FreeMesh( mesh );
	
	/* ydnar */
	FreeTWLights( &tw );
}