Mass-spring and dynamic relaxation

[horyd]

Hey guys,

Quick question, could someone tell me exactly what the difference between mass-spring soft body physics and dynamic relaxation is? As far as I can tell they appear to be quite similar, however all relaxation is based from F = Kx + Cv + Ma while mass spring systems are generally confined to F=Kx? I've been looking for information about the differences for ages but I cant quite find any information. Are the base equations the same, but the numerical methods different? (with most dynamic relaxation systems using finite difference method).

Genuinely baffled about this, so any information on this would be tops, thanks.

Jaryd

[guernika]

hello to all,

I'm also interested about this...hence any help or suggestion will be appreciated

Thanks in Advance

Francesco

[Dirk Gregorius]

The term relaxation as used in game physics is related to solving constrained numerical systems. Instead of solving the MLPC with e.g. a direct pivoting solver you solve each constraint individually. Since this violates the other constraints again you do this in a loop. Mathematically this is equivalent to the iterative Gauss-Seidel method for solving linear systems.

I don't see any relation between relaxation and spring-damper system. You *maybe* could create one if you integrate your system with an implicit Euler scheme and then use a Gauss-Seidel solver for the linear system. But I am guessing only.

Here are some useful links:

All GDC presentations from Erin Catto:
http://code.google.com/p/box2d/downloads/list

Thomas Jacobsen:
http://www.gpgstudy.com/gpgiki/GDC%2020 ... %20Physics

Relation between constraints and springs:
http://ode.org/ode-0.5-userguide.html#sec_3_8_2

Gauss-Seidel on Wikipedia:
http://en.wikipedia.org/wiki/Gauss%E2%8 ... del_method

Finally Google is your friend:
http://en.wikipedia.org/wiki/Relaxation_method

[h4tt3n]

As far as I can tell they appear to be quite similar, however all relaxation is based from F = Kx + Cv + Ma while mass spring systems are generally confined to F=Kx?

Where exactly did you read this?

[horyd]

Yea don't worry that statement was complete bull, they are both of the longer form, my bad ><

Please correct anything that's not right, my knowledge is still sketchy to say the least. Dynamic Relaxation as far as I'm aware is explicit integration with use of the Gauss-Siedel method. I believe you are referring to position based dynamics (by the likes of Muller, whos method is part GS and part Jacobi), but is this dynamic relaxation exactly? Even with it's disregard of the velocity component?

I've read in "Physically Based Deformable Models in Computer Graphics" that mass-spring systems are an example of non-continuum mechanics simulation, so nodes for a mass-spring system are derived from 2D or 3D models no regards to overall continuum mechanics. Dynamic relaxation is the process of applying simpler mass-spring(-damper) mechanics to a pre-discretized mesh that HAS been constructed considering elastic continuum (finite elements), but ignores these factors (you can see from the mathematics on the wiki page the absence of any consideration of strain tensors etc that would have originally derived from the initial PDE). It could be said the Dynamic Relaxation is properly technically termed as the application of the central finite difference explicit integrating method to physical bodies under a continuum discretization. Since the continuum mechanics are ignored, is it equally viable to say that DR is technically a mass-spring system using central-finite diff integration?

This is a bit of a noob question, but mass-spring systems, like DR, are looking to alter nodal properties (position/displacement, velocity, acceleration) in order to make the residual forces equal to 0 [and in doing so obtain an equilibrium? i.e. P(internal) = P(external)?].

If this is the case then isn't the link between the two undoubtedly evident? The underlying mechanics would be the same, merely a different solution mechanism used?

Again, please correct this, I am certainly not 100% sure about everything here

Cheers guys

Jaryd

[Dirk Gregorius]

In constrained dynamics you have to solve a system of differential-algebraic equations and *no* ODE nor PDE.

In the holonomic/rheonome case you need to solve:
dx/dt = v
dv/dt = M^-1 * ( f_ext + JT * lambda )
C(x) = 0

Note that the first two equations are differential-equations and the last is an algebraic equation. The are many way to solve this, like penalty method, index reduction, constraint projection and whatever. In games we usually solve on the so called velocity level with Baumgarte stabilization which leads to solve the following system:

J*M^-1*JT * lambda = -J*v - beta * C / dt

This is sometimes called the effective mass form. This is a linear system which can be solved using a Gauss-Seidel method which itself is a relaxation method (as Jacobi, SOR, etc). It can also be shown that a Gauss-Seidel method that solves the above effective mass form is equivalent to applying sequential impulses. The broad idea is to solve one constraint after the other. Similar to the Gauss-Seidel method where you handle each row of the linear system individually. So correcting "individual errors" using an iterative loop in the broadest sense like the Gauss-Seidel methods can be called relaxation.

In position based dynamics you also have an error function and resolve one error after the other in an iterative loop. So again this is a relaxation method. Also note that position based dynamics is *not* a mixture of Gauss-Seidel and Jacobi. It is a mixture of Gauss-Seidel and Newton sometimes called Newton-Gauss-Seidel or Non-linear Gauss-Seidel. The reason is that you have to solve a *non-linear* system if you project constraints on the position level instead of a *linear* system if you solve on the velocity level.


HTH,
-Dirk

[horyd]

This paper on dynamic relaxation states that there *is* an ODE (of the non-linear type) to solve...

so confusing ><

[Dirk Gregorius]

From the text (first sentence): "The method of dynamic relaxation (DR) seeks to solve a linear or nonlinear system of equations". This is what I have written. If the problem the try to solve in this text arises from ODEs this is good for them. In games you usually have DAEs since you formulate constraints as a geometric relation between rigid bodies. I don't know what the text is trying solve and I don't have time to read it.

[horyd]

ahh i see

that's cool, cheers for your help Dirk

Jaryd

[ndujar]

Hi all:

Well, hopefully its not too late.

Physically Based Deformable Models in Computer Graphics
http://www.matthiasmueller.info/publica ... ar2005.pdf

This is a very good starting point for getting some scope on this numerical simulation world.

Regards