Algoritmul pictorului
Algoritmul pictorului , cunoscut și ca umplere prioritară , este una dintre cele mai simple soluții la problema vizibilității în grafica computerizată . Când reprezentați o scenă tridimensională pe un plan bidimensional, este necesar să decideți ce poligoane sunt vizibile și care vor fi ascunse.
Numele algoritmului se referă la metoda simplă utilizată de pictorii care desenează mai întâi părțile îndepărtate ale scenei și apoi le acoperă cu cele mai apropiate părți. Algoritmul pictorului sortează toate poligoanele din scenă după adâncimea lor și ulterior le desenează în ordine. [1] În acest fel, părțile ascunse vor fi revopsite cu părțile vizibile, în detrimentul costului de a fi necesară revopsirea zonelor scenei.
Algoritmul poate eșua în unele cazuri. În acest exemplu, poligoanele A, B și C se suprapun. Nu este posibil să decidem care poligon se află deasupra celorlalte. [2] În acest caz, poligoanele trebuie tăiate într-un fel pentru a permite sortarea. Algoritmul lui Newell propus în 1972 oferă o metodă pentru tăierea acestor poligoane. Au fost propuse numeroase alte metode în domeniul geometriei de calcul .
În implementarea sa de bază, algoritmul pictorului poate fi ineficient. Forțează sistemul să redea fiecare punct al tuturor poligoanelor din setul vizibil, chiar dacă unele poligoane sunt ascunse în scena finală.
Algoritmul pictorului inversat [3] este folosit uneori prin desenarea mai întâi a obiectelor apropiate de pictor - cu regula că părțile deja desenate nu vor fi redesenate. Acest lucru poate fi foarte eficient, deoarece nu este necesar să se calculeze culorile pentru piesele care sunt îndepărtate și ascunse de obiecte din apropiere. Cu toate acestea, algoritmul invers suferă de aceleași probleme ca și versiunea obișnuită.
Acest lucru și alte defecte ale algoritmului au condus la dezvoltarea tehnicii tamponului Z , care poate fi văzută ca o dezvoltare a algoritmului pictorului care rezolvă conflictele de adâncime, eliminând necesitatea unei ordonări de redare bazate pe adâncime.
Notă
- ^ (2008) Partiții spațiale binare. În: Geometrie computațională. Springer, Berlin, Heidelberg , capitolul 12, p 259. ISBN 9783540779742
- ^ (2008) Partiții spațiale binare. În: Geometrie computațională. Springer, Berlin, Heidelberg , capitolul 12, p 260. ISBN 9783540779742
- ^ (2004) Dezvoltarea jocurilor în Java . În: New Riders Games Series. Brackeen, D., Barker, B., Vanhelsuwé, L. New Riders. , p. 485. ISBN 9781592730056
Alte proiecte
-
Wikimedia Commons conține imagini sau alte fișiere pe algoritmul pictorului
