Tehnici de decupare - Decuparea segmentelor de dreapta 2D. Algoritmul Cohen-Sutherland

Tehnici de decupare

In procesul de manipulare si reprezentare a obiectelor grafice, este posibil ca unele parti ale acestora sa nu se incadreze in interiorul ferestrei de vizualizare. O solutie simpla pentru rezolvarea evitarea redarii punctelor situate in afara ferestrei de afisare este sa se verifice pentru fiecare punct incadrarea in fereastra si sa se traseze pixelul corespunzator numai in cazul afirmativ. O asemenea rezolvare nu este insa si rapida. Pentru forme simple, de tipul dreapta sau poligon, este mai eficient sa se determine partea vizibila inainte de afisare si sa se reprezinte numai partea respectiva. Partea invizibila se decupeaza.

1. Decuparea segmentelor de dreapta 2D. Algoritmul Cohen-Sutherland

Planul grafic se imparte in noua regiuni, codificate conform figurii de mai jos.

Codurile se construiesc atribuind fiecaruia din cei 4 biti valori dupa cum urmeaza:

• Bitul b₀ este 1 daca punctul este deasupra marginii superioare, y_vt
• Bitul b₁ este 1 daca punctul este dedesubtul marginii inferioare, y_vb
• Bitul b₂ este 1 daca punctul este la dreapta marginii din dreapta, x_vr
• Bitul b₃ este 1 daca punctul este la stanga marginii din stanga, x_vl

Algoritmul primeste codurile capeletor segmentului de dreapta, pe care le combina eficient pentru a identifica mai multe situatii posibile. In exemplul din figura, P₁ are codul 1010, iar P₂ are codul 0001.

Pasul 1.

Se calculeaza functia logica pe biti SAU. Daca SAU da zero pe toate pozitiile, ambele puncte sunt in interiorul ferestrei de afisare si nu este nevoie de decupare. Se trece la Pasul 5, pentru a se trasa dreapta. In caz contrar, se trece la pasul urmator.

Pasul 2.

Daca SAU nu da 0 pe toate pozitiile, se face SI logic intre coduri. Daca functia SI nu da zero pe toate pozitiile (avem cel putin un 1) segmentul este complet in afara ferestrei de afisare, deci nu avem de trasat nimic si algoritmul se incheie. In caz contrar, segmentul trebuie decupat si se trece la pasul urmator.

Pasul 3.

Se inspecteaza codul lui P₁.

Astfel, daca P₁ are codul este 0000, P₁ este un punct valid si se trece la pasul urmator.

Daca P₁ are nu are codul este 0000, urmeaza sa fie decupat. Se verifica intai bitul cel mai semnificativ, b₃. Daca b₃=1, P₁ este situat la stanga marginii din stanga. In acest caz (valabil pentru figura de mai sus), se calculeaza intersectia dintre segmentul P₁P₂ si marginea din stanga. Se obtin coordonatele punctului care inlocuieste P₁. In exemplul din figura, este punctul A. Acesta primeste codul corespunzator pozitiei si algoritmul se reia de la primul pas, cu P₁=A. In exemplul din figura, A primeste codul 0010 (un punct de pe marginea stanga este considerat valid pentru trasare, deci bitul b₃ este setat pe zero). 

Pasul 4.

Se inspecteaza codul lui P₂. Se procedeaza la fel ca la Pasul 3, pentru punctul P₂.

De observat ca la acest punct se ajunge numai dupa ce punctul P₁ a fost complet rezolvat. In exemplul din figura, pentru ca noul P₁ (A) are codul nenul, este din nou decupat, de data aceasta fata de marginea de jos, pentru care bitul b₁ este setat pe 1. Se obtine punctul B, care devine noul P₁. La Pasul 4, P₂ va fi decupat si va primi coordonatele lui C.

Pasul 5.

Se traseaza segmentul de dreapta P₁P₂ decupat (devenit segmentul BC).

Algoritmul se incheie.

Un exemplu de program C de decupare ce foloseste doua functii pentru implementarea agoritmului de decupare Cohen-Sutherland se prezinta in continuare.

#define LEFT                      8 // 1000

