Alguém pode fornecer uma explicação curta e agradável (ou sugerir umaBo tutorial) sobre como lançar um raio contra um voxel octree sem recursão?

Eu tenho um modelo complexo assado em uma octree e preciso encontrar a melhor / mais próxima folha que cruza um raio. Uma caminhada de árvore iterativa de pesquisa padrão:

Pegue o nó raizVerifique se há interseçãoNão? SaídSim? Encontre um filho que cruze o raio mais próximo da origem do raio Laço até chegar a uma folha ou sair da árvore

Sempre retorna uma folha, mas nos casos em que a árvore armazena, digamos, terreno, o nó mais próximo à origem do raio não contém necessariamente a folha que é a melhor correspondência. Isso não é surpreendente - objetos mais altos em nós distantes não serão testados usando essa abordage

Eu posso fazer isso recursivamente encontrando todas as folhas que se cruzam na árvore, classificando por distância e escolhendo a mais próxima da posição do raio. No entanto, isso é lento e requer recursão.

Eu li um pouco sobre o uso do algoritmo de linha Bresenham para percorrer a árvore, o que parece exigir que cada nó contenha ponteiros para vizinhos adjacentes, mas não sou claro como implementá-lo de uma maneira úti

Alguma sugestão? Posso falsificar uma pilha no HLSL usando uma matriz de comprimento fixo ou uma estrutura com um elemento para cada entrada potencial da pilha, mas os requisitos de memória para isso podem se tornar incapacitantes com uma árvore suficientemente grand

Socorro