Geração de Malhas – SME5827 Coordenadas Baricéntricas
Transcrição
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...