Quickhull 3D

Quickhull is a well known algorithm to calculate the convex hull from a set of points. During a lab course in computational geometry I have implemented the Quickhull algorithm for its application in 3D space and wrote a little demo application.

The calculation of the convex hull is written from scratch and based on the algorithm by Barber et al. "The Quickhull Algorithm for Convex Hulls". It's an iterative algorithm that roughly works as follows:

  • Create a tetrahedron out of any 4 points of the input set. A tetrahedron is the three-dimensional case of a simplex. It is also the convex hull of its fours points. We are assuming that the set of input points is well behaved, i.e. no duplicate points.
  • Assign outside sets of points for each face.
  • For each face F with a non-empty outside set do the following:
    • Determine the furthest vertex p of F's outside set
    • Determine all visible faces as seen from p. The edges around this visible set forms the so-called horizon ridge.
    • Create new faces between p and the horizon ridge and add them to the convex hull. Delete the previously visible faces. Assign new outside-sets of unprocessed input points to the newly created faces. Proceed with the next unprocessed face of the convex hull.
  • Done

You can find a more detailed explanation of this particular algorithm in the original paper.

There are a few robust libraries such as CGAL, qhull or the more recent generic boost::geometry library that implement the quickhull algorithm, even for higher dimensions. My demo application implements the convex hull calculation from scratch. However, it was built mainly for documentation purposes and for me experimenting with it. Source code is freely available under MIT license. The demo app is written for Mac OS X 10.6 as I also took the opportunity to test mixing OpenGL with Apple's AppKit using more modern approaches, i.e. GUI overlays using CoreAnimation.

Here is a short guide how to use the demo app:

  • Use the right overlay panel to add random points to the input set of vertices.
  • Use the bottom overlay panel to visualize the quickhull algorithm step by step in simulation mode.
  • Navigate using Alt-Left Mouse for camera orbit and scrolling, pinching or Alt-Right Mouse for zooming.
  • You can switch to fullscreen mode using Cmd-F or the fancy button in the bottom right corner.

If you don't have the opportunity to test it yourself on a Mac, checkout this short screen capture video: