Mapas de Auto-reconstrução
Aluna: Renata Lúcia Mendonça Ernesto do Rêgo
Orientador: Aluizio Fausto Ribeiro Araújo
Reconstrução de Superfícies a
partir de nuvem de pontos.

Problema:

Dada uma nuvem de pontos, encontrar
um modelo 3D representado por uma
malha de polígonos:
Mapas de Auto Reconstrução


(Rego et al, 2007)
Objetivos do método:




Lidar com grande quantidade de pontos
Reconstruir malhas com diferentes
resoluções.
Aprender geometria dos pontos de
entrada (coordenadas dos vértices).
Aprender a topologia dos dados de
entrada (conexões entre os vértices).
Mapas Auto-organizáveis


SOM (Self Organizing Maps).
TRN (Topology Self Organizing Maps)




NG (Neural Gas)
CHL (Competitive Hebbian Learning)
GCS (Growing Cell Structures)
GNG (Growing Neural Gas).
Mapas Auto-organizáveis
SOM
TRN
Nodos ou Vértices
Conexões ou Arestas
s
x
GCS
GNG
y
z
Resultados
Limitações



Aberturas
Faces indesejadas
Normais não
orientadas no
mesmo sentido
Pós processamento



Remover faces indesejadas de modo
que cada aresta possua apenas duas
faces incidentes.
Preencher aberturas indesejadas.
Orientar normais das faces em um
mesmo sentido.
Eliminação de faces
indesejadas (1)

va
Foram estudadas três soluções
possíveis:




(Barhak, 2003)
Dada singular, ou seja, uma aresta
com mais de três faces incidentes,
permanecem na malha apenas as
duas faces que tiverem maior ângulo
entre si. As demais são removidas.
Solução implementada e testada.
Problemas:

Funciona apenas em casos onde a
superfície possui poucas curvaturas.
vb
a
c
d
b
Eliminação de faces
indesejadas (2)




Dada uma singular, verificar quais delas possuem arestas
de borda, ou seja, arestas com apenas 1 face incidente, e
eliminar estas faces.
Se não for suficiente, ou seja, se ainda assim, a aresta a
permanecer com mais de três faces incidentes, percorrer
a vizinhança das faces incidentes na aresta até que seja
encontrada uma aresta de borda.
Permanecem na malha apenas as duas faces com o
maior caminho até uma aresta de borda.
Conclusão:


A solução é útil para malhas com poucas arestas singulares,
caso contrário se torna custosa.
Outro problema é que a ordem com que se percorre as
arestas singulares afeta a determinação das faces
removidas.
Eliminação de faces
indesejadas (3)

Filtragem por normais utilizada no método Crust
(Amenta et al, 1998).



Os vetores sp+ e sp- de um ponto s a seus pólos p+ e psão aproximadamente ortogonais à superfície em s.
Estes vetores são usados em um passo de filtro de
normais que elimina as faces (triângulos) cuja direção da
normal é muito diferente da direção dos vetores sp+ e spdos vértices do triângulos a seus pólos.
Como abordar esta solução?


Quão diferente?
Como comparar um único vetor normal a seis outros
vetores?


Fazer uma média dos vetores?
Fazer uma média da distância?
Eliminação de faces
indesejadas (3)

Amenta et al (1998)

Filtro de normais pode ser perigoso em
bordas e arestas e arestas afiadas (sharp
edges).
Definição de pólos



Dado um conjunto de ponto, calcular o diagrama de Voronoi para
estes pontos.
Os pólos de um ponto s são os vetores os vértices de da região
de Voronoi de s (Vs) mais distantes de s em cada lado da
superfície.
p+ é o vértice de Vs mais distante de s e p- é o vértice de Vs mais
distantes de s com produto interno sp+.sp- negativo (p+.p- < 0).
Definição de pólos

p+ é o vértice de Vs mais distante de s e pé o vértice de Vs mais distantes de s com
produto interno sp+.sp- negativo (p+.p- < 0).
Orientação das normais das
faces


(Yang, 2004), http://artis.imag.fr
Se duas faces compartilham uma aresta, então verifica-se a
direção em que a aresta foi percorrida em cada uma delas na
definição da face. Se as faces percorrem a aresta em sentido
oposto, então suas normais estão consistentes, caso contrário
estão inconsistentes.
A
D
A
D
ABD
BAC
C
B
consistência
ABD
ABC
C
B
inconsistência
Orientação das normais das
faces




Considera-se que uma face está corretamente orientada.
Toma-se esta face como semente para corrigir todos as faces suas
faces vizinhas (com arestas compartilhadas).
Estas faces são usadas para corrigir suas faces vizinhas e assim
por diante.
Este método não é válido em malhas que possuam singularidades.



Faces que se encontram em vértices.
Faces que não se encontram.
Mais de duas faces se encontram em uma aresta.
Preenchimento de bordas
indesejadas

Alteração em um
parâmetro do
algoritmo reduziu a
quantidade de
bordas
indesejadas.

O parâmetro
a_max define a
freqüência de
eliminação de
arestas e faces;
Preenchimento de bordas
indesejadas


(Barhak, 2003)
Para cada aresta de borda


Verificar se os vértices da aresta incidem em outras arestas (a e b)de
borda.
Verificar se as extremidades e a e b são as mesmas.



Se positivo, o polígono que define a abertura foi encontrado.
Senão repetir o processo até encontrar o polígono.
Encontrado o polígono:


Se for um triângulo basta acrescentá-lo à lista de faces.
Colocar um vértice no meio dele e criar arestas entre o novo vértice e os
vértices do polígono e criar novas faces triangulares.
Observação: Este método só pode
ser executado depois que a
eliminação de faces indesejadas
tenha sido realizada. Caso contrário
novas faces indesejadas serão
criadas.
Referências






Rêgo, R.L.M.E., Araújo, A.F.R, Neto, F.B.L (2007). “Growing SelfOrganizing Maps for Surface Reconstruction from Unstructured
Point Clouds”. To appear in Proceedings of the International Joint
Conference on Neural Networks.
Fritzke, B. (1996). Unsupervised ontogenetic networks. Handbook
of Neural Computation, IOP Publishing and Oxford University
Press.
N. Amenta, M. Bern, M. Kamvysselis, “A new voronoi–based
surface reconstruction algorithm,” In Siggraph 98, Conference
Proceedings, pp. 415–422, 1998.
J. Barhak, “Reconstruction of freeform objects with arbitrary
topology from multi range images,” Ph.D. Thesis, Mechanical
Engineering Faculty, Technion, Haifa, Israel, 2003.
http://artis.imag.fr/Projets/Arcade/WP1/WP1LIMITED/task1.1/prepro/preprocess.html
Yang, J. (2004). "A procedural approach of inspecting CAD model
errors. Engineering Computations Vol. 21 No. 7, pp. 736-747