Entries for tag "math", ordered from most recent. Entry count: 63.
# Generowanie liczb pseudolosowych
Fri
20
Jun 2008
Wczorajszy wieczór spędziłem na zajmowaniu się liczbami pseudolosowymi. Ogólne wnioski: Są różne algorytmy. Do kryptografii potrzebne są wyjątkowo dobre i istnieją różne hardcore'owe metody ich badania, ale w zwykłym programowaniu nie trzeba aż tak kombinować.
Popularnym algorytmem jest Linear congruential generator, który działa wg wzoru: x[i] = (x[i-1] * a + c) mod m
. Z niego korzystają biblioteki standardowe w popularnych kompilatorach C, C++, Delphi. Działa szybko, ale ma słabo losowe młodsze bity.
Napisałem sobie program pozwalający oceniać generatory liczb pseudolosowych metodą organoleptyczną ;) czyli wizualizując wyniki - wartości, rozkład wartości oraz poszczególne bity generowanych liczb. (Przy okazji przekonałem się, jak beznadziejną i pełną błędów biblioteką jest DevIL.) Oto wyniki:
Rozwiązaniem jest po prostu branie tylko starszych bitów z liczb generowanych przez Linear congruential generator. Tak z resztą robią biblioteki standardowe w różnych środowiskach. Można też użyć innego algorytmu - dobry i szybki jest podobno Mersenne twister.
Przy okazji ciekawostki: Na Random.org można sobie wygenerować prawdziwie losowe liczby, łańcuchy, bitmapy, a także rzuty kośćmi czy monetą (w tym polskimi złotymi! :) Po wyczerpaniu limitu liczb losowych na adres IP można sobie dokupić więcej. Są też w sprzedaży generatory liczb prawdziwie losowych pod USB :)
# Metaballs
Sat
14
Jun 2008
Metaballe (inaczej bloby) to takie kulki, które zlewają się ze sobą. Matematycznie to są izopowierzchnie opisane odpowiednimi wzorami. Metod ich renderowania jest kilka. Można je wyliczać bezpośrednio przez jakiś ray-casting. Można je zamieniać z reprezentacji wokselowej na siatki trójkątów za pomocą Marching Cubes Algorithm. Do renderowania dużych ilości metaballi w czasie rzeczywistym ze wsparciem GPU wymyślono nawet technikę w Image Space.
Ja chciałem być sprytniejszy i wpadłem na pomysł, żeby renderować metaballe odkształcając siatkę kulki w kierunku drugiej kulki. Niestety nic z tego nie wyszło, bo nie udało mi się znaleźć wzoru, który by zapewnił ładne łączenie między kulkami.
Comments | #rendering #math Share
# Ostatni artykuł - Zaawansowana kamera 3D
Thu
05
Jun 2008
Mój nowy artykuł nosi tytuł Zaawansowana kamera 3D. Jest bardzo długi i opisuje kilka zagadnień programistyczno-matematycznych dotyczących grafiki 3D: koncepcję kamery i jej implementację jako zestaw klas, rysowanie prostokątów zwróconych przodem do kamery (Billboard), w tym efektów cząsteczkowych, testowanie kolizji obiektów z polem widzenia kamery w celu nierysowania tego co niewidoczne (Frustum Culling) oraz testowanie kolizji promienia celem sprawdzania, który obiekt 3D gracz wskazał myszką (Picking). Dołączony kod zawiera spory kawałek mojej biblioteki matematycznej.
Na tym kończę maraton pisania artykułów i wracam do kodu :) Nie zrealizowałem nawet połowy z listy pomysłów na artykuły, ale myślę, że wybrałem te najlepsze.
Comments | #rendering #math #productions Share
# Nowy artykuł - Kwaterniony w praktyce
Tue
20
May 2008
Mój następny artykuł nosi tytuł Kwaterniony w praktyce. Przeznaczony jest dla tych, którzy znają już podstawy matematyki potrzebnej w programowaniu grafiki 3D (wektory, macierze), ale dotychczas omijali temat kwaternionów szerokim łukiem myśląc, że są bardzo trudne. Artykuł pokazuje (mam nadzieję), że nie ma w nich żadnej czarnej magii - są po prostu wygodnym narzędziem do zapisywanie obrotów i orientacji w 3D, z którego można się nauczyć korzystać bez rozumienia, że kwaternion to rozszerzenie liczb zespolonych mające trzy pierwiastki urojone :) Zamiast wzorów pokazałem fragmenty kodu C++.
Comments | #productions #math Share
# Floor, ceil i reszta
Fri
09
May 2008
Mieliśmy właśnie przed chwilą na IRC-u dyskusję o zasadach, według jakich działa zaokrąglanie/obcinanie liczb zmiennoprzecinkowych przez funkcje floor, ceil i rzutowanie na int. Przypomniałem sobie, że to temat, z którym nieraz się już spotkałem i pomyślałem, że warto to usystematyzować:
x -2.9 -2.2 2.2 2.9 --------------------------------- (int)x -2 -2 2 2 floor(x) -3.0 -3.0 2.0 2.0 ceil(x) -2.0 -2.0 3.0 3.0 round(x) -3.0 -2.0 2.0 3.0
Problem w tym, że funkcji zaokrąglającej round w C++ nie ma, trzeba ją sobie napisać. Podobnie brakuje funkcji zostawiającej samą część ułamkową 0..1, a jest ona bardzo potrzebna np. do robienia funkcji okresowych i występuje np. w języku HLSL jako frac.
inline int round(float x) { return (int)(x+0.5f); } inline float frac(float x) { return x - (float)(int)(x); }
Nie jestem tylko pewny, czy rzutowanie na int faktycznie zawsze obcina część ułamkową. Na moim Visual C++, Windows XP i procesorze Intel Core2Duo 32bit tak jest, ale nie zaglądałem do standardu C++, więc nie wiem czy tak samo jest wszędzie. Wkrótce jakiś językoznawca powinien wyjaśnić tą kwestię w tym wątku forum. Gdyby się jednak okazało, że nie można polegać na tym rzutowaniu, funkcję obcinającą część ułamkową można sobie napisać samemu:
inline float trunc(float x) { return (x < 0.0f) ? ceilf(x) : floorf(x); }
Takich niby prostych (prostych dla tego co już je zna) sztuczek matematycznych jest bardzo dużo. Przydałoby się je kiedyś porządnie spisać :) Na przykład ta nasza dyskusja IRC-owa zaczęła się od pytania, jak obciąć liczbę do 2 miejsc po przecinku. Rozwiązaniem jest:
y = (float)(int)(x * 100.0f) / 100.0f;
Comments | #c++ #math #algorithms Share
# Policzone tangenty do mapy
Thu
01
May 2008
Wieści z pierwszej linii frontu: Chyba udało mi się policzyć normalne i tangenty dla mapy Indoor, z wygładzeniem zależnie od kąta krawędzi. Wzory na tangenty wziąłem z tego artykułu. Ciekawy patent wymyśliłem, żeby w poszukiwaniu wierzchołków leżacych w pobliżu nie działać ze złożnością kwadratową. Otóż posortowałem wierzchołki w każdej grupie (rysowane danym materiałem) wg współrzędnej X. Potem dla każdego wierzchołka przeglądam tylko kilka następnych, tak długo jak (v2.x - v1.x) < EPSILON_DIST. Czyż to nie dużo prostsze, niż jakieś Octree czy k-d tree? :D
Comments | #rendering #math Share
# GameDev Calc
Fri
18
Apr 2008
Opublikowałem moją nową małą, wielką produkcję. Jest mała, bo kodowanie wcale nie wymagało dużo pracy, ale wielka, bo od dawna bardzo chciałem to napisać. To GameDev Calc - kalkulator dla programistów gier.
Pobierz: GameDevCalc_1-0.zip (53.06 KB)
Jednostką danych jest wektor 1-4 liczb zmiennoprzecinkowych, który można traktować jako wektor (x,y,z,w) lub kolor (r,g,b,a). Oprócz podstawowych operacji jak dodawanie, mnożenie czy sinus, dostępne są operacje wektorowe, np. normalizacja wektora, a także zamiana kątów na stopnie i radiany, zamiana kolorów na RGB i HSB, znajdowanie współczynników funkcji liniowej i kwadratowej oraz wiele innych. Zamiast tylko ostatnio wprowadzonej liczby, widoczna jest cała historia obliczeń w postaci stosu i na tym stosie są przeprowadzane wszystkie operacje. Dane można wprowadzać i wyprowadzać w dowolnym wybranym formacie, np. jako "D3DXVECTOR4(0.0f, 0.5f, 0.752f, 1.0f)" albo "0xFF0080C0". Platforma: Windows. Język: C#. Licencja: GNU GPL.
Comments | #productions #tools #math Share
# Przekształcenie wektora przez macierz
Thu
20
Mar 2008
Transformację w 3D opisuje macierz 4x4. Pełne przekształcenie punktu (x,y,z) przez taką macierz polega na pomnożeniu (x,y,z,1) przez tą macierz, a potem podzieleniu trzech pierwszych składowych przez składową czwartą w. Używamy tu tzw. współrzędnych jednorodnych (ang. Homogeneous Coordinates). W D3DX dokonuje tego funkcja D3DXVec3TransformCoord.
Przekształcenie wektora wskazującego kierunek (w przeciwieństwie do punktu opisującego położenie) musi nie brać pod uwagę translacji, czyli czwartego wiersza macierzy. Dlatego przekształcenie wektora polega zwykle na pomnożeniu (x,y,z) przez podmacierz 3x3 tej macierzy. W D3DX dokonuje tego funkcja D3DXVec3TransformNormal.
Jeśli ten wektor jest wektorem normalnym wierzchołka siatki, teoretycznie należy go przekształcić przez odwrotność transpozycji (lub transpozycję odwrotności - to bez różnicy) tej macierzy, której używamy do przekształcania pozycji wierzchołków. W praktyce jednak, jeśli podmacierz 3x3 tej macierzy zawiera tylko rotację (i ewentualnie skalowanie proporcjonalne), a nie zawiera skalowania nieproporcjonalnego ani ścinania, wektory bazowe w tej macierzy są ortogonalne, więc jej odwrotność jest równa jej transpozycji i te przekształcenia się znoszą. Dlatego wystarczy przekształcić wektor wprost przez daną macierz, bez odwracania i transponowania (a wynik ewentualnie znormalizować, jeśli było skalowanie).
W swojej bibliotece matematycznej mam jeszcze jedną funkcję, nazwaną po prostu Transform. Przekształca ona punkt (x,y,z,1) przez podmacierz 4x3 podanej macierzy, nie wyliczając współczynnika w i nie dzieląc przez niego. To znacznie przyspiesza obliczenia względem funkcji TransformCoord i wystarcza wszędzie tam, gdzie macierz nie zawiera przekształcenia perspektywicznego, bo jej czwarta kolumna jest wtedy zawsze równa (0,0,0,1).
Za wszelkie uproszczenia przepraszam. Możnaby o tym dużo pisać. Chciałem tu tylko pokazać, że teoretyczne "pomnożyć wektor przez macierz" przybiera w praktyce różne formy i trzeba umieć prawidłowo je stosować.