Otimização de Raytracing
Ian Medeiros
Joner Duarte
Vanessa Leite
Raytracing

O termo raytracing é usado livremente para
designar uma infinidade de diferentes
abordagens ao problema de rendering,
desde que baseados no princípio de
interseção de uma semireta (raio) com
primitivas geométricas.
Raytracing: Complexidade

O algoritmo usado para determinar a
visibilidade ao longo de um raio requer que
cada raio seja interseptado (testado) com
TODAS as primitivas geométricas da cena

O tempo para cada raio é, portanto, linear
com o número de primitivas N:
Tray(N)
Raytracing: Complexidade

No entanto, cada raio não passa próximo da
maioria das primitivas
Raytracing: otimizações iniciais

Melhorias no código:
–
–

Utilização de #define
Mudança de código economizando uma
chamada isInShadow
Utilização de Paralelismo:
–
OpenMP
omp_set_num_threads(omp_get_num_procs());
#pragma omp parallel default(none) private(y,x,
pixel, ray) shared(image, camera, scene,
eye, width, yc, height)
(...)
#pragma omp for schedule(guided)
Raytracing: Estruturas de Aceleração


O objetivo das estruturas de aceleração é diminuir o
número de interseções por raio
Isso pode ser feito utilizando-se dois critérios:
–
–
Permitindo a rejeição rápida e simultânea de grupos de
primitivas
Se possível, ordenando o processo de procura
(intersecções), tal que as primitivas mais próximas da
origem do raio sejam processadas primeiro, evitando
processar as mais distantes se for encontrada uma
interseção.
Raytracing: Estruturas de Aceleração

Duas abordagens:
–
Subdivisão do espaço:

–
Grades regulares, Octrees, Kd-Ttrees – permitem
aplicar os critérios 1 e 2
Subdivisão dos objetos:

Bound Volume Hierarchy (BVH) – permite aplicar o
critério 1.
Raytracing: Grade regular

O espaço 3D é subdividido montando-se
uma grade regular que o subdivide em
espaços com mesma dimensão
Raytracing: Grade regular

Vantagens:
–

Construção muito rápida
Desvantagens:
–
Travessia pouco eficiente devido à
distribuição das primitivas pelos espaços
má
Raytracing: Octree

O
espaço
é
hierarquicamente
e
adaptativamente subdividido em 8 espaços

Compromisso entre construção e travessia
Raytracing: KD-Tree




O espaço é subdividido em dois por um plano
Cada um dos subespaços resultantes é depois
subdividido da mesma forma até atingir um critério
de parada
Travessia mais eficiente se um bom critério de
subdivisão for utilizado (ex: SAH)
Quanto mais sofisticado o critério de subdivisão
maior é o tempo necessário para a construção da
árvore.
Raytracing: KD-Tree (SAH)
 SAH (Surface Area Heuristic) é uma
heurística que leva em consideração a
probabilidade de um determinado objeto ser
interceptado ou não por um raio.
CustoDivisao = CustoTravessia + P[pedaçoEsquerda |Cena]
C(pedaçoEsquerda) + P[pedaçoDireita| Cena]
C(pedaçoDireita)
Raytracing: KD-Tree
tmin
X
Z
B
X
Y
C
Y
D
Z
A
A
tmax
B
C
D
Raytracing: Bounding Volume
Hierarchy


Os objetos são agrupados dentro de
bounding volumes.
Cada um desses grupos é depois
subdividido hierarquicamente por outros
volumes
Raytracing: Bounding Volume
Hierarchy



Não ordena o espaço
Construção semelhante à KD-Tree
Travessia ligeiramente inferior à KD-Tree
Raytracing: Complexidade 2

A complexidade do raytracing com a
utilização de estruturas de aceleração é
logaritmica com relação ao número de
estruturas na cena:
T

(log
N
)
ray

O tempo de construção depende do critério
de subdivisão do espaço/agrupamento de
primitivas
Raytracing: Complexidade 2

Critérios sofisticados (como o SAH para KDTree) resultam em travessias muito
eficientes, entretanto exigem um tempo de
construção muito elevado.
Raytracing: Comparação de
Resultados
Nome da
cena/arquivo
Tempo de execução
algoritmo inicial (s)
Tempo de execução
c/ otimizações (s)
5balls
2.453
0.478
Bolas
4.547
0.285
Bunny
974.825
3.601
Cavalo
31.718
0.277
Esfera
0.763
0.074
Esfera_planos
0.964
0.094
Esferas
1.012
0.097
Espelho
0.977
0.166
Manual
0.888
0.082
Pessoa
2.013
0.143
Pool
9.275
0.499
Room
8.625
0.686
Wall
2.147
0.291
Referências




Highly Parallel Fast KD-tree Construction for Interactive Ray
Tracing of Dynamic Scenes - EUROGRAPHICS 2007 / D.
Cohen-Or and P. Slavík
Interactive k-D Tree GPU Raytracing (Daniel Reiter Horn,
Jeremy Sugerman, Mike Houston, Pat Hanrahan – Stanford
University)
Construção eficiente de kd-trees para primitivas triangulares
(Alessandro Ribeiro da Silva, Wallace Santos Lages - UFMG)
Ray Tracing Interactivo: Estrutura de Aceleração - Ademar
Gonçalves - Universidade do Minho, Braga, 2009