# Physics Simulation Forum

 Page 1 of 1 [ 3 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: LCP solvers and nonpenetration CCDPosted: Sun Apr 02, 2006 10:30 pm

Joined: Sat Jan 14, 2006 8:32 pm
Posts: 6
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.

Top

 Post subject: Posted: Sun Apr 02, 2006 11:14 pm

Joined: Fri Jul 01, 2005 5:29 am
Posts: 324
Location: Irvine
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.

http://www.gphysics.com/gdc-2006/

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)+.

Top

 Post subject: Re: LCP solvers and nonpenetration CCDPosted: Wed Apr 05, 2006 11:53 pm

Joined: Fri Aug 12, 2005 3:47 pm
Posts: 117
Location: Newyork, USA
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.

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 3 posts ]

#### Who is online

Users browsing this forum: No registered users and 4 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ BULLET PHYSICS LIBRARY USERS    General Bullet Physics Support and Feedback    Release Announcements    Applications, Games, Demos or Movies using Bullet PHYSICS AUTHORING TOOLS, SERIALIZATION AND STANDARDS    Physics authoring tools, serialization, standards and related topics RESEARCH AND DEVELOPMENT IN COLLISION DETECTION & PHYSICS. Don't post Bullet support questions here!    Research and development discussion about Collision Detection and Physics Simulation    Links, Papers, Libraries, Demos, Movies, Comparisons       Non-technical forum and license/patent discussion    Career Opportunities