Podręcznik Grafika komputerowa i wizualizacja

Algorytm bufora głębokości (Z-bufora) został zaproponowany przez Catmulla w 1974 roku. Jest jednym z najprostszych w implementacji algorytmów rozstrzygania widoczności. Zakłada istnienie bufora o rozmiarze całego wyświetlanego obszaru (ekranu) – występuje w tym przypadku odpowiedniość pozycji piksela ekranu i odpowiadającej mu pozycji w buforze. Dla każdego piksela w buforze zapamiętywana jest odpowiadająca mu głębokość czyli współrzędna z_P.

Na początku pracy algorytmu bufor Z jest wypełniany maksymalną wartością współrzędnej z, jaka może wystąpić w analizowanym obszarze. Jednocześnie wszystkie piksele obrazu przyjmują barwę tła. Następnie rysowane są wielokąty (w dowolnej kolejności) – to znaczy wypełniane są ich rzuty odpowiednią barwą. Podczas wypełniania zwykła procedura wypełniająca jest poszerzona o sprawdzenie głębokości odpowiadającej danemu pikselowi. Piksel jest wypełniony tylko wtedy, kiedy jego z jest mniejsze niż wartość zapisana w buforze – rysunek 9.14.

Mechanizm ten powoduje, że podczas wypełniania kolejnych wielokątów szukany jest piksel, którego współrzędna z jest najmniejsza – to znaczy szukany jest punkt leżący najbliżej obserwatora – czyli punkt rzeczywiście widoczny.

 

Algorytm eliminacji elementów zasłoniętych z wykorzystaniem bufora głębokości można zapisać następująco:

 

ALGORYTM_BUFORA_GŁEBOKOŚCI

1. zdefiniuj bufor Z, który dla każdego piksela (x_P,y_P) ekranu zapamiętuje głębokość z_P ;

2. rysuj kolejne wielokąty poprzez wypełnianie ich rzutów pikselami

     o odpowiedniej barwie;

    w przypadku każdego piksela weź pod uwagę wartość z bufora :

3. jeżeli nowa wartość z > z_P to nie wypełniaj piksela.

    w przeciwnym przypadku wypełnij piksel i uaktualnij  z_P ;

 

Obliczenie głębokości danego punktu wielokąta może zostać przeprowadzone jako interpolacja bilingowa, zgodnie z rysunkiem 9.15.

                Rys. 9.15. Obliczanie głębokości punktu (współrzędnej z)

                w algorytmie bufora głębokości.

 

Algorytm bufora głębokości rozstrzyga widoczność dla dowolnych scen wielościennych, jest niewrażliwy na zasłanianie cykliczne ani przecinanie obiektów. Nie wymaga żadnych dodatkowych struktur danych ani operacji wstępnych. Nie jest potrzebne żadne wstępne sortowanie wielokątów, ani żadne porównywanie obiekt-obiekt czy ściana-ściana! Dodatkowo, biorąc pod uwagę fakt, że wielokąty są obiektami płaskimi można wyznaczyć proste zależności przyrostowe wiążąc kolejne zmiany współrzędnych z wypełnianiem wielokąta liniami. Powoduje to, że dodatkowy czas potrzebny na rozszerzenie algorytmu wypełniania o rozstrzyganie widoczności jest niewielki. Przyjmuje się, że jest to algorytm o złożoności liniowej ze względu na liczbę wielokątów, ale dla ich dużej liczby czas rozstrzygania widoczności staje się w przybliżeniu praktycznie niezależny od liczby wielokątów w danej bryle widzenia.

 

Algorytm ma tylko jedną wadę – potrzebuje pamięci o rozmiarze obrazu, pozwalającej zapisać odległość dla każdego piksela. Jeszcze do niedawna (koniec dwudziestego wieku) był to warunek trudny do spełnienia. Realizacja algorytmu wymagała dodatkowo wykonania podziału obrazu na fragmenty, które mogły być razem z odpowiadającym mu buforem zmieszczone do pamięci. Dzisiaj nie stanowi to żadnego problemu.

Prostota algorytmu sprzyja również implementacji sprzętowej. Stacje graficzne i większość dobrych kart graficznych ma dzisiaj możliwość sprzętowej realizacji bufora głębokości.

 

Podstawowe właściwości algorytmu bufora głębokości można scharakteryzować w następujący sposób:

 

• Zalety
  • Bardzo prosty !!! Pracuje w każdych warunkach !!!
  • Łatwy do implementacji sprzętowej.
    Algorytm  Z-Buffer jest bardzo często realizowany przez sprzęt kart graficznych !!!
  • Pozwala przetwarzać wielokąty w dowolnej kolejności. Złożoność O(n), gdzie n — liczba wielokątów.
  • Nie jest potrzebne żadne wstępne sortowanie wielokątów, ani żadne porównywanie obiekt-obiekt
    czy ściana-ściana !!!
  • Rozwiązuje zasłanianie cykliczne, przenikanie obiektów i inne problemy geometryczne.
  • Może być efektywnie wykorzystany także w cieniowaniu.
• Wady
  • Wymaga dużej ilości pamięci
  • Wymaga szybkiej pamięci (typowa pętla to odczyt, modyfikacja, zapis).
  • Trudno uwzględnić (równie efektywnie) antyaliasing.
  • Trudna realizacja przezroczystości.