Jump to content

  • Log In with Google      Sign In   
  • Create Account

Like
31Likes
Dislike

Swept AABB Collision Detection and Response

By BrendanL.K | Published Apr 30 2013 12:51 PM in Game Programming
Peer Reviewed by (Josh Vega, Michael Tanczos, AllEightUp)


Collision detection is an area of game development that scares most into using third party physics APIs due to its seemingly vertically-steep learning curve. Most programmers understand the axis-aligned bounding box (AABB) algorithm but have trouble transitioning to the more difficult algorithms such as SAT and GJK. Swept AABB is the middle player that will show a lot of the problems that can occur with normal AABB and help understand core concepts used in more advanced collision techniques.

Note:  This article assumes you understand the AABB algorithm. There is also a bit of vector math, but it won’t get overly complicated. Examples are done in C/C++ but can be easily converted to other languages. At the end, I have given source files for C/C++ and C#.


What is Swept?


AABB has a major fundamental problem that may not be visible at first. Take these 3 examples:


Attached Image: 01.png

Example 1: A normal AABB collision. The blue box is where the box is at the beginning of the frame. The green box is where the box is expected to be by the end of the frame. The aqua box shows where AABB will place the box after collision. The gray box is a static (unmovable) block that is tested for collision. This shows a normal collision. The box is moved to the nearest point that is not a collision. This is fine and is the expected result of AABB.


Attached Image: 02.png

Example 2 shows a similar collision where the destination is further on the opposite side. As you can see, AABB has placed the response box on the opposite side of the block. Logically, this makes no sense as it has magically passed through the object.


Attached Image: 03.png

Example 3 shows a destination that doesn’t collide with the object. AABB will assume that there was no collision and the moving box will move through it like there was no collision at all.

So when do these problems occur?

These problems usually appear when objects are moving fast and/or the program is running at a low frame rate. To avoid this, we need to somehow predict where the box travelled between each frame. This concept is called swept.

Implementing Swept AABB


In this implementation, we will assume that a box is defined by a position at the top-left corner of the box and a width and height. Now that we are taking swept into consideration, we also need to remember the velocity.

Note:  The velocity of an object is how far the object will move per second. If we multiply the velocity by the delta time, you will have the displacement that the object must move in this frame.


So we will define our box like so:

// describes an axis-aligned rectangle with a velocity
struct Box
{
	// position of top-left corner
	float x, y;

	// dimensions
	float w, h;

	// velocity
	float vx, vy;
};

vx and vy refer to the velocities, w and h are the box dimensions.

The function that will perform the test will look like this:

float SweptAABB(Box b1, Box b2, float& normalx, float& normaly)

The first parameter is the box that is moving. The second is the static box that will be tested against. The last two parameters make up the normal of the collided surface. This will be used later on when we want to respond to the collision.

Note:  A normal is the direction that an edge of an object is facing. Think of a perpendicular arrow pointing away from face at 90 degrees.


The return value is a number between 0 and 1 that indicates when the collision occurred. A value of 0 indicates the start of the movement and 1 indicates the end. If we get a value of 1, we can assume that there was no collision. A value of 0.5 means that the collision occurred halfway through the frame. This will also be used later to respond to the collision.


Attached Image: 04.png

Now, to first start the algorithm, we need to find the distance and time that it takes to reach a collision on each axis.

    float xInvEntry, yInvEntry;
    float xInvExit, yInvExit;

    // find the distance between the objects on the near and far sides for both x and y
    if (b1.vx > 0.0f)
    {
        xInvEntry = b2.x - (b1.x + b1.w);
        xInvExit = (b2.x + b2.w) - b1.x;
    }
    else 
    {
        xInvEntry = (b2.x + b2.w) - b1.x;
        xInvExit = b2.x - (b1.x + b1.w);
    }

    if (b1.vy > 0.0f)
    {
        yInvEntry = b2.y - (b1.y + b1.h);
        yInvExit = (b2.y + b2.h) - b1.y;
    }
    else
    {
        yInvEntry = (b2.y + b2.h) - b1.y;
        yInvExit = b2.y - (b1.y + b1.h);
    }

