Algorytm Warnocka

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Algorytm Warnockaalgorytm dziel i zwyciężaj usuwania powierzchni niewidocznych, używany w polu grafiki komputerowej. Autorem jest John Edward Warnock, który zawarł opis w pracy doktorskiej pt. A hidden surface algorithm for computer generated halftone pictures (1969).

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

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
Przykładowy podział obszaru renderowania dla prostej sceny

Algorytm dzieli pole renderowania na kwadraty; początkowo jest jeden kwadrat obejmujący cały obszar rysowania. 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 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 p. 3. W przeciwnym razie kwadrat jest przetwarzany dalej.

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ń.

Bibliografia[edytuj | edytuj kod]

  • 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.

Zobacz też[edytuj | edytuj kod]