Fast, Exact, Linear Booleans
work with Don Fussell
Sculpted Bunny
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-28x 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.
UPDATE! Mar. 1, 2013 My new Boolean library, Cork is available on Github. (note that Cork is not an implementation of the BSP technique presented in this paper.)
Paper (pdf 2.8MB)
Movie (mov 2.6MB)
(If you would like a copy of my old code for this project, please e-mail me. If you attempt to write your own implementation, please feel free to contact me with any questions you have.)