Parallel mesh clustering (English)

Fast and qualitative clustering of large polygonal surface meshes still remains one of the wast 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 the authors 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 the focus is 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. The authors show how these algorithms can be entirely implemented (giving some non-trivial GPU-specific solutions) and accelerated on GPU. The authors demonstrate both approaches applying them to Centroidal Voronoi Diagram (CVD) based clustering. For boundary-based mesh clustering the authors achieved speed up factors of 10 to 18. The paper is organized as follows: After discussing related work (section2), the Boundary-based Mesh Clustering concept is presented (section 3). Section 4 presents the Parallel Multilevel Mesh Clustering approach. In section 5 all GPU-based implementation details for proposed concepts arc described. Sections 7 and 8 present results and some final conclusions.