+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, texture_t *texture)
+{
+#if 1
+ // more optimized
+ float d1, d2, d, f, impact[3], edgenormal[3], faceplanenormal[3], faceplanedist, faceplanenormallength2, edge01[3], edge21[3], edge02[3];
+
+ // this function executes:
+ // 32 ops when line starts behind triangle
+ // 38 ops when line ends infront of triangle
+ // 43 ops when line fraction is already closer than this triangle
+ // 72 ops when line is outside edge 01
+ // 92 ops when line is outside edge 21
+ // 115 ops when line is outside edge 02
+ // 123 ops when line impacts triangle and updates trace results
+
+ // this code is designed for clockwise triangles, conversion to
+ // counterclockwise would require swapping some things around...
+ // it is easier to simply swap the point0 and point2 parameters to this
+ // function when calling it than it is to rewire the internals.
+
+ // calculate the faceplanenormal of the triangle, this represents the front side
+ // 15 ops
+ VectorSubtract(point0, point1, edge01);
+ VectorSubtract(point2, point1, edge21);
+ CrossProduct(edge01, edge21, faceplanenormal);
+ // there's no point in processing a degenerate triangle (GIGO - Garbage In, Garbage Out)
+ // 6 ops
+ faceplanenormallength2 = DotProduct(faceplanenormal, faceplanenormal);
+ if (faceplanenormallength2 < 0.0001f)
+ return;
+ // calculate the distance
+ // 5 ops
+ faceplanedist = DotProduct(point0, faceplanenormal);
+
+ // if start point is on the back side there is no collision
+ // (we don't care about traces going through the triangle the wrong way)
+
+ // calculate the start distance
+ // 6 ops
+ d1 = DotProduct(faceplanenormal, linestart);
+ if (d1 <= faceplanedist)
+ return;
+
+ // calculate the end distance
+ // 6 ops
+ d2 = DotProduct(faceplanenormal, lineend);
+ // if both are in front, there is no collision
+ if (d2 >= faceplanedist)
+ return;
+
+ // from here on we know d1 is >= 0 and d2 is < 0
+ // this means the line starts infront and ends behind, passing through it
+
+ // calculate the recipricol of the distance delta,
+ // so we can use it multiple times cheaply (instead of division)
+ // 2 ops
+ d = 1.0f / (d1 - d2);
+ // calculate the impact fraction by taking the start distance (> 0)
+ // and subtracting the face plane distance (this is the distance of the
+ // triangle along that same normal)
+ // then multiply by the recipricol distance delta
+ // 2 ops
+ f = (d1 - faceplanedist) * d;
+ // skip out if this impact is further away than previous ones
+ // 1 ops
+ if (f > trace->realfraction)
+ return;
+ // calculate the perfect impact point for classification of insidedness
+ // 9 ops
+ impact[0] = linestart[0] + f * (lineend[0] - linestart[0]);
+ impact[1] = linestart[1] + f * (lineend[1] - linestart[1]);
+ impact[2] = linestart[2] + f * (lineend[2] - linestart[2]);
+
+ // calculate the edge normal and reject if impact is outside triangle
+ // (an edge normal faces away from the triangle, to get the desired normal
+ // a crossproduct with the faceplanenormal is used, and because of the way
+ // the insidedness comparison is written it does not need to be normalized)
+
+ // first use the two edges from the triangle plane math
+ // the other edge only gets calculated if the point survives that long
+
+ // 20 ops
+ CrossProduct(edge01, faceplanenormal, edgenormal);
+ if (DotProduct(impact, edgenormal) > DotProduct(point1, edgenormal))
+ return;
+
+ // 20 ops
+ CrossProduct(faceplanenormal, edge21, edgenormal);
+ if (DotProduct(impact, edgenormal) > DotProduct(point2, edgenormal))
+ return;
+
+ // 23 ops
+ VectorSubtract(point0, point2, edge02);
+ CrossProduct(faceplanenormal, edge02, edgenormal);
+ if (DotProduct(impact, edgenormal) > DotProduct(point0, edgenormal))
+ return;
+
+ // 8 ops (rare)
+
+ // store the new trace fraction
+ trace->realfraction = f;
+
+ // calculate a nudged fraction to keep it out of the surface
+ // (the main fraction remains perfect)
+ trace->fraction = f - collision_impactnudge.value * d;
+
+ if (collision_prefernudgedfraction.integer)
+ trace->realfraction = trace->fraction;
+
+ // store the new trace plane (because collisions only happen from
+ // the front this is always simply the triangle normal, never flipped)
+ d = 1.0 / sqrt(faceplanenormallength2);
+ VectorScale(faceplanenormal, d, trace->plane.normal);
+ trace->plane.dist = faceplanedist * d;
+
+ trace->hitsupercontents = supercontents;
+ trace->hitq3surfaceflags = q3surfaceflags;
+ trace->hittexture = texture;
+#else
+ float d1, d2, d, f, fnudged, impact[3], edgenormal[3], faceplanenormal[3], faceplanedist, edge[3];
+
+ // this code is designed for clockwise triangles, conversion to
+ // counterclockwise would require swapping some things around...
+ // it is easier to simply swap the point0 and point2 parameters to this
+ // function when calling it than it is to rewire the internals.
+
+ // calculate the unnormalized faceplanenormal of the triangle,
+ // this represents the front side
+ TriangleNormal(point0, point1, point2, faceplanenormal);
+ // there's no point in processing a degenerate triangle
+ // (GIGO - Garbage In, Garbage Out)
+ if (DotProduct(faceplanenormal, faceplanenormal) < 0.0001f)
+ return;
+ // calculate the unnormalized distance
+ faceplanedist = DotProduct(point0, faceplanenormal);
+
+ // calculate the unnormalized start distance
+ d1 = DotProduct(faceplanenormal, linestart) - faceplanedist;
+ // if start point is on the back side there is no collision
+ // (we don't care about traces going through the triangle the wrong way)
+ if (d1 <= 0)
+ return;
+
+ // calculate the unnormalized end distance
+ d2 = DotProduct(faceplanenormal, lineend) - faceplanedist;
+ // if both are in front, there is no collision
+ if (d2 >= 0)
+ return;
+
+ // from here on we know d1 is >= 0 and d2 is < 0
+ // this means the line starts infront and ends behind, passing through it
+
+ // calculate the recipricol of the distance delta,
+ // so we can use it multiple times cheaply (instead of division)
+ d = 1.0f / (d1 - d2);
+ // calculate the impact fraction by taking the start distance (> 0)
+ // and subtracting the face plane distance (this is the distance of the
+ // triangle along that same normal)
+ // then multiply by the recipricol distance delta
+ f = d1 * d;
+ // skip out if this impact is further away than previous ones
+ if (f > trace->realfraction)
+ return;
+ // calculate the perfect impact point for classification of insidedness
+ impact[0] = linestart[0] + f * (lineend[0] - linestart[0]);
+ impact[1] = linestart[1] + f * (lineend[1] - linestart[1]);
+ impact[2] = linestart[2] + f * (lineend[2] - linestart[2]);
+
+ // calculate the edge normal and reject if impact is outside triangle
+ // (an edge normal faces away from the triangle, to get the desired normal
+ // a crossproduct with the faceplanenormal is used, and because of the way
+ // the insidedness comparison is written it does not need to be normalized)
+
+ VectorSubtract(point2, point0, edge);
+ CrossProduct(edge, faceplanenormal, edgenormal);
+ if (DotProduct(impact, edgenormal) > DotProduct(point0, edgenormal))
+ return;
+
+ VectorSubtract(point0, point1, edge);
+ CrossProduct(edge, faceplanenormal, edgenormal);
+ if (DotProduct(impact, edgenormal) > DotProduct(point1, edgenormal))
+ return;
+
+ VectorSubtract(point1, point2, edge);
+ CrossProduct(edge, faceplanenormal, edgenormal);
+ if (DotProduct(impact, edgenormal) > DotProduct(point2, edgenormal))
+ return;
+
+ // store the new trace fraction
+ trace->realfraction = bound(0, f, 1);
+
+ // store the new trace plane (because collisions only happen from
+ // the front this is always simply the triangle normal, never flipped)
+ VectorNormalize(faceplanenormal);
+ VectorCopy(faceplanenormal, trace->plane.normal);
+ trace->plane.dist = DotProduct(point0, faceplanenormal);
+
+ // calculate the normalized start and end distances
+ d1 = DotProduct(trace->plane.normal, linestart) - trace->plane.dist;
+ d2 = DotProduct(trace->plane.normal, lineend) - trace->plane.dist;
+
+ // calculate a nudged fraction to keep it out of the surface
+ // (the main fraction remains perfect)
+ fnudged = (d1 - collision_impactnudge.value) / (d1 - d2);
+ trace->fraction = bound(0, fnudged, 1);
+
+ // store the new trace endpos
+ // not needed, it's calculated later when the trace is finished
+ //trace->endpos[0] = linestart[0] + fnudged * (lineend[0] - linestart[0]);
+ //trace->endpos[1] = linestart[1] + fnudged * (lineend[1] - linestart[1]);
+ //trace->endpos[2] = linestart[2] + fnudged * (lineend[2] - linestart[2]);
+ trace->hitsupercontents = supercontents;
+ trace->hitq3surfaceflags = q3surfaceflags;
+ trace->hittexture = texture;
+#endif
+}
+
+typedef struct colbspnode_s
+{
+ mplane_t plane;
+ struct colbspnode_s *children[2];
+ // the node is reallocated or split if max is reached
+ int numcolbrushf;
+ int maxcolbrushf;
+ colbrushf_t **colbrushflist;
+ //int numcolbrushd;
+ //int maxcolbrushd;
+ //colbrushd_t **colbrushdlist;
+}
+colbspnode_t;
+
+typedef struct colbsp_s
+{
+ mempool_t *mempool;
+ colbspnode_t *nodes;
+}
+colbsp_t;
+
+colbsp_t *Collision_CreateCollisionBSP(mempool_t *mempool)
+{
+ colbsp_t *bsp;
+ bsp = (colbsp_t *)Mem_Alloc(mempool, sizeof(colbsp_t));
+ bsp->mempool = mempool;
+ bsp->nodes = (colbspnode_t *)Mem_Alloc(bsp->mempool, sizeof(colbspnode_t));
+ return bsp;
+}
+
+void Collision_FreeCollisionBSPNode(colbspnode_t *node)
+{
+ if (node->children[0])
+ Collision_FreeCollisionBSPNode(node->children[0]);
+ if (node->children[1])
+ Collision_FreeCollisionBSPNode(node->children[1]);
+ while (--node->numcolbrushf)
+ Mem_Free(node->colbrushflist[node->numcolbrushf]);
+ //while (--node->numcolbrushd)
+ // Mem_Free(node->colbrushdlist[node->numcolbrushd]);
+ Mem_Free(node);
+}
+
+void Collision_FreeCollisionBSP(colbsp_t *bsp)
+{
+ Collision_FreeCollisionBSPNode(bsp->nodes);
+ Mem_Free(bsp);
+}
+
+void Collision_BoundingBoxOfBrushTraceSegment(const colbrushf_t *start, const colbrushf_t *end, vec3_t mins, vec3_t maxs, float startfrac, float endfrac)
+{
+ int i;
+ colpointf_t *ps, *pe;
+ float tempstart[3], tempend[3];
+ VectorLerp(start->points[0].v, startfrac, end->points[0].v, mins);
+ VectorCopy(mins, maxs);
+ for (i = 0, ps = start->points, pe = end->points;i < start->numpoints;i++, ps++, pe++)
+ {
+ VectorLerp(ps->v, startfrac, pe->v, tempstart);
+ VectorLerp(ps->v, endfrac, pe->v, tempend);
+ mins[0] = min(mins[0], min(tempstart[0], tempend[0]));
+ mins[1] = min(mins[1], min(tempstart[1], tempend[1]));
+ mins[2] = min(mins[2], min(tempstart[2], tempend[2]));
+ maxs[0] = min(maxs[0], min(tempstart[0], tempend[0]));
+ maxs[1] = min(maxs[1], min(tempstart[1], tempend[1]));
+ maxs[2] = min(maxs[2], min(tempstart[2], tempend[2]));
+ }
+ mins[0] -= 1;
+ mins[1] -= 1;
+ mins[2] -= 1;
+ maxs[0] += 1;
+ maxs[1] += 1;
+ maxs[2] += 1;
+}
+
+//===========================================
+
+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 start, const vec3_t mins, const vec3_t maxs, const vec3_t end, int hitsupercontentsmask)
+{
+ float starttransformed[3], endtransformed[3];
+
+ memset(trace, 0, sizeof(*trace));
+ trace->fraction = trace->realfraction = 1;
+
+ Matrix4x4_Transform(inversematrix, start, starttransformed);
+ Matrix4x4_Transform(inversematrix, end, endtransformed);
+#if COLLISIONPARANOID >= 3
+ Con_Printf("trans(%f %f %f -> %f %f %f, %f %f %f -> %f %f %f)", start[0], start[1], start[2], starttransformed[0], starttransformed[1], starttransformed[2], end[0], end[1], end[2], endtransformed[0], endtransformed[1], endtransformed[2]);
+#endif
+
+ if (model && model->TraceBox)
+ model->TraceBox(model, frameblend, skeleton, trace, starttransformed, mins, maxs, endtransformed, hitsupercontentsmask);
+ else
+ Collision_ClipTrace_Box(trace, bodymins, bodymaxs, starttransformed, mins, maxs, endtransformed, hitsupercontentsmask, bodysupercontents, 0, NULL);
+ trace->fraction = bound(0, trace->fraction, 1);
+ trace->realfraction = bound(0, trace->realfraction, 1);
+
+ VectorLerp(start, trace->fraction, end, trace->endpos);
+ // transform plane
+ // NOTE: this relies on plane.dist being directly after plane.normal
+ Matrix4x4_TransformPositivePlane(matrix, trace->plane.normal[0], trace->plane.normal[1], trace->plane.normal[2], trace->plane.dist, trace->plane.normal);
+}
+
+void Collision_ClipToWorld(trace_t *trace, dp_model_t *model, const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end, int hitsupercontents)
+{
+ memset(trace, 0, sizeof(*trace));
+ trace->fraction = trace->realfraction = 1;
+ if (model && model->TraceBox)
+ model->TraceBox(model, NULL, NULL, trace, start, mins, maxs, end, hitsupercontents);
+ trace->fraction = bound(0, trace->fraction, 1);
+ trace->realfraction = bound(0, trace->realfraction, 1);
+ VectorLerp(start, trace->fraction, end, trace->endpos);
+}
+
+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 start, const vec3_t end, int hitsupercontentsmask)
+{
+ float starttransformed[3], endtransformed[3];
+
+ memset(trace, 0, sizeof(*trace));
+ trace->fraction = trace->realfraction = 1;
+
+ Matrix4x4_Transform(inversematrix, start, starttransformed);
+ Matrix4x4_Transform(inversematrix, end, endtransformed);
+#if COLLISIONPARANOID >= 3
+ Con_Printf("trans(%f %f %f -> %f %f %f, %f %f %f -> %f %f %f)", start[0], start[1], start[2], starttransformed[0], starttransformed[1], starttransformed[2], end[0], end[1], end[2], endtransformed[0], endtransformed[1], endtransformed[2]);
+#endif
+
+ if (model && model->TraceLine)
+ model->TraceLine(model, frameblend, skeleton, trace, starttransformed, endtransformed, hitsupercontentsmask);
+ else
+ Collision_ClipTrace_Box(trace, bodymins, bodymaxs, starttransformed, vec3_origin, vec3_origin, endtransformed, hitsupercontentsmask, bodysupercontents, 0, NULL);
+ trace->fraction = bound(0, trace->fraction, 1);
+ trace->realfraction = bound(0, trace->realfraction, 1);
+
+ VectorLerp(start, trace->fraction, end, trace->endpos);
+ // transform plane
+ // NOTE: this relies on plane.dist being directly after plane.normal
+ Matrix4x4_TransformPositivePlane(matrix, trace->plane.normal[0], trace->plane.normal[1], trace->plane.normal[2], trace->plane.dist, trace->plane.normal);
+}
+
+void Collision_ClipLineToWorld(trace_t *trace, dp_model_t *model, const vec3_t start, const vec3_t end, int hitsupercontents)
+{
+ memset(trace, 0, sizeof(*trace));
+ trace->fraction = trace->realfraction = 1;
+ if (model && model->TraceLine)
+ model->TraceLine(model, NULL, NULL, trace, start, end, hitsupercontents);
+ trace->fraction = bound(0, trace->fraction, 1);
+ trace->realfraction = bound(0, trace->realfraction, 1);
+ VectorLerp(start, trace->fraction, end, trace->endpos);
+}
+
+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)
+{
+ float starttransformed[3];
+
+ memset(trace, 0, sizeof(*trace));
+ trace->fraction = trace->realfraction = 1;
+
+ Matrix4x4_Transform(inversematrix, start, starttransformed);
+#if COLLISIONPARANOID >= 3
+ Con_Printf("trans(%f %f %f -> %f %f %f)", start[0], start[1], start[2], starttransformed[0], starttransformed[1], starttransformed[2]);
+#endif
+
+ if (model && model->TracePoint)
+ model->TracePoint(model, NULL, NULL, trace, starttransformed, hitsupercontentsmask);
+ else
+ Collision_ClipTrace_Point(trace, bodymins, bodymaxs, starttransformed, hitsupercontentsmask, bodysupercontents, 0, NULL);
+
+ VectorCopy(start, trace->endpos);
+ // transform plane
+ // NOTE: this relies on plane.dist being directly after plane.normal
+ Matrix4x4_TransformPositivePlane(matrix, trace->plane.normal[0], trace->plane.normal[1], trace->plane.normal[2], trace->plane.dist, trace->plane.normal);
+}
+
+void Collision_ClipPointToWorld(trace_t *trace, dp_model_t *model, const vec3_t start, int hitsupercontents)
+{
+ memset(trace, 0, sizeof(*trace));
+ trace->fraction = trace->realfraction = 1;
+ if (model && model->TracePoint)
+ model->TracePoint(model, NULL, NULL, trace, start, hitsupercontents);
+ VectorCopy(start, trace->endpos);
+}
+
+void Collision_CombineTraces(trace_t *cliptrace, const trace_t *trace, void *touch, qboolean isbmodel)
+{
+ // take the 'best' answers from the new trace and combine with existing data
+ if (trace->allsolid)
+ cliptrace->allsolid = true;
+ if (trace->startsolid)
+ {
+ if (isbmodel)
+ cliptrace->bmodelstartsolid = true;
+ cliptrace->startsolid = true;
+ if (cliptrace->realfraction == 1)
+ cliptrace->ent = touch;
+ if (cliptrace->startdepth > trace->startdepth)
+ {
+ cliptrace->startdepth = trace->startdepth;
+ VectorCopy(trace->startdepthnormal, cliptrace->startdepthnormal);
+ }
+ }
+ // don't set this except on the world, because it can easily confuse
+ // monsters underwater if there's a bmodel involved in the trace
+ // (inopen && inwater is how they check water visibility)
+ //if (trace->inopen)
+ // cliptrace->inopen = true;
+ if (trace->inwater)
+ cliptrace->inwater = true;
+ if ((trace->realfraction <= cliptrace->realfraction) && (VectorLength2(trace->plane.normal) > 0))
+ {
+ cliptrace->fraction = trace->fraction;
+ cliptrace->realfraction = trace->realfraction;
+ VectorCopy(trace->endpos, cliptrace->endpos);
+ cliptrace->plane = trace->plane;
+ cliptrace->ent = touch;
+ cliptrace->hitsupercontents = trace->hitsupercontents;
+ cliptrace->hitq3surfaceflags = trace->hitq3surfaceflags;
+ cliptrace->hittexture = trace->hittexture;
+ }
+ cliptrace->startsupercontents |= trace->startsupercontents;
+}
+
+void Collision_ShortenTrace(trace_t *trace, float shorten_factor, const vec3_t end)
+{
+ // now undo our moving end 1 qu farther...
+ trace->fraction = bound(trace->fraction, trace->fraction / shorten_factor - 1e-6, 1); // we subtract 1e-6 to guard for roundoff errors
+ trace->realfraction = bound(trace->realfraction, trace->realfraction / shorten_factor - 1e-6, 1); // we subtract 1e-6 to guard for roundoff errors
+ if(trace->fraction >= 1) // trace would NOT hit if not expanded!
+ {
+ trace->fraction = 1;
+ trace->realfraction = 1;
+ VectorCopy(end, trace->endpos);
+ memset(&trace->plane, 0, sizeof(trace->plane));
+ trace->ent = NULL;
+ trace->hitsupercontentsmask = 0;
+ trace->hitsupercontents = 0;
+ trace->hitq3surfaceflags = 0;
+ trace->hittexture = NULL;
+ }
+}