Ageia paper on position based physics

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

Ageia paper on position based physics

Post by Erwin Coumans »

Some of Ageia's engineers published a new paper on position based dynamics. A quote from the paper:
Jakobsen built his Fysix engine on a position based approach. His central idea was to use a Verlet integrator and manipulate positions directly. Because velocities are implicitly stored by current and the previous positions, the velocities are implicitly updated by the position manipulation. While he focused mainly on distance constraints, he only gave vague hints on how more general constraints could be handled.
In this paper we present a fully general approach which handles general constraints. We also focus on the important issue of conservation of linear and angular momenta by position projection. We work with explicit velocities instead of storing previous positions which makes damping and friction simulation much easier.
http://graphics.ethz.ch/~mattmuel/publi ... sedDyn.pdf

According to that paper, position-based dynamics helps the two-way interaction between rigidbodies and cloth (for example).
This is something which has already been discussed on this forum before:
http://www.continuousphysics.com/Bullet ... .php?t=404

An older demo by Meqon (acquired by Ageia) showing cloth-rigidbody interaction:
http://www.continuousphysics.com/ftp/pu ... 202005.zip
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

Nice paper, Erwin. Thanks for bringing it up here.

I read through the paper and there are a lot of interessting ideas. Anyway I can't understand one thing. Under "5. Results" they write:
Real Time Self Collision:
[...]The simulation runs at 30 FPS on average...
I wonder how anybody can assume an algorithm that runs at 30FPS for a single rectangular cloth piece being of any practical use for realtime simulations. What does AGEIA expect from a game producer he is willing to spend for a simple eye candy like cloth? This is so far from reality in my opinion that I hardly can put it in words. It would have been nice to have results when self collision is ignored so I could see how much the performance is affected because of considering self collision.


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

Post by Erwin Coumans »

This positional based physics has interesting application in two-way interfaction between all kind of physics systems. Being able to handle distance, planar and volume preservation in a stable way allows you to do very good quality deformable objects. So it might very well be a fast and stable alternative to FEM. People used verlet for years now in cloth and rigidbody context, and this new paper describes a more general application. Volume preservation, bending etc fit in the same framework.

Position based derivation/solution provides a much simpler formulation and implementation for deformable objects.
Another interesting paper by the same author / Ageia engineer Matthias Muller: http://graphics.ethz.ch/~mattmuel/publi ... GI2004.pdf

So we can expect some more destructable physics systems soon, I suppose.
Last edited by Erwin Coumans on Fri Oct 06, 2006 1:36 am, edited 2 times in total.
mewert
Posts: 52
Joined: Sat Oct 08, 2005 1:16 am
Location: Itinerant

Post by mewert »

The two-way interaction stuff is nice.

I have a problem with the treatment of collision constraints, though. Since you're moving the positions of the verticies around each iteration, the collision constraints that you detected outside of the constraint solver quickly become invalid. I believe you will see many artifacts on curved surfaces while fast motion is occuring. I tried this scheme before, but had to abandon it in favour of doing collision detection each iteration of the solver ( yes, very expensive ).

I'm still hoping someone will come up with a stable and efficient velocity-based character cloth solution! Then all those per-iteration collision checks can be removed.
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

I agree with your collision concerns, but it might be that the CCD helps here a little. They also adjust the velocity at the very end of the solver to account for friction and restitution which also might help a little.

What I really like is the bending model. I tried the Bridson stuff and it really looked amazing. On the other side it much more expensive then a simple unilateral distance constraint across the shared edge which does work as well.
Jan Bender
Posts: 111
Joined: Fri Sep 08, 2006 1:26 pm
Location: Germany
Contact:

Post by Jan Bender »

I am already very interested in the presentation of the paper about position based dynamics on the VRIPHYS conference in november. I will present my newest paper in the same session and directly after Matthias Mueller-Fischer, so I will be able to listen to his presentation :wink:

He also has an invited talk about "Physically Based Simulation - Academic Research and What Works in Games".

So, is anybody interested to visit the VRIPHYS?

Jan
clanzotti
Posts: 15
Joined: Tue Jul 26, 2005 10:11 am

Post by clanzotti »

mewert wrote:The two-way interaction stuff is nice.

I have a problem with the treatment of collision constraints, though. Since you're moving the positions of the verticies around each iteration, the collision constraints that you detected outside of the constraint solver quickly become invalid. I believe you will see many artifacts on curved surfaces while fast motion is occuring. I tried this scheme before, but had to abandon it in favour of doing collision detection each iteration of the solver ( yes, very expensive ).

I'm still hoping someone will come up with a stable and efficient velocity-based character cloth solution! Then all those per-iteration collision checks can be removed.
I've used this approach for years too and i had the same problem with those collision artifacts.

Actually to solve the problem i've used a mix of various tecniques but still some artifacts are difficult to remove.

Anyway, in the field of realtime simulation, where accuracy is not the main concern, it adapt very well.

Another limitation that forced me to not use this method over the years is the dependency of the stiffness constant with the timestep size, a nightmare to deal with if an adaptive step size is required.

Regards,

Carlo Lanzotti
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

Another limitation that forced me to not use this method over the years is the dependency of the stiffness constant with the timestep size, a nightmare to deal with if an adaptive step size is required.
Actually not only for situations where adaptive timesteps are required, since I personally find it very difficult to establish fixed timesteps in a game as opposed to simple demos.

Anyway, how could such a dependency be removed? Actually I would like to understand where the dependency actually exists, how it effects the system and how to deal with it? Any hints?

Cheers,
-Dirk
raigan2
Posts: 197
Joined: Sat Aug 19, 2006 11:52 pm

Post by raigan2 »

I don't suppose anyone could explain how you'd go about determining the gradiant of a constraint function?

I wish they'd extended the method to deal with rigid bodies..
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

The gradient of the Constraint function is actually the Jacobian. The relation is:

C(x) = 0

dC/dt = dC/dx * dx/dt = J * v

The first is the position constraint (non-linear) and the second is the (hidden) velocity constraint (linear). You find the Jacobian by building all partial derivates and collect them in a matrix. See Kenny's thesis and book for an in depth explanation. Also see Wikepedia.

HTH,
-Dirk
John Schultz
Posts: 23
Joined: Sat Aug 06, 2005 7:48 am
Contact:

Post by John Schultz »

Regarding section 7 of the paper, Future Work and rigid bodies:

1. Load track Colline Verdi II in my demo here: http://www.brightland.com/ac/
2. Run into/shoot the box stacks.

The rigid bodies are implemented using the methods described here: http://www.brightland.com/Physics/index.htm

In simple terms, tetrahedrons are deformed as per Jakobsen's suggestions giving new positions and orientations. The particles making up the vertices are tracked so that the kinetic energy change resulting from the movement can be corrected (performed pairwise for object-object collisions). The new momenta are used to integrate the rigid bodies (momentum based integrator as opposed to velocity based). Standard impulse-momentum calculations are also used for collisions. To my knowledge, this method has not been published before, nor have any demos been shown using such a method in operation. Seems kind of obvious to me now, not sure why no one tried this method before (perhaps they have, and did not publish their results?). This method can be extended to allow blending between deformable rigid bodies and hard rigidbodies (don't reset the tetrahedrons every iteration: iterate them as with cloth).

Image
At 100Hz, no iteration is required for stacks as shown in the demo. The most expensive element in my game is dealing with real-time bicubic patch collisions and flexible tire simulation. Constraints use the same position deformation along with impulses.

What I like about this method is it's based on constrained particle physics as opposed to optimization methods, which IMO looks much more realistic, and so far runs fast (have not spent any time optimizing the final system yet). Since it's possible to switch between a tetrahedral-particle based integrator and rigidbody momentum-based integrator, one can validate motion for accuracy (rigidbodies being a simplification/averaging approximation to particle systems).

John
clanzotti
Posts: 15
Joined: Tue Jul 26, 2005 10:11 am

Post by clanzotti »

John Schultz wrote:Regarding section 7 of the paper, Future Work and rigid bodies:

[snip]

What I like about this method is it's based on constrained particle physics as opposed to optimization methods, which IMO looks much more realistic, and so far runs fast (have not spent any time optimizing the final system yet). Since it's possible to switch between a tetrahedral-particle based integrator and rigidbody momentum-based integrator, one can validate motion for accuracy (rigidbodies being a simplification/averaging approximation to particle systems).

John
Well, as already mentioned i used this method years ago. I've published no papers about it for some reasons.

The anims below where all made using a method similar to the proposed 'position based physic' (Circa 2003) :

Cloth samples:

http://win.dynadream.com/cloth/anims/cl ... h_self.avi
http://win.dynadream.com/cloth/anims/da ... border.avi
http://win.dynadream.com/cloth/anims/re ... _simul.avi
http://win.dynadream.com/cloth/anims/skirt_test.avi
http://win.dynadream.com/cloth/anims/teddy_dance_ne.avi
http://win.dynadream.com/dynatomic/anim ... _cloth.avi
http://win.dynadream.com/dynatomic/anims/da_c_coll.avi

Rigid-Soft-Samples:

http://win.dynadream.com/wobble/anims/d ... magnet.avi
http://win.dynadream.com/wobble/anims/d ... magnet.avi
http://win.dynadream.com/wobble/anims/da_diff_mass.avi
http://win.dynadream.com/wobble/anims/da_face.avi
http://win.dynadream.com/wobble/anims/d ... traint.avi
http://win.dynadream.com/wobble/anims/da_motor.avi
http://win.dynadream.com/wobble/anims/da_motor_back.avi
http://win.dynadream.com/wobble/anims/da_multi_obj.avi
http://win.dynadream.com/wobble/anims/da_ropes.avi
http://win.dynadream.com/wobble/anims/rw_dominos.avi
http://win.dynadream.com/wobble/anims/rw_ell_blocks.avi
http://win.dynadream.com/wobble/anims/rw_links.avi
http://win.dynadream.com/wobble/anims/rw_ell_blocks.avi
http://win.dynadream.com/wobble/anims/r ... achine.avi
http://win.dynadream.com/wobble/anims/rw_multiobj.avi
http://win.dynadream.com/wobble/anims/rw_tentacle.avi
http://win.dynadream.com/wobble/anims/r ... _torus.avi

I used CCD from the beginning :-)

Somethings that let me think about... :-|

Regards,

Carlo Lanzotti
Jan Bender
Posts: 111
Joined: Fri Sep 08, 2006 1:26 pm
Location: Germany
Contact:

Post by Jan Bender »

I have a problem with the algorithm described in the "position based dynamics" paper. Maybe anybody can help me.

In line 5 of the algorithm the new velocities of the vertices are computed. And then in line 7 the new positions p_i are determined by

p_i = x_i + h * v_i

where h is the time step size. So the external force is treated as an impulse but why? If a force is used the position of a vertex after integrating the acceleration should be

p_i = x_i + v_i*h + 0.5 * (F_ext/m) * t^2

If the equation of the paper is used, a vertex has the correct velocity but the position p_i is wrong.

Could anybody explain to me why the factor 0.5 is missing in the equation of the paper?

Jan
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

The equations of motion are (omitting non-holonome constraints for simplicity):

dx/dt = v
dv/dt = W * (f_ext - JT * lambda)

C(x) = 0

This is what you have to solve. Several strategies exist here, e.g. for rigid bodies we use the following discretization:

x(t + dt) = x(t) + v(t + dt) * dt
v(t + dt) = v(t) + W * (f_ext - JT * lambda) * dt

and use the (hidden) velocity constraints with Baumgarte stabilization. You get:

J * v = -tau * C(x) / dt

You can combine the equations and end up with:

J*W*JT * lambda * dt = -tau * C(x) / dt - J * ( v(t) + W * f_ext * dt )

This is a linear system for equality constraints or a LCP in the presents of inequality constraints (e.g. contacts or limits). Erin Catto showed that solving this using a PGS algorithm is equivalent to applying sequentiel impulses where each delta impulse is basically computed as:

J*W*JT * impulse = -tau * C(x) / dt - dv


Instead of solving on the velocity level you can also try to solve the following system.

x(t + dt) = x(t) + v(t + dt) * dt
v(t + dt) = v(t) + W * (f_ext - JT * lambda) * dt

C(x) = 0
dC/dt = J * v = 0

I suggest looking at Hairer "Solving ordinary differential equations II" VII.1 The index and Various examples - Mechanical systems (GGL) and VII.2 Index Reduction Methods - Stabilization by projection

I think the idea is to solve the following system:

M(x')(x - x') + JT * lambda = 0
C(x) = 0

and

M(x')(v - v') + JT * lambda = 0
J*v = 0


So there is nothing new to these ideas I guess. The outcome is for my understanding that solving the position constraints using simplified Newton iterations is equivalent to sequentiel projections (Jacobsen) and an iterative solution for the second system using a Gauss - Seidel like scheme is equivalent to sequentiel impulses (Catto).

I think your method is (intentionally) more decoupled from this abstract mathematical formulation. The advantage might be that it is maybe physical more plausible, on the other hand the above methods can more easily prove convergence.

@clanzotti
Where did you use the methods before? Which projects did you work on? The examples look very nice - do you have any timing informations for the examples? Do they run in realtime?


Cheers,
-Dirk
clanzotti
Posts: 15
Joined: Tue Jul 26, 2005 10:11 am

Post by clanzotti »

Hi Dirk,
Dirk Gregorius wrote:The equations of motion are (omitting
@clanzotti
Where did you use the methods before? Which projects did you work on? The examples look very nice - do you have any timing informations for the examples? Do they run in realtime?
Cheers,
-Dirk
Yes, sorry for not included before such informations.

The method was used in a very early version of my cloth dynamic simulation system (Called RealCloth at the time). The project started in 2000~ targeted to become a plugin for Realsoft3D (http://www.realsoft.com).

The simulations where not realtime, but most of them ran at an average speed of 2-3 seconds per frame on a P3 800Mhz. (1-2~ minutes for the 100 meters cloth).

The system was designed for offline simulations.

Then it evolved until today, major rewrite and a new name: DynAtomic (http://www.dynadream.com). It will be released for the forthcoming Realsoft3D V6.

Actually the system is capable of simulating clothes and soft objects as well as rigid body dynamic, all interacting togheter.

More informations can be found on the forthcoming web site i mentioned above. (Planned launch November/December).

Regards,

Carlo Lanzotti
Post Reply