Advertisement Jump to content
Sign in to follow this  
Winegums

Cube-Sphere intersection

This topic is 4349 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement
http://www.siggraph.org/education/materials/HyperGraph/raytrace/rtinter0.htm

read through this stuff and you may get a feeling for this.

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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?)

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.

Share this post


Link to post
Share on other sites
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



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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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;
}


Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!