Projekt- / Diplomarbeit

Abtastung Abtastung parametrischer Flächen mit Partikelsystemen und anisotropen Voronoi Diagrammen

[1]

[2]

Kurze Problembeschreibung:

Detaillierte Problembeschreibung:

Die Abtastung parametrischer Flächen zur graphischen Darstellung oder für den Einsatz in Finite Elemente Berechnungen verlangt eine geschickte Wahl der Abtastpunkte im Parametergebiet, so daß eine gleichmäßige Verteilung im R³ mit größerer Dichte an Stellen hoher Krümmung entsteht.

Bisher exisitieren zu diesem Zwecke hauptsächlich Verfeinerungsalgorithmen, die abhängig von lokalen Fehlermassen weitere Abtastpunkte einfügen. Dabei werden einmal eingefügte Punkte nicht mehr verändert, was in der Regel zu suboptimalen Ergebnissen führt. In einem verwandten Forschungsgebiet, der Isoflächenextraktion, existiert zur Lösung desselben Problems der Ansatz der dynamischen Partikel [1]. Hier werden die Abtastpunkte durch Partikel repräsentiert, die sich durch ein sie umgebendes, abstossendes Energiepotential autonom so im Raum verteilen, daß entsprechende Qualitätskriterien erfüllt sind. Im Prinzip stellt die Abtastung parametrischer Flächen einen Spezialfall dessen mit gewissen Nebenbedingungen dar.

Bei der direkten Anwendung dynamischer Partikel zur Abtastung von parametrischen Flächen wird nicht ausgenutzt, daß wir die Topologie der Mannigfaltigkeit lokal kennen. Das führt bei dicht aneinanderliegenden Flächenteilen zu Unterabtastung, was wir vermeiden möchten.

Die von den Energiepotentialen induzierten Kräfte, die zur Selbstorganisation der Partikel führen, hängen sowohl von Distanzen im R³ als auch von der Krümmung der Fläche ab. Zur effizienten Berechnung der Partikelentwicklung sowie auch zur Vermeidung degenerierter Fälle können Nachbarschaftsbeziehungen zwischen Partikeln im Parametergebiet herangezogen werden.

Um die in R³ existierenden Beziehungen im Parametergebiet abzubilden, wo sich die Partikel letztendlich bewegen, sollen anisotrope Voronoi Diagramme eingesetzt werden [2]. Diese zeichnen sich dadurch aus, daß jeder Punkt der generierenden Menge seinen eigenen, richtungsabhängigen Distanzbegriff besitzt.

Aufgabenbeschreibung:

Im Zuge der Diplom- / Projektarbeit sollen folgende Punkte erarbeitet werden:

• Umsetzung des Verfahrens der selbstorganisierenden, dynamischen Partikel auf parametrischen Flächen.
• Implementierung einer effizienten Datenstruktur für anisotrope Voronoi Diagramme.
• Untersuchung verschiedener Kriterien für die bestimmung der Metriktensoren zur Steuerung der Verteilung der Partikel im R³ anhand der anisotropen Voronoi Diagramme.

Optional sind noch folgende Punkte möglich:

• Implementierung eines Splatrenderers zur Visualisierung
• Implementierung des Anisotropic Meshing Verfahrens von J. R. Shewchuk

Die Arbeit kann (muss aber nicht) auf bestehenden C++ Bibliotheken aufsetzen. Eine (langsame) Referenzimplementierung der dynamischen Partikel steht in C++ / Nurbs++ zur Verfügung. Erwünschte Vorkenntnisse: Programmierung in C++ Geometrische Modellierung Differentialgeometrie Bei Interesse und Fragen wenden Sie sich bitte an

• Dipl. Inform. Tom Bobach, Raum 237, bobach @ informatik.uni-kl.de
• Prof. Georg Umlauf, Raum 236, umlauf @ informatik.uni-kl.de

Referenzen:

[1] M. Meyer and P. Georgel and R.T. Whitaker, Robust Particle Systems for Curvature Dependent Sampling of Implicit Surfaces, Proceedings of the International Conference on Shape Modeling and Applications (SMI), June 2005

[2] François Labelle and Jonathan Richard Shewchuk, Anisotropic Voronoi Diagrams and Guaranteed-Quality Anisotropic Mesh Generation, Proceedings of the Nineteenth Annual Symposium on Computational Geometry (San Diego, California), pages 191-200, Association for Computing Machinery, June 2003.

Date: 21st June 2007