tools/quake2/q2map/tree.c

   1 /*
   2    Copyright (C) 1999-2007 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         plane_t *plane;
  29         vec_t d;
  30
  31         while ( node->planenum != PLANENUM_LEAF )
  32         {
  33                 plane = &mapplanes[node->planenum];
  34                 d = DotProduct( origin, plane->normal ) - plane->dist;
  35                 if ( d >= 0 ) {
  36                         node = node->children[0];
  37                 }
  38                 else{
  39                         node = node->children[1];
  40                 }
  41         }
  42
  43         return node;
  44 }
  45
  46
  47
  48 /*
  49    =============
  50    FreeTreePortals_r
  51    =============
  52  */
  53 void FreeTreePortals_r( node_t *node ){
  54         portal_t    *p, *nextp;
  55         int s;
  56
  57         // free children
  58         if ( node->planenum != PLANENUM_LEAF ) {
  59                 FreeTreePortals_r( node->children[0] );
  60                 FreeTreePortals_r( node->children[1] );
  61         }
  62
  63         // free portals
  64         for ( p = node->portals ; p ; p = nextp )
  65         {
  66                 s = ( p->nodes[1] == node );
  67                 nextp = p->next[s];
  68
  69                 RemovePortalFromNode( p, p->nodes[!s] );
  70                 FreePortal( p );
  71         }
  72         node->portals = NULL;
  73 }
  74
  75 /*
  76    =============
  77    FreeTree_r
  78    =============
  79  */
  80 void FreeTree_r( node_t *node ){
  81         face_t      *f, *nextf;
  82
  83         // free children
  84         if ( node->planenum != PLANENUM_LEAF ) {
  85                 FreeTree_r( node->children[0] );
  86                 FreeTree_r( node->children[1] );
  87         }
  88
  89         // free bspbrushes
  90         FreeBrushList( node->brushlist );
  91
  92         // free faces
  93         for ( f = node->faces ; f ; f = nextf )
  94         {
  95                 nextf = f->next;
  96                 FreeFace( f );
  97         }
  98
  99         // free the node
 100         if ( node->volume ) {
 101                 FreeBrush( node->volume );
 102         }
 103
 104         if ( numthreads == 1 ) {
 105                 c_nodes--;
 106         }
 107         free( node );
 108 }
 109
 110
 111 /*
 112    =============
 113    FreeTree
 114    =============
 115  */
 116 void FreeTree( tree_t *tree ){
 117         FreeTreePortals_r( tree->headnode );
 118         FreeTree_r( tree->headnode );
 119         free( tree );
 120 }
 121
 122 //===============================================================
 123
 124 void PrintTree_r( node_t *node, int depth ){
 125         int i;
 126         plane_t *plane;
 127         bspbrush_t  *bb;
 128
 129         for ( i = 0 ; i < depth ; i++ )
 130                 Sys_Printf( "  " );
 131         if ( node->planenum == PLANENUM_LEAF ) {
 132                 if ( !node->brushlist ) {
 133                         Sys_Printf( "NULL\n" );
 134                 }
 135                 else
 136                 {
 137                         for ( bb = node->brushlist ; bb ; bb = bb->next )
 138                                 Sys_Printf( "%i ", bb->original->brushnum );
 139                         Sys_Printf( "\n" );
 140                 }
 141                 return;
 142         }
 143
 144         plane = &mapplanes[node->planenum];
 145         Sys_Printf( "#%i (%5.2f %5.2f %5.2f):%5.2f\n", node->planenum,
 146                                 plane->normal[0], plane->normal[1], plane->normal[2],
 147                                 plane->dist );
 148         PrintTree_r( node->children[0], depth + 1 );
 149         PrintTree_r( node->children[1], depth + 1 );
 150 }
 151
 152 /*
 153    =========================================================
 154
 155    NODES THAT DON'T SEPERATE DIFFERENT CONTENTS CAN BE PRUNED
 156
 157    =========================================================
 158  */
 159
 160 int c_pruned;
 161
 162 /*
 163    ============
 164    PruneNodes_r
 165    ============
 166  */
 167 void PruneNodes_r( node_t *node ){
 168         bspbrush_t      *b, *next;
 169
 170         if ( node->planenum == PLANENUM_LEAF ) {
 171                 return;
 172         }
 173         PruneNodes_r( node->children[0] );
 174         PruneNodes_r( node->children[1] );
 175
 176         if ( ( node->children[0]->contents & CONTENTS_SOLID )
 177                  && ( node->children[1]->contents & CONTENTS_SOLID ) ) {
 178                 if ( node->faces ) {
 179                         Error( "node->faces seperating CONTENTS_SOLID" );
 180                 }
 181                 if ( node->children[0]->faces || node->children[1]->faces ) {
 182                         Error( "!node->faces with children" );
 183                 }
 184
 185                 // FIXME: free stuff
 186                 node->planenum = PLANENUM_LEAF;
 187                 node->contents = CONTENTS_SOLID;
 188                 node->detail_seperator = false;
 189
 190                 if ( node->brushlist ) {
 191                         Error( "PruneNodes: node->brushlist" );
 192                 }
 193
 194                 // combine brush lists
 195                 node->brushlist = node->children[1]->brushlist;
 196
 197                 for ( b = node->children[0]->brushlist ; b ; b = next )
 198                 {
 199                         next = b->next;
 200                         b->next = node->brushlist;
 201                         node->brushlist = b;
 202                 }
 203
 204                 c_pruned++;
 205         }
 206 }
 207
 208
 209 void PruneNodes( node_t *node ){
 210         Sys_FPrintf( SYS_VRB, "--- PruneNodes ---\n" );
 211         c_pruned = 0;
 212         PruneNodes_r( node );
 213         Sys_FPrintf( SYS_VRB, "%5i pruned nodes\n", c_pruned );
 214 }
 215
 216 //===========================================================