User Manual

Author

François Protais

Volume Mesh Smoothing and Geometric Fitting

This package implements an optimization algorithm for improving the quality of volumetric meshes and fitting them to geometric targets, based on the method described in [1]. It can be used to improve an already valid mesh, untangle an invalid mesh, or deform a mesh so that its boundary follows a prescribed geometry.

The algorithm only modifies vertex coordinates. It does not insert or remove vertices, change cell connectivity, or alter the combinatorial structure of the input mesh. Consequently, cell indices, material labels, adjacency relations, and other data attached to the mesh are preserved throughout the optimization. When changes to the mesh connectivity or element sizing are required, the Tetrahedral Remeshing package should be used instead.

Smoothing and Fitting Algorithm

The algorithm optimizes vertex positions according to an element-quality energy. It currently uses a conformal energy (MIPS3D) that improves the dihedral angles of the cells. Interior vertices are moved to improve the volume mesh, while boundary vertices can additionally be attracted towards a target geometry.

The energy incorporates a barrier term preventing element inversion. For an initially valid mesh, all accepted optimization steps preserve element orientation, providing a validity guarantee while the element quality is improved. The use of a penalization approach also allows the optimizer to start from an invalid mesh and recover a valid configuration by untangling inverted elements.

Geometric targets can be specified at several dimensions:

• surface targets constrain boundary polygons to locally estimated tangent planes;
• curve targets constrain selected mesh edges to target tangent directions;
• point targets attract individual vertices to prescribed positions.

Surface patches and curves may be assigned different identifiers, allowing different parts of the mesh to use different target geometries. Constraints are soft and weighted by default, so geometric fidelity can be balanced against element quality. Vertices, or individual coordinate dimensions, can also be locked when hard constraints are required. Combining surface, curve, and point targets allows smooth regions, sharp curves, corners, and user handles to be treated within the same optimization.

By recovering the tangent planes of the target geometry, the smoother can recover curvature discontinuities, enabling automatic feature recovery and preservation.

API

The main function of the package is CGAL::boundary_aware_mesh_smoothing(), which takes a CGAL::Mesh_complex_3_in_triangulation_3 as input mesh and a ConstructTangentSpace for re-projections. It then updates its vertex coordinates to improve element quality and fit geometric targets.

CGAL::Mesh_smoothing_3::C3t3_mesh_projector provides a model of ConstructTangentSpace to re-project the input mesh into another mesh represented by a CGAL::Mesh_complex_3_in_triangulation_3.

Warning

The algorithm relocates vertices without updating the connectivity of the triangulation. Therefore, if the input triangulation satisfies a Delaunay or regular triangulation property, this property is not maintained and must be considered lost after smoothing.

Untangling an invalid mesh without any boundary constraints or fitting terms will result in a collapsed mesh. It is a current limitation of the optimization approach.

Examples

Direct Smoothing of a C3t3

The following example demonstrates the direct use of the smoother on a CGAL::Mesh_complex_3_in_triangulation_3. A C3t3 is read from a Medit file with its surface patches, and CGAL::boundary_aware_mesh_smoothing() is then called to improve the mesh quality while preserving the input surface patches.

Note that the CGAL reader does not currently read feature edges from Medit files, so the current example only preserves input patches.

Figure 69.1 Running the smoother on mambo_m3.mesh slightly improves the dihedral angles, as the initial mesh is already of good quality for its current geometric target. The elements can slide along their respective patches while preserving sharpness and key features. The bunny.mesh file only contains volume elements; consequently, the smoother does not attempt to preserve any boundary surface. The resulting boundary is therefore less geometrically regular, but the quality of the volume elements is significantly improved.

Example: Mesh_smoothing_3/c3t3_smooth.cpp

Show / Hide

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
 
#include <CGAL/Triangulation_3.h>
#include <CGAL/Triangulation_data_structure_3.h>
#include <CGAL/Simplicial_mesh_cell_base_3.h>
#include <CGAL/Simplicial_mesh_vertex_base_3.h>
#include <CGAL/Mesh_complex_3_in_triangulation_3.h>
 
#include <CGAL/tags.h>
 
#include <CGAL/IO/File_medit.h>
#include <fstream>
 
#include <CGAL/Mesh_smoothing_3/boundary_aware_mesh_smoothing.h>
#include <CGAL/Mesh_smoothing_3/projectors.h>
 
using K = CGAL::Exact_predicates_inexact_constructions_kernel;
 
using Subdomain_index = int;
using Surface_patch_index = unsigned;
using Curve_index = unsigned;
using Corner_index = unsigned;
 
using Cb = CGAL::Simplicial_mesh_cell_base_3<K, Subdomain_index, Surface_patch_index>;
using Vb = CGAL::Simplicial_mesh_vertex_base_3<K, Subdomain_index, Surface_patch_index,
                                                  Curve_index, Corner_index>;
 
using Tds = CGAL::Triangulation_data_structure_3<Vb, Cb, CGAL::Sequential_tag>;
using Triangulation = CGAL::Triangulation_3<K, Tds>;
 
using C3t3 = CGAL::Mesh_complex_3_in_triangulation_3<Triangulation>;
 
 
int main(int argc, char* argv[])
{
    std::string filename = (argc > 1) ? std::string(argv[1])
                                      : "../data/mambo_m3.mesh";
 
    C3t3 c3t3;
 
    std::ifstream is(filename, std::ios_base::in);
    if(!CGAL::IO::read_MEDIT(is,c3t3.triangulation()))
    {
      std::cerr << "Failed to read" << std::endl;
      return EXIT_FAILURE;
    }
    c3t3.rescan_after_load_of_triangulation();
 
    std::ofstream os("c3t3_initial.mesh");
    CGAL::IO::write_MEDIT(os, c3t3.triangulation(), CGAL::parameters::all_vertices(true));
    os.close();
 
    auto result =
    CGAL::boundary_aware_mesh_smoothing(
        c3t3,
        CGAL::Mesh_smoothing_3::C3t3_mesh_projector(c3t3),
        CGAL::parameters::verbose(true).number_of_iterations(100)
    );
 
    std::cout << "Number of inverted elements: " << result.nb_invalid_elements << std::endl;
    std::cout << "Number of vertex updates: " << result.nb_vertex_updates << std::endl;
    std::cout << "Pre-processing time: " << result.pre_processing_time << std::endl;
    std::cout << "Smoothing time: " << result.optimization_time << std::endl;
 
    std::ofstream os2("c3t3_smoothed.mesh");
    CGAL::IO::write_MEDIT(os2, c3t3.triangulation(), CGAL::parameters::all_vertices(true));
    os2.close();
 
    std::cout << "Done" << std::endl;
    return EXIT_SUCCESS;
 
}
 
 
 
 

Implementation History

The optimization method implemented in this package was introduced by François Protais, Gianmarco Cherchi, and Marco Livesu in [1].

The original implementation was developed as part of the Mesh_optimization project. The CGAL implementation was subsequently adapted to operate directly on CGAL::Mesh_complex_3_in_triangulation_3 objects and to expose the geometric fitting mechanism through the concepts ConstructTangentSpace and TangentSpace.

It was initially published in CGAL-6.3.