# Bounding sphere

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

## Recommended Posts

Best/Fastest way to get an aproximation of minimum bounding sphere of a point set?

##### Share on other sites
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 on other sites
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 on other sites
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 on other sites
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 on other sites
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 on other sites
@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 on other sites
Thanks haegarr.
This solution is not optimal, but still it's very tight. From my experience this usually proves to be more than enough.

##### Share on other sites
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) {}boolBoundingSphere::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 on other sites
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.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 14
• 11
• 28
• 15
• 39
• ### Forum Statistics

• Total Topics
634838
• Total Posts
3019547
×