2D AABB vs AABB Sweep : How to calculate hit normal?

I've implemented a 2D AABBvsAABB sweep cast into my game, however, I'm having difficulty calculating the hit normal of the sweep cast.

I have the sweep direction, both a and b AABB positions and xy min-maxs, first and last hit times to work with, but not the colliding edge(s) or normal direction. I just can't conceptualise an efficient solution to this specific problem. Any Ideas? :)

*edit

This is what I have so far - just a general implementation of Gomez's and Christer Ericson's AABB sweep. There's no hit normal, so while the normal calculation is a mystery to me I'm unable to produce any collision response for my character controller.

bool SweepVelAABBvsAABB(AABB a, AABB b, Vector2 v, out Vector2 outVel, out Vector2 norm )
{
outVel = v; //Initialise out velocity
norm = Vector2.zero;

if( AABBvsAABB(a,b) ) return true; //return early if a,b overlap

v = -v;
float hitTime = 0.0f;
float outTime = 1.0f;

if(v.x < 0.0f) //sweep is going right
{
if(b.max.x < a.min.x) return false;
if(a.max.x < b.min.x) hitTime = Mathf.Max( (a.max.x - b.min.x) / v.x, hitTime );
if(b.max.x > a.min.x) outTime = Mathf.Min( (a.min.x - b.max.x) / v.x, outTime );
}
else if(v.x > 0.0f) //sweep is going left
{
if(b.min.x > a.max.x) return false;
if(b.max.x < a.min.x) hitTime = Mathf.Max( (a.min.x - b.max.x) / v.x, hitTime );
if(a.max.x > b.min.x) outTime = Mathf.Min( (a.max.x - b.min.x) / v.x, outTime );
}

if(hitTime > outTime) return false;

//=================================

if(v.y < 0.0f) //sweep is going up
{
if(b.max.y < a.min.y) return false;
if(a.max.y < b.min.y) hitTime = Mathf.Max( (a.max.y - b.min.y) / v.y, hitTime );
if(b.max.y > a.min.y) outTime = Mathf.Min( (a.min.y - b.max.y) / v.y, outTime );
}
else if(v.y > 0.0f) //sweep is going down
{
if(b.min.y > a.max.y) return false;
if(b.max.y < a.min.y) hitTime = Mathf.Max( (a.min.y - b.max.y) / v.y, hitTime );
if(a.max.y > b.min.y) outTime = Mathf.Min( (a.max.y - b.min.y) / v.y, outTime );
}

if(hitTime > outTime) return false;

outVel = -v * hitTime;

return true;
}

• Are your objects boxes? Are they supposed to be able to rotate? – aaaaaaaaaaaa May 5 '12 at 15:23

I've managed to come up with a simple and efficient solution by observing the separating axes.

// Sweep a in the direction of v against b, returns true & info if there was a hit
// ===================================================================
bool SweepBoxBox( AABB a, AABB b, Vector2 v, out Vector2 outVel, out Vector2 hitNormal )
{
//Initialise out info
outVel = v;
hitNormal = Vector2.zero;

// Return early if a & b are already overlapping
if( AABBvsAABB(a, b) ) return false;

// Treat b as stationary, so invert v to get relative velocity
v = -v;

float hitTime = 0.0f;
float outTime = 1.0f;
Vector2 overlapTime = Vector2.zero;

// X axis overlap
if( v.x < 0 )
{
if( b.max.x < a.min.x ) return false;
if( b.max.x > a.min.x ) outTime = Mathf.Min( (a.min.x - b.max.x) / v.x, outTime );

if( a.max.x < b.min.x )
{
overlapTime.x = (a.max.x - b.min.x) / v.x;
hitTime = Mathf.Max(overlapTime.x, hitTime);
}
}
else if( v.x > 0 )
{
if( b.min.x > a.max.x ) return false;
if( a.max.x > b.min.x ) outTime = Mathf.Min( (a.max.x - b.min.x) / v.x, outTime );

if( b.max.x < a.min.x )
{
overlapTime.x = (a.min.x - b.max.x) / v.x;
hitTime = Mathf.Max(overlapTime.x, hitTime);
}
}

if( hitTime > outTime ) return false;

//=================================

// Y axis overlap
if( v.y < 0 )
{
if( b.max.y < a.min.y ) return false;
if( b.max.y > a.min.y ) outTime = Mathf.Min( (a.min.y - b.max.y) / v.y, outTime );

if( a.max.y < b.min.y )
{
overlapTime.y = (a.max.y - b.min.y) / v.y;
hitTime = Mathf.Max(overlapTime.y, hitTime);
}
}
else if( v.y > 0 )
{
if( b.min.y > a.max.y ) return false;
if( a.max.y > b.min.y ) outTime = Mathf.Min( (a.max.y - b.min.y) / v.y, outTime );

if( b.max.y < a.min.y )
{
overlapTime.y = (a.min.y - b.max.y) / v.y;
hitTime = Mathf.Max(overlapTime.y, hitTime);
}
}

if( hitTime > outTime ) return false;

// Scale resulting velocity by normalized hit time
outVel = -v * hitTime;

// Hit normal is along axis with the highest overlap time
if( overlapTime.x > overlapTime.y )
{
hitNormal = new Vector2(Mathf.Sign(v.x), 0);
}
else
{
hitNormal = new Vector2(0, Mathf.Sign(v.y));
}

return true;
}


Notice how the A's hit normal is sum(Normals of Vectors of Edges on B involved in collision). In order words:

1. Find the edges involved on the object we are colliding with.
2. From get the vertices from those edges.
3. Sum the normals of those vertices.
4. Turn the resulting vector into a unit vector (normalise).

Remember that an 'edge' might actually be just one vertex (we are colliding with the corner on another box).

You will also note that this applies to B's hit normal.

• Ah I see, that would be good way to get the normal direction, however, one problem with that is that I don't have the edge that is colliding to calculate the normal direction. – Larolaro May 4 '12 at 13:34
• make the aabb vs aabb test, then further check which of the edges are colliding. – Gustavo Maciel May 4 '12 at 15:13
• Unfortunately, how to check the edges is the very thing that eludes me, I can't check the edges in question if I don't know how to get them. – Larolaro May 4 '12 at 17:48
• check aabb vs aabb if true, then check vertex vs aabb, get all vertices that intersects, get the edges by the vertices, calculate the normal. – Gustavo Maciel May 4 '12 at 18:25
• I can do that but at no point is the "A" actually intersecting "B", even if were to be (the sweep would become invalid being inside of the object you're sweeping against) I would get any number of vertices/edges irrelevant to the actual colliding edge. Would you mind posting an answer to explain your theory? – Larolaro May 4 '12 at 18:35

If I understand correctly, your algorithm so far finds the position along the motion of A at which A and B are just touching.

With that position, perform an one-dimensional intersection test between A and B on all three axes. One (or more in corner cases) of these axes will have no overlap; the hit normal should be parallel to that axis and in the direction from B to A.

If more than one axis has no overlap, then you have hit an edge or corner perfectly; you could either arbitrarily pick an option, or sum the results for a "rounded" corner.

• Checking overlaps with "B" and the hit time "A" would give inconsistent results because the edges are pretty much equal to each other (the calculation slides the edges infinitely flush) even with an additional epsilon on the hit time, the intersection would be always overlapping over two axes. – Larolaro May 5 '12 at 15:00
• Yes, it should be overlapping over two axes. It is the axis that is not overlapping, or barely overlapping, that is parallel to the normal. If you are concerned about numerical error, then choose the axis which is least overlapping (or not overlapping). – Kevin Reid May 5 '12 at 16:11