Traçado de raios em tempo real
Paulo Ivson
20-10-2008
Sumário




Algoritmo convencional
Problemas
Grade Regular
Kd-tree
Algoritmo convencional

Para cada raio da imagem

Para cada objeto na cena



Calcular interseção raio x objeto
Guardar interseção mais próxima
Se houve interseção, calcular iluminação
Problemas

Para cada raio da imagem

Para cada objeto na cena




Calcular interseção raio x objeto
Guardar interseção mais próxima
Se houve interseção, calcular iluminação
Processamento custoso



Divisões de ponto flutuante
Cálculo de raiz quadrada
etc
Problemas

Para cada raio da imagem

Para cada objeto na cena




Calcular interseção raio x objeto
Guardar interseção mais próxima
Se houve interseção, calcular iluminação
Complexidade O(rn)

“Busca” em força bruta pela interseção mais
próxima
Problemas

Para cada raio da imagem

Para cada objeto na cena




Calcular interseção raio x objeto
Guardar interseção mais próxima
Se houve interseção, calcular iluminação
Cerca de 90% do tempo é gasto no cálculo de
interseções

Sem chance de ser tempo real
Solução

Otimizar cálculo de interseções



Pré-calcular divisões
Evitar raiz quadrada
Reduzir complexidade do algoritmo

O(rn) → O(r lg n)
Estrutura de Aceleração

Índice espacial



Encontrar geometria mais próxima ao longo de um
raio
Da forma mais eficiente possível
Objetivo

Trocar custo de interseção pelo custo de percurso
na estrutura
Estuturas mais bem-sucedidas

Grade regular
Kd-tree
BVH*

Queremos





Boa adaptação (teapot in a stadium)
Percurso de raios eficiente
Construção eficiente*
Mas antes, volumes envolventes
AABB (revisão)

Construção O(n)

Para cada vértice



Armazenar mín. e máx. para coordenadas x, y e z
Ajuste nem sempre bom
Mas suficiente para o traçado de raios
Estruturas de aceleração
Grade Regular

Subdivisão espacial



Regular
Não-adaptativa
Células de tamanho uniforme

Largura, altura e profundidade



Não precisam ser iguais entre si
São iguais para todas as células
Aplicações principais


Busca por vizinhos próximos
Traçado de raios
Representação

vec3 boxMin
vec3 boxMax
vec3 cellSize
vec3 numCells
int** data

vec3 invCellSize




Construção
Encontrar AABB da cena
Determinar número de células
1.
2.
kN
Nx  dx
V
3
kN
Nz  dz
V
Para cada geometria
3.


kN
Ny  dy
V
3
Determinar quais células ela ocupa
Complexidade O(n)
3
Determinar células ocupadas

Dado ponto no espaço, qual célula ele ocupa?
1.
Obter AABB da geometria
Determinar cellStart, cellEnd
Calcular interseção exata de cada célula com
a geometria
2.
3.
Percurso de raios



Similar à rasterização
3D-DDA
Amanatides, J., Woo, A. A Fast Voxel Traversal Algorithm for Ray Tracing. In Eurographics ’87.
Eurographics Association, 3–10.
Percurso de raios

Intervalos regulares em cada dimensão
Percurso de raios
Percurso de Raios
Inicialização
1.
•
•
Determinar célula inicial
Calcular limites para percurso do raio
Percurso
2.
•
•
•
•
•
Determinar qual próxima célula a ser visitada
Calcular interseção com triângulos
Se encontrou interseção, retorna
Senão, atualizar limites em cada dimensão
Loop
kd-Tree


Estritamente binária
Um plano de corte por nó



Distribuição irregular de geometrias


Alinhado com um dos eixos coordenados
Posicionado arbitrariamente
Adapta-se melhor do que Octree
Aplicações principais


Busca por vizinhos próximos
Traçado de raios
Construção
1.
2.
Testar critério de parada
Encontrar “melhor” plano de corte


Eixo: alternado, maior extensão da caixa do nó
Posição: mediana espacial, heurística
4.
Classificar geometrias em cada lado do plano
Chamadas recursivas para cada nó filho

