+ }
+ Collision_ValidateBrush(brush);
+ return brush;
+}
+
+void Collision_ClipTrace_BrushBox(trace_t *trace, const vec3_t cmins, const vec3_t cmaxs, const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end, int hitsupercontentsmask)
+{
+ colbrushf_t *boxbrush, *thisbrush_start, *thisbrush_end;
+ matrix4x4_t identitymatrix;
+ vec3_t startmins, startmaxs, endmins, endmaxs;
+
+ // create brushes for the collision
+ VectorAdd(start, mins, startmins);
+ VectorAdd(start, maxs, startmaxs);
+ VectorAdd(end, mins, endmins);
+ VectorAdd(end, maxs, endmaxs);
+ Matrix4x4_CreateIdentity(&identitymatrix);
+ boxbrush = Collision_BrushForBox(&identitymatrix, cmins, cmaxs);
+ thisbrush_start = Collision_BrushForBox(&identitymatrix, startmins, startmaxs);
+ thisbrush_end = Collision_BrushForBox(&identitymatrix, endmins, endmaxs);
+
+ memset(trace, 0, sizeof(trace_t));
+ trace->hitsupercontentsmask = hitsupercontentsmask;
+ trace->fraction = 1;
+ trace->allsolid = true;
+ Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, boxbrush, boxbrush);
+}
+
+// LordHavoc: currently unused and not yet tested
+// note: this can be used for tracing a moving sphere vs a stationary sphere,
+// by simply adding the moving sphere's radius to the sphereradius parameter,
+// all the results are correct (impactpoint, impactnormal, and fraction)
+float Collision_ClipTrace_Line_Sphere(double *linestart, double *lineend, double *sphereorigin, double sphereradius, double *impactpoint, double *impactnormal)
+{
+ double dir[3], scale, v[3], deviationdist, impactdist, linelength;
+ // make sure the impactpoint and impactnormal are valid even if there is
+ // no collision
+ impactpoint[0] = lineend[0];
+ impactpoint[1] = lineend[1];
+ impactpoint[2] = lineend[2];
+ impactnormal[0] = 0;
+ impactnormal[1] = 0;
+ impactnormal[2] = 0;
+ // calculate line direction
+ dir[0] = lineend[0] - linestart[0];
+ dir[1] = lineend[1] - linestart[1];
+ dir[2] = lineend[2] - linestart[2];
+ // normalize direction
+ linelength = sqrt(dir[0] * dir[0] + dir[1] * dir[1] + dir[2] * dir[2]);
+ if (linelength)
+ {
+ scale = 1.0 / linelength;
+ dir[0] *= scale;
+ dir[1] *= scale;
+ dir[2] *= scale;
+ }
+ // this dotproduct calculates the distance along the line at which the
+ // sphere origin is (nearest point to the sphere origin on the line)
+ impactdist = dir[0] * (sphereorigin[0] - linestart[0]) + dir[1] * (sphereorigin[1] - linestart[1]) + dir[2] * (sphereorigin[2] - linestart[2]);
+ // calculate point on line at that distance, and subtract the
+ // sphereorigin from it, so we have a vector to measure for the distance
+ // of the line from the sphereorigin (deviation, how off-center it is)
+ v[0] = linestart[0] + impactdist * dir[0] - sphereorigin[0];
+ v[1] = linestart[1] + impactdist * dir[1] - sphereorigin[1];
+ v[2] = linestart[2] + impactdist * dir[2] - sphereorigin[2];
+ deviationdist = v[0] * v[0] + v[1] * v[1] + v[2] * v[2];
+ // if outside the radius, it's a miss for sure
+ // (we do this comparison using squared radius to avoid a sqrt)
+ if (deviationdist > sphereradius*sphereradius)
+ return 1; // miss (off to the side)
+ // nudge back to find the correct impact distance
+ impactdist += (sqrt(deviationdist) - sphereradius);
+ if (impactdist >= linelength)
+ return 1; // miss (not close enough)
+ if (impactdist < 0)
+ return 1; // miss (linestart is past or inside sphere)
+ // calculate new impactpoint
+ impactpoint[0] = linestart[0] + impactdist * dir[0];
+ impactpoint[1] = linestart[1] + impactdist * dir[1];
+ impactpoint[2] = linestart[2] + impactdist * dir[2];
+ // calculate impactnormal (surface normal at point of impact)
+ impactnormal[0] = impactpoint[0] - sphereorigin[0];
+ impactnormal[1] = impactpoint[1] - sphereorigin[1];
+ impactnormal[2] = impactpoint[2] - sphereorigin[2];
+ // normalize impactnormal
+ scale = impactnormal[0] * impactnormal[0] + impactnormal[1] * impactnormal[1] + impactnormal[2] * impactnormal[2];
+ if (scale)
+ {
+ scale = 1.0 / sqrt(scale);
+ impactnormal[0] *= scale;
+ impactnormal[1] *= scale;
+ impactnormal[2] *= scale;
+ }
+ // return fraction of movement distance
+ return impactdist / linelength;
+}
+
+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 = Mem_Alloc(mempool, sizeof(colbsp_t));
+ bsp->mempool = mempool;
+ bsp->nodes = 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]));