www.wikidata.de-de.nina.az

Sichtbarkeitsproblem Das ist beim Rendern in der Computergrafik die Fragestellung welche Teile von Oberflächen in einer

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 Bearbeiten

Nach Ivan Sutherland können Algorithmen zur Verdeckungsberechnung in Objektraumverfahren, Bildraumverfahren und List-Priority-Verfahren eingeteilt werden. 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 Bearbeiten

List-Priority-Verfahren Bearbeiten

Bildraumverfahren Bearbeiten

Implementierungen Bearbeiten

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 Bearbeiten

  • 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 Bearbeiten

  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 Hidden-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
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Das Sichtbarkeitsproblem ist beim Rendern in der Computergrafik die Fragestellung welche Teile von Oberflachen in einer 3D Szene bei der Projektion auf die zweidimensionale Anzeigeflache sichtbar sind Als Verdeckungsberechnung oder Sichtbarkeitsentscheid wird dementsprechend ein Vorgehen bezeichnet mit dem nicht sichtbare Oberflachen erkannt und aussortiert werden und so das Sichtbarkeitsproblem gelost 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 Oberflachen die fur den Betrachter nicht sichtbar sind auch nicht dargestellt werden sollten Viele Verfahren beschleunigen zusatzlich das Rendern weil nicht sichtbare Oberflachen von der weiteren Verarbeitung durch die Grafikpipeline ausgeschlossen werden konnen Inhaltsverzeichnis 1 Verfahren 1 1 Objektraumverfahren 1 2 List Priority Verfahren 1 3 Bildraumverfahren 1 4 Implementierungen 2 Literatur 3 EinzelnachweiseVerfahren BearbeitenNach Ivan Sutherland konnen Algorithmen zur Verdeckungsberechnung in Objektraumverfahren Bildraumverfahren und List Priority Verfahren eingeteilt werden 1 Wahrend bei den Objektraumverfahren die Sichtbarkeiten direkt anhand der Objekte analytisch und unabhangig vom Ausgabegerat berechnet werden wird bei den Bildraumverfahren die Verdeckungsberechnung fur jede einzelne Bild oder Pixelposition separat durchgefuhrt List Priority Algorithmen berechnen zunachst anhand der Objekte eine Sichtbarkeitsreihenfolge oder Prioritat im Voraus und farben anschliessend 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 haufig Raytracing verwendet Fur ein verwandtes Problem siehe Sichtbarkeitspolygon Objektraumverfahren Bearbeiten 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 vollstandig verdeckt wird Dieser Test wird durchgefuhrt indem ein lineares Gleichungsproblem gelost wird Roberts Algorithmus funktioniert nur mit konvexen Polyedern Appel Loutrel Galimberti Montanari 1967 69 Appels Algorithmus 4 steht stellvertretend fur eine Klasse von Algorithmen die die sichtbaren Kantensegmente ermitteln Im Unterschied zum Roberts Algorithmus konnen sie auch die Verdeckung durch einzelne Polygone nicht nur durch ganze Polyeder berechnen Appel definiert die quantitative Unsichtbarkeit eines Punkts als die Anzahl massgeblicher Polygone die ihn verdecken Wenn eine Kante hinter ein verdeckendes Polygon gleitet wird die quantitative Unsichtbarkeit um 1 erhoht und wenn sie vom Polygon nicht mehr verdeckt wird um 1 erniedrigt Um das Sichtbarkeitsproblem zu losen muss die quantitative Unsichtbarkeit jedes Punkts auf jeder Kante berechnet werden ein Punkt ist sichtbar wenn der Wert 0 betragt Die Algorithmen von Loutrel 5 und Galimberti und Montanari 6 arbeiten sehr ahnlich Weiler Atherton 1977 Der Weiler Atherton Algorithmus 7 bestimmt die Sichtbarkeit indem er vom a priori nachstgelegenen 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 zuruck Haloed Lines 1979 Der Haloed Line Algorithmus von Appel Rohlf und Stein 8 arbeitet ausschliesslich mit Liniensegmenten und ist nicht von den Objekten die sich aus ihnen zusammensetzen abhangig Es handelt sich also um einen Algorithmus zum Sichtbarkeitsentscheid von Linien Visible Line Determination und nicht von Oberflachen Visible Surface Determination Jedes gezeichnete Liniensegment erhalt auf beiden Seiten eine Kontur Halo die die dahinter liegenden Linien teilweise verdeckt List Priority Verfahren Bearbeiten Schumacker Brand Gilliland Sharp 1969 Schumackers Algorithmus 9 war die erste Echtzeitlosung des Sichtbarkeitsproblems und war fur Flugsimulationen optimiert 10 Er ist nur auf konvexe Polyeder anwendbar Der Algorithmus verwendet eine Prioritatsliste die hauptsachlich von der Szene und kaum von der Betrachterposition abhangig ist Aus Effizienzgrunden 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 uberlappenden Polygonen durch Teilung der Polygone zu losen und schliesslich jedes Polygon beginnend mit dem hintersten zu rastern Eine vereinfachte Version des Algorithmus bei der uneindeutige Falle ignoriert werden wird oft Maleralgorithmus genannt Er ist nur fur Anwendungen geeignet bei denen die Objekte nicht entlang der z Achse uberlappen 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 Bearbeiten Scanline Algorithmen Ende 1960er Es wurden mehrere ahnliche Scanline Algorithmen veroffentlicht 13 14 15 16 Alle diese Verfahren fuhren zunachst eine Sortierung entlang der y Achse und dann entlang der x Achse durch um schliesslich fur jedes Pixel das sichtbare Polygon mit der geringsten Entfernung zum Betrachter auszuwahlen Da sich von Bildzeile zu Bildzeile die Konfiguration der Polygone nur wenig andert werden die fur jede Bildzeile aktiven Polygone in einer Liste eingetragen die bei Bedarf aktualisiert wird Raytracing Ende 1960er Der Raytracing Algorithmus veroffentlicht 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 Fur den Raytracing Algorithmus sind zahlreiche Beschleunigungstechniken entwickelt worden die die Zahl der zu testenden Objekte drastisch reduzieren Raycasting ist eine eingeschrankte Variante von Raytracing die sich nur fur 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 hochstens 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 einschliessen Z Buffer 1974 Edwin Catmulls sehr einfacher Z Buffer Algorithmus 21 speichert fur jedes Pixel eine zusatzliche 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 Bearbeiten Die bekanntesten Ansatze zur Losung des Sichtbarkeitsproblems in der 3D Computergrafik besonders im Hinblick auf Performance sind das Culling und die Verwendung eines Z Buffers Literatur BearbeitenMax 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 9Einzelnachweise Bearbeiten Ivan Sutherland u a A Characterization of Ten Hidden Surface Algorithms ACM Computing Surveys CSUR 6 1 March 1974 1 55 ISSN 0360 0300 Lawrence Roberts Machine Perception Of Three Dimensional Solids Lincoln Laboratory TR 315 MIT Cambridge 1963 Online Rogers Procedural Elements for Computer Graphics S 303 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 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 R Galimberti U Montanari An Algorithm for Hidden Line Elimination Communications of the ACM 12 4 April 1969 206 211 ISSN 0001 0782 Kevin Weiler Peter Atherton Hidden Surface Removal Using Polygon Area Sorting ACM SIGGRAPH Computer Graphics 11 2 Summer 1977 214 222 ISSN 0097 8930 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 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 Ivan Sutherland u a A Characterization of Ten Hidden Surface Algorithms S 23 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 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 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 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 Gary Scott Watkins A Real Time Visible Surface Algorithm Dissertation University of Utah 1970 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 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 Mathematical Applications Group Inc 3 D Simulated Graphics Offered by Service Bureau Datamation 13 1 Feb 1968 69 ISSN 0011 6963 Robert Goldstein Roger Nagel 3 D Visual Simulation Simulation 16 1 Jan 1971 25 31 ISSN 0037 5497 John Warnock A Hidden 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 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 Abgerufen von https de wikipedia org w index php title Sichtbarkeitsproblem amp oldid 212709776