8

What's the easiest way of doing this? I fail at math, and i found pretty complicate formulaes over the internet... im hoping if theres some simpler one?

I just need to know if a sphere is overlapping a cube, i dont care about which point it does that etc.

I'm also hoping it would take advantage of the fact that both shapes are symmetric.

Edit: the cube is aligned straight in the x,y,z axises

Newbie
  • 1,143
  • 5
  • 20
  • 30
  • 1
    If you don't post the complicated ones, how can we know if we have a simpler one? – Puppy Jan 02 '11 at 15:21
  • Well, i thought you could make up some simple formula on top of your head. but if you cant, then i dont think its possible to make it simpler than the complicated ones i found... – Newbie Jan 02 '11 at 15:25
  • Likely the complications are mostly due to considering the potential orientations of the cube. If the faces of the cube are parallel to coordinate planes, then the ideas are pretty simple to explain. In your case is the orientation of the cube variable? – hardmath Jan 02 '11 at 15:34
  • oh, i forgot to mention that fact as well, so the cube indeed isnt rotated at all, sides are always going straight in the x,y,z axises – Newbie Jan 02 '11 at 15:35
  • @Newbie, do you want to know whether cube and sphere intersect, or if cube is completely inside the sphere? – Dialecticus Jan 02 '11 at 15:52
  • @Dialecticus: yes, i want to know if sphere "touches" cube in any way. – Newbie Jan 02 '11 at 16:02
  • By the way, in case you ever have to contend with mathematicians, to them (well, us), a "sphere" is what civilians call "the surface of a sphere", and a "ball" includes the volume in the middle (the so-called "inside" of the sphere). It's only relevant here because in that terminology, a cube of side 1 intersects with the *ball* of radius 1 and the same centre, but doesn't intersect with the *sphere* of the same radius and centre, because the cube is entirely in the inside. – Steve Jessop Jan 02 '11 at 18:10
  • @Steve: hence my answer saying "assume both objects are solid". – Ben Voigt Jan 02 '11 at 18:38

3 Answers3

25

Jim Arvo has an algorithm for this in Graphics Gems 2 which works in N-Dimensions. I believe you want "case 3" at the bottom of this page: http://www.ics.uci.edu/~arvo/code/BoxSphereIntersect.c which cleaned up for your case is:

bool BoxIntersectsSphere(Vec3 Bmin, Vec3 Bmax, Vec3 C, float r) {
  float r2 = r * r;
  dmin = 0;
  for( i = 0; i < 3; i++ ) {
    if( C[i] < Bmin[i] ) dmin += SQR( C[i] - Bmin[i] );
    else if( C[i] > Bmax[i] ) dmin += SQR( C[i] - Bmax[i] );     
  }
  return dmin <= r2;
}
Gabe
  • 1,081
  • 2
  • 11
  • 16
24

Looking at half-spaces is not enough, you have to consider also the point of closest approach:

Borrowing Adam's notation:

Assuming an axis-aligned cube and letting C1 and C2 be opposing corners, S the center of the sphere, and R the radius of the sphere, and that both objects are solid:

inline float squared(float v) { return v * v; }
bool doesCubeIntersectSphere(vec3 C1, vec3 C2, vec3 S, float R)
{
    float dist_squared = R * R;
    /* assume C1 and C2 are element-wise sorted, if not, do that now */
    if (S.X < C1.X) dist_squared -= squared(S.X - C1.X);
    else if (S.X > C2.X) dist_squared -= squared(S.X - C2.X);
    if (S.Y < C1.Y) dist_squared -= squared(S.Y - C1.Y);
    else if (S.Y > C2.Y) dist_squared -= squared(S.Y - C2.Y);
    if (S.Z < C1.Z) dist_squared -= squared(S.Z - C1.Z);
    else if (S.Z > C2.Z) dist_squared -= squared(S.Z - C2.Z);
    return dist_squared > 0;
}
Ben Voigt
  • 277,958
  • 43
  • 419
  • 720
  • what does C1,C2,S mean? i assume R = radius of the sphere? – Newbie Jan 02 '11 at 15:39
  • `x = C1.X` is the left-most face of the cube, C2.X is the right-most face, C1.Y is the bottom-most face, C2.Y is the top-most face, C1.Z is the farthest face, C2.Z is the nearest face. S.{X, Y, Z} are the coordinates of the center of the sphere. – Ben Voigt Jan 02 '11 at 15:42
  • what is the initial value of `dist`? its not declared there – Newbie Jan 02 '11 at 15:50
  • I think OP wants to know if cube is inside sphere, not the other way around. – Dialecticus Jan 02 '11 at 15:50
  • @Dialecticus: no, i want to know if a sphere is overlapping cube – Newbie Jan 02 '11 at 15:50
  • @Newbie: Sorry, `dist` was just a typo for `dist_squared`. – Ben Voigt Jan 02 '11 at 18:35
  • cool, got this working, is this the most optimal way of calculating it? it looks very quick code... – Newbie Jan 02 '11 at 20:04
  • I would also expect it to run very quickly, since there are no slow operations such as sqrt needed. I believe it is optimal for this particular case (solid cube and sphere, with cube faces perpendicular to the axes) – Ben Voigt Jan 02 '11 at 21:03
  • Perhaps you wouldn't mind adding an equivalent code in Taxicab (Manhattan) metric? – user1 Oct 17 '14 at 02:11
  • 1
    @mr_jigsaw: Simply change `squared` to `abs`. I think. – Ben Voigt Oct 17 '14 at 03:44
  • You're right. That's what I did in the first place but my program didn't work. But it turned out that I had a mistake somewhere else. – user1 Oct 17 '14 at 08:34
-1
// Assume clampTo is a new value. Obviously, don't move the sphere
closestPointBox = sphere.center.clampTo(box)

isIntersecting = sphere.center.distanceTo(closestPointBox) < sphere.radius

Everything else is just optimization.

Wow, -2. Tough crowd. Ok, here's the three.js implementation that basically says the same thing word for word. https://github.com/mrdoob/three.js/blob/dev/src/math/Box3.js

intersectsSphere: ( function () {

    var closestPoint;

    return function intersectsSphere( sphere ) {

        if ( closestPoint === undefined ) closestPoint = new Vector3();

        // Find the point on the AABB closest to the sphere center.
        this.clampPoint( sphere.center, closestPoint );

        // If that point is inside the sphere, the AABB and sphere intersect.
        return closestPoint.distanceToSquared( sphere.center ) <= ( sphere.radius * sphere.radius );

    };

} )(),
Samuel Danielson
  • 5,231
  • 3
  • 35
  • 37