Seperating Axis Theorem - How to Resolve Contact Points

The separating axis that realizes the axis of minimum penetration is either a face normal or the cross product between two edges. In the first case let's call this face the "Reference Face". Now you find the most parallel face on the other shape which we call the "Incident Face". To find the contact points you clip the incident face against the side planes of the reference face and keep all points below the reference face plane.

In the case where the separating axis is the cross product between two edge directions you can keep the closest points of on the edges. Note that several edge cross products can realize thhe same axis of minimum penetration. You have to make sure that the edges are actually the "Support Edges" (similar to the concept of a support point) in the direction of your separating axis. This means geometrically that the edges are actually "close" to each other. Or from a Minkowski viewpoint this means that the edges actually build a face on the Minkowski sum.

You can look at ODE dBoxBox for an example.

Quote:

Original post by DonDickieD The separating axis that realizes the axis of minimum penetration is either a face normal or the cross product between two edges. In the first case let's call this face the "Reference Face". Now you find the most parallel face on the other shape which we call the "Incident Face". To find the contact points you clip the incident face against the side planes of the reference face and keep all points below the reference face plane. In the case where the separating axis is the cross product between two edge directions you can keep the closest points of on the edges. Note that several edge cross products can realize thhe same axis of minimum penetration. You have to make sure that the edges are actually the "Support Edges" (similar to the concept of a support point) in the direction of your separating axis. This means geometrically that the edges are actually "close" to each other. Or from a Minkowski viewpoint this means that the edges actually build a face on the Minkowski sum. You can look at ODE dBoxBox for an example.

DonDickieD, thanks so much for the help.

I am attempting to implement 3D collision detection using Oriented Bounding Boxes (OBB), deriving a contact manifold using the SAT.
If I understand, it involves identifying the "features" of the two objects (boxes in this case) that project minimally, onto the axis that is determined to be the axis that is parallel to the minimum translational vector (MTD). Once I've identified these features, I can clip them against one another to yield the contact manifold.

Now, what SAT will give me, will be the normal of the collision and the depth of intersection, both combined can they compute the minimum translation distance (MTD), how?

I think the support points/edges are basically the points on the objects that provide a stable base along the normal of collision. So, instead of talking about support points, is it better to consider them as supporting "feature"? If I understand, in my case these features can be either, a point, an edge and a polygon.
How can the normal of collision be used to find the features on the two surface?

If I consider two boxes (box A sitting on box B), one sitting on top of the other, you will get 4 support points a piece (one polygon each). The bottom face of box A, and the top face of box B. To find the contact points, will I need MTD to 'clip' one polygon against another, how?

Also, how can I know that the feature are actually the "Support feature" in the direction of my separating axis, when several edge cross products can realize the same axis of minimum penetration?
Can I combine SAT and GJK, with the latter only used to find the contact points?

In addition, but no less important, I will test my intersection algorithm using boxes of various dimensions and orientations intersecting in various configurations, but for the collision response, I have to apply an impulse always to the box A. So, I make sure that the penetration direction and length refer always in the right way, relatively to the box A (outward box B)... But I'm still confused about it.

I would appreciate any assistance, Thank you!

These are very general questions. Please read Erin Catto's 2007 GDC presentation on contact manifolds which you can download here:

http://code.google.com/p/box2d/downloads/list.

It is the second PPT. Also Download the 2009 GDC presentation and look at the Box2D Lite implementation. Then extend this to 3D and add the edge cases yourself - maybe looking into dBoxBox from the ODE.

The idea to extend to a support feature is correct. You can indeed have a support point, edge or face. Identifying support edges is crucial for general convex collision using SAT. As it turns out the associated arcs on the Gauss-Map must intersect. This is maybe non-trivial to understand so let me quickly try to give you the basic idea. Basically an edge has two adjacent faces. These faces have normals which you can interpret as points on a unit sphere. This is called the Gauss-Map. Now you test whether the two arcs intersect. If and only if these arcs intersect the edges are support edges and can actually realize a contact. I am editor of a book called "Game Physic Pearls" which has a nice article about Gauss-Maps.

For clipping you basically clip a polygon against several planes. Christer Ericson's "Real-Time Collision Detection" has some nice code and article how to do this.

If you want to write your own physic engine I absolutely recommend looking into Box2D lite and port it through 3D making sure you understand every detail. The basic engine can have a brute force broadphase and should support spheres, capsules and boxes as shapes. A simple spherical joint is sufficient initially. Finally implement an impulse solver. From there you can dive into all other topics you want, but now having some idea how things work.

HTH,
-Dirk