Inicio > Artículos, Geometría, Programación > Algoritmo de De Casteljau

Algoritmo de De Casteljau

Domingo, 22 de julio de 2012
Citar este artículo 8.599 visitas
Algoritmo de De Casteljau

Frecuentemente en el diseño se habla de “gráficos vectoriales”, los que son el resultado de avances que varios matemáticos hicieron en los años 60 al enfrentar problemas de diseño de carrocerías de autos.

Un gran ejemplo, son las llamadas curvas de Bézier, desarrolladas por el matemático francés Pierre Bézier en la Renault, y que también fueron estudiadas por Paul de Casteljau en la Citroen. En este post veremos cómo el Algoritmo de De Casteljau, para generar una curva de Bézier, genera una familia de otras curvas de menor grado, que están todas relacionadas jerárquicamente.

A fines del 2010 mostré las Curvas de Bézier, su construcicón y el algoritmo de Paul de De Casteljau para aproximar tales curvas, pero un aspecto que no queda completamente claro es su interpretación geométrica.

1. Curvas de Bézier

Partamos diciendo que una curva de Bézier es esencialmente una curva que se basa en los Polinomios de Bernstein, y el objetivo que se planteó Bézier fue poder aproximar una curva simplemente modificando la posición de algunos puntos. Tal interfaz está incluida actualmente en la mayoría de los programas de diseño, especialmente en aquellos de diseño vectorial, y donde es muy intuitivo construirlas y modificarlas.

Para visualizar correctamente este applet, debes instalar (o activar) Java. Visita Java.com/es

En esta escena, por ejemplo, tenemos una curva de Bézier de orden “n”. Nótese que “n” corresponde a la cantidad de segmentos que permiten unir los puntos iniciales (puntos de control), y tal poligonal (abierta) se denomina el polígono de control. Lo notable de este avance, es que Bézier ideó cómo construir una curva suave que parte en el primer punto y termina en el segundo, y así es posible adaptarla simplemente modificando los puntos de control.

Esta es la base del diseño vectorial, si a partir de un conjunto finito de puntos sabemos cómo construir la curva de Bézier asociada, lo único que debemos conocer son las coordenadas de los puntos de control. Así, el gráfico vectorial guarda en esencia información de los vectores que definen esta curva, en oposición a los mapas de bits (o imágenes rasterizadas) que guardan una tabla de información de cada pixel, y por tal razón cuando se amplían estos se “pixelan”.

2. El algoritmo de De Casteljau

De Casteljau ideó un algoritmo para aproximarse a las curvas de Bézier, como mostraba en el post citado al principio, el grado y la cantidad de términos de las ecuaciones (paramétricas además) de una curva de Bézier es la misma que la cantidad de lados del polígono de control, de manera que para los recursos que se contaban en la época era un tanto complejo.

El Algoritmo de De Casteljau, consiste esencialmente en dividir en una razón dada los lados del polígono de control. Partiendo de los puntos P1, P2, P3, … , Pn+1, la primera parte del algoritmo consiste en obtener “n” puntos, cada uno de los cuales divide en la razón “t” cada segmento, es decir, puntos de la forma:

Primera generación de puntos

B1 = P1 + t * (P2 – P1)
B2 = P2 + t * (P3 – P2)
.
.
.
Bn = Pn + t * (Pn+1 – Pn)

Luego, a partir de “n+1” puntos, se generan “n” puntos, que dividen los lados del polígono de control en la razón “t” (siendo t un valor entre 0 y 1). Este mismo procedimiento se repite (n veces en total) con los resultantes, sucesivamente, hasta que se obtenga un último punto que estará sobre la curva de Bézier asociada.

Para visualizar correctamente este applet, debes instalar (o activar) Java. Visita Java.com/es

En esta escena se pueden ver los distintos pasos del algoritmo, para generar una curva de grado 4. El parámetro “t” es variable entre 0 y 1, y corresponde a la razón en la que los segmentos son divididos. El deslizador “g”, en cambio, permite observar las distintas generaciones de puntos que se obtienen. De tal forma, partimos con los puntos A, B, C, D, E, para obtener en la primera iteración los puntos F, G, H e I. Luego debemos dividir los segmentos en la misma razón, obteniendo J, K y L, y así sucesivamente el último punto que se genera es O.

En consecuencia, en esta escena, al aumentar el deslizador “g” observamos las etapas sucesivas del algoritmo, mientras que modificando el deslizador “t” vemos cómo cambian estos puntos al variar la razón en la que se dividen los segmentos. Esto último permite observar el lugar geométrico de O, respecto al deslizador “t” es la curva de Bézier que depende de los puntos A, B, C y D.

Ahora bien, es importante aclarar que el algoritmo sólo genera un punto, es decir, contando con un valor de “t” y las coordenadas de los puntos de control, obtenemos finalmente un punto sobre la curva. Pero aprovechando las características de Geogebra logramos ver qué curva describe O a medida que “t” varía. Esto último no lo pudieron observar en su época Bézier ni De Casteljau, sino que deben haber utilizado estas ideas para generar puntos sobre la curva a generar. Es poco probable que hayan podido ver lo que veremos a continuación (aunque sí deben haberlo imaginado).

3. Curvas intermedias

Para generar una curva de Bézier de orden 4, hemos calculado las coordenadas de 10 puntos (4+3+2+1), es decir, hay 15 puntos involucrados en el algoritmo, pero ¿qué curvas describen estos 15 puntos al hacer variar “t”.

 

Para visualizar correctamente este applet, debes instalar (o activar) Java. Visita Java.com/es

En esta escena está visible la hoja de cálculo, que es sumamente útil para implementar el algoritmo (ver los videos al final). Lo interesante de este ejercicio es observar qué curvas describe cada punto involucrado en el algoritmo. Todas estas son curvas de Bézier, de hecho, cada punto de la generación “m” del algoritmo, describe una curva de bezier de grado “m”, es decir:

  • g = 1: B2, B3, B4 y B5, describen curvas de Bézier de grado 1 (segmentos)
  • g = 2: C3, C4 y C5, describen curvas de Bézier de grado 2 (arcos parabólicos)
  • g = 3: D4 y D5, describen curvas de Bézier de grado 3
  • g = 4: E5, describe una curvas de Bézier de grado 4

Entonces, cada punto del algoritmo describe una curva, y como todas las de este tipo, parten en un punto y terminan en otro, siendo la cantidad de puntos que se saltan igual al grado menos 1, es decir, las curvas de grado 1 se saltan 0 puntos, las de grado 2 se saltan 1 punto, las de grado 3 se saltan 2 puntos y la de grado 4 se salta 3 puntos.

Más importante que lo anterior, los segmentos que se generan en este algoritmo, parecieran deslizarse sobre los segmentos de la generación anterior, es casi como un mecanismo, pero no lo es. Sí ocurre que los puntos se “deslizan” por segmentos, pero esto no es la única forma en que se pueden “dibujar” estas curvas, y esto es quizás más curioso (sino, sorprendente).

4. Deslizamiento sobre curvas

Para visualizar correctamente este applet, debes instalar (o activar) Java. Visita Java.com/es

En la construcción anterior vemos puntos que se deslizan por segmentos, dibujando curvas de Bézier cada vez de mayor orden. Sin embargo, ¿qué ocurriría si esos puntos se deslizaran sobre curvas de Bézier?

En esta escena se muestra tal idea, los puntos de la primera generación describen segmentos, que son en rigor curvas de Bézier de orden 1. Pero los puntos de la segunda generación (g=2) se deslizan sobre tales curvas anteriores. Obsérvese qué ocurre con la tercera generación (g=3), los puntos C3, C4 y C5 se deslizan sobre curvas de Bézier de orden 2, para que los segmentos que forman dibujen curvas de Bézier de orden 3. Esto es, C3 se desliza sobre una curva de orden 2, C4 se desliza sobre la siguiente curva, también de orden 2; y el que divide el segmento C3C4, describe una curva de orden 3.

Esta lógica puede seguir escalando, puntos sobre dos curvas de grado “n” se deslizan, para que el segmento que los une dibuje una curva de grado “n+1”. Eso no es completamente sorpresivo, en rigor, pues una curva de Bézier es un lugar geométrico envolvente. Si se observan las contrucciones del post Curva de Bézier con cuidado, se podrá entender esta lógica, en la que los segmentos son tangentes a las curvas y el punto móvil sobre el segmento es en realidad un punto de tangencia, así que el punto se mueve al mismo tiempo sobre el segmento y sobre la curva.

En este video se ilustra tal relación entre curvas:

5. Nube de puntos

 

Para visualizar correctamente este applet, debes instalar (o activar) Java. Visita Java.com/es

En suma, el algoritmo de De Casteljau genera una nube de puntos, que a simple vista, para quien no conoce estas curvas, moverse de manera curiosa, pero sin seguir ningún patrón. Sin embargo, esta nube tiene un sentido, los puntos de cada generación describen curvas que conectan dos puntos de control cualesquiera. Así, el algoritmo que genera la curva asociada a un conjunto finito de puntos (por ejemplo, {AB,C,D,E,F,G,H}), también genera las curvas asociadas a todos sus subconjuntos, ¿habrá imaginado De Casteljau esta imagen?

Dejo finalmente un enlace al post inicial que hice en mi blog de Tumblr, que me motivó a escribir estas ideas, y que lo ilustra de manera más gráfica: http://mirandamolina.tumblr.com/post/28095982332/de-casteljaus-algoritm-produces-successive

Además incluyo los videos del post del 2010 que muestran algunas de estas construcciones en Geogebra.

Artículos, Geometría, Programación , , , , , , ,

  1. Sin comentarios aún.
  1. Sin trackbacks aún.

Artículo publicado en http://www.geometriadinamica.cl/2012/07/algoritmo-de-de-casteljau/.