Author Archive

Data-Oriented-Design – SceneGraph proof of concept

Jakiś czas temu postanowiłem do swojego silnika dołączyć SceneGraph, którego zadaniem byłaby hierarchizacja modeli (w relacji rodzic-dzieci) występujących na scenie oraz aktualizacja ich macierzy świata. Generalnie taki graf zawiera nieco więcej informacji, takich jak na przykład bryły otaczające wraz z drzewem ósemkowym, na podstawie których można odrzucić modele niebędące w zasięgu kamery, jeszcze przed renderowaniem całej sceny. Jednak aktualnie zależało mi na zaimplementowaniu samej podstawy, czyli macierzy świata, ale w sposób zorientowany na dane, jak ma to miejsce w prezentacji Pitfalls of Object-Oriented Programming.

Hierarchizacja sceny polega na zebraniu wszystkich elementów sceny i połączeniu ich w drzewo, które składa się z korzenia oraz węzłów potomnych. W takim drzewie każdy rodzic oddziałuje bezpośrednio na swoje dziecko, czyli w tym przypadku transformacja, którą przechowuje rodzic ma wpływ na transformację przechowywaną przez dziecko, dla D3DX wygląda to tak:

D3DXMatrixMultiply(&childWorldMatrix, &childLocalMatrix, &parentWorldMatrix);

Istnieje kilka sposobów na powiązanie węzłów SceneGraph z elementami sceny. Najprostszym z nich jest struktura SGNode, której instancję można umieścić w klasie reprezentującej jakiś element sceny. Taka struktura wygląda następująco:

1
2
3
4
5
struct SGNode
{
   SGNode* pSibling, pChild;
   D3DXMATRIX localMatrix, worldMatrix;
};

Ponieważ sceny zwykle nie są statyczne, każdy taki węzeł powinien być aktualizowany co klatkę. Do tego celu powinna służyć odpowiednia funkcja klasy zarządzającej drzewem, której zadaniem będzie przejście rekursywnie po całym drzewie i zaktualizowanie danych. Oto przykład takiej funkcji:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void updateNodes(SGNode* pRoot)
{
   SGNode* pNode = pRoot->pChild;
 
   while(pNode != null)
   {
      D3DXMatrixMultiply(&pNode->worldMatrix, &pNode->localMatrix, &pRoot->worldMatrix);
      updateNodes(pNode);
      pNode->pSibling;
   }
}
 
// Wywołanie na korzeniu
updateNodes(m_pRoot);

Ten prosty przykład wystarczy by zauważyć problem, który został poruszony w wymienionej prezentacji. Chodzi przede wszystkim o skakanie po pamięci wskaźnikami, które są dość obficie używane w takiej implementacji. Powoduje to cache-missy, zwłaszcza w przypadku, gdy każdy węzeł jest alokowany osobno.

Rozwiązaniem tego, jak można się domyślić, jest umieszczenie tych danych w sposób liniowy, tak jak ma to miejsce w wymienionej prezentacji. Ważne jest również, aby dane były rozdzielone i uszeregowane w kolejności ich późniejszej aktualizacji.

W swoim silniku rozwiązałem to wykorzystując uchwyty, a węzły traktując jak każdy inny zasób, który można tworzyć i niszczyć. Wszystko to znajduje się w jednej klasie, która wygląda następująco:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
class NSceneGraph
{
   struct NSceneGraphNode
   {
      NSize_t   uChild,
            uSibling;
      NSize_t uIndex;            // Indeks do tablic danych
      NSize_t uNext;             // Indeks następnego węzła
   };
 
public:
   NRESULT InitSceneGraph();
 
   void Release();
 
   NRESULT CreateNode(NHSceneGraphNode& hNode);
 
   void ReleaseNode(NHSceneGraphNode hNode);
 
   void ChangeParent(NHSceneGraphNode hNode);
 
   void ChangeParent(NHSceneGraphNode hNode, NHSceneGraphNode hParent);
 
   NMMatrixPP GetLocalMatrix(NHSceneGraphNode hNode);
 
   void SetLocalMatrix(NHSceneGraphNode hNode, NMMatrixPP matrix);
 
   NMMatrixPP GetWorldMatrix(NHSceneGraphNode hNode);
 
   const NMMatrix* GetWorldMatrixPtr(NHSceneGraphNode hNode);
 
   // Funkcja aktualizuje macierze world i inne dane
   void Update();
 
   // Funkcja porządkuje drzewo tak, by przechodzenie wszerz było liniowe i cache-friendly
   NRESULT ApplyChanges();
 
private:
   NRESULT ResizeArrays(NSize_t uSize);
 
   void AddSubtree(NSize_t uNode, NSize_t uNewParent);
 
   void RemoveSubtree(NSize_t uNode);
 
   void SetChildIndex(NSize_t uNode, NSize_t uChild)
   {
      m_aSceneNodes[uNode].uChild = uChild;
   }
 
   NSize_t GetChildIndex(NSize_t uNode)
   {
      return m_aSceneNodes[uNode].uChild;
   }
 
   void SetSiblingIndex(NSize_t uNode, NSize_t uSibling);
 
   NSize_t GetSiblingIndex(NSize_t uNode);
 
   void SetDataIndex(NSize_t uNode, NUint32 uIndex);
 
   NSize_t GetDataIndex(NSize_t uNode);
 
   void SetNextIndex(NSize_t uNode, NSize_t uNext);
 
   NSize_t GetNextIndex(NSize_t uNode);
 
