Friday, September 25, 2009

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.

Drawing1

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:

 WithoutAABB WithAABB

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

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.

ContactPoint

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:

Improved overview

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

image

4 comments:

Anonymous said...

Shouldn't narrow phase be a branch of broad phase? i mean broad phase would be performed before any expensive narrow phase yes?

Genbox said...

You are correct that the broad phase is run before the narrow phase. When the object has entered the broad phase and successfully created a pair (geometries are close to each other), the narrow phase is run on the pair. However, they are still separate parts of the engine and you can indeed run the narrow phase on a pair without using the broad phase; depending on the structure of the engine.

Anonymous said...

Great series ! This is really the kind of stuff the Internet needs ! Keep up the good work !

Jack said...

I agree, great job on the articles.

Post a Comment