QuickHull and OrientedBBox

Hi Gorg,

I had a look how you compute the covariance matrix and I have a few questions:

  1. The covariance matrix shouldn’t depend on anything else than vertices if you want to get a tight bounding box. Why do you include triangle information in the calculation? Take a collection of points and find a tight bounding box. Now take the same collection of points and add some random triangles between these points (you don’t add more points). The bounding box should be the same as in the first calculation -> it doesn’t depend on triangle information.

  2. The way I compute the covariance matrix is:
    I compute the mean position of all vertices of my convex hull: mu[3]
    Then, for each vertice (p[3]) of my convex hull (c[3][3] which is the covariance matrix is initialized to zero):

for (i=0;i<n;i++)
{
float p[3];
p[0]=convHull[3i+0]; // x component of n-th vertice
p[1]=convHull[3
i+1]; // y component of n-th vertice
p[2]=convHull[3i+2]; // z component of n-th vertice
for (int j=0;j<3;j++)
for (int k=0;k<3;k++)
c[j][k]=c[j][k]+(p[j]-mu[j])
(p[k]-mu[k]);
}

for (j=0;j<3;j++)
for (int k=0;k<3;k++)
c[j][k]=c[j][k]/n;

  1. By computing it my way you can clearly see that the covariance matrix of a rotated cube is always diagonal. Where did I do a mistake?

  2. The bounding box one can compute is never the tightest because to compute the covariance in a exact way, one should need to know in advance the center ((max+min)/2) of the bounding box (that means with max and min computed along the axis of the bounding box). Since me don’t know it in advance, we compute the mean (mu) which is an approximation of the real center.
    What if we compute the bounding box in more than one passes?
    First pass: mu=mean position of all vertices of the convex hull
    Second pass: mu=center of the obtained bounding box (mu=(max+min)/2)
    Third pass: mu=center of the obtained bounding box

    I think that in that way we could find the tightest bounding box. What do you think?

Cheers,

Marc
(About your question: I implemented a incremental convex hull algorithm and when a point lies on a plane containing a triangle of my conv. hull, I just ignore it (I decide that it is just inside))

I got the covariance matrix from this paper.
http://www.cs.unc.edu/~geom/OBB/paper.html

You can look at the correct equation. But I do not use this equation, because for some reason, I cannot find the eigenvalues of the matrix created by it. So I use the formula from the Book Real-time rendering.

for the equations you use, if the convex hull you find happens to have a huge set of points in a corner, the bbox might get aligned with it and it means it might not be the correct orientation.

the equations I use try to resolve this by “weighting” the covariance with area of the triangles so that the box aligns with the longest triangles.

The explanation for using the triangle is not in the paper and I cannot find where I read it. hmm I am starting to doubt I ever did!! In that case, then I don’t why my equation or your equation is better.

[This message has been edited by Gorg (edited 06-04-2002).]

I was inspired by the same paper, but I don’t agree with their triangle “trick” (weighting with the triangles). I think it’s a “trick” (approximation) because it is impossible to get the main axis in one unique pass and that’s why I proposed a second pass (or more) to avoid the problem you mentioned (with a huge set of points in a corner…). In the second pass the “huge set of points” don’t weight anymore in the balance since we just take the (min+max)/2 along the axis found in the first pass.

When you say that you want your box to get aligned with the longest triangles… again, I have to say that triangles don’t matter at all in the calculation of the bounding box, only vertices matter (if all vertices are inside of the box, then all triangles are inside too).

Hum, I hope you can understand my poor explanation

I misread your last post where you proposed multiple passes. It seems it could work well, though I have to sit down and do some calculations and tests.

How well does it work for you for something else than a box?

I have tried to find an explanation for taking the area of the triangle. In the paper, it mention that a better way to calculate the covariance matrix is integrating over the surface of the triangle and then they give the integrated formula.

My guess is that the formula I used is a tweaked formula or simply modified formula of the integral.
But I could not find more details on the web.

Statistics is not my forte, so those things are starting to be out of my limited knowledge.

For something else than a box (with sizeX=sizeY=sizeZ), the results are what one expects: tight bounding boxes (at least they look tight).
I compared bounding boxes generated in one pass and in two passes (as I proposed) and the difference is really negligible for normal shapes (quite equilibrated). For heavily non-equilibrated shapes, the difference is also very small (I got an improvement of 3% with 2 passes). This surprised me a bit.

About your question if a point lies on the plane of a triangle of your convex hull… I think I missunderstood you. What I do is:
If the point lies inside or on that plane, fine.
If the point lies outside of that plane, I remove the triangle associated with that plane and all other triangles of the convex hull which are in the same plane (triangles in the same planes are tagged with a same identifier). By doing so I don’t get overlapping triangles in my convex hull (because of precision errors). Then I close the hull with the new point and the edges resulting from the triangles removal.
In your quickhull implementation (I implemented it in an incremental algogithm) it might be a bit more difficult to implement I guess…

[This message has been edited by Mr.Freeze (edited 06-05-2002).]

I believe you will find this interesting :

I tried your method, just the first pass, and I got the exact same boxes. the difference in eigenvectors were usually in the second or third decimal place or they were simply scaled.

So I believe it is actually the same technique, but my version uses an interface where the convex hull comes described in triangles instead of only points(or the triangle contains indexes to the points).

As for the small difference you see when you use 2 or 3 passes, I not sure if it suprising or not, because for most of the models they are actually quite close. But I don’t really know how to interpret what you see.

[This message has been edited by Gorg (edited 06-05-2002).]

[This message has been edited by Gorg (edited 06-05-2002).]

Now I understand… :

First I used to compute the bounding box out of a collection of vertices which were not filtered by the convex hull function (I was too lazy to implement it ). That’s why I didn’t use the proposed method in the paper. But up until now (even after implementing the convex hull function) I somehow kept in mind that my bounding box function should work with any kind of vertices… My fault m(__)m. Sure, if you weight your triangles of your convex hull, it’s perfectly correct!

Well, this one’s over!

Hey guys,

that is exactly what I’m looking for at the moment. But the link on the first site is down… :frowning:
Gorg, maybe you can upload the code somewhere for me? Or can someone else provide the software? That would be great!

Thanks!
Flo