ExactHull 0.5.0

<p align="center"> <img src="https://raw.githubusercontent.com/notgiven688/ExactHull/main/media/logo_small.png" alt="ExactHull" width="240"> </p>

ExactHull — Exact 3D Convex Hull in C#

An unbreakable 3D convex hull library using exact arithmetic. No floating-point epsilon hacks — geometric predicates are computed exactly using a dyadic rational representation backed by BigInteger.

🌐 Try the Interactive Web Demo →

📦 NuGet Package →

Disclaimer

This project started from the hunch that a convex hull algorithm could be made robust by using exact arithmetic instead of floating-point hacks. It was built in a single morning to explore that idea using ChatGPT 5.4 in thinking mode and Amp by Sourcegraph. Nearly all code in this repository was generated by AI.

The central conclusion (in a very ChatGPT tone):

Exact 3D convex hull construction is practical, not just theoretical.

In its current form, the project is aimed primarily at small to medium-sized point clouds, where exactness and robustness matter more than absolute peak throughput.

Quick Start

using ExactHull;

var hull = ExactHull3D.Build(
    (0.0, 0.0, 0.0),
    (1.0, 0.0, 0.0),
    (0.0, 1.0, 0.0),
    (0.0, 0.0, 1.0),
    (0.25, 0.25, -1.0));

foreach (var face in hull.Faces)
    Console.WriteLine($"{face.A}, {face.B}, {face.C}");

Use the generic overload to pass any custom point type:

List<Vector3> myPoints = ...;
var hull = ExactHull3D.Build(myPoints, v => (v.X, v.Y, v.Z));

How It Works

Every IEEE-754 double is imported as an exact dyadic value of the form mantissa × 2^exponent. All geometric decisions — orientation, visibility, sidedness — are computed exactly. This eliminates the robustness failures that plague floating-point convex hull implementations.

Algorithm

The algorithm builds the convex hull incrementally:

1. Initial polytope. Four non-coplanar points are selected to form an initial tetrahedron. Each remaining point is assigned to a face it lies above (the outside set).

2. Expand the polytope. For each face that has an outside set, the farthest point is selected. A BFS from that face along face adjacencies collects all faces visible from the point, identifying the horizon — the boundary between visible and non-visible faces.

3. Replace visible faces. The visible faces are removed and replaced by new triangular faces connecting the horizon edges to the new point, forming a cone. The new faces are linked to each other and to the surviving neighbors across the horizon.

4. Reassign points. Points from the removed faces' outside sets are each reassigned to a new face they lie above. Points now inside the polytope are discarded.

5. Repeat until no face has any outside points remaining.

Why Exact Arithmetic Works Here

Convex hull construction mostly evaluates predicates on the original input points (orientation, visibility). It does not build long chains of constructed coordinates, so the exact representations stay manageable.

Project Structure

src/
  ExactHull/          # Core library (NuGet package)
  ExactHull.Tests/    # Test suite
  ExactHull.Demo/     # Benchmark CLI
  ExactHull.WebDemo/  # Interactive WebAssembly demo

Testing

dotnet test src/ExactHull.Tests/ExactHull.Tests.csproj

Tested on tetrahedra, cubes, octahedra, duplicate points, interior points, random point clouds, shuffled input order, sphere-distributed points, nearly coplanar clouds, and large coordinates with tiny offsets.

Benchmarks

Two point distributions are benchmarked:

• Cube interior — points uniformly distributed inside a cube. Most points are not on the hull.
• Sphere surface — points uniformly distributed on the unit sphere. All points lie on the hull.

To reproduce:

dotnet run --project src/ExactHull.Demo -c Release
python3 misc/plot.py