0
$\begingroup$

Given:

  • An arbitrary circular cylinder (defined by startpoint, endpoint, and radius). An Infinite cylinder is acceptable as well, as long as it passes through those points and has the same radius.
  • An axis-aligned box (defined by its minimum and maximum point)
  • The box being completely inside the volume of the cylinder should also count as an intersection

To test if the cylinder and the box intersect.

Does such a test exist?

EDIT: I found this on the mathmatics stack exchange, though at the moment I do not follow it. If there is an example of it in code form that would be fantastic.

$\endgroup$
  • $\begingroup$ The key observation from the mathematics stack exchange link is that, if the two touch, either the center of the (infinite) cylinder goes through the box or an edge of the box intersects the cylinder. Does that help? $\endgroup$ – Daniel M Gessel Feb 25 at 17:19
  • $\begingroup$ @DanielMGessel Well the center is easy, I already have a ray-box intersection test. The edge of the box I'm not sure. I could manually calculate all the startpoint/endpoints of the box's edges, but then I guess I would be looking for a line-segement and cylidner intersection test? $\endgroup$ – Tyler Shellberg Feb 25 at 17:24
  • $\begingroup$ Yes, I was thinking a line segment vs cylinder intersection test too. When you do the math, you might find each of the 4 parallel lines along one axis, with the same extent, share/simplify computation. On the other hand, I also think a bounded cylinder is a little more challenging. $\endgroup$ – Daniel M Gessel Feb 25 at 17:33
  • $\begingroup$ To be honest, the fact that the cylinder is bounded is not a requirement. Infinite works too! I should specify that in the question. I thought bounded would be easier. $\endgroup$ – Tyler Shellberg Feb 25 at 17:35
  • $\begingroup$ @DanielMGessel What about the case where the box is much smaller than the radius of the cylinder and is inside it. It could not intersect with the lines of the box, while the center would miss the box as well. $\endgroup$ – Tyler Shellberg Feb 25 at 20:45
1
$\begingroup$

As mentioned the problem of cylinder box intersection reduces to the problem of line-parallelogram intersection, and line segment-cylinder intersection.

I will assume that you know how to intersect a line and a parallelogram. Here is a sketch for solving the line segment-cylinder intersection:

The canonical equation of an elliptic cylinder aligned with the $Z$ axis and having center $(c_x, c_y, c_z)$ is given as: $$\frac{(x-c_x)^2}{a^2} + \frac{(y-c_y)^2}{b^2} = 1$$ The parametric form of a ray is given as: $$\vec{r}(t) = \vec{o} + t\vec{d}$$ Then by plugging r into the canonical equation one gets: $$\frac{(o_x + td_x -c_x)^2}{a^2} + \frac{(o_y + td_y -c_y)^2}{b^2} = 1$$ Solve the quadratic equation for $t$ and you have your intersection. If the discriminant is negative then there is no intersection. To get a rotated cylinder, the easiest way is to apply the inverse rotation to the ray (the equation may be modified however too). Note that for a line segment, you simply need to check whether $t \in [t_0, t_1]$, where $\vec{a} = \vec{o} + t_0\vec{d}$ is the first point of the line segment, and $\vec{b} = \vec{o} + t_1\vec{d}$ is the second one.

EDIT: To clarify you further questions in the comments:

1) a,b in the denominator are the radii along the $X$ and $Y$ axes respectively. In the trivial case where $a=b=r$ we have the canonical equation for a circular cylinder: $$(x-c_x)^2 + (y-c_y)^2 = r^2$$

2) For the intersection between the cylinder axis and the box a rotation is only required if your box is OOBB and you want to use your AABB intersection code.

3) The solution of the quadratic equation is trivial (note, I renamed $a,b$ to $r_1,r_2$ to further emphasize that they are the radii):

$$\frac{(o_x + td_x -c_x)^2}{r_1^2} + \frac{(o_y + td_y -c_y)^2}{r_2^2} = 1$$ $$r_2^2(o_x + td_x - c_x)^2 + r_1^2(o_y + td_y -c_y)^2 = r_1^2r_2^2$$ $$(r_2^2d_x^2+r_1^2d_y^2)t^2 - 2(r_2^2d_x(c_x-o_x) + r_1^2d_y(c_y-o_y))t + r_2^2(c_x-o_x)^2 + r_1^2(c_y-o_y)^2 - r_1^2r_2^2 = 0$$

Let us substitute: $$A = (r_2^2d_x^2+r_1^2d_y^2)$$ $$B = (r_2^2d_x(c_x-o_x) + r_1^2d_y(c_y-o_y))$$ $$C = r_2^2(c_x-o_x)^2 + r_1^2(c_y-o_y)^2 - r_1^2r_2^2$$

Then you have the quadratic equation:

$$At^2 -2Bt + C = 0$$ $$D = B^2-AC$$

If $D<0$ there is no intersection between the ray $\vec{o}+t\vec{d}$ and the cylinder, otherwise:

$$t_1 = \frac{B-\sqrt{D}}{A}, t_2 = \frac{B+\sqrt{D}}{A},$$

give you the two intersections (it is one intersection if $D=0$).

