# 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.

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

• If we're talking C++, you'll need to specify a size for your child array or create it at runtime with a memory allocation. – tenpn Sep 3 '10 at 7:47
• The official C99-approved way is to leave the array size specification empty. – user744 Sep 3 '10 at 7:56
• @tenpn- the idea is that you have a purpose built buffer. The whole point is to avoid extra allocations; you can't specify the array size because you don't know how big it'll be. After you write num children, you write into your child array, but then the next Transform starts after the child array ends. (This is why you need to use byte offsets and not indices for this structure; you don't know how big each entry is, but it is still efficient to traverse and is self contained so it can move as a unit.) – dash-tom-bang Sep 3 '10 at 17:00
• This is called the "struct hack." See also: informit.com/guides/content.aspx?g=cplusplus&seqNum=288 – Neverender Sep 3 '10 at 20:39
• @tenpn Aka variable-length structs. Used appropriately they can halve the number of heap allocations. – user77245 Jan 10 '18 at 21:28

Indexing into array of matrices would probably be the most straight forward, memory efficient approach.

A chain of transforms could be held in a LIFO as series of pointers or integers or other small struct that index into the matrix array. This would help prevent storing redundant matrices and would separate the data storage code from the data accessor code.

Ultimately you would just push and pop index values from the LIFO to store or play back your transform chain.

You might also be able to save a little memory if your matrix structure could also contain the transform type...rotation, translation, etc. Otherwise the type would need to be stored with the index resulting in more possible duplication.