Programming, graphics, games, media, C++, Windows, Internet and more...
Entries for tag "math", ordered from most recent. Entry count: 69.
# Krzywe i gówienko na kole
Thu
23
Apr 2009
Matematycy mają mądre nazwy na różnego rodzaju krzywe. Czytałem sobie o nich ostatnio na Wikipedii. Nie chodzi mi tu o dobrze znane programistom grafiki krzywe Beziera czy B-spline.
Na przykład taka krzywa Lissajous powstaje przez wykreślenie w 2D albo 3D śladu ruchu punktu wg funkcji sinus, z określoną amplitudą, okresem i fazą w każdej osi. Dawno temu napisałem wygaszacz ekranu rysujący coś takiego - ProgrameX Linear Screensaver - nie wiedząc nawet, że to się tak nazywa.
Z kolei Roulette to ogólna klasa krzywych wykreślanych przez punkt przyczepiony do jakiejś figury, która "toczy się" wzdłuż innej figury. Na przykład jeśli okrąg toczy się po prostej, to jakiś punkt skojarzony z tym okręgiem tworzy Trochoid. Jeśli ten punkt leży na tym okręgu, to jest przypadek szczególny - cykloida (Cycloid). Skojarzenie nazwy z cyklistami zapewne nie jest przypadkowe - krzywa przypomina kształt, jaki zakreśla w powietrzu gówienko przylepione do koła jadącego roweru :)
Źródło: Wikipedia
Jeśli okrąg porusza się po wewnętrznej stronie większego okręgu, powstaje hipotrochoida (Hypotrochoid). Jej szczególnym przypadkiem (punkt leży na okręgu) jest hipocykloida (Hypocycloid), a z kolei jej przykładem jest czteroramienna gwiazdka - Astroid. Podobnie, okrąg poruszający się po zewnętrznej stronie większego okręgu tworzy epitrochoidę (Epitrochoid), której szczególnym przypadkiem (punkt na okręgu) jest epicykloida (Epicycloid), której przykładem z kolei może być przypominająca kształtem serce kardioida (Cardioid).
Źródło: Wikipedia
# 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.