xInvEntry and yInvEntry both specify how far away the closest edges of the objects are from each other. xInvExit and yInvExit is the distance to the far side of the object. You can think of this is a being like shooting through an object; the entry point is where the bullet goes through, and the exit point is where it exits from the other side. These values are the inverse time until it hits the other object on the axis. We will now use these values to take the velocity into account.

    // find time of collision and time of leaving for each axis (if statement is to prevent divide by zero)
    float xEntry, yEntry;
    float xExit, yExit;

    if (b1.vx == 0.0f)
    {
        xEntry = -std::numeric_limits<float>::infinity();
        xExit = std::numeric_limits<float>::infinity();
    }
    else
    {
        xEntry = xInvEntry / b1.vx;
        xExit = xInvExit / b1.vx;
    }

    if (b1.vy == 0.0f)
    {
        yEntry = -std::numeric_limits<float>::infinity();
        yExit = std::numeric_limits<float>::infinity();
    }
    else
    {
        yEntry = yInvEntry / b1.vy;
        yExit = yInvExit / b1.vy;
    }

What we are doing here is dividing the xEntry, yEntry, xExit and yExit by the object’s velocity. Of course, if the velocity is zero on any axis, it will cause a divide-by-zero error. These new variables will give us our value between 0 and 1 of when each collision occurred on each axis. The next step is to find which axis collided first.

    // find the earliest/latest times of collision
    float entryTime = std::max(xEntry, yEntry);
    float exitTime = std::min(xExit, yExit);

entryTime will tell use when the collision first occurred and exitTime will tell us when it exited the object from the other side. This can be useful for certain effects, but at the moment, we just need it to calculate if a collision occurred at all.

    // if there was no collision
    if (entryTime > exitTime || xEntry < 0.0f && yEntry < 0.0f || xEntry > 1.0f || yEntry > 1.0f)
    {
        normalx = 0.0f;
        normaly = 0.0f;
        return 1.0f;
    }

The if statement checks to see if there was a collision or not. If the collision time was not within 0 and 1, then obviously there was no collision during this frame. Also, the time when the collision first entered should never be after when it exited out the other side. This is checked, and if it failed, then we assume that there was no collision. We specify 1 to indicate that there was no collision.

If there was a collision, our last step is to calculate the normal of the edge that was collided with.

    else // if there was a collision
    {        		
        // calculate normal of collided surface
        if (xEntry > yEntry)
        {
            if (xInvEntry < 0.0f)
            {
                normalx = 1.0f;
                normaly = 0.0f;
            }
	        else
            {
                normalx = -1.0f;
                normaly = 0.0f;
            }
        }
        else
        {
            if (yInvEntry < 0.0f)
            {
                normalx = 0.0f;
                normaly = 1.0f;
            }
	        else
            {
                normalx = 0.0f;
		        normaly = -1.0f;
            }
        }

        // return the time of collision
        return entryTime;
    }

Since all of our boxes are axis-aligned, we can assume that there are only 4 possible normals (one for each edge of the box). This simple test will figure that out and then return the collision entry time.

This is all of the code we will use for swept AABB but it won't work correctly in certain cases! That is because we need to implement broadphase (we will cover this soon). But, for now, there is a whole other step in a collision, and that is the response.

Responses


A collision response is how we want the object to behave after a collision. Before going into some of the different types of responses, we need to figure out the new point where the collision occurred. This should be easy now that we have our swept AABB function.

    float normalx, normaly;
    float collisiontime = SweptAABB(box, block, out normalx, out normaly);
	box.x += box.vx * collisiontime;
	box.y += box.vy * collisiontime;
	
	float remainingtime = 1.0f - collisiontime;


Attached Image: 05.png

Doing 1.0f – collisiontime will give us the remaining time left in this frame (0 to 1 value again). This will perform the collision correctly and might be enough for some uses. But if you try to move the box diagonally into the object (“hugging the wall”) then you’ll find that you can’t move. The moving box will not move at all. This is where the different responses can help.

Deflecting


This is most common in games like pong where there is a ball that bounces off objects.


Attached Image: 06.png

You will notice that when the objects collide, the moving object still has some velocity left in it. What will happen is that the remaining velocity will be reused to move it in the opposite direction, creating a bounce-like effect.

    // deflect
    box.vx *= remainingtime;
    box.vy *= remainingtime;
    if (abs(normalx) > 0.0001f)
        box.vx = -box.vx;
    if (abs(normaly) > 0.0001f)
        box.vy = -box.vy;

