Experiências com Construção de KD-Trees SAH em Streaming

Uma das principais razões para os avanços recentes no desempenho de ray tracing é o uso de estruturas de aceleração otimizadas, nomeadamente kd-trees baseados na heurística de área da superfície (SAH). Embora existam algoritmos para construir essas árvores de busca em O(n log n), os tempos de construção para cenas maiores ainda são altos e não permitem a reconstrução da kd-tree a cada quadro para apoiar mudanças dinâmicas. Neste artigo, propomos modificações nos algoritmos de construção de kd-tree anteriores que aumentam significativamente a coerência dos acessos à memória durante a construção da kd-tree. Além disso, fornecemos resultados teóricos e práticos sobre o subamostragem conservadora da função de custo SAH.