header

Profile


photo

Julius Nehring-Wirxel, M.Sc.
Room 108
Phone: +49 241 8021806
Fax: +49 241 8022899
Email: nehring-wirxel@cs.rwth-aachen.de



Publications


EMBER: Exact Mesh Booleans via Efficient & Robust Local Arrangements


Philip Trettner, Julius Nehring-Wirxel, Leif Kobbelt
SIGGRAPH 2022
pubimg

Boolean operators are an essential tool in a wide range of geometry processing and CAD/CAM tasks. We present a novel method, EMBER, to compute Boolean operations on polygon meshes which is exact, reliable, and highly performant at the same time. Exactness is guaranteed by using a plane-based representation for the input meshes along with recently introduced homogeneous integer coordinates. Reliability and robustness emerge from a formulation of the algorithm via generalized winding numbers and mesh arrangements. High performance is achieved by avoiding the (pre-)construction of a global acceleration structure. Instead, our algorithm performs an adaptive recursive subdivision of the scene’s bounding box while generating and tracking all required data on the fly. By leveraging a number of early-out termination criteria, we can avoid the generation and inspection of regions that do not contribute to the output. With a careful implementation and a work-stealing multi-threading architecture, we are able to compute Boolean operations between meshes with millions of triangles at interactive rates. We run an extensive evaluation on the Thingi10K dataset to demonstrate that our method outperforms state-of-the-art algorithms, even inexact ones like QuickCSG, by orders of magnitude.



Contact: trettner@shapedcode.com
» Show Videos



Fast Exact Booleans for Iterated CSG using Octree-Embedded BSPs


Julius Nehring-Wirxel, Philip Trettner, Leif Kobbelt
Computer-Aided Design
pubimg

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.

» Show BibTeX

@article{NEHRINGWIRXEL2021103015,
title = {Fast Exact Booleans for Iterated CSG using Octree-Embedded BSPs},
journal = {Computer-Aided Design},
volume = {135},
pages = {103015},
year = {2021},
issn = {0010-4485},
doi = {https://doi.org/10.1016/j.cad.2021.103015},
url = {https://www.sciencedirect.com/science/article/pii/S0010448521000269},
author = {Julius Nehring-Wirxel and Philip Trettner and Leif Kobbelt},
keywords = {Plane-based geometry, CSG, Mesh Booleans, BSP, Octree, Integer arithmetic},
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.}
}





Disclaimer Home Visual Computing institute RWTH Aachen University