First we are reducing the velocity by our remaining time. Then we negate the velocity on whichever axis there was a collision. Pretty simple.

Push


Pushing is more of the traditional “wall hugging” concept where if you run towards a wall on an angle, you will slide along the wall.

Attached Image: 07.png

    // push
    float magnitude = sqrt((box.vx * box.vx + box.vy * box.vy)) * remainingtime;
    float dotprod = box.vx * normaly + box.vy * normalx;
    if (dotprod > 0.0f)
        dotprod = 1.0f;
    else if (dotprod < 0.0f)
        dotprod = -1.0f;
    NewBox.vx = dotprod * normaly * magnitude;
    NewBox.vy = dotprod * normalx * magnitude;

It reuses the remaining velocity and pushes it in the direction that is parallel to the collided edge. The first step is to calculate the magnitude of the velocity (this is a programmer version of the Pythagorean Theorem). The next step is performing the dot product with the velocity and the normal of the collided face. We must then normalize this scalar (because we are going to set our own distance). The final step is to multiply the normalized dot product, the switched normal and the magnitude.

Alternatively, you could normalize the velocity after calculating the magnitude, so then you don’t have to normalize dotprod.

Slide


The problem with the push technique is that it may push the object along faster than expected. A more realistic approach is to do sliding.


Attached Image: 08.png

This uses vector projection to find the equivalent position on the edge. This is a simpler approach than the push method.

    // slide
    float dotprod = (box.vx * normaly + box.vy * normalx) * remainingtime;
    NewBox.vx = dotprod * normaly;
    NewBox.vy = dotprod * normalx;

The first thing to remember is that we are swapping the normals around (swap x value with y value). We calculate the dot product, multiply it by the magnitude, and finally multiply it by the swapped normal value. And now we should have our projected velocity.

Broad-Phasing


The swept AABB algorithm runs pretty fast, but as more objects come into play, the performance will drop rapidly. A way to combat this is called broad-phasing. This is where you can do a faster, less accurate test to quickly determine if there isn’t a collision. There are a few techniques to do this (such as circular distance) but, because our objects are all axis-aligned boxes, it makes sense to use a box again.


Attached Image: 09.png

The black box around the outside shows us the broad-phase area. This is a box that we can perform a simple AABB test to check if there is a collision or not. Looking at the image, it is safe to say that if an object is not in this broad-phase area, it will not collide with the object. But just because it is within the broad-phase area, does not indicate that there is a collision. If there is a collision with the broad-phase area, we know that we should perform the swept AABB check to get a more precise answer.

Box GetSweptBroadphaseBox(Box b)
{
    Box broadphasebox;
    broadphasebox.x = b.vx > 0 ? b.x : b.x + b.vx;
    broadphasebox.y = b.vy > 0 ? b.y : b.y + b.vy;
    broadphasebox.w = b.vx > 0 ? b.vx + b.w : b.w - b.vx;
    broadphasebox.h = b.vy > 0 ? b.vy + b.h : b.h - b.vy;

    return broadphasebox;
}

This first step is to calculate the broad-phase area. As bad as this looks, all it is doing is adding the velocity to the edge (depending on the direction of the velocity). Now all we have to do is a generic AABB test.

bool AABBCheck(Box b1, Box b2)
{
    return !(b1.x + b1.w < b2.x || b1.x > b2.x + b2.w || b1.y + b1.h < b2.y || b1.y > b2.y + b2.h);
}

This is a rather simplified function that returns true if a collision occurred.

Now we should be able to put all of the pieces together like this:

	// box is the moving box
	// block is the static box

	Box broadphasebox = GetSweptBroadphaseBox(box);
	if (AABBCheck(broadphasebox, block))
	{
		float normalx, normaly;
		float collisiontime = SweptAABB(box, block, out normalx, out normaly);
		box.x += box.vx * collisiontime;
		box.y += box.vy * collisiontime;

		if (collisiontime < 1.0f)
		{
			// perform response here
		}
	}

Limitations


