|
CGAL 6.2 - Boolean Operations on Meshes
|
Loading...
Searching...
No Matches
|
CGAL 6.2 - Boolean Operations on Meshes
|
The computation of mesh Boolean operations is one of the most essential parts of the geometry processing toolkit, with numerous applications in CAD and computer graphics. As an example, it constitutes the essential operation of Constructive Solid Geometry (CSG).
This CGAL package offers functions to compute the union, intersection, and difference of volumes bounded by triangle meshes. The core of the method is the corefinement technique, which refines two meshes such that they become conformal. This technique is re-used to also propose functions that enable trimming a mesh ("clipping") and bisecting a mesh ("splitting") with a plane, a box, or another mesh.
We begin by introducing the core concepts of this package in Definitions. Mesh Boolean functions and their input requirements are described in Computing Mesh Boolean Operations, and the guarantees on the output are discussed in Kernel Choice and Output Validity. Related functions for clipping, splitting, and slicing are documented in Clipping and Splitting Meshes and Slicer.
CGAL does exact stuff, and handles degeneracies. [TODO]
Corefinement: Given two triangulated surface meshes, the corefinement of these two meshes consists in refining both meshes such that their intersection polylines form a subset of the edges of both refined meshes.
Autorefinement: Given a triangle mesh or a triangle soup, the autorefinement consists in refining the mesh/soup such that all intersections between triangles form a subset of the edges of the output.
Figure 76.2 Corefinement of two triangulated surface meshes. (Left) Input meshes; (Right) The two input meshes after corefinement. The common edges of the two meshes are drawn in green.
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 in a clockwise (resp. counterclockwise) manner 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.
Figure 76.3 Volumes bounded by a triangulated surface mesh: The figure shows meshes representing three nested spheres (three connected components). The left side of the picture shows a clipped triangulated surface mesh, with the two possible orientations of the faces for which a volume is bounded by the mesh. The positive and negative sides of each connected component are displayed in light and dark blue, respectively. The right part of the picture shows clipped tetrahedral meshes of the corresponding bounded volumes.
Corefinement of two triangulated surface meshes can be performed using the function CGAL::Polygon_mesh_processing::corefine(). If constrained edge maps are provided, edges belonging to the intersection of the input meshes will be marked as constrained. Additionally, if a constrained edge is split during corefinement, the resulting sub-edges will also be marked as constrained.
Example: Polygon_mesh_processing/corefinement_SM.cpp
The function CGAL::Polygon_mesh_processing::autorefine_triangle_soup() provides a way to refine a triangle soup using the intersections of the triangles from the soup. In particular, if some points are duplicated they will be merged.
Example: Polygon_mesh_processing/soup_autorefinement.cpp
Corefinement of two triangulated surface meshes is a natural basis for computing Boolean operations on volumes. Given two triangulated surface meshes, each bounding a volume, the following functions are provided:
CGAL::Polygon_mesh_processing::corefine_and_compute_union(),CGAL::Polygon_mesh_processing::corefine_and_compute_intersection(),CGAL::Polygon_mesh_processing::corefine_and_compute_difference().respectively compute the union, intersection, and difference of the two volumes.
If several Boolean operations must be computed at the same time, the function CGAL::Polygon_mesh_processing::corefine_and_compute_boolean_operations() should be used as to factorize the corefinement operation, which makes up for the essential of the runtime.
The following basic example illustrates how to compute the union of two meshes:
Example: Polygon_mesh_processing/corefinement_mesh_union.cpp
Figure 76.4 Let 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.
There are no restrictions on the topology of the input volumes. However, certain requirements must be met to ensure that the operation is feasible. First, the input meshes must not self-intersect. Second, the operation is only possible if the output can be bounded by a manifold triangulated surface mesh. In particular, this means that the output volume must not contain regions of zero thickness. Mathematically, the intersection with an infinitesimally small ball centered at any point of the output volume must be 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 share an edge. If such scenarios arise, 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 this case, the entire mesh is not copied; only the region around the intersection polyline is modified. However, note that if the Boolean operation is not possible, the input mesh will still be corefined.
The corefinement operation (which is also used internally in the Boolean operations) will correctly modify 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 the kernel does not provide exact constructions, the embedding of the output surface mesh may contain self-intersections. For consecutive operations, it is 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.
For the specific case of CGAL::Polygon_mesh_processing::autorefine_triangle_soup(), the option apply_iterative_snap_rounding is a robust heuristic to resolve this issue. When set to true, it ensures that coordinates are rounded to fit in double with potential additional subdivisions, preventing self-intersections.
The following table illustrates the strength of the approach over the 10 000 models of the Thingi10k data set, demonstrating that naive rounding to floating point types is insufficient and fails to eliminate all self-intersections despite autorefinement, whereas the combination of autorefinement and iterative snap rounding resolves all of them on all meshes:
| Inputs with self-intersections | Autorefinement with naive rounding | Autorefinement with iterative snap rounding | ||
| 3870 | 529 | 0 | ||
This example is similar to the previous one, but here we subtract 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.
Example: Polygon_mesh_processing/corefinement_difference_remeshed.cpp
This example computes the intersection of two volumes and then performs 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 points from a kernel with exact constructions, the exact points are stored as a property of the mesh vertices and can be reused in later operations. With this property, it is possible to manipulate a mesh with points having floating point coordinates while benefiting from the robustness provided by exact constructions.
Example: Polygon_mesh_processing/corefinement_consecutive_bool_op.cpp
The corefinement of two meshes can be also used to provide clipping functionalities with a volume bounded by a closed mesh and a clipper. The clipper can be a plane, a box, or another closed mesh. For example, in the case of plane clipping, the input mesh is corefined with the plane, and all parts of the mesh lying on the negative side of the plane are retained. Alternatively, one may choose not to discard any part, but simply split the input according to a plane, box, or mesh. This operation is called splitting.
The functions implementing these operations are:
Both functions offer options to select whether clipping should be performed at the volume or surface level, and whether the clipper should be considered compact. This is illustrated in Figure 76.5 and Figure 76.6.
Figure 76.5 Clipping a cube with a halfspace. From left to right: (i) initial cube and the plane defining the clipping halfspace; (ii) clip_volume=false: clipping of the surface mesh (boundary edges depicted in red); (iii) clip_volume=true: clipping of the volume bounded by the surface mesh.
Figure 76.6 Clipping a cube with a halfspace: compactivity of the clipper (clip_volume=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.
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 also handled.
Figure 76.7 shows the polylines returned by the slicing operation for a triangle mesh and a set of parallel planes.
Figure 76.7 Slicing a mesh. A triangle mesh (left) and the polylines computed by the mesh slicer by intersecting a set of parallel planes (right).
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.
Example: Polygon_mesh_processing/mesh_slicer_example.cpp
Corefinement was introduced in CGAL 4.10 by Sébastien Loriot.
The apply_iterative_snap_rounding option for autorefinement was developed by Sylvain Lazard and Léo Vaque [1], and implemented by Léo Valque in 2025.
1.9.6