memory efficiency - Efficient structure for representing a transform hierarchy

Can anyone suggest a memory efficient way to represent a tree of matrices, for example in a hierarchy model?

I'm particularly keen to preserve data locality, and I suspect a structure-of-arrays (matrices & indices to matrices) type approach might be suitable.

As well as many chained matrix computations, this structure will probably be copied around in memory a fair bit, so having contiguous storage would be a big bonus.

Answer

The tree-as-array sounds like a win to me. Just do a depth-first traversal of your hierarchy and fill out an array; when rewinding through the recursion you can either update the parent with the absolute index to the child or just the delta-from-me, and the children can store the parent indices either way as well. Indeed, if you use relative offsets then you don't need to carry the root address around. I suppose that the structure would probably look something like

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

...so you'd need nodes to know how to get to siblings too since you can't (easily) have a variable size structure. Although I guess if you used byte offsets instead of Transform offsets, you could have a variable number of children per transform:

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

...then you just need to make sure that you put successive Transforms in the right place.

Here's how you build a totally self-contained tree with embedded child "pointers".

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

}

(If you want to store relative locations, just add - currentLocation to the two "location" writes.)