基于自适应延迟切割的三角网格布尔运算优化

规则化的布尔运算被广泛应用在三维建模系统中.近年来，随着图形硬件的发展，基于三角网格的规则化布尔算法由于输出结果能直接被图形硬件处理，表现出了明显的优势.但是传统的算法由于采用CSG树局部评估策略，使得面片在相交测试中反复被切割，并且由于面片分类在切割后的模型之间直接进行，导致算法无法在保证鲁棒性的同时实现高性能.为了避免这些问题，本文呈现了一种CSG树全局评估算法来统一执行单次和连续布尔运算.算法由两部分组成：自适应的延迟切割和全局化面片分类.在自适应的延迟切割阶段，算法通过仔细处理多个三角面片相交导致的各种情况使得延迟切割被扩展到整个CSG树来避免由于面片的反复切割带来的数值误差累积并利用自适应的八叉树使得相交测试能在线性时间内完成.在全局化面片分类阶段，算法通过分治法使得分类始终在切割后的面片和原始输入模型之间进行来保证分类的精度；通过结合组分类策略和自适应的八叉树来进一步优化了分类性能。实验结果表明，本文提出的算法无论是在执行单次或连续布尔运算时都能在保证鲁棒性同时性能优于其他的算法，因此本文算法可广泛应用于交互式建模系统中，如数字雕刻、计算机辅助设计和制造（CAD/CAM）等.

Optimization of Set Operations on Triangulated Polyhedrons Using Adaptive Lazy Splitting

Regularized Boolean Operations have been widely used in 3D modeling systems. In recent years, Boolean algorithms based on triangular polyhedron show the distinct advantages aligning with the development of graphic hardware, as their outputs can be processed by graphic hardware directly. But most existing methods rely on constructive solid geometry (CSG) tree localized evaluation strategy to perform regularized set operations. As a result, these methods cannot guarantee robustness while synchronously keeping high efficiency, because a facet may repeatedly split up in the splitting phase and the facets classification is carried out between the split polyhedrons by triangulation. In this paper, we present a novel algorithm to realize robust, exact and fastregularized Boolean operations through CSG tree global evaluation strategy. The algorithm is comprised of two steps:adaptive lazy splitting and globalized facets classification. The two steps aim to optimize splitting and facets classification phases of the regularized Boolean algorithms on triangulated polyhedrons respectively. In the adaptive lazy splitting phase, we apply a lazy splitting strategy to the whole CSG tree by coping with all intersection cases of triangular facets in order to eliminate the accumulation of number errors. At the meantime, an adaptive octree is employed to speed up the intersection test process. In the globalized facets classification phase, to ensure the accuracy of classification, we always execute the classification method between the split facet and the original input polyhedrons by divide and conquer algorithm. The performance of classification is further optimized by combining the grouping classification strategy and the octree. Experimental results demonstrate that the proposed approach cannot only guarantee the robustness of Boolean computations but also achieve better performance than existing approaches. Thus, the algorithm can be widely used for interactive modeling systems, such as digital sculpture, CAD/CAM etc.