Algorytm Warnocka

Algorytm Warnocka – algorytm dziel i zwyciężaj usuwania powierzchni niewidocznych, używany w dziedzinie grafiki komputerowej. Jego autorem jest John Edward Warnock, który zawarł opis algorytmu w swojej pracy doktorskiej pt. „A hidden surface algorithm for computer generated halftone pictures” (1969).

Złożoność obliczeniowa algorytmu wynosi ${\displaystyle \mathrm {O} (n\cdot p),}$ gdzie ${\displaystyle n}$ to liczba rasteryzowanych wielokątów, a ${\displaystyle p}$ to liczba pikseli w polu renderowania.

Opis działania

Przykładowy podział obszaru renderowania dla prostej sceny

Algorytm dzieli pole renderowania na kwadraty; początkowo jest tylko jeden kwadrat obejmujący cały obszar rysowania. Każdy kwadrat jest klasyfikowany ze względu na położenie wielokątów:

1. Gdy żaden wielokąt nie ma części wspólnej z kwadratem (na rysunku poniżej przypadek d), wówczas jest on wypełniany kolorem tła.
2. Gdy jest tylko jeden wielokąt w całości bądź częściowo widoczny (przypadki b, c), wówczas kwadrat jest wypełniany kolorem tła, następnie część wielokąta zawarta w kwadracie jest rasteryzowana.
3. Gdy jest tylko jeden wielokąt otaczający (przypadek a), rasteryzowana jest jego część zawarta w kwadracie.
4. Gdy jest jeden wielokąt otaczający i wiele wielokątów zawartych w całości lub częściowo, oraz w rozważanym kwadracie wielokąt otaczający znajduje się przed pozostałymi wielokątami (zasłania je), wówczas jest rasteryzowany jak w pkt. 3. W przeciwnym razie kwadrat jest przetwarzany dalej.

Rozpatrywane położenia pojedynczego wielokąta względem kwadratu. a) wielokąt otaczający, b) wielokąt częściowo widoczny, c) wielokąt widoczny w całości, d) wielokąt niewidoczny

Jeśli nie można zastosować żadnej z powyższych reguł w którymś kwadracie, dokonywany jest podział na cztery mniejsze kwadraty i są one przetwarzane rekurencyjnie.

Podział kwadratów jest kończony, gdy mają rozmiar jednego piksela, wówczas kolor piksela określa się np. sortując wielokąty ze względu na głębokość. Podział może być też kontynuowany dalej do kwadratów o bokach krótszych niż piksel, co pozwala uzyskać obrazy bez zakłóceń.

Zobacz też

• algorytm malarza
• bufor Z
• drzewo czwórkowe
• drzewo ósemkowe

Bibliografia

• Algorytmy podziału powierzchni. W: James D Foley, Andries van Dam, Steven K Freiner, John F Hughes, Richard L Phillips: Wprowadzenie do grafiki komputerowej. Jan Zabrodzki (tłumaczenie). Warszawa: Wydawnictwa Naukowo-Techniczne, 1995, s. 579–582. ISBN 83-204-1840-2.