Implementation und Analyse von Triangle Strip Algorithmen

Friedrich Hattendorf, Leibniz Universität Hannover, masters thesis
05/2013

Volumenkörper werden in der Computergrafik oft durch die Darstellung ihrer Oberfläche als Dreiecksnetz repräsentiert. Gerade bei komplexeren Objekten kann dabei die Dreieckszahl schnell mehrere Millionen erreichen, was auch heute noch eine Herausforderung für die Grafikkarte darstellt. Zwar existieren Verfahren, die ein Dreiecksnetz vereinfachen (= die Anzahl der Dreiekce reduzieren), dabei besteht jedoch immer die Gefahr, dass wichtige Details der Oberfläche Verloren gehen können oder schlimmstenfalls sogar Selbstüberschneidungen erzeugt werden.

Eine interessante Alternative stellen die sogenannten Triangle-Strips dar. Bei dieser Datenstruktur, wird versucht, das Netz aus möglichst langen Dreiecks-Streifen zusammenzusetzen, bei der sich jeweilst zwei aufeinanderfolgende Dreiecke genau eine Kante teilen. Durch diesen Trick lässt sich im Idealfall der benöitgte Speicheraufwand auf 1/3 reduzieren. Das Problem der Findung einer solchen idealen Zerlegung ist jedoch N(P) vollständig. Daher existieren eine Vielzahl von Verfahren, die mit heuristischen Methoden versuchen, eine möglichst gute Triangle Strip Darstellung zu finden.

Ziel dieser Arbeit ist es, verschiedene Verfahren aus dieser Kateogrie zu implementieren und für Dreiecksflächen aus medizinischen Anwendungen zu vergleichen. Zusätzlich soll ein eigenes Verfahren implentiert werden, bei dem der Augenmerk nicht in einer möglichst guten Strip Darstellung sondern der Erzeugung der Strip Struktur ohne nennenswerten Zeit- und Speicheraufwand liegt.

Kontakt: Karl-Ingo Friese