¿Qué tipo de hardware se necesitaría para renderizar un Minecraft del tamaño de la Tierra como un mapa?

He estado pensando en este problema. ¿Es posible con la tecnología actual crear una réplica 1: 1 de la tierra en un juego basado en voxel? ¿Cuál es la mejor estructura de datos para almacenar este mapa gigante? ¿Qué algoritmo se debe usar para representar esta estructura de datos en tiempo real?

Estas preguntas hacen estas suposiciones:

• Cada vóxel tiene una resolución de 1 metro cúbico.

• Por simplicidad, cada vóxel requiere solo 1 byte de información de metadatos. Esta información se utilizará para almacenar la identificación del "tipo" del vóxel (tierra, agua, roca, etc.).

• El volumen de la tierra es 1 * 10ˆ21 metros cúbicos.

• Por "tecnología actual" incluyo todo lo que está disponible comercialmente, pero no las supercomputadoras.

• Solo la topografía de la Tierra y la batimetría se utilizarán para generar el mapa. Se excluyen las construcciones humanas, plantas o cuevas. Los bloques subterráneos se elegirán en base a estudios geológicos, por ejemplo: si la profundidad es mayor de 3000 km, se convertirá en un vóxel 'magma'.

• Al igual que en Minecraft, el mapa no es estático, se puede modificar en el juego.

• Una distancia de extracción 'infinita' es una gran ventaja, ¿cuál es el punto de tener a toda la Tierra en un mapa si no puedes volar y mirar todo el planeta?

La primera conclusión a la que llegué cuando pensé en este problema es que almacenar los datos de la Tierra de forma lineal no es factible, suponiendo que cada vóxel ocupe solo 1 byte de memoria, esto todavía requeriría 1 zettabyte para almacenar el mapa. Por lo tanto, se requiere algún tipo de compresión.

Creo que un voxel octree podría comprimir el mapa, pero no estoy seguro de cuánto. La entropía de este mapa de vóxel es probablemente muy baja, por lo que supongo que se puede lograr un nivel muy alto de compresión.

Descargo de responsabilidad

Esta es una pregunta teórica, no tengo intenciones de escribir un voxel earth

EDITAR

El ESA GOCE ya ha mapeado el geoide de la Tierra con una precisión de 1 cm a 2 cm. Creo que esta información podría usarse para generar un mapa de altura muy preciso de la Tierra. Esto excluiría la necesidad de usar un algoritmo para llenar los vacíos en la topografía de la Tierra.

Eso depende del método de subdivisión espacial que use, aunque todos los métodos de subdivisión (como cualquier método de compresión) eventualmente se despliegan donde no puede producirse más compresión, debido a los gastos generales de la estructura de datos y otros factores lógicos / matemáticos. Un ejemplo se puede encontrar en octrees. Para cada nodo en el octree, se debe mantener un puntero a sus padres y / o hijos (dependiendo de cómo se realice la arquitectura de la estructura de datos), para permitir un recorrido significativo. Cualquier estructura de árbol puede contener n hijos. Cuanto menor sea la relación 1: n, más eficiente será el uso del espacio que gane, y en consecuencia mayores serán los gastos generales en el recorrido del árbol, ya que debe tener más nodos ancestrales para contener la misma cantidad de vóxeles de hojas (en su caso, aproximadamente 510 billones de estos representando el área de superficie).

Teniendo en cuenta que, en su caso, los problemas principales son el costo de almacenamiento y la representación de todo el planeta (o partes del mismo) desde una distancia considerable, no hay una estructura de datos que recomendaría en un día. Mipmapping es una necesidad: 12.8 millones de metros de diámetro a la potencia más alta más cercana de 2 es 2 ^ 24 = 16.8 millones. Los niveles de 24 octree para recorrer equivaldrían a una enorme cantidad de ramificaciones, muy costoso para GPU y CPU por igual. Pero siempre que haga las cosas bien, solo tendrá que atravesar algunos niveles a la vez. Sin embargo, dada la cantidad de espacio requerido, las alternativas son pocas y distantes entre sí (ver más abajo).

