Poniższy artykuł pozwala zrozumieć, czym jest interpolacja, jak można ją wykorzystać programista, a przede wszystkim jak sporządzić jej najszybsze wcielenie w języku asemblera.

Szczypta teorii

Czynność interpolowania w skrócie polega na odtworzeniu nieznanych wartości argumentów z danego przedziału na podstawie znanych wartości argumentów spoza tegoż przedziału. Jeżeli dana jest dowolna funkcja f(x), gdzie x należy do przedziału (p,q), to z łatwością można wyliczyć wartości funkcji dla wszystkich argumentów jej dziedziny. Gorzej jest, gdy dana jest nam tylko dziedzina funkcji i wartości części jej argumentów, a nie są znane wartości pozostałych argumentów i sama funkcja. W takich przypadkach z pomocą przychodzi interpolacja, która pozwala odtworzyć nieznane wartości argumentów wewnątrz dziedziny. Artykuł poniższy traktuje wyłącznie o interpolacji linearnej, tzn. takiej, gdzie odtwarzane są wartości argumentów funkcji liniowej. W naszych rozważaniach z danej dziedziny (p,q) znane są tylko p i q. Choć wystarcza to do odtworzenia samej funkcji, to nie będziemy tu do tego zmierzać, gdyż jest to boczna, dłuższa droga prowadząca do rozwiązania, czyli wyliczenia wartości wszystkich argumentów. Konieczne dla zrozumienia dalszej części artykułu pojęcia wytłumaczę, na przykładzie -( f(p)=5, f(q)=9 ), czyli:

                                   5 - - - - - - 9

Dziedzinę funkcji liniowej stanowią wszystkie podane elementy (p, sześć elementów pustych, q). Zakresem interpolacji (A) nazwiemy liczbę elementów pustych. By móc cieszyć się efektami poprawnie wykonanej interpolacji (dla uproszczenia posługuję się tylko liczbami naturalnymi), tzn.

                                   5 6 6 7 7 8 8 9

należy wyliczyć współczynnik interpolacji (WI) z dość oczywistego wzorku:

                                     f(q) - f(p)
                              WI = ---------------
                                         A+1

Wartość kolejnych elementów zakresu interpolacji można wyliczyć mnożąc numer elementu (kolejną pozycję w dziedzinie) przez WI, a wynik dodając do f(p). W praktyce współczynniki interpolacji tablicuje się w zwykłej tablicy wyników dzielenia, a następnie żmudnie dodaje się. Wyliczone w ten sposób wartości przelicza się następnie na pozycję w teksturze, stopień natężenia światła (gourard), kąt padania światła (phong) itp. Natomiast tajemnica szybkiej interpolacji tkwi w posłużeniu się tablicą trójwymiarową, która pozwala uniknąć czasochłonnego dodawania.

Tablica 3D

Metoda tradycyjna opierała się na dwuwymiarowej tablicy ilorazów (wymiarem pierwszym dzielna, a drugim dzielnik), dzięki której wyliczyć można współczynnik iterpolacji. Metoda szybka, jak wspomniałem, opiera się na tablicy trójwymiarowej, pierwsze jej dwa wymiary pozostają bez zmian (dzielna i dzielnik WI), trzecim jest liczba całkowita nieujemna, przez którą mnożony jest wynik dzielenia. I tak np. dla ilorazu równego 1.7 kolejne elementy fragmentu tablicy przybiorą wartości: 0, 2, 3, 5, 7 itd. Ze zrozumiałych powodów wyniki w tablicy są wyłącznie liczbami całkowitymi nieujemnymi. Problem znaku elementu tablicy (znak WI zależy od stosunku f(p) do f(q)) poruszam poniżej.

Sugeruję sporządzenie jednej tablicy trójwymiarowej zamiast dwóch dwuwymiarowych (tzn. tablicy ilorazów oraz tablicy ich iloczynów z liczbami całkowitymi nieujemnymi). Jest to rozwiązanie najszybsze, choć nieekonomicznie wykorzystujące pamięć komputera (przecież jeden iloraz nie jest przypisany tylko do jednej pary dzielnej i dzielnika!). Dobrym rozwiązaniem jest, by wielkośc trzeciego wymiaru miała stałą wartość (0,c) dla każdego WI, gdzie c powinno być nie mniejsze od zakresu interpolacji powiększonego o 1. Jak korzystać z tablicy? Spieszę z odpowiedzią - jeżeli f(q)-f(p) (I wymiar) mieści się w przedziale (0,a), a A (II wymiar) w zakresie (0,b), to odpowiedni fragment tablicy z iloczynami odnajdujemy wyliczając: dzielna*(b+1)*(c+1)+dzielnik*(c+1). Znajduje się tam c+1 elementowy ciąg iloczynów WI z kolejnymi liczbami całkowitymi nieujemnymi. Pozostaje już tylko z niego skorzystać.

Szybki gourard

Cieniowanie ścianki metodą Gourarda polega na wyliczeniu natężenia światła na krawędziach, a następnie rysowanie jej kolejnymi poziomymi liniami, na których interpoluje się wartości natężenia światła wzięte z wcześniej wyliczonych krawędzi. Liczba punktów linii stanowi dziedzinę interpolacji, natężenie światła na jej skraju to f(p) i f(q). Po szczegóły odsyłam do artykułu "O wypełnianiu i wypełniankach" z trzeciego numeru magazynu dyskowego Serious. Oto jak przedstawia się główna procedura interpolacji:

L0      LDY 3D,X        ; 00
        LDA ODCIEN1,Y   ; 01
        DEX             ; 02 
        BPL L1          ; 03
        JMP PUNKT       ; 04
L1      LDY 3D,X        ; 05
        ORA ODCIEN2,Y   ; 06
L2      STA EKRAN       ; 07
        DEC L2+1        ; 08
        DEX             ; 09
        BPL L0          ; 10
        JMP KONIEC      ; 11

Procedura rysuje poziomą linię w trybie graficznym 9 BASICa (cztery bity wyznaczają jasność punktu) interpolując na całej jej długości krańcowe wartości określające natężenie oświetlenia. Linie 00-04 zapełniają cztery młodsze bity bajtów pamięci obrazu (prawe połówki), a linie 05-11 robią to z bitami starszymi (lewe połówki). W miejscach gdzie widnieje stała 3D (czyli pod L0+1 i L1+1), należy przed uruchomieniem procedury wpisać wyliczony w opisany wyżej sposób adres odpowiedniego fragmentu tablicy trójwymiarowej, natomiast w miejscu stałej EKRAN (L2+1) - miejsce w pamięci obrazu, gdzie ma być narysowany pierwszy od prawej strony punkt linii.

Uwaga! Jeżeli f(q)-f(p)>=0, to w linii 07 należy umieścić adres bajtu, gdzie narysowany będzie pierwszy punkt linii od lewej strony (bo w tym przypadku, przeciwnie do opisywanego wyżej, linia będzie rysowana od lewej do prawej strony), w linii 08 INC zamienić na DEC oraz zamienić odwołanie do tablicy ODCIEN1 na ODCIEN2 i na odwrót (linie 01 i 06).

Pary rozkazów 01,02 i 05,06 pobierają dane z tablicy trójwymiarowej, a następnie przetwarzają na piksel do wyświetlenia (w tablicy ODCIEN1 prawe połówki bajtów np. 0,5,9,A,B,F - a w ODCIEN2 połówki lewe - np. 0,10,20,B0,D0,E0). Po dokonaniu tych operacji w akumulatorze znajduje się bajt, który należy wpisać do pamięci obrazu (linia 07) i przygotować się do bajtu kolejnego (linia 08). Przed uruchomieniem procedury należy w rejestrze X umieścić liczbę pikseli w linii pomniejszoną o jeden. Pobranie z tablicy ostatniego piksela do wyświetlenia oznajmia procesor przez ustawienie znacznika N (linie 02,03 i 09,10). Jeżeli ostatni piksel przypada na lewą połówkę bajtu, możemy opuścić procedurę (linia 11). Jeśli natomiast ostatni piksel przypadnie na prawą połówkę bajtu, należy skoczyć do procedurki PUNKT (linia 04), która lewą połówkę weźmie z tła i całość umieści na ekranie. Odpowiednio, jeśli pierwszy rysowany piksel ma znaleźć się w lewej połówce, to naszą procedurę należy wywoływać skokiem do L1, a nie do L0 (oczywiście uprzednio wziąwszy z tła prawą połówkę bajtu). Oczywiście zupełnie odwrotnie brzmiałyby te uwagi w przypadku, gdy f(q)-f(p)>0.

Podsumowanie

Procedury (dwie, bo najwygodniej jest sporządzić jedną dla interpolacji rosnącej - f(q)-f(p)>0 i drugą dla malejącej - f(q)-f(p)<0) są naprawdę bardzo szybkie, szczególnie jeśli umieści się je na stronie zerowej (ze względu na często samo modyfikowanie się). Proponowana metoda ma jednak swoje wady - po pierwsze tablica trójwymiarowa jest ogromna (przy skromnych wymiarach 32 na 32 na 32 zajmuje połowę pamięci podstawowej komputera), a po drugie przy interpolowaniu większej liczy wartości (np. 3 przy gouraudowanych teksturach) szybkość metody przynosi pewne rozczarowanie, choć jest wiąż wyraźnie szybsza od metody tradycyjnej. Zastosowanie szybkiej interpolacji jest bardzo szerokie, ogranicza je tylko wyobraźnia programisty.

Paweł Cierkoński (Króger/Quasimodos)