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.