QuickHull and OrientedBBox

Offtopic, but some of you might be interested.

I just finished implementing the algorithm presented in Real-time rendering to calculate a tight fitting bounding box.

It uses quickhull to create the convex hull and then compute the covariance matrix and it’s eigenvectors to then find the OBB.

I tested it with all sorts of models and it looks pretty robust. If one of you ever use it and make it crash or throw, just send me the points you used.

You can pick it up here.
http://members.rogers.com/deseric/hullbbox.zip

I believe it is documented well enough(at least the convex hull part!). I know it compiles under gcc3.1, gcc3.0.4, and Borland 5.

MSVC++ users should only need to fix for-loop index variable repetitions.

Well, I hope it will be of use to someone.

I forgot to mention, the point list can contain duplicated points. So that way you just need to dump your vertices in a vector.

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

Thanks Gorg … that’s just the thing I was looking for.

> MSVC++ users should only need to fix for-
> loop index variable repetitions.

Put this in StdAfx.h (or some other always-included file, or maybe even on the command line):

#define for if(0); else for

This moves the variables declared in the scope of the for clause into the scope of the else clause, so they won’t leak out outside the end of the for.

As you know, you CAN turn off language extensions to make the for variable scoping be correct in MSVC. It’s a pity the Microsoft headers don’t compile correctly when you turn these off, though.

Originally posted by jwatte:
[b]> MSVC++ users should only need to fix for-
> loop index variable repetitions.

Put this in StdAfx.h (or some other always-included file, or maybe even on the command line):

#define for if(0); else for

This moves the variables declared in the scope of the for clause into the scope of the else clause, so they won’t leak out outside the end of the for.

As you know, you CAN turn off language extensions to make the for variable scoping be correct in MSVC. It’s a pity the Microsoft headers don’t compile correctly when you turn these off, though.[/b]

Yes it is a pity.
But I am not going to write a fix. I dont use MSVC so, I prefer to let people take the decision on the solution they want to use. Besides, Its only in one function anyway.

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

Cool, I have been wanting some code to do this. gg!

-SirKnight

I just uploaded a new version. I found some problems with highly tessaled models with very uniform distributio n of points(like a sphere of 60000 vertices ).

I added a scale to reduce floating point issue. If you ever get an exception that says “Found only trivial solution. Did you try to pass a plane”. Go in ConvexHull.cpp and raise the SCALE variable. For now it seems good.

As side effect, this changes make the algorithm find tighter bounding box because the coefficients of the covariance matrix are bigger.

And I also optimised the initialisation where the redundant points are removed. I got about a 25% speed up.
http://members.rogers.com/hullbbox.h

On a side notes, does anybody knows how to find a good hash value for floats? If I get that, I might be able to speed it up a little more.

I use hashing for building up a half-edge datastructure out of triangles. For this I have to find duplicate points fast. My hashing function is:

hVal = (unsigned int)fmod(fabs(100 * p.x() + 10000 * p.y() + 1000000 * p.z()), MESH_BUCKETS);

I use MESH_BUCKTES = 16381.

The problem with floats is only, that for one point you get 1.0000 and for the other you get 0.9999 for a coordinate. As I have a tolerance for which two coordinates are considered the same, I wrote a function to find a point in the hash table which searches the bucket which is returned by the hash function and also the bucket before and after this. But it’s still faster… I search three buckets instead all points.
After this I could read a 35 MByte STL Model into a half edge structure in 15 seconds instead of 5 Minutes!

Kilam.

[This message has been edited by Kilam Malik (edited 06-03-2002).]

Thank you Kilam. That’s much better than just hashing each float separatly.!!!

I have tried a few formula like that, but I got more chaining than I should and I could not find one the web.

update

Great I just implemented it with the hashing of point got another minor speed up.

I guess one day I do some key repartition tests, but for now it is good for me.

The new version is uploaded for anybody interested. This will be last version until a while(unless someone finds a way to break it),

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

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

Kilam Malik, could you explain the hashing in more depth? I just did some searches and they resulted in only descriptions of what it does and not how to do it. I’m not quite undertanding how the method works.

I need it to remove redundent vertices. A faster method than a modified balloon sort would be great.

Here’s my first question: what do you do with hVal?

I’m quite excited to know that there’s an algorithm out there that’s really fast compaired to my modified balloon sort.

I found this, but I don’t understand it: http://www.concentric.net/~Ttwang/tech/inthash.htm

I don’t know what to do with the Key, or even how to generate it.

Hi Grog,

I didn’t compile your code yet, but I have a question:
I just implemented the same thing a few days ago and it gives me the results I was expecting (tight fitted bounding boxes) except if the shape is a cube (xSize=ySize=zSize)… then the bounding box is randomly oriented and doesn’t tightly fit anymore. How did (if you did) you solve that problem?

Thanks,

Marc

(In case I try to get the convex hull of a planar shape, I just add an artificial point outside of the plane and compute the convex hull. Then I remove all triangles containing the added point. This gives me the convex planar shape)

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

WhatEver, just download my code and have look at ConvexHull.cpp.

Look for “PointHashTable”.

Mr.Freeze :

Not too be annoying but it’s Gorg grog sounds grouchy.

Anyway, for the cube. In that case the covariance matrix should be diagonal ==> all the values are 0 aside from those on the diagonal(which are the eigenvalues). If the matrix is diagonal, then the vector are simply ( i, j, k ) the standard basis.

This is true for all object with a symetrical distribution. So spheres and boxes fall in that category.

So before trying to compute the eigenvectors(which you cannot actually because if your matrix is diagonal then you get only the trivial solution(0,0,0)), I simply check if the matrix is diagonal or not.

I stupidly update a version where the hash table doesn’t have a prime number as a size. I updated the new version if anybody is interested.

Hopefully it will be the last time I update it for a while., I passed 5 consecutive days doing doing the #%$#!% implementation.

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

Thx Gorg! I will check that out asap!

Mr. Freeze, I forgot to mention : If you have a rotated cube, then your covariance matrix will not be diagonal and you will have to solve for the eigenvalues and eigenvectors.

And everythings comes down to how you do that. If you actually test my code with a rotated box, you will see that OBB it finds is slightly off. This is because of the errors caused by finding the eigenvectors. I find the error very small so I don’t really care. You can try it and see for yourself I guess.

If you want to know this how I find the eigenvectors.

  1. CreateCovariance Matrix
    2a. If matrix is diagonal, assign i,j,k to eigenvectors.
    and we are done
    2b. Find the characteristic polynomial. Solve it. This gives you the eigenvalues. Now solve the 3 following system. If the eigenvalues are e1,e2,e3

(e1 * I - A)v = 0

The nice thing about our matrices, is that they always have 3 eigenvectors.

Now this is a 3x3 system. 2x2 are much more easier to solve. So we do a trick where we set one the component of v to 1. This might change the results of the true eigenvectors by a scale only, so you will still get the correct vectors.

Which component you set to 1. Well any that is not really 0!! a component will really be 0 if all coefficient of this component in the matrix are 0.

So in my code I simply check if x can be 1. So I look for mat[0][0] != 0 | | mat[0][1] != 0 | | mat[0][2] != 0.

If all the coefficients of X are zero, then I check those of Y. If they are all 0, then I check for those of Z. If they are all 0 I quit, because it means you can only find the trivial solution.

But if you found a correct convexhull, this should never happen and you should always find one of the coordinate to set to 1.

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

Marc alias Mr. Freeze

About you planar shapes. this will not give you 3d hull will it?

I guess you could take the remaining triangles and change their winding and offset them by a bit… hmm.

Anyway, I don’t support or plan to support planar meshes anyway, but I will keep it in my mind if I ever need to.

WhatEver : Comment of the Insert function is wrong. It should say “return true if the point is inserted and false if the point was already inserted”. But I guess you can figure this out by yourself

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

Gorg,

Sorry for my wrong spelling of your name…

About the rotated cube, well, I guess there must be a subtle mistake in my code and I don’t get the correct bounding box. But any other rectangle (where sizeX!=sizeY!=sizeZ!=sizeX) works perfectly fine as for other shapes… ?!? I’ll have a look at your code
But basically I compute it the exact same way as you.

My convex hull routine doesn’t really return the convex hull of a planar shape, just it’s corresponding planar convex shape, but as you said, from there the hull is quickly found.

Cheers,

Marc

the best advice I can give you is to output the matrices and eigen values and eigen vectors for each case. (normal cube and rotated cube) and check the difference.

And If you spot anything that can be improved in my code, please let me know.

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

Gorg,

it seems very strange to me that for a rotated cube you don’t get a diagonal matrix for the covariance matrix.
I checked and check, and I always get a diagonal matrix with a cube… ??

Marc

I get a symetric matrix(like in all case pretty much) but it is not diagonal. Which is normal, Otherwise the only possible eigenvectors would be i,j,k and this is obviously not correct for a rotated cube.

I have a question about your quickhull implementation. What do you do when a point is directly on the plane of the triangle?

What I currenttly do is say that it’s outside. And if it ever gives me degenerate triangles, I just don’t create then when filling the hole.