Integration methods
From DmWiki
Integration is the inverse of differentiation. It is the summation of a function's value over a varying parameter, such as time. In a situation such as game physics, integration is discrete; that is, you are approximating the integral by calculating the value of a function at various times.
For example, consider a simple moving particle in a game world. To calculate the next point in its path, one needs to know its current position, velocity and acceleration. We will denote these by p, v and a respectively.
At each time-step of length Δt,
Hence, we can calculate our next position (pn + 1) by simply knowing how fast we're currently moving (vn). We could calculate our acceleration by using Newton's second law.
This is simple Euler integration. Other methods include Runge-Kutta and Verlet integration. Euler is an unstable but very fast and simple method for numerical integration; other methods are more complex to implement, but give better results.
| Table of contents |
Numerical integration methods suitable for use in game physics
- Euler
- Euler midpoint method
- Leapfrog method
- Runge-Kutta order 4 (RK4)
- Verlet
- Adaptive methods
Each of these methods will be discussed briefly below.
Euler integration, and variations
Main article: Euler integration
Euler integration is the simplest and most ubiquitous form of integration. Mathematically, it involves simply evaluating the derivative of a function at a certain time, and linearly extrapolating based on that derivative to the next time step. This is fast and works well for "outer-space" simulations (where objects move in straight lines and interact infrequently) but leads to numerical instability even in as simple a situation as viscous drag or a spring.
The Euler method can be improved slightly by using the midpoint method. In this case, the derivative is first evaluated at the current time, then the simulation is linearly extrapolated by half of a time step; then the derivative is evaluated again (at the "midpoint" of the time step) and the simulation is re-extrapolated from its original state using the new derivative. This is actually a second-order Runge-Kutta method.
A second variation on Euler integration is called the leapfrog method. Instead of updating the velocities and the locations of the simulated bodies at the same time, we first update the locations, then update the velocities using force calculated from the new value of the locations. This has about the same computational cost as the Euler method, but is much more stable. For more information, see the main article.
Runge-Kutta integration
Main article: Runge-Kutta integration
The fourth-order Runge-Kutta method is more than stable enough for most purposes; its disadvantage is that it requires four evaluations of the derivative, and so it can be quite slow. See the main article for more information.
Verlet integration
Main article: Verlet integration
Originally developed for use in molecular dynamics simulations, the Verlet method differs from all the others in that it does not store explicit velocities. Instead, the positions of all objects at both time tn and tn - 1 are stored. This "velocityless" representation allows Verlet to be extremely stable in cases where there are large numbers of mutually interacting particles, such as in a piece of cloth or a ragdoll. However, Verlet is not quite as physically accurate as some of the other methods; its results are only physically "plausible" (which is usually quite good enough for games).
Adaptive methods
A simple physics simulator uses a fixed time step. However, almost all integration methods can be extended to work with variable time steps. This allows the game to dynamically control the tradeoff between speed and accuracy; where accuracy is not an issue, the time step can be increased to move faster, and where necessary the time step can be decreased for greater accuracy.
Monte Carlo integration
Main article : Monte Carlo integration
In some simulations, one has to deal with high-dimensional integrals that are difficult to solve directly. In these cases, a method introduced by Stanislaw Ulam comes in very handy. Monte Carlo integration works by sampling the integrand domain many times at randomly chosen points in its domain, and averaging the results. This converges towards the value of the integral as the number of samples increases. Convergence is not very good (the error goes as the inverse square root of the number of samples), but graphics computations sometimes require evaluating high-dimensional integrals, or ones with singularities in the domain. In both cases conventional numerical methods fail or are unreliable, and Monte Carlo is the best way forward. For example, ray tracing area lights and many other ray tracing problems fall into this category.
See Also
- http://rainman.astro.uiuc.edu/ddr/ddr-galaxy/parameters.htm - Contains a good discussion of different integration methods.
- http://burtleburtle.net/bob/math/multistep.html - Even more integration methods for your perusal.
