Collision Detection. SAT implementation issue. Randy Gaul

Recommended Posts

Posted (edited)

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

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


  • Forum Statistics

    • Total Topics
      628667
    • Total Posts
      2984139
  • Similar Content

    • By GraphXGames
      Service Pack 1 include [ http://store.steampowered.com/app/718840/DiamondFalls/ ]:
      - Improved performance;
      - Fixed small bugs;

      WebSite: http://www.graphxgames.com/
      Twitter: https://twitter.com/GraphXGames
       
    • By Mevvay
      Hi guys! Our tight-knit AEL Entertainment team is going to release a new installment of popular saga Happy Empire - A Bouquet for the Princess.

      We have always enjoyed playing strategies but this time we’ve decided not to kick it off with long-running strategy games but with time-management games. Our game allows you to command workers and princes. Workers collect resources and repair bridges, roads and buildings. The main task for princes is to find flowers for a bouquet to win a princess`s heart.
      We took into account all the comments and recommendations from players concerning the first installment of Happy Empire saga; we improved CGI and added charismatic characters with a variety of dialogues. We did our best to fill characters` interactions with wit and humor and to build conversations the way you will never be bored.
      Our project Steam link: Happy Empire - A Bouquet for the Princess on Steam
      Trailer on Youtube: Happy Empire A Bouquet for the Princess Trailer (Youtube)
      All updates will be published in this thread. If you have any questions, comments or suggestions, please feel free to post them here or to send us e-mail happy@aelgames.com.

    • By lawnjelly
      It comes that time again when I try and get my PC build working on Android via Android Studio. All was going swimmingly, it ran in the emulator fine, but on my first actual test device (Google Nexus 7 2012 tablet (32 bit ARM Cortex-A9, ARM v7A architecture)) I was getting a 'SIGBUS illegal alignment' crash.
      My little research has indicated that while x86 is fine with loading 16 / 32 / 64 bit values from any byte address in memory, the earlier ARM chips may need data to be aligned to the data size. This isn't a massive problem, and I see the reason for it (probably faster, like SIMD aligned loads, and simpler for the CPU). I probably have quite a few of these, particular in my own byte packed file formats. I can adjust the exporter / formats so that they are using the required alignment.
      Just to confirm, if anyone knows this, is it all 16 / 32 / 64 bit accesses that need to be data size aligned on early android devices? Or e.g. just 64 bit size access? 
      And is there any easy way to get the compiler to spit out some kind of useful information as to the alignment of each member of a struct / class, so I can quickly pin down the culprits?
      The ARM docs (http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.faqs/ka15414.html) suggest another alternative is using a __packed qualifier. Anyone used this, is this practical?
    • By Josheir
      In the following code:

       
      Point p = a[1]; center of rotation for (int i = 0; I<4; i++) { int x = a[i].x - p.x; int y = a[i].y - p.y; a[i].x = y + p.x; a[i].y = - x + p.y; }  
      I am understanding that a 90 degree shift results in a change like:   
      xNew = -y
      yNew = x
       
      Could someone please explain how the two additions and subtractions of the p.x and p.y works?
       
      Thank you,
      Josheir
    • By dell96
      I'm trying to make my first project but I'm stuck i don't know how to make my crate to start to spawn again when i hit the start button after i die.
      hoping someone can help!!!
      Crate.cs
      CrateSpawn.cs
      Cratework.cs
      GameController.cs
      GameManager.cs
  • Popular Now