Skip to main content
SpringerLink
Log in

Consistent mesh partitioning and skeletonisation using the shape diameter function

  • Original Article
  • Published:
The Visual Computer Aims and scope Submit manuscript

Abstract

Mesh partitioning and skeletonisation are fundamental for many computer graphics and animation techniques. Because of the close link between an object’s skeleton and its boundary, these two problems are in many cases complementary. Any partitioning of the object can assist in the creation of a skeleton and any segmentation of the skeleton can infer a partitioning of the object. In this paper, we consider these two problems on a wide variety of meshes, and strive to construct partitioning and skeletons which remain consistent across a family of objects, not a single one. Such families can consist of either a single object in multiple poses and resolutions, or multiple objects which have a general common shape. To achieve consistency, we base our algorithms on a volume-based shape-function called the shape-diameter-function (SDF), which remains largely oblivious to pose changes of the same object and maintains similar values in analogue parts of different objects. The SDF is a scalar function defined on the mesh surface; however, it expresses a measure of the diameter of the object’s volume in the neighborhood of each point on the surface. Using the SDF we are able to process and manipulate families of objects which contain similarities using a simple and consistent algorithm: consistently partitioning and creating skeletons among multiple meshes.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Amenta, N., Choi, S., Kolluri, R.: The power crust, unions of balls, and the medial axis transform. Comput. Geom. Theory Appl. 19(2,3), 127–153 (2001)

    MATH  MathSciNet  Google Scholar 

  2. Attene, M., Biasotti, S., Spagnuolo, M.: Shape understanding by contour-driven retiling. Visual Comput. 19(2,3), 127–138 (2003)

    MATH  Google Scholar 

  3. Attene, M., Falcidieno, B., Spagnuolo, M.: Hierarchical mesh segmentation based on fitting primitives. Visual Comput. 22(3), 181–193 (2006)

    Article  Google Scholar 

  4. Choi, H., Choi, S., Moon, H.: Mathematical theory of medial axis transform. Pac. J. Math. 181(1), 57–88 (1997)

    Article  MathSciNet  Google Scholar 

  5. Cohen-Steiner, D., Alliez, P., Desbrun, M.: Variational shape approximation. ACM Trans. Graph. 23(3), 905–914 (2004)

    Article  Google Scholar 

  6. Cox, M., Cox, T.: Multidimensional Scaling. Chapman and Hall, London (1994)

    MATH  Google Scholar 

  7. Dasgupta, S.: Learning mixtures of gaussians. Tech. Rep. UCB/CSD-99-1047, EECS Department, University of California, Berkeley (1999)

  8. Dey, T., Giesen, J., Goswami, S.: Shape segmentation and matching with flow discretization. In: Proceedings of the Workshop on Algorithms and Data Structures (WADS 03). Lect. Notes Comput. Sci., vol. 2748, pp. 25–36. Springer, Berlin/Heidelberg (2003)

  9. Dey, T.K., Zhao, W.: Approximating the medial axis from the voronoi diagram with a convergence guarantee. In: Algorithms - ESA 2002: 10th Annual European Symposium, pp. 387–398. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  10. Gelfand, N., Guibas, L.J.: Shape segmentation using local slippage analysis. In: SGP’04: Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, pp. 214–223. ACM Press, New York, NY, USA (2004)

    Chapter  Google Scholar 

  11. Hilaga, M., Shinagawa, Y., Kohmura, T., Kunii, T.L.: Topology matching for fully automatic similarity estimation of 3D shapes. In: Proceedings of the 28th Annual Conference on Computer graphics and Interactive Techniques (SIGGRAPH ’01), pp. 203–212. ACM, New York, NY (2001)

    Chapter  Google Scholar 

  12. Katz, S., Leifman, G., Tal, A.: Mesh segmentation using feature point and core extraction. Visual Comput. (Pac. Graph.) 21(8–10), 865–875 (2005)

    Google Scholar 

  13. Katz, S., Tal, A.: Hierarchical mesh decomposition using fuzzy clustering and cuts. ACM Trans. Graph. (Proceedings SIGGRAPH 2003) 22(3), 954–961 (2003)

    Google Scholar 

  14. Kraevoy, V., Julius, D., Sheffer, A.: Shuffler: Modeling with interchangeable parts. Visual Comput. (2007) (to appear)

  15. Lee, I.K.: Curve reconstruction from unorganized points. Comput. Aided Geom. Des. 17(2), 161–177 (2000)

    Article  Google Scholar 

  16. 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, pp. 279–287. IEEE Computer Society, Washington DC (2004)

    Google Scholar 

  17. Levin, D.: The approximation power of moving least-squares. Math. Comput. 67(224), 1517–1531 (1998)

    Article  MATH  Google Scholar 

  18. Lien, J.M., Amato, N.M.: Approximate convex decomposition of polygons. In: SCG ’04: Proceedings of the twentieth annual symposium on Computational geometry, pp. 17–26. ACM Press, New York, NY, USA (2004)

    Chapter  Google Scholar 

  19. Lien, J.M., Amato, N.M.: Simultaneous shape decomposition and skeletonization. Tech. rep., Texas AM University (2005)

    Google Scholar 

  20. Liu, R., Zhang, H.: Segmentation of 3D meshes through spectral clustering. In: The 12th Pacific Conference on Computer Graphics and Applications (PG’04), pp. 298–305. IEEE Computer Society, Seoul (2004)

    Google Scholar 

  21. Mangan, A., Whitaker, R.: Partitioning 3D surface meshes using watershed segmentation. IEEE Trans. Vis. Comput. Graph. 5(4), 308–321 (1999)

    Article  Google Scholar 

  22. Mortara, M., Patanè, G.: Shape-covering for skeleton extraction. Int. J. Shape Modeling 8(2), 139–158 (2002)

    Article  MATH  Google Scholar 

  23. Mortara, M., Patanè, G., Spagnuolo, M., Falcidieno, B., Rossignac, J.: Blowing bubbles for multi-scale analysis and decomposition of triangle meshes. Algorithmica 38(1), 227–248 (2003)

    Article  Google Scholar 

  24. Ni, X., Garland, M., Hart, J.C.: Fair morse functions for extracting the topological structure of a surface mesh. ACM Trans. Graph. 23(3), 613–622 (2004)

    Article  Google Scholar 

  25. 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, pp. 91–97 (2003)

  26. 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, pp. 27–32. IEEE Computer Society, Los Alamitos, CA (2003)

    Google Scholar 

  27. Shamir, A.: Segmentation and shape extraction of 3D boundary meshes. In: State-of-the-Art Report, Proceedings Eurographics 2006, The Eurographics Association (2006)

  28. Shlafman, S., Tal, A., Katz, S.: Metamorphosis of polyhedral surfaces using decomposition. Comput. Graph. Forum 21(3) (2002) (Proceedings Eurographics 2002)

  29. Svensson, S., di Baja, G.S.: Using distance transforms to decompose 3d discrete objects. Image Vis. Comput. 20(8), 529–540 (2002)

    Article  Google Scholar 

  30. Tierny, J., Vandeborre, J.P., Daoudi, M.: 3d Mesh Skeleton Extraction Using Topological and Geometrical Analyses. In: 14th Pacific Conference on Computer Graphics and Applications (Pacific Graphics 2006), pp. 85–94. Taipei, Taiwan (2006) (URL http://www.lifl.fr/∼tierny/pacific06.html)

  31. Tierny, J., Vandeborre, J.P., Daoudi, M.: Topology driven 3D mesh hierarchical segmentation. In: IEEE International Conference on Shape Modeling and Applications (SMI’2007). IEEE, Lyon (2007) (URL http://www.lifl.fr/∼tierny/smi07.html)

  32. Verroust, A., Lazarus, F.: Extracting skeletal curves from 3D scattered data. Visual Comput. 16(1), 15–25 (2000) (URL citeseer.ist.psu.edu/verroust97extracting.html)

    Google Scholar 

  33. Vlassis, N., Likas, A.: A greedy EM algorithm for Gaussian mixture learning. Neural Process. Lett. 15(1), 77–87 (2002) (URL citeseer.ist.psu.edu/article/vlassis00greedy.html)

  34. Wu, F.C., Ma, W.C., Liang, R.H., Chen, B.Y., Ouhyoung, M.: Domain connected graph: the skeleton of a closed 3d shape for animation. Visual Comput. 22(2), 117–135 (2006)

    Article  Google Scholar 

  35. Zabih, R., Kolmogorov, V.: Spatially coherent clustering using graph cuts. cvpr 02, 437–444 (2004) (DOI http://doi.ieeecomputersociety.org/10.1109/CVPR.2004.238)

    Google Scholar 

  36. Zhu, S.C., Yuille, A.L.: Forms: A flexible object recognition and modeling system. Int. J. Comput. Vis. 20(3), 187–212 (1996)

    Article  Google Scholar 

  37. Zuckerberger, E., Tal, A., Shlafman, S.: Polyhedral surface decomposition with applications. Comput. Graph. 26(5), 733–743 (2002)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Tel-Aviv University, Tel-Aviv, Israel

    Lior Shapira & Daniel Cohen-Or

  2. The Interdisciplinary Center, Herzeliya, Israel

    Ariel Shamir

Authors
  1. Lior Shapira
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ariel Shamir
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Daniel Cohen-Or
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lior Shapira.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Shapira, L., Shamir, A. & Cohen-Or, D. Consistent mesh partitioning and skeletonisation using the shape diameter function. Visual Comput 24, 249–259 (2008). https://doi.org/10.1007/s00371-007-0197-5

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00371-007-0197-5

Keywords

Search

Navigation