tools/quake2/extra/bsp/qrad3/trace.c

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