clipping - facultatea de matematica iasimunteanu/cursuri/curs_08_an3.pdf · clipping este una...

Clipping

Marian Ioan MUNTEANU

Al.I.Cuza University of Iasi, Romaniawebpage: http://www.math.uaic.ro/∼munteanu

22 noiembrie 2011

Marian Ioan MUNTEANU (UAIC) Clipping 22 noiembrie 2011 1 / 19

Cuprins

1 Clipping pentru segmente de dreapta

2 Teste de acceptare / respingere

3 Algoritmul Cohen - Sutherland

Cuprins

Ce ınseamna clipping?

Pana acum am ignorat orice legatura ıntre rasterizare si dimensiunilemonitorului sau ferestrei destinate aplicatiei grafice.

Clipping este una dintre cele mai importante probleme ın ComputerGraphics si ideea de baza este scrierea primitivelor grafice folosindcoordonatele zonei de lucru.

A face clipping ınseamna a indentifica portiunile primitivei care suntvizibile si care nu. In consecinta, clipping ınseamna a ilumina doarpixelii care se afla ın interiorul suprafetei de desenat, care, ın modfrecvent, este un dreptunghi cu axele paralele cu axele de coordonate.

Cuprins

Poate fi realizata analitic ınainte sau ın timpul conversiei de scanare.Deoarece ”decuparea” analitica a liniilor si poligoanelor este usor derealizat, aceasta este realizata de obicei ınaintea conversiei de scanare, ıntimp ce alte primitive sunt decupate ın timpul conversiei.

Cuprins

Clipping pentru segmente de dreapta

Clipping pentru punct

Presupunem ca fereastra dreptunghiulara are varful din stanga-jos decoordonate (xmin, ymin) iar pe cel din dreapta-sus de coordonate(xmax , ymax).

Pentru ca un punct P(x , y) sa fie vizibil ın fereastra trebuiesatisfacute relatiile:

xmin ≤ x ≤ xmax , ymin ≤ y ≤ ymax .

Un segment de dreapta fata de o fereastra:

a) complet ın interior: (AB)b) complet ın exterior: (EF ) si (IJ)c) un capat ın interior, celalalt ın exterior: (CD)d) ambele capete ın exterior, dar o parte a segmentului ın interior: (GH)

Un algoritm simplu este urmatorul:

• daca ambele capete ale segmentului sunt ın interior, se traseazasegmentul;

• daca numai un capat este ın interior (si celalalt ın exterior) sedetermina punctul de intersectie cu marginea ferestrei si se traseazasubsegmentul de interior;

• altfel, se calculeaza intersectiile cu liniile ce definesc margineaferestrei si, daca punctele de intersectie sunt pe segmentele de dreapta cedefinesc frontiera ferestrei, se traseaza subsegmentul dintre acestea.

Teste de acceptare / respingere

Ce ınseamna?

Algoritmul de mai ınainte poate fi perfectionat prin efectuarea unor testesimple asupra capetelor segmentului.√

Testul care verifica daca ambele capete ale segmentului suntinterioare fereastrei poarta numele de test de acceptare.√

Orice segment care are ambele capete de aceeasi parte a ferestrei(sus, jos, stanga, dreapta) este complet invizibil. Testul care verificaaceasta conditie se numeste test de respingere.

Prin adaugarea testelor de acceptare si respingere se obtine un algoritm acarui eficienta se manifesta cu precadere ın doua situatii:

(a) majoritatea segmentelor de reprezentat se afla ın interiorul ferestrei;(b) majoritatea segmentelor de reprezentat se afla ın afara ferestrei.

Ce ınseamna?

Algoritmul Cohen - Sutherland

Daca o linie nu este nici respinsa si nici acceptata atunci secalculeaza, ıntr-o ordine prestabilita, intersectiile liniei cu dreptelesuport ale laturilor ferestrei de lucru: y = ymax, x = xmax, y = ymin,x = xmin, ındepartand portiunile de segment care se situeaza ın afaraferestrei dreptunghiulare. Rezulta astfel un nou segment, iarprocedura se bucleaza asupra ei ınsasi pana cand un segment rezultateste acceptat sau respins.

Algoritmul care urmeaza propune caecranul sa se divida ın 9 regiuni de-terminate de marginile ferestrei. Inprezentarea clasica a algoritmului Co-hen - Sutherland se asociaza fiecaruicapat al unui segment un cod de 4 cifresi anume:

1001 1000 10100001 0000 00100101 0100 0110

Daca o linie nu este nici respinsa si nici acceptata atunci secalculeaza, ıntr-o ordine prestabilita, intersectiile liniei cu dreptelesuport ale laturilor ferestrei de lucru: y = ymax, x = xmax, y = ymin,x = xmin, ındepartand portiunile de segment care se situeaza ın afaraferestrei dreptunghiulare. Rezulta astfel un nou segment, iarprocedura se bucleaza asupra ei ınsasi pana cand un segment rezultateste acceptat sau respins.

Algoritmul care urmeaza propune caecranul sa se divida ın 9 regiuni de-terminate de marginile ferestrei. Inprezentarea clasica a algoritmului Co-hen - Sutherland se asociaza fiecaruicapat al unui segment un cod de 4 cifresi anume:

1001 1000 10100001 0000 00100101 0100 0110

a) prima cifra este→ 1 daca punctul este deasupra ferestrei→ 0 ın rest

b) a doua cifra este→ 1 daca punctul este sub fereastra→ 0 ın rest

c) a treia cifra este→ 1 daca punctul este ın dreapta ferestrei→ 0 ın rest

d) a patra cifra este→ 1 daca punctul este ın stanga ferestrei→ 0 ın rest .

Puterea algoritmului consta ın faptul ca, odata determinate codurileasociate capetelor segmentului, testele de acceptare sau respingere serealizeaza prin operatii logice rapide.

Daca ambele capete ale segmentului au codul 0000 atunci, ın modbanal, se poate decide ca segmentul se afla ın ıntregime ın interiorulferestrei. Acesta este cazul segmentului (AB) din figura.

De asemenea, ın mod banal se poate decide ca un segment este ınıntregime ın exterior cand operatia AND logic ıntre codurile celordoua puncte conduce la un rezultat diferit de 0. Intr-adevar, ın acestcaz, ambele puncte se afla ıntr-un acelasi semiplan (cel indentificat debitul 1 al rezultatului) si astfel segmentul nu intersecteazadreptunghiul de clipping. Este cazul segmentului (EF ) din figura.Avem: E (0001) si F (1001) si astfel

0001 ∧ 1001 = 0001 6= 0000.

Daca ınsa rezultatul operatiei AND este 0000 se testeaza care din celedoua puncte extreme se afla ın exteriorul dreptunghiului (cel putin unuleste!!!) si se ımparte segmentul ın doua parti, din care una poate fiınlaturata (deoarece se afla ın exteriorul dreptunghiului).

Sa luam cazul segmentului (CD) din figura: D(1000) si C (0000). Dreaptacu care se calculeaza intersectia este cea care corespunde bitului 1 dincodul punctului. Pentru D se calculeaza intersectia D ′ cu dreaptay = ymax. Noul punct D ′ ıl va substitui pe precedentul D. Se scrie din noucodul si se reia procedeul.

Pentru exemplul din figura avem:

AB CD EF GH IJ0000 0000 0001 0100 01000000 1000 1001 0010 0010—————————————————— AND0000 0000 0001 0000 0000

Concluzie. Rezultat nenul ınseamna respingere automata: este cazulsegmentului (EF ). Ambii termeni nuli ınseamna acceptare automata:cazul segmentului (AB). Celelalte segmente urmeaza a fi subdivizate.

Pentru exemplul din figura avem:

AB CD EF GH IJ0000 0000 0001 0100 01000000 1000 1001 0010 0010—————————————————— AND0000 0000 0001 0000 0000

Concluzie. Rezultat nenul ınseamna respingere automata: este cazulsegmentului (EF ). Ambii termeni nuli ınseamna acceptare automata:cazul segmentului (AB). Celelalte segmente urmeaza a fi subdivizate.

Scriem ın continuare codul C pentru algoritmul Cohen - Sutherland.

Fie P0(x0, y0), P1(x1, y1) si dreptunghiul cu diagonala (xmin, ymin) −(xmax, ymax).

Definim tipul laturaenum latura { sus = 0x8, jos = 0x4, dreapta = 0x2, stanga = 0x1, nul = 0x0 };si variabilele outcode0, outcode1, respectiv outcodeOut de tip latura(care reprezinta codurile capetelor segmentului (P0P1), respectiv alpunctului de intersectie a segmentului cu o latura a ferestrei de clipping).

Definim de asemenea constantele (booleene) TRUE = 1 si FALSE = 0.

Calcul cod

Scriem mai ıntai functia care calculeaza codul unui punct ın raport cudreptunghiul de clipping. Aceasta se numeste Calcul outcode si este detip latura. Sa mai facem observatia ca vom folosi operatorii | si & (anumesau, respectiv si bit per bit). Avem:latura Calcul outcode (double x, double y,

/* coordonatele punctului */int xmin, int ymin, int xmax, int ymax)

/* coordonatele ferestrei de clipping */{ latura code = nul;

if (y > ymax) code = code | sus;else if (y < ymin) code = code | jos;

if (x > xmax) code = code | dreapta;else if (x < xmin) code = code | stanga;

return code;}

Calcul cod

Scriem mai ıntai functia care calculeaza codul unui punct ın raport cudreptunghiul de clipping. Aceasta se numeste Calcul outcode si este detip latura. Sa mai facem observatia ca vom folosi operatorii | si & (anumesau, respectiv si bit per bit). Avem:latura Calcul outcode (double x, double y,

/* coordonatele punctului */int xmin, int ymin, int xmax, int ymax)

/* coordonatele ferestrei de clipping */{ latura code = nul;

if (y > ymax) code = code | sus;else if (y < ymin) code = code | jos;

if (x > xmax) code = code | dreapta;else if (x < xmin) code = code | stanga;

return code;}

Prezentam acum functia CohenSutherland care realizeaza clippingfolosind algoritmul descris anterior.

void CohenSutherland (double x0, double y0, double x1, double y1,/* coordonatele capetelor segmentelor care initial sunt

intregi, insa dupa o decupare valorile pot deveni reale */int xmin, int ymin, int xmax, int ymax)

/* coordonatele dreptunghiului de clipping */{

latura outcode0, outcode1, outcodeOut;int accept, done;

/* accept - pentru testul de acceptare *//* done - pentru testul de respingere */

accept = FALSE; done = FALSE;

double x, y; /* coordonatele punctelor de intersectie */

outcode0 = Calcul outcode(x0, y0, xmin, ymin, xmax, ymax);outcode1 = Calcul outcode(x1, y1, xmin, ymin, xmax, ymax);

{if (! (outcode0 | outcode1)){ /* acceptare triviala si iesire */

accept = TRUE; done = TRUE;}

else if (outcode0 & outcode1)done = TRUE; /* respingere triviala si iesire */

else { /* nu avem nici acceptare si nici respingere trivialaasa ca vom face efectiv clipping */

if (outcode0) outcodeOut = outcode0;else outcodeOut = outcode1;

/* se determina capatul exterior */if (outcodeOut & sus){ /* se face clip cu latura de sus */

x = x0+float(x1 − x0)*(ymax − y0)/float(y1 − y0);y = ymax;}

else if (outcodeOut & jos){ /* se face clip cu latura de jos */

x = x0+float (x1 − x0)*(ymin − y0)/float(y1 − y0);y = ymin;}else if (outcodeOut & dreapta){ /* se face clip cu latura din dreapta */

y = y0+float(y1 − y0)*(xmax − x0)/float (x1 − x0);x = xmax;}else if (outcodeOut & stanga){ /* se face clip cu latura din stanga */

y = y0+float(y1 − y0)*(xmin − x0)/float (x1 − x0);

x = xmin;}

/* acum se elimina capatul exterior */if (outcodeOut == outcode0) {

x0 = x; y0 = y;outcode0 = Calcul outcode(x0, y0, xmin, ymin, xmax, ymax);

} else {x1=x; y1=y;outcode1 = Calcul outcode(x1, y1, xmin, ymin, xmax, ymax);

} while (! done);

if (accept) line(x0, y0, x1, y1);} /* end functie */

clipping - facultatea de matematica iasimunteanu/cursuri/curs_08_an3.pdf · clipping este una...

Documents