Fragen bzgl. Voxel Engine

[mike7774]

Hallo liebe Zfx Community,

ich bin momentan dabei eine kleine Voxel Engine für ein Spiel zu schreiben und hätte ein paar Fragen dazu, habe bereits im Internet alle möglichen Papers dazu durchgelesen, aber ein paar Dinge sind mir noch unklar. Das ganze Projekt wird in C/C++ ohne irgendwelche Fremdbibliotheken geschrieben.

Also ich fang mal an^^
1. Die Engine soll Sparse Voxel Octrees für die Verwaltung der Daten verwenden, wäre es sinnvoller Voxelchunks (32x32x32) oder Voxel in die Octrees zu packen? (1 Voxel ~10cm³)
2. In den GPU Gems werden für eine Voxel Demo ~300 Vertexbuffer verwendet - kann jede Grafikkarte soviele Vertexbuffer verarbeiten? (Das Spiel soll auch auf Nicht-High-End Rechner funktionieren - skalierbare Voxeldichte)
3. Wie handhabe ich die Kommunikation zwischen Spiel und Daten auf der Festplatte, also das Streaming der Daten (das Spiel soll eine "unendliche" Welt darstellen können)?

Das wären mal die Dinge die mir schnell einfallen... falls jemand ein paar Vorschläge dazu hat, oder ein paar Dokumente kennt die weiterhelfen können, bitte posten.

Mfg
Mike

[Schrompf]

Viel Spaß. Du hast Dir da ein hammerhartes Thema ausgesucht, das kann ich Dir aus eigener Erfahrung sagen.

1) hängt davon ab, wie Deine Welt nachher aussehen soll. Wie hoch ist denn die Chance, dass ein Chunk tatsächlich vollständig leer oder vollständig einheitlich gefüllt ist? Davon hängt ja ab, wieviel Speicher Du verschwendest, wenn Du 32er Blöcke nimmst. Ich habe mal Experimente mit 2er Blöcken gemacht. Das hatte gut funktioniert und ergab halbwegs sauberen Code, weil Du quasi das Konzept des SVOs bis runter zur letzten Stufe durchziehen kannst. Allerdings wurde das System in den letzten Unterteilungsstufen schon ziemlich ineffizient. Daher baue ich das gerade auf 8x8x8-Blöcke um, die ich einzelbit-komprimiert mit Palette speichere. 8er-Blöcke sind nach meiner Überlegung ein guter Kompromiss zwischen Verwaltungskosten und Sparpotential bei komplett einheitlichen Blöcken, aber das kann bei Dir ganz anders aussehen. Je nachdem, welche Geometrie Du abbilden willst.

2) Die Anzahl VertexBuffer ist der GPU völlig wurscht. 300 oder auch 3000 sind völlig ok. Die Frage ist eher, wie Du die Voxel prinzipiell rendern willst. Willst Du raycasten? Willst Du splatten? Du solltest damit unbedingt rumspielen und Experimente machen. Nach meiner Erfahrung haben speziell Low-End-Grafikkarten extreme Probleme mit den Datenmassen, die mit Voxelwelten einhergehen, egal welche Methode Du wählst.

3) Wenn Du die Datenmassen einmal beherrschst, ist das Streaming das kleinste Problem. Speichere die Welt einfach als Chunks ab - ich nehme dafür z.B. 1024er oder 2048er-Blöcke - und lade die halt einzeln nach. Du könntest auch die einzelnen SVO-Unterteilungsstufen pro Chunk separat lesen und somit entfernte Chunks nur in niederer Detailstufe im Speicher halten. Das hängt dann sehr von Deiner LOD-Strategie ab.

Allgemein: nimm Dir Zeit zum Experimentieren. Du wirst einer Menge Probleme begegnen, an die Du jetzt noch nichtmal denkst.

[mike7774]

Ja, hab auch schon bemerkt dass das ganze nicht so einfach ist^^

Bin jetzt seit ein paar Monaten an der Thematik Voxelgrafik dran, hab mich vorher eigentlich nur mit "einfacher Vectorgrafik" beschäftigt. Aber weil die Volumengrafik mit der immer besser werdenden Hardware immer interessanter wird führt meiner Meinung nach kein Weg dran vorbei.

