Jump to content
  • Advertisement
Sign in to follow this  

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.

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

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));

    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));

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

Share this post

Link to post
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 smile.png

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 this post

Link to post
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

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!