构造实体几何(Constructive Solid Geometry,CSG)一直以来是计算机辅助设计/制造(Computer Aid Design/Manufacture,CAD/CAM)领域常用的建模方法。它将简单的元几何体通过布尔运算、刚体变换(平移、缩放、仿射变换)和曲面细分等操作拼...
详细信息
构造实体几何(Constructive Solid Geometry,CSG)一直以来是计算机辅助设计/制造(Computer Aid Design/Manufacture,CAD/CAM)领域常用的建模方法。它将简单的元几何体通过布尔运算、刚体变换(平移、缩放、仿射变换)和曲面细分等操作拼接起来构成更为复杂的模型。其中,布尔运算——将多个几何元(primitive)通过并、交、差结合成一个复杂几何体的运算——已经被研究了很多年。基于边界表示的精确布尔运算(以下简称布尔运算)的主要挑战是如何兼顾算法的鲁棒性和性能。在现代计算机当中,浮点数的计算存在不可避免的截断误差,而在布尔运算当中,浮点误差会产生错误的拓扑结构,甚至导致程序崩溃。因此,很多布尔算法选择采用精确数值运算来解决鲁棒性问题。然而,精确数值计算通常要比一般浮点数运算慢一个数量级以上,并且需要数倍于一般浮点数的存储空间。这个问题在面对包含大量面片的复杂场景时尤为突出。而不用精确数值运算的布尔算法,通常只能部分的解决鲁棒性的问题。它们使用数值容差的方法减少错判,或者通过引入随机数值抖动来避免退化情形。然而,这些方法都不够可靠。浮点误差广泛存在于布尔运算的各个阶段,仅仅通过一些小技巧,而不是系统性的解决方案,是难以奏效的。本文提出了一种新的基于三角形网格的布尔运算方法,它在正则闭集输入下具有完备的鲁棒性,并且有和不鲁棒的算法相近的性能。我们的方法避免了使用低效的精确数值运算,而选择将平面表示嵌入了三角网格当中,形成一种对几何实体的混合表示方法,并在此混合表示方法上进行布尔运算。通过该混合表示方法中的平面表示信息,我们避免了计算过程中浮点误差的引入,避免了计算新的顶点坐标,并使得所有退化几何情形可以被系统地妥善处理。另一方面,边界表示信息被用来进行粗略判断和高效的邻接查询,大大减少了相对低效的基于平面表示的几何计算的需求。另外,我们的算法不仅仅可以用于处理二元的布尔运算,还可以用于进行复合布尔表达式的求值。传统方法对于复杂布尔表达式,通常首先将表达式分解为多个二元布尔运算,并逐个进行布尔运算求值。这种思路存在两个问题:第一,如果每一次进行布尔运算的结果带有误差,而这个运算结果又被用于接下来的布尔运算,则误差会在求值过程中积累,产生不可预测的错误;第二,在某些情形下,连续多次的二元布尔运算可能存在大量的重复计算。我们的方法可以一次性得到一个复合布尔表达式的最终模型,因而赋予了使用者优化求值策略以提高性能的可能。通过实验证明,我们提出的布尔运算方法拥有与不鲁棒的布尔运算方法相近的性能,却可以做到对正则闭集输入无条件鲁棒。相比而言,绝大部分鲁棒的布尔运算方法都要比不鲁棒的算法慢近一个数量级以上。
暂无评论