Sign in to follow this  
mrbig

Detecting the Kind of Contacts Between Polygons

Recommended Posts

I AM using the SAT.
I want to know which of the two cases occured so I could find the exact contact point.
To find the contact point in case 1, I need to find the bottom-most vertex of the triangle in the direction of the MTD, and then add the MTD vector to it.
In case two, I need to do the same but with the negated MTD and the triangle.
I want to know which of the two cases occured so I could know how to respond.

Share this post


Link to post
Share on other sites
Quote:
In case two, I need to do the same but with the negated MTD and the triangle.
This is the key here, In addition to the information you're currently tracking, you need to track the 'side' associated with the mtd. That is, on the 1d number line on which the intervals were analyzed, was the minimum distance associated with moving the second interval left on the number line, or right? At the end of the process you have a 'side', usually encoded as -1 or +1, which can be used directly as the sign of the mtd for the purpose of finding the contact points.

Ok, that wasn't a very good explanation, so please ask if you need further clarification.

Share this post


Link to post
Share on other sites
I didn't really get your explanation.
Assuming 'body' is the triangle, 'push' is the MTD and the case is case 1, this function works:


void find_support_point(vec_t push, body_t body, int &support_index)
{
float mindist = vec_dot_product(push, body.edge[0].world), dist;
static const float threshold = 1.0E-8f;
int i;
support_index = 0;

for(i = 1; i < body.edge_num; i++)
{
dist = vec_dot_product(push, body.edge[i].world);

if(dist < mindist - threshold)
{
mindist = dist;
support_index = i;
}
}
}





What exactly should I do (code wise) to make it detect case 1 or case 2 and respond correctly?

Share this post


Link to post
Share on other sites
You can tell by which has vertices in which. If you wind counter-clockwise then if any vertex of the square is to the left of all of the sides of the triangle then it lies within the triangle. With 2D you can just use (-dy,dx) to get a left pointing vector to use with the sign of the dot product to tell if it is left or right. In 3D you can use the cross product of the normal for the plane of the polygon and the direction from one vertex to the next to get a left pointing vector.

Share this post


Link to post
Share on other sites
Quote:
You can tell by which has vertices in which. If you wind counter-clockwise then if any vertex of the square is to the left of all of the sides of the triangle then it lies within the triangle. With 2D you can just use (-dy,dx) to get a left pointing vector to use with the sign of the dot product to tell if it is left or right. In 3D you can use the cross product of the normal for the plane of the polygon and the direction from one vertex to the next to get a left pointing vector.
This is all unnecessary; the contact points are predetermined by the results of the SAT interval tests, so no such post-processing is required.

Let's look at your diagram again:

???

In the first case, the 'push' vector is presumably derived from the normal to the top edge of the box, and the contact point 'belongs' to the triangle (i.e. the bottom-most vertex). In the second example the push vector is derived from a triangle edge normal and the contact point is the upper-right corner of the box.

A more general way to look at it is to find the supporting features for both objects and clip them together to find the contact points. Quite often it will be a point clipped to a line segment, which is simply the point itself. Sometimes it may be two line segments (e.g. if an edge of the triangle were parallel to an edge of the box), in which case you would clip the segments together to yield two contact points.

No matter how you approach it, in order to find the contact points correctly you need to know the 'side' corresponding to the mtd. Let's look at a sample interval test:
1 *-------------*
2 *-------*
In this example 2 gets pushed to the right, so side = 1. In this example:
     1 *--------*
2 *-------*
2 gets pushed to the left, so side = -1. As you process each axis, you keep track of the side associated with the mtd. At the end of the process this gives you the information you need to correctly determine the contact points, either by using it as the sign of the mtd and clipping features together, or by using various shortcuts to more directly determine the contact points.

I have to admit I'm not doing a very good job of explaining things this morning. I'm sure that in one way or another this is all represented in oliii's demo code, so if you're working from that you should be able to piece it together.

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