What is the easiest way to find a cyl <-> cyl intersection?

Hello, thanks for looking at this,

I've been working on this problem for awhile, basically I want to find the fastest and most accurate way to find the intersection (if one exists) between two cylinders.

I've been looking at doing this using barycentric coordinates, and I can get it working quickly and efficiently using rays. When it comes to 3D, though, the mathematical formulation I have begins to slow down rapidly (~3 seconds for ~100 segments). Is there a faster way to do this, perhaps just using geometry (NURBS perhaps)?

[Amit]

Does the cylinders have finite length? In case two cylinders intersect, there can be 2, 4 ,8 or infinte intersection point (infinite in case where two cylinders touch each other). If you are interested in only one intersection point (which verifies the cylinder do intersect), there is a simple approach using fsolve.

[Brian]

Hello,

I'm just about to reduce this to a ray - cylinder to make things easier (and there's code available to look at), but its different from what I would ideally have, and perhaps give false negatives. In this way, there would be a max of two intersection points (entering, and if it pierces, a exit point).

Ideally, I would like to have two cylinders. I just want to know if they do in fact intersect. fsolve, then, would be sufficient?

Answer 1

[Amit]

Lets assume both of your cylinders are of radius r1 and r2. You can represent a cylinder in cartesian coordinates (x,y,z) using parameters phi and theta (for more reference see this - http://en.wikipedia.org/wiki/Cylinder_(geometry)#About_an_arbitrary_axis) A ith cylinder can be represented as:

A_i = -x*sin(theta_i)+y*cos(theta_i)*cos(phi_i) + z*cos(theta_1)sin(phi_1)
B_i = -y*sin(phi_1) + z*cos(phi_1)
and A_i^2 + B_i^2 = ri^2

The point of intersection (x1,y1,z1) will satisfy for both cylinders.

So your function will take ([x y z]) as input (which you wanna solve) and in the function you will compute A_1, B_1, A_2 and B_2 and function output will be

F = (A_1^2+B_1^2-r1^2)^2 + (A_2^2+B_2^2-r2^2)^2 % This is what will be zero if condition satifies

You can easily solve this using fsolve. Hope this helps.

[Brian]

Sorry for the late response.

I'll check this out. I took a look at the link, and I think I know what to do. Basically, if the fsolve command is equal to zero (or very close to zero) you have an intersection. i=1,2 refers to both cylinders.

By using

   A_i^2 + B_i^2 = ri^2

and subtracting it from ri^2, you should get zero (or something close to zero). Thats why the third equation works.

I'll give it a try and see how it works out. Thanks again!