0
$\begingroup$

Say I have a cuboid in $\mathbb R^3$ space whose axes are aligned with the axes of the coordinates system (also called an axis aligned bounding box). The cuboid is defined by it's minimum coordinate $A$ (the vertex with the lowest values in all coordinates) and it's maximum coordinate $B$. And a capsule defined by a segment with end points $a$ and $b$, and radius $r$.

The two shapes intersect if the capsule's defining segment intersects the cuboid. However if the segment and the cuboid do not intersect, what is the condition for which the two shapes can still intersect?

$\endgroup$

1 Answer 1

1
$\begingroup$

Hint:

You can reason in terms of Minkowski sums.

If you dilate the cube with a sphere of radius $r$ and at the same time erode the capsule, you transform the problem to the intersection of a rounded cube with a line segment. The rounded cube can be described as the union of three orthogonal prisms, twelve cylinders and eight spheres.

You can process the intersection of the segment and these shapes independently. First consider the intersections of the line of support of the segment. The intersection with the prisms amounts to intersections with planes. Intersection with a sphere depends on the distance of the line to the center of the sphere and intersection with the cylinders depends on the shortest distance to the axis.

If the distance criteria pass, you still need to compute the intersection points with the surfaces and check if they belong to the useful patches. As all surfaces are at most quadrics, you'll have to solve quadratic equations.

$\endgroup$
5
  • $\begingroup$ Thank you, this is an interesting solution! Can I ask, I just looked into separating axis theorem. Could we use that as an alternative solution? By projecting the capsule onto each normal of the cuboid, which in this case overlap with the coordinate axes. $\endgroup$ Commented Apr 3, 2021 at 18:47
  • $\begingroup$ @LennyWhite: it is a fact from computational geometry: you cannot escape checking the segment against all surfaces I described. No approach will make it simpler, there is no free lunch. $\endgroup$
    – user65203
    Commented Apr 3, 2021 at 19:04
  • $\begingroup$ I see thanks! I did indeed just test out the separating axis theorem and it doesn't work for this case. I have to say though this looks like one expensive intersection test for the computer to handle. $\endgroup$ Commented Apr 3, 2021 at 23:51
  • $\begingroup$ @LennyWhite: yes and no. Implementing the complete test is a little tedious because of the various cases. But one can arrange the computation to minimize the workload, by ordering the tests so that the most costly are only performed when really needed. For example, you can begin by a simple bounding box test that will settle the cases of the capsule sufficiently far from the cuboid. If these cases are frequent, the average cost will be pretty low. $\endgroup$
    – user65203
    Commented Apr 5, 2021 at 7:55
  • $\begingroup$ @LennyWhite: note that the separating axis theorem perfectly works on this problem, but it will in no way simplify the discussion. As I said, there is no free lunch. $\endgroup$
    – user65203
    Commented Apr 5, 2021 at 7:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .