9 replies to this topic

[GrayScale]

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.

[GrayScale]

Does anyone know if the coordinate system effects the outcome of GJK algorithm?  Being that the win32 GDI api origin is(0,0), topleft, It turns out that one of the bugs in my code was that the initial y-component of the direction vector has to be negative( or inverted I assume ), otherwise it does not work. It is my understanding that I should be able to use an abitrary direction, right? If so, why am I limited to a negative y-component?

 

 

Here's the code of main gjk loop:

 

bool        gjktest( SmyPoint polygon01[], int size01, SmyPoint polygon02[], int size02 )
    {
        SmyPoint simplex[4];

        // start direction
        SmyPoint direction( 0, -1, 0 ); // NOTE: due to win32 coordinate system, the y-component of the direction vector should be negative to invert.

        // get farthest point in both vectors
        SmyPoint p1    = this->gjksupport(  direction, polygon01, size01 );
        SmyPoint p2    = this->gjksupport( -direction, polygon02, size02 );

        // add start vector to simplex
        int count            = 0;
        simplex[count++]    =  p1 - p2;
        
        // reverse the search direction
        direction.negate();    
        
        // start iteration
        int expire = 0;
        do
        {
            // calculate minkowski difference to produce a point inside minkowski space
            p1    = this->gjksupport( direction, polygon01, size01);
            p2    = this->gjksupport(-direction, polygon02, size02);
            
            SmyPoint p3    = p1 - p2;
            
            // no intersection. the origin cannot be enveloped because the furthest point does not cross the origin.
            if( p3.dot(direction) < 0 )
                return false;
            
            // add point to simplex
            simplex[count++]    = p3;

            // check simplex for intersection
            if( this->gjkwork( direction, simplex, count ) )
                return true;
        }
        while(++expire < 100);

        return false;
  

[Inferiarum]

There is an error in your 2 point simplex case.

You have to check AB, not perpAB.

perpAB is just needed for the new search direction if dot(AB,origin)

[GrayScale]

There is an error in your 2 point simplex case.

You have to check AB, not perpAB.

perpAB is just needed for the new search direction if dot(AB,origin)

I have made modifications since my last question, and have edited the first post, to updated code. Nevertheless, I don't see how or why I should check edge AB? all the tutorials that I have read checks for perpAB, and as far as it(edge perpAB) being the new search direction, I can agree with what you've said. However, will this fix the  "direction" bug that I am having? With an exception to that It works fine, so long as the y-direction is negative...?

[Inferiarum]

Did you check out this video:

 

http://mollyrocket.com/849

 

I did an gjk implementation based on the explanation there. In 2D it should be pretty straightforward.

[GrayScale]

Did you check out this video:

 

http://mollyrocket.com/849

Yup, its a very good video, I watched it more than once. Actually, my original code was based off of it, but after failing miserably to implement it, I simplified it to the 2D code above. I plan on expanding it to 3D once I've ironed out the wrinkles in my current code.

 

My code is based off this guys:  http://blog.zylinski.se/?p=251.

 

And as you can see in his code, he starts with an arbitrary direction and his works fine. ATM, I'm working on my 2D platform game. So eventually I'll get around to setting up a DirectX project to see if my assumption that WIN32 API coordinate system is indeed the problem...

[Inferiarum]

Ok, I checked out the 2D gjk explanation. And while I think it is not optimal it should still yield the correct result.

The direction of the y axis should not matter in your implementation, since you check the direction of the normal vectors anyway.

You do not mention how you actually calculate the normal vectors. If you have x=[x1, x2] the normal could be calculated as nx=[x2, -x1].

[GrayScale]

You do not mention how you actually calculate the normal vectors. If you have x=[x1, x2] the normal could be calculated as nx=[x2, -x1].

 

Wow! awesome, I thank you. Weeks of frustration summed up by something so trivial... a single minus sign. Does this have to do with the whole left-handedness and right-handedness thing?

This is how I calculated the normal before:

SMYUTI_Vector    normal()
{
        return SMYUTI_Vector( -this->y, this->x, this->z );
}

Then I swapped the minus sign just as you suggested and voila, no bugs.

Care to explain why this is? I read in the book, Mathematics and Physics for Game Programming that it does not matter in which component you place the minus sign when calculating the normal, clearly it does. Also what optimizations can be made? I thought the optimization was check outside of edge AB and edge AC, and/or vertex A, If not there then the origin is enclosed. Is it that both sides of each of the edges are being checked? If so, I figured it was for orientation, so that you know which direction you're facing. Nevertheless, Thanks Again for the help.
 

[Inferiarum]

In your implementation it should actually not make a difference where you place the minus sign. You do an extra check after calculating the normals and after the check the vector should always point in the same direction, no matter where you put the minus sign initially. Maybe there is something wrong with the negate method?

 

I think if you base your implementation on the video it should be faster in general. But if your current implementation is working I it would only be worth the effort if you identify the gjk algorithm as a bottleneck in your game.

[GrayScale]

Yup, you're right about the minus sign, though. Anyhow, the code works fine now and all the bugs are gone. I will work on the optimization on a later date. Thanks for the help.