tree.c (7508B)
1 /* 2 =========================================================================== 3 Copyright (C) 1999-2005 Id Software, Inc. 4 5 This file is part of Quake III Arena source code. 6 7 Quake III Arena source code is free software; you can redistribute it 8 and/or modify it under the terms of the GNU General Public License as 9 published by the Free Software Foundation; either version 2 of the License, 10 or (at your option) any later version. 11 12 Quake III Arena source code is distributed in the hope that it will be 13 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with Foobar; if not, write to the Free Software 19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 20 =========================================================================== 21 */ 22 23 #include "qbsp.h" 24 25 extern int c_nodes; 26 int c_pruned; 27 int freedtreemem = 0; 28 29 void RemovePortalFromNode (portal_t *portal, node_t *l); 30 31 //=========================================================================== 32 // 33 // Parameter: - 34 // Returns: - 35 // Changes Globals: - 36 //=========================================================================== 37 node_t *NodeForPoint (node_t *node, vec3_t origin) 38 { 39 plane_t *plane; 40 vec_t d; 41 42 while (node->planenum != PLANENUM_LEAF) 43 { 44 plane = &mapplanes[node->planenum]; 45 d = DotProduct (origin, plane->normal) - plane->dist; 46 if (d >= 0) 47 node = node->children[0]; 48 else 49 node = node->children[1]; 50 } 51 return node; 52 } //end of the function NodeForPoint 53 //=========================================================================== 54 // 55 // Parameter: - 56 // Returns: - 57 // Changes Globals: - 58 //=========================================================================== 59 void Tree_FreePortals_r (node_t *node) 60 { 61 portal_t *p, *nextp; 62 int s; 63 64 // free children 65 if (node->planenum != PLANENUM_LEAF) 66 { 67 Tree_FreePortals_r(node->children[0]); 68 Tree_FreePortals_r(node->children[1]); 69 } 70 71 // free portals 72 for (p = node->portals; p; p = nextp) 73 { 74 s = (p->nodes[1] == node); 75 nextp = p->next[s]; 76 77 RemovePortalFromNode (p, p->nodes[!s]); 78 #ifdef ME 79 if (p->winding) freedtreemem += MemorySize(p->winding); 80 freedtreemem += MemorySize(p); 81 #endif //ME 82 FreePortal(p); 83 } 84 node->portals = NULL; 85 } //end of the function Tree_FreePortals_r 86 //=========================================================================== 87 // 88 // Parameter: - 89 // Returns: - 90 // Changes Globals: - 91 //=========================================================================== 92 void Tree_Free_r (node_t *node) 93 { 94 // face_t *f, *nextf; 95 bspbrush_t *brush, *nextbrush; 96 97 //free children 98 if (node->planenum != PLANENUM_LEAF) 99 { 100 Tree_Free_r (node->children[0]); 101 Tree_Free_r (node->children[1]); 102 } //end if 103 //free bspbrushes 104 // FreeBrushList (node->brushlist); 105 for (brush = node->brushlist; brush; brush = nextbrush) 106 { 107 nextbrush = brush->next; 108 #ifdef ME 109 freedtreemem += MemorySize(brush); 110 #endif //ME 111 FreeBrush(brush); 112 } //end for 113 node->brushlist = NULL; 114 115 /* 116 NOTE: only used when creating Q2 bsp 117 // free faces 118 for (f = node->faces; f; f = nextf) 119 { 120 nextf = f->next; 121 #ifdef ME 122 if (f->w) freedtreemem += MemorySize(f->w); 123 freedtreemem += sizeof(face_t); 124 #endif //ME 125 FreeFace(f); 126 } //end for 127 */ 128 129 // free the node 130 if (node->volume) 131 { 132 #ifdef ME 133 freedtreemem += MemorySize(node->volume); 134 #endif //ME 135 FreeBrush (node->volume); 136 } //end if 137 138 if (numthreads == 1) c_nodes--; 139 #ifdef ME 140 freedtreemem += MemorySize(node); 141 #endif //ME 142 FreeMemory(node); 143 } //end of the function Tree_Free_r 144 //=========================================================================== 145 // 146 // Parameter: - 147 // Returns: - 148 // Changes Globals: - 149 //=========================================================================== 150 void Tree_Free(tree_t *tree) 151 { 152 //if no tree just return 153 if (!tree) return; 154 // 155 freedtreemem = 0; 156 // 157 Tree_FreePortals_r(tree->headnode); 158 Tree_Free_r(tree->headnode); 159 #ifdef ME 160 freedtreemem += MemorySize(tree); 161 #endif //ME 162 FreeMemory(tree); 163 #ifdef ME 164 Log_Print("freed "); 165 PrintMemorySize(freedtreemem); 166 Log_Print(" of tree memory\n"); 167 #endif //ME 168 } //end of the function Tree_Free 169 //=========================================================================== 170 // 171 // Parameter: - 172 // Returns: - 173 // Changes Globals: - 174 //=========================================================================== 175 tree_t *Tree_Alloc(void) 176 { 177 tree_t *tree; 178 179 tree = GetMemory(sizeof(*tree)); 180 memset (tree, 0, sizeof(*tree)); 181 ClearBounds (tree->mins, tree->maxs); 182 183 return tree; 184 } //end of the function Tree_Alloc 185 //=========================================================================== 186 // 187 // Parameter: - 188 // Returns: - 189 // Changes Globals: - 190 //=========================================================================== 191 void Tree_Print_r (node_t *node, int depth) 192 { 193 int i; 194 plane_t *plane; 195 bspbrush_t *bb; 196 197 for (i=0 ; i<depth ; i++) 198 printf (" "); 199 if (node->planenum == PLANENUM_LEAF) 200 { 201 if (!node->brushlist) 202 printf ("NULL\n"); 203 else 204 { 205 for (bb=node->brushlist ; bb ; bb=bb->next) 206 printf ("%i ", bb->original->brushnum); 207 printf ("\n"); 208 } 209 return; 210 } 211 212 plane = &mapplanes[node->planenum]; 213 printf ("#%i (%5.2f %5.2f %5.2f):%5.2f\n", node->planenum, 214 plane->normal[0], plane->normal[1], plane->normal[2], 215 plane->dist); 216 Tree_Print_r (node->children[0], depth+1); 217 Tree_Print_r (node->children[1], depth+1); 218 } //end of the function Tree_Print_r 219 //=========================================================================== 220 // NODES THAT DON'T SEPERATE DIFFERENT CONTENTS CAN BE PRUNED 221 // 222 // Parameter: - 223 // Returns: - 224 // Changes Globals: - 225 //=========================================================================== 226 void Tree_PruneNodes_r (node_t *node) 227 { 228 bspbrush_t *b, *next; 229 230 if (node->planenum == PLANENUM_LEAF) return; 231 232 Tree_PruneNodes_r (node->children[0]); 233 Tree_PruneNodes_r (node->children[1]); 234 235 if (create_aas) 236 { 237 if ((node->children[0]->contents & CONTENTS_LADDER) || 238 (node->children[1]->contents & CONTENTS_LADDER)) return; 239 } 240 241 if ((node->children[0]->contents & CONTENTS_SOLID) 242 && (node->children[1]->contents & CONTENTS_SOLID)) 243 { 244 if (node->faces) 245 Error ("node->faces seperating CONTENTS_SOLID"); 246 if (node->children[0]->faces || node->children[1]->faces) 247 Error ("!node->faces with children"); 248 // FIXME: free stuff 249 node->planenum = PLANENUM_LEAF; 250 node->contents = CONTENTS_SOLID; 251 node->detail_seperator = false; 252 253 if (node->brushlist) 254 Error ("PruneNodes: node->brushlist"); 255 // combine brush lists 256 node->brushlist = node->children[1]->brushlist; 257 258 for (b = node->children[0]->brushlist; b; b = next) 259 { 260 next = b->next; 261 b->next = node->brushlist; 262 node->brushlist = b; 263 } //end for 264 //free the child nodes 265 FreeMemory(node->children[0]); 266 FreeMemory(node->children[1]); 267 //two nodes are cut away 268 c_pruned += 2; 269 } //end if 270 } //end of the function Tree_PruneNodes_r 271 //=========================================================================== 272 // 273 // Parameter: - 274 // Returns: - 275 // Changes Globals: - 276 //=========================================================================== 277 void Tree_PruneNodes(node_t *node) 278 { 279 Log_Print("------- Prune Nodes --------\n"); 280 c_pruned = 0; 281 Tree_PruneNodes_r(node); 282 Log_Print("%5i pruned nodes\n", c_pruned); 283 } //end of the function Tree_PruneNodes