Graf sceny
Kolejną ze struktur danych, jakie przydadzą się podczas tworzenia gry, jest graf sceny. Graf sceny będzie grafem dość specyficznym (acyklicznym i spójnym), co w teorii sprowadzi go do drzewa.
Zielonym do.. dołu.
Drzewa w informatyce rosną w dół. Korzeń znajduje się u szczytu, kolejne gałęzie, węzły (wierzchołki posiadające dzieci) i liście (wierzchołki, nie posiadające dzieci) są umieszczane niżej.
Przykładowe drzewo binarne (takie, w którym każdy wierzchołek może mieć co najwyżej dwoje dzieci) jest przedstawione na rysunku (źródło: Wikipedia).
Koncepcja
Drzewo (bądź graf sceny, będę używał tych określeń zamiennie) posłuży do zorganizowania hierarchii sceny. Każdy z wierzchołków będzie obiektem klasy dziedziczącej po abstrakcyjnej klasie GraphNode
.
Będzie ona przechowywać macierz świata dla danego wierzchołka, listę jego dzieci, oraz informację o rodzicu. Pozwoli również na uaktualnienie stanu wierzchołka oraz narysowanie jego zawartości (przy obu metodach skorzystamy z polimorfizmu).
Węzeł (wierzchołek)
Klasa węzła przedstawia się następująco:
public class GraphNode { #region Variables private readonly Dictionary<string, GraphNode> children; protected Matrix world; protected GraphNode parent; protected bool Visible; public string Name { get; set; } public GraphNode Parent { get { return parent; } } #endregion public GraphNode this[string name] { get { if (children.ContainsKey(name)) return children[name]; foreach (GraphNode node in children.Values) { GraphNode res = node[name]; if (res != null) return res; } return null; } } public GraphNode() { parent = null; children = new Dictionary<string, GraphNode>(); world = Matrix.Identity; Visible = true; } public void AddChild(GraphNode child) { child.parent = this; if (children.ContainsKey(child.Name)) return; children.Add(child.Name, child); } public void RemoveChild(GraphNode child) { children.Remove(child.Name); } public virtual void Update(GameTime gameTime) { foreach (GraphNode child in children.Values) child.Update(gameTime); } public virtual void Draw(GameTime gameTime, Matrix _world) { foreach (GraphNode child in children.Values) { if (!child.Visible) continue; child.Draw(gameTime, _world); } } }
Kilka wyjaśnień na temat zorganizowania klasy:
- Każdy węzeł ma swoją nazwę, pozwoli to na odwoływanie się do konkretnego węzła przez odwołanie tylko do korzenia.
- Ze względu na poprzedni punkt, można użyć słownika do przechowywania listy dzieci – to implikuje metody do dodawania i usuwania dzieci.
- Rodzic (pole
parent
) jest równenull
tylko dla korzenia drzewa. - metody
Draw
orazUpdate
są oznaczone jakovirtual
– będziemy je nadpisywać w klasach pochodnych.
Klasy pochodne będą reprezentować model oraz transformację względem rodzica. Pozwoli to na intuicyjne poruszanie się po grafie.
Węzeł reprezentujący model
Klasa ta jest mało złożona:
public class ModelNode : GraphNode { #region Variables private MyModel geometry; #endregion public MyModel Geometry { get { return geometry; } set { geometry = value; } } public ModelNode(MyModel geometry) { this.geometry = geometry; } public override void Draw(GameTime gameTime, Matrix _world, Matrix view, Matrix projection) { geometry.Draw(_world, view, projection); base.Draw(gameTime, _world, view, projection); } }
Nadpisaliśmy tu tylko metodę odpowiedzialną za odrysowanie siatki.
Węzeł reprezentujący transformację
Kod mówi sam za siebie – uaktualniana jest macierz świata.
public class TransformationNode : GraphNode { public TransformationNode(Matrix transformation) { world = transformation; } public void Apply(Matrix transformation) { world *= transformation; } public Quaternion Rotation { get { Quaternion rotation; Vector3 scale; Vector3 translation; world.Decompose(out scale, out rotation, out translation); return rotation; } } public Vector3 Translation { get { Quaternion rotation; Vector3 scale; Vector3 translation; world.Decompose(out scale, out rotation, out translation); return translation; } } public Matrix Transformation { get { return world; } set { world = value; } } public override void Draw(GameTime gameTime, Matrix _world, Matrix view, Matrix projection) { Matrix tmp = _world * world; base.Draw(gameTime, tmp, view, projection); } }
Przykład zastosowania
Modelowym przykładem zastosowania grafu sceny jest Układ Słoneczny. Planety krążą wokół Słońca (każda z różną prędkością), dodatkowo każda z nich obraca się wokół własnej osi (każda z nich z różną prędkością), dodatkowo wokół nich krążą satelity (księżyce), które również się obracają.. ufff… sporo tego -> uporządkujmy to. Najpierw rysunek powered by MS Paint:
Prostokąty reprezentują węzły zawierające model do narysowania, okręgi – transformacje. Poszczególne transformacje przedstawiają się następująco („I” to przekształcenie identycznościowe – macierz jednostkowa) :
- Rotacja wokół osi Z (skierowanej w górę układu współrzędnych) – rotacja Marsa wokół własnej osi.
- Translacja wzdłuż osi X o odległość Marsa od Słońca.
- Rotacja wokół osi Z – rotacja Marsa wokół Słońca.
- Rotacja wokół osi Z (skierowanej w górę układu współrzędnych) – rotacja Ziemi wokół własnej osi.
- Translacja wzdłuż osi X o odległość Ziemi od Słońca.
- Rotacja wokół osi Z – rotacja Ziemi wokół Słońca.
- itd. itd. itd.
Jak będzie wyglądało rysowanie sceny?
- Zaczynamy od korzenia (transformacja: macierz jednostkowa)
- Wywołujemy
Draw
dla pierwszego dziecka (niech będzie to transformacja 1); macierz świata = rotacja wokół Z - Wywołujemy
Draw
dla pierwszego (i, jak się okazuje, jedynego) dziecka węzła z 2) – macierz świata = rotacja wokół Z * translacja - Wywołujemy
Draw
dalej dla dziecka; macierz świata = rotacja wokół Z * translacja * rotacja wokół Z - Wywołujemy
Draw
dla modelu Marsa, ustawiamy odpowiednią macierz świata (ustawiającą model planety w dobre położenie) i rysujemy model, voila! - Wracamy z przechodzeniem drzewa do korzenia (ponieważ węzeł z modelem Marsa jest liściem); macierz świata = macierz jednostkowa
- Wywołujemy
Draw
dla kolejnego dziecka (transformacja 4); macierz świata = rotacja Ziemi wokół osi Z - itd. itd.
Jako, że transformacje są przechowywane względem rodzica (analogia do budowy modelu), transformujemy je do układu globalnego przez kolejne mnożenia macierzy. W ten sposób możemy intuicyjnie zbudować nawet dość skomplikowaną scenę.
Podsumowanie i możliwości rozszerzeń
Przedstawiony graf sceny służy jedynie do odpowiedniego rozmieszczenia obiektów na potrzeby rysowania. Jako rozszerzenie można zamknąć scenę w jakąś strukturę danych do hierarchicznego podziału przestrzeni (np. Octree) aby usprawnić liczenie kolizji między obiektami, lub łatwo eliminować je z rysowania przeprowadzając wstępne testy widoczności obiektu. Ale to już materiał na jedno z innych spotkań.
Odpowiedzi: 2 Zostaw komentarz
Celów jest kilka:
1) Edukacyjny – pokazanie zastosowania grafu sceny, idei oddzielnej transformacji każdego modelu, na optymalizacje zawsze jest czas później.
2) Dobranie się do każdej składowej transformacji (rotacja, translacja) oddzielnie (co też poniekąd łączy się z punktem pierwszym).
3) Kod i koncepcja, które tu przestawiłem to tylko baza do dalszych prac. Zauważ, że węzeł reprezentujący transformację ma właściwości Rotation i Translation – na etapie budowania (edycji) sceny można zrobić większe drzewo, potem złożyć ciąg transformacji w jedną, kod nie będzie musiał być zmieniany (tak robię w tym momencie).
Jaki cel przyświeca oddzieleniu transformacji od obiektu? Wystarczy przecież złożyć wszystkie transformacje na ścieżce w drzewie między dwoma obiektami i wynik umieścić w węźle z drugim obiektem dla tego samego efektu, mniejszego rozmiaru drzewa i mniejszej ilości mnożeń macierzy potrzebnych do renderowania.