Visibility Culling

Visibility Culling
Conservative Visibility Preprocessing using
Extended Projections
Durand et al
João Carlos Freitas - LCG - Junho 2001
Roteiro
•
•
•
•
•
•
•
•
Motivação
Técnicas Existentes
Visão Geral
Extended Projections
Algoritmo - Pré-processamento e Visualização
Resultados
Conclusões
Bibliografia
Motivações
• Aplicações atuais utilizam número muito grande
de polígonos
• Excesso de polígonos renderizados inviabiliza
visualização de cenas complexas em tempo real
• Algoritmos de visibility culling reduzem o número
de polígonos que são renderizados
• Os algoritmos tentam evitar que sejam
renderizados polígonos que não são vistos na cena
Técnicas Existentes
• Back-face culling
• View frustum culling
Técnicas Existentes
• Occlusion Culling
– Identifica as partes visíveis da cena
• cell-based: Portais e BSP
• point-based: tempo real
• preprocess: pré-processamento
Visão Geral
• Cell: espaço é dividido em células, que contêm os
objetos
• Viewing cell: região de movimento do observador
• PVS - Potentially Visible Set: grupo de objetos
que podem ser vistos de um ponto de visão dentro
da viewing cell. Quanto menor, melhor.
• Extended Projection: operador usado para
determinar o PVS de uma célula.
Visão Geral
• Pré processamento:
– Definir viewing cells de uma cena
– Calcular o PVS de cada célula
• Visualização Interativa:
– Renderizar objetos do PVS da viewing cell
correspondente
– Atualizar viewing cell à medida que observador
se movimenta
Extended Projections
• Projeções em planos a partir de viewpoints
• Objetos são divididos em duas categorias: ocultadores
(occluders) e ocultados (occludees)
• Para um objeto estar oculto para todos os viewpoints
de uma viewing cell:
– sua projeção estendida deve estar contida na
projeção estendida de um occluder (Overlap Test)
– deve estar atrás do occluder (Depth Test)
Extended Projections
• Projection de um occluder: interseção das projeções
• Projection de um occludee: união das projeções
Extended Projections
• Projection de um occluder
Extended Projections
• Projection de um occludee
Extended Projections
• Depth Test
– se a projeção de um occludee indica que o objeto pode
estar invisível, é feito um DepthTest
– para cada plano de projeção, é gerado um Depth Map.
Cada pixel tem um valor de Depth associado do occluder
– O valor do Depth Map é comparado ao do occludee. Se o
Depth do occludee for menor, o objeto está visível
– Foi usado também um Hierarchical Depth Map, para
agilizar as comparações
Extended Projections
• Reprojection permite Occlusion Sweep com
atualização do Occlusion Map
Extended Projections
• Occlusion Fusion
Algoritmo - Pré Processamento
• Criação das viewing cells, organizadas numa
estrutura hierárquica espacial
• Para cada viewing cell, devem ser escolhidos os
occluders e os planos de projeção (6 planos)
• Os occluders devem ser preferencialmente
grandes, próximos da viewing cell e de baixa
complexidade de renderização. Devem estar
dentro do view frustum
• Foi desenvolvido um algoritmo dinâmico que
escolhe mais occluders em regiões onde existem
muitos occludees visíveis
Algoritmo - Pré Processamento
• Cada plano de projeção tem associado um Depth
Map e um Occlusion Map.
• O Occlusion Map contém as Projections de todos
os occluders selecionados.
• Os occludees são testados recursivamente, para a
geração do PVS
• As viewing cells podem ser subdivididas caso o
PVS seja muito grande.
• Foi usado o mecanismo de armazenamento deltaPVS.
Algoritmo - Visualização
• Foi usada uma estrutura em grafo onde cada nó
contém uma flag de visibilidade
• Quando o observador entra num novo nó do grafo,
a flag dos outros nós é atualizada de acordo com
os dados obtidos no pré processamento.
Resultados
• Para uma cena de uma cidade, com um total de 6M de
polígonos:
– 96% de occlusion, 60 MB de PVS, 165 minutos, 0.81
s/célula, 18 vezes mais rápido que frustum culling
Resultados
Conclusões
• O método é eficiente para ambientes estáticos.
Mas ineficiente para occluders dinâmicos.
• O tamanho das cenas após o pré processamento é
bem menor.
• O overhead de primitivas sendo renderizadas
ainda é grande.
• A fase de display não requer computação
intensiva, ao contrário de métodos que fazem
culling em tempo real
• Implementação de LOD
Bibliografia
• Conservative Visibility Preprocessing using
Extended Projections, Durand et al, 2000
• Visibility Culling using Hierarchical Occlusion
Maps, Zhang et al, 1997
• Gamasutra
• Gamedev