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 |

2/10/2004 1:12:56 PM

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

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 |

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 |

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 |

2/12/2004 10:35:24 AM