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

摘要

采用简化构型的SMC算法相比标准MC算法能够有效减少构成等值面的三角片的数量,但因为其仅是在体元内部的简化,所以不能较好地利用数据集表面局部形态特征.针对这一问题进一步提出OSMC算法.其根据简化构型的特点,首先采用八叉树结构组织体元,然后采用自底向上的合并策略合并节点,最后实现局部区域三角片合并.实验证明:OSMC算法能够实现比SMC算法更多的三角片削减,尤其对于具有较多平坦区域的数据集效果显著,其对公开数据集数据的平均削减率为55.1%,而SMC算法为29.7%,在面对高分辨率的地质数据时其最高削减率达到了80%,平均也超过了50%,同时OSMC算法能够更好地适应数据集分辨率的增长.%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 pa-per.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 experi-mental 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 aver-age when OSMC is used on high-resolution geological dataset.Moreover,the new method is more adaptive to the increment of the dataset resolution.