6 // the hull we're tracing through
9 // the trace structure to fill in
12 // start and end of the trace (in model space)
16 // end - start (for quick fraction -> vector conversions)
19 RecursiveHullCheckTraceInfo_t;
21 // 1/32 epsilon to keep floating point happy
22 #define DIST_EPSILON (0.03125)
24 #define HULLCHECKSTATE_EMPTY 0
25 #define HULLCHECKSTATE_SOLID 1
26 #define HULLCHECKSTATE_DONE 2
28 static void RecursiveHullCheck_Impact (RecursiveHullCheckTraceInfo_t *t, const mplane_t *plane, const int side)
30 // LordHavoc: using doubles for extra accuracy
31 double t1, t2, frac, pdist;
33 // LordHavoc: now that we have found the impact, recalculate the impact
34 // point from scratch for maximum accuracy, with an epsilon bias on the
39 pdist -= DIST_EPSILON;
40 VectorNegate (plane->normal, t->trace->plane.normal);
41 t->trace->plane.dist = -plane->dist;
45 pdist += DIST_EPSILON;
46 VectorCopy (plane->normal, t->trace->plane.normal);
47 t->trace->plane.dist = plane->dist;
52 t1 = t->start[plane->type] - pdist;
53 t2 = t->start[plane->type] + t->dist[plane->type] - pdist;
57 t1 = plane->normal[0] * t->start[0] + plane->normal[1] * t->start[1] + plane->normal[2] * t->start[2] - pdist;
58 t2 = plane->normal[0] * (t->start[0] + t->dist[0]) + plane->normal[1] * (t->start[1] + t->dist[1]) + plane->normal[2] * (t->start[2] + t->dist[2]) - pdist;
61 frac = t1 / (t1 - t2);
62 frac = bound(0.0f, frac, 1.0);
64 t->trace->fraction = frac;
65 VectorMA(t->start, frac, t->dist, t->trace->endpos);
68 static int RecursiveHullCheck (RecursiveHullCheckTraceInfo_t *t, int num, double p1f, double p2f, const double p1[3], const double p2[3])
70 // status variables, these don't need to be saved on the stack when
71 // recursing... but are because this should be thread-safe
72 // (note: tracing against a bbox is not thread-safe, yet)
77 // variables that need to be stored on the stack when recursing
82 // LordHavoc: a goto! everyone flee in terror... :)
87 t->trace->endcontents = num;
88 if (t->trace->startcontents)
90 if (num == t->trace->startcontents)
91 t->trace->allsolid = false;
94 // if the first leaf is solid, set startsolid
95 if (t->trace->allsolid)
96 t->trace->startsolid = true;
97 return HULLCHECKSTATE_SOLID;
99 return HULLCHECKSTATE_EMPTY;
103 if (num != CONTENTS_SOLID)
105 t->trace->allsolid = false;
106 if (num == CONTENTS_EMPTY)
107 t->trace->inopen = true;
109 t->trace->inwater = true;
113 // if the first leaf is solid, set startsolid
114 if (t->trace->allsolid)
115 t->trace->startsolid = true;
116 return HULLCHECKSTATE_SOLID;
118 return HULLCHECKSTATE_EMPTY;
122 // find the point distances
123 node = t->hull->clipnodes + num;
125 plane = t->hull->planes + node->planenum;
128 t1 = p1[plane->type] - plane->dist;
129 t2 = p2[plane->type] - plane->dist;
133 t1 = DotProduct (plane->normal, p1) - plane->dist;
134 t2 = DotProduct (plane->normal, p2) - plane->dist;
141 if (t1 < -DIST_EPSILON && t2 < -DIST_EPSILON)
143 num = node->children[1];
149 if (t1 > DIST_EPSILON && t2 > DIST_EPSILON)
151 num = node->children[0];
156 // the line (almost) intersects, recurse both sides
158 frac = t1 / (t1 - t2);
159 frac = bound(0.0f, frac, 1.0);
161 midf = p1f + ((p2f - p1f) * frac);
162 VectorMA(t->start, midf, t->dist, mid);
165 ret = RecursiveHullCheck (t, node->children[side], p1f, midf, p1, mid);
166 if (ret != HULLCHECKSTATE_EMPTY)
167 return ret; // solid or done
168 ret = RecursiveHullCheck (t, node->children[!side], midf, p2f, mid, p2);
169 if (ret != HULLCHECKSTATE_SOLID)
170 return ret; // empty or done
172 // front is air and back is solid, this is the impact point...
173 RecursiveHullCheck_Impact(t, t->hull->planes + node->planenum, side);
175 return HULLCHECKSTATE_DONE;
178 void Collision_RoundUpToHullSize(const model_t *cmodel, const vec3_t inmins, const vec3_t inmaxs, vec3_t outmins, vec3_t outmaxs)
183 VectorSubtract(inmaxs, inmins, size);
187 hull = &cmodel->hulls[0]; // 0x0x0
188 else if (size[0] <= 32)
190 if (size[2] < 54) // pick the nearest of 36 or 72
191 hull = &cmodel->hulls[3]; // 32x32x36
193 hull = &cmodel->hulls[1]; // 32x32x72
196 hull = &cmodel->hulls[2]; // 64x64x64
201 hull = &cmodel->hulls[0]; // 0x0x0
202 else if (size[0] <= 32)
203 hull = &cmodel->hulls[1]; // 32x32x56
205 hull = &cmodel->hulls[2]; // 64x64x88
207 VectorCopy(inmins, outmins);
208 VectorAdd(inmins, hull->clip_size, outmaxs);
211 static hull_t box_hull;
212 static dclipnode_t box_clipnodes[6];
213 static mplane_t box_planes[6];
215 void Collision_Init (void)
220 //Set up the planes and clipnodes so that the six floats of a bounding box
221 //can just be stored out and get a proper hull_t structure.
223 box_hull.clipnodes = box_clipnodes;
224 box_hull.planes = box_planes;
225 box_hull.firstclipnode = 0;
226 box_hull.lastclipnode = 5;
228 for (i = 0;i < 6;i++)
230 box_clipnodes[i].planenum = i;
234 box_clipnodes[i].children[side] = CONTENTS_EMPTY;
236 box_clipnodes[i].children[side^1] = i + 1;
238 box_clipnodes[i].children[side^1] = CONTENTS_SOLID;
240 box_planes[i].type = i>>1;
241 box_planes[i].normal[i>>1] = 1;
246 static hull_t *HullForBBoxEntity (const vec3_t corigin, const vec3_t cmins, const vec3_t cmaxs, const vec3_t mins, const vec3_t maxs, vec3_t offset)
248 vec3_t hullmins, hullmaxs;
250 // create a temp hull from bounding box sizes
251 VectorCopy (corigin, offset);
252 VectorSubtract (cmins, maxs, hullmins);
253 VectorSubtract (cmaxs, mins, hullmaxs);
255 //To keep everything totally uniform, bounding boxes are turned into small
256 //BSP trees instead of being compared directly.
257 box_planes[0].dist = hullmaxs[0];
258 box_planes[1].dist = hullmins[0];
259 box_planes[2].dist = hullmaxs[1];
260 box_planes[3].dist = hullmins[1];
261 box_planes[4].dist = hullmaxs[2];
262 box_planes[5].dist = hullmins[2];
266 static const hull_t *HullForBrushModel (const model_t *cmodel, const vec3_t corigin, const vec3_t mins, const vec3_t maxs, vec3_t offset)
271 // decide which clipping hull to use, based on the size
272 // explicit hulls in the BSP model
273 VectorSubtract (maxs, mins, size);
274 // LordHavoc: FIXME!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
278 hull = &cmodel->hulls[0]; // 0x0x0
279 else if (size[0] <= 32)
281 if (size[2] < 54) // pick the nearest of 36 or 72
282 hull = &cmodel->hulls[3]; // 32x32x36
284 hull = &cmodel->hulls[1]; // 32x32x72
287 hull = &cmodel->hulls[2]; // 64x64x64
292 hull = &cmodel->hulls[0]; // 0x0x0
293 else if (size[0] <= 32)
294 hull = &cmodel->hulls[1]; // 32x32x56
296 hull = &cmodel->hulls[2]; // 64x64x88
299 // calculate an offset value to center the origin
300 VectorSubtract (hull->clip_mins, mins, offset);
301 VectorAdd (offset, corigin, offset);
306 void Collision_ClipTrace (trace_t *trace, const void *cent, const model_t *cmodel, const vec3_t corigin, const vec3_t cangles, const vec3_t cmins, const vec3_t cmaxs, const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end)
308 RecursiveHullCheckTraceInfo_t rhc;
309 vec3_t offset, forward, left, up;
310 double startd[3], endd[3], tempd[3];
312 // fill in a default trace
313 memset (&rhc, 0, sizeof(rhc));
314 memset (trace, 0, sizeof(trace_t));
318 rhc.trace->fraction = 1;
319 rhc.trace->allsolid = true;
321 if (cmodel && cmodel->type == mod_brush)
325 // get the clipping hull
326 rhc.hull = HullForBrushModel (cmodel, corigin, mins, maxs, offset);
328 VectorSubtract(start, offset, startd);
329 VectorSubtract(end, offset, endd);
331 // rotate start and end into the model's frame of reference
332 if (cangles[0] || cangles[1] || cangles[2])
334 AngleVectorsFLU (cangles, forward, left, up);
335 VectorCopy(startd, tempd);
336 startd[0] = DotProduct (tempd, forward);
337 startd[1] = DotProduct (tempd, left);
338 startd[2] = DotProduct (tempd, up);
339 VectorCopy(endd, tempd);
340 endd[0] = DotProduct (tempd, forward);
341 endd[1] = DotProduct (tempd, left);
342 endd[2] = DotProduct (tempd, up);
345 VectorCopy(end, rhc.trace->endpos);
347 // trace a line through the appropriate clipping hull
348 VectorCopy(startd, rhc.start);
349 VectorCopy(endd, rhc.end);
351 VectorSubtract(rhc.end, rhc.start, rhc.dist);
352 RecursiveHullCheck (&rhc, rhc.hull->firstclipnode, 0, 1, startd, endd);
354 // if we hit, unrotate endpos and normal, and store the entity we hit
355 if (rhc.trace->fraction != 1)
357 // rotate endpos back to world frame of reference
358 if (cangles[0] || cangles[1] || cangles[2])
360 VectorNegate (cangles, offset);
361 AngleVectorsFLU (offset, forward, left, up);
363 VectorCopy (rhc.trace->endpos, tempd);
364 rhc.trace->endpos[0] = DotProduct (tempd, forward);
365 rhc.trace->endpos[1] = DotProduct (tempd, left);
366 rhc.trace->endpos[2] = DotProduct (tempd, up);
368 VectorCopy (rhc.trace->plane.normal, tempd);
369 rhc.trace->plane.normal[0] = DotProduct (tempd, forward);
370 rhc.trace->plane.normal[1] = DotProduct (tempd, left);
371 rhc.trace->plane.normal[2] = DotProduct (tempd, up);
374 VectorAdd (rhc.trace->endpos, offset, rhc.trace->endpos);
375 rhc.trace->ent = (void *) cent;
377 else if (rhc.trace->allsolid || rhc.trace->startsolid)
378 rhc.trace->ent = (void *) cent;
384 rhc.hull = HullForBBoxEntity (corigin, cmins, cmaxs, mins, maxs, offset);
386 VectorSubtract(start, offset, startd);
387 VectorSubtract(end, offset, endd);
388 VectorCopy(end, rhc.trace->endpos);
390 // trace a line through the generated clipping hull
391 VectorCopy(startd, rhc.start);
392 VectorSubtract(endd, startd, rhc.dist);
393 RecursiveHullCheck (&rhc, rhc.hull->firstclipnode, 0, 1, startd, endd);
395 // if we hit, store the entity we hit
396 if (rhc.trace->fraction != 1)
399 VectorAdd (rhc.trace->endpos, offset, rhc.trace->endpos);
400 rhc.trace->ent = (void *) cent;
402 else if (rhc.trace->allsolid || rhc.trace->startsolid)
403 rhc.trace->ent = (void *) cent;