Efficiently cutting a 3D domain into a volumetric decomposition through a series of planar cuts

What is it about?

Given a three-dimensional domain delimited by a closed triangulated surface, a common geometry processing task consists in cutting up the domain into cells through a set of planar cuts, creating a “cut-cell mesh”, i.e., a volumetric decomposition of the domain amenable to visualization (e.g., exploded views), animation (e.g., virtual surgery), or simulation (finite volume computations). While a large number of methods have proposed either efficient or robust solutions, none can guarantee both properties, severely limiting their usefulness in practice. At the core of the difficulty is the determination of topological relationships among large numbers of vertices, edges, faces and cells in order to assemble a proper cut-cell mesh: while exact geometric computations provide a robust solution to this issue, their high computational cost has prompted a number of faster solutions based on, e.g., local floating-point angle sorting to significantly accelerate the process — but losing robustness in doing so.

Featured Image

Photo by Markus Winkler on Unsplash

Photo by Markus Winkler on Unsplash

Why is it important?

This paper introduces a new approach to planar cutting of 3D domains that substitutes topological inference for numerical ordering through a novel mesh data structure, and revert to exact numerical evaluations only in the few rare cases where it is strictly necessary. This novel concept of topological cuts exploits the inherent structure of cut-cell mesh generation to save computational time while still guaranteeing exactness for, and robustness to, arbitrary cuts and arbitrary surface geometry.