Sumário
COMPUTAÇÃO GRÁFICA E INTERFACES
Curvas Planas
◊ Introdução
◊ Curvas paramétricas
◊ Curva Bèzier
◊ Curva Hermite
◊ Curva B-Spline
◊ Curva Catmull-Rom
Carlos Carreto
Curso de Engenharia Informática
Ano lectivo 2003/2004
Escola Superior de Tecnologia e Gestão da Guarda
Introdução
Hoje em dia, uma das aplicações mais importantes da computação gráfica é
sem duvida o computer-aided design (CAD). O CAD é usado extensivamente
num grande número de áreas tais como engenharia aeroespacial, engenharia
automóvel, engenharia náutica, engenharia civil e engenharia electrónica.
O sucesso da aplicação da computação gráfica à engenharia deve-se
sobretudo ao progresso do chamado computer aided geometric design
(CAGD) que proporciona a base matemática para descrever e processar
forma geométricas, nomeadamente (curvas, superfícies e sólidos).
Os métodos mais promissores para descrever formas geométricas são as
curvas e superfícies paramétricas. Embora estes métodos sejam em
conhecidos na teoria, as suas aplicações em sistemas CAD têm sido objecto
de investigação nos últimos 50 anos. Os maiores avanços conseguidos são sem
duvida as representações Bèzier e B-spline de curvas e superfícies que são
hoje em dia o standard da industria.
Veremos a seguir a matemática por detrás destes métodos que são de
grande importância para a modelação de superfícies e sólidos.
Introdução
Formas de representar curvas
Forma não paramétricas
Representação por equações onde uma das coordenadas é
determinada em função da outra:
y = F(x)
Equações paramétricas
Representação por equações onde as coordenadas são obtidas
em função de um parâmetro:
y = F(t)
x = F(t)
1
Introdução
Introdução
Forma não paramétrica
Forma não paramétrica
Exemplos de equações não paramétricas na forma explicita
Exemplos de equações não paramétricas na forma implícita
y = f(x)
y = mx + b
z = - (Ax + By + D) / C
f( x, y) = 0
Ax + By + C = 0
(x - x0)2 + (y - y0)2 - r2 = 0
Levantam problemas na hora de representar curvas com laços ou com
tangentes verticais (m = ∞ na equação da recta).Por esse motivo têm um uso
limitado na computação gráfica.
Resolvem alguns problemas da representação explicita, mas não permitem o
calculo directo das coordenadas dos pontos. São úteis em computação para
determinar o exterior e o interior.
f( x, y, z) > 0 => Exterior
f( x, y, z) < 0 => Interior
Introdução
Principais desvantagens da forma não paramétricas para uso em CAGD
É difícil definir a equação não paramétrica de uma curva a partir de um
conjunto de pontos de controlo (é difícil de manipular interactivamente).
Introdução
Forma paramétrica
Curvas paramétricas
Superfícies Paramétricas
x = f(u)
y = g(u)
z = h(u)
x = f(u,v)
y = g(u,v)
z = h(u,v)
Exemplos de equações paramétricas
Não permite a representação de curvas com laços.
Circunferência:
x = x0 + r cos θ
y = y0 + r sin θ
θ∈[0, 2π]
É difícil definir a equação não paramétrica de uma curva que passe por um
conjunto de pontos pré-definidos.
Segmento de recta:
x = (1-t) . x0 + t . x1
y = (1-t) . y0 + t . y1
t ∈[0, 1]
2
Introdução
Introdução
Principais vantagens da forma paramétricas para uso em CAGD
Resolve os problemas da forma não paramétrica.
A curva pode ser definida a partir de um conjunto de pontos de controlo (é
fácil de manipular interactivamente).
A curva pode ou não passar por um conjunto de pontos pré-definidos.
A curva é aproximada por polinómios que definem as suas várias partes.
O comportamento da curva em relação a cada um dos eixos é definido por
equações independentes.
A curva é definida através de um
conjunto de pontos de controlo que
influenciam a forma da curva.
Os nós são pontos de controlo que
pertencem à curva.
A curva pode ser interpolada, passando
nesse caso por todos os pontos de
controlo, ou pode ser aproximada,
passando apenas em alguns pontos de
controlo ou mesmo em nenhum.
Os pontos de controlo definem a
fronteira de um polígono designado por
convex hull.
As coordenadas são obtidas em função de um parâmetro.
Introdução
Introdução
Por vezes é necessário representar a curva através de um conjunto de
curvas menores ligadas entre si. Nesse caso queremos garantir a
continuidade das curvas.
Definição de Spline
Uma Spline é uma curva composta por segmentos de curvas
definidos por polinómios que satisfazem determinadas
condições de continuidade nas extremidades de cada segmento.
Uma equação é classificada de acordo com os termos que
contem. Se todos os termos são elevados a uma determinada
potência, a equação é um polinómio. Se a maior potência é um, a
equação é linear. Se a maior potência é dois, a equação é
quadrática. E a maior potência é três, a equação é cúbica.
Continuidade de ordem
zero, as curvas
encontram-se num ponto
Continuidade de primeira
ordem, as tangentes são
coincidentes
Continuidade de segunda
ordem, a “velocidade”
antes e depois é igual
3
Introdução
Curvas Bèzier
Curvas paramétricas cúbicas
Características da curva Bèzier
Para garantir a continuidade de primeira ordem, as curvas são aproximadas
por polinómios de grau 3:
É definida por 4 pontos de controlo (P0, P1, P2, P3).
x(t) = axt3 + bxt2 + cxt + dx
y(t) = ayt3 + byt2 + cyt + dy
t∈[0, 1]
Passa pelos pontos extremos.
Os vectores tangentes dos pontos extremos são determinados a partir dos
segmentos de recta (P0, P1) e (P2, P3) .
Forma matricial:
[x y] =[t
3
t
2
a x
b
x
t 1 
c x

dx
]
P1
a y
by
c y

dy
P3
P0
P2
Curvas Bèzier
Curvas Bèzier
Curva Bèzier de 3 pontos
Curva Bèzier de 4 pontos
Considerem-se 3 pontos P0, P1 e P2 definindo os segmentos de recta (P0, P1) e
(P1, P2).
Seguindo o mesmo raciocínio e fazendo agora a ponderação de duas curvas:
C1(t) = (1-t) . R1 + t . R2
C2(t) = (1-t) . R2 + t . R3
Vimos que a equação da recta consiste numa média ponderada onde (1-t) é o
peso de P0 e t é o peso de P1: P(t) = (1-t) . P0 + t . P1
C3(t) = (1-t)3 . P0 + 3 . t . (1-t)2 . P1 + 3 . t2 . (1-t) . P2 + t3 . P3
É então possível definir uma curva com os 3 pontos, fazendo a ponderação
entre os dois segmentos de recta:
P
R1(t) = (1-t) . P0 + t . P1
R2(t) = (1-t) . P1 + t . P2
P1
1
C(t) = (1-t) . R1 + t . R2
C(t) = (1-t)2 . P0 + 2 . (1-t) . t . P1 + t2 . P2
C2
C1
P0
P0
P3
P2
P2
4
Curvas Bèzier
Curvas Bèzier
Curva Bèzier de 4 pontos
Vantagens
É fácil de construir.
A forma matricial fica:
Os vectores tangentes são definidos automaticamente pelos segmentos de
recta.
[x y] =[t 3
t2
-1
3
t 1 
−3

1
]
3 −3 1 P0
−6 3 0 P1 
3 0 0 P2
 
0 0 0 P3
Desvantagens
Não garante, de forma automática, a continuidade entre os segmentos de
curvas. Para que haja continuidade os últimos dois pontos do primeiro
segmento e os dois primeiros pontos do segundo segmento têm que ser
colineares.
Não permite controlo local, isto é, a alteração de um ponto de controlo altera
toda a curva.
Curvas Hermite
Curvas Hermite
Características da curva Hermite
Construção da curva Hermite
É definida por dois pontos de controlo P0 e P1, e dois vectores tangentes
(derivadas nos pontos), V0 e V1.
Sabemos que tem a forma geral P(t) = a . t3 + b . t2 + c . t + d, com t∈[0, 1].
Passa pelos dois pontos de controlo.
Sabemos que passo nos pontos extremos P0 e P1 e as derivadas nesses pontos
são V0 e V1.
Então:
P’(t) = 3 . a . t2 + 2 . b . t + c
V0
P0
P(0) = P0, P(1) = P1, P’(0) = V0, P’(1) = V1
P1
V1
V0
P0
P1
V1
5
Curvas Hermite
Curvas Hermite
Construção da curva Hermite
a
b
P(0) = [0 0 0 1 ]  
c

d
a
b
P(1) = [1 1 1 1 ]  
c

