imported>Maximum 2520: /* Berechnungen */ Erklärung verbessert, Reihenfolge der Bilder 2 und 3 geändert, Bezug zu Bild 3 hergestellt

2026-03-09T19:16:29Z

Berechnungen: Erklärung verbessert, Reihenfolge der Bilder 2 und 3 geändert, Bezug zu Bild 3 hergestellt

Neue Seite

{{Begriffsklärungshinweis|Für den Begriff in der Drucktechnik siehe [[Druckraster]].}}

[[Datei:Scan-conversion.svg|mini|hochkant=2.1|Bei der Rasterung einer [[Vektorgrafik]], in diesem Beispiel im [[Scalable Vector Graphics|SVG]]-Format, müssen die Pixel-Farbwerte der resultierenden [[Rastergrafik]] ermittelt werden.]]

In der 2D-[[Computergrafik]] bezeichnet '''Rasterung''' (von „Raster“: auf der Fläche verteilte regelmäßige Muster<ref>[[Hans Friedrich Ebel|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.</ref>), auch ''Rendern'' oder ''Scankonvertierung'' genannt, die Umwandlung einer [[Vektorgrafik|Vektor]]- in eine [[Rastergrafik]].

== Verfahren ==
[[Datei:textrenderp2.png|mini|Die Ergebnisse von zwei [[Portable Document Format|PDF]]-Renderern, die [[Vektorschrift]] in [[Pixelgrafik]] umsetzen.<br>Oben: [[Sumatra PDF]],<br>unten: [[Adobe Reader]].]]

Es gibt eine Vielzahl von [[Algorithmus|Algorithmen]] zur Rasterung von [[Grafisches Primitiv|grafischen Primitiven]], wie Linien, [[Polygon]]en, [[Kreis]]en und anderen [[Geometrisch|geometrischen]] Formen, siehe dazu:
* [[Rasterung von Linien]]
* [[Rasterung von Polygonen]]
* [[Rasterung von Kreisen]]

Ein bekanntes Problem der Rasterung ist der [[Treppeneffekt]]. Steht für die zu erzeugende [[Rastergrafik]] eine [[Farbtiefe (Computergrafik)|Farbtiefe]] von mehr als 1 [[Bit]] pro [[Pixel]] zur Verfügung, so kann dieser Effekt mittels Kantenglättung ([[Antialiasing (Computergrafik)|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 [[Hint]]ing vermieden werden können.

== Rasterung dicker Primitiven ==
Bei der Rasterung von [[Grafisches Primitiv|grafischen Primitiven]] mit einer bestimmten Dicke gibt es, sofern sie nicht bereits vom verwendeten [[Antialiasing (Computergrafik)|Antialiasing]]-[[Algorithmus]] unterstützt wird, mehrere Möglichkeiten. Bei [[Polygon]]en müssen 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 Lücken kommen. Außerdem weisen derartig gerasterte [[Kurve (Mathematik)|Kurven]], ähnlich wie dünne Linien, eine unterschiedliche Dicke in Abhängigkeit von der lokalen [[Steigung]] auf.
; Pinsel:Hierbei wird eine bestimmte [[Rastergrafik]] als „Pinsel“, im einfachsten Fall ein [[Quadrat]] mit gewünschter Kantenlänge, entlang der [[Kurve (Mathematik)|Kurve]] bewegt. Auch hier variiert die Dicke in Abhängigkeit von der Steigung, im Gegensatz zur Pixelwiederholung ist die Linie jedoch bei Diagonalschritten am dicksten. Dieses Problem lässt sich dadurch umgehen, dass das Quadrat gemäß 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 eingefärbte [[Pixel]] stößt. Dieser Effekt ist umso größer, je dicker die Kurve ist. Um das Problem der variierenden Kurvendicke zu lösen, können polygonförmige Pinsel verwendet werden.<ref>John D. Hobby: ''Digitized Brush Trajectories.'' Dissertation, Stanford University, 1985 ({{Webarchiv |url=http://cm.bell-labs.com/who/hobby/thesis.pdf |text=PDF, 30 MB |wayback=20061026074816}})</ref>
; Füllen zwischen Rändern:Eine andere Methode zur Rasterung einer dicken [[Kurve (Mathematik)|Kurve]] besteht darin, ihre beiden Ränder in einigem [[Abstand]] voneinander zu zeichnen und den dazwischen liegenden Bereich auszufüllen. Ein Nachteil ist, dass bei der zweifarbigen Rasterung die Kurve wegen Rundungsfehlern möglicherweise etwas verschoben erscheint. Bei [[Ellipse]]n muss beachtet werden, dass die Rasterung durch das Zeichnen zweier konfokaler Ellipsen mit unterschiedlich langen [[Halbachsen der Ellipse|Halbachsen]] geometrisch nicht korrekt ist.
; Liniensegmente:Schließlich gibt es die Möglichkeit, dicke [[Kurve (Mathematik)|Kurven]] durch eine Aneinanderreihung kurzer Liniensegmente zu zeichnen. Dabei müssen die gleichen Besonderheiten wie bei der Rasterung von [[Polygon]]en beachtet werden, damit die Liniensegmente korrekt miteinander verbunden werden.

== Löschung von Primitiven ==
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 ==
[[Raytracing]] und Rasterung sind zwei grundlegend unterschiedliche Ansätze zum [[Rendern (Bildsynthese)|Rendern]] von Bildern von [[3D]]-Szenen, obwohl sie für Primärstrahlen dieselben Ergebnisse berechnen. Durch die Rasterung wird jedes [[Dreieck]] auf die [[Bildebene (darstellende Geometrie)|Bildebene]] projiziert und alle abgedeckten Pixel in [[2D]] aufgelistet. Die Strahlverfolgung wird dabei in 3D ausgeführt, indem [[Strahl (Geometrie)|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 [[Gleitkommazahl]]en 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 (darstellende Geometrie)|Bildebene]] (siehe [[Binning]]).<ref name=":0" />

=== Berechnungen ===
<div style="float:right;">[[Datei:01 3D-Rasterung-c.svg|mini|hochkant=1.3|Bild 2: Das [[Pixel]] <math>\vec d</math> muss in bestimmten durch die [[Dreieck|Dreiecke]] <math>(\vec e, \vec{p_1}, \vec{p_0})</math>, <math>(\vec e, \vec{p_2}, \vec{p_1})</math> und <math>(\vec e, \vec{p_0}, \vec{p_2})</math> definierten [[Halbraum|Halbräumen]] liegen.]]</div>
<div style="float:right;">[[Datei:01 3D-Rasterung-a.svg|mini|hochkant=1.3|Bild 1: Projektionszentrum <math>\vec e</math> als [[Koordinatenursprung]] des [[Dreidimensional|dreidimensionalen]] [[Kartesisches Koordinatensystem|kartesischen Koordinatensystems]] mit dem Pixel <math>\vec d</math>, das in der [[Bildebene (darstellende Geometrie)|Bildebene]] liegt, und dem [[Dreieck]] <math>(\vec{p_0}, \vec{p_1}, \vec{p_2})</math>.]]</div>
[[Datei:01 3D-Rasterung-b.svg|mini|hochkant=1.3|Bild 3: Der [[Normalenvektor]] <math>\vec {n_2}</math> ist [[Orthogonalität|orthogonal]] zum [[Dreieck]] <math>(\vec e, \vec{p_1}, \vec{p_0})</math>.]]
[[Datei:01 3D-Rasterung-d.svg|mini|hochkant=1.3|Bild 4: Lage des [[Schnittpunkt|Schnittpunkts]] <math>\vec e + t \cdot \vec d</math> im [[Dreieck]] <math>(\vec{p_0}, \vec{p_1}, \vec{p_2})</math>.]]
Um herauszufinden, ob ein [[Pixel]] der [[Bildebene (darstellende Geometrie)|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 <math>\vec e</math> der [[Koordinatenursprung]] des [[Dreidimensional|dreidimensionalen]] [[Kartesisches Koordinatensystem|kartesischen Koordinatensystems]] ist, und bezeichnet die [[Ecke]]n des projizierten Dreiecks mit <math>\vec{p_0}</math>, <math>\vec{p_1}</math>, <math>\vec{p_2}</math> (Bild 1), dann ergibt sich folgende Bedingungen dafür, dass das Pixel <math>\vec d</math> im projizierten Dreieck liegt (Bild 2):

* Die Ebene, die durch das Dreieck <math>(\vec e, \vec{p_1}, \vec{p_0})</math> verläuft, teilt den [[Dreidimensional|dreidimensionalen]] [[Raum (Mathematik)|Raum]] in zwei [[Halbraum|Halbräume]]. Das Pixel der Bildebene muss in dem Halbraum liegen, in dem sich der [[Punkt (Geometrie)|Punkt]] <math>\vec{p_2}</math> befindet. Außerdem muss das [[Pixel]]
* in dem durch das Dreieck <math>(\vec e, \vec{p_2}, \vec{p_1})</math> definierten Halbraum liegen, in dem sich der Punkt <math>\vec{p_0}</math> befindet und
* in dem durch das Dreieck <math>(\vec e, \vec{p_0}, \vec{p_2})</math> definierten Halbraum liegen, in dem sich der Punkt <math>\vec{p_1}</math> befindet.
Um zu prüfen, ob sich ein Punkt <math>\vec d</math> in einem durch die Punkte <math>\vec e</math>, <math>\vec{p_1}</math> und <math>\vec{p_0}</math> definierten Halbraum befindet, kann man folgende [[Funktion (Mathematik)|Funktion]] verwenden (Bild 3):
:<math>V(\vec d) := \vec{n_2} \cdot \vec d = ((\vec{p_1} - \vec e) \times (\vec{p_0} - \vec{p_1})) \cdot \vec d</math>
wobei <math>\vec{n_2} \cdot \vec d</math> das [[Skalarprodukt]] der [[Vektor]]en <math>\vec{n_2}</math> und <math>\vec d</math> ist. Der [[Normalenvektor]] <math>\vec{n_2}</math> ist durch das [[Kreuzprodukt]]
:<math>\vec{n_2} := (\vec{p_1} - \vec e) \times (\vec{p_0} - \vec{p_1})</math>
definiert und ist [[Orthogonalität|orthogonal]] zum [[Dreieck]] <math>(\vec e, \vec{p_1}, \vec{p_0})</math>. Diese Funktion berechnet das 6-fache vom [[Volumen]] des [[Tetraeder|Tetraders]] mit den [[Ecke]]n <math>\vec e</math>, <math>\vec{p_1}</math>, <math>\vec{p_0}</math>, <math>\vec d</math>. Wenn der Punkt <math>\vec d</math> oberhalb des Dreiecks <math>(\vec e, \vec{p_1}, \vec{p_0})</math> liegt, ist das [[Vorzeichen (Zahl)|Vorzeichen]] positiv, wenn <math>\vec d</math> unterhalb liegt, ist das Vorzeichen negativ. Wenn <math>\vec d</math> in der Ebene des Dreiecks <math>(\vec e, \vec{p_1}, \vec{p_0})</math> liegt, ist das Volumen gleich 0. Der Skalierungsfaktor für das Volumen kann hier weggelassen werden, weil bei diesen Betrachtungen nur das Vorzeichen der Funktion wichtig ist.

Entsprechendes gilt für die Dreiecke <math>(\vec e, \vec{p_2}, \vec{p_1})</math> und <math>(\vec e, \vec{p_0}, \vec{p_2})</math>.

Mit den [[Funktion (Mathematik)|Funktionen]]
:<math>V_0(\vec d) := (\vec{p_2} - \vec e) \times (\vec{p_1} - \vec{p_2})</math>
:<math>V_1(\vec d) := (\vec{p_0} - \vec e) \times (\vec{p_2} - \vec{p_0})</math>
:<math>V_2(\vec d) := (\vec{p_1} - \vec e) \times (\vec{p_0} - \vec{p_1})</math>

kann folgende Aussage formuliert werden:

* Das Pixel <math>\vec d</math> liegt genau dann im projizierten Dreieck, wenn <math>V_0(\vec d) > 0</math> und <math>V_1(\vec d) > 0</math> und <math>V_2(\vec d) > 0</math> ist.

Der [[Schnittpunkt]] <math>\vec e + t \cdot \vec d</math> des Pixels <math>\vec d</math> mit dem ursprünglichen Dreieck <math>(\vec{p_0}, \vec{p_1}, \vec{p_2})</math> kann auch mit [[Baryzentrische Koordinaten|baryzentrischen Koordinaten]] der Punkte <math>\vec{p_0}</math>, <math>\vec{p_1}</math>, <math>\vec{p_2}</math> ausgedrückt werden (Bild 4). Dann gilt:
:<math>\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} </math> mit <math>\lambda_i = \frac{V_i(\vec d)}{V_0(\vec d) + V_1(\vec d) + V_2(\vec d)} </math>
wobei <math>t</math> und die <math>\lambda_i</math> [[Reelle Zahl|reelle Zahlen]] sind. Die baryzentrischen Koordinaten werden mit <math>\vec e + t \cdot \vec d = (\lambda_0 : \lambda_1 : \lambda_2)</math> bezeichnet.<ref name=":0">[https://cg.ivd.kit.edu/publications/p2012/3dr/gi2012.pdf 3D Rasterization: A Bridge between Rasterization and Ray Casting]</ref>

=== Algorithmen ===
Sobald ein [[Dreieck]] zum [[Rendern (Bildsynthese)|Rendern]] ausgewählt wurde, müssen die [[Strahl (Geometrie)|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 Programmierung|rekursive]] [[Funktion (Programmierung)|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 (Graphentheorie)|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.<ref name=":0" />

== Siehe auch ==
* [[Kachelgrafik]]

== 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

== Weblinks ==
{{Commonscat|Rasterization|Rasterung}}
* {{Internetquelle|url=http://computergrafik.informatiker-wissen.de/rastern-antialiasing.html|titel=Grundlagen der Computergrafik – Rasterisierung|archiv-url=https://web.archive.org/web/20160806220358/http://computergrafik.informatiker-wissen.de/rastern-antialiasing.html|archiv-datum=2016-08-06|zugriff=2017-11-09}}

== Einzelnachweise ==
<references />

[[Kategorie:Computergrafik]]
[[Kategorie:Fonttechnologie]]
[[Kategorie:Druckraster]]

Rasterung - Versionsgeschichte

imported>Maximum 2520: /* Berechnungen */ Erklärung verbessert, Reihenfolge der Bilder 2 und 3 geändert, Bezug zu Bild 3 hergestellt