Raytracing acelerado: Bounding Interval Hierarchy

Raytracing acelerado: Bounding Interval Hierarchy

Luciano Monteiro dos Santos

Bounding Interval Hierarchy

Estrutura de particionamento espacial; Abordagem hibrida entre árvores de partição

(BSP, Kd-Trees) e Hierarquias de Volumes (Bounding Volume Hierarchy); Permite construção e atualização rápidas, o que

possibilita a utilização em cenas dinâmicas; Desempenho em aceleração comparável com as kd-

trees.

Vantagens e Desvantagens

Vantagem Sem subdivisão de elementos

O tamanho da arvore na memória é deterministico. A profundidade de busca tende a ser menor.

Estrutura semelhante à kd-tree permite busca sem pilha

Desvantagem Sub-arvores se sobrepôem parcialmente

Não é possível retornar logo após encontrar a primeira intersecção – é necessário testar os outros nós na pilha.

Construção

Escolhe-se um plano de particionamento a partir de uma dada heurística; Comumente, divide-se a maior dimensão do volume

ao meio. Classifica-se os objetos entre os filhos da

esquerda e da direita, de acordo com o lado no qual cada objeto mais pertence;

Ajusta-se os planos limites para conter todos os objetos;

Construção

Construção

Construção

Pesquisa

Semelhante à kd-tree. Deve-se testar quatro casos distintos:O raio atravessa apenas o filho da esquerda;O raio atravessa apenas o filho da direita;O raio atravessa ambos os filhos;O raio não atravessa nenhum filho (não

possível numa kd-tree normal);

Exemplo: Arauna

Engine experimental para jogos com Ray-tracing em tempo real;

Utiliza Kd-trees para elementos estáticos e BIHs para elementos dinâmicos;

Exemplo: Arauna

Aplicação: Bunny.rt4

Original BIH

2.500s 43s

Referências

Instant Ray Tracing: The Bounding Interval Hierarchy. Carsten Wächter and Alexander Keller. Eurographics Symposium on Rendering (2006)

Arauna Real Time Raytrace Engine: http://igad.nhtv.nl/~bikker/