Impulse-based dynamic simulation library (IBDS)

Jan Bender · Post by **Jan Bender** » Fri Jul 06, 2007 2:35 pm

Hi,

after much work the first version of my impulse-based dynamic simulation library called IBDS is online:

http://www.impulse-based.de

The impulse-based dynamic simulation is a new method for the simulation of articulated rigid body systems that I have developed during my PhD. It can handle all kinds of joints, velocity constraints, collisions and contacts with friction. The iterative method even can handle models with loops. The methods described in "Fast Dynamic Simulation of Multi-Body Systems Using Impulses" and "Impulse-based dynamic simulation in linear time" are not yet integrated into the library but they will soon follow.

At the moment I just provide project files for VS2005 and VS2003. If you need files for Linux or Mac OS then either wait a bit or make them by your own and send them to me

Jan

KenB · Post by **KenB** » Sun Jul 08, 2007 2:37 pm

I haven't had time to read your papers yet, but I will eventually.
Could you just give a brief explanation of the difference between your work and the the relaxed projected Gauss-Seidel type of solvers the everyone else is using (and which is also often referred to as an impulse-based solver since if solves for velocities).

Jan Bender · Post by **Jan Bender** » Mon Jul 09, 2007 7:33 am

Hi,

I haven't had time to read your papers yet, but I will eventually.

You should do this

Could you just give a brief explanation of the difference between your work and the the relaxed projected Gauss-Seidel type of solvers the everyone else is using (and which is also often referred to as an impulse-based solver since if solves for velocities).

Everyone else? I even know some guys who use Lagrange multipliers or reduced coordinates

I don't know much about the relaxed projected Gauss-Seidel solvers. So I can only tell you how my method works. We develop the impulse-based dynamic simulation method since the year 2000 at the institute. First it was only developed for mass point systems and later for rigid bodies. One of the goals was to get an exact method for dynamic simulation. Later we found out that the method is very fast and flexible so it is also suitable for games.

For the simulation of joints the main idea is to use a prediction of the joint state in order to compute a correction impulse. With this prediction you can determine the future error that would occur if the bodies have a ballistic motion. The same idea is used many years later by Rachel Weinstein in her paper "Dynamic Simulation of Articulated Rigid Bodies with Contact and Collision". In contrast to her paper I don't solve a nonlinear equation by Newton iteration. Since the relative motion of the bodies is almost linear I use a linearization of the equation. By this linearization I get a good approximation of the correction impulse. The impulse is then computed in an iterative loop to get an exact result. At the moment a student of mine is comparing Weinstein's and my method. The speed should be the same but the linearization of the problem has several advantages. The method of Weinstein seems to have problems with singular matrices when using to small time steps. With my method it is guaranteed that the matrices are regular. Another advantage is that I can compute all impulses at once using a system of linear equations. This system describes all dependencies between the joints. The system can even be solved in linear time if there are no loops in the model. So I was able to simulate a tree model with 255 ball joints (the corresponding SLE has a dimension of 765) almost three times faster than real-time with a high degree of accuracy (on my Pentium 4 with 3.4 GHz). The method can handle all kinds of position and velocity constraints.

Since a resting contact defines a position constraint and a collision a velocity constraint I was able to use nearly the same method for collision and contact handling with friction.

At the moment I just work on the simulation of deformable bodies. The first results of my cloth simulation are already online.

The results you can see in the videos on my web page.

Hope that helps,

Jan

Antonio Martini · Post by **Antonio Martini** » Mon Jul 09, 2007 7:12 pm

Jan Bender wrote:I don't know much about the relaxed projected Gauss-Seidel solvers. So I can only tell you how my method works.

a claim of having developed a new algorithm in the field somehow implies that you are aware of what is already out there.

cheers,
Antonio

Jan Bender · Post by **Jan Bender** » Tue Jul 10, 2007 7:02 am

a claim of having developed a new algorithm in the field somehow implies that you are aware of what is already out there.

Sorry, but I didn't even find the term "relaxed projected Gauss-Seidel" with Google. I know Gauss-Seidel algorithm that is used for solving systems of linear equations and as far as I know the projected Gauss-Seidel is used to handle bounds.

The new idea of my algorithm was to use a prediction of a joint state and then to solve the constraint with impulses. I don't have a new method for solving systems of linear equations.

My iterative method is a kind of Gauss-Seidel which solves a system of linear equations where the matrix is a diagonal block matrix.

Jan

Dirk Gregorius · Post by **Dirk Gregorius** » Tue Jul 10, 2007 8:57 am

Are you sure your matrix is block diagonal? Physically this would mean that you system is totally decoupled which it obvioulsy isn't, right?

Jan Bender · Post by **Jan Bender** » Tue Jul 10, 2007 9:07 am

Are you sure your matrix is block diagonal? Physically this would mean that you system is totally decoupled which it obvioulsy isn't, right?

For the iterative approach I don't regard the dependencies between the joints directly. So for each joint there is just a matrix block K or L (the matrices of my papers) on the diagonal of the SLE. But you don't need to build up a SLE since in this case you can compute each impulse independently from each other just by inverting the regular matrices K or L.

Jan

Dirk Gregorius · Post by **Dirk Gregorius** » Tue Jul 10, 2007 10:09 am

There is always a system matrix that describes the physical system either as a LS or a LCP (in the presence of unary constraints).

The Gauss-Seidel algorithm basically solves each row (or block) indepently of the whole system. If you investigate how the Gauss-Seidel works you will see that this is equivalent to applying sequential impulses. So the iterative method is not new at all, also applying sequential impulses (or prejocetion like in SHAKE or RATTLE) is not new. Solving each constraint individually doesn't make the system block diagonal.

Anyway there a lot of nice ideas in your approach, e.g. to iteratively adjust velocities at 't' such that the positions satisfy the position constraints at 't + dt'. So they are indeed new at least to my knowledge. I only came across those stuff in Bridson's PhD and cloth papers which were published before Weinstein, so I can't say if this was published before your stuff, but I believe it was after 2000...

If this is really different/new to a method where you inegrate forward and then project back onto the constraint manifold is beyond my mathematical understanding. Maybe Antonio or Ken know this...

Cheers,
-Dirk

Jan Bender · Post by **Jan Bender** » Tue Jul 10, 2007 10:23 am

There is always a system matrix that describes the physical system either as a LS or a LCP (in the presence of unary constraints).

Yes, of course. I just wanted to say that you just need to regard the diagonal elements since the rest is zero. So there is no need to waste space for the whole matrix.

The Gauss-Seidel algorithm basically solves each row (or block) indepently of the whole system. If you investigate how the Gauss-Seidel works you will see that this is equivalent to applying sequential impulses. So the iterative method is not new at all, also applying sequential impulses (or prejocetion like in SHAKE or RATTLE) is not new. Solving each constraint individually doesn't make the system block diagonal.

There is nothing of new or complicated to use an iterative loop. I know Gauss-Seidel and how it works. Anyway I said the idea to solve a joint constraint by an impulse computed with a prediction was new. We simulate joint constraints in this way since the year 2000. I think at this time there were not much people using impulses to simulate joints.

Anyway there a lot of nice ideas in your approach, e.g. to iteratively adjust velocities at 't' such that the positions satisfy the position constraints at 't + dt'. So they are indeed new at least to my knowledge. I only came across those stuff in Bridson's PhD and cloth papers which were published before Weinstein, so I can't say if this was published before your stuff, but I believe it was after 2000...

That is all I wanted to say

Jan

Erin Catto · Post by **Erin Catto** » Tue Jul 10, 2007 5:15 pm

Jan, it would be nice to see some side-by-side comparisons between your method and PGS. I think that would help people determine exactly how your algorithm is different and what those differences bring.

raigan2 · Post by **raigan2** » Tue Jul 10, 2007 5:22 pm

I did a very quick+dirty test implementation of articulated bodies/joints using both sequential impulses and jan's method; the latter seemed to handle joints a lot better.. i didn't try collision constraints though, Box2D certainly seems to excel in that department.

Dirk Gregorius · Post by **Dirk Gregorius** » Tue Jul 10, 2007 5:24 pm

I asked Jan once if could warmstart his solver as well, but I am not sure if he was able to test this.

Raigan2: How was the difference in the performance? You actually iterate the constraints twice here...

raigan2 · Post by **raigan2** » Tue Jul 10, 2007 8:45 pm

It was in flash/actionscript so I can't really say.. the overhead of the VM screws things up (sqrts aren't much slower than mults, etc). Also I didn't spend much time screwing around with iteration count, baumgarte terms, etc -- I was just trying to see how impulse-based methods handled joints and large errors (neither was amazing, but Jan's was certainly more stable/firm and faster to converge). I suspect you could get away with a much lower iteration# as well.

However I don't know that you could beat sequential-impulses for stacking-type stuff, it really performs amazingly well for loose/non-articulated bodies.

Dirk Gregorius · Post by **Dirk Gregorius** » Wed Jul 11, 2007 8:18 am

Jan's method is somehow similar to Erin's super_split method where the position constraints are handled individually. Since you get rid of the Baumgarte term you have better joint behavior I guess...

It might be an interessting test to use Jan's method only for position constraints and stabilize it in a Baumgarte way on the velocities (see Barenbrug). IIRC Jan mentioned that this behaves already very nice. Maybe it is possible to mix both methods and solve non-penetration constraints using SI and joints with Jan's "stabilized" approach.

Cheers,
-Dirk

Jan Bender · Post by **Jan Bender** » Wed Jul 11, 2007 11:21 am

Hi,

Dirk: I tried the warmstart but I didn't had enough time to get it stable. I should spend again some time on this.

Why you want to use Baumgarte terms in combination with my method? In fact you can use my velocity correction for an accurate result. Solving the velocity constraints needs less time then position constraints, since the velocity difference is known and can be instantaneously corrected by an impulse. You can even use my method as stabilization method for Lagrange multiplier simulations instead of Baumgarte. We have described this in a paper.

Btw. if the sum of all impulses for a single joint is limited you can even repair total disintegrated models with my method. This makes the simulation even more stable. I just integrate this feature in IBDS.

Jan