Computational Geometry

Interactive algorithm visualisation · 3D Convex Hull

QuickHull - 3D Convex Hull

The following demonstration steps through the QuickHull algorithm applied to a synthetic LiDAR point cloud representing a building survey. QuickHull is the algorithm at the core of Qhull - the computational geometry library used in AutoCAD, MATLAB, SciPy, and many professional BIM toolchains.

Click Next to advance through each stage. The model is interactive, feel free to rotate and zoom!

1 / 18

InitialisationStep 1

Identify Extreme Points

QuickHull begins by finding the six extreme points - minimum and maximum along each axis. The candidate set is:

E = { argmin(P·x^), argmax(P·x^),

argmin(P·y^), argmax(P·y^),

argmin(P·z^), argmax(P·z^) }

These 4 unique candidates are guaranteed hull vertices - no convex combination of other points can exceed them. From a LiDAR survey of 16 points, this initial sweep runs in O(n) time and immediately eliminates most interior points from consideration.

Colour Key

Extreme / highlighted points

Active point being added

Unprocessed survey points

Confirmed hull faces

Visible faces (to be removed)

Newly created faces

Horizon edges