Boolean operations are among the most used paradigms to create and edit digital shapes. Despite being conceptually simple, the computation of mesh Booleans is notoriously challenging. Main issues come from numerical approximations that make the detection and processing of intersection points inconsistent and unreliable, exposing implementations based on floating point arithmetic to many kinds of degeneracy and failure. Numerical methods based on rational numbers or exact geometric predicates have the needed robustness guarantees, that are achieved at the cost of increased computation times that, as of today, has always restricted the use of robust mesh Booleans to offline applications. We introduce the first algorithm for Boolean operations with robustness guarantees that is capable of operating at interactive frame rates on meshes with up to 200K triangles. We evaluate our tool thoroughly, considering not only interactive applications but also batch processing of large collections of meshes, processing of huge meshes containing millions of elements and variadic Booleans of hundreds of shapes altogether. In all these experiments, we consistently outperform prior art by at least one order of magnitude.
翻译:Boolean 操作是创建和编辑数字形状的最常用范例之一。 尽管在概念上是简单的, 计算网状布林斯的计算却极具挑战性。 主要问题来自使交叉点的探测和处理不连贯和不可靠的数字近似值, 使基于浮点算术的执行暴露为多种变性和失败。 基于合理数字或精确几何前提的数值方法具有必要的稳健性保证, 而这些保证是以增加计算时间为代价实现的, 而迄今为止,这些计算时间一直限制使用强健的网状布林斯进行离线应用。 我们引入了第一个具有强健保证的布尔恩操作的算法, 保证能够在高达200K三角线的模件上以互动框架速度运行。 我们彻底评估了我们的工具, 不仅考虑交互式应用, 而且还考虑大量米舍的批量处理, 处理含有数以百万计元素和成百种形状的Varidi Booleans的巨型的胶片。 在所有这些实验中, 我们始终以至少一个数量级的顺序超越了先前的艺术。