The Study On Optimization Of Regularized Boolean Operation On Triangulated Polyhedrons

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 fast regularized 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.