Fürs Rendering ist meine momentanr Ansatz das Raycasting, aber muss mich da noch ein wenig reinlesen.

Danke schonmal für die Antworten, damit sind schonmal ein paar Probleme gelöst die mir so durch den Kopf schwirrten.

[Schrompf]

Und auch wichtig: zeige Bilder, sobald Du was erreicht hast :-) Ich bin neugierig.

[mike7774]

Momentan sieht das ganze noch so aus (ja ich weiß, schön ist anders, aber das ist nur ein erster sehr früher Test).



Das ganze verwendet noch keinerlei Optimierungen (deswegen auch die niedrige FPS) und arbeitet mit Voxelchunklisten. Das "Terrain" wird momentan noch aus einer festgelegten Heightmap erzeugt, später sollen aber prozedurale Heightmaps erzeugt werden. Der nächste Schritt wäre halt das ganze in SVO's zu packen, den Trianglecount zu verringern (große Flächen weniger Dreiecke, etc.) und unendlich zu machen, nur häng ich da derzeit noch ein wenig.

[Schrompf]

Nuja, das ist doch schon ein Anfang. Aber das ist doch kein Raycasting, oder?

[Artificial Mind]

Die Artefakte im Hintergrund sehen stark nach Schrittweitenprobleme aus, oder?

[mike7774]

Nuja, das ist doch schon ein Anfang. Aber das ist doch kein Raycasting, oder?

Nope ist kein Raycasting, das ganze ist halt noch in einer sehr frühen Phase und mehr ein Test überhaupt irgendetwas auf den Bildschirm zu bekommen...

Die Artefakte im Hintergrund sehen stark nach Schrittweitenprobleme aus, oder?

Die Artefakte kommen vom falschen (in dem Fall, fehlenden) Hidden Face Removal, die Methode hat noch Probleme mit transparenten Teilen.

Das Programm macht halt momentan nur folgendes: Erstellen einer Liste von Voxelchunks, prüfen wo sich Würfel befinden und an der Stelle Geometrie erstellen und jeden Chunk mit einem DrawPrimitive Aufruf rendern.
Wie ich das Verstanden habe müsste ich jetzt vor diese ganze Methode einen SVO setzen und die Daten die ich daraus bekomme an diesen Teil des Programms übergeben, oder liege ich damit komplett daneben?

[Schrompf]

Wie erstellst Du denn die Geometrie? Das ist doch das Erzeugen von Vertexdaten, um sie dann in ein VBO zu schreiben und damit zu rendern.

Das Knicken der Würfelseiten zu benachbarten besetzten Voxels bringt Dir übrigens massiv Performance-Gewinn. Aber falls Du mit OpenGL Immediate Mode renderst, dürfte auch der Einsatz von VBOs bereits ordentlich Performance bringen.

[mike7774]

Genau die Geometrie sind Vertexdaten die dann in einen VertexBuffer gepackt werden (DirectX), es wird überprüft ob eine Würfelseite verdeckt ist, falls nicht werden für die Seite Vertex/Index Daten erstellt.

Was die Performance anbelangt, wird mit Hidden Face Removal die Performance verbessert (in der aktuellen Demo verdoppelt). Frustrum Culling ist noch nicht ganz drinnen weil ich das warscheinlich über den Octree machen werde, habs derzeit für die Chunks drinnen aber deaktiviert.

[mike7774]

Mal ein kleines Update.

Habe jetzt ein bisschen herumgespielt und ein paar neue Optimierungen eingebaut. Hidden Face Removal entfernt jetzt die verdeckte Geometrie und dank Frustrum Culling werden nur mehr sichtbare Chunks gerendert.
Als nächstes werde ich Face Merging einbauen um die Geometrie weiter zu vereinfachen, nur sehe ich da schon das nächste Problem dass ich für jeden Chunk einen eigene Vertex/Index Pool habe und damit das ganze (noch) nicht soweit Optimieren kann wie ich will...

Auch weiß ich noch nicht wie ich den Octree einbauen kann, momentan rendere ich noch einen Voxelchunkcluster (ka wie man das nennt, ich nenns mal so).

[Schrompf]

Es geht vorwärts, sehr gut! Aber wenn Du von einem einzelnen VertexBuffer aus 60k Dreiecke renderst, müsstest Du auf heutiger Hardware doch ~500 fps bekommen. Was passiert da noch im Hintergrund?

