Icon ASCII : A Love Letter


Icon My Neural Network isn't working! What should I do?


Icon Phase-Functioned Neural Networks for Character Control


Icon 17 Line Markov Chain


Icon 14 Character Random Number Generator


Icon Simple Two Joint IK


Icon Generating Icons with Pixel Sorting


Icon Neural Network Ambient Occlusion


Icon Three Short Stories about the East Coast Main Line


Icon The New Alphabet


Icon "The Color Munifni Exists"


Icon A Deep Learning Framework For Character Motion Synthesis and Editing


Icon The Halting Problem and The Moral Arbitrator


Icon The Witness


Icon Four Seasons Crisp Omelette


Icon At the Bottom of the Elevator


Icon Tracing Functions in Python


Icon Still Things and Moving Things


Icon water.cpp


Icon Making Poetry in Piet


Icon Learning Motion Manifolds with Convolutional Autoencoders


Icon Learning an Inverse Rig Mapping for Character Animation


Icon Infinity Doesn't Exist


Icon Polyconf


Icon Raleigh


Icon The Skagerrak


Icon Printing a Stack Trace with MinGW


Icon The Border Pines


Icon You could have invented Parser Combinators


Icon Ready for the Fight


Icon Earthbound


Icon Turing Drawings


Icon Lost Child Announcement


Icon Shelter


Icon Data Science, how hard can it be?


Icon Denki Furo


Icon In Defence of the Unitype


Icon Maya Velocity Node


Icon Sandy Denny


Icon What type of Machine is the C Preprocessor?


Icon Which AI is more human?


Icon Gone Home


Icon Thoughts on Japan


Icon Can Computers Think?


Icon Counting Sheep & Infinity


Icon How Nature Builds Computers


Icon Painkillers


Icon Correct Box Sphere Intersection


Icon Avoiding Shader Conditionals


Icon Writing Portable OpenGL


Icon The Only Cable Car in Ireland


Icon Is the C Preprocessor Turing Complete?


Icon The aesthetics of code


Icon Issues with SDL on iOS and Android


Icon How I learned to stop worrying and love statistics


Icon PyMark


Icon AutoC Tools


Icon Scripting xNormal with Python


Icon Six Myths About Ray Tracing


Icon The Web Giants Will Fall


Icon PyAutoC


Icon The Pirate Song


Icon Dear Esther


Icon Unsharp Anti Aliasing


Icon The First Boy


Icon Parallel programming isn't hard, optimisation is.


Icon Skyrim


Icon Recognizing a language is solving a problem


Icon Could an animal learn to program?




Icon Pure Depth SSAO


Icon Synchronized in Python


Icon 3d Printing


Icon Real Time Graphics is Virtual Reality


Icon Painting Style Renderer


Icon A very hard problem


Icon Indie Development vs Modding


Icon Corange


Icon 3ds Max PLY Exporter


Icon A Case for the Technical Artist


Icon Enums


Icon Scorpions have won evolution


Icon Dirt and Ashes


Icon Lazy Python


Icon Subdivision Modelling


Icon The Owl


Icon Mouse Traps


Icon Updated Art Reel


Icon Tech Reel


Icon Graphics Aren't the Enemy


Icon On Being A Games Artist


Icon The Bluebird


Icon Everything2


Icon Duck Engine


Icon Boarding Preview


Icon Sailing Preview


Icon Exodus Village Flyover


Icon Art Reel




Icon One Cat Just Leads To Another

Correct Box Sphere Intersection

Created on April 2, 2013, 1:21 p.m.

Testing for intersection between a box and sphere is not as trivial as it may first seem.

I found many resources on the web explaining how to do it, but after struggling for a while I realized all of them listed an incorrect algorithm. What they stated was that you had to try for intersection against all face planes of the box. Some did mentioned briefly that this is flawed, but most didn't seem to even be aware. With a little bit of thought the reason this is incorrect becomes obvious.

Box Sphere Intersection

If you simply check for intersection with the face planes of the box you get a bunch of false positives where the planes extend past the ends of the box. While perhaps a few false positives may not be a big deal in some cases, when there are large spheres and acceleration structures such as quad trees, false positives can mean many, many more operations than usual. Actually doing the correct checks are not much more expensive and overall improve performance.

To start we need to write three tests for checking if a sphere is inside, outside or intersecting a plane. This can be done by taking the signed distance from the plane and comparing to the sphere radius.

If the distance is negative and greater than the radius we know it is inside. If the distance is positive and greater than the radius we know it is outside. Finally if the absolute distance is less than or equal to the radius we know there is an intersection.

float plane_distance(plane p, vec3 point) {
  return vec3_dot(vec3_sub(point, p.position), p.direction);

bool sphere_inside_plane(sphere s, plane p) {
  return -plane_distance(p, s.center) > s.radius;

bool sphere_outside_plane(sphere s, plane p) {
  return plane_distance(p, s.center) > s.radius;

bool sphere_intersects_plane(sphere s, plane p) {
  return fabs(plane_distance(p, s.center)) <= s.radius;

Using these we can test for if a sphere is inside, outside or intersecting a box (specified as 6 planes). The reasoning behind this representation of 6 planes is that we can use it with non axis-aligned boxes, and boxes of odd shapes such as view frustums (which was my original application). When constructing these planes it is important to ensure all the plane normals face outward.

The test for if a sphere is inside a box is easy. Just check that the sphere is inside all of the face planes.

bool sphere_inside_box(sphere s, box b) {
  if (!sphere_inside_plane(s, b.front))  { return false; }
  if (!sphere_inside_plane(s, b.back))   { return false; }
  if (!sphere_inside_plane(s, b.top))    { return false; }
  if (!sphere_inside_plane(s, b.bottom)) { return false; }
  if (!sphere_inside_plane(s, b.left))   { return false; }
  if (!sphere_inside_plane(s, b.right))  { return false; }
  return true;

The intersection test, our original goal, is a little harder. For each face we check if there is an intersection, and if there is an intersection we ensure it is within the region of the face. To do this we ensure it is inside (or at least intersecting) all the surrounding face planes.

bool sphere_intersects_box(sphere s, box b) {
  bool in_left   = !sphere_outside_plane(s, b.left);
  bool in_right  = !sphere_outside_plane(s, b.right);
  bool in_front  = !sphere_outside_plane(s, b.front);
  bool in_back   = !sphere_outside_plane(s, b.back);
  bool in_top    = !sphere_outside_plane(s, b.top);
  bool in_bottom = !sphere_outside_plane(s, b.bottom);
  if (sphere_intersects_plane(s, b.top) && 
    in_left && in_right && in_front && in_back) {
    return true;
  if (sphere_intersects_plane(s, b.bottom) && 
    in_left && in_right && in_front && in_back) {
    return true;
  if (sphere_intersects_plane(s, b.left) &&
    in_top && in_bottom && in_front && in_back) {
    return true;
  if (sphere_intersects_plane(s, b.right) &&
    in_top && in_bottom && in_front && in_back) {
    return true;
  if (sphere_intersects_plane(s, b.front) &&
    in_top && in_bottom && in_left && in_right) {
    return true;
  if (sphere_intersects_plane(s, b.back) &&
    in_top && in_bottom && in_left && in_right) {
    return true;
  return false;

Once we have these tests, checking if a box is outside is as simple as ensuring it is not inside or intersecting.

bool sphere_outside_box(sphere s, box b) {
  return !(sphere_inside_box(s, b) || sphere_intersects_box(s, b));

It may seem more expensive but really it is only a handful more dot products and conditionals which the compiler can hopefully optimize away nicely. I feel like capturing the logic and making it clear is more important. Hope this helps any of you who were in my situation!

github twitter rss