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         plane_t *plane;
  46         vec_t d;
  47
  48         while ( node->planenum != PLANENUM_LEAF )
  49         {
  50                 plane = &mapplanes[node->planenum];
  51                 d = DotProduct( origin, plane->normal ) - plane->dist;
  52                 if ( d >= 0 ) {
  53                         node = node->children[0];
  54                 }
  55                 else{
  56                         node = node->children[1];
  57                 }
  58         }
  59
  60         return node;
  61 }
  62
  63
  64
  65 /*
  66    =============
  67    FreeTreePortals_r
  68    =============
  69  */
  70 void FreeTreePortals_r( node_t *node ){
  71         portal_t    *p, *nextp;
  72         int s;
  73
  74         // free children
  75         if ( node->planenum != PLANENUM_LEAF ) {
  76                 FreeTreePortals_r( node->children[0] );
  77                 FreeTreePortals_r( node->children[1] );
  78         }
  79
  80         // free portals
  81         for ( p = node->portals ; p ; p = nextp )
  82         {
  83                 s = ( p->nodes[1] == node );
  84                 nextp = p->next[s];
  85
  86                 RemovePortalFromNode( p, p->nodes[!s] );
  87                 FreePortal( p );
  88         }
  89         node->portals = NULL;
  90 }
  91
  92 /*
  93    =============
  94    FreeTree_r
  95    =============
  96  */
  97 void FreeTree_r( node_t *node ){
  98         // free children
  99         if ( node->planenum != PLANENUM_LEAF ) {
 100                 FreeTree_r( node->children[0] );
 101                 FreeTree_r( node->children[1] );
 102         }
 103
 104         // free bspbrushes
 105         FreeBrushList( node->brushlist );
 106
 107         // free the node
 108         if ( node->volume ) {
 109                 FreeBrush( node->volume );
 110         }
 111
 112         free( node );
 113 }
 114
 115
 116 /*
 117    =============
 118    FreeTree
 119    =============
 120  */
 121 void FreeTree( tree_t *tree ){
 122         FreeTreePortals_r( tree->headnode );
 123         FreeTree_r( tree->headnode );
 124         free( tree );
 125 }
 126
 127 //===============================================================
 128
 129 void PrintTree_r( node_t *node, int depth ){
 130         int i;
 131         plane_t *plane;
 132         brush_t *bb;
 133
 134         for ( i = 0 ; i < depth ; i++ )
 135                 Sys_Printf( "  " );
 136         if ( node->planenum == PLANENUM_LEAF ) {
 137                 if ( !node->brushlist ) {
 138                         Sys_Printf( "NULL\n" );
 139                 }
 140                 else
 141                 {
 142                         for ( bb = node->brushlist ; bb ; bb = bb->next )
 143                                 Sys_Printf( "%d ", bb->original->brushNum );
 144                         Sys_Printf( "\n" );
 145                 }
 146                 return;
 147         }
 148
 149         plane = &mapplanes[node->planenum];
 150         Sys_Printf( "#%d (%5.2f %5.2f %5.2f):%5.2f\n", node->planenum,
 151                                 plane->normal[0], plane->normal[1], plane->normal[2],
 152                                 plane->dist );
 153         PrintTree_r( node->children[0], depth + 1 );
 154         PrintTree_r( node->children[1], depth + 1 );
 155 }