   bool RemoveSubtree(NSize_t uRoot, NSize_t uNode);
 
private:
   NStableDataVector<NSceneGraphNode> m_aSceneNodes;
 
   bool m_bDirty;
   NSize_t m_uArraysSize;
   NAlignedDynamicTable<NMMatrix> m_aLocalMatrices;
   NAlignedDynamicTable<NMMatrix> m_aWorldMatrices;
};

Teraz przydałoby się wyjaśnienie co do tego kodu. Po pierwsze nie ma tutaj wskaźników, ponieważ jednym z założeń silnika jest wykorzystywanie większych obszarów pamięci zamiast pojedynczych alokacji. Z tego wynika założenie o uchwytach, co implikuje wykorzystanie w przedstawionym kodzie indeksów. NStableDataVector reprezentuje kontener, którego kluczowym założeniem jest niezmienność pozycji przechowywanych danych, dzięki czemu uchwyty pozostają ważne przez cały czas działania aplikacji. NAlignedDynamicTable jest natomiast klasą, która odpowiada za tworzenie i obsługę tablicy przechowującej różne dane (w tym przypadku macierze), które wymagają wyrównanego adresu.

Wracając jednak do samego drzewa sceny – ponieważ jego głównym założeniem jest implementacja rozwiązań z wymienionej prezentacji, dane zostały podzielone na kilka odpowiednich tablic, a indeksy do tych tablic zostały dodane do węzła. Wszystkie nowo utworzone węzły są potomkami węzła głównego, a zmiana rodzica jest transakcją, która usuwa podany węzeł i od razu dodaje go jako dziecko nowego rodzica (funkcja ChangeParent()).

Kluczową funkcją tej klasy jest ApplyChanges(), jej zadaniem ułożenie danych w taki sposób, aby zredukować liczbę cache-missów do minimum, wygląda ona tak:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
NRESULT NSceneGraph::ApplyChanges()
{
   NAssert(m_bDirty != false, "Needless call of this function");
 
   NRESULT result;
   // Temp arrays
   NDataQueue<NSize_t> tempQueue;
   NAlignedDynamicTable<NMMatrix> tempLocalMatrices;
   NAlignedDynamicTable<NMMatrix> tempWorldMatrices;
 
   if(NFAILED(result = tempLocalMatrices.Create(m_aLocalMatrices.GetSize(), MATRIX_ALIGNMENT))
   || NFAILED(result = tempWorldMatrices.Create(m_aWorldMatrices.GetSize(), MATRIX_ALIGNMENT))
   || NFAILED(result = tempQueue.Create(m_uArraysSize / 2, 0)))
   {
      tempLocalMatrices.Release();
      tempWorldMatrices.Release();
      tempQueue.Release();
      return result;
   }
 
   tempLocalMatrices[0] = m_aLocalMatrices[0];
   tempWorldMatrices[0] = m_aWorldMatrices[0];
 
   // Główny algorytm
   NSize_t uRootNode = 0;
   tempQueue.PushElement(GetChildIndex(uRootNode));
 
   SetNextIndex(uRootNode, GetChildIndex(uRootNode));
 
   NSize_t uNext = uRootNode;
   for(NUint32 i = 1; !tempQueue.IsEmpty(); )
   {
      NSize_t uNode = *tempQueue.GetFront();
      tempQueue.PopElement();
 
      for(; uNode != NMAX_SIZE_T; ++i)
      {
         SetNextIndex(uNext, uNode);
 
         tempLocalMatrices[i] = m_aLocalMatrices[GetDataIndex(uNode)];
         tempWorldMatrices[i] = m_aWorldMatrices[GetDataIndex(uNode)];
         SetDataIndex(uNode, i);
 
         if(GetChildIndex(uNode) != NMAX_SIZE_T)
         {
            tempQueue.PushElement(GetChildIndex(uNode));
         }
 
         uNext = GetNextIndex(uNext);
         uNode = GetSiblingIndex(uNode);
      }
   }
   SetNextIndex(uNext, NMAX_SIZE_T);
 
   m_aLocalMatrices.Release();
   m_aWorldMatrices.Release();
   tempQueue.Release();
 
   m_aLocalMatrices = tempLocalMatrices;
   m_aWorldMatrices = tempWorldMatrices;
   m_bDirty = false;
 
   Update();
 
   return NRV_SUCCESS;
}

Powyższa funkcja została wyrwana prosto z pliku źródłowego. Jak widać przechodzi ona całe drzewo wszerz porządkując dane (macierze) oraz aktualizując indeks danych i następnego węzła. Najważniejszym faktem dotyczącym tej funkcji jest to, że powinna być wywołana po wszystkich czynnościach związanych z dodawaniem, usuwaniem lub przenoszeniem węzłów. Dane uporządkowane można później wielokrotnie uaktualniać za pomocą funkcji Update(), która nie będzie posiadać narzutu związanego ze skakaniem po danych (pozostaje tylko skakanie po węzłach, które same w sobie nie są duże).

Funkcja ta wygląda w tym przypadku tak:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void NSceneGraph::Update()
{
   NAssert(m_bDirty == false, "Call this function before running updates");
 
   NSize_t uParentNode = 0;
 
   while(uParentNode != NMAX_SIZE_T)
   {
      NSize_t uNode = GetChildIndex(uParentNode);
 
      while(uNode != NMAX_SIZE_T)
      {
         NSize_t uDataIndex = GetDataIndex(uNode);
         // Macierze globalne
         m_aWorldMatrices[uDataIndex] = NMMatrixMul(m_aLocalMatrices[GetDataIndex(uNode)], m_aWorldMatrices[GetDataIndex(uParentNode)]);
 
         uNode = GetSiblingIndex(uNode);
      }
 
      uParentNode = GetNextIndex(uParentNode);
   }
}

