Mesh Arrangements for Solid Geometry ACM SIGGRAPH 2016

Qingnan Zhou¹  Eitan Grinspun²  Denis Zorin¹  Alec Jacobson²

¹New York University  ²Columbia University

Our method takes as input any number of meshes (three shown in this 2D illustration). We resolve intersections and assign a winding number vector to every delineated cell. Different boolean operations are achieved as extractions according to these winding number vectors.

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.

Downloads

Definitions

triangle meshA list of n 3D vertex positions and a list of m triplets (triangle corners) of indices between [1,n] in the vertex list.
PWNA (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.
solidA 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.
polyhedronA sinlge component solid mesh without non-manifold elements. This is equivalent to the usual definition of (orientable) polyhedron.

BibTeX

@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},
}

Acknowledgements

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.