Structure efficace pour représenter une hiérarchie de transformation

Quelqu'un peut-il suggérer un moyen efficace de mémoire pour représenter un arbre de matrices, par exemple dans un modèle de hiérarchie?

Je tiens particulièrement à préserver la localisation des données, et je soupçonne qu'une approche de type structure de tableaux (matrices et indices sur matrices) pourrait convenir.

En plus de nombreux calculs matriciels chaînés, cette structure sera probablement copiée en mémoire un peu, donc avoir un stockage contigu serait un gros avantage.

L'arbre comme un tableau me semble être une victoire. Faites simplement une analyse en profondeur de votre hiérarchie et remplissez un tableau; lors du rembobinage de la récursivité, vous pouvez mettre à jour le parent avec l'index absolu vers l'enfant ou simplement le delta-from-me, et les enfants peuvent également stocker les index parents dans les deux cas. En effet, si vous utilisez des décalages relatifs, vous n'avez pas besoin de transporter l'adresse racine. Je suppose que la structure ressemblerait probablement à quelque chose comme

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

... vous auriez donc besoin de nœuds pour savoir comment vous rendre chez vos frères et sœurs, car vous ne pouvez pas (facilement) avoir une structure de taille variable. Bien que je suppose que si vous avez utilisé des décalages d'octets au lieu de décalages de transformation, vous pouvez avoir un nombre variable d'enfants par transformation:

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

... alors il vous suffit de vous assurer que vous placez les Transformations successives au bon endroit.

Voici comment vous créez une arborescence totalement autonome avec des "pointeurs" enfants intégrés.

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 vous souhaitez stocker des emplacements relatifs, ajoutez simplement - currentLocationles deux écritures "emplacement".)

L'indexation dans un tableau de matrices serait probablement l'approche la plus simple et la plus efficace en termes de mémoire.

Une chaîne de transformations peut être conservée dans un LIFO sous la forme d'une série de pointeurs ou d'entiers ou d'une autre petite structure qui indexe dans le tableau matriciel. Cela aiderait à empêcher le stockage de matrices redondantes et séparerait le code de stockage de données du code d'accès aux données.

En fin de compte, il vous suffirait de pousser et d'afficher les valeurs d'index du LIFO pour stocker ou lire votre chaîne de transformation.

Vous pourriez également être en mesure d'économiser un peu de mémoire si votre structure matricielle pouvait également contenir le type de transformation ... rotation, traduction, etc. Sinon, le type devrait être stocké avec l'index, ce qui entraînerait une duplication plus possible.