diff options
Diffstat (limited to 'code/bspc/tree.c')
| -rwxr-xr-x | code/bspc/tree.c | 283 |
1 files changed, 283 insertions, 0 deletions
diff --git a/code/bspc/tree.c b/code/bspc/tree.c new file mode 100755 index 0000000..3d2ee9c --- /dev/null +++ b/code/bspc/tree.c @@ -0,0 +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
|