I'm working on implementing Welzl's algorithm for finding the minimal bounding sphere of a set of vertices. I'm getting some pretty huge bounding spheres though, which can't be right. I'm thinking that something must be wrong with how I'm calculating my sphere from either 3 points or from 4 points (possibly both are wrong). As far as I can tell, there's 4 different ways to build a sphere:
sphere from 1 point: Center is point, radius is 0
sphere from 2 points: Center is midpoint, radius is half distance
sphere from 3 points: I use this method:
Sphere::Sphere( Vector& p1, Vector& p2, Vector& p3 )
{
Vector v23 = p2 - p3;
Vector v13 = p1 - p3;
Vector v12 = p1 - p2;
Vector v21 = p2 - p1;
Vector v31 = p3 - p1;
Vector v32 = p3 - p2;
float denominator = ( 2 * ( v12.CrossProduct(v23).Length() * v12.CrossProduct(v23).Length() ) );
float alpha = ( (v23.Length() * v23.Length()) * (v12.DotProduct(v13)) ) / denominator;
float beta = ( (v13.Length() * v13.Length()) * (v21.DotProduct(v23)) ) / denominator;
float gamma = ( (v12.Length() * v12.Length()) * (v31.DotProduct(v32)) ) / denominator;
center = alpha * p1 + beta * p2 + gamma * p3;
radius = ( v12.Length() * v23.Length() * v31.Length() ) / ( 2 * v12.CrossProduct(v23).Length() );
}
I've tried several methods for the 4 point sphere, here's the one that I've settled on:
4 point sphere method
Now when I expand a sphere, I take the support set (all points currently used to define the sphere, always less than 5) and the new point and test all possible permutations of the support set and the new point to find the minimal sphere. For instance, if my support set has 4 vertices then I first try all two point combinations of the support set and the new point, then all 3 point combinations and finally all 4 point combinations. I then replace/remove any necessary points from the support set and add the newpoint to the support set. I'm 99% sure that the logical flow of my algorithm is right, I believe I just have some grievous math error somewhere in my Sphere calculation routine.
Are there any better ways to calculate a minimal bounding sphere from 3 or 4 points?
Thank you.
Edit: Also, on the off chance that anyone needs to see my sphere calculation functions in order to help:
Full Sphere Calculation Functions