Journal of Software:2016.27(10):2473-2487

(上海交通大学 计算机科学与工程系, 上海 200240;欧特克(中国)软件研发有限公司, 上海 200122;上海交通大学 计算机科学与工程系, 上海 200240;计算机科学国家重点实验室(中国科学院 软件研究所), 北京 100190)
Optimization of Set Operations on Triangulated Polyhedrons Using Adaptive Lazy Splitting
JIANG Xu-Dong,SHENG Bin,MA Li-Zhuang,SHEN Rui-Min,WU En-Hua
(Department of Computer Science and Engineering, Shanghai Jiaotong University, Shanghai 200240, China;Autodesk(China) Software Research and Development Co., Ltd., Shanghai 200122, China;Department of Computer Science and Engineering, Shanghai Jiaotong University, Shanghai 200240, China;State Key Laboratory of Computer Science(Institute of Software, The Chinese Academy of Sciences), Beijing 100190, China)
Chart / table
Similar Articles
Article :Browse 2176   Download 1469
Received:January 20, 2016    Revised:March 25, 2016
> 中文摘要: 规则化的布尔运算被广泛应用在三维建模系统中.近年来,随着图形硬件的发展,基于三角网格的规则化布尔算法由于输出结果能直接被图形硬件处理,表现出了明显的优势.但是传统的算法由于采用CSG树局部评估策略,使得面片在相交测试中反复被切割,并且由于面片分类在切割后的模型之间直接进行,导致算法无法在保证鲁棒性的同时实现高性能.为了避免这些问题,提出了一种CSG树全局评估算法来统一执行单次和连续布尔运算.算法由两部分组成:自适应的延迟切割和全局化面片分类.在自适应的延迟切割阶段,算法通过仔细处理多个三角面片相交导致的各种情况扩展延迟切割到整个CSG树来避免由于面片的反复切割带来的数值误差累积,并利用自适应的八叉树使得相交测试可在线性时间内完成.在全局化面片分类阶段,算法通过分治法使得分类始终在切割后的面片和原始输入模型之间进行来保证分类的精度;通过结合组分类策略和自适应的八叉树来进一步优化分类性能.实验结果表明,所提算法无论是在执行单次还是在连续布尔运算时,都能在保证鲁棒性的同时性能优于其他算法,因此该算法可广泛应用于交互式建模系统中,如数字雕刻、计算机辅助设计和制造(CAD/CAM)等.
Abstract: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 localized evaluation strategy over constructive solid geometry (CSG) tree 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, a novel algorithm is presented to realize robust, exact and fast regularized Boolean operations through global evaluation of CSG tree. 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, a lazy splitting strategy is applied to the whole CSG tree by coping with all intersection cases of triangular facets in order to eliminate the accumulation of number errors. In 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, the classification method is always executed 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 offers wide-ranging usage in for interactive modeling systems, such as digital sculpture, and CAD/CAM.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(61572316,61133009);国家高技术研究发展计划(863)(2015AA015904) 国家自然科学基金(61572316,61133009);国家高技术研究发展计划(863)(2015AA015904)
Foundation items:National Natural Science Foundation of China (61572316, 61133009); National High Technology Research and Development Program of China (863) (2015AA015904)
Reference text:


JIANG Xu-Dong,SHENG Bin,MA Li-Zhuang,SHEN Rui-Min,WU En-Hua.Optimization of Set Operations on Triangulated Polyhedrons Using Adaptive Lazy Splitting.Journal of Software,2016,27(10):2473-2487