Clustering, as a process of partitioning data elements with similar properties, is an essential task in many application areas. Due to technological advances, the amount as well as the dimensionality of data sets in general is steadily growing. This is especially the case for large polygonal surface meshes since existing 3D geometry acquisition systems can nowadays provide models with up to several million triangles. Thus, fast and high-quality data and polygonal mesh processing becomes more demanding.
To deal with such a huge and diverse heap of clustering problems efficient algorithms are required. At the same time the resulting clustering quality is of highest importance in almost all situations. Thus, identifying an optimal tradeoff between efficiency and quality is crucial in many clustering tasks.
For data clustering tasks in general as well as mesh clustering applications in particular, k-means like techniques or hierarchical methods are used most often. Nonetheless, these approaches are deficient in many respects thus a considerable amount of work is still required to improve them.
This dissertation describes new feasible solutions for efficient and high quality mesh and data clustering. It addresses both the algorithm and the theoretical part of many clustering problems, and new clustering strategies are proposed to overcome inherent problems of the standard algorithms.
With the advent of general-purpose computing on Graphics Processing Units (GPU), which allows the usage of a highly parallel processing power, new tendencies emerged to solve clustering tasks on the GPU.
In this work, a first GPU-based mesh clustering approach, which employs mesh connectivity in the clustering process, is described. The technique is designed as parallel algorithm and it is solely based on the GPU resources. It is free from any global data structure, thus allowing an efficient GPU implementation and a further step in parallelization.
Based on the original concepts a GPU-based data clustering framework is also proposed. The formulation uses the spatial coherence present in the cluster optimization and in the hierarchical merging of clusters to significantly reduce the number of comparisons in both parts. The approach solves the problem of the missing topological information, which is inherent to the general data clustering, by performing a dynamic cluster neighborhood tracking. Compared to classical approaches, our techniques generate results with at least the same clustering quality. Furthermore, our technique proofs to scale very well, currently being limited only by the available amount of graphics memory.