Added developer_memorylargerthanmb cvar which dprints notices about very large memory...
[xonotic/darkplaces.git] / collision.c
1
2 #include "quakedef.h"
3 #include "polygon.h"
4
5 #define COLLISION_EDGEDIR_DOT_EPSILON (0.999f)
6 #define COLLISION_EDGECROSS_MINLENGTH2 (1.0f / 4194304.0f)
7 #define COLLISION_SNAPSCALE (32.0f)
8 #define COLLISION_SNAP (1.0f / COLLISION_SNAPSCALE)
9 #define COLLISION_SNAP2 (2.0f / COLLISION_SNAPSCALE)
10 #define COLLISION_PLANE_DIST_EPSILON (2.0f / COLLISION_SNAPSCALE)
11
12 cvar_t collision_impactnudge = {0, "collision_impactnudge", "0.03125", "how much to back off from the impact"};
13 cvar_t collision_extendmovelength = {0, "collision_extendmovelength", "16", "internal bias on trace length to ensure detection of collisions within the collision_impactnudge distance so that short moves do not degrade across frames (this does not alter the final trace length)"};
14 cvar_t collision_extendtraceboxlength = {0, "collision_extendtraceboxlength", "1", "internal bias for tracebox() qc builtin to account for collision_impactnudge (this does not alter the final trace length)"};
15 cvar_t collision_extendtracelinelength = {0, "collision_extendtracelinelength", "1", "internal bias for traceline() qc builtin to account for collision_impactnudge (this does not alter the final trace length)"};
16 cvar_t collision_debug_tracelineasbox = {0, "collision_debug_tracelineasbox", "0", "workaround for any bugs in Collision_TraceLineBrushFloat by using Collision_TraceBrushBrushFloat"};
17 cvar_t collision_cache = {0, "collision_cache", "1", "store results of collision traces for next frame to reuse if possible (optimization)"};
18 //cvar_t collision_triangle_neighborsides = {0, "collision_triangle_neighborsides", "1", "override automatic side generation if triangle has neighbors with face planes that form a convex edge (perfect solution, but can not work for all edges)"};
19 cvar_t collision_triangle_bevelsides = {0, "collision_triangle_bevelsides", "0", "generate sloped edge planes on triangles - if 0, see axialedgeplanes"};
20 cvar_t collision_triangle_axialsides = {0, "collision_triangle_axialsides", "1", "generate axially-aligned edge planes on triangles - otherwise use perpendicular edge planes"};
21
22 mempool_t *collision_mempool;
23
24 void Collision_Init (void)
25 {
26         Cvar_RegisterVariable(&collision_impactnudge);
27         Cvar_RegisterVariable(&collision_extendmovelength);
28         Cvar_RegisterVariable(&collision_extendtracelinelength);
29         Cvar_RegisterVariable(&collision_extendtraceboxlength);
30         Cvar_RegisterVariable(&collision_debug_tracelineasbox);
31         Cvar_RegisterVariable(&collision_cache);
32 //      Cvar_RegisterVariable(&collision_triangle_neighborsides);
33         Cvar_RegisterVariable(&collision_triangle_bevelsides);
34         Cvar_RegisterVariable(&collision_triangle_axialsides);
35         collision_mempool = Mem_AllocPool("collision cache", 0, NULL);
36         Collision_Cache_Init(collision_mempool);
37 }
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52 static void Collision_PrintBrushAsQHull(colbrushf_t *brush, const char *name)
53 {
54         int i;
55         Con_Printf("3 %s\n%i\n", name, brush->numpoints);
56         for (i = 0;i < brush->numpoints;i++)
57                 Con_Printf("%f %f %f\n", brush->points[i].v[0], brush->points[i].v[1], brush->points[i].v[2]);
58         // FIXME: optimize!
59         Con_Printf("4\n%i\n", brush->numplanes);
60         for (i = 0;i < brush->numplanes;i++)
61                 Con_Printf("%f %f %f %f\n", brush->planes[i].normal[0], brush->planes[i].normal[1], brush->planes[i].normal[2], brush->planes[i].dist);
62 }
63
64 static void Collision_ValidateBrush(colbrushf_t *brush)
65 {
66         int j, k, pointsoffplanes, pointonplanes, pointswithinsufficientplanes, printbrush;
67         float d;
68         printbrush = false;
69         if (!brush->numpoints)
70         {
71                 Con_Print("Collision_ValidateBrush: brush with no points!\n");
72                 printbrush = true;
73         }
74 #if 0
75         // it's ok for a brush to have one point and no planes...
76         if (brush->numplanes == 0 && brush->numpoints != 1)
77         {
78                 Con_Print("Collision_ValidateBrush: brush with no planes and more than one point!\n");
79                 printbrush = true;
80         }
81 #endif
82         if (brush->numplanes)
83         {
84                 pointsoffplanes = 0;
85                 pointswithinsufficientplanes = 0;
86                 for (k = 0;k < brush->numplanes;k++)
87                         if (DotProduct(brush->planes[k].normal, brush->planes[k].normal) < 0.0001f)
88                                 Con_Printf("Collision_ValidateBrush: plane #%i (%f %f %f %f) is degenerate\n", k, brush->planes[k].normal[0], brush->planes[k].normal[1], brush->planes[k].normal[2], brush->planes[k].dist);
89                 for (j = 0;j < brush->numpoints;j++)
90                 {
91                         pointonplanes = 0;
92                         for (k = 0;k < brush->numplanes;k++)
93                         {
94                                 d = DotProduct(brush->points[j].v, brush->planes[k].normal) - brush->planes[k].dist;
95                                 if (d > COLLISION_PLANE_DIST_EPSILON)
96                                 {
97                                         Con_Printf("Collision_ValidateBrush: point #%i (%f %f %f) infront of plane #%i (%f %f %f %f)\n", j, brush->points[j].v[0], brush->points[j].v[1], brush->points[j].v[2], k, brush->planes[k].normal[0], brush->planes[k].normal[1], brush->planes[k].normal[2], brush->planes[k].dist);
98                                         printbrush = true;
99                                 }
100                                 if (fabs(d) > COLLISION_PLANE_DIST_EPSILON)
101                                         pointsoffplanes++;
102                                 else
103                                         pointonplanes++;
104                         }
105                         if (pointonplanes < 3)
106                                 pointswithinsufficientplanes++;
107                 }
108                 if (pointswithinsufficientplanes)
109                 {
110                         Con_Print("Collision_ValidateBrush: some points have insufficient planes, every point must be on at least 3 planes to form a corner.\n");
111                         printbrush = true;
112                 }
113                 if (pointsoffplanes == 0) // all points are on all planes
114                 {
115                         Con_Print("Collision_ValidateBrush: all points lie on all planes (degenerate, no brush volume!)\n");
116                         printbrush = true;
117                 }
118         }
119         if (printbrush)
120                 Collision_PrintBrushAsQHull(brush, "unnamed");
121 }
122
123 static float nearestplanedist_float(const float *normal, const colpointf_t *points, int numpoints)
124 {
125         float dist, bestdist;
126         if (!numpoints)
127                 return 0;
128         bestdist = DotProduct(points->v, normal);
129         points++;
130         while(--numpoints)
131         {
132                 dist = DotProduct(points->v, normal);
133                 bestdist = min(bestdist, dist);
134                 points++;
135         }
136         return bestdist;
137 }
138
139 static float furthestplanedist_float(const float *normal, const colpointf_t *points, int numpoints)
140 {
141         float dist, bestdist;
142         if (!numpoints)
143                 return 0;
144         bestdist = DotProduct(points->v, normal);
145         points++;
146         while(--numpoints)
147         {
148                 dist = DotProduct(points->v, normal);
149                 bestdist = max(bestdist, dist);
150                 points++;
151         }
152         return bestdist;
153 }
154
155 static void Collision_CalcEdgeDirsForPolygonBrushFloat(colbrushf_t *brush)
156 {
157         int i, j;
158         for (i = 0, j = brush->numpoints - 1;i < brush->numpoints;j = i, i++)
159                 VectorSubtract(brush->points[i].v, brush->points[j].v, brush->edgedirs[j].v);
160 }
161
162 colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalplanes, const colplanef_t *originalplanes, int supercontents, int q3surfaceflags, const texture_t *texture, int hasaabbplanes)
163 {
164         // TODO: planesbuf could be replaced by a remapping table
165         int j, k, w, xyzflags;
166         int numpointsbuf = 0, maxpointsbuf = 256, numedgedirsbuf = 0, maxedgedirsbuf = 256, numplanesbuf = 0, maxplanesbuf = 256, numelementsbuf = 0, maxelementsbuf = 256;
167         int isaabb = true;
168         double maxdist;
169         colbrushf_t *brush;
170         colpointf_t pointsbuf[256];
171         colpointf_t edgedirsbuf[256];
172         colplanef_t planesbuf[256];
173         int elementsbuf[1024];
174         int polypointbuf[256];
175         int pmaxpoints = 64;
176         int pnumpoints;
177         double p[2][3*64];
178 #if 0
179         // enable these if debugging to avoid seeing garbage in unused data-
180         memset(pointsbuf, 0, sizeof(pointsbuf));
181         memset(edgedirsbuf, 0, sizeof(edgedirsbuf));
182         memset(planesbuf, 0, sizeof(planesbuf));
183         memset(elementsbuf, 0, sizeof(elementsbuf));
184         memset(polypointbuf, 0, sizeof(polypointbuf));
185         memset(p, 0, sizeof(p));
186 #endif
187
188         // check if there are too many planes and skip the brush
189         if (numoriginalplanes >= maxplanesbuf)
190         {
191                 Con_DPrint("Collision_NewBrushFromPlanes: failed to build collision brush: too many planes for buffer\n");
192                 return NULL;
193         }
194
195         // figure out how large a bounding box we need to properly compute this brush
196         maxdist = 0;
197         for (j = 0;j < numoriginalplanes;j++)
198                 maxdist = max(maxdist, fabs(originalplanes[j].dist));
199         // now make it large enough to enclose the entire brush, and round it off to a reasonable multiple of 1024
200         maxdist = floor(maxdist * (4.0 / 1024.0) + 2) * 1024.0;
201         // construct a collision brush (points, planes, and renderable mesh) from
202         // a set of planes, this also optimizes out any unnecessary planes (ones
203         // whose polygon is clipped away by the other planes)
204         for (j = 0;j < numoriginalplanes;j++)
205         {
206                 int n;
207                 // add the new plane
208                 VectorCopy(originalplanes[j].normal, planesbuf[numplanesbuf].normal);
209                 planesbuf[numplanesbuf].dist = originalplanes[j].dist;
210                 planesbuf[numplanesbuf].q3surfaceflags = originalplanes[j].q3surfaceflags;
211                 planesbuf[numplanesbuf].texture = originalplanes[j].texture;
212                 numplanesbuf++;
213
214                 // create a large polygon from the plane
215                 w = 0;
216                 PolygonD_QuadForPlane(p[w], originalplanes[j].normal[0], originalplanes[j].normal[1], originalplanes[j].normal[2], originalplanes[j].dist, maxdist);
217                 pnumpoints = 4;
218                 // clip it by all other planes
219                 for (k = 0;k < numoriginalplanes && pnumpoints >= 3 && pnumpoints <= pmaxpoints;k++)
220                 {
221                         // skip the plane this polygon
222                         // (nothing happens if it is processed, this is just an optimization)
223                         if (k != j)
224                         {
225                                 // we want to keep the inside of the brush plane so we flip
226                                 // the cutting plane
227                                 PolygonD_Divide(pnumpoints, p[w], -originalplanes[k].normal[0], -originalplanes[k].normal[1], -originalplanes[k].normal[2], -originalplanes[k].dist, COLLISION_PLANE_DIST_EPSILON, pmaxpoints, p[!w], &pnumpoints, 0, NULL, NULL, NULL);
228                                 w = !w;
229                         }
230                 }
231
232                 // if nothing is left, skip it
233                 if (pnumpoints < 3)
234                 {
235                         //Con_DPrintf("Collision_NewBrushFromPlanes: warning: polygon for plane %f %f %f %f clipped away\n", originalplanes[j].normal[0], originalplanes[j].normal[1], originalplanes[j].normal[2], originalplanes[j].dist);
236                         continue;
237                 }
238
239                 for (k = 0;k < pnumpoints;k++)
240                 {
241                         int l, m;
242                         m = 0;
243                         for (l = 0;l < numoriginalplanes;l++)
244                                 if (fabs(DotProduct(&p[w][k*3], originalplanes[l].normal) - originalplanes[l].dist) < COLLISION_PLANE_DIST_EPSILON)
245                                         m++;
246                         if (m < 3)
247                                 break;
248                 }
249                 if (k < pnumpoints)
250                 {
251                         Con_DPrintf("Collision_NewBrushFromPlanes: warning: polygon point does not lie on at least 3 planes\n");
252                         //return NULL;
253                 }
254
255                 // check if there are too many polygon vertices for buffer
256                 if (pnumpoints > pmaxpoints)
257                 {
258                         Con_DPrint("Collision_NewBrushFromPlanes: failed to build collision brush: too many points for buffer\n");
259                         return NULL;
260                 }
261
262                 // check if there are too many triangle elements for buffer
263                 if (numelementsbuf + (pnumpoints - 2) * 3 > maxelementsbuf)
264                 {
265                         Con_DPrint("Collision_NewBrushFromPlanes: failed to build collision brush: too many triangle elements for buffer\n");
266                         return NULL;
267                 }
268
269                 // add the unique points for this polygon
270                 for (k = 0;k < pnumpoints;k++)
271                 {
272                         int m;
273                         float v[3];
274                         // downgrade to float precision before comparing
275                         VectorCopy(&p[w][k*3], v);
276
277                         // check if there is already a matching point (no duplicates)
278                         for (m = 0;m < numpointsbuf;m++)
279                                 if (VectorDistance2(v, pointsbuf[m].v) < COLLISION_SNAP2)
280                                         break;
281
282                         // if there is no match, add a new one
283                         if (m == numpointsbuf)
284                         {
285                                 // check if there are too many and skip the brush
286                                 if (numpointsbuf >= maxpointsbuf)
287                                 {
288                                         Con_DPrint("Collision_NewBrushFromPlanes: failed to build collision brush: too many points for buffer\n");
289                                         return NULL;
290                                 }
291                                 // add the new one
292                                 VectorCopy(&p[w][k*3], pointsbuf[numpointsbuf].v);
293                                 numpointsbuf++;
294                         }
295
296                         // store the index into a buffer
297                         polypointbuf[k] = m;
298                 }
299
300                 // add the triangles for the polygon
301                 // (this particular code makes a triangle fan)
302                 for (k = 0;k < pnumpoints - 2;k++)
303                 {
304                         elementsbuf[numelementsbuf++] = polypointbuf[0];
305                         elementsbuf[numelementsbuf++] = polypointbuf[k + 1];
306                         elementsbuf[numelementsbuf++] = polypointbuf[k + 2];
307                 }
308
309                 // add the unique edgedirs for this polygon
310                 for (k = 0, n = pnumpoints-1;k < pnumpoints;n = k, k++)
311                 {
312                         int m;
313                         float dir[3];
314                         // downgrade to float precision before comparing
315                         VectorSubtract(&p[w][k*3], &p[w][n*3], dir);
316                         VectorNormalize(dir);
317
318                         // check if there is already a matching edgedir (no duplicates)
319                         for (m = 0;m < numedgedirsbuf;m++)
320                                 if (DotProduct(dir, edgedirsbuf[m].v) >= COLLISION_EDGEDIR_DOT_EPSILON)
321                                         break;
322                         // skip this if there is
323                         if (m < numedgedirsbuf)
324                                 continue;
325
326                         // try again with negated edgedir
327                         VectorNegate(dir, dir);
328                         // check if there is already a matching edgedir (no duplicates)
329                         for (m = 0;m < numedgedirsbuf;m++)
330                                 if (DotProduct(dir, edgedirsbuf[m].v) >= COLLISION_EDGEDIR_DOT_EPSILON)
331                                         break;
332                         // if there is no match, add a new one
333                         if (m == numedgedirsbuf)
334                         {
335                                 // check if there are too many and skip the brush
336                                 if (numedgedirsbuf >= maxedgedirsbuf)
337                                 {
338                                         Con_DPrint("Collision_NewBrushFromPlanes: failed to build collision brush: too many edgedirs for buffer\n");
339                                         return NULL;
340                                 }
341                                 // add the new one
342                                 VectorCopy(dir, edgedirsbuf[numedgedirsbuf].v);
343                                 numedgedirsbuf++;
344                         }
345                 }
346
347                 // if any normal is not purely axial, it's not an axis-aligned box
348                 if (isaabb && (originalplanes[j].normal[0] == 0) + (originalplanes[j].normal[1] == 0) + (originalplanes[j].normal[2] == 0) < 2)
349                         isaabb = false;
350         }
351
352         // if nothing is left, there's nothing to allocate
353         if (numplanesbuf < 4)
354         {
355                 Con_DPrintf("Collision_NewBrushFromPlanes: failed to build collision brush: %i triangles, %i planes (input was %i planes), %i vertices\n", numelementsbuf / 3, numplanesbuf, numoriginalplanes, numpointsbuf);
356                 return NULL;
357         }
358
359         // if no triangles or points could be constructed, then this routine failed but the brush is not discarded
360         if (numelementsbuf < 12 || numpointsbuf < 4)
361                 Con_DPrintf("Collision_NewBrushFromPlanes: unable to rebuild triangles/points for collision brush: %i triangles, %i planes (input was %i planes), %i vertices\n", numelementsbuf / 3, numplanesbuf, numoriginalplanes, numpointsbuf);
362
363         // validate plane distances
364         for (j = 0;j < numplanesbuf;j++)
365         {
366                 float d = furthestplanedist_float(planesbuf[j].normal, pointsbuf, numpointsbuf);
367                 if (fabs(planesbuf[j].dist - d) > COLLISION_PLANE_DIST_EPSILON)
368                         Con_DPrintf("plane %f %f %f %f mismatches dist %f\n", planesbuf[j].normal[0], planesbuf[j].normal[1], planesbuf[j].normal[2], planesbuf[j].dist, d);
369         }
370
371         // allocate the brush and copy to it
372         brush = (colbrushf_t *)Mem_Alloc(mempool, sizeof(colbrushf_t) + sizeof(colpointf_t) * numpointsbuf + sizeof(colpointf_t) * numedgedirsbuf + sizeof(colplanef_t) * numplanesbuf + sizeof(int) * numelementsbuf);
373         brush->isaabb = isaabb;
374         brush->hasaabbplanes = hasaabbplanes;
375         brush->supercontents = supercontents;
376         brush->numplanes = numplanesbuf;
377         brush->numedgedirs = numedgedirsbuf;
378         brush->numpoints = numpointsbuf;
379         brush->numtriangles = numelementsbuf / 3;
380         brush->planes = (colplanef_t *)(brush + 1);
381         brush->points = (colpointf_t *)(brush->planes + brush->numplanes);
382         brush->edgedirs = (colpointf_t *)(brush->points + brush->numpoints);
383         brush->elements = (int *)(brush->points + brush->numpoints);
384         brush->q3surfaceflags = q3surfaceflags;
385         brush->texture = texture;
386         for (j = 0;j < brush->numpoints;j++)
387         {
388                 brush->points[j].v[0] = pointsbuf[j].v[0];
389                 brush->points[j].v[1] = pointsbuf[j].v[1];
390                 brush->points[j].v[2] = pointsbuf[j].v[2];
391         }
392         for (j = 0;j < brush->numedgedirs;j++)
393         {
394                 brush->edgedirs[j].v[0] = edgedirsbuf[j].v[0];
395                 brush->edgedirs[j].v[1] = edgedirsbuf[j].v[1];
396                 brush->edgedirs[j].v[2] = edgedirsbuf[j].v[2];
397         }
398         for (j = 0;j < brush->numplanes;j++)
399         {
400                 brush->planes[j].normal[0] = planesbuf[j].normal[0];
401                 brush->planes[j].normal[1] = planesbuf[j].normal[1];
402                 brush->planes[j].normal[2] = planesbuf[j].normal[2];
403                 brush->planes[j].dist = planesbuf[j].dist;
404                 brush->planes[j].q3surfaceflags = planesbuf[j].q3surfaceflags;
405                 brush->planes[j].texture = planesbuf[j].texture;
406         }
407         for (j = 0;j < brush->numtriangles * 3;j++)
408                 brush->elements[j] = elementsbuf[j];
409
410         xyzflags = 0;
411         VectorClear(brush->mins);
412         VectorClear(brush->maxs);
413         for (j = 0;j < min(6, numoriginalplanes);j++)
414         {
415                      if (originalplanes[j].normal[0] ==  1) {xyzflags |=  1;brush->maxs[0] =  originalplanes[j].dist;}
416                 else if (originalplanes[j].normal[0] == -1) {xyzflags |=  2;brush->mins[0] = -originalplanes[j].dist;}
417                 else if (originalplanes[j].normal[1] ==  1) {xyzflags |=  4;brush->maxs[1] =  originalplanes[j].dist;}
418                 else if (originalplanes[j].normal[1] == -1) {xyzflags |=  8;brush->mins[1] = -originalplanes[j].dist;}
419                 else if (originalplanes[j].normal[2] ==  1) {xyzflags |= 16;brush->maxs[2] =  originalplanes[j].dist;}
420                 else if (originalplanes[j].normal[2] == -1) {xyzflags |= 32;brush->mins[2] = -originalplanes[j].dist;}
421         }
422         // if not all xyzflags were set, then this is not a brush from q3map/q3map2, and needs reconstruction of the bounding box
423         // (this case works for any brush with valid points, but sometimes brushes are not reconstructed properly and hence the points are not valid, so this is reserved as a fallback case)
424         if (xyzflags != 63)
425         {
426                 VectorCopy(brush->points[0].v, brush->mins);
427                 VectorCopy(brush->points[0].v, brush->maxs);
428                 for (j = 1;j < brush->numpoints;j++)
429                 {
430                         brush->mins[0] = min(brush->mins[0], brush->points[j].v[0]);
431                         brush->mins[1] = min(brush->mins[1], brush->points[j].v[1]);
432                         brush->mins[2] = min(brush->mins[2], brush->points[j].v[2]);
433                         brush->maxs[0] = max(brush->maxs[0], brush->points[j].v[0]);
434                         brush->maxs[1] = max(brush->maxs[1], brush->points[j].v[1]);
435                         brush->maxs[2] = max(brush->maxs[2], brush->points[j].v[2]);
436                 }
437         }
438         brush->mins[0] -= 1;
439         brush->mins[1] -= 1;
440         brush->mins[2] -= 1;
441         brush->maxs[0] += 1;
442         brush->maxs[1] += 1;
443         brush->maxs[2] += 1;
444         Collision_ValidateBrush(brush);
445         return brush;
446 }
447
448
449
450 void Collision_CalcPlanesForTriangleBrushFloat(colbrushf_t *brush)
451 {
452         float edge0[3], edge1[3], edge2[3];
453         colpointf_t *p;
454
455         TriangleNormal(brush->points[0].v, brush->points[1].v, brush->points[2].v, brush->planes[0].normal);
456         if (DotProduct(brush->planes[0].normal, brush->planes[0].normal) < 0.0001f)
457         {
458                 // there's no point in processing a degenerate triangle (GIGO - Garbage In, Garbage Out)
459                 // note that some of these exist in q3bsp bspline patches
460                 brush->numplanes = 0;
461                 return;
462         }
463
464         // there are 5 planes (front, back, sides) and 3 edges
465         brush->numplanes = 5;
466         brush->numedgedirs = 3;
467         VectorNormalize(brush->planes[0].normal);
468         brush->planes[0].dist = DotProduct(brush->points->v, brush->planes[0].normal);
469         VectorNegate(brush->planes[0].normal, brush->planes[1].normal);
470         brush->planes[1].dist = -brush->planes[0].dist;
471         // edge directions are easy to calculate
472         VectorSubtract(brush->points[2].v, brush->points[0].v, edge0);
473         VectorSubtract(brush->points[0].v, brush->points[1].v, edge1);
474         VectorSubtract(brush->points[1].v, brush->points[2].v, edge2);
475         VectorCopy(edge0, brush->edgedirs[0].v);
476         VectorCopy(edge1, brush->edgedirs[1].v);
477         VectorCopy(edge2, brush->edgedirs[2].v);
478         // now select an algorithm to generate the side planes
479         if (collision_triangle_bevelsides.integer)
480         {
481                 // use 45 degree slopes at the edges of the triangle to make a sinking trace error turn into "riding up" the slope rather than getting stuck
482                 CrossProduct(edge0, brush->planes->normal, brush->planes[2].normal);
483                 CrossProduct(edge1, brush->planes->normal, brush->planes[3].normal);
484                 CrossProduct(edge2, brush->planes->normal, brush->planes[4].normal);
485                 VectorNormalize(brush->planes[2].normal);
486                 VectorNormalize(brush->planes[3].normal);
487                 VectorNormalize(brush->planes[4].normal);
488                 VectorAdd(brush->planes[2].normal, brush->planes[0].normal, brush->planes[2].normal);
489                 VectorAdd(brush->planes[3].normal, brush->planes[0].normal, brush->planes[3].normal);
490                 VectorAdd(brush->planes[4].normal, brush->planes[0].normal, brush->planes[4].normal);
491                 VectorNormalize(brush->planes[2].normal);
492                 VectorNormalize(brush->planes[3].normal);
493                 VectorNormalize(brush->planes[4].normal);
494         }
495         else if (collision_triangle_axialsides.integer)
496         {
497                 float projectionnormal[3], projectionedge0[3], projectionedge1[3], projectionedge2[3];
498                 int i, best;
499                 float dist, bestdist;
500                 bestdist = fabs(brush->planes[0].normal[0]);
501                 best = 0;
502                 for (i = 1;i < 3;i++)
503                 {
504                         dist = fabs(brush->planes[0].normal[i]);
505                         if (bestdist < dist)
506                         {
507                                 bestdist = dist;
508                                 best = i;
509                         }
510                 }
511                 VectorClear(projectionnormal);
512                 if (brush->planes[0].normal[best] < 0)
513                         projectionnormal[best] = -1;
514                 else
515                         projectionnormal[best] = 1;
516                 VectorCopy(edge0, projectionedge0);
517                 VectorCopy(edge1, projectionedge1);
518                 VectorCopy(edge2, projectionedge2);
519                 projectionedge0[best] = 0;
520                 projectionedge1[best] = 0;
521                 projectionedge2[best] = 0;
522                 CrossProduct(projectionedge0, projectionnormal, brush->planes[2].normal);
523                 CrossProduct(projectionedge1, projectionnormal, brush->planes[3].normal);
524                 CrossProduct(projectionedge2, projectionnormal, brush->planes[4].normal);
525                 VectorNormalize(brush->planes[2].normal);
526                 VectorNormalize(brush->planes[3].normal);
527                 VectorNormalize(brush->planes[4].normal);
528         }
529         else
530         {
531                 CrossProduct(edge0, brush->planes->normal, brush->planes[2].normal);
532                 CrossProduct(edge1, brush->planes->normal, brush->planes[3].normal);
533                 CrossProduct(edge2, brush->planes->normal, brush->planes[4].normal);
534                 VectorNormalize(brush->planes[2].normal);
535                 VectorNormalize(brush->planes[3].normal);
536                 VectorNormalize(brush->planes[4].normal);
537         }
538         brush->planes[2].dist = DotProduct(brush->points[2].v, brush->planes[2].normal);
539         brush->planes[3].dist = DotProduct(brush->points[0].v, brush->planes[3].normal);
540         brush->planes[4].dist = DotProduct(brush->points[1].v, brush->planes[4].normal);
541
542         if (developer_extra.integer)
543         {
544                 int i;
545                 // validity check - will be disabled later
546                 Collision_ValidateBrush(brush);
547                 for (i = 0;i < brush->numplanes;i++)
548                 {
549                         int j;
550                         for (j = 0, p = brush->points;j < brush->numpoints;j++, p++)
551                                 if (DotProduct(p->v, brush->planes[i].normal) > brush->planes[i].dist + COLLISION_PLANE_DIST_EPSILON)
552                                         Con_DPrintf("Error in brush plane generation, plane %i\n", i);
553                 }
554         }
555 }
556
557 colbrushf_t *Collision_AllocBrushFromPermanentPolygonFloat(mempool_t *mempool, int numpoints, float *points, int supercontents, int q3surfaceflags, const texture_t *texture)
558 {
559         colbrushf_t *brush;
560         brush = (colbrushf_t *)Mem_Alloc(mempool, sizeof(colbrushf_t) + sizeof(colplanef_t) * (numpoints + 2) + sizeof(colpointf_t) * numpoints);
561         brush->isaabb = false;
562         brush->hasaabbplanes = false;
563         brush->supercontents = supercontents;
564         brush->numpoints = numpoints;
565         brush->numedgedirs = numpoints;
566         brush->numplanes = numpoints + 2;
567         brush->planes = (colplanef_t *)(brush + 1);
568         brush->points = (colpointf_t *)points;
569         brush->edgedirs = (colpointf_t *)(brush->planes + brush->numplanes);
570         brush->q3surfaceflags = q3surfaceflags;
571         brush->texture = texture;
572         Sys_Error("Collision_AllocBrushFromPermanentPolygonFloat: FIXME: this code needs to be updated to generate a mesh...");
573         return brush;
574 }
575
576 // NOTE: start and end of each brush pair must have same numplanes/numpoints
577 void Collision_TraceBrushBrushFloat(trace_t *trace, const colbrushf_t *trace_start, const colbrushf_t *trace_end, const colbrushf_t *other_start, const colbrushf_t *other_end)
578 {
579         int nplane, nplane2, nedge1, nedge2, hitq3surfaceflags = 0;
580         int tracenumedgedirs = trace_start->numedgedirs;
581         //int othernumedgedirs = other_start->numedgedirs;
582         int tracenumpoints = trace_start->numpoints;
583         int othernumpoints = other_start->numpoints;
584         int numplanes1 = other_start->numplanes;
585         int numplanes2 = numplanes1 + trace_start->numplanes;
586         int numplanes3 = numplanes2 + trace_start->numedgedirs * other_start->numedgedirs * 2;
587         vec_t enterfrac = -1, leavefrac = 1, startdist, enddist, ie, f, imove, enterfrac2 = -1;
588         vec4_t startplane;
589         vec4_t endplane;
590         vec4_t newimpactplane;
591         const texture_t *hittexture = NULL;
592         vec_t startdepth = 1;
593         vec3_t startdepthnormal;
594
595         VectorClear(startdepthnormal);
596         Vector4Clear(newimpactplane);
597
598         // fast case for AABB vs compiled brushes (which begin with AABB planes and also have precomputed bevels for AABB collisions)
599         if (trace_start->isaabb && other_start->hasaabbplanes)
600                 numplanes3 = numplanes2 = numplanes1;
601
602         // Separating Axis Theorem:
603         // if a supporting vector (plane normal) can be found that separates two
604         // objects, they are not colliding.
605         //
606         // Minkowski Sum:
607         // reduce the size of one object to a point while enlarging the other to
608         // represent the space that point can not occupy.
609         //
610         // try every plane we can construct between the two brushes and measure
611         // the distance between them.
612         for (nplane = 0;nplane < numplanes3;nplane++)
613         {
614                 if (nplane < numplanes1)
615                 {
616                         nplane2 = nplane;
617                         VectorCopy(other_start->planes[nplane2].normal, startplane);
618                         VectorCopy(other_end->planes[nplane2].normal, endplane);
619                 }
620                 else if (nplane < numplanes2)
621                 {
622                         nplane2 = nplane - numplanes1;
623                         VectorCopy(trace_start->planes[nplane2].normal, startplane);
624                         VectorCopy(trace_end->planes[nplane2].normal, endplane);
625                 }
626                 else
627                 {
628                         // pick an edgedir from each brush and cross them
629                         nplane2 = nplane - numplanes2;
630                         nedge1 = nplane2 >> 1;
631                         nedge2 = nedge1 / tracenumedgedirs;
632                         nedge1 -= nedge2 * tracenumedgedirs;
633                         if (nplane2 & 1)
634                         {
635                                 CrossProduct(trace_start->edgedirs[nedge1].v, other_start->edgedirs[nedge2].v, startplane);
636                                 CrossProduct(trace_end->edgedirs[nedge1].v, other_end->edgedirs[nedge2].v, endplane);
637                         }
638                         else
639                         {
640                                 CrossProduct(other_start->edgedirs[nedge2].v, trace_start->edgedirs[nedge1].v, startplane);
641                                 CrossProduct(other_end->edgedirs[nedge2].v, trace_end->edgedirs[nedge1].v, endplane);
642                         }
643                         if (VectorLength2(startplane) < COLLISION_EDGECROSS_MINLENGTH2 || VectorLength2(endplane) < COLLISION_EDGECROSS_MINLENGTH2)
644                                 continue; // degenerate crossproducts
645                         VectorNormalize(startplane);
646                         VectorNormalize(endplane);
647                 }
648                 startplane[3] = furthestplanedist_float(startplane, other_start->points, othernumpoints);
649                 endplane[3] = furthestplanedist_float(startplane, other_end->points, othernumpoints);
650                 startdist = nearestplanedist_float(startplane, trace_start->points, tracenumpoints) - startplane[3];
651                 enddist = nearestplanedist_float(endplane, trace_end->points, tracenumpoints) - endplane[3];
652                 //Con_Printf("%c%i: startdist = %f, enddist = %f, startdist / (startdist - enddist) = %f\n", nplane2 != nplane ? 'b' : 'a', nplane2, startdist, enddist, startdist / (startdist - enddist));
653
654                 // aside from collisions, this is also used for error correction
655                 if (startdist <= 0.0f && nplane < numplanes1 && (startdepth < startdist || startdepth == 1))
656                 {
657                         startdepth = startdist;
658                         VectorCopy(startplane, startdepthnormal);
659                 }
660
661                 if (startdist > enddist)
662                 {
663                         // moving into brush
664                         if (enddist > 0.0f)
665                                 return;
666                         if (startdist >= 0)
667                         {
668                                 // enter
669                                 imove = 1 / (startdist - enddist);
670                                 f = startdist * imove;
671                                 // check if this will reduce the collision time range
672                                 if (enterfrac < f)
673                                 {
674                                         // reduced collision time range
675                                         enterfrac = f;
676                                         // if the collision time range is now empty, no collision
677                                         if (enterfrac > leavefrac)
678                                                 return;
679                                         // calculate the nudged fraction and impact normal we'll
680                                         // need if we accept this collision later
681                                         enterfrac2 = (startdist - collision_impactnudge.value) * imove;
682                                         // if the collision would be further away than the trace's
683                                         // existing collision data, we don't care about this
684                                         // collision
685                                         if (enterfrac2 >= trace->fraction)
686                                                 return;
687                                         ie = 1.0f - enterfrac;
688                                         newimpactplane[0] = startplane[0] * ie + endplane[0] * enterfrac;
689                                         newimpactplane[1] = startplane[1] * ie + endplane[1] * enterfrac;
690                                         newimpactplane[2] = startplane[2] * ie + endplane[2] * enterfrac;
691                                         newimpactplane[3] = startplane[3] * ie + endplane[3] * enterfrac;
692                                         if (nplane < numplanes1)
693                                         {
694                                                 // use the plane from other
695                                                 nplane2 = nplane;
696                                                 hitq3surfaceflags = other_start->planes[nplane2].q3surfaceflags;
697                                                 hittexture = other_start->planes[nplane2].texture;
698                                         }
699                                         else if (nplane < numplanes2)
700                                         {
701                                                 // use the plane from trace
702                                                 nplane2 = nplane - numplanes1;
703                                                 hitq3surfaceflags = trace_start->planes[nplane2].q3surfaceflags;
704                                                 hittexture = trace_start->planes[nplane2].texture;
705                                         }
706                                         else
707                                         {
708                                                 hitq3surfaceflags = other_start->q3surfaceflags;
709                                                 hittexture = other_start->texture;
710                                         }
711                                 }
712                         }
713                 }
714                 else
715                 {
716                         // moving out of brush
717                         if (startdist >= 0)
718                                 return;
719                         if (enddist > 0)
720                         {
721                                 // leave
722                                 f = startdist / (startdist - enddist);
723                                 // check if this will reduce the collision time range
724                                 if (leavefrac > f)
725                                 {
726                                         // reduced collision time range
727                                         leavefrac = f;
728                                         // if the collision time range is now empty, no collision
729                                         if (enterfrac > leavefrac)
730                                                 return;
731                                 }
732                         }
733                 }
734         }
735
736         // at this point we know the trace overlaps the brush because it was not
737         // rejected at any point in the loop above
738
739         // see if the trace started outside the brush or not
740         if (enterfrac > -1)
741         {
742                 // started outside, and overlaps, therefore there is a collision here
743                 // store out the impact information
744                 if ((trace->hitsupercontentsmask & other_start->supercontents) && !(trace->skipsupercontentsmask & other_start->supercontents))
745                 {
746                         trace->hitsupercontents = other_start->supercontents;
747                         trace->hitq3surfaceflags = hitq3surfaceflags;
748                         trace->hittexture = hittexture;
749                         trace->fraction = bound(0, enterfrac2, 1);
750                         VectorCopy(newimpactplane, trace->plane.normal);
751                         trace->plane.dist = newimpactplane[3];
752                 }
753         }
754         else
755         {
756                 // started inside, update startsolid and friends
757                 trace->startsupercontents |= other_start->supercontents;
758                 if ((trace->hitsupercontentsmask & other_start->supercontents) && !(trace->skipsupercontentsmask & other_start->supercontents))
759                 {
760                         trace->startsolid = true;
761                         if (leavefrac < 1)
762                                 trace->allsolid = true;
763                         VectorCopy(newimpactplane, trace->plane.normal);
764                         trace->plane.dist = newimpactplane[3];
765                         if (trace->startdepth > startdepth)
766                         {
767                                 trace->startdepth = startdepth;
768                                 VectorCopy(startdepthnormal, trace->startdepthnormal);
769                         }
770                 }
771         }
772 }
773
774 // NOTE: start and end of each brush pair must have same numplanes/numpoints
775 void Collision_TraceLineBrushFloat(trace_t *trace, const vec3_t linestart, const vec3_t lineend, const colbrushf_t *other_start, const colbrushf_t *other_end)
776 {
777         int nplane, hitq3surfaceflags = 0;
778         int numplanes = other_start->numplanes;
779         vec_t enterfrac = -1, leavefrac = 1, startdist, enddist, ie, f, imove, enterfrac2 = -1;
780         vec4_t startplane;
781         vec4_t endplane;
782         vec4_t newimpactplane;
783         const texture_t *hittexture = NULL;
784         vec_t startdepth = 1;
785         vec3_t startdepthnormal;
786
787         if (collision_debug_tracelineasbox.integer)
788         {
789                 colboxbrushf_t thisbrush_start, thisbrush_end;
790                 Collision_BrushForBox(&thisbrush_start, linestart, linestart, 0, 0, NULL);
791                 Collision_BrushForBox(&thisbrush_end, lineend, lineend, 0, 0, NULL);
792                 Collision_TraceBrushBrushFloat(trace, &thisbrush_start.brush, &thisbrush_end.brush, other_start, other_end);
793                 return;
794         }
795
796         VectorClear(startdepthnormal);
797         Vector4Clear(newimpactplane);
798
799         // Separating Axis Theorem:
800         // if a supporting vector (plane normal) can be found that separates two
801         // objects, they are not colliding.
802         //
803         // Minkowski Sum:
804         // reduce the size of one object to a point while enlarging the other to
805         // represent the space that point can not occupy.
806         //
807         // try every plane we can construct between the two brushes and measure
808         // the distance between them.
809         for (nplane = 0;nplane < numplanes;nplane++)
810         {
811                 VectorCopy(other_start->planes[nplane].normal, startplane);
812                 startplane[3] = other_start->planes[nplane].dist;
813                 VectorCopy(other_end->planes[nplane].normal, endplane);
814                 endplane[3] = other_end->planes[nplane].dist;
815                 startdist = DotProduct(linestart, startplane) - startplane[3];
816                 enddist = DotProduct(lineend, endplane) - endplane[3];
817                 //Con_Printf("%c%i: startdist = %f, enddist = %f, startdist / (startdist - enddist) = %f\n", nplane2 != nplane ? 'b' : 'a', nplane2, startdist, enddist, startdist / (startdist - enddist));
818
819                 // aside from collisions, this is also used for error correction
820                 if (startdist <= 0.0f && (startdepth < startdist || startdepth == 1))
821                 {
822                         startdepth = startdist;
823                         VectorCopy(startplane, startdepthnormal);
824                 }
825
826                 if (startdist > enddist)
827                 {
828                         // moving into brush
829                         if (enddist > 0.0f)
830                                 return;
831                         if (startdist > 0)
832                         {
833                                 // enter
834                                 imove = 1 / (startdist - enddist);
835                                 f = startdist * imove;
836                                 // check if this will reduce the collision time range
837                                 if (enterfrac < f)
838                                 {
839                                         // reduced collision time range
840                                         enterfrac = f;
841                                         // if the collision time range is now empty, no collision
842                                         if (enterfrac > leavefrac)
843                                                 return;
844                                         // calculate the nudged fraction and impact normal we'll
845                                         // need if we accept this collision later
846                                         enterfrac2 = (startdist - collision_impactnudge.value) * imove;
847                                         // if the collision would be further away than the trace's
848                                         // existing collision data, we don't care about this
849                                         // collision
850                                         if (enterfrac2 >= trace->fraction)
851                                                 return;
852                                         ie = 1.0f - enterfrac;
853                                         newimpactplane[0] = startplane[0] * ie + endplane[0] * enterfrac;
854                                         newimpactplane[1] = startplane[1] * ie + endplane[1] * enterfrac;
855                                         newimpactplane[2] = startplane[2] * ie + endplane[2] * enterfrac;
856                                         newimpactplane[3] = startplane[3] * ie + endplane[3] * enterfrac;
857                                         hitq3surfaceflags = other_start->planes[nplane].q3surfaceflags;
858                                         hittexture = other_start->planes[nplane].texture;
859                                 }
860                         }
861                 }
862                 else
863                 {
864                         // moving out of brush
865                         if (startdist > 0)
866                                 return;
867                         if (enddist > 0)
868                         {
869                                 // leave
870                                 f = startdist / (startdist - enddist);
871                                 // check if this will reduce the collision time range
872                                 if (leavefrac > f)
873                                 {
874                                         // reduced collision time range
875                                         leavefrac = f;
876                                         // if the collision time range is now empty, no collision
877                                         if (enterfrac > leavefrac)
878                                                 return;
879                                 }
880                         }
881                 }
882         }
883
884         // at this point we know the trace overlaps the brush because it was not
885         // rejected at any point in the loop above
886
887         // see if the trace started outside the brush or not
888         if (enterfrac > -1)
889         {
890                 // started outside, and overlaps, therefore there is a collision here
891                 // store out the impact information
892                 if ((trace->hitsupercontentsmask & other_start->supercontents) && !(trace->skipsupercontentsmask & other_start->supercontents))
893                 {
894                         trace->hitsupercontents = other_start->supercontents;
895                         trace->hitq3surfaceflags = hitq3surfaceflags;
896                         trace->hittexture = hittexture;
897                         trace->fraction = bound(0, enterfrac2, 1);
898                         VectorCopy(newimpactplane, trace->plane.normal);
899                         trace->plane.dist = newimpactplane[3];
900                 }
901         }
902         else
903         {
904                 // started inside, update startsolid and friends
905                 trace->startsupercontents |= other_start->supercontents;
906                 if ((trace->hitsupercontentsmask & other_start->supercontents) && !(trace->skipsupercontentsmask & other_start->supercontents))
907                 {
908                         trace->startsolid = true;
909                         if (leavefrac < 1)
910                                 trace->allsolid = true;
911                         VectorCopy(newimpactplane, trace->plane.normal);
912                         trace->plane.dist = newimpactplane[3];
913                         if (trace->startdepth > startdepth)
914                         {
915                                 trace->startdepth = startdepth;
916                                 VectorCopy(startdepthnormal, trace->startdepthnormal);
917                         }
918                 }
919         }
920 }
921
922 qboolean Collision_PointInsideBrushFloat(const vec3_t point, const colbrushf_t *brush)
923 {
924         int nplane;
925         const colplanef_t *plane;
926
927         if (!BoxesOverlap(point, point, brush->mins, brush->maxs))
928                 return false;
929         for (nplane = 0, plane = brush->planes;nplane < brush->numplanes;nplane++, plane++)
930                 if (DotProduct(plane->normal, point) > plane->dist)
931                         return false;
932         return true;
933 }
934
935 void Collision_TracePointBrushFloat(trace_t *trace, const vec3_t point, const colbrushf_t *thatbrush)
936 {
937         if (!Collision_PointInsideBrushFloat(point, thatbrush))
938                 return;
939
940         trace->startsupercontents |= thatbrush->supercontents;
941         if ((trace->hitsupercontentsmask & thatbrush->supercontents) && !(trace->skipsupercontentsmask & thatbrush->supercontents))
942         {
943                 trace->startsolid = true;
944                 trace->allsolid = true;
945         }
946 }
947
948 static void Collision_SnapCopyPoints(int numpoints, const colpointf_t *in, colpointf_t *out, float fractionprecision, float invfractionprecision)
949 {
950         int i;
951         for (i = 0;i < numpoints;i++)
952         {
953                 out[i].v[0] = floor(in[i].v[0] * fractionprecision + 0.5f) * invfractionprecision;
954                 out[i].v[1] = floor(in[i].v[1] * fractionprecision + 0.5f) * invfractionprecision;
955                 out[i].v[2] = floor(in[i].v[2] * fractionprecision + 0.5f) * invfractionprecision;
956         }
957 }
958
959 void Collision_TraceBrushTriangleMeshFloat(trace_t *trace, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, int numtriangles, const int *element3i, const float *vertex3f, int stride, float *bbox6f, int supercontents, int q3surfaceflags, const texture_t *texture, const vec3_t segmentmins, const vec3_t segmentmaxs)
960 {
961         int i;
962         colpointf_t points[3];
963         colpointf_t edgedirs[3];
964         colplanef_t planes[5];
965         colbrushf_t brush;
966         memset(&brush, 0, sizeof(brush));
967         brush.isaabb = false;
968         brush.hasaabbplanes = false;
969         brush.numpoints = 3;
970         brush.numedgedirs = 3;
971         brush.numplanes = 5;
972         brush.points = points;
973         brush.edgedirs = edgedirs;
974         brush.planes = planes;
975         brush.supercontents = supercontents;
976         brush.q3surfaceflags = q3surfaceflags;
977         brush.texture = texture;
978         for (i = 0;i < brush.numplanes;i++)
979         {
980                 brush.planes[i].q3surfaceflags = q3surfaceflags;
981                 brush.planes[i].texture = texture;
982         }
983         if(stride > 0)
984         {
985                 int k, cnt, tri;
986                 cnt = (numtriangles + stride - 1) / stride;
987                 for(i = 0; i < cnt; ++i)
988                 {
989                         if(BoxesOverlap(bbox6f + i * 6, bbox6f + i * 6 + 3, segmentmins, segmentmaxs))
990                         {
991                                 for(k = 0; k < stride; ++k)
992                                 {
993                                         tri = i * stride + k;
994                                         if(tri >= numtriangles)
995                                                 break;
996                                         VectorCopy(vertex3f + element3i[tri * 3 + 0] * 3, points[0].v);
997                                         VectorCopy(vertex3f + element3i[tri * 3 + 1] * 3, points[1].v);
998                                         VectorCopy(vertex3f + element3i[tri * 3 + 2] * 3, points[2].v);
999                                         Collision_SnapCopyPoints(brush.numpoints, points, points, COLLISION_SNAPSCALE, COLLISION_SNAP);
1000                                         Collision_CalcEdgeDirsForPolygonBrushFloat(&brush);
1001                                         Collision_CalcPlanesForTriangleBrushFloat(&brush);
1002                                         //Collision_PrintBrushAsQHull(&brush, "brush");
1003                                         Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, &brush, &brush);
1004                                 }
1005                         }
1006                 }
1007         }
1008         else if(stride == 0)
1009         {
1010                 for (i = 0;i < numtriangles;i++, element3i += 3)
1011                 {
1012                         if (TriangleBBoxOverlapsBox(vertex3f + element3i[0]*3, vertex3f + element3i[1]*3, vertex3f + element3i[2]*3, segmentmins, segmentmaxs))
1013                         {
1014                                 VectorCopy(vertex3f + element3i[0] * 3, points[0].v);
1015                                 VectorCopy(vertex3f + element3i[1] * 3, points[1].v);
1016                                 VectorCopy(vertex3f + element3i[2] * 3, points[2].v);
1017                                 Collision_SnapCopyPoints(brush.numpoints, points, points, COLLISION_SNAPSCALE, COLLISION_SNAP);
1018                                 Collision_CalcEdgeDirsForPolygonBrushFloat(&brush);
1019                                 Collision_CalcPlanesForTriangleBrushFloat(&brush);
1020                                 //Collision_PrintBrushAsQHull(&brush, "brush");
1021                                 Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, &brush, &brush);
1022                         }
1023                 }
1024         }
1025         else
1026         {
1027                 for (i = 0;i < numtriangles;i++, element3i += 3)
1028                 {
1029                         VectorCopy(vertex3f + element3i[0] * 3, points[0].v);
1030                         VectorCopy(vertex3f + element3i[1] * 3, points[1].v);
1031                         VectorCopy(vertex3f + element3i[2] * 3, points[2].v);
1032                         Collision_SnapCopyPoints(brush.numpoints, points, points, COLLISION_SNAPSCALE, COLLISION_SNAP);
1033                         Collision_CalcEdgeDirsForPolygonBrushFloat(&brush);
1034                         Collision_CalcPlanesForTriangleBrushFloat(&brush);
1035                         //Collision_PrintBrushAsQHull(&brush, "brush");
1036                         Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, &brush, &brush);
1037                 }
1038         }
1039 }
1040
1041 void Collision_TraceLineTriangleMeshFloat(trace_t *trace, const vec3_t linestart, const vec3_t lineend, int numtriangles, const int *element3i, const float *vertex3f, int stride, float *bbox6f, int supercontents, int q3surfaceflags, const texture_t *texture, const vec3_t segmentmins, const vec3_t segmentmaxs)
1042 {
1043         int i;
1044         // FIXME: snap vertices?
1045         if(stride > 0)
1046         {
1047                 int k, cnt, tri;
1048                 cnt = (numtriangles + stride - 1) / stride;
1049                 for(i = 0; i < cnt; ++i)
1050                 {
1051                         if(BoxesOverlap(bbox6f + i * 6, bbox6f + i * 6 + 3, segmentmins, segmentmaxs))
1052                         {
1053                                 for(k = 0; k < stride; ++k)
1054                                 {
1055                                         tri = i * stride + k;
1056                                         if(tri >= numtriangles)
1057                                                 break;
1058                                         Collision_TraceLineTriangleFloat(trace, linestart, lineend, vertex3f + element3i[tri * 3 + 0] * 3, vertex3f + element3i[tri * 3 + 1] * 3, vertex3f + element3i[tri * 3 + 2] * 3, supercontents, q3surfaceflags, texture);
1059                                 }
1060                         }
1061                 }
1062         }
1063         else
1064         {
1065                 for (i = 0;i < numtriangles;i++, element3i += 3)
1066                         Collision_TraceLineTriangleFloat(trace, linestart, lineend, vertex3f + element3i[0] * 3, vertex3f + element3i[1] * 3, vertex3f + element3i[2] * 3, supercontents, q3surfaceflags, texture);
1067         }
1068 }
1069
1070 void Collision_TraceBrushTriangleFloat(trace_t *trace, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, const float *v0, const float *v1, const float *v2, int supercontents, int q3surfaceflags, const texture_t *texture)
1071 {
1072         int i;
1073         colpointf_t points[3];
1074         colpointf_t edgedirs[3];
1075         colplanef_t planes[5];
1076         colbrushf_t brush;
1077         memset(&brush, 0, sizeof(brush));
1078         brush.isaabb = false;
1079         brush.hasaabbplanes = false;
1080         brush.numpoints = 3;
1081         brush.numedgedirs = 3;
1082         brush.numplanes = 5;
1083         brush.points = points;
1084         brush.edgedirs = edgedirs;
1085         brush.planes = planes;
1086         brush.supercontents = supercontents;
1087         brush.q3surfaceflags = q3surfaceflags;
1088         brush.texture = texture;
1089         for (i = 0;i < brush.numplanes;i++)
1090         {
1091                 brush.planes[i].q3surfaceflags = q3surfaceflags;
1092                 brush.planes[i].texture = texture;
1093         }
1094         VectorCopy(v0, points[0].v);
1095         VectorCopy(v1, points[1].v);
1096         VectorCopy(v2, points[2].v);
1097         Collision_SnapCopyPoints(brush.numpoints, points, points, COLLISION_SNAPSCALE, COLLISION_SNAP);
1098         Collision_CalcEdgeDirsForPolygonBrushFloat(&brush);
1099         Collision_CalcPlanesForTriangleBrushFloat(&brush);
1100         //Collision_PrintBrushAsQHull(&brush, "brush");
1101         Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, &brush, &brush);
1102 }
1103
1104 void Collision_BrushForBox(colboxbrushf_t *boxbrush, const vec3_t mins, const vec3_t maxs, int supercontents, int q3surfaceflags, const texture_t *texture)
1105 {
1106         int i;
1107         memset(boxbrush, 0, sizeof(*boxbrush));
1108         boxbrush->brush.isaabb = true;
1109         boxbrush->brush.hasaabbplanes = true;
1110         boxbrush->brush.points = boxbrush->points;
1111         boxbrush->brush.edgedirs = boxbrush->edgedirs;
1112         boxbrush->brush.planes = boxbrush->planes;
1113         boxbrush->brush.supercontents = supercontents;
1114         boxbrush->brush.q3surfaceflags = q3surfaceflags;
1115         boxbrush->brush.texture = texture;
1116         if (VectorCompare(mins, maxs))
1117         {
1118                 // point brush
1119                 boxbrush->brush.numpoints = 1;
1120                 boxbrush->brush.numedgedirs = 0;
1121                 boxbrush->brush.numplanes = 0;
1122                 VectorCopy(mins, boxbrush->brush.points[0].v);
1123         }
1124         else
1125         {
1126                 boxbrush->brush.numpoints = 8;
1127                 boxbrush->brush.numedgedirs = 3;
1128                 boxbrush->brush.numplanes = 6;
1129                 // there are 8 points on a box
1130                 // there are 3 edgedirs on a box (both signs are tested in collision)
1131                 // there are 6 planes on a box
1132                 VectorSet(boxbrush->brush.points[0].v, mins[0], mins[1], mins[2]);
1133                 VectorSet(boxbrush->brush.points[1].v, maxs[0], mins[1], mins[2]);
1134                 VectorSet(boxbrush->brush.points[2].v, mins[0], maxs[1], mins[2]);
1135                 VectorSet(boxbrush->brush.points[3].v, maxs[0], maxs[1], mins[2]);
1136                 VectorSet(boxbrush->brush.points[4].v, mins[0], mins[1], maxs[2]);
1137                 VectorSet(boxbrush->brush.points[5].v, maxs[0], mins[1], maxs[2]);
1138                 VectorSet(boxbrush->brush.points[6].v, mins[0], maxs[1], maxs[2]);
1139                 VectorSet(boxbrush->brush.points[7].v, maxs[0], maxs[1], maxs[2]);
1140                 VectorSet(boxbrush->brush.edgedirs[0].v, 1, 0, 0);
1141                 VectorSet(boxbrush->brush.edgedirs[1].v, 0, 1, 0);
1142                 VectorSet(boxbrush->brush.edgedirs[2].v, 0, 0, 1);
1143                 VectorSet(boxbrush->brush.planes[0].normal, -1,  0,  0);boxbrush->brush.planes[0].dist = -mins[0];
1144                 VectorSet(boxbrush->brush.planes[1].normal,  1,  0,  0);boxbrush->brush.planes[1].dist =  maxs[0];
1145                 VectorSet(boxbrush->brush.planes[2].normal,  0, -1,  0);boxbrush->brush.planes[2].dist = -mins[1];
1146                 VectorSet(boxbrush->brush.planes[3].normal,  0,  1,  0);boxbrush->brush.planes[3].dist =  maxs[1];
1147                 VectorSet(boxbrush->brush.planes[4].normal,  0,  0, -1);boxbrush->brush.planes[4].dist = -mins[2];
1148                 VectorSet(boxbrush->brush.planes[5].normal,  0,  0,  1);boxbrush->brush.planes[5].dist =  maxs[2];
1149                 for (i = 0;i < 6;i++)
1150                 {
1151                         boxbrush->brush.planes[i].q3surfaceflags = q3surfaceflags;
1152                         boxbrush->brush.planes[i].texture = texture;
1153                 }
1154         }
1155         boxbrush->brush.supercontents = supercontents;
1156         boxbrush->brush.q3surfaceflags = q3surfaceflags;
1157         boxbrush->brush.texture = texture;
1158         VectorSet(boxbrush->brush.mins, mins[0] - 1, mins[1] - 1, mins[2] - 1);
1159         VectorSet(boxbrush->brush.maxs, maxs[0] + 1, maxs[1] + 1, maxs[2] + 1);
1160         //Collision_ValidateBrush(&boxbrush->brush);
1161 }
1162
1163 //pseudocode for detecting line/sphere overlap without calculating an impact point
1164 //linesphereorigin = sphereorigin - linestart;linediff = lineend - linestart;linespherefrac = DotProduct(linesphereorigin, linediff) / DotProduct(linediff, linediff);return VectorLength2(linesphereorigin - bound(0, linespherefrac, 1) * linediff) >= sphereradius*sphereradius;
1165
1166 // LordHavoc: currently unused, but tested
1167 // note: this can be used for tracing a moving sphere vs a stationary sphere,
1168 // by simply adding the moving sphere's radius to the sphereradius parameter,
1169 // all the results are correct (impactpoint, impactnormal, and fraction)
1170 float Collision_ClipTrace_Line_Sphere(double *linestart, double *lineend, double *sphereorigin, double sphereradius, double *impactpoint, double *impactnormal)
1171 {
1172         double dir[3], scale, v[3], deviationdist2, impactdist, linelength;
1173         // make sure the impactpoint and impactnormal are valid even if there is
1174         // no collision
1175         VectorCopy(lineend, impactpoint);
1176         VectorClear(impactnormal);
1177         // calculate line direction
1178         VectorSubtract(lineend, linestart, dir);
1179         // normalize direction
1180         linelength = VectorLength(dir);
1181         if (linelength)
1182         {
1183                 scale = 1.0 / linelength;
1184                 VectorScale(dir, scale, dir);
1185         }
1186         // this dotproduct calculates the distance along the line at which the
1187         // sphere origin is (nearest point to the sphere origin on the line)
1188         impactdist = DotProduct(sphereorigin, dir) - DotProduct(linestart, dir);
1189         // calculate point on line at that distance, and subtract the
1190         // sphereorigin from it, so we have a vector to measure for the distance
1191         // of the line from the sphereorigin (deviation, how off-center it is)
1192         VectorMA(linestart, impactdist, dir, v);
1193         VectorSubtract(v, sphereorigin, v);
1194         deviationdist2 = sphereradius * sphereradius - VectorLength2(v);
1195         // if squared offset length is outside the squared sphere radius, miss
1196         if (deviationdist2 < 0)
1197                 return 1; // miss (off to the side)
1198         // nudge back to find the correct impact distance
1199         impactdist -= sqrt(deviationdist2);
1200         if (impactdist >= linelength)
1201                 return 1; // miss (not close enough)
1202         if (impactdist < 0)
1203                 return 1; // miss (linestart is past or inside sphere)
1204         // calculate new impactpoint
1205         VectorMA(linestart, impactdist, dir, impactpoint);
1206         // calculate impactnormal (surface normal at point of impact)
1207         VectorSubtract(impactpoint, sphereorigin, impactnormal);
1208         // normalize impactnormal
1209         VectorNormalize(impactnormal);
1210         // return fraction of movement distance
1211         return impactdist / linelength;
1212 }
1213
1214 void Collision_TraceLineTriangleFloat(trace_t *trace, const vec3_t linestart, const vec3_t lineend, const float *point0, const float *point1, const float *point2, int supercontents, int q3surfaceflags, const texture_t *texture)
1215 {
1216         float d1, d2, d, f, f2, impact[3], edgenormal[3], faceplanenormal[3], faceplanedist, faceplanenormallength2, edge01[3], edge21[3], edge02[3];
1217
1218         // this function executes:
1219         // 32 ops when line starts behind triangle
1220         // 38 ops when line ends infront of triangle
1221         // 43 ops when line fraction is already closer than this triangle
1222         // 72 ops when line is outside edge 01
1223         // 92 ops when line is outside edge 21
1224         // 115 ops when line is outside edge 02
1225         // 123 ops when line impacts triangle and updates trace results
1226
1227         // this code is designed for clockwise triangles, conversion to
1228         // counterclockwise would require swapping some things around...
1229         // it is easier to simply swap the point0 and point2 parameters to this
1230         // function when calling it than it is to rewire the internals.
1231
1232         // calculate the faceplanenormal of the triangle, this represents the front side
1233         // 15 ops
1234         VectorSubtract(point0, point1, edge01);
1235         VectorSubtract(point2, point1, edge21);
1236         CrossProduct(edge01, edge21, faceplanenormal);
1237         // there's no point in processing a degenerate triangle (GIGO - Garbage In, Garbage Out)
1238         // 6 ops
1239         faceplanenormallength2 = DotProduct(faceplanenormal, faceplanenormal);
1240         if (faceplanenormallength2 < 0.0001f)
1241                 return;
1242         // calculate the distance
1243         // 5 ops
1244         faceplanedist = DotProduct(point0, faceplanenormal);
1245
1246         // if start point is on the back side there is no collision
1247         // (we don't care about traces going through the triangle the wrong way)
1248
1249         // calculate the start distance
1250         // 6 ops
1251         d1 = DotProduct(faceplanenormal, linestart);
1252         if (d1 <= faceplanedist)
1253                 return;
1254
1255         // calculate the end distance
1256         // 6 ops
1257         d2 = DotProduct(faceplanenormal, lineend);
1258         // if both are in front, there is no collision
1259         if (d2 >= faceplanedist)
1260                 return;
1261
1262         // from here on we know d1 is >= 0 and d2 is < 0
1263         // this means the line starts infront and ends behind, passing through it
1264
1265         // calculate the recipricol of the distance delta,
1266         // so we can use it multiple times cheaply (instead of division)
1267         // 2 ops
1268         d = 1.0f / (d1 - d2);
1269         // calculate the impact fraction by taking the start distance (> 0)
1270         // and subtracting the face plane distance (this is the distance of the
1271         // triangle along that same normal)
1272         // then multiply by the recipricol distance delta
1273         // 4 ops
1274         f = (d1 - faceplanedist) * d;
1275         f2  = f - collision_impactnudge.value * d;
1276         // skip out if this impact is further away than previous ones
1277         // 1 ops
1278         if (f2 >= trace->fraction)
1279                 return;
1280         // calculate the perfect impact point for classification of insidedness
1281         // 9 ops
1282         impact[0] = linestart[0] + f * (lineend[0] - linestart[0]);
1283         impact[1] = linestart[1] + f * (lineend[1] - linestart[1]);
1284         impact[2] = linestart[2] + f * (lineend[2] - linestart[2]);
1285
1286         // calculate the edge normal and reject if impact is outside triangle
1287         // (an edge normal faces away from the triangle, to get the desired normal
1288         //  a crossproduct with the faceplanenormal is used, and because of the way
1289         // the insidedness comparison is written it does not need to be normalized)
1290
1291         // first use the two edges from the triangle plane math
1292         // the other edge only gets calculated if the point survives that long
1293
1294         // 20 ops
1295         CrossProduct(edge01, faceplanenormal, edgenormal);
1296         if (DotProduct(impact, edgenormal) > DotProduct(point1, edgenormal))
1297                 return;
1298
1299         // 20 ops
1300         CrossProduct(faceplanenormal, edge21, edgenormal);
1301         if (DotProduct(impact, edgenormal) > DotProduct(point2, edgenormal))
1302                 return;
1303
1304         // 23 ops
1305         VectorSubtract(point0, point2, edge02);
1306         CrossProduct(faceplanenormal, edge02, edgenormal);
1307         if (DotProduct(impact, edgenormal) > DotProduct(point0, edgenormal))
1308                 return;
1309
1310         // 8 ops (rare)
1311
1312         // skip if this trace should not be blocked by these contents
1313         if (!(supercontents & trace->hitsupercontentsmask) || (supercontents & trace->skipsupercontentsmask))
1314                 return;
1315
1316         // store the new trace fraction
1317         trace->fraction = f2;
1318
1319         // store the new trace plane (because collisions only happen from
1320         // the front this is always simply the triangle normal, never flipped)
1321         d = 1.0 / sqrt(faceplanenormallength2);
1322         VectorScale(faceplanenormal, d, trace->plane.normal);
1323         trace->plane.dist = faceplanedist * d;
1324
1325         trace->hitsupercontents = supercontents;
1326         trace->hitq3surfaceflags = q3surfaceflags;
1327         trace->hittexture = texture;
1328 }
1329
1330 void Collision_BoundingBoxOfBrushTraceSegment(const colbrushf_t *start, const colbrushf_t *end, vec3_t mins, vec3_t maxs, float startfrac, float endfrac)
1331 {
1332         int i;
1333         colpointf_t *ps, *pe;
1334         float tempstart[3], tempend[3];
1335         VectorLerp(start->points[0].v, startfrac, end->points[0].v, mins);
1336         VectorCopy(mins, maxs);
1337         for (i = 0, ps = start->points, pe = end->points;i < start->numpoints;i++, ps++, pe++)
1338         {
1339                 VectorLerp(ps->v, startfrac, pe->v, tempstart);
1340                 VectorLerp(ps->v, endfrac, pe->v, tempend);
1341                 mins[0] = min(mins[0], min(tempstart[0], tempend[0]));
1342                 mins[1] = min(mins[1], min(tempstart[1], tempend[1]));
1343                 mins[2] = min(mins[2], min(tempstart[2], tempend[2]));
1344                 maxs[0] = min(maxs[0], min(tempstart[0], tempend[0]));
1345                 maxs[1] = min(maxs[1], min(tempstart[1], tempend[1]));
1346                 maxs[2] = min(maxs[2], min(tempstart[2], tempend[2]));
1347         }
1348         mins[0] -= 1;
1349         mins[1] -= 1;
1350         mins[2] -= 1;
1351         maxs[0] += 1;
1352         maxs[1] += 1;
1353         maxs[2] += 1;
1354 }
1355
1356 //===========================================
1357
1358 static void Collision_TranslateBrush(const vec3_t shift, colbrushf_t *brush)
1359 {
1360         int i;
1361         // now we can transform the data
1362         for(i = 0; i < brush->numplanes; ++i)
1363         {
1364                 brush->planes[i].dist += DotProduct(shift, brush->planes[i].normal);
1365         }
1366         for(i = 0; i < brush->numpoints; ++i)
1367         {
1368                 VectorAdd(brush->points[i].v, shift, brush->points[i].v);
1369         }
1370         VectorAdd(brush->mins, shift, brush->mins);
1371         VectorAdd(brush->maxs, shift, brush->maxs);
1372 }
1373
1374 static void Collision_TransformBrush(const matrix4x4_t *matrix, colbrushf_t *brush)
1375 {
1376         int i;
1377         vec3_t v;
1378         // we're breaking any AABB properties here...
1379         brush->isaabb = false;
1380         brush->hasaabbplanes = false;
1381         // now we can transform the data
1382         for(i = 0; i < brush->numplanes; ++i)
1383         {
1384                 Matrix4x4_TransformPositivePlane(matrix, brush->planes[i].normal[0], brush->planes[i].normal[1], brush->planes[i].normal[2], brush->planes[i].dist, brush->planes[i].normal_and_dist);
1385         }
1386         for(i = 0; i < brush->numedgedirs; ++i)
1387         {
1388                 Matrix4x4_Transform(matrix, brush->edgedirs[i].v, v);
1389                 VectorCopy(v, brush->edgedirs[i].v);
1390         }
1391         for(i = 0; i < brush->numpoints; ++i)
1392         {
1393                 Matrix4x4_Transform(matrix, brush->points[i].v, v);
1394                 VectorCopy(v, brush->points[i].v);
1395         }
1396         VectorCopy(brush->points[0].v, brush->mins);
1397         VectorCopy(brush->points[0].v, brush->maxs);
1398         for(i = 1; i < brush->numpoints; ++i)
1399         {
1400                 if(brush->points[i].v[0] < brush->mins[0]) brush->mins[0] = brush->points[i].v[0];
1401                 if(brush->points[i].v[1] < brush->mins[1]) brush->mins[1] = brush->points[i].v[1];
1402                 if(brush->points[i].v[2] < brush->mins[2]) brush->mins[2] = brush->points[i].v[2];
1403                 if(brush->points[i].v[0] > brush->maxs[0]) brush->maxs[0] = brush->points[i].v[0];
1404                 if(brush->points[i].v[1] > brush->maxs[1]) brush->maxs[1] = brush->points[i].v[1];
1405                 if(brush->points[i].v[2] > brush->maxs[2]) brush->maxs[2] = brush->points[i].v[2];
1406         }
1407 }
1408
1409 typedef struct collision_cachedtrace_parameters_s
1410 {
1411         dp_model_t *model;
1412         vec3_t end;
1413         vec3_t start;
1414         int hitsupercontentsmask;
1415         int skipsupercontentsmask;
1416         matrix4x4_t matrix;
1417 }
1418 collision_cachedtrace_parameters_t;
1419
1420 typedef struct collision_cachedtrace_s
1421 {
1422         qboolean valid;
1423         collision_cachedtrace_parameters_t p;
1424         trace_t result;
1425 }
1426 collision_cachedtrace_t;
1427
1428 static mempool_t *collision_cachedtrace_mempool;
1429 static collision_cachedtrace_t *collision_cachedtrace_array;
1430 static int collision_cachedtrace_firstfree;
1431 static int collision_cachedtrace_lastused;
1432 static int collision_cachedtrace_max;
1433 static unsigned char collision_cachedtrace_sequence;
1434 static int collision_cachedtrace_hashsize;
1435 static int *collision_cachedtrace_hash;
1436 static unsigned int *collision_cachedtrace_arrayfullhashindex;
1437 static unsigned int *collision_cachedtrace_arrayhashindex;
1438 static unsigned int *collision_cachedtrace_arraynext;
1439 static unsigned char *collision_cachedtrace_arrayused;
1440 static qboolean collision_cachedtrace_rebuildhash;
1441
1442 void Collision_Cache_Reset(qboolean resetlimits)
1443 {
1444         if (collision_cachedtrace_hash)
1445                 Mem_Free(collision_cachedtrace_hash);
1446         if (collision_cachedtrace_array)
1447                 Mem_Free(collision_cachedtrace_array);
1448         if (collision_cachedtrace_arrayfullhashindex)
1449                 Mem_Free(collision_cachedtrace_arrayfullhashindex);
1450         if (collision_cachedtrace_arrayhashindex)
1451                 Mem_Free(collision_cachedtrace_arrayhashindex);
1452         if (collision_cachedtrace_arraynext)
1453                 Mem_Free(collision_cachedtrace_arraynext);
1454         if (collision_cachedtrace_arrayused)
1455                 Mem_Free(collision_cachedtrace_arrayused);
1456         if (resetlimits || !collision_cachedtrace_max)
1457                 collision_cachedtrace_max = collision_cache.integer ? 128 : 1;
1458         collision_cachedtrace_firstfree = 1;
1459         collision_cachedtrace_lastused = 0;
1460         collision_cachedtrace_hashsize = collision_cachedtrace_max;
1461         collision_cachedtrace_array = (collision_cachedtrace_t *)Mem_Alloc(collision_cachedtrace_mempool, collision_cachedtrace_max * sizeof(collision_cachedtrace_t));
1462         collision_cachedtrace_hash = (int *)Mem_Alloc(collision_cachedtrace_mempool, collision_cachedtrace_hashsize * sizeof(int));
1463         collision_cachedtrace_arrayfullhashindex = (unsigned int *)Mem_Alloc(collision_cachedtrace_mempool, collision_cachedtrace_max * sizeof(unsigned int));
1464         collision_cachedtrace_arrayhashindex = (unsigned int *)Mem_Alloc(collision_cachedtrace_mempool, collision_cachedtrace_max * sizeof(unsigned int));
1465         collision_cachedtrace_arraynext = (unsigned int *)Mem_Alloc(collision_cachedtrace_mempool, collision_cachedtrace_max * sizeof(unsigned int));
1466         collision_cachedtrace_arrayused = (unsigned char *)Mem_Alloc(collision_cachedtrace_mempool, collision_cachedtrace_max * sizeof(unsigned char));
1467         collision_cachedtrace_sequence = 1;
1468         collision_cachedtrace_rebuildhash = false;
1469 }
1470
1471 void Collision_Cache_Init(mempool_t *mempool)
1472 {
1473         collision_cachedtrace_mempool = mempool;
1474         Collision_Cache_Reset(true);
1475 }
1476
1477 static void Collision_Cache_RebuildHash(void)
1478 {
1479         int index;
1480         int range = collision_cachedtrace_lastused + 1;
1481         unsigned char sequence = collision_cachedtrace_sequence;
1482         int firstfree = collision_cachedtrace_max;
1483         int lastused = 0;
1484         int *hash = collision_cachedtrace_hash;
1485         unsigned int hashindex;
1486         unsigned int *arrayhashindex = collision_cachedtrace_arrayhashindex;
1487         unsigned int *arraynext = collision_cachedtrace_arraynext;
1488         collision_cachedtrace_rebuildhash = false;
1489         memset(collision_cachedtrace_hash, 0, collision_cachedtrace_hashsize * sizeof(int));
1490         for (index = 1;index < range;index++)
1491         {
1492                 if (collision_cachedtrace_arrayused[index] == sequence)
1493                 {
1494                         hashindex = arrayhashindex[index];
1495                         arraynext[index] = hash[hashindex];
1496                         hash[hashindex] = index;
1497                         lastused = index;
1498                 }
1499                 else
1500                 {
1501                         if (firstfree > index)
1502                                 firstfree = index;
1503                         collision_cachedtrace_arrayused[index] = 0;
1504                 }
1505         }
1506         collision_cachedtrace_firstfree = firstfree;
1507         collision_cachedtrace_lastused = lastused;
1508 }
1509
1510 void Collision_Cache_NewFrame(void)
1511 {
1512         if (collision_cache.integer)
1513         {
1514                 if (collision_cachedtrace_max < 128)
1515                         Collision_Cache_Reset(true);
1516         }
1517         else
1518         {
1519                 if (collision_cachedtrace_max > 1)
1520                         Collision_Cache_Reset(true);
1521         }
1522         // rebuild hash if sequence would overflow byte, otherwise increment
1523         if (collision_cachedtrace_sequence == 255)
1524         {
1525                 Collision_Cache_RebuildHash();
1526                 collision_cachedtrace_sequence = 1;
1527         }
1528         else
1529         {
1530                 collision_cachedtrace_rebuildhash = true;
1531                 collision_cachedtrace_sequence++;
1532         }
1533 }
1534
1535 static unsigned int Collision_Cache_HashIndexForArray(unsigned int *array, unsigned int size)
1536 {
1537         unsigned int i;
1538         unsigned int hashindex = 0;
1539         // this is a super-cheesy checksum, designed only for speed
1540         for (i = 0;i < size;i++)
1541                 hashindex += array[i] * (1 + i);
1542         return hashindex;
1543 }
1544
1545 static collision_cachedtrace_t *Collision_Cache_Lookup(dp_model_t *model, const matrix4x4_t *matrix, const matrix4x4_t *inversematrix, const vec3_t start, const vec3_t end, int hitsupercontentsmask, int skipsupercontentsmask)
1546 {
1547         int hashindex = 0;
1548         unsigned int fullhashindex;
1549         int index = 0;
1550         int range;
1551         unsigned char sequence = collision_cachedtrace_sequence;
1552         int *hash = collision_cachedtrace_hash;
1553         unsigned int *arrayfullhashindex = collision_cachedtrace_arrayfullhashindex;
1554         unsigned int *arraynext = collision_cachedtrace_arraynext;
1555         collision_cachedtrace_t *cached = collision_cachedtrace_array + index;
1556         collision_cachedtrace_parameters_t params;
1557         // all non-cached traces use the same index
1558         if (!collision_cache.integer)
1559                 r_refdef.stats[r_stat_photoncache_traced]++;
1560         else
1561         {
1562                 // cached trace lookup
1563                 memset(&params, 0, sizeof(params));
1564                 params.model = model;
1565                 VectorCopy(start, params.start);
1566                 VectorCopy(end,   params.end);
1567                 params.hitsupercontentsmask = hitsupercontentsmask;
1568                 params.skipsupercontentsmask = skipsupercontentsmask;
1569                 params.matrix = *matrix;
1570                 fullhashindex = Collision_Cache_HashIndexForArray((unsigned int *)&params, sizeof(params) / sizeof(unsigned int));
1571                 hashindex = (int)(fullhashindex % (unsigned int)collision_cachedtrace_hashsize);
1572                 for (index = hash[hashindex];index;index = arraynext[index])
1573                 {
1574                         if (arrayfullhashindex[index] != fullhashindex)
1575                                 continue;
1576                         cached = collision_cachedtrace_array + index;
1577                         //if (memcmp(&cached->p, &params, sizeof(params)))
1578                         if (cached->p.model != params.model
1579                          || cached->p.end[0] != params.end[0]
1580                          || cached->p.end[1] != params.end[1]
1581                          || cached->p.end[2] != params.end[2]
1582                          || cached->p.start[0] != params.start[0]
1583                          || cached->p.start[1] != params.start[1]
1584                          || cached->p.start[2] != params.start[2]
1585                          || cached->p.hitsupercontentsmask != params.hitsupercontentsmask
1586                          || cached->p.skipsupercontentsmask != params.skipsupercontentsmask
1587                          || cached->p.matrix.m[0][0] != params.matrix.m[0][0]
1588                          || cached->p.matrix.m[0][1] != params.matrix.m[0][1]
1589                          || cached->p.matrix.m[0][2] != params.matrix.m[0][2]
1590                          || cached->p.matrix.m[0][3] != params.matrix.m[0][3]
1591                          || cached->p.matrix.m[1][0] != params.matrix.m[1][0]
1592                          || cached->p.matrix.m[1][1] != params.matrix.m[1][1]
1593                          || cached->p.matrix.m[1][2] != params.matrix.m[1][2]
1594                          || cached->p.matrix.m[1][3] != params.matrix.m[1][3]
1595                          || cached->p.matrix.m[2][0] != params.matrix.m[2][0]
1596                          || cached->p.matrix.m[2][1] != params.matrix.m[2][1]
1597                          || cached->p.matrix.m[2][2] != params.matrix.m[2][2]
1598                          || cached->p.matrix.m[2][3] != params.matrix.m[2][3]
1599                          || cached->p.matrix.m[3][0] != params.matrix.m[3][0]
1600                          || cached->p.matrix.m[3][1] != params.matrix.m[3][1]
1601                          || cached->p.matrix.m[3][2] != params.matrix.m[3][2]
1602                          || cached->p.matrix.m[3][3] != params.matrix.m[3][3]
1603                         )
1604                                 continue;
1605                         // found a matching trace in the cache
1606                         r_refdef.stats[r_stat_photoncache_cached]++;
1607                         cached->valid = true;
1608                         collision_cachedtrace_arrayused[index] = collision_cachedtrace_sequence;
1609                         return cached;
1610                 }
1611                 r_refdef.stats[r_stat_photoncache_traced]++;
1612                 // find an unused cache entry
1613                 for (index = collision_cachedtrace_firstfree, range = collision_cachedtrace_max;index < range;index++)
1614                         if (collision_cachedtrace_arrayused[index] == 0)
1615                                 break;
1616                 if (index == range)
1617                 {
1618                         // all claimed, but probably some are stale...
1619                         for (index = 1, range = collision_cachedtrace_max;index < range;index++)
1620                                 if (collision_cachedtrace_arrayused[index] != sequence)
1621                                         break;
1622                         if (index < range)
1623                         {
1624                                 // found a stale one, rebuild the hash
1625                                 Collision_Cache_RebuildHash();
1626                         }
1627                         else
1628                         {
1629                                 // we need to grow the cache
1630                                 collision_cachedtrace_max *= 2;
1631                                 Collision_Cache_Reset(false);
1632                                 index = 1;
1633                         }
1634                 }
1635                 // link the new cache entry into the hash bucket
1636                 collision_cachedtrace_firstfree = index + 1;
1637                 if (collision_cachedtrace_lastused < index)
1638                         collision_cachedtrace_lastused = index;
1639                 cached = collision_cachedtrace_array + index;
1640                 collision_cachedtrace_arraynext[index] = collision_cachedtrace_hash[hashindex];
1641                 collision_cachedtrace_hash[hashindex] = index;
1642                 collision_cachedtrace_arrayhashindex[index] = hashindex;
1643                 cached->valid = false;
1644                 cached->p = params;
1645                 collision_cachedtrace_arrayfullhashindex[index] = fullhashindex;
1646                 collision_cachedtrace_arrayused[index] = collision_cachedtrace_sequence;
1647         }
1648         return cached;
1649 }
1650
1651 void Collision_Cache_ClipLineToGenericEntitySurfaces(trace_t *trace, dp_model_t *model, matrix4x4_t *matrix, matrix4x4_t *inversematrix, const vec3_t start, const vec3_t end, int hitsupercontentsmask, int skipsupercontentsmask)
1652 {
1653         collision_cachedtrace_t *cached = Collision_Cache_Lookup(model, matrix, inversematrix, start, end, hitsupercontentsmask, skipsupercontentsmask);
1654         if (cached->valid)
1655         {
1656                 *trace = cached->result;
1657                 return;
1658         }
1659
1660         Collision_ClipLineToGenericEntity(trace, model, NULL, NULL, vec3_origin, vec3_origin, 0, matrix, inversematrix, start, end, hitsupercontentsmask, skipsupercontentsmask, collision_extendmovelength.value, true);
1661
1662         cached->result = *trace;
1663 }
1664
1665 void Collision_Cache_ClipLineToWorldSurfaces(trace_t *trace, dp_model_t *model, const vec3_t start, const vec3_t end, int hitsupercontentsmask, int skipsupercontentsmask)
1666 {
1667         collision_cachedtrace_t *cached = Collision_Cache_Lookup(model, &identitymatrix, &identitymatrix, start, end, hitsupercontentsmask, skipsupercontentsmask);
1668         if (cached->valid)
1669         {
1670                 *trace = cached->result;
1671                 return;
1672         }
1673
1674         Collision_ClipLineToWorld(trace, model, start, end, hitsupercontentsmask, skipsupercontentsmask, collision_extendmovelength.value, true);
1675
1676         cached->result = *trace;
1677 }
1678
1679 typedef struct extendtraceinfo_s
1680 {
1681         trace_t *trace;
1682         float realstart[3];
1683         float realend[3];
1684         float realdelta[3];
1685         float extendstart[3];
1686         float extendend[3];
1687         float extenddelta[3];
1688         float reallength;
1689         float extendlength;
1690         float scaletoextend;
1691         float extend;
1692 }
1693 extendtraceinfo_t;
1694
1695 static void Collision_ClipExtendPrepare(extendtraceinfo_t *extendtraceinfo, trace_t *trace, const vec3_t tstart, const vec3_t tend, float textend)
1696 {
1697         memset(trace, 0, sizeof(*trace));
1698         trace->fraction = 1;
1699
1700         extendtraceinfo->trace = trace;
1701         VectorCopy(tstart, extendtraceinfo->realstart);
1702         VectorCopy(tend, extendtraceinfo->realend);
1703         VectorSubtract(extendtraceinfo->realend, extendtraceinfo->realstart, extendtraceinfo->realdelta);
1704         VectorCopy(extendtraceinfo->realstart, extendtraceinfo->extendstart);
1705         VectorCopy(extendtraceinfo->realend, extendtraceinfo->extendend);
1706         VectorCopy(extendtraceinfo->realdelta, extendtraceinfo->extenddelta);
1707         extendtraceinfo->reallength = VectorLength(extendtraceinfo->realdelta);
1708         extendtraceinfo->extendlength = extendtraceinfo->reallength;
1709         extendtraceinfo->scaletoextend = 1.0f;
1710         extendtraceinfo->extend = textend;
1711
1712         // make the trace longer according to the extend parameter
1713         if (extendtraceinfo->reallength && extendtraceinfo->extend)
1714         {
1715                 extendtraceinfo->extendlength = extendtraceinfo->reallength + extendtraceinfo->extend;
1716                 extendtraceinfo->scaletoextend = extendtraceinfo->extendlength / extendtraceinfo->reallength;
1717                 VectorMA(extendtraceinfo->realstart, extendtraceinfo->scaletoextend, extendtraceinfo->realdelta, extendtraceinfo->extendend);
1718                 VectorSubtract(extendtraceinfo->extendend, extendtraceinfo->extendstart, extendtraceinfo->extenddelta);
1719         }
1720 }
1721
1722 static void Collision_ClipExtendFinish(extendtraceinfo_t *extendtraceinfo)
1723 {
1724         trace_t *trace = extendtraceinfo->trace;
1725
1726         if (trace->fraction != 1.0f)
1727         {
1728                 // undo the extended trace length
1729                 trace->fraction *= extendtraceinfo->scaletoextend;
1730
1731                 // if the extended trace hit something that the unextended trace did not hit (even considering the collision_impactnudge), then we have to clear the hit information
1732                 if (trace->fraction > 1.0f)
1733                 {
1734                         // note that ent may refer to either startsolid or fraction<1, we can't restore the startsolid ent unfortunately
1735                         trace->ent = NULL;
1736                         trace->hitq3surfaceflags = 0;
1737                         trace->hitsupercontents = 0;
1738                         trace->hittexture = NULL;
1739                         VectorClear(trace->plane.normal);
1740                         trace->plane.dist = 0.0f;
1741                 }
1742         }
1743
1744         // clamp things
1745         trace->fraction = bound(0, trace->fraction, 1);
1746
1747         // calculate the end position
1748         VectorMA(extendtraceinfo->realstart, trace->fraction, extendtraceinfo->realdelta, trace->endpos);
1749 }
1750
1751 void Collision_ClipToGenericEntity(trace_t *trace, dp_model_t *model, const frameblend_t *frameblend, const skeleton_t *skeleton, const vec3_t bodymins, const vec3_t bodymaxs, int bodysupercontents, matrix4x4_t *matrix, matrix4x4_t *inversematrix, const vec3_t tstart, const vec3_t mins, const vec3_t maxs, const vec3_t tend, int hitsupercontentsmask, int skipsupercontentsmask, float extend)
1752 {
1753         vec3_t starttransformed, endtransformed;
1754         extendtraceinfo_t extendtraceinfo;
1755         Collision_ClipExtendPrepare(&extendtraceinfo, trace, tstart, tend, extend);
1756
1757         Matrix4x4_Transform(inversematrix, extendtraceinfo.extendstart, starttransformed);
1758         Matrix4x4_Transform(inversematrix, extendtraceinfo.extendend, endtransformed);
1759 #if COLLISIONPARANOID >= 3
1760         Con_Printf("trans(%f %f %f -> %f %f %f, %f %f %f -> %f %f %f)", extendtraceinfo.extendstart[0], extendtraceinfo.extendstart[1], extendtraceinfo.extendstart[2], starttransformed[0], starttransformed[1], starttransformed[2], extendtraceinfo.extendend[0], extendtraceinfo.extendend[1], extendtraceinfo.extendend[2], endtransformed[0], endtransformed[1], endtransformed[2]);
1761 #endif
1762
1763         if (model && model->TraceBox)
1764         {
1765                 if(model->TraceBrush && (inversematrix->m[0][1] || inversematrix->m[0][2] || inversematrix->m[1][0] || inversematrix->m[1][2] || inversematrix->m[2][0] || inversematrix->m[2][1]))
1766                 {
1767                         // we get here if TraceBrush exists, AND we have a rotation component (SOLID_BSP case)
1768                         // using starttransformed, endtransformed is WRONG in this case!
1769                         // should rather build a brush and trace using it
1770                         colboxbrushf_t thisbrush_start, thisbrush_end;
1771                         Collision_BrushForBox(&thisbrush_start, mins, maxs, 0, 0, NULL);
1772                         Collision_BrushForBox(&thisbrush_end, mins, maxs, 0, 0, NULL);
1773                         Collision_TranslateBrush(extendtraceinfo.extendstart, &thisbrush_start.brush);
1774                         Collision_TranslateBrush(extendtraceinfo.extendend, &thisbrush_end.brush);
1775                         Collision_TransformBrush(inversematrix, &thisbrush_start.brush);
1776                         Collision_TransformBrush(inversematrix, &thisbrush_end.brush);
1777                         //Collision_TranslateBrush(starttransformed, &thisbrush_start.brush);
1778                         //Collision_TranslateBrush(endtransformed, &thisbrush_end.brush);
1779                         model->TraceBrush(model, frameblend, skeleton, trace, &thisbrush_start.brush, &thisbrush_end.brush, hitsupercontentsmask, skipsupercontentsmask);
1780                 }
1781                 else // this is only approximate if rotated, quite useless
1782                         model->TraceBox(model, frameblend, skeleton, trace, starttransformed, mins, maxs, endtransformed, hitsupercontentsmask, skipsupercontentsmask);
1783         }
1784         else // and this requires that the transformation matrix doesn't have angles components, like SV_TraceBox ensures; FIXME may get called if a model is SOLID_BSP but has no TraceBox function
1785                 Collision_ClipTrace_Box(trace, bodymins, bodymaxs, starttransformed, mins, maxs, endtransformed, hitsupercontentsmask, skipsupercontentsmask, bodysupercontents, 0, NULL);
1786
1787         Collision_ClipExtendFinish(&extendtraceinfo);
1788
1789         // transform plane
1790         // NOTE: this relies on plane.dist being directly after plane.normal
1791         Matrix4x4_TransformPositivePlane(matrix, trace->plane.normal[0], trace->plane.normal[1], trace->plane.normal[2], trace->plane.dist, trace->plane.normal_and_dist);
1792 }
1793
1794 void Collision_ClipToWorld(trace_t *trace, dp_model_t *model, const vec3_t tstart, const vec3_t mins, const vec3_t maxs, const vec3_t tend, int hitsupercontentsmask, int skipsupercontentsmask, float extend)
1795 {
1796         extendtraceinfo_t extendtraceinfo;
1797         Collision_ClipExtendPrepare(&extendtraceinfo, trace, tstart, tend, extend);
1798         // ->TraceBox: TraceBrush not needed here, as worldmodel is never rotated
1799         if (model && model->TraceBox)
1800                 model->TraceBox(model, NULL, NULL, trace, extendtraceinfo.extendstart, mins, maxs, extendtraceinfo.extendend, hitsupercontentsmask, skipsupercontentsmask);
1801         Collision_ClipExtendFinish(&extendtraceinfo);
1802 }
1803
1804 void Collision_ClipLineToGenericEntity(trace_t *trace, dp_model_t *model, const frameblend_t *frameblend, const skeleton_t *skeleton, const vec3_t bodymins, const vec3_t bodymaxs, int bodysupercontents, matrix4x4_t *matrix, matrix4x4_t *inversematrix, const vec3_t tstart, const vec3_t tend, int hitsupercontentsmask, int skipsupercontentsmask, float extend, qboolean hitsurfaces)
1805 {
1806         vec3_t starttransformed, endtransformed;
1807         extendtraceinfo_t extendtraceinfo;
1808         Collision_ClipExtendPrepare(&extendtraceinfo, trace, tstart, tend, extend);
1809
1810         Matrix4x4_Transform(inversematrix, extendtraceinfo.extendstart, starttransformed);
1811         Matrix4x4_Transform(inversematrix, extendtraceinfo.extendend, endtransformed);
1812 #if COLLISIONPARANOID >= 3
1813         Con_Printf("trans(%f %f %f -> %f %f %f, %f %f %f -> %f %f %f)", extendtraceinfo.extendstart[0], extendtraceinfo.extendstart[1], extendtraceinfo.extendstart[2], starttransformed[0], starttransformed[1], starttransformed[2], extendtraceinfo.extendend[0], extendtraceinfo.extendend[1], extendtraceinfo.extendend[2], endtransformed[0], endtransformed[1], endtransformed[2]);
1814 #endif
1815
1816         if (model && model->TraceLineAgainstSurfaces && hitsurfaces)
1817                 model->TraceLineAgainstSurfaces(model, frameblend, skeleton, trace, starttransformed, endtransformed, hitsupercontentsmask, skipsupercontentsmask);
1818         else if (model && model->TraceLine)
1819                 model->TraceLine(model, frameblend, skeleton, trace, starttransformed, endtransformed, hitsupercontentsmask, skipsupercontentsmask);
1820         else
1821                 Collision_ClipTrace_Box(trace, bodymins, bodymaxs, starttransformed, vec3_origin, vec3_origin, endtransformed, hitsupercontentsmask, skipsupercontentsmask, bodysupercontents, 0, NULL);
1822
1823         Collision_ClipExtendFinish(&extendtraceinfo);
1824
1825         // transform plane
1826         // NOTE: this relies on plane.dist being directly after plane.normal
1827         Matrix4x4_TransformPositivePlane(matrix, trace->plane.normal[0], trace->plane.normal[1], trace->plane.normal[2], trace->plane.dist, trace->plane.normal_and_dist);
1828 }
1829
1830 void Collision_ClipLineToWorld(trace_t *trace, dp_model_t *model, const vec3_t tstart, const vec3_t tend, int hitsupercontentsmask, int skipsupercontentsmask, float extend, qboolean hitsurfaces)
1831 {
1832         extendtraceinfo_t extendtraceinfo;
1833         Collision_ClipExtendPrepare(&extendtraceinfo, trace, tstart, tend, extend);
1834
1835         if (model && model->TraceLineAgainstSurfaces && hitsurfaces)
1836                 model->TraceLineAgainstSurfaces(model, NULL, NULL, trace, extendtraceinfo.extendstart, extendtraceinfo.extendend, hitsupercontentsmask, skipsupercontentsmask);
1837         else if (model && model->TraceLine)
1838                 model->TraceLine(model, NULL, NULL, trace, extendtraceinfo.extendstart, extendtraceinfo.extendend, hitsupercontentsmask, skipsupercontentsmask);
1839
1840         Collision_ClipExtendFinish(&extendtraceinfo);
1841 }
1842
1843 void Collision_ClipPointToGenericEntity(trace_t *trace, dp_model_t *model, const frameblend_t *frameblend, const skeleton_t *skeleton, const vec3_t bodymins, const vec3_t bodymaxs, int bodysupercontents, matrix4x4_t *matrix, matrix4x4_t *inversematrix, const vec3_t start, int hitsupercontentsmask, int skipsupercontentsmask)
1844 {
1845         float starttransformed[3];
1846         memset(trace, 0, sizeof(*trace));
1847         trace->fraction = 1;
1848
1849         Matrix4x4_Transform(inversematrix, start, starttransformed);
1850 #if COLLISIONPARANOID >= 3
1851         Con_Printf("trans(%f %f %f -> %f %f %f)", start[0], start[1], start[2], starttransformed[0], starttransformed[1], starttransformed[2]);
1852 #endif
1853
1854         if (model && model->TracePoint)
1855                 model->TracePoint(model, NULL, NULL, trace, starttransformed, hitsupercontentsmask, skipsupercontentsmask);
1856         else
1857                 Collision_ClipTrace_Point(trace, bodymins, bodymaxs, starttransformed, hitsupercontentsmask, skipsupercontentsmask, bodysupercontents, 0, NULL);
1858
1859         VectorCopy(start, trace->endpos);
1860         // transform plane
1861         // NOTE: this relies on plane.dist being directly after plane.normal
1862         Matrix4x4_TransformPositivePlane(matrix, trace->plane.normal[0], trace->plane.normal[1], trace->plane.normal[2], trace->plane.dist, trace->plane.normal_and_dist);
1863 }
1864
1865 void Collision_ClipPointToWorld(trace_t *trace, dp_model_t *model, const vec3_t start, int hitsupercontentsmask, int skipsupercontentsmask)
1866 {
1867         memset(trace, 0, sizeof(*trace));
1868         trace->fraction = 1;
1869         if (model && model->TracePoint)
1870                 model->TracePoint(model, NULL, NULL, trace, start, hitsupercontentsmask, skipsupercontentsmask);
1871         VectorCopy(start, trace->endpos);
1872 }
1873
1874 void Collision_CombineTraces(trace_t *cliptrace, const trace_t *trace, void *touch, qboolean isbmodel)
1875 {
1876         // take the 'best' answers from the new trace and combine with existing data
1877         if (trace->allsolid)
1878                 cliptrace->allsolid = true;
1879         if (trace->startsolid)
1880         {
1881                 if (isbmodel)
1882                         cliptrace->bmodelstartsolid = true;
1883                 cliptrace->startsolid = true;
1884                 if (cliptrace->fraction == 1)
1885                         cliptrace->ent = touch;
1886                 if (cliptrace->startdepth > trace->startdepth)
1887                 {
1888                         cliptrace->startdepth = trace->startdepth;
1889                         VectorCopy(trace->startdepthnormal, cliptrace->startdepthnormal);
1890                 }
1891         }
1892         // don't set this except on the world, because it can easily confuse
1893         // monsters underwater if there's a bmodel involved in the trace
1894         // (inopen && inwater is how they check water visibility)
1895         //if (trace->inopen)
1896         //      cliptrace->inopen = true;
1897         if (trace->inwater)
1898                 cliptrace->inwater = true;
1899         if ((trace->fraction < cliptrace->fraction) && (VectorLength2(trace->plane.normal) > 0))
1900         {
1901                 cliptrace->fraction = trace->fraction;
1902                 VectorCopy(trace->endpos, cliptrace->endpos);
1903                 cliptrace->plane = trace->plane;
1904                 cliptrace->ent = touch;
1905                 cliptrace->hitsupercontents = trace->hitsupercontents;
1906                 cliptrace->hitq3surfaceflags = trace->hitq3surfaceflags;
1907                 cliptrace->hittexture = trace->hittexture;
1908         }
1909         cliptrace->startsupercontents |= trace->startsupercontents;
1910 }