Interactive and Robust Mesh Booleans

Boolean operations are among the most used paradigms to create and editdigital shapes. Despite being conceptually simple, the computation of meshBooleans is notoriously challenging. Main issues come from numerical approximationsthat make the detection and processing of intersection pointsinconsistent and unreliable, exposing implementations based on floatingpoint arithmetic to many kinds of degeneracy and failure. Numerical methodsbased on rational numbers or exact geometric predicates have the neededrobustness guarantees, that are achieved at the cost of increased computationtimes that, as of today, has always restricted the use of robust meshBooleans to offline applications.We introduce the first algorithm for Booleanoperations with robustness guarantees that is capable of operating at interactiveframe rates on meshes with up to 200K triangles. We evaluateour tool thoroughly, considering not only interactive applications but alsobatch processing of large collections of meshes, processing of huge meshescontaining millions of elements and variadic Booleans of hundreds of shapesaltogether. In all these experiments, we consistently outperform prior art byat least one order of magnitude.