June 2008

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

20:58
Sat
28
Jun 2008

Blender 2.46

W maju ukazała się nowa wersja Blendera - najlepszego darmowego programu do grafiki 3D. Lista nowości wersji 2.46 jest imponująca, w tym m.in.:

Jednego tylko twórcy uparcie nie chcą zmienić - koszmarnego interfejsu użytkownika. Wręcz przeciwnie - jest coraz gorzej. Oto przykład: Jesteśmy w UV/Image Editor, chcemy wczytać plik tekstury. Klikamy w menu Image > Open... i pokazuje się File Browser. Jak wybrać teksturę za pomocą nowego Image Browser? Trzeba wejść do menu Image i kliknąć polecenie Open... z przytrzymanym klawiszem CTRL! Nowy rekord absurdu został pobity.

Comments (0) | Tags: graphics software | Author: Adam Sawicki | Share

10:30
Mon
23
Jun 2008

Tablice 2D

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 (0) | Tags: algorithms c++ | Author: Adam Sawicki | Share

10:38
Sun
22
Jun 2008

Kasowanie linijki w konsoli

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 (1) | Tags: c++ stl algorithms | Author: Adam Sawicki | Share

11:01
Sat
21
Jun 2008

Liczby losowe o rozkładzie normalnym

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.

Comments (1) | Tags: math | Author: Adam Sawicki | Share

12:31
Fri
20
Jun 2008

Generowanie liczb pseudolosowych

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

Comments (0) | Tags: math | Author: Adam Sawicki | Share

15:27
Thu
19
Jun 2008

Firefox 3

Przedwczoraj miała miejsce premiera długo oczekiwanej, zupełnie nowej wersji popularnej przeglądarki WWW - Firefox 3. Na pierwszy rzut oka zmiany nie są duże. Przeglądarka faktycznie sprawia wrażenie trochę lżejszej i szybszej, a przede wszystkim szybciej (albo raczej - bardziej wielowątkowo) robi swoją robotę, nie dając się zablokować jakiemuś dużemu obrazkowi czy JavaScriptowi. Twórcy wprowadzili zmiany głównie do paska adresu (wpisywane słowa szuka nie tylko w adresach, ale i tytułach odwiedzonych wcześniej stron) i mechanizmu zakładek (np. można dodać bieżacą stronę do zakładek jednym kliknięciem). Strony można powiększać razem z obrazkami. No i jeszcze ma nowe, ładniejsze ikonki :)

Comments (0) | Tags: software web | Author: Adam Sawicki | Share

17:22
Mon
16
Jun 2008

mgr inż. Adam Sawicki

Stało się. Obroniłem pracę magisterską. Temat: "Architektura i implementacja silnika grafiki trójwymiarowej". Od dziś nie jestem już student, tylko wyżej wykształcony magister inżynier informatyk :) Tysiące myśli, radości ale i smutków, wspomnień ale i nadziei... Nie ma sensu ich wymieniać. Zobaczymy, co dalej przyniesie los.

Comments (0) | Tags: studies life | Author: Adam Sawicki | Share

23:12
Sun
15
Jun 2008

Jutro obrona

Wszystko wskazuje na to, że jutro mam obronę pracy magisterskiej, a przy okazji egzamin dyplomowy, który obejmuje materiał z całych studiów. Co to będzie... :/ Gram ostatnio w WoW-a, to może znajdę jeszcze jakąś tarczę, co ma +50 do obrony :)

Comments (0) | Tags: studies life | Author: Adam Sawicki | Share

20:18
Sat
14
Jun 2008

Metaballs

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 (0) | Tags: rendering math | Author: Adam Sawicki | Share

15:36
Wed
11
Jun 2008

Subsurface Scattering

W ostatnich dniach pracowałem nad SSS - Subsurface Scattering. Zacząłem od artykułu Simon Green, "Real-Time Approximations to Subsurface Scattering" z książki "GPU Gems 1" (rozdz. 16). Metoda działa tak jak Shadow Mapping, tekstura przedstawia głębokość z punktu widzenia światła i z niej wyliczana jest w każdym miejscu grubość obiektu w kierunku źródła światła. Nie uzyskałem zadowalającego efektu. Model wygląda dziwnie i wyraźnie widać na nim "cień" od światła. Nie o to chodzi.

Wkurzony, wziąłem do ręki plastikowy przedmiot i obserwowałem go pod różnymi kątami padania światła, żeby opracować swój model SSS. Moja główna obserwacja polega na tym, że najważniejsza jest grubość modelu w kierunku patrzenia kamery, niezależnie od światła. Renderowanie głębokości z punktu widzenia przeciwnego do kamery dało dobry efekt, najlepszy jaki udało mi się uzyskać.

Ta metoda działa idealnie dla obiektów wypukłych, ale dla niewypukłych pod niektórymi kątami wyraźnie widać niestety geometrię z przeciwnej strony modelu.

Potem spróbowałem wyliczyć i zapisać w wierzchołkach grubość modelu w danym miejscu w kierunku zanegowanej normalnej. Efekt, jak można się spodziewać, jest daleki od oczekiwanego, bo pojedyncza grubość nie bierze pod uwagę kąta patrzenia kamery ani światła.

Wreszcie, spróbowałem wyliczać i zapisywać dla każdego wierzchołka po 3 grubości w 3 różnych kierunkach, zgodnie z "bazą Half-Life 2", której Valve użyło do Radiosity Normal Mapping. Gdyby się udało, to by mógł być epokowy wynalazek :) Ale się nie udało.

Comments (0) | Tags: rendering | Author: Adam Sawicki | Share

22:45
Tue
10
Jun 2008

Jakie programy graficzne?

Trafiłem dzisiaj na fajny program do przeglądania plików graficznych - FastStone Image Viewer. Jest darmowy i wygląda na lepszy, niż stara wersja ACDSee, której używałem dotychczas jako szczęśliwy posiadacz jej pełnej, oryginalnej wersji. Ta zmiana zainspirowała mnie do wypisania listy znanych mi programów graficznych, które warto mieć. Przy okazji chętnie przeczytam w komentarzach wasze typy.

Oprócz przeglądania zdjęć z aparatu i innych ładnych obrazków ;) bywają też potrzebne funkcje specjalistyczne i wtedy trzeba sięgnąć po odpowiednie oprogramowanie. Nie wiem jak to jest ze sprawami graficznymi, takimi jak RAW czy CMYK. Ze spraw gierkoderskich, obsługę formatu DDS i generowanie normal map załatwiają odpowiednie wtyczki do GIMP-a.

Comments (0) | Tags: graphics software | Author: Adam Sawicki | Share

14:03
Sat
07
Jun 2008

Jak zrobiłem kd-tree

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

Comments (2) | Tags: algorithms | Author: Adam Sawicki | Share

20:09
Fri
06
Jun 2008

Oren-Nayar

Trafiłem przypadkowo na hasło oświetlenia wg modelu Orena-Nayara i sobie go na szybko skodziłem z pomocą tego artykułu. Jest to model oświetlenia rozproszonego (Diffuse) uogólniający stosowane powszechnie prawo Lamberta na powierzchnie o współczynniku chropowatości 0..1. Nie chodzi o żadne mapowanie nierówności takie jak Normal Mapping, a raczej tylko o odpowiednie "spłaszczenie" funkcji liczącej oświetlenie. Fajnie to wygląda, ale niestety jest skomplikowane obliczeniowo. Dlatego wartoby poszukać jakiejś prostej aproksymacji tej funkcji albo zakodować ją w jakiejś teksturze przeglądowej.

Oren-Nayar

Comments (0) | Tags: rendering | Author: Adam Sawicki | Share

11:09
Fri
06
Jun 2008

HDR i Glare

Na czym to ja skończyłem... Miałem mapę i Deferred Shading, dopisałem HDR i miałem zrobić Tone Mapping. W ramach HDR akumuluję oświetlenie sceny kolejnymi światłami do Render Targeta o formacie zmiennoprzecinkowym. Już samo to znacznie poprawia kolorystykę sceny. Żeby było pełne HDR, wypada potem mierzyć średnią jasność sceny i zależnie od tego robić Tone Mapping. Nie udało mi się jednak znaleźć takiego wzoru, któryby dał ładny wygląd.

HDR, Glare

Kolejną rzeczą jest rozbłysk od źródeł światła. To nie jest żaden Bloom, tylko zwykłe quady zwrócone przodem do kamery, pokryte odpowiednią teksturą. One są rysowane z wyłączonym Z-buforem, ale tylko wtedy, kiedy liczony na CPU test kolizji promienia od kamery do światła nie wykaże żadnej przeszkody po drodze. Odpowiednią teksturę wyliczyłem na podstawie wzoru, który znam od Krzyśka K. i wrzuciłem ją też do pobrania:

Glare - tekstura narzędziowa

Comments (0) | Tags: rendering | Author: Adam Sawicki | Share

10:52
Thu
05
Jun 2008

Ostatni artykuł - Zaawansowana kamera 3D

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 (0) | Tags: rendering math productions | Author: Adam Sawicki | Share

STAT NO AD [Stat] [Admin] [STAT NO AD] [pub] [Mirror] Copyright © 2004-2017 Adam Sawicki
Copyright © 2004-2017 Adam Sawicki