Benutzer:FylypK/Artikelentwurf
Affine Texture Mapping
Affine Texture Mapping ist ein Verfahren, das in der Computergrafik genutzt wird, um jedem Pixel, das sich innerhalb eines Polygons befindet, einen Texel, der sich innerhalb einer Textur befindet, zu zuordnen. Speziell affines Texture Mapping ist eine bijektive Abbildung aus dem Texturenraum in den Pixelraum eines Polygons und umgekehrt. Des Weiteren ist es die Aufgabe eines Mapping-Alorithmus eine Filterung vorzunehmen, da in der Realität nicht jedem Pixel direkt ein Texel zugeordnet werden kann.
Affine Texture Mapping: Grundlagen/Vorüberlegungen
Um die Funktionalität des Mappings zu erläutern folgen hier einige kurze Erklärungen der bei einem solche Verfahren verwendeten Komponenten.
Texturenraum
Der Texturenraum ist ein zweidimensionaler Raum, in dem eine Textur existiert. Dieser Raum wird in horizontaler Richtung durch die u-Achse und in vertikaler Richtung druch die v-Achse aufgespannt. Der Texturenraum ist jedoch für u und v begrenzt durch 0 <= u,v <= 1, so dass (0,0) den unteren linken Eckpunkt einer Textur beschreibt und (1,1) den oberen rechten Eckpunkt. Ein Beispiel bietet Abbildung 1, in dem unter der Überschrift texture space ein solcher Koordinatenraum gezeigt wird.
Bildschirmraum
Der Bildschirmraum stellt den Bildschirm dar, also den für einen Benutzer sichtbaren Bereich. Der Bildschirmraum ist ebenso ein zweidimensionaler Raum, der in horizontaler Richtung durch x und in vertikaler Richtung durch y aufgespannt wird. Für beide Richtungen gilt typischerweise -1 <= x,y <= 1, so dass der Punkt (0,0) in der Mitte des Bildschirms liegt. Um aber die Berechnungen zu vereinfachen, wird im folgenden Beispiel mit Werten 0 <= x,y < 1 gerechnet. Dies ist Beispielhaft in Abbildung 2 unter der Überschrift screen space zu sehen.
Umrechnung von Bildschirmkoordinaten in Texturkoordinaten
Für das affine Texture Mapping ist es notwendig Koordinaten aus dem Texturenraum in den Bildschirmraum umzuwandeln. Für eine Mx x My große Textur ergibt sich also die folgende Formel für die jeweiligen Komponenten U und V:
U = floor((Mx * u) + 1);
V = floor((My * v) + 1);
Für eine korrekte Berechnung ist bei einer solche Funktion jedoch sicher zu stellen, dass 0 < u,v < 1 gilt, da sichergestellt werden muss, dass 0 <= U < Mx und 0 <= V < My gilt.
Scanline
Das Scanlineverfahren wird zur Rasterung des Polygons genutzt. Innerhalb dieses Verfahrens werden Punkte aus dem Texturenraum mit Punkten im Polygon (Bildschirmraum) gemappt. In den Abbildungen 1 und 2 ist die für dieses Verfahren wichtige Scanline in rot eingezeichnet. Diese gibt an, an welcher Stelle das Polygon aktuell im screen space gerastert wird und welche Texel des texture space mit diesen gemappt werden.
Vorüberlegungen
Das affine Texture Mapping wird normalerweise in Verbindung mit Verfahren zur Rasterung von Polygonen genutzt, wie der Scanline-Methode. Im Folgenden soll mit Hilfe dieser Methode visualisiert werden, wie affines Texture Mapping funktioniert. Um einige Rechnungen zu vereinfachen, ist es notwendig die gegebenen Daten geschickt zu organisieren. So soll jedem Eckpunkt eines Polygons ein Punkt innerhalb der Textur zugeordnet werden. In Abbildung 1 ist dies veranschaulicht, in dem man {PL,QL}, {PR,QR}, so wie {P1,Q1},{P2,Q2},{P3,Q3},{P4,Q4}, als Paare interpretiert. An dieser Stelle sei kurz erwähnt, dass dieses Verfahren eine Interpolation ist, da die gesuchten Werte zwischen den, vorher beschreibenen, Punkten liegen und zunächst nicht bekannt sind. Die rote Linie stellt die Scanline dar, sie gibt an, auf welcher Höhe in y-Richtung das Polygon gerastert wird. Aufgrund der Anzahl der im Polygon enthaltenen Punkt entstehen in diesem Beispiel, je nach Rotation des Polygons im Bildschirmbereich, bis zu drei Abschnitte die analog abgearbeitet werden können. Für Dreicke ergeben sich für das Mapping maximal zwei verschiedene Fälle, die bedacht werden müssen.
Affine Texture Mapping: Verfahren
Zur Veranschaulichung soll hier der erste Bildabschnitt zwischen {P2,Q2} und {P3,Q3} dienen. Die Interpolation findet hier statt, in dem die Farbwerte für das Polygon im Texturenraum anhand der gegebenen Koordinaten im Bildschirmbereich berechnet werden. Da sich dieses Verfahren in der Computergrafik mit seinene Räumen (Textur,Bildschirm) im Körper der reellen Zahlen bewegt, Pixel auf dem Bildschirm aber in der Realität nur in ganzen Zahlen angegeben werden können, muss hier eine Filterfunktion/Abtastfunktion bestimmt werden. Diese entscheidet mit über die Qualität des Bildes. Eine einfache Funktion ist die nearest neighbor-Methode, die den Farbwert des am nächsten liegenden ganzzahligen Texels auswählt.
Beschreibung der Fakten
Da die Kanten des Polygons von jeweils zwei Punkten aufgespannt werden, repräsentieren diese eine lineare Funktion, eine Gerade. Dies bedeutet, dass die x-, bzw. y-Differenzen,in Abbildung 2 als 'dyl','dxl','dyr' und 'dxr' eingezeichnet, zwischen P2 und P3, so wie P2 und P1 konstant sind. PL und PR bewegen sich also von P2 aus auf den jeweiligen Kanten auf P1 (für PL) und P3 (für PR) zu. Da der Abstand von PL und PR zu ihren Zielpunkten ,bzw. Startpunkten also leicht berechnet werden kann, kann man diese Verhältnisse in den Texturenraum auf die Pendants QL und QR übertragen. So werden PL/QL und PR/QR auf ihren Kanten von unten nach oben geschoben. In Abbildung 3 zeigt eine Mathematischere Schreibweise zur Beschreibung der Punkte PL und PR, wie sich diese Punkte für die jeweils folgende Zeile verschieben. Die Äquivalente der Punkte PL und PR, namentlich QL und QR, aus dem Texturenraum berechnen sich dann wie in Abbildung 4. Zwischen diesen beiden Punkten findet nun die eigentliche Interpolation statt, jedem Pixel der Strecke PLPR soll also nun ein Texel der Strecke QLQR zugewiesen werden. Somit muss das Verfahren lediglich die Punkte der Strecke QLQR auf die Differenz in x-Richtung zwischen PL und PR aufteilen. Um nun die zu Interpolierenden Farbwerte jeder Zeile zu berechnen, wird die Distanz zwischen QL und QL auf die Differenz in x-Richtung zwischen PL und PR aufgeteilt um im Bildschirmbereich ein Spaltenweises Mapping zu erhalten. Abbildung 5 beschreibt, wie sich ein Punkt zwischen QL und QR bewegen muss, wenn der aktuell zu berechnende Punkt auf der Scanline zwischen PL und PR von links nach rechts wandert. Nun kann jedem Pixel auf der Strecke PLPR ein Texel der Strecke QLQR zugewiesen werden. An dieser Stelle finden des weiteren verschiedene Filterungsverfahren ihren Einsatzort.
Möglicher Pseudocode
Da eine Implementierung für Dreiecke am wenigsten aufwendig ist wird hier nachfolgend ein möglicher Pseudocode, für eine Implementierung eines Mappers für ein Dreieck aufgezeigt.
//Voraussetzung für das gelingen dieser Funktion ist, dass v0.y < v1.y < v2.y und v1 liegt links neben dem Verbindungsvektor v0v2
//des weiteren wird angenommen, dass m0 das Mapping für v0 ist usw.
//Für eine Implementierung für beliebige Dreiecke, muss diese Funktion nur noch für ein Dreieck implementiert werden, in dem v1 rechts neben dem Verbindungsvektor v0v2 liegt!
MAP(Vektor v0,Vector v1,Vector v2,Vektor m0,Vektor m1,Vektor m2,I:Texture)
//rechne v0,v1,v2 um, so dass alle x-Koordinaten 0 <= x < BILDSCHIRM_WEITE und alle y-Koordinaten 0 <= y < BILDSCHIRM_HÖHE
v0.x = (v0.x + 1) * BILDSCHIRM_WEITE / 2
v1.x = (v1.x + 1) * BILDSCHIRM_WEITE / 2
v2.x = (v2.x + 1) * BILDSCHIRM_WEITE / 2
v0.y = (v0.y + 1) * BILDSCHIRM_HÖHE / 2
v1.y = (v1.y + 1) * BILDSCHIRM_HÖHE / 2
v2.y = (v2.y + 1) * BILDSCHIRM_HÖHE / 2
//erstelle die im Artikel erwähnten Konstanten, alle Differenzen zwischen den gegebenen Punkten v0,v1,v2 und m0,m1,m2 sind konstant
double dyl_lower,dyl_upper,dxl_lower,dxl_upper,dyr,dxr,dul_lower,dvl_lower,dur,dvr
dyl_lower = v1.y - v0.y
dyl_upper = v2.y - v1.y
dxl_lower = v1.x - v0.x
dxl_upper = v2.x - v1.x
dyr = v2.y - v0.y
dvl_lower = m1.v - m0.v
dul_lower = m1.u - m0.u
dvl_upper = m2.v - m1.v
dul_upper = m2.u - m2.u
//da es hier nur um ein Dreieck geht, in dem v2 auf der linken Seite liegt, bleibt die rechte Kante zwischen v0 und v2 konstant
dxr = v2.x - v0.x
double y = floor(v0.y)
Vector XL,XR,TL,TR
//Initialisierung von PL und PR, sowie QL und QR
PL = PR = v0
QL = QR = m0
//solange das gesamte Dreieck nicht abgearbeitet ist
while y < v2.y do
//berechne die Werte für PL und PR, sowie für u und v
double dxl
double dul,dvl,dur,dvr
dxl = PR.x - PL.x
du = QR.u - QL.u
dv = QR.v - QL.v
Vektor q = QL
//mappe die Punkte der Strecke QLQR auf die Punkte der Zeile PLPR
for x = PL.x; x < PR.x; x++ do
Vektor texelKoordinaten = toTexelCoordinates(q.u,q.v,I.width,I.height)
color = I.getRGB(texelKoordinaten.U,texelKoordinaten.V)
Färbe Pixel(x,y) mit color ein
q.u = q.u + du
q.v = q.v + dv
end
if y < v1.y then
//falls sich die Scanline zwischen v0 und v1 befindet
QL.u = QL.x + dul_lower / dyl_lower
QL.v = QL.v + dvl_lower / dyl_lower
QR.u = QR.x + dur_lower / dyr
QR.v = QR.v + dvr / dyr
PL.x = PL.x + dxl_lower / dyl_lower
PR.x = PR.x + dxr / dyr
else
//falls sich die Scanline zwischen v1 und v2 befindet
QL.u = QL.x + dul_upper / dyl_upper
QL.v = QL.v + dvl_upper / dyl_upper
QR.u = QR.x + dur / dyr
QR.v = QR.v + dvr / dyr
PL.x = PL.x + dxl_upper / dyl_upper
PR.x = PR.x + dxr / dyr
end
end
end
Die Definition einer Hilfsfunktionen ist für eine leichtere Berechnung wünschenswert:
toTexelCoordinates(u,v,Mx,My)
If u,v <= 1*10^-6 then
u = 0, v = 0
else if u,v >= 1 - 1*10^-6 then
u = 1 - 1*10^-6, v = 1 - 1*10^-6
end
U = floor((u*Mx)+1)
V = floor((v*My)+1)
return (U,V)
Weblinks
- Texture Mapping I (Video)
- Scanline (Video)
