Nagłówek:
Math.hpp
Elementy modułu:
Moduł Math
To jest zaanwasowana biblioteka matematyczna. Definiuje typu takie jak wektor czy macierz. Elementy matematyczne nie wymagające tych typów, a jedynie operujące na zwykłych liczbach, znajdziesz w module Base. Math to największy z modułów CommonLib. Zawarte w nim elementy przeznaczone są głównie do programowania gier. Math dubluje większość funkcjonalności biblioteki D3DX z DirectX w zakresie matematyki, a także implementuje dużo innych funkcji wyższego poziomu, jak kolizje między różnymi obiektami geometrycznymi.
- Nastawiona na maksymalną wydajność.
- Jako liczby zmiennoprzecinkowe używa typu float.
- Przenośna na Windows i Linux (jak cały CommonLib).
- W systemie Windows integruje się z DirectX (D3DX) używając jego typów, ale go nie wymaga - w przypadku jego braku definiuje własne.
- Korzysta tylko z modułu Base.
- Nie używa wyjątków modułu Error.
- Możliwości: Nie wszystko to co ma D3DX, ale duża część z tego. Wszystko, co często używane, ważne i potrzebne. Dodatkowo zaawansowane obliczenia typu kolizje między różnego rodzaju obiektami.
- Nastawiona bardziej nia współpracę z DirectX niż OpenGL - układ współrzędnych lewoskrętny, macierze w porządku wierszowym, kolory w formacie A8R8G8B8 itp.
- W funkcjach generujących czy liczących coś wszelkie struktury bardziej złożone niż pojedyncza liczba zwracane są przez pierwszy parametr wskaźnikowy, a nie przez zwrócenie wartości.
- Każdy kolor reprezentowany jest przez składowe ARGB, kanał alfa jest tak samo ważny i nie jest nigdzie pomijany ani domyślnie inicjalizowany. Domyślny format koloru to A8R8G8B8 (kompatybilny z uint4).
- DECYZJA: Jak zrobić operacje, np.: 1.
dot3(v1, v2) 2. VEC3::dot(v1, v2) 3. v1.dot3(v2) DECYZJA: 1 BO:
- Ta opcja jest najkrótsza
- Zapis 3 jest brzydki i nienaturalny, bo niesymetrynczy
- Zapis 2 jest dłuższy i niczego nie polepsza, bo nawet kiedy będzie konflikt w przestrzeni globalnej to funkcja się przeładuje albo się ją inaczej nazwie.
- DECYZJA: Jak zrobić inicjalizację struktur, np.: 1.
PLANE plane1(v1, v2, v3); 2. PLANE plane1; CreatePlane(&plane1, v1, v2, v3); 3. PLANE plane1; plane1.Fill(v1, v2, v3); DECYZJA: 2, konstruktor tylko do bezpośredniej inicjalizacji pól bez konwersji. BO:
- Opcja 1 sama nie wystarczy, czasem chce się zmienić, wtedy trzebaby dodać 2 lub 3.
- Jest zgodna z konwencją funkcji wypełniających, konwertujących itp. Rozróżnienie między inicjalizacją a konwersją jest płynne.
- Nie ma kolizji odcinka z obiektami. Dlaczego? Bo można skorzystać z kolizji promienia i sprawdzić czy otrzymane t nie przekracza długości odcinka (0..1 czy też 0..Długość).
Podstawą modułu matematycznego są różne obiekty geometryczne, z których większość posiada swoją reprezentację jako osobne struktury. Dla każdej z tych struktur zdefiniowany jest szereg przeładowanych operatorów, metod oraz funkcji globalnych, które nie są tutaj szczegółowo opisane. Każdy z nich daje się również skonwertować do/z łańcucha znaków za pomocą ujednoliconego mechanizmu SthToStr i StrToSth.
- Punkt 2D opisany liczbami całkowitymi reprezentuje struktura common::POINT_. Odpowiada ona typowi POINT z WinAPI i złożona jest z pól
int x, y. - Punkt lub wektor 2-, 3- i 4-wymiarowy opisany liczbami zmiennoprzecinkowymi reprezentują struktury odpowiednio common::VEC2, common::VEC3 i common::VEC4. Posiadają one pola
float x, y oraz dodatkowo z i w. Jeśli zdefiniowane jest makro USE_DIRECTX, są to aliasy do typów z D3DX: D3DXVECTOR2, D3DXVECTOR3 i D3DXVECTOR4. Jeśli nie, moduł dostarcza własnej implementacji o zbliżonej funkcjonalności. Zdefiniowane jest wiele funkcji do operacji na tych wektorach, w tym iloczyn skalarny i wektorowy, obliczanie długości i odległości, normalizacja, interpolacja liniowak, rzutowanie, ortogonalizacja i inne. - Trójkąt w przestrzeni 3D nie posiada jawnej reprezentacji w postaci własnej struktury. Do jego opisania używane są trzy punkty typu common::VEC3. Zbiór funkcji wspierających trójkąty obejmuje m.in. operacje na współrzędnych barycentrycznych.
- Promień (ang. Ray, inaczej półprosta w przestrzeni 3D) również nie posiada swojej reprezentacji jako osobnej struktury. Do jego opisania używane są dwie zmienne typu common::VEC3 - punkt początkowy oraz wektor kierunku (nazywane w kodzie RayOrig od "Origin" i RayDir od "Direction").
- Prostokąt 2D zbudowany z liczb całkowitych reprezentuje struktura common::RECTI. Posiada ona pola
int left, top, right, bottom. Odpowiada strukturze RECT z WinAPI. - Prostokąt 2D zbudowany z liczb zmiennoprzecinkowych reprezentuje struktura common::RECTF. Posiada ona pola
float left, top, right, bottom. Istnieją funkcje testujące czy punkt lub inny prostokąt zawiera się w danym prostokącie, jak również liczące sumę i część wspólną dwóch prostokątów. - AABB (ang. Axis-Aligned Bounding Box, czyli prostopadłościan o krawędziach równoległych do osi układu współrzędnych) posiada reprezentację w postaci struktury common::BOX wyposażonej w pola opisujące jego dwa wierzchołki - o najmniejszych i o największych współrzędnych -
VEC3 p1, p2. - Kolor wraz z czwartym kanałem - Alfa oznaczającym przezroczystość - posiada dwie reprezentacje. Struktura common::COLOR zbudowana jest z pojedynczej liczby całkowitej 4-bajtowej, której poszczególne bajty przechowują wartości czterech kanałów w zakresie 0..255. Struktura common::COLORF posiada pola
float R, G, B, A reprezentujące poszczególne składowe jako liczby zmiennoprzecinkowe w zakresie 0.0..1.0. Funkcje operujące na kolorach obejmują m.in. interpolację i konwersję do/z przestrzeni kolorystycznej HSB. - Płaszczyzna w 3D opisywana jest równaniem
A x + B y + C z + D = 0. Jej współczynniki float a, b, c, d potrafi przechowywać struktura common::PLANE. Jeśli zdefiniowane jest makro USE_DIRECTX, jest on aliasem do typu D3DXPLANE. W przeciwnym razie moduł dostarcza własnej struktury o podobnych możliwościach. Tworzenie płaszczyzny polega zazwyczaj na podaniu wektora normalnego i przykładowego punktu który do niej należy bądź podaniu trzech należących do niej punktów. - Prosta 2D (na płaszczyźnie) opisywana jest równaniem
A x + B y + C = 0. Do reprezentacji jej współczynników float a, b, c zdefiniowana została struktura common::LINE2D. - Macierz 4x4 opisuje struktura common::MATRIX. Jeśli zdefiniowane jest makro USE_DIRECTX, ten typ jest aliasem do D3DXMATRIX. Jeśli nie, moduł dostarcza własnej implementacji o podobnej funkcjonalności. Używana jest w geometrii obliczeniowej do reprezentowania szerokiej klasy przekształceń w przestrzeni 3D. Jej minor 3x3 potrafi reprezentować przekształcenia liniowe - dowolną rotację, skalowanie, ścinanie, odbicie oraz dowolne złożenie tych przekształceń w określonej kolejności. Macierz 4x3 potrafi reprezentować przekształcenia afiniczne - te wymienione powyżej oraz translację. W macierzy 4x4, dzięki wykorzystaniu współrzędnych jednorodnych (polegających na zapisaniu punktów i wektorów 3D za pomocą 4 składowych), dodatkowo reprezentowane może być rzutowanie perspektywiczne, co wyczerpuje większość przekszałceń stosowanych w grafice 3D (niemożliwe do opisania taką mcierzą pozostają np. przekształcenia sferyczne i paraboloidalne). Liczne funkcje związane z tą strukturą służą przede wszystkim do tworzenia macierzy reprezentujących poszczególne rodzaje przekształceń.
- Kwaternion to rozszerzenie liczb zespolonych na wartość posiadającą 4 składowe -
float x, y, z, w. Nie powinien być mylony z punktem we współrzędnych jednorodnych, gdyż zachowuje się zupełnie inaczej. Dlatego reprezentowania kwaternionów utworzona została osobna struktura - common::QUATERNION. Jeśli zdefiniowane jest makro USE_DIRECTX, ten typ jest aliasem do D3DXQUATERNION. Jeśli nie, moduł dostarcza własnej implementacji o podobnej funkcjonalności. Kwaternion wykorzystywany jest w grafice 3D do opisywania dowolnej rotacji lub orientacji i jest w tym zastosowaniu lepszy niż kąty Eulera czy macierz, ponieważ nie posiada zjawiska "Gimbal Lock" oraz daje się łatwo interpolować (SLERP - ang. Spherical Linear Interpolation). Kwaternion powstaje przez podanie wektora osi obrotu i kąta obrotu wokół tej osi. Możliwe jest jednak dowolne przechodzenie między opisem rotacji przez kąty Eulera, macierz rotacji lub kwaternion. Do wszystkich tych przekształceń dostarczone są odpowiednie funkcje. - Frustum to ścięty ostrosłup o podstawie prostokąta. Nie posiada eleganckiego polskiego tłumaczenia (w środowisku internetowym zaproponowany został termin "ściętosłup"). Kształt ten posiada znaczenie w grafice 3D, ponieważ opisuje obszar widoczny w kamerze stosującej rzutowanie perspektywiczne. Stąd bardzo istotna jest możliwość stwierdzenia, czy obiekt (a raczej jego uproszczona bryła otaczająca) przecina to pole widzenia, a tym samym czy wymaga narysowania na ekranie. Moduł dostarcza trzech różnych reprezentacji frustuma, między którymi można przechodzić. Struktura common::FRUSTUM_PLANES opisuje frustum jako 6 płaszczyzn. Struktura common::FRUSTUM_POINTS} opisuje go jako 8 punktów. Struktura common::FRUSTUM_RADAR natomiast to tzw. reprezentacja radarowa.
- Sfera lub kula w 3D nie posiada dedykowanej struktury. Opisywana jest jako punkt - pozycja środka oraz wartość skalarna oznaczająca promień:
VEC3 SphereCenter; float SphereRadius;.
To tak naprawdę szablon funkcji, który w ogólnym przypadku nie działa (rzuca assertion failed), ale ma zdefiniowane specjalizacje. Służy do konwersji między typami tego modułu math a typami innymi matematycznymi, np. z Win32API. Ma zwykle zerowy narzut, bo dokonuje reinterpretacji, a nie żadnej konwersji. Używa się go intuicyjnie, tak samo jak normalnego rzutowania, np.:
Zdefiniowane są następujące konwersje:
Zbiór kilkudziesięciu funkcji oznaczonych jako liczące kolizje pozwala stwierdzać o zachodzeniu na siebie brył różnego rodzaju. Praktycznie każda z tych funkcji zawiera w swojej implementacji pewien sprytny algorytm pochodzący z jakiejś książki lub publikacji internetowej, a skompletowanie biblioteki tych funkcji kosztowało wiele czasu i pracy. Wiele z nich zostalo opracowanych na podstawie Fletcher Dunn, Ian Parberry, "3D Math Primer for Graphics and Game Development", Wordware Publishing, 2002. Dokładne informacje o źródłach poszczególnych algorytmów znaleźć można w komentarzach w kodzie.
Przykładowo, funkcja common::SweptBoxToBox sprawdza kolizję poruszającego się prostopadłościanu z innym prostopadłościanem. Wykorzystuje w tym celu sumę Minkowskiego. Funkcja common::TriangleToBox sprawdza, czy trójkąt w przestrzeni 3D przecina prostopadłościan. Wykorzystuje w tym celu twierdzenie o płaszczyznach rozdzielających (ang. Separating Axis Theorem).
Punkt:
- Punkt
- Promień, prosta, odcinek
- Prostopadłościan
- Sfera
- Płaszczyzna
- Trójkąt
- Frustum
- Wielokąt
Promień, prosta, odcinek:
- Promień, prosta, odcinek:
- Prostopadłościan
- Sfera
- Płaszczyzna
- Trójkąt
- Frustum
- Wielokąt
Prostopadłościan AABB:
- Prostopadłościan:
- Sfera:
- Płaszczyzna:
- Trójkąt:
- Frustum:
Sfera:
- Sfera:
- Płaszczyzna:
- Trójkąt: (BRAK)
- Frustum:
Płaszczyzna:
- Płaszczyzna:
- Trójkąt:
- Frustum:
Trójkąt:
Frustum:
Kolizję odcinka z dowolnym obiektem można zrobić tak: Dany jest odcinek o początku w punkcie SegOrig, kierunku SegDir i parametrze końca SegEndT oraz obiekt Coś, z którym testujemy kolizję. Użyjemy funkcji dla prostej i niezależnie czy w przypadku kolizji z tyłu punktu RayOrig (zwrócone T ujemne) zwróci miejsce kolizji bliższe czy dalsze, odcinek koliduje z obiektem, kiedy:
float T;
if (PointInCoś(SegOrig, Coś))
return true;
if (!LineToCoś(SegOrig, SegDir, Coś, &T))
return false;
if (T < 0 || T > SegEndT)
return false;
return true;
Dysk Poissona (ang. Poisson Disc) to takie rozmieszczenie punktów na płaszczyźnie lub w przestrzeni, w którym pozycje tych punktów są losowe, ale żadna para punktów nie jest od siebie odległa o mniej niż określona stała granica. Taki rozkład punktów wykorzystywany bywa w różnych zastosowaniach, np. podczas próbkowania przy śledzeniu promieni (Supersampling). Ma tę zaletę ponad regularną siatką punktów, że ich losowe rozmieszczenie zapobiega zjawisku aliasingu, natomiast jego zaleta w porównaniu z rozmieszczeniem zupełnie losowym polega na nieskupianiu się punktów w miejscach o większej lub mniejszej gęstości.
Problem z zastosowaniem dysku Poissona polega na dużej złożoności obliczeniowej generowania zbioru takich punktów. Dlatego dobrze jest przygotować wcześniej tablicę wypełnioną przykładowymi punktami o tym rozkładzie. Problemem jest jednak dostosowanie ich liczby do wymagań konkretnego zastosowania.
Aby temu zaradzić, postanowiłem wygenerować zbiór punktów dysku Poissona wg następującego algorytmu: Losowane są punkty odległe od siebie nie mniej, niż o pewną dużą wartość. Po wielu nieudanych próbach dodania następnego takiego punktu wartość ta jest zmniejszana pozwalając na obecność punktów nieco bliżej siebie położonych. Proces jest powtarzany aż do wygenerowania pożadanej liczby punktów.
Takie podejście pozwala otrzymać tablicę punktów, z których można wziąć N pierwszych elementów i zawsze stanowić one będą poprawny dysk Poissona o wartości granicznej odległości tym większej, im mniejsze jest N. Dzięki temu te same tablice punktów zastosowne mogą być w różnych sytuacjach. Napisałem specjalny program generujący takie tablice za pomocą kosztownych czasowo obliczeń, a następnie zapisałem je bezpośrednio w kodzie jako zbiory 100 1-, 2- i 3-wymiarowych punktów w zmiennych odpowiednio: common::POISSON_DISC_1D, common::POISSON_DISC_2D i common::POISSON_DISC_3D. Proponuję nazwę dla takiego rozwiązania: "progresywny dysk Poissona" (ang. Progressive Poisson Disc).
- Macierzy innych niż 4x4, np. 3x3, 4x3 itp.
- Pełnego wsparcia dla geometrii 2D (są wektory, prostokąty i proste w 2D, ale brakuje kolizji między nimi).
- Większości kolizji obiektów typu Swept - poruszających się (dynamicznych).
- Następujących obiektów geometrycznych:
- Oriented Bounding Box (OBB)
- Dowolny wielościan wypukły opisany płaszczyznami lub wierzchołkami
- Siatka trójkątów
- Zaawansowanych algorytmów geometrycznych, takich jak triangulacja czy Constructive Solid Geometry (CSG).
