Swept AABB

Introduction

Normal AABB Collision detecton has a major problem.

AABB Collison works fine if the box new position collides with the intersecting object and is not further than the center of the wall. But if the destination is further than the center of the wall it will push the object to the wrong side of the wall.

When traveling it high velocities there can be a wall between your position and your destination but AABB will just teleport you trough the wall.

If there is a wall between your position and your destination normal AABB will just ignore the wall and teleport you to your destination.

These problems occur when traveling at high velocities or the program is running at a low frame rate. To prevent this we need to predict where the object has travelled between each frame. We do this using a segment intersection tests.

Segment Collision Tests

You can use Segment Collision (SC) tests for many things. For example line of sight or checking if a bullet hit something. But you can also use it as a way of detcting collision. SC tests find the time of the line’s intersection with the near and far edges of each axis of the AABB. The near edge is the first point of collision. The near and far edges are the entry and exit point of the line’s intersection with the AABB.

My implementation of SC tests returns a Hit object with a time, position and normal properties. To calculate these properties we need a start position, delta (velocity) and padding vector. Instead creating a segment argument I express the segment from A to B with the equation S(t) = A + t * (B - A), for 0 <= t <= 1. In this equation, t is the time along the line, or percentage distance from A to B.

We can calculate the linear time (for both the near and the far point) by substracting the position of the edge from the start position. Than deviding it by the delta. We can use this to calculate the collision time by checking which value is greater than the other as shown in my implementation. Because we calculated the near and far time seperatly we can also use those to determine the normal of the hit.

Swept Volume Tests

Swept volume tell you whetever object A hits object B at any point along a movement path. We do this by inflating the static object by the size of the moving box and test the movement segment against the inflated box. The point of intersection is the tells you where the moving box first collided with the static box.

Implementation

Intersect Segment Test

This first thing this function needs to do is calculating the linear time at the point of collision. This is done as follows: First divide 1 by the velocity (delta) to get the scale. Now we can calculate the near time and the far time. We do this by multiplying the box’s pos minus the signum value by the center point of the box + the padding of the line we are testing. After that we subtract the position of the box. Finally we scale the entire thing by the previously calculated scale variable.

float scaleX = 1.0 / delta.x;
float scaleY = 1.0 / delta.y;
float signX = sgn(scaleX);
float signY = sgn(scaleY);
float nearTimeX = (b1p.x - signX * ((b1s.x / 2) + padding_x) - pos.x) * scaleX;
float nearTimeY = (b1p.y - signY * ((b1s.y / 2) + padding_y) - pos.y) * scaleY;
float farTimeX = (b1p.x + signX * ((b1s.x / 2) + padding_x) - pos.x) * scaleX;
float farTimeY = (b1p.y + signY * ((b1s.y / 2) + padding_y) - pos.y) * scaleY;

We can now use these variables to check if static collision occurred. This function uses the following arguments: box1 and box2. If we are not colliding we return a nullptr (or set a isValid variable to false when not using pointers) and if we are we return a Hit struct with the position, delta, normal and time of the hit. First we check for the near check is more than 1 and the far time is less than 0. If this returns true we can be sure there won’t occur any collision so we return a nullptr. Now we can set the normal of the hit we are going to return. If the nearTimeX is greater than the fire time the nomal would be (reverse of the signum of scaleX, 0) and if the nearTimeX is less than the nearTimeY the normal would be (0, reverse of the signum of scaleY). Now we only have to calculate the delta and the position of the hit. The delta is the time multiplied by the input delta and the position is the position of the box + the hit delta.

if (nearTimeX > farTimeY || nearTimeY > farTimeX)
return nullptr;

float nearTime = (nearTimeX > nearTimeY) ? nearTimeX : nearTimeY;
float farTime = (farTimeX < farTimeY) ? farTimeX : farTimeY;

if (nearTime >= 1 || farTime <= 0)
return nullptr;

hit->time = clamp(nearTime, 0, 1);
hit->time_v.x = clamp(-nearTimeX, 0, 1);
hit->time_v.y = clamp(nearTimeY, 0, 1);
if (nearTimeX > nearTimeY) {
hit->normal.x = -signX;
hit->normal.y = 0;
}
else {
hit->normal.x = 0;
hit->normal.y = -signY;
}
hit->delta = hit->time * delta;
hit->pos = pos + hit->delta;

return hit;

Intersect AAB check

This is very similar to the intersect segment check but we pass the following arguments: box1’s pos, delta, and the padding of the line . We check for overlaps on each axis. For this we calculate 2 variables. A D vector2 and a P vector2. The D vector should be the box1’s pos minus box2’s box and P should be the absolute value of the center of box1 + the center of box2. If px or py is is the same or less then 0 we return a nullptr.

d.x = b2p.x - b1p.x;
p.x = ((b2p.x + (b2s.x / 2)) + (b1p.x + (b1s.x / 2))) - abs(d.x);

if (px <= 0)
return nullptr;

d.y = b2p.y - b1p.y;
p.y = (b2p.y + (b2s.y / 2) + b1p.y + (b1s.y / 2)) - abs(d.y);

if (py <= 0)
return nullptr;

