www.wikidata.de-de.nina.az

Rasterung Der Titel dieses Artikels ist mehrdeutig Für den Begriff in der Drucktechnik siehe Druckraster In der 2D Compu

Rasterung

In der 2D-Computergrafik bezeichnet Rasterung (von „Raster“: auf der Fläche verteilte regelmäßige Muster), auch Rendern oder Scankonvertierung genannt, die Umwandlung einer Vektor- in eine Rastergrafik.

Bei der Rasterung einer Vektorgrafik, in diesem Beispiel im SVG-Format, müssen die Pixel-Farbwerte der resultierenden Rastergrafik ermittelt werden.

Verfahren Bearbeiten

PDF-Renderer, der Vektorschrift in Pixelgrafik umsetzt. Oben Sumatra PDF, unten Adobe Reader.

Es gibt eine Vielzahl von Algorithmen zur Rasterung von grafischen Primitiven, wie Linien, Polygonen, Kreisen und anderen geometrischen Formen, siehe dazu:

Ein bekanntes Problem der Rasterung ist der Treppeneffekt. Steht für die zu erzeugende Rastergrafik eine Farbtiefe von mehr als 1 Bit pro Pixel zur Verfügung, so kann dieser Effekt mittels Kantenglättung (Antialiasing) vermindert werden. Dazu gibt es mehrere Methoden, die teils ungewichtet arbeiten, teils einen speziellen Rekonstruktionsfilter verwenden. Bei der Rasterung von Text treten spezielle Probleme auf, die mittels Hinting vermieden werden können.

Rasterung dicker Primitiven Bearbeiten

Bei der Rasterung von grafischen Primitiven mit einer bestimmten Dicke gibt es, sofern sie nicht bereits vom verwendeten Antialiasing-Algorithmus unterstützt wird, mehrere Möglichkeiten. Bei Polygonen müssen hierbei auch die Verbindungsstellen zwischen den einzelnen Liniensegmenten beachtet werden, siehe hierzu Rasterung von Polygonen.

Löschung von Primitiven Bearbeiten

Bereits gezeichnete Figuren können selektiv gelöscht werden, indem sie nochmals mit der Hintergrundfarbe gezeichnet werden. Das funktioniert jedoch nicht, wenn sie andere Figuren überschneiden, da hierbei auch unerwünschte Bildteile gelöscht werden können. Eine effiziente Möglichkeit, dies zu vermeiden, sind Minimax- oder Boxing-Tests. Hierbei wird zunächst geprüft, ob sich in dem von der zu löschenden Figur aufgespannten Rechteck andere Figuren befinden. Nur wenn dies der Fall ist, muss auf Schnittpunkte getestet und gegebenenfalls der gesamte Bereich neu gezeichnet werden.

3D-Rasterung Bearbeiten

Raytracing und Rasterung sind zwei grundlegend unterschiedliche Ansätze zum Rendern von Bildern von 3D-Szenen, obwohl sie für Primärstrahlen dieselben Ergebnisse berechnen. Durch die Rasterung wird jedes Dreieck auf die Bildebene projiziert und alle abgedeckten Pixel in 2D aufgelistet. Die Strahlverfolgung wird dabei in 3D ausgeführt, indem Strahlen durch jedes Pixel erzeugt und dann der nächstgelegene Schnittpunkt mit einem Dreieck gefunden wird.

Man kann die Anwendung einer Modell- oder Ansichtstransformation vermeiden, indem man stattdessen den Sampler-Generator transformiert. Während beim Raytracing normalerweise Gleitkommazahlen mit ihren numerischen Problemen verwendet werden, kann 3D-Rasterung mit denselben Konsistenzregeln wie die 2D-Rasterung implementiert werden. Bei der 3D-Rasterung bestehen die einzigen verbleibenden Unterschiede zwischen den beiden Ansätzen in der Szenenüberquerung und der Aufzählung potenziell abgedeckter Samples auf der Bildebene (siehe Binning).

Berechnungen Bearbeiten

