Sichtbarkeitsproblem

Das Sichtbarkeitsproblem ist beim Rendern in der Computergrafik die Fragestellung, welche Teile von Oberflächen in einer 3D-Szene bei der Projektion auf die zweidimensionale Anzeigefläche sichtbar sind. Als Verdeckungsberechnung oder Sichtbarkeitsentscheid wird dementsprechend ein Vorgehen bezeichnet, mit dem nicht sichtbare Oberflächen erkannt und aussortiert werden und so das Sichtbarkeitsproblem gelöst wird. Das Sichtbarkeitsproblem war eines der ersten wichtigen Probleme der Computergrafik.

Oben: Ansicht einer Szene mit Betrachter.
Unten links: Projizierte Objekte ohne Verdeckungsberechnung.
Unten rechts: Gerendertes Bild nach Verdeckungsberechnung, bei der ermittelt wurde, dass die blaue Kugel und das graue Dreieck die gelbe Kugel teilweise verdecken.

Die Verdeckungsberechnung ist zum korrekten Rendern einer 3D-Szene notwendig, weil Oberflächen, die für den Betrachter nicht sichtbar sind, auch nicht dargestellt werden sollten. Viele Verfahren beschleunigen zusätzlich das Rendern, weil nicht sichtbare Oberflächen von der weiteren Verarbeitung durch die Grafikpipeline ausgeschlossen werden können.

Verfahren

Nach Ivan Sutherland können Algorithmen zur Verdeckungsberechnung in Objektraumverfahren, Bildraumverfahren und List-Priority-Verfahren eingeteilt werden.^[1] Während bei den Objektraumverfahren die Sichtbarkeiten direkt anhand der Objekte analytisch und unabhängig vom Ausgabegerät berechnet werden, wird bei den Bildraumverfahren die Verdeckungsberechnung für jede einzelne Bild- oder Pixelposition separat durchgeführt. List-Priority-Algorithmen berechnen zunächst anhand der Objekte eine Sichtbarkeitsreihenfolge oder „Priorität“ im Voraus und färben anschließend die Pixel des Bildes ein; sie arbeiten also teils im Objekt- als auch im Bildraum.

Heutige Grafikhardware nutzt zur Verdeckungsberechnung meist einen Z-Buffer; bei der realistischen Bildsynthese wird häufig Raytracing verwendet.

Für ein verwandtes Problem siehe Sichtbarkeitspolygon.

Objektraumverfahren

Roberts (1963)

Von Larry Roberts^[2] stammt das erste bekannte Verfahren zur Verdeckungsberechnung.^[3] Roberts’ Algorithmus testet jede Polygonkante gegen jedes Polyeder, ob sie (teilweise oder vollständig) verdeckt wird. Dieser Test wird durchgeführt, indem ein lineares Gleichungsproblem gelöst wird. Roberts’ Algorithmus funktioniert nur mit konvexen Polyedern.

Appel, Loutrel, Galimberti, Montanari (1967/69)

Appels Algorithmus^[4] steht stellvertretend für eine Klasse von Algorithmen, die die sichtbaren Kantensegmente ermitteln. Im Unterschied zum Roberts-Algorithmus können sie auch die Verdeckung durch einzelne Polygone, nicht nur durch ganze Polyeder, berechnen. Appel definiert die quantitative Unsichtbarkeit eines Punkts als die Anzahl maßgeblicher Polygone, die ihn verdecken. Wenn eine Kante hinter ein verdeckendes Polygon gleitet, wird die quantitative Unsichtbarkeit um 1 erhöht, und wenn sie vom Polygon nicht mehr verdeckt wird, um 1 erniedrigt. Um das Sichtbarkeitsproblem zu lösen, muss die quantitative Unsichtbarkeit jedes Punkts auf jeder Kante berechnet werden; ein Punkt ist sichtbar, wenn der Wert 0 beträgt. Die Algorithmen von Loutrel^[5] und Galimberti und Montanari^[6] arbeiten sehr ähnlich.

Weiler, Atherton (1977)

Der Weiler-Atherton-Algorithmus^[7] bestimmt die Sichtbarkeit, indem er vom a priori nächstgelegenen Polygon ausgeht und alle Polygone gegen dieses Polygon clippt. Dadurch werden die Polygone entlang der Grenze vom sichtbaren und unsichtbaren Teil aufgeteilt und die unsichtbaren Teile verworfen. Am Ende liefert der Algorithmus eine Liste von sichtbaren Polygonteilen zurück.

Haloed Lines (1979)

Der Haloed-Line-Algorithmus von Appel, Rohlf und Stein^[8] arbeitet ausschließlich mit Liniensegmenten und ist nicht von den Objekten, die sich aus ihnen zusammensetzen, abhängig. Es handelt sich also um einen Algorithmus zum Sichtbarkeitsentscheid von Linien (Visible Line Determination) und nicht von Oberflächen (Visible Surface Determination). Jedes gezeichnete Liniensegment erhält auf beiden Seiten eine Kontur („Halo“), die die dahinter liegenden Linien teilweise verdeckt.

List-Priority-Verfahren

Schumacker, Brand, Gilliland, Sharp (1969)

Schumackers Algorithmus^[9] war die erste Echtzeitlösung des Sichtbarkeitsproblems und war für Flugsimulationen optimiert.^[10] Er ist nur auf konvexe Polyeder anwendbar. Der Algorithmus verwendet eine Prioritätsliste, die hauptsächlich von der Szene und kaum von der Betrachterposition abhängig ist. Aus Effizienzgründen wird die Geometrie in sogenannte Cluster zusammengefasst.

Depth Sort (1972)

Die Idee des Depth-Sort-Algorithmus von Newell, Newell und Sancha^[11] besteht darin, alle Polygone nach ihrer kleinsten z-Koordinate zu sortieren, eventuelle Uneindeutigkeiten bei überlappenden Polygonen durch Teilung der Polygone zu lösen, und schließlich jedes Polygon, beginnend mit dem hintersten, zu rastern. Eine vereinfachte Version des Algorithmus, bei der uneindeutige Fälle ignoriert werden, wird oft Maleralgorithmus genannt. Er ist nur für Anwendungen geeignet, bei denen die Objekte nicht entlang der z-Achse überlappen.

BSP-Algorithmus (1980)

Der BSP-Algorithmus von Fuchs, Kedem und Naylor^[12] ist eine Verbesserung von Schumackers Algorithmus, bei der die Zusammenfassung von Objekten in Cluster automatisiert wird. Hierzu wird ein BSP-Baum aufgebaut.

Bildraumverfahren

Scanline-Algorithmen (Ende 1960er)

Es wurden mehrere ähnliche Scanline-Algorithmen veröffentlicht.^{[13][14][15][16]} Alle diese Verfahren führen zunächst eine Sortierung entlang der y-Achse und dann entlang der x-Achse durch, um schließlich für jedes Pixel das sichtbare Polygon mit der geringsten Entfernung zum Betrachter auszuwählen. Da sich von Bildzeile zu Bildzeile die Konfiguration der Polygone nur wenig ändert, werden die für jede Bildzeile „aktiven“ Polygone in einer Liste eingetragen, die bei Bedarf aktualisiert wird.

Raytracing (Ende 1960er)

Der Raytracing-Algorithmus, veröffentlicht durch Appel, Goldstein und Nagel^[17][18][19], basiert auf der „Aussendung“ von Strahlen vom Beobachter aus, die durch die Bildebene in die Szene geschickt werden. Jeder Strahl wird gegen alle Primitiven getestet und gegebenenfalls die Entfernung berechnet. Das sichtbare Objekt ist dasjenige mit der geringsten Entfernung. Für den Raytracing-Algorithmus sind zahlreiche Beschleunigungstechniken entwickelt worden, die die Zahl der zu testenden Objekte drastisch reduzieren. Raycasting ist eine eingeschränkte Variante von Raytracing, die sich nur für Szenen eignet, die aus an den Achsen ausgerichteten, gleich hohen Rechtecken bestehen.

Warnock (1968)

Der Warnock-Algorithmus^[20] basiert auf der Annahme, dass das Bild in rechteckige Regionen unterteilt werden kann, in denen höchstens ein Polygon den Bildinhalt bestimmt. Ist dies in einer Region nicht der Fall, so wird sie unterteilt. Die Unterteilung setzt sich so lange rekursiv fort, bis die Regionen nur noch ein Pixel einschließen.

Z-Buffer (1974)

Edwin Catmulls sehr einfacher Z-Buffer-Algorithmus^[21] speichert für jedes Pixel eine zusätzliche Tiefeninformation. Beim Rastern jedes Objekts wird der Pixel-Farbwert sowie der Wert im Z-Buffer aktualisiert, wenn die Entfernung des entsprechenden Punkts des Objekts geringer als der aktuelle Z-Buffer-Wert ist.

Implementierungen

Die bekanntesten Ansätze zur Lösung des Sichtbarkeitsproblems in der 3D-Computergrafik, besonders im Hinblick auf Performance, sind das Culling und die Verwendung eines Z-Buffers.

Literatur

• Max Agoston: Computer Graphics and Geometric Modeling: Implementation and Algorithms. Springer, London 2005, ISBN 1-85233-818-0
• 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
• Alan Watt: 3D Computer Graphics. Addison-Wesley, Harlow 2000, ISBN 0-201-39855-9