Hierarchical mesh decomposition using fuzzy clustering and cuts
The DOI matches its Crossref record; 24 of the 24 references it cites were found in a registry or an index.
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Normalized cuts and image segmentation
Shi, J., & Malik, J. (2000) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.868688 · Cited by 15,502
(1973) · CERN Document Server (European Organization for Nuclear Research) · Cited by 12,895
Grossman, P. (2009) · Discrete Mathematics for Computing · doi:10.1007/978-0-230-37405-8_1 · Cited by 8,834
Recognition-by-components: A theory of human image understanding.
Biederman, I. (1987) · Psychological Review · doi:10.1037/0033-295x.94.2.115 · Cited by 5,621 · cited 1×
“The boundaries between the meaningful components pass at regions of deep concavities [Biederman 1987], as illustrated in Figure 1, where the dino-pet is decomposed into its organs.”
BackgroundSurface simplification using quadric error metrics
Garland, M., & Heckbert, P. S. (1997) · Proceedings of the 24th annual conference on Computer graphics and interactive techniques - SIGGRAPH '97 · doi:10.1145/258734.258849 · Cited by 3,412
A new approach to the maximum-flow problem
Goldberg, A. V., & Tarjan, R. E. (1988) · Journal of the ACM · doi:10.1145/48014.61051 · Cited by 1,882
Wu, Z., & Leahy, R. (1993) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.244673 · Cited by 1,137
Least squares conformal maps for automatic texture atlas generation
Lévy, B., Petitjean, S., Ray, N., & Maillot, J. (2002) · Proceedings of the 29th annual conference on Computer graphics and interactive techniques · doi:10.1145/566570.566590 · Cited by 943
Pose space deformation: a unified approach to shape interpolation and skeleton-driven deformation
Lewis, J. P., Cordner, M., & Fong, N. (2000) · Proceedings of the 27th annual conference on Computer graphics and interactive techniques - SIGGRAPH '00 · doi:10.1145/344779.344862 · Cited by 853
Spectral compression of mesh geometry
Karni, Z., & Gotsman, C. (2000) · Proceedings of the 27th annual conference on Computer graphics and interactive techniques - SIGGRAPH '00 · doi:10.1145/344779.344924 · Cited by 652
Cited by
Lee, C. H., Varshney, A., & Jacobs, D. W. (2005) · ACM Transactions on Graphics · doi:10.1145/1073204.1073244 · Cited by 667
A benchmark for 3D mesh segmentation
Chen, X., Golovinskiy, A., & Funkhouser, T. (2009) · ACM Transactions on Graphics · doi:10.1145/1531326.1531379 · Cited by 654
Variational shape approximation
Cohen-Steiner, D., Alliez, P., & Desbrun, M. (2004) · ACM Transactions on Graphics · doi:10.1145/1015706.1015817 · Cited by 642
A survey on Mesh Segmentation Techniques
Shamir, A. (2008) · Computer Graphics Forum · doi:10.1111/j.1467-8659.2007.01103.x · Cited by 593
Consistent mesh partitioning and skeletonisation using the shape diameter function
Shapira, L., Shamir, A., & Cohen-Or, D. (2008) · The Visual Computer · doi:10.1007/s00371-007-0197-5 · Cited by 542
Skeleton extraction by mesh contraction
Au, O. K.-C., Tai, C.-L., Chu, H.-K., Cohen-Or, D., & Lee, T.-Y. (2008) · ACM Transactions on Graphics · doi:10.1145/1360612.1360643 · Cited by 521
Funkhouser, T., Kazhdan, M., Shilane, P., Min, P., Kiefer, W., Tal, A., Rusinkiewicz, S., & Dobkin, D. (2004) · ACM Transactions on Graphics · doi:10.1145/1015706.1015775 · Cited by 506
Self-citationAutomatic rigging and animation of 3D characters
Baran, I., & Popović, J. (2007) · ACM SIGGRAPH 2007 papers · doi:10.1145/1275808.1276467 · Cited by 495
Fast exact and approximate geodesics on meshes
Surazhsky, V., Surazhsky, T., Kirsanov, D., Gortler, S. J., & Hoppe, H. (2005) · ACM Transactions on Graphics · doi:10.1145/1073204.1073228 · Cited by 502
Curve-Skeleton Properties, Applications, and Algorithms
Cornea, N. D., Silver, D., & Min, P. (2007) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2007.1002 · Cited by 484
Learning 3D mesh segmentation and labeling
Kalogerakis, E., Hertzmann, A., & Singh, K. (2010) · ACM Transactions on Graphics · doi:10.1145/1778765.1778839 · Cited by 469
PointGrid: A Deep Network for 3D Shape Understanding
Le, T., & Duan, Y. (2018) · 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2018.00959 · Cited by 432
Mesh segmentation using feature point and core extraction
Katz, S., Leifman, G., & Tal, A. (2005) · The Visual Computer · doi:10.1007/s00371-005-0344-9 · Cited by 375
Self-citationA planar-reflective symmetry transform for 3D shapes
Podolak, J., Shilane, P., Golovinskiy, A., Rusinkiewicz, S., & Funkhouser, T. (2006) · ACM Transactions on Graphics · doi:10.1145/1141911.1141923 · Cited by 297
Min-cut based segmentation of point clouds
Golovinskiy, A., & Funk, T. (2009) · 2009 IEEE 12th International Conference on Computer Vision Workshops, ICCV Workshops · doi:10.1109/iccvw.2009.5457721 · Cited by 293
Feature-based surface parameterization and texture mapping
Zhang, E., Mischaikow, K., & Turk, G. (2005) · ACM Transactions on Graphics · doi:10.1145/1037957.1037958 · Cited by 288
L 1 -medial skeleton of point cloud
Huang, H., Wu, S., Cohen-Or, D., Gong, M., Zhang, H., Li, G., & Chen, B. (2013) · ACM Transactions on Graphics · doi:10.1145/2461912.2461913 · Cited by 278
3D Skeletons: A State‐of‐the‐Art Report
Tagliasacchi, A., Delame, T., Spagnuolo, M., Amenta, N., & Telea, A. (2016) · Computer Graphics Forum · doi:10.1111/cgf.12865 · Cited by 264
Curve skeleton extraction from incomplete point cloud
Tagliasacchi, A., Zhang, H., & Cohen-Or, D. (2009) · ACM Transactions on Graphics · doi:10.1145/1531326.1531377 · Cited by 249
Randomized cuts for 3D mesh analysis
Golovinskiy, A., & Funkhouser, T. (2008) · ACM Transactions on Graphics · doi:10.1145/1409060.1409098 · Cited by 226
A new CAD mesh segmentation method, based on curvature tensor analysis
Lavoué, G., Dupont, F., & Baskurt, A. (2005) · Computer-Aided Design · doi:10.1016/j.cad.2004.09.001 · Cited by 210
“Only Katz et al. [15] specifically handle the boundaries by using a fuzzy decomposition.”
MethodIso-charts: stretch-driven mesh parameterization using spectral analysis
Zhou, K., Synder, J., Guo, B., & Shum, H.-Y. (2004) · Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing · doi:10.1145/1057432.1057439 · Cited by 177
A 3D Shape Retrieval Framework Supporting Multimodal Queries
Daras, P., & Axenopoulos, A. (2010) · International Journal of Computer Vision · doi:10.1007/s11263-009-0277-2 · Cited by 171
“A mesh decomposition method, similar to Katz and Tal (2003), is presented in Tal and Zuckerberger (2006).”
MethodInfluentialReuter, M. (2010) · International Journal of Computer Vision · doi:10.1007/s11263-009-0278-1 · Cited by 161
“Quite a few segmentation methods, e.g. [8,9], are hierarchical (as is the one in this paper).”
(2007) · doi:10.5555/1281991.1282013 · Cited by 88
Learning skeletons for shape and pose
Hasler, N., Thormählen, T., Rosenhahn, B., & Seidel, H.-P. (2010) · Proceedings of the 2010 ACM SIGGRAPH symposium on Interactive 3D Graphics and Games · doi:10.1145/1730804.1730809 · Cited by 66
RigNet: Neural Rigging for Articulated Characters
Xu, Z., Zhou, Y., Kalogerakis, E., Landreth, C., & Singh, K. (2020) · arXiv · doi:10.48550/arxiv.2005.00559 · Cited by 13
Widget based automated rigging of bipedal character with custom manipulators
Bhatti, Z., & Shah, A. (2012) · Proceedings of the 11th ACM SIGGRAPH International Conference on Virtual-Reality Continuum and its Applications in Industry · doi:10.1145/2407516.2407593 · Cited by 8
Bhati, Z., Shah, A., Waqas, A., & Mahmood, N. (2015) · International Journal of Computer Graphics & Animation · doi:10.5121/ijcga.2015.5104 · Cited by 4
“Whereas, Katz and Tal [7] suggested extraction of skeleton as an application through surface partitioning algorithm.”
MethodSkin Tokens: A Learned Compact Representation for Unified Autoregressive Rigging
Zhang, J.-P., Pu, C.-F., Guo, M.-H., Cao, Y.-P., & Hu, S.-M. (2026) · arXiv · doi:10.48550/arxiv.2602.04805
Metadata
- Authors
- Katz, S., & Tal, A.
- Venue
- ACM SIGGRAPH 2003 Papers
- Publisher
- ACM
- Published
- 2003-07
- Pages
- 954-961
- OpenAlex
- W2160994953
- Cited by
- 577
- References
- 24
- FWCI
- 20.10
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.