Según la página de Wikipedia sobre vóxeles, "la [...] posición de un vóxel se infiere en función de su posición con respecto a otros vóxeles (es decir, su posición en la estructura de datos que forma una sola imagen volumétrica)".
¿Cómo se debe implementar tal estructura de datos? Estaba pensando en un octree, pero me pregunto si hay algo más de lo que nunca haya oído hablar.
Respuestas:
Primero. Vamos a escribir qué sabemos sobre cada vóxel:
Almacenamiento general
La forma general es simplemente esto:
Tenga en cuenta que ese triplete (x, y, z) identifica cada vóxel de manera única, ya que el vóxel es un punto en el espacio y no hay forma de que dos puntos ocupen un lugar (creo que estamos hablando de datos estáticos del vóxel).
Debería estar bien para datos simples. Pero de ninguna manera es una estructura de datos rápida.
El renderizado es AFAIK hecho por el algoritmo scanline. El artículo de Tom's Hardware sobre voxels tiene una imagen del algoritmo scanline .
Búsqueda rápida
Si se necesita una búsqueda rápida, la estructura de datos más rápida para la búsqueda es hash (también conocido como matriz, mapa ...). Entonces tienes que hacer hash con eso. Entonces, ingenuamente, queremos la forma más rápida de obtener elementos arbitrarios:
Esto tiene O (1) para buscar voxel por coordenadas x, y, z.
El problema es que los requisitos de espacio son O (D ^ 3), donde D es el rango de cada número x, y y z (olvide el número real, ya que si fueran caracteres, que tienen un rango de 256 valores, habría 256 ^ 3 = 2 ^ 24 == 16 777 216 elementos en la matriz).
Pero depende de lo que quieras hacer con los vóxeles. Si la representación es lo que desea, entonces probablemente sea esta matriz la que desea. Pero el problema de almacenamiento sigue siendo ...
Si el problema es el almacenamiento
Un método es usar la compresión RLE en la matriz. Imagine una rebanada de vóxeles (conjunto de vóxeles, donde los vóxeles tienen un valor constante coordinado ... como el plano donde z = 13, por ejemplo). Tal porción de vóxeles se vería como un simple dibujo en MSPaint . El modelo de vóxel, diría, generalmente ocupa una fracción de todos los lugares posibles (espacio D ^ 3 de todos los vóxeles posibles). Creo que "tomar un par del triplete de coordenadas y comprimir el eje restante" haría el truco (por ejemplo, tomar [x] [y] y para cada elemento comprimir todos los vóxeles en el eje z en x, y .. Debería haber 0 a pocos elementos, RLE estaría bien aquí):
Otro método para resolver el problema de almacenamiento sería en lugar de la matriz utilizando la estructura de datos de árbol:
Si los vóxeles son un mapa de altura simplista, puede almacenar eso. O bien, puede almacenar parámetros para la función que genera el mapa de altura, es decir, generarlo procesalmente ...
Y, por supuesto, puede combinar todos los enfoques posibles. Pero no exagere, a menos que pruebe que su código funciona y mida que es REALMENTE más rápido (por lo que vale la pena la optimización).
TL; DR
Además de Octrees es la compresión RLE con voxels, google "voxlap", "ken silverman" ...
Recursos
Hay una lista de recursos y discusión sobre cómo hacer un procesador rápido de vóxel, incluye documentos y código fuente .
fuente
Hay dos aspectos diferentes de la estructura de datos de los que pueden estar hablando.
Estructuras de matriz
Cuando hace referencia a un elemento de una matriz de cualquier número de dimensiones, considere que la matriz en sí misma, una vez que pasa los índices (por ejemplo
myArray[4][6][15]), sabe lo que hay en esa ubicación. Si lo que está en esa ubicación es un vóxel, ese vóxel no necesita registrar adicionalmente sus propias coordenadas x, y y z: la matriz que contiene el vóxel especifica su ubicación mundial implícitamente en función de su ubicación indexada por la matriz.La razón por la que esto es bueno es que la aritmética del puntero utilizada para este tipo de acceso a la matriz es inherentemente rápida y, en general, proporciona la base para la mayoría de las matrices rápidas (a menudo llamadas "nativas") que se encuentran en todos los idiomas. La desventaja de estas matrices es que deben tener elementos de igual tamaño en bytes, para que dicha aritmética de puntero sea aplicable.
Octrees
(Observo este segundo, porque es menos probable que esto sea a lo que se refiere wikipedia, y las implementaciones de voxel no requieren el uso de octrees, aunque casi todos los modernos usan octrees).
El nodo raíz de un octree es un cubo único e indiviso. Pongamos un ejemplo. Digamos que la raíz de tu octree, el centro del cubo, está
{0, 0, 0}en el espacio 3D. Una vez que comience a colocar objetos dentro de ese espacio (léase: más de un objeto), es hora de subdividir el octree más. Aquí es donde se divide en 8 ( oct- ), dividiéndolo en 3 planos, siendo estos planos los planos xy, xz e yz. Su cubo original ahora contiene exactamente 8 cubos más pequeños. Cada uno de estos subnodos se posiciona como un desplazamiento desde el cubo principal central . Es decir, que por ejemplo, el cubo que se encuentra en el octante positivo xyz tendría un desplazamiento del centro del cubo principal / que contiene exactamente{root.width / 4, root.height / 4, root.depth / 4}. En lugar de especificar una posición absoluta para cada subnodo, tiene más sentido lógico considerar el nodo padre como el origen de su espacio para niños. Esta es la misma forma en que funcionan los gráficos de escena.Es bastante simple ver esto en un dibujo 2D, donde dibujas un cuadrado y lo subdivides en 4 regiones iguales. Si, como nuestro nodo raíz octree, se considera que el centro del cuadrado principal es
{0, 0}, entonces los 4 centros de los cuadrados secundarios serían{root.width / 4, root.height / 4},{-root.width / 4, root.height / 4},{root.width / 4, -root.height / 4},{-root.width / 4, -root.height / 4}... En relación con sus padres, el mismo principio que en 3D.
fuente
Puedes usar RLE. Pero puede usar SVO (Sparse Voxel Octree), id Tech 6 usa SVO. Un SVO es una técnica de representación de gráficos por computadora en 3D que utiliza un enfoque de emisión de rayos o, a veces, un trazado de rayos en una representación de datos de octree.
La técnica varía un poco, pero generalmente se basa en generar y procesar el casco de puntos (vóxeles dispersos) que son visibles o pueden ser visibles, dada la resolución y el tamaño de la pantalla.
Use la emisión de rayos, porque es más rápido.
fuente
En general, puede evitar una estructura de datos 3D para el terreno. Puede usar un mapa de altura en su lugar. Esto se puede voxelizar de manera muy económica y eficiente en tiempo de ejecución. Por lo general, vale la pena (en mi experiencia) rastrear la altura mínima que necesita para renderizar en cada columna y también a veces ángulos start-stop-top para que también pueda eliminar las columnas de la cara posterior.
Aquí hay uno que hice hace mucho tiempo: http://sites.google.com/site/williamedwardscoder/spinning-voxels-in-flash
Si su terreno tiene una pequeña cantidad de voladizos o cuevas u otras características que no pueden ser representadas por un mapa de altura, entonces puede tener agujeros en su mapa de altura y tener una representación alternativa, por ejemplo, verdaderos objetos voxel 3D que llenen solo aquellos lugares localizados donde el gasto de tiempo de ejecución Está justificado.
Las representaciones dispersas de voxel valen la pena cuando tienes grandes mundos voxel verdaderos. John Carmack los ha estado hablando durante los últimos años ...
fuente