+ int i;
+ memset(boxbrush, 0, sizeof(*boxbrush));
+ boxbrush->brush.isaabb = true;
+ boxbrush->brush.hasaabbplanes = true;
+ boxbrush->brush.points = boxbrush->points;
+ boxbrush->brush.edgedirs = boxbrush->edgedirs;
+ boxbrush->brush.planes = boxbrush->planes;
+ boxbrush->brush.supercontents = supercontents;
+ boxbrush->brush.q3surfaceflags = q3surfaceflags;
+ boxbrush->brush.texture = texture;
+ if (VectorCompare(mins, maxs))
+ {
+ // point brush
+ boxbrush->brush.numpoints = 1;
+ boxbrush->brush.numedgedirs = 0;
+ boxbrush->brush.numplanes = 0;
+ VectorCopy(mins, boxbrush->brush.points[0].v);
+ }
+ else
+ {
+ boxbrush->brush.numpoints = 8;
+ boxbrush->brush.numedgedirs = 3;
+ boxbrush->brush.numplanes = 6;
+ // there are 8 points on a box
+ // there are 3 edgedirs on a box (both signs are tested in collision)
+ // there are 6 planes on a box
+ VectorSet(boxbrush->brush.points[0].v, mins[0], mins[1], mins[2]);
+ VectorSet(boxbrush->brush.points[1].v, maxs[0], mins[1], mins[2]);
+ VectorSet(boxbrush->brush.points[2].v, mins[0], maxs[1], mins[2]);
+ VectorSet(boxbrush->brush.points[3].v, maxs[0], maxs[1], mins[2]);
+ VectorSet(boxbrush->brush.points[4].v, mins[0], mins[1], maxs[2]);
+ VectorSet(boxbrush->brush.points[5].v, maxs[0], mins[1], maxs[2]);
+ VectorSet(boxbrush->brush.points[6].v, mins[0], maxs[1], maxs[2]);
+ VectorSet(boxbrush->brush.points[7].v, maxs[0], maxs[1], maxs[2]);
+ VectorSet(boxbrush->brush.edgedirs[0].v, 1, 0, 0);
+ VectorSet(boxbrush->brush.edgedirs[1].v, 0, 1, 0);
+ VectorSet(boxbrush->brush.edgedirs[2].v, 0, 0, 1);
+ VectorSet(boxbrush->brush.planes[0].normal, -1, 0, 0);boxbrush->brush.planes[0].dist = -mins[0];
+ VectorSet(boxbrush->brush.planes[1].normal, 1, 0, 0);boxbrush->brush.planes[1].dist = maxs[0];
+ VectorSet(boxbrush->brush.planes[2].normal, 0, -1, 0);boxbrush->brush.planes[2].dist = -mins[1];
+ VectorSet(boxbrush->brush.planes[3].normal, 0, 1, 0);boxbrush->brush.planes[3].dist = maxs[1];
+ VectorSet(boxbrush->brush.planes[4].normal, 0, 0, -1);boxbrush->brush.planes[4].dist = -mins[2];
+ VectorSet(boxbrush->brush.planes[5].normal, 0, 0, 1);boxbrush->brush.planes[5].dist = maxs[2];
+ for (i = 0;i < 6;i++)
+ {
+ boxbrush->brush.planes[i].q3surfaceflags = q3surfaceflags;
+ boxbrush->brush.planes[i].texture = texture;
+ }
+ }
+ boxbrush->brush.supercontents = supercontents;
+ boxbrush->brush.q3surfaceflags = q3surfaceflags;
+ boxbrush->brush.texture = texture;
+ VectorSet(boxbrush->brush.mins, mins[0] - 1, mins[1] - 1, mins[2] - 1);
+ VectorSet(boxbrush->brush.maxs, maxs[0] + 1, maxs[1] + 1, maxs[2] + 1);
+ //Collision_ValidateBrush(&boxbrush->brush);
+}
+
+//pseudocode for detecting line/sphere overlap without calculating an impact point
+//linesphereorigin = sphereorigin - linestart;linediff = lineend - linestart;linespherefrac = DotProduct(linesphereorigin, linediff) / DotProduct(linediff, linediff);return VectorLength2(linesphereorigin - bound(0, linespherefrac, 1) * linediff) >= sphereradius*sphereradius;
+
+// LadyHavoc: currently unused, but 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], deviationdist2, impactdist, linelength;
+ // make sure the impactpoint and impactnormal are valid even if there is
+ // no collision
+ VectorCopy(lineend, impactpoint);
+ VectorClear(impactnormal);
+ // calculate line direction
+ VectorSubtract(lineend, linestart, dir);
+ // normalize direction
+ linelength = VectorLength(dir);
+ if (linelength)
+ {
+ scale = 1.0 / linelength;
+ VectorScale(dir, scale, dir);
+ }
+ // this dotproduct calculates the distance along the line at which the
+ // sphere origin is (nearest point to the sphere origin on the line)
+ impactdist = DotProduct(sphereorigin, dir) - DotProduct(linestart, dir);
+ // 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)
+ VectorMA(linestart, impactdist, dir, v);
+ VectorSubtract(v, sphereorigin, v);
+ deviationdist2 = sphereradius * sphereradius - VectorLength2(v);
+ // if squared offset length is outside the squared sphere radius, miss
+ if (deviationdist2 < 0)
+ return 1; // miss (off to the side)
+ // nudge back to find the correct impact distance
+ impactdist -= sqrt(deviationdist2);
+ if (impactdist >= linelength)
+ return 1; // miss (not close enough)
+ if (impactdist < 0)
+ return 1; // miss (linestart is past or inside sphere)
+ // calculate new impactpoint
+ VectorMA(linestart, impactdist, dir, impactpoint);
+ // calculate impactnormal (surface normal at point of impact)
+ VectorSubtract(impactpoint, sphereorigin, impactnormal);
+ // normalize impactnormal
+ VectorNormalize(impactnormal);
+ // return fraction of movement distance
+ return impactdist / linelength;
+}
+
+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)
+{
+ float d1, d2, d, f, f2, 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
+ // 4 ops
+ f = (d1 - faceplanedist) * d;
+ f2 = f - collision_impactnudge.value * d;
+ // skip out if this impact is further away than previous ones
+ // 1 ops
+ if (f2 >= trace->fraction)
+ 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;