czoper.devlog

.NET, CAD/CAM

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!

• 
•