Determine Collision Point and Normal (3D SAT AABB-AABB)

Recommended Posts

AABB.cpp


int AABB::supportFaceCount()
{
// there are only three directions for every face of an AABB box.
return 3;
}

XMVECTOR AABB::supportFaceDirection(int i)
{
// the three axes of an AABB box. along the x, y and z axis.
static const XMVECTOR s_aabbAxes[] = { XMVectorSet(1, 0, 0, 0), XMVectorSet(0, 1, 0, 0), XMVectorSet(0, 0, 1, 0) };
return s_aabbAxes[i];
}

int AABB::supportEdgeCount()
{
// there are only three directions for every edges of an AABB box.
return 3;
}

XMVECTOR AABB::supportEdgeDirection(int i)
{
// every edge go along the x y, or z axis.
static const XMVECTOR s_aabbEdges[] = { XMVectorSet(1, 0, 0, 0), XMVectorSet(0, 1, 0, 0), XMVectorSet(0, 0, 1, 0) };
return s_aabbEdges[i];
}

void AABB::supportInterval(XMVECTOR direction, float& min, float& max)
{
XMVECTOR centre = XMVectorSet(Center[0], Center[1], Center[2], 1);
// projection of the box centre
float p = XMVector3Dot(centre, direction).m128_f32[0];

// projection of the box extents
float rx = fabs(direction.m128_f32[0]) * Radius[0];
float ry = fabs(direction.m128_f32[1]) * Radius[1];
float rz = fabs(direction.m128_f32[2]) * Radius[2];

// the projection interval along the direction.
float rb = rx + ry + rz;
min = p - rb;
max = p + rb;
}
bool ObjectsSeparatedAlongDirection(XMVECTOR& direction, AABB* a, AABB* b)
{
float mina, maxa;
float minb, maxb;
a->supportInterval(direction, mina, maxa);
b->supportInterval(direction, minb, maxb);
return (mina > maxb || minb > maxa);
}

bool ObjectsIntersected(AABB* a, AABB* b)
{
// test faces of A
for(int i = 0; i < a->supportFaceCount(); i++)
{
XMVECTOR direction = a->supportFaceDirection(i);
if(ObjectsSeparatedAlongDirection(direction, a, b))
return false;
}

// test faces of B
for(int i = 0; i < b->supportFaceCount(); i++)
{
XMVECTOR direction = b->supportFaceDirection(i);
if(ObjectsSeparatedAlongDirection(direction, a, b))
return false;
}

// test cross product of edges of A against edges of B.
for(int i = 0; i < a->supportEdgeCount(); i++)
{
XMVECTOR edge_a = a->supportEdgeDirection(i);

for(int j = 0; j < b->supportEdgeCount(); j++)
{
XMVECTOR edge_b = b->supportEdgeDirection(j);

XMVECTOR direction = XMVector3Cross(edge_a, edge_b);

if(ObjectsSeparatedAlongDirection(direction, a, b))
return false;
}
}
return true;
}

Share on other sites

You don't need to test edge directions for two AABB. This is only necessary for OBB.

For two AABB everything boils down to determine the two faces that are in contact. Then you can clip one against the side planes of the other. This gives you the contact points. For the normal you can choose either face direction.

I gave a talk about contact generation some time ago. It doesn't handle AABB vs AABB, but the more general OBB vs OBB. Your case is simpler since you don't need to handle the edge cases.

Edited by Dirk Gregorius

Share on other sites
2 hours ago, Dirk Gregorius said:

You don't need to test edge directions for two AABB. This is only necessary for OBB.

Thanks for the input.

2 hours ago, Dirk Gregorius said:

Then you can clip one against the side planes of the other﻿. This gives you the contact points.﻿﻿

How do I do that? Can you give me a pseudo code for that? It took me several hours to code that SAT part. At the moment, I use this code for finding contact point and normal. Is that right?

static bool TestAxis(XMVECTOR axis, AABB& a, AABB& b, XMVECTOR& mtd, float& mtd2)
{
// intervals along axis
float mina, maxa;
float minb, maxb;
a.supportInterval(axis, mina, maxa);
b.supportInterval(axis, minb, maxb);

// calculate the two possible overlap ranges.
// either we overlap on the left or right sides.
float d0 = (maxb - mina); // 'left' side
float d1 = (maxa - minb); // 'right' side

// the axis length squared
float axis_length_squared = XMVector3Dot(axis, axis).m128_f32[0];

// axis is degenerate. ignore.
if(axis_length_squared < 1.0e-8f)
return true;

// intervals do not overlap. no intersection.
if(d0 < 0.0f || d1 < 0.0f)
return false;

// find out if we overlap on the 'right' or 'left' of the object.
float overlap = (d0 < d1)? d0 : -d1;

// the mtd vector for that axis
XMVECTOR sep = axis * (overlap / axis_length_squared);

// the mtd vector length squared.
float sep_length_squared = XMVector3Dot(sep, sep).m128_f32[0];

// if that vector is smaller than our computed MTD (or the mtd hasn't been computed yet)
// use that vector as our current mtd.
if(sep_length_squared < mtd2 || mtd2 < 0.0f)
{
mtd2 = sep_length_squared;
mtd  = sep;
}
return true;
}

static bool AABBAABBIntersection(RigidBody* rba, AABB& a, RigidBody* rbb, AABB& b, Contact* c)
{
XMVECTOR mtd = XMVectorSet(0, 0, 0, 0), mtddirection;
float mtd2 = -1.0f;

// test faces of A
for(int i=0; i<a.supportFaceCount(); i++)
{
if(!TestAxis(a.supportFaceDirection(i), a, b, mtd, mtd2))
return false;
}

// test faces of B
for(int i=0; i<b.supportFaceCount(); i++)
{
if(!TestAxis(b.supportFaceDirection(i), a, b, mtd, mtd2))
return false;
}

// no intersections were ever tested.
if(mtd2 < 0.0f)
return false;

float Penetration = sqrt(mtd2);

c->a = rba;
c->b = rbb;
c->n = XMVector3Normalize(mtd);
c->p = rba->GetPosition() + mtd*Penetration;

return true;
}

Edited by isu diss

Share on other sites
6 hours ago, isu diss said:

Thanks for the input.

How do I do that? Can you give me a pseudo code for that? It took me several hours to code that SAT part. At the moment, I use this code for finding contact point and normal. Is that right?


static bool TestAxis(XMVECTOR axis, AABB& a, AABB& b, XMVECTOR& mtd, float& mtd2)
{
// intervals along axis
float mina, maxa;
float minb, maxb;
a.supportInterval(axis, mina, maxa);
b.supportInterval(axis, minb, maxb);

// calculate the two possible overlap ranges.
// either we overlap on the left or right sides.
float d0 = (maxb - mina); // 'left' side
float d1 = (maxa - minb); // 'right' side

// the axis length squared
float axis_length_squared = XMVector3Dot(axis, axis).m128_f32[0];

// axis is degenerate. ignore.
if(axis_length_squared < 1.0e-8f)
return true;

// intervals do not overlap. no intersection.
if(d0 < 0.0f || d1 < 0.0f)
return false;

// find out if we overlap on the 'right' or 'left' of the object.
float overlap = (d0 < d1)? d0 : -d1;

// the mtd vector for that axis
XMVECTOR sep = axis * (overlap / axis_length_squared);

// the mtd vector length squared.
float sep_length_squared = XMVector3Dot(sep, sep).m128_f32[0];

// if that vector is smaller than our computed MTD (or the mtd hasn't been computed yet)
// use that vector as our current mtd.
if(sep_length_squared < mtd2 || mtd2 < 0.0f)
{
mtd2 = sep_length_squared;
mtd  = sep;
}
return true;
}


