Now implemented in Blender and available to Blender's 1-3 million users.
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.
| triangle mesh | A list of n 3D vertex positions and a list of m triplets (triangle corners) of indices between [1,n] in the vertex list. |
| PWN | A (triangle) mesh inducing a piecewise constant generalized winding number field. These meshes may contain self-intersections, non-manifold elements, multiple components, degenerate faces, and even open boundaries (seams), so long as the winding number is still piecewise constant. |
| solid | A PWN mesh without self-intersections inducing a generalized winding number field that is everywhere zero (outside) or one (inside). Solid mesh may contain non-manifold elements and multiple components, but will never contain open boundaries or degenerate faces. |
| polyhedron | A sinlge component solid mesh without non-manifold elements. This is equivalent to the usual definition of (orientable) polyhedron. |
@article{Zhou:2016:MASG,
author = {Qingnan Zhou and Eitan Grinspun and Denis Zorin and Alec Jacobson},
title = {Mesh Arrangements for Solid Geometry},
journal = {ACM Transactions on Graphics (TOG)},
volume = {35},
number = {4},
year = {2016},
}We thank G. Bernstein for sharing code and M. Attene for testing on the Thingi10K dataset. We thank M. Campen, A. Fleming H. Maia, J. Panetta, R. Sawhney, O. Stein, P. Thamjaroenporn, O. Winn, and E. Yao for early feedback and proofreading. Funded in part by NSF grants CMMI-11-29917, IIS-14-09286, and IIS-17257.