GKIW Moduł 4 - Przekształcenia geometryczne

Wykład

---

---

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 $P={\left[\begin{array}{cc}{x}_p& y_p\\ \end{array}\right]}^T$ opisuje położenie punktu na płaszczyźnie. Najprostszym rozwiązaniem byłoby przyjęcie, że macierz $M(2\times 2)$ opisuje przekształcenie punktu $P$, na $P^{\prime }$, i że $P^{\prime }=M\cdot P$

---

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.

---

Niech $M_{T1}=\left[\begin{array}{cc}a& b\\ c& d\\ \end{array}\right]$. Niech wektor $\left[\begin{array}{cc}{T}_X& T_Y\\ \end{array}\right]$ opisuje translację punktu na płaszczyźnie. Czy można znaleźć takie a, b, c, d, aby $\left[\begin{array}{c}{x}_p+T_X\\ y_p+T_Y\\ \end{array}\right]=\left[\begin{array}{cc}a& b\\ c& d\\ \end{array}\right]\cdot \left[\begin{array}{c}{x}_p\\ y_p\\ \end{array}\right]$ dla $T_X\ne 0$ i $T_Y\ne 0$ . Widać że nie jest to możliwe dla współrzędnych dowolnego punktu. Na dodatek punkt $P={\left[\begin{array}{cc}0& 0\\ \end{array}\right]}^T$ byłby punktem stałym takiego przekształcenia. Jak zatem opisać translację na płaszczyźnie? Operację tę można opisać macierzą $M=\left[\begin{array}{ccc}1& 0& T_X\\ 0& 1& T_Y\\ 0& 0& 1\end{array}\right]$ Między współrzędnymi zachodzi następujący związek: $\left[\begin{array}{c}{X}_p^{\text{'}}\\ Y_p^{\text{'}}\\ 1\end{array}\right]=\left[\begin{array}{ccc}1& 0& T_X\\ 0& 1& T_Y\\ 0& 0& 1\end{array}\right]\cdot \left[\begin{array}{c}{X}_p\\ Y_p\\ 1\end{array}\right]$ i jest to równoważne opisowi translacji o wektor w postaci układu równań: $\{\begin{array}{l}{x}_p^{\text{'}}=x_p+T_X\\ y_p^{\text{'}}=y_p+T_Y\end{array}$ Tak wykonana operacja wymaga użycia współrzędnych jednorodnych.

---

Niech $x_p,y_p,z_p$,, 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 $x_p,y_p,z_p$, opisują położenie punktu, to odpowiada temu wektor $P={\left[\begin{array}{cccc}{x}_p& y_p& z_p& 1\\ \end{array}\right]}^T$ we współrzędnych jednorodnych znormalizowanych. We współrzędnych nieznormalizowanych wektor ten miałby postać $P={\left[\begin{array}{cccc}\stackrel{\sim }{x_p}& \stackrel{\sim }{y_p}& \stackrel{\sim }{z_p}& \stackrel{\sim }{N}\\ \end{array}\right]}^T$ dla $\stackrel{\sim }{N}\ne 0$ . Przy czym $x_p=\frac{\stackrel{\sim }{x_p}}{\stackrel{\sim }{N}}$ , $y_p=\frac{\stackrel{\sim }{y_p}}{\stackrel{\sim }{N}}$ , $z_p=\frac{\stackrel{\sim }{z_p}}{\stackrel{\sim }{N}}$ , 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 $z=h_z\ne 0$ ). 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 $z=1$. 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..

---

Niech położenie punktu o współrzędnych $(x_p,y_p)$ na płaszczyźnie reprezentuje wektor P : $P=\left[\begin{array}{c}{x}_P\\ y_P\\ 1\end{array}\right]$ Jeśli macierz M opisuje pewną transformację geometryczną to operację tę można opisać następująco: $P^{\prime }=M\cdot P$ czyli: $\left[\begin{array}{c}{x}_P^{\text{'}}\\ y_P^{\text{'}}\\ 1\end{array}\right]=M\cdot \left[\begin{array}{c}{x}_P\\ y_P\\ 1\end{array}\right]$ 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.: $\{\begin{array}{l}{x}_P^{\text{'}}=f_{XM}(x_P,y_P,z_P)\\ y_P^{\text{'}}=f_{YM}(x_P,y_P,z_P)\end{array}$ 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.: ${P^{\prime }}^T=P^T\cdot M^T$ 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.

---

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.

---

---

---

---

---

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.

---

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 $(x_p,y_p,z_p)$ w przestrzeni trójwymiarowej reprezentuje wektor P : $\left[\begin{array}{c}{x}_P\\ y_P\\ z_P\\ 1\end{array}\right]$ Jeśli macierz M opisuje pewną transformację geometryczną w przestrzeni 3D, to operację tę można opisać następująco: $P^{\prime }=M\cdot P$ czyli: $\left[\begin{array}{c}{x}_P^{\text{'}}\\ y_P^{\text{'}}\\ z_P^{\text{'}}\\ 1\end{array}\right]=M\cdot \left[\begin{array}{c}{x}_P\\ y_P\\ z_P\\ 1\end{array}\right]$ 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

---

---

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.

---

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

---

---

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.

---

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

---

---

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.

---

Obiekt na rysunku został obrócony o kat $-45^{\circ }$ wokół osi OX.

---

Obiekt na rysunku został obrócony o kat $45^{\circ }$ wokół osi OY

---

Obiekt na rysunku został obrócony o kat $45^{\circ }$ wokół osi OZ.

---

Warto zwrócić uwagę na fakt, że jeśli $S=S_X=S_Y=S_Z\ne 0$ to skalowanie można opisać macierzą: $M_{S1}=\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& \frac{1}{S}\end{array}\right]$ wtedy $M_{S1}\cdot \left[\begin{array}{c}{x}_P\\ y_P\\ z_P\\ 1\end{array}\right]=\left[\begin{array}{c}{x}_P\\ y_P\\ z_P\\ \frac{1}{S}\end{array}\right]$ 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 $\left[\begin{array}{c}{x}_P\\ y_P\\ z_P\\ \frac{1}{S}\end{array}\right]⟹\left[\begin{array}{c}S\cdot x_P\\ S\cdot y_P\\ S\cdot z_P\\ 1\end{array}\right]$ co odpowiada skalowaniu ze współczynnikiem S.

---

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.

---

Składanie przekształceń i operowanie macierzą wynikową pozwala realizować operacje efektywniej. Jeśli zatem $M_C$, opisuje całkowite przekształcenie będące wynikiem złożenia przekształceń elementarnych $M_1,M_2,M_3\cdots M_N$, (w takiej kolejności) to : $M_C=M_N\cdot ...\cdot M_3\cdot M_2\cdot M_1$, 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.

---

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: Przesunięcie obiektu, aby punkt odniesienia znalazł się w początku układu współrzędnych. Skalowanie obiektu. Przesunięcie odwrotne do operacji 1.

---

Jeśli macierz $M$, opisuje pewną transformację geometryczną, przekształcenie współrzędnych jest opisane równaniem $P^{\prime }=M\cdot P$ i jeśli istnieje przekształcenie odwrotne opisane macierzą $M^{-1}$, to $P=M^{-1}\cdot P^{\prime }$ 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 $M_C$, opisuje całkowite przekształcenie będące wynikiem złożenia przekształceń elementarnych $M_C=M_N\cdot ...\cdot M_3\cdot M_2\cdot M_1$, i jeśli każde z nich jest odwracalne to : $M_C^{-1}=M_1^{-1}\cdot M_2^{-1}\cdot M_3^{-1}\cdot ...\cdot M_N^{-1}$,

---

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 $l$ 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 $\phi$, wokół zadanej osi zrealizować bezpośrednio jako obrót o kąt $\phi$, wokół osi układu. Zadanie można rozwiązać na wiele sposobów. Przyjęto następujący zestaw operacji: Przesunięcie, aby punkt $T_1$, znalazł się w początku układu współrzędnych. Obrót wokół osi OX. Obrót wokół osi OY. Obroty (etap 2. i 3. ) zapewniają, że zadana oś obrotu (prosta $l$) pokryje się (z uwzględnieniem zwrotów) z osią OX układu współrzędnych. Realizacja zadanego obrotu o kąt $\phi$, wokół osi OX. Obrót będący operacją odwrotną do operacji 3. Obrót będący operacją odwrotną do operacji 2. Przesunięcie odwrotne do przesunięcia 1.

---

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.

---

Po zrealizowaniu obrotu wokół OX prosta $l$ znalazła się na płaszczyźnie XOZ.

---

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

---

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

---

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.

---

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.

---

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.

---

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ń.

---

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.

---

Kwaterniony (quaternions) są czterowymiarowym rozwinięciem liczb zespolonych. Zostały zaproponowane przez Williama Hamiltona w 1953 roku. $i^2=j^2=k^2=ijk=-1$ 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.

---

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ą

---

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 $\overrightarrow{u}$ reprezentujący oś obrotu w przestrzeni. Biorąc pod uwagę kwaternion jednostkowy $q_u$, związany z tym wektorem jednostkowym, można wyznaczyć kwaternion $Q_{Pu}$, zgodnie z zaproponowanym wzorem. Kwaternion ten reprezentuje punkt będący obrazem w obrocie wokół osi wyznaczonej przez wektor $\overrightarrow{u}$ o kąt $\phi$, . 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

---