tools/quake2/q2map/tree.c

   1 /*\r
   2 Copyright (C) 1999-2007 id Software, Inc. and contributors.\r
   3 For a list of contributors, see the accompanying CONTRIBUTORS file.\r
   4 \r
   5 This file is part of GtkRadiant.\r
   6 \r
   7 GtkRadiant is free software; you can redistribute it and/or modify\r
   8 it under the terms of the GNU General Public License as published by\r
   9 the Free Software Foundation; either version 2 of the License, or\r
  10 (at your option) any later version.\r
  11 \r
  12 GtkRadiant is distributed in the hope that it will be useful,\r
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
  15 GNU General Public License for more details.\r
  16 \r
  17 You should have received a copy of the GNU General Public License\r
  18 along with GtkRadiant; if not, write to the Free Software\r
  19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA\r
  20 */\r
  21 #include "qbsp.h"\r
  22 \r
  23 extern  int     c_nodes;\r
  24 \r
  25 void RemovePortalFromNode (portal_t *portal, node_t *l);\r
  26 \r
  27 node_t *NodeForPoint (node_t *node, vec3_t origin)\r
  28 {\r
  29         plane_t *plane;\r
  30         vec_t   d;\r
  31 \r
  32         while (node->planenum != PLANENUM_LEAF)\r
  33         {\r
  34                 plane = &mapplanes[node->planenum];\r
  35                 d = DotProduct (origin, plane->normal) - plane->dist;\r
  36                 if (d >= 0)\r
  37                         node = node->children[0];\r
  38                 else\r
  39                         node = node->children[1];\r
  40         }\r
  41 \r
  42         return node;\r
  43 }\r
  44 \r
  45 \r
  46 \r
  47 /*\r
  48 =============\r
  49 FreeTreePortals_r\r
  50 =============\r
  51 */\r
  52 void FreeTreePortals_r (node_t *node)\r
  53 {\r
  54         portal_t        *p, *nextp;\r
  55         int                     s;\r
  56 \r
  57         // free children\r
  58         if (node->planenum != PLANENUM_LEAF)\r
  59         {\r
  60                 FreeTreePortals_r (node->children[0]);\r
  61                 FreeTreePortals_r (node->children[1]);\r
  62         }\r
  63 \r
  64         // free portals\r
  65         for (p=node->portals ; p ; p=nextp)\r
  66         {\r
  67                 s = (p->nodes[1] == node);\r
  68                 nextp = p->next[s];\r
  69 \r
  70                 RemovePortalFromNode (p, p->nodes[!s]);\r
  71                 FreePortal (p);\r
  72         }\r
  73         node->portals = NULL;\r
  74 }\r
  75 \r
  76 /*\r
  77 =============\r
  78 FreeTree_r\r
  79 =============\r
  80 */\r
  81 void FreeTree_r (node_t *node)\r
  82 {\r
  83         face_t          *f, *nextf;\r
  84 \r
  85         // free children\r
  86         if (node->planenum != PLANENUM_LEAF)\r
  87         {\r
  88                 FreeTree_r (node->children[0]);\r
  89                 FreeTree_r (node->children[1]);\r
  90         }\r
  91 \r
  92         // free bspbrushes\r
  93         FreeBrushList (node->brushlist);\r
  94 \r
  95         // free faces\r
  96         for (f=node->faces ; f ; f=nextf)\r
  97         {\r
  98                 nextf = f->next;\r
  99                 FreeFace (f);\r
 100         }\r
 101 \r
 102         // free the node\r
 103         if (node->volume)\r
 104                 FreeBrush (node->volume);\r
 105 \r
 106         if (numthreads == 1)\r
 107                 c_nodes--;\r
 108         free (node);\r
 109 }\r
 110 \r
 111 \r
 112 /*\r
 113 =============\r
 114 FreeTree\r
 115 =============\r
 116 */\r
 117 void FreeTree (tree_t *tree)\r
 118 {\r
 119         FreeTreePortals_r (tree->headnode);\r
 120         FreeTree_r (tree->headnode);\r
 121         free (tree);\r
 122 }\r
 123 \r
 124 //===============================================================\r
 125 \r
 126 void PrintTree_r (node_t *node, int depth)\r
 127 {\r
 128         int             i;\r
 129         plane_t *plane;\r
 130         bspbrush_t      *bb;\r
 131 \r
 132         for (i=0 ; i<depth ; i++)\r
 133                 Sys_Printf ("  ");\r
 134         if (node->planenum == PLANENUM_LEAF)\r
 135         {\r
 136                 if (!node->brushlist)\r
 137                         Sys_Printf ("NULL\n");\r
 138                 else\r
 139                 {\r
 140                         for (bb=node->brushlist ; bb ; bb=bb->next)\r
 141                                 Sys_Printf ("%i ", bb->original->brushnum);\r
 142                         Sys_Printf ("\n");\r
 143                 }\r
 144                 return;\r
 145         }\r
 146 \r
 147         plane = &mapplanes[node->planenum];\r
 148         Sys_Printf ("#%i (%5.2f %5.2f %5.2f):%5.2f\n", node->planenum,\r
 149                 plane->normal[0], plane->normal[1], plane->normal[2],\r
 150                 plane->dist);\r
 151         PrintTree_r (node->children[0], depth+1);\r
 152         PrintTree_r (node->children[1], depth+1);\r
 153 }\r
 154 \r
 155 /*\r
 156 =========================================================\r
 157 \r
 158 NODES THAT DON'T SEPERATE DIFFERENT CONTENTS CAN BE PRUNED\r
 159 \r
 160 =========================================================\r
 161 */\r
 162 \r
 163 int     c_pruned;\r
 164 \r
 165 /*\r
 166 ============\r
 167 PruneNodes_r\r
 168 ============\r
 169 */\r
 170 void PruneNodes_r (node_t *node)\r
 171 {\r
 172         bspbrush_t              *b, *next;\r
 173 \r
 174         if (node->planenum == PLANENUM_LEAF)\r
 175                 return;\r
 176         PruneNodes_r (node->children[0]);\r
 177         PruneNodes_r (node->children[1]);\r
 178 \r
 179         if ( (node->children[0]->contents & CONTENTS_SOLID)\r
 180         && (node->children[1]->contents & CONTENTS_SOLID) )\r
 181         {\r
 182                 if (node->faces)\r
 183                         Error ("node->faces seperating CONTENTS_SOLID");\r
 184                 if (node->children[0]->faces || node->children[1]->faces)\r
 185                         Error ("!node->faces with children");\r
 186 \r
 187                 // FIXME: free stuff\r
 188                 node->planenum = PLANENUM_LEAF;\r
 189                 node->contents = CONTENTS_SOLID;\r
 190                 node->detail_seperator = false;\r
 191 \r
 192                 if (node->brushlist)\r
 193                         Error ("PruneNodes: node->brushlist");\r
 194 \r
 195                 // combine brush lists\r
 196                 node->brushlist = node->children[1]->brushlist;\r
 197 \r
 198                 for (b=node->children[0]->brushlist ; b ; b=next)\r
 199                 {\r
 200                         next = b->next;\r
 201                         b->next = node->brushlist;\r
 202                         node->brushlist = b;\r
 203                 }\r
 204 \r
 205                 c_pruned++;\r
 206         }\r
 207 }\r
 208 \r
 209 \r
 210 void PruneNodes (node_t *node)\r
 211 {\r
 212         Sys_FPrintf( SYS_VRB, "--- PruneNodes ---\n");\r
 213         c_pruned = 0;\r
 214         PruneNodes_r (node);\r
 215         Sys_FPrintf( SYS_VRB, "%5i pruned nodes\n", c_pruned);\r
 216 }\r
 217 \r
 218 //===========================================================\r