Haloed-Line-Algorithmus

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.

Funktionsweise

Vorbereitung

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 ${\displaystyle z=ax+by+d}$ gespeichert. Für jede Linie ${\displaystyle L_{i}}$ werden die Gitterzellen ermittelt, durch die sie läuft. In einer Liste werden zu jeder Zelle die dazugehörigen Linien als ${\displaystyle (C_{i,\,j},\,L_{i})}$ vermerkt und nach Zelle sortiert.

Für jede Zelle werden hindurchlaufende Linien ${\displaystyle L_{i}}$ und ${\displaystyle L_{j}}$ paarweise geprüft, ob sie einander schneiden. Ist dies der Fall, so wird der Schnittpunkt ${\displaystyle I}$ beider Linien ermittelt. Außerdem wird bestimmt, welche der Linien am Schnittpunkt die kleinere z-Koordinate besitzt, also dem Betrachter näher liegt. Liegt ${\displaystyle L_{i}}$ näher, so wird der Winkel ${\displaystyle \theta }$ zwischen ${\displaystyle L_{i}}$ und ${\displaystyle L_{j}}$ berechnet. Die Ergebnisse werden als ${\displaystyle (L_{i},\,I,\,\theta )}$ in einer Tabelle ${\displaystyle T}$ gespeichert. Sobald alle Gitterzellen abgearbeitet wurden, wird die Tabelle ${\displaystyle T}$ nach ${\displaystyle L_{i}}$ 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.

Anzeige

Um die Linien anzuzeigen, wird die Tabelle ${\displaystyle T}$ Eintrag für Eintrag durchgegangen. Für jeden Eintrag werden mittels ${\displaystyle H}$ und ${\displaystyle \theta }$ die Punkte ${\displaystyle I_{1}}$ und ${\displaystyle I_{2}}$ berechnet, an denen das Halo auf der Linie um den Schnittpunkt herum aufhört und wieder anfängt. Die Paare ${\displaystyle (I_{1},-1)}$ und ${\displaystyle (I_{2},+1)}$ werden in einer Tabelle ${\displaystyle S}$ gespeichert. Zusätzlich werden die Paare ${\displaystyle (E_{1},+1)}$ und ${\displaystyle (E_{2},-1)}$ gespeichert, wobei ${\displaystyle E_{1}}$ und ${\displaystyle E_{2}}$ die Endpunkte der Linie sind.

Die so entstandene Tabelle ${\displaystyle S}$ wird nun nach ${\displaystyle L_{i}}$ 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 ${\displaystyle T}$ abgearbeitet wurden.

Literatur

• 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