Skip to Main content Skip to Navigation

QuickCSG: Arbitrary and Faster Boolean Combinations of N Solids

Matthijs Douze 1, 2 Jean-Sébastien Franco 2 Bruno Raffin 3
2 MORPHEO - Capture and Analysis of Shapes in Motion
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann, Grenoble INP - Institut polytechnique de Grenoble - Grenoble Institute of Technology
3 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : While studied over several decades, the computation of boolean operations on polyhedra is almost always addressed by focusing on the case of two polyhedra. For multiple input polyhedra and an arbitrary boolean operation to be applied, the operation is decomposed over a binary CSG tree, each node being processed separately in quasilinear time. For large trees, this is both error prone due to intermediate geometry and error accumulation, and inefficient because each node yields a specific overhead. We introduce a fundamentally new approach to polyhedral CSG evaluation, addressing the general N-polyhedron case. We propose a new vertex-centric view of the problem, which both simplifies the algorithm computing resulting geometric contributions, and vastly facilitates its spatial decomposition. We then embed the entire problem in a single KD-tree, specifically geared toward the final result by early pruning of any region of space not contributing to the final surface. This not only improves the robustness of the approach, it also gives it a fundamental speed advantage, with an output complexity depending on the output mesh size instead of the input size as with usual approaches. Complemented with a task-stealing parallelization, the algorithm achieves breakthrough performance, one to two orders of magnitude speedups with respect to state-of-the-art CPU algorithms, on boolean operations over two to several dozen polyhedra. The algorithm is also shown to outperform recent GPU implementations and approximate discretizations, while producing an exact output without redundant facets.
Complete list of metadata

Cited literature [34 references]  Display  Hide  Download
Contributor : Douze Matthijs Connect in order to contact the contributor
Submitted on : Wednesday, July 27, 2016 - 3:21:27 PM
Last modification on : Thursday, October 21, 2021 - 3:51:58 AM


Files produced by the author(s)


Distributed under a Creative Commons Attribution - NonCommercial - NoDerivatives 4.0 International License


  • HAL Id : hal-01121419, version 1



Matthijs Douze, Jean-Sébastien Franco, Bruno Raffin. QuickCSG: Arbitrary and Faster Boolean Combinations of N Solids. [Research Report] RR-8687, Inria - Research Centre Grenoble – Rhône-Alpes; INRIA. 2015, pp.36. ⟨hal-01121419⟩



Les métriques sont temporairement indisponibles