2. Modele geometrice şi tehnici asociate 2.1. Metode de reprezentare a obiectelor geometrice Scopul principal al unui modelator al obiectelor planare şi spaţiale constă în realizarea descrierii corecte şi consistente a obiectelor ţintă, inclusiv a metodelor de evaluare a proprietăţilor geometrice şi fizice, cum şi asigurarea interfeţei cu module de fabricaţie asistată de calculator, simulare şi analize variate. O componentă importantă a oricărui modelator o reprezintă modelatorul geometric. Sunt două categorii de probleme de modelare geometrică:

(1) reprezentarea geometrica şi (2) calcule geometrice.

Programele de modelare 3D sunt constituite din câteva modele standard: (1) modelator spaţial al obiectelor; (2) modul de gestionare a proprietăţilor fizice (texturi, volume etc.); (3) modul de prelucrare ambientală (vedere persepectivă, iluminare, feno-

mene atmosferice, modalităţi de propagare a luminii); (4) modul de animaţie pentru gestiunea mişcărilor unor obiecte şi

interacţiunea obiecte-proiectant (jucător). Calculele geometrice efectuate depind de natura aplicaţiei: arii, volume, intersecţii, distanţe etc.

Metodele de modelare propriu-zisă a obiectelor spaţiale influenţează performanţele generale ale aplicaţiei. Cele mai importante metode de reprezentare a obiectelor sunt:

(a) instanţierea primitivelor geometrice; (b) reprezentarea prin muchii şi vârfuri; (c) măturarea geometrică; (d) reprezentarea prin frontiere; (e) descompunerea în celule şi enumerarea ocupării spaţiale; (f) descrierea booleană (geometria solidă constructivă) ş. a.

Practic, se pot utiliza: (1) modelatoare de suprafeţe; (2) modelatoare bazate pe curbe spline; (3) modelatoare poligonale şi (4) modelatoare de solide. Modelele geometrice sunt de tip neparametric şi de tip parametric. Tehnicile de modelare la nivel global sunt abordate în acest capitol. Modelarea curbelor, suprafeţelor şi solidelor prin metode parametrice este descrisă detaliat în capitolul 4. Modelatoarele de suprafeţe construiesc obiectul prin aplicarea unui înveliş asupra unui schelet subiacent constituit fie din poligoane, fie din curbe (spline). Se obţine o structură ce ocupă un volum în spaţiu, dar care nu are caracteristici fizice legate de volumul respectiv: inerţie, densitate, masă etc. Modelatoarele bazate pe curbe spline construiesc obiectele 3D (fie suprafeţe, fie volume) prin curbe spline uniforme sau neuniforme raţionale (eng.: NURBS - Non-Uniform Rational B-splines).

Modelatoarele poligonale utilizează poligoane pentru a construi obiecte 3D. Ele aproximează permanent suprafeţele curbe prin suprafeţe plane. De aceea beneficiază de algoritmi eficienţi, bine puşi la punct pentru calcule geometrice şi vizualizare grafică. Modelatoarele solide, cu preţul creşterii semnificative a timpului de calcul, furnizează informaţii nu numai despre caracteristicele fizice, dar permit şi operaţii (cum sunt cele booleene) pentru a realiza interacţiuni între obiecte.

Pe lângă metodele de reprezentare, descrise mai jos, procedeele de modelare se bazează pe următoarele idei majore:

(1) utilizarea primitivelor (vezi mai jos); (2) extrudarea - prelucrarea unei entităţi 2D simple (cerc, dreptunghi, poli-gon etc.) şi translatarea ei după o curbă pentru a produce obiecte 3D. Prin parametrizarea extrudării (transformări geometrice) se pot obţine variaţii de grosime/formă ale obiectului final. (3) revoluţie (eng.: lathing) - generarea obiectelor prin rotaţia unei curbe în jurul unei axe; (4) mulare (eng.: lofting) - întinderea unei suprafeţe pe scheletul format de mai multe curbe de secţiune (vezi capitolul 1: curbe pe suprafaţă), similar cu construcţia unei carene de nave; (5) editarea vârfurilor (eng.: vertex) - modificarea numărului şi poziţiei vâr-furilor suprafeţei (punct cu punct sau editare elastică: mişcarea unui vârf este însoţită de mişcarea vârfurilor vecine); (6) acţiuni booleene care permit operarea unor obiecte 3D asupra altor obiecte 3D.

Aceste aspecte vor fi acoperite în secţiunile următoare. 2.1.1. Instanţierea primitivelor geometrice

Primitive geometrice fundamentale Instanţierea primitivelor constă în definirea unei familii de entităţi - primitive - membrii unei familii numindu-se instanţă sau exemplar. O primitivă poate fi privită ca un prototip parametrizat. În afară de modelele parametrice prezentate în capitolul următor, câteva primitive simple vor fi descrise în această secţiune. a) Poligoane şi poliedre Modelarea geometrică pune la dispoziţia proiectanţilor de aplicaţii grafice, în general, şi celor de proiectare asistată de calculator, în special, mai multe categorii de poligoane4. Tipul particular de poligon ales va determina complexitatea atât a

4 În spaţiul euclidian 2D, un poligon simplu este definit ca o mulţime de segmente cu proprietatea că formează un circuit simplu închis (în limbajul teoriei grafurilor)

algoritmilor de editare, dar mai ales a algoritmilor de vizualizare grafică. De exemplu, un algoritm de triangularizare (descompunere în triunghuri) a unui poligon convex este un lucru simplu, dar devine complicat în cazul unui poligon cu găuri. Următoarele categorii de poligoane se întâlnesc atât în cazul 2D cât şi în domeniul spaţial. Triunghiul reprezintă cel mai utilizat model, poate şi pentru că toate vârfurile sale sunt coplanare, iar normala la planul său coincide cu normala suprafeţei poligonale din care face parte. Aproximarea poligonală a suprafeţelor 2D conduce, în general, la o reţea de dreptunghiuri. Multe aplicaţii care conduc la feţe dreptunghiulare, datorită şi erorilor de rotunjire, nu asigură, în general, coplanaritatea tuturor vărfurilor dreptunghiului. Desigur, descompunerea dreptunghiului în două triunghiuri va fi soluţia de abordat. Poligoanele convexe5 reprezintă cele mai simple poligoane care au mai mult de 3 sau 4 vărfuri. Problema intersecţiei a două poligoane convexe, problema punctului interior, calculul diverselor elemente este relativ uşor. De aceea, poligoanele convexe reprezintă primitive de bază în diverse “motoare” de modelare. Poligoanele concave sunt cele mai “simple” poligoane care nu sunt convexe şi nu au găuri. Mulţi algoritmi de determinare a vizibilităţii scenelor au fost adaptaţi pentru lucrul cu astfel de obiecte. Poligoanele cu găuri sunt poligoane complexe. Ele pot fi specificate în mai multe moduri. Metoda uzuală presupune definirea părţii solide în sensul acelor de ceasornic şi a găurii în sens trigonometric. Poligoanele cu găuri pot fi transformate în poligoane concave prin introducerea a două muchii (ce se suprapun) între două

sau o mulţime de segmente astfel încât oricare două adiacente au intersecţia redusă la un punct (numit vărf), oricare două neadiacente au intersecţia vidă, iar numărul de vârfuri coincide cu numărul segmentelor. Dacă există segmente neadiacente care au intersecţia nevidă, dar circuitul este închis, atunci poligonul este unul oarecare. Orice poligon simplu împarte planul în două regiuni: interiorul - regiunea mărginită) şi exteriorul - regiunea nemărginită. 5 În general, o figură este convexă dacă (interiorul său) conţine integral toate segmentele unind oricare două din punctele sale. Figuri convexe simple sunt: cercul, semicercul, elipsa etc. Anumite patrulatere sunt convexe, altele nu. Un sector circular este convex dacă unghiul său la centru este cel mult 180° şi neconvex, în caz contrar. O dreaptă este o figură convexă, orice parte convexă a liniei este fie un segment, fie o semidreaptă. Un tip de poligon interesant este poligonul stelat. Interiorul acestuia conţine cel puţin un punct z astfel încât segmentul zP este situat în interior, oricare ar fi punctul P interior poligonului. Pentru un poligon oarecare, mulţimea punctelor z cu această proprietate se numeşte nucleul poligonului.

dintre vărfurile celor două poligoane. Pentru cazul găurilor multiple, aceste vărfuri trebuie alese cu mare grijă pentru a nu se obţine poligoane care să se suprapună. Poligoanele autointersectante creează mari dificultăţi în prelucrarea grafică, de aceea ele sunt evitate în partea de modelare. Dacă poligonul este regulat (laturile având aceeaşi lungime) atunci poligonul este modelat şi prin: centrul cercului, o rază şi numărul de laturi. Se va specifica dacă poligonul este înscris sau circumscris cercului. Un poliedru (în spaţiul euclidian 3D) este definit printr-o mulţime finită de poligoane plane astfel încât fiecare muchie a unui poligon mai aparţine exact unui alt poligon (cele două poligoane sunt adiacente) şi nu mai există alte poligoane cu aceeaşi proprietate. Vârfurile şi muchiile poligoanelor sunt vârfurile şi muchiile poliedrului, iar poligoanele sunt feţele poliedrului. Se definesc similar noţiunile de poliedru simplu şi poliedru convex. Exemple Convenim ca specificarea unui punct, identificat prin eticheta Vn şi coordonatele reale x, y, z, să se realizeze prin abstractizarea: POINT Vn, x, y, z De asemenea, descrierea unei feţe poligonale, necesită specificarea listei vârfurilor în sens trigonometric, privit din exteriorul obiectului: FACE n1, n2, n3, ... Cu precizările de mai sus, descriem [16]: cubul, octaedrul şi tetraedrul.

Cubul centrat în origine, de latură 2, are vărfuri ale căror coordonate sunt reprezentabile prin numerele 1.0 şi -1.0. Cele 8 vârfuri şi 6 feţe sunt: POINT V1, 1.0, 1.0, 1.0 POINT V2, 1.0, 1.0, -1.0 POINT V3, 1.0, -1.0, 1.0 POINT V4, 1.0, -1.0, -1.0 POINT V5, -1.0, 1.0, 1.0 POINT V6, -1.0, 1.0, -1.0 POINT V7, -1.0, -1.0, 1.0 POINT V8, -1.0, -1.0, -1.0 FACE V1, V3, V4, V2 FACE V1, V5, V7, V3 FACE V1, V2, V6, V5 FACE V8, V6, V2, V4 FACE V8, V4, V3, V7 FACE V8, V7, V5, V6 Octaedrul (poliedrul cu opt feţe) este forma duală a cubului. Prin scalarea uniformă a cubului cu 1/3, vârfurile cubului ajung în centrul feţelor octaedrului. Fiecare vârf al octaedrului este centrul feţei cubului. Cu convenţia că vârful j al octaedrului este situat în centrul feţei j a cubului, baza de date care descrie octaedrul este: POINT V1, 1.0, 0.0, 0.0

POINT V2, -1.0, 0.0, 0.0 POINT V3, 0.0, 1.0, 0.0 POINT V4, 0.0, -1.0, 0.0 POINT V5, 0.0, 0.0, 1.0 POINT V6, 0.0, 0.0, -1.0 FACE V1, V3, V5 FACE V1, V6, V3 FACE V1, V5, V4 FACE V1, V4, V6 FACE V2, V5, V3 FACE V2, V3, V6 FACE V2, V4, V5 FACE V2, V6, V4 Un exemplu de tetraedru este specificat prin următoarea bază de date: POINT V1, 1.0, 1.0, 1.0 POINT V2, 1.0, -1.0, -1.0 POINT V3, -1.0, 1.0, -1.0 POINT V4, -1.0, -1.0, 1.0 FACE V1, V2, V3 FACE V1, V4, V2 FACE V1, V3, V4 FACE V2, V4, V3. b) Cercul şi sfera Multe aplicaţii de grafică trasează punctele prin cercuri cu o anumită rază (în grafica 2D) şi prin sfere (în grafica 3D). De asemenea un obiect modelat prin sfere (de exemplu o curbă sau o scenă cu obiecte neregulate încadrate în sfere) poate fi prelucrat uşor cu ajutorul algoritmului de vizibilitate ray-tracing. Pentru o soluţie a problemei intersecţiei dintre o rază şi un cerc se poate urmări observaţia 3 din capitolul 2. Cazul 3D, pentru problema intersecţiei dintre o dreaptă şi o sferă va fi prezentat mai jos. De asemenea cercurile şi sferele reprezintă primitive de bază în geometria solidă constructivă. Din punct de vedere parametric, o sferă este descrisă cu ajutorul coordonatelor polare. Ilustrăm cazul sferei unitate. Ecuaţiile unui punct de pe sfera unitate sunt:

x = cos(θ) cos(φ), y = cos(θ) sin(φ), z = sin(θ), -π/2 ≤ θ ≤ π/2 , 0 ≤ φ ≤ 2π. Arătăm, în continuare, un mod de tratare a problemei intersecţiei dintre o dreaptă şi o sferă. Fiecare punct de pe dreapta care trece prin punctele A(x0, y0, z0) şi B(x1, y1, z1) este obţinut, parametric astfel: x = x0 + t(x1 - x0), y = y0 + t(y1 - y0), z = z0 + t(z1 - z0), t ∈ R. Sfera cu centrul C(a, b, c) şi raza r > 0, în reprezentare implicită, este dată prin: (x-a)2 + (y-b)2 + (z-c)2 = r2. Notănd ∆x := x1 - x0, ∆y := y1 - y0, ∆z := z1 - z0 şi substituind valorile x, y, z din prima ecuaţie în formula sferei, după calcule,

obţinem o ecuaţie de gradul doi în t, cu coeficienţi exprimaţi în funcţie de elementele definitorii ale dreptei şi sferei: (∆x2 + ∆y2 + ∆z2)t2+2t[∆x(x0-a)+∆y(y0-b)+∆z(z0-c)]+(x0-a)2+(y0-b)2+(z0-c)2 - r2 =

0. Dacă ecuaţia obţinută nu are rădăcini reale atunci obiectele nu se

intersectează, dacă există numai o rădăcină reală atunci dreapta este tangent% ecuaţiei, altfel se obţin două puncte de intersecţie.

c) Superelipse şi superelipsoizi [8] Pentru proiectarea asistată de calculator au fost propuse noi primitive. Domeniului 2D îi sunt dedicate elipsele şi cercurile, iar sferele şi elipsoizii sunt utilizaţi în domeniul spaţial. Superelipsa 2D, centrată în origine este definită în formă parametrică, prin: x(θ) = a cosn(θ), y(θ) = b sinn(θ), unde 0 ≤ θ ≤ 2π şi 0 < n < ∞. Curba intersectează axa Ox în (-a, 0) şi (a, 0), iar axa Oy în (0, -b) şi (0, b). Superelipsa este mărginită de dreptunghiul cu laturile de lungime 2a şi lăţime 2b.

Definind nn

by

axyxf

22

),(

+

= ,

atunci: dacă f(x, y) = 1 rezultă că (x, y) se află pe frontiera superelipsei, dacă f(x, y) < 1 atunci punctul (x, y) se află în interiorul superelipsei, în caz contrar el se situează în afara elipsei. Prin modificarea parametrului n se schimbă forma superelipsei, după cum urmează:

n a, b Descriere (mod text) 0 - Dreptunghi 0 a = b Pătrat < 1 - Dreptunghi rotunjit = 1 - Elipsă = 1 a = b Cerc = 2 - Romb > 2 - Romb circular → ∞ - Plus

Trebuie observat că superelipsa are puncte fixe pentru θ = 0, π/2, π, 3π/2 indiferent de valoarea parametrului n. Superelipsolizii sunt obiecte 3D care pot avea forme particulare precum: sfera, cilindrul, paralelipipedul şi alte forme intermediare. Superelipsoidul centrat în origine, înscris în paralelipipedul cu dimensiunile: 2a, 2b şi 2c, este dat, parametric, prin ecuaţiile:

x = a cosm(α)cosn(β), y = b cosm(α)sinn(β), z = c sinm(α), unde

-π/2 ≤ α ≤ π/2, -π ≤ β ≤π şi

0 < m, n < ∞. Pentru valori particulare ale parametrilor m şi n obţinem obiecte precum:

M N a, b, c Descriere (text) a obiectului 0 0 - Paralelipiped 0 0 a = b = c Cub < 1 < 1 - Cuboid < 1 1 - formă de pernă 1 < 1 - formă cilindrică 1 1 - Elipsoid 1 1 a = b = c Sferă 2 2 a = b = c Octaedru → ∞ → ∞ - plus 3D

Definind

mmnnn

cz

by

axzyxf

222

),,(

+

+

= ,

atunci: pentru f(x, y, z) = 1, punctul (x, y, z) se află pe suprafaţa superelipsoidului, pentru f(x, y, z) < 1, punctul (x, y, z) este situat în interiorul superelipsoidului, altfel este situat în exteriorul superelipsoidului. d) Torul şi supertoroidul Torul este un obiect spaţial utilizat mai puţin în aplicaţiile practice de modelare, dar multe sisteme de grafică îl prezintă ca primitivă spaţială. Notând prin r0 distanţa de la centrul torului la mijlocul inelului şi cu r1 raza secţiunii circulare a torului, punctele de pe tor sunt definite, parametric, prin:

x = cos(θ)[r0+r1cos(φ)], y = sin(θ)[r0+r1cos(φ)], z = r1sin(φ), unde 0 ≤ θ, φ ≤ 2π. Supertoroidul este o familie de primitive geometrice bazate pe tor. Fie m şi n numere naturale. Ecuaţiile supertoroidului sunt:

x = cosm(θ)[r0+r1cosn(φ)], y = sinm(θ)[r0+r1cosn(φ)], z = r1sinn(φ), unde 0 ≤ θ, φ ≤ 2π. Parametrul m determină forma inelului, iar parametrul n, determină forma secţiunii inelare.

Instanţe în grafuri de asamblare ierarhică Strategia preferată în proiectarea modelelor geometrice este de tip ierarhic, prin compunerea obiectelor sau părţilor în obiecte mult mai complexe. O astfel de

abordare poate fi implementată cu ajutorul grafurilor ierarhice de asamblare [68], digrafuri aciclice în care nodurile reprezintă obiecte, iar arcele descriu relaţii de tipul: “este parte” sau “se obţine prin transformarea”. Parametrii geometrici şi de altă natură pot fi ataşaţi nodurilor sau arcelor. De exemplu, arcelor le pot fi ataşate transformări afine.

Totuşi, nodurile interne nu reprezintă instanţe ale obiectelor din modelul final, ci “obiecte generice”. Un obiect generic apare în mai multe instanţe, după cum există mai multe trasee de la el la nodul considerat “rădăcină”. Un arc de la un nod A la alt nod B descrie faptul că obiectul B este unul din obiectele care participă la formarea lui A. Se spune că arcul este o instanţiere a obiectului B. Trebuie remarcat faptul că este posibil ca un obiect să folosească un alt obiect de mai multe ori, dar cu parametri diferiţi, deci structura relaţională este una generalizată. Printre avantajele acestei metode enumerăm: informaţia comună tuturor instanţelor generate din acelaşi obiect generic este stocată o singură dată, iar modificările parametrilor sau informaţiei relative la obiectul generic sunt instantaneu reflectată în toate instanţele din graf. 2.1.2. Reprezentarea prin muchii şi vârfuri Reprezentarea “cadru de sârmă” (eng.: wireframe) descrie un solid doar prin “scheletul său”. Din punct de vedere istoric, este prima metodă utilizată pentru modelare solidă. Modelul topologic de bază în reprezentarea wireframe (wf) constă din muchii şi vârfuri, nu şi din feţe. Astfel, formula lui Euler-Poincaré pentru verificarea validităţii unui obiect wf este: v - m + b - 2n = 0, unde v reprezintă numărul vărfurilor, m este numărul muchiilor, b este numărul de bucle, iar n este multiplicitatea (numărul de modele). O buclă este o secvenţă ordonată de vârfuri şi muchii alternative care definesc un punct unic sau o curbă spaţială care nu se autointersectează (eventualele porţiuni comune trebuie parcurse în sens diferit). Pentru modelarea wf se utilizează operatorii Euler care asigură validitatea modelului: crearea unui vârf, eliminarea unui vârf, crearea unei muchii şi a unui vârf, crearea unei muchii, eliminarea unei muchii. La crearea unei muchii, dacă cele două vârfuri aparţin aceluiaşi graf, se incrementează contorul buclelor, altfel grafurile sunt unite, se decrementează contorul buclelor, precum şi multiplicitatea. La eliminarea unei muchii se va executa una din următoarele acţiuni: dacă muchia nu are nici un capăt liber şi dacă după ştergerea muchiei vârfurile rămân în acelaşi graf atunci se decrementează contorul buclelor; dacă muchia nu are nici un capăt liber, dar după ştergere apar două grafuri distincte, atunci se incrementează contorul buclelor şi multiplicitatea; dacă muchia are un capăt liber atunci se şterge vârful respectiv.

Avantajele modelării wf sunt: (1) procesul de proiectare este tipic wf, adică utilizatorul îşi defineşte un plan de interes şi desenează în planul respectiv; (2) necesită un consum mic de memorie pentru stocarea modelului; (3) pentru muchii şi vărfuri sunt suficiente elementele de editare 2D; (4) se pot realiza uşor programe de postprocesare. Totuşi, metoda wf are şi dezavantaje. Cele mai importante dezavantaje constau în imposibilitatea eliminării suprafeţelor ascunse şi în imposibilitatea aplicării unor proceduri de analiză şi calcule geometrice. 2.1.3. Modelare prin măturare geometrică Metoda de măturare (baleiere) a spaţiului cu contururi bidimensionale pentru a definii obiecte 3D necesită specificarea profilului 2D al unui solid - obiectul generator - şi o curbă spaţială care precizează traiectoria - obiectul director - pe care se deplasează profilul în cadrul procesului de măturare. Din punct de vedere practic, sunt utile traiectorii drepte pentru baliere prin translaţie şi traiectorii circulare pentru baleiere prin rotaţie. Metoda baleierii spaţiale este utilă şi pentru modelarea suprafeţelor. O astfel de abordare este descrisă în capitolul 4. Avantajele acestei metode de modelare sunt: (1) reprezentare internă compactă (se memorează modelul profilului şi modelul curbei); (2) majoritatea pieselor obţinute prin extrudare, strunjire, laminare, turnare etc. se pot reprezenta prin baleiere spaţială; (3) profilul fiind de tip 2D se pot implementa uşor mai multe metode de editare grafică. Trebuie reţinut că nu orice profil 2D închis, prin baleiere, conduce la obiecte reale. Pentru grafică nu este un mare dezavantaj deoarece pot fi vizualizate obiecte fictive, dar nu întotdeauna astfel de obiecte pot fi produse practic (cu ajutorul maşinilor cu comandă numerică). 2.1.4. Reprezentarea prin frontiere

Principiile B-rep Reprezentarea prin frontiere (eng.: B-rep. Boundary representation) constă dintr-o descriere sistematică a elementelor care compun frontierea unui solid. Elementele constiturive (numite feţe) sunt suprafeţe modelate fie prin reţele poligonale (eng.: meshes), fie prin petice parametrizate (eng.: patches), în general de tip cubic. Fiecare faţă este mărginită (are arie finită) şi are o ecuaţie bine precizată. Feţele se întâlnesc două câte două în muchii (segmente de dreaptă sau arce de curbă). Extremităţile muchiei se numesc vârfuri. Se poate întâmpla ca cele două vârfuri să coincidă. Este foarte important ca o faţă să aparţină unui înveliş unic (prin înveliş gândim întreaga colecţie de feţe orientate consistent care alcătuiesc frontiera unui volum închis, simplu conex). O secvenţă ordonată de vârfuri şi muchii alternative care definesc un punct unic sau o curbă spaţială ce nu se autointersectează va fi

numită buclă. O buclă aparţine unei singure feţe, fiind de fapt frontiera acesteia. Totuşi, pentru o faţă pot fi descrise mai multe bucle. Un obiect valid topologic trebuie să fie: (1) complet - fiecare faţă să aibă asociată o suprafaţă, fiecare muchie să aibă asociată o curbă şi fiecare vârf să aibă asociat un punct geometric; (2) consistent - toate curbele în punctele aparţin suprafeţelor feţelor, geometria unei feţe nu se autointersectează şi obiectul, în întregime, nu se autointersectează. Modelarea B-rep are la bază validitatea de tip Euler-Poincaré:

v - m + f - o = 2(c- g), unde: v - numărul vârfurilor; m - numărul muchiilor; f - numărul feţelor; o - numă-rul găurilor în feţe; c - numărul componentelor separate ale modelului, iar g defineşte genul obiectului.

Metode B-rep Cea mai simplă abordare B-rep constă în descrierea unei liste de feţe poligonale, fiecare reprezentată de o listă de coordonate de vârfuri (poligoane explicite) sau o listă de referinţe (pointeri) la vârfurile obiectului. Pentru a indica, complet, topologia obiectului se poate utiliza un graf care să indice:

- pentru fiecare vârf: lista vârfurilor de care este conectat; lista muchiilor în care apare şi lista feţelor corespunzătoare;

- pentru fiecare muchie: vărfurile care o delimitează; lista muchiilor vecine; lista feţelor pe care le mărgineşte;

- pentru fiecare faţă: lista vârfurilor ce o definesc; lista muchiilor ce o mărginesc; lista feţelor vecine.

O astfel de reprezentare permite evaluarea corectă a următoarelor elemente: (1) vârfurile care înconjoară o faţă; (2) laturile care înconjoară o faţă; (3) feţele care înconjoară o faţă; (4) vărfurile care marginesc o latură; (5) laturile care pleacă de la o extremitate a laturii; (6) feţele care pleacă dintr-un vârf; (7) feţele care mărginesc o latură; (8) vârfurile vecine unui vârf; (9) laturile care pleacă dintr-un vărf.

Aproximarea poligonală a suprafeţelor Determinarea reţelei de poligoane ce aproximează o suprafaţă este o activitate importantă atât pentru grafică cât şi pentru proiectarea asistată de calculator. Pentru proiectare asistată de calculator, o sferă trebuie să fie complet rotundă, iar dacă se secţionează cu un plan trebuie să se obţină două solide. Modelarea sferei cu poligoane prezintă un obiect neted numai dacă se utilizează un număr foarte mare de poligoane mici, iar la secţionare trebuie avută mare grijă pentru a obţine obiecte solide, aproximarea poligonală fiind specifică mai mult aproximării suprafeţelor decât aproximării solidelor. Totuşi anumite solide pot fi aproximate cu poliedre şi pentru multe aplicaţii ale graficii pe calculator, aceste aproximări sunt suficiente.

