Sign in to follow this  
HalcyonX

Constructing bounding spheres

Recommended Posts

HalcyonX    130
Im trying to construct bounding spheres for arbitrary polyhedrons, and so far, ive found 3 ways to do it: 1. Use the average of all the verticies as the center, and then loop through the verticies to find the longest radius. 2. Construct an AABB, and use its center as the center of the sphere, then find the longest radius as in #1. 3. Use Welzl's algo, which i dont fully understand yet (By the way, does anyone know of a place that has a clear explanation of it?). I found some code online that compares methods #1 and #3based on execution time and radius when ran on a set of random points, and modified the code to add in method #2 too. #2 turned out the fastest, followed by #1, with #3 being the slowest (taking about 3-4 times longer that #2). But #3 always gave a small radius, while #1 and #2 had roughly the same radii. So im wondering, how big of a radius-length advantage does Welvl's algo give over the other 2 methods? Is it worth the extra execution time? I plan on constructing the spheres on the fly every frame, since my objects change quite often.

Share this post


Link to post
Share on other sites
JohnBolton    1372
#2 is generally the best in terms of speed and efficiency (as you determined). It is fast and the result is usually close to optimal.
#1 has some problems -- for example a cone would give bad results because the center of the bounding sphere would be near the base.
#3 gives the optimal answer, but it is slow.

As for which is the best for your application ... there is only one way to find out.

Share this post


Link to post
Share on other sites

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