• 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