Analizator stosu

Dawno nic nie napisałem, ale przez ten miesiąc zwyczajnie nie było kiedy. Poszukiwanie pracy, użeranie się z urzędasami w PUPie, dalsze poszukiwanie pracy. Ostatecznie znalazłem "pracę". Pomagam przy projekcie prowadzonym przez Politechnikę. Napisałem "pracę", bo tak naprawdę to robię to póki co charytatywnie i jeśli doktor będzie zadowolony to będę miał pracę. Zadania dostaje zróżnicowane. Na początek dostałem płytkę drukowaną z dwoma mikrokontrolerami i polecenie opracowania procedury testowej dla elektronika, który je robi. Teraz piszę przenośny (windows linux) moduł do rysowania wykresów funkcji.

Analizator stosu doczekał się czegoś co można określić betą. Czyli u mnie działa i robi to co ma robić, ale nie został jeszcze należycie przetestowany i nie doczekał się wdrożenia. Wrzuciłbym cały kod, ale jest go nieco za dużo, więc tylko najciekawsze fragmenty.

Radzi sobie zarówno ze zwykłymi funkcjami jak i wywołaniami wirtualnymi.
Wymogiem jest aby ramka stosu była skonstruowana zgodnie z tym co opisałem wcześniej.
Wynikiem działania są kolejne adresy powrotne.

Wydobycie aktualnego BP i adresu powrotnego:

void GetCurrentFrame(void * basepointer, void * retaddr)
{
 __asm
 {
  mov eax, ebp
  mov eax, [eax]
  mov basepointer, eax
  mov eax, ebp
  add eax, 0x4
  mov eax, [eax]
  mov retaddr, eax
 }
}

Wydobycie kolejnej ramki:

bool GetNextFrame(void * basepointer, void * retaddr)
 if (0 == *(unsigned int *)basepointer)
 {
  return false;
 }
 else
 {
  __asm
  {
   mov eax, basepointer
   add eax, 0x4
   mov eax, [eax]
   mov retaddr, eax
   mov eax, basepointer
   mov eax, [eax]
   mov basepointer, eax
  } 
  return true;
 }
}

Wydobycie adresu bazowego (o tym już pisałem wcześniej):

void GetBaseAddress(unsigned int & baseAddr)
{
 HMODULE proces = GetModuleHandleA(0);
 baseAddr = (unsigned int)proces;
}

Na początku należy wywołać GetCurrentFrame, potem w pętli GetNextFrame. Adres bazowy można wyciągnąć w dowolnym momencie.
Osobiście ubrałem to sobie w klasy, a ten kod (jak wspomniałem) jest tak na szybko uproszczony, żeby się go dało zaprezentować na tym blogu.

Na koniec chciałbym życzyć wszystkim aby rok 2010 okazał się owocniejszy od wszystkich minionych.

PS.
Właśnie odkryłem, że blogger zapisuje sobie datę utworzenia posta, a nie publikacji. Data publikacji 01.01.2010.

Analiza stosu i funkcje wirtualne

Dziś garść informacji o tym jak działają funkcje wirtualne.

Przede wszystkim dla tych co nie wiedzą czym jest funkcja wirtualna źródła: [1],[2] i [3].

O tym jak działa wywołanie funkcji i jak istotną rolę w tym procederze pełni stos napisałem tutaj.

Przykładowy kawałek kodu w C++:

class A {
public:
 virtual void fun();
 __declspec(noinline)  void fun2();
}; 
class B : public A {
public:
 virtual void fun();
};
int main(int argc, char * argv[])
{
 A * a = new A();
 A * b = new B();
 a->fun();
 b->fun();
 a->fun2();
 b->fun2();
}

Wywołania klasyczne:

; 36   :  a->fun2();
 mov eax, edi
 call ?fun2@A@@QAEXXZ    ; A::fun2
; 37   :  b->fun2();
 mov eax, esi
 call ?fun2@A@@QAEXXZ    ; A::fun2

Wywołania wirtualne:

Po kompilacji:
; 26   :  a->fun();
 mov eax, DWORD PTR [edi]
 mov edx, DWORD PTR [eax+4]
 mov ecx, edi
 call edx
; 27   :  b->fun();
 mov eax, DWORD PTR [esi]
 mov edx, DWORD PTR [eax+4]
 mov ecx, esi
 call edx

Przy rozwiązaniu statycznym:
1. do rejestru eax ładowany jest adres obiektu, czyli wskaźnik this,
2. wykonywana jest instrukcja call z adresem funkcji fun2.

W przypadku wirtualnym:
1. do rejestru eax ładowane są pierwsze 4 bajty obiektu,
2. do rejestru edx ładowana jest pamięć spod adresu eax + 4,
3. do rejestru ecx ładowany jest adres obiektu, czyli wskaźnik this,
4. wykonywana jest instrukcja call z zawartością rejestru edx.

Na co tu zwrócić uwagę?
1. przy wywołaniu statycznym adres funkcji jest na stałe zapisany w kodzie,
2. przy wywołaniu wirtualnym adres funkcji jest ładowany z pamięci,
3. adres funkcji wirtualnej znajduje się w tablicy metod wirtualnych
4. adres tej tabeli jest zapisany jako pierwsze pole w obiekcie.

Tak to wygląda na stosie:

EBP -0xXX -0x4 0x0 +0x4 +0x8

Co lokalne lokalne oldBP retAddr Parametry funkcji

Rejestr <-ESP <-EBP

Dokładnie tak samo jak w przypadku statycznym.

Pod adresem powrotnym znajduje się opcode ff To jest dwubajtowa instrukcja. Jeden na ff i jeden na parametr. Dokładny opis wszystkich instrukcji i parametrów można znaleźć w [4] i [5].

Jak te informacje zamienić na adres funkcji ?
Jeszcze nie wiem, ale mam dwa pomysły:

1. Wszystko wskazuje na to, że poszukiwana wartość zapisana jest jedynie w tablicy metod wirtualnych. Można pokusić się o analizę kodu wywołania pod kątem indeksu metody w tablicy. Mając ten indeks wystarczy odczytać [[this]+indeks].
2. Można też olać dokładny adres funkcji i zapisać sobie jedynie zawartość retAddr. Jeżeli mamy adres 0x01234568 oraz wiemy, że funkcja a - 0x01234000 i b - 0x01235000, to jasne jest, ze była to funkcja a.

Pierwsze rozwiązanie jest fajne, bo daje nam na talerzu to czego chcemy.
Drugie rozwiązanie jest fajne, bo:
a. działa nie zależnie od tego czy wywołanie jest statyczne czy dynamiczne,
b. powinno działać nie zależnie od użytego kompilatora, czy wybranych ustawień budowania

Wniosek ?
Rozwiązanie drugie jest wyborem lepszym. Jest prostsze w implementacji i bardziej uniwersalne. Będzie wymagało jednak stworzenia dodatkowego narzędzia, które zamieni zapisane dane na adresy funkcji.

Źródła:
1) Wikibooks - Funkcje wirtualne
2) Wikipedia - Metoda wirtualna
3) What is a "virtual member function"?
4) Intel Instruction Set A-M
5) Intel Instruction Set N-Z

Reinstalacja Windowsa

Postanowiłem przeinstalować system na laptopie. Do tej pory był zainstalowany Windows 7 RC 1 x64 Ultimate PL i muszę powiedzieć, że byłem z niego bardzo zadowolony. Teraz zainstalowałem Windows 7 RTM x64 Profesional EN. Na początek update, sterowniki prawie do wszystkiego zainstalowały się same. Nie działa kilka drobnostek w stylu kamery i kilka klawiszy specjalnych. Obowiązkowy restart komputera i …

Aero się nie włączyło. Co jest ?!

Przeszukałem wszystkie opcje wydajności i wyglądu, lipa. W końcu spytałem się kryształowej kuli i o to co znalazłem: link
Otóż należy:
1) Otworzyć Menu Start
2) Wpisać Aero
3) Wybrać pozycję Find and fix problems with transparency and other visual effects
4) Kliknąć Next
5) Jeśli mamy szczęście to cieszymy się prześlicznym interfejsem Windowsa 7 (czytaj u mnie zadziałało).

Dumny i pełen optymizmu zainstalowałem Visual Studio 2008 Pro, MSDN, Service Pack 1 do VS oraz DX SDK, a następnie postanowiłem poszukać materiałów na temat tablic metod wirtualnych (ostatecznie chcę zrobić tą analizę stosu i podzielić się wiedzą tutaj na blogu :) ). Na szybko stworzyłem projekcik do celów eksperymentalnych, build i …

Linker oświadczył mi, że nie może znaleźć kernel.lib. Z ust wyrwało mi się "WTF ?!" tylko nieco bardziej swojsko i soczyście.

Poszukiwania z google zaowocowały tym linkiem. Zgodnie z poradą poszukałem klucza:
HKEY_CURRENT_USER\SOFTWARE\Microsoft\MicrosoftSDKs\Windows\CurrentInstallFolder.
Niestety nic z tego, nie było takiego wpisu.

Odkryłem, że zainstalowane zostało SDK tylko w wersji x64. Postanowiłem zainstalować najnowsze SDK w wersji 7.0.
Ściągnąłem te 1.4 GB, jednak przy próbie instalacji dowiedziałem się, że nic z tego, bo to nie jest SDK dla systemów x64 :(

Wywaliłem Visual Studio, zainstalowałem ponownie. Tym razem zostawiłem domyślne opcje, wyleciały tylko opcje Crystal Report i …

Działa :)

Postanowiłem jednak ściągnąć to SDK 7.0 tym razem w wersji dla x64. Zainstalowałem i …

Tak tak, i nie działa. Konkretniej to nie działa aplikacja Windows SDK Configuration Tool mająca za zadanie skonfigurowanie Visual Studio tak aby korzystało z wybranej wersji. Działanie kończy się objawieniem komunikatu:
Your system does not have visual studio 2005 or visual studio 2008 installed.
Rozwiązanie znów przyniósł google: link. Należy odpalić linie komend z Menu Start/Microsoft Windows SDK 7.0/CMD Shell i wykonać WindowsSdkVer.exe -version:v7.0.

I w ten o to sposób udało mi się przeinstalować Windowsa i skonfigurować go do podstawowego użytku.

Zmiany

Życiowe zmiany.

Po pierwsze, o tym już pisałem, dnia 28 października 2009 roku ukończyłem studia. Mam tytuł magistra inżyniera informatyki, specjalność inżynieria oprogramowania i systemy sieciowe.

Po drugie, dnia 31 października 2009 roku mój największy dotychczasowy projekt (ponad 8 lat ciężkiej pracy) osiągnął status pełnej wersji. Tadam! Tadam! 1.0 !!! Teraz zostało mi tylko go pielęgnować i czerpać korzyści.
Ponieważ to może nie być oczywiste to wyjaśnię, że chodzi o małżeństwo ;)

Po trzecie, udało się w końcu otrząsnąć po obronie i ślubie, zabieram się za poszukiwanie pracy. Trochę mnie to przeraża, bo trudno mi ocenić moje kwalifikacje. Z jednej strony znam bardzo dobrze C++, wiem co nieco o inżynierii, potrafię korzystać z asemblera, niestraszny mi brak IDE, miałem też romans z Pythonem, Javą i SQL. Z drugiej strony brak mi doświadczenia. Poza C++ w zasadzie programowałem dość sporadycznie.

Do następnego razu. Planuje sprawdzić jak to jest z tą kolejnością globalnych oraz napisać na temat analizy stosu przy wywołaniach metod wirtualnych, tylko jakoś czasu nie mam.

Analiza stosu i mapa pliku

Ten post miał pójść w piątek (23 X), ale niestety w piątek rano zostałem poinformowany o terminie obrony, tj środa 28 X. W sumie to stety, bo od wczoraj jestem magister inżynier informatyki specjalizacja inżynieria oprogramowana i systemy sieciowe.

Sama obrona to w sumie dość sympatyczne przeżycie, gdyby nie jeden drobny detal, OGROMNY STRES!

A teraz do rzeczy. Jak ustalić adres aktualnie wykonywanej funkcji ? Należy przeanalizować zawartość stosu. Czym jest stos, mam nadzieję wszyscy wiedzą. Nie wszyscy natomiast muszą wiedzieć co w praktyce dzieje się ze stosem i rejestrami w momencie wywołania funkcji. Na początku wykonywany jest kawałek kodu nazywany prologiem funkcji, ma on na celu przygotowanie na stosie tzw ramki:

push ebp
mov ebp, esp
sub esp, 0xXX

W tym momencie stos wygląda tak:
-0xXX ... <- ESP
-0x4 ...
0x0 oldBP <- EBP

Czyli EBP wskazuje na poprzednią zawartość rejestru EBP. ESP wskazuje gdzieś, przy czym gdzieś nie jest gdziekolwiek, ale zależy od rozmiaru zmiennych lokalnych funkcji, 0xXX to właśnie ten rozmiar w bajtach. Warto tu zwrócić szczególną uwagę, iż wszystkie zmienne lokalne funkcji mają adresy od EBP - 4, aż do EBP - 0xXX. Takie rozwiązanie pozwala m.in na prostą organizację rekurencji.
Po wykonaniu prologu wykonywane jest ciało funkcji. Gdy funkcja się kończy rejestr ESP jest odpowiednio modyfikowany o wartość 0xXX, a EBP popowane. Pamięć użyta pod zmienne lokalne nie jest w żaden sposób czyszczona, ale jest traktowana jako wolna przestrzeń.

To dzieje się po wywołaniu funkcji. Zanim jednak do tego dojdzie trzeba ją jakoś wywołać.

mov eax, [ebp-4]
push eax
call test
add esp, 4

Stos:

0x0 oldBP <- tutaj będzie wskazywać EBP po wykonaniu prologu
0x4 retAddr
0x8 [ebp-4]

Na początek do EAX ładowana jest pamięć spod adresu EBP - 4, czyli wartość zmiennej lokalnej. Następnie wartość ta jest odkładana na stos, jest to parametr wywoływanej funkcji. Wywołanie wykonuje się instrukcją call. Instrukcja ta robi dwie rzeczy, odkłada na stos rejestr EIP oraz wykonuje skok pod podany adresy. Ponieważ rejestr EIP zawsze zawiera adres następnej instrukcji do wykonania, odłożona wartość jest adresem pod jaki należy powrócić gdy funkcja się zakończy, w tym wypadku jest to usunięcie ze stosu przekazanego parametru.

Wyciągamy ze stosu adres powrotu, [EBP + 4] i odczytujemy co siedzi w pamięci:

e8 zz yy xx ww 83 blah blah
Dokładnie pod adresem powrotnym jest wartość 83, która nie jest szczególnie ciekawa, bo to opcode dodawania. Interesujące są natomiast cztery poprzednie bajty, czyli wartość wwyyxxzz, jest to offset skoku. Adres pod jaki wykonany został skok, czyli teoretyczny adres funkcji, uzyskuje się po dodaniu offsetu do wartości retAddr.

Tak to właśnie wygląda w teorii, w praktyce kompilatory oszukują :) Otóż MSVC 2008 Debug umieszcza instrukcję JMP pod adresem dla CALL. Czyli mamy tak: CALL -> JMP -> Wywoływana funkcja.

JMP w pamięci wygląda tak: e9 zz yy xx ww. Podobnie jak przy callu jest to offset, tym razem należy dodać adres jmp'a powiększony o 5 aby uzyskać oczekiwany adres funkcji.

No na razie o stosie wystarczy, teraz parę słów o mapowaniu PE do pamięci wirtualnej.

Ostatnio napisałem, że w pliku z mapą są wszystkie informacje potrzebne do identyfikacji funkcji na podstawie jej adresu. No więc nie jest to do końca prawda. Wraz z systemem Vista Beta 2 wprowadzono technologię Address space layout randomization. Robi ona dokładnie to na co wskazuje nazwa, czyli miesza przestrzeń pamięci, aby utrudnić życie piszącym wszelkiej maści exploity.

Przykładowy wpis z mapy:
" 0002:00000540 ?test@@YAXAAVFrame@@@Z 00411540 f TestApp.obj".

Listing disasemblera:
"void test(Frame & frame)
{
013C1540 push ebp
013C1541 mov ebp,esp"

Jest problem, adres 0x013C1540 ma się nijak do 0x00411540 (znaczy końcówkę mają wspólną). Rozwiązania znalazłem dwa:
1) przełączyć flagę /DYNAMICBASE. Wyłączy to ASLR i adresy będą się pokrywać. Sprawdzone, działa pod 7.
2) znaleźć adres pod jaki windows załadował exeka i na tej podstawie ustalić jaka jest wartość w mapie. Również sprawdzone, działa pod 7.

W celu ustalenia adresu bazowego procesu można posłużyć się funkcją GetModuleHandleA. Zwraca ona wartość typu HMODULE, a przyjmuje łańcuch znakowy z nazwą poszukiwanego modułu. Przekazanie jej wartości NULL sprawi, że poszuka ona adresu bazowego procesu wywołującego. Zwrócony HMODULE to poszukiwany przez nas adres. Nie wiem niestety jak to wygląda w przypadku aplikacji 64 bitowych. Zakładam, że HMODULE jest wtedy typem 64 bitowym, ale ...

Uzyskany w ten sposób adres bazowy, w tym wypadku była to wartość 0x13B0000, odejmujemy od adresów pod jakie wykonywane są skoki. Wynikiem jest offset, czyli dla funkcji test 0x11540. Offset ten należy zwiększyć o adres bazowy podany w mapie, 0x400000, aby uzyskać dokładny adres funkcji. Ostatecznie otrzymamy 0x00411540.

Logger

Miała miejsce długa przerwa, ale nie jest źle. Ostatecznie to będzie drugi wpis w tym miesiącu ;)

Oddałem pracę i dostałem lenia. Kompletnie nic mi się nie chciało. Chyba musiałem trochę odreagować. Powoli jednak zbieram się do roboty, choć nieco straszy mnie obrona. Kochana uczelnia raczyła mnie postawić w bardzo nieprzyjemnej sytuacji. Termin egzaminu ma być za tydzień, czyli 26 - 27 X, ale na dzień dzisiejszy nikt nie wie kiedy dokładnie. Co za tym idzie nie jest znany skład komisji. Boję się, że termin wypadnie na poniedziałek, a poinformują mnie w piątek, oczywiście po południu. I jak ja niby mam się przygotować ?

