Estrutura eficiente para representar uma hierarquia de transformação

Alguém pode sugerir uma maneira eficiente de memória para representar uma árvore de matrizes, por exemplo, em um modelo de hierarquia?

Estou particularmente interessado em preservar a localidade dos dados e suspeito que uma abordagem do tipo estrutura de matrizes (matrizes e índices para matrizes) possa ser adequada.

Assim como muitos cálculos matriciais encadeados, essa estrutura provavelmente será copiada na memória um pouco, de modo que ter armazenamento contíguo seria um grande bônus.

A árvore como matriz parece uma vitória para mim. Basta fazer uma travessia profunda da sua hierarquia e preencher uma matriz; ao retroceder a recursão, você pode atualizar o pai com o índice absoluto para o filho ou apenas o delta-de-mim, e os filhos também podem armazenar os índices pai de qualquer maneira. De fato, se você usar deslocamentos relativos, não precisará carregar o endereço raiz. Suponho que a estrutura provavelmente seria algo como

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

... então você precisará de nós para saber como chegar aos irmãos, já que você não pode (facilmente) ter uma estrutura de tamanho variável. Embora eu ache que, se você usou desvios de bytes em vez de desvios de transformação, poderá ter um número variável de filhos por transformação:

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
};

... então você só precisa ter certeza de colocar as transformações sucessivas no lugar certo.

Veja como você constrói uma árvore totalmente independente com "ponteiros" filhos incorporados.

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);
}

(Se você deseja armazenar locais relativos, basta adicionar - currentLocationàs duas gravações "locais".)

A indexação em matriz de matrizes provavelmente seria a abordagem mais direta e eficiente em termos de memória.

Uma cadeia de transformações pode ser mantida em um LIFO como uma série de ponteiros ou números inteiros ou outra estrutura pequena que indexa na matriz. Isso ajudaria a impedir o armazenamento de matrizes redundantes e separaria o código de armazenamento de dados do código do acessador de dados.

Por fim, basta pressionar e exibir valores de índice do LIFO para armazenar ou reproduzir sua cadeia de transformação.

Você também poderá economizar um pouco de memória se a estrutura da matriz também puder conter o tipo de transformação ... rotação, conversão, etc. Caso contrário, o tipo precisará ser armazenado com o índice, resultando em maior duplicação possível.