Quote:Original post by Numsgil
They are mathematically equivelant according to David Kofke of the Department of Chemical Engineering at SUNY Buffalo. See my "source 3" above (which are his lecture notes apparently). It may depend on exactly what you mean by "mathematically equivelant" of course. I'm assuming Kofke meant they are algebraic transformations of one another.
Do you have any sources for your assertion that vanilla verlet has better positional accuracy than velocity verlet?
I used to be a member of the faculty in the dept of applied mathematics and the university of colorado in boulder. I'm not too interested in the claims of a chemical engineer on the mathematical equivalence of two numerical integrators.
The Verlet method is a special case of a Stormer method. It is simply derived by adding two Taylor series in the following way. Suppose you have a differential equation of the form x'' = f(t,x(t)), where x(t) is smooth. Using a Taylor series we can write
x(t+h) = x(t) + h x'(t) + h^2 x''(t)/2 + h^3 x'''(t)/6 + O(h^4)
where h > 0. In other words, we take a small step forward in time. We can also take a small step backward in time resulting in the following series
x(t-h) = x(t) - h x'(t) + h^2 x''(t)/2 - h^3 x'''(t)/6 + O(h^4)
It is important to note that the terms with odd-order derivatives have different signs but those of even-order do not. Add these two series together and you get
x(t+h) + x(t-h) = 2 x(t) + h^2 x''(t) + O(h^4)
i.e. all odd-order terms cancel. From the original equation (and with a little rearrangement) we get
x(t+h) = 2 x(t) - x(t-h) + h^2 x''(t) + O(h^4)
Thus Verlet's algorithm has a truncation error of O(h^4). To get an approximation of the velocity, v(t), you can use
v(t) = (x(t) - x(t-h))/h + O(h)
The 'velocity' Verlet algorithm begins with the Taylor series
x(t+h) = x(t) + x'(t) + h^2 x''(t) + O(h^3)
Using the relation v(t) = x'(t), and the original equation, we get
x(t+h) = x(t) + v(t) + h^2 f(t)/2 + O(h^3)
'velocity' Verlet truncates the h^3 and higher-order terms here, so the truncation error scales like O(h^3). Here we see that the displacement in 'velocity' Verlet is one order less than the original.
The velocity is calculated in a way similar to the original Verlet method. We write out the Taylor series for the velocity
v(t+h) = v(t) + h f(t) + O(h^2)
We can also write a Taylor series from v(t+h) back to v(t)
v(t) = v(t+h) - h f(t+h) + O(h^2)
which we can also write as
v(t+h) = v(t) + h f(t+h) + O(h^2)
Combining these equations gives
v(t+h) = v(t) + (h / 2) ( f(t) + f(t+h) ) + O(h^2)
Note that this formula is implicit if the forcing depends on the velocity. Note that the truncation error is O(h^2) or one order higher than in the original Verlet method. When the forcing depends only of the displacement, the force can be calculated before calculating the velocity. Thus we get the steps
x(t+h) = x(t) + h v(t) + h^2 f(t,x(t)) / 2
f(t+h) = f(t+h,x(t+h))
v(t+h) = v(t) + (h / 2) ( f(t) + f(t+h) )
Forgive my abuse of notation, I think the meaning is clear though.
I suspect that the reason only a few methods are commonly used in games reflects the history and requirements that are particular to games:
(1) kickass physics engines are a relatively recent development
(2) physical accuracy is not so important as it is in the physical sciences
(3) the realtime demand on games is a severe constraint, although one that will probably lessen as computers become more powerful.
Games require fast, stable methods. Often the amount of memory used is a constraint too. This limits the methods that people are willing to explore. Implicit methods would be great, if only they didn't come with a high cost to memory. Multi-step methods suffer a similar fate and the additional problem of start-up problems and that changing the size of the timestep is awkward. As such, explicit methods with few function evaluations are currently the best option for most games. I believe that will change in time, and I hope that more use can be made of implicit methods so that my ragdolls will behave more stably [smile]
Oh, almost forgot. You wanted some sources "the art of molecular dynamics simulation" by rapaport; "numerical recipes" by press et al.; "solving ordinary differential equation I and II" by hairer and wanner. I also really like "computer methods for ordinary differential equations and differential-algebraic equations" by ascher and petzold.
