Curvas Paramétricas em 2D

4 Curvas Paramétricas

Curvas Paramétricas

Neste capítulo vamos abordar o desenho de curvas com naturalidade e eficiência. Para isso veremos um pouco da história do desenvolvimento de métodos cálculo e plotagem de curvas e depois os principais modelos de curvas paramétricas utilizados em Computação Gráfica. Por fim veremos uma técnica de desenho eficiente de curvas paramétricas baseada unicamente em somas e também como realizar o recorte de curvas. Todo o capítulo é voltado para 2D, mas os métodos são apresentados de forma genérica e podem ser diertamente aplicados ao caso 3D.

Curvas

Para prover realismo e exatidão é necessária a representação de curvas de forma:

  • fiel aos dados originais;
  • rápida e eficiente;

Para isso deve ser possível:

  • determinar-se a qualquer momento posição no espaço de qualquer ponto em uma curva;
  • uma representação compacta;
  • realização de zoom eficiente.

Isto é muito custoso através de representações geométricas tradicionais.

Não podemos sempre representar todos os pontos que necessitamos. Para isso é necessária a utilização de Representações Paramétricas de Curvas, onde com poucos parâmetros e um algoritmo eficiente podemos gerar uma curva com as características desejadas.

Uma superfície curva: Para desenhá-la de forma eficiente os “retalhos” que a formam devem poder ser calculados por um algoritmo a partir de um conjunto de parâmetros.
Curvas Paramétricas em 2D

A representação de curvas mais usada em CG foi descoberta independentemente por Pierre Bézier, engenheiro da Renault e Paul de Casteljau, engenheiro da Citroën.

Ambos os engenheiros desenvolveram um esquema de plotagem de curvas que possui ao mesmo tempo raízes paramétricas e analíticas:

  • Os valores dos parâmetros são pontos no espaço;
  • Estes pontos são ligados através de polinômios.

O trabalho de de Casteljau foi pouco anterior ao de Bézier, mas nunca foi publicado. O modelo leva o nome de Bézier. O algoritmo básico para desenho foi inventado por Casteljau.

Subdivisão de curvas usando Dividir-para-Conquistar: O Algoritmo de de Casteljau

Vamos construir uma curva pelo método desenvolvido por de Casteljau através de divisões sucessivas See Situação inicial:

    • Nesta curva P0 e P2 definem os extremos;
    • P1 atua como um parâmetro de curvatura ou “ponto de controle”.
Situação Inicial.
  • Recursivamente dividimos e criamos a curva.

Próximo passo: Seja P1(1) o ponto médio do segmento P0P1:

Fazemos P1(1) o ponto médio do segmento P0P1.

Agora fazemos P2(1) ser o ponto médio do segmento P1P2. Dessa forma dividimos cada um dos dois segmentos ao meio See Fazemos P2(1) o ponto médio do segmento P1P2.

Fazemos P2(1) o ponto médio do segmento P1P2.

Seja agora o ponto P2(2) o ponto médio do segmento P1(1) P2(1) See Fazemos P2(2) o ponto médio do segmento P1(1) P2(1)...

Fazemos P2(2) o ponto médio do segmento P1(1) P2(1).

Assim criamos um novo ponto. Pelo algoritmo de de Casteljau este ponto estará sobre a curva.

Agora podemos utilizar dois novos conjuntos de pontos como novos pontos de controle para continuar subdividindo a nossa “curva” de forma hierárquica: [ P0, P1(1) e P2(2) ] e [ P2(2) P2(1) e P2 ]. Recursivamente recriamos o problema com mais três novos pontos, fazendo primeiro [ P0, P1(1) e P2(2) ] serem P0 , P1 e P2 e reaplicando o método See Criamos uma nova sub-curva à esquerda, a qual começaremos a subdividir.:.

Criamos uma nova sub-curva à esquerda, a qual começaremos a subdividir.

Seja o novo P1(1) o ponto médio do segmento que rebatizamos de P0P1.See Subdividir à esquerda.

Subdividir à esquerda.

Seja o novo P2(1) o ponto médio do segmento que rebatizamos de P1P2.See Subdividir à direita do segmento esquerdo.

Subdividir à direita do segmento esquerdo.

Seja agora um novo ponto P2(2) o ponto médio do segmento P1(1) P2(1) dessa subcurva esquerda See Fazemos P2(2) o ponto médio do novo segmento P1(1) P2(1)...

Fazemos P2(2) o ponto médio do novo segmento P1(1) P2(1).

Esta seqüência demonstra o processo para a subárvore esquerda1. O processo é o mesmo para o outro lado. Demonstraremos a seguir apenas a seqüência de operações, dispensando explicações..

Fazemos P2(2) o ponto médio do novo segmento P1(1) P2(1).

Quando decidimos terminar, podemos plotar a curva desejada. A condição de término é a profundidade da árvore de chamadas recursivas e é definida pelo usuário/programador. É a condição de término que determina a qualidade da curva.

Vantagens:
  • Precisão ilimitada;
  • Suporte a efeitos de Zoom;
Desvantagens:
  • Muitos cálculos de pontos médios;
  • Recursão: Consumo de muita memória;
  • Muito custoso realizar desenho incremental partindo-se de um ponto inicial;
  • Impossível determinar a posição de um ponto a uma dada distância do início sem desenhar toda a curva;
Curvas Cúbicas Paramétricas em 2D

Antes de discutirmos algum tipo de curva cúbica paramétrica específica, vamos dar uma olhada em alguns princípios matemáticos básicos das curvas cúbicas na sua representação paramétrica.

A forma geral de representação de um ponto em uma curva paramétrica é:

A fórmula geral de uma Curva Cúbica na Forma Paramétrica:

As derivadas com relação a t são todas iguais. Aqui a derivada de x em relação a t:

As três derivadas formam o vetor tangente. As inclinações da curva são funções das componentes tangentes:

Com estas definições em mente, podemos passar a ver as curvas específicas usadas em CG.

Curva de Hermite

A curva de Hermite é determinada por dois pontos finais P1 e P4 e suas tangentes R1 e R4. A partir daí queremos encontrar os coeficientes a(x,y,z),b(x,y,z),c(x,y,z) e d(x,y,z) tais que:

Várias curvas de Hermite. Observe-se os vetores R1 e R4, que são responsáveis pela curvatura.

Reescrevendo matricialmente x(t) temos:

Reescrevendo o vetor coluna dos coeficientes como Cx:

Reescrevendo o vetor linha das potências de t como T:

Podemos expressar as condições da Eq. 5.5 (para x) usando a Eq. 5.7:

Para expressar as condições para os vetores tangentes, diferenciamos 5.7 em relação a t:

Assim:

Dessa forma, agora as condições em 5.9 e 5.11 podem ser expressas em uma única equação matricial:

Invertendo a matriz 4×4 atingimos o objetivo de calcular Cx:

Onde MH é a Matriz de Hermite e GH é o vetor de geometria. Desta forma obtemos:

Substituindo na forma geral de representação de um ponto em uma curva paramétrica:

Dessa forma podemos calcular qualquer ponto entre P1 e P4 em uma curva dada pelos vetores tangentes R1 e R4. Como? Se tomamos o produto TMH temos:

Multiplicando See por GHx obtemos:

As quatro funções de t no produto TMH são chamadas de funções de suavização ou blending functions.

Continuidade de Curvas de Hermite Subseqüentes

É possível ligar-se facilmente várias curvas de Hermite para obter uma forma mais complexa, basta que algumas poucas condições estejam satisfeitas para que se obtenha um efeito bastante natural.

Para obter-se continuidade de primeira derivada (continuidade de tangência) C(1) em P devemos modelar curvas de Hermite subsequentes da seguinte forma:

A repetição do primeiro ponto de controle e da direção do vetor de direção garante a continuidade de primeira derivada de várias curvas interligadas.

Continuidade C(1): Curvas de Hermite possuem continuidade de primeira derivada se os vetores final de uma e inicial da seguinte forem colineare e de mesma direçãos.
Continuidade de Curvas Interligadas
  • Para conseguirmos modelar a estrutura curva que desejamos através de cúbicas, necessitamos utilizar várias curvas interligadas:
  • para obter um efeito de realismo essas curvas têm de ser contínuas;
  • existem vários graus de continuidade;
  • Designamos os graus de continuidade como C(grau) (continuidade analítica) ou G(grau) (continuidade geométrica). A seguir veremos alguns exemplos. Mais tarde, ao apresentarmos as próximas formas de curva, discutiremos em que condições qual grau de continuidade pode ser alcançado.
Continuidade C(0) (direta) ou continuidade G(0) (geométrica)
    • São:
    • curvas que se tocam fisicamente;
    • descontínuas sob qquer outro ponto de vista
Um polígono é um objeto com continuidades direta e geométrica.
Continuidade C(1)
  • Existe em curvas que possuem vetores tangentes idênticos no ponto de interpolação onde se tocam. Estes vetores são idênticos tanto em direção como em magnitude.
Continuidade G(1)
    • As curvas necessitam possuir apenas vetores tangentes de mesma direção no ponto de interpolação onde se tocam.
    • As magnitudes podem ser diferentes, ocasionando curvaturas diferentes antes e depois da junção
A Continuidade C(1) não produz necessariamente curvas realistas.
Continuidade C(2):
    • Os pontos finais das curvas encontram-se e as curvas possuem vetores tangentes exatamente idênticos no ponto de interpolação onde se tocam, tanto em direção como em magnitude.
    • Além disso, a segunda derivada de ambas as curvas no ponto de interpolação também é idêntica. Esta condição é importante para o efeito de realismo a ser provido pela curva.
Esta curva parece bastante “natural”, sendo porém a parte direita difícil de ser distingüida a olho nu da curva 5.14b, da figura anterior. Na parte esquerda vemos que aqui o ângulo abrupto se comporta de tal forma que o efeito é agradável, apesar de ser bastante fechado.
Curva de Bézier

A curva desenvolvida por Bézier em 1972 é similar ao modelo de Hermite, mas difere na definição dos vetores tangentes dos pontos extremos.

O modelo de Bézier utiliza 4 pontos (P1 a P4), dois extremos e dois de controle internos. As tangentes são definidas pelos segmentos P1P2 e P3P4.

As tangentes de Hermite possuem a seguinte relação com os pontos de Bézier:

Relação entre forma das curvas e posição dos pontos de controle.

A relação entre a matriz de geometria de Hermite GH e a matriz de geometria de Bézier GB é:

Substituindo na See obtemos:

E, definindo o produto MHMHB em Eq.5.21 como MB, temos que x(t) = TMBGBx. A matriz MB obtida do produto MHMHB é:

Podemos desenhar uma curva com as propriedades da Curva de Bézier através do Algoritmo de de Casteljau, se quisermos…

As blending functions para Bézier podem ser calculadas da mesma forma que foram em See e See para Hermite.

Condição de continuidade C(1) está garantida quando:

  • Duas curvas adjacentes [P1 a P4] e [P4 a P7] compartilham P4
  • P3P4= kP4 P5
B-splines Uniformes

O termo Spline remonta às longas tiras de aço flexíveis utilizadas antigamente na construção naval para determinar a forma do casco dos navios.

As splines eram deformadas através de pesos chamados “Ducks”, que eram atados a estas em posições determinadas para deformá-las em várias direções da forma desejada.

As splines, a não ser que puxadas de forma muito extrema, possuíam a propriedade de manterem continuidade de segunda ordem.

O equivalente matemático dessas tiras, as splines cúbicas naturais, são portanto curvas polinomiais cúbicas com continuidades C0, C1 e C2, que passam através dos pontos de controle. Em função disso, as splines, por possuírem um grau de continuidade a mais que a continuidade inerente às curvas de Bézier e de Hermite, são consideradas mais suaves como elementos de interpolação.

Os coeficientes polinomiais das splines cúbicas naturais, no entanto, são dependentes de todos os n pontos de controle. Isto implica em inversões de matrizes n+1 por n+1, que devem ser repetidas toda vez que um ponto de controle é movido, pois cada ponto afeta toda a curva. Isto é computacionalmente desinteressante.

B-splines são segmentos de curva cujo comportamento depende de apenas uns poucos pontos de controle.

As b-splines são tratadas de forma um pouco diferente das curvas de Bézier ou Hermite:

Nas curvas anteriores, a únicas interdependência que existia, era que para conseguir continuidade C1, repetíamos um ponto e garantíamos a colinearidade do segmento de reta formado pelos pontos de controle na junção.

As b-splines são curvas com muitos pontos de controle, mas que são tratadas como uma seqüência de segmentos de ordem cúbica.

Assim: Uma b-spline com P0 … Pm pontos de controle, onde m >= 3, é formada por m – 2 segmentos cúbicos.

Denotamos estes segmentos por Q3 a Qm.

Cada um dos m – 2 segmentos de curva de uma b-spline é definido por quatro dos m + 1 pontos de controle.

Segmento Qm é definido pelos pontos Pm – 3, Pm – 2, Pm – 1 e Pm.

Conjunto de 3 splines em seqüência, todas sobre a mesma reta.

O vetor de geometria b-spline GBSi para aproximar o segmento Qi, que inicia próximo de Pi – 2 e termina próximo de Pi – 1 é:

Esta matriz será recalculada e usada, no caso de b-spline, para interpolar cada um dos segmentos definidos por um par de pontos Pi – 2, Pi – 1. Assim, a formulação de um segmento i de b-spline fica:

…onde a matriz-b-spline-base, que relaciona o vetor de geometria às blending functions e os coeficientes polinomiais é:

As blending functions podem ser calculadas similarmente a Bézier e Hermite.

Splines com um ponto de controle fora da reta.
Comentários
Splines semifechadas e fechadas: Se repetimos um ponto (a) e se repetimos dois pontos (b).
Propriedade do Casco Convexo em Splines.
Complexidade

A geração de curvas utilizando as blending functions possue 3 grandes vantagens sobre o método global hierárquico usando divide-and-conquer proposto por de Casteljau:

  • incremental: posso ir gerando a curva até onde quero. Por de Casteljau eu tinha de gerar a curva toda e ir refinando.
  • acurácia e passo variáveis: defino um passo t = 1/k e gero a curva como um conjunto de k-1 polígonos
  • resolve o problema do clipping: verifico se o fim do próximo segmento t/k está dentro do window usando clipping de pontos.

Desvantagem:

  • para cada passo t, tenho de calcular T = [t3 t2 t 1], o que é computacionalmente caro.
Otimização do Desenho: Clipping
  • Posso realizar a clipagem de uma forma muito simples: vou desenhando a curva com passo t/k.

A cada ponto gerado, verifico se está dentro da janela. Se estiver, desenho o segmento de reta. Se não estiver, executo clipping de segmento de reta para ver onde cortei.

Para situações onde existe a possibilidade de uma curva sair e entrar de novo na janela, posso usar pesquisa binária, começando dos dois extremos da curva, para determinar onde entra e onde sai.

A figura a seguir ilustra o procedimento mais simples, sem a utilização da pesquisa binária.

Como fazer o clipping de uma curva…
Desenhando Curvas de Forma Eficiente

Existem duas maneiras básica de se desenhar curvas cúbicas paramétricas:

  • Através do cálculo iterativo de x(t), y(t) e z(t) para valores de t incrmentais, plotando-se os pontos calculados e ligando-se estes através de retas, como mostrado na See Como fazer o clipping de uma curva… Possui a desvantagem de se ter de calcular o valor das blending functions para cada passo e, por conseguinte, os valores de t3 e t2;
  • Através da subdivisão recursiva pelo método de divisão do ponto médio visto no início. As desvantagens deste método já forma discutidas.

Uma terceira forma muito mais eficiente de se repetidamente calcular o valor de um polinômio é através das forward differences.

Forward Differences
    • A forward difference


de uma função f(t) é dada por:

que pode ser reescrita da seguinte forma:

se reescrevermos isto em termos iterativos, teremos:

onde n é calculado para intervalos iguais de tamanho
δ, de forma que tn = n δ e fn = f(tn).

Para um polinômio de terceiro grau:

A forward difference fica então:

Dessa forma, vemos que é um polinômio de segundo grau. Isto é ruim, porque para calcular a See , temos de calcular e uma adição.

Mas podemos aplicar forward differences a também. Isto simplifica seu cálculo. Podemos escrever:

Aplicando isto à Eq. 5.30, temos:

o que é uma equação de primeira ordem em t.

Reescrevendo 5.31 usando o índice n, obtemos:

Se reorganizarmos a equação, substituindo n por n – 1, temos:

Agora, para calcular  para usar na Eq.5.28, nós calculamos  e adicionamos o resultado a  . Uma vez que  é linear em t, isto é muito menos trabalho do que calcular  diretamente a partir do polinômio de segundo grau.

Este processo é repetido mais uma vez para evitar o cálculo direto de See . para acharmos :

Como a terceira forward difference é uma constante, não é necessário levar este processo adiante, pois a equação não é diferenciável além da terceira derivada. Reescrevendo a See usando o iterador n e  como uma constante, temos:

Se agora substituirmos n por n-2, completamos o desenvolvimento necessário da equação:

Este resultado pode então ser usado na See para calcular , que por usa vez pode então ser usado na See para calcular f
n+1
.

Para se utilizar as forward differences em um algoritmo que itera de n=0 até nδ=1, nós computamos as condições iniciais com See , See , See e See para t=0. Estas condições são:

Pode-se determinar as condições iniciais através do cálculo direto das equações. Chamando de D o vetor das diferenças iniciais, temos:

Com base nessa representação, o algoritmo para plotar uma curva através da utilização de forward differences é apresentado abaixo.

Como eu calculo os coeficientes a,b,c e d ?

A técnica das forward differences exige que se possua n, x,
Δx, Δ2x, Δ3x, y,Δy,Δ2y,Δ3y, z,Δz,Δ2z eΔ3z para o primeiro ponto da curva como valores iniciais para a primeira iteração. Como estes valores surgem durante o processo iterativo é fácil de perceber: surgem da iteração anterior, mas como fazemos para calcular estes valores para a primeira iteração?

Para calcular estes valores, eu só preciso jogar os valores dos coeficientes constantes a, b, c e d na See e assim obtenho os deltas que preciso para iniciar o processo iterativo. De onde surgem estas constantes ?

Para entendermos de onde surgem, basta recapitularmos o que vimos no início deste capítulo: Lembremos que a forma geral de representação de um ponto em uma curva paramétrica é dada pela See Daí construímos a fórmula geral da curva paramétrica, dada pela See . Se observarmos este sistema de equações, vamos ver ali os coeficientes a, b, c e d que precisamos para o nosso cálculo inicial. São os coeficientes da curva paramétrica!

Estes coeficientes são constantes no correr de uma curva e somente precisam ser calculados uma vez, para toda ela.

Para fazer isso, reescrevemos matricialmente estas equações e representamos os coeficientes através da matriz dos coeficientes, como na See . Agora só temos de encontrar uma forma de isolá-los em uma equação onde conheçamos os outros dados.

Para tanto seguimos o caminho desenvolvido anteriormente, até chegarmos à equação matricial para uma forma de curva paramétrica, como para Hermite, mostrada na See , repetida abaixo para a coordenada x.

Invertendo a matriz 4×4 atingimos o objetivo de calcular Cx:

O mesmo processo temos de fazer para os eixos y e z. Esta possibilidade provavelmente não havia chamado nossa atenção antes, pois se usarmos as blending functions não precisamos explicitamente desta equação. Para as forward differences vamos ter de calcular explicitamente Cx, Cy e Cz para podermos calcular os valores iniciais dos deltas para o algoritmos iterativo.

Agora ficou fácil. Para aplicarmos este método para as outras curvas só temos de considerar o seguinte:

Hermite

Cx(Hermite) = MH . GxH

Cy(Hermite) = MH . GyH

Cz(Hermite) = MH . GzH

Bèzier

C(Bèzier) = MB. GB com GB matriz de geometria para x,y e z

Spline

C(b-Spline) = MBS. GBS com GBS matriz de geometria para x,y e z

Exercício 1.4: Implementando Curvas em 2D
1.4a: Blending Functions

Implemente a curva de Hermite, Spline ou Bézier como mais um objeto gráfico de seu sistema. Utilize as blending functions como método de cálculo. Um objeto Curva2D poderá conter uma ou mais curvas com continuidade no mínimo G(0). Crie uma interface para entrar com estes dados. Implemente a clipagem para esta curva utilizando o método descrito anteriormente.

Possível forma de implementar a janela para entrada de dados para um objeto do tipo Curva. Este exemplo já mostra a janela prevendo objetos-curva em 3D e oferece possibilidade de entrada da coordenada z. A barra de rolagem ao lado permite rolar a interface e incluir tantos pontos quantos se desejar no caso de B-Splines.
1.4b: Forward Differences

Implemente no seu programa gráfico b-splines utilizando Forward Differences. Deve ser possível ao usuário definir uma curva com quantos pontos de controle desejar, entrando simplesmente com uma lista de pontos, desde que tenhamos n > 3.


1.Falamos de subárvore porque este método é evidentemente um método recursivo e a sua execução gerará uma árvore de chamadas como qualquer outro algoritmo usando a filosofia divide-and-conquer (vide por exemplo o algoritmo do método de ordenação Quicksort).

 

Sobre o Autor