O cerinţă importantă a aplicaţiilor de grafică interactivă spaţială o constituie minimizarea numărului de poligoane, dar fără pierderi mari în privinţa înfăţişării obiectului, pentru a mări viteza de generare pe suprafaţa unui display. Abordarea de bază în simplificarea suprafeţelor poligonale o constituie înlocuirea a două puncte care sunt extremităţi ale celei mai scurte muchii care este comună la două poligoane cu mijlocul muchiei. Astfel cele două poligoane sunt eliminate, iar vărfurile poligoanelor rămase se deplasează în noul punct. Pentru a adăuga detalii unei suprafeţe sau pentru a creşte gradul de aproxi-mare poligonală se poate realiza divizarea feţelor. Dacă feţele sunt triunghiuri, atunci se pot considera următoarele strategii posibile: (1) se consideră mijloacele laturilor triunghiului care vor determina trei muchii noi, deci numărul feţelor va creşte cu 3; (2) se consideră mijlocul celei mai lungi laturi şi se formează o muchie cu vârful opus, numărul feţelor se va dubla; (3) centrul de greutate al feţei unit cu cele trei vărfuri va da naştere la 3 triunghiuri; (4) centrul de greutate se uneşte cu mijloacele laturilor, se obţin 3 patrulatere care se vor descompune în triunghiuri; (5) linia mijlocie a triunghiului va determina un triunghi şi un patrulater, patrulaterul se va diviza în triunghiuri; etc. Dacă feţele sunt patrulatere convexe atunci se pot realiza divizări precum: (1) o muchie care uneşte mijloacele a două laturi opuse va da naştere la două patrulatere; (2) unind mijloacele laturilor adiacente se obţine un patrulater şi 4 triunghiuri; (3) ducerea unei diagonale pentru a obţine două triunghiuri; (4) ducerea ambelor diagonale şi obţinerea a patru triunghiuri; etc. Dacă poligonul are altă formă, atunci se aplică algoritmi de triangularizare. Poligoanele pot fi împărţite în triunghiuri prin considerarea a zero sau mai multe diagonale. Demonstraţia acestui fapt - un rezultat fundamental de geometrie computaţională - nu face obiectul acestei lucrări. Una din cele mai cunoscute metode de triangularizare este metoda lui Delaunay (vezi secţiunea 3.3), care produce o triangularizare cu proprietatea că unghiurile minime ale triunghiurilor generate sunt maxime faţă de toate celelalte triangularizări posibile. 2.1.5. Descompunerea în celule şi enumerarea ocupării spaţiale Enumerarea ocupării spaţiale constă în împărţirea spaţiului într-o reţea fină de celule tridimensionale (în general, cuburi), numite voxeli (eng.: volume element) şi reprezentarea obiectului solid prin lista celulelor pe care acesta le ocupă. Pentru stocarea unei astfel de liste se folosesc structuri de date speciale, cel mai des arbori octali (eng.: octree). Această abordare este extinderea metodologiei de compresie a imaginilor folosind arbori cuaternari (eng.: quadtree) - fiecare nod avănd fie zero, fie patru fii.

Atunci când divizarea nu este realizată la nivelului unei unităţi spaţiale, ci la nivelul componentelor obiectului avem de-a face cu o metodă similară instanţierii primitivelor: descompunerea în părţi (celule). Se poate obţine o descriere arborescentă a obiectului în care frunzele sunt cele mai simple părţi, iar nodurile interne indică operaţii sau transformări care produc un obiect intermediar.

2.1.6. Operaţii booleene Furnizarea unei familii flexibile de primitive solide care pot fi combinate prin intermediul operatorilor booleeni: reuniune, intersecţie şi diferenţă, stă la baza geometriei solide constructive (eng.: CSG - Constructive Solid Geometry). Primitivele solide mai des întâlnite sunt: paralelipiped, cilindru, con, sferă, tor, dar şi alte solide pot fi luate în considerare. Practic, un solid în metoda CSG este descris de un arbore ale cărui frunze sunt primitivele solide, iar nodurile interne sunt operatori booleeni. O astfel de reprezentare este una neevaluată deoarece conţine multe muchii ce rezultă din intersecţii de suprafeteţe şi din secţionări de muchii şi suprafeţe ale primitivelor constituente. Pentru a obţine numai solide în urma evaluării se lucrează cu mulţimi regulate (care îşi conţin frontiera) şi operatori booleeni regulaţi: Dacă op este un operator boolean clasic şi op* este operatorul boolean regulat atunci: A op* B = închiderea(interior(A op B)). Recent au fost introduşi operatori pseudo-booleeni în legătură cu operaţii asupra curbelor şi suprafeţelor. Ei reprezintă o extindere a operatorilor clasici la obiecte care nu mai sunt închise topologic [59]. Pentru multe aplicaţii este necesară evaluarea feţelor, muchiilor şi vârfurilor care formează frontiera obiectului modelat. De exemplu, muchiile sunt necesare pentru afişarea pe un display grafic a reprezentării wf. Fiecare primitivă poate fi aproximată cu un poliedru, fiecare din feţele curbe fiind o colecţie de feţe planare. Operatorii booleeni se aplică numai asupra poliedrelor. Aceasta simplifică algoritmii geometrici deoarece se manipulează numai suprafeţe plane. De asemenea, topologia obiectului este uşor de investigat deoarece vârfurile poliedrului aparţin muchiilor existente, iar noile vârfuri rezultate din intersecţii sau diferenţe aparţin unor muchii care existau în descrierea iniţială. Există, însă şi dezavantaje deoarece, uneori, este ascunsă adevărata structură topologică. De exemplu, o gaură printr-un cilindru este reprezentată printr-o colecţie de feţe; nu se ştie că este de natură circulară. Aproximarea poliedrală are consecinţe negative şi asupra preciziei calculelor geometrice. Evaluarea frontierei unui solid descris boolean este o sarcină dificilă cănd suprafeţele primitivelor sunt descrise prin petice (vezi capitolul 4). În acest caz se realizează o aproximare poligonală a fiecărui petic. Sistemele de modelare bazate pe suprafeţe curbe folosesc o reprezentare matematică exactă (vezi şi capitolul 1) pentru fiecare suprafaţă. Astfel operatorii booleeni trebuie să se aplice solidelor cu suprafeţe curbe. Pentru a obţine muchiile şi vârfurile solidului rezultat este necesară aplicarea de metode numerice şi analitice (vezi [20]). Astfel, reprezentarea rezultată are un grad ridicat de precizie atât din punct de vedere topologic cât şi geometric. Caracteristicele topologice semnificative sunt reprezentate direct. Geometria fiecărei suprafeţe este (aproape) exactă. Muchiile şi vârfurile nu sunt chiar exacte, dar pot fi determinate cu o anumită precizie. Implementarea operatorilor booleeni necesită rezolvarea anumitor

probleme de natură numerică (exemplu: determinarea intersecţiei a două suprafeţe) şi topologică (exemplu: aparţin un anumit punct unei suprafeţe date?). Determinarea cu acurateţe a reprezentării prin frontiere poate fi realizată şi prin intermediul aproximărilor poliedrale: o pereche de aproximări poliedrale care includ frontiera obiectului (vezi [78]). Anumite situaţii impun partiţionarea unui poliedru în părţi care nu se intersectează. Un alt algoritm care implementează operatori booleeni asupra poliedrelor este descris de Segal şi Sequin [74]. Rezultă că faţă de reprezentarea prin frontiere, metoda CSG are următoarele avantaje: (1) construcţia modelului se poate realiza interactiv, utilizatorul alegănd primitivele şi operatorii necesari; (2) modelele rezultate reprezintă obiecte reale, nu este nevoie de verificări asupra topologiei; (3) structura de date arborescentă permite o memorare compactă a obiectului. Deoarece arborele CSG asociat unui solid nu este unic, experienţa proiectantului va decide asupra vitezei cu care se vor realiza prelucrările ulterioare. 2.2. Construcţia obiectelor geometrice 2.2.1. Construcţii geometrice plane Implementarea unor tehnici de modelare a obiectelor plane şi spaţială necesită cunoaşterea unor metode fundamentale utilizate în construcţia obiectelor geometrice. Cele mai importante categorii de construcţii geometrice plane sunt: 1) construcţii de drepte perpendiculare sau paralele; 2) împărţirea unui segment de dreaptă în părţi egale sau într-un raport dat; 3) construcţia unghiurilor; 4)construcţia triunghiurilor; 5) construcţia patrulaterelor plane convexe; 6) construcţii de cercuri şi arce de cerc; 7) construcţii de poligoane înscrise inclusiv de poligoane regulate; 8) racordarea dreptelor prin arce de cerc; 9) racordări de drepte cu cercuri prin arce de cerc; 10) curbe construite din arce de cerc, ş.a. Pentru ridicarea unei perpendiculare într-un punct situat pe o dreaptă se utilizează proprietatea pantelor dreptelor perpendiculare (două drepte neparalele cu axele de coordonate sunt perpendiculare dacă şi numai dacă produsul pantelor dreptelor este egal cu -1) şi ecuaţia dreptei de pantă dată care trece printr-un punct. La nevoie se poate utiliza şi formula distanţei. Aceeaşi metodă se poate aplica şi pentru implementarea coborârii unei perpendiculare dintr-un punct din plan pe o dreaptă care nu conţine punctul respectiv. Proprietatea pantelor dreptelor paralele (pantele a două drepte sunt egale dacă şi numai dacă dreptele sunt paralele) ne permite obţinerea unei drepte paralele, printr-un punct dat, la o dreaptă dată.

Referitor la bisectoarele unghiurilor formate de dreptele a1x + b1y + c1 = 0 şi a2x + b2y + c2 = 0, pentru grafica computerizată este suficient să folosim ecuaţiile bisectoarelor:

22

22222

21

2111 /)(/)( bacybxabacybxa +++±=+++ .

În afară de modelarea triunghiurilor cu ajutorul a trei vârfuri, mai pot fi considerate şi combinaţii precum: trei laturi, o latură şi două unghiuri adiacente,

două laturi şi unghiul cuprins între ele, două laturi şi unghiul opus uneia din laturi, înăţimea triunghiului echilateral, înălţimea şi laturile egale ale unui triunghi isoscel, perimetrul triunghiului şi două unghiuri, raza cercului circumscris, mediana şi înălţimea care pleacă (ambele dintr-un vârf), mijloacele laturilor, două laturi şi mediana din vârful comun ş.a.m.d. Sunt numeroase formule pentru calculul ariei unui triunghi (formula determinantului, formula lui Heron etc.). Aria unui patrulater convex este egală cu jumătate din produsul lungimilor diagonalelor prin sinusul unghiului cuprins între ele sau, în funcţie de laturi şi unghiurile dintre ele:

2S = ab sin A + cd sin C = bc sin B + da sin D. Uneori este utilă ecuaţia cercului care trece prin trei puncte (x1, y1), (x2, y2) şi (x3, y3):

0

1111

3323

23

2222

22

1121

21

22

=

++++

yxyxyxyxyxyxyxyx

.

Dacă se doreşte împărţirea cercului în arce congruente atunci cunoaşterea laturii poligonului regulat înscris în cerc este suficientă. Pentru un cerc de rază R, latura (ln) şi apotema (an) poligonului regulat înscris satisfac următoarele relaţii de recurenţă:

)42( 222 nn lRRRl −−= ,

2/)42( 222 nn lRRRa −+= .

Pentru racordarea dintre două drepte d1 şi d2 printr-un arc de cerc de rază r dată se procedează astfel: Centrul O al cercului de racordare este la intersecţia paralelelor duse faţă de cele două drepte la distanţă r. Dacă punctul de racordare (fie acesta M) este situat pe una din drepte atunci se construieşte perpendiculara pe acea dreaptă în M, iar centrul cercului se va afla prin intersecţia acesteia cu bisectoarea unghiului celor două drepte. Dacă dreptele sunt paralele se pot realiza racordări cu un arc, două sau mai multe arce de cerc:

1. Fie Ai ∈ di ( i =1, 2) puncte de racordare date şi M un punct pe segmentul A1A2. Racordarea se poate face prin intermediul a două arce de cerc cu centrele de o parte şi de alta a segmentului A1A2. Centrul Oi se obţine ca intersecţie a mediatoarei segmentului AiM cu perpendiculara ridicată în punctul Ai (i = 1, 2).

2. Racordare prin două arce tangente într-un punct T, mijlocul unei secante MN care intersectează dreptele d1 şi d2 (Se definesc ca puncte de racordare, punctele A1 şi A2 astfel încât: A1M = MT = TN = NA2; O1 se află la intersecţia perpendicularei în T pe MN cu bisectoarea

unghiului A1MN, iar O2 la intersecţia aceleiaşi perpendiculare cu bisectoarea unghiului MNA2).

3. Pentru punctele de racordare A1 şi A2 date şi T punctul de tangenţă, cele două arce se obţin astfel: Fie M mijlocul segmentului A1A2 şi N piciorul perpendicularei din T pe A1A2. Oi este intersecţia perpendicularei ridicate în Ai cu dreapta TN (i = 1, 2).

Un tip aparte de racordare se face între perechi de drepte paralele. Tipul de racord depinde atât de modul de dispunere a dreptelor căt şi de relaţia dintre distanţele dintre dreptele fiecărei perechi. Dacă perechile de paralele nu sunt dispunse în unghi drept, iar ele sunt egal depărtate, atunci se poate proceda ca la tipul 1 de mai sus. Când perechile de paralele sunt inegal depărtate şi dispuse sub unghi drept atunci se prelungesc dreptele până la formarea unghiului drept. Dreptele exterioare se racordează cu un sfert din cercul cu centrul în O1 situat la intersecţia perpendicularelor ridicate în punctele A1 şi B1 situate astfel încât A1B1 să fie diagonala unui pătrat. Racordarea dreptelor interioare unghiului drept se face similar. Racordarea dreptelor şi a cercurilor se poate realiza prin intermediul arcelor de rază dată sau arcelor tangente sau nu la cercul dat. Racordarea arcelor de cerc prin intermediul arcelor de cerc depinde de restricţiile impuse. Se pot racorda arce de cerc prin intermediul unui arc de cerc tangent exterior lor, când unul din punctele de racordare este dat, arce de cerc printr-un arc de cerc de rază dată cu tangentă în interior sau în exterior ş.a. Modele utile pentru construcţia de curbe din arce de cerc sunt: ovalele lui Cassini şi Descartes (definibile şi ca loc geometric), ovoidul, spirala lui Arhimede şi diverse curbe ciclice: cicloida, epicicloida, elicea etc. 2.2.2. Construcţii geometrice în spaţiul discret

Generarea liniilor Fie ecuaţia unei drepte: y = m*x+n. Dacă dreapta nu este verticală şi se cunosc două puncte ale dreptei: P1(x1, y1) şi P2(x2, y2), atunci m = (y2-y1)/(x2-x1) , adică panta dreptei, iar n = y1 - m*x1. Determinarea punctelor aparţinând segmentului P1P2 se bazează pe relaţia ∆y = m*∆x, unde ∆x: = x2-x1 şi ∆y = y2-y1. Descriem metodele DDA, Bresenham şi metoda punctului mijlociu.

Metoda DDA (eng.: Digital Differential Analyzer) constă în alegerea unui pas pentru o axă şi calcularea coordonatelor corespunzătoare pe cealaltă. Pentru claritate, presupunem că panta m este pozitivă. Dacă m > 1, atunci ∆x < ∆y, iar numărul punctelor prezentate este mai mare dacă se consideră variaţia după y. Se consideră valorile coordonatei y din unu în unu şi se determină valorile pentru coordonatele x după regula: xi+1 = xi + 1/m.

Dacă m ≤ 1, atunci ∆x ≥ ∆y şi se va inversa rolul jucat de coordonatele x şi y. Se consideră punctele ale căror coordonate x variază din unu în unu şi se determină valorile pentru coordonatele y pe baza relaţiei: yi+1 = yi + m.

Cum valoarea lui m este, în general, un număr real se vor rotunji valorile coordonatelor calculate la valori întregi.

Metoda Bresenham foloseşte operaţii simple precum: adunarea şi scăderea numerelor întregi şi operaţii de deplasare (eng.: shift).

Vectorii definiţi în spaţiul 2D, care nu sunt orizontali sau verticali, pot fi clasificaţi în opt clase geometrice, numite octanţi. Fie vectorul P1P2 cu P1(x1, y1) şi P2(x2, y2). Octantul din care acest vector face parte se stabileşte în funcţie de diferenţele ∆x: = x2-x1 şi ∆y = y2-y1 astfel:

octantul 1: ∆x > 0, ∆y > 0 şi ∆x ≥ ∆y; octantul 2: ∆x > 0, ∆y > 0 şi ∆x < ∆y; octantul 3: ∆x < 0, ∆y > 0 şi |∆x| < ∆y; octantul 4: ∆x < 0, ∆y > 0 şi |∆x| ≥ ∆y; octantul 5: ∆x < 0, ∆y < 0 şi |∆x| ≥ |∆y|; octantul 6: ∆x < 0, ∆y < 0 şi |∆x| < |∆y|; octantul 7: ∆x > 0, ∆y < 0 şi ∆x < |∆y|; octantul 8: ∆x > 0, ∆y < 0 şi ∆x ≥ |∆y|.

Metoda Bresenham se aplică numai pentru vectorii din primul octant, cu punctul P1 plasat în origine, deoarece vectorii din ceilalţi octanţi pot fi obţinuţi prin transformările de oglindire şi translatare. Astfel deplasările necesare sunt numai de două tipuri: direcţia 1 (la dreapta cu un punct) şi direcţia 2 (punctul vecin de pe diagonală). Metoda generală are două etape: determinarea octantului şi determinarea punctelor ce aproximează cel mai bine segmentul de trasat. Presupunem că ultimul punct generat are coordonatele (r, q). Cei doi candidaţi posibili pentru alegerea următoare sunt: (r+1, q+1) care corespunde deplasării diagonale şi (r+1, q) ce corespunde deplasării de-a lungul axei.

Fie b/a := m = ∆y/∆x, atunci y = m* (r+1). Notăm S1 := y-q = m*(r+1)-q

şi S2 := (q+1) - y = (q+1) - m*(r+1).

Dacă S1 < S2 atunci deplasarea este axială, altfel deplasarea este de tip diagonal. Evident, deoarece a>0,

S1 < S2 ⇔ 2*(b*r - a*q) + 2*b – a<0. Fie S(r, q) := 2*(b*r -a*q) + 2*b -a. Atunci:

S(r+1, q) = S(r, q) + 2*b, iar

S(r+1, q+1) = S(r, q) +2*b - 2*a. Evident S(0, 0) = 2*b-a.

O altă metodă se bazează pe utilizarea punctului mijlociu. În formularea metodei punctului mijlociu se determină de care parte a segmentului considerat se situează punctul Q aflat la mijlocul distanţei dintre cele două valori posibile ale lui y (yi şi yi+1) pentru valoarea xi.

Dacă punctul Q se află deasupra liniei, pixelul mai apropiat de linie va fi yi, în caz contrar se va alege yi+1. Este posibil ca linia să treacă printre punctele (xi, yi) şi (xi, yi+1) sau ambele puncte se pot situa de aceeaşi parte a liniei. În oricare dintre situaţii, testul punctului mijlociu va determina pixelul cel mai apropiat de linie. Practic, distanţa dintre punctul ales şi valoarea exactă nu va depăşi 0.5. Pentru deducerea relaţiilor necesare metodei, se consideră ecuaţia dreptei sub forma: F(x, y) = 0, unde F(x, y) = a*x + b * y + c = ∆y * x - ∆x * y + b*∆x (adică: a := ∆y, b:=-∆x, c:= n*∆x, din reprezentarea y = ∆y/∆x*x+n).

Evident F(x, y) > 0 pentru punctele situate sub linie şi F(x, y) < 0 pentru punctele situate deasupra liniei.

Fie d := F(xi+1, yi+0.5). Dacă d > 0 se alege pixelul (xi+1, yi+1), altfel se alege (xi+1,yi). Este important ca valorile lui d să se calculeze incremental.

Fie dvechi := F(xi+1, yi+0.5) = a * (xi + 1) + b *(yi +1/2). Dacă se alege punctul (xi+1, yi) atunci dnou = dvechi + a (adică incrementare cu ∆y). Dacă se alege punctul (xi+1, yi+1) atunci dnou = dvechi + a + b (adică incrementare cu ∆x+∆y). Primul punct este (x1, y1), iar primul punct mijlociu este (xi+1, yi+1/2). Deci, dstart:=∆y-∆x/2. Apoi se aplică ideile de mai sus.

Generarea cercurilor Metodele de generare a interiorului cercurilor în spaţiul discret folosesc pentru calculul punctelor numai operaţii de adunare/scădere cu numere întregi şi testare de semn. Se consideră cercul cu centrul în originea sistemului de coordonate şi raza r. Metoda cea mai puţin performantă constă în a vedea cât de departe este fiecare pixel de centru şi de al colora, dacă este în interior.

Alegerea punctelor care aproximează cel mai bine cercul se bazează pe una dintre următoarele măsuri ale erorii de aproximare:

• diferenţele dy1 = |y-yi| şi dy2 = |yi+1-y| dintre ordonata punctului de pe cercul teoretic, y, şi ordonatele punctelor spaţiului discret, yi şi yi+1, care au aceeaşi abscisă cu punctele de pe cerc; diferenţa dy1-dy2 este numită eroare axială;

• diferenţele dr1 = |r-rinterior| şi dr2 = |rexterior-r| dintre raza cercului teoretic, r, şi razele cercurilor care au acelaşi centru cu cercul teoretic şi trec prin punctele spaţiului discret între care se efectuează alegerea; diferenţa dr1-dr2 este numită eroare radială;

• diferenţele ds1 = |r2-rinterior2| şi ds2 =|rexterior

2-r2| dintre suprafaţa cercului teoretic şi suprafeţele cercurilor care au acelaşi centru cu cercul teoretic şi trec prin punctele spaţiului discret între care se efectuează alegerea; diferenţa ds1-ds2 este numită eroare reziduală sau pătratică;

Metoda Bresenham, prezentată în continuare, foloseşte eroarea axială ca

măsură a apropierii punctului ales de cercul teoretic.

Se consideră cercul cu centrul în originea sistemului de coordonate şi raza r>0. Metoda calculează numai punctele din octantul al doilea, celelalte obţinându-se prin simetrie. Fie (xi, yi) ultimul punct al spaţiului discret, ales pentru aproximarea cercului. Următorul punct va fi unul dintre (xi+1, yi) şi (xi+1, yi-1). Ordonata punctului de pe cercul teoretic se obţine din ecuaţia cercului în coordonate carteziene:

y2 = r2 – (xi+1)2 Se calculează distanţa dintre punctul de pe cerc şi cele două puncte candidate:

d1 = yi2-y2 = yi

2-r2+(xi+1)2 ; d2 = y2- (yi-1)2 = r2 – (xi+1)2-(yi-1)2. Fie ti eroarea de aproximare în pasul curent:

ti = d1-d2 = yi2+2*(xi+1)2+(yi-1)2-2*r.

Se obţine o relaţie de recurenţă pentru calculul erorii de aproximare în pasul următor, folosind

ti+1 = yi+12+2*(xi+1+1)2+(yi+1-1)2-2*r.

Cazul 1: Dacă ti<0 atunci xi+1 = xi+1 şi yi+1=yi. Deci, ti+1 = yi

2+2*((xi+1)+1)2+(yi-1)2-2*r sau

ti+1 = ti+4*xi+6. Cazul 2: Dacă ti ≥ 0 atunci xi+1 = xi+1 şi yi+1 = yi. Deci,

ti+1 = (yi-1)2+2*((xi+1)+1)2+((yi-1)2-2*r sau

ti+1 = ti+4*(xi-yi)+10 Valoarea erorii la primul pas se obţine înlocuind în expresia lui ti pe xi cu x1 = 0 şi pe yi cu y1 = r. Rezultă:

t1 = 3-2*r. Metoda punctului mijlociu se aplică şi pentru generarea cercurilor. Fie F(x,

y) = x2 + y2 -r2. Evident F este nulă pe cerc, pozitivă în exterior şi negativă în interior. Fie P(xi, yi) punctul ales anterior (nu neapărat pe cercul teoretic), E(xi+1, yi), SE(xi+1, yi-1) şi M mijlocul segmentului determinat de punctele E şi SE. Se presupune că cercul teoretic trece printre E şi SE. Pixelul curent va fi ales dintre E şi SE pe baza testului asupra punctului M. Fie d o variabilă de decizie, valoarea funcţiei în punctul M:

dvechi = F(xi+1, yi-0.5). Dacă dvechi < 0, se alege E, iar următorul punct mijlociu va conduce la:

dnou = F(xi+2, yi-0.5), adică

dnou = dvechi + 2*(xi+3). Notăm ∆E := 2*(xi + 3). Dacă dvechi ≥ 0, alegem punctul SE. Deci alegerea noului punct mijlociu va conduce la:

dnou = F(xi+2, yi-1.5), adică

dnou = dvechi + (2*xi - 2*yi + 5).

Notăm cu ∆SE expresia dintre paranteze. Dacă generăm cercuri cu rază întreagă în al doilea octant atunci pixelul de start este (0, r), iar următorul punct mijlociu este (1, r-0.5). Efectuând calculele obţinem dstart = 5/4-r (operaţii executate în virgulă mobilă).

Generarea elipselor Pentru generarea elipselor în spaţiul discret au fost propuse mai multe metode: Pitteway (1967), Van Aken (1984), Kappel (1985) şi Da Silva (1989). Prezentăm metoda lui Da Silva (vezi [39]) care combină ideile predecesorilor săi cu scopul obţinerii eficienţei. Fie elipsa standard, cu centrul în origine, definită prin ecuaţia implicită:

F(x,y) = b2 * x2 + a2 * y2 – a2 * b2 = 0, unde a şi b sunt numere întregi pozitive care reprezintă lungimile semiaxelor (2*a este lungimea axei mari, iar 2*b este lungimea axei mici). Elipsa intersectează axa Ox în (a, 0) şi (–a, 0), iar axa Oy în (0, b) şi (0, –b).

Metoda generează aproximarea discretă a elipsei în primul cadran, împărţit în două regiuni: punctul care separă cele două regiuni are proprietatea că panta tangentei la curbă în acest punct este -1. Celelalte puncte se obţin prin simetrie. Se utilizează metoda punctului mijlociu. Deoarece

gradient F(x, y) = (2b2x, 2a2y), rezultă că între cele două regiuni se comută atunci când coordonatele punctului mijlociu verifică inegalitatea:

b2(xi+1) ≥ a2(yi-0.5). Fie d1 variabila de decizie asociată regiunii 1 şi d2 variabila de decizie a regiunii 2. Dacă pixelul curent este P(xi, yi) atunci d1 este definită prin F(xi, yi-0.5), iar d2 prin F(xi+0.5, yi-1). Pentru prima regiune se va alege între E(xi+1, yi) şi SE(xi+1, yi-1). Dacă se alege punctul E atunci variabila de decizie pentru următorul punct mijlociu este:

dvechi = F(xi + 1, yi - 0.5). Cum

dnou = F(xi + 2, yi - 0.5), efectuând diferenţa de ordinul I, se obţine:

dnou = dvechi + b2(2xi+3), adică

∆E = b2(2xi+3). Dacă se alege punctul SE, în mod similar se obţine:

∆SE=b2(2xi+3)+a2(-2yi+2). În regiunea 2, variabila de decizie se calculează în punctul mijlociu dintre S(xi, yi-1) şi SE(xi+1, yi-1). Se obţin:

∆E = a2(-2yi+3) şi ∆SE = b2(2xi+2)+a2(-2yi+3). Pentru stabilirea condiţiilor iniţiale, se consideră că semiaxele sunt date

prin numere întregi, punctul iniţial este (0, b), iar primul punct mijlociu are coordonatele (1, b-0.5):

dstart = F(1, b-0.5)=b2+a2(-b+0.25). Spre deosebire de cazul circumferinţei, pentru elipsă, la fiecare pas din regiunea 1, în afara actualizării variabilei de decizie şi a cantităţilor ∆, trebuie verificat dacă nu s-a intrat în regiunea 2. 2.2.3. Calculul unor proprietăţi globale Pentru entităţile 2D se pot calcula lungimii (inclusiv pentru curbe), suprafeţe, centru de greutate etc. Mărimi similare ataşate obiectelor spaţiale sunt descrise în continuare. Proprietăţile globale ale solidelor se referă la volum, arie, momente de inerţie, centru de greutate ş.a.m.d. În general, calculul proprietăţilor globale necesită evaluarea unei integrale triple de forma:

∫=Solid

dVpf )(ϕ ,

unde ϕ este proprietatea considerată, iar f(p) este funcţia care descrie proprietatea ϕ. Considerând reprezentările primitivelor geometrice se pot obţine proprietăţile globale pentru fiecare din acestea. Cititorul îşi poate aminti formulele de calcul ale suprafeţei şi volumului pentru corpurile geometrice de bază. Desigur, pentru unele primitive există şi metode analitice simple. Exemplificăm prin volumul unui tetraedru cu coordonatele vârfurilor (xi, yi, zi), i = 1, 2, 3, 4:

1111

61

444

333

222

111

zyxzyxzyxzyx

V ±= .

Dacă solidul este descris prin metoda descompunerii şi enumerării ocupării spaţiale:

Ui

iCelulaSolid =

folosind compunerea disjunctă a celulelor şi solidelor (celulele au interioarele disjuncte), atunci integrala pe tot solidul este suma integralelor:

∑ ∫∫ =i CelulaSolid i

dVpfdVpf )()( .

Complexitatea evaluării integralei asociate unei celule depinde de tipul celulei. Celule întâlnite în descompunerea octree sunt de acelaşi tip (elemente de volum).

Dacă parametrii reprezentării celulei sunt valori în intervalul unitate [0, 1] şi J este matricea iacobian a transformării de coordonate, rezultă:

[ ]dudvdw dxdydz

31,0∫∫∫∫∫∫ = Jff

Celula

.

În reprezentarea pe frontiere, teorema lui Gauss ne furnizează metoda imediată de calcul.

Fie g o funcţie vectorială continuă, atunci

∫∫ ><=>∇<SuprafataVolum

dAn g,dVg , ,

unde n este normala (vector unitar) la suprafaţa. Integrala din membrul drept este considerată pe întreaga suprafaţa a volumului V. De obicei, suprafaţa este compusă din feţe disjuncte:

∑ ∫∫ ><=><i FSuprafata i

idFn g,dAn g, .

Aceste formule se aplică şi în cazul modelelor de tip petic ale suprafeţelor. Pentru abordarea CSG, care facilitează o abordare de tip “divide et impera” se pot utiliza următoarele formule:

∫ ∫∫ ∫ ∩∪−+=

B BABA AfdVfdVfdVfdV ,

∫∫∫ −=− BAABA

fdVfdVfdVI

.

Totuşi o abordare de acest tip este costisitoare din punct de vedere al calculelor, mai ales că evaluarea numerică a unei integrale nu este o problemă simplă, iar erorile de calcul se pot propaga (de la frunze spre rădăcină) în întreg arborele. Timmer şi Stern (vezi [64]) propun utilizarea repetată a teoremelor de integrare (teorema lui Gauss, teorema lui Green) pentru a transforma integrala volumetrică în integrală curbilinie şi aplicarea formulelor de cuadratură gaussiene pentru aproximarea integralelor. Dificultatea majoră apare privind identificarea unei funcţii g (care să conducă la calcule simple) astfel încât: f = <∇, g>. Folosind reprezentarea prin frontieră sau rezultatul evaluării frontierei, în cazul reprezentării CSG, integrala pe volum se va reduce la o sumă de integrale pe porţiuni ale suprafeţei. Dacă suprafaţa este o parametrizare a unei triangularizări atunci se pot utiliza formule de cuadratură convenabile, atât planare cât şi spaţiale. 2.3. Diagrame şi probleme conexe Descompunerea unei suprafeţe într-o reţea de poligoane este utilă atăt pentru modelarea prin frontiere căt şi pentru realizarea diferitelor calcule geometrice. Metoda elementului finit, utilizează din abundenţă astfel de descompuneri. Cu excepţia descompunerilor ce apar în rezolvarea unor probleme particulare (de calcul numeric), cele mai importante descompuneri sunt triangularizările. Desigur, metodele euristice, descrise mai sus, pentru obţinerea unei reţele cu triunghiuri mai mici sunt utile. Dar, este nevoie de un mecanism automat pentru realizarea unor astfel de descompuneri. 2.3.1. Diagrama Voronoi

Fie S o mulţime de puncte din plan şi d distanţa euclidiană. Dacă pi şi pj sunt două puncte distincte din S atunci mulţimea punctelor q astfel încât d(q, pi) ≤ d(q, pj) este semiplanul H(pi, pj), determinat de mediatoarea segmentului pipj, care conţine punctul pi. Regiunea Voronoi6 asociată punctului pi este mulţimea V(i) obţinută ca intersecţie a celor n-1 semiplane:

V(i) = I . ij

ji ppH≠

),(

Cele n regiuni formează o partiţie a planului numită diagramă Voronoi, notată prin V(S). Vârfurile diagramei (intersecţii de mediatoare) se numesc vârfuri Voronoi, iar segmentele rezultate se numesc muchii Voronoi. Notăm, simplu, prin V mulţimea Vârfurilor şi prin E mulţimea muchiilor diagramei V(S). Pentru un punct oarecare din plan, dacă (x, y) ∈ V(i) atunci pi este unicul punct din S situat la cea mai mică distanţă de (x, y). Presupunem că oricare patru puncte din S nu sunt conciclice. Diagrama Voronoi are următoarele proprietăţi:

(1) Fiecare vârf al diagramei Voronoi este intersecţia a exact trei muchii ale diagramei - adică, vârfurile Voronoi sunt centre ale cercurilor definite de trei puncte din mulţimea S. Pentru un punct v ∈ V, fie C(v) cercul cu centru în v.

(2) Pentru oricare v ∈ V, C(v) ∩ S =∅ (rezultă imediat prin reducere la absurd).

(3) Fiecare cel mai apropiat vecin pentru pi, în S defineşte o muchie a regiunii V(i).

(4) Regiunea V(i) este nemărginită dacă şi numai dacă pi este un punct pe frontiera acoperirii convexe a mulţimii S.

2.3.2. Triangularizare Delaunay Graful dual al unei diagrame Voronoi V(S) este graful D = (S, M) unde nodurile grafului D sunt punctele mulţimii S, iar muchiile reprezintă mulţimea perechilor (pi, pj)∈SxS cu proprietatea că V(i) şi V(j) au în comun o muchie din E. Delaunay (1934) a demonstrat că, în ipoteza de mai sus asupra mulţimii S, graful D defineşte o triangularizare plană a mulţimii de puncte S - acoperirea convexă a mulţimii S este partiţionată în triunghiuri, determinate de punctele din S, astfel încât oricare două triunghiuri au interioarele disjuncte. Elementele mulţimii M se numesc muchii Delaunay. Rezultă că trei puncte din S dau naştere la un triunghi Delaunay dacă şi numai dacă cercul lor circumscris nu conţine în interior nici un alt punct din S. Obţinem, astfel, un algoritm pentru obţinerea triangularizării Delaunay, de complexitate n4, numit algoritmul cercului vid care pentru fiecare din cele n(n-1)(n-

6 Regiunile Voronoi au fost studiate de Dirichlet, în 1850. Ele se mai numesc zone Wigner-Seitz sau poligoane Thiessen.

2) triplete (pi, pj, pK), verifică dacă vreunul din cele n-3 puncte pt, cu t ∉ {i, j, k}, se află în interiorul cercului. Shamos şi Hoey (vezi [67]) au propus un algoritm, bazat pe metoda Divide et impera, a cărui complexitate, în cazul cel mai defavorabil, este O(n log n) pentru a construi diagrama Voronoi. Rezultă un algoritm cu aceeaşi complexitate pentru a obţine triangularizarea Delaunay. Un algoritm de complexitate O(n2), dar mai simplu de implementat, dezvoltat de Guibas şi Stolfi, construieşte triangularizarea Delaunay Di = Di(p1, p2, ..., pi-1, pi) prin inserarea vârfului pi în triangularizarea Di-1. Mulţimea Di este obţinută prin schimbarea muchiilor, conform procedurii Lawson, până când toate muchiile care invalidau punctul pi au fost înlăturate. Dacă e = pq este o muchie a acoperirii convexe a mulţimii S, semiplanul H mărginit de muchia e care nu conţine S este triunghi infinit cu latura e, iar cercul său circumscris, prin convenţie, este chiar H. Acel triunghi din Di-1 (finit sau infinit) al cărui cerc circumscris conţine noul punct pi este în conflict cu pi.

Fie qr ∈ Di-1 şi T(q, r, t) un triunghi adiacent laturii f situat de cealaltă parte a laturii qr decât pi. Dacă cercul circumscris C(q, r, t) conţine pi atunci orice cerc prin q şi r conţine cel puţin unul din punctele pi, t. Deci qr ∉ Di. Rezultă că pit este o nouă muchie Delaunay deoarece există cercul circumscris C(q, r, t) care conţine numai pi şi t în interior sau pe frontieră. Înlocuirile de muchii continuă până nu se mai pot face înlocuiri. În final se obţine mulţimea Di. Cunoaşterea unui triunghi T(q, s, r) din Di-1 care conţine pi facilitează procesul de înlocuire. Segmentele piq, pir şi pis vor fi muchii Delaunay din aceleaşi motive ca mai sus. Se testează dacă muchiile qr, qt şi tr pot fi înlocuite. Numărul de înlocuiri este maximum gradul vârfului pi (numărul muchiilor care îl au ca extremitate). Dar acesta este majorat de n. Cum trebuie introduse n vârfuri, complexitatea algoritmului este O(n2). Dacă S este o submulţime din spaţiul Euclidian (3D) atunci prin triangularizare se înţelege o descompunere a acoperirii convexe a mulţimii S în tetraedre cu interioare disjuncte ale căror vârfuri sunt puncte din S. Generalizând metoda Delaunay, se poate adăuga faptul că sfera circumscrisă fiecărui tetraedru să nu mai conţină un alt punct din S în interior. Dintre multitudinea de metode propuse pentru a construi diagrama Voronoi 3D, metoda incrementală este cea mai intuitivă şi uşor de implementat. 2.4. Modelarea terenurilor Datele geometrice manipulate de sistemele informatice geografice (eng.: GIS - Geographical Information Systems) sunt de tip hartă (eng.: map) şi de tip teren (eng.: terrain). Datele de tip hartă sunt localizate pe suprafaţa Pământului fiind modelate bidimensional: puncte, linii, regiuni poligonale, combinate pentru a forma fie aranjamente, fie subdivizări, organizate pe straturi, iar datele de tip teren sunt

configuraţii tridimensionale, modelate ca suprafeţe 212

, adică suprafeţe în spaţiul

3D descrise prin funcţii de două variabile. Datele de tip true - 3D sunt modelate ca

mai sus, metodele de reprezentare şi redare a obiectelor spaţiale fiind împrumutate din domeniul proiectării asistate de calculator. Pe baza datelor eşantionate se pot construi diverse modele pentru reprezentarea reliefului (eng.: DTM - Digital Terrain Models). Modelele matematice pot fi globale (o singură funcţie care interpolează toate datele) sau locale (definite pe o partiţie a domeniului compusă din petice). O suprafaţă topografică (teren) σ este imaginea unei funcţii de două variabile definită pe un domeniu compact Θ din planul Euclidian: σ = {(x, y, f(x,y)|(x,y)∈Θ}. Fiind dată o valoare reală h, mulţimea Cσ(h) = {(x,y) ∈ Θ | f(x,y) = h} este mulţimea contururilor suprafeţei σ de înălţime h şi este formată din curbe simple (curbe de nivel) dacă f nu are puncte de maxim, minim, şea sau platou la înălţimea h. Un model digital (DTM) utilizează doar o mulţime finită de date: V = {v0, v1, ..., vn} ⊂ Θ şi o mulţime de segmente, care să nu se intersecteze, cu extremităţile în V: E = {e0, e1, ...., em}. Pentru sistemele GIS sunt utile următoarele clase de modele:

1. Terenuri poliedrale: imaginea unei funcţii liniare pe porţiuni. Modelul unui teren poliedral este constituit dintr-o reţea poligonală a domeniului Θ, cu vârfurile din mulţimea V (astfel încât segmentele din E apar ca muchii frontieră pentru regiunile poligonale). Imaginea funcţiei f pe fiecare regiune poligonală este un petic planar (vezi şi reprezentările parametrice din capitolul 4).Cele mai utilizate reţele poligonale sunt bazate pe triunghiuri, în general, reţeaua triunghiulară fiind neregulată (eng.: TIN - Triangulated Irregular Network). Se poate lucra şi cu descompunere asociată grilelor. Grilele pot fi carteziene (ortogonale), uniforme - cu spaţiere constantă între liniile grilei (de obicei dreptunghiulare, dar pot fi şi oblice), rectangulare neuniforme, regulate - fiecare punct interior are acelaşi număr de vecini (exemplu: numai de triunghiuri sau numai de patrulatere), neregulate sau nestructurate cât şi de tip hibrid.

2. Modele ortogonale: Se consideră o reţea (grilă) regulat% (în general orogonală) peste Θ şi o descompunere în patrulatere cu vârfurile în V (V fiind puncte ale grilei). Modelul RSG: Regular Square Grid utilizează pătratul ca obiect director al descompunerii. Funcţia f este o funcţie biliniară (liniară în ambele argumente) care interpolează punctele reţelei. Uneori se utilizează modele în trepte: pe fiecare patrulater, funcţia f este considerată constantă.

3. Curbe de nivel: Fiind dată o mulţime H = {h1, h2, ..., hk} de numere reale, o hartă digitală a curbelor de nivel pentru suprafaţa σ este o aproximare a colecţiei de contururi: Cσ,H = {Cσ(hi) | I = 1, 2, ... k}. Adesea, contururile sunt reprezentate prin puncte (redate folosind cercuri sau discuri). Prin interpolare se pot obţine reprezentări de la cele poligonale până la funcţii spline.

Deşi curbele de nivel sunt uşor de înţeles de către operatorul uman şi uşor de reprezentat pe hârtie, ele nu oferă informaţii despre morfologia terenului între curbele de nivel. De aceea nu sunt potrivite pentru o analiză asistată de calculator a terenurilor. Analiza asistată de calculator se poate realiza pentru modelele TIN şi RSG. Un model TIN constă dintr-o triangularizare T a unui domeniu ale cărui vârfuri sunt proiecţii pe planul x-y a punctelor (x, y, f(x,y)) sau doar a unei submulţimi de puncte, incluzând, eventual, o mulţime de segmente ca muchii ale triangularizării T. Cel mai utilizat tip de triangularizare este triangularizarea Delaunay (vezi [77]). Alte triangularizări, unele dependente de valoare f(x,y), se bazează pe criterii de optimalitate conform unor cerinţe specificate. Se pot considera criterii precum: 1) criterii 3D (nu asupra triunghiurilor plane, ci asupra peticelor suprafeţei: maximizarea unghiurilor minime sau minimizarea unghiurilor maxime, minimizarea lungimii muchiilor sau a curbelor ce delimitează peticele suprafeţei etc.); 2) asigurarea unor condiţii de netezime (suprafaţa definită pe porţiuni să fie continuă, eventual de clasa C1); 3) criterii variaţionale: se va alege acea suprafaţă care minimizează o funcţională definită pe un anumit spaţiu de funcţii. Un model TIN se poate obţine direct din puncte, din modelul RSG precum şi din reprezentarea sub formă de curbe de nivel.

Modelul RSG se poate obţine direct din punctele eşantionate (prin mediere asupra vecinilor, metode de interpolare globală, metode de interpolare pe porţiuni), din modelul TIN, sau din contururi (curbe de nivel) prin considerarea acelor puncte care se potrivesc cu grila de pătrate. 2.5. Reprezentarea datelor volumetrice Fie mulţimea D = {(xi, yi, zi, fi) | i = 1, 2, ..., n}. Se doreşte construcţia unui model ϕ parametric sau nu, care să interpoleze sau să aproximeze conform unui criteriu de optimalitate datele din mulţimea D, adică ϕ(xi, yi, zi) = fi, i = 1, 2, ..., n. Procesul de modelare poate fi văzut ca un operator care asociază mulţimii D o funcţie de trei variabile. Dacă notăm X = (x1, x2, ..., xn), Y = (y1, y2, ..., yn), Z = (z1, z2, ..., zn) şi F = (f1, f2, ..., fn) atunci aplicaţia de modelare este definită astfel:

M(X, Y, Z) = MX, Y, Z; F(x, y, z). Dacă se cere ca M să fie liniară relativ la F, adică:

MX, Y, Z; aF(x, y, z) = aMX, Y, Z; F(x, y, z) şi

MX, Y, Z; G+H(x, y, z) = MX, Y, Z, G(x, y, z) + MX, Y, Z; H(x, y, z) atunci funcţia model este o combinaţie liniară de anumite funcţii de bază:

∑=

=n

iiiFZYX zyxBazyxM

1;,, ),,(),,( .

Alături de funcţiile spline şi funcţiile Hermite, funcţiile distanţă reprezintă o categorie aparte de funcţii de bază.

Fie pi := (xi, yi, zi), i = 1, ..., n; p = (x, y, z) un punct 3D şi ||p-q|| distanţa euclidiană dintre punctele p, q ∈ R3. Considerăm modelul:

dzcybxapppM i

n

ii ++++−= ∑

=

3

1)( α .

Dacă impunem condiţia de interpolare şi condiţii suplimentare pentru punctele p1 şi pn, se poate obţine un sistem de ecuaţii liniare de dimensiune (n+4) x (n+4), n fiind numărul de puncte:

M(pi) = fi, i = 1, 2, ..., n; α1 + α2 + ... + αn = 0;

α1x1 + α2x2 + ... + αnxn = 0; α1y1 + α2y2 + ... + αnyn = 0

şi α1z1 + α2z2 + ... + αnzn = 0.

Un astfel de sistem poate fi rău condiţionat numeric. Pe de altă parte, din punct de vedere practic, numărul de punct este foarte mare şi metoda devine greu de implementat pe calculator.

Sunt posibile două alternative (cel puţin): aproximare prin metoda celor mai mici pătrate şi metoda interpolării locale. Prin metoda celor mai mici pătrate, coeficienţii α1, α2, ..., αm, a, b, c, d se determină prin minimizarea expresiei:

2

1 1

3∑ ∑

= =

−++++−

n

i

m

jiiiijij fdzcybxaqpα ,

modelul datelor fiind de forma:

dzcybxaqppM j

m

ji ++++−= ∑

=

3

1)( α ,

unde punctele qj trebuie alese potrivit aplicaţiei. Cea mai simplă alegere constă în generarea unei mulţimi de puncte uniform distribuite în cubul de acoperire a mulţimii iniţiale. O altă abordare se bazează pe alegerea punctelor q astfel distribuite să acopere domeniul similar acoperirii realizate de datele iniţiale. De exemplu putem alege qi drept centrul de greutate al regiunii Voronoi V(pi). Metoda interpolării locale se bazează pe alegerea a două familii de funcţii: Funcţiile wk(p) cu suport local (nenule pe o mică vecinătate) îndeplinesc şi condiţia: w1(p) + w2(p) + ... + wm(p) = 1 pentru oricare p din domeniul considerat. A doua familie de funcţii Fk(p), în general tricubice, are proprietatea interpolării locale: Fk(pi) = fi pentru toate punctele pi din suportul funcţiei wk. Modelul datelor va fi de forma:

)()(1

pFwpM k

m

kk∑

=

= ,

cu proprietatea că M(pi) = fi pentru toate punctele din reuniunea mulţimilor suport ale funcţiilor wk. Trebuie avut grijă ca reuniunea acestor mulţimi suport să acopere întreg domeniul de eşantionare.