Sign in to follow this  
Promag

Bounding sphere

Recommended Posts

dmatter    4826
fastest way: define the radius yourself

Alternatively you could do a pre-process and ensure that the first point in the set is the maximum point.

Or a general and simple solution is to iterate through all points and find the one farthest away from the center, this would give an exaxt fitting sphere. You could just check one point for every every 2 or for every polygon to get an approximation.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Try using google with phrases like "bounding sphere" and "point set" to find some pointers to good algorithms. It seems there is an exact algorithm with expected linear time complexity, and some good approximations with linear time complexity.

There is no best way because you don't indicate what you need this for. If you are precalculating the bounding sphere, it would make sense to calculate it exactly. If you were calculating it frequently, then the question arises of how accurate it needs to be. If the points were moving and the sphere had to be recalulated, then it may be possible to calculate an approximate sphere faster by knowing what the old sphere was.

Share this post


Link to post
Share on other sites
Promag    132
Well its a static model so its a pre-calculated sphere. After reading some googled stuff i found a O(n) algorithm witch gives an 5% aproximation error (Pretty nice).

Anyway, this problem is something like resolving the equation:

r(O) = max { distance(O,v) : p in P } , r = sphere radious, O = sphere center, P = point set

here the O must be one that gives the minimum r(O).

So what numerical algorithm should I use to resolve it?!

Share this post


Link to post
Share on other sites
haegarr    7372
The problem in computing the bounding sphere is not to compute the radius but the center. If the center is known then computing the radius is like

float maxDistance = 0;
for( vertex = firstVertex(); vertex != 0; vertex = nextVertex() ) {
distance = squaredDistance( vertex - center );
if( distance > maxDistance ) {
maxDistance = distance;
}
}
radius = sqrt( maxDistance );


The method simply iterates through all vertices and computes the distance of the vertex from the center of the sphere. (Using the squaredDistance here is sufficient since the function is monotonic.) The square root of the maximum distance is the wanted radius.

This piece of code fulfills the
r(O) = max { distance(O,v) : p in P } , r = sphere radious, O = sphere center, P = point set

[Edited by - haegarr on November 29, 2005 4:27:21 AM]

Share this post


Link to post
Share on other sites
ury    476
Here's the code that I use:

void BoundingSphereFromPoints( VECTOR& vCenter, FLOAT& fRad, PVECTOR pPoints, UINT nNumPoints )
{
assert( nNumPoints );

if ( !nNumPoints )
return;

// Compute a bounding box
VECTOR vMin( pPoints[0] ),
vMax( vMin );

for ( UINT i = 1; i < nNumPoints; ++i )
{
const VECTOR& vPnt = pPoints[ i ];

vMin = vMin.Min( vPnt );
vMax = vMax.Max( vPnt );
}

// Compute the sphere
FLOAT fRadSq, fRadNew, fLen;
VECTOR vDiff;

vCenter = (vMin + vMax) * 0.5f;
fRad = 0.5f * (vMax - vMin).MaxScalar();
fRadSq = SQR( fRad );

for ( i = 0; i < nNumPoints; ++i )
{
const VECTOR& vPnt = pPoints[ i ];

vDiff = vPnt - vCenter;
fLen = vDiff.LengthSq();
if ( fLen > fRadSq )
{
fLen = __Sqrt( fLen );
fRadNew = (fRad + fLen) * 0.5f;
vCenter += vDiff * ((fRadNew - fRad) / fLen);

fRad = fRadNew;
fRadSq = SQR( fRad );
}
}
}



Notice that the first for-loop approximates the bounding sphere using an AABB.
The result might not contain the entire point set, so this is where the second for-loop kicks in. If a certain point is not contained within the sphere, the shere is refined by adjusting both it's position and radius.

Share this post


Link to post
Share on other sites
haegarr    7372
@ury: Fine solution. Does a proof exists whether this solution results in an optimum w.r.t. a sphere with the lowest possible volume (or at least how good it is)? I've though formerly of a similar solution (not starting with a BB approximation but clustering all points in sequence) but have dropped it since I thought it wouldn't be good enough...

Share this post


Link to post
Share on other sites
ury    476
Thanks haegarr.
This solution is not optimal, but still it's very tight. From my experience this usually proves to be more than enough.

You can read about optimal solutions here.

Share this post


Link to post
Share on other sites
haegarr    7372
To those who are interested in (and especially ury :-)

This is my "full clustering" solution. It is, as already mentioned earlier, similar to ury's solution but does not have a "preprocessing" step.

