tools/quake2/q2map/tree.c

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