bsp.c

Go to the documentation of this file.

/*
Copyright (C) 1997-2001 Id Software, Inc.
 
This program 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.
 
This program 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 this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/
// r_bsp.c
 
#include "sw.h"
 
//
// current entity info
//
qboolean        insubmodel;
entity_t        *currententity;
vec3_t          modelorg;       // modelorg is the viewpoint reletive to
                                // the currently rendering entity
vec3_t          r_entorigin;    // the currently rendering entity in world
                                // coordinates
 
vec3_t          entity_rotation[3];
 
int             r_currentbkey;
 
#define MAX_BMODEL_VERTS    500         // 6K
#define MAX_BMODEL_EDGES    1000        // 12K
 
static mvertex_t    *pbverts;
static bedge_t      *pbedges;
static int          numbverts, numbedges;
 
static mvertex_t    *pfrontenter, *pfrontexit;
 
static qboolean     makeclippededge;
 
 
//===========================================================================
 
/*
================
R_EntityRotate
================
*/
static void R_EntityRotate(vec3_t vec)
{
    vec3_t  tvec;
 
    VectorCopy(vec, tvec);
    vec[0] = DotProduct(entity_rotation[0], tvec);
    vec[1] = DotProduct(entity_rotation[1], tvec);
    vec[2] = DotProduct(entity_rotation[2], tvec);
}
 
 
/*
================
R_RotateBmodel
================
*/
void R_RotateBmodel(void)
{
    AnglesToAxis(currententity->angles, entity_rotation);
 
//
// rotate modelorg and the transformation matrix
//
    R_EntityRotate(modelorg);
    R_EntityRotate(vpn);
    R_EntityRotate(vright);
    R_EntityRotate(vup);
 
    R_TransformFrustum();
}
 
 
/*
================
R_RecursiveClipBPoly
 
Clip a bmodel poly down the world bsp tree
================
*/
static void R_RecursiveClipBPoly(bedge_t *pedges, mnode_t *pnode, mface_t *psurf)
{
    bedge_t     *psideedges[2], *pnextedge, *ptedge;
    int         i, side, lastside;
    float       dist, frac, lastdist;
    cplane_t    *splitplane, tplane;
    mvertex_t   *pvert, *plastvert, *ptvert;
    mnode_t     *pn;
    int         area;
 
    psideedges[0] = psideedges[1] = NULL;
 
    makeclippededge = qfalse;
 
// transform the BSP plane into model space
// FIXME: cache these?
    splitplane = pnode->plane;
    tplane.dist = -PlaneDiff(r_entorigin, splitplane);
    tplane.normal[0] = DotProduct(entity_rotation[0], splitplane->normal);
    tplane.normal[1] = DotProduct(entity_rotation[1], splitplane->normal);
    tplane.normal[2] = DotProduct(entity_rotation[2], splitplane->normal);
 
// clip edges to BSP plane
    for (; pedges; pedges = pnextedge) {
        pnextedge = pedges->pnext;
 
        // set the status for the last point as the previous point
        // FIXME: cache this stuff somehow?
        plastvert = pedges->v[0];
        lastdist = PlaneDiff(plastvert->point, &tplane);
 
        if (lastdist > 0)
            lastside = 0;
        else
            lastside = 1;
 
        pvert = pedges->v[1];
        dist = PlaneDiff(pvert->point, &tplane);
 
        if (dist > 0)
            side = 0;
        else
            side = 1;
 
        if (side != lastside) {
            // clipped
            if (numbverts >= MAX_BMODEL_VERTS)
                return;
 
            // generate the clipped vertex
            frac = lastdist / (lastdist - dist);
            ptvert = &pbverts[numbverts++];
            LerpVector(plastvert->point, pvert->point, frac, ptvert->point);
 
            // split into two edges, one on each side, and remember entering
            // and exiting points
            // FIXME: share the clip edge by having a winding direction flag?
            if (numbedges >= (MAX_BMODEL_EDGES - 1)) {
                Com_Printf("Out of edges for bmodel\n");
                return;
            }
 
            ptedge = &pbedges[numbedges];
            ptedge->pnext = psideedges[lastside];
            psideedges[lastside] = ptedge;
            ptedge->v[0] = plastvert;
            ptedge->v[1] = ptvert;
 
            ptedge = &pbedges[numbedges + 1];
            ptedge->pnext = psideedges[side];
            psideedges[side] = ptedge;
            ptedge->v[0] = ptvert;
            ptedge->v[1] = pvert;
 
            numbedges += 2;
 
            if (side == 0) {
                // entering for front, exiting for back
                pfrontenter = ptvert;
                makeclippededge = qtrue;
            } else {
                pfrontexit = ptvert;
                makeclippededge = qtrue;
            }
        } else {
            // add the edge to the appropriate side
            pedges->pnext = psideedges[side];
            psideedges[side] = pedges;
        }
    }
 
// if anything was clipped, reconstitute and add the edges along the clip
// plane to both sides (but in opposite directions)
    if (makeclippededge) {
        if (numbedges >= (MAX_BMODEL_EDGES - 2)) {
            Com_Error(ERR_DROP, "Out of edges for bmodel");
        }
 
        ptedge = &pbedges[numbedges];
        ptedge->pnext = psideedges[0];
        psideedges[0] = ptedge;
        ptedge->v[0] = pfrontexit;
        ptedge->v[1] = pfrontenter;
 
        ptedge = &pbedges[numbedges + 1];
        ptedge->pnext = psideedges[1];
        psideedges[1] = ptedge;
        ptedge->v[0] = pfrontenter;
        ptedge->v[1] = pfrontexit;
 
        numbedges += 2;
    }
 
// draw or recurse further
    for (i = 0; i < 2; i++) {
        if (psideedges[i]) {
            // draw if we've reached a non-solid leaf, done if all that's left is a
            // solid leaf, and continue down the tree if it's not a leaf
            pn = pnode->children[i];
 
            // we're done with this branch if the node or leaf isn't in the PVS
            if (pn->visframe == r_visframecount) {
                if (!pn->plane) {
                    mleaf_t *pl = (mleaf_t *)pn;
                    if (pl->contents != CONTENTS_SOLID) {
                        if (r_newrefdef.areabits) {
                            area = pl->area;
                            if (!Q_IsBitSet(r_newrefdef.areabits, area))
                                continue;       // not visible
                        }
 
                        r_currentbkey = pl->key;
                        R_RenderBmodelFace(psideedges[i], psurf);
                    }
                } else {
                    R_RecursiveClipBPoly(psideedges[i], pnode->children[i],
                                         psurf);
                }
            }
        }
    }
}
 
 
/*
================
R_DrawSolidClippedSubmodelPolygons
 
Bmodel crosses multiple leafs
================
*/
void R_DrawSolidClippedSubmodelPolygons(mmodel_t *pmodel, mnode_t *topnode)
{
    int         i, j;
    vec_t       dot;
    mface_t     *psurf;
    int         numsurfaces;
    cplane_t    *pplane;
    mvertex_t   bverts[MAX_BMODEL_VERTS];
    bedge_t     bedges[MAX_BMODEL_EDGES], *pbedge;
    msurfedge_t *surfedge;
 
// FIXME: use bounding-box-based frustum clipping info?
 
    psurf = pmodel->firstface;
    numsurfaces = pmodel->numfaces;
 
    for (i = 0; i < numsurfaces; i++, psurf++) {
        // find which side of the node we are on
        pplane = psurf->plane;
 
        dot = PlaneDiff(modelorg, pplane);
 
        // draw the polygon
        if ((!(psurf->drawflags & DSURF_PLANEBACK) && (dot < -BACKFACE_EPSILON)) ||
            ((psurf->drawflags & DSURF_PLANEBACK) && (dot > BACKFACE_EPSILON)))
            continue;
 
        // FIXME: use bounding-box-based frustum clipping info?
 
        // copy the edges to bedges, flipping if necessary so always
        // clockwise winding
        // FIXME: if edges and vertices get caches, these assignments must move
        // outside the loop, and overflow checking must be done here
        pbverts = bverts;
        pbedges = bedges;
        numbverts = numbedges = 0;
        pbedge = &bedges[numbedges];
        numbedges += psurf->numsurfedges;
 
        if (numbedges >= MAX_BMODEL_EDGES) {
            Com_Printf("Out of edges for bmodel\n");
            return;
        }
 
        surfedge = psurf->firstsurfedge;
        for (j = 0; j < psurf->numsurfedges; j++, surfedge++) {
            pbedge[j].v[0] = surfedge->edge->v[surfedge->vert    ];
            pbedge[j].v[1] = surfedge->edge->v[surfedge->vert ^ 1];
            pbedge[j].pnext = &pbedge[j + 1];
        }
 
        pbedge[j - 1].pnext = NULL; // mark end of edges
 
        if (!(psurf->texinfo->c.flags & SURF_TRANS_MASK))
            R_RecursiveClipBPoly(pbedge, topnode, psurf);
        else
            R_RenderBmodelFace(pbedge, psurf);
    }
}
 
 
/*
================
R_DrawSubmodelPolygons
 
All in one leaf
================
*/
void R_DrawSubmodelPolygons(mmodel_t *pmodel, int clipflags, mnode_t *topnode)
{
    int         i;
    vec_t       dot;
    mface_t *psurf;
    int         numsurfaces;
    cplane_t    *pplane;
 
// FIXME: use bounding-box-based frustum clipping info?
 
    psurf = pmodel->firstface;
    numsurfaces = pmodel->numfaces;
 
    for (i = 0; i < numsurfaces; i++, psurf++) {
        // find which side of the node we are on
        pplane = psurf->plane;
 
        dot = PlaneDiff(modelorg, pplane);
 
        // draw the polygon
        if (((psurf->drawflags & DSURF_PLANEBACK) && (dot < -BACKFACE_EPSILON)) ||
            (!(psurf->drawflags & DSURF_PLANEBACK) && (dot > BACKFACE_EPSILON))) {
            r_currentkey = ((mleaf_t *)topnode)->key;
 
            // FIXME: use bounding-box-based frustum clipping info?
            R_RenderFace(psurf, clipflags);
        }
    }
}
 
 
int c_drawnode;
 
