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.

[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.

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.