Complexidade O(n lg n)
3.

Depende da heurística para encontrar plano de
corte
Como encontrar plano de corte

Eixo


Posição


Alternado, ao longo da maior dimensão
Mediana espacial, mediana das geometrias, média
das geometrias
Término

Mín. primitivas em uma folha, limite no tamanho da
altura
Como encontrar plano de corte

Eixo


Posição


Mediana espacial, mediana das geometrias, média
das geometrias
Término


Alternado, ao longo da maior dimensão
Mín. primitivas em uma folha, limite no tamanho da
altura
Não são recomendadas (usem como plano B)
Como encontrar plano de corte

Melhor algoritmo atualmente


Surface Area Heuristic
Qual plano escolher?



Aquele que for melhor para o traçado de raios
Escreva função de custo e minimize ela
Algoritmo guloso (solução ótima local)
Função de custo

Qual custo de traçar um raio por um nó?

Probabilidade de um raio qualquer atingir o nó


Proporcional à área de superfície do nó
Custo de interseção das primitivas contidas pelo nó

Proporcional à quantidade de primitivas (aproximação)
Cost(node) = c_trav + Prob(hit L) * Cost(L) + Prob(hit R) * Cost(R)
= c_trav + c_intr * ( SA(L) * nPrim(L) + SA(R) * nPrim(R) )
Levando em conta o custo
Levando em conta o custo


Probabilidades de L & R iguais
Não considera custos de L & R
Levando em conta o custo


Custos de L & R iguais
Não considera probabilidades de L & R
Partição otimizando custo


Automaticamente isola complexidade
Produz grandes regiões de espaço vazio
Onde avaliar função de custo



Onde estão os pontos críticos?
Variar áreas → variação linear (contínuo)
Variar nPrim → degrau (discreto)



Mínimo quando número de triângulos muda
Utilizar limites das AABBs ou interseção exata
Para cada dimensão x, y, z


Avaliar custo de plano nos pontos críticos
Guardar plano de menor custo
Critério de parada

Quando terminar subdivisão?


Considerar nó atual uma folha
Vale a pena subdividir?
CostLeaf(node) = c_trav + c_intr * nPrim(node)
If CostLeaf(node) <= Cost(node)
stop recursion
Representação

Node

É folha? + Eixo do plano de corte (0=x, 1=y, 2=z)


Posição do plano de corte


32 bit float
Sempre dois filhos, colocar lado-a-lado na memória


2 bits
Um ponteiro de 32-bits
Conseguimos 8 bytes?
Representação

Node

É folha? + Eixo do plano de corte (0=x, 1=y, 2=z)


Posição do plano de corte


32 bit float
Sempre dois filhos, colocar lado-a-lado na memória


2 bits
Um ponteiro de 32-bits
Conseguimos 8 bytes?

Usar 2 bits menos significativos do ponteiro
kD-Tree Traversal Step
t_split
t_min
split
t_max
kD-Tree Traversal Step
t_max
t_split
split
t_min
kD-Tree Traversal Step
t_max
t_split
t_min
split
Passo do percurso
Dado: ray P & iV (1/V), t_min, t_max, split_location, split_axis
t_at_split = ( split_location - ray->P[split_axis] ) * ray_iV[split_axis]
if t_at_split > t_min
need to test against near child
If t_at_split < t_max
need to test against far child
Percurso de raios
while ( not a leaf )
t_at_split = (split_location - ray->P[split_axis]) * ray_iV[split_axis]
if t_split < t_min
continue with far child
if t_split > t_max
continue with near child
// hit either far child or none
// hit near child only
// hit both children
push (far child, t_split, t_max) onto stack
continue with (near child, t_min, t_split)
Considerações finais


Usar float ao invés de double
Pré-calcular valores




Utilizar early exits
Otimizar raios de sombra



Evitar divisões
Evitar raiz quadrada
Interseção com alguma primitiva?
Não precisam de informação de hit
Muitas outras otimizações



Pacotes de raios (SIMD)
Representações paramétricas
etc