tools/quake3/q3map2/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 ----------------------------------------------------------------------------------\r
  22 \r
  23 This code has been altered significantly from its original form, to support\r
  24 several games based on the Quake III Arena engine, in the form of "Q3Map2."\r
  25 \r
  26 ------------------------------------------------------------------------------- */\r
  27 \r
  28 \r
  29 \r
  30 /* marker */\r
  31 #define TREE_C\r
  32 \r
  33 \r
  34 \r
  35 /* dependencies */\r
  36 #include "q3map2.h"\r
  37 \r
  38 \r
  39 \r
  40 \r
  41 void RemovePortalFromNode (portal_t *portal, node_t *l);\r
  42 \r
  43 node_t *NodeForPoint (node_t *node, vec3_t origin)\r
  44 {\r
  45         plane_t *plane;\r
  46         vec_t   d;\r
  47 \r
  48         while (node->planenum != PLANENUM_LEAF)\r
  49         {\r
  50                 plane = &mapplanes[node->planenum];\r
  51                 d = DotProduct (origin, plane->normal) - plane->dist;\r
  52                 if (d >= 0)\r
  53                         node = node->children[0];\r
  54                 else\r
  55                         node = node->children[1];\r
  56         }\r
  57 \r
  58         return node;\r
  59 }\r
  60 \r
  61 \r
  62 \r
  63 /*\r
  64 =============\r
  65 FreeTreePortals_r\r
  66 =============\r
  67 */\r
  68 void FreeTreePortals_r (node_t *node)\r
  69 {\r
  70         portal_t        *p, *nextp;\r
  71         int                     s;\r
  72 \r
  73         // free children\r
  74         if (node->planenum != PLANENUM_LEAF)\r
  75         {\r
  76                 FreeTreePortals_r (node->children[0]);\r
  77                 FreeTreePortals_r (node->children[1]);\r
  78         }\r
  79 \r
  80         // free portals\r
  81         for (p=node->portals ; p ; p=nextp)\r
  82         {\r
  83                 s = (p->nodes[1] == node);\r
  84                 nextp = p->next[s];\r
  85 \r
  86                 RemovePortalFromNode (p, p->nodes[!s]);\r
  87                 FreePortal (p);\r
  88         }\r
  89         node->portals = NULL;\r
  90 }\r
  91 \r
  92 /*\r
  93 =============\r
  94 FreeTree_r\r
  95 =============\r
  96 */\r
  97 void FreeTree_r (node_t *node)\r
  98 {\r
  99         // free children\r
 100         if (node->planenum != PLANENUM_LEAF)\r
 101         {\r
 102                 FreeTree_r (node->children[0]);\r
 103                 FreeTree_r (node->children[1]);\r
 104         }\r
 105 \r
 106         // free bspbrushes\r
 107         FreeBrushList (node->brushlist);\r
 108 \r
 109         // free the node\r
 110         if (node->volume)\r
 111                 FreeBrush (node->volume);\r
 112 \r
 113         free (node);\r
 114 }\r
 115 \r
 116 \r
 117 /*\r
 118 =============\r
 119 FreeTree\r
 120 =============\r
 121 */\r
 122 void FreeTree (tree_t *tree)\r
 123 {\r
 124         FreeTreePortals_r (tree->headnode);\r
 125         FreeTree_r (tree->headnode);\r
 126         free (tree);\r
 127 }\r
 128 \r
 129 //===============================================================\r
 130 \r
 131 void PrintTree_r (node_t *node, int depth)\r
 132 {\r
 133         int             i;\r
 134         plane_t *plane;\r
 135         brush_t *bb;\r
 136 \r
 137         for (i=0 ; i<depth ; i++)\r
 138                 Sys_Printf ("  ");\r
 139         if (node->planenum == PLANENUM_LEAF)\r
 140         {\r
 141                 if (!node->brushlist)\r
 142                         Sys_Printf ("NULL\n");\r
 143                 else\r
 144                 {\r
 145                         for (bb=node->brushlist ; bb ; bb=bb->next)\r
 146                                 Sys_Printf ("%d ", bb->original->brushNum);\r
 147                         Sys_Printf ("\n");\r
 148                 }\r
 149                 return;\r
 150         }\r
 151 \r
 152         plane = &mapplanes[node->planenum];\r
 153         Sys_Printf ("#%d (%5.2f %5.2f %5.2f):%5.2f\n", node->planenum,\r
 154                 plane->normal[0], plane->normal[1], plane->normal[2],\r
 155                 plane->dist);\r
 156         PrintTree_r (node->children[0], depth+1);\r
 157         PrintTree_r (node->children[1], depth+1);\r
 158 }\r