Tightest bounding box
Author
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
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.
Author
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?
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?
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.
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.
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.
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?
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?
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]
[edited by - LilBudyWizer on March 18, 2003 9:33:38 AM]
Author
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?
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?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
