Structuri de elemente: intersec ția de segmente liniare in plan, [600765]

Proiect MAPI

Structuri de elemente: intersec ția de segmente liniare in plan,
triunghi, paralelogram, punct principal, cerc

Student: [anonimizat]: Dr. Ing. Andrei Hossu
Master PCSAM

2
Introducere. Imagini. Formarea imaginilor
Termenul de „imagine‟ se refera la o functie bidimensionala a intensitatii luminoase
f(x,y), unde x si y sunt coordonatele spatiale, iar valoarea lui f in orice punct (x,y) este
proportionala cu stralucirea (sau nive -lul de gri ) al imaginii in acel punct . O imagine binara este
o imagine f(x,y) car e a fost discretizata atat spatial cat si din punct de vedere al stralucirii.
Cele doua parti din procesul de formare al imaginilor:
– Geometria formarii imaginii care determina unde se va gasi proiectia unui punct in
planul imaginii;
– Fizica luminii care det ermina luminozitatea punctului in planul imaginii, ca o functie
de iluminare si suprafata.

Imaginea se formeaza pe retina cu ajutorul sistemului diopti c al ochiului. Imaginea care
se formeaza este o imagine reala, rasturnata si mai mica decat obiectul vizat. Ochiul are toate
punctele cardinale situate pe axa optica. Toate suprafetele de refractie ale ochiului se comporta
ca si cum ar fi o singura lentila cu centrul la 17 mm inaintea retinei si cu o putere de refractive
totala de cca 60 dioptrii. Multa vreme s -a considerat ca echivalenta acestei lentile este cristalinul.
Dar cea mai mar e putere de refractie nu o are cristalinul, ci fata anterioara a corneei. Diferenta
maxima de densitate a mediilor transparente strabatute de razele luminoase se intalneste la
interfata aer -cornee.
Un model simplu :
– Scena este iluminata de o singura sursa ;
– Scena refleca radiatia spre camera;
– Camera o vede prin intermediul senzorului.

3

Geometria camerei :
– Cel mai simplu dispozitiv ca sa formezi o imagine a unei scene 3D pe o suprafata 2D este
“pinhole camera ”.
– Raze le de lumină trece printr -o "orificiu" și formează o imagine inversată a obiectului pe planul
imaginii.

4
Structuri de elemente: intersectia de segmente liniare in plan, triunghi, paralelogram,
punct principal, cerc
Românul Grigore Burdea, profesor la Universitatea Rutgers (USA) și unul dintre
precursorii cercetărilor asup ra sistemelor de realitate virtuală teoretice și practice (a condus
Departamentul de Interfețe om -mașină), înscrie realitatea virtuală într -un triunghi având fiecare
latură notată cu „i", ele raportându -se la cele 3 fundamente ale realității virtuale:

Imersiunea este trăsătura care impune ca subiectul să se scufunde fizic în mediul virtual.
Imersiunea propune deplasarea și exploatarea universului virtual, ceea ce este posibil prin
suprimarea contactului cu lumea reală, utilizând dispozitive speciale car e împiedică acțiunea
stimulilor din lumea reală și care astfel fac să dispară orice punct de reper din sistemul de
referință al lumii reale.
Conceptul de imersiune propune o altă viziune a lumii, prin izolarea totală a subiectului
de lumea exterioară. Ace asta se realizează în primul rând, prin evitarea oricăror interferențe cu
realul.
Ființa umană percepe realitatea prin intermediul celor cinci simțuri care, după Morton
Heilig, influențează ate nția în următoarele procente :
– văzul 70%

