Sign in to follow this  

Minimal containing sphere for a set of spheres?

This topic is 4074 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

Simple question, but I can't seem to figure out the answer. Basically, given a set of spheres defined by their centers and radii, determine the center and radius of the minimal volume sphere that completely contains all of these spheres. How should I go about doing this? The radius is pretty easy to do once I have the center, but I'm not sure how to determine the optimal center point. This isn't homework. I was originally doing this because I wanted to figure out the bounding sphere for a model, given the bounding spheres of all its submeshes. I determine the center of the sphere there from the combined AABB of those submeshes, since I had per-submesh and total AABBs anyway. Then I just get the final radius from the individual bounding spheres. But I'm still curious about the more general case of the problem, where you have been given just the spheres. It seems like a fairly interesting problem to deal with.

Share this post


Link to post
Share on other sites
why couldn't you just average all the centers of the set of spheres? Then find the longest distance between any two spheres, and that's the definition of you're best-fit bounding sphere.

Share this post


Link to post
Share on other sites
It's easy, look at softsurfer.net and you'd see IIRC three algorithms. You can have fast algorithm, or precisse algorithm choose.

I use bounding boxes, because they are less wastefull.

Share this post


Link to post
Share on other sites
Quote:
Original post by Morpheus011
why couldn't you just average all the centers of the set of spheres? Then find the longest distance between any two spheres, and that's the definition of you're best-fit bounding sphere.


Because it's not the guaranteed minimum enclosure :)

There was an article on Game Programming Gems II (or 1?) about a dynamic sphere tree. There was code there to calculate what you are looking for.

Share this post


Link to post
Share on other sites
One solution might be to find the enclosing sphere for all midpoints of the spheres (by finding the longest distance between to sphere midpoints) and then intersect all the spheres with the enclosing sphere. If an intersection exists you can extend the radius of the enclosing sphere by the amount of the diameter of the testet sphere minus the overlap with the enclosing sphere.

Share this post


Link to post
Share on other sites

This topic is 4074 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this