Infinite cone surface * AABB intersection testing

Question

I'm trying to discover a faster algorithm for testing whether an axis-aligned conical surface intersects the volume of an axis-aligned bounding box.

The current algorithm I developed is as follows:

• x = 0
• For each of any 4 parallel edges of the AABB:
  • Intersect its line with the cone.
  • If the intersection point is within the AABB:
    • Return true.
  • If the intersection point is on a specific side of the AABB:
    • x += 1
• If x == 0 or x == 4 (all the intersections were on one side of the AABB):
  • Return false.
• Return true.

Can anyone think of a more efficient one? This seems to do a lot of extra work by computing each line intersection.

EDIT:

Above algorithm is bad, for example:

The cone can intersect only one edge of the box in a way that all the axis-line intersections are on one side, so the above algorithm doesn't work unless all edges are tested or the edges to be tested are intelligently chosen (maybe the edges closest to the cone?).

EDIT EDIT: See my own answer below for the solution I later discovered, which seems nearly optimal to me.

Answer 1

I found a possibly optimal solution:

The equation for a unit right cone opening along the +-z axis is x^2 + y^2 - z^2 = 0.

Find the maximum and minimum of x^2 + y^2 - z^2 over the AABB using interval arithmatic. Hint: For x^2, the minimum is clamp(0, [xmin, xmax])^2 and the maximum is max(xmin^2, xmax^2).

• If the resulting interval is completely negative, the box is completely inside the cone.
• If the resulting interval contains 0, the box intersects the surface of the cone.
• If the resulting interval is completely positive, the box is completely outside of the cone.