More Web Proxy on the site http://driver.im/

Article

Hierarchical mesh decomposition using fuzzy clustering and cuts

Authors:

Ayellet TalAuthors Info & Claims

SIGGRAPH '03: ACM SIGGRAPH 2003 Papers

Pages 954 - 961

https://doi.org/10.1145/1201775.882369

Published: 01 July 2003 Publication History

Abstract

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.

Supplementary Material

MP4 File (tal_hierarchicicalmesh.mp4)

Download
46.76 MB

References

[1]

BIEDERMAN, I. 1987. Recognition-by-components: A theory of human image understanding. Psychological Review 94, 115--147.

[2]

BLOOMENTHAL, J., AND LIM, C. 1999. Skeletal methods of shape manipulation. In International Conference on Shape Modeling and Applications, 44--49.

Digital Library

[3]

CHAZELLE, B., AND PALIOS, L. 1992. Decomposing the boundary of a nonconvex polyhedron. In SWAT, 364--375.

Digital Library

[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.

[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.

Digital Library

[6]

CORMEN, T., LEISERSON, C., RIVEST, R., AND STEIN, C. 2001. Introduction to Algorithms. McGraw-Hill.

[7]

DUDA, R., AND HART, P. 1973. Pattern Classification and Scene Analysis. New-York, Wiley.

[8]

GAGVANI, N., KENCHAMMANA-HOSEKOTE, D., AND SILVER, D. 1998. Volume animation using the skeleton tree. In IEEE Symposium on Volume Visualization, 47--53.

Digital Library

[9]

GARLAND, M., AND HECKBERT, P. 1997. Surface simplification using quadric error metrics. In Proceedings of SIGGRAPH 1997, 209--216.

Digital 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.

Digital Library

[11]

GOLDBERG, A., AND TARJAN, R. 1988. A new approach to the maximum flow problem. Journal of the ACM 35, 4, 921--940.

Digital 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.

Digital Library

[13]

KARNI, Z., AND GOTSMAN, C. 2000. Spectral compression of mesh geometry. In Proceedings of SIGGRAPH 2000, ACM SIGGRAPH, 279--286.

Digital Library

[14]

LAZARUS, F., AND VERROUST, A. 1999. Level set diagrams of polyhedral objects. In ACM Symposium on Solid Modeling and Applications, 130--140.

Digital Library

[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.

Digital 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.

Digital Library

[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.

Digital Library

[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.

Digital 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.

[20]

SHI, J., AND MALIK, J. 2000. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 22, 8, 888--905.

Digital 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.

Digital Library

[22]

SHLAFMAN, S., TAL, A., AND KATZ, S. 2002. Metamorphosis of polyhedral surfaces using decomposition. In Eurographics 2002, 219--228.

[23]

TEICHMANN, M., AND TELLER, S. 1998. Assisted articulation of closed polygonal models. In Conference abstracts and applications: SIGGRAPH, ACM SIGGRAPH, 14--21.

Digital Library

[24]

WADE, L., AND PARENT, R. 2002. Automated generation of control skeletons for use in animation. The Visual Computer 18, 2, 97--110.

Digital Library

[25]

WEBER, J. 2000. Run-Time Skin Deformation. Intel Architecture Labs, www.intel.com.

[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.

Digital 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.

[28]

ZUCKERBERGER, E., TAL, A., AND SHLAFMAN, S. 2002. Polyhedral surface decomposition with applications. Computers & Graphics 26, 5, 733--743.

Cited By

Wang MMa L(2024)UV Map Generation on Triangular MeshEncyclopedia of Computer Graphics and Games10.1007/978-3-031-23161-2_98(1960-1965)Online publication date: 5-Jan-2024
Lin WHuang Q(2023)Automated deviation-aware landmark selection for freeform product accuracy qualification in 3D printingIISE Transactions10.1080/24725854.2023.228060656:12(1321-1330)Online publication date: 20-Dec-2023
(2022)Heterogeneous Spatial DataundefinedOnline publication date: 9-Apr-2022
Show More Cited By

Recommendations

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, ...
Template-based quadrilateral mesh generation from imaging data
Special Issue on SIBGRAPI 2010

This paper describes a novel template-based meshing approach for generating good quality quadrilateral meshes from 2D digital images. This approach builds upon an existing image-based mesh generation technique called Imeshp, which enables us to create a ...
Template-Based Remeshing for Image Decomposition
SIBGRAPI '10: Proceedings of the 2010 23rd SIBGRAPI Conference on Graphics, Patterns and Images

This paper presents a novel quad-based remeshing scheme, which can be regarded as a replacement for the triangle-based improvement step of an existing image-based mesh generation technique called Imesh. This remeshing scheme makes it possible for the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGGRAPH '03: ACM SIGGRAPH 2003 Papers

July 2003

683 pages

ISBN:1581137095

DOI:10.1145/1201775

Conference Chair:
Alyn P. Rockwood
Colorado School of Mines

Copyright © 2003 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SIGGRAPH03

Sponsor:

SIGGRAPH

SIGGRAPH03: Special Interest Group on Computer Graphics and Interactive Techniques

July 27 - 31, 2003

California, San Diego

Acceptance Rates

SIGGRAPH '03 Paper Acceptance Rate 81 of 424 submissions, 19%;

Overall Acceptance Rate 1,822 of 8,601 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

77
Total Citations
View Citations
2,918
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wang MMa L(2024)UV Map Generation on Triangular MeshEncyclopedia of Computer Graphics and Games10.1007/978-3-031-23161-2_98(1960-1965)Online publication date: 5-Jan-2024
Lin WHuang Q(2023)Automated deviation-aware landmark selection for freeform product accuracy qualification in 3D printingIISE Transactions10.1080/24725854.2023.228060656:12(1321-1330)Online publication date: 20-Dec-2023
(2022)Heterogeneous Spatial DataundefinedOnline publication date: 9-Apr-2022
Chen CQian SFang QXu C(2021)HAPGN: Hierarchical Attentive Pooling Graph Network for Point Cloud SegmentationIEEE Transactions on Multimedia10.1109/TMM.2020.300949923(2335-2346)Online publication date: 1-Jan-2021
Piñones ECascini GCaruso GMorosi F(2021)OVERCOMING AUGMENTED REALITY ADOPTION BARRIERS IN DESIGN: A MIXED PROTOTYPING CONTENT AUTHORING TOOL SUPPORTED BY COMPUTER VISIONProceedings of the Design Society10.1017/pds.2021.4971(2359-2368)Online publication date: 27-Jul-2021
Loizou MAverkiou MKalogerakis E(2020)Learning Part Boundaries from 3D Point CloudsComputer Graphics Forum10.1111/cgf.1407839:5(183-195)Online publication date: 12-Aug-2020
Li RPeng Q(2020)Surface quality improvement and support material reduction in 3D printed shell products based on efficient spectral clusteringThe International Journal of Advanced Manufacturing Technology10.1007/s00170-020-05299-6107:9-10(4273-4286)Online publication date: 25-Apr-2020
Chen JGopi M(2019)Geometry Aware Tori DecompositionComputer Graphics Forum10.1111/cgf.1364138:2(331-341)Online publication date: 7-Jun-2019
Tong WYang XPan MChen F(2019)Spectral Mesh Segmentation via $\ell_0$ Gradient MinimizationIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2018.2882212(1-1)Online publication date: 2019
Yamakawa SShimada K(2018)Feature Edge Extraction Via Angle-Based Edge Collapsing and RecoveryJournal of Computing and Information Science in Engineering10.1115/1.403722718:2Online publication date: 31-Jan-2018
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents