Ray Tracing Interactivo - Departamento de Informática
Transcrição
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/
Documentos relacionados
Processo de Acabamento Virtual Professor: João Humberto
totalmente remodelado em relação às versões anteriores Complementa o Blender, equipando-o para a obtenção de imagens de maior qualidade Mais sobre o Yaf(a)Ray: http://wiki.yafray.org/bin/view.p...
Leia mais