¿Almacenamiento eficiente para un octree escaso?

Question

¿Puede alguien 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 una aplicación de raycasting / voxel)

En este caso, el árbol se puede precalcular, por lo que estoy en su mayoría preocupado por el tamaño y el tiempo de búsqueda.

actualización

Para cualquier persona que quiera hacer esto, puede ser una solución más eficiente para guardar los nodos como un octree lineal generado con una curva Z-ORDE / Morton Tree.Al 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 Voxel individual.

Answer 1

No tengo mucha experiencia en HLSL, así que no estoy seguro de que esto satisfaga sus necesidades, aquí están mis pensamientos. Déjame saber si algo aquí no está sano para sus necesidades, me gustaría discutir, así que tal vez pueda aprender algo mismo.

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 utilizar como un campo de banderas. una. El campo W-BLAGS puede denotar qué nodos octales los niños siguen el 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 puede ser las dimensiones del cuadro delimitador, y se puede usar w para lo que sea.
3. Defina un vector especial que denota que sigue una lista de objetos. Por ejemplo, si el (W + Z) es un valor mágico. Un poco de FUNC (X, Y) puede, digamos, sea el número de objetos que siguen. O, lo que funciona. una. Cada nodo es potencialmente seguido de este vector especial, lo que indica que hay objetos almacenados en el nodo. Los siguientes vectores X son todos solo identificadores de objetos o algo así. B. Alternativamente, podría tener un nodo que solo especifica una lista de objetos en memoria. Nuevamente, no estoy seguro de lo que necesita aquí o las restricciones sobre cómo acceder a los objetos.

Entonces, primero, construye el octree y rellena con tus objetos. Luego, simplemente camine por Octree, saliendo de los vectores a un búfer de memoria.

Estoy pensando que una textura de 512x512 puede contener a un nivel de octree 5 completamente empacado profundos (32,768 nodos), cada uno que contiene 8 objetos. O, un octree de 4 niveles completamente empacado con 64 objetos cada uno.

Answer 2

Hay un gran artículo sobre los ocrees escasos centrados en las GPUS: Voxel escaso eficienteOctrees - análisis, extensiones e implementación