Almacenar vóxeles para un motor de vóxel en C ++

9

Estoy tratando de escribir un pequeño motor de vóxel porque es divertido, pero me cuesta encontrar la mejor manera de almacenar los vóxeles reales. Soy consciente de que necesitaré trozos de algún tipo, así que no necesito tener todo el mundo en la memoria, y sé que necesito renderizarlos con un rendimiento razonable.

Leí sobre octrees y, por lo que entiendo, comienza con 1 cubo, y en ese cubo puede haber 8 cubos más, y en todos esos 8 cubos puede haber otros 8 cubos, etc. Pero no creo que esto se ajuste a mi motor de vóxel porque mis cubos / artículos de voxel serán todos exactamente del mismo tamaño.

Entonces, otra opción es simplemente crear una matriz de tamaño 16 * 16 * 16 y hacer que sea un fragmento, y llenarlo con elementos. Y las partes donde no hay ningún artículo tendrán 0 como valor (0 = aire). Pero me temo que esto va a desperdiciar mucha memoria y no será muy rápido.

Luego, otra opción es un vector para cada fragmento y llenarlo con cubos. Y el cubo mantiene su posición en el trozo. Esto ahorra memoria (sin bloqueos de aire), pero hace que la búsqueda de un cubo en una ubicación específica sea mucho más lenta.

Así que realmente no puedo encontrar una buena solución, y espero que alguien pueda ayudarme con eso. Entonces, ¿qué usarías y por qué?

Pero otro problema es el renderizado. Simplemente leer cada fragmento y enviarlo a la GPU usando OpenGL es fácil, pero muy lento. Generar una malla por fragmento sería mejor, pero eso significa que cada vez que rompo un bloque, tengo que reconstruir todo el fragmento, lo que podría llevar un poco de tiempo y causar un hipo menor pero notable, que obviamente tampoco quiero. Entonces eso sería más difícil. Entonces, ¿cómo renderizaría los cubos? Simplemente cree todos los cubos en un búfer de vértices por fragmento y renderícelo, y tal vez intente ponerlo en otro hilo, ¿o hay alguna otra forma?

¡Gracias!

Clonkex
fuente
1
Deberías usar instancing para renderizar tus cubos. Puede encontrar un tutorial aquí learnopengl.com/Advanced-OpenGL/Instancing . Para almacenar los cubos: ¿tiene fuertes restricciones de memoria en el hardware? 16 ^ 3 cubos no parecen demasiada memoria.
Turnos
@Turms ¡Gracias por tu comentario! No tengo fuertes restricciones de memoria, es solo una PC normal. Pero pensé, si cada parte más alta es 50% de aire, y el mundo es muy grande, entonces debe haber un poco de memoria desperdiciada. Pero probablemente no se parezca mucho a lo que dices. Entonces, ¿debería elegir trozos de 16 * 16 * 16 con una cantidad estática de bloques? Y también, usted dice que debería usar instancias, ¿es realmente necesario? Mi idea era generar una malla para cada fragmento, porque de esa manera puedo dejar de lado todos los triángulos invisibles.
66
No recomiendo usar instancias para los cubos como describe Turms. Esto solo reducirá sus llamadas de sorteo, pero no hará nada para sobregiros y caras ocultas; de hecho, limita sus manos para resolver ese problema, ya que la instancia funciona para todos los cubos tiene que ser el mismo: no puede eliminar caras ocultas de algunos cubos ni fusionar caras coplanarias en polígonos individuales más grandes.
DMGregory
Elegir el mejor motor de voxel puede ser un desafío. La gran pregunta que debe hacerse es "¿qué operaciones necesito hacer en mis voxels?" Eso guía las operaciones. Por ejemplo, le preocupa lo difícil que es averiguar qué vóxel es en qué lugar de un oct-tree. Los algoritmos Oct-tree son excelentes para los problemas que pueden generar esta información según sea necesario a medida que avanza por el árbol (a menudo de manera recursiva). Si tiene problemas específicos donde esto es demasiado costoso, entonces puede buscar otras opciones.
Cort Ammon
Otra gran pregunta es con qué frecuencia se actualizan los vóxeles. Algunos algoritmos son excelentes si pueden preprocesar datos para almacenarlos de manera eficiente, pero menos eficientes si los datos se actualizan de manera continua (como podrían hacerlo en una simulación de fluidos basada en partículas)
Cort Ammon

Respuestas:

23

Almacenar los bloques como las posiciones y los valores es realmente muy ineficiente. Incluso sin ninguna sobrecarga causada por la estructura o el objeto que utiliza, debe almacenar 4 valores distintos por bloque. Solo tendría sentido usarlo sobre el método de "almacenamiento de bloques en arreglos fijos" (el que describió anteriormente) es cuando solo una cuarta parte de los bloques son sólidos, y de esta manera ni siquiera toma otros métodos de optimización en cuenta.

Los octrees son realmente excelentes para juegos basados ​​en voxel, ya que se especializan en almacenar datos con características más grandes (por ejemplo, parches del mismo bloque). Para ilustrar esto, usé un quadtree (básicamente octrees en 2d):

Este es mi conjunto inicial que contiene mosaicos de 32x32, que equivaldrían a 1024 valores: ingrese la descripción de la imagen aquí

Almacenar esto como 1024 valores separados no parece tan ineficiente, pero una vez que alcanza tamaños de mapas similares a los juegos, como Terraria , cargar pantallas tomaría varios segundos. Y si lo aumenta a la tercera dimensión, comienza a utilizar todo el espacio del sistema.

Los quadtrees (o octrees en 3d) pueden ayudar a la situación. Para crear uno, puede ir desde los mosaicos y agruparlos, o desde una celda enorme y dividirlo hasta llegar a los mosaicos. Usaré el primer enfoque, porque es más fácil de visualizar.

Entonces, en la primera iteración, agrupa todo en celdas 2x2, y si una celda solo contiene mosaicos del mismo tipo, suelta los mosaicos y simplemente almacena el tipo. Después de una iteración, nuestro mapa se verá así:

ingrese la descripción de la imagen aquí

Las líneas rojas marcan lo que almacenamos. Cada cuadrado es solo 1 valor. Esto redujo el tamaño de 1024 valores a 439, que es una disminución del 57%.

Pero conoces el mantra . Avancemos un paso más y agrupemos estos en celdas:

ingrese la descripción de la imagen aquí

Esto redujo la cantidad de valores almacenados a 367. Eso es solo el 36% del tamaño original.

Obviamente, necesita hacer esta división hasta que cada 4 celdas adyacentes (8 bloques adyacentes en 3d) dentro de un fragmento se almacene dentro de una celda, convirtiendo esencialmente un fragmento en una celda grande.

Esto también tiene algunos otros beneficios, principalmente cuando se produce una colisión, pero es posible que desee crear un octree separado para eso, que solo se preocupa por si un solo bloque es sólido o no. De esa manera, en lugar de verificar la colisión para cada bloque dentro de un trozo, puede hacerlo contra las celdas.

Bálint
fuente
¡Gracias por su respuesta! Parece que los octree son el camino a seguir. (Dado que mi motor de vóxel será 3D), tengo algunas preguntas que me gustaría hacer: tu última imagen muestra las partes negras para tener cuadrados más grandes, ya que tengo la intención de tener un Minecraft como motor donde puede modificar el terreno de vóxel, preferiría mantener todo lo que tiene un bloque del mismo tamaño, porque de lo contrario haría las cosas muy complicadas, ¿eso es posible? (Todavía simplificaría las ranuras de vacío / aire del curso). Segundo , ¿hay algún tipo de tutorial sobre cómo programar un octree? ¡Gracias!
77
@ appmaker1358 eso no es problema en absoluto. Si el jugador intenta modificar un bloque grande, entonces lo divide en bloques más pequeños en ese momento . No es necesario almacenar valores de 16x16x16 de "roca" cuando se podría decir "todo este fragmento es roca sólida" hasta que ya no sea cierto.
DMGregory
1
@ appmaker1358 Como dijo DMGregory, actualizar los datos almacenados en un octree es relativamente fácil. Todo lo que tiene que hacer es dividir la celda en la que ocurrió el cambio hasta que cada subcelda contenga solo un tipo de bloque. Aquí hay un ejemplo interactivo con un quadtree . Generar uno también es simple. Crea una celda grande, que contiene completamente el fragmento, luego revisa recursivamente cada celda de la hoja (celdas que no tienen hijos), verifica si la parte del terreno que representa contiene múltiples tipos de bloques, si es así, subdivida el celular
Bálint
@ appmaker1358 El problema más grande es en realidad lo contrario: asegurarse de que el octree no se llene de hojas con solo un bloque, lo que puede suceder fácilmente en un juego de estilo Minecraft. Sin embargo, hay muchas soluciones al problema: se trata solo de elegir lo que considere apropiado. Y solo se convierte en un problema real cuando hay muchas obras en marcha.
Luaan
Los octrees no son necesariamente la mejor opción. Aquí hay una lectura interesante: 0fps.net/2012/01/14/an-analysis-of-minecraft-like-engines
Polygnome
7

Existen octrees para resolver exactamente el problema que describe, lo que permite el almacenamiento denso de datos escasos sin grandes tiempos de búsqueda.

El hecho de que tus vóxeles sean del mismo tamaño solo significa que tu octree tiene una profundidad fija. p.ej. para un trozo de 16x16x16, necesita como máximo 5 niveles de árbol:

  • raíz fragmentada (16x16x16)
    • octavante de primer nivel (8x8x8)
      • octavante de segundo nivel (4x4x4)
        • octavo de tercer nivel (2x2x2)
          • vóxel simple (1x1x1)

Esto significa que tiene como máximo 5 pasos para averiguar si hay un vóxel en una posición particular del bloque:

  • raíz del fragmento: ¿el fragmento completo tiene el mismo valor (por ejemplo, todo aire)? Si es así, hemos terminado. Si no...
    • primer nivel: ¿el octante que contiene esta posición tiene el mismo valor? Si no...
      • segundo nivel...
        • tercer nivel ...
          • ahora nos dirigimos a un único vóxel y podemos devolver su valor.

¡Mucho más corto que escanear incluso el 1% del camino a través de una matriz de hasta 4096 vóxeles!

Tenga en cuenta que esto nos permite comprimir los datos donde haya un octante completo del mismo valor, ya sea que ese valor sea todo aire o roca o cualquier otra cosa. Es solo donde los octantes contienen valores mixtos que necesitamos subdividir aún más, hasta el límite de los nodos de hoja de un solo vóxel.


Para dirigirse a los hijos de un fragmento, normalmente procederemos en el orden de Morton , algo como esto:

  1. X- Y- Z-
  2. X- Y- Z +
  3. X- Y + Z-
  4. X- Y + Z +
  5. X + Y- Z-
  6. X + Y- Z +
  7. X + Y + Z-
  8. X + Y + Z +

Entonces, nuestra navegación del nodo Octree podría verse así:

GetOctreeValue(OctreeNode node, int depth, int3 nodeOrigin, int3 queryPoint) {
    if(node.IsAllOneValue)
        return node.Value;

    int childIndex =  0;
    childIndex += (queryPoint.x > nodeOrigin.x) ? 4 : 0;
    childIndex += (queryPoint.y > nodeOrigin.y) ? 2 : 0;
    childIndex += (queryPoint.z > nodeOrigin.z) ? 1 : 0;

    OctreeNode child = node.GetChild(childIndex);

    return GetOctreeValue(
                child, 
                depth + 1,
                nodeOrigin + childOffset[depth, childIndex],
                queryPoint
    );
}
DMGregory
fuente
¡Gracias por su respuesta! Parece que los octree son el camino a seguir. Sin embargo, tengo 2 preguntas, usted dice que los octree son más rápidos que escanear a través de una matriz, lo cual es correcto. Pero no necesitaría hacer eso, ya que la matriz podría ser estática, lo que significa que puedo calcular dónde está el cubo que necesito. Entonces, ¿por qué necesitaría escanear? Segunda pregunta, en el último nivel del octree (el 1x1x1), ¿cómo sé dónde está el cubo, ya que si lo entiendo correctamente y octree node tiene 8 nodos más, cómo sabe qué nodo pertenece a qué posición 3d (¿O se supone que debo recordar eso yo mismo?)
Sí, ya cubriste el caso de un conjunto exhaustivo de voxels de 16x16x16 en tu pregunta, y pareciste rechazar la huella de memoria de 4K por fragmento (suponiendo que cada ID de voxel es un byte) como excesiva. La búsqueda que mencionó se produce al almacenar una lista de vóxeles con una posición, lo que le obliga a escanear a través de la lista para encontrar el vóxel en su posición de destino. 4096 aquí es el límite superior de la longitud de esa lista, por lo general será más pequeño que eso, pero generalmente aún más profundo que una búsqueda de octree correspondiente.
DMGregory