Loading…
Interfaces and Algorithms for the Creation, Modification, and Optimization of Surface Meshes
Nealen, Andrew
Diese Dissertation beschreibt Benutzerschnittstellen und Algorithmen fuer die Erzeugung, Modifizierung und Optimierung diskreter Flaechen. Nach einer kurzen Einfuehrung, Motivation und Zusammenstellung der neuen Beitraege wird der aktuelle Stand der Technik bezueglich der Erstellung und Modellierung diskreter Flaechen beschrieben, sowie ein Ueberblick der verwendeten mathematischen Werkzeuge gegeben. Fuer das einfache Erzeugen diskreter Flaechen wird eine Benutzerschnittstelle fuer das Design von Freiformflaechen unter Verwendung dreidimensionaler Kurven praesentiert. Der Benutzer erzeugt ein grobes dreidimensionales Modell unter Zuhilfenahme einer auf Freihand Skizzen basierenden Benutzerschnittstelle. Anders als in bisherigen Systemen bleiben die Skizzen und Striche des Benutzers auf dem Oberflaechenmodell bestehen, und dienen als kurvenfoermige Griffe (Kontrollkurven) mit denen die Geometrie veraendert werden kann. Der Benutzer kann diese Kontrollkurven sehr einfach hinzufuegen, entfernen und deformieren, als wuerde man mit einer zweidimensionalen Linienzeichnung arbeiten. Den Kurven kann eine beliebige Topologie zugrunde liegen; Sie muessen nicht verbunden sein. Fuer eine gegebene Kurvenmenge wird durch die Optimierung eines Flaechenfunktionals automatisch eine interpolierende, glatte Flaeche konstruiert. Das System ist mit Echtzeit Algorithmen ausgestattet, sowohl fuer die Deformation von Kontrollkurven als auch fuer die darauffolgende Flaechenoptimierung. Es werden anspruchsvolle Modelle die mit diesem System erstellt wurden praesentiert, welche mit bisherigen skizzenbasierten Werkzeugen nicht moeglich waren. Daraufhin werden Methoden fuer das intuitive Editieren diskreter Flaechen anhand von blickpunktsabhaengigen Skizzen vorgestellt. In den meisten existierenden Arbeiten zur Modelldeformation wird eine Editieroperation durch Auswahl und Verschiebung eines Griffs durchgefuehrt. Ein Griff wird dabei i.d.R. als Knotenmenge des Graphen repraesentiert. Im neuen System kann der Benutzer diesen Griff entweder durch Auswahl und Zuschnitt einer Silhouette, oder durch direktes Skizzieren auf die Flaeche auswaehlen. Editieroperationen werden danach entweder durch das Skizzieren einer neuen, blickpunktsabhaengigen Griffposition, oder durch das Variieren differentieller Eigenschaften entlang der Skizze ausgefuehrt. In Kombination vereinfachen diese Editier- und Griffmetaphern ansonsten komplexe Flaechenmodifikationen. Um den Prozess des Editierens weiter zu vereinfachen, wird eine skizzenbasierte Benutzerschnittstelle vorgestellt, die das Auswaehlen von Griff und Deformationsbereich auf der Modelloberflaeche automatisiert. Der Benutzer skizziert die neue Position eines Teils einer Silhouette in der aktuellen Ansicht. Daraufhin segmentiert das System alle Bildraumsilhouetten, identifiziert unter allen Silhouettensegmenten das Segment, welches der Benutzerskizze am aehnlichsten ist, leitet daraus die korrespondierenden Knoten der diskreten Flaeche ab, waehlt eine Region der Flaeche zur Deformation aus, und stellt diese Informationen fuer ein Flaechendeformationswerkzeug zur Verfuegung. Insgesamt wurde dieser Algorithmus entwickelt, um eine interaktive Modifizierung der Flaeche zu ermoeglichen -- dabei wurde ein Flaechendeformationswerkzeug entwickelt, welches dem zweidimensionalen Skizzieren auf Papier sehr nahe kommt. Sowohl diskrete Flaechen die mit den vorgestellten Werkzeugen und Algorithmen erstellt wurden, als auch eingescannte, abgetastete und vereinfachte Modelle koennen Dreiecke mit schlechtem Seitenverhaeltnis oder starkes Rauschen beinhalten. Zur Verbesserung wird ein Verfahren zur Dreiecksoptimierung und merkmalserhaltender Glaettung vorgestellt, welches von uniform- und Kotangens-diskretisierten Laplace Vektoren gesteuert wird. Knotenpunkte werden verschoben, so dass sie vorgeschriebene Laplace Vektoren und Positionen im Sinne der gewichteten kleinsten Fehlerquadrate approximieren. Das daraus resultierende lineare Gleichungssystem laesst sich effizient loesen. Es werden verschiedene Verfahren zur Gewichtung bereitgestellt. Um die Effizienz des Verfahrens zu demonstrieren werden eine Vielzahl von detaillierten und irregulaeren Netzen hinsichtlich Dreiecksform und Rauschen optimiert. Abschliessend werden die vorgestellten Loesungen diskutiert, offene Fragen hinsichtlich dieser Dissertation und Flaechenmodellierung im Allgemeinen praesentiert, moegliche Verbesserungen skizziert, und Vorschläge für weiterführende Forschung gemacht.
In this dissertation we present interfaces and algorithms for the creation, modification and optimization of surface meshes. After a short introduction, motivation, and list of contributions, we describe the current state of the art in mesh creation and modeling, and also give an overview of the mathematical tools that are used throughout this dissertation. For the simple creation of surface meshes, we present an interface for designing freeform surfaces with a collection of 3D curves. The user first creates a rough 3D model by using a sketching interface. Unlike previous sketching systems, the user-drawn strokes stay on the model surface and serve as handles for controlling the geometry. The user can add, remove, and deform these control curves easily, as if working with a 2D line drawing. The curves can have arbitrary topology; they need not be connected to each other. For a given set of curves, the system automatically constructs a smooth surface embedding by applying functional optimization. Our system provides real-time algorithms for both control curve deformation and the subsequent surface optimization. We show that one can create sophisticated models using this system that have not yet been seen in previous sketching or functional optimization systems. Thereafter, we present methods for the intuitive editing of surface meshes by means of view-dependent sketching. In most existing shape deformation work, editing is carried out by selecting and moving a handle, usually a set of vertices. Our system lets the user easily determine the handle, either by silhouette selection and cropping, or by sketching directly onto the surface. An edit is carried out by sketching a new, view-dependent handle position or by indirectly influencing differential properties along the sketch. Combined, these editing and handle metaphors greatly ease otherwise complex shape modeling tasks. To further simplify the editing process, we introduce an over-sketching interface for surface mesh editing that automates the processes of determining both the deformation handle, as well as the region to be deformed. The user sketches a stroke that is the suggested position of part of a silhouette of the displayed surface. The system then segments all image-space silhouettes of the projected surface, identifies among all silhouette segments the best matching part, derives vertices in the surface mesh corresponding to the silhouette part, selects a sub-region of the mesh to be modified, and feeds appropriately modified vertex positions together with the sub-mesh into a mesh deformation tool. The overall algorithm has been designed to enable interactive modification of the surface -- yielding a surface editing system that comes close to the experience of over-sketching 2D drawings on paper. Surface meshes created and edited with our tools -- as well as scanned, contoured or simplified models -- may contain triangles with bad aspect ratios and/or significant noise. To improve this, we introduce a framework for triangle shape optimization and feature preserving smoothing of triangular meshes that is guided by vertex Laplacians, specifically, the uniformly weighted Laplacian and the discrete mean curvature normal. Vertices are relocated so that they approximate prescribed Laplacians and positions in a weighted least-squares sense; the resulting linear system leads to an efficient, non-iterative solution. We provide different weighting schemes and demonstrate the effectiveness of the framework on a number of detailed and highly irregular meshes; our technique successfully improves the quality of the triangulation while remaining faithful to the original surface geometry, and it is also capable of smoothing the surface while preserving geometric features. In closing, we discuss our proposed solutions, present open questions related to this dissertation and shape modeling in general, outline possible improvements, and propose areas for further research.
