Speichern von Voxeln für eine Voxel-Engine in C ++

9

Ich versuche, eine kleine Voxel-Engine zu schreiben, weil es Spaß macht, aber ich habe Mühe, den besten Weg zu finden, um die tatsächlichen Voxel zu speichern. Ich bin mir bewusst, dass ich Blöcke benötigen werde, damit ich nicht die ganze Welt im Gedächtnis haben muss, und ich bin mir bewusst, dass ich sie mit angemessener Leistung rendern muss.

Ich lese über Oktrees und nach meinem Verständnis beginnt es mit 1 Würfel, und in diesem Würfel können 8 weitere Würfel sein, und in all diesen 8 Würfeln können weitere 8 Würfel usw. sein. Aber ich denke nicht, dass dies zu meiner Voxel-Engine passt, weil Meine Voxelwürfel / -gegenstände haben alle genau die gleiche Größe.

Eine andere Möglichkeit besteht darin, einfach ein Array mit einer Größe von 16 * 16 * 16 zu erstellen und dies zu einem Block zu machen, und Sie füllen es mit Elementen. Und Teile, in denen keine Elemente vorhanden sind, haben den Wert 0 (0 = Luft). Aber ich fürchte, das wird viel Speicher verschwenden und nicht sehr schnell sein.

Eine andere Option ist ein Vektor für jeden Block, und füllen Sie ihn mit Würfeln. Und der Würfel hält seine Position im Stück. Dies spart Speicher (keine Luftblöcke), verlangsamt jedoch die Suche nach einem Würfel an einer bestimmten Stelle erheblich.

Ich kann also keine wirklich gute Lösung finden und hoffe, dass mir jemand dabei helfen kann. Was würden Sie verwenden und warum?

Ein weiteres Problem ist das Rendern. Es ist einfach, aber sehr langsam, jeden Block zu lesen und ihn mit OpenGL an die GPU zu senden. Es wäre besser, ein Netz pro Block zu generieren, aber das bedeutet, dass ich jedes Mal, wenn ich einen Block breche, den gesamten Block neu erstellen muss, was einige Zeit in Anspruch nehmen kann und einen kleinen, aber spürbaren Schluckauf verursacht, den ich natürlich auch nicht möchte. Das wäre also schwieriger. Wie würde ich die Würfel rendern? Erstellen Sie einfach alle Cubes in einem Vertex-Puffer pro Chunk und rendern Sie das. Versuchen Sie vielleicht, das in einen anderen Thread einzufügen, oder gibt es einen anderen Weg?

Vielen Dank!

Clonkex
quelle
1
Sie sollten Instanzen zum Rendern Ihrer Cubes verwenden. Ein Tutorial finden Sie hier learnopengl.com/Advanced-OpenGL/Instancing . Zum Speichern der Cubes: Haben Sie starke Speicherbeschränkungen auf der Hardware? 16 ^ 3 Würfel scheinen nicht zu viel Speicher zu haben.
Turms
@Turms Danke für deinen Kommentar! Ich habe keine starken Speicherbeschränkungen, es ist nur ein normaler PC. Aber ich dachte, wenn jeder oberste Teil zu 50% aus Luft besteht und die Welt sehr groß ist, muss ziemlich viel Speicher verschwendet werden. Aber es ist wahrscheinlich nicht viel wie du sagst. Soll ich mich also für 16 * 16 * 16 Chunks mit einer statischen Anzahl von Blöcken entscheiden? Und du sagst auch, ich sollte Instanzen verwenden, ist das wirklich nötig? Meine Idee war es, für jeden Block ein Netz zu generieren, da ich auf diese Weise alle unsichtbaren Dreiecke weglassen kann.
6
Ich empfehle nicht, die Instanzen für die Würfel zu verwenden, wie Turms beschreibt. Dies reduziert nur Ihre Draw-Aufrufe, tut aber nichts für Überzeichnungen und versteckte Gesichter - tatsächlich bindet es Ihre Hände daran, dieses Problem zu lösen, da die Instanzen alle Würfel bearbeiten müssen gleich sein - Sie können versteckte Flächen einiger Würfel nicht löschen oder koplanare Flächen zu größeren einzelnen Polygonen zusammenführen.
DMGregory
Die Wahl des besten Voxelmotors kann eine Herausforderung sein. Die große Frage, die Sie sich stellen müssen, lautet: "Welche Operationen muss ich an meinen Voxeln durchführen?" Das leitet die Operationen. Sie sind beispielsweise besorgt darüber, wie schwierig es ist, herauszufinden, welches Voxel in einem Okt-Baum wo ist. Oct-Tree-Algorithmen eignen sich hervorragend für Probleme, bei denen diese Informationen nach Bedarf beim Durchlaufen des Baums generiert werden können (häufig rekursiv). Wenn Sie bestimmte Probleme haben, bei denen dies zu teuer ist, können Sie andere Optionen in Betracht ziehen.
Cort Ammon
Eine weitere große Frage ist, wie oft Voxel aktualisiert werden. Einige Algorithmen sind großartig, wenn sie Daten vorverarbeiten können, um sie effizient zu speichern, aber weniger effizient, wenn die Daten ständig aktualisiert werden (wie Daten in einer partikelbasierten Flüssigkeitssimulation)
Cort Ammon

Antworten:

23

Das Speichern der Blöcke als Positionen und Werte ist tatsächlich sehr ineffizient. Auch ohne Overhead, der durch die von Ihnen verwendete Struktur oder das verwendete Objekt verursacht wird, müssen Sie 4 verschiedene Werte pro Block speichern. Es wäre nur dann sinnvoll, es über die Methode "Speichern von Blöcken in festen Arrays" (die zuvor beschriebene) zu verwenden, wenn nur ein Viertel der Blöcke fest ist und Sie auf diese Weise nicht einmal andere Optimierungsmethoden berücksichtigen Konto.

Octrees eignen sich hervorragend für voxelbasierte Spiele, da sie sich auf das Speichern von Daten mit größeren Funktionen (z. B. Patches desselben Blocks) spezialisiert haben. Um dies zu veranschaulichen, habe ich einen Quadtree verwendet (im Grunde Octrees in 2d):

Dies ist mein Startsatz mit 32x32 Kacheln, was 1024 Werten entspricht: Geben Sie hier die Bildbeschreibung ein

Das Speichern als 1024 separate Werte scheint nicht so ineffizient zu sein, aber sobald Sie Kartengrößen erreicht haben, die Spielen wie Terraria ähneln, würde das Laden von Bildschirmen mehrere Sekunden dauern. Wenn Sie es auf die dritte Dimension erhöhen, wird der gesamte Speicherplatz im System belegt.

Quadtrees (oder Octrees in 3d) können die Situation verbessern. Um eine zu erstellen, können Sie entweder von Kacheln gehen und sie gruppieren oder von einer riesigen Zelle aus gehen und sie teilen, bis Sie die Kacheln erreichen. Ich werde den ersten Ansatz verwenden, da es einfacher zu visualisieren ist.

In der ersten Iteration gruppieren Sie also alles in 2x2-Zellen. Wenn eine Zelle nur Kacheln desselben Typs enthält, legen Sie die Kacheln ab und speichern nur den Typ. Nach einer Iteration sieht unsere Karte folgendermaßen aus:

Geben Sie hier die Bildbeschreibung ein

Die roten Linien markieren, was wir speichern. Jedes Quadrat ist nur 1 Wert. Dies reduzierte die Größe von 1024 auf 439, was einem Rückgang von 57% entspricht.

Aber du kennst das Mantra . Gehen wir noch einen Schritt weiter und gruppieren diese in Zellen:

Geben Sie hier die Bildbeschreibung ein

Dadurch wurde die Anzahl der gespeicherten Werte auf 367 reduziert. Das sind nur 36% der ursprünglichen Größe.

