Verlet integration

Verlet integration is a method of calculating classical physics in a way suitable to real-time simulations on computers. It is a method with more stability with larger steps in time than the equations usually used in Newtonian physics. It is most often used for molecular dynamics and real-time computer simulation of objects. A very similar method is often used as an optimized method of water ripple simulation.

Contents

1 The algorithm 2 Constraints 3 Collision reactions 4 External links

The algorithm

Verlet is designed to be calculated over and over again by a computer, processing a set of points. Here is the usual Newtonian method of doing this:

<math>x_2=x_1+v_1 t<math>

<math>v_2=v_1+a t<math>

where <math>x_2<math> is the new position of the point, <math>x_1<math> is the current position, <math>v_2<math> is the new velocity, <math>v_1<math> is the old velocity, and t is the time step. Here is the verlet method:

<math>x_3=2x_2-x_1 + at^2<math>

Where <math>x_3<math> is the new position for the point, <math>x_2<math> is the current position, <math>x_1<math> is the old position, a is the acceleration, and t is the timestep. Yes, this equation is actually more complicated, however it allows for simplicity later, and is more stable. In other words, it is less likely to blow up (accumulate physics errors and break rigid bodies or defy physical probability) than the Newtonian equations. The verlet equations can also allow for a very simple method of resistance to movement (for instance air friction):

<math>x_3=(2-f)x_2-(1-f)x_1+at^2.\,<math>

Where f is a number representing the percentage of velocity per update that is lost to friction (0-1).

Constraints

The most notable thing that is now easier due to using verlet integration rather than Newtonian is that constraints between particles are very easy to do. A constraint is a connection between multiple points that limits them in some way, perhaps setting them at a specific distance or keeping them apart, or making sure they are closer than a specific distance. Often times physics systems use springs between the points in order to keep them in the locations they are supposed to be. However, using springs of infinite tension between two points usually gives the best results coupled with the verlet algorithm. Here's how:

<math>d_1=x_2-x_1<math>

<math>d_2=\sqrt{d_1^2}<math>

<math>d_3=(d_2-r)/d_2<math>

<math>x_1=x_1+.5d_1d_3<math>

<math>x_2=x_2-.5d_1d_3<math>

The x variables are the positions of the points, the d variables are temporary (they are added for optimization as the results of their expressions are needed multiple times), and r is the distance that is supposed to be between the two points. Currently this is in one dimension; however, it is easily expanded to two or 3. Simply find the delta (first equation) of each dimension, and then add the deltas squared to the inside of the square root of the second equation (Pythagorean theorem). Then, duplicate the last two equations for the number of dimensions there are. This is where verlet makes constraints simple - instead of say, applying a velocity to the points that would eventually satisfy the constraint, you can simply position the point where it should be and the verlet integrator takes care of the rest.

Here's what an optimized 2D verlet constraint would look like in C:

dx = x2-x1;
dy = y2-y1;
d1 = Sqrt(dx*dx+dy*dy);
d2 = 0.5*(d1-r)/d1;
dx = dx*d2;
dy = dy*d2;
x1 += dx;
x2 -= dx;
y1 += dy;
y2 -= dy;

3D:

dx = x2-x1;
dy = y2-y1;
dz = z2-z1;
d1 = Sqrt(dx*dx+dy*dy+dz*dz);
d2 = .5*(d1-r)/d1;
dx = dx*d2;
dy = dy*d2;
dy = dz*d2;
x1 += dx;
x2 -= dx;
y1 += dy;
y2 -= dy;
z1 += dz;
z2 -= dz;

Problems, however, arise when multiple constraints position a point. It is extremely hard not to violate at least one. One way to solve this is to loop through all the constraints multiple times, eventually coming to a set of positions that satisfies the constraints enough to be accurate, or have it simply loop a set number of times.

Collision reactions

One way of reacting to collisions is to use a penalty-based system. which basically applies a set force to a point upon contact. The problem with this is that it is very difficult to choose the force imparted. Too strong and objects will become unstable, too weak and the objects will penetrate each other. Another way is to use projection collision reactions which takes the offending point and attempts to move it the shortest distance possible to move it out of the other object. Simple as that. The verlet integration takes care of the velocity imparted because of the collision. For more information on how to do this, click Advanced Character Physics by Thomas Jakobsen.

External links

• Advanced Character Physics by Thomas Jakobsen (http://www.gamasutra.com/resource_guide/20030121/jacobson_01.shtml) - covers all this and more (Requires free registration)
• The verlet algorithm (http://www.fisica.uniud.it/~ercolessi/md/md/node21.html)
• Theory of Molecular Dynamics Simulations (http://www.ch.embnet.org/MD_tutorial/pages/MD.Part1.html) - bottom of page