2 Copyright (C) 1999-2007 id Software, Inc. and contributors.
\r
3 For a list of contributors, see the accompanying CONTRIBUTORS file.
\r
5 This file is part of GtkRadiant.
\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
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
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
24 #include "mathlib.h"
\r
25 #include "bspfile.h"
\r
30 #define ON_EPSILON 0.1
\r
32 typedef struct tnode_s
\r
41 tnode_t *tnodes, *tnode_p;
\r
47 Converts the disk node structure into the efficient tracing structure
\r
50 void MakeTnode (int nodenum)
\r
59 node = dnodes + nodenum;
\r
60 plane = dplanes + node->planenum;
\r
62 t->type = plane->type;
\r
63 VectorCopy (plane->normal, t->normal);
\r
64 t->dist = plane->dist;
\r
66 for (i=0 ; i<2 ; i++)
\r
68 if (node->children[i] < 0)
\r
69 t->children[i] = (dleafs[-node->children[i] - 1].contents & CONTENTS_SOLID) | (1<<31);
\r
72 t->children[i] = tnode_p - tnodes;
\r
73 MakeTnode (node->children[i]);
\r
84 Loads the node structure out of a .bsp file to be used for light occlusion
\r
87 void MakeTnodes (dmodel_t *bm)
\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
98 //==========================================================
\r
101 int TestLine_r (int node, vec3_t start, vec3_t stop)
\r
110 if (node & (1<<31))
\r
111 return node & ~(1<<31); // leaf node
\r
113 tnode = &tnodes[node];
\r
114 switch (tnode->type)
\r
117 front = start[0] - tnode->dist;
\r
118 back = stop[0] - tnode->dist;
\r
121 front = start[1] - tnode->dist;
\r
122 back = stop[1] - tnode->dist;
\r
125 front = start[2] - tnode->dist;
\r
126 back = stop[2] - tnode->dist;
\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
134 if (front >= -ON_EPSILON && back >= -ON_EPSILON)
\r
135 return TestLine_r (tnode->children[0], start, stop);
\r
137 if (front < ON_EPSILON && back < ON_EPSILON)
\r
138 return TestLine_r (tnode->children[1], start, stop);
\r
142 frac = front / (front-back);
\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
148 r = TestLine_r (tnode->children[side], start, mid);
\r
151 return TestLine_r (tnode->children[!side], mid, stop);
\r
154 int TestLine (vec3_t start, vec3_t stop)
\r
156 return TestLine_r (0, start, stop);
\r
160 ==============================================================================
\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
167 ==============================================================================
\r
183 qboolean _TestLine (vec3_t start, vec3_t stop)
\r
187 tracestack_t *tstack_p;
\r
189 float frontx,fronty, frontz, backx, backy, backz;
\r
190 tracestack_t tracestack[64];
\r
200 tstack_p = tracestack;
\r
205 if (node == CONTENTS_SOLID)
\r
210 d1 = backx - frontx;
\r
211 d2 = backy - fronty;
\r
212 d3 = backz - frontz;
\r
214 if (d1*d1 + d2*d2 + d3*d3 > 1)
\r
216 return false; // DONE!
\r
221 // pop up the stack for a back side
\r
223 if (tstack_p < tracestack)
\r
225 node = tstack_p->node;
\r
227 // set the hit point for this plane
\r
233 // go down the back side
\r
235 backx = tstack_p->backpt[0];
\r
236 backy = tstack_p->backpt[1];
\r
237 backz = tstack_p->backpt[2];
\r
239 node = tnodes[tstack_p->node].children[!tstack_p->side];
\r
242 tnode = &tnodes[node];
\r
244 switch (tnode->type)
\r
247 front = frontx - tnode->dist;
\r
248 back = backx - tnode->dist;
\r
251 front = fronty - tnode->dist;
\r
252 back = backy - tnode->dist;
\r
255 front = frontz - tnode->dist;
\r
256 back = backz - tnode->dist;
\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
264 if (front > -ON_EPSILON && back > -ON_EPSILON)
\r
265 // if (front > 0 && back > 0)
\r
267 node = tnode->children[0];
\r
271 if (front < ON_EPSILON && back < ON_EPSILON)
\r
272 // if (front <= 0 && back <= 0)
\r
274 node = tnode->children[1];
\r
280 front = front / (front-back);
\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
290 backx = frontx + front*(backx-frontx);
\r
291 backy = fronty + front*(backy-fronty);
\r
292 backz = frontz + front*(backz-frontz);
\r
294 node = tnode->children[side];
\r