facebsp.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 "qbsp.h"


int         c_faceLeafs;


/*
================
AllocBspFace
================
*/
bspface_t   *AllocBspFace( void ) {
    bspface_t   *f;

    f = malloc(sizeof(*f));
    memset( f, 0, sizeof(*f) );

    return f;
}

/*
================
FreeBspFace
================
*/
void    FreeBspFace( bspface_t *f ) {
    if ( f->w ) {
        FreeWinding( f->w );
    }
    free( f );
}


/*
================
SelectSplitPlaneNum
================
*/
int hintsplit;

#define BLOCK_SIZE  1024
int SelectSplitPlaneNum( node_t *node, bspface_t *list ) {
    bspface_t   *split;
    bspface_t   *check;
    bspface_t   *bestSplit;
    int         splits, facing, front, back;
    int         side;
    plane_t     *plane;
    int         value, bestValue;
    int         i;
    vec3_t      normal;
    float       dist;
    int         planenum;

    hintsplit = qfalse;
    // if it is crossing a 1k block boundary, force a split
    for ( i = 0 ; i < 2 ; i++ ) {
        dist = BLOCK_SIZE * ( floor( node->mins[i] / BLOCK_SIZE ) + 1 );    
        if ( node->maxs[i] > dist ) {
            VectorClear( normal );
            normal[i] = 1;
            planenum = FindFloatPlane( normal, dist );
            return planenum;
        }
    }

    // pick one of the face planes
    bestValue = -99999;
    bestSplit = list;

    for ( split = list ; split ; split = split->next ) {
        split->checked = qfalse;
    }

    for ( split = list ; split ; split = split->next ) {
        if ( split->checked ) {
            continue;
        }
        plane = &mapplanes[ split->planenum ];
        splits = 0;
        facing = 0;
        front = 0;
        back = 0;
        for ( check = list ; check ; check = check->next ) {
            if ( check->planenum == split->planenum ) {
                facing++;
                check->checked = qtrue; // won't need to test this plane again
                continue;
            }
            side = WindingOnPlaneSide( check->w, plane->normal, plane->dist );
            if ( side == SIDE_CROSS ) {
                splits++;
            } else if ( side == SIDE_FRONT ) {
                front++;
            } else if ( side == SIDE_BACK ) {
                back++;
            }
        }
        value =  5*facing - 5*splits; // - abs(front-back);
        if ( plane->type < 3 ) {
            value+=5;       // axial is better
        }
        value += split->priority;       // prioritize hints higher

        if ( value > bestValue ) {
            bestValue = value;
            bestSplit = split;
        }
    }

    if ( bestValue == -99999 ) {
        return -1;
    }

    if (bestSplit->hint)
        hintsplit = qtrue;

    return bestSplit->planenum;
}

int CountFaceList( bspface_t *list ) {
    int     c;
    c = 0;
    for ( ; list ; list = list->next ) {
        c++;
    }
    return c;
}

/*
================
BuildFaceTree_r
================
*/
void    BuildFaceTree_r( node_t *node, bspface_t *list ) {
    bspface_t   *split;
    bspface_t   *next;
    int         side;
    plane_t     *plane;
    bspface_t   *newFace;
    bspface_t   *childLists[2];
    winding_t   *frontWinding, *backWinding;
    int         i;
    int         splitPlaneNum;

    i = CountFaceList( list );

    splitPlaneNum = SelectSplitPlaneNum( node, list );
    // if we don't have any more faces, this is a node
    if ( splitPlaneNum == -1 ) {
        node->planenum = PLANENUM_LEAF;
        c_faceLeafs++;
        return;
    }

    // partition the list
    node->planenum = splitPlaneNum;
    node->hint = hintsplit;
    plane = &mapplanes[ splitPlaneNum ];
    childLists[0] = NULL;
    childLists[1] = NULL;
    for ( split = list ; split ; split = next ) {
        next = split->next;

        if ( split->planenum == node->planenum ) {
            FreeBspFace( split );
            continue;
        }

        side = WindingOnPlaneSide( split->w, plane->normal, plane->dist );

        if ( side == SIDE_CROSS ) {
            ClipWindingEpsilon( split->w, plane->normal, plane->dist, CLIP_EPSILON * 2,
                &frontWinding, &backWinding );
            if ( frontWinding ) {
                newFace = AllocBspFace();
                newFace->w = frontWinding;
                newFace->next = childLists[0];
                newFace->planenum = split->planenum;
                newFace->priority = split->priority;
                newFace->hint = split->hint;
                childLists[0] = newFace;
            }
            if ( backWinding ) {
                newFace = AllocBspFace();
                newFace->w = backWinding;
                newFace->next = childLists[1];
                newFace->planenum = split->planenum;
                newFace->priority = split->priority;
                newFace->hint = split->hint;
                childLists[1] = newFace;
            }
            FreeBspFace( split );
        } else if ( side == SIDE_FRONT ) {
            split->next = childLists[0];
            childLists[0] = split;
        } else if ( side == SIDE_BACK ) {
            split->next = childLists[1];
            childLists[1] = split;
        }
    }


    // recursively process children
    for ( i = 0 ; i < 2 ; i++ ) {
        node->children[i] = AllocNode();
        node->children[i]->parent = node;
        VectorCopy( node->mins, node->children[i]->mins );
        VectorCopy( node->maxs, node->children[i]->maxs );
    }

    for ( i = 0 ; i < 3 ; i++ ) {
        if ( plane->normal[i] == 1 ) {
            node->children[0]->mins[i] = plane->dist;
            node->children[1]->maxs[i] = plane->dist;
            break;
        }
    }

    for ( i = 0 ; i < 2 ; i++ ) {
        BuildFaceTree_r ( node->children[i], childLists[i]);
    }
}


/*
================
FaceBSP

List will be freed before returning
================
*/
tree_t *FaceBSP( bspface_t *list ) {
    tree_t      *tree;
    bspface_t   *face;
    int         i;
    int         count;

    qprintf( "--- FaceBSP ---\n" );

    tree = AllocTree ();

    count = 0;
    for ( face = list ; face ; face = face->next ) {
        count++;
        for ( i = 0 ; i < face->w->numpoints ; i++ ) {
            AddPointToBounds( face->w->p[i], tree->mins, tree->maxs);
        }
    }
    qprintf( "%5i faces\n", count );

    tree->headnode = AllocNode();
    VectorCopy( tree->mins, tree->headnode->mins );
    VectorCopy( tree->maxs, tree->headnode->maxs );
    c_faceLeafs = 0;

    BuildFaceTree_r ( tree->headnode, list );

    qprintf( "%5i leafs\n", c_faceLeafs );

    return tree;
}


/*
=================
BspFaceForPortal
=================
*/
bspface_t *BspFaceForPortal( portal_t *p ) {
    bspface_t   *f;

    f = AllocBspFace();
    f->w = CopyWinding( p->winding );
    f->planenum = p->onnode->planenum & ~1;

    return f;
}



/*
=================
MakeStructuralBspFaceList
=================
*/
bspface_t   *MakeStructuralBspFaceList( bspbrush_t *list ) {
    bspbrush_t  *b;
    int         i;
    side_t      *s;
    winding_t   *w;
    bspface_t   *f, *flist;

    flist = NULL;
    for ( b = list ; b ; b = b->next ) {
        if ( b->detail ) {
            continue;
        }
        for ( i = 0 ; i < b->numsides ; i++ ) {
            s = &b->sides[i];
            w = s->winding;
            if ( !w ) {
                continue;
            }
            f = AllocBspFace();
            f->w = CopyWinding( w );
            f->planenum = s->planenum & ~1;
            f->next = flist;
            if (s->surfaceFlags & SURF_HINT) {
                //f->priority = HINT_PRIORITY;
                f->hint = qtrue;
            }
            flist = f;
        }
    }

    return flist;
}

/*
=================
MakeVisibleBspFaceList
=================
*/
bspface_t   *MakeVisibleBspFaceList( bspbrush_t *list ) {
    bspbrush_t  *b;
    int         i;
    side_t      *s;
    winding_t   *w;
    bspface_t   *f, *flist;

    flist = NULL;
    for ( b = list ; b ; b = b->next ) {
        if ( b->detail ) {
            continue;
        }
        for ( i = 0 ; i < b->numsides ; i++ ) {
            s = &b->sides[i];
            w = s->visibleHull;
            if ( !w ) {
                continue;
            }
            f = AllocBspFace();
            f->w = CopyWinding( w );
            f->planenum = s->planenum & ~1;
            f->next = flist;
            if (s->surfaceFlags & SURF_HINT) {
                //f->priority = HINT_PRIORITY;
                f->hint = qtrue;
            }
            flist = f;
        }
    }

    return flist;
}

---