Jump to content
  • Advertisement
Sign in to follow this  
Donner

Seperating Axis Theorem - Find the contact information

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey, so I understand the Seperating Axis Theorem (SAT) and how it works, but what I need to know is for two OBBs, where exactly they collide. This thread helped a lot so far: Click (thanks to oliii). So I think a good approach to get the contact point(s) is the following:
Quote:
1. Find the separating axis with minimum overlap. In this determination, I bias against edge-edge contact. 2. If the minimum axis is edge-edge, I just generate one point. 3. If the minimum axis is face-(vert | edge | face), I determine the reference face according to the minimum axis and the incident face on the other box. I then clip the incident face against the reference face. I then reduce the generated points to at most 4 using an approximate convex hull.
So first of all, if I know which of the axis is the one with minimum overlap, how do I know what kind of collision this is? So what axis means what kind of collision(edge-edge, face-vertex, face-edge, face-face)? Then, how do I find the exact contact point? If I have a edge-edge collision, I need one point (and the normal). If I have a vertex-face collision, I need one point (and the normal). If I have a face-face collision, I need four points (and the normal of the faces). And so on... So how do I find those points? Thanks, D.

Share this post


Link to post
Share on other sites
Advertisement
I think you only have two types of collision (in case of SAT):

Point(the two edges at that point to be precise) intersect the edge of the other box, and vice versa.
and:

|
|
---|-----
| |
--------
|
|



The others you mentioned are special cases, that might never occur.

And you can determine which is that point and that side, at that point where you determine the axe and the minimal penetration.
So the point's place will be the place of penetration.

If it's not enough (you need a area of impact instead and its center for example):

intersect the 2 lines (from the point) with the edge of type one, and you have the penetrated section.
and for type 2:

|
|
--/-----
|/|
----/--
|
|


I've implemented SAT (my signature) and I think it's hard to give a general solution to the response, it depends heavily on the thing you want from it.

All I can say is work hard with a pen and a paper.

I hope that helps somehow...

Share this post


Link to post
Share on other sites
Hey, thank you so much for your answer! :)

I still got a few questions left, though:
Well, I see how you can reduce the collision types to two basic types (oliii was speaking of point-plane and edge-edge...).

But I really don't get how to determine what kind of collision it is if an axis is overlapping.

So if I got the following axes (A and B are the two OBBs):
A.X
A.Y
A.Z

B.X
B.Y
B.Z

A.X x B.X
A.X x B.Y
A.X x B.Z

A.Y x B.X
A.Y x B.Y
A.Y x B.Z

A.Z x B.X
A.Z x B.Y
A.Z x B.Z


Which of them mean what kind of collision? Isn't it possible to have some kind of a table which says for example: if A.X is overlapping, we have a edge-edge-collision or whatever...?


my second problem:
I need to get all the "border collision points", so if there is a Face-Face collision, I need the 4 points (you can see what I meen in the picture at the end of this post). But how do I know if there is a face-face collision? How do I find the points that actually matter?

Here the picture I made (I always need the points which are marked red):
ImageHost.org

EDIT: I made a mistake: The left picture is not a point-point collision, of course, but a combination of point-face and edge-edge... But still I don't know how to get the position of those contact points...???

[Edited by - Donner on November 1, 2009 1:03:10 PM]

Share this post


Link to post
Share on other sites
Sorry, I was speaking of 2D SAT. My mistake.
Anyway, the problem is that you will probably never get perfect point-face/anything collisions, just edge-face collision (unless you have infinite framerate)

I don't know 3D SAT, but I'm sure you can determine which face is penetrated (at the time you determine the minimal penetration's axis, it's one of the two perpendicular faces) so you have the normal you seek.

EDIT: this still stands: Then I would check all edges of the other box against all the faces of the first box. ("section_of_line-rectangle intersection"). And vice versa

This would produce a bunch of intersection points (their amount may vary, you have to implement good indexing)

So you have these points, and they will form a collision "point-cloud", so you can do anything with this cloud, maybe determining its center to have the collision point's coordinate.


I hope that helps. (Or it's true, I'm not sure at all...)

EDIT: it's probably totally wrong what I'm saying here.

Share this post


Link to post
Share on other sites
you can't really rely on the axis to determine the type of collision. If you have the example 1, the mtd direction could be a face normal, or the cross product of two edges, both being on the faces that generate the 4 points of contact. Taking the edges, you will end up with a direction parallel to the face normal, but the result will not be a edge-edge collision, but a face-face collision.

Once you have the MTD direction (in example 1, pointing up), you need to find the supporting feature for both objects along that direction.

A supporting feature will be a set of points that share the same projection value along the MTD. If you take the bottom box of example 1, the MTD direction, or normal of contact, will be pointing up.

The four points at the top of box A will share the same value when projected vertically. These four points are at the 'maxima' of A.

The four points at the bottom side of box B will share a common value too.

Since you have four points on a, and four points on B, then you have a face-face collision. These two set of four points represent the supporting features of box A and box B along the collision direction.

You can also use the topology of the boxes to detect what feature support a box along a given direction. Given a direction, a box's supporting feature will either be a single vertex, an edge, or a rectangular face.

So you have three cases for polytopes (basically objects made of polygonal faces, like pyramids and so on). A supporting face, a supporting edge, or a supporting vertex.

That's three cases you have to consider to compute the contact points on the two objects.

Given the SAT, the most likely outcomes are.

point-face
face-point
edge-edge
edge-face
face-edge
face-face

the cases like point-edge or point-point should not happen, due to how the SAT works.

To find the supporting feature on a box, you can work through elimination. Here, I'm assuming the axis is normalised.

Quote:

void findSupportingFeature(const Vector& axis, const OBBox& box, Vector* supports, int supportsCount)
{
// start with nothing
supportsCount = 0;

static const float align_tolerance = acos(pi() * 0.1f / 180.0f); // tolerance of 1/10 degree to detect alignment

// check box faces first one by one
for(int i = 0; i < 6; i ++)
{
float deviation = dotProduct(box.faceNormal(i), axis);

// face normal parallel and in same direction to axis.
// therefore, face IS supporting the box along axis.
if(deviation > align_tolerance)
{
// record all the points in the face polygon
for(int j = 0; j < 4; j++)
{
supports[supportsCount++] = box.faceVertex(i, j);
}
return;
}
}

// get points with the maximum projected value along axis.
// basically the vertex that's the farthest along the direction.
float max = getBoxMaxProjectedValue(axis);
static const float project_tolerance = 1.0E-4f;

// now list all the points that share that value.
for(int i = 0; i < 8; i ++)
{
float value = dotProduct(box.vertex(i), axis);

// that point is close to the extremum, record it.
if(value >= max - project_tolerance)
{
supports[supportsCount++] = box.vertex(i);
}
}

// we should get either, an edge, or a single vertex.
assert(supportsCount == 1 || supportsCount == 2);
}


ok, this is not the most efficient method, but basically, you try to get all the points that are the 'maximum' along the axis of interest (i.e. the collision normal, or it's opposite).

One box, you find the support feature along the normal of contact, the other box, you find the support feature along the opposite of the normal of contact.

Once you have the two supporting features, given the number of vertices returned (one two or four, other options should be invalid), you can decide to run one of the test above (edge-edge, point-face, face-face, ...).

for face face, and edge face cases, what you have to do to fing the points of contact, is to 'clip' one supporting feature with the other. That will give you all the supporting contact points.

Clipping is easy, it's similar to how you would go on about clipping convex polygons and edges in 2D, but you take 3D clipping planes that run on the edges of one polygon.

Share this post


Link to post
Share on other sites
ok, for the edge-edge collision case, it's quite easy. the two points of ocntact on edges are the points that are closest to each other. That sort of algorithm has been discussed many times :)

point face is even easier. One contact will be the vertex itself, the other will be the projection of that vertex onto the face.

I've explained face-face and edge-face already, but not in great details :) If you look at piecewise clipping, you should get an idea.

here's an example.

http://en.wikipedia.org/wiki/Sutherland-Hodgman_clipping_algorithm

the clipper has to be convex, but that's a given when doing the SAT algorithm (the faces are always convex).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!