Jump to content
  • Advertisement

Archived

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

Floating

Tightest bounding box

This topic is 5570 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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
Let''s see, somewhere around here I have a book... Here it is, Real-time Rendering and it say, hum, use the eigen vectors of the covariance matrix. Perhaps it just isn''t something to worry about.

Share this post


Link to post
Share on other sites
How is a covariance matrix for a mesh defined?

I know what a covariance matrix for a set of variables {x1, x2, .... , xn} is, but I wouldn''t know what to do if the xi were vertices.

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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!