Backward Integration Cloth Simulation

Post Reply
melax
Posts: 42
Joined: Mon Apr 24, 2006 4:55 pm

Backward Integration Cloth Simulation

Post by melax »

Because Dennis from Meqon (now ageia) had asked me my 2c on different cloth simulations, I ended up spending a couple weekends implementing a backward integrator. Its just easier to show something than to try and explain something. Actually all the demo framework, asset creation, and writeup took more time than the core implementation, but, well, that's what you need to do in order to show something.

The URL for the demo, writeup, and source is at:
www dot melax dot com slash cloth

I assume you can decode the above line (all lower case). I dont want the search engines to pick this up yet since I want to do some more polishing and provide more detailed explanations of the math for those who might be intimidated. I certainly welcome anyone here from the Bullet community to have a look at this time.

Any feedback is welcome.

The posted .cpp files are not quite current, but close enough.

There are lots of details that dont seem to end up in the published research papers out there. For example, Im curious if anybody ever tried to modify the "filter" between sucessive conjugate gradient iterations to adapt to whether a point will actually collide or not. Or is symmetric constraints the only option.

If anybody has a strong opinion on template metaprogramming (one way or the other), then check out the expression optimization system that I used. I think its a reasonable compromise that has the best of both worlds - sweet looking high level code without the performance penalty and without relying on overly complicated recursive compiler tricks.


Note, I realize that there are different approaches to simulating cloth. I'm not saying that one is right and one is wrong. Only that I believe backward integration might be the right choice in some circumstances. Certainly each approach has its own set of advantages and disadvantages.


As I mentioned any discussion is most welcome.
Erin Catto
Posts: 316
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine
Contact:

Post by Erin Catto »

Thanks for the demo Stan. Fun stuff!

I have a few random comments on the subject of cloth.

- What everyone calls "Verlet" is just sequential position projection (SPP) along with a certain choice of integrator (the Verlet integrator). One could also do SPP with any other integrator.

- SPP constraints do not affect momentum, so SPP cannot be used to simulate an oscillating pendulum. This is one reason why SPP looks unnatural in some cases.

- Sequential impulses (SI) can be used to simulate cloth. SI can be used to simulate oscillating pendulums.

- SI can model constraint softness, giving the appearance of stretchiness without stability issues. See this handy tip from Russell Smith: http://www.ode.org/ode-latest-userguide.html#sec_3_8_2

- If one uses SI for cloth and rigid body simulation, the two systems may be coupled with bilateral response. Stability will be an issue for large mass ratios.
John Schultz
Posts: 23
Joined: Sat Aug 06, 2005 7:48 am
Contact:

Post by John Schultz »

Hi Stan- looks good, fast and stable.

Comments:

Dean Macri @ Intel released an implicit cloth demo; I could not find the page/source on Intel's site (was not as fast/stable as your example).

While searching for Dean's paper/demo, I found this link, with source:

http://www.people.fas.harvard.edu/~hcho ... index.html

Re: Verlet Integration- it has been called semi-implicit; not aware of anyone calling it implicit. More info on the so-called Verlet (Newton-Stormer-Verlet) integrator here (recommeded by Erin): http://www.amazon.com/gp/product/354043 ... 63?ie=UTF8

Re: Jacobsen-style Verlet cloth- a demo that shows the difference between "Verlet cloth" and implicit cloth would be useful. With both versions highly optimized, I would estimate that "Verlet cloth" would run faster and look more realistic (any KE error is easy to fix up). I have also successfully blended springs with projected updates to give a slightly springy feel to otherwise non-springy Verlet cloth. Stability is guaranteed via clamping. For stiff cloth-like structures, I would agree that implicit cloth should dominate.

If it's possible to make an implicit cloth integrator run faster and look as realistic as Verlet cloth, that would be very cool indeed. It would also be cool to see a good solution for kinetic energy correction (I believe Baraff+Witkin and others worked on a few different methods).

Perhaps a 3-way demo with Verlet cloth, implicit cloth, and Erin's suggested sequential impulse cloth would be a worthwhile exploration?
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Post by Erwin Coumans »

moved my reply here, because general cloth discussion will reach more people:

http://continuousphysics.com/Bullet/php ... php?p=1280
deberle
Posts: 1
Joined: Wed Dec 07, 2005 6:15 pm
Location: San Francisco

Cloth Mechanical model

Post by deberle »

Hey,

So I saw that you are experimenting with the model from Ko's paper and had some questions for you. Are you using it on irregular meshes or grids? He later published a paper about irregular meshes, but I believe I found an error. First the function should be based on the distance perpendicular to the edge shared by the triangles. If you use the actual distance, the amount of force pushing apart the vertices varies, even though the mass of the particles (if area based) does not.

I have also run into a problem when not applying any force if there is tension for bend and doing the same for compression under stretch and shear. Putting in an if statement based on this leads to a discontinuous response and I've have noticed artifacts which I believe result from this. Have you encountered this and if so have you come up with a solution?

I am favoring models based on the dihedral angle, though they lead to a less well conditioned system. In Ko's model if you constrain the two endpoints and let it sag under gravity, no amount of stiffness will bring the four vertices back to a plane.

While speed is important to me, it is not of the utmost importance. Where I seem to get thrashed is not in the number of CG iterations, but the time for a single sparse matrix multiply. It appears it is not the flops, but the traversal of the vector that might be thrashing the cache. Does anyone have a good suggestion for improving this? My system is naturally blocked and I reorder the vertices to reduce the bandwith. Any suggestions are appreciated. Thanks.

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

Post by Dirk Gregorius »

Looks very interessting - thanks for sharing this. A nice implementation of the Baraff paper can also be found here:

http://davidpritchard.org/freecloth/

And I also like his bibliographie of papers here:

http://davidpritchard.org/graphics/clothref.html

Besides the papers you suggested I recommend also looking into the work of Boxerman here:

http://www.cs.ubc.ca/~eddybox/

Also look for his master thesis. If you cannot find it drop me a mail and I send you a copy. Some other ideas w.r.t. Baraff can be found in the work of Kang:

http://www.informatik.uni-trier.de/~ley ... g=Min.html

Again if you cannot find anything I should have it.

The final thing to look into is the work of R. Bridson here:

http://graphics.stanford.edu/~fedkiw/pa ... 003-06.pdf
http://graphics.stanford.edu/~fedkiw/pa ... 002-01.pdf

PhD:

http://www.cs.ubc.ca/~rbridson/docs/rbridson_phd.pdf

If you look into this papers you will find some parallels to the rigid body time-stepping method in the Guendelman paper - so quite interessting to read...

HTH,

-Dirk
Frankyboy
Posts: 2
Joined: Wed Nov 29, 2006 10:29 pm

Re: Backward Integration Cloth Simulation

Post by Frankyboy »

melax wrote:The URL for the demo, writeup, and source is at:
www dot melax dot com slash cloth
This link no longer works! Is the code still available?
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Backward Integration Cloth Simulation

Post by Erwin Coumans »

Frankyboy wrote:
melax wrote:The URL for the demo, writeup, and source is at:
www dot melax dot com slash cloth
This link no longer works! Is the code still available?
Yes, the cached version is here:
source:
http://www.continuousphysics.com/ftp/pu ... =cloth.cpp
http://www.continuousphysics.com/ftp/pu ... h_extern.h
http://www.continuousphysics.com/ftp/pu ... njgrad.cpp
and
http://www.continuousphysics.com/ftp/pu ... sions.html
or follow Optimized Expressions http://www.melax.com/gamedev.html
binary demo:
http://www.continuousphysics.com/ftp/pu ... _cloth.zip
Last edited by Erwin Coumans on Mon Dec 04, 2006 12:15 am, edited 1 time in total.
Frankyboy
Posts: 2
Joined: Wed Nov 29, 2006 10:29 pm

Post by Frankyboy »

Many thanks!
raigan2
Posts: 197
Joined: Sat Aug 19, 2006 11:52 pm

Post by raigan2 »

unless i'm misunderstanding something (i've only just glanced through the code), a source file is missing: the function ConjGradientFiltered isn't defined anywhere..
Genscher
Posts: 25
Joined: Thu Jul 20, 2006 1:29 pm

License

Post by Genscher »

Hello!

The links Erwin posted are NOT the links to the files from melax/Stan.

These files which you get when you follow the links are modified by me and a friend and therefore under the license of GPL.

I posted Erwin the original files from melax/Stan and I think he will put them online pretty fast.

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

Post by Erwin Coumans »

Thanks to Genscher, Stan's original posted code is here:

http://www.continuousphysics.com/ftp/pu ... th2006.cpp

The ConjGradientFiltered snippet extracted:

Code: Select all

int  ConjGradientFiltered(float3N &X, const float3Nx3N &A, const float3N &B,const float3Nx3N &S)
{
       // Solves for unknown X in equation AX=B
       conjgrad_loopcount=0;
       int n=B.count;
       float3N q(n),d(n),tmp(n),r(n);
       r = B - Mul(tmp,A,X);    // just use B if X known to be zero
       filter(r,S);
       d = r;
       float s = dot(r,r);
       float starget = s * sqr(conjgrad_epsilon);
       while( s>starget && conjgrad_loopcount++ < conjgrad_looplimit)
       {
               Mul(q,A,d); // q = A*d;
               filter(q,S);
               float a = s/dot(d,q);
               X = X + d*a;
               if(conjgrad_loopcount%50==0)
               {
                       r = B - Mul(tmp,A,X);
                       filter(r,S);
               }
               else
               {
                       r = r - q*a;
               }
               float s_prev = s;
               s = dot(r,r);
               d = r+d*(s/s_prev);
               filter(d,S);
       }
       conjgrad_lasterror = s;
       return conjgrad_loopcount<conjgrad_looplimit;  // true means we reached desired accuracy in given time - ie stable
}
The links in my previous posting on this thread might contain some modifications, but no additional license headers were removed/added.
Erwin
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

Some stuff can still be found here. Note that Stan only released snippets:

http://www.melax.com/dspring
http://www.melax.com/optex
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Post by Erwin Coumans »

Your links can be found on the same melax site I posted before in this thread: http://www.melax.com/gamedev.html

I think Genscher managed to compile and run those Stan's snippets with a bit of effort:
http://www.continuousphysics.com/ftp/pu ... th2006.cpp
Dirk Gregorius wrote:Some stuff can still be found here. Note that Stan only released snippets:

http://www.melax.com/dspring
http://www.melax.com/optex
Post Reply