+static int Mod_Q3BSP_TraceLineOfSight_RecursiveNodeCheck(mnode_t *node, double p1[3], double p2[3], double endpos[3])
+{
+ double t1, t2;
+ double midf, mid[3];
+ int ret, side;
+
+ // check for empty
+ while (node->plane)
+ {
+ // find the point distances
+ mplane_t *plane = node->plane;
+ if (plane->type < 3)
+ {
+ t1 = p1[plane->type] - plane->dist;
+ t2 = p2[plane->type] - plane->dist;
+ }
+ else
+ {
+ t1 = DotProduct (plane->normal, p1) - plane->dist;
+ t2 = DotProduct (plane->normal, p2) - plane->dist;
+ }
+
+ if (t1 < 0)
+ {
+ if (t2 < 0)
+ {
+ node = node->children[1];
+ continue;
+ }
+ side = 1;
+ }
+ else
+ {
+ if (t2 >= 0)
+ {
+ node = node->children[0];
+ continue;
+ }
+ side = 0;
+ }
+
+ midf = t1 / (t1 - t2);
+ VectorLerp(p1, midf, p2, mid);
+
+ // recurse both sides, front side first
+ // return 2 if empty is followed by solid (hit something)
+ // do not return 2 if both are solid or both empty,
+ // or if start is solid and end is empty
+ // as these degenerate cases usually indicate the eye is in solid and
+ // should see the target point anyway
+ ret = Mod_Q3BSP_TraceLineOfSight_RecursiveNodeCheck(node->children[side ], p1, mid, endpos);
+ if (ret != 0)
+ return ret;
+ ret = Mod_Q3BSP_TraceLineOfSight_RecursiveNodeCheck(node->children[side ^ 1], mid, p2, endpos);
+ if (ret != 1)
+ return ret;
+ VectorCopy(mid, endpos);
+ return 2;
+ }
+ return ((mleaf_t *)node)->clusterindex < 0;
+}
+
+static qboolean Mod_Q3BSP_TraceLineOfSight(struct model_s *model, const vec3_t start, const vec3_t end, const vec3_t acceptmins, const vec3_t acceptmaxs)
+{
+ if (model->brush.submodel || mod_q3bsp_tracelineofsight_brushes.integer)
+ {
+ trace_t trace;
+ model->TraceLine(model, NULL, NULL, &trace, start, end, SUPERCONTENTS_VISBLOCKERMASK, 0, MATERIALFLAGMASK_TRANSLUCENT);
+ return trace.fraction == 1 || BoxesOverlap(trace.endpos, trace.endpos, acceptmins, acceptmaxs);
+ }
+ else
+ {
+ double tracestart[3], traceend[3], traceendpos[3];
+ VectorCopy(start, tracestart);
+ VectorCopy(end, traceend);
+ VectorCopy(end, traceendpos);
+ Mod_Q3BSP_TraceLineOfSight_RecursiveNodeCheck(model->brush.data_nodes, tracestart, traceend, traceendpos);
+ return BoxesOverlap(traceendpos, traceendpos, acceptmins, acceptmaxs);
+ }
+}
+
+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, int skipsupercontentsmask, int skipmaterialflagsmask)
+{
+ const bih_t *bih;
+ const bih_leaf_t *leaf;
+ const bih_node_t *node;
+ const colbrushf_t *brush;
+ int axis;
+ int nodenum;
+ int nodestackpos = 0;
+ int nodestack[1024];
+
+ memset(trace, 0, sizeof(*trace));
+ trace->fraction = 1;
+ trace->hitsupercontentsmask = hitsupercontentsmask;
+ trace->skipsupercontentsmask = skipsupercontentsmask;
+ trace->skipmaterialflagsmask = skipmaterialflagsmask;
+
+ bih = &model->collision_bih;
+ if(!bih->nodes)
+ return;
+
+ nodenum = bih->rootnode;
+ nodestack[nodestackpos++] = nodenum;
+ while (nodestackpos)
+ {
+ nodenum = nodestack[--nodestackpos];
+ node = bih->nodes + nodenum;
+#if 1
+ if (!BoxesOverlap(start, start, node->mins, node->maxs))
+ continue;
+#endif
+ if (node->type <= BIH_SPLITZ && nodestackpos+2 <= 1024)
+ {
+ axis = node->type - BIH_SPLITX;
+ if (start[axis] >= node->frontmin)
+ nodestack[nodestackpos++] = node->front;
+ if (start[axis] <= node->backmax)
+ nodestack[nodestackpos++] = node->back;
+ }
+ else if (node->type == BIH_UNORDERED)
+ {
+ for (axis = 0;axis < BIH_MAXUNORDEREDCHILDREN && node->children[axis] >= 0;axis++)
+ {
+ leaf = bih->leafs + node->children[axis];
+#if 1
+ if (!BoxesOverlap(start, start, leaf->mins, leaf->maxs))
+ continue;
+#endif
+ switch(leaf->type)
+ {
+ case BIH_BRUSH:
+ brush = model->brush.data_brushes[leaf->itemindex].colbrushf;
+ Collision_TracePointBrushFloat(trace, start, brush);
+ break;
+ case BIH_COLLISIONTRIANGLE:
+ // collision triangle - skipped because they have no volume
+ break;
+ case BIH_RENDERTRIANGLE:
+ // render triangle - skipped because they have no volume
+ break;
+ }
+ }
+ }
+ }
+}
+
+static void Mod_CollisionBIH_TraceLineShared(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, int skipsupercontentsmask, int skipmaterialflagsmask, const bih_t *bih)
+{
+ const bih_leaf_t *leaf;
+ const bih_node_t *node;
+ const colbrushf_t *brush;
+ const int *e;
+ const texture_t *texture;
+ vec3_t nodebigmins, nodebigmaxs, nodestart, nodeend, sweepnodemins, sweepnodemaxs;
+ vec_t d1, d2, d3, d4, f, nodestackline[1024][6];
+ int axis, nodenum, nodestackpos = 0, nodestack[1024];
+
+ if(!bih->nodes)
+ return;
+
+ if (VectorCompare(start, end))
+ {
+ Mod_CollisionBIH_TracePoint(model, frameblend, skeleton, trace, start, hitsupercontentsmask, skipsupercontentsmask, skipmaterialflagsmask);
+ return;
+ }
+
+ nodenum = bih->rootnode;
+
+ memset(trace, 0, sizeof(*trace));
+ trace->fraction = 1;
+ trace->hitsupercontentsmask = hitsupercontentsmask;
+ trace->skipsupercontentsmask = skipsupercontentsmask;
+ trace->skipmaterialflagsmask = skipmaterialflagsmask;
+
+ // push first node
+ nodestackline[nodestackpos][0] = start[0];
+ nodestackline[nodestackpos][1] = start[1];
+ nodestackline[nodestackpos][2] = start[2];
+ nodestackline[nodestackpos][3] = end[0];
+ nodestackline[nodestackpos][4] = end[1];
+ nodestackline[nodestackpos][5] = end[2];
+ nodestack[nodestackpos++] = nodenum;
+ while (nodestackpos)
+ {
+ nodenum = nodestack[--nodestackpos];
+ node = bih->nodes + nodenum;
+ VectorCopy(nodestackline[nodestackpos], nodestart);
+ VectorCopy(nodestackline[nodestackpos] + 3, nodeend);
+ sweepnodemins[0] = min(nodestart[0], nodeend[0]) - 1;
+ sweepnodemins[1] = min(nodestart[1], nodeend[1]) - 1;
+ sweepnodemins[2] = min(nodestart[2], nodeend[2]) - 1;
+ sweepnodemaxs[0] = max(nodestart[0], nodeend[0]) + 1;
+ sweepnodemaxs[1] = max(nodestart[1], nodeend[1]) + 1;
+ sweepnodemaxs[2] = max(nodestart[2], nodeend[2]) + 1;
+ if (!BoxesOverlap(sweepnodemins, sweepnodemaxs, node->mins, node->maxs) && !collision_bih_fullrecursion.integer)
+ continue;
+ if (node->type <= BIH_SPLITZ && nodestackpos+2 <= 1024)
+ {
+ // recurse children of the split
+ axis = node->type - BIH_SPLITX;
+ d1 = node->backmax - nodestart[axis];
+ d2 = node->backmax - nodeend[axis];
+ d3 = nodestart[axis] - node->frontmin;
+ d4 = nodeend[axis] - node->frontmin;
+ if (collision_bih_fullrecursion.integer)
+ d1 = d2 = d3 = d4 = 1; // force full recursion
+ switch((d1 < 0) | ((d2 < 0) << 1) | ((d3 < 0) << 2) | ((d4 < 0) << 3))
+ {
+ case 0: /* >>>> */ VectorCopy(nodestart, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; VectorCopy(nodestart, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 1: /* <>>> */ f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; VectorCopy(nodestart, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 2: /* ><>> */ f = d1 / (d1 - d2); VectorCopy(nodestart, nodestackline[nodestackpos]); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; VectorCopy(nodestart, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 3: /* <<>> */ VectorCopy(nodestart, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 4: /* >><> */ VectorCopy(nodestart, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; f = d3 / (d3 - d4); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 5: /* <><> */ f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; f = d3 / (d3 - d4); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 6: /* ><<> */ f = d1 / (d1 - d2); VectorCopy(nodestart, nodestackline[nodestackpos]); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; f = d3 / (d3 - d4); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 7: /* <<<> */ f = d3 / (d3 - d4); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 8: /* >>>< */ VectorCopy(nodestart, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; f = d3 / (d3 - d4); VectorCopy(nodestart, nodestackline[nodestackpos]); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 9: /* <>>< */ f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; f = d3 / (d3 - d4); VectorCopy(nodestart, nodestackline[nodestackpos]); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 10: /* ><>< */ f = d1 / (d1 - d2); VectorCopy(nodestart, nodestackline[nodestackpos]); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; f = d3 / (d3 - d4); VectorCopy(nodestart, nodestackline[nodestackpos]); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 11: /* <<>< */ f = d3 / (d3 - d4); VectorCopy(nodestart, nodestackline[nodestackpos]); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 12: /* >><< */ VectorCopy(nodestart, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; break;
+ case 13: /* <><< */ f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; break;
+ case 14: /* ><<< */ f = d1 / (d1 - d2); VectorCopy(nodestart, nodestackline[nodestackpos]); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; break;
+ case 15: /* <<<< */ break;
+ }
+ }
+ else if (node->type == BIH_UNORDERED)
+ {
+ // calculate sweep bounds for this node
+ // copy node bounds into local variables
+ VectorCopy(node->mins, nodebigmins);
+ VectorCopy(node->maxs, nodebigmaxs);
+ // clip line to this node bounds
+ axis = 0; d1 = nodestart[axis] - nodebigmins[axis]; d2 = nodeend[axis] - nodebigmins[axis]; if (d1 < 0) { if (d2 < 0) continue; f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestart); } else if (d2 < 0) { f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodeend); } d1 = nodebigmaxs[axis] - nodestart[axis]; d2 = nodebigmaxs[axis] - nodeend[axis]; if (d1 < 0) { if (d2 < 0) continue; f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestart); } else if (d2 < 0) { f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodeend); }
+ axis = 1; d1 = nodestart[axis] - nodebigmins[axis]; d2 = nodeend[axis] - nodebigmins[axis]; if (d1 < 0) { if (d2 < 0) continue; f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestart); } else if (d2 < 0) { f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodeend); } d1 = nodebigmaxs[axis] - nodestart[axis]; d2 = nodebigmaxs[axis] - nodeend[axis]; if (d1 < 0) { if (d2 < 0) continue; f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestart); } else if (d2 < 0) { f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodeend); }
+ axis = 2; d1 = nodestart[axis] - nodebigmins[axis]; d2 = nodeend[axis] - nodebigmins[axis]; if (d1 < 0) { if (d2 < 0) continue; f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestart); } else if (d2 < 0) { f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodeend); } d1 = nodebigmaxs[axis] - nodestart[axis]; d2 = nodebigmaxs[axis] - nodeend[axis]; if (d1 < 0) { if (d2 < 0) continue; f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestart); } else if (d2 < 0) { f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodeend); }
+ // some of the line intersected the enlarged node box
+ // calculate sweep bounds for this node
+ sweepnodemins[0] = min(nodestart[0], nodeend[0]) - 1;
+ sweepnodemins[1] = min(nodestart[1], nodeend[1]) - 1;
+ sweepnodemins[2] = min(nodestart[2], nodeend[2]) - 1;
+ sweepnodemaxs[0] = max(nodestart[0], nodeend[0]) + 1;
+ sweepnodemaxs[1] = max(nodestart[1], nodeend[1]) + 1;
+ sweepnodemaxs[2] = max(nodestart[2], nodeend[2]) + 1;
+ for (axis = 0;axis < BIH_MAXUNORDEREDCHILDREN && node->children[axis] >= 0;axis++)
+ {
+ leaf = bih->leafs + node->children[axis];
+ if (!BoxesOverlap(sweepnodemins, sweepnodemaxs, leaf->mins, leaf->maxs))
+ continue;
+ switch(leaf->type)
+ {
+ case BIH_BRUSH:
+ brush = model->brush.data_brushes[leaf->itemindex].colbrushf;
+ Collision_TraceLineBrushFloat(trace, start, 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_TraceLineTriangleFloat(trace, start, 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_TraceLineTriangleFloat(trace, start, 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;
+ }
+ }
+ }
+ }
+}
+
+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, int skipsupercontentsmask, int skipmaterialflagsmask)
+{
+ if (VectorCompare(start, end))
+ {
+ Mod_CollisionBIH_TracePoint(model, frameblend, skeleton, trace, start, hitsupercontentsmask, skipsupercontentsmask, skipmaterialflagsmask);
+ return;
+ }
+ Mod_CollisionBIH_TraceLineShared(model, frameblend, skeleton, trace, start, end, hitsupercontentsmask, skipsupercontentsmask, skipmaterialflagsmask, &model->collision_bih);
+}
+
+void Mod_CollisionBIH_TraceBrush(dp_model_t *model, const frameblend_t *frameblend, const skeleton_t *skeleton, trace_t *trace, colbrushf_t *thisbrush_start, colbrushf_t *thisbrush_end, int hitsupercontentsmask, int skipsupercontentsmask, int skipmaterialflagsmask)
+{
+ const bih_t *bih;
+ const bih_leaf_t *leaf;
+ const bih_node_t *node;
+ const colbrushf_t *brush;
+ const int *e;
+ const texture_t *texture;
+ vec3_t start, end, startmins, startmaxs, endmins, endmaxs, mins, maxs;
+ vec3_t nodebigmins, nodebigmaxs, nodestart, nodeend, sweepnodemins, sweepnodemaxs;
+ vec_t d1, d2, d3, d4, f, nodestackline[1024][6];
+ int axis, nodenum, nodestackpos = 0, nodestack[1024];
+
+ if (mod_q3bsp_optimizedtraceline.integer && VectorCompare(thisbrush_start->mins, thisbrush_start->maxs) && VectorCompare(thisbrush_end->mins, thisbrush_end->maxs))
+ {
+ if (VectorCompare(thisbrush_start->mins, thisbrush_end->mins))
+ Mod_CollisionBIH_TracePoint(model, frameblend, skeleton, trace, thisbrush_start->mins, hitsupercontentsmask, skipsupercontentsmask, skipmaterialflagsmask);
+ else
+ Mod_CollisionBIH_TraceLine(model, frameblend, skeleton, trace, thisbrush_start->mins, thisbrush_end->mins, hitsupercontentsmask, skipsupercontentsmask, skipmaterialflagsmask);
+ return;
+ }
+
+ bih = &model->collision_bih;
+ if(!bih->nodes)
+ return;
+ nodenum = bih->rootnode;
+
+ // box trace, performed as brush trace
+ memset(trace, 0, sizeof(*trace));
+ trace->fraction = 1;
+ trace->hitsupercontentsmask = hitsupercontentsmask;
+ trace->skipsupercontentsmask = skipsupercontentsmask;
+ trace->skipmaterialflagsmask = skipmaterialflagsmask;
+
+ // calculate tracebox-like parameters for efficient culling
+ VectorMAM(0.5f, thisbrush_start->mins, 0.5f, thisbrush_start->maxs, start);
+ VectorMAM(0.5f, thisbrush_end->mins, 0.5f, thisbrush_end->maxs, end);
+ VectorSubtract(thisbrush_start->mins, start, startmins);
+ VectorSubtract(thisbrush_start->maxs, start, startmaxs);
+ VectorSubtract(thisbrush_end->mins, end, endmins);
+ VectorSubtract(thisbrush_end->maxs, end, endmaxs);
+ mins[0] = min(startmins[0], endmins[0]);
+ mins[1] = min(startmins[1], endmins[1]);
+ mins[2] = min(startmins[2], endmins[2]);
+ maxs[0] = max(startmaxs[0], endmaxs[0]);
+ maxs[1] = max(startmaxs[1], endmaxs[1]);
+ maxs[2] = max(startmaxs[2], endmaxs[2]);
+
+ // push first node
+ nodestackline[nodestackpos][0] = start[0];
+ nodestackline[nodestackpos][1] = start[1];
+ nodestackline[nodestackpos][2] = start[2];
+ nodestackline[nodestackpos][3] = end[0];
+ nodestackline[nodestackpos][4] = end[1];
+ nodestackline[nodestackpos][5] = end[2];
+ nodestack[nodestackpos++] = nodenum;
+ while (nodestackpos)
+ {
+ nodenum = nodestack[--nodestackpos];
+ node = bih->nodes + nodenum;
+ VectorCopy(nodestackline[nodestackpos], nodestart);
+ VectorCopy(nodestackline[nodestackpos] + 3, nodeend);
+ sweepnodemins[0] = min(nodestart[0], nodeend[0]) + mins[0] - 1;
+ sweepnodemins[1] = min(nodestart[1], nodeend[1]) + mins[1] - 1;
+ sweepnodemins[2] = min(nodestart[2], nodeend[2]) + mins[2] - 1;
+ sweepnodemaxs[0] = max(nodestart[0], nodeend[0]) + maxs[0] + 1;
+ sweepnodemaxs[1] = max(nodestart[1], nodeend[1]) + maxs[1] + 1;
+ sweepnodemaxs[2] = max(nodestart[2], nodeend[2]) + maxs[2] + 1;
+ if (!BoxesOverlap(sweepnodemins, sweepnodemaxs, node->mins, node->maxs))
+ continue;
+ if (node->type <= BIH_SPLITZ && nodestackpos+2 <= 1024)
+ {
+ // recurse children of the split
+ axis = node->type - BIH_SPLITX;
+ d1 = node->backmax - nodestart[axis] - mins[axis];
+ d2 = node->backmax - nodeend[axis] - mins[axis];
+ d3 = nodestart[axis] - node->frontmin + maxs[axis];
+ d4 = nodeend[axis] - node->frontmin + maxs[axis];
+ switch((d1 < 0) | ((d2 < 0) << 1) | ((d3 < 0) << 2) | ((d4 < 0) << 3))
+ {
+ case 0: /* >>>> */ VectorCopy(nodestart, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; VectorCopy(nodestart, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 1: /* <>>> */ f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; VectorCopy(nodestart, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 2: /* ><>> */ f = d1 / (d1 - d2); VectorCopy(nodestart, nodestackline[nodestackpos]); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; VectorCopy(nodestart, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 3: /* <<>> */ VectorCopy(nodestart, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 4: /* >><> */ VectorCopy(nodestart, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; f = d3 / (d3 - d4); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 5: /* <><> */ f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; f = d3 / (d3 - d4); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 6: /* ><<> */ f = d1 / (d1 - d2); VectorCopy(nodestart, nodestackline[nodestackpos]); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; f = d3 / (d3 - d4); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 7: /* <<<> */ f = d3 / (d3 - d4); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 8: /* >>>< */ VectorCopy(nodestart, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; f = d3 / (d3 - d4); VectorCopy(nodestart, nodestackline[nodestackpos]); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 9: /* <>>< */ f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; f = d3 / (d3 - d4); VectorCopy(nodestart, nodestackline[nodestackpos]); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 10: /* ><>< */ f = d1 / (d1 - d2); VectorCopy(nodestart, nodestackline[nodestackpos]); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; f = d3 / (d3 - d4); VectorCopy(nodestart, nodestackline[nodestackpos]); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 11: /* <<>< */ f = d3 / (d3 - d4); VectorCopy(nodestart, nodestackline[nodestackpos]); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->front; break;
+ case 12: /* >><< */ VectorCopy(nodestart, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; break;
+ case 13: /* <><< */ f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos]); VectorCopy( nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; break;
+ case 14: /* ><<< */ f = d1 / (d1 - d2); VectorCopy(nodestart, nodestackline[nodestackpos]); VectorLerp(nodestart, f, nodeend, nodestackline[nodestackpos] + 3); nodestack[nodestackpos++] = node->back; break;
+ case 15: /* <<<< */ break;
+ }
+ }
+ else if (node->type == BIH_UNORDERED)
+ {
+ // calculate sweep bounds for this node
+ // copy node bounds into local variables and expand to get Minkowski Sum of the two shapes
+ VectorSubtract(node->mins, maxs, nodebigmins);
+ VectorSubtract(node->maxs, mins, nodebigmaxs);
+ // clip line to this node bounds
+ axis = 0; d1 = nodestart[axis] - nodebigmins[axis]; d2 = nodeend[axis] - nodebigmins[axis]; if (d1 < 0) { if (d2 < 0) continue; f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestart); } else if (d2 < 0) { f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodeend); } d1 = nodebigmaxs[axis] - nodestart[axis]; d2 = nodebigmaxs[axis] - nodeend[axis]; if (d1 < 0) { if (d2 < 0) continue; f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestart); } else if (d2 < 0) { f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodeend); }
+ axis = 1; d1 = nodestart[axis] - nodebigmins[axis]; d2 = nodeend[axis] - nodebigmins[axis]; if (d1 < 0) { if (d2 < 0) continue; f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestart); } else if (d2 < 0) { f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodeend); } d1 = nodebigmaxs[axis] - nodestart[axis]; d2 = nodebigmaxs[axis] - nodeend[axis]; if (d1 < 0) { if (d2 < 0) continue; f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestart); } else if (d2 < 0) { f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodeend); }
+ axis = 2; d1 = nodestart[axis] - nodebigmins[axis]; d2 = nodeend[axis] - nodebigmins[axis]; if (d1 < 0) { if (d2 < 0) continue; f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestart); } else if (d2 < 0) { f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodeend); } d1 = nodebigmaxs[axis] - nodestart[axis]; d2 = nodebigmaxs[axis] - nodeend[axis]; if (d1 < 0) { if (d2 < 0) continue; f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodestart); } else if (d2 < 0) { f = d1 / (d1 - d2); VectorLerp(nodestart, f, nodeend, nodeend); }
+ // some of the line intersected the enlarged node box
+ // calculate sweep bounds for this node
+ sweepnodemins[0] = min(nodestart[0], nodeend[0]) + mins[0] - 1;
+ sweepnodemins[1] = min(nodestart[1], nodeend[1]) + mins[1] - 1;
+ sweepnodemins[2] = min(nodestart[2], nodeend[2]) + mins[2] - 1;
+ sweepnodemaxs[0] = max(nodestart[0], nodeend[0]) + maxs[0] + 1;
+ sweepnodemaxs[1] = max(nodestart[1], nodeend[1]) + maxs[1] + 1;
+ sweepnodemaxs[2] = max(nodestart[2], nodeend[2]) + maxs[2] + 1;
+ for (axis = 0;axis < BIH_MAXUNORDEREDCHILDREN && node->children[axis] >= 0;axis++)
+ {
+ leaf = bih->leafs + node->children[axis];
+ if (!BoxesOverlap(sweepnodemins, sweepnodemaxs, leaf->mins, leaf->maxs))
+ continue;
+ 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;
+ }
+ }
+ }
+ }
+}
+
+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, int skipsupercontentsmask, int skipmaterialflagsmask)
+{
+ colboxbrushf_t thisbrush_start, thisbrush_end;
+ vec3_t boxstartmins, boxstartmaxs, boxendmins, boxendmaxs;
+
+ // box trace, performed as brush trace
+ 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(model, frameblend, skeleton, trace, &thisbrush_start.brush, &thisbrush_end.brush, hitsupercontentsmask, skipsupercontentsmask, skipmaterialflagsmask);
+}
+
+
+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, 0, 0);
+ return trace.startsupercontents;
+}
+
+qboolean Mod_CollisionBIH_TraceLineOfSight(struct model_s *model, const vec3_t start, const vec3_t end, const vec3_t acceptmins, const vec3_t acceptmaxs)
+{
+ trace_t trace;
+ Mod_CollisionBIH_TraceLine(model, NULL, NULL, &trace, start, end, SUPERCONTENTS_VISBLOCKERMASK, 0, MATERIALFLAGMASK_TRANSLUCENT);
+ return trace.fraction == 1 || BoxesOverlap(trace.endpos, trace.endpos, acceptmins, acceptmaxs);
+}
+
+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, int skipsupercontentsmask, int skipmaterialflagsmask)
+{
+#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->hitsupercontentsmask = hitsupercontentsmask;
+ trace->skipsupercontentsmask = skipsupercontentsmask;
+ trace->skipmaterialflagsmask = skipmaterialflagsmask;
+#if 0
+ Mod_CollisionBIH_TraceLine(model, frameblend, skeleton, trace, start, end, hitsupercontentsmask, skipsupercontentsmask, skipmaterialflagsmask);
+ hitsupercontents = trace->hitsupercontents;
+ memset(trace, 0, sizeof(*trace));
+ trace->fraction = 1;
+ trace->hitsupercontentsmask = hitsupercontentsmask;
+ trace->skipsupercontentsmask = skipsupercontentsmask;
+ trace->skipmaterialflagsmask = skipmaterialflagsmask;
+ 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.hitsupercontentsmask = hitsupercontentsmask;
+ trace.skipsupercontentsmask = skipsupercontentsmask;
+ trace.skipmaterialflagsmask = skipmaterialflagsmask;
+ Mod_CollisionBIH_TraceLine(model, frameblend, skeleton, trace, start, end, hitsupercontentsmask, skipsupercontentsmask, skipmaterialflagsmask);
+ return trace.hitsupercontents;
+#else
+ return 0;
+#endif
+}
+