you can now (try to) play in maps you don't have, and models you don't have are shown...
[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 // used if start and end are the same
169 static void RecursiveHullCheckPoint (RecursiveHullCheckTraceInfo_t *t, int num)
170 {
171         // If you can read this, you understand BSP trees
172         while (num >= 0)
173                 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];
174
175         // check for empty
176         t->trace->endcontents = num;
177         if (t->trace->startcontents)
178         {
179                 if (num == t->trace->startcontents)
180                         t->trace->allsolid = false;
181                 else
182                 {
183                         // if the first leaf is solid, set startsolid
184                         if (t->trace->allsolid)
185                                 t->trace->startsolid = true;
186                 }
187         }
188         else
189         {
190                 if (num != CONTENTS_SOLID)
191                 {
192                         t->trace->allsolid = false;
193                         if (num == CONTENTS_EMPTY)
194                                 t->trace->inopen = true;
195                         else
196                                 t->trace->inwater = true;
197                 }
198                 else
199                 {
200                         // if the first leaf is solid, set startsolid
201                         if (t->trace->allsolid)
202                                 t->trace->startsolid = true;
203                 }
204         }
205 }
206
207 void Collision_RoundUpToHullSize(const model_t *cmodel, const vec3_t inmins, const vec3_t inmaxs, vec3_t outmins, vec3_t outmaxs)
208 {
209         vec3_t size;
210         const hull_t *hull;
211
212         VectorSubtract(inmaxs, inmins, size);
213         if (cmodel->ishlbsp)
214         {
215                 if (size[0] < 3)
216                         hull = &cmodel->hulls[0]; // 0x0x0
217                 else if (size[0] <= 32)
218                 {
219                         if (size[2] < 54) // pick the nearest of 36 or 72
220                                 hull = &cmodel->hulls[3]; // 32x32x36
221                         else
222                                 hull = &cmodel->hulls[1]; // 32x32x72
223                 }
224                 else
225                         hull = &cmodel->hulls[2]; // 64x64x64
226         }
227         else
228         {
229                 if (size[0] < 3)
230                         hull = &cmodel->hulls[0]; // 0x0x0
231                 else if (size[0] <= 32)
232                         hull = &cmodel->hulls[1]; // 32x32x56
233                 else
234                         hull = &cmodel->hulls[2]; // 64x64x88
235         }
236         VectorCopy(inmins, outmins);
237         VectorAdd(inmins, hull->clip_size, outmaxs);
238 }
239
240 static hull_t box_hull;
241 static dclipnode_t box_clipnodes[6];
242 static mplane_t box_planes[6];
243
244 void Collision_Init (void)
245 {
246         int             i;
247         int             side;
248
249         //Set up the planes and clipnodes so that the six floats of a bounding box
250         //can just be stored out and get a proper hull_t structure.
251
252         box_hull.clipnodes = box_clipnodes;
253         box_hull.planes = box_planes;
254         box_hull.firstclipnode = 0;
255         box_hull.lastclipnode = 5;
256
257         for (i = 0;i < 6;i++)
258         {
259                 box_clipnodes[i].planenum = i;
260
261                 side = i&1;
262
263                 box_clipnodes[i].children[side] = CONTENTS_EMPTY;
264                 if (i != 5)
265                         box_clipnodes[i].children[side^1] = i + 1;
266                 else
267                         box_clipnodes[i].children[side^1] = CONTENTS_SOLID;
268
269                 box_planes[i].type = i>>1;
270                 box_planes[i].normal[i>>1] = 1;
271         }
272 }
273
274
275 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)
276 {
277         vec3_t hullmins, hullmaxs;
278
279         // create a temp hull from bounding box sizes
280         VectorCopy (corigin, offset);
281         VectorSubtract (cmins, maxs, hullmins);
282         VectorSubtract (cmaxs, mins, hullmaxs);
283
284         //To keep everything totally uniform, bounding boxes are turned into small
285         //BSP trees instead of being compared directly.
286         box_planes[0].dist = hullmaxs[0];
287         box_planes[1].dist = hullmins[0];
288         box_planes[2].dist = hullmaxs[1];
289         box_planes[3].dist = hullmins[1];
290         box_planes[4].dist = hullmaxs[2];
291         box_planes[5].dist = hullmins[2];
292         return &box_hull;
293 }
294
295 static const hull_t *HullForBrushModel (const model_t *cmodel, const vec3_t corigin, const vec3_t mins, const vec3_t maxs, vec3_t offset)
296 {
297         vec3_t size;
298         const hull_t *hull;
299
300         // decide which clipping hull to use, based on the size
301         // explicit hulls in the BSP model
302         VectorSubtract (maxs, mins, size);
303         // LordHavoc: FIXME!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
304         if (cmodel->ishlbsp)
305         {
306                 if (size[0] < 3)
307                         hull = &cmodel->hulls[0]; // 0x0x0
308                 else if (size[0] <= 32)
309                 {
310                         if (size[2] < 54) // pick the nearest of 36 or 72
311                                 hull = &cmodel->hulls[3]; // 32x32x36
312                         else
313                                 hull = &cmodel->hulls[1]; // 32x32x72
314                 }
315                 else
316                         hull = &cmodel->hulls[2]; // 64x64x64
317         }
318         else
319         {
320                 if (size[0] < 3)
321                         hull = &cmodel->hulls[0]; // 0x0x0
322                 else if (size[0] <= 32)
323                         hull = &cmodel->hulls[1]; // 32x32x56
324                 else
325                         hull = &cmodel->hulls[2]; // 64x64x88
326         }
327
328         // calculate an offset value to center the origin
329         VectorSubtract (hull->clip_mins, mins, offset);
330         VectorAdd (offset, corigin, offset);
331
332         return hull;
333 }
334
335 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)
336 {
337         RecursiveHullCheckTraceInfo_t rhc;
338         vec3_t offset, forward, left, up;
339         double startd[3], endd[3], tempd[3];
340
341         // fill in a default trace
342         memset (&rhc, 0, sizeof(rhc));
343         memset (trace, 0, sizeof(trace_t));
344
345         rhc.trace = trace;
346
347         rhc.trace->fraction = 1;
348         rhc.trace->allsolid = true;
349
350         if (cmodel && cmodel->type == mod_brush)
351         {
352                 // brush model
353
354                 // get the clipping hull
355                 rhc.hull = HullForBrushModel (cmodel, corigin, mins, maxs, offset);
356
357                 VectorSubtract(start, offset, startd);
358                 VectorSubtract(end, offset, endd);
359
360                 // rotate start and end into the model's frame of reference
361                 if (cangles[0] || cangles[1] || cangles[2])
362                 {
363                         AngleVectorsFLU (cangles, forward, left, up);
364                         VectorCopy(startd, tempd);
365                         startd[0] = DotProduct (tempd, forward);
366                         startd[1] = DotProduct (tempd, left);
367                         startd[2] = DotProduct (tempd, up);
368                         VectorCopy(endd, tempd);
369                         endd[0] = DotProduct (tempd, forward);
370                         endd[1] = DotProduct (tempd, left);
371                         endd[2] = DotProduct (tempd, up);
372                 }
373
374                 // trace a line through the appropriate clipping hull
375                 VectorCopy(startd, rhc.start);
376                 VectorCopy(endd, rhc.end);
377                 VectorCopy(rhc.end, rhc.trace->endpos);
378                 VectorSubtract(rhc.end, rhc.start, rhc.dist);
379                 if (rhc.dist[0] || rhc.dist[1] || rhc.dist[2])
380                         RecursiveHullCheck (&rhc, rhc.hull->firstclipnode, 0, 1, rhc.start, rhc.end);
381                 else
382                         RecursiveHullCheckPoint (&rhc, rhc.hull->firstclipnode);
383
384                 // if we hit, unrotate endpos and normal, and store the entity we hit
385                 if (rhc.trace->fraction != 1)
386                 {
387                         // rotate endpos back to world frame of reference
388                         if (cangles[0] || cangles[1] || cangles[2])
389                         {
390                                 VectorNegate (cangles, offset);
391                                 AngleVectorsFLU (offset, forward, left, up);
392
393                                 VectorCopy (rhc.trace->endpos, tempd);
394                                 rhc.trace->endpos[0] = DotProduct (tempd, forward);
395                                 rhc.trace->endpos[1] = DotProduct (tempd, left);
396                                 rhc.trace->endpos[2] = DotProduct (tempd, up);
397
398                                 VectorCopy (rhc.trace->plane.normal, tempd);
399                                 rhc.trace->plane.normal[0] = DotProduct (tempd, forward);
400                                 rhc.trace->plane.normal[1] = DotProduct (tempd, left);
401                                 rhc.trace->plane.normal[2] = DotProduct (tempd, up);
402                         }
403                         rhc.trace->ent = (void *) cent;
404                 }
405                 else if (rhc.trace->allsolid || rhc.trace->startsolid)
406                         rhc.trace->ent = (void *) cent;
407                 // fix offset
408                 VectorAdd (rhc.trace->endpos, offset, rhc.trace->endpos);
409         }
410         else
411         {
412                 // bounding box
413
414                 rhc.hull = HullForBBoxEntity (corigin, cmins, cmaxs, mins, maxs, offset);
415
416                 // trace a line through the generated clipping hull
417                 VectorSubtract(start, offset, rhc.start);
418                 VectorSubtract(end, offset, rhc.end);
419                 VectorCopy(rhc.end, rhc.trace->endpos);
420                 VectorSubtract(rhc.end, rhc.start, rhc.dist);
421                 if (rhc.dist[0] || rhc.dist[1] || rhc.dist[2])
422                         RecursiveHullCheck (&rhc, rhc.hull->firstclipnode, 0, 1, rhc.start, rhc.end);
423                 else
424                         RecursiveHullCheckPoint (&rhc, rhc.hull->firstclipnode);
425
426                 // if we hit, store the entity we hit
427                 if (rhc.trace->fraction != 1)
428                 {
429                         // fix offset
430                         VectorAdd (rhc.trace->endpos, offset, rhc.trace->endpos);
431                         rhc.trace->ent = (void *) cent;
432                 }
433                 else if (rhc.trace->allsolid || rhc.trace->startsolid)
434                         rhc.trace->ent = (void *) cent;
435         }
436 }
437