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

#include "qbsp.h"
#include "l_mem.h"

/*

  some faces will be removed before saving, but still form nodes:

  the insides of sky volumes
  meeting planes of different water current volumes

*/

// undefine for dumb linear searches
#define USE_HASHING

#define INTEGRAL_EPSILON    0.01
#define POINT_EPSILON       0.5
#define OFF_EPSILON         0.5

int c_merge;
int c_subdivide;

int c_totalverts;
int c_uniqueverts;
int c_degenerate;
int c_tjunctions;
int c_faceoverflows;
int c_facecollapse;
int c_badstartverts;

#define MAX_SUPERVERTS  512
int superverts[MAX_SUPERVERTS];
int numsuperverts;

face_t      *edgefaces[MAX_MAP_EDGES][2];
int     firstmodeledge = 1;
int     firstmodelface;

int c_tryedges;

vec3_t  edge_dir;
vec3_t  edge_start;
vec_t   edge_len;

int     num_edge_verts;
int     edge_verts[MAX_MAP_VERTS];

face_t *NewFaceFromFace (face_t *f);

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

typedef struct hashvert_s
{
    struct hashvert_s   *next;
    int     num;
} hashvert_t;


#define HASH_SIZE   64


int vertexchain[MAX_MAP_VERTS];     // the next vertex in a hash chain
int hashverts[HASH_SIZE*HASH_SIZE]; // a vertex number, or 0 for no verts

face_t      *edgefaces[MAX_MAP_EDGES][2];

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


unsigned HashVec (vec3_t vec)
{
    int         x, y;

    x = (4096 + (int)(vec[0]+0.5)) >> 7;
    y = (4096 + (int)(vec[1]+0.5)) >> 7;

    if ( x < 0 || x >= HASH_SIZE || y < 0 || y >= HASH_SIZE )
        Error ("HashVec: point outside valid range");
    
    return y*HASH_SIZE + x;
}

#ifdef USE_HASHING
/*
=============
GetVertex

Uses hashing
=============
*/
int GetVertexnum (vec3_t in)
{
    int         h;
    int         i;
    float       *p;
    vec3_t      vert;
    int         vnum;

    c_totalverts++;

    for (i=0 ; i<3 ; i++)
    {
        if ( fabs(in[i] - Q_rint(in[i])) < INTEGRAL_EPSILON)
            vert[i] = Q_rint(in[i]);
        else
            vert[i] = in[i];
    }
    
    h = HashVec (vert);
    
    for (vnum=hashverts[h] ; vnum ; vnum=vertexchain[vnum])
    {
        p = dvertexes[vnum].point;
        if ( fabs(p[0]-vert[0])<POINT_EPSILON
        && fabs(p[1]-vert[1])<POINT_EPSILON
        && fabs(p[2]-vert[2])<POINT_EPSILON )
            return vnum;
    }
    
// emit a vertex
    if (numvertexes == MAX_MAP_VERTS)
        Error ("numvertexes == MAX_MAP_VERTS");

    dvertexes[numvertexes].point[0] = vert[0];
    dvertexes[numvertexes].point[1] = vert[1];
    dvertexes[numvertexes].point[2] = vert[2];

    vertexchain[numvertexes] = hashverts[h];
    hashverts[h] = numvertexes;

    c_uniqueverts++;

    numvertexes++;
        
    return numvertexes-1;
}
#else
/*
==================
GetVertexnum

Dumb linear search
==================
*/
int GetVertexnum (vec3_t v)
{
    int         i, j;
    dvertex_t   *dv;
    vec_t       d;

    c_totalverts++;

    // make really close values exactly integral
    for (i=0 ; i<3 ; i++)
    {
        if ( fabs(v[i] - (int)(v[i]+0.5)) < INTEGRAL_EPSILON )
            v[i] = (int)(v[i]+0.5);
        if (v[i] < -4096 || v[i] > 4096)
            Error ("GetVertexnum: outside +/- 4096");
    }

    // search for an existing vertex match
    for (i=0, dv=dvertexes ; i<numvertexes ; i++, dv++)
    {
        for (j=0 ; j<3 ; j++)
        {
            d = v[j] - dv->point[j];
            if ( d > POINT_EPSILON || d < -POINT_EPSILON)
                break;
        }
        if (j == 3)
            return i;       // a match
    }

    // new point
    if (numvertexes == MAX_MAP_VERTS)
        Error ("MAX_MAP_VERTS");
    VectorCopy (v, dv->point);
    numvertexes++;
    c_uniqueverts++;

    return numvertexes-1;
}
#endif


