I've been implementing a somewhat simple physics engine for a project I've been working on. Since about last June I've been researching different ways of doing it. I started with Euler, then moved on to Verlet. Both have problems, though with different things. Verlet has issues with things like velocity limiting and collisions (specifically, making them respect proper physics rules, like conservation of momentum). Euler has issues with rigid constraints, and alot of instability can occur if forces become rather large. Dissatisfied, I decided to look for more schemes to use. I found references to "leap frog" and "velocity" versions of verlet in the Jakobsen article. Leap frog didn't really appeal to me, but velocity verlet certainly did. This short article describes the method Since you have an explicit velocity term, velocity limiting and collision response become as easy as they were in Euler. Since it's a verlet scheme, it inherits all the stability and rigid constraint advantages of the more regular verlet method. I've already done the simpler aspects of my physics demo (collision response between spheres, rigid in-bounds constraints, etc.) in velocity verlet, and I'm quite pleased. I simply don't see anything that would indicate it's inferior in any way to either the regular verlet or Euler. Why then can't I find any game-related literature on it? Every reference I find to it is related to particle simulations in legitimate physics research. Things like explosion simulators and atomic interaction simulations. Is there some hiccup to using velocity verlet I'm not seeing? Maybe everyone is just following that Jakobsen article without doing any further research?

That's a bold assertion Sneftel. I disagree.

They are mathematically equivellant, and have similar orders of convergence. However, in practice they work quite differently, as my experience at the very least can attest.

Take for instance collisions. In regular verlet, since you don't have explicit control over velocity, correct collision response becomes difficult. Anyone whose ever tried to use verlet as their main integration method for their physics engine can probably attest to this, I found such problems discussed quite often during my research.

Verlet is absolutely beautiful at handling projections and other constraints. Push the ball off the wall, keep the stick rigid, etc. It fails, however, at tasks that are less rigid.

One account in particular (which I can't seem to find at the moment, but I may be able to look up if anyone is interested) describes how a programmer became enamored with verlet after reading Jakobsen's article, and suggested using it to his boss. They ran into serious problems down the road and had to use several hacks to get the physics to look right in their project, which the author was most displeased with. I was having similar problems.

Velocity verlet has several advantages over vanilla verlet, addressing the pitfall I described above:

Source 1
Source 2
Source 3

note that none of the above really seem to be game-related, which is what I really find curious. Game programmers seem to have really dropped the ball IMO. I would expect to find even a reference somewhere, something to show that someone involved with video games tried it even once.

To sum it all the sources up, velocity verlet allows for more precise treatments of velocities (absolutely a necessity for proper collision response) and updates all variables from the previous time step only, as opposed to vanilla verlet which updates from the previous two time steps. It does require more vectors to be stored than vanilla verlet, and is slightly more computationally expensive.

edit:
Oh, I forgot to respond to the second part of your post.

I did try using the Runge-Kutta method. I found it overkill for my purposes, and too slow. At least compared to Euler and Verlet, etc. I could see it being useful if you're running a very precise simulation, where numerical accuracy is paramount, but I think that's the exception instead of the rule for game physics.

2nd edit:
This article describes the problems of using regular verlet

Apparently the velocity term is far more inaccurate than the position term.

[Edited by - Numsgil on February 12, 2006 12:07:51 AM]

Quote:Original post by Numsgil
Take for instance collisions. In regular verlet, since you don't have explicit control over velocity, correct collision response becomes difficult. Anyone whose ever tried to use verlet as their main integration method for their physics engine can probably attest to this, I found such problems discussed quite often during my research.

Try this test program. The first version is really Newton-Stormer-Verlet (NSV), AKA "Semi-implicit" Euler, as velocity is computed first and used to update position (traditional Euler has the order reversed).

All of those methods compute the same result (within the limits of float precision). When using velocity-less Verlet, updating velocity explicitly is straightforward: back project the old position to directly update the effective velocity.

I would agree that NSV with stability clamping for spring-like forces and potentially unstable impulses is superior to RK2/RK4 for typical game applications. However, RK and similar higher order methods provide better behavior for high angular velocities (and for some periodic force systems with larger time steps). Also keep in mind that the higher order methods are not always more accurate (they can lose energy, and may not be symplectic), though they are generally more stable at a particular time step.

As you may find, there are many formulations for Verlet; some with RK-like properties while maintaining symplectic behavior (important for some applications). The higher order methods will require more derivative evaluations and more float ops: it's a tradeoff.

Quote:
All of those methods compute the same result (within the limits of float precision). When using velocity-less Verlet, updating velocity explicitly is straightforward: back project the old position to directly update the effective velocity.

Yes, however there is significantly more error in this velocity term than in the position term, as my second edit above explains. I don't know if this error term is significant enough to matter in games necessarily, but you add to it the conceptual overhead of not having an explicit velocity term, and I don't see any significant advantage at all.

It's all a matter of your needs of course. Most games, however, generally follow similar needs. One of those needs is having a velocity term for several different calculations (collisions in particular). You'll probably be saving the velocity term to a variable instead of recalculating it several times if you use vanilla verlet.

If that's the case, vanilla verlet doesn't save you any vectors in storage. Even if that wasn't the case, a measly one extra vector to give you explicit control over velocity seems worth it to me at least. Admitedly, the implementation is slightly more complex, but I doubt it's above the head of anyone who understands verlet.

There are a whole family of verlet-esque algorithms that don't really seem explored, which I guess is what I have issue with. They all have strengths/weaknesses, (though some are clearly superior to others in all but extreme cases) but any articles game-related on physics only makes a passing reference to leap-frog and velocity versions without exploring why the author picked vanilla verlet.

Case in point:

Article on Molecular Dynamics Simulations

Near the bottom, there is a small passage on integration techniques, exploring the pros/cons of each method. It also lists something called "Beeman's algorithm" which I haven't found mentioned even in passing on any game sites.

This stuff isn't hard to find, I'm just wondering why no one's made a survey of it for game physics specifically.

Quote:Original post by Numsgil

Quote:
All of those methods compute the same result (within the limits of float precision). When using velocity-less Verlet, updating velocity explicitly is straightforward: back project the old position to directly update the effective velocity.

Yes, however there is significantly more error in this velocity term than in the position term, as my second edit above explains. I don't know if this error term is significant enough to matter in games necessarily, but you add to it the conceptual overhead of not having an explicit velocity term, and I don't see any significant advantage at all.

From experience, the following methods are simple and fast, with no major issues for simple game applications when used with force/acceleration clamping (including very stiff springs for vehicle suspensions). Generalized constraints are most easily handled using big-matrix (semi-implicit (solved simultaneously) optimization-based: LCP/Jacobi/PGS) formulations (though I have so far gotten away with a pure impulse-with-tricks methodology):

v += a*dt
x += v*dt

or

v += a*dt*dt
x += v // v is prescaled, now a displacement

First best results, use a fixed time step. The following is then possible:

dt2 = dt*dt

...

v += a*dt2
x += v // v is prescaled, now a displacement

Quote:Original post by John Schultz

Quote:Original post by Numsgil

Quote:
All of those methods compute the same result (within the limits of float precision). When using velocity-less Verlet, updating velocity explicitly is straightforward: back project the old position to directly update the effective velocity.

Yes, however there is significantly more error in this velocity term than in the position term, as my second edit above explains. I don't know if this error term is significant enough to matter in games necessarily, but you add to it the conceptual overhead of not having an explicit velocity term, and I don't see any significant advantage at all.

From experience, the following methods are simple and fast, with no major issues for simple game applications when used with force/acceleration clamping (including very stiff springs for vehicle suspensions).

There is something to say for straightforwardness and the ability to plop down off the top of your head. That's why bubble-sort still exists (though not without controversy).

However if Euler alone was adequate, I don't think that Jakobsen article would even be around. There are solutions that are moderately more complex and generally more stable, meaning the range of forces you have to clamp is diminished.

We aren't even talking hundreds or even tens of lines of code. The code from my engine using velocity verlet as it stands (it uses a time step of 1):

pos += vel + 0.5f * oldImpulse / mass;
vel += (oldImpulse + Impulse) / (2 * mass);
oldImpulse = Impulse;

The same code would look in Euler like:

vel += Impulse / mass;
pos += vel;

The difference is so minor, I don't see why you wouldn't take the (I'm assuming) better method on a larger project. There is a slightly higher computational overhead, but I can't imagine it actually being a bottleneck for any modern game. Especially since the code in my engine could be further optimized if need be.

Quote:
Generalized constraints are most easily handled using big-matrix (semi-implicit (solved simultaneously) optimization-based: LCP/Jacobi/PGS) formulations

A little off topic, but are there any resources for constraint solving in games other than relaxation shown in the Jakobsen article? My matrix skills are a little rusty, and most of the methods I find described in math articles are matrix based. I'm sure the final implementation of a Jacobi or other technique would involve matrices, but some source is always nice ;)

Quote:Original post by Numsgil
pos += vel + 0.5f * oldImpulse / mass;
vel += (oldImpulse + Impulse) / (2 * mass);
oldImpulse = Impulse;

I experimented with similar methods (effectively applies a low-pass filter on the velocity update) while trying to get cheap RK-like (multi-derivative/higher order) methods by staggering the calculations and averaging.

Quote:Original post by Numsgil
The same code would look in Euler like:

vel += Impulse / mass;
pos += vel;

If you have a simple demo that shows the first method provides better behavior than the second, other developers might find it interesting.

Quote:Original post by Numsgil
A little off topic, but are there any resources for constraint solving in games other than relaxation shown in the Jakobsen article? My matrix skills are a little rusty, and most of the methods I find described in math articles are matrix based. I'm sure the final implementation of a Jacobi or other technique would involve matrices, but some source is always nice ;)

See the ODE and Doom III source code. See also the Bullet forum (active discussion on LCP, PGS, etc.).