Collision Detection System

Detecting collision is extremely time-consuming. Thus, on every game-tick, the Untold Engine parses the game scene and creates a tree-like structure to determine which entities are most likely to collide. The Engine then divides the Collision Detection into two processes: Broad Phase and Narrow Phase.

The Untold Engine delegates collision detection to U4DEngine::U4DCollisionDetection and its inner workings are summarized in the image below:

image
  1. The scene's space is parse and a tree-like structure known as a Boundary Volume Hierarchy Tree is computed
  2. Entities most likely to collide are sent to the Broad-Phase Stage
  3. Entities that pass the Broad-Phase stage, are sent to the Narrow-Phase stage

As the physics engine hands down objects to the collision system, the objects are wrapped with bounding volumes. The most traditional bounding volumes are Spheres, Axis-Aligned Bounding Boxes (AABB), and Oriented Bounding Boxes (OBB).

image

During the Space-Parsing, every object is wrapped with a Sphere bounding volume. The physics engine parses the space of every object and creates a Boundary Volume Hierarchy (BVH). The BVH produces a tree-like structure where each node contains objects that are most likely to collide.
The physics engine tests each node and creates a list of collision pairs. The Broad Phase is fast, and it may report false positives collisions. But even so, it removes all non-possible collision pairs.

image

A sphere-sphere collision is faster to detect than an OBB-OBB collisions. However, it does report false positives.

The collision-pair list is then passed down to the Narrow Phase Collision Detection. In this phase, each object is wrapped with a Convex Hull Volume approximating its shape. The collision detection then performs a collision test between these convex hulls using the Gilbert-Johnson-Keerthi (GJK) algorithm. This algorithm is precise but expensive.