lightv.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
===========================================================================
*/


#include "cmdlib.h"
#include "mathlib.h"
#include "bspfile.h"
#include "imagelib.h"
#include "threads.h"
#include "mutex.h"
#include "scriplib.h"

#include "shaders.h"
#include "mesh.h"

#ifdef _WIN32
//Improve floating-point consistency.
#pragma optimize( "p", on )
#endif

#ifdef _WIN32
#include "../libs/pakstuff.h"
#endif

#define MAX_CLUSTERS        16384
#define MAX_PORTALS         32768
#define MAX_FACETS          65536
#define MAX_LIGHTS          16384

#define LIGHTMAP_SIZE       128

#define LIGHTMAP_PIXELSHIFT     0.5

//#define LIGHTMAP_PATCHSHIFT

#define PORTALFILE  "PRT1"

#define ON_EPSILON  0.1

#define VectorSet(v, x, y, z)       v[0] = x;v[1] = y;v[2] = z;

typedef struct
{
    vec3_t      normal;
    float       dist;
} plane_t;

#define MAX_POINTS_ON_WINDING   64
//NOTE: whenever this is overflowed parts of lightmaps might end up not being lit
#define MAX_POINTS_ON_FIXED_WINDING 48

typedef struct
{
    int     numpoints;
    vec3_t  points[MAX_POINTS_ON_FIXED_WINDING];            // variable sized
} winding_t;

typedef struct
{
    plane_t     plane;  // normal pointing into neighbor
    int         leaf;   // neighbor
    winding_t   *winding;
    vec3_t      origin; // for fast clip testing
    float       radius;
} lportal_t;

#define MAX_PORTALS_ON_LEAF     128
typedef struct lleaf_s
{
    int         numportals;
    lportal_t   *portals[MAX_PORTALS_ON_LEAF];
    //
    int         numSurfaces;
    int         firstSurface;
} lleaf_t;

typedef struct lFacet_s
{
    int     num;
    plane_t plane;
    vec3_t  points[4];              //
    int     numpoints;
    float   lightmapCoords[4][2];
    plane_t boundaries[4];          // negative is outside the bounds
    float   textureMatrix[2][4];    // texture coordinates for translucency
    float   lightmapMatrix[2][4];   // lightmap texture coordinates
    vec3_t  mins;
    int     x, y, width, height;
} lFacet_t;

typedef struct lsurfaceTest_s
{
    vec3_t          mins, maxs;
    vec3_t          origin;
    float           radius;
    qboolean        patch;          // true if this is a patch
    qboolean        trisoup;        // true if this is a triangle soup
    int             numFacets;
    lFacet_t        *facets;
    mesh_t          *detailMesh;    // detailed mesh with points for each lmp
    shaderInfo_t    *shader;        // for translucency
    mutex_t         *mutex;
    int             numvolumes;     // number of volumes casted at this surface
    //
    int             always_tracelight;
    int             always_vlight;
} lsurfaceTest_t;

//volume types
#define VOLUME_NORMAL           0
#define VOLUME_DIRECTED         1

#define MAX_TRANSLUCENTFACETS   32

typedef struct lightvolume_s
{
    int num;
    int cluster;                            //cluster this light volume started in
    plane_t endplane;                       //end plane
    plane_t farplane;                       //original end plane
    vec3_t points[MAX_POINTS_ON_WINDING];   //end winding points
    plane_t planes[MAX_POINTS_ON_WINDING];  //volume bounding planes
    int numplanes;                          //number of volume bounding planes
    int type;                               //light volume type
    //list with translucent surfaces the volume went through
    int transFacets[MAX_TRANSLUCENTFACETS];
    int transSurfaces[MAX_TRANSLUCENTFACETS];
    int numtransFacets;
    //clusters already tested
    byte clusterTested[MAX_CLUSTERS/8];
    //facets already tested
    byte facetTested[MAX_FACETS/8];
    int facetNum;           //number of the facet blocking the light in this volume
    int surfaceNum;         //number of the surface blocking the light in this volume
} lightvolume_t;

//light types
#define LIGHT_POINTRADIAL           1
#define LIGHT_POINTSPOT             2
#define LIGHT_POINTFAKESURFACE      3
#define LIGHT_SURFACEDIRECTED       4
#define LIGHT_SURFACERADIAL         5
#define LIGHT_SURFACESPOT           6

//light distance attenuation types
#define LDAT_QUADRATIC              0
#define LDAT_LINEAR                 1
#define LDAT_NOSCALE                2

//light angle attenuation types
#define LAAT_NORMAL                 0
#define LAAT_QUADRATIC              1
#define LAAT_DOUBLEQUADRATIC        2

typedef struct vlight_s
{
    vec3_t origin;              //light origin, for point lights
    winding_t w;                //light winding, for area lights
    vec4_t plane;               //light winding plane
    vec3_t normal;              //direction of the light
    int type;                   //light type
    vec3_t color;               //light color
    qboolean twosided;          //radiates light at both sides of the winding
    int style;                  //light style (not used)
    int atten_disttype;         //light distance attenuation type
    int atten_angletype;        //light angle attenuation type
    float atten_distscale;      //distance attenuation scale
    float atten_anglescale;     //angle attenuation scale
    float radiusByDist;         //radius by distance for spot lights
    float photons;              //emitted photons
    float intensity;            //intensity
    vec3_t emitColor;           //full out-of-gamut value (not used)
    struct shaderInfo_s *si;    //shader info
    int insolid;                //set when light is in solid
} vlight_t;

float   lightLinearScale            = 1.0 / 8000;
float   lightPointScale             = 7500;
float   lightAreaScale              = 0.25;
float   lightFormFactorValueScale   = 3;
int     lightDefaultSubdivide       = 999;      // vary by surface size?
vec3_t  lightAmbientColor;

int         portalclusters, numportals, numfaces;
lleaf_t     *leafs;
lportal_t   *portals;
int         numvlights = 0;
vlight_t    *vlights[MAX_LIGHTS];
int         nostitching = 0;
int         noalphashading = 0;
int         nocolorshading = 0;
int         nobackfaceculling = 0;
int         defaulttracelight = 0;
int         radiosity = 0;
int         radiosity_scale;

int             clustersurfaces[MAX_MAP_LEAFFACES];
int             numclustersurfaces = 0;
lsurfaceTest_t  *lsurfaceTest[MAX_MAP_DRAW_SURFS];
int             numfacets;
float           lightmappixelarea[MAX_MAP_LIGHTING/3];
float           *lightFloats;//[MAX_MAP_LIGHTING];

// from polylib.c
winding_t   *AllocWinding (int points);
void        FreeWinding (winding_t *w);
void        WindingCenter (winding_t *w, vec3_t center);
void        WindingBounds (winding_t *w, vec3_t mins, vec3_t maxs);
vec_t       WindingArea (winding_t *w);
winding_t   *BaseWindingForPlane (vec3_t normal, vec_t dist);
void        ClipWindingEpsilon (winding_t *in, vec3_t normal, vec_t dist, 
                vec_t epsilon, winding_t **front, winding_t **back);
winding_t   *ReverseWinding (winding_t *w);

// from light.c
extern char     source[1024];
extern vec3_t   surfaceOrigin[ MAX_MAP_DRAW_SURFS ];
extern int      entitySurface[ MAX_MAP_DRAW_SURFS ];
extern int      samplesize;
extern int      novertexlighting;
extern int      nogridlighting;
extern qboolean patchshadows;
extern vec3_t   gridSize;

float PointToPolygonFormFactor( const vec3_t point, const vec3_t normal, const winding_t *w );
void ColorToBytes( const float *color, byte *colorBytes );
void CountLightmaps( void );
void GridAndVertexLighting( void );
void SetEntityOrigins( void );


//#define DEBUGNET

#ifdef DEBUGNET

#include "l_net.h"

socket_t *debug_socket;

/*
=====================
DebugNet_Setup
=====================
*/
void DebugNet_Setup(void)
{
    address_t address;
    int i;

    Net_Setup();
    Net_StringToAddress("127.0.0.1:28000", &address);
    for (i = 0; i < 10; i++)
    {
        debug_socket = Net_Connect(&address, 28005 + i);
        if (debug_socket)
            break;
    }
}

/*
=====================
DebugNet_Shutdown
=====================
*/
void DebugNet_Shutdown(void)
{
    netmessage_t msg;

    if (debug_socket)
    {
        NMSG_Clear(&msg);
        NMSG_WriteByte(&msg, 1);
        Net_Send(debug_socket, &msg);
        Net_Disconnect(debug_socket);
    }
    debug_socket = NULL;
    Net_Shutdown();
}

/*
=====================
DebugNet_RemoveAllPolys
=====================
*/
void DebugNet_RemoveAllPolys(void)
{
    netmessage_t msg;

    if (!debug_socket)
        return;
    NMSG_Clear(&msg);
    NMSG_WriteByte(&msg, 2);        //remove all debug polys
    Net_Send(debug_socket, &msg);
}

/*
====================
DebugNet_DrawWinding
=====================
*/
void DebugNet_DrawWinding(winding_t *w, int color)
{
    netmessage_t msg;
    int i;

    if (!debug_socket)
        return;
    NMSG_Clear(&msg);
    NMSG_WriteByte(&msg, 0);                //draw a winding
    NMSG_WriteByte(&msg, w->numpoints);     //number of points
    NMSG_WriteLong(&msg, color);            //color
    for (i = 0; i < w->numpoints; i++)
    {
        NMSG_WriteFloat(&msg, w->points[i][0]);
        NMSG_WriteFloat(&msg, w->points[i][1]);
        NMSG_WriteFloat(&msg, w->points[i][2]);
    }
    Net_Send(debug_socket, &msg);
}

/*
=====================
DebugNet_DrawLine
=====================
*/
void DebugNet_DrawLine(vec3_t p1, vec3_t p2, int color)
{
    netmessage_t msg;

    if (!debug_socket)
        return;
    NMSG_Clear(&msg);
    NMSG_WriteByte(&msg, 1);                //draw a line
    NMSG_WriteLong(&msg, color);            //color
    NMSG_WriteFloat(&msg, p1[0]);
    NMSG_WriteFloat(&msg, p1[1]);
    NMSG_WriteFloat(&msg, p1[2]);
    NMSG_WriteFloat(&msg, p2[0]);
    NMSG_WriteFloat(&msg, p2[1]);
    NMSG_WriteFloat(&msg, p2[2]);
    Net_Send(debug_socket, &msg);
}

/*
=====================
DebugNet_DrawMesh
=====================
*/
void DebugNet_DrawMesh(mesh_t *mesh)
{
    int i, j;
    float dot;
    drawVert_t  *v1, *v2, *v3, *v4;
    winding_t winding;
    plane_t plane;
    vec3_t d1, d2;

    for ( i = 0 ; i < mesh->width - 1 ; i++ ) {
        for ( j = 0 ; j < mesh->height - 1 ; j++ ) {

            v1 = mesh->verts + j * mesh->width + i;
            v2 = v1 + 1;
            v3 = v1 + mesh->width + 1;
            v4 = v1 + mesh->width;

            VectorSubtract( v4->xyz, v1->xyz, d1 );
            VectorSubtract( v3->xyz, v1->xyz, d2 );
            CrossProduct( d2, d1, plane.normal );
            if ( VectorNormalize( plane.normal, plane.normal ) != 0 )
            {
                plane.dist = DotProduct( v1->xyz, plane.normal );
                dot = DotProduct(plane.normal, v2->xyz) - plane.dist;
                if (fabs(dot) < 0.1)
                {
                    VectorCopy(v1->xyz, winding.points[0]);
                    VectorCopy(v4->xyz, winding.points[1]);
                    VectorCopy(v3->xyz, winding.points[2]);
                    VectorCopy(v2->xyz, winding.points[3]);
                    winding.numpoints = 4;
                    DebugNet_DrawWinding(&winding, 2);
                    continue;
                }
            }

            winding.numpoints = 3;
            VectorCopy(v1->xyz, winding.points[0]);
            VectorCopy(v4->xyz, winding.points[1]);
            VectorCopy(v3->xyz, winding.points[2]);
            DebugNet_DrawWinding(&winding, 2);

            VectorCopy(v1->xyz, winding.points[0]);
            VectorCopy(v3->xyz, winding.points[1]);
            VectorCopy(v2->xyz, winding.points[2]);
            DebugNet_DrawWinding(&winding, 2);
        }
    }
}

/*
=====================
VL_DrawLightVolume
=====================
*/
int VL_ChopWinding (winding_t *in, plane_t *split, float epsilon);

void VL_DrawLightVolume(vlight_t *light, lightvolume_t *volume)
{
    winding_t w;
    int i;
    vec3_t p2, invlight;

    memcpy(w.points, volume->points, volume->numplanes * sizeof(vec3_t));
    w.numpoints = volume->numplanes;
    DebugNet_DrawWinding(&w, 2);

    if (volume->type == VOLUME_DIRECTED)
    {
        VectorCopy(light->normal, invlight);
        VectorInverse(invlight);
        for (i = 0; i < volume->numplanes; i++)
        {
            VectorCopy(volume->points[i], w.points[0]);
            VectorCopy(volume->points[(i+1) % volume->numplanes], w.points[1]);
            VectorMA(w.points[1], MAX_WORLD_COORD, invlight, w.points[2]);
            VectorMA(w.points[0], MAX_WORLD_COORD, invlight, w.points[3]);
            w.numpoints = 4;
            DebugNet_DrawWinding(&w, 2);
            VectorMA(volume->points[i], 8, volume->planes[i].normal, p2);
            DebugNet_DrawLine(volume->points[i], p2, 3);
        }
    }
    else
    {
        //
        VectorCopy(light->origin, w.points[0]);
        w.numpoints = 3;
        for (i = 0; i < volume->numplanes; i++)
        {
            VectorCopy(volume->points[i], w.points[1]);
            VectorCopy(volume->points[(i+1) % volume->numplanes], w.points[2]);
            VL_ChopWinding(&w, &volume->endplane, 0);
            DebugNet_DrawWinding(&w, 2);
            VectorMA(volume->points[i], 8, volume->planes[i].normal, p2);
            DebugNet_DrawLine(volume->points[i], p2, 3);
        }
    }
}

/*
=============
VL_DrawLightmapPixel
=============
*/
void VL_DrawLightmapPixel(int surfaceNum, int x, int y, int color)
{
    winding_t w;
    dsurface_t *ds;
    mesh_t *mesh;

    ds = &drawSurfaces[surfaceNum];

    if (ds->surfaceType == MST_PATCH)
    {
        mesh = lsurfaceTest[surfaceNum]->detailMesh;
        VectorCopy( mesh->verts[(y-ds->lightmapY)*mesh->width+x-ds->lightmapX].xyz, w.points[0]);
        VectorCopy( mesh->verts[(y+1-ds->lightmapY)*mesh->width+x-ds->lightmapX].xyz, w.points[1]);
        VectorCopy( mesh->verts[(y+1-ds->lightmapY)*mesh->width+x+1-ds->lightmapX].xyz, w.points[2]);
        VectorCopy( mesh->verts[(y-ds->lightmapY)*mesh->width+x+1-ds->lightmapX].xyz, w.points[3]);
        w.numpoints = 4;
    }
    else
    {
        VectorMA(ds->lightmapOrigin, (float) x - LIGHTMAP_PIXELSHIFT - ds->lightmapX, ds->lightmapVecs[0], w.points[0]);
        VectorMA(w.points[0], (float) y - LIGHTMAP_PIXELSHIFT - ds->lightmapY, ds->lightmapVecs[1], w.points[0]);
        VectorMA(ds->lightmapOrigin, (float) x - LIGHTMAP_PIXELSHIFT - ds->lightmapX, ds->lightmapVecs[0], w.points[1]);
        VectorMA(w.points[1], (float) y - LIGHTMAP_PIXELSHIFT + 1 - ds->lightmapY, ds->lightmapVecs[1], w.points[1]);
        VectorMA(ds->lightmapOrigin, (float) x - LIGHTMAP_PIXELSHIFT + 1 - ds->lightmapX, ds->lightmapVecs[0], w.points[2]);
        VectorMA(w.points[2], (float) y - LIGHTMAP_PIXELSHIFT + 1 - ds->lightmapY, ds->lightmapVecs[1], w.points[2]);
        VectorMA(ds->lightmapOrigin, (float) x - LIGHTMAP_PIXELSHIFT + 1 - ds->lightmapX, ds->lightmapVecs[0], w.points[3]);
        VectorMA(w.points[3], (float) y - LIGHTMAP_PIXELSHIFT - ds->lightmapY, ds->lightmapVecs[1], w.points[3]);
        w.numpoints = 4;
    }
    DebugNet_DrawWinding(&w, color);
}

/*
============
VL_DrawPortals
============
*/
void VL_DrawPortals(void)
{
    int j;
    lportal_t *p;

    for (j = 0; j < numportals * 2; j++)
    {
        p = portals + j;
        DebugNet_DrawWinding(p->winding, 1);
    }
}

/*
============
VL_DrawLeaf
============
*/
void VL_DrawLeaf(int cluster)
{
    int i;
    lleaf_t *leaf;
    lportal_t *p;

    leaf = &leafs[cluster];
    for (i = 0; i < leaf->numportals; i++)
    {
        p = leaf->portals[i];
        DebugNet_DrawWinding(p->winding, 1);
    }
}

#endif //DEBUGNET

/*
=============
VL_SplitWinding
=============
*/
int VL_SplitWinding (winding_t *in, winding_t *back, plane_t *split, float epsilon)
{
    vec_t   dists[128];
    int     sides[128];
    int     counts[3];
    vec_t   dot;
    int     i, j;
    vec_t   *p1, *p2;
    vec3_t  mid;
    winding_t out;
    winding_t   *neww;

    counts[0] = counts[1] = counts[2] = 0;

    // determine sides for each point
    for (i=0 ; i<in->numpoints ; i++)
    {
        dot = DotProduct (in->points[i], split->normal);
        dot -= split->dist;
        dists[i] = dot;
        if (dot > epsilon)
            sides[i] = SIDE_FRONT;
        else if (dot < -epsilon)
            sides[i] = SIDE_BACK;
        else
        {
            sides[i] = SIDE_ON;
        }
        counts[sides[i]]++;
    }

    if (!counts[SIDE_BACK])
    {
        if (!counts[SIDE_FRONT])
            return SIDE_ON;
        else
            return SIDE_FRONT;
    }
    
    if (!counts[SIDE_FRONT])
    {
        return SIDE_BACK;
    }

    sides[i] = sides[0];
    dists[i] = dists[0];
    
    neww = &out;

    neww->numpoints = 0;
    back->numpoints = 0;

    for (i=0 ; i<in->numpoints ; i++)
    {
        p1 = in->points[i];

        if (neww->numpoints >= MAX_POINTS_ON_FIXED_WINDING)
        {
            _printf("WARNING: VL_SplitWinding -> MAX_POINTS_ON_FIXED_WINDING overflowed\n");
            return SIDE_FRONT;      // can't chop -- fall back to original
        }
        if (back->numpoints >= MAX_POINTS_ON_FIXED_WINDING)
        {
            _printf("WARNING: VL_SplitWinding -> MAX_POINTS_ON_FIXED_WINDING overflowed\n");
            return SIDE_FRONT;
        }

        if (sides[i] == SIDE_ON)
        {
            VectorCopy (p1, neww->points[neww->numpoints]);
            neww->numpoints++;
            VectorCopy (p1, back->points[back->numpoints]);
            back->numpoints++;
            continue;
        }
    
        if (sides[i] == SIDE_FRONT)
        {
            VectorCopy (p1, neww->points[neww->numpoints]);
            neww->numpoints++;
        }
        if (sides[i] == SIDE_BACK)
        {
            VectorCopy (p1, back->points[back->numpoints]);
            back->numpoints++;
        }
        
        if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
            continue;
            
        if (neww->numpoints >= MAX_POINTS_ON_FIXED_WINDING)
        {
            _printf("WARNING: VL_SplitWinding -> MAX_POINTS_ON_FIXED_WINDING overflowed\n");
            return SIDE_FRONT;      // can't chop -- fall back to original
        }

        if (back->numpoints >= MAX_POINTS_ON_FIXED_WINDING)
        {
            _printf("WARNING: VL_SplitWinding -> MAX_POINTS_ON_FIXED_WINDING overflowed\n");
            return SIDE_FRONT;      // can't chop -- fall back to original
        }

        // generate a split point
        p2 = in->points[(i+1)%in->numpoints];
        
        dot = dists[i] / (dists[i]-dists[i+1]);
        for (j=0 ; j<3 ; j++)
        {   // avoid round off error when possible
            if (split->normal[j] == 1)
                mid[j] = split->dist;
            else if (split->normal[j] == -1)
                mid[j] = -split->dist;
            else
                mid[j] = p1[j] + dot*(p2[j]-p1[j]);
        }
            
        VectorCopy (mid, neww->points[neww->numpoints]);
        neww->numpoints++;
        VectorCopy (mid, back->points[back->numpoints]);
        back->numpoints++;
    }
    memcpy(in, &out, sizeof(winding_t));
    
    return SIDE_CROSS;
}

/*
=====================
VL_LinkSurfaceIntoCluster
=====================
*/
void VL_LinkSurfaceIntoCluster(int cluster, int surfaceNum)
{
    lleaf_t *leaf;
    int i;

    leaf = &leafs[cluster];

    for (i = 0; i < leaf->numSurfaces; i++)
    {
        if (clustersurfaces[leaf->firstSurface + i] == surfaceNum)
            return;
    }
    for (i = numclustersurfaces; i > leaf->firstSurface + leaf->numSurfaces; i--)
        clustersurfaces[i] = clustersurfaces[i-1];
    for (i = 0; i < portalclusters; i++)
    {
        if (i == cluster)
            continue;
        if (leafs[i].firstSurface >= leaf->firstSurface + leaf->numSurfaces)
            leafs[i].firstSurface++;
    }
    clustersurfaces[leaf->firstSurface + leaf->numSurfaces] = surfaceNum;
    leaf->numSurfaces++;
    numclustersurfaces++;
    if (numclustersurfaces >= MAX_MAP_LEAFFACES)
        Error("MAX_MAP_LEAFFACES");
}

/*
=====================
VL_R_LinkSurface
=====================
*/
void VL_R_LinkSurface(int nodenum, int surfaceNum, winding_t *w)
{
    int leafnum, cluster, res;
    dnode_t *node;
    dplane_t *plane;
    winding_t back;
    plane_t split;

    while(nodenum >= 0)
    {
        node = &dnodes[nodenum];
        plane = &dplanes[node->planeNum];

        VectorCopy(plane->normal, split.normal);
        split.dist = plane->dist;
        res = VL_SplitWinding (w, &back, &split, 0.1);

        if (res == SIDE_FRONT)
        {
            nodenum = node->children[0];
        }
        else if (res == SIDE_BACK)
        {
            nodenum = node->children[1];
        }
        else if (res == SIDE_ON)
        {
            memcpy(&back, w, sizeof(winding_t));
            VL_R_LinkSurface(node->children[1], surfaceNum, &back);
            nodenum = node->children[0];
        }
        else
        {
            VL_R_LinkSurface(node->children[1], surfaceNum, &back);
            nodenum = node->children[0];
        }
    }
    leafnum = -nodenum - 1;
    cluster = dleafs[leafnum].cluster;
    if (cluster != -1)
    {
        VL_LinkSurfaceIntoCluster(cluster, surfaceNum);
    }
}

/*
=====================
VL_LinkSurfaces

maybe link each facet seperately instead of the test surfaces?
=====================
*/
void VL_LinkSurfaces(void)
{
    int i, j;
    lsurfaceTest_t *test;
    lFacet_t *facet;
    winding_t winding;

    for ( i = 0 ; i < numDrawSurfaces ; i++ )
    {
        test = lsurfaceTest[ i ];
        if (!test)
            continue;
        for (j = 0; j < test->numFacets; j++)
        {
            facet = &test->facets[j];
            memcpy(winding.points, facet->points, facet->numpoints * sizeof(vec3_t));
            winding.numpoints = facet->numpoints;
            VL_R_LinkSurface(0, i, &winding);
        }
    }
}

