Przekształcenia afiniczne

Wprowadzenie

W tym ćwiczeniu będziemy omawiać wykorzystanie podstawowych operacji matematycznych na macierzach w grafice komputerowej.

Jednym z głównych problemów grafiki komputerowej jest dokonywanie prostych przekształceń obrazów. Wyobraźmy sobie, że chcemy zrobić prostą grę platformową, podobną do Super Mario ®.

Składa się ona z wielu małych obrazków nazwanych po angielsku sprites. Animacja w takiej grze polega na dwóch podstawowych elementach:

szybkiej podmianie obrazów na kolejne klatki animacji
przesuwaniu, skalowaniu i obrocie każdego obrazka w przestrzeni 2D

W tym ćwiczeniu będziemy omawiać drugi z tych problemów - jak wydajnie przesuwać, skalować i obracać przedmioty w przestrzeni. Dla uproszczenia ćwiczenie będzie dotyczyć grafiki 2D, ale bez problemu można ten pomysł rozwinąć do dowolnej ilości wymiarów.

Wstępny program

Zacznijmy od następującego programu:

<style> body { background-color:#ccc; } </style>

<script src="//cdnjs.cloudflare.com/ajax/libs/p5.js/0.5.7/p5.js"></script>

<body>

<script type="text/javascript">

var imgA;

var imgB;

function setup() {

    createCanvas(512,512);

    background(255);

    imgA = createImage(512,512);

    imgB = createImage(512,512);

    imgA.loadPixels();

    imgB.loadPixels();

    var d = pixelDensity();

    for(var i=0; i<512*512*4*d; i+=4) {

      imgA.pixels[i]=240;

      imgA.pixels[i+1]=250;

      imgA.pixels[i+2]=240;

      imgA.pixels[i+3]=255;

      imgB.pixels[i]=240;

      imgB.pixels[i+1]=240;

      imgB.pixels[i+2]=250;

      imgB.pixels[i+3]=255;

    imgA.updatePixels();

    imgB.updatePixels();

function draw() {

    if (!keyIsDown(32)) {

      image(imgA,0,0);

      text('Image A',10,20);

    } else {

      image(imgB,0,0);

      text('Image B',10,20);

</script>

</body>

Program ten rysuje planszę z dwoma buforami do rysowania. Najpierw jest wyświetlany jasnozielony bufor o nazwie imgA, a po naciśnięciu spacji, wyświetla się bufor jasnoniebieski o nazwie imgB. Te dwa obrazy umożliwią obserwowanie różnic między dokonywanymi przekształceniami.

Wektorowa reprezentacja obrazów

(zadanie na ocenę 3)

Operacje opisywane w tym ćwiczeniu służą do przekształcania obiektów w układzie współrzędnych, niezależnie od ich rzeczywistego wyglądu. Może to być pojedynczy punkt w przestrzeni, grupa punktów określająca jakiś kształt (np. cztery wierzchołki kwadratu) albo nawet zbiór pikseli w obrazie rastrowym (gdzie każdy piksel ma zdefiniowaną współrzędną x i y). Dla uproszczenia my będziemy przekształcać pojedyncze punkty w przestrzeni 2D.

Zacznijmy więc od definicji takiego punktu w postaci wektora. Wektor to zbiór liczb powiązanych ze sobą uwzględniający ich pozycję. Wektory zapisujemy zazwyczaj w postaci wiersza albo kolumny:

W grafice 2D, wektor reprezentujący punkt w przestrzeni ma 3 wartości. Pierwsze dwie to współrzędne x i y, a trzecia wartość to zawsze 1. Ze względu na istnienie trzeciej wartości, mamy do czynienia z przestrzenią afiniczną, dzięki czemu oprócz obrotu i skalowania, możemy skutecznie modelować również przesunięcia. Z jednej strony jest ona konieczna, ale z drugiej strony może też służyć jako skuteczna metoda do sprawdzania poprawności operacji matematycznych omawianych później.

Jako pierwsze zadanie, należy stworzyć funkcję makeVector z argumentami x i y. Funkcja ta ma zwracać tablicę jednowymiarową, tak jak pokazano wyżej. Tablice w JavaScripcie definiujemy używając następującej składni: var tab=[1,2,3,4];

Następnie należy stworzyć funkcję drawVector przyjmującą dwa argumenty img i vec. Pierwszy argument to obraz, na jakim chcemy rysować (imgA lub imgB), a drugi argument to wektor, jaki ma być narysowany. Do rysowania możesz użyć funkcji img.set(x,y,kolor);. Po użyciu tej funkcji należy uruchomić funkcję img.updatePixels(); żeby zaktualizować wartość bufora w pamięci.

Jako ostatni krok tego zadania należy zaimplementować wydarzenie function mouseDragged(). Wewnątrz tego wydarzenia należy najpierw stworzyć wektor metodą makeVector, podając do niej współrzędne mouseX i mouseY, a potem należy przekazać otrzymany wektor do funkcji drawVector razem z obrazem imgA (na razie tylko tego obrazu będziemy używać).

Po pomyślnym wykonaniu tego zadania powinieneś móc rysować proste kształty na obrazie imgA.

Macierze przekształceń

(zadanie na ocenę 3.5)

Po wykonaniu poprzedniego zadania można mieć wrażenie, że tworzenie wektorów jest trochę bez sensu, ponieważ można od razu ustawić piksel na obrazie. Niemniej jednak jest pewien dobry powód, dla którego wprowadzamy pojęcie wektora. Okazuje się, że wszystkie wspomniane poprzednio operacje przekształcania można zdefiniować matematycznie jako operacje mnożenia wektora z macierzą. Wektor, tak jak wyżej, ma reprezentować współrzędne obiektu, jaki podlega przekształceniom, a macierz samo przekształcenie.

Zanim jednak przejdziemy do stosowania tych przekształceń, zdefiniujmy najpierw kilka podstawowych macierzy, zaczynając od najprostszej - macierzy jednostkowej (ang. identity matrix):

Macierz ta ma prosty efekt, że nie dokonuje żadnego przekształcenia - jest swoistą jedynką w przestrzeni macierzy. Wydawałoby się, że powinna się ona składać z samych zer albo jedynek, ale jak się okaże, ma ona wygląd taki jak powyżej.

Kolejną, często stosowaną macierzą jest macierz przesunięcia lub translacji:

Podstawiając w miejsce t_xi t_y wartości przesunięcia (o ile ma zostać przesunięty obiekt), macierz ta dokona tego przekształcenia po wykonaniu operacji mnożenia z wektorem reprezentującym obiekt.

Analogicznie możemy zdefiniować macierz skalowania:

Trochę bardziej skomplikowana jest macierz obrotu:

Litera Θ reprezentuje tutaj kąt, o jaki należy dokonać obrotu. Warto tutaj jednak pamiętać o tym, że w JavaScript (jak i większości języków programowania) funkcje trygonometryczne przyjmują wartości w radianach a nie w stopniach. Chcąc zatem dokonać obrotu o 30 stopni, trzeba do wartości Θ wpisać liczbę ~0.5236. Żeby dokonać konwersji kąta ze stopni na radiany wystarczy podzielić najpierw stopnie przez wartość 180, a potem pomnożyć otrzymaną wartość przez π (w JavaScripcie Math.PI).

Na sam koniec warto jeszcze wspomnieć o ostatnim przekształceniu, trochę rzadziej stosowanym niż powyższe, tj. przekształceniu pochylania (ang. shear):

Do zaliczenia tego zadania, należy zaimplementować funkcje tworzące wszystkie powyższe macierze według specyfikacji (analogicznie do makeVector, np. makeIdentity albo makeScale). Na razie nie zobaczymy ich w akcji, ale możesz użyć polecenia console.log(...); żeby je wypisać do konsoli. Wypisywanie to możesz umieścić na zewnątrz jakiejkolwiek funkcji, pod koniec skryptu (zostanie wtedy wykonane tylko raz).

Zastosowanie macierzy przekształceń

(zadanie na ocenę 4)

Mając już stworzony wektor i macierze przekształceń, czas zastosować wybrane przekształcenia w naszej aplikacji.

Żeby zastosować przekształcenie, należy dokonać operacji mnożenia macierzy z wektorem używając wzoru poniżej:

Literka V w powyższym wzorze to długość wektora v, a W długość wektora w. Tym samym rozmiar macierzy musi być VxW.

Zrób funkcję do wykonywania powyższej operacji mnożenia wektora z macierzą, a potem zmodyfikuj funkcję mouseDragged tak, żeby po narysowaniu piksela na pierwszym obrazie dokonać mnożenia jego wektora z jedną z powyższych macierzy, a potem narysować otrzymany wektor na obrazku imgB.

Po zaimplementowaniu tej części ćwiczenia, powinieneś móc narysować obraz i naciskając spację zobaczyć, jak on wygląda po dokonaniu na nim transformaty. Zaobserwuj, jak wyglądają poszczególne przekształcenia. Na czym polega przesunięcie, na czym obrót a na czym skalowanie? Zrób macierze dla wszystkich przekształceń i zakomentuj wszystkie oprócz jednego, żeby pokazać prowadzącemu dowolne z nich.

(Mała rada: żeby ułatwić sobie debugowanie powyższej funkcji, pamiętaj, że wynikiem operacji musi być poprawny wektor, czyli ostatnia jego wartość musi zawsze wynosić 1. Oprócz tego, pamiętaj, że mnożenie dowolnego wektora z macierzą jednostkową powinno dać ten sam wektor.)

Łączenie przekształceń

(zadanie na ocenę 4.5)

W tej chwili jesteśmy w stanie dokonywać dowolnych przekształceń, ale nadal operacja ta nie jest bardziej wydajna od bezpośredniej modyfikacji wartości współrzędnych. Chcąc wykonać kilka przekształceń po kolei, możemy dokonać najpierw jednego, potem na jego wyniku dokonać kolejnych i tak dalej:

Okazuje się jednak, że jest to matematycznie identyczne do wykonania operacji mnożenia pierwszego wektora z iloczynem wszystkich macierzy razem:

Co więcej, ponieważ macierze przekształceń są z reguły znane na samym początku i nie zmieniają się w trakcie rysowania, to wszystko co jest w nawiasie w powyższym wzorze, można wyliczyć tylko raz i przez to przyspieszyć działanie algorytmów rysowania o rząd wielkości (np. ze złożoności O(n²) możemy go przyspieszyć do złożoności O(n)).

Do zaliczenia tego zadania, należy zaimplementować analogiczną funkcję do mnożenia macierzy z macierzą:

W powyższym wzorze macierz wynikowa O ma wymiary AxB, macierz M ma wymiary AxC, a macierz N ma wymiary CxB.

Do zaliczenia ćwiczenia zmodyfikuj kod w mouseDragged, żeby oprócz dokonywania pojedynczych przekształceń, dokonać sekwencji kilku. Zauważ, że kolejność przekształceń ma znaczenie! Inaczej mówiąc, operacja mnożenia macierzy nie jest przemienna (tak jak w przypadku pojedynczych liczb). Zrób przykład, gdzie na imgA mamy jedną sekwencję przekształceń (np. przesunięcie + obrót + skalowanie), a na imgB mamy inną sekwencję używającą tych samych przekształceń, ale w innej kolejności (np. skalowanie + przesunięcie + obrót).

(Mała rada: tak jak poprzednio, warto zrobić kilka przykładów do debugowania powyższego kodu. Na pewno warto sprawdzić mnożenie macierzy z macierzą jednostkową, w wyniku którego powinniśmy otrzymać tę samą macierz.)

Interaktywna aplikacja

(zadanie na ocenę 5)

Na najwyższą ocenę należy przygotować aplikacje pozwalającą na rysowanie na imgA i wykonanie przekształceń otrzymanego obrazu w imgB, z elementami interfejsu użytkownika.

pokazywać cały czas zawartość macierzy przekształceń, jaka jest używana w danym momencie
umożliwić użytkownikowi dokonanie resetu macierzy na macierz jednostkową
umożliwić użytkownikowi zastosowanie przekształcenia (obrotu, skalowania, translacji, pochylenia), dokonując wymnożenie bieżącej macierzy przez wybraną macierz przekształceń
umożliwić użytkownikowi zmiany poszczególnych wartości przekształceń.

Report abuse