Improving 3D alpha wrapping by preserving concave features and reducing mesh complexity

Abstract

CGAL’s 3D Alpha Wrap robustly produces valid enclosing meshes for defective input using two parameters: α, which controls the carving-ball size, and δ, an offset that controls the distance between the input and the output surface vertices. However, preserving sharp concave features often requires a small global α-value, which also increases refinement in regions where additional vertices do not substantially improve the approximation. This paper proposes a 𝜏-guided extension that adds a local face-to-input distance criterion to the original algorithm. The new parameter 𝜏 triggers additional refinement only where the current wrap remains locally too far from the input.

To make this refinement effective near concave features, we introduce R3 as an additional vertex-insertion strategy alongside the two insertion strategies of the original algorithm. R3 aims to place new vertices more directly near sharp concave features, whereas the original two insertion strategies may reach comparable vertex positions only after repeated refinement. The extension preserves the carving-based structure of the original algorithm, and we prove that the guarantees of termination, strict enclosure, watertightness, and manifoldness still hold. Experiments on 3D BAG building data show that the proposed method improves both average and local approximation quality, achieving lower directed Chamfer distances with fewer output faces than the original algorithm. Although R3 is less time efficient per insertion, it places vertices more effectively near concave features, so fewer insertions are needed to reach lower approximation errors. As a result, the proposed method can reduce runtime in the tested use case.