Game Programming

Swept AABB Collision Detection Illuminated

by Cory on September 15, 2018 11:57 PM

I think I finally fucking figured it out. I've been using these two website guides for the "swept AABB" collision detection algorithm and I couldn't figure out why it wasn't completely right.

1. Swept AABB Collision Detection and Response

2. Intersection Tests in 2D

The two guides use slightly different variables. The second one assumes you have axis aligned bounding boxes that originate from the center. So when it says "this.pos.x" or some shit, it means the center of the box. The first one is actually assuming an origin of the top left corner. So the "this.pos.x" equivelant actually points to the leftmost point of the box.

Anyway, as you can see in the previous post, copying this algorithm verbatim still lead to what I saw were some "false positives" in the collision detection. I finally found another set of articles asking about "ghost collisions" after implementing swept AABB and I got to this article. That's a useful term to know. I wasn't able to find much online until I stumbled across that term. Anyway, this person also observes what I did, in that if your velocity is travelling along a single axis, a collision would be falsely detected by the algorithms above.

This write up helped me add two more additional conditions in the collision detection statement:

|| (this->near_time_x == -std::numeric_limits<float>::infinity() && this->overlap_x <= 0.f)
|| (this->near_time_y == -std::numeric_limits<float>::infinity() && this->overlap_y <= 0.f)

Basically I just check if we are not moving in one axis and if that's the case, do an overlap check. If the two boxes aren't overlapping, there is no collision. Here it is in context, in case you're trying to make sense of it:

if (((this->near_time_x > this->far_time_y || this->near_time_y > this->far_time_x)
|| near_time >= 1
|| far_time <= 0.f)
|| (this->near_time_x == -std::numeric_limits<float>::infinity() && this->overlap_x <= 0.f)
|| (this->near_time_y == -std::numeric_limits<float>::infinity() &this->overlap_y <= 0.f)
) {
// collision has not happened
} else {
// collision has happened

This if statement uses the measurement vectors and tests all the conditions to see if we have a collision or not. The two statements I add seem to resolve the ghost collisions.

From that stack overflow page it looks like the websites' algorithm are assuming you are using some sort of "broad phase" culling to avoid this ghost collision issue. Basically, the "broad phase" is when you do really rough, quick calculations and determine which objects don't even come into the vicinity of other objects. Usually this is done with spatial partitioning or some sort of sorted tree. You can get rid of a whole bunch of calculations by doing this.

This Thought is part of Game Programming

Game programming general topic. I eventually hope to split this into separate ideas exclusively about specific games that I make.

back to the