Superfacets-2D

The Superfacets-2D is a C++ tool for segmenting the boundary of triangulated 3D shapes into patches by extending the idea of superpixel to triangle meshes. The tool computes oversegmentations of triangle meshes based on a k-means style approach using shortest-path distances over the face graph of the mesh. Its algorithm can be subdivided into three high-level steps: 1) initialization, 2) update of segment centers, and 3) classification of triangles, where steps 2) and 3) are alternately repeated until convergence. By using a bounded expansion strategy in the reclassification step, our approach obtains a log-linear complexity, enabling the segmentation of large meshes (with several million triangles) where applying normalized cuts or other such cut-based approaches would be intractable.
The source code and additional information can be found on GitHub.
Reference: Fast and Scalable Mesh Superfacets by Patricio Simari, Giulia Picciau, and Leila De Floriani in Computer Graphics Forum, 33 (7), pages 181-190, 2014.