Tuesday, December 1, 2009

Full hull

Today I was scouting around for a decent convex hull generator. It's quite surprising to me that such a clearly defined task still doesn't have a de facto standard implementation that everybody uses. I just wanted one for computing the visualization meshes, so performance is not even critical.

I looked into a couple of different ones that had clean interfaces. This one looked promising due to its simplicity, but after trying just a few point clouds it crashed on me. Convex hull generation is tricky that way "Oh, how hard can it be, just split that triangle, merge those two, test for that plane, blah blah" and then when you sit down and implement it there are all these degenerate cases, and you can't really make assumptions about anything. Our convex hull generator at Meqon was a constant pain in the ass for three years. I don't think we ever got it right. Qhull seems to be very robust, but a) it's a huge mess, b) it has a ton of features you don't want and c) it has a somewhat questionable license.

James Dolan kindly pointed me to an implementation written by my former colleague Stan Melax for a physics exporter. John Ratcliff then wrapped it up, gave it the name "stanhull" and posted it on his code suppository. It took me five minutes to integrate, it works like a charm, it has a great interface, no dependencies and it's fast. Look no more and cheers to Stan.

I have also contemplated to do an automatic visualization of implicit convex hulls using only the support function. Not that it would be super-useful, but still pretty cool to use the same code for visualizing all types of convex objects. A naive approach would be to sample the support function in a ton of different directions and just build a hull of the resulting points, but I've been thinking about a more intelligent subdivision method to avoid sampling crazy many directions and still not miss corners. Might try it tomorrow.


No comments:

Post a Comment