Cube-Sphere intersection
Author
Hi, I've been trying to write some collision detection methods for an application I'm writeing. I am really stuck, however, on cube-sphere intersections. I cannot actually think of how to find the intersection, let alone program it.
I get the feeling i need to find the plane that represents the face of the cube, but do I? And if i have that, what do i use it for? I would think i would then find the (shortest) distance from the sphere centre to the face of the plane (not sure how to do that) then compare it to the raidus.
Can anyone lend a hand? I haven't had much luck googling this and any results i have in books are very convoluted.
http://www.siggraph.org/education/materials/HyperGraph/raytrace/rtinter0.htm
read through this stuff and you may get a feeling for this.
read through this stuff and you may get a feeling for this.
Transform the coordinate system so the cube (or cuboid) is axis aligned (not as hard as it sounds, just find where the centre of the sphere is in terms of its three basis vectors). Then it's a sphere-AABB collision test, which is fairly easy (find the closest point in each of the three dimensions, then check that you're within the sphere's radius).
Author
thanks for the replies guys, but there are still some things i'm not sure about.
for the source Eitsch supplied, the methods rely on having an initial ray. I would imagine this ray should be the vector that defines the shortest distance between the centre of the sphere and the plane. Is there a method to find this? (surley it can't just be vector-plane, since there is the D element to consider?)
thanks for that, but can you explain what you mean by sphere-AABB collision test? I think finding the closest point also falls under the problem i'm having with eitsch's method.
for the source Eitsch supplied, the methods rely on having an initial ray. I would imagine this ray should be the vector that defines the shortest distance between the centre of the sphere and the plane. Is there a method to find this? (surley it can't just be vector-plane, since there is the D element to consider?)
Quote:Original post by Bob Janova
Transform the coordinate system so the cube (or cuboid) is axis aligned (not as hard as it sounds, just find where the centre of the sphere is in terms of its three basis vectors). Then it's a sphere-AABB collision test, which is fairly easy (find the closest point in each of the three dimensions, then check that you're within the sphere's radius).
thanks for that, but can you explain what you mean by sphere-AABB collision test? I think finding the closest point also falls under the problem i'm having with eitsch's method.
Is that just for intersections? THen it's quite easy. All you need to do is find the closest opint on the box to the sphere centre, and check if that point is at a distance (squared) fronm the sphere centre. That's usually how intersection with spheres work (plane, segment, triangle, box, convex hull, wahtever!).
to find the closest point, first with an AABB
with that point, then you check if it is withing the sphere range or not.
with an oriented box, it's quite similar. You can use the transpose orientation matrix, or do it by hand, which is really the same.
I think something like that should do it.
inside tells you if the point was found to be inside the box. This is important, because is the sphere is much smaller than the box, then the closest point might not be inside the sphere, and yet the sphere and the box intersect.
to find the closest point, first with an AABB
Vector ClosestPointOnBox(const Vector& Point, const Vector& Centre, const Vector& Extent, bool& inside){ Vector Delta = (Point - Centre); inside = true; if (fabs(Delta.x) > Extent.x) { inside = false; Delta.x = Extent.x * sign(Delta.x); } if (fabs(Delta.y) > Extent.y) { inside = false; Delta.y = Extent.y * sign(Delta.y); } if (fabs(Delta.z) > Extent.z) { inside = false; Delta.z = Extent.z * sign(Delta.z); } // point was found outside. all good. if(!inside) { return Centre + Delta; } // point was found inside. Find which face is closest to our point. if (fabs(Delta.x) < fabs(Delta.y)) { Delta.y = 0.0f; if (fabs(Delta.z) < fabs(Delta.x)) Delta.x = 0.0f; else Delta.z = 0.0f; } else { Delta.x = 0.0f; if (fabs(Delta.z) < fabs(Delta.y)) Delta.y = 0.0f; else Delta.z = 0.0f; } return Centre + Delta;}with that point, then you check if it is withing the sphere range or not.
with an oriented box, it's quite similar. You can use the transpose orientation matrix, or do it by hand, which is really the same.
Vector ClosestPointOnOrientedBox(const Vector& Point, const Vector& Centre, const Vector& Extent, const Matrix33& Orientation, bool& inside){ Vector Delta = (Point - Centre).MultiplyByTransposeMatrix(Orientation); inside = true; if (fabs(Delta.x) > Extent.x) { inside = false; Delta.x = Extent.x * sign(Delta.x); } if (fabs(Delta.y) > Extent.y) { inside = false; Delta.y = Extent.y * sign(Delta.y); } if (fabs(Delta.z) > Extent.z) { inside = false; Delta.z = Extent.z * sign(Delta.z); } // point was found outside. all good. if(!inside) { return Centre + Delta.MultiplyByMatrix(Orientation); } // point was found inside. Find which face is closest to our point. if (fabs(Delta.x) < fabs(Delta.y)) { Delta.y = 0.0f; if (fabs(Delta.z) < fabs(Delta.x)) Delta.x = 0.0f; else Delta.z = 0.0f; } else { Delta.x = 0.0f; if (fabs(Delta.z) < fabs(Delta.y)) Delta.y = 0.0f; else Delta.z = 0.0f; } return Centre + Delta.MultiplyByMatrix(Orientation);}I think something like that should do it.
inside tells you if the point was found to be inside the box. This is important, because is the sphere is much smaller than the box, then the closest point might not be inside the sphere, and yet the sphere and the box intersect.
If the box is solid, then if the center of the sphere is inside the box then the sphere and the box intersect.
Doublebuck, what are you trying to do in the case that the center of the sphere is inside of the box? That part of your code doesn't make much sense to me...I think you meant to find the closest point on the box to the sphere, assuming the box is not solid (that it only exists at its boundary), but it doesn't look right.
Doublebuck, what are you trying to do in the case that the center of the sphere is inside of the box? That part of your code doesn't make much sense to me...I think you meant to find the closest point on the box to the sphere, assuming the box is not solid (that it only exists at its boundary), but it doesn't look right.
Yeah, that's gone slightly wrong, isn't it.
// point was found outside. all good. if(!inside) return Centre + Delta; // find the MTD. Delta.x = (Extent.x - fabs(Delta.x)) * sgn(Delta.x); Delta.y = (Extent.y - fabs(Delta.y)) * sgn(Delta.y); Delta.z = (Extent.z - fabs(Delta.z)) * sgn(Delta.z); // point was found inside. Find which face is closest to our point. if (fabs(Delta.x) < fabs(Delta.y)) { Delta.y = 0.0f; if (fabs(Delta.z) < fabs(Delta.x)) Delta.x = 0.0f; else Delta.z = 0.0f; } else { Delta.x = 0.0f; if (fabs(Delta.z) < fabs(Delta.y)) Delta.y = 0.0f; else Delta.z = 0.0f; } return Point + Delta;}
If you don't do the last part, the algorithm will return the centre of the sphere as being the closest point. That can be sufficient, but usually, you want to be able to resolve the intersection, and find the point on the surface of the box helps more than return nothing.
Author
thanks for the replies guys!
for finding the closest point on the surface of the cube to the sphere, how would i do that? should i find the planes defining the faces of the cube, then check for ray-plane intersections with the ray between cube and sphere centre, and the planes? sorry if i'm coming accross as a bit rubbish, but i don't want to waste time because i've missunderstood something.
for finding the closest point on the surface of the cube to the sphere, how would i do that? should i find the planes defining the faces of the cube, then check for ray-plane intersections with the ray between cube and sphere centre, and the planes? sorry if i'm coming accross as a bit rubbish, but i don't want to waste time because i've missunderstood something.
For finding the closest point on the surface of the cube to the sphere you should try to understand DoubleBuck's code, which does exactly that. The way to represent a box in this case is with the box's center and the distance from the center to each of its sides (the extents). There are only three extents because the box is symmetric about its center. If the box is a cube, then you only need one extent since the value is the same for all six sides. If the box is not axis aligned, then you also need to have the orientation of the box, which is also handled in one of DoubleBuck's code examples.
The method works by taking advantage of the symmetries of a box and a sphere. Note that the method is slightly different depending on if the center of the sphere is inside or outside of the box. Doublebuck's code handles both cases, but depending on what you are using it for you might only need one or the other.
The method works by taking advantage of the symmetries of a box and a sphere. Note that the method is slightly different depending on if the center of the sphere is inside or outside of the box. Doublebuck's code handles both cases, but depending on what you are using it for you might only need one or the other.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
