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.

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!