Eingang zum Volltext
Lizenz
Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:kobv:83-opus-17140
URL: http://opus.kobv.de/tuberlin/volltexte/2007/1714/
Nealen, Andrew
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.
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.
URN: urn:nbn:de:kobv:83-opus-17140
URL: http://opus.kobv.de/tuberlin/volltexte/2007/1714/
Nealen, Andrew
Interfaces and Algorithms for the Creation, Modification, and Optimization of Surface Meshes
Schnittstellen und Algorithmen zur Erstellung, Modifikation und Optimierung von Flaechennetzen
| pdf-Format: |
|
Kurzfassung in Englisch
In this dissertation we present interfaces and algorithms for thecreation, 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.
Kurzfassung in Deutsch
Diese Dissertation beschreibt Benutzerschnittstellen und Algorithmenfuer 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.
| Freie Schlagwörter (deutsch): | Computergraphik , geometrische Modellierung , nichtlineare Optimierung , Benutzerschnittstellen , Glaettung | |
| Freie Schlagwörter (englisch): | computer graphics , geometric modeling , nonlinear optimization , user interfaces , smoothing | |
| Institut: | Institut für Technische Informatik und Mikroelektronik | |
| Fakultät: | Fakultät IV - Elektrotechnik und Informatik | |
| DDC-Sachgruppe: | Informatik | |
| Dokumentart: | Dissertation | |
| Hauptberichter: | Alexa, Marc (Prof. Dr.-Ing.) | |
| Sprache: | Englisch | |
| Tag der mündlichen Prüfung: | 12.10.2007 | |
| Erstellungsjahr: | 2007 | |
| Publikationsdatum: | 19.12.2007 | |
| Lizenz: | Minimallizenz mit PoD (Print-on-Demand): Typ Dissertation |
