Simplificação de superfícies
Margareth Catoia Varela
O Problema

Seja uma superfície com n vértices

Encontrar uma boa aproximação usando m
vértices.

Encontrar uma aproximação compacta com erro
menor que um valor estipulado (ε).
Quem faz simplificação?

Cartografia, Sistemas de informação geográfica

Simuladores

Computação Gráfica

Visualização científica

Visão computacional

Geometria computacional

CAD

Teoria da aproximação
Características do Problema
Que problema resolver?

Topologia da saída

Topologia e geometria da entrada

Outros atributos

Domínio da saída

Topologia da triangulação

Elementos de aproximação

Métrica de erro

Restrições
Simplificação

Métodos incrementais baseados em atualizações locais



Decimação de malhas
Otimização da função de energia
Métrica do erro usando quádricas
[Schroeder et al. ‘92,... e outros]
[Hoppe et al. ‘93, Hoppe ‘96, Hoppe ‘97]

Junção de faces coplanares (merging)

Re-tiling

Clustering

Baseados em wavelets
[Garland et al. ‘97]
[Hinker et al. ’93, Kalvin et al. ’96]
[Turk’92]
[Rossignac et al. ’93,... e outros]
[Eck et al. ‘95]
Métodos incrementais baseados em
atualizações locais

Simplificação procede como uma seqüência de
atualizações locais

Cada atualização reduz o tamanho da malha e
diminui a precisão da aproximação
...Métodos incrementais baseados em
atualizações locais...

Operações de atualização local:

Remoção de vértices

Contração de arestas

Contração de triângulo
...Métodos incrementais baseados em
atualizações locais...

Pseudo-código comum:
Faça



Seleciona elemento a ser removido / contraído
Executa operação
Atualiza malha
Até que: precisão/tamanho da malha esteja satisfatório
Otimização da função de energia
Mesh Optimization

[Hoppe et al. ’93]
Simplificação baseada na execução iterativa de:



Contração de aresta (collapse)
Partição de aresta (split)
Troca de aresta (swap)
Otimização da função de energia:

Mesh Optimization
Qualidade da aproximação avaliada com uma
função de energia:
E(M) = Edist(M) + Erep(M) + Espring(M)
Edist: soma das distâncias dos pontos originais a M
Erep: fator proporcional ao número de vértices em M
Espring: soma dos comprimentos das arestas
Otimização da função de energia:

Mesh Optimization
Estrutura do algoritmo

Ciclo de minimização exterior



Seleciona uma ação legal (collapse/split/swap) que reduza a
função de energia
Executa a ação e atualiza a malha (Mi  Mi+1)
Ciclo de minimização interior

Otimiza a posição dos vértices de Mi+1 com respeito a malha
inicial M0
Para reduzir a complexidade:


Seleção da ação lega é feita randomicamente
Número fixo de iterações para minimização interna
Otimização da função de energia:
Mesh Optimization
Otimização da função de energia:

Mesh Optimization
Avaliação






Alta qualidade dos resultados
Preserva topologia, re-amostra os vértices
Tempo de processamento alto
Não é fácil de implementar
Não é fácil de usar
Adota avaliação de erro global, mas aproximação
não-limitada
Otimização da função de energia:
Progressive Meshes
Progressive Meshes
[Hoppe ’96]

Ação executada: apenas Collapse

Armazenamento da sequência de transformações
inversas




Multiresolução
Transmissão progressiva
Refinamento seletivo
Geomorph
Otimização da função de energia:
Progressive Meshes

Preserva aparência da malha (2 novos componentes
na função de energia: Escalar, Edisc)

Exemplo:
Otimização da função de energia:

Progressive Meshes
Avaliação








Alta qualidade dos resultados
Preserva topologia, re-amostra os vértices
Não é fácil de implementar
Não é fácil de usar
Adota avaliação de erro global, mas aproximação
não-limitada
Preserva atributos vetoriais/escalares e
descontinuidades
Suporta saída em multiresolução, morphing
geométrico, transmissão progressiva, refinamento
seletivo
Mais rápido do que MeshOptm.
Decimação
Mesh Decimation
[Schoroeder et al ‘92]

Baseado na remoção controlada de vértices

Classificação dos vértices (removível ou
não) baseada na topologia/geometria local e
precisão requerida
Faça



Escolhe um vértice removível vi
Remove vi e suas faces incidentes
Triangula o “buraco”
Até que: não exista vértice removível ou taxa
de redução alcançada
...Decimação...

Fases do Algoritmo

Classificação topológica dos vértices

Avaliação do critério de decimação
(avaliação do erro)

Re-triangulação do pedaço de
triângulos removidos
...Decimação...



Adota avaliação local da aproximação!
max determinado pelo usuário
Exemplo:
...Decimação...

Avaliação:

Eficiente (velocidade e taxa de redução)

Implementação e uso simples

Boa aproximação

Trabalha sobre malhas enormes

Preserva topologia

Erro não limitado
Mesh Decimation: Trabalhos complementares

Precisão da aproximação melhorada, garantia de
erro limitado



Erro limitado
[Cohen ’96, Gueziec ‘96]
Avaliação global de erro [Soucy’96,Bajaj’96,Klein’96,Ciampalini’97, + ...]
Re-triangulação esperta (edge flipping) [Cohen ’96, Gueziec ‘96]

Multiresolução

Decimação de outras entidades


Arestas
Faces
[Ciampalini ‘97]
[Gueziec ’95-’96, Ronfard’96, Algorri ‘96]

Cores e atributos preservados

Simplificação de topologia
[Hamann ‘94]
[Soucy ’96, Cohen et al. ‘98]
[Lorensen ‘97]
Métrica de erro por quádricas
Simplificação com Métrica de Erro usando quádricas
[Garland et al. ’97]

Baseado em sequência de operações de contração
de aresta

Topologia não preservada
...Métrica de erro por quádricas...

Erro geométrico da aproximação gerenciado pela
distância quádrica ao planos incidentes ao vértice
=> representação matricial

Estrutura do algoritmo


Seleciona um par de vértices válido e insere em uma
estrutura de dados ordenada pelo mínimo custo
Faça



Extrai um par válido de vértices, v1 e v2, da estrutura ordenada e
contrai-os num novo vértice vnovo;
Recalcula o custo para todos os pares que contém v1 e v2 e atualiza
a estrutura ordenada.
Até que: Aproximação/redução seja suficiente ou estrutura
ordenada esteja vazia
...Métrica de erro por quádricas...

Exemplo
...Métrica de erro por quádricas...

Avaliação:

Método incremental; iterativo

Erro é limitado

Permite simplificação de topologia

Resultados com alta qualidade e tempo de processamento
baixo
Algoritmos de simplificação

Métodos não incrementais

Junção de faces coplanares (merging)[Hinker et al. ’93, Kalvin et al. ’96]

Re-tiling

Clustering

Baseados em wavelets
[Turk’92]
[Rossignac et al. ’93,... e outros]
[Eck et al. ‘95]
Junção de faces coplanares
Otimização geométrica
[Hinker ’93]

Construção de conjuntos de “quase”
coplanares

Criação de lista de arestas e remoção de
arestas duplicadas

Remoção de vértices colineares

Triangulação dos polígonos resultantes
... Junção de faces coplanares...

Avaliação:

Heurística simples e eficiente

Avaliação do erro é altamente imprecisa e erro não é
limitado (depende do tamanho relativo da faces unidas)

Vértices são subconjunto dos originais

Preserva descontinuidades geométricas e topologia
...Junção de faces coplanares...
Superfaces

Agrupa as faces da malha em conjunto de superfaces:





[Kalvin, Taylor ‘96]
Iterativamente escolhe uma face fi como a superface corrente Sfj
Encontra, por propagação, todas as faces adjacentes a fi, cujos
vértices estão a uma distância /2 do plano principal até Sfj e
insere-as nesta superface
Para ser unida, cada face tem que ter orientação similar às outras
em Sfj
Alinha a borda da superface
Retriangula cada superface
Junção de faces coplanares: Superfaces

Exemplo:
Junção de faces coplanares: Superfaces

Avaliação:

Heurística um pouco mais complexa

Avaliação do erro mais precisa e erro limitado

Vértices são subconjunto dos originais

Preserva descontinuidades geométricas e topologia
Re-tiling
Re-Tiling
[Turk ‘92]

Distribui um novo conjunto de
vértices sobre a malha
triangular original

Remoção de parte dos
vértices originais

Retriangulação local
Clustering
Vertex Clustering
[Rossignac, Borrel ‘93]
 Detecta e une grupos de vértices próximos
 Todas as faces com 2 ou 3 vértices num grupo são
removidas
 Aproximação depende da resolução do grid
 Não preserva topologia
...Clustering...

Exemplo
...Clustering...

Avaliação:

Alta eficiência

Implementação e uso muito simples

Aproximações de baixa qualidade

Não preserva topologia

Erro é limitado pelo tamanho da célula do grid
Métodos Wavelet
Análise de Multiresolução
[Eck et al. ’95, Lounsbery ‘97]
 Baseado na aproximação por wavelet



Dado uma malha de entrada




Malha base simples
Termos de correção local (coeficientes wavelet)
Particiona
Parametriza
Re-amostra
Caracterísiticas

Erro limitado, compacta representação em multiresolução,
edição da malha em múltiplas escalas
... Métodos Wavelet...

Exemplo
Bibliografia da apresentação

Surface Simplification Algorithms Overview
Leila De Floriani, Enrico Puppo, Roberto Scopigno

Survey of Polygonal Surface Simplification
Algorithms
Paul S. Heckbert, Michael Garland