Algoritmii de îndepărtare a fețelor invizibile pot fi împărțite condiționat în două clase, în funcție de principiile stabilite pentru punerea lor în aplicare. Prima clasă este algoritmii care lucrează în spațiul obiect. Aceasta înseamnă că pentru a determina vizibilitatea unei fețe date, este comparată poziția sa relativă cu toate celelalte fețe din scena tridimensională. Fie N numarul de fete din scena tridimensionala. Pentru a construi o scenă tridimensională în acest caz, este necesar să se compare poziția fiecărei fețe cu celelalte, ceea ce necesită ordinea
O altă clasă de algoritmi - care funcționează în spațiul imaginii, se bazează pe găsirea punctului celui mai apropiat chip care intersectează linia de vedere care trece prin punctul dat pe raster. Deoarece numărul punctelor de pe ecranul raster este fix, atunci algoritmii din această clasă sunt mai puțin sensibili la creșterea numărului de obiecte din scena tridimensională. Fie n numărul de puncte de pe ecranul raster. Atunci numărul de operații necesare pentru a construi o scenă tridimensională va fi de ordinul
Luați în considerare un algoritm pentru eliminarea fețelor invizibile folosind z-buffer, care este unul dintre cele mai frecvent utilizate în aplicațiile grafice moderne de calculator. Funcționează în spațiul imaginii și este utilizat în bibliotecile grafice populare precum OpenGL și Direct3D.
Algoritmul funcționează în proiecție paralelă. Permiteți ca fereastra de ieșire sau dimensiunea ecranului să fie puncte X în lățime și puncte Y în înălțime. Ca z-buffer, introducem o matrice bidimensionala rectangulara de numere cu dimensiuni care coincid cu fereastra de iesire sau ecran, adica X
La începutul algoritmului, valorile corespunzătoare infinitului sunt înscrise în bufferul z. Fiecare față a unui obiect tridimensional, reprezentat ca un poligon, este transformat într-o formă raster. Când se descompune într-un raster, valoarea coordonatei sale z este calculată pentru fiecare punct al poligonului. Dacă coordonatul z este mai mic decât valoarea curentă din z-buffer, coordonatul z al punctului este scris în z-buffer, iar punctul este desenat pe ecran cu culoarea poligonului curent. După descompunerea tuturor poligoanelor în raster, este construită imaginea scenei tridimensionale.
Să considerăm o metodă de calcul accelerat al coordonatelor z la descompunerea poligoanelor într-un raster. Să scriem ecuația planului format de poligon în spațiu:.
Exprimăm z-coordonatele punctului :. Lasă-l să fie. Gasim coordonata z pentru punctul vecin
Metoda constă în trei etape principale:
Aranjamentul tuturor poligoanelor în conformitate cu cele mai mari coordonate z.
Rezolvarea tuturor incertitudinilor care apar atunci când se suprapun z-shell-uri de poligoane.
Conversia fiecărui poligon într-o formă bitmap, produsă în ordinea descrescătoare a celei mai mari coordonate z.
Cea mai apropiată poligoane sunt convertite în format raster a acestuia din urmă și închise poligoane mai îndepărtate, așa cum este ilustrat în partea de sus a celor anterioare. Punerea în aplicare a punctelor 1 și 3 este destul de evidentă. Să luăm în considerare mai multe detalii de la punctul 2.
Fie ca poligonul P să fie la sfârșitul listei, adică este cel mai îndepărtat. Toate cojile poligonale se suprapun cu z-shell-ul P trebuie să treacă testul a cinci teste (pași). Dacă într-un anumit pas este primit un răspuns afirmativ, atunci P este imediat transformat într-o formă raster.
x-Shells de poligoane nu se suprapun, astfel încât poligoane în sine nu se suprapun.
y - Cochilii poligonali nu se suprapun, astfel încât poligoanii înșiși nu se suprapun.
Situat complet pe partea laterală a planului Q, care este mai departe din punct de vedere (acest test dă un răspuns pozitiv, așa cum se arată în figura 36 a).
Q este situat complet pe partea laterală a planului P, care este mai aproape de punctul de vedere. Acest test oferă un răspuns pozitiv, așa cum se arată în Fig. 36b).
Proiecțiile poligonului de pe planul xOy, adică pe ecran, nu se suprapun (acest lucru este determinat prin compararea marginilor unui poligon cu marginile celuilalt).
Fig. 35.
Fig. 36. Aranjamente mutuale de triunghiuri în spațiu.
Dacă în toate cele cinci teste este primit un răspuns negativ, atunci P - închide cu adevărat Q. Apoi schimbați P și Q în listă în locuri. În acest caz, după cum se arată în figura 37, algoritmul este înclinat.
Pentru a evita buclele, este introdusă o constrângere: un poligon mutat la sfârșitul listei (adică etichetat) nu poate fi repus în mișcare. În schimb, poligonul P sau Q este divizat de planul celuilalt în două poligoane noi. Aceste două poligoane noi sunt incluse în locurile corespunzătoare din lista ordonată, iar algoritmul continuă să funcționeze.
Spre deosebire de algoritmii universali, un algoritm foarte specializat pentru îndepărtarea fețelor invizibile ale corpurilor convexe face posibilă efectuarea calculelor mult mai rapid. Funcționează pentru proiecția de perspectivă centrală. Luați în considerare funcționarea acestui algoritm folosind exemplul prezentat în Fig. 38.
Fig. 38. Intersecțiile liniei AB cu planurile fețelor prismei.
Lăsați observatorul să se afle în punctul A. Alegeți punctul B. care este cunoscută ca fiind internă pentru o figură convexă, în acest caz o prismă. Alegem o față, despre care vrem să știm că este vizibilă din punctul A. sau nu este vizibilă. Construim planul în care se află chipul selectat. Gasim punctul de intersectie al planului si al liniei drepte, care este formata de segmentul AB. Dacă punctul de intersecție al unei linii drepte și al unui plan se află în interiorul segmentului AB. apoi concluzionăm că această față este vizibilă. Dacă punctul de intersecție este în afara segmentului AB. atunci fața nu este vizibilă. În cazul în care linia și planul sunt paralele, presupunem că fața nu este vizibilă.
Trimiteți-le prietenilor: