主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2018年第12期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
姜旭东,盛斌,马利庄,申瑞民,吴恩华.基于自适应延迟切割的三角网格布尔运算优化.软件学报,2016,27(10):2473-2487
基于自适应延迟切割的三角网格布尔运算优化
Optimization of Set Operations on Triangulated Polyhedrons Using Adaptive Lazy Splitting
投稿时间:2016-01-20  修订日期:2016-03-25
DOI:10.13328/j.cnki.jos.005086
中文关键词:  布尔运算  三角网格  构造实体几何  延迟切割  自适应八叉树
英文关键词:Boolean operations  triangular polyhedron  constructive solid geometry  lazy splitting  adaptive octree
基金项目:国家自然科学基金(61572316,61133009);国家高技术研究发展计划(863)(2015AA015904)
作者单位E-mail
姜旭东 上海交通大学 计算机科学与工程系, 上海 200240
欧特克(中国)软件研发有限公司, 上海 200122 
 
盛斌 上海交通大学 计算机科学与工程系, 上海 200240
计算机科学国家重点实验室(中国科学院 软件研究所), 北京 100190 
shengbin@cs.sjtu.edu.cn 
马利庄 上海交通大学 计算机科学与工程系, 上海 200240  
申瑞民 上海交通大学 计算机科学与工程系, 上海 200240  
吴恩华 计算机科学国家重点实验室(中国科学院 软件研究所), 北京 100190  
摘要点击次数: 1631
全文下载次数: 1163
中文摘要:
      规则化的布尔运算被广泛应用在三维建模系统中.近年来,随着图形硬件的发展,基于三角网格的规则化布尔算法由于输出结果能直接被图形硬件处理,表现出了明显的优势.但是传统的算法由于采用CSG树局部评估策略,使得面片在相交测试中反复被切割,并且由于面片分类在切割后的模型之间直接进行,导致算法法在保证鲁棒性的同时实现高性能.为了避免这些问题,提出了一种CSG树全局评估算法来统一执行单次和连续布尔运算.算法由两部分组成:自适应的延迟切割和全局化面片分类.在自适应的延迟切割阶段,算法通过仔细处理多个三角面片相交导致的各种情况扩展延迟切割到整个CSG树来避免由于面片的反复切割带来的数值误差累积,并利用自适应的八叉树使得相交测试可在线性时间内完成.在全局化面片分类阶段,算法通过分治法使得分类始终在切割后的面片和原始输入模型之间进行来保证分类的精度;通过结合组分类策略和自适应的八叉树来进一步优化分类性能.实验结果表明,所提算法论是在执行单次还是在连续布尔运算时,都能在保证鲁棒性的同时性能优于其他算法,因此该算法可广泛应用于交互式建模系统中,如数字雕刻、计算机辅助设计和制造(CAD/CAM)等.
英文摘要:
      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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利