Técnicas de Bézier e interpolación mediante splines

Facultad de Ciencias Trabajo Fin de Grado Grado en Matemáticas Técnicas de Bézier e Interpolación mediante Splines Autora: Alicia Nieto Ramos Tutora: María Paz Calvo Cabrero Índice general Introducción 3 1. Polinomios de Bernstein 5 1.1. Definición y propiedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2. Representación de Bézier de un polinomio P∈P2 n15 2.1. Algoritmo de De Casteljau . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2. Derivación de polinomios representados en la forma de Bézier . . . . . . . . 19 3. Operaciones con curvas de Bézier 25 3.1. Subdivisión ................................... 25 3.2. Elevacióndelgrado............................... 28 3.3. Reduccióndelgrado .............................. 33 4. Splines en la forma de Bézier 37 4.1. Parámetros globales y locales . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.2. Condiciones de regularidad . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.3. Splines de Bézier cuadráticos a trozos con regularidad C1.......... 44 4.4. Splines de Bézier cúbicos a trozos con regularidad C2............ 46 5. Ejemplos prácticos: diseño mediante splines de Bézier a trozos 51 5.1. Splines de Bézier a trozos al diseñar la letra S . . . . . . . . . . . . . . . . 52 5.2. Splines de Bézier a trozos al diseñar una firma . . . . . . . . . . . . . . . . 60 Bibliografía 69 A. Código de los programas más significativos en MATLAB®71 1 Introducción El diseño gráfico y el diseño asistido por ordenador surgieron a mediados de los años 60 y se han convertido a día de hoy, en dos herramientas fundamentales tanto en ciencia como en ingeniería. El objetivo de este Trabajo de Fin de Grado es el estudio de los splines de Bézier a trozos definidos en el plano, partiendo de los principales conceptos y propiedades relacionados con los polinomios de Bernstein y las curvas de Bézier, ilustrando con dos ejemplos el uso de estos en el ámbito del diseño. En el Capítulo 1, se definen los polinomios de Bernstein tanto en [0,1] como en un intervalo [a, b]real arbitrairio, y se enuncian y demuestran algunas de sus propiedades más significativas. También se enuncia y prueba el Teorema de aproximación de Weierstrass utilizando estos polinomios. En el Capítulo 2, se emplea la base que forman los polinomios de Bernstein para escribir curvas en el plano, lo que se conoce como representación de Bézier de una curva. Los coeficientes que acompañan a los polinomios de Bernstein en dicha representación, reciben el nombre de nodos de Bézier. A continuación se estudia el algoritmo de De Casteljau, fundamental en la construcción recursiva de las curvas de Bézier y se finaliza el capítulo con resultados relativos a la derivación de dichas curvas. En el Capítulo 3, se estudian las operaciones más usuales que se realizan cuando se trabaja con curvas de Bézier: la operación de subdivisión (que permite definir parte de la traza de una curva de Bézier definiendo nuevos nodos de Bézier a partir de los iniciales), la elevación de grado (profundizando también en la elevación reiterada del grado de una curva de Bézier) y finalmente, la reducción de grado. En el Capítulo 4, se da la definición de spline de Bézier a trozos, y se especifican las condiciones que debe cumplir un spline para poseer regularidad Cr,r∈N. Se tratan con mayor profundidad los casos de spline cuadrático con regularidad C1y de spline cúbico con regularidad C2. En el Capítulo 5, se consideran dos imágenes (la letra S de la tipografía Times New Roman©y una firma) y se efectúa la interpolación mediante splines de Bézier de varios grados con y sin regularidad, para ilustrar la aplicación directa de estas curvas en el área del diseño gráfico. Se emplea MATLAB®como programa principal y GeoGebra como herramienta auxiliar para determinar los nodos de Bézier de manera interactiva. En el caso 3 Índice general de la firma, se corrobora el resultado obtenido mediante InkScape, programa orientado al diseño gráfico. Finalmente, en el Apéndice A se han incluido las funciones de MATLAB®que implementan los distintos algoritmos estudiados a lo largo de este trabajo y se han utilizado para la elaboración de las gráficas que aparecen en la memoria. Se destaca la función bspline_cubico.m, que efectúa la interpolación mediante splines cúbicos de Bézier para Ltrozos con regularidad C2, crucial para las aproximaciones de los ejemplos presentes en el Capítulo 5. Me gustaría agradecer a la Dra. María Paz Calvo Cabrero su implicación, dedicación y paciencia mostrados durante la elaboración de este trabajo. 4 Capítulo 1 Polinomios de Bernstein En este capítulo vamos a definir y a estudiar las principales propiedades de los polinomios de Bernstein. 1.1. Definición y propiedades A medida que fueron evolucionando las técnicas interpolatorias, surgieron distintas bases del espacio de polinomios de grado ≤n, al que denotaremos por Pn. Si bien la más conocida es la base de monomios {1, x2, . . . , xn}, Lagrange introduce junto a su polinomio interpolador una nueva base {L0(x), L1(x), . . . , Ln(x)}, donde Li(x) = Y j6=i (x−xj) Y j6=i (xi−xj), i = 0, . . . , n, y Newton la base {w0(x), w1(x), . . . , wn(x)}donde wi(x)∈Piy w0(x) = 1, wi(x) = i−1 Y j=0 (x−xj), i = 1, . . . , n, que, a diferencia de la primera, dependen de n+ 1 nodos concretos x0, . . . , xn. Sin embargo, es en los últimos treinta años del siglo pasado cuando el auge tanto del diseño como de la construcción asistidos por ordenador hace que la teoría de aproximación se centre en la forma geométrica de los polinomios y en buscar nuevas bases que permitan dibujar y manipular curvas de la forma más eficiente posible. Surgen así los polinomios de Bernstein, los cuales desempeñan un papel fundamental en la representación de las curvas de Bézier tal y como se mostrará a lo largo de este capítulo (ver Deuflhard y Hohmann (2003)). 5 Capítulo 1. Polinomios de Bernstein Figura 1.1: Polinomios de Bernstein para n= 4 definidos en el intervalo [0,1]. Definición 1.1. Se define el i-ésimo polinomio de Bernstein de grado ncon respecto al intervalo [0,1],Bn i(λ)∈Pn, como Bn i(λ) := n i!(1 −λ)n−iλi, i = 0, . . . , n. (1.1.1) En la Figura 1.1 se han dibujado los polinomios de Bernstein de grado 4. Considerando la aplicación afín, λ: [a, b]−→ [0,1] t−→ λ(t) = t−a b−a,(1.1.2) se define el i-ésimo polinomio de Bernstein de grado ncon respecto al intervalo [a,b], a < b, a, b ∈R, como Bn i(t;a, b) := Bn i(λ(t)) = n i!1−t−a b−an−it−a b−ai=1 (b−a)n n i!(b−t)n−i(t−a)i, para i= 0, . . . , n. Enunciaremos y probaremos los resultados correspondientes a los polinomios de Bernstein para [0,1] que, utilizando la aplicación (1.1.2), se generalizan a cualquier intervalo [a, b], a, b ∈R, a < b. Exponemos en el siguiente teorema las propiedades más significativas de estos polinomios. 6 1.1. Definición y propiedades Teorema 1.2. Los polinomios de Bernstein Bn i(λ),0≤i≤n, satisfacen: 1. λ= 0 es una raíz de Bn i(λ)con multiplicidad i. 2. λ= 1 es una raíz de Bn i(λ)con multiplicidad n−i. 3. Propiedad de simetría: Bn i(λ) = Bn n−i(1 −λ), i = 0, . . . , n. (1.1.3) 4. (1 −λ)Bn 0(λ) = Bn+1 0(λ), y λBn n(λ) = Bn+1 n+1(λ). 5. Los polinomios de Bernstein Bn i(λ)son no negativos en [0,1] y forman una partición de la unidad, esto es, Bn i(λ)≥0, λ ∈[0,1], n X i=0 Bn i(λ) = 1, λ ∈[0,1].(1.1.4) 6. Bn i(λ)tiene exactamente un máximo en [0,1] en el punto λ=i n. 7. Los polinomios de Bernstein satisfacen la relación de recurrencia Bn i(λ) = λBn−1 i−1(λ) + (1 −λ)Bn−1 i(λ), i = 1, . . . , n, λ ∈[0,1].(1.1.5) 8. Los polinomios de Bernstein forman una base B={Bn 0(λ), . . . , Bn n(λ)}de Pn. 9. Las derivadas de los polinomios de Bernstein Bn i(λ)en el intervalo [0,1] vienen dadas por d dλBn 0(λ) = −nBn−1 0(λ), d dλBn i(λ) = n(Bn−1 i−1(λ)−Bn−1 i(λ)), i = 1, . . . , n −1, d dλBn n(λ) = nBn−1 n−1(λ). (1.1.6) Demostración. 1 y 2. Inmediatas por la Definición 1.1. 3. Bn n−i(1 −λ) = n n−i!(1 −(1 −λ))n−(n−i)(1 −λ)n−i= n i!(1 −λ)n−iλi=Bn i(λ). 4. Utilizando la expresión (1.1.1), notamos que Bn 0(λ) = (1 −λ)nyBn n(λ) = λn. Es claro entonces que Bn+1 0(λ) = (1 −λ)n+1 = (1 −λ)Bn 0(λ), Bn+1 n+1(λ) = λn+1 =λBn n(λ). 7 Capítulo 1. Polinomios de Bernstein 14 Capítulo 2 Representación de Bézier de un polinomio P∈P2 n Gracias a la Propiedad (8) del Teorema 1.2, sabemos que los polinomios de Bernstein forman una base tanto si están definidos en [0,1] como si lo están en [a, b]para a < b, a, b ∈R. Definición 2.1. Una curva polinomial (o polinomio) de grado n en R2es una función Pde la forma P:R−→ R2 t−→ P(t) = n X i=0 aiti,a0,...,an∈R2,an6= 0. El espacio de polinomios de grado menor o igual que nen R2se denota mediante P2 n. Definición 2.2. Dada una curva polinomial P∈P2 nse definen los puntos de Bézier de Popuntos de control de Pcomo los coeficientes b0,...,bn∈R2de la representación de Pen la base de polinomios de Bernstein en [a, b], P(t) = n X i=0 biBn i(t;a, b), t ∈[a, b].(2.0.1) A la representación de Pen esta base se le conoce como representación de Bézier de P, y al polígono que surge de unir mediante segmentos los puntos de Bézier que están consecutivos se le conoce como polígono de Bézier de P. Notación. Aunque esta definición está expresada en términos del intervalo genérico [a, b], en numerosas ocasiones se hablará de puntos de Bézier haciéndose referencia a la representación de Pen la base {Bn 0(λ), . . . , Bn n(λ)}donde cada Bn i(λ)está definido en [0,1]. 15 Capítulo 2. Representación de Bézier de un polinomio P∈P2 n Observación 2.3. Dada una aplicación afín φ:R2−→ R2, φ(u) = Au+v,v∈R2, A ∈ M2,2se verifica que las imágenes φ(bi)de los puntos de Bézier de un polinomio P∈P2 n definido en [0,1] son los puntos de Bézier de φ◦P n X i=0 φ(bi)Bn i(λ) = n X i=0 (Abi+v)Bn i(λ) = n X i=0 AbiBn i(λ) + n X i=0 vBn i(λ) =A n X i=0 biBn i(λ)!+v=φ n X i=0 biBn i(λ)!=φ(P(λ)), λ ∈[0,1]. Notamos que para probar las igualdades anteriores, se ha utilizado la expresión (1.1.4). Antes de continuar, ilustramos mediante la Figura 2.1, cómo influye en la estructura de la curva la ordenación de los nodos de Bézier en la definición del polígono. Para ello, se consideran los puntos A= (−0,8,2,55), B= (−5,36,−1,77), C= (0,72,−1,85), D= (−1,56,−3,61), y para λ∈[0,1] se consideran, (a) 3 X i=0 biBn i(λ) = AB3 0(λ) + BB3 1(λ) + CB3 2(λ) + DB3 3(λ), (b) 3 X i=0 biBn i(λ) = DB3 0(λ) + AB3 1(λ) + BB3 2(λ) + CB3 3(λ), (c) 3 X i=0 biBn i(λ) = AB3 0(λ) + DB3 1(λ) + BB3 2(λ) + CB3 3(λ), (d) 3 X i=0 biBn i(λ) = AB3 0(λ) + BB3 1(λ) + DB3 2(λ) + CB3 3(λ), que muestran cuatro curvas distintas que pueden obtenerse al permutar dichos nodos. Pese a que existen veinticuatro reordenaciones posibles de los cuatro puntos del plano A, B,C,D, muchas de ellas se repiten debido a la Propiedad (1.1.3), como es por ejemplo el caso de (b0,b1,b2,b3) = (A,B,C,D)y(b0,b1,b2,b3) = (D,C,B,A). En todos los casos observamos que la curva pasa por el primer punto y por el último. Esto es consecuencia de las Propiedades 1 y 2 del Teorema 1.2. Aunque se justificará más adelante, se observa también en las cuatro figuras que el segmento que une los dos primeros nodos tiene la misma dirección que la tangente a la curva en el primer nodo, y que el segmento que une los dos últimos nodos tiene la misma dirección que la tangente a la curva en el último nodo. 16 (a) (b0,b1,b2,b3)=(A,B,C,D).(b) (b0,b1,b2,b3)=(D,A,B,C). (c) (b0,b1,b2,b3)=(A,D,B,C). (d) (b0,b1,b2,b3)=(A,B,D,C). Figura 2.1: Ejemplo de polinomios de Bézier cúbicos que utilizan los mismos nodos pero en distinto orden. 17 Capítulo 2. Representación de Bézier de un polinomio P∈P2 n 2.1. Algoritmo de De Casteljau De manera análoga a la tabla de diferencias divididas utilizada en la construcción de la forma de Newton del polinomio interpolador de Lagrange, existe un algoritmo para la construcción de la representación de Bézier de un polinomio Pde grado menor o igual que nen el plano definido por un polígono b0,...,bn. Este construye el polinomio utilizando combinaciones continuas convexas de puntos de Bézier y la información que nos aportan las derivadas. Introducimos a continuación la definición de polinomios parciales de P. Definición 2.4. Sea P(λ) = n X i=0 biBn i(λ), λ ∈[0,1].Se definen los polinomios parciales bk i(λ)∈P2 kde Pcomo bk i(λ) := k X j=0 bi+jBk j(λ) = i+k X j=i bjBk j−i(λ), i = 0, . . . , n −k, λ ∈[0,1]. Para un polinomio P(t) = n X i=0 biBn i(t;a, b), t ∈[a, b],los polinomios parciales bk i(t)∈P2 k se definen de manera similar, utilizando el cambio de variable (1.1.2), bk i(t;a, b) := bk i(λ(t)) = k X j=0 bi+jBk j(t;a, b) = i+k X j=i bjBk j−i(t;a, b), i = 0, . . . , n−k, t ∈[a, b]. De este modo, el polinomio parcial bk i∈P2 kes justamente el polinomio de Bézier definido mediante los puntos de control bi,...,bi+k. En particular, P(t) = bn 0(t)yb0 i(t) = bi, t ∈[a, b], y para los extremos se verifica bk i(a) = biybk i(b) = bi+k. Expresamos a continuación el lema que va a ser fundamental en el desarrollo del algoritmo de De Casteljau: Lema 2.5. Los polinomios parciales bk i(t;a, b)de P(t) = n X i=0 biBn i(t;a, b)satisfacen la relación de recurrencia bk i(t;a, b) = (1 −λ(t))bk−1 i(t;a, b) + λ(t)bk−1 i+1 (t;a, b), k = 0, . . . , n;i= 0, . . . , n −k. (2.1.1) con λ(t)dado por (1.1.2),t∈[a, b]. Demostración. Basta insertar la relación de recurrencia (1.1.5) en la definición de los 18 2.2. Derivación de polinomios representados en la forma de Bézier polinomios parciales bk i(t)para obtener bk i(t;a, b) = k X j=0 bi+jBk j(t;a, b) = biBk 0(t;a, b) + bi+kBk k(t;a, b) + k−1 X j=1 bi+jBk j(t;a, b) =bi(1 −λ(t))Bk−1 0(t;a, b) + bi+kλ(t)Bk−1 k−1(t;a, b) + k−1 X j=1 bi+j(1 −λ(t))Bk−1 j(t;a, b) + λ(t)Bk−1 j−1(t;a, b) = k−1 X j=0 bi+j(1 −λ(t))Bk−1 j(t;a, b) + k X j=1 bi+jλ(t)Bk−1 j−1(t;a, b) = (1 −λ(t))bk−1 i(t;a, b) + λ(t)bk−1 i+1 (t;a, b), t ∈[a, b]. Gracias a que b0 i(t) = bi, i = 0, . . . , n, t ∈[a, b],podemos ir construyendo P(t) = bn 0(t) mediante combinaciones continuas convexas a partir de los puntos de Bézier, tal y como se expone en el Lema 2.5. Este proceso recursivo de construcción de P(t) = bn 0se conoce con el nombre de algoritmo de De Casteljau, y aparece esquematizado en la Figura 2.2. Figura 2.2: Algoritmo de De Casteljau esquematizado. A simple vista puede parecer que el algoritmo de De Casteljau tan solo utiliza los distintos bipara construir P, sin rastro alguno de las derivadas de P. Sin embargo, la siguiente sección muestra cómo las derivadas k-ésimas P(k), k ∈N, están ocultas tras los polinomios auxiliares bk i, i = 0, . . . , n −k. 2.2. Derivación de polinomios representados en la forma de Bézier En la sección anterior se comentó que como consecuencia del Teorema 1.2 el polígono y la curva de Bézier comienzan y acaban ambos en los mismos puntos. Parece intuitivo 19 Capítulo 2. Representación de Bézier de un polinomio P∈P2 n pensar que las tangentes en los nodos b0,bncoinciden con las rectas más próximas correspondientes al polígono de Bézier. Para ver si esta suposición es cierta o es una mera ilusión óptica, procedemos a analizar las derivadas de las curvas representadas en la forma (2.0.1). Comenzamos analizando las derivadas de los polinomios representados en la forma de Bézier definidos en el intervalo [0,1]. Teorema 2.6. Sea P(λ) = n X i=0 biBn i(λ)la representación de Bézier con respecto a [0,1] de un polinomio. La derivada k-ésima de Psatisface P(k)(λ) = n! (n−k)! n−k X i=0 4kbiBn−k i(λ), λ ∈[0,1],(2.2.1) donde 4denota el operador de diferencias progresivas, definido por 4bi=bi+1 −bi, 4kbi=4k−1bi+1 −4k−1bi, k > 1, i = 0, . . . , n −k. Demostración. Razonamos mediante inducción sobre k. Para k= 1, utilizando las ecuaciones (1.1.6) tenemos P0(λ) = −nb0Bn−1 0(λ) + n−1 X i=0 nbiBn−1 i−1(λ)−Bn−1 i(λ)+nbnBn−1 n−1(λ) =n"bnBn−1 n−1(λ)−b0Bn−1 0(λ) +b1Bn−1 0(λ) + n−2 X i=1 bi+1 −biBn−1 i(λ)−bn−1Bn−1 n−1(λ)# =n n−1 X i=0 (bi+1 −bi)Bn−1 i(λ) =n n−1 X i=0 4biBn−1 i(λ). Supongamos que P(k)(λ) = n! (n−k)! n−k X i=0 4kbiBn−k i(λ),y veamos que P(k+1)(λ) = n! (n−k−1)! n−k−1 X i=0 4k+1biBn−k−1 i(λ). 20 2.2. Derivación de polinomios representados en la forma de Bézier De nuevo, utilizando las ecuaciones (1.1.6) pero esta vez derivando P(k), P(k+1)(λ) = n! (n−k)! n−k X i=0 4kbi d dλBn−k i(λ) =n! (n−k)!"−(n−k)4kb0Bn−k−1 0(λ)+(n−k)4kbn−kBn−k−1 n−k−1(λ) + (n−k) n−k−1 X i=0 4kbi(Bn−k−1 i−1(λ)−Bn−k−1 i(λ))# =n! (n−k−1)!"−4kb0Bn−k−1 0(λ) + 4kbn−kBn−k−1 n−k−1(λ) + n−k−1 X i=0 4kbiBn−k−1 i−1(λ)−Bn−k−1 i(λ)# =n! (n−k−1)!"n−k−1 X i=0 4kbi+1 −4kbiBn−k−1 i(λ)# =n! (n−k−1)! n−k−1 X i=0 4k+1biBn−k−1 i(λ). Observación 2.7. Para extender el Teorema 2.6 al caso de polinomios de Bézier representados en un intervalo cualquiera [a, b], a, b ∈R, a < b, basta con derivar la función λ definida en (1.1.2),λ0(t) = 1 b−a,y emplear la regla de la cadena para obtener finalmente, P(k)(t;a, b) = n! (n−k)! n−k X i=0 4kbiBn−k i(t;a, b) 1 b−a!k , t ∈[a, b]. Corolario 2.8. Sea Puna curva de Bézier definida en [0,1]. Entonces para λ= 0,1, P(k)(0) = n! (n−k)!4kb0, P(k)(1) = n! (n−k)!4kbn−k. En particular, P(0) = b0,P(1) = bn, P0(0) = n(b1−b0),P0(1) = n(bn−bn−1), P00(0) = n(n−1)(b2−2b1+b0),P00(1) = n(n−1)(bn−2bn−1+bn−2). Demostración. Basta con tener en cuenta que Bn−k i(0) = δ0,i yBn−k i(1) = δn−k,i y el resultado es inmediato gracias al Teorema 2.6. 21 Capítulo 2. Representación de Bézier de un polinomio P∈P2 n El corolario anterior confirma las sospechas que habíamos expuesto con anterioridad. En efecto, en los nodos extremos la tangente a la curva coincide con la pendiente de la recta que une los primeros dos puntos (respectivamente los dos últimos) del polígono de Bézier. Es especialmente significativo el hecho de que en un nodo extremo la curva está determinada, hasta la derivada k-ésima, por los kpuntos de Bézier más próximos, tal y como puede verse en el Corolario 2.8. Esta propiedad será crucial más adelante, en el Capítulo 4, cuando se trate de unir varios segmentos de curva en un único spline regular. El teorema siguiente afirma que la curva polinómica Pestá siempre contenida en la envolvente convexa de sus puntos de Bézier. Teorema 2.9. La imagen P([a, b]) de un polinomio P∈P2 nen la representación de Bézier P(t) = n X i=0 biBn i(t;a, b)con respecto de [a, b]está contenida en la envolvente convexa de los puntos de Bézier bi, es decir, P(t)∈co({b0,...,bn}), t ∈[a, b]. Demostración. Recordamos que la envolvente convexa co(A)de A⊂R2es el conjunto de todas las combinaciones convexas de puntos de A, esto es, co(A) = (m X i=1 λixi, m ∈N, xi∈A, λi≥0, m X i=1 λi= 1). En [a, b], los polinomios de Bernstein forman una partición no negativa de la unidad, esto es Bn i(t;a, b)≥0para t∈[a, b]y n X i=0 Bn i(t;a, b) = 1. Entonces P(t) = n X i=0 biBn i(t;a, b) es una combinación convexa de los puntos de Bézier b0,...,bn. Teorema 2.10. Sea P(λ) = n X i=0 biBn i(λ)un polinomio en la representación de Bézier en [0,1]. Entonces las derivadas P(k)para k= 0, . . . , n pueden construirse a partir de los polinomios parciales bk imediante la relación P(k)(λ) = n! (n−k)!4kbn−k 0(λ),(2.2.2) donde 4bk i=bk i+1 −bk i. 22 2.2. Derivación de polinomios representados en la forma de Bézier Demostración. En virtud del Teorema 2.6 sabemos que P(k)(λ) = n! (n−k)! n−k X i=0 4kbiBn−k i(λ). Por la linealidad del operador 4k, n−k X j=0 4kbjBn−k j(λ) = 4k n−k X j=0 bjBn−k j(λ) = 4kbn−k 0(λ), lo que concluye la demostración. Como consecuencia del Teorema 2.10, sabemos que la derivada k-ésima de Pse obtiene a partir de la columna (n−k)-ésima del algoritmo de De Casteljau. En particular, para λ∈[0,1], P(λ) = bn 0(λ), P0(λ) = n(bn−1 1(λ)−bn−1 0(λ)), P00(λ) = n(n−1)(bn−2 2(λ)−2bn−2 1(λ) + bn−2 0(λ)). Observación 2.11. La expresión (2.2.2), puede extenderse al caso de polinomios de Bézier definidos en un intervalo cualquiera [a, b], a, b ∈R, a < b, tal y como se hizo en la Observación 2.7, P(k)(t;a, b) = n! (n−k)!4kbn−k 0(t;a, b) 1 b−a!k , t ∈[a, b]. 23 Capítulo 3. Operaciones con curvas de Bézier b(r+1) i= n X j=0 bj n j!r+1 i−j n+r+1 i,0≤i≤n+r+ 1. Sabemos que para 0≤i≤n+r+ 1, b(r+1) i=i n+r+ 1b(r) i−1+ 1−i n+r+ 1!b(r) i =i n+r+ 1 n X j=0 bj n j!r i−j−1 n+r i−1+ 1−i n+r+ 1!n X j=0 bj n j!r i−j n+r i =i n+r+ 1 n X j=0 bj n j!r!(n+r−i+ 1)!(i−1)! (n+r)!(i−j)!(r−i+j+ 1)!(r+ 1) = n X j=0 bj n j!(r+ 1)!(n+r−i+ 1)!i! (n+r+ 1)!(i−j)!(r−i+j+ 1)! = n X j=0 bj n j!r+1 i−j n+r+1 i. Investiguemos ahora qué sucede si elevamos el grado repetidas veces. Proposición 3.4. Los polígonos ErPconvergen a la curva que ellos mismos definen cuando r→ ∞. Demostración. En la demostración de la Proposición 3.4 vamos a utilizar los tres resultados auxiliares que se enuncian a continuación y cuya demostración se omite. Resultado 1. Gracias a la Fórmula de Stirling, podemos afirmar que cuando r→ ∞ e i→ ∞ (que es justamente lo que ocurre en este caso), r!∼√2πr r e!r , i!∼√2πi i e!i , (i−j)! ∼q2π(i−j) i−j e!i−j , (n+r)! ∼q2π(n+r) n+r e!n+r . 30 3.2. Elevación del grado Figura 3.2: Elevación repetida del grado para una curva de Bézier cúbica hasta r= 6. Resultado 2. l´ım r→∞ r n+r!r = l´ım r→∞" 1 + 1 −(n+r) n! −(n+r) n# −nr n+r=el´ımr→∞ −nr n+r=e−n. l´ım i→∞ i i−j!i = l´ım i→∞" 1 + 1 i−j j!i−j j#ij i−j=el´ımi→∞ ij i−j=ej. Resultado 3. l´ım r,i→∞ sri (i−j)(n+r)= l´ım r,i→∞ sri ri +ni −nj −jr = l´ım r,i→∞ v u u t 1 1 + n r−nj ri −j i = 1. Fijamos ahora un valor del parámetro t∈[0,1], y para cada r∈Nconsideramos ir= m´ın 0≤i≤n+r t−i n+r ,0≤ir≤n+r, de tal manera que cuando r→ ∞ (y ir→ ∞), ir n+r→t. Si logramos probar que, l´ım ir r+n→tr ir−j n+r ir=tj(1 −t)n−j,(3.2.3) 31 Capítulo 3. Operaciones con curvas de Bézier habremos finalizado la demostración. l´ım ir r+n→tr ir−j n+r ir= l´ım ir r+n→t r!ir!(r+n−ir)! (ir−j)!(r−ir+j)!(n+r)! 1 = l´ım ir r+n→t 2π√rirrriir r(r+n−ir)!eir−j+n+r 2πer+irq(ir−j)(n+r)(ir−j)ir−j(n+r)n+r(r−ir+j)! = l´ım i r+n→t en−j r n+r!r ir ir−j!irsrir (ir−j)(n+r) (ir−j)j(r+n−ir)! (n+r)n(r−ir+j)! 2 = l´ım ir r+n→t en−je−n+jsrir (ir−j)(n+r) (ir−j)j(r+n−ir)! (n+r)n(r−ir+j)! 3 = l´ım ir r+n→t (ir−j)j (n+r)n(r−ir+n)···(r−ir+j+ 1) = l´ım ir r+n→t (ir−j)j (n+r)n(n+r)n−j 1−ir n+r!··· 1−n+ir−j−1 n+r! = l´ım ir r+n→t (ir−j)j (n+r)n(1 −t)n−j(n+r)n−j = l´ım ir r+n→t ir−j n+r!j (1 −t)n−j= l´ım ir r+n→t ir n+r!j (1 −t)n−j=tj(1 −t)n−j. Por tanto, hemos demostrado que, fijado t∈[0,1], l´ım ir r+n→t b(r) ir= l´ım ir r+n→t"ir−r X j=0 bj n j!r ir−j n+r ir#= ir−r X j=0 bj n j!" l´ım ir r+n→tr ir−j n+r ir# = ir−r X j=0 bj n j!tj(1 −t)n−j=P(t). Dicho de manera informal, hemos probado que para cada t∈[0,1], el nodo i-ésimo del polígono inicial Pde grado nmás cercano a P(t), converge al valor P(t)al aumentar sucesivamente el grado del polinomio (es decir, cuando r→ ∞). La Figura 3.2 ilustra este hecho para una curva de grado 3. Se han incluido junto con el polígono original formado por cuatro puntos de control, los polígonos que se van obteniendo al elevar el grado hasta 6 veces. 32 3.3. Reducción del grado 3.3. Reducción del grado El proceso de elevación del grado resulta, en cierto modo, redundante, pues la curva está descrita mediante más información de la que realmente necesita. El proceso inverso puede resultar más interesante: Dada una curva de Bézier de grado ndefinida mediante los n+ 1 puntos de control b0,...,bn, ¿podemos encontrar una curva de Bézier de grado n−1definida mediante npuntos de control ˆ b0, ..., ˆ bn−1que la aproxime? Denominaremos a este aún hipotético algoritmo, reducción del grado. Supongamos que los bise obtuvieron a partir de los ˆ biempleando el proceso de elevación del grado descrito en la Sección 3.2. Entonces, según (3.2.1) debería ser, bi=i nˆ bi−1+n−i nˆ bi, i = 0, . . . , n. (3.3.1) De esta ecuación derivan dos fórmulas recursivas que expresan la generación de los ˆ bi a partir de bi, −→ bi=nbi−i−−→ bi−1 n−i, i = 0, . . . , n −1,(3.3.2) ←−− bi−1=nbi−(n−i)←− bi i, i =n, n −1, . . . , 1,(3.3.3) donde los −→ bise obtienen de despejar en (3.3.1) de izquierda a derecha, mientras que los ←− bise obtienen de despejar en (3.3.1) de derecha a izquierda. Además, de (3.3.2) y (3.3.3) se deduce que −→ b0=b0y←−− bn−1=bn. Observación 3.5. En las ecuaciones (3.3.2) y(3.3.3), aparecen dos términos indefinidos, −−→ b−1y←− bn. Sin embargo van precedidos de un factor multiplicativo nulo, por lo que ambas expresiones son coherentes. En la mayoría de las ocasiones, la reducción del grado no puede llevarse a cabo de forma exacta, por lo que es vista como un método de aproximación. Si la curva dada tiene grado n−1inicialmente, entonces −→ biy←− bi, i = 0, . . . , n −1,producirán ambas la curva original de grado n−1, pero al ser 3.3.2 y 3.3.3 fórmulas de extrapolación, son numéricamente inestables y por tanto lo más usual será obtener aproximaciones poco afinadas e inservibles. En la Figura 3.3 se puede intuir el hecho de que todos los vectores −→ bi−←− bison paralelos. Para verlo, debemos observar que los triángulos ←−− bi−1,−−→ bi−1,biy←− bi,−→ bi,bison similares. Demostración. Gracias a (3.3.2) y a (3.3.3), ←−− bi−1=(n−i)(bi−←− bi) + ibi i,−→ bi=(n−i)bi−i(−−→ bi−1−bi) n−i. 33 Capítulo 3. Operaciones con curvas de Bézier Figura 3.3: Ejemplo de reducción del grado. En azul la curva de Bézier cúbica a aproximar, en verde la curva de Bézier cuadrática que tiene por puntos de control los definidos mediante (3.3.2) y en rojo la curva de Bézier cuadrática que tiene por puntos de control los definidos mediante (3.3.3). Despejando se obtiene, bi−←− bi ←−− bi−1−bi =i n−i,−→ bi−bi bi−−−→ bi−1 =i n−i, por lo que, bi−←− bi ←−− bi−1−bi =−→ bi−bi bi−−−→ bi−1 , tal y como se quería probar. A continuación, se da una fórmula que permite calcular los nodos −→ bi, i = 0, . . . , n −1 a partir de b0,...,bi, i = 0, . . . , n −1. Corolario 3.6. −→ bi=1 n−1 i i X j=0 (−1)i+j n j!bj, i = 0, . . . , n −1. Demostración. Para i= 0, es obvio pues 1 n−1 0(−1)0 n 0!b0=b0=−→ b0. 34 3.3. Reducción del grado Supongamos que −→ bi=1 n−1 i i X j=0 (−1)i+j n j!bj. y veamos que −−→ bi+1 =1 n−1 i+1 i+1 X j=0 (−1)i+1+j n j!bj. Para ello, tan solo hay que tener en cuenta que, −−→ bi+1 =nbi+1 −(i+ 1)−→ bi n−i−1 =1 n−i−1"nbi+1 −i+ 1 n−1 i i X j=0 (−1)i+j n j!bj# =1 (n−1)! (i+1)!(n−i−2)!   n! (i+ 1)!(n−i−1)!bi+1 + i X j=0 (−1)i+j+1 n j!bj  =1 n−1 i+1" n i+ 1!bi+1 + i X j=0 (−1)i+j+1 n j!bj# =1 n−1 i+1 i+1 X j=0 (−1)i+1+j n j!bj. En la Figura 3.3 puede intuirse que (3.3.2) es una buena aproximación al polinomio de grado n= 3 cerca de b0y (3.3.3) de bn=b3. Es por esta razón por la que parece coherente combinar ambas expresiones, ˆ bi= (1 −λi)−→ bi+λi←− bi, i = 0, . . . , n −1. buscando así λi∈R, i = 0, . . . , n −1tales que los ˆ bigeneren el polinomio de grado n−1 que mejor aproxime al de grado ndado. La búsqueda de estos λi∈R, i = 0, . . . , n −1 no es sencilla. En primer lugar, es necesario expresar el polinomio de grado ndado en la base de los Polinomios de Chebyschev {T0(t), . . . , Tn(t)}, definidos en [−1,1], P(t) = n X i=0 tiTi(t), t ∈[−1,1]. Posteriormente se trunca el término de mayor grado tnTn(t),obteniendo así el único polinomio Qde grado n−1que dista del dado lo menos posible. Dicho de otro modo, encontramos así el polinomio Q∈Pn−1tal que m´ax −1≤t≤1||P(t)−Q(t)|| ≤ m´ax −1≤t≤1||P(t)−R(t)||,∀R∈Pn−1, 35 Capítulo 3. Operaciones con curvas de Bézier Figura 3.4: En negro, las curvas de la Figura 3.3. En rosa, aproximación mediante el polinomio de grado n−1=2definido por los nodos ˆ b0,ˆ b1yˆ b2donde λ0=1 25, λ1=1 2y λ2= 1. y se reescribe el polinomio resultante, de nuevo, en la base de los Polinomios de Bernstein. A este proceso se le conoce con el nombre de Economización de Chebyschev. Finalmente, se obtiene que los λióptimos vienen dados por, λi=1 22n−1 i X j=0 2n 2j!, i = 0, . . . , n −1.(3.3.4) No profundizaremos más en este resultado, pues excede en extensión al alcance de este trabajo. Para más información, consultar Eck (1993). La Figura 3.4 muestra la aproximación del ejemplo de la Figura 3.3 en color negro junto la aproximación mediante los λi definidos en (3.3.4) en rosa. 36 Capítulo 4 Splines en la forma de Bézier Si bien es cierto que las curvas de Bézier son de extrema utilidad en el ámbito del diseño, presentan numerosos problemas cuando la curva a aproximar tiene forma complicada. En este caso, su representación de Bézier tendrá grado alto, y en la práctica, polinomios de grado ≥10 resultan de una complejidad muy elevada (tal y como podrá apreciarse posteriormente en la Figura 5.5 del Capítulo 5). Un ejemplo de este suceso fue observado por Carl Runge al intentar aproximar la función f(x) = 1 1 + x2, x ∈[−5,5], mediante el polinomio Pnque interpola los nodos x(n) j=−5+10j n, j = 0, . . . , n, pues este presenta una oscilación de gran amplitud cerca de los extremos del intervalo. Además el error de interpolación tiende a infinito cuando crece el grado del polinomio (ver Epperson (1987)), l´ım n→∞ m´ax −5≤x≤5|f(x)−Pn(x)|=∞. Este problema desaparece al interpolar a trozos utilizando una partición cada vez más fina. De manera análoga, se pueden construir curvas de Bézier a trozos para evitar el uso de curvas polinómicas de grado tan elevado. 4.1. Parámetros globales y locales Definición 4.1. Dados u0<··· < uL,ui∈R,0≤i≤L, llamamos spline de Bézier con L trozos (o simplemente spline de Bézier a trozos) a toda aplicación continua s: [u0, uL]−→ R2, donde cada intervalo [ui, ui+1], i = 0, . . . , L −1,tiene por imagen un segmento de curva de Bézier. Llamaremos polígono de Bézier a trozos de sal conjunto formado por los polígonos de Bézier de todos los segmentos de curva. 37 Capítulo 4. Splines en la forma de Bézier Para cada valor del parámetro u∈[u0, uL]obtendremos un punto s(u)en la curva sy al mismo tiempo existirá un único subintervalo [ui, ui+1]para un iconcreto de tal manera que u∈[ui, ui+1]. Podemos introducir un parámetro local tipara cada intervalo [ui, ui+1], ti=u−ui ui+1 −ui =u−ui 4i .(4.1.1) De este modo tivaría desde 0hasta 1mientras uvaría desde uihasta ui+1. Para referirnos al i−ésimo segmento de s, emplearemos la notación side tal manera que para u∈[ui, ui+1],s(u) = si(ti), ti∈[0,1]. Tras la introducción de parámetros locales ti∈[0,1],0≤i≤L, la definición de las derivadas se transformaría en ds(u) du =dsi(ti) dti dti du =1 4i dsi(ti) dti .(4.1.2) 4.2. Condiciones de regularidad Supongamos que conocemos dos curvas de Bézier, s0ys1,definidas mediante los puntos de control b0,...,bnybn,...,b2nrespectivamente (las dos curvas pasan por el punto bn). Pensemos en cada una de ellas como una curva en si misma. Imaginemos que al mismo tiempo dichas curvas son segmentos de una única curva mayor sdefinida en un intervalo [u0, u2]y con imagen en R2. Supongamos sin pérdida de generalidad que la curva s0es el segmento de la izquierda definido en el intervalo [u0, u1]mientras que la curva s1es el segmento de la derecha definido en el intervalo [u1, u2]. Gracias a la Sección 3.1 sabemos que los dos polígonos b0,...,bnybn,...,b2n,han de ser el resultado de un proceso de subdivisión. Por tanto sus vértices han de estar relacionados mediante bn+i=bi n−i(t), i = 0, . . . , n, donde t=u2−u0 u1−u0 es la coordenada local de u2con respecto al intervalo [u0, u1]. Supongamos ahora que modificamos arbitrariamente b2n, produciendo así que las dos curvas no definan ya un mismo polinomio global s. Sin embargo, siguen coincidiendo en todas las derivadas de orden 0, . . . , n −1en el punto u=u1, pues b2nno ejerce influencia alguna en las derivadas de orden menor que nen dicho punto (ver Teoremas 2.6 y 2.10). De manera similar, podemos modificar los nodos b2n−1,...,b2n−ry seguir manteniendo la continuidad de todas las derivadas hasta la de orden n−r−1. Farin (1997) describe precisamente cómo hemos encontrado de este modo una condición necesaria y suficiente que han de cumplir las curvas de Bézier para tener regularidad Cr,0≤r < n. Definición 4.2. Sean dos curvas de Bézier s0ys1definidas en [u0, u1]y[u1, u2]respectivamente mediante los puntos de control b0,...,bnybn,...,b2n. Diremos que la curva 38 4.2. Condiciones de regularidad de Bézier sdefinida por s: [u0, u2]−→ R2 u−→ s(u) =            s0(t0) = s0 u−u0 u1−u0!, si u ∈[u0, u1], s1(t1) = s1 u−u1 u2−u1!, si u ∈[u1, u2], (4.2.1) es rveces continuamente diferenciable en u1si y solo si bn+i=bi n−i(t), i = 0, . . . , r, (4.2.2) donde t=u2−u0 u1−u0 es la coordenada local de u2con respecto al intervalo [u0, u1]y bi n−i(t) := i X j=0 bn−i+jBi j(t) = n X j=n−i bjBi j−n+i(t), i = 0, . . . , n −i. Se puede manejar otra condición de regularidad Cr, obtenida igualando las derivadas de s0ys1y aplicando la regla de la cadena. Gracias a (2.2.1) y a la Observación 2.7 se puede deducir que dks0 duk(t0) = n! (n−k)! n−k X i=0 4kbiBn−k i(t0)dkt0 duk, t0=u−u0 u1−u0 , dks1 duk(t1) = n! (n−k)! n−k X i=0 4kbn+iBn−k i(t1)dkt1 duk, t1=u−u1 u2−u1 . Tras reemplazar dkt0 dukydkt1 dukpor 1 u1−u0!k y 1 u2−u1!k respectivamente y evaluando en t0= 1 yt1= 0, dks0 duk(1) = n! (n−k)! n−k X i=0 4kbiBn−k i(1) 1 u1−u0!k , dks1 duk(0) = n! (n−k)! n−k X i=0 4kbn+iBn−k i(0) 1 u2−u1!k . Igualando el lado derecho de ambas expresiones, 4kbn−kBn−k n−k(1) 1 40!k =4kbnBn−k 0(0) 1 41!k , 39 Capítulo 4. Splines en la forma de Bézier cambio en uno de los vértices de control afecta a la curva entera. Es lo que se denomina un cambio global. Esto supone que si la curva de Bézier no se ajusta al contorno que quiere reproducir en una zona determinada, pero sí lo hace en otra, los cambios que se introduzcan en los puntos de control para mejorar la aproximación en la primera zona puedan destruir la buena aproximación ya conseguida en la segunda. Sin embargo, la modificación de un punto de control en un spline cuadrático de Bézier a trozos, va a afectar a lo sumo a tres de los segmentos de curva, lo que permite poder modificar algún punto de control para mejorar el ajuste en las zonas donde se observan mayores discrepancias sin afectar a las zonas en las que ya se ha conseguido un buen ajuste. Como una consecuencia de esta propiedad de control local, pueden introducirse segmentos rectilíneos dentro de los splines cuadráticos de Bézier a trozos con regularidad C1, pues si tres puntos de control consecutivos están alineados, el segmento de curva que definen ha de ser lineal. Esto no es posible si en su lugar empleamos una única curva de Bézier de grado elevado, pues no podrá contener fragmentos de recta a no ser que lo sea ella en sí misma. Estos splines se utilizan con frecuencia en el diseño de fuentes, tal y como se verá posteriormente en la Sección 5.1. 4.4. Splines de Bézier cúbicos a trozos con regularidad C2 Tal y como se hizo en la Sección 4.3, consideramos u0<··· < uL, ui∈R, i = 0, . . . , L, L ∈N,y los intervalos [ui, ui+1], i = 0, . . . , L −1,solo que esta vez con el propósito de construir s: [u0, uL]−→ R2spline cúbico de Bézier a trozos con regularidad C2, de tal manera que para u∈[ui, ui+1], con i= 0, . . . , L −1concreto, s(u) = si(ti) = si u−ui ui+1 −ui!=si u−ui 4i!. Por ser cúbico a trozos, si(ti) = 3 X j=0 b3i+jB3 j(ti;ui, ui+1), i = 0, . . . , L −1. Veamos qué condiciones deben establecerse sobre los nodos para conseguir la regularidad deseada, y cómo se construyen y relacionan entre sí. En primer lugar, consideremos dos segmentos de curva adyacentes, digamos si−1y sipara un i= 0, . . . , L −1concreto. Para conseguir regularidad C1en ui, los nodos adyacentes han de estar en la proporción 4i−1:4i, es decir, b3i=4i 4i−1+4i b3i−1+4i−1 4i−1+4i b3i+1, i = 1, . . . , L −1.(4.4.1) 46 4.4. Splines de Bézier cúbicos a trozos con regularidad C2 Para obtener regularidad C2, ha de existir un punto auxiliar dide tal manera que los nodos b3i−2,b3i−1,diydi,b3i+1,b3i+2 estén en la misma proporción 4i−1:4i, tal y como se deduce de las condiciones (4.2.5). Es por esto que, para i= 1, . . . , L −1, b3i−1= 4i 4i−1+4i!b3i−2+ 4i−1 4i−1+4i!di,(4.4.2) b3i−2= 4i−1 4i−2+4i−1!di−1+ 4i−2 4i−2+4i−1!b3i−1.(4.4.3) Reescribiendo (4.4.3) como b3i−1= 4i−1+4i−2 4i−2!b3i−2+ 4i−1 4i−2!di−1, y restando (4.4.3) de (4.4.2), obtenemos que b3i−2 4i−1+4i−2 4i−2−4i 4i−1+4i!=4i−1 4i+4i−1 di+4i−1 4i−2 di−1, o lo que es equivalente, b3i−2 4i−1 4i−2! 4i+4i−1+4i−2 4i−1+4i!=4i−1 4i+4i−1 di+4i−1 4i−2 di−1. Llamando, Γi=4i+4i−1+4i−2(4.4.4) y despejando b3i−2obtenemos que, b3i−2=4i−2 Γi di+4i−1+4i Γi di−1.(4.4.5) Finalmente, introducimos este valor en (4.4.2) para obtener así b3i−1=4i−2+4i−1 Γi di+4i Γi di−1.(4.4.6) Juntando las condiciones (4.4.1), (4.4.5) y (4.4.6), se consiguen las expresiones de todos 47 Capítulo 4. Splines en la forma de Bézier los nodos del polígono del spline de Bézier cúbico a trozos, b0=d−1, b1=d0, b2=41 40+41 d0+40 41+40 d1, ... b3i=4i 4i−1+4i b3i−1+4i−1 4i−1+4i b3i+1, i = 1, . . . , L −1, b3i−1=4i−2+4i−1 Γi di+4i Γi di−1, i = 2, . . . , L −1, b3i−2=4i−2 Γi di+4i−1+4i Γi di−1, i = 2, . . . , L −1, ... b3L−2=4L−1 4L−1+4L−2 dL−1+4L−2 4L−1+4L−2 dL, b3L−1=dL, b3L=dL+1, (4.4.7) empleando la misma notación que la mencionada en la Observación 4.3. De manera análoga al caso de splines de Bézier cuadráticos a trozos con regularidad C1, la partición del espacio parámetrico, u0<··· < uL, junto al polígono formado por d−1,...,dL+1, determinan completamente los splines de Bézier cúbicos a trozos con regularidad C2. La Figura 4.6 muestra las proporciones de los parámetros de un spline cúbico de Bézier a trozos con regularidad C2. En ella aparecen, además de los parámetros, los nodos b0,...,b3Len negro y el polígono que los une en naranja, los nodos d−1,...,dL+1 en rojo y el polígono que los une en azul. Los trozos de curva en diferentes colores. La Figura 4.7 muestra un ejemplo de spline de Bézier cúbico con 3 trozos y regularidad C2. En negro los nodos b0,...,b9y el polígono que los une en azul. En rojo los nodos d−1,...,d4y el polígono que los une en naranja. Los trozos de curva en diferentes colores. 48 4.4. Splines de Bézier cúbicos a trozos con regularidad C2 Figura 4.6: Ejemplo que muestra las proporciones de los parámetros en un spline cúbico a trozos con regularidad C2. Figura 4.7: Ejemplo de spline de Bézier cúbico definido mediante tres trozos con regularidad C2. 49 Capítulo 4. Splines en la forma de Bézier 50 Capítulo 5 Ejemplos prácticos: diseño mediante splines de Bézier a trozos En los capítulos anteriores, se ha mencionado la utilidad de las curvas de Bézier y de los splines de Bézier a trozos en el diseño gráfico y asistido por ordenador. Si bien es cierto que las funciones bez_cubatrozos.m ybspline_cubico.m programadas en MATLAB® (ver Funciones 11, 12 del Apéndice A), cuyas primeras líneas son, function [] = bez_cubatrozos(b,u); function [] = bspline_cubico(d,u); permiten aproximar diseños mediante splines de Bézier cúbicos a trozos (en el caso de bspline_cubico.m, con regularidad C2), es necesario conocer una aproximación previa de los nodos b0,...,b3L, en el caso de la primera función y de d−1,d0,...,dL,dL+1,en el caso de la segunda, para poder efectuar la interpolación de los mismos. Existen diversas herramientas que permiten elegir interactivamente dichos nodos, como por ejemplo, las funciones del paquete MuPAD de MATLAB®. A su vez, el programa GeoGebra resulta ser especialmente rápido y sencillo, pues al arrastrar cualquier nodo por la pantalla, actualiza su valor automáticamente. De este modo, podremos considerar puntos en las figuras a interpolar, definir en ellos splines de Bézier a trozos, y desplazar manualmente los nodos hasta que las curvas se aproximen lo máximo posible al contorno del dibujo. El programa GeoGebra se ha utilizado, por tanto, como herramienta auxiliar para determinar los nodos de los polígonos, pero se ha utilizado MATLAB®para construir funciones que construyen y dibujan los splines de Bezier a trozos, a partir de un conjunto de nodos dado. En este capítulo se muestran dos ejemplos en los que se han utilizado splines de Bézier a trozos con y sin regularidad C2para aproximar dos curvas dadas: 1. El contorno de la letra Sde la tipografía Times New Roman©(Figura 5.1 (a)). 2. Una firma (Figura 5.8). 51 Capítulo 5. Ejemplos prácticos: diseño mediante splines de Bézier a trozos Observación 5.1. Durante el resto del capítulo, se considerará 0 = u0<··· < uL=L. Se ha considerado de esta forma para que 4i=ui+1 −ui=i+1−i= 1, i = 0, . . . , L −1. Para cada trozo de curva se considerará el parámetro tidefinido en la ecuación (4.1.1), de tal manera que para u∈[i, i + 1] se tendrá que ti∈[0,1]. 5.1. Splines de Bézier a trozos al diseñar la letra S Antes de iniciar el proceso de interpolación, es necesario destacar que en la letra que queremos representar sólo existen unos pocos puntos angulosos en los extremos de la figura (ver Figura 5.1 (a)), por lo que buscaremos regularidad en la curva aproximante. 5.1.1. Aproximación mediante splines de Bézier cúbicos considerando 24 nodos, sin imponer condiciones de regularidad Comenzamos construyendo un spline de Bézier cúbico formado por 6 trozos para recuperar el contorno curvo de la letra S. Para ello fijamos 6 polígonos de Bézier de manera que cada uno esté formado por dos puntos sobre el contorno de la letra, que denotaremos por Ay que serán los extremos de cada curva, y por dos puntos alejados del contorno, que denotaremos por B. Tendremos entonces dos grupos de 10 nodos según la secuencia ABBABBABBA, para determinar dos splines de Bézier cúbicos de 3 trozos cada uno, y cuatro nodos más para los segmentos rectilíneos representados en color azul en la Figura 5.1 (b), lo que hace un total de 24 nodos. Definiendo un segmento de curva de Bézier para cada cuaterna de nodos mediante el comando de GeoGebra Bi_{x}= {x(b_{i}),x(b_{i+1}),x(b_{i+2}),x(b_{i+3})} Bi_{y}= {y(b_{i}),y(b_{i+1}),y(b_{i+2}),y(b_{i+3})} elemento(Bi_{x},1)*(1−x)^3+ elemento(Bi_{x},2)*3*(1−x)^2*x+ elemento(Bi_{x},3)*3*(1−x)*x^2+ elemento(Bi_{x},4)*x^3 elemento(Bi_{y},1)*(1−x)^3+ elemento(Bi_{y},2)*3*(1−x)^2*x+ elemento(Bi_{y},3)*3*(1−x)*x^2+ elemento(Bi_{y},4)*x^3 curva(fi(u),gi(u),u,0,1) obtenemos la Figura 5.1 (c). Los segmentos de curva obtenidos apenas se asemejan al contorno original. Sin embargo, utilizando las ya mencionadas facilidades que ofrece el programa GeoGebra, hemos desplazado las posiciones de los puntos de control de la forma B(los que no están sobre el contorno de la letra) para obtener una aproximación mejor, como muestra la Figura 5.2 (a). 52 5.1. Splines de Bézier a trozos al diseñar la letra S (a) Imagen de partida. (b) Selección de los nodos según la secuencia ABBABBABBA. (c) Comienzo del proceso de interpolación mediante splines de Bézier cúbicos empleando 24 nodos. Figura 5.1: Inicio del proceso de interpolación. (a) Imagen inicial junto a los puntos de control (en azul) y al spline de Bézier cúbico a trozos que interpola a la letra S. (b) Spline de Bézier cúbico a trozos junto al polígono de Bézier asociado. (c) Spline de Bézier cúbico a trozos que interpola a la letra S. Figura 5.2: Interpolación mediante splines de Bézier cúbicos a trozos considerando 24 nodos, sin imponer condiciones de regularidad, tras modificar los nodos tipo B. 53 Capítulo 5. Ejemplos prácticos: diseño mediante splines de Bézier a trozos La aproximación conseguida es bastante similar a la letra original, pero ¿y si repetimos el proceso anterior aumentando esta vez el número de nodos considerado? 5.1.2. Aproximación mediante splines de Bézier cúbicos a trozos considerando 40 nodos, sin imponer condiciones de regularidad Si consideramos 40 nodos en lugar de 24, obtenemos como resultado la Figura 5.3. (a) Imagen inicial junto a los puntos de control (en azul) y al spline de Bézier cúbico a trozos que interpola a la letra S. (b) Spline cúbico de Bézier a trozos junto al polígono de Bézier asociado. (c) Spline cúbico de Bézier a trozos que interpola a la letra S. Figura 5.3: Interpolación mediante splines de Bézier cúbicos a trozos considerando 40 nodos, sin imponer condiciones de regularidad. La Figura 5.3(a) muestra una aproximación notablemente mejor que la anterior (es lógico, pues hemos efectuado un proceso de subdivisión) y aparentemente buena. Por esta razón podríamos pensar, ¿y si en vez de emplear splines de Bézier cúbicos, optamos por emplear splines de Bézier cuadráticos para aproximar la imagen? 54 5.1. Splines de Bézier a trozos al diseñar la letra S 5.1.3. Aproximación mediante splines de Bézier cuadráticos a trozos considerando 35 nodos, sin imponer condiciones de regularidad En este caso, consideramos 35 nodos según la secuencia ABABA, . . . , ABA (el polígono de Bézier de cada segmento de curva tiene ahora tres puntos de control: dos sobre la curva y uno exterior), y ejecutamos para cada trío de nodos, el comando Bi_{x}= {x(b_{i}),x(b_{i+1}),x(b_{i+2})} Bi_{y}= {y(b_{i}),y(b_{i+1}),y(b_{i+2})} elemento(Bi_{x},1)*(1−x)^2+ elemento(Bi_{x},2)*2*(1−x)*x+ elemento(Bi_{x},4)*x^2 elemento(Bi_{y},1)*(1−x)^2+ elemento(Bi_{y},2)*2*(1−x)*x+ elemento(Bi_{y},4)*x^2 curva(fi(u),gi(u),u,0,1) obteniendo así la Figura 5.4. De nuevo se han representado en color azul los puntos de control y se han utilizado distintos colores para los diferentes trozos de curva. (a) Imagen inicial junto a los puntos de control (en azul) y al spline de Bézier cuadrático a trozos que interpola a la letra S. (b) Spline de Bézier cuadrático a trozos junto al polígono de Bézier asociado. (c) Spline de Bézier cuadrático a trozos que interpola a la letra S. Figura 5.4: Interpolación mediante splines de Bézier cuadráticos a trozos considerando 35 nodos, sin imponer condiciones de regularidad. En este caso, comienzan a apreciarse puntos angulosos nada deseables en el diseño de esta letra. No parece que la misma se haya llevado a cabo mediante un único trazo tal y como cabría esperar de la imagen original. Parece que bajar el grado no ha proporcionado un resultado favorable, ¿y subirlo? 55 Capítulo 5. Ejemplos prácticos: diseño mediante splines de Bézier a trozos Figura 5.11: Interpolación mediante splines de Bézier cúbicos a trozos sin imponer condiciones de regularidad (observar los ángulos que se forman en los puntos en los que se produce cambio de color). 62 5.2. Splines de Bézier a trozos al diseñar una firma 5.2.2. Aproximación mediante splines de Bézier cúbico a trozos imponiendo condiciones de regularidad C2 Partimos de los puntos azules d−1,d0,...,dL,dL+1, y determinamos, de manera única, los nodos grises b0,...,bn, mediante las condiciones establecidas en (4.4.7). El resultado final es el que se muestra en la Figura 5.12. Figura 5.12: Imagen original junto al polígono y spline cúbico de Bézier a trozos con regularidad C2que aproxima la firma. 63 Capítulo 5. Ejemplos prácticos: diseño mediante splines de Bézier a trozos 5.2.3. Mediante funciones en MATLAB® Una vez obtenida la aproximación descrita en la Subsección 5.2.2, hemos exportado el valor de los nodos d−1,d0,...,dL,dL+1,que en la Figura 5.12 aparecen en color azul y ejecutamos la función bspline_cubico.m de MATLAB®(ver el código en la función 12 del Apéndice A) con dichos valores, para obtener la Figura 5.13, la cual muestra la misma aproximación que aparece en la Figura 5.12. La Figura 5.14 muestra esta misma aproximación pero mostrando también el polígono asociado al spline cúbico de Bézier con regularidad C2que aproxima la firma. Figura 5.13: Spline cúbico de Bézier a trozos con regularidad C2que aproxima la firma, empleando la función de MATLAB®bspline_cubico.m (ver Anexo A, Función 12). 64 5.2. Splines de Bézier a trozos al diseñar una firma Figura 5.14: Polígono y spline cúbico de Bézier a trozos con regularidad C2que aproximan la firma, empleando la Función de MATLAB®bspline_cubico.m (ver Anexo A, función 12). Misma aproximación que en la Figura 5.12 65 Capítulo 5. Ejemplos prácticos: diseño mediante splines de Bézier a trozos 5.2.4. Mediante el programa InkScape El programa InkScape está destinado explícitamente al diseño gráfico y emplea splines de Bézier cúbicos a trozos para aproximar dibujos. Estos vienen implícitamente definidos, y el diseñador tan solo tiene que escoger los nodos d−1,d0,...,dL,dL+1 y ajustarlos adecuadamente al contorno del dibujo. Hemos exportado los nodos d−1,d0,...,dL,dL+1, que han sido aproximados con GeoGebra en la Subsección 5.2.2 y ya empleados para hallar las Figuras 5.13 y 5.14, y los hemos introducido en el programa InkScape para obtener las Figuras 5.16 y 5.15, las cuales muestran la misma aproximación solo que en la segunda se ha dejado el polígono asociado al spline cúbico de Bézier que aproxima la firma de manera ilustrativa. Figura 5.15: Spline cúbico de Bézier a trozos con regularidad C2que aproxirma la firma mediante el programa de diseño gráfico InkScape. Como cabría esperar, se ha obtenido el mismo ajuste que en las Figuras 5.12, 5.13 y 5.14, al emplearse para los tres casos el mismo polígono d−1,...,dL+1. 66 5.2. Splines de Bézier a trozos al diseñar una firma Figura 5.16: Misma aproximación que la que muestra la Figura 5.15 empleando también el programa de diseño gráfico InkScape pero mostrando junto al spline cúbico de Bézier a trozos con regularidad C2, el polígono de Bézier asociado. 67 Capítulo 5. Ejemplos prácticos: diseño mediante splines de Bézier a trozos 68 Bibliografía Cheney, E. W. (1982). Introduction to Approximation Theory (Second ed.). AMS Chelsea Pub. Deuflhard, P., y Hohmann, A. (2003). Numerical Analysis in Modern Scientific Computing: An Introduction (Second ed.). Springer. Eck, M. (1993). Degree reduction of Bézier curves. Computer Aided Geometric Design, 10(3), 237 - 251. Epperson, J. F. (1987). On the Runge Example. The American Mathematical Monthly, 94(4), 329 - 341. Farin, G. (1990). Curves and Surfaces for Computer Aided Geometric Design: A Practical Guide (Second ed.). Academic Press. Farin, G. (1997). Curves and Surfaces for Computer Aided Geometric Design: A Practical Guide (Fourth ed.). Academic Press. 69 Bibliografía 70 Apéndice A Código de los programas más significativos en MATLAB® 1. Función que evalúa el polinomio de Bernstein Bn i(t;a, b)en t∈[a, b]concreto. function [r]=bernstein_pol(a,b,n,i,t); r = nchoosek(n,i)*power(b−a,−n)*power(b−t,n−i)*power(t−a,i); end 2. Función que evalúa el polinomio cúbico P(t) = 3 X i=0 biB3 i(t;a, b)en t∈[a, b]concreto. function [q] = bez_cub(b0,b1,b2,b3,t,a,b); c = [b0,b1,b2,b3]; q = zeros(2,1); for i = 0:3, q = q + c(:,i+1)*bernstein_pol(a,b,3,i,t); end end 3. Función que construye los polinomios parciales bk i(t;a, b), i = 0, . . . , n−ksiguiendo la fórmula de recurrencia (2.1.1) y devuelve el valor de bn 0(t;a, b)para t∈[a, b] concreto. function [r]=valor_algoritmo_ab(c,t,a,b); %c es la matriz que contiene los nodos de Bezier b0,...,bn %t valor del parametro a evaluar (t en [a,b]). n = size(c,2); mx = zeros(n,n); %Matriz auxiliar para abscisas my = zeros(n,n); %Matriz auxiliar para ordenadas mx(:,1)=c(1,n:−1:1); my(:,1)=c(2,n:−1:1); lambdat = (t−a)/(b−a); for j = 2:n 71 Apéndice A. Código de los programas más significativos en MATLAB® legendInfo{2} = ['Poligono de Bezier']; for k = 1:L, plot(q(k,:,1),q(k,:,2)); %Curva de Bezier legendInfo{k+2} = ['Trozo de curva de Bezier ' num2str(k)]; end legend(legendInfo); hold off else error('Las dimensiones no encajan. Introduzca u y b con ... size(u)=[1,L+1] y size(b)=[2,3*L+1], L natural.'); end end 12. Spline cúbico de Bézier para Ltrozos con regularidad C2.Función que crea el spline cúbico de Bézier s(u)con Ltrozos, definido en u0< u1<··· < uL. Para ello, emplea los puntos d−1,...,dL+1 introducidos por el usuario en la matriz d. function [] = bspline_cubico(d,u); %d es una matriz de dimensiones 2xL+3, que tiene los nodos ... d_−1,...,d_L %u es un vector de dimension n+1, que tiene los puntos u_0<...<u_L L1 = size(d,2)−3; L2 = length(u)−1; if (L1 == L2) L = size(d,2)−3; figure(1) clf hold on b = zeros(2,3*L+1); Delta = zeros(L); for i = 1:L, Delta(i) = u(i+1)−u(i); end %Igualamos las primeras y ultimas condiciones. b(:,1) = d(:,1); b(:,2) = d(:,2); p = Delta(1)+Delta(2); b(:,3) = (Delta(2)/p)*d(:,2)+(Delta(1)/p)*d(:,3); r = Delta(L−1)+Delta(L); b(:,3*L−1) = (Delta(L)/r)*d(:,L+1)+(Delta(L−1)/r)*d(:,L+2); b(:,3*L) = d(:,L+2); b(:,3*L+1) = d(:,L+3); for i=2:L−1, q0 = Delta(i−1)+Delta(i); q1 = Delta(i+1)+Delta(i); q2 = Delta(i−1)+Delta(i)+Delta(i+1); b(:,3*i−1) = (q1/q2)*d(:,i+1) + (Delta(i−1)/q2)*d(:,i+2); b(:,3*i) = (Delta(i+1)/q2)*d(:,i+1) + (q0/q2)*d(:,i+2); end 78 for i=1:L−1, q3 = Delta(i)+Delta(i+1); b(:,3*i+1) = (Delta(i+1)/q3)*b(:,3*i)+... (Delta(i)/q3)*b(:,3*i+2); end cont = 1; for i = 1:L, t(i,:) = linspace(u(i),u(i+1),1000); for j = 1:1000, q(i,j,:) = bez_cub(b(:,cont),b(:,cont+1),b(:,cont+2),... b(:,cont+3),t(i,j),u(i),u(i+1)); end cont = cont + 3; end plot(b(1,:),b(2,:),'k*'); %Puntos de control plot(b(1,:).',b(2,:).','LineWidth',1.5); %Poligono de Bezier plot(d(1,:),d(2,:),'ro'); %Puntos de control plot(d(1,:).',d(2,:).','LineWidth',0.6); %Poligono de Bezier legendInfo{1} = ['b_{0},...,b_{3L}']; legendInfo{2} = ['Poligono de Bezier']; legendInfo{3} = ['d_{−1}, . . . ,d_{L+1}']; legendInfo{4} = ['Poligono del Spline cubico']; for k = 1:L, plot(q(k,:,1),q(k,:,2)); legendInfo{k+4} = ['Trozo de spline de Bezier s_' ... num2str(k)−1]; end legend(legendInfo); hold off else error('Las dimensiones no encajan. Introduzca u y d con ... size(u)=[1,L+1] y size(d)=[2,L+3], L natural.'); end end 79