# Seperating Axis Theorem assistance

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

## Recommended Posts

So my results after implementing SAT seem wonky at best. I am only using 8 vertex bounding boxes to test it until I can get it running smoothly. I have problems with tunneling(unrelated to time step), shooting my object through another when aproached from a specific side. Any thoughts?

Thank you in advance.

Here I create my axes to test against a body and a neighboring body

LWXList<LWXVector3> axes;

LWXList<LWXVector3> bodyPrimitives = body->GetTransformedBoundingVectors();
LWXList<LWXVector3> neighborPrimitives = neighbor->GetTransformedBoundingVectors();

LWXVector3 axis;

//body faces
axis = LWXCrossProduct(bodyPrimitives[1] - bodyPrimitives[0], bodyPrimitives[2] - bodyPrimitives[0]); axes.Push(LWXNormalize(axis));
axis = LWXCrossProduct(bodyPrimitives[2] - bodyPrimitives[1], bodyPrimitives[6] - bodyPrimitives[1]); axes.Push(LWXNormalize(axis));
axis = LWXCrossProduct(bodyPrimitives[1] - bodyPrimitives[0], bodyPrimitives[5] - bodyPrimitives[0]); axes.Push(LWXNormalize(axis));

//neighbor faces
axis = LWXCrossProduct(neighborPrimitives[1] - neighborPrimitives[0], neighborPrimitives[2] - neighborPrimitives[0]); axes.Push(LWXNormalize(axis));
axis = LWXCrossProduct(neighborPrimitives[2] - neighborPrimitives[1], neighborPrimitives[6] - neighborPrimitives[1]); axes.Push(LWXNormalize(axis));
axis = LWXCrossProduct(neighborPrimitives[1] - neighborPrimitives[0], neighborPrimitives[5] - neighborPrimitives[0]); axes.Push(LWXNormalize(axis));

//Edges
axis = LWXCrossProduct(bodyPrimitives[0] - bodyPrimitives[1], neighborPrimitives[1] - neighborPrimitives[0]); axes.Push(LWXNormalize(axis));
axis = LWXCrossProduct(bodyPrimitives[0] - bodyPrimitives[1], neighborPrimitives[5] - neighborPrimitives[1]); axes.Push(LWXNormalize(axis));
axis = LWXCrossProduct(bodyPrimitives[0] - bodyPrimitives[1], neighborPrimitives[1] - neighborPrimitives[2]); axes.Push(LWXNormalize(axis));

axis = LWXCrossProduct(bodyPrimitives[1] - bodyPrimitives[2], neighborPrimitives[1] - neighborPrimitives[0]); axes.Push(LWXNormalize(axis));
axis = LWXCrossProduct(bodyPrimitives[1] - bodyPrimitives[2], neighborPrimitives[5] - neighborPrimitives[1]); axes.Push(LWXNormalize(axis));
axis = LWXCrossProduct(bodyPrimitives[1] - bodyPrimitives[2], neighborPrimitives[1] - neighborPrimitives[2]); axes.Push(LWXNormalize(axis));

axis = LWXCrossProduct(bodyPrimitives[5] - bodyPrimitives[1], neighborPrimitives[1] - neighborPrimitives[0]); axes.Push(LWXNormalize(axis));
axis = LWXCrossProduct(bodyPrimitives[5] - bodyPrimitives[1], neighborPrimitives[5] - neighborPrimitives[1]); axes.Push(LWXNormalize(axis));
axis = LWXCrossProduct(bodyPrimitives[5] - bodyPrimitives[1], neighborPrimitives[1] - neighborPrimitives[2]); axes.Push(LWXNormalize(axis));

return axes;

Here is my overlap check

_OverlapResults results;
results.axis = axis;

//First body min/max
float bodyMin = LWXDotProduct(bodyVertices[0], axis);
float bodyMax = bodyMin;
for(int i = 1; i < bodyVertices.Size(); i++)
{
float projection = LWXDotProduct(bodyVertices[i], axis);
if(projection < bodyMin)
{
bodyMin = projection;
}
else if(projection > bodyMax)
{
bodyMax = projection;
}
}

//Second body min/max
float neighborMin = LWXDotProduct(neighborVertices[0], axis);
float neighborMax = neighborMin;
for(int i = 1; i < neighborVertices.Size(); i++)
{
float projection = LWXDotProduct(neighborVertices[i], axis);
if(projection <= neighborMin)
{
neighborMin = projection;
}
else if(projection >= neighborMax)
{
neighborMax = projection;
}
}

