Bullet Constraint Solver Algorithm

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

Bullet Constraint Solver Algorithm

Post by CitizenSnips »

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 »

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: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA

Re: Bullet Constraint Solver Algorithm

Post by Erwin Coumans »

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