Ray TracingRay Tracing

Ismael Andrade PimentelIsmael Andrade Pimentel

Objetivo do trabalhoObjetivo do trabalho

Apresentar técnicas para diminuir a complexidade do Apresentar técnicas para diminuir a complexidade do algoritmo (tempo de execução) sem perda de qualidade visual.algoritmo (tempo de execução) sem perda de qualidade visual.

DefiniçãoDefiniçãoRay tracingRay tracing é um algoritmo de computação gráfica usado é um algoritmo de computação gráfica usado para síntese (renderização) de imagens tridimensionais.para síntese (renderização) de imagens tridimensionais.O método utilizado pelo algoritmo, baseia-se na simulação do O método utilizado pelo algoritmo, baseia-se na simulação do trajeto que os raios de luz percorreriam no mundo real, mas, trajeto que os raios de luz percorreriam no mundo real, mas, neste caso, de trás para a frente. Ou seja, no mundo real, os neste caso, de trás para a frente. Ou seja, no mundo real, os raios de luz são emitidos a partir de uma fonte de luz, raios de luz são emitidos a partir de uma fonte de luz, percorrendo o espaço até encontrar um objeto. Após os raios percorrendo o espaço até encontrar um objeto. Após os raios de luz atingirem o objeto, estes são retratados ou refletidos, de de luz atingirem o objeto, estes são retratados ou refletidos, de acordo com as características do objeto, nomeadamente, cor, acordo com as características do objeto, nomeadamente, cor, textura e transparência, alterando assim a sua trajetória, e textura e transparência, alterando assim a sua trajetória, e fazendo com que apenas uma infinitésima minoria dos raios fazendo com que apenas uma infinitésima minoria dos raios que partiram da fonte de luz atinjam, por fim, os olhos do que partiram da fonte de luz atinjam, por fim, os olhos do observadorobservador..

Definição ContinuaçãoDefinição ContinuaçãoO algoritmo O algoritmo ray tracingray tracing é um algoritmo recursivo que consiste é um algoritmo recursivo que consiste em projetar, a partir do observador, um vetor (raio) por cada em projetar, a partir do observador, um vetor (raio) por cada um dos pixeis constituintes da nossa cena/imagem, vetor este um dos pixeis constituintes da nossa cena/imagem, vetor este que irá intersectar os objetos que formam a cena em análise. que irá intersectar os objetos que formam a cena em análise. As intersecções a que estão sujeitos cada um dos vetores As intersecções a que estão sujeitos cada um dos vetores projetados tem que ser confirmadas para todos os objetos que projetados tem que ser confirmadas para todos os objetos que compõe a imagem a fim de determinar qual o que está mais compõe a imagem a fim de determinar qual o que está mais próximo do observador.próximo do observador.

AlgoritmoAlgoritmoPara cada Para cada pixelpixel da tela da telaLance uma raio;Lance uma raio;Para cada objeto da cenaPara cada objeto da cena

Calcule a interseção do raio com este o objeto;Calcule a interseção do raio com este o objeto;Armazene a interseção mais próxima;Armazene a interseção mais próxima;

Se o raio interceptou algum objeto Se o raio interceptou algum objeto Calcule a contribuição das luzes neste ponto;Calcule a contribuição das luzes neste ponto;Pinte o Pinte o pixelpixel com esta cor; com esta cor;

Interseção Interseção

O algoritmo de Ray Tracing gasta entre 75% e 95% de seu O algoritmo de Ray Tracing gasta entre 75% e 95% de seu tempo determinando as interseções com os objetos, por isso, a tempo determinando as interseções com os objetos, por isso, a eficiência da rotina de interseção raio-objetos afeta eficiência da rotina de interseção raio-objetos afeta significativamente a eficiência do algoritmo. Os objetos da significativamente a eficiência do algoritmo. Os objetos da cena a ser visualizada são descritos sob a forma de estruturas cena a ser visualizada são descritos sob a forma de estruturas de dados.de dados.

SoluçõesSoluçõesVolumes envolventes (esferas, caixas,....)Volumes envolventes (esferas, caixas,....)Divisão espacial ( octree, bsp, grid uniforme....)Divisão espacial ( octree, bsp, grid uniforme....)OBB-TreeOBB-Tree

Sólidos Limitantes ( Bounding Sólidos Limitantes ( Bounding Volumes )Volumes )

Para evitar estas interseções desnecessárias, fazemos a Para evitar estas interseções desnecessárias, fazemos a interseção do raio com um sólido limitante, antes de interseção do raio com um sólido limitante, antes de interceptá-lo com a superfície do objeto. Este sólido limitante interceptá-lo com a superfície do objeto. Este sólido limitante geralmente é uma esfera (bounding sphere) ou um bloco geralmente é uma esfera (bounding sphere) ou um bloco (bounding box). A idéia é simples: se o raio não intercepta o (bounding box). A idéia é simples: se o raio não intercepta o sólido limitante do objeto, então este raio não interceptará o sólido limitante do objeto, então este raio não interceptará o objeto e, então, deve ser descartado. Assim, eliminamos as objeto e, então, deve ser descartado. Assim, eliminamos as interseções desnecessárias. O uso de sólidos limitantes pode interseções desnecessárias. O uso de sólidos limitantes pode aumentar em até 40% a velocidade de renderização das cenas.aumentar em até 40% a velocidade de renderização das cenas.

OctreeOctreeA Octree é uma estrutura de dados tipo arvore onde cada nó A Octree é uma estrutura de dados tipo arvore onde cada nó inteiro (que não seja folha) possui uma interligação com no inteiro (que não seja folha) possui uma interligação com no máximo oito filhos, máximo oito filhos, esta interligação se faz normalmente por esta interligação se faz normalmente por meio de ponteirosmeio de ponteiros. Cada nó da octree representa um cubo. A . Cada nó da octree representa um cubo. A representação se dá pela subdivisão recursiva do espaço representação se dá pela subdivisão recursiva do espaço cúbico em octantes (ou voxels), com cada voxel de dimensão cúbico em octantes (ou voxels), com cada voxel de dimensão , sendo subdividido em oito voxels com dimensões. , sendo subdividido em oito voxels com dimensões.

111 222 ddd

Referências BibliográficasReferências Bibliográficas[Rogers85] - Rogers, D.F., “Procedural Elements For Computer Graphics”, [Rogers85] - Rogers, D.F., “Procedural Elements For Computer Graphics”, McGRAWHILL,McGRAWHILL,1985.1985.[Roth82] - Roth, S. D., “Ray Casting for Modeling Solids”, [Roth82] - Roth, S. D., “Ray Casting for Modeling Solids”, Computer Computer Graphics andGraphics andImage Processing, 18, 109-144 (1982).Image Processing, 18, 109-144 (1982).[Kay79] - Kay, Douglas S., “Transparency, Refraction and Ray Tracing for [Kay79] - Kay, Douglas S., “Transparency, Refraction and Ray Tracing for ComputerComputerSynthesized Images”, Synthesized Images”, Master Thesis, Program of Computer Graphics, Master Thesis, Program of Computer Graphics, CornellCornellUniversity, Jan 1979.University, Jan 1979.