Progressive Convex Hull Simplification

Implementation of the algorithm from the paper

https://arxiv.org/abs/2604.14468

What it does

Given a 3D mesh, produces a sequence of progressively simpler convex hulls that are guaranteed to strictly contain the input at every step (conservative / exterior simplification).

The key idea is to work in the dual of the convex hull. Removing a vertex from the dual corresponds to removing a halfspace from the primal hull's H-representation — i.e., eliminating one face constraint and slightly enlarging the hull. Dual vertices are removed greedily in order of a per-vertex cost (primal volume added, surface area change, or mean width change), analogous to quadric-error simplification for triangle meshes.

Build

Requires CMake ≥ 3.24 (libigl's dependency recipes need it) and a C++17 compiler. Dependencies are fetched automatically via FetchContent. Builds on Linux and macOS. (On CMake 4.x the project sets a policy floor internally so the commands below work as-is; no extra flags needed.)

# Full build (includes interactive viewer; polyscope + embree fetched automatically)
cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --target pchs

# Headless build (no polyscope or embree dependency)
cmake -B build-headless -DCMAKE_BUILD_TYPE=Release -DPCHS_INTERACTIVE=OFF
cmake --build build-headless --target pchs

# Python bindings (nanobind fetched automatically; pass your Python executable)
cmake -B build-py -DCMAKE_BUILD_TYPE=Release -DPCHS_INTERACTIVE=OFF -DPCHS_PYTHON_BINDINGS=ON \
      -DPython_EXECUTABLE=$(python3 -c "import sys; print(sys.executable)")
cmake --build build-py --target pchs_python_module

Mesh backend (CGAL or native)

The geometry/mesh backend is swappable at configure time via -DPCHS_BACKEND:

• CGAL (default) — CGAL::Polyhedron_3 + CGAL predicates + CGAL::convex_hull_3.

• NATIVE — a dependency-light backend using only the C++ standard library, a small half-edge mesh, qhull for the convex hull, and Shewchuk's robust predicates for orient3d. The native build fetches no CGAL and links no gmp/mpfr:

  cmake -B build-native -DCMAKE_BUILD_TYPE=Release -DPCHS_INTERACTIVE=OFF \
        -DPCHS_TESTS=OFF -DPCHS_BACKEND=NATIVE
  cmake --build build-native --target pchs
  

Both backends produce the same hulls; they differ only in floating-point tie-breaks that can change the greedy removal order late in a run. See docs/backend-abstraction-plan.md for the design and tests/native_regression.sh (also wired as an opt-in CTest via -DPCHS_NATIVE_REGRESSION=ON) for the A/B check.

Tests

The test suite (on by default; disable with -DPCHS_TESTS=OFF) is wired into CTest:

cmake -B build-headless -DCMAKE_BUILD_TYPE=Release -DPCHS_INTERACTIVE=OFF
cmake --build build-headless --target pchs pchs_tests
ctest --test-dir build-headless --output-on-failure

It covers global invariants (closed / genus-0 dual, conservative containment), byte-exact golden regression on the icosahedron, and per-component units (Chebyshev center, dual round-trip, cost vs finite-difference, mean width, the half-edge Euler ops, and the native geometry/mesh/hull vs CGAL). Add -DPCHS_NATIVE_REGRESSION=ON to also A/B-build the native backend and compare it against CGAL.

Usage

./build/pchs [options] [mesh.ply]

Defaults to an icosahedron if no mesh is given.

Default output filenames are derived from the input stem, e.g. Actaeon.ply → Actaeon-primal.ply, Actaeon-dual.ply, Actaeon-costs.dmat, etc.

Interactive viewer

./build/pchs --interactive --target 18 Actaeon.ply

Opens a polyscope window showing the input mesh (ambient occlusion computed in the background) and the current simplified hull (transparent, colored by face normals or graph coloring). Controls are in the left panel under Hull Simplification:

• Target / Animate to target / Step / Go to target — drive simplification one step at a time or animate to the target count.
• Cost function — switch between Volume, Area, and Mean Width cost metrics; switching resets to the full hull and re-simplifies to the current vertex count.
• Hull alpha — adjust hull transparency.
• Coloring — graph coloring or normal pseudocolor.
• Reset — rebuild from the full hull.

Algorithm sketch

1. Compute the convex hull of the input primal mesh (CGAL).
2. Find the Chebyshev center of the primal halfspaces via a small linear program (SDLP).
3. Map each non-(nearly-)degenerate primal face to a dual vertex via the polarity transform about the Chebyshev center.
4. Compute the convex hull of the dual points (CGAL).
5. For each dual vertex, measure the cost of removing it and re-triangulating the hole convexly: the primal volume added, the change in primal surface area, or the change in mean width.
6. Maintain a lazy-deletion min-heap. Repeatedly pop the cheapest vertex, erase it from the dual (retriangulating the resulting hole convexly), and update neighbors' costs.
7. Convert the simplified dual back to a primal polygon mesh.

Library API

The core logic is in ConvexHullSimplification (convex_hull_simplification.h):

ConvexHullSimplification chs(V, F);   // build primal hull, dual, init queue
chs.simplify_to(18);                  // greedily simplify to 18 dual vertices
auto [pV, pPI, pPC] = chs.get_primal_mesh();  // get current hull as polygon mesh
auto [dV, dF]       = chs.get_dual_mesh();    // get current dual as triangle mesh

For step-by-step control:

while(chs.step()) { ... }             // one greedy removal per call
chs.num_dual_vertices();              // current vertex count
chs.popped_dual_vertex_costs();       // VectorXd, NaN for surviving vertices
chs.popped_dual_vertex_ids();         // removal order
chs.stats();                          // timing breakdown (t_primal_hull, t_dual_hull,
                                      //   t_queue_init, t_last_simplify)

The cost function defaults to CostFunction::PRIMAL_VOLUME; alternatives are CostFunction::PRIMAL_AREA and CostFunction::PRIMAL_MEAN_WIDTH:

ConvexHullSimplification chs(V, F, /*max_degree_for_flips=*/100, CostFunction::PRIMAL_AREA);

MAX_DEGREE_FOR_FLIPS (env var, default 100) controls the vertex-degree threshold above which the convex-hull-based one-ring triangulation is used instead of the flip-based method.

Python API

Install

pip install git+https://github.com/alecjacobson/progressive-convex-hull-simplification.git

This builds the pchs extension module via CMake/nanobind under the hood (using scikit-build-core); the default build links CGAL, so the compile can take a few minutes and the resulting module is GPL-encumbered (see License). To build the dependency-light native backend instead (no CGAL/GPL), pass it through CMAKE_ARGS:

CMAKE_ARGS="-DPCHS_BACKEND=NATIVE" \
  pip install git+https://github.com/alecjacobson/progressive-convex-hull-simplification.git

Alternatively, building manually (see Build above) with -DPCHS_PYTHON_BINDINGS=ON, adding the build directory to PYTHONPATH also works:

import pchs
import igl

V, F = igl.read_triangle_mesh("mesh.obj")

chs = pchs.ConvexHullSimplification(V, F,
    max_degree_for_flips=100,
    cost_function=pchs.CostFunction.volume)  # or pchs.CostFunction.area

chs.simplify_to(18)

pV, pPI, pPC = chs.get_primal_mesh()   # polygon mesh
dV, dF       = chs.get_dual_mesh()     # triangle mesh

costs = chs.popped_dual_vertex_costs() # VectorXd, NaN for surviving vertices
ids   = chs.popped_dual_vertex_ids()   # removal order

s = chs.stats()
print(s.t_primal_hull, s.t_dual_hull, s.t_queue_init, s.t_last_simplify)

# Or use the one-shot wrapper:
pV, pPI, pPC = pchs.simplify_convex_hull(V, F, 18)

Construct a convex polytope directly from a set of halfspaces (skipping the mesh → primal-hull → dual pipeline entirely, and with no simplification):

# Halfspaces as rows [nx, ny, nz, b], interior: n·x + b <= 0.
halfspaces = ...  # N x 4

x0 = pchs.chebyshev_center(halfspaces)  # optional; computed automatically if omitted
pV, pPI, pPC = pchs.primal_mesh_from_halfspaces(halfspaces, x0)

chebyshev_center raises if the underlying LP fails outright, but — like the igl::chebyshev_center it wraps — doesn't always detect a genuinely empty intersection (e.g. two disjoint opposing planes); sanity-check the result if the input isn't already known to bound a nonempty region.

License

The code in this repository is released under the MIT License (see LICENSE). Which license governs a compiled program, however, depends on the backend you build, because the dependencies differ.

Native backend (-DPCHS_BACKEND=NATIVE) — no copyleft

Links only permissive / weak-copyleft dependencies:

None of these is GPL/LGPL, so a native build carries no viral copyleft: you may ship it under your own (e.g. MIT) terms while preserving the upstream notices. It fetches no CGAL and links no gmp/mpfr/boost.

CGAL backend (default) — GPL

The default build additionally links CGAL. The packages it uses, Convex_hull_3 and Polyhedron_3, are GPL-3.0-or-later (the kernel and HalfedgeDS are LGPL-3.0-or-later, and CGAL pulls in Boost). Because those two packages are GPL, a distributed CGAL-backend binary is effectively GPL-3.0-or-later — unless you obtain a commercial CGAL license. MIT is GPL-compatible, so combining is fine; it just means the program as a whole is copyleft.

In short: the library code is MIT. Build the native backend and the only obligations are the permissive / weak-copyleft notices above; build with CGAL and the distributed binary is GPL.

LLM use

I wrote the original prototype of this algorithm in matlab without much input from llms or coding agents (probably copilot tab-complete helped a little bit). Then I wrote most of first draft of the paper. My thought was that Claude Code etc. would have no trouble taking the paper source and the matlab prototype and spitting out a C++ implementation. A few failed attempts and a lot of spent tokens later, I gave up doing it completely automatically. The llms were simultaneously immensely helpful parsing through CGAL's otherwise forboding documentation and templating and also terribly confused by how to build anything more complicated than simple loops over elements using CGAL's half-edge datastructure. Using webchat llms effectively as a search engine on the CGAL documentation, I wrote the initial core of the vertex_erasure, primal_change, and convex_hull_simplification functions more or less manually (with tab-complete copilot stuff). When a very minimal version of this was working, I let Claude Code at it with CMake build junk, adding visualization, flags, python bindings, and most of this readme file. I did not use coding agents of llms to write any of the paper text (beyond looking for typos or double-checking derivations).

I added the mean-width cost metric after the first round of reviews. Again, I thought that because the area and volume metrics were already in place this would be an easy fully automatic task for Claude Code. It burnt an entire session quota and output nothing. So, I ended up writing that manually (with copilot tab-complete), and then Claude code cleaned up the flags and visualization code to expose the new cost metric.

Update: Since then, I've had Claude implement a non-CGAL (i.e., non-GPL) backend. I did this in --dangerously-skip-permissions mode which was fairly successful at not nagging me for instruction. I told it to use Qhull and to build its own half-edge data-structure using STL. It appears to have done that effectively.