|
|
Fast mesh segmentation algorithm based on tensor voting |
SHU Zhen-yu1,2, WANG Guo-zhao1 |
1. Institute of Computer Graphics and Image Processing, Department of Mathematics, Zhejiang University, Hangzhou 310027, China; 2. Laboratory of Information and Optimization Technologies, Ningbo Institute of Technology, Zhejiang University, Ningbo 315100, China |
|
|
Abstract A novel algorithm for triangular mesh segmentation based on tensor voting theory was proposed to correctly segment the input triangular mesh according to the sharp geometrical features on the mesh. All triangles of the input mesh clustered to a user-specified number of regions such that the sharp geometrical features of vertices belonging to the same region were as similar as possible. With the correspondence between the sharp geometrical features and the distribution of normal tensor voting matrix’s eigen values, the mesh segmentation was converted to an energy minimization problem. Then a fast clustering method was applied to solve the problem with simplified energy terms. By introducing a heuristic constraint, no segment was separated into disconnected parts with the algorithm. Experimental results show that the algorithm is faster and the regions with sharp geometrical features are segmented better compared with some existing algorithms.
|
Published: 14 July 2011
|
|
基于张量投票的快速网格分割算法
为了根据网格模型上的尖锐几何特征对三角网格曲面进行合理分片,提出一种新的基于张量投票(tensor voting)理论的三角网格分割算法.该算法将输入网格模型上所有的三角面片聚类成由用户指定数目的若干个区域,使得区域内部三角面片上点的尖锐几何特征尽可能接近.根据网格模型顶点上基于法向的张量投票矩阵的特征值分布与顶点尖锐几何特征的对应关系,算法将网格分割转化为能量最小化问题,并适当简化能量函数的形式,用快速聚类算法求解.通过引入启发式约束,算法较好地防止了分割区域的分离.实验表明:与已有算法相比,该算法具有较快的速度,同时能够较好地分割网格曲面上的尖锐几何特征区域.
|
|
[1] SHU Z, WANG G, DONG C. Adaptive triangular mesh coarsening with centroidal Voronoi tessellations[J]. Journal of Zhejiang UniversityScience A, 2009, 10(4): 535-545. [2] COHENSTEINER D, ALLIEZ P, DESBRUN M. Variational shape approximation[C]∥ ACM SIGGRAPH 2004 Papers. Los Angeles: ACM, 2004: 905-914. [3] GELFAND N, GUIBAS L J. Shape segmentation using local slippage analysis[C]∥ Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing. Nice, France: ACM, 2004: 214-223. [4] RENIERS D, TELEA A. Hierarchical parttype segmentation using voxelbased curve skeletons[J]. The Visual Computer, 2008, 24(6): 383-395. [5] LAI Y K, HU S M, MARTIN R R, et al. Fast mesh segmentation using random walks[C]∥ Proceedings of the 2008 ACM Symposium on Solid and Physical Modeling. New York: ACM, 2008: 183-191. [6] MORTARA M, PATAN G, SPAGNUOLO M. From geometric to semantic human body models[J]. Computers & Graphics, 2006, 30(2): 185-196. [7] VARADY T, MARTIN R R, COX J. Reverse engineering of geometric models--an introduction[J]. ComputerAided Design, 1997, 29(4): 255-268. [8] SHAH J J, ANDERSON D, KIM Y S, et al. A discourse on geometric feature recognition from CAD models[J]. Journal of Computing and Information Science in Engineering, 2001, 1(1): 41-51. [9] IP C Y, REGLI W C. Manufacturing classification of CAD models using curvature and SVMs[C]∥ Proceedings of the International Conference on Shape Modeling and Applications 2005. Cambridge: IEEE Computer Society, 2005: 363-367. [10] SANDER P V, SNYDER J, GORTLER S J, et al. Texture mapping progressive meshes[C]∥ Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM, 2001: 409-416. [11] SORKINE O, COHENOR D, GOLDENTHAL R, et al. Boundeddistortion piecewise mesh parameterization[C]∥ Proceedings of the Conference on Visualization ’02. Boston: IEEE Computer Society, 2002: 355-362. [12] ZHANG E, MISCHAIKOW K, TURK G. Featurebased surface parameterization and texture mapping[J]. ACM Transactions on Graphics, 2005, 24(1): 1-27. [13] SANDER P V, WOOD Z J, GORTLER S J, et al. Multichart geometry images[C]∥ Proceedings of the 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry processing. Aachen: Eurographics Association, 2003: 146-155. [14] KALVIN A D, TAYLOR R H. Superfaces: Polygonal Mesh Simplification with Bounded Error[J]. IEEE Computer Graphics and Applications, 1996, 16(3): 64-77. [15] GARLAND M, WILLMOTT A, HECKBERT P S. Hierarchical face clustering on polygonal surfaces[C]∥ Proceedings of the 2001 Symposium on Interactive 3D graphics. New York: ACM, 2001: 49-58. [16] SHEFFER A. Model simplification for meshing using face clustering[J]. ComputerAided Design, 2001, 33(13): 925-934. [17] ZUCKERBERGER E, TAL A, SHLAFMAN S. Polyhedral surface decomposition with applications[J]. Computers & Graphics, 2002, 26(5): 733-743. [18] BOIERMARTIN I M. Domain decomposition for multiresolution analysis[C]∥ Proceedings of the 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry processing. Aachen: Eurographics Association, 2003: 31-40. [19] INOUE K, ITOH T, YAMADA A, et al. Face clustering of a largescale CAD model for surface mesh generation[J]. ComputerAided Design, 2001, 33(3): 251-261. [20] PETITJEAN S. A survey of methods for recovering quadrics in triangle meshes[J]. ACM Computing Surveys, 2002, 34(2): 211-262. [21] LAVOU G, DUPONT F, BASKURT A. A new CAD mesh segmentation method, based on curvature tensor analysis[J]. ComputerAided Design, 2005, 37(10): 975-987. [22] WU Jianhua, LEIF K. Structure recovery via hybrid variational surface approximation[J]. Computer Graphics Forum, 2005, 24(3): 277-284. [23] ATTENE M, FALCIDIENO B, SPAGNUOLO M. Hierarchical mesh segmentation based on fitting primitives[J]. The Visual Computer, 2006, 22(3): 181-193.< |
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|