Mael Rouxel-Labbé
GeometryFactory
Introduced in CGAL 5.5, the package 3D Alpha Wrapping can be used to generate watertight, manifold surface triangle meshes from any given inputs provided we can compute distances and intersections to this input. This enables the method to guarantee output properties, and genericity with respect to the input format (triangles, polylines, ...). In addition, it is guaranteed to strictly encloses the input, which is a mandatory property for applications needing conservative distance queries, such as collision avoidance, or motion planning. Finally, it is fully robust to defects in the input such as self-intersections, degeneracies, non-manifoldness...
Season's wrappings.
In the upcoming CGAL release, CGAL 6.0, we introduce a few improvements to the 3D Alpha Wrapping package: pause & resuming functionalities, fast "LOD" wrapping, generation of volumetric wraps, and some speed-ups.
Resume and Restart Functionalities
The main function of the package 3D Alpha Wrapping takes two input parameters: the size of the the feature size (alpha), and the isosurface of the distance field on which new vertices are created (offset, also named delta). The parameter alpha can be understood as the size of a spoon carving around the input. A larger alpha will thus remove small features and fill large gaps, and a small alpha will preserve those features, and enter the gaps and cavities (see also Section Choosing Parameters of the documentation). Although the physicality can be understood, it might be that one is not exactly sure which value should be used; or, one might simply wish to create a wrap that is as detailed as possible within a fixed amount of time.
This is now possible thanks to the addition of a visitor to the wrapping algorithm, which gives more information and control to the user during the wrapping process. An example showing how to use the visitor to pause and resume a wrapping process has been added: pause_and_resume_wrapping.cpp.
Another closely related feature being added is the possibility of generating multiple wraps for different values of alpha for the same input, for example to generate different levels of detail (LODs). One could of course simply launch the wrapping process from scratch as many times as needed, but the resuming functionality improves greatly on this: by sorting the value of alpha in decreasing order (coarse to fine), we can restart from a previous result to generate the next version. By avoiding a recomputation from scratch, a lot of time is saved. Here is a new example illustrating the process: successive_wraps.cpp.
Wrapping of an engine piece with complex interior (left) for different values of alpha.
Volumetric Meshing
The wrapping algorithm constructs an underlying 3D triangulation of which the final wrap is a selected set of faces. Thus, at the end of the algorithm, we have a tetrahedrization of the volume bounded by the wrap. This tetrahedral mesh was totally unused so far, but a getter has been added. By combining this with the recent package Tetrahedral Remeshing, one can generate high-quality volumetric tetrahedral meshes of the space enclosed by the wrap.
The following example describes this process: volumetric_wrap.cpp.
Speed-up
Finally, we always look for improvements while working on code. Various enhancements to the wrapping algorithms have resulted in a 2x speed-up of the code since CGAL 5.6!
Status
All these new improvements are already integrated in CGAL's master branch on the CGAL GitHub repository, and will be officially released in the upcoming version of CGAL, CGAL 6.0, scheduled for June 2024.
Documentation of the package Alpha_wrap_3
CGAL master branch on GitHub
