Programming, graphics, games, media, C++, Windows, Internet and more...
Entries for tag "algorithms", ordered from most recent. Entry count: 68.
# Tablice 2D
Mon
23
Jun 2008
Mieliśmy ostatnio w tym wątku forum dyskusję na temat tablic 2D w C++. Sposobów na to jest kilka. Ten najbardziej oczywisty to podwójny wskaźnik, czyli tablica tablic:
int **Tab = new int*[SizeX]; for (int x = 0; x < SizeX; x++) Tab[x] = new int[SizeY]; Tab[x][y] // Odwołanie
Forumowi specjaliści piszą, że metoda z jednowymiarową tablicą jest lepsza, bo wszystko jest w jednym kawałku pamięci, co zapewnia lepszą spójność cache i mniejsze ryzyko wystąpienia problemów ze stronnicowaniem. Co ciekawe, odwołania do takiej tablicy wcale nie są wolniejsze ze względu na mnożenie, bo w kodzie powyżej mnożenie też zachodzi, skoro elementy pierwszej tablicy nie mają przecież wielkości 1 bajtu.
int *Tab = new int[SizeX*SizeY]; Tab[y*SizeX + x] // Odwołanie
Możliwa jest jeszcze inna metoda, ale ona jest już przekombinowana, a poza tym zadziała tylko kiedy drugi wymiar tablicy jest stały.
int (*Tab)[16]; Tab = new int[16][16]; Tab[x][y] // Odwołanie
Comments | #algorithms #c++ Share
# Kasowanie linijki w konsoli
Sun
22
Jun 2008
Konsola systemowa, używana przez funkcje C (jak printf) lub C++ (jak std::cout) pozwala tylko wypisywać na wyjście i pobierać na wejściu znaki lub całe łańcuchy. Dopiero Windows API umożliwia bardziej niskopioziomowe reagowanie na klawiaturę, myszkę i swobodne rysowanie znakami po dowolnych miejscach konsoli, także z użyciem kolorów. Zawsze zastanawiało mnie, jak bez WinAPI radzą sobie twórcy programów konsolowych, którzy kasują bieżącą linijkę zamiast tylko dopisywać nowe informacje, jak wtedy kiedy następuje odliczanie 10%, 20%, 30% itd.
Ostatnio znalazłem rozwiązanie. Jest nim magiczny znak "\r", który użyty samodzielnie (a nie jako część końca wiersza "\r\n") powoduje powrót karetki na początek linii umożliwiając napisanie w jej miejscu czegoś nowego. Na przykład:
for (unsigned i = 0; i < 10; i++)
{
std::cout << "\rLiczba: " << i;
Sleep(500);
}
std::cout << std::endl;
Comments | #c++ #stl #algorithms Share
# Jak zrobiłem kd-tree
Sat
07
Jun 2008
Do testowania kolizji promienia od kamery do świateł napisałem sobie drzewo kd, w którym przechowałem odniesienia do trójkątów mapy. Właściwie to jest swobodne drzewo kd, analogicznie do swobodnych drzew ósemkowych.
Interesujący jest sposób, w jaki go zapisałem. Wcześniej zawsze węzeł drzewa był u mnie prawdziwym, alokowanym dynamicznie obiektem przechowującym własny wektor trójkątów. Tym razem wszystko mieści się w zwykłych tablicach:
struct NODE
{
BOX Bounds; // AABB węzła
unsigned FirstTriangle;
unsigned TriangleCount;
unsigned SubnodeIndex[2];
};
// To jest kd-tree
std::vector<NODE> Nodes;
std::vector<unsigned> Triangles;
// To jest siatka mapy
std::vector<unsigned> Indices;
std::vector<VERTEX> Vertices;
Pierwszy element tablicy węzłów to korzeń. Każdy węzeł przechowuje indeksy swoich dwóch podwęzłów SubnodeIndex odnoszące się do tablicy Nodes. Każdy węzeł wyznacza też zakres trójkątów, które do niego należą - FirstTriangle i TriangleCount odnoszące się do tablicy Triangles. Każdy element Triangles to z kolei numer pierwszego z indeksów wierzchołków należących do danego trójkąta, odnoszący się do tablicy Indices. Natomiast Indices to już zwykły bufor indeksów siatki, odnoszący się do tablicy Vertices.
Jak takie drzewo powstaje? Funkcja rekurencyjna dla danego węzła z Nodes tworzy dwa podwęzły, a zakres trójkątów należących do tego węzła rozdziela na trzy podzakresy: te które trafiają do pierwszego podwęzła, które trafiają do drugiego podwęzła i które zostają w tym węźle. W tym celu wykonuje dwukrotnie algorytm podziału zakresu na dwa podzakresy - tego samego którego używa QuickSort. On ma złożoność liniową i jest do dyspozycji w STL jako algorytm std::partition.
Podsumowując, takie podejście do tworzenia i przechowywania drzewa podziału przestrzeni ma liczne zalety: drzewo zajmuje mniej pamięci, szybciej się wylicza, łatwiej się zapisuje i odczytuje z pliku. Ma też jedną wadę - wymaga używania zamotanych odwołań takich jak to:
x = Vertices[Indices[Triangles[Nodes[ NodeIndex].FirstTriangle+ti]+vi]].Pos.x;
Profesjonaliści pewnie mnie wyśmieją że dopiero teraz na to wpadłem, a początkujący i tak tego nie zrozumieją, ale co mi zależy... Piszę to na co mam ochotę :)
# Nowy artykuł - Szybki alokator FreeList
Wed
28
May 2008
Mój następny artykuł nosi tytuł Szybki alokator FreeList. Opisuje przykład implementacji mechanizmu zwanego Free List. Jest to samodzielne zarządznie pamięcią polegające na utrzymywaniu listy wolnych elementów, z której można przydzielać elementy dużo szybciej, niż to robi alokacja pamięci ze sterty standardowym operatorem new. Mój kod oparty jest na artykułach z książek "Game Programming Gems", a przeprowadzony test pokazuje, że faktycznie osiąga on bardzo dobrą wydajność.
Comments | #productions #c++ #algorithms 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
# Deferred Shading - pakowanie pozycji i normalnej
Sun
04
May 2008
Piszemy Deferred Shading... Pierwsze co przychodzi do głowy, to zapisywanie do G-buforów pozycji i wektora normalnego w przestrzeni kamery jako pełne (x,y,z). Żeby oszczędzić komponentów, można je spakować. Zakładając, że wszystkie widoczne ścianki są zwrócone przodem do kamery, jako wektor normalny wystarczy zapisać tylko (x,y), a trzecią składową odzyskać ze wzoru:
Normal.z = - sqrt(1 - Normal.x*Normal.x - Normal.y*Normal.y);
Długo szukałem działającego wzoru na kodowanie pozycji jako pojedyncza odległość/głębokość, więc tym chętniej się nim podzielę. Są tutaj różne szkoły. Można zapisywać głębokość z/w, można odległość od kamery, można też odległość od bliskiej płaszczyzny przycinania. U mnie sprawdziło się takie rozwiązanie:
// Kodowanie - VS: Out.ViewPos = mul(float4(In.Pos, 1), (float4x3)WorldView); // Kodowanie - PS: G1.b = length(In.ViewPos); // Dekodowanie - VS: Out.EyeVec = float3(In.Pos.x * AspectRatio, In.Pos.y, TanFovY); // Dekodowanie - PS: Pos = normalize(In.EyeVec) * G1.b;
Gdzie podczas dekodowania: Pos.xy to pozycja wierzchołków fullscreen quada w przestrzeni rzutowania -1..1, TanFovY to tangens kąta widzenia pionowego w radianach używanego w macierzy rzutowania tan(FovY), AspectRatio to stosunek szerokości do wysokości widoku.
Trzeba jeszcze pamiętać, że jeśli tekstura G-bufora nie jest w formacie zmiennoprzecinkowym (jak u mnie A16B16G16R16F), to zapisywane wartości trzeba jakoś skalować do przedziału 0..1.
Comments | #algorithms #rendering Share
# Elementarne algorytmy
Tue
25
Mar 2008
float t;
for (uint i = 0; i < Count; i++) {
t = (float)i / (float)(Count - 1);
Foo(t);
}
Czy da się ten kod napisać lepiej? Ano da się. Zamiast wyliczać zmienną t za każdym razem na podstawie i, można ją zwiększać niezależnie:
float t = 0.0f, t_step = 1.0f / (float)(Count - 1); for (uint i = 0; i < Count; i++, t += t_step) Foo(t);
Dla niektórych to oczywiste, ale każdy musiał się tego skądś nauczyć albo samemu wymyślić. Ja mam na to nazwę "elementarne algorytmy" i uważam, że takich rzeczy nie powinno się poznawać gdzieś przy okazji, ale porządnie spisać i nauczać początkujących programistów.
Mam nawet spisane pomysły na ponad pół setki takich drobiazgów, które możnaby opisać i zacząłem to robić w czasie wakacji 2007 jako nowa wersja mojego artykułu "Struktury danych i formaty plików" (nowy tytuł to "Brakujące ogniwo"), ale dokładne opisanie i zilustrowanie tego wszystkiego przerosło moje możliwości :)
Comments | #c++ #algorithms #teaching Share
# Metoda szablonowa zamiast rzutowania
Tue
29
Jan 2008
Wpadłem ostatnio na pomysł, żeby się z wami podzielić drobnym rozwiązaniem, które wymyśliłem i które stosuję od dawna w swoim kodzie. Jako przykład weźmy manager zasobów. U mnie jest jeden ogólny, a każda klasa zasobu dziedziczy ze wspólnej klasy bazowej IResource. Są więc klasy pochodne takie jak D3dTexture czy FmodSound. Zasobów używam przez wskaźnik, ale ponieważ ich lista jest zapisana w pliku tekstowym, trzeba taki wskaźnik najpierw pobrać na podstawie nazwy. Trzeba przy tym zrzutować otrzymany zasób w dół na określony typ pochodny. Można to zrobić tak:
res::D3dTexture *Tex = (res::D3dTexture*)res::g_Manager->MustGetResource(L"Potwór01"); Tex->Cośtam();
lub bezpieczniej ze względu na typ:
res::D3dTexture *Tex = dynamic_cast<res::D3dTexture*>(res::g_Manager->GetResource(L"Potwór01")); if (Tex == NULL) throw Error(...); Tex->Cośtam();
Mój pomysł polega na napisaniu metody szablonowej, która ukryje rzutowanie:
template <typename T>
T * MustGetResourceExf(const wstring &Name)
{
return static_cast<T*>(MustGetResource(Name));
}
I jej wersji wolniejszej ale bezpieczniejszej:
template <typename T>
T * MustGetResourceEx(const wstring &Name)
{
IResource *R = MustGetResource(Name);
if (typeid(*R) != typeid(T)) throw Error(...);
return static_cast*lt;T*>(R);
}
Używa się ich tak:
res::D3dTexture *Tex = res::g_Manager->MustGetResourceEx<res::D3dTexture>(L"Potwór01"); Tex->Cośtam();
Prawda, że bardziej eleganckie? :) Gdyby ktoś pytał, przedrostek "Must" oznacza u mnie, że w przypadku nieznalezienia zasobu o podanej nazwie rzucony zostaje wyjątek, w przeciwieństwie do metod bez niego, które w takim przypadu zwracają NULL.