Eficiente de armazenamento para um esparso octree?

Question

Alguém pode sugerir um rápido, método eficiente para armazenar e acessar um esparso octree?

De preferência, algo que pode ser facilmente implementado em HLSL.(Eu estou trabalhando um raycasting/voxel app)

Neste exemplo, a árvore pode ser calculados, então eu estou mais preocupado com o tamanho e o tempo de pesquisa.

Atualização

Para quem quer fazer isso, uma solução mais eficiente pode ser a de armazenar a nós como um linear octree gerado com uma Z-ordem de curva/Morton árvore.Desta forma, elimina o armazenamento do interior de nós, mas podem exigir o cruzamento linear árvore matriz, com um segundo de dados "textura", contendo informações sobre cada voxel.

Answer 1

Eu não sou muito experiente em HLSL, então eu não tenho certeza que isso vai atender às suas necessidades, aqui estão os meus pensamentos.Deixe-me saber se algo aqui não é sadio para as suas necessidades - eu gostaria de discutir, então talvez eu possa aprender alguma coisa.

1. Cada nó na octree pode existir como um vector3, onde a (x,y,z) componente representa o ponto central do nó.W componente pode ser usado como um campo de sinalizadores.um.W-campo sinalizadores podem indicar que octante nós filho siga o nó atual.Isso exigiria 8 bits de valor.
2. Cada entidade armazenados em seu octree pode ser armazenado como uma caixa delimitadora, onde r,g,b pode ser a caixa delimitadora dimensões, e w pode ser usado para qualquer coisa.
3. Definir um especial vetor indicando que um objeto lista segue.Por exemplo, se o (w + z) é um pouco de magia valor.Algumas func(x, y) pode, digamos, ser o número de objetos que se seguem.Ou, o que funciona.um.Cada nó é potencialmente seguido por este especial vetor, indicando que há objetos armazenados no nó.O próximo X vetores são apenas os identificadores de objeto ou algo assim.b.Como alternativa, você poderia ter um nó que apenas especifica um objeto em memória lista.Novamente, não sei o que você precisa aqui ou restrições sobre como acessar objetos.

Assim, em primeiro lugar, construir a octree e enchê-lo com seus objetos.Em seguida, basta andar a octree, a saída de vetores para um buffer de memória.

Eu estou pensando que um 512x512 textura pode realizar uma totalmente embalado octree 5 níveis de profundidade (32.768 e nós), cada um contendo 8 objetos.Ou, totalmente embalado 4-nível de octree com 64 objetos de cada um.

Answer 2

Há um ótimo artigo sobre os ocorros esparsos com foco em GPUs: eficiente voxel esparsoOcrees - análise, extensões e implementação