4. Usuwanie punktów i ścian niewidocznych

4.2. Algorytm z z-buforem

Algorytm z z-buforem, nazywany też często buforem głębokości (ang. depth buffer), opracowany przez Catmulla, jest najprostszym algorytmem usuwania punktów niewidocznych, toteż jest powszechnie stosowany w realizacji sprzętowej (i również bardzo prosty w implementacji programowej). Może być używany do renderingu dowolnego obiektu, jeżeli dla każdego punktu rzutu można obliczyć barwę i wartość z. Algorytm z z-buforem nie wymaga, aby obiekty były wielokątami.

Algorytm z z-buforem wymaga korzystania obok pamięci obrazu z z-bufora, czyli tablicy o takiej samej liczbie pozycji, jak pamięc obrazu; w z-buforze pamiętana jest wartość z dla każdego piksela.

W fazie początkowej z-bufor jest wypełniany minimalną głębokością, co odpowiada zapamiętaniu wartości z dla tylnej ściany obcinającej scenę, czyli dla najdalej od obserwatora połozonego elementu sceny, a do bufora obrazu jest wpisywana barwa tła. Największa wartość, jaka może być wpisana w z-buforze, reprezentuje z dla przedniej ściany obcinającej. Obiekty są przeglądane punkt po punkcie, np. wielokąty są przeglądane wierszami, powierzchnie są przeglądane wzdłuż linii stałego parametru. Kolejność przeglądania obiektów, wielokątów jest dowolna. Jeżeli rozpatrywany punkt (x, y) nie leży dalej od obserwatora niż punkt, którego barwa i głębokość są zapisane w buforach, to nowa barwa i głębokość zastępują stare wartości.

 

Rysunek 31. Zasada działania z-bufora; wszystkie punkty zaznaczone na czerwono zamalowują ten sam piksel ekranu.

 

W pamięci obrazu i w z-buforze są zapisywane informacje związane z największą wartością z napotkaną dotychczas dla każdego (x, y). Dlatego obiekty (wielokąty) pojawiają się na ekranie w kolejności, w jakiej są przetwarzane.

Warto podkreślić, że jeśli przyjmiemy inny niż przyjęty na Rys. 31 układ współrzędnych, w którym oś z będzie skierowana w głąb ekranu, wówczas należy odpowiednio zmodyfikować algorytm: z- bufor wypełnić największą możliwą wartością z i relację "większy niż " zamienić na relację "mniejszy niż".

 

Prześledźmy działanie z-bufora na poniższym rysunku, przy założeniu, że przetwarzane obiekty są trójkątami. W górnej części rysunku z lewej strony mamy pusty z-bufor. Pośrodku znajduje się tablica z określonymi wartościami z trójkąta. Po prawej stronie otrzymamy z-bufor po przeprowadzeniu operacji dodania trójkąta do z-bufora. W dolnej części z lewej strony mamy wynikowy z-bufor z górnej części. Pośrodku tablica z określonymi wartościami z drugiego trójkąta. Po prawej stronie mamy wynik dodania go do z-bufora:

 

Rysunek 32. Zasada działania z-bufora na przykładzie dwóch trójkątów

Jeżeli przetwarzamy wielokąty, to można uprościć obliczanie z dla każdego punktu w przeglądanym wierszu korzystając z faktu, że wielokąt jest płaski. Zazwyczaj w celu obliczenia z powinniśmy rozwiązać równanie płaszczyzny:

Ax+By+Cz+D=0

dla zmiennej z ma postać

 

z=\frac{-D-Ax-Bz}{C}

 

Jeżeli w punkcie (x, y) z powyższego równania otrzymamy z1, to w punkcie 

(x +∆ xz)

wartość z wynosi

z_1-\frac{A}{C}(∆x)

W przypadku, gdy znamy z(x, y), to do obliczenia

 z(+ 1, y)

będziemy musieli wykonać tylko jedno odejmowanie, ponieważ iloraz  

\frac{A}{C}=const\ \ \ \ \ i\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ∆x=1

W celu obliczenia pierwszej wartości z w następnym przeglądanym wierszu należy wykonać podobne obliczenie przyrostowe, zmniejszając z o 

   \frac{B}{C}

dla każdego

 

 

 

W przypadku, gdy płaszczyzna nie została określona, albo gdy wielokąt nie jest płaski, to wówczas z(x, y) można określić interpolując współrzędne z wierzchołków wielokąta wzdłuż par krawędzi, a potem wzdłuż każdego przeglądanego wiersza.

Rysunek 33.. Interpolacja wartości z wzdłuż krawędzi wielokąta i wierszy przeglądania.

W powyższej sytuacji za jest interpolowane między z1 i z2, zb między z1 i z3 a zp między za i zb.

Poszczególne punkty wyznaczymy z poniższych zależności:

 

z_a=z_1-\left(z_1-z_2\right)\frac{y_1-y_s}{y_1-y_2}

z_b=z_1-(z_1-z_3)\frac{y_1-y_s}{y_1-y_3}

z_p=z_b-(z_b-z_a)\frac{x_b-x_p}{x_b-x_a}

 

Możemy tu także wykorzystać obliczenia przyrostowe. Zauważmy, że barwa piksela nie musi być obliczana, jeżeli warunkowe określanie widoczności piksela nie jest spełnione. Zatem jeżeli obliczenia związane z cieniowaniem są czasochłonne, można zwiększyć efektywność wykonując zgrubne sortowanie obiektów. Sortowanie pozwoli posegregować je według kryterium od najbliższego do najdalszego, a następnie będzie można najpierw wyświetlać najbliższe obiekty. Czas zajmowany przez obliczenia z użyciem z-bufora jest w przybliżeniu niezależny od liczby wielokątów w obiektach. Dzieje się tak, ponieważ średnio liczba pikseli pokrytych przez każdy wielokąt zmniejsza się wraz ze wzrostem liczby wielokątów w bryle widzenia.

 

Na zakończenie pouczająca aplikacja (Rysunek 34), która pokazuje efekty wyświetlania obiektów z z-buforem i bez:

 

Rysunek 34 - Aplikacja nr 4 ilustrująca efekty działania algorytmu z z-buforem.
Efekty 3D zobaczymy po włączeniu oświetlenia i przemieszczeniu obiektów.