Page 1 of 1
Backward Integration Cloth Simulation
Posted: Wed Jul 05, 2006 4:50 am
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.
Posted: Wed Jul 05, 2006 6:18 am
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.
Posted: Wed Jul 05, 2006 7:29 am
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?
Posted: Wed Jul 05, 2006 5:52 pm
by Erwin Coumans
moved my reply here, because general cloth discussion will reach more people:
http://continuousphysics.com/Bullet/php ... php?p=1280
Cloth Mechanical model
Posted: Thu Jul 06, 2006 12:01 am
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
Posted: Fri Jul 07, 2006 7:18 pm
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
Re: Backward Integration Cloth Simulation
Posted: Wed Nov 29, 2006 10:32 pm
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?
Re: Backward Integration Cloth Simulation
Posted: Wed Nov 29, 2006 10:46 pm
by Erwin Coumans
Posted: Wed Nov 29, 2006 11:11 pm
by Frankyboy
Many thanks!
Posted: Sun Dec 03, 2006 8:22 pm
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..
License
Posted: Mon Dec 04, 2006 8:38 am
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!
Posted: Mon Dec 04, 2006 1:01 pm
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
Posted: Mon Dec 04, 2006 1:30 pm
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
Posted: Mon Dec 04, 2006 1:41 pm
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