Textur zeichnen wenn 4 2D-Eckpunkte gegeben

Sers, ich habe folgendes Problem:

ich möchte eine einfache 3D Engine schreiben, ohne OpenGL, sie soll Pixel für Pixel zeichnen.

Ich habe die 2D Bildschirm-Koordinaten von einem Rechteck. Außerdem habe ich eine Textur als RGB-Array im Speicher. Das Rechteck soll nun mit der Textur gefüllt werden.

Nun laufe ich durch die Pixel des Quadrates auf dem Bildschirm. Frage: wie errechne ich den Index des Pixels aus der Textur das an die aktuelle Bildschirmposition gehört?

Das soll dann wie hier aussehen:

http://trackmania-carpark.com/imagespark/up/475ffe48…

Also die Textur ist immer rechteckig und ihre Größe ist natürlich bekannt.

Das Quadrat kann irgendwie im Raum liegen, auch verkehrt herum oder gedreht oder gestaucht.

Die Quadratkoordinaten sind z.B.:

(50,100),(145, 90),(140,200),(40,204)

Wichtig: die Quadrat-Eck-Koordinaten sind die auf dem Bildschirm, nicht im 3D-Raum! Ich möchte durch die Pixel des Rechtecks laufen und die zugehörige Position in der Textur bestimmen, nicht umgekehrt.

Danke vielmals!

Hi!

Sers, ich habe folgendes Problem:

ich möchte eine einfache 3D Engine schreiben, ohne OpenGL, sie
soll Pixel für Pixel zeichnen.

Ist natürlich die Frage: In welcher Sprache?

Ich habe die 2D Bildschirm-Koordinaten von einem Rechteck.
Außerdem habe ich eine Textur als RGB-Array im Speicher. Das
Rechteck soll nun mit der Textur gefüllt werden.

Klingt gut.

Nun laufe ich durch die Pixel des Quadrates auf dem
Bildschirm. Frage: wie errechne ich den Index des Pixels aus
der Textur das an die aktuelle Bildschirmposition gehört?

Wichtig: die Quadrat-Eck-Koordinaten sind die auf dem
Bildschirm, nicht im 3D-Raum! Ich möchte durch die Pixel des
Rechtecks laufen und die zugehörige Position in der Textur
bestimmen, nicht umgekehrt.

Vor Ewigkeiten hatte ich sowas mal inspiriert durch

https://de.wikipedia.org/wiki/Bresenham-Algorithmus

mit reinen Festkomma-Berechnungen gemacht. Laut den
Kommentaren im alten Code ging das so, Variabelen
sind jeweils Festkomma X/Y Paare, also Bildschirm-
koordinaten * 65536, Gleitkomma war damals langsam.

achse1 = (unten links - oben links) / 64
(Textur war 64x64 gross)
achse2 „oben“ = (oben rechts - oben links) / 64

… dann gab es noch einen Korrekturfaktor, damit
das Viereck kein Parallelogramm zu sein braucht:

achse2 „unten“ = (unten rechts - unten links) / 64

Immmer, wenn man entlang Achse1 einen Schritt
weiter kam, wurde die Achse2 um 1/64 Unterschied
mehr „Achse 2 unten artiger“, also:

Achse2 neu = Achse2 alt +
((Achse2 unten - Achse2 oben) / 64)

… wobei man den Anpassungswert nur einmal am
Anfang berechnen muss. Die eigentliche Schleife:

Ort = oben links

  1. Merker = Ort
  2. Farbe = folgender Wert aus Textur Array
    (ggf Transparenz behandeln)
    Pixel ausgeben
    Ort = Ort plus Achse1
    Wiederhole 64 mal ab 2.
    Ort = Merker + Achse2
    Achse1 = Achse1 + Korrekturfaktor
    Wiederhole 64 mal ab 1.

Im Textur-Array kommen die Zeilen einfach direkt hintereinander, das macht es „zweidimensional“.

Der Algorithmus oben kannst du nicht gut zoomen:
Jedes Pixel des Textur-Array wird genau einmal
gezeichnet, auch wenn damit Bildschirm-Pixel
mehrfach gezeichnet werden (Verkleinerung) oder
ein Loch entsteht (wenn du rein zoomst). Vorteil
ist aber, dass die komplette Schleife nur mit
„Plus“ auf Koordinaten bzw Vektoren rechnet und
der Zugriff auf den Array sogar linear passiert.

In der Schleife kommen also keinerlei komplexe
Berechnungen wie Multiplikationen oder sogar
Divisionen vor. Das macht die Sache schnell :smile:

Ich denke, man kann die Idee auch umdrehen: Gehe
bei jedem Pixel auf dem Bildschirm genau einmal
vorbei und berechne die Koordinaten in Einheiten
von Achse1 und Achse2 ab „oben links“. Wenn sie
ausserhalb von 0 bis 64 liegen, passiert Nichts,
ansonsten sind die Koordinaten der Ort in deinem
Texturspeicher den du zugreifen willst. Vorteil:

Du kannst beliebig zoomen und mit Modulo sogar
deine Textur kacheln, also z.B. sagen, das Vier-
eck soll die Textur genau 3x2 mal enthalten. Die
Achse1 und Achse2 teilst du dann einfach durch 3
und 2 und beim Zeichnen bekommen Pixel (0;0) bis
(192;128) jeweils die Farbe aus Textur(Koord. in
Achse1 modulo 64; Koord. in Achse2 modulo 64)…

