Geração de Malhas – SME5827 Coordenadas Baricéntricas

Geração de Malhas SME5827
Coordenadas Baricéntricas
Afonso Paiva
ICMC-USP
4 de outubro de 2013
Coordenadas Baricéntricas
Denição
O ponto
v
é o baricentro dos pontos
somente se
v
=
v1
,...,v
n
w1 v1 + · · · + w
w1 + · · · + w
n
com pesos
vn
n
Os valores
w
i
são as coordendas baricéntricas de
v.
w1 , . . . , w
n
se
Coordenadas Baricéntricas
Denição
O ponto
v
é o baricentro dos pontos
somente se
v
=
v1
,...,v
n
w1 v1 + · · · + w
w1 + · · · + w
n
com pesos
vn
n
Os valores
w
i
são as coordendas baricéntricas de
v.
Coordenadas Baricéntricas Normalizadas
λ (v ) =
i
w (v)
i
w1 (v) + · · · + w
n
(v)
w1 , . . . , w
n
se
Coordenadas Baricéntricas
Denição
O ponto
v
é o baricentro dos pontos
somente se
v
=
v1
,...,v
n
w1 v1 + · · · + w
w1 + · · · + w
n
com pesos
w1 , . . . , w
n
se
vn
n
Os valores
w
são as coordendas baricéntricas de
i
v.
Coordenadas Baricéntricas Normalizadas
λ (v ) =
i
Logo,
P
=
λv
v1 , · · · , v .
v
pontos
i
i
i
n
com
P
i
i
w1 (v) + · · · + w
λ = 1,
i
w (v)
n
(v)
isto é, uma combinação convexa dos
Coordenadas Baricéntricas no Triângulo
v3
T
x
v2
v1
Objetivo: dado
x
∈ T,
queremos
λ1 , λ2 , λ3 ≥ 0
tal que:
λ1 + λ2 + λ3 = 1 ,
e
x
= λ1 v1 + λ2 v2 + λ3 v3
Coordenadas Baricéntricas no Triângulo
Precisamos resolver o sistema linear de ordem 3:


1
1
1
1
2
v
v
1
2
1
2
2
v
v
1
3
1
3
2
v
v

 
λ1
  λ2  = 
λ3
1
x1
x2


Coordenadas Baricéntricas no Triângulo
Precisamos resolver o sistema linear de ordem 3:


1
1
1
1
2
v
v
1
2
1
2
2
v
v
1
3
1
3
2
v
v

 
λ1
  λ2  = 
λ3
1
x1
x2


Pela Regra de Cramer a solução (única) é
λ1 =
A1
,
A
λ2 =
A2
,
A
λ3 =
A3
.
A
v3
A
A2
v1
x
A3
A1
v2
Coordenadas Baricéntricas no Triângulo
v3
A
A2
v1
Propriedades
x
A3
A1
v2
Coordenadas Baricéntricas no Triângulo
v3
A
A2
v1
Propriedades
I linearidade:
λ ∈ L(R2 ; R);
i
x
A3
A1
v2
Coordenadas Baricéntricas no Triângulo
v3
A
A2
x
A3
A1
v2
v1
Propriedades
I linearidade:
λ ∈ L(R2 ; R);
i
I propriedade de Lagrange:
λ (v ) = δ
i
j
ij
;
Coordenadas Baricéntricas no Triângulo
v3
A
A2
x
A3
A1
v2
v1
Propriedades
I linearidade:
λ ∈ L(R2 ; R);
i
I propriedade de Lagrange:
I inteporlação linear:
λ (v ) = δ ;
P
g (x) = 3=1 λ (x)f (v );
i
j
i
ij
i
i
Coordenadas Baricéntricas no Triângulo
v3
A
A2
x
A3
A1
v2
v1
Propriedades
I linearidade:
λ ∈ L(R2 ; R);
i
I propriedade de Lagrange:
I inteporlação linear:
I precisão linear: se
f
λ (v ) = δ ;
P
g (x) = 3=1 λ (x)f (v );
i
j
i
é linear
ij
i
⇒g =f.
i
Coordenadas Baricéntricas em Polígonos
v4
v3
v5
v2
x
vn
Seja
Ω
v1
um polígono convexo. As funções
coordenadas baricéntricas se para todo
x
=
x
λ : Ω → R, i = 1, . . . , n, são
∈ Ω, temos λ ≥ 0, i = 1, . . . , n
i
i
n
n
X
X
λ (x)v ,
i
i
=1
i
λ (x) = 1
i
i
=1
e
Wachspress Coordinates:
Wachspress, 1973
vi+1
vi
x
vi-1
Dado um polígono convexo com
λ (x) = P
i
j
Então
λ1 , . . . , λ
w (x)
=1 w (x)
i
n
n
j
com
n vértices.
w (x) =
i
Seja
A(v −1 , v , v +1 )
A(x, v −1 , v )A(x, v , v +1 )
são coordenadas baricéntricas.
i
i
i
i
i
i
i
Wachspress Coordinates:
Prova:
A
Sejam
i
= A(x, v , v +1 )
i
Assim, podemos escrever
x
Wachspress, 1973
A
B
i
=
x
vi −1
i
B
e
i
= A(v −1 , v , v +1 )
i
i
i
como:
+
(B − A −1 − A )
i
i
i
B
i
vi
A −1
v
B +1
i
+
i
i
i
e reagrupando:
B
i
A −1 A
i
(v − x) =
i
i
1
A −1
(v − v −1 ) −
i
i
i
1
A
(v +1 − v )
i
i
i
i
Somando os dois lados em :
X
i
B
i
A −1 A
i
(v − x) = 0 ⇒
X
i
i
w (v
i
i
i
− x) = 0 ⇒
x
=
X
w
i
P
i
j
w
vi
j
Mean Value Coordinates (MVC):
Floater, 2003
vi+1
αi
vi
x α i-1
vi-1
n vértices.
w
(
x
)
,
onde
=1
Dado um polígono convexo com
λ (x) = w (x)/
i
i
j
w (x) =
i
j
1
kv − xk
i
Então
λ1 , . . . , λ
Seja
n
P
n
tan
α −1 (x)
i
2
+ tan
são coordenadas baricéntricas.
α (x)
i
2
Mean Value Coordinates (MVC):
Prova:
Fazendo
n
Xh
tan
i
α
i
−1
ei
2
=1
= (v − x)/kv − xk,
+ tan
Para mostrar isto, faça
tan
α i
2
i
α i
ei
(e + e +1 ) =
i
i
i
i
2
Floater, 2003
basta provar que
n
X
= 0 ⇐⇒
ei
i
= (cos(θ ), sin(θ ))
i
tan
α i
2
i
tan
α i
2
=1
e
(e + e +1 ) = 0
i
α = θ +1 − θ
i
i
i
i
. Logo,
(cos(θ ) + cos(θ +1 ), sin(θ ) + sin(θ +1 ))
i
i
i
i
= (sin(θ +1 ) − sin(θ ), cos(θ ) − cos(θ +1 ))
i
i
Somando a última expressão em , temos
i
P
i
i
w (v
i
i
i
− x) = 0.
Mean Value Coordinates (MVC):
Floater, 2003
Não é limitado a polígonos convexos, pode ser
estendido para pontos no núcleo de um polígono
estrelado.
Propriedades
Mean Value Coordinates (MVC):
Floater, 2003
Não é limitado a polígonos convexos, pode ser
estendido para pontos no núcleo de um polígono
estrelado.
Propriedades
I linearidade na fronteira:
λ |[v ,v +1 ] ∈ L(R2 ; R);
i
i
i
Mean Value Coordinates (MVC):
Floater, 2003
Não é limitado a polígonos convexos, pode ser
estendido para pontos no núcleo de um polígono
estrelado.
Propriedades
I linearidade na fronteira:
λ |[v ,v +1 ] ∈ L(R2 ; R);
I propriedade de Lagrange:
i
i
i
λ (v ) = δ
i
j
ij
;
Mean Value Coordinates (MVC):
Floater, 2003
Não é limitado a polígonos convexos, pode ser
estendido para pontos no núcleo de um polígono
estrelado.
Propriedades
I linearidade na fronteira:
λ |[v ,v +1 ] ∈ L(R2 ; R);
I propriedade de Lagrange:
I inteporlação linear:
i
i
i
λ (v ) = δ ;
P
g (x) = =1 λ (x)f (v );
i
j
ij
n
i
i
i
Mean Value Coordinates (MVC):
Floater, 2003
Não é limitado a polígonos convexos, pode ser
estendido para pontos no núcleo de um polígono
estrelado.
Propriedades
I linearidade na fronteira:
λ |[v ,v +1 ] ∈ L(R2 ; R);
I propriedade de Lagrange:
I inteporlação linear:
I precisão linear: se
f
i
i
i
λ (v ) = δ ;
P
g (x) = =1 λ (x)f (v );
i
j
ij
n
i
é linear
i
⇒g =f.
i
Mean Value Coordinates (MVC):
Floater, 2003
Não é limitado a polígonos convexos, pode ser
estendido para pontos no núcleo de um polígono
estrelado.
Propriedades
I linearidade na fronteira:
λ |[v ,v +1 ] ∈ L(R2 ; R);
I propriedade de Lagrange:
I inteporlação linear:
I precisão linear: se
I suavidade:
C
0 em
f
i
i
i
λ (v ) = δ ;
P
g (x) = =1 λ (x)f (v );
i
j
ij
n
i
é linear
vi ,
i
⇒g =f.
caso contrário
C∞
i
Aplicação: deformação
Aplicação: deformação
Algoritmo: Dado
x
∈ Ω.
Aplicação: deformação
Algoritmo: Dado
1. Escreva
x
x
∈ Ω.
na forma
x
=
P
i
λ (x)v
i
i
usando MVC;
Aplicação: deformação
Algoritmo: Dado
1. Escreva
2. Faça
x
x
=
x
∈ Ω.
na forma
P
i
λ (x)v
i
x
i
.
=
P
i
λ (x)v
i
i
usando MVC;
Aplicação: parametrização de malhas
Próxima aula...