Und übrigens: ein Voxel von 10cm³ hat bei mir eine Kantenlänge von 2,15cm. Das sind bereits nach wenigen Metern Sichtweite solche extremen Massen an Voxeln, dass Du Dir evtl. zuerst über wirklich gutes Level Of Detail Gedanken machen solltest. Und erprobe frühzeitig mehrere Voxelsorten, weil das auch alle nachfolgenden Verarbeitungsschritte beeinflusst. Das Zusammenfassen zu größeren Flächen z.B. muss ja an Voxeltyp-Grenzen absetzen.

[mike7774]

Sooo, hab das ganze jetzt mal soweit das alles über einen Octree läuft und das Programm 64x64x64 Voxelchunks mit je 16x16x16 Voxel verarbeiten und darstellen kann.
Jetzt habe ich aber das Problem mit meinem 3D Daten Management. Momentan verwende ich Vertex-/Indexarrays (ungefähr so - Vertices[maxArray][maxVertexCount]) in welche ich die Geometrie schreibe nachdem festgestellt wurde welche Voxel im Sichtfeld liegen.

Funktioniert auch ganz gut, mit dem kleinen Problem das ich meine Arrays nur füllen, aber spezifische Daten nicht mehr entfernen kann. Die einzige Möglichkeit ist die gesamten Arrays zu leeren und neu zu füllen, was zu unschönen Effekten führt. Habe auch versucht für jeden Chunk ein eigenes Array zu erstellen was aber immer wieder dazu führt das mir das Programm abstürzt (scheinbar ein Out of Memory Fehler, kann aber eigentlich nicht sein da mein System genügend Grafikspeicher haben sollte, und die Arrays gelöscht werden sobald sie nicht mehr im Sichtfeld sind).

Hab auch schon versucht die Geometriedaten zu indizieren (über einen Offset im Array und eine ID der Daten), aber das scheint auch nicht das Optimum zu sein.
Achja, und nach einigen Desigüberlegungen habe ich mich dazu entschlossen kein Raytracing für das Rendern zu verwenden sondern einen Art "Mesh-Creation" aus den Voxeldaten.

Ja, das wäre jetzt so das Problem für das ich Lösungsansätze suche^^

[Artificial Mind]

In absolut fieser Eigenwerbung möchte ich diesen Artikel hier posten: http://upvoid.com/devblog/2013/05/terra ... ontouring/

Dort wird ein wenig der "Dual Contouring"-Ansatz zur "Mesh Extraction" aus Volumendaten beschrieben.

Mit dem Speicher wirst du sehr schnell am Ende sein. Wenn die 64³ Chunks je 16³ komplett ausgereizt werden, bekommst du pro Voxel-Byte ein Gigabyte RAM-Auslastung dazu.

[mike7774]

Ok, hab das Problem behoben, realloc() hat nicht ganz so gearbeitet wie es sollte... hab jetzt für jeden Chunk (wenn er geladen ist) ein eigenes Vertex-/Index Array.
Können die nächsten Probleme ja auf mich zukommen :lol:

[mike7774]

Mit dem Speicher wirst du sehr schnell am Ende sein. Wenn die 64³ Chunks je 16³ komplett ausgereizt werden, bekommst du pro Voxel-Byte ein Gigabyte RAM-Auslastung dazu.

Mein derzeitiger Ansatz ist es nur die Chunks zu laden die auch sichtbar sind und Chunks die nicht sichtbar sind wieder zu entladen, also den Speicher freigeben. Was momentan noch ein wenig die Framerate drückt, aber da kommen noch ein paar Optimierungen rein.

Momentan habe ich ein kleines Problem mit dem Rendering. Ich habe jetzt mehrere Methoden durchprobiert und werde die hier mal aufzählen und die Probleme die ich damit bekomme:

1 Methode: Für jeden Chunk einen eigene Vertex/Index Buffer und einen eigenen DrawPrimitive Aufruf
Problem - egal in welcher Reihenfolge (von hinten nach vorne) ich die Chunks rendere, sie werden "überzeichnet".
Meine Lösungsidee wäre alle Daten zu sammeln, in einen großen Vertex/Indexbuffer zu packen und mit einem einzigen Draw Aufruf alles zu zeichnen, wobei ich aber jedes mal einen Offset für meine Indices hinzuaddieren müsste was ich mir sehr ineffizient vorstelle (und natürlich der Speicherbedarf - Vertex/Index Daten in den Chunks und den Buffern).

