Laurent Rineau, Jane Tournois
GeometryFactory
Triangulations, and in particular Delaunay triangulations, are fundamental tools in computational geometry and have been part of CGAL since its very first release. CGAL offers (Delaunay) triangulations in Euclidean spaces of any dimension, as well as specialized types such as periodic or hyperbolic triangulations.
Among these, a particularly interesting subset of triangulations are Constrained (Delaunay) Triangulations, which guarantee that a given set of points, segments, or polygonal constraints are present in the triangulation. By ensuring that key features are retained in the resulting mesh, constrained triangulations provide a faithful representation of complex geometries for simulation and analysis. CGAL has long supported two-dimensional constrained triangulations, but the notoriously harder three-dimensional version was missing, until now.
New Package: 3D Constrained Triangulations
As a major milestone for the CGAL library, the upcoming release CGAL 6.1 will offer a new package, 3D Constrained Triangulations, which enables the construction of 3D Delaunay triangulations that can preserve a user-defined set of segments and 3D polygons.
These new triangulations leverage the exact geometric paradigm of CGAL, and the experience of existing triangulations to achieve robustness to degeneracies. For example, the algorithm successfully constructs constrained Delaunay triangulations for all inputs of Thingi10k that meet the input geometrical and topological requirements.
Piecewise linear complex input (left) and its 3D constrained Delaunay triangulation (right)
The package supports two types of input: piecewise linear complexes and 3D polygon soups. These are used as parameters for the two main functions to generate constrained triangulations in 3D:
CGAL::make_conforming_constrained_Delaunay_triangulation_3(plc)to build the constrained triangulation from a piecewise linear complex;CGAL::make_conforming_constrained_Delaunay_triangulation_3(points, polygons)to build the constrained triangulation from a polygon soup.
The class
CGAL::Conforming_constrained_Delaunay_triangulation_3
provides a richer interface to build and explore the triangulation.
Interfacing with Existing CGAL Packages
The new 3D constrained triangulations have been designed to interface easily with other CGAL components,
such as Polygon Mesh Processing
or Tetrahedral Remeshing packages.
As an illustration of this, a preprocessing step can be performed using the function
CGAL::Polygon_mesh_processing::remesh_planar_patches
to systematically detect and merge all coplanar faces within a piecewise linear complex.
This operation simplifies the input data by reducing its overall complexity, while striving to preserve
as constraints, only the boundary edges of the planar surface patches.
The resulting structure can then serve as input to the constrained triangulation algorithm,
leading to simpler and higher quality results, as illustrated in the following two figures.
Piecewise linear complex (left) and its 3D Constrained Triangulation (right)
Piecewise linear complex after remeshing of planar faces (left), and its 3D Constrained Triangulation (right)
Status
The package 3D Constrained Triangulations is already available in CGAL's master branch on the CGAL GitHub repository, and will be officially released in CGAL 6.1, scheduled for mid 2025.
Documentation about 3D Constrained Triangulations
CGAL master branch on GitHub