Las capacidades de mipmapping de los octrees son las que lo convierten en una herramienta increíblemente poderosa para grandes volúmenes como el que usted describe. A diferencia de todos los demás métodos de subdivisión conocidos (con la excepción de los árboles KD), el octree mantiene la subdivisión por nivel mínimo, lo que significa que las diferencias visuales y físicas entre los niveles de mipmap también se mantienen mínimas, lo que significa deltas mucho más finos en granularidad a medida que avanza y Abajo del árbol.

Si, por otro lado, desea generar un mundo donde el recorrido jerárquico de la cuadrícula se mantenga al mínimo, entonces deberá intercambiar espacio para aumentar la velocidad.

Hablando de la relación ideal 1: n, no hay una estructura más fina que el árbol kd a este respecto. Donde el octree se divide en 2 para cada eje, dando como resultado 2 ^ 3 = 8 celdas secundarias individuales, el árbol kd se divide exactamente una vez por nivel de subdivisión. El problema con esto es que debe elegir un hiperplano para dividirlo, y este hiperplano podría elegirse alrededor de cualquiera de los 3 ejes. Si bien es óptimo en términos de espacio, hace que los recorridos en 3D (como durante las marcas de rayos, una operación fundamental cuando se usan octrees para física o renderización) sean mucho más difíciles que en un octree, ya que se debe mantener una estructura dinámica de tipo portal. interfaces entre nodos de árbol kd individuales.

RLE es otro enfoque de la compresión, pero en muchos sentidos es más difícil de aplicar a un problema como este (donde la base de operaciones es esférica), ya que la compresión RLE es unidimensional y debe elegir el eje en el que opera. planeta, uno podría elegir el eje polar, pero cualquier elección de un solo eje introduciría ciertos problemas con los recorridos para el renderizado y la física al actuar desde ciertos ángulos no óptimos. Por supuesto, también podría ejecutar RLE en 3 ejes simultáneamente, triplicando el costo de almacenamiento, o en 6 ejes (-x, + x, -y, + y, -z, + z) como una optimización adicional.

Entonces, para responder a tu pregunta (¡o no!)

No voy a ir directamente a responder qué tipo de hardware, pero creo que mirarlo desde una perspectiva de diez años comienza a darle una idea de lo que de hecho es posible en qué tipo de hardware. Te animo a que sigas por esta ruta, si realmente quieres saber, podría ser más fácil implementar un simple y escaso octree(vea el documento de Laine en las referencias) y coloque una capa esférica de vóxeles de superficie en él, y vea cómo es el uso del espacio resultante. Avanza desde allí. Vea hasta dónde puede llegar antes de que la memoria de su sistema comience a agotarse. Esto no requiere que escriba un renderizador a menos que desee visualización. También tenga en cuenta que esto se hace mejor en la CPU: las GPU en general no tienen la capacidad de memoria para lidiar con problemas de esta escala. Esta es una de las razones por las que Intel está buscando avanzar hacia procesadores masivamente paralelos: los beneficios de GPGPU, que es mejor en este tipo de cosas, se pueden aplicar a un espacio de memoria mucho más amplio sin cuellos de botella del bus del sistema con los que lidiar. Probablemente hay otros aquí, o en matemáticas.stackexchange.com,

En términos de su requisito de distancia de vista infinita, claro, pero la pregunta siempre se reduce a "cuántos detalles a qué distancia". Representar detalles infinitos requeriría recursos infinitos. Ahí es donde entra en juego el mipmapping variable por escena. También tenga en cuenta que todas las estructuras de datos incorporan cierta compensación de velocidad por espacio o viceversa. Eso significa una representación menos / más lenta, si desea un mundo más grande para la misma cantidad de esfuerzo de ingeniería.

La primera conclusión a la que llegué cuando pensé en este problema es que almacenar los datos de la Tierra de manera lineal no es factible, suponiendo que cada vóxel ocupe solo 1 byte de memoria, esto todavía requeriría 1 zettabyte para almacenar el mapa. Por lo tanto, se requiere algún tipo de compresión.

Como lo más probable es que nunca descubras las propiedades de cada metro cúbico del mundo real, necesitarás alguna forma de generar esa información que es incierta en base a suposiciones. Entonces, si tiene eso resuelto, no hay necesidad de calcular y almacenar todos esos datos, sino que puede generarlos sobre la marcha.

En primer lugar, puede descartar todos los vóxeles dentro de la tierra, ya que estos solo tendrán que calcularse si alguien realmente cava un agujero, por ejemplo. los vóxeles se hacen visibles.

Para la superficie de la tierra, probablemente tomaría una imagen como punto de partida para mis cálculos. Tal vez algún tipo de mapa de temperatura y humedad le permita calcular el tipo de bloques a aplicar. P.ej. Agua, arena (desierto), hierba, nieve, etc. Dado que la imagen probablemente no tendrá un píxel de información por cada metro cuadrado de la superficie terrestre, tendría que mezclar esto con algo de ruido para generar un poco de variación en la superficie. Si siempre usa las mismas semillas aleatorias, su resultado debe ser determinista, sin embargo.

Además, un mapa de elevación sería útil, para que pueda determinar la altura de las características de la superficie. De esa manera puedes agregar montañas, etc.

Esto se reduce a un volumen de datos de algunas imágenes 2D que contienen información sobre la superficie terrestre. Para todo en el interior, volvería a un enfoque de procedimiento puro, donde renderiza diferentes tipos de bloques, dependiendo de la distancia desde el centro de la tierra. Pero como se dijo anteriormente, estos deben calcularse solo cuando alguien cava un hoyo.

Para hacer cambios persistentes, solo guardaría modificaciones en el mundo. Entonces, si alguien cava un hoyo, almacenaría información sobre qué voxels se han eliminado, ya que debería poder procesar los voxels circundantes de manera procesal.

En cuanto a la representación: necesitará algunos sofisticados algoritmos de nivel de detalle y selección para que esto funcione. Es tonto renderizar todos los vóxeles de superficie, cuando la cámara está en un nivel de zoom que muestra todo el mundo. En este nivel, los vóxeles deberían ser mucho más grandes, tal vez incluso una simple esfera texturizada sería suficiente.

Supongo que lo más complicado sería tener un generador sólido que le permita calcular las propiedades de vóxel, incluso para diferentes "resoluciones", de modo que pueda usarlo para generar diferentes niveles de detalle.

Básicamente puedes hacer lo mismo que hace Minecraft. En lugar de generar tal cantidad de datos, puede definir un mundo como una fórmula matemática, siempre que se requiera un dato para mostrarlo, lo genera utilizando la fórmula.

Dicha fórmula generalmente se construye utilizando el concepto de ruido Perlin , esto permite detalles en todos los niveles, puede tener cadenas montañosas tan grandes como las del mundo real, pero elegir generar solo una pequeña parte de ellas. Puede generar la cantidad de detalles que desee, por lo que es posible crear detalles muy finos para cosas cercanas, pero también generar escenarios lejanos en el nivel de detalle requerido.

Minecraft guarda todos los bloques que ha visitado, con los cambios que se hayan realizado, uno podría simplemente salvar la diferencia entre el mundo generado y el mundo actualizado, pero supongo que guardar bloques grandes fue más fácil, y se comprimen relativamente bien.

No creo que haya ningún juego que realmente lleve esto al límite, pero es muy común usar la generación de fórmulas de todos los detalles "sin importancia" de los grandes mundos de juegos. Sin embargo, no estoy seguro de qué tan común es el enfoque generar cuando es necesario, en lugar de simplemente generar el lote y ponerlo en el disco.

Puede buscar datos vectoriales de las masas terrestres de la Tierra, ya que los datos vectoriales tienen la ventaja de escalar a cualquier escala que desee. Combínalo con un mapa de altura de la Tierra para generar la altura del terreno. El último paso son algunas imágenes satelitales detalladas, desde donde puede elegir el tipo de bloque superior en función de la imagen, para obtener roca donde hay roca, arena donde hay arena, etc. Probablemente se deba generar el interior real del planeta. como lo hace Minecraft, a menos que pueda encontrar datos geográficos detallados para trabajar. Básicamente, lo que desea hacer es encontrar datos geográficos y extrapolar a partir de ellos, dada solo la entrada de coordenadas XYZ. Esto significa que tiene datos limitados y extrapola el resto de la forma más precisa posible.