***** 3 rysunki (na Amidze) ************* Jak ulepszyê procedurë? (odc. 14.) ---------------------------------- ALGORYTMY WYZNACZANIA WIDOCZNYCH CZËÔCI POWIERZCHNI Standardowe metody, uûywane kiedyô w demach (wektory punktowe i "druciaki"), mogâ sîuûyê jedynie do tworzenia obrazów zbiorów punktów, poddanych uprzednio pewnym transformacjom i rzutowanych na pîaszczyznë w ukîadzie obserwatora. Punkty poîâczone w odpowiednie struktury definiujâ równoczeônie wierzchoîki, krawëdzie i ôciany obiektów trójwymiarowych. Miklesz/Damage Wizualizacja tych obiektów na ekranie monitora moûe byê sprowadzona do wyôwietlenia odpowiedniej liczby linii, przedstawiajâcych krawëdzie bryî, które znajdujâ sië w obrëbie ostrosîupa widzenia. Uzyskujemy w ten sposób obraz "druciany", nieczytelny, gdyû jest na nim zbyt wiele figur (rys. 1.). Aby obraz byî czytelny, naleûy usunâê zasîoniëte krawëdzie (rys. 2.). Moûna takûe pokazywaê tylko widoczne czëôci ôcian i odpowiednio je oôwietlaê (rys. 3.). Tym razem przykîad pochodzi akurat z programu Imagine. Prolog Wyszukiwanie i selekcja widocznych fragmentów krawëdzi ma bardzo duûe zastosowanie, kiedy zamierzamy nasz obraz wydrukowaê (na przykîad na ploterze, drukarce czy naôwietlarce). Kiedy jednak potrzebujemy osiâgnâê efektownie obracajâcâ sië bryîë w naszym demie lub grze, zdecydowanie lepiej zastosowaê algorytm, sîuûâcy do znajdowania widocznych czëôci powierzchni. W którymô z póúniejszych odcinków omówië jeden z ciekawszych i wydajniejszych algorytmów tego typu, jakim jest scanline. Pomysî opiera sië na przeglâdaniu obrazu liniami poziomymi. Idea tego algorytmu zostaîa wziëta z ksiâûki Michaîa Jankowskiego: "Elementy grafiki komputerowej." WNT, 1990). Dzisiaj natomiast przeprowadzë krótki wstëp do algorytmów wyznaczania widocznych czëôci powierzchni, omawiajâc niektóre z nich. Zaczâê naleûy przede wszystkim od podziaîu algorytmów wizualizacji obiektów na dwa rodzaje: -- metody przestrzeni obrazu; -- metody przestrzeni danych; Okazuje sië, ûe kaûdy z typów algorytmów ma swoje zalety i wady, tak wiëc nie istnieje rozwiâzanie idealne. Najpierw omówië metodë, operujâcâ na danych. Charakteryzuje sië ona tym, ûe wszelkie obliczenia, dotyczâce widocznoôci ôcian i krawëdzi, dokonywane sâ jeszcze przed ich narysowaniem. Zaletami tego typu algorytmów sâ: bardzo dokîadne i îatwe do interpretacji wyniki dziaîania. W praktyce oznacza to, ûe otrzymujemy wspóîrzëdne wszystkich widocznych krawëdzi, które wystarczy poîâczyê w ôciany i narysowaê. Wady metod, opierajâcych sië na przestrzeni danych, to dîugi czas dziaîania i duûa pamiëcioûernoôê. Druga grupa algorytmów (opierajâcych sië na przestrzeni obrazu), przede wszystkim nie daje juû w wyniku dziaîania danych trójwymiarowych, a jedynie dwuwymiarowe. Jednakûe na podstawie otrzymanych danych moûemy bez problemu stwierdziê, która ôciana (lub czëôê ôciany) znajduje sië bliûej nas i w zwiâzku z tym powinna byê narysowana. Oczywiôcie rozstrzyganie "bliskoôci" punktów wymaga dodatkowej tablicy, zawierajâcej dane osi Z. Jak zapewne îatwo zauwaûyê, ta wîaônie grupa algorytmów lepiej nadaje sië do tworzenia szybkiej grafiki trójwymiarowej w demach i dlatego teû na niej sië skoncentrujë. Warto zwróciê uwagë na jeszcze jednâ ciekawâ zaleûnoôê. O ile w wypadku algorytmów, operujâcych na danych, prëdkoôê ich dziaîania oraz pamiëcioûernoôê zaleûâ w duûej mierze od liczby punktów, krawëdzi i ôcian obiektu wyôwietlanego na ekranie, o tyle druga grupa algorytmów uzaleûniona jest raczej od liczby punktów graficznych generowanego obrazu. Tak czy siak, po tym wstëpie pora, abym przeszedî do konkretnych przykîadów i przedstawiî kilka metod wyznaczania widocznoôci ôcian (lub jedynie niektórych ich fragmentów). Najstarszym i najprostszym algorytmem jest sortowanie ôcian wedîug uôrednionych ze wszystkich wierzchoîków danej ôciany odlegîoôci od obserwatora w osi Z. Teraz pozostaje nam jedynie narysowanie powierzchni, poczynajâc od najdalszej, a koïczâc na najbliûszej. Kaûdâ ôcianë moûemy oczywiôcie przy okazji rysowaê w jakimô zdefiniowanym kolorze. W ten sposób powierzchnie bliûsze bëdâ kolejno, warstwowo przykrywaê te dalsze. Niestety, wadâ tej metody jest niemoûnoôê rysowania przecinajâcych sië oraz niewypukîych ôcian. Kiedy nadchodzi potrzeba narysowania takiej powierzchni, algorytm kompletnie zawodzi. Trochë bardziej skomplikowanym sposobem jest uûycie metody "dziel i zwyciëûaj". Polega ona na rekurencyjnym dzieleniu widocznego ekranu na coraz mniejsze prostokâty. Czynimy to tak dîugo, aû uzyskamy fragment jednej ôciany w badanym prostokâcie lub badany obszar zacznie zajmowaê powierzchnië jednego piksela (dalsze podziaîy w tym momencie juû tracâ sens). Naleûy pamiëtaê o tym, ûe kiedy napotykamy na prostokât, na którego powierzchni znajdujâ sië fragmenty dwóch ôcian, musimy go podzieliê na cztery identyczne mniejsze czëôci i detekcjë przeprowadzaê dalej. Zaletâ podanej tu przeze mnie metody jest szybkoôê dziaîania. Problem widocznoôci rozstrzygany jest tylko tam, gdzie generowany przez nas obraz naprawdë tego wymaga. Kolejnym algorytmem, jaki chciaîbym przedstawiê, jest tak zwany Z-Buffer. Metoda polega na stworzeniu dodatkowej tablicy, o rozmiarach szerokoôê ekranu x wysokoôê ekranu. Podczas rysowania ôcian dla kaûdego piksela, naleûâcego do rzutu kaûdej ôciany znajdujâcej sië na scenie, obliczamy odlegîoôê trójwymiarowego przeciwobrazu tego piksela od obserwatora. Obliczonâ wartoôê zapisujemy do tablicy-bufora gîëbokoôci w wierszu i kolumnie, odpowiadajâcych poîoûeniu tego piksela na ekranie. Zapis jest wykonywany wyîâcznie wtedy, gdy zapisywana wartoôê jest mniejsza od zawartoôci tablicy. Jeûeli jest speîniony ten warunek, to do tablicy kolorów zapisujemy kolor ôciany, do której naleûy dany punkt. Tablica gîëbokoôci powinna byê na poczâtku zainicjowana maksymalnie duûymi liczbami, a tablica kolorów -- kolorem tîa. Po wykonaniu tych operacji dla wszystkich rzutów ôcian tablica kolorów moûe byê, punkt po punkcie, wyôwietlona na ekranie komputera -- w niej mieôci sië obraz sceny. Wiëcej o Z-Bufferze i innych algorytmach wyznaczania widocznych czëôci powierzchni napiszë za miesiâc. Literatura: Marek Domaradzki, Robert Gembara: "Tworzenie realistycznej grafiki 3D." Lynx-SFT, 1993. Michaî Jankowski: "Elementy grafiki komputerowej." WNT, 1990.