# Identifying the wall of impact during BSP traversal

I'm building a 2D BSP based physics game and am having trouble implementing what might seem like an easy feature. I'm using Gamemaker as the basis for this project.

## Basic Info and Point of Impact Finding

Identifying the point of impact using a BSP traversal algorithm is relatively simple. What I'm trying to identify is which wall the segment collided with. This is not only to gather the correct surface information used in collision resolution, but also to invoke that surface's method for being impacted (play the right sound, enter a door, etc).

Each node stores its wall in a struct variable called split, which contains its two points, its normal, and any other relevant information about the wall. During construction, these walls are used to split the other walls and distribute them to either the front or back subtree, hence the name. Colinear walls are handled as such: If it faces our split, send it to our front. Otherwise, send it to the back.

Leaf nodes have a split of int -1 for empty and -2 for solid. This is checked as the base case for the traversal algorithm (GML is dynamically typed).

All nodes are stored in an array with their index being used as their address in memory. A node's children are stored using the integer variables frontChild and backChild.

I will not be covering the details on how BSP traversal is typically performed. This can easily be found online and I haven't done anything out of the ordinary to my knowledge so far. Finding the point of impact works well, and I've accounted for floating point errors using an epsilon value.

function bspTestSegment(p1, p2, w, ind=0)
{
//Returns where (if at all) a given segment intersects with the bsp walls, along with the
//wall itself.

var n = cWorld.bsp[? room][ind]

//If we've hit a leaf node, return the result.
if n.split == -1
{
//Empty node.
return 0
}
if n.split == -2
{
//Solid node. Return point of impact.
return p1
}

//Get our dot products.
var d1 = p1.sub(n.split.p1).dot(n.split.normal)
var d2 = p2.sub(n.split.p1).dot(n.split.normal)

//If we're only on one side of the splitting line, just send us to that subtree.
if d1 >= -EPSILON and d2 >= -EPSILON
{
return bspTestSegment(p1, p2, w, n.frontChild)
}
if d1 < -EPSILON and d2 < -EPSILON
{
return bspTestSegment(p1, p2, w, n.backChild)
}

//We know we're straddling the line, so split our wall.
var seg = bspSplitWallsTest(p1, p2, n.split.p1, n.split.p2)

//Find which direction relative to the wall we're headed. If we're headed toward the
//wall, send us to its front child first.
if d1 >= -EPSILON
{
//Claim the wall of impact.
w[P] = n.split

//Test the front child.
var hit = bspTestSegment(seg[0], seg[1], w, n.frontChild)

//If we hit something, return where.
if hit != 0
{
return hit
}

//Otherwise, test the backchild.
return bspTestSegment(seg[1], seg[2], w, n.backChild)
}
//Otherwise send us to its backchild first.
else
{
var hit = bspTestSegment(seg[0], seg[1], w, n.backChild)

//If we hit something, return where.
if hit != 0
{
return hit
}

//Otherwise, test the frontchild.
return bspTestSegment(seg[1], seg[2], w, n.frontChild)
}
}


Collision resolution also works well, granted we have the correct wall of impact.

## Wall of Impact Finding

The issue is in identifying which wall was the first along the segment to be impacted. The simplest possible approach is to pass a pointer w (GML doesn't have proper pointers so I use an array) to the traversal function, and whenever a split is straddled while the segment is heading toward it, that node overrides the pointer with its split (wall). Therefore, the lowest node on the tree that the segment ran head-first into will claim the impact as its own, and assign its split (wall) to the pointer. This works for most cases.

The issue is when a node claims the wall of impact as its own, and is then overridden by a node in its rear sub-tree. The segment will be split by the correct node, but a node behind it will end up satisfying both conditions (segment is heading towards and straddling) and override the pointer incorrectly.

## Attempted Solutions

If a segment intersects the BSP, the point of impact is guaranteed to be the starting point of the segment that reaches a solid node. A solid node is only reached when a segment is straddling a wall. When a segment is straddling a wall, the segment is split, and the sub-segment between its midpoint and endpoint is the one sent to the solid leaf (granted it's headed toward the node that split it). Therefore, we can guarantee that the point of impact is the midpoint of some node's split segment. Logically, this midpoint is going to belong to the correct wall of impact.

If a node splits the segment (again, while the segment is headed toward it), we consider it a potential candidate for the wall of impact. Once we've reached a solid leaf, we can then walk back up the tree and compare this point of impact with every candidate's midpoint. Only the one that matches (or is within epsilon distance of) the point of impact will claim the wall of impact.

This would be inside the "heading toward the wall" block:

//Otherwise, test the backchild.
hit = bspTestSegment(seg[1], seg[2], w, n.backChild)

//Override the wall of impact if we're the one that split the colliding segment.
if hit != 0 and hit.sub(seg[1]).lenSqr() < 1
{
w[P] = n.split
}

return hit


(note: I have my own vector constructor. hit, seg[0-2], p1, and p2 are all 2D vectors. the method lenSqr() returns the vector's squared magnitude for distance comparisons.)

This works, but then creates a new issue. If a rear descendant is colinear with a node, the descendant's rightful claim to the wall will be overridden by its ancestor node on the walk back up.

Another attempt had me building the tree such that any colinear wall was passed down to the front sub-tree. Then, during traversal, in the case where our segment lies entirely in front of the split, I allowed it to claim the wall if the endpoint of the segment was colinear with it. This fails as not only is it possible for a front descendant to be colinear and entirely elsewhere, it's also claimed while walking down the tree, meaning the previously implemented walk back up overrides it.

I can't find research as to how this specific part of the traversal is handled and yet I know it is because many BSP based engines handle this just fine. If anyone can help or point me to a good resource I'd be more than a little grateful. Thank you so much for reading...

• Welcome to GDSE. Please edit to include your images directly in your question & please include your code as formatted text, rather than images. Jan 9 at 2:03

I figured it out. It was similar to my first attempted solution, but slightly more robust.

//Otherwise, test the backchild.
hit = bspTestSegment(seg[1], seg[2], n.backChild)

//Override the wall of impact if the point of impact is colinear and within the
//bounds of our wall.
if hit != 0
{
if hit[0].sub(n.split.p1).dot(n.split.vunit) >= 0 and
hit[0].sub(n.split.p2).dot(n.split.vunit) <= 0 and
hit[0].sub(n.split.p1).dot(n.split.normal) >= 0
{
hit[1] = n.split
}
}

return hit


The above section of code is in the same place as the first failed solution. While going back up the tree, instead of overriding the wall when our midpoint of the split segment matches the point of impact (which failed because that wasn't necessarily touching the wall), we simply ensure that the point of impact runs along the wall itself, and is between our wall's start split.p1 and end split.p2 points.

To do this, we simply take the line of the wall itself (here it's called vunit) and get its dot product with the point of impact relative to the start and endpoints of the wall (conditions 1 and 2). Then all that's left is to make sure it's colinear and we're done! (condition 3).

The reason this works is that we're basically ensuring that the point of impact lies along the line segment rather than just the line. In fact, the first wall to claim the impact will never be overridden, so it's possible to make this even more efficient by not running these tests after one does.

Since we're only overriding the wall while walking back up the tree, we don't even need to pass a pointer for the wall to each recursive call. Here I simply returned the point of impact in hit[0] and the wall of impact in hit[1]. Just be sure that, at the solid base case, you return [p1, <empty_wall_struct>] instead of just p1 to ensure that the game doesn't crash when you have a point of impact but no wall (when the object is outside of the map, for example).

: y