intersection of two cylinders in 3D space

35 views (last 30 days)
Tyler
Tyler on 10 May 2014
Edited: Bruno Luong on 13 Sep 2018
HI everyone,
does anyone know of an existing algorithm to check the intersection of two cylinders in 3D space? I believe this is done by projecting the cylinders onto a plane and checking for a "separating axis"
Any help would be greatly appreciated!
  2 Comments
Matt J
Matt J on 10 May 2014
Edited: Matt J on 10 May 2014
Are they infinitely long cylinders?
Tyler
Tyler on 10 May 2014
sorry, to clarify - the cylinders are finite in length (therefore the edges need to be taken into account)

Sign in to comment.

Answers (4)

Matt J
Matt J on 10 May 2014
Edited: Matt J on 10 May 2014
If the cylinders are of infinite length, it can be done by finding the shortest distance between the cylinder axes. Calculating the distance between two lines in 3D is explained, for example in this video
Once you have the distance between the central axes of the cylinders, you just check if it is less than the sum of the cylinder radii. If so, the cylinders intersect, otherwise, they do not.
  5 Comments
Tyler
Tyler on 11 May 2014
Matt J, can you elaborate on subjecting the norm command to constraints? from what i understand the norm command finds the distance between two vectors - are you representing the cylinders as vectors?
Matt J
Matt J on 11 May 2014
Edited: Matt J on 11 May 2014
The cylinders are to be represented using inequality constraints. So, for example, suppose x=(u1,u2,u3), is a point in Cylinder 1 and y=(v1,v2,v3) is a point in Cylinder 2. Suppose further, for simplicity, that Cylinder 1 is centered on the u3/v3 axis, and Cylinder2 is centered on the u1/v1 axis. Then the 6-dimensional vector (u1,u2,u3,v1,v2,v3) satisfies inequalities
u1^2+u2^2<=radius1^2
LowerBound1<=u3<=UpperBound1 %containment in Cylinder 1
v2^2+v3^2<=radius2^2
LowerBound2<=v1<=UpperBound2 %containment in Cylinder 2
If you minimize the function
f(u1,u2,u3,v1,v2,v3) = norm((u1,u2,3) - (v1,v2,3))^2
subject to the inequalities, you will find the shortest separation (squared) between the cylinders, which will be zero if the cylinders intersect.
The above is a nonlinear, constrained optimization problem. It can be solved analytically using Lagrange Multipliers. Or, you can let fmincon() do it for you, but that's an iterative solver, so it might take longer and not be as exact.
To modify the constraints to handle cylinders in arbitrary positions, you must make a variable substitution x'=R*x+t in the inequalities for each cylinder, where R is an appopriate 3x3 rotation matrix and t is a translation vector.

Sign in to comment.


Matt J
Matt J on 11 May 2014
Edited: Matt J on 11 May 2014
I believe this is done by projecting the cylinders onto a plane and checking for a "separating axis"
I didn't realize until a short while ago how this could be done, but I think I understand it now and it does make things a lot easier.
First, I'll assume that the cylinders are not parallel. It is easy to detect the intersection of parallel cylinders. It occurs when both (1) the separation of their axes is less than the sum of their radii (2) projecting the cylinders onto a common parallel axis results in overlapping line segments.
I'll also assume that the cylinders do intersect when extended to infinity. I explained in my other answer why this is easy to detect. If they don't intersect when extended to infinity, they don't intersect period.
Since the cylinders are not parallel, then their axes have direction vectors u1 and u2 with non-zero cross product
u3=cross(u1,u2)
I claim that if you project the cylinders onto the plane normal to u3, you will get rectangles which intersect if and only if the original cylinders intersect. So, the problem reduces to finding the intersection of 2 rectangles.
Finding the intersection of rectangles is very easy to do using, for example, this FEX sumbmission
When the cylinders are projected onto the plane, the rectangles will be given by 2 sets of inequalities
A1*x<=b1
A2*x<=b2
where A1,A2 are each 4x3 and b1,b2 are 4x1. You can then use lcon2vert in the FEX package to get the vertices of the intersection, by combining the equalities into one system
V=lcon2vert([A1;A2],[b1;b2])
If it returns V=[], then no vertices and hence no intersection, was detected.
  4 Comments
Berti
Berti on 10 Apr 2015
I'm afraid this test is not 100% accurate. The problem arises if the infinite cylinder barely touch each other. In the projection to u3, the intersection would be close to the projected main axis of the cylinders. However, the two rectangles would intersect in cases where there is no actual cylinder intersection. For example, the corners of the rectangles could overlap before the projected main axis intersects.
Matt J
Matt J on 10 Apr 2015
I think I see what you mean, Berti. Well, I think that the test can at least be used to rule out intersection of the projected rectangles don't overlap.
I conjecture that if you make two more projections - one onto the plane perpendicular to u1 and the other onto the plane perpendicular to u2 -- that you would complete the test. The cylinders do not intersect if and only the projected shapes fail to intersect on at least one of those 3 planes....?

Sign in to comment.


Matt J
Matt J on 10 May 2014
Edited: Matt J on 10 May 2014
Another option would be to take lots of sample points (x,y,z) on the circular caps of both cylinders and try to find a separating plane between them. This is equivalent to what is done in the training of support vector machines and can be done using the svmtrain() command in the Statistics Toolbox.
It's an approximate solution of course, with error depending on how much sampling you do.

Bruno Luong
Bruno Luong on 13 Sep 2018
Edited: Bruno Luong on 13 Sep 2018
This FEX might provide an answer:

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!