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

2 Comments

  1. tapczan:

    Piszesz, że nie będzie trzeba często przebudowywać tablicy.
    Idealnym ułożeniem danych w tablicy byłoby takie, jak po przejściu drzewa sceny wszerz, co chyba czynisz. Jednak dodanie jakiegoś dziecka w czasie działania gry do jakiegoś rodzica powinno polegać na wstawieniu nowego Node gdzieś wewnątrz tej tablicy. Wtedy jednak indeksy następnych, przesuniętych wierzchołków przestają być aktualne.
    Natomiast dostawienie go gdziekolwiek indziej też jest problematyczne – skaczemy po indeksach, co jest prawie tak samo złe jak skakanie wskaźnikami (nieprzewidywalne, może być wstecz i w ogóle…).

  2. Netrix:

    Tak, ale jeśli już trzeba coś zmienić, to można wykonać kilka zmian za jednym zamachem i na końcu zaktualizować takie drzewo. Myślę, że zmiana organizacji drzewa nie jest aż tak częsta jak sama aktualizacja macierzy, dlatego zaproponowałem takie rozwiązanie.

Leave a comment