# GJK Raycast

This topic is 2894 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I read Gino's paper Here on general convex raycasting. I tried to just get a feel for what we was doing and implement it myself.

The way i see it, one finds the closest feature to a minimum ray bound, clips the ray with the result, and continues searching until the minimum bound:
* goes beyond the ray
* passes the convex shape
* gets within a tolerance to the shape

For the most part my implementation works.

In one test case, i have two lumpy convex hulls (rocks) overlapping each other and i cast a ray straight down into the intersection region.
Depending on the result, i move the ray up and down to be a fixed distance away from the intersection pt. (Basic raycast character behavior)

What i'm seeing is that the intersection results differ depending on the starting height of the ray. In one frame it will find rock A and move the ray up.
Then it misses rock A and finds rock B and moves the ray down. This oscillates back and forth every frame.

I suspect that the order of terminations conditions or another simple mistake was made. Any suggestions?

 void tGJKRaycast::fCompute( ) { const f32 cTolerance = 0.001f; const f32 cToleranceSqr = cTolerance * cTolerance; tVec3f lastNormal = tVec3f::cYAxis; b32 hasStepped = false; mIntersects = false; mT = 0.f; mRaySupport->mCenter = mRay.fEvaluate( mT ); mGJK.fReset( ); while( 1 ) { mGJK.fResume( ); mGJK.fCompute( ); if( !hasStepped && mGJK.fIntersects( ) ) { // origin is contained // miss return; } // points from shape to ray. tVec3f diff = mRaySupport->mCenter - mGJK.fClosestPtA( ); if( diff.fLengthSquared( ) < cToleranceSqr ) { mIntersects = true; mNormal = lastNormal; mPoint = mGJK.fClosestPtA( ); mT = fClipRay( mRay, lastNormal, mGJK.fClosestPtA( ) ); return; } if( diff.fDot( mRay.mExtent ) >= -cEpsilon ) { //clip plane and ray are either coplanar or facing the same direction. // miss. return; } hasStepped = true; lastNormal = diff; lastNormal.fNormalize( ); // plane on convex shape. mT = fClipRay( mRay, lastNormal, mGJK.fClosestPtA( ) ); if( mT > 1.f ) { // beyond ray length. // miss return; } mRaySupport->mCenter = mRay.fEvaluate( mT ); } } 

My tolerance is 0.001f but any smaller number exhibits the same behavior.
mRaySupport is just a point support mapping, containing the location of the current minimum bound location.

##### Share on other sites
I'm not totally sure what's going on when you say: "[color=#1C2837][size=2]In one frame it will find rock A and move the ray up. [color=#1C2837][size=2]

Then it misses rock A and finds rock B and moves the ray down"...

[color=#1C2837][size=2]

[color=#1C2837][size=2]

Obviously this is ray-cast against the MD of the two shapes, not the individual convex objects.

[color=#1C2837][size=2]

[color=#1C2837][size=2]

I recommend taking GJK out of the equation (as a test) and just substitute a function which gives you the closest point and the normal at that point to a simple shape, like a sphere and then try using this function to ray-cast against the sphere.

[color=#1C2837][size=2]

[color=#1C2837][size=2]

That will rule out the GJK part

[color=#1C2837][size=2]

[color=#1C2837][size=2]

Cheers, Paul.

##### Share on other sites

[color="#1C2837"]

Obviously this is ray-cast against the MD of the two shapes, not the individual convex objects.

Sorry for not being more clear. Here is an illustration: http://i42.tinypic.com/2zywsvb.png

This is actually just a 3d ray cast, and not a continuous collision test. There are just two ray casts happening during the test, one against each rock, and the lowest "t" value is chosen as the result.

Referencing the illustration, in setup 1, rock A is found as the best result, and the ray is moved up some (Character is now standing on rock A).
The next frame (setup 2), rock B is found as the best result, and the ray is moved back down. This cycle repeats.

Obviously the ray is dangerously close to the edge of rock A which is what leads me to believe it's an erroneous termination condition. (also, the underlying gjk has been thoroughly abused and hasn't shown any signs of failure)

While constructing the picture above i did come up with a hypothesis.
In this image: http://i43.tinypic.com/14l4zls.png

If vertex "a" was chosen as the closest feature (indicating an error in the underlying gjk), and the ray clipped against the blue plane, this would totally ruin the test. When i get near the code again i'll debug for the clip planes used.

I was hoping to just get another pair of eyes on my terminations conditions and see if they seem logical.

##### Share on other sites
How close is the ray from A? Is it within some tiny numerical tolerance?

Can you draw the iterations of the algorithm as it progresses?

One thing I'm thinking - in the first diagram, the ray start point will project onto the plane of the edge of A which is facing it. In the second diagram its not clear whether the same thing happens, or whether the vertex is the closest feature and therefore, the normal returned will be different?

Cheers, Paul.

##### Share on other sites
After a lot of debugging, the problem thus far has been two-fold.

One of my gjk termination conditions is that the closest pt to the origin, get closer by some tolerance with each iteration.
This caused issues when geometry was nearly coplanar. The simplex would end on a large inner triangle, when there was one more vertex closer on the shape surface.

Second was the mGJK.fResume( ) line in the above code. This attempts to restart the simplex with the old vertices in their new location.
In theory this should work but in my experience (specifically with raycast) it did not.

I'll have to look further into Gino's method of optimizing the nested loops.

Thanks for your help. The raycast is stable now, albeit slower.

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 15
• 11
• 9
• 11
• 15