Wydajna struktura do reprezentowania hierarchii transformacji

Czy ktoś może zasugerować efektywny sposób pamięci do reprezentowania drzewa macierzy, na przykład w modelu hierarchicznym?

Szczególnie zależy mi na zachowaniu lokalizacji danych i podejrzewam, że odpowiednie może być podejście typu struktura tablic (macierze i wskaźniki do macierzy).

Oprócz wielu łańcuchowych obliczeń macierzowych, ta struktura prawdopodobnie zostanie skopiowana do pamięci całkiem sporo, więc posiadanie ciągłej pamięci byłoby dużą zaletą.

Drzewo jak tablica brzmi dla mnie jak wygrana. Po prostu wykonaj głębokie przemierzanie swojej hierarchii i wypełnij tablicę; podczas przewijania przez rekurencję możesz albo zaktualizować element nadrzędny z indeksem bezwzględnym do elementu podrzędnego, albo po prostu delta-od-mnie, a dzieci mogą również przechowywać indeksy nadrzędne w dowolny sposób. Rzeczywiście, jeśli użyjesz względnych przesunięć, nie musisz nosić adresu głównego. Przypuszczam, że struktura prawdopodobnie wyglądałaby podobnie

struct Transform
{
   Matrix m; // whatever you like
   int parent;   // index or offset, you choose!
   int sibling;
   int firstchild;
};

... więc potrzebujesz węzłów, aby wiedzieć, jak dostać się do rodzeństwa, ponieważ nie możesz (łatwo) mieć struktury o zmiennym rozmiarze. Chociaż myślę, że jeśli użyłeś przesunięć bajtów zamiast przesunięć transformacji, możesz mieć zmienną liczbę dzieci na transformację:

struct Transform
{
   Matrix m; // whatever you like
   int parent;  // negative byte offest
   int numchildren;
   int child[0]; // can't remember if you put a 0 there or leave it empty;
                 // but it's an array of positive byte offsets
};

... musisz tylko upewnić się, że umieszczasz kolejne Transformacje we właściwym miejscu.

Oto jak zbudować całkowicie samodzielne drzewo z osadzonymi „wskaźnikami” dla dzieci.

int BuildTransforms(Entity* e, OutputStream& os, int parentLocation)
{
    int currentLocation = os.Tell();

    os.Write(e->localMatrix);
    os.Write(parentLocation);
    int numChildren = e->GetNumChildren();
    os.Write(numChildren);

    int childArray = os.Tell();
    os.Skip(numChildren * sizeof(int));
    os.AlignAsNecessary();  // if you need to align transforms

    childLocation = os.Tell();
    for (int i = 0; i < numChildren; ++i) {
        os.Seek(childArray + (i * sizeof(int)));
        os.Write(childLocation);
        os.Seek(childLocation);
        childLocation = BuildTransforms(e->GetChild(i), os, currentLocation);
    }

    return os.Tell();
}

void BuildTransforms(Entity* root)
{
    OutputStream os;
    BuildTransforms(root, os, -1, 0);
}

(Jeśli chcesz przechowywać względne lokalizacje, po prostu dodaj - currentLocationdo dwóch zapisów „lokalizacja”).

Indeksowanie w macierz macierzy byłoby prawdopodobnie najprostszym i najbardziej wydajnym podejściem do pamięci.

Łańcuch transformacji może być przechowywany w LIFO jako seria wskaźników lub liczb całkowitych lub innej małej struktury, która indeksuje się do macierzy macierzy. Pomoże to zapobiec przechowywaniu zbędnych matryc i oddzieli kod przechowywania danych od kodu dostępu do danych.

Ostatecznie wystarczy popchnąć i wyskoczyć wartości indeksu z LIFO, aby zapisać lub odtworzyć łańcuch transformacji.

Możesz również zaoszczędzić trochę pamięci, jeśli struktura macierzy może również zawierać typ transformacji ... obrót, translację itp. W przeciwnym razie typ musiałby być zapisany z indeksem, co spowodowałoby większą możliwą duplikację.