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.

      Dwie przedstawione przeze mnie poniżej procedury wypełniają obiekty poziomymi liniami. We wskazanej na schemacie linii częśc obiektu jest w dwóch fragmentach. Z takimi właśnie obiektami proponowane przeze mnie algorytmy sobie nie radzą. By sobie dały radę, należy feralny obiekt podzielić na kilka mniejszych.

      Poniżej przedstawiam dwa sposoby wypełniania. Pierwszy klasyczny, blitterowy, drugi nowatorski (??) nieblitterowy. Każdy posiada inne cechy i możliwości zastosowania.


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.

      Trójkąciki w narożnikach wyznaczają rogi prostokąta, którym zajmie się blitter. Kółeczkami zaznaczyłem wierzchołki narysowanego prostokąta.

      Współrzędne narożników prostokąta uzyskujemy poprzez odnalezienie skrajnych warości horyzontalnych i wertykalnych spośród wszystkich wierzchołków tworzących figurę.

      Blitter wypełnia liniami. Zaczyna od górnej linii prostokąta a kończy na ostatniej. Wypełnia linie od lewej do prawej. Blitter wypełnia w kratkę.

Na przykład taką linię...


...wypełniłby następująco:



      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:

      Drawto funkcyjne ustawia tylko jednego piksela w linii. Ale dlaczego powinniśmy używać akurat tego algorytmu? Po pierwsze dlatego, że w przypadku, gdy narysujemy figury tradycyjnym drawto, przy ich wypełnianiu będzie powstawać wiele błędów i nieścisłości. Po drugie dlatego, że tradycyjne drawto jest znacznie wolniejsze. Wadą tej procedury jest to, że mniej dokładnie wyznacza granice rysowanych płaszczyzn. Po trzecie algorytm funkcyjnego drawta jest używany do wyznaczania krawędzi ścian także w metodzie nieblitterowej.

      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:

Jej wierzchołki są numerowane kolejno, od dowolnie wybrnego, w porządku prawoskrętnym. Aby zrozumieć ideę prawoskrętności, najłatwiej jest wyobrazić sobie obwód ścianki jako tor, po którym porusza się w kierunku:

0-1-2-3-0

Wówczas łatwo zauważyć, że w ruchu wykonuje się ciągłe skręty w prawo.

Gdy mamy ponumerowane wierzchołki należy ponumerować krawędzie (również w porządku prawoskrętnym):

numer krawędzi
od do (wierzchołki)
0
0 1
1
1 2
2
2 3
3
3 0

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ę:

sciana
0123456789ab
0
!!!!--------
1
----!!!!----
2
!---!---!!--
3
--!---!---!!
3
---!---!!-!-
3
-!---!---!-!

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:

0123456789ab
!!!!!--!!!!-

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.

      Oto krawędź o zaznaczonych powyżej współrzędnych. Zanim zapamiętamy w pamięci jej przebieg, należy zapisać w "ustronnym miejscu" dwie dane o niej. Pierwszą jest Y1, świadcząca odkąd na osi wertykalnej się rozciąga, a drugą delta Y (Y2-Y1) świadcząca o długości krawędzi.

      Teraz możemy już zapisać w pamięci przebieg linii. Najpierw należy wyznaczyć w przestrzeni adresowej dziewięć (w przypadku sześcianu) 48 bajtowych (przy ekranie z 48 liniami) buforów. Dla ułatwienia dostępu do buforów niech każdy będzie ulokowany na początku osobnej strony pamięci.

     Dlaczego dziewieć buforów, a nie cztery (tyle krawędzi mają przecież ścianki sześcianu)? Optymalizując kod (ale zarazem go komplikując) sugerowałbym przed narysowaniem pierwszej ścianki wyliczyć przebiegi wszystkich (od 4 przy widocznej jednej ściance aż po 9 przy widocznych trzech) krawędzi, a następnie sztukować z nich kształty ścianek. Daje to znaczną oszczędność czasu.

     Po tym wyjaśnieniu możemy przystąpić do wyznaczenia przebiegu krawędzi. Dla każdej z nich przypada jeden bufor. Wyznaczać je będziemy stosować algorytm drawta funkcyjnego opisany w rozdziale 3. Zapisywać do bufora będziemy tylko wartości odwzorowujące przebieg horyzontalny krawędzi. Dane o przebiegu wertykalnym (Y1 oraz Y2-Y1) już mamy zapisane. Bufor naszej krawędzi po zapisaniu powinien wyglądać tak:

5,5,6,6,6,7,7,8,8,8,9,9

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:

      Załóżmy, że po obrotach i rzucie perspektywicznym nasza ścianka przybrała powyższe kształty. Postarajmy się ją narysować.

      W pierwszym kroku musimy wyznaczyć skrajne wierzchołki - położony najwyżej (3) i najniżej (1). Pamiętając o prawoskrętnej kolejności numerowania krawędzi (patrz rozdział 4), łatwo możemy stwierdzić, że krawędzie 1 i 2 wyznaczają lewą granicę ścianki, a krawędzie 3 i 0 granicę prawą. Ponieważ przebieg krawędzi mamy zapisany w buforach, rysując kolejne linie (od lewej do prawej) możemy odwzorować na ekranie całą ściankę. Oczywiście, gdy rysujemy pojedynczą linię, nie należy tego robić punktowo (pikselami), a o ile jest to możliwe, od razu zapełniać całe bajty.

      Przy rozstrzyganiu, które krawędzie są "lewymi", a które prawymi, należy wziąć pod uwagę, że niektóre mogą nie odgrywać żadnej roli dla kształtu ścianki. Są to krawędzie których y2-y1=0. Schemat mówi wszystko:
      Jak widać krawędź rozciągająca się między wierzchołkami 1 i 2 nie jest lewostronna jak i prawostronna. Powyższy algorytm ma swe zastosowanie, gdy równolegle z przebiegiem krawędzi w osobnym buforze zapisujemy jakieś interpolowane wartości (jest tak w przypadku wyżej wspomnianych gouraudów i textur). W wypełnianych wektorkach można go użyć, jeśli:
  • obracana bryła jest bardzo dużych rozmiarów, czyli ma długie krawędzie
  • stosunek liczby krawędzi do liczby ścian nie przekracza rozsądnej wartści 2
Choć oczywiście z tymi sugestiami zgadzać się nie trzeba. Do prostych wypełnianek zalecałbym drugą wersję nieblitterowej metody wypełniania.

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.

      Liczby 0-9 to numery kolejnych komórek bufora, a liczby w buforach to numery krawędzi, których przebieg będzie w rzeczywistości umieszany w buforach. Czyli w buforze 1 będą umieszczone dane o przebiegu krawędzi 0 i 1, a w buforze 2 dane o przebiegu krawędzi 2 i 3. Oczywiście dotyczy to tego szczególnego ustawienia ścianki.

O tym, czym jest przebieg krawędzi szerzej wspominałem w poprzednim rozdziale.

Umiejscowienie krawędzi w buforze zależy od ich położenia w ściance, a dokładniej mówiąc jest równoległe, co widać na schemacie.

Oto obiecany algorytm:
  1. Wyczyść bufory.
  2. Bufor 1 buforem bieżącym.
  3. Sprawdź pierwszy i ostatni bajt miejsca w buforze bieżącym, w które powinien być wpisany przebieg krawędzi.
  4. Jeśli któryś z nich jest zerem, wpisz przebieg krawędzi.
  5. Jeśli żaden z nich nie jest zerem zmień bufor bieżący i wpisz doń przebieg krawędzi.
  6. Czy jest jeszcze krawędż do rysowania? Jeśli tak, skocz do 3
  7. Jeśli nie, zakończ.
A teraz przeanalizujmy funkcjonowanie powyższego algorytmu dla naszego schematu.

Krawędź 0 powinna być wpisana do buf1 5-9. Zarówno 5 jak i 9 są wolne więc zostaje wpisana.
Krawędź 1 powinna być wpisana do buf1 0-5, 0 jest wolne, więc zostaje wpisana.
Krawędź 2 powinna być wpisana do buf1 0-6, ale zarówno 0 jak i 6 są zajęte, dlatego też buf2 staje się buforem bieżącym i dane o krawędzi 2 zostają wpisane do buf2 0-6.
Krawędź 3 powinna być wpisana do buf2 6-9, 9 jest wolne i 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.

      Każda ścianka będąca po obrocie nadal w układzie prawoskrętnym, pozostaje widoczna. Ścianki niewidoczne, to ścianki w układzie lewoskrętnym, np. ta (po obrocie o 180 stopni wokół osi Y),
lub ta (po obrocie o 180 stopni wokół osi X).
A oto wzorek:

w=(x2-x1)*(y3-y2)-(x3-x2)*(y2-y1)

      Pod x1, x2, x3 podstawiamy współrzędne horyzontalne trzech kolejnych (nie istotne, od którego się zaczyna ) wierzchołków ścianki. Natomiast pod y1, y2, y3 współrzędne wertykalne tychże. Jeżeli w>=0, to ścianka jest w układzie prawoskrętnym, czyli jest widoczna.

      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:

    w
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:
      m1 - mnożna
      m2 - mnożnik

Dane wyjściowe:
      wn - LSB wyniku
      akumulator - MSB wyniku

(MSB - bardziej znaczący bajt)
(LSB - mniej znaczący bajt)

   lda #0
   sta wn
   ldx #8
l0 lsr m1
   bcc l1
   clc
   adc m2
l1 ror @
   ror wn
   dex
   bne l0

Wykonanie tego zajmie 171 cykli. Zdecydowanie zbyt dużo. Przyspieszeń można dokonać poprzez:

  • rezygnację z pętli, oczywiście wydłuży to kod, ale przecież walczymy o szybkość
  • rezygnację z LSB wyniku-jeśli w dalszych obliczeniach posługujemy się nadal liczbami ośmiobitowymi, możemy śmiało się na to zdecydować,obliczenia stracą jednak troszkę na dokładności
  • rezygnację z rozkazu CLC w pętli,możemy się na to zdecydować przypadku, gdy operujemy na dużych liczbach i nie dbamy o precyzję obliczeń
Jeśliby dokonać optymalizacji uwzględniając wszystkie możliwości otrzymamy następujący kod:

   lsr m1
   bcc l0
   adc m2
l0 ror @
   lsr m1
   bcc l1
   adc m2
l1 ror @
   ...

I tak aż do l7. Procedura zajmowałaby 56 bajtów i zabierałaby tylo 84 cykle, ale zarazem dawałaby dosyć niedokładne wyniki. Dalsze przyspieszenie mnożenia możnaby uzyskać przy założeniu, że M1 nie zajmuje wszystkich (starszych) bitów.

Przejdżmy do dzielenia.

Dane wejściowe:
      akumulator - MSB dzielnej
      DA - LSB dzielnej
      DK - dzielnik

Dane wyjściowe:
      DA - iloraz
      akumulator - reszta z dzielenia

   ldx #8
l0 asl da
   rol @
   cmp dk
   bcc l1
   sbc dk
   inc da
l1 dex
   bne l0

      Przed wywołaniem procedury należy sprawdzić, czy dzielnik nie jest większy od MSB dzielnej. Wówczas należy przerwać operację. Zaznaczę, że przed rozkazem SBC DK nie jest wymagane SEC, gdyż znacznik C jest już ustawiony. Możliwości optymalizacji są już bardziej ograniczone, możemy jedynie zrezygnować z użycia pętli.

      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:

a=0  $000  a*0 a*1 a*2 ... a*38 a*39
b=1  $100  b*0 b*1 b*2 ... b*38 b*39
c=2  $200  c*0 c*1 c*2 ... c*38 c*39
      ...                            
z=39 $2700 z*0 z*1 z*2 ... z*38 z*39

Tablica jest rozpisana czterdziestobajtowymi fragmentami na te same miejsca kolejnych stron. Na skorzystanie z tej tablicy wystarczy kilka rozkazów:

X - mnożna
Y - mnożnik

   clc
   txa
   adc >tab1
   sta adr1+1
   sta adr2+1
   lda (adr1),y
   sta w_lsb
   lda (adr2),y
   sta w_msb

Oczywiście należy to poprzedzić ustaleniem młodszego bajtu adresu tablicy, ale wystarczy to zrobić raz, na początku programu:

   lda <tab1
   sta adr1
   lda <tab2
   sta adr2

      Dążąc do uproszczeń możemy zdecydować się na to, by nasza tablica zawierała jedynie jednobajtowe wyniki. Wówczas należy wszystkie elementy tablicy podzielić przez tę samą liczbę, odpowiednio dużą, by żaden element nie był większy od 255. W przypadku tablicy 40*40 wszystkie elementy możemy podzielić przez 6, gdyż:

   39*39=1521
   1521/6=253.5

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
2 ściany, potrzebujesz tylko danych o 6 wierzchołkach
3 sciany, potrzebujesz tylko danych o 7 wierzchołkach

Rozważania te dotyczą przypadku sześcianu. Czas na krótką ewaluację:

Zalety półprekalka:

  • najwyższa jakość wyliczenia danych
  • oszczędność pamięci - nie musisz rezerwować pamięci na tablice sinusów, tablice do wyliczenia perspektywy, tablice do testowania widoczności ścianki
  • oszczędność 2000-3000 cykli
Wady półprekalka:
  • sztywność kodu - bryły mogą się obracać tylko we wcześniej wyznaczony sposób
  • konieczność napisania w BASICU programu prekalkulacyjnego
  • rozterki moralne, czy powinno się takie rzeczy robić (!?!)
      Może się oczywiście zdarzyć, że przeliczona przez nas tablica obrotów przewyższy swymi rozmiarami łączną rozpiętość wszystkich tablic, z których korzystania jesteśmy zwolnieni. Wówczas nie możnaby mówić o oszczędności pamięci.

      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:

  1. Lewe skrzydło
  2. Kadłub
  3. Prawe skrzydło
Odwrotnie będzie, gdy bardziej zagłębiony będzie punkt kontrolny prawgo skrzydła. Ogon będzie rysowany przed pozostałymi trzema elementami (bez zmieniania ich kolejności) jeżeli jego punkt wskażnikowy będzie bardziej zagłębiony od punktu wskaźnikowego kadłuba (umieszczonego w dziobie). W przeciwnym wypadku, będzie rysowany na samym końcu.

      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.