Sie müssen diese Teilung offensichtlich durchführen, bis alle 4 benachbarten Zellen (8 benachbarte Blöcke in 3d) in einem Block in einer Zelle gespeichert sind und im Wesentlichen einen Block in eine große Zelle konvertieren.

Dies hat auch einige andere Vorteile, vor allem bei Kollisionen. Möglicherweise möchten Sie jedoch einen separaten Octree dafür erstellen, der sich nur darum kümmert, ob ein einzelner Block fest ist oder nicht. Auf diese Weise können Sie die Kollision nicht für jeden Block in einem Block überprüfen, sondern nur gegen die Zellen.

Bálint
quelle
Danke für deine Antwort! Es scheint, dass Octrees der richtige Weg sind. (Da meine Voxel-Engine 3D sein wird) Ich habe einige Fragen, die ich gerne stellen möchte: Ihr letztes Bild zeigt die schwarzen Teile mit größeren Quadraten, da ich beabsichtige, ein Minecraft wie dieses zu haben Motor, in dem Sie das Voxel-Terrain modifizieren können, würde ich es vorziehen, alles, was einen Block hat, gleich groß zu halten, da dies sonst die Dinge sehr kompliziert machen würde, ist das möglich, oder? (Ich würde natürlich die Leer- / Luftschlitze natürlich vereinfachen.) Zweitens Gibt es eine Art Tutorial, wie man einen Octree programmiert? Vielen Dank!
7
@ appmaker1358 das ist überhaupt kein problem. Wenn der Spieler versucht, einen großen Block zu ändern, teilen Sie ihn in diesem Moment in kleinere Blöcke auf . Es ist nicht nötig, 16x16x16-Werte von "Rock" zu speichern, wenn Sie stattdessen sagen könnten "dieser ganze Teil ist fester Rock", bis dies nicht mehr wahr ist.
DMGregory
1
@ appmaker1358 Wie DMGregory sagte, ist das Aktualisieren der in einem Octree gespeicherten Daten relativ einfach. Alles, was Sie tun müssen, ist die Zelle zu teilen, in der die Änderung stattgefunden hat, bis jede Unterzelle nur einen einzigen Blocktyp enthält. Hier ist ein interaktives Beispiel mit einem Quadtree . Eine zu generieren ist ebenfalls einfach. Sie erstellen eine große Zelle, die den Block vollständig enthält, und gehen dann rekursiv jede Blattzelle durch (Zellen ohne untergeordnete Elemente). Überprüfen Sie, ob der Teil des Geländes, den es darstellt, mehrere Arten von Blöcken enthält. Wenn ja, unterteilen Sie die Zelle
Bálint
@ appmaker1358 Das größere Problem ist eigentlich das Gegenteil: Stellen Sie sicher, dass das Octree nicht mit nur einem Block voller Blätter ist, was in einem Spiel im Minecraft-Stil leicht passieren kann. Es gibt jedoch viele Lösungen für das Problem - es geht nur darum, das auszuwählen, was Sie für angemessen halten. Und es wird nur dann zu einem echten Problem, wenn viel gebaut wird.
Luaan
Octrees sind nicht unbedingt die beste Wahl. Hier ist eine interessante Lektüre: 0fps.net/2012/01/14/an-analysis-of-minecraft-like-engines
Polygnome
7

Es gibt Oktrees, um genau das von Ihnen beschriebene Problem zu lösen und eine dichte Speicherung von Daten mit geringer Dichte ohne große Suchzeiten zu ermöglichen.

Die Tatsache, dass Ihre Voxel die gleiche Größe haben, bedeutet nur, dass Ihr Octree eine feste Tiefe hat. z.B. Für einen 16x16x16-Block benötigen Sie höchstens 5 Baumstufen:

  • Blockwurzel (16x16x16)
    • Oktant der ersten Stufe (8x8x8)
      • Oktant der zweiten Stufe (4x4x4)
        • Oktant der dritten Stufe (2x2x2)
          • einzelnes Voxel (1x1x1)

