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. Die gezeichneten Linien erhalten dabei eine Kontur („Halo“), die dahinterliegende Linien verdeckt. Dadurch wird der Eindruck von Räumlichkeit verstärkt. 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 z = ax + by + d gespeichert. Für jede Linie L_i werden die Gitterzellen ermittelt, durch die sie läuft. In einer Liste werden zu jeder Zelle die dazugehörigen Linien als $(C_{i,\,j},\,L_i)$ vermerkt und nach Zelle sortiert.

Für jede Zelle werden hindurchlaufende Linien L_i und L_j paarweise geprüft, ob sie einander schneiden. Ist dies der Fall, so wird der Schnittpunkt 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 L_i näher, so wird der Winkel θ zwischen L_i und L_j berechnet. Die Ergebnisse werden als $(L_i,\,I,\,\theta)$ in einer Tabelle T gespeichert. Sobald alle Gitterzellen abgearbeitet wurden, wird die Tabelle T nach 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 T Eintrag für Eintrag durchgegangen. Für jeden Eintrag werden mittels H und θ die Punkte I₁ und I₂ berechnet, an denen das Halo auf der Linie um den Schnittpunkt herum aufhört und wieder anfängt. Die Paare (I₁, − 1) und (I₂, + 1) werden in einer Tabelle S gespeichert. Zusätzlich werden die Paare (E₁, + 1) und (E₂, − 1) gespeichert, wobei E₁ und E₂ die Endpunkte der Linie sind.

Die so entstandene Tabelle S wird nun nach 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 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