/*
=====================
VL_TextureMatrixFromPoints
=====================
*/
void VL_TextureMatrixFromPoints( lFacet_t *f, drawVert_t *a, drawVert_t *b, drawVert_t *c ) {
    int         i, j;
    float       t;
    float       m[3][4];
    float       s;

    // This is an incredibly stupid way of solving a three variable equation
    for ( i = 0 ; i < 2 ; i++ ) {

        m[0][0] = a->xyz[0];
        m[0][1] = a->xyz[1];
        m[0][2] = a->xyz[2];
        m[0][3] = a->st[i];

        m[1][0] = b->xyz[0];
        m[1][1] = b->xyz[1];
        m[1][2] = b->xyz[2];
        m[1][3] = b->st[i];

        m[2][0] = c->xyz[0];
        m[2][1] = c->xyz[1];
        m[2][2] = c->xyz[2];
        m[2][3] = c->st[i];

        if ( fabs(m[1][0]) > fabs(m[0][0]) && fabs(m[1][0]) > fabs(m[2][0]) ) {
            for ( j = 0 ; j < 4 ; j ++ ) {
                t = m[0][j];
                m[0][j] = m[1][j];
                m[1][j] = t;
            }
        } else if ( fabs(m[2][0]) > fabs(m[0][0]) && fabs(m[2][0]) > fabs(m[1][0]) ) {
            for ( j = 0 ; j < 4 ; j ++ ) {
                t = m[0][j];
                m[0][j] = m[2][j];
                m[2][j] = t;
            }
        }

        s = 1.0 / m[0][0];
        m[0][0] *= s;
        m[0][1] *= s;
        m[0][2] *= s;
        m[0][3] *= s;

        s = m[1][0];
        m[1][0] -= m[0][0] * s;
        m[1][1] -= m[0][1] * s;
        m[1][2] -= m[0][2] * s;
        m[1][3] -= m[0][3] * s;

        s = m[2][0];
        m[2][0] -= m[0][0] * s;
        m[2][1] -= m[0][1] * s;
        m[2][2] -= m[0][2] * s;
        m[2][3] -= m[0][3] * s;

        if ( fabs(m[2][1]) > fabs(m[1][1]) ) {
            for ( j = 0 ; j < 4 ; j ++ ) {
                t = m[1][j];
                m[1][j] = m[2][j];
                m[2][j] = t;
            }
        }

        s = 1.0 / m[1][1];
        m[1][0] *= s;
        m[1][1] *= s;
        m[1][2] *= s;
        m[1][3] *= s;

        s = m[2][1];// / m[1][1];
        m[2][0] -= m[1][0] * s;
        m[2][1] -= m[1][1] * s;
        m[2][2] -= m[1][2] * s;
        m[2][3] -= m[1][3] * s;

        s = 1.0 / m[2][2];
        m[2][0] *= s;
        m[2][1] *= s;
        m[2][2] *= s;
        m[2][3] *= s;

        f->textureMatrix[i][2] = m[2][3];
        f->textureMatrix[i][1] = m[1][3] - f->textureMatrix[i][2] * m[1][2];
        f->textureMatrix[i][0] = m[0][3] - f->textureMatrix[i][2] * m[0][2] - f->textureMatrix[i][1] * m[0][1];

        f->textureMatrix[i][3] = 0;
/*
        s = fabs( DotProduct( a->xyz, f->textureMatrix[i] ) - a->st[i] );
        if ( s > 0.01 ) {
            Error( "Bad textureMatrix" );
        }
        s = fabs( DotProduct( b->xyz, f->textureMatrix[i] ) - b->st[i] );
        if ( s > 0.01 ) {
            Error( "Bad textureMatrix" );
        }
        s = fabs( DotProduct( c->xyz, f->textureMatrix[i] ) - c->st[i] );
        if ( s > 0.01 ) {
            Error( "Bad textureMatrix" );
        }
*/
    }
}

