Axis-Aligned Bounding Box - Cone Intersection
~ 4 Minute Read.
During my bachelor’s thesis about view culling using cone view volumes, I had to figure out whether an axis-aligned bounding box overlaps a cone.
And when I say figure out, I mean that I didn’t find any resources online (even the comprehensive table on realtimerendering.com had an empty cell here). Whether this is because I don’t know how to use google search, nobody had use for this before (e.g. physics engines require more than just whether two objects intersect) or because it’s so simple that nobody wrote it down (which would mean I wasted many many hours over this not seeing the easy way)… here is the solution I came up with.
Important: I describe a method here that determines whether an AABB intersects with a cone, not trying to calculate the full intersection volume.
Disclaimer: Algorithm is not valid!
I want to thank Eric Haines and David Eberly for their efforts to thoroughly inspecting this algorithm, leading to the following input for which it fails:
Cone origin = {0, 0, 0}
Cone direction = normalize({1, 0.5, -1})
Cone angle = 2*0.464
Box min point = {0, 2, -1}
Box max point = {4, 4, 1}
Box center = 0.5*(min + max)
Box extents = 0.5*(max – min)For this input the box is tangent to the cone, touching it at the single point {2.5, 2, -1} on the cone’s surface, yet the algorithm reports no intersection. So it is a false negative (I originally called it a false positive here—that was a mistake). The cause is the shortcut of testing only the per-face point closest to the cone axis: that point can lie outside the cone while another point on the same face lies inside it.
Sadly, I am currently not able to make the time to look for a solution/fix. In case you find a solution, please drop an email: squareys@googlemail.com
realtimerendering.com
For a brief timeperiod this algorithm could be found on the table of Static Object Intersections on realtimerendering.com. See above note.
Algorithm
The axis-aligned constraint is pretty great here: you can simplify the 3D problem into a 2D problem by omitting one axis at a time. So that is what we’re going to do; for each axis only look at the other two.
Say the axis we chose is x for more practical explanation. Next we would extend the faces whose normals are parallel to x to infinite planes. This allows us to ray-cast the cone axis through these planes and figure out where they intersect. Since our normal is {1.0f, 0.0f, 0.0f} for this plane, the line-plane intersection formula can be simplified quite a bit even.
As the image shows, we have now reduced the problem in 3D (left) to a problem in 2D (right). We have a last problem, though: the intersection of the cone surface usually does not result in a perfect circle but an ellipse.
Instead of trying to intersect that oval/elliptic area with the square, we can instead find the point that is closest to the cone axis---this point is also closest to the cone. If it is inside the cone, we found a point that is shared by both objects and know that they intersect. This is therefore now a point cone test.
If it does not intersect, we still need to check all the other faces! If none of those result in intersection, the objects do not intersect.
Code
If you’re interested in an implementation, please have a look at the one I contributed to the Magnum Engine: find the code here and the documentation here. You will also find extensive tests there, which you can use as a starting point for trying to break this method.
May I have saved you some time :)
Written in 45 minutes, edited in 15 minutes.