Netrix's devLog

W tej notce postaram się opisać w jaki sposób, krok po kroku, postawić główne repozytorium Gita na własnym serwerze z zainstalowanym systemem linux (na przykładzie Slackware, z którego korzystam, ale myślę, że nie będzie problemów na innych dystrybucjach). Repozytorium nie będzie wykorzystywać interfejsu webowego i nie będzie uwzględniać podziału na konta, ale będzie wystarczającą alternatywą dla publicznego repozytorium w serwisie GitHub. Jednak zaczynając od początku wypadałoby powiedzieć kilka słów o tym czym jest Git.

Git jest jednym z kilku systemów kontroli wersji (SVN, Mercurial), czyli narzędzi służących do śledzenia zmian w kodzie źródłowym. Jego głównym zadaniem jest łączenie i modyfikacja zmian, a w razie błędu, umożliwienie przywrócenia poprzedniej, działającej wersji. Jedną z bardzo ważnych cech Gita jest to, że wszystkie zmiany są przechowywane lokalnie, dzięki czemu nie wymaga on do działania połączenia z głównym repozytorium. W porównaniu do Subversion, z którego do tej pory korzystałem, jest również szybszy i nie występują w nim problemy z łączeniem równoległych wersji (branchy).

Wracając jednak do tematu, na początek wypadałoby się upewnić czy na komputerze, na którym chcemy zainstalować Gita jest jedna z jego nowszych wersji. Ma to związek z przeniesieniem wewnętrznych plików wykonywalnych z katalogu /usr/bin/ do /usr/libexec/git-core/.

Instalacja Gita

Tak więc na początek pobieramy paczkę z git-core z tej strony, za pomocą polecenia:

wget http://kernel.org/pub/software/scm/git/git-1.7.4.1.tar.bz2

i ją rozpakowujemy:

tar –xvf git-1.7.4.1.tar.bz2

następnie przechodzimy do tego katalogu i (po przeczytaniu README oraz INSTALL), wykonujemy następujące polecenia:

./configure && make && make prefix=/usr install install-doc install-html install-info

Tutaj można napotkać problem przy instalowaniu dokumentacji, jak to miało miejsce u mnie. Rozwiązanie tego problemu znajduje się na tej stronie.

W tym momencie Git powinien być już zainstalowany, w przypadku gdy mieliśmy na dysku starą wersję, która pliki wykonywalne przechowuje w katalogu /usr/bin/, należy je ręcznie skasować, żeby nie sprawiały problemu. Jeśli jest to możliwe, można je rozpoznać po datach modyfikacji, po czym na koniec powinny zostać tam następujące pliki:

git
git-cvsserver
git-receive-pack
git-shell
git-upload-archive
git-upload-pack
gitk

Konto shellowe Git

Kolejnym krokiem jest utworzenie odpowiedniego konta shellowego, dzięki któremu będzie można połączyć się z repozytorium za pomocą protokołu ssh. Konto należy utworzyć z uid i gid równymi 9418 oraz git-shell jako programem startowym:

groupadd git –g 9418
useradd git –u 9418 –g git –c git –d /home/git –s /usr/libexec/git-core/git-shell
passwd –d git

Istotna jest ostatnia komenda, ponieważ bez niej nie uda się nam połączyć z repozytorium. Następnie tworzymy repozytorium i nadajemy prawa:

chown git:git /home/git/
chmod 700 /home/git/
mkdir /home/git/base/
chown git:git /home/git/base/
chmod 775 /home/git/base/

Kolejnym krokiem jest utworzenie właściwego repozytorium, robi się to za pomocą poleceń:

mkdir /home/git/base/repo.git
cd /home/git/base/repo.git
git init –-bare -–shared
sudo chmod -R g+ws *
sudo chgrp -R git *

Repozytorium jest już gotowe, niestety jeszcze nie można się z nim połączyć, ponieważ konto git nie posiada hasła. W celu umożliwienia łączenia się do repozytorium należy skorzystać mechanizmu autoryzacji sesji ssh za pomocą klucza prywatnego.

Autoryzacja za pomocą klucza prywatnego

W tym celu należy na każdej maszynie, z której będziemy się łączyć, utworzyć dwa klucze rsa, jeden publiczny drugi prywatny. Nie będę tego opisywał w tej notce, ponieważ jest to fajnie wyjaśnione na stronie GitHuba, w wersji dla systemu windows i linux. Opiszę natomiast w jaki sposób dodać te klucze do konta git na serwerze, umożliwiając tym autoryzację.

Na początek należy utworzyć w katalogu /home/git/ katalog .ssh, w nim plik authorized_keys i nadać im odpowiednie prawa:

mkdir /home/git/.ssh
chmod 700 /home/git/.ssh/
touch /home/git/.ssh/authorized_keys
chmod 600 /home/git/.ssh/authorized_keys
cat id_rsa.pub >> /home/git/.ssh/authorized_keys
chown –R git:git /home/git/.ssh/

Gdzie id_rsa.pub to klucz publiczny skopiowany z komputera klienckiego.

I to by było na tyle, w tym momencie można już wysyłać dane do repozytorium, którego adres jest następujący:

git@adres_serwera:base/repo.git

Źródła:
[1] http://forums.freebsd.org/showthread.php?t=10810
[2] http://stackoverflow.com/questions/897477/installing-git-on-os-x
[3] https://wincent.com/wiki/Updating_to_Git_1.6.0.1
[4] http://mapopa.blogspot.com/2009/10/git-insufficient-permission-for-adding.html

Tym razem krótki wpis wraz z aplikacją przedstawiającą zaimplementowany SceneGraph. Różnica między tą a poprzednią wersją jest taka, że do obracającego modelu Tiny (postać) został podpięty model LandShark (statek) dzięki czemu zaczął on latać nad planszą zgodnie z obrotem Tiny. Dodatkowo pod ten ostatni można podpiąć kamerę, którą nie traci swobodnego ruchu, co pozwala poruszać się po nowym lokalnym układzie współrzędnych. Hierarchię modeli można zobaczyć na poniższym obrazku:

Odnośnie sterowania odsyłam do ReadMe. Aplikację można pobrać stąd.

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