Intersection between a cylinder and an axis-aligned bounding box

Given a 3D axis-aligned bounding box (represented as its minimum point and maximum point) and a 3D cylinder of infinite length, what's the best way to test for intersection?

-
So the box is given to you as $x_{min}\leq x\leq x_{max},y_{min}\leq y\leq y_{max},z_{min}\leq z\leq z_{max}$? How is the cylinder presented? –  Alex Becker Jul 5 '12 at 4:54
The cylinder is represented as a point (that lies somewhere on the line at the cylinder's center), a vector (that points along the line), and a radius. And the cylinder extends infinitely far along the line (in both directions from the point.) –  Nicholas Bishop Jul 5 '12 at 5:05

Suppose you are given a box defined by $$x_{min}\leq x\leq x_{max},y_{min}\leq y\leq y_{max},z_{min}\leq z\leq z_{max}$$ and a cylinder of radius $r$ along the vector $\vec v=(v_1,v_2,v_3)^T$ with its center passing through $\vec p=(p_1,p_2,p_3)^T$. First construct the projection matrix $P$ which maps vectors onto their projection in the plane perpendicular to $\vec v$. I assume $v_1\neq 0$, otherwise the matrix will have to be constructed slightly differently. We have $$P=\begin{pmatrix} 0 & 1 & 0\\ 0 & 0 & 1\\ \end{pmatrix}\begin{pmatrix} v_1 & 0 & 0\\ v_2 & 1 & 0\\ v_3 & 0 & 1\\ \end{pmatrix}^{-1}=\begin{pmatrix} \frac{-v_2}{v_1} & 1 & 0\\ \frac{-v_3}{v_1} & 0 & 1\\ \end{pmatrix}$$ and thus a vector $\vec x$ lies in the cylinder iff $\|P(\vec x-\vec p)\|\leq r$. Note that the projection of the box is a convex set and is equal to the convex hull of the images of its vertices, and that either the image of center of the cylinder is contained in the image of the box or the boundary of the image of the box intersects the image of the cylinder.

In the first case, we have that the line $\vec p + t\vec v$ intersects one of the three planes $x=x_{min},y=y_{min},z=z_{min}$ within the boundary of the box. The points of intersection are given by $$\begin{pmatrix} x_{min}\\ p_2+\frac{x_{min}-p_1}{v_1}v_2\\ p_3+\frac{x_{min}-p_1}{v_1}v_3\\ \end{pmatrix}, \begin{pmatrix} p_1+\frac{y_{min}-p_2}{v_2}v_1\\ y_{min}\\ p_3+\frac{y_{min}-p_2}{v_2}v_3\\ \end{pmatrix}, \begin{pmatrix} p_1+\frac{z_{min}-p_3}{v_3}v_1\\ p_2+\frac{z_{min}-p_3}{v_3}v_2\\ z_{min}\\ \end{pmatrix}$$ and are nonexistant if $v_1,v_2$ or $v_3$ respectively are $0$. It is easy to check whether these are contained in the box. If any of them are, the intersection is nonempty.

In the second case, let $\vec x_1+t\vec y_1,\ldots,\vec x_{12}+t\vec y_{12}$ be the lines which form the edges of the box (and are exactly the edges when $0\leq t\leq 1$), which are easy to determine from the vertices. We want to know whether there is a solution to $\|P(\vec x_i+t\vec y_i-\vec p)\|\leq r$ for any $i$ with $0\leq t\leq 1$. Observe that $\|P(\vec x_i+t\vec y_i-\vec p)\|^2-r^2$ is a quadratic equation in $t$, so we can differentiate it to get a linear equation and solve for $0$ to get a value $t_i$. We then check for $i=1,\ldots,12$ whether $\|P(\vec x_i+t_i\vec y_i-\vec p)\|\leq r$ and $0\leq t_i\leq 1$. If this holds for some $i$, then the intersection is nonempty. Otherwise we test the endpoints $t=0$ and $t=1$ for each $i$ to see whether any of them satisfy $\|P(\vec x_i+t\vec y_i-\vec p)\|\leq r$. If so, the intersection is nonempty.

Finally, if all the above tests have failed then the intersection is empty.

In general, problems like this are studied bin the field of Real Semialgebraic Geometry. More complicated questions of this form are approached by a method known as Cylindrical Algebraic Decomposition or CAD, which is similar to the method I employed but would have reduced the number of needed calculations by determining the six lines which bound the image rather than using all twelve lines that bound the box, but is more difficult to grasp.

-
I think you could construct $P$ more simply as $P = 1 - \vec v \vec v^T$. The matrix $\vec v \vec v^T$ (the outer product of $\vec v$ with itself) maps a vector to its projection on $\vec v$, assuming that $\vec v$ is unit length. Then $1 - \vec v \vec v^T$ projects onto the plane perpendicular to $\vec v$. –  Nathan Reed Feb 11 at 5:30