Collision Detection Tutorial

2014-01-23

This tutorial presents a robust method for collision detection and response. The concepts demonstrated apply equally well to both 2D and 3D simulations, and can be generalized for a wide variety of situations. Examples are in C-like pseudocode; basic familiarity with C language syntax is assumed. A working example application is provided at the end to demonstrate the collision system in action.

Terminology

Penetration

Before we start, a few terms I'll be using:

Penetration: When two solid objects occupy overlapping physical space.
Intersection Test: Determination of whether two solid objects are penetrating each other in their current positions.
Collision Response: Changes to one or more objects' positions, velocities, etc. made to resolve an intersection between them.
Simulation: The virtual world to which collision detection is being applied.
Framestep: A single logic update to the simulation state, advancing the simulation by a small amount of time.
Timeslice: A finite temporal interval of the simulation. For example, a 1-dimensional object starts at position 0 with a velocity of 0.5 units per second. The timeslice [0.5..1.5] (0.5 seconds through 1.5 seconds) expresses the period of time when the object is between positions 0.25 and 0.75.

Implementation

Enough preamble, let's look at some code! The objects we'll be using in this example look like this:

struct movingObject {
	Vector2 lastPosition;
	Vector2 position;
	Vector2 velocity;
	float width;
	float height;
};

struct staticObject {
	Vector2 position;
	float width;
	float height;
};

Our moving objects are rectangular, and store their current position, previous position, and velocity. Static objects only need position and size. Each framestep of the simulation will look something like this (simplified a bit for clarity):

void run() {
	// Update movingObject->velocity as appropriate
	
	movingObject->lastPosition = movingObject->position;
	movingObject->position.x += movingObject->velocity.x;
	movingObject->position.y += movingObject->velocity.y;
	
	resolveCollisions(movingObject, staticObjects, numberOfStaticObjects);
}

When movingObject is updated, its previous position (presumed to be non-penetrating) is saved in lastPosition. Its position is a hypothetical future state; resolveCollisions may interpolate position back toward lastPosition to some extent in order resolve new penetrations. Note that the example in this tutorial assumes a single moving object; multiple moving objects will be covered in part 2.

Now, the resolveCollisions function itself:

struct collision {
	float time; // [0..1]
	float surfaceArea; // [0..n]
	int axis; // X_AXIS or Y_AXIS
};

#define X_AXIS 0
#define Y_AXIS 1

// Arbitrarily small number used to account for floating point rounding error
#define TIMESLICE_EPSILON 0.00001f

// Arbitrarily high number used prevent infinite loops in degenerate cases
#define MAX_TIMESLICE_SUBDIVISIONS 32

void resolveCollisions(struct movingObject * movingObject,
                       struct staticObject * staticObjects,
                       int numberOfStaticObjects) {
	int staticObjectIndex;
	float timesliceRemaining;
	int numberOfTimesSubdivided;
	struct collision collision, bestCollision;
	bool collided;
	
	timesliceRemaining = 1.0f;
	numberOfTimesSubdivided = 0;
	
	while (timesliceRemaining > TIMESLICE_EPSILON) {
		bestCollision.time = 1.0f + TIMESLICE_EPSILON;
		collided = false;
		
		for (staticObjectIndex = 0; staticObjectIndex < numberOfStaticObjects; staticObjectIndex++) {
			if (intersectionTest(movingObject, staticObjects[staticObjectIndex], &collision)) {
				if (collision.time < bestCollision.time ||
				    (collision.time < bestCollision.time + TIMESLICE_EPSILON &&
				     collision.surfaceArea > bestCollision.surfaceArea)) {
					collided = true;
					bestCollision = collision;
				}
			}
		}
		
		if (!collided) {
			break;
		}
		
		resolveCollision(movingObject, bestCollision, timesliceRemaining);
		
		timesliceRemaining = (1.0f - bestCollision.time) * timesliceRemaining;
		numberOfTimesSubdivided++;
		
		if (numberOfTimesSubdivided > MAX_TIMESLICE_SUBDIVISIONS) {
			printf("Warning: Maximum timeslice subdivisons reached; collision resolution may be incomplete\n");
			break;
		}
	}
}

Conceptually, it's fairly simple. It starts with the assumption that the entire framestep is being processed as a single timeslice. An intersection test with the moving object is performed against every* static object, returning a collision struct if penetration has occurred.

*This could be made more efficient with space partitioning, which would allow you to test against only the static objects that are closest to the moving object and may be penetrated by it.

The collision struct contains all of the information necessary to resolve penetration. However, it is not processed until all objects have been intersection tested; if there are multiple collisions, they must be processed in order based on when they occur in the current timeslice. Otherwise, collisions are order-dependent, and the simulation will behave inconsistently. Don't pay attention to the surfaceArea test just yet; we'll come back to it in a moment.

