Welfenlab - Leibniz 
                        Universität Hannover Welfenlab Leibniz Universität Hannover

Zerlegung polygonal berandeter Gebiete in der euklidischen Ebene in konvexe Teilbereiche

Daniela Lauer, Leibniz Universität Hannover, bachelor thesis
01/2005

In der Computergrafik werden möglichst einfache Darstellungen verwendet um geometrische Objekte zu modellieren. Eine gÀngige Methode ist es ein Objekt durch die Approximation seiner OberflÀche darzustellen. Dabei wird diese aus einer Menge planarer Vielecke,

 

hier Polygone genannt, zusammengesetzt. Damit auch komplexe Objekte effektiv verwaltet und bearbeitet werden können, wird jedoch noch eine einfachere Darstellung der TeilstĂŒcke benötigt. Eine Möglichkeit ist, Polygone als die Vereinigung von weniger komplexen TeilstĂŒcken zu reprĂ€sentieren. Ein konvex zerlegtes Polygon setzt sich nur aus konvexen TeilstĂŒcken (einfacheren Polygonen) zusammen.

Die Motivation fĂŒr die vorliegende Arbeit kommt aus der Computergrafik aus dem Gebiet wissenschaftliche Visualisierung mit Spiele-Engines. FĂŒr eine optisch anspruchsvolle Visualisierung in Echtzeit wird unter anderem eine leistungsstarke Renderingsoftware benötigt. Eine gĂŒnstige Alternative zu kommerziellen Produkten wie z.B. 3D Studio MAX oder Autocad bieten Spiele-Engines. Im Gegensatz zu den AnfĂ€ngen der Computergrafik sind heute die Hersteller von animierten Filmen und Computerspielen fĂŒhrend im Bereich der Echtzeit 3D-Visualisierung.

Deshalb wird am Lehrstuhl Graphische Datenverarbeitung, Institut fĂŒr Mensch-Maschine-Kommunikation der Leibniz UniversitĂ€t Hannover, die Eignung von Spieleengines fĂŒr die Visualisierung wissenschaftlicher Daten anhand einiger Beispiele (Sarnow: Quake 3, Hanel: Unreal 2) erprobt. Die von einem Laserscanner gemessene Punktwolke der HöhlenwĂ€nde wurde in Diplomarbeiten (Farajollahi, Friese,) in eine triangulierte Darstellung ĂŒberfĂŒhrt und dient als Datenquelle fĂŒr diese Untersuchungen. Erste Ergebnisse ermöglichen ein flĂŒssiges Durchwandern der Höhle. In der Darstellung mit der Quake-Engine fĂŒhrte jedoch beispielsweise das HinzufĂŒgen von aufwĂ€ndigen Lichteffekten zu Performanceverlusten. Dies liegt unter anderem an der Menge der darzustellende Polygone (bislang Dreiecke). Die Quake Engine ist jedoch in der Lage, nicht nur Dreiecke, sondern konvexe Polygone einzulesen und zu verarbeiten. Dies eröffnet die Möglichkeit, durch das Verwenden grĂ¶ĂŸerer konvexer TeilstĂŒcke mit möglichst wenig Detailverlust die Anzahl der Polygone zu reduzieren.

Die Idee liegt also nahe, nach großen planaren oder quasiplanaren Teilgebieten bestehend aus mehreren Dreiecken zu suchen, um diese dann als Vereinigung einer Menge von konvexen Polygonen darzustellen. Es wird also ein Algorithmus benötigt, der ein in triangulierter Form vorliegendes Gebiet (Polygone) in möglichst wenige konvexe TeilstĂŒcke zerlegt.

Kontakt: Karl-Ingo Friese

Top | Last Change 26.04.2009 | Editorial Responsibility 
| Imprint | © FG Graphische Datenverarbeitung