Programming, graphics, games, media, C++, Windows, Internet and more...
Entries for tag "math", ordered from most recent. Entry count: 68.
# Programy matematyczne
Sun
01
Mar 2009
Czasem trzeba coś policzyć. Do prostych obliczeń wystarczy systemowy kalkulator. Pewne obliczenia na wektorach i kolorach daje się zrobić za pomocą mojego GameDev Calc. Czasami potrzebne są jednak bardziej zaawansowane funkcje. Jaki program matematyczny jest dobry? Niedościgniony jest podobno Matlab, ale on niestety nie należy do darmowych. Na szczęście są darmowe programy, które do wielu rzeczy z powodzeniem wystarczą.
Pierwszy z nich to Scilab. Używa składni podobnej do Matlaba i potrafi robić dużo rzeczy. Na przykład aby znormalizować wektor i pomnożyć go przez macierz:
v=[1 2 3] vn=v/norm(v) M=[1 0 0; 0 0 1; 0 1 0] v2=vn*M
# Funkcja liniowa i kwadratowa
Wed
14
Jan 2009
W programowaniu bardzo często stosuje się funkcję liniową lub kwadratową. Przykładowo, jeśli mgła ma się zaczynać w głębokości Min i kończyć w głębokości Max, to jej intensywość od głębokości można wyrazić prostym wzorem:
FogIntensity = saturate(Depth * FogScale + FogBias);
Problem w tym, żeby znaleźć współczynniki tej funkcji. Do tego przydają się wzory, które wyliczają współczynniki dla funkcji przechodzącej przez dane punkty. Potrafi to robić mój GameDev Calc, ale żeby policzyć je w swoim programie albo na kartce, warto mieć pod ręką te wzory.
Funkcja liniowa
przechodząca przez dwa punkty (x1, y1), (x2, y2) ma wzór:
Co w przełożeniu na kod daje:
float W = p2.x - p1.x; if (W == 0.f) Error(); float a = (p2.y - p1.y) / W; float b = (p2.x * p1.y - p2.y * p1.x) / W;
Z kolei funkcja kwadratowa 
przechodząca przez trzy punkty (x1, y1), (x2, y2), (x3, y3) ma wzór:
Co daje trochę dłuższy kod:
float x1 = p1.x, x2 = p2.x, x3 = p3.x; float y1 = p1.y, y2 = p2.y, y3 = p3.y; float W = x1 * x1 * x2 + x3 * x3 * x1 + x2 * x2 * x3 - x1 * x1 * x3 - x2 * x2 * x1 - x3 * x3 * x2; if (W == 0.f) Error(); float a = y1 * x2 + y3 * x1 + y2 * x3 - y1 * x3 - y2 * x1 - y3 * x2; float b = x1 * x1 * y2 + x3 * x3 * y1 + x2 * x2 * y3 - x1 * x1 * y3 - x2 * x2 * y1 - x3 * x3 * y2; float c = x1 * x1 * x2 * y3 + x3 * x3 * x1 * y2 + x2 * x2 * x3 * y1 - x1 * x1 * x3 * y2 - x2 * x2 * x1 * y3 - x3 * x3 * x2 * y1; a /= W; b /= W; c /= W;
# Co wynalazł Hilbert i Morton
Mon
12
Jan 2009
Tablicę jednowymiarową można posortować, żeby przyspieszyć jej przeszukiwanie. W programowaniu gier, do przestrzeni 2D i 3D używamy technik podziału przestrzeni (jak BSP, Octree, k-d tree), bo nie sposób uporządkować punktów czy obiektów w kolejności. Jednak czy napewno?
Otóż wynaleziono funkcje, które przeliczają pozycję punktu w przestrzeni (podzielonej wprawdzie na dyskretną siatkę) na pojedynczą liczbę taką, że dwa punkty leżące blisko siebie dostają często zbliżoną wartość. Te funkcje to numer komórki wzdłuż pewnej krzywej (Space-filling curve).
Przykładem może być Morton value:
Źródło: Wikipedia
lub lepsza, ale bardziej kosztowna obliczeniowo Hilbert value:
![Hilbert value](http://upload.wikimedia.org/wikipedia/commons/thumb/1/13/Hilbert3d-step3.png/180px-Hilbert3d-step3.png")
Źródło: Wikipedia
Comments | #math #algorithms #rendering Share
# Funkcje do kolizji
Mon
03
Nov 2008
Zachęcony notką na blogu Yarpena kupiłem sobie książkę Real-Time Collision Detection (Christer Ericson). Teraz czytam ją wrzucając znalezione funkcje do modułu matematycznego mojej biblioteki CommonLib. Żeby je testować, napisałem sobie prosty program z Direct3D, który pokazuje kolidujące bryły:
Jak pisałem już kiedyś, w programowaniu (szczególnie tam gdzie jest matematyka) występuje tajemnicze zjawisko, które powoduje, że skopiowany kod - choćby nie wiem jak gotowy do użycia - zwykle nie działa. Pojawiają się różne błędy zmuszając do podjęcia wysiłku jego zrozumienia, żeby te błędy naprawić. Wczoraj to zjawisko dało o sobie znać w wyjątkowo niezwykły sposób. Kompilator pokazał błąd:
error C2146: syntax error : missing ';' before identifier '-'
Dłuższą chwilę zajęło mi stwierdzenie, że powodem jest sam znak minusa, który w skopiowanym kodzie nie jest prawdziwym minusem, ale jakimś znakiem specjalnym, który minus przypomina. Mimo tych trudności nie poddaję się - metoda Kopiego-Pasta rządzi! :)
# Liczby losowe o rozkładzie normalnym
Sat
21
Jun 2008
Osobnym zagadnieniem jest generowanie liczb o rozkładzie normalnym. Dotychczas używałem do tego algorytmu Box-Muller, który jednak jest wolny, bo wykorzystuje cosinus, pierwiastek i logarytm naturalny. Szybciej działa jego odmiana biegunowa, która bierze dwie liczby o rozkładzie równomiernym 0..1 i generuje na raz dwie liczby o rozkładzie normalnym w ten sposób:
float x1, x2, w;
do {
x1 = 2.0f * RandFloat() - 1.0f;
x2 = 2.0f * RandFloat() - 1.0f;
w = x1 * x1 + x2 * x2;
} while (w >= 1.0f);
w = sqrtf((-2.0f * logf(w)) / w);
Result1 = x1 * w;
Result2 = x2 * w;
Jeszcze inna metoda, opisana w dostępnej za darmo książce The Scientist and Engineer's Guide to Digital Signal Processing, opiera się na obserwacji, że suma 12 liczb losowych 0..1 o rozkładzie równomiernym ma rozkład normalny ze średnią 6 i oschyleniem standardowym 1. Wystarczy więc 1) Zsumować 12 liczb losowych 0..1, 2) Odjąć 6, 3) Pomnożyć przez żądane odchylenie standardowe, 4) Dodać żądaną średnią. Mój pomiar wykazał jednak jasno, że ta metoda z sumą 12 generowań nie będzie szybsza od pokazanego wyżej kodu, nawet mając szybki i sprytnie napisany generator o rozkładzie równomiernym 0..1.
# 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.
