alpha-wrap

A clean-room, CGAL-free and copyleft-free implementation of "Alpha Wrapping with an Offset" (Portaneri, Alliez, Hemmer, Birklein, Kobbelt — ACM TOG 2022).

Given an arbitrary input triangle soup (which may be non-manifold, self-intersecting, open, or defective) and two parameters — alpha (the carving-ball radius / level of detail) and offset (the distance-field iso-level / tightness) — it produces a surface mesh that is:

• watertight (closed),
• combinatorially 2-manifold,
• outward-oriented,
• strictly enclosing the input, with vertices ~offset outside it,
• bounded within an O(alpha+offset) band of the offset surface, every facet having circumradius < alpha.

alpha acts as a topological level-of-detail knob: features (holes, handles, gaps) narrower than ~alpha are bridged/filled; wider ones are preserved.

Install (Python)

# directly from GitHub
pip install "git+https://github.com/alecjacobson/alpha-wrap.git"

# or from a local clone
pip install .

import numpy as np, alpha_wrap
W, G = alpha_wrap.wrap(V, F, alpha_rel=1/30, offset_rel=1/900)  # V:(N,3), F:(M,3)

Building the wheel compiles the C++ extension, so a C++17 compiler and CMake ≥ 3.16 are needed at install time (plus network access on the first build to fetch the predicates). See Python bindings for the full API.

Dependencies

Only Shewchuk's public-domain robust predicates (danshapero/predicates), fetched automatically by CMake. No CGAL, no geogram, no GPL / non-commercial code. The incremental 3D Delaunay triangulation, the AABB-tree distance/intersection oracle, and the whole wrap algorithm are implemented from scratch. See DESIGN.md for the rationale (including why geogram was rejected).

Build

cmake -B build -DCMAKE_BUILD_TYPE=RelWithDebInfo
cmake --build build -j
ctest --test-dir build --output-on-failure

Requires a C++17 compiler and CMake ≥ 3.16. Network access is needed on the first configure to fetch the predicates.

Command-line usage

# defaults: alpha = diag/20, offset = alpha/30
./build/alpha_wrap input.obj output.obj

# relative parameters (fractions of the bounding-box diagonal)
./build/alpha_wrap input.obj out.obj --adiv 40 --odiv 1200

# absolute parameters
./build/alpha_wrap input.ply out.ply --alpha 0.05 --offset 0.002 --no-manifold

Reads/writes ASCII .obj and .ply. Each run self-reports output invariants (closed / oriented / vertex-manifold / Euler characteristic).

Library

#include "alpha_wrap.hpp"

std::vector<aw::Triangle> soup = /* your input */;
aw::WrapStats stats;
aw::Mesh m = aw::alpha_wrap(soup, /*alpha=*/0.05, /*offset=*/0.002,
                            /*manifold=*/true, &stats);
// m.V : vertices, m.F : outward-oriented triangles

Python bindings

Install from source (builds the C++ extension via scikit-build-core + nanobind; needs a C++17 compiler, CMake ≥ 3.16, and network access on first build to fetch the predicates):

pip install .
# or straight from GitHub:
pip install "git+https://github.com/alecjacobson/alpha-wrap.git"

Usage — wrap takes a triangle soup (vertices, faces) and returns the wrapped (V, F) as NumPy arrays (float64 and int32):

import numpy as np
import alpha_wrap

V = np.asarray(vertices, float)     # (N, 3)
F = np.asarray(faces, np.int64)     # (M, 3), may be non-manifold / defective

# relative parameters (fractions of the bounding-box diagonal)
W, G = alpha_wrap.wrap(V, F, alpha_rel=1/30, offset_rel=1/900)

# or absolute, and grab the internal stats
W, G, stats = alpha_wrap.wrap(V, F, alpha=0.05, offset=0.002,
                              manifold=True, return_stats=True)

Defaults follow the paper: alpha = diag/20, offset = alpha/30. The output is watertight, outward-oriented, 2-manifold, and strictly encloses the input.

Optional CGAL reference backend

The package can additionally expose alpha_wrap.wrap_cgal(...), which runs CGAL::alpha_wrap_3 for comparison/validation. It is off by default (it fetches Boost + CGAL at build time). Enable it with a build flag on the same install command:

pip install "git+https://github.com/alecjacobson/alpha-wrap.git" \
    -C cmake.define.AW_PYTHON_CGAL=ON
# or, from a local clone:
pip install . -C cmake.define.AW_PYTHON_CGAL=ON

Then:

import alpha_wrap
alpha_wrap.has_cgal()                 # True with the flag, False otherwise
Wc, Gc = alpha_wrap.wrap_cgal(V, F, alpha_rel=1/30)   # same signature as wrap()

wrap_cgal raises a helpful error if the package was built without the flag. CGAL is GPL/LGPL, so a package built with AW_PYTHON_CGAL=ON is GPL-encumbered (see License); the default build stays MIT/CGAL-free.

Architecture

File	Role
src/predicates.*	convention-normalized exact orient3d / insphere
src/delaunay.*	incremental Bowyer-Watson 3D Delaunay (super-tet, exact)
src/aabb_tree.*	AABB tree: distance, closest point, tet∩soup, offset crossing
src/alpha_wrap.*	loose bbox, gates, α-traversability, carve+refine, make_manifold, extract
src/mesh_io.hpp	OBJ / ASCII-PLY read & write
src/main.cpp	CLI
python/bindings.cpp, python/alpha_wrap/	nanobind module + Python package
docs/algorithm-spec.md	reconstructed algorithm reference (from paper + CGAL docs)

Testing

Bottom-up, per-subroutine (tests/): exact predicates (sign conventions, near-degenerate), incremental Delaunay (empty-sphere + topology invariants vs brute force, incl. cospherical/coplanar stress), AABB oracle (vs brute force), and end-to-end wrap invariants (watertight, oriented, vertex-manifold, strict enclosure, offset band, facet-size bound, and the α-controlled topology: torus genus, gap bridging). The official CGAL implementation is used only as a behavioral reference (matching guarantees / qualitative topology) — no code is copied.

Comparison against CGAL

A reference build of CGAL's Alpha_wrap_3 and a metrics tool are provided for validation and tuning:

# fetches Boost headers + CGAL 6.x (GMP-free) and builds tools/cgal_wrap
cmake -B build-cgal -DCMAKE_BUILD_TYPE=Release -DAW_CGAL_REFERENCE=ON
cmake --build build-cgal --target cgal_wrap -j

./build-cgal/tools/cgal_wrap in.obj cgal.obj <alpha> <offset>
./build/alpha_wrap        in.obj ours.obj --alpha <alpha> --offset <offset>
# symmetric Hausdorff + distance bands + facet stats between the two wraps
./build/aw_metrics in.obj ours.obj cgal.obj

Findings across the bundled meshes plus a 100k-triangle sphere and a 236k Actaeon statue (α = diag/30):

• Topology matches CGAL (same Euler characteristic / genus) on every input except a single borderline genus-transition α on one model — both wraps are valid there; independent implementations cross the transition at marginally different α.
• Geometry: symmetric Hausdorff distance between ours and CGAL is 0.1%–3.4% of the bbox diagonal (≈0.6·α), shrinking with α; mean surface deviation is well under 0.1% of the diagonal. Both satisfy the facet circumradius < α bound and the same offset-distance band.
• Density: ours emits 0.6–1.0× CGAL's face count — a slightly coarser but geometrically equivalent wrap.
• Speed: competitive to faster (ours ~2× faster on most inputs in this GMP-free CGAL environment).
• Robustness: on defective input (self-intersecting, open, flipped, duplicate, and degenerate triangles) ours produces a clean closed, oriented, vertex-manifold wrap and recovers the correct genus, matching CGAL.

License

This project is licensed under the MIT License (see LICENSE).

• The core library and CLI depend only on Shewchuk's robust predicates (danshapero/predicates), which are in the public domain and fetched at build time — MIT-compatible, nothing copyleft is vendored or shipped.
• The optional CGAL reference tool (tools/, built only with -DAW_CGAL_REFERENCE=ON) fetches CGAL (GPL/LGPL) and Boost (BSL) at build time for comparison purposes. It is a development/benchmarking aid and is not part of the MIT-licensed library or CLI; building it produces a GPL-encumbered binary that is not distributed here.

Robustness note

Degenerate (zero-area) input triangles are filtered before building the oracle — left in, they corrupt the offset projection and tet-intersection tests and cause runaway refinement on defective input. The offset-surface crossing used by Rule 1 is found by sphere tracing the (1-Lipschitz) distance field, which is O(log) in the offset size rather than O(segment/offset) for a fixed march.

Predicates are exact (Shewchuk). Cospherical/coplanar degeneracies in the Delaunay are handled by a deterministic "cospherical ⇒ not-in-conflict" rule (validated on cubes, grids, and points-on-faces); a residual zero-volume-cell case is detectable via verify_topology() and can be closed with full simulation-of-simplicity if a real input ever triggers it. Geometric constructions (circumcenters, Steiner points) are inexact, which the algorithm tolerates by design.