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