Hierarchical mesh segmentation based on fitting primitives

By Marco Attene, Bianca Falcidieno, Michela Spagnuolo. The Visual Computer, 2006

490 citations recorded by the source corpus.

In this paper, we describe a hierarchical face clustering algorithm for triangle meshes based on fitting primitives belonging to an arbitrary set. The method proposed is completely automatic, and generates a binary tree of clusters, each of which is fitted by one of the primitives employed. Initially, each triangle represents a single cluster; at every iteration, all the pairs of adjacent clusters are considered, and the one that can be better approximated by one of the primitives forms a new single cluster. The approximation error is evaluated using the same metric for all the primitives, so that it makes sense to choose which is the most suitable primitive to approximate the set of triangles in a cluster.Based on this approach, we have implemented a prototype that uses planes, spheres and cylinders, and have experimented that for meshes made of 100 K faces, the whole binary tree of clusters can be built in about 8 s on a standard PC.The framework described here has natural application in reverse engineering processes, but it has also been tested for surface denoising, feature recovery and character skinning.

Subfields: Computational Mechanics, Computer Graphics and Computer-Aided Design, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/de196571268cc2ecaf84446bf3633448c7b668d9

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Graphics and Computer-Aided Design

In Computer Vision and Pattern Recognition

Citations in the corpus

Scene Understanding by Reasoning Stability and Safety (2015, methodology): “For work in 3D geometric reasoning, Attene et al. (2006) extracts 3D geometric primitives (planes or cylinders) from a 3D mesh.”
Contextual Part Analogies in 3D Objects (2010, methodology): “Nevertheless, other part-type partitioning methods such as Attene et al. (2006b), Katz and Tal (2003) could also be used in the first stage of our algorithm.”
Consistent mesh partitioning and skeletonisation using the shape diameter function (2008, methodology): “These attributes include curvature and geodesic distances [13, 16, 21, 25, 26, 37], dihedral angles [28], planarity and normal direction [3, 5], slippage [10] etc.”
The 3D Hough Transform for plane detection in point clouds: A review and a new accumulator design (2011, methodology): “Keywords Hough Transform, 3D laser scans, plane detection, indoor mapping”
Beyond Point Clouds: Scene Understanding by Reasoning Geometry and Physics (2013, background): “[1] extracts 3D geometric primitives (planes or cylinders) from 3D mesh.”
Supervised learning of hidden and non-hidden 0-order affordances and detection in real scenes (2012, background): “The triangle faces of the convex hull can be grouped in planar faces by performing a hierarchical clustering [15].”
PointGrid: A Deep Network for 3D Shape Understanding (2018, methodology): “k-NN, random forest, SVM [14], JointBoost classifier [23], correspondence analysis [56, 62]) or employ some local and greedy methods such as region growing [52, 20], hierarchical clustering [3, 11, 24], spectral clustering [46], k-means [60], normalized cut [13], random walk [29] and heat walk [5].”
Mesh Segmentation - A Comparative Study (2006, methodology): “As described in [2], the hierarchical clustering may be actually used to remove the noise by snapping the vertex positions onto the corresponding fitting primitive(s).”