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ówne null tylko dla korzenia drzewa.
  • metody Draw oraz Update są oznaczone jako virtual – 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) :

  1. Rotacja wokół osi Z (skierowanej w górę układu współrzędnych) – rotacja Marsa wokół własnej osi.
  2. Translacja wzdłuż osi X o odległość Marsa od Słońca.
  3. Rotacja wokół osi Z – rotacja Marsa wokół Słońca.
  4. Rotacja wokół osi Z (skierowanej w górę układu współrzędnych) – rotacja Ziemi wokół własnej osi.
  5. Translacja wzdłuż osi X o odległość Ziemi od Słońca.
  6. Rotacja wokół osi Z – rotacja Ziemi wokół Słońca.
  7. itd. itd. itd.

Jak będzie wyglądało rysowanie sceny?

  1. Zaczynamy od korzenia (transformacja: macierz jednostkowa)
  2. Wywołujemy Draw dla pierwszego dziecka (niech będzie to transformacja 1); macierz świata = rotacja wokół Z
  3. Wywołujemy Draw dla pierwszego (i, jak się okazuje, jedynego) dziecka węzła z 2) – macierz świata = rotacja wokół Z * translacja
  4. Wywołujemy Draw dalej dla dziecka; macierz świata = rotacja wokół Z * translacja * rotacja wokół Z
  5. Wywołujemy Draw dla modelu Marsa, ustawiamy odpowiednią macierz świata (ustawiającą model planety w dobre położenie) i rysujemy model, voila!
  6. Wracamy z przechodzeniem drzewa do korzenia (ponieważ węzeł z modelem Marsa jest liściem); macierz świata = macierz jednostkowa
  7. Wywołujemy Draw dla kolejnego dziecka (transformacja 4); macierz świata = rotacja Ziemi wokół osi Z
  8. 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ń.

Be Sociable, Share!
czoper opublikowano dnia 2010-10-7 Kategoria: Daj się poznać, Programowanie, Theme Festival | Tagi:, , ,

Odpowiedzi: 2 Zostaw komentarz

  1. #2czoper @ 2010-10-8 08:02

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

  2. #1Xion @ 2010-10-8 07:49

    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.

Zostaw odpowiedź

(Ctrl + Enter)