1 Conforming Delaunay Triangulations in 3D

This package implements the construction of a 3D conforming Delaunay triangulation, constrained to a set of faces of a surface polygon mesh.

For any Piecewise Linear Complex (PLC) in 3D, the algorithm builds a Delaunay triangulation conforming to this PLC. The constrained triangulation does not always exist, and it may be necessary to add Steiner points to the PLC to make it triangulable.

The problem is described by Cohen-Steiner et al [2], and by Si [7].

2 Definitions

In this section, we define the main concepts that have to be understood to use this package.

2.1 Piecewise Linear Complex

A Piecewise Linear Complex is the 3-dimensional generalization of a polyhedron.

A PLC is built from simple geometric elements, called simplices that are topologically connected together in a structured way. Simplices (vertices, edges, and facets) are the basic elements forming the complex. Their geometric counterparts are points, segments, polygons, respectively. The polygons can be non-convex, have holes, and as many boundary segments as needed. Each simplex is embedded into the geometric space via the points coordinates.

The simplices must satisfy the following conditions :

they must be connected together by their common faces;
each simplex is polygonal, with at least three vertices, that must be closed and coplanar;
two edges can only intersect at a common vertex which is also in the PLC;
two facets can only intersect at a common edge or vertex which is also in the PLC;
two cells can only intersect at a common facet, edge or vertex which is also in the PLC.

2.2 Conforming Delaunay Triangulation

The goal of the algorithms developed in this package is to compute a Delaunay mesh containing a given set of polygonal constraints in 3D as sub-complex. See package 3D Triangulations for more details on Delaunay triangulations.

A triangulation is a Delaunay triangulation if the circumscribing sphere of any cell of the triangulation contains no vertex in its interior. A constrained Delaunay triangulation is a constrained triangulation which is as much Delaunay as possible, given that some facets are marked as constrained. The circumscribing sphere of any cell contains in its interior no data point which is on the same side of the constrained facet as the cell.

In 3D, constrained triangulations do not always exist. It can be shown using the example of the Schönhardt polyhedra [4], [1], that requires the addition of Steiner points to be triangulable.

Shewchuk [5] showed that for any PLC, there exists another PLC that is a refined version of the original one, that admits a constrained Delaunay triangulation. The refined PLC is obtained by adding Steiner points on the input edges and facets, and the constrained triangulation built on this PLC is called a conforming Delaunay triangulation.

The algorithm implemented in this package is based on the work of Hang Si [6], [3]. Steiner points are added on input edges and input facets of the PLC to make it triangulable.

3 API

3.1 Classes

This package provides one main class Conforming_constrained_Delaunay_triangulation_3 that represents a 3D conforming Delaunay triangulation. The class is templated by the geometric traits class and the underlying triangulation class. The other classes that are provided are secondary classes that define the vertex and cell types and metadata that constitute the triangulation.

3.2 Functions

Some helper constructor functions, like make_conforming_constrained_Delaunay_triangulation_3(), are provided to create a Conforming_constrained_Delaunay_triangulation_3 object.

4 Examples

4.1 Build a conforming constrained Delaunay triangulation

The following example shows how to use the helper constructor function make_conforming_constrained_Delaunay_triangulation_3() to create a conforming constrained Delaunay triangulation from a given PLC.

File Constrained_triangulation_3/conforming_constrained_Delaunay_triangulation_3.cpp

#include <CGAL/make_conforming_constrained_Delaunay_triangulation_3.h>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/draw_triangulation_3.h>
 
#include <algorithm>
 
using K = CGAL::Exact_predicates_inexact_constructions_kernel;
 
int main(int argc, char* argv[])
{
  CGAL::Surface_mesh<K::Point_3> mesh;
 
  auto filename = (argc > 1) ? argv[1] : CGAL::data_file_path("meshes/mpi.off");
  std::ifstream in(filename);
  if(!in || !CGAL::IO::read_OFF(in, mesh)) {
    std::cerr << "Error: cannot read file " << filename << std::endl;
    return EXIT_FAILURE;
  }
 
  std::cout << "Read " << mesh.number_of_vertices() << " vertices and "
            << mesh.number_of_faces() << " faces" << std::endl;
 
  auto ccdt = CGAL::make_conforming_constrained_Delaunay_triangulation_3(mesh);
 
  std::cout << "Number of vertices in the CDT: "
            << ccdt.triangulation().number_of_vertices() << '\n'
            << "Number of constrained facets in the CDT: "
            << ccdt.number_of_constrained_facets() << '\n';
 
  CGAL::draw(ccdt.triangulation());
 
  return EXIT_SUCCESS;
}

4.2 Build a conforming constrained Delaunay triangulation from a polygon soup

It is also possible to create a conforming constrained Delaunay triangulation from a polygon soup, i.e., a set of polygons for which the connectivity is not known a priori. This example shows an example of building such a triangulation.

File Constrained_triangulation_3/conforming_constrained_Delaunay_triangulation_3_from_soup.cpp

#include <CGAL/make_conforming_constrained_Delaunay_triangulation_3.h>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <vector>
#include <CGAL/draw_triangulation_3.h>
 
#include <algorithm>
 
using K = CGAL::Exact_predicates_inexact_constructions_kernel;
 
int main(int argc, char* argv[])
{
  std::vector<K::Point_3> points;
  std::vector<std::vector<std::size_t>> polygons;
 
  auto filename = (argc > 1) ? argv[1] : CGAL::data_file_path("meshes/cubes.off");
  std::ifstream in(filename);
  if(!in || !CGAL::IO::read_OFF(in, points, polygons)) {
    std::cerr << "Error: cannot read file " << filename << std::endl;
    return EXIT_FAILURE;
  }
 
  std::cout << "Read " << points.size() << " vertices and "
            << polygons.size() << " polygons" << std::endl;
 
  auto ccdt = CGAL::make_conforming_constrained_Delaunay_triangulation_3(points, polygons);
 
  std::cout << "Number of vertices in the CDT: "
            << ccdt.triangulation().number_of_vertices() << '\n'
            << "Number of constrained facets in the CDT: "
            << ccdt.number_of_constrained_facets() << '\n';
 
  CGAL::draw(ccdt.triangulation());
 
  return EXIT_SUCCESS;
}

4.3 Remeshing a conforming constrained Delaunay triangulation

Once the triangulation is built, it is possible to remesh it using the CGAL::tetrahedral_isotropic_remeshing() function from the Tetrahedral Remeshing package, to improve the quality of the mesh or adapt it to a given sizing field.

The following example shows how to remesh a conforming constrained Delaunay triangulation.

File Constrained_triangulation_3/remesh_constrained_Delaunay_triangulation_3.cpp

#define CGAL_TETRAHEDRAL_REMESHING_VERBOSE 1
 
#include <CGAL/make_conforming_constrained_Delaunay_triangulation_3.h>
 
#include <CGAL/tetrahedral_remeshing.h>
 
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/draw_triangulation_3.h>
 
#include <fstream>
#include <string>
 
using K   = CGAL::Exact_predicates_inexact_constructions_kernel;
using Vb  = CGAL::Conforming_constrained_Delaunay_triangulation_vertex_base_3<K>;
using Cb  = CGAL::Conforming_constrained_Delaunay_triangulation_cell_base_3<K>;
using Tds = CGAL::Triangulation_data_structure_3<Vb, Cb>;
using Tr  = CGAL::Triangulation_3<K, Tds>;
using CCDT = CGAL::Conforming_constrained_Delaunay_triangulation_3<K, Tr>;
 
int main(int argc, char* argv[])
{
  std::string filename = (argc > 1) ? argv[1] : CGAL::data_file_path("meshes/mpi.off");
  std::ifstream in(filename);
 
  CGAL::Surface_mesh<K::Point_3> mesh;
  if(!in || !CGAL::IO::read_OFF(in, mesh)) {
    std::cerr << "Error: cannot read file " << filename << std::endl;
    return EXIT_FAILURE;
  }
  CCDT ccdt = CGAL::make_conforming_constrained_Delaunay_triangulation_3<CCDT>(mesh);
 
  Tr tr = CGAL::convert_to_triangulation_3(std::move(ccdt));
  std::cout << "Number of vertices in tr: " << tr.number_of_vertices() << std::endl;
 
  CGAL::tetrahedral_isotropic_remeshing(tr, 1.,
    CGAL::parameters::number_of_iterations(10));
 
  std::cout << "Number of vertices in tr: "
            << tr.number_of_vertices() << std::endl;
  CGAL::draw(tr);
 
  std::ofstream ofs("out.mesh");
  CGAL::IO::write_MEDIT(ofs, tr);
 
  return EXIT_SUCCESS;
}

5 Design and Implementation History