基于降维的三维布尔运算算法与实现

摘要

目前，通过计算机辅助建模生成物体是最高效也是最广泛应用的方法，布尔运算在建模过程中的作用显得尤为重要。其中二维布尔运算一般应用于二维建模以及为三维建模提供计算基础的低维运算；三维布尔运算在工程设计、工程制造、计算机辅助教学、动画设计等一系列领域具有广泛应用，是计算机辅助造型中最基础、最核心的部分。三维布尔运算算法的核心问题是解决因运算对象相互间的共点、共线和共面引起的奇异问题，它影响了算法的稳定性，直接导致应用系统的可用性。本文讨论了一个由边界表示的两个一般多面体之间的三维布尔运算算法。试图用“降维”的办法将三维空间中的运算下降到在二维空间中进行，降低复杂性，解决奇异问题。在简要的描述三维布尔运算基本概念后，我们给出了具体的三维到二维的降维过程，讨论了在二维空间中解决奇异问题的方法，最后得到三维重构拓扑信息。使得三维布尔运算的算法大大简化，稳定性也得到了提高。为了验证本文的方法，在计算机辅助设计平台KerenCAD 上实现了此算法，并成功地完成了一些常用考题的布尔运算，结果表明了算法有较好的健壮性。