Hello,
I was just wondering if someone could briefely mention some of the more common types of contact/joint solvers (and what they are called) so that I can do some more research into each and figure out which one works the best. It seems to be a pretty big field, and there are alot of terms floating around; I just want to get them straight.
For example the two I am currently familiar with the box2d solver (I believe he calls it sequential impulse?) as well as position based dynamics. Are these just specific implementations of a more general method? What are some of the others called? (ex the one that ODE, or PhysX uses)
THanks,
Chris
Different types of solvers
-
Dirk Gregorius
- Posts: 861
- Joined: Sun Jul 03, 2005 4:06 pm
- Location: Kirkland, WA
Re: Different types of solvers
I think you need to distinguish between direct methods (e.g. Danzig, Lemke or Baraff) and iterative methods (e.g. sequential impulses or projected Gauss-Seidel). Then you can either solve your constrained dynamics problem on the acceleration level (e.g. Baraff), the velocity level (basically all game engines) or the position level (Jacobsen or Position Based Dynamics). It simply depends on how you formulate the problem. You need to understand that each holonome position constraint basically defines a velocity constraint and an acceleration constraint (sometimes called hidden constraints). Holonome just means that you can find the other constraints through derivation. Example:
If you want to constraint some particle to move on a circle you can formulate the constraint like this:
C(x) = x^2 - r^2 = 0
This also imposes that the velocity is always tangential to the circle (basically this requires that x and v are orthogonal - maybe you draw a quick sketch):
dC/dt = 2*x*v = 0
Examples for non-holonome constraints would be motors and friction. Finally note that in the literature inequality constraints are also called non-holonome. This is not consistent through all books I have read. So I stuck with the group that considers e.g. non-penetration constraints (contact) as holonome.
For rigid body dynamics PGS or SI on the velocity level is currently the common method. Most recently Erin Catto suggested post-projection instead of Baumgarte stabilization. Jan Bender takes a similar approach. The position projection is basically a second solver similar to the Jacobsen method and sometimes referred to as non-linear Gauss-Seidel. The difference is that solving on the velocity level is basically a linear problem while solving on the position level is not. The problem is that at each timestep all constraints on all levels need to be satisfied- not just one level. For games the position constraints are most crucial since you notice errors (e.g. separation at joints aka exploding ragdolls) very quickly. So Baumgarte treats this as one problem by combining velocity and position constraints. Post-projection treats both separately.
HTH,
-Dirk
If you want to constraint some particle to move on a circle you can formulate the constraint like this:
C(x) = x^2 - r^2 = 0
This also imposes that the velocity is always tangential to the circle (basically this requires that x and v are orthogonal - maybe you draw a quick sketch):
dC/dt = 2*x*v = 0
Examples for non-holonome constraints would be motors and friction. Finally note that in the literature inequality constraints are also called non-holonome. This is not consistent through all books I have read. So I stuck with the group that considers e.g. non-penetration constraints (contact) as holonome.
For rigid body dynamics PGS or SI on the velocity level is currently the common method. Most recently Erin Catto suggested post-projection instead of Baumgarte stabilization. Jan Bender takes a similar approach. The position projection is basically a second solver similar to the Jacobsen method and sometimes referred to as non-linear Gauss-Seidel. The difference is that solving on the velocity level is basically a linear problem while solving on the position level is not. The problem is that at each timestep all constraints on all levels need to be satisfied- not just one level. For games the position constraints are most crucial since you notice errors (e.g. separation at joints aka exploding ragdolls) very quickly. So Baumgarte treats this as one problem by combining velocity and position constraints. Post-projection treats both separately.
HTH,
-Dirk