Extracting and Exploiting Structure in Point Clouds for Editing and Interpolation

Abstract

Modern movies and computer games employ rich virtual environments to offer the consumer an immersive experience. Digital models are often easier and more cost-efficient to create than acquiring real-world film footage of exotic locations, items, creatures or plants. With advances in range scanning technology, acquisition times for point clouds have been reduced to the order of seconds. Point clouds offer a very detailed representation of 3D data, but at the same time pose considerable challenges due to the amount and nature of data. <br /> In this thesis, we present our recent approaches to working with point clouds as a representation of 3D data and corresponding editing operations. First, we demonstrate how to apply non-linear editing operations on a point cloud based 3D model, allowing to bend, strech, rotate or scale parts of it in real-time, while ensuring smooth deformations and intuitive user interactions. A key ingredient is the use of quaternions to describe and compute point neighborhood relationships in a pose-invariant manner. Second, we introduce a technique to compute the skeleton of a biological tree, given real-world laser scan data. Such data may contain densely sampled regions, such as the tree trunk, while branches in the tree crown may be sampled sparsely and suffer from occlusions and noise. Our approach can determine the positions of branches and bifurcation points and also compute branch radii. <br /> Finally, we combine the previously described methods to create a framework for generating tree models by interpolating and extrapolating from given tree samples. The input tree point clouds are skeletonized and then transformed into a quaternion-based representation in a shape space. Different points in that shape space represent different trees, which are similar to the input samples, but still distinct and unique, so that they can be employed to populate diversified virtual environments.

Moderne Filme und Computerspiele nutzen reichhaltige virtuelle Umgebungen, um dem Verbraucher ein immersives Erlebnis zu bieten. Digitale Modelle sind oft einfacher und kostengünstiger zu erstellen als reales Filmmaterial von exotischen Orten, Gegenständen, Kreaturen oder Pflanzen zu beschaffen. Mit Fortschritten bei der Laser-basierten Entfernungsmessung haben sich die Erfassungszeiten für Punktwolken auf Sekunden verkürzt. Punktwolken bieten eine sehr detaillierte Darstellung von 3D-Daten, stellen aber gleichzeitig aufgrund der Datenmenge und -beschaffenheit eine große Herausforderung dar. <br /> In dieser Arbeit stellen wir unsere jüngsten Ansätze zur Arbeit mit Punktwolken als Repräsentation von 3D-Daten und entsprechende Bearbeitungsvorgänge vor. Zunächst zeigen wir, wie nicht-lineare Bearbeitungsoperationen auf ein punktwolkenbasiertes 3D-Modell angewendet werden können, die es ermöglichen, Teile des Modells in Echtzeit zu biegen, zu strecken, zu drehen oder zu skalieren, während plausible Verformungen und intuitive Benutzerinteraktionen sichergestellt werden. Ein Schlüsselelement ist die Verwendung von Quaternionen, um die Beziehungen zwischen benachbarten Punkten zu beschreiben und zu berechnen, und zwar auf eine positionsinvariante Weise. Anschließend stellen wir eine Technik zur Berechnung des Skeletts eines biologischen Baums anhand von realen Laserscan-Daten vor. Solche Daten können dicht abgetastete Regionen enthalten, wie beispielsweise den Baumstamm, während die Äste in der Baumkrone nur spärlich abgetastet werden und von Verdeckungen und Rauschen betroffen sind. Unser Ansatz kann die Positionen von Ästen und Verzweigungspunkten bestimmen und auch Zweigradien berechnen. <br /> Schließlich kombinieren wir die zuvor beschriebenen Methoden, um ein Verfahren für die Erzeugung von Baummodellen durch Interpolation und Extrapolation aus gegebenen Baumexemplaren vorzustellen. Die eingegebenen Punktwolken von Bäumen werden skelettiert und dann in eine Quaternionen-basierte Darstellung in einem Formraum überführt. Verschiedene Punkte in diesem Formraum repräsentieren verschiedene Bäume, die ähnlich sind, aber dennoch unterscheidbar und einzigartig, so dass sie sich für die Bestückung von diversifizierten virtuellen Umgebungen eignen.