|
CGAL 4.14 - Polygon Mesh Processing
|
|
CGAL 4.14 - Polygon Mesh Processing
|
This package implements a collection of methods and classes for polygon mesh processing, ranging from basic operations on simplices, to complex geometry processing algorithms. The implementation of this package mainly follows algorithms and references given in Botsch et al.'s book on polygon mesh processing [4].
A polygon mesh is a consistent and orientable surface mesh, that can have one or more boundaries. The faces are simple polygons. The edges are segments. Each edge connects two vertices, and is shared by two faces (including the null face for boundary edges). A polygon mesh can have any number of connected components, and also some self-intersections. In this package, a polygon mesh is considered to have the topology of a 2-manifold.
This package follows the BGL API described in CGAL and the Boost Graph Library. It can thus be used either with Polyhedron_3, Surface_mesh, or any class model of the concept FaceGraph. Each function or class of this package details the requirements on the input polygon mesh.
Named Parameters are used to deal with optional parameters. The page Named Parameters for Polygon Mesh Processing describes their usage and provides a list of the parameters that are used in this package.
The algorithms described in this manual are organized in sections:
A surface patch can be refined by inserting new vertices and flipping edges to get a triangulation. Using a criterion presented in [6], the density of triangles near the boundary of the patch is approximated by the refinement function. The validity of the mesh is enforced by flipping edges. An edge is flipped only if the opposite edge does not exist in the original mesh and if no degenerate triangles are generated.
A region of the surface mesh (e.g. the refined region), can be faired to obtain a tangentially continuous and smooth surface patch. The region to be faired is defined as a range of vertices that are relocated. The fairing step minimizes a linear bi-Laplacian system with boundary constraints, described in [3]. The visual results of aforementioned steps are depicted by Figure 63.7 (c and d).
Refinement and fairing functions can be applied to an arbitrary region on a triangle mesh, using :
CGAL::Polygon_mesh_processing::refine() : given a set of facets on a mesh, refines the region.CGAL::Polygon_mesh_processing::fair() : given a set of vertices on a mesh, fairs the region.Fairing needs a sparse linear solver and we recommend the use of Eigen 3.2 or later. Note that fairing might fail if fixed vertices, which are used as boundary conditions, do not suffice to solve the constructed linear system.
Many algorithms require as input meshes in which all the faces have the same degree, or even are triangles. Hence, one may want to triangulate all polygon faces of a mesh.
This package provides the function CGAL::Polygon_mesh_processing::triangulate_faces() that triangulates all faces of the input polygon mesh. An approximated support plane is chosen for each face, orthogonal to the normal vector computed by CGAL::Polygon_mesh_processing::compute_face_normal(). Then, the triangulation of each face is the one obtained by building a CGAL::Constrained_Delaunay_triangulation_2 in this plane. This choice is made because the constrained Delaunay triangulation is the triangulation that, given the edges of the face to be triangulated, maximizes the minimum angle of all the angles of the triangles in the triangulation.
The incremental triangle-based isotropic remeshing algorithm introduced by Botsch et al [2], [4] is implemented in this package. This algorithm incrementally performs simple operations such as edge splits, edge collapses, edge flips, and Laplacian smoothing. All the vertices of the remeshed patch are reprojected to the original surface to keep a good approximation of the input.
A triangulated region of a polygon mesh can be remeshed using the function CGAL::Polygon_mesh_processing::isotropic_remeshing(), as illustrated by Figure 63.1. The algorithm has only two parameters : the target edge length for the remeshed surface patch, and the number of iterations of the abovementioned sequence of operations. The bigger this number, the smoother and closer to target edge length the mesh will be.
An additional option has been added to protect (i.e. not modify) some given polylines. In some cases, those polylines are too long, and reaching the desired target edge length while protecting them is not possible and leads to an infinite loop of edge splits in the incident faces. To avoid that pitfall, the function CGAL::Polygon_mesh_processing::split_long_edges() should be called on the list of constrained edges before remeshing.
The following example calls the functions CGAL::Polygon_mesh_processing::refine() and CGAL::Polygon_mesh_processing::fair() for some selected regions on the input triangle mesh.
File Polygon_mesh_processing/refine_fair_example.cpp
Triangulating a polygon mesh can be achieved through the function CGAL::Polygon_mesh_processing::triangulate_faces() as shown in the following example.
File Polygon_mesh_processing/triangulate_faces_example.cpp
The following example shows a complete example of how the isotropic remeshing function can be used. First, the border of the polygon mesh is collected. Since the boundary edges will be considered as constrained and protected in this example, the function split_long_edges() is called first on these edges.
Once this is done, remeshing is run on all the surface, with protection of constraints activated, for 3 iterations.
File Polygon_mesh_processing/isotropic_remeshing_example.cpp
Corefinement Given two triangulated surface meshes, the corefinement operation consists in refining both meshes so that their intersection polylines are a subset of edges in both refined meshes.
Volume bounded by a triangulated surface mesh Given a closed triangulated surface mesh, each connected component splits the 3D space into two subspaces. The vertex sequence of each face of a component is seen either clockwise or counterclockwise from these two subspaces. The subspace that sees the sequence clockwise (resp. counterclockwise) is on the negative (resp. positive) side of the component. Given a closed triangulated surface mesh tm with no self-intersections, the connected components of tm divide the 3D space into subspaces. We say that tm bounds a volume if each subspace lies exclusively on the positive (or negative) side of all the incident connected components of tm. The volume bounded by tm is the union of all subspaces that are on negative sides of their incident connected components of tm.
The corefinement of two triangulated surface meshes can be done using the function CGAL::Polygon_mesh_processing::corefine(). It takes as input the two triangulated surface meshes to corefine. If constrained edge maps are provided, edges belonging to the intersection of the input meshes will be marked as constrained. In addition, if an edge that was marked as constrained is split during the corefinement, sub-edges will be marked as constrained as well.
C and S be the volumes bounded by the triangulated surface meshes of a cube and a sphere, respectively. From left to right, the picture shows the triangulated surface meshes bounding the union of C and S, C minus S, the intersection of C and S and S minus C. The corefinement of two triangulated surface meshes can naturally be used for computing Boolean operations on volumes. Considering two triangulated surface meshes, each bounding a volume, the functions CGAL::Polygon_mesh_processing::corefine_and_compute_union(), CGAL::Polygon_mesh_processing::corefine_and_compute_intersection() and CGAL::Polygon_mesh_processing::corefine_and_compute_difference() respectively compute the union, the intersection and the difference of the two volumes. If several Boolean operations must be computed at the same time, the function corefine_and_compute_boolean_operations() should be used.
There is no restriction on the topology of the input volumes. However, there are some requirements on the input to guarantee that the operation is possible. First, the input meshes must not self-intersect. Second, the operation is possible only if the output can be bounded by a manifold triangulated surface mesh. In particular this means that the output volume has no part with zero thickness. Mathematically speaking, the intersection with an infinitesimally small ball centered in the output volume is a topological ball. At the surface level this means that no non-manifold vertex or edge is allowed in the output. For example, it is not possible to compute the union of two cubes that are disjoint but sharing an edge. In case you have to deal with such scenarios, you should consider using the package 3D Boolean Operations on Nef Polyhedra.
It is possible to update the input so that it contains the result (in-place operation). In that case the whole mesh will not be copied and only the region around the intersection polyline will be modified. In case the Boolean operation is not possible, the input mesh will nevertheless be corefined.
The corefinement operation (which is also internally used in the three Boolean operations) will correctly change the topology of the input surface mesh if the point type used in the point property maps of the input meshes is from a CGAL Kernel with exact predicates. If that kernel does not have exact constructions, the embedding of the output surface mesh might have self-intersections. In case of consecutive operations, it is thus recommended to use a point property map with points from a kernel with exact predicates and exact constructions (such as CGAL::Exact_predicates_exact_constructions_kernel).
In practice, this means that with exact predicates and inexact constructions, edges will be split at each intersection with a triangle but the position of the intersection point might create self-intersections due to the limited precision of floating point numbers.
As a natural extension, some clipping functionalities with a volume bounded by a closed mesh and a halfspace (defined by the negative side of a plane to be consistent with the outward normal convention) are offered. The functions CGAL::Polygon_mesh_processing::clip() have some options to select whether the clipping should be done at the volume or surface level, and also if the clipper should be considered as compact or not. This is illustrated on Figure 63.5 and Figure 63.6.
close_volumes=false: clipping of the surface mesh (boundary edges depicted in red); (iii) close_volumes=true: clipping of the volume bounded by the surface mesh. 
close_volumes=false in both cases). From left to right: (i) initial cube and the plane defining the clipping halfspace, note that a whole face of the cube (2 triangles) is exactly contained in the plane; (ii) use_compact_clipper=true: clipping of the surface mesh with a compact halfspace: coplanar faces are part of the output; (iii) use_compact_clipper=false: clipping of the surface mesh with a non-compact halfspace: coplanar faces are not part of the output.
File Polygon_mesh_processing/corefinement_mesh_union.cpp
This example is similar to the previous one, but here we substract a volume and update the first input triangulated surface mesh (in-place operation). The edges that are on the intersection of the input meshes are marked and the region around them is remeshed isotropically while preserving the intersection polyline.
File Polygon_mesh_processing/corefinement_difference_remeshed.cpp
This example computes the intersection of two volumes and then does the union of the result with one of the input volumes. This operation is in general not possible when using inexact constructions. Instead of using a mesh with a point from a kernel with exact constructions, the exact points are a property of the mesh vertices that we can reuse in a later operations. With that property, we can manipulate a mesh with points having floating point coordinates but benefit from the robustness provided by the exact constructions.
File Polygon_mesh_processing/corefinement_consecutive_bool_op.cpp
This package provides an algorithm for filling one closed hole that is either in a triangulated surface mesh or defined by a sequence of points that describe a polyline. The main steps of the algorithm are described in [6] and can be summarized as follows.
First, the largest patch triangulating the boundary of the hole is generated without introducing any new vertex. The patch is selected so as to minimize a quality function evaluated for all possible triangular patches. The quality function first minimizes the worst dihedral angle between patch triangles, then the total surface area of the patch as a tiebreaker. Following the suggestions in [7], the performance of the algorithm is significantly improved by narrowing the search space to faces of a 3D Delaunay triangulation of the hole boundary vertices, from all possible patches, while searching for the best patch with respect to the aforementioned quality criteria.
For some complicated input hole boundary, the generated patch may have self-intersections. After hole filling, the generated patch can be refined and faired using the meshing functions CGAL::Polygon_mesh_processing::refine() and CGAL::Polygon_mesh_processing::fair() described in Section Meshing.
This package provides four functions for hole filling:
triangulate_hole_polyline() : given a sequence of points defining the hole, triangulates the hole.triangulate_hole() : given a border halfedge on the boundary of the hole on a mesh, triangulates the hole.triangulate_and_refine_hole() : in addition to triangulate_hole() the generated patch is refined.triangulate_refine_and_fair_hole() : in addition to triangulate_and_refine_hole() the generated patch is also faired.The following example triangulates a hole described by an input polyline.
File Polygon_mesh_processing/triangulate_polyline_example.cpp
If the input polygon mesh has a hole or more than one hole, it is possible to iteratively fill them by detecting border edges (i.e. with only one incident non-null face) after each hole filling step.
Holes are filled one after the other, and the process stops when there is no border edge left.
This process is illustrated by the example below, where holes are iteratively filled, refined and faired to get a faired mesh with no hole.
File Polygon_mesh_processing/hole_filling_example.cpp
The hole filling algorithm has a complexity which depends on the number of vertices. While [6] has a running time of \( O(n^3)\) , [7] in most cases has running time of \( O(n \log n)\). We benchmarked the function triangulate_refine_and_fair_hole() for the two meshes below (as well as two more meshes with smaller holes). The machine used was a PC running Windows 10 with an Intel Core i7 CPU clocked at 2.70 GHz. The program was compiled with the Visual C++ 2013 compiler with the O2 option, which maximizes speed.
The following running times were observed:
| # vertices | without Delaunay (sec.) | with Delaunay (sec.) |
|---|---|---|
| 565 | 8.5 | 0.03 |
| 774 | 21 | 0.035 |
| 967 | 43 | 0.06 |
| 7657 | na | 0.4 |
This packages provides several predicates to be evaluated with respect to a triangle mesh.
Intersection tests between triangle meshes and/or polylines can be done using CGAL::Polygon_mesh_processing::do_intersect() . Additionally, the function CGAL::Polygon_mesh_processing::intersecting_meshes() records all pairs of intersecting meshes in a range.
Self intersections within a triangle mesh can be detected by calling the function CGAL::Polygon_mesh_processing::does_self_intersect(). Additionally, the function CGAL::Polygon_mesh_processing::self_intersections() reports all pairs of intersecting triangles.
The following example illustrates the detection of self intersection in the pig.off mesh. The detected self-intersection is illustrated on Figure Figure 63.10.
File Polygon_mesh_processing/self_intersections_example.cpp
The class CGAL::Side_of_triangle_mesh provides a functor that tests whether a query point is inside, outside, or on the boundary of the domain bounded by a given closed triangle mesh.
A point is said to be on the bounded side of the domain bounded by the input triangle mesh if an odd number of surfaces is crossed when walking from the point to infinity. The input triangle mesh is expected to contain no self-intersections and to be free from self-inclusions.
The algorithm can handle the case of a triangle mesh with several connected components, and returns correct results. In case of self-inclusions, the ray intersections parity test is performed, and the execution will not fail. However, the user should be aware that the predicate alternately considers sub-volumes to be on the bounded and unbounded sides of the input triangle mesh.
File Polygon_mesh_processing/point_inside_example.cpp
Badly shaped or, even worse, completely degenerate elements of a polygon mesh are problematic in many algorithms which one might want to use on the mesh. This package offers a toolkit of functions to detect such undesirable elements.
CGAL::Polygon_mesh_processing::is_degenerate_edge(), to detect if an edge is degenerate (that is, if its two vertices share the same geometric location).CGAL::Polygon_mesh_processing::is_degenerate_triangle_face(), to detect if a face is degenerate (that is, if its three vertices are collinear).CGAL::Polygon_mesh_processing::degenerate_edges(), to collect degenerate edges within a range of edges.CGAL::Polygon_mesh_processing::degenerate_faces(), to collect degenerate faces within a range of faces.CGAL::Polygon_mesh_processing::is_cap_triangle_face()CGAL::Polygon_mesh_processing::is_needle_triangle_face()This package offers multiple functions to compute consistent face orientations for set of faces (Section Polygon Soups) and polygon meshes (Section Polygon Meshes). Section Orientation Example offers an example of combination of these functions.
When the faces of a polygon mesh are given but the connectivity is unknown, this set of faces is called a polygon soup.
Before running any of the algorithms on a polygon soup, one should ensure that the polygons are consistently oriented. To do so, this package provides the function CGAL::Polygon_mesh_processing::orient_polygon_soup(), described in [1].
To deal with polygon soups that cannot be converted to a combinatorially manifold surface, some points must be duplicated. Because a polygon soup does not have any connectivity (each point has as many occurences as the number of polygons it belongs to), duplicating one point (or a pair of points) amounts to duplicating the polygon to which it belongs. The duplicated points are either an endpoint of an edge incident to more than two polygons, an endpoint of an edge between two polygons with incompatible orientations (during the re-orientation process), or more generally a point p at which the intersection of an infinitesimally small ball centered at p with the polygons incident to it is not a topological disk.
Once the polygon soup is consistently oriented, with possibly duplicated (or more) points, the connectivity can be recovered and made consistent to build a valid polygon mesh. The function CGAL::Polygon_mesh_processing::polygon_soup_to_polygon_mesh() performs this mesh construction step.
This package provides functions dealing with the orientation of faces in a closed polygon mesh.
CGAL::Polygon_mesh_processing::orient() makes each connected component of a closed polygon mesh outward- or inward-oriented.CGAL::Polygon_mesh_processing::orient_to_bound_a_volume() orients the connected components of a closed polygon mesh so that it bounds a volume (see Definitions for the precise definition).CGAL::Polygon_mesh_processing::is_outward_oriented() checks whether an oriented polygon mesh is oriented such that the normals to all faces are oriented towards the outside of the domain bounded by the input polygon mesh.CGAL::Polygon_mesh_processing::reverse_face_orientations() reverses the orientation of halfedges around faces. As a consequence, the normal computed for each face (see Section Computing Normals) is also reversed.This example shows how to generate a mesh from a polygon soup. The first step is to get a soup of consistently oriented faces, before rebuilding the connectivity. In this example, some orientation tests are performed on the output polygon mesh to illustrate Section Orientation.
File Polygon_mesh_processing/orient_polygon_soup_example.cpp
To ensure that a polygon soup can be oriented (see Section Polygon Soups) and transformed into a workable polygon mesh, it might be necessary to preprocess the data to remove combinatorial and geometrical errors. This package offers the following functions:
CGAL::Polygon_mesh_processing::merge_duplicate_points_in_polygon_soup(),CGAL::Polygon_mesh_processing::merge_duplicate_polygons_in_polygon_soup(),CGAL::Polygon_mesh_processing::remove_isolated_points_in_polygon_soup(),as well as the function CGAL::Polygon_mesh_processing::repair_polygon_soup(), which bundles the previous functions and an additional handful of repairing techniques to obtain an as-clean-as-possible polygon soup.
It happens that a polygon mesh has several edges and vertices that are duplicated. For those edges and vertices, the connectivity of the mesh is incomplete, if not considered incorrect.
Stitching the borders of such a polygon mesh consists in two main steps. First, border edges that are similar but duplicated are detected and paired. Then, they are "stitched" together so that the edges and vertices duplicates are removed from the mesh, and each of these remaining edges is incident to exactly two faces.
The function CGAL::Polygon_mesh_processing::stitch_borders() performs such repairing operation. The input mesh should be manifold. Otherwise, stitching is not guaranteed to succeed.
The following example applies the stitching operation to a simple quad mesh with duplicated border edges.
File Polygon_mesh_processing/stitch_borders_example.cpp
This package offers repairing methods to clean ill-formed polygon soups, see Section Combinatorial Repairing.
Non-manifold vertices can be detected using the function CGAL::Polygon_mesh_processing::is_non_manifold_vertex(). The function CGAL::Polygon_mesh_processing::duplicate_non_manifold_vertices() can be used to attempt to create a combinatorially manifold surface mesh by splitting any non-manifold vertex into as many vertices as there are manifold sheets at this geometric position. Note however that the mesh will still not be manifold from a geometric point of view, as the positions of the new vertices introduced at a non-manifold vertex are identical to the input non-manifold vertex.
In the following example, a non-manifold configuration is artifically created and fixed with the help of the functions described above.
File Polygon_mesh_processing/manifoldness_repair_example.cpp
Similarly to the problematic configuration described in the previous section, another issue that can be present in a polygon mesh is the occurrence of a "pinched" hole, that is the configuration where, when starting from a border halfedge and walking the halfedges of this border, a geometric position appears more than once (although, with different vertices) before reaching the initial border halfedge again. The functions CGAL::Polygon_mesh_processing::merge_duplicated_vertices_in_boundary_cycle() and CGAL::Polygon_mesh_processing::merge_duplicated_vertices_in_boundary_cycle(), which merge vertices at identical positions, can be used to repair this configuration.
This package provides methods to compute normals on the polygon mesh. The normal can either be computed for each single face, or estimated for each vertex, as the average of its incident face normals. These computations are performed with :
CGAL::Polygon_mesh_processing::compute_face_normal()CGAL::Polygon_mesh_processing::compute_vertex_normal()Furthermore, we provide functions to compute all the normals to faces, or to vertices, or to both :
CGAL::Polygon_mesh_processing::compute_face_normals()CGAL::Polygon_mesh_processing::compute_vertex_normals()CGAL::Polygon_mesh_processing::compute_normals().Property maps are used to record the computed normals.
Property maps are an API introduced in the boost library that allows to associate values to keys. In the following examples we associate a normal vector to each vertex and to each face.
The following example illustrates how to compute the normals to faces and vertices and store them in property maps provided by the class Surface_mesh.
File Polygon_mesh_processing/compute_normals_example.cpp
The following example illustrates how to compute the normals to faces and vertices and store them in ordered or unordered maps as the class Polyhedron_3 does not provide storage for the normals.
File Polygon_mesh_processing/compute_normals_example_Polyhedron.cpp
The CGAL::Polygon_mesh_slicer is an operator that intersects a triangle surface mesh with a plane. It records the intersection as a set of polylines since the intersection can be made of more than one connected component. The degenerate case where the intersection is a single point is handled.
Figure 63.11 shows the polylines returned by the slicing operation for a triangle mesh and a set of parallel planes.
The example below illustrates how to use the mesh slicer for a given triangle mesh and a plane. Two constructors are used in the example for pedagogical purposes.
File Polygon_mesh_processing/mesh_slicer_example.cpp
This package provides functions to enumerate and store the connected components of a polygon mesh. The connected components can be either closed and geometrically separated, or separated by border or user-specified constraint edges.
First, the function CGAL::Polygon_mesh_processing::connected_component() collects all the faces that belong to the same connected component as the face that is given as a parameter.
Then, CGAL::Polygon_mesh_processing::connected_components() collects all the connected components, and fills a property map with the indices of the different connected components.
The functions CGAL::Polygon_mesh_processing::keep_connected_components() and CGAL::Polygon_mesh_processing::remove_connected_components() enable the user to keep and remove only a selection of connected components, provided either as a range of faces that belong to the desired connected components or as a range of connected component ids (one or more per connected component).
Finally, CGAL::Polygon_mesh_processing::keep_largest_connected_components() enables the user to keep only the largest connected components. This feature can for example be useful for noisy data were small connected components should be discarded in favour of major connected components.
The first example shows how to record the connected components of a polygon mesh. In particular, we provide an example for the optional parameter EdgeConstraintMap, a property map that returns information about an edge being a constraint or not. A constraint provides a mean to demarcate the border of a connected component, and prevents the propagation of a connected component index to cross it.
File Polygon_mesh_processing/connected_components_example.cpp
The second example shows how to use the class template Face_filtered_graph which enables to treat one or several connected components as a face graph.
File Polygon_mesh_processing/face_filtered_graph_example.cpp
This package provides methods to compute (approximate) distances between meshes and point sets.
The function approximate_Hausdorff_distance() computes an approximation of the Hausdorff distance from a mesh tm1 to a mesh tm2. Given a a sampling of tm1, it computes the distance to tm2 of the farthest sample point to tm2 [5]. The symmetric version (approximate_symmetric_Hausdorff_distance()) is the maximum of the two non-symmetric distances. Internally, points are sampled using sample_triangle_mesh() and the distance to each sample point is computed using max_distance_to_triangle_mesh(). The quality of the approximation depends on the quality of the sampling and the runtime depends on the number of sample points. Three sampling methods with different parameters are provided (see Figure 63.12).
The function approximate_max_distance_to_point_set() computes an approximation of the Hausdorff distance from a mesh to a point set. For each triangle, a lower and upper bound of the Hausdorff distance to the point set are computed. Triangles are refined until the difference between the bounds is lower than a user-defined precision threshold.
In the following example, a mesh is isotropically remeshed and the approximate distance between the input and the output is computed.
File Polygon_mesh_processing/hausdorff_distance_remeshing_example.cpp
In Poisson_surface_reconstruction_3/poisson_reconstruction_example.cpp, a triangulated surface mesh is constructed from a point set using the Poisson reconstruction algorithm , and the distance between the point set and the reconstructed surface is computed with the following code:
This package provides methods to detect some features of a polygon mesh.
The function CGAL::Polygon_mesh_processing::sharp_edges_segmentation() detects the sharp edges of a polygon mesh and deduces surface patches and vertices incidences. It can be split into three functions : CGAL::Polygon_mesh_processing::detect_sharp_edges(), CGAL::Polygon_mesh_processing::connected_components() and CGAL::Polygon_mesh_processing::detect_vertex_incident_patches(), that respectively detect the sharp edges, compute the patch indices, and give each of pmesh vertices the patch indices of its incident faces.
In the following example, we count how many edges of pmesh are incident to two faces whose normals form an angle smaller than 90 degrees, and the number of surface patches that are separated by these edges.
File Polygon_mesh_processing/detect_features_example.cpp
A first version of this package was started by Ilker O. Yaz and Sébastien Loriot. Jane Tournois worked on the finalization of the API, code, and documentation.
1.8.13