Lucrarea nr. 4
Operatii de decupare (clipping)

A.Descriere

1.Necesitatea operatiei de clipping

Pe parcursul executiei unei aplicatii grafice in orice moment sunt active o fereastra si un port de vedere. Sistemul grafic asigura ca imaginile elementelor grafice continute in fereastra activa vor fi produse in zona ecran definita de portul de vedere curent pe baza unei transformari de coordonate numita transformare de vizualizare. Aceasta transformare mapeaza (aplica) continutul ferestrei pe zona portului de vedere. In acest proces nu se verifica daca punctul supus tranformarii este sau nu in interiorul ferestrei. Punctul ecran corespunzator unui punct din exteriorul ferestrei este plasat de transformarea de vedere in afara portului activ, sau chiar in afara spatiului ecranului. Aceste situatii trebuie deci evitate prin introducerea unei etape intermediare in procesul reprezentarii elementelor grafice.

In momentul in care utilizatorul defineste o fereastra, in mod implicit este stabilit si un sistem de coordonate cartezian. Elementele componente ale unei scene grafice se raporteaza la acest sistem de coordonate. In raport cu fereastra, elementele grafice pot fi continute total, exterioare sau se pot intersecta.

Transformarea de vizualizare trebuie aplicata si asupra acelor elemente sau portiuni de elemente care sunt incluse in fereastra activa. Operatia de prelucrarea a unei scene grafice in urma carei sunt eliminate portiunile care nu se incadreaza in fereastra activa poarta numele de clipping. Algoritmii de clipping trebuie sa stabileasca pentru fiecare element grafic al scenei portiunile care se incadreaza in fereastra activa iar pe celelalte sa le indeparteze.

Procedurile de reprezentare a elementelor grafice vor face aple la operatia de clipping inaintea aplicarii transformarii de vizualizare, asigurand in acest fel ca elementele grafice vor fi produse in interiorul portului de vedere activ.

2. Clipping pentru segmente de dreapta

Unul dintre algoritmii cei mai des utilizati pentru clipping-ul segmentelor de dreapta este algoritmul Cohen-Sutherland.

Vom considera ca fereastra activa este definita de 4 valori reale: xmin, ymin, xmax, ymax. Un punct P(x, y) definit in coordonate utilizator este in interiorul ferestrei (deci vizibil) daca indeplineste relatiile :

	xmin <= x <= xmax
	ymin <= y <= ymax

Aceste relatii trebuie in principiu verificate pentru fiecare punct al segmentului, ceea ce evident, este imposibil. Algoritmul de clipping Cohen-Sutherland porneste de la determinarea pozitiei relative a segmentului fata de fereastra. Exista 4 posibilitati:

1. ambele capete ale segmentului sunt in interiorul ferestrei
2. un capat al segmentului este in interior iar celelalt in exterior
3. ambele capete ale segmentului sunt exterioare ferestrei, dar segmentul intersecteaza fereastra
4. ambele capete sunt in exteriorul ferestrei dar segmentul nu intersecteaza fereastra

Planul utilizator este impartit in 9 regiuni carora li se asociaza cate un cod unic, format din 2 valori intregi (0 respectiv 1) conform figurii:

Unui punct oarecare P(x, y) i se asociaza codul de regiune (b3, b2, b1, b0) al zonei in care este plasat astfel:

se seteaza initial: b3=b2=b1=b0=0 si apoi daca

x < xmin

-> b3=1

x > xmax

-> b2=1

y < ymin

-> b1=1

y > ymax

-> b0=1

Se determina cate un cod de regiune pentru cele doua capete ale segmentului, punctele P1 respectiv P2. In continuare se face un test pentru a determina daca segmentul nu este in totalitate in afara ferestrei. Daca nu, se vor translata capetele segmentului care sunt exterioare ferestrei pana la cea mai apropiata frontiera a ferestrei. In acest scop se va determina intersectia segmentului cu frontierele ferestrei dupa modelul urmator:

Descrierea algoritmului este urmatoarea:

1. Determina codurile de regiune pentru punctele P1, P2
2. Cele doua coduri sunt insumate logic (OR).
   Daca rezultatul este codul (0,0,0,0) segmentul este complet interior si este acceptat. EXIT. Altfel treci la pasul 3.
3. Cele doua coduri sunt inmultite logic (AND). Daca rezultatul este diferit de codul (0,0,0,0) segmentul este complet in afara ferestrei si este eliminat. EXIT. Altfel treci la pasul 4.
4. Se alege codul unui capat al segmentului. Daca acesta este codul (0,0,0,0) se alege celalalt cod.
5. Se inspecteaza codul in ordinea b3, b2, b1, b0 pentru a determina primul element b _i = 1 care precizeaza frontiera ferestrei fata de care punctul este exterior.
6. Se calculeaza intersectia segmentului cu acea frontiera si se inlocuieste punctul cu intersectia determinata.
7. Se trece la pasul 1.

