In article <3e11c6bb$1@news.povray.org>,
 "Apache" <apa### [at] yahoocom> wrote:

> I'm not sure if that will lead to the smallest sphere possible, because the
> rotation of the bounding box will matter a lot. If the rotation is wrong,
> the bounding box will be too big and so will be the sphere.

It isn't even close, the sphere will be very "loose" in almost every 
case. It will only be minimal if the object touches the bounding box at 
two opposite corners and the box is a perfect cube. It might work well 
as a first approximation, though. I haven't done any research on it, but 
here's what I'd try:

Calculate the sphere enclosing the box.

Compute the minimum radius required to contain all points.

There will now be at least one point on the sphere. Go to the step with 
the number of contacting points:

1: Move the sphere toward the contact point, reducing radius to keep it 
on the sphere surface, until one other point is on the surface.

2: The same as step 1, but move toward the midpoint of the two existing 
points.

3: The 3 points define a triangle. Do the same thing as the first two 
steps, but toward a point in the triangle that is equidistant from all 3 
points.

4: Stop. The sphere is pretty tight, maybe the best possible.

There are probably mathematical solutions for all of these steps, but it 
might be easier to do it iteratively, moving the sphere in small steps 
or doing a binary search.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message