Upload
internet
View
116
Download
3
Embed Size (px)
Citation preview
Temos site!
www.tecgraf.puc-rio.br/~psantos
Aulas Códigos fonte Exemplos Bibliotecas Material de pesquisa (e.g. papers)
Sumário
Motivação Vdlib Descarte contra o volume de visão Descarte por oclusão Resultados de desempenho
Motivação Eliminar objetos não-visíveis para o observador
Não contribuem para a imagem final Diminuir quantidade de dados transferidos Reduzir processamento no hardware
Vdlib Visibility Determination Library
http://www.tecgraf.puc-rio.br/~psantos/software/vdlib.7z
Volumes envolventes AABB OBB
Construção de hierarquia Kd-tree, média das geometrias
Descarte por visibilidade Volume de visão Oclusão
Descarte contra o volume de visão
Objetivo Identificar objetos fora do frustum de visão Seriam descartados no HW (teste de clipping)
Efetuar teste na CPU Antes de enviar geometria para GPU
Qual teste podemos fazer?
Descarte contra o volume de visão
Frustum Tronco de pirâmide Pode ser definido pela interseção de 6 planos
Near, far, left, right, top, bottom
Convenção: planos orientados para dentro Como testar uma geometria?
Testar seu volume envolvente! Determinar se este se encontra dentro ou fora do
frustum
Descarte contra o volume de visão
Se volume envolvente está totalmente fora Descartar geometria
Senão, continuar testando outros planos
Como obter planos do frustum?
A partir da matriz projection Plano definido no espaço do olho
A partir da matriz view * projection Plano definido no espaço global
Idéia Obter planos a partir do espaço de clipping Cubo → maís fácil de extrair planos
Vide aula de pipeline de geometria Material no site
Seção “Frustum Culling”
Teste AABB x Plano p-vertex
p = (xmin,ymin,zmin)
if (normal.x >= 0)
p.x = xmax;
if (normal.y >=0))
p.y = ymax;
if (normal.z >= 0)
p.z = zmax;
n-vertexn = (xmax,ymax,zmax)
if (normal.x >= 0)
n.x = xmin;
if (normal.y >=0))
n.y = ymin;
if (normal.z >= 0)
n.z = zmin;
Teste AABB x Plano
Se p-vertex está do lado negativo Caixa está totalmente fora
Se n-vertex está do lado positivo Caixa está totalmente dentro
Teste OBB x Plano
Descrever plano no espaço local da caixa n: normal do plano b: base ortonormal da OBB
nb = (bx . n, by . n, bz . n)
Usar nb para determinar n-vertex e p-vertex
Teste OBB x Plano (2) Separating Axis
“Two convex curves will not curve around each other. Thus, if separated there will be a gap into which a plane can be inserted. A separating axis is a line perpendicular to this plane. Objects projected on the axis give non-overlapping intervals if objets do not intersect.”
No caso da OBB x Plano O plano de separação é paralelo ao plano sendo
testado O eixo de separação é paralelo à normal do plano
sendo testado
Teste OBB x Plano (2)int IntersectionBetween( const Plane& plane, const Box& box ){
const float projectedCenter = DistanceBetween( box.center, plane );const float projectedRadius = abs( plane.normal.dot( box.axis[0] ) * box.extents[0] )+
abs( plane.normal.dot( box.axis[1] ) * box.extents[1] ) + abs( plane.normal.dot( box.axis[2] ) * box.extents[2] );
// Totally insideif( projectedCenter >= projectedRadius )
return +1;
// Totally outsideif( projectedCenter <= ( -projectedRadius ) )
return -1;
// Intersectedreturn 0;
}
Otimizações
Evitar testar todos os planos contra todos os volumes envolventes
De um quadro para o outro, câmera não costuma se mover bruscamente
Será que podemos agrupar testes? Idéia: hierarquias!
Coerência temporal
Para cada geometria, guardar índice do último plano a descartá-la
Testar primeiro este plano Boa chance de descartar novamente geometria
Coerência espacial
Dado um conjunto de geometrias Se seu volume envolvente está totalmente fora de
um plano, descartar todas as geometrias Se seu volume envolvente está totalmente dentro
de um dos planos, não testar volumes menores contra este plano Se totalmente dentro do frustum, não é preciso testar
contra nenhum plano
Senão, é necessário testar volumes menores
Coerência espacial
Construir hierarquia de uma cena Testar volume envolvente do nó pai Guardar máscara de quais planos ainda precisam
ser testados Ao visitar nó filho, verificar máscara do nó pai
Se indica que está totalmente dentro do frustum → não testar nenhum plano
Se indica que está totalmente dentro de um plano → não testar este plano
Atualizar máscara para continuar percurso na hierarquia
Outras otimizações possíveis
Octantes Identificar qual octante um volume envolvente se
encontra Testar somente contra 3 planos
Translações e rotações Identificar objetos que permenecerão fora do
frustum Projetar translação da câmera ao longo da normal
do plano Guardar direção de rotação da câmera
Descarte por oclusão
Descarte coerente hierárquico Utilizar placa gráfica para determinar oclusão
Occlusion queries
Explorar coerência temporal Explorar coerência espacial
Mais uma vez Volumes envolventes! Hierarquias!
Occlusion Queries
Extensão do OpenGLint glCreateQuery( num )
void glBeginQuery( id, OCCLUSION_QUERY )
Draw();
void glEndQuery()
void glGetQueryObject( id, GL_NUM_SAMPLES_PASSED, int* )
Retorna número de pixels que seriam gerados Draw() passa pelo pipeline convencional
Occlusion Queries
Paradoxo Precisamos desenhar para saber oclusão Mas queremos saber oclusão para saber se vamos
desenhar
Occlusion Queries
Paradoxo Precisamos desenhar para saber oclusão Mas queremos saber oclusão para saber se vamos
desenhar
Solução Desenhar volume envolvente!
Occlusion Queries
Paradoxo Precisamos desenhar para saber oclusão Mas queremos saber oclusão para saber se vamos
desenhar
Solução Desenhar volume envolvente! Mas e a imagem final?
Occlusion Queries
Paradoxo Precisamos desenhar para saber oclusão Mas queremos saber oclusão para saber se vamos
desenhar
Solução Desenhar volume envolvente! Mas e a imagem final? “Fingir” que vai desenhar!
Desligar escrita no framebuffer: glColorMask( false )
Considerações Se vamos desenhar volumes envolventes
Deve ter baixo custo para desenhar Usar caixas: 8 vértices, 12-14 triângulos Não usar esferas ou volumes mais complexos
Ajuste do volume é importante! Usar AABB ou OBB? Ajuste ruim → falsos positivos
Renderização de frente-para-trás Potenciais oclusores primeiro Fila de prioridade
Occlusion query tem overhead?
Problema crítico Sincronização CPU e GPU
Descarte coerente hierárquico
Algoritmo hierárquico Percurso de frente-para-trás Análogo ao descarte contra volume de visão Caso volume seja descartado
Descartar subárvore do nó correspondente Continuar em um irmão ou ancestral
Desafios Gerenciar envio de occlusion queries Obter somente os resultados já disponíveis Minimizar stalls e starvation
Descarte coerente hierárquico
Coerência temporal Assume movimentos suaves do observador Nós previamente visíveis continuam visíveis
Não esperar resultados de visibilidade Já renderizar assumindo coerência temporal
Adiar classificação de um nó interno Marcar como invisível por default Atualizar de acordo com visibilidade dos filhos Pull-up visibility
Descarte coerente hierárquico
Para cada nó visitado Interno previamente visível
Visitar sub-árvores Marcar como invisível por default
Interno ou Folha previamente invisível Enviar query para volume envolvente Armazenar teste em uma fila Continuar caminhamento em irmão ou ancestral
Folha previamente visível Renderizar geometrias enviando uma occlusion query
Simples!
Enquanto caminha na hierarquia Obter resultados conforme tornam-se disponíveis Se resultado for “visível”
Pull-up visibility Renderizar geometrias (folha) Visitar sub-árvores (nó interno)
Intercalar Visita de um nó da hierarquia Obtenção de resultados já disponíveis
Algoritmo
enquanto não terminou caminhamento ou existem queries pendentes
enquanto existem queries com resultado disponível, ou se caminhamento já acabou
obter resultado da occlusion query do início da fila (mais antiga)
se visivel
pull-up visibility, renderizar geometrias e adicionar filhos à fila de prioridade
se já terminou caminhamento, continue. Senão, obter próximo nó a ser visitado
se nó está totalmente fora do volume de visão, continue
se nó intercepta o plano near
pull-up visibility, renderizar geometrias e adicionar filhos à fila de prioridade
senão se nó era previamente visível
se nó é interno
adicionar filhos à fila de prioridade
senão
renderizar geometrias efetuando uma occlusion query
senão
efetuar occlusion query para volume envolvente
Possíveis melhorias
Caminhamento terminou E ainda existem occlusion queries pendentes CPU Stalls!
Renderizar especulativamente Adiar atualização de visibilidade
Possíveis melhorias Muitas occlusion queries por quadro
Mesmo com hierarquia Depende da cena e divisão espacial
Estimar visibilidade Nós continuam de fato visíveis no quadro atual? Sim!
Propostas Queries somente de tempos em tempos Histórico de visibilidade de cada nó Probabilidade Movimento da câmera Outras
Configuração de Testes
Windows XP Professional Microsoft Visual Studio 2003 .NET
Athlon XP 3800+ (2.4 Ghz) 2 Gb RAM DDR2 800 MHz NVIDIA GeForce 7800 GT 256 Mb (PCI-E)
Testes Volumes envolventes
AABB ~ OBB Clássica Melhor custo x benefício
OBB Aproximada Mínima
tempo área tempo área tempo área tempo áreaAABB 0,00 27,88 0,00 6.306,58 0,15 10.623,51 1,59 10.835,00Covar 0,00 27,48 0,00 3.304,90 0,17 13.117,38 1,78 13.928,76
Hull_Covar 0,02 26,97 0,12 3.657,13 17,92 13.413,87 164,91 15.149,93Hull_Unif_1 0,02 27,65 0,13 5.652,73 17,99 11.927,99 164,78 13.253,46Hull_Unif_2 0,02 27,41 0,12 3.426,37 17,88 13.298,16 166,89 12.786,44Hull_Unif_3 0,02 25,71 0,12 13.897,29 17,85 31.878,56 164,98 36.239,65Min_Aprox 0,02 22,84 0,10 3.069,29 14,68 10.581,23 206,01 10.802,03
Min_Aprox_GA 2,19 22,71 2,70 3.033,52 102,51 10.581,15 1.351,43 10.802,03Min_Aprox_G 7,35 22,70 42,47 3.030,00 6.886,68 10.581,23 - -
Teapots(5000,10)Teapots(1,10) Teapots(5,10) Teapots(500,10)
Testes Occlusion Queries
tTesteDisp: Apenas um teste de disponibilidade Desprezível
tDisp: Tempo para resultado disponível Proporcional à complexidade geométrica
tDispObt: Resultado disponível + obtenção Obter resultado é desprezível
No. Teapots tTesteDisp tDisp tDispObt1 0,00176 0,24 0,245 0,00181 0,29 0,29
10 0,00183 0,36 0,3650 0,00180 0,88 0,88
100 0,00175 1,56 1,56500 0,00176 6,99 6,99
1000 0,00177 13,67 13,62
Occlusion Queries
Tempo para disponibilidade de resultado Linearmente proporcional à complexidade geométrica
Testes
-2
0
2
4
6
8
10
12
14
16
-100 100 300 500 700 900 1100
tTesteDisp
tDisp
tDispObt
Testes Occlusion Queries
tRender: Renderização sem teste de visibilidade tUmaQuery: Apenas um teste de visibilidade
Sem overhead tVariasQueries: Um teste para cada geometria
Quanto mais testes, maior o custo de cada um
No. Teapots tRender tUmaQuery tVariasQueries1 0,003 0,005 0,0055 0,008 0,009 0,011
10 0,013 0,014 0,01950 0,052 0,055 0,085
100 0,103 0,106 0,163500 0,503 0,508 0,808600 0,598 0,610 2,606700 0,698 0,703 5,415800 0,789 0,791 8,270900 0,910 0,898 11,092
1000 0,997 0,995 13,915
Testes
Occlusion Queries
Limiar em torno de 500 queries por quadro
0,0
2,0
4,0
6,0
8,0
10,0
12,0
14,0
-100 100 300 500 700 900 1100
tRender
tUmaQuery
tVariasQueries
Performance de Visualização
Caminho automático percorrido pelo observador Variando número de objetos visíves
Base de comparação Renderização simples, sem otimizações
Avaliar Impacto de diferentes hierarquias Algoritmo de descarte contra volume de visão Algoritmo de descarte por oclusão AABB, OBB Clássica e Aproximada Mínima
Teapots(500,30)
Descarte contra volume de visão: 5% Descarte por oclusão: 40% Aprox. Mín não vale a pena, 100x mais lento
para construir
caixa simples vfc chcAABB 3.134 2.982 1.892OBB Clássica 3.138 2.978 1.919OBB Aprox. Mínima 3.186 2.991 1.869
Teapots(5000,3)
Elevada complexidade geométrica Pouca oclusão “Medir overhead dos testes de visibilidade”
Teapots(5000,3)
Descarte contra volume de visão: 8% Descarte por oclusão: 12%
caixa simples vfc chcAABB 27.491 25.330 24.063OBB Clássica 27.497 25.639 24.656OBB Aprox. Mínima 27.422 25.334 24.021
Teapots(5000,20)
Elevada complexidade geométrica Muita oclusão “Melhor cenário para descarte por oclusão”
Teapots(5000,20)
Descarte contra volume de visão: 6% Descarte por oclusão: 81% (5x fps)
caixa simples vfc chcAABB 27.962 26.176 5.371OBB Clássica 28.206 26.464 5.774OBB Aprox. Mínima 29.341 26.897 5.818
P-38
Elevada complexidade geométrica Muitas geometrias pouco complexas Distribuição irregular no espaço “Caso de uso real”
P-38
Descarte contra volume de visão: 5% Descarte por oclusão: 57%
caixa simples vfc chcAABB 76.119 74.709 33.964OBB Clássica 78.014 74.488 36.546OBB Aprox. Mínima 73.735 69.834 31.130
Conclusões Hierarquia essencial para escalabilidade Descarte contra volume de visão
Otimização fundamental, mas não suficiente
Descarte por oclusão Traz melhorias mesmo com pouca oclusão Dificilmente se torna overhead
Mesmo assim, perda de desempenho é mínima Extremamente eficiente
Ganhos de até 6x na média de quadros por segundo Cerca de 2x no caso real de uso
Bom-ajuste dos volumes não é essencial AABB é suficiente