light.c

/*
===========================================================================
Copyright (C) 1999-2005 Id Software, Inc.

This file is part of Quake III Arena source code.

Quake III Arena source code is free software; you can redistribute it
and/or modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of the License,
or (at your option) any later version.

Quake III Arena source code is distributed in the hope that it will be
useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with Foobar; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
===========================================================================
*/
// light.c

#include "light.h"
#ifdef _WIN32
#ifdef _TTIMOBUILD
#include "pakstuff.h"
#else
#include "../libs/pakstuff.h"
#endif
#endif


#define	EXTRASCALE	2

typedef struct {
	float		plane[4];
	vec3_t		origin;
	vec3_t		vectors[2];
	shaderInfo_t	*si;
} filter_t;

#define	MAX_FILTERS	1024
filter_t	filters[MAX_FILTERS];
int			numFilters;

extern char	source[1024];

qboolean	notrace;
qboolean	patchshadows;
qboolean	dump;
qboolean	extra;
qboolean	extraWide;
qboolean	lightmapBorder;

qboolean	noSurfaces;

int			samplesize = 16;		//sample size in units
int			novertexlighting = 0;
int			nogridlighting = 0;

// for run time tweaking of all area sources in the level
float		areaScale =	0.25;

// for run time tweaking of all point sources in the level
float		pointScale = 7500;

qboolean	exactPointToPolygon = qtrue;

float		formFactorValueScale = 3;

float		linearScale = 1.0 / 8000;

light_t		*lights;
int			numPointLights;
int			numAreaLights;

FILE		*dumpFile;

int			c_visible, c_occluded;

//int			defaultLightSubdivide = 128;		// vary by surface size?
int			defaultLightSubdivide = 999;		// vary by surface size?

vec3_t		ambientColor;

vec3_t		surfaceOrigin[ MAX_MAP_DRAW_SURFS ];
int			entitySurface[ MAX_MAP_DRAW_SURFS ];

// 7,9,11 normalized to avoid being nearly coplanar with common faces
//vec3_t		sunDirection = { 0.441835, 0.56807, 0.694313 };
//vec3_t		sunDirection = { 0.45, 0, 0.9 };
//vec3_t		sunDirection = { 0, 0, 1 };

// these are usually overrided by shader values
vec3_t		sunDirection = { 0.45, 0.3, 0.9 };
vec3_t		sunLight = { 100, 100, 50 };



typedef struct {
	dbrush_t	*b;
	vec3_t		bounds[2];
} skyBrush_t;

int			numSkyBrushes;
skyBrush_t	skyBrushes[MAX_MAP_BRUSHES];


/*

the corners of a patch mesh will always be exactly at lightmap samples.
The dimensions of the lightmap will be equal to the average length of the control
mesh in each dimension divided by 2.
The lightmap sample points should correspond to the chosen subdivision points.

*/

/*
===============================================================

SURFACE LOADING

===============================================================
*/

#define	MAX_FACE_POINTS		128

/*
===============
SubdivideAreaLight

Subdivide area lights that are very large
A light that is subdivided will never backsplash, avoiding weird pools of light near edges
===============
*/
void SubdivideAreaLight( shaderInfo_t *ls, winding_t *w, vec3_t normal, 
						float areaSubdivide, qboolean backsplash ) {
	float			area, value, intensity;
	light_t			*dl, *dl2;
	vec3_t			mins, maxs;
	int				axis;
	winding_t		*front, *back;
	vec3_t			planeNormal;
	float			planeDist;

	if ( !w ) {
		return;
	}

	WindingBounds( w, mins, maxs );

	// check for subdivision
	for ( axis = 0 ; axis < 3 ; axis++ ) {
		if ( maxs[axis] - mins[axis] > areaSubdivide ) {
			VectorClear( planeNormal );
			planeNormal[axis] = 1;
			planeDist = ( maxs[axis] + mins[axis] ) * 0.5;
			ClipWindingEpsilon ( w, planeNormal, planeDist, ON_EPSILON, &front, &back );
			SubdivideAreaLight( ls, front, normal, areaSubdivide, qfalse );
			SubdivideAreaLight( ls, back, normal, areaSubdivide, qfalse );
			FreeWinding( w );
			return;
		}
	}

	// create a light from this
	area = WindingArea (w);
	if ( area <= 0 || area > 20000000 ) {
		return;
	}

	numAreaLights++;
	dl = malloc(sizeof(*dl));
	memset (dl, 0, sizeof(*dl));
	dl->next = lights;
	lights = dl;
	dl->type = emit_area;

	WindingCenter( w, dl->origin );
	dl->w = w;
	VectorCopy ( normal, dl->normal);
	dl->dist = DotProduct( dl->origin, normal );

	value = ls->value;
	intensity = value * area * areaScale;
	VectorAdd( dl->origin, dl->normal, dl->origin );

	VectorCopy( ls->color, dl->color );

	dl->photons = intensity;

	// emitColor is irrespective of the area
	VectorScale( ls->color, value*formFactorValueScale*areaScale, dl->emitColor );

	dl->si = ls;

	if ( ls->contents & CONTENTS_FOG ) {
		dl->twosided = qtrue;
	}

	// optionally create a point backsplash light
	if ( backsplash && ls->backsplashFraction > 0 ) {
		dl2 = malloc(sizeof(*dl));
		memset (dl2, 0, sizeof(*dl2));
		dl2->next = lights;
		lights = dl2;
		dl2->type = emit_point;

		VectorMA( dl->origin, ls->backsplashDistance, normal, dl2->origin );

		VectorCopy( ls->color, dl2->color );

		dl2->photons = dl->photons * ls->backsplashFraction;
		dl2->si = ls;
	}
}


/*
===============
CountLightmaps
===============
*/
void CountLightmaps( void ) {
	int			count;
	int			i;
	dsurface_t	*ds;

	qprintf ("--- CountLightmaps ---\n");
	count = 0;
	for ( i = 0 ; i < numDrawSurfaces ; i++ ) {
		// see if this surface is light emiting
		ds = &drawSurfaces[i];
		if ( ds->lightmapNum > count ) {
			count = ds->lightmapNum;
		}
	}

	count++;
	numLightBytes = count * LIGHTMAP_WIDTH * LIGHTMAP_HEIGHT * 3;
	if ( numLightBytes > MAX_MAP_LIGHTING ) {
		Error("MAX_MAP_LIGHTING exceeded");
	}

	qprintf( "%5i drawSurfaces\n", numDrawSurfaces );
	qprintf( "%5i lightmaps\n", count );
}

