imported>Llydia: interne Verlinkung gestärkt

2024-02-11T12:19:56Z

interne Verlinkung gestärkt

Neue Seite

[[Datei:Haloed wireframe.png|thumb|Ein Drahtgittermodell ohne und mit Halo]]
Der '''Haloed-Line-Algorithmus''' ist ein Verfahren der [[Computergrafik]], um [[Drahtgittermodell]]e oder allgemeine dreidimensionale Linien darzustellen. Durch diese Form der [[Geometrische_Modellierung#Oberflächendarstellung|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 [[Halo (Bildbearbeitung)|Halos]] groß genug gewählt wird, entsteht der Effekt, dass wie bei einer vollständigen [[Sichtbarkeitsproblem|Verdeckungsberechnung]] nur die sichtbaren Flächen angezeigt werden.

== Funktionsweise ==

=== Vorbereitung ===
[[Datei:Haloed line.svg|thumb|upright=0.8|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 (Mathematik)|Gitter]] eingeteilt, dessen Feinheit von der durchschnittlichen Linienlänge abhängt. Zusätzlich werden für jede Linie die Koeffizienten der entsprechenden [[Geradengleichung]] <math>z = ax + by + d</math> gespeichert. Für jede Linie <math>L_i</math> werden die Gitterzellen ermittelt, durch die sie läuft. In einer Liste werden zu jeder Zelle die dazugehörigen Linien als <math>(C_{i,\,j},\,L_i)</math> vermerkt und nach Zelle sortiert.

Für jede Zelle werden hindurchlaufende Linien <math>L_i</math> und <math>L_j</math> paarweise geprüft, ob sie einander schneiden. Ist dies der Fall, so wird der Schnittpunkt <math>I</math> beider Linien ermittelt. Außerdem wird bestimmt, welche der Linien am Schnittpunkt die kleinere ''z''-Koordinate besitzt, also dem Betrachter näher liegt. Liegt <math>L_i</math> näher, so wird der Winkel <math>\theta</math> zwischen <math>L_i</math> und <math>L_j</math> berechnet. Die Ergebnisse werden als <math>(L_i,\,I,\,\theta)</math> in einer Tabelle <math>T</math> gespeichert. Sobald alle Gitterzellen abgearbeitet wurden, wird die
Tabelle <math>T</math> nach <math>L_i</math> 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 <math>T</math> Eintrag für Eintrag durchgegangen. Für jeden Eintrag werden mittels <math>H</math> und <math>\theta</math> die Punkte <math>I_1</math> und <math>I_2</math> berechnet, an denen das Halo auf der Linie um den Schnittpunkt herum aufhört und wieder anfängt. Die Paare <math>(I_1, -1)</math> und <math>(I_2, +1)</math> werden in einer Tabelle <math>S</math> gespeichert. Zusätzlich werden die Paare <math>(E_1, +1)</math> und <math>(E_2, -1)</math> gespeichert, wobei <math>E_1</math> und <math>E_2</math> die Endpunkte der Linie sind.

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

[[Kategorie:Bildsynthese]]
[[Kategorie:Algorithmus (Computergrafik)]]

Haloed-Line-Algorithmus - Versionsgeschichte

imported>Llydia: interne Verlinkung gestärkt