Introduction
When creating physics simulations, a mathematical model that describes the motion of the bodies - equations of motion - must be created. Then those equations of motion must be solved.
Numerical integration is the branch of numerical analysis that deals with the solution of differential equations. Fundamentally, we need an interation scheme to simulate motion because it involves solving Newton's second law of motion which is a a diferential equation.
As a reminder, Newton's second law is \(F = ma\).
Acceleration is actually a derivative of velocity \(a= dv/dt\), so that we can rewrite the second law as:
\[F=m\frac{dv}{dt}\]
This is so called a first order differential equation with respect to velocity because it involves the first derivative of velocity.
By recalling that \(v= dx/dt\), and expressing force \(F\) as a function of position and velocity, we can rewrite this as:
\[F(x,t)=m\frac{d^2x}{dt^2}\]
This is now a second order differential equation with respect to displacement, as it relates the second derivative of the position to the force applied.
In principle, the precededing differential equation can be solved by integrating analytically or numerically to yield the diplacement \(x\) and velocity \(v\) as a function of time. Specifically you can integrate the first equation to arrive at velocity, then integrate the velocity to arrive at displaycement.
Analytical solution
For simple equations of motion, you can use calculus and other mathematical techniques to find the exact solution. This is called the analytic solution. It is also referred to as a closed form solution.
Numerical solution
Most physics simulations (even relatively simple ones) are too complicate to be able to find an analytic solution. Instead numerical analysis is used to find an approximate solution.
Problem Statement
Let an initial value problem be specified as follows:
\[v= \frac {dx}{dt}=f(x, t),\quad x(t_{0})=x_{0}\]
The displacement \(x\) is an unknown function of time \(t\), which we would like to approximate.
We are told that velocity \(v=\frac{dx}{dt}\), the rate at which \(x\) changes, is a function of time \(t\) and of \(x\) itself.
At the initial time \(t_0\), the corresponding \(x\) value is \(x_0\). The function \(f\) and the initial conditions \(t_0,\, y_0\) are given.
Given \(x_n\) and \(t_n\) we want to calculate an approximation for \(x_{n+1}\) at a brief time later, \(t_{n+1}=(t_n+h)\), where \(h\) is the step-size, ie the "brief time".
The above is indeed what a physics simulation needs to solve, using numerical integration.
Popular Integration Methods
There are many numerical integration methods. In this post we will look at probably the simplest of such methods called the Euler method, including a number of its variants.
- Explicit Euler method (often referred to simply as Euler method)
- Implicit Euler method (also referred to as Backward Euler)
- Semi-Implicit method (Symplectic Euler method)
Euler method
The simplest method is to use finite difference approximations.
From any point on a curve, you can find an approximation of a nearby point on the curve by moving a short distance along a line tangent to the curve.
\(x′\) is replaced by the finite difference approximation\[x'(t)\approx {\frac {x(t+h)-x(t)}{h}}\]
which when re-arranged yields the following formula
\[x(t+h)\approx x(t)+hx'(t)\]
which gives:
\[x(t+h)\approx x(t)+hf(x(t), t)\]
This formula is usually applied in the following way.
We choose a step size h, and we construct the sequence \(t_{0},t_{1}=t_{0}+h,t_{2}=t_{0}+2h\),... We denote by \(x_{n}\) a numerical estimate of the exact solution \(x(t_{n})\). These estimates can be calculated by the following recursive scheme
\[x_{n+1}=x_{n}+hf(x_{n},t_{n})\]
or,
\[x_{n+1}=x_{n}+k_1\]
where \(k_1=hf(x_{n},t_{n})\)
\[x_{n+1}=x_{n}+k_1\]
where \(k_1=hf(x_{n},t_{n})\)
This Euler method is an example of an explicit method. This means that the new \(x_{n+1}\) is defined in terms of things that are already known, like \(x_n\).
Sometimes our differential equation which requires solving is something like below where we start with the second derivative, like in Newton's second law (acceleration is function g of x and t):
\[F=ma=m\frac{d^2x}{dt^2}=mg(x,t)\]
For this second derivative ODE we can apply Euler's method by defining:
For this second derivative ODE we can apply Euler's method by defining:
\[v=\frac{dx}{dt}\]
which menas our differential equation becomes
\[\frac{dv}{dt}=g(x_n,t_n)\]
which is solved by using the Euler method:
which is solved by using the Euler method:
\[v_{n+1}=v_n+hg(x_n,t_n)\]
This gives us two Euler equations:
\[x_{n+1}=x_{n}+hf(x_{n},t_{n})\]
\[v_{n+1}=v_n+hg(x_n,t_n)\]
Writing this in terms of variable names more familiar to games programming gives:
\begin{aligned}x_{n+1}&=x_n+v_n\cdot \Delta t\\v_{n+1}&=v_n+a_{n}\cdot \Delta t\end{aligned}
This is the forward Euler method, in contrast with a similar but different backward Euler method described later.
\(x(t)\) can be expressed as follows by means of Taylor's expansion.
\[x(t+h)=x(t)+hx'(t)+\frac{1}{2!}h^2x''(t)+\frac{1}{3!}h^3x'''(t)+\cdots\]
You can see that the Euler method is simply the above equation with exerything after the first two terms truncated.
Writing this in terms of variable names more familiar to games programming gives:
\begin{aligned}x_{n+1}&=x_n+v_n\cdot \Delta t\\v_{n+1}&=v_n+a_{n}\cdot \Delta t\end{aligned}
This is the forward Euler method, in contrast with a similar but different backward Euler method described later.
Error term
\(x(t)\) can be expressed as follows by means of Taylor's expansion.
\[x(t+h)=x(t)+hx'(t)+\frac{1}{2!}h^2x''(t)+\frac{1}{3!}h^3x'''(t)+\cdots\]
You can see that the Euler method is simply the above equation with exerything after the first two terms truncated.
Euler formula would be correct if all derivatives beyond the first were zero, otherwise there is an error. The error is described as \(O(h^2)\).
\[x_{n+1}=x_n+k_1+O(h^2)\]
\[x_{n+1}=x_n+k_1+O(h^2)\]
Energy of the system
I will not delve into the details here, but using forward Euler integration has a tendency to "add" energy, thereby violating the energy conversation principle. For physics simulations this is a problem (for a very good explanation, see here).
This is the backward Euler method which uses the following approximation.\[y'(t)\approx {\frac {y(t)-y(t-h)}{h}}\]
which, following the same derivation process as above gives:\[y_{n+1}=y_{n}+hf(t_{n+1},y_{n+1})\]Writing this in terms of variable names more familiar to games programming gives:\[\begin{aligned}v_{n+1}&=v_n+a_{n+1}\cdot\Delta t\\x_{n+1}&=x_n+v_{n+1}\cdot \Delta t\end{aligned}\]
This relies on knowing the future value of acceleration \(a_{n+1}\); hence "implicit". This tend not to be used for games physics simulations.
This is probably the most popular method, used by a lot of game physics engines.
Implicit Euler method
This is the backward Euler method which uses the following approximation.\[y'(t)\approx {\frac {y(t)-y(t-h)}{h}}\]
which, following the same derivation process as above gives:\[y_{n+1}=y_{n}+hf(t_{n+1},y_{n+1})\]Writing this in terms of variable names more familiar to games programming gives:\[\begin{aligned}v_{n+1}&=v_n+a_{n+1}\cdot\Delta t\\x_{n+1}&=x_n+v_{n+1}\cdot \Delta t\end{aligned}\]
This relies on knowing the future value of acceleration \(a_{n+1}\); hence "implicit". This tend not to be used for games physics simulations.
Semi-Implicit Euler method
This is probably the most popular method, used by a lot of game physics engines.
\[\begin{aligned} v_{n+1}&=v_n+a_{n}\cdot \Delta t\\ x_{n+1}&=x_n+v_{n+1}\cdot \Delta t \end{aligned}\]
Current acceleration is used to calculate the future velocity which is then used to approximate the future position.
http://www.physics.umd.edu/hep/drew/numerical_integration/
Useful References
https://gdcvault.com/play/1022196/Physics-for-Game-Programmers-Numerical (presentation by Erin Catto)
https://gdcvault.com/play/1022197/Physics-for-Game-Programmers-Numerical (powerpoint to go with the above)
0 件のコメント:
コメントを投稿