Abstract
In this paper, we describe a hierarchical face clustering algorithm for triangle meshes based on fitting primitives belonging to an arbitrary set. The method proposed is completely automatic, and generates a binary tree of clusters, each of which is fitted by one of the primitives employed. Initially, each triangle represents a single cluster; at every iteration, all the pairs of adjacent clusters are considered, and the one that can be better approximated by one of the primitives forms a new single cluster. The approximation error is evaluated using the same metric for all the primitives, so that it makes sense to choose which is the most suitable primitive to approximate the set of triangles in a cluster.
Based on this approach, we have implemented a prototype that uses planes, spheres and cylinders, and have experimented that for meshes made of 100 K faces, the whole binary tree of clusters can be built in about 8 s on a standard PC.
The framework described here has natural application in reverse engineering processes, but it has also been tested for surface denoising, feature recovery and character skinning.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Alliez, P., Cohen-Steiner, D., Devillers, O., Levy, B., Desbrun, M.: Anisotropic polygonal remeshing. ACM Trans. Graph. 22(3), 485–493 (2003)
Attene, M., Biasotti, S., Spagnuolo, M.: Shape understanding by contour-driven retiling. Visual Comput. 19(2-3), 127–138 (2003)
Attene, M., Falcidieno, B., Rossignac, J., Spagnuolo, M.: Sharpen&bend: recovering curved sharp edges in triangle meshes produced by feature-insensitive sampling. IEEE Trans. Vis. Comput. Graph.11(2), 181–192 (2005)
Biasotti, S., Falcidieno, B, Spagnuolo, M.: Surface understanding based on extended reeb graph representation. In: Rana, S. (ed.) Topological Data Structures for Surfaces: An Introduction to Geographical Information Science, pp. 87–102. Wiley publishers (2004)
Chaperon, T., Goulette, F.: Extracting cylinders in full 3D data using a random sampling method and the Gaussian image. Proceedings of VMV 2001, held in Stuttgart, Germany, pp. 35–42 Aka GmbH (2001)
Cignoni, P., Rocchini, C., Scopigno, R.: Metro: measuring error on simplified surfaces. Comput. Graph. Forum 17(2) (Proceedings of Eurographics ’98), 167–174 (1998)
Cohen-Steiner, D., Alliez, P. and Desbrun, M.: Variational Shape Approximation. ACM Trans. Graph. 23(3), 905–914 (2004)
Garland, M., Willmott, A., Heckbert, P.S.: Hierarchical face clustering on polygonal surfaces. Proceedings ACM Symposium on Interactive 3D Graphics, pp. 49–58 (2001)
Gelfand, N., Guibas, L.J.: Shape segmentation using local slippage analysis. Proceedings Eurographics Symposium on Geometry Processing, pp. 219–228 (2004)
Glantz, S.A., Slinker, B.K.: Primer of Applied Regression and Analysis of Variance. McGraw-Hill Medical, ISBN 0071360867 (2000)
Jolliffe, I.T.: Principal Component Analysis. Springer, Berlin Heidelberg New York (1986)
Lewis, J. P., Cordner, M., Fong, N.: Pose space deformations: a unified approach to shape interpolation and skeleton-driven deformation. In Proceedings ACM SIGGRAPH 2000, pp. 165–172 (2000)
Lloyd, S.: Least square quantization on PCM. IEEE Trans. Information Theory 18, 129–137 (1982)
Marr, D.: Vision. Freeman Publishers, New York (1982)
Meyer, M., Desbrun, M., Schröder, P., Barr, A.H.: Discrete differential geometry operators for triangulated 2-manifolds. Visualization and Mathematics III, 35–57 (2003)
Mortara, M., Patanè, G., Spagnuolo, M., Falcidieno, B. and Rossignac, J.: Blowing bubbles for multi-scale analysis and decomposition of triangle meshes. Algoritmica 38(2), 227–248 (2003)
Petitjean, S.: A survey of methods for recovering quardics in triangle meshes. ACM Comput. Surv. 34(2), 211–262 (2002)
Ponce, J., Brady, J.: Toward a surface primal sketch. In: Kanade, T (ed.) Three-Dimensional Machine Vision, pp. 195–240. Kluwer, Dordrecht (1987)
Pottman, H., Leopoldseder, S., Hofer, M., Steiner, T., Wang, W.: Industrial geometry: recent advances and applications in CAD. Comput.-Aid. Des. 1, 513–522 (2004)
Pratt, V.: Direct least-squares fitting of algebraic surfaces. Computer Graphics 21(4), 145–152 (Proceedings of SIGGRAPH’87) (1987)
Renner, G., Várady, T., Wiess, V.: Reverse engineering of free-form features. In Proceedings of PROLAMAT 98, Trento, IFIP (1998)
Rössl, C., Kobbelt, L., Seidel, H.-P.: Extraction of feature lines on triangulated surfaces using morphological operators. In Proc. of Smart Graphics’00, AAAI Spring Symposium, pp. 71–75 (2000)
Sander, P., Wood, Z., Gortler, S.J., Snyder, J., Hoppe, H.: Multi-chart geometry images. In Proceedings of the Eurographics Symposium on Geometry Processing, pp. 146–155 (2003)
Sapidis, N., Besl, P.: Direct construction of polynomial surfaces from dense range images through region growing. ACM Trans. Graph. 14(2), 171–200 (1995)
Scales, L.E.: Introduction to Non-linear Optimization. Springer, Berlin Heidelberg New York (1985)
Thompson, W.B., Owen, J.C., James de St. Germain, H., Stark, S.R., Henderson, T.C.: Feature-based reverse engineering of mechanical parts. IEEE Trans. Robot. Autom. 15(1), 57–66 (1999)
Várady, T., Martin, R.: Reverse engineering. In Handbook of Computer Aided Geometric Design, pp. 651–681. Elsevier (2002)
Várady, T., Benkö, P., Kós, G.: Reverse engineering regular objects: simple segmentation and surface fitting procedures. Int. J. Shape Modeling 4(3), 127–141 (1998)
Vergeest, J.S.M., Horváth, I., Kuczogi, G., Opyio, E., Wiegers, T.: Reverse engineering for shape synthesis in industrial engineering. In Proceedings of the 26th International Conference on Computers in Industrial Engineering, 15–17 December, Melbourne, Australia, pp. 84–90 (1999)
Watanabe, K., Belyaev, A.G.: Detection of salient curvature features on polygonal surfaces. Comput. Graph. Forum 20(3), 385–392 (Proceedings of Eurographics‘01) (2001)
Wu, J., Kobbelt, L.: Structure recovery via hybrid variational surface approximation. Proc. Eurographics 2005, Comput. Graph. Forum 24(3), 277–284 (2005)
Yang, M., Lee, E.: Segmentation of measured point data using a parametric quadric surface approximation. Comput. Aid. Des. 31(7), 449–458 (1999)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Attene, M., Falcidieno, B. & Spagnuolo, M. Hierarchical mesh segmentation based on fitting primitives. Visual Comput 22, 181–193 (2006). https://doi.org/10.1007/s00371-006-0375-x
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00371-006-0375-x