![]() | ||||||||||||||||||||||||||||||||||||||||||||||
O wypełnianiu i wypełniankach | ||||||||||||||||||||||||||||||||||||||||||||||
![]() | ||||||||||||||||||||||||||||||||||||||||||||||
Poniższy tekst swą formą nawiązuje do artykułu mojego autorstwa, który został zamieszczony w CA Zine 1. Jak jego poprzednik jest adresowany do średniozaawansowanych koderów. Artykuł ten traktuje o wszelkich problemach związanych z wypełnianiem zamkniętych płaszczyzn na ekranie oraz z rysowaniem obiektów złożonych. Na marginesie tych rozważań poruszonych jest wiele kwestii, które dla wielu mogą być bardziej interesujące od głównego tematu tego artykułu. 1. Metody wypełniania Jak doskonale wiemy, zamknięte obszary na ekranie możemy w Basicu wypełniać przy pomocy funkcji XIO. Jej działanie pozostawaia wiele do życzenia. Dzieje się tak przede wszystkim z powodu algorytmu, na podstawie którego funkcjonuje. Za pomocą funkcji XIO możemy wypełnić dowolną zamkniętą płaszczyznę. Płaszczyzna może mieć dowolny kształt, choćby dziesięcioramiennej gwiazdy. Wypełnianie rozpoczyna się od wskazanego punktu, a kończy się, gdy wszystkie sąsiednie punkty o tej samej barwie zostały zapełnione. Taki algorytm jest bardzo powolny, ale za to bardzo uniwersalny.
Omawiane przeze mnie metody nie są w tym stopniu doskonałe, ale za to są bardzo szybkie. Ich podstawowym wyróżnikiem jest to, że można przy ich pomocy wypełniać jedynie takie figury, które w jednej linii horyzontalnej są w jednym kawałku.
2. Metoda blitterowa Jej nazwa pochodzi od nazwy pewnego amigowskiego scalaka, którego zadaniem między innymi jest wypełnianie płaszczyzn na bitplanach.
Oto krótki opis sposbu pracy blittera. Zrozumienie zasad jego pracy umożliwi zrozumienie działania algorytmu blitterowego. Blitterowi na wejście podaje się lokację prostokątnej płaszczyzny do wypełnienia. Należy podać współrzędne lewego górnego i prawego dolnego rogu wypełnianego prostokąta.
![]() ![]() Czyli wypełnia co drugi zamknięty fragment linii. Taką metodą, linia po linii wypełniałby również nasz obrazek. Właśnie, dlaczego ten czworobok na obrazku ma dziurawe niektóre linie? Do metody blitterowej jest wymagana specjalna procedura drawto. 3. Drawto blitterowe Choć lepiej byłoby nazwać je drawtem funkcyjnym. Według definicji matematycznej prosta jest wykresem pewnej funkcji, co znaczy, że dla każdego argumentu dziedziny istnieje tylko jedna wartość.
Linie rysowane na ekranie nie spełniają tego warunku i jedynie umownie są odcinkami. Drawto funkcyjne kreśli odcinki zgodnie z definicją (stąd właśnie dziury w liniach). A oto przykład:
Samych metod kreśenia linii nie będę tutaj omawiał, gdyż nie jest to kwestia trudna. Przy wnikliwej analizie dołączonej do artykułu żródłówki, łatwo wyłuskasz algorytm procedury służącej do wyznaczania przebiegu krawędzi, która opiera się na zasadach drawta blitterowego. Ambitnym podsunę pewien pomysł. Spróbujcie napisać drawto chamskie z osobnym kodem dla każdego nachylenia będzie zajmować masę pamięci, ale za to zyska na szybkości. Metoda blitterowa jest, na tle pozostałych, bardzo szybka. Jej wadą jest natomiast niewielka precyzja. Najprostszym sposobem na uzyskanie pełnej skuteczności tej metody jest rysowanie każdej ścianki na osobnym roboczym bitplanie, który przed każdym użyciem jest czyszczony, a następnie przenoszenie jej na ekran główny. Jednak taka operacja przynosi dwukrotne obniżenie efektywności procesu rysowania. 4. "Nonblitter fill methode" Opiszę zastosowanie metody nieblitterowej w dwóch wersjach. Obie opierają się na moich pomysłach i doświadczeniach i nie zdziwiłbym się, gdyby osobom obeznanym z tematem wydały się dziwne. Metoda blitterowa opiera się na narysowaniu granic płaszczyzny (konturów figury) na ekranie. W metodzie nieblitterowej na ekranie będzie rysowana od razu cała ścianka, której kontury zostaną wcześniej wyliczone i zapamiętane. Podstawą funkcjonowania metody nieblitterowej jest wyznaczenie, które linie ograniczają ściankę od prawej, a które od lewej strony. Umożliwi to łatwe rysowanie ścianki linia po linii. Aby to zrobić, przede wszystkim należy uporządkować wierzchołki figury tworzącej ściankę. Załóżmy, że przedmiotem naszych operacji jest ścianka czworokątna, zdefiniowana jako kwadrat:
Jest to konieczne przygotowanie, by nasze algorytmy poprawnie działały. 5. Wersja 1 Wersja ta jest bardzo skomplikowana, swe pełne zasosowanie znajduje dopiero przy gouraudach i texturach. Wykorzystywanie jej jedynie dla wypełnianych wektorków jest bezzasadne, ale zapoznanie się z jej istotą może znacznie wpłynąć na poszerzenie twoich koderskich horyzontów.
Załóżmy, że nasza ścianka jest jedną z sześciu tworzących sześcian, który mamy zamiar animować na ekranie. Nasza bryła posiada 12 krawędzi, ale naraz na ekranie nie może ich być więcej niż 9 ( przy widocznych trzech ścianach ). By określić, które krawędzie będą widoczne, należy sporządzić poręczną tablicę: A następnie dokonać sumy logicznej (ORA) odpowiednich fragmentów tablicy i zapisać ją w ustronnym miejscu (najlepiej na stronie zerowej). Np. suma logiczna dla ścianek 0,2 i 4 wyglądałaby następująco:
!!!!!--!!!!- Wykrzyniki oznaczają oczywiście krawędzie widoczne. Powyższa tablica jest jedynie przykładem i pasuje do sześcianu narysowanego przeze mnie na kartce.
Następnie należy zapisać w pamięci, jaki jest przebieg krawędzi. Dla ułatwienia znów wyjdziemy od przykładu.
Pamiętaj jednak, że ostatni punkt krawędzi jest zarazem pierwszym kolejnej. Przy rysowaniu ścianki odgrywa to ogromną rolę.
W powyższy sposób należy wyznaczyć przebieg wszystkich krawędzi. Jeśli to wykonasz, możesz przystąpić do konstruowania ścianek. Zaczniemy od schematu pomocniczego:
6. Wersja 2 Metoda ta jest dosyć prosta do przyswojenia i przystępna w użyciu. Nadam jej nazwę metody dwóch granic. Wymaga dwóch buforów (najlepiej na stronie zerowej), których długość wynosi Ymax-Ymin+1, czyli jest równa wysokości ścianki. Przed narysowaniem każdej ścianki bufory należy wyczyścić (wypełnić zerami). Następnie od wartości wertykalnej każdego wierzchołka należy odjąć Ymin. Wówczas Ymin będzie równy 0, a Ymax będzie sięgał do ostatniego bajtu buforów.
Zanim przeczytasz algorytm wpisywania przebiegu krawędzi do buforów, przyjrzyj się poniższemu schematowi.
Krawędź 0 powinna być wpisana do buf1 5-9. Zarówno 5 jak i 9 są wolne więc zostaje wpisana. Zwróć uwagę, że bufor bieżący może być zmieniany nawet dwukrotnie. Przeanalizuj działanie algorytmu, jeśliby program zaczynał od krawędzi 1, a kończył na krawędzi 0. Po wykonaniu tych operacji, w jednym z buforów (nie wiemy w którym) znajdą się dane o przebiegu krawędzi prawostronnych, a w drugim o przebiegu krawędzi lewostronnych. By stało się jasne, co jet w czym, wystarczy dodać do siebie kilka początkowych wartości wpisanych do buforów, wyniki dodawań porównać. Wynik mniejszy będzie posiadał bufor lewostronny, a większy prawostronny. Proste, szybkie i zawsze działa. 7. Eliminacja zasłoniętych ścian W tym oraz w pozostałych rozdziałach zajmę się kilkoma zagadnieniami związanymi z eliminacją zasłoniętych ścian. Na początku zajmę się najprostszym testem na widoczność ścianki. Algorytm, którym się posłużymy sprawdza kierunek rysowania krawędzi ścianki. Jeśli z testu wyniknie, że kierunek jest prawoskrętny będzie to oznaczać, że ścianka jest widoczna, przeciwnie będzie, gdy okaże się, że kierunek jest lewoskrętny.
Aby, móc poddać ściankę testowi, musimy ją najpierw odpowiednio opisać. Robimy to poprzez uporządkowanie jej wierzchołków w sposób opisany w rozdziale czwartym. Wierzchołki numerujemy kolejno przyjmujemy prawoskrętny porządek numerowania.
Wspomnę jeszcze o pobocznej zalecie korzystania z tego wzoru, która ujawnia się, gdy mamy do czynienia ze ściankami trójkątnymi (o trzech wierzchołkach). Wynik obliczeń jest proporcjonalny do pola ścianki. Dzięki temu łatwo można zrobić efekt, w którym obracana bryła będzie oświetlana przez lampę umieszczoną "przed ekranem". Aby to zrobić, należy obliczyć jaka jest wartość "W" dla każdej ścianki w położeniu, gdy ma największe pole. Następnie obliczenie:
a = ---- wMax pozwoli nam obliczyć kolor ścianki. Wynik ilorazu będzie zamknięty w przedziale [-1, 1]. Jeśli a będzie ujemne, ścianka jest niewidoczna, jeśli a jest równe 1, ścianka ma największe pole i powinna być najmocniej oświetlona. 8. Rzecz o półprekalkach Teraz pozostaje już tylko drobny szczegół - jak wykonać te obliczenia w asemblerze. Dla każdego 16 bitowego procesora wystarczyłoby na to zaledwie kilka rozkazów. Dla 6502 kwestia mnożenia urasta do rangi problemu. Można go rozwiązać na dwa sposoby. Pierwszym jest liczenie "na piechotę", drugim jest zastosowanie tablic. Oba pozostawiają wiele do życzenia. Jedyne rozkazy 6502 pozwalające na dokonanie mnożenia i dzielenia to rozkazy przesunięć logicznych. Musimy zatem posłużyć się w miarę szybkimi procedurami. Prezentuję dwie - zadaniem pierwszej jest przemnożenie liczby ośmiobitowej przez ośmiobitową, natomiast zadaniem drugiej jest dzielenie liczby szesnastobitowej przez ośmiobitową. Samych procedur nie omawiam poruszając jedynie kwestie optymalizacji. Jeśli chcesz zgłębić istotę ich funkconowania, polecam "Asembler 6502" Jana Ruszczyca (str. 110-113) oraz artykuł "MulDiv" z 4(24)/93 numeru Tajemnic Atari. Na pierwszy ogień pójdzie mnożenie.
Dane wejściowe:
Dane wyjściowe:
(MSB - bardziej znaczący bajt)
lda #0
lsr m1
Przejdżmy do dzielenia.
Dane wejściowe:
Dane wyjściowe:
ldx #8
Korzystanie z powyższych procedur może być uzasadnione w niewieu wypadkach. W wielu efektach dla narysowania jednej klatki wymagane jest wykonanie niekiedy wielu tysięcy mnożeń, wykonywanie ich na bieżąco znacznie zmniejszyłoby efektywność kodu. Istnieje na szczęście alternatywa - stosowanie tablic. Niestety, obok licznych zalet posiada ona również wady. Szerokie zastosowanie tablic ogranicza niewielka ilość posiadanej pamięci. Jeśli potrzebujemy tablicy do testowania widoczności ścian, korzystając z trybu graficznego o chunku 4x4 (rozdzielczość 64x48), wystarczająca okaże się tablica z 1600 elementów (40x40). Aby wyniki obliczeń były dokładne, wypadałoby, aby każdy element był dwubajtowy (#1521=$5f1). By ułatwić sobie dostęp do wyników, należałoby sporządzić dwie tablice - jedną z młodszymi, a drugą ze starszymi bajtami wyników. Oszczędziłoby to niepotrzebnego mnożenia przez dwa przy wyszukiwaniu odpowiedniej lokacji w tablicy. Tablica nie musi być zwarta, dla ułatwienia dostępu do niej (by nie mnożyć przez 40) wystarczy rozpisać ją w sposób podobny do rozłożenia pamięci obrazu w "szybkich efektach" (opisałem go w CA Zine #1). Należy zrobić to w następujący sposób:
Tablica jest rozpisana czterdziestobajtowymi fragmentami na te same miejsca kolejnych stron. Na skorzystanie z tej tablicy wystarczy kilka rozkazów:
X - mnożna
clc
lda <tab1
39*39=1521 Oczywiście taka tablica nie będzie gwarantowała wysokiej jakości obliczeń. Jeśli decydujesz się na tablicę z dwubajtowymi wynikami, możesz ją wyliczyć w asemblerze tuż przed jej użyciem (przykładowa procedurka znajduje się na dysku z magazynem). Natomiast, jeśli decydujesz się na wyniki jednobajtowe, w trosce o precyzję obliczeń, radziłbym wyliczyć tablicę w BASICu i umieścić ją na stałe w pamięci (aż do momentu, gdy stanie się niepotrzebna). Nie zdziwiłbym się, gdyby powyższe sugestie dotyczące wykonania mnożeń i dzieleń, bardzo cię wystraszyły. Rzeczywiście sprawiają trudności w zrozumieniu ich istoty, jak i we wprowadzeniu ich w życie. Osobiście znam ten ból - często korzystam z którejś z dwóch powyższych opcji, ale robię to tylko wówczas, gdy jest to naprawdę konieczne. Osobiście w przypadku testowania widoczności ścian zaleciłbym wykonanie półprekalka. Prekalkiem zwykliśmy złośliwie określać efekty, których trudność wykonania sprowadza się do napisania szybkich procedur rozpakowujących z pamięci kolejne klatki animacji. Jednym słowem - animki. Robienie czegoś takiego (bez informowania widza) oczywiście uwłacza godności kodera. Zrobienie półprekalka jeszcze mieści się w ramach naszego kodeksu etyki zawodowej. Laik zdziwiłby się w ilu demach można znaleść półprekalki. Półprekalk to efekt, w którym jedynie część danych koniecznych do narysowania klatki animacji jest wcześniej przeliczona. Załóżmy, że naszym celem jest wykonanie efektu prezentującego wektorowo obracany sześcian z wypełnionymi ściankami bocznymi. Istotą tego efektu jest oczywiście wypełnianie i dla czystości sztuki powinno być ono wykonywane na bieżąco. Nie mogłoby się to odbyć bez rysowanych (tworzonych) w czasie rzeczywistym krawędzi bryły. Co zatem możemy wcześniej przeliczyć? Oczywiście wierzchołki i dane dotyczące widoczności ścian. Wszystkie danedotyczące widoczności możemy zawrzeć w jednym bajcie - dla każdej ścianki będzie przypadał jeden bit. Natomiast dla każdego wierzchołka sześcianu potrzebujemy dwóch bajtów - jeden dla danej horyzontalnej, drugi dla danej wertykalnej. Pamiętaj jednak, że jeśli widoczna jest:
1 ściana, potrzebujesz tylko danych o 4 wierzchołkach Rozważania te dotyczą przypadku sześcianu. Czas na krótką ewaluację:
Zalety półprekalka:
Jako praktyk zalecam ci robienie półprekalków, oczywiście w granicach rozsądku i tylko w przypadkach, gdy jest to rzeczywiście uzasadnione i opłacalne. Dodam, że wszystkie sześciany obracające się w naszym demie (Ergo Bibamus) są półprekalkami. Pozostałe obliczenia we wszystkich efektach są wykonywane w pełni w czasie rzeczywistym. 9. Obiekty złożone Korzystając z algorytmu przedstawionego w rozdziale 7 możemy skutecznie odwzorowywać na ekranie jedynie bryły najprostsze - graniastosłupy, ostrosłupy, walce i bryły sferyczne - uściślając, te bryły, przy rysowaniu których nie zajdzie możliwość by któraś ze ścianek zasłoniła jedynie fragment innej. Ale tę niedogodność można oczywiście obejść, najlepszym dowodem na to są choćby fantazyjne obiekty z Intel Outside i Bitter Reality oraz torusy z Asskickera i Ergo Bibamus. Problem można rozwikłać na dwa sposoby - pierwszy poprzez składanie bryły a drugi poprzez wyliczenia matematyczne. Drugi sposób w zastosowaniu widziałem tylo raz - w intrze do Energy Zine. Tam rzeczywiście zasłonięte fragmenty brył są wyliczane - jest to bardzo wysoka szkoła jazdy. Największą wadą tej metody jest to, że dla każdej z brył trzeba wyliczyć odpowiednie funkcje. Zainteresowanym polecam lekturę 43 rozdziału książki R. Baumanna "Grafika komputerowa". W tym przypadku zainteresowany = szalony. Zajmijmy się zatem sposobem pierwszym. Ogranicza się on do animowania jednocześnie kilku odrębnych obiektów, które po odpowiednim odwzorowaniu na ekranie tworzą jeden obiekt końcowy. Wyobrażmy sobie, że naszym celem jest animowanie bryły przypominającej samolot. Nasz samolot będzie dość schematyczny, będzie składał się z kadłuba, pary skrzydeł i ogona. Każdy z tych elementów w swej konstrukcji musi spełniać warunki elementu pierwotnego, czyli takiego, w którym żadna ze ścianek nie zasłania częściowo innej ścianki. I tak, załóżmy, że kadłub będzie owalem, a skrzydła i ogon płaszczyznami. Dokonanie animacji każdego z tych elementów z osobna nikomu nie sprawiłoby trudności, problem pojawia się, gdy musimy je ze sobą zestawić. By to skutecznie zrobić, musimy określić kolejność rysowania elementów na ekranie. By to zrobić, należy dla każdego elementu wyznaczyć punkt kontrolny, którego położeniem posłużymy się do wyznaczenia priorytetu ścianki. Punkty kontrolne skrzydeł niech znajdą się na koniuszkach skrzydeł, kadłuba na samym dziobie, a ogona w jego zakończeniu. Punkty te poddajemy tym samym obrotom, co całą bryłę i możemy przystąpić do dzieła. Interesować nas będzie wyłącznie położenie punktów względem osi Z (czyli wartości ich "Z"). Jeżeli punkt kontrolny lewego skrzydła jest bardziej zagłębiony od prawego to elementy rysujemy w kolejności:
Dla ułatwienia zrozumienia istoty tego problemu podam jeszcze jeden przykład. Pamiętasz sześcian z rozklejonymi ściankami z Bitter Reality? W tym przypadku każda ze ścianek posiada aż cztery punkty wskażnikowe - własne wierzchołki. Dla każdej ze ścianek wystarczy dobrać dowolne dwa wierzchołki, dodać ich wartości położenia względem osi Z, co pozwoli określić stopień zagłębienia, a następnie rysować ścianki w kolejności od najbardziej do najmniej zagłębionej. Wadą tej metody jest to, że korzystając z niej często rysujemy ścianki, które następnie są całkowicie przesłonięte przez inne elementy bryły. Istnieją metody pozwalające na częściowe wyeliminowanie tej wady, jednak nie ośmielę się opisać żadnej z nich, gdyż każda z nich jest na razie dla mnie wyłącznie pomysłem, którego jeszcze nie sprawdziłem w działaniu. I ostatnia uwaga. Jeżeli rysujesz obiekty złożone, nie możesz korzystać z blitterowej metody wypełniania ścianek. Chyba nie muszę tłumaczyć d aczego. Mam nadzieję, że powyższe wskazówki okażą się przydatne komukolwiek. Liczba koderów będących w stanie zrobić na naszym komputerze cokolwiek godnego uwagi niestety nie zachwyca, dlatego każda nowa twarz w gronie doświadczonych jest bardzo cenna. Pisząc ten artykuł miałem bardziej na uwadze interes sceny niż redakcji magazynu, w którym został on opublikowany. Chłopaki, jest nas coraz mniej, musimy zacząć dbać o siebie i trochę sobie pomagać, nie prowadzić scenowych wojen podjazdowych.
To tyle na dziś, ale nie myślcie, że znikam na zawsze. Króger/Quasimodos Ps. Być może kilka osób zawiodłem tym, że nasze demo - Ergo Bibamus - nie zostało wypuszczone zarówno na QP '97 jak i QP '98. W chwili obecnej jego kod jest zupełnie rozczłonkowany, a ono samo raczej dalekie od ukończenia, ale, jeśli nie opadnę z sił, to Ergo Bibamus znajdzie się w waszych zbiorach jeszcze w tym roku kalendarzowym. Choć też nie koniecznie musi się tak stać. Bumelanctwo to przywilej koderów.
|