Weiler-Atherton-Algorithmus

Der Weiler-Atherton-Algorithmus ist ein Verfahren aus der Computergrafik zur Verdeckungsberechnung von Polygonen.

Funktionsweise

Unterteilung mit dem Weiler-Atherton-Algorithmus

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 B_inA), sowie eine „Außenliste“ mit allen außerhalb liegenden Teilen (im Beispielbild B_outA).

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

• 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