search

samizdatco / arbor

a graph visualization library using web workers and jQuery
http://arborjs.org
2.66k stars 633 forks source link

Velocity Verlet Integration #26

Open pcottle opened 12 years ago

pcottle commented 12 years ago

Would anyone be interested in a patch to add (optional) Velocity Verlet integration? You can see the algorithm here:

http://en.wikipedia.org/wiki/Verlet_integration#Velocity_Verlet

It wouldn't be a huge performance hit, but since Arbor currently uses Euler integration, the energy of the dynamical system is not conserved. One compensation for this is heavy amounts of friction, but Verlet integration would allow for simulation at low friction levels and also increase the general stability of the simulation.

Thanks, Peter

samizdatco commented 12 years ago

hi peter,

i'd definitely be interested in seeing your verlet patch. the thing that stopped me when i toyed with the idea a year ago was figuring out how to repurpose the euler state variables (since each particle under verlet just has a velocity and no acceleration, right?). was it tough to bolt another integrator on top of the existing one?

One compensation for this is heavy amounts of friction

something that's been in the back of my mind for a while now is that a lot of the jumpiness in arbor's current behavior is probably due to its dead-simple hooke's law implementation. if the springs had a damping term i'm sure everything would be much less prone to exploding: http://en.wikipedia.org/wiki/Harmonic_oscillator#Damped_harmonic_oscillator don't suppose you'd be interested in tackling that would you?

in any case, looking forward to seeing your code, christian

pcottle commented 12 years ago

Hi Christian,

Thanks for the quick reply back. In terms of the euler state variables, velocity verlet integration only requires one extra variable - the acceleration at the previous time step. The rest is just making sure you update your position, velocity, and acceleration in the right order.

Verlet integration is really important for gravity simulators, for there is no friction in outer space so the energy of your system can blow up quite rapidly. I wrote an n-body simulator last semester for a course project. The overall loop (with comments) for Verlet integration can be seen here:

https://github.com/pcottle/gsim/blob/master/glut_example.cpp#L1666

I've only toyed around the idea right now; since there's interest, I'll crank out a patch this weekend to see the performance differences.

Springs with dampening is a good idea, but that's essentially just another way to strip energy out of the system. That might be a bit harder to implement as well, because you would need to know the velocity for each spring in the system relative to the nodes it is connected to. This might reduce the simplicity of the code.

Finally, a video of the project is here if you're interested. Several thousand timesteps later, the particles have the same orbits as they do initially: http://www.youtube.com/watch?v=r_68uPETMJk

Regardless, I'll hopefully have a patch this weekend to show. Thanks again, Peter