I have a mesh, I want to find the smallest possible bounding sphere that
encompasses all the points. I know this is a colossal combinatorial problem
and to test every possible bounding sphere were talking about an algorithm
that runs in O(k*(k-1)^2*(k-2)^3*(k-3)^4) time, which is completely
unreasonable even for small meshes. I did some reading into the subject, but
all I could find was a bit of really poorly documented code and a couple of
brief mentions of Welzl's algorithm for computing bounding volumes. Anyone
have any thoughts on a method of finding this? so far I have two possible
solutions, but neither of them are super accurate. I've been pondering
heuristic methods, I know how they work but I really and truly do not have
any idea as to how I might go about implementing them.

Solution 1:

#declare Centre = <0, 0, 0>;
#declare i = 0;
#while(i < Pts)
    #declare Centre = Centre + Point[i];
    #declare i = i + 1;
#end

#declare Centre = Centre / Pts;

#declare Radius = 0;
#declare i = 0;
#while(i < Pts)
    #if(vlength(Points[i] - Centre) > r)
        #declare Radius = vlength(Points[i] - Centre);
    #end
    #declare i = i + 1;
#end

Solution 2:

#declare Centre = (min_extent + max_extent) / 2;

#declare Radius = 0;
#declare i = 0;
#while(i < Pts)
    #if(vlength(Points[i] - Centre) > r)
        #declare Radius = vlength(Points[i] - Centre);
    #end
    #declare i = i + 1;
#end

--
Kevin
http://www.geocities.com/qsquared_1999/
#macro _(r)#if(r<12)#local i=asc(substr("oqshilacefg",r,1))-97;
disc{<mod(i,7)-3,div(i,7)-1,6>,z,.4pigment{rgb 10}}_(r+1)
#end#end _(1)//KL

Post a reply to this message