“Hierarchical mesh decomposition using fuzzy clustering and cuts” by Katz and Tal

  • ©Sagi Katz and Ayellet Tal




    Hierarchical mesh decomposition using fuzzy clustering and cuts



    Cutting up a complex object into simpler sub-objects is a fundamental problem in various disciplines. In image processing, images are segmented while in computational geometry, solid polyhedra are decomposed. In recent years, in computer graphics, polygonal meshes are decomposed into sub-meshes. In this paper we propose a novel hierarchical mesh decomposition algorithm. Our algorithm computes a decomposition into the meaningful components of a given mesh, which generally refers to segmentation at regions of deep concavities. The algorithm also avoids over-segmentation and jaggy boundaries between the components. Finally, we demonstrate the utility of the algorithm in control-skeleton extraction.


    1. BIEDERMAN, I. 1987. Recognition-by-components: A theory of human image understanding. Psychological Review 94, 115–147.Google ScholarCross Ref
    2. BLOOMENTHAL, J., AND LIM, C. 1999. Skeletal methods of shape manipulation. In International Conference on Shape Modeling and Applications, 44–49. Google Scholar
    3. CHAZELLE, B., AND PALIOS, L. 1992. Decomposing the boundary of a nonconvex polyhedron. In SWAT, 364–375. Google Scholar
    4. CHAZELLE, B., AND PALIOS, L. 1994. Decomposition algorithms in geometry. In Algebraic Geometry and its Applications, Springer-Verlag, C. C. Bajaj, Ed., Ed., 419–447.Google Scholar
    5. CHAZELLE, B., DOBKIN, D., SHOURHURA, N., AND TAL, A. 1997. Strategies for polyhedral surface decomposition: An experimental study. Computational Geometry: Theory and Applications 7, 4–5, 327–342. Google ScholarDigital Library
    6. CORMEN, T., LEISERSON, C., RIVEST, R., AND STEIN, C. 2001. Introduction to Algorithms. McGraw-Hill. Google Scholar
    7. DUDA, R., AND HART, P. 1973. Pattern Classification and Scene Analysis. New-York, Wiley.Google Scholar
    8. GAGVANI, N., KENCHAMMANA-HOSEKOTE, D., AND SILVER, D. 1998. Volume animation using the skeleton tree. In IEEE Symposium on Volume Visualization, 47–53. Google Scholar
    9. GARLAND, M., AND HECKBERT, P. 1997. Surface simplification using quadric error metrics. In Proceedings of SIGGRAPH 1997, 209–216. Google ScholarDigital Library
    10. GARLAND, M., WILLMOTT, A., AND HECKBERT, P. 2001. Hierarchical face clustering on polygonal surfaces. In Proceedings of ACM Symposium on Interactive 3D Graphics, 49–58. Google Scholar
    11. GOLDBERG, A., AND TARJAN, R. 1988. A new approach to the maximum flow problem. Journal of the ACM 35, 4, 921–940. Google ScholarDigital Library
    12. GREGORY, A., STATE, A., LIN, M., MANOCHA, D., AND LIVINGSTON, M. 1999. Interactive surface decomposition for polyhedral morphing. The Visual Computer 15, 453–470.Google ScholarDigital Library
    13. KARNI, Z., AND GOTSMAN, C. 2000. Spectral compression of mesh geometry. In Proceedings of SIGGRAPH 2000, ACM SIGGRAPH, 279–286. Google ScholarDigital Library
    14. LAZARUS, F., AND VERROUST, A. 1999. Level set diagrams of polyhedral objects. In ACM Symposium on Solid Modeling and Applications, 130–140. Google Scholar
    15. LEVY, B., PETITJEAN, S., RAY, N., AND MAILLOT, J. 2002. Least squares conformal maps for automatic texture atlas generation. In Proceedings of SIGGRAPH 2002, ACM SIGGRAPH, 362–371. Google ScholarDigital Library
    16. LEWIS, J., CORDNER, M., AND FONG, N. 2000. Pose space deformations: A unified approach to shape. In Proceedings of SIGGRAPH 2000, ACM SIGGRAPH, 165–172. Google Scholar
    17. LI, X., TOON, T., TAN, T., AND HUANG, Z. 2001. Decomposing polygon meshes for interactive applications. In Proceedings of the 2001 symposium on Interactive 3D graphics, 35–42. Google Scholar
    18. MANGAN, A., AND WHITAKER, R. 1999. Partitioning 3D surface meshes using watershed segmentation. IEEE Transactions on Visualization and Computer Graphics 5, 4, 308–321. Google ScholarDigital Library
    19. SHARON, E., BRANDT, A., AND BASRI, R. 2000. Fast multiscale image segmentation. In Proceedings IEEE Conference on Computer Vision and Pattern Recognition, 70–77.Google ScholarCross Ref
    20. SHI, J., AND MALIK, J. 2000. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 22, 8, 888–905. Google ScholarDigital Library
    21. SHINAGAWA, Y., KUNII, T., AND KERGOSIEN, Y. 1991. Surface coding based on morse theory. IEEE Computer Graphics and Applications 11, 5, 66–78. Google ScholarDigital Library
    22. SHLAFMAN, S., TAL, A., AND KATZ, S. 2002. Metamorphosis of polyhedral surfaces using decomposition. In Eurographics 2002, 219–228.Google Scholar
    23. TEICHMANN, M., AND TELLER, S. 1998. Assisted articulation of closed polygonal models. In Conference abstracts and applications: SIGGRAPH, ACM SIGGRAPH, 14–21. Google Scholar
    24. WADE, L., AND PARENT, R. 2002. Automated generation of control skeletons for use in animation. The Visual Computer 18, 2, 97–110.Google ScholarDigital Library
    25. WEBER, J. 2000. Run-Time Skin Deformation. Intel Architecture Labs, www.intel.com.Google Scholar
    26. WU, Z., AND LEAHY, R. 1993. An optinal graph theoretic approach to data clustering: Theory and its application to image segmentation. PAMI 11, 1101–1113. Google ScholarDigital Library
    27. ZOCKLER, M., STALLING, D., AND HEGE, H.-C. 2000. Fast and intuitive generation of geometric shape transitions. The Visual Computer 16, 5, 241–253.Google ScholarCross Ref
    28. ZUCKERBERGER, E., TAL, A., AND SHLAFMAN, S. 2002. Polyhedral surface decomposition with applications. Computers & Graphics 26, 5, 733–743.Google ScholarCross Ref

ACM Digital Library Publication:

Overview Page: