Upload
mendel
View
24
Download
0
Embed Size (px)
DESCRIPTION
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. - PowerPoint PPT Presentation
Citation preview
Aproximação de Terrenos
Uma rápida abordagem ao algorítmo
Greedy Insert
Fast Polygonal Approximation of Terains and Height Fields
Garland – Heckbert1995
Marcelo Barreiros FurtadoLCG/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 EmpregadoRefinamentos 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.
Greedy InsertionBabylon 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(Poiint 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 usadoMesh_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 nilmaxerr 0para todo ponto de entrada p {
err Error(p)se err > maxerr então{
maxerr errbest 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);
Então, no pior caso: )()( 2
1
nmOinOm
i
Algorítmo I (cont.) Caso Esperado:
… L = O(1); e I =
Logo: Seleção = O(n); Inserção = Recálculo = O(n);
Então no caso esperado: )()(1
mnOnOm
i
)( iO
)( iO
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 usadoMesh_Insert(p)para todo triângulo t incidente em p
para todo ponto q dentro de tCache[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 nilmaxerr 0para 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 errbest 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
)( 2nmO
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= Logo:
Seleção = O(n); Inserção = Recálculo = O(n/i);
Então, o caso esperado também continua inalterado:
)( iO
)( iO
)()(1
mnOnOm
i
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:
)log()/(1
mnOinOm
i
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. Elilminar a busca do triângulo, armazenando-se em cada candidato um ponteiro para o triângulo que o contém.
2. Precomputar as equações dos planos armazenando-as 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ãose key > 0 então
Heap_Update(h, key)senão{
Heap_Delete(h)retornar nil
}senão
se key > 0 entãoretornar Heap_Insert(key, T)
retornar h
Algorítmo III (cont.) Scan_Triangle(Triangle T ):
plane Find_Triangle_Plane(T )best nilmaxerr 0para todo ponto p dentro de T {
err |H(p) – Interpolate_to_Plane(p, plane)|
se err > maxerr então {maxerr errbest 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 usadoMesh_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. Inserção no heap;2. Remoção do heap; e3. 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);
Então, no pior caso: )()(1
mnOnOm
i
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 é:
)log)(()/(log1
mnmOiniOm
i
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.