+ if (segmentmaxs[axis] >= node->frontmin)
+ Mod_CollisionBIH_TraceLine_RecursiveBIHNode(trace, model, bih, node->front, start, end, linestart, lineend);
+ nodenum = node->back;
+ }
+ else if (segmentmaxs[axis] >= node->frontmin)
+ nodenum = node->front;
+ else
+ return; // trace falls between children
+#else
+ frontdist1 = start[axis] - node->frontmin;
+ frontdist2 = end[axis] - node->frontmin;
+ backdist1 = start[axis] - node->backmax;
+ backdist2 = end[axis] - node->backmax;
+ sideflags = 0;
+ if (frontdist1 < 0)
+ sideflags |= 1;
+ if (frontdist2 < 0)
+ sideflags |= 2;
+ if (backdist1 < 0)
+ sideflags |= 4;
+ if (backdist2 < 0)
+ sideflags |= 8;
+#if 0
+ if (sideflags & 12)
+ {
+ if ((sideflags & 3) != 3)
+ Mod_CollisionBIH_TraceLine_RecursiveBIHNode(trace, model, bih, node->front, start, end, linestart, lineend);
+ nodenum = node->back;
+ }
+ else if ((sideflags & 3) != 3)
+ nodenum = node->front;
+ else
+ return; // trace falls between children
+#else
+ switch(sideflags)
+ {
+ case 0:
+ // start end START END
+ nodenum = node->front;
+ continue;
+ case 1:
+ // START end START END
+#ifdef BIHLINECLIP
+ frontfrac = frontdist1 / (frontdist1 - frontdist2);
+ VectorLerp(start, frontfrac, end, newstart); start = newstart;
+ segmentmins[0] = min(start[0], end[0]);
+ segmentmins[1] = min(start[1], end[1]);
+ segmentmins[2] = min(start[2], end[2]);
+ segmentmaxs[0] = max(start[0], end[0]);
+ segmentmaxs[1] = max(start[1], end[1]);
+ segmentmaxs[2] = max(start[2], end[2]);
+#endif
+ nodenum = node->front;
+ break;
+ case 2:
+#ifdef BIHLINECLIP
+ // start END START END
+ frontfrac = frontdist1 / (frontdist1 - frontdist2);
+ VectorLerp(start, frontfrac, end, newend); end = newend;
+ segmentmins[0] = min(start[0], end[0]);
+ segmentmins[1] = min(start[1], end[1]);
+ segmentmins[2] = min(start[2], end[2]);
+ segmentmaxs[0] = max(start[0], end[0]);
+ segmentmaxs[1] = max(start[1], end[1]);
+ segmentmaxs[2] = max(start[2], end[2]);
+#endif
+ nodenum = node->front;
+ break;
+ case 3:
+ // START END START END
+ return; // line falls in gap between children
+ case 4:
+ // start end start END
+ Mod_CollisionBIH_TraceLine_RecursiveBIHNode(trace, model, bih, node->front, start, end, linestart, lineend);
+#ifdef BIHLINECLIP
+ backfrac = backdist1 / (backdist1 - backdist2);
+ VectorLerp(start, backfrac, end, newend); end = newend;
+ segmentmins[0] = min(start[0], end[0]);
+ segmentmins[1] = min(start[1], end[1]);
+ segmentmins[2] = min(start[2], end[2]);
+ segmentmaxs[0] = max(start[0], end[0]);
+ segmentmaxs[1] = max(start[1], end[1]);
+ segmentmaxs[2] = max(start[2], end[2]);
+#endif
+ nodenum = node->back;
+ break;
+ case 5:
+ // START end start END
+#ifdef BIHLINECLIP
+ frontfrac = frontdist1 / (frontdist1 - frontdist2);
+ VectorLerp(start, frontfrac, end, clipped);
+ Mod_CollisionBIH_TraceLine_RecursiveBIHNode(trace, model, bih, node->front, clipped, end, linestart, lineend);
+ backfrac = backdist1 / (backdist1 - backdist2);
+ VectorLerp(start, backfrac, end, newend); end = newend;
+ segmentmins[0] = min(start[0], end[0]);
+ segmentmins[1] = min(start[1], end[1]);
+ segmentmins[2] = min(start[2], end[2]);
+ segmentmaxs[0] = max(start[0], end[0]);
+ segmentmaxs[1] = max(start[1], end[1]);
+ segmentmaxs[2] = max(start[2], end[2]);
+#else
+ Mod_CollisionBIH_TraceLine_RecursiveBIHNode(trace, model, bih, node->front, start, end, linestart, lineend);
+#endif
+ nodenum = node->back;
+ break;
+ case 6:
+ // start END start END
+#ifdef BIHLINECLIP
+ frontfrac = frontdist1 / (frontdist1 - frontdist2);
+ VectorLerp(start, frontfrac, end, clipped);
+ Mod_CollisionBIH_TraceLine_RecursiveBIHNode(trace, model, bih, node->front, start, clipped, linestart, lineend);
+ backfrac = backdist1 / (backdist1 - backdist2);
+ VectorLerp(start, backfrac, end, newend); end = newend;
+ segmentmins[0] = min(start[0], end[0]);
+ segmentmins[1] = min(start[1], end[1]);
+ segmentmins[2] = min(start[2], end[2]);
+ segmentmaxs[0] = max(start[0], end[0]);
+ segmentmaxs[1] = max(start[1], end[1]);
+ segmentmaxs[2] = max(start[2], end[2]);
+#else
+ Mod_CollisionBIH_TraceLine_RecursiveBIHNode(trace, model, bih, node->front, start, end, linestart, lineend);
+#endif
+ nodenum = node->back;
+ break;
+ case 7:
+ // START END start END
+#ifdef BIHLINECLIP
+ backfrac = backdist1 / (backdist1 - backdist2);
+ VectorLerp(start, backfrac, end, newend); end = newend;
+ segmentmins[0] = min(start[0], end[0]);
+ segmentmins[1] = min(start[1], end[1]);
+ segmentmins[2] = min(start[2], end[2]);
+ segmentmaxs[0] = max(start[0], end[0]);
+ segmentmaxs[1] = max(start[1], end[1]);
+ segmentmaxs[2] = max(start[2], end[2]);
+#endif
+ nodenum = node->back;
+ break;
+ case 8:
+ // start end START end
+ Mod_CollisionBIH_TraceLine_RecursiveBIHNode(trace, model, bih, node->front, start, end, linestart, lineend);
+#ifdef BIHLINECLIP
+ backfrac = backdist1 / (backdist1 - backdist2);
+ VectorLerp(start, backfrac, end, newstart); start = newstart;
+ segmentmins[0] = min(start[0], end[0]);
+ segmentmins[1] = min(start[1], end[1]);
+ segmentmins[2] = min(start[2], end[2]);
+ segmentmaxs[0] = max(start[0], end[0]);
+ segmentmaxs[1] = max(start[1], end[1]);
+ segmentmaxs[2] = max(start[2], end[2]);
+#endif
+ nodenum = node->back;
+ break;
+ case 9:
+ // START end START end
+#ifdef BIHLINECLIP
+ frontfrac = frontdist1 / (frontdist1 - frontdist2);
+ VectorLerp(start, frontfrac, end, clipped);
+ Mod_CollisionBIH_TraceLine_RecursiveBIHNode(trace, model, bih, node->front, clipped, end, linestart, lineend);
+ backfrac = backdist1 / (backdist1 - backdist2);
+ VectorLerp(start, backfrac, end, newstart); start = newstart;
+ segmentmins[0] = min(start[0], end[0]);
+ segmentmins[1] = min(start[1], end[1]);
+ segmentmins[2] = min(start[2], end[2]);
+ segmentmaxs[0] = max(start[0], end[0]);
+ segmentmaxs[1] = max(start[1], end[1]);
+ segmentmaxs[2] = max(start[2], end[2]);
+#else
+ Mod_CollisionBIH_TraceLine_RecursiveBIHNode(trace, model, bih, node->front, start, end, linestart, lineend);
+#endif
+ nodenum = node->back;
+ break;
+ case 10:
+ // start END START end
+#ifdef BIHLINECLIP
+ frontfrac = frontdist1 / (frontdist1 - frontdist2);
+ VectorLerp(start, frontfrac, end, clipped);
+ Mod_CollisionBIH_TraceLine_RecursiveBIHNode(trace, model, bih, node->front, start, clipped, linestart, lineend);
+ backfrac = backdist1 / (backdist1 - backdist2);
+ VectorLerp(start, backfrac, end, newstart); start = newstart;
+ segmentmins[0] = min(start[0], end[0]);
+ segmentmins[1] = min(start[1], end[1]);
+ segmentmins[2] = min(start[2], end[2]);
+ segmentmaxs[0] = max(start[0], end[0]);
+ segmentmaxs[1] = max(start[1], end[1]);
+ segmentmaxs[2] = max(start[2], end[2]);
+#else
+ Mod_CollisionBIH_TraceLine_RecursiveBIHNode(trace, model, bih, node->front, start, end, linestart, lineend);
+#endif
+ nodenum = node->back;
+ break;
+ case 11:
+ // START END START end
+#ifdef BIHLINECLIP
+ backfrac = backdist1 / (backdist1 - backdist2);
+ VectorLerp(start, backfrac, end, newstart); start = newstart;
+ segmentmins[0] = min(start[0], end[0]);
+ segmentmins[1] = min(start[1], end[1]);
+ segmentmins[2] = min(start[2], end[2]);
+ segmentmaxs[0] = max(start[0], end[0]);
+ segmentmaxs[1] = max(start[1], end[1]);
+ segmentmaxs[2] = max(start[2], end[2]);
+#endif
+ nodenum = node->back;
+ break;
+ case 12:
+ // start end start end
+ Mod_CollisionBIH_TraceLine_RecursiveBIHNode(trace, model, bih, node->front, start, end, linestart, lineend);
+ nodenum = node->back;
+ break;
+ case 13:
+ // START end start end
+#ifdef BIHLINECLIP
+ frontfrac = frontdist1 / (frontdist1 - frontdist2);
+ VectorLerp(start, frontfrac, end, clipped);
+ Mod_CollisionBIH_TraceLine_RecursiveBIHNode(trace, model, bih, node->front, clipped, end, linestart, lineend);
+#else
+ Mod_CollisionBIH_TraceLine_RecursiveBIHNode(trace, model, bih, node->front, start, end, linestart, lineend);
+#endif
+ nodenum = node->back;
+ break;
+ case 14:
+ // start END start end
+#ifdef BIHLINECLIP
+ frontfrac = frontdist1 / (frontdist1 - frontdist2);
+ VectorLerp(start, frontfrac, end, clipped);
+ Mod_CollisionBIH_TraceLine_RecursiveBIHNode(trace, model, bih, node->front, start, clipped, linestart, lineend);
+#else
+ Mod_CollisionBIH_TraceLine_RecursiveBIHNode(trace, model, bih, node->front, start, end, linestart, lineend);
+#endif
+ nodenum = node->back;
+ break;
+ case 15:
+ // START END start end
+ nodenum = node->back;
+ continue;
+ }
+#endif
+#endif
+ }
+}
+
+static void Mod_CollisionBIH_TraceBrush_RecursiveBIHNode(trace_t *trace, dp_model_t *model, int nodenum, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, const vec3_t segmentmins, const vec3_t segmentmaxs)
+{
+ const bih_leaf_t *leaf;
+ const bih_node_t *node;
+ const colbrushf_t *brush;
+ const int *e;
+ const texture_t *texture;
+ int axis;
+ for(;;)
+ {
+ node = model->collision_bih.nodes + nodenum;
+ if (node->type == BIH_UNORDERED)
+ {
+ for (axis = 0;axis < BIH_MAXUNORDEREDCHILDREN && node->children[axis] >= 0;axis++)
+ {
+ leaf = model->collision_bih.leafs + node->children[axis];
+#if 1
+ if (!BoxesOverlap(segmentmins, segmentmaxs, leaf->mins, leaf->maxs))
+ continue;
+#endif
+ switch(leaf->type)
+ {
+ case BIH_BRUSH:
+ brush = model->brush.data_brushes[leaf->itemindex].colbrushf;
+ Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, brush, brush);
+ break;
+ case BIH_COLLISIONTRIANGLE:
+ if (!mod_q3bsp_curves_collisions.integer)
+ continue;
+ e = model->brush.data_collisionelement3i + 3*leaf->itemindex;
+ texture = model->data_textures + leaf->textureindex;
+ Collision_TraceBrushTriangleFloat(trace, thisbrush_start, thisbrush_end, model->brush.data_collisionvertex3f + e[0] * 3, model->brush.data_collisionvertex3f + e[1] * 3, model->brush.data_collisionvertex3f + e[2] * 3, texture->supercontents, texture->surfaceflags, texture);
+ break;
+ case BIH_RENDERTRIANGLE:
+ e = model->surfmesh.data_element3i + 3*leaf->itemindex;
+ texture = model->data_textures + leaf->textureindex;
+ Collision_TraceBrushTriangleFloat(trace, thisbrush_start, thisbrush_end, model->surfmesh.data_vertex3f + e[0] * 3, model->surfmesh.data_vertex3f + e[1] * 3, model->surfmesh.data_vertex3f + e[2] * 3, texture->supercontents, texture->surfaceflags, texture);
+ break;
+ }
+ }
+ return;
+ }
+ axis = node->type - BIH_SPLITX;
+#if 1
+ if (!BoxesOverlap(segmentmins, segmentmaxs, node->mins, node->maxs))
+ return;
+#endif
+#if 0
+ Mod_CollisionBIH_TraceBrush_RecursiveBIHNode(trace, model, node->front, thisbrush_start, thisbrush_end, segmentmins, segmentmaxs);
+ nodenum = node->back;
+ continue;
+#endif
+ if (segmentmins[axis] <= node->backmax)
+ {
+ if (segmentmaxs[axis] >= node->frontmin)
+ Mod_CollisionBIH_TraceBrush_RecursiveBIHNode(trace, model, node->front, thisbrush_start, thisbrush_end, segmentmins, segmentmaxs);
+ nodenum = node->back;
+ }
+ else if (segmentmaxs[axis] >= node->frontmin)
+ nodenum = node->front;
+ else
+ return; // trace falls between children
+ }
+}
+
+void Mod_CollisionBIH_TracePoint(dp_model_t *model, const frameblend_t *frameblend, const skeleton_t *skeleton, trace_t *trace, const vec3_t start, int hitsupercontentsmask)
+{
+ memset(trace, 0, sizeof(*trace));
+ trace->fraction = 1;
+ trace->realfraction = 1;
+ trace->hitsupercontentsmask = hitsupercontentsmask;
+ Mod_CollisionBIH_TracePoint_RecursiveBIHNode(trace, model, model->collision_bih.rootnode, start);
+}
+
+void Mod_CollisionBIH_TraceLine(dp_model_t *model, const frameblend_t *frameblend, const skeleton_t *skeleton, trace_t *trace, const vec3_t start, const vec3_t end, int hitsupercontentsmask)
+{
+ if (VectorCompare(start, end))
+ {
+ Mod_CollisionBIH_TracePoint(model, frameblend, skeleton, trace, start, hitsupercontentsmask);
+ return;
+ }
+
+ memset(trace, 0, sizeof(*trace));
+ trace->fraction = 1;
+ trace->realfraction = 1;
+ trace->hitsupercontentsmask = hitsupercontentsmask;
+ Mod_CollisionBIH_TraceLine_RecursiveBIHNode(trace, model, &model->collision_bih, model->collision_bih.rootnode, start, end, start, end);
+}
+
+void Mod_CollisionBIH_TraceBox(dp_model_t *model, const frameblend_t *frameblend, const skeleton_t *skeleton, trace_t *trace, const vec3_t start, const vec3_t boxmins, const vec3_t boxmaxs, const vec3_t end, int hitsupercontentsmask)
+{
+ float segmentmins[3], segmentmaxs[3];
+ colboxbrushf_t thisbrush_start, thisbrush_end;
+ vec3_t boxstartmins, boxstartmaxs, boxendmins, boxendmaxs;
+
+ if (mod_q3bsp_optimizedtraceline.integer && VectorCompare(boxmins, boxmaxs))
+ {
+ vec3_t shiftstart, shiftend;
+ VectorAdd(start, boxmins, shiftstart);
+ VectorAdd(end, boxmins, shiftend);
+ if (VectorCompare(start, end))
+ Mod_CollisionBIH_TracePoint(model, frameblend, skeleton, trace, shiftstart, hitsupercontentsmask);
+ else
+ Mod_CollisionBIH_TraceLine(model, frameblend, skeleton, trace, shiftstart, shiftend, hitsupercontentsmask);
+ return;
+ }
+
+ // box trace, performed as brush trace
+ memset(trace, 0, sizeof(*trace));
+ trace->fraction = 1;
+ trace->realfraction = 1;
+ trace->hitsupercontentsmask = hitsupercontentsmask;
+ segmentmins[0] = min(start[0], end[0]) + boxmins[0] - 1;
+ segmentmins[1] = min(start[1], end[1]) + boxmins[1] - 1;
+ segmentmins[2] = min(start[2], end[2]) + boxmins[2] - 1;
+ segmentmaxs[0] = max(start[0], end[0]) + boxmaxs[0] + 1;
+ segmentmaxs[1] = max(start[1], end[1]) + boxmaxs[1] + 1;
+ segmentmaxs[2] = max(start[2], end[2]) + boxmaxs[2] + 1;
+ VectorAdd(start, boxmins, boxstartmins);
+ VectorAdd(start, boxmaxs, boxstartmaxs);
+ VectorAdd(end, boxmins, boxendmins);
+ VectorAdd(end, boxmaxs, boxendmaxs);
+ Collision_BrushForBox(&thisbrush_start, boxstartmins, boxstartmaxs, 0, 0, NULL);
+ Collision_BrushForBox(&thisbrush_end, boxendmins, boxendmaxs, 0, 0, NULL);
+ Mod_CollisionBIH_TraceBrush_RecursiveBIHNode(trace, model, model->collision_bih.rootnode, &thisbrush_start.brush, &thisbrush_end.brush, segmentmins, segmentmaxs);
+}
+
+void Mod_CollisionBIH_TraceBrush(dp_model_t *model, const frameblend_t *frameblend, const skeleton_t *skeleton, trace_t *trace, colbrushf_t *start, colbrushf_t *end, int hitsupercontentsmask)
+{
+ float segmentmins[3], segmentmaxs[3];
+
+ if (mod_q3bsp_optimizedtraceline.integer && VectorCompare(start->mins, start->maxs) && VectorCompare(end->mins, end->maxs))
+ {
+ if (VectorCompare(start->mins, end->mins))
+ Mod_CollisionBIH_TracePoint(model, frameblend, skeleton, trace, start->mins, hitsupercontentsmask);
+ else
+ Mod_CollisionBIH_TraceLine(model, frameblend, skeleton, trace, start->mins, end->mins, hitsupercontentsmask);
+ return;
+ }
+
+ // box trace, performed as brush trace
+ memset(trace, 0, sizeof(*trace));
+ trace->fraction = 1;
+ trace->realfraction = 1;
+ trace->hitsupercontentsmask = hitsupercontentsmask;
+ segmentmins[0] = min(start->mins[0], end->mins[0]);
+ segmentmins[1] = min(start->mins[1], end->mins[1]);
+ segmentmins[2] = min(start->mins[2], end->mins[2]);
+ segmentmaxs[0] = max(start->maxs[0], end->maxs[0]);
+ segmentmaxs[1] = max(start->maxs[1], end->maxs[1]);
+ segmentmaxs[2] = max(start->maxs[2], end->maxs[2]);
+ Mod_CollisionBIH_TraceBrush_RecursiveBIHNode(trace, model, model->collision_bih.rootnode, start, end, segmentmins, segmentmaxs);
+}
+
+int Mod_CollisionBIH_PointSuperContents(struct model_s *model, int frame, const vec3_t point)
+{
+ trace_t trace;
+ Mod_CollisionBIH_TracePoint(model, NULL, NULL, &trace, point, 0);
+ return trace.startsupercontents;
+}
+
+void Mod_CollisionBIH_TracePoint_Mesh(dp_model_t *model, const frameblend_t *frameblend, const skeleton_t *skeleton, trace_t *trace, const vec3_t start, int hitsupercontentsmask)
+{
+#if 0
+ // broken - needs to be modified to count front faces and backfaces to figure out if it is in solid
+ vec3_t end;
+ int hitsupercontents;
+ VectorSet(end, start[0], start[1], model->normalmins[2]);
+#endif
+ memset(trace, 0, sizeof(*trace));
+ trace->fraction = 1;
+ trace->realfraction = 1;
+ trace->hitsupercontentsmask = hitsupercontentsmask;
+#if 0
+ Mod_CollisionBIH_TraceLine_RecursiveBIHNode(trace, model, model->collision_bih.rootnode, start, end, start, end);
+ hitsupercontents = trace->hitsupercontents;
+ memset(trace, 0, sizeof(*trace));
+ trace->fraction = 1;
+ trace->realfraction = 1;
+ trace->hitsupercontentsmask = hitsupercontentsmask;
+ trace->startsupercontents = hitsupercontents;
+#endif
+}
+
+int Mod_CollisionBIH_PointSuperContents_Mesh(struct model_s *model, int frame, const vec3_t start)
+{
+#if 0
+ // broken - needs to be modified to count front faces and backfaces to figure out if it is in solid
+ trace_t trace;
+ vec3_t end;
+ VectorSet(end, start[0], start[1], model->normalmins[2]);
+ memset(&trace, 0, sizeof(trace));
+ trace.fraction = 1;
+ trace.realfraction = 1;
+ trace.hitsupercontentsmask = 0;
+ Mod_CollisionBIH_TraceLine_RecursiveBIHNode(&trace, model, model->collision_bih.rootnode, start, end, start, end);
+ return trace.hitsupercontents;
+#else
+ return 0;
+#endif
+}
+
+static void Mod_Q3BSP_TracePoint_RecursiveBSPNode(trace_t *trace, dp_model_t *model, mnode_t *node, const vec3_t point, int markframe)
+{
+ int i;
+ mleaf_t *leaf;
+ colbrushf_t *brush;
+ // find which leaf the point is in
+ while (node->plane)
+ node = node->children[(node->plane->type < 3 ? point[node->plane->type] : DotProduct(point, node->plane->normal)) < node->plane->dist];
+ // point trace the brushes
+ leaf = (mleaf_t *)node;
+ for (i = 0;i < leaf->numleafbrushes;i++)
+ {
+ brush = model->brush.data_brushes[leaf->firstleafbrush[i]].colbrushf;
+ if (brush && brush->markframe != markframe && BoxesOverlap(point, point, brush->mins, brush->maxs))
+ {
+ brush->markframe = markframe;
+ Collision_TracePointBrushFloat(trace, point, brush);
+ }
+ }
+ // can't do point traces on curves (they have no thickness)
+}
+
+static void Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace_t *trace, dp_model_t *model, mnode_t *node, const vec3_t start, const vec3_t end, vec_t startfrac, vec_t endfrac, const vec3_t linestart, const vec3_t lineend, int markframe, const vec3_t segmentmins, const vec3_t segmentmaxs)
+{
+ int i, startside, endside;
+ float dist1, dist2, midfrac, mid[3], nodesegmentmins[3], nodesegmentmaxs[3];
+ mleaf_t *leaf;
+ msurface_t *surface;
+ mplane_t *plane;
+ colbrushf_t *brush;
+ // walk the tree until we hit a leaf, recursing for any split cases
+ while (node->plane)
+ {
+#if 0
+ if (!BoxesOverlap(segmentmins, segmentmaxs, node->mins, node->maxs))
+ return;
+ Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace, model, node->children[0], start, end, startfrac, endfrac, linestart, lineend, markframe, segmentmins, segmentmaxs);
+ node = node->children[1];
+#else
+ // abort if this part of the bsp tree can not be hit by this trace
+// if (!(node->combinedsupercontents & trace->hitsupercontentsmask))
+// return;
+ plane = node->plane;
+ // axial planes are much more common than non-axial, so an optimized
+ // axial case pays off here
+ if (plane->type < 3)
+ {
+ dist1 = start[plane->type] - plane->dist;
+ dist2 = end[plane->type] - plane->dist;
+ }
+ else
+ {
+ dist1 = DotProduct(start, plane->normal) - plane->dist;
+ dist2 = DotProduct(end, plane->normal) - plane->dist;