Press G or tap to generate a new random hull.

ExactHull — Exact 3D Convex Hull

An unbreakable convex hull library that uses exact arithmetic instead of floating-point epsilon hacks. Every IEEE-754 double is imported as an exact dyadic value (mantissa × 2exp backed by BigInteger), and all geometric predicates are computed without rounding.

How It Works

1. Initial tetrahedron. Four non-coplanar points form the starting polytope. Each remaining point is assigned to a face it lies above.
2. Expand. For each face with outside points, the farthest point is selected. A BFS collects all faces visible from that point, identifying the horizon boundary.
3. Replace. Visible faces are removed and replaced by new triangles connecting the horizon edges to the new point.
4. Reassign. Orphaned points are reassigned to the new faces. Points now inside the polytope are discarded.
5. Repeat until no face has outside points.

Why Not Just Use Floating Point?

Convex hull construction is unusually sensitive to numerical precision. The algorithm repeatedly asks questions like “is this point above or below that face?” or “which faces are visible from this point?”. With floating-point arithmetic, nearly degenerate inputs can flip those decisions because of rounding error. One wrong predicate is enough to damage the hull. ExactHull replaces those fragile decisions with exact ones.

Why Exact Arithmetic Is Practical Here

Exact arithmetic works well here because the algorithm never feeds constructed coordinates back into later geometry calculations. It only evaluates predicates on the original input points, so intermediate exact values stay bounded rather than growing with scene complexity.