Aproximação de Terrenos
Uma rápida abordagem ao algorítmo
Greedy Insert
Fast Polygonal Approximation of
Terains and Height Fields
Garland – Heckbert
1995
Marcelo Barreiros Furtado
LCG/COS/COPPE/UFRJ
29/08/2003
Terminologia


Campos de Elevação (height fields):
Conjunto de amostras de elevação sobre um domínio
plano.
DEMs (USGS); DTMs, GTDR (NASA); TINs.
Introdução


Objetivo:
Gerar modelos simplificados e precisos do campo de
elevação original utilizando o menor número de triângulos
possível da forma mais rápida possível.
Por quê?
Introdução (cont.)



Renderização direta do modelo original (DEM, DTM,
GTDR, etc.) é muito lenta;
Detalhes se perdem quando vistos à distância (acuidade
visual);
Economia de memória, espaço em disco ou tráfego de
rede.
Definição do Problema


Assumimos que H, um conjunto discreto bidimensional de
amostras de alguma superfície subjacente, é fornecido.
H(x, y) = z significa que o ponto (x, y, z) pertence à
superfície real.

A superfície será reconstruída a partir da triangulação dos
pontos de H.
Definição do Problema (cont.)


Seja  o operador de reconstrução que mapeia uma
função definida sobre um conjunto disperso de pontos em
um domínio contínuo (uma função como H) a uma função
definida a cada ponto no domínio.
O mapeamento é feito a partir de uma triangulação do
conjunto disperso de pontos, que será usada para dar
valor aos demais pontos.
Definição do Problema (cont.)

Se S é algum subconjunto de H, então S é a superfície
reconstruída.

(S )(x, y) é o valor da superfície reconstruída para o
ponto (x, y).

O problema, então, é encontrar o suconjunto S que
melhor aproxima H usando o menor número de pontos
possível o mais rápidamente possível.
Métodos de Simplificação

Grid uniforme;

Subdivisão hierárquica;

Levantamento de características;

Decimações incrementais;

Refinamentos incrementais; etc.
Método Empregado
Refinamentos incrementais


Começa-se com uma aproximação inicial e iterativamente
adiciona-se novos pontos como vértices na triangulação.
O processo continua até que algum objetivo pré-estabelecido
seja alcançado.
Análise de Erro

Erro local: |H(x, y) - (S )(x, y)|

Curvatura …

Erro global …

Produto, etc.
Greedy Insertion
Babylon English-Portuguese:

greedy
adj. voraz; guloso; insaciável; ávido; mesquinho

insertion
s. inserção; acréscimo
Greedy Insertion (cont.)

Algorítmo I:
Força Bruta

Algorítmo II:
Otimização do Recálculo

Algorítmo III:
Otimização da Seleção

Algorítmo IV:
Triangulação dependente dos dados
Algorítmo I



Os pontos são inseridos em uma Triangulação de
Delaunay;
Aproximação inicial usando-se os pontos limítrofes de H.
Repetidamente procurar por pontos não utilizados para
encontrar o que apresenta maior erro e inserí-lo à
aproximação corrente até que alguma condição arbitrada
seja alcançada (e.g. n° de triângulos, limite de erro).
Algorítmo I (cont.)



Mesh_Insert(Point p):
Insere p em uma Triangulação de Delaunay.
Mesh_Locate(Point p):
Acha qual triângulo na malha contem
o ponto p.
Locate_and_Interpolate(Point p):
Acha o triângulo que contem p e retorna a elevação
interpolada.
Algorítmo I (cont.)




Mesh_Initialize():
Inicializa a malha com os pontos limítrofes de H
Goal_Met():
Condição de parada (e.g n° de pontos)
Insert(Point p):
marcar p como usado
Mesh_Insert(p)
Error(Point p):
retornar |H (p) – Locate_and_Interpolate(p)|
Algorítmo I (cont.)

Greedy_Insert():
Mesh_Initialize()
enquanto Goal_Met() = Falso {
best  nil
maxerr  0
para todo ponto de entrada p {
err  Error(p)
se err > maxerr então{
maxerr  err
best  p
}
}
Insert(best)
}
Algorítmo I (cont.)

Análise de Custo:
Seja L o custo para se localizar um ponto na
triangulação de Delaunay; I o custo para se inserir um
vértice na triangulação; e i o número do passo.
A cada passo, classifica-se o custo em três
categorias:
 Seleção:
