A Simple Time-Corrected Verlet Integration Method
A Simple Time-Correction SchemeThe remaining fundamental problem with the Verlet integration method lies with its assumption of a constant time step. The (xi - xi-1) term from equation (4a) is the portion of the equation which is dependent on the constant acceleration and constant time step assumptions. It has been explained (OK, hand-waved away) why the usage of the last time step's acceleration will not be corrected, but we still have the problem of dti-1 being stale information. Rewriting equation (4) yet again, we see that: (4b) xi - xi-1 = (vi - 0.5 * ai-1 * dti-1) * dti-1 so taking the easy way out and ignoring the dti-1 linked with the acceleration, I can swap out the old dti-1 for my new dti by multiplying (4b) by (dti / dti-1). Plugging all of this in yields my final form of the Time-Corrected Verlet integration method: (7) xi+1 = xi + (xi - xi-1) * (dti / dti-1) + a * dti * dti You will notice that when the last frame's time step equals the current frame's time step, the modifier term becomes 1.0, yielding the traditional form of the Verlet equation. As an optimization note, only one value needs to be stored per frame, as the dt was constant for all points in the last frame. So the term (dti / dti-1) can be computed once per frame and stored in a variable. At the end of the Verlet update subroutine simply store the current frame's dt as old_dt. Likewise, dti * dti can be computed once and stored in a variable, saving a multiplication. To show how the Time-Corrected Verlet behaves, a spreadsheet was set up with the TCV, the original Verlet and Euler's method, each simulating three different problems with known solutions. These are the same tests as were performed earlier, but with randomized time steps. Of course since every time step (except the first) was random, the graph looked different each time a simulation was "run". Sometimes both the original Verlet and the TCV simulations were similar, however the original Verlet always fell further away from the exact solution than the TCV version eventually. Here are some sample graphs: ConclusionUsing the Time-Corrected form of the Verlet integration method with the proper equation for initializing the state makes the TCV integration scheme a simple, yet powerful method for doing game physics, even with changing frame rates. It restores some of the accuracy of the method (still 4th order with constant time steps, between 2nd and 4th with changing dt), while maintaining its cheap numerical cost. I hope this helps a bit when implementing your own physics simulation code. |
|