Sébastien Loriot*
*GeometryFactory
Clipping and Splitting Meshes with Planes
Several releases ago, CGAL introduced the function CGAL::Polygon_mesh_processing::clip(), which enabled users to restrict the volume bounded by a triangle mesh to a halfspace defined by an oriented plane. Over the releases, this function has been extended to also enable clipping of surfaces represented by triangle meshes with boundaries, as well as self-intersecting surfaces. A closely related function, CGAL::Polygon_mesh_processing::split(), can be used to cut and separate a surface in multiple components.
Fig 1: Four successive clips of the "elephant" surface, using planes in arbitrary directions.
10x Runtime Improvements
The original implementation of the two functions was a by-product of the Boolean operations
function CGAL::Polygon_mesh_processing::corefine_and_compute_intersection().
With CGAL 6.1, the functions clip() and split() have been reimplemented from scratch, without changing the API.
The new implemention now takes advantage of the fact that the clipper is simply a plane,
for which efficient orientation tests can be performed, which results in a tenfold speed-up,
In addition, the functions can now be used with meshes with polygonal faces, which is crucial
to avoid cascading growth of the number of subfaces when a face is clipped several times (see Figure 3).
| Input | 1st clip | 2nd clip | 3rd clip | 4th clip | |
| Runtime in seconds (CGAL 6.0) | - | 2.716 | 0.879 | 0.607 | 0.368 |
| Runtime in seconds (CGAL 6.1) | - | 0.197 | 0.121 | 0.045 | 0.036 |
| Number of faces (CGAL 6.0) | 1,422,848 | 749,714 | 173,542 | 116,520 | 58,800 |
| Number of faces (CGAL 6.1) | 1,422,848 | 743,276 | 170,652 | 113,425 | 55,245 |
The runtimes and numbers of faces for CGAL 6.1 are given when the resulting clipped mesh is not triangulated. Below you can see the final output of CGAL 6.1 (not trianguled) vs. that of CGAL 6.0 (necessarily triangulated):
Fig 2: Output of CGAL 6.1 vs output of CGAL 6.0.
Behind the Scenes: a New Function for Mesh Refinement
The new implementation uses internally a new function introduced in CGAL 6.1 to the Polygon Mesh Processing package: CGAL::Polygon_mesh_processing::refine_with_plane(). This function inserts in an input surface mesh the intersection edges between the surface and a plane, and provides access to the created intersection edges.
Fig 3: Intersection edges (in red) of a triangle mesh with planes forming a regular grid for CGAL 6.0 (left) and CGAL 6.1 (right).
Status
All these enhancements are already integrated in CGAL's master branch on the CGAL GitHub repository and will be officially released in the upcoming version of CGAL, CGAL 6.1, scheduled for mid 2025.
Documentation of the function CGAL::Polygon_mesh_processing::clip()
CGAL master branch on GitHub