The implementation described here has some limitations that you may have figured out already. These include:
  • Doesn’t take resizing into consideration (i.e. if a box resizes throughout the frame).
  • Only allows linear movement. If your moving box is moving in a circular fashion, it will not check where it was extended out on the curve.
  • Only allows one box to be moving (i.e. if two boxes move towards each other and collide). This is something I intentionally left out as it starts to involve many of the physics concepts like mass and force.
  • It is still only square shapes! You can’t even rotate them! This is obvious because the name of the algorithm sort of says that already. But if you have conquered swept AABB, then you might be ready to move onto the next level (like SAT or GJK).
  • It is made for 2D only. Luckily, it is quite easy to convert this code to 3D. So long as you understand the concept well, you shouldn’t have much trouble with it. I kept it as 2D to keep things as simple as possible.

Code


All of the C/C++ code specified in this article is available for download here. I have also implemented it in C#. This example code will not run a demonstration; it shows only the functions involved.

And, just for the hell of it, here’s a picture of everything in action:


Attached Image: 10.png






License


GDOL (Gamedev.net Open License)




Comments

Excellent tutorial!
Thank you for this contribution,

can't wait to implement this in my own project! 

Thank you! It confused me for a long time.

An excellent tutorial, you run through it very well. It's not something I'm particularly familiar with, but I had a couple of queries just based on running through the article and the C# code.

 

float entryTime = std::max(xEntry, yEntry);
float exitTime = std::min(xExit, yExit);

 

To me it makes more sense that these would be inverted, finding the minimum entry time and maximum exit time. It's probably I'm missing something, but it's not something I could understand from the article.


Following that section, there's related code that follows the same rule, which suggests to me it's intentional and I'm simply missing something.

 

if (xEntry > yEntry)
{
     if (xInvEntry < 0.0f)
     {
          normalx = 1.0f;
          normaly = 0.0f;
     }
     else
     {
          normalx = -1.0f;
          normaly = 0.0f;
     }
// etc...

 

In this code you check whether the xEntry was greater than the yEntry to determine which surface we're colliding with first. Once again, it makes more sense to me for it to be xEntry < yEntry.

I apologise if I've missed something very obvious, but would you/someone be able to clarify this for me?

My apologies, it seems my mind wasn't switched on. Of course you need the latter as it needs to intersect on both axes. Please forgive my foolishness, if it's any excuse I was up half the night fixing mundane bugs in old code so nothing's really on full power today.

A solid article on a tough bugger of a problem.  Now, gimme one that does this with capsules and I'll be really happy.  :)

Hi there. I have been trying to implement aabb collision detection for a couple days now. This is one of the nicest resources I've found. However, after a lot of testing and re-reading the code, here's something that just isn't making sense for me:
 
The Sweep function returns a collisionTime value between 0 and 1 even when only ONE axis ends up intersecting at any given time. Shouldn't it only return a non-1 value if there is a point when ALL axes intersect?
 
For instance, if I have a character sprite that is travelling sideways (only on the x axis), and there is a single square wall sprite, and my character passes under this wall, then there is only an intersection in the x-axis (since the wall is always above my character in the y-axis) so the two sprites never actually collide. However, this algorithm returns an collisionTime between 0 and 1 because of the x-axis intersection.
 
That means, if I use something like this from your examples:
 

box.x += box.vx * collisiontime;

box.y += box.vy * collisiontime; 

 


 the character's movement is affected by this collision, even though it never actually collided.

 

I think there is some big hole in my understanding. The logic in the Sweep function all seems to make sense to me, but it seems like it returns a valid collisionTime value even when it shouldn't. What am I missing?

 

Thanks for a great article by the way!

If there is no collision, then the collisionTime (return value) should be 1.

if (entryTime > exitTime || xEntry < 0.0f && yEntry < 0.0f || xEntry > 1.0f || yEntry > 1.0f)

 

This line will check that there is a collision on both the x and y axis. A collision on one axis only should not result in a return value less than 1.

 

...not sure if that answered your question.

It seems you understand where I'm coming from, however, when I work out the logic step by step, That conditional statement is not satisfied. So I must be doing something stupid.



So lets say my character is moving left to right, and intersects only the x-axis of the wall. Then:
-----------------[ wall ]---
---[ c ]-->[c_next]-------

xEntry = some positive number between 0 and 1;
yEntry = -INFINITY;
xExit = some bigger positive than xEntry, still between 0 and 1;
yExit = +INFINITY;

entryTime = Max(xEntry, yEntry) = xEntry;
exitTime = Min(xExit, yExit) = xExit;

//This means that, looking at all the conditions, we see that:
entryTime > exitTime;//First condition fails. exitTime >= entryTime
xEntry < 0 && yEntry < 0;//Second condition fails.xEntry >= 0.
xEntry > 1;//Third condition fails. xEntry is a valid positive number between 0 and 1
yEntry > 1;//Fourth condition fails. yEntry is -INF which is less than 1 as well.

All conditions fail, the way I am seeing it, which means it goes to the else statement. What am I getting wrong here?

I have run your test, and it seems you are right. This is a rare case where it is moving perfectly horizontally. But this will never occur if you are doing broad phase (which you should be).

 

I'll try to come up with some code that works a bit better later, but, for now, you should use the broad phase first and that should remove the problem.

Yeah it occurred to me that this only works with some form of initial check for a collision. I was thinking that I wanted to take things piece by piece. Make sure that the sweep worked, and then make everything more efficient with a broad phase check, but in this case I'll have to implement the broad phase first for collisions to work correctly at all.

 

It was just odd because I've seen a few articles on a similar approach to collision detection and response, and they all seem to have the same "flaw", but they never mention that a broad phase is actually required, just that it makes it more efficient. That's why I thought I might just be doing something stupid.

 

Thanks for putting my mind at ease. In my 2d tile based game, perfectly horizontal or vertical movement will be pretty common. I'll try to implement the broad phase in a couple days and see if I get that perfect collision response that I've been working at :P

 

Anyways I appreciate the help, and I would definitely like to see any code you come up with that may work more ideally. Keep me posted with any epiphany :)

