Jump to content

  • Log In with Google      Sign In   
  • Create Account


#ActualGrayScale

Posted 15 April 2013 - 04:46 AM

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.


#1GrayScale

Posted 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        gjkwork( 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;                           // origin(direction towards origin) = origin(0,0) - a which equals -a
        SmyPoint ab        = b - a;                       // edge ab

        if( count == 2 )// simplex-1( line )
        {
            SmyPoint perpAB    = ab.normal();// perpendicular vector to check edge ab in direction of the origin

            if( perpAB.dot(origin) > 0 )// check the edge pointing toward the origin
                D = perpAB;
            else
            {
                // remove b, point a is closest to the origin
                count          = 1;
                simplex[0]   = a;
                D                = origin;
            }
        }
        else
        if( count == 3 )//simplex-2(triangle)
        {
            SmyPoint c              = simplex[1];
            SmyPoint ac            = c - a;
            SmyPoint perpAB    = ab.normal();
            SmyPoint perpAC    = ac.normal();

            if( perpAB.dot(origin) > 0 )// check edge AB
            {
                // remove point c, edge ab is closest to the origin
                count           = 2;
                simplex[0]    = b;
                simplex[1]    = a;
                D                 = perpAB;
            }
            else
            if( perpAC.dot(origin) > 0 )// check edge AC
            {
                // remove point b, edge ac is closest to the origin
                count           = 2;
                simplex[0]    = c;
                simplex[1]    = a;
                D                 = perpAC;
            }
            else
            {
                // outside of edges AB & AC are not closest to origin, thus, the origin must be enclosed
                return true;
            }
        }

        // 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