Promag 132 Report post Posted November 27, 2005 Best/Fastest way to get an aproximation of minimum bounding sphere of a point set? 0 Share this post Link to post Share on other sites
dmatter 4826 Report post Posted November 27, 2005 fastest way: define the radius yourselfAlternatively 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. 0 Share this post Link to post Share on other sites
Guest Anonymous Poster Report post Posted November 27, 2005 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. 0 Share this post Link to post Share on other sites
Promag 132 Report post Posted November 28, 2005 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 sethere the O must be one that gives the minimum r(O).So what numerical algorithm should I use to resolve it?! 0 Share this post Link to post Share on other sites
haegarr 7372 Report post Posted November 29, 2005 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 ther(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] 0 Share this post Link to post Share on other sites
ury 476 Report post Posted November 29, 2005 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. 0 Share this post Link to post Share on other sites
haegarr 7372 Report post Posted November 29, 2005 @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... 0 Share this post Link to post Share on other sites
ury 476 Report post Posted November 29, 2005 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. 0 Share this post Link to post Share on other sites
haegarr 7372 Report post Posted November 29, 2005 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.538934EDIT: 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] 0 Share this post Link to post Share on other sites
vNistelrooy 140 Report post Posted November 29, 2005 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. 0 Share this post Link to post Share on other sites
haegarr 7372 Report post Posted November 29, 2005 Quote:Original post by vNistelrooyAccording 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. 0 Share this post Link to post Share on other sites
ury 476 Report post Posted November 29, 2005 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) 0 Share this post Link to post Share on other sites
haegarr 7372 Report post Posted November 29, 2005 @ury: I know, but thanks for the hint.My implementation of BoundingSphere has just now get another routinevoidBoundingSphere::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. 0 Share this post Link to post Share on other sites