LCP solvers and nonpenetration CCD

Please don't post Bullet support questions here, use the above forums instead.
Post Reply
Posts: 6
Joined: Sat Jan 14, 2006 8:32 pm

LCP solvers and nonpenetration CCD

Post by michael » Sun Apr 02, 2006 10:30 pm

Hello all,

I've implemented continuous collision detection that allows no interpenetration (based on Redon's method). Currenly I'm using an impulse based approach to handle simultaneous collisions (resting contacts are handled as microcollisions). I'd like to move to some analytical form of LCP solver.

I tried understanding how to use PGS, from Erin Catto's paper ("Iterative Dynamics with Temporal Coherence") but ran into trouble:

1. I don't see any mentioning of the coefficient of restitution. Instead, I see "The velocity constraint is augmented with a feedback term proportional to the penetration depth". What should I do when there is never any interpenetration? I know I could use the separation distance, but isn't there a way to do it without taking any distance into account?

2. In Erin's paper, the big matrix equation which is solved using PGS has the term "delta t" in it. If I understand correctly, this means the solver solves through time. In my simulator I don't know "delta t" when I need to resolve the simultaneous collisions. Can I use PGS to compute the impulses that need to be applied at a specific instant in time? (not over some time interval)

3. Is there a way to implement friction with real "weight feeling" with PGS? In a box stack I'd like lower boxes to have stronger friction compared to higher boxes. (I've read about this in another thread but couldn't find an answer there)

4. Is there another LCP solver method which is more suitable for my configuration? I assumed any LCP solver could be used, but I'm very inexperienced as you know and may be terribly confused. Any hints will be highly appreciated.
Redon says he uses the method from Baraff 94 - should I conclude that this method is preferable for me? (applied to impulses and velocities instead of forces and accelerations)
In any case, I'd be grateful if you could point me to some paper explaining PGS or other solver methods, if you know of any.

5. Baraff mentions the need for an incremental matrix factorization routine, in order to solve some A11x = -v1 equation in his paper. I wonder what routines are most common nowadays (LU decomposition or something else?).

Thanks and sorry again for the long posts.

Erin Catto
Posts: 324
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine

Post by Erin Catto » Sun Apr 02, 2006 11:14 pm

I'm now recommending a sequential impulse algorithm over the PGS algorithm. While these two algorithms give similar results, it is conceptually simpler to implement sequential impulses.

Download slides and code here:

Within the slides, I show how to include weight feeling friction. Also, deltaT is not needed for the impulse calculations.

Caveat: If you don't plan to allow penetration, you must at least have a slop region. Otherwise you will end up cutting your time-step extremely small. My opinion is that CCD should be used to prevent tunneling, but should not be used for objects that are already touching.

You can achieve restitution by simply augmenting the bias velocity (mentioned in the slides) with a restitution term.

Now if you really want an accurate simulation you will have to implement an O(n^3)+ LCP solver (see Mihai Anitescu's work). If you can use the normal force from the previous step for friction, you might consider using a conjugate gradient algorithm like GPCG, which is O(n)+.

Posts: 117
Joined: Fri Aug 12, 2005 3:47 pm
Location: Newyork, USA

Re: LCP solvers and nonpenetration CCD

Post by ngbinh » Wed Apr 05, 2006 11:53 pm

michael wrote: I've implemented continuous collision detection that allows no interpenetration (based on Redon's method). .
Could you accomplish that?
Right now the only way to 95% avoid intepenetration is backing up and step ahead with smaller time step. But as Erin said, for complex scene, you will get so small step that your system cannot advance in time.
The Stewart-Trinkle time stepper prevent says 80% of interpenetrations with polygonal objects and guarantee that the system always advance.
We'll see how good is it compare to usual Anitescu-Potra time stepper.

Post Reply