/*
================
R_RecursiveWorldNode
================
*/
static void R_RecursiveWorldNode(mnode_t *node, int clipflags)
{
    int         i, c, side, *pindex;
    vec3_t      acceptpt, rejectpt;
    cplane_t    *plane;
    mface_t     *surf, **mark;
    float       d, dot;
    mleaf_t     *pleaf;
 
    while (node->visframe == r_visframecount) {
        // cull the clipping planes if not trivial accept
        // FIXME: the compiler is doing a lousy job of optimizing here; it could be
        //  twice as fast in ASM
        if (clipflags) {
            for (i = 0; i < 4; i++) {
                if (!(clipflags & (1 << i)))
                    continue;   // don't need to clip against it
 
                // generate accept and reject points
                // FIXME: do with fast look-ups or integer tests based on the sign bit
                // of the floating point values
 
                pindex = pfrustum_indexes[i];
 
                rejectpt[0] = (float)node->minmaxs[pindex[0]];
                rejectpt[1] = (float)node->minmaxs[pindex[1]];
                rejectpt[2] = (float)node->minmaxs[pindex[2]];
 
                d = PlaneDiff(rejectpt, &view_clipplanes[i]);
                if (d <= 0)
                    return;
 
                acceptpt[0] = (float)node->minmaxs[pindex[3 + 0]];
                acceptpt[1] = (float)node->minmaxs[pindex[3 + 1]];
                acceptpt[2] = (float)node->minmaxs[pindex[3 + 2]];
 
                d = PlaneDiff(acceptpt, &view_clipplanes[i]);
                if (d >= 0)
                    clipflags &= ~(1 << i); // node is entirely on screen
            }
        }
 
        c_drawnode++;
 
        // if a leaf node, draw stuff
        if (!node->plane) {
            pleaf = (mleaf_t *)node;
 
            if (pleaf->contents == CONTENTS_SOLID)
                return;     // solid
 
            // check for door connected areas
            if (r_newrefdef.areabits) {
                if (! Q_IsBitSet(r_newrefdef.areabits, pleaf->area))
                    return;     // not visible
            }
 
            mark = pleaf->firstleafface;
            c = pleaf->numleaffaces;
            if (c) {
                do {
                    (*mark)->drawframe = r_framecount;
                    mark++;
                } while (--c);
            }
 
            pleaf->key = r_currentkey;
            r_currentkey++;     // all bmodels in a leaf share the same key
            return;
        }
        // node is just a decision point, so go down the apropriate sides
 
        // find which side of the node we are on
        plane = node->plane;
 
        dot = PlaneDiffFast(modelorg, plane);
 
        if (dot >= 0)
            side = 0;
        else
            side = 1;
 
        // recurse down the children, front side first
        R_RecursiveWorldNode(node->children[side], clipflags);
 
        // draw stuff
        c = node->numfaces;
        if (c) {
            surf = node->firstface;
            if (dot < -BACKFACE_EPSILON) {
                do {
                    if ((surf->drawflags & DSURF_PLANEBACK) &&
                        (surf->drawframe == r_framecount)) {
                        R_RenderFace(surf, clipflags);
                    }
                    surf++;
                } while (--c);
            } else if (dot > BACKFACE_EPSILON) {
                do {
                    if (!(surf->drawflags & DSURF_PLANEBACK) &&
                        (surf->drawframe == r_framecount)) {
                        R_RenderFace(surf, clipflags);
                    }
                    surf++;
                } while (--c);
            }
 
            // all surfaces on the same node share the same sequence number
            r_currentkey++;
        }
 
        // recurse down the back side
        node = node->children[side ^ 1];
    }
}
 
 
 
/*
================
R_RenderWorld
================
*/
void R_RenderWorld(void)
{
 
    if (!r_drawworld->integer)
        return;
    if (r_newrefdef.rdflags & RDF_NOWORLDMODEL)
        return;
 
    c_drawnode = 0;
 
    // auto cycle the world frame for texture animation
    r_worldentity.frame = (int)(r_newrefdef.time * 2);
    currententity = &r_worldentity;
 
    VectorCopy(r_origin, modelorg);
 
    R_RecursiveWorldNode(r_worldmodel->nodes, 15);
}