diff options
Diffstat (limited to 'code/bspc/tree.c')
-rwxr-xr-x | code/bspc/tree.c | 566 |
1 files changed, 283 insertions, 283 deletions
diff --git a/code/bspc/tree.c b/code/bspc/tree.c index 3d2ee9c..bc3cb8e 100755 --- a/code/bspc/tree.c +++ b/code/bspc/tree.c @@ -1,283 +1,283 @@ -/*
-===========================================================================
-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"
-
-extern int c_nodes;
-int c_pruned;
-int freedtreemem = 0;
-
-void RemovePortalFromNode (portal_t *portal, node_t *l);
-
-//===========================================================================
-//
-// Parameter: -
-// Returns: -
-// Changes Globals: -
-//===========================================================================
-node_t *NodeForPoint (node_t *node, vec3_t origin)
-{
- plane_t *plane;
- vec_t d;
-
- while (node->planenum != PLANENUM_LEAF)
- {
- plane = &mapplanes[node->planenum];
- d = DotProduct (origin, plane->normal) - plane->dist;
- if (d >= 0)
- node = node->children[0];
- else
- node = node->children[1];
- }
- return node;
-} //end of the function NodeForPoint
-//===========================================================================
-//
-// Parameter: -
-// Returns: -
-// Changes Globals: -
-//===========================================================================
-void Tree_FreePortals_r (node_t *node)
-{
- portal_t *p, *nextp;
- int s;
-
- // free children
- if (node->planenum != PLANENUM_LEAF)
- {
- Tree_FreePortals_r(node->children[0]);
- Tree_FreePortals_r(node->children[1]);
- }
-
- // free portals
- for (p = node->portals; p; p = nextp)
- {
- s = (p->nodes[1] == node);
- nextp = p->next[s];
-
- RemovePortalFromNode (p, p->nodes[!s]);
-#ifdef ME
- if (p->winding) freedtreemem += MemorySize(p->winding);
- freedtreemem += MemorySize(p);
-#endif //ME
- FreePortal(p);
- }
- node->portals = NULL;
-} //end of the function Tree_FreePortals_r
-//===========================================================================
-//
-// Parameter: -
-// Returns: -
-// Changes Globals: -
-//===========================================================================
-void Tree_Free_r (node_t *node)
-{
-// face_t *f, *nextf;
- bspbrush_t *brush, *nextbrush;
-
- //free children
- if (node->planenum != PLANENUM_LEAF)
- {
- Tree_Free_r (node->children[0]);
- Tree_Free_r (node->children[1]);
- } //end if
- //free bspbrushes
-// FreeBrushList (node->brushlist);
- for (brush = node->brushlist; brush; brush = nextbrush)
- {
- nextbrush = brush->next;
-#ifdef ME
- freedtreemem += MemorySize(brush);
-#endif //ME
- FreeBrush(brush);
- } //end for
- node->brushlist = NULL;
-
- /*
- NOTE: only used when creating Q2 bsp
- // free faces
- for (f = node->faces; f; f = nextf)
- {
- nextf = f->next;
-#ifdef ME
- if (f->w) freedtreemem += MemorySize(f->w);
- freedtreemem += sizeof(face_t);
-#endif //ME
- FreeFace(f);
- } //end for
- */
-
- // free the node
- if (node->volume)
- {
-#ifdef ME
- freedtreemem += MemorySize(node->volume);
-#endif //ME
- FreeBrush (node->volume);
- } //end if
-
- if (numthreads == 1) c_nodes--;
-#ifdef ME
- freedtreemem += MemorySize(node);
-#endif //ME
- FreeMemory(node);
-} //end of the function Tree_Free_r
-//===========================================================================
-//
-// Parameter: -
-// Returns: -
-// Changes Globals: -
-//===========================================================================
-void Tree_Free(tree_t *tree)
-{
- //if no tree just return
- if (!tree) return;
- //
- freedtreemem = 0;
- //
- Tree_FreePortals_r(tree->headnode);
- Tree_Free_r(tree->headnode);
-#ifdef ME
- freedtreemem += MemorySize(tree);
-#endif //ME
- FreeMemory(tree);
-#ifdef ME
- Log_Print("freed ");
- PrintMemorySize(freedtreemem);
- Log_Print(" of tree memory\n");
-#endif //ME
-} //end of the function Tree_Free
-//===========================================================================
-//
-// Parameter: -
-// Returns: -
-// Changes Globals: -
-//===========================================================================
-tree_t *Tree_Alloc(void)
-{
- tree_t *tree;
-
- tree = GetMemory(sizeof(*tree));
- memset (tree, 0, sizeof(*tree));
- ClearBounds (tree->mins, tree->maxs);
-
- return tree;
-} //end of the function Tree_Alloc
-//===========================================================================
-//
-// Parameter: -
-// Returns: -
-// Changes Globals: -
-//===========================================================================
-void Tree_Print_r (node_t *node, int depth)
-{
- int i;
- plane_t *plane;
- bspbrush_t *bb;
-
- for (i=0 ; i<depth ; i++)
- printf (" ");
- if (node->planenum == PLANENUM_LEAF)
- {
- if (!node->brushlist)
- printf ("NULL\n");
- else
- {
- for (bb=node->brushlist ; bb ; bb=bb->next)
- printf ("%i ", bb->original->brushnum);
- printf ("\n");
- }
- return;
- }
-
- plane = &mapplanes[node->planenum];
- printf ("#%i (%5.2f %5.2f %5.2f):%5.2f\n", node->planenum,
- plane->normal[0], plane->normal[1], plane->normal[2],
- plane->dist);
- Tree_Print_r (node->children[0], depth+1);
- Tree_Print_r (node->children[1], depth+1);
-} //end of the function Tree_Print_r
-//===========================================================================
-// NODES THAT DON'T SEPERATE DIFFERENT CONTENTS CAN BE PRUNED
-//
-// Parameter: -
-// Returns: -
-// Changes Globals: -
-//===========================================================================
-void Tree_PruneNodes_r (node_t *node)
-{
- bspbrush_t *b, *next;
-
- if (node->planenum == PLANENUM_LEAF) return;
-
- Tree_PruneNodes_r (node->children[0]);
- Tree_PruneNodes_r (node->children[1]);
-
- if (create_aas)
- {
- if ((node->children[0]->contents & CONTENTS_LADDER) ||
- (node->children[1]->contents & CONTENTS_LADDER)) return;
- }
-
- if ((node->children[0]->contents & CONTENTS_SOLID)
- && (node->children[1]->contents & CONTENTS_SOLID))
- {
- if (node->faces)
- Error ("node->faces seperating CONTENTS_SOLID");
- if (node->children[0]->faces || node->children[1]->faces)
- Error ("!node->faces with children");
- // FIXME: free stuff
- node->planenum = PLANENUM_LEAF;
- node->contents = CONTENTS_SOLID;
- node->detail_seperator = false;
-
- if (node->brushlist)
- 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;
- } //end for
- //free the child nodes
- FreeMemory(node->children[0]);
- FreeMemory(node->children[1]);
- //two nodes are cut away
- c_pruned += 2;
- } //end if
-} //end of the function Tree_PruneNodes_r
-//===========================================================================
-//
-// Parameter: -
-// Returns: -
-// Changes Globals: -
-//===========================================================================
-void Tree_PruneNodes(node_t *node)
-{
- Log_Print("------- Prune Nodes --------\n");
- c_pruned = 0;
- Tree_PruneNodes_r(node);
- Log_Print("%5i pruned nodes\n", c_pruned);
-} //end of the function Tree_PruneNodes
+/* +=========================================================================== +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" + +extern int c_nodes; +int c_pruned; +int freedtreemem = 0; + +void RemovePortalFromNode (portal_t *portal, node_t *l); + +//=========================================================================== +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +node_t *NodeForPoint (node_t *node, vec3_t origin) +{ + plane_t *plane; + vec_t d; + + while (node->planenum != PLANENUM_LEAF) + { + plane = &mapplanes[node->planenum]; + d = DotProduct (origin, plane->normal) - plane->dist; + if (d >= 0) + node = node->children[0]; + else + node = node->children[1]; + } + return node; +} //end of the function NodeForPoint +//=========================================================================== +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +void Tree_FreePortals_r (node_t *node) +{ + portal_t *p, *nextp; + int s; + + // free children + if (node->planenum != PLANENUM_LEAF) + { + Tree_FreePortals_r(node->children[0]); + Tree_FreePortals_r(node->children[1]); + } + + // free portals + for (p = node->portals; p; p = nextp) + { + s = (p->nodes[1] == node); + nextp = p->next[s]; + + RemovePortalFromNode (p, p->nodes[!s]); +#ifdef ME + if (p->winding) freedtreemem += MemorySize(p->winding); + freedtreemem += MemorySize(p); +#endif //ME + FreePortal(p); + } + node->portals = NULL; +} //end of the function Tree_FreePortals_r +//=========================================================================== +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +void Tree_Free_r (node_t *node) +{ +// face_t *f, *nextf; + bspbrush_t *brush, *nextbrush; + + //free children + if (node->planenum != PLANENUM_LEAF) + { + Tree_Free_r (node->children[0]); + Tree_Free_r (node->children[1]); + } //end if + //free bspbrushes +// FreeBrushList (node->brushlist); + for (brush = node->brushlist; brush; brush = nextbrush) + { + nextbrush = brush->next; +#ifdef ME + freedtreemem += MemorySize(brush); +#endif //ME + FreeBrush(brush); + } //end for + node->brushlist = NULL; + + /* + NOTE: only used when creating Q2 bsp + // free faces + for (f = node->faces; f; f = nextf) + { + nextf = f->next; +#ifdef ME + if (f->w) freedtreemem += MemorySize(f->w); + freedtreemem += sizeof(face_t); +#endif //ME + FreeFace(f); + } //end for + */ + + // free the node + if (node->volume) + { +#ifdef ME + freedtreemem += MemorySize(node->volume); +#endif //ME + FreeBrush (node->volume); + } //end if + + if (numthreads == 1) c_nodes--; +#ifdef ME + freedtreemem += MemorySize(node); +#endif //ME + FreeMemory(node); +} //end of the function Tree_Free_r +//=========================================================================== +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +void Tree_Free(tree_t *tree) +{ + //if no tree just return + if (!tree) return; + // + freedtreemem = 0; + // + Tree_FreePortals_r(tree->headnode); + Tree_Free_r(tree->headnode); +#ifdef ME + freedtreemem += MemorySize(tree); +#endif //ME + FreeMemory(tree); +#ifdef ME + Log_Print("freed "); + PrintMemorySize(freedtreemem); + Log_Print(" of tree memory\n"); +#endif //ME +} //end of the function Tree_Free +//=========================================================================== +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +tree_t *Tree_Alloc(void) +{ + tree_t *tree; + + tree = GetMemory(sizeof(*tree)); + memset (tree, 0, sizeof(*tree)); + ClearBounds (tree->mins, tree->maxs); + + return tree; +} //end of the function Tree_Alloc +//=========================================================================== +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +void Tree_Print_r (node_t *node, int depth) +{ + int i; + plane_t *plane; + bspbrush_t *bb; + + for (i=0 ; i<depth ; i++) + printf (" "); + if (node->planenum == PLANENUM_LEAF) + { + if (!node->brushlist) + printf ("NULL\n"); + else + { + for (bb=node->brushlist ; bb ; bb=bb->next) + printf ("%i ", bb->original->brushnum); + printf ("\n"); + } + return; + } + + plane = &mapplanes[node->planenum]; + printf ("#%i (%5.2f %5.2f %5.2f):%5.2f\n", node->planenum, + plane->normal[0], plane->normal[1], plane->normal[2], + plane->dist); + Tree_Print_r (node->children[0], depth+1); + Tree_Print_r (node->children[1], depth+1); +} //end of the function Tree_Print_r +//=========================================================================== +// NODES THAT DON'T SEPERATE DIFFERENT CONTENTS CAN BE PRUNED +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +void Tree_PruneNodes_r (node_t *node) +{ + bspbrush_t *b, *next; + + if (node->planenum == PLANENUM_LEAF) return; + + Tree_PruneNodes_r (node->children[0]); + Tree_PruneNodes_r (node->children[1]); + + if (create_aas) + { + if ((node->children[0]->contents & CONTENTS_LADDER) || + (node->children[1]->contents & CONTENTS_LADDER)) return; + } + + if ((node->children[0]->contents & CONTENTS_SOLID) + && (node->children[1]->contents & CONTENTS_SOLID)) + { + if (node->faces) + Error ("node->faces seperating CONTENTS_SOLID"); + if (node->children[0]->faces || node->children[1]->faces) + Error ("!node->faces with children"); + // FIXME: free stuff + node->planenum = PLANENUM_LEAF; + node->contents = CONTENTS_SOLID; + node->detail_seperator = false; + + if (node->brushlist) + 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; + } //end for + //free the child nodes + FreeMemory(node->children[0]); + FreeMemory(node->children[1]); + //two nodes are cut away + c_pruned += 2; + } //end if +} //end of the function Tree_PruneNodes_r +//=========================================================================== +// +// Parameter: - +// Returns: - +// Changes Globals: - +//=========================================================================== +void Tree_PruneNodes(node_t *node) +{ + Log_Print("------- Prune Nodes --------\n"); + c_pruned = 0; + Tree_PruneNodes_r(node); + Log_Print("%5i pruned nodes\n", c_pruned); +} //end of the function Tree_PruneNodes |