d
a
b
P'(0) = [0 0 1 0 ]  
c

d
a
b
P'(1) = [3 2 1 0 ]  
c

d
Curvas Hermite
Construção da curva Hermite
a
b
t t 1 
c

d
Como
[
P(t) = t
3
Fica:
[
P(t) = t
3
t
]
2
2
2
-3
t 1
0

1
]
-2 1 1   P(0)
3 -2 -1  P(1)
0 1 0 P'(0)


0 0 0 P'(1)
Construção da curva Hermite
As quatro incógnitas a, b, c e d podem ser determinadas resolvendo o sistema
de equações:
 P(0) 0

 
 P(1) = 1
P'(0) 0

 
P'(1) 3
0 0 1 a
1 1 1 b
0 1 0 c
 
2 1 0 d
Resolvendo em ordem aos coeficientes:
a  2
b -3
 =
c  0
 
d  1
-2 1 1   P(0)
3 -2 -1  P(1)
0 1 0 P'(0)


0 0 0 P'(1)
Curvas Hermite
Vantagens
É fácil de construir.
É adequada para aplicações onde seja útil definir a curva em função da inclinação dos
vectores tangentes.
Passa nos pontos de controlo.
Desvantagens
Não garante, de forma automática, a continuidade entre os segmentos de curvas.
Para que haja continuidade, o vector de fim do primeiro segmento deve ter a mesma
direcção e sentido do vector de inicio do segundo segmento.
Não permite controlo local, isto é, a alteração de um ponto de controlo altera toda a
curva.
6
Curvas B-Spline
Características da curva B-Spline
Curvas B-Spline
Equação matricial da curva B-Spline
É definida por quatro pontos de controlo (P0, P1, P2, P3).
Não passa por nenhum dos pontos de controlo.
É um tipo de curva mais suave do que as anteriores, com continuidade de
segunda ordem entre segmentos.
Curvas B-Spline
Vantagens
É fácil de construir.
Garante a continuidade automaticamente.
Permite controlo local.
[
P(t) = t 3 t 2
-1
3
t 1
-3

1
]
3 -3 1 P0 
-6 3 0 P1 
0 3 0 P2 
 
4 1 0 P2 
Curvas Catmull-Rom
Características da curva Catmull-Rom
É definida por quatro pontos de controlo (P0, P1, P2, P3).
É formada a partir de uma sequência de curvas Hermite, cujas tangentes são
calculadas automaticamente a partir dos pontos de controlo.
É traçada uma curva Hermite a cada par de pontos.
Desvantagens
Não passa nos pontos de controlo.
A curva passa pelos pontos de controlo excepto pelo primeiro e último.
7
Curvas Catmull-Rom
Curvas Catmull-Rom
Construção da curva Catmull-Rom
Construção da curva Catmull-Rom
Dado um conjunto de pontos de controlo {P0, P1, …, Pn}, queremos a curva que passa por todos os
pontos. A curva Catmull-Rom é construída com segmentos de curvas Hermite a cada par (Pi, Pi+1)
de pontos de controlo, cujos respectivas tangentes são: (Pi+1 – Pi-1) / 2 e (Pi+2 – Pi) / 2.
Multiplicando as duas matrizes de coeficientes obtemos a equação matricial da curva:
Considerando a equação matricial da curva Hermite:
P(t) = t 3 t 2
[
2
-3
t 1 
0

1
-2 1 1 
3 -2 -1
0 1 0

0 0 0
 Pi 
 P

 i +1 
Pi +1 − Pi −1 
 2 
 Pi +2 − Pi 


 2 
[
2
-3
t 1 
0

1
-2
3
0
0

0
 1
−
 2
0
0

ou
P(t) = t 3 t 2
]
]
1
-2
1
0
1
-1
0

0
[
P(t) = t
3
t
2
-1
2
t 1 
-1

0
]
3 -3 1 
-5 4 -1
0 1 0

2 0 0
Pi - 1 
P 
 i 
Pi +1 
 
Pi +2 
1
1
0  Pi - 1 
2
2  
1   Pi 
0
0
2  Pi +1 
0 1 0  
Pi +2 
1 0 0
−
Curvas Catmull-Rom
Curvas Catmull-Rom
Vantagens
É fácil de construir.
Construção da curva Catmull-Rom
Garante a continuidade automaticamente.
(Pi+1 – Pi-1) / 2
Permite controlo local.
(Pi+2 – Pi) / 2
Passa nos pontos de controlo.
8