#define HULLCHECKSTATE_SOLID 1
#define HULLCHECKSTATE_DONE 2
-extern cvar_t collision_prefernudgedfraction;
static int Mod_Q1BSP_RecursiveHullCheck(RecursiveHullCheckTraceInfo_t *t, int num, double p1f, double p2f, double p1[3], double p2[3])
{
// status variables, these don't need to be saved on the stack when
// variables that need to be stored on the stack when recursing
mclipnode_t *node;
- int side;
+ int p1side, p2side;
double midf, mid[3];
- // LordHavoc: a goto! everyone flee in terror... :)
-loc0:
- // check for empty
- if (num < 0)
- {
- num = Mod_Q1BSP_SuperContentsFromNativeContents(NULL, num);
- if (!t->trace->startfound)
- {
- t->trace->startfound = true;
- t->trace->startsupercontents |= num;
- }
- if (num & SUPERCONTENTS_LIQUIDSMASK)
- t->trace->inwater = true;
- if (num == 0)
- t->trace->inopen = true;
- if (num & SUPERCONTENTS_SOLID)
- t->trace->hittexture = &mod_q1bsp_texture_solid;
- else if (num & SUPERCONTENTS_SKY)
- t->trace->hittexture = &mod_q1bsp_texture_sky;
- else if (num & SUPERCONTENTS_LAVA)
- t->trace->hittexture = &mod_q1bsp_texture_lava;
- else if (num & SUPERCONTENTS_SLIME)
- t->trace->hittexture = &mod_q1bsp_texture_slime;
- else
- t->trace->hittexture = &mod_q1bsp_texture_water;
- t->trace->hitq3surfaceflags = t->trace->hittexture->surfaceflags;
- t->trace->hitsupercontents = num;
- if (num & t->trace->hitsupercontentsmask)
+ // keep looping until we hit a leaf
+ while (num >= 0)
+ {
+ // find the point distances
+ node = t->hull->clipnodes + num;
+ plane = t->hull->planes + node->planenum;
+
+ // axial planes can be calculated more quickly without the DotProduct
+ if (plane->type < 3)
{
- // if the first leaf is solid, set startsolid
- if (t->trace->allsolid)
- t->trace->startsolid = true;
-#if COLLISIONPARANOID >= 3
- Con_Print("S");
-#endif
- return HULLCHECKSTATE_SOLID;
+ t1 = p1[plane->type] - plane->dist;
+ t2 = p2[plane->type] - plane->dist;
}
else
{
- t->trace->allsolid = false;
-#if COLLISIONPARANOID >= 3
- Con_Print("E");
-#endif
- return HULLCHECKSTATE_EMPTY;
+ t1 = DotProduct (plane->normal, p1) - plane->dist;
+ t2 = DotProduct (plane->normal, p2) - plane->dist;
}
- }
- // find the point distances
- node = t->hull->clipnodes + num;
+ // negative plane distances indicate children[1] (behind plane)
+ p1side = t1 < 0;
+ p2side = t2 < 0;
- plane = t->hull->planes + node->planenum;
- 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)
+ // if the line starts and ends on the same side of the plane, recurse
+ // into that child instantly
+ if (p1side == p2side)
{
#if COLLISIONPARANOID >= 3
- Con_Print("<");
+ if (p1side)
+ Con_Print("<");
+ else
+ Con_Print(">");
#endif
- num = node->children[1];
- goto loc0;
+ // loop back and process the start child
+ num = node->children[p1side];
}
- side = 1;
- }
- else
- {
- if (t2 >= 0)
+ else
{
+ // find the midpoint where the line crosses the plane, use the
+ // original line for best accuracy
#if COLLISIONPARANOID >= 3
- Con_Print(">");
+ Con_Print("M");
#endif
- num = node->children[0];
- goto loc0;
- }
- side = 0;
- }
+ if (plane->type < 3)
+ {
+ t1 = t->start[plane->type] - plane->dist;
+ t2 = t->end[plane->type] - plane->dist;
+ }
+ else
+ {
+ t1 = DotProduct (plane->normal, t->start) - plane->dist;
+ t2 = DotProduct (plane->normal, t->end) - plane->dist;
+ }
+ midf = t1 / (t1 - t2);
+ midf = bound(p1f, midf, p2f);
+ VectorMA(t->start, midf, t->dist, mid);
+
+ // we now have a mid point, essentially splitting the line into
+ // the segments in the near child and the far child, we can now
+ // recurse those in order and get their results
+
+ // recurse both sides, front side first
+ ret = Mod_Q1BSP_RecursiveHullCheck(t, node->children[p1side], p1f, midf, p1, mid);
+ // if this side is not empty, return what it is (solid or done)
+ if (ret != HULLCHECKSTATE_EMPTY)
+ return ret;
+
+ ret = Mod_Q1BSP_RecursiveHullCheck(t, node->children[p2side], midf, p2f, mid, p2);
+ // if other side is not solid, return what it is (empty or done)
+ if (ret != HULLCHECKSTATE_SOLID)
+ return ret;
+
+ // front is air and back is solid, this is the impact point...
+
+ // copy the plane information, flipping it if needed
+ if (p1side)
+ {
+ t->trace->plane.dist = -plane->dist;
+ VectorNegate (plane->normal, t->trace->plane.normal);
+ }
+ else
+ {
+ t->trace->plane.dist = plane->dist;
+ VectorCopy (plane->normal, t->trace->plane.normal);
+ }
+
+ // calculate the true fraction
+ t1 = DotProduct(t->trace->plane.normal, t->start) - t->trace->plane.dist;
+ t2 = DotProduct(t->trace->plane.normal, t->end) - t->trace->plane.dist;
+ midf = t1 / (t1 - t2);
+ t->trace->realfraction = bound(0, midf, 1);
+
+ // calculate the return fraction which is nudged off the surface a bit
+ midf = (t1 - collision_impactnudge.value) / (t1 - t2);
+ t->trace->fraction = bound(0, midf, 1);
+
+ if (collision_prefernudgedfraction.integer)
+ t->trace->realfraction = t->trace->fraction;
- // the line intersects, find intersection point
- // LordHavoc: this uses the original trace for maximum accuracy
#if COLLISIONPARANOID >= 3
- Con_Print("M");
+ Con_Print("D");
#endif
- if (plane->type < 3)
- {
- t1 = t->start[plane->type] - plane->dist;
- t2 = t->end[plane->type] - plane->dist;
- }
- else
- {
- t1 = DotProduct (plane->normal, t->start) - plane->dist;
- t2 = DotProduct (plane->normal, t->end) - plane->dist;
+ return HULLCHECKSTATE_DONE;
+ }
}
- midf = t1 / (t1 - t2);
- midf = bound(p1f, midf, p2f);
- VectorMA(t->start, midf, t->dist, mid);
+ // we reached a leaf contents
- // recurse both sides, front side first
- ret = Mod_Q1BSP_RecursiveHullCheck(t, node->children[side], p1f, midf, p1, mid);
- // if this side is not empty, return what it is (solid or done)
- if (ret != HULLCHECKSTATE_EMPTY)
- return ret;
-
- ret = Mod_Q1BSP_RecursiveHullCheck(t, node->children[side ^ 1], midf, p2f, mid, p2);
- // if other side is not solid, return what it is (empty or done)
- if (ret != HULLCHECKSTATE_SOLID)
- return ret;
-
- // front is air and back is solid, this is the impact point...
- if (side)
+ // check for empty
+ num = Mod_Q1BSP_SuperContentsFromNativeContents(NULL, num);
+ if (!t->trace->startfound)
{
- t->trace->plane.dist = -plane->dist;
- VectorNegate (plane->normal, t->trace->plane.normal);
+ t->trace->startfound = true;
+ t->trace->startsupercontents |= num;
}
+ if (num & SUPERCONTENTS_LIQUIDSMASK)
+ t->trace->inwater = true;
+ if (num == 0)
+ t->trace->inopen = true;
+ if (num & SUPERCONTENTS_SOLID)
+ t->trace->hittexture = &mod_q1bsp_texture_solid;
+ else if (num & SUPERCONTENTS_SKY)
+ t->trace->hittexture = &mod_q1bsp_texture_sky;
+ else if (num & SUPERCONTENTS_LAVA)
+ t->trace->hittexture = &mod_q1bsp_texture_lava;
+ else if (num & SUPERCONTENTS_SLIME)
+ t->trace->hittexture = &mod_q1bsp_texture_slime;
else
+ t->trace->hittexture = &mod_q1bsp_texture_water;
+ t->trace->hitq3surfaceflags = t->trace->hittexture->surfaceflags;
+ t->trace->hitsupercontents = num;
+ if (num & t->trace->hitsupercontentsmask)
{
- t->trace->plane.dist = plane->dist;
- VectorCopy (plane->normal, t->trace->plane.normal);
+ // if the first leaf is solid, set startsolid
+ if (t->trace->allsolid)
+ t->trace->startsolid = true;
+#if COLLISIONPARANOID >= 3
+ Con_Print("S");
+#endif
+ return HULLCHECKSTATE_SOLID;
}
-
- // calculate the true fraction
- t1 = DotProduct(t->trace->plane.normal, t->start) - t->trace->plane.dist;
- t2 = DotProduct(t->trace->plane.normal, t->end) - t->trace->plane.dist;
- midf = t1 / (t1 - t2);
- t->trace->realfraction = bound(0, midf, 1);
-
- // calculate the return fraction which is nudged off the surface a bit
- midf = (t1 - DIST_EPSILON) / (t1 - t2);
- t->trace->fraction = bound(0, midf, 1);
-
- if (collision_prefernudgedfraction.integer)
- t->trace->realfraction = t->trace->fraction;
-
+ else
+ {
+ t->trace->allsolid = false;
#if COLLISIONPARANOID >= 3
- Con_Print("D");
+ Con_Print("E");
#endif
- return HULLCHECKSTATE_DONE;
+ return HULLCHECKSTATE_EMPTY;
+ }
}
//#if COLLISIONPARANOID < 2
float front, back;
float mid, distz = endz - startz;
-loc0:
- if (!node->plane)
- return false; // didn't hit anything
-
- switch (node->plane->type)
+ while (node->plane)
{
- case PLANE_X:
- node = node->children[x < node->plane->dist];
- goto loc0;
- case PLANE_Y:
- node = node->children[y < node->plane->dist];
- goto loc0;
- case PLANE_Z:
- side = startz < node->plane->dist;
- if ((endz < node->plane->dist) == side)
- {
- node = node->children[side];
- goto loc0;
- }
- // found an intersection
- mid = node->plane->dist;
- break;
- default:
- back = front = x * node->plane->normal[0] + y * node->plane->normal[1];
- front += startz * node->plane->normal[2];
- back += endz * node->plane->normal[2];
- side = front < node->plane->dist;
- if ((back < node->plane->dist) == side)
- {
- node = node->children[side];
- goto loc0;
+ switch (node->plane->type)
+ {
+ case PLANE_X:
+ node = node->children[x < node->plane->dist];
+ continue; // loop back and process the new node
+ case PLANE_Y:
+ node = node->children[y < node->plane->dist];
+ continue; // loop back and process the new node
+ case PLANE_Z:
+ side = startz < node->plane->dist;
+ if ((endz < node->plane->dist) == side)
+ {
+ node = node->children[side];
+ continue; // loop back and process the new node
+ }
+ // found an intersection
+ mid = node->plane->dist;
+ break;
+ default:
+ back = front = x * node->plane->normal[0] + y * node->plane->normal[1];
+ front += startz * node->plane->normal[2];
+ back += endz * node->plane->normal[2];
+ side = front < node->plane->dist;
+ if ((back < node->plane->dist) == side)
+ {
+ node = node->children[side];
+ continue; // loop back and process the new node
+ }
+ // found an intersection
+ mid = startz + distz * (front - node->plane->dist) / (front - back);
+ break;
}
- // found an intersection
- mid = startz + distz * (front - node->plane->dist) / (front - back);
- break;
- }
- // go down front side
- if (node->children[side]->plane && Mod_Q1BSP_LightPoint_RecursiveBSPNode(model, ambientcolor, diffusecolor, diffusenormal, node->children[side], x, y, startz, mid))
- return true; // hit something
- else
- {
+ // go down front side
+ if (node->children[side]->plane && Mod_Q1BSP_LightPoint_RecursiveBSPNode(model, ambientcolor, diffusecolor, diffusenormal, node->children[side], x, y, startz, mid))
+ return true; // hit something
+
// check for impact on this node
if (node->numsurfaces)
{
node = node->children[side ^ 1];
startz = mid;
distz = endz - startz;
- goto loc0;
+ // loop back and process the new node
}
+
+ // did not hit anything
+ return false;
}
static void Mod_Q1BSP_LightPoint(dp_model_t *model, const vec3_t p, vec3_t ambientcolor, vec3_t diffusecolor, vec3_t diffusenormal)
t->trace->realfraction = midf;
// calculate the return fraction which is nudged off the surface a bit
- midf = (t1 - DIST_EPSILON) / (t1 - t2);
+ midf = (t1 - collision_impactnudge.value) / (t1 - t2);
t->trace->fraction = bound(0, midf, 1);
if (collision_prefernudgedfraction.integer)
node = bih->nodes + nodenum;
VectorCopy(nodestackline[nodestackpos], nodestart);
VectorCopy(nodestackline[nodestackpos] + 3, nodeend);
- sweepnodemins[0] = min(nodestart[0], nodeend[0]); sweepnodemins[1] = min(nodestart[1], nodeend[1]); sweepnodemins[2] = min(nodestart[2], nodeend[2]); sweepnodemaxs[0] = max(nodestart[0], nodeend[0]); sweepnodemaxs[1] = max(nodestart[1], nodeend[1]); sweepnodemaxs[2] = max(nodestart[2], nodeend[2]);
+ 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))
continue;
if (node->type <= BIH_SPLITZ && nodestackpos+2 <= 1024)
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]); sweepnodemins[1] = min(nodestart[1], nodeend[1]); sweepnodemins[2] = min(nodestart[2], nodeend[2]); sweepnodemaxs[0] = max(nodestart[0], nodeend[0]); sweepnodemaxs[1] = max(nodestart[1], nodeend[1]); sweepnodemaxs[2] = max(nodestart[2], nodeend[2]);
+ 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];
node = bih->nodes + nodenum;
VectorCopy(nodestackline[nodestackpos], nodestart);
VectorCopy(nodestackline[nodestackpos] + 3, nodeend);
- sweepnodemins[0] = min(nodestart[0], nodeend[0]) + mins[0]; sweepnodemins[1] = min(nodestart[1], nodeend[1]) + mins[1]; sweepnodemins[2] = min(nodestart[2], nodeend[2]) + mins[2]; sweepnodemaxs[0] = max(nodestart[0], nodeend[0]) + maxs[0]; sweepnodemaxs[1] = max(nodestart[1], nodeend[1]) + maxs[1]; sweepnodemaxs[2] = max(nodestart[2], nodeend[2]) + maxs[2];
+ 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)
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]; sweepnodemins[1] = min(nodestart[1], nodeend[1]) + mins[1]; sweepnodemins[2] = min(nodestart[2], nodeend[2]) + mins[2]; sweepnodemaxs[0] = max(nodestart[0], nodeend[0]) + maxs[0]; sweepnodemaxs[1] = max(nodestart[1], nodeend[1]) + maxs[1]; sweepnodemaxs[2] = max(nodestart[2], nodeend[2]) + maxs[2];
+ 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];
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]);
+ segmentmins[0] = min(start->mins[0], end->mins[0]) - 1;
+ segmentmins[1] = min(start->mins[1], end->mins[1]) - 1;
+ segmentmins[2] = min(start->mins[2], end->mins[2]) - 1;
+ segmentmaxs[0] = max(start->maxs[0], end->maxs[0]) + 1;
+ segmentmaxs[1] = max(start->maxs[1], end->maxs[1]) + 1;
+ segmentmaxs[2] = max(start->maxs[2], end->maxs[2]) + 1;
if (mod_collision_bih.integer)
Mod_CollisionBIH_TraceBrush(model, frameblend, skeleton, trace, start, end, hitsupercontentsmask);
else if (model->brush.submodel)