R-symmetry for triangle meshes: detection and applications

Abstract

In this thesis, we investigate a certain type of local similarities between geometric shapes. We analyze the surface of a shape and find all points that are contained inside identical, spherical neighborhoods of a radius r. This allows us to decompose surfaces into canonical sets of building blocks, which we call microtiles. We show that the microtiles of a given object can be used to describe a complete family of related shapes. Each of these shapes is locally similar to the original, meaning that it contains identical r-neighborhoods, but can have completely different global structure. This allows for using r-microtiling for inverse modeling of shape variations and we develop a method for shape decomposi tion into rigid, 3D manufacturable building blocks that can be used to physically assemble shape collections. We obtain a small set of constructor pieces that are well suited for manufacturing and assembly by a novel method for tiling grammar simplification: We consider the connection between microtiles and noncontext-free tiling grammars and optimize a graph-based representation, finding a good balance between expressiveness, simplicity and ease of assembly. By changing the objective function, we can re-purpose the grammar simplification method for mesh compression. The microtiles of a model encode its geometrically redundant parts, which can be used for creating shape representations with minimal memory footprints. Altogether, with this work we attempt to give insights into how rigid partial symmetries can be efficiently computed and used in the context of inverse modeling of shape families, shape understanding, and compression.

Diese Dissertation beschäftigt sich mit den Eigenschaften von Symmetrieabbildungen von geometrischen Flächen. Wir betrachten r-symmetrische Punkte, die mittels Euklidische Transformationen aufeinander abgebildet werden können, sodass alle Nachbarpunkte in einer sphärischen Umgebung mit Radius r identisch bleiben. Wir zerlegen 3D-Modellen in Bausteine, die wir Microtiles nennen. Alle Punkte im selben Baustein haben die gleichen Symmetrietransformationen. Wir zeigen, dass sich aus den Microtiles eines 3D-Objektes einen wohl-definierten Raum ähnlicher Objekten konstruieren lässt. Jedes neues Objekt ist punkweise gleich mit dem ursprnglichen Modell, kann aber eine beliebige globale Struktur haben. Diese Eigenschaft ermöglicht das automatische Zerlegen von Geometrieobjekten in herstellbare Bausteine, die Objektvariationen bilden können. Wir stellen ein Optimierungsverfahren vor, wodurch wir verschiedene Eigenschaften von den Bausteinen beeinflussen können. Wir betrachten die Microtiles als eine formale Grammatik und transformieren einen darauf basierenden Graphen. Das ermöglicht uns anwendungspezifische Eigenschaften der Bausteine wie Variationsmenge, Einfachheit, Zusammensetzbarkeit zu verbessern. Dasselbe Optimierungsverfahren findet zusätzliche Anwendungen im Bereich der Datenkomprimierung. Da die Microtiles Redundanzen in der Geometrie darstellen,ist es möglich aus den Bausteinen eine Flächendarstellung zu berechnen, die möglichst wenig Speicherplatz benötigt. Im ganzen, gewinnen wir mit dieser Arbeit einen Einblick in die Zusammenhnge zwischen Symmetrien, der Analyse und Synthese von 3D-Objekten, und deren Komprimierung.