Now we can again check if one value is greater than the other but instead of comparing time we now compare P.y with X.y. If it is true the Hit normal should be the signum of d.x and the x position box1’s x position + the center multiplied by the signum of d.x. The y position is just the bos1’s y position. If the p.x is less than p.y we do the exactly the same but we switch the x variables with y.

if (p.y > p.x) {
float sy = sgn(d.y);
hit->delta.y = py * sy;
hit->normal.y = sy;
hit->pos.x = b2p.x;
hit->pos.y = b1p.y + (b1p.y + (b2s.y / 2) * sy);

}
else {
float sx = sgn(d.x);
hit->delta.x = p.x * sx;
hit->normal.x = sx;
hit->pos.x = b1p.x + (b1p.x + (b1s.x / 2) * sx);
hit->pos.y = b2p.y;

}

Sweep Test

Now we can finally get to the juicy part of this collision method. The sweep test itself. Now we have written those other checks it is actually quite easy to write this. This function has the parameters box1, box2 and delta and is going to return a struct with the position of the sweep, the Hit and the collision time. If the box is not moving we just do a static test using the Intersect AABB Test. If this is the case the sweep pos would be the same as the box1’s pos and the hit -obviously- the hit returned by the AABB check. If this check returns true the sweep time should be the same as the hit time.

if (delta.x == 0 && delta.y == 0) {
sweep.pos.x = b2p.x;
sweep.pos.y = b2p.y;
sweep.hit = IntersectCollider(b1, b2);
if (sweep.hit) {
sweep.time = sweep.hit->time = 0
sweep.time_v = sweep.hit->time_v = glm::vec2(0, 0);;
}
else {
sweep.time = 1;
sweep.time_v = glm::vec2(1, 1);
}
}

If we are moving we need to use the Intersect Segment Test. Again set the sweep’s hit to the returned value of the previously mentioned check. If we do not have a hit we just set the sweep’s position to the box2’s position + the delta. But if we do have collision we need to do the same position calculation but multiply it by the clamped hit’s time - epsilon (between 0 and 1). I am not entirely sure why we have to subtract hit’s time by epsilon. Now we calculate the direction of the delta by normalizing the delta. We use this direction to add to the sweep’s position multiplied by the center of box2. And of course at the end of the function we return the calculated sweep.

else {
sweep.hit = IntersectSegment(b1, b2p, delt, b2s.x / 2, b2s.y / 2);
if (sweep.hit) {
sweep.time = clamp(sweep.hit->time - numeric_limits::epsilon(), 0, 1);

sweep.pos = b2p + delt * sweep.time;
glm::vec2 direction = delt;
direction = glm::normalize(direction);
sweep.hit->pos += direction * (b2s / 2);
}
else {
sweep.pos = b2p + delt;
sweep.time = 1;
sweep.time_v = glm::vec2(1, 1);
}
}

And that is all there is to it! A effective 2D collision test. Not the most optimized but it has consistent results.

In Practice This is how you use the previously explained checks in your program:

Sweep nearest;
nearest.time = 1;
nearest.time_v = glm::vec2(1, 1);
nearest.pos.x = bp + delta;

for (auto i = 0; i < colliders.size(); i++) {
Sweep sweep = SweepAABB(colliders[i], b, delta);

if (sweep.time < nearest.time && sweep.hit) {
nearest = sweep;
}
}

return nearest;

Collision Responses

There is actually more to it when using it in games since you don’t want the player just to stop moving at all when collision occurs. Instead you want to maybe bounce, slide or invert the velocity. Luckily the once I know off are rather easy to implement.

Slide

This is mathematically the hardest in my opinion because it uses the dot product of the vector to calculate the amount of sideways velocity is left over from initial impact.

dotprod = (delta.x * nearest.hit->normal.y + delta.y * nearest.hit->normal.x) * remaining_time;
new_velocity = dotprod * nearest.hit->normal;

You may notice this won’t work with collision on multiple axis because the new velocity will slide you through walls since you have never checked for collision with the newly added velocity. I solved this by running a 2e Sweep Test. This may not be the most effective solution but it was the only one I could think off. (You don’t have to do this for the other responses)

Bounce

This is quite simple. Just reverse the velocity on the axis of impact and subtract a amount of force loss.

new_velocity.x = delta * nearest.hit.normal.x;
Invert

Inverting is the simplest response. Just invert the entire velocity vector and you are done.

new_velocity.x = delta * -1;

There are probably more responses but I think if you know how to use these basic responses you can also implement more advanced behaviour.

Broad-Phase algorithms help reduce the cost of collision tests. It returns a set of colliders which have a likely chance of collision. Two of the most used aproaches are Sweep and Prune and spacial partitioning. I currently have not implemented these techniques due to lack of time.

Sweep and Prune.

Sweep and Prune sorts the colliders based on their lower bound and upper bound. For example when you have a 2D sidescroller and you are P in this example you don’t want to test all the tiles under the ground for collision. Tiles that should be checked are marked with Y and tiles which should not are marked with X

p
yyyyyyyyyy
xxxxxxxxxx

Spacial Partitioning

This devides the scene into two until the requirements are met. Some examples of special partitioning are k-d trees and quadtrees. I do not axactly know how this works yet but I do understand how back face culling uses the painter algorithm. The painter algorithm sorts all polygons based on their depth value and paints them in this order. 