1 /*
2 Copyright (C) 1996-1997 Id Software, Inc.
3
4 This program is free software; you can redistribute it and/or
5 modify it under the terms of the GNU General Public License
6 as published by the Free Software Foundation; either version 2
7 of the License, or (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12
13 See the GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
18
19 */
20 #include "quakedef.h"
21
22 static hull_t box_hull;
23 static dclipnode_t box_clipnodes[6];
24 static mplane_t box_planes[6];
25
26 extern vec3_t player_mins;
27 extern vec3_t player_maxs;
28
29 /*
30 ===================
31 PM_InitBoxHull
32
33 Set up the planes and clipnodes so that the six floats of a bounding box
34 can just be stored out and get a proper hull_t structure.
35 ===================
36 */
PM_InitBoxHull(void)37 void PM_InitBoxHull (void)
38 {
39 int i;
40 int side;
41
42 box_hull.clipnodes = box_clipnodes;
43 box_hull.planes = box_planes;
44 box_hull.firstclipnode = 0;
45 box_hull.lastclipnode = 5;
46
47 for (i=0 ; i<6 ; i++)
48 {
49 box_clipnodes[i].planenum = i;
50
51 side = i&1;
52
53 box_clipnodes[i].children[side] = CONTENTS_EMPTY;
54 if (i != 5)
55 box_clipnodes[i].children[side^1] = i + 1;
56 else
57 box_clipnodes[i].children[side^1] = CONTENTS_SOLID;
58
59 box_planes[i].type = i>>1;
60 box_planes[i].normal[i>>1] = 1;
61 }
62
63 }
64
65
66 /*
67 ===================
68 PM_HullForBox
69
70 To keep everything totally uniform, bounding boxes are turned into small
71 BSP trees instead of being compared directly.
72 ===================
73 */
PM_HullForBox(vec3_t mins,vec3_t maxs)74 hull_t *PM_HullForBox (vec3_t mins, vec3_t maxs)
75 {
76 box_planes[0].dist = maxs[0];
77 box_planes[1].dist = mins[0];
78 box_planes[2].dist = maxs[1];
79 box_planes[3].dist = mins[1];
80 box_planes[4].dist = maxs[2];
81 box_planes[5].dist = mins[2];
82
83 return &box_hull;
84 }
85
86
87 /*
88 ==================
89 PM_HullPointContents
90
91 ==================
92 */
PM_HullPointContents(hull_t * hull,int num,vec3_t p)93 int PM_HullPointContents (hull_t *hull, int num, vec3_t p)
94 {
95 float d;
96 dclipnode_t *node;
97 mplane_t *plane;
98
99 while (num >= 0)
100 {
101 if (num < hull->firstclipnode || num > hull->lastclipnode)
102 Sys_Error ("PM_HullPointContents: bad node number");
103
104 node = hull->clipnodes + num;
105 plane = hull->planes + node->planenum;
106
107 if (plane->type < 3)
108 d = p[plane->type] - plane->dist;
109 else
110 d = DotProduct (plane->normal, p) - plane->dist;
111 if (d < 0)
112 num = node->children[1];
113 else
114 num = node->children[0];
115 }
116
117 return num;
118 }
119
120 /*
121 ==================
122 PM_PointContents
123
124 ==================
125 */
PM_PointContents(vec3_t p)126 int PM_PointContents (vec3_t p)
127 {
128 float d;
129 dclipnode_t *node;
130 mplane_t *plane;
131 hull_t *hull;
132 int num;
133
134 hull = &pmove.physents[0].model->hulls[0];
135
136 num = hull->firstclipnode;
137
138 while (num >= 0)
139 {
140 if (num < hull->firstclipnode || num > hull->lastclipnode)
141 Sys_Error ("PM_HullPointContents: bad node number");
142
143 node = hull->clipnodes + num;
144 plane = hull->planes + node->planenum;
145
146 if (plane->type < 3)
147 d = p[plane->type] - plane->dist;
148 else
149 d = DotProduct (plane->normal, p) - plane->dist;
150 if (d < 0)
151 num = node->children[1];
152 else
153 num = node->children[0];
154 }
155
156 return num;
157 }
158
159 /*
160 ===============================================================================
161
162 LINE TESTING IN HULLS
163
164 ===============================================================================
165 */
166
167 // 1/32 epsilon to keep floating point happy
168 #define DIST_EPSILON (0.03125)
169
170 /*
171 ==================
172 PM_RecursiveHullCheck
173
174 ==================
175 */
PM_RecursiveHullCheck(hull_t * hull,int num,float p1f,float p2f,vec3_t p1,vec3_t p2,pmtrace_t * trace)176 qboolean PM_RecursiveHullCheck (hull_t *hull, int num, float p1f, float p2f, vec3_t p1, vec3_t p2, pmtrace_t *trace)
177 {
178 dclipnode_t *node;
179 mplane_t *plane;
180 float t1, t2;
181 float frac;
182 int i;
183 vec3_t mid;
184 int side;
185 float midf;
186
187 // check for empty
188 if (num < 0)
189 {
190 if (num != CONTENTS_SOLID)
191 {
192 trace->allsolid = false;
193 if (num == CONTENTS_EMPTY)
194 trace->inopen = true;
195 else
196 trace->inwater = true;
197 }
198 else
199 trace->startsolid = true;
200 return true; // empty
201 }
202
203 if (num < hull->firstclipnode || num > hull->lastclipnode)
204 Sys_Error ("PM_RecursiveHullCheck: bad node number");
205
206 //
207 // find the point distances
208 //
209 node = hull->clipnodes + num;
210 plane = hull->planes + node->planenum;
211
212 if (plane->type < 3)
213 {
214 t1 = p1[plane->type] - plane->dist;
215 t2 = p2[plane->type] - plane->dist;
216 }
217 else
218 {
219 t1 = DotProduct (plane->normal, p1) - plane->dist;
220 t2 = DotProduct (plane->normal, p2) - plane->dist;
221 }
222
223 #if 1
224 if (t1 >= 0 && t2 >= 0)
225 return PM_RecursiveHullCheck (hull, node->children[0], p1f, p2f, p1, p2, trace);
226 if (t1 < 0 && t2 < 0)
227 return PM_RecursiveHullCheck (hull, node->children[1], p1f, p2f, p1, p2, trace);
228 #else
229 if ( (t1 >= DIST_EPSILON && t2 >= DIST_EPSILON) || (t2 > t1 && t1 >= 0) )
230 return PM_RecursiveHullCheck (hull, node->children[0], p1f, p2f, p1, p2, trace);
231 if ( (t1 <= -DIST_EPSILON && t2 <= -DIST_EPSILON) || (t2 < t1 && t1 <= 0) )
232 return PM_RecursiveHullCheck (hull, node->children[1], p1f, p2f, p1, p2, trace);
233 #endif
234
235 // put the crosspoint DIST_EPSILON pixels on the near side
236 if (t1 < 0)
237 frac = (t1 + DIST_EPSILON)/(t1-t2);
238 else
239 frac = (t1 - DIST_EPSILON)/(t1-t2);
240 if (frac < 0)
241 frac = 0;
242 if (frac > 1)
243 frac = 1;
244
245 midf = p1f + (p2f - p1f)*frac;
246 for (i=0 ; i<3 ; i++)
247 mid[i] = p1[i] + frac*(p2[i] - p1[i]);
248
249 side = (t1 < 0);
250
251 // move up to the node
252 if (!PM_RecursiveHullCheck (hull, node->children[side], p1f, midf, p1, mid, trace) )
253 return false;
254
255 #ifdef PARANOID
256 if (PM_HullPointContents (pm_hullmodel, mid, node->children[side])
257 == CONTENTS_SOLID)
258 {
259 Con_Printf ("mid PointInHullSolid\n");
260 return false;
261 }
262 #endif
263
264 if (PM_HullPointContents (hull, node->children[side^1], mid)
265 != CONTENTS_SOLID)
266 // go past the node
267 return PM_RecursiveHullCheck (hull, node->children[side^1], midf, p2f, mid, p2, trace);
268
269 if (trace->allsolid)
270 return false; // never got out of the solid area
271
272 //==================
273 // the other side of the node is solid, this is the impact point
274 //==================
275 if (!side)
276 {
277 VectorCopy (plane->normal, trace->plane.normal);
278 trace->plane.dist = plane->dist;
279 }
280 else
281 {
282 VectorSubtract (vec3_origin, plane->normal, trace->plane.normal);
283 trace->plane.dist = -plane->dist;
284 }
285
286 while (PM_HullPointContents (hull, hull->firstclipnode, mid)
287 == CONTENTS_SOLID)
288 { // shouldn't really happen, but does occasionally
289 frac -= 0.1;
290 if (frac < 0)
291 {
292 trace->fraction = midf;
293 VectorCopy (mid, trace->endpos);
294 Con_DPrintf ("backup past 0\n");
295 return false;
296 }
297 midf = p1f + (p2f - p1f)*frac;
298 for (i=0 ; i<3 ; i++)
299 mid[i] = p1[i] + frac*(p2[i] - p1[i]);
300 }
301
302 trace->fraction = midf;
303 VectorCopy (mid, trace->endpos);
304
305 return false;
306 }
307
308
309 /*
310 ================
311 PM_TestPlayerPosition
312
313 Returns false if the given player position is not valid (in solid)
314 ================
315 */
PM_TestPlayerPosition(vec3_t pos)316 qboolean PM_TestPlayerPosition (vec3_t pos)
317 {
318 int i;
319 physent_t *pe;
320 vec3_t mins, maxs, test;
321 hull_t *hull;
322
323 for (i=0 ; i< pmove.numphysent ; i++)
324 {
325 pe = &pmove.physents[i];
326 // get the clipping hull
327 if (pe->model)
328 hull = &pmove.physents[i].model->hulls[1];
329 else
330 {
331 VectorSubtract (pe->mins, player_maxs, mins);
332 VectorSubtract (pe->maxs, player_mins, maxs);
333 hull = PM_HullForBox (mins, maxs);
334 }
335
336 VectorSubtract (pos, pe->origin, test);
337
338 if (PM_HullPointContents (hull, hull->firstclipnode, test) == CONTENTS_SOLID)
339 return false;
340 }
341
342 return true;
343 }
344
345 /*
346 ================
347 PM_PlayerMove
348 ================
349 */
PM_PlayerMove(vec3_t start,vec3_t end)350 pmtrace_t PM_PlayerMove (vec3_t start, vec3_t end)
351 {
352 pmtrace_t trace, total;
353 vec3_t offset;
354 vec3_t start_l, end_l;
355 hull_t *hull;
356 int i;
357 physent_t *pe;
358 vec3_t mins, maxs;
359
360 // fill in a default trace
361 memset (&total, 0, sizeof(pmtrace_t));
362 total.fraction = 1;
363 total.ent = -1;
364 VectorCopy (end, total.endpos);
365
366 for (i=0 ; i< pmove.numphysent ; i++)
367 {
368 pe = &pmove.physents[i];
369 // get the clipping hull
370 if (pe->model)
371 hull = &pmove.physents[i].model->hulls[1];
372 else
373 {
374 VectorSubtract (pe->mins, player_maxs, mins);
375 VectorSubtract (pe->maxs, player_mins, maxs);
376 hull = PM_HullForBox (mins, maxs);
377 }
378
379 // PM_HullForEntity (ent, mins, maxs, offset);
380 VectorCopy (pe->origin, offset);
381
382 VectorSubtract (start, offset, start_l);
383 VectorSubtract (end, offset, end_l);
384
385 // fill in a default trace
386 memset (&trace, 0, sizeof(pmtrace_t));
387 trace.fraction = 1;
388 trace.allsolid = true;
389 // trace.startsolid = true;
390 VectorCopy (end, trace.endpos);
391
392 // trace a line through the apropriate clipping hull
393 PM_RecursiveHullCheck (hull, hull->firstclipnode, 0, 1, start_l, end_l, &trace);
394
395 if (trace.allsolid)
396 trace.startsolid = true;
397 if (trace.startsolid)
398 trace.fraction = 0;
399
400 // did we clip the move?
401 if (trace.fraction < total.fraction)
402 {
403 // fix trace up by the offset
404 VectorAdd (trace.endpos, offset, trace.endpos);
405 total = trace;
406 total.ent = i;
407 }
408
409 }
410
411 return total;
412 }
413
414
415