Jane Tournois
GeometryFactory
The CGAL component 3D Mesh Generation is the primary component to generate isotropic simplicial meshes discretizing 3D domains with CGAL. First introduced in CGAL-3.5 (2009!), this component has been constantly updated through the years to improve its performance, its versatility, and the quality of the meshes it produces.
Recent releases of CGAL have once again introduced new enhancements that enable more accurate representations of input surfaces, for a wider range of input data types. It is now possible to:
- detect and recover sharp features in labeled images,
- generate meshes of weighted labeled images,
- control the maximum error on the approximation error of polyline features.
Recovery of Sharp Features in Labeled Images
CGAL's tetrahedral mesh generation algorithm is able to generate tetrahedral meshes from 3D segmented images. Regardless of input type, one-dimensional feature detection and construction must be performed before the generation of the mesh. In 3D segmented images, these features correspond to the intersections of the bounding box of the image with the surfaces defined by the image, as well as polylines that lie at the intersection of three or more subdomains (including the outside).
The article Hege, H. C., Seebass, M., Stalling, D., & Zöckler, M. (1997), A generalized marching cubes algorithm based on non-binary classifications provides a classification of possible voxel configurations. This description has been generalized for tetrahedral mesh generation needs, and implemented in CGAL.
Following feature lines detection, polyline features are added to the feature graph of the domain for feature protection, similarly to what is done for polyhedral surfaces.
Two new detection functors are introduced to support the protection of triple lines:
CGAL::Detect_features_in_image(): detect and construct all polylines lying at the intersection of three or more subdomains, andCGAL::Detect_features_on_image_bbox(): detect and construct the polylines that lie at the intersection of two or more subdomains and the bounding box of the input labeled image.
Mesh generation from labeled image without (left) and with triple lines detection and protection (right). Protection of the feature lines at the intersection of the three subdomains (pink, blue, outside) enables a much more faithful mesh, with fewer vertices.
Weighted Labeled Images
When a segmented image is given as input for tetrahedral mesh generation,
the generated mesh surface sometimes sticks too closely to the voxels surface, causing an aliasing effect.
A solution to generate a smooth and accurate output surface was described by Stalling et al. in
Stalling, D., Zöckler, M., Sander, O., & Hege, H. C. (1998),
Weighted labels for 3D image segmentation.
The approach consists in generating a second input image made of integer coefficients called weights,
and to use those weights to define smoother domain boundaries.
This addition has been added to CGAL, and the 3D image of weights can be generated using the new function
CGAL::Mesh_3::generate_label_weights().
Mesh generation from labeled image without weights (left, 88,000 vertices) and with weights (right, 67,000 vertices).
The following example shows how to use weighted labeled images: mesh_3D_weighted_image.cpp.
A new method combining triple line protection and weighted labels has been designed and implemented in CGAL, achieving smooth and feature preserving meshes. This method leverages the best of these two new functionalities.
Approximation Criterion for Feature Edges
Our Delaunay refinement algorithm is guided by meshing criteria (size, shape, etc.). When these criteria are not honored, new vertices are inserted until the criteria are satisfied, a process guaranteed to terminate. The list of CGAL meshing criteria has been enriched with a new criterion that enables users to define an upper bound on the distance between the input feature graph and the output feature edges, providing finer control over the mesh features.
The example
mesh_polyhedral_domain_with_edge_distance.cpp shows how to use this new criterion, called edge_distance.
Mesh generation from polyhedral surface with a varying
edge_distance meshing criterion.
The quality improvement is noticeable at the extremities of the stool legs.
Status
All these new improvements are part of CGAL-6.0.1, which has just been officially released.
CGAL-6.0.1 announcement
Documentation of the Tetrahedral Mesh Generation package
CGAL master branch on GitHub
