Re: [Algorithms] Hair, clothing, like DOA3

[Tom L. <to...@kr...>]

It just doesn't seem that its the verlet integration that is making the
described algorithms stable. Comparing Verlet with the explicit equivalent,
Newton's method.

Verlet: (from Advanced Character Physics)
1. temp = x
2. x += x - oldX + a*dt*dt
3. oldX = temp

Newton's:
1. x += v*dt + 0.5*a*dt*dt
2. v += a*dt

Newton's is also second order so solves ballistic motion exactly.
Now lets take a simple spring where a = -10*x, dt is 1 and x0 = oldX0 = 1.
We get the sequence:
1, -9, 71, -630 with Verlet and 1, -4, 6, -114 with Newton's
Both systems blow up ie are unstable for a large spring constant. What
appears to make the Verlet method stable in articles I've read is that the
position is updated (line 2.) many times before the old position is updated
(line 3.). This is successive relaxation and can be done with explicit
methods too (perform 1. many times before line 2. using the sum of all the
accelerations) this successive relaxation is what gives stability, not the
Verlet integrator.

Actually the verlet scheme from 'Advanced character physics' doesn't solve
ballistic motion exactly, perhaps there's another scheme but the one above
gives 0, 1, 3, 6 for an a of 1, rather than the correct 0, 0.5, 2, 4.5 given
by Newton's method.

----- Original Message ----- 
From: "Acy James Stapp" <as...@fi...>
To: <gda...@li...>
Sent: Tuesday, August 03, 2004 6:38 AM
Subject: RE: [Algorithms] Hair, clothing, like DOA3


> The ramification of this is that a symplectic iterator will not drift
> to a higher or lower-energy state over the long term due to numerical
> issues. Using a non-symplectic integrator you need to either verify
> that the drift will always go the direction you want (which is beyond
> my math background) or add a relaxation or renormalizing step.
>
> Caveat: My knowledge about this comes from molecular dynamics simulation
> but should apply to game physics equally well.
>
> Acy
>
> Erin Catto wrote:
> > Verlet is much more stable than explicit (forward) Euler. However, if
> > you modify Euler integration to compute the new positions based on
> > the _new_ velocities, then they are equally stable. This is called
> > symplectic Euler or semi-implicit Euler. Vanilla explicit Euler is
> > very bad - don't mess with it.
> >
> > The nice thing about Verlet and symplectic Euler is that they conserve
> > energy on average. Verlet is better than symplectic Euler because it
> > is second order and solves ballistic motion exactly.
> >
> > Erin
> >
> > -----Original Message-----
> > From: gda...@li...
> > [mailto:gda...@li...] On Behalf Of
> > Tom Lowe Sent: Sunday, August 01, 2004 10:08 PM
> > To: gda...@li...
> > Subject: Re: [Algorithms] Hair, clothing, like DOA3
> >
> > I'm also a little confused by claims I've seen that Verlet integration
> > allows for 1000 times harder constraints than Euler or even bigger
> > figures. As far as I see, Verlet is just like Euler but damps sudden
> > changes in velocities, like a low pass filter. Definitely good, but
> > not much more stable. You can't use much larger spring constants, but
> > you can get harder constraints by lots of iterations with a
> > reasonable spring constant (which is the iterative deformation
> > constraint enforcement), you can of course do this with Euler too.
> > I must be thinking about it wrong or something.
> >
> > The basic cloth algo is pretty simple
> > 1. Add forces onto velocity of each particle in cloth (f = ma)
> > 2. Add velocity onto position of each particle (p += v*dt)
> > 3. Loop through each pair of connected particles and move the
> > positions to match the distance constraint.
> > 4. Repeat 3 several times
> > 5. Adjust the velocity based on the new position (v = (p - oldPos)/dt)
> >
> > ----- Original Message -----
> > From: "Bill Baxter" <ba...@cs...>
> > To: <gda...@li...>
> > Sent: Monday, August 02, 2004 1:54 PM
> > Subject: Re: [Algorithms] Hair, clothing, like DOA3
> >
> >
> >> This is something that's been bugging me for a long time.  As far as
> >> I recall from reading the GDC paper, the Verlet integrator didn't
> >> seem to have that much to do with the success of the method as far
> >> as I could tell.  It's the iterative deformation constraint
> >> enforcement that really "takes care of the rest", which is really a
> >> separate issue altogether from the numerical integrator used.  No?
> >>
> >> --bb
> >>
>
>
> -------------------------------------------------------
> This SF.Net email is sponsored by OSTG. Have you noticed the changes on
> Linux.com, ITManagersJournal and NewsForge in the past few weeks? Now,
> one more big change to announce. We are now OSTG- Open Source Technology
> Group. Come see the changes on the new OSTG site. www.ostg.com
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_ida88