Stick constraint
Thomas Jakobsen uses a stick constraint to model a cloth simualation in his article "Advanced Character Physics".
Below it is his motivation for using a stick constraint instead of springs
"Strong springs leads to stiff systems of equations that lead to instability if only simple integration techniques are used, or at least bad performance – which leads to pain. Conversely, weak springs lead to elastically looking cloth.
However, an interesting thing happens if we let the stiffness of the springs go to infinity: The system suddenly becomes solvable in a stable way with a very simple and fast approach."
I don't quite understand the 2nd paragraph of his statements. Wouldn't an infinitely strong spring(stick constraint) lead to instability problem as well.
No, if you were to simulate an extremely stiff spring that is extended a large distance, you'd have to calculate the huge force necessary to restore the spring, then try to integrate that over a small timestep. By infinitely stiff, you know exactly what length it will restore to, so you can bypass math dealing simultaneously with huge and small numbers being multiplied, divided, squared and approximated.
I'll second ajas95's reply, which basically answers the question.
With truly 100% rigid constraints (stick constraints), things can all of a sudden be solved in a way that avoids the force-as-a-function-of-displacement term that leads to the instabilities in explicit numerical methods. (In real life, even "rigid" constraints are the result of a tiny stretching or compression of the object, so stiffness isn't really infinite. But the approximation of infinite stiffness makes things mathematically nice for numerical simulation.)
I'll also add that Jakobsen does use the penalty method for collision response, which uses springs at interpenetration points to resolve collisions over a series of time steps. He uses potential functions instead of linear springs, but the idea is the same, and these penalty forces (forces that are functions of displacement---interpenetration depth) can lead to instability.
The way Jakobsen deals with this aspect of the simulation is to use an implicit solver instead of the more commonly-discussed (and maybe used) explicit solvers. Implicit solvers can deal with extremely stiff springs, even springs approaching infinite stiffness.
I wrote a paper on some of this---the finer details of why the heck numerical methods go unstable---and presented at GDC 2001. If you really want to dig into the math more, you can download my paper and presentation at:
GDC 2001 Archives
Look for my name.
With truly 100% rigid constraints (stick constraints), things can all of a sudden be solved in a way that avoids the force-as-a-function-of-displacement term that leads to the instabilities in explicit numerical methods. (In real life, even "rigid" constraints are the result of a tiny stretching or compression of the object, so stiffness isn't really infinite. But the approximation of infinite stiffness makes things mathematically nice for numerical simulation.)
I'll also add that Jakobsen does use the penalty method for collision response, which uses springs at interpenetration points to resolve collisions over a series of time steps. He uses potential functions instead of linear springs, but the idea is the same, and these penalty forces (forces that are functions of displacement---interpenetration depth) can lead to instability.
The way Jakobsen deals with this aspect of the simulation is to use an implicit solver instead of the more commonly-discussed (and maybe used) explicit solvers. Implicit solvers can deal with extremely stiff springs, even springs approaching infinite stiffness.
I wrote a paper on some of this---the finer details of why the heck numerical methods go unstable---and presented at GDC 2001. If you really want to dig into the math more, you can download my paper and presentation at:
GDC 2001 Archives
Look for my name.
Just to clarify things a little. Am I right to say Verlet Integration alone is an explicit solver? It is only the combination with iterative method(Jacobi or Gauss-Seidel iteration) that makes it an implicit solver.
Quote:Original post by Mystery
Just to clarify things a little. Am I right to say Verlet Integration alone is an explicit solver? It is only the combination with iterative method(Jacobi or Gauss-Seidel iteration) that makes it an implicit solver.
You're partially correct. Verlet integration is, by definition, an explicit solver. You need not ever use an iterative method to find the solution to a series of equations represented using the difference formulas of Verlet integration. (You could, but you shouldn't. It'd be a 100% waste of effort.) And, in fact, you need not ever use iterative or direct solvers (Gaussian Elimination type) for any of the explicit integrators. With explicit methods you can find the solution directly, one equation at a time, since none of the equations are coupled (all equations contain exactly 1 unknown value and no two equations contain the same unknown value).
Implicit integrators are those specific methods that require the use of an iterative or direct solver for systems of equations (such as the Jacobi and Gauss-Seidel methods, the Gaussian Elimination family of direct solvers, or other direct solvers such as the Thomas method for tridiagonal systems). These integrators produce equations that contain more than 1 unknown value and multiple equations share the same unknown. A simple example of an implicit integrator is the implicit Euler method (which is different from the straight "Euler" methods usually discussed around here).
Hi, Mystery.
There are two parts to your simulation:
1) Equations of motion: the F=ma type stuff, and getting velocity and position from acceleration (forces, gravity, etc.) This is using the Verlet integrator, which is explicit.
2) Satisfying constraints: this is where your "sticks" come into play, or contact with the ground. For this you are using an iterative point Gauss-Siedel solver, which is implicit. If you were using springs instead of sticks, then the springs would generate forces, which would go back into the Equations of Motion category.
because of the two different sections of your solver, I would call it a hybrid system.
There are two parts to your simulation:
1) Equations of motion: the F=ma type stuff, and getting velocity and position from acceleration (forces, gravity, etc.) This is using the Verlet integrator, which is explicit.
2) Satisfying constraints: this is where your "sticks" come into play, or contact with the ground. For this you are using an iterative point Gauss-Siedel solver, which is implicit. If you were using springs instead of sticks, then the springs would generate forces, which would go back into the Equations of Motion category.
because of the two different sections of your solver, I would call it a hybrid system.
Thanks all for the explanations.
Lonesock:
Could you take a look at this thread:
http://www.gamedev.net/community/forums/topic.asp?topic_id=291135
Would love to hear some advice from you. I believe you will nt encounter such a problem because you lock all the points to plane they are of a certain height.
Lonesock:
Could you take a look at this thread:
http://www.gamedev.net/community/forums/topic.asp?topic_id=291135
Would love to hear some advice from you. I believe you will nt encounter such a problem because you lock all the points to plane they are of a certain height.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement