tools/quake2/q2map/trace.c

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