[Projekt] Falling Sand Voxel Engine

[x1m4]

Moin alle zusammen!

Ich bin neu hier und dachte mir mal mein Projekt zu teilen, an dem ich seit ein paar Monaten arbeite.

Das Spiel Genre "Falling Sand" ist schon einige Jahrzehnte alt und es geht darum, Pixel mit verschiedenen Materialien "physikalisch" zu simulieren. Falling Sand befindet sich sehr nahe an den zellularen Automaten (z.B. Game of Life), da die Regeln, wie sich ein Pixel verhält, entsprechend der direkten Nachbaren gegeben ist.
Bekannte Titel aus dem Bereich Falling Sand und zellulare Automaten sind z.B. Noita, Powdertoy und sogar Minecraft.

Ziel des Projekts ist es, Spielern eine Möglichkeit zum Bauen von Voxel Welten zu geben. Jeder Voxel ist physikalisch simuliert und mit Ray tracing gerendert. Neben gängigen Materialien wie Sand und Wasser, gibt es auch die Möglichkeit, seine Welten mit Schaltungen zu automatisieren. Spieler sollen zudem optional ihre gebauten Welten über Kryptowährungen handeln können.

Was die Engine hauptsächlich kann:
- Bis zu 512x512x512 große Voxel Welten simulieren
- Physikalisch berechnete Lichtsimulation mit Ray tracing
- Eine Turing-vollständige Schaltungs-Simulation, mit Ähnlichkeit zu Minecraft Redstone (Batterie, Kupfer, Kraft Generator, LED, Morse Code Enkodierer/Dekodierer)
- Weitere simulierte Materialien sind Wasser, Sand, Feuer, Stein, Pflanze und Plastik

Zu der Technik meiner Engine:
- Die Simulation läuft auf der GPU über Compute shader und es gibt auch eine multi-threading basierte CPU Version, welche in C geschrieben und nach WebAssembly kompiliert ist (ohne Emscripten)
- Für die Lichtberechnung verwende ich Path Tracing und einen Spatio-Temporalen Denoiser, welcher auf Voxel Oberflächen spezialisiert ist
- Eine alternative Lichtberechnung, an der ich im Moment arbeite, verwendet Voxel Cone Tracing und ist deutlich schneller als das Path Tracing
- Die Render Engine ist in WebGL sowie in WebGPU implementiert

Links zu ein paar Videos:
- Lichtberechnung mit Cone Tracing
- Lichtberechnung mit Path Tracing
- Gallerie zu zellularen Schaltungen
- Prozedurale Terrain Generierung mit einer 3D Variante des Diamond-Square Algorithmus
- Falling Sand Simulation in einem Compute Shader

Ein paar Screenshots der Licht Engine (In Echtzeit dargestellt auf einer GTX 1070):

[Mirror]

Sieht auf jeden Fall sehr beeindruckend aus. Ich würde es auf jeden Fall mal ausprobieren wollen.

[Matthias Gubisch]

Wow sieht beeindruckend aus.

[Schrompf]

Sehr cool! Zelluläre Automaten, so wie Noita auf Steam, aber in 3D... hm, wenn's die Grafikkarte wuppt, wär das lustig!

Dein Cone Tracing würde mich interessieren, weil ich da selbst Aktien drin habe. Wie machst Du das? Das Video zeigt leider nur ein paar Demoszenen und vom Rendering erkennt man als Einziges einen iterativen Ansatz bei Schatten und AO, der über mehrere Sekunden nachzieht.

[x1m4]

Das Video zeigt leider nur ein paar Demoszenen und vom Rendering erkennt man als Einziges einen iterativen Ansatz bei Schatten und AO, der über mehrere Sekunden nachzieht.

Cool dass dir das aufgefallen ist. Schatten und Licht werden als Teil der Simulation berechnet und sind daher verzögert.
Jeder Voxel hat ein Shadow bit, was wie folgt getoggelt wird:
- Wenn Nachbar Richtung Sonne solide ist, dann mach dich zu Schatten
- Wenn Nachbar Richtung Sonne im Schatten ist, dann mach dich zu Schatten

