Pairwise matching of 3D fragments using cluster trees

We propose a novel and efficient surface matching approach for reassembling broken solids as well as for matching assembly components using cluster trees of oriented points. The method rapidly scans through the space of all possible contact poses of the fragments to be ( re) assembled using a tree search strategy, which neither relies on any surface features nor requires an initial solution. The new method first decomposes each point set into a binary tree structure using a hierarchical clustering algorithm. Subsequently the fragments are matched pairwise by descending the cluster trees simultaneously in a depth-first fashion. In contrast to the reassemblage of pottery and thin walled artifacts, this paper addresses the problem of matching broken 3D solids on the basis of their 2.5D fracture surfaces, which are assumed to be reasonable large. Our proposed contact area maximization is a powerful common basis for most surface matching tasks, which can be adapted to numerous special applications. The suggested approach is very robust and offers an outstanding efficiency.