BoundingSphere::BoundingSphere()
: _center(Point3_t::ZERO),
_radius(-1),
_squaredRadius(-1) {}

bool
BoundingSphere::consider(const Point3_t& point) {
// classifying the point (initially _sqRadius is -1, so that the first candidate is ever classified as an outlier)
const Point3_t difference(_center,point);
scalar_t distance = difference.squaredNorm2(); // in fact the squared distance
const bool isOutlier = distance > _squaredRadius;
// if the point is an outlier the volumes geometry must be adapted ...
if(isOutlier) {
distance = XMath<scalar_t>::sqrt(distance);
// faking on the first point ...
if(_radius<0) {
// due to this little trick the newRadius will become 0, and the center will be translated by 1 multiple of
// the difference vector from Point3_t::ZERO on, so yielding in the point as center of a sphere w/ radius 0
_radius = -distance;
}
// computing the new radius to include the sphere so far as well as the outlier
const scalar_t newRadius = (_radius+distance)*0.5f;
// shifting the sphere "half-way" towards the outlier
if(distance) {
_center.add(difference,(newRadius-_radius)/distance);
}
// scaling the sphere
_radius = newRadius;
_squaredRadius = newRadius*newRadius;
}
// done
return isOutlier;
}


Here for clarity the points are to be provided one-by-one by invoking BoundingSphere::consider(point). The XMath is just a selector for the appropriate functions in dependence of scalar_t, what is either float or double.

When providing 4 points (0,0,0), (10,0,0), (0,0,10), and (0,10,0) in differing orders, the resulting spheres are:
[ 2.399498 1.318533 3.140984 ] x 9.538934
[ 3.140984 2.399498 1.318533 ] x 9.538934
[ 1.318533 2.399498 3.140984 ] x 9.538934
[ 3.140984 1.318533 2.399498 ] x 9.538934

EDIT: The volume depends in both the center as well as the radius from the order in which points are supplied.

[Edited by - haegarr on November 29, 2005 12:22:44 PM]

Share this post


Link to post
Share on other sites
vNistelrooy    140
According to Jack Ritter a near-optimal sphere can be created by:
1) Finding the minimal and maximal vertices along each axis (x,y,z).
2) For those three pairs chose the one pair which has the largest distance.
3) The center of the sphere is the midpoint between those two vertices and its radius is half the distance between them.
4) Go through all vertices again, if you find a vertex whose distance (d) is greater than the radius (r), move the sphere towards this vertex by (d-r)/2 and then set the new sphere radius to (d+r)/2.

Share this post


Link to post
Share on other sites
haegarr    7372
Quote:
Original post by vNistelrooy
According to Jack Ritter a near-optimal sphere can be created by:
1) Finding the minimal and maximal vertices along each axis (x,y,z).
2) For those three pairs chose the one pair which has the largest distance.
3) The center of the sphere is the midpoint between those two vertices and its radius is half the distance between them.
4) Go through all vertices again, if you find a vertex whose distance (d) is greater than the radius (r), move the sphere towards this vertex by (d-r)/2 and then set the new sphere radius to (d+r)/2.

Yep. That is exactly the algorithm ury has posted above. (Although it is not clear whether AABB or OOBB is meant in 1.)

It is a clustering solution with a pre-processing step for an approximated initial volume. One could say that the full clustering solution uses the first vertex as initial volume. As seems to be with any clustering, the solution depends on the order in which the vertices are supplied. Due to the pre-processing step the probability of having outliers is reduced, so that Ritter's algo is in the mean more stable w.r.t. to the resulting volumes.

Share this post


Link to post
Share on other sites
ury    476
haegarr, another issue with not performing a pre-processing step is performance.

The pre-processing step makes sure that most of the points will be inside the resulting sphere. This means that you won't have to perform the refining step for most of the points. (No costly square roots or vector math)

Share this post


Link to post
Share on other sites
haegarr    7372
@ury: I know, but thanks for the hint.

My implementation of BoundingSphere has just now get another routine

void
BoundingSphere::presetFrom(const BoundingBox& box) {
// setting center to COG of the box
_center.set(box.minimum()).add(box.maximum()).multiply(0.5f);
// setting radius to the half of the maximum difference
_radius = box.maximumExtent()*0.5f;
_squaredRadius = _radius*_radius;
}


You see, I'm willing to learn ;-)

However, speed is not my only concern, since I'm working on a model editor as well (its a special purpose editor for supplementing paper modelling). So I'm sometimes interested in speed, and sometimes in precision, and hence also will try to look at the link you've provided. The class (or at least a derived class) will implement several ways, so that the running app has a possibility of choice.

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