The above few comments are right: If you're having troubles with the collision "sticking" on one axis until you go diagonally, you need to do a broad phase check before you do the swept collision check! (Make sure to add in the vector for your broad phase as well)

 

The author should make sure to clarify this!

 

Other than that, the article is excellent, and the method works well!

Thanks for the comments! I've added a little note in there that indicates this.

So now here's a question about responding to collisions with multiple entities (if you aren't sick of me yet). Suppose I have multiple wall tiles lined up vertically, and a character to the left moving diagonally right and up towards the WALL2:

 

..................[WALL1]

..................[WALL2]

....[char]..................

 

I would like to use the slide method, but here are my results:

 

This works on WALL2(the first to collide). I hit it from the left side, the AABBSwept function returns normx = -1, and the dot product causes a slide upwards.

 

However when I get to the level of the bottom of WALL1, there is a collision under WALL1, and to the left of WALL2, at the same time. And, since I am iterating through these walls (in general from top to bottom), WALL1 is processed first.

 

Since we collide with the bottom of WALL1, it returns normy = 1, and causes a slide to the right (as it should if there were no other walls).

 

Then when we process WALL2, we are already inside of it, meaning that we get a negative xEntry and yEntry time in AABBSwept, and therefore it registers no collision, so the character enters WALL2 even though it should collide.

 

I am not sure how to resolve this, but it seems like we need to somehow order the collisions , or accumulate all the changes into an x and y value that changes the character's position after all entities are processed. Would I need to process collisions in order from smallest collisionTime? that's about all I could come up with.

 

By the way, feel free to clear any of my previous posts if my long-winded questions are cluttering the page too much.

 

I appreciate all the help.

@HendrixA4L: Look into "time of impact" ordering. But generally, yes, you order/sort your collisions such that the first collisions get solved/fixed first. This may invalidate/change some of the later collisions (in a larger, more dynamic physics simulation), but that's the gist of it.

If the objects are colliding before the velocity is added (during broad phase), does the swept method not work? If so, what should I do? I'm getting tunnelling ~25% of the time.

 

Specifically, I'm using the swept method with my tile map. Broad phase always detects collisions properly, but swept allows tunnelling through the objects. Here's a screenshot of it functioning (notice the slight overlap of the red bounding box):

FF6zT8a.png

@makuto: Yeah, the algorithm won't work if the moving object starts in a collision at the beginning of the frame. What you can do is add a simple AABB check after the broad phase to check if its colliding. If it is, then push it out with the normal AABB algorithm.

But why are you starting inside another object? You shouldn't be doing this.

To tell you the truth, I have no idea why they end up in the tiles. I'm checking all of the relevant tiles well before they are even close to colliding. Could it be floating point/fast velocity etc.?

Fast velocity shouldn't matter assuming swept was implemented correctly. Floating point inaccuracies all depends on the size of your world. You should test the collision system with a smaller and easier scenario so you can ensure that it is implemented properly.

This works well, the only problem I am having is dealing with multiple collisions on edges. Seems that some extra collision sorting is in order.

 

Would it be the case that you have to create a list of collisions for each step and resolve them in order?

    // if there was no collision
    if (entryTime > exitTime || xEntry < 0.0f && yEntry < 0.0f || xEntry > 1.0f || yEntry > 1.0f)
    {
        normalx = 0.0f;
        normaly = 0.0f;
        return 1.0f;
    }

This works well but i don't understand why you compare "xEntry" and "yEntry" with "1.0f".

Thanks heaps for the tutorial. Unfortunately the given swept AABB code is buggy. Sorry my following code has a slightly different naming scheme from the above (and is also in Java).

Firstly, the code is missing these two lines before finding earliest / latest exit/entry points. This corrects the bug in the tutorial code where an axis non-entry due to overshooting can cover an entry on the other axis.

if (entryY > 1.0f) entryY = -Float.MAX_VALUE;
if (entryX > 1.0f) entryX = -Float.MAX_VALUE;
// Find the earliest/latest times of collision.
float entryTime = Math.max(entryX, entryY);
float exitTime = Math.min(exitX, exitY);

The no-collision check is also incorrect. The check given was:

if (entryTime > exitTime) return 1.0f;
if (entryX < 0.0f && entryY < 0.0f) return 1.0f;
if (entryX > 1.0f || entryY > 1.0f) return 1.0f;

First problem with this check is that it fails to catch the case where one axis overshoots, but the other axis undershoots eg. entryX < 0.0f but entryY > 1.0f. This should be a non-collision, but this code will register that as a collision.

 

Second problem with this check is that it does not correctly handle single-entry collisions at all. Undershooting single-entries collisions are incorrectly ignored, while overshooting single-entries non-collisions are incorrectly collided.

The following image demonstrates a counter-example of two cases which should result in different collision results but are incorrectly treated the same in the tutorial code:
ZtTdjc8.png

The correct set of checks should instead be:

//if (entryY > 1.0f) entryY = -Float.MAX_VALUE; // From previous bug above.
//if (entryX > 1.0f) entryX = -Float.MAX_VALUE; // From previous bug above.
if (entryTime > exitTime) return 1.0f; // This check was correct.
if (entryX < 0.0f && entryY < 0.0f) return 1.0f;
if (entryX < 0.0f) {
    // Check that the bounding box started overlapped or not.
    if (s.max.x < t.min.x || s.min.x > t.max.x) return 1.0f;
}
if (entryY < 0.0f) {
    // Check that the bounding box started overlapped or not.
    if (s.max.y < t.min.y || s.min.y > t.max.y) return 1.0f;
}

After these bugs are corrected, the sweptAABB collision works fine.
Hope this saves someone hours and hours of debugging smile.png
 

This is not working for me not sure where everything went wrong :/ 

// if there was no collision
if (entryTime > exitTime || xEntry < 0.0f && yEntry < 0.0f || xEntry > 1.0f || yEntry > 1.0f)
{
normalx = 0.0f;
normaly = 0.0f;
return 1.0f;  // My code always returns this when collision occurs 
}
// if there was a collision,, It never checks for this since its returns 1.0 all the time 
else 
{         
// calculate normal of collided surface
if (xEntry > yEntry)
{
if (xInvEntry < 0.0f)
{
normalx = 1.0f;
normaly = 0.0f;
}
     else
{
normalx = -1.0f;
normaly = 0.0f;
}
}
else
{
if (yInvEntry < 0.0f)
{
normalx = 0.0f;
normaly = 1.0f;
}
     else
{
normalx = 0.0f;
         normaly = -1.0f;
}
}

// return the time of collision
return entryTime;
}

Note: Please offer only positive, constructive comments - we are looking to promote a positive atmosphere where collaboration is valued above all else.




PARTNERS