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 ) {