Having a little issue calculating the bounding sphere radius

Question

I have managed to calculate the bounding sphere radius in two ways, but none is giving me exactly what I want. I don't need a "pixel" perfect bounding sphere but I would like something better than what I currently have.

I'm using Wavefront .obj models and to calculate the bounding sphere radius for those models I extract the current model dimensions (I'm using the GLM library from Nate Robbins) which will give me the dimension on each axis.

First approach: Divide each axis by 2 and that will give me the radius on each axis. The largest is the one I'll use for my bounding sphere. This will work for most objects specific to my project. It will not work for some, like cube-shaped ones. Basically, if I have a cube and calculate the radius with this approach, the sphere will leave the cube corners outside.

Second approach: Divide each axis by 2 and that will give me the radius on each axis. Then I do this to take out the radius for the bounding sphere:

r = SQRT(x*x + y*y + z*z)

But this gives me a pretty large radius. The object will be totally enclosed in the sphere but the sphere is pretty large, more than it should be.

I don't understand what I'm doing wrong in the formula above, as far as I know it, it should work. But I'm obviously wrong...

For a cube or a box your second approach gives you the exact bounding sphere radius. Thus there is no better approach using only the dimensional extents per axis. — Howard, May 21 '11 at 17:28

Theran · Accepted Answer · 2011-05-21T18:51:24.400

Your second approach should give you the bounding sphere for your bounding box, but as you discovered, it will be larger than necessary for anything other than a box.

A better bounding sphere can be found by translating the model points so they're centered on the origin using the bounding box dimensions you already have, then for each individual vertex calculate the radius from the origin for that point using the sqrt(x*x + y*y + z*z) formula. Whichever of those is the largest is the radius of your bounding sphere.

Note that this won't be the optimal bounding sphere. For that you'd have to find the convex hull of your model and use something like rotating calipers to pick the optimal center point for the sphere.

To show it in 2D, the red outline is the bounding box of the shape, and the blue circle is the bounding circle of the box. The improved circle using the polygon vertices, and centered on the box is green. Note that none of the points of the black polygon touch the blue circle.

polygon (black), bounding box (red), bounding circle of the poly (green), bounding circle of the box (blue)

I understand it will be larger than necessary but shouldn't at least one point of the object "touch" the sphere somewhere? Cause none of them "touches", they all are way off, and I understand why... — rfgamaral, May 21 '11 at 17:53
For instance, let's think in 2D. If I have a rectangle of 4x2, the radius will be `SQRT(2*2 + 1*1)`. Drawing a circle inside the rectangle will have the rectangle's corners touch the circle. Shouldn't it be the same in 3D? — rfgamaral, May 21 '11 at 18:00

score 1 · Answer 2 · answered May 21 '11 at 18:35

1

One easy way would be to use Miniball to calculate the exact bounding sphere of the model. Integrating it into your project is hassle-free, as it only consists of a single header. It is licensed under the GPL however, which could be a problem. Example:

#include "Miniball.h"

// ...

Miniball<3> boundingSphere;

// Iterate over all vertices in the model
for (int vertexId = 0; vertexId < model.getNumVertices(); ++vertexId) {
  // Convert vertex position to Miniball point type
  Point<3> point;
  for (int dim = 0; dim < 3; ++dim) {
    point[dim] = model.getVertex(vertexId)[dim];
  }
  // Add point to bounding sphere
  boundingSphere.check_in(point);
}
// Actually calculate the sphere
boundingSphere.build();

// Get back the results
Point<3> center = boundingSphere.center();
double radiusSq = boundingSphere.squared_radius();

answered May 21 '11 at 18:35

reima

2,076
15
22

Thanks but I want to avoid using any more "libraries" and it's not really relevant that I have the exact bounding sphere. I just want to understand why my calculations are failing in the first place (or what I'm failing to understand). – rfgamaral May 21 '11 at 18:39
@Nazgulled: it is a well-known geometrical computation problem with known solution. Please see Wikipedia's [Bounding sphere problem](http://en.wikipedia.org/wiki/Bounding_sphere) article. – rwong May 21 '11 at 18:52
Here's another library for computing the miniball that is available under the Apache license: http://github.com/hbf/miniball – Hbf Mar 25 '13 at 07:25

score 0 · Answer 3 · answered May 21 '11 at 17:26

0

If it's a sphere, then don't you only need to work it out based on one axis? I might be way off here - but by definition, won't a sphere have the same width, height and depth? So radius on one axis=radius on another=radius of another?

answered May 21 '11 at 17:26

Joseph Redfern

939
1
6
13

Then why use sqrt(x*x + y*y + z*z) when you could just use 0.5*x? I might be missing something here. – Joseph Redfern May 21 '11 at 17:52
Because x!=y!=z. Or they might be equal, depends on the object. I need all the axises because the object could be really tall and thin for instance. And so I need to use the Pythagoras theorem. Maybe I'm the one missing something but that's the way I see. – rfgamaral May 21 '11 at 18:04

Having a little issue calculating the bounding sphere radius

3 Answers3

Linked