A survey on mesh segmentation techniques. (English) Zbl 1162.68769
Summary: We present a review of the state of the art of segmentation and partitioning techniques of boundary meshes. Recently, these have become a part of many mesh and object manipulation algorithms in computer graphics, geometric modelling and computer aided design. We formulate the segmentation problem as an optimization problem and identify two primarily distinct types of mesh segmentation, namely part segmentation and surface-patch segmentation. We classify previous segmentation solutions according to the different segmentation goals, the optimization criteria and features used, and the various algorithmic techniques employed. We also present some generic algorithms for the major segmentation techniques.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 68U07 | Computer science aspects of computer-aided design |
References:
| [1] | Amenta, The power crust, unions of balls, and the medial axis transform, Computational Geometry: Theory and Applications 19 (2-3) pp 127– (2001) · Zbl 0988.65015 · doi:10.1016/S0925-7721(01)00017-7 |
| [2] | Alliez, Anisotropic polygonal remeshing, ACM Transactions on Graphics. Special issue for SIGGRAPH conference pp 485– (2003) · doi:10.1145/882262.882296 |
| [3] | Attene, Hierarchical mesh segmentation based on fitting primitives, The Visual Computer 22 (3) pp 181– (2006) |
| [4] | [AHD96]ArabieR., HubertL., DeSoeteG. (Eds.): Clustering and Classification. World Scientific Publishers, River Edge, NJ, 1996. · Zbl 0874.90198 |
| [5] | [Aim]Aim At Shape: Advanced and innovative models and tools for the development of semantic-based systems for handling, acquiring, and processing knowledge embedded in multidimensional digital objects. http://www.aim-at-shape.net/, February 2007. |
| [6] | Attene, Proceedings Shape Modeling International (SMI’06) pp 14– (2006) |
| [7] | [AY95] Alpert C. , Yao S. : Spectral partitioning: The more eigenvectors, the better. In 32nd ACM/IEEE Design Automation Conference (San Francisco, 1995), pp. 195-200. |
| [8] | Bajaj, Convex decomposition of polyhedra and robustness, SIAM Journal on Computing 21 (2) pp 339– (1992) · Zbl 0747.68093 |
| [9] | [BMM*03] Biasotti S. , Marini S. , Mortara M. , Patane G. , Spagnuolo M. , Falcidieno B. : Proceedings ofthe 11th International Conference On Discrete Geometry for Computer Imagery DGCI 2003, Naples, Italy, November 19-21, 2003 Lecture Notes in Computer Science Springer, Berlin/Heidelberg Volume 2886/2003, pp. 194-203. |
| [10] | Biederman, Recognition-by-components: A theory of human image understanding, Psychological Review 94 pp 115– (1987) |
| [11] | [BJ01] Boykov Y. , Jolly M. : Interactive graph cuts for optimal boundary & region segmentation of objects in n-d images. In International Conference on Computer Vision (ICCV) (2001), vol. I, pp. 105-112. |
| [12] | [BM03] Boier-Martin I. M. : Domain decomposition for multiresolution analysis. In Proceedings of the Eurographics Symposium on Geometry Processing (2003), pp. 29-40. |
| [13] | Choi, Mathematical theory of medial axis transform, Pacific Journal of Mathematics 181 (1) pp 57– (1997) · Zbl 0885.53004 |
| [14] | Chazelle, Strategies for polyhedral surface decomposition: An experimental study, Computational Geometry: Theory and Applications 7 (4-5) pp 327– (1997) · Zbl 1133.52305 · doi:10.1016/S0925-7721(96)00024-7 |
| [15] | Chazelle, STOC ’81: Proceedings of the thirteenth annual ACM symposium on Theory of computing pp 70– (1981) |
| [16] | Chung, Spectral Graph Theory (1997) · Zbl 0867.05046 |
| [17] | Comaniciu, Mean shift: A robust approach towards feature space analysis, IEEE Trans. Pattern Analysis and Machine Intelligence 24 pp 603– (2002) |
| [18] | Chazelle, Algebraic Geometry and its Applications pp 419– (1994) · doi:10.1007/978-1-4612-2628-4_27 |
| [19] | Cohen-Steiner, Variational shape approximation, ACM Transactions on Graphics 23 (3) pp 905– (2004) |
| [20] | Cohen-Steiner, SCG ’03: Proceedings of the nineteenth annual symposium on Computational geometry pp 312– (2003) · Zbl 1422.65051 · doi:10.1145/777792.777839 |
| [21] | Cornea, Curve skeleton, properties and algorithms, IEEE Transactions on Visualization and Computer Graphics accepted for publication (2007) |
| [22] | Delingette, General object reconstruction based on simplex meshes, International Journal of Computer Vision 32 (2) pp 111– (1999) |
| [23] | Duda, Pattern Classification (2nd ed.) (2000) |
| [24] | DeRose, ACM Computer Graphics, Proc. SIGGRAPH 1998 pp 85– (1998) |
| [25] | Dey, Algorithms - ESA 2002: 10th Annual European Symposium pp 387– (2002) |
| [26] | Eck, Proceedings of ACM SIGGRAPH 1995 pp 173– (1995) |
| [27] | Funkhouser, Modeling by example, ACM Transactions on Graphics (Proceedings SIGGRAPH 2004) 23 (3) pp 652– (2004) |
| [28] | Gunter, Ray tracing animated scenes using motion decomposition, Computer Graphics Forum (Proc. EG 2006) 3 pp 517– (2006) |
| [29] | Gelfand, SGP ’04: Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing pp 214– (2004) |
| [30] | Gu, Geometry images, ACM Transaction on Graphics, Special issue for SIGGRAPH conference 21 (3) pp 355– (2002) |
| [31] | Garey, Some simplified np-complete graph problems, Theoretical Computer Science 1 pp 237– (1976) · Zbl 0338.05120 |
| [32] | Gotsman, Proceedings of Shape Modeling International pp 165– (2003) |
| [33] | Gregory, Interactive surface decomposition for polyhedral morphing, The Visual Computer 15 pp 453– (1999) |
| [34] | Garland, Proc. ACM Symposium on Interactive 3D Graphics (2001) |
| [35] | Hoffman, Parts of recognition, Cognition 18 (1-3) pp 65– (1984) |
| [36] | Hoffman, Salience of visual parts, Cognition 63 pp 29– (1997) |
| [37] | Ip, International Conference on Shape Modeling and Applications 2005 (SMI’ 05) pp 363– (2005) |
| [38] | Inoue, Face clustering of a large-scale cad model for surface mesh generation, Computer Aided Design 33 pp 3– (2001) |
| [39] | Julius, D-charts: Quasi-developable mesh segmentation, Computer Graphics Forum (Proceedings Eurographics 2005) 24 (3) pp 981– (2005) |
| [40] | Ji, Easy mesh cutting, Computer Graphics Forum (Proc. EG 2006) 3 pp 283– (2006) |
| [41] | Karni, Proceedings of ACM SIGGRAPH 2000 pp 279– (2000) |
| [42] | Kraevoy, Shuffler: Modeling with Interchangeable Parts (2006) |
| [43] | [KK98] Karypis G. , Kumar V. : Metis: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices. http://www.users.cs.umn.edu/karypis/metis/metis.html, 1998, February 2007. |
| [44] | [KK99] Karypis G. , Kumar V. : Multilevel algorithms for multi-constraint graph partitioning. In Proceedings of the 36th ACM/IEEE conference on Design automation conference (New Orleans, Louisiana, 1999), pp. 343-348. |
| [45] | Katz, Mesh segmentation using feature point and core extraction, The Visual Computer (Proceedings of Pacific Graphics 2005) 21 (810) pp 865– (2005) |
| [46] | Kimmel, Fast marching methods on triangulated domains, Proceedings of the National Academy of Sciences 95 pp 8341– (1998) |
| [47] | Kraevoy, Cross-parameterization and compatible remeshing of 3D models, ACM Transaction on Graphics (Proceedings SIGGRAPH 2004) 23 (3) pp 861– (2004) |
| [48] | Kalvin, Superfaces: Polygonal mesh simplification with bounded error, IEEE Computer Graphics and Applications 16 (3) (1996) |
| [49] | Katz, Hierarchical mesh decomposition using fuzzy clustering and cuts, ACM Transactions on Graphics (Proceedings SIGGRAPH 2003) 22 (3) pp 954– (2003) · doi:10.1145/882262.882369 |
| [50] | Lien, Approximate convex decomposition of polyhedra (2006) |
| [51] | Lavoué, New cad mesh segmentation method A, based on curvature tensor analysis, Computer Aided Design 37 (10) pp 975– (2005) |
| [52] | Lien, Proceedings of ACM Solid and Physical Modeling Symposium (SPM’06) pp 219– (2006) |
| [53] | Lloyd, Least square quantization in pcm, IEEE Transactions on Information Theory 28 pp 129– (1982) · Zbl 0504.94015 |
| [54] | [LLS*04] Lee Y. , Lee S. , Shamir A. , Cohen-Or D. , Seidel H.-P. : Intelligent mesh scissoring using 3D snakes. In Proceedings of the 12th Pacific Conference on Computer Graphics and Applications (2004), pp. 279-287. |
| [55] | Lee, Mesh scissoring with minima rule and part salience, Computer Aided Geometric Design 22 (5) pp 444– (2005) · Zbl 1205.65120 |
| [56] | Lee, Proceedings of Computer Animation and Virtual Worlds pp 519– (2005) |
| [57] | Levy, ACM Computer Graphics, Proc. SIGGRAPH 2002 pp 362– (2002) |
| [58] | Li, Lazy snapping, ACM Transactions on Graphics 23 (3) pp 303– (2004) |
| [59] | [LTTH01] Li X. , Toon T. , Tan T. , Huang Z. : Decomposing polygon meshes for interactive applications. In Proceedings of the 2001 symposium on Interactive 3D graphics (2001), pp. 35-42. |
| [60] | [LZ04] Liu R. , Zhang H. : Segmentation of 3D meshes through spectral clustering. In The 12th Pacific Conference on Computer Graphics and Applications (PG’04) (Seoul, Korea, 2004), pp. 298-305. |
| [61] | Liu, Mesh segmentation via spectral embedding and contour analysis, Computer Graphics Forum, Eurographics Proceedings to appear (2007) |
| [62] | [MDSB02] Meyer M. , Desburn M. , Schröder P. , Barr A. H. : Discrete differential - geometry operators for triangulated 2-manifolds. In Proceedings VisMath ’02 (Berlin, 2002). |
| [63] | [MK01] Moulitsas I. , Karypis G. : Multilevel algorithms for generating coarse grids for multigrid methods. In Proceedings of the 2001 ACM/IEEE conference on Supercomputing (Denver, Colorado, 2001), pp. 45-45. |
| [64] | Mortara, Blowing bubbles for multi-scale analysis and decomposition of triangle meshes, Algorithmica 38 (1) pp 227– (2003) |
| [65] | Mortara, Proceedings of ACM Symposium on Solid Modeling and Applications pp 139– (2004) |
| [66] | Mortara, From geometric to semantic human body models, Computers & Graphics 30 (2) pp 185– (2006) |
| [67] | Mitani, Making papercraft toys from meshes using strip-based approximate unfolding, ACM Transaction on Graphics (Proceedings SIGGRAPH 2004) 23 (3) pp 259– (2004) |
| [68] | Mangan, Proc. IEEE Visualization 1998 Late Breaking Hot Topics (1998) |
| [69] | Mangan, Partitioning 3D surface meshes using watershed segmentation, IEEE Transactions on Visualization and Computer Graphics 5 (4) pp 308– (1999) |
| [70] | [NN99] Nikos C. , Nave D. : Simultaneous mesh generation and partitioning for delaunay meshes. In Proceedings of the 8th International Meshing Roundtable (South Lake Tahoe, 1999), pp. 55-66. |
| [71] | [PAKZ03] Page D. , Abidi M. , Koschan A. , Zhang Y. : Object representation using the minima rule and superquadrics for under vehicle inspection. In Proceedings of the 1st IEEE Latin American Conference on Robotics and Automation (2003), pp. 91-97. |
| [72] | Petitjean, A survey of methods for recovering quadrics in triangle meshes, ACM Computing Surveys 34 (2) pp 211– (2002) |
| [73] | [PKA03] Page D. , Koschan A. , Abidi M. : Perception-based 3D triangle mesh segmentation using fast marching watersheds. In Conference on Computer Vision and Pattern Recognition (CVPR ’03) - Volume II (2003), pp. 27-32. |
| [74] | Pratt, Direct least-squares fitting of algebraic surfaces, Computer Graphics (SIGGRAPH 1987) 21 (4) pp 145– (1987) |
| [75] | [PRF01] Pulla S. , Razdan A. , Farin G. : Improved curvature estimation for watershed segmentation of 3-dimensional meshes. manuscript, 2001. |
| [76] | Podolak, A planar-reflective symmetry transform for 3D shapes, ACM Transactions on Graphics (Proc. SIGGRAPH) 25 (3) (2006) · doi:10.1145/1141911.1141923 |
| [77] | Raab, Virtual woodwork: Generating bead figures from 3d models, International Journal on Shape Modeling 10 (1) pp 1– (2004) |
| [78] | Roberts, Parametric and non-parametric unsupervised cluster analysis, Pattern Recognistion 30 pp 327– (1997) |
| [79] | Shah, A discourse on geometric feature recognition from cad models, Journal of Computing and Infomations Science in Engineering 1 (1) pp 41– (2001) |
| [80] | Schreiner, Inter-surface mapping, ACM Transaction on Graphics (Proceedings SIGGRAPH 2004) 23 (3) pp 870– (2004) |
| [81] | Sharf, Snap-paste: An interactive technique for easy mesh composition, The Visual Computer (Proceedings of Pacific Graphics 2006) 22 pp 835– (2006) |
| [82] | [SCOGL02] Sorkine O. , Cohen-Or D. , Goldenthal R. , Lischinski D. : Bounded-distortion piecewise mesh parameterization. In Proceedings of IEEE Visualization 2002 (2002). |
| [83] | [Sha04] Shamir A. : A formalization of boundary mesh segmentation. In Proceedings of the second International Symposium on 3DPVT (3D Data Processing, Visualization, and Transmission) (2004), pp. 82-89. |
| [84] | Sheffer, Model simplification for meshing using face clustering, Computer Aided Design 33 pp 925– (2001) |
| [85] | Shi, Normalized cuts and image segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence 22 (8) pp 888– (2000) |
| [86] | [SPP*02] Sun Y. , Page D. L. , Paik J. K. , Koschan A. , Abidi M. A. : Triangle mesh-based edge detection and its application to surface segmentation and adaptive surface smoothing. In Proceedings of the International Conference on Image Processing ICIP02, Vol. III (Rochester, N.Y., 2002), pp. 825-828. |
| [87] | Shapira, Consistent Partitioning of Meshes (2005) |
| [88] | [SSGH01] Sander P. , Snyder J. , Gortler S. , Hoppe H. : Texture mapping progressive meshes. In Proceedings of ACM SIGGRAPH (2001), pp. 409-416. |
| [89] | [SSK05] Sattler M. , Sarlette R. , Klein R. : Simpler and efficient compression of animation sequence. In Proceedings of 2005 ACM SIGGRAPH/EG symposium on computer animation (2005), pp. 209-217. |
| [90] | Shlafman, Metamorphosis of polyhedral surfaces using decomposition, Computer Graphics forum 21 (3) (2002) |
| [91] | Shatz, Paper craft models from meshes, The Visual Computer (Proceedings of Pacific Graphics 2006) 22 (911) pp 825– (2006) |
| [92] | [SWG*03] Sander P. , Wood Z. , Gortler S. , Snyder J. , Hoppe H. : Multi-chart geometry images. In Proceedings of the Eurographics Symposium on Geometry Processing (2003), pp. 146-155. |
| [93] | [TM98] Tomasi C. , Manduchi R. : Bilateral filtering for gray and color images. In Proc. of the sixth international Conference of Computer Vision (1998), pp. 839-846. |
| [94] | Varady, Reverse engineering of geometric models-an introduction, Computer-Aided Design 29 (4) pp 255– (1997) |
| [95] | Wu, Structure recovery via hybrid variational surface approximation, Computer Graphics Forum (Proceedings Eurographics 2005) 24 (3) pp 277– (2005) |
| [96] | Wu, 3D part segmentation using simulated electrical charge distributions, IEEE transactions on pattern analysis and machine intelligence 19 (11) pp 1223– (1997) |
| [97] | Wu, Domain connected graph: the skeleton of a closed 3d shape for animation, The Visual Computer 22 (2) pp 117– (2006) |
| [98] | [ZH04] Zhou Y. , Huang Z. : Decomposing polygon meshes by means of critical points. In MMM ’04: Proceedings of the 10th International Multimedia Modelling Conference (Washington, DC, USA, 2004), IEEE Computer Society, p. 187. |
| [99] | Zhuang, Gaussian mixture density modelling: Decomposition and applications, IEEE Transactions on Image Processing 5 (9) pp 1293– (1996) |
| [100] | Zhang, Proceedings of Vision, Modeling, and Visualization pp 429– (2005) |
| [101] | Zhang, Feature-based surface parameterization and texture mapping, ACM Transaction on Graphics 24 (1) pp 1– (2005) |
| [102] | Zhou, SGP ’04: Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing pp 45– (2004) |
| [103] | Zockler, Fast and intuitive generation of geometric shape transitions, The Visual Computer 16 (5) pp 241– (2000) |
| [104] | Zuckerberger, Polyhedral surface decomposition with applications, Computers & Graphics 26 (5) pp 733– (2002) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
