PhD Thesis

Faniry H. Razafindrazaka
Quad Layout Generation and Symmetric Tilings of Closed Surfaces. PhD Thesis, Freie Universität Berlin, 2016

This thesis concerns two fundamental concepts in surface topology. The first part proposes a solution of the problem of generating an all quadrilateral patch layout on a given surface. We approach the problem from a combinatorial graph optimization point of view. Mainly, finding a nice quad layout of a given surface is equivalent to solving a minimum weight perfect matching problem with additional quad guarantee constraints. The results are of high quality in terms of coarseness and alignment to important features of the geometry which can be used for wide range of applications such as hierarchical subdivision or high order surface fitting. The second part suggests an algorithm to symmetrically generate high genus surfaces suitable for space models of regular maps. It is based on a novel identification in hyperbolic space to derive directly the tubular neighborhood of the edge of a tiling directly the the hyperbolic representation followed by a spring relaxation procedure with intersection-free guarantee. We succeed to produce new embeddings of regular maps ranging from genus 5 to 85.

[Dissertation online]


Christoph von Tycowicz
Concepts and Algorithms for the Deformation, Analysis, and Compression of Digital Shapes. PhD Thesis, Freie Universität Berlin, 2014

This thesis concerns model reduction techniques for the efficient numerical treatment of physical systems governing the deformation behavior of geometrically complex shapes. We present new strategies for the construction of simplified, low-dimensional models that capture the main features of the original complex system and are suitable for use in interactive computer graphics applications.
To demonstrate the effectiveness of the new techniques we propose frameworks for real-time simulation and interactive deformation-based modeling of elastic solids and shells and compare them to alternative approaches. In addition, we investigate differential operators that are derived from the physical models and hence can serve as alternatives to the Laplace-Beltrami operator for applications in modal shape analysis. Furthermore, this thesis addresses the compression of digital shapes. In particular, we present a lossless compression scheme that is adapted to the special characteristics of adaptively refined, hierarchical meshes.

[Dissertation online]


Stefan W. von Deylen
Numerical Approximation in Riemannian Manifolds by Karcher Means. PhD Thesis, Freie Universität Berlin, 2013

This dissertation treats questions about the definition of “simplices” inside Riemannian manifolds, the comparison between those simplices and Euclidean ones, as well as Galerkin methods for variational problems on manifolds. During the last three years, the “Riemannian centre of mass” technique introduced by Karcher (1977) has been successfully employed to define the notion of a simplex in a Riemannian manifold M of non-constant curvature by Rustamov (2010), Sander (2012) and others. This approach constructs, for given vertices p_i in M, a uniquely defined “barycentric map” x from the standard simplex Delta into the manifold, and calls x(Delta) the “Karcher simplex” with vertices pi. However, the question whether x is bijective and hence actually induces “barycentric coordinates” on x(Delta) remained open for most cases. We show that under “shape regularity” conditions similar to the Euclidean setting, the distortion induced by x is of the same order as for normal coordinates: dx is almost an isometry (of course, this can only work if Delta is endowed with an appropriately-chosen Euclidean metric), and "nabla dx" almost vanishes. The estimate on dx could have already been deduced from the work of Jost and Karcher (1982), but it is the combination with the "nabla dx" estimate which paves the ground for applications of Galerkin finite element techniques. For example, the construction can be employed to triangulate M and solve problems like the Poisson problem or the Hodge decomposition on the piecewise flat simplicial manifold instead of M. This leads to analogues of the classical estimates by Dziuk (1988) and subsequent authors in the field of surface pde’s (we only mention Hildebrandt et al. 2006 and Holst and Stern 2012 at this point), but as no embedding is needed in our approach, the range of the surface finite element method is extended to abstract Riemannian manifolds without modification of the computational scheme. Second, one can approximate submanifolds S inside spaces M unequal to R^m (for example, minimal submanifolds in hyperbolic space), for which the classical “normal height map” or “orthogonal projection” construction from the above-mentioned literature directly carries over, and the error term generated by the curvature of M is dominated by the well-known error from the principal curvatures of S. Apart from classical conforming Galerkin methods, there are other discretisation ideas, e. g. the “discrete exterior calculus” (DEC, see Hirani 2003) in which variational problems such as the Poisson problem or the Hodge decomposition can be solved without any reference to some smooth problem. Convergence proofs are less developed in this area, mainly because albeit there are interpolation operators from discrete k-forms to L^2 Omega^k, these interpolations do not commute with the (differing) notions of exterior derivative on both sides. We re-interpret DEC as non-conforming Galerkin schemes.

[Dissertation online]


Felix Kälberer
Low Distortion Surface Parameterization. PhD Thesis, Freie Universität Berlin, 2013

Die vorliegende Arbeit befasst sich mit der Parametrisierung simplizialer Flächen. Darunter versteht man das Erzeugen einer Abbildung zwischen einer Fläche und der euklidische Ebene, um durch diese Korrespondenz die vorhandene Struktur der Ebene auf der Fläche nutzbar zu machen. Zum Beispiel besitzt die Ebene eine natürliche Rasterung in Einheitsquadrate, die mithilfe der Parametrisierungsfunktion auf die Fläche übertragen werden kann. Anwendungen hierfür sind zum Beispiel die Neuvernetzung und Texturierung von Flächen, und die Erstellung von Kontrollnetzen zur Generierung von Subdivisions- oder NURBS-Flächen. Parametrisierungsfunktionen haben meist eine Reihe von Gütekriterien zu erfüllen, wichtig ist zum Beispiel geringe Längen- und Winkelverzerrung. Oft ist zusätzlich gefordert, dass die Gradienten der Abbildung mit der Ausrichtung von Flächenmerkmalen -- etwa von scharfen Kanten -- übereinstimmen. Unser QuadCover-Verfahren, das die Grundlage dieser Arbeit bildet, erzeugt automatisch aus einem Tensorfeld von Merkmalsrichtungen eine Parametrisierung. Das Verfahren basiert auf der Grundlage, dass diese mehrdimensionalen Tensorfelder als eindimensionale Vektorfelder auf einer verzweigten Überlagerung der Fläche interpretiert werden können. Auf diese Weise können bekannte Resultate über Vektorfelder, zum Beispiel die Hodge-Zerlegung, angewendet werden. Auf dieser Basis findet QuadCover die Parametrisierung, die einem gegebenen Richtungsfeld am nächsten kommt. Für Parametrisierungen höchster Güte muss zusätzlich die Längen- und Winkelverzerrung minimiert werden. Hierfür ist die Anzahl und Position von Verzweigungspunkten im Richtungsfeld entscheidend. In dieser Arbeit setzen wir an drei unterschiedlichen Punkten an: Erstens, zeigen wir mit einem neuen Verfahren, dass die Verzerrung durch das Verschieben und vor allem durch das Erschaffen von Verzweigungspunkten drastisch minimiert werden kann. Zweitens wird die Verzerrung, die durch die Existenz von Verzweigungspunkten entsteht, durch ein neues Rundungsverfahren deutlich stärker verringert als mit bisherigen Methoden. Der dritte Ansatz stellt die unterschiedlichen Arten von Verzerrung der zuvor genannten Verfahren gegenüber, so dass daraus die optimale Anzahl von Verzweigungspunkten bestimmt werden kann. Die Kombination der Ansätze erlaubt es, auch neue Verfahren hinsichtlich der Verzerrung zu übertreffen.

[Dissertation online]


Christian Schulz
Interactive Spacetime Control of Deformable Objects and Modal Shape Analysis beyond Laplacian. PhD Thesis, Freie Universität Berlin, 2013

In der mathematischen Geometrieverarbeitung nutzt eine Vielzahl moderner und etablierter Methoden die Eigenschaften von Spektren und Eigenvektoren. So wurden unter anderem Verfahren zur Segmentierung, Parametrisierung und Deformation von Oberflächen entwickelt, die das Lösen generalisierter Eigenwertprobleme erfordern. In dieser Arbeit werden zwei Anwendungen vorgestellt, die von energiebasierten Spektren und Eigenfunktionen abhängen. Im Bereich der physikalisch basierten Computeranimation präsentieren wir eine Verallgemeinerung der üblichen Spline Interpolationsmethode von Keyframes. Unsere Verfahren ermöglicht die interaktive Kontrolle über eine Reihe von animationsrelavanten Parametern selbst für komplexe Formen, d.h. unter anderem für diskrete Geometrien die deformierbare Objekte, wie z.B. dünne Schalen oder elastische Körper, beschreiben. Die Interaktivität wird durch eine geeignete Problemreduktion und einer expliziten Darstellung der Wiggly Splines erreicht. Die Reduktion und die Darstellung der Wiggly Splines erfordert das Lösen generalisierter Eigenwertprobleme. Wir demonstrieren die Vielseitigkeit unseres Verfahrens an einer Reihe von Animationen für ein-, zwei- und dreidimensionalen Formen. Im Bereich der Oberflächenanalyse stellen wir eine neue Familie von Operatoren für Funktionen auf Oberflächen vor. Im Gegensatz zum Laplace- Operator besitzen diese Operatoren merkmals-sensitive Spektren und Eigenfunktionen. Wir konstruieren eine Punkt-Signatur, die auf den merkmalssensitiven Spektren und Eigenfunktionen basiert. Wir vergleichen die gefundenen ähnlichen Punkte bzgl. dieser Signatur mit Ergebnissen der Diffusionssignatur, d.h. einer Signatur die aus dem Laplacespektrum und Eigenfunktionen konstruiert wird. Weiterhin zeigen wir, dass das Spektrum eines bestimmten Operators dieser Familie zur Abschätzung des Stabilitätsindexes einer diskreten Fläche konstanter mittlerer Krümmung verwendet werden kann. Abschliessend stellen wir noch eine Methode vor, die eine merkmalssensitive Oberflächenstrukturierung ermöglicht.

[Dissertation online]


Klaus Hildebrandt
Discretization and approximation of the shape operator, the Laplace--Beltrami operator, and the Willmore energy of surfaces. PhD Thesis, Freie Universität Berlin, 2012

Die diskrete Differentialgeometrie ist ein mathematisches Gebiet, in dem diskrete Entsprechungen zu Begriffen und Konzepten der klassischen und modernen Differentialgeometrie glatter Mannigfaltigkeiten konstruiert und analysiert werden. Die Entwicklung in diesem Gebiet wird katalysiert durch die Anwendbarkeit der Resultate in der Computergraphik, der Geometrieverarbeitung, der numerischen Physik und der Architekturgeometrie. In dieser Arbeit befassen wir uns mit polyedrischen Flächen im R3. Im ersten Kapitel fassen wir Resultate zusammen, die die Grundlage dieser Arbeit bilden. Insbesondere betrachten wir die Approximation des metrischen Tensors einer glatten Fläche und die Definition von Funktionenräumen auf polyedrischen Flächen. Im zweiten Kapitel beschäftigt uns die Frage, wie sich Krümmungen polyedrischer Flächen beschreiben lassen. In der klassischen Differentialgeometrie glatter Flächen wird dafür die Weingartenabbildung verwendet. Da polyedrische Flächen im R3 nur Lipschitz--Untermannigfaltigkeiten sind, lässt sich die klassische Definition der Krümmungen nicht anwenden. Wir führen daher eine verallgemeinerte Weingartenabbildung ein, die ein vektorwertiges Funktional auf einem Sobolevraum schwach differenzierbarer Vektorfelder ist und sich rigoros auf polyedrischen Flächen definieren lässt. Zur Rechtfertigung des Konzepts zeigen wir, wie die verallgemeinerte Weingartenabbildung einer polyedrischen Fläche benutzt werden kann, um die klassische Weingartenabbildung einer glatten Fläche zu approximieren. Im dritten Kapitel beschäftigen wir uns mit diskreten Laplace--Beltrami-- Operatoren polyedrischer Flächen. Wir zeigen, wie die starke (oder klassische) Form des Laplace--Beltrami--Operators konsistent diskretisiert werden kann. Darüber hinaus betrachten wir die Willmore--Energie, ein wichtiges geometrisches Funktional, und führen eine konsistente Diskretisierung der Willmore-- Energie auf polyedrischen Flächen ein. Im vierten Kapitel entwickeln wir ein Verfahren zur Glättung verrauschter Flächen. Die Besonderheit dieses Verfahrens ist, dass die maximale Abweichung jedes Punktes von seiner gemessenen Position beschränkt werden kann.

[Dissertation online]


Matthias Nieser
Parameterization and Tiling of Polyhedral Surfaces. PhD Thesis, Freie Universität Berlin, 2012

Die vorgelegte Arbeit beschäftigt sich mit dem Problem der Parametrisierung von simplizialen Flächen, d.h. deren Abbildung in die Ebene. Dabei sollen sich die Parameterlinien an vorgegebenen Richtungsfeldern orientieren, häufig den Hauptkrümmungsrichtungen der Fläche. Richtungsfelder sind mehrwertige Funktionen. In dieser Arbeit wird die Äquivalenz zu einem (ein-wertigen) Vektorfeld auf einer Riemannschen Fläche gezeigt und damit die theoretische Grundlage für das QuadCover-Verfahren gelegt. QuadCover generiert automatisch globale Parametrisierungen von beliebigen zweidimensionalen polyedrischen Mannigfaltigkeiten. Das resultierende Gitter aus Parameterlinien ist global stetig und erlaubt eine Neuvernetzung der Fläche in ein hochqualitatives Netz aus reinen Vierecken, Dreiecken oder Sechsecken. Eine weitere Anwendung von QuadCover ist das Texturieren von Oberflächen. Diese kann mit beliebigen kachelbaren Mustern überzogen werden. Dabei muss die Parametrisierung mit der Rotationssymmetrie des Musters kompatibel sein. In der Arbeit wird gezeigt, wie mithilfe von QuadCover eine Fläche mit Vierecks-, Sechsecks-, Dreiecks- oder Streifenmuster gekachelt werden kann. Ein Benutzer hat häufig spezielle Vorstellungen an eine gute Parametrisierung, so dass es notwendig ist, dass der Benutzer in den Parametrisierungsprozess eingreifen kann. QuadCover ermöglicht das manuelle Platzieren und Verschieben von Singularitäten auf der Fläche. Desweiteren können Kurven auf der Fläche vorgegeben werden, die geometrische Nebenbedingungen definieren, d.h. die Parametrisierung richtet sich exakt an der gegebenen Kurve aus. Ausserdem kann durch Vorgabe von kombinatorischen Nebenbedingungen Ein uss auf die Netztopologie genommen werden.

[Dissertation online]