For a game character to experience physics, a game engine needs to compute the equations of motion, collision, contact points, etc. There is a set of basic algorithms that aids a character experience such effects. For example, the Runge-Kutta Method computes the Equations of Motion using numerical integration methods. The Gilbert-Johnson-Keerthi (GJK) algorithm detects collision using the Minkowski Difference. The Sutherland-Hodgman algorithm identifies collision contact points by clipping a polygon.
Numerical Integration Methods
Calculating the equations of motion allows a character to fall as if gravity was acting on the object. The Equations of Motion are Newton's Second Law:
and Rotational Force:
A game engine integrates the Equations of Motion to obtain the velocity and displacement of a character. The engine does this operation in a continuous loop which consists of the following steps:
- Identify all forces and moments acting on the object.
- Take the vector sum of all forces and moments.
- Solve the equation of motion for linear and angular acceleration.
- Integrate the acceleration with respect to time to find the linear and angular velocity.
- Integrate the velocity with respect to time to find the linear and angular displacement.
If a character experiences gravitational and torque forces, the continuous loop creates the illusion that an object falls and rotates.
The problem is the Integration of the acceleration and velocity. Computers can only approximate the value of an integral by using Numerical Integration techniques.
There are three numerical integration methods used in game engine development. They are:
- Euler Method
- Verlet Method
- Runge-Kutta Method
The Euler's Method calculates the velocity at a time interval and predicts the next velocity at t+∆t. The method is simple to implement yet it is the least accurate.The illustration below shows the shortcoming of this approach. You can argue that making ∆t smaller, the closer you'll get to the exact solution. However, there is a practical limit as to how small a time step you can take.
The Runge-Kutta Method is a numerical integration technique which provides a better approximation to the equation of motion. Unlike the Euler's Method, which calculates one slope at an interval, the Runge-Kutta calculates four different slopes and uses them as weighted averages.
These slopes are commonly referred as k1, k2, k3 and k4, and an engine needs to compute them at every time step.
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.
Collision Detection
Detecting collisions has trade-offs. A simple collision detection system is fast but unprecise. Whereas, a complex collision detection system is precise but very computationally expensive.
During collision detection, an engine bounds a game character with a geometrical volume. This volume is known as a Boundary Volume. And the most common are:
- Sphere
- OBB
- AABB
- Convex Hull
A collision detection system works by detecting if boundary volumes are intersecting. A system that uses Spherical Boundary Volumes are fast but returns many false detections.
Back in the 1980s, I'm sure a detection system using spherical boundary volumes was acceptable, but nowadays, gamers may not be so happy with many false detections.
A more precise detection system uses Convex Hulls as boundary volumes.
The intersection between Convex Hulls is computed using the Gilbert-Johnson-Keerthi (GJK) algorithm. Surprisingly, the mathematics behind this algorithm is quite simple. The algorithm determines if the volumes have intersected if their Minkowski Difference contains the origin point. The image below illustrates two convex hulls intersecting (left). Since the Minkowski Difference (right) includes the origin point, the algorithm reports the intersection.
Even though the mathematics behind the GJK algorithm is simple, it is very computationally expensive.
A collision system circumvents calling the GJK algorithm for every possible collision through a Two-Phase Detection System. These phases are known as Broad-Phase and Narrow Phase detection.
A Broad Phase detection system detects collision using spherical boundary volumes. This phase is fast and reports any possible collision to the Narrow Phase. The Narrow Phase tests the reported collision, but it uses the more expensive and precise GJK algorithm.
To further minimize calls to the GJK algorithm, a game engine parses the space of game characters and creates a tree-like structure known as a Boundary Volume Hierarchy (BVH).
The BVH algorithm parses the position of every object and assigns them to a particular node in the binary tree. The algorithm recursively analyzes each node until each node contains two characters most likely to collide.
Collision Response
A collision detection system reports if a collision has occurred. Unfortunately, it does not report the Contact-Manifold (contact points) of the collision. The contact-manifold are essential to determine the Collision Response (impulse and resulting velocities) of collided characters.
A game engine uses the Sutherland-Hodgman Algorithm to compute the contact manifolds of two colliding characters. The algorithm starts off by identifying a Reference and an Incident polygon.
The segments of the reference polygon serve as Reference Planes for the algorithm.
Once a reference polygon is identified, the algorithm tests each vertex of the incident polygon against each reference plane by using a Clipping rule.
Upon termination, the algorithm generates a new polygon whose vertices are the contact points (Contact Manifold) of two collided polygons.
Visualizing Game Engine Algorithms
Now that you know these game engine algorithms, you may want to know how to implement them. Several books go straight into the implementations of these algorithms without giving you a visual depiction of how they work. I think that if you can see a visual representation of an algorithm, you can implement them easier and faster. Thus, I wrote several posts where I provide a visual explanation for each algorithm. I hope they are helpful:
- Visualizing the Runge-Kutta Method
- Visualizing the GJK Algorithm
- Visualizing the BVH Algorithm
- Visualizing the Sutherland-Hodgman Algorithm
Enjoy.
PS. Sign up to my newsletter and get Game Engine development tips.
