Blog

Written by:
Thursday, October 07, 2010 

Collision detection in 3d games detects whether objects are intersecting. The normal discrete collision detection does so by checking the objects at their current position. Then the game moves the objects and the collision detection checks the objects at their new positions.

This method works for slow moving objects, but for fast moving objects critical collisions can be missed. To detect all collisions we need “Continuous Collision Detection” (CCD), which we will discuss in this and the next blog posts.

Why do we need CCD?

A normal game computes 30 or 60 frames per second. In each frame objects are positioned, collisions are detected and the objects are displayed on the screen. Object movement is not really continuous – instead each simulated objects makes 30 or 60 hops per second. In other words: the movement of the objects is sampled with 30 or 60 Hz.

Two unwanted situations can occur:

1. Two objects are separated in one frame and they are penetrating each other in the next frame. Most game objects are solid objects that should not overlap.
2. A bullet is shot at a thin wall. In one frame the bullet is in front of the wall. In the next frame the bullet is behind the wall. No collision is detected because the collision happened between two frames. This problem is also known as “tunneling”.

The following video shows the second problem. Two spheres move towards the wall. The sphere in the front uses discrete collision detection. The collision with the wall is missed because it happens between two frames. The sphere in the back uses Continuous Collision Detection and the collision is detected.

CCD is more difficult than discrete collision detection, but it does two important things:

1. Compute the time of impact.
   The time of impact is the time when the objects start to touch. The result of a time of impact query is often a value between 0 and 1. 0 means that the objects are touching in the current frame. 1 means that the objects do not start to touch before the next frame. 0.5 means that the time of impact is halfway between the current and the next frame, etc.
2. Avoid tunneling.

In the next blog post, we will discuss ways to implement CCD and how we have implemented CCD in the upcoming version of DigitalRune Geometry.

Trackback Print

Tags: Collision Detection , Continuous Collision Detection

Categories: Game Programming, Collision Detection

Location: Blogs DigitalRune Blog

Your name:
Your email:
	(Optional) Email used only to show Gravatar.
Your website:
Title:
Comment:
Security Code Enter the code shown above in the box below
Add Comment   Cancel