基于张量投票的快速网格分割算法

《基于张量投票的快速网格分割算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、*基于张量投票的快速网格分割算法摘要:提出一种新的基于张量投票（Tensorvoting）理论的三角网格分割算法。该算法将给定的网格模型上所有的三角面片聚类成若干个集合，使得集合内部三角面片上点的几何特征尽量接近。根据张量投票矩阵的特征值分布与顶点几何特征的对应关系，算法将网格分割问题转化为目标能量函数最小化问题，并用快速聚类算法求解。实验表明，与已有算法相比，该算法具有较快的速度和较好的效果。关键词：网格分割；张量投票理论；聚类中图分类号TP391.4Fastmeshsegmentationbasedontens

2、orvotingtheoryAbstract:Inthispaper,wepresentanovelalgorithmfortriangularmeshsegmentationbasedontensorvotingtheory.Alltrianglesofinputmeshclustertoauser-specifiednumberofsegmentssuchthatgeometricalfeaturesofverticesbelongingtothesamesegmentareassimilaraspossibl

3、e.Accordingtothecorrespondencebetweeneigenvalues’distributionoftensorvotingmatrixandgeometricalfeatures,weconvertthemeshsegmentationtoanenergyminimizationproblem.Thenwesolveitbyintroducingafastfaceclusteringmethod.Experimentalresultsshowthatourmethodisfastande

4、ffective.Keywords:meshsegmentation;tensorvotingtheory;clustering网格分割技术在几何建模和数字几何处理中起着非常关键的作用。在网格参数化，纹理映射，形状匹配，几何变形，多分辨率建模，网格编辑，网格简化，压缩和动画等多个领域，[1]网格分割都有着重要的应用。例如，在文献中，作者先把三角网格分割成若干个近似的重心Voronoi区域(centroidalVoronoiregion)，然后将每个区域用一个中心点来代替，从而达到简化网格的目的。网格分割是指将一个网

5、格分割成若干个互不相交的区域，这些区域的并集[2]构成了网格本身。网格分割算法的结果往往要满足某些约束条件，例如，在文献中，给定[3]的网格被分割成若干个接近于平面的区域。在文献中，网格被分割成一些简单的几何曲面的近似，包括平面，球面，和圆柱面等等。本文提出了一种新的基于张量投票理论的网格分割算法。该算法通过最大化分割后子网格片上的能量函数，使得同一子网格片内部点的几何特征尽量相似，来实现对网格曲面的分割。实验表明该算法速度较快，效果较好。1.相关工作近些年来，为了适应各种不同的应用场合，很多网格分割算法被提了出来

6、。根据分割对象的不同，这些算法可以分为两大类。第一类将网格模型对应的体分割成若干个子几何体[4-6]。第二类则根据网格表面上的某些几何性质将网格模型分割成若干个表面片，例如，在[7-9]文献中，网格模型被分解成平面，圆柱面，及球面等基本几何形状。本文提出的算法根据网格曲面上的张量投票性质将网格分割成若干个表面片，因而属于上述第二类网格分割算法。一般来说，对于不同的应用场合，网格分割算法对分割后得到的子网格片的要求也各不[10-12][13]相同。例如，在纹理映射,几何图像（geometry-image）等应用领域中

7、,分割得到的*基金项目：国家自然科学基金(60773179，60970079)；国家“九七三”重点基础研究发展规划项目(2004CB318000)；宁波市自然科学基金(2009A610071)1子网格片应该尽量与圆盘同胚，而且在参数化到二维平面后，不应该引入较大的形变。另外，[2,14-19]在网格重构和网格简化等场合,子网格片经常会由一系列的平面多边形来代替，因此要求分割得到的子网格片应该尽量接近平面。根据对分割后子网格片特征的不同要求，有越[20,21]来越多的网格分割算法被提了出来。例如，文献提出了在CAD反

8、向工程和建模中以一[22,23]般二次曲面为分割目标的分割算法。在文献中，作者用平面，球面，圆柱面等基本几[24-26]何形状来替换子网格片。文献中提出了将网格模型分割成条带状面片和拟可展面片的分[3]割算法。在文献中，作者提出了基于滑移分析(slippageanalysis)的网格分割算法，该算法[27]得到的结果能够保证位于同一个表面片中的顶点和区域具有