f



bounding boxes

Hi everyone!

    I'm looking for a good explanation of minimal bounding boxes 
creation. I found some mathematical papers f.e. at 
www.magic-software.com, but they're a little bit too tough. Please, help 
if you know any other.

    regards

    - m z -

0
ISO
2/10/2004 1:12:56 PM
comp.graphics.api.opengl 7074 articles. 1 followers. Post Follow

4 Replies
569 Views

Similar Articles

[PageSpeed] 18

"Micha�" <firewire1@wp.pl> schrieb im Newsbeitrag
news:c0algb$nkn$1@nemesis.news.tpi.pl...
> Hi everyone!
>
>     I'm looking for a good explanation of minimal bounding boxes
> creation. I found some mathematical papers f.e. at
> www.magic-software.com, but they're a little bit too tough. Please,
help
> if you know any other.
>
>     regards
>
>     - m z -
>

minmax[0][xyz] = min box-coords
minmax[1][xyz] = max box

for (i =0; i< max_vertices; i++)
{
 if (i==0)
{
  minmax[0][0] = vert[0][0];
  minmax[0][1] = vert[0][1];
  minmax[0][2] = vert[0][2];
  minmax[1][0] = vert[0][0];
  minmax[1][1] = vert[0][1];
  minmax[1][2] = vert[0][2];
}
else
{
   minmax[0][0] = min(vert[0][0], minmax[0][0]);
   minmax[0][1] = min(vert[0][1], minmax[0][1]);
   minmax[0][2] = min(vert[0][2], minmax[0][2]);
   minmax[1][0] = min(vert[0][0], minmax[1][0]);
   minmax[1][1] = min(vert[0][1], minmax[1][1]);
   minmax[1][2] = min(vert[0][2], minmax[1][2]);
}

}

Was that your question?
-- 
-Gernot

Post here, don't email. If you feel you have to mail, revert my
forename from:
tonreG.Frisch.at.Dream-D-Sign.de@invalid.com
________________________________________
Looking for a good game? Do it yourself!
GLBasic - you can do
www.GLBasic.com




0
Gernot
2/10/2004 1:49:59 PM
maybe he means abritary bounding boxes and not axis aligned, but axis
aligned is surely the way to do it right and in less time ;)

"Gernot Frisch" <Me@Privacy.net> schrieb im Newsbeitrag
news:c0anlk$14hhhl$1@ID-37212.news.uni-berlin.de...
>
> "Micha�" <firewire1@wp.pl> schrieb im Newsbeitrag
> news:c0algb$nkn$1@nemesis.news.tpi.pl...
> > Hi everyone!
> >
> >     I'm looking for a good explanation of minimal bounding boxes
> > creation. I found some mathematical papers f.e. at
> > www.magic-software.com, but they're a little bit too tough. Please,
> help
> > if you know any other.
> >
> >     regards
> >
> >     - m z -
> >
>
> minmax[0][xyz] = min box-coords
> minmax[1][xyz] = max box
>
> for (i =0; i< max_vertices; i++)
> {
>  if (i==0)
> {
>   minmax[0][0] = vert[0][0];
>   minmax[0][1] = vert[0][1];
>   minmax[0][2] = vert[0][2];
>   minmax[1][0] = vert[0][0];
>   minmax[1][1] = vert[0][1];
>   minmax[1][2] = vert[0][2];
> }
> else
> {
>    minmax[0][0] = min(vert[0][0], minmax[0][0]);
>    minmax[0][1] = min(vert[0][1], minmax[0][1]);
>    minmax[0][2] = min(vert[0][2], minmax[0][2]);
>    minmax[1][0] = min(vert[0][0], minmax[1][0]);
>    minmax[1][1] = min(vert[0][1], minmax[1][1]);
>    minmax[1][2] = min(vert[0][2], minmax[1][2]);
> }
>
> }
>
> Was that your question?
> --
> -Gernot
>
> Post here, don't email. If you feel you have to mail, revert my
> forename from:
> tonreG.Frisch.at.Dream-D-Sign.de@invalid.com
> ________________________________________
> Looking for a good game? Do it yourself!
> GLBasic - you can do
> www.GLBasic.com
>
>
>
>


0
Christian
2/10/2004 3:32:44 PM
"Micha�" <firewire1@wp.pl> wrote in message
news:c0algb$nkn$1@nemesis.news.tpi.pl...
>     I'm looking for a good explanation of minimal bounding boxes
> creation. I found some mathematical papers f.e. at
> www.magic-software.com, but they're a little bit too tough. Please, help
> if you know any other.

