Jiia 592 Report post Posted November 14, 2004 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] 0 Share this post Link to post Share on other sites
Eelco 301 Report post Posted November 14, 2004 i think capsules are a bit of a hack. they are not a true primitive.i just use infinite cylinders and other simple primitives in combination with CSG. 0 Share this post Link to post Share on other sites
Dmytry 1151 Report post Posted November 14, 2004 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.) 0 Share this post Link to post Share on other sites
Jiia 592 Report post Posted November 14, 2004 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 capsuleVEC contact_point;// Only check if ray is not parallel with the cylinderFLOAT 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 linesVEC shared_plane = CROSS( ray_direction, cylinder_direction );// Get the normal that the cylinder line is resting onVEC cylinder_normal = CROSS( shared_plane, cylinder_direction );cylinder_normal.Normalize();// Get the intersect distance from ray -> cylinder's planediff = 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 planecontact_point = ray_position + ( ray_direction * dist );// Get the closest point on the infinite cylinder line to this intersect pointdiff = 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 cylinderVEC 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 doneif( dist > ray_length ){ diff = 0.0f; return FALSE;}// Force this point back onto raycontact_point = ray_position + (ray_direction * dist);// Make sure the closest point on cylinder is now on the linediff = 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 hitreturn 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 0 Share this post Link to post Share on other sites