split out RecursiveHullCheck and related code into collision.c (shared by client...
[divverent/darkplaces.git] / collision.c
1
2 #include "quakedef.h"
3
4 typedef struct
5 {
6         // the hull we're tracing through
7         const hull_t *hull;
8
9         // the trace structure to fill in
10         trace_t *trace;
11
12         // start and end of the trace (in model space)
13         double start[3];
14         double end[3];
15
16         // end - start (for quick fraction -> vector conversions)
17         double dist[3];
18 }
19 RecursiveHullCheckTraceInfo_t;
20
21 // 1/32 epsilon to keep floating point happy
22 #define DIST_EPSILON (0.03125)
23
24 #define HULLCHECKSTATE_EMPTY 0
25 #define HULLCHECKSTATE_SOLID 1
26 #define HULLCHECKSTATE_DONE 2
27
28 static void RecursiveHullCheck_Impact (RecursiveHullCheckTraceInfo_t *t, const mplane_t *plane, const int side)
29 {
30         // LordHavoc: using doubles for extra accuracy
31         double t1, t2, frac, pdist;
32
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
35         // surface distance
36         pdist = plane->dist;
37         if (side)
38         {
39                 pdist -= DIST_EPSILON;
40                 VectorNegate (plane->normal, t->trace->plane.normal);
41                 t->trace->plane.dist = -plane->dist;
42         }
43         else
44         {
45                 pdist += DIST_EPSILON;
46                 VectorCopy (plane->normal, t->trace->plane.normal);
47                 t->trace->plane.dist = plane->dist;
48         }
49
50         if (plane->type < 3)
51         {
52                 t1 = t->start[plane->type] - pdist;
53                 t2 = t->start[plane->type] + t->dist[plane->type] - pdist;
54         }
55         else
56         {
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;
59         }
60
61         frac = t1 / (t1 - t2);
62         frac = bound(0.0f, frac, 1.0);
63
64         t->trace->fraction = frac;
65         VectorMA(t->start, frac, t->dist, t->trace->endpos);
66 }
67
68 static int RecursiveHullCheck (RecursiveHullCheckTraceInfo_t *t, int num, double p1f, double p2f, const double p1[3], const double p2[3])
69 {
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)
73         int ret;
74         mplane_t *plane;
75         double t1, t2, frac;
76
77         // variables that need to be stored on the stack when recursing
78         dclipnode_t     *node;
79         int                     side;
80         double          midf, mid[3];
81
82         // LordHavoc: a goto!  everyone flee in terror... :)
83 loc0:
84         // check for empty
85         if (num < 0)
86         {
87                 t->trace->endcontents = num;
88                 if (t->trace->startcontents)
89                 {
90                         if (num == t->trace->startcontents)
91                                 t->trace->allsolid = false;
92                         else
93                         {
94                                 // if the first leaf is solid, set startsolid
95                                 if (t->trace->allsolid)
96                                         t->trace->startsolid = true;
97                                 return HULLCHECKSTATE_SOLID;
98                         }
99                         return HULLCHECKSTATE_EMPTY;
100                 }
101                 else
102                 {
103                         if (num != CONTENTS_SOLID)
104                         {
105                                 t->trace->allsolid = false;
106                                 if (num == CONTENTS_EMPTY)
107                                         t->trace->inopen = true;
108                                 else
109                                         t->trace->inwater = true;
110                         }
111                         else
112                         {
113                                 // if the first leaf is solid, set startsolid
114                                 if (t->trace->allsolid)
115                                         t->trace->startsolid = true;
116                                 return HULLCHECKSTATE_SOLID;
117                         }
118                         return HULLCHECKSTATE_EMPTY;
119                 }
120         }
121
122         // find the point distances
123         node = t->hull->clipnodes + num;
124
125         plane = t->hull->planes + node->planenum;
126         if (plane->type < 3)
127         {
128                 t1 = p1[plane->type] - plane->dist;
129                 t2 = p2[plane->type] - plane->dist;
130         }
131         else
132         {
133                 t1 = DotProduct (plane->normal, p1) - plane->dist;
134                 t2 = DotProduct (plane->normal, p2) - plane->dist;
135         }
136
137         side = t1 < 0;
138
139         if (side)
140         {
141                 if (t1 < -DIST_EPSILON && t2 < -DIST_EPSILON)
142                 {
143                         num = node->children[1];
144                         goto loc0;
145                 }
146         }
147         else
148         {
149                 if (t1 > DIST_EPSILON && t2 > DIST_EPSILON)
150                 {
151                         num = node->children[0];
152                         goto loc0;
153                 }
154         }
155
156         // the line (almost) intersects, recurse both sides
157
158         frac = t1 / (t1 - t2);
159         frac = bound(0.0f, frac, 1.0);
160
161         midf = p1f + ((p2f - p1f) * frac);
162         VectorMA(t->start, midf, t->dist, mid);
163
164         // front side first
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
171
172         // front is air and back is solid, this is the impact point...
173         RecursiveHullCheck_Impact(t, t->hull->planes + node->planenum, side);
174
175         return HULLCHECKSTATE_DONE;
176 }
177
178 void Collision_RoundUpToHullSize(const model_t *cmodel, const vec3_t inmins, const vec3_t inmaxs, vec3_t outmins, vec3_t outmaxs)
179 {
180         vec3_t size;
181         const hull_t *hull;
182
183         VectorSubtract(inmaxs, inmins, size);
184         if (cmodel->ishlbsp)
185         {
186                 if (size[0] < 3)
187                         hull = &cmodel->hulls[0]; // 0x0x0
188                 else if (size[0] <= 32)
189                 {
190                         if (size[2] < 54) // pick the nearest of 36 or 72
191                                 hull = &cmodel->hulls[3]; // 32x32x36
192                         else
193                                 hull = &cmodel->hulls[1]; // 32x32x72
194                 }
195                 else
196                         hull = &cmodel->hulls[2]; // 64x64x64
197         }
198         else
199         {
200                 if (size[0] < 3)
201                         hull = &cmodel->hulls[0]; // 0x0x0
202                 else if (size[0] <= 32)
203                         hull = &cmodel->hulls[1]; // 32x32x56
204                 else
205                         hull = &cmodel->hulls[2]; // 64x64x88
206         }
207         VectorCopy(inmins, outmins);
208         VectorAdd(inmins, hull->clip_size, outmaxs);
209 }
210
211 static hull_t box_hull;
212 static dclipnode_t box_clipnodes[6];
213 static mplane_t box_planes[6];
214
215 void Collision_Init (void)
216 {
217         int             i;
218         int             side;
219
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.
222
223         box_hull.clipnodes = box_clipnodes;
224         box_hull.planes = box_planes;
225         box_hull.firstclipnode = 0;
226         box_hull.lastclipnode = 5;
227
228         for (i = 0;i < 6;i++)
229         {
230                 box_clipnodes[i].planenum = i;
231
232                 side = i&1;
233
234                 box_clipnodes[i].children[side] = CONTENTS_EMPTY;
235                 if (i != 5)
236                         box_clipnodes[i].children[side^1] = i + 1;
237                 else
238                         box_clipnodes[i].children[side^1] = CONTENTS_SOLID;
239
240                 box_planes[i].type = i>>1;
241                 box_planes[i].normal[i>>1] = 1;
242         }
243 }
244
245
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)
247 {
248         vec3_t hullmins, hullmaxs;
249
250         // create a temp hull from bounding box sizes
251         VectorCopy (corigin, offset);
252         VectorSubtract (cmins, maxs, hullmins);
253         VectorSubtract (cmaxs, mins, hullmaxs);
254
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];
263         return &box_hull;
264 }
265
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)
267 {
268         vec3_t size;
269         const hull_t *hull;
270
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!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
275         if (cmodel->ishlbsp)
276         {
277                 if (size[0] < 3)
278                         hull = &cmodel->hulls[0]; // 0x0x0
279                 else if (size[0] <= 32)
280                 {
281                         if (size[2] < 54) // pick the nearest of 36 or 72
282                                 hull = &cmodel->hulls[3]; // 32x32x36
283                         else
284                                 hull = &cmodel->hulls[1]; // 32x32x72
285                 }
286                 else
287                         hull = &cmodel->hulls[2]; // 64x64x64
288         }
289         else
290         {
291                 if (size[0] < 3)
292                         hull = &cmodel->hulls[0]; // 0x0x0
293                 else if (size[0] <= 32)
294                         hull = &cmodel->hulls[1]; // 32x32x56
295                 else
296                         hull = &cmodel->hulls[2]; // 64x64x88
297         }
298
299         // calculate an offset value to center the origin
300         VectorSubtract (hull->clip_mins, mins, offset);
301         VectorAdd (offset, corigin, offset);
302
303         return hull;
304 }
305
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)
307 {
308         RecursiveHullCheckTraceInfo_t rhc;
309         vec3_t offset, forward, left, up;
310         double startd[3], endd[3], tempd[3];
311
312         // fill in a default trace
313         memset (&rhc, 0, sizeof(rhc));
314         memset (trace, 0, sizeof(trace_t));
315
316         rhc.trace = trace;
317
318         rhc.trace->fraction = 1;
319         rhc.trace->allsolid = true;
320
321         if (cmodel && cmodel->type == mod_brush)
322         {
323                 // brush model
324
325                 // get the clipping hull
326                 rhc.hull = HullForBrushModel (cmodel, corigin, mins, maxs, offset);
327
328                 VectorSubtract(start, offset, startd);
329                 VectorSubtract(end, offset, endd);
330
331                 // rotate start and end into the model's frame of reference
332                 if (cangles[0] || cangles[1] || cangles[2])
333                 {
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);
343                 }
344
345                 VectorCopy(end, rhc.trace->endpos);
346
347                 // trace a line through the appropriate clipping hull
348                 VectorCopy(startd, rhc.start);
349                 VectorCopy(endd, rhc.end);
350
351                 VectorSubtract(rhc.end, rhc.start, rhc.dist);
352                 RecursiveHullCheck (&rhc, rhc.hull->firstclipnode, 0, 1, startd, endd);
353
354                 // if we hit, unrotate endpos and normal, and store the entity we hit
355                 if (rhc.trace->fraction != 1)
356                 {
357                         // rotate endpos back to world frame of reference
358                         if (cangles[0] || cangles[1] || cangles[2])
359                         {
360                                 VectorNegate (cangles, offset);
361                                 AngleVectorsFLU (offset, forward, left, up);
362
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);
367
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);
372                         }
373                         // fix offset
374                         VectorAdd (rhc.trace->endpos, offset, rhc.trace->endpos);
375                         rhc.trace->ent = (void *) cent;
376                 }
377                 else if (rhc.trace->allsolid || rhc.trace->startsolid)
378                         rhc.trace->ent = (void *) cent;
379         }
380         else
381         {
382                 // bounding box
383
384                 rhc.hull = HullForBBoxEntity (corigin, cmins, cmaxs, mins, maxs, offset);
385
386                 VectorSubtract(start, offset, startd);
387                 VectorSubtract(end, offset, endd);
388                 VectorCopy(end, rhc.trace->endpos);
389
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);
394
395                 // if we hit, store the entity we hit
396                 if (rhc.trace->fraction != 1)
397                 {
398                         // fix offset
399                         VectorAdd (rhc.trace->endpos, offset, rhc.trace->endpos);
400                         rhc.trace->ent = (void *) cent;
401                 }
402                 else if (rhc.trace->allsolid || rhc.trace->startsolid)
403                         rhc.trace->ent = (void *) cent;
404         }
405 }