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