This is an implementation and visualization of Timothy Chan's 3d Convex Hull Algorithm.
Here are some slides from a presentation about the algorithm.
To build the program (requires Qt 4.5 with OpenGL support):
This creates a platform specific build system, which you can use to build the project.
The program can open point sets from a file, in the same format as Chan's original implementation of this algorithm:
n x_0 y_0 z_0 ... x_{n-1} y_{n-1} z_{n-1}
All points should lie strictly between -1e12 and 1e12, as these are considered to be -infinity and +infinity by the code. Chan's algorithm uses 1e99 for these special values, however my OpenGL drivers have trouble rendering when things get so large, possibly due to the use of floats instead of doubles. So my implementation drops infinity down to 1e12, which is rendering without problems. The 3d projection view is set up to view only a depth of 2000 at one time however.
The code implementation has changed in appearance, but not a great deal in functionality from Chan's. In particular, this means it does not handle degenerate cases any better than the original code did.
The program can generate a random point set of between 3 and 1000 points, by going to the File menu, and selecting "New Point Set...". The random point sets are generated as integers in the range of 0 and 5*1e8, then squished as floating point numbers into the range of -500 and 500. This range was chosen largely to fit within the z-range of the 3d projection. The more points you add to a random generation, the larger the chances of creating degeneracies, which may show up in the 2d projection as a non-convex hull.
The program runs through the algorithm two times for a point set. The first time it computes the lower hull, and the second time the upper hull. At the end, an entire 3d convex hull is formed. Step through the creation of the convex hull with the Spacebar hotkey, or in the Run menu choose "Find Next Face".