• Advertisement

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
  • Advertisement
  • Popular Tags

  • Advertisement
  • Popular Now

  • Similar Content

    • By LifeArtist
      Good Evening,
      I want to make a 2D game which involves displaying some debug information. Especially for collision, enemy sights and so on ...
      First of I was thinking about all those shapes which I need will need for debugging purposes: circles, rectangles, lines, polygons.
      I am really stucked right now because of the fundamental question:
      Where do I store my vertices positions for each line (object)? Currently I am not using a model matrix because I am using orthographic projection and set the final position within the VBO. That means that if I add a new line I would have to expand the "points" array and re-upload (recall glBufferData) it every time. The other method would be to use a model matrix and a fixed vbo for a line but it would be also messy to exactly create a line from (0,0) to (100,20) calculating the rotation and scale to make it fit.
      If I proceed with option 1 "updating the array each frame" I was thinking of having 4 draw calls every frame for the lines vao, polygons vao and so on. 
      In addition to that I am planning to use some sort of ECS based architecture. So the other question would be:
      Should I treat those debug objects as entities/components?
      For me it would make sense to treat them as entities but that's creates a new issue with the previous array approach because it would have for example a transform and render component. A special render component for debug objects (no texture etc) ... For me the transform component is also just a matrix but how would I then define a line?
      Treating them as components would'nt be a good idea in my eyes because then I would always need an entity. Well entity is just an id !? So maybe its a component?
      Regards,
      LifeArtist
    • By steve negrin
      hello, i'm steve and im designer, i can design any idea and i'm looking for projects to help, if you are interesting write and we can talk about it
    • By nickyc95
      Hi.
      I'm kind of late to this party but I thought I would ask anyway as I haven't found a concrete answer.
       
      When creating a game engine, when should you choose one methodology over another (more specifically OOP and DOD)? Which areas benefit from DOD? Which areas benefit from OOP? Do people typically mix multiple methodologies throughout a project? I.e. certain sub-systems created in one, and others in the another?  
      DOD - Data Oriented Design
      OOP - Object Oriented Design
       
      Pretty simple
      Thanks
  • Advertisement