In article <3DFF8126.37A7E1BE@hotmail.com>,
 Dan Johnson <zap### [at] hotmailcom> wrote:

> I think you are right.  I don't think it would be too hard to make a
> macro to do that either.  Now I guess the next thing is to find the
> smallest oriented bounding box, and see which one is smaller.  If one is
> always smaller.  

I am almost certain the box is always smaller. The optimal sphere 
bounding is a circumscribed sphere around a regular tetrahedron. The 
optimal box bounding of that tetrahedron would have each corner of the 
tetrahedron at a corner of the box, the least optimal (I think) would 
have two edges of the tetrahedron against opposing faces of the box, 
parallel to different axii (the best case, rotated 45 degrees around one 
axis).

For a regular tetrahedron with 1-unit edges, the best bounding sphere 
has a radius of sqrt(3)/sqrt(8) (~0.612), the best-case box a 
2/sqrt(8)-unit (~0.707) cube, the worst-case box a 1x1x2/sqrt(8) 
(1x1x~0.707) box. The sphere has a volume of 0.96 units^3, the cube 
0.353 units^3, and the box 0.707 units^3.

For optimal bounding of irregular tetrahedrons, both will be less 
efficient, but I think a box will always be better. Even if the 
tetrahedron is a thin rod along a diagonal of the box (the worst case), 
the sphere will have a larger volume (having a diameter about equal to 
the length of the diagonal of the box).

This is for axis-aligned boxes, if you use oriented boxes the bounding 
of a regular tetrahedron or some irregular tetrahedrons (those you can 
get by applying an affine transformation to a regular tetrahedron) is 
always the best case, for other tetrahedrons it still improves.

-- 
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