Bullet Constraint Solver Algorithm

Post Reply
CitizenSnips
Posts: 1
Joined: Mon Mar 14, 2011 9:04 pm

Bullet Constraint Solver Algorithm

Post by CitizenSnips » Mon Mar 14, 2011 9:39 pm

Hi all!

I am a student trying to measure the number of cycles spent in the constraint solver in Bullet. I've downloaded and compiled the code (on Ubuntu 10.04) and I can run the test programs; but since I'm still learning about physics engines, I am having trouble reading the source code and understanding what's going on. I am looking through the sequentialImpulseConstraintSolver code; but I am confused about which algorithm it is implementing. Specifically, is it implementing the Gauss-Seidel method? What is different between that and "projected" Gauss-Seidel? Is there a paper or set of papers I could read that explain the algorithm Bullet is implementing?

Admittedly I am still learning about physics engines. I have a physics background so I understand the concept of the Euler-Lagrange equations (and solving those in matrix form). However, just from reading the source code I am having a hard time seeing what's going on.

Any help or nudges would certainly be greatly appreciated.

Cheers!

leromi
Posts: 6
Joined: Thu Oct 07, 2010 8:27 pm

Re: Bullet Constraint Solver Algorithm

Post by leromi » Thu Mar 17, 2011 3:36 pm

sequentialImpulseConstraintSolver implements Sequential Impulse method, which is matrix-free formulation of projected Gauss-Seidel.
http://code.google.com/p/box2d/downloads/list
download GDC2009_ErinCatto.zip for more information on SI.
Also Catto's "Iterative Dynamics with Temporal Coherence" explains difference between Gauss-Seidel and projected Gauss-Seidel.

User avatar
Erwin Coumans
Site Admin
Posts: 4198
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Bullet Constraint Solver Algorithm

Post by Erwin Coumans » Thu Mar 17, 2011 11:27 pm

Kenny Erleben's PhD thesis also describes the iterative constraint solving method, known as projected gauss seidel (PGS) or sequential impulse as Erin Catto calls it.

See Chapter 6, you can download it here: ftp://ftp.diku.dk/diku/image/publicatio ... 050401.pdf
Kenny's PhD thesis is also listed in the resource topic here: http://bulletphysics.org/Bullet/phpBB3/ ... p?f=6&t=63

xThanks,
Erwin

Post Reply