How to determine whether two cylinders intersect or not?

Question

Considering any two cylinders, defined as: the center of their bottoms $A_i$, the radius of their bottom $R_i$, the unit vector $W_i$ of their axis direction, and the length $L_i$ of the cylinders, where $i=1,2$:

what is the necessary and sufficient condition of the intersection of the two cylinders?

I want to numerically determine (by program, e.g., Matlab or C++) whether two given cylinders intersect with each other or not. So whether the problem is numerically solvable and the uniqueness and existence of the solution become important.

Numerically, I tried to convert the problem into a linearly constrained least squares problem, but found it is hard to prove the equivalence between the intersection and the solution of the problem.

The constrained least squares problem is:

1. linear constraints: the convex point sets of points between the top and bottoms of the two cylinders, this defines four linear constraints;
2. find the point of which the summed squares of distance to the two cylinder axes is at minimum;

Then compare the minimum value with $\displaystyle\sum\limits_{i=1}^2 R_i^2$ to determine whether the cylinders intersect or not. -- It seems counter example can be found when there is no intersection point while the minimum is still less than the criterion.

How to find a numerically solvable (e.g., numerically convex optimization) necessary and sufficient condition so as to determine whether two cylinders intersect or not?

Answer 1

David Eberly has a good description of the solution (with pseudocode) here: http://www.geometrictools.com/Documentation/IntersectionOfCylinders.pdf

The short summary: like most convex-convex collision detection algorithms, you search systematically for a separating axis between the cylinders.

For future reference on similar problems, the authors of Real-Time Rendering maintain a table of links for intersection tests between different types of primitives.

Answer 2

Hint:

If the two cylinders are parallel, the problem is easy. Otherwise, if the perpendicular distance between the axis exceeds the sum of the radii, there is no intersection.

Otherwise, there is an intersection curve between the two lateral surfaces. It can be expressed analytically: without loss of generality, the second cylinder is vertical with a base at the origin (if not, rotate and translate). Its lateral surface has the implicit equation

$$x^2+y^2=R_2^2.$$

Any point of the lateral surface of the first cylinder can be reached by the parametric equation

$$A_1+U_1R_1\cos(s)+V_1R_1\sin(s)+W_1t,\\ 0\le s\le 2\pi$$ where $U_1$ and $V_1$ form an orthogonal basis with $W_1$.

Plugging the parametric equation in the implicit one, you get an equation which is quadratic in $t$. So you can express $t$ as a function of $s$, analytically.

Solving for $t=0$ and $t=L_1$ (numerically) gives you the useful sections of the curve that belong to the first cylinder, and delimit an $(s,t)$ domain.

By plugging the equations of the boundaries of this domain in the parametric equation ($z$ component), you should be able to tell if

$$0\le A_{1z}+U_{1z}R_1\cos(s)+V_{1z}R_1\sin(s)+W_{1z}t\le L_2$$ occurs in the domain.