Interpolação
Interpolação
• Princípio
– Alterar a posição espacial de um ponto de forma
incremental
• Questões fundamentais
– Qual a função de interpolação mais adaptada para
cada situação?
– Como parametrizar as funções de interpolação com
base na distância percorrida?
– Como assegurar o controlo da posição ao longo do
tempo?
– Definidos os key-frames, como gerar os in-betweens
da maneira mais eficaz?
1
Interpolação
• Existem 3 tipos de equações:
– Equações explícitas: y = f(x)
• Adequadas para a geração de novos pontos
– Equações implícitas: f(x,y) = 0
• Boas para conservar a consistência
– Equações paramétricas: x = f(t) e y = g(t)
• Adequadas para gerar sequências de pontos
• Classificadas de acordo com o grau dos seus termos: linear
(grau 1), quadrática (grau 2), cúbica (grau 3), transcendental
(sin, cos, ...)
Interpolação
• Representação paramétrica:
– Aproximação por polinômios que definem
partes de uma curva ou superfície (piecewise
polynomials)
• Parâmetro (t) é usado para percorrer a
curva
– x(t) = fx(t)
– y(t) = fy(t)
– z(t) = fz(t)
2
Interpolação
• Representação paramétrica
• Exemplo: círculo
x(t) = r . sin(t)
y(t) = r . cos(t)
0 <= t < 2π
Interpolação
• Interpolação linear
3
Interpolação
• Equação da curva Bézier 4 pontos
C3(t) = (1-t)3 * P1 + 3 * t * (1-t)2 * P2 + 3 * t2 * (1-t) * P3 + t3 * P4
Interpolação
• Escolha da função adequada
– Algumas técnicas
•
•
•
•
Interpolação linear
Hermite
Catmull-Rom
Bézier, etc.
– Como escolher a função adequada?
•
•
•
•
Interpolação ou aproximação
Complexidade
Continuidade
Controlo local ou controlo global
4
Interpolação
• A função adequada
– Interpolação ou Aproximação
• Interpolação: Hermite, Catmull-Rom spline
• Aproximação: Bézier, curvas B-spline
Interpolação
• A função escolhida
– Influi na eficiência do algoritmo
– Funções polinomiais de ordem maior que
cúbica não oferecem vantagens que
compensem o seu uso (em termos de
precisão e no caso geral)
5
Interpolação
• A função escolhida
– Continuidade
• Propriedade muito
importante
• Métodos adequados:
–
–
–
–
–
Hermite
Catmull-Rom
Blending de parábolas
Curvas Bézier cúbicas
etc.
Interpolação
• A função escolhida
– Controlo local ou controlo global?
6
Interpolação
• A função escolhida
– Métodos mais usados
• Bézier
• Catmull-Rom spline
– Curva passa por todos os pontos
– Continuidade tangencial
Interpolação
• Métodos mais usados
– Exemplo:
http://www.mvps.org/directx/articles/catmull/
7
Movimento ao longo de uma curva
• A que velocidade deve uma curva ser
percorrida?
• O animador deve ser capaz de controlar a
velocidade para poder produzir os resultados
desejados
• Primeiro passo
– Fornecer ao animador métodos para percorrer uma
curva em velocidade constante
• Segundo passo
– Permitir aceleração e desaceleração
Movimento ao longo de uma curva
• Dada uma função de interpolação P(u) que produz para
um dado u um valor p = P(u)
• Variação de u constante, não significa variação de p
constante
8
Movimento ao longo de uma curva
• Como manter a velocidade constante?
– Para manter a variação de p constante, a
função de interpolação deve ser
parametrizada de acordo com o comprimento
do arco (distância total)
Movimento ao longo de uma curva
• Como calcular o comprimento do arco?
– Opção 1: criar uma simplificação da curva e assumir o
comprimento do arco como a soma das distâncias
lineares entre os pontos de amostragem
– Opção 2: usar quadratura Gaussiana para estimar
numericamente o comprimento do arco
– Opção 1 e 2, pode-se usar subdivisão adaptativa para
controle de erros
– Opção 3: calcula o comprimento do arco de forma
analítica
• Não é possível para vários tipos de curvas
9
Movimento ao longo de uma curva
• Subdivisão adaptativa
Movimento ao longo de uma curva
•
Cálculo do comprimento do arco
•
Função de interpolação
•
Caminho do objecto
•
Movimento ao longo de uma curva
P(u) = au3 + bu2 + cu + d
– curva no espaço
– Definido por um polinomio do terceiro grau
10
Movimento ao longo de uma curva
• Cálculo do comprimento do arco
– Curva que define o caminho pode ser
uma qualquer (e.g. Bézier)
– Qual a função que relaciona o tempo
com a posição ao longo da curva?
– Dois problemas a resolver:
• Dados dois pontos P(u1) e P(u2),
encontrar a função Length(u1,u2)
• Dado um comprimento de arco s e um
ponto P(u1), encontrar um ponto P(u2)
tal que Length(u1,u2) = s
Movimento ao longo de uma curva
• Cálculo do comprimento do arco
– Passo 1: estabelecer a relação entre
parâmetros (u) e comprimento do arco (s)
• Especificar função s = G(u) que calcule, para cada
u, o comprimento de arco a partir de u0.
• Se inversa G-1 puder ser calculada (ou estimada),
a curva pode ser parametrizada de acordo com o
seu comprimento através de P(G-1(s))
– Passo 2: especificar em quanto tempo uma
dada distância deve ser percorrida
11
Movimento ao longo de uma curva
• Cálculo da velocidade
– Só funciona se a interpolação for
parametrizada relativamente ao comprimento
da curva
– Time-steps constantes significam velocidade
também constante
• s(t) é uma função linear
– Para resultados mais interessantes (e.g.
aceleração/desaceleração), usar time-steps
variáveis.
Movimento ao longo de uma curva
• Cálculo da velocidade
• Função s(t) deve ser contínua e monotónica
• Não devem haver saltos de velocidade (manter
continuidade de primeira ordem C1)
• Pode ser definida de forma gráfica e interactiva
12
Movimento ao longo de uma curva
• Cálculo da velocidade
– Forma automática
• Secção de curva de seno de –π/2 até π/2
• Mapear valores de -1 a 1 no intervalo 0 a 1
Movimento ao longo de uma curva
13
Rotações representadas por
Quaternions
• Usam-se porque:
– São facilmente interpoladas
– Não causam o efeito gimbal lock
– Unidade quaternion = um ponto sobre esfera
unitária
– Interpolação linear directa, (ao contrário dos
outros métodos), gera movimento não-linear
Rotações representadas por
Quaternions
• Representadas no
espaço 4D
• Interpolação linear entre
2 quaternions (espaço
4D) não produz
intervalos regulares na
esfera unitária
• Exemplo análogo
• Interpolação linear entre 2
pontos num círculo 2D
14
Rotações representadas por
Quaternions
• Para obter rotação com
velocidade constante, calcula-se
orientações intermediárias
directamente na superfície da
esfera unitária
– Interpolação entre 2 quaternions
• Um quaternion [s,v] e sua
negação [-s,-v] representam a
mesma orientação.
• Escolher entre quais interpolar
(caminho mais curto)
– q1 e q2 ou
– q1 e - q2
Rotações representadas por
Quaternions
• Como determinar o caminho mais curto?
– Produto escalar (4D) entre os dois quaternions calcula
o coseno do ângulo entre q1 e q2
– Se coseno positivo, caminho mais curto é entre q1 e
q2
– Caso contrário, mais curto é entre q1 e - q2
– Fórmula para interpolação linear esférica entre dois
quaternions, considerando u entre 0 a 1 corresponde a
15
Rotações representadas por
Quaternions
• Problemas podem persistir:
– Ao interpolar vários pares de quaternions, a
continuidade C2 e suavidade do movimento
não é garantida
– Solução: usar interpolação cúbica de Bézier
entre os vários quaternions
Seguir Caminhos
• Seguir um caminho requer mais do que
interpolação ao longo de uma curva
• A orientação do objecto ao longo do caminho
também deve ser considerada
– Ex: objecto = câmara virtual
• Eventualmente, o caminho precisa ser suavizado
– Ex: Controlo interactivo do movimento
• Por vezes: percorrer caminho sobre um outro
objecto
16
Orientação ao longo de Caminho
• Define-se um sistema
de referência (u,v,w)
centrado em um
ponto ao longo do
caminho
• w e v são definidos e
u é calculado
• O sistema de
referência (u,v,w) é
móvel
Suavização de Caminho
• Vários métodos
• Interpolação linear
dos valores
adjacentes
• Aplicações repetidas do
método tendem a reduzir
concavidades
17
Suavização de Caminho
• Ainda outros métodos
– Interpolação cúbica dos valores adjacentes
(curva parabólica)
– Suavização por núcleos de convolução
– Suavização por aproximação B-spline
Caminho ao longo de Superfície
• Dados os pontos inicial e final do caminho
encontrar os pontos intermédios
• Custo computacional para achar o melhor
caminho é elevado
• Existem alternativas para encontrar
caminhos sub-optimais:
– Determinar o plano que contém o ponto de
partida e o ponto de chegada e que é
perpendicular à superfície
– A intersecção desse plano com os vários patchs
da superfície define os pontos do caminho
18
Sistemas Key-frame
Sistemas Key-frame
• O termo key-frame vem da animação tradicional
• Foi generalizado para animação por computador
– Aplicado a cada variável cujo valor é definido num frame (quadro)
específico, que deve ser interpolado de acordo com um
procedimento dado
– Também conhecidas como articulation variables (avars)
• Sistemas key-frame são também designados track based
• Possível especificar interactivamente os dados
19
Sistemas Key-frame
Sistemas Key-frame
• C(t) obtida através de técnicas de surface patch
• Técnicas relativas a uma dimensão superior em 1
20