Jump to content

  • Log In with Google      Sign In   
  • Create Account

Awesome job so far everyone! Please give us your feedback on how our article efforts are going. We still need more finished articles for our May contest theme: Remake the Classics

GrayScale

Member Since 23 Nov 2007
Online Last Active Today, 01:02 AM
-----

Topics I've Started

Need help solving GJK woes

17 March 2013 - 03:51 PM

Good afternoon people of Game Dev.
 
        For the past several days now I have been trying to implement the GJK algorithm for my 2D game with no avail. I fully understand the concept behind the algorithm and theoretically implementing it. But I believe my problems lie elsewhere: lacking knowledge and experience with vectors(resulting in bad calculation), Win32 API(Inverted coordinate), multiple resources whose implementation of the algorithm greatly varies, etc.
 
        Nevertheless, I'd appreciate it if someone could look at my code and tell me what I'm doing wrong. I believe the problem lies with me failing to  find the correct perpendicular vectors of an edge. I've tried various methods of calculations: perpAB = ABxACxAC, ABxAOxAB. and the last method, posted in the code below, with no conclusive result. I've tried just using the normal/perpendicular, being that for now I'm attempt to implement it in 2D.
 
The brunt of the Code:
       

bool                SMYGJK::gjk_work( SmyPoint & D, SmyPoint simplex[], int & count )
{        
    SmyPoint a        = simplex[count-1];            // point a, the newest point added to the simplex
    SmyPoint b        = simplex[0];                // point b
    SmyPoint origin    = -a;                        // ao(direction towards origin) = origin(0,0) - a which equals -a
    SmyPoint ab        = b - a;                    // edge ab( vector between a and b )

    if( count == 2 )// simplex-1( line )
    {
        SmyPoint abp    = ab.normal();

        // Find ab perp in direction of the origin
        if( abp.dot( origin ) < 0 )
            abp.negate();

        D    = abp;                        // change the direction to where a new point should be located
    }
    else
    if( count == 3 )//simplex-2(triangle)
    {
        SmyPoint c        = simplex[1];
        SmyPoint ac        = c - a;
        SmyPoint abp    = ab.normal();    // possible new search direction if collision not found

        if( abp.dot( c ) >= 0 )            // Check other side if facing wrong way
            abp.negate();

        if( abp.dot( origin ) > 0 )
        {
            // remove c
            count--;
            simplex[0]    = b;
            simplex[1]    = a;
            D            = abp;            // change the direction to where a new point should be located
        }
        else
        {
            // check direction ac perp
            SmyPoint acp    = ac.normal();

            if( acp.dot( b ) >= 0 )        // Check other side if facing wrong way
                acp.negate();
            
            if( acp.dot( origin ) <= 0 )// collision detected because not in region acperp nor abperp, thus, origin is enclosed
                return true;

            // remove b
            count--;
            simplex[0]    = c;
            simplex[1]    = a;
            D            = acp;            // Face direction perpendicular to edge ac
        }
    }

    // keep building
    return false;
}

 

Help is much appreciated. If you'd like to see the support function or function that contains the loop of the algorithm let me know.


PARTNERS