I'm looking for a way to represent a dynamic transform hierarchy (i.e. one where nodes can be inserted and removed arbitrarily) that's a bit more efficient than using a standard tree of pointers . I saw the answers to this question ( Efficient structure for representing a transform hierarchy ), but as far as I can determine the tree-as-array approach only works for static hierarchies or dynamic ones where nodes have a fixed number of children (both deal-breakers for me). I'm probably wrong about that but could anyone point out how? If I'm not wrong are there other alternatives that work for dynamic hierarchies?
Well.. judging from the discussion, I'd say if the changes are frequent, the tree model wins; if changes are infrequent, the array model wins (it's ok to rebuild the array if it's rare)..
In a real-world case some hybrid might be the optimal, leaving most of the hierarchy static while other parts are dynamic.
I didn't post this as an answer before though, as someone might have actual experience on the matter, instead of just pondering on it on an algorithmic level. In any case, I'd look into this only after it's found to be an issue.
One quite efficient representation is an array of matrices combined with an array of parent indices. If you keep things sorted, and updates is just a loop over the array. See Practical Examples in Data Oriented Design by the BitSquid guys. You might not need to resort that much depending of your change patterns.