Moduł Math

Nagłówek: Math.hpp
Elementy modułu: Math Module

Wstęp

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.

Założenia

Składniki

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.

math_cast

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

common::POINT_ Pt(1, 2);
POINT WinPt = common::math_cast<POINT>(Pt);

Zdefiniowane są następujące konwersje:

Kolizje

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:

Promień, prosta, odcinek:

Prostopadłościan AABB:

Sfera:

Płaszczyzna:

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;

PoissonDisc

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

Czego nie ma


Generated on Wed Dec 16 20:44:52 2009 for CommonLib by  doxygen 1.6.1