Cédric Portaneri*, Mael Rouxel-Labbé°, Michael Hemmer, David Cohen-Steiner*, Pierre Alliez*
*INRIA Sophia Antipolis, °GeometryFactory
In 2022, the package 3D Alpha Wrapping was introduced in CGAL and a companion paper was accepted at Siggraph. Alpha wrapping is a method to generate valid (i.e., watertight, combinatorially 2-manifold and orientable) meshes that strictly enclose the input. In addition, this algorithm is unconditionally robust to any type of defect in the input, and generic with respect to the nature of the input (points, segments, triangles, ...).
For more information on the Alpha_wrap_3, we refer to the associated news entry.
The 2D Alpha Wrapping Package
In the next CGAL release, we add the 2D equivalent to the 3D Alpha Wrapping package: the method can be used to generate polygons (possibly with holes) that strictly enclose an input. The algorithm is identical to the 3D counterpart, proceeding by carving and refining a 2D Delaunay triangulation.
An input (purple and blue) and wrapping results (black). The input is composed of many overlapping polylines, as shown in the head zoom (leftmost).
The new method comes with the same properties as the 3D version:
- Guaranteed to produce simple polygons which contain the input
- Unconditionally robust to input defects (self-intersections, non-manifoldness, etc.)
- Generic with respect to the nature of the input (points, segments, polygons, mixed, etc.)
- Adjustable complexity-fidelity tradeoff via two meaningful parameters
- Output sensitive
Usage
Two parameters control the behavior of our algorithm: alpha and offset. The parameter alpha controls the minimum carving size, and thus the size of straits and holes that cannot be traversed during carving. The parameter \delta is the value of the distance field level-set defining the offset surface. It controls the distance of the mesh vertices to the input, and thus the tightness of the approximation (see Figure below). Both parameters can be chosen independently and arbitrarily large or small, but must be strictly positive.
Multiple wrappings (black) of the racers model (blue) for various combinations of alpha and offset (click to enlarge).
Alpha and offset impact the complexity-fidelity tradeoff.
Status
The package Alpha_wrap_2 is already integrated in CGAL's "main" branch on the CGAL GitHub repository, and will be officially released in the upcoming version of CGAL, CGAL 6.2, scheduled for June 2026.
Documentation of the package Alpha_wrap_2
CGAL “main” branch on GitHub
