+ else
+ {
+ // recurse down node sides
+ int i, bits;
+ float dist1, dist2;
+ colpointf_t *ps, *pe;
+ bits = 0;
+ // FIXME? if TraceBrushPolygonTransform were to be made usable, the
+ // node planes would need to be transformed too
+ dist1 = node->plane->dist - (1.0f / 8.0f);
+ dist2 = node->plane->dist + (1.0f / 8.0f);
+ for (i = 0, ps = info->thisbrush_start->points, pe = info->thisbrush_end->points;i < info->thisbrush_start->numpoints;i++, ps++, pe++)
+ {
+ if (!(bits & 1) && (DotProduct(ps->v, node->plane->normal) > dist1 || DotProduct(pe->v, node->plane->normal) > dist1))
+ bits |= 1;
+ if (!(bits & 2) && (DotProduct(ps->v, node->plane->normal) < dist2 || DotProduct(pe->v, node->plane->normal) < dist2))
+ bits |= 2;
+ }
+ if (bits & 1)
+ Collision_RecursiveTraceBrushNode(info, node->children[0]);
+ if (bits & 2)
+ Collision_RecursiveTraceBrushNode(info, node->children[1]);
+ }
+}
+
+float Collision_TraceBrushBModel(const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, model_t *model, float *impactnormal, int *startsolid, int *allsolid)
+{
+ colbrushbmodelinfo_t info;
+ colframecount++;
+ info.model = model;
+ info.thisbrush_start = thisbrush_start;
+ info.thisbrush_end = thisbrush_end;
+ info.fraction = 1;
+ info.startsolid = false;
+ info.allsolid = false;
+ Collision_RecursiveTraceBrushNode(&info, model->brushq1.nodes + model->brushq1.hulls[0].firstclipnode);
+ if (info.fraction < 1)
+ VectorCopy(info.impactnormal, impactnormal);
+ if (startsolid)
+ *startsolid = info.startsolid;
+ if (allsolid)
+ *allsolid = info.allsolid;
+ return info.fraction;
+}
+
+float Collision_TraceBrushBModelTransform(const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, model_t *model, float *impactnormal, const matrix4x4_t *modelmatrixstart, const matrix4x4_t *modelmatrixend, int *startsolid, int *allsolid)
+{
+ colbrushbmodelinfo_t info;
+ colframecount++;
+ info.model = model;
+ info.modelmatrixstart = modelmatrixstart;
+ info.modelmatrixend = modelmatrixend;
+ info.thisbrush_start = thisbrush_start;
+ info.thisbrush_end = thisbrush_end;
+ info.fraction = 1;
+ info.startsolid = false;
+ info.allsolid = false;
+ Collision_RecursiveTraceBrushNode(&info, model->brushq1.nodes);
+ if (info.fraction < 1)
+ VectorCopy(info.impactnormal, impactnormal);
+ if (startsolid)
+ *startsolid = info.startsolid;
+ if (allsolid)
+ *allsolid = info.allsolid;
+ return info.fraction;
+}
+
+
+
+#define MAX_BRUSHFORBOX 16
+static int brushforbox_index = 0;
+static colpointf_t brushforbox_point[MAX_BRUSHFORBOX*8];
+static colplanef_t brushforbox_plane[MAX_BRUSHFORBOX*6];
+static colbrushf_t brushforbox_brush[MAX_BRUSHFORBOX];
+
+void Collision_InitBrushForBox(void)
+{
+ int i;
+ for (i = 0;i < MAX_BRUSHFORBOX;i++)
+ {
+ brushforbox_brush[i].numpoints = 8;
+ brushforbox_brush[i].numplanes = 6;
+ brushforbox_brush[i].points = brushforbox_point + i * 8;
+ brushforbox_brush[i].planes = brushforbox_plane + i * 6;
+ }
+}
+
+colbrushf_t *Collision_BrushForBox(const matrix4x4_t *matrix, const vec3_t mins, const vec3_t maxs)
+{
+ int i;
+ vec3_t v;
+ colbrushf_t *brush;
+ if (brushforbox_brush[0].numpoints == 0)
+ Collision_InitBrushForBox();
+ brush = brushforbox_brush + ((brushforbox_index++) % MAX_BRUSHFORBOX);
+ // FIXME: optimize
+ for (i = 0;i < 8;i++)
+ {
+ v[0] = i & 1 ? maxs[0] : mins[0];
+ v[1] = i & 2 ? maxs[1] : mins[1];
+ v[2] = i & 4 ? maxs[2] : mins[2];
+ Matrix4x4_Transform(matrix, v, brush->points[i].v);
+ }
+ // FIXME: optimize!
+ for (i = 0;i < 6;i++)
+ {
+ VectorClear(v);
+ v[i >> 1] = i & 1 ? 1 : -1;
+ Matrix4x4_Transform3x3(matrix, v, brush->planes[i].normal);
+ VectorNormalize(brush->planes[i].normal);
+ brush->planes[i].dist = furthestplanedist_float(brush->planes[i].normal, brush->points, brush->numpoints);
+ }
+ return brush;
+}
+
+void Collision_PolygonClipTrace (trace_t *trace, const void *cent, model_t *cmodel, const vec3_t corigin, const vec3_t cangles, const vec3_t cmins, const vec3_t cmaxs, const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end)
+{
+ vec3_t impactnormal;
+ //vec3_t mins2, maxs2;
+ matrix4x4_t cmatrix, cimatrix, startmatrix, endmatrix;
+ matrix4x4_t mstartmatrix, mendmatrix, identitymatrix;
+ colbrushf_t *thisbrush_start, *thisbrush_end, *cbrush;
+
+ Matrix4x4_CreateFromQuakeEntity(&cmatrix, corigin[0], corigin[1], corigin[2], cangles[0], cangles[1], cangles[2], 1);
+ Matrix4x4_Invert_Simple(&cimatrix, &cmatrix);
+ Matrix4x4_CreateTranslate(&startmatrix, start[0], start[1], start[2]);
+ Matrix4x4_CreateTranslate(&endmatrix, end[0], end[1], end[2]);
+
+ Matrix4x4_CreateIdentity(&identitymatrix);
+ Matrix4x4_Concat(&mstartmatrix, &cimatrix, &startmatrix);
+ Matrix4x4_Concat(&mendmatrix, &cimatrix, &endmatrix);
+ thisbrush_start = Collision_BrushForBox(&mstartmatrix, mins, maxs);
+ //mins2[0] = mins[0] - 0.0625;mins2[1] = mins[1] - 0.0625;mins2[2] = mins[2] - 0.0625;
+ //maxs2[0] = maxs[0] + 0.0625;maxs2[1] = maxs[1] + 0.0625;maxs2[2] = maxs[2] + 0.0625;
+ thisbrush_end = Collision_BrushForBox(&mendmatrix, mins, maxs);
+
+ //Collision_PrintBrushAsQHull(thisbrush_start, "thisbrush_start");
+ //Collision_PrintBrushAsQHull(thisbrush_end, "thisbrush_end");
+ memset (trace, 0, sizeof(trace_t));
+ if (cmodel && cmodel->type == mod_brush)
+ {
+ // brush model
+ trace->fraction = Collision_TraceBrushBModel(thisbrush_start, thisbrush_end, cmodel, impactnormal, &trace->startsolid, &trace->allsolid);
+ //trace->fraction = Collision_TraceBrushBModelTransform(thisbrush_start, thisbrush_end, cmodel, trace->plane.normal, &cmatrix, &cmatrix, &trace->startsolid, &trace->allsolid);
+ }
+ else
+ {
+ // bounding box
+ cbrush = Collision_BrushForBox(&identitymatrix, cmins, cmaxs);
+ trace->fraction = Collision_TraceBrushBrushFloat(thisbrush_start, thisbrush_end, cbrush, cbrush, impactnormal, &trace->startsolid, &trace->allsolid);
+ //cbrush = Collision_BrushForBox(&cmatrix, cmins, cmaxs);
+ //trace->fraction = Collision_TraceBrushBrushFloat(thisbrush_start, thisbrush_end, cbrush, cbrush, trace->plane.normal, &trace->startsolid, &trace->allsolid);
+ }
+
+ if (trace->fraction < 0 || trace->fraction > 1)
+ Con_Printf("fraction out of bounds %f %s:%d\n", trace->fraction, __FILE__, __LINE__);
+
+ if (trace->fraction < 1)
+ {
+ trace->ent = (void *) cent;
+ VectorBlend(start, end, trace->fraction, trace->endpos);
+ Matrix4x4_Transform(&cmatrix, impactnormal, trace->plane.normal);
+ VectorNormalize(trace->plane.normal);
+ //Con_Printf("fraction %f normal %f %f %f\n", trace->fraction, trace->plane.normal[0], trace->plane.normal[1], trace->plane.normal[2]);
+ }
+ else
+ VectorCopy(end, trace->endpos);
+}
+
+
+// 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;