Archived

This topic is now archived and is closed to further replies.

Floating

Tightest bounding box

Recommended Posts

Hi, I need to find a tight fitting bounding box for my objects (oriented bounding box). What I do is compute the covariance matrix from the vertices composing the convex hull of my mesh. With that matrix I can then find the eigenvectors which give me the direction of my bounding box. That''s fine, except when my mesh is a cube. My covariance matrix for my cube is always the identity matrix, whatever the orientation of my cube is. Of course I don''t get a tight fitting bounding box. So my question: how can I handle objects like my cube and find it''s orientation? Thanks

Share this post


Link to post
Share on other sites
First I suck at statistics. So I may be wrong about what a 2nd order covariance matrix is. Higher order is specified by two values. That is the power on the terms that you are taking the product of. If you square both you get a semmetric matrix, i.e. (x-mx)^2*(y-my)^2 = (y-my)^2*(x-mx)^2. Without any doubt if you square those terms you will get differant covariance matrices depending upon the rotation of the cube. Right now you get a diagonal matrix with the variance of each component on the diagonal. I have no idea what it is going to do to your bounding box. If squaring both doesn''t work try squaring one. It should be a relatively minor coding change so it doesn''t cost much to try it and see what happens.

Share this post


Link to post
Share on other sites
Thank you LilBudyWizer,

I tried what you suggested but it is not working...
If I think of a 0 centered 2*2*2 cube, I can''t imagine how I could get a non-diagonal matrix. Maybe there is another way?

Share this post


Link to post
Share on other sites
Nevermind, I found some paper by Gottschalk, Lin and Manocha in some Siggraph proceedings.

For the cube you describe with vertices at (-1,-1,-1) ... (1,1,1) I get the following covariance matrix

C = [1 1/9 1/9; 1/9 1 1/9; 1/9 1/9 1]

without using the convex hull. I have no idea whether this is correct or not.

What made you think you can''t get a non-diagonal covariance matrix?

Share this post


Link to post
Share on other sites
There is no linear correlation between the variables. So anything not on the diagonal should be zero. Any line through the center of a square fits the points of a square just as well as any other line. With a cube the same is true for planes and lines. The same would be true for a geodesic dome. Just using covariance for 2d points at the corner of a square you get 1*1, -1*1, 1*-1 and -1*-1 which sums to zero. If you rotate the square you get differant product terms, but they still sum to zero.

[edited by - LilBudyWizer on March 18, 2003 9:33:38 AM]

Share this post


Link to post
Share on other sites
sQuid: I programmed my tight bounding boxes based on the same paper. However I don''t make the calculations with each triangles as proposed, but with each vertex (which works well for any shape except for cubes). Anyways the covariance matrix should be the same for a cube:

From Gottschalk''s paper:

MU = sum(Pi+Qi+Ri)/3n

Cjk=sum((Pij-MUj)(Pik-MUk)+(Qij-MUj)(Qik-MUk)+(Rij-MUj)(Rik-MUk))/3n

What I do:

MU = sum(Pi)/n

Cjk=sum((Pij-MUj)(Pik-MUk))/n

Which should give the exact same result, no?

LilBudyWizer: If I understood your last post correctly, you mean that a cube gives the same covariance matrix as a sphere: orientation independant? At least this seems to be true according to my calculations. But there must be a way, no?

Share this post


Link to post
Share on other sites
I think it is really just an oddity. I don''t think it is a real problem. Why would the cube be rotated in it''s local coordinate system? This "problem" causes you to always generate an axis aligned bounding box, but it seems in practice that is most likely what you are going to want.

Share this post


Link to post
Share on other sites
The problem is that the user can create/import/edit shapes which might not be axis-aligned. I want my imported cube (in fact the application doesn''t know it is a cube) to get a tight fitting bounding box, whatever orientation it has.

Share this post


Link to post
Share on other sites
I think the "triangulation" as they put it might be important.

If we consider a square centred on the origin then the mean μ = (0,0) and the covariance matrix is always diagonal. If you triangulate the square then two of the corners get counted twice in that formula they give and you start to see the proper orientation of the eigenvectors. (try it for the two squares { (1,1), (1,-1), (-1,-1), (-1,1)} and { (sqrt(2),0), (0,-sqrt(2)), (-sqrt(2),0), (0,sqrt(2)) }

If by "triangulation" in 3 dimensions they mean tetrahedrons then this might work for a cube. They seem quite focused on triangles though so I really don''t know what they are talking about.

Have you tried emailing one of the authors?

Share this post


Link to post
Share on other sites
As near as I can tell (xy*xz*yz)^2/(xx*yy*zz)^2 will tell you your degree of confidence in the method. I think for three variables it is the equivalent of the correlation coefficent for two variables. If the value is near zero then the orientation you get has very little to do witht the distribution of the data.

If think if you repeat the vertices for each triangle it is part of then you tend to align with the diagonal. As an example with the covariance matrix you gave above one of the eigen vectors is a diagonal for the cube given. Aligning with a diagonal is the worst fit for the cube.

[edited by - LilBudyWizer on March 19, 2003 1:48:29 AM]

Share this post


Link to post
Share on other sites
I also tried to compute the bounding box as described in the paper, but the results were not as good as with the ''simplified'' way (taking the vertices only): for a 1*2*3 rectangle the result is an approximate bounding box. The simplified method gives me a perfect bounding box! I am aware that the method described in the paper is an approximation and will not give exact results unless you integrate over each triangle''s surface (given a convex hull).
I guess I''ll have to try this sooner or later...

Anyway, thanks a lot LilBudyWizer and sQuid

Share this post


Link to post
Share on other sites