Dissertação
Dissertação_Diego_Chicuta.pdf
Documento PDF (7.3MB)
Documento PDF (7.3MB)
UNIVERSIDADE FEDERAL DE ALAGOAS
INSTITUTO DE MATEMÁTICA
PROGRAMA DE PÓS GRADUAÇÃO EM MATEMÁTICA
Diego Chicuta Macedo
Simplificação de Malhas Triangulares Baseada em Templates
Maceió
2015
Diego Chicuta Macedo
Simplificação de Malhas Triangulares Baseada em Templates
Dissertação de Mestrado submetida em Outubro de 2015 à Banca Examinadora, designada
pelo Colegiado do Programa de Pós-Graduação
em Matemática da Universidade Federal de
Alagoas, como parte dos requisitos necessários
à obtenção do grau de Mestre em Matemática.
Orientador: Prof. Dr. Dimas Martínez Morera
Catalogação na fonte
Universidade Federal de Alagoas
Biblioteca Central
Divisão de Tratamento Técnico
Bibliotecário Responsável: Valter dos Santos Andrade
M141s
Macedo, Diego Chicuta.
Simplificação de malhas triangulares baseada em templates / Diego Chicuta
Macedo. - 2015.
61 f. : il.
Orientador: Dimas Martínez Morera.
Coorientador: Thales Miranda de Almeida Vieira.
Dissertação (Mestrado em Matemática) – Universidade Federal de Alagoas.
Instituto de Matemática. Maceió, 2015.
Bibliografia: f. 59-60.
1. Geometria. 2. Simplificação de malhas. 3. Topologia. 4. Distância
geodésica. 5. Principal Components Analysis (PCA). 6. Fast Marching Method
(FMM). I. Título.
CDU: 514.772.2:004.92
Aos meus pais, irmãs, noiva e avós.
Dedico este trabalho aos meus pais que nunca mediram esforços para que seus filhos
evoluíssem em conhecimento e em espírito, minhas irmãs, minha noiva e meus avós que sempre
me deram forças para continuar firme em minha caminhada.
AGRADECIMENTOS
Primeiramente e sobretudo à DEUS pela força, equilíbrio e determinação de todos os dias
durante o desenvolvimento deste trabalho, que só assim consegui ter inspiração e motivação
para continuar.
As minhas primeiras palavras de apreço tem que ir, sem qualquer dúvida, para os meus
pais, irmãs, avós e noiva. Eles são a razão da minha existência, o meu porto seguro, a minha
luz guia, fonte de inspiração e força. Sem eles não seria quem sou, nem estaria aqui hoje no
final desta etapa. A eles devo tudo o que tenho e que venha a ter. Um agradecimento especial
a toda a minha família pelo apoio.
Quero prestar agradecimento ao meu orientador professor Dimas Martínez pela supervisão
prestada durante todas as fases deste trabalho, pelas reuniões de aconselhamento e verificação
do trabalho e como guia na execução do trabalho de forma mais correta, bem como seu imenso
incentivo e credibilidade diante deste trabalho e principalmente por sua grande paciência e
compreensão que foram de fundamentais importância para que esse trabalho tivesse o objetivo
alcançado, meus sinceros agradecimentos. Agradeço também ao professor Thales por suas
sugestões, verificações, conselhos e discussões que engrandeceram bastante este trabalho.
Uma palavra de agradecimento à todos os docentes do programa, em especial ao
professor Adelailson por seu grande companheirismo e amizade em todos os meus momentos
aqui. Agradeço também à todos que fazem a coordenação do programa como Ewerton e Ana
que me ajudaram bastante com esclarecimentos e todo o apoio e acompanhamento de minha
vida acadêmica junto ao departamento. Agradeço aos colegas de minha turma, do IM, do
CPMAT que me ajudaram na execução do trabalho, me deram apoio, idéias e ajuda técnica,
pelos bons e por muitas vezes descontraídos momentos do café, que foram muito importantes
em todos os momentos.
Não posso deixar de agradecer aos meus amigos. Aos do laboratório e da turma em
especial, Tiago, Alexandre, Ícaro, Michel, Fabrício, Ailton, Nayane, Rogério e Robson, que
representam a minha “família da UFAL”. Os amigos que me acompanharam ao longo de todo
esse tempo, tanto os que passaram quanto os que permanecem aqui, de trabalho árduo, de
muitas horas de estudo, de muitos risos e bons momentos e partilha de todas as experiências
vividas no mestrado ao longo destes anos. E aos demais amigos que passaram pela minha vida
acadêmica e pessoal.
Minha gratidão a todos aqueles que estiveram ao meu lado. A ajuda dessas pessoas
sempre foi de fundamental importância.
A todos, muito obrigado.
RESUMO
Algoritmos para simplificação de malhas podem ser aplicados de forma a eliminar vértices
da malha resultante, sem prejudicar a topologia da mesma. Neste trabalho desenvolvemos
um técnica de simplificação de malhas 3D baseada em templates, que reduz a sua quantidade
de vértices. Apresentaremos um método que busca otmizar a complexidade de uma malha a
partir da redução no seu número de vértices e faces, de forma que a geometria e topologia da
superfície sejam preservadas. Isso é garantido com o uso de uma malha base, ou template, que
tem gênero zero, topologia e conectividade desejada. Nosso objetivo é definir a geometria do
template, de modo que aproxime nossa superfície original. Usaremos Análise de Componentes
Principais (PCA) para o alinhamento inicial das duas superfícies. Este alinhamento busca
encaixar as duas malhas de forma que tenhamos um alinhamento de suas direções principais,
o que permite a devida geração de correspondência entre seus vértices. Com o intuito de
melhorar a correspondência entre os vértices de ambas as malhas, adicionamos a informação da
distância geodésica de cada vértice à dos pontos fixos da malha densa, usando o Fast Marching
(FMM). Isso nos permite discriminar vértices distantes na malha, mas próximos na distância
euclidiana. Para a geração da nova malha que é menos densa que a inicial usaremos uma
técnica baseada em projeções que visa trocar a posição de vértices de uma malha densa por
suas respectivas correspondências no template que possui quantidade de vértices menor. Como
resultado destas projeções teremos uma malha resultante muito menos densa que a inicial, que
preserva as características geométricas e topológicas.
Palavras-Chave: Simplificações. Geometria. Topologia. Template. Distância Geodésica.
ABSTRACT
Algorithms for mesh simplification can be applied to remove vertices avoiding changes to
the topology of the object. In this work we have developed a technique for simplification of
3D meshes based on templates. We present a method that tries to optimize the complexity
of a mesh decreasing the number of vertices and faces, so that the geometry and topology
of the surface are preserved. Our goal is to define the geometry of the template so that it
approximates our original surface. We will use the Principal Components Analysis (PCA) to
achieve an initial alignment of the two surfaces. This alignment searches a fit between the two
meshes so that we have an alignment of its main directions, which allows proper generation of
correspondence between its vertices. With the aim of improving the correspondence between
the vertices of both meshes, we added the geodetic distance information of each vertex to the
of fixed points of dense mesh, using Fast Marching (FMM). This allows us to discriminate
vertices distant in the mesh, but next in the distance euclidean. For the generation of the
new mesh that is less dense than the initial we will use a technique based on projections that
aims to change the position of the vertices of a dense mesh by their respective correspondences
in the template that has quantity of vertices less. As a result of these projections we will
have a mesh resulting much less dense than the initial, which preserves the geometrical and
topological properties.
Keywords: Simplifications. Geometry. Topology. Template. Geodesic Distance.
LISTA DE FIGURAS
1.1
Simplificação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 13
1.2
Classificação dos Vértices . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 14
1.3
Mesh Decimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 15
1.4
Movimentos Legais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 17
1.5
Transformação de Collapse . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 18
1.6
Elipsóides de Erro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 18
1.7
Colapso de Aresta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 19
1.8
Junção de Vértices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 19
2.1
Superfície . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 21
2.2
Malha de uma Superfície . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 22
2.3
Bitoro de Gênero 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 23
2.4
Vizinhança Estrelada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 24
2.5
Terceira Vizinhança Estrelada . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 24
3.1
Aplicação do PCA ao Bunny e a Mão . . . . . . . . . . . . . . . . . . . . . .
p. 30
3.2
Alinhamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 31
4.1
Ilustração FMM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 32
4.2
Discretização do FMM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 33
4.3
Processo de Iteração . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 34
4.4
Processo de Propagação . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 35
4.5
FMM na Esfera e no Bunny . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 36
4.6
FMM no Cavalo e no Armadillo . . . . . . . . . . . . . . . . . . . . . . . . .
p. 36
5.1
Primeira Projeção para o Bunny . . . . . . . . . . . . . . . . . . . . . . . . .
p. 39
5.2
Relação das Correspondências entre o Bunny e a Esfera . . . . . . . . . . . .
p. 41
5.3
Terceira Vizinhança para cada Vértice do Template . . . . . . . . . . . . . .
p. 42
5.4
Correção dos Vértices Distantes . . . . . . . . . . . . . . . . . . . . . . . . .
p. 44
5.5
Processo de Subdivisão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 46
6.1
Simplificação do Bunny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 49
6.2
Simplificação de Vênus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 50
6.3
Simplificação de Buste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 51
6.4
Simplificação de Max . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 52
6.5
RMSD Bunny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 55
6.6
RMSD Vênus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 55
6.7
RMSD Buste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 56
6.8
RMSD Max . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 56
6.9
Colorização de Max . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 58
SUMÁRIO
Página
INTRODUÇÃO
p. 13
1.1 Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 13
1.2 Trabalhos Relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 14
1.2.1
Mesh Decimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 14
1.2.2
Re-Tiling Polygonal Surfaces . . . . . . . . . . . . . . . . . . . . . . .
p. 16
1.2.3
Otimização de Energia . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 16
1.2.4
Métrica de Erros por Quádricas . . . . . . . . . . . . . . . . . . . . .
p. 18
1.3 Contribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 19
1.4 Visão Geral do Trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 19
2 FUNDAMENTOS
p. 21
2.1
Superfícies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 21
2.2
Malhas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 22
2.3
Vizinhança Estrelada . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 23
2.4
Transformações Tridimensionais . . . . . . . . . . . . . . . . . . . . . .
p. 24
2.4.1
Translação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 25
2.4.2
Rotação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 25
2.4.3
Escala . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 26
3 ANÁLISE DE COMPONENTES PRINCIPAIS
3.1
p. 27
Componentes Principais . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 27
3.1.1
p. 28
Matriz de Covariância . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2
Análise de Componentes Principais - PCA
3.2.1
. . . . . . . . . . . . . . .
p. 29
Alinhamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 30
4 FAST MARCHING
p. 32
4.1
Fast Marching
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 32
4.2
Fast Marching na Malha . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 36
5 SIMPLIFICAÇÃO DE MALHAS
5.1
Projeção do Template . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6 RESULTADOS
6.1
Análise dos Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 38
p. 38
p. 48
p. 53
7 CONCLUSÕES
p. 59
REFERÊNCIAS
p. 60
13
INTRODUÇÃO
A modelagem de objetos 3D em computação gráfica é usualmente aplicada para o
desenvolvimento de ferramentas cada vez mais eficazes e com baixo custo computacional,
que visam ter uma boa performace de execução. Malhas triangulares são tipicamente a
escolha adotada, dado a eficiência de algoritmos e seu tratamento especial em computadores.
Entretanto, quando estas malhas são muito grandes, algoritmos para reduzir a complexidade e
gerar malhas menos densas são necessários.
Neste trabalho desenvolvemos uma técnica de simplificação de malhas densas baseada
em templates que preservam regiões perceptualmente interessantes da malha, do ponto de vista
geométrico e topológico. Para isto, propomos uma técnica baseada em projeções de vértices
entre uma malha densa, com muitos vértices, e uma malha grosseira ou menos densa, que
chamamos de template, com menos vértices que a anterior. Tais projeções são realizadas a
partir da criação de correspondências entre estas duas malhas, as quais são obtidas a partir da
distância euclidiana entre cada ponto da malha densa ao seu mais próximo no template, depois
de ter alinhado as duas malhas.
Figura 1.1: Simplificação
Fonte: Disponível em [Hoppe]
1.1
Objetivo
Neste trabalho apresentaremos um método capaz de simplificar uma malha a partir de
projeções. Esse método deve manter a topologia e preservar ao máximo a geometria inicial da
superfície. Para isto usaremos um template, que tem a mesma topologia da malha original, mas
conectividade e tamanho desejados. Dessa forma nosso principal objetivo é definir a geometria
do template, de modo que aproxime nossa superfície original.
1.2 Trabalhos Relacionados
1.2
14
Trabalhos Relacionados
A simplificação de malhas tridimensionais possibilita a obtenção de novas representações
de uma superfície através de malhas que se caracterizam por uma quantidade de informação
menor do que a malha inicialmente dada. De um modo geral, os trabalhos relacionados à
simplificação de malhas triangulares que podemos encontrar em nossa literatura, buscam
representar uma malha por uma equivalente que possui um número de vértices e faces menor.
Em nossa literatura a simplificação de uma malha é geralmente utilizada em compressão,
velocidade de processamento bem como para melhorar sua qualidade. Este último caso por
vezes é uma característica subjetiva, uma vez que depende unica e exclusivamente de sua
aplicação. A malha pode ser modificada em termos da sua quantidade de elementos bem como
obter uma resultante que apresente poucos vértices, arestas e faces, mantendo a topologia e
preservando a geometria original. A seguir apresentaremos algumas abordagens do problema de
simplificação de malhas sob seus diferentes aspectos para a obtenção de uma malha resultante.
1.2.1
Mesh Decimation
A decimação de uma malha triangular consiste em eliminar de forma iterativa vértices,
arestas e faces, que não satisfazem um determinado critério local e efetuar uma triangulação
na região removida.
Incremental Decimation
Segundo [Schroeder] a decimação de uma malha segue os seguintes passos:
Passo 1: Os vértices da malha são classificados como simples, singular, de bordo, de
aresta, interior ou de canto.
Figura 1.2: Classificação dos Vértices
Fonte: Disponível em [Schroeder]
Passo 2: Nesta etapa são avaliados se os vértices candidatos satisfazem determinados
critérios para a remoção. Assim para cada vértice simples é calculado um plano médio π com
normal Nπ e com x ∈ π tal que:
X
Ni Ai
Nπ = X
Ai
1.2 Trabalhos Relacionados
15
e
X
ci Ai
x= X
Ai
Onde Ni , Ai e ci são respectivamente as normais, as áreas e os centróides de cada triângulo
da vizinhança estrelada dos vértices simples.
Sendo assim, um vértice v será removido se d(v, π) > .
Passo 3: Nesta etapa é realizada a triangulação nas regiões onde os vértices foram
removidos.
Vertex Clustering
No trabalho de [Gotsman] é desenvolvida uma representação compacta de um modelo
3D que inclui:
• Métodos para reduzir a complexidade de uma malha por simplificação, reduzindo assim
o número de vértices e faces na malha.
• Métodos para reamostrar a geometria na ordem de distribuição dos vértices.
A técnica tratada no referido trabalho descreve uma classe de algoritmos para transformar
uma malha inicial Mi em uma malha Mf com uma quantidade menor de vértices, arestas e
faces. O processo é usualmente controlado por critérios definidos pelo usuário que preservem
as propriedades esfecíficas iniciais da malha.
Figura 1.3: Mesh Decimation
Fonte: Disponível em [Gotsman]
1.2 Trabalhos Relacionados
16
A ideia básica é, para uma determinada tolerância é particionada uma região da malha
em células que possuem diâmetro menor que . Com base na proximidade geométrica, para
cada célula é determinado um vértice representante que é atribuído à todos os vértices que
estão nesta célula. Nesta célula temos um cluster o qual é composto por vários vértices que tem
uma relação de adjacência com o representante, daí o processo busca substituir os vértices deste
cluster por um único vértice. No geral este é um algoritmo eficaz e robusto cuja complexidade
é linear no número de vértice da malha, no entanto a qualidade da malha resultante não é
satisfatória.
1.2.2
Re-Tiling Polygonal Surfaces
Neste método de simplificação descrito por [Turk] a entrada do algoritmo é a malha densa
e a quantidade de vértices da malha simplificada. Esses pontos são distribuídos aleatoriamente
sobre as faces e até mesmo sobre os vértices da malha original. Em seguida ocorre um processo
de relaxamento da posição desses pontos sobre a malha, de forma que para um ponto p, os
pontos próximos a ele são projetados no plano tangente à superfície em p e calcula-se a força
de repulsão que cada um exerce sobre ele, movendo-o para uma nova posicão na malha.
Feito isto, os vértices adicionados estarão fixados na malha. Daí é gerada uma nova malha
através da adição destes vértices, e em seguida os vértices da malha original são removidos e
uma nova triangulação é refeita obtendo assim a malha simplificada.
1.2.3
Otimização de Energia
Este método de simplificação de malhas visa realizar operações de remoção ou contrações
locais com o objetivo simplificar à malha através de uma função de energia. Neste sentido a
abordagem de otimização da malha define uma função de energia que mede a qualidade da
aproximação da malha inicial à resultante.
Mesh Optimization
Um trabalho que traz uma outra abordagem para o problema de simplificação é baseado
na minimização da função energia da malha [Hoppe]. Dada uma malha inicial M0 e um
conjunto de vértices V0 , queremos encontrar uma malha M que aproxime V0 com a menor
quantidade de vértices e seja topologicamente equivalente à M0 , através da minimização da
função energia:
E(M) = Edist (M) + Erep (M) + Espring (M)
1.2 Trabalhos Relacionados
17
Onde:
• Edist : Soma das distâncias dos pontos originais à malha, que controla a posição dos
vértices.
• Erep : Fator proporcional ao número de vértices à malha, que controla a quantidade de
vértices.
• Espring : Soma dos comprimentos das arestas, para garantir a convergência.
A otimização é iterativa obtida realizando movimentos legais que são movimentos que
não alteram a topologia da malha, como edge collapse, edge swap e edge split. Estes movimentos
legais são conduzidos por um processo de otimização da função de energia. Em cada etapa, o
vértice cuja eliminação causa o menor aumento da função de energia é suprimido.
Figura 1.4: Movimentos Legais
Fonte: Disponível em [Hoppe]
O processo de minimização da energia ocorre de forma iterativa através da otimização da
topologia e geometria da malha. Em cada etapa é gerado um complexo simplicial K através de
uma operação legal. Para K fixo, a posição dos vértices que minimiza o erro é determinada,
definindo assim uma malha M. Assim, se E(M) é menor que o erro da malha anterior, M
passa a ser a nova malha. A simplificação é obtida quando algum critério de convergência seja
satisfeito.
Progressive Meshes
Este método [Hugges] também segue a linha do trabalho descrito anteriormente. Dada
uma malha inicial M0 , a malha simplificada Mr é obtida através de um conjunto de operações
de colapso de arestas denominadas por ecol.
1.2 Trabalhos Relacionados
18
Aqui apenas a operação de edge collapse, e sua inversa, são consideradas para navegar
sobre diferentes níveis de representação de detalhes da malha.
Figura 1.5: Transformação de Collapse
Fonte: Disponível em [Hugges]
1.2.4
Métrica de Erros por Quádricas
A métrica de erros por quádricas descrito por [Garland] consiste em definir para cada
vértice em cada iteração uma métrica de erro de acordo com o desvio do vértice às faces as
quais ele pertencia na iteração anterior. Dado um triângulo Ti , a sua distância de um ponto x
2
pode ser escrita como (nT
i x − pi ) , com ni normal à Ti . O funcional E(x) =
2
(nT
i x − pi ) define o
P
erro no vértice e seus isocontornos são elipsóides. Na figura abaixo, é ilustrado o erro associado
a cada vértice:
Figura 1.6: Elipsóides de Erro
Fonte: Disponível em [Garland]
Dessa forma, os pares de vértices adjacentes que possuem menos erro são marcados para
colapso da aresta, que pode ser para qualquer ponto da aresta formada por esses vértices, como
mostra a figura 1.7.
Caso se deseje uma maior simplificação, deve-se considerar vértices que não são adjacentes
para junção, figura 1.8. Uma possível escolha é tomar vértices e planos em uma determinada
região do espaço. Isso permite alterar a topologia da malha simplificada.
1.3 Contribuições
19
Figura 1.7: Colapso de Aresta
Fonte: Disponível em [Garland]
Figura 1.8: Junção de Vértices
Fonte: Disponível em [Garland]
1.3
Contribuições
O trabalho aqui apresentado, mostra uma nova forma de simplificar malhas a partir de
templates, diferenciando-se um pouco dos trabalhos relacionados que buscam aplicar operações
e movimentos legais aos componentes da malha, tais como usando swap, collapse e split em
uma malha e minimizando os termos de energia, resultando assim em uma malha simplificada.
A principal contribuição deste trabalho radica na obtenção de uma malha simplificada
com propriedades topológicas definidas a priori em uma malha base que tem a função de um
tamplate.
1.4
Visão Geral do Trabalho
Em nosso trabalho, a solução do problema é encontrada de modo iterativo. Inicialmente
temos duas malhas Md e M0 de forma que a primeira é densa, e fixa ao longo de todo o processo,
e a segunda a do template. O algoritmo inicia com estas duas malhas, primeiramente elas
são alinhadas, de forma que suas direções principais coincidam. Após o alinhamento, criamos
uma correspondência entre cada vértice da malha densa com o mais próximo dele no template,
segundo a distância euclidiana. Dessa forma são gerados clusters de vértices da malha densa,
cada um correspondente a um vértice do template.
No final deste processo, percebemos que há vértices cujos clusters possuem duas componentes conexas, e para estes vértices realizamos um procedimento de identificação e correção.
Após corrigirmos tais vértices, aplicamos o processo de subdvisão das arestas do template cujo
tamanho ficou muito grande após a projeção. Estas arestas grandes aparecem em áreas de
1.4 Visão Geral do Trabalho
20
concavidade da malha.
Com isso temos o fim do primeiro passo da iteração, que gera uma malha Mr que é
geometrica e topologicamente mais próxima de Md . Daí o processo de iteração é repetido
sempre entre a nova malha gerada Mr , com a malha fixa Md . E ao fim de toda a iteração temos
como resultado a simplificação de Md . O processo é finalizado quando encontramos uma malha
resultante da simplificação que é o mais próximo possível da malha densa inicial, do ponto de
vista topológico e geométrico.
No segundo capítulo descreveremos as principais características de uma malha do ponto
de vista topológico e geométrico, bem como trataremos das transformações geométricas e
topológicas em uma malha. No terceiro capítulo abordaremos a Análise de Componentes
Principais e sua aplicação para o alinhamento das malhas. No quarto capítulo tratamos do Fast
Marching Method. No quinto capítulo descreveremos o algoritmo de simplificação para reduzir
o número de elementos na malha através das projeções, e no sexto capítulo apresentaremos
alguns resultados bem como algumas análises.
21
2 FUNDAMENTOS
Neste capítulo apresentamos as definições e conceitos matemáticos que estão por trás
das técnicas desenvolvidas neste trabalho.
2.1
Superfícies
Definição 1. Um subconjunto S ⊂ R3 é uma superfície regular se, para cada p ∈ S, existe uma
vizinhança V de p em R3 e uma aplicação x : U → V ∩ S de um aberto U ∈ R2 sobre V ∩ S ⊂ R3
tal que:
1. x é diferenciável. Isto significa que se escrevemos
x(u, v) = (x(u, v), y(u, v), z(u, v))
com (u, v) ∈ U, as funções x(u, v), y(u, v) e z(u, v) têm derivadas parciais contínuas de
todas as ordens em U.
2. x é um homeomorfismo. Como x é contínua pela condição 1, isto significa que x tem
inversa x−1 : V ∩ S → U que é contínua.
3. Para todo q ∈ U, a diferencial dxq : R2 → R3 é injetiva
Figura 2.1: Superfície
Fonte: Disponível em http://www.professores.uff.br/katia_frensel/aulasgeodif/gdif.pdf
2.2 Malhas
2.2
22
Malhas
Uma malha triangular de uma superfície, é formada por três conjuntos: vértices, arestas
e faces. A informação que descreve os elementos da malha consiste na topologia e geometria da
malha. A topologia da malha fornece as relações de incidência entre seus elementos. Estas
relações de incidência especificam para cada face os vértices e arestas que à contém, para cada
aresta os vértices que estas incidem bem como as faces a qual a aresta é incidente, e para cada
vértice as arestas e face incidentes.
Uma malha M caracteriza a geometria da superfície pela posição de seus vértices
V = {v1 , v2 , ...., vn }
Figura 2.2: Malha de uma Superfície
Fonte: Autor, 2015
Definição 2. Uma malha M de uma superfície S é um conjunto de faces em que a intersecção
de duas faces quaisquer é uma aresta comum, um vértice comum a estas duas faces ou vazia.
A orientação de uma face é uma ordem cíclica dos vértices incidentes. Há duas possibilidades de orientação para cada face, no sentido horário ou anti-horário. A orientação de duas
faces adjacentes é compatível se, e somente se, os dois vértices da aresta comum incidente estão
em ordem inversa. Uma malha é denominada orientável, se e somente se, existe uma escolha
de orientações da face que faz com que todos os pares de faces adjacentes sejam compatíveis.
2.3 Vizinhança Estrelada
23
A Característica de Euler é um invariante topológico que descreve uma relação entre o
número de vértices V, arestas A e faces F, e o tipo topológico de uma variedade orientável:
|V| − |A| + |F| = 2(1 − g)
onde g é o genus (gênero) da superfície, isto é, o número de furos que a superfície apresenta.
Uma malha tem gênero g se, e somente se, podemos cortar a malha ao longo de dois
caminhos fechados sem desconectar a malha. A esfera, por exemplo, tem gênero zero e o toro
tem gênero um. Algumas malhas de gênero g podem ser deformadas em uma esfera com g
alças.
Figura 2.3: Bitoro de Gênero 2
Fonte: Disponível em https://en.wikipedia.org/wiki/Genus-2_surface
No caso especial de uma variedade fechada cada aresta tem exatamente dois triângulos
incidentes e cada triângulo três arestas incidentes, daí teremos:
• O número de faces é duas vezes o número de vértices, |F| ≈ 2|V|.
• O número de arestas é três vezes o número de vértices, |A| ≈ 3|V|.
2.3
Vizinhança Estrelada
Definição 3. Seja vi um vértice da malha M. A vizinhança estrelada de ordem k de vi é o
conjunto de vértices {v1 , v2 , ...., vn } que está separado de vi por no máximo k arestas.
A primeira vizinhança estrelada de vi é composta pelos vértices adjacentes a este vértice
inicial, a segunda vizinhança de vi é o conjunto de vértices adjacentes a cada vértice da primeira
vizinhança de vi junto com esta primeira.
2.4 Transformações Tridimensionais
24
Figura 2.4: Vizinhança Estrelada
Fonte: Disponível em http://www.maxwell.vrac.puc-rio.br/8176/8176_3.PDF
A k-ésima vizinhança estrelada é o conjunto de vértices adjacentes a cada vértice da
(k − 1)-ésima vizinhança, junto com esta vizinhança.
Figura 2.5: Terceira Vizinhança Estrelada
Fonte: Autor, 2015
2.4
Transformações Tridimensionais
Em diversas aplicações na área de computação gráfica, há a necessidade de alterar e
manipular a posição dos elementos que compõem uma dada superfície ou malha. Mudanças
na orientação, tamanho e formato do objeto estão ligadas às transformações geométricas.
Estas são aplicadas à malha para alterar sua geometria sem fazer alterações topológicas. Uma
transformação geométrica é uma aplicação bijetiva entre duas malhas de forma que a partir de
uma malha inicial Mi dada se forma outra topologicamente equivalente, Mf .
As principais transformações geométricas, como translação, rotação e escala, serão
discutidas aqui, as quais são de fundamental importância para o alinhamento de duas malhas
usando PCA.
2.4 Transformações Tridimensionais
2.4.1
25
Translação
Seja M uma malha a ser transladada. A translação de M é uma mudança na posição dos
vértices vi em relação ao seu sistema de coordenadas. Transladar M é adicionar uma constante
para cada vi , gerando assim novas posições para cada vértice de M.
Seja v = (x, y, z) um vértice de M, se transladamos v por (tx , ty , tz ) à nova posição de v
será um vértice v 0 = (x0 , y 0 , z 0 ) tal que:
x0 = x + tx
y 0 = y + ty
z 0 = z + tz
Então transladar uma malha Mi é somar um vetor de translação a cada vértice da malha,
e como resultado temos uma malha Mf que preserva a geometria e topologia de Mi .
2.4.2
Rotação
Seja M uma malha a ser rotacionada. A rotação de M é uma mudança na posição dos
vértices vi em relação ao seu sistema de coordenadas. Em nosso caso particular, rotacionar M
é, para cada vi ∈ M aplicarmos uma matriz de mudança de base gerando assim novas posições
para cada vértice de M.
Seja TM = {m1 , m2 , m3 } a base do espaço definida por M e TN = {n1 , n2 , n3 } a base do
espaço definida por N, então a rotação de M é a mudança de base T : M −→ N.
Para rotacionar M mudamos a base de TM para TN . Sendo assim, existe uma lista de
escalares λij tal que:
n1 = λ11 m1 + λ21 m2 + λ31 m3
n2 = λ12 m1 + λ22 m2 + λ32 m3
n3 = λ13 m1 + λ23 m2 + λ33 m3
E se quisermos:
nj =
3
X
i=1
λij mi
2.4 Transformações Tridimensionais
26
A matriz de mudança da base M para a base N é:
λ11 λ21 λ31
λ12 λ22 λ32
MN←−M =
λ13 λ23 λ33
Esta é a matriz de mudança de base que será aplicada a cada um dos vértices de M,
após sua aplicação teremos a nova posição de cada vértice que implica na rotação de M.
2.4.3
Escala
Seja M uma malha a ser escalada. A escala de M é uma mudança na posição dos vértices
vi em relação ao seu sistema de coordenadas. Escalar M é multiplicar todas as coordenadas do
vértice vi por um fator não nulo, gerando assim novas posições para cada vértice de M.
Seja v = (x, y, z) um vértice de M, se escalarmos v por (sx , sy , sz ) a nova posição de v
será um vértice v 0 = (x0 , y 0 , z 0 ) tal que:
x0 = x · s x
y 0 = y · sy
z 0 = z · sz
Em termos matriciais temos:
sx
0
0
0
y =
0
sy
0
0
· y
0
x0
z0
x
sz
z
Tomando S = (sx , sy , sz ), podemos ter:
• Se S > 1 a escala provoca uma ampliação em M na direção do(s) eixo(s) afetado(s) pelo
fator;
• Se 0 < S < 1 a escala provoca uma redução de M;
27
3 ANÁLISE DE COMPONENTES PRINCIPAIS
A Análise de Componentes Principais ou Principal Components Analysis PCA é um
método que tem por finalidade básica tanto a análise de dados visando reduzir sua dimensão
quanto a eliminação de sobreposições a partir de combinações lineares das váriaveis originais.
A PCA por muitas vezes é chamado também de Transformada Discreta de Karhunen-Loève
(KLT) ou ainda de Transformada Hotelling [Lindsay], em homenagem a Kari Karhunen, Michael
Loève e Harold Hotelling. Esta transforma variáveis discretas em coeficientes descorrelacionados.
Foi derivada por Hotelling e por ele denominada como Método dos Componentes Principais.
3.1
Componentes Principais
A PCA é uma maneira de identificar a relação entre características extraídas de dados.
É de grande utilidade quando os vetores de características tem muitas dimensões, quando uma
representação gráfica não é possível, mas também pode ser útil em dimensões menores. Em
nosso caso particular, temos uma malha M que possui v vértices. Nosso objetivo ao aplicar
PCA, é gerar em M um triedro que fornecerá as direções principais desta malha, de forma que
estas sejam representadas por vetores no R3 , onde a maior direção indica onde os vértices estão
mais espalhados e a menor direção indica onde estão menos espalhados os vértices ao longo da
malha.
A componente principal é a direção que melhor representa a distribuição dos vértices ao
longo da malha, de forma que é nesta componente onde há menor concentração de vértices
ao longo da malha, onde há maior concentração denominamos por componente secundária, e
entre estas há uma outra componente de distribuição à qual chamamos de componente média
da distribiução. Com estas três componentes formamos o triedro associado à malha, que
fornece à informação da distribuição dos vértices ao longo da malha em suas direções, principal,
secundária e média.
3.1 Componentes Principais
28
Para a determinação da PCA em uma malha M, tomemos V como o conjunto de todos os
vértices vi , com i = 1, ..., n de M, tal que V = {v1 , v2 , ..., vn }. Para determinar os componentes
principais seguimos os passos:
1 - Tomamos todos os vértices v de M, os quais escrevemos como uma lista de dimensão n.
2 - Determinamos a média vm de todos os vértices de M.
3 - Determinamos a diferença de cada v à vm .
4 - Calcular a matriz de covariância usando todas as diferenças.
5 - Calcular os autovalores e autovetores da matriz de covariância.
6 - Arranjar a Matriz de Hotelling, de tal forma que as colunas são formadas a partir dos
autovetores da matriz de covariância arranjados de modo que a primeira coluna, seja o
autovetor correspondente ao maior autovalor, e a última coluna corresponda ao menor
autovalor.
O autovetor com maior autovalor associado, corresponde à componente principal do
conjunto de vértices da malha, consequentemente o autovetor com menor autovalor associado,
corresponde à componente secundária.
3.1.1
Matriz de Covariância
Dado um conjunto de dados, sabemos que é possível determinar suas principais características no que diz respeito à estatística. Sobre tais dados podemos fazer uma análise a partir
da Média Aritmética, Desvio Padrão e Variância.
Definição 4. A covariância é um conjunto de primeira ordem das variáveis aleatórias x e y,
centrados nas respectivas médias, ou seja, é a média do grau de interdependência entre estas
duas variáveis.
A covariância é dada por:
cov(x, y) =
n
1X
[(xi − mx ) · (yi − my )]
n i=1
Onde, x e y são as componentes bidimensionais da lista de dados, mx e my são respectivamente, as médias da componente x e y da lista. E xi e yi , são os elementos da listas nas duas
direções em sua i-ésima posição. E finalmente n é o número de elementos da lista.
3.2 Análise de Componentes Principais - PCA
29
Propriedade: Sejam x e y duas variáveis aleatórias de valor real, então:
(a) cov(x, x) = var(x)
(b) cov(x, y) = cov(y, x)
Como estamos trabalhando com superfícies, então sendo M a malha, nossa lista de dados
guarda todos os vértices de M, com isso para cada i = 0, ..., n teremos os vértices vi = (xi , yi , zi ).
Então como esta lista de vértices está em coordenadas tridimensionais, calculamos a covariância
entre cada par de dimensões, isto é, determinamos cov(x, y), cov(x, z) e cov(y, z).
O vetor médio para os vértices de M em cada coordenada é:
mx =
n
1X
xi
n i=1
my =
n
1X
yi
n i=1
mz =
n
1X
zi
n i=1
Sendo assim teremos a matriz de covariância:
cov(x, x) cov(x, y) cov(x, z)
C = cov(y, x) cov(y, y) cov(y, z)
cov(z, x) cov(z, y) cov(z, z)
A diagonal principal da matriz C contém as variâncias e as demais posições a correlação
entre as direções. Essa matriz é simétrica e real, de modo que é sempre possível encontrar um
conjunto de autovetores ortonormais.
3.2
Análise de Componentes Principais - PCA
Dada uma malha M, aplicar PCA à M consiste em encontrar os eixos principais nesta
malha.
3.2 Análise de Componentes Principais - PCA
30
Figura 3.1: Aplicação do PCA ao Bunny e a Mão
Fonte: Autor, 2015
Vemos que após aplicarmos PCA na malha original, temos um triedro na nova malha
que indica as direções principais a partir do centro de massa de M. Este triedro é composto
pelos autovetores ordenados segundo seus autovalores, os quais formam as colunas em ordem
crescente da matriz de covariância. O triedro mostrado na figura 3.1 foi colorido segundo o
espalhamento dos vértices naquela direção:
• Azul: Aponta na direção com maior espalhamento de vértices;
• Vermelho: Aponta na direção com menor espalhamento de vértices;
• Verde: Aponta na direção com espalhamento de vértices intermediárias as anteriores;
A matriz de transformação para o cálculo da PCA consiste na matriz cujas colunas são
os autovetores da matriz de covariância dos vértices da malha. A matriz de covariância é uma
matriz simétrica e definida positiva, que guarda a informação sobre as variâncias em todos os
eixos onde os dados estão distribuídos.
3.2.1
Alinhamento
O processo de alinhamento de duas malhas usando PCA, nos fornece um encaixe entre
estas duas malhas de forma à facilitar o processo de projeções que veremos no capítulo posterior.
Sejam Ms e Mb as malhas que queremos alinhar. Dessa forma, o alinhamento ocorre da seguinte
maneira:
1. Transladamos o baricentro de Ms para o baricentro de Mb .
2. Após a translação, aplicamos a rotação em Ms , que nada mais é que mudar a base do
triedro de Ms dada pelo PCA para a base de Mb , o mesmo para seus vértices.
3. E finalmente, aplicamos uma escala Ms que busca deixar a Esfera com o "tamanho"aproximadamente igual ao do Bunny.
3.2 Análise de Componentes Principais - PCA
31
O procedimento de aplicarmos as transformações geométricas de translação, escala e
rotação a uma das malhas, é fundamentado primeiramente pelo uso do PCA, pois é nesta que
temos o ponto de referência inicial para ter o suporte necessário à aplicação das transformações.
Todos os procedimentos para o alinhamento inicial das malhas são baseados no PCA,
pois é aí que temos a determinação dos baricentros e triedros das malhas, os quais nos dão o
suporte necessário para à aplicação das transformações rígidas.
No processo de alinhamento inicial das malhas, é necessário a determinação do vetor
adcional para a translação que denominamos aqui por (tx , ty , tz ). Sendo assim, dadas as
malhas M e N, inicialmente queremos transladar M para N, para isto determinamos primeiro
o baricentro para ambas as malhas, BM = (bmx , bmy , bmz ) e BN = (bnx , bny , bnz ). A translação
simplesmente é fazer coincidir os baricentros de ambas as malhas, dessa forma o vetor de
translação será a diferença dos baricentros BN e BM :
(tx , ty , tz ) = (bnx − bmx , bny − bmy , bnz − bmz )
Quando aplicamos a PCA, o triedro é ordenado segundo o seu autovalor associado.
Sejam (λMx , λMy , λMz ) e (λNx , λNy , λNz ) os autovalores ordenados em valores ascendentes para
os triedros de M e N respectivamente. Então o fator de escala (sx , sy , sz ) aplicado à M é:
s
v
u
λN
λNx u
,t y ,
(sx , sy , sz ) = (
λMx
λMy
s
λNz
)
λM z
Desta maneira, com a determinação da translação, rotação e escala, e com a aplicação
da PCA já temos as ferramentas necessárias para realizar as transformações geométricas entre
duas malhas afim de determinarmos o alinhamento inicial entre elas, para daí dar inicio à
construção de suas resultantes simplificadas a partir do processo de projeções. Então, aplicados
todos os procedimentos descritos acima para as superfícies da Esfera e do Bunny temos o
alinhamento:
Figura 3.2: Alinhamento
Fonte: Autor, 2015
32
4 FAST MARCHING
Quando se atira uma pedra em um lago é gerada uma série de ondas consecultivas e
concêntricas, as quais se expandem sempre ao mesmo tempo. Este fenômeno natural se deve à
geração da onda em um meio homogênio que possibilita a velocidade de expansão constante no
meio. O ponto de origem da expansão é o ponto onde a pedra cai, que irá gerar as demais
ondas circulares onde teremos um certo tempo para alcançar cada uma delas.
Dessa forma, durante a expansão da onda, temos o tempo para se alcançar os pontos do
espaço, sendo o tempo onde a onda se origina em T = 0.
Figura 4.1: Ilustração FMM
Fonte: Autor, 2015
O Fast Marching Method (FMM), proposto inicialmente por J. Sethian em 1996 [Sethian],
é um método numérico que tem por objetivo aproximar a solução viscosa em uma malha M em
O(n log n) passos, onde n é o número de vértices de M, da equação Eikonal:
| OT |= F (x, y)
4.1
(4.1)
Fast Marching
A equação (4.1) descreve como se expande uma onda, onde x é a posição, F(x) é a
velocidade de propagação da onda na posição dada, e T(x) é o tempo para alcançar a posição
x. A idéia central é construir uma aproximação para o gradiente de T.
4.1 Fast Marching
33
Assim, utilizamos F ≡ 1, o que leva a função distância a um ponto ser monótona crescente.
Na figura 4.5, mostramos a propagação de uma onda.
Figura 4.2: Discretização do FMM
Fonte: Autor, 2015
Para determinar a distância do ponto u ao ponto v, calcula-se inicialmente a distânncia
à primeira vizinhança estrelada de u utilizando a distância euclidiana. A partir daí o FMM
procede com o cálculo da propagação da onda sobre a malha pela discretização adequada do
gradiente definindo uma solução T em cada vértice w na vizinhança de u, utilizando os valores
de distância de vizinhos já definidos. Dessa forma, utilizando a notação da figura 4.2, deve-se
determinar o valor de T(C) a partir dos valores conhecidos de T(A) e T(B).
Em uma construção para triângulos agudos, a discretização é obtida da seguinte maneira:
• u = T(B) − T(A)
• Resolver a equação em t:
(a2 + b2 − 2ab cos θ)t2 + 2bu(a cos θ − b)t + b2 (u2 − F 2 a2 sin2 θ) = 0
• Se u < t e cos θ < b(t−u)
< cosa θ :
t
T(C) = min{T(C), t + T(A)}
• Caso contrário:
T(C) = min{T(C), bF + T(A), cF + T(B)}
4.1 Fast Marching
34
A equação 4.1 é um caso particular da Equação de Hamilton - Jacobi [Peixoto e Velho].
A solução numérica desta equação é baseada nas Leis da Conservação Hiperbólica. Sendo assim,
a equação Eikonal pode ser resolvida pela equação:
h
i1
−y
+y
−x
+x
max(Dij
T, −Dij
T, 0)2 + max(Dij
T, Dij
T, 0)2 2 = Fij
Onde:
−x
Dij
=
Tij − Ti−1,j
4x
+x
Dij
=
Ti+1,j − Tij
4x
−y
Dij
=
Tij − Ti,j−1
4y
+y
Dij
=
Ti,j+1 − Tij
4y
e
e
A idéia central por trás do FMM para resolver estas equações é o processo de iteração
nos pontos da malha, e cada iteração os novos pontos vão sendo calculados:
Figura 4.3: Processo de Iteração
Fonte: Disponível em [Verónica Gonzalez]
Ao aplicarmos o FMM, durante o cálculo dos valores de T a informação vai sempre se
propagando na direção dos pontos que possuem os menores valores de T.
4.1 Fast Marching
35
Pela figura abaixo, vamos verificar como o processo de propagação ocorre à cada iteração:
Figura 4.4: Processo de Propagação
Fonte: Disponível em [Peixoto e Velho]
Os pontos pretos representam as posições onde a função T é conhecida e os pontos
brancos, posições onde T é desconhecida. Partindo de uma interface inicial, representada por
um ponto preto, onde T = 0 são calculados os valores de seus quatro vizinhos (representados
pelos pontos cinzas A, B, C e D, na segunda imagem), através da equação Eikonal discreta.
Dentre estes quatro pontos a propagação deve seguir a partir daquele que tiver o menor valor
de T, ou seja, o algoritmo para propagação requer que haja uma ordenação dos pontos cinzas.
Supondo que o ponto A contém o menor T, a propagação deve prosseguir a partir dele (terceira
imagem), ou seja, o ponto A é alterado para preto, indicando que a propagação já é conhecida
em A, e seus vizinhos são calculados (representados pelos pontos cinzas E, F e G, na quarta
imagem).
É importante observar que o ponto preto inicial, apesar de ser vizinho de A, não entrou
neste processo, pois a propagação tem sentido único, não é retroativa. A propagação deve
continuar a partir do ponto cinza (B, C, D, E, F ou G) que tiver o menor valor de T. Mais uma
vez será necessária a rotina de ordenação para selecionar o ponto cinza de menor T. Supondo
que o ponto D contém o menor valor, a propagação deve seguir a partir dele (quinta imagem).
O valor de T é calculado nos vizinhos de D, que são setados para cinza. É importante observar
que um dos vizinhos de D (o ponto E) já era cinza, pois também é vizinho de A, mas seu valor
deve ser recalculado (apenas os vizinhos pretos são poupados). O processo se repete até que a
função T seja determinada.
Usando a equação Eikonal, o cálculo de T nos vizinhos nunca fornece valores menores
do que os pontos já conhecidos e portanto, a “marcha” segue sempre em um único sentido, se
afastando da origem.
4.2 Fast Marching na Malha
4.2
36
Fast Marching na Malha
Agora vamos aplicar o FMM a uma malha M começando de um vértice inicial v0 , tomado
arbitrariamente, de forma que a "marcha"percorre para fora em única direção sem retorno
ao vértice inicial, alcançando outros vértices da malha. O objetivo principal é explorar uma
técnica baseda em uma fila de prioridades rápida para localizar sistematicamente o vértice da
malha adequado para atualizar, de modo que nunca precisa recuar para os vértices previamente
avaliados. A técnica resultante varre através da malha de n vértices em O(n log n) passos para
obter a distância ao ponto inicial.
Vejamos a aplicação do FMM em agumas malhas:
Figura 4.5: FMM na Esfera e no Bunny
Fonte: Autor, 2015
Figura 4.6: FMM no Cavalo e no Armadillo
Fonte: Autor, 2015
O vértice tomado inicialmente, está na região representada na cor azul nas figuras acima.
Sendo assim os pontos mais próximos ao vértice inicial são estes que aparecem na região azul,
os da região verde são os pontos que estão à uma distância média do vértice inicial, já os pontos
da região em vermelho ou que se aproximam de vermelho, em tons, são os pontos que estão
mais afastados do vértice tomado inicialmente.
4.2 Fast Marching na Malha
37
Ao aplicarmos o FMM a um vértice da malha M, estamos criando uma relação de distâncias
deste vértice inicial aos demais vértices da malha, isto significa que além de determinarmos o
vértice que está mais afastado do inicial, temos as distâncias entre este e os demais.
38
5 SIMPLIFICAÇÃO DE MALHAS
Diferente de como é tratado em alguns trabalhos relacionados a simplificações de
malhas que usualmente vemos nas referências atuais, a proposta deste trabalho é realizar uma
simplificação baseada em templates, de tal forma que inicialmente temos duas malhas Md e M0 ,
com Md densa, e a malha simplificada resultante vem da técnica de projeções dos vértices de
M0 em Md baseado na geração de correspondências entre vértices por uma distância euclidiana
mínima.
Neste capítulo trataremos do problema principal de nosso trabalho, de forma que dadas
duas malhas Md e M0 , com Md mais densa que M0 , vamos adaptar a geometria de M0 , de modo
que fique o mais próximo possível de Md . Note que o template M0 já vem com a topologia
predefinida.
5.1
Projeção do Template
Para iniciarmos o processo de projeção dos vértices do template na malha densa, e
consequentemente começar a gerar a malha simplificada resultante, é necessário estabelecermos
uma relação entre cada vértice de ambas as malhas. Essa relação será dada usando as menores
distâncias entre cada vértice da malha densa aos vértices do template.
Sejam, M0 e Md o template e a malha densa, respectivamente. A geração de correspondência busca para cada vértice vd ∈ Md quem é o vértice mais próximo vg ∈ M0 . Após calcular
para cada vértice da malha densa seu mais próximo no template, naturalmente cada vértice
do template está associado a um cluster de vértices da malha densa, que eventualmente pode
estar vazio ou ter apenas um elemento.
Então, para cada umas destas situações descritas acima, teremos um tratamento diferenciado:
Cluster com um ou mais Elementos
Para cada cluster, iremos agora determinar a média dos vértices que o compõem. Assim
sendo, todos os clusters Ci terão associados a ele uma média Mi de seus n elementos.
5.1 Projeção do Template
39
A princípio a projeção é dada da seguinte maneira:
1. Determinamos as correspondências entre a malha densa e o template.
2. Determinadas as correspondências, a projeção consiste em colocar cada vértice do template
na média de seu cluster.
Cluster Vazio
Eventualmente existem vértices de M0 que não são mais próximos de nenhum vértice de
Md . Neste caso fazemos um procedimento semelhante ao de determinar os mais próximos, só
que neste no sentido contrário. De tal forma que, para cada vi ∈ M0 que não é mais próximo de
ninguém, determinamos agora quem é o vértice de Md que é mais próximo deste. Então esses
vértices que inicialmente não eram correspondentes de ninguém serão trocados pelos vértices
de Md que são mais próximo a eles. A projeção para estes vértices é determinada pelo seu mais
próximo da malha densa.
Para uma primeira verificação do resultado da simplificação, tomemos a malha densa
como sendo a malha do Bunny e o template à Esfera. Daí temos o seguinte resultado:
Figura 5.1: Primeira Projeção para o Bunny
Fonte: Autor, 2015
5.1 Projeção do Template
40
Algoritmo Projeções
Vejamos agora os passos a serem seguidos para a realização da projeção dos vértices do
template M0 na malha densa Md .
entrada : Malha densa Md e o Template M0
saída
: Um vetor de listas de correspondências Ldg e Malha Projetada
1
Seja Ldg uma lista de listas vazias com o tamanho de M0 .
2
para cada vértice vd em Md faça
3
Calcule o vértice vg ∈ M0 mais próximo.
4
Insira vd em Ldg na posição de seu mais próximo vg
5
fim
6
para cada entrada de Ldg faça
7
se a quantidade de vértices é maior que zero, ou se a lista não for vazia então
8
Determine os clusters
9
Calcule a média de cada cluster
10
Na posição vg coloque a média do cluster correspondente
11
fim
12
senão
Coloque na posição de vg seu mais próximo na malha densa
13
14
15
fim
fim
Algoritmo 5.1: Projeção
No caso especial do Bunny que inicialmente possui 35.165 vértices, e após o processo de
projeção passa a ter 482 vértices, percebemos que na região com a concavidade na malha do
Bunny, entre a orelha e seu lombo, não fica muito bem representada geometricamente. Isto do
ponto de vista topológico não é um problema, e muito menos em seu aspecto de simplificação,
pois a malha resultante é muito menos densa que a malha original.
5.1 Projeção do Template
41
O que ocorre é o seguinte, nesta região da concavidade há correspondentes da esfera que
apesar de estarem no mesmo cluster pertencem à regiões não convexas do Bunny:
Figura 5.2: Relação das Correspondências entre o Bunny e a Esfera
Fonte: Autor, 2015
Dessa forma, no momento em que a malha resultante é redesenhada estes vértices no
"meio do caminho"geram faces entre as regiões não convexas do Bunny, ou seja, as faces ligam
a orelha ao lombo da malha. Para resolver esta situação nossa proposta inicialmente é detectar
esses vértices em cada cluster do Bunny. Em resumo queremos tomar os vértices dos clusters
que possuem pontos em duas ou mais regiões da malha, e estas regiões estão distantes se
andamos sobre esta malha, e tratá-los de alguma maneira que venha a resolver ou minimizar
esta situação. A estes vértices cujos clusters têm duas componentes conexas denominaremos
como Vértices Distantes.
Vértices Distantes
Aqui denominamos como vértices distantes, os vértices de Md que pertencem aos mesmos
clusters, mas estão em regiões diferentes da malha. Para resolvermos esse problema, iremos
determinar uma relação entre a distância da média dos vértices do cluster ao qual cada vértice
distante pertence à uma outra média, que é a média dos clusters de Md . Esse procedimento
serve para detectar os vértices de Md que estão mais afastados da média dos clusters, um fato
natural do ponto de vista estatístico, que é encontrar e de alguma maneira tratar o vértice que
se afasta e/ou está londe da média, que possivelmente são estes que causam o problema da
concavidade. Sendo assim vamos construir essa ferramenta para a criação de uma métrica que
estabelece quem é ou não distante.
Dado um vértice vi qualquer da malha densa Md , tomado aleatoriamente, ao aplicarmos
o FMM em vi estamos criando uma lista de distâncias entre vi e os demais vértices de Md .
Seja vd o vértice de Md que é o mais distante de vi pelo FMM. Agora aplicamos novamente o
FMM ao vértice vd . Daí temos todas as distâncias de cada vértice de Md a vi e vd . Então para
5.1 Projeção do Template
42
qualquer vértice de Md sabemos sua distância para cada um destes dois vértices ao aplicarmos
o FMM.
Qualquer vértice de Md , digamos v, é da forma v = (x, y, z). Desta feita, nosso objetivo
aqui é criar uma relação de distância entre cada vértice da malha e os vértices vi e vd , de forma
que o vértice v agora além de guardar as informações das coordenadas x, y e z, passsam a
guardar as duas informações de sua distância a cada um dos vértices que fora aplicada o FMM.
Em resumo seja v um vértice da malha, como vimos acima, sabemos a distância
di = d(v, vi ) bem como a distância df = d(v, vd ), daí cada vértice da malha agora passa a guardar
mais estas duas informações das distâncias, então v passa a ser da forma v = (x, y, z, di , df ). O
que estamos fazendo aqui é colocando mais duas coordenadas a cada vértice de Md , nas quais
as duas últimas são uma aproximação da geodésica discreta entre dois pontos. Isso permite que
nós possamos usar estas novas coordenadas como termos ponderadores no cálculo das médias
que fazemos para a projeção das malhas.
Figura 5.3: Terceira Vizinhança para cada Vértice do Template
Fonte: Autor, 2015
Para cada vértice v de M0 , representado em vermelho na figura 5.3, tomamos sua terceira
vizinhança estrelada. Fazemos o seguinte:
1. Determinamos a quantidade de vértices ni de seu cluster correspondente.
2. Determinamos a média mi do seu cluster correspondente.
5.1 Projeção do Template
43
Como sabemos, os vértices do template são correspondentes de algum cluster de vértices
da malha densa. Sendo assim cada vértice vt do template possui duas informações que dizem
respeito à média mi de seu cluster correspondente, bem como a quantidade ni de vértices deste
cluster. Então cada vértice vi da terceira vizinhança, em azul na figura 5.3, guarda estas duas
informações, com vi = (mi , ni ). Com isso podemos então calcular a média das correspondências
na terceira vizinhança para cada vértice do template.
Assim, para cada vértice de M0 a média dos clusters é calculada por:
n
X
Mclusters =
mi · ni
i=1
n
X
ni
i=1
Determinada a média das correspondências dos clusters para cada vértice de M0 , podemos
então estabelecer um critério para marcar quem é ou não um vértice distante em Md . Para
isto usamos o critério de que o vértice vi ∈ Md será marcado como distante se:
kmi − Mclusters k > δ
Onde mi é a média do cluster correspondente ao vi e Mclusters a média dos clusters
correspondentes aos vértices da terceira vizinhança de vi . Isto nos diz basicamente que são
distantes aqueles vértices que estão muito afastados da média dos clusters. Em nosso trabalho
o valor de δ é dado como parâmetro, o obtemos simplesmente testando alguns valores que
identificassem os vértices que realmente causavam problemas naquela região da concavidade.
Assim feito o valor adotado na maioria dos resultados foi de δ = 4.2. Por conta da dificuldade
de relacionar as características presentes em tudo que é calculado e determinado em cada malha
com essa tolerância, fica difícil estabelecer um valor fixo para δ, um critério determinístico
para isso, daí nossos resultados buscaram o melhor valor por tentativas que nos fornecessem os
resultados esperados.
Solução para os Vértices Distantes
Após determinar os vértices distantes em Md bem como suas duas novas coordenadas
dadas pelo FMM, temos que resolver o que fazer com eles. A princípio fazemos o seguinte, para
cada vértice vd ∈ Md em cada cluster:
• Se vd não é distante, a média do cluster é mantida na posição inicial da correspondência.
• Se vd é distante, verificamos a vizinhança de seu vértice correspondente vdc na malha
5.1 Projeção do Template
44
simplificada.
Agora para estes novos vértices de vdc que ficaram na posição dos vértices distantes, nós
fazemos a seguinte análise:
1. Tomamos a vizinhança estrelada Svdc .
2. Determinamos a quantidade de vértices nv de Svdc que são provenientes de médias.
3. Se nv ⩾ 3, calculamos a média destes vértices mv , e na posição de vdc colocamos mv .
4. Se nv < 3, colocamos a média do cluster correspondente à vdc em sua posição.
Após aplicarmos o procedimento acima para determinação e substituição dos vértices
distantes obtemos o seguinte resultado:
(a) Projeção
(b) Correção
Figura 5.4: Correção dos Vértices Distantes
Fonte: Autor, 2015
Pelo visto acima, após realizarmos a correção dos vértices distantes, há ainda arestas que
ligam as regiões da orelha esquerda do Bunny com seu lombo. Apesar de feita esta correção
e termos agora uma malha resultante topologica e geometricamente correta, há ainda essa
situação das arestas grandes que tornam a malha não muito agradável do ponto de vista
percepitível em comparação com a malha inicial.
Sendo assim, para resolvermos este problema, vamos denominar como arestas grandes, as
arestas que possuem um comprimento maior do que as demais arestas da malha, por exemplo,
estas arestas que ligam o lombo e a orelha do Bunny. Para consertar isso usaremos o processo
de subdivisão destas arestas grandes, a fim de que à cada iteração tenhamos uma redução no
tamanho destas arestas e por fim estas deixem de aparecer como no caso acima.
5.1 Projeção do Template
Algoritmo para Detecção e Correção dos Vértices Distantes
entrada : Cluster C
saída
1
: Lista de Vértices Distantes Ld e Malha Corrigida
para cada vértice vc em C faça
2
Calcule à distância d da média do cluster de vc à média dos clusters de S3 de vc .
3
se d > tolerância então
4
Marque vc como distante
5
Na posição de vc coloque o seu correspondente da malha grosseira
6
fim
7
senão
Na posição coloque a média de seu cluster.
8
9
fim
10
fim
11
para cada vértice vc marcado como distante faça
12
Verifique a quantidade nv de vizinhos que não são distantes
13
se nv > 3 então
14
Calcule a média mn destes vizinhos.
15
Na posição de vc coloque mn .
16
fim
17
senão
Na posição de vc coloque à média de seu cluster
18
19
20
fim
fim
Algoritmo 5.2: Detecção e Correção dos Vértices Distantes
45
5.1 Projeção do Template
46
Subdivisão das Arestas Grandes
Como descrito acima, temos por objetivo agora resolver o caso particular das arestas
que possuem tamanho superior as demais arestas que compõem a malha original. Para isto
usamos o processo de subdivisão que busca reduzir tais arestas acrescentando um novo vértice
à malha bem como duas novas faces que serão associadas a cada aresta grande encontrada.
Como visto anteriormente, mesmo após encontrar e resolver os vértices distantes de Md
ocorre a situação acima apresentada que são essas arestas grandes na região côncava do Bunny
entre a orelha e o lombo. Primeiramente temos que detectar quais são estas arestas na malha
resultante da projeção.
O processo de subdivisão ocorre da seguinte maneira:
1. Encontramos a maior aresta le do template.
2. Para cada aresta ln da malha resultante da projeção, construímos a desigualdade ln > k · le
3. Se a condição da desigualdade é verificada, à aresta ln é subdividida.
4. Se não, à aresta ln é mantida.
Temos os seguinte resultado para a subdivisão:
(a) Original
(b) Subdividida
Figura 5.5: Processo de Subdivisão
Fonte: Autor, 2015
5.1 Projeção do Template
47
O processo para verificar quais arestas serão subvidididas é descrito pelo algoritmo:
Algoritmo para Subdividir
entrada : Malha densa Md e Template Mg
saída
: Arestas Subdivididas
1
Calcule a maior aresta le de Mg
2
para cada aresta ld em Md faça
3
se ld > 1.2 · le então
4
Subdivida ld
5
fim
6
senão
Mantenha ld
7
8
9
fim
fim
Algoritmo 5.3: Arestas Grandes
Concluída a subdivisão, dadas as malhas M0 do template e Md densa, obtemos uma
malha Mr tal que a projeção agora é um processo completo dado da seguinte maneira:
1. Aplicamos o PCA a M0 para alinhá-la à malha Md .
2. Criamos as correspondências e realizamos a primeira projeção.
3. Detectamos e resolvemos os vértices problemáticos de Md .
4. Detectamos as arestas grandes e aplicamos a subdivisão a estas arestas.
5. Realizamos todo o processo de projeção novamente, agora levando em conta os novos
vértices.
48
6 RESULTADOS
Para gerar os resultados implementamos as aplicações em C + + usando gsl, OpenGL
e a estrutura de dados Directed edge. O fator para determinar os vértices distantes de Md
foi δ = 4.2. Para a aplicação da subdivisão nas arestas grandes usamos o fator multiplicativo
da desigualdade das arestas de k = 1.2. Nos resultados mostrados a seguir, a nova malha
simplificada gerada apresentará a quantidade de vértices pelo menos igual a do template.
Nas primeiras imagens mostradas abaixo, temos que:
• (a) Bunny Original: Refere-se à malha original do Bunny que possui 35.165 vértices;
• (b) Vênus Original: Refere-se à malha original de Vênus que possui 100.759 vértices;
• (c) Buste Original: Refere-se à malha original de Buste que possui 28.955 vértices;
• (d) Max Original: Refere-se à malha original de Max que possui 24.491 vértices;
Em todos os resultados gerados usamos como template a esfera, tanto a esfera menor
com 162 vértices, até uma esfera maior com 5.122 vértices. No caso do Bunny o processo de
iteração foi repetido quatro vezes, para as demais malhas um única vez.
6 RESULTADOS
49
Esfera e Bunny
(a) Bunny Original
(b) Bunny com 285 Vértices
(c) Bunny com 564 Vértices
(d) Bunny com 775 Vértices
(e) Bunny com 1443 Vértices
Figura 6.1: Simplificação do Bunny
Fonte: Autor, 2015
6 RESULTADOS
50
Esfera e Vênus
(a) Vênus Original
(b) 162 Vértices
(c) 482 Vértices
(d) 642 Vértices
(e) 1282 Vértices
(f) 2562 Vértices
(g) 5122 Vértices
Figura 6.2: Simplificação de Vênus
Fonte: Autor, 2015
6 RESULTADOS
51
Esfera e Buste
(a) Buste Original
(b) 162 Vértices
(c) 482 Vértices
(d) 642 Vértices
(e) 1282 Vértices
(f) 2562 Vértices
(g) 5122 Vértices
Figura 6.3: Simplificação de Buste
Fonte: Autor, 2015
6 RESULTADOS
52
Esfera e Max
(a) Max Original
(b) 162 Vértices
(c) 482 Vértices
(d) 642 Vértices
(e) 1282 Vértices
(f) 2562 Vértices
(g) 5122 Vértices
Figura 6.4: Simplificação de Max
Fonte: Autor, 2015
6.1 Análise dos Resultados
6.1
53
Análise dos Resultados
Tabelas
Para as malhas densas que usamos em nosso processo de simplificação, temos as
quantidades de vértices e arestas:
Malha
Bunny
Vênus
Buster
Max
Informações Iniciais
Vértices
35165
100759
28955
24941
Faces
70326
201514
57906
49878
Após realizarmos o processo de simplificação pelas projeções, as malhas apresentadas
nas figuras acima apresentam as seguintes características:
Figura
Bunny 6.1(b)
Bunny 6.1(c)
Bunny 6.1(d)
Bunny 6.1(e)
Vênus 6.2(b)
Vênus 6.2(c)
Vênus 6.2(d)
Vênus 6.2(e)
Vênus 6.2(f)
Vênus 6.2(g)
Buster 6.3(b)
Buster 6.3(c)
Buster 6.3(d)
Buster 6.3(e)
Buster 6.3(f)
Buster 6.3(g)
Max 6.4(b)
Max 6.4(c)
Max 6.4(d)
Max 6.4(e)
Max 6.4(f)
Max 6.4(g)
Informações Sobre os Resultados
Vértices
Faces
272
540
531
1058
725
1446
1443
2882
162
320
482
960
642
1280
1282
2560
2562
5120
5122
10240
162
320
482
960
642
1280
1282
2560
2562
5120
5122
10240
162
320
482
960
642
1280
1282
2560
2562
5120
5122
10240
Tabela 6.1: Malhas Simplificadas
RMSD
0.030918
0.030502
0.029839
0.029312
0.046982
0.046670
0.043839
0.042576
0.042144
0.041623
0.048447
0.048390
0.048373
0.048349
0.048332
0.048319
0.026986
0.026091
0.025967
0.025602
0.025329
0.025143
6.1 Análise dos Resultados
54
Nas tabelas apresentadas acima, vemos que após o processo de simplificação pela projeção
do template em cada uma das malhas dadas obtemos um resultado bastante satisfatório, uma
vez que além de reduzir o número de vértices da malha inicial, conseguimos construir a geometria
do template de forma que este preservou a topologia inicial da malha.
Obtidas as malhas simplificadas, agora iremos analisar o quão fiél é a representação
geométrica desta malha com relação a malha densa. Para isto, iremos verificar a proximidade
geométrica entre os vértices destas duas malhas no que diz respeito ao erro que mede sua
aproximação.
O erro de proximidade ao qual nos referimos é o desvio quadrático médio (RMSD) ou
a raiz do quadrado médio de erro (RMSE), que é uma medida das diferenças entre os valores
previstos por um modelo ou um estimador e os valores efetivamente observados.
Gráficos
Dadas as duas malhas, Md densa e Mr a simplificada resultante, iremos agora verificar o
quanto estas duas estão próximas do ponto de vista geométrico. Para isto usaremos uma métrica
de distância que busca quantificar a diferença entre a malha inicial e a malha simplificada, que
é dada pela distância de Hausdorf [Huttenlocher] que mede o quão distantes entre si estão dois
conjuntos de pontos. Esta distância atribui para dois conjuntos de vértices uma medida de
distância entre eles através de seus vértices.
Definição 5. (Distância de Hausdorff): Sejam A e B dois subconjuntos não vazios em
um espaço métrico (M, d). A função H : A × B → R, com H(A, B) = sup{inf d(a, b)} mede a
a∈A b∈B
proximidade de A e B.
Assim, a distância de Hausdorff dH é definida como:
dH (A, B) = max{H(A, B), H(B, A)}
A distância de Hausdorff representa uma distância entre duas superfícies. Vejamos a
aplicação desta distância em cada uma das malhas resultantes na simplificação apresentada em
nosso trabalho. Para cada par de malhas, densa e sua respectiva simplificação, determinamos a
similaridade entre estas duas malhas por um medida de erro dada pela distância de Hausdorff,
que a cada malha simplificada que apresenta maior quantidade de vértices o erro de aproximação
diminui indicando assim que as duas malhas ficam cada vez mais próximas.
Vejamos nos gráficos abaixo como ficaram os resultados após à aplicação da distância de
Hausdorff e a determinação do erro de quantificação da direfença entre ambas as malhas.
6.1 Análise dos Resultados
55
Figura 6.5: RMSD Bunny
Fonte: Autor, 2015
Figura 6.6: RMSD Vênus
Fonte: Autor, 2015
6.1 Análise dos Resultados
56
Figura 6.7: RMSD Buste
Fonte: Autor, 2015
Figura 6.8: RMSD Max
Fonte: Autor, 2015
Pelos gráficos mostrados acima para cada uma das malhas densas, percebemos que ao
passo que aumentamos a quantidade de vértices do template, a medida do erro de sua malha
resultante à inicial vai diminuindo. Isto significa que, no processo de projeção do template
na malha densa, quanto mais vértices tem o template mais fidelizada é sua representação
geométrica e topológica com respeito a malha inicial, de forma que termos duas superfícies
geometricamente mais próximas quando o erro é menor.
6.1 Análise dos Resultados
57
Colorização
Para verificar a medida do erro que foi determinada para cada malha simplificada usando
a distância de Hausdorff, iremos agora mostrar como fica representado tal erro na malha densa
original. Para isto iremos plotar o erro nesta malha usando um processo de colorização dos
vértices baseado em sua proximidade à malha inicial.
Na tabela abaixo mostramos os valores de mínimo e máximo obtidos pela distância de
Hausdorff para cada uma das malhas simplificadas de Max.
Malha
Figura 6.4 (b)
Figura 6.4 (c)
Figura 6.4 (d)
Figura 6.4 (e)
Figura 6.4 (f)
Figura 6.4 (g)
Max
Erro Mínimo
0.000001
0.000001
0.000003
0.000002
0.000001
0.000001
Erro Máximo
0.213896
0.168313
0.133386
0.123945
0.110488
0.109941
Tabela 6.2: Erros Max
Nos resultados mostrados abaixo, as regiões em vermelho correspondem ao erro mínimo,
e as em azul ao erro máximo. O processo de colorização mostrado a seguir foi obtido usando o
MeshLab.
Como vemos na tabela acima, para cada malha simplificada temos um valor para o erro
mínimo e outro para o erro máximo. Então, para realizar o processo de colorização mostrado
na figura 6.9, determinamos a escala do histograma, de forma que esta foi a mesma para todas
as malhas simplificadas. Para a determinação desta escala, dentre todos o valores mínimos do
erros tomamos o menor vmin , e dentre todos os valores máximos dos erros tomamos o maior
vmax . Sendo assim nossa escala para o histograma usado na colorização foi fixa (vmin ,vmax ).
6.1 Análise dos Resultados
(a)
58
(b) Max com 162 Vértices
(c)
(d) Max com 642 Vértices
(e)
(f) Max com 2562 Vértices
(g)
Figura 6.9: Colorização através da distância de Hausdorff em Max.
59
7 CONCLUSÕES
Este trabalho apresentou um procedimento para simplificar malhas de superfíces densas
a partir da projeção de vértices de um template. Para isto utilizamos alguns conceitos bastante
conhecidos, como a Análise de Componentes Principais e Fast Marching.
Nosso trabalho foi dividido em quatro etapas. A primeira foi dadas duas malhas Md
densa e Mg do template, calculamos o alinhamento entre estas duas a partir da PCA que fornece
o melhor "encaixe"entre elas. A segunda etapa foi a realização das projeções a partir da geração
de correspondências pela menor distância euclidiana, onde os vértices de Mg foram projetados
em Md segundo sua relação com a quantidade de elementos de cada cluster. Realizadas todas
as projeções, na terceira etapa identificamos e tratamos todos os vértices de Md cujo cluster
possuía duas componentes conexas. Na quarta etapa tratamos os casos das arestas grandes da
malha resultante das projeções na região côncava desta malha.
De um modo geral, nosso trabalho apresentou bons resultados principalmente para
aquelas malhas que possuem uma geometria muito parecida com a da esfera, como por exemplo
à de Vênus que na primeira iteração do processo já gerou uma boa aproximação em sua malha
resultante. Além disso, a proposta deste trabalho nos fornece a possibilidade de gerar uma
malha simplificada de uma inicialmente densa a partir do processo de projeção dos vértices
do template, o que viabiliza a reconstrução de malhas simplificadas entre superfícies que
apresentam a mesma topologia. A contribuição dada por este trabalho é de construir um
algoritmo simples que projeta vértices de um template em uma malha densa, tendo a topologia
e geometria definidas pela primeira.
Para um trabalho futuro, poderemos ter:
1. Otmizar o tempo de execução do nosso algoritmo.
2. Generalizar este processo de simplificação para malhas com gêneros diferentes de zero.
3. Encontrar uma relação entre os parâmetros para a determinação dos vértices cujos clusters
possuem duas componentes conexas, bem como para aplicar o processo de subdivisão
das arestas grandes.
4. Determinar uma solução mais eficaz para tratar os vértices cujos clusters possuem duas
componentes conexas.
60
REFERÊNCIAS
[Hoppe] Hoppe Hugues, Tony DeRose, Tom Duchamp, Jonh McDonald e Werner Stuetzle.
Mesh Optimization. Univertsity of Washington.
[Gotsman] Craig Gotsan, Stefan Gumhold and leif Kobbelt. Simplification and Compression of 3D Meshes. Computer Graphics Group, RWTH-Aachen, Germany.
[Garland] Michael Garland and Paul S. Heckbert. Surface Simplification Using Quadric
Error Metrics. Carnegie Mellon University, 1997.
[do Carmo] Manfredo Perdigao do Carmo. Geometria diferencial de curvas e superfícies.
SBM, 2010.
[Lindsay] Lindsay I Smith. A tutorial on Principal Components Analysis. February,
2002.
[Sethian] Ron Kimmel e James A Sethian. Computing Geodesic paths on Manifolds.
Proceedings of the National Academy of Sciences. Departament of Mathematics
and Lawrence Berkley National Laboratory, University of California, Berkeley. May, 1998.
[Verónica Gonzalez] Verónica González Pérez, Concepción A. Monje e Carlos Balaguer. Planificatión de Misiones de Vehículos Áereos no Tripulados con Fast Marching
en un Entorno 3D. Dpto. Ingeniería de Sistemas y Automática, Universidad Carlos III
de Madrid.
[Peixoto e Velho] Adelailson Peixoto e Luiz Velho. Transformadas de Distâncias. PUC-Rio,
Setembro, 2000.
[Morera] Dimas Martínez Morera. Geodesic-based Modeling on Manifold Triangulations. IMPA, 2006. Oriented by Paulo Cezar Carvalho and Luiz Velho.
[Lorusso] A. Lorusso, D. W. Eggert and R. B. Fisher. A comparasion of Four Algorithms
for Estimating 3D Rigid Transformations. Robotics and Automation Departament
Tecnopolis CSATA Novus Ortus. Valenzano, Bari, Italy.
[Shaoyi] Shaoyi Du, Nanning Zheng, Shihui Ying, Qubo You, Yang Wu. An Extension Of
The ICP Algorithm Considering Scale Factor. Institute of Artificial Intelligence
and Robotics. Xi’an Jiaotong University, Xi’an Shaanxi Province, China.
[Horn] Berthold K.P Horn. Closed Form Solution of Absolute Orietation Using Unit
Quaternios. Departament of Electrical Engineering. University of Hawaii. November,
1986.
[Vidal] Vincent Vidal, Christian Wolf. Robust Feature Line Extraction on CAD Triangular Meshes. Université de Lyon. Villeurbanne, France.
REFERÊNCIAS
61
[Cullière] Jean Christophe Cullière, Vincent Francois, Jean Marc Drouert. Automatic Mesh
Generation and Tranformation for Topology Optmization Methods. Departement de Génie Mecanique, Université du Québec. Canada.
[Sethian] J. A. Sethian. A Fast marching Level Set Method for Monotonically Advancing Fronts. Department of Mathematics, University of California, Berkeley. November,
1995.
[Schroeder] William J. Schroeder, Jonathan A. Zarge, William E. Lorensen. Decimation of
Triangle Meshes. General Electric Company. Schenectady, NY.
[Turk] Greg Turk. Re-Tiling Polygonal Surfaces. Department of Computer Science,
University of North Carolina at Chapel Hill .
[Hugges] Hugues Hoppe. Progressive Meshes. Microsoft Research.
[Huttenlocher] Daniel P. Huttenlocher, Gregory A. Klandermam and William J. Rucklidge.
Comparing Images Using the Hausdorff Distance.