2 Methode: Ich sammle alle Daten packe sie in mehrere große Vertex/Indexbuffer (ohne die Daten in den Chunks zu speichern) und rendere sie.
Problem - Meine Buffer werden, je mehr Chunks aktiviert werden, immer größer und die Framerate immer kleiner^^.
Eine Lösungsidee war es die Buffer ab einer bestimmten Größe zu leeren und neu zu füllen, was aber zu unschönen Effekten während des Leerens und Neu-Befüllens geführt hat.

Hat jemand gute Lösungsansätze wie man das ganze effektiv rendern kann, oder Links zu Seiten die sich mit dem Thema beschäftigen.

[Schrompf]

Ich hätte ja zu Methode 1 geraten, weil die praktisch und schnell gemacht ist, wenn die Blöcke sich ändern sollen. Was meinst Du mit "überzeichnen"?

[mike7774]

Ich hätte ja zu Methode 1 geraten, weil die praktisch und schnell gemacht ist, wenn die Blöcke sich ändern sollen. Was meinst Du mit "überzeichnen"?

Bevorzuge auch die 1 Methode weil das Culling so weniger Aufwand benötigt.
Mit "überzeichnen" meine ich das die hinteren Chunks über die vorderen Chunks gerendert werden, also so eine Art Z-Buffer Problem weil jeder Chunk einen eigenen Draw Aufruf hat. Hab schon versucht zu sortieren, aber das Problem besteht weiter. Liegt vermutlich an meiner Kamera Klasse.

[Schrompf]

Wut? Genau dafür wurde der ZBuffer erfunden. Achte aber darauf, dass die Near Clipping Plane nicht zu nah ist und die Far Clipping Plane zu weit weg. Das Verhältnis zwischen den beiden Zahlen sollte kleiner als ~100.000 sein.

[mike7774]

Ok, es lag an einer zu nahen NearPlane, daran hatte ich nicht gedacht... -.-
Danke Schrompf! War schon am verzweifeln und hab alles mögliche versucht um an dem Fehler vorbeizuarbeiten.

[mike7774]

Hier mal ein kleiner Screen des aktuellen Fortschrittes (ja, momentan ist noch Minecraft Style, aber da kommt noch mehr!)

[Schrompf]

Schönschön, es geht vorwärts!

[mike7774]

Ich verwende jetzt zum Texturieren einen Texture Atlas und hab das "Texture Bleeding" Problem. Hab bereits gegoogelt, aber die Lösungsvorschläge die ich gefunden habe sind eher suboptimal, u.a. einen Rand für jede Textur der bei Anisotroper Filterung 8 Pixel breit wäre und für jede Filter Einstellung eine eigene Textur benötigen würde...
Das sollte ja eigentlich ein häufiges Problem sein, gibts dafür keine Standardmethode (z.b. RenderStates) das ganze zu lösen? Achja, ich verwende Momentan DX9 zum Rendern (ab DX10 gibts das "Bleeding" Problem ja scheinbar nicht mehr), werde aber später noch einen DX10 bzw. DX11 Renderer implementieren.

[Schrompf]

Doch, das gibt's auch unter DX10. Das ist ein ganz normales Phänomen, weil der Texturfilter ja nichts von Deinem Texturatlas weiß und demzufolge einfach von der Stelle samplet, die Du im sagst. Da eine Menge Bildqualität davon abhängt, betreibt die GPU einigen Aufwand beim Samplen und liest da gleich ein mehr oder weniger großes Gebiet rund um den Sample-Punkt. Damit bekommst Du zwangsweise Farben von benachbarten Atlas-Segmenten mit rein, wenn Du samplest. Das sind bis zu +-8 Texel bei Anisotropischem Filter, mal eine Zweierpotenz bei MipMapping. Das kann also beliebig heftig werden.

