Verdeckungsberechnung

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.

Beim Rendern in der Computergrafik ist das Sichtbarkeitsproblem 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.

Die Verdeckungsberechnung ist zum korrekten Rendern einer 3D-Szene notwendig, weil Oberflächen, die vom 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 den Z-Buffer; bei der realistischen Bildsynthese wird häufig Raytracing verwendet.

Objektraumverfahren

Roberts (1963)

Von Roberts^[2] stammt das erste bekannte Verfahren zur Verdeckungsberechnung.^[3] Roberts’ Algorithmus testet jede Polygonkante gegen jedes Polyeder, um zu testen, 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.

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

Einzelnachweise

1. ↑ Ivan Sutherland u. a.: A Characterization of Ten Hidden-Surface Algorithms. ACM Computing Surveys (CSUR) 6, 1 (March 1974): 1–55, ISSN 0360-0300
2. ↑ Lawrence Roberts: Machine Perception Of Three-Dimensional Solids. Lincoln Laboratory, TR 315, MIT, Cambridge 1963 (Online)
3. ↑ Rogers: Procedural Elements for Computer Graphics, S. 303
4. ↑ Arthur Appel: The Notion of Quantitative Invisibility and the Machine Rendering of Solids. In Proceedings of the 1967 22nd ACM Annual Conference. S. 387–393. ACM, New York 1967
5. ↑ Philippe Paul Loutrel: A Solution to the Hidden-Line Problem for Computer-Drawn Polyhedra. Department of Electrical Engineering, New York University, Technical Report 400-167, 1967
6. ↑ R. Galimberti, U. Montanari: An Algorithm for Hidden Line Elimination. Communications of the ACM 12, 4 (April 1969): 206–211, ISSN 0001-0782
7. ↑ Kevin Weiler, Peter Atherton: Hidden Surface Removal Using Polygon Area Sorting. ACM SIGGRAPH Computer Graphics 11, 2 (Summer 1977): 214−222, ISSN 0097-8930
8. ↑ 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
9. ↑ R. A. Schumaker u. a.: Study for Applying Computer-Generated Images to Visual Simulation. AFHRL-TR-69-14. US Air Force Human Resources Laboratory, 1969
10. ↑ Ivan Sutherland u. a.: A Characterization of Ten Hidden-Surface Algorithms, S. 23
11. ↑ M. E. Newell u. a.: A Solution to the Hidden Surface Problem. In Proceedings of the ACM Annual Conference 1972 – Volume 1. ACM, New York 1972
12. ↑ Henry Fuchs u. a.: On Visible Surface Generation by A Priori Tree Structures. In SIGGRAPH ’80 Proceedings, S. 124–133. ACM, New York 1980, ISBN 0-89791-021-4
13. ↑ Jack Bouknight: A procedure for generation of three-dimensional half-toned computer graphics presentations. Communications of the ACM 13, 9 (Sep. 1970): 527–536, ISSN 0001-0782
14. ↑ Jack Bouknight, K. Kelley: An algorithm for producing half-tone computer graphics presentations with shadows and movable light sources. In AFIPS Conference Proceedings, vol. 36: 1970 Fall Joint Computer Conference. S. 1–10. AFIPS Press, Montvale 1970
15. ↑ Gary Scott Watkins: A Real Time Visible Surface Algorithm. Dissertation, University of Utah 1970
16. ↑ C. Wylie u. a.: Halftone Perspective Drawings by Computer. In AFIPS Conference Proceedings, vol. 31: 1967 Fall Joint Computer Conference. S. 49–58. AFIPS Press, Montvale 1967
17. ↑ Arthur Appel: Some Techniques for Shading Machine Renderings of Solids. In Proceedings of the Spring Joint Computer Conference 1968. S. 37–45. AFIPS Press, Arlington
18. ↑ Mathematical Applications Group, Inc.: 3-D Simulated Graphics Offered by Service Bureau. Datamation 13, 1 (Feb. 1968): 69, ISSN 0011-6963
19. ↑ Robert Goldstein, Roger Nagel: 3-D Visual Simulation. Simulation 16, 1 (Jan. 1971): 25–31, ISSN 0037-5497
20. ↑ John Warnock: A Hiddden-Surface Algorithm for Computer Generated Half-Tone Pictures. Technical Report TR 4-15, NTIS AD-753 671, Computer Graphics Department, University of Utah, Salt Lake City 1969
21. ↑ Edwin Catmull: A Subdivision Algorithm for Computer Display of Curved Surfaces. Dissertation, Report UTEC-CSc-74-133, Computer Science Department, University of Utah, Salt Lake City 1974