# 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.
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 '14 at 5:30