• 12
• 12
• 9
• 10
• 13

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

This topic is 2950 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 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 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 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;                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 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.