v - USP

Transcrição

v - USP

Métodos Numéricos para Geração de Malhas – SME0250
Complexos Simpliciais e
Estruturas de Dados
Afonso Paiva
ICMC-USP
19 de agosto de 2016
Qualidade da malha importa
Dois parabolóides: z = x 2 + y 2 com (x, y ) ∈ [−1, 1]2 com 400 triângulos.
Qualidade da malha importa
Dois parabolóides: z = x 2 + y 2 com (x, y ) ∈ [−1, 1]2 com 400 triângulos.
Triângulos finos causam erro de discretização e
de interpolação de derivadas.
Células e Simplexos
Definição (célula)
Dado um conjunto de pontos {v0 , v1 , . . . , vk } ⊂ Rn , a célula gerada por
estes pontos é o conjunto (combinação convexa):
(
)
k
k
X
X
[v0 , v1 , . . . , vk ] = v =
λi vi ; λi ≥ 0 ;
λi = 1
i=0
i=0
Definição (célula)
Dado um conjunto de pontos {v0 , v1 , . . . , vk } ⊂ Rn , a célula gerada por
estes pontos é o conjunto (combinação convexa):
(
)
k
k
X
X
[v0 , v1 , . . . , vk ] = v =
λi vi ; λi ≥ 0 ;
λi = 1
i=0
i=0
Exemplo
A célula gerada por [v0 , v1 , v2 ] pode ser um ponto, um segmento de reta
ou um triângulo, de acordo com a relação de dependência linear dos vetores
v1 − v0 e v2 − v0 .
Definição (posição geral)
Dado um conjunto de pontos {v0 , v1 , . . . , vm } ⊂ Rn , dizemos que eles
estão em posição geral, se para qualquer subconjunto {v0 , v1 , . . . , vk }, com
k ≤ n, os vetores v1 − v0 , v2 − v0 , . . . , vk − v0 são LI.
Definição (posição geral)
Dado um conjunto de pontos {v0 , v1 , . . . , vm } ⊂ Rn , dizemos que eles
estão em posição geral, se para qualquer subconjunto {v0 , v1 , . . . , vk }, com
k ≤ n, os vetores v1 − v0 , v2 − v0 , . . . , vk − v0 são LI.
v0
v0
v0
v1
P.G.
v1
P.G.
P.G.
v0
v1
v2
Não P.G.
v1
v0
v2
v3
Não P.G.
v2
Definição (k-simplexo)
Quando {v0 , v1 , . . . , vk } ⊂ Rn estão em posição geral, a célula por eles
gerada é chamada de simplexo de dimensão k ou k-simplexo. Denotaremos
tal simplexo por hv0 , v1 , . . . , vk i.
0-simplexo
1-simplexo
2-simplexo
3-simplexo
0-simplexo
1-simplexo
2-simplexo
3-simplexo
Dado σ = hv0 , . . . , vk i, cada ponto vi é chamado de vértice (ou 0-faces).
Os 1-simplexos gerados pelo par hvi , vj i, com i 6= j, são chamados de
arestas (1-faces). Os 2-simplexos gerados por hvi , vj , vk i, com i 6= j 6= k,
são chamados de faces (2-faces) de σ.
Decomposição Celular
Definição (decomposição celular)
Uma decomposição celular de um subconjunto D ⊂ Rn é um conjunto
finito de células C = {ci } que satisfazem às seguintes propriedades:
1. D = ∪i ci e
2. Se ci , cj ∈ C então ci ∩ cj ∈ C.
Decomposição Celular
Definição (decomposição celular)
Uma decomposição celular de um subconjunto D ⊂ Rn é um conjunto
finito de células C = {ci } que satisfazem às seguintes propriedades:
1. D = ∪i ci e
2. Se ci , cj ∈ C então ci ∩ cj ∈ C.
v3
v0
v2
v1
Decomposição celular do quadrado unitário que
possui células de 0, 1 e 2 dimensões:
I
dimensão 0: v0 , v1 , v2 , v3
I
dimensão 1: [v0 , v1 ], [v1 , v2 ], [v2 , v3 ], [v3 , v0 ]
I
dimensão 2: [v0 , v1 , v2 , v3 ]
Complexo Simplicial
Definição (complexo simplicial)
Quando todos os elementos de uma decomposição celular de uma região D
são simplexos dizemos que ela é um complexo simplicial (ou triangulação)
de D e denotaremos por T (D).
Complexo Simplicial
Definição (complexo simplicial)
Quando todos os elementos de uma decomposição celular de uma região D
são simplexos dizemos que ela é um complexo simplicial (ou triangulação)
de D e denotaremos por T (D).
trinagulação inválida
região D
duas triangulações de D
triangulação válida
Triangulação de Coxeter-Freudenthal-Kuhn (CFK)
v3
v2
v0
v1
v3
v2
v0
v1
A triangulação de um quadrado é formada pelos simplexos:
I
0-simplexos: v0 , v1 , v2 , v3
v3
v2
v0
v1
I
I
1-simplexos: hv0 , v1 i, hv1 , v2 i, hv2 , v3 i, hv3 , v0 i, hv0 , v2 i
v3
v2
v0
v1
I
I
1-simplexos: hv0 , v1 i, hv1 , v2 i, hv2 , v3 i, hv3 , v0 i, hv0 , v2 i
I
2-simplexos: hv0 , v1 , v2 i, hv0 , v2 , v3 i
Usando a diagonal do cubo, podemos decompô-lo em 6 tetraedros
(3-simplexos).
Fecho
Definição (fecho)
Seja Σ uma coleção de simplexos em T (D). O fecho de Σ, denotado por
close(Σ), é o menor subconjunto de T (D) que contém todas faces de Σ.
Fecho
Definição (fecho)
Seja Σ uma coleção de simplexos em T (D). O fecho de Σ, denotado por
close(Σ), é o menor subconjunto de T (D) que contém todas faces de Σ.
O fecho close(σ) pode ser obtido adicionando a σ todas as suas faces.
Estrela
Definição (estrela)
Seja Σ uma coleção de simplexos em T (D). Uma estrela de Σ, denotada
por star(Σ), é o conjunto de todos os simplexos em T (D) que tenham
uma face em Σ.
Estrela
Definição (estrela)
Seja Σ uma coleção de simplexos em T (D). Uma estrela de Σ, denotada
por star(Σ), é o conjunto de todos os simplexos em T (D) que tenham
uma face em Σ.
Geralmente star(Σ) não é um complexo simplicial!
Link & 1-anel
Definição (link)
Seja Σ uma coleção de simplexos em T (D). O link de Σ, denotado por
link(Σ), é definido por close(star(Σ)) \ star(close(Σ)).
Link & 1-anel
Definição (link)
Link & 1-anel
Definição (link)
Definição (1-anel)
O 1-anel de um vértice v é o conjunto de vértices de link(v).
Estruturas de Dados (ED)
O que armazenar na ED?
I
Geometria:
I
Geometria:
I
coordenadas 2D ou 3D;
I
Geometria:
I
I
Atributos de vértice ou face:
I
Geometria:
I
I
I
normal, cor, coordenada de textura;
I
Geometria:
I
I
I
I
Topologia:
I
Geometria:
I
I
I
I
Topologia:
I
relações de adjacência (conectividade).
O que a ED deve suportar?
I
Rendering;
I
I
Rendering;
Consultas geométricas:
I
I
Rendering;
I
Quais são os vértices da face i?
I
I
Rendering;
I
I
Qual são os vértices do 1-anel do vértice j?
vj
I
I
Rendering;
I
I
I
Quais são as faces adjacentes a face k?
vj
I
I
Rendering;
I
I
I
I
Modificações:
vj
I
I
Rendering;
I
I
I
I
Modificações:
I
Remover ou adicionar um vértice/face;
vj
I
I
Rendering;
I
I
I
I
vj
Modificações:
I
I
Remover ou adicionar um vértice/face;
edge-flip, edge collapse, vertex split
edge collapse
edge-flip
vertex split
O quão eficiente é a ED?
I
Tempo de construção
(pré-processamento);
I
I
Tempo de resposta de uma consulta;
I
I
I
Tempo para realizar uma operação;
I
I
I
Tempo para realizar uma operação;
I
Consumo de memória RAM.
Face Set
I
Face: 3 posições;
I
Não possui conectividade;
I
Arquivos do formato STL;
I
Simples e redundante.
(x11 , y11 , z11 )
(x12 , y12 , z12 )
(x13 , y13 , z13 )
..
.
f
(x1 , y1f , z1f )
Triângulos
(x21 , y21 , z21 )
(x22 , y22 , z22 )
(x23 , y23 , z23 )
..
.
(x31 , y31 , z31 )
(x32 , y32 , z32 )
(x33 , y33 , z33 )
..
.
(x2f , y2f , z2f )
(x3f , y3f , z3f )
Shared Vertex
I
Vértice: posição;
I
Face: índices dos vértices;
I
Não possui informação de vizinhança;
I
Arquivos dos formatos OBJ, OFF e PLY;
Vértices
x1 y1 z1
x2 y2 z2
x3 y3 z3
..
..
..
.
.
.
Triângulos
v11 v21 v31
v12 v22 v32
v13 v23 v33
..
..
..
.
.
.
xv
v1f
yv
zv
v2f
v3f
Shared Vertex no MATLAB
Como representar e desenhar um tetraedro no MATLAB?
V1
V3
V1
V4
V2
V1
V1
V3
V1
Vértices
1.0 0.0 0.0
0.0 1.0 0.0
0.0 0.0 1.0
0.0 0.0 0.0
V4
V2
V1
V1
V3
V1
Vértices
1.0 0.0 0.0
0.0 1.0 0.0
0.0 0.0 1.0
0.0 0.0 0.0
V4
V2
Triângulos
v2 v4 v3
v4 v2 v1
v3 v1 v2
v1 v3 v4
V1
Atenção: impor orientação nas faces (regra da mão direita).
V1
V3
V1
Vértices
1.0 0.0 0.0
0.0 1.0 0.0
0.0 0.0 1.0
0.0 0.0 0.0
V4
V2
Triângulos
v2 v4 v3
v4 v2 v1
v3 v1 v2
v1 v3 v4
V1
Atenção: impor orientação nas faces (regra da mão direita).
trimesh(trigs,X,Y,Z)
% trigs: lista de triângulos (índices)
% X,Y,Z: coordenadas dos vértices
Exemplo: arquivos .OBJ
Tetraedro
#
v
v
v
v
f
f
f
f
OBJ
1.0
0.0
0.0
0.0
2 4
4 2
3 1
1 3
file format with ext .obj
0.0 0.0
1.0 0.0
0.0 1.0
0.0 0.0
3
1
2
4
Shared Vertex
v3
v6
f3
v1
f1
f2
v2
I
Quem são os vértices da face f1 ?;
v4
f4
v5
Shared Vertex
v3
v6
f3
v1
f1
f2
v4
v2
I
I
O(1) – basta consultar a lista de faces;
f4
v5
Shared Vertex
v3
v6
f3
v1
f1
f2
v4
f4
v2
I
I
I
Quem são os vértices do 1-anel do vértice v3 ?;
v5
Shared Vertex
v3
v6
f3
v1
f1
f2
v4
f4
v2
I
I
I
I
busca completa em todos os vértices;
v5
Shared Vertex
v3
v6
f3
v1
f1
f2
v4
f4
v2
I
I
I
I
I
Os vértices v2 e v6 são adjacentes?;
v5
Shared Vertex
v3
v6
f3
v1
f1
f2
v4
f4
v2
I
I
I
I
I
Os vértices v2 e v6 são adjacentes?;
I
busca completa em todas as faces.
v5
Aquecimento MATLAB
Exercício
Plote no MATLAB um parabolóide usando os comandos meshgrid e surf.
Aquecimento MATLAB
Exercício
Plote no MATLAB um parabolóide usando os comandos meshgrid e surf.
Exercício
Faça uma função que gere uma malha triangular do parabolóide do
exercício anterior. Para plotar use o comando trimesh do MATLAB.
Half-Edge (HE)
I
Vértice:
I
I
posição
1 HE que sai do vértice
Half-Edge (HE)
I
Vértice:
I
I
I
posição
Half-Edge:
I
I
I
I
orientação consistente
1 índice do vértice de origem
1 índice da face incidente
1, 2, ou 3 índices de HEs
(próxima, anterior e oposta)
Half-Edge (HE)
I
Vértice:
I
I
I
Half-Edge:
I
I
I
I
I
posição
orientação consistente
1 índice do vértice de origem
1 índice da face incidente
1, 2, ou 3 índices de HEs
(próxima, anterior e oposta)
Face:
I
1 índice da HE adjacente
1-Anel com Half-Edge
1. Comece em um vértice
2. HE que sai do vértice
3. HE oposta
3. HE oposta
4. Próxima HE
3. HE oposta
4. Próxima HE
5. HE oposta
3. HE oposta
4. Próxima HE
5. HE oposta
6. Próxima HE
7. · · ·
Matriz de Adjacência
v3
v6
f3
v1
f1
f2
v4
f4
v5
v2
aij =
v1
v2
v3
v4
v5
v6
v1
0
1
1
0
0
0
v2
1
0
1
1
0
0
v3
1
1
0
1
0
1
v4
0
1
1
0
1
1
1 se os vértices vi e vj formam uma aresta
0 caso contrário
v5
0
0
0
1
0
1
v6
0
0
1
1
1
0
v3
v6
f3
v1
f1
f2
v4
v5
v2
aij =
I
f4
v1
v2
v3
v4
v5
v6
v1
0
1
1
0
0
0
v2
1
0
1
1
0
0
v3
1
1
0
1
0
1
v4
0
1
1
0
1
1
0 caso contrário
Nenhuma informação de conectividade entre um
vértice e suas faces adjacentes;
v5
0
0
0
1
0
1
v6
0
0
1
1
1
0
v3
v6
f3
v1
f1
f2
v4
f4
v5
v2
aij =
v1
v2
v3
v4
v5
v6
v1
0
1
1
0
0
0
v2
1
0
1
1
0
0
v3
1
1
0
1
0
1
v4
0
1
1
0
1
1
0 caso contrário
I
I
Esparsa e simétrica (grafos simples não orientados);
v5
0
0
0
1
0
1
v6
0
0
1
1
1
0
v3
v6
f3
v1
f1
f2
v4
f4
v5
v2
aij =
v1
v2
v3
v4
v5
v6
v1
0
1
1
0
0
0
v2
1
0
1
1
0
0
v3
1
1
0
1
0
1
v4
0
1
1
0
1
1
0 caso contrário
I
I
Esparsa e simétrica (grafos simples não orientados);
I
Pode representar malhas non-manifold.
v5
0
0
0
1
0
1
v6
0
0
1
1
1
0
Corner Table
Corner é um vértice com um dos seus triângulos incidentes
I
Corner – c
v3
c8
c3 c4
v1
c1
f2
f1
c2 c5
v2
f3
c6
c9
v4
c10
v6
c7
c12
f4
c11
v5
Corner Table
I
Corner – c
I
Triângulo – c.t
v3
c8
c3 c4
v1
c1
f2
f1
c2 c5
v2
f3
c6
c9
v4
c10
v6
c7
c12
f4
c11
v5
Corner Table
I
Corner – c
I
Triângulo – c.t
I
Vértice – c.v
v3
c8
c3 c4
v1
c1
f2
f1
c2 c5
v2
f3
c6
c9
v4
c10
v6
c7
c12
f4
c11
v5
Corner Table
I
Corner – c
I
Triângulo – c.t
I
Vértice – c.v
I
Corner próximo em c.t – c.n
(sentido anti-horário)
v3
c8
c3 c4
v1
c1
f2
f1
c2 c5
v2
f3
c6
c9
v4
c10
v6
c7
c12
f4
c11
v5
Corner Table
I
Corner – c
I
Triângulo – c.t
I
Vértice – c.v
I
I
Corner anterior em c.t – c.p (≡ c.n.n)
v3
c8
c3 c4
v1
c1
f2
f1
c2 c5
v2
f3
c6
c9
v4
c10
v6
c7
c12
f4
c11
v5
Corner Table
I
Corner – c
I
Triângulo – c.t
I
Vértice – c.v
I
I
I
Corner oposto – c.o
v3
c8
c3 c4
v1
c1
f2
f1
c2 c5
v2
f3
c6
c9
v4
c10
v6
c7
c12
f4
c11
v5
Corner Table
I
Corner – c
I
Triângulo – c.t
I
Vértice – c.v
I
I
I
Corner oposto – c.o
I
Corner direito – c.r (≡ c.n.o)
I
Corner esquerdo – c.l (≡ c.p.o)
v3
c8
c3 c4
v1
c1
f2
f1
c2 c5
v2
f3
c6
c9
v4
c10
v6
c7
c12
f4
c11
v5
Corner Table
Armazenamento
I
para cada vértice uma lista de todos os seus corners
Corner Table
Armazenamento
I
v3
c8
c3 c4
v1
c1
f2
f1
c2 c5
v2
f3
c6
c9
v4
c10
v6
c7
c12
f4
c11
v5
corner
c.v
c.t
c.n
c.p
c.o
c.l
c.r
c1
c2
c3
c4
c5
c6
..
.
v1
v2
v3
v3
v2
v4
..
.
f1
f1
f1
f2
f2
f2
..
.
c2
c3
c1
c5
c6
c4
..
.
c3
c1
c2
c6
c4
c5
..
.
c6
∅
∅
∅
c7
c1
..
.
∅
∅
c6
c7
c1
∅
..
.
∅
c6
∅
c1
∅
c7
..
.
Corner Table
Armazenamento
I
v3
c8
c3 c4
v1
c1
f2
f1
c2 c5
v2
f3
c6
c9
v4
c10
v6
c7
c12
f4
c11
v5
corner
c.v
c.t
c.n
c.p
c.o
c.l
c.r
c1
c2
c3
c4
c5
c6
..
.
v1
v2
v3
v3
v2
v4
..
.
f1
f1
f1
f2
f2
f2
..
.
c2
c3
c1
c5
c6
c4
..
.
c3
c1
c2
c6
c4
c5
..
.
c6
∅
∅
∅
c7
c1
..
.
∅
∅
c6
c7
c1
∅
..
.
∅
c6
∅
c1
∅
c7
..
.
Dada uma face j os corners são enumerados da forma: 3j, 3j − 1 e 3j − 2
Corner Table
v3
c8
c3 c4
v1
c1
f2
f1
c2 c5
v2
I
Quais são os vértices da face f3 ?
f3
c6
c9
v4
c10
v6
c7
c12
f4
c11
v5
Corner Table
v3
c8
c3 c4
v1
c1
f2
f1
c2 c5
v2
I
I
os c.v de corners 9, 8 e 7
f3
c6
c9
v4
c10
v6
c7
c12
f4
c11
v5
Corner Table
v3
c8
c3 c4
v1
c1
f2
f1
c2 c5
v2
I
I
I
Os vértices v2 e v6 são adjacentes?
f3
c6
c9
v4
c10
v6
c7
c12
f4
c11
v5
Corner Table
v3
c8
c3 c4
v1
c1
f2
f1
c2 c5
v2
I
c6
c9
v4
c10
f4
c11
v5
I
I
f3
v6
c7
c12
I
passe pelos corners de v2 , testando se c.p.v ou c.n.n são v6
Corner Table
v3
c8
c3 c4
v1
c1
f2
f1
f3
c6
c2 c5
v2
I
f4
c11
v5
I
I
v4
c10
I
I
c9
v6
c7
c12
Quais são as faces adjacentes a v3 ?
Corner Table
v3
c8
c3 c4
v1
c1
f2
f1
f3
c6
c2 c5
c9
v4
c10
v6
c7
c12
f4
c11
v2
I
I
I
I
I
v5
Quais são as faces adjacentes a v3 ?
I
verefique c.t de todos os corners de vértice v3
Cálculo da Normal
Normal por Face (regra da mão direita)
nT = [(b − a) × (c − a)]/k(b − a) × (c − a)k
Cálculo da Normal
nT = [(b − a) × (c − a)]/k(b − a) × (c − a)k
n
c
b
T
a
Cálculo da Normal
nT = [(b − a) × (c − a)]/k(b − a) × (c − a)k
n
c
b
T
a
Normal por Vértice (Gouraud shading)
na = v/kvk com v =
X
T ∈ star(a)
nT area(T )
Processamento Geométrico
Suavização de Vértice (Botsch & Kobbelt, 2004)
I
Melhora a qualidade dos triângulos
I
Move um vértice v para o baricentro bv de seu 1-anel
I
I
b
v
v
I
I
b
v
v
v = v + α [dv − (dv · nv )nv ]
e
dv = bv − v ,
onde nv é a normal do vértice v e α ∈ [0, 1] é um fator de relaxação.
Qualidade da Malha
Razão de Aspecto dos Triângulos (Desigualdade de Weizenbock)
√
4 3 area(T )
R= 2
a + b2 + c 2
onde a, b e c são os comprimentos dos lados de um triângulo T e a área
do triângulo pode ser calculada pela fórmula de Heron:
area(T ) =
p
a+b+c
s(s − a)(s − b)(s − c) com s =
2
Valores perto de 1 indicam que os 4s se aproximam de um 4 equilátero.
Qualidade da Malha

v - USP

Transcrição

Documentos relacionados

Avenida Nove de Julho, 4275 – Jardim Paulista

Corner

Corner Ad Corner Ad :

Corner "T"

PREFEITURA MUNICIPAL DE VESPASIANO

EXAME DE GEOMETRIA DESCRITIVA A

81lm

International Cultural Exchange Forum 問合せ

Alg I - Glencoe

oficial de registro de imóveis, títulos e documentos e civil de pessoa