Einstieg in Spieleprogrammierung mit Voxels

[DestiX]

Hi Leute!

Ich wäre in letzter Zeit sehr daran interessiert ein Spiel, wenn nicht sogar eine Engine, auf Voxels basierend, zu programmieren.
Nun hatte ich mit 3D Echtzeit Programmierung aber noch nie wirklich so viel am Hut.
Deswegen wollte ich hier nur mal fragen, was zu lernen nötig wäre, um die besagte Engine / das Spiel zu entwickeln. Erfahrung habe ich bisher eigentlich nur in Programmentwicklung und Bildverarbeitung. Hab auch schon mal ein bisschen mit der Unity Engine rumexperimentiert :)
Zeit hab ich auch genug ;)

MfG,
DestiX

[Top-OR]

Moin Destix.

Was willst du den voxeln? "Nur" das Terrain (a la Comanche) oder auch solche Geschichten wie Charaktere (wie in Lands of Lore 3)?

Das ist ja grundsätzlich ein interessantes Konzept. Ich glaube, das "Problem" an Voxeln ist der u.U. enorme Speicheraufwand und dass du eben mit einem gewissen Grad an Artefaktbildung leben musst. Weiterhin würde ich mich mal aus dem Fenster lehnen und sagen, dass die ne Grafikkarte da so ohne weiteres auch nicht weiterhelfen wird (es sei denn, unsere Shadermagier belehren mich eines Besseren), d.h. du wirst soviel CPU (und Bandbreite) brauchen, wie du in den Rechner kippen kannst.

Wie kommste auf die Idee? Magste den Look?

[DestiX]

Du Voxels sollten eigentlich garnicht groß hochauflößend sein. Gerade noch so, dass das Terrain vielleicht nicht wie in z.B. Minecraft nur aus Blöcken besteht.
Eigentlich wäre es am Anfang auch besser, nur das Terrain aus Voxels bestehen zu lassen. Auf die Idee kam ich durch Ace of Spades (http://www.ace-spades.com/). Würde da auch gerne sowas in der Richtung machen... Und ja, ich liebe den Look :)

MfG,
DestiX

[Top-OR]

Hmm, danke liebe GEMA. Kann das Video leider nicht sehen. Aber ich stell mir jetzt mal Comanche/Outcast vor...

Im Prinzip waren das ja "nur" Heightmaps (also keine überhängenden Klippen). Ich hab sowas vor bestimmt 10 Jahren mal gebaut (schön 320x200 unter DOS).
Folgende Links kommen mir von "damals" schwer bekannt vor - ist sicher nicht das State-of-the-Art-Komplettpaket von heute, aber reicht vielleicht aus, um entscheidende Denkanstöße zu geben:

* http://www.flipcode.com/archives/Realti ... tion.shtml
* http://archive.gamedev.net/reference/ar ... cle655.asp
Der ist auch noch schön:
* http://www.codermind.com/articles/Voxel ... rrain.html

Das Konzept ist ja, 2-dimensional über das Bild (Heightmap) zu laufen und zu schauen, welche Pixel (Höhen) man sieht (im Frustum hat). Diese muss man dann als eine Art Säule interpretieren und ein bissel perspektivisch verzerrt (nach hinten kleiner und u.U. [je nach Ansatz] schmaler werdend; geht durch einfache Divisionen) darstellen. Hat son bissel was von Raycasting bzw. ist ne Form davon...

Wer bessere Links hat nur zu - ich bin ein wenig out-of-date ...

[DestiX]

Ok, vielen dank für die schnelle & nette Antwort ;)
Hier haste noch ein Video von besagtem Ace of Spades: http://www.youtube.com/watch?v=38fe2Mt9QQg

Jetzt hab ich aber noch eine Frage:
Wäre es möglich, das mit den von dir beschriebenen Methoden erstellte Terrain in Echtzeit zu verformen / zerstören ? Oder einzelnen Voxels bestimmte Eigenschaften, wie zB Zerstörungsresistenz usw. zuzuschreiben ?
Mit den 3 Arti

[DestiX]

Ok, vielen dank für die schnelle & nette Antwort ;)
Hier haste noch ein Video von besagtem Ace of Spades: http://www.youtube.com/watch?v=38fe2Mt9QQg

Jetzt hab ich aber noch eine Frage:
Wäre es möglich, das mit den von dir beschriebenen Methoden erstellte Terrain in Echtzeit zu verformen / zerstören ? Oder einzelnen Voxels bestimmte Eigenschaften, wie zB Zerstörungsresistenz usw. zuzuschreiben ?
(huch, das waren 2 Fragen...)
Mit den 3 Artikeln bin ich jetz eh erst einmal beschäfftigt ;)

MfG,
DestiX

[Top-OR]

Ich seh gerade in dem Video, dass der sich da nen Tunnel durch den Berg buddelt. Hmm, das geht SO mit Heightmaps natürlich nicht direkt (keine Überhänge) , denn du hast ja nur 2D-Daten, also Höheninformationen ...

Dann müsste man sich schonmal überlegen, wie man son 3D-Array besser darstellt: Hab jetzt aber auch keinen eleganten Ansatz dafür - außer Brute-Force mit nem Uniform-Grid (3D Array x*y*z, wo du dir Infos für jeden Block merkst (da/nicht da/texture/andere Attribute).

Ein solches Modell könnte man höchsten noch mit ner Heightmao befüllen, aber es ist an sich um einiges komplexer als reines "Landschaften/Heightmap-voxeln".
Für sowas hab ich leider kein Tutorial bzw. nen guten Ansatz aus dem Stand ...

Vielleicht hat hier ja noch jemand ne gute Idee - irgend ne Art von Baum vielleicht - ein Octree? In solche Überlegungen spielen dann solche Dinge wie maximale Größe der Welt natürlich auch mit rein.

[DestiX]

Würde es eigentlich viel Rechenleistung brauchen, wenn ich in Unity eine ein Terrain aus lauter Cubes erstelle ? Die könnte man dann in einem 3 dimensionalen Array speichern. Man könnte das Terrain an sich aus einer Highmap erstellen und das ganze dann, wenns fertig generiert ist, in einem 3D Array speichern. Dann könnte man auch Tunnel graben, nich ?
Sorry, falls ich dumme Fragen stelle unso, hab mich noch nie so intensiv damit beschäfftigt ;)

MfG,
DestiX

[Top-OR]

Würde es eigentlich viel Rechenleistung brauchen, wenn ich in Unity eine ein Terrain aus lauter Cubes erstelle ? Die könnte man dann in einem 3 dimensionalen Array speichern.

Das weiß ich nicht, aber es kommt sicher auf die Weltgröße an. Da müssen die Unity-Leute hier mal was zu sagen. Ich hab da nicht mal den Ansatz eines Gefühls dafür ...

Man könnte das Terrain an sich aus einer Highmap erstellen und das ganze dann, wenns fertig generiert ist, in einem 3D Array speichern. Dann könnte man auch Tunnel graben, nich ?

Das meinte ich mit, das 3D-Array kann man durch eine Heightmap zumindest befüllen.

Sorry, falls ich dumme Fragen stelle unso, hab mich noch nie so intensiv damit beschäfftigt ;)

Och wieso, scheint ja nun keine Standard-Aufgabe zu sein...

Dir scheints ja auch eher um den "look" zu gehen, als um die wirkliche technische Umsetzung: Ich denke, mit ein bissel Kreativität bekommst man schon was auf die Beine.

[DestiX]

Ok, dann werd ich mich jetzt erstmal dransetzen.
Danke für deine nette Unterstützung :)

MfG,
DestiX

[joggel]

Letztendlich braucht ma ja nur das 3D-Array, denke ich.
Gabs nicht schonmal einen Thread dazu hier? Oder war das auf Sppro
Würfel die "im" Berg sind, braucht man ja nicht zu rendern...

[Krishty]

Ein 3D-Array wächst aber so unverhältnismäßig stark, dass du es nicht gespeichert bekommst – ein Würfel mit einem Kilometer Seitenlänge würde schon bei einem Byte Information pro Kubikmeter Terrain ein GiB Speicher verbrauchen; normalerweise braucht man deutlich mehr. Eine komplette Spielwelt bekommst du nicht auf deine Festplatte, geschweige denn zum Rendern auf die GPU oder in irgendeiner Weise effizient verarbeitet.

Ich würde eigentlich auf einen Octree ausweichen, der nur die Oberflächenvoxel enthält. Den erweitert man dann, falls irgendwo gegraben wird, mit prozeduralen Daten – wo in 10 m Tiefe ein Stein lag kann sich eh niemand merken. Kann man dann auch gut als Marching Cubes direkt auf der GPU visualisieren. So bildet man das 3D-Problem (das Voxel-Volumen) auf ein 2D-Problem (dessen Oberfläche) ab und bringt es dadurch in berechen- und speicherbare Bereiche.

Ist jetzt aber eine primitive Einschätzung; ich habe mich aber nie intensiv mit Voxeln beschäftigt.

[waigie]

Die Idee mit den dem Octree hat aber einen kleinen Nachteil. Wenn du einen Tunnel durch einen Berg baust kannst du diesen nicht speichern. Zumindest wenn ich das richtig verstanden habe.

Aber bei seinen Beispielen sieht das sehr stark danach aus, als wollte er Würfel als Voxel nutzen. Daher würde ich wohl die Außenhülle der Welt aus Polygonen darstellen. Diese dann in nen KD oder BSP Tree packen und dann die nötigen Volumina mit den Würfeln ausfüllen. Was die Daten angeht wie Textur, Farbe etc wären die dann nur in den Vertices der Polygone vorhanden dazwischen wird interpoliert und zufällig eingestreut. Damit hätte man zumindest die Möglichkeit auch Höhlen zu Graben etc. Und das ganze sollte sich recht gut paralell auf der Grafikkarte berechnen lassen.

[Aramis]

Natuerlich, der Octree zerteilt einfach den Raum rekursiv in immer kleiner werdende Wuerfel. Wenn in einer Region Detailgeometrie erforderlich ist, werden die Wuerfel eben entsprechend fein aufgeloest - das funktioniert in einem Berg wie an seiner Oberflaeche. Der Vorteil ist, dass relativ grosse, gleichfoermige Volumina mit nur wenigen Bytes abhandelbar sind.

So habe ich das jedenfalls verstanden.

[Krishty]

Die Idee mit den dem Octree hat aber einen kleinen Nachteil. Wenn du einen Tunnel durch einen Berg baust kannst du diesen nicht speichern. Zumindest wenn ich das richtig verstanden habe.

Du kannst mit einem Octree allem Raum, den er umschließt, Information zuweisen (indem du die umhüllten Voxel drin speicherst, wie die für die Tunnelwände) oder auch nicht (indem du den entsprechenden Knoten leer lässt). Du speicherst einfach alle Blätter, die die Tunnelwände berühren, und lässt alles andere (die Knoten und Blätter mit Kram, der im Berg drin und deshalb unsichtbar ist und auch die, die ausschließlich den Raum innerhalb des Tunnels umschließen und darum leer sind) leer, undefiniert, als uniformes Volumen definiert o.Ä..

Ich denke, das läuft bei uns beiden auf was Ähnliches hinaus.

[waigie]

Ja ist richtig das ganze Gerede von Oberflächen hat mich irgendwie dazu verleitet das irgendwie falsch zu interpretieren. Natürlich kann man mittels eines Octrees alles machen, ich sollte nicht im Forum schreiben wenn ich mal wieder zu viele Überstunden gemacht habe ...

[Krishty]

Besser einmal zu viel als einmal zu wenig – du warst ja vielleicht nicht der Einzige, der es missverstanden hatte …

[DestiX]

Ok, zu den Octrees:
Kann mir da mal bitte jemand nen Denkanstoß geben ? Ich kann mir nämlich nich so wirklich vorstellen, wie ich damit Voxel Terrain speichern soll ?

Danke schonmal im Vorraus !

MfG,
DestiX

[kimmi]

Du brauchst ja eigentlich nur die Umhüllung beziehunsgweise Oberfläche deines durch Voxel beschriebenden Geländes. Und um diese zu generieren, kannst du einen Octtree benutzen, der diese Geometries diskreditiert. Hier wird beispielsweise ein Verfahren dazu beschrieben.

Das ist zumindest ein Ansatz, den ich kenne.

Gruß Kimmi

[kimmi]

Gerade gesehen: DDraw-basierte Voxelengine . Vielleicht ist die für dich ja interessant.

Gruß Kimmi

[joggel]

Ich gehe nochmal auf das 3D-Array ein^^.
Vlt. könnte man da so rangehen (kurz mal hinge***, und nicht wirklich zu Ende gedacht):

Ich muss ja nicht ein Byte verwenden, um ein Voxel zu identifizieren.
Um nur zu sagen, ob an der Position einer vorhanden ist, reicht ja 1Bit.
Bei 1Km³ ==125.000.000 Bytes ist jetzt nun nicht sooo viel.
Okay, damit ist aber nicht festgehalten, um was für ein Voxel es sich handelt. Also vlt. doch 1Byte pro Voxel (Höhle, Wasser, Baum, etc.).
Bei 1Km³ sind das = 1.000.000.000Bytes ~1GB. Man kann ja auch streamen von der HD was im sichtbaren Bereich läge.

Über ein anderes Array kann man die Elemente der gestreamten Voxel referenzieren, die tatsächlich auch sichtbar sind, also zB wenn man eine Höhle gräbt.

Wie gesagt, nicht wirklich zu Ende gedacht... aber so wäre es etwas einfacher gehalten, zu mindest beim Erstellen der Welt.

[Krishty]

Darum geht es nicht. Es geht darum, dass das Problem viel zu schnell wächst. Doppelte Seitenlänge – achtfacher Speicherbedarf. Wenn du hingegen nur die Voxel speicherst, die an der Oberfläche liegen, wächst das Problem langsamer – doppelte Seitenlänge, vierfacher Speicherbedarf. (Vergleich das mit der Kugel, wo das Volumen mit der dritten Potenz des Radius wächst, die Oberfläche aber nur mit der zweiten.)

Das bedeutet: Ein 3D-Array bleibt immer gleich (in)effizient, egal, wie groß deine Welt ist. Ein Baum, der die Oberfläche speichert, wird hingegen umso effizienter, je größer die darin gespeicherte Welt ist. Falls die Rechner also in zehn Jahren die hundertfache Rechenleistung haben, kannst du per 3D-Array eine viereinhalbmal so detaillierte Welt bauen (dritte Wurzel aus 100), mit dem Baumansatz hingegen eine zehnmal so detaillierte (Quadratwurzel aus 100).

(Natürlich sind das theoretische Werte; man kann eine Spielwelt auch so gestalten, dass sie die maximale Oberfläche aus dem Volumen rausholt (so wie die Form des Gehirns oder des Darms, die auch auf Maximierung der Oberfläche innerhalb eines Volumens ausgerichtet sind) … und ein bisschen Overhead kommt auch hinzu. Aber das sind synthetische Extremsituationen, die in Spielen keinen Nutzwert hätten. Und selbst dann würden die Zusatzkosten für den Baum gegenüber dem Array nur logarithmisch wachsen.)

Das ist anschaulich damit vergleichbar, einen Sortieralgorithmus mit der Laufzeit O(n) einem mit der Laufzeit O(log(n)) vorzuziehen, weil er einfacher ist. Je mehr dein Array wächst, desto mehr bereust du die Entscheidung.

[kimmi]

ich hatte mal mit einem Volumen-Mesher zu tun, der hat eben aus diesem Grund das Volumen eben als Octtree beschrieben. Warum sollte man interne Würfel vorhalten, wenn sie nicht gebraucht werden?

Gruß Kimmi

[joggel]

Das bedeutet: Ein 3D-Array bleibt immer gleich (in)effizient, egal, wie groß deine Welt ist. Ein Baum, der die Oberfläche speichert, wird hingegen umso effizienter, je größer die darin gespeicherte Welt ist. Falls die Rechner also in zehn Jahren die hundertfache Rechenleistung haben, kannst du per 3D-Array eine viereinhalbmal so detaillierte Welt bauen (dritte Wurzel aus 100), mit dem Baumansatz hingegen eine zehnmal so detaillierte (Quadratwurzel aus 100).

Sorry... aber ich bin verwirrt.
Um Oberflächen in einer 3D-Welt zu speichern benötigt man doch ein Octree... oder wie meinst Du das?


@Warum Voxel speicher, die im inneren eines Körpers sind?
Naja, somit könnte man Eigenschaften der Voxel festhalten, die sich bspw. unter der Oberfläche befinden...

Oder ich verstehe gerade das Prinzip nicht.
Ich meine:
Wenn ich jetzt in einen Berg eine höle grabe, welche Attribute haben sie dann? (Farbe, etc).. oder spielt das keine Rolle?

[joggel]

Ein 3D-Array wächst aber so unverhältnismäßig stark, dass du es nicht gespeichert bekommst – ein Würfel mit einem Kilometer Seitenlänge würde schon bei einem Byte Information pro Kubikmeter Terrain ein GiB Speicher verbrauchen; normalerweise braucht man deutlich mehr. Eine komplette Spielwelt bekommst du nicht auf deine Festplatte, geschweige denn zum Rendern auf die GPU oder in irgendeiner Weise effizient verarbeitet.

Ich würde eigentlich auf einen Octree ausweichen, der nur die Oberflächenvoxel enthält. Den erweitert man dann, falls irgendwo gegraben wird, mit prozeduralen Daten – wo in 10 m Tiefe ein Stein lag kann sich eh niemand merken. Kann man dann auch gut als Marching Cubes direkt auf der GPU visualisieren. So bildet man das 3D-Problem (das Voxel-Volumen) auf ein 2D-Problem (dessen Oberfläche) ab und bringt es dadurch in berechen- und speicherbare Bereiche.

Ist jetzt aber eine primitive Einschätzung; ich habe mich aber nie intensiv mit Voxeln beschäftigt.

Ah... okay!
Jetzt versteh ich was Du meinst, und oben meintest Du bestimmt auch Octree anstatt Quadtree.
Also Eigenschaften der Voxel werden nirgends festgehalten.

ICh glaube, die Frage sollte etwas spezielisiert werden.
Irgendwo eine Welt mit einem Editor bauen (zum Beispiel) ?
Möchtest Du die Möglichkeit haben, jedem Voxel eine bestimmte Eigenschaft zuzuweisen (Farbe,...)
Falls ja, dann kommt man um ein 3D-Arry nicht herum.
Wenn nein,
wie speichert man dann die Welt?
Kann man dazu sich auch Octrees zu nutze machen?
Bestimmt, oder?
Oder gar aus einer HightMap erstellen.
Okay, in der Engine kann man sich dann wieder Octrees zu nutze machen...

[Schrompf]

Wenn Du in den Berg hineingraben willst und dort Erz- oder Rohstoffadern finden willst, brauchst Du natürlich mehr als nur die Oberfläche. Aber ich würde auch in diesem Fall zu einem Octtree raten, da man mit dem zumindest leere Blöcke speichersparsam abbilden kann. Und es besteht ja immer grob die Hälfte der Landschaft aus Himmel :-)

Genau genommen sind das zwei getrennte Problembereiche:

1) Speicherhaltung. Da tut es ein banales 3D-Array, aber es empfiehlt sich, hier etwas Hirnschmalz zu investieren, da die Datenmengen sehr schnell sehr groß werden.

2) Darstellung. Da gibt es viele Methoden. Sei es die Minecraft-Methode, jeden Voxel als Würfel darzustellen und damit nur die Würfelseiten zeichnen zu müssen, die keinen oder durchsichtige Würfel als Nachbarn haben. Oder sei es die Anwendung eines gängigen Volumen-Zu-Oberfläche-Algorithmus wie z.B. Marching Cubes. Letzteres tut ja zum Beispiel Zudomon, wenn ich mich recht erinnere.

[Krishty]

Ah... okay!
Jetzt versteh ich was Du meinst, und oben meintest Du bestimmt auch Octree anstatt Quadtree.

Habe ich das nicht auch geschrieben? :)

Also Eigenschaften der Voxel werden nirgends festgehalten.

Doch, klar. Du kannst in einem Baum alles mögliche speichern; es hält dich keiner ab, da in dem Baum für jedes Blatt (also Voxel) Materialtyp, Farbe, Texturposition oder sonstwas reinzuschreiben. Was immer du brauchst.

Wenn Du in den Berg hineingraben willst und dort Erz- oder Rohstoffadern finden willst, brauchst Du natürlich mehr als nur die Oberfläche.

Ja; die Formulierung „Oberfläche“ war vielleicht vorschnell gewählt. Ich persönlich würde alle Voxel an „Trennflächen“ speichern (oder, anders formuliert, die inneren und äußeren Hüllen jeder Materialkonzentration) – also, wenn du eine Erzader hast, zum einen die Voxel, die die äußere Hülle des Erzes ausmachen und dann nochmal jene der Erde, die an diesen Erzvoxeln anliegt. Dasselbe für Wasser–Erde, Erde–Luft, Erde–Beton, Beton–Luft usw usf.

[Schrompf]

Das stimmt: man könnte den Octtree weiter optimieren, indem man nicht nur komplett leere Blöcke als solche speichert, sondern allgemein jeden Block, der vollständig mit nur einem einzelnen Material gefüllt ist. Damit sind auch große Bereiche im Berg speichersparend abgelegt, wenn sie nur aus Stein bestehen. Zumal der Octree ja hierarchisch ist, Du kannt also auch stressfrei eine weitere Unterteilung hinzufügen, wenn Du ausgerechnet hast, dass es was bringen würde.

[edit] Das Schlimme ist, dass ich mich seit Ewigkeiten mit dem Gedanken an ein (natürlich besseres :-D ) Minecraft trage. Immer, wenn wir hier solche Diskussionen führen, krieg ich wieder mächtig Lust, das Projekt mal anzufangen. Aber nuja - jetzt gibt's erstmal Wichtigeres.

[kimmi]

Siehe dazu den oben verlinkten Artikel. Nicht ohne Grund wird dort von einem Sparse-Octtree gesprochen. Ein ähnliches Konzept sprich N-Tree wird auch gern zum Beschreiben von Matrizen bzw. Sparse-Matrizen benutzt, wenn die Matrixen sehr sehr groß sind.
So etwas findet Verwendung in so manchem FE-Paket, um die Happen von zu multiplizierenden Daten cachegerecht an die CPU verteilen zu können. Anstellen von Geometrie beschreibt der Baum besetzte Elemente der Matrix, die Würfel werden die besetzten Teile der Spare / Band / Whatever - Matrix. N-Tree, weil n Leafes. Aber ich schweife ab :).

Gruß Kimmi

[joeydee]

Man könnte auch den Octree nur für die aktuelle Oberfläche verwenden. Adern usw. per (prozeduraler) Funktionen verteilen, auch wenn man sowas platzieren möchte. Man muss halt eine getVoxelAt(x,y,z)-Methode implementieren, die alle platzierten Objekte im Level abarbeitet und das richtige Voxelobjekt erstellt und zurückgibt. Geschieht aber ja nicht ständig für die gesamte Landschaft, sondern nur beim Graben/Verändern, und das "dauert" ja sowieso pro Voxel.
Der aktuelle Oberflächen-Tree wird dann jeweils entsprechend aktualisiert. Neu gebaute Voxel bleiben dagegen zusätzlich im Baum.