北京航空航天大学学报 ›› 2018, Vol. 44 ›› Issue (4): 851-861.doi: 10.13700/j.bh.1001-5965.2017.0282

• 论文 • 上一篇    下一篇

基于八叉树的简化构型三角片等值面削减算法

徐雷, 王华锋, 潘海侠, 林广艳, 陈栎曦   

  1. 北京航空航天大学软件学院, 北京 100083
  • 收稿日期:2017-05-05 出版日期:2018-04-20 发布日期:2018-04-27
  • 通讯作者: 王华锋 E-mail:wanghuafeng@buaa.edu.cn
  • 作者简介:徐雷,男,硕士研究生。主要研究方向:模式识别、机器学习;王华锋,男,博士,副教授,硕士生导师。主要研究方向:图像处理、模式识别、机器学习。

Octree based decimation algorithm for triangle isosurface using simplified patterns

XU Lei, WANG Huafeng, PAN Haixia, LIN Guangyan, CHEN Yuexi   

  1. School of Software, Beijing University of Aeronautics and Astronautics, Beijing 100083, China
  • Received:2017-05-05 Online:2018-04-20 Published:2018-04-27

摘要: 采用简化构型的SMC算法相比标准MC算法能够有效减少构成等值面的三角片的数量,但因为其仅是在体元内部的简化,所以不能较好地利用数据集表面局部形态特征。针对这一问题进一步提出OSMC算法。其根据简化构型的特点,首先采用八叉树结构组织体元,然后采用自底向上的合并策略合并节点,最后实现局部区域三角片合并。实验证明:OSMC算法能够实现比SMC算法更多的三角片削减,尤其对于具有较多平坦区域的数据集效果显著,其对公开数据集数据的平均削减率为55.1%,而SMC算法为29.7%,在面对高分辨率的地质数据时其最高削减率达到了80%,平均也超过了50%,同时OSMC算法能够更好地适应数据集分辨率的增长。

关键词: 等值面, MC算法, SMC算法, 八叉树, 超体元

Abstract: It is universally acknowledged that SMC based on simplified patterns extracts less triangles than the standard MC. Because only in-cube decimation was exploited, SMC is not able to take full advantage of local features of isosurfaces. Based on this observation, a new method named OSMC is presented in this paper. Based on characteristics of simplified configuration, OSMC first use octree structure to organize cells as nodes, then merge the nodes from bottom to top, and finally achieve local area triangles merging. The experimental results illustrate that the proposed method does further decimation than SMC, especially for datasets with large flat areas. The proposed method achieves an average reduction rate up to 55.1%, while the average reduction rate for SMC is 29.7%. The reduction rate reaches 80% at the highest and it is above 50% in average when OSMC is used on high-resolution geological dataset. Moreover, the new method is more adaptive to the increment of the dataset resolution.

Key words: isosurface, MC algorithm, SMC algorithm, octree, super cell

中图分类号: 


版权所有 © 《北京航空航天大学学报》编辑部
通讯地址:北京市海淀区学院路37号 北京航空航天大学学报编辑部 邮编:100191 E-mail:jbuaa@buaa.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发