This post is Part 1 of 3 about Metareal’s collision subsystem.

Building my own engine is deeply satisfying. But it is iterative, to be sure. This will be the third major overhaul of the collision system. Might be the last, we’ll see. Where were we…

Move-Then-Fix: A Failed Approach

Back here is a description of a first pass at collision management. Basically, it does these steps:

• Move the thing where the thing thinks it’s going
• Look at any intersections
• Try to do some more movement to get out of intersections
• Some secret sauce to move the least, but also not get snagged on seams, and stuff like that

It worked just enough to fool me. But had problems. Here’s one. When moving into a narrow space, but more “into” than “across”:

The minimal intersection-fix is also illegal, and would lead to a metastable vibration:

In some cases it’d just get stuck in walls. Maybe with further analysis it could undo more of the move, but it’s no longer so simple as “Move and then fix.” It also didn’t support “pushing” in any obvious way. So came up with a whole new approach.

Recursive Intersection Testing

When an object A moves distance d in the X-axis, one of four things will happen:

1. It will move the entire distance without bumping into anything
2. It will bump into something it cannot push, and stop
3. It will bump into object B that it can push, and might continue pushing it

In case 3, then object B must be tested for however far A might push it. This is implemented recursively. And it is performed independently for each axis of motion.

Here’s an example. A moves 4 units to the right, so it’s going to bump into B and C. Also, B will hit a wall.

The analysis descends like so:

• A wants to move 4 units right. How far can you move, A?
• A sees intersections first with C (1 unit away) and then B (2 units away)
• Recurse. C wants to move 3 units right. How far can you move, C?
• C has no intersections within 3 units. I can move all 3 units!
• Recurse. B wants to move 2 units right. How far can you move, B?
• B hits a wall in 1 unit. I can move 1 unit right.
• We know that A can move 3 units to the right (distance to B is 2, plus how far B can move).

After this analysis, we simply move A 3 units right, and each of the previously analyzed intersections moves by what’s left.

And this is done for delta X, delta Y, and delta Z. Doing these axes separately completely eliminates any possibility of entering a shaft too narrow for the object.

The Bullet Problem

Problem: If an object is moving quickly, its proposed position could be on the other side of a wall, with no intersection.

Solution: Move only the leading edge. That is, check for intersections of the swept volume.

The actual test is simply: Does the leading edge start out before the closest edge of the obstacle, and end after the obstacle. In the implementation there’s plenty of cruft relating to positive- or negative-motion, to check which edges are moved, which are compared against, and so on.

---

That’s enough for this post. Part 2 will discuss diagonal movement and roundoff errors. Part 3 will describe collision objects more complex than “A Box”.