Ray Tracing Interactivo - Departamento de Informática

Ray Tracing Interactivo
Estrutura de Aceleração
Ademar Gonçalves
PG13364
Universidade do Minho, Braga
20 de Janeiro, 2009
Abstract. No departamento de informática desta universidade está a
ser desenvolvido um motor de Síntese de Imagem interactivo baseado no
algoritmo de Ray Tracing. Pretendia-se implementar uma estrutura de
aceleração, mais concretamente uma hierarquia de volumes, que permitisse reduzir o número de intersecções raio/primitiva geométrica, diminuindo assim o tempo de execução. A implementação foi bem sucedida e
os resultados comprovam que o objectivo de reduzir o número de intersecções e o tempo de execução foi conseguido.
1
Introdução
No âmbito do projecto IGIDE, financiado pela FCT e actualmente a decorrer
neste Centro de Investigação, está a ser desenvolvido um motor de Síntese de
Imagem (Rendering) interactivo baseado no algoritmo de Ray Tracing [1]. Este
algoritmo é tradicionalmente visto como produzindo imagens de alta qualidade
mas exigindo elevados tempos de processamento. Tem a particularidade de permitir várias “frames” por segundo e disponibilizar a possibilidade de modificar a
cena.
Desenvolvimentos recentes têm mostrado que o ray tracing interactivo é possível através do recurso à computação paralela (SIMD, multicore, cluster), optimização cuidada do código e a uma selecção criteriosa dos raios a disparar.
A eficiência de um ray tracer está dependente da eficiência da estrutura de ordenação do espaço 3D utilizada. Uma estrutura de ordenação eficiente diminui
o número de intersecções raio/primitiva geométrica, diminuindo consequentemente, o tempo de rendering. Exemplos típicos de estruturas de aceleração são
grelhas, kd-trees e hierarquias de volumes.
A eficiência destas estruturas é proporcional ao tempo de construção das
mesmas: quanto mais longo este tempo, mais eficiente a estrutura (i.e., menos
intersecções serão necessárias). No contexto do ray tracing interactivo, onde a
estrutura deverá ser construída para cada imagem, dispõe-se apenas de alguns
milissegundos para esta operação. De notar que neste trabalho a estrutura de
aceleração não é reconstruída para cada “frame”
O objectivo deste trabalho era implementar uma hierarquia de volumes, para
integração no ray tracer interactivo (iRT) em desenvolvimento neste Centro.
Uma hierarquia de volumes não passa de uma árvore de “bounding volumes”.
Um “bounding volume” para um conjunto de objectos é um volume fechado que
contém completamente todos os objectos do conjunto. São usados para melhorar
a eficiência de operações geométricas, usando volumes mais simples, para conter
objectos mais complexos. Como cada “bounding volume” de um dado nodo da
árvore engloba os “bounding volumes” dos seus filhos, se um raio falha a “bouding
volume” de um nodo, então o raio vai falhar todos os seu filhos, sendo possível
dessa forma evitar várias intersecções. Ao evitar várias intersecções consegue-se
atingir o objectivo, que é diminuir o número de intersecções.
Este artigo é constituído por várias secções. Depois da introdução, na secção
trabalho relacionado, são referidas algumas escolhas alternativas que poderiam
ter sido feitas para a estrutura de aceleração. Descreve-se com mais detalhe o
funcionamento da hierarquia de volumes, assim como a heurística escolhida para
a sua construção.
Na secção número três descrevem-se os algoritmos de construção e travessia.
De seguida, na secção quatro são analisados os resultados, tendo em conta diferentes métricas. Finalmente na última secção são discutidas algumas conclusões
e são feitas algumas sugestões para trabalho futuro.
2
Hierarquia de Volumes
Apesar das duas hipóteses referidas nas sub-secções anteriores, neste trabalho
foi pedido o uso de uma hierarquia de volumes [3].
Como já foi dito, uma hierarquia de volumes não passa de uma árvore de
“bounding volumes”. Cada “bounding volume” de um nodo engloba os seus filhos
e o “bounding volume” de uma folha da árvore engloba uma ou mais primitivas.
Se um raio falha a “bouding volume” de um nodo, então o raio vai falhar todos
os seu filhos, sendo possível dessa forma evitar várias intersecções.
Apresenta-se a seguir um exemplo do funcionamento desta estrutura de aceleração.
1. Inicialmente temos um conjunto de primitivas
2. Encontra-se a “bounding box” que engloba todos os objectos
3. Dividide-se os objectos em 2 grupos de acordo com algum critério de
divisão (secção 2.1)
4. Recursivamente faz-se o mesmo
5. No final, obtemos uma “bounding box” que engloba um número de primitivas que vai depender do critério de paragem. No caso da figura, um triângulo
por “bounding box”.
Fig. 1. Construção da hierarquia de “bounding volumes”
2.1
SAH
Apesar de existirem vários critérios de subdivisão, nas hierarquias de volumes
o método mais conhecido para maximizar a eficiência é o SAH (Surface Area
Heuristic) [4].
Neste que foi o método escolhido na realização deste trabalho, a cena original é
dividida usando uma estratégia para minimizar o custo esperado de travessia.
Dado um conjunto N de primitivas contidas numa árvore que abrange o volume 3D V e assumindo que a árvore é dividida em duas partes L e R com número
de triângulos N L e NR e com volumes associados VL e VR respectivamente, o
custo esperado de travessia para a árvore pode ser estimado segundo a fórmula,
Custo(V → {L, R}) = KT + KI (
SA(VL )
SA(V ) NL
+
SA(VR )
SA(V ) NR
),
onde SA(V) é a “surface area” de V e KT e KI são constantes específicas da
implementação para estimar o custo da travessia, e intersecção com triângulo
respectivamente.
Usando esta estimativa de custo, são avaliadas várias possibilidades e é escolhida
a que tem menor custo, voltando a fazê-lo recursivamente. Na implementação foi
usado o algoritmo de min-max binning [2], cuja ideia, é permitir saber facilmente
onde começa e onde termina uma AABB (Axis Aligned Bounding Box).
3
3.1
Trabalho Relacionado
Kd-tree
Neste trabalho poderia ter sido usada outra estrutura de aceleração que não a
hierarquia de volumes. Uma das possibilidades seria usar uma Kd-tree [8], que
é a estrutura de aceleração muitas vezes escolhida para os algoritmos de ray
tracing interactivo.
Uma kd-tree (fig 1) é uma árvore BSP alinhada com os eixos, ou seja, apenas
usa planos de corte prependiculares aos eixos do sistema de coordenadas. Começa
com uma “bouding box” que engloba toda a cena. Se o número de primitivas
dentro da “box” for maior que um valor de “threshold”, a “box” é dividida a meio
por um plano. Um problema surge na divisão, quando certas primitivas ficam a
pertencer a ambos os lados da divisão.
É melhor que as Grids caso a cena seja distribuída irregularmente.
A hierarquia de volumes tem uma vantagem: quando a geometria é alterada é possível manter a topologia da árvore e alterar apenas as dimensões dos
“bounding volumes”. A Kd-tree tem de ser rescontruída do início.
Fig. 2. Exemplo de uma Kd-Tree 3D
3.2
Grelha
Outra possibilidade seria usar uma grelha [6,7] que é uma estrutura de aceleração
que divide o espaço em “voxels” de tamanho igual (fig 2).
É fácil de construir pois não necessita que se decida onde é que se divide o espaço. Isto é determinado pela própria grelha independentemente da distribuição
espacial da geometria.
Esta simplicidade também tem desvantagens, uma vez que pode ter uma eficiência reduzida, quando os dados da cena não estão distribuídos uniformemente.
Se existe uma pequena região do espaço, com muita geometria concentrada, toda
a geometria pode ficar contida apenas num “voxel”. Quando um raio passa nesse
“voxel”, quantas mais intersecções forem calculadas, pior será a eficácia.
Fig. 3. Exemplo de uma grelha
4
4.1
Descrição e Abordagem Utilizada
Construção
Como já foi referido na secção 2.4, a construção da estrutura de aceleração usa
a heurística SAH (Surface Area Heuristic) [4] baseada no algoritmo de binning
[2].
Inicialmente são calculadas e guardadas as “bounding boxes” de todos os
triângulos que constituem a cena. É calculada a “bounding box” geral da cena
que será a “bounding box” da raiz da árvore.
De seguida começa-se a construir a hierarquia de volumes propriamente
dita. Depois de efectuados os cálculos necessários para saber a posição de corte
(critério de subdivisão), os triângulos vão sendo divididos pelas sub-árvores esquerda e direita até que o número de triângulos seja inferior ou igual ao valor
previamente definido (critério de paragem).
Quando assim for, é criada uma folha da árvore. É possível definir esse limiar
com o valor 1 ou 2, o que significa que a árvore vai conter 1 ou 2 triângulos por
folha respectivamente.
4.2
Travessia
Para cada raio a árvore vai ser percorrida a partir da raiz , testando se existe
intersecção entre o raio e a “bounding box” de cada nodo.
Quando não existe intersecção num determinado nodo, os seus filhos não são
testados, reduzindo desta forma o número de intersecções significativamente.
Sempre que se chega a uma folha da árvore, vai ser feita a intersecção entre
o raio e os triângulos nela contidos (1 ou 2).
5
5.1
Resultados
Ambiente Experimental
O equipamento usado para teste, foi uma máquina dual quad-core Intel Xeon
E5420, 2.5 GHZ com 8GB de RAM, sistema operativo Linux CentOS 4, no
entanto, o código não é “multithreaded”.
Foram usadas três cenas diferentes, chamadas sphere.geom, 9spheres.geom,
63spheres.geom com 759 , 6831 e 47817 triângulos respectivamente.
5.2
Tempo de Execução
Na tabela 1, são apresentados os tempos de execução da aplicação. É usado o
acrónimo BVH do nome em inglês para hierarquia de volumes. Assim sendo, para
três cenas diferentes, apresenta-se o número de triângulos que constituem a cena,
e os tempos de execução da aplicação sem estrutura de aceleração, com estrutura
de aceleração (1 e 2 triângulos por folha). O tempo de execução com estrutura
de aceleração é ainda dividido em tempo de construção e tempo de travessia,
que como os nomes indicam, se referem às duas fases do algoritmo de ray tracing.
Cena
# Tri sem BVH
BVH (1T)
BVH (2T)
constr. travess. total ganho constr. travess. total ganho
sphere 759
0.6323 0.0037 0.0162 0.0199 31.77 0.0023 0.01520 0.0175 36.13
9sphere 6.831 4.6684 0.0339 0.0598 0.0937 49.82 0.0216 0.0578 0.0794 58.80
63sphere 47.817 30.7135 0.2435 0.0977 0.3412 89.75 0.1566 0.094 0.2505 122.61
Table 1. Tempos de execução (segundos) , total = construção + travessia
Analisando os resultados, é de notar um ganho bastante grande relativamente
ao tempo sem BVH. Foram conseguidos melhores resultados na BVH com dois
triângulos por folha do que na BVH com apenas 1. Os ganhos para cada cena e
para cada versão da BHV ( 1 e 2 triângulos ) são detalhados a seguir:
sphere:
GanhoT 1 =
TsemBV H
TcomBV H1T
= 31.77
GanhoT 2 =
TsemBV H
TcomBV H2T
= 36.13
GanhoT 1 =
TsemBV H
TcomBV H1T
= 49.82
GanhoT 2 =
TsemBV H
TcomBV H2T
= 58.80
9spheres:
63spheres:
GanhoT 1 =
TsemBV H
TcomBV H1T
= 89.75
GanhoT 2 =
TsemBV H
TcomBV H2T
= 122.61
É possivel verificar que quanto maior for a cena, ou seja, quanto maior for o
número de triângulos que a constituem, maior é o ganho. Regista-se também, um
ganho constantemente superior da BVH com 2 triângulos por folha em relação
à BVH com 1.
Analisando com maior cuidado os tempos de execução com BVH, verificamos
algo que não era esperado. Esperava-se que com aumento do número de triângulos por folha, o tempo de construção fosse menor, mas por outro lado que tempo
de travessia fosse maior.
Na prática o tempo de construção diminui com o aumento do número de
triângulos por folha, mas inesperadamente o tempo de travessia também diminui.
A explicação possível para esta situação é que o teste com as “bounding boxes”
não é muito eficiente, fazendo com que o aumento do número de triângulos por
folha saia a ganhar, uma vez que há menos testes com as “bounding boxes” a
realizar.
5.3
Número de Intersecções
Na tabela 2, são apresentadas o número de intersecções raio/triângulo para cada
uma das cenas testadas. O número de intersecções ideais são as verdadeiramente
necessárias, isto é, o número de raios que efectivamente intersecta um triângulo.
De notar que em alguns dos pixeis não se projecta qualquer geomtria.
Cena Intersecções Ideais Sem BVH BVH (1T) BVH (2T)
sphere
9.960
30.400.000
31.030
41.974
9sphere
20.960
273.600.000
76.356
107.076
63sphere
33.448
1.915.200.000 117.323
165.498
Table 2. Número de intersecções raio/triângulo
Apresenta-se de seguida a razão entre o número de intersecções com BVH e
o número de intersecções ideais. O valor obtido demonstra o quanto ainda é possível ganhar. Quanto maior o valor, maiores são as possibilidades para melhorar.
sphere:
#I1 =
#IBV H1T
#Iideais
= 3.12
#I2 =
#IBV H2T
#Iideais
= 4.21
9spheres:
#I1 =
#IBV H1T
#Iideais
= 3.64
#I2 =
#IBV H2T
#Iideais
= 5.11
63spheres:
6
#I1 =
#IBV H1T
#Iideais
= 4.95
#I2 =
#IBV H2T
#Iideais
= 4.94
Conclusões
Neste projecto foi implementada uma estrutura de aceleração para o “ray tracer”
existente, diminuíndo assim o número de intersecções realizadas e consequentemente o tempo de “rendering”.
Como é possível verificar na secção referente aos resultados os objectivos
foram cumpridos, uma vez que os tempos de execução com o uso da estrutura
de aceleração são bastante mais baixos.
Relativamente a trabalho futuro, seria interessante abordar as seguintes tarefas:
– Optimizar código e algoritmos para construção e travessia da estrutura de
aceleração
– Optimizar a BVH para reduzir o número de intersecções efectivamente real#Ibvh
izadas. A razão #I
mostra que há margem para melhorar.
ideal
– Estudar o comportamento com outra heurística mais simples que a utilizada.
Espera-se que o tempo de construção diminua, mas em contrapartida que o
tempo de travessia aumente. Pode ser útil para geometria dinâmica.
References
1. Andrew Glassner. An Introduction to Raytracing. Academic Press, 1989.
2. Maxim Shevtsov, Alexei Soupikov e Alexander Kapustin. Highly Parallel Fast
KD-tree Construction for Interactive Ray Tracing of Dynamic Scenes. Intel
Corporation, 2007.
3. Herman Haverkort. Introduction to bounding volume hierarchies. Ultrecht University, 2004.
4. Ingo Wald. On fast Construction of SAH-based Bounding Volume Hierarchies. SCI
Institute, University of Utah, 2007.
5. Johannes Gunther, Stefan Popov, Hans-Peter Seidel e Philipp Slusallek. Realtime Ray Tracing on GPU with BVH-base Packet Traversal. Proceedings of the
IEEE/Eurographics Symposium on Interactive Ray Tracing, 2007.
6. Erik Reinhard, Brian Smitse Charles Hansen. Dynamic acceleration structures for
interactive ray tracing. University of Utah, 2000.
7. Ingo Wald, Thiago Ize, Andrew Kensler, Aaron Knoll e Steven Parker. Ray tracing
animated scenes using coherent grid traversal. ACM Transactions on Graphics, 2006.
8. Ingo Wald e Vlastimil Havran. On building fast kd-trees for ray tracing. Proceedings
of 2006 IEEE Symposium on Interactive Ray Tracing, 2006
9. http://lucille.svn.sourceforge.net/viewvc/lucille/