Minecraft Klon auf Taschenrechner

Design Patterns, Erklärungen zu Algorithmen, Optimierung, Softwarearchitektur
Forumsregeln
Wenn das Problem mit einer Programmiersprache direkt zusammenhängt, bitte HIER posten.
Antworten
focus0941
Beiträge: 44
Registriert: 27.03.2023, 18:28
Benutzertext: hatte mit 3 einen Bart
Echter Name: Vladimir Ilyushko

Minecraft Klon auf Taschenrechner

Beitrag von 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.
Benutzeravatar
Jonathan
Establishment
Beiträge: 2547
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: Minecraft Klon auf Taschenrechner

Beitrag von 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.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
focus0941
Beiträge: 44
Registriert: 27.03.2023, 18:28
Benutzertext: hatte mit 3 einen Bart
Echter Name: Vladimir Ilyushko

Re: Minecraft Klon auf Taschenrechner

Beitrag von 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.
Benutzeravatar
Krishty
Establishment
Beiträge: 8317
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Minecraft Klon auf Taschenrechner

Beitrag von 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.
Jonathan hat geschrieben: 04.10.2024, 19:56Du 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.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Jonathan
Establishment
Beiträge: 2547
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: Minecraft Klon auf Taschenrechner

Beitrag von Jonathan »

ah, verstehe. Ist schon eine ganze Weile her, dass ich das per Hand gerechnet habe :D
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
focus0941
Beiträge: 44
Registriert: 27.03.2023, 18:28
Benutzertext: hatte mit 3 einen Bart
Echter Name: Vladimir Ilyushko

Re: Minecraft Klon auf Taschenrechner

Beitrag von focus0941 »

Krishty hat geschrieben: 04.10.2024, 20:31 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.
Benutzeravatar
Jonathan
Establishment
Beiträge: 2547
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: Minecraft Klon auf Taschenrechner

Beitrag von Jonathan »

focus0941 hat geschrieben: 05.10.2024, 01:05Ich 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.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
TomasRiker
Beiträge: 99
Registriert: 18.07.2011, 11:45
Echter Name: David Scherfgen
Wohnort: Hildesheim

Re: Minecraft Klon auf Taschenrechner

Beitrag von 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
Establishment
Beiträge: 897
Registriert: 28.07.2010, 20:18

Re: Minecraft Klon auf Taschenrechner

Beitrag von 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
Beiträge: 44
Registriert: 27.03.2023, 18:28
Benutzertext: hatte mit 3 einen Bart
Echter Name: Vladimir Ilyushko

Re: Minecraft Klon auf Taschenrechner

Beitrag von focus0941 »

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