Parallel Mesh Clustering

Abstract

Fast and qualitative clustering of large polygonal surface meshes still remains one of the most demanding fields in mesh processing. Because existing clustering algorithms are very time-consuming, the use of parallel hardware, i.e. the graphics processing unit (GPU), is a reasonable and crucial task in this domain. However, due to the sequential nature of most of these algorithms this is hard to be achieved. In this paper we address the parallel reformulation of the existing approaches and show a suitable GPU implementation for variational or hierarchical parallel mesh clustering. A boundary-based mesh clustering framework is proposed as a new clustering concept which provides all necessary ingredients for parallel mesh clustering. Here we focus on a specific subtype of the variational clustering algorithm which does not restrict the applicability of the approach as such but reveals much better performance characteristics. A parallel multilevel (ML) mesh clustering, for which several dual edges are collapsed in each step, is proposed as an option to the classical ML clustering, where only one dual edge collapse is applied in each step. We show how these algorithms can be entirely implemented (giving some non-trivial GPU-specific solutions) and accelerated on GPU. We demonstrate both approaches applying them to Centroidal Voronoi Diagram (CVD) based clustering. For boundary-based mesh clustering we achieved speed up factors of 10 to 18.