Fast Exact Linear Booleans

我们提出了一个新的系统,用于在线性3D多面体上可靠地执行布尔运算。我们的系统是精确的,这意味着所有内部数字谓词都是从精确的几何计算中确定的。我们的基于BSP树的系统执行迭代计算的速度比基于CGAL的Nef Polyhedra的系统快16-28倍,后者是鲁棒布尔运算的当前最佳实践,但速度却是非鲁棒建模器Maya的两倍。同时,与以前的工作相比,我们获得的几何子例程要小得多,它仅包含4个谓词,凸多边形构造函数和凸多边形分割例程。在此基础上使用基于BSP树的布尔算法使我们能够显式处理所有几何退化(曲面变成平面,线变成了点),而无需面对大量复杂情况。