Publikation
Microtiles: Extracting Building Blocks from Correspondences
Philipp Slusallek; Hans-Peter Seidel; Leonidas Guibas; Michael Wand; Martin Bokeloh; Javor Kalojanov
In: Eitan Grinspun; Niloy Mitra (Hrsg.). Computer Graphics Forum, Vol. 31, Pages 1597-1606, The Eurographics Association and Blackwell Publishing Ltd. 2012.
Zusammenfassung
In this paper, we develop a theoretical framework for characterizing shapes by building blocks. We address two
questions: First, how do shape correspondences induce building blocks? For this, we introduce a new representation
for structuring partial symmetries (partial self-correspondences), which we call “microtiles”. Starting from
input correspondences that form point-wise equivalence relations, microtiles are obtained by grouping connected
components of points that share the same set of symmetry transformations. The decomposition is unique, requires
no parameters beyond the input correspondences, and encodes the partial symmetries of all subsets of the input.
The second question is: What is the class of shapes that can be assembled from these building blocks? Here, we
specifically consider r-similarity as correspondence model, i.e., matching of local r-neighborhoods. Our main result
is that the microtiles of the partial r-symmetries of an object S can build all objects that are (r+e)-similar to
S for any e>0. Again, the construction is unique. Furthermore, we give necessary conditions for a set of assembly
rules for the pairwise connection of tiles. We describe a practical algorithm for computing microtile decompositions
under rigid motions, a corresponding prototype implementation, and conduct a number of experiments to
visualize the structural properties in practice.