5
$\begingroup$

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$:

enter image description here

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?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @bsumirak: interesting comment. Is there anything I can do for you ? $\endgroup$ – Yves Daoust Feb 3 '17 at 10:41
  • $\begingroup$ Sorry, was too slow editing after accidentally hitting return. Here it is: Two problems with this approach: (1) The cylinders, if intersecting, do not necessarily intersect in BOTH lateral surfaces. (2) When solving the parametric description of the intersection curve on the first cylinder for $t=0$ and $t=L_1$, there need not necessarily be a solution as the intersection line might be completely inside or completely outside the bounds for t. $\endgroup$ – bsumirak Feb 3 '17 at 10:52
  • $\begingroup$ @bsumirak It is unclear to me if the OP means intersection of the volumes or of the surfaces (with or without the caps). In all cases, the intersection curves will play a role, but the complete discussions are different. This is just a hint how to establish a tractable formulation if the problem. $\endgroup$ – Yves Daoust Feb 3 '17 at 11:01

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.