light.c

Go to the documentation of this file.

/*
===========================================================================
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;
}

---