Licht breitet sich mit einer Art asynchronen Flood-Fill (genau wie Kraft Felder und Strom) aus, was es sehr skalierbar macht. Der Ansatz besitzt auch starke Ähnlichkeit mit dem Propagation Part von Light Propagation Volumes.

Das Video hier beschreibt die Idee vielleicht ein bisschen besser:




Die globale Illumination und Dinge wie AO sind allerdings instant, da ich hierfür reguläres Cone Tracing verwende. Jedenfalls, die neue Lichtberechnung ist noch ein großes Experiment, bin viel am rumprobieren und noch nicht zufrieden mit dem momentanen Stand.

[Schrompf]

Genau das "reguläre Cone Tracing" hätte mich halt interessiert :-) Light Propagation Volumes sind mir ein Begriff, habe ich aber wegen zu großer Szenen bei mir nie verwendet. Deine Szene ist schön limitiert, da ist das ne wirklich gute Sache.

Wie machst Du denn das Cone Tracing? Diese Sparse Voxel-Ding von Crassin, wo man einen Sparse Voxel Tree aus jeweils 3³ Voxel als Mini-Volume-Textur samplet?

[x1m4]

Light Propagation Volumes sind mir ein Begriff, habe ich aber wegen zu großer Szenen bei mir nie verwendet

Cone Tracing hat ähnliche Speicherprobleme wie LPV, es bietet sich bei beiden Methoden sehr an ein Kaskaden bzw. Clipmap System zu verwenden, hauptsächlich zur Speichereinsparung und Darstellung von großen Szenen, aber auch um den VRAM Traffic deutlich zu reduzieren.

Wie machst Du denn das Cone Tracing? Diese Sparse Voxel-Ding von Crassin, wo man einen Sparse Voxel Tree aus jeweils 3³ Voxel als Mini-Volume-Textur samplet?

Ich benutze zwar einen Octree, allerdings einen MIP basierten, da z.B. Stack basierte Octrees für mein Projekt zu langsam sind. In meiner Szene gehe ich grundsätzlich vom schlimmstem Fall aus, nämlich dass sich jeder einzelne Voxel jedes Frame bewegen und ändern kann.

Neben meinem Voxel Volumen (zum Ray Casten der Voxel) habe ich ein Radianz Volumen, in der Blockfarbe und Opazität drin stehen. Hier benutz ich ein gewöhnliches 3D Volumen, hab allerdings vor ein Clipmap System wie hier einzubauen.

[Lord Delvin]

Spannend zu sehen, dass man da mittlerweile was zustande bekommt. Wir haben uns das vor vielen Jahren mal auf der CPU angeschaut und wieder aufgegeben, weil es für uns so aussah, als würden wir nicht zu den Durchsätzen kommen, die wir haben wollten.
Vermutlich lohnt sich die CPU-Version höchstens zum Debuggen.

Sieht auf jeden Fall sehr gut aus :)

[x1m4]

Die Lichtberechnung ist nun ein Mix aus Cone Tracing und Light Propagation Volumes. Anstatt Radianz durch MIP Blurring zu erzielen verwende ich jetzt direkt das Licht aus der zellularen Simulation. Das reduziert das Problem von "Light leaking", also Licht, das durch solide Voxel durchdringt.

Um dichte Bereiche abzudunkeln schieße ich nun einen sehr weiten Cone, was der Szene noch mehr Tiefe gibt. Außerdem werden Cones nun stochastisch gejittert, was Banding reduziert, und als Nebeneffekt ein subtiles Rauschen mit sich bringt. Das Jittering kostet leider auch ein bisschen mehr Leistung, da es den Cache killt.

Für zusätzliches Ambient Occlusion verwende ich nun einen Ansatz, ähnlich dem von Minecraft. Die Idee ist, anhand der soliden Nachbaren und den UV-Koordinaten auf den Voxeln einen Schattenverlauf zu interpolieren.

[x1m4]

Habe nun endlich geschafft TAA (Temporal Anti-Aliasing) zu implementieren. In der Vergangenheit hab ich dazu bereits mehrere Versuche unternommen, allerdings war das Ergebnis immer dermaßen mangelhaft, dass ich es lieber wieder verworfen habe.

Das Ergebnis ist nun schönes AA, was auch über Frames hinweg stabil bleibt und ziemlich flott läuft. Geometrie wird beim Zeichnen mit einer Halton-Sequenz "gejittert". Für die Reprojektion verwende ich Motion Vektoren und eine RGB Bounding Box, welche entscheidet, wie viel des vorherigen Pixels in die neue Textur reprojeziert wird.

Es hat sich außerdem herausgestellt, dass durch das TAA das Bild auch allgemein sehr viel stabiler ist. Wenn Voxel auf dem Bildschirm nur wenige Pixel schneiden, dann entsteht dadurch ein Präzisions bedingtes "Flackern". Dem Problem wird durch das jittern und akkumulieren über Zeit entgegen gewirkt.

Hier das Ergebnis:

[Lord Delvin]

Sieht auf jeden Fall extrem gut aus. Mir ist allerdings nicht ganz klar, ob es beabsichtigt ist, dass die Würfel durchsichtig zu sein scheinen.

[x1m4]

Ja durch das Cone tracing dringt Licht leider durch mind. 1 Voxel durch, dadurch sehen Oberflächen schnell "glasig" aus. Hab schon ein paar Versuche unternommen das zu fixen, allerdings ohne erfolg :/ Bei Cone tracing mit detaillierten Triangel Szenen fällt das nicht so auf, mein Radianz Volumen ist allerdings 1:1 so groß wie das Voxel Volumen selbst.

[x1m4]

Nochmal das Licht ein bisschen überarbeitet, jetzt sieht man deutlicher, wie das Licht springt (z.B. vom roten Boden aus):


Bin mit der Szene sonst aber noch nicht ganz zufrieden. Vor allem wenn man rauszoomt sieht die Szene viel zu matt aus, da muss ich wahrscheinlich noch irgendwas am Sonnenlicht oder so ändern. Auch das Ambient Occlusion ist noch nicht wirklich so wie ich es haben will.

[marcgfx]

Am besten gefällt mir das Bild. Bin gespannt wie es weitergeht.

[x1m4]

Am besten gefällt mir das Bild. Bin gespannt wie es weitergeht.

Danke, hab nochmal eine ähnliche Szene wie in dem Bild gemacht:

[x1m4]

Es gibt nun die Möglichkeit, im Hauptvolumen Referenzen zu Untervolumen (Sub-Voxel) zu setzen. Das ermöglicht, für beispielsweise Objekte detailliertere Modelle zu verwenden. Das Prinzip ist ähnlich zu klassischem GPU Instancing, allerdings ist meins vollständig CPU entkoppelt und läuft sehr viel schneller (bis zu 16.777.216 instances ohne Probleme, mehr hab ich nicht getestet).

Knifflig ist die Lichtberechnung der Untervolumen. Neben dem Cone tracing im Hauptvolumen, führe ich das Cone tracing nun auch innerhalb der Untervolumen aus. Allerdings anstatt eines diffusen Cones schieße ich lediglich einen Ambient Cone, um das Ambient Occlusion zu approximieren. Das lässt die Sub-Voxel weniger flachen aussehen und es wirkt so, als wären sie tatsächlich Teil der Welt.

Eine interessante Idee ist auch, dass ich anstatt Voxel basierten Untervolumen stattdessen SDFs darstellen könnte. Da fehlen mir nur leider im Moment die Anwendungsfälle, wo das nützlich sein könnte.

Hier lediglich ein 8^3 großes Block Modell als Untervolumen:


Hier ein 7^3 großes Block Modell:


Hier ein Test Modell:


Hier ein Video mit Kugel Modell:

[xq]

Ich sehe und staune. Hab nicht viel zu sagen, find das Projekt aber sehr, sehr geil!

[Tiles]

Me likes!

[x1m4]

Cool dass es euch gefällt!

Wenn jemand z.B. optisch Verbesserungsvorschläge hat, dann bitte einfach mitteilen. Hab bei meinem Projekt oft das Problem, dass ich nicht oder erst sehr viel später sehe, dass etwas vom Licht her nicht ganz richtig aussieht. Also wenn was ins Auge springt oder so, nicht zögern^^

[Schrompf]

Coole Tech! Aber wenn Du fragst, was nicht ganz richtig aussieht: Deine AO hat ein Self Shadowing Problem. Am besten zu sehen hier:



Die glatten hochstehenden Wände sind leicht verdunkelt durch's AO, zu den Würfelkanten hin werden sie heller. Ich denke, das ist das Voxel Cone Tracing, was zu nahe am Voxel selbst sampled, so dass der lineare Texturfilter ein bissl was vom eigenen Voxel mit reinsampelt. Ein Offset von 0,5 von der Wand weg, so dass der erste Sample genau nicht mehr den eigenen Voxel reinfiltert, könnte helfen.

[x1m4]

Ja da muss ich echt nochmal ran. Den Cone über die Normale offseten mache ich bereits. Das Problem ist, dass mein "Geometrie-Volumen" in der Welt und das Volumen zur Lichtberechnung 1:1 die gleiche Größe haben. Wenn man dann zu weit weg offsetet, dann dringt man in den Nachbar ein, wenn zu wenig dann schneidet der Cone den eigenen Voxel. Wird wahrscheinlich Fummelarbeit das zu fixen^^

[Schrompf]

Hm, an Ecken vielleicht, aber Du hast ja saubere 90°-Oberflächen. Da müsste es echt nur ein halber Texel sein, so dass der eigene Voxel gerade nicht mehr in die Texturfilterung einfließt.

[x1m4]

Nach ein bisschen Fummelei:


Sehen jetzt ein bisschen mehr nach Klötzen aus.

Hm, an Ecken vielleicht, aber Du hast ja saubere 90°-Oberflächen. Da müsste es echt nur ein halber Texel sein, so dass der eigene Voxel gerade nicht mehr in die Texturfilterung einfließt.

Ja wahrscheinlich wäre eine saubere Lösung eine Funktion, die Anhand der Nachbar Positionen und anhand der Distanz zu den eigenen Ecken einen smoothen Wert zum verschieben über die Normale gibt.

Hab mal ein bisschen rumprobiert, so in die Richtung könnte die Funktion dann aussehen:

Flache Ebenen müsste ich noch anfangen.

[Schrompf]

Bissl rund fände ich sehr cool. Aber wenn Du anfängst, Deine Normalen von 90° wegzuschrägen, muss Dein Sample-Offset noch weiter wachsen :-) Die Normale ist normiert, der Texturfilter filtert aber unbeeindruckt achsenseparat bis zur 0.5f.

Nuja, Du kriegst das hin. Oder auch nicht, sieht ja nicht so schlimm aus, der Leidensdruck ist also gering.

[joeydee]

Cool dass es euch gefällt!

Wenn jemand z.B. optisch Verbesserungsvorschläge hat, dann bitte einfach mitteilen. Hab bei meinem Projekt oft das Problem, dass ich nicht oder erst sehr viel später sehe, dass etwas vom Licht her nicht ganz richtig aussieht. Also wenn was ins Auge springt oder so, nicht zögern^^

Ich schließe mich dem "cool, gefällt" an :)

Da du explizit fragst - was mir auffällt: Seiten, die den Lichtquellen abgewandt sind, sind trotzdem beleuchtet. Es wirkt eher diffundierend durchgefärbt statt beleuchtet. Fällt z.B. auch in deinem letzten Beitrag auf bei der grünen Lichtquelle in Bildmitte. Falls das vom Bouncing kommen sollte, ist es viel zu stark im Vergleich zum direkten Licht. Oder ist die Lichtdiffusion ein absichtlicher Effekt?

P.S., zur Kantendetektion, kennst du diesen Artikel?
https://iquilezles.org/www/articles/vox ... llines.htm

[x1m4]

Da du explizit fragst - was mir auffällt: Seiten, die den Lichtquellen abgewandt sind, sind trotzdem beleuchtet. Es wirkt eher diffundierend durchgefärbt statt beleuchtet. Fällt z.B. auch in deinem letzten Beitrag auf bei der grünen Lichtquelle in Bildmitte. Falls das vom Bouncing kommen sollte, ist es viel zu stark im Vergleich zum direkten Licht. Oder ist die Lichtdiffusion ein absichtlicher Effekt?

Ich verwende statt Farbinformationen von soliden Blöcken eine Art Lichtvolumen, welches das Licht der Sonne und das Licht von Lichtquellen beinhaltet (geht in die Richtung von Light Propagation Volumes). Das Licht geht um Ecken, da es in der Simulation mit einem Flood-Fill ausgebreitet wird. Das hat also nicht direkt mit dem Cone tracing sondern mit der Lichtausbreitung in der Simulation selbst zu tun. Hier ein Beispiel in 2D:


Grund dafür ist, dass Cone Tracing mit einem Radianz Volumen, das 1:1 mit der Geometrie der Welt skaliert schwierig zu sampeln ist, da man nur einen schmalen Grad zwischen Selbst-Okklusion und Nachbar-Okklusion hat. Wäre das Radianz Volume z.B. doppelt so groß, dann hätte man schon mehr Spielraum.

P.S., zur Kantendetektion, kennst du diesen Artikel?
https://iquilezles.org/www/articles/vox ... llines.htm

Ja für die Funktion in meinem vorherigen Post verwende ich einen ähnlichen Algorithmus, allerdings mit einem Box SDF, welches auf die Oberfläche der Voxel projiziert wird. Den Artikel hab ich schon mal gesehen, das Ergebnis sieht gut aus und scheint sich für mein Problem zum Offseten der Cones an den Kanten echt anzubieten.

[joeydee]

Dann scheint mir der Floodfill so wie er ist relativ ungeeignet auch für nur grob angenäherte Lichtausbreitung. Aber ich rede nichtmal von korrekter Lichtquellen-Okklusion und Schattenwurf.
Beachtest du irgendwie, dass die Lichtmenge, die auf einem Oberflächenfragment tatsächlich zu sehen ist, auch vom Neigungswinkel der Oberfläche zur Quelle abhängt, und nicht nur von der "Lichtmenge" die in diesen Sektor weitergegeben wurde? Jedenfalls wirkt es so als ob das nicht der Fall ist. Das wäre ungefähr so, als ob man in einem Mesh-Level Punktlichtquellen ausschließlich mit Falloff rendert, aber ohne NdotL.
Ich habe mich damit noch nicht näher befasst, vielleicht rede ich da auch Müll, aber vielleicht kannst du neben dem Intensitätswert auch einen Richtungsvektor im Floodfill weiterreichen?

[x1m4]

Ja das mit dem Flood-Fill ist hald Minecraft Licht. Eventuell kann ich irgendwann das Cone Tracing anstatt LPV auf ein normales Farb/Emissions Volumen umstellen. Mein letzter Versuch das umzustellen war aber leider kein Erfolg und das Problem mit der Selbst-Okklusion war leider extrem sichtbar.

Eine Art NdotL bekomme ich, indem ich von der Cone Richtung und der Oberflächen Normalen das Punktprodukt ziehe, dabei kommt ein ähnlicher Effekt bei raus. Bei meiner Force Simulation (Force wird in Velocity umgewandelt und ermöglicht es Zellen zu pushen/pullen) speichere ich eine Richtung mit.
Ein Richtungsvektor ist zwar möglich aber knifflig, da wenn sich zwei Lichtquellen (eine Links, eine Rechts) in der Mitte treffen, sich die Richtungen dann mehr oder weniger gegenseitig weg-chanceln.

[x1m4]

Nochmal die Lichtberechnung überarbeitet. Das für das Cone tracing verwendete Volumen beinhaltet jetzt nur noch Farben und Okklusions Informationen. Die Änderung wird es möglich machen, Reflektionen und Refraktionen zu implementieren.

Außerdem sind Schatten nun nicht länger Teil der Simulation, sondern werden ebenfalls über Cone tracing berechnet. Ich hab auch normales Shadow Mapping und Ray tracing versucht, aber die Kanten waren viel zu hart. Durch das Cone tracing sind Schatten nun sehr smooth und haben eine schöne Penumbra, und kosten auch kaum Leistung.

Hier zwei Screenshots:

[Schrompf]

Schick! Schatten über ConeTracing hatte mich eh gewundert, warum Du das noch nicht gemacht hast. Ja, sind ein paar Samples mehr pro Pixel, aber das sollten die meisten Grafikkarten abkönnen, und notfalls kannst Du es auf halber Auflösung oder so berechnen und hochskalieren