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 */
MakeTnode(int nodenum)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 */
MakeTnodes(dmodel_t * bm)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
TestLine_r(int node,vec3_t start,vec3_t stop)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
TestLine(vec3_t start,vec3_t stop)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 */
_TestLine(vec3_t start,vec3_t stop)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
296