/*
===============
CreateSurfaceLights

This creates area lights
===============
*/
void CreateSurfaceLights( void ) {
	int				i, j, side;
	dsurface_t		*ds;
	shaderInfo_t	*ls;
	winding_t		*w;
	cFacet_t		*f;
	light_t			*dl;
	vec3_t			origin;
	drawVert_t		*dv;
	int				c_lightSurfaces;
	float			lightSubdivide;
	vec3_t			normal;

	qprintf ("--- CreateSurfaceLights ---\n");
	c_lightSurfaces = 0;

	for ( i = 0 ; i < numDrawSurfaces ; i++ ) {
		// see if this surface is light emiting
		ds = &drawSurfaces[i];

		ls = ShaderInfoForShader( dshaders[ ds->shaderNum].shader );
		if ( ls->value == 0 ) {
			continue;
		}

		// determine how much we need to chop up the surface
		if ( ls->lightSubdivide ) {
			lightSubdivide = ls->lightSubdivide;
		} else {
			lightSubdivide = defaultLightSubdivide;
		}

		c_lightSurfaces++;

		// an autosprite shader will become
		// a point light instead of an area light
		if ( ls->autosprite ) {
			// autosprite geometry should only have four vertexes
			if ( surfaceTest[i] ) {
				// curve or misc_model
				f = surfaceTest[i]->facets;
				if ( surfaceTest[i]->numFacets != 1 || f->numBoundaries != 4 ) {
					_printf( "WARNING: surface at (%i %i %i) has autosprite shader but isn't a quad\n",
						(int)f->points[0], (int)f->points[1], (int)f->points[2] );
				}
				VectorAdd( f->points[0], f->points[1], origin );
				VectorAdd( f->points[2], origin, origin );
				VectorAdd( f->points[3], origin, origin );
				VectorScale( origin, 0.25, origin );
			} else {
				// normal polygon
				dv = &drawVerts[ ds->firstVert ];
				if ( ds->numVerts != 4 ) {
					_printf( "WARNING: surface at (%i %i %i) has autosprite shader but %i verts\n",
						(int)dv->xyz[0], (int)dv->xyz[1], (int)dv->xyz[2] );
					continue;
				}

				VectorAdd( dv[0].xyz, dv[1].xyz, origin );
				VectorAdd( dv[2].xyz, origin, origin );
				VectorAdd( dv[3].xyz, origin, origin );
				VectorScale( origin, 0.25, origin );
			}


			numPointLights++;
			dl = malloc(sizeof(*dl));
			memset (dl, 0, sizeof(*dl));
			dl->next = lights;
			lights = dl;

			VectorCopy( origin, dl->origin );
			VectorCopy( ls->color, dl->color );
			dl->photons = ls->value * pointScale;
			dl->type = emit_point;
			continue;
		}

		// possibly create for both sides of the polygon
		for ( side = 0 ; side <= ls->twoSided ; side++ ) {
			// create area lights
			if ( surfaceTest[i] ) {
				// curve or misc_model
				for ( j = 0 ; j < surfaceTest[i]->numFacets ; j++ ) {
					f = surfaceTest[i]->facets + j;
					w = AllocWinding( f->numBoundaries );
					w->numpoints = f->numBoundaries;
					memcpy( w->p, f->points, f->numBoundaries * 12 );

					VectorCopy( f->surface, normal );
					if ( side ) {
						winding_t	*t;

						t = w;
						w = ReverseWinding( t );
						FreeWinding( t );
						VectorSubtract( vec3_origin, normal, normal );
					}
					SubdivideAreaLight( ls, w, normal, lightSubdivide, qtrue );
				}
			} else {
				// normal polygon

				w = AllocWinding( ds->numVerts );
				w->numpoints = ds->numVerts;
				for ( j = 0 ; j < ds->numVerts ; j++ ) {
					VectorCopy( drawVerts[ds->firstVert+j].xyz, w->p[j] );
				}
				VectorCopy( ds->lightmapVecs[2], normal );
				if ( side ) {
					winding_t	*t;

					t = w;
					w = ReverseWinding( t );
					FreeWinding( t );
					VectorSubtract( vec3_origin, normal, normal );
				}
				SubdivideAreaLight( ls, w, normal, lightSubdivide, qtrue );
			}
		}
	}

	_printf( "%5i light emitting surfaces\n", c_lightSurfaces );
}



/*
================
FindSkyBrushes
================
*/
void FindSkyBrushes( void ) {
	int				i, j;
	dbrush_t		*b;
	skyBrush_t		*sb;
	shaderInfo_t	*si;
	dbrushside_t	*s;

	// find the brushes
	for ( i = 0 ; i < numbrushes ; i++ ) {
		b = &dbrushes[i];
		for ( j = 0 ; j < b->numSides ; j++ ) {
			s = &dbrushsides[ b->firstSide + j ];
			if ( dshaders[ s->shaderNum ].surfaceFlags & SURF_SKY ) {
				sb = &skyBrushes[ numSkyBrushes ];
				sb->b = b;
				sb->bounds[0][0] = -dplanes[ dbrushsides[ b->firstSide + 0 ].planeNum ].dist - 1;
				sb->bounds[1][0] = dplanes[ dbrushsides[ b->firstSide + 1 ].planeNum ].dist + 1;
				sb->bounds[0][1] = -dplanes[ dbrushsides[ b->firstSide + 2 ].planeNum ].dist - 1;
				sb->bounds[1][1] = dplanes[ dbrushsides[ b->firstSide + 3 ].planeNum ].dist + 1;
				sb->bounds[0][2] = -dplanes[ dbrushsides[ b->firstSide + 4 ].planeNum ].dist - 1;
				sb->bounds[1][2] = dplanes[ dbrushsides[ b->firstSide + 5 ].planeNum ].dist + 1;
				numSkyBrushes++;
				break;
			}
		}
	}

	// default
	VectorNormalize( sunDirection, sunDirection );

	// find the sky shader
	for ( i = 0 ; i < numDrawSurfaces ; i++ ) {
		si = ShaderInfoForShader( dshaders[ drawSurfaces[i].shaderNum ].shader );
		if ( si->surfaceFlags & SURF_SKY ) {
			VectorCopy( si->sunLight, sunLight );
			VectorCopy( si->sunDirection, sunDirection );
			break;
		}
	}
}

/*
=================================================================

  LIGHT SETUP

=================================================================
*/

/*
==================
FindTargetEntity
==================
*/
entity_t *FindTargetEntity( const char *target ) {
	int			i;
	const char	*n;

	for ( i = 0 ; i < num_entities ; i++ ) {
		n = ValueForKey (&entities[i], "targetname");
		if ( !strcmp (n, target) ) {
			return &entities[i];
		}
	}

	return NULL;
}



/*
=============
CreateEntityLights
=============
*/
void CreateEntityLights (void)
{
	int		i;
	light_t	*dl;
	entity_t	*e, *e2;
	const char	*name;
	const char	*target;
	vec3_t	dest;
	const char	*_color;
	float	intensity;
	int		spawnflags;

	//
	// entities
	//
	for ( i = 0 ; i < num_entities ; i++ ) {
		e = &entities[i];
		name = ValueForKey (e, "classname");
		if (strncmp (name, "light", 5))
			continue;

		numPointLights++;
		dl = malloc(sizeof(*dl));
		memset (dl, 0, sizeof(*dl));
		dl->next = lights;
		lights = dl;

		spawnflags = FloatForKey (e, "spawnflags");
		if ( spawnflags & 1 ) {
			dl->linearLight = qtrue;
		}

		GetVectorForKey (e, "origin", dl->origin);
		dl->style = FloatForKey (e, "_style");
		if (!dl->style)
			dl->style = FloatForKey (e, "style");
		if (dl->style < 0)
			dl->style = 0;

		intensity = FloatForKey (e, "light");
		if (!intensity)
			intensity = FloatForKey (e, "_light");
		if (!intensity)
			intensity = 300;
		_color = ValueForKey (e, "_color");
		if (_color && _color[0])
		{
			sscanf (_color, "%f %f %f", &dl->color[0],&dl->color[1],&dl->color[2]);
			ColorNormalize (dl->color, dl->color);
		}
		else
			dl->color[0] = dl->color[1] = dl->color[2] = 1.0;

		intensity = intensity * pointScale;
		dl->photons = intensity;

		dl->type = emit_point;

		// lights with a target will be spotlights
		target = ValueForKey (e, "target");

		if ( target[0] ) {
			float	radius;
			float	dist;

			e2 = FindTargetEntity (target);
			if (!e2) {
				_printf ("WARNING: light at (%i %i %i) has missing target\n",
				(int)dl->origin[0], (int)dl->origin[1], (int)dl->origin[2]);
			} else {
				GetVectorForKey (e2, "origin", dest);
				VectorSubtract (dest, dl->origin, dl->normal);
				dist = VectorNormalize (dl->normal, dl->normal);
				radius = FloatForKey (e, "radius");
				if ( !radius ) {
					radius = 64;
				}
				if ( !dist ) {
					dist = 64;
				}
				dl->radiusByDist = (radius + 16) / dist;
				dl->type = emit_spotlight;
			}
		}
	}
}

