Estructura eficiente para representar una jerarquía de transformación.

¿Alguien puede sugerir una forma eficiente de memoria para representar un árbol de matrices, por ejemplo en un modelo de jerarquía?

Estoy particularmente interesado en preservar la localidad de datos, y sospecho que un enfoque de tipo estructura de matrices (matrices e índices a matrices) podría ser adecuado.

Además de muchos cálculos matriciales encadenados, esta estructura probablemente se copiará en la memoria un poco, por lo que tener un almacenamiento contiguo sería una gran ventaja.

El árbol como matriz me parece una victoria. Simplemente haga un recorrido profundo de su jerarquía y complete una matriz; al retroceder a través de la recursión, puede actualizar el elemento primario con el índice absoluto para el elemento secundario o solo el delta de mí, y los elementos secundarios también pueden almacenar los índices principales de cualquier manera. De hecho, si usa compensaciones relativas, entonces no necesita llevar la dirección raíz. Supongo que la estructura probablemente se vería algo así

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

... por lo que necesitaría nodos para saber cómo llegar a los hermanos también, ya que no puede (fácilmente) tener una estructura de tamaño variable. Aunque supongo que si usaba desplazamientos de bytes en lugar de desplazamientos de transformación, podría tener un número variable de hijos por transformación:

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

... entonces solo necesita asegurarse de colocar las Transformaciones sucesivas en el lugar correcto.

Así es como se construye un árbol totalmente autónomo con "punteros" secundarios incrustados.

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

(Si desea almacenar ubicaciones relativas, simplemente agregue - currentLocationa las dos escrituras de "ubicación").

La indexación en una matriz de matrices probablemente sería el enfoque más directo y eficiente en la memoria.

Una cadena de transformaciones podría mantenerse en un LIFO como una serie de punteros o enteros u otra pequeña estructura que se indexe en la matriz. Esto ayudaría a evitar el almacenamiento de matrices redundantes y separaría el código de almacenamiento de datos del código de acceso a datos.

En última instancia, simplemente empujaría y desplegaría valores de índice de LIFO para almacenar o reproducir su cadena de transformación.

También podría ahorrar un poco de memoria si la estructura de su matriz también pudiera contener el tipo de transformación ... rotación, traslación, etc. De lo contrario, el tipo debería almacenarse con el índice, lo que daría lugar a una posible duplicación.