/*
=====================
VL_LightmapMatrixFromPoints
=====================
*/
void VL_LightmapMatrixFromPoints( dsurface_t *dsurf, shaderInfo_t *si, lFacet_t *f, drawVert_t *a, drawVert_t *b, drawVert_t *c ) {
    int         i, j;
    float       t;
    float       m[3][4], al, bl, cl;
    float       s;
    int         h, w, ssize;
    vec3_t      mins, maxs, delta, size, planeNormal;
    drawVert_t  *verts;
    static int  message;

    // vertex-lit triangle model
    if ( dsurf->surfaceType == MST_TRIANGLE_SOUP ) {
        return;
    }
    
    if ( dsurf->lightmapNum < 0 ) {
        return;     // doesn't need lighting
    }

    VectorClear(f->mins);
    if (dsurf->surfaceType != MST_PATCH)
    {
        ssize = samplesize;
        if (si->lightmapSampleSize)
            ssize = si->lightmapSampleSize;
        ClearBounds( mins, maxs );
        verts = &drawVerts[dsurf->firstVert];
        for ( i = 0 ; i < dsurf->numVerts ; i++ ) {
            AddPointToBounds( verts[i].xyz, mins, maxs );
        }
        // round to the lightmap resolution
        for ( i = 0 ; i < 3 ; i++ ) {
            mins[i] = ssize * floor( mins[i] / ssize );
            maxs[i] = ssize * ceil( maxs[i] / ssize );
            f->mins[i] = mins[i];
            size[i] = (maxs[i] - mins[i]) / ssize + 1;
        }
        // the two largest axis will be the lightmap size
        VectorClear(f->lightmapMatrix[0]);
        f->lightmapMatrix[0][3] = 0;
        VectorClear(f->lightmapMatrix[1]);
        f->lightmapMatrix[1][3] = 0;

        planeNormal[0] = fabs( dsurf->lightmapVecs[2][0] );
        planeNormal[1] = fabs( dsurf->lightmapVecs[2][1] );
        planeNormal[2] = fabs( dsurf->lightmapVecs[2][2] );

        if ( planeNormal[0] >= planeNormal[1] && planeNormal[0] >= planeNormal[2] ) {
            w = size[1];
            h = size[2];
            f->lightmapMatrix[0][1] = 1.0 / ssize;
            f->lightmapMatrix[1][2] = 1.0 / ssize;
        } else if ( planeNormal[1] >= planeNormal[0] && planeNormal[1] >= planeNormal[2] ) {
            w = size[0];
            h = size[2];
            f->lightmapMatrix[0][0] = 1.0 / ssize;
            f->lightmapMatrix[1][2] = 1.0 / ssize;
        } else {
            w = size[0];
            h = size[1];
            f->lightmapMatrix[0][0] = 1.0 / ssize;
            f->lightmapMatrix[1][1] = 1.0 / ssize;
        }
        if ( w > LIGHTMAP_WIDTH ) {
            VectorScale ( f->lightmapMatrix[0], (float)LIGHTMAP_SIZE/w, f->lightmapMatrix[0] );
        }
        
        if ( h > LIGHTMAP_HEIGHT ) {
            VectorScale ( f->lightmapMatrix[1], (float)LIGHTMAP_SIZE/h, f->lightmapMatrix[1] );
        }
        VectorSubtract(a->xyz, f->mins, delta);
        s = (DotProduct( delta, f->lightmapMatrix[0] ) + dsurf->lightmapX + 0.5) / LIGHTMAP_SIZE;
        if ( fabs(s - a->lightmap[0]) > 0.01 ) {
            _printf( "Bad lightmapMatrix" );
        }
        t = (DotProduct( delta, f->lightmapMatrix[1] ) + dsurf->lightmapY + 0.5) / LIGHTMAP_SIZE;
        if ( fabs(t - a->lightmap[1]) > 0.01 ) {
            _printf( "Bad lightmapMatrix" );
        }
        VectorSubtract(b->xyz, f->mins, delta);
        s = (DotProduct( delta, f->lightmapMatrix[0] ) + dsurf->lightmapX + 0.5) / LIGHTMAP_SIZE;
        if ( fabs(s - b->lightmap[0]) > 0.01 ) {
            _printf( "Bad lightmapMatrix" );
        }
        t = (DotProduct( delta, f->lightmapMatrix[1] ) + dsurf->lightmapY + 0.5) / LIGHTMAP_SIZE;
        if ( fabs(t - b->lightmap[1]) > 0.01 ) {
            _printf( "Bad lightmapMatrix" );
        }
        VectorSubtract(c->xyz, f->mins, delta);
        s = (DotProduct( delta, f->lightmapMatrix[0] ) + dsurf->lightmapX + 0.5) / LIGHTMAP_SIZE;
        if ( fabs(s - c->lightmap[0]) > 0.01 ) {
            _printf( "Bad lightmapMatrix" );
        }
        t = (DotProduct( delta, f->lightmapMatrix[1] ) + dsurf->lightmapY + 0.5) / LIGHTMAP_SIZE;
        if ( fabs(t - c->lightmap[1]) > 0.01 ) {
            _printf( "Bad lightmapMatrix" );
        }
        VectorAdd(f->mins, surfaceOrigin[dsurf - drawSurfaces], f->mins);
        return;
    }
    // This is an incredibly stupid way of solving a three variable equation
    for ( i = 0 ; i < 2 ; i++ ) {

        if (i)
            al = a->lightmap[i] - ((float) dsurf->lightmapY + 0.5) / LIGHTMAP_SIZE;
        else
            al = a->lightmap[i] - ((float) dsurf->lightmapX + 0.5) / LIGHTMAP_SIZE;

        m[0][0] = a->xyz[0] - f->mins[0];
        m[0][1] = a->xyz[1] - f->mins[1];
        m[0][2] = a->xyz[2] - f->mins[2];
        m[0][3] = al;

        if (i)
            bl = b->lightmap[i] - ((float) dsurf->lightmapY + 0.5) / LIGHTMAP_SIZE;
        else
            bl = b->lightmap[i] - ((float) dsurf->lightmapX + 0.5) / LIGHTMAP_SIZE;

        m[1][0] = b->xyz[0] - f->mins[0];
        m[1][1] = b->xyz[1] - f->mins[1];
        m[1][2] = b->xyz[2] - f->mins[2];
        m[1][3] = bl;

        if (i)
            cl = c->lightmap[i] - ((float) dsurf->lightmapY + 0.5) / LIGHTMAP_SIZE;
        else
            cl = c->lightmap[i] - ((float) dsurf->lightmapX + 0.5) / LIGHTMAP_SIZE;

        m[2][0] = c->xyz[0] - f->mins[0];
        m[2][1] = c->xyz[1] - f->mins[1];
        m[2][2] = c->xyz[2] - f->mins[2];
        m[2][3] = cl;

        if ( fabs(m[1][0]) > fabs(m[0][0]) && fabs(m[1][0]) >= fabs(m[2][0]) ) {
            for ( j = 0 ; j < 4 ; j ++ ) {
                t = m[0][j];
                m[0][j] = m[1][j];
                m[1][j] = t;
            }
        } else if ( fabs(m[2][0]) > fabs(m[0][0]) && fabs(m[2][0]) >= fabs(m[1][0]) ) {
            for ( j = 0 ; j < 4 ; j ++ ) {
                t = m[0][j];
                m[0][j] = m[2][j];
                m[2][j] = t;
            }
        }

        if (m[0][0])
        {
            s = 1.0 / m[0][0];
            m[0][0] *= s;
            m[0][1] *= s;
            m[0][2] *= s;
            m[0][3] *= s;

            s = m[1][0];
            m[1][0] -= m[0][0] * s;
            m[1][1] -= m[0][1] * s;
            m[1][2] -= m[0][2] * s;
            m[1][3] -= m[0][3] * s;

            s = m[2][0];
            m[2][0] -= m[0][0] * s;
            m[2][1] -= m[0][1] * s;
            m[2][2] -= m[0][2] * s;
            m[2][3] -= m[0][3] * s;
        }

        if ( fabs(m[2][1]) > fabs(m[1][1]) ) {
            for ( j = 0 ; j < 4 ; j ++ ) {
                t = m[1][j];
                m[1][j] = m[2][j];
                m[2][j] = t;
            }
        }

        if (m[1][1])
        {
            s = 1.0 / m[1][1];
            m[1][0] *= s;
            m[1][1] *= s;
            m[1][2] *= s;
            m[1][3] *= s;

            s = m[2][1];
            m[2][0] -= m[1][0] * s;
            m[2][1] -= m[1][1] * s;
            m[2][2] -= m[1][2] * s;
            m[2][3] -= m[1][3] * s;
        }

        if (m[2][2])
        {
            s = 1.0 / m[2][2];
            m[2][0] *= s;
            m[2][1] *= s;
            m[2][2] *= s;
            m[2][3] *= s;
        }

        f->lightmapMatrix[i][2] = m[2][3];
        f->lightmapMatrix[i][1] = m[1][3] - f->lightmapMatrix[i][2] * m[1][2];
        f->lightmapMatrix[i][0] = m[0][3] - f->lightmapMatrix[i][2] * m[0][2] - f->lightmapMatrix[i][1] * m[0][1];

        f->lightmapMatrix[i][3] = 0;

        VectorSubtract(a->xyz, f->mins, delta);
        s = fabs( DotProduct( delta, f->lightmapMatrix[i] ) - al );
        if ( s > 0.01 ) {
            if (!message)
                _printf( "Bad lightmapMatrix\n" );
            message = qtrue;
        }
        VectorSubtract(b->xyz, f->mins, delta);
        s = fabs( DotProduct( delta, f->lightmapMatrix[i] ) - bl );
        if ( s > 0.01 ) {
            if (!message)
                _printf( "Bad lightmapMatrix\n" );
            message = qtrue;
        }
        VectorSubtract(c->xyz, f->mins, delta);
        s = fabs( DotProduct( delta, f->lightmapMatrix[i] ) - cl );
        if ( s > 0.01 ) {
            if (!message)
                _printf( "Bad lightmapMatrix\n" );
            message = qtrue;
        }
        VectorAdd(f->mins, surfaceOrigin[dsurf - drawSurfaces], f->mins);
    }
}