Einfache Lösung: schalte alle Texturfilter ab. Sieht aber scheiße aus.
Komplexere Lösung: ähnlich farbigen Platz rund um jedes Segment im Texturatlas lassen. Verschwendet Texturplatz.
Meine Lösung: im Vertex- oder Geometrie-Shader ausrechnen, welche MipMap-Stufe wahrscheinlich zum Einsatz kommt, und dann die Texturkoordinaten auf einen Bereich clampen, der um soviel Texel kleiner ist als das ursprüngliche Atlassegment.

Hab ich allerdings bisher nur bei 2D-Grafiken erprobt, aber da funktioniert es tadellos.

[Slin]

Einen Texturatlas nutzt man ja normalerweise um den Overhead durch das ständige neu setzen von Texturen zu reduzieren. Die moderne Lösung für das Problem scheinen Array Texturen zu sein, die gibt es aber soweit ich weiß erst in DX10, oder sogar erst in 11...
Um an deinen Atlas angepasste Mipmaps führt nichts drumherum ansonsten ist dieses Paper eigentlich noch ganz interessant, da es Lösungen für die meisten Probleme vorstellt: ftp://download.nvidia.com/developer/NVT ... epaper.pdf

[mike7774]

Einfache Lösung: schalte alle Texturfilter ab. Sieht aber scheiße aus.
Komplexere Lösung: ähnlich farbigen Platz rund um jedes Segment im Texturatlas lassen. Verschwendet Texturplatz.
Meine Lösung: im Vertex- oder Geometrie-Shader ausrechnen, welche MipMap-Stufe wahrscheinlich zum Einsatz kommt, und dann die Texturkoordinaten auf einen Bereich clampen, der um soviel Texel kleiner ist als das ursprüngliche Atlassegment.

Ja, das sind so die Lösungen die ich beim Googlen herausgefunden habe. Werde vorerst mal nur lineares Filtering verwenden und das Texturproblem aufschieben^^

... Die moderne Lösung für das Problem scheinen Array Texturen zu sein, die gibt es aber soweit ich weiß erst in DX10, oder sogar erst in 11...

Bin auch auf das Thema Array Texturen gestoßen, aber dazu findet man fast nur Methoden für OpenGL.

Aber mal ein bisschen was anderes - Lässt sich Face-Merging mit Texturatlas Texturierung kombinieren? Wenn ich das ganze so durchdenke finde ich keine Möglichkeit.

[Schrompf]

Nein, das wird knifflig. Zumindest die Eingaben für den PixelShader müssen an der Materialkante geändert werden. Das machst Du üblicherweise ja durch neue Vertices. Du könntest aber auch einen Texture Index auf eine Textur schreiben und jeder Würfelseitenfläche Texturkoordinaten mitgeben, dann kannst Du das live im PixelShader sampeln.

[mike7774]

Dachte mir schon das falls es funktioniert das ganze nicht ganz einfach ist... Aber der Vertexcount ist momentan eh eine meiner kleineren Sorgen, im Gegensatz zum Laden und Erstellen der Chunks...

[mike7774]

Soo, hätte mal wieder eine Frage bzgl. eines Problems. :D
Und zwar geht es um das View Frustum Culling. Das ganze funktioniert nicht ganz wie es sollte, ich beschreibe mal wie das ganze funktioniert.
Ich verwende einen Octree für das Culling, erstelle mir die Planes und die Eckpunkte des Frustums und habe eine "BoxInFrustum" sowie eine "FrustumInBox" Methode um herauszufinden welche Chunks gerendert werden sollen. Das Problem ist, dass ich scheinbar False Negative Werte zurückbekomme (hatte zuerst nur BoxInFrustum Culling, nachdem ich FrustumInBox Culling hinzugefügt hatte wurde es besser aber es sind trotzdem noch Fehler), und zwar werden mir Chunks zu früh ausgeblendet.
Die Methoden sollten fehlerfrei sein, die Werte im Octree sollten auch stimmen, also vermute ich das ich irgendetwas übersehe.
Hoffe ich habe das Problem gut genug beschrieben, den Code hier zu posten wäre zu unübersichtlich.

[Schrompf]

Warum unübersichtlich? Ein Frustum besteht aus 5 Ebenen. Eine Box aus 8 Eckpunkten. Eine Box ist im einfachsten Fall nur dann nicht im Frustum, wenn alle 8 Ecken der Box jenseits der selben Ebene sind.