QuadLOD: Uma Estrutura para a
Visualização Interativa de Terrenos
Rodrigo Penteado R. de Toledo
Orientador: Marcelo Gattass
Co-orientador: Luiz Velho
PUC-RIO - TecGraf
OBJETIVO
Gerar imagem a partir dos dados de um terreno.
Trocar o ponto de vista em tempo real.
MODELAGEM DIGITAL DE TERRENOS
Modelo
Representação
Reconstrução
MODELO
Função de duas variáveis:
REPRESENTAÇÃO
Amostras de alturas:
Grade regular
Distribuição irregular
RECONSTRUÇÃO
Superfície poligonal de altura:
(malha de triângulos)
Malha regular
Malha irregular
PIPELINE
Coleta de Dados
(Grade regular)
Adaptação
à Geografia
(Amostras esparsas)
Triangulação
(Malha de polígonos)
Representação por
Níveis de detalhe
(Estruturas de multi-resolução)
PIPELINE
Coleta de Dados
(Grade regular)
Adaptação
à Geografia
(Amostras esparsas)
Triangulação
(Malha de polígonos)
Representação por
Níveis de detalhe
(Estruturas de multi-resolução)
PIPELINE
Coleta de Dados
(Grade regular)
Adaptação
à Geografia
(Amostras esparsas)
Triangulação
(Malha de polígonos)
Representação por
Níveis de detalhe
(Estruturas de multi-resolução)
PIPELINE
Coleta de Dados
(Grade regular)
Adaptação
à Geografia
(Amostras esparsas)
Triangulação
(Malha de polígonos)
Representação por
Níveis de detalhe
(Estruturas de multi-resolução)
PIPELINE
Coleta de Dados
(Grade regular)
Adaptação
à Geografia
(Amostras esparsas)
Triangulação
(Malha de polígonos)
Representação por
Níveis de detalhe
(Estruturas de multi-resolução)
?
VISUALIZAÇÃO
Câmera Virtual
RESOLUÇÃO E VISUALIZAÇÃO
Câmera
Perto
Câmera
Longe
VISUALIZAÇÃO DE TERRENO
Terreno visto inclinadamente
COMO SELECIONAR A RESOLUÇÃO?
FUNÇÃO ADAPTATIVA
Critérios (geométricos e/ou perceptuais):
•Distância
• Projeção dos polígonos
• Silhueta
• Centro da imagem
• Velocidade
EXEMPLO DE FUNÇÃO ADAPTATIVA
Função Adaptativa baseada em distância
(usada na implementação)
ESTRUTURAS HIERÁRQUICAS
Classificação:
Não Adaptativas:
Estruturas de Multi-resolução
Estruturas Progressivas
Adaptativas:
Estruturas de Resolução Variável
ESTRUTURAS DE MULTI-RESOLUÇÃO
Construção: refinamento global
Malhas regulares
ESTRUTURAS PROGRESSIVAS
Construção: Simplicamento local
Malhas irregulares
Ordem das operações pré-fixada
Obs: Pode ser armazenado com seqüência de operações
ESTRUTURAS DE RESOLUÇÃO VARIÁVEL
Construção: Operações locais
(refinamento ou simplificação)
Malha Base
Malhas regulares ou irregulares
Ordem das operações não é fixa
Representação: DAG grafo de
dependência (interferência)
Malha Final
ESTRUTURAS HIERÁRQUICAS E
VISUALIZAÇÃO
Permitem visualização interativa
Construção da estrutura em pré-processamento
Extração em tempo real
Estrutura adequada: Resolução Variável
• Malhas Regulares
• Malhas Irregulares
QuadLOD
 Malha irregular com estrutura regular.
Combina vantagens de estruturas regulares e irregulares.
Conceitos:
• Bloco Regular
• Estrutura Regular Subjacente
• Estrutura Regular em Multi-resolução
BLOCO REGULAR
Região retangular de uma malha irregular.
• Interior: malha irregular.
• Fronteira: quatro poligonais retas.
ESTRUTURA REGULAR SUBJACENTE
União da fronteira dos blocos regulares
Estrutura Regular em Multi-resolução
Decomposição hierárquica do domínio
ESTRUTURA QuadLOD
Malha irregular de resolução variável com uma
estrutura regular de multi-resolução
Representação da QuadLOD
Decomposição hierárquica: árvore quaternária.
Cada nó: malha progressiva
Compatibilidade:
• Triangulação dos nós pais e filhos
• Restrição de fronteira
ANÁLISE
Vantagem
Desvantagem
Estrutura Hierárquica irrestrita
Triângulos Finos
CONSTRUÇÃO DA QuadLOD
• Pré-processamento
• Construção da Hierarquia
• Simplificação dos Blocos Regulares
PRÉ-PROCESSAMENTO
Objetivo:
Gerar malha irregular com estrutura regular subjacente.
Pré-processamento depende do dado de entrada.

Mapa de Alturas
Malha estrutura regular
CONSTRUÇÃO DA HIERARQUIA
Objetivo:
Montagem da quadtree (decomposição hierárquica do domínio)
SIMPLIFICAÇÃO DOS
BLOCOS REGULARES
Objetivo:
Obter uma estrutura de multi-resolução.
Construção da malha progressiva (biblioteca MLOD).
ETAPAS DA CONSTRUÇÃO DA
QuadLOD
Triangulação irregular com
Estrutura regular subjacente
2.1
Dado original
do terreno
Mapas de
Altura
Construção da
Hierarquia
Decomposição hierárquica
do domínio
2.2
1.0
Pré-Processamento
Simplificação dos
Blocos Regulares
Estrutura regular subjacente
em Multi-resolução
VISUALIZAÇÃO COM QuadLOD
Interatividade:
•malha compatível com a resolução da tela.
• frame rate constante (15 a 30 frames por segundo)
Algoritmo:
Visualiza()
{
Lê estrutura que represente o terreno
Para sempre
{
Obtém parâmetros de câmera
malha = EXTRAI_MALHA (parâmetros)
Desenha (malha)
}
}
EXTRAÇÃO DA MALHA
EXTRAI_MALHA(parâmetros)
{
Calcula uma função de adaptação
DECIDE_RESOLUÇÃO_MALHA (função de adaptação)
Retorna a malha com a resolução calculada
}
Função adaptativa:
distância projetada e normalizada [0,1].
Vantagens:
• Bons resultados perceptuais.
• Pode-se usar o Z-Buffer.
DECIDE_RESOLUÇÃO_MALHA
Duas etapas:
1. Cálculo da resolução ideal
1.1. Escolha do nível hierárquico (top-down)
1.2. Escolha da resolução do nó
2. Cálculo da resolução a ser desenhada
2.1. Transição
2
3
0
1
0 1 2 3
TRANSIÇÃO
• Evita descontinuidade na troca de resolução.
• Interpola entre última malha desenhada e a ideal.
• Faz uso da malha progressiva.
(interpola posição dos vértices)
TEXTURA
Exemplos:
• Foto de satélite
• Mapa temático
• Imagem pré-iluminada do terreno.
TEXTURA E ILUMINAÇÃO
Imagem pré-iluminada
Aplicação de textura é mais eficiente
que o cálculo de iluminação
A resolução do sombreamento
independe da resolução da malha
Iluminação em tempo real
Resposta imediata a qualquer
alteração na fonte de luz (posição,
intensidade ou cor)
EFEITOS
FOG
(simula atenuação d’água no fundo mar)
TESTES
Experimentos:
Medições:
• 2 terrenos
• frames por segundo
• 3 caminhos
• triângulos desperdiçados
• 3 plataformas
• triângulos em transição
• tamanho dos triângulos
Terrenos
Terreno Submerso:
(60 milhões de amostras 725 mil triângulos)
Terreno Bolívia:
(1,6 milhões de amostras 230 mil triângulos)
CAMINHOS SUBMERSOS
Caminho Submerso1
Caminho Submerso2
RESULTADOS CAMINHO SUBMERSO1
Triângulos desenhados por frame:
25000
d
20000
e
f
15000
c
b
10000
h
g
5000
a
0
1
101
201
301
401
501
601
701
801
Triângulos desperdiçados e bons:
901
1001
1101
RESULTADOS CAMINHO SUBMERSO2
Caminho de ida e volta.
(a) (b) (a)
(a)
(b)
(a)
(triângulos
por frame)
A volta é de marcha ré.
(frame rate)
RESULTADOS CAMINHO BOLÍVIA
Triângulos desenhados por frame:
45000
40000
35000
30000
25000
20000
15000
10000
5000
0
1
101
201
301
401
501
601
701
801
901 1001 1101
Análise de 1 frame
Histograma do tamanho dos triângulos
Frame 632 do caminho Submerso1:
1242
QuadLOD
2327
Sem
Simplif icar
31080
0%
10%
20%
30%
(5944)
2375
3692 (56382)
21610
40%
menor que 1
50%
60%
de 1 a 20
70%
80%
90%
100%
maior que 20
Frame 328 do caminho Bolívia:
804
QuadLOD
Sem
Simplificar
2081
7700
0%
10%
(7183)
4298
20106
20%
30%
40%
menor que 1
50%
60%
de 1 a 20
4323
70%
80%
maior que 20
90%
(32129)
100%
APLICAÇÃO
VÍDEO
CONCLUSÃO
QuadLOD: nova estrutura para representação digital de terrenos
Vantagens:
•Permite a visualização interativa de terrenos complexos
•Combina características de malhas regulares e
irregulares
ANÁLISE
Estrutura regular facilita a construção e uso da
representação
Função adaptativa baseada em distância teve bons
resultados
Grande proporção de triângulos desperdiçados.
O uso do Z-Buffer para a visualização permite
visualização de outros objetos.
TRABALHOS FUTUROS
Acesso à memória secundária.
Aperfeiçoar cálculo da resolução transitória.
Função adaptativa mais sofisticada.
Triângulos com melhor razão de aspecto
Explorar o uso de textura em multi-resolução.
Estender a QuadLOD para malhas genéricas.
Investigar outras aplicações para a QuadLOD.