# Bounding Sphere construction

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

## Recommended Posts

Hello all!

Bounding Spheres!!

I have a decision to make regarding bounding spheres, I though I would put it out there to get some thoughts on the matter as I am making things up as I go as usual.

Basically I am considering two options.

a) Have the bounding spheres centred around the origin, and if a model isn't suited to this then tough cheddar.
b) Centre the sphere at the centroid of the object.

There are other options but these are the two I am considering..

Am I a wally for even considering a)?

The problem comes from when working with the spheres... which I am quite a bit, the one centred around the origin is much easier and faster to work with given that I don't have to transform the sphere into world space... as it by default always is. It only needs to be scaled if the model is.

This then is very fast and simple, the centre of the sphere is the same as its position always.

If the sphere's centre can be anywhere, then every time I use it; it will have to be transformed by the local to world matrix (at least I think it will) am I wrong?

Is there a better way to handle this?

Is the speed of the 1st approach enough to ignore the potential inaccuracy of its volume?

FYI I am programming in as3 for flash so I need every ounce of performance gain I can... large amounts of math will bring the engine to its knees in no time.. speed speed speeeeed.

Thanks for any input

##### Share on other sites
I was trying this at oene point and did a fair bit of reading around to figure out how. Its surprisingly complicated, I saw some nice 2d apps with code doing some of the algorithms but trying to get it to 3d was hard. In the end it wasn't all that impornant for me so I didn't go for it.

I would go for B, center it around the object and make sure its large enough to fit all the vertices in. thats still a fair bit of processing, particulally if your objects are complex (its pretty much just a brute force search). It will not be an ideal fit either but if its good enough when you use it, then its good enough.

##### Share on other sites

I would go for B, center it around the object and make sure its large enough to fit all the vertices in. thats still a fair bit of processing, particulally if your objects are complex (its pretty much just a brute force search). It will not be an ideal fit either but if its good enough when you use it, then its good enough.

thanks! I already got a couple of implementations that work well for both approaches. So I know I can build the spheres easily enough... its just deciding if the tightness of the centred sphere is worth the additional transformations whenever I want to use it.

##### Share on other sites
Finding a minimal bounding sphere is easy. There is a trivial n^4 time algorithm for doing it, just search over all sets of tetrahedra over the convex hull of the object, take the smallest enclosing sphere of each tet, and then take the smallest one that includes all points. There are also the special cases for the situation where the bounding sphere is determined by two and 3 points respectively, though they follow similarly.

There are several much faster linear time algorithms, though you can just look those up on wikipedia: http://en.wikipedia...._circle_problem

##### Share on other sites
thanks again, but what I am really after is the PROS and CONS of bounding spheres around the origin vs around the centroid.

##### Share on other sites
You can preprocess your models to make the origin be the centroid, or even the center of the minimal bounding sphere. Then you'll get the best of both worlds.

##### Share on other sites

You can preprocess your models to make the origin be the centroid, or even the center of the minimal bounding sphere. Then you'll get the best of both worlds.

good thinking (dismissed it myself due to the trivial work required to shift all the verts by the offset haha am so lazy), the one drawback with this is that it may be confusing to the end user who loads a model and positions it only to find out its not where they thought it was...maybe that's too small an issue

may well go with that, could be the simplest solution

• 37
• 12
• 10
• 10
• 9
• ### Forum Statistics

• Total Topics
631362
• Total Posts
2999571
×