Numerical Integrator

Physics Engine Overview

A physics engine is responsible for solving the equation of motion and for detecting collisions. You can think of a physics engine as a continuous loop. It starts off by simulating an external force such as gravity. At each new time step, it detects any collisions, then calculates the velocity and position of an object. And finally, sends the location data to the GPU. This continuous loop creates the illusion that an object is falling due to gravity.

image

Physics Engine Loop

The Physics engine is responsible for computing the resulting accelerations, velocity, and displacement of an object from forces and torques acting on the body.

In Physics engine development, the most important equations are:

Newton's second law:
image
Rotational Force (Moments, Torque):
image

These two equations are known as the Equations of Motion.

Recall that if you integrate acceleration with respect to time, you obtain velocity. If you integrate velocity with respect to time, you get displacement.

The Physics Engine integrates the Equation of Motion to obtain the resultant velocity and displacement of an object. And it does this in a continuous loop which consists of the following steps:

  1. Identify all forces and moments acting on the object.
  2. Take the vector sum of all forces and moments.
  3. Solve the equation of motion for linear and angular acceleration.
  4. Integrate the acceleration with respect to time to find the linear and angular velocity.
  5. Integrate the velocity with respect to time to find the linear and angular displacement.

If a gravitational force and torque are applied to an object, the Physics Engine loop creates the illusion that an object falls and rotates.

image

Numerical Integration

In computers, Integrals are evaluated using Numerical Integration. The reason is that computers can only approximate the value of an integral by using numerical techniques.

There are several numerical integration techniques used for solving the equation of motion. The most common are:

  • Euler Method
  • Verlet Method
  • Runge-Kutta Method

The Euler Method is simple to implement but is the least exact. The Runge-Kutta method is complicated to implement but the most precise.

image

The Untold Engine uses the 4th Order Runge-Kutta Method to evaluate the Equation of Motion.

4th Order Runge-Kutta Method

During every game-tick, the Physics Engine, U4DEngine::U4DPhysicsEngine, integrates the Equation of Motion for each 3D entity, thus computing the resultant velocity and displacement.

image

The Untold Engine uses the 4th Order Runge-Kutta Method class, U4DEngine::U4DRungaKuttaMethod, to evaluate the Equation of Motion.

image

Unlike the Euler's Method, which calculates one slope at an interval:

image

The Runge-Kutta calculates four different slopes and uses them as weighted averages. These slopes are commonly referred as k1, k2, k3 and k4. The Untold Engine computes each of these slopes at every game step.

image

Visualizing the 4th Order Runge-Kutta Method

Visually, the U4DEngine::U4DRungaKuttaMethod works as follows:

1) At time interval t0, calculate slope k1.

2) Create a triangle by projecting k1 to t+∆t.

image

3) Calculate half the height of the triangle, (∆t/2) k1, and draw a horizontal line.

4) Draw a vertical line at interval t+(1/2)∆t.

5) At this intersection point, calculate the slope k2.

image

6) Starting out with k2, create a triangle by projecting k2 to t+(3/2)∆t.

7) Calculate half the height of the triangle, (∆t/2)k2.

image

8) Translate the height to the base of the triangle formed by k1 at t+(1/2)∆t.

image

9) At this point, calculate the slope k3.

image

10) Create the another triangle by projecting k3 to t+(3/2)∆t

11) Find half the height of the triangle, (∆t/2)k3

image

12) Translate this height to the base of the triangle formed by k1 at point t+∆t

13) Find the slope k4.

image

The Runga-Kutta uses these slopes as weighted average to better approximate the actual slope, velocity, of the object. The position of the object is then calculated using this new slope.

image