# Fast Exact Booleans for Iterated CSG using Octree-Embedded BSPs

arXiv: https://arxiv.org/abs/2103.02486 · HTML: https://mlsanity.com/paper/2103.02486/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Mar 2021.

## Built on by (most cited first, 1 of 1)

- [GPU-Accelerated 3D Polygon Visibility Volumes for Synergistic Perception and Navigation](https://mlsanity.com/paper/2402.03135/) (2024)

## Abstract (arXiv)

We present octree-embedded BSPs, a volumetric mesh data structure suited for performing a sequence of Boolean operations (iterated CSG) efficiently. At its core, our data structure leverages a plane-based geometry representation and integer arithmetics to guarantee unconditionally robust operations. These typically present considerable performance challenges which we overcome by using custom-tailored fixed-precision operations and an efficient algorithm for cutting a convex mesh against a plane. Consequently, BSP Booleans and mesh extraction are formulated in terms of mesh cutting. The octree is used as a global acceleration structure to keep modifications local and bound the BSP complexity. With our optimizations, we can perform up to 2.5 million mesh-plane cuts per second on a single core, which creates roughly 40-50 million output BSP nodes for CSG. We demonstrate our system in two iterated CSG settings: sweep volumes and a milling simulation.