Ich habe über dieses Problem nachgedacht. Ist es mit der aktuellen Technologie möglich, eine 1: 1-Nachbildung der Erde in einem voxelbasierten Spiel zu erstellen? Was ist die beste Datenstruktur zum Speichern dieser riesigen Karte? Welcher Algorithmus sollte verwendet werden, um diese Datenstruktur in Echtzeit zu rendern?
Diese Fragen machen diese Annahmen:
Jedes Voxel hat eine Auflösung von 1 Kubikmeter.
Der Einfachheit halber benötigt jedes Voxel nur 1 Byte Metadateninformationen. Diese Informationen werden verwendet, um die Identifizierung des "Typs" des Voxels (Erde, Wasser, Gestein usw.) zu speichern.
Das Erdvolumen beträgt 1 * 10ˆ21 Kubikmeter.
Unter "aktueller Technologie" verstehe ich alles, was im Handel erhältlich ist, aber keine Supercomputer.
Zur Erstellung der Karte werden nur die Erdtopographie und die Bathymetrie verwendet. Menschliches Bauen, Pflanzen oder Höhlen sind ausgeschlossen. Die unterirdischen Blöcke werden basierend auf geologischen Studien ausgewählt, z. B.: Wenn die Tiefe größer als 3000 km ist, wird ein Magma-Voxel erzeugt.
Genau wie in Minecraft ist die Karte nicht statisch, sondern kann im Spiel geändert werden.
Eine "unendliche" Zugentfernung ist ein großes Plus. Was bringt es, die ganze Erde auf einer Karte zu haben, wenn man nicht hochfliegen und den ganzen Planeten beobachten kann?
Die erste Schlussfolgerung, zu der ich kam, als ich über dieses Problem nachdachte, ist, dass das lineare Speichern der Erddaten nicht möglich ist, vorausgesetzt, dass jedes Voxel nur 1 Byte Speicher belegt. Dies würde immer noch 1 Zettabyte zum Speichern der Karte erfordern. Es ist also eine Art Komprimierung erforderlich.
Ich denke, dass ein Voxel-Octree die Karte komprimieren könnte, aber ich bin mir nicht sicher, um wie viel. Die Entropie dieser Voxelkarte ist wahrscheinlich sehr niedrig, so dass ich denke, dass ein sehr hohes Maß an Komprimierung erreicht werden kann.
Haftungsausschluss
Dies ist eine theoretische Frage, ich habe nicht die Absicht, eine Voxelerde zu schreiben
BEARBEITEN
Die ESA GOCE hat das Erdgeoid bereits mit einer Genauigkeit von 1 cm bis 2 cm kartiert. Ich glaube, dass diese Informationen verwendet werden könnten, um eine sehr genaue Höhenkarte der Erde zu erstellen. Dies würde die Notwendigkeit ausschließen, einen Algorithmus zu verwenden, um Lücken in der Erdtopographie zu füllen.
quelle
Antworten:
Dies hängt von der von Ihnen verwendeten räumlichen Unterteilungsmethode ab, obwohl alle Unterteilungsmethoden (wie jede Komprimierungsmethode) aufgrund von Datenstruktur-Overheads und anderen logischen / mathematischen Faktoren letztendlich dort eingesetzt werden, wo keine weitere Komprimierung stattfinden kann. Ein Beispiel finden Sie in Oktrees. Für jeden Knoten im Octree muss ein Zeiger auf seine übergeordneten und / oder untergeordneten Knoten beibehalten werden (abhängig davon, wie Sie Ihre Datenstrukturarchitektur ausführen), um eine sinnvolle Durchquerung zu ermöglichen. Jede Baumstruktur kann n untergeordnete Elemente enthalten. Je niedriger das Verhältnis 1: n ist, desto effizienter wird der gewonnene Speicherplatz und desto größer ist der Overhead beim Durchqueren von Bäumen, da Sie mehr Ahnenknoten haben müssen, um die gleiche Anzahl von Blattvoxeln zu enthalten (in Ihrem Fall ungefähr 510 Billionen) davon die Oberfläche darstellend).
In Anbetracht dessen, dass in Ihrem Fall die Hauptprobleme die Speicherkosten und das Rendern des gesamten Planeten (oder von Teilen davon) aus angemessener Entfernung sind, gibt es keine Datenstruktur, die ich über einen Octree empfehlen würde. Mipmapping ist eine Notwendigkeit: 12,8 Millionen Meter Durchmesser bei der nächsthöheren Potenz von 2 sind 2 ^ 24 = 16,8 Millionen. Das Durchqueren von 24 Octree-Ebenen würde eine gigantische Menge an Verzweigungen bedeuten - sehr teuer für GPUs und CPUs gleichermaßen. Aber wenn Sie die Dinge richtig machen, müssen Sie immer nur ein paar Level gleichzeitig durchqueren. Angesichts des Platzbedarfs gibt es jedoch nur wenige Alternativen (siehe unten).
Die Mipmapping-Funktionen von Octrees machen es zu einem unglaublich leistungsstarken Tool für große Volumes, wie Sie es beschreiben. Im Gegensatz zu allen anderen bekannten Unterteilungsmethoden (mit Ausnahme von KD-Bäumen) hält der Octree die Unterteilung pro Ebene minimal, was bedeutet, dass die visuellen und physischen Unterschiede zwischen den Mipmap-Ebenen ebenfalls minimal gehalten werden, was bedeutet, dass die Granularität beim Gehen und Gehen viel feiner ist den Baum runter.
Wenn Sie andererseits eine Welt generieren möchten, in der die hierarchische Gitterdurchquerung auf ein Minimum beschränkt ist, müssen Sie den Platz austauschen, um die Geschwindigkeit zu erhöhen.
Apropos ideales 1: n-Verhältnis: In dieser Hinsicht gibt es keine feinere Struktur als den kd-Baum. Wenn sich das Octree für jede Achse in 2 teilt, was zu 2 ^ 3 = 8 einzelnen untergeordneten Zellen führt, teilt sich der kd-Baum genau einmal pro Unterteilungsebene. Das Problem dabei ist, dass Sie eine Hyperebene auswählen müssen, nach der geteilt werden soll, und diese Hyperebene kann um eine der drei Achsen ausgewählt werden. Obwohl es räumlich optimal ist, erschwert es 3D-Durchquerungen (z. B. bei Raymarches, eine grundlegende Aufgabe bei der Verwendung von Octrees für die Physik oder beim Rendern) erheblich als bei einem Octree, da eine dynamische Struktur vom Typ Portal aufgezeichnet werden muss Schnittstellen zwischen einzelnen kd-Baumknoten.
RLE ist ein anderer Ansatz zur Komprimierung, aber in vielerlei Hinsicht schwieriger auf ein Problem wie dieses anzuwenden (bei dem die Operationsbasis sphärisch ist), da die RLE-Komprimierung eindimensional ist und Sie die Achse auswählen müssen, in der sie arbeitet Planet könnte man die Polarachse wählen, aber jede Einzelachsenwahl würde bestimmte Probleme mit Durchquerungen für Rendering und Physik mit sich bringen, wenn aus bestimmten nicht optimalen Winkeln gehandelt wird. Natürlich können Sie RLE auch in 3 Achsen gleichzeitig ausführen, wodurch sich die Speicherkosten verdreifachen, oder in 6 Achsen (-x, + x, -y, + y, -z, + z) als weitere Optimierung.
Also, um deine Frage zu beantworten (oder nicht!)
Ich werde gehe nicht direkt in der Beantwortung , welche Art von Hardware, aber ich denke , es bei der Suche von einer Octree Perspektive beginnt Ihr eine Vorstellung davon zu geben , was in der Tat möglich ist , auf welcher Art von Hardware. Ich würde Sie ermutigen, diesen Weg zu gehen. Wenn Sie wirklich wissen möchten, ist es möglicherweise am einfachsten, einen einfachen, spärlichen Octree zu implementieren(siehe Laines Artikel in den Referenzen) und platzieren Sie eine Kugelschale aus Oberflächenvoxeln darin und sehen Sie, wie die resultierende Raumnutzung ist. Steig von dort auf. Sehen Sie, wie weit Sie kommen können, bevor Ihr Systemspeicher leer wird. Dazu müssen Sie keinen Renderer schreiben, es sei denn, Sie möchten eine Visualisierung. Beachten Sie auch, dass dies am besten auf der CPU erfolgt - GPUs verfügen im Großen und Ganzen nicht über die Speicherkapazität, um Probleme dieser Größenordnung zu lösen. Dies ist einer der Gründe, warum Intel auf massiv parallele Prozessoren umsteigen möchte: Die Vorteile von GPGPU, die in dieser Hinsicht besser sind, können auf einen weitaus größeren Speicherplatz angewendet werden, ohne dass es zu Engpässen bei Systembussen kommt. Es gibt wahrscheinlich andere hier oder auf mathematik.stackexchange.com,
Sicher, in Bezug auf Ihre unendliche Sichtentfernungsanforderung, aber die Frage lautet immer: "Wie viele Details in welcher Entfernung?". Das Rendern von unendlichen Details würde unendliche Ressourcen erfordern. Hier kommt das Mipmapping mit variablen Szenen ins Spiel. Denken Sie auch daran, dass alle Datenstrukturen einen Kompromiss zwischen Geschwindigkeit und Raum darstellen oder umgekehrt. Das bedeutet weniger / langsameres Rendern, wenn Sie eine größere Welt bei gleichem Engineering-Aufwand wünschen.
quelle
Da Sie höchstwahrscheinlich nie die Eigenschaften jedes Kubikmeters der realen Welt herausfinden werden, benötigen Sie eine Möglichkeit, diese Daten zu generieren, die aufgrund von Annahmen unsicher sind. Wenn Sie das herausgefunden haben, müssen Sie nicht alle diese Daten berechnen und speichern, sondern können sie lieber im laufenden Betrieb generieren.
In erster Linie können Sie alle Voxel in der Erde verwerfen, da diese nur berechnet werden müssen, wenn jemand tatsächlich ein Loch gräbt, z. Die Voxel werden sichtbar.
Für die Erdoberfläche würde ich wahrscheinlich ein Bild als Ausgangspunkt für meine Berechnungen nehmen. Vielleicht können Sie mit einer Art Temperatur- und Feuchtigkeitskarte die Art der anzuwendenden Blöcke berechnen. Z.B. Wasser, Sand (Wüste), Gras, Schnee usw. Da das Bild wahrscheinlich nicht ein Pixel an Informationen für jeden Quadratmeter der Erdoberfläche enthält, müssten Sie dies mit etwas Rauschen mischen, um ein wenig Variation zu erzeugen die Oberfläche. Wenn Sie immer dieselben Zufallssamen verwenden, sollte Ihr Ergebnis dennoch deterministisch sein.
Außerdem wäre eine Höhenkarte hilfreich, damit Sie die Höhe der Oberflächenmerkmale bestimmen können. Auf diese Weise können Sie Berge usw. hinzufügen.
Dies läuft also auf ein Datenvolumen einiger 2D-Bilder hinaus, die Informationen über die Erdoberfläche enthalten. Für alles im Inneren würden Sie zu einem reinen prozeduralen Ansatz zurückkehren, bei dem Sie je nach Entfernung vom Erdmittelpunkt verschiedene Arten von Blöcken rendern. Aber wie oben gesagt, müssen diese nur berechnet werden, wenn jemand ein Loch gräbt.
Um Änderungen dauerhaft zu machen, würde ich nur Änderungen an der Welt speichern . Wenn also jemand ein Loch gräbt, würde ich Informationen darüber speichern, welche Voxel entfernt wurden, da ich in der Lage sein sollte, die umgebenden Voxel prozedural zu rendern.
Was das Rendern betrifft: Sie benötigen einige ausgefeilte Detaillierungs- und Culling-Algorithmen, damit dies funktioniert. Es ist albern, alle Oberflächenvoxel zu rendern, wenn sich die Kamera in einer Zoomstufe befindet, die die ganze Welt zeigt. Auf dieser Ebene sollten die Voxel viel größer sein, vielleicht würde sogar eine einfache strukturierte Kugel ausreichen.
Ich denke, das Schwierigste wäre, einen soliden Generator zu haben, mit dem Sie die Voxeleigenschaften auch für verschiedene "Auflösungen" berechnen können, damit Sie damit verschiedene Detaillierungsgrade generieren können.
quelle
Sie können im Grunde das Gleiche tun wie Minecraft. Anstatt eine solche Datenmenge zu erstellen, können Sie eine Welt als mathematische Formel definieren. Wenn ein Datenelement für die Anzeige benötigt wird, generieren Sie es mithilfe der Formel.
Eine solche Formel wird normalerweise nach dem Konzept des Perlin-Rauschens erstellt . Dies ermöglicht Details auf allen Ebenen. Sie können Gebirgszüge haben, die so groß sind wie die in der realen Welt, aber nur einen kleinen Teil davon erzeugen. Sie können die Menge an Details generieren, die Sie mögen, so dass es möglich ist, sehr feine Details für Nahaufnahmen zu erstellen, aber auch weit entfernte Landschaften in der erforderlichen Detailstufe zu generieren.
Minecraft speichert alle von Ihnen besuchten Blöcke, einschließlich aller vorgenommenen Änderungen. Man könnte einfach nur den Unterschied zwischen der generierten und der aktualisierten Welt speichern, aber ich denke, das Speichern großer Blöcke war einfacher und sie komprimieren relativ gut.
Ich glaube nicht, dass es ein Spiel gibt, das dies wirklich an seine Grenzen bringt, aber es ist sehr üblich, die formelhafte Generierung aller "unwichtigen" Details großer Spielwelten zu verwenden. Ich bin mir nicht sicher, wie häufig der Ansatz zum Generieren bei Bedarf ist, anstatt einfach das Los zu generieren und es auf die CD zu legen.
quelle
Sie können nach Vektordaten der Landmassen der Erde suchen, da Vektordaten den Vorteil haben, dass sie auf jede gewünschte Skala skaliert werden können. Kombinieren Sie es mit einer Höhenkarte der Erde, um die Höhe des Geländes zu ermitteln. Der letzte Schritt sind einige detaillierte Satellitenbilder, aus denen Sie anhand des Bildes den Typ des oberen Blocks auswählen können, sodass Sie Felsen erhalten, wo sich Felsen befinden, Sand, wo sich Sand befindet usw. Die tatsächlichen Innenseiten des Planeten sollten wahrscheinlich generiert werden wie Minecraft es tut, es sei denn, Sie finden detaillierte geografische Daten, von denen aus Sie arbeiten können. Grundsätzlich möchten Sie geografische Daten suchen und daraus extrapolieren, wenn Sie nur die XYZ-Koordinaten eingeben. Dies bedeutet, dass Sie nur über begrenzte Daten verfügen und den Rest so genau wie möglich extrapolieren.
quelle