Cały algorytm przechodzenia po tym drzewie polega na aktualizacji każdego dziecka dla bieżącego rodzica. Dzięki informacji o następnym węźle przechodzenie po drzewie odbywa się poziom po poziomie.

Jak widać cały problem podejścia zorientowanego na dane udało się umieścić w jednej klasie, co więcej funkcja porządkująca dane nie wymaga częstego wywoływania, ponieważ najprawdopodobniej będzie to miało miejsce w przypadku ładowania/usuwania sceny. Narzut związany z korzystaniem z uchwytów i indeksacją również można zredukować przed dodanie funkcji zwracających wskaźnik na żądane dane, które po każdym wywołaniu ApplyChanges() należy zaktualizować.

SerialPort i nasłuchiwanie w C#

W poprzedniej notce zaprezentowałem prosty emulator Modbus, który niedawno napisałem. W tej notce postaram się napisać w jaki sposób zaimplementowałem obsługę portu szeregowego COM oraz nasłuchiwanie nieblokujące aplikację.

Zaczynając od początku, SerialPort jest klasą z .NET Framework, która umożliwia obsługę portów szeregowych. Na początek przykład, w jaki sposób pobrać listę dostępnych w komputerze portów:

string[] ports = SerialPort.GetPortNames();

I tyle, tablica stringów zawiera nazwy dostępnych portów. Ważniejszym krokiem jest ustanowienie połączenia (tu przykładowe dane):

SerialPort sp = new SerialPort();
sp.ReadTimeout = 1000;
sp.WriteTimeout = 1000;
sp.PortName = "COM1"	// Jeden z wylistowanych portów
sp.BaudRate = 115200;
sp.DataBits = 8
sp.Parity = Parity.None;
sp.StopBits = StopBits.One
sp.Encoding = Encoding.BigEndianUnicode;
 
try
{
    sp.Open();
}
catch (Exception err)
{
    /* ... */
}

Skoro port został otwarty można już coś do niego wysłać:

byte[] data = /* jakieś dane */
sp.Write(data, 0, data.Length);

Odbieranie danych wygląda analogicznie:

byte[] data = null;
if (sp.BytesToRead > 0)
{
    data = new byte[sp.BytesToRead];
    sp.Read(data, 0, data.Length);
}

Troszkę większym problemem jest sprawienie, by aplikacja oczekiwała na nowe dane, a w razie czego je obsłużyła, nie powodując jednocześnie zastoju. Do tego celu należy użyć wątków, a dokładniej jednego, w którym należy wywołać taką funkcję:

private boolean bReceiving = false;
 
public void Receive()
{
    byte[] data;
    while (bReceiving)
    {
        if (sp.BytesToRead > 0)
        {
            data = new byte[sp.BytesToRead];
            sp.Read(data, 0, data.Length);
            receiveHandler.DataReceivedEvent(data);
        }
 
        Thread.Sleep(50); // Żeby nie zużywać niepotrzebnie zasobów
    }
}

Funkcja ta, jak widać zawiera pętle, która sprawdza czy istnieją dane do odczytu, jeśli tak to je odczytuje i przekazuje dalej do metody, która z nich skorzysta. Kod wywołania wątku oraz interfejs receiveHandler jest następujący:

interface IDataReceiveListener
{
    void DataReceivedEvent(byte[] data);
}
 
Thread transmissionThread = null;
 
void Run()
{
    bReceiving = true;
    transmissionThread = new Thread(() => { Receive(); });
    transmissionThread.Start();
}

Teraz najważniejsze, ponieważ korzystam w tym kodzie z dwóch wątków (głównego + dodatkowego), w tym miejscu należy zwrócić szczególną uwagę na dostęp do danych prze oba wątki. W mojej aplikacji założyłem, że drugi wątek obsługuje obiekt SerialPort (mimo że tworzę go w pierwszym wątku), zatem dostęp do tego obiektu z wątku głównego (tutaj w przypadku wysyłania) musi być opatrzony sekcją krytyczną:

Thread.BeginCriticalRegion();
 
sp.Write(data, 0, data.Length);
 
Thread.EndCriticalRegion();

Natomiast jest jeszcze przypadek gdy wątek drugi odbiera dane i odwołuje się do obiektów z wątku pierwszego. W tym przypadku należy skorzystać funkcji Invoke() klasy Form, która przyjmuje obiekt typu delegate, a jego zadaniem jest wywołanie odpowiedniej funkcji z wątku pierwszego. Kod który to robi jest następujący:

private delegate void ProcessRequestDelegate(byte[] data);
 
/* funkcja interfejsu IDataReceiveListener */
public void DataReceivedEvent(byte[] data)
{
    this.Invoke(new ProcessRequestDelegate(this.ProcessRequest), new object[] { data });
}
 
private void ProcessRequest(byte[] data)
{
    // some stuff
}

I to wszystko na ten temat. Jak widać pisanie aplikacji okienkowych w C# jest banalnie proste.

Modbus Emulator

modbusEmulatorJednym z ostatnich zadań na laboratorium Informatycznych Systemów Sterowania (i jednocześnie jedynym ciekawym) było zaimplementowanie protokołu Modbus w postaci aplikacji emulujących urządzenia master i slave, komunikujących się ze sobą bezpośrednio korzystając z portów szeregowych COM (RS-232). Zadanie to zrealizowałem minimalistycznie tworząc jedną aplikację, która emuluje oba urządzenia i implementuje 6 pierwszych publicznych funkcji wraz z podglądem rejestrów.

Aplikacja jest napisana w C# i korzysta z Windows Forms oraz klasy SerialPort (która załatwia całą komunikację po porcie COM). Całość implementacji bazuje na specyfikacji Modbusa znajdującej się tutaj. Oprócz tego podczas pisania wykorzystywałem również kilka aplikacji:

Dwie ostatnie aplikacje posłużyły mi jako referencja implementacji protokołu, ponieważ sama specyfikacja nie zawiera informacji o sposobie liczenia CRC i LRC, więc trzeba było do tego dojść metodą prób, błędów i Google.

Sam program obsługuje (jak już wcześniej wspomniałem) 6 pierwszych, publicznych funkcji protokołu Modbus dla obu urządzeń (Master i Slave) przesyłając dane w trybie ASCII lub RTU. Urządzenie Slave posiada podgląd rejestrów Coils, Discrete Inputs, Input Registers oraz Holding Registers, po 4096 sztuk każdy (wszystkie Read-Only, generowane na podstawie seed = 0). Aplikacja posiada również podgląd wysyłanych i otrzymywanych ramek w postaci logu transmisji.

Program wraz z kodem źródłowym znajdują się tutaj (wymaga .NET Framework 2.0) .

NIne3 – stan aktualny

W tej notce prezentuję aktualny stan mojego frameworka NIne3, którego strukturę opisałem jakiś czas temu. Jest to swego rodzaju ‘proof of concept’, czyli że to jednak działa. Z głównych feature’ów chciałbym wymienić:

  • shadowmapy (nowość :))
  • oświetlenie per-pixel
  • pliki wykonywalne dla platfrom x64 i x86 z obsługą SSE i bez
  • stały krok update’u logiki (tego akurat można nie zauważyć)
  • obsługa heightmap

I to chyba tyle, a tutaj link do aplikacji (wymaga redistów DX Feb 2010).

Struktura katalogów w projekcie

Czasami istnieje potrzeba pisania jednego projektu w różnych środowiskach programistycznych, tym bardziej jeśli korzystamy z systemu kontroli wersji (np. SVN,  GIT) i chcemy skompilować projekt z założenia multiplatformowy na innym systemie operacyjnym. W takim przypadku fajnie by było, aby projekt miał strukturę katalogów niezależną od IDE, ale jak powinna ona wyglądać? Według mnie tak:

  • include
  • src
  • workdir
  • projects
  • libs

Katalog include powinien zawierać tylko pliki nagłówkowe, które będą dołączane w innych projektach. Tak naprawdę jest on tutaj tylko ze względu na projekt biblioteki (np. lib, dll, itp.), więc w przypadku kompilacji do pliku wykonywalnego, można ten katalog pominąć, wtedy wszystkie pliki nagłówkowe powinny znaleźć się w katalogu src. Katalog src jest przeznaczony tylko dla plików źródłowych bieżącego projektu, które mogą być uporządkowane w różnych podkatalogach. W workdir powinna się znaleźć cała struktura katalogów docelowego programu, czyli wszystkie pliki i katalogi, które będą dostarczane ze skompilowanym plikiem wykonywalnym. Katalog libs służy do przechowywania wszystkich dołączanych bibliotek używanych w aplikacji. Dla każdej z nich powinien znaleźć się odpowiedni katalog a w nim jeszcze dwa – include i lib. Ostatnim katalogiem jest projects, który jest przeznaczony do przechowywania plików projektów dla każdego IDE (oczywiście każdy w osobnym katalogu).

Taka struktura jest przejrzysta i niezależna od stosowanego IDE. Zresztą nie jest to mój pomysł, ponieważ jest on od dawna stosowany w środowiskach linuksowych, ale w nieco innej postaci. Kluczowe jest po prostu trzymanie plików źródłowych w jednym katalogu niezależnym od stosowanego środowiska.

NIne3 – założenia i struktura silnika

Witam ponownie. Tym razem napiszę nieco o założeniach i strukturze mojego silnika, którym ma docelowo być NIne3. Numerek ‘3’ świadczy o tym, że jest to już trzecia iteracja, zatem jest to pewna zmiana w stosunku do wcześniejszych postów. Kod został przepisany na nowo, zmieniły się również założenia, ale część z nich oraz różne fragmenty kodu zostały wykorzystane ponownie. Muszę przyznać, że jestem zadowolony z aktualnego stanu kodu i myślę, że ta iteracja będzie jedną z tych dłuższych i dotrwa do czegoś większego :).

Założenia

Podstawowe założenia to:

  • brak wyjątków
  • brak STL (strumienie, kontenery, std::string)
  • brak funkcji wirtualnych (przynajmniej na niskim poziomie)
  • obiektowość
  • modułowość
  • całkowite ukrycie wykorzystywanego API graficznego
  • oddzielenie klas implementacyjnych od interfejsu programistycznego
  • minimalizacja alokacji pamięci
  • bezpieczny kod

Dlaczego takie założenia? Otóż, po pierwsze, wyjątki, mimo że jest to bardzo wygodny feature języka C++, są dość kosztowne, ponieważ wymagają dużo pracy włożonej w napisanie kodu, który zwolni wszystkie zasoby i sam przy tym nie wygeneruje błędów. Z drugiej strony różne kompilatory różnie implementują obsługę wyjątków, więc nie jest do końca pewne czy nie pojawi się dodatkowy narzut związany z obsługą powrotu z funkcji wewnątrz bloku try/catch.

Natomiast STL mimo, że jest biblioteką napisaną w najwydajniejszy możliwy sposób (a przynajmniej powinna być) i jednocześnie jest dość elastyczna, jest dość obszerna i na start dorzuca niecałe pół megabajta danych do pliku .exe, z czego z większości i tak się nie korzysta bezpośrednio. Ostatecznie nie spełnia ona również podstawowego założenia jaką jest brak obsługi wyjątków, którą można co prawda wyłączyć, ale nie jest to łatwe. Dlatego strumienie zostały u mnie zastąpione starą, dobrą funkcją printf, kontener std::vector własną implementacją uwzględniającą jeden z punktów o minimalnej ilości alokacji, a z std::string zrezygnowałem całkowicie, ponieważ nie jest ona konieczna, a poza tym dodatkowo nie spełniają kilku z wymienionych punktów.

Brak funkcji wirtualnych na niskim poziomie wziął się z oczywistego narzutu w postaci vtable, zatem wykorzystywany interfejs został napisany z użyciem PIMPL, dzięki czemu możliwa jest optymalizacja i inline’owanie funkcji (na poziomie konsolidacji). Nie wykluczam natomiast użycia ich w przyszłości na wyższym poziomie kodu, ale póki co staram się je omijać.

Obiektowość wiąże się przede wszystkim z enkapsulacją kodu, co pozwala oddzielić kod obsługi tekstur od kodu obsługi okna, efektów etc. w sposób wyraźny. Dzięki temu kod jest przejrzysty i łatwy w modyfikowaniu. Ten punkt powiązany jest bezpośrednio z punktem następnym czyli modułowością. Chciałbym, żeby kod był łatwo rozszerzalny i umożliwiał wymianę różnych klas oraz ich dodawanie, bez modyfikowania pozostałych. Pokażę to niżej na przykładzie hierarchii modułów.

W tej iteracji postanowiłem również ukryć całkowicie wykorzystywane API graficzne, którym póki co nadal jest Direct3D 9. API jest ukryte nie tylko na zewnątrz biblioteki, ale również wewnątrz dla modułów wyższego rzędu, które nie korzystają bezpośrednio z klas implementacyjnych, ale z interfejsu użytkownika, co zapewnia niezależność.

Docelowy użytkownik biblioteki nie widzi bezpośrednio klas implementacyjnych tylko klasy interfejsowe napisane przy użyciu PIMPL, które są uporządkowane w odpowiedniej hierarchii, którą pokażę nieco niżej. Daje to swobodę działania wewnątrz silnika i uporządkowanie na zewnątrz, jest również mniej błędogenne.

Ostatnie dwa punkty są niejako powiązane, ponieważ zakładam uruchamianie silnika na maszynach z ograniczoną ilością pamięci i możliwość wystąpienia błędu alokacji pamięci, więc obsługa takich błędów jest wymagana. Natomiast w celu minimalizacji tego typu błędów postanowiłem zmniejszyć ilość alokacji do minimum stosując kilka własnych klas do tego celu (bez menadżera pamięci póki co). Dodatkowo zakładam, że wszelkie możliwe błędy wystąpią w przypadku inicjalizacji i ładowania zasobów, więc każdy możliwy błąd zostaje przekazany do użytkownika biblioteki i zapisany w logu. Natomiast w czasie działania aplikacji błędy nie powinny wystąpić  albo będą występować bardzo rzadko, w tym przypadku ich sprawdzenie, o ile to możliwe, będzie występować w jednym ustalonym miejscu.

Hierarchia interfejsów

Jak już wspomniałem wcześniej klasy implementacyjne są oddzielone od użytkownika warstwą interfejsu, który ma za zadanie utworzyć odpowiednią hierarchię po to, aby klasy specjalizowane, zależne od ogólnych, nie mogły być pobrane i użyte przed zainicjalizowaniem tamtych. Dodatkowo daje to możliwość zmian wewnątrz silnika, bez zmiany samego interfejsu. Sama hierarchia wygląda następująco:

  • ICore:
    • IWindowManager:
      • INInput
    • ITimer
    • IRenderer:
      • IMeshManager
      • ITextureManager
      • IEffectManager:
        • IEffect
      • IModelLoader:
        • IModel:
          • IMaterial
      • IMeshLoaderX
      • IMeshLoaderHeightmap

Jak widać podział jest dość wyraźny. Wyszczególniłem całkowicie niezależne od siebie moduły: Timer, WindowManager i Renderer. Każdą z nich można inicjalizować osobno lub zrobić to za pomocą klasy Core, która zainicjalizuje wszystkie moduły i udostępni kilka podstawowych funkcji takich jak: Update(), Present(), ChangeDisplayMode(), które na nich operują.

Największym modułem jest Renderer, który również został wyraźnie podzielony na kilka podmodułów. Podstawowymi są tak naprawdę MeshManager, TextureManager oraz EffectManager (shadery) i to te klasy są odpowiedzialne za obsługę podstawowych zasobów niezbędnych do wyrenderowania czegokolwiek: siatek, tekstur oraz shaderów. Drugą grupą podmodułów są te odpowiedzialne za ładowanie wymienionych zasobów z plików w różnych formatach – aktualnie obsługuję tylko dwa – pliki .x oraz heightmapy. Ostatnią grupą są podmoduły zarządzające, których przedstawicielem jest ModelManager. Jego zadaniem jest zebranie zasobów w jednym miejscu i dodanie im odpowiedniej funkcjonalności tak, aby było mniej roboty przy renderowaniu.

Hierarchia modułów

Sercem silnika jest hierarchia modułów, która składa się z klas bibliotecznych, struktur oraz klas silnika:

  • Klasy biblioteczne:
    • NMath:
      • NMVector
      • NMMatrix
      • NMQuaternion
    • NAssert
    • NLogger
    • NDynamicTable
    • NDataVector
    • NStableDataVector
    • Inne (mniejsze klasy implementujące różną funkcjonalność)
  • Struktury
  • Engine:
    • Core
    • WindowManager:
      • Input
    • Timer
    • Renderer:
      • SubRenderer (Direct3D_9)
        • BuiltInLoader
          • MeshLoaderX
        • EffectManager
        • MeshManager
        • TextureManager
      • BuiltInLoaders
        • MeshLoaderHeightmap
      • ModelManager

W klasach bibliotecznych można znaleźć definicje typów podstawowych, bibliotekę matematyczną, kontenery oraz klasy pomocne w debugowaniu (logger i asercja). Biblioteka matematyczna jest napisana z myślą o wykorzystaniu funkcji intrinsic procesora (SSE) i jej wygląd bazuje w bardzo dużej mierze na XNAMath. Aktualnie obsługiwane są tylko wektory i macierze, ale nie wszystkie operacje zostały zaimplementowane, są tylko te aktualnie potrzebne. Między kontenerami można wyróżnić opakowaną w klasę zwykła tablicę dynamiczną (NDynamicTable), odpowiednik std::vector (NDataVector) oraz ten sam kontener, ale zachowujący wewnętrzne ułożenie danych (NStableDataVector – pomocne przy korzystaniu z uchwytów).

Hierarchia silnika różni się to trochę od hierarchii interfejsów, którą implementuje. Przede wszystkim wyróżnia się tutaj grupa SubRenderer. Jej celem jest zebranie wszystkich klas zależnych od API graficznego w jednym miejscu. Dzięki temu możliwa jest łatwa wymiana tego API przy zachowaniu funkcjonalności silnika. Wszystkie klasy, które znajdują się poza tą grupą korzystają albo z klasy pośredniej SubRenderer, albo z interfejsów użytkownika. Zmiana API będzie możliwa tylko statycznie, za pomocą odpowiedniej dyrektywy preprocesora. Klasy znajdujące się w tej grupie odpowiedzialne są za zarządzanie podstawowymi zasobami oraz samym urządzeniem i nie robią nic poza podstawowymi operacjami.

Wszystkie zasoby są udostępniane za pomocą uchwytów, dzięki którym można łatwo manipulować zasobami wewnątrz silnika bez obawy, że coś zostanie zgubione na zewnątrz. Niektóre z nich udostępniają dodatkowy interfejs (Effect, Model), który umożliwia bardziej szczegółową manipulację danym zasobem, ale klasy wewnętrzne Renderera manipulują wyłącznie uchwytami.

Oprócz tego istnieje cały zestaw pomocnych struktur, w tym właśnie szablon uchwytów, które bazują na odpowiednich akcesorach. Dzięki temu wszystko pozostaje hermetycznie zamknięte wewnątrz silnika.

Co dalej?

Aktualnie zakończyłem restrukturyzację hierarchii modułów do postaci takiej jaką przedstawiłem. Kolejnym moim celem jest dodanie SceneGraph, który będzie zarządzał drzewem modeli oraz przechowywał ich macierze świata i je aktualizował. Chcę przy tym wykorzystać poprawkę z tej prezentacji , czyli zawrzeć całe drzewo macierzy w jednej tablicy, która będzie cache-friendly.
Oprócz tego w związku z wydzieleniem SubRenderera chciałbym dodać drugi, oparty o OpenGL, ale to już będzie większy orzech do zgryzienia. Muszę przyznać, że sam jestem ciekaw wyniku :).

Praktyka w ADB


Witam ponownie, dzisiejszy post będzie podsumowaniem trzymiesięcznej praktyki, którą miałem przyjemność odbyć w wakacje. Jak wskazuje tytuł praktykę robiłem w firmie Advanced Digital Broadcast Polska Sp. z o.o., która zajmuje się tworzeniem oprogramowania związanego z odbiornikami cyfrowymi i samymi urządzeniami typu Set-Top Box. Jednym z ich produktów, który może być znany polskiemu odbiorcy jest dekoder cyfrowy telewizji n. Samą praktykę odbyłem w siedzibie ADB, która mieści się w Zielonej Górze. Wszystko to dzięki uprzejmości mojego kolegi Mateusza Semegena, który mnie zarekomendował.

Wracając do samych praktyk – pracowałem w dziale sterowników Audio/Video, a moim głównym zadaniem było zbudowanie i uruchomienie oraz sprawdzenie środowiska testowego do badań kolejnych sterowników odpowiedzialnych za prezentację oraz dekodowanie danych Audio/Video. Muszę przyznać, że zadanie okazało się całkiem ciekawe, a przy okazji przyczyniło się do polepszenia mojej znajomości Linuksa, na którym dane mi było pracować.

Praca w ADB jest moim pierwszym doświadczeniem zawodowym związanym z tworzeniem oprogramowania, ale muszę przyznać, że było bardzo pozytywnie. Atmosfera pracy była luźna, w firmie pracują ludzie, którzy wiedzą co robią, a w razie jakichkolwiek pytań chętnie udzielają na nie odpowiedzi. Można również pogadać na wiele tematów, o różnych zainteresowaniach. Firma od czasu do czasu organizuje różne imprezy integracyjne – zdarzyło mi się być na trzech, w tym dwie były ogólnofirmowe, a jedna z departamentu, w węższym gronie. Wszystkie bardzo miło wspominam.

Podsumowując, muszę przyznać, że czas spędzony na tych praktykach jest dla mnie bardzo cenny. Dzięki temu wiele dowiedziałem się na temat funkcjonowania pracownika w firmie, więc jest to jak najbardziej inwestycja w przyszłość.

RAW Input

Tym razem będzie znów coś związanego z systemem Windows i programowaniem gier, czyli obsługa myszy za pomocą RAW Input. Jest to jeden z trzech popularnych sposobów obsługi tych urządzeń. Pozostałymi są komunikaty procedury okna oraz DirectInput, z tym że ten ostatni jest niezalecany i już nie jest wspierany przez Microsoft na rzecz właśnie RAW Input. Jednak dlaczego nie te dwa?

Komunikaty procedury okna nie są tak naprawdę takie złe, co więcej bardzo dobrze nadają się do małych gier casualowych, najlepiej tych odpalanych w oknie, ponieważ wartościami otrzymywanymi od systemu (w przypadku myszy) jest pozycja kursora, a pozycja jest poprawiana tak, aby znalazł się on w miejscu w którym użytkownik się tego spodziewa. Niestety dane otrzymywane w ten sposób nie są dokładne więc w bardziej wymagających grach mogą okazać się nieprzydatne.
DirectInput jest natomiast sposobem na uzyskanie dokładniejszych danych, jednak zasada jego działania opiera się na utworzeniu dodatkowego wątku, podpięcia się do wskazanego okna i odczytywaniu danych bezpośrednio ze sterownika, czyli surowych danych (RAW). Najprawdopodobniej jest to przyczyną braku wsparcia dla tej metody, dodatkowo niektóre antywirusy mogą ostrzegać że aplikacja którą napisaliśmy jest keyloggerem.

RAW Input umożliwia aplikacji uzyskanie surowych danych bezpośrednio ze sterownika. Zasada działania opiera się tutaj, tak samo jak w pierwszej metodzie, na komunikatach procedury okna. Różnica polega na tym, że chęć otrzymywania tych danych należy wcześniej w systemie zarejestrować. Jest to póki co najlepsza metoda uzyskiwania dokładnych danych z myszy, ponieważ dostarcza informacje na temat przesunięć, a nie pozycji kursora. Otrzymywanie danych z klawiatury również jest możliwe, ale w tym przypadku dokładność nie ma sensu.

Do rejestracji urządzeń, których dane chcielibyśmy otrzymywać tą metodą, służy funkcja:

<a href="http://msdn.microsoft.com/en-us/library/ms645600%28VS.85%29.aspx">BOOL WINAPI RegisterRawInputDevices(
  __in  PCRAWINPUTDEVICE pRawInputDevices,
  __in  UINT uiNumDevices,
  __in  UINT cbSize
);
</a>

Pierwszym parametrem tej funkcji jest tablica obiektów struktury RAWINPUTDEVICE, która opisuje rejestrowane urządzenie. Pozostałe parametry to ilość urządzeń i rozmiar struktury, czyli sizeof(RAWINPUTDEVICE).

Poniższy przykład pokazuje rejestrację myszy:

RAWINPUTDEVICE rawStructure;
rawStructure.usUsagePage = 1;                            // Typ urządzenia (w tym przypadku GENERIC)
rawStructure.hwndTarget = m_hWnd;                    // Uchwyt okna
rawStructure.usUsage = 2;                                   // Rodzaj urządzenia (2 - mysz)
rawStructure.dwFlags = RIDEV_NOLEGACY;        // Więcej info w opisie struktury
 
if(!RegisterRawInputDevices(&amp;rawStructure, 1, sizeof(RAWINPUTDEVICE)))
{
    // Obsługa błędu
}

Wartości usUsage i usUsagePage można znaleźć w tym dokumencie.

Jeśli rejestracja urządzenia się powiedzie, to aplikacja przestanie otrzymywać standardowe komunikaty związane z tym urządzeniem, a zacznie otrzymywać komunikaty WM_INPUT z danymi RAW tego urządzenia.
Dane można otrzymywać na dwa sposoby: pojedynczo, bezpośrednio w trakcie obsługi komunikatu lub zbuforowane. Poniżej podam przykład na standardową obsługę komunikatu WM_INPUT, więcej info na temat tej i drugiej metody można znaleźć na tej stronie.

LRESULT WndProc(HWND hWnd, UINT msg, WPARAM wParam, LPARAM lParam)
{
     switch(msg)
     {
     case WM_INPUT:
          {
               RAWINPUT riStruct;
               DWORD dwSize = sizeof(RAWINPUT);
 
               if(GetRawInputData((HRAWINPUT)lParam, RID_INPUT, &amp;riStruct, &amp;dwSize, sizeof(RAWINPUTHEADER)) == (UINT)-1)
               {
                    // Obsługa błędu
               }
 
               if(riStruct.header.dwType == RIM_TYPEMOUSE)
               {
                    riStruct.data.mouse.lLastX;     // Przesuniecie X
                    riStruct.data.mouse.lLastY;     // Przesuniecie Y
 
                    riStruct.data.mouse.ulButtons;     // Przyciski myszy
 
                    riStruct.data.mouse.usButtonData;     // Rolka myszy
               }
          }
          break;
     }
}

Dziwić może to, że funkcja przyjmuje wskaźnik na zmienną do rozmiaru struktury RAWINPUT. Jest to spowodowane tym, że różne urządzenia mają różne struktury i podanie niewłaściwego rozmiaru skutkuje błędem oraz wpisaniem wymaganego rozmiaru pod podanym adresem.

Wyrejestrowanie urządzenia następuje po wywołaniu funkcji RegisterRawInputDevices podając jako w flagę w przekazywanej strukturze RIDEV_REMOVE.

Ogólnie rzecz biorąc RAW Input jest najlepszym sposobem na otrzymanie dokładnych danych z urządzeń wejściowych. Obsługa klawiatury jest trochę bardziej skomplikowana, a szczerze mówiąc nie widzę sensu korzystania z tego sposobu. Lepiej pozostać przy komunikatach. Osobiście uważam, że odpytywanie o stan inputu jest lepsze niż odpowiadanie na komunikaty, ponieważ aplikacja jest wtedy bardziej przewidywalna.

Java 2 Micro Edition

Tym razem będzie trochę o programowaniu aplikacji na telefon komórkowy korzystając z platformy J2ME, co jak się okazuje wcale nie jest takie trudne. Aby w ogóle zacząć pisać aplikację na tę platformę należy zaopatrzyć się w odpowiednie narzędzia. Praktycznie każdy szanujący się edytor do tworzenia aplikacji Javowych, umożliwia tworzenie projektów na urządzenia mobilne. Ja jednak postanowiłem pójść po linii najmniejszego oporu i ściągnąłem pakiet J2ME Platform SDK. Pakiet ten zawiera w sobie wszystko co jest potrzebne do pisania tego typu aplikacji (w tym niewielki edytor oparty na Netbeans). Można go znaleźć pod tym linkiem.

Aplikacje J2ME nazywa się Midletami, ponieważ punktem startowym aplikacji jest klasa dziedzicząca po interfejsie o tej nazwie. Interfejs ten wymusza implementacje 3 podstawowych funkcji:

  • void startApp()
  • void pauseApp()
  • void destroyApp(boolean unconditional)

Pierwsza funkcja wywoływana jest gdy aplikacja rozpoczyna lub wznawia działanie, w celu umożliwienia załadowania, zainicjalizowania odpowiednich danych. Druga funkcja umożliwia aplikacji zwolnienie części zasobów w momencie gdy aplikacja przechodzi w stan wstrzymania. Ostatnia funkcja jest wywoływana w momencie zamykania midletu. Funkcja ta posiada argument typu boolean, który określa, czy aplikacja ma zostać zamknięta bezwarunkowo (w przeciwnym wypadku powinien zostać rzucony odpowiedni wyjątek).

Oprócz tego działanie aplikacji opiera się na kilku innych klasach: Display, Command oraz dziedziczących po klasie abstrakcyjnej DisplayableScreen lub Canvas. Klasa Display odpowiada za to co jest wyświetlane na ekranie, a wyświetlane są obiekty klas pochodnych od klasy Displayable. Dodatkowo te obiekty mogą wysyłać różne zdarzenia, czyli obiekty klasy Command. W celu rejestracji tych zdarzeń potrzebny jest jeszcze obiekt klasy implementującej interfejs CommandListener, który należy przekazać do funkcji Displayable::setCommandListener().

Oto przykładowy kod Hello World:

package hello;
 
import javax.microedition.midlet.*;
import javax.microedition.lcdui.*;
 
public class HelloMIDlet extends MIDlet implements CommandListener
{
    private Command exitCommand; // The exit command
    private Display display;     // The display for this MIDlet
 
    public HelloMIDlet()
    {
        display = Display.getDisplay(this);
        exitCommand = new Command("Exit", Command.EXIT, 0);
    }
 
    public void startApp()
    {
        TextBox t = new TextBox("Hello", "Hello, World!", 256, 0);
 
        t.addCommand(exitCommand);
        t.setCommandListener(this);
 
        display.setCurrent(t);
    }
 
    public void pauseApp()
    {
    }
 
    public void destroyApp(boolean unconditional)
    {
    }
 
    public void commandAction(Command c, Displayable s)
    {
        if (c == exitCommand)
        {
            destroyApp(false);
            notifyDestroyed();
        }
    }
}

Jak widać te kilka klas wystarcza, aby utworzyć prostą aplikację na telefon komórkowy. Bardziej złożone korzystają dodatkowo z RecordStore do zapisywania informacji między różnymi uruchomieniami aplikacji oraz kilku innych.

Nowa strona – Linki

Postanowiłem dodać nową stronę na bloga – Linki. Będę na niej zamieszczał odnośniki, które według mnie są warte kliknięcia. Lista linków będzie podzielona na dwie części, z których pierwsza będzie zawierać te, które już widziałem, a do pozostałych po prostu zajrzałem. Postaram się również, w miarę możliwości, dodawać do nich opisy.