Minecraft Klon auf Taschenrechner

[focus0941]

Hallo,
nachdem ich mehrere Videos über Minecraft Klone auf grafischen Taschenrechnern gesehen hatte und wir uns einen für die Schule anschaffen mussten, habe ich beschlossen, einen eignen zu machen. Also habe ich damit angefangen einen Rasterizer zu programmieren. Da Taschenrechner dafür bekannt sind, nicht besonders schnell zu sein, muss man an allen Stellen sparen, wo es geht.
Meine Frage ist nun, ob es sinnvoll ist z_far nicht zu benutzen, um Operationen in den Matrixmultiplikationen zu sparen. Die Welt ist sowieso nur 8x8x8 groß, also dachte ich mir das wäre vielleicht nützliche, allerding bin ich kein Experte in Sachen Optimierung.
Ansontsten würde ich hoffen, dass Backface- und Frustum-Culling einen gute Job machen und dass ich dann mehr als 1 FPS haben werde.

[Jonathan]

Ich verstehe nicht so ganz, wovon du redest. Was genau ist z_far? Far-Clipping Plane? Du transformierst ja die Punkte in den Screen Space und musst durch die Entfernung teilen um Perspektive zu bekommen, und dafür wirst du wohl irgendwo etwas definieren, was man z-far nennen könnte. Das kann man dann also nicht so einfach weglassen, irgendwie muss ja definiert sein, was "Tiefe" bedeutet.

[focus0941]

Also meine ProjectionMatrix sieht normal so aus:

Code: Alles auswählen

[aspect_ratio / tan_half_fov,          0,                  0,                         0               ]
[             0,              1 / tan_half_fov,            0,                         0               ]
[             0,                       0,       -zfar / (zfar - znear), -zfar * znear / (zfar - znear)]
[             0,                       0,                  1,                         0               ]

Wenn ich mich nicht irre, sieht diese nach Weglassen von z_far nur noch so aus:

Code: Alles auswählen

[aspect_ratio * fov,  0,   0, 0]
[         0,         fov,  0, 0]
[         0,          0,   1, 1]
[         0,          0,  -1, 0]

Die z-Koordinate geht dabei nicht verloren, es wird bei der Transformation nur kein Wert mehr darauf gelegt, wie weit ein Punkt entfernt ist.

[Krishty]

Weglassen der Far Clipping Plane ist eine gängige Optimierung bei Spielen, die Software Rasterization ohne Depth Buffer betreiben. Wenn du keine affine Texturprojektion brauchst, kannst du so auch die W-Koordinate wegsparen.

Das erlaubt dir dann auch, anstelle einer 4×4-Matrix eine 3×3-Matrix (für Rotation) plus drei Additionen (für Verschiebung) zu nutzen.

Du transformierst ja die Punkte in den Screen Space und musst durch die Entfernung teilen um Perspektive zu bekommen, und dafür wirst du wohl irgendwo etwas definieren, was man z-far nennen könnte. Das kann man dann also nicht so einfach weglassen, irgendwie muss ja definiert sein, was "Tiefe" bedeutet.

Wie er schreibt – die Tiefe steckt noch in der Z-Koordinate. Sie wird halt nur nicht auf einen Wertebereich normalisiert, der normalerweise im Depth Buffer landen würde.

[Jonathan]

ah, verstehe. Ist schon eine ganze Weile her, dass ich das per Hand gerechnet habe :D

[focus0941]

Weglassen der Far Clipping Plane ist eine gängige Optimierung bei Spielen, die Software Rasterization ohne Depth Buffer betreiben. Wenn du keine affine Texturprojektion brauchst, kannst du so auch die W-Koordinate wegsparen.

Das erlaubt dir dann auch, anstelle einer 4×4-Matrix eine 3×3-Matrix (für Rotation) plus drei Additionen (für Verschiebung) zu nutzen.

Ja, das ist eine gute Idee. Ich könnte auch noch die Rotationsmatrix um die Kamera-Z-Achse weglassen, da sie in diesem Fall sowieso nicht verwendet wird.

Wenn ich alles richtig verstanden habe, dann sind das hier alle Matrizen, die ich brauche:

Code: Alles auswählen

projectionMatrix
[aspect_ratio * fov,  0,   0]
[         0,         fov,  0]
[         0,          0,   1]

translationMatrix
[1, 0, -cameraPosition.x]
[0, 1, -cameraPosition.y]
[0, 0, -cameraPosition.z]

cx, cy = Math.cos(cameraRotation.x), Math.cos(cameraRotation.y)
sx, sy = Math.sin(cameraRotation.x), Math.sin(cameraRotation.y)

rxMatrix
[1,  0,   0]
[0, cx, -sx]
[0, sx,  cx]

ryMatrix
[ cy,  0, sy]
[  0,  1,  0]
[-sy,  0, cy]

Die Frage ist nun, wie das Texture-Mapping funktionieren wird. Ich glaube Quads wären effizienter, denn da müsste ich theoretisch nur die Texturkoordinaten bilinear interpolieren zwischen den Bildschirmkoordinaten der vier Ecken der Quads. Und ich schätze mal die Pixelfarbe sollte auch nur durch den nähesten Pixel der Textur bestimmt werden, anstatt zu interpolieren.

[Jonathan]

Ich glaube Quads wären effizienter, denn da müsste ich theoretisch nur die Texturkoordinaten bilinear interpolieren zwischen den Bildschirmkoordinaten der vier Ecken der Quads.

Das wird aber Probleme machen, siehe hier:

https://mtrebi.github.io/2017/03/15/tex ... ctive.html

Zu den Matrizen: Ich bin mir nicht ganz sicher, wieso du eine Matrix pro Rotationsachse hast. In der Regel ändern die sich ja viel seltener als sie benutzt werden (z.B. wird die ganze Szene mit der selben Kamera gerendert, die ändert sich also nicht zwischen verschiedenen Vertexen), weswegen du wohl eh einmal die gesamte Transformation als einzelne Matrix ausrechnen würdest. Wenn du die benutzt ist es ja egal, aus wie vielen Matrizen die ursprünglich mal zusammengesetzt war, und weil du die Gesamttransformation vielleicht hundertmal oder gar tausendmal seltener ausrechnen muss, wie du sie benutzt, spielen da eine handvoll zusätzliche Operationen wirklich keine Rolle.

[TomasRiker]

Das Problem mit affiner Interpolation der Texturkoordinaten kann man einigermaßen in den Griff kriegen, wenn man das Mesh ein wenig mehr unterteilt (ggf. auch abhängig von der Entfernung und dem Winkel zur Kamera). Wenn ich mich richtig erinnere, haben das einige frühe 3D-Spiele so gemacht, wenn perspektivische Interpolation zu teuer war.

[scheichs]

Man kann auch im Screenspace subdividen, Quake (und andere SW-Rasterizer) hatte das so gemacht.

https://en.wikipedia.org/wiki/Texture_mapping -> "Screen space subdivision"

[focus0941]

Mir ist gerade aufgefallen, dass es doch konkave Formen geben kann, also brauche ich doch eine 4x4 Matrix :(