Jump to content
  • Advertisement
Sign in to follow this  
bzroom

GJK Raycast

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!