tools/quake2/q2map/trace.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 // 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 {
  52         tnode_t                 *t;
  53         dplane_t                *plane;
  54         int                             i;
  55         dnode_t                 *node;
  56
  57         t = tnode_p++;
  58
  59         node = dnodes + nodenum;
  60         plane = dplanes + node->planenum;
  61
  62         t->type = plane->type;
  63         VectorCopy (plane->normal, t->normal);
  64         t->dist = plane->dist;
  65
  66         for (i=0 ; i<2 ; i++)
  67         {
  68                 if (node->children[i] < 0)
  69                         t->children[i] = (dleafs[-node->children[i] - 1].contents & CONTENTS_SOLID) | (1<<31);
  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 {
  89         // 32 byte align the structs
  90         tnodes = malloc( (numnodes+1) * sizeof(tnode_t));
  91         tnodes = (tnode_t *)(((int)tnodes + 31)&~31);
  92         tnode_p = tnodes;
  93
  94         MakeTnode (0);
  95 }
  96
  97
  98 //==========================================================
  99
 100
 101 int TestLine_r (int node, vec3_t start, vec3_t stop)
 102 {
 103         tnode_t *tnode;
 104         float   front, back;
 105         vec3_t  mid;
 106         float   frac;
 107         int             side;
 108         int             r;
 109
 110         if (node & (1<<31))
 111                 return node & ~(1<<31); // leaf node
 112
 113         tnode = &tnodes[node];
 114         switch (tnode->type)
 115         {
 116         case PLANE_X:
 117                 front = start[0] - tnode->dist;
 118                 back = stop[0] - tnode->dist;
 119                 break;
 120         case PLANE_Y:
 121                 front = start[1] - tnode->dist;
 122                 back = stop[1] - tnode->dist;
 123                 break;
 124         case PLANE_Z:
 125                 front = start[2] - tnode->dist;
 126                 back = stop[2] - tnode->dist;
 127                 break;
 128         default:
 129                 front = (start[0]*tnode->normal[0] + start[1]*tnode->normal[1] + start[2]*tnode->normal[2]) - tnode->dist;
 130                 back = (stop[0]*tnode->normal[0] + stop[1]*tnode->normal[1] + stop[2]*tnode->normal[2]) - tnode->dist;
 131                 break;
 132         }
 133
 134         if (front >= -ON_EPSILON && back >= -ON_EPSILON)
 135                 return TestLine_r (tnode->children[0], start, stop);
 136
 137         if (front < ON_EPSILON && back < ON_EPSILON)
 138                 return TestLine_r (tnode->children[1], start, stop);
 139
 140         side = front < 0;
 141
 142         frac = front / (front-back);
 143
 144         mid[0] = start[0] + (stop[0] - start[0])*frac;
 145         mid[1] = start[1] + (stop[1] - start[1])*frac;
 146         mid[2] = start[2] + (stop[2] - start[2])*frac;
 147
 148         r = TestLine_r (tnode->children[side], start, mid);
 149         if (r)
 150                 return r;
 151         return TestLine_r (tnode->children[!side], mid, stop);
 152 }
 153
 154 int TestLine (vec3_t start, vec3_t stop)
 155 {
 156         return TestLine_r (0, start, stop);
 157 }
 158
 159 /*
 160 ==============================================================================
 161
 162 LINE TRACING
 163
 164 The major lighting operation is a point to point visibility test, performed
 165 by recursive subdivision of the line by the BSP tree.
 166
 167 ==============================================================================
 168 */
 169
 170 typedef struct
 171 {
 172         vec3_t  backpt;
 173         int             side;
 174         int             node;
 175 } tracestack_t;
 176
 177
 178 /*
 179 ==============
 180 TestLine
 181 ==============
 182 */
 183 qboolean _TestLine (vec3_t start, vec3_t stop)
 184 {
 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                 {
 207 #if 0
 208                         float   d1, d2, d3;
 209
 210                         d1 = backx - frontx;
 211                         d2 = backy - fronty;
 212                         d3 = backz - frontz;
 213
 214                         if (d1*d1 + d2*d2 + d3*d3 > 1)
 215 #endif
 216                                 return false;   // DONE!
 217                 }
 218
 219                 while (node < 0)
 220                 {
 221                 // pop up the stack for a back side
 222                         tstack_p--;
 223                         if (tstack_p < tracestack)
 224                                 return true;
 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                 {
 267                         node = tnode->children[0];
 268                         continue;
 269                 }
 270
 271                 if (front < ON_EPSILON && back < ON_EPSILON)
 272 //              if (front <= 0 && back <= 0)
 273                 {
 274                         node = tnode->children[1];
 275                         continue;
 276                 }
 277
 278                 side = front < 0;
 279
 280                 front = front / (front-back);
 281
 282                 tstack_p->node = node;
 283                 tstack_p->side = side;
 284                 tstack_p->backpt[0] = backx;
 285                 tstack_p->backpt[1] = backy;
 286                 tstack_p->backpt[2] = backz;
 287
 288                 tstack_p++;
 289
 290                 backx = frontx + front*(backx-frontx);
 291                 backy = fronty + front*(backy-fronty);
 292                 backz = frontz + front*(backz-frontz);
 293
 294                 node = tnode->children[side];
 295         }
 296 }
 297
 298