intersection of two cylinders in 3D space

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!

[Matt J]

Are they infinitely long cylinders?

[Tyler]

sorry, to clarify - the cylinders are finite in length (therefore the edges need to be taken into account)

Answer 1

[Matt J]

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

https://www.youtube.com/watch?v=HC5YikQxwZA

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.

[Image Analyst]

This is a brilliant explanation for infinitely long cylinders. What about a small pipe hovering above the top end of a large diameter barrel? How would you modify the method to say that they don't intersect?

[Matt J]

For finite cylinders, you would first check if they intersect when extended to infinity. If not, the finite versions can't intersect either, and that's a quick test. If the infinite versions do intersect, you would then determine the point(s) where they intersect. If those points lie within truncated cylinders, the truncated cylinders also intersect.

If the above tests are all inclusive, the quickest solution (in terms of coding time, not necessarily execution time), would be to use fmincon to find the distance between the finite cylinders. If the distance is zero, they intersect.

The distance can be computed by using fmincon to solve

 min norm(x-y)^2

 subject to the constraints

    x in Cylinder 1
    y in Cylinder 2

This is a convex problem and therefore has only global solutions.

EDIT:

In terms of computation speed, it might be faster to solve the above problem analytically using the method of Lagrange multipliers. There are only 6 inequalities needed to express the constraints and only 36 combinations of them that can be active. Not sure, though.

[Star Strider]

One of the best Answers I’ve seen here!

[Tyler]

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]

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.

Answer 2

[Matt J]

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

http://www.mathworks.com/matlabcentral/fileexchange/30892-representing-polyhedral-convex-hulls-by-vertices-or--in-equalities

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.

[Tyler]

Matt J, thank you for being so detailed and helpful. I will play around with what you suggested above when i get a chance.

is there an existing matlab function that will project a cylinder onto a plane? presumably the outcome i want is the 4 corners of the rectangle.

[Matt J]

No there's no ready-to-go function that I'm aware of, but the geometry shouldn't be that hard. You know the rectangles will have the same width and height as the cylinders they project from. Once you project the endpoints of the cylinder axes onto the plane, the known width should be enough to reconstruct the corners of the rectangles.

[Berti]

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]

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....?

Answer 3

[Matt J]

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.

Answer 4

[Bruno Luong]

This FEX might provide an answer: