¿Cómo puedo optimizar un mundo voxel de Minecraft-esque?

Encontré los maravillosos mundos grandes de Minecraft extremadamente lentos para navegar, incluso con una tarjeta gráfica de cuatro núcleos y carnosa.

Supongo que la lentitud de Minecraft proviene de:

• Java, ya que la partición espacial y la administración de memoria son más rápidas en C ++ nativo.
• Particionamiento mundial débil.

Podría estar equivocado en ambos supuestos. Sin embargo, esto me hizo pensar en la mejor manera de administrar grandes mundos voxel. Como es un verdadero mundo 3D, donde un bloque puede existir en cualquier parte del mundo, es básicamente una gran matriz 3D [x][y][z], donde cada bloque del mundo tiene un tipo (es decir BlockType.Empty = 0,BlockType.Dirt = 1 , etc.)

Supongo que para que este tipo de mundo funcione bien, necesitarías:

• Use un árbol de alguna variedad ( oct / kd / bsp ) para dividir todos los cubos; parece que un oct / kd sería la mejor opción, ya que puedes dividir en un nivel por cubo, no por un nivel de triángulo.
• Use algún algoritmo para determinar qué bloques se pueden ver actualmente, ya que los bloques más cercanos al usuario podrían ofuscar los bloques detrás, por lo que no tiene sentido renderizarlos.
• Mantenga el objeto de bloque ligero, para que sea rápido agregarlo y eliminarlo de los árboles.

Supongo que no hay una respuesta correcta a esto, pero me interesaría ver las opiniones de las personas sobre el tema. ¿Cómo mejoraría el rendimiento en un gran mundo basado en voxel?

Con respecto a Java vs C ++, he escrito un motor de vóxel en ambos (la versión de C ++ se muestra arriba). También he estado escribiendo motores voxel desde 2004 (cuando no estaban de moda). :) Puedo decir con pocas dudas que el rendimiento de C ++ es muy superior (pero también es más difícil de codificar). Se trata menos de la velocidad computacional y más sobre la gestión de la memoria. Sin lugar a dudas, cuando está asignando / desasignando tantos datos como sea posible en un mundo de vóxeles, C (++) es el lenguaje a superar. sin embargo, deberías pensar en tu objetivo. Si el rendimiento es su máxima prioridad, vaya con C ++. Si solo quieres escribir un juego sin un rendimiento de vanguardia, Java es definitivamente aceptable (como lo demuestra Minecraft). Hay muchos casos triviales / perimetrales, pero en general puede esperar que Java se ejecute aproximadamente 1.75-2.0 veces más lento que (bien escrito) C ++. Puede ver una versión anterior de mi motor mal optimizada en acción aquí (EDITAR: versión más nueva aquí ). Si bien la generación de fragmentos puede parecer lenta, tenga en cuenta que está generando diagramas voronoi 3D volumétricamente, calculando normales de superficie, iluminación, AO y sombras en la CPU con métodos de fuerza bruta. He probado varias técnicas y puedo obtener una generación de fragmentos 100 veces más rápida utilizando varias técnicas de almacenamiento en caché e instancias.

Para responder el resto de su pregunta, hay muchas cosas que puede hacer para mejorar el rendimiento.

1. Almacenamiento en caché. Siempre que pueda, debe calcular los datos una vez. Por ejemplo, cuento la iluminación en la escena. Podría usar iluminación dinámica (en el espacio de la pantalla, como un proceso posterior), pero hornear en la iluminación significa que no tengo que pasar las normales para los triángulos, lo que significa ...

2. Pase la menor cantidad de datos posible a la tarjeta de video. Una cosa que la gente tiende a olvidar es que cuantos más datos pases a la GPU, más tiempo llevará. Paso en un solo color y una posición de vértice. Si quiero hacer ciclos de día / noche, simplemente puedo hacer una gradación de color o puedo recalcular la escena a medida que el sol cambia gradualmente.

3. Dado que pasar datos a la GPU es muy costoso, es posible escribir un motor en un software que sea más rápido en algunos aspectos. La ventaja del software es que puede hacer todo tipo de manipulación de datos / acceso a la memoria que simplemente no es posible en una GPU.

4. Juega con el tamaño del lote. Si está utilizando una GPU, el rendimiento puede variar drásticamente según el tamaño de cada matriz de vértices que pase. En consecuencia, juegue con el tamaño de los fragmentos (si usa fragmentos). Descubrí que los fragmentos de 64x64x64 funcionan bastante bien. No importa qué, mantenga sus trozos cúbicos (sin prismas rectangulares). Esto hará que la codificación y varias operaciones (como las transformaciones) sean más fáciles y, en algunos casos, más efectivas. Si solo almacena un valor para la longitud de cada dimensión, tenga en cuenta que son dos registros menos que se intercambian durante el cálculo.

5. Considere mostrar listas (para OpenGL). Aunque son la forma "antigua", pueden ser más rápidos. Debe hornear una lista de visualización en una variable ... si llama a operaciones de creación de lista de visualización en tiempo real, será muy lento. ¿Cómo es una lista de visualización más rápida? Solo actualiza el estado, frente a los atributos por vértice. Esto significa que puedo pasar hasta seis caras, luego un color (frente a un color para cada vértice del vóxel). Si está utilizando GL_QUADS y vóxeles cúbicos, ¡esto podría ahorrar hasta 20 bytes (160 bits) por vóxel! (15 bytes sin alfa, aunque generalmente desea mantener las cosas alineadas en 4 bytes).

6. Utilizo un método de fuerza bruta para representar "fragmentos", o páginas de datos, que es una técnica común. A diferencia de los octrees, es mucho más fácil / rápido leer / procesar los datos, aunque es mucho menos amigable con la memoria (sin embargo, en estos días puede obtener 64 gigabytes de memoria por $ 200- $ 300) ... no es que el usuario promedio tenga eso. Obviamente, no puede asignar una gran matriz para todo el mundo (un conjunto de 1024x1024x1024 de voxels es 4 gigabytes de memoria, suponiendo que se use un int de 32 bits por voxel). Entonces asigna / reparte muchos arreglos pequeños, en función de su proximidad al espectador. También puede asignar los datos, obtener la lista de visualización necesaria y luego volcar los datos para ahorrar memoria. Creo que el combo ideal podría ser utilizar un enfoque híbrido de octrees y arrays: almacenar los datos en una matriz cuando se realiza la generación de procedimientos del mundo, la iluminación, etc.

7. Renderizar de cerca a lejos ... un píxel recortado es tiempo ahorrado. La GPU arrojará un píxel si no pasa la prueba de profundidad del búfer.

8. Renderizar solo fragmentos / páginas en la ventana gráfica (se explica por sí mismo). Incluso si el gpu sabe cómo recortar polígonos fuera de la ventana gráfica, pasar estos datos todavía lleva tiempo. No sé cuál sería la estructura más eficiente para esto ("vergonzosamente", nunca he escrito un árbol BSP), pero incluso un simple raycast por fragmento podría mejorar el rendimiento, y obviamente probar contra el frustum de visualización ahorrar tiempo.

9. Información obvia, pero para los novatos: elimine todos los polígonos que no estén en la superficie, es decir, si un vóxel consta de seis caras, elimine las caras que nunca se representan (están tocando otro vóxel).

10. Como regla general de todo lo que haces en programación: CACHE LOCALITY! Si puede mantener las cosas en la memoria caché local (incluso por un corto período de tiempo, marcará una gran diferencia. Esto significa mantener sus datos congruentes (en la misma región de memoria) y no cambiar áreas de memoria para procesarlas con demasiada frecuencia). , idealmente, trabaje en un fragmento por subproceso y mantenga esa memoria exclusiva para el subproceso. Esto no solo se aplica al caché de la CPU. Piense en la jerarquía del caché de esta manera (más lenta a más rápida): red (nube / base de datos / etc.) -> disco duro (obtenga un SSD si aún no tiene uno), ram (obtenga un triple canal o mayor RAM si aún no lo tiene), caché (s) de CPU, registros. Intente mantener sus datos en el último extremo, y no lo cambies más de lo necesario.

11. Enhebrado Hazlo. Los mundos Voxel son muy adecuados para el enhebrado, ya que cada parte se puede calcular (en su mayoría) independientemente de las demás ... Vi literalmente una mejora casi 4x (en un Core i7 de 4 núcleos y 8 hilos) en la generación del mundo procesal cuando escribí el rutinas para enhebrar.

