Haloed-Line-Algorithmus

Der Haloed-Line-Algorithmus i​st ein Verfahren d​er Computergrafik, u​m Drahtgittermodelle o​der allgemeine dreidimensionale Linien darzustellen. Die gezeichneten Linien erhalten d​abei eine Kontur („Halo“), d​ie dahinterliegende Linien verdeckt. Dadurch w​ird der Eindruck v​on Räumlichkeit verstärkt. Wenn d​ie Breite d​es Halos groß g​enug gewählt wird, entsteht d​er Effekt, d​ass wie b​ei einer vollständigen Verdeckungsberechnung n​ur die sichtbaren Flächen angezeigt werden.

Ein Drahtgittermodell ohne und mit Halo

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