/*
==================
FaceFromSuperverts

The faces vertexes have been added to the superverts[] array,
and there may be more there than can be held in a face (MAXEDGES).

If less, the faces vertexnums[] will be filled in, otherwise
face will reference a tree of split[] faces until all of the
vertexnums can be added.

superverts[base] will become face->vertexnums[0], and the others
will be circularly filled in.
==================
*/
void FaceFromSuperverts (node_t *node, face_t *f, int base)
{
    face_t  *newf;
    int     remaining;
    int     i;

    remaining = numsuperverts;
    while (remaining > MAXEDGES)
    {   // must split into two faces, because of vertex overload
        c_faceoverflows++;

        newf = f->split[0] = NewFaceFromFace (f);
        newf = f->split[0];
        newf->next = node->faces;
        node->faces = newf;

        newf->numpoints = MAXEDGES;
        for (i=0 ; i<MAXEDGES ; i++)
            newf->vertexnums[i] = superverts[(i+base)%numsuperverts];

        f->split[1] = NewFaceFromFace (f);
        f = f->split[1];
        f->next = node->faces;
        node->faces = f;

        remaining -= (MAXEDGES-2);
        base = (base+MAXEDGES-1)%numsuperverts;
    }

    // copy the vertexes back to the face
    f->numpoints = remaining;
    for (i=0 ; i<remaining ; i++)
        f->vertexnums[i] = superverts[(i+base)%numsuperverts];
}


/*
==================
EmitFaceVertexes
==================
*/
void EmitFaceVertexes (node_t *node, face_t *f)
{
    winding_t   *w;
    int         i;

    if (f->merged || f->split[0] || f->split[1])
        return;

    w = f->w;
    for (i=0 ; i<w->numpoints ; i++)
    {
        if (noweld)
        {   // make every point unique
            if (numvertexes == MAX_MAP_VERTS)
                Error ("MAX_MAP_VERTS");
            superverts[i] = numvertexes;
            VectorCopy (w->p[i], dvertexes[numvertexes].point);
            numvertexes++;
            c_uniqueverts++;
            c_totalverts++;
        }
        else
            superverts[i] = GetVertexnum (w->p[i]);
    }
    numsuperverts = w->numpoints;

    // this may fragment the face if > MAXEDGES
    FaceFromSuperverts (node, f, 0);
}

/*
==================
EmitVertexes_r
==================
*/
void EmitVertexes_r (node_t *node)
{
    int     i;
    face_t  *f;

    if (node->planenum == PLANENUM_LEAF)
        return;

    for (f=node->faces ; f ; f=f->next)
    {
        EmitFaceVertexes (node, f);
    }

    for (i=0 ; i<2 ; i++)
        EmitVertexes_r (node->children[i]);
}


#ifdef USE_HASHING
/*
==========
FindEdgeVerts

Uses the hash tables to cut down to a small number
==========
*/
void FindEdgeVerts (vec3_t v1, vec3_t v2)
{
    int     x1, x2, y1, y2, t;
    int     x, y;
    int     vnum;

#if 0
{
    int     i;
    num_edge_verts = numvertexes-1;
    for (i=0 ; i<numvertexes-1 ; i++)
        edge_verts[i] = i+1;
}
#endif

    x1 = (4096 + (int)(v1[0]+0.5)) >> 7;
    y1 = (4096 + (int)(v1[1]+0.5)) >> 7;
    x2 = (4096 + (int)(v2[0]+0.5)) >> 7;
    y2 = (4096 + (int)(v2[1]+0.5)) >> 7;

    if (x1 > x2)
    {
        t = x1;
        x1 = x2;
        x2 = t;
    }
    if (y1 > y2)
    {
        t = y1;
        y1 = y2;
        y2 = t;
    }
#if 0
    x1--;
    x2++;
    y1--;
    y2++;
    if (x1 < 0)
        x1 = 0;
    if (x2 >= HASH_SIZE)
        x2 = HASH_SIZE;
    if (y1 < 0)
        y1 = 0;
    if (y2 >= HASH_SIZE)
        y2 = HASH_SIZE;
#endif
    num_edge_verts = 0;
    for (x=x1 ; x <= x2 ; x++)
    {
        for (y=y1 ; y <= y2 ; y++)
        {
            for (vnum=hashverts[y*HASH_SIZE+x] ; vnum ; vnum=vertexchain[vnum])
            {
                edge_verts[num_edge_verts++] = vnum;
            }
        }
    }
}

#else
/*
==========
FindEdgeVerts

Forced a dumb check of everything
==========
*/
void FindEdgeVerts (vec3_t v1, vec3_t v2)
{
    int     i;

    num_edge_verts = numvertexes-1;
    for (i=0 ; i<num_edge_verts ; i++)
        edge_verts[i] = i+1;
}
#endif

