make bbox collisions work again
[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
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 int RecursiveHullCheck (RecursiveHullCheckTraceInfo_t *t, int num, double p1f, double p2f, double p1[3], double p2[3])
29 {
30         // status variables, these don't need to be saved on the stack when
31         // recursing...  but are because this should be thread-safe
32         // (note: tracing against a bbox is not thread-safe, yet)
33         int ret;
34         mplane_t *plane;
35         double t1, t2;
36         //double frac;
37         //double mid[3];
38
39         // variables that need to be stored on the stack when recursing
40         dclipnode_t *node;
41         int side;
42         double midf, mid[3];
43
44         // LordHavoc: a goto!  everyone flee in terror... :)
45 loc0:
46         // check for empty
47         if (num < 0)
48         {
49                 t->trace->endcontents = num;
50                 if (t->trace->startcontents)
51                 {
52                         if (num == t->trace->startcontents)
53                                 t->trace->allsolid = false;
54                         else
55                         {
56                                 // if the first leaf is solid, set startsolid
57                                 if (t->trace->allsolid)
58                                         t->trace->startsolid = true;
59                                 return HULLCHECKSTATE_SOLID;
60                         }
61                         return HULLCHECKSTATE_EMPTY;
62                 }
63                 else
64                 {
65                         if (num != CONTENTS_SOLID)
66                         {
67                                 t->trace->allsolid = false;
68                                 if (num == CONTENTS_EMPTY)
69                                         t->trace->inopen = true;
70                                 else
71                                         t->trace->inwater = true;
72                         }
73                         else
74                         {
75                                 // if the first leaf is solid, set startsolid
76                                 if (t->trace->allsolid)
77                                         t->trace->startsolid = true;
78                                 return HULLCHECKSTATE_SOLID;
79                         }
80                         return HULLCHECKSTATE_EMPTY;
81                 }
82         }
83
84         // find the point distances
85         node = t->hull->clipnodes + num;
86
87         plane = t->hull->planes + node->planenum;
88         if (plane->type < 3)
89         {
90                 t1 = p1[plane->type] - plane->dist;
91                 t2 = p2[plane->type] - plane->dist;
92         }
93         else
94         {
95                 t1 = DotProduct (plane->normal, p1) - plane->dist;
96                 t2 = DotProduct (plane->normal, p2) - plane->dist;
97         }
98
99         if (t1 < 0)
100         {
101                 if (t2 < 0)
102                 {
103                         num = node->children[1];
104                         goto loc0;
105                 }
106                 side = 1;
107         }
108         else
109         {
110                 if (t2 >= 0)
111                 {
112                         num = node->children[0];
113                         goto loc0;
114                 }
115                 side = 0;
116         }
117
118         // the line intersects, find intersection point
119         // LordHavoc: this uses the original trace for maximum accuracy
120         if (plane->type < 3)
121         {
122                 t1 = t->start[plane->type] - plane->dist;
123                 t2 = t->end[plane->type] - plane->dist;
124         }
125         else
126         {
127                 t1 = DotProduct (plane->normal, t->start) - plane->dist;
128                 t2 = DotProduct (plane->normal, t->end) - plane->dist;
129         }
130
131         midf = t1 / (t1 - t2);
132         midf = bound(p1f, midf, p2f);
133         VectorMA(t->start, midf, t->dist, mid);
134
135         // recurse both sides, front side first
136         ret = RecursiveHullCheck (t, node->children[side], p1f, midf, p1, mid);
137         // if this side is not empty, return what it is (solid or done)
138         if (ret != HULLCHECKSTATE_EMPTY)
139                 return ret;
140
141         ret = RecursiveHullCheck (t, node->children[side ^ 1], midf, p2f, mid, p2);
142         // if other side is not solid, return what it is (empty or done)
143         if (ret != HULLCHECKSTATE_SOLID)
144                 return ret;
145
146         // front is air and back is solid, this is the impact point...
147         if (side)
148         {
149                 t->trace->plane.dist = -plane->dist;
150                 VectorNegate (plane->normal, t->trace->plane.normal);
151         }
152         else
153         {
154                 t->trace->plane.dist = plane->dist;
155                 VectorCopy (plane->normal, t->trace->plane.normal);
156         }
157
158         // bias away from surface a bit
159         t1 = DotProduct(t->trace->plane.normal, t->start) - (t->trace->plane.dist + DIST_EPSILON);
160         t2 = DotProduct(t->trace->plane.normal, t->end) - (t->trace->plane.dist + DIST_EPSILON);
161
162         midf = t1 / (t1 - t2);
163         t->trace->fraction = bound(0.0f, midf, 1.0);
164
165         VectorMA(t->start, t->trace->fraction, t->dist, t->trace->endpos);
166
167         return HULLCHECKSTATE_DONE;
168 }
169
170 // used if start and end are the same
171 static void RecursiveHullCheckPoint (RecursiveHullCheckTraceInfo_t *t, int num)
172 {
173         while (num >= 0)
174                 num = t->hull->clipnodes[num].children[((t->hull->planes[t->hull->clipnodes[num].planenum].type < 3) ? (t->start[t->hull->planes[t->hull->clipnodes[num].planenum].type]) : (DotProduct(t->hull->planes[t->hull->clipnodes[num].planenum].normal, t->start))) < t->hull->planes[t->hull->clipnodes[num].planenum].dist];
175
176         // check for empty
177         t->trace->endcontents = num;
178         if (t->trace->startcontents)
179         {
180                 if (num == t->trace->startcontents)
181                         t->trace->allsolid = false;
182                 else
183                 {
184                         // if the first leaf is solid, set startsolid
185                         if (t->trace->allsolid)
186                                 t->trace->startsolid = true;
187                 }
188         }
189         else
190         {
191                 if (num != CONTENTS_SOLID)
192                 {
193                         t->trace->allsolid = false;
194                         if (num == CONTENTS_EMPTY)
195                                 t->trace->inopen = true;
196                         else
197                                 t->trace->inwater = true;
198                 }
199                 else
200                 {
201                         // if the first leaf is solid, set startsolid
202                         if (t->trace->allsolid)
203                                 t->trace->startsolid = true;
204                 }
205         }
206 }
207
208 void Collision_RoundUpToHullSize(const model_t *cmodel, const vec3_t inmins, const vec3_t inmaxs, vec3_t outmins, vec3_t outmaxs)
209 {
210         vec3_t size;
211         const hull_t *hull;
212
213         VectorSubtract(inmaxs, inmins, size);
214         if (cmodel->ishlbsp)
215         {
216                 if (size[0] < 3)
217                         hull = &cmodel->hulls[0]; // 0x0x0
218                 else if (size[0] <= 32)
219                 {
220                         if (size[2] < 54) // pick the nearest of 36 or 72
221                                 hull = &cmodel->hulls[3]; // 32x32x36
222                         else
223                                 hull = &cmodel->hulls[1]; // 32x32x72
224                 }
225                 else
226                         hull = &cmodel->hulls[2]; // 64x64x64
227         }
228         else
229         {
230                 if (size[0] < 3)
231                         hull = &cmodel->hulls[0]; // 0x0x0
232                 else if (size[0] <= 32)
233                         hull = &cmodel->hulls[1]; // 32x32x56
234                 else
235                         hull = &cmodel->hulls[2]; // 64x64x88
236         }
237         VectorCopy(inmins, outmins);
238         VectorAdd(inmins, hull->clip_size, outmaxs);
239 }
240
241 static hull_t box_hull;
242 static dclipnode_t box_clipnodes[6];
243 static mplane_t box_planes[6];
244
245 void Collision_Init (void)
246 {
247         int             i;
248         int             side;
249
250         //Set up the planes and clipnodes so that the six floats of a bounding box
251         //can just be stored out and get a proper hull_t structure.
252
253         box_hull.clipnodes = box_clipnodes;
254         box_hull.planes = box_planes;
255         box_hull.firstclipnode = 0;
256         box_hull.lastclipnode = 5;
257
258         for (i = 0;i < 6;i++)
259         {
260                 box_clipnodes[i].planenum = i;
261
262                 side = i&1;
263
264                 box_clipnodes[i].children[side] = CONTENTS_EMPTY;
265                 if (i != 5)
266                         box_clipnodes[i].children[side^1] = i + 1;
267                 else
268                         box_clipnodes[i].children[side^1] = CONTENTS_SOLID;
269
270                 box_planes[i].type = i>>1;
271                 box_planes[i].normal[i>>1] = 1;
272         }
273 }
274
275
276 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)
277 {
278         vec3_t hullmins, hullmaxs;
279
280         // create a temp hull from bounding box sizes
281         VectorCopy (corigin, offset);
282         VectorSubtract (cmins, maxs, hullmins);
283         VectorSubtract (cmaxs, mins, hullmaxs);
284
285         //To keep everything totally uniform, bounding boxes are turned into small
286         //BSP trees instead of being compared directly.
287         box_planes[0].dist = hullmaxs[0];
288         box_planes[1].dist = hullmins[0];
289         box_planes[2].dist = hullmaxs[1];
290         box_planes[3].dist = hullmins[1];
291         box_planes[4].dist = hullmaxs[2];
292         box_planes[5].dist = hullmins[2];
293         return &box_hull;
294 }
295
296 static const hull_t *HullForBrushModel (const model_t *cmodel, const vec3_t corigin, const vec3_t mins, const vec3_t maxs, vec3_t offset)
297 {
298         vec3_t size;
299         const hull_t *hull;
300
301         // decide which clipping hull to use, based on the size
302         // explicit hulls in the BSP model
303         VectorSubtract (maxs, mins, size);
304         // LordHavoc: FIXME!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
305         if (cmodel->ishlbsp)
306         {
307                 if (size[0] < 3)
308                         hull = &cmodel->hulls[0]; // 0x0x0
309                 else if (size[0] <= 32)
310                 {
311                         if (size[2] < 54) // pick the nearest of 36 or 72
312                                 hull = &cmodel->hulls[3]; // 32x32x36
313                         else
314                                 hull = &cmodel->hulls[1]; // 32x32x72
315                 }
316                 else
317                         hull = &cmodel->hulls[2]; // 64x64x64
318         }
319         else
320         {
321                 if (size[0] < 3)
322                         hull = &cmodel->hulls[0]; // 0x0x0
323                 else if (size[0] <= 32)
324                         hull = &cmodel->hulls[1]; // 32x32x56
325                 else
326                         hull = &cmodel->hulls[2]; // 64x64x88
327         }
328
329         // calculate an offset value to center the origin
330         VectorSubtract (hull->clip_mins, mins, offset);
331         VectorAdd (offset, corigin, offset);
332
333         return hull;
334 }
335
336 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)
337 {
338         RecursiveHullCheckTraceInfo_t rhc;
339         vec3_t offset, forward, left, up;
340         double startd[3], endd[3], tempd[3];
341
342         // fill in a default trace
343         memset (&rhc, 0, sizeof(rhc));
344         memset (trace, 0, sizeof(trace_t));
345
346         rhc.trace = trace;
347
348         rhc.trace->fraction = 1;
349         rhc.trace->allsolid = true;
350
351         if (cmodel && cmodel->type == mod_brush)
352         {
353                 // brush model
354
355                 // get the clipping hull
356                 rhc.hull = HullForBrushModel (cmodel, corigin, mins, maxs, offset);
357
358                 VectorSubtract(start, offset, startd);
359                 VectorSubtract(end, offset, endd);
360
361                 // rotate start and end into the model's frame of reference
362                 if (cangles[0] || cangles[1] || cangles[2])
363                 {
364                         AngleVectorsFLU (cangles, forward, left, up);
365                         VectorCopy(startd, tempd);
366                         startd[0] = DotProduct (tempd, forward);
367                         startd[1] = DotProduct (tempd, left);
368                         startd[2] = DotProduct (tempd, up);
369                         VectorCopy(endd, tempd);
370                         endd[0] = DotProduct (tempd, forward);
371                         endd[1] = DotProduct (tempd, left);
372                         endd[2] = DotProduct (tempd, up);
373                 }
374
375                 // trace a line through the appropriate clipping hull
376                 VectorCopy(startd, rhc.start);
377                 VectorCopy(endd, rhc.end);
378                 VectorCopy(rhc.end, rhc.trace->endpos);
379                 VectorSubtract(rhc.end, rhc.start, rhc.dist);
380                 if (DotProduct(rhc.dist, rhc.dist) > 0.00001)
381                         RecursiveHullCheck (&rhc, rhc.hull->firstclipnode, 0, 1, rhc.start, rhc.end);
382                 else
383                         RecursiveHullCheckPoint (&rhc, rhc.hull->firstclipnode);
384
385                 // if we hit, unrotate endpos and normal, and store the entity we hit
386                 if (rhc.trace->fraction != 1)
387                 {
388                         // rotate endpos back to world frame of reference
389                         if (cangles[0] || cangles[1] || cangles[2])
390                         {
391                                 VectorNegate (cangles, offset);
392                                 AngleVectorsFLU (offset, forward, left, up);
393
394                                 VectorCopy (rhc.trace->endpos, tempd);
395                                 rhc.trace->endpos[0] = DotProduct (tempd, forward);
396                                 rhc.trace->endpos[1] = DotProduct (tempd, left);
397                                 rhc.trace->endpos[2] = DotProduct (tempd, up);
398
399                                 VectorCopy (rhc.trace->plane.normal, tempd);
400                                 rhc.trace->plane.normal[0] = DotProduct (tempd, forward);
401                                 rhc.trace->plane.normal[1] = DotProduct (tempd, left);
402                                 rhc.trace->plane.normal[2] = DotProduct (tempd, up);
403                         }
404                         // fix offset
405                         VectorAdd (rhc.trace->endpos, offset, rhc.trace->endpos);
406                         rhc.trace->ent = (void *) cent;
407                 }
408                 else if (rhc.trace->allsolid || rhc.trace->startsolid)
409                         rhc.trace->ent = (void *) cent;
410         }
411         else
412         {
413                 // bounding box
414
415                 rhc.hull = HullForBBoxEntity (corigin, cmins, cmaxs, mins, maxs, offset);
416
417                 // trace a line through the generated clipping hull
418                 VectorSubtract(start, offset, rhc.start);
419                 VectorSubtract(end, offset, rhc.end);
420                 VectorCopy(rhc.end, rhc.trace->endpos);
421                 VectorSubtract(rhc.end, rhc.start, rhc.dist);
422                 if (DotProduct(rhc.dist, rhc.dist) > 0.00001)
423                         RecursiveHullCheck (&rhc, rhc.hull->firstclipnode, 0, 1, rhc.start, rhc.end);
424                 else
425                         RecursiveHullCheckPoint (&rhc, rhc.hull->firstclipnode);
426
427                 // if we hit, store the entity we hit
428                 if (rhc.trace->fraction != 1)
429                 {
430                         // fix offset
431                         VectorAdd (rhc.trace->endpos, offset, rhc.trace->endpos);
432                         rhc.trace->ent = (void *) cent;
433                 }
434                 else if (rhc.trace->allsolid || rhc.trace->startsolid)
435                         rhc.trace->ent = (void *) cent;
436         }
437 }