Almacenamiento eficiente para un octree escaso?

Question

¿Alguien puede sugerir un rápido, método eficiente para almacenar y acceder a un octree escaso?

Preferiblemente algo que se puede implementar fácilmente en HLSL. (Estoy trabajando en una aplicación raycasting/voxel)

En este caso, el árbol se puede calcular previamente, por lo que me preocupa principalmente el tamaño y el tiempo de búsqueda.

actualización

para cualquiera que quiera hacer esto, una solución más eficiente puede ser para almacenar los nodos como octree lineal generado con un árbol curva de orden Z/Morton. Hacerlo elimina el almacenamiento de los nodos internos, pero puede requerir referencias cruzadas de la matriz de árbol lineal con una segunda "textura de datos" que contiene información sobre el vóxel individual.

Answer 1

No tengo mucha experiencia en HLSL, así que no estoy seguro de que esto satisfaga sus necesidades, estos son mis pensamientos. Avíseme si algo aquí no es sensato para sus necesidades. Me gustaría hablar para que yo también pueda aprender algo.

1. Cada nodo en el octree puede existir como un vector3, donde el componente (x, y, z) representa el punto central del nodo. El componente w se puede usar como un campo de banderas. a. El campo w-flags puede indicar qué nodos secundarios de octante siguen al nodo actual. Esto requeriría 8 bits del valor.
2. Cada entidad almacenada en su octree se puede almacenar como un cuadro delimitador, donde r, g, b pueden ser las dimensiones del cuadro delimitador, yw se puede usar para lo que sea.
3. Define un vector especial que indica que sigue una lista de objetos. Por ejemplo, si el (w + z) es algún valor mágico. Algunos func (x, y) pueden, digamos, ser el número de objetos que siguen. O lo que sea que funcione a. Cada nodo es potencialmente seguido por este vector especial, lo que indica que hay objetos almacenados en el nodo. Los siguientes vectores X son solo identificadores de objeto o algo así. b. Alternativamente, podría tener un nodo que simplemente especifique una lista de objetos en memoria. De nuevo, no estoy seguro de lo que necesita aquí o las restricciones sobre cómo acceder a los objetos.

Así que, primero, construye el octree y rellena con tus objetos. Luego, simplemente recorre el octárbol, sacando los vectores a un búfer de memoria.

Estoy pensando que una textura de 512x512 puede contener un octree totalmente empaquetado de 5 niveles de profundidad (32,768 nodos), cada uno con 8 objetos. O bien, un octree completamente embalado de 4 niveles con 64 objetos cada uno.

Answer 2

Hay un gran artículo sobre octrees dispersos centrados en la GPU: Efficient Sparse Voxel Octrees – Analysis, Extensions, and Implementation