/*
==========
TestEdge

Can be recursively reentered
==========
*/
void TestEdge (vec_t start, vec_t end, int p1, int p2, int startvert)
{
    int     j, k;
    vec_t   dist;
    vec3_t  delta;
    vec3_t  exact;
    vec3_t  off;
    vec_t   error;
    vec3_t  p;

    if (p1 == p2)
    {
        c_degenerate++;
        return;     // degenerate edge
    }

    for (k=startvert ; k<num_edge_verts ; k++)
    {
        j = edge_verts[k];
        if (j==p1 || j == p2)
            continue;

        VectorCopy (dvertexes[j].point, p);

        VectorSubtract (p, edge_start, delta);
        dist = DotProduct (delta, edge_dir);
        if (dist <=start || dist >= end)
            continue;       // off an end
        VectorMA (edge_start, dist, edge_dir, exact);
        VectorSubtract (p, exact, off);
        error = VectorLength (off);

        if (fabs(error) > OFF_EPSILON)
            continue;       // not on the edge

        // break the edge
        c_tjunctions++;
        TestEdge (start, dist, p1, j, k+1);
        TestEdge (dist, end, j, p2, k+1);
        return;
    }

    // the edge p1 to p2 is now free of tjunctions
    if (numsuperverts >= MAX_SUPERVERTS)
        Error ("MAX_SUPERVERTS");
    superverts[numsuperverts] = p1;
    numsuperverts++;
}

/*
==================
FixFaceEdges

==================
*/
void FixFaceEdges (node_t *node, face_t *f)
{
    int     p1, p2;
    int     i;
    vec3_t  e2;
    vec_t   len;
    int     count[MAX_SUPERVERTS], start[MAX_SUPERVERTS];
    int     base;

    if (f->merged || f->split[0] || f->split[1])
        return;

    numsuperverts = 0;

    for (i=0 ; i<f->numpoints ; i++)
    {
        p1 = f->vertexnums[i];
        p2 = f->vertexnums[(i+1)%f->numpoints];

        VectorCopy (dvertexes[p1].point, edge_start);
        VectorCopy (dvertexes[p2].point, e2);

        FindEdgeVerts (edge_start, e2);

        VectorSubtract (e2, edge_start, edge_dir);
        len = VectorNormalize(edge_dir);

        start[i] = numsuperverts;
        TestEdge (0, len, p1, p2, 0);

        count[i] = numsuperverts - start[i];
    }

    if (numsuperverts < 3)
    {   // entire face collapsed
        f->numpoints = 0;
        c_facecollapse++;
        return;
    }

    // we want to pick a vertex that doesn't have tjunctions
    // on either side, which can cause artifacts on trifans,
    // especially underwater
    for (i=0 ; i<f->numpoints ; i++)
    {
        if (count[i] == 1 && count[(i+f->numpoints-1)%f->numpoints] == 1)
            break;
    }
    if (i == f->numpoints)
    {
        f->badstartvert = true;
        c_badstartverts++;
        base = 0;
    }
    else
    {   // rotate the vertex order
        base = start[i];
    }

    // this may fragment the face if > MAXEDGES
    FaceFromSuperverts (node, f, base);
}

/*
==================
FixEdges_r
==================
*/
void FixEdges_r (node_t *node)
{
    int     i;
    face_t  *f;

    if (node->planenum == PLANENUM_LEAF)
        return;

    for (f=node->faces ; f ; f=f->next)
        FixFaceEdges (node, f);

    for (i=0 ; i<2 ; i++)
        FixEdges_r (node->children[i]);
}

/*
===========
FixTjuncs

===========
*/
void FixTjuncs (node_t *headnode)
{
    // snap and merge all vertexes
    qprintf ("---- snap verts ----\n");
    memset (hashverts, 0, sizeof(hashverts));
    c_totalverts = 0;
    c_uniqueverts = 0;
    c_faceoverflows = 0;
    EmitVertexes_r (headnode);
    qprintf ("%i unique from %i\n", c_uniqueverts, c_totalverts);

    // break edges on tjunctions
    qprintf ("---- tjunc ----\n");
    c_tryedges = 0;
    c_degenerate = 0;
    c_facecollapse = 0;
    c_tjunctions = 0;
    if (!notjunc)
        FixEdges_r (headnode);
    qprintf ("%5i edges degenerated\n", c_degenerate);
    qprintf ("%5i faces degenerated\n", c_facecollapse);
    qprintf ("%5i edges added by tjunctions\n", c_tjunctions);
    qprintf ("%5i faces added by tjunctions\n", c_faceoverflows);
    qprintf ("%5i bad start verts\n", c_badstartverts);
}


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

