Hierarchical Mesh Decomposition using Fuzzy Clustering and Cuts

Sagi Katz, Ayellet Tal

ACM Transactions on Graphics (TOG)

Volume 22, Number 3, Pages 954-961, 2003


Motivation

Decomposing a mesh into smaller pieces is helpful in many applications such as morphing, compression, simplification, 3D shape retrieval, collision detection and texture mapping. In general, decomposing a shape into appropriate simpler pieces is very useful in many areas of computer graphics.

Goal of This Research

The authors wish to design a mesh segmentation algorithm that is hierarchical, handles orientable meshes even if they contain holes, and avoids over-segmentation and jagged boundaries.

Goal of This Paper

The authors present a mesh decomposition algorithm that focuses on segmenting at the regions of deep concavities. Then they use this algorithm to compute skeletons of meshes. The segmentation algorithm allows boundaries to be ``fuzzy", i.e. some faces of the mesh are allowed to be part of more than one segment. The algorithm consists of four general stages:
  1. Assign a distance to every pair of faces in the mesh
  2. Compute an initial segmentation and for each face, assign a probability of belonging to each segment
  3. Refine the probability values using an iterative clustering scheme to compute a fuzzy decomposition
  4. Transform the fuzzy decomposition into a final decomposition by computing exact boundaries between the segments

Related Work

Results

The segmentation algorithm presented in this paper is able to extract the natural features in a variety of shapes in a hierarchical fashion. The boundaries conform to the shape fairly well. However the algorithm can be improved in many ways, for instance by using other distance functions and capacity functions, and other attributes such as color and texture can be added to the algorithm. The algorithm is also flexible for computing and animating the control skeleton of a mesh or sequence of meshes.

As expected, this paper's segmentation algorithm appears to perform best on meshes containing distinct parts, each of which is separated from the rest of the mesh by sharp changes in curvature, such as the legs of the animals in the paper. The segmentation seems less natural and less accurate for parts of a mesh that do not have very sharp concavity.

Bibliography


ctj