How do I find the intersection of a ray and a cylinder?

Question

I'm looking for the algorithm to find the intersection (or lack of) between a ray and a cylinder. I have rotating coin like objects in my game world and need to check for a collision on that object. I also need to know the location of intersection to determine which part of the coin was hit.

The cylinder has an arbitrary rotation. I can provide as input the direction (vector) it is facing, a centre point, and a radius.

For the ray I can generalize to a line, as it'll be easy to check within the segment afterwards. Ideally I'd like the array to be an infinite cylinder, but I can easily fudge this aspect once I have the collision for a line.

Answer 1

This breaks into two distinct pieces: testing collisions against the endcaps, and testing collisions against the body of the cylinder.

The simplest way to handle both is to first transform your way into object space — the ideal 'object space' for a cylinder is with the origin at the center of one endcap and one axis (for concreteness' sake, we'll say the Z axis) running along the 'body' of the cylinder, orthogonal to the endcap planes. In this space, your cylinder is then a pair of discs of radius R in the xy plane, capping a cylinder that runs from z=0 to z=L.

To intersect the ray with one endcap, then, you need to find the point on your ray where it intersects the xy plane: assuming that your ray's equation is r(t)=r0+d*t (I'm using boldface here for vector quantities), then by solving r_z(t)=0 for t, you find t=-(r0_z/d_z) (note that this breaks down if d_z=0; in other words, if your ray is parallel to the xy-plane. In that case, you can skip the endcap test and just test against the cylinder, along with a check to make sure that r0_z is between 0 and L). (Similarly, if you were trying to intersect with the z=L endcap, you'd find t=(L-r0_z)/d_z ). Plugging this value of t into your ray equation then gives you a point p where the ray intersects the plane of the endcap; now you just need to test whether this point is within your disc or not - in other words, whether p_x²+p_y² ≤ R².

Testing against the body of the cylinder works similarly, but is a bit more complicated: in this case, you'll project your ray down to the 2d plane (since we're working in object coordinates, this is as simple as dropping the z component of your ray equation — you can see why these coordinates are so useful!) and then doing a 2d line-circle intersection: essentially you want to find the points where |r_xy(t)|²=R² (here r_xy(t) is the ray equation 'projected' down to the xy plane by dropping the z component); this equation is just a quadratic in t, and you can solve it for the two possible values of t. One big caveat, though: once you find the two values of t that solve the equation (and note that there may be none, which means that your ray doesn't intersect the cylinder at all), you'll have to plug them back into your original equation to make sure the corresponding z values fall in the 0..L range.

Finally, you'll have (up to) four distinct t values: the two possible intersections with the endcaps, and the two possible intersections with the sides of the cylinder. (Of course, in practice there can only be two, but that's a separate matter). Just choose the smallest of these that's greater than zero, and that's your intersection point.

Answer 2

Ray intersection usually starts with a faster check against the bounding box of the cylinder, before you do the more expensive check against the cylinder geometry. Either way, it boils down to a line-plane intersection test (since the cylinder is comprised of a bunch of polygons, which are themselves bounded planes).

The math for that is explained here (hope you're good at math!) http://geomalgorithms.com/a05-_intersect-1.html#Plane-Intersections

(incidentally I'm assuming you need to do the math from scratch and aren't using a framework with raycasting already in it, since you don't mention that)