Tag: math

Entries for tag "math", ordered from most recent. Entry count: 62.

Uwaga! Informacje na tej stronie mają ponad 5 lat. Nadal je udostępniam, ale prawdopodobnie nie odzwierciedlają one mojej aktualnej wiedzy ani przekonań.

Pages: 1 ... 3 4 5 6 7 8

# KD-Tree

Thu
09
Jul 2009

People at forums are usually advised to learn BSP, quadtree or octree as space partitioning data structure, but there are many more interesting structures than these three. This time my choice for home project is KD-tree. It's actually something between BSP and octree. Just like BSP it's a binary tree (each non-leaf node has two child nodes) and optimal splitting plane is estimated each time by special algorithm, but splitting planes are always aligned to one of three main axes and thus each node can be described by an AABB (axis-aligned bounding box), just like in octree.

As my tree is designed to manage objects and not geometry, nothing can be split and some of objects may intersect splitting planes. How to deal with them? I simply assign them to the parent node, so not only leaves are allowed to contain list of objects. To avoid too many small objects intersecting splitting planes to degrade performance by falling into top level nodes (it's called "sticky planes" or something like that :) I adopted "loose octree" idea to my KD-tree. It simply means I extend each node’s bounding box so that each node's children slightly overlap each other and small objects intersecting splitting plane fall into one of the children.

My KD-tree is also dynamic, which means it reorganizes itself as objects get added, removed and moved in the tree. It's actually quite simple. Each time an object is added to a node, that node can be split into two children if it's object number exceeds constant limit. Similarly node can be merged by deleting it's children each time an object is removed from one of its children, if the number of objects in that node and its children drops under constant minimum.

For additional performance, I allocate tree nodes from my own "Free List" memory pool and I keep objects connected to each node as doubly-linked list.

I also came up with an idea how to easily visualize quality of my space partitioning technique. I keep track of the number of tree nodes and objects on each depth level. This way I can tell from these several numbers whether tree is more "tall" or "wide" and whether most of objects stay in leaves instead of some top-level nodes.

Here are some screenshots and a video from my recent code:

Comments | #rendering #video #gallery #algorithms #math

# 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```

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

Źródło: Wikipedia

lub lepsza, ale bardziej kosztowna obliczeniowo Hilbert value:

Źródło: Wikipedia

# 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 :)