Tell me more ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 2 down vote favorite

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?

share|improve this question
Is the hierarchy modification really a bottleneck? – Jari Komppa Mar 15 '11 at 14:23
Ultimately probably not but I was curious from an academic standpoint. Also, I did some really rough testing and when I put all the transforms in an array and updated them by going linearly through the array it ran almost an order of magnitude faster than by traversing the tree (same exact calculations on the transforms - the only thing I changed was how the list of transforms was iterated). That test is definitely not indicative of any "real world" performance but seeing that difference did make me curious about seeing if there was a different approach. – Mattia Mar 15 '11 at 14:48
Well.. judging from this, 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).. and in a real-world case some hybrid might be the optimal, leaving most of the hierarchy static while other parts are dynamic.. I won't post this as an answer though, as someone might have actual experience on the matter =) – Jari Komppa Mar 15 '11 at 14:59
Thanks for the suggestions/opinions - they definitely work as an answer for me. I really just wanted to know if there was some low hanging fruit to be picked but it sounds like there isn't so I think I'll stick to the tree. – Mattia Mar 15 '11 at 21:33

2 Answers

up vote 0 down vote accepted

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.

share|improve this answer
up vote 2 down vote

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.

share|improve this answer
Thanks for the link to the article. The scene graph approach in it was interesting and while I'll stick to the tree for now it's definitely nice to know about it for future reference – Mattia Mar 17 '11 at 12:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.