#define RIGHT    4 // 0100

#define BOTTOM              2 // 0010

#define TOP                       1 // 0001

int cod_regiune( // returneaza codul regiunii pentru punctul (x,y)

double x, // coordonate punct testat

double y,

double xvl, // coordonate margini

double xvr,

double yvt,

double yvb

void decupare

double x1,          // coordonate P₁

double y1,

double x2, // coordonate P₂

double y2

else if( cod & RIGHT ) // decupare la dreapta

else if( cod & BOTTOM ) // decupare jos

else if( cod & TOP ) // decupare sus

if( cod == cod1 )

else

} // end while - bucla este parcursa de 4 ori in cazul cel mai defavorabil

linie_2d( x1, y1, x2, y2 ); // functie de trasare a segmentului de dreapta

2. Decuparea poligoanelor. Algoritmul Sutherland-Hodgman

Decuparea poligoanelor NU se reduce la decuparea laturilor, fiind mult mai complexa. E chiar posibil ca un poligon concav sa se separe in mai multe componente, asa cum se ilustreaza in figura urmatoare.

Algoritmul Shuterland-Hodgman foloseste o strategie de tipul divide si castiga (divide and conquer), pentru a rezolva o problema complexa rezolvand succesiv mai multe probleme simple identice. In acest caz, problema simpla consta in decuparea unei laturi a poligonului in raport cu una din marginile ferestrei, considerata o dreapta (infinit de lunga). Mentionam ca algoritmul Shuterland-Hodgman original este de fapt mai general, realizand decuparea 3D a unui poligon oarecare in raport cu un alt poligon oarecare.

Algoritmul se deruleaza in patru etape succesive si similare. In fiecare etapa se realizeaza decuparea intregului poligon in raport cu o singura margine.

In cadrul unei etape de decupare, se parcurg succesiv varfurile poligonului, in ordinea de definitie si se examineaza relatia dintre punctul curent (C) si punctul urmator (U) in raport cu latura pentru care se face decuparea. Pe masura ce se parcurg varfurile poligonului, se construieste o noua lista de varfuri.

Fig..Decuparea poligoanelor

Dreapta corespunzatoare laturii pentru care se face decuparea inparte planul de vizualizare in doua regiuni: interioara si exterioara. In consecinta, sunt posibile urmatoarele 4 situatii:

In functie de situatia intalnita, algoritmul face urmatoarele actiuni, ilustrate in figura de mai jos:

1)      Insereaza U in noua lista de varfuri.

2)      Gaseste intersectia I a laturii CU cu dreapta de margine si o insereaza in noua lista de varfuri.

3)      Gaseste intersectia I a laturii CU cu drapta de margine si insereaza in noua lista de varfuri pe I si pe U.

4)      Nu insereaza nimic.

Cele 4 etape de decupare a unui poligon concav sunt ilustrate in figura urmatoare.

In ordine lexicografica, sunt ilustrate:

poligonul initial cu fereastra de vizualizare, decuparea la dreapta, decuparea jos,

decuparea la stanga si decuparea sus (finala).

3. Decuparea cercurilor si elipselor

Se face initial o evaluare globala, testand-se daca dreptunghiul de incadrare al cercului sau elipsei este sau nu complet continut de fereastra de vizualizare. In caz afirmativ, nu este nevoie de decupare. In cazul negativ, se testeaza incluziunea cadranelor (sferturi de cerc). Cele complet incluse se pot trasa, nu se decupeaza. Cele partial incluse se pot divide in continuare in octanti (optimi de cerc). Octantii complet inclusi se traseaza. La cei partial inclusi se poate proceda la determinarea intersectiilor cu marginile prin metode analitice sau, mai simplu si adesea chiar mai rapid in aceasta faza, se testeaza individual pozitia fiecarui pixel la trasare, fiind marcati numai cei interiori. La elipse, descompunerea se face numai pana la nivel de quadranti.

4. Decuparea textelor

Se poate face in urmatoarele moduri:

La nivel de pixel

La nivel de litera (daca este partial inclusa se decupeaza toata litera)

La nivel de cuvant (se decupeaza intreg cuvantul partial inclus)