Merge remote-tracking branch 'origin/divVerent/weird-shift-a'
[divverent/netradiant.git] / tools / quake3 / q3map2 / tree.c
1 /* -------------------------------------------------------------------------------
2
3 Copyright (C) 1999-2007 id Software, Inc. and contributors.
4 For a list of contributors, see the accompanying CONTRIBUTORS file.
5
6 This file is part of GtkRadiant.
7
8 GtkRadiant is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2 of the License, or
11 (at your option) any later version.
12
13 GtkRadiant is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GtkRadiant; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
21
22 ----------------------------------------------------------------------------------
23
24 This code has been altered significantly from its original form, to support
25 several games based on the Quake III Arena engine, in the form of "Q3Map2."
26
27 ------------------------------------------------------------------------------- */
28
29
30
31 /* marker */
32 #define TREE_C
33
34
35
36 /* dependencies */
37 #include "q3map2.h"
38
39
40
41
42 void RemovePortalFromNode (portal_t *portal, node_t *l);
43
44 node_t *NodeForPoint (node_t *node, vec3_t origin)
45 {
46         plane_t *plane;
47         vec_t   d;
48
49         while (node->planenum != PLANENUM_LEAF)
50         {
51                 plane = &mapplanes[node->planenum];
52                 d = DotProduct (origin, plane->normal) - plane->dist;
53                 if (d >= 0)
54                         node = node->children[0];
55                 else
56                         node = node->children[1];
57         }
58
59         return node;
60 }
61
62
63
64 /*
65 =============
66 FreeTreePortals_r
67 =============
68 */
69 void FreeTreePortals_r (node_t *node)
70 {
71         portal_t        *p, *nextp;
72         int                     s;
73
74         // free children
75         if (node->planenum != PLANENUM_LEAF)
76         {
77                 FreeTreePortals_r (node->children[0]);
78                 FreeTreePortals_r (node->children[1]);
79         }
80
81         // free portals
82         for (p=node->portals ; p ; p=nextp)
83         {
84                 s = (p->nodes[1] == node);
85                 nextp = p->next[s];
86
87                 RemovePortalFromNode (p, p->nodes[!s]);
88                 FreePortal (p);
89         }
90         node->portals = NULL;
91 }
92
93 /*
94 =============
95 FreeTree_r
96 =============
97 */
98 void FreeTree_r (node_t *node)
99 {
100         // free children
101         if (node->planenum != PLANENUM_LEAF)
102         {
103                 FreeTree_r (node->children[0]);
104                 FreeTree_r (node->children[1]);
105         }
106
107         // free bspbrushes
108         FreeBrushList (node->brushlist);
109
110         // free the node
111         if (node->volume)
112                 FreeBrush (node->volume);
113
114         free (node);
115 }
116
117
118 /*
119 =============
120 FreeTree
121 =============
122 */
123 void FreeTree (tree_t *tree)
124 {
125         FreeTreePortals_r (tree->headnode);
126         FreeTree_r (tree->headnode);
127         free (tree);
128 }
129
130 //===============================================================
131
132 void PrintTree_r (node_t *node, int depth)
133 {
134         int             i;
135         plane_t *plane;
136         brush_t *bb;
137
138         for (i=0 ; i<depth ; i++)
139                 Sys_Printf ("  ");
140         if (node->planenum == PLANENUM_LEAF)
141         {
142                 if (!node->brushlist)
143                         Sys_Printf ("NULL\n");
144                 else
145                 {
146                         for (bb=node->brushlist ; bb ; bb=bb->next)
147                                 Sys_Printf ("%d ", bb->original->brushNum);
148                         Sys_Printf ("\n");
149                 }
150                 return;
151         }
152
153         plane = &mapplanes[node->planenum];
154         Sys_Printf ("#%d (%5.2f %5.2f %5.2f):%5.2f\n", node->planenum,
155                 plane->normal[0], plane->normal[1], plane->normal[2],
156                 plane->dist);
157         PrintTree_r (node->children[0], depth+1);
158         PrintTree_r (node->children[1], depth+1);
159 }