Traçado de Raios de Cenas
Dinâmicas na GPU
Autor: Paulo Ivson Netto Santos
Orientador: Waldemar Celes Filho
23 de Março de 2009
[email protected]
Sumário








Motivação
Estado da Arte
Contribuições do Trabalho
Construção da Grade Uniforme
Traçado de Raios
Resultados
Conclusão
Trabalhos Futuros
2
Motivação
Por que o traçado de raios?
Por que usar a GPU?
Vantagens

Eficiência



O(log(n)) na complexidade da cena
Descarte de visibilidade e oclusão
Instanciação
Imagens: [Wald et al. 2003]
4
Vantagens

Alta qualidade de imagem



Efeitos de sombreamento
Cálculos fisicamente corretos
Iluminação Global
Imagens: [Wald et al. 2003]
5
Iluminação Global
Imagens: [Wald et al. 2003]
6
Placa Gráfica
GPUs se tornaram eficientes e flexíveis
 Centenas de processadores em paralelo
 Suporta precisão de 32-bits de ponto flutuante
 Oferece muitos GFLOPS
GFLOPS

G80 = GeForce 8800 GTX
G71 = GeForce 7900 GTX
G70 = GeForce 7800 GTX
NV40 = GeForce 6800 Ultra
NV35 = GeForce FX 5950 Ultra
NV30 = GeForce FX 5800

Placas gráficas em cada PC e estação de trabalho
Imagens: Nvidia
7
Desafios




Constantes enormes
 1 raio ~ 1.000 ciclos da CPU
Precisa de muitos raios
 ~1M pixels/quadro
 4x anti-serrilhamento
 25 quadros/seg
 10 raios/pixel
 Um bilhão de raios por segundo…
Sem hardware especializado
 Rasterização tem evoluído há 20 anos!
Sem API unificada
 OpenGL vs OpenRT
8
Estado da Arte
Como obter desempenho interativo
Explorar Paralelismo

Agrupar raios próximos



Instruções SIMD
Raios primários
Utilizar vários processadores


Clusters de PCs
Placas gráficas
10
Reduzir Interseções

Interseção com primitivas


90% do processamento
Estrutura de Aceleração (EA)

Minimizar interseções


Trocar pelo custo de percorrer a estrutura
Reduzir complexidade do algoritmo

O(n) → O(log(n))
11
Cenas Dinâmicas

Movimento de corpo rígido


Animação estruturada



Transformar raio para espaço local do objeto
Pré-construir EAs para cada quadro-chave
Deformar volumes envolventes da EA
Não estruturada

Reconstruir ou adaptar EA a cada quadro
12
Trabalhos Relacionados

CPU




Ray Tracing Animated Scenes using Coherent Grid Traversal
[Wald et al. 2006]
Ray Tracing Deformable Scenes using Dynamic Bounding Volume Hierarchies
[Wald et al. 2007]
Highly Parallel Fast KD-Tree Construction for Interactive Ray Tracing of Dynamic
Scenes
[Shevtsov et al. 2007]
GPU

Real-Time KD-Tree Construction on Graphics Hardware
[Zhou et al. 2008]
13
Contribuições do Trabalho
Solução proposta
Objetivos


Explorar paralelismo da GPU
Cenas dinâmicas




Movimento de corpo rígido
Deformações
Movimento não-estruturado
Estrutura de Aceleração


Grade Uniforme
Reconstruir quando houver movimento
15
Algoritmos na GPU



Construção da Grade Uniforme em paralelo
Percurso e interseção de raios
Cálculo de sombreamento



Texturas
Sombras
Reflexões
16
Resumo da Solução
Cena
Materiais
Coords Tex
Normais
Vértices
Configurar
grade
Inicialização
Visualização
Novo
quadro-chave?
laço
principal
sim
Enviar dados
para GPU
não
Traçar raios
Reconstruir
grade
17
Construção da Grade
Uniforme
Implementação em paralelo
Algoritmo Básico
1.
2.
3.
4.
Encontrar AABB da cena
kN
kN
Nx  dx3
Nz  dz3
Ny  dy3
Determinar no. de células
V
V
Construir listas de triângulos contidos em cada célula
Construir índice ID célula → lista de primitivas
0
ID célula
(1)
2
6
kN
V
11 15
22
Início da lista atual
Início da próx. lista
(2, 6)
Percurso de Raios
ID primitivas
(7, 1, 3, 9)
3
2
7
1
3
9
11 6
2
4
5
7
4
6
8
8
3
7
5
13
12 11 14 21 5
19
Desafios em Paralelo

Como paralelizar a construção das listas?

Por primitiva


Por célula


Conflitos de escrita na mesma célula
Inúmeros acessos a muitos dados
Como construir índice para as listas?

Determinar início e tamanho de cada lista
20
Observação

Difícil


Obter primitivas ocupadas por cada célula
Fácil

Obter células ocupadas por cada primitiva
21
Idéia Fundamental



Escrever pares (ID célula, ID primitiva)
Ordenados por ID primitiva
Reordenar pares de acordo com ID célula
(ID célula, ID primitiva)
4
7
9
7
13
7
14 7
9
12
10 12 4
5
4
8
10 2
14 8
Ordenar por ID célula
4
5
4
7
4
8
9
7
9
12
10 2
7
10 12 13
14 7
14 8
22
Algoritmo
1.
2.
3.
4.
5.
Obter quantas células cada primitiva ocupa
Acumular valores da Etapa 1
Escrever pares (ID célula, ID primitiva) usando
índices da Etapa 2
Ordenar pares da Etapa 3
Dado ID célula, encontrar sua lista dentre
pares ordenados da Etapa 4
23
Etapa 1

Objetivos


Implementação




Obter quantas células cada primitiva ocupa
Fragment shader
Estimativa pela AABB de cada triângulo
Escrever total de células em cada pixel
Exemplo
24
Etapa 2

Objetivos



Implementação




Acumular valores da Etapa 1
Índices para listas de células ocupadas por primitiva
Soma de prefixos em paralelo
CUDA Data-Parallel Primitives (CUDPP)
Acumular um valor adicional no final
Exemplo
25
Etapa 3 – Considerações

Objetivos


Escrever pares (ID célula, ID primitiva)
Usar índices acumulados da Etapa 2
Uma operação de
escrita
Várias operações
de escrita
Uma passada
Fragment shader
CUDA
Geometry shader
Várias
passadas
Vertex shader
-
26
Etapa 3 – Solução Proposta

Dado ID par na saída


Dentre os valores da Etapa 2




Obter ID célula e ID primitiva
Busca binária pelo maior valor Vmáx menor que ID par
ID primitiva = índice de Vmáx na Etapa 2
ID célula = ID célula inicial + (ID par – Vmáx)
Exemplo
27
Etapa 4

Objetivos


Implementação



Ordenar pares da Etapa 3 de acordo com ID célula
CUDA
Radix-sort
Exemplo
28
Etapa 5

Objetivos


Implementação




Construir índices para acessar listas da Etapa 4
Busca binária pelo ID célula nas listas ordenadas
Obter início e tamanho de cada lista
Fragment shader
Exemplo
29
Vantagens

Paralelismo



Banda de memória


Sem conflitos de escrita
Sem múltiplos valores de saída
Poucos acessos a dados
Implementação eficiente na GPU



Soma de prefixos
Ordenação
Busca binária
30
Traçado de Raios
Implementação na GPU
Algoritmo Conceitual
Materiais
Novo
quadro-chave?
sim
Enviar dados
para GPU
Coords Tex
Normais
Vértices
não
Inicializar
percurso de
raios
Cor de
fundo
não
não
Obter próx.
célula nãovazia
Reconstruir
grade
Dados da Grade
Índices da
Grade
Índices da
Grade
sim
Obter
interseção
mais próxima
sim
Vértices
Dados da Grade
Materiais
sombra, reflexão
Sombreamento
Coords Tex
Normais
32
Rotinas Principais

Percurso de raios


Interseção raio x triângulo


3D-DDA [Amanatides and Woo 1987]
Coordenadas baricêntricas [Möller and Trumbore 1997]
Sombreamento



Phong + texturas
Raios de sombra
Raios de reflexão
33
Implementação na GPU

Várias etapas
Raios
primários
interseções
Raios
de
sombra
interseções
em sombra
cor final
Sombreamento
Reflexão: passada adicional com blend
34
Resultados
Análise de desempenho
Roteiro



Construção da Grade Uniforme
Cenas de Teste
Desempenho


Cenas Estáticas
Cenas Dinâmicas



Trabalhos Relacionados
Etapas de Visualização
Configuração de testes


Nvidia GeForce 8800 Ultra
Resolução de 1024 x 1024
36
Construção da Grade Uniforme
Tempo para reconstrução (ms)


De 2x a 3x mais rápido que CPU
Lento para cenas pequenas (API gráfica)
37
Cenas de Teste - CAD
MonoBR
(112K tris)
P40
(470K tris)
Boat
(50K tris)
38
Cenas de Teste - Benchmarks
Hand
(16K tris)
Ben
(78K tris)
Wood-doll
(5K tris)
39
Cenas de Teste - Benchmarks
Toys
(11K tris)
Forest
(174K tris)
Marbles
(9K tris)
40
Cenas Estáticas - CAD
Quadros por segundo (fps)

Resultados P-40



Sombras


Escalabilidade
Descarte por oclusão
Cerca de 50% mais lento
Reflexões

Pior para modelos grandes
41
Cenas Estáticas - Benchmarks
Quadros por segundo (fps)



“Forest” é pior caso para Grade Uniforme
 “Teapot in a stadium”
Sombras
 Até 50% mais lento
Reflexões
 Até 85% mais lento
 “Forest” pior (modelo grande)
42
Cenas Dinâmicas - Benchmarks
Quadros por segundo (fps)

Reconstrução da Grade Uniforme


Custo pequeno (-10%)
Exceto “Forest” (-30%)
43
Trabalhos Relacionados
Quadros por segundo (fps)


Desempenho até 4x mais rápido que BVH e Grade na CPU
“Toys”


Melhor que CPU kd-tree e pior que GPU kd-tree
“Forest”

Pior que ambas pesquisas com kd-tree
44
Etapas de Visualização
Tempo de cada etapa (ms)




Enviar dados para GPU é rápido
Construção da Grade mais rápida que CPU
Kd-tree mais lenta para ser construída
Gargalo: etapa de traçado de raios
45
Demonstração

Vídeos
46
Conclusão
Revisão dos resultados e proposta
inicial
Objetivos Atingidos

Construção da Grade Uniforme na GPU



Implementação em paralelo
Rápida e escalável
Traçado de raios de cenas dinâmicas


Desempenho interativo
Sombras, reflexões
48
Contribuições

Construção da Grade Uniforme na GPU


Mais rápido que pesquisas similares na CPU
Traçado de raios na GPU


Mais rápido que Grade e BVH na CPU
Cenas esparsas


Mais lento que kd-tree na CPU e GPU
Várias melhorias possíveis
49
Trabalhos Futuros
Melhorias e novas pesquisas
Próximos Passos






Grades hierárquicas
Várias Grades (movimento de corpo rígido)
Distância até próxima célula ocupada
Outras estruturas na GPU (BIH, BVH)
Traçar pacotes de raios
Simulação física
51
Bibliografia

AMANATIDES, J.; WOO, A. A fast voxel traversal algorithm for ray tracing. In: IN EUROGRAPHICS
'87, p. 3-10, 1987.

MOLLER, T. A.; TRUMBORE, B. Fast, minimum storage ray-triangle intersection. JGTOOLS: Journal
of Graphics Tools, 2, 1997.

SHEVTSOV, M.; SOUPIKOV, A. ; KAPUSTIN, A. Highly parallel fast kd-tree construction for
interactive ray tracing of dynamic scenes. Comput. Graph. Forum, 26(3):395-404, 2007.

WALD, I.; PURCELL, T. J.; SCHMITTLER, J.; BENTHIN, C. ; SLUSALLEK, P. Realtime Ray Tracing
and its use for Interactive Global Illumination. In: Eurographics State of the Art Reports, 2003.

WALD, I.; IZE, T.; KENSLER, A.; KNOLL, A. ; PARKER, S. G. Ray Tracing Animated Scenes using
Coherent Grid Traversal. ACM Transactions on Graphics, p. 485-493, 2006. (Proceedings of ACM
SIGGRAPH 2006).

WALD, I.; BOULOS, S. ; SHIRLEY, P. Ray Tracing Deformable Scenes using Dynamic Bounding
Volume Hierarchies. ACM Transactions on Graphics, 26(1), 2007.

ZHOU, K.; HOU, Q.; WANG, R. ; GUO, B. Real-time kd-tree construction on graphics hardware. In:
SIGGRAPH ASIA '08: ACM SIGGRAPH ASIA 2008 PAPERS, p. 1-11, New York, NY, USA, 2008. ACM.
52