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
- Merker = Ort
- 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 
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
Gruss, Eric