Now let your segment vertices be $\vec{v}_a = \vec{o}+t_a\vec{d}$ and $\vec{v}_b = \vec{o} + t_b\vec{d}$. If $t_a \leq t_1 \leq t_b$ then you have an intersection at $t_1$, if $t_a \leq t_2 \leq t_b$ then you have an intersection at $t_2$, otherwise there is not intersection.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Sorry for the late reply. How does this boil down to a line-parallelogram intersection, again? Is the parallelogram the profile of the box from the perspective of the cylinder? Does this mean the steps boil down to: 1: Rotate cylinder to the Z axis (somehow) 2: Apply same rotation to the box (somehow) 3: Use the X and Y positions of the box after rotation to get the line segments that make it up. 4: Convert them into parametric form? 5: Plug into the equation, solve for T 6: T >= 0, intersection. Otherwise, false. Does that sound about right? Never worked with parametrics before. $\endgroup$ – Tyler Shellberg Feb 27 at 20:46
  • $\begingroup$ If the cylinder is a circular one, a and b become the radius, right? $\endgroup$ – Tyler Shellberg Feb 27 at 21:01
  • $\begingroup$ I think I must be wrong about some of those steps. Read over what you wrote again. I don't follow a few things. What rotation are we getting the inverse of? The rotation of the ray? So we rotate the box first...and then the cylinder after? Why the inverse of the rotation? Is there some way to boil this down to a line segment and circle intersection test or is there a reason that doesn't work? I feel very lost. And I think any of this rotation stuff will require quaternions and converting to-from them as well. $\endgroup$ – Tyler Shellberg Feb 27 at 21:34
  • $\begingroup$ The parallelogram was for testing the central axis of the cylinder vs box faces, but you could also rotate the coord system and just do ray-AABB intersection in that case. As for the radii for circular cylinder, $a=b=r$, yes. If the cylinder is not aligned to the Z axis, it can be transformed to such through a rotation matrix $R$. Then apply this to your rays before intersecting with the Z aligned cylinder. $\endgroup$ – lightxbulb Feb 27 at 21:56
  • 1
    $\begingroup$ @TylerShellberg I edited the post to include the segment-cylinder intersection details. Note that if the cylinder is not aligned with the $Z$ axis, you need to find the rotation $R$ that transforms the $Z$ aligned cylinder to yours. Then use that rotation on the edges of your AABB to get the line segments ($\vec{o} = R\vec{o}'$, $\vec{d}=R\vec{d}'$). $\endgroup$ – lightxbulb Feb 28 at 19:36
0
$\begingroup$

I ended up finding a fairly simple, fairly performant solution.

1: Create a transformation matrix that rotates the cylinder to one of the axis (x, y or z)

(That part is non-trivial)

2: Apply the transformation matrix to the cylinder

3: Apply the transformation matrix to the eight corners of the axis-aligned bounding box.

(Applying a transformation matrix is not too hard, it looks like this:)

newPoint[0] = (original[0] * xform[0][0]) + (original[1] * xform[1][0]) + (original[2] * xform[2][0] + xform[3][0]);
newPoint[1] = (original[0] * xform[0][1]) + (original[1] * xform[1][1]) + (original[2] * xform[2][1] + xform[3][1]);
newPoint[2] = (original[0] * xform[0][2]) + (original[1] * xform[1][2]) + (original[2] * xform[2][2] + xform[3][2]);

4: Get the distance of the corners to (0,0,0). Keep in mind that depending on your method of determining distance (IE, using a 3D distance formula) you may need to zero out the value of the point on the axis the cylinder was rotated to. If the cylinder was rotated to the Z axis, you would need to zero out the Z value for that point.

5: If any of the points report a distance less than the radius of the cylinder, you know there must be a volume intersection.

6: Special case: If the cylinder has a diameter small enough, it could fit inside of the bounding box completely, thus there would be no points for which their distance < cylinder radius. I am unsure of the maximum circle that fits within the projection of a box while not encompassing any points. My best guess is just to check if the diameter is < than any of the box's edge length, or check if the diameter is less than the diagonal of the box, which may be safer. Not sure.

7: If you want the cylinder to have a maximum length, that's not too bad either. Just take one point of the cylinder, a vector representing its direction and its length, and do origin + (dir * length) to get the endpoint of the cylinder. Transform it as well, and make sure any points you have fall within the Z of that transformed endpoint.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Will still fail in the case where a box edge intersects the cylinder, none of the box vertices are inside the cylinder, and the cylinder's axis doesn't intersect any fact of the box. $\endgroup$ – lightxbulb Mar 3 at 7:33
  • $\begingroup$ Shoot. That's a good point! I guess I will need to come up with some workarounds for those cases if I can detect them. $\endgroup$ – Tyler Shellberg Mar 3 at 15:47
  • $\begingroup$ Well, the surface intersection should work in that case. The only possibility where the volumes intersect but the boundaries (surfaces) do not, is when one is inside the other. So just use 3 checks: 1) any box vertex is closer to the cylinder axis than the cylinder radius, 2) cylinder axis-box intersection, 3) box edges-cylinder intersection. $\endgroup$ – lightxbulb Mar 3 at 16:05

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.