//=================================================================

/*
================
SetEntityOrigins

Find the offset values for inline models
================
*/
void SetEntityOrigins( void ) {
	int			i, j;
	entity_t	*e;
	vec3_t		origin;
	const char	*key;
	int			modelnum;
	dmodel_t	*dm;

	for ( i=0 ; i < num_entities ; i++ ) {
		e = &entities[i];
		key = ValueForKey (e, "model");
		if ( key[0] != '*' ) {
			continue;
		}
		modelnum = atoi( key + 1 );
		dm = &dmodels[ modelnum ];

		// set entity surface to true for all surfaces for this model
		for ( j = 0 ; j < dm->numSurfaces ; j++ ) {
			entitySurface[ dm->firstSurface + j ] = qtrue;
		}

		key = ValueForKey (e, "origin");
		if ( !key[0] ) {
			continue;
		}
		GetVectorForKey ( e, "origin", origin );

		// set origin for all surfaces for this model
		for ( j = 0 ; j < dm->numSurfaces ; j++ ) {
			VectorCopy( origin, surfaceOrigin[ dm->firstSurface + j ] );
		}
	}
}


/*
=================================================================


=================================================================
*/

#define	MAX_POINTS_ON_WINDINGS	64

/*
================
PointToPolygonFormFactor
================
*/
float	PointToPolygonFormFactor( const vec3_t point, const vec3_t normal, const winding_t *w ) {
	vec3_t		triVector, triNormal;
	int			i, j;
	vec3_t		dirs[MAX_POINTS_ON_WINDING];
	float		total;
	float		dot, angle, facing;

	for ( i = 0 ; i < w->numpoints ; i++ ) {
		VectorSubtract( w->p[i], point, dirs[i] );
		VectorNormalize( dirs[i], dirs[i] );
	}

	// duplicate first vertex to avoid mod operation
	VectorCopy( dirs[0], dirs[i] );

	total = 0;
	for ( i = 0 ; i < w->numpoints ; i++ ) {
		j = i+1;
		dot = DotProduct( dirs[i], dirs[j] );

		// roundoff can cause slight creep, which gives an IND from acos
		if ( dot > 1.0 ) {
			dot = 1.0;
		} else if ( dot < -1.0 ) {
			dot = -1.0;
		}
		
		angle = acos( dot );
		CrossProduct( dirs[i], dirs[j], triVector );
		if ( VectorNormalize( triVector, triNormal ) < 0.0001 ) {
			continue;
		}
		facing = DotProduct( normal, triNormal );
		total += facing * angle;

		if ( total > 6.3 || total < -6.3 ) {
			static qboolean printed;

			if ( !printed ) {
				printed = qtrue;
				_printf( "WARNING: bad PointToPolygonFormFactor: %f at %1.1f %1.1f %1.1f from %1.1f %1.1f %1.1f\n", total,
					w->p[i][0], w->p[i][1], w->p[i][2], point[0], point[1], point[2]);
			}
			return 0;
		}

	}

	total /= 2*3.141592657;		// now in the range of 0 to 1 over the entire incoming hemisphere

	return total;
}


/*
================
FilterTrace

Returns 0 to 1.0 filter fractions for the given trace
================
*/
void	FilterTrace( const vec3_t start, const vec3_t end, vec3_t filter ) {
	float		d1, d2;
	filter_t	*f;
	int			filterNum;
	vec3_t		point;
	float		frac;
	int			i;
	float		s, t;
	int			u, v;
	int			x, y;
	byte		*pixel;
	float		radius;
	float		len;
	vec3_t		total;

	filter[0] = 1.0;
	filter[1] = 1.0;
	filter[2] = 1.0;

	for ( filterNum = 0 ; filterNum < numFilters ; filterNum++ ) {
		f = &filters[ filterNum ];

		// see if the plane is crossed
		d1 = DotProduct( start, f->plane ) - f->plane[3];
		d2 = DotProduct( end, f->plane ) - f->plane[3];

		if ( ( d1 < 0 ) == ( d2 < 0 ) ) {
			continue;
		}

		// calculate the crossing point
		frac = d1 / ( d1 - d2 );

		for ( i = 0 ; i < 3 ; i++ ) {
			point[i] = start[i] + frac * ( end[i] - start[i] );
		}

		VectorSubtract( point, f->origin, point );

		s = DotProduct( point, f->vectors[0] );
		t = 1.0 - DotProduct( point, f->vectors[1] );
		if ( s < 0 || s >= 1.0 || t < 0 || t >= 1.0 ) {
			continue;
		}

		// decide the filter size
		radius = 10 * frac;
		len = VectorLength( f->vectors[0] );
		if ( !len ) {
			continue;
		}
		radius = radius * len * f->si->width;

		// look up the filter, taking multiple samples
		VectorClear( total );
		for ( u = -1 ; u <= 1 ; u++ ) {
			for ( v = -1 ; v <=1 ; v++ ) {
				x = s * f->si->width + u * radius;
				if ( x < 0 ) {
					x = 0;
				}
				if ( x >= f->si->width ) {
					x = f->si->width - 1;
				}
				y = t * f->si->height + v * radius;
				if ( y < 0 ) {
					y = 0;
				}
				if ( y >= f->si->height ) {
					y = f->si->height - 1;
				}

				pixel = f->si->pixels + ( y * f->si->width + x ) * 4;
				total[0] += pixel[0];
				total[1] += pixel[1];
				total[2] += pixel[2];
			}
		}

		filter[0] *= total[0]/(255.0*9);
		filter[1] *= total[1]/(255.0*9);
		filter[2] *= total[2]/(255.0*9);
	}

}

