I've got an AABB vs triangle collision detection implementation, but I'm running into some precision issues.

When the AABB is moved I compute the time of impact (a float in the range 0.0 - 1.0) and lerp the AABB to that time. I then slide along the triangles sliding plane.

There are two things I'm noticing:

1. Precision issues with the time value. If this value is slightly too large, then it will let the AABB clip through the triangle.

2. Computing the slide vector by projecting the velocity onto the triangles plane sometimes produces a vector that isn't perfectly perpendicular with the triangle, thus collision is detected with the triangle being slid against causing the AABB to get "snagged" as its moving.

These issues are extremely difficult to reproduce but are more prevalent when the frame rate is uncapped and the delta time is extremely small. I could bump into a wall N times with collision and then have it break on the Nth + 1 time. I notice more precision issues against triangles with planes oriented in directions other then the primary axis e.g. (1, 0, 0), (0, 1, 0), (0, 0, 1) work fine.

What are some techniques for avoiding or correcting these issues and getting more deterministic behavior?

Also, what are good tips for debugging and unit testing these issues?

You could fix your timestep to make the simulation consistent.
http://gafferongames.com/game-physics/fix-your-timestep/

As for the precision issues, you just need to determine what range your floating point values should be in and clamp them to that range with a tolerenace. So your float in the range 0-1 could be clamped to 0-0.999999

You could fix your timestep to make the simulation consistent. http://gafferongames.com/game-physics/fix-your-timestep/

Doesn't running with vsync guarantee a fixed timestep? This seems to only solve for the case were vsync is off.

As for the precision issues, you just need to determine what range your floating point values should be in and clamp them to that range with a tolerenace. So your float in the range 0-1 could be clamped to 0-0.999999

I've been playing with precision/epsilons for a while now. I'm wondering if there is a better solution.

With floats, some tolerance of fuzziness is going to be necessary. A good rule of thumb is that floats have at best 7 digits worth of accuracy, and the bigger the numbers are the worse your precision. For our system it was sufficient to detect collisions when features were within one ten-thousandth of a meter from each other, and to resolve the collision we forced them to be at least three ten-thousandths meters apart.

Multiple collisions with the same triangle should generally be ok if your collision resolution math is correct. After the first collision you should be moving almost completely parallel to the triangle, so any velocity subtracted from a subsequent collision in the normal direction should be tiny.

Doesn't running with vsync guarantee a fixed timestep? This seems to only solve for the case were vsync is off.

No, it's not guaranteed. Frames can be skipped in a variety of situations. For example, the CPU of the device might not be able to keep the requested frame rate.

Video game engines typically have two different loops running at the same time:

• Fixed timestep loop. This runs at fixed timestep (i.e. 0.02 sec, which is 50 Hz). No frames are ever skipped in this loop, even under high CPU loads. In that case the game might slow down. The logic of the game should run here (physics, movements, decisions, etc), so the result will always be the same no matter the cpu load, vsync or refresh rate.
• Visual loop. This runs once per visual frame. Time step is variable here depending on the refesh rate. Frames might be skipped under heavy CPU load. All visual stuff, art stuff, and any "expendable" stuff should run here. The code here would take the current state (which is calculated in the fixed timestep loop) and update the visual entities accordingly. The point is that even if this loop is not running, the game would still run properly but without visual output (as the logic is executed in the fixed timestep loop).

As example, you can take a look at the execution flow of the Unity 3D engine here:

https://docs.unity3d.com/Manual/ExecutionOrder.html

(scroll down for the flow chart picture)

The fixed timestep loop is named "Physics" in the chart. The Visual loop is the rest of the loop below Physics. Note that the "Game Logic" label is not correct in that chart. I think this is a "legacy" definition, as in the beginning of Unity the game logic was typically developed in the visual loop.

Consider the following steps:

1. I check at the end of my collision logic to catch when the AABB is clipping through the triangle plane during the computed time of impact [1]. In this same check I also verify the original AABB position is NOT clipping. This is basically catching the tic when the computed TOI is allowing the AABB through the triangle plane.

2. When this tic is caught, I printf the AABB's initial position, target position, and computed TOI. I've also printf'd the triangles vertex coordinates.

3. I setup unit tests that call my collision handler with the exact same triangle vertices and AABB initial/target positions. I'm getting back the same TOI and AABB position, but now it does not clip through the plane.

[1] I determine if the AABB is clipping through the plane by checking if there are vertices of the AABB behind the plane.

This makes no sense to me. Given the same input, I would have expected the same output. I suspect printf might be rounding the floats which means my input isn't exactly the same. I'm not sure whats going on here. I'm just using the %f format option.

I'd love to hear other debugging strategies.

EDIT: I've edited the original contents of this post.

there are two basic ways to handle collisions:

1. move everything fully, check for collisions, then backsolve to fix things.

2. stepped movement for fast objects.

stepped movement makes all these backsolve issues go away.

1. move everything fully, check for collisions, then backsolve to fix things.

2. stepped movement for fast objects.

I assume you mean 1. continuous motion versus 2. discrete motion? I'm currently using continuous motion to detect collision and avoid tunneling. Could you elaborate on backsolving?

My issue is the computed TOI seems to have occasional precision issues which cause the AABB to be lerped to a time where it actually clips through the surface it should collide against.

Also, I did manage to finally reproduce a precision issue in a unit test. I was very close when I made my prior post about it. I had one value slightly off. I currently "solved" the issue by subtracting a small epsilon from the TOI, but I'd still like to get more feedback on this topic.

Printf formatting will definitely cause you to flip a bit or two. You might consider reinterpret_casting the memory to print it as a uint32 in hex, assuming you can't just dump the binary value directly. The TOC calculation will never be perfect with floats, and you need an epsilon to handle the fact that you might not be absolutely perfectly coplanar at that point in time (this gets worse when you have a more involved toc calculation, like finding the roots of a cubic). Resolution also definitely needs an epsilon, because otherwise your velocity or even just final position can again be off enough from coplanar that you end up on the wrong side.

Using cubics with a collision epsilon we discovered that you need to test both the computed continuous TOCs and at a TOC of 1.0, because the cubic on the next timestep could be different enough that it ends up reporting a collision at 0.0 when the previous timestep didn't find one. A collision at 1.0 can still be solved without issue by moving the ending position to be epsilon above the collision plane in the normal direction (there's just no time left in the step to keep sliding). However a collision at 0.0 can never be solved because during the step your starting location never changes - just where you end up. If you start out colliding, no resolution of your endpoint will change that fact.

If you are extremely turned off by introducing epsilons, CGAL (http://www.cgal.org/exact.html) takes the philosophy that geometry calculations should be exact, and has algorithms for continuing to zoom in on a problem until it can provide a solution with 100% accuracy. Obviously this will never be as cheap as just computing with floats, but if you are interested in the topic it might be worth researching.