{"id":743,"date":"2011-02-08T03:10:02","date_gmt":"2011-02-08T02:10:02","guid":{"rendered":"http:\/\/netrix.org.pl\/?p=743"},"modified":"2011-02-12T02:24:15","modified_gmt":"2011-02-12T01:24:15","slug":"data-oriented-design-scenegraph-proof-of-concept","status":"publish","type":"post","link":"https:\/\/netrix.org.pl\/index.php\/2011\/02\/08\/data-oriented-design-scenegraph-proof-of-concept\/","title":{"rendered":"Data-Oriented-Design – SceneGraph proof of concept"},"content":{"rendered":"

Jaki\u015b czas temu postanowi\u0142em do swojego silnika do\u0142\u0105czy\u0107 SceneGraph, kt\u00f3rego zadaniem by\u0142aby hierarchizacja modeli (w relacji rodzic-dzieci) wyst\u0119puj\u0105cych na scenie oraz aktualizacja ich macierzy \u015bwiata. Generalnie taki graf zawiera nieco wi\u0119cej informacji, takich jak na przyk\u0142ad bry\u0142y otaczaj\u0105ce wraz z drzewem \u00f3semkowym, na podstawie kt\u00f3rych mo\u017cna odrzuci\u0107 modele nieb\u0119d\u0105ce w zasi\u0119gu kamery, jeszcze przed renderowaniem ca\u0142ej sceny. Jednak aktualnie zale\u017ca\u0142o mi na zaimplementowaniu samej podstawy, czyli macierzy \u015bwiata, ale w spos\u00f3b zorientowany na dane, jak ma to miejsce w prezentacji Pitfalls of Object-Oriented Programming<\/a><\/em>. <\/p>\n

Hierarchizacja sceny polega na zebraniu wszystkich element\u00f3w sceny i po\u0142\u0105czeniu ich w drzewo, kt\u00f3re sk\u0142ada si\u0119 z korzenia oraz w\u0119z\u0142\u00f3w potomnych. W takim drzewie ka\u017cdy rodzic oddzia\u0142uje bezpo\u015brednio na swoje dziecko, czyli w tym przypadku transformacja, kt\u00f3r\u0105 przechowuje rodzic ma wp\u0142yw na transformacj\u0119 przechowywan\u0105 przez dziecko, dla D3DX wygl\u0105da to tak:<\/p>\n

\r\nD3DXMatrixMultiply(&childWorldMatrix, &childLocalMatrix, &parentWorldMatrix);\r\n<\/pre>\n
\nIstnieje kilka sposob\u00f3w na powi\u0105zanie w\u0119z\u0142\u00f3w SceneGraph z elementami sceny. Najprostszym z nich jest struktura SGNode, kt\u00f3rej instancj\u0119 mo\u017cna umie\u015bci\u0107 w klasie reprezentuj\u0105cej jaki\u015b element sceny. Taka struktura wygl\u0105da nast\u0119puj\u0105co:\n<\/p>\n
\r\nstruct SGNode\r\n{\r\n   SGNode* pSibling, pChild;\r\n   D3DXMATRIX localMatrix, worldMatrix;\r\n};\r\n<\/pre>\n
Poniewa\u017c sceny zwykle nie s\u0105 statyczne, ka\u017cdy taki w\u0119ze\u0142 powinien by\u0107 aktualizowany co klatk\u0119. Do tego celu powinna s\u0142u\u017cy\u0107 odpowiednia funkcja klasy zarz\u0105dzaj\u0105cej drzewem, kt\u00f3rej zadaniem b\u0119dzie przej\u015bcie rekursywnie po ca\u0142ym drzewie i zaktualizowanie danych. Oto przyk\u0142ad takiej funkcji:<\/p>\n
\r\nvoid updateNodes(SGNode* pRoot)\r\n{\r\n   SGNode* pNode = pRoot->pChild;\r\n\r\n   while(pNode != null)\r\n   {\r\n      D3DXMatrixMultiply(&pNode->worldMatrix, &pNode->localMatrix, &pRoot->worldMatrix);\r\n      updateNodes(pNode);\r\n      pNode->pSibling;\r\n   }\r\n}\r\n\r\n\/\/ Wywo\u0142anie na korzeniu\r\nupdateNodes(m_pRoot);\r\n<\/pre>\n
Ten prosty przyk\u0142ad wystarczy by zauwa\u017cy\u0107 problem, kt\u00f3ry zosta\u0142 poruszony w wymienionej prezentacji. Chodzi przede wszystkim o skakanie po pami\u0119ci wska\u017anikami, kt\u00f3re s\u0105 do\u015b\u0107 obficie u\u017cywane w takiej implementacji. Powoduje to cache-missy, zw\u0142aszcza w przypadku, gdy ka\u017cdy w\u0119ze\u0142 jest alokowany osobno.<\/p>\n
Rozwi\u0105zaniem tego, jak mo\u017cna si\u0119 domy\u015bli\u0107, jest umieszczenie tych danych w spos\u00f3b liniowy, tak jak ma to miejsce w wymienionej prezentacji. Wa\u017cne jest r\u00f3wnie\u017c, aby dane by\u0142y rozdzielone i uszeregowane w kolejno\u015bci ich p\u00f3\u017aniejszej aktualizacji.<\/p>\n
W swoim silniku rozwi\u0105za\u0142em to wykorzystuj\u0105c uchwyty, a w\u0119z\u0142y traktuj\u0105c jak ka\u017cdy inny zas\u00f3b, kt\u00f3ry mo\u017cna tworzy\u0107 i niszczy\u0107. Wszystko to znajduje si\u0119 w jednej klasie, kt\u00f3ra wygl\u0105da nast\u0119puj\u0105co:<\/p>\n
class NSceneGraph\r\n{\r\n   struct NSceneGraphNode\r\n   {\r\n      NSize_t   uChild,\r\n            uSibling;\r\n      NSize_t uIndex;            \/\/ Indeks do tablic danych\r\n      NSize_t uNext;             \/\/ Indeks nast\u0119pnego w\u0119z\u0142a\r\n   };\r\n\r\npublic:\r\n   NRESULT InitSceneGraph();\r\n\r\n   void Release();\r\n\r\n   NRESULT CreateNode(NHSceneGraphNode& hNode);\r\n\r\n   void ReleaseNode(NHSceneGraphNode hNode);\r\n\r\n   void ChangeParent(NHSceneGraphNode hNode);\r\n\r\n   void ChangeParent(NHSceneGraphNode hNode, NHSceneGraphNode hParent);\r\n\r\n   NMMatrixPP GetLocalMatrix(NHSceneGraphNode hNode);\r\n\r\n   void SetLocalMatrix(NHSceneGraphNode hNode, NMMatrixPP matrix);\r\n\r\n   NMMatrixPP GetWorldMatrix(NHSceneGraphNode hNode);\r\n\r\n   const NMMatrix* GetWorldMatrixPtr(NHSceneGraphNode hNode);\r\n\r\n   \/\/ Funkcja aktualizuje macierze world i inne dane\r\n   void Update();\r\n\r\n   \/\/ Funkcja porz\u0105dkuje drzewo tak, by przechodzenie wszerz by\u0142o liniowe i cache-friendly\r\n   NRESULT ApplyChanges();\r\n\r\nprivate:\r\n   NRESULT ResizeArrays(NSize_t uSize);\r\n\r\n   void AddSubtree(NSize_t uNode, NSize_t uNewParent);\r\n\r\n   void RemoveSubtree(NSize_t uNode);\r\n\r\n   void SetChildIndex(NSize_t uNode, NSize_t uChild)\r\n   {\r\n      m_aSceneNodes[uNode].uChild = uChild;\r\n   }\r\n\r\n   NSize_t GetChildIndex(NSize_t uNode)\r\n   {\r\n      return m_aSceneNodes[uNode].uChild;\r\n   }\r\n\r\n   void SetSiblingIndex(NSize_t uNode, NSize_t uSibling);\r\n\r\n   NSize_t GetSiblingIndex(NSize_t uNode);\r\n\r\n   void SetDataIndex(NSize_t uNode, NUint32 uIndex);\r\n\r\n   NSize_t GetDataIndex(NSize_t uNode);\r\n\r\n   void SetNextIndex(NSize_t uNode, NSize_t uNext);\r\n\r\n   NSize_t GetNextIndex(NSize_t uNode);\r\n\r\n   bool RemoveSubtree(NSize_t uRoot, NSize_t uNode);\r\n\r\nprivate:\r\n   NStableDataVector m_aSceneNodes;\r\n\r\n   bool m_bDirty;\r\n   NSize_t m_uArraysSize;\r\n   NAlignedDynamicTable m_aLocalMatrices;\r\n   NAlignedDynamicTable m_aWorldMatrices;\r\n};<\/pre>\n
\nTeraz przyda\u0142oby si\u0119 wyja\u015bnienie co do tego kodu. Po pierwsze nie ma tutaj wska\u017anik\u00f3w, poniewa\u017c jednym z za\u0142o\u017ce\u0144 silnika jest wykorzystywanie wi\u0119kszych obszar\u00f3w pami\u0119ci zamiast pojedynczych alokacji. Z tego wynika za\u0142o\u017cenie o uchwytach, co implikuje wykorzystanie w przedstawionym kodzie indeks\u00f3w. NStableDataVector<\/em> reprezentuje kontener, kt\u00f3rego kluczowym za\u0142o\u017ceniem jest niezmienno\u015b\u0107 pozycji przechowywanych danych, dzi\u0119ki czemu uchwyty pozostaj\u0105 wa\u017cne przez ca\u0142y czas dzia\u0142ania aplikacji. NAlignedDynamicTable<\/em> jest natomiast klas\u0105, kt\u00f3ra odpowiada za tworzenie i obs\u0142ug\u0119 tablicy przechowuj\u0105cej r\u00f3\u017cne dane (w tym przypadku macierze), kt\u00f3re wymagaj\u0105 wyr\u00f3wnanego adresu.\n<\/p>\n
\nWracaj\u0105c jednak do samego drzewa sceny – poniewa\u017c jego g\u0142\u00f3wnym za\u0142o\u017ceniem jest implementacja rozwi\u0105za\u0144 z wymienionej prezentacji, dane zosta\u0142y podzielone na  kilka odpowiednich tablic, a indeksy do tych tablic zosta\u0142y dodane do w\u0119z\u0142a. Wszystkie nowo utworzone w\u0119z\u0142y s\u0105 potomkami w\u0119z\u0142a g\u0142\u00f3wnego, a zmiana rodzica jest transakcj\u0105, kt\u00f3ra usuwa podany w\u0119ze\u0142 i od razu dodaje go jako dziecko nowego rodzica (funkcja ChangeParent()<\/em>).\n<\/p>\n
\nKluczow\u0105 funkcj\u0105 tej klasy jest ApplyChanges()<\/em>, jej zadaniem u\u0142o\u017cenie danych w taki spos\u00f3b, aby zredukowa\u0107 liczb\u0119 cache-miss\u00f3w do minimum, wygl\u0105da ona tak:\n<\/p>\n
\r\nNRESULT NSceneGraph::ApplyChanges()\r\n{\r\n   NAssert(m_bDirty != false, \"Needless call of this function\");\r\n\r\n   NRESULT result;\r\n   \/\/ Temp arrays\r\n   NDataQueue tempQueue;\r\n   NAlignedDynamicTable tempLocalMatrices;\r\n   NAlignedDynamicTable tempWorldMatrices;\r\n\r\n   if(NFAILED(result = tempLocalMatrices.Create(m_aLocalMatrices.GetSize(), MATRIX_ALIGNMENT))\r\n   || NFAILED(result = tempWorldMatrices.Create(m_aWorldMatrices.GetSize(), MATRIX_ALIGNMENT))\r\n   || NFAILED(result = tempQueue.Create(m_uArraysSize \/ 2, 0)))\r\n   {\r\n      tempLocalMatrices.Release();\r\n      tempWorldMatrices.Release();\r\n      tempQueue.Release();\r\n      return result;\r\n   }\r\n\r\n   tempLocalMatrices[0] = m_aLocalMatrices[0];\r\n   tempWorldMatrices[0] = m_aWorldMatrices[0];\r\n\r\n   \/\/ G\u0142\u00f3wny algorytm\r\n   NSize_t uRootNode = 0;\r\n   tempQueue.PushElement(GetChildIndex(uRootNode));\r\n\r\n   SetNextIndex(uRootNode, GetChildIndex(uRootNode));\r\n\r\n   NSize_t uNext = uRootNode;\r\n   for(NUint32 i = 1; !tempQueue.IsEmpty(); )\r\n   {\r\n      NSize_t uNode = *tempQueue.GetFront();\r\n      tempQueue.PopElement();\r\n\r\n      for(; uNode != NMAX_SIZE_T; ++i)\r\n      {\r\n         SetNextIndex(uNext, uNode);\r\n\r\n         tempLocalMatrices[i] = m_aLocalMatrices[GetDataIndex(uNode)];\r\n         tempWorldMatrices[i] = m_aWorldMatrices[GetDataIndex(uNode)];\r\n         SetDataIndex(uNode, i);\r\n\r\n         if(GetChildIndex(uNode) != NMAX_SIZE_T)\r\n         {\r\n            tempQueue.PushElement(GetChildIndex(uNode));\r\n         }\r\n\r\n         uNext = GetNextIndex(uNext);\r\n         uNode = GetSiblingIndex(uNode);\r\n      }\r\n   }\r\n   SetNextIndex(uNext, NMAX_SIZE_T);\r\n\r\n   m_aLocalMatrices.Release();\r\n   m_aWorldMatrices.Release();\r\n   tempQueue.Release();\r\n\r\n   m_aLocalMatrices = tempLocalMatrices;\r\n   m_aWorldMatrices = tempWorldMatrices;\r\n   m_bDirty = false;\r\n\r\n   Update();\r\n\r\n   return NRV_SUCCESS;\r\n}\r\n<\/pre>\n
\nPowy\u017csza funkcja zosta\u0142a wyrwana prosto z pliku \u017ar\u00f3d\u0142owego. Jak wida\u0107 przechodzi ona ca\u0142e drzewo wszerz porz\u0105dkuj\u0105c dane (macierze) oraz aktualizuj\u0105c indeks danych i nast\u0119pnego w\u0119z\u0142a. Najwa\u017cniejszym faktem dotycz\u0105cym tej funkcji jest to, \u017ce powinna by\u0107 wywo\u0142ana po wszystkich czynno\u015bciach zwi\u0105zanych z dodawaniem, usuwaniem lub przenoszeniem w\u0119z\u0142\u00f3w. Dane uporz\u0105dkowane mo\u017cna p\u00f3\u017aniej wielokrotnie uaktualnia\u0107 za pomoc\u0105 funkcji Update()<\/em>, kt\u00f3ra nie b\u0119dzie posiada\u0107 narzutu zwi\u0105zanego ze skakaniem po danych (pozostaje tylko skakanie po w\u0119z\u0142ach, kt\u00f3re same w sobie nie s\u0105 du\u017ce).\n<\/p>\n
\nFunkcja ta wygl\u0105da w tym przypadku tak:\n<\/p>\n
\r\nvoid NSceneGraph::Update()\r\n{\r\n   NAssert(m_bDirty == false, \"Call this function before running updates\");\r\n\r\n   NSize_t uParentNode = 0;\r\n\r\n   while(uParentNode != NMAX_SIZE_T)\r\n   {\r\n      NSize_t uNode = GetChildIndex(uParentNode);\r\n\r\n      while(uNode != NMAX_SIZE_T)\r\n      {\r\n         NSize_t uDataIndex = GetDataIndex(uNode);\r\n         \/\/ Macierze globalne\r\n         m_aWorldMatrices[uDataIndex] = NMMatrixMul(m_aLocalMatrices[GetDataIndex(uNode)], m_aWorldMatrices[GetDataIndex(uParentNode)]);\r\n\r\n         uNode = GetSiblingIndex(uNode);\r\n      }\r\n\r\n      uParentNode = GetNextIndex(uParentNode);\r\n   }\r\n}\r\n<\/pre>\n
\nCa\u0142y algorytm przechodzenia po tym drzewie polega na aktualizacji ka\u017cdego dziecka dla bie\u017c\u0105cego rodzica. Dzi\u0119ki informacji o nast\u0119pnym w\u0119\u017ale przechodzenie po drzewie odbywa si\u0119 poziom po poziomie.\n<\/p>\n
\nJak wida\u0107 ca\u0142y problem podej\u015bcia zorientowanego na dane uda\u0142o si\u0119 umie\u015bci\u0107 w jednej klasie, co wi\u0119cej funkcja porz\u0105dkuj\u0105ca dane nie wymaga cz\u0119stego wywo\u0142ywania, poniewa\u017c najprawdopodobniej b\u0119dzie to mia\u0142o miejsce w przypadku \u0142adowania\/usuwania sceny. Narzut zwi\u0105zany z korzystaniem z uchwyt\u00f3w i indeksacj\u0105 r\u00f3wnie\u017c mo\u017cna zredukowa\u0107 przed dodanie funkcji zwracaj\u0105cych wska\u017anik na \u017c\u0105dane dane, kt\u00f3re po ka\u017cdym wywo\u0142aniu ApplyChanges()<\/em> nale\u017cy zaktualizowa\u0107.<\/p>\n","protected":false},"excerpt":{"rendered":"
Jaki\u015b czas temu postanowi\u0142em do swojego silnika do\u0142\u0105czy\u0107 SceneGraph, kt\u00f3rego zadaniem by\u0142aby hierarchizacja modeli (w relacji rodzic-dzieci) wyst\u0119puj\u0105cych na scenie oraz aktualizacja ich macierzy \u015bwiata. Generalnie taki graf zawiera nieco wi\u0119cej informacji, takich jak na przyk\u0142ad bry\u0142y otaczaj\u0105ce wraz z drzewem \u00f3semkowym, na podstawie kt\u00f3rych mo\u017cna odrzuci\u0107 modele nieb\u0119d\u0105ce w zasi\u0119gu kamery, jeszcze przed renderowaniem […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[179,10,135,180,134,68,133],"_links":{"self":[{"href":"https:\/\/netrix.org.pl\/index.php\/wp-json\/wp\/v2\/posts\/743"}],"collection":[{"href":"https:\/\/netrix.org.pl\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/netrix.org.pl\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/netrix.org.pl\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/netrix.org.pl\/index.php\/wp-json\/wp\/v2\/comments?post=743"}],"version-history":[{"count":32,"href":"https:\/\/netrix.org.pl\/index.php\/wp-json\/wp\/v2\/posts\/743\/revisions"}],"predecessor-version":[{"id":798,"href":"https:\/\/netrix.org.pl\/index.php\/wp-json\/wp\/v2\/posts\/743\/revisions\/798"}],"wp:attachment":[{"href":"https:\/\/netrix.org.pl\/index.php\/wp-json\/wp\/v2\/media?parent=743"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/netrix.org.pl\/index.php\/wp-json\/wp\/v2\/categories?post=743"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/netrix.org.pl\/index.php\/wp-json\/wp\/v2\/tags?post=743"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}