The concept is simple to visualize.  Given three axis directions
U0, U1, and U2 (unit-length, mutually orthogonal), project your
vertices onto those axes.  For example, t*U0 is the line with the
specified direction where t is any real number.  The projection
of the vertices generates two extreme points, min0*U0 and
max0*U0; that is, if p*U0 is a projected vertex, then
min0 <= p <= max0.  Similarly define min1, max1, min2, and
max2.  The smallest box with these axes and containing the
vertices has center
  C = 0.5*(min0+max0)*U0 + 0.5*(min1+max1)*U1 + 0.5*(min2+max2)*U2
The lengths of the sides of the box are (max0-min0)/2, (max1-min1)/2,
and (max2-min2)/2.

There are infinitely many ways to choose the three axis directions,
each choice producing a box as described.  The problem is to
select the axes that produces the *minimum volume* box.  This is
the hard part.   My code uses three angles to parameterize the
axis directions.  The code uses a numerical minimizer that searches
the three-dimensional space of angles to find those angles that lead
to a minimum volume.  This method is "iterative" in the sense that
you keep searching until some convergence criteria are met.

It is sufficient to compute the minimum volume box containing the
convex hull of the vertices.  A "combinatorial" approach is based on:
    J. O'Rourke,
    Finding minimal enclosing boxes,
    Internat. J. Comput. Inform. Sci.,
    volume 14, pp. 183-199, June 1985.
Such a box has either (1) a face coincident with a face of the
convex hull or (2) three edges coincident with three edges of
the convex hull (necessarily the edges are orthogonal).  This allows
you to exhaustively search for the minimum volume box with a
guaranteed finite number of steps.  In case (1), for each face you
project the convex hull onto the plane of the face to get a convex
polygon.  The method of rotating calipers can be used to quickly
compute the bounding rectangle of the projection.  The axes of
this rectangle and the normal to the face form the 3D box axes.
In case (2), given three orthogonal edges, the projection method
I described above allows you to compute the volume.

All in all, you are hoping for a "trivial" algorithm for computing the
minimum volume box.  As is the case with many algorithms in
graphics that are conceptually easy to visualize, a conceptually
easy implementation does not exist.  Sorry to disappoint you...

--
Dave Eberly
eberly@magic-software.com
http://www.magic-software.com
http://www.wild-magic.com


0
Dave
2/10/2004 3:34:12 PM
Dave Eberly wrote:

>"Micha�" <firewire1@wp.pl> wrote in message
>news:c0algb$nkn$1@nemesis.news.tpi.pl...
>  
>
>>    I'm looking for a good explanation of minimal bounding boxes
>>creation. I found some mathematical papers f.e. at
>>www.magic-software.com, but they're a little bit too tough. Please, help
>>if you know any other.
>>    
>>
>
>The concept is simple to visualize.  Given three axis directions
>U0, U1, and U2 (unit-length, mutually orthogonal), project your
>vertices onto those axes.  For example, t*U0 is the line with the
>specified direction where t is any real number.  The projection
>of the vertices generates two extreme points, min0*U0 and
>max0*U0; that is, if p*U0 is a projected vertex, then
>min0 <= p <= max0.  Similarly define min1, max1, min2, and
>max2.  The smallest box with these axes and containing the
>vertices has center
>  C = 0.5*(min0+max0)*U0 + 0.5*(min1+max1)*U1 + 0.5*(min2+max2)*U2
>The lengths of the sides of the box are (max0-min0)/2, (max1-min1)/2,
>and (max2-min2)/2.
>
>[...]
>All in all, you are hoping for a "trivial" algorithm for computing the
>minimum volume box.  As is the case with many algorithms in
>graphics that are conceptually easy to visualize, a conceptually
>easy implementation does not exist.  Sorry to disappoint you...
>
>--
>Dave Eberly
>eberly@magic-software.com
>http://www.magic-software.com
>http://www.wild-magic.com
>
>  
>

Thanks for explanation, it gives me a lot. Now I see it much better.
The problem is, I don't understand math text in english good enough and 
I usually stuck into this kind of elaboration.
I didn't expect trivial algorithm, but easy enough explanation of how it 
works. Thanks again, you helped me a lot.

    regards

    - m z -

0
ISO
2/12/2004 10:35:24 AM
Reply: