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

来源：软件学报杂志2016年第10期北京时间：

作者：姜旭东,盛斌,马利庄,申瑞民,吴恩华

单位：姜旭东，上海交通大学 计算机科学与工程系, 上海 200240;欧特克(中国)软件研发有限公司, 上海 20012211,盛斌，上海交通大学 计算机科学与工程系, 上海 200240;计算机科学国家重点实验室(中国科学院 软件研究所), 北京 10019002,马利庄，上海交通大学 计算机科学与工程系, 上海 20024003,申瑞民，上海交通大学 计算机科学与工程系, 上海 20024004,吴恩华，计算机科学国家重点实验室(中国科学院 软件研究所), 北京 10019005

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

关键词：布尔运算;三角网格;构造实体几何;延迟切割;自适应八叉树

基金资助：国家自然科学基金（61572316，61133009）；国家高技术研究发展计划（863）（2015AA015904）