Reading

This article covers some techniques of physics used in games; however, collision detection, rigid-body dynamics, ragdoll physics, soft-body dynamics, etc are already well implemented by major game engines such as Godot, Unity, Unreal and so on.

Collision Detection Overview

This section provides basic bounding-volume based collision detection techniques that should be a good start.

2D Bounding-box Collision

To simplify the collision, we assume our game object to be bounded by a rectangle. We then check if it intersects with other rectangles. Pseudocode in C-like syntax clarify it:

class BoundingBox2D:
    def __init__(self, x, y, width, height):
        self.x = x
        self.y = y
        self.width = width
        self.height = height

    def is_colliding(self, other_box):
        # Check for non-overlapping conditions
        if (self.x + self.width) < other_box.x or self.x > (other_box.x + other_box.width):
            return False

        if (self.y + self.height) < other_box.y or self.y > (other_box.y + other_box.height):
            return False
        
        return True

The above code defines a bounding box (a rectangle in simple) & is_colliding() checks if it is colliding/intersecting with some other box.

3D Axis-aligned Bounding-box Collision

3D bounding box is like a cube. Axis aligned means that if the object is rotated, the bounding box will not rotate but instead, change its dimensions to accommodate the change. It is one of the cheapest algorithms to check collision. The reason why we prevent rotation is because it makes the computation of collision complex & thus slow.
Check if a vector3 point is inside AABB:

    def is_point_inside_aabb(self, point):
        return (
            self.x <= point.x <= self.x + self.width and
            self.y <= point.y <= self.y + self.height and
            self.z <= point.z <= self.z + self.depth
        )

Check if two AABBs are colliding:

    def is_colliding(self, other_box):
        # Check for non-overlapping conditions along each axis
        if (
            (self.x + self.width) < other_box.x or self.x > (other_box.x + other_box.width) or
            (self.y + self.height) < other_box.y or self.y > (other_box.y + other_box.height) or
            (self.z + self.depth) < other_box.z or self.z > (other_box.z + other_box.depth)
        ):
            return False

        # If none of the non-overlapping conditions are met, boxes are colliding
        return True

3D Bounding-sphere Collision

We can also assume our objects to be spherical in thus check for spherical collisions. The approximation of objects such as a penguin as a sphere is a good idea, but for objects such as human, bounding-box approximation is more accurate (as sphere will cause a lot of false-positives).
The advantage of bounding-sphere is that; it doesn’t need to re-computed if object rotates; disadvantage is that for object such as a rod, it will be extremely inaccurate.
Checking if vector3 point is inside sphere:

    def is_point_inside_sphere(sphere, point):
        distance_squared = (point.x - sphere.center.x)**2 + (point.y - sphere.center.y)**2 + (point.z - sphere.center.z)**2
        return distance_squared <= self.radius**2

Checking if two spheres intersect:

    def is_colliding(sphere, other_sphere):
        distance_between_centers = math.sqrt(
            (sphere.center.x - other_sphere.center.x)**2 +
            (sphere.center.y - other_sphere.center.y)**2 +
            (sphere.center.z - other_sphere.center.z)**2
        )

        combined_radii = self.radius + other_sphere.radius

        return distance_between_centers <= combined_radii

Check collision between AABB & Sphere

def intersect(sphere, box):
    # Get box closest point to sphere center by clamping
    x = max(box.x, min(sphere.x, box.x + box.width))
    y = max(box.y, min(sphere.y, box.y + box.height))
    z = max(box.z, min(sphere.z, box.z + box.depth))

    # This is the same as is_point_inside_sphere
    distance = ((x - sphere.x) ** 2 + (y - sphere.y) ** 2 + (z - sphere.z) ** 2) ** 0.5

    return distance < sphere.radius

(x, y, z) is the point of collision/contact if condition (distance < sphere.radius) is true. A very useful value to later apply forces on.

Rigid-body Dynamics

In rigid body simulations, if we have n objects, the collision detection between all possible combinations of objects is n^2; thus complexity O(n^2). This makes collision detection  expensive for a simulation. Also, collision check for each pair of objects is itself an expensive compute.
To optimize the simulation, we divide the process into 2 phases:

1. Broad Phase: Computation to find what objects could be colliding. So their collision will later be checked in more detail in narrow phase. We use space partitioning & bounding volume-based basic collision detection (discussed above) to figure this out.
2. Narrow Phase: Precise collision detection computation between those pair of objects which are probably colliding. This keeps the no. of objects being checked to lower; thus making the process faster.

Broad Phase

To check & filter out those pair of objects which could be colliding, we use space partitioning and simpler collision algorithms such as above discussed bounding-volumes.

Space partitioning

There are variety of algorithms used: Binary Space Partitioning (BSP), Quadtree (in 2D), Octree (in 3D), Bounding Volume Hierarchy (BVH), Uniform Grid and so on.

Sweep & Prune Algorithm

This spatial partitioning algorithm sorts the starts (lower bound) and ends (upper bound) of the bounding volume of each solid along a number of arbitrary axes. As the solids move, their starts and ends may overlap. When the bounding volumes of a pair of solids overlap in all axes they are marked to be probably colliding (and thus require better check in narrow phase).

Bounding Volume Hierarchy (BVH)

It is the hierarchy/tree structure of bounding volumes, in which the bounding volumes of nearby solids are wrapped in bigger bounding volumes of which nearby ones are wrapped in more bigger bounding volumes until the biggest bounding volume covering the entire simulation is reached.

This makes sure that children of separate branches in the tree are never intersecting, so we skip their computation & end up achieving better performance.

Narrow Phase

In broad phase, we determined what pair of objects are possibly colliding. In narrow phase, we check if pairs of objects are actually colliding, their point of contact, and intersections between them.

Concept of Convex & Concave Shapes

Since we are now working with actual shapes of physics bodies (rather than their bounding volumes), we need to know what kind of shape they have. There are 2 possible kinds:

1. Convex Polygon: Shape that does not have cavity. In math language, any line must not intersect the boundary more than 2 times 9once when entering, once when leaving).
2. Concave Polygon: Shape with a cavity. A line can intersect it more than twice.

Concave polygons are expensive to check for collisions so we convexify them using some techniques:

1. Convex Hull: A single convex polygon covering the entire concave object; the convex approximation of a concave polygon. For this, we often use algorithms such as quickhull to create this convex hull approximation from a concave shape. If we still want object to behave in a concave style, we can decompose a concave object into set of shapes such that each individual shape is convex, but they are jointly approximating a concave shape (see v-hacd repo here that does this).

Checking for Collisions

For simple pair of shapes, such as spheres, boxes & some other primitive shapes; the collision detection computation is cheaper. In case of spheres & boxes, it is same as in bounding-volume based collisions discussed above. But when it comes to polygons, we have to go through more detail.

Separating Axis Theorem

This theorem can be used for fast collision detection between pair of convex polygons. This theorem says: “Two solid shapes don’t touch each other if we can find a line where their flat views (projections) don’t overlap”.

Object faces’ normal direction can be used as possible separating axes. To test for collision, we need to check; for each edge of a polygon, are the vertices of other polygons in front of it. If a vertex is behind the edge of the 1st polygon, it is indeed penetrating the surface and thus the dot product between the separating axis (which is the normal vector of a face or an edge) and the vector pointing from a vertex of one shape to a vertex of the other shape returned value > 0.

If the dot product is greater than 0 for all combinations of vertices and separating axes, it means that all the vertices are on the same side of the separating axis, and the shapes are not intersecting. If, for any combination, the dot product is less than or equal to 0, it suggests that at least one vertex is on the opposite side of the separating axis, indicating a potential collision.

For more depth, see computing distance between polygons, the depth of penetration & the continuous collision detection on internet.

What after detecting collisions?

We need to change the motion of bodies detected to be colliding, by using different collision information (such as point of contact). Applying classical mechanics can result in Newtonian physics simulation.

Soft-body Dynamics

It is the simulation of deformable objects such as cloth. To start, think of 2 objects joined by a spring. Rigid-body physics applies separately on both objects, but they influence one other through the spring using Hooke’s law. This creates interaction between them. If we have a whole mesh of connected spring mass systems like this, it can result in a simple soft body.
For some inspiration look at:

1. https://github.com/mikemarek/soft-body-physics?tab=readme-ov-file
2. https://lisyarus.github.io/blog/physics/2023/05/10/soft-body-physics.html

This section is still incomplete.