 |
Author |
Topic: Help: Springs, instability, and explosions! (Read 2157 times) |
|
mflux
|
Help: Springs, instability, and explosions!
« on: Feb 19th, 2005, 2:43am » |
|
I'm working on this little app to improve my spring lattice code and I've hit a bit of a snag:
http://users.design.ucla.edu/~mflux/p5/springbody/applet/
Keep clicking the same location. Masses will start appearing and connect themselves, until all of a sudden they turn unstable and fly apart completely. Anyone have experiences with springs and know why this is happening?
In my springs.pde there is a line I commented out to constrain the spring force. The instability still occurs even when this line is in, but after many more springs are added.
The number of springs it takes to explode also seems to be related to the tension force applied to it. The greater the tension K, the easier for it to explode.
Anyone know why this is happening? Is it just a law of nature or something? Flux is totally confused.
|
|
|
|
|
Quasimondo
|
Re: Help: Springs, instability, and explosions!
« Reply #1 on: Feb 20th, 2005, 5:26pm » |
|
This is the typical numerical instability that shows up when you are using the classic Euler method to calculate you timesteps. Most people use it even without knowing its name because it's the easiest to implement. But there are other methods, one that you might have heard of is Runge-Kutta or RK4.
The problem is that I haven't yet used the latter either so I cannot explain it any more detailed, but google will help you here definitely.
|
Mario Klingemann | Quasimondo | Incubator | côdeazur
|
|
|
mflux
|
Re: Help: Springs, instability, and explosions!
« Reply #2 on: Feb 20th, 2005, 10:12pm » |
|
Thanks Quasi!
You're right I didn't even know it was called the Euler. I just assumed that's the way you calculate a spring, but taking the position of a mass, taking another mass, and moving it towards the other mass at a certain percentage.
I did some googling and uh. Holy crap. I'm hitting myself for not having taken physics OR calculus in college or in highschool. I don't understand any of it..
http://en.wikipedia.org/wiki/Runge-Kutta
http://www.myphysicslab.com/runge_kutta.html
Anyone have any experience with this? ... or care to explain it in laymans?
|
|
|
|
|
Quasimondo
|
Re: Help: Springs, instability, and explosions!
« Reply #3 on: Feb 20th, 2005, 10:52pm » |
|
I especially like the sentence in the wiki:
"The fourth-order formulation ("RK4") is the most commonly used, since it provides substantial accuracy without excessive complexity."
Yeah you bet - not a trace of excessive complexity here...
Okay I guess that I get at least a little bit of what it says. The essence of it is that you slice your timestep into 4 pieces and then take the average of those 4, but weight the middle ones twice as the begining and the end. Probably this sentence will reserve me a special place in the torture chamber of the mathematics' hell.
But I'm pretty sure that there is some ready-to-copy code for this somewhere on the internet.
|
Mario Klingemann | Quasimondo | Incubator | côdeazur
|
|
|
mflux
|
Re: Help: Springs, instability, and explosions!
« Reply #5 on: Feb 21st, 2005, 12:04am » |
|
I still don't get it. Maybe my mind is still operating on high school physics. I've been reading up and catching up on what "derivatives" and "differential equations" are, but to me these abstract concepts feel like they belong in a whole other paradigm away from objects in motion, objects colliding, and objects doing things.
Looking at: http://drewk.net/projects/ipendulum/ipendulum.html
I would never "solve" for the motion of a pendulum in its entirety, something real physicists would probably want to do. I would simply tell the pendulum to add vector forces downwards (gravity) and then add vector force of its constraint (towards whatever it's tied to). Stepping through the program simply causes the pendulum to swing, and I don't write -any- physical formulas, not even F=MA. The positions of the pendulum would already be data inside variables, so theres never a reason for me to solve for them through elaborate equations.
Perhaps I've been getting too far by learning too little? I feel completely lost in the realm of physics calculus.
In regards to solving for an average of the positions over several time steps, how would this, in any concievable way, allow an overload of springs to become stable? If it's just that, I already have many ideas of how to implement that using my own current paradigm, but I'm not sure how that would change anything...
Thanks again Quasi!
|
| « Last Edit: Feb 21st, 2005, 12:20am by mflux » |
|
|
|
|
skloopy
|
Re: Help: Springs, instability, and explosions!
« Reply #6 on: Feb 21st, 2005, 7:19am » |
|
hi mflux. you might be doing this already, but i usually multiply the particle velocities by about 0.8 every frame. You could turn down the spring force too, and that'd help, But damping with the multiply lets you use higher spring forces, so things dont happen so slowly. The bad thing is that the more damping, the more it's gonna look like balls rolling in sand, or bullets in honey.
|
|
|
|
|
mflux
|
Re: Help: Springs, instability, and explosions!
« Reply #7 on: Feb 21st, 2005, 11:22am » |
|
Hi Skloopy
I'm already damping my velocities down with a frictional force, a la
Code:
void doFriction()
{
velocity.m*=FRICTION_FORCE;
// velocity.m=constrain(velocity.m,-20,20);
}
|
|
Where the friction is 0.8 It works to some degree, but it also influences the motion of things. The final project that I'm using these springs with is to simulate the motion of underwater, so the whole "bulelts in honey" look is to my advantage anyways.
I can't set the friction any higher or else things won't look like they have inertia. Any lower, and things start to explode too quickly...
|
|
|
|
|
v3ga
|
Re: Help: Springs, instability, and explosions!
« Reply #8 on: Feb 21st, 2005, 12:12pm » |
|
Hello mflux,
maybe you could also look at Verlet integration which is another way to integrate. It is known to be a stable method, and deals perfectly with constraints. There's a nice tutorial at http://www.gamasutra.com/resource_guide/20030121/jacobson_pfv.htm . I used this method in an applet, you could take a look at http://v3ga.net/show.php?id=1&type=0 .
Back to Euler integration, two methods exist : explicit integration and implicit integration. I dont remember well the details but basically explicit method is known to make the system gain energy whereas implicit is known to make the system loose energy, preventing it from explosing. It's something like , supposing we're at (t+dt) , and having Forces(t+dt):
- Explicit :
v(t+dt) = v(t) + a(t+dt).dt
x(t+dt) = x(t) + v(t+dt).dt
- Implicit :
save v(t);
v(t+dt) = v(t) + a(t+dt).dt ;
x(t+dt) = x(t) + v(t).dt
Hope it makes sense and helps!
Julien
|
| « Last Edit: Feb 21st, 2005, 12:15pm by v3ga » |
|
http://v3ga.net
|
|
|
mflux
|
Re: Help: Springs, instability, and explosions!
« Reply #9 on: Feb 21st, 2005, 11:56pm » |
|
Hey v3ga
I read through as much about Verlet intergration as I could. From what I understand it uses the difference between the current position of a mass and the previous position of the mass to derive the velocity vector, as opposed to using the velocity vector directly. Am I wrong?
I tried implementing this and realized that, in effect, I'm already doing something extremely similar.
Here's an excerpt from update() of my Mass class (comments added for your reading):
Code:
void update()
{
oldP=new position(p); //Verlet intergration, saving the old position
if(velocity.m<.01)
velocity.m=0; //My attempt to remove errors
doFriction();
if(useGravity)
doGravity();
doVelocity();
doBorders();
if(velocity.m<.01)
velocity.m=0; //My attempt to remove errors
velocity=new vector(oldP,p); //Verlet intergration, deriving velocity
velocity.m*=.9; //damping to (hopefully) make system lose energy
}
|
|
Here is an excerpt from update() of my Lattice class, which handles all the point masses:
Code:
void update()
{
doConnectedSprings(); //accumulates forces (see below)
for(int i=0;i<nodes.length;i++)
{
nodes[i].update(); //update from above
}
}
|
|
Here is doConnectedSprings() from Lattice:
Code:
void doConnectedSprings()
{
for(int i=0;i<amount;i++)
{
if(nodes[i].c.output.length!=0)
{
for(int s=0;s<nodes[i].c.output.length;s++)
{
mass otherNode=nodes[nodes[i].c.output[s]]; //this refers to the node connected to node[i]
float distance=dist(nodes[i].p,otherNode.p);
vector f=getSpringForceVerlet(nodes[i].p,otherNode.p,nodes[i].c.distanceOut[s],tension); //see below
float forceMag=f.m;
forceMag=f.m*.25; //damping the force (again!)
float angle=f.a;
nodes[i].velocity=nodes[i].velocity.add(f.a,forceMag); //this is acceleration, by adding the force onto the velocity
otherNode.velocity=otherNode.velocity.add(f.a,forceMag*-1); //do the same in opposite direction
}
}
}
}
|
|
Finally, the last piece of the puzzle.. two flavors of getSpringForce. One is found looking up info about Verlet intergration that I just wrote and tested (it's almost identical, just not in implementation):
Code:
vector getSpringForce(position from,position to,float desiredLength,float constant)
{
vector force=new vector(from,to);
if(dist(from,to)>.5)
{
vector deltaLength=new vector(force);
position targetPos=new position(to.displace(getHeading(to,from),desiredLength)); //where the point -wants- to be
deltaLength=new vector(from,targetPos); //this is the spring force at tension 1.0
force=new vector(deltaLength);
force.m*=constant; //reduce the magnitude
}
return force;
}
//This version taken from a website about Verlet intergration
vector getSpringForceVerlet(position from,position to,float desiredLength,float constant)
{
float dx=to.x-from.x;
float dy=to.y-from.y;
float d1=sqrt(dx*dx+dy*dy);
float d2=constant*(d1-desiredLength)/d1;
dx=dx*d2;
dy=dy*d2;
position newFrom=new position(from.x+dx,from.y+dy);
vector force=new vector(from,newFrom);
return force;
}
|
|
The two do -basically- the same thing. They also both explode in your face. The thing is, I can't figure out where energy is introduced into the system, if at all. Once there are x number of nodes connected, numbers begin to bounce up inexplicably. From what I've read, this happens often in Euler integration. Is what I'm doing even considered Euler integration?
It's important that my springs don't explode, because I'm doing a more-or-less A-Life project using these springs. I don't wish to evolve exploding creatures or creatures who exploit any faults in my springs engine.
I don't quite understand your explanation of implicit versus explicit. Care to elaborate?
Finally, v3ga, I can't seem to look at your source for your SodaTest app. I don't think it's linked right, or it may no longer exist. Care to share? Thanks for your help!
|
| « Last Edit: Feb 22nd, 2005, 12:14am by mflux » |
|
|
|
|
mflux
|
Re: Help: Springs, instability, and explosions!
« Reply #10 on: Feb 22nd, 2005, 12:55am » |
|
To help others and myself, here's an explanation of Euler, improved Euler, and Runge-Kutta:
http://goanna.cs.rmit.edu.au/~crpearce/CLS/Ass1HTML/report.html
"1. Euler
Euler's method uses the gradient of the current position to estimate the position for the next step. As the gradient is calculated at only one point there is a bias towards this point. As approximations are based on previous approximations, the estimated solution gradually worsens as errors continually grow.
The Initial Value Problem (IVP) is when the gradient (in our case, velocity) is not dependant on the independant variable (in our case, time).
Both Euler and Improved Euler integration methods solves the Initial Value Problem (IVP) by estimating an initial position in the following manner: x(t0) = x0 where x is position (y-axis) and t is time (x-axis).
2. Improved Euler
The Improved Euler's method extends Euler's method by taking an average of two gradients, resulting in closer extrapolations. As two points of references are used instead of one, there is less bias to a particular reference. Errors are generally either negative or positive and tend to cancel each other out. This reduces the effect of gradual deteriation due to error accumulation.
As discussed, both Euler and Improved Euler (a second order Runge-Kutta) numerical methods use linear extrapolation to perform the integration. A better method is Runge-Kutta which uses polynomial extrapolation.
3. Runge-Kutta
The Runge-Kutta numerical method estimates a new position by using a polynomial to fit the graph function. Our assignment uses a fourth order Runge-Kutta method, evaludating the function at four different points. Gradients are calculated at each point and a weighted average is used to estimate the new position.
This is the most accurate of the three method described here, as you will see with the graphs further on. "
|
|
|
|
|
skloopy
|
Re: Help: Springs, instability, and explosions!
« Reply #11 on: Feb 22nd, 2005, 8:15am » |
|
It seems like what you want to do shouldn't be this complicated. Are you calculating the spring forces with angle and magnitude? It might be simpler to just use x and y velocity. I'm not sure if it's as accurate, but this is how i've been doing it.
It might not help you any, but I stripped down the code I usually use for springs and made this little demo. It's still euler (i think) so it can explode, but it's no problem if you keep the forces under control and use the damping (friction).
http://elfman.vendetta.com/ryan/p5/simplesprings
|
|
|
|
|
v3ga
|
Re: Help: Springs, instability, and explosions!
« Reply #12 on: Feb 22nd, 2005, 1:26pm » |
|
Yes, verlet integration is about taking current position and old position for an approximation of velocity. I didn't fully read your implementation, but as Skloopy pointed it out, it seems to be quite 'complicated' for what you want to achieve. Sorry for the source code missing, it appears that I didn't even have it on my HD  Anyway, you could take a look at http://v3ga.net/show.php?id=3&type=0 ( class VerletPhysicsEngine ). The verlet integration is basically an iterative method, in a sense that the engine tries to satisfy each constraint at the same time while slowly converging to a solution.
Concerning explicit vs implicit, I didn't remember well the details ( I gave you raw stuff as I remembered it ) but here's a link that can enlighten you http://www-2.cs.cmu.edu/~baraff/sigcourse/slidese.pdf . More generally, all papers by Baraff & Witkin are good to read when you start to play with physics.
Cheers
|
| « Last Edit: Feb 22nd, 2005, 1:27pm by v3ga » |
|
http://v3ga.net
|
|
|
marcello
|
Re: Help: Springs, instability, and explosions!
« Reply #13 on: Feb 22nd, 2005, 3:14pm » |
|
Hi,
i'm working to a similar project since a couple of years. I'm working to a 3d version of sodaplay and i'm doing this using processing. The applet it is definitively ready in its game functionality (contruction-interaction) and now i'm working to allow users to save and load their own models in my web space. I'm doing this using a php script between the applet and the database. It is a bit difficult for me since i'm learning php just in these days, but i've already solved the main difficulties.
Time ago i wrote a long paper about sodaconstructor where i also taked about runge-kutta methods. You'll find it at this url:
http://www.sodaplaycentral.com/features/paper.php
If you want to see an old (april 2004) preview of my applet, you'll find it clicking my home address. That is an old non-interactive version. Now it is possible also to construct models and to interact with them. In few time i'll release the final version. I used an adaptive stepsize runge-kutta alghoritm and the result is a really very stable simulation.
Best Regards,
Marcello
|
| « Last Edit: Feb 22nd, 2005, 3:16pm by marcello » |
|
|
|
|
mflux
|
Re: Help: Springs, instability, and explosions!
« Reply #14 on: Feb 24th, 2005, 12:26am » |
|
Hey guys thanks for all your help!
I'm going to lay off on the springs code for a week (suggested by Casey... lol) and work on the rest of my project before coming back and fixing it. Next week I'll do a super simple implementation of Runge-Kutta and see if it works, and possibly a new thread.
Thanks again!
|
|
|
|
|
|
