Estou procurando um bom algoritmo de interseção ray-octree, que me dê as folhas pelas quais o raio passa de maneira iterativa. Estou planejando implementá-lo na CPU, já que eu não quero mergulhar na CUDA ainda :)

No momento, o meu radiodifusor Voxel apenas faz o 3D DDA (versão Amanatides / Woo) em uma matriz não hierárquica de voxels XxYxZ. Você pode imaginar que isso é muito caro quando há muito espaço vazio, como demonstrado na figura a seguir (vermelho brilhante = mais trabalho :)):

Eu já descobri que existem dois tipos de algoritmos para essa tarefa:debaixo para cima, que funciona das folhas de volta para cima, eCareca, que é basicamente pesquisa em profundidade.

Eu já encontrei o algoritmo de Revelles de 2000, chamadoUm algoritmo paramétrico eficiente para travessia de octree, o que parece interessante, mas é bastante antigo. Este é um algoritmo top-down.

A abordagem bottom-up mais popular parece serK. Sung, Algoritmo de Traversal DDA Octree para Ray Tracing, Eurographics'91, North Holland-Elsevier, ISBN 0444 89096 3, p. 73-85. O problema é que a maioria dos algoritmos de travessia DDA Octree espera que a octree seja da mesma profundidade, o que eu não quero - as subárvores vazias devem ser apenas um ponteiro nulo ou algo similar.

Na literatura mais recente sobre Sparse Voxel Octrees eu consegui ler através de (mais notavelmenteO trabalho de Laine em SVO's, todos eles parecem ser baseados em algum tipo de versão implementada pela GPU do DDA (estilo Amanatides / Woo).

Agora, aqui está a minha pergunta: alguém tem alguma experiência em implementar um algoritmo básico de interseção ray-octree sem frescuras? O que você recomendaria?