Skip to main content

Convex Hull Dilemma

As i haven't found any good function in 3D Studio Max to generate a convex hull, i had to do it on my own if i really wanted it. So i did do some research and stumbled over a nice java applet demonstrating various convex hull algorithms. Excellent!

I at least understand the java source code, so all i have to do is port da shit. It wasn't all too easy, as it needed quite some rewriting thanks to the OOP-unfriendly MaxScript, but finally i got it working.

And that way i found a problem with the algorithm implemented like this: The moment where four outside vertices are on the same plane and part of the hull, you run into the following problem: When you test one vertice against the other three wether he is "outside" and therefore part of the hull, he tests positive. Yet all the other four vertices do that too! So the code ends up looping through the edges of those four vertices for ever...

As the applet only creates random vertices to test and doesn't try geometrical primitives like for example boxes, this problem pretty much never occures. And the moment i shake up those quad-vertices, the algorithm works excellent.

I only tried gift-wrapping so far, so maybe the other algorithms don't have this problem, but my feeling is they do too... At least in some or the other way...

That means i have to adapt the algorithm for a more rigorous edge-filtering.