Uhrig, Stefan (2007)
Automatische Generierung von dreidimensionalen Dreiecksnetzen aus Punktwolken-Daten.
Technische Universität Darmstadt
Masterarbeit, Bibliographie

Kurzbeschreibung (Abstract)

In den vergangenen Jahren wurden beachtliche Fortschritte in der Entwicklung von Technologien zur Abtastung geometrischer Objekte erzielt. Resultat solcher Abtastungen sind üblicherweise sogenannte Punktwolken. Sie bestehen aus einzelnen Punkten, die von der Oberfläche des abgetasteten Gegenstands aufgenommen wurden. Die effiziente und qualitativ hochwertige Rekonstruktion des ursprünglichen Objekts aus den gemessenen Daten ist dabei in der modernen Computergrafik von zentraler Bedeutung. Neben der eigentlichen Rekonstruktion der Oberfläche stellt die Überführung in eine geeignete nicht-diskrete Repräsentation eine zentrale Herausforderung dar. Nach wie vor ist die Darstellung von Oberflächen durch Dreiecksnetze ein weit verbreiteter Standard. Diese Arbeit untersucht sowohl die Rekonstruktion von Oberflächen beliebiger Topologie aus Punktwolken als auch die anschließende Triangulierung der rekonstruierten Oberfläche. Insbesondere werden moderne Advancing Front Algorithmen analysiert, die durch ein hohes Maß an Kontrolle über die Triangulierung in der Lage sind, ein qualitativ hochwertiges Dreiecksnetz zu erzeugen. Advancing Front Algorithmen rekonstruieren Oberflächen durch den Einsatz von Projektionsverfahren, die Punkte im Raum auf die Oberfläche abbilden. Die Bereitstellung eines robusten und effizienten Projektionsverfahrens bildet damit die Basis einer erfolgreichen Triangulierung. Als Projektionsverfahren, das Punkte auf die Oberfläche abbildet, die durch eine Punktwolke repräsentiert wird, wurde bisher gewöhnlich das Moving Least Squares Verfahren eingesetzt. Wie aufgezeigt werden wird, bestehen bei Einsatz des Moving Least Squares Verfahrens in Verbindung mit Advancing Front Algorithmen praktische Berechnungsprobleme, die auf der Notwendigkeit der Lösung eines nicht-linearen Minimierungsproblems beruhen. Hauptbeitrag dieser Arbeit bildet die Entwicklung eines neuen Projektionsverfahrens, das auf Delaunay-Triangulierungen basiert. Gegenüber dem Moving Least Squares Verfahren zeichnet es sich zum einen durch bessere Rekonstruktionseigenschaften aus. Zum anderen kommt das von uns vorgeschlagene Verfahren ohne die numerische Lösung nicht-linearer Minimierungs- und verwandter Probleme aus. Zur Durchführung einer Projektion müssen lediglich Berechnungen durchgeführt werden, für die effiziente und robuste Algorithmen existieren. Als unmittelbare Folge bleibt auch der Berechnungsaufwand geringer. Die vielfältigen aus unseren aufwendigen Implementierungen resultierenden Tests zeigen, dass die neuen Methoden insgesamt auf eine bis dato nicht bekannte hohe Robustheit und Effizienz zur automatischen Triangulierung von Punktwolken allgemeiner Art führen. In recent years considerable advancements in development of geometric object scanning technologies were achieved. Typically so called point clouds are result of these scans. They consist of discrete points recorded from the surface of the scanned object. An efficient and high-quality reconstruction of the original object based on the measured data is of high importance in modern computer graphics. Besides the actual surface reconstruction the conversion to an appropriate non-discrete representation forms a challenging task. The description of surfaces by triangular meshes is still a wide-spread standard. This thesis studies both arbitrary topology surface reconstructions from point clouds and the following surface meshing. Especially modern advancing front algorithms are analyzed. Due to a high level of control on the triangulation these algorithms are able to produce a high-quality mesh. They reconstruct surfaces by employing a method that projects points in space onto the surface. Providing an efficient and robust projection method therefore constitutes a central requirement of a successful triangulation. Up to now Moving Least Squares were usually used to project points onto surfaces represented by point clouds. We will show that there occur practical computation problems when using Moving Least Squares in conjunction with advancing front algorithms. These problems are based on the necessity to solve a non-linear minimization-problem. The main contribution of this thesis is the development of a new projection method that is based on Delaunay triangulations. Compared to Moving Least Squares it features better reconstruction of surfaces represented by point clouds. Furthermore our method does not require solving a non-linear minimization or similar problem but there exist efficient and robust algorithms for all necessary computations. As the direct consequence the computational costs are lower. Numerous tests resulting from our complex implementations show that these new methods lead to a previously unachieved high robustness and performance in automatic point cloud triangulations.

Frage zum Eintrag

Redaktionelle Details anzeigen