Od dawna zastanawiałem się nad poprawieniem loggera. To co stworzyłem na początku projektu było skuteczne, poza tym miało same wady. Rozwiązanie to jest oparte o wzorzec singletona, do tego bardzo zależało mi na łatwym formatowaniu a'la strumienie (operator <<) oraz na śledzeniu przebiegu wywołań funkcji. Wyszło rozwiązanie paskudne w użyciu i co znacznie gorsze, nie spełniające do końca moich oczekiwań.
Problemem okazało się zbieranie informacji o stosie. Automatyczna zamiana adresu funkcji na jej nazwę nie jest zadaniem trywialnym. Coś takiego można znaleźć na blogu Gynvaela Coldwinda: w tym wpisie. Sam wymyśliłem nieco inne rozwiązanie, również oparte o makra. W skrócie mniej asemblera, więcej C++. Tylko czy ja mam ochotę przejrzeć 37 linii kodu i pozamieniać definicje wszystkich funkcji w makra ? Wymyśliłem więc, że trzeba ręcznie opatrzyć każdy zapis do logu informacją o tym skąd pochodzi. Sprawa jest dosyć prosta, posłużyłem się standardowym makrem __FUNCTION__. Nieco kłopotliwa jest nazwa klasy w przypadku metod. Rozwiązałem to tak:

#define __CLASS__ "Nazwa klasy"
#define HERE __CLASS__ << "::" << __FUNCTION__

No i działa. Brakuje jednak danych stosu, czyli informacji o stanie aplikacji gdy doszło do powstania wpisu. Fajnie by też było mieć zarejestrowane trochę danych o tym co działo się wcześniej.

Zadałem sobie jednak fundamentalne pytanie, czy umieszczanie nazw funkcji i klas w kodzie ma sens ? No i wyszło mi, że nie. Wracamy do punktu wyjścia, jak zamienić adres funkcji na nazwę ? Linker z Visual Studio ma taki fajny przełącznik /MAP. W efekcie powstaje plik tekstowy chyba ze wszystkim co nam do szczęścia potrzebne, tj adres w pliku, adres w obrazie, nazwa funkcji, atrybuty, plik z którego dana funkcja pochodzi.

Na koniec zabawny błąd:

Logger LoggerInstance;
std::fstream logFile;
Logger::Logger()
{
 logFile.open("log.txt", std::fstream::out);
...
}

Otwarcie pliku kończy się wyjątkiem przy próbie odczytu spod adresu 0. Czemu? Bo w momencie wywołania tego konstruktora obiekt logFile jeszcze nie powstał ;) Trzeba zamienić kolejność.

std::fstream logFile;
Logger LoggerInstance;

Precompiled headers, Visual oraz smart pointers

Po lekturze komentarzy pod Postem Precompiled header. Postanowiłem wypróbować radę raffimoni. W skrócie warto. Raz, że upraszcza to kod. Dwa, że czas budowania spadł z 107250 ms na 91016, czyli 15%.

Mój silniczek ma błędy z którymi nie mogę sobie poradzić przy użyciu Eclipse'a. Przeniosłem, więc projekt do Visual Studio 2008 ze względu na ichni debugger. No i wyszło parę ciekawostek:
* Generalnie kod się kompilował, konieczne były drobne poprawki, np wstawki asm.
* Visual wrzuca wszystkie pliki obiektowe do jednego katalogu. Jeżeli istnieją dwa pliki o tej samej nazwie to je radośnie nadpisuje. Trzeba ręcznie zmienić nazwę pliku obiektowego dla danego cpp.
* Pomieszanie new i delete w wersji z i bez [] powoduje podniesienie wyjątku systemowego.

Ten ostatni punkt jest dość ciekawy. Całkiem możliwe, że to właśnie to jest winne temu, że Eclipse wychwytywał błędy. Tak czy siak postanowiłem się zabezpieczyć i wprowadzić inteligentne wskaźniki, które zajmą się prawidłowym zwolnieniem pamięci. Powstały, więc dwa szablony:
* SmartPtr,
* SmartArray
Kodu nie podam, bo nic odkrywczego nie opracowałem. Jeżeli ktoś poszukuje jakiegoś wzorca to polecam boost i "C++ Szablony: vademecum profesjonalisty" David Vandevoorde i Nicolai M. Josuttis.

Praca magisterska - Mission accomplished !

Skończyłem pisać pracę magisterską. Leży sobie teraz obok mnie kilka wydrukowanych egzemplarzy i czeka na oddanie do katedry. Tytuł "System interaktywnej wizualizacji dynamicznych scen 3D dla potrzeb symulacji komputerowej" w skrócie "silnik graficzny". Praca ma 104 strony w wersji dla uczelni, 115 ma mój egzemplarz. Samo przygotowanie treści i obrazków zajęło mi około 2-3 tygodni, ale do tego jeszcze doszły poprawki zasugerowane przez promotora i narzeczoną (filolog, uwierzcie czepia się strasznie), co zaowocowało przedłużeniem prac do miesiąca. Praca pisana w LaTeXu, jako edytora użyłem eclipse galileo z pluginem texclipse, "kompilator" to miktex bodajże w wersji 2.7.

Projekt silniczka wyszedł tak sobie. Nie jestem zadowolony. Nie udało mi się zrobić wszystkiego co chciałem. Przede wszystkim nawaliło ładowanie plików md5, w efekcie nawet nie wiem, czy rozwiązanie animacji szkieletowej jest ok. Nie zrobiłem normal mappingu. Nie ma przeźroczystości. Za to udało mi się zrobić:
* deferred shading,
* shadow mapping,
* instancing,
* vertex blending,
* height mapping,
* dość mocno odseparowałem klienta od API, więc teoretycznie silnik jest wieloplatformowy :),
* GUI.

To może wydawać się nie wiele, ale ogrom pracy poszedł w uzyskanie przenośności. Poza tym, to był mój pierwszy prawdziwy projekt z grafiki 3d. Startując miałem średnie pojęcie o tym jak funkcjonuje DirectX. W sumie 31 tysięcy niepustych linii kodu (ogólnie jest 37 tysięcy), 17 shaderów, 1200 godzin pracy. Generalnie uznaję ten projekt za sukces, ale światła dziennego to on nie ujrzy ;)

Wnioski odnośnie LaTeXa dla potomnych:
* Eclipse Galileo ma funkcję sprawdzania poprawności kodu. Trzeba tylko dostarczyć mu słownik. Instrukcja choćby tutaj: http://www.jakubiak.eu/2008/06/eclipse-i-sownik-jzyka-polskiego.html. UWAGA! Sam nie korzystałem z takiego rozwiązania. Plugin Texclipse potrafi wykorzystać słownik Aspell do sprawdzania poprawności pisowni. Niestety pomimo chęci nie udało mi się znaleźć wspólnego kodowania plików dla eclipse'a i aspella. Pewnie jakoś się da, ale ... OpenOffcie całkiem nieźle poradził sobie z korekcją wszystkich literówek i to bezpośrednio na plikach tex (choć najpierw zawsze robiłem backup) ;)

* Gdyby ktoś potrzebował zamienić LaTeXa w coś innego niż PDF, to można skorzystać z polecenia oolatex, które stworzy plik ODT. Program znajduje się w paczce miktexa. Jeżeli nie działa to trzeba go poprawnie skonfigurować, np zainstalować javę i podać poprawne ścieżki w pliku konfiguracyjnym tex4ht. Ponadto będzie potrzebna paczka miktex-zip. Mi się udało, jak pokombinujecie to też wam się uda. Ale od razu powiem, że nie ma się co napalać. Formatowanie wychodzi zmasakrowane. Nie działają linki. Nie ma obrazków, choć na to pewnie da się coś poradzić. Za to jest poprawna treść, błędy pojawiły się tylko dla polskich znaczków w tytułach rozdziałów.

* Do zapisu matmy najlepiej korzystać z paczki amsmath. Potrafi sporo. W zasadzie udało mi się zapisać wszystko co chciałem z numerowaniem takim jak chciałem. Środowiska: equation, gather i cases. Polecenia \nonumber \numberwithin{equation}{section}.

* Przy 100 stronach już widać, że otwarcie dokumentu w OpenOffice trochę trwa. Możliwość rozbicia pracy na kilka plików w LaTeXu jest cudowna. Polecenie \input{}.

* Do listignów użyłem paczki listings. W zasadzie potrafi wszystko, ale nie udało mi się poradzić z jedną sprawą. Górna linia ramki wypadała dokładnie przez środek opisu. Gdyby ktoś chciał zmienić tytuł rozdziału z "Listings" na coś bardziej swojskiego dla polecenia \lstlistoflistings, to ja to zrobiłem tak:
\newpage
\section*{Spis listingów}
\addcontentsline{toc}{section}{Spis listingów}
\markboth{SPIS LISTINGÓW}{}
\newcommand\stdsection{}
\newcommand\stdaddtocontents{}
\let\stdsection\section
\let\stdaddtocontents\addtocontents
\def\section*#1{}
\renewcommand\addtocontents[3]{}
\lstlistoflistings
\let\section\stdsection
\let\addtocontents\stdaddtocontents

* Jest paczuszka nomencl do robienia nomenklatury. Niestety u mnie polecenie mające na celu wypisanie listy symboli nie zadziałało. Ostatecznie posłużyłem się wygenerowanym plikiem NLO z zestawieniem wszystkich symboli. Do wypisania użyłem środowiska tabular z zafiksowanymi szerokościami kolumn. \begin{tabular}{p{3cm}p{12.5cm}}.

* LaTeX nie usuwa sierotek, to jest wyrazów jedno literowych na końcu linii. Może dlatego, że w angielskim nie ma takich wyrazów ? Tak czy siak pomaga polecenie \nolinebreak zaraz po sierotce.

* Odradzam modyfikowanie przerw pomiędzy paragrafami \parskip. Mam wrażenie, że wartość ta jest używana nie tylko przy okazji nowego akapitu. Znacznie lepszy efekt wizualny da użycie wcięć \parindent. Nie warto też walczyć z brakiem wcięcia w pierwszym akapicie. W gruncie rzeczy tak jest lepiej.

* Nic tak nie poprawia czytelności jak wyraźna przerwa między A i B. Żeby zrobić pustą stronę bądź linię należy posłużyć się takim zapisem:
\newpage/line
\mbox{}
\newpage/line

Praca magisterska, md5 i nokia 3120 clasic

Dawno nic nie napisałem, ale prawda jest taka, że nie było o czym. Założenie było takie, że piszę tutaj o tym co uda mi się stworzyć w świecie programowania, a od ostatniego posta nie powstało nic. Aż do dziś ;)

Przez ostatnie niemal 2 tygodnie pisałem swoją pracę magisterską. Wciąż jestem w polu, ale w sumie wygląda to coraz lepiej. Już dawno postanowiłem, że napiszę ją w latex'u i jak na razie nie żałuje decyzji. Pisze się naprawdę sprawnie. Najfajniejsze jest to, że nie ma problemów z aktualizacją obrazków i bardzo łatwo jest rozbić cały dokument na osobne piliki. Boli tylko brak sprawdzania pisowni. Jakoś nie udało mi się tego skonfigurować. Teoretycznie Eclipse z dodatkiem Texclipse potrafi skorzystać ze słowników aspell. Niestety sprawa robiła się o kodowanie dokumentu. Nie jest to na szczęście zbyt bolesne, bo wciąż można skorzystać z innego softu, choćby open office'a.

Zanim zacząłem pisać pracę walczyłem jeszcze trochę z tym ładowaniem plików md5. Lipa. Coś mi tu umyka. Nie wiem, czy to błąd w kodzie, czy nie zrozumienie jakiegoś aspektu, np jak posługiwać się kwaternionami. W każdym bądź razie lipa. Udało mi się doprowadzić do tego, że szkielet mojego modelu animował się poprawnie. Jednak gotowiec ma coś nie tak z orientacją. Pozycje są poprawne. Brakło mi czasu, żeby problem rozwiązać.

Co do tego wszystkiego ma Nokia 3120 clasic ? Ano jest pretekstem do spłodzenia tego posta. Otóż mój szanowny rodziciel, wszedł w posiadanie tego modelu, drogą podpisania umowy z jednym z operatorów sieci gsm w Polsce. Telefon potęgą nie jest, czego się zresztą spodziewać po gratisie. Nie spodziewałem się jednak, że aż tak.
Wydawałoby się prosta sprawa skopiować kontakty z jednego telefonu na drugi. Poprzednik to sony erricson. Oba telefony posiadają moduł bluetooth. No to kopiujemy całą listę przez BT i po bólu ;)
Otóż nie. SE potrafi wysłać wszystkie kontakty na raz w formie pliku vcf. Nokia natomiast takiego pliku zrozumieć nie potrafi. Grrr.
Szybko okazało się, że problemem jest to iż jest to lista. Pojedynczą wizytówkę można przesłać. Czyli co, na SE strzałka w dół > opcje > wiecej > zaawansowane > wyslij > bt, Nokia > akceptuj > zapisz. I tak 380 razy. Masakra.
Po długim kombinowaniu wyszło, że takie wizytówki można wysyłać także z komputera. Byleby nie była to lista, a pojedyncze wpisy. Na szybko napisałem kawałek kodu do konwersji listy na osobne pliki.

Nie zagłębiałem się przy tej okazji nadmiernie w strukturę pliku .vcf. Także raczej nie należy się na to powoływać. Programik zadziałał zgodnie z oczekiwaniem, a cała operacja zakończyła się pełnym sukcesem, dając tym samym Nokii pierwszą szansę na dłuższe testy u mnie w domu. Wcześniej była tylko jedna i wytrzymała jeden dzień, zanim mnie szlag trafił ;)

/*
 * main.cpp
 *
 *  Created on: 2009-08-28
 *      Author: Adam Śmigielski
 *      E-mail: adam.smigielski@gmail.com
 *   Copyright: Adam Śmigielski
 */

#include <fstream>
#include <iostream>
#include <stdio.h>

using namespace std;

int main(int argc, char * argv[])
{
 const char * filename = 0;
 if (2 >= argc)
 {
  filename = argv[1];
  cout << "Plik: " << filename << endl;
 }
 else
 {
  cout << "Podaj nazwe pliku" << endl;
  return 1;
 }

 fstream in;
 fstream out;
 in.open(filename, fstream::in);
 if (false == in.is_open())
 {
  cout << "Plik nie istnieje" << endl;
  return 2;
 }
 else
 {
  cout << "Otwarto plik" << endl;
 }

 char buffer[256];
 unsigned int count = 0;
 char name[] = "result\\xxxx.vcf";
 char rev[] = "REV:20090828T071515Z";
 int revsize = strlen(rev);

 while (true)
 {
  in.getline(buffer, 256);

  cout << buffer << endl;

  if (0 == strcmp(buffer, "BEGIN:VCARD"))
  {
   sprintf(name + 7, "%04d.vcf", count++);
   cout << "Nazwa pliku: " << name << endl;

   out.open(name, fstream::out);
   if (false == out.is_open())
   {
    cout << "Nie udalo sie otworzyc pliku" << endl;
    return 2;
   }
   else
   {
    cout << "Otwarto plik" << endl;
   }

   out << buffer << endl;
   while (true)
   {

    in.getline(buffer, 256);

    cout << buffer << endl;

    if (0 != strstr(buffer, "X-IRMC-LUID:"))
    {
     out << rev << endl;
    }
    else if (0 == strcmp(buffer, "END:VCARD"))
    {
     out << buffer << endl;
     break;
    }
    else if (0 != strstr(buffer, "TEL:"))
    {
     out << "TEL;CELL:" << buffer + 4 << endl;
    }
    else
    {
     out << buffer << endl;
    }
   }

   out.close();
  }
  else if (0 == strcmp(buffer, ""))
  {
   break;
  }
 }

 in.close();

 return 0;
}

EDIT
Właśnie odkryłem, że mój sprytny sposób na zamieszczanie kodu wyświetla bool'e na czarno. Ehh, już zmienione. Teraz będą zielono niebieskawe :)

Animacja szkieletowa

No temat masakra. Od poprzedniego postu cały czas walczę ze skiningiem. Na dobry początek zawiodły mnie szadery. Z jakiegoś, kompletnie nie zrozumiałego dla mnie, powodu pętla:

for (int i = 0; i < 4; i++)

wykonywała się tylko raz. Później, głównie dzięki przykładowi, zawartemu w Dx SDK, SkinMesh, udało mi się przekonać kompilator, że ta pętla to ma jednak 4 przebiegi. Co było przyczyną problemu wciąż nie wiem.
Następnie odkryłem, że kod (tym razem c++)

if (0 != flag & 1)
{
}
if (0 != flag & 2)
{
}
...
if (0 != flag & 32)
{
}

kompiluje się tylko do jednego, pierwszego, if'a. Cała reszta jest pomijana. Dzieje się tak przy -o0 -g3, a także dla domyślnych ustawień (czyt. bez flagi). Innych ustawień nie sprawdziłem. Nie mam pojęcia o co gcc chodziło. Czyżby bug ;)
Wyszło jeszcze kilka błędów. Wczoraj wieczorem udało mi się wyświetlić model w bind pose, ale ... . Ale wynik był zniekształcony. Geometria z całą pewnością jest poprawna, bo po ustawieniu macierzy jednostkowej wygląda jak należy. Czyli SUKCES, udało mi się w końcu zmusić wszystko do działania, a błędy muszą wynikać z nieprawidłowych macierzy.

Od początku idea aby wysyłać do karty "globalne" macierze dla każdej kości wydał mi się dziwny. Przecież to się musi rozjechać. Pomyślałem jednak, że może te wagi odpowiednio modyfikują transformację. Dzisiaj rano postanowiłem to przeanalizować matematycznie. No i oczywiście okazało się, że jest źle.

Weźmy taki przykład:
Punkt p [1, 1, 1], zaczepiony do dwóch kości, do obu po równo, czyli wagi 0,5
Kość A [0, 0, 0] zorientowana neutralnie (macierz jednostkowa)
Kość B [0, 0, 2] zorientowana neutralnie

p' = 0,5 * A * p + 0,5 * B * p
p' = [0,5 0,5 0,5] + [0,5 0,5 (0,5 * (1 + 2))] = [1, 1, 1,5]

A powinno wyjść [1, 1, 1]. Co z tym zrobić ? Bardzo UWAŻNIE przeczytać cokolwiek na ten temat. Na przykład ten temat na warsztacie. Odkryjemy w ten sposób, że macierze mają być "globalne", ale muszą uwzględniać pewien myk.

Na koniec screen, z bind pose:

Z Engine

Model pochodzi ze wspomnianej już strony: link

MD5 mesh loader

Przebrnąłem przez napisanie funkcji ładującej model z pliku md5.

Na początek linki:
1 Eksporter do Blendera i modele
2 Opis formatu
3 Opis jak ładować z tego formatu
4 Temat na Warsztacie

A teraz moje uwagi i wnioski:
1. Dane joint'ów zapisane są względem początku układu, a nie rodzica. Aby wyznaczyć transformację względem rodzica należy skorzystać z tych równań:
p * q = g => q = p^-1 * g
p + v = g => v = g - p
p - parent, czyli dane rodzica
g - global, czyli dane zapisane w pliku
q i v - to kwaternion i wektor
p^-1 to oczywiście inwersja kwaternionu rodzica
2. Kwaterniony są zapisane w formie samych osi, bez w. Ja dowiedziałem się o tym z [3]. Skorzystano tu z faktu, że długość kwaternionu musi być równa 1. 1 = w*w + x*x + y*y + z*z. Chyba łatwo wyznaczyć ile wynosi w. Pamiętać tylko trzeba, że nie należy wyciągać pierwiastka kwadratowego z liczb ujemnych.
3. Pozycje wag są zapisane względem kości i to z uwzględnieniem orientacji. Aby wyznaczyć finalną pozycję, trzeba najpierw obrócić pozycję wagi o orientację kości. Dopiero tak obróconą translację możemy zsumować z pozycją kości. Wzór na rotację [3] punktu o kwaternion: a' = q * a * q^-1. Przy czym a i a' to kwaterniony z częścią rzeczywistą równą pozycji punktu i urojoną 0, trzeba o tym pamiętać.
4. Format nie przechowuje informacji o normalnych. Wyznacza się je oczywiście przy użyciu mnożenia wektorowego (cross product). Trzeba tu jednak wziąć pod uwagę, że indeksy wierzchołków są w CCW. To mnie zaskoczyło, ale tak mi wyszło. Nie wiem jednak czy to przypadkiem nie jest "wina" eksportera.
5. Plik ma 682 linijki. Czyli kupa roboty.

Optymalizcja gemetrii ciąg dalszy

Ze względu na pewne wątpliwości odnośnie licencji dla NvTriStrip, zdecydowałem się poszukać innego rozwiązania.

Założyłem nawet temat na Warsztacie.

Ostatecznie zdecydowałem się na Vertex cache optimization librar.

Efekty działania są jak najbardziej zadowalające.

Optymalizacja geometrii

Ponieważ wczytany model zmasakrował moją aplikację, postanowiłem zainteresować się tym jak go zoptymalizować.

Jak na razie postanowiłem sprawić, aby stał się bardziej "cache friendly". Wyjaśnię co to znaczy, bo okazało się, że kolega programista nie zrozumiał.

Otóż procesor graficzny GPU, ma wbudowaną pamięć tzw. vertex cache. Przechowuje w niej wyniki obliczeń dla ostatnich N wierzchołków. Kluczem do ponownego użycia już otrzymanych wyników jest użycie indeksowanej geometrii.

Warunkiem jest tu jednak, aby już obliczone wierzchołki nie "wypadły" z cache'u. Odpowiednia organizacja bufora indeksów nie jest zadaniem trywialnym, postanowiłem więc skorzystać z gotowca: biblioteka NvtriStrip. Do biblioteki jest przykład użycia: NVTriStrip Test App.

Co	przed	po
Ilość narysowanych obiektów:	28673	28673
Średni czas jednego draw call'a [ms]:	0.0688297	0.0721264
Średni czas jednej klatki [ms]:	13.7571	11.497
Ilość draw call'i na klatkę:	8	8
Średni fps:	68.3995	81.8658

Co z tego wynika ?
1) Relacja pomiędzy fps, a czasem renderowania klatki jest wyraźna. Czyli dobrze, bo to znaczy, że system nie spędza za dużo czasu poza samym renderingiem.
2) Draw call, o ile wiem jest wykonywany asynchronicznie. CPU nie czeka na jego zakończenie. Pomiary nijak się mają do czasu rysowania całej klatki. To też dobrze wróży, bo oznacza, że CPU ma lepsze rzeczy do roboty niż zlecanie kolejnych zadań do narysowania. Mam tu też pewien, spory jak sądzę, zapas mocy.
3) Zyskałem ~2.3 milisekundy. Co znaczy, że optymalizacja geometrii dała zysk rzędu 16 %. Jednak ta wartość jest zakłamana, ponieważ pixel shader do lekkich nie należy. Uruchomiłem aplikację w perfHud, ale za dużo nie udało mi się wyciągnąć sensownych informacji. Wiem tylko, że % VS z 40 spadł do 30. Niestety nie za bardzo wiem jak to dokładnie interpretować.
4) 1 + 2 + 3 moja grafika ledwo zipie ;)

Instancing ciąg dalszy

Tak jak sądziłem przesunięcie analizy kolejki obiektów do wyrenderowania o jeden stopień wyżej poprawiło nieco osiągnięty wynik:
Ilość narysowanych obiektów: 28673 - 28673
Średni czas jednego draw call'a: 0.0054 ms - 0.00342 ms
Średni czas jednej klatki: 19.02 ms - 12.46 ms
Ilość draw call'i na klatkę: 8 - 8
Średni fps: 49.3 - 69.9

To dobrze. Chciałoby się podnieść ten etap jeszcze o jeden poziom wyżej, ale to chyba nie możliwe. Założenie jest takie, że dla każdego punktu obserwacji (kamery, światła) do kolejki trafią inne obiekty, więc ich wspólna analiza nie za bardzo wchodzi w grę.

Mój początkowy zachwyt nad tymi wynikami spotkał się dziś z lodowatym prysznicem :) Skończyłem pisać ładowanie plików ASE i zamieniłem sześcian na sześcian z wyciętym środkiem. Źródło inspiracji: ten projekt. Spodobał mi się, bo ten w sumie prosty model ma tę cechę, że rzuca cień sam na siebie. Model i render wykonany w blenderze przeze mnie:

Z Engine

Jak się jednak okazało, model wcale taki prosty nie jest. 97 trójkątów i 105 wierzchołków !!! Pewnie dałoby się to nieco poprawić, ale na drastyczne zmiany bym nie liczył. Tak czy siak, z 70 fps zrobiło się przerywane ~25 (trochę płynnie, trochę szarpie)

Literatura:
Opis formatu ASE
Plugin do blendera

Instancing

Dziś udało mi się zakończyć kod odpowiedzialny za stosowanie instancing'u.
Scena złożona z 4096 klocków, oświetlona światłem punktowym z wyliczaną dynamicznie mapą cienia (cube).

Klasyczne podejście:
Ilość narysowanych obiektów: 28673
Średni czas jednego draw call'a: 0.0026 ms
Średni czas jednej klatki: 84.91 ms
Ilość draw call'i na klatkę: 28673
Średni fps: 11.33

Instancing:
Ilość narysowanych obiektów: 28673
Średni czas jednego draw call'a: 0.0054 ms
Średni czas jednej klatki: 19.02 ms
Ilość draw call'i na klatkę: 8 !!!
Średni fps: 49.3

No i tu pojawia się pytanie. 8 razy 0.005 to przecież 0.04 milisekundy, czemu więc klatka trwa 20 milisekund ? To jest bagatela 500 razy dłuższy czas ! Mam taką teorię: bufory z macierzami do transformacji świata są nie optymalnie tworzone i wysyłane do karty.

Czemu tak sądzę ?
1. Aktualizuje shadow mapę
1a. Wyznaczenie macierzy PV
1b. Analiza danych pod kątem batch'y
1c. Przygotowanie bufora z macierzami (macierze są już wyliczone, trzeba tylko je skopiować do bufora)
1d. Ustawienie wszystkiego związanego z shaderami
1e. Draw call
1f. Jeśli został jeszcze jakiś kierunek w cube mapie idź do 1a (czyli 6 razy)
2. Aktualizacja kamery
2a. To samo co dla światła, tylko, że mamy jeden kierunek i 4 mrt.
2b. Rysowanie świateł

Łącznie 7 razy analizuję i kopiuje te same dane do karty graficznej. Konieczne są jednak tylko 2 razy.

Pożyjemy zobaczymy, muszę to sprawdzić, ale upał jest tak nieznośny, że wszystkiego się odechciewa.

Depresja

Dawno nic nie napisałem tutaj na blogu, także witam wszystkich po przerwie.

Co się działo przez ostatnie półtora miesiąca ? Mało. Mój projekt znajduje się w stanie "depresji", czyli nastąpiło ogólne zniechęcenie do jego kontynuacji. Poczucie niemocy jest wszechogarniające. Jedyne co mnie jako tako trzyma to fakt, że mi się śpieszy z jego ukończeniem (obrona mgr inż. , poszukiwanie pracy, ślub - wszystko to do Listopada)

Oto co robiłem przez ten czas:

Podstawy GUI napisane. Przyjąłem model a'la Java, czyli słuchacze - ang Listener, który otrzymuje wszystkie informacje o zmianach statusu powiązanego elementu. elementy mają swoje ID, dzięki temu jeden słuchacz może obsłużyć więcej niż jeden element danego typu. Jest i działa, ale dalsze prace nad tym modułem zostały zawieszone na bliżej nie określony czas.

Sporo zmian związanych z modelem danych. Zmieniłem dziedziczenie na kompozycję w kilku istotnych miejscach. Powstała klasa zasobów bez nazwy. Wprowadziłem materiały, zastąpiły one pomyłkę pod tytułem efekty pixel i vertex. W planach są jeszcze efekty post process. Zmieniłem tez nieco koncepcję samego renderingu. Wszystko to razem wymusiło niemal całkowite przepisanie renderera. Przy okazji wprowadziłem nieco rozsądniejszy mechanizm rysowania: "Batch! Batch! Batch!" ;)

Animacja szkieletowa i instancing. Aktualnie pracuje nad tym jak pożenić ze sobą te dwie technologie. Podstawy są już niemal na ukończeniu, potem poprawki do renderera, wykończenie loaderów dla plików md5 i ase.

A co robiłem dzisiaj ? Heh, znowu skracałem czas kompilacji, źródło inspiracji: Czasy kompilacji gier Zaoszczędziłem 12 sekund.

Precompiled header

Budowanie mojego projektu przekroczyło 150.000 ms. Postanowiłem, więc skorzystać z tej techniki, aby nieco skrócić czas oczekiwania.
Zysk jest całkiem spory, różnica 36 sekund, czyli około 20 %.

A teraz jak uzyskać pre kompilowane nagłówki pod Eclipsem ?
Eclispe z CDT nie posiada narzędzi do obsługi tej techniki, więc zapomnijcie o magicznym przełączniku. Wszystko trzeba zrobić samemu.
Na szczęście GCC automatycznie wykorzystuje pch, o ile one istnieją. Sami budujemy nagłówek i umieszczamy pch w odpowiednim miejscu, a kompilator go znajdzie i wykorzysta.

Jak zrobić nagłówek?
Tworzymy zwykły plik .h i włączamy w nim wszystkie potrzebne pliki nagłówkowe.
Przykład:

#ifndef STD_H_
#define STD_H_

#include <string>
#include <fstream>
#include <sstream>
#include <map>
#include <deque>
#include <vector>

#endif /* STD_H_ */

Jak zbudować nagłówek ?
Do zbudowania nagłówka wywołujemy z linii komend "g++ -opcje -xc++-header -otest.h.gch test.h". W efekcie powinniśmy otrzymać plik test.h.gch.
- test.h to rzecz jasna nazwa pliku
- teoretycznie flaga -x nie jest potrzebna, bo gcc zna rozszerzenie .h, ale jakoś nie za bardzo bez niej chciało działać
- opcje powinny być takie same jak projektu korzystającego z nagłówka

Jak z nagłówka skorzystać ?
- pch zostanie wykorzystany automatycznie
- gcc wykorzysta ten plik, który znajdzie pierwszy, przy czym najpierw sprawdza czy w danym katalogu jest pch, dopiero potem czy jest zwykły plik. Najprościej oba pliki umieścić w tym samym katalogu
- projekt powinien mieć te same opcje co pch
- pch może być tylko jeden na raz

Co zrobić z błędem "calling fdopen: Bad file descriptor" ?
Pch może zostać użyte tylko raz podczas kompilacji. Jeżeli mamy sytuację w której plik pch zostanie włączony dwa razy, zobaczymy taki właśnie błąd. Przykładowo mamy:
foo.h włącza "std.h"
bar.h włącza "std.h"
foobar.cpp włącza "foo.h" i "bar.h"
Nie wiem jak to rozwiązują inni, ja po prostu opatrzyłem dyrektywę strażnikiem:

//Precompiled header
#ifndef STD_H_
#include "std.h"
#endif

Warto przeczytać: gcc/Precompiled-Headers

GUI

Nie dawno uznałem, że nadszedł moment od którego scena powinna być ładowana z pliku. Co oznacza konieczność utworzenia jakiegoś formatu sceny, importera i co najgorsze edytora. Jakoś nie mam ochoty ręcznie zapisywać liczb typu float.

Jak tu napisać edytor ? Poza win API i javą nie znam, żadnego narzędzia do robienia GUI. Edytor potrzebuje jakoś ładować, zapisywać i wyświetlać taką scenę. Pisanie wszystkiego dwa razy to absurd, więc java odpada. Pisanie edytora w win API też mi się nie uśmiecha. Wpadłem na idiotyczny pomysł, napiszę sobie GUI w oparciu o mój silnik. Sam się zastanawiam, po co ja to robię ?! Istnieją już gotowe biblioteki, choćby Cegui. Na razie walczę, jak uznam swą porażkę z czasem, to pomyślę nad gotowcem:

Odroczone oświetlenie 2

Drugi post od kiedy nad tym pracuję.

Natknąłem się na dziwny problem z CG. Przyznam, że nie wiem czy to moja wina czy biblioteki. Nagle CG przestało lubić shader nad którym pracowałem. Cały problem jest opisany tutaj. Z jednej strony sam nie mogę uwierzyć, że trafiłem na bug'a. Ta biblioteka powinna być naprawdę dobrze przetestowana. Z drugiej strony mój kod działał poprawnie przez pół roku i nagle przestał ?! Nie, nie tak to nie ma :)

Czemu uważam, że mój kod jest w porządku:
1) Poprawnie ładowane są wszystkie pozostałe shadery, w tym kilka równie "skomplikowanych" co ten felerny.
2) Kod działał poprawnie od dawna. Nie robiłem żadnych specjalnych testów, ale przeszedł chrzest bojowy.
3) Każde wywołanie funkcji z cg ma walidowany wynik.
4) Zwrócony błąd według CG to: Unkown error, dla DX to Invalid data.

Jak będę miał trochę wolnego czasu, to może wrócę do cg i poszukam rozwiązania. Póki co przeniosłem kod odpowiedzialny za shadery całkowicie na directx:

Odroczone oświetlenie

Jakoś dawno nic nie napisałem. Nie było o czym i kiedy. Święta skończą się dla mnie jutro. Jak dobrze pójdzie to w środę wrócę do mojej pracy mgr inż.

Ponieważ oświetlenie zaczęło działać postanowiłem je popsuć :) Konkretniej to nadszedł czas aby zamienić klasyczne podejście na cieniowanie odroczone. Przez te dwa tygodnie przemyślałem sprawę, poczytałem co nieco, odkryłem kilka problemów, generalnie poważnie zbliżyłem się do zaimplementowania tej metody.

Jednym z problemów jest to jakiej geometrii użyć przy renderowaniu świateł. Pomysłów miałem kilka.
1) Pełno ekranowy quad. Za długo się nad tym nie zastanawiałem. Uruchomienie 200 razy shadera dla każdego piksela jest pomysłem złym.
2) Modyfikacja punktu 1, polegająca na przycięciu quad'a do rozmiarów ekranowych światła. Pytanie tylko jak to zrobić.
a) Wojciech Toman w swoim artykule proponuje zastosowanie metody opisanej tutaj. Mi się ona jednak nie podoba.
b) Wykorzystujemy macierz świata z odpowiednio zmodyfikowanymi współczynnikami skali i translacji. Wykonujemy normalną transformację i quad pokrywa cała niezbędną powierzchnię. Tylko, że w ten sposób renderujemy więcej pikseli niż jest to konieczne. Światło jest kuliste, a quad jest prostokątny, czyli na oko (4 - Pi) * r^2 pikseli za dużo. Poza tym musimy renderować taki quad z wyłączonym testem Z (przynajmniej ja do takiego wniosku doszedłem).
3) Kula. Z całą pewnością da dużo lepsze przybliżenie kształtu światła na ekranie. Można też wykorzystać Z test. Tylko, że geometria robi się skomplikowana. Może się okazać, że więcej stracimy na transformacji niż zyskamy na precyzji.
4) Sześcian. Pewien kompromis pomiędzy 2b i 3.

	Kula	Quad
Przybliżenie	-	+
Geometria	+	-
Z test	=	+

Mamy więc 3 +, 2 - i 1 remis. Dlatego wybrałem właśnie sześcian jako geometrię dla światła.

O co chodzi z tym Z test'em. Wymyśliłem (pewnie nie ja pierwszy), że można wykorzystać go do eliminacji pikseli tła podczas rysowania pierwszoplanowych świateł. Cała sztuczka polega na rysowaniu światła za geometrią z ustawionym testem Z na funkcję "greater". Potrzebujemy do tego bryły, która obejmuje całą niezbędną przestrzeń.
1) Macierz świata musi dokonać skalowania i translacji. Rotacja nie jest konieczna.
2) Zmieniamy funkcję Z.
3) Wyłączamy zapis Z.
4) Zmieniamy culling na rysowanie backface'ów.
5) Renderujemy sześcian.

Podczas kodowania wymyśliłem, że odwrócenie funkcji Z i cullingu pozwoli na eliminację w odwrotnej sytuacji, czyli pikseli pierwszoplanowych dla świateł w oddali.

error: variable `Math::Quaternion x; has initializer but incomplete type

Bardzo ciekawy błąd. Klasa ma inicjalizator, ale typ nie kompletny. Cóż to może znaczyć ?
Sprawa jest dosyć prosta. Klasa kwaternionu jest klasą zaprzyjaźnioną z klasą macierzy. Czyli mamy mniej więcej taki zapis w pliku Matrix.hpp:

class Quaternion;

class Matrix
{
 friend class Quaternion;
 ...
};

Jest to przydatne przy tworzeniu macierzy rotacji z kwaternionu.
No ale gdzie błąd ? Otóż w miejscu w którym korzystałem z kwaternionów był włączony plik Matrix.hpp, ale plik Quaternion.hpp już nie. Nie było potrzeby umieszczać tego nagłówka w macierzy, więc tego nie zrobiłem.

No ale skoro już mowa o kwaternionach, to znaczy, że robiłem coś z rotacjami. Tak, zrobiłem prosty kontroler kamery. Można sobie teraz polatać po scenie. Koniec z re kompilacją po byle zmianie położenia kamery :)

Zrobiłem też trochę cienie. Działają poprawnie światła spot i omni. Kierunkowych nawet nie sprawdzałem.

Dodałem też proste oświetlenie per pixel.

1	2	3

Cube shadow mapa średnio poprawnie wyświetla się na moim GF 7600. Jednak na kartach z serii 8xxx widać poprawnie jedną ze ścianek.

Oświetlenie punktowe i "coding standard"

Po pierwsze chwalenie się. Zrobiłem oświetlenie punktowe :) Wyszło przy okazji parę ciekawostek. Przede wszystkim samodzielnie wymyśliłem jak poprawnie znaleźć koordynaty dla takiej tekstury :), nie jest specjalnie skomplikowane, ale zawsze miło samemu coś odkryć, a nie tylko ctrl-c ctrl-v. Początkowo myślałem, że współrzędne powinny być normalizowane. Nie ma jednak takiej potrzeby.

Znormalizowane wspólrzędne

Zapomniałem, że w klasie tekstury nie było kodu tworzącego mapy sześcienne. Dalej okazało się, że macierz widoku jest robiona nie tak jak powinna. W efekcie cień poruszał się w innym kierunku niż obiekt. Ostatecznym problemem były "poszarpane" cienie.

Niedobra macierz projekcji

Przyczyną było nie schodzenie się obrazków na krawędziach, czyli źle zrobiona macierz projekcji.

Poprawny efekt

Po drugie, dziękuję Ci Motorolo za Twój coding standard. Dzięki niemu nie musiałem szukać tego błędu:

if (LightType_Directional = type)

Wskazał mi go kompilator, takim oto komunikatem: "non-lvalue in assignment"

Premature optimization is root of all evil 2

Jak się okazało efekt cieniowania nie był prawidłowy, ponieważ pokusiłem o pewną optymalizację. Przemnorzyłem macierz światła przez macierz Range. Miało to na celu przycięcie wynikowych współrzędnych do zakresu <0; 1>. Problem w tym, że wspołrzędną z też przycinałem, natomiast do shadow mapy trafiały "pełne" wartości. W efekcie porównywanie obu wartości nie bardzo dawało oczekiwane rezultaty.


Piksele oświetlone mają różne kolorki, w zależności od tego z jakim biasem zostały zaklasyfikowane.
1 - bias = 0
0.8 - bias = 0.001
0.6 - bias = 0.01
0.4 - bias = 0.1
0.2 - bias = 0.2
0 - cień
Masakra :)
Poprawiłem macierz range:

Premature optimization is root of all evil

Niby wiem wiem, że tak jest. Nawet nie dawno na forum warsztatu sugerowałem Lukaz'owi, żeby najpierw nauczył się programować i dopiero potem pomyślał o wydajności. I co, i sam się wpakowałem w optymalizowanie czegoś, co wciąż jest dla mnie nowością.

Chcę wykorzystać shadow mapping jako technikę oświetlenia w swoim silniku. Kod od strony silnika jest już gotowy. Zostało tylko napisać (raczej dostosować niż napisać) shadery.
1) Renderowanie shadow mapy. Trzeba zapisać wartość głębokości, czyli z / w. Sprytnie wymyśliłem, że można tu ładnie zaoszczędzić wykonując to dzielenie w vertex shaderze. Wartość powinna się ładnie interpolować.
W vertex shaderze dodałem parametr:

out float oDepth : TEXCOORD2

, oraz kod obliczający ten parametr:

oDepth = oPosition.z / oPosition.w;

Pixel shader był nowy:

void ps(in float depth : TEXCOORD2, out float3 oColor : COLOR)
{
 oColor = float3(depth , depth , depth);
}

2) Renderowanie wynikowego obrazka. Tutaj vertex shader wzbogacił się o wyliczanie pozycji względem światła, a pixel shader zajął się wyznaczeniem koordynatów dla shadow mapy, dystansu od światła i stwierdzeniem czy cień jest czy go nie ma.

Geometria	Projekcja shadow mapy	Dystans do światła

Jak widać zawartość shadow mapy nie pokrywa się z dystansem. Dokładniej to mamy źle wyznaczoną shadow mapę. Czemu ?? Błąd pojawia się gdy któryś wierzchołek znajduję się za światłem, czyli ma ujemną współrzędną z. Nie wiem dokładnie czemu tak się dzieje, jednak wydaje się, że taki trójkąt ma niewłaściwie interpolowany parametr depth. Przeniosłem dzielenie z / w do pixel shadera, rozwiązało to problem.

Wynikowe światło

Efekt wciąż nie jest poprawny, ale jest progress :)

base class `class __gnu_cxx::new_allocator< Graphics::Actor*> has a non-virtual destructor - czyli co robić gdy release nie działa

Co robić gdy program nie działa poprawnie w wersji Release, w przeciwieństwie do wersji zbudowanej z ustawieniami Debug ? Jak zawsze trzeba pomyśleć. Opracowanie planu działania wymaga zastanowienia się nad tym czym różnią się te dwie wersje:
1) Kod. Czy możliwe jest aby do kompilacji trafił różny kod ?
2) Ustawienia kompilatora. Jakie są różnice w budowaniu tych wersji ?
3) Inne :) Czy coś innego mogło wpłynąć na wynikowy kod ?

Jak się już ma plana to można przystąpić do działania.

Ad 1. Tak to jest możliwe. Myślę tu o pre procesorze. Zaczynamy więc nasze działania od przeszukania kodu pod tym kątem. Warto też zajrzeć od ustawień projektu i sprawdzić czy któraś z wersji nie ma definiowanych symboli, bo tak przecież się z tego korzysta.

Ad 2. Jeśli mamy pewność, że nie ma różnicy w kodzie, zaczynamy podejrzewać, że kompilator ma buga. No bo ten sam kod a on go zbudować nie umie :)
Oczywiście w obu wypadkach stosuje się różne ustawienia kompilatora. Szczególnie istotne są dwie flagi -o i -g w przypadku gcc, albo zestaw flag /O i /G, /Z /Y, /RTC ... dla kompilatora Microsoftu.
Co robią flagi -g ? Robią kilka rzeczy. Przede wszystkim włączają informacje niezbędne debuggerowi do pracy, ale nie tylko. Kompilator będzie również dodawał inicjację zmiennych. W małym projekcie coś takiego dosyć łatwo znaleźć. Przy większych z pomocą przyjdzie nam kompilator ze swoimi flagami kontrolującymi ostrzeżenia: -Wall,
-Weffc++, -Wuninitialized, -W-missing-field-initializers. Ich zastosowanie może sprawić, że kod przestanie się kompilować, za to zostaną nam wytknięte wszystkie braki w kodzie.
Jeśli to nie pomaga, to zostały jeszcze flagi -o, odpowiadające za optymalizację. Z reguły release ma dosyć wysoki poziom -o3+, a debug ma -o0, czyli optymalizacje wyłączone. Kompilator podczas optymalizacji będzie stosował przeróżne sztuczki, również takie które są potencjalnie niebezpieczne. Zaczynamy, więc podnosić poziom optymalizacji dla wersji debug. W ten sposób powinno udać się wyśledzić błąd.

Ad 3. Co innego może wpłynąć na wynikowy program ? Do głowy przychodzą mi tylko biblioteki. Może zdarzyć się tak, że włączane są różne ich wersje.

Co dalej ? Nie wiem, może porzucenie projektu, może zmiana zawodu ;)

EDIT: Drobna edycja tytułu.

Zliczanie referencji

Ehh, nadszedł ten dzień kiedy ostatecznie uznałem, że zliczanie referencji trzeba zrobić. Bufor tu, bufor tam. Potem ktoś ten bufor skasuje i pół aplikacji zostaje z wskaźnikiem na skasowany obiekt.
Zastosowane rozwiązanie jest oparte na wcześniejszym modelu zarządzania zasobami. Wzbogaciłem go jedynie o dodatkową klasę Handle i parę metod zliczających referencje.
Wszystkie elementy posługują się już uchwytami, a same zasoby póki co nie wychodzą poza menadżerów.

class Handle
{
    friend class Resources::Resource;
public:
    Handle(const Handle & arg);
    Handle();
    virtual ~Handle();

    Handle & operator = (const Handle & arg);

    std::string & GetName();
    bool IsCreated();

protected:
    Resource * getResource();
private:
    Handle(Resource * resource);

    Resource * resource;
};

class Resource
{
    friend class Resources::ResourceFactory;
    friend class Resources::Handle;
public:
    std::string & GetName();
    bool IsCreated();
    bool Remove();
protected:
    Resource(const std::string & name, ResourceFactory & resourceFactory);
    virtual ~Resource();

    Handle getHandle();

    void setCreated(bool isCreated);
private:
    Resource();

    void add();
    void remove();

    void addRef();
    void removeRef();

    std::string name;
    ResourceFactory & resourceFactory;

    bool isCreated;
    unsigned int references;
};

typedef std::map<std::string, Resource *> ResourceMap;

class ResourceFactory
{
    friend class Resource;
public:
    //No public interface.
protected:
    ResourceFactory();
    virtual ~ResourceFactory();

    ResourceMap resources;
};

GUI

Jest progress, więc się chwalę. Zmieniłem metodę rysowania elementów z StrechtRect, na renderowanie geometrii. Wymagało to pewnych zmian w koncepcji, i ogromnej ilości poprawek przeróżnych błędów czających się w kodzie ;) Jednak opłaciło się:
* działa bez zauważalnego spadku fps.
* element może mieć dowolny kształt, np kulę.
* element może wysunąć się poza obszar ekranu bez żadnych zabiegów z mojej strony. StrechtRect strasznie marudziło w takiej sytuacji.

Gorzej tylko, że to znacznie skomplikowało budowę elementów i napisanie nowego będzie wymagać znajomości macierzy.

Oto 2 screeny. Na obu widać dwa okienka jedno pełnoekranowe z podpiętą kamerą, a drugie w rogu z podpiętym światłem. Niestety rysowanie bufora głębokości jeszcze nie działa, więc jest biała plama. Shader użyty przy liczeniu oświetlenia też nie robi do końca tego co powinien, więc mamy tylko przekopiowany kanał czerwony :)

GUI

Dawno nic nie napisałem. Jakoś nie było kiedy. Mogę tylko powiedzieć, że sporo napisałem. Zacząłem robić GUI. Idea jest prosta. GUI składa się z prostokątnych elementów, które reagują na polecenia typu kliknięcie myszką. Początkowo postanowiłem, wykorzystać do ich rysowania IDirect3DDevice9::StretchRect. Efekt wyszedł nawet całkiem przyjemny. Szybko się jednak okazało, że o ile użycie 32 bitowego render targetu rgba jako źródła obrazu nie stanowi problemu, to już r32f okazał nie akceptowalny dla tej metody. Konieczne jest wykonanie konwersji, a ta z kolej wymaga ściągnięcia danych do pamięci ram, przerobienia danych i odesłania ich do karty graficznej. Z 60 fps'ów zrobiło się 5.

Na obrazku widać dwa okienka (elementy). Pełnoekranowe używa kamery jako źródła obrazu, a to małe w rogu światła. Tylko, że shadow mapa nie była renderowana i wyszły śmieci :)

Android

Nie dawno spotkałem się z platformą Android. Posłuchałem o niej w ramach wykładu z przedmiotu "Programowanie urządzeń mobilnych" i postanowiłem zobaczyć co tam google wysmażyło. Wszystko działa aż miło. Pisze się też bardzo przyjemnie. Ogólnie jestem bardzo pozytywnie zaskoczony. Postanowiłem nawet napisać projekt zaliczeniowy z przedmiotu właśnie na tę platformę. Jakoś J2ME mnie odstrasza.
Tytuł projektu "Obsługa rozkładów jazdy miejskich środków komunikacji".

Kilka detali o api androida:
Język java, ale możecie zapomnieć o jej przenośności. VM Androida, Dalvik, nie obsłuży ani J2SE ani J2ME.
Do sdk dołączony jest emulator.
W paczce znajduje się również plugin do Eclipse'a.
Cała dokumentacja znajduje się na podanej wyżej stronie. Jest tam też instrukcja instalacji ;)

To drm, or not to drm ?

Ostatnio na Warsztacie pojawił się wątek o drm. Autor [revo] pyta o porady w kwestii zbudowania jakiegoś prostego mechanizmu zabezpieczenia programu dystrybuowanego przez internet. Oprócz kilku sugestii rozwiązania, rozpoczęła się również dyskusja nad zasadnością stosowania takich mechanizmów.

Generalnie moją opinię [bez sensu] można poznać na forum. Chodzi mi jednak po głowie kilka pytań.

Jak daleko można posunąć się w walce z piractwem ? Autor ma niezaprzeczalne prawo do otrzymania wynagrodzenia za swoją pracę, a piraci to prawo teoretycznie łamią. Zwalczanie piractwa jest więc czymś naturalnym i moralnie uzasadnionym ;) Tylko czy śledzenie swoich klientów i traktowanie każdego z nich jak złodzieja jest etyczne ? Czy utrudnianie życia klientowi jest dopuszczalne ?

Zdarzyło mi się już zobaczyć komunikat informujący mnie, że odpalenie legalnie nabytej gry nie jest możliwe, bo jakieś zabezpieczenie uznało oryginalną płytę za nie oryginalną. Co ma zrobić użytkownik w takiej sytuacji, szukać crack'a, może czekać na rozwiązanie od wydawcy ? Ja usunąłem grę i nie zainstalowałem patch'a który ten błąd wywołał. Akurat się dało, ale nie zawsze musi.

Anonimowość w sieci nie istnieje. Zmuszanie klienta do zdradzenia nam swoich danych (ip, mac) poprzez różne formy rejestracji, aktywacji itp. również jest czymś z czym trudno mi się pogodzić. Jaką klient ma pewność, że serwer przechowujący te dane jest odpowiednio zabezpieczony i że nikt tych danych nie wykorzysta ? W stanach FBI ma władze absolutną, a ja nie chcę żeby mnie FBI śledziło, bo kupiłem sobie grę, którą jakiś gryzipiórek uzna za podejrzaną ! (nie mam manii prześladowczych, ot taki przesadzony przykład ;) )

Czemu piraci tylko teoretycznie naruszają prawo do wynagrodzenia ? Długo myślałem i nie wymyśliłem jak udowodnić, że pirat kupiłby dany program, gdyby nie mógł go ukraść. Z drugiej strony pojawia się również kwestia możliwego zakupu legalnej wersji po przetestowaniu pirackiej (może jakieś promile promila). Osobiście mam wrażenie, że ogromna większość piratów nie dokonałaby zakupu, zmniejszając tym samym popularność produktu.

Kłopoty i problemy

Witam wszystkich w nowym roku.
Wyjazd na narty sie udał. Niestety tydzień po powrocie dopadła mnie angina, która po czterech dniach zamieniła się zapalenie ślinianek. W efekcie przez prawie dwa tygodnie nie mogłem nic napisać :(
Tak naprawdę usiadłem przed kompem dopiero wczoraj. No i muszę powiedzieć, że były to całkiem ciekawe dwa dni ;) Tuż przed świętami zacząłem robić obsługę urządzeń wejściowych. Wybrałem bibliotekę OIS, bo przyjazna w użyciu i raczej nie ma co narzekać na możliwości. Oczywiście przed wyjazdem nie skończyłem tego i takie rozgrzebane przeleżało aż do wczoraj. Udało mi zapanować nad wszystkimi problemami i skompilować kod. Jednak linker zaczął płakać, że ma nie zdefiniowane symbole z biblioteki OIS ?! No przecież ją "instalowałem". Zajrzałem do ustawień projektu no i jest OIS_static dodane. Google podpowiedziało rozwiązanie. W projekcie C::B nie są włączone wszystkie pliki. Heh. Odpaliłem C::B, dodałem brakujący plik, rebuild, kopiowanie lib'ki do mingw. Eclipse wciąż marudził na nie zdefiniowane symbole. Okazało się, że trzeba jeszcze dołączyć bibliotekę DirectX Input, w postaci dwóch plików dx input 8, oraz dx guid. I na tym się dzień wczorajszy skończył.
Dziś postanowiłem dopisać kod, który będzie inicjalizował moduł wejścia. Zrobiłem sobie klasę Input::Manager, zbliżoną do Graphics::Manager. Oczywiście klasa wylądowała w plikach manager.hpp i cpp, podobnie jak jej siostra z modułu graficznego. No i rzecz jasna w obu plikach pojawił standardowy strażnik "#ifndef MANAGER_HPP ... " A ja przez pól dnia zastanawiałem się czemu do licha klasa Input::Manager jest undefined ;)