After all objects have been intersection tested, if there were no collisions, we're finished. If there was at least one collision, we've saved the one which occurred earliest within the timeslice in bestCollision. This collision can now be resolved, moving the penetrating object back in time to a point when there's no penetration.

At this point, the timeslice is subdivided. Since we've already tested all of the objects in the simulation and processed the earliest collision, we know that everything up to the time when that collision occurred has been fully resolved. However, if the collision occurred at an earlier time than the very end of the framestep, the moving object may still have some distance to move, and could collide with other objects. Since the simulation has been changed by resolving a collision, we need to start over and test everything again for the remaining timeslice within the framestep.

This continues until either all collisions have been processed, or we hit an arbitrary limit on the number of subdivisions. This limit is imposed so that resolveCollisions cannot get into an infinite loop in a degenerate case where collisions fail to be resolved. The printed warning is so that you'll know you may need to debug your intersection tests or collision response.

Surface Discontinuities

Collision with a seam

There's one bothersome problem with this approach for the sort of rectangular objects we're using in this example. If two static objects are flush against each other forming a solid wall, and the moving object is moving diagonally against that wall, a collision may be detected with the inside edge, causing the moving object to get hung up on the seam where the two static objects meet. This is why the surfaceArea field exists in the collision struct. If two collisions occur at the same time, a secondary check is performed to give the one with greater surface area priority over the other. A collision with the inside edge of a seam will produce a surface area of zero or close to zero, while the collision against the solid edge of the wall will have a much larger surface area, so it will take priority and prevent snags.

Discrete vs. Swept Collisions

Discrete

Swept

I'd like to draw a contrast between two approaches to collision testing: Discrete and Swept. Discrete collision tests involve checking for penetration at a single point in time. While this is simpler to implement, it can allow small and/or fast-moving objects to pass directly through each other without colliding. If your timestep isn't fixed, whether this occurs or not may depend on frame rate. In contrast, a swept collision test considers the entire range of movement at once, allowing detection of collisions that would have been missed by a discrete collision test.

Intersection Test

The above resolveCollisions code calls two functions we haven't defined yet: intersectionTest and resolveCollision. Here's a possible intersectionTest implementation:

// Arbitrarily small number used to account for floating point rounding error
#define COLLISION_EPSILON 0.00001f

#define min(lhs, rhs) ((lhs) < (rhs) ? (lhs) : (rhs))
#define max(lhs, rhs) ((lhs) > (rhs) ? (lhs) : (rhs))

bool intersectionTest(struct movingObject * movingObject,
                      struct staticObject staticObject,
                      struct collision * outCollision) {
	float timeX, timeY;
	bool collisionX = false, collisionY = false;
	float newX, newY;
	float staticLeft, staticRight, staticBottom, staticTop;
	float movingLeft, movingRight, movingBottom, movingTop;
	float lastMovingLeft, lastMovingRight, lastMovingBottom, lastMovingTop;
	
	staticLeft = staticObject.position.x;
	staticRight = staticLeft + staticObject.width;
	staticBottom = staticObject.position.y;
	staticTop = staticBottom + staticObject.height;
	movingLeft = movingObject->position.x;
	movingRight = movingLeft + movingObject->width;
	movingBottom = movingObject->position.y;
	movingTop = movingBottom + movingObject->height;
	lastMovingLeft = movingObject->lastPosition.x;
	lastMovingRight = lastMovingLeft + movingObject->width;
	lastMovingBottom = movingObject->lastPosition.y;
	lastMovingTop = lastMovingBottom + movingObject->height;
	
	// Incorrect sweeping, but better than nothing
	if (min(movingBottom, lastMovingBottom) < staticTop    - COLLISION_EPSILON &&
	    max(movingTop,    lastMovingTop)    > staticBottom + COLLISION_EPSILON) {
		if (lastMovingRight <= staticLeft + COLLISION_EPSILON &&
		    movingRight     >  staticLeft + COLLISION_EPSILON) {
			collisionX = true;
			timeX = (staticLeft - lastMovingRight) / (movingLeft - lastMovingLeft);
			
		} else if (lastMovingLeft >= staticRight - COLLISION_EPSILON &&
		           movingLeft     <  staticRight - COLLISION_EPSILON) {
			collisionX = true;
			timeX = (staticRight - lastMovingLeft) / (movingLeft - lastMovingLeft);
		}
		
		/* Compensate somewhat for incorrect sweeping by discarding collisions that
		   don't intersect at collision time. Without this, collisions with seams
		   where you're moving perpendicular to the wall faster than parallel to it
		   will be registered. */
		if (collisionX) {
			newY = lastMovingBottom + (movingBottom - lastMovingBottom) * timeX;
			if (newY                       >= staticTop    - COLLISION_EPSILON ||
			    newY + staticObject.height <= staticBottom + COLLISION_EPSILON) {
				collisionX = false;
			}
		}
	}
	
	if (min(movingLeft,  lastMovingLeft)  < staticRight - COLLISION_EPSILON &&
	    max(movingRight, lastMovingRight) > staticLeft  + COLLISION_EPSILON) {
		if (lastMovingTop <= staticBottom + COLLISION_EPSILON &&
		    movingTop     >  staticBottom + COLLISION_EPSILON) {
			collisionY = true;
			timeY = (staticBottom - lastMovingTop) / (movingBottom - lastMovingBottom);
			
		} else if (lastMovingBottom >= staticTop - COLLISION_EPSILON &&
		           movingBottom     <  staticTop - COLLISION_EPSILON) {
			collisionY = true;
			timeY = (staticTop - lastMovingBottom) / (movingBottom - lastMovingBottom);
		}
		
		if (collisionX) {
			newX = lastMovingLeft + (movingLeft - lastMovingLeft) * timeY;
			if (newX                      >= staticRight - COLLISION_EPSILON ||
			    newY + staticObject.width <= staticLeft  + COLLISION_EPSILON) {
				collisionY = false;
			}
		}
	}
	
	if (collisionX || collisionY) {
		if (!collisionX || (collisionY && timeY < timeX)) {
			outCollision->time = timeY;
			outCollision->axis = Y_AXIS;
			outCollision->surfaceArea = min(staticRight, newX + movingObject->width) - max(staticLeft, newX);
			return true;
		}
		
		outCollision->time = timeX;
		outCollision->axis = X_AXIS;
		outCollision->surfaceArea = min(staticTop, newY + movingObject->height) - max(staticBottom, newY);
		return true;
	}
	
	return false;
}

This may look complex, but it's mostly just tedious. The rectangular bounds of the static object and the moving object in its previous and current positions are saved to temporary variables to help readability. Intersections are tested first on the X axis, then on the Y axis. At the end, whichever axis had the earlier collision (if any) writes the necessary information to outCollision.

1D Span Test
(X axis)

For each axis, intersectionTest first checks one-dimensionally to see if the moving object is within the span of the static object on the opposite axis as the one being tested. It then checks one-dimensionlly on the other axis to see if either side of the moving object will penetrate the boundary of the static object. If so, a collision has been detected, and the time at which it occurs within the timeslice is calculated. If objects are already penetrating or moving away from each other, no collision will be registered.

Overlapping union rects,
but no collision

The test that follows may seem a bit strange, but it's necessary to compensate for the fact that this implementation of intersectionTest doesn't truly implement swept collision detection; it simply uses the union rect of the moving object's last and current positions in a discrete test against the static object. If an object is moving diagonally, it's possible to get a false positive if a corner of the union rect passes through a static object, but the actual path of the object does not. By rechecking to make sure the moving object is within range of the static object at the computed collision time, this problem is averted.

Collision Response

The last step in the process is to resolve collisions once the best one has been found. A resolveCollisions implementation might look like this:

void resolveCollision(struct movingObject * object, struct collision collision, float timesliceRemaining) {
	object->position.x = object->lastPosition.x + (object->position.x - object->lastPosition.x) * collision.time;
	object->position.y = object->lastPosition.y + (object->position.y - object->lastPosition.y) * collision.time;
	
	if (collision.axis == X_AXIS) {
		object->velocity.x = 0.0f;
	} else {
		object->velocity.y = 0.0f;
	}
	
	object->lastPosition = object->position;
	object->position.x += object->velocity.x * (1.0f - collision.time) * timesliceRemaining;
	object->position.y += object->velocity.y * (1.0f - collision.time) * timesliceRemaining;
}

The moving object's position is interpolated back toward its lastPosition. In essence, it travels back in time to the latest non-penetrating moment. Velocity is set to zero on the collision axis. (For elastic collisions, you could also negate and dampen velocity on that axis.) Finally, a new lastPosition is saved, and position is updated based on the new velocity for the remaining timeslice. When the next iteration of collision detection is run, the updated velocity ensures that the moving object will not subsequently penetrate the static object that caused this collision again, and the updated lastPosition and position allow it to collide with objects in its newly-altered path of travel.

Conclusion

This technique is not limited to rigid 2D collisions with axis aligned rectangular objects. The intersection test and collision response presented here are only examples. You can replace them with something that detects differently shaped objects, or responds to collisions with different dynamics, or works with a third dimension, and resolveCollisions is still just as applicable. The timeslice subdivision and in-order collision processing is a skeleton on top of which you can implement a wide variety of collision detection behaviors.

Companion Application

Source
Mac OS X binary
Windows binary
Linux binary