Main Page | Class Hierarchy | Alphabetical List | Data Structures | Directories | File List | Data Fields | Globals
code / bspc

tree.c File Reference

#include "qbsp.h"

Include dependency graph for tree.c:

Include dependency graph

Go to the source code of this file.

Functions

node_t * NodeForPoint (node_t *node, vec3_t origin)
void RemovePortalFromNode (portal_t *portal, node_t *l)
tree_t * Tree_Alloc (void)
void Tree_Free (tree_t *tree)
void Tree_Free_r (node_t *node)
void Tree_FreePortals_r (node_t *node)
void Tree_Print_r (node_t *node, int depth)
void Tree_PruneNodes (node_t *node)
void Tree_PruneNodes_r (node_t *node)

Variables

int c_nodes
int c_pruned
int freedtreemem = 0

Function Documentation

node_t* NodeForPoint (  node_t *  node,
vec3_t  origin
) 
 

Definition at line 37 of file tree.c.

References node_s::children, d, plane_t::dist, DotProduct, mapplanes, node_t, plane_t::normal, node_s::planenum, and vec_t.

00038 {
00039     plane_t *plane;
00040     vec_t   d;
00041 
00042     while (node->planenum != PLANENUM_LEAF)
00043     {
00044         plane = &mapplanes[node->planenum];
00045         d = DotProduct (origin, plane->normal) - plane->dist;
00046         if (d >= 0)
00047             node = node->children[0];
00048         else
00049             node = node->children[1];
00050     }
00051     return node;
00052 } //end of the function NodeForPoint

void RemovePortalFromNode (  portal_t *  portal,
node_t *  l
) 
 

Definition at line 211 of file portals.c.

00212 {
00213     portal_t    **pp, *t;
00214 
00215     int s, i, n;
00216     portal_t *p;
00217     portal_t *portals[4096];
00218     
00219 // remove reference to the current portal
00220     pp = &l->portals;
00221     while (1)
00222     {
00223         t = *pp;
00224         if (!t)
00225             Error ("RemovePortalFromNode: portal not in leaf"); 
00226 
00227         if ( t == portal )
00228             break;
00229 
00230         if (t->nodes[0] == l)
00231             pp = &t->next[0];
00232         else if (t->nodes[1] == l)
00233             pp = &t->next[1];
00234         else
00235             Error ("RemovePortalFromNode: portal not bounding leaf");
00236     }
00237     
00238     if (portal->nodes[0] == l)
00239     {
00240         *pp = portal->next[0];
00241         portal->nodes[0] = NULL;
00242     } //end if
00243     else if (portal->nodes[1] == l)
00244     {
00245         *pp = portal->next[1];  
00246         portal->nodes[1] = NULL;
00247     } //end else if
00248     else
00249     {
00250         Error("RemovePortalFromNode: mislinked portal");
00251     } //end else
00252 //#ifdef ME
00253     n = 0;
00254     for (p = l->portals; p; p = p->next[s])
00255     {
00256         for (i = 0; i < n; i++)
00257         {
00258             if (p == portals[i]) Error("RemovePortalFromNode: circular linked\n");
00259         } //end for
00260         if (p->nodes[0] != l && p->nodes[1] != l)
00261         {
00262             Error("RemovePortalFromNodes: portal does not belong to node\n");
00263         } //end if
00264         portals[n] = p;
00265         s = (p->nodes[1] == l);
00266 //      if (++n >= 4096) Error("RemovePortalFromNode: more than 4096 portals\n");
00267     } //end for
00268 //#endif
00269 } //end of the function RemovePortalFromNode

tree_t* Tree_Alloc (  void   ) 
 

Definition at line 175 of file tree.c.

References ClearBounds(), GetMemory(), memset(), and tree().

Referenced by BrushBSP(), and ProcessWorldBrushes().

00176 {
00177     tree_t  *tree;
00178 
00179     tree = GetMemory(sizeof(*tree));
00180     memset (tree, 0, sizeof(*tree));
00181     ClearBounds (tree->mins, tree->maxs);
00182 
00183     return tree;
00184 } //end of the function Tree_Alloc

Here is the call graph for this function:

void Tree_Free (  tree_t *  tree  ) 
 

Definition at line 150 of file tree.c.