Bild 2: Der Normalenvektor ist orthogonal zum Dreieck .
Bild 1: Projektionszentrum als Koordinatenursprung des dreidimensionalen kartesischen Koordinatensystems mit dem Pixel , das in der Bildebene liegt, und dem Dreieck .
Bild 3: Das Pixel muss in bestimmten durch die Dreiecke , und definierten Halbräumen liegen.
Bild 4: Lage des Schnittpunkts im Dreieck .

Um herauszufinden, ob ein Pixel der Bildebene von einem Dreieck bedeckt wird, reicht es, zu prüfen, ob der Projektionsstrahl (siehe Zentralprojektion), der durch das Pixel verläuft, das Dreieck schneidet.

Nimmt man an, dass das Projektionszentrum der Koordinatenursprung des dreidimensionalen kartesischen Koordinatensystems ist, und bezeichnet die Ecken des projizierten Dreiecks mit , , (Bild 1), dann ergibt sich folgende Bedingungen dafür, dass das Pixel im projizierten Dreieck liegt (Bild 3):

  • Die Ebene, die durch das Dreieck verläuft, teilt den dreidimensionalen Raum in zwei Halbräume. Das Pixel der Bildebene muss in dem Halbraum liegen, in dem sich der Punkt befindet. Außerdem muss das Pixel
  • in dem durch das Dreieck definierten Halbraum liegen, in dem sich der Punkt befindet und
  • in dem durch das Dreieck definierten Halbraum liegen, in dem sich der Punkt befindet.

Um zu prüfen, ob sich ein Punkt in einem durch die Punkte , und definierten Halbraum befindet, kann man folgende Funktion verwenden:

wobei das Skalarprodukt der Vektoren und ist. Der Normalenvektor ist durch das Kreuzprodukt

definiert und ist orthogonal zum Dreieck . Diese Funktion berechnet das Volumen des Tetraders mit den Ecken , , , . Wenn der Punkt oberhalb des Dreiecks liegt, ist das Vorzeichen positiv, wenn unterhalb liegt, ist das Vorzeichen negativ. Wenn in der Ebene des Dreiecks liegt, ist das Volumen gleich 0.

Mit den Funktionen

kann folgende Aussage formuliert werden:

  • Das Pixel liegt genau dann im projizierten Dreieck, wenn und und ist.

Der Schnittpunkt des Pixels mit dem ursprünglichen Dreieck kann auch mit baryzentrischen Koordinaten der Punkte , , ausgedrückt werden (Bild 4). Dann gilt:

wobei und die reelle Zahlen sind. Die baryzentrischen Koordinaten werden mit bezeichnet.

Algorithmen Bearbeiten

Sobald ein Dreieck zum Rendern ausgewählt wurde, müssen die Strahlen, die es abdeckt, effizient identifiziert werden. Bei der herkömmlichen Strahlverfolgung werden nur Dreiecke, die wahrscheinlich geschnitten werden, durch die Durchquerung aufgelistet. Bei größeren Bildausschnitten kann ein Dreieck jedoch nur einen kleinen Teil der Pixel bedecken, und es kann vorteilhaft sein, Binning zu verwenden, um das Auffinden der bedeckten Pixel zu beschleunigen. Aus dem gleichen Grund wurde bei der Rasterung immer das Binning verwendet, um die abgedeckten Pixel schnell auf dem Bildschirm zu lokalisieren.

Eine generische Formulierung von kombiniertem Durchlaufen und Binning zeigt folgende rekursive Funktion, die in Pseudocode dargestellt ist: 

funktion durchlaufen(bildausschnitt F, knoten N) falls istVerdeckt oder istAuszerhalb dann stop falls bildausschnittTeilen dann teile F in teilausschnitte F[i] für jeden teilausschnitt F[i] durchlaufen(F[i], N) ende sonst falls pixelErzeugen dann rastern(N, binning) sonst für jeden nachfolger_von_N durchlaufen(F, nachfolger_von_N) ende ende durchlaufen(F, nachfolger_von_N)

