Trying to implement Gino's GJK-based ray-cast

Please don't post Bullet support questions here, use the above forums instead.
Post Reply
concubicycle
Posts: 3
Joined: Wed Apr 04, 2012 5:40 pm

Trying to implement Gino's GJK-based ray-cast

Post by concubicycle »

Hi! Sorry if this has been posted before (tried a few searches), but I need help implementing Gino Van Bergen's "Ray Casting against General Convex Objects with Application to Continuous Collision Detection". I've read through the paper, and tried to take everything in to the best of my ability, but I'm still new to game physics and I'd like to get much better at it. I also went through some Bullet code, but I found a lot of it somewhat difficult to understand.

I'm trying to implement this approach in C# for a 2D xna game. It currently works about 3/4 of the time. I was wondering if anyone would be kind enough to tell me if I'm on the right track, and to point me to helpful resources that would help me master (to a reasonable extent) collision detection.

Here is the method. I'm not sure that all the methods I've used are working completely, but I assume for now that they are. The objects are in world space.

Code: Select all

public bool generalGJK(BoundingVolume objA, BoundingVolume objB, Vector2 velA, Vector2 velB, out GJKOutputForm form)
        {
            maxIter = 1000;
            Vector2 r = velB - velA; //r - this is my assumption based on obseving behavior of minkowski difference

            //This is not an intersection test, for now. We can run an axis of separation if vel = 0 HERE later.
            if (r.Length() == 0)
            {
                form.TOI = 2;
                form.collisionNormal = Vector2.Zero;
                return false;
            }
            
            float hitParam = 0; //lambda
            Vector2 s = Vector2.Zero; //s, which is the origin I think...
            Vector2 hitSpot = s; //x
            Vector2 normal = Vector2.Zero; //n
            Vector2 nOriginToHitSpot; //w 
            VoronoiSimplex simplex = new VoronoiSimplex(); //P
            Vector2 convergingNormal; //V
            Vector2 tempMinkVert;

            float epsilon = float.Epsilon;
            //epsilon *= epsilon;

            GeometryUtilities.minkDiffSupportMap(objA, objB, Vector2.One, out tempMinkVert); //get arbitrary point in C (which I assume is the
                                                                                             //minkowski difference).
            convergingNormal = hitSpot - tempMinkVert; //v = x − "arbitrary point in C"

            while (Vector2.Dot(convergingNormal, convergingNormal) > epsilon && (maxIter--) > 0)
            {
                GeometryUtilities.minkDiffSupportMap(objA, objB, convergingNormal, out tempMinkVert); // p <- Sc(v). v is a normal of C at p
                nOriginToHitSpot = hitSpot - tempMinkVert;

                float VdotW = Vector2.Dot(nOriginToHitSpot, convergingNormal);

                if (hitParam > 1.0f)
                {
                    form.TOI = 2;
                    form.collisionNormal = Vector2.Zero;
                    return false;
                }

                if (VdotW > 0)
                {
                    float VdotR = Vector2.Dot(r, convergingNormal);

                    if (VdotR >= -1.0f*epsilon)
                    {
                        form.TOI = 2;
                        form.collisionNormal = Vector2.Zero;
                        return false;
                    }
                    else
                    {
                        hitParam = hitParam - VdotW / VdotR;
                        hitSpot = s+hitSpot+hitParam * r;
                        normal = convergingNormal;
                    }
                }
                simplex.addVertex(new Vector3(tempMinkVert.X, tempMinkVert.Y, 0.0f));
                simplex.resetUsedVerts();
                //simplex.deformAccordingToHitParam(new Vector3(hitSpot.X, hitSpot.Y, 0.0f));
                simplex.findClosestPointOnSimplexTo(Vector3.Zero);
                convergingNormal.X = simplex.PointOfMinNorm.X;
                convergingNormal.Y = simplex.PointOfMinNorm.Y;
                simplex.reduceSimplex();
            }

            float time = hitParam;
            if (time > 1)
            {
                form.TOI = 2;
                form.collisionNormal = Vector2.Zero;
                return false;
            }
            else
            {
                form.TOI = time;
                form.collisionNormal = normal;
                return true;
            }
        }
Thanks,
concubicycle
Post Reply