Alpha Wrapping

1. Alpha Wrapping Overview

1.1. Approach

To enclose a 3D model within a volume, various methods balance runtime and approximation quality. Simple methods, like bounding boxes, have large errors. Convex hulls improve quality but remain crude, especially for complex models. Alpha shapes, a special case of the Delaunay triangulation, offer piecewise-linear approximations but struggle with complex input data.

Inspired by alpha shapes, this approach uses shrink-wrapping. It constructs a 3D Delaunay triangulation and iteratively removes eligible boundary tetrahedra. This process refines the triangulation, avoiding inner structures and unnecessary computations. The method supports flexible input formats (triangle soups, polygon soups, point clouds) and allows trading tightness for mesh complexity.

1.1.1. Algorithm Initialization

The algorithm starts by inserting the vertices of a bounding box into a 3D Delaunay triangulation. In CGAL’s 3D Delaunay triangulation, boundary facets are adjacent to infinite cells tagged as outside, while finite tetrahedra are tagged inside.

1.1.2. Shrink-wrapping

The algorithm traverses from outside to inside cells, using a priority queue of Delaunay triangle facets (gates). A gate is alpha-traversable if its circumradius exceeds a user-defined alpha. The priority queue, initialized with convex hull gates, is sorted by decreasing circumradius. Traversal uses dual Voronoi edges.

When moving from an outside cell \( c_o \) to an inside cell \( c_i \) through an alpha-traversable facet \( f \):

  1. Check for intersections between \( f \)'s dual Voronoi edge and the offset surface. Insert the first intersection point as a Steiner point into the triangulation.

  2. If no intersection but \( c_i \) intersects the input, project \( c_i \)'s circumcenter onto the offset surface and insert it as a Steiner point.

Newly alpha-traversable gates are added to the queue. If neither criterion is met, \( c_i \) is tagged outside, and its gates are pushed to the queue. The process terminates when the queue empties, producing a triangle surface mesh from the Delaunay triangulation.

alpha wrapping steps
Figure 1. Steps of the shrink-wrapping algorithm in 2D. The algorithm initializes by inserting the bounding box corners into a Delaunay triangulation, tagging finite triangles inside. The current gate (green edge) is alpha-traversable. Adjacent triangles are tagged outside if they do not intersect the input. If they do, new Steiner points are inserted, and traversal resumes. The output edges (dark blue) separate inside from outside triangles.

1.1.3. Termination and Guarantees

The algorithm guarantees termination and produces a 2-manifold triangulated surface mesh that encloses the input data. By wrapping from outside to inside and refining the triangulation as needed, it ensures no intersecting cells are flagged inside. Steiner points inserted during refinement break necessary cells, reducing circumradii and ensuring completion.

Source : CGAL 3D Alpha Wrapping User Manual

Next: Placing Trees

References