1 /*
2 trace.c
3
4 BSP line tracing
5
6 Copyright (C) 2004 Bill Currie
7
8 Author: Bill Currie <bill@taniwha.org>
9 Date: 2004/9/25
10
11 This program is free software; you can redistribute it and/or
12 modify it under the terms of the GNU General Public License
13 as published by the Free Software Foundation; either version 2
14 of the License, or (at your option) any later version.
15
16 This program is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
19
20 See the GNU General Public License for more details.
21
22 You should have received a copy of the GNU General Public License
23 along with this program; if not, write to:
24
25 Free Software Foundation, Inc.
26 59 Temple Place - Suite 330
27 Boston, MA 02111-1307, USA
28
29 */
30 #ifdef HAVE_CONFIG_H
31 # include "config.h"
32 #endif
33
34 #ifdef HAVE_STRING_H
35 # include <string.h>
36 #endif
37 #ifdef HAVE_STRINGS_H
38 # include <strings.h>
39 #endif
40
41 #include "QF/model.h"
42 #include "QF/sys.h"
43
44 #include "compat.h"
45 #include "world.h"
46
47 /* LINE TESTING IN HULLS */
48
49 // 1/32 epsilon to keep floating point happy
50 #ifndef DIST_EPSILON
51 #define DIST_EPSILON (0.03125)
52 #endif
53
54 typedef struct {
55 vec3_t end;
56 int side;
57 int num;
58 mplane_t *plane;
59 } tracestack_t;
60
61 static inline void
calc_impact(trace_t * trace,const vec3_t start,const vec3_t end,mplane_t * plane)62 calc_impact (trace_t *trace, const vec3_t start, const vec3_t end,
63 mplane_t *plane)
64 {
65 vec_t t1, t2, frac;
66 vec3_t dist;
67
68 t1 = PlaneDiff (start, plane);
69 t2 = PlaneDiff (end, plane);
70
71 if (t1 < 0) {
72 frac = (t1 + DIST_EPSILON) / (t1 - t2);
73 // invert plane paramterers
74 VectorNegate (plane->normal, trace->plane.normal);
75 trace->plane.dist = -plane->dist;
76 } else {
77 frac = (t1 - DIST_EPSILON) / (t1 - t2);
78 VectorCopy (plane->normal, trace->plane.normal);
79 trace->plane.dist = plane->dist;
80 }
81 frac = bound (0, frac, 1);
82 trace->fraction = frac;
83 VectorSubtract (end, start, dist);
84 VectorMultAdd (start, frac, dist, trace->endpos);
85 }
86
87 VISIBLE void
MOD_TraceLine(hull_t * hull,int num,const vec3_t start_point,const vec3_t end_point,trace_t * trace)88 MOD_TraceLine (hull_t *hull, int num,
89 const vec3_t start_point, const vec3_t end_point,
90 trace_t *trace)
91 {
92 vec_t start_dist, end_dist, frac;
93 vec3_t start, end, dist;
94 int side, empty, solid;
95 tracestack_t *tstack;
96 tracestack_t tracestack[256];
97 mclipnode_t *node;
98 mplane_t *plane, *split_plane;
99
100 VectorCopy (start_point, start);
101 VectorCopy (end_point, end);
102
103 tstack = tracestack;
104 empty = 0;
105 solid = 0;
106 split_plane = 0;
107
108 while (1) {
109 while (num < 0) {
110 if (!solid && num != CONTENTS_SOLID) {
111 empty = 1;
112 if (num == CONTENTS_EMPTY)
113 trace->inopen = true;
114 else
115 trace->inwater = true;
116 } else if (!empty && num == CONTENTS_SOLID) {
117 solid = 1;
118 } else if (solid && num != CONTENTS_SOLID) {
119 //FIXME not sure what I want
120 //made it out of the solid and into open space, continue
121 //on as if we were always in empty space
122 empty = 1;
123 solid = 0;
124 trace->startsolid = 1;
125 if (num == CONTENTS_EMPTY)
126 trace->inopen = true;
127 else
128 trace->inwater = true;
129 } else if (empty/* || solid*/) {//FIXME not sure what I want
130 // DONE!
131 trace->allsolid = solid & (num == CONTENTS_SOLID);
132 trace->startsolid = solid;
133 calc_impact (trace, start_point, end_point, split_plane);
134 return;
135 }
136
137 // pop up the stack for a back side
138 if (tstack-- == tracestack) {
139 // we've finished.
140 trace->allsolid = solid & (num == CONTENTS_SOLID);
141 trace->startsolid = solid;
142 return;
143 }
144
145 // set the hit point for this plane
146 VectorCopy (end, start);
147
148 // go down the back side
149 VectorCopy (tstack->end, end);
150 side = tstack->side;
151 split_plane = tstack->plane;
152
153 num = hull->clipnodes[tstack->num].children[side ^ 1];
154 }
155
156 node = hull->clipnodes + num;
157 plane = hull->planes + node->planenum;
158
159 start_dist = PlaneDiff (start, plane);
160 end_dist = PlaneDiff (end, plane);
161
162 if (start_dist >= 0 && end_dist >= 0) {
163 // entirely in front of the plane
164 num = node->children[0];
165 continue;
166 }
167 if (start_dist < 0 && end_dist < 0) {
168 // entirely behind the plane
169 num = node->children[1];
170 continue;
171 }
172
173 side = start_dist < 0;
174 frac = start_dist / (start_dist - end_dist);
175 frac = bound (0, frac, 1);
176
177 tstack->num = num;
178 tstack->side = side;
179 tstack->plane = plane;
180 VectorCopy (end, tstack->end);
181 tstack++;
182
183 VectorSubtract (end, start, dist);
184 VectorMultAdd (start, frac, dist, end);
185
186 num = node->children[side];
187 }
188 }
189