Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

What is the complete code (C#, pseudo, does not matter) for calculating the resulting segment (or its absence) for the intersection of the segment and the 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 floating-point value as Radius.

share|improve this question
    
You don't tell us what you've tried and what the specific problem is. –  Byte56 Apr 11 '12 at 15:19
    
Hm, it's generally a bad practice to ask for code. Pseudocode is fine, because it's just that vague as not to be copy-pasted somewhere. By pseudocode I understand any human readable crap though. Hence my answer. –  teodron Apr 11 '12 at 15:57

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
Excellent explanation. –  AgentFire Apr 12 '12 at 5:33
    
... but really bad formatting –  bummzack Apr 12 '12 at 7:58
    
Ok, ok, I'll do it in LaTeX. Can't find how to add LaTeX directly here, so it's going to be mathbin instead. Hope it will help.. somehow. –  teodron Apr 12 '12 at 9:18
    
It did help me. –  AgentFire Apr 12 '12 at 11:20
    
You can now check the updated version with decently written equations and symbols. Good luck! –  teodron Apr 12 '12 at 11:31

You may find what you're looking for with this question from SO. The last answer seems to fit your request, remember to up-vote that if it helped you.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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