“TopoCut: fast and robust planar cutting of arbitrary domains” by Fang, Desbrun, Bao and Huang

Given a complex three-dimensional domain delimited by a closed and non-degenerate input triangle mesh without any self-intersection, 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). A large number of methods have proposed either efficient or robust solutions, sometimes restricting the cuts to form a regular or adaptive grid for simplicity; yet, 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. In this paper, we introduce 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. We show that our 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 surface geometry. We demonstrate the superiority of our approach over state-of-the-art methods on almost 10,000 meshes with a wide range of geometric and topological complexity. We also provide an open source implementation.

1. M. J. Aftosmis, M. J. Berger, and J. E. Melton. 1998. Robust and Efficient Cartesian Mesh Generation for Component-Based Geometry. AIAA Journal 36, 6 (1998), 952–960. Google ScholarCross Ref
2. Marco Attene. 2020. Indirect Predicates for Geometric Constructions. Computer-Aided Design 126 (2020), 102856. https://www.sciencedirect.com/science/article/pii/S001044852030049XGoogle ScholarCross Ref
3. Vinicius C. Azevedo, Christopher Batty, and Manuel M. Oliveira. 2016. Preserving Geometry and Topology for Fluid Flows with Thin Obstacles and Narrow Gaps. ACM Trans. Graph. 35, 4, Article 97 (July 2016), 12 pages.Google ScholarDigital Library
4. Chandrajit L. Bajaj and Valerio Pascucci. 1996. Splitting a Complex of Convex Polytopes in Any Dimension. In Proceedings of the Twelfth Annual Symposium on Computational Geometry (SCG ’96). Association for Computing Machinery, New York, NY, USA, 88–97.Google Scholar
5. Gilbert Bernstein and Don Fussell. 2009. Fast, Exact, Linear Booleans. Computer Graphics Forum 28, 5 (2009), 1269–1278.Google ScholarCross Ref
6. Marcel Campen and Leif Kobbelt. 2010. Exact and Robust (Self-)Intersections for Polygonal Meshes. Computer Graphics Forum 29, 2 (2010), 397–406.Google ScholarCross Ref
7. CGAL. 2021. CGAL – Computational Geometry Algorithms Library. https://www.cgal.orgGoogle Scholar
8. Gianmarco Cherchi, Marco Livesu, Riccardo Scateni, and Marco Attene. 2020. Fast and Robust Mesh Arrangements Using Floating-Point Arithmetic. ACM Trans. Graph. 39, 6, Article 250 (Nov. 2020), 16 pages.Google ScholarDigital Library
9. Olivier Devillers, Sylvain Lazard, and William J. Lenhart. 2018. 3D Snap Rounding. In 34th International Symposium on Computational Geometry (SoCG 2018) (Leibniz International Proceedings in Informatics (LIPIcs)), Bettina Speckmann and Csaba D. Tóth (Eds.), Vol. 99. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 30:1–30:14.Google Scholar
10. Lorenzo Diazzi and Marco Attene. 2021. Convex Polyhedral Meshing for Robust Solid Modeling. ACM Trans. Graph. 40, 6, Article 259 (dec 2021), 16 pages.Google ScholarDigital Library
11. Essex Edwards and Robert Bridson. 2014. Detailed Water with Coarse Grids: Combining Surface Meshes and Adaptive Discontinuous Galerkin. ACM Trans. Graph. 33, 4, Article 136 (July 2014), 9 pages.Google ScholarDigital Library
12. F.R. Feito and J.C. Torres. 1997. Inclusion test for general polyhedra. Computers & Graphics 21, 1 (1997), 23 — 30.Google ScholarCross Ref
13. Steven Fortune. 1997. Vertex-Rounding a Three-Dimensional Polyhedral Subdivision. Discrete Comput. Geom 22 (1997), 116–125.Google Scholar
14. GMP. 2021. GMP – The GNU Multiple Precision Arithmetic Library. https://gmplib.orgGoogle Scholar
15. Yixin Hu, Qingnan Zhou, Xifeng Gao, Alec Jacobson, Denis Zorin, and Daniele Panozzo. 2018. Tetrahedral Meshing in the Wild. ACM Trans. Graph. 37, 4, Article 60 (July 2018), 14 pages.Google ScholarDigital Library
16. J. Jaśkowiec, P. Pluciński, and A. Stankiewicz. 2016. Discontinuous Galerkin method with arbitrary polygonal finite elements. Finite Elements in Analysis and Design 120 (2016), 1 — 17.Google ScholarDigital Library
17. Yehuda E Kalay. 1982. Determining the spatial containment of a point in general polyhedra. Computer Graphics and Image Processing 19, 4 (1982), 303 — 334.Google ScholarCross Ref
18. Marco Livesu. 2019. Cinolib: A Generic Programming Header Only C++ Library for Processing Polygonal and Polyhedral Meshes. Springer Berlin Heidelberg, Berlin, Heidelberg, 64–76.Google Scholar
19. Matthias Meinke, Lennart Schneiders, Claudia Günther, and Wolfgang Schröder. 2013. A cut-cell method for sharp moving boundaries in Cartesian grids. Computers & Fluids 85 (2013), 135 — 142. International Workshop on Future of CFD and Aerospace Sciences.Google ScholarCross Ref
20. V. J. Milenkovic and L. R. Nackman. 1990. Finding compact coordinate representations for polygons and polyhedra. IBM Journal of Research and Development 34, 5 (1 Jan. 1990), 753–769.Google ScholarDigital Library
21. Julius Nehring-Wirxel, Philip Trettner, and Leif Kobbelt. 2021. Fast Exact Booleans for Iterated CSG using Octree-Embedded BSPs. Computer-Aided Design 135 (2021), 103015.Google ScholarCross Ref
22. OpenMesh. 2021. OpenMesh – A generic and efficient polygon mesh data structure. https://www.openmesh.orgGoogle Scholar
23. OpenVolumeMesh. 2021. OpenVolumeMesh – A Generic and Versatile Index-Based Data Structure for Polytopal Meshes. https://www.openvolumemesh.orgGoogle Scholar
24. Daniele Panozzo and Alec Jacobson. 2019. libigl: Prototyping Geometry Processing Research in C++. In Eurographics 2019 – Tutorials, Wenzel Jakob and Enrico Puppo (Eds.). The Eurographics Association. Google ScholarCross Ref
25. Taylor Patterson, Nathan Mitchell, and Eftychios Sifakis. 2012. Simulation of Complex Nonlinear Elastic Bodies Using Lattice Deformers. ACM Trans. Graph. 31, 6, Article 197 (2012), 10 pages.Google ScholarDigital Library
26. Jonathan R. Shewchuk. 1997. Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates. Discrete Comput. Geom. 18, 3 (1997), 305–363.Google ScholarCross Ref
27. Eftychios Sifakis, Kevin G. Der, and Ronald Fedkiw. 2007. Arbitrary Cutting of Deformable Tetrahedralized Objects. In Proceedings of the 2007 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA ’07). Eurographics Association, Goslar, DEU, 73–80.Google ScholarDigital Library
28. Michael Tao, Christopher Batty, Eugene Fiume, and David I. W. Levin. 2019. Mandoline: Robust Cut-cell Generation for Arbitrary Triangle Meshes. ACM Trans. Graph. 38, 6, Article 179 (Nov. 2019), 17 pages.Google ScholarDigital Library
29. Charlie C. L. Wang and Dinesh Manocha. 2013. Efficient Boundary Extraction of BSP Solids Based on Clipping Operations. IEEE Transactions on Visualization and Computer Graphics 19, 1 (Jan. 2013), 16–29.Google ScholarDigital Library
30. Chee K. Yap and Vikram Sharma. 2008. Robust Geometric Computation. Springer US, Boston, MA, 788–790.Google Scholar
31. Qingnan Zhou, Eitan Grinspun, Denis Zorin, and Alec Jacobson. 2016. Mesh Arrangements for Solid Geometry. ACM Trans. Graph. 35, 4, Article 39 (July 2016), 15 pages.Google ScholarDigital Library