5
– auzul 20%
– mirosul 5%
– tactilul 4%
– gustul 1%
Simțurile care captează atenția în proporția cea mai mare sunt văzul și auzul. În
momentul de față în domeniul audio s -au realizat și funcționează sisteme de audiție 3D care
satisfac cerințele celor mai pretențioase ap licații de realitate virtuală. Domeniul vizualului, care
captează peste 70% din stimuli reali, a putut fi dezvoltat prin progresul graficii de sinteză ,
calculul numeric computerizat permițând producția imaginilor tridimensionale, determinarea
instantanee a poziției ochiul ui și unghiului de vizionare .
Interacțiunea oferă subiectului puteri asupra lumii virtuale, îi permite să se miște după
cum dorește, să sesizeze obiectele și să comunice acestora comenzi sau să converseze cu ființele
de sinteză pe care l e întâlnește . Aceste particularități disting RV de teatru, de cinema sau de
televiziune, unde spectatorul nu poate interveni asupra derulării acțiunii.
Fără interacțiune, subiectul nu este decât un spectator pasiv al unui univers asupra căruia
nu poate in terveni. Interacțiunea îi permite să se deplaseze liber și să primească în retur stimuli
vizuali (după mișcarea privirii), auditivi sau senzoriali (șoc, elasticitatea unui obiect, greutate sau
rezistență la apăsare). Interacțiunea se obține printr -un schim b bidirecțional de date între operator
și mediul virtual. Ea implică însă din partea sistemului de realitate virtuală, timpi de răspuns
foarte scurți.
Imaginația lasă utilizatorului concepția liberă de a defini legile care regizează universul
virtual. Se pot modela lumi și obiecte strict conforme cu realitatea (simulare) sau care eludează
toate sau o parte din legile fizice.
Generarea imaginilor de sinteză este o succesiune de două acțiuni: crearea scenei ca parte
a mediului virtual și reprez entarea prin afișare cât mai realistă a scenei create. Pentru activitățile
de generare a scenelor, este essential studiul trasării și modelării primitivelor (curbe, suprafețe,

6
volume), precum și al asamblării primitivelor pentru obținerea obiectelor comple xe și apoi, al
scenelor.
Reprezentarea exactă a unui obiect complex este foarte dificilă. Se impune utilizarea unor
simplificări, a unor aproximări mai mult sau mai puțin exacte cu ajutorul curbelor și suprafețelor,
ca primitive matematice. Acestea pot fi stocate în memoria calculatorului de o manieră eficace și,
de asemenea, manipularea lor este facilă.
În această lucrare se referă trei tipuri de definiții ale primitivelor geometrice:
– parametrice (ansamblul punctelor (x, y) pentru care x = f(t); y = g( t), unde t este un parametru
variabil);
– implicite (ansamblul de puncte (x, y) pentru care f(x, y) = 0);
– explicite (ansamblul de puncte (x, y) pentru care y = f(x); aceasta este o formă mai rar utilizată).
Definirea matematică a suprafețelor nu este suficientă pentru a reprezenta un obiect de o
manieră completă și pentru sinteza de imagine. Cea mai mare parte a algoritmilor pentru redarea
obiectelor complexe au nevoie de informații topologice (puncte aflate în interiorul conturului,
puncte aflate în exterior sau puncte de frontieră) sau de vecinătate (obiecte vecine).
Elaborarea imaginii unui obiect folosind grafica de sinteză pe calculator, constă în
asamblarea mai multor primitive (volume și suprafețe simple).
Modelarea se definește în acest contex t, ca fiind reprezentarea în memorie a acelui obiect.
De exemplu, un cub poate fi reprezentat prin juxtapunerea a șase careuri în spațiu, sau prin
intersecția a șase semi -suprafețe sau prin deplasarea unui pătrat într -o direcție ortogonală.
Alegerea reprez entării ține cont de scopul modelării: afișarea obiectului, calculul masei sau
volumului său etc.
Alegerea tipului de model și deci a algoritmului de reprezentare trebuie să țină cont d e
următoarele premise :
• domeniul de modelare trebuie să fie suficient de larg pentru a putea reprezenta toate obiectele
care se presupune că va fi necesar să fie modelate;

7
• un obiect trebuie să corespundă unei reprezentări unice și reciproc (nonambiguitate / unicitate);
• reprezentarea obținută trebuie să descrie obiectul modelat cu suficientă precizie;
• evitarea obținerii unei reprezentări invalide;
• reprezentările obținute trebuie să fie arhivate în memoria calculatorului în formă comprimată
(arhivare / compresie).
Dispozitivele de afișare (ecranul monitorului, imprima nta etc.) lucrează, în general, pe o
suprafață bidimensională. Vizualizarea obiectelor 3D trebuie să parcurgă o etapă de proiecție
într-un spațiu tridimensional.
Proiecțiile sunt definite ca transformări particulare ale unui punct din spațiul
tridimensional, într -un punct în planul bidimensional. Acestea sunt bine reprezentate de matricea
de transformare 3D (pentru coordonate omogene), dar care sunt ireversibile (se "pierde" o
dimensiune). Proiecția este definite printr -o suprafață de proiecți e (în general, plană) și un centru
de proiecție.
Fiecare punct al unui obiect de reprezentat este proiectat pe un plan. În cartografie se
utilizează frecvent suprafețe de proiecție non -planare și proiectoare care nu sunt rectilinii.
Proiecțiile rectilinii plane se clasifică în două categorii: proiecții paralele și proiecții perspectivă,
după cum centrul de proiecție este situat sau nu la infinit.
Proiecțiile perspectivă sunt similare celor utilizate de aparatele foto sau de către ochiul
uman, ele dând o b ună sugestie de relief, datorită faptului că un obiect pare cu atât mai mic, cu
cât este situat mai departe.
Proiecția paralelă este mai puțin realistă, deoarece nu are proprietatea de "îndepărtare", în
schimb, aceasta permite măsurarea cotelor unei repre zentări și conservă paralelismul, motiv
pentru care este utilizată în desenul tehnic ingineresc .

8
Modele ale unor e ntități geometrice sunt dezvoltate cu ajutorul unor rețele de puncte.
Aceste puncte pot fi entități ele însele, pot fi puncte de legătură cu alte entități sau pot rezulta în
urma unor intersecții între entități.
Acestea pot fi definite prin valori de tip c oordonate, punctând o anumită poziție pe ecran
sau utilizând o rețea -ghid care identifică coordonatele pe ecran. Alte facilități sunt acelea care
permit configurarea unor noi entități geometrice în scopul folosirii ulterioare a acestora .
Pentru că geometria fiecărei componente trebuie definită precis și construită la
dimens iunea maximă, riscul de a se produce erori este mult mai mic decât într -un sistem
tradițional.
Acest avantaj este evident când se folosesc adnotări sau funcții anterior create sau
facilitățile de stocare pentru modele și în plus, de manipulare a unor baze mari de date. Toate
acestea recomandă proiectarea asistată de calculator drept un instrument puternic pentru
elaborarea de imagini grafice prin sinteză pe calculator.
Curbele Spline sunt curbe de interpolare. Cuvântul Spline desemnează instrumentul
folosit în desenul tehnic pentru trasarea curbelor netede. Spline -ul este fixat în punctele prin care
trebuie să treacă curba cu ajutorul unor greutăți . O curbă Spline poate fi trasată prin oricâte
puncte de control. Forma curbei Spline între două puncte de control este descrisă matematic
printr -un polinom de gradul 3. În general, o curbă Spline este descrisă printr -o funcție
polinomială de grad k definită pe porț iuni, cu derivatele de ordin k-1 continue în punctele de
joncțiune. Astfel, curba Spline cubică are continuitate de ordin 2 în punctele de joncțiune.
Curbe B -spline
Acestea sunt, ca și curbele Bezier, curbe de aproximare definite prin puncte de control,
dar spre deosebire de curbele Bezier, ele sunt descries prin funcții polinomiale definite pe
porțiuni, ceea ce le conferă proprietatea de control local.
Segmentele de curbă B-spline sunt descrise prin polinoame de grad doi sau trei, gradul
fiind independent de numărul punctelor de control.

9
Curbele B-spline sunt definite analitic prin ecuația vectorială:

unde p i sunt punctele de control, iar Ni,k(u) sunt funcțiile de aproximare, numite funcții B -spline;
k determină gradul polinomului de aproxi mare (k – 1) și ordinul de continuitate (k – 2) al curbei.
Funcțiile B-spline sunt definite recursiv astfel:

Din această definiție rezultă că o funcție N j,k(u) este nenulă numai pentru k interval
consecutive. Valorile ti numite valori nodale, trebuie să fo rmeze o secvență monoton crescătoare
( t i ≤ t i + 1 ). Ele asociază variabila u punctelor de control Pi . Pot fi valori reale sau întregi. Dacă
valorile nodale sunt egal distanțate, se spune că vectorul pe care -l formează este uniform, iar
funcțiile B-spline astfel definite sunt uniforme .
Proprietăți ale curbelor B -spline
1. Puncte de control multiple : o curbă B-spline de grad m trece întotdeauna printr -un punct de
control de multiplicitate m. Deci, se poate forța trecerea unei curbe B-spline printr-un punct de
control, introducând punctual respectiv în vectorul punctelor de control din mai multe poziții
succesive.
2. Puncte de control coliniare: dacă m + 1 puncte de control successive sunt situate pe o dreaptă,
atunci curba B-spline de grad m este situată partial pe dreapta respectivă. Astfel, dacă punctele
Pi-1 , Pi , Pi+1 sunt coliniare, segmentul pi , de curbă B-spline de grad 2 se confundă parțial cu
segmental Pi-1 – Pi.

10
3. Curbe închise: pentru a obține o curbă B-spline de grad m închisă, este suficient ca primele
puncte de control să fie identice cu ultimele.
4. Proprietatea de "închidere" convexă: orice curbă B-spline este complet inclusă în poligonul
convex format prin unirea punctelor de control.
5. Invarianța afină: pentru a transforma o cu rbă B-spline este sufficient să se aplice
transformarea afină punctelor de control și apoi să se regenereze curba. Această proprietate o au
și curbele Bezier.
Proprietăți ale curbelor B -spline de gradul 2
Curbele B-spline de gradul 2 sunt adecvate reprezent ării formelor de înaltă precizie
deoarece au un aspect mult mai bine definit decât cubicele.
Astfel, caracterele din setul True Type folosit în sistemul Windows sunt definite folosind
curbe B-spline de grad 2. În afară de proprietățile generale enunțate mai sus, orice curbă B-spline
de grad 2 are și următoarele caracteristici suplimentare :
 trece prin punctul situat la mijlocul distanței dintre două puncte de control succesive;
 în acest punct, tangenta la curbă se confundă cu segmentul care
 unește cele două puncte de control;
 curba este situată în triunghiul definit de un punct de control P i și mijloacele segmentelor
Pi-1 – P1 și Pi – Pi+i.
Reprezentări ale suprafețelor
Una din cele mai importante p robleme în realizarea pe calculator a imaginilor de sinteză
este aceea a modelării suprafețelor. Modelele trebuie să ofere flexibilitate în proiectare, să
conducă la implementări simple ale calculelor proprietăților suprafețelor și, nu în ultimul rând, să
permită descrierea unor forme oricât de variate . Dacă segmentul de curbă este blocul de
construcție fundamental pentru entitățile curbe, "peticele" sunt părțile fundamentale pentru
suprafețe.

11
O suprafață poate fi definită matematic în trei moduri (definiți a analitică a suprafețelor):
(1) printr -o ecuație implicită de forma:
F(x, y, z) = 0;
(2) printr -o ecuație explicită , care exprimă variația uneia dintre cele trei variabile în
funcție de celelalte două:
x = f x (y, z) sau y = f y (x, z) sau z = f z (x, y);
(3) prin ecuațiile parametrice:
x = f x (u, v);
y = f y (u, v); u min ≤ u ≤ umax
z = f z (u, v); v min ≤ v ≤ vmax
Utilizarea ecuațiilor parametrice oferă, ca și în cazul curbelor, o serie de avantaje față de
celelalte metode de modelare, dintre care cele mai evidente sunt:
– reprezentarea este independentă de sistemul de coordonate;
– pot fi reprezentate suprafețe definite prin funcții cu valori multiple;
– transformările 3D exprimate în coordonate omogene pot fi aplicate direct asupra ecuațiilor
parametrice;
– suprafețele definite parametric sunt în mod inerent limitate, prin domeniul de variație al
variabilelor parametrice; alegând domeniul pentru fiecare variabilă se poate defini orice porțiune
a suprafeței;
– ecuațiile paramet rice oferă mai multe grade de libertate pentru controlul formei unei suprafețe.
Ecuațiile parametrice pot fi folosite pentru a reprezenta o mare varietate de suprafețe, așa
cum sunt cele obținute prin baleiere spațială și suprafețele de formă liberă.
Formul ări Bézier
Esența acestor formulări este aceea că definirea suprafețelor și curbelor este asigurată de
un număr de puncte, toate relative la originea și axele modelului. O curbă cubică parametrică

12
poate fi astfel definită prin patru puncte, punctele de sfâ rșit și câte un punct de proiecție
tangențial pentru fiecare vector curbiliniu .

Reprezentările multistrat folosesc straturi Coons bicubice. Când un strat este definit
prima dată, acesta are valori presetate, cu toate pantele 0. ( Figura a). În aceste condiții, muchiile
curbei sunt linii drepte și rămân astfel pâ nă când colțurile A,B,C,D sunt modificate printr -o
comandă a utilizatorului .

13
Când colțurile sunt plasate satisfăcător, stratul este "normalizat" pentru a face din fiecare
din cei 8 vectori de pantă, vectori de coardă ( Figura c). Deși această normalizare nu modifică
muchiile stratului, schimbarea vectorilor de pantă alterează distribuția liniilor parametrice,
prezentând locurile unde vectorii sunt mari / mici. Un vector tangențial mare are o rază mare a
curbei și spațiu mare între liniile parametrice, pe când un vector tangențial mic, are o rază mică a
curbei și un mănunchi de linii parametrice. Normalizarea pregătește utilizarea vectorilor
tangențiali pentru reprezentarea obiectelor tridimensionale.
Mutarea colțurilor stratului int roduce muchii curbe ale stratului ( Figura d). Renunțând la
statica colțurilor, tangentele S AB și SBA, pot fi proiectate pentru a produce muchii curbe pentru
un anumit strat. ( Figu ra e). Schimbările asupra unei muchii determină schimbarea automată ș i
pentru stratul cu care se îmbină.
Figura f prezintă două straturi separate, iar figura g prezintă efectul îmbinării muchiei
AD a stratului 2 cu muchia BC a stratului 1. Dacă este cerută o continuitate a pantei stratului 2,
atunci doar stratul 2 e ste modificat (Figura h). O schimbare asupra SAB din stratul 2 se reflectă
automat asupra lui SBA din stratul 1 și reciproc. Trebuie reconsiderate multiplele schimbări
posibile ce pot afecta un strat și efectul lor asupra straturilor adiacente .
Metode de decupare a poligoanelor și segmentelor
Problema decupării apare atunci când se dorește determinarea intersecției a două sau mai
multe poligoane sau atunci când se afișează o scenă compusă din mai multe poligoane (foarte des
sunt tratate cazurile cu fațete triunghiulare) .

14
După transformare, fațetele pot fi situate în afara ecranului sau chiar în fereastra de afișaj.
Decuparea unui poligon sau a unui segment constă în eliminarea părții poligonului (segmentului)
care se află în afara poligonului sau a ferestrei de afișaj. Vizibilitatea segmentului se determină
pornind de la poziția extremităților sale. Acesta este total vizibil dacă ambele extremități se află
în interiorul ferestrei, este total invizibil când ambele extremități se află în exterior și partial
vizibil în alte cazuri.
Pentru un segment cu extremitățile P1 și P2 și având panta m, intersecțiile posibile cu
fereastra rectangulară sunt:
• la stânga;
• la dreapta;
• sus;
• jos.
În mod analog, se lucrează pentru decuparea poligoanelor. Condiț ia este ca perimetrul
reprezentând conturul unei suprafețe să fie închis. Decuparea suprafeței se face prin
descompunere în părți elementare, după cum acesta se află în interiorul sau în exte riorul ferestrei
de decupar e. Se memorează toate acestea și în pl us, intersecțiile cu laturile ferestrei de decupare.
În mod particular, se pun următoarele probleme:
• vizibilitate (calculul se face prin abordare vectorială);

• tăiere (se determină dacă vizibilitatea actuală și / sau viitoare diferă);
• intersectare (se calculează punctul de intersecție între segmente/ suprafețe și marginile ferestrei
de decupare);
• stocare (se memorează locul punctelor în cadrul decupajului).

15
Bibliografie:
[1] Akeley K. , Reality Engine Graphics. Computer Graphics Proceedings, Annual Conference
Series,1993, ACM SIGGRAPH, July 1993, 109 -116
[2] Saphiro L., Stockman G., Computer Vision, 2000
[3] Bernardini F., Rushmeier H. E., The 3D Model Acquisition Pipeline, Computer Graphics
Forum 21(2), pp 149 -172, 2002
[4] Burdea G., Coiffet Ph., La realite Virtuelle , Ed. Hermes, Paris, 1995
[5] Cack L., Hege H., Hardware -accelerated point -based rendering of complex scenes, 13th
Eurographics workshop on Redering, pp 43 -52, 2002
[6] Stefanescu B., Tehnici modern de generare a mediilor virtuale prin sinteză grafică
asistată de calculator
[7] Goldstein R. A., Nagel R., 3D Visual Simulation , Simulation, 2004
[8] Glassner A., An introduction to Raz Tra cing, Academic Press, 1999
[9] Ionescu F., Programarea aplicațiilor grafice , București, Printech, 2004
[10] Alexandru C. , Modelarea și prototipizarea virtuală a mecanismelor pe baza softurilor
performante tip MBS, Universitatea Transilvania Brașov, Facultat ea I.T., 2009
[11] Vince J., Virtual Reality Systems , Wokingham Addison -Wesley, 1995
[12] Visa A., Texture classification and segmentation based on neural network me thods ,
Helsinky University of Technology, 2006