基于深度遍历的网格模型表面分割算法

Mesh surface segmentation based on depth-first traversing

文章提出一种基于深度遍历进行网格模型表面分割的算法。该算法根据网格模型外表面拓扑结构特点,将模型表面所有的面片单元及其邻边以图的数据结构形式存储,再利用深度遍历的算法提取出所有满足法矢角度要求的面片单元。算例验证表明,算法在搜索过程中能够自动调整搜索区域的大小,以减少搜索量,并且能够快速稳定的处理各类复杂网格模型表面的分割问题,时间复杂度为0(n)。

An algorithm based on depth-first traversing was proposed for mesh surface segmentation. According to the topologic characteristics of the mesh model surface, all the elements of the model surface and the associated edges were stored in the format of graph data structure in this algorithm, then all the elements which met the normal vector angle requirements were searched out using the depth-first traversing algorithm of graph. The results showed that in the search process this algorithm could adjust the search area automatically to reduce the search volume and this search algorithm was fast and stable enough to handle all types of complex mesh models to extract the surface elements, the relevant time complexity was O（n）.