1 /*
2 trace.c
3
4 (description)
5
6 Copyright (C) 1996-1997 Id Software, Inc.
7 Copyright (C) 2002 Colin Thompson
8
9 This program is free software; you can redistribute it and/or
10 modify it under the terms of the GNU General Public License
11 as published by the Free Software Foundation; either version 2
12 of the License, or (at your option) any later version.
13
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
17
18 See the GNU General Public License for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to:
22
23 Free Software Foundation, Inc.
24 59 Temple Place - Suite 330
25 Boston, MA 02111-1307, USA
26
27 */
28 #ifdef HAVE_CONFIG_H
29 # include "config.h"
30 #endif
31
32 #ifdef HAVE_UNISTD_H
33 # include <unistd.h>
34 #endif
35 #ifdef HAVE_IO_H
36 # include <io.h>
37 #endif
38 #ifdef HAVE_STRING_H
39 # include <string.h>
40 #endif
41 #ifdef HAVE_STRINGS_H
42 # include <strings.h>
43 #endif
44 #include <stdlib.h>
45
46 #include "QF/bspfile.h"
47 #include "QF/mathlib.h"
48 #include "QF/qtypes.h"
49 #include "QF/dstring.h"
50 #include "QF/quakefs.h"
51 #include "QF/sys.h"
52 #include "light.h"
53
54 typedef struct {
55 int type;
56 vec3_t normal;
57 float dist;
58 int children[2];
59 int pad;
60 } tnode_t;
61
62 typedef struct {
63 vec3_t backpt;
64 int side;
65 int node;
66 } tracestack_t;
67
68 tnode_t *tnodes, *tnode_p;
69
70 /*
71 LINE TRACING
72
73 The major lighting operation is a point to point visibility test, performed
74 by recursive subdivision of the line by the BSP tree.
75 */
76
77
78 /*
79 MakeTnode
80
81 Converts the disk node structure into the efficient tracing structure
82 */
83 static void
MakeTnode(int nodenum)84 MakeTnode (int nodenum)
85 {
86 dnode_t *node;
87 dplane_t *plane;
88 int i;
89 tnode_t *t;
90
91 t = tnode_p++;
92
93 node = bsp->nodes + nodenum;
94 plane = bsp->planes + node->planenum;
95
96 t->type = plane->type;
97 VectorCopy (plane->normal, t->normal);
98 t->dist = plane->dist;
99
100 for (i = 0; i < 2; i++) {
101 if (node->children[i] < 0)
102 t->children[i] = bsp->leafs[-node->children[i] - 1].contents;
103 else {
104 t->children[i] = tnode_p - tnodes;
105 MakeTnode (node->children[i]);
106 }
107 }
108 }
109
110 /*
111 MakeTnodes
112
113 Loads the node structure out of a .bsp file to be used for light occlusion
114 */
115 void
MakeTnodes(dmodel_t * bm)116 MakeTnodes (dmodel_t *bm)
117 {
118 tnode_p = tnodes = malloc (bsp->numnodes * sizeof (tnode_t));
119
120 MakeTnode (0);
121 }
122
123 /* LordHavoc: this function operates by doing depth-first front-to-back
124 recursion through the BSP tree, checking at every split for a empty to
125 solid transition (impact) in the children, and returns false if one is
126 found.
127 note: 'no impact' does not mean it is empty, it occurs when there is no
128 transition from empty to solid; all solid or a transition from solid to
129 empty are not considered impacts. (this does mean that tracing is not
130 symmetrical; point A to point B may have different results than point B to
131 point A, if either start in solid)
132 */
133
134 #define TESTLINESTATE_BLOCKED 0
135 #define TESTLINESTATE_EMPTY 1
136 #define TESTLINESTATE_SOLID 2
137
138 qboolean
TestLine(lightinfo_t * l,vec3_t start,vec3_t end)139 TestLine (lightinfo_t *l, vec3_t start, vec3_t end)
140 {
141 vec_t front, back;
142 vec3_t frontpt, backpt;
143 int node, side, empty;
144 tracestack_t *tstack;
145 tracestack_t tracestack[64];
146 tnode_t *tnode;
147
148 VectorCopy (start, frontpt);
149 VectorCopy (end, backpt);
150
151 tstack = tracestack;
152 node = 0;
153 empty = 0;
154
155 while (1) {
156 while (node < 0) {
157 if (node != CONTENTS_SOLID)
158 empty = 1;
159 else if (empty) {
160 // DONE!
161 VectorCopy (backpt, l->testlineimpact);
162 return false;
163 }
164
165 // pop up the stack for a back side
166 if (tstack-- == tracestack)
167 return true;
168
169 // set the hit point for this plane
170 VectorCopy (backpt, frontpt);
171
172 // go down the back side
173 VectorCopy (tstack->backpt, backpt);
174
175 node = tnodes[tstack->node].children[tstack->side ^ 1];
176 }
177
178 tnode = &tnodes[node];
179
180 if (tnode->type < 3) {
181 front = frontpt[tnode->type] - tnode->dist;
182 back = backpt[tnode->type] - tnode->dist;
183 } else {
184 front = DotProduct (tnode->normal, frontpt) - tnode->dist;
185 back = DotProduct (tnode->normal, backpt) - tnode->dist;
186 }
187
188 if (front >= 0 && back >= 0) {
189 node = tnode->children[0];
190 continue;
191 }
192
193 if (front < 0 && back < 0) {
194 node = tnode->children[1];
195 continue;
196 }
197
198 side = front < 0;
199
200 front = front / (front - back);
201
202 tstack->node = node;
203 tstack->side = side;
204 VectorCopy (backpt, tstack->backpt);
205
206 tstack++;
207
208 backpt[0] = frontpt[0] + front * (backpt[0] - frontpt[0]);
209 backpt[1] = frontpt[1] + front * (backpt[1] - frontpt[1]);
210 backpt[2] = frontpt[2] + front * (backpt[2] - frontpt[2]);
211
212 node = tnode->children[side];
213 }
214 }
215