UNIVERSIDADE ESTADUAL DO NORTE FLUMINENSE DARCY RIBEIRO CENTRO DE CIÊNCIA E TECNOLOGIA LABORATÓRIO DE CIÊNCIAS MATEMÁTICAS MANIPULAÇÃO DIRETA DE CURVAS Emildo Mothé Ribeiro Filho Campos dos Goytacazes 14 de Setembro de 2006 AUTOR Emildo Mothé Ribeiro Filho ORIENTADOR Luis Antonio Rivera Escriba CO-ORIENTADOR Luiz Humberto Guillermo Felipe PARCERIA Leandro Moraes Valle Cruz 2 ÍNDICE 1 Introdução.................................................................................................. 4 2 Curvas paramétricas................................................................................. 5 3 4 2.1 Curvas de Bezier................................................................................... 6 2.2 Curvas B-Splines .................................................................................. 9 Livre manipulação direta de curvas ...................................................... 11 3.1 Manipulação de Curvas de Bezier ...................................................... 12 3.2 Manipulando Curvas B-Spline............................................................. 15 Manipulação direta com restrições ....................................................... 17 4.1 Uma restrição...................................................................................... 20 4.2 Dupla restrição .................................................................................... 21 4.3 Tripla restrição .................................................................................... 22 5 Resultados experimentais ...................................................................... 23 6 Conclusões .............................................................................................. 25 1 3 1 Introdução A modelagem de curvas e superfícies é bastante usada nos designes assistidos por computador (CAD – Computer Aided Design) para propósitos industriais, arquiteturas, manufaturas, educacionais e entretenimentos. Muitas vezes se devem construir contornos de objetos a partir de pontos distribuídos no plano, dando uma aproximação a um objeto desejado. As curvas B-Splines permitem uma reconstrução de contornos dos objetos com características suaves, e são bem comportados na manipulação de segmentos após sua definição inicial. Os sistemas de modelagem geométrica possuem mecanismos de interação direta que permita gerar objetos de forma desejada. Uma forma de interação direta é a manipulação direta, que consiste em capturar com o mouse um ponto da curva e arrastar até uma outra posição, de forma a gerar uma deformação do segmento do objeto. Os efeitos das deformações podem ser controlados impondo restrições nas propriedades variacionais, como tangencial, curvatura, em particular em curvas paramétricas. Com a técnica de manipulação direta em curvas B-Splines, os vértices de controle são deslocados automaticamente de forma a gerar uma deformação desejada, dependendo das restrições impostas ao ponto arrastado com o mouse. Neste trabalho, abordamos modelagem de curvas B-Splines cúbicas com manipulação direta com restrições variacionais. Este trabalho está organizado de forma que primeiro, vamos introduzir alguns conceitos de Curvas paramétricas na Seção 2 e nossa ênfase nas curvas de Bézier e B-Splines. Na Seção 3 trataremos da Manipulação Direta de curvas; na seguinte seção tratamos das restrições na manipulação e por fim na Seção 5 vamos mostrar os resultados experimentais. Concluímos brevemente na Seção 6. 4 2 Curvas paramétricas Existe uma variada gama de aplicações onde há necessidade de se trabalhar com curvas paramétricas. Como no desenvolvimento de objetos de pequeno e grande porte, por exemplo: • Para o desenvolvimento de automóveis, aviões e navios; • Objetos que por conforto ou por questões estéticas tem formas suaves; • Em válvulas hidráulicas onde cantos ou quinas podem reter o fluxo dos fluidos. Os objetos que possuem estas características citadas acima cuja forma é variada e de difícil descrição, são chamadas de objetos de forma livre [1]. Esta representação reduz substancialmente dificuldades como as curvas com laços, passar uma curva suave por determinados pontos entre outros exemplos tornando a representação paramétrica mais adequada. Na representação paramétrica, as curvas são representadas como funções de algum parâmetro, como mostrada na Figura 1. A primeira classe de curvas paramétricas é aquela em que, o comportamento da curva, ao longo do tempo, em relação a cada um dos eixos, é definida por uma equação independente. A forma geral destas curvas pode ser expressa por: x = X (t ) y = Y (t ) um ponto em tal curva é representado pelo vetor: P(t ) = [ X (t ), Y (t )] . O ponto é o elemento básico em modelagem. Sendo definido como um conjunto ordenado de números reais, em geral sua posição no plano. Um vetor 5 pode ser representado da mesma maneira. Para determinarmos o vetor tangente de uma curva paramétrica é bastante simples, deriva-se as equações X (t ) e Y (t ) : P' (t ) = [ X ' (t ), Y ' (t )] Há uma gama de técnicas em que podemos determinar a curva com seus pontos e suas respectivas derivadas, denominada interpolação. Das técnicas envolvendo estas características nos interessa as Curvas de Bezier e as Curvas B-Spline. Figura 1: Parametrização de curva. 2.1 Curvas de Bezier São curvas paramétricas polinomiais de grau n definidas por n + 1 pontos de controle, sendo n > 1 e n ∈ N . Em uma curva de Bezier a determinação de vetores tangentes nos pontos iniciais e finais da curva é bastante simples: o vetor tangente ao ponto inicial é obtido multiplicando-se o vetor definido pelos dois primeiros pontos por n . O vetor do ponto final é obtido de maneira análoga utilizando os dois últimos pontos. 6 Analisando a equação paramétrica da reta entre os pontos P0 e P1 chega-se a conclusão de que se trata de uma média ponderada entre P0 e P1 onde o peso de cada ponto é definido de forma que quando um deles pesa no resultado, menos o outro influencia no mesmo. Para obter esta ponderação os pesos podem ser expressos pelas funções, portanto: P0 = 1 − t ; P1 = t ; Com isso a equação paramétrica da reta fica: P(t ) = (1 − t ) P0 + tP1 . Caso seja preciso ponderar três pontos, denominados P0 , P1 e P2 . gerando uma curva. Consideremos duas retas R1 de P0 a P1 e R2 de P1 a P2 é possível obter uma curva fazendo a ponderação entre R1 e R2 . Sendo R1 e R2 : R1 = (1 − t ) P0 + tP1 R2 = (1 − t ) P1 + tP2 Reaplicando-se a idéia de ponderação tem-se a curva C1 definida pela equação: C1 = (1 − t ) R1 + tR2 C1 = (1 − t )[(1 − t ) P0 + tP1 ] + t[(1 − t ) P1 + tP2 ] C1 = (1 − t ) 2 P0 + 2t (1 − t ) P1 + t 2 P2 A Figura 2 mostra como deve ser a curva de Bezier de 3 pontos, onde pode-se observar que a curva definida por esses três pontos de controle passa 7 pelos pontos extremos. Figura 2: Curva de Bezier com 3 pontos de controle. A obtenção de curvas de Bezier de 4 pontos segue o mesmo raciocínio, ponderando-se duas curvas C1 e C 2 , definidas parametricamente. Então a curva C 3 pode ser expressa por: C 3 = (1 − t )C1 + tC 2 C 3 = (1 − t ) 3 P0 + 3t (1 − t ) 2 P1 + 3t 2 (1 − t ) P2 + t 3 P3 A Figura 4 mostra varias curvas de Bezier de quatro pontos de controle: Figura 3: curvas de Bezier de 4 pontos de controle. 8 As vantagens de se utilizar este tipo de cura é a simplicidade na construção, não exige que se tenha conhecimento dos vetores tangente de partida e chegada durante a definição dos segmentos da curva e a curva interpola o primeiro e o ultimo ponto de cada segmento sendo influenciada pelos outros dois. Em contrapartida as curvas de Bezier não garantem entre dois segmentos consecutivos da curva a menos que os dois últimos pontos do primeiro segmento e os dois primeiros do segundo sejam colineares e não possui a propriedade de controle local. 2.2 Curvas B-Splines O termo Spline refere-se à longa e flexível barra de metal utilizada pelos desenhistas para delinear as superfícies de aviões e navios. A equivalência matemática a estas barras, a spline cúbica natural, é continuidade cúbica polinomial de posição, inclinação e curvatura, que interpolam os pontos de controle. Assim, as splines são mais suaves do que outras formas de modelagem de curvas paramétricas cúbicas [2]. A representação cúbica B-Spline, em geral, não passa por "algum" ponto de controle, mas é contínua e também possui continuidade do vetor tangente (inclinação) e de curvatura (isto é, sua primeira e segunda derivada são contínuas nos pontos extremos). Da mesma maneira que as curvas Bezier, as curvas B-Spline são curvas paramétricas polinomiais de grau três (ou maior) definidas por 4 pontos de controle (quanto maior o número de pontos de controle, maior o grau do polinômio). Em geral, constroem-se representações compostas utilizando-se BSplines cúbicas. É importante ressaltar que para aproximar os pontos de controle P1 , P2 , ..., Pn por uma série de B-Splines, utiliza-se uma matriz geometrica entre cada 9 "par" de pontos adjacentes. A aproximação do próximo Pi para o próximo Pi +1 utiliza: Pi −1 P i i G = , 2≤i≤ n−2 Pi +1 Pi + 2 A figura a seguir apresenta um exemplo de uma curva B-Spline. Figura 4: Curva B-Spline As vantagens de se utilizar este tipo de curva são: • Simplicidade de construção; • Continuidade paramétrica C² garantida entre os segmentos de curva; • Possui a propriedade de controle local. As desvantagens são: • Não interpola nenhum dos 4 pontos de controle. • As extremidades não pertencem aos pontos de controle inicial e final 10 3 Livre manipulação direta de curvas Uma curva paramétrica anteriormente definida como P(t ) para t ∈ U ⊂ R , podemos deforma-la arrastando um ponto da curva, denominado P(t a ) , até uma posição desejada. A curva que antes era P(t ) se ajusta a deformação de P(t a ) construindo uma nova curva denominada P ′(t ) , para o mesmo domínio U. Esta técnica de construção, descrita acima, de modelagem de curvas, chama-se livre manipulação direta, porque descarta restrições de outras propriedades da curva. A Figura 5 mostra como se obtêm uma geometria desejada através da uma seqüência de manipulação direta a partir de uma geometria inicial. Figura 5: Seqüência de variações de curva usando manipulação direta. Para conseguirmos deformar uma curva paramétrica utilizamos vértices de controle, que a partir deles é desenhada a curva. Sendo ideal o reposicionamento automático e adequado dos vértices de controle de acordo com o ponto da curva deslocado. 11 3.1 Manipulação de Curvas de Bezier Dada uma equação de Bezier C (t ) = ( x(t ), y (t )) , para 0 ≤ t ≤ 1 . Sejam n vértices de controle V0 ,..., Vn −1 . Então a curva é dada pela equação: d Bi , n = (1 − t ) d −i u i i onde a i-esima função da base de Bezier de grau d , que abreviamos por Bi quando d está claro no contexto. A manipulação direta consiste em selecionar um ponto p = ( x, y ) sobre a curva e desloca-la para uma outra posição p ′ = ( x' , y ' ) , de forma que a curva se altere e passe por p ' (t ) a transformando em uma nova curva, para o mesmo parâmetro t . Insto é C ' (t ) = ( x' , y ' ) , de forma que C ' (t ) = C (t ) + ∆C (t ) , e ∆C (t ) como a deformação. Então a curva de Bezier cúbica pode ser escrita como: p + ∆p = (V0 + ∆V0 ) B0,3 + (V1 + ∆V1 ) B1,3 + (V2 + ∆V2 ) B2,3 + (V3 + ∆V3 ) B3,3 . Da equação bidimensional acima temos a variação ∆xi e ∆y i que se ∆xi = ∆x e ∆y i = ∆y o efeito seria translação da curva, enquanto se cada ∆xi e ∆y i variar proporcionalmente a ∆x e ∆y teremos a deformação da curva, como mostrado abaixo na Figura 6. Figura 6`: Traslação e deformação da curva. 12 3.1.1 Deformação de Curvas de Bezier Se p é um ponto da curva C (t ) , então existe um segundo C i (t ) que contem o ponto p tal que P(t ) = p , para 0 ≤ t ≤ 1 . A Figura 7 mostra a variação de um segmento da curva e o deslocamento de um ponto. Figura 7: Variação de um segmento de curva Se p se desloca em ∆p , então os quatro vértices de controle V = [V0 V1 V2 V3 ] vão se reposicionar para permitir a deformação de C (t ) passando por p + ∆p , satisfazendo a condição: V0 + ∆V0 ∆V0 V + ∆V ∆V 1 1 1 p' = p + ∆p = [ B0 B1 B2 B3 ] , que implica ∆p = [ B0 B1 B2 B3 ] . V2 + ∆V2 ∆V2 V3 + ∆V3 ∆V3 dessa expressão computar-se cada variação dos vértices de controle ∆Vi porque são conhecidos B j e ∆p . 13 Para resolver esta equação é usada a transformada de House-holder [3] que relaciona os elementos da ultima equação com a expressão matricial da forma: H=I− 1 T ω ω π Onde ω = [( B0 + σ ) B1 B2 B3 ] B0 = σ ( B0 + σ ) 2 σ = SIG ( B0 ) B01 + B12 + B22 + B 3 A matriz H é ortogonal com a propriedade [ B0 B1 B2 B3 ]H = [−σ 000] . Isso permite expressar a inversa da matriz H como a sua transposta H T por tanto, HH T = I . Com essa expressão, temos: ∆V0 ∆V 1 ∆p = [ B0 B1 B2 B3 ]HH T ∆V2 ∆V3 considerando [∆ V 0 ∆ V 1 ∆ V 2 ∆ V 3 ] = H [e 0 e 1 e 2 e 3 ] , e substituindo nas T equações acima: ∆p = [− σ 0 0 0] e0 e 1 e 2 e3 Resolvendo essa equação obtemos e0 = − ∆p / σ . Os valores de e1 , e2 e e3 não necessariamente são zeros. Mas considerando que ei é proporcional em 14 comprimento a ∆Vi , e se desejar que ∆Vi seja mínima, então se conclui que e1 = e2 = e3 = 0 . Por tanto, a expressão [e0 e1 e2 e3 ] = H T [∆V0 ∆V1 ∆V2 ∆V3 ] T T pode ser re-escrita como − ∆p / σ ∆V0 B0 + σ ∆V B 1 = I − 1 1 [( B0 + σ ) B1 B2 B3 ] 0 σ ( B0 +σ ) 0 ∆V2 B2 V B ∆ 3 3 0 ∆V0 ∆V ∆p 1 = 2 2 ∆V2 B0 + B1 + B22 + B32 ∆V3 B0 B 1 B2 B3 que é equivalente a [ ∆V = ∆p B T (u )(B(u ) B T (u ) ) −1 ] para ∆V = [∆V0 ∆V1∆V2 ∆V3 ] e B = [B0 B1 B2 B3 ] . T T Observa-se que o reposicionamento adequado dos quatro vértices de controle geradores do segmento da curva que contem o ponto deslocado permite deformar adequadamente a curva. De fato, o deslocamento de pontos dos segmentos extremos permitira o reposicionamento de unicamente três vértices geradores do segmento, porque só esses vértices geram o último segmento da curva. 3.2 Manipulando Curvas B-Spline Dado um segmento de curva B-Spline cúbica S i (t ) , definida por 15 ∆ Vi −1 ∆V S i (t ) = [ N i −1, 4 N i , 4 N i +1, 4 N i + 2 , 4 ] i , t ≤ t ≤ t , i +1 ∆ Vi +1 i ∆ Vi + 2 para bases N j , 4 (t ) ≠ 0 definidos sobre os nós t j − 2 ≤ t ≤ t j + 2 , segundo ilustrado na Figura 8. t t t t t t t t t Figura 8: Bases de curvas B-Splines cúbicas Equivalente em notação matricial é S i (t ) = Bi ( (t )ViT , onde Bi (t ) = [ N i −1, 4 N i , 4 N i +1, 4 N i + 2 , 4 ] . Com isto, se o ponto P(t ) varia em ∆P(t ) , os quatro vértices de controle do segmento S (t ) vão reposicionar-se experimentando comprimentos de variações mínimas, similar a variação de Bezier, como ∆V0 ∆V ∆P(t ) 1 = 2 ∆V2 B0 + B12 + B22 + B32 ∆V3 B0 B 1 B2 B3 onde Bi são as bases B-spline N i , 4 . A Figura 9 é uma curva B-spline cúbica composta de nove segmentos e doze vértices de controle, deslocando um ponto extremo da curva e suas respectivas deformações dos vértices de controle e a deformação esperada da 16 curva. Figura 9: Curva B-spline Se um segmento de curva cúbico Si é gerado por quatro vértices de controle [Vi −1ViVi +1Vi + 2 ] , o reposicionamento dos quatro vértices de controle. A raiz de deslocamento de um ponto P(t ) em ∆P , também gera a variação dos seis segmentos adjacentes. Sendo, um total de sete segmentos deformados. Em geral, o deslocamento de um ponto de um segmento de uma curva de ordem k , afeta a variação de 2k − 1 segmentos adjacentes. 4 Manipulação direta com restrições Pode-se manipular segmentos de curva em função de suas características. Sendo da escolha as opções de variação da curvatura, tangente e posição; também podendo variar em conjunto. Esses três elementos associados a um ponto de uma curva cúbica, podem ser generalizados para curvas de grau m , em geral, como as derivadas de ordem r , para 0 ≤ r ≤ m . Então as restrições impostas sobre um ponto da curva são associadas às derivadas. Assim, para m = 3 , as derivadas da curva S (t ) 17 podem ser expressas como S ( r ) (t ) , para r = 0,1,2 . Sendo as restrições associadas a: • Posição: S ( 0 ) (t ) ; • Tangente: S (1) (t ) ; • Curvatura: S ( 2 ) (t ) ; ou, outras propriedades associadas a derivadas superiores, caso a curva for derivável de ordem r > 2 . A Figura 10 ilustra manipulação de uma das propriedades mencionadas. Figura 10: Deformação da curva por manipulação direta: (a) posição; (b) tangente; (c) curvatura; (d) posição, tangente e curvatura. Em geral um segmento de curva paramétrica de grau m é definida por 18 V0 S (t ) = [B0 (t ) Λ Bm (t )] Μ Vm cuja derivada k , para k = 0,..., m − 1 , é dada por S (k ) [ (t ) = B (k ) 0 (t ) Λ B (k ) m V0 (t ) Μ . Vm ] Considere a expressão anterior, em notação vetorial como S ( k ) (t ) = B ( k ) (t ) ∆V aplicando as variações de suas características no ponto P(t ) , tem-se P ( k ) (t ) + ∆P ( k ) (t ) = B ( k ) (t )(V + ∆V ) O que significa que a variação da propriedade k da curva no ponto P(t ) depende unicamente da variação da posição dos vértices de controle respectivos. A solução da variação implica no adequamento e reposicionamento dos vértices de controle. Relacionando a variação de uma propriedade com a livre manipulação direta. Portanto: ( ( ) ) (B ) ∆V = ∆p ( k ) (t ) B ( k ) B ( k ) T −1 (k ) T Esta expressão resolve a variação de uma única propriedade, por vez, da curva no ponto P(t ) . 19 4.1 Uma restrição A curva manipulada com uma restrição, tal o caso de livre manipulação direta, demanda unicamente uma equação linear, pois as outras propriedades não são restringidas a variar. Portanto, a solução da variação é simplificada para ( ∆V = b0−,10 ∆S ( k ) (t ) B ( k ) (t ) ) T A restrição posicional é quando k = 0 , varia a posição em ∆S ( 0 ) (t ) , deixando livre as outras propriedades. A expressão para esta variação é dada por ( ∆V = b0−,10 ∆S ( 0 ) (t ) B ( 0) (t ) ) A Figura 11(a) ilustra esta operação. A restrição tangencial é quando k = 1 , a tangente varia no ponto em que ∆S (1) (t ) , deixando livre as outras propriedades. Sua expressão é dada por ( ∆V = b0−,10 ∆S (1) (t ) B (1) (t ) ) A Figura 11(b) ilustra esta operação. A restrição de curvatura é logicamente quando k = 2 , como nos casos anteriores, a curvatura varia em ∆S ( 2) (t ) , deixando livre as outras propriedades. A expressão para esta variação é dada por ( ∆V = b0−,10 ∆S ( 2 ) (t ) B ( 2) (t ) ) A Figura 11(c) ilustra esta operação. 20 Figura 11: Deformação por uma restrição 4.2 Dupla restrição A manipulação de um ponto da curva S (t ) com duas propriedades restritas, pode ser modelada mantendo fixa uma das propriedades. A expressão impondo as restrições nas propriedades k0 e k1 é dada por B ( k0 ) T 0 ( k1 ) ∆V = ( k1 ) ∆S B Mantendo fixa a variação posicional e manipulando uma das derivadas ∆S ( k1 ) para k1 = 1,2 é formulada a expressão B (0) T 0 ( k1 ) ∆V = ( k1 ) ∆S B A Figura 12 ilustra o resultado gráfico da operação desta expressão 21 Figura 12: Dupla restrição, com a posição fixa e variando a tangencial e curvatura Outro exemplo nesta categoria é variar a posição em ∆S ( 0) mantendo fixa uma das derivadas ∆S ( k0 ) = 0 para k0 = 1,2 . A expressão correspondente poderia ser da forma B ( k0 ) T 0 ( 0 ) ∆V = ( k1 ) ∆S B A Figura 13 ilustra o resultado gráfico desta operação. Figura 13: Dupla restrição, com a tangente invariante 4.3 Tripla restrição A manipulação de um ponto da curva S (t ) impondo restrições em três propriedades, pode ser modelada mantendo invariante duas propriedades e variando a outra. A expressão com propriedades k0 , k1 e k 2 é dada por 22 B ( k0 ) 0 ( k1 ) T B ∆V = 0 B ( k2 ) ∆S ( k 2 ) A solução específica, a partir da solução geral, considerando as características do vetor ∆S e as facilidades, os elementos de cálculo da matriz B e sua inversa por determinantes , é dada por ∆V T = d −1 B[α 0, 2α1, 2α 2, 2 ] ∆S ( k 2 ) T onde α 0, 2 = b0,1b1, 2 − b1,1b0, 2 α1, 2 = b0,1b0, 2 − b0, 0b1, 2 α 2, 2 = b0, 0b1,1 − b02,1 d = b0 , 2α 0 , 2 + b1, 2α1, 2 + b2 , 2α 2, 2 Figura 14: Exemplos de tripla restrição 5 Resultados experimentais A partir destas técnicas, o desenvolvimento de modelos que executem estas características no computador estão sendo feitas em Linguagem C++ como auxilio das bibliotecas Open GL e FLTK. A implementação de um modelo 23 para curvas está na fase de implementação da interfase e sendo inserido os dois tipos de curvas discutidas acima. Como também na inclusão de restrições tipo, tangencial, curvatura e posicional. A Figura 15 mostra um exemplo da construção do programa, que apresenta duas curvas um em verde e outra azul. A curva verde é a curva original que ao variarmos a tangente modificou-se na curva azul. Em especial, nesta curva a parte me azul é somente a região alterada da curva. Os pontos azuis são os vértices de controle que ao alterarmos a curva se reposicionaram para as posições em marrom modificando automaticamente a curva. Figura 15: Exemplo na execução do programa Nosso objetivo é estender este projeto para curvas no espaço e na implementação de superfícies de Bézier e B-Splines 24 6 Conclusões A manipulação direta, seja ela livre ou restrita, por propriedades geométricas de curvas é uma técnica que permite ao designer em CAD criar objetos baseados em curvas paramétricas realistas, de uma forma intuitiva. Existem ferramentas computacionais comerciais que usam esses princípios de modelagem, mas as pesquisas continuam de forma a estabelecer, cada vez, uma técnica eficiente de modelagem. Referencia bibliográfica [1] Figueiredo, L.H. e Carvalho, P.C. Introdução à Geometria Computacional, Impa, 18º colóquio brasileiro de matemática, 1991, págs. 111. [2] Foley, James D., Computer Graphics: Principles and Practice. New York: Addison Wesley, 1990. [3] Tammeraid, Ivan; Majak, Jüri. http://math.ut.ee/~toomas_l/linalg/ [4] Rivera, L. Manipulação direta em modelagem de curvas e superfícies, UENF, 2006. [5] Fowler, B. Geometric Maniplation of Tensor Product of Surfaces. ACM Proceedings of SIGRAPH´91, 1991, pp. 101-108. 25