Continuous Collision Detection: which method?

[xissburg]

Hi. I'm going to do my physics engine but I need to do CCD for my system to work properly, but I don't know how. I've read some papers about the topic but I couldn't fully understand them. . . I'm coming here to ask for you, experienced guys, what is best CCD method for realtime applications nowadays and a clear explanation or a link to a paper/article. Please Thanks

[Numsgil]

I believe Bullet uses "conservative advancement". Box2D uses it as well. I believe this is the paper where the idea was layed out.

[xissburg]

Hah! What does this paper has to do with CCD or CA? I don't see anything related and I don't want to reinvent the wheel...

[Dirk Gregorius]

The idea comes from the PhD of B. Mirtich.

[Numsgil]

Oops, wrong link Been reading too many thesises (thesi?)

This is the link you want.

[xissburg]

Thanks. I read that and I think I understood but, is that an iterative algorithm? Or I just solve for t in the last equation at page 34 and get the TOI? Is there anything else I need to do? The explanation in that thesis is somewhat poor in my opinion...or I'm and idiot

[Numsgil]

It's an iterative algorithm. It's doing a conservative numerical root finding on the time of impact.

[xissburg]

And when should I stop? When the distance between the bodies is below some small tolerance?

[Erwin Coumans]

Please read the FAST paper and CATCH paper for more details on CA, time of impact calculation. Gino van den Bergen also released a ray / convex cast paper, restricted to linear motion. It includes some optimizations by merging the iteration loop with the GJK closest distance iteration loop. This, and versions that include angular motion are implemented in Bullet.

There are several termination conditions, one of them if the distance between objects falls below a given threshold. Another one is if the projected relative motion onto the separating normal becomes positive. This means objects move away from eachother. A maximum iteration count is another termination condition, but keep in mind that typically only 2-4 iterations are needed.

Hope this helps,
Erwin

[RobW]

What about objects which are in contact at time zero? I think that objects with angular velocity could still rotate into deep penetration, especially if the contact manifold is built incrementally.

It seems to me that "time of deep penetration" is as important as "time of impact", perhaps more important, if we want to permit shallow penetration (which I think is a very good decision, for games at least ). Do any of the CCD algorithms deal with this?

Rob

[raigan2]

@Rob: AFAIK Box2D does this by using shrunken shapes for CCD.

[xissburg]

Another one is if the projected relative motion onto the separating normal becomes positive. This means objects move away from eachother.

Would this mean that the bodies will not collide?

Another question: what distance computation method should I use? GJK? And what about that GJK-LinCanny Mixing? Could you briefly explain me (or point me to somewhere with the explanation) how Bullet performs this?

Thanks.