12. No utilice tipos de datos char / byte. O pantalones cortos. Su consumidor promedio tendrá un procesador AMD o Intel moderno (como usted probablemente). Estos procesadores no tienen registros de 8 bits. Calculan los bytes colocándolos en una ranura de 32 bits, luego los vuelven a convertir (tal vez) en la memoria. Su compilador puede hacer todo tipo de vudú, pero usar un número de 32 o 64 bits le dará los resultados más predecibles (y más rápidos). Del mismo modo, un valor "bool" no toma 1 bit; el compilador a menudo usará 32 bits completos para un bool. Puede ser tentador hacer ciertos tipos de compresión en sus datos. Por ejemplo, podría almacenar 8 vóxeles como un solo número (2 ^ 8 = 256 combinaciones) si todos fueran del mismo tipo / color. Sin embargo, debe pensar en las ramificaciones de esto: podría ahorrar una gran cantidad de memoria, pero también puede dificultar el rendimiento, incluso con un pequeño tiempo de descompresión, porque incluso esa pequeña cantidad de tiempo adicional se escala cúbicamente con el tamaño de su mundo. Imagina calcular un rayo; para cada paso de la emisión de rayos, tendría que ejecutar el algoritmo de descompresión (a menos que encuentre una forma inteligente de generalizar el cálculo de 8 voxels en un paso de rayos).

13. Como menciona José Chávez, el patrón de diseño de peso mosca puede ser útil. Del mismo modo que usaría un mapa de bits para representar un mosaico en un juego en 2D, puede construir su mundo a partir de varios tipos de mosaico (o bloque) en 3D. La desventaja de esto es la repetición de texturas, pero puede mejorar esto usando texturas de varianza que encajen entre sí. Como regla general, desea utilizar instancias siempre que pueda.

14. Evite el procesamiento de vértices y píxeles en el sombreador al generar la geometría. En un motor vóxel inevitablemente tendrá muchos triángulos, por lo que incluso un sombreador de píxeles simple puede reducir el tiempo de renderizado en gran medida. Es mejor renderizar a un búfer, luego haces un sombreador de píxeles como un proceso posterior. Si no puede hacer eso, intente hacer cálculos en su sombreador de vértices. Se deben hornear otros cálculos en los datos del vértice cuando sea posible. Los pases adicionales se vuelven muy caros si debe volver a representar toda la geometría (como la asignación de sombras o la asignación de entorno). A veces es mejor renunciar a una escena dinámica en favor de detalles más ricos. Si su juego tiene escenas modificables (es decir, terreno destructible), siempre puede volver a calcular la escena a medida que se destruyen las cosas. La recompilación no es costosa y debería tomar menos de un segundo.

15. ¡Desenrolle sus bucles y mantenga las matrices planas! No hagas esto:

    for (i = 0; i < chunkLength; i++) {
     for (j = 0; j < chunkLength; j++) {
      for (k = 0; k < chunkLength; k++) {
       MyData[i][j][k] = newVal;
      }
     }
    }
    //Instead, do this:
    for (i = 0; i < chunkLengthCubed; i++) {
     //figure out x, y, z index of chunk using modulus and div operators on i
     //myData should have chunkLengthCubed number of indices, obviously
     myData[i] = newVal;
    }

    EDITAR: a través de pruebas más extensas, he descubierto que esto puede estar mal. Use el caso que funcione mejor para su escenario. En general, las matrices deben ser planas, pero el uso de bucles de índice múltiple a menudo puede ser más rápido según el caso

EDIT 2: cuando se usan bucles de múltiples índices, es mejor hacer un bucle en el orden z, y, x en lugar de al revés. Su compilador podría optimizar esto, pero me sorprendería si lo hiciera. Esto maximiza la eficiencia en el acceso a la memoria y la localidad.

for (k < 0; k < volumePitch; k++) {
    for (j = 0; j < volumePitch; j++) {
        for (i = 0; i < volumePitch; i++) {
            myIndex = k*volumePitch*volumePitch + j*volumePitch + i;
        }
    }
}

16. A veces tienes que hacer suposiciones, generalizaciones y sacrificios. Lo mejor que puede hacer es asumir que la mayor parte de su mundo es completamente estático, y solo cambia cada dos mil cuadros. Para las partes animadas del mundo, se pueden hacer en un pase separado. También suponga que la mayor parte de su mundo es completamente opaco. Los objetos transparentes se pueden representar en un pase separado. Suponga que las texturas solo varían cada x unidades, o que los objetos solo se pueden colocar en incrementos de x. Asuma un tamaño mundial fijo ... por tentador que sea un mundo infinito, puede llevar a requisitos de sistema impredecibles. Por ejemplo, para simplificar la generación del patrón de voronoi en las rocas de arriba, supuse que cada punto central de voronoi se encontraba en una cuadrícula uniforme, con un ligero desplazamiento (en otras palabras, hashing geométrico implícito). Supongamos un mundo que no se ajusta (tiene bordes). Esto puede simplificar muchas complejidades introducidas por un sistema de coordenadas de ajuste, a un costo mínimo para la experiencia del usuario.

Puedes leer más sobre mis implementaciones en mi sitio

Minecraft podría estar haciendo muchas cosas de manera más eficiente. Por ejemplo, Minecraft carga pilares verticales enteros de aproximadamente 16x16 fichas y los renderiza. Siento que es muy ineficiente enviar y renderizar tantos mosaicos innecesariamente. Pero no creo que la elección del idioma sea importante.

Java puede ser bastante rápido, pero para algo orientado a los datos, C ++ tiene una gran ventaja con una sobrecarga significativamente menor para acceder a las matrices y trabajar en bytes. Por otro lado, es mucho más fácil realizar subprocesos en todas las plataformas en Java. A menos que planee utilizar OpenMP u OpenCL, no encontrará esa comodidad en C ++.

Mi sistema ideal sería una jerarquía un poco más compleja.

El mosaico es una sola unidad, probablemente alrededor de 4 bytes para guardar información como el tipo de material y la iluminación.

El segmento sería un bloque de mosaicos de 32x32x32.

1. Se establecerían banderas para cada uno de los seis lados, si todo ese lado es bloques sólidos. Eso permitiría al renderizador ocluir segmentos detrás de ese segmento. Minecraft actualmente no parece realizar pruebas de oclusión. Pero se mencionó el hecho de tener disponible la eliminación de oclusión de hardware, que puede ser costosa pero mejor que generar cantidades masivas de polígonos en tarjetas de gama baja.
2. Los segmentos solo se cargarían en la memoria durante la actividad (jugadores, NPC, física del agua, crecimiento de árboles, etc.). De lo contrario, se enviarían directamente aún comprimidos del disco a los clientes.

Los sectores serían un bloque de segmentos de 16x16x8.

1. Los sectores rastrearían el segmento más alto para cada columna vertical de modo que los segmentos más altos que ese puedan determinarse rápidamente vacíos.
2. También rastrearía el segmento ocluido inferior, de modo que cada segmento que necesita ser renderizado desde la superficie pueda ser capturado rápidamente.
3. Los sectores también realizarán un seguimiento de la próxima vez que cada segmento necesite ser actualizado (física del agua, crecimiento de los árboles, etc.). De esta manera, cargar en cada sector sería suficiente para mantener vivo al mundo y solo cargar en segmentos el tiempo suficiente para completar sus tareas.
4. Todas las posiciones de la entidad serían rastreadas en relación con el Sector. Esto evitaría los errores de punto flotante presentes en Minecraft cuando se viaja muy lejos del centro del mapa.

El mundo sería un mapa infinito de sectores.

1. El mundo sería responsable de administrar los sectores y sus próximas actualizaciones.
2. El mundo enviaría segmentos preventivos a los jugadores a lo largo de sus rutas potenciales. Minecraft envía reactivamente segmentos que el cliente solicita, incitando un retraso.

Minecraft es bastante rápido, incluso en mi 2-core. Java no parece ser un factor limitante, aquí, aunque hay un poco de retraso del servidor. Los juegos locales parecen funcionar mejor, así que voy a asumir algunas ineficiencias allí.

En cuanto a su pregunta, Notch (autor de Minecraft) ha blogueado un poco sobre la tecnología. En particular, el mundo se almacena en "fragmentos" (a veces se ven estos, especialmente cuando falta uno, ya que el mundo aún no se ha completado), por lo que la primera optimización es decidir si se puede ver un fragmento o no. .

Dentro de un fragmento, como has adivinado, la aplicación tiene que decidir si se puede ver un bloque o no, en función de si otros bloques lo ocultan o no.

Tenga en cuenta también que hay CARAS de bloque, que se puede suponer que no se ve, en virtud de estar ocultas (es decir, otro bloque cubre la cara) o en qué dirección apunta la cámara (si la cámara mira hacia el Norte, puede ¡No vea la cara norte de CUALQUIER bloque!)

Las técnicas comunes también incluirían no mantener objetos de bloque separados sino, más bien, una "porción" de tipos de bloque, con un único bloque prototipo para cada uno, junto con un conjunto mínimo de datos para describir cómo este bloque puede ser personalizado. Por ejemplo, no hay ningún bloque de granito personalizado (que yo sepa), pero el agua tiene datos para determinar qué tan profundo es a lo largo de cada cara lateral, a partir de la cual se puede calcular su dirección de flujo.

Su pregunta no está clara si está buscando optimizar la velocidad de renderizado, el tamaño de los datos o qué. Aclaración allí sería útil.

Aquí hay algunas palabras de información general y consejos, que puedo dar como un modder de Minecraft con mucha experiencia (que al menos en parte puede brindarle alguna orientación).

La razón por la que Minecraft es lento tiene MUCHO que ver con algunas decisiones de diseño cuestionables de bajo nivel; por ejemplo, cada vez que se hace referencia a un bloque por posicionamiento, el juego valida las coordenadas con aproximadamente 7 declaraciones if para garantizar que no esté fuera de los límites . Además, no hay forma de tomar una 'porción' (una unidad de bloques de 16x16x256 con la que trabaja el juego), luego hacer referencia a los bloques directamente para evitar las búsquedas de caché y, erm, problemas de validación tontos (ahora, cada referencia de bloque también implica una búsqueda fragmentaria, entre otras cosas.) En mi mod, creé una forma de agarrar y cambiar la matriz de bloques directamente, lo que impulsó la generación masiva de mazmorras de insoportablemente lenta a notablemente rápida.

EDITAR: Se eliminó la afirmación de que declarar variables en un alcance diferente resultó en ganancias de rendimiento, este no parece ser el caso. Creo que en ese momento combiné este resultado con algo más con lo que estaba experimentando (específicamente, eliminar los moldes entre dobles y flotantes en el código relacionado con la explosión al consolidarlos en dobles ... ¡comprensiblemente, esto tuvo un gran impacto!)

Además, aunque no es el área en la que paso mucho tiempo, la mayor parte del estrangulamiento de rendimiento en Minecraft es un problema con el renderizado (aproximadamente el 75% del tiempo de juego está dedicado a mi sistema). Obviamente no te importa mucho si la preocupación es apoyar a más jugadores en el modo multijugador (el servidor no representa nada), pero es importante en la medida en que las máquinas de todos puedan incluso jugar.

Entonces, sea cual sea el idioma que elija, trate de intimar con la implementación / detalles de bajo nivel, porque incluso un pequeño detalle en un proyecto como este podría marcar la diferencia (un ejemplo para mí en C ++ fue "¿Puede el compilador funcionar estáticamente en línea? ¿punteros? "¡Sí puede! Hizo una diferencia increíble en uno de los proyectos en los que estaba trabajando, ya que tenía menos código y la ventaja de incluirlo en línea".

Realmente no me gusta esa respuesta porque dificulta el diseño de alto nivel, pero es una verdad dolorosa si el rendimiento es una preocupación. ¡Espero que hayas encontrado esto útil!

Además, la respuesta de Gavin cubre algunos detalles que no quería reiterar (¡y mucho más! Claramente tiene más conocimientos sobre el tema que yo), y estoy de acuerdo con él en su mayor parte. Tendré que experimentar con su comentario sobre procesadores y tamaños variables más cortos, nunca he oído hablar de eso. ¡Me gustaría probarme a mí mismo que es verdad!

La cuestión es pensar cómo cargaría primero los datos. Si transmite sus datos de mapas a la memoria cuando sea necesario, existe un límite natural para lo que puede procesar, esto ya es una actualización del rendimiento de representación.

Lo que haga con estos datos depende de usted. Para el rendimiento de GFX, puede usar Recorte para recortar objetos ocultos, objetos que son demasiado pequeños para ser visibles, etc.

Si está buscando técnicas de rendimiento gráfico, estoy seguro de que puede encontrar montañas de cosas en la red.

Algo a tener en cuenta es el patrón de diseño Flyweight . Creo que la mayoría de las respuestas aquí hacen referencia a este patrón de diseño de una forma u otra.

Si bien no sé el método exacto que Minecraft está usando para minimizar la memoria para cada tipo de bloque, esta es una posible vía para usar en tu juego. La idea es tener solo un objeto, como un prototipo, que contenga información sobre todos los bloques. La única diferencia sería la ubicación de cada bloque.

Pero incluso la ubicación se puede minimizar: si sabe que un bloque de tierra es de un tipo, ¿por qué no almacenar las dimensiones de esa tierra como un bloque gigante, con un conjunto de datos de ubicación?

Obviamente, la única forma de saberlo es comenzar a implementar la suya y hacer algunas pruebas de memoria para el rendimiento. ¡Háganos saber cómo va!