static bool AABBAABBIntersection(RigidBody* rba, AABB& a, RigidBody* rbb, AABB& b, Contact* c)
{
XMVECTOR mtd = XMVectorSet(0, 0, 0, 0), mtddirection;
float mtd2 = -1.0f;

// test faces of A
for(int i=0; i<a.supportFaceCount(); i++)
{
if(!TestAxis(a.supportFaceDirection(i), a, b, mtd, mtd2))
return false;
}

// test faces of B
for(int i=0; i<b.supportFaceCount(); i++)
{
if(!TestAxis(b.supportFaceDirection(i), a, b, mtd, mtd2))
return false;
}

// no intersections were ever tested.
if(mtd2 < 0.0f)
return false;

float Penetration = sqrt(mtd2);

c->a = rba;
c->b = rbb;
c->n = XMVector3Normalize(mtd);
c->p = rba->GetPosition() + mtd*Penetration;

return true;
}

Well, your function computes the minimum translation vector - which is nothing more than a vector you can apply, to resolve a penetration in the most basic way. Dont know what you are making, but if this is enough for you - then its totally fine. For example, for a simple game this may be totally fine. If not, check out dirks great post about contact generation or other resources regarding this topic.

Also, if you want to apply rotation to your bodies, then this system does not work at all - then you definitly need to deal with OBB´s instead.

Share on other sites

@Finalspace I'm making a cricket game. So far, I've been able to resolve collision for ball-ground(ball without any rotation after hitting the ground) & ball-stump(not accurately). I need accurate contact point (c->p) to compute rotation part in the collision resolving code. As you can see the above posted code (c->p) is computed using (c->n), cross product of ra n rb with n goes to zero in the collision resolve code.

void CollisionResponse(Contact *c, float epsilon)
{
XMVECTOR pbdot = c->b->GetVelocityAtPoint(c->p);
XMVECTOR n = c->n;
XMVECTOR ra = (c->p - c->a->GetPosition());
XMVECTOR rb = (c->p - c->b->GetPosition());
XMVECTOR vrel = XMVector3Dot(c->n, (padot - pbdot));
float numerator = (-(1.0f + epsilon)*vrel.m128_f32[0]);
float term1 = (1.0f / c->a->GetMass());
float term2 = (1.0f / c->b->GetMass());
XMVECTOR term3 = XMVector3Dot(c->n, XMVector3Cross(XMVector4Transform(XMVector3Cross(ra, n), c->a->GetIInverse()), ra));
XMVECTOR term4 = XMVector3Dot(c->n, XMVector3Cross(XMVector4Transform(XMVector3Cross(rb, n), c->b->GetIInverse()), rb));
float j = (numerator / (term1+ term2 + term3.m128_f32[0] + term4.m128_f32[0]));
XMVECTOR f = (j*n);

}

Share on other sites
3 hours ago, isu diss said:

@Finalspace I'm making a cricket game. So far, I've been able to resolve collision for ball-ground(ball without any rotation after hitting the ground) & ball-stump(not accurately). I need accurate contact point (c->p) to compute rotation part in the collision resolving code. As you can see the above posted code (c->p) is computed using (c->n), cross product of ra n rb with n goes to zero in the collision resolve code.


void CollisionResponse(Contact *c, float epsilon)
{
XMVECTOR pbdot = c->b->GetVelocityAtPoint(c->p);
XMVECTOR n = c->n;
XMVECTOR ra = (c->p - c->a->GetPosition());
XMVECTOR rb = (c->p - c->b->GetPosition());
XMVECTOR vrel = XMVector3Dot(c->n, (padot - pbdot));
float numerator = (-(1.0f + epsilon)*vrel.m128_f32[0]);
float term1 = (1.0f / c->a->GetMass());
float term2 = (1.0f / c->b->GetMass());
XMVECTOR term3 = XMVector3Dot(c->n, XMVector3Cross(XMVector4Transform(XMVector3Cross(ra, n), c->a->GetIInverse()), ra));
XMVECTOR term4 = XMVector3Dot(c->n, XMVector3Cross(XMVector4Transform(XMVector3Cross(rb, n), c->b->GetIInverse()), rb));
float j = (numerator / (term1+ term2 + term3.m128_f32[0] + term4.m128_f32[0]));
XMVECTOR f = (j*n);

}

Okay then you have no choice and need to produce proper contact points and switch to OBB instead.

For sphere vs OBB you need just one contact point, for OBB vs OBB you can have at max 4 contact points.

I cannot explain how the generation in actual 3D works, but the concept for 2D are similar.

First of, you use SAT to determine the normal with most overlap and record the penetration depth and the normal/axis -> This is what you actually have right now. Also you need to record the body and the face where the axis was found, this is either A or B.

Treat A as the reference and B as the incident body first. But if the most penetrating axis is found on B, then B is your reference body and A is your incident body. Its just swapped.

The recorded body and face A is your reference face. The most anti-parallel face on B is your incident face.

Next is to clip the incident face against the side planes of the reference face (Sutherland Hodgman clipping) -> You dont clip against the reference face.

You save all the clipped points below the reference face. Note that this clipped points are on the incident face - not on the reference face!

For better coherence you project the saved clip points to the reference face.

Now you have all the contact points on A. To get the second contact point its as simple as: PointOnB = PointOnA + -Normal * PenetrationDistance;

There you have it.

Again, everything i am talking about is good explained in "DirkGregorius_Contacts.pdf" - even with code!

One last tip i can give you: Visualize everything! Draw the face planes, the clipping planes, the contact points and the penetration depth. Colorize the reference body red, the incident body blue  Trust me, this helps a lot!

Edited by Finalspace

Share on other sites

I learned SAT and applied for AABB. It gives me part of the answer. To have the full answer, I need S-H clippings. But S-H clipping is so hard. @Finalspacetold me how to combine SAT result with S-H clippings for AABB. I don't have much experience of implementing like that. Can anybody share sourcecode? even one bit? please, I wouldn't ask if I knew

Share on other sites

Here you go:

//--------------------------------------------------------------------------------------------------
RnArray< RnVector3 > rnClipPolygon( const RnArray< RnVector3 >& Polygon, const RnPlane& Plane, int Edge )
{
RN_ASSERT( Polygon.Size() >= 3 );
RnArray< RnVector3 > Out;

RnVector3 Vertex1 = Polygon.Back();
float Distance1 = rnDistance( Plane, Vertex1 );

for ( int Index = 0; Index < Polygon.Size(); ++Index )
{
RnVector3 Vertex2 = Polygon[ Index ];
float Distance2 = rnDistance( Plane, Vertex2 );

if ( Distance1 <= 0.0f && Distance2 <= 0.0f )
{
// Both vertices are behind the plane - keep vertex2
Out.PushBack( Vertex2 );
}
else if ( Distance1 <= 0.0f && Distance2 > 0.0f )
{
// Vertex1 is behind of the plane, vertex2 is in front -> intersection point
float Fraction = Distance1 / ( Distance1 - Distance2 );
RnVector3 IntersectionPoint = Vertex1.Position + Fraction * ( Vertex2.Position - Vertex1.Position );

// Keep intersection point
Out.PushBack( IntersectionPoint );
}
else if ( Distance2 <= 0.0f && Distance1 > 0 )
{
// Vertex2 is behind of the plane, vertex1 is in front -> intersection point
float Fraction = Distance1 / ( Distance1 - Distance2 );
RnVector3 IntersectionPoint = Vertex1.Position + Fraction * ( Vertex2.Position - Vertex1.Position );

// Keep intersection point
Out.PushBack( IntersectionPoint );

// And also keep vertex2
Out.PushBack( Vertex2 );
}

// Keep vertex2 as starting vertex for next edge
Vertex1 = Vertex2;
Distance1 = Distance2;
}

return Out;
}

HTH,

-Dirk

Create an account

Register a new account

• What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 11
• 13
• 9
• 25
• 18
• Forum Statistics

• Total Topics
634437
• Total Posts
3017459
×