CGAL 6.2 - Boolean Operations on Meshes

Loading...
Searching...
No Matches
User Manual

Authors
  Sébastien Loriot, Léo Valque, and Ilker O. Yaz

# Introduction

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.

## Outline

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.

# Core Concepts and Definitions

## Definitions

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 77.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 77.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.

# Mesh Boolean Operations

## Computing Corefinement and Autorefinement

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: PMP_Boolean_operations/corefinement_SM.cpp

Show / Hide
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/Polygon_mesh_processing/corefinement.h>
#include <CGAL/Polygon_mesh_processing/IO/polygon_mesh_io.h>
#include <iostream>
#include <string>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Surface_mesh<K::Point_3> Mesh;
namespace PMP = CGAL::Polygon_mesh_processing;
int main(int argc, char* argv[])
{
const std::string filename1 = (argc > 1) ? argv[1] : CGAL::data_file_path("meshes/blobby.off");
const std::string filename2 = (argc > 2) ? argv[2] : CGAL::data_file_path("meshes/eight.off");
Mesh mesh1, mesh2;
if(!PMP::IO::read_polygon_mesh(filename1, mesh1) || !PMP::IO::read_polygon_mesh(filename2, mesh2))
{
std::cerr << "Invalid input." << std::endl;
return 1;
}
std::cout << "Number of vertices before corefinement "
<< num_vertices(mesh1) << " and "
<< num_vertices(mesh2) << "\n";
PMP::corefine(mesh1,mesh2);
std::cout << "Number of vertices after corefinement "
<< num_vertices(mesh1) << " and "
<< num_vertices(mesh2) << "\n";
CGAL::IO::write_polygon_mesh("mesh1_refined.off", mesh1, CGAL::parameters::stream_precision(17));
CGAL::IO::write_polygon_mesh("mesh2_refined.off", mesh2, CGAL::parameters::stream_precision(17));
return 0;
}
CGAL::Exact_predicates_inexact_constructions_kernel
CGAL::Surface_mesh
CGAL::Polygon_mesh_processing::corefine
void corefine(TriangleMesh &tm1, TriangleMesh &tm2, const NamedParameters1 &np1=parameters::default_values(), const NamedParameters2 &np2=parameters::default_values())
corefines tm1 and tm2.
Definition: corefinement.h:757
CGAL::IO::write_polygon_mesh
bool write_polygon_mesh(const std::string &fname, Graph &g, const NamedParameters &np=parameters::default_values())

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: PMP_Boolean_operations/soup_autorefinement.cpp

Show / Hide
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polygon_mesh_processing/autorefinement.h>
#include <CGAL/Polygon_mesh_processing/repair_polygon_soup.h>
#include <CGAL/Polygon_mesh_processing/polygon_soup_to_polygon_mesh.h>
#include <CGAL/Polygon_mesh_processing/triangulate_faces.h>
#include <CGAL/IO/polygon_soup_io.h>
#include <CGAL/Real_timer.h>
#include <boost/container/small_vector.hpp>
#include <iostream>
typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef Kernel::Point_3 Point;
namespace PMP = CGAL::Polygon_mesh_processing;
int main(int argc, char** argv)
{
const std::string filename = argc == 1 ? CGAL::data_file_path("meshes/elephant.off")
: std::string(argv[1]);
std::vector<Point> input_points;
std::vector<boost::container::small_vector<std::size_t, 3>> input_triangles;
if (!CGAL::IO::read_polygon_soup(filename, input_points, input_triangles))
{
std::cerr << "Cannot read " << filename << "\n";
return 1;
}
PMP::repair_polygon_soup(input_points, input_triangles);
PMP::triangulate_polygons(input_points, input_triangles);
CGAL::Real_timer t;
t.start();
PMP::autorefine_triangle_soup(input_points, input_triangles,
CGAL::parameters::concurrency_tag(CGAL::Parallel_if_available_tag()));
t.stop();
std::cout << "#points = " << input_points.size() << " and #triangles = " << input_triangles.size() << " in " << t.time() << " sec." << std::endl;
CGAL::IO::write_polygon_soup("autorefined.off", input_points, input_triangles, CGAL::parameters::stream_precision(17));
return 0;
}
Kernel::Point_3
CGAL::IO::write_polygon_soup
bool write_polygon_soup(const std::string &fname, const PointRange &points, const PolygonRange &polygons, const NamedParameters &np=parameters::default_values())
CGAL::IO::read_polygon_soup
bool read_polygon_soup(const std::string &fname, PointRange &points, PolygonRange &polygons, const NamedParameters &np=parameters::default_values())
CGAL::Polygon_mesh_processing::repair_polygon_soup
void repair_polygon_soup(PointRange &points, PolygonRange &polygons, const NamedParameters &np=parameters::default_values())
CGAL::Polygon_mesh_processing::autorefine_triangle_soup
bool autorefine_triangle_soup(PointRange &soup_points, TriangleRange &soup_triangles, const NamedParameters &np=parameters::default_values())
refines a soup of triangles so that no pair of triangles intersects.
Definition: autorefinement.h:1725
CGAL::Polygon_mesh_processing::triangulate_polygons
bool triangulate_polygons(const PointRange &points, PolygonRange &polygons, const NamedParameters &np=parameters::default_values())
Kernel
std
STL namespace.
CGAL::Parallel_if_available_tag

