Box to Sphere Collision

I need to check if a box is colliding with a sphere. I have a BoundingBox class defined with x, y, z, width, height, depth. I also have a BoundingSpher开发者_运维问答e class defined with x, y, z, radius. How to I check to see if they intersect?

The first thing to check is if the BoundingBox for the BoundingSphere intersects. The reason for this is that it's a very simple way to rule out the more complicated math involved.

The next step would be to take each of the six planes (or twelve triangles) of the bounding box and do a distance from point to polygon test on them to the center of the sphere. If one of them is less than the radius of the sphere, then you have a hit.

Matlab code for polygon-to-point-distance: http://www.mathworks.com/matlabcentral/fileexchange/12744-distance-from-a-point-to-polygon

If you want to keep the test at the level you described, you can place a bounding box around the sphere where width, height, and depth = 2r. Of course, this admits the risk of false positives for collisions at "non-polar" or "non-equatorial" points on the sphere. To solve that, you might consider building a series of hierarchical bounding boxes to increase the granularity of hit tests in these problems regions.

You might also approach the problem from a rendering level. Since you cannot render a sphere, some sort of polygonal mesh is commonly used. Hit tests between 2D (or 3D) polygons is a straightforward exercise.

There's a chapter in Graphics Gems by Jim Arvo.

I guess the stale link above used to point to his code as there's "arvo" in the URL. This link works - at least right now.

There is a simple and cheap way to construct the coordinates of the point on the box that is closest to the center of the sphere (I discuss how to do this below). If the distance to the closest point is bigger than the radius, then the box and the ball intersect. Otherwise they do not intersect.

Let

• r = radius of sphere
• c = (x_sphere, y_sphere, z_sphere) = center of sphere
• b_min = (x_box, y_box, z_box) = box "min" point
• b_max = (x_box + width, y_box + height, z_box + depth) = box "max" point.
• p = closest point on box to center of the sphere (we want to find p)

The closest point on the box to the sphere center can be constructed componentwise (pseudocode):

for i=1,2,3:

if              c[i] < b_min[i]   then   p[i] = b_min[i]
if   b_min[i] < c[i] < b_max[i]   then   p[i] = c[i]
if   b_max[i] < c[i]              then   p[i] = b_max[i]

if p[1]^2 + p[2]^2 + p[3]^2 < r^2 then the box intersects the ball
otherwise the box doesn't intersect the ball

In python this can be written as follows:

import numpy as np

# r is a float, and c, b_min, b_max are numpy vectors
def box_intersects_ball(r, c, b_min, b_max):
    p = c.copy()
    p[c < b_min] = b_min[c < b_min]
    p[c > b_max] = b_max[c > b_max]
    return (np.linalg.norm(p - c) <= r)

Note that this actually works for boxes/spheres in any dimensional space, 2d, 3d, 4d, 100d, whatever.

To see why this gives the closest point, let p be the point defined by the method shown above, and let q be any other point in the box. If q differs from p in the i'th coordinate, replacing q[i] with p[i] will make q get closer to p, because |q[i]-c[i]| gets smaller while |q[j]-c[j]| remains the same for all other coordinates j not equal i. In other words, p must be the closest point in the box to c, because any other point in the box can be made closer to c by modifying it.

Note 1: here I am assuming that the x,y,z coordinates you have for the box are in the lowermost corner in all dimensions.

Note 2: I am assuming that the box and sphere are "solid" not "hollow".

You just have to check all the corners of the bounding box against the distance from the center of the sphere. Here's some pseudocode:

bool collidesWith(BoundingBox b, BoundingSphere s) {
  for(Vertex v in b) {
    if(distanceBetween(v, s.center) <= s.radius)
      return true;
  }
  return false;
}