Jump to content
  • Advertisement
Franco Gentili

Collision Detection. SAT implementation issue. Randy Gaul

Recommended Posts

I'm trying to implement OBB vs OBB SAT collision from Randy Gaul's article.

I have been playing with it for days, but I can't figure it out why it doesn't work.

I am storing all vertex positions of each box, and also each edge normal on two lists. Then I use them on the algorithm, I tried a lot of changes to make it work but no luck.

This is my C++ code:

QVector2D Entity::getSupport(QVector2D dir)
{
    float bestProjection = -std::numeric_limits<float>::max();

    QVector2D bestVertex;

    for(quint32 i = 0; i < verticesList.count(); ++i)
    {
        QVector2D v = verticesList.at(i);

        float projection = QVector2D::dotProduct(v,dir);

        if(projection > bestProjection)
        {
            bestVertex = v;
            bestProjection = projection;
        }
    }

    return bestVertex;
}

qreal Collision::FindAxisLeastPenetration(Entity *A, Entity *B )
{
    float bestDistance = -std::numeric_limits<float>::max();

    for(quint32 k = 0; k < A->verticesList.count() ; ++k)
    {
        QVector2D n = A->normalList.at(k);  
        QVector2D s = B->getSupport(-n);          
        QVector2D v = A->verticesList.at(k);          
        QVector2D r = s-v;   
        qreal d = QVector2D::dotProduct(n,r);

        if(d > bestDistance)
        {
            bestDistance = d;
        }
    }
      return bestDistance;
}

if (coli->FindAxisLeastPenetration(player,player2) <0 && FindAxisLeastPenetration(player2,player) <0 )
{
   qDebug() << "Collision detected ";
}

 

Edited by Franco Gentili

Share this post


Link to post
Share on other sites
Advertisement

I don't have time to look too carefully at your code, but since you want to do OBB against OBB there is a good implementation by Erin Catto here for 2D: http://box2d.org/files/GDC2006/Box2D_Lite.zip

Another great resource for this code is Dirk's 2013 GDC lecture. His lecture is where I really learned the most about implementing a separating axis test. This thread has some good links: http://bulletphysics.org/Bullet/phpBB3/viewtopic.php?f=4&t=9109

Share this post


Link to post
Share on other sites

I think you are missing the transforms. Speculating about what your code does it should more look like this.

qreal Collision::FindAxisLeastPenetration(Entity *A, Entity *B )
{
    float bestDistance = -std::numeric_limits<float>::max();

    for(quint32 k = 0; k < A->verticesList.count() ; ++k)
    {
        QVector2D n = A->transformVectorToWorld( A->normalList.at(k) );  
        QVector2D s = B->getSupport(-n);          
        QVector2D v = A->transformPointToWorld( A->verticesList.at(k) );          
        QVector2D r = s-v;   
        qreal d = QVector2D::dotProduct(n,r);

        if(d > bestDistance)
        {
            bestDistance = d;
        }
    }
      return bestDistance;
}

 

Same for the support function:

 

QVector2D Entity::getSupport(QVector2D worldDir)
{
    QVector2D dir = transformVectorToLocal( worldDir );
    
    float bestProjection = -std::numeric_limits<float>::max();
    QVector2D bestVertex;

    for(quint32 i = 0; i < verticesList.count(); ++i)
    {
        QVector2D v = verticesList.at(i);
        float projection = QVector2D::dotProduct(v,dir);

        if(projection > bestProjection)
        {
            bestVertex = v;
            bestProjection = projection;
        }
    }

    return transformPointToWorld(bestVertex);
}

The other thing to watch out for is that the vertex you grab is on the actual plane of the edge. I assume you have ordered your normals and vertices accordingly, but I would double check. 

Edited by DonDickieD

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • 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!