tree.cpp

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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 
*/
 
#include "bsp.h"
 
int c_nodes;
int c_nonvis;

node_t* AllocNode (void)
{
    return Mem_AllocType(node_t);
}
 
static void FreeTreePortals_r (node_t* node)
{
    portal_t* p, *nextp;
 
    /* free children */
    if (node->planenum != PLANENUM_LEAF) {
        FreeTreePortals_r(node->children[0]);
        FreeTreePortals_r(node->children[1]);
    }
 
    /* free portals */
    for (p = node->portals; p; p = nextp) {
        const int s = (p->nodes[1] == node);
        nextp = p->next[s];
 
        RemovePortalFromNode(p, p->nodes[!s]);
        FreePortal(p);
    }
    node->portals = nullptr;
}
 
static void FreeTree_r (node_t* node)
{
    face_t* f, *nextf;
 
    /* free children */
    if (node->planenum != PLANENUM_LEAF) {
        FreeTree_r(node->children[0]);
        FreeTree_r(node->children[1]);
    }
 
    /* free bspbrushes */
    FreeBrushList(node->brushlist);
 
    /* free faces */
    for (f = node->faces; f; f = nextf) {
        nextf = f->next;
        FreeFace(f);
    }
 
    /* free the node */
    if (node->volume)
        FreeBrush(node->volume);
 
    if (threadstate.numthreads == 1)
        c_nodes--;
    Mem_Free(node);
}
 

tree_t* AllocTree (void)
{
    tree_t* tree = Mem_AllocType(tree_t);
 
    tree->aabb.setNegativeVolume();
 
    return tree;
}
 
 
void FreeTree (tree_t* tree)
{
    FreeTreePortals_r(tree->headnode);
    FreeTree_r(tree->headnode);
    Mem_Free(tree);
}
 
 
static void CheckPlaneAgainstParents (uint16_t pnum, const node_t* node)
{
    node_t* p;
 
    for (p = node->parent; p; p = p->parent) {
        if (p->planenum == pnum)
            Sys_Error("Tried parent");
    }
}
 
static void LeafNode (node_t* node, bspbrush_t* brushes)
{
    node->side = nullptr;
    node->planenum = PLANENUM_LEAF;
 
    Verb_Printf(VERB_DUMP, "LeafNode: scanning brushes.\n");
 
    node->contentFlags = BrushListCalcContents(brushes);
    node->brushlist = brushes;
}
 
static node_t* BuildTree_r (node_t* node, bspbrush_t* brushes)
{
    node_t* newnode;
    side_t* bestside;
    int i;
    bspbrush_t* children[2];
 
    if (threadstate.numthreads == 1)
        c_nodes++;
 
    /* find the best plane to use as a splitter */
    bestside = SelectSplitSide(brushes, node->volume);
    if (!bestside) {
        /* leaf node */
        LeafNode(node, brushes);
        Verb_Printf(VERB_DUMP, "BuildTree_r: Created a leaf node.\n");
        return node;
    }
    /* make sure the selected plane hasn't been used before. */
    CheckPlaneAgainstParents(bestside->planenum, node);
 
    Verb_Printf(VERB_DUMP, "BuildTree_r: splitting along plane %i\n", (int)bestside->planenum);
 
    /* this is a splitplane node */
    node->side = bestside;
    node->planenum = bestside->planenum & ~1;   /* always use front facing */
 
    SplitBrushList(brushes, node->planenum, &children[0], &children[1]);
    FreeBrushList(brushes);
 
    /* allocate children before recursing */
    for (i = 0; i < 2; i++) {
        newnode = AllocNode();
        newnode->parent = node;
        node->children[i] = newnode;
    }
 
    SplitBrush(node->volume, node->planenum, &node->children[0]->volume,
        &node->children[1]->volume);
 
    /* recursively process children */
    for (i = 0; i < 2; i++) {
        node->children[i] = BuildTree_r(node->children[i], children[i]);
    }
 
    return node;
}

tree_t* BuildTree (bspbrush_t* brushlist, const vec3_t mins, const vec3_t maxs)
{
    node_t* node;
    tree_t* tree;
    AABB blBox;
 
    Verb_Printf(VERB_EXTRA, "--- BrushBSP ---\n");
 
    tree = AllocTree();
 
    blBox.setNegativeVolume();
    BrushlistCalcStats(brushlist, blBox);
    tree->aabb.add(blBox);
 
    c_nodes = 0;
    c_nonvis = 0;
    node = AllocNode();
 
    node->volume = BrushFromBounds(mins, maxs);
 
    tree->headnode = node;
 
    node = BuildTree_r(node, brushlist);
 
    Verb_Printf(VERB_EXTRA, "%5i visible nodes\n", c_nodes / 2 - c_nonvis);
    Verb_Printf(VERB_EXTRA, "%5i nonvis nodes\n", c_nonvis);
    Verb_Printf(VERB_EXTRA, "%5i leafs\n", (c_nodes + 1) / 2);
    return tree;
}
 
/*=========================================================
NODES THAT DON'T SEPERATE DIFFERENT CONTENTS CAN BE PRUNED
=========================================================*/
 
static int c_pruned;

static void PruneNodes_r (node_t* node)
{
    bspbrush_t* b, *next;
 
    if (node->planenum == PLANENUM_LEAF)
        return;
    PruneNodes_r(node->children[0]);
    PruneNodes_r(node->children[1]);
 
    if ((node->children[0]->contentFlags & CONTENTS_SOLID)
     && (node->children[1]->contentFlags & CONTENTS_SOLID)) {
        if (node->faces)
            Sys_Error("node->faces seperating CONTENTS_SOLID");
        if (node->children[0]->faces || node->children[1]->faces)
            Sys_Error("!node->faces with children");

        node->planenum = PLANENUM_LEAF;
        node->contentFlags = CONTENTS_SOLID;
 
        if (node->brushlist)
            Sys_Error("PruneNodes: node->brushlist");
 
        /* combine brush lists */
        node->brushlist = node->children[1]->brushlist;
 
        for (b = node->children[0]->brushlist; b; b = next) {
            next = b->next;
            b->next = node->brushlist;
            node->brushlist = b;
        }
 
        c_pruned++;
    }
}

void PruneNodes (node_t* node)
{
    Verb_Printf(VERB_EXTRA, "--- PruneNodes ---\n");
    c_pruned = 0;
    PruneNodes_r(node);
    Verb_Printf(VERB_EXTRA, "%5i pruned nodes\n", c_pruned);
}