Welche Datenstruktur soll zur Darstellung des Voxel-Terrains verwendet werden?

18

Laut der Wikipedia-Seite über Voxel wird "[...] die Position eines Voxels auf der Grundlage seiner Position relativ zu anderen Voxeln (dh seiner Position in der Datenstruktur, die ein einzelnes volumetrisches Bild ausmacht) abgeleitet."

Wie soll man eine solche Datenstruktur implementieren? Ich habe über ein Octree nachgedacht, aber ich frage mich, ob es noch etwas gibt, von dem ich noch nie gehört habe.

pwny
quelle
1
Diese Frage ist etwas schwierig zu stellen, da sie stark davon abhängt, welche Daten Ihre Voxeldaten benötigen. Dinge wie, wie voll das Voxel ist, wie es aussieht, usw. werden ziemlich davon abhängen, was Sie tun. Zweitens muss sich die Datenstruktur für einen Hochgeschwindigkeitszugriff eignen, um die Daten in Echtzeit zu manipulieren und anschließend zu aktualisieren. Wie man die Speicherstruktur pro Voxel niedrig hält und wie man schnell auf Daten zugreift / manipuliert, sind die wichtigsten technischen Herausforderungen Ziemlich zielgerichtet bei der Arbeit mit Voxel-Motoren. Keine Antwort, also ein Kommentar.
James

Antworten:

14

Zuerst. Schreiben wir, was wir über jedes Voxel wissen:

voxel = (x, y, z, color) // or some other information

Allgemeine Lagerung

Der allgemeine Weg ist einfach:

set of voxels = set of (x,y,z, color)

Beachten Sie, dass das Triplett (x, y, z) jedes Voxel eindeutig identifiziert, da Voxel ein Punkt im Raum ist und auf keinen Fall zwei Punkte einen Platz einnehmen (ich glaube, es handelt sich um statische Voxeldaten).

Für einfache Daten sollte es in Ordnung sein. Es handelt sich aber keineswegs um eine schnelle Datenstruktur.

Das Rendern erfolgt AFAIK mit dem Scanline-Algorithmus. Toms Hardware-Artikel über Voxel enthält ein Bild des Scanline-Algorithmus .

Schnelle Suche

Wenn eine schnelle Suche erforderlich ist, ist die schnellste Datenstruktur für die Suche Hash (auch Array, Karte ... genannt). Also muss man daraus Hasch machen. Naiv wollen wir also nur den schnellsten Weg, um ein beliebiges Element zu erhalten:

array [x][y][z] of (color)
  • Dies hat O (1) zum Nachschlagen des Voxels nach x-, y-, z-Koordinaten.

  • Das Problem ist, dass der Platzbedarf O (D ^ 3) ist, wobei D der Bereich jeder x-, y- und z-Zahl ist (vergessen Sie die reelle Zahl, denn wenn es Zeichen wären, die einen Bereich von 256 Werten haben, gäbe es 256 ^ 3 = 2 ^ 24 == 16 777 216 Elemente im Array).

Aber es kommt darauf an, was Sie mit Voxeln machen wollen. Wenn Rendern das ist, was Sie wollen, dann ist es wahrscheinlich dieses Array, was Sie wollen. Aber das Problem der Lagerung bleibt immer noch ...

Wenn die Lagerung das Problem ist

Eine Methode ist die Verwendung der RLE-Komprimierung im Array. Stellen Sie sich eine Voxelscheibe vor (eine Voxelmenge, bei der Voxel einen konstanten Koordinatenwert haben ... wie zum Beispiel eine Ebene mit z = 13). Ein solches Stück Voxel würde wie eine einfache Zeichnung in MSPaint aussehen . Ich würde sagen, das Voxelmodell belegt normalerweise einen Bruchteil aller möglichen Plätze (D ^ 3-Raum aller möglichen Voxel). Ich glaube, dass "nimm ein Paar aus einem Triplett von Koordinaten und komprimiere die verbleibende Achse" den Trick machen würde (zum Beispiel nimm [x] [y] und komprimiere für jedes Element alle Voxel auf der z-Achse bei gegebenem x, y. sollte es 0 bis wenige Elemente geben, würde RLE hier gut tun):

array [x][y] of RLE compressed z "lines" of voxel; each uncompressed voxel has color 

Eine andere Methode zur Lösung des Speicherproblems wäre, anstelle eines Arrays die Baumdatenstruktur zu verwenden:

tree data structure  = recursively classified voxels
for octrees: recursively classified by which octant does voxel at (x,y,z) belong to
  • Octree, wie von Nick erwähnt. Es sollte Voxel komprimieren. Octree hat sogar eine anständige Geschwindigkeit für das Nachschlagen, ich denke, es ist ein O (log N), wobei N die Anzahl der Voxel ist.
  • Octree sollte in der Lage sein, anständig beliebige Voxeldaten zu speichern.

Wenn Voxel eine vereinfachte Höhenkarte sind, können Sie genau das speichern. Oder Sie können Parameter für Funktionen speichern, die die Höhenkarte generieren, oder sie prozedural generieren ...

Und natürlich können Sie alle möglichen Ansätze kombinieren. Aber übertreiben Sie es nicht, es sei denn, Sie testen, dass Ihr Code funktioniert und messen, dass er WIRKLICH schneller ist (es lohnt sich also, ihn zu optimieren).

TL; DR

Anders als Octrees ist RLE-Komprimierung mit Voxeln, Google "Voxlap", "Ken Silverman" ...

Ressourcen

Es gibt eine Liste von Ressourcen und Diskussionen darüber, wie ein schneller Voxel-Renderer erstellt werden kann, einschließlich Artikel und Quellcode .

user712092
quelle
1
"Wenn der Speicher das Problem ist": Sie können auch VTC ( oss.sgi.com/projects/ogl-sample/registry/NV/… ) oder DXT-Komprimierung verwenden
KindDragon
@KindDragon Danke für diese Information. :) Das ist eine sehr gute Idee.
user712092
Der Ressourcenlink ist nicht aktiv.
Ezequiel
4

Es gibt zwei verschiedene Datenstrukturaspekte, über die sie möglicherweise sprechen.

Array-Strukturen

Wenn Sie auf ein Element eines Arrays mit einer beliebigen Anzahl von Dimensionen verweisen, berücksichtigen Sie, dass das Array selbst nach dem Übergeben der Indizes (z. B. myArray[4][6][15]) weiß, was sich an dieser Stelle befindet. Wenn es sich an diesem Ort um ein Voxel handelt, muss dieses Voxel seine eigenen x-, y- und z-Koordinaten nicht zusätzlich aufzeichnen. Das Array, das das Voxel enthält, gibt den Weltort implizit basierend auf dem Array-indizierten Ort an.

Der Grund dafür ist, dass die für diese Art des Arrayzugriffs verwendete Zeigerarithmetik von Natur aus schnell ist und im Allgemeinen die Grundlage für die meisten schnellen (oft als "native" bezeichneten) Arrays in verschiedenen Sprachen bildet. Der Nachteil dieser Arrays ist, dass sie Elemente gleicher Größe in Bytes aufweisen müssen, damit die Zeigerarithmetik anwendbar ist.

Octrees

(Ich stelle dies als zweites fest, da dies weniger wahrscheinlich ist, worauf sich Wikipedia bezieht, und Voxel-Implementierungen die Verwendung von Octrees nicht erfordern, obwohl fast alle modernen Octrees verwenden.)

Der Wurzelknoten eines Octrees ist ein einzelner, ungeteilter Würfel. Lassen Sie uns ein Beispiel aufstellen. Angenommen, die Wurzel Ihres Octrees, die Mitte des Würfels, befindet sich {0, 0, 0}im 3D-Raum. Sobald Sie anfangen, Objekte in diesem Raum zu platzieren (sprich: mehr als ein Objekt), ist es Zeit, den Octree weiter zu unterteilen. Hier teilen Sie in 8 ( Okt- ) auf, indem Sie es in 3 Ebenen aufteilen , wobei diese Ebenen die xy-, xz- und yz-Ebenen sind. Ihr ursprünglicher Würfel enthält jetzt genau 8 kleinere Würfel. Jeder dieser Unterknoten ist als Versatz zum zentralen übergeordneten Würfel positioniert . Das heißt, dass zum Beispiel der Würfel, der im positiven XYZ-Oktanten liegt, einen Versatz vom Mittelpunkt des übergeordneten / enthaltenden Würfels von genau hat{root.width / 4, root.height / 4, root.depth / 4}. Anstatt für jeden Unterknoten eine absolute Position anzugeben, ist es logischer, den übergeordneten Knoten als Ursprung des Kinderraums zu betrachten. So funktionieren Szenendiagramme auch.

Es ist einfach genug, dies in einer 2D-Zeichnung zu sehen, in der Sie ein Quadrat zeichnen und es in 4 gleiche Bereiche unterteilen. Wenn, wie bei unserem Octree-Wurzelknoten, die Mitte des übergeordneten Quadrats als betrachtet {0, 0}würde, wären dies die 4 Zentren der untergeordneten Quadrate

{root.width / 4, root.height / 4}, {-root.width / 4, root.height / 4}, {root.width / 4, -root.height / 4}, {-root.width / 4, -root.height / 4}

... In Bezug auf ihre Eltern - das gleiche Prinzip wie in 3D.

Ingenieur
quelle
Vielen Dank für Ihre Antwort. In meinem Fall würden einige große Teile des Geländes aus dem gleichen Voxeltyp bestehen, weshalb ich über Octrees nachdachte (ein großer Teil müsste nicht unterteilt werden). Ich werde das 3D-Array jedoch ausprobieren, da es einfacher zu implementieren ist. Ich bin mir sicher, dass ich es schaffen kann, die Implementierungsdetails meiner Geländeklasse so weit zu abstrahieren, dass es nicht so schwer ist, die Implementierung zu wechseln, wenn dies erforderlich ist.
Mittwoch,
Bitte. Ich würde auf jeden Fall empfehlen, sich mit Octrees zu befassen, die wirklich nicht schwer zu verstehen sind. Aber ja, Ihr Ansatz macht vorerst Sinn. Es lohnt sich sicherlich, ein erstes Prototyping mit einem 3D-Array durchzuführen.
Ingenieur
Eine ausführliche Beschreibung der Implementierung von Octrees mit einigen nützlichen Hinweisen finden Sie in Intels Artikel " Extending the STL for Games ".
Martin Foot
1

Sie können RLE verwenden. Sie können jedoch SVO (Sparse Voxel Octree) verwenden, id Tech 6 verwendet SVO. Ein SVO ist eine 3D-Computergrafik-Rendering-Technik, die einen Raycasting- oder manchmal einen Raytracing-Ansatz in eine Octree-Datendarstellung verwendet.

Die Technik variiert etwas, beruht jedoch im Allgemeinen auf der Erzeugung und Verarbeitung der Hülle von Punkten (spärlichen Voxeln), die angesichts der Auflösung und Größe des Bildschirms sichtbar sind oder sichtbar sein können.

Verwenden Sie Raycasting, weil es schneller ist.

RealTimeGraph9999
quelle
0

Im Allgemeinen können Sie eine 3D-Datenstruktur für das Gelände vermeiden. Sie können stattdessen eine Höhenkarte verwenden. Dies kann zur Laufzeit sehr kostengünstig und effizient voxelisiert werden. In der Regel lohnt es sich (meiner Erfahrung nach), die minimale Höhe nachzuverfolgen, die Sie in jeder Spalte rendern müssen, und manchmal auch Start-Stopp-Top-Winkel, damit Sie auch die Spalten der Rückseite aussortieren können.

Hier ist eine, die ich vor langer Zeit erstellt habe: http://sites.google.com/site/williamedwardscoder/spinning-voxels-in-flash

Wenn Ihr Terrain eine geringe Anzahl von Überhängen, Höhlen oder anderen Merkmalen aufweist, die nicht durch eine Höhenkarte dargestellt werden können, können Sie Löcher in Ihrer Höhenkarte und eine alternative Darstellung haben, z. B. echte 3D-Voxelobjekte, die nur die lokalisierten Stellen ausfüllen, an denen die Laufzeitkosten anfallen Es ist garantiert.

Sparse Voxel-Darstellungen sind es wert, wenn Sie große wahre Voxel-Welten haben. John Carmack spricht sie seit einigen Jahren an ...

Wille
quelle
Ich dachte auch über Höhenkarten nach, aber ein paar Dinge trieben mich von ihnen weg. Die Sache ist, dass in meinem Fall das Gelände keineswegs wirklich groß oder sehr kompliziert ist (man denke an ein Terrain vom Labyrinthtyp, sehr kartesisch). Ich möchte auch, dass ein Teil des Geländes zerstörbar ist oder dass der Benutzer das Gelände durch die Konstruktion beeinflusst. Dies kann dazu führen, dass der Spieler "Tunnel" im Gelände erstellt, deren Darstellung mit einer Höhenkarte komplizierter erscheint.
Pwny