Weiler-Atherton-Algorithmus
Der Weiler-Atherton-Algorithmus ist ein Verfahren aus der Computergrafik zur Verdeckungsberechnung von Polygonen.
Funktionsweise
[Bearbeiten | Quelltext bearbeiten]
Der erste Schritt des Weiler-Atherton-Algorithmus besteht darin, alle Polygone näherungsweise nach ihren z-Koordinaten zu sortieren. Das Polygon A, das laut dieser groben Sortierung am nächsten liegt, wird nun dazu verwendet, alle Polygone gegen A zu clippen und entlang dessen Kontur aufzuteilen. So entstehen zwei Listen: eine „Innenliste“, die alle Polygonteile enthält, die sich nach Projektion innerhalb vom clippenden Polygon A befinden (im Beispielbild rechts BinA), sowie eine „Außenliste“ mit allen außerhalb liegenden Teilen (im Beispielbild BoutA).
Alle Polygone der Innenliste, die sich hinter A befinden, werden gelöscht, da sie nicht sichtbar sind. Falls hingegen eines der Polygone der Innenliste näher am Betrachter als A liegt, so liegt das daran, dass die anfängliche Sortierung hier versagt hat. Für jedes dieser Polygone werden die Polygonteile der Innenliste darauf getestet, ob sie näher liegen, und eventuell geclippt. Dies läuft rekursiv ab. Am Ende des Prozesses wird die Innenliste entsprechend aktualisiert. Anschließend werden die Polygone der Außenliste abgearbeitet.
Zum Clippen werden stets die anfänglichen und nicht die aufgeteilten Polygone verwendet, da dies wegen der meist einfacheren Form der Originalpolygone weniger Aufwand erfordert. Daher muss für jedes aufgeteilte Polygon auch das Originalpolygon angegeben werden.
Um auch Polygone verarbeiten zu können, die sich gegenseitig überlappen, verwendet der Algorithmus einen Stapelspeicher. Dieser enthält alle clippenden Polygone, deren Verarbeitung wegen eines rekursiven Aufrufs unterbrochen wurde. Wenn ein Polygon gefunden wurde, das sich vor dem aktuellen clippenden Polygon befindet, wird es zunächst im Stapelspeicher gesucht. Falls es dort schon eingetragen wurde, ist keine Rekursion nötig, da alle Polygonteile innerhalb und hinter diesem Polygon bereits entfernt wurden.
Literatur
[Bearbeiten | Quelltext bearbeiten]- James D. Foley u. a.: Computer Graphics: Principles and Practice. Addison-Wesley, Reading 1995, ISBN 0-201-84840-6
- David F. Rogers: Procedural Elements for Computer Graphics. WCB/McGraw-Hill, Boston 1998, ISBN 0-07-053548-5
- Kevin Weiler, Peter Atherton: Hidden Surface Removal Using Polygon Area Sorting. ACM SIGGRAPH Computer Graphics 11, 2 (Summer 1977): 214–222, ISSN 0097-8930