3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ If your cylinders are coins, then it sounds like you're mostly interested in clamped cylinders, and particularly the endcaps - is that a fair characterization? \$\endgroup\$ – Steven Stadnicki May 19 '14 at 19:31
  • \$\begingroup\$ At first I though that. However, it is vitally important that I can detect an intersection on the walls as well. It'll happen often enough that the player will feel cheated if I don't. \$\endgroup\$ – edA-qa mort-ora-y May 19 '14 at 20:36
6
\$\begingroup\$

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 rz(t)=0 for t, you find t=-(r0z/dz) (note that this breaks down if dz=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 r0z is between 0 and L). (Similarly, if you were trying to intersect with the z=L endcap, you'd find t=(L-r0z)/dz ). 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 px2+py2 ≤ R2.

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 |rxy(t)|2=R2 (here rxy(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.

\$\endgroup\$
0
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ My ray library doesn't include cylinders. I don't want to do the polygon level checks, I'm looking for an exact cylinder check (I don't want the test to be dependent on how I've created the mesh for the cylinder). \$\endgroup\$ – edA-qa mort-ora-y May 19 '14 at 16:15
  • \$\begingroup\$ And yes, bounding check will of course be done before. In this case a sphere check works. \$\endgroup\$ – edA-qa mort-ora-y May 19 '14 at 16:16
-1
\$\begingroup\$

I found a C++ library that contains the intersection code I want. It looks reasonably well commented so I can follow what is happening.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.