//Check if overlaping projected vertices
if(!LWXBoundry(neighborMin, neighborMax, bodyMin) && !LWXBoundry(neighborMin, neighborMax, bodyMax)
&& !LWXBoundry(bodyMin, bodyMax, neighborMin) && !LWXBoundry(bodyMin, bodyMax, neighborMax))
{
//Projections do not overlap
results.overlap = false;
return results;
}

//An overlap has occured, find how much of an overlap exist
results.overlap = true;

//Check if one set completely encloses the other
if(LWXBoundry(neighborMin, neighborMax, bodyMin) && LWXBoundry(neighborMin, neighborMax, bodyMax))
{
results.overlapDistance = abs(bodyMax - bodyMin);
}
else if(LWXBoundry(bodyMin, bodyMax, neighborMin) && LWXBoundry(bodyMin, bodyMax, neighborMax))
{
results.overlapDistance = abs(neighborMax - neighborMin);
}
//Check stagger distance
else if(LWXBoundry(neighborMin, neighborMax, bodyMin))
{
results.overlapDistance = abs(neighborMax - bodyMin);
}
else if(LWXBoundry(neighborMin, neighborMax, bodyMax))
{
results.overlapDistance = abs(bodyMax - neighborMin);
}

//Projections overlap
return results;

And as long as all the axes overlap, I update my bodies position via:

//If function has reached this point a collision has occured
LWXVector3* bodyPos = body->GetUpdatePosition();
LWXVector3 bodyDir = body->GetDirection();

//TODO I beleive jumping glitch is caused because my overlapDistance is only for a 2d space. Need to know how much they overlap and on which axis...
//Projet the body out of the neighbor
bodyPos->x += bodyDir.x > 0.0f ? shortestCollisionResults.axis.x * shortestCollisionResults.overlapDistance
: -shortestCollisionResults.axis.x * shortestCollisionResults.overlapDistance;
bodyPos->y += bodyDir.y > 0.0f ? shortestCollisionResults.axis.y * shortestCollisionResults.overlapDistance
: -shortestCollisionResults.axis.y * shortestCollisionResults.overlapDistance;
bodyPos->z += bodyDir.z > 0.0f ? shortestCollisionResults.axis.z * shortestCollisionResults.overlapDistance
: -shortestCollisionResults.axis.z * shortestCollisionResults.overlapDistance;

//If the body's shortest y axis is negative, it has landed on top of the neighbor. Mark the body as grounded
shortestCollisionResults.axis.y < 0.0f ? body->_grounded = true : body->_grounded = false;

//Apply appropriate forces to body and neighbor
LWXVector3 bodyForce = LWXVector3((body->p_physicsProperties.mass * body->_acceleration.x),
(body->p_physicsProperties.mass * body->_acceleration.y),
(body->p_physicsProperties.mass * body->_acceleration.z));

neighbor->ApplyForce(bodyForce);
body->ApplyForce(LWXVector3(-bodyForce.x, -bodyForce.y, -bodyForce.z));



##### Share on other sites

Hi there, we get this kind of question a lot, and people usually solve their problems by:

• Debug rendering of shapes, collision points, collision normals
• Explaining the algorithm in english so others can debug-at-a-glance. It would be helpful to tell us a little more about your specific approach
• Debug rendering even more things
• Finally, debug rendering some more

If you want to compare your implementation against another 8 point OBB implementation you can check out this open source lib here. Judging by your quick description of having problems shooting at a specific side, you probably have some incorrect math somewhere (unless by tunneling you just meant objects are going too fast and pass through each other, in which case you need a new algorithm to handle this for you outside of conventional SAT). Usually this kind of problem is fixed through the steps I mentioned above, and through referencing working source code.

Edited by Randy Gaul

##### Share on other sites

Why do you need the vertices to build the separating axes? Given two shapes each has a current orientation matrix R = ( u, v, w ). Here u, v, and w are column vectors defining the current coordinate frame. Then for each body simply test each axis u, v, and w. This defines the six face directions. Then test the nine unique pair-wise cross products, e.g. axis = cross( u1, v2 ). This would define the nine edge cases.

I recommend Christer Ericson's and Gino v.d. Bergen's books if you want to learn these things!

Edited by Dirk Gregorius

1. 1
2. 2
Rutin
21
3. 3
A4L
15
4. 4
5. 5

• 13
• 26
• 10
• 11
• 44
• ### Forum Statistics

• Total Topics
633740
• Total Posts
3013621
×