int     c_faces;

face_t  *AllocFace (void)
{
    face_t  *f;

    f = GetMemory(sizeof(*f));
    memset (f, 0, sizeof(*f));
    c_faces++;

    return f;
}

face_t *NewFaceFromFace (face_t *f)
{
    face_t  *newf;

    newf = AllocFace ();
    *newf = *f;
    newf->merged = NULL;
    newf->split[0] = newf->split[1] = NULL;
    newf->w = NULL;
    return newf;
}

void FreeFace (face_t *f)
{
    if (f->w)
        FreeWinding (f->w);
    FreeMemory(f);
    c_faces--;
}

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

/*
==================
GetEdge

Called by writebsp.
Don't allow four way edges
==================
*/
int GetEdge2 (int v1, int v2,  face_t *f)
{
    dedge_t *edge;
    int     i;

    c_tryedges++;

    if (!noshare)
    {
        for (i=firstmodeledge ; i < numedges ; i++)
        {
            edge = &dedges[i];
            if (v1 == edge->v[1] && v2 == edge->v[0]
            && edgefaces[i][0]->contents == f->contents)
            {
                if (edgefaces[i][1])
    //              printf ("WARNING: multiple backward edge\n");
                    continue;
                edgefaces[i][1] = f;
                return -i;
            }
    #if 0
            if (v1 == edge->v[0] && v2 == edge->v[1])
            {
                printf ("WARNING: multiple forward edge\n");
                return i;
            }
    #endif
        }
    }

// emit an edge
    if (numedges >= MAX_MAP_EDGES)
        Error ("numedges == MAX_MAP_EDGES");
    edge = &dedges[numedges];
    numedges++;
    edge->v[0] = v1;
    edge->v[1] = v2;
    edgefaces[numedges-1][0] = f;
    
    return numedges-1;
}

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

FACE MERGING

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

/*
=============
TryMerge

If two polygons share a common edge and the edges that meet at the
common points are both inside the other polygons, merge them

Returns NULL if the faces couldn't be merged, or the new face.
The originals will NOT be freed.
=============
*/
face_t *TryMerge (face_t *f1, face_t *f2, vec3_t planenormal)
{
    face_t      *newf;
    winding_t   *nw;

    if (!f1->w || !f2->w)
        return NULL;
    if (f1->texinfo != f2->texinfo)
        return NULL;
    if (f1->planenum != f2->planenum)   // on front and back sides
        return NULL;
    if (f1->contents != f2->contents)
        return NULL;
        

    nw = TryMergeWinding (f1->w, f2->w, planenormal);
    if (!nw)
        return NULL;

    c_merge++;
    newf = NewFaceFromFace (f1);
    newf->w = nw;

    f1->merged = newf;
    f2->merged = newf;

    return newf;
}

/*
===============
MergeNodeFaces
===============
*/
void MergeNodeFaces (node_t *node)
{
    face_t  *f1, *f2, *end;
    face_t  *merged;
    plane_t *plane;

    plane = &mapplanes[node->planenum];
    merged = NULL;
    
    for (f1 = node->faces ; f1 ; f1 = f1->next)
    {
        if (f1->merged || f1->split[0] || f1->split[1])
            continue;

        for (f2 = node->faces ; f2 != f1 ; f2=f2->next)
        {
            if (f2->merged || f2->split[0] || f2->split[1])
                continue;

            //IDBUG: always passes the face's node's normal to TryMerge()
            //regardless of which side the face is on. Approximately 50% of
            //the time the face will be on the other side of node, and thus
            //the result of the convex/concave test in TryMergeWinding(),
            //which depends on the normal, is flipped. This causes faces
            //that shouldn't be merged to be merged and faces that
            //should be merged to not be merged. 
            //the following added line fixes this bug
            //thanks to: Alexander Malmberg <alexander@malmberg.org>
            plane = &mapplanes[f1->planenum];
            //
            merged = TryMerge (f1, f2, plane->normal);
            if (!merged)
                continue;

            // add merged to the end of the node face list 
            // so it will be checked against all the faces again
            for (end = node->faces ; end->next ; end = end->next)
            ;
            merged->next = NULL;
            end->next = merged;
            break;
        }
    }
}

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

