Segment-Cylinder intersection

Question

What is the complete code (C#, pseudo, does not matter) for calculating the resulting segment (or its absence) for the intersection of asegment and a cylinder?

The segment is defined by Vector3(x,y,z) as Start andVector3(x,y,z) as End.

The cylinder is defined by the same parameters plus a value for Radius.

Answer 1

Mathematical explanation with readable symbols and LaTeX format - great for 1st or 2nd year undergrad students or skilled high-school people.

Well, if you need to understand the maths behind it rather than copy-pasting some code that might not be the good one (it's not clear whether it will work or not judging from the SO code). Here are the steps:

• It's easier to find the intersection points if the cylinder is aligned with the Z axis of your Oxyz frame.

Let v = normalize(Cylinder.End - Cylinder.Start)

Compute w = cross(v, vec3(0,0,1)). If w's not the null vector, you have to perform a T transform for both Cylinder and Segment to align the scene with the oZ axis:

T = Rotation(w, arccos(dot(v,z)) ) x Translation( - Cylinder.Start) Use this transform to find the coordinates of the transformed Cylinder and Segment: Cylinder2 = T x Cylinder1, Segment2 = T x Segment1. For simplicity, I'll call the results Cylinder and Segment.

• Since the Cylinder is aligned with the Z axis, the equation of a point that lies on its surface is x^2 + y^2 = r^2, there's no constraint on the z component.

Let the equation of your segment be (x0 + t(x1-x0), y0 + t(y1-y0), z0 + t(z1-z0)) where Segment.Start(x0,y0,z0) and Segment.End(x1,y1,z1). For simplicity, let's forget about v, w and all those letters that were used until now and call x1-x0 = u, y1-y0 = v, z1-z0 = w.

That means that a POINT on the segment is written as vec3(x0+tu, y0+tv, z0+tw), where t should be in the [0,1] interval! Remember the condition for a POINT to also lie ON the SURFACE of the Cylinder? Now we get:

-- (x0+tu)^2 + (y0 + tv)^2 = r^2 which is equivalent to

-- (u^2 + v^2)t^2 + 2(u x0 + v y0)t + x0^2 + y0^2 - r^2 = 0.

Let A = (u^2 +v^2), B= 2(u x0 + v y0)t, C= x0^2 + y0^2 -r^2. You end up with a quadratic equation. Delta = B^2 - 4AC.

• Discussion:

If Delta <0 you have no intersection.

If Delta = 0, the segment is tangent to the cylinder.

If Delta > 0, you solving for t gives you t1 and t2.

Plug t1 and t2 in the POINT ON SEGMENT equation and get your P1 and P2 points that are CANDIDATES.

Remember, t1 and t2 must be between [0 and 1] in order for P1 and P2 to be points on your segment. If one of them is outside [0,1], it means your segment has an endpoint inside the cylinder. If both t1,t2 are outside [0,1], the supporting LINE of the segment intersects the cylinder, but not your segment.

One last checkup, P1.z and P2.z should be between 0 and Cylinder.End.Z, because you work with finite cylinders.

Wrap-up: you have to plug in your t1, t2 values in the INITIAL SEGMENT equation to recover the intersection points. That's it, I don't have the time to sum it up in a C# snippet, but I hope you understand what to do.