Re-triangulation

After generating the contour lines, the next crucial step is to triangulate the assembled contour mesh and refine it to create a high-quality final mesh. This process is handled by the triangulateAssembledMesh function within the ContourConstraint class. The function utilizes the CGAL library, specifically the Constrained_Delaunay_triangulation_2 class, to perform the triangulation while respecting the contour constraints.

1. TriangulateAssembledMesh function

The triangulateAssembledMesh function is responsible for taking the non-triangulated mesh, which consists of edges from the computed contour lines, and generating a triangulated mesh that adheres to these constraints. This is crucial for ensuring that the contour lines are preserved in the final mesh.


std::unique_ptr<ContourConstraint::mesh_type> ContourConstraint::triangulateAssembledMesh(mesh_type const &nonTriangulated)
{
    typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
    typedef CGAL::Triangulation_vertex_base_2<K> Vb;
    typedef CGAL::Constrained_triangulation_face_base_2<K> Fb;
    typedef CGAL::Triangulation_data_structure_2<Vb, Fb> Tds;
    typedef CGAL::Constrained_Delaunay_triangulation_2<K, Tds> CDT;
    typedef CDT::Point Point;

    CDT cdt;

    for (const auto &edge : nonTriangulated.edges())
    {
        Point p1(edge->point(0).x(), edge->point(0).y());
        Point p2(edge->point(1).x(), edge->point(1).y());
        cdt.insert_constraint(p1, p2);
    }

    CGAL::make_conforming_Delaunay_2(cdt);

    std::unique_ptr<mesh_type> ret = std::make_unique<mesh_type>();

    for (auto fit = cdt.finite_faces_begin(); fit != cdt.finite_faces_end(); ++fit)
    {
        auto v0 = fit->vertex(0)->point();
        auto v1 = fit->vertex(1)->point();
        auto v2 = fit->vertex(2)->point();
        auto p0 = ret->addPoint(std::make_unique<mesh_type::point_type>(v0.x(), v0.y(), 0));
        auto p1 = ret->addPoint(std::make_unique<mesh_type::point_type>(v1.x(), v1.y(), 0));
        auto p2 = ret->addPoint(std::make_unique<mesh_type::point_type>(v2.x(), v2.y(), 0));

        auto tri = std::make_unique<mesh_type::triangle_type>(p0, p1, p2);
        ret->addTriangle(std::move(tri));
    }
    return ret;
}

2. CGAL and constrained Delaunay triangulation

The CGAL library provides a robust framework for computational geometry, and one of its key offerings is the Constrained_Delaunay_triangulation_2 class. This class extends the concept of Delaunay triangulation by allowing the inclusion of constraints, such as the edges composing the contour lines in our case.

A Delaunay triangulation is a triangulation where no point in the set is inside the circumcircle of any triangle. However, when constraints are applied, such as pre-existing edges that must be part of the triangulation (in this case, contour lines), the triangulation may no longer fulfill the strict Delaunay criterion. This is where constrained Delaunay triangulation (CDT) comes in.

3. How constrained Delaunay triangulation works

  1. Inserting constraints: The triangulateAssembledMesh function begins by iterating over the edges of the non-triangulated mesh. Each edge represents a segment of a contour line. These edges are inserted into the Constrained_Delaunay_triangulation_2 object (cdt) as constraints using the insert_constraint method. This ensures that the resulting triangulation respects the contour lines.

  2. Conforming Delaunay triangulation: Once all constraints are inserted, the CGAL::make_conforming_Delaunay_2 function is called. This function refines the triangulation to ensure that the resulting mesh is as close as possible to a Delaunay triangulation, given the constraints. The refinement involves flipping edges and inserting additional vertices as needed to satisfy the Delaunay condition (source) wherever possible, without violating the constraints.

  3. Generating the final mesh: After the constrained Delaunay triangulation is complete, the function iterates over the faces of the triangulation. For each triangular face, the vertices are added to the final mesh, and the corresponding triangle is created and stored.

4. Implementation in the project

In the provided code, the ContourConstraint class makes extensive use of CDT via the CGAL::Constrained_Delaunay_triangulation_2 class from the CGAL library. This class enables the project to handle complex geometries with constraints, such as terrain contours or other critical boundaries.

The triangulation is performed by inserting constraints—typically line segments or polylines—into the CDT, which then computes a triangulation that honors these constraints while attempting to maintain as much of the Delaunay property as possible.

Here’s a brief overview of how this is applied in the code:

  • Constraint insertion: Constraints are inserted using the insert_constraint method of CGAL::Constrained_Delaunay_triangulation_2, which ensures that the specified edges appear in the triangulation.

  • Triangulation: Once the constraints are in place, the CDT algorithm generates the triangulated mesh, which is then used for further processing or export.

  • Post-processing: After triangulation, additional steps such as merging duplicate points and restoring the original heights (z-values) of vertices are performed to refine the mesh.

The following key features and types from the CGAL library are used:

  • Traits: Defines the geometric properties and operations needed for the triangulation.

  • Tds: The Triangulation Data Structure, which organizes the vertices, edges, and faces of the triangulation.

  • Itag: Determines how the intersection of constraints is handled.

In summary, the triangulateAssembledMesh function leverages CGAL's Constrained_Delaunay_triangulation_2 to create a high-quality, triangulated mesh that respects the original contour lines. This process is critical for maintaining the accuracy of the terrain model while reducing the complexity of the mesh.


Next: Exporting and visualization


References