## Computing Mesh Boolean Operations

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: PMP_Boolean_operations/corefinement_mesh_union.cpp

Show / Hide
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/Polygon_mesh_processing/corefinement.h>
#include <CGAL/Polygon_mesh_processing/IO/polygon_mesh_io.h>
#include <iostream>
#include <string>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Surface_mesh<K::Point_3> Mesh;
namespace PMP = CGAL::Polygon_mesh_processing;
int main(int argc, char* argv[])
{
const std::string filename1 = (argc > 1) ? argv[1] : CGAL::data_file_path("meshes/blobby.off");
const std::string filename2 = (argc > 2) ? argv[2] : CGAL::data_file_path("meshes/eight.off");
Mesh mesh1, mesh2;
if(!PMP::IO::read_polygon_mesh(filename1, mesh1) || !PMP::IO::read_polygon_mesh(filename2, mesh2))
{
std::cerr << "Invalid input." << std::endl;
return 1;
}
Mesh out;
bool valid_union = PMP::corefine_and_compute_union(mesh1,mesh2, out);
if(valid_union)
{
std::cout << "Union was successfully computed\n";
CGAL::IO::write_polygon_mesh("union.off", out, CGAL::parameters::stream_precision(17));
return 0;
}
std::cout << "Union could not be computed\n";
return 1;
}
CGAL::Polygon_mesh_processing::corefine_and_compute_union
bool corefine_and_compute_union(TriangleMesh &tm1, TriangleMesh &tm2, TriangleMesh &tm_out, const NamedParameters1 &np1=parameters::default_values(), const NamedParameters2 &np2=parameters::default_values(), const NamedParametersOut &np_out=parameters::default_values())
corefines tm1 and tm2 and puts in tm_out a triangulated surface mesh bounding the union of the volu...
Definition: corefinement.h:605

Figure 77.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`.

## Input and Output Requirements

### Corefinement Based Operations

There is no restriction 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 be manifold triangulated surfaces bounding volumes. In particular, this means that they should 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. Alternatively, a special visitor (`CGAL::Polygon_mesh_processing::Corefinement::Non_manifold_output_visitor`) is provided for such cases and enables the user to get a triangle soup representing such a non-manifold output. See the example PMP_Boolean_operations/corefinement_mesh_non_manifold_intersection.cpp

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.

If the input meshes contain triangles that are coplanar, it is guaranteed that the triangulations of those triangles in the two corefined meshes will be identical. Also all edges of those refined triangles will be reported as intersection edges (both in the function `CGAL::Polygon_mesh_processing::surface_intersection()` and in the named parameter `edge_is_constrained_map()` of corefine prefixed functions).

### Autorefinement

There is no restriction on the input for the function `CGAL::Polygon_mesh_processing::autorefine_triangle_soup()`. Degenerate triangles will be eliminated, duplicated points will be merged. If several triangles are coplanar, the output will contain as many copies of the triangulation of those refined triangles.

## Kernel Choice and Output Validity

### Corefinement Based Operations

The minimal requirements of the corefinement based operations to terminate without crashing is to use a CGAL Kernel with exact predicates (such as `CGAL::Exact_predicates_inexact_constructions_kernel`). The graph structure is then always guaranteed to have the right topology as exact constructions are used internally. However, because of the rounding of the coordinates of the new intersection points, the embedding of the output surface meshes in the chosen kernel may feature self-intersections. This embedding issue goes away if a kernel with additionally exact constructions (such as `CGAL::Exact_predicates_exact_constructions_kernel`) is used. In particular, for consecutive operations, it is recommended to use a kernel with exact predicates and exact constructions.

From a user point of view, the choice of the kernel is done using the named parameter `geom_traits()`. If not provided, the kernel is deduced from the point type of the named parameter `vertex_point_map()`, which is by default the internal vertex point map of the mutable face graph used as input. If we take the example of `CGAL::Surface_mesh<CGAL::Point_3<K>>`, the kernel used will be `K`.

### Autorefinement

As for corefinement based operations described in the previous section, the function `CGAL::Polygon_mesh_processing::autorefine_triangle_soup()` requires a kernel with exact predicates in order to guarantee to terminate without issue. The output will then have the same topology as the exact output (for a triangle soup this means the indexed points and triangles will be the same as if exact computations were used). If non-exact constructions are used, points will be naively rounded and self-intersection might be created. In order to avoid that, we provide a robust heuristic that can be enabled using the named parameter `apply_iterative_snap_rounding()`. 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

## Advanced Examples

### Boolean Operation and Local Remeshing

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: PMP_Boolean_operations/corefinement_difference_remeshed.cpp

Show / Hide
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/Polygon_mesh_processing/corefinement.h>
#include <CGAL/Polygon_mesh_processing/IO/polygon_mesh_io.h>
#include <CGAL/Polygon_mesh_processing/remesh.h>
#include <CGAL/boost/graph/selection.h>
#include <fstream>
#include <iostream>
#include <iterator>
#include <vector>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Surface_mesh<K::Point_3> Mesh;
typedef boost::graph_traits<Mesh>::halfedge_descriptor halfedge_descriptor;
typedef boost::graph_traits<Mesh>::edge_descriptor edge_descriptor;
typedef boost::graph_traits<Mesh>::face_descriptor face_descriptor;
namespace PMP = CGAL::Polygon_mesh_processing;
namespace params = CGAL::parameters;
struct Vector_pmap_wrapper
{
std::vector<bool>& vect;
Vector_pmap_wrapper(std::vector<bool>& v) : vect(v) {}
friend bool get(const Vector_pmap_wrapper& m, face_descriptor f)
{
return m.vect[f];
}
friend void put(const Vector_pmap_wrapper& m, face_descriptor f, bool b)
{
m.vect[f]=b;
}
};
int main(int argc, char* argv[])
{
const std::string filename1 = (argc > 1) ? argv[1] : CGAL::data_file_path("meshes/blobby.off");
const std::string filename2 = (argc > 2) ? argv[2] : CGAL::data_file_path("meshes/eight.off");
Mesh mesh1, mesh2;
if (!PMP::IO::read_polygon_mesh(filename1, mesh1) || !PMP::IO::read_polygon_mesh(filename2, mesh2))
{
std::cerr << "Invalid input." << std::endl;
return 1;
}
// create a property on edges to indicate whether they are constrained
Mesh::Property_map<edge_descriptor,bool> is_constrained_map =
mesh1.add_property_map<edge_descriptor,bool>("e:is_constrained", false).first;
// update mesh1 to contain the mesh bounding the difference
// of the two input volumes.
bool valid_difference =
PMP::corefine_and_compute_difference(mesh1,
mesh2,
mesh1,
params::default_values(), // default parameters for mesh1
params::default_values(), // default parameters for mesh2
params::edge_is_constrained_map(is_constrained_map));
if (valid_difference)
{
std::cout << "Difference was successfully computed\n";
CGAL::IO::write_polygon_mesh("difference.off", mesh1, CGAL::parameters::stream_precision(17));
}
else
{
std::cout << "Difference could not be computed\n";
return 1;
}
// collect faces incident to a constrained edge
std::vector<face_descriptor> selected_faces;
std::vector<bool> is_selected(num_faces(mesh1), false);
for (edge_descriptor e : edges(mesh1))
if (is_constrained_map[e])
{
// insert all faces incident to the target vertex
for (halfedge_descriptor h : halfedges_around_target(halfedge(e,mesh1),mesh1))
{
if (!is_border(h, mesh1) )
{
face_descriptor f = face(h, mesh1);
if (!is_selected[f])
{
selected_faces.push_back(f);
is_selected[f] = true;
}
}
}
}
// increase the face selection
CGAL::expand_face_selection(selected_faces, mesh1, 2,
Vector_pmap_wrapper(is_selected),
std::back_inserter(selected_faces));
std::cout << selected_faces.size() << " faces were selected for the remeshing step\n";
// remesh the region around the intersection polylines
PMP::isotropic_remeshing(selected_faces, 0.02, mesh1,
params::edge_is_constrained_map(is_constrained_map));
CGAL::IO::write_polygon_mesh("difference_remeshed.off", mesh1, CGAL::parameters::stream_precision(17));
return 0;
}
CGAL::Polygon_mesh_processing::corefine_and_compute_difference
bool corefine_and_compute_difference(TriangleMesh &tm1, TriangleMesh &tm2, TriangleMesh &tm_out, const NamedParameters1 &np1=parameters::default_values(), const NamedParameters2 &np2=parameters::default_values(), const NamedParametersOut &np_out=parameters::default_values())
corefines tm1 and tm2 and puts in tm_out a triangulated surface mesh bounding the volume bounded by...
Definition: corefinement.h:669
CGAL::Polygon_mesh_processing::isotropic_remeshing
void isotropic_remeshing(const FaceRange &faces, SizingFunction &sizing, PolygonMesh &pmesh, const NamedParameters &np=parameters::default_values())
CGAL::is_border
bool is_border(typename boost::graph_traits< FaceGraph >::halfedge_descriptor hd, const FaceGraph &g)
CGAL::halfedges_around_target
Iterator_range< Halfedge_around_target_iterator< Graph > > halfedges_around_target(typename boost::graph_traits< Graph >::halfedge_descriptor h, const Graph &g)
CGAL::expand_face_selection
OutputIterator expand_face_selection(const FaceRange &selection, FaceGraph &fg, unsigned int k, IsFaceSelectedPMap is_selected, OutputIterator out)
CGAL::parameters

### Robustness of Consecutive Operations

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: PMP_Boolean_operations/corefinement_consecutive_bool_op.cpp

Show / Hide
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/Polygon_mesh_processing/corefinement.h>
#include <CGAL/Polygon_mesh_processing/IO/polygon_mesh_io.h>
#include <iostream>
#include <string>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Exact_predicates_exact_constructions_kernel EK;
typedef CGAL::Surface_mesh<K::Point_3> Mesh;
typedef boost::graph_traits<Mesh>::vertex_descriptor vertex_descriptor;
typedef Mesh::Property_map<vertex_descriptor,EK::Point_3> Exact_point_map;
namespace PMP = CGAL::Polygon_mesh_processing;
namespace params = CGAL::parameters;
// One could perform Boolean operations directly on inexact meshes as an exact computation
// is done internally. However, if we want to perform consecutive Boolean operations,
// we can avoid multiple conversions and possible precision issues by maintaining
// explicitly the exact points in the meshes.
struct Exact_vertex_point_map
{
// typedef for the property map
typedef boost::property_traits<Exact_point_map>::value_type value_type;
typedef boost::property_traits<Exact_point_map>::reference reference;
typedef boost::property_traits<Exact_point_map>::key_type key_type;
typedef boost::read_write_property_map_tag category;
// exterior references
Exact_point_map exact_point_map;
Mesh* tm_ptr;
// Converters
CGAL::Cartesian_converter<K, EK> to_exact;
CGAL::Cartesian_converter<EK, K> to_input;
Exact_vertex_point_map()
: tm_ptr(nullptr)
{}
Exact_vertex_point_map(const Exact_point_map& ep, Mesh& tm)
: exact_point_map(ep)
, tm_ptr(&tm)
{
for (Mesh::Vertex_index v : vertices(tm))
exact_point_map[v]=to_exact(tm.point(v));
}
friend
reference get(const Exact_vertex_point_map& map, key_type k)
{
CGAL_precondition(map.tm_ptr!=nullptr);
return map.exact_point_map[k];
}
friend
void put(const Exact_vertex_point_map& map, key_type k, const EK::Point_3& p)
{
CGAL_precondition(map.tm_ptr!=nullptr);
map.exact_point_map[k]=p;
// create the input point from the exact one
map.tm_ptr->point(k)=map.to_input(p);
}
};
int main(int argc, char* argv[])
{
const std::string filename1 = (argc > 1) ? argv[1] : CGAL::data_file_path("meshes/blobby.off");
const std::string filename2 = (argc > 2) ? argv[2] : CGAL::data_file_path("meshes/eight.off");
Mesh mesh1, mesh2;
if(!PMP::IO::read_polygon_mesh(filename1, mesh1) || !PMP::IO::read_polygon_mesh(filename2, mesh2))
{
std::cerr << "Invalid input." << std::endl;
return 1;
}
Exact_point_map mesh1_exact_points =
mesh1.add_property_map<vertex_descriptor,EK::Point_3>("v:exact_point").first;
Exact_point_map mesh2_exact_points =
mesh2.add_property_map<vertex_descriptor,EK::Point_3>("v:exact_point").first;
Exact_vertex_point_map mesh1_vpm(mesh1_exact_points, mesh1);
Exact_vertex_point_map mesh2_vpm(mesh2_exact_points, mesh2);
if ( PMP::corefine_and_compute_intersection(mesh1,
mesh2,
mesh1,
params::vertex_point_map(mesh1_vpm),
params::vertex_point_map(mesh2_vpm),
params::vertex_point_map(mesh1_vpm) ) )
{
if ( PMP::corefine_and_compute_union(mesh1,
mesh2,
mesh2,
params::vertex_point_map(mesh1_vpm),
params::vertex_point_map(mesh2_vpm),
params::vertex_point_map(mesh2_vpm) ) )
{
std::cout << "Intersection and union were successfully computed\n";
CGAL::IO::write_polygon_mesh("inter_union.off", mesh2, CGAL::parameters::stream_precision(17));
return 0;
}
std::cout << "Union could not be computed\n";
return 1;
}
std::cout << "Intersection could not be computed\n";
return 1;
}
CGAL::Cartesian_converter
CGAL::Exact_predicates_exact_constructions_kernel
CGAL::Polygon_mesh_processing::corefine_and_compute_intersection
bool corefine_and_compute_intersection(TriangleMesh &tm1, TriangleMesh &tm2, TriangleMesh &tm_out, const NamedParameters1 &np1=parameters::default_values(), const NamedParameters2 &np2=parameters::default_values(), const NamedParametersOut &np_out=parameters::default_values())
corefines tm1 and tm2 and puts in tm_out a triangulated surface mesh bounding the intersection of t...
Definition: corefinement.h:637

# Clipping and Splitting Meshes

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:

- `CGAL::Polygon_mesh_processing::clip()`,
- `CGAL::Polygon_mesh_processing::split()`.

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 77.5 and Figure 77.6.

Figure 77.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 77.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.

# Slicer

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 77.7 shows the polylines returned by the slicing operation for a triangle mesh and a set of parallel planes.

Figure 77.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: PMP_Boolean_operations/mesh_slicer_example.cpp

Show / Hide
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/Polygon_mesh_slicer.h>
#include <CGAL/Polygon_mesh_processing/IO/polygon_mesh_io.h>
#include <CGAL/AABB_halfedge_graph_segment_primitive.h>
#include <CGAL/AABB_tree.h>
#include <CGAL/AABB_traits_3.h>
#include <iostream>
#include <list>
#include <string>
#include <vector>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Surface_mesh<K::Point_3> Mesh;
typedef std::vector<K::Point_3> Polyline_type;
typedef std::list<Polyline_type> Polylines;
typedef CGAL::AABB_halfedge_graph_segment_primitive<Mesh> HGSP;
typedef CGAL::AABB_traits_3<K, HGSP> AABB_traits;
typedef CGAL::AABB_tree<AABB_traits> AABB_tree;
namespace PMP = CGAL::Polygon_mesh_processing;
int main(int argc, char* argv[])
{
const std::string filename = (argc > 1) ? argv[1] : CGAL::data_file_path("meshes/eight.off");
Mesh mesh;
if(!PMP::IO::read_polygon_mesh(filename, mesh) || CGAL::is_empty(mesh) || !CGAL::is_triangle_mesh(mesh))
{
std::cerr << "Invalid input." << std::endl;
return 1;
}
// Slicer constructor from the mesh
CGAL::Polygon_mesh_slicer<Mesh, K> slicer(mesh);
Polylines polylines;
slicer(K::Plane_3(0, 0, 1, -0.4), std::back_inserter(polylines));
std::cout << "At z = 0.4, the slicer intersects "
<< polylines.size() << " polylines" << std::endl;
polylines.clear();
slicer(K::Plane_3(0, 0, 1, 0.2), std::back_inserter(polylines));
std::cout << "At z = -0.2, the slicer intersects "
<< polylines.size() << " polylines" << std::endl;
polylines.clear();
// Use the Slicer constructor from a pre-built AABB_tree
AABB_tree tree(edges(mesh).first, edges(mesh).second, mesh);
CGAL::Polygon_mesh_slicer<Mesh, K> slicer_aabb(mesh, tree);
slicer_aabb(K::Plane_3(0, 0, 1, -0.4), std::back_inserter(polylines));
std::cout << "At z = 0.4, the slicer intersects "
<< polylines.size() << " polylines" << std::endl;
polylines.clear();
return 0;
}
CGAL::AABB_halfedge_graph_segment_primitive
CGAL::AABB_traits_3
CGAL::AABB_tree
CGAL::Polygon_mesh_slicer
Function object that computes the intersection of a plane with a triangulated surface mesh.
Definition: Polygon_mesh_slicer.h:90
CGAL::AABB_traits
AABB_traits_3< GeomTraits, AABBPrimitive, BboxMap > AABB_traits
CGAL::is_triangle_mesh
bool is_triangle_mesh(const FaceGraph &g)
CGAL::is_empty
bool is_empty(const FaceGraph &g)

# Mesh Kernels

The kernel of a mesh is defined as the set of points from which the entire (oriented) surface of the mesh is visible. More formally, a point belongs to the kernel if, for every point on the mesh, the segment connecting them lies inside the mesh. Equivalently, the kernel is the intersection of all the half-spaces on the negative side of the oriented supporting planes of the faces of the mesh.

Figure 77.8 Mesh kernel: From left to right: (i) The input mesh; (ii) The kernel of the input; (iii) The kernel inside the mesh. All segments between a point of the kernel and a point of the mesh are inside the mesh.

The functions `CGAL::Polygon_mesh_processing::kernel()`, `CGAL::Polygon_mesh_processing::kernel_point()` and `CGAL::Polygon_mesh_processing::has_empty_kernel()` output the full kernel, a single point inside it or a Boolean indicating whether the kernel exists or not, respectively.

# Implementation History

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 [2], and implemented by Léo Valque in 2025.

The kernel functions and the specialization of clipping and plane refinement to convex inputs were implemented in 2025 by Léo Valque, inspired by the work of Sorgente et al. [1].