Sign in to follow this  
lol

is this a good way to calculate a bounding sphere?

Recommended Posts

I have been working on a 3d game engine for about a month now, and am planning on adding frustum culling. To acocmplish this I need to be able to calculate the bounding sphere of a model. I always assumed that the best way to do this is to loop through each vertex, figure out which one is farthest from the center of the model, and use the magnitude of it as the radius. In pseudocode:
[source lang = 'not a real language']


float radius = 0

for each frame f in model
{
     for each vertex v in f
     {
          float magnitude = sqrt(v.x * v.x + v.y * v.y + v.z * v.z)//this is assuming that the center of the model is at (0, 0, 0)

          if (magnitude > radius)
               radius = magnitude
     }
}

BoundingSphere s = new BoundingSphere(model.position, radius)

[/SOURCE]
[/source] However, everytime I look this up on the internet, they have much more complicated algorithims (such as this one), and in Beginning OpenGL Game Programming, they went for a more confusing approach that they admit isnt always right:
[source lang = 'C']

// this is a bit of a hack, since the sphere isn't guaranteed to completely

// surround the model. However, the results for this demo are satisfactory

void CalculateBoundingSphere(sphere_t &sphere, GLfloat miny, GLfloat maxy)

{

  sphere.center.x = 0;

  sphere.center.y = (maxy + miny) / 2.0f;

  sphere.center.z = 0;

  sphere.radius = maxy - sphere.center.y + SPHERE_PADDING;

}

[/SOURCE]
[/source] my question is: is my algorithim (which merely uses the magnitude of the point farthest from the center of the model as a radius) correct, or is this not a good way to calculate bounding spheres? Thanks in advance for your help and advice.

Share this post


Link to post
Share on other sites
Quote:
//this is assuming that the center of the model is at (0, 0, 0)

If you can make that assumption, the process is trivial. You usually can't make that assumption.

Share this post


Link to post
Share on other sites
A simple method such as yours is sufficient to create a non optimal (i.e. not the smallest) bounding sphere.

For example, if your object consisted of a single vector at 100,100,100, then your sphere would enclose a lot of space not actually enclosing your object.

If your object had three points at {90,100,100}, {100, 100, 100} and {110, 100, 100} then a sphere at 100,100,100 or radius 10 would be much more efficient than a sphere at 0,0,0 of radius 110.

Other methods can be used to calculate an optimal bounding sphere though obviously will be more complicated. This is fine if you will pre-calculate the sphere ouside of run-time (e.g. in you object conversion tool), but may take up neccesary processor time if done during your game's run time.

The advantage of using an optimal sphere in you're collsion code is that you are more likely to calculate a 'cheap' miss than with a non-optimal sphere.

Share this post


Link to post
Share on other sites
To get the optimal bounding sphere, what you need to do is find four such vertices in your model that are on the surface of such a sphere that all of the other vertices are on or inside it. You could go through all of the combinations of four vertices, but that's kind of slow. There's a better algorithm, but unfortunately I can't remember what it was. Google for optimal bounding sphere.

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