B. Implementare

In cadrul acestei lucrari se va realiza:

• modificarea procedurii punct_2d pentru excluderea punctelor din exteriorul ferestrei
• implementarea algoritmului de clipping pentru segmente de dreapta
• includerea operatiei de clipping in procedura linie_2d.

Se vor aduce urmatoarele modificari la modulul G2Dnucleu:

/* Margini */
#define STANGA 8
#define DREAPTA 4
#define JOS 2
#define SUS 1

typedef unsigned int cod_regiune;

static void clip_segment (double x1, double y1, double x2, double y2,
double *x1c, double *y1c, double *x2c, double *y2c);

static cod_regiune det_cod (double x, double y);


void
punct_2d (double x, double y)
{
   int dcx, dcy;

   if ((window.xmin <= x) && (x <= window.xmax) &&
       (window.ymin <= y) && (y <= window.ymax))
   {
      user_to_out (x, y, &dcx, &dcy);
      PutPixel (dcx, dcy);
   }
} /* punct_2d */


void
linie_2d (double x1, double y1, double x2, double y2)
{
#define EPS 0.0001
   double x1c, y1c;
   double x2c, y2c;
   int dcx1, dcy1;
   int dcx2, dcy2;

   clip_segment (x1, y1, x2, y2, &x1c, &y1c, &x2c, &y2c);
   if ((fabs (x2c-x1c) > EPS) || (fabs (y2c-y1c) > EPS))
   {
      user_to_out (x1c, y1c, &dcx1, &dcy1);
      user_to_out (x2c, y2c, &dcx2, &dcy2);
      Line (dcx1, dcy1, dcx2, dcy2);
   }
} /* linie_2d */



static void
clip_segment (double x1, double y1, double x2, double y2,
   double *x1c, double *y1c, double *x2c, double *y2c)
{
   cod_regiune cod;
   cod_regiune cod1;
   cod_regiune cod2;
   double x, y;

   cod1 = det_cod (x1, y1);
   cod2 = det_cod (x2, y2);

   while (cod1 != 0 || cod2 != 0)
   {
      if (cod1 & cod2)
      {
         *x1c = 0.0; *y1c = 0.0;
         *x2c = 0.0; *y2c = 0.0;
         return;
      }

      cod = cod1 ? cod1 : cod2;

      if (STANGA & cod)
      {
         x = window.xmin;
         y = y1 + (y2-y1)*(window.xmin-x1) / (x2-x1);
      }
      else if (DREAPTA & cod)
      {
         x = window.xmax;
         y = y1 + (y2-y1)*(window.xmax-x1) / (x2-x1);
      }
      else if (JOS & cod)
      {
         x = x1 + (x2-x1)*(window.ymin-y1) / (y2-y1);
         y = window.ymin;
      }
      else if (SUS & cod)
      {
         x = x1 + (x2-x1)*(window.ymax-y1) / (y2-y1);
         y = window.ymax;
      }

      if (cod == cod1)
      {
         x1 = x; y1 = y;
         cod1 = det_cod (x1, y1);
      }
      else
      {
         x2 = x; y2 = y;
         cod2 = det_cod (x2, y2);
      }
   } /* while */

   *x1c = x1; *y1c = y1;
   *x2c = x2; *y2c = y2;

} /* clip_segment */



static cod_regiune
det_cod (double x, double y)
{
   cod_regiune result = 0;

   if (x < window.xmin)
      result |= STANGA;
   else if (x > window.xmax)
      result |= DREAPTA;

   if (y < window.ymin)
      result |= JOS;
   else if (y > window.ymax)
      result |= SUS;

   return (result);
} /* det_cod */

C. Aplicatii

1. Implementati procedura clip_segment si modificati linie_2d, punct_2d.
2. Definiti un port de vedere avand coordonatele (0,0,100) si o fereastra avand coordonatele (0,0,100,100). Generati o imagine formata din segmente avand coordonatele capetelor valori aleatoare in domeniul (-100, 200) si reprezenati-le. Observati efectul operatiei de clipping.
3. Scrieti un program de aplicatie care genereaza imaginea urmatoare:



Definiti 4 porturi de vedere in care transpuneti zonele indicate pe figura prin numere de ordine. (Se va modifica fereastra activa si se va regenera imaginea initiala.)

4. Modificati procedura clip_segment astfel incat sa fie posibil clipping-ul unui segment de dreapta fata de o regiune dreptunghiulara oarecare.