Sign in to follow this  
Spa8nky

2D SAT AABB AABB collision, contact point is not accurate enough?

Recommended Posts

Currently I have the following for detecting collisions between two 2D AABBs:
        public static bool TestAABBAABB(Shape s1, Shape s2, ref Contact2D contact)
        {
            CD_AABB2D a = (CD_AABB2D)s1;
            CD_AABB2D b = (CD_AABB2D)s2;

            // [Separating Axis Theorem]
            // • Two convex shapes only overlap if they overlap on all axes of separation
            // • In order to create accurate responses we need to find the collision vector (Minimum Translation Vector)   
            // • Find if the two boxes intersect along a single axis 
            // • Compute the intersection interval for that axis
            // • Keep the smallest intersection/penetration value

            // Minimum Translation Vector parameters
            float mtv_Distance = float.MaxValue;            // Set current minimum distance (max float value so next value is always less)
            int mtv_Axis = 0;                               // Axis along which to travel with the minimum distance

            // For each separating axis
            for (int i = 0; i < 2; ++i)
            {
                // Find distance intervals for current two slabs
                // Distance is between slab min/max values
                float d_S0 = a.MinPoint.Index(i) - b.MaxPoint.Index(i);
                float d_S1 = b.MinPoint.Index(i) - a.MaxPoint.Index(i);

                // The distance is positive if the intervals do not overlap
                // Must be >= to 0 and not > 0, otherwise MTV can equal Vector2.Zero and cause NaN
                if (d_S0 >= 0f || d_S1 >= 0f)
                {
                    return false;
                }

                // Current distance interval for slabs
                float d = (d_S0 > d_S1) ? -d_S0 : d_S1;

                // If d is the smallest distance so far
                if (Math.Abs(d) < Math.Abs(mtv_Distance))
                {
                    // Store the distance and the current axis
                    mtv_Distance = d;
                    mtv_Axis = i;
                }
            }

            // Minimum Translation Vector
            Vector2 mtv = Vector2.Zero;

            switch (mtv_Axis)
            {
                case 0:
                    mtv.X = mtv_Distance;
                    break;
                case 1:
                    mtv.Y = mtv_Distance;
                    break;
            }

            contact.normal = Vector2.Normalize(mtv);
            contact.point = (a.Position + b.Position) * 0.5f;                    // Point for half way between the centres
            contact.penetration = Math.Abs(mtv_Distance) + Settings.EPSILON;

            return true;
        }



Currently there is only only one contact point, which is set to half way between the AABB centres. Unfortunately I have found that this is not going to be accurate enough when calculating impulses in a physics engine. I've had a look through Oliii's "2D box contact calculations" code and I was wondering if anyone had any advice on the subject or alternative tutorials/links/books they could recommend in helping me find these contacts? Thank you. EDIT: Edge/Edge contact points are what I'm having difficulty finding. Vertex/Vertex, Edge/Vertex, Vertex/Edge have all been found correctly. [Edited by - Spa8nky on February 22, 2010 8:53:04 AM]

Share this post


Link to post
Share on other sites
No, your contact point being set to halfway between the two AABB centers isn't quite good....it is easy to code, but it isn't the best representation of the contact point.

Looking at the edge/edge case you mentioned in your edit...once you know the overlap interval for the pair of edges that are in contact (regardless of orientation...I know yours are AABB), you could choose a contact point to be at the midpoint along that overlap interval (*on* the edge) or just take an appropriate edge endpoint and use the edge endpoint as your contact point (there will always be at least one edge endpoint from each edge on the overlap interval).

Share this post


Link to post
Share on other sites
in case of edge-edge contacts, you will have two contact pairs, which will be linked to two corners of the two edges.

The two edges provide 4 vertices, two for each edges. The vertices to be considered are the two vertices that are the two vertices 'in the middle'.

Quote:

A B
|------------|
|----------------|
C D

-> x-------x (contacts)
C B





A B
|------------|
|----------------|
C D

-> x------------x (contacts)
A B





A B
|------------|
|----------------|
C D

-> x--------x (contacts)
A D


Sorting your vertices along the edge direction, and taking the two in the middle will give you the two points of contact.

Share this post


Link to post
Share on other sites
Thanks guys. I've now got the following code for doing what Oliii suggested:


private static Vector2[] GetContactPoints_EdgeEdge(List<Vector2> supportA, List<Vector2> supportB)
{
// [Finding contact points with edge/edge collision]
// • Sort your vertices along the edge direction
// • The two points in middle will give you the two points of contact
//
//=======================================================
//--[Example 1]------------------------------------------
//=======================================================
// A B (supportA points)
// |------------|
// |----------------|
// C D (supportB points)
//
// x-------x (contact points)
// C B
//=======================================================
//--[Example 2]------------------------------------------
//=======================================================
// A B (supportA points)
// |------------|
// |----------------| (supportB points)
// C D
//
// x------------x (contact points)
// A B
//=======================================================
//--[Example 3]------------------------------------------
//=======================================================
// A B (supportA points)
// |------------|
// |----------------| (supportB points)
// C D
//
// x----------x (contact points)
// A D
//=======================================================

// Direction of sorting
Vector2 direction = supportA[1] - supportA[0];

List<SupportSort> supports = new List<SupportSort>
{
new SupportSort(supportA[0], direction, 0),
new SupportSort(supportA[1], direction, 0),
new SupportSort(supportB[0], direction, 1),
new SupportSort(supportB[1], direction, 1)
};

// Sort the supports list by d value
supports.Sort(delegate(SupportSort s1, SupportSort s2) {return s1.d.CompareTo(s2.d); });

Vector2[] contacts = new Vector2[2];

// Take middle two points as contact points
for (int i = 2; i < 4; ++i)
{
SupportSort ss = supports[i];

if (ss.body == 0)
{
contacts[i - 2] = ss.p;
}
else
{
contacts[i - 1] = ss.p;
}
}

return contacts;
}






Please let me know if you can see any horrible errors; I think it works fine based on your precise instructions.

EDIT: The if, else function is incorrect. I'm not near my code at the moment so I cannot correct it just yet.

[Edited by - Spa8nky on February 22, 2010 6:09:01 PM]

Share this post


Link to post
Share on other sites
There are probably optimisations to be added, notably the qsort() function, with is a bit overkill for just four points (I think I used that myself, but I'm a bit lazy!). a bit of logic should do the trick. In any case, that should work.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this