QuickCSG: Fast Arbitrary Boolean Combinations of N Solids

Matthijs Douze 1, 2 Jean-Sébastien Franco 1 Bruno Raffin 3, 4
1 MORPHEO - Capture and Analysis of Shapes in Motion
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann, INPG - Institut National Polytechnique de Grenoble
4 DATAMOVE - Data Aware Large Scale Computing
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : QuickCSG computes the result for general N-polyhedron boolean expressions without an intermediate tree of solids. We propose a vertex-centric view of the problem, which simplifies the identification of final geometric contributions, and facilitates its spatial decomposition. The problem is then cast in a single KD-tree exploration, geared toward the result by early pruning of any region of space not contributing to the final surface. We assume strong regularity properties on the input meshes and that they are in general position. This simplifying assumption, in combination with our vertex-centric approach, improves the speed of the approach. 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 dozens of polyhedra. The algorithm also outperforms GPU implementations with approximate discretizations, while producing an output without redundant facets. Despite the restrictive assumptions on the input, we show the usefulness of QuickCSG for applications with large CSG problems and strong temporal constraints, e.g. modeling for 3D printers, reconstruction from visual hulls and collision detection.
Liste complète des métadonnées

https://hal.inria.fr/hal-01587902
Contributor : Jean-Sébastien Franco <>
Submitted on : Thursday, September 14, 2017 - 5:40:57 PM
Last modification on : Monday, February 25, 2019 - 4:34:20 PM
Document(s) archivé(s) le : Friday, December 15, 2017 - 8:45:36 PM

File

1706.01558.quickcsg.archiv.pdf
Files produced by the author(s)

Licence


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

Identifiers

  • HAL Id : hal-01587902, version 1

Citation

Matthijs Douze, Jean-Sébastien Franco, Bruno Raffin. QuickCSG: Fast Arbitrary Boolean Combinations of N Solids. [Research Report] ArXiv. 2017. ⟨hal-01587902⟩

Share

Metrics

Record views

626

Files downloads

428