encontrar o ponto de maior erro
 Inserção:
inserir o vértice na triangulação
 Recálculo:
recalcular os erros nos pontos do grid
Algorítmo I (cont.)


Temos então que de forma geral:
 Seleção
=
O(n)
 Inserção
=
I
 Recálculo
=
O(nL)
Pior Caso:
…  L= I= O( i ); Logo:
 Seleção
=
O(n);
 Inserção
=
O( i );
 Recálculo
=
O( i n);
m

Então, no pior caso:
O(in)  O(m n)
2
i 1
Algorítmo I (cont.)

Caso Esperado:
…  L = O(1); e I = O( i )
Logo:
 Seleção
 Inserção
 Recálculo
=
=
=
O(n);
O( i )
O(n);
m

Então no caso esperado:
O(n)  O(m n)
i 1
Algorítmo II



Explora a localidade das mudanças na triangulação de
Delaunay para efetuar mais rapidamente o recálculo do
erro.
Após a inserção de um ponto na triangulação, o ponto
inserido terá arestas partindo dele até um polígono
limitante. Este polígono é exatamente a área onde a
triangulação se alterou, ou seja, a área onde a
aproximação foi modificada.
A idéia é recomputar o erro somente para os pontos
dentro desta região.
Algorítmo II (cont.)

Cache [0 .. n-1]:
Array de n posições que guardará o erro computado
em cada ponto de entrada.

Insert(Point p)
macar p como usado
Mesh_Insert(p)
para todo triângulo t incidente em p
para todo ponto q dentro de t
Cache[q]  Error(q)
Algorítmo II (cont.)

Greedy_Insert():
Mesh_Initialize()
para todo ponto de entrada p
Cache[p]  Error(p)
enquanto Goal_Met() = Falso {
best  nil
maxerr  0
para todo ponto de entrada p {
…
}
}
Insert(best)
Algorítmo II (cont.)
…
…
para todo ponto de entrada p {
err  Cache[p]
se err > maxerr então{
maxerr  err
best  p
}
}
Algorítmo II (cont.)


Análise de Custo:
Seja A a área de recálculo no passo I, então, o custo
no recálculo é O(AL) para localizar o ponto e O(A) para a
interpolação, ou seja, Recálculo = O(AL).
Pior Caso:
A área de recálculo se reduz somente por uma
constante a cada passo, então: A = O(n – i).
Logo o custo do recálculo permanece o mesmo do
algorítmo original, O(nL), e a complexidade de pior caso
permanece inalterada em O(m2n)
Algorítmo II (cont.)


Caso Esperado:
…  A = O(n/i);
Como antes, o custo esperado para a localização e
inserção são: L= O(1) e I= O( i )
Logo:
 Seleção
=
O(n);
 Inserção
=
O( i )
 Recálculo
=
O(n/i);

Então, o caso esperado também continua
inalterado: m
O(n)  O(m n)
i 1
Algorítmo II (cont.)

Qual a diferença então?
Se considerarmos somente a complexidade assintótica,
nenhuma. Mas isto não é o que ocorre na prática, por estes
dois motivos:
1.
O pior caso é ainda mais improvável para o algorítmo II do
que era para o algorítmo I;
2.
O valor da complexidade assintótica pode esconder
constantes significativas. No algorítmo I, tanto o recálculo
como a seleção tem custo esperado de O(n). No algorítmo
II, somente a seleção tem custo O(n); o recálculo caiu para
O(n/i). O fator constante para o recálculo é muito maior
que o da seleção, logo o recálculo é dominante para o
algorítmo II na prática, o que resultaria num custo de:
m
O(n / i)  O(n logm)
i 1
Algorítmo III



Optimiza tanto a seleção do ponto de maior erro quanto o
recálculo dos erros.
A seleção é agilizada utilizando-se um Heap.
Para isto define-se o ponto candidato de um triângulo
como sendo o ponto do grid com o maior erro na
aproximação atual.
Algorítmo III (cont.)



Cada triângulo pode ter no máximo um ponto candidato.
A maioria dos triângulos tem um candidato, mas se o erro
máximo dentro do triângulo for desprezível, ou se não
houverem pontos dentro do triângulo, então o triângulo
não possui nenhum candidato.
Os candidatos são, então, mantidos no heap indexado por
seus respectivos erros.
A cada passo retira-se o candidato com maior erro do
topo do heap.
Algorítmo III (cont.)


Até agora, a função Error() tem feito:

uma busca para achar o triângulo que contém o
ponto;
 uma interpolação com base neste triângulo.
A interpolação é feita computando-se o plano definido
pelos três vértices do triângulo, e, aplicando-se então a
equação deste plano ao ponto especificado.
Algorítmo III (cont.)
O recálculo pode ser, então, agilizado de duas formas:

1.
2.
Elilminar a busca do triângulo, armazenando-se em
cada candidato um ponteiro para o triângulo que o
contém.
Precomputar as equações dos planos armazenandoas junto com os triângulos.
Algorítmo III (cont.)

Estruturas de dados empregadas:
 Campos de Elevação
 Array de pontos, cada qual contendo uma elevação
H(x, y) e um bit usado/não usado.
 Triangulações
 Quad-Edge modificada
 Faces guardam informação sobre os candidatos e o erro
calculado no triângulo.
 Planos
 Heap
 Erro do candidato e um ponteiro ao triângulo (face) a
qual o candidato pertence.
Algorítmo III (cont.)

HeapNode Heap_Change
(HeapNode h, float key, Triangle T):
se h != nil então
se key > 0 então
Heap_Update(h, key)
senão{
Heap_Delete(h)
retornar nil
}
senão
se key > 0 então
retornar Heap_Insert(key, T)
retornar h
Algorítmo III (cont.)

Scan_Triangle(Triangle T ):
plane  Find_Triangle_Plane(T )
best  nil
maxerr  0
para todo ponto p dentro de T {
err  |H(p) – Interpolate_to_Plane(p, plane)|
se err > maxerr então {
maxerr  err
best  p
}
}
T.heapptr  HeapChange(T.heapptr, maxerr, T )
T.candpos best
Algorítmo III (cont.)


Mesh_Insert (Point p, Triangle T ):
Insere p dentro de T e atualiza a triangulação de
Delaunay
Insert(Point p, Triangle T ):
marcar p como usado
Mesh_Insert(p, T )
para todo triangulo U adjacente a p
Scan_Triangle(U )
Algorítmo III (cont.)

Greedy_Insert():
Mesh_Initialize()
para todo triangulo inicial T
Scan_Triangle(T )
enquanto Goal_Met() = Falso {
T  Heap_Delete_Max()
Insert(T.candpos, T)
}
Algorítmo III (cont.)

Análise de Custo:
Assintóticamente, a melhoria mais significativa em
relação ao algorítmo II é uma seleção mais rápida. Na
prática, a otimização da interpolação é igualmente
importante.
Nesse novo algorítmo o custo para seleção é dividio
em três partes:
1.
2.
3.
Inserção no heap;
Remoção do heap; e
Atualização do heap.
Algorítmo III (cont.)
… Custo total do heap, por passo, e consequentemente o
custo da seleção, é O(log i).
Inserção e recálculo são mais “baratos” agora, uma vez
que não dependem mais de L. O custo do recálculo caiu de
O(AL) para O(A).

Pior Caso:
No pior caso, o custo de inserção é I = O( i ), e a área de
recálculo é A = O(n). Logo:
 Seleção
=
O(log i);
 Inserção
=
O( i );
 Recálculo
=
O( n);
m

Então, no pior caso:
O(n)  O(m n)
i 1
Algorítmo III (cont.)


Caso Esperado:
No caso esperado, o custo da inserção é I=O(1) e a
área de recálculo é A=O(n/i).
Logo:
 Seleção
=
O(log i);
 Inserção
=
O(1);
 Recálculo
=
O(n/i);

Então, o custo do caso esperado é:
m
O(logi  n / i)  O((m  n) logm)
i 1
O Problema do Penhasco



O algorítmo Greedy Insert não
funciona bem quando o campo
de elevação contém uma
descontinuidade abrupta ou
“Penhasco” (cliff).
Este problema é causado pelo
fato do algorítmo ser
extremamente local em
relação aos pontos
aproximados.
Uma solução seria encontrar
todos penhascos e forçar a
triangulação a passar por eles.
Crater Lake
Original x Aproximação: 0.5%
Original x Aproximação: 1%
Original x Aproximação: 5%