GKIW Moduł 4 - Przekształcenia geometryczne

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Wykład

GKIW M4 Slajd intro.png

GKIW M4 Slajd 0.png

GKIW M4 Slajd1.png
Współczesna grafika komputerowa operuje na milionach elementów (punktów, trójkątów). Przy tak dużej liczbie zachodzi konieczność opisania operacji geometrycznych w taki sposób, aby ich wykonanie było z jednej strony efektywne, a z drugiej, aby opis był prosty i ujednolicony. Takie warunki spełnia opis macierzowy.

Niech opisuje położenie punktu na płaszczyźnie. Najprostszym rozwiązaniem byłoby przyjęcie, że macierz opisuje przekształcenie punktu na i że


GKIW M4 Slajd2.png
Można zastanowić się nad tym, czy takie podejście do problemu wystarczy do opisu prostych operacji geometrycznych.

Rozpatrzmy zestaw przekształceń na płaszczyźnie: obrót, skalowanie, przesunięcie (translację).

Można zaproponować macierz 2x2, która, opisuje obrót punktu wokół początku układu współrzędnych.

Analogiczny opis można zaproponować dla operacji skalowania.


GKIW M4 Slajd3.png
Niech . Niech wektor opisuje translację punktu na płaszczyźnie.

Czy można znaleźć takie a, b, c, d, aby dla i .

Widać że nie jest to możliwe dla współrzędnych dowolnego punktu. Na dodatek punkt byłby punktem stałym takiego przekształcenia.

Jak zatem opisać translację na płaszczyźnie?

Operację tę można opisać macierzą

Między współrzędnymi zachodzi następujący związek:

i jest to równoważne opisowi translacji o wektor w postaci układu równań:

Tak wykonana operacja wymaga użycia współrzędnych jednorodnych.


GKIW M4 Slajd4.png
Niech , opisują położenie punktu w trójwymiarowym kartezjańskim układzie współrzędnych. W grafice komputerowej do opisu położenia oraz opisu operacji (transformacji geometrycznych), którym punkty będą podlegały, jest używany układ współrzędnych jednorodnych znormalizowanych. Dzięki temu wszystkie stosowane transformacje geometryczne mogą być opisane w identyczny sposób za pomocą mnożenia macierzowego. Jeśli współrzędne opisują położenie punktu, to odpowiada temu wektor we współrzędnych jednorodnych znormalizowanych. We współrzędnych nieznormalizowanych wektor ten miałby postać dla . Przy czym , , , co nosi nazwę operacji normalizacji.

Zastosowanie w przypadku przesunięcia na płaszczyźnie współrzędnych jednorodnych można sobie wyobrazić jako umieszczenie płaszczyzny, na której pracujemy, w trójwymiarowym układzie współrzędnych, w taki sposób, aby nie przechodziła ona przez początek układu (tzn. dla ). Wtedy analogiczne opisanie operacji translacji na płaszczyźnie (ale już jako macierz 3x3) da poprawne rozwiązanie, gdyż punkt stały – początek układu współrzędnych jest poza płaszczyzną, na której jest wykonywana operacja. Jednocześnie, aby wynik operacji znajdował się na tej samej płaszczyźnie, najprościej operować na współrzędnych znormalizowanych, czyli pracować na płaszczyźnie .

Gdyby operacja normalizacji nie została wykonana mogłoby się zdarzyć, że wynik operacji leżałby na innej płaszczyźnie – a to nie miałoby sensu

A zatem zawsze jeśli wynik operacji będzie nieznormalizowany zostanie przeprowadzona operacja normalizacji.

Analogicznie dla przekształceń trójwymiarowych można wyobrazić sobie umieszczenie przestrzeni 3D i trójwymiarowego układu współrzędnych wewnątrz układu czterowymiarowego, tak aby nie zawierał on początku układu współrzędnych..


GKIW M4 Slajd5.png
Niech położenie punktu o współrzędnych na płaszczyźnie reprezentuje wektor P :

Jeśli macierz M opisuje pewną transformację geometryczną to operację tę można opisać następująco:

czyli:

gdzie P' opisuje położenie punktu po przekształceniu. Oczywiście, jeśli wynik mnożenia macierzy jest nieznormalizowany, to należy dokonać normalizacji.

W grafice komputerowej operacje na płaszczyźnie opisuje macierz 3x3.

Można powiedzieć, że macierz M definiuje liniowe funkcje określające każdą ze współrzędnych punktu tzn.:

Wykorzystując rachunek macierzowy przekształcenia punktu można opisać również za pomocą prawostronnego mnożenia macierzy. Wtedy, dla przyjętych wyżej danych operacja wyglądałaby tak.:

Jak widać tę samą operację można zapisać jako mnożenie lewostronne lub prawostronne przez macierz przekształcenia.

Tak naprawdę trudno byłoby wskazać uzasadnienie dla wyboru jednej lub drugiej formy zapisu. W książkach dotyczących grafiki komputerowej w ostatnich latach częściej stosowany jest zapis lewostronnego mnożenia, chociaż są autorzy, którzy nadal konsekwentnie trzymają się mnożenia prawostronnego. Natomiast sposób używania zależy od przyzwyczajeń i upodobań użytkownika. Jedno jest jednak bardzo istotne – konsekwencja. Nie można mieszać postaci opisu.


GKIW M4 Slajd6.png
Można zaproponować pewien minimalny zestaw operacji: symetrie (względem osi układu współrzędnych i środkowa), obroty, przesunięcie (translacja), skalowanie oraz pochylenie.

GKIW M4 Slajd7.png

GKIW M4 Slajd8 v4.png

GKIW M4 Slajd9.png

GKIW M4 Slajd10.png

GKIW M4 Slajd11.png
Pochylenie jest rzadziej stosowanym przekształceniem. Daje możliwość zniekształcenia figury. Nie zachowuje odległości punktów. Figura i jej obraz w tym przekształceniu nie są podobne.

GKIW M4 Slajd12.png
Możliwe są dwa ustawienia osi trójwymiarowego układu współrzędnych. Najczęściej do opisu położenia obiektów na scenie (w przestrzeni obiektu) stosowany jest układ prawoskrętny. Natomiast w operacjach związanych z rzutowaniem układ lewoskrętny. Wybór układu współrzędnych dla operacji rzutowania jest konsekwencją naturalnego rozumienia odległości obiektu od obserwatora. Jeśli osie OX i OY zdefiniują układ współrzędnych na rzutni (utożsamianej z płaszczyzną XOY) (pozioma oś OX skierowana w prawo i pionowa oś OY skierowana do góry), to kierunek wzrostu odległości od obserwatora wskaże oś OZ. Tak zdefiniowany układ współrzędnych będzie układem lewoskrętnym.

Niech położenie punktu o współrzędnych w przestrzeni trójwymiarowej reprezentuje wektor P :

Jeśli macierz M opisuje pewną transformację geometryczną w przestrzeni 3D, to operację tę można opisać następująco:

czyli:

gdzie P' opisuje położenie punktu po przekształceniu. Oczywiście, jeśli wynik mnożenia macierzy jest nieznormalizowany, to należy dokonać normalizacji.

Operacje w przestrzeni 3D opisuje macierz 4x4 w przestrzeni 4D


GKIW M4 Slajd13.png

GKIW M4 Slajd14.png
Macierze opisujące symetrie płaszczyznowe względem pozostałych dwóch płaszczyzn (XOY i YOZ) mają analogiczną postać ze zmienionym znakiem przy 1 w odpowiedniej kolumnie.

GKIW M4 Slajd15.png
Podobnie macierze opisujące symetrie osiowe względem pozostałych dwóch osi (OY i OZ) mają analogiczną postać ze zmienionymi znakami.

GKIW M4 Slajd16.png

GKIW M4 Slajd17.png
Jeżeli założyliśmy, że położenie obiektów sceny będzie opisywane w układzie prawoskrętnym, natomiast rzutowanie będzie rozpatrywane w układzie lewoskrętnym, to współrzędne tego samego punktu w obu układach będą się różniły znakiem przy współrzędnej z. Przeliczenie współrzędnych między układami zapewnia macierz symetrii płaszczyznowej względem XOY.

GKIW M4 Slajd18 v4.png
Przesunięcie w układzie trójwymiarowym odbywa się w sposób analogiczny do przesunięcia na płaszczyźnie.

GKIW M4 Slajd19 v4.png

GKIW M4 Slajd20.png
W układzie współrzędnych kartezjańskich trójwymiarowych zdefiniowanie obrotów wokół osi układu wymaga przyjęcia reguł uznawania obrotów za dodatnie. Najczęściej przyjmuje się konwencję, według której dodatnie obroty są zdefiniowane zgodnie z rysunkiem.

GKIW M4 Slajd21.png
Obiekt na rysunku został obrócony o kat wokół osi OX.

GKIW M4 Slajd22.png
Obiekt na rysunku został obrócony o kat wokół osi OY

GKIW M4 Slajd23.png
Obiekt na rysunku został obrócony o kat wokół osi OZ.

GKIW M4 Slajd24.png
Warto zwrócić uwagę na fakt, że jeśli to skalowanie można opisać macierzą:

wtedy

Ale wynik tej operacji nie jest znormalizowany. Zgodnie z przyjętymi wcześniej zasadami posługiwania się współrzędnymi jednorodnymi taka operacja jest w tym przypadku niezbędna.

Zatem co odpowiada skalowaniu ze współczynnikiem S.


GKIW M4 Slajd25.png
Rysunek podaje macierz pochylenia trójwymiarowego dla z stałego, oraz przykład zniekształcenia sześcianu przez takie przekształcenie. Analogicznie można zaproponować przekształcenia i macierze je opisujące dla pochylenia przy stałym x oraz przy stałym y.

GKIW M4 Slajd26.png
Składanie przekształceń i operowanie macierzą wynikową pozwala realizować operacje efektywniej.

Jeśli zatem opisuje całkowite przekształcenie będące wynikiem złożenia przekształceń elementarnych (w takiej kolejności) to :

Oczywiście mnożenie macierzy i składanie przekształceń geometrycznych, jest operacją łączną ale nie jest operacją przemienną – złożenie najpierw translacji a potem obrotu jest innym przekształceniem niż złożenie najpierw obrotu a potem translacji.


GKIW M4 Slajd27.png
Często pojawiającym się problemem w próbach implementacji przekształceń geometrycznych w grafice jest problem punktu odniesienia operacji.

Skalowanie jest operacją zmieniającą proporcje wymiarów względem początku układu współrzędnych. Punkt [0,0,0] jest punktem stałym tego przekształcenia. Wyobraźmy sobie dwukrotne powiększenie pewnego obiektu (np. powiększenie domu jak na rysunku). Powiększenie dwukrotne oznacza nie tylko, że zwiększą się wymiary obiektu. Oznacza również, że każdy punkt obiektu zwiększy dwukrotnie odległość od początku układu współrzędnych. A przecież obiekt jest „osadzony” w pewnych realiach sceny – np. wejście do domu jest w określonym miejscu. Prosta realizacja skalowania prowadzi do pewnych konfliktów. Aby tego uniknąć należy wybrać punkt obiektu, który powinien zachować współrzędne – punkt odniesienia. A następnie zrealizować skalowanie względem tego punktu odniesienia.

To jednak wymaga złożenia operacji:

  1. Przesunięcie obiektu, aby punkt odniesienia znalazł się w początku układu współrzędnych.
  2. Skalowanie obiektu.
  3. Przesunięcie odwrotne do operacji 1.

GKIW M4 Slajd28.png
Jeśli macierz opisuje pewną transformację geometryczną, przekształcenie współrzędnych jest opisane równaniem i jeśli istnieje przekształcenie odwrotne opisane macierzą to

Oczywiście nie zawsze konieczne jest wyznaczanie macierzy odwrotnej, np. dla translacji o dany wektor przekształceniem odwrotnym będzie translacja o wektor przeciwny, dla obrotu o zadany kąt obrót wokół tej samej osi o kąt przeciwny itp.

Ponieważ symetrie, translacja, obroty i skalowanie opisane odpowiednimi macierzami są operacjami odwracalnymi, to w bardzo prosty sposób można pokazać, że dowolna operacja będąca złożeniem dowolnego zestawu tych operacji, jest też operacją odwracalną.

Jeśli zatem opisuje całkowite przekształcenie będące wynikiem złożenia przekształceń elementarnych i jeśli każde z nich jest odwracalne to :


GKIW M4 Slajd29.png
Zestaw podstawowych operacji obejmował obroty, ale tylko wokół osi układu współrzędnych. Obrót wokół dowolnej osi musi być zatem zrealizowany jako złożenie operacji. Można przyjąć założenie, że generalnie celem operacji wstępnych jest takie przekształcenie przestrzeni, aby zadana oś obrotu (prosta na rysunku) pokryła się z wybraną osią układu współrzędnych. Przy czym przyjęty zwrot osi obrotu powinien być zgodny ze zwrotem osi okładu. Takie warunki pozwolą obrót o kąt wokół zadanej osi zrealizować bezpośrednio jako obrót o kąt wokół osi układu.

Zadanie można rozwiązać na wiele sposobów. Przyjęto następujący zestaw operacji:

  1. Przesunięcie, aby punkt znalazł się w początku układu współrzędnych.
  2. Obrót wokół osi OX.
  3. Obrót wokół osi OY. Obroty (etap 2. i 3. ) zapewniają, że zadana oś obrotu (prosta ) pokryje się (z uwzględnieniem zwrotów) z osią OX układu współrzędnych.
  4. Realizacja zadanego obrotu o kąt wokół osi OX.
  5. Obrót będący operacją odwrotną do operacji 3.
  6. Obrót będący operacją odwrotną do operacji 2.
  7. Przesunięcie odwrotne do przesunięcia 1.

GKIW M4 Slajd30.png
Rysunek pokazuje wynik pierwszej operacji – przesunięcia. Zadana oś obrotu zawiera teraz przekątną prostopadłościanu o bokach A, B, C. Ułatwi to definicje kątów obrotu.

GKIW M4 Slajd31.png
Po zrealizowaniu obrotu wokół OX prosta znalazła się na płaszczyźnie XOZ.

GKIW M4 Slajd32.png
Po zrealizowaniu obrotu wokół OY prosta pokryje się z osią OX układu współrzędnych. Jednocześnie odpowiednio dobrane operacje zapewniły zgodność zwrotów obu osi.

GKIW M4 Slajd33.png
Teraz można wreszcie wykonać obrót o kąt wokół prostej co, dzięki odpowiednim operacjom wstępnym, odpowiada obrotowi o kąt wokół osi OX układu współrzędnych.

GKIW M4 Slajd34.png
Następnymi etapami będą operacje przeciwne realizowane w odwrotnej kolejności.

Macierz przekształcenia całkowitego jest iloczynem macierzy opisujących przekształcenia odpowiadające kolejnym przedstawionym etapom.


GKIW M4 Slajd35.png
Problem dokładności obliczeń przy wykorzystaniu komputerów jest znany od kiedy istnieją komputery. Wiadomo, że liczby w komputerze są reprezentowane przez skończony ciąg cyfr. W przypadku liczb całkowitych stosowana jest reprezentacja stałopozycyjna i i jeśli rozpatrzymy arytmetykę binarną, to liczbie takiej odpowiada rozwinięcie dwójkowe o określonej długości słowa. Liczby rzeczywiste reprezentowane są zmiennopozycyjnie w postaci cechy i mantysy. Stosowanie określonej długości słowa do reprezentacji mantysy powoduje powstanie dokładności danej arytmetyki. Oznacza to, że reprezentacja liczb rzeczywistych obarczona jest zawsze pewnym błędem wynikającym z tej arytmetyki. Przeprowadzanie operacji graficznych wymaga często wielokrotnych obliczeń. Błędy reprezentacji (dokładność arytmetyki) mogą w widoczny sposób wpływać na efekt (graficzny !) obliczeń. Stosowane algorytmy powinny być tak realizowane, aby, o ile jest to możliwe, minimalizować te błędy.

Rozpatrzmy przykład zegara, dla którego należy wyznaczyć położenie wskazówek.


GKIW M4 Slajd36 v4.png
Najprostszym rozwiązaniem jest algorytm iteracyjny powiększający w każdym kroku bieżący kąt o zadany przyrost. Niestety takie rozwiązanie prowadzi do powstania widocznych na tarczy zegara błędów już po kilkudziesięciu godzinach.

GKIW M4 Slajd37.png
Jeśli przeanalizujemy algorytm naiwny, to okaże się, że wraz z powiększaniem wartości kąta dodajemy błędy. Błąd się nakłada wraz z postępowaniem obliczeń.

GKIW M4 Slajd38 v4.png
Zadanie może być tak zrealizowane, aby błąd nie powiększał się.

Realizując algorytm graficzny należy zawsze zwrócić uwagę na dokładność obliczeń numerycznych. Aby błąd zaokrągleń nie wpłynął na efekt obliczeń i nie zniweczył naszej pracy psując efekt końcowy.


GKIW M4 Slajd39.png
Kwaterniony (quaternions) są czterowymiarowym rozwinięciem liczb zespolonych. Zostały zaproponowane przez Williama Hamiltona w 1953 roku.

Dla dowolnego kwaternionu istnieje kwaternion przeciwny.

Dla dowolnego kwaternionu różnego od zera istnieje kwaternion odwrotny.

Suma dwóch kwaternionów jest kwaternionem.

Iloczyn dwóch kwaternionów jest kwaternionem.


GKIW M4 Slajd40.png
Suma i iloczyn są zdefiniowane tak jak na rysunku.

Dodawanie kwaternionów jest operacją łączną i przemienną.

Mnożenie kwaternionów jest operacją łączną i nie jest operacją przemienną


GKIW M4 Slajd41.png
Kwaterniony są wykorzystywane w grafice komputerowej w związku z jedną operacją w przestrzeni trójwymiarowej: z obrotem punktu wokół dowolnie zdefiniowanej osi. Aby skorzystać z tej możliwości należy zdefiniować reprezentację punktu w postaci kwaternionu oraz jednostkowy wektor reprezentujący oś obrotu w przestrzeni.

Biorąc pod uwagę kwaternion jednostkowy związany z tym wektorem jednostkowym, można wyznaczyć kwaternion zgodnie z zaproponowanym wzorem. Kwaternion ten reprezentuje punkt będący obrazem w obrocie wokół osi wyznaczonej przez wektor o kąt .

Porównując to rozwiązanie z zadaniem opisanym wcześniej widać prostotę operacji obrotu wykonywanej z wykorzystaniem kwaternionów.

Większość obrotów realizowanych w grach komputerowych jest wykonywana w taki sposób.


Literatura

GKIW M4 Slajd42.png