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, INPG - Institut National Polytechnique de Grenoble
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 metadatas

Cited literature [34 references]  Display  Hide  Download


https://hal.inria.fr/hal-01121419
Contributor : Douze Matthijs <>
Submitted on : Wednesday, July 27, 2016 - 3:21:27 PM
Last modification on : Thursday, October 11, 2018 - 8:48:03 AM

Files

RR-8687.pdf
Files produced by the author(s)

Licence


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

Identifiers

  • HAL Id : hal-01121419, version 1

Citation

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⟩

Share

Metrics

Record views

1925

Files downloads

2446