Introduo Computao Grfica Curvas Claudio Esperana Paulo Roma
Cavalcanti
Slide 2
Modelagem Geomtrica Disciplina que visa obter representaes
algbricas para curvas e superfcies com determinado aspecto e/ou
propriedades At agora temos considerado quase que exclusivamente
objetos geomtricos compostos de segmentos de reta ou polgonos
(curvas/superfcies lineares por parte) Na maioria dos casos, so
aproximaes de curvas e superfcies algbricas Mesmo quando s podemos
desenhar segmentos de reta e polgonos, conhecer o objeto que
estamos aproximando fundamental
Slide 3
Curvas e Superfcies Paramtricas Normalmente, o resultado da
modelagem dado em forma paramtrica Permite que a curva/superfcie
seja desenhada (aproximada) facilmente Permite indicar que trechos
da curva/superfcie sero usados Manipulao algbrica mais simples
Curva em 3D dada por C ( t ) = [ C x ( t ) C y ( t ) C z ( t )] T
Superfcie em 3D dada por S ( u, v ) = [ S x ( u, v ) S y ( u, v ) S
z ( u, v )] T
Slide 4
Continuidade Normalmente queremos curvas e superfcies suaves
Critrio de suavidade associado com critrio de continuidade algbrica
Continuidade C 0 funes paramtricas so contnuas, isto , sem pulos
Continuidade C 1 funes paramtricas tm primeiras derivadas contnuas,
isto , tangentes variam suavemente Continuidade C k funes
paramtricas tm k simas derivadas contnuas Alternativamente, G k :
continuidade geomtrica Independente de parametrizao Assumir curva
parametrizada por comprimento de arco C0C0 C1C1 C2C2
Slide 5
Interpolao x Aproximao natural querermos modelar uma curva
suave que passa por um conjunto de pontos dados Se a curva desejada
polinomial, chamamos tal curva de interpolao polinomial lagrangeana
Entretanto, o resultado nem sempre o esperado (oscilaes) mais comum
querermos curvas que passem perto dos pontos dados, isto ,
aproximaes
Slide 6
Algoritmo de De Casteljau Suponha que queiramos aproximar uma
curva polinomial entre dois pontos p 0 e p 1 dados A soluo natural
um segmento de reta que passa por p 0 e p 1 cuja parametrizao mais
comum p ( u ) = (1 u ) p 0 + u p 1 Podemos pensar em p ( u ) como
uma mdia ponderada entre p 0 e p 1 Observe que os polinmios (1 u )
e u somam 1 para qualquer valor de u So chamadas de funes de
mistura ( blending functions ) p0p0 p1p1 u
Slide 7
Algoritmo de De Casteljau Para generalizar a idia para trs
pontos p 0, p 1 e p 2 consideramos primeiramente os segmentos de
reta p 0 - p 1 e p 1 p 2 p 01 ( u ) = (1 u ) p 0 + u p 1 p 12 ( u )
= (1 u ) p 1 + u p 2 Podemos agora realizar uma interpolao entre p
01 ( u ) e p 12 ( u ) p 02 ( u ) = (1 u ) p 01 ( u ) + u p 12 ( u )
= (1 u ) 2 p 0 + 2 u (1 u ) p 1 + u 2 p 2
Slide 8
Algoritmo de De Casteljau p0p0 p1p1 p2p2 p 11 p 01 u = 0.25 p
02
Slide 9
Algoritmo de De Casteljau p0p0 p1p1 p2p2 p 11 p 01 u = 0.5 p
02
Slide 10
Algoritmo de De Casteljau p0p0 p1p1 p2p2 p 11 p 01 u = 0.75 p
02
Slide 11
Algoritmo de De Casteljau p0p0 p1p1 p2p2 p 02 ( u )
Slide 12
Algoritmo de De Casteljau A curva obtida pode ser entendida
como a mistura dos pontos p 0, p 1 e p 2 por intermdio de trs funes
quadrticas: b 02 ( u ) = (1 u ) 2 b 12 ( u ) = 2 u (1 u ) b 22 ( u
) = u 2 Aplicando mais uma vez a idia podemos definir uma cbica por
4 pontos p 02 ( u ) = (1 u ) 2 p 0 + 2 u (1 u ) p 1 + u 2 p 2 p 13
( u ) = (1 u ) 2 p 1 + 2 u (1 u ) p 2 + u 2 p 3 p 03 ( u ) = (1 u )
p 02 ( u ) + u p 13 ( u ) = (1 u ) 3 p 0 + 3 u (1 u ) 2 p 1 + 3 u 2
(1 u ) p 2 + u 3 p 3
Slide 13
Algoritmo de De Casteljau p0p0 p1p1 p2p2 p 02 ( u ) p 13 ( u )
p3p3 u = 0.25 p 03
Slide 14
Algoritmo de De Casteljau p0p0 p1p1 p2p2 p 02 ( u ) p 13 ( u )
p3p3 u = 0.5 p 03
Slide 15
Algoritmo de De Casteljau p0p0 p1p1 p2p2 p 02 ( u ) p 13 ( u )
p3p3 u = 0.75 p 03
Slide 16
Algoritmo de De Casteljau p0p0 p1p1 p2p2 p 02 ( u ) p 13 ( u )
p3p3 p 03 ( u )
Slide 17
Algoritmo de De Casteljau Novamente temos uma curva dada pela
soma de 4 funes de mistura (agora cbicas), cada uma multiplicada
por um dos 4 pontos b 03 ( u ) = (1 u ) 3 b 13 ( u ) = 3 u (1 u ) 2
b 23 ( u ) = 3 u 2 (1 u ) b 33 ( u ) = u 3 Em geral, uma curva de
grau n pode ser construda desta forma e ser expressa por
Slide 18
Curvas de Bzier e Polinmios de Bernstein As curvas construdas
pelo algoritmo de De Casteljau so conhecidas como curvas de Bzier e
as funes de mistura so chamadas de base Bzier ou polinmios de
Bernstein Observamos que os polinmios de Bernstein de grau n tm
como forma geral b i n ( u ) = c i u i (1 u ) n i Se escrevermos as
constantes c i para os diversos polinmios, teremos 1 o grau: 1 1 2
o grau: 1 2 1 3 o grau: 1 3 3 1 4 o grau: 1 4 6 4 1 Vemos que o
padro de formao corresponde ao Tringulo de Pascal e portanto,
podemos escrever
Slide 19
Polinmios de Bernstein
Slide 20
Forma Matricial da Base Bzier Podemos escrever a equao para uma
curva de Bzier cbica na forma
Slide 21
Propriedades de Curva de Bzier Continuidade infinita (todas as
derivadas so contnuas) O grau da curva (do polinmio) dado pelo
nmero de pontos do polgono de controle menos 1 A curva de Bzier est
contida no fecho convexo do polgono de controle Os polinmios de
Bernstein somam 1 para qualquer u A curva interpola o primeiro e
ltimo ponto do polgono de controle
Slide 22
Propriedades de Curva de Bzier As tangentes curva em p 0 e p n
tm a direo dos segmentos de reta p 0 p 1 e p n -1 p n,
respectivamente Para cbicas, as derivadas so 3( p 1 p 0 ) e 3( p 2
p 3 ) Qualquer linha reta intercepta a curva tantas ou menos vezes
quanto intercepta o polgono de controle No pode oscilar
demasiadamente Transformar os pontos de controle (transf. afim) e
desenhar a curva equivalente a desenhar a curva transformada
Slide 23
Desenhando Curvas Bzier Curva normalmente aproximada por uma
linha poligonal Pontos podem ser obtidos avaliando a curva em u = u
1, u 2... u k Avaliar os polinmios de Bernstein Usar o algoritmo
recursivo de De Casteljau Quantos pontos? Mais pontos em regies de
alta curvatura Idia: subdividir recursivamente a curva em trechos
at que cada trecho seja aproximadamente reto
Slide 24
Subdiviso de Curvas Bzier Como saber se trecho da curva reto?
Encontrar o polgono de controle do trecho Parar se vrtices do
polgono forem aproximadamente colineares p 00 p 10 p 20 p 30 u =
0.5 p 01 p 11 p 21 p 02 p 12 p 03
Slide 25
Curvas de Hermite Ao invs de modelar a curva a partir de um
polgono de controle (Bzier), especifica-se pontos de controle e
vetores tangentes nesses pontos Vantagem: fcil emendar vrias curvas
bastando especificar tangentes iguais nos pontos de emenda Exemplos
(cbicas):
Slide 26
Curvas de Hermite No caso de cbicas, temos o ponto inicial e
final alm dos vetores tangentes
Slide 27
Curvas Longas Curvas Bzier com k pontos de controle so de grau
k 1 Curvas de grau alto so difceis de desenhar Complexas Sujeitas a
erros de preciso Normalmente, queremos que pontos de controle
tenham efeito local Em curvas Bzier, todos os pontos de controle tm
efeito global Soluo: Emendar curvas polinomiais de grau baixo
Relaxar condies de continuidade
Slide 28
Emendando Curvas Bzier Continuidade C 0 : ltimo ponto da
primeira = primeiro ponto da segunda Continuidade C 1 : C 0 e
segmento p 2 p 3 da primeira com mesma direo e comprimento que o
segmento p 0 p 1 da segunda Continuidade C 2 : C 1 e + restries
sobre pontos p 1 da primeira e p 2 da segunda p0p0 p1p1 p2p2 p2p2
p3p3 p0p0 p1p1 p2p2
Slide 29
Splines A base de Bzier no prpria para a modelagem de curvas
longas Bzier nica: suporte no local Trechos emendados: restries no
so naturais Base alternativa: B-Splines Nome vem de um instrumento
usado por desenhistas Modelagem por polgonos de controle sem
restries adicionais Suporte local Alterao de um vrtice afeta curva
apenas na vizinhana Existem muitos tipos de Splines, mas vamos nos
concentrar em B-splines uniformes Uma B-spline uniforme de grau d
tem continuidade C d -1
Slide 30
Curvas B-Spline Funes de base so no nulas apenas em um
intervalo no espao do parmetro Como impossvel obter isso com apenas
1 polinomial, cada funo de base composta da emenda de funes
polinomiais Por exemplo, uma funo de base de uma B-spline quadrtica
tem 3 trechos (no nulos) emendados com continuidade C 1 u B i ( u
)
Slide 31
Curvas B-Spline Todas as funes de base tm a mesma forma, mas so
deslocadas entre si em intervalos no espao de parmetros Num
determinado intervalo, apenas um pequeno nmero de funes de base so
no-nulas Numa B-spline quadrtica, cada intervalo influenciado por 3
funes de base u B i ( u ) B i+ 1 ( u ) B i 1 ( u )
Slide 32
Curvas B-Spline Os valores u i do espao de parmetro que
delimitam os intervalos so chamados de ns Podemos pensar em
intervalos regulares por enquanto (B-Splines uniformes) isto , u i
= 1 u B i ( u ) B i+ 1 ( u ) B i 1 ( u ) u i1 uiui u i+1 u i+2 u
i+3 u i+4
Slide 33
Funes da Base B-Spline Queremos exprimir curvas como pontos
mesclados por intermdio de funes da base B-Spline onde m o nmero de
pontos do polgono de controle e d o grau da B-spline que se quer
usar Para derivar as funes da base B-spline pode-se resolver um
sistema de equaes Para B-splines cbicas, requere-se continuidade C
2 nos ns, a propriedade do fecho convexo, etc Uma maneira mais
natural utilizar a recorrncia de Cox-de Boor que exprime as funes
da base B-Spline de grau k como uma intepolao linear das funes de
grau k-1
Slide 34
Recorrncia Cox-de Boor u u i1 uiui u i+1 u i+2 u i+3 u i+4 B
i,0 ( u ) B i+ 1,0 ( u ) B i+ 2,0 ( u ) B i,1 ( u ) B i+ 1,1 ( u )
B i+ 2,0 ( u ) B i,2 ( u ) B i+1,2 ( u ) B i,3 ( u )
Slide 35
Recorrncia Cox-de Boor pipi p i+ 1 p i+ 2 p i+ 3 d = 0 (assumir
que para u = u i Spline de grau 0 passa por p i ) p ( u i u