Sign in to follow this  

Ray-Capsule Intersection

This topic is 4775 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

Is there a non-quadratic approach to this? Or is the non-quadratic approach more cpu intensive? I can't seem to find any information about this anywhere. The only capsule intersection I can find on the entire web is on David Eberly's website. I have some ideas on how to do this, but I haven't tried them yet. To get the shape of a cylinder in one direction, it would be possible to do a simple sphere intersect where the sphere was resting on the capsule line. Is there another way to do this? For example, if the capsule line was straight up-and-down. If you find the intersect point of the ray on the capsule line plane (the cross of the shared lines plane normal with the capsule line direction), you can place a sphere there, and do a sphere intersect straight towards the capsule line plane. The distance tells you how far to move the plane outward to do another plane intersect with the ray. The routine would simply be to get the shape of an infinite cylinder along the capsule line, using the x-offset of the ray intersect point. To put this in other words, if a ray is aimed straight at the center of a sphere, the distance is 0. If the x-offset is > || < radius, the distance is radius. Is there another way to get the distance depending on how far left or right (from the sphere) the ray moves, based on radius? I'm also afraid this method will end up being more intensive than the quadratic version I've seen. Has anyone done this before? Thanks for any advice [smile]

Share this post


Link to post
Share on other sites
there's no non-quadratic way that may be faster than quadratic, i think. Otherwise quadratic equations qould be solved that way [grin].
Also, rejection is done before taking square root so it's not that bad - you don't take square root if don't intersect.
Also, if ray does not intersect infinite cylinder, you don't need to test spheres.
Also, sphere intersection is quadratic too.

in summary, i think straightforward quadratic is faster than anything else. Also you can try using approximation to square root.(if it's raytracer, using prev. pixel's result as initial approximation.)

Share this post


Link to post
Share on other sites
Hmm, but his routine is exactly 100 more lines of code than mine, and I have a lot more comments [smile]

I know this doesn't mean it's faster or slower, but it means it is more complicated. Plus, well, I wrote mine myself, so I know exactly how it works [grin]

Maybe someone could point out any crazy ideas in my algorithm. Please remember my math skills are pretty weak, and I wrote this routine from scratch, so if you spot something that looks dumb, it probably is. Point it out for me! :)

// the diff float variable is used after this method.
// if diff is < 0, a sphere intersect is done on the
// beginning of the capsule line. If its > 0, on the end of it
// If it is == 0.0, the line completely missed the capsule

VEC contact_point;

// Only check if ray is not parallel with the cylinder
FLOAT diff = DOT( ray_directionection , cylinder_direction );
if(diff < -0.99999f || diff > 0.99999f)
{
diff = -diff;
return FALSE;
}

// Get the shared plane's normal of both lines
VEC shared_plane = CROSS( ray_direction, cylinder_direction );

// Get the normal that the cylinder line is resting on
VEC cylinder_normal = CROSS( shared_plane, cylinder_direction );
cylinder_normal.Normalize();

// Get the intersect distance from ray -> cylinder's plane
diff = DOT( cylinder_normal, ray_direction );
dist = ( DOT( cylinder_position, cylinder_normal ) - DOT( ray_position, cylinder_normal) ) / diff;

// Get the point on the ray which intersects this plane
contact_point = ray_position + ( ray_direction * dist );

// Get the closest point on the infinite cylinder line to this intersect point
diff = DOT( cylinder_direction, contact_point - cylinder_position );
VEC closest_on_cyl = cylinder_position + (cylinder_direction * diff);

// Intersect a sphere from this position, but angled straight toward cylinder
// THIS IS THE PART that feels the most hacked - because of my lack of math skills :)
VEC sp_position = contact_point - (cylinder_normal * cylinder_radius);
sp_position = closest_on_cyl - sp_position;
diff = DOT( cylinder_normal, sp_position );
dist = diff * diff - ( sp_position.LengthSquared() - (cylinder_radius * cylinder_radius) );
if(dist < 0.0f)
{
diff = 0.0f;
return FALSE;
}
dist = diff - sqrtf( dist );
if(dist < -0.0001f)
{
diff = 0.0f;
return FALSE;
}

// Insersect the plane again, but move the plane forward according to sphere shape - so we are intersecting an infinite cylinder
VEC plane_position = cylinder_position + ( cylinder_normal * (cylinder_radius - dist) );
diff = DOT( cylinder_normal, ray_direction );
dist = ( DOT( plane_position, cylinder_normal ) - DOT( ray_position, cylinder_normal ) ) / diff;

// If the ray cannot reach the infinite cylinder, we are done
if( dist > ray_length )
{
diff = 0.0f;
return FALSE;
}

// Force this point back onto ray
contact_point = ray_position + (ray_direction * dist);

// Make sure the closest point on cylinder is now on the line
diff = DOT( cylinder_direction, contact_point - cylinder_position );
if(diff < -0.0001f || diff > cyl_len + 0.0001f)
return FALSE; // diff can now be used to place a sphere when this method returns

// We hit
return TRUE;



The idea of finding the point where a line comes so close to another line sounds easy. So maybe I just went way overboard here. What do you think?

Thanks for any suggestions

Share this post


Link to post
Share on other sites

This topic is 4775 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this