Fast Exact Booleans for Iterated CSG using Octree-Embedded BSPs. (June 2021)

• Record Type: Journal Article
• Authors: Nehring-Wirxel, Julius; Trettner, Philip; Kobbelt, Leif
• Is Part Of: Computer aided design. Volume 135(2021)
• Publication Date: 2021-06
• Subjects: Plane-based geometry -- CSG -- Mesh Booleans -- BSP -- Octree -- Integer arithmetic; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2021.103015
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: 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. Highlights: Scalable high-performance CSG via octree-embedded BSPs. Cutting-based BSP Booleans for iterated CSG. Robust and efficient BSP to mesh conversion using in-place mesh cutting. Fast and exact plane-based geometry representation via fixed-width integer arithmetic.