Ein Problem bei der Sache: Du willst nicht alle
Pixel auf dem Bildschirm testen, sondern nur ein
Rechteck von Min(x und y von allen 4 Ecken) bis
Max(x und y von allen 4 Ecken) oder noch besser
z.B. ein Parallelogramm, wenn du jeweils vorher
berechnen kannst, wo die aktuelle Bildschirmzeile
dein Viereck schneidet (min/max X an dem Y Ort).

Noch problematischer: Du willst immernoch, dass
das Viereck beliebige Form haben kann. Und dann
wird es schwierig, von Bildschirmkoordinaten auf
Achse1 und Achse2 umzurechnen, weil mindestens
eine Achsel je nach Position entlang der anderen
Achse verzerrt wird. Vielleicht ist es dann doch
einfacher, Dreiecke zu zeichnen, da passiert das
nicht. Und zwei Dreiecke geben auch ein Viereck.

Jedenfalls willst du eine Formel, bei der sich
die Position in Einheiten von Achse1 und Achse2
linear bewegt, wenn du 1 Pixel in Bildschirm-
koordinaten nach rechts oder unten gehst. Denn
du willst ja die Bildschirmkoordinaten in einer
Schleife durchlaufen und nicht bei jedem Pixel
wieder eine komplette Umrechnung machen, sonst
wird die Schleife ja viel zu langsam.

Das waren jetzt zwar alles leider keine besonders
konkreten Algorithmen, aber ich glaube, dass die
Antwort trotzdem als Inspiration weiterhilft :smile:

Gruss, Eric

Hallo,

Wäre es eine Lösung, wenn du von der textur ausgehst und dann die Fläche ausgehend davon füllst?
Die Skalierung und Translation in den 3D Raum würde ich danach machen. Im Grunde genommen ist ja das Resultat nur die Textur, im Raum verzerrt.

Bin mal gespannt, was andere für Ideen haben.
Interessant, dass Du das Problem selber lösen willst, denn fertige Libraries gibt es beliebig viele.

Gruß, Ralf

Du willst also von der 2d bildschirmkoordinate, die sich eigentlich aus dem 3d modell ergibt mit einer textur belegen, indem du die textur auf die 2d transformation des 3d rechtecks anwendest.
Das ist meines erachtens unsinn. Du malst die textur auf den bildschirm statt auf das objekt. Das verfahren scheitert sofort, wenn sich irgendwelche ueberdeckungen ergeben, bzw es wird dann richtig kompliziert.
Du musst dich mit 3d raeumen und ihrer mathematik beschaeftigen, sowie der abbildung von 3d auf 2d, sonst programmierst du dich zu tode.

d.h. Zuerst hausaufgaben machen, dann programmieren.
Alles andere fuehrt nicht zu einem brauchbaren ziel.

Viel Erfolg,
Martin

Ich fürchte, ich kann dein Problem nicht bis ins Detail lösen. Du musst dich aber vermutlich mit dem Thema Projektionen und Vektoren befassen. Die Gleichungen dazu findest du im Tafelwerk und einen kleinen Denkanstoß hier:

http://de.wikipedia.org/wiki/Vektorraum

Vielen Dank Eric,

ich werde deine Antwort in den nächsten Tagen genau studieren. Ich melde mich dann noch mal!

Es ist so: die Textur ist 1024 x 768 Pixel groß. Auf dem Bildschirm ist das Rechteck viel kleiner, z.B. ca. 100 x 100. Wenn ich durch die Pixel auf dem Bildschirm laufe, sind das 10000 Operationen. Wenn ich durch die Pixel der Textur laufe, über 70 (!) mal so viele. Ich habe mir schon etwas dabei gedacht. Meine simple 3D Engine funktioniert ja fast, nur in bestimmten Situationen versagt die jetzige Implementation.

Da kann ich Dir leider nicht weiterhelfen.

ich möchte eine einfache 3D Engine schreiben, ohne OpenGL, sie
soll Pixel für Pixel zeichnen.

Ich habe die 2D Bildschirm-Koordinaten von einem Rechteck.
Außerdem habe ich eine Textur als RGB-Array im Speicher. Das
Rechteck soll nun mit der Textur gefüllt werden.

Nun laufe ich durch die Pixel des Quadrates auf dem
Bildschirm. Frage: wie errechne ich den Index des Pixels aus
der Textur das an die aktuelle Bildschirmposition gehört?

Das soll dann wie hier aussehen:

http://trackmania-carpark.com/imagespark/up/475ffe48…

Also die Textur ist immer rechteckig und ihre Größe ist
natürlich bekannt.

Das Quadrat kann irgendwie im Raum liegen, auch verkehrt herum
oder gedreht oder gestaucht.

Die Quadratkoordinaten sind z.B.:

(50,100),(145, 90),(140,200),(40,204)

Wichtig: die Quadrat-Eck-Koordinaten sind die auf dem
Bildschirm, nicht im 3D-Raum! Ich möchte durch die Pixel des
Rechtecks laufen und die zugehörige Position in der Textur
bestimmen, nicht umgekehrt.

Danke vielmals!

Hi,
Es scheint, als wäre dir noch nicht ganz klar, auf was du dich da eingelassen hast.
Lies doch mal als appetitanreger folgenden wikipediaartikel http://de.wikipedia.org/wiki/Texture_Mapping
Vielleicht ist auch das thema grafikengine was für dich: http://de.wikipedia.org/wiki/Grafikengine
Wie gesagt, nur als Einstieg um einen Eindruck zu bekommen, von was für einem Problem du sprichst bzw. Warum es keine sinnvolle Antwort auf deine Frage gibt.

Viel Spass, Martin