Mesh arrangements for solid geometry
Authors:
Open Access
- 11 July 2016
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 35 (4) , 1-15
Abstract
Many high-level geometry processing tasks rely on low-level constructive solid geometry operations. Though trivial for implicit representations, boolean operations are notoriously difficult to execute robustly for explicit boundary representations. Existing methods for 3D triangle meshes fall short in one way or another. Some methods are fast but fail to produce closed, self-intersection free output. Other methods are robust but place prohibitively strict assumptions on the input, e.g., no hollow cavities, non-manifold edges or self-intersections. We propose a systematic recipe for conducting a family of exact constructive solid geometry operations. The two-stage method makes no general position assumptions and does not resort to numerical perturbation. The method is variadic , operating on any number of input meshes. This generalizes unary mesh-repair operations, classic binary boolean differencing, and n -ary operations such as finding all regions inside at least k out of n inputs. We demonstrate the superior effectiveness and robustness of our method on a dataset of 10,000 "real-world" meshes from a popular online repository. To encourage development, validation, and comparison, we release both our code and dataset to the public.Keywords
Funding Information
- National Science Foundation (CMMI-11-29917)
This publication has 27 references indexed in Scilit:
- Consistent Volumetric Discretizations Inside Self‐Intersecting SurfacesComputer Graphics Forum, 2013
- Polygon mesh repairingACM Computing Surveys, 2013
- Fast and robust Booleans on polyhedraComputer-Aided Design, 2013
- A lightweight approach to repairing digitized polygon meshesThe Visual Computer, 2010
- Hybrid BooleansComputer Graphics Forum, 2010
- Fast, Exact, Linear BooleansComputer Graphics Forum, 2009
- Level set surface editing operatorsACM Transactions on Graphics, 2002
- Topologically exact evaluation of polyhedra defined in CSG with loose primitivesComputer Graphics Forum, 1996
- Construction of the Voronoi diagram for 'one million' generators in single-precision arithmeticProceedings of the IEEE, 1992
- Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithmsACM Transactions on Graphics, 1990