It turns out that QuickHull is a fairly involved algorithm due to numerical imprecision and the difficulties of representing a 3D form effectively in code. In order to account for numerical issues, planes and faces have to be represented with thickness, which adds some complexity to basic math operations. But more importantly, (robust) 3D QuickHull implementations have to handle 3D traversal and manipulation of vertices, edges, and faces.

Half-Edge Data Structure

The authors of the QuickHull Algorithm recommended a half-edge data structure for relatively easy manipulation of the convex hull mesh. Sometimes, faces need to be merged in case they might be coplanar, so such a data structure is needed. Maya doesn't use the half-edge format internally (it is index-based), so I had to create one that extends the Maya API myself.

I spent a long time wondering where the ownership of data would go, since there are several options (Maya, the Maya command, the QuickHull class root, or the half-edge data structure). I resorted to storing the vertex data in QuickHull and everything else in the half-edge data structure since Maya and the Maya command are too far removed. The data structure also appears to be extended to be doubly-linked on the half-edge and vertex level, which added some complicating factors to the data ownership problem. Because I saved vertex data in the QuickHull class, I was able to forgo the vertex list and pass around iterators to a vertex pointer list instead.

There are quite a few more notes to the implementation outside of the QuickHull3D lecture, so I referenced the original Java implementation as well as a JavaScript port that I found to be more readable. Unfortunately both languages don't use pointers, so figuring out what was a copy and what was a reference took some time.

However, now that the interface design for the classes is largely complete, I imagine that implementing the algorithm wouldn't take too much time.

I do want to note that I did find one Maya implementation of QuickHull, but it is not robust.

Visual Progress

So far I have been able to extend the initial plane to be 3D (which is nontrivial as described above). Here are the resulting images from Maya.

Simplex Convex Hull of a Dog Simplex Convex Hull of a Humanoid Rat

The hull mesh isn't green anymore! The polyPrimitveCmd example that Autodesk includes had some code that could add the mesh to the initial shading group. I also added locator generation to help determine which vertex was which.