Sign in to follow this  
bwhiting

Bounding Sphere construction

Recommended Posts

bwhiting    1562
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 this post


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


Link to post
Share on other sites
bwhiting    1562
[quote name='Nanoha' timestamp='1307005136' post='4818577']
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.
[/quote]



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 this post


Link to post
Share on other sites
robotichrist    193
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: [url="http://en.wikipedia.org/wiki/Smallest_circle_problem"]http://en.wikipedia...._circle_problem[/url]

Share this post


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

Share this post


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


Link to post
Share on other sites
bwhiting    1562
[quote name='alvaro' timestamp='1307112716' post='4819070']
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.
[/quote]


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

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