Bounding sphere
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.
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.
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.
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.
Author
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?!
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?!
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
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]
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]
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;<br><br> vMin = vMin.Min( vPnt );<br> vMax = vMax.Max( vPnt );<br> }<br><br> <span class="cpp-comment">// Compute the sphere</span><br> <span class="cpp-keyword">FLOAT</span> fRadSq, fRadNew, fLen;<br> VECTOR vDiff;<br><br> vCenter = (vMin + vMax) * <span class="cpp-number">0</span>.5f;<br> fRad = <span class="cpp-number">0</span>.5f * (vMax - vMin).MaxScalar();<br> fRadSq = SQR( fRad );<br><br> <span class="cpp-keyword">for</span> ( i = <span class="cpp-number">0</span>; i < nNumPoints; ++i )<br> {<br> <span class="cpp-keyword">const</span> VECTOR& vPnt = pPoints;<br><br> vDiff = vPnt - vCenter;<br> fLen = vDiff.LengthSq();<br> <span class="cpp-keyword">if</span> ( fLen > fRadSq )<br> {<br> fLen = __Sqrt( fLen );<br> fRadNew = (fRad + fLen) * <span class="cpp-number">0</span>.5f;<br> vCenter += vDiff * ((fRadNew - fRad) / fLen);<br> <br> fRad = fRadNew;<br> fRadSq = SQR( fRad );<br> }<br> }<br>}<br><br></pre></div><!–ENDSCRIPT–><br><br>Notice that the first for-loop approximates the bounding sphere using an AABB.<br>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.
@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...
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.
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.
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.
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]
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]
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
