moved all type-specific model fields to respective structures (alias, sprite, brush)
[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->brushq1.ishlbsp)
214         {
215                 if (size[0] < 3)
216                         hull = &cmodel->brushq1.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->brushq1.hulls[3]; // 32x32x36
221                         else
222                                 hull = &cmodel->brushq1.hulls[1]; // 32x32x72
223                 }
224                 else
225                         hull = &cmodel->brushq1.hulls[2]; // 64x64x64
226         }
227         else
228         {
229                 if (size[0] < 3)
230                         hull = &cmodel->brushq1.hulls[0]; // 0x0x0
231                 else if (size[0] <= 32)
232                         hull = &cmodel->brushq1.hulls[1]; // 32x32x56
233                 else
234                         hull = &cmodel->brushq1.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->brushq1.ishlbsp)
305         {
306                 if (size[0] < 3)
307                         hull = &cmodel->brushq1.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->brushq1.hulls[3]; // 32x32x36
312                         else
313                                 hull = &cmodel->brushq1.hulls[1]; // 32x32x72
314                 }
315                 else
316                         hull = &cmodel->brushq1.hulls[2]; // 64x64x64
317         }
318         else
319         {
320                 if (size[0] < 3)
321                         hull = &cmodel->brushq1.hulls[0]; // 0x0x0
322                 else if (size[0] <= 32)
323                         hull = &cmodel->brushq1.hulls[1]; // 32x32x56
324                 else
325                         hull = &cmodel->brushq1.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                 if (rhc.trace->fraction < 0 || rhc.trace->fraction > 1) Con_Printf("fraction out of bounds %f %s:%d\n", rhc.trace->fraction, __FILE__, __LINE__);
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                         rhc.trace->ent = (void *) cent;
405                 }
406                 else if (rhc.trace->allsolid || rhc.trace->startsolid)
407                         rhc.trace->ent = (void *) cent;
408                 // fix offset
409                 VectorAdd (rhc.trace->endpos, offset, rhc.trace->endpos);
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 (rhc.dist[0] || rhc.dist[1] || rhc.dist[2])
423                         RecursiveHullCheck (&rhc, rhc.hull->firstclipnode, 0, 1, rhc.start, rhc.end);
424                 else
425                         RecursiveHullCheckPoint (&rhc, rhc.hull->firstclipnode);
426                 if (rhc.trace->fraction < 0 || rhc.trace->fraction > 1) Con_Printf("fraction out of bounds %f %s:%d\n", rhc.trace->fraction, __FILE__, __LINE__);
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
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454 void Collision_PrintBrushAsQHull(colbrushf_t *brush, const char *name)
455 {
456         int i;
457         Con_Printf("3 %s\n%i\n", name, brush->numpoints);
458         for (i = 0;i < brush->numpoints;i++)
459                 Con_Printf("%g %g %g\n", brush->points[i].v[0], brush->points[i].v[1], brush->points[i].v[2]);
460         // FIXME: optimize!
461         Con_Printf("4\n%i\n", brush->numplanes);
462         for (i = 0;i < brush->numplanes;i++)
463                 Con_Printf("%g %g %g %g\n", brush->planes[i].normal[0], brush->planes[i].normal[1], brush->planes[i].normal[2], brush->planes[i].dist);
464 }
465
466
467 colbrushf_t *Collision_AllocBrushFloat(mempool_t *mempool, int numpoints, int numplanes)
468 {
469         colbrushf_t *brush;
470         brush = Mem_Alloc(mempool, sizeof(colbrushf_t) + sizeof(colpointf_t) * numpoints + sizeof(colplanef_t) * numplanes);
471         brush->numpoints = numpoints;
472         brush->numplanes = numplanes;
473         brush->planes = (void *)(brush + 1);
474         brush->points = (void *)(brush->planes + brush->numplanes);
475         return brush;
476 }
477
478 void Collision_CalcPlanesForPolygonBrushFloat(colbrushf_t *brush)
479 {
480         int i;
481         float edge0[3], edge1[3], normal[3], dist, bestdist;
482         colpointf_t *p, *p2;
483
484         // choose best surface normal for polygon's plane
485         bestdist = 0;
486         for (i = 0, p = brush->points + 1;i < brush->numpoints - 2;i++, p++)
487         {
488                 VectorSubtract(p[-1].v, p[0].v, edge0);
489                 VectorSubtract(p[1].v, p[0].v, edge1);
490                 CrossProduct(edge0, edge1, normal);
491                 dist = DotProduct(normal, normal);
492                 if (i == 0 || bestdist < dist)
493                 {
494                         bestdist = dist;
495                         VectorCopy(normal, brush->planes->normal);
496                 }
497         }
498
499         VectorNormalize(brush->planes->normal);
500         brush->planes->dist = DotProduct(brush->points->v, brush->planes->normal);
501
502         // negate plane to create other side
503         VectorNegate(brush->planes[0].normal, brush->planes[1].normal);
504         brush->planes[1].dist = -brush->planes[0].dist;
505         for (i = 0, p = brush->points + (brush->numpoints - 1), p2 = brush->points;i < brush->numpoints;i++, p = p2, p2++)
506         {
507                 VectorSubtract(p->v, p2->v, edge0);
508                 CrossProduct(edge0, brush->planes->normal, brush->planes[i + 2].normal);
509                 VectorNormalize(brush->planes[i + 2].normal);
510                 brush->planes[i + 2].dist = DotProduct(p->v, brush->planes[i + 2].normal);
511         }
512
513 #if 1
514         // validity check - will be disabled later
515         for (i = 0;i < brush->numplanes;i++)
516         {
517                 int j;
518                 for (j = 0, p = brush->points;j < brush->numpoints;j++, p++)
519                         if (DotProduct(p->v, brush->planes[i].normal) > brush->planes[i].dist + (1.0 / 32.0))
520                                 Con_Printf("Error in brush plane generation, plane %i\n", i);
521         }
522 #endif
523 }
524
525 colbrushf_t *Collision_AllocBrushFromPermanentPolygonFloat(mempool_t *mempool, int numpoints, float *points)
526 {
527         colbrushf_t *brush;
528         brush = Mem_Alloc(mempool, sizeof(colbrushf_t) + sizeof(colplanef_t) * (numpoints + 2));
529         brush->numpoints = numpoints;
530         brush->numplanes = numpoints + 2;
531         brush->planes = (void *)(brush + 1);
532         brush->points = (colpointf_t *)points;
533         return brush;
534 }
535
536 float nearestplanedist_float(const float *normal, const colpointf_t *points, int numpoints)
537 {
538         float dist, bestdist;
539         bestdist = DotProduct(points->v, normal);
540         points++;
541         while(--numpoints)
542         {
543                 dist = DotProduct(points->v, normal);
544                 if (bestdist > dist)
545                         bestdist = dist;
546                 points++;
547         }
548         return bestdist;
549 }
550
551 float furthestplanedist_float(const float *normal, const colpointf_t *points, int numpoints)
552 {
553         float dist, bestdist;
554         bestdist = DotProduct(points->v, normal);
555         points++;
556         while(--numpoints)
557         {
558                 dist = DotProduct(points->v, normal);
559                 if (bestdist < dist)
560                         bestdist = dist;
561                 points++;
562         }
563         return bestdist;
564 }
565
566 #define COLLISIONEPSILON (1.0f / 32.0f)
567 #define COLLISIONEPSILON2 0//(1.0f / 32.0f)
568
569 // NOTE: start and end of each brush pair must have same numplanes/numpoints
570 float Collision_TraceBrushBrushFloat(const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, const colbrushf_t *thatbrush_start, const colbrushf_t *thatbrush_end, float *impactnormal, int *startsolid, int *allsolid)
571 {
572         int nplane, nplane2, fstartsolid, fendsolid;
573         float enterfrac, leavefrac, d1, d2, f, newimpactnormal[3];
574         const colplanef_t *startplane, *endplane;
575
576         enterfrac = -1;
577         leavefrac = 1;
578         fstartsolid = true;
579         fendsolid = true;
580
581         for (nplane = 0;nplane < thatbrush_start->numplanes + thisbrush_start->numplanes;nplane++)
582         {
583                 nplane2 = nplane;
584                 if (nplane2 >= thatbrush_start->numplanes)
585                 {
586                         nplane2 -= thatbrush_start->numplanes;
587                         startplane = thisbrush_start->planes + nplane2;
588                         endplane = thisbrush_end->planes + nplane2;
589                 }
590                 else
591                 {
592                         startplane = thatbrush_start->planes + nplane2;
593                         endplane = thatbrush_end->planes + nplane2;
594                 }
595                 d1 = nearestplanedist_float(startplane->normal, thisbrush_start->points, thisbrush_start->numpoints) - furthestplanedist_float(startplane->normal, thatbrush_start->points, thatbrush_start->numpoints);
596                 d2 = nearestplanedist_float(endplane->normal, thisbrush_end->points, thisbrush_end->numpoints) - furthestplanedist_float(endplane->normal, thatbrush_end->points, thatbrush_end->numpoints) - COLLISIONEPSILON2;
597                 //Con_Printf("%c%i: d1 = %f, d2 = %f, d1 / (d1 - d2) = %f\n", nplane2 != nplane ? 'b' : 'a', nplane2, d1, d2, d1 / (d1 - d2));
598
599                 f = d1 - d2;
600                 if (f >= 0)
601                 {
602                         // moving into brush
603                         if (d2 > 0)
604                                 return 1;
605                         if (d1 < 0)
606                                 continue;
607                         // enter
608                         fstartsolid = false;
609                         f = (d1 - COLLISIONEPSILON) / f;
610                         f = bound(0, f, 1);
611                         if (enterfrac < f)
612                         {
613                                 enterfrac = f;
614                                 VectorBlend(startplane->normal, endplane->normal, enterfrac, newimpactnormal);
615                         }
616                 }
617                 else if (f < 0)
618                 {
619                         // moving out of brush
620                         if (d1 > 0)
621                                 return 1;
622                         if (d2 < 0)
623                                 continue;
624                         // leave
625                         fendsolid = false;
626                         f = (d1 + COLLISIONEPSILON) / f;
627                         f = bound(0, f, 1);
628                         if (leavefrac > f)
629                                 leavefrac = f;
630                 }
631         }
632
633         if (fstartsolid)
634         {
635                 if (startsolid)
636                         *startsolid = true;
637                 if (fendsolid && allsolid)
638                         *allsolid = true;
639         }
640
641         // LordHavoc: we need an epsilon nudge here because for a point trace the
642         // penetrating line segment is normally zero length if this brush was
643         // generated from a polygon (infinitely thin), and could even be slightly
644         // positive or negative due to rounding errors in that case.
645         if (enterfrac > -1 && enterfrac < 1 && enterfrac - (1.0f / 1024.0f) <= leavefrac)
646         {
647                 //if (enterfrac < (1.0f / 1024.0f))
648                 //      enterfrac = 0;
649                 enterfrac = bound(0, enterfrac, 1);
650                 VectorCopy(newimpactnormal, impactnormal);
651                 return enterfrac;
652         }
653         return 1;
654 }
655
656 static colplanef_t polyf_planes[256 + 2];
657 static colbrushf_t polyf_brush;
658
659 float Collision_TraceBrushPolygonFloat(const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, int numpoints, const float *points, float *impactnormal, int *startsolid, int *allsolid)
660 {
661         if (numpoints > 256)
662         {
663                 Con_Printf("Polygon with more than 256 points not supported yet (fixme!)\n");
664                 return 1;
665         }
666         polyf_brush.numpoints = numpoints;
667         polyf_brush.numplanes = numpoints + 2;
668         polyf_brush.points = (colpointf_t *)points;
669         polyf_brush.planes = polyf_planes;
670         Collision_CalcPlanesForPolygonBrushFloat(&polyf_brush);
671         //Collision_PrintBrushAsQHull(&polyf_brush, "polyf_brush");
672         return Collision_TraceBrushBrushFloat(thisbrush_start, thisbrush_end, &polyf_brush, &polyf_brush, impactnormal, startsolid, allsolid);
673 }
674
675 static colpointf_t polyf_pointsstart[256], polyf_pointsend[256];
676 static colplanef_t polyf_planesstart[256 + 2], polyf_planesend[256 + 2];
677 static colbrushf_t polyf_brushstart, polyf_brushend;
678
679 float Collision_TraceBrushPolygonTransformFloat(const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, int numpoints, const float *points, float *impactnormal, const matrix4x4_t *polygonmatrixstart, const matrix4x4_t *polygonmatrixend, int *startsolid, int *allsolid)
680 {
681         int i;
682         if (numpoints > 256)
683         {
684                 Con_Printf("Polygon with more than 256 points not supported yet (fixme!)\n");
685                 return 1;
686         }
687         polyf_brushstart.numpoints = numpoints;
688         polyf_brushstart.numplanes = numpoints + 2;
689         polyf_brushstart.points = polyf_pointsstart;//(colpointf_t *)points;
690         polyf_brushstart.planes = polyf_planesstart;
691         for (i = 0;i < numpoints;i++)
692                 Matrix4x4_Transform(polygonmatrixstart, points + i * 3, polyf_brushstart.points[i].v);
693         polyf_brushend.numpoints = numpoints;
694         polyf_brushend.numplanes = numpoints + 2;
695         polyf_brushend.points = polyf_pointsend;//(colpointf_t *)points;
696         polyf_brushend.planes = polyf_planesend;
697         for (i = 0;i < numpoints;i++)
698                 Matrix4x4_Transform(polygonmatrixend, points + i * 3, polyf_brushend.points[i].v);
699         Collision_CalcPlanesForPolygonBrushFloat(&polyf_brushstart);
700         Collision_CalcPlanesForPolygonBrushFloat(&polyf_brushend);
701
702         //Collision_PrintBrushAsQHull(&polyf_brushstart, "polyf_brushstart");
703         //Collision_PrintBrushAsQHull(&polyf_brushend, "polyf_brushend");
704
705         return Collision_TraceBrushBrushFloat(thisbrush_start, thisbrush_end, &polyf_brushstart, &polyf_brushend, impactnormal, startsolid, allsolid);
706 }
707
708 colbrushd_t *Collision_AllocBrushDouble(mempool_t *mempool, int numpoints, int numplanes)
709 {
710         colbrushd_t *brush;
711         brush = Mem_Alloc(mempool, sizeof(colbrushd_t) + sizeof(colpointd_t) * numpoints + sizeof(colplaned_t) * numplanes);
712         brush->numpoints = numpoints;
713         brush->numplanes = numplanes;
714         brush->planes = (void *)(brush + 1);
715         brush->points = (void *)(brush->planes + brush->numplanes);
716         return brush;
717 }
718
719 void Collision_CalcPlanesForPolygonBrushDouble(colbrushd_t *brush)
720 {
721         int i;
722         double edge0[3], edge1[3], normal[3], dist, bestdist;
723         colpointd_t *p, *p2;
724
725         // choose best surface normal for polygon's plane
726         bestdist = 0;
727         for (i = 2, p = brush->points + 2;i < brush->numpoints;i++, p++)
728         {
729                 VectorSubtract(p[-1].v, p[0].v, edge0);
730                 VectorSubtract(p[1].v, p[0].v, edge1);
731                 CrossProduct(edge0, edge1, normal);
732                 dist = DotProduct(normal, normal);
733                 if (i == 2 || bestdist < dist)
734                 {
735                         bestdist = dist;
736                         VectorCopy(normal, brush->planes->normal);
737                 }
738         }
739
740         VectorNormalize(brush->planes->normal);
741         brush->planes->dist = DotProduct(brush->points->v, brush->planes->normal);
742
743         // negate plane to create other side
744         VectorNegate(brush->planes[0].normal, brush->planes[1].normal);
745         brush->planes[1].dist = -brush->planes[0].dist;
746         for (i = 0, p = brush->points + (brush->numpoints - 1), p2 = brush->points + 2;i < brush->numpoints;i++, p = p2, p2++)
747         {
748                 VectorSubtract(p->v, p2->v, edge0);
749                 CrossProduct(edge0, brush->planes->normal, brush->planes[i].normal);
750                 VectorNormalize(brush->planes[i].normal);
751                 brush->planes[i].dist = DotProduct(p->v, brush->planes[i].normal);
752         }
753
754 #if 1
755         // validity check - will be disabled later
756         for (i = 0;i < brush->numplanes;i++)
757         {
758                 int j;
759                 for (j = 0, p = brush->points;j < brush->numpoints;j++, p++)
760                         if (DotProduct(p->v, brush->planes[i].normal) > brush->planes[i].dist + (1.0 / 32.0))
761                                 Con_Printf("Error in brush plane generation, plane %i\n");
762         }
763 #endif
764 }
765
766 colbrushd_t *Collision_AllocBrushFromPermanentPolygonDouble(mempool_t *mempool, int numpoints, double *points)
767 {
768         colbrushd_t *brush;
769         brush = Mem_Alloc(mempool, sizeof(colbrushd_t) + sizeof(colplaned_t) * (numpoints + 2));
770         brush->numpoints = numpoints;
771         brush->numplanes = numpoints + 2;
772         brush->planes = (void *)(brush + 1);
773         brush->points = (colpointd_t *)points;
774         return brush;
775 }
776
777
778 double nearestplanedist_double(const double *normal, const colpointd_t *points, int numpoints)
779 {
780         double dist, bestdist;
781         bestdist = DotProduct(points->v, normal);
782         points++;
783         while(--numpoints)
784         {
785                 dist = DotProduct(points->v, normal);
786                 if (bestdist > dist)
787                         bestdist = dist;
788                 points++;
789         }
790         return bestdist;
791 }
792
793 double furthestplanedist_double(const double *normal, const colpointd_t *points, int numpoints)
794 {
795         double dist, bestdist;
796         bestdist = DotProduct(points->v, normal);
797         points++;
798         while(--numpoints)
799         {
800                 dist = DotProduct(points->v, normal);
801                 if (bestdist < dist)
802                         bestdist = dist;
803                 points++;
804         }
805         return bestdist;
806 }
807
808 // NOTE: start and end of each brush pair must have same numplanes/numpoints
809 double Collision_TraceBrushBrushDouble(const colbrushd_t *thisbrush_start, const colbrushd_t *thisbrush_end, const colbrushd_t *thatbrush_start, const colbrushd_t *thatbrush_end, double *impactnormal)
810 {
811         int nplane;
812         double enterfrac, leavefrac, d1, d2, f, newimpactnormal[3];
813         const colplaned_t *startplane, *endplane;
814
815         enterfrac = -1;
816         leavefrac = 1;
817
818         for (nplane = 0;nplane < thatbrush_start->numplanes;nplane++)
819         {
820                 startplane = thatbrush_start->planes + nplane;
821                 endplane = thatbrush_end->planes + nplane;
822                 d1 = nearestplanedist_double(startplane->normal, thisbrush_start->points, thisbrush_start->numpoints) - furthestplanedist_double(startplane->normal, thatbrush_start->points, thatbrush_start->numpoints);
823                 d2 = nearestplanedist_double(endplane->normal, thisbrush_end->points, thisbrush_start->numpoints) - furthestplanedist_double(endplane->normal, thatbrush_end->points, thatbrush_start->numpoints) - (1.0 / 32.0);
824
825                 f = d1 - d2;
826                 if (f >= 0)
827                 {
828                         // moving into brush
829                         if (d2 > 0)
830                                 return 1;
831                         if (d1 < 0)
832                                 continue;
833                         // enter
834                         f = d1 / f;
835                         if (enterfrac < f)
836                         {
837                                 enterfrac = f;
838                                 VectorSubtract(endplane->normal, startplane->normal, newimpactnormal);
839                                 VectorMA(startplane->normal, enterfrac, impactnormal, newimpactnormal);
840                         }
841                 }
842                 else
843                 {
844                         // moving out of brush
845                         if (d1 > 0)
846                                 return 1;
847                         if (d2 < 0)
848                                 continue;
849                         // leave
850                         f = d1 / f;
851                         if (leavefrac > f)
852                                 leavefrac = f;
853                 }
854         }
855
856         for (nplane = 0;nplane < thisbrush_start->numplanes;nplane++)
857         {
858                 startplane = thisbrush_start->planes + nplane;
859                 endplane = thisbrush_end->planes + nplane;
860                 d1 = nearestplanedist_double(startplane->normal, thisbrush_start->points, thisbrush_start->numpoints) - furthestplanedist_double(startplane->normal, thatbrush_start->points, thatbrush_start->numpoints);
861                 d2 = nearestplanedist_double(endplane->normal, thisbrush_end->points, thisbrush_start->numpoints) - furthestplanedist_double(endplane->normal, thatbrush_end->points, thatbrush_start->numpoints) - (1.0 / 32.0);
862
863                 f = d1 - d2;
864                 if (f >= 0)
865                 {
866                         // moving into brush
867                         if (d2 > 0)
868                                 return 1;
869                         if (d1 < 0)
870                                 continue;
871                         // enter
872                         f = d1 / f;
873                         if (enterfrac < f)
874                         {
875                                 enterfrac = f;
876                                 VectorSubtract(endplane->normal, startplane->normal, newimpactnormal);
877                                 VectorMA(startplane->normal, enterfrac, impactnormal, newimpactnormal);
878                         }
879                 }
880                 else
881                 {
882                         // moving out of brush
883                         if (d1 > 0)
884                                 return 1;
885                         if (d2 < 0)
886                                 continue;
887                         // leave
888                         f = d1 / f;
889                         if (leavefrac > f)
890                                 leavefrac = f;
891                 }
892         }
893
894         // LordHavoc: we need an epsilon nudge here because for a point trace the
895         // penetrating line segment is normally zero length if this brush was
896         // generated from a polygon (infinitely thin), and could even be slightly
897         // positive or negative due to rounding errors in that case.
898         enterfrac -= (1.0 / 16384.0);
899         if (leavefrac - enterfrac >= 0 && enterfrac > -1)
900         {
901                 VectorCopy(newimpactnormal, impactnormal);
902                 enterfrac = bound(0, enterfrac, 1);
903                 return enterfrac;
904         }
905         return 1;
906 }
907
908 static colplaned_t polyd_planes[256 + 2];
909 static colbrushd_t polyd_brush;
910 double Collision_TraceBrushPolygonDouble(const colbrushd_t *thisbrush_start, const colbrushd_t *thisbrush_end, int numpoints, const double *points, double *impactnormal)
911 {
912         if (numpoints > 256)
913         {
914                 Con_Printf("Polygon with more than 256 points not supported yet (fixme!)\n");
915                 return 1;
916         }
917         polyd_brush.numpoints = numpoints;
918         polyd_brush.numplanes = numpoints + 2;
919         polyd_brush.points = (colpointd_t *)points;
920         polyd_brush.planes = polyd_planes;
921         Collision_CalcPlanesForPolygonBrushDouble(&polyd_brush);
922         return Collision_TraceBrushBrushDouble(thisbrush_start, thisbrush_end, &polyd_brush, &polyd_brush, impactnormal);
923 }
924
925
926
927
928 typedef struct colbrushbmodelinfo_s
929 {
930         model_t *model;
931         const matrix4x4_t *modelmatrixstart;
932         const matrix4x4_t *modelmatrixend;
933         const colbrushf_t *thisbrush_start;
934         const colbrushf_t *thisbrush_end;
935         float impactnormal[3];
936         float tempimpactnormal[3];
937         float fraction;
938         int startsolid;
939         int allsolid;
940 }
941 colbrushbmodelinfo_t;
942
943 static int colframecount = 1;
944
945 void Collision_RecursiveTraceBrushNode(colbrushbmodelinfo_t *info, mnode_t *node)
946 {
947         if (node->contents)
948         {
949                 // collide with surfaces marked by this leaf
950                 int i, *mark;
951                 float result;
952                 mleaf_t *leaf = (mleaf_t *)node;
953                 msurface_t *surf;
954                 for (i = 0, mark = leaf->firstmarksurface;i < leaf->nummarksurfaces;i++, mark++)
955                 {
956                         surf = info->model->brushq1.surfaces + *mark;
957                         // don't check a surface twice
958                         if (surf->colframe != colframecount)
959                         {
960                                 surf->colframe = colframecount;
961                                 if (surf->flags & SURF_SOLIDCLIP)
962                                 {
963                                         result = Collision_TraceBrushPolygonFloat(info->thisbrush_start, info->thisbrush_end, surf->poly_numverts, surf->poly_verts, info->tempimpactnormal, &info->startsolid, &info->allsolid);
964                                         //result = Collision_TraceBrushPolygonTransformFloat(info->thisbrush_start, info->thisbrush_end, surf->poly_numverts, surf->poly_verts, info->tempimpactnormal, info->modelmatrixstart, info->modelmatrixend, &info->startsolid, &info->allsolid);
965                                         if (info->fraction > result)
966                                         {
967                                                 info->fraction = result;
968                                                 // use the surface's plane instead of the actual
969                                                 // collision plane because the actual collision plane
970                                                 // might be to the side (on a seam between polygons)
971                                                 // or something, we want objects to bounce off the
972                                                 // front...
973                                                 //if (surf->flags & SURF_PLANEBACK)
974                                                 //      VectorNegate(surf->plane->normal, info->impactnormal);
975                                                 //else
976                                                 //      VectorCopy(surf->plane->normal, info->impactnormal);
977                                                 VectorCopy(info->tempimpactnormal, info->impactnormal);
978                                         }
979                                 }
980                         }
981                 }
982         }
983         else
984         {
985                 // recurse down node sides
986                 int i, bits;
987                 float dist1, dist2;
988                 colpointf_t *ps, *pe;
989                 bits = 0;
990                 // FIXME? if TraceBrushPolygonTransform were to be made usable, the
991                 // node planes would need to be transformed too
992                 dist1 = node->plane->dist - (1.0f / 8.0f);
993                 dist2 = node->plane->dist + (1.0f / 8.0f);
994                 for (i = 0, ps = info->thisbrush_start->points, pe = info->thisbrush_end->points;i < info->thisbrush_start->numpoints;i++, ps++, pe++)
995                 {
996                         if (!(bits & 1) && (DotProduct(ps->v, node->plane->normal) > dist1 || DotProduct(pe->v, node->plane->normal) > dist1))
997                                 bits |= 1;
998                         if (!(bits & 2) && (DotProduct(ps->v, node->plane->normal) < dist2 || DotProduct(pe->v, node->plane->normal) < dist2))
999                                 bits |= 2;
1000                 }
1001                 if (bits & 1)
1002                         Collision_RecursiveTraceBrushNode(info, node->children[0]);
1003                 if (bits & 2)
1004                         Collision_RecursiveTraceBrushNode(info, node->children[1]);
1005         }
1006 }
1007
1008 float Collision_TraceBrushBModel(const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, model_t *model, float *impactnormal, int *startsolid, int *allsolid)
1009 {
1010         colbrushbmodelinfo_t info;
1011         colframecount++;
1012         info.model = model;
1013         info.thisbrush_start = thisbrush_start;
1014         info.thisbrush_end = thisbrush_end;
1015         info.fraction = 1;
1016         info.startsolid = false;
1017         info.allsolid = false;
1018         Collision_RecursiveTraceBrushNode(&info, model->brushq1.nodes + model->brushq1.hulls[0].firstclipnode);
1019         if (info.fraction < 1)
1020                 VectorCopy(info.impactnormal, impactnormal);
1021         if (startsolid)
1022                 *startsolid = info.startsolid;
1023         if (allsolid)
1024                 *allsolid = info.allsolid;
1025         return info.fraction;
1026 }
1027
1028 float Collision_TraceBrushBModelTransform(const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, model_t *model, float *impactnormal, const matrix4x4_t *modelmatrixstart, const matrix4x4_t *modelmatrixend, int *startsolid, int *allsolid)
1029 {
1030         colbrushbmodelinfo_t info;
1031         colframecount++;
1032         info.model = model;
1033         info.modelmatrixstart = modelmatrixstart;
1034         info.modelmatrixend = modelmatrixend;
1035         info.thisbrush_start = thisbrush_start;
1036         info.thisbrush_end = thisbrush_end;
1037         info.fraction = 1;
1038         info.startsolid = false;
1039         info.allsolid = false;
1040         Collision_RecursiveTraceBrushNode(&info, model->brushq1.nodes);
1041         if (info.fraction < 1)
1042                 VectorCopy(info.impactnormal, impactnormal);
1043         if (startsolid)
1044                 *startsolid = info.startsolid;
1045         if (allsolid)
1046                 *allsolid = info.allsolid;
1047         return info.fraction;
1048 }
1049
1050
1051
1052 #define MAX_BRUSHFORBOX 16
1053 static int brushforbox_index = 0;
1054 static colpointf_t brushforbox_point[MAX_BRUSHFORBOX*8];
1055 static colplanef_t brushforbox_plane[MAX_BRUSHFORBOX*6];
1056 static colbrushf_t brushforbox_brush[MAX_BRUSHFORBOX];
1057
1058 void Collision_InitBrushForBox(void)
1059 {
1060         int i;
1061         for (i = 0;i < MAX_BRUSHFORBOX;i++)
1062         {
1063                 brushforbox_brush[i].numpoints = 8;
1064                 brushforbox_brush[i].numplanes = 6;
1065                 brushforbox_brush[i].points = brushforbox_point + i * 8;
1066                 brushforbox_brush[i].planes = brushforbox_plane + i * 6;
1067         }
1068 }
1069
1070 colbrushf_t *Collision_BrushForBox(const matrix4x4_t *matrix, const vec3_t mins, const vec3_t maxs)
1071 {
1072         int i;
1073         vec3_t v;
1074         colbrushf_t *brush;
1075         if (brushforbox_brush[0].numpoints == 0)
1076                 Collision_InitBrushForBox();
1077         brush = brushforbox_brush + ((brushforbox_index++) % MAX_BRUSHFORBOX);
1078         // FIXME: optimize
1079         for (i = 0;i < 8;i++)
1080         {
1081                 v[0] = i & 1 ? maxs[0] : mins[0];
1082                 v[1] = i & 2 ? maxs[1] : mins[1];
1083                 v[2] = i & 4 ? maxs[2] : mins[2];
1084                 Matrix4x4_Transform(matrix, v, brush->points[i].v);
1085         }
1086         // FIXME: optimize!
1087         for (i = 0;i < 6;i++)
1088         {
1089                 VectorClear(v);
1090                 v[i >> 1] = i & 1 ? 1 : -1;
1091                 Matrix4x4_Transform3x3(matrix, v, brush->planes[i].normal);
1092                 VectorNormalize(brush->planes[i].normal);
1093                 brush->planes[i].dist = furthestplanedist_float(brush->planes[i].normal, brush->points, brush->numpoints);
1094         }
1095         return brush;
1096 }
1097
1098 void Collision_PolygonClipTrace (trace_t *trace, const void *cent, 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)
1099 {
1100         vec3_t impactnormal;
1101         //vec3_t mins2, maxs2;
1102         matrix4x4_t cmatrix, cimatrix, startmatrix, endmatrix;
1103         matrix4x4_t mstartmatrix, mendmatrix, identitymatrix;
1104         colbrushf_t *thisbrush_start, *thisbrush_end, *cbrush;
1105
1106         Matrix4x4_CreateFromQuakeEntity(&cmatrix, corigin[0], corigin[1], corigin[2], cangles[0], cangles[1], cangles[2], 1);
1107         Matrix4x4_Invert_Simple(&cimatrix, &cmatrix);
1108         Matrix4x4_CreateTranslate(&startmatrix, start[0], start[1], start[2]);
1109         Matrix4x4_CreateTranslate(&endmatrix, end[0], end[1], end[2]);
1110
1111         Matrix4x4_CreateIdentity(&identitymatrix);
1112         Matrix4x4_Concat(&mstartmatrix, &cimatrix, &startmatrix);
1113         Matrix4x4_Concat(&mendmatrix, &cimatrix, &endmatrix);
1114         thisbrush_start = Collision_BrushForBox(&mstartmatrix, mins, maxs);
1115         //mins2[0] = mins[0] - 0.0625;mins2[1] = mins[1] - 0.0625;mins2[2] = mins[2] - 0.0625;
1116         //maxs2[0] = maxs[0] + 0.0625;maxs2[1] = maxs[1] + 0.0625;maxs2[2] = maxs[2] + 0.0625;
1117         thisbrush_end = Collision_BrushForBox(&mendmatrix, mins, maxs);
1118
1119         //Collision_PrintBrushAsQHull(thisbrush_start, "thisbrush_start");
1120         //Collision_PrintBrushAsQHull(thisbrush_end, "thisbrush_end");
1121         memset (trace, 0, sizeof(trace_t));
1122         if (cmodel && cmodel->type == mod_brush)
1123         {
1124                 // brush model
1125                 trace->fraction = Collision_TraceBrushBModel(thisbrush_start, thisbrush_end, cmodel, impactnormal, &trace->startsolid, &trace->allsolid);
1126                 //trace->fraction = Collision_TraceBrushBModelTransform(thisbrush_start, thisbrush_end, cmodel, trace->plane.normal, &cmatrix, &cmatrix, &trace->startsolid, &trace->allsolid);
1127         }
1128         else
1129         {
1130                 // bounding box
1131                 cbrush = Collision_BrushForBox(&identitymatrix, cmins, cmaxs);
1132                 trace->fraction = Collision_TraceBrushBrushFloat(thisbrush_start, thisbrush_end, cbrush, cbrush, impactnormal, &trace->startsolid, &trace->allsolid);
1133                 //cbrush = Collision_BrushForBox(&cmatrix, cmins, cmaxs);
1134                 //trace->fraction = Collision_TraceBrushBrushFloat(thisbrush_start, thisbrush_end, cbrush, cbrush, trace->plane.normal, &trace->startsolid, &trace->allsolid);
1135         }
1136
1137         if (trace->fraction < 0 || trace->fraction > 1)
1138                 Con_Printf("fraction out of bounds %f %s:%d\n", trace->fraction, __FILE__, __LINE__);
1139
1140         if (trace->fraction < 1)
1141         {
1142                 trace->ent = (void *) cent;
1143                 VectorBlend(start, end, trace->fraction, trace->endpos);
1144                 Matrix4x4_Transform(&cmatrix, impactnormal, trace->plane.normal);
1145                 VectorNormalize(trace->plane.normal);
1146                 //Con_Printf("fraction %f normal %f %f %f\n", trace->fraction, trace->plane.normal[0], trace->plane.normal[1], trace->plane.normal[2]);
1147         }
1148         else
1149                 VectorCopy(end, trace->endpos);
1150 }
1151