Algorytm Warnocka
Algorytm Warnocka to metoda oparta na zasadzie dziel i zwyciężaj służąca do eliminacji niewidocznych powierzchni, stosowana w dziedzinie grafiki komputerowej. Jego twórcą jest John Edward Warnock, który szczegółowo opisał ten algorytm w swojej pracy doktorskiej zatytułowanej „A hidden surface algorithm for computer generated halftone pictures” (1969).
Złożoność obliczeniowa algorytmu wynosi:
O(n ⋅ p), gdzie:
- n oznacza liczbę rasteryzowanych wielokątów,
- p to liczba pikseli w obszarze renderowania.
Opis działania
Algorytm zaczyna od podziału obszaru renderowania na kwadraty; początkowo mamy jeden kwadrat obejmujący cały obszar rysowania. Każdy kwadrat jest klasyfikowany na podstawie położenia wielokątów:
- Jeżeli żaden wielokąt nie pokrywa się z kwadratem (jak w przypadku d na poniższym rysunku), kwadrat jest wypełniany kolorem tła.
- W przypadku, gdy w kwadracie znajduje się tylko jeden wielokąt w całości lub częściowo (przypadki b, c), kwadrat również jest wypełniany kolorem tła, a następnie rasteryzowana jest widoczna część wielokąta.
- Kiedy mamy jeden wielokąt otaczający (przypadek a), rasteryzowana jest jego część znajdująca się w kwadracie.
- Jeśli występuje jeden wielokąt otaczający oraz wiele wielokątów zawartych w całości lub częściowo, a wielokąt otaczający znajduje się przed innymi (zakrywa je), wtedy jest on rasteryzowany jak w punkcie 3. W przeciwnym razie, kwadrat jest przetwarzany dalej.
- Jeżeli żadne z powyższych reguł nie może być zastosowane do kwadratu, następuje jego podział na cztery mniejsze kwadraty, które są przetwarzane rekurencyjnie.
Podział kwadratów kończy się, gdy osiągną one rozmiar jednego piksela; kolor piksela ustala się na przykład poprzez sortowanie wielokątów według głębokości. Możliwe jest także kontynuowanie podziału do kwadratów o bokach krótszych niż piksel, co umożliwia uzyskanie obrazów o wysokiej jakości bez zniekształceń.
Zobacz też
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.