References freedtreemem, FreeMemory(), Log_Print(), MemorySize(), PrintMemorySize(), tree(), Tree_Free_r(), and Tree_FreePortals_r().

Referenced by AAS_Create().

00151 {
00152     //if no tree just return
00153     if (!tree) return;
00154     //
00155     freedtreemem = 0;
00156     //
00157     Tree_FreePortals_r(tree->headnode);
00158     Tree_Free_r(tree->headnode);
00159 #ifdef ME
00160     freedtreemem += MemorySize(tree);
00161 #endif //ME
00162     FreeMemory(tree);
00163 #ifdef ME
00164     Log_Print("freed ");
00165     PrintMemorySize(freedtreemem);
00166     Log_Print(" of tree memory\n");
00167 #endif //ME
00168 } //end of the function Tree_Free

Here is the call graph for this function:

void Tree_Free_r (  node_t *  node  ) 
 

Definition at line 92 of file tree.c.

References node_s::brushlist, bspbrush_t, c_nodes, node_s::children, FreeBrush(), freedtreemem, FreeMemory(), MemorySize(), bspbrush_s::next, node_t, numthreads, node_s::planenum, and node_s::volume.

Referenced by Tree_Free().

00093 {
00094 //  face_t *f, *nextf;
00095     bspbrush_t *brush, *nextbrush;
00096 
00097     //free children
00098     if (node->planenum != PLANENUM_LEAF)
00099     {
00100         Tree_Free_r (node->children[0]);
00101         Tree_Free_r (node->children[1]);
00102     } //end if
00103     //free bspbrushes
00104 //  FreeBrushList (node->brushlist);
00105     for (brush = node->brushlist; brush; brush = nextbrush)
00106     {
00107         nextbrush = brush->next;
00108 #ifdef ME
00109         freedtreemem += MemorySize(brush);
00110 #endif //ME
00111         FreeBrush(brush);
00112     } //end for
00113     node->brushlist = NULL;
00114 
00115     /*
00116     NOTE: only used when creating Q2 bsp
00117     // free faces
00118     for (f = node->faces; f; f = nextf)
00119     {
00120         nextf = f->next;
00121 #ifdef ME
00122         if (f->w) freedtreemem += MemorySize(f->w);
00123         freedtreemem += sizeof(face_t);
00124 #endif //ME
00125         FreeFace(f);
00126     } //end for
00127     */
00128 
00129     // free the node
00130     if (node->volume)
00131     {
00132 #ifdef ME
00133         freedtreemem += MemorySize(node->volume);
00134 #endif //ME
00135         FreeBrush (node->volume);
00136     } //end if
00137 
00138     if (numthreads == 1) c_nodes--;
00139 #ifdef ME
00140     freedtreemem += MemorySize(node);
00141 #endif //ME
00142     FreeMemory(node);
00143 } //end of the function Tree_Free_r

Here is the call graph for this function:

void Tree_FreePortals_r (  node_t *  node  ) 
 

Definition at line 59 of file tree.c.

References node_s::children, freedtreemem, FreePortal(), MemorySize(), portal_s::next, node_t, portal_s::nodes, p, node_s::planenum, portal_t, node_s::portals, RemovePortalFromNode(), s, and portal_s::winding.

Referenced by Tree_Free(), and WritePortalFile().

00060 {
00061     portal_t    *p, *nextp;
00062     int         s;
00063 
00064     // free children
00065     if (node->planenum != PLANENUM_LEAF)
00066     {
00067         Tree_FreePortals_r(node->children[0]);
00068         Tree_FreePortals_r(node->children[1]);
00069     }
00070 
00071     // free portals
00072     for (p = node->portals; p; p = nextp)
00073     {
00074         s = (p->nodes[1] == node);
00075         nextp = p->next[s];
00076 
00077         RemovePortalFromNode (p, p->nodes[!s]);
00078 #ifdef ME
00079         if (p->winding) freedtreemem += MemorySize(p->winding);
00080         freedtreemem += MemorySize(p);
00081 #endif //ME
00082         FreePortal(p);
00083     }
00084     node->portals = NULL;
00085 } //end of the function Tree_FreePortals_r

Here is the call graph for this function:

void Tree_Print_r (  node_t *  node,
int  depth
) 
 

Definition at line 191 of file tree.c.

References node_s::brushlist, mapbrush_s::brushnum, bspbrush_t, node_s::children, plane_t::dist, i, mapplanes, bspbrush_s::next, node_t, plane_t::normal, bspbrush_s::original, node_s::planenum, and printf().

00192 {
00193     int     i;
00194     plane_t *plane;
00195     bspbrush_t  *bb;
00196 
00197     for (i=0 ; i<depth ; i++)
00198         printf ("  ");
00199     if (node->planenum == PLANENUM_LEAF)
00200     {
00201         if (!node->brushlist)
00202             printf ("NULL\n");
00203         else
00204         {
00205             for (bb=node->brushlist ; bb ; bb=bb->next)
00206                 printf ("%i ", bb->original->brushnum);
00207             printf ("\n");
00208         }
00209         return;
00210     }
00211 
00212     plane = &mapplanes[node->planenum];
00213     printf ("#%i (%5.2f %5.2f %5.2f):%5.2f\n", node->planenum,
00214         plane->normal[0], plane->normal[1], plane->normal[2],
00215         plane->dist);
00216     Tree_Print_r (node->children[0], depth+1);
00217     Tree_Print_r (node->children[1], depth+1);
00218 } //end of the function Tree_Print_r

Here is the call graph for this function:

void Tree_PruneNodes (  node_t *  node  ) 
 

Definition at line 277 of file tree.c.

References c_pruned, Log_Print(), node_t, and Tree_PruneNodes_r().

Referenced by AAS_Create().

00278 {
00279     Log_Print("------- Prune Nodes --------\n");
00280     c_pruned = 0;
00281     Tree_PruneNodes_r(node);
00282     Log_Print("%5i pruned nodes\n", c_pruned);
00283 } //end of the function Tree_PruneNodes

Here is the call graph for this function:

void Tree_PruneNodes_r (  node_t *  node  ) 
 

Definition at line 226 of file tree.c.

References b, node_s::brushlist, bspbrush_t, c_pruned, node_s::children, node_s::contents, node_s::detail_seperator, Error(), node_s::faces, FreeMemory(), bspbrush_s::next, next, node_t, and node_s::planenum.

Referenced by Tree_PruneNodes().

00227 {
00228     bspbrush_t *b, *next;
00229 
00230     if (node->planenum == PLANENUM_LEAF) return;
00231 
00232     Tree_PruneNodes_r (node->children[0]);
00233     Tree_PruneNodes_r (node->children[1]);
00234 
00235     if (create_aas)
00236     {
00237         if ((node->children[0]->contents & CONTENTS_LADDER) ||
00238                 (node->children[1]->contents & CONTENTS_LADDER)) return;
00239     }
00240 
00241     if ((node->children[0]->contents & CONTENTS_SOLID)
00242         && (node->children[1]->contents & CONTENTS_SOLID))
00243     {
00244         if (node->faces)
00245             Error ("node->faces seperating CONTENTS_SOLID");
00246         if (node->children[0]->faces || node->children[1]->faces)
00247             Error ("!node->faces with children");
00248         // FIXME: free stuff
00249         node->planenum = PLANENUM_LEAF;
00250         node->contents = CONTENTS_SOLID;
00251         node->detail_seperator = false;
00252 
00253         if (node->brushlist)
00254             Error ("PruneNodes: node->brushlist");
00255         // combine brush lists
00256         node->brushlist = node->children[1]->brushlist;
00257 
00258         for (b = node->children[0]->brushlist; b; b = next)
00259         {
00260             next = b->next;
00261             b->next = node->brushlist;
00262             node->brushlist = b;
00263         } //end for
00264         //free the child nodes
00265         FreeMemory(node->children[0]);
00266         FreeMemory(node->children[1]);
00267         //two nodes are cut away
00268         c_pruned += 2;
00269     } //end if
00270 } //end of the function Tree_PruneNodes_r

Here is the call graph for this function:

Variable Documentation

int c_nodes
 

Definition at line 50 of file brushbsp.c.

int c_pruned
 

Definition at line 26 of file tree.c.

Referenced by Tree_PruneNodes(), and Tree_PruneNodes_r().

int freedtreemem = 0
 

Definition at line 27 of file tree.c.

Referenced by Tree_Free(), Tree_Free_r(), and Tree_FreePortals_r().

Generated on Thu Aug 25 13:09:36 2005 for Quake III Arena by  doxygen 1.3.9.1