基于Delaunay四面体剖分的网格分割算法

为了构建有意义曲面分片,提出一种基于Delaunay四面体剖分的网格分割算法.首先根据Delaunay四面体剖分得到多边形网格内部的四面体,求出每个面上反映网格内部信息的Delaunay体距离;然后对Delaunay体距离进行平滑处理,再对网格上面的Delaunay体距离进行聚类,用高斯混合模型对Delaunay体距离作柱状图的拟合,利用期望最大化算法来快速求得拟合结果;最后结合图切分技术,同时考虑聚类的结果、分割区域的边界平滑和视觉认知中的最小规则,得到最终的网格分割结果.实验结果表明,采用文中算法可以有效地实现有意义的网格分割.

Mesh Segmentation Based on 3D Delaunay Triangulation

A novel mesh segmentation algorithm based on 3D Delaunay triangulation is presented to partition meshes meaningfully. A volume-based distance (VD) for each face is first computed using 3D Delaunay triangulation. After a smoothing process, clustering of the mesh faces is performed to extract k clusters based on their VD values: a Gaussian mixture model (GMM) fitting k Gaussians to the histogram of VD values of the faces, this is achieved using the expectation-maximization (EM) algorithm. Finally, by considering the quality of clustering, the smoothness of the partition boundary and the minima rule proposed in human cognitive vision theory, our method employs a graph-cut algorithm to get the meaningful partitioning. Experiment indicates that the method is efficient and can partition a mesh into meaningful parts.