Sphere - Cone Intersection

4 minute read.

Dur­ing my bach­e­lor’s the­sis about view culling for VR us­ing cones as view vol­umes, I med­i­tat­ed on dif­fer­ent in­ter­sec­tion al­go­rithms. Find my last blog post on this top­ic here: Ax­is-Aligned Bound­ing Box - Cone In­ter­sec­tion.

As cel­e­bra­tion that the blog post got ac­cept­ed in­to the ta­ble of stat­ic ob­ject in­ter­sec­tion al­go­rithms on re­al­timeren­der­ing.com, here is my slight­ly en­hanced ver­sion of David Eber­ly’s method I found for cone-sphere in­ter­sec­tion.

Sphere-cone intersection visualization.

The over­all idea is to check whether the dis­tance of the sphere’s cen­ter to the cone’s sur­face is clos­er less than its ra­dius. Find this sit­u­a­tion out­lined in the fol­low­ing fig­ure:

Sphere-cone intersection schematic.

Com­put­ing the dis­tance of the cen­ter to the cone is rather cum­ber­some and we want our so­lu­tion to be as per­for­mant as pos­si­ble, so in­stead we ex­pand the cone by the ra­dius in ev­ery di­rec­tion to then be able to do a sim­ple point-cone test.

This can be eas­i­ly achieved by off­set­ting the ori­gin back along its nor­mal, as shown by the ar­row in the op­po­site di­rec­tion of the nor­mal:

Offsetting the cone to expand its surface.

To ex­pand the cone’s sur­face by r, we move back the cone’s ori­gin by -r/sin(theta) (theta be­ing the cone’s an­gle) along the nor­mal. You will quick­ly re­al­ize that in most cas­es the new ori­gin is now fur­ther away from the orig­i­nal ori­gin than the ra­dius r and this re­sults in false pos­i­tives if the sphere is around the apex of the cone.

We there­fore split our test in­to two cas­es: the case half-space where test­ing against our off­set cone is valid and the half-space in which we in­stead test the cone’s ori­gin with the sphere. The dif­fer­ence to Eber­ly’s method is the re­al­iza­tion that two cas­es suf­fice, where Eber­ly dif­fer­en­ti­ates “be­hind the off­set cone”, “in front us­ing the off­set cone” and “in front us­ing the sphere”.

By re­al­iz­ing we can in­stead split in­to two cas­es we save a plane test, but trade that off for al­ways hav­ing to com­pute sin(theta), even if the sphere is on the half-space be­hind the off­set cone. But, this sine can be pre­com­put­ed once for the cone, which works es­pe­cial­ly well for view culling where the field of view gen­er­al­ly stays the same.

How to off­set the orig­i­nal cone’s half-space is shown in the fol­low­ing sketch:

Sphere-cone intersection schematic. Sphere-cone intersection schematic.

Re­sources and Im­ple­men­ta­tion

For a more thor­ough ex­pla­na­tion in­clud­ing the for­mu­las for off­set of plane and ori­gin, please re­fer to my bach­e­lor’s the­sis (p. 14).

Find my im­ple­men­ta­tion of this method in the code of the open-source mag­num graph­ics en­gine and its doc­u­men­ta­tion here, as well as ex­ten­sive tests and a bench­mark.