/*
=============
Plane_Equal
=============
*/
#define NORMAL_EPSILON  0.0001
#define DIST_EPSILON    0.02

int Plane_Equal(plane_t *a, plane_t *b, int flip)
{
    vec3_t normal;
    float dist;

    if (flip) {
        normal[0] = - b->normal[0];
        normal[1] = - b->normal[1];
        normal[2] = - b->normal[2];
        dist = - b->dist;
    }
    else {
        normal[0] = b->normal[0];
        normal[1] = b->normal[1];
        normal[2] = b->normal[2];
        dist = b->dist;
    }
    if (
       fabs(a->normal[0] - normal[0]) < NORMAL_EPSILON
    && fabs(a->normal[1] - normal[1]) < NORMAL_EPSILON
    && fabs(a->normal[2] - normal[2]) < NORMAL_EPSILON
    && fabs(a->dist - dist) < DIST_EPSILON )
        return qtrue;
    return qfalse;
}

/*
=============
VL_PlaneFromPoints
=============
*/
qboolean VL_PlaneFromPoints( plane_t *plane, const vec3_t a, const vec3_t b, const vec3_t c ) {
    vec3_t  d1, d2;

    VectorSubtract( b, a, d1 );
    VectorSubtract( c, a, d2 );
    CrossProduct( d2, d1, plane->normal );
    if ( VectorNormalize( plane->normal, plane->normal ) == 0 ) {
        return qfalse;
    }

    plane->dist =