Algoritmul lui Warnock

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare
Vizibilitatea poligoanelor într-o fereastră dată: a) poligonul umple fereastra, b) parțial, c) complet vizibil, d) poligon invizibil.
Patru pași către o împărțire a unei ferestre de vedere printr-o scenă simplă

Algoritmul Warnock este un algoritm pentru determinarea suprafeței ascunse inventat de John Warnock care este de obicei utilizat în domeniul graficii computerizate . [1] Rezolvă problema redării imaginilor complicate, printr-o subdiviziune recursivă a unei scene, care duce la arii care sunt banale de calculat. Cu alte cuvinte, dacă scena este suficient de simplă pentru a calcula eficient, aceasta este redată; altfel este împărțit în părți mai mici. [2]

Acesta este un algoritm de divizare și cucerire cu durata de execuție a , unde este este numărul de poligoane și este numărul de pixeli din fereastra de vizualizare.

Intrările sunt o listă de poligoane și o fereastră de vizualizare. Cel mai bun caz este că, dacă lista poligonelor este simplă, atunci poligoanele sunt desenate în fereastra de vizualizare. Prin „simplu” înțelegem dacă există un poligon (deci poligonul sau părțile sale sunt desenate într-o parte corespunzătoare a ferestrei) sau dacă o fereastră cu o dimensiune de un pixel (astfel încât pixelul obține o culoare a celui mai apropiat poligon către observator). Următorul pas este să împărțiți fereastra de vizualizare în patru cadrane de dimensiuni egale și să apelați recursiv algoritmul pentru fiecare cadran, cu o listă modificată de poligoane, pentru a conține doar poligoane vizibile în acel cadran.

Notă

Elemente conexe

linkuri externe