tools/quake2/q2map/trace.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 // trace.c
  22 /*
  23    #include "cmdlib.h"
  24    #include "mathlib.h"
  25    #include "bspfile.h"
  26  */
  27
  28 #include "qrad.h"
  29
  30 #define ON_EPSILON  0.1
  31
  32 typedef struct tnode_s
  33 {
  34         int type;
  35         vec3_t normal;
  36         float dist;
  37         int children[2];
  38         int pad;
  39 } tnode_t;
  40
  41 tnode_t     *tnodes, *tnode_p;
  42
  43 /*
  44    ==============
  45    MakeTnode
  46
  47    Converts the disk node structure into the efficient tracing structure
  48    ==============
  49  */
  50 void MakeTnode( int nodenum ){
  51         tnode_t         *t;
  52         dplane_t        *plane;
  53         int i;
  54         dnode_t         *node;
  55
  56         t = tnode_p++;
  57
  58         node = dnodes + nodenum;
  59         plane = dplanes + node->planenum;
  60
  61         t->type = plane->type;
  62         VectorCopy( plane->normal, t->normal );
  63         t->dist = plane->dist;
  64
  65         for ( i = 0 ; i < 2 ; i++ )
  66         {
  67                 if ( node->children[i] < 0 ) {
  68                         t->children[i] = ( dleafs[-node->children[i] - 1].contents & CONTENTS_SOLID ) | ( 1 << 31 );
  69                 }
  70                 else
  71                 {
  72                         t->children[i] = tnode_p - tnodes;
  73                         MakeTnode( node->children[i] );
  74                 }
  75         }
  76
  77 }
  78
  79
  80 /*
  81    =============
  82    MakeTnodes
  83
  84    Loads the node structure out of a .bsp file to be used for light occlusion
  85    =============
  86  */
  87 void MakeTnodes( dmodel_t *bm ){
  88         // 32 byte align the structs
  89         tnodes = malloc( ( numnodes + 1 ) * sizeof( tnode_t ) );
  90         tnodes = (tnode_t *)( ( (int)tnodes + 31 ) & ~31 );
  91         tnode_p = tnodes;
  92
  93         MakeTnode( 0 );
  94 }
  95
  96
  97 //==========================================================
  98
  99
 100 int TestLine_r( int node, vec3_t start, vec3_t stop ){
 101         tnode_t *tnode;
 102         float front, back;
 103         vec3_t mid;
 104         float frac;
 105         int side;
 106         int r;
 107
 108         if ( node & ( 1 << 31 ) ) {
 109                 return node & ~( 1 << 31 ); // leaf node
 110
 111         }
 112         tnode = &tnodes[node];
 113         switch ( tnode->type )
 114         {
 115         case PLANE_X:
 116                 front = start[0] - tnode->dist;
 117                 back = stop[0] - tnode->dist;
 118                 break;
 119         case PLANE_Y:
 120                 front = start[1] - tnode->dist;
 121                 back = stop[1] - tnode->dist;
 122                 break;
 123         case PLANE_Z:
 124                 front = start[2] - tnode->dist;
 125                 back = stop[2] - tnode->dist;
 126                 break;
 127         default:
 128                 front = ( start[0] * tnode->normal[0] + start[1] * tnode->normal[1] + start[2] * tnode->normal[2] ) - tnode->dist;
 129                 back = ( stop[0] * tnode->normal[0] + stop[1] * tnode->normal[1] + stop[2] * tnode->normal[2] ) - tnode->dist;
 130                 break;
 131         }
 132
 133         if ( front >= -ON_EPSILON && back >= -ON_EPSILON ) {
 134                 return TestLine_r( tnode->children[0], start, stop );
 135         }
 136
 137         if ( front < ON_EPSILON && back < ON_EPSILON ) {
 138                 return TestLine_r( tnode->children[1], start, stop );
 139         }
 140
 141         side = front < 0;
 142
 143         frac = front / ( front - back );
 144
 145         mid[0] = start[0] + ( stop[0] - start[0] ) * frac;
 146         mid[1] = start[1] + ( stop[1] - start[1] ) * frac;
 147         mid[2] = start[2] + ( stop[2] - start[2] ) * frac;
 148
 149         r = TestLine_r( tnode->children[side], start, mid );
 150         if ( r ) {
 151                 return r;
 152         }
 153         return TestLine_r( tnode->children[!side], mid, stop );
 154 }
 155
 156 int TestLine( vec3_t start, vec3_t stop ){
 157         return TestLine_r( 0, start, stop );
 158 }
 159
 160 /*
 161    ==============================================================================
 162
 163    LINE TRACING
 164
 165    The major lighting operation is a point to point visibility test, performed
 166    by recursive subdivision of the line by the BSP tree.
 167
 168    ==============================================================================
 169  */
 170
 171 typedef struct
 172 {
 173         vec3_t backpt;
 174         int side;
 175         int node;
 176 } tracestack_t;
 177
 178
 179 /*
 180    ==============
 181    TestLine
 182    ==============
 183  */
 184 qboolean _TestLine( vec3_t start, vec3_t stop ){
 185         int node;
 186         float front, back;
 187         tracestack_t    *tstack_p;
 188         int side;
 189         float frontx,fronty, frontz, backx, backy, backz;
 190         tracestack_t tracestack[64];
 191         tnode_t         *tnode;
 192
 193         frontx = start[0];
 194         fronty = start[1];
 195         frontz = start[2];
 196         backx = stop[0];
 197         backy = stop[1];
 198         backz = stop[2];
 199
 200         tstack_p = tracestack;
 201         node = 0;
 202
 203         while ( 1 )
 204         {
 205                 if ( node == CONTENTS_SOLID ) {
 206 #if 0
 207                         float d1, d2, d3;
 208
 209                         d1 = backx - frontx;
 210                         d2 = backy - fronty;
 211                         d3 = backz - frontz;
 212
 213                         if ( d1 * d1 + d2 * d2 + d3 * d3 > 1 )
 214 #endif
 215                         return false;       // DONE!
 216                 }
 217
 218                 while ( node < 0 )
 219                 {
 220                         // pop up the stack for a back side
 221                         tstack_p--;
 222                         if ( tstack_p < tracestack ) {
 223                                 return true;
 224                         }
 225                         node = tstack_p->node;
 226
 227                         // set the hit point for this plane
 228
 229                         frontx = backx;
 230                         fronty = backy;
 231                         frontz = backz;
 232
 233                         // go down the back side
 234
 235                         backx = tstack_p->backpt[0];
 236                         backy = tstack_p->backpt[1];
 237                         backz = tstack_p->backpt[2];
 238
 239                         node = tnodes[tstack_p->node].children[!tstack_p->side];
 240                 }
 241
 242                 tnode = &tnodes[node];
 243
 244                 switch ( tnode->type )
 245                 {
 246                 case PLANE_X:
 247                         front = frontx - tnode->dist;
 248                         back = backx - tnode->dist;
 249                         break;
 250                 case PLANE_Y:
 251                         front = fronty - tnode->dist;
 252                         back = backy - tnode->dist;
 253                         break;
 254                 case PLANE_Z:
 255                         front = frontz - tnode->dist;
 256                         back = backz - tnode->dist;
 257                         break;
 258                 default:
 259                         front = ( frontx * tnode->normal[0] + fronty * tnode->normal[1] + frontz * tnode->normal[2] ) - tnode->dist;
 260                         back = ( backx * tnode->normal[0] + backy * tnode->normal[1] + backz * tnode->normal[2] ) - tnode->dist;
 261                         break;
 262                 }
 263
 264                 if ( front > -ON_EPSILON && back > -ON_EPSILON ) {
 265 //              if (front > 0 && back > 0)
 266                         node = tnode->children[0];
 267                         continue;
 268                 }
 269
 270                 if ( front < ON_EPSILON && back < ON_EPSILON ) {
 271 //              if (front <= 0 && back <= 0)
 272                         node = tnode->children[1];
 273                         continue;
 274                 }
 275
 276                 side = front < 0;
 277
 278                 front = front / ( front - back );
 279
 280                 tstack_p->node = node;
 281                 tstack_p->side = side;
 282                 tstack_p->backpt[0] = backx;
 283                 tstack_p->backpt[1] = backy;
 284                 tstack_p->backpt[2] = backz;
 285
 286                 tstack_p++;
 287
 288                 backx = frontx + front * ( backx - frontx );
 289                 backy = fronty + front * ( backy - fronty );
 290                 backz = frontz + front * ( backz - frontz );
 291
 292                 node = tnode->children[side];
 293         }
 294 }