speculative contacts

[raigan2]

[this posting was split from Newton's Cradle thread]

I would actually like to put contacts into the LCP solver before they even become contacts. That helps the bullet-through-paper problem. Kind of a speculative contact.

This is how our solver works; there are a few papers describing Steward-Trinkle/Anitescu-Potra solvers which also do this, for instance: http://www.cs.rpi.edu/~trink/Papers/EBTtr03.pdf

What we do is wrap shapes in AABBs which enclose their current and predicted positions, and then generate constraints for any shapes whose AABBs overlap; this could also be seen as similar to Guendelman, using a predicted/future position to collect collision info.

The two biggest downsides for us is that (1) you end up with more constraints to solve, (2) narrow/sharp features (acute convex corners) which are rotating quickly can cause fly-through -- this may simply be due to our method of extrapolating/collecting future collisions though (the AABBs don't really model the path of the objects perfectly).

Still, it's pretty awesome in that you get really solid collision using only static tests, without having to resort to a complex event-scheduling problem as with real CCD; the simplicity of "move everything forward, then solve everything" is nice.

[bone]

I would actually like to put contacts into the LCP solver before they even become contacts. That helps the bullet-through-paper problem. Kind of a speculative contact.

This is how our solver works; there are a few papers describing Steward-Trinkle/Anitescu-Potra solvers which also do this, for instance: http://www.cs.rpi.edu/~trink/Papers/EBTtr03.pdf

What we do is wrap shapes in AABBs which enclose their current and predicted positions, and then generate constraints for any shapes whose AABBs overlap; this could also be seen as similar to Guendelman, using a predicted/future position to collect collision info.

The two biggest downsides for us is that (1) you end up with more constraints to solve, (2) narrow/sharp features (acute convex corners) which are rotating quickly can cause fly-through -- this may simply be due to our method of extrapolating/collecting future collisions though (the AABBs don't really model the path of the objects perfectly).

Do you deal at all with predictions that turned out to be wrong, in other words your object moved out of the predicted AABB after all? For example, a box sitting on the ground next to a wall might be predicted to just sit there, but then I crash into it with a fast-moving vehicle and it's suddenly flying through the wall. Or do you just make the AABB big enough to handle any such case that might come up in your game?

[raigan2]

Definitely the problem you mention could happen, so far it hasn't come up -- if you had very heavy and fast objects this could definitely happen though, since such objects are capable of pushing lighter things fairly far in a single iteration.

We inflate the AABBs by a certain amount so that any "nearby" shapes are added, this was necessary since our solver is position-based, and thus things move around during each iteration. We don't check to make sure things have stayed in their predicted AABBs, but that's a great idea! Increasing the inflation amount of the AABBs based on the mass of the objects just occurred to me -- the inflated AABB is the predicted neighborhood of the object, and lighter objects are less predictable since they're easier to move around during the solve.

The proper solution would be to run full collision detection at each iteration; this is the biggest problem with position-based stuff.. jacobians, proximity queries, etc all change per-iteration. Adding "speculative constraints" was just an optimization that let us only run broadphase (rebuild AABBs and update grid) once.