Skip to main content
GameDev.net gamedev.net
🔒 Locked

accessing/modifying data in a tree structure (hierarchical skeleton)

Started by TheAdamRomney Jan 12, 2013 at 11:05 AM 0 replies 1.6k views
Original Post
TheAdamRomney
TheAdamRomney

Given a hierarchical joint/bone structure, what is the fastest/best way to access a specific node, e.g. LeftKnee? I take it there is no way to access a node in constant time or am I forgetting something? Would it be possible to create a map that pairs a string name identifier to the JointNode pointer? This seems like a bad idea because now there are two structures, the map and the node tree itself. But otherwise, it would seem that a depth first traversal with string comparison at every step is required every time. Perhaps this isn't so bad since there are relatively few joint nodes, but doesn't this add up if you have a large population of characters being articulated?

If further context is helpful, I'm tracking the location of end effectors, or leaf nodes, and may need to modify a joint node further up the tree via inverse kinematics.

mrbastard
mrbastard

Does the hierarchy change? If not, you don't need to store in a tree with actual parent-> child ptrs. Instead, store all the bones in an array/vector, and keep the index of each. Instead of traversing the tree, just look up using the index. Keep a map of strings to indices for lookup in asset loading / ui / scripting, but otherwise refer to joints by their index.

[size="1"]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.