Haloed-Line-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Ein Drahtgittermodell ohne und mit Halo

Der Haloed-Line-Algorithmus ist ein Verfahren der Computergrafik, um Drahtgittermodelle oder allgemeine dreidimensionale Linien darzustellen. Durch diese Form der Oberflächendarstellung erhalten die gezeichneten Linien eine Kontur („Halo“), die dahinterliegende Linien verdeckt. Diese Perspektive verstärkt den Eindruck von Räumlichkeit. Wenn die Breite des Halos groß genug gewählt wird, entsteht der Effekt, dass wie bei einer vollständigen Verdeckungsberechnung nur die sichtbaren Flächen angezeigt werden.

Geometrie einer Linie mit Halo. Die hinter der Linie A liegende Linie B wird vom Halo verdeckt.

Der Haloed-Line-Algorithmus besteht aus einer Vorbereitungs- und einer Anzeigeroutine. Bei der Vorbereitung wird das Bild in ein Gitter eingeteilt, dessen Feinheit von der durchschnittlichen Linienlänge abhängt. Zusätzlich werden für jede Linie die Koeffizienten der entsprechenden Geradengleichung gespeichert. Für jede Linie werden die Gitterzellen ermittelt, durch die sie läuft. In einer Liste werden zu jeder Zelle die dazugehörigen Linien als vermerkt und nach Zelle sortiert.

Für jede Zelle werden hindurchlaufende Linien und paarweise geprüft, ob sie einander schneiden. Ist dies der Fall, so wird der Schnittpunkt beider Linien ermittelt. Außerdem wird bestimmt, welche der Linien am Schnittpunkt die kleinere z-Koordinate besitzt, also dem Betrachter näher liegt. Liegt näher, so wird der Winkel zwischen und berechnet. Die Ergebnisse werden als in einer Tabelle gespeichert. Sobald alle Gitterzellen abgearbeitet wurden, wird die Tabelle nach sortiert. Linien, die nicht in der Tabelle eingetragen sind, schneiden keine anderen Linien und sind somit stets sichtbar; sie werden ebenfalls in die Tabelle eingetragen.

Um die Linien anzuzeigen, wird die Tabelle Eintrag für Eintrag durchgegangen. Für jeden Eintrag werden mittels und die Punkte und berechnet, an denen das Halo auf der Linie um den Schnittpunkt herum aufhört und wieder anfängt. Die Paare und werden in einer Tabelle gespeichert. Zusätzlich werden die Paare und gespeichert, wobei und die Endpunkte der Linie sind.

Die so entstandene Tabelle wird nun nach sortiert und der Reihe nach durchgegangen, wobei die jeweiligen Werte +1 oder −1 summiert werden. Wenn die Summe 1 beträgt, wird angefangen, die Linie zu zeichnen, wenn sie einen Wert ≤0 erreicht, wird die Zeichnung der Linie wieder gestoppt.

Diese Prozedur ist beendet, wenn alle Einträge der Tabelle abgearbeitet wurden.

  • Arthur Appel u. a.: The Haloed Line Effect for Hidden Line Elimination. ACM SIGGRAPH Computer Graphics 13, 2 (Aug. 1979): 151–157, ISSN 0097-8930
  • David F. Rogers: Procedural Elements for Computer Graphics. WCB/McGraw-Hill, Boston 1998, ISBN 0-07-053548-5