6 #define COLLISION_EDGEDIR_DOT_EPSILON (0.999f)
7 #define COLLISION_EDGECROSS_MINLENGTH2 (1.0f / 4194304.0f)
8 #define COLLISION_SNAPSCALE (32.0f)
9 #define COLLISION_SNAP (1.0f / COLLISION_SNAPSCALE)
10 #define COLLISION_SNAP2 (2.0f / COLLISION_SNAPSCALE)
11 #define COLLISION_PLANE_DIST_EPSILON (2.0f / COLLISION_SNAPSCALE)
13 cvar_t collision_impactnudge = {CVAR_CLIENT | CVAR_SERVER, "collision_impactnudge", "0.03125", "how much to back off from the impact"};
14 cvar_t collision_extendmovelength = {CVAR_CLIENT | CVAR_SERVER, "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)"};
15 cvar_t collision_extendtraceboxlength = {CVAR_CLIENT | CVAR_SERVER, "collision_extendtraceboxlength", "1", "internal bias for tracebox() qc builtin to account for collision_impactnudge (this does not alter the final trace length)"};
16 cvar_t collision_extendtracelinelength = {CVAR_CLIENT | CVAR_SERVER, "collision_extendtracelinelength", "1", "internal bias for traceline() qc builtin to account for collision_impactnudge (this does not alter the final trace length)"};
17 cvar_t collision_debug_tracelineasbox = {CVAR_CLIENT | CVAR_SERVER, "collision_debug_tracelineasbox", "0", "workaround for any bugs in Collision_TraceLineBrushFloat by using Collision_TraceBrushBrushFloat"};
18 cvar_t collision_cache = {CVAR_CLIENT | CVAR_SERVER, "collision_cache", "1", "store results of collision traces for next frame to reuse if possible (optimization)"};
19 cvar_t collision_triangle_bevelsides = {CVAR_CLIENT | CVAR_SERVER, "collision_triangle_bevelsides", "0", "generate sloped edge planes on triangles - if 0, see axialedgeplanes"};
20 cvar_t collision_triangle_axialsides = {CVAR_CLIENT | CVAR_SERVER, "collision_triangle_axialsides", "1", "generate axially-aligned edge planes on triangles - otherwise use perpendicular edge planes"};
21 cvar_t collision_bih_fullrecursion = {CVAR_CLIENT | CVAR_SERVER, "collision_bih_fullrecursion", "0", "debugging option to disable the bih recursion optimizations by iterating the entire tree"};
23 mempool_t *collision_mempool;
25 void Collision_Init_Commands (void)
27 Cvar_RegisterVariable(&collision_impactnudge);
28 Cvar_RegisterVariable(&collision_extendmovelength);
29 Cvar_RegisterVariable(&collision_extendtracelinelength);
30 Cvar_RegisterVariable(&collision_extendtraceboxlength);
31 Cvar_RegisterVariable(&collision_debug_tracelineasbox);
32 Cvar_RegisterVariable(&collision_cache);
33 Cvar_RegisterVariable(&collision_triangle_bevelsides);
34 Cvar_RegisterVariable(&collision_triangle_axialsides);
35 Cvar_RegisterVariable(&collision_bih_fullrecursion);
38 void Collision_Init (void)
40 collision_mempool = Mem_AllocPool("collision cache", 0, NULL);
41 Collision_Cache_Init(collision_mempool);
57 static void Collision_PrintBrushAsQHull(colbrushf_t *brush, const char *name)
60 Con_Printf("3 %s\n%i\n", name, brush->numpoints);
61 for (i = 0;i < brush->numpoints;i++)
62 Con_Printf("%f %f %f\n", brush->points[i].v[0], brush->points[i].v[1], brush->points[i].v[2]);
64 Con_Printf("4\n%i\n", brush->numplanes);
65 for (i = 0;i < brush->numplanes;i++)
66 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);
69 static void Collision_ValidateBrush(colbrushf_t *brush)
71 int j, k, pointsoffplanes, pointonplanes, pointswithinsufficientplanes, printbrush;
74 if (!brush->numpoints)
76 Con_Print("Collision_ValidateBrush: brush with no points!\n");
80 // it's ok for a brush to have one point and no planes...
81 if (brush->numplanes == 0 && brush->numpoints != 1)
83 Con_Print("Collision_ValidateBrush: brush with no planes and more than one point!\n");
90 pointswithinsufficientplanes = 0;
91 for (k = 0;k < brush->numplanes;k++)
92 if (DotProduct(brush->planes[k].normal, brush->planes[k].normal) < 0.0001f)
93 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);
94 for (j = 0;j < brush->numpoints;j++)
97 for (k = 0;k < brush->numplanes;k++)
99 d = DotProduct(brush->points[j].v, brush->planes[k].normal) - brush->planes[k].dist;
100 if (d > COLLISION_PLANE_DIST_EPSILON)
102 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);
105 if (fabs(d) > COLLISION_PLANE_DIST_EPSILON)
110 if (pointonplanes < 3)
111 pointswithinsufficientplanes++;
113 if (pointswithinsufficientplanes)
115 Con_Print("Collision_ValidateBrush: some points have insufficient planes, every point must be on at least 3 planes to form a corner.\n");
118 if (pointsoffplanes == 0) // all points are on all planes
120 Con_Print("Collision_ValidateBrush: all points lie on all planes (degenerate, no brush volume!)\n");
125 Collision_PrintBrushAsQHull(brush, "unnamed");
128 static float nearestplanedist_float(const float *normal, const colpointf_t *points, int numpoints)
130 float dist, bestdist;
133 bestdist = DotProduct(points->v, normal);
137 dist = DotProduct(points->v, normal);
138 bestdist = min(bestdist, dist);
144 static float furthestplanedist_float(const float *normal, const colpointf_t *points, int numpoints)
146 float dist, bestdist;
149 bestdist = DotProduct(points->v, normal);
153 dist = DotProduct(points->v, normal);
154 bestdist = max(bestdist, dist);
160 static void Collision_CalcEdgeDirsForPolygonBrushFloat(colbrushf_t *brush)
163 for (i = 0, j = brush->numpoints - 1;i < brush->numpoints;j = i, i++)
164 VectorSubtract(brush->points[i].v, brush->points[j].v, brush->edgedirs[j].v);
167 colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalplanes, const colplanef_t *originalplanes, int supercontents, int q3surfaceflags, const texture_t *texture, int hasaabbplanes)
169 // TODO: planesbuf could be replaced by a remapping table
170 int j, k, w, xyzflags;
171 int numpointsbuf = 0, maxpointsbuf = 256, numedgedirsbuf = 0, maxedgedirsbuf = 256, numplanesbuf = 0, maxplanesbuf = 256, numelementsbuf = 0, maxelementsbuf = 256;
175 colpointf_t pointsbuf[256];
176 colpointf_t edgedirsbuf[256];
177 colplanef_t planesbuf[256];
178 int elementsbuf[1024];
179 int polypointbuf[256];
184 // enable these if debugging to avoid seeing garbage in unused data-
185 memset(pointsbuf, 0, sizeof(pointsbuf));
186 memset(edgedirsbuf, 0, sizeof(edgedirsbuf));
187 memset(planesbuf, 0, sizeof(planesbuf));
188 memset(elementsbuf, 0, sizeof(elementsbuf));
189 memset(polypointbuf, 0, sizeof(polypointbuf));
190 memset(p, 0, sizeof(p));
193 // check if there are too many planes and skip the brush
194 if (numoriginalplanes >= maxplanesbuf)
196 Con_DPrint("Collision_NewBrushFromPlanes: failed to build collision brush: too many planes for buffer\n");
200 // figure out how large a bounding box we need to properly compute this brush
202 for (j = 0;j < numoriginalplanes;j++)
203 maxdist = max(maxdist, fabs(originalplanes[j].dist));
204 // now make it large enough to enclose the entire brush, and round it off to a reasonable multiple of 1024
205 maxdist = floor(maxdist * (4.0 / 1024.0) + 2) * 1024.0;
206 // construct a collision brush (points, planes, and renderable mesh) from
207 // a set of planes, this also optimizes out any unnecessary planes (ones
208 // whose polygon is clipped away by the other planes)
209 for (j = 0;j < numoriginalplanes;j++)
213 VectorCopy(originalplanes[j].normal, planesbuf[numplanesbuf].normal);
214 planesbuf[numplanesbuf].dist = originalplanes[j].dist;
215 planesbuf[numplanesbuf].q3surfaceflags = originalplanes[j].q3surfaceflags;
216 planesbuf[numplanesbuf].texture = originalplanes[j].texture;
219 // create a large polygon from the plane
221 PolygonD_QuadForPlane(p[w], originalplanes[j].normal[0], originalplanes[j].normal[1], originalplanes[j].normal[2], originalplanes[j].dist, maxdist);
223 // clip it by all other planes
224 for (k = 0;k < numoriginalplanes && pnumpoints >= 3 && pnumpoints <= pmaxpoints;k++)
226 // skip the plane this polygon
227 // (nothing happens if it is processed, this is just an optimization)
230 // we want to keep the inside of the brush plane so we flip
232 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);
237 // if nothing is left, skip it
240 //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);
244 for (k = 0;k < pnumpoints;k++)
248 for (l = 0;l < numoriginalplanes;l++)
249 if (fabs(DotProduct(&p[w][k*3], originalplanes[l].normal) - originalplanes[l].dist) < COLLISION_PLANE_DIST_EPSILON)
256 Con_DPrintf("Collision_NewBrushFromPlanes: warning: polygon point does not lie on at least 3 planes\n");
260 // check if there are too many polygon vertices for buffer
261 if (pnumpoints > pmaxpoints)
263 Con_DPrint("Collision_NewBrushFromPlanes: failed to build collision brush: too many points for buffer\n");
267 // check if there are too many triangle elements for buffer
268 if (numelementsbuf + (pnumpoints - 2) * 3 > maxelementsbuf)
270 Con_DPrint("Collision_NewBrushFromPlanes: failed to build collision brush: too many triangle elements for buffer\n");
274 // add the unique points for this polygon
275 for (k = 0;k < pnumpoints;k++)
279 // downgrade to float precision before comparing
280 VectorCopy(&p[w][k*3], v);
282 // check if there is already a matching point (no duplicates)
283 for (m = 0;m < numpointsbuf;m++)
284 if (VectorDistance2(v, pointsbuf[m].v) < COLLISION_SNAP2)
287 // if there is no match, add a new one
288 if (m == numpointsbuf)
290 // check if there are too many and skip the brush
291 if (numpointsbuf >= maxpointsbuf)
293 Con_DPrint("Collision_NewBrushFromPlanes: failed to build collision brush: too many points for buffer\n");
297 VectorCopy(&p[w][k*3], pointsbuf[numpointsbuf].v);
301 // store the index into a buffer
305 // add the triangles for the polygon
306 // (this particular code makes a triangle fan)
307 for (k = 0;k < pnumpoints - 2;k++)
309 elementsbuf[numelementsbuf++] = polypointbuf[0];
310 elementsbuf[numelementsbuf++] = polypointbuf[k + 1];
311 elementsbuf[numelementsbuf++] = polypointbuf[k + 2];
314 // add the unique edgedirs for this polygon
315 for (k = 0, n = pnumpoints-1;k < pnumpoints;n = k, k++)
319 // downgrade to float precision before comparing
320 VectorSubtract(&p[w][k*3], &p[w][n*3], dir);
321 VectorNormalize(dir);
323 // check if there is already a matching edgedir (no duplicates)
324 for (m = 0;m < numedgedirsbuf;m++)
325 if (DotProduct(dir, edgedirsbuf[m].v) >= COLLISION_EDGEDIR_DOT_EPSILON)
327 // skip this if there is
328 if (m < numedgedirsbuf)
331 // try again with negated edgedir
332 VectorNegate(dir, dir);
333 // check if there is already a matching edgedir (no duplicates)
334 for (m = 0;m < numedgedirsbuf;m++)
335 if (DotProduct(dir, edgedirsbuf[m].v) >= COLLISION_EDGEDIR_DOT_EPSILON)
337 // if there is no match, add a new one
338 if (m == numedgedirsbuf)
340 // check if there are too many and skip the brush
341 if (numedgedirsbuf >= maxedgedirsbuf)
343 Con_DPrint("Collision_NewBrushFromPlanes: failed to build collision brush: too many edgedirs for buffer\n");
347 VectorCopy(dir, edgedirsbuf[numedgedirsbuf].v);
352 // if any normal is not purely axial, it's not an axis-aligned box
353 if (isaabb && (originalplanes[j].normal[0] == 0) + (originalplanes[j].normal[1] == 0) + (originalplanes[j].normal[2] == 0) < 2)
357 // if nothing is left, there's nothing to allocate
358 if (numplanesbuf < 4)
360 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);
364 // if no triangles or points could be constructed, then this routine failed but the brush is not discarded
365 if (numelementsbuf < 12 || numpointsbuf < 4)
366 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);
368 // validate plane distances
369 for (j = 0;j < numplanesbuf;j++)
371 float d = furthestplanedist_float(planesbuf[j].normal, pointsbuf, numpointsbuf);
372 if (fabs(planesbuf[j].dist - d) > COLLISION_PLANE_DIST_EPSILON)
373 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);
376 // allocate the brush and copy to it
377 brush = (colbrushf_t *)Mem_Alloc(mempool, sizeof(colbrushf_t) + sizeof(colpointf_t) * numpointsbuf + sizeof(colpointf_t) * numedgedirsbuf + sizeof(colplanef_t) * numplanesbuf + sizeof(int) * numelementsbuf);
378 brush->isaabb = isaabb;
379 brush->hasaabbplanes = hasaabbplanes;
380 brush->supercontents = supercontents;
381 brush->numplanes = numplanesbuf;
382 brush->numedgedirs = numedgedirsbuf;
383 brush->numpoints = numpointsbuf;
384 brush->numtriangles = numelementsbuf / 3;
385 brush->planes = (colplanef_t *)(brush + 1);
386 brush->points = (colpointf_t *)(brush->planes + brush->numplanes);
387 brush->edgedirs = (colpointf_t *)(brush->points + brush->numpoints);
388 brush->elements = (int *)(brush->points + brush->numpoints);
389 brush->q3surfaceflags = q3surfaceflags;
390 brush->texture = texture;
391 for (j = 0;j < brush->numpoints;j++)
393 brush->points[j].v[0] = pointsbuf[j].v[0];
394 brush->points[j].v[1] = pointsbuf[j].v[1];
395 brush->points[j].v[2] = pointsbuf[j].v[2];
397 for (j = 0;j < brush->numedgedirs;j++)
399 brush->edgedirs[j].v[0] = edgedirsbuf[j].v[0];
400 brush->edgedirs[j].v[1] = edgedirsbuf[j].v[1];
401 brush->edgedirs[j].v[2] = edgedirsbuf[j].v[2];
403 for (j = 0;j < brush->numplanes;j++)
405 brush->planes[j].normal[0] = planesbuf[j].normal[0];
406 brush->planes[j].normal[1] = planesbuf[j].normal[1];
407 brush->planes[j].normal[2] = planesbuf[j].normal[2];
408 brush->planes[j].dist = planesbuf[j].dist;
409 brush->planes[j].q3surfaceflags = planesbuf[j].q3surfaceflags;
410 brush->planes[j].texture = planesbuf[j].texture;
412 for (j = 0;j < brush->numtriangles * 3;j++)
413 brush->elements[j] = elementsbuf[j];
416 VectorClear(brush->mins);
417 VectorClear(brush->maxs);
418 for (j = 0;j < min(6, numoriginalplanes);j++)
420 if (originalplanes[j].normal[0] == 1) {xyzflags |= 1;brush->maxs[0] = originalplanes[j].dist;}
421 else if (originalplanes[j].normal[0] == -1) {xyzflags |= 2;brush->mins[0] = -originalplanes[j].dist;}
422 else if (originalplanes[j].normal[1] == 1) {xyzflags |= 4;brush->maxs[1] = originalplanes[j].dist;}
423 else if (originalplanes[j].normal[1] == -1) {xyzflags |= 8;brush->mins[1] = -originalplanes[j].dist;}
424 else if (originalplanes[j].normal[2] == 1) {xyzflags |= 16;brush->maxs[2] = originalplanes[j].dist;}
425 else if (originalplanes[j].normal[2] == -1) {xyzflags |= 32;brush->mins[2] = -originalplanes[j].dist;}
427 // if not all xyzflags were set, then this is not a brush from q3map/q3map2, and needs reconstruction of the bounding box
428 // (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)
431 VectorCopy(brush->points[0].v, brush->mins);
432 VectorCopy(brush->points[0].v, brush->maxs);
433 for (j = 1;j < brush->numpoints;j++)
435 brush->mins[0] = min(brush->mins[0], brush->points[j].v[0]);
436 brush->mins[1] = min(brush->mins[1], brush->points[j].v[1]);
437 brush->mins[2] = min(brush->mins[2], brush->points[j].v[2]);
438 brush->maxs[0] = max(brush->maxs[0], brush->points[j].v[0]);
439 brush->maxs[1] = max(brush->maxs[1], brush->points[j].v[1]);
440 brush->maxs[2] = max(brush->maxs[2], brush->points[j].v[2]);
449 Collision_ValidateBrush(brush);
455 void Collision_CalcPlanesForTriangleBrushFloat(colbrushf_t *brush)
457 float edge0[3], edge1[3], edge2[3];
460 TriangleNormal(brush->points[0].v, brush->points[1].v, brush->points[2].v, brush->planes[0].normal);
461 if (DotProduct(brush->planes[0].normal, brush->planes[0].normal) < 0.0001f)
463 // there's no point in processing a degenerate triangle (GIGO - Garbage In, Garbage Out)
464 // note that some of these exist in q3bsp bspline patches
465 brush->numplanes = 0;
469 // there are 5 planes (front, back, sides) and 3 edges
470 brush->numplanes = 5;
471 brush->numedgedirs = 3;
472 VectorNormalize(brush->planes[0].normal);
473 brush->planes[0].dist = DotProduct(brush->points->v, brush->planes[0].normal);
474 VectorNegate(brush->planes[0].normal, brush->planes[1].normal);
475 brush->planes[1].dist = -brush->planes[0].dist;
476 // edge directions are easy to calculate
477 VectorSubtract(brush->points[2].v, brush->points[0].v, edge0);
478 VectorSubtract(brush->points[0].v, brush->points[1].v, edge1);
479 VectorSubtract(brush->points[1].v, brush->points[2].v, edge2);
480 VectorCopy(edge0, brush->edgedirs[0].v);
481 VectorCopy(edge1, brush->edgedirs[1].v);
482 VectorCopy(edge2, brush->edgedirs[2].v);
483 // now select an algorithm to generate the side planes
484 if (collision_triangle_bevelsides.integer)
486 // 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
487 CrossProduct(edge0, brush->planes->normal, brush->planes[2].normal);
488 CrossProduct(edge1, brush->planes->normal, brush->planes[3].normal);
489 CrossProduct(edge2, brush->planes->normal, brush->planes[4].normal);
490 VectorNormalize(brush->planes[2].normal);
491 VectorNormalize(brush->planes[3].normal);
492 VectorNormalize(brush->planes[4].normal);
493 VectorAdd(brush->planes[2].normal, brush->planes[0].normal, brush->planes[2].normal);
494 VectorAdd(brush->planes[3].normal, brush->planes[0].normal, brush->planes[3].normal);
495 VectorAdd(brush->planes[4].normal, brush->planes[0].normal, brush->planes[4].normal);
496 VectorNormalize(brush->planes[2].normal);
497 VectorNormalize(brush->planes[3].normal);
498 VectorNormalize(brush->planes[4].normal);
500 else if (collision_triangle_axialsides.integer)
502 float projectionnormal[3], projectionedge0[3], projectionedge1[3], projectionedge2[3];
504 float dist, bestdist;
505 bestdist = fabs(brush->planes[0].normal[0]);
507 for (i = 1;i < 3;i++)
509 dist = fabs(brush->planes[0].normal[i]);
516 VectorClear(projectionnormal);
517 if (brush->planes[0].normal[best] < 0)
518 projectionnormal[best] = -1;
520 projectionnormal[best] = 1;
521 VectorCopy(edge0, projectionedge0);
522 VectorCopy(edge1, projectionedge1);
523 VectorCopy(edge2, projectionedge2);
524 projectionedge0[best] = 0;
525 projectionedge1[best] = 0;
526 projectionedge2[best] = 0;
527 CrossProduct(projectionedge0, projectionnormal, brush->planes[2].normal);
528 CrossProduct(projectionedge1, projectionnormal, brush->planes[3].normal);
529 CrossProduct(projectionedge2, projectionnormal, brush->planes[4].normal);
530 VectorNormalize(brush->planes[2].normal);
531 VectorNormalize(brush->planes[3].normal);
532 VectorNormalize(brush->planes[4].normal);
536 CrossProduct(edge0, brush->planes->normal, brush->planes[2].normal);
537 CrossProduct(edge1, brush->planes->normal, brush->planes[3].normal);
538 CrossProduct(edge2, brush->planes->normal, brush->planes[4].normal);
539 VectorNormalize(brush->planes[2].normal);
540 VectorNormalize(brush->planes[3].normal);
541 VectorNormalize(brush->planes[4].normal);
543 brush->planes[2].dist = DotProduct(brush->points[2].v, brush->planes[2].normal);
544 brush->planes[3].dist = DotProduct(brush->points[0].v, brush->planes[3].normal);
545 brush->planes[4].dist = DotProduct(brush->points[1].v, brush->planes[4].normal);
547 if (developer_extra.integer)
550 // validity check - will be disabled later
551 Collision_ValidateBrush(brush);
552 for (i = 0;i < brush->numplanes;i++)
555 for (j = 0, p = brush->points;j < brush->numpoints;j++, p++)
556 if (DotProduct(p->v, brush->planes[i].normal) > brush->planes[i].dist + COLLISION_PLANE_DIST_EPSILON)
557 Con_DPrintf("Error in brush plane generation, plane %i\n", i);
562 // NOTE: start and end of each brush pair must have same numplanes/numpoints
563 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)
565 int nplane, nplane2, nedge1, nedge2, hitq3surfaceflags = 0;
566 int tracenumedgedirs = trace_start->numedgedirs;
567 //int othernumedgedirs = other_start->numedgedirs;
568 int tracenumpoints = trace_start->numpoints;
569 int othernumpoints = other_start->numpoints;
570 int numplanes1 = other_start->numplanes;
571 int numplanes2 = numplanes1 + trace_start->numplanes;
572 int numplanes3 = numplanes2 + trace_start->numedgedirs * other_start->numedgedirs * 2;
573 vec_t enterfrac = -1, leavefrac = 1, startdist, enddist, ie, f, imove, enterfrac2 = -1;
576 vec4_t newimpactplane;
577 const texture_t *hittexture = NULL;
578 vec_t startdepth = 1;
579 vec3_t startdepthnormal;
580 const texture_t *starttexture = NULL;
582 VectorClear(startdepthnormal);
583 Vector4Clear(newimpactplane);
585 // fast case for AABB vs compiled brushes (which begin with AABB planes and also have precomputed bevels for AABB collisions)
586 if (trace_start->isaabb && other_start->hasaabbplanes)
587 numplanes3 = numplanes2 = numplanes1;
589 // Separating Axis Theorem:
590 // if a supporting vector (plane normal) can be found that separates two
591 // objects, they are not colliding.
594 // reduce the size of one object to a point while enlarging the other to
595 // represent the space that point can not occupy.
597 // try every plane we can construct between the two brushes and measure
598 // the distance between them.
599 for (nplane = 0;nplane < numplanes3;nplane++)
601 if (nplane < numplanes1)
604 VectorCopy(other_start->planes[nplane2].normal, startplane);
605 VectorCopy(other_end->planes[nplane2].normal, endplane);
607 else if (nplane < numplanes2)
609 nplane2 = nplane - numplanes1;
610 VectorCopy(trace_start->planes[nplane2].normal, startplane);
611 VectorCopy(trace_end->planes[nplane2].normal, endplane);
615 // pick an edgedir from each brush and cross them
616 nplane2 = nplane - numplanes2;
617 nedge1 = nplane2 >> 1;
618 nedge2 = nedge1 / tracenumedgedirs;
619 nedge1 -= nedge2 * tracenumedgedirs;
622 CrossProduct(trace_start->edgedirs[nedge1].v, other_start->edgedirs[nedge2].v, startplane);
623 CrossProduct(trace_end->edgedirs[nedge1].v, other_end->edgedirs[nedge2].v, endplane);
627 CrossProduct(other_start->edgedirs[nedge2].v, trace_start->edgedirs[nedge1].v, startplane);
628 CrossProduct(other_end->edgedirs[nedge2].v, trace_end->edgedirs[nedge1].v, endplane);
630 if (VectorLength2(startplane) < COLLISION_EDGECROSS_MINLENGTH2 || VectorLength2(endplane) < COLLISION_EDGECROSS_MINLENGTH2)
631 continue; // degenerate crossproducts
632 VectorNormalize(startplane);
633 VectorNormalize(endplane);
635 startplane[3] = furthestplanedist_float(startplane, other_start->points, othernumpoints);
636 endplane[3] = furthestplanedist_float(endplane, other_end->points, othernumpoints);
637 startdist = nearestplanedist_float(startplane, trace_start->points, tracenumpoints) - startplane[3];
638 enddist = nearestplanedist_float(endplane, trace_end->points, tracenumpoints) - endplane[3];
639 //Con_Printf("%c%i: startdist = %f, enddist = %f, startdist / (startdist - enddist) = %f\n", nplane2 != nplane ? 'b' : 'a', nplane2, startdist, enddist, startdist / (startdist - enddist));
641 // aside from collisions, this is also used for error correction
642 if (startdist <= 0.0f && nplane < numplanes1 && (startdepth < startdist || startdepth == 1))
644 startdepth = startdist;
645 VectorCopy(startplane, startdepthnormal);
646 starttexture = other_start->planes[nplane2].texture;
649 if (startdist > enddist)
657 imove = 1 / (startdist - enddist);
658 f = startdist * imove;
659 // check if this will reduce the collision time range
662 // reduced collision time range
664 // if the collision time range is now empty, no collision
665 if (enterfrac > leavefrac)
667 // calculate the nudged fraction and impact normal we'll
668 // need if we accept this collision later
669 enterfrac2 = (startdist - collision_impactnudge.value) * imove;
670 // if the collision would be further away than the trace's
671 // existing collision data, we don't care about this
673 if (enterfrac2 >= trace->fraction)
675 ie = 1.0f - enterfrac;
676 newimpactplane[0] = startplane[0] * ie + endplane[0] * enterfrac;
677 newimpactplane[1] = startplane[1] * ie + endplane[1] * enterfrac;
678 newimpactplane[2] = startplane[2] * ie + endplane[2] * enterfrac;
679 newimpactplane[3] = startplane[3] * ie + endplane[3] * enterfrac;
680 if (nplane < numplanes1)
682 // use the plane from other
684 hitq3surfaceflags = other_start->planes[nplane2].q3surfaceflags;
685 hittexture = other_start->planes[nplane2].texture;
687 else if (nplane < numplanes2)
689 // use the plane from trace
690 nplane2 = nplane - numplanes1;
691 hitq3surfaceflags = trace_start->planes[nplane2].q3surfaceflags;
692 hittexture = trace_start->planes[nplane2].texture;
696 hitq3surfaceflags = other_start->q3surfaceflags;
697 hittexture = other_start->texture;
704 // moving out of brush
710 f = startdist / (startdist - enddist);
711 // check if this will reduce the collision time range
714 // reduced collision time range
716 // if the collision time range is now empty, no collision
717 if (enterfrac > leavefrac)
724 // at this point we know the trace overlaps the brush because it was not
725 // rejected at any point in the loop above
727 // see if the trace started outside the brush or not
730 // started outside, and overlaps, therefore there is a collision here
731 // store out the impact information
732 if ((trace->hitsupercontentsmask & other_start->supercontents) && !(trace->skipsupercontentsmask & other_start->supercontents) && !(trace->skipmaterialflagsmask & (hittexture ? hittexture->currentmaterialflags : 0)))
734 trace->hitsupercontents = other_start->supercontents;
735 trace->hitq3surfaceflags = hitq3surfaceflags;
736 trace->hittexture = hittexture;
737 trace->fraction = bound(0, enterfrac2, 1);
738 VectorCopy(newimpactplane, trace->plane.normal);
739 trace->plane.dist = newimpactplane[3];
744 // started inside, update startsolid and friends
745 trace->startsupercontents |= other_start->supercontents;
746 if ((trace->hitsupercontentsmask & other_start->supercontents) && !(trace->skipsupercontentsmask & other_start->supercontents) && !(trace->skipmaterialflagsmask & (starttexture ? starttexture->currentmaterialflags : 0)))
748 trace->startsolid = true;
750 trace->allsolid = true;
751 VectorCopy(newimpactplane, trace->plane.normal);
752 trace->plane.dist = newimpactplane[3];
753 if (trace->startdepth > startdepth)
755 trace->startdepth = startdepth;
756 VectorCopy(startdepthnormal, trace->startdepthnormal);
757 trace->starttexture = starttexture;
763 // NOTE: start and end of each brush pair must have same numplanes/numpoints
764 void Collision_TraceLineBrushFloat(trace_t *trace, const vec3_t linestart, const vec3_t lineend, const colbrushf_t *other_start, const colbrushf_t *other_end)
766 int nplane, hitq3surfaceflags = 0;
767 int numplanes = other_start->numplanes;
768 vec_t enterfrac = -1, leavefrac = 1, startdist, enddist, ie, f, imove, enterfrac2 = -1;
771 vec4_t newimpactplane;
772 const texture_t *hittexture = NULL;
773 vec_t startdepth = 1;
774 vec3_t startdepthnormal;
775 const texture_t *starttexture = NULL;
777 if (collision_debug_tracelineasbox.integer)
779 colboxbrushf_t thisbrush_start, thisbrush_end;
780 Collision_BrushForBox(&thisbrush_start, linestart, linestart, 0, 0, NULL);
781 Collision_BrushForBox(&thisbrush_end, lineend, lineend, 0, 0, NULL);
782 Collision_TraceBrushBrushFloat(trace, &thisbrush_start.brush, &thisbrush_end.brush, other_start, other_end);
786 VectorClear(startdepthnormal);
787 Vector4Clear(newimpactplane);
789 // Separating Axis Theorem:
790 // if a supporting vector (plane normal) can be found that separates two
791 // objects, they are not colliding.
794 // reduce the size of one object to a point while enlarging the other to
795 // represent the space that point can not occupy.
797 // try every plane we can construct between the two brushes and measure
798 // the distance between them.
799 for (nplane = 0;nplane < numplanes;nplane++)
801 VectorCopy(other_start->planes[nplane].normal, startplane);
802 startplane[3] = other_start->planes[nplane].dist;
803 VectorCopy(other_end->planes[nplane].normal, endplane);
804 endplane[3] = other_end->planes[nplane].dist;
805 startdist = DotProduct(linestart, startplane) - startplane[3];
806 enddist = DotProduct(lineend, endplane) - endplane[3];
807 //Con_Printf("%c%i: startdist = %f, enddist = %f, startdist / (startdist - enddist) = %f\n", nplane2 != nplane ? 'b' : 'a', nplane2, startdist, enddist, startdist / (startdist - enddist));
809 // aside from collisions, this is also used for error correction
810 if (startdist <= 0.0f && (startdepth < startdist || startdepth == 1))
812 startdepth = startdist;
813 VectorCopy(startplane, startdepthnormal);
814 starttexture = other_start->planes[nplane].texture;
817 if (startdist > enddist)
825 imove = 1 / (startdist - enddist);
826 f = startdist * imove;
827 // check if this will reduce the collision time range
830 // reduced collision time range
832 // if the collision time range is now empty, no collision
833 if (enterfrac > leavefrac)
835 // calculate the nudged fraction and impact normal we'll
836 // need if we accept this collision later
837 enterfrac2 = (startdist - collision_impactnudge.value) * imove;
838 // if the collision would be further away than the trace's
839 // existing collision data, we don't care about this
841 if (enterfrac2 >= trace->fraction)
843 ie = 1.0f - enterfrac;
844 newimpactplane[0] = startplane[0] * ie + endplane[0] * enterfrac;
845 newimpactplane[1] = startplane[1] * ie + endplane[1] * enterfrac;
846 newimpactplane[2] = startplane[2] * ie + endplane[2] * enterfrac;
847 newimpactplane[3] = startplane[3] * ie + endplane[3] * enterfrac;
848 hitq3surfaceflags = other_start->planes[nplane].q3surfaceflags;
849 hittexture = other_start->planes[nplane].texture;
855 // moving out of brush
861 f = startdist / (startdist - enddist);
862 // check if this will reduce the collision time range
865 // reduced collision time range
867 // if the collision time range is now empty, no collision
868 if (enterfrac > leavefrac)
875 // at this point we know the trace overlaps the brush because it was not
876 // rejected at any point in the loop above
878 // see if the trace started outside the brush or not
881 // started outside, and overlaps, therefore there is a collision here
882 // store out the impact information
883 if ((trace->hitsupercontentsmask & other_start->supercontents) && !(trace->skipsupercontentsmask & other_start->supercontents) && !(trace->skipmaterialflagsmask & (hittexture ? hittexture->currentmaterialflags : 0)))
885 trace->hitsupercontents = other_start->supercontents;
886 trace->hitq3surfaceflags = hitq3surfaceflags;
887 trace->hittexture = hittexture;
888 trace->fraction = bound(0, enterfrac2, 1);
889 VectorCopy(newimpactplane, trace->plane.normal);
890 trace->plane.dist = newimpactplane[3];
895 // started inside, update startsolid and friends
896 trace->startsupercontents |= other_start->supercontents;
897 if ((trace->hitsupercontentsmask & other_start->supercontents) && !(trace->skipsupercontentsmask & other_start->supercontents) && !(trace->skipmaterialflagsmask & (starttexture ? starttexture->currentmaterialflags : 0)))
899 trace->startsolid = true;
901 trace->allsolid = true;
902 VectorCopy(newimpactplane, trace->plane.normal);
903 trace->plane.dist = newimpactplane[3];
904 if (trace->startdepth > startdepth)
906 trace->startdepth = startdepth;
907 VectorCopy(startdepthnormal, trace->startdepthnormal);
908 trace->starttexture = starttexture;
914 qboolean Collision_PointInsideBrushFloat(const vec3_t point, const colbrushf_t *brush)
917 const colplanef_t *plane;
919 if (!BoxesOverlap(point, point, brush->mins, brush->maxs))
921 for (nplane = 0, plane = brush->planes;nplane < brush->numplanes;nplane++, plane++)
922 if (DotProduct(plane->normal, point) > plane->dist)
927 void Collision_TracePointBrushFloat(trace_t *trace, const vec3_t linestart, const colbrushf_t *other_start)
930 int numplanes = other_start->numplanes;
933 vec4_t newimpactplane;
934 vec_t startdepth = 1;
935 vec3_t startdepthnormal;
936 const texture_t *starttexture = NULL;
938 VectorClear(startdepthnormal);
939 Vector4Clear(newimpactplane);
941 // Separating Axis Theorem:
942 // if a supporting vector (plane normal) can be found that separates two
943 // objects, they are not colliding.
946 // reduce the size of one object to a point while enlarging the other to
947 // represent the space that point can not occupy.
949 // try every plane we can construct between the two brushes and measure
950 // the distance between them.
951 for (nplane = 0; nplane < numplanes; nplane++)
953 VectorCopy(other_start->planes[nplane].normal, startplane);
954 startplane[3] = other_start->planes[nplane].dist;
955 startdist = DotProduct(linestart, startplane) - startplane[3];
960 // aside from collisions, this is also used for error correction
961 if (startdepth < startdist || startdepth == 1)
963 startdepth = startdist;
964 VectorCopy(startplane, startdepthnormal);
965 starttexture = other_start->planes[nplane].texture;
969 // at this point we know the trace overlaps the brush because it was not
970 // rejected at any point in the loop above
972 // started inside, update startsolid and friends
973 trace->startsupercontents |= other_start->supercontents;
974 if ((trace->hitsupercontentsmask & other_start->supercontents) && !(trace->skipsupercontentsmask & other_start->supercontents) && !(trace->skipmaterialflagsmask & (starttexture ? starttexture->currentmaterialflags : 0)))
976 trace->startsolid = true;
977 trace->allsolid = true;
978 VectorCopy(newimpactplane, trace->plane.normal);
979 trace->plane.dist = newimpactplane[3];
980 if (trace->startdepth > startdepth)
982 trace->startdepth = startdepth;
983 VectorCopy(startdepthnormal, trace->startdepthnormal);
984 trace->starttexture = starttexture;
989 static void Collision_SnapCopyPoints(int numpoints, const colpointf_t *in, colpointf_t *out, float fractionprecision, float invfractionprecision)
992 for (i = 0;i < numpoints;i++)
994 out[i].v[0] = floor(in[i].v[0] * fractionprecision + 0.5f) * invfractionprecision;
995 out[i].v[1] = floor(in[i].v[1] * fractionprecision + 0.5f) * invfractionprecision;
996 out[i].v[2] = floor(in[i].v[2] * fractionprecision + 0.5f) * invfractionprecision;
1000 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)
1003 colpointf_t points[3];
1004 colpointf_t edgedirs[3];
1005 colplanef_t planes[5];
1007 memset(&brush, 0, sizeof(brush));
1008 brush.isaabb = false;
1009 brush.hasaabbplanes = false;
1010 brush.numpoints = 3;
1011 brush.numedgedirs = 3;
1012 brush.numplanes = 5;
1013 brush.points = points;
1014 brush.edgedirs = edgedirs;
1015 brush.planes = planes;
1016 brush.supercontents = supercontents;
1017 brush.q3surfaceflags = q3surfaceflags;
1018 brush.texture = texture;
1019 for (i = 0;i < brush.numplanes;i++)
1021 brush.planes[i].q3surfaceflags = q3surfaceflags;
1022 brush.planes[i].texture = texture;
1027 cnt = (numtriangles + stride - 1) / stride;
1028 for(i = 0; i < cnt; ++i)
1030 if(BoxesOverlap(bbox6f + i * 6, bbox6f + i * 6 + 3, segmentmins, segmentmaxs))
1032 for(k = 0; k < stride; ++k)
1034 tri = i * stride + k;
1035 if(tri >= numtriangles)
1037 VectorCopy(vertex3f + element3i[tri * 3 + 0] * 3, points[0].v);
1038 VectorCopy(vertex3f + element3i[tri * 3 + 1] * 3, points[1].v);
1039 VectorCopy(vertex3f + element3i[tri * 3 + 2] * 3, points[2].v);
1040 Collision_SnapCopyPoints(brush.numpoints, points, points, COLLISION_SNAPSCALE, COLLISION_SNAP);
1041 Collision_CalcEdgeDirsForPolygonBrushFloat(&brush);
1042 Collision_CalcPlanesForTriangleBrushFloat(&brush);
1043 //Collision_PrintBrushAsQHull(&brush, "brush");
1044 Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, &brush, &brush);
1049 else if(stride == 0)
1051 for (i = 0;i < numtriangles;i++, element3i += 3)
1053 if (TriangleBBoxOverlapsBox(vertex3f + element3i[0]*3, vertex3f + element3i[1]*3, vertex3f + element3i[2]*3, segmentmins, segmentmaxs))
1055 VectorCopy(vertex3f + element3i[0] * 3, points[0].v);
1056 VectorCopy(vertex3f + element3i[1] * 3, points[1].v);
1057 VectorCopy(vertex3f + element3i[2] * 3, points[2].v);
1058 Collision_SnapCopyPoints(brush.numpoints, points, points, COLLISION_SNAPSCALE, COLLISION_SNAP);
1059 Collision_CalcEdgeDirsForPolygonBrushFloat(&brush);
1060 Collision_CalcPlanesForTriangleBrushFloat(&brush);
1061 //Collision_PrintBrushAsQHull(&brush, "brush");
1062 Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, &brush, &brush);
1068 for (i = 0;i < numtriangles;i++, element3i += 3)
1070 VectorCopy(vertex3f + element3i[0] * 3, points[0].v);
1071 VectorCopy(vertex3f + element3i[1] * 3, points[1].v);
1072 VectorCopy(vertex3f + element3i[2] * 3, points[2].v);
1073 Collision_SnapCopyPoints(brush.numpoints, points, points, COLLISION_SNAPSCALE, COLLISION_SNAP);
1074 Collision_CalcEdgeDirsForPolygonBrushFloat(&brush);
1075 Collision_CalcPlanesForTriangleBrushFloat(&brush);
1076 //Collision_PrintBrushAsQHull(&brush, "brush");
1077 Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, &brush, &brush);
1082 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)
1085 // FIXME: snap vertices?
1089 cnt = (numtriangles + stride - 1) / stride;
1090 for(i = 0; i < cnt; ++i)
1092 if(BoxesOverlap(bbox6f + i * 6, bbox6f + i * 6 + 3, segmentmins, segmentmaxs))
1094 for(k = 0; k < stride; ++k)
1096 tri = i * stride + k;
1097 if(tri >= numtriangles)
1099 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);
1106 for (i = 0;i < numtriangles;i++, element3i += 3)
1107 Collision_TraceLineTriangleFloat(trace, linestart, lineend, vertex3f + element3i[0] * 3, vertex3f + element3i[1] * 3, vertex3f + element3i[2] * 3, supercontents, q3surfaceflags, texture);
1111 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)
1114 colpointf_t points[3];
1115 colpointf_t edgedirs[3];
1116 colplanef_t planes[5];
1118 memset(&brush, 0, sizeof(brush));
1119 brush.isaabb = false;
1120 brush.hasaabbplanes = false;
1121 brush.numpoints = 3;
1122 brush.numedgedirs = 3;
1123 brush.numplanes = 5;
1124 brush.points = points;
1125 brush.edgedirs = edgedirs;
1126 brush.planes = planes;
1127 brush.supercontents = supercontents;
1128 brush.q3surfaceflags = q3surfaceflags;
1129 brush.texture = texture;
1130 for (i = 0;i < brush.numplanes;i++)
1132 brush.planes[i].q3surfaceflags = q3surfaceflags;
1133 brush.planes[i].texture = texture;
1135 VectorCopy(v0, points[0].v);
1136 VectorCopy(v1, points[1].v);
1137 VectorCopy(v2, points[2].v);
1138 Collision_SnapCopyPoints(brush.numpoints, points, points, COLLISION_SNAPSCALE, COLLISION_SNAP);
1139 Collision_CalcEdgeDirsForPolygonBrushFloat(&brush);
1140 Collision_CalcPlanesForTriangleBrushFloat(&brush);
1141 //Collision_PrintBrushAsQHull(&brush, "brush");
1142 Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, &brush, &brush);
1145 void Collision_BrushForBox(colboxbrushf_t *boxbrush, const vec3_t mins, const vec3_t maxs, int supercontents, int q3surfaceflags, const texture_t *texture)
1148 memset(boxbrush, 0, sizeof(*boxbrush));
1149 boxbrush->brush.isaabb = true;
1150 boxbrush->brush.hasaabbplanes = true;
1151 boxbrush->brush.points = boxbrush->points;
1152 boxbrush->brush.edgedirs = boxbrush->edgedirs;
1153 boxbrush->brush.planes = boxbrush->planes;
1154 boxbrush->brush.supercontents = supercontents;
1155 boxbrush->brush.q3surfaceflags = q3surfaceflags;
1156 boxbrush->brush.texture = texture;
1157 if (VectorCompare(mins, maxs))
1160 boxbrush->brush.numpoints = 1;
1161 boxbrush->brush.numedgedirs = 0;
1162 boxbrush->brush.numplanes = 0;
1163 VectorCopy(mins, boxbrush->brush.points[0].v);
1167 boxbrush->brush.numpoints = 8;
1168 boxbrush->brush.numedgedirs = 3;
1169 boxbrush->brush.numplanes = 6;
1170 // there are 8 points on a box
1171 // there are 3 edgedirs on a box (both signs are tested in collision)
1172 // there are 6 planes on a box
1173 VectorSet(boxbrush->brush.points[0].v, mins[0], mins[1], mins[2]);
1174 VectorSet(boxbrush->brush.points[1].v, maxs[0], mins[1], mins[2]);
1175 VectorSet(boxbrush->brush.points[2].v, mins[0], maxs[1], mins[2]);
1176 VectorSet(boxbrush->brush.points[3].v, maxs[0], maxs[1], mins[2]);
1177 VectorSet(boxbrush->brush.points[4].v, mins[0], mins[1], maxs[2]);
1178 VectorSet(boxbrush->brush.points[5].v, maxs[0], mins[1], maxs[2]);
1179 VectorSet(boxbrush->brush.points[6].v, mins[0], maxs[1], maxs[2]);
1180 VectorSet(boxbrush->brush.points[7].v, maxs[0], maxs[1], maxs[2]);
1181 VectorSet(boxbrush->brush.edgedirs[0].v, 1, 0, 0);
1182 VectorSet(boxbrush->brush.edgedirs[1].v, 0, 1, 0);
1183 VectorSet(boxbrush->brush.edgedirs[2].v, 0, 0, 1);
1184 VectorSet(boxbrush->brush.planes[0].normal, -1, 0, 0);boxbrush->brush.planes[0].dist = -mins[0];
1185 VectorSet(boxbrush->brush.planes[1].normal, 1, 0, 0);boxbrush->brush.planes[1].dist = maxs[0];
1186 VectorSet(boxbrush->brush.planes[2].normal, 0, -1, 0);boxbrush->brush.planes[2].dist = -mins[1];
1187 VectorSet(boxbrush->brush.planes[3].normal, 0, 1, 0);boxbrush->brush.planes[3].dist = maxs[1];
1188 VectorSet(boxbrush->brush.planes[4].normal, 0, 0, -1);boxbrush->brush.planes[4].dist = -mins[2];
1189 VectorSet(boxbrush->brush.planes[5].normal, 0, 0, 1);boxbrush->brush.planes[5].dist = maxs[2];
1190 for (i = 0;i < 6;i++)
1192 boxbrush->brush.planes[i].q3surfaceflags = q3surfaceflags;
1193 boxbrush->brush.planes[i].texture = texture;
1196 boxbrush->brush.supercontents = supercontents;
1197 boxbrush->brush.q3surfaceflags = q3surfaceflags;
1198 boxbrush->brush.texture = texture;
1199 VectorSet(boxbrush->brush.mins, mins[0] - 1, mins[1] - 1, mins[2] - 1);
1200 VectorSet(boxbrush->brush.maxs, maxs[0] + 1, maxs[1] + 1, maxs[2] + 1);
1201 //Collision_ValidateBrush(&boxbrush->brush);
1204 //pseudocode for detecting line/sphere overlap without calculating an impact point
1205 //linesphereorigin = sphereorigin - linestart;linediff = lineend - linestart;linespherefrac = DotProduct(linesphereorigin, linediff) / DotProduct(linediff, linediff);return VectorLength2(linesphereorigin - bound(0, linespherefrac, 1) * linediff) >= sphereradius*sphereradius;
1207 // LadyHavoc: currently unused, but tested
1208 // note: this can be used for tracing a moving sphere vs a stationary sphere,
1209 // by simply adding the moving sphere's radius to the sphereradius parameter,
1210 // all the results are correct (impactpoint, impactnormal, and fraction)
1211 float Collision_ClipTrace_Line_Sphere(double *linestart, double *lineend, double *sphereorigin, double sphereradius, double *impactpoint, double *impactnormal)
1213 double dir[3], scale, v[3], deviationdist2, impactdist, linelength;
1214 // make sure the impactpoint and impactnormal are valid even if there is
1216 VectorCopy(lineend, impactpoint);
1217 VectorClear(impactnormal);
1218 // calculate line direction
1219 VectorSubtract(lineend, linestart, dir);
1220 // normalize direction
1221 linelength = VectorLength(dir);
1224 scale = 1.0 / linelength;
1225 VectorScale(dir, scale, dir);
1227 // this dotproduct calculates the distance along the line at which the
1228 // sphere origin is (nearest point to the sphere origin on the line)
1229 impactdist = DotProduct(sphereorigin, dir) - DotProduct(linestart, dir);
1230 // calculate point on line at that distance, and subtract the
1231 // sphereorigin from it, so we have a vector to measure for the distance
1232 // of the line from the sphereorigin (deviation, how off-center it is)
1233 VectorMA(linestart, impactdist, dir, v);
1234 VectorSubtract(v, sphereorigin, v);
1235 deviationdist2 = sphereradius * sphereradius - VectorLength2(v);
1236 // if squared offset length is outside the squared sphere radius, miss
1237 if (deviationdist2 < 0)
1238 return 1; // miss (off to the side)
1239 // nudge back to find the correct impact distance
1240 impactdist -= sqrt(deviationdist2);
1241 if (impactdist >= linelength)
1242 return 1; // miss (not close enough)
1244 return 1; // miss (linestart is past or inside sphere)
1245 // calculate new impactpoint
1246 VectorMA(linestart, impactdist, dir, impactpoint);
1247 // calculate impactnormal (surface normal at point of impact)
1248 VectorSubtract(impactpoint, sphereorigin, impactnormal);
1249 // normalize impactnormal
1250 VectorNormalize(impactnormal);
1251 // return fraction of movement distance
1252 return impactdist / linelength;
1255 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)
1257 float d1, d2, d, f, f2, impact[3], edgenormal[3], faceplanenormal[3], faceplanedist, faceplanenormallength2, edge01[3], edge21[3], edge02[3];
1259 // this function executes:
1260 // 32 ops when line starts behind triangle
1261 // 38 ops when line ends infront of triangle
1262 // 43 ops when line fraction is already closer than this triangle
1263 // 72 ops when line is outside edge 01
1264 // 92 ops when line is outside edge 21
1265 // 115 ops when line is outside edge 02
1266 // 123 ops when line impacts triangle and updates trace results
1268 // this code is designed for clockwise triangles, conversion to
1269 // counterclockwise would require swapping some things around...
1270 // it is easier to simply swap the point0 and point2 parameters to this
1271 // function when calling it than it is to rewire the internals.
1273 // calculate the faceplanenormal of the triangle, this represents the front side
1275 VectorSubtract(point0, point1, edge01);
1276 VectorSubtract(point2, point1, edge21);
1277 CrossProduct(edge01, edge21, faceplanenormal);
1278 // there's no point in processing a degenerate triangle (GIGO - Garbage In, Garbage Out)
1280 faceplanenormallength2 = DotProduct(faceplanenormal, faceplanenormal);
1281 if (faceplanenormallength2 < 0.0001f)
1283 // calculate the distance
1285 faceplanedist = DotProduct(point0, faceplanenormal);
1287 // if start point is on the back side there is no collision
1288 // (we don't care about traces going through the triangle the wrong way)
1290 // calculate the start distance
1292 d1 = DotProduct(faceplanenormal, linestart);
1293 if (d1 <= faceplanedist)
1296 // calculate the end distance
1298 d2 = DotProduct(faceplanenormal, lineend);
1299 // if both are in front, there is no collision
1300 if (d2 >= faceplanedist)
1303 // from here on we know d1 is >= 0 and d2 is < 0
1304 // this means the line starts infront and ends behind, passing through it
1306 // calculate the recipricol of the distance delta,
1307 // so we can use it multiple times cheaply (instead of division)
1309 d = 1.0f / (d1 - d2);
1310 // calculate the impact fraction by taking the start distance (> 0)
1311 // and subtracting the face plane distance (this is the distance of the
1312 // triangle along that same normal)
1313 // then multiply by the recipricol distance delta
1315 f = (d1 - faceplanedist) * d;
1316 f2 = f - collision_impactnudge.value * d;
1317 // skip out if this impact is further away than previous ones
1319 if (f2 >= trace->fraction)
1321 // calculate the perfect impact point for classification of insidedness
1323 impact[0] = linestart[0] + f * (lineend[0] - linestart[0]);
1324 impact[1] = linestart[1] + f * (lineend[1] - linestart[1]);
1325 impact[2] = linestart[2] + f * (lineend[2] - linestart[2]);
1327 // calculate the edge normal and reject if impact is outside triangle
1328 // (an edge normal faces away from the triangle, to get the desired normal
1329 // a crossproduct with the faceplanenormal is used, and because of the way
1330 // the insidedness comparison is written it does not need to be normalized)
1332 // first use the two edges from the triangle plane math
1333 // the other edge only gets calculated if the point survives that long
1336 CrossProduct(edge01, faceplanenormal, edgenormal);
1337 if (DotProduct(impact, edgenormal) > DotProduct(point1, edgenormal))
1341 CrossProduct(faceplanenormal, edge21, edgenormal);
1342 if (DotProduct(impact, edgenormal) > DotProduct(point2, edgenormal))
1346 VectorSubtract(point0, point2, edge02);
1347 CrossProduct(faceplanenormal, edge02, edgenormal);
1348 if (DotProduct(impact, edgenormal) > DotProduct(point0, edgenormal))
1353 // skip if this trace should not be blocked by these contents
1354 if (!(supercontents & trace->hitsupercontentsmask) || (supercontents & trace->skipsupercontentsmask) || (texture->currentmaterialflags & trace->skipmaterialflagsmask))
1357 // store the new trace fraction
1358 trace->fraction = f2;
1360 // store the new trace plane (because collisions only happen from
1361 // the front this is always simply the triangle normal, never flipped)
1362 d = 1.0 / sqrt(faceplanenormallength2);
1363 VectorScale(faceplanenormal, d, trace->plane.normal);
1364 trace->plane.dist = faceplanedist * d;
1366 trace->hitsupercontents = supercontents;
1367 trace->hitq3surfaceflags = q3surfaceflags;
1368 trace->hittexture = texture;
1371 void Collision_BoundingBoxOfBrushTraceSegment(const colbrushf_t *start, const colbrushf_t *end, vec3_t mins, vec3_t maxs, float startfrac, float endfrac)
1374 colpointf_t *ps, *pe;
1375 float tempstart[3], tempend[3];
1376 VectorLerp(start->points[0].v, startfrac, end->points[0].v, mins);
1377 VectorCopy(mins, maxs);
1378 for (i = 0, ps = start->points, pe = end->points;i < start->numpoints;i++, ps++, pe++)
1380 VectorLerp(ps->v, startfrac, pe->v, tempstart);
1381 VectorLerp(ps->v, endfrac, pe->v, tempend);
1382 mins[0] = min(mins[0], min(tempstart[0], tempend[0]));
1383 mins[1] = min(mins[1], min(tempstart[1], tempend[1]));
1384 mins[2] = min(mins[2], min(tempstart[2], tempend[2]));
1385 maxs[0] = min(maxs[0], min(tempstart[0], tempend[0]));
1386 maxs[1] = min(maxs[1], min(tempstart[1], tempend[1]));
1387 maxs[2] = min(maxs[2], min(tempstart[2], tempend[2]));
1397 //===========================================
1399 static void Collision_TranslateBrush(const vec3_t shift, colbrushf_t *brush)
1402 // now we can transform the data
1403 for(i = 0; i < brush->numplanes; ++i)
1405 brush->planes[i].dist += DotProduct(shift, brush->planes[i].normal);
1407 for(i = 0; i < brush->numpoints; ++i)
1409 VectorAdd(brush->points[i].v, shift, brush->points[i].v);
1411 VectorAdd(brush->mins, shift, brush->mins);
1412 VectorAdd(brush->maxs, shift, brush->maxs);
1415 static void Collision_TransformBrush(const matrix4x4_t *matrix, colbrushf_t *brush)
1419 // we're breaking any AABB properties here...
1420 brush->isaabb = false;
1421 brush->hasaabbplanes = false;
1422 // now we can transform the data
1423 for(i = 0; i < brush->numplanes; ++i)
1425 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);
1427 for(i = 0; i < brush->numedgedirs; ++i)
1429 Matrix4x4_Transform(matrix, brush->edgedirs[i].v, v);
1430 VectorCopy(v, brush->edgedirs[i].v);
1432 for(i = 0; i < brush->numpoints; ++i)
1434 Matrix4x4_Transform(matrix, brush->points[i].v, v);
1435 VectorCopy(v, brush->points[i].v);
1437 VectorCopy(brush->points[0].v, brush->mins);
1438 VectorCopy(brush->points[0].v, brush->maxs);
1439 for(i = 1; i < brush->numpoints; ++i)
1441 if(brush->points[i].v[0] < brush->mins[0]) brush->mins[0] = brush->points[i].v[0];
1442 if(brush->points[i].v[1] < brush->mins[1]) brush->mins[1] = brush->points[i].v[1];
1443 if(brush->points[i].v[2] < brush->mins[2]) brush->mins[2] = brush->points[i].v[2];
1444 if(brush->points[i].v[0] > brush->maxs[0]) brush->maxs[0] = brush->points[i].v[0];
1445 if(brush->points[i].v[1] > brush->maxs[1]) brush->maxs[1] = brush->points[i].v[1];
1446 if(brush->points[i].v[2] > brush->maxs[2]) brush->maxs[2] = brush->points[i].v[2];
1450 typedef struct collision_cachedtrace_parameters_s
1455 int hitsupercontentsmask;
1456 int skipsupercontentsmask;
1457 int skipmaterialflagsmask;
1460 collision_cachedtrace_parameters_t;
1462 typedef struct collision_cachedtrace_s
1465 collision_cachedtrace_parameters_t p;
1468 collision_cachedtrace_t;
1470 static mempool_t *collision_cachedtrace_mempool;
1471 static collision_cachedtrace_t *collision_cachedtrace_array;
1472 static int collision_cachedtrace_firstfree;
1473 static int collision_cachedtrace_lastused;
1474 static int collision_cachedtrace_max;
1475 static unsigned char collision_cachedtrace_sequence;
1476 static int collision_cachedtrace_hashsize;
1477 static int *collision_cachedtrace_hash;
1478 static unsigned int *collision_cachedtrace_arrayfullhashindex;
1479 static unsigned int *collision_cachedtrace_arrayhashindex;
1480 static unsigned int *collision_cachedtrace_arraynext;
1481 static unsigned char *collision_cachedtrace_arrayused;
1482 static qboolean collision_cachedtrace_rebuildhash;
1484 void Collision_Cache_Reset(qboolean resetlimits)
1486 if (collision_cachedtrace_hash)
1487 Mem_Free(collision_cachedtrace_hash);
1488 if (collision_cachedtrace_array)
1489 Mem_Free(collision_cachedtrace_array);
1490 if (collision_cachedtrace_arrayfullhashindex)
1491 Mem_Free(collision_cachedtrace_arrayfullhashindex);
1492 if (collision_cachedtrace_arrayhashindex)
1493 Mem_Free(collision_cachedtrace_arrayhashindex);
1494 if (collision_cachedtrace_arraynext)
1495 Mem_Free(collision_cachedtrace_arraynext);
1496 if (collision_cachedtrace_arrayused)
1497 Mem_Free(collision_cachedtrace_arrayused);
1498 if (resetlimits || !collision_cachedtrace_max)
1499 collision_cachedtrace_max = collision_cache.integer ? 128 : 1;
1500 collision_cachedtrace_firstfree = 1;
1501 collision_cachedtrace_lastused = 0;
1502 collision_cachedtrace_hashsize = collision_cachedtrace_max;
1503 collision_cachedtrace_array = (collision_cachedtrace_t *)Mem_Alloc(collision_cachedtrace_mempool, collision_cachedtrace_max * sizeof(collision_cachedtrace_t));
1504 collision_cachedtrace_hash = (int *)Mem_Alloc(collision_cachedtrace_mempool, collision_cachedtrace_hashsize * sizeof(int));
1505 collision_cachedtrace_arrayfullhashindex = (unsigned int *)Mem_Alloc(collision_cachedtrace_mempool, collision_cachedtrace_max * sizeof(unsigned int));
1506 collision_cachedtrace_arrayhashindex = (unsigned int *)Mem_Alloc(collision_cachedtrace_mempool, collision_cachedtrace_max * sizeof(unsigned int));
1507 collision_cachedtrace_arraynext = (unsigned int *)Mem_Alloc(collision_cachedtrace_mempool, collision_cachedtrace_max * sizeof(unsigned int));
1508 collision_cachedtrace_arrayused = (unsigned char *)Mem_Alloc(collision_cachedtrace_mempool, collision_cachedtrace_max * sizeof(unsigned char));
1509 collision_cachedtrace_sequence = 1;
1510 collision_cachedtrace_rebuildhash = false;
1513 void Collision_Cache_Init(mempool_t *mempool)
1515 collision_cachedtrace_mempool = mempool;
1516 Collision_Cache_Reset(true);
1519 static void Collision_Cache_RebuildHash(void)
1522 int range = collision_cachedtrace_lastused + 1;
1523 unsigned char sequence = collision_cachedtrace_sequence;
1524 int firstfree = collision_cachedtrace_max;
1526 int *hash = collision_cachedtrace_hash;
1527 unsigned int hashindex;
1528 unsigned int *arrayhashindex = collision_cachedtrace_arrayhashindex;
1529 unsigned int *arraynext = collision_cachedtrace_arraynext;
1530 collision_cachedtrace_rebuildhash = false;
1531 memset(collision_cachedtrace_hash, 0, collision_cachedtrace_hashsize * sizeof(int));
1532 for (index = 1;index < range;index++)
1534 if (collision_cachedtrace_arrayused[index] == sequence)
1536 hashindex = arrayhashindex[index];
1537 arraynext[index] = hash[hashindex];
1538 hash[hashindex] = index;
1543 if (firstfree > index)
1545 collision_cachedtrace_arrayused[index] = 0;
1548 collision_cachedtrace_firstfree = firstfree;
1549 collision_cachedtrace_lastused = lastused;
1552 void Collision_Cache_NewFrame(void)
1554 if (collision_cache.integer)
1556 if (collision_cachedtrace_max < 128)
1557 Collision_Cache_Reset(true);
1561 if (collision_cachedtrace_max > 1)
1562 Collision_Cache_Reset(true);
1564 // rebuild hash if sequence would overflow byte, otherwise increment
1565 if (collision_cachedtrace_sequence == 255)
1567 Collision_Cache_RebuildHash();
1568 collision_cachedtrace_sequence = 1;
1572 collision_cachedtrace_rebuildhash = true;
1573 collision_cachedtrace_sequence++;
1577 static unsigned int Collision_Cache_HashIndexForArray(unsigned int *array, unsigned int size)
1580 unsigned int hashindex = 0;
1581 // this is a super-cheesy checksum, designed only for speed
1582 for (i = 0;i < size;i++)
1583 hashindex += array[i] * (1 + i);
1587 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, int skipmaterialflagsmask)
1590 unsigned int fullhashindex;
1593 unsigned char sequence = collision_cachedtrace_sequence;
1594 int *hash = collision_cachedtrace_hash;
1595 unsigned int *arrayfullhashindex = collision_cachedtrace_arrayfullhashindex;
1596 unsigned int *arraynext = collision_cachedtrace_arraynext;
1597 collision_cachedtrace_t *cached = collision_cachedtrace_array + index;
1598 collision_cachedtrace_parameters_t params;
1599 // all non-cached traces use the same index
1600 if (!collision_cache.integer)
1601 r_refdef.stats[r_stat_photoncache_traced]++;
1604 // cached trace lookup
1605 memset(¶ms, 0, sizeof(params));
1606 params.model = model;
1607 VectorCopy(start, params.start);
1608 VectorCopy(end, params.end);
1609 params.hitsupercontentsmask = hitsupercontentsmask;
1610 params.skipsupercontentsmask = skipsupercontentsmask;
1611 params.skipmaterialflagsmask = skipmaterialflagsmask;
1612 params.matrix = *matrix;
1613 fullhashindex = Collision_Cache_HashIndexForArray((unsigned int *)¶ms, sizeof(params) / sizeof(unsigned int));
1614 hashindex = (int)(fullhashindex % (unsigned int)collision_cachedtrace_hashsize);
1615 for (index = hash[hashindex];index;index = arraynext[index])
1617 if (arrayfullhashindex[index] != fullhashindex)
1619 cached = collision_cachedtrace_array + index;
1620 //if (memcmp(&cached->p, ¶ms, sizeof(params)))
1621 if (cached->p.model != params.model
1622 || cached->p.end[0] != params.end[0]
1623 || cached->p.end[1] != params.end[1]
1624 || cached->p.end[2] != params.end[2]
1625 || cached->p.start[0] != params.start[0]
1626 || cached->p.start[1] != params.start[1]
1627 || cached->p.start[2] != params.start[2]
1628 || cached->p.hitsupercontentsmask != params.hitsupercontentsmask
1629 || cached->p.skipsupercontentsmask != params.skipsupercontentsmask
1630 || cached->p.skipmaterialflagsmask != params.skipmaterialflagsmask
1631 || cached->p.matrix.m[0][0] != params.matrix.m[0][0]
1632 || cached->p.matrix.m[0][1] != params.matrix.m[0][1]
1633 || cached->p.matrix.m[0][2] != params.matrix.m[0][2]
1634 || cached->p.matrix.m[0][3] != params.matrix.m[0][3]
1635 || cached->p.matrix.m[1][0] != params.matrix.m[1][0]
1636 || cached->p.matrix.m[1][1] != params.matrix.m[1][1]
1637 || cached->p.matrix.m[1][2] != params.matrix.m[1][2]
1638 || cached->p.matrix.m[1][3] != params.matrix.m[1][3]
1639 || cached->p.matrix.m[2][0] != params.matrix.m[2][0]
1640 || cached->p.matrix.m[2][1] != params.matrix.m[2][1]
1641 || cached->p.matrix.m[2][2] != params.matrix.m[2][2]
1642 || cached->p.matrix.m[2][3] != params.matrix.m[2][3]
1643 || cached->p.matrix.m[3][0] != params.matrix.m[3][0]
1644 || cached->p.matrix.m[3][1] != params.matrix.m[3][1]
1645 || cached->p.matrix.m[3][2] != params.matrix.m[3][2]
1646 || cached->p.matrix.m[3][3] != params.matrix.m[3][3]
1649 // found a matching trace in the cache
1650 r_refdef.stats[r_stat_photoncache_cached]++;
1651 cached->valid = true;
1652 collision_cachedtrace_arrayused[index] = collision_cachedtrace_sequence;
1655 r_refdef.stats[r_stat_photoncache_traced]++;
1656 // find an unused cache entry
1657 for (index = collision_cachedtrace_firstfree, range = collision_cachedtrace_max;index < range;index++)
1658 if (collision_cachedtrace_arrayused[index] == 0)
1662 // all claimed, but probably some are stale...
1663 for (index = 1, range = collision_cachedtrace_max;index < range;index++)
1664 if (collision_cachedtrace_arrayused[index] != sequence)
1668 // found a stale one, rebuild the hash
1669 Collision_Cache_RebuildHash();
1673 // we need to grow the cache
1674 collision_cachedtrace_max *= 2;
1675 Collision_Cache_Reset(false);
1679 // link the new cache entry into the hash bucket
1680 collision_cachedtrace_firstfree = index + 1;
1681 if (collision_cachedtrace_lastused < index)
1682 collision_cachedtrace_lastused = index;
1683 cached = collision_cachedtrace_array + index;
1684 collision_cachedtrace_arraynext[index] = collision_cachedtrace_hash[hashindex];
1685 collision_cachedtrace_hash[hashindex] = index;
1686 collision_cachedtrace_arrayhashindex[index] = hashindex;
1687 cached->valid = false;
1689 collision_cachedtrace_arrayfullhashindex[index] = fullhashindex;
1690 collision_cachedtrace_arrayused[index] = collision_cachedtrace_sequence;
1695 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, int skipmaterialflagsmask)
1697 collision_cachedtrace_t *cached = Collision_Cache_Lookup(model, matrix, inversematrix, start, end, hitsupercontentsmask, skipsupercontentsmask, skipmaterialflagsmask);
1700 *trace = cached->result;
1704 Collision_ClipLineToGenericEntity(trace, model, NULL, NULL, vec3_origin, vec3_origin, 0, matrix, inversematrix, start, end, hitsupercontentsmask, skipsupercontentsmask, skipmaterialflagsmask, collision_extendmovelength.value, true);
1706 cached->result = *trace;
1709 void Collision_Cache_ClipLineToWorldSurfaces(trace_t *trace, dp_model_t *model, const vec3_t start, const vec3_t end, int hitsupercontentsmask, int skipsupercontentsmask, int skipmaterialflagsmask)
1711 collision_cachedtrace_t *cached = Collision_Cache_Lookup(model, &identitymatrix, &identitymatrix, start, end, hitsupercontentsmask, skipsupercontentsmask, skipmaterialflagsmask);
1714 *trace = cached->result;
1718 Collision_ClipLineToWorld(trace, model, start, end, hitsupercontentsmask, skipsupercontentsmask, skipmaterialflagsmask, collision_extendmovelength.value, true);
1720 cached->result = *trace;
1723 typedef struct extendtraceinfo_s
1729 float extendstart[3];
1731 float extenddelta[3];
1734 float scaletoextend;
1739 static void Collision_ClipExtendPrepare(extendtraceinfo_t *extendtraceinfo, trace_t *trace, const vec3_t tstart, const vec3_t tend, float textend)
1741 memset(trace, 0, sizeof(*trace));
1742 trace->fraction = 1;
1744 extendtraceinfo->trace = trace;
1745 VectorCopy(tstart, extendtraceinfo->realstart);
1746 VectorCopy(tend, extendtraceinfo->realend);
1747 VectorSubtract(extendtraceinfo->realend, extendtraceinfo->realstart, extendtraceinfo->realdelta);
1748 VectorCopy(extendtraceinfo->realstart, extendtraceinfo->extendstart);
1749 VectorCopy(extendtraceinfo->realend, extendtraceinfo->extendend);
1750 VectorCopy(extendtraceinfo->realdelta, extendtraceinfo->extenddelta);
1751 extendtraceinfo->reallength = VectorLength(extendtraceinfo->realdelta);
1752 extendtraceinfo->extendlength = extendtraceinfo->reallength;
1753 extendtraceinfo->scaletoextend = 1.0f;
1754 extendtraceinfo->extend = textend;
1756 // make the trace longer according to the extend parameter
1757 if (extendtraceinfo->reallength && extendtraceinfo->extend)
1759 extendtraceinfo->extendlength = extendtraceinfo->reallength + extendtraceinfo->extend;
1760 extendtraceinfo->scaletoextend = extendtraceinfo->extendlength / extendtraceinfo->reallength;
1761 VectorMA(extendtraceinfo->realstart, extendtraceinfo->scaletoextend, extendtraceinfo->realdelta, extendtraceinfo->extendend);
1762 VectorSubtract(extendtraceinfo->extendend, extendtraceinfo->extendstart, extendtraceinfo->extenddelta);
1766 static void Collision_ClipExtendFinish(extendtraceinfo_t *extendtraceinfo)
1768 trace_t *trace = extendtraceinfo->trace;
1770 if (trace->fraction != 1.0f)
1772 // undo the extended trace length
1773 trace->fraction *= extendtraceinfo->scaletoextend;
1775 // 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
1776 if (trace->fraction > 1.0f)
1778 // note that ent may refer to either startsolid or fraction<1, we can't restore the startsolid ent unfortunately
1780 trace->hitq3surfaceflags = 0;
1781 trace->hitsupercontents = 0;
1782 trace->hittexture = NULL;
1783 VectorClear(trace->plane.normal);
1784 trace->plane.dist = 0.0f;
1789 trace->fraction = bound(0, trace->fraction, 1);
1791 // calculate the end position
1792 VectorMA(extendtraceinfo->realstart, trace->fraction, extendtraceinfo->realdelta, trace->endpos);
1795 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, int skipmaterialflagsmask, float extend)
1797 vec3_t starttransformed, endtransformed;
1798 extendtraceinfo_t extendtraceinfo;
1799 Collision_ClipExtendPrepare(&extendtraceinfo, trace, tstart, tend, extend);
1801 Matrix4x4_Transform(inversematrix, extendtraceinfo.extendstart, starttransformed);
1802 Matrix4x4_Transform(inversematrix, extendtraceinfo.extendend, endtransformed);
1803 #if COLLISIONPARANOID >= 3
1804 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]);
1807 if (model && model->TraceBox)
1809 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]))
1811 // we get here if TraceBrush exists, AND we have a rotation component (SOLID_BSP case)
1812 // using starttransformed, endtransformed is WRONG in this case!
1813 // should rather build a brush and trace using it
1814 colboxbrushf_t thisbrush_start, thisbrush_end;
1815 Collision_BrushForBox(&thisbrush_start, mins, maxs, 0, 0, NULL);
1816 Collision_BrushForBox(&thisbrush_end, mins, maxs, 0, 0, NULL);
1817 Collision_TranslateBrush(extendtraceinfo.extendstart, &thisbrush_start.brush);
1818 Collision_TranslateBrush(extendtraceinfo.extendend, &thisbrush_end.brush);
1819 Collision_TransformBrush(inversematrix, &thisbrush_start.brush);
1820 Collision_TransformBrush(inversematrix, &thisbrush_end.brush);
1821 //Collision_TranslateBrush(starttransformed, &thisbrush_start.brush);
1822 //Collision_TranslateBrush(endtransformed, &thisbrush_end.brush);
1823 model->TraceBrush(model, frameblend, skeleton, trace, &thisbrush_start.brush, &thisbrush_end.brush, hitsupercontentsmask, skipsupercontentsmask, skipmaterialflagsmask);
1825 else // this is only approximate if rotated, quite useless
1826 model->TraceBox(model, frameblend, skeleton, trace, starttransformed, mins, maxs, endtransformed, hitsupercontentsmask, skipsupercontentsmask, skipmaterialflagsmask);
1828 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
1829 Collision_ClipTrace_Box(trace, bodymins, bodymaxs, starttransformed, mins, maxs, endtransformed, hitsupercontentsmask, skipsupercontentsmask, skipmaterialflagsmask, bodysupercontents, 0, NULL);
1831 Collision_ClipExtendFinish(&extendtraceinfo);
1834 // NOTE: this relies on plane.dist being directly after plane.normal
1835 Matrix4x4_TransformPositivePlane(matrix, trace->plane.normal[0], trace->plane.normal[1], trace->plane.normal[2], trace->plane.dist, trace->plane.normal_and_dist);
1838 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, int skipmaterialflagsmask, float extend)
1840 extendtraceinfo_t extendtraceinfo;
1841 Collision_ClipExtendPrepare(&extendtraceinfo, trace, tstart, tend, extend);
1842 // ->TraceBox: TraceBrush not needed here, as worldmodel is never rotated
1843 if (model && model->TraceBox)
1844 model->TraceBox(model, NULL, NULL, trace, extendtraceinfo.extendstart, mins, maxs, extendtraceinfo.extendend, hitsupercontentsmask, skipsupercontentsmask, skipmaterialflagsmask);
1845 Collision_ClipExtendFinish(&extendtraceinfo);
1848 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, int skipmaterialflagsmask, float extend, qboolean hitsurfaces)
1850 vec3_t starttransformed, endtransformed;
1851 extendtraceinfo_t extendtraceinfo;
1852 Collision_ClipExtendPrepare(&extendtraceinfo, trace, tstart, tend, extend);
1854 Matrix4x4_Transform(inversematrix, extendtraceinfo.extendstart, starttransformed);
1855 Matrix4x4_Transform(inversematrix, extendtraceinfo.extendend, endtransformed);
1856 #if COLLISIONPARANOID >= 3
1857 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]);
1860 if (model && model->TraceLineAgainstSurfaces && hitsurfaces)
1861 model->TraceLineAgainstSurfaces(model, frameblend, skeleton, trace, starttransformed, endtransformed, hitsupercontentsmask, skipsupercontentsmask, skipmaterialflagsmask);
1862 else if (model && model->TraceLine)
1863 model->TraceLine(model, frameblend, skeleton, trace, starttransformed, endtransformed, hitsupercontentsmask, skipsupercontentsmask, skipmaterialflagsmask);
1865 Collision_ClipTrace_Box(trace, bodymins, bodymaxs, starttransformed, vec3_origin, vec3_origin, endtransformed, hitsupercontentsmask, skipsupercontentsmask, skipmaterialflagsmask, bodysupercontents, 0, NULL);
1867 Collision_ClipExtendFinish(&extendtraceinfo);
1870 // NOTE: this relies on plane.dist being directly after plane.normal
1871 Matrix4x4_TransformPositivePlane(matrix, trace->plane.normal[0], trace->plane.normal[1], trace->plane.normal[2], trace->plane.dist, trace->plane.normal_and_dist);
1874 void Collision_ClipLineToWorld(trace_t *trace, dp_model_t *model, const vec3_t tstart, const vec3_t tend, int hitsupercontentsmask, int skipsupercontentsmask, int skipmaterialflagsmask, float extend, qboolean hitsurfaces)
1876 extendtraceinfo_t extendtraceinfo;
1877 Collision_ClipExtendPrepare(&extendtraceinfo, trace, tstart, tend, extend);
1879 if (model && model->TraceLineAgainstSurfaces && hitsurfaces)
1880 model->TraceLineAgainstSurfaces(model, NULL, NULL, trace, extendtraceinfo.extendstart, extendtraceinfo.extendend, hitsupercontentsmask, skipsupercontentsmask, skipmaterialflagsmask);
1881 else if (model && model->TraceLine)
1882 model->TraceLine(model, NULL, NULL, trace, extendtraceinfo.extendstart, extendtraceinfo.extendend, hitsupercontentsmask, skipsupercontentsmask, skipmaterialflagsmask);
1884 Collision_ClipExtendFinish(&extendtraceinfo);
1887 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, int skipmaterialflagsmask)
1889 float starttransformed[3];
1890 memset(trace, 0, sizeof(*trace));
1891 trace->fraction = 1;
1893 Matrix4x4_Transform(inversematrix, start, starttransformed);
1894 #if COLLISIONPARANOID >= 3
1895 Con_Printf("trans(%f %f %f -> %f %f %f)", start[0], start[1], start[2], starttransformed[0], starttransformed[1], starttransformed[2]);
1898 if (model && model->TracePoint)
1899 model->TracePoint(model, NULL, NULL, trace, starttransformed, hitsupercontentsmask, skipsupercontentsmask, skipmaterialflagsmask);
1901 Collision_ClipTrace_Point(trace, bodymins, bodymaxs, starttransformed, hitsupercontentsmask, skipsupercontentsmask, skipmaterialflagsmask, bodysupercontents, 0, NULL);
1903 VectorCopy(start, trace->endpos);
1905 // NOTE: this relies on plane.dist being directly after plane.normal
1906 Matrix4x4_TransformPositivePlane(matrix, trace->plane.normal[0], trace->plane.normal[1], trace->plane.normal[2], trace->plane.dist, trace->plane.normal_and_dist);
1909 void Collision_ClipPointToWorld(trace_t *trace, dp_model_t *model, const vec3_t start, int hitsupercontentsmask, int skipsupercontentsmask, int skipmaterialflagsmask)
1911 memset(trace, 0, sizeof(*trace));
1912 trace->fraction = 1;
1913 if (model && model->TracePoint)
1914 model->TracePoint(model, NULL, NULL, trace, start, hitsupercontentsmask, skipsupercontentsmask, skipmaterialflagsmask);
1915 VectorCopy(start, trace->endpos);
1918 void Collision_CombineTraces(trace_t *cliptrace, const trace_t *trace, void *touch, qboolean isbmodel)
1920 // take the 'best' answers from the new trace and combine with existing data
1921 if (trace->allsolid)
1922 cliptrace->allsolid = true;
1923 if (trace->startsolid)
1926 cliptrace->bmodelstartsolid = true;
1927 cliptrace->startsolid = true;
1928 if (cliptrace->fraction == 1)
1929 cliptrace->ent = touch;
1930 if (cliptrace->startdepth > trace->startdepth)
1932 cliptrace->startdepth = trace->startdepth;
1933 VectorCopy(trace->startdepthnormal, cliptrace->startdepthnormal);
1936 // don't set this except on the world, because it can easily confuse
1937 // monsters underwater if there's a bmodel involved in the trace
1938 // (inopen && inwater is how they check water visibility)
1939 //if (trace->inopen)
1940 // cliptrace->inopen = true;
1942 cliptrace->inwater = true;
1943 if ((trace->fraction < cliptrace->fraction) && (VectorLength2(trace->plane.normal) > 0))
1945 cliptrace->fraction = trace->fraction;
1946 VectorCopy(trace->endpos, cliptrace->endpos);
1947 cliptrace->plane = trace->plane;
1948 cliptrace->ent = touch;
1949 cliptrace->hitsupercontents = trace->hitsupercontents;
1950 cliptrace->hitq3surfaceflags = trace->hitq3surfaceflags;
1951 cliptrace->hittexture = trace->hittexture;
1953 cliptrace->startsupercontents |= trace->startsupercontents;