Fast, Exact, Linear Booleans
Authors:
- 1 July 2009
- journal article
- Published by Wiley in Computer Graphics Forum
- Vol. 28 (5) , 1269-1278
Abstract
We present a new system for robustly performing Boolean operations on linear, 3D polyhedra. Our system is exact, meaning that all internal numeric predicates are exactly decided in the sense of exact geometric computation. Our BSP‐tree based system is 16‐28× faster at performing iterative computations than CGAL's Nef Polyhedra based system, the current best practice in robust Boolean operations, while being only twice as slow as the non‐robust modeler Maya. Meanwhile, we achieve a much smaller substrate of geometric subroutines than previous work, comprised of only 4 predicates, a convex polygon constructor, and a convex polygon splitting routine. The use of a BSP‐tree based Boolean algorithm atop this substrate allows us to explicitly handle all geometric degeneracies without treating a large number of cases.Keywords
This publication has 22 references indexed in Scilit:
- Improved Binary Space Partition mergingComputer-Aided Design, 2008
- Boolean Operations on 3D Selective Nef Complexes: Data Structure, Algorithms, and Implementation2003
- Practical volumetric sculptingThe Visual Computer, 2000
- Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric PredicatesDiscrete & Computational Geometry, 1997
- Polyhedral modelling with multiprecision integer arithmeticComputer-Aided Design, 1997
- Topologically exact evaluation of polyhedra defined in CSG with loose primitivesComputer Graphics Forum, 1996
- Static analysis yields efficient exact integer arithmetic for computational geometryACM Transactions on Graphics, 1996
- Merging BSP trees yields polyhedral set operationsACM SIGGRAPH Computer Graphics, 1990
- Set operations on polyhedra using binary space partitioning treesACM SIGGRAPH Computer Graphics, 1987
- Constructive solid geometry for polyhedral objectsACM SIGGRAPH Computer Graphics, 1986