/*
===============
SubdivideFace

Chop up faces that are larger than we want in the surface cache
===============
*/
void SubdivideFace (node_t *node, face_t *f)
{
    float       mins, maxs;
    vec_t       v;
    int         axis, i;
    texinfo_t   *tex;
    vec3_t      temp;
    vec_t       dist;
    winding_t   *w, *frontw, *backw;

    if (f->merged)
        return;

// special (non-surface cached) faces don't need subdivision
    tex = &texinfo[f->texinfo];

    if ( tex->flags & (SURF_WARP|SURF_SKY) )
    {
        return;
    }

    for (axis = 0 ; axis < 2 ; axis++)
    {
        while (1)
        {
            mins = 999999;
            maxs = -999999;
            
            VectorCopy (tex->vecs[axis], temp);
            w = f->w;
            for (i=0 ; i<w->numpoints ; i++)
            {
                v = DotProduct (w->p[i], temp);
                if (v < mins)
                    mins = v;
                if (v > maxs)
                    maxs = v;
            }
#if 0
            if (maxs - mins <= 0)
                Error ("zero extents");
#endif
            if (axis == 2)
            {   // allow double high walls
                if (maxs - mins <= subdivide_size/* *2 */)
                    break;
            }
            else if (maxs - mins <= subdivide_size)
                break;
            
        // split it
            c_subdivide++;
            
            v = VectorNormalize (temp);

            dist = (mins + subdivide_size - 16)/v;

            ClipWindingEpsilon (w, temp, dist, ON_EPSILON, &frontw, &backw);
            if (!frontw || !backw)
                Error ("SubdivideFace: didn't split the polygon");

            f->split[0] = NewFaceFromFace (f);
            f->split[0]->w = frontw;
            f->split[0]->next = node->faces;
            node->faces = f->split[0];

            f->split[1] = NewFaceFromFace (f);
            f->split[1]->w = backw;
            f->split[1]->next = node->faces;
            node->faces = f->split[1];

            SubdivideFace (node, f->split[0]);
            SubdivideFace (node, f->split[1]);
            return;
        }
    }
}

void SubdivideNodeFaces (node_t *node)
{
    face_t  *f;

    for (f = node->faces ; f ; f=f->next)
    {
        SubdivideFace (node, f);
    }
}

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

int c_nodefaces;


/*
============
FaceFromPortal

============
*/
face_t *FaceFromPortal (portal_t *p, int pside)
{
    face_t  *f;
    side_t  *side;

    side = p->side;
    if (!side)
        return NULL;    // portal does not bridge different visible contents

    f = AllocFace ();

    f->texinfo = side->texinfo;
    f->planenum = (side->planenum & ~1) | pside;
    f->portal = p;

    if ( (p->nodes[pside]->contents & CONTENTS_WINDOW)
        && VisibleContents(p->nodes[!pside]->contents^p->nodes[pside]->contents) == CONTENTS_WINDOW )
        return NULL;    // don't show insides of windows

    if (pside)
    {
        f->w = ReverseWinding(p->winding);
        f->contents = p->nodes[1]->contents;
    }
    else
    {
        f->w = CopyWinding(p->winding);
        f->contents = p->nodes[0]->contents;
    }
    return f;
}


/*
===============
MakeFaces_r

If a portal will make a visible face,
mark the side that originally created it

  solid / empty : solid
  solid / water : solid
  water / empty : water
  water / water : none
===============
*/
void MakeFaces_r (node_t *node)
{
    portal_t    *p;
    int         s;

    // recurse down to leafs
    if (node->planenum != PLANENUM_LEAF)
    {
        MakeFaces_r (node->children[0]);
        MakeFaces_r (node->children[1]);

        // merge together all visible faces on the node
        if (!nomerge)
            MergeNodeFaces (node);
        if (!nosubdiv)
            SubdivideNodeFaces (node);

        return;
    }

    // solid leafs never have visible faces
    if (node->contents & CONTENTS_SOLID)
        return;

    // see which portals are valid
    for (p=node->portals ; p ; p = p->next[s])
    {
        s = (p->nodes[1] == node);

        p->face[s] = FaceFromPortal (p, s);
        if (p->face[s])
        {
            c_nodefaces++;
            p->face[s]->next = p->onnode->faces;
            p->onnode->faces = p->face[s];
        }
    }
}

/*
============
MakeFaces
============
*/
void MakeFaces (node_t *node)
{
    qprintf ("--- MakeFaces ---\n");
    c_merge = 0;
    c_subdivide = 0;
    c_nodefaces = 0;

    MakeFaces_r (node);

    qprintf ("%5i makefaces\n", c_nodefaces);
    qprintf ("%5i merged\n", c_merge);
    qprintf ("%5i subdivided\n", c_subdivide);
}

---