CA and numerical integration and root finding

[Erin Catto]

1. When you detect a mid-frame collision, do you advance/regress the entire simulation back to the time of impact? That's my biggest gripe with most continuous collision response methods (or my understanding of most continuous collision response methods, at least), since the problem has such a highly localized nature.

TOI events are handled locally. I only advance the TOI island to the time of impact. After the TOI island is solved, I proceed to update any invalid TOI pairs as I search for the new minimum TOI. As part of this search, some bodies may be advanced so that both bodies are swept over the same time interval.

For example, body1 is in the TOI = 0.5 island. After the TOI:0.5 island is solved, body1 has a new sweep from t=0.5 to t=1.0. Now suppose body6 was not in any TOI island yet, so it's sweep is t=0.0 to 1.0. The broad-phase indicates that the sweep of body1 and body6 overlap, so now I want to perform CCD on the body1-body6 pair. I know that body6 is safe until t=0.5, so I advance it and then perform CCD from t=0.5 to 1.0. As you can see, body6 only needs to be advanced to t=0.5 on demand. Suppose body3 was never in a TOI island. It's sweep would remain from t=0.0 to 1.0 until the end of the simulation, where it is finally advanced to t=1.0 (along with all other bodies).

2. Are your results deterministic independent of the order that the bodies are resolved? That is, are you actually resolving the collisions in the order that they happen to arrive at the "correct" motion?

Yes, I process the minimum TOI event. Most time steps have no TOI events. I work with shrunken shapes for CCD and most dynamic-dynamic contact doesn't use CCD.

Box2D's continuous physics handles fast translations+rotations and limited dynamic-dynamic CCD with good results. All dynamic-static ineractions are continuous to prevent tunnelling through the environment. Some cases still fail: make an enclosed static region with hyper-elastic walls (say restitution = 1.4). Now put a dynamic hollow box in that room. The box will bounce around wildly in that room until it reaches my velocity caps (~mach1). The box will not tunnel. However, I put a ball inside that box, eventually the ball will tunnel outside of the box (yet remain inside the static region). I believe this shortcoming to be related to linearization of rotational motion. For example, the velocity of a pendulum is tangent, yet it moves inward.

[Numsgil]

Box2D's continuous physics handles fast translations+rotations and limited dynamic-dynamic CCD with good results. All dynamic-static ineractions are continuous to prevent tunnelling through the environment. Some cases still fail: make an enclosed static region with hyper-elastic walls (say restitution = 1.4). Now put a dynamic hollow box in that room. The box will bounce around wildly in that room until it reaches my velocity caps (~mach1). The box will not tunnel. However, I put a ball inside that box, eventually the ball will tunnel outside of the box (yet remain inside the static region). I believe this shortcoming to be related to linearization of rotational motion. For example, the velocity of a pendulum is tangent, yet it moves inward.

I have another question related to this. It's the one pathological case I'm having a hard time resolving. Suppose you had a very large sphere, with a smaller sphere on top of it placed so that it will roll (instead of slide) down the larger sphere and eventually fall of. As far as I can tell, it can't be resolved as a series of discrete collisions. After any arbitrarily small delta t, the collision normal, and thus the force, has changed.

You could of course simplify the system with a gear joint or something, but that doesn't help the case when you have several hundred spheres bouncing around in an enclosed volume with gravity.

[ewjordan]

However, I put a ball inside that box, eventually the ball will tunnel outside of the box (yet remain inside the static region). I believe this shortcoming to be related to linearization of rotational motion. For example, the velocity of a pendulum is tangent, yet it moves inward.

There could also be a swept AABB issue - a toothpick aligned with the x-axis and rotating quickly enough so that it spins a full 180 degrees in a frame will have a swept AABB that is far too thin in the y-direction, and you could conceivably miss some collisions that way.

Suppose you had a very large sphere, with a smaller sphere on top of it placed so that it will roll (instead of slide) down the larger sphere and eventually fall of. As far as I can tell, it can't be resolved as a series of discrete collisions. After any arbitrarily small delta t, the collision normal, and thus the force, has changed.

In Box2d's case, this is a non-issue, because you're not even "in CCD mode" when solving that situation, you're in "normal" mode, where you just have a persistent contact point that goes in to the usual contact solver.

The CCD and normal collision systems play distinct roles, and rely on each other. The CCD's only job is to check through all the TOIs by using swept and shrunken core shapes, and then step the islands just far enough so that the core shapes are almost touching. At that point, the true unshrunken shapes should actually be overlapping, so you invoke the normal contact solver to resolve the collision. Once the constraint is satisfied, control passes back to the CCD handler, and we repeat.

But this is very dependent on the usual overlap-based approach to collision handling, and it ultimately falls back on it - Box2d started out without CCD, and its addition was really just a few hundred extra lines of code, which tells you how well CCD leverages the pre-CCD code to do its thing.

Apart from that stuff, don't get too bent out of shape about tiny changes in certain values over a time step. Those are unavoidable unless you can explicitly solve your system, and most realistic systems are very resistant to analytical solution.

[Numsgil]

However, I put a ball inside that box, eventually the ball will tunnel outside of the box (yet remain inside the static region). I believe this shortcoming to be related to linearization of rotational motion. For example, the velocity of a pendulum is tangent, yet it moves inward.

There could also be a swept AABB issue - a toothpick aligned with the x-axis and rotating quickly enough so that it spins a full 180 degrees in a frame will have a swept AABB that is far too thin in the y-direction, and you could conceivably miss some collisions that way.

Suppose you had a very large sphere, with a smaller sphere on top of it placed so that it will roll (instead of slide) down the larger sphere and eventually fall of. As far as I can tell, it can't be resolved as a series of discrete collisions. After any arbitrarily small delta t, the collision normal, and thus the force, has changed.

In Box2d's case, this is a non-issue, because you're not even "in CCD mode" when solving that situation, you're in "normal" mode, where you just have a persistent contact point that goes in to the usual contact solver.

The CCD and normal collision systems play distinct roles, and rely on each other. The CCD's only job is to check through all the TOIs by using swept and shrunken core shapes, and then step the islands just far enough so that the core shapes are almost touching. At that point, the true unshrunken shapes should actually be overlapping, so you invoke the normal contact solver to resolve the collision. Once the constraint is satisfied, control passes back to the CCD handler, and we repeat.

But this is very dependent on the usual overlap-based approach to collision handling, and it ultimately falls back on it - Box2d started out without CCD, and its addition was really just a few hundred extra lines of code, which tells you how well CCD leverages the pre-CCD code to do its thing.

Apart from that stuff, don't get too bent out of shape about tiny changes in certain values over a time step. Those are unavoidable unless you can explicitly solve your system, and most realistic systems are very resistant to analytical solution.

That's sort of what I figured. I'd like to build a response system that relies on bodies exactly colliding (my primary idea being that it will allow for more robust stacking behavior, since you can immediately create a static contact joint between two boxes in the stack as soon as you resolve their relative velocity to 0. If you never interpenetrate, you can never create instabilities that will topple the stack (minus machine accuracy issues of course)). The whole system hinges on the idea that after you resolve an island you can move the time step forward some finite, non zero amount safely. The sphere-on-sphere issue would seem to violate that basic assumption. I guess Box2D doesn't have any clever way of resolving that beyond just allowing some penetration and going from there.

At present I might just cheat and say that circles are actually hexagons or octagons or something like that.