2D Physics Engine Tutorial – Part 2

In part 1 I explained what a physics engine does and what kind of physics engines there exists. This post will focus on the collision detection internals of physics engines.

Overview

A physics engine does two things: Collision detection and physics reaction. They work seamless together to create the illusion of things colliding and bouncing back.

Collision Detection

The collision detection part of the engine is responsible for detecting when things overlap and by how much they overlap. Most physics engines have developed a two-tier architecture where you first detect if objects are near each other using a crude representation of the object. Then it performs the collision detection on the objects itself using its real representation. It basically is setup like this:

Broad phase

The broad phase is the one responsible for detecting objects near each other. It was developed to speed up the collision detection phase by reducing the amount of collision checks needed. Imagine a simulation containing 11 balls; the engine would need to do 121 (11^2) expensive (real shape) collision checks. If a broad phase is introduced, this number of checks can be reduced to a smaller amount. Broad phase algorithms usually use AABBs to represent a crude shape of the object. It is a lot cheaper to test AABB vs. AABB than a polygon vs. polygon.

The example from before with 11 balls would in the following images only have to do 121 cheap tests and 25 (5^2) expensive checks.

With and without AABBs:

 

There exists a lot of algorithms to do broad phase tests:

• Brute force
• Sweep and prune
• Dynamic tree
• Spatial hash
• BSP tree
• QuadTree

All of them have in common that they divide the screen up into smaller parts using trees (flat or hierarchical), grid or axis-division. Have in mind that no broad phase algorithm is the “best” – it depends on the situation in which they are used.

Narrow phase

When the broad phase has detected that two objects are near each other (their crude representations intersect) the engine should create a pair (sometimes called an arbiter) that contains the two objects. The objects are then tested using the narrow phase algorithm. Unlike the broad phase, the narrow phase tests the real shapes (polygons) against each other. This is an expensive test in most cases since a polygon can be anything from 3 to n points. The narrow phase algorithm needs to find the following information:

• Does a collision exist
• Position
• Normal
• Distance

The last 3 items are vital for the collision response phase. The information is used to generate a contact; it contains the previous gathered information and can be persisted over several time steps.

Green: Normal of contact point
Red: Centroid
Black: Shortest distance to collision point

Just like the broad phase collision detection system, there are a lot of narrow phase algorithms:

• GJK
• Signed Distance Field
• VClip
• SAT
• Raycasting

Improved overview

Now that the collision detection system has been identified, the new overview looks like this: