Refinamento e Simplificação de Malhas
( CPS851 - Bloco1 / 2002 )
Disney Douglas de Lima Oliveira
Eduardo Barrére
Índice
Conceitos Básicos envolvidos
Simplificação de Malhas
Método de Simplificação Memoryless
Método de Otimização de Malhas
Comparação entre os métodos
Conclusão
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Disney - Barrére
Conceitos Básicos envolvidos
Modelagem de Objetos numa cena
 Representação na forma de polígonos, mais
especificamente triângulos
Visualização de Objetos numa cena
 Quanto mais próximo da câmera, melhor deve ser a
definição do objeto ( maior quantidade de
triângulos para desenhá-lo ) - Múltiplos Níveis (
Modelagem multiresolução )
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Disney - Barrére
Objetivo da Simplificação de Malhas
 Acelerar a apresentação de Modelos com uma
grande quantidade de pontos
Com isso temos:
 Redução do custo na transformação do modelo
 Redução da banda de memória utilizada pela parte
gráfica
 Maior rapidez na renderização da cena
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Disney - Barrére
Simplificação de Malhas
Simplificar uma malha é basicamente diminuir a
quantidade de pontos (vértices) necessários para
representar o objeto. Pode ser feita de forma
estática ou dinâmica. Principais áreas de aplicação:
 Cartografia ( generalização da informação cartográfica
- rios, estradas, encostas, etc.)
 Visão Computacional ( representação de modelos
adquiridos com milhões de pontos - arqueologia, etc.)
 Computação Gráfica ( simuladores, tempo real,
realidade virtual, etc.)
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Disney - Barrére
Simplificação de Malhas: Algoritmos
Os algoritmos que fazem este processo devem levar em
consideração [Garland-SIGGRAPH’97]:
 Topologia e Geometria do Modelo de Entrada ( conjunto de
pontos, manifold )
 Outros atributos do Modelo de Entrada ( cor, textura, normal
da superfície )
 Domínio dos Vértices do Modelo de Saída ( subconjunto do
modelo de entrada ou não )
 Erros de aproximação ( métrica de erro entre o modelo
original e o simplificado )
 Velocidade / Qualidade do algoritmo
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Disney - Barrére
Simplificação de Malhas: Operações
São possíveis as seguintes operações básicas:
 Agrupamento de vértices
 Remoção de vértices
 Colapso de bordas
 Par de vértices
 outras variações
Observações:
Cada operação reduz a complexidade, influenciando uma
pequena região do modelo
A execução desta operação em todas as regiões do modelo,
leva a grandes reduções
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Disney - Barrére
Simplificação de Malhas:
Agrupamento de Vértices
 Agrupa um conjunto de vértices que se
encontram (geometricamente) próximos
 Alguns triângulos somem, tornando-se
linhas ou pontos
 Pode causar um grande impacto na
topologia do objeto ( dificultada nas
transições)
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Disney - Barrére
Simplificação de Malhas:
Remoção de Vértices
 Remove um vértice e as faces adjacentes
 É necessário termos superfícies (faces) manifold em
relação ao vértice
 Preserva a topologia local
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Disney - Barrére
Simplificação de Malhas:
Colapso de Bordas
 Agrupa dois vértices próximos num único vértice
 Apaga os triângulos degenerados
 A remoção pode ser utilizada para suavizar transições
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Disney - Barrére
Simplificação de Malhas:
Remoção de Vértice x Colapso de Aresta
Remoção de Colapso de
semi-aresta
Vértice
Vizinhança
Novos Vértices
Nova Malha
Transições
Suaves
Colapso de
aresta
1 vértice
2 vértices
não
1 sem posição fixa
Várias
Dificilmente
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Uma
natural
Disney - Barrére
Simplificação de Malhas:
Par de Vértices
 Combina quaisquer 2 vértices
Escolha baseada na geometria, topologia,
atributos, etc.
 Mais flexível do que o Colapso de Aresta
Pode mudar facilmente a topologia
 Maior controle local do que o Agrupamento
de Vértices
Escolha de vértices baseadas não somente na
proximidade dos vértices
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Disney - Barrére
Simplificação de Malhas:
Métricas de Erro
Estão sempre presentes nos componentes geométricos:
 Distância entre vértices
v3
Ocorre durante a mudança da topologia
( Agrupamento de Vértices e Par de Vértices )
v1
v2
 Distância entre um vértice e um plano
Armazena um conjunto de planos com cada Vértice. Ocorre
quando se une os vértices, pois une-se o “conjunto de planos”
a
b
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
c
Disney - Barrére
Simplificação de Malhas:
Métricas de Erro
Distância entre pontos de uma superfície
Mede a distância de um conjunto de pontos em relação à uma
superfície
Distância entre superfícies
Limita a máxima distância entre a superfície original e a superfície
simplificada
Erros também podem ocorrer nos atributos ( Cor dos pixels,
Vetor Normal, textura… )
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Disney - Barrére
Simplificação de Malhas:
Eficiência dos Métodos
Para medir a eficiência de cada algoritmo,
pode ser utilizada uma ferramenta chamada
Metro (http://vcg.iei.pi.cnr.it/metro.html), que
mede a distância entre o modelo original e o
modelo gerado.
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Disney - Barrére
Simplificação de Malhas:
METRO
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Disney - Barrére
Simplificação de Malhas:
Metro – Resultados Numéricos
Amostras
Tamanho
Objeto
Vértices
Faces
Área
Original
34,834
69,451
571.28
Reduzido
2,052
4,001
569.35
Erro Máximo
No.
Erro Médio
Volume
Tempo
E+
E-
Em+
Em-
Em
Ev+
Ev-
Ev
seg
1.00
1,170
0.397
0.444
0.070
0.069
0.070
7.14
2.91
10.04
13.5
0.50
104,640
0.609
0.490
0.074
0.065
0.071
7.45
2.76
10.22
82.5
0.10
1,234,402
0.623
0.490
0.073
0.061
0.069
7.27
2.66
9.94
271.5
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Disney - Barrére
Simplificação de Malhas:
Metro – Visualização dos Resultados
Malha
Original
Mapeamento
de erros
por vértices
Malha
Simplificada
Mapeamento
de erros
baseado
na textura
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Disney - Barrére
Método de Simplificação Memoryless
Este método foi apresentado por Lindstrom e Turk
em 1998 e propõe:
Reduzir o número de triângulos em um modelo
utilizando o Colapso de Bordas. Ele difere de
outros métodos por não reter a história da
geometria do modelo original durante a
simplificação.
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Disney - Barrére
Método de Simplificação Memoryless
Algoritmo
 Simplificação baseada no Colapso de Bordas
(uma borda é substituída por um vértice, sendo
removido 1 vértice, 2 triângulos e 3 arestas)
 Novos vértices são inseridos através de
otimização linear, preservando o volume e as
fronteiras
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Disney - Barrére
Método de Simplificação Memoryless
Algoritmo
 Não afeta outros triângulos além dos vizinhos
 Não armazena as informações do modelo
durante a simplificação
utiliza a incrementação dos erros de superfície
utiliza pouca memória
apresenta simplicidade computacional
Estrutura de dados simples
Fácil de implementar
Computa 500 triângulos por segundo
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Disney - Barrére
Método de Simplificação Memoryless
Escolha do Novo Vértice
 O vértice substituto “V” é encontrado através
da interseção de 3 planos não paralelos:
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Disney - Barrére
Método de Simplificação Memoryless
Escolha do Novo Vértice
 Os limites lineares para o vértice V são
introduzidos em ordem de importância:
Preservação do volume (Vi = 0)
Otimização do volume ( menor Vi2 )
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Disney - Barrére
Método de Simplificação Memoryless
Escolha do Novo Vértice
Preservação e Otimização da Área
Otimização da forma do triângulo
só é utilizada quando a malha está degenerada ( as
superfícies são planares e linearmente limítrofes)
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Disney - Barrére
Método de Simplificação Memoryless
Ordenação do Colapso de Arestas
 O colapso de arestas é ordenado de acordo
com a medida de custo referente a
combinação do volume e da varredura da
área
Vi2+(1-)L2 Ai2
Onde: L é o tamanho da aresta e  pode variar
de 0 a 1, indicando ao fator de “qualidade”
entre o interior da face e seus limites .
 Bordas com baixo custo são eleitas em
cada iteração
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Disney - Barrére
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Disney - Barrére
Comparação de Resultados
Utilizamos o paper escrito por Lindstrom &
Turk no paper “Evaluation of Memoryless
Simplification” [IEEE Transactions – Junho 99]
como fonte de comparação entre os métodos
de simplificação Memoryless e Otimização de
Malhas
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Disney - Barrére
Comparação: Exemplo 1
Original
Mesh
Memoryless
T=96966
T=598
T=596
1h07m27s
01m36s
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Disney - Barrére
Comparação: Exemplo 1
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Disney - Barrére
Comparação: Exemplo 1
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Disney - Barrére
Comparação: Exemplo 2
Original
Mesh
T=69451
V=34834
T=1342
V=701
42m04s
E=2.046
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Memoryless
T=1336
V=686
01m20s
E=2.025
Disney - Barrére
Comparação: Exemplo 3
Original
Mesh
T=16384
V=8448
T=51
V=37
T=49
V=38
08m47s
E=88
17s
E=87
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Memoryless
Disney - Barrére
Conclusão
Simplificação Memoryless
Resultados comparável com os melhores
métodos, é rápido, utiliza pouca memória e gera
bons resultados para modelos grandes
Atualmente já incorpora atributos como cor e
vêm sendo testado em aplicações cartográficas.
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Disney - Barrére
Bibliografia
H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuezle, “Mesh
Optimization”, Proc. SIGGRAPH 93, pp. 19-26, Aug. 1993
P. Cignoni, C. Rochini, and R. Scopigno, “Metro: Measuring Error on
Simplified Surfaces, Computer Graphics Forum, vol. 17, no. 2, pp. 167-174,
June 1998.
P. Lindstrom and G. Turk, “Evaluation of Memoryless Simplification”, IEEE
Transactions on Visualizatioon and Computer Graphics, vol. 5, no. 2, pp.
98-115, Apr. 1999
P. Lindstrom and V. Pascucci, “Terrain Simplification Simplified: A General
Framework for View-Dependent Out-of-Core Visualization”, submit for
”IEEE Transactions on Visualizatioon and Computer Graphics”, May 2002.
Refinamento e Simplificação de Malhas (CPS851 - Bloco1/2002)
Disney - Barrére