• Assume continuous collision detection
• When we find the time of impact, t, between any two objects, A, B, about to collide, there is a lot of rounding error built into t
• As such, if we advance physics simulation (which will have rounding error) by t, A and B may now be (1) Slightly overlapping (2) Exactly touching (3) Slightly separated.

Do we:

1. Advance physics by t - e for some small e (potentially will have issues for things like friction)
2. Remember what objects are in contact

Yes, generally we do t - e for some small e. The delicacy here is in how to apply e. e can be applied along the collision normal, or along the previous path the rigid body in question had traveled (in effect producing a "collision avoidance" rather than a collision "response"). Generally we will remember that bodies A and B had a time of impact via broad phase overlap, and store some state about the collision for the next simulation step.

If e is applied along the collision normal the resulting configuration may have body A (if we moved A along the normal by e) colliding with a new body C. At this point we should be comfortable assuming A and B are not colliding, but must now somehow deal with C. Some sub-stepping may be necessary to exhaust the rest of the timestep, and should be capped a maximum number of iterations.

After you compute a TOI you need to make sure to move the shapes 'close enough' such that the contact generation doesn't fail. E.g. the classical error is to advance the shapes to the determined TOI and when running the contact creation routine you end up an empty manifold. This will lead to the object tunneling out of the world even though you determined the correct TOI. In order to to handle this my contact creation routing considers shapes withing some margin touching and builds the manifold. I use an adjusted SAT which can handle small separations.

For me the major source of failure in the TOI computation using any form of conservative advancement was the GJK. If you run a GJK with some epsilon tolerance to support e.g. quadric shapes you run into a numerical nightmare with 32bit floating precision. So in Rubikon I only support spheres, capsules, hulls and meshes and the GJK implementation continues until it doesn't make any absolute progress getting me as close as possible. With this I haven't seen any numerical problems in practice. Note that spheres can be handled as points and capsules as segments and the radius is handled afterwards.

Erin's GJK and TOI actually address these problems, though they might not be explicitly mentioned here:

http://box2d.org/files/GDC2013/ErinCatto_GDC2013.zip

http://box2d.org/files/GDC2010/GDC2010_Catto_Erin_GJK.pdf

I gave a presentation a GDC on contact creating in general which might also be helpful:

http://media.steampowered.com/apps/valve/2015/DirkGregorius_Contacts.pdf

Finally I recommend studying the Box2D continuous physics solution. It addresses a lot of problems with continuous physics. You will find a great example of sub-stepping there as well which I didn't discuss in my answer here.

HTH,

-Dirk

@Randy Gaul

Are you applying this epsilon in space (not time)?

If so, if you only apply the epsilon to the colliding bodies (regardless if it's applied along trajectory, or along contact normal), you run the risk of producing a state where either body could be in contact with a third body.

Only if you apply the epsilon in time can you guarantee you won't produce any other contacts; however, choice of epsilon needs to account for speed of colliding objects (or cap max speed). Regardless, trying to maintain a consistent, separated world in this manner seems to be vulnerable to floating point inaccuracies.

@Dirk Gregorius

Very cool to hear from you! I just watched your 2013 GDC presentation: The SAT between Convex Polyhedra last week.

Thank you for linking your 2015 GDC presentation - seems to answer many questions I had. Hopefully I can respond intelligently after reading it :)

That being said, my initial question would be why not generate contacts at the same time as computing TOI (particularly if you are using SAT for TOI) ?

Thanks Dirk,

Zach

Here is how continuous physics works in a nutshell. We start with the general discrete solver step:

1) You integrate external forces (e.g. gravity)

2) You solve the joint and contact constraints

3) You integrate the velocities to find the new positions

Of course we might have tunneled right now. So in a continuous solver the new positions are tentative and we now enter the continuous part of the solver:

1) For each shape you build the swept AABB and add it into the broadphase.

2) For each contact you compute and cache the TOI

3) You advance the bodies to the minimum TOI, build the contacts and solve them

4) You invalidate the cached TOI for the involved bodies and recompute them

5) Repeat from 3) until you have reached the end of the timestep

I left out a lot of detail, but this is the general idea. Note that you still need to run the normal contact phase before entering the continuous phase.

So to answer you question. Yes, of course you need to compute the contact at each TOI.

HTH,

-Dirk