Lucrarea nr.7

Curbe de aproximare si interpolare:
Curbe Bezier

[ Prev ] Lucrarea 7 [ Next ]

Descriere

Implementare

Aplicatii

A.Descriere

1. Puncte de control

Ecuatiile analitice ale curbelor care descriu formele diverselor obiecte reale sunt de cele mai multe ori deosebit de complicate. In aceasta situatie este insa suficient sa cunoastem un set de puncte ale curbei respective si sa incercam sa conectam aceste puncte printr-o curba a carei ecuatie analitica este in general simpla. Aceste puncte le vom numi in continuare puncte de control.

In grafica pe calculator, ceea ce prezinta interes in primul rand este aspectul vizual al curbei reprezentate si mai putin proprietatile sale matematice. Pronind de la un set de puncte de control, constructia unei curbe controlate de acestea poate fi realizata utilizand metode de interpolare sau de aproximare. In primul caz, curba obtinuta va trece prin punctele de control. In cel de-al doilea caz, curba nu va mai trece in mod necesar prin punctele de control ci prin vecinatatea acestora:

2. Curbe Bezier

O curba Bezier plana este o curba neteda care este definita prin n puncte specificate prin coordonatele carteziene X_i, Y_i. In forma parametrica, este data de ecuatiile:

Functiile B_k,m sunt functii polinomiale Bernstein:

Se observa ca x(0) = x₁, x(1) = x_n, y(0) = y_1, y(1) = y_n, deci curba porneste de la primul punct de control si sfarseste la ultimul.

Curba Bezier nu trece in mod necesar prin alt punct de control dar are proprietatea de a se mentine tot timpul in interiorul poligonului convex definit de aceste puncte.

Utilizand o secventa de curbe Bezier de grad 3 se obtine o curba de aproximare formata din portiuni avand proprietatea de a trece prin punctele P_i si P_i+3 ale setului de puncte din control panta tangentei la curba in punctul P_i+3, ceea ce permite constructia unei curbe ce trece printr-un set de puncte avand forma controlata de punctele intermediare:

Prin alegerea punctelor P₂, P₃, P₄ coliniare se va obtine aspectul neted al curbei in P₃.

Utilizand forma parametrica cu 0 <= t <=1 pentru fiecare curba componenta C_i determinata de punctele [P_i, P_i+1, P_i+2, P_i+3], vom avea:

Atunci cand parametrul t parcurge intervalul [0,1], formula de mai sus furnizeaza punctele curbei dintre punctul corespunzator punctului de control P_i si cel corespunzator lui P_i+1. Curba finala se obtine prin trasarea segmentelor de curba pentru valorile i=1, i=4, …, i=3*(j-1)+1.

B. Implementare

/*======================================================================*/
/* G2Dcurbe.h                                                           */
/*======================================================================*/
/* contine rutine pentru trasarea curbelor Bezier                       */
/*----------------------------------------------------------------------*/

/*
 * Traseaza curba Bezier generala controlata de un set de puncte de
 * control incluse in fisierul "nume_set"; curba este aproximata
 * prin 'ns' segmente de dreapta.
 */
extern void curba_Bezier (char *nume_set, int ns);


/*======================================================================*/
/* End of G2Dcurbe.h                                                    */
/*======================================================================*/

/*======================================================================*/
/* G2Dcurbe.c                                                           */
/*======================================================================*/
/* contine rutine pentru trasarea curbelor Bezier                       */
/*----------------------------------------------------------------------*/
#include <stdio.h>
#include <errno.h>


#include "G2Dnucleu.h"
#include "G2Dprimitive.h"

#include "G2Dcurbe.h"

static lista_puncte lista;

#define MAXB 20
typedef double coeficienti[MAXB];

static coeficienti coef_bezier;

/* Prototipuri Private -------------------------------------------------*/

static void citeste_puncte (char *nume_set);

static void traseaza (int ns);

static void calculeaza_coeficienti (int m);

static void punct_Bezier (double t, double *px, double *py);

static double valoare (int m, int k, double t);

/* Rutine Publice ------------------------------------------------------*/

/*
 * Traseaza curba Bezier generala controlata de un set de puncte de
 * control incluse in fisierul "nume_set"; curba este aproximata
 * prin 'ns' segmente de dreapta.
 */
void
curba_Bezier (char *nume_set, int ns)
{
   citeste_puncte (nume_set);
   traseaza (ns);
} /* curba_Bezier */


/* Rutine Private ------------------------------------------------------*/

static void
citeste_puncte (char *nume_set)
{
   /*
    * Citeste punctele de control din fisierul text cu numele dat de
    * parametrul nume_set si le stocheaza in variabila 'lista'
    */
} /* citeste_puncte */


/*
 * Se considera domeniul de variatie al parametrului ca fiind
 * impartit intr-un numar de 'ns' intervale egale; se calculeaza
 * punctele curbei in capetele subintervalelor si se unesc
 * prin segmente de dreapta.
 */
static void
traseaza (int ns)
{
   double x1, y1;
   double x2, y2;
   int i;

   if (lista.n > 0)
   {
      calculeaza_coeficienti (lista.n-1);
      punct_Bezier (0.0, &x1, &y1);
      for (i = 0; i < ns; i++)
      {
         punct_Bezier ((i+1.0)/ns, &x2, &y2);
         linie_2d (x1, y1, x2, y2);
         x1 = x2; y1 = y2;
      }
   }
} /* traseaza */




static void
calculeaza_coeficienti (int m)
{
   int k;

   coef_bezier[0] = 1.0;
   for (k = 1; k < (m+1); k++)
   {
      coef_bezier[k] = coef_bezier[k-1] * (m-k+1) / k;
   }
} /* calculeaza_coeficienti */



static void
punct_Bezier (double t, double *px, double *py)
{
   double bv;
   int k, m;

   *px = 0.0; *py = 0.0;
   m = lista.n - 1;
   for (k = 0; k < (m+1); k++)
   {
      bv = valoare (m, k, t);
      *px += bv * lista.x[k];
      *py += bv * lista.y[k];
   }
} /* punct_Bezier */



static double
valoare (int m, int k, double t)
{
   double bv;
   double v;
   int i;

   bv = coef_bezier[k];
   for (i = 1; i <= k; i++)
   {
      bv *= t;
   }

   v = 1.0 - t;
   for (i = 1; i <= m-k; i++)
   {
      bv *= v;
   }

   return (bv);
} /* valoare */


/*======================================================================*/
/* End of G2Dcurbe.c                                                    */
/*======================================================================*/

Download G2Dcurbe.h, G2Dcurbe.c.

C. Aplicatii

1. Sa se elaboreze unitatea G2Dcurbe.
2. Sa se execute procedura obtinuta pentru un set de date de forma:

a) 0,20 5,15 10,10 12,12 15,-1 20,-10 25,-15 30,-10 35,10 

b) 5,20 10,15 15,20 20,0 25,-5 22,7 18,-5 15,0 22,10 30,15 35,20

c) 30,40 25,35 20,25 25,15 30,10 35,8 40,15 45,5 40,35 35,37 30,40 (curba inchisa)

3. Sa se urmareasca efectul pe care il are asupra curbei modificarea unuia din punctelor de control trasand cele doua curbe obtinute suprapuse.
4. Se va observa proprietatea curbei de a fi continuta in poligonul convex definit de punctele de control, reprezentand pe ecran acest poligon. Pe baza acestei proprietati scrieti o procedura care determina fereastra minima care incadreaza curba. Reprezentati sistemul de axe de coordonate.
5. Sa se construiasca si sa se implementeze procedura pentru desenarea curbelor formate din secvente de curbe elementare Bezier de ordinul 3, dupa cum se prezinta in text. Reluati exemplele de la punctul 2.

[ Home ][ Up ][ Previous ][ Next ]

Send mail to sorin@aspc.cs.utt.ro with questions or comments about this web site.
Copyright © 2000 Graphics Laboratory
Last modified: