Infinite cone surface * AABB intersection testing

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 exampl开发者_运维百科e:

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.

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.

Looking at this table of object/object intersection tests it seems that there's no well-known cone/AABB intersection test. So you're on your own, I'm afraid!

You might start with David Eberly's article "Intersection of a Triangle and a Cone" and see how much of that you can adapt to your situation. (In the worst case, an AABB is made up of 12 triangles, but I expect you can do better than that.)

The link to the David Eberly article from @Gareth Rees is a good one, but if you split everything into triangles, you'll end up checking redundant vertices and edges. I think this will work well:

1. (Optional) Check if the AABB is entirely on the opposite side of the plane perpendicular to the cone axis. If so, there's no intersection.

2. Check each of the 8 vertices to see if it's inside the cone. If any vertex is, the cone and AABB intersect. This is pretty straighforward, but it's explained on page 4 of the link.

3. Check each of the 12 edges to see if they intersect the cone. If any edge does, the cone and AABB intersect. This is on pages 4-5 of the link.

4. Check each of the 6 faces to see if they intersect the cone. If any edge does, the cone and AABB intersect. It's sufficient to the check ray formed by the cone axis against the AABB; this is a pretty standard intersection test.

It may actually be better to swap the order the face and edge checks; I'd expect the face checks to be faster that the edge ones, so you might be able to exit earlier.

There are probably some nice opportunities for SIMD optimizations since the numbers of vertices and edges are both multiples of 4 and the cone is axis-aligned, but that's beyond the scope of this answer :)

I came up with an algorithm to solve the general case of an arbitrary cone and aabb, but it still handles your specific case efficiently.

I described it in another thread: Detect if a cube and a cone intersect each other?