/*
================
SunToPoint

Returns an amount of light to add at the point
================
*/
int		c_sunHit, c_sunMiss;
void SunToPoint( const vec3_t origin, traceWork_t *tw, vec3_t addLight ) {
	int			i;
	trace_t		trace;
	skyBrush_t	*b;
	vec3_t		end;

	if ( !numSkyBrushes ) {
		VectorClear( addLight );
		return;
	}

	VectorMA( origin, MAX_WORLD_COORD * 2, sunDirection, end );

	TraceLine( origin, end, &trace, qtrue, tw );

	// see if trace.hit is inside a sky brush
	for ( i = 0 ; i < numSkyBrushes ; i++) {
		b = &skyBrushes[ i ];

		// this assumes that sky brushes are axial...
		if (   trace.hit[0] < b->bounds[0][0] 
			|| trace.hit[0] > b->bounds[1][0]
			|| trace.hit[1] < b->bounds[0][1]
			|| trace.hit[1] > b->bounds[1][1]
			|| trace.hit[2] < b->bounds[0][2]
			|| trace.hit[2] > b->bounds[1][2] ) {
			continue;
		}


		// trace again to get intermediate filters
		TraceLine( origin, trace.hit, &trace, qtrue, tw );

		// we hit the sky, so add sunlight
		if ( numthreads == 1 ) {
			c_sunHit++;
		}
		addLight[0] = trace.filter[0] * sunLight[0];
		addLight[1] = trace.filter[1] * sunLight[1];
		addLight[2] = trace.filter[2] * sunLight[2];

		return;
	}

	if ( numthreads == 1 ) {
		c_sunMiss++;
	}

	VectorClear( addLight );
}

/*
================
SunToPlane
================
*/
void SunToPlane( const vec3_t origin, const vec3_t normal, vec3_t color, traceWork_t *tw ) {
	float		angle;
	vec3_t		sunColor;

	if ( !numSkyBrushes ) {
		return;
	}

	angle = DotProduct( normal, sunDirection );
	if ( angle <= 0 ) {
		return;		// facing away
	}

	SunToPoint( origin, tw, sunColor );
	VectorMA( color, angle, sunColor, color );
}

/*
================
LightingAtSample
================
*/
void LightingAtSample( vec3_t origin, vec3_t normal, vec3_t color, 
					  qboolean testOcclusion, qboolean forceSunLight, traceWork_t *tw ) {
	light_t		*light;
	trace_t		trace;
	float		angle;
	float		add;
	float		dist;
	vec3_t		dir;

	VectorCopy( ambientColor, color );

	// trace to all the lights
	for ( light = lights ; light ; light = light->next ) {

		//MrE: if the light is behind the surface
		if ( DotProduct(light->origin, normal) - DotProduct(normal, origin) < 0 )
			continue;
		// testing exact PTPFF
		if ( exactPointToPolygon && light->type == emit_area ) {
			float		factor;
			float		d;
			vec3_t		pushedOrigin;

			// see if the point is behind the light
			d = DotProduct( origin, light->normal ) - light->dist;
			if ( !light->twosided ) {
				if ( d < -1 ) {
					continue;		// point is behind light
				}
			}

			// test occlusion and find light filters
			// clip the line, tracing from the surface towards the light
			if ( !notrace && testOcclusion ) {
				TraceLine( origin, light->origin, &trace, qfalse, tw );

				// other light rays must not hit anything
				if ( trace.passSolid ) {
					continue;
				}
			} else {
				trace.filter[0] = 1.0;
				trace.filter[1] = 1.0;
				trace.filter[2] = 1.0;
			}

			// nudge the point so that it is clearly forward of the light
			// so that surfaces meeting a light emiter don't get black edges
			if ( d > -8 && d < 8 ) {
				VectorMA( origin, (8-d), light->normal, pushedOrigin );	
			} else {
				VectorCopy( origin, pushedOrigin );
			}

			// calculate the contribution
			factor = PointToPolygonFormFactor( pushedOrigin, normal, light->w );
			if ( factor <= 0 ) {
				if ( light->twosided ) {
					factor = -factor;
				} else {
					continue;
				}
			}
			color[0] += factor * light->emitColor[0] * trace.filter[0];
			color[1] += factor * light->emitColor[1] * trace.filter[1];
			color[2] += factor * light->emitColor[2] * trace.filter[2];

			continue;
		}

		// calculate the amount of light at this sample
		if ( light->type == emit_point ) {
			VectorSubtract( light->origin, origin, dir );
			dist = VectorNormalize( dir, dir );
			// clamp the distance to prevent super hot spots
			if ( dist < 16 ) {
				dist = 16;
			}
			angle = DotProduct( normal, dir );
			if ( light->linearLight ) {
				add = angle * light->photons * linearScale - dist;
				if ( add < 0 ) {
					add = 0;
				}
			} else {
				add = light->photons / ( dist * dist ) * angle;
			}
		} else if ( light->type == emit_spotlight ) {
			float	distByNormal;
			vec3_t	pointAtDist;
			float	radiusAtDist;
			float	sampleRadius;
			vec3_t	distToSample;
			float	coneScale;

			VectorSubtract( light->origin, origin, dir );

			distByNormal = -DotProduct( dir, light->normal );
			if ( distByNormal < 0 ) {
				continue;
			}
			VectorMA( light->origin, distByNormal, light->normal, pointAtDist );
			radiusAtDist = light->radiusByDist * distByNormal;

			VectorSubtract( origin, pointAtDist, distToSample );
			sampleRadius = VectorLength( distToSample );

			if ( sampleRadius >= radiusAtDist ) {
				continue;		// outside the cone
			}
			if ( sampleRadius <= radiusAtDist - 32 ) {
				coneScale = 1.0;	// fully inside
			} else {
				coneScale = ( radiusAtDist - sampleRadius ) / 32.0;
			}
			
			dist = VectorNormalize( dir, dir );
			// clamp the distance to prevent super hot spots
			if ( dist < 16 ) {
				dist = 16;
			}
			angle = DotProduct( normal, dir );
			add = light->photons / ( dist * dist ) * angle * coneScale;

		} else if ( light->type == emit_area ) {
			VectorSubtract( light->origin, origin, dir );
			dist = VectorNormalize( dir, dir );
			// clamp the distance to prevent super hot spots
			if ( dist < 16 ) {
				dist = 16;
			}
			angle = DotProduct( normal, dir );
			if ( angle <= 0 ) {
				continue;
			}
			angle *= -DotProduct( light->normal, dir );
			if ( angle <= 0 ) {
				continue;
			}

			if ( light->linearLight ) {
				add = angle * light->photons * linearScale - dist;
				if ( add < 0 ) {
					add = 0;
				}
			} else {
				add = light->photons / ( dist * dist ) * angle;
			}
		}

		if ( add <= 1.0 ) {
			continue;
		}

		// clip the line, tracing from the surface towards the light
		if ( !notrace && testOcclusion ) {
			TraceLine( origin, light->origin, &trace, qfalse, tw );

			// other light rays must not hit anything
			if ( trace.passSolid ) {
				continue;
			}
		} else {
			trace.filter[0] = 1;
			trace.filter[1] = 1;
			trace.filter[2] = 1;
		}
		
		// add the result
		color[0] += add * light->color[0] * trace.filter[0];
		color[1] += add * light->color[1] * trace.filter[1];
		color[2] += add * light->color[2] * trace.filter[2];
	}

	//
	// trace directly to the sun
	//
	if ( testOcclusion || forceSunLight ) {
		SunToPlane( origin, normal, color, tw );
	}
}

/*
=============
PrintOccluded

For debugging
=============
*/
void PrintOccluded( byte occluded[LIGHTMAP_WIDTH*EXTRASCALE][LIGHTMAP_HEIGHT*EXTRASCALE], 
				   int width, int height ) {
	int	i, j;

	_printf( "\n" );

	for ( i = 0 ; i < height ; i++ ) {
		for ( j = 0 ; j < width ; j++ ) {
			_printf("%i", (int)occluded[j][i] );
		}
		_printf( "\n" );
	}
}


/*
=============
VertexLighting

Vertex lighting will completely ignore occlusion, because
shadows would not be resolvable anyway.
=============
*/
void VertexLighting( dsurface_t *ds, qboolean testOcclusion, qboolean forceSunLight, float scale, traceWork_t *tw ) {
	int			i, j;
	drawVert_t	*dv;
	vec3_t		sample, normal;
	float		max;

	VectorCopy( ds->lightmapVecs[2], normal );

	// generate vertex lighting
	for ( i = 0 ; i < ds->numVerts ; i++ ) {
		dv = &drawVerts[ ds->firstVert + i ];

		if ( ds->patchWidth ) {
			LightingAtSample( dv->xyz, dv->normal, sample, testOcclusion, forceSunLight, tw );
		}
		else if (ds->surfaceType == MST_TRIANGLE_SOUP) {
			LightingAtSample( dv->xyz, dv->normal, sample, testOcclusion, forceSunLight, tw );
		}
		else {
			LightingAtSample( dv->xyz, normal, sample, testOcclusion, forceSunLight, tw );
		}

		if (scale >= 0)
			VectorScale(sample, scale, sample);
		// clamp with color normalization
		max = sample[0];
		if ( sample[1] > max ) {
			max = sample[1];
		}
		if ( sample[2] > max ) {
			max = sample[2];
		}
		if ( max > 255 ) {
			VectorScale( sample, 255/max, sample );
		}

		// save the sample
		for ( j = 0 ; j < 3 ; j++ ) {
			if ( sample[j] > 255 ) {
				sample[j] = 255;
			}
			dv->color[j] = sample[j];
		}

		// Don't bother writing alpha since it will already be set to 255,
		// plus we don't want to write over alpha generated by SetTerrainTextures
		//dv->color[3] = 255;
	}
}


/*
=================
LinearSubdivideMesh

For extra lighting, just midpoint one of the axis.
The edges are clamped at the original edges.
=================
*/
mesh_t *LinearSubdivideMesh( mesh_t *in ) {
	int			i, j;
	mesh_t		*out;
	drawVert_t	*v1, *v2, *vout;

	out = malloc( sizeof( *out ) );

	out->width = in->width * 2;
	out->height = in->height;
	out->verts = malloc( out->width * out->height * sizeof(*out->verts) );
	for ( j = 0 ; j < in->height ; j++ ) {
		out->verts[ j * out->width + 0 ] = in->verts[ j * in->width + 0 ];
		out->verts[ j * out->width + out->width - 1 ] = in->verts[ j * in->width + in->width - 1 ];
		for ( i = 1 ; i < out->width - 1 ; i+= 2 ) {
			v1 = in->verts + j * in->width + (i >> 1);
			v2 = v1 + 1;
			vout = out->verts + j * out->width + i;

			vout->xyz[0] = 0.75 * v1->xyz[0] + 0.25 * v2->xyz[0];
			vout->xyz[1] = 0.75 * v1->xyz[1] + 0.25 * v2->xyz[1];
			vout->xyz[2] = 0.75 * v1->xyz[2] + 0.25 * v2->xyz[2];

			vout->normal[0] = 0.75 * v1->normal[0] + 0.25 * v2->normal[0];
			vout->normal[1] = 0.75 * v1->normal[1] + 0.25 * v2->normal[1];
			vout->normal[2] = 0.75 * v1->normal[2] + 0.25 * v2->normal[2];

			VectorNormalize( vout->normal, vout->normal );

			vout++;

			vout->xyz[0] = 0.25 * v1->xyz[0] + 0.75 * v2->xyz[0];
			vout->xyz[1] = 0.25 * v1->xyz[1] + 0.75 * v2->xyz[1];
			vout->xyz[2] = 0.25 * v1->xyz[2] + 0.75 * v2->xyz[2];

			vout->normal[0] = 0.25 * v1->normal[0] + 0.75 * v2->normal[0];
			vout->normal[1] = 0.25 * v1->normal[1] + 0.75 * v2->normal[1];
			vout->normal[2] = 0.25 * v1->normal[2] + 0.75 * v2->normal[2];

			VectorNormalize( vout->normal, vout->normal );

		}
	}

	FreeMesh( in );

	return out;
}

/*
==============
ColorToBytes
==============
*/
void ColorToBytes( const float *color, byte *colorBytes ) {
	float	max;
	vec3_t	sample;

	VectorCopy( color, sample );

	// clamp with color normalization
	max = sample[0];
	if ( sample[1] > max ) {
		max = sample[1];
	}
	if ( sample[2] > max ) {
		max = sample[2];
	}
	if ( max > 255 ) {
		VectorScale( sample, 255/max, sample );
	}
	colorBytes[ 0 ] = sample[0];
	colorBytes[ 1 ] = sample[1];
	colorBytes[ 2 ] = sample[2];
}



/*
=============
TraceLtm
=============
*/
void TraceLtm( int num ) {
	dsurface_t	*ds;
	int			i, j, k;
	int			x, y;
	int			position, numPositions;
	vec3_t		base, origin, normal;
	byte		occluded[LIGHTMAP_WIDTH*EXTRASCALE][LIGHTMAP_HEIGHT*EXTRASCALE];
	vec3_t		color[LIGHTMAP_WIDTH*EXTRASCALE][LIGHTMAP_HEIGHT*EXTRASCALE];
	traceWork_t	tw;
	vec3_t		average;
	int			count;
	mesh_t		srcMesh, *mesh, *subdivided;
	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];

	ds = &drawSurfaces[num];
	si = ShaderInfoForShader( dshaders[ ds->shaderNum].shader );

	// vertex-lit triangle model
	if ( ds->surfaceType == MST_TRIANGLE_SOUP ) {
		VertexLighting( ds, !si->noVertexShadows, si->forceSunLight, 1.0, &tw );
		return;
	}
	
	if ( ds->lightmapNum == -1 ) {
		return;		// doesn't need lighting at all
	}

	if (!novertexlighting) {
		// calculate the vertex lighting for gouraud shade mode
		VertexLighting( ds, si->vertexShadows, si->forceSunLight, si->vertexScale, &tw );
	}

	if ( ds->lightmapNum < 0 ) {
		return;		// doesn't need lightmap lighting
	}

	si = ShaderInfoForShader( dshaders[ ds->shaderNum].shader );
	ssize = samplesize;
	if (si->lightmapSampleSize)
		ssize = si->lightmapSampleSize;

	if (si->patchShadows)
		tw.patchshadows = qtrue;
	else
		tw.patchshadows = patchshadows;

	if ( ds->surfaceType == MST_PATCH ) {
		srcMesh.width = ds->patchWidth;
		srcMesh.height = ds->patchHeight;
		srcMesh.verts = drawVerts + ds->firstVert;
		mesh = SubdivideMesh( srcMesh, 8, 999 );
		PutMeshOnCurve( *mesh );
		MakeMeshNormals( *mesh );

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

		mesh = SubdivideMeshQuads( subdivided, ssize, LIGHTMAP_WIDTH, widthtable, heighttable);
		if ( mesh->width != ds->lightmapWidth || mesh->height != ds->lightmapHeight ) {
			Error( "Mesh lightmap miscount");
		}

		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;
		}
	} else {
		VectorCopy( ds->lightmapVecs[2], normal );

		if ( !extra ) {
			VectorCopy( ds->lightmapOrigin, lightmapOrigin );
			VectorCopy( ds->lightmapVecs[0], lightmapVecs[0] );
			VectorCopy( ds->lightmapVecs[1], lightmapVecs[1] );
		} else {
			// sample at a closer spacing for antialiasing
			VectorCopy( ds->lightmapOrigin, lightmapOrigin );
			VectorScale( ds->lightmapVecs[0], 0.5, lightmapVecs[0] );
			VectorScale( ds->lightmapVecs[1], 0.5, lightmapVecs[1] );
			VectorMA( lightmapOrigin, -0.5, lightmapVecs[0], lightmapOrigin );
			VectorMA( lightmapOrigin, -0.5, lightmapVecs[1], lightmapOrigin );
		}
	}

	if ( extra ) {
		sampleWidth = ds->lightmapWidth * 2;
		sampleHeight = ds->lightmapHeight * 2;
	} else {
		sampleWidth = ds->lightmapWidth;
		sampleHeight = ds->lightmapHeight;
	}

	memset ( color, 0, sizeof( color ) );

	// determine which samples are occluded
	memset ( occluded, 0, sizeof( occluded ) );
	for ( i = 0 ; i < sampleWidth ; i++ ) {
		for ( j = 0 ; j < sampleHeight ; j++ ) {

			if ( ds->patchWidth ) {
				numPositions = 9;
				VectorCopy( mesh->verts[j*mesh->width+i].normal, normal );
				// VectorNormalize( 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
			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;
				}
				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;
			}
			
			if ( numthreads == 1 ) {
				c_visible++;
			}
			occluded[i][j] = qfalse;
			LightingAtSample( origin, normal, color[i][j], qtrue, qfalse, &tw );
		}
	}

	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 ( ds->lightmapWidth != sampleWidth ) {
		for ( i = 0 ; i < ds->lightmapWidth ; i++ ) {
			for ( j = 0 ; j < ds->lightmapHeight ; j++ ) {
				for ( k = 0 ; k < 3 ; k++ ) {
					float		value, coverage;

					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;
					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 < ds->lightmapWidth - 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 < ds->lightmapHeight - 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;
						}
					}

					color[i][j][k] = value / coverage;
				}
			}
		}
	}

	// optionally create a debugging border around the lightmap
	if ( lightmapBorder ) {
		for ( i = 0 ; i < ds->lightmapWidth ; i++ ) {
			color[i][0][0] = 255;
			color[i][0][1] = 0;
			color[i][0][2] = 0;

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

			color[ds->lightmapWidth-1][i][0] = 255;
			color[ds->lightmapWidth-1][i][1] = 0;
			color[ds->lightmapWidth-1][i][2] = 0;
		}
	}

	// clamp the colors to bytes and store off
	for ( i = 0 ; i < ds->lightmapWidth ; i++ ) {
		for ( j = 0 ; j < ds->lightmapHeight ; j++ ) {
			k = ( ds->lightmapNum * LIGHTMAP_HEIGHT + ds->lightmapY + j) 
				* LIGHTMAP_WIDTH + ds->lightmapX + i;

			ColorToBytes( color[i][j], lightBytes + k*3 );
		}
	}

	if (ds->surfaceType == MST_PATCH)
	{
		FreeMesh(mesh);
	}
}


//=============================================================================

vec3_t	gridMins;
vec3_t	gridSize = { 64, 64, 128 };
int		gridBounds[3];


/*
========================
LightContributionToPoint
========================
*/
qboolean LightContributionToPoint( const light_t *light, const vec3_t origin,
								  vec3_t color, traceWork_t *tw ) {
	trace_t		trace;
	float		add;

	add = 0;

	VectorClear( color );

	// testing exact PTPFF
	if ( exactPointToPolygon && light->type == emit_area ) {
		float		factor;
		float		d;
		vec3_t		normal;

		// see if the point is behind the light
		d = DotProduct( origin, light->normal ) - light->dist;
		if ( !light->twosided ) {
			if ( d < 1 ) {
				return qfalse;		// point is behind light
			}
		}

		// test occlusion
		// clip the line, tracing from the surface towards the light
		TraceLine( origin, light->origin, &trace, qfalse, tw );
		if ( trace.passSolid ) {
			return qfalse;
		}

		// calculate the contribution
		VectorSubtract( light->origin, origin, normal );
		if ( VectorNormalize( normal, normal ) == 0 ) {
			return qfalse;
		}
		factor = PointToPolygonFormFactor( origin, normal, light->w );
		if ( factor <= 0 ) {
			if ( light->twosided ) {
				factor = -factor;
			} else {
				return qfalse;
			}
		}
		VectorScale( light->emitColor, factor, color );
		return qtrue;
	}

	// calculate the amount of light at this sample
	if ( light->type == emit_point || light->type == emit_spotlight ) {
		vec3_t		dir;
		float		dist;

		VectorSubtract( light->origin, origin, dir );
		dist = VectorLength( dir );
		// clamp the distance to prevent super hot spots
		if ( dist < 16 ) {
			dist = 16;
		}
		if ( light->linearLight ) {
			add = light->photons * linearScale - dist;
			if ( add < 0 ) {
				add = 0;
			}
		} else {
			add = light->photons / ( dist * dist );
		}
	} else {
		return qfalse;
	}

	if ( add <= 1.0 ) {
		return qfalse;
	}

	// clip the line, tracing from the surface towards the light
	TraceLine( origin, light->origin, &trace, qfalse, tw );

	// other light rays must not hit anything
	if ( trace.passSolid ) {
		return qfalse;
	}

	// add the result
	color[0] = add * light->color[0];
	color[1] = add * light->color[1];
	color[2] = add * light->color[2];

	return qtrue;
}

typedef struct {
	vec3_t		dir;
	vec3_t		color;
} contribution_t;

/*
=============
TraceGrid

Grid samples are foe quickly determining the lighting
of dynamically placed entities in the world
=============
*/
#define	MAX_CONTRIBUTIONS	1024
void TraceGrid( int num ) {
	int			x, y, z;
	vec3_t		origin;
	light_t		*light;
	vec3_t		color;
	int			mod;
	vec3_t		directedColor;
	vec3_t		summedDir;
	contribution_t	contributions[MAX_CONTRIBUTIONS];
	int			numCon;
	int			i;
	traceWork_t	tw;
	float		addSize;

	mod = num;
	z = mod / ( gridBounds[0] * gridBounds[1] );
	mod -= z * ( gridBounds[0] * gridBounds[1] );

	y = mod / gridBounds[0];
	mod -= y * gridBounds[0];

	x = mod;

	origin[0] = gridMins[0] + x * gridSize[0];
	origin[1] = gridMins[1] + y * gridSize[1];
	origin[2] = gridMins[2] + z * gridSize[2];

	if ( PointInSolid( origin ) ) {
		vec3_t	baseOrigin;
		int		step;

		VectorCopy( origin, baseOrigin );

		// try to nudge the origin around to find a valid point
		for ( step = 9 ; step <= 18 ; step += 9 ) {
			for ( i = 0 ; i < 8 ; i++ ) {
				VectorCopy( baseOrigin, origin );
				if ( i & 1 ) {
					origin[0] += step;
				} else {
					origin[0] -= step;
				}
				if ( i & 2 ) {
					origin[1] += step;
				} else {
					origin[1] -= step;
				}
				if ( i & 4 ) {
					origin[2] += step;
				} else {
					origin[2] -= step;
				}

				if ( !PointInSolid( origin ) ) {
					break;
				}
			}
			if ( i != 8 ) {
				break;
			}
		}
		if ( step > 18 ) {
			// can't find a valid point at all
			for ( i = 0 ; i < 8 ; i++ ) {
				gridData[ num*8 + i ] = 0;
			}
			return;
		}
	}

	VectorClear( summedDir );

	// trace to all the lights

	// find the major light direction, and divide the
	// total light between that along the direction and
	// the remaining in the ambient 
	numCon = 0;
	for ( light = lights ; light ; light = light->next ) {
		vec3_t		add;
		vec3_t		dir;
		float		addSize;

		if ( !LightContributionToPoint( light, origin, add, &tw ) ) {
			continue;
		}

		VectorSubtract( light->origin, origin, dir );
		VectorNormalize( dir, dir );

		VectorCopy( add, contributions[numCon].color );
		VectorCopy( dir, contributions[numCon].dir );
		numCon++;

		addSize = VectorLength( add );
		VectorMA( summedDir, addSize, dir, summedDir );

		if ( numCon == MAX_CONTRIBUTIONS-1 ) {
			break;
		}
	}

	//
	// trace directly to the sun
	//
	SunToPoint( origin, &tw, color );
	addSize = VectorLength( color );
	if ( addSize > 0 ) {
		VectorCopy( color, contributions[numCon].color );
		VectorCopy( sunDirection, contributions[numCon].dir );
		VectorMA( summedDir, addSize, sunDirection, summedDir );
		numCon++;
	}


	// now that we have identified the primary light direction,
	// go back and seperate all the light into directed and ambient
	VectorNormalize( summedDir, summedDir );
	VectorCopy( ambientColor, color );
	VectorClear( directedColor );

	for ( i = 0 ; i < numCon ; i++ ) {
		float	d;

		d = DotProduct( contributions[i].dir, summedDir );
		if ( d < 0 ) {
			d = 0;
		}

		VectorMA( directedColor, d, contributions[i].color, directedColor );

		// the ambient light will be at 1/4 the value of directed light
		d = 0.25 * ( 1.0 - d );
		VectorMA( color, d, contributions[i].color, color );
	}

	// now do some fudging to keep the ambient from being too low
	VectorMA( color, 0.25, directedColor, color );

	//
	// save the resulting value out
	//
	ColorToBytes( color, gridData + num*8 );
	ColorToBytes( directedColor, gridData + num*8 + 3 );

	VectorNormalize( summedDir, summedDir );
	NormalToLatLong( summedDir, gridData + num*8 + 6);
}


/*
=============
SetupGrid
=============
*/
void SetupGrid( void ) {
	int		i;
	vec3_t	maxs;

	for ( i = 0 ; i < 3 ; i++ ) {
		gridMins[i] = gridSize[i] * ceil( dmodels[0].mins[i] / gridSize[i] );
		maxs[i] = gridSize[i] * floor( dmodels[0].maxs[i] / gridSize[i] );
		gridBounds[i] = (maxs[i] - gridMins[i])/gridSize[i] + 1;
	}

	numGridPoints = gridBounds[0] * gridBounds[1] * gridBounds[2];
	if (numGridPoints * 8 >= MAX_MAP_LIGHTGRID)
		Error("MAX_MAP_LIGHTGRID");
	qprintf( "%5i gridPoints\n", numGridPoints );
}

//=============================================================================

/*
=============
RemoveLightsInSolid
=============
*/
void RemoveLightsInSolid(void)
{
	light_t *light, *prev;
	int numsolid = 0;

	prev = NULL;
	for ( light = lights ; light ;  ) {
		if (PointInSolid(light->origin))
		{
			if (prev) prev->next = light->next;
			else lights = light->next;
			if (light->w)
				FreeWinding(light->w);
			free(light);
			numsolid++;
			if (prev)
				light = prev->next;
			else
				light = lights;
		}
		else
		{
			prev = light;
			light = light->next;
		}
	}
	_printf (" %7i lights in solid\n", numsolid);
}

/*
=============
LightWorld
=============
*/
void LightWorld (void) {
	float		f;

	// determine the number of grid points
	SetupGrid();

	// find the optional world ambient
	GetVectorForKey( &entities[0], "_color", ambientColor );
	f = FloatForKey( &entities[0], "ambient" );
	VectorScale( ambientColor, f, ambientColor );

	// create lights out of patches and lights
	qprintf ("--- CreateLights ---\n");
	CreateEntityLights ();
	qprintf ("%i point lights\n", numPointLights);
	qprintf ("%i area lights\n", numAreaLights);

	if (!nogridlighting) {
		qprintf ("--- TraceGrid ---\n");
		RunThreadsOnIndividual( numGridPoints, qtrue, TraceGrid );
		qprintf( "%i x %i x %i = %i grid\n", gridBounds[0], gridBounds[1],
			gridBounds[2], numGridPoints);
	}

	qprintf ("--- TraceLtm ---\n");
	RunThreadsOnIndividual( numDrawSurfaces, qtrue, TraceLtm );
	qprintf( "%5i visible samples\n", c_visible );
	qprintf( "%5i occluded samples\n", c_occluded );
}

/*
========
CreateFilters

EXPERIMENTAL, UNUSED

Look for transparent light filter surfaces.

This will only work for flat 3*3 patches that exactly hold one copy of the texture.
========
*/
#define	PLANAR_PATCH_EPSILON	0.1
void CreateFilters( void ) {
	int				i;
	filter_t		*f;
	dsurface_t		*ds;
	shaderInfo_t	*si;
	drawVert_t		*v1, *v2, *v3;
	vec3_t			d1, d2;
	int				vertNum;

	numFilters = 0;

	return;

	for ( i = 0 ; i < numDrawSurfaces ; i++ ) {
		ds = &drawSurfaces[i];
		if ( !ds->patchWidth ) {
			continue;
		}
		si = ShaderInfoForShader( dshaders[ ds->shaderNum ].shader );
/*
		if ( !(si->surfaceFlags & SURF_LIGHTFILTER) ) {
			continue;
		}
*/

		// we have a filter patch
		v1 = &drawVerts[ ds->firstVert ];

		if ( ds->patchWidth != 3 || ds->patchHeight != 3 ) {
			_printf("WARNING: patch at %i %i %i has SURF_LIGHTFILTER but isn't a 3 by 3\n",
				v1->xyz[0], v1->xyz[1], v1->xyz[2] );
			continue;
		}

		if ( numFilters == MAX_FILTERS ) {
			Error( "MAX_FILTERS" );
		}
		f = &filters[ numFilters ];
		numFilters++;

		v2 = &drawVerts[ ds->firstVert + 2 ];
		v3 = &drawVerts[ ds->firstVert + 6 ];

		VectorSubtract( v2->xyz, v1->xyz, d1 );
		VectorSubtract( v3->xyz, v1->xyz, d2 );
		VectorNormalize( d1, d1 );
		VectorNormalize( d2, d2 );
		CrossProduct( d1, d2, f->plane );
		f->plane[3] = DotProduct( v1->xyz, f->plane );

		// make sure all the control points are on the plane
		for ( vertNum = 0 ; vertNum < ds->numVerts ; vertNum++ ) {
			float	d;

			d = DotProduct( drawVerts[ ds->firstVert + vertNum ].xyz, f->plane ) - f->plane[3];
			if ( fabs( d ) > PLANAR_PATCH_EPSILON ) {
				break;
			}
		}
		if ( vertNum != ds->numVerts ) {
			numFilters--;
			_printf("WARNING: patch at %i %i %i has SURF_LIGHTFILTER but isn't flat\n",
				v1->xyz[0], v1->xyz[1], v1->xyz[2] );
			continue;
		}
	}

	f = &filters[0];
	numFilters = 1;

	f->plane[0] = 1;
	f->plane[1] = 0;
	f->plane[2] = 0;
	f->plane[3] = 448;

	f->origin[0] = 448;
	f->origin[1] = 192;
	f->origin[2] = 0;

	f->vectors[0][0] = 0;
	f->vectors[0][1] = -1.0 / 128;
	f->vectors[0][2] = 0;

	f->vectors[1][0] = 0;
	f->vectors[1][1] = 0;
	f->vectors[1][2] = 1.0 / 128;

	f->si = ShaderInfoForShader( "textures/hell/blocks11ct" );
}

/*
=============
VertexLightingThread
=============
*/
void VertexLightingThread(int num) {
	dsurface_t	*ds;
	traceWork_t	tw;
	shaderInfo_t *si;

	ds = &drawSurfaces[num];

	// vertex-lit triangle model
	if ( ds->surfaceType == MST_TRIANGLE_SOUP ) {
		return;
	}

	if (novertexlighting)
		return;

	if ( ds->lightmapNum == -1 ) {
		return;	// doesn't need lighting at all
	}

	si = ShaderInfoForShader( dshaders[ ds->shaderNum].shader );

	// calculate the vertex lighting for gouraud shade mode
	VertexLighting( ds, si->vertexShadows, si->forceSunLight, si->vertexScale, &tw );
}

/*
=============
TriSoupLightingThread
=============
*/
void TriSoupLightingThread(int num) {
	dsurface_t	*ds;
	traceWork_t	tw;
	shaderInfo_t *si;

	ds = &drawSurfaces[num];
	si = ShaderInfoForShader( dshaders[ ds->shaderNum].shader );

	// vertex-lit triangle model
	if ( ds->surfaceType == MST_TRIANGLE_SOUP ) {
		VertexLighting( ds, !si->noVertexShadows, si->forceSunLight, 1.0, &tw );
	}
}

/*
=============
GridAndVertexLighting
=============
*/
void GridAndVertexLighting(void) {
	SetupGrid();

	FindSkyBrushes();
	CreateFilters();
	InitTrace();
	CreateEntityLights ();
	CreateSurfaceLights();

	if (!nogridlighting) {
		_printf ("--- TraceGrid ---\n");
		RunThreadsOnIndividual( numGridPoints, qtrue, TraceGrid );
	}

	if (!novertexlighting) {
		_printf ("--- Vertex Lighting ---\n");
		RunThreadsOnIndividual( numDrawSurfaces, qtrue, VertexLightingThread );
	}

	_printf("--- Model Lighting ---\n");
	RunThreadsOnIndividual( numDrawSurfaces, qtrue, TriSoupLightingThread );
}

/*
========
LightMain

========
*/
int LightMain (int argc, char **argv) {
	int			i;
	double		start, end;
	const char	*value;

	_printf ("----- Lighting ----\n");

	verbose = qfalse;

	for (i=1 ; i<argc ; i++) {
		if (!strcmp(argv[i],"-tempname"))
    {
      i++;
    } else if (!strcmp(argv[i],"-v")) {
			verbose = qtrue;
		} else if (!strcmp(argv[i],"-threads")) {
			numthreads = atoi (argv[i+1]);
			i++;
		} else if (!strcmp(argv[i],"-area")) {
			areaScale *= atof(argv[i+1]);
			_printf ("area light scaling at %f\n", areaScale);
			i++;
		} else if (!strcmp(argv[i],"-point")) {
			pointScale *= atof(argv[i+1]);
			_printf ("point light scaling at %f\n", pointScale);
			i++;
		} else if (!strcmp(argv[i],"-notrace")) {
			notrace = qtrue;
			_printf ("No occlusion tracing\n");
		} else if (!strcmp(argv[i],"-patchshadows")) {
			patchshadows = qtrue;
			_printf ("Patch shadow casting enabled\n");
		} else if (!strcmp(argv[i],"-extra")) {
			extra = qtrue;
			_printf ("Extra detail tracing\n");
		} else if (!strcmp(argv[i],"-extrawide")) {
			extra = qtrue;
			extraWide = qtrue;
			_printf ("Extra wide detail tracing\n");
		} else if (!strcmp(argv[i], "-samplesize")) {
			samplesize = atoi(argv[i+1]);
			if (samplesize < 1) samplesize = 1;
			i++;
			_printf("lightmap sample size is %dx%d units\n", samplesize, samplesize);
		} else if (!strcmp(argv[i], "-novertex")) {
			novertexlighting = qtrue;
			_printf("no vertex lighting = true\n");
		} else if (!strcmp(argv[i], "-nogrid")) {
			nogridlighting = qtrue;
			_printf("no grid lighting = true\n");
		} else if (!strcmp(argv[i],"-border")) {
			lightmapBorder = qtrue;
			_printf ("Adding debug border to lightmaps\n");
		} else if (!strcmp(argv[i],"-nosurf")) {
			noSurfaces = qtrue;
			_printf ("Not tracing against surfaces\n" );
		} else if (!strcmp(argv[i],"-dump")) {
			dump = qtrue;
			_printf ("Dumping occlusion maps\n");
		} else {
			break;
		}
	}

	ThreadSetDefault ();

	if (i != argc - 1) {
		_printf("usage: q3map -light [-<switch> [-<switch> ...]] <mapname>\n"
				"\n"
				"Switches:\n"
				"   v              = verbose output\n"
				"   threads <X>    = set number of threads to X\n"
				"   area <V>       = set the area light scale to V\n"
				"   point <W>      = set the point light scale to W\n"
				"   notrace        = don't cast any shadows\n"
				"   extra          = enable super sampling for anti-aliasing\n"
				"   extrawide      = same as extra but smoothen more\n"
				"   nogrid         = don't calculate light grid for dynamic model lighting\n"
				"   novertex       = don't calculate vertex lighting\n"
				"   samplesize <N> = set the lightmap pixel size to NxN units\n");
		exit(0);
	}

	start = I_FloatTime ();

	SetQdirFromPath (argv[i]);	

#ifdef _WIN32
	InitPakFile(gamedir, NULL);
#endif

	strcpy (source, ExpandArg(argv[i]));
	StripExtension (source);
	DefaultExtension (source, ".bsp");

	LoadShaderInfo();

	_printf ("reading %s\n", source);

	LoadBSPFile (source);

	FindSkyBrushes();

	ParseEntities();

	value = ValueForKey( &entities[0], "gridsize" );
	if (strlen(value)) {
		sscanf( value, "%f %f %f", &gridSize[0], &gridSize[1], &gridSize[2] );
		_printf("grid size = {%1.1f, %1.1f, %1.1f}\n", gridSize[0], gridSize[1], gridSize[2]);
	}

	CreateFilters();

	InitTrace();

	SetEntityOrigins();

	CountLightmaps();

	CreateSurfaceLights();

	LightWorld();

	_printf ("writing %s\n", source);
	WriteBSPFile (source);

	end = I_FloatTime ();
	_printf ("%5.0f seconds elapsed\n", end-start);
	
	return 0;
}