Algoritmos de Interseções de Curvas de Bézier com Uma Aplicação à Localização de Raízes de Equações

Rodrigo L.R. Madureira

Programa de Pós-Graduação em Informática, PPGI, UFRJ 21941-590, Cidade Universitária, Ilha do Fundão, Rio de Janeiro, RJ

E-mail: rodrigo.rangel@nce.ufrj.br

Mauro Antonio Rincon Luis Menasche Schechter

Departamento de Ciência da Computação, IM, UFRJ 21941-590, Cidade Universitária, Ilha do Fundão, Rio de Janeiro, RJ

E-mail: rincon@dcc.ufrj.br, luisms@dcc.ufrj.br

Resumo: As curvas de Bézier receberam essa denominação a partir do trabalho do engenheiro francês Pierre Bézier Etienne (1919-1999) com sistemas CADCAM na Renault, no início dos anos 60. Um pouco antes, Paul De Casteljau, um físico e matemático da Citröen, já havia desenvolvido métodos matemáticos equivalentes para essas curvas, muito importantes na área de Computação Gráfica, já que muitos softwares disponíveis no mercado utilizam este conceito [1]. Os principais algoritmos para localizar interseções entre duas curvas de Bézier encontrados na literatura são: Subdivisão Recursiva de De Casteljau, Subdivisão Intervalar adotado por Koparkar e Mudur [4] e Bézier Clipping [2]. A proposta deste trabalho trata do estudo e análise comparativa dos três algoritmos para o cálculo de interseções entre duas curvas de Bézier, seguidos de um estudo de uma aplicação destes algoritmos para o cálculo de raízes reais de funções (não necessariamente polinomiais).

1. Curvas de Bézier 1.1. Definição

Seja n 1≥ um número inteiro. A curva de Bézier de grau n, Qn(t), definida por n + 1 pontos de controle P0, P1, ..., Pn é uma curva definida parametricamente dada por:

nin

i 0

i n i in

(t) B (t) , (1)

no domínio 0 t 1, t , onde:

nB (t) (1 t) t , 0 i n,

i

=

−

=

≤ ≤ ∈

= − ≤ ≤

∑n iQ P

ℝ

(2)

são as funções-base denominadas . Polinômios de Bernstein

A Figura 1 mostra um exemplo de curva de Bézier de grau 3.

1.2. Principais características

Algumas características importantes das curvas de Bézier são [1]: 1. Para curvas de Bézier de grau n ≥ 2, o polígono formado pelos pontos de controle

P0, P1, ... , Pn formará o polígono de controle. A Figura 1 mostra uma curva cúbica e seu respectivo polígono de controle.

153

2. O ponto inicial P0 e o ponto final Pn são denominados pontos extremos do polígono de controle, pois se localizam nas extremidades dele. Os pontos P1, P2, ... , Pn – 1 são denominados pontos intermediários ou interiores do polígono de controle.

3. Os pontos extremos do polígono de controle também são extremidades da curva. Assim, P0 = Qn(0) e Pn = Qn(1).

4. Propriedade do fecho convexo: a curva sempre estará contida no fecho convexo do polígono de controle.

5. Propriedade de invariância afim: Qualquer transformação nos pontos de controle implica em transformação na curva. A curva é uma aproximação mais suave do polígono de controle. Assim, a quantidade de vezes que os segmentos do polígono de controle interceptam a curva será no máximo a quantidade destes segmentos.

6. Derivadas da curva de Bézier de grau n nos pontos extremos:

(0) n( )

(1) n( )

′ = −

′ = −

n 1 0

n n n-1

Q P P

Q P P

Figura 1: Curva de Bézier de grau 3.

2. Principais algoritmos de interseções de curvas de Bézier 2.1. Subdivisão recursiva de De Casteljau

É o processo de divisão de uma curva de Bézier em duas sub-curvas usando o método de De Casteljau. É muito usado quando se quer aproximar uma curva de Bézier por segmentos de reta [1].

Quando os segmentos estão bastante subdivididos, eles devem estar suficientemente próximos de retas. Assim, encontrando o ponto de interseção entre estas retas, encontra-se o ponto de interseção entre as curvas relacionadas a elas. A Figura 2 mostra três iterações.

Figura 2: Três iterações da subdivisão recursiva [4].

P0

P1 P2

P3

Q3(t)

154

2.2. Subdivisão intervalar de Koparkar e Mudur

Trata-se de um algoritmo semelhante à Subdivisão recursiva de De Casteljau, sendo que neste caso, cada curva é pré-processada para determinar suas tangentes horizontais e verticais apenas nos pontos extremos. Os limites destas tangentes definirão o intervalo. A Figura 3 mostra duas iterações do algoritmo para uma curva de Bézier cúbica.

Figura 3: Duas iterações da subdivisão intervalar [4]

2.3. Bézier Clipping

Trata-se de um algoritmo proposto em 1990 por Tomoyuki Nishita, professor do Departamento de Engenharia da Universidade de Tóquio, e Thomas W. Sederberg, professor do Departamento de Ciência da Computação da Universidade de Brigham Young, nos Estados Unidos, para o problema da interseção de curvas de Bézier [2].

O funcionamento do algoritmo acontece da seguinte forma: sejam duas curvas de Bézier P(t) e Q(u) e uma fat line L, uma região que representa a fronteira de Q(u). A Figura 4 mostra um exemplo.

Figura 4: Fat Line para curva de Bézier cúbica Q(u) no processo de Bézier Clipping [2]

P(t) é definida pela equação paramétrica n

ni i

i 0

(t) B (t)=

=∑P P

A função d(t) é um polinômio interpolador das distâncias id , 0 i n,≤ ≤ dos pontos de

controle da curva P(t) à fat line L e pode ter a seguinte representação paramétrica na forma Bernstein-Bézier:

D(t) = (t, d(t)) = n

ni

i 0

B (t)=∑ iD

Os pontos de controle i i(t ,d )=iD são igualmente espaçados em t (it i / n= ).

155

Como n

n ni

i 0

(i / n)B (t) t[(1 t) t] t=

= − + =∑ , a coordenada horizontal de qualquer ponto

D(t) é de fato o parâmetro t.

Figura 5: Curva de Bézier para representação Bernstein-Bézier de d(t) [2].

Os valores de t para os quais P(t) se encontra fora de L correspondem aos valores de t

para os quais D(t) se encontra abaixo de mind ou acima de maxd . Na Figura 5, tem-se que P(t) se

encontra fora de L em t < 0.25 e t > 0.75. Dessa forma, chega-se à uma das etapas do algoritmo de Bézier Clipping, que é o recorte das partes da curva P(t) que ficarem nesses intervalos. Essas partes são eliminadas de P(t) [2].

Após o recorte, uma fat line L será aplicada à curva P(t) no intervalo 0.25 t 0.75≤ ≤ . O próximo passo é repetir o procedimento aplicado anteriormente para P(t) na curva Q(u), depois P(t) terá um novo recorte contra Q(u) e assim alternando a curva de recorte sucessivamente [2].

No caso de múltiplas interseções, a solução é dividir uma das curvas pela metade e computar as interseções de cada metade com a outra curva [2].

3. Alguns resultados obtidos para localização de raízes de equações

Exemplo 1: Resolver a equação xsen(x) e−= , no intervalo [0, / 4]π , usando o algoritmo de Bézier Clipping.

Primeiro, vamos aproximar a função sen(x) por uma curva de Bézier de grau 3 no

intervalo dado.

Neste caso, os pontos de controle extremos devem ser: (0,0) e ( / 4,sen( / 4)) (0.785,0.7071).π π= = ≈0 3P P

Para calcular os pontos interiores, devemos aplicar as seguintes propriedades de derivadas das curvas de Bézier nos pontos extremos:

'(0) 3( )

'(1) 3( )

= −= −

1 0

3 2

P P P

P P P

Estes são os valores dos vetores tangentes à curva normalizados nos seus extremos [3].

156

Neste exemplo, temos: P’(0) = (0.7071, 0.7071) e P’(1) = (0.816, 0.577). Substituindo os valores, chegamos a: (0.2357,0.2357); (0.513,0.5151)= =1 2P P

Analogamente, para o caso de xe− , chegamos aos seguintes pontos de controle: (0,1); (0.236,0.764); (0.482,0.594); (0.785,0.456)= = = =0 1 2 3Q Q Q Q .

A Figura 6 mostra os gráficos obtidos para as curvas.

Figura 6: Aplicação das curvas de Bézier de grau 3 para localização de raízes de equações.

Os resultados encontrados para as três primeiras iterações se encontram na seguinte

tabela:

Iteração tmin tmax umin umax

0 0 1 0 1 1 0.7515 0.7650 0.7513 0.7949 2 0.7521 0.7656 0.7655 0.7836 3 0.7520 0.7654 0.7668 0.7838

Tabela 1: Resultados para três iterações de Bézier Clipping.

Na iteração 3, são colhidos os seguintes resultados para as curvas: Curva P(t): xP(0.7520) ≈ 0.5824; yP(0.7520) ≈ 0.5501; xP(0.7654) ≈ 0.5933; yP(0.7654) ≈ 0.5592; Curva Q(u): xQ(0.7668) ≈ 0.5817; yQ(0.7668) ≈ 0.5582; xQ(0.7838) ≈ 0.5960; yQ(0.7838) ≈ 0.5503;

157

Estes resultados se aproximam do ponto de interseção (0.5885, 0.5551) dado pela solução analítica com precisão de quatro casas decimais.

Exemplo 2: Resolver a equação xsen(x) e−= , no intervalo [0, / 4]π , usando o algoritmo da Subdivisão Recursiva de De Casteljau.

Os pontos de controle são os mesmos vistos no exemplo 1 para as respectivas curvas. Após cinco iterações, as sub-curvas que se interceptaram foram aproximadas de retas.

Para uma reta, foi obtida a equação 0.0131x + 0.0282 y – 0.0231 = 0. Para a outra, foi obtida a equação – 0.0182x + 0.0255y – 0.0037 = 0.

Portanto, deve ser resolvido o sistema linear:

0.0131 x + 0.0282 y – 0.0231 = 0 – 0.0182 x + 0.0255 y – 0.0037 = 0

A solução deste sistema com precisão de quatro casas decimais será x ≈ 0.5721, y ≈

0.5533997. Ou seja, após cinco iterações, os valores já estão relativamente próximos da solução analítica x ≈ 0.5885, y ≈ 0.5551.

Exemplo 3: Resolver a equação xsen(x) e−= , no intervalo [0, / 4]π , usando o algoritmo da

Subdivisão Intervalar de Koparkar e Mudur. A tabela a seguir mostra os resultados para cinco iterações do algoritmo.

Iteração t = u xP(t) yP(t) xQ(u) yQ(u) 1 0.5 0.3789 0.3699 0.3674 0.6913 2 0.75 0.5807 0.5488 0.5677 0.5660 3 0.875 0.6828 0.6313 0.6740 0.5093 4 0.8125 0.6318 0.5907 0.6203 0.5372 5 0.78125 0.6062 0.5699 0.5938 0.5515

Tabela 2: Resultados para cinco iterações de Subdivisão Intervalar.

Referências [1] Samuel R. Buss, “3-D Computer Graphics – A Mathematical Introduction with OpenGL”, Cambridge University Press, 2003. [2] T. Nishita, T.W. Sederberg, “Curve Intersection Using Bézier Clipping”, pp. 538-549, Computer-Aided Design 22(9), 1990. [3] David Salomon, “Curves and Surfaces for Computer Graphics”, Springer, 2006. [4] T.W. Sederberg, S.R. Parry, “Comparison of Three Curves Intersection Algorithms”, pp. 58-63, Computer-Aided Design Vol. 18.

158