Hier ist F ein Bildausschnitt und N ist ein Knoten der räumlichen Indexstruktur, der typischerweise mit dem gesamten Ansichtsfenster bzw. dem Wurzelknoten beginnt. Die kursiven Wörter istVerdeckt, istAuszerhalb, bildausschnittTeilen, pixelErzeugen, istAuszerhalb und binning bezeichnen Testfunktionen, die das Verhalten des Algorithmus steuern und es uns ermöglichen, die oben genannten Rendering-Algorithmen zu produzieren und neue Wege zu erkunden.

Literatur 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

Weblinks Bearbeiten

Commons: Rasterung – Sammlung von Bildern, Videos und Audiodateien
  • Archiviert vom Original am 6. August 2016; abgerufen am 9. November 2017.

Einzelnachweise Bearbeiten

  1. Hans F. Ebel, Claus Bliefert: Vortragen in Naturwissenschaft, Technik und Medizin. 1991; 2., bearbeitete Auflage 1994, VCH, Weinheim ISBN 3-527-30047-3, S. 302.
  2. John D. Hobby: Digitized Brush Trajectories. Dissertation, Stanford University, 1985 ( (Memento vom 26. Oktober 2006 im Internet Archive))
  3. ↑ 3D Rasterization: A Bridge between Rasterization and Ray Casting
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:
Der Titel dieses Artikels ist mehrdeutig Fur den Begriff in der Drucktechnik siehe Druckraster In der 2D Computergrafik bezeichnet Rasterung von Raster auf der Flache verteilte regelmassige Muster 1 auch Rendern oder Scankonvertierung genannt die Umwandlung einer Vektor in eine Rastergrafik Bei der Rasterung einer Vektorgrafik in diesem Beispiel im SVG Format mussen die Pixel Farbwerte der resultierenden Rastergrafik ermittelt werden Inhaltsverzeichnis 1 Verfahren 2 Rasterung dicker Primitiven 3 Loschung von Primitiven 4 3D Rasterung 4 1 Berechnungen 4 2 Algorithmen 5 Literatur 6 Weblinks 7 EinzelnachweiseVerfahren Bearbeiten nbsp PDF Renderer der Vektorschrift in Pixelgrafik umsetzt Oben Sumatra PDF unten Adobe Reader Es gibt eine Vielzahl von Algorithmen zur Rasterung von grafischen Primitiven wie Linien Polygonen Kreisen und anderen geometrischen Formen siehe dazu Rasterung von Linien Rasterung von Polygonen Rasterung von KreisenEin bekanntes Problem der Rasterung ist der Treppeneffekt Steht fur die zu erzeugende Rastergrafik eine Farbtiefe von mehr als 1 Bit pro Pixel zur Verfugung so kann dieser Effekt mittels Kantenglattung Antialiasing vermindert werden Dazu gibt es mehrere Methoden die teils ungewichtet arbeiten teils einen speziellen Rekonstruktionsfilter verwenden Bei der Rasterung von Text treten spezielle Probleme auf die mittels Hinting vermieden werden konnen Rasterung dicker Primitiven BearbeitenBei der Rasterung von grafischen Primitiven mit einer bestimmten Dicke gibt es sofern sie nicht bereits vom verwendeten Antialiasing Algorithmus unterstutzt wird mehrere Moglichkeiten Bei Polygonen mussen hierbei auch die Verbindungsstellen zwischen den einzelnen Liniensegmenten beachtet werden siehe hierzu Rasterung von Polygonen Pixelwiederholung Eine Methode ist bei der Rasterung anstatt eines mehrere Pixel vertikal bzw horizontal zu zeichnen Ein Problem ist dass Kurvenenden bei dicken Kurven abgeschnitten wirken Daneben kann es an den Stellen an denen von horizontaler zu vertikaler Wiederholung oder umgekehrt gewechselt wird zu merklichen Lucken kommen Ausserdem weisen derartig gerasterte Kurven ahnlich wie dunne Linien eine unterschiedliche Dicke in Abhangigkeit von der lokalen Steigung auf Pinsel Hierbei wird eine bestimmte Rastergrafik als Pinsel im einfachsten Fall ein Quadrat mit gewunschter Kantenlange entlang der Kurve bewegt Auch hier variiert die Dicke in Abhangigkeit von der Steigung im Gegensatz zur Pixelwiederholung ist die Linie jedoch bei Diagonalschritten am dicksten Dieses Problem lasst sich dadurch umgehen dass das Quadrat gemass der lokalen Steigung der Kurve gedreht wird einfacher ist es jedoch einen Kreis als Pinsel zu verwenden Ein Nachteil der Methode ist dass man bei der Rasterung auf sehr viele bereits in den vorhergehenden Schritten eingefarbte Pixel stosst Dieser Effekt ist umso grosser je dicker die Kurve ist Um das Problem der variierenden Kurvendicke zu losen konnen polygonformige Pinsel verwendet werden 2 Fullen zwischen Randern Eine andere Methode zur Rasterung einer dicken Kurve besteht darin ihre beiden Rander in einigem Abstand voneinander zu zeichnen und den dazwischen liegenden Bereich auszufullen Ein Nachteil ist dass bei der zweifarbigen Rasterung die Kurve wegen Rundungsfehlern moglicherweise etwas verschoben erscheint Bei Ellipsen muss beachtet werden dass die Rasterung durch das Zeichnen zweier konfokaler Ellipsen mit unterschiedlich langen Halbachsen geometrisch nicht korrekt ist Liniensegmente Schliesslich gibt es die Moglichkeit dicke Kurven durch eine Aneinanderreihung kurzer Liniensegmente zu zeichnen Dabei mussen die gleichen Besonderheiten wie bei der Rasterung von Polygonen beachtet werden damit die Liniensegmente korrekt miteinander verbunden werden Loschung von Primitiven BearbeitenBereits gezeichnete Figuren konnen selektiv geloscht werden indem sie nochmals mit der Hintergrundfarbe gezeichnet werden Das funktioniert jedoch nicht wenn sie andere Figuren uberschneiden da hierbei auch unerwunschte Bildteile geloscht werden konnen Eine effiziente Moglichkeit dies zu vermeiden sind Minimax oder Boxing Tests Hierbei wird zunachst gepruft ob sich in dem von der zu loschenden Figur aufgespannten Rechteck andere Figuren befinden Nur wenn dies der Fall ist muss auf Schnittpunkte getestet und gegebenenfalls der gesamte Bereich neu gezeichnet werden 3D Rasterung BearbeitenRaytracing und Rasterung sind zwei grundlegend unterschiedliche Ansatze zum Rendern von Bildern von 3D Szenen obwohl sie fur Primarstrahlen dieselben Ergebnisse berechnen Durch die Rasterung wird jedes Dreieck auf die Bildebene projiziert und alle abgedeckten Pixel in 2D aufgelistet Die Strahlverfolgung wird dabei in 3D ausgefuhrt indem Strahlen durch jedes Pixel erzeugt und dann der nachstgelegene Schnittpunkt mit einem Dreieck gefunden wird Man kann die Anwendung einer Modell oder Ansichtstransformation vermeiden indem man stattdessen den Sampler Generator transformiert Wahrend beim Raytracing normalerweise Gleitkommazahlen mit ihren numerischen Problemen verwendet werden kann 3D Rasterung mit denselben Konsistenzregeln wie die 2D Rasterung implementiert werden Bei der 3D Rasterung bestehen die einzigen verbleibenden Unterschiede zwischen den beiden Ansatzen in der Szenenuberquerung und der Aufzahlung potenziell abgedeckter Samples auf der Bildebene siehe Binning 3 Berechnungen Bearbeiten nbsp Bild 2 Der Normalenvektor n 2 displaystyle vec n 2 nbsp ist orthogonal zum Dreieck e p 1 p 0 displaystyle vec e vec p 1 vec p 0 nbsp nbsp Bild 1 Projektionszentrum e displaystyle vec e nbsp als Koordinatenursprung des dreidimensionalen kartesischen Koordinatensystems mit dem Pixel d displaystyle vec d nbsp das in der Bildebene liegt und dem Dreieck p 0 p 1 p 2 displaystyle vec p 0 vec p 1 vec p 2 nbsp nbsp Bild 3 Das Pixel d displaystyle vec d nbsp muss in bestimmten durch die Dreiecke e p 1 p 0 displaystyle vec e vec p 1 vec p 0 nbsp e p 2 p 1 displaystyle vec e vec p 2 vec p 1 nbsp und e p 0 p 2 displaystyle vec e vec p 0 vec p 2 nbsp definierten Halbraumen liegen nbsp Bild 4 Lage des Schnittpunkts e t d displaystyle vec e t cdot vec d nbsp im Dreieck p 0 p 1 p 2 displaystyle vec p 0 vec p 1 vec p 2 nbsp Um herauszufinden ob ein Pixel der Bildebene von einem Dreieck bedeckt wird reicht es zu prufen ob der Projektionsstrahl siehe Zentralprojektion der durch das Pixel verlauft das Dreieck schneidet Nimmt man an dass das Projektionszentrum e displaystyle vec e nbsp der Koordinatenursprung des dreidimensionalen kartesischen Koordinatensystems ist und bezeichnet die Ecken des projizierten Dreiecks mit p 0 displaystyle vec p 0 nbsp p 1 displaystyle vec p 1 nbsp p 2 displaystyle vec p 2 nbsp Bild 1 dann ergibt sich folgende Bedingungen dafur dass das Pixel d displaystyle vec d nbsp im projizierten Dreieck liegt Bild 3 Die Ebene die durch das Dreieck e p 1 p 0 displaystyle vec e vec p 1 vec p 0 nbsp verlauft teilt den dreidimensionalen Raum in zwei Halbraume Das Pixel der Bildebene muss in dem Halbraum liegen in dem sich der Punkt p 2 displaystyle vec p 2 nbsp befindet Ausserdem muss das Pixel in dem durch das Dreieck e p 2 p 1 displaystyle vec e vec p 2 vec p 1 nbsp definierten Halbraum liegen in dem sich der Punkt p 0 displaystyle vec p 0 nbsp befindet und in dem durch das Dreieck e p 0 p 2 displaystyle vec e vec p 0 vec p 2 nbsp definierten Halbraum liegen in dem sich der Punkt p 1 displaystyle vec p 1 nbsp befindet Um zu prufen ob sich ein Punkt p displaystyle vec p nbsp in einem durch die Punkte a displaystyle vec a nbsp b displaystyle vec b nbsp und c displaystyle vec c nbsp definierten Halbraum befindet kann man folgende Funktion verwenden V p n p b a c b p displaystyle V vec p vec n cdot vec p vec b vec a times vec c vec b cdot vec p nbsp wobei n p displaystyle vec n cdot vec p nbsp das Skalarprodukt der Vektoren n displaystyle vec n nbsp und p displaystyle vec p nbsp ist Der Normalenvektor n displaystyle vec n nbsp ist durch das Kreuzprodukt n b a c b displaystyle vec n vec b vec a times vec c vec b nbsp definiert und ist orthogonal zum Dreieck a b c displaystyle vec a vec b vec c nbsp Diese Funktion berechnet das Volumen des Tetraders mit den Ecken a displaystyle vec a nbsp b displaystyle vec b nbsp c displaystyle vec c nbsp p displaystyle vec p nbsp Wenn der Punkt p displaystyle vec p nbsp oberhalb des Dreiecks a b c displaystyle vec a vec b vec c nbsp liegt ist das Vorzeichen positiv wenn p displaystyle vec p nbsp unterhalb liegt ist das Vorzeichen negativ Wenn p displaystyle vec p nbsp in der Ebene des Dreiecks a b c displaystyle vec a vec b vec c nbsp liegt ist das Volumen gleich 0 Mit den Funktionen V 0 d p 2 e p 1 p 2 displaystyle V 0 vec d vec p 2 vec e times vec p 1 vec p 2 nbsp V 1 d p 0 e p 2 p 0 displaystyle V 1 vec d vec p 0 vec e times vec p 2 vec p 0 nbsp V 2 d p 1 e p 0 p 1 displaystyle V 2 vec d vec p 1 vec e times vec p 0 vec p 1 nbsp kann folgende Aussage formuliert werden Das Pixel d displaystyle vec d nbsp liegt genau dann im projizierten Dreieck wenn V 0 d gt 0 displaystyle V 0 vec d gt 0 nbsp und V 1 d gt 0 displaystyle V 1 vec d gt 0 nbsp und V 2 d gt 0 displaystyle V 2 vec d gt 0 nbsp ist Der Schnittpunkt e t d displaystyle vec e t cdot vec d nbsp des Pixels d displaystyle vec d nbsp mit dem ursprunglichen Dreieck p 0 p 1 p 2 displaystyle vec p 0 vec p 1 vec p 2 nbsp kann auch mit baryzentrischen Koordinaten der Punkte p 0 displaystyle vec p 0 nbsp p 1 displaystyle vec p 1 nbsp p 2 displaystyle vec p 2 nbsp ausgedruckt werden Bild 4 Dann gilt e t d t d l 0 p 0 l 1 p 1 l 2 p 2 displaystyle vec e t cdot vec d t cdot vec d lambda 0 cdot vec p 0 lambda 1 cdot vec p 1 lambda 2 cdot vec p 2 nbsp mit l i V i d V 0 d V 1 d V 2 d displaystyle lambda i frac V i vec d V 0 vec d V 1 vec d V 2 vec d nbsp wobei t displaystyle t nbsp und die l i displaystyle lambda i nbsp reelle Zahlen sind Die baryzentrischen Koordinaten werden mit e t d l 0 l 1 l 2 displaystyle vec e t cdot vec d lambda 0 lambda 1 lambda 2 nbsp bezeichnet 3 Algorithmen Bearbeiten Sobald ein Dreieck zum Rendern ausgewahlt wurde mussen die Strahlen die es abdeckt effizient identifiziert werden Bei der herkommlichen Strahlverfolgung werden nur Dreiecke die wahrscheinlich geschnitten werden durch die Durchquerung aufgelistet Bei grosseren Bildausschnitten kann ein Dreieck jedoch nur einen kleinen Teil der Pixel bedecken und es kann vorteilhaft sein Binning zu verwenden um das Auffinden der bedeckten Pixel zu beschleunigen Aus dem gleichen Grund wurde bei der Rasterung immer das Binning verwendet um die abgedeckten Pixel schnell auf dem Bildschirm zu lokalisieren Eine generische Formulierung von kombiniertem Durchlaufen und Binning zeigt folgende rekursive Funktion die in Pseudocode dargestellt ist funktion durchlaufen bildausschnitt F knoten N falls istVerdeckt oder istAuszerhalb dann stop falls bildausschnittTeilen dann teile F in teilausschnitte F i fur jeden teilausschnitt F i durchlaufen F i N ende sonst falls pixelErzeugen dann rastern N binning sonst fur jeden nachfolger von N durchlaufen F nachfolger von N ende ende durchlaufen F nachfolger von N Hier ist F ein Bildausschnitt und N ist ein Knoten der raumlichen Indexstruktur der typischerweise mit dem gesamten Ansichtsfenster bzw dem Wurzelknoten beginnt Die kursiven Worter istVerdeckt istAuszerhalb bildausschnittTeilen pixelErzeugen istAuszerhalb und binning bezeichnen Testfunktionen die das Verhalten des Algorithmus steuern und es uns ermoglichen die oben genannten Rendering Algorithmen zu produzieren und neue Wege zu erkunden 3 Literatur BearbeitenJames 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 5Weblinks Bearbeiten nbsp Commons Rasterung Sammlung von Bildern Videos und Audiodateien Grundlagen der Computergrafik Rasterisierung Archiviert vom Original am 6 August 2016 abgerufen am 9 November 2017 Einzelnachweise Bearbeiten Hans F Ebel Claus Bliefert Vortragen in Naturwissenschaft Technik und Medizin 1991 2 bearbeitete Auflage 1994 VCH Weinheim ISBN 3 527 30047 3 S 302 John D Hobby Digitized Brush Trajectories Dissertation Stanford University 1985 PDF 30 MB Memento vom 26 Oktober 2006 im Internet Archive a b c 3D Rasterization A Bridge between Rasterization and Ray Casting Abgerufen von https de wikipedia org w index php title Rasterung amp oldid 233319180