Dies bedeutet, dass Sie höchstens 5 Schritte ausführen müssen, um herauszufinden, ob sich an einer bestimmten Position im Block ein Voxel befindet:

  • Blockwurzel: Ist der gesamte Block der gleiche Wert (z. B. die gesamte Luft)? Wenn ja, sind wir fertig. Wenn nicht...
    • Erste Stufe: Ist der Oktant, der diese Position enthält, alle der gleiche Wert? Wenn nicht...
      • zweite Stufe...
        • dritte Stufe ...
          • Jetzt adressieren wir ein einzelnes Voxel und können seinen Wert zurückgeben.

Viel kürzer als das Scannen von 1% des Weges durch ein Array von bis zu 4096 Voxeln!

Beachten Sie, dass wir damit die Daten überall dort komprimieren können, wo ein vollständiger Oktant mit demselben Wert vorhanden ist - unabhängig davon, ob es sich bei diesem Wert ausschließlich um Luft oder nur um Gestein oder etwas anderes handelt. Nur dort, wo Oktanten gemischte Werte enthalten, müssen wir bis zur Grenze der Einzelvoxel-Blattknoten weiter unterteilen.


Um die Kinder eines Stücks anzusprechen, gehen wir normalerweise in der Reihenfolge Morton vor , ungefähr so:

  1. X- Y- Z-
  2. X-Y-Z +
  3. X- Y + Z-
  4. X- Y + Z +
  5. X + Y- Z-
  6. X + Y- Z +
  7. X + Y + Z-
  8. X + Y + Z +

Unsere Octree-Knotennavigation könnte also ungefähr so ​​aussehen:

GetOctreeValue(OctreeNode node, int depth, int3 nodeOrigin, int3 queryPoint) {
    if(node.IsAllOneValue)
        return node.Value;

    int childIndex =  0;
    childIndex += (queryPoint.x > nodeOrigin.x) ? 4 : 0;
    childIndex += (queryPoint.y > nodeOrigin.y) ? 2 : 0;
    childIndex += (queryPoint.z > nodeOrigin.z) ? 1 : 0;

    OctreeNode child = node.GetChild(childIndex);

    return GetOctreeValue(
                child, 
                depth + 1,
                nodeOrigin + childOffset[depth, childIndex],
                queryPoint
    );
}
DMGregory
quelle
Danke für deine Antwort! Es scheint, dass Octrees der richtige Weg sind. Ich habe jedoch zwei Fragen: Sie sagen, Octrees sind schneller als das Durchsuchen eines Arrays, was richtig ist. Aber ich würde das nicht tun müssen, da das Array statisch sein könnte, was bedeutet, dass ich berechnen kann, wo sich der benötigte Würfel befindet. Warum sollte ich also scannen müssen? Zweite Frage, in der letzten Stufe des Octree (1x1x1), woher weiß ich, welcher Würfel wo ist, denn wenn ich es richtig verstehe und der Octree-Knoten 8 weitere Knoten hat, woher weißt du, welcher Knoten zu welcher 3D-Position gehört ? (Oder soll ich mich daran erinnern?)
Ja, Sie haben in Ihrer Frage bereits den Fall eines umfassenden Arrays von 16 x 16 x 16 Voxeln behandelt und den Speicherbedarf von 4 KB pro Block (vorausgesetzt, jede Voxel-ID ist ein Byte) als übermäßig abgelehnt. Die von Ihnen erwähnte Suche erfolgt beim Speichern einer Liste von Voxeln mit einer Position, sodass Sie die Liste durchsuchen müssen, um das Voxel an Ihrer Zielposition zu finden. 4096 ist hier die Obergrenze dieser Listenlänge - normalerweise ist sie kleiner als diese, aber im Allgemeinen immer noch tiefer als eine entsprechende Octree-Suche.
DMGregory