# 3D SAT Problem

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

## Recommended Posts

Hello, newbie to SAT algorithm.

What am I missing in the SAT implementation below?

http://pastebin.com/CqNbB7ph

I think the problem is between the edge-edge case. Code doing all computations in world-space. Edited by Irlan Robson

##### Share on other sites

I wasn't finding a separating axis at all . Here's the solution:

if ( !TestFaces(_psiShape0, _psiShape1) ) {
return false;
}
if ( !TestFaces( _psiShape1, _psiShape0 ) ) {
return false;
}
if ( !TestEdges( _psiShape0, _psiShape1 ) ) {
return false;
}
return true;

Edited by Irlan

##### Share on other sites

You also want to check for parallel edges in the edge test. A random normal can generate a false separation or penetration.

E.g. you could use: |e1 x e2| = |e1| * |e2| * sin( alpha ) *and* sin( alpha ) ~= alpha for alpha << 1

##### Share on other sites

You also want to check for parallel edges in the edge test. A random normal can generate a false separation or penetration.

E.g. you could use: |e1 x e2| = |e1| * |e2| * sin( alpha ) *and* sin( alpha ) ~= alpha for alpha << 1

Thanks for pointing that out.

I'm skipping the edge-edge test if the cross product between them is small than 0.00001f.

Now (little off-topic), I'm facing with the problem of detecting the side planes of the reference face. The problem is that I'm not using an good structure (such the half-edge) to get the connected face planes.

The incident face is just the face of the second object that is most on the negative direction of the reference face right?

Do you have any recommendation?

Edited by Irlan

##### Share on other sites

I'm skipping the edge-edge test if the cross product between them is small than 0.00001f.

If you don't normalize the edge vectors you need to take their length into account. Otherwise this would just be an absolute tolerance. Here is a good discussion how to use relative and absolute tolerances together: http://realtimecollisiondetection.net/pubs/Tolerances/

Now (little off-topic), I'm facing with the problem of detecting the side planes of the reference face.

You don't clip against the neighboring planes. For every edge of the reference face you build a 'side' plane with the reference face normal. E.g. say you have a plane class which takes a normal and point on the plane:

// Build plane (v are the vertices and n is the normal of the reference face)

RnPlane ClipPlane( RnCross( v[ 2 ] - v[ 1 ], n ), v[ 1 ] );

ClipPlane.Normalize();

// Clip (e.g. using Sutherland-Hodgeman)

aPolyhedron.Clip( ClipPlane );

The incident face is just the face of the second object that is most on the negative direction of the reference face right?

Yes, essentially the most anti-parallel face! In practice just the face with the smallest (negative) dot product with the reference face normal.

Do you have any recommendation?

Did you see my presentations on the SAT? You can have a look at my 2013 and 2015 presentations here:

http://www.valvesoftware.com/company/publications.html

Edited by Dirk Gregorius

##### Share on other sites

Oh, I see. However, I'm confused about the vertices connections. For example, I've a working Sutherland-Hodgman clipping, but it assumes that the vertices are wind ordered in order to get correct edges connections (A to B, A to C, etc.). Another example is that if the edges are not correctly ordered, the side planes creation won't generate correct planes (which I've checked).

For testing purposes, I've manually created an OBB which the edges orders are CCW.  In the picture below, the edges are 0-3, 3-2, etc.

Nice GDC slides, BTW.

Edited by Irlan Robson

##### Share on other sites

You mean A to B, B to C, C to D and then X to A I assume. Yes, that is correct, but all you need is an integer array for the edges and then store an offset into that array per face. At the first index you store the number of vertices for that face and the following entries contain the vertex indices for that face. In your example above the top face followed by the front face would be indexed like this { 4, 1, 2, 6, 5, 4, 0, 3, 2, 1, ... }

Then in code you have an array of face planes and a parallel array of offsets into the topology list. In code then this could look something like this:

for ( all faces i )
{
int offset = mTopologyOffsets[ i ];

int vertexCount = mFaceTopology[ offset ];
for ( all vertices k = 1 as long as k <= vertexCount )
{
int vertexIndex = mFaces[ offset + k ]
Vector3 vertex = mFaceTopology[ vertexIndex ];
}

} 

This is easy and can get you going for a simple box and convex polyhedra.

Edited by Dirk Gregorius

##### Share on other sites
Oh. Thanks!

I'll try it. Edited by Irlan Robson

##### Share on other sites
Do you compute all edges during pre-processing step or compute its normals on the fly? I still think I'll need to implement QuickHull and half-edges since it's the most viable structure to acess adjacency information. Edited by Irlan Robson

##### Share on other sites

- You compute the vertices, local face planes and topology during pre-processing. You then compute the edge cross products at runtime.

- Edges are just indices into the vertex array.

HTH, I am not sure if I understand what the question is.

Quickhull and HE are indeed a very good solution for this problem. But the one I showed here is fine as well and easy to construct for e.g. boxes. The half-edge structure becomes really useful if you start pruning edge pairs that don't build a Minkowski face. But this is an optimization and I would handle this at the end when everything is working correctly.

• 11
• 9
• 9
• 10
• 24