Axis-Aligned Bounding Box - Cone Intersection

~ 4 Minute Read.

Dur­ing my bach­e­lor’s the­sis about view culling us­ing cone view vol­umes, I had to fig­ure out whether an ax­is-aligned bound­ing box over­laps a cone.

Visualization of aabb cone intersection.

And when I say fig­ure out, I mean that I didn’t find any re­sources on­line (even the com­pre­hen­sive ta­ble on re­al­timeren­der­ing.com had an emp­ty cell here). Whether this is be­cause I don’t know how to use google search, no­body had use for this be­fore (e.g. physics en­gines re­quire more than just whether two ob­jects in­ter­sect) or be­cause it’s so sim­ple that no­body wrote it down (which would mean I wast­ed many many hours over this not see­ing the easy way)… here is the so­lu­tion I came up with.

Im­por­tant: I de­scribe a method here that de­ter­mines whether an AABB in­ter­sects with a cone, not try­ing to cal­cu­late the full in­ter­sec­tion vol­ume.

Al­go­rithm

The ax­is-aligned con­straint is pret­ty great here: you can sim­pli­fy the 3D prob­lem in­to a 2D prob­lem by omit­ting one ax­is at a time. So that is what we’re go­ing to do; for each ax­is on­ly look at the oth­er two.

Say the ax­is we chose is x for more prac­ti­cal ex­pla­na­tion. Next we would ex­tend the faces whose nor­mals are par­al­lel to x to in­fi­nite planes. This al­lows us to ray-cast the cone ax­is through these planes and fig­ure out where they in­ter­sect. Since our nor­mal is {1.0f, 0.0f, 0.0f} for this plane, the line-plane in­ter­sec­tion for­mu­la can be sim­pli­fied quite a bit even.

Sketch of aabb cone intersection.

As the im­age shows, we have now re­duced the prob­lem in 3D (left) to a prob­lem in 2D (right). We have a last prob­lem, though: the in­ter­sec­tion of the cone sur­face usu­al­ly does not re­sult in a per­fect cir­cle but an el­lipse.

In­stead of try­ing to in­ter­sect that oval/el­lip­tic area with the square, we can in­stead find the point that is clos­est to the cone ax­is—this point is al­so clos­est to the cone. If it is in­side the cone, we found a point that is shared by both ob­jects and know that they in­ter­sect. This is there­fore now a point cone test.

If it does not in­ter­sect, we still need to check all the oth­er faces! If none of those re­sult in in­ter­sec­tion, the ob­jects do not in­ter­sect.

Code

If you’re in­ter­est­ed in an im­ple­men­ta­tion, please have a look at the one I con­trib­uted to the Mag­num En­gine: find the code here and the doc­u­men­ta­tion here. You will al­so find ex­ten­sive tests there, which you can use as a start­ing point for try­ing to break this method.

May I have saved you some time :)

Writ­ten in 45 min­utes, ed­it­ed in 15 min­utes.