home *** CD-ROM | disk | FTP | other *** search
/ Amiga MA Magazine 1997 #3 / amigamamagazinepolishissue03-1 / ma_1995 / 12 / ami035.txt < prev    next >
Text File  |  1997-04-07  |  6KB  |  137 lines
  1.  
  2. ***** 3 rysunki (na Amidze) *************
  3.  
  4.  
  5.  
  6. Jak ulepszyê procedurë? (odc. 14.)
  7. ----------------------------------
  8.  
  9. ALGORYTMY WYZNACZANIA WIDOCZNYCH CZËÔCI POWIERZCHNI
  10.  
  11. <lead>Standardowe metody, uûywane kiedyô w demach (wektory
  12. punktowe i "druciaki"), mogâ sîuûyê jedynie do tworzenia obrazów
  13. zbiorów punktów, poddanych uprzednio pewnym transformacjom i
  14. rzutowanych na pîaszczyznë w ukîadzie obserwatora. Punkty
  15. poîâczone w odpowiednie struktury definiujâ równoczeônie
  16. wierzchoîki, krawëdzie i ôciany obiektów trójwymiarowych.
  17.  
  18. <a>Miklesz/Damage
  19.  
  20. <txt>Wizualizacja tych obiektów na ekranie monitora moûe byê
  21. sprowadzona do wyôwietlenia odpowiedniej liczby linii,
  22. przedstawiajâcych krawëdzie bryî, które znajdujâ sië w obrëbie
  23. ostrosîupa widzenia. Uzyskujemy w ten sposób obraz "druciany",
  24. nieczytelny, gdyû jest na nim zbyt wiele figur (rys. 1.). Aby
  25. obraz byî czytelny, naleûy usunâê zasîoniëte krawëdzie (rys. 2.).
  26. Moûna takûe pokazywaê tylko widoczne czëôci ôcian i odpowiednio
  27. je oôwietlaê (rys. 3.). Tym razem przykîad pochodzi akurat z
  28. programu Imagine.
  29.  
  30. <sr>Prolog
  31.  
  32. <txt>Wyszukiwanie i selekcja widocznych fragmentów krawëdzi ma
  33. bardzo duûe zastosowanie, kiedy zamierzamy nasz obraz wydrukowaê
  34. (na przykîad na ploterze, drukarce czy naôwietlarce). Kiedy
  35. jednak potrzebujemy osiâgnâê efektownie obracajâcâ sië bryîë w
  36. naszym demie lub grze, zdecydowanie lepiej zastosowaê algorytm,
  37. sîuûâcy do znajdowania widocznych czëôci powierzchni. W którymô z
  38. póúniejszych odcinków omówië jeden z ciekawszych i wydajniejszych
  39. algorytmów tego typu, jakim jest scanline. Pomysî opiera sië na
  40. przeglâdaniu obrazu liniami poziomymi. Idea tego algorytmu
  41. zostaîa wziëta z ksiâûki Michaîa Jankowskiego: "Elementy grafiki
  42. komputerowej." WNT, 1990). Dzisiaj natomiast przeprowadzë krótki
  43. wstëp do algorytmów wyznaczania widocznych czëôci powierzchni,
  44. omawiajâc niektóre z nich.
  45.  
  46. Zaczâê naleûy przede wszystkim od podziaîu algorytmów
  47. wizualizacji obiektów na dwa rodzaje:
  48.  
  49. -- metody przestrzeni obrazu;
  50.  
  51. -- metody przestrzeni danych;
  52.  
  53. Okazuje sië, ûe kaûdy z typów algorytmów ma swoje zalety i wady,
  54. tak wiëc nie istnieje rozwiâzanie idealne.
  55.  
  56. Najpierw omówië metodë, operujâcâ na danych. Charakteryzuje sië
  57. ona tym, ûe wszelkie obliczenia, dotyczâce widocznoôci ôcian i
  58. krawëdzi, dokonywane sâ jeszcze przed ich narysowaniem. Zaletami
  59. tego typu algorytmów sâ: bardzo dokîadne i îatwe do interpretacji
  60. wyniki dziaîania. W praktyce oznacza to, ûe otrzymujemy
  61. wspóîrzëdne wszystkich widocznych krawëdzi, które wystarczy
  62. poîâczyê w ôciany i narysowaê. Wady metod, opierajâcych sië na
  63. przestrzeni danych, to dîugi czas dziaîania i duûa
  64. pamiëcioûernoôê.
  65.  
  66. Druga grupa algorytmów (opierajâcych sië na przestrzeni obrazu),
  67. przede wszystkim nie daje juû w wyniku dziaîania danych
  68. trójwymiarowych, a jedynie dwuwymiarowe. Jednakûe na podstawie
  69. otrzymanych danych moûemy bez problemu stwierdziê, która ôciana
  70. (lub czëôê ôciany) znajduje sië bliûej nas i w zwiâzku z tym
  71. powinna byê narysowana. Oczywiôcie rozstrzyganie "bliskoôci"
  72. punktów wymaga dodatkowej tablicy, zawierajâcej dane osi Z. Jak
  73. zapewne îatwo zauwaûyê, ta wîaônie grupa algorytmów lepiej nadaje
  74. sië do tworzenia szybkiej grafiki trójwymiarowej w demach i
  75. dlatego teû na niej sië skoncentrujë.
  76.  
  77. Warto zwróciê uwagë na jeszcze jednâ ciekawâ zaleûnoôê. O ile w
  78. wypadku algorytmów, operujâcych na danych, prëdkoôê ich dziaîania
  79. oraz pamiëcioûernoôê zaleûâ w duûej mierze od liczby punktów,
  80. krawëdzi i ôcian obiektu wyôwietlanego na ekranie, o tyle druga
  81. grupa algorytmów uzaleûniona jest raczej od liczby punktów
  82. graficznych generowanego obrazu. Tak czy siak, po tym wstëpie
  83. pora, abym przeszedî do konkretnych przykîadów i przedstawiî
  84. kilka metod wyznaczania widocznoôci ôcian (lub jedynie niektórych
  85. ich fragmentów).
  86.  
  87. Najstarszym i najprostszym algorytmem jest sortowanie ôcian
  88. wedîug uôrednionych ze wszystkich wierzchoîków danej ôciany
  89. odlegîoôci od obserwatora w osi Z. Teraz pozostaje nam jedynie
  90. narysowanie powierzchni, poczynajâc od najdalszej, a koïczâc na
  91. najbliûszej. Kaûdâ ôcianë moûemy oczywiôcie przy okazji rysowaê w
  92. jakimô zdefiniowanym kolorze. W ten sposób powierzchnie bliûsze
  93. bëdâ kolejno, warstwowo przykrywaê te dalsze. Niestety, wadâ tej
  94. metody jest niemoûnoôê rysowania przecinajâcych sië oraz
  95. niewypukîych ôcian. Kiedy nadchodzi potrzeba narysowania takiej
  96. powierzchni, algorytm kompletnie zawodzi.
  97.  
  98. Trochë bardziej skomplikowanym sposobem jest uûycie metody "dziel
  99. i zwyciëûaj". Polega ona na rekurencyjnym dzieleniu widocznego
  100. ekranu na coraz mniejsze prostokâty. Czynimy to tak dîugo, aû
  101. uzyskamy fragment jednej ôciany w badanym prostokâcie lub badany
  102. obszar zacznie zajmowaê powierzchnië jednego piksela (dalsze
  103. podziaîy w tym momencie juû tracâ sens). Naleûy pamiëtaê o tym,
  104. ûe kiedy napotykamy na prostokât, na którego powierzchni znajdujâ
  105. sië fragmenty dwóch ôcian, musimy go podzieliê na cztery
  106. identyczne mniejsze czëôci i detekcjë przeprowadzaê dalej. Zaletâ
  107. podanej tu przeze mnie metody jest szybkoôê dziaîania. Problem
  108. widocznoôci rozstrzygany jest tylko tam, gdzie generowany przez
  109. nas obraz naprawdë tego wymaga.
  110.  
  111. Kolejnym algorytmem, jaki chciaîbym przedstawiê, jest tak zwany
  112. Z-Buffer. Metoda polega na stworzeniu dodatkowej tablicy, o
  113. rozmiarach szerokoôê ekranu x wysokoôê ekranu. Podczas rysowania
  114. ôcian dla kaûdego piksela, naleûâcego do rzutu kaûdej ôciany
  115. znajdujâcej sië na scenie, obliczamy odlegîoôê trójwymiarowego
  116. przeciwobrazu tego piksela od obserwatora. Obliczonâ wartoôê
  117. zapisujemy do tablicy-bufora gîëbokoôci w wierszu i kolumnie,
  118. odpowiadajâcych poîoûeniu tego piksela na ekranie. Zapis jest
  119. wykonywany wyîâcznie wtedy, gdy zapisywana wartoôê jest mniejsza
  120. od zawartoôci tablicy. Jeûeli jest speîniony ten warunek, to do
  121. tablicy kolorów zapisujemy kolor ôciany, do której naleûy dany
  122. punkt. Tablica gîëbokoôci powinna byê na poczâtku zainicjowana
  123. maksymalnie duûymi liczbami, a tablica kolorów -- kolorem tîa. Po
  124. wykonaniu tych operacji dla wszystkich rzutów ôcian tablica
  125. kolorów moûe byê, punkt po punkcie, wyôwietlona na ekranie
  126. komputera -- w niej mieôci sië obraz sceny.
  127.  
  128. Wiëcej o Z-Bufferze i innych algorytmach wyznaczania widocznych
  129. czëôci powierzchni napiszë za miesiâc.
  130.  
  131. <przyp>Literatura:
  132.  
  133. Marek Domaradzki, Robert Gembara: "Tworzenie realistycznej
  134. grafiki 3D." Lynx-SFT, 1993.
  135.  
  136. Michaî Jankowski: "Elementy grafiki komputerowej." WNT, 1990.
  137.