Sign in to follow this  

Bones with multiple children

This topic is 2665 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi,

I'm confused again. Yes again. If you took the following type of set-up:

animFrame root; level 1
animFrame spine; level 2
animFrame r_hip; level 3
animFrame l_hip; level 3
animFrame head; level 3

and you intended to use the typical recursive function to loop through all the frame updates... what do you do when you hit the spine bone? Consider the root is the parent of spine. Spine has three children, the head (or neck bone) and the two hip bones. Now I've only seen recursive functions with one child and one sibling frame in them. I know if you hit the child frame l_hip and have its sibling as r_hip you'll be ok as they'll both update within the recursion. But what about the head bone? Is that another *sibling* of the hip bones? Am I talking total carp? Who knows! I'm trying that's all ;o)

So seriously for a moment - should I set-up my frame hierachy with the head bone as a sibling of the two hip bones? Is this acceptable - is it the right idea? I could goto animFrame r_hip, list its sibling as l_hip and list l_hip's sibling as animFrame head right?

Thanks ;o)

Share this post


Link to post
Share on other sites
Quote:
Original post by adder_noir
Hi,

I'm confused again. Yes again. If you took the following type of set-up:

animFrame root; level 1
animFrame spine; level 2
animFrame r_hip; level 3
animFrame l_hip; level 3
animFrame head; level 3

and you intended to use the typical recursive function to loop through all the frame updates... what do you do when you hit the spine bone?

This is a bit of an odd question - having multiple children on a single bone should not affect your recursion at all. Just recursively update all the child bones of the current bone when updating the bone animations.

so, to update the hierarchy above, you would first call UpdateFrame(root), which would update the local animation transformation of that bone, and then after (or before, doesn't matter) that it would call UpdateFrame(spine) for its only child spine, which would update its animation tm frame, and call a sequence of three UpdateFrames, namely UpdateFrame(r_hip), UpdateFrame(l_hip) and UpdateFrame(head). Each of these three would update their own anim tm frames, and return since they don't have any children to recurse into.

If your UpdateFrame is also computing the new bone->world matrices, or "global world" transformation matrices of each bone, then you can also pass propagate the parent tm matrix as a parameter into the recursion and do the multiplication while you go along.

Quote:

But what about the head bone? Is that another *sibling* of the hip bones? Am I talking total carp? Who knows! I'm trying that's all ;o)

So seriously for a moment - should I set-up my frame hierachy with the head bone as a sibling of the two hip bones? Is this acceptable - is it the right idea? I could goto animFrame r_hip, list its sibling as l_hip and list l_hip's sibling as animFrame head right?
Thanks ;o)


Having multiple siblings on a bone is ok - which is equivalent to saying that a single bone has multiple children. Sibling relation is transitive, so r_hip, l_hip and head are all siblings of each other.

Or, perhaps you were doing something else in your UpdateFrame that is problematic in this context?

Share this post


Link to post
Share on other sites
Quote:
Original post by clbThis is a bit of an odd question


I'm a bit of an odd person :oD I think you're post has cleared it up to be honest although I haven't digested it fully yet. I justed wanted to say thanks for replying ;o)

Share this post


Link to post
Share on other sites
Ok great post pal. So I'd have to store the number of children of a frame in each frame right? I was getting confused as the only examples I've seen don't do that, although I was probably reading about less articulated skeletons. probably just a robot arm joint or something.

I was thinking of going something like this:

pseudo:


int childNo = 3;
mat local;
mat parent;
mat combined;
frame* l_hip;
frame* r_hip;
frame* head;
....
....
animate(&l_hip, &combined);
animate(&r_hip, &combined);
animate(&head, &combined);

animate(frame* child, mat* parent)
{
....
}




Far from perfect but it gets the idea across I just typed that up on the fly. I've done stuff like this before yet never considered how much more specific I'll have to be for a full skeleton. I think maybe once I've built a skeleton template with all frames correctly and individually built from the perespective of numbers of children and siblings I should maybe leave it alone and fit any future models into that template.

It's obviously a bigger and more individual specific job than I thought. You can't just write one general frame struct for all joints in a complex skeleton ;o)

Thanks so much clb another really good post.

Share this post


Link to post
Share on other sites
Ah, right, you're only storing a flat list of bone structs to represent your tree hierarchy. In that case, you can try something like the following:

struct Bone
{
string name;
int parentIndex; // -1 for no parent.
float3x4 tmMatrix; // The bone->world transformation matrix.
};

// The bones must be presented here in ascending order of parentIndex.
Bone testSkeleton[] =
{
{ "root", -1, float3x4::identity },
{ "spine", 0, float3x4::identity },
{ "r_hip", 1, float3x4::identity },
{ "l_hip", 1, float3x4::identity },
{ "head", 1, float3x4::identity },
};

// This function defined by the animation data source.
float3x4 ComputeNewLocalBoneTransform(string boneName)
{
// Returns the new tm matrix to transform the given bone by name from local->parent.
}

void UpdateSkeleton(Bone *skeleton, int numBones)
{
for(int i = 0; i < numBones; ++i)
{
float3x4 tm = ComputeNewLocalBoneTransform(skeleton[i]->name);
if (skeleton[i]->parentIndex != -1) // If this skeleton has parent, accumulate the parent transform.
skeleton[i]->tmMatrix = skeleton[skeleton[i]->parentIndex]->tmMatrix * tm;
else // no parent, the bone->world tm equals the local bone tm.
skeleton[i]->tmMatrix = tm;
}
}


In the above loop, as long as the parentIndex of each bone is a smaller number than the index of the bone itself, the propagation works ok, since you're guaranteed to have recomputed the new tm of the parent before computing the child bone tm.

This way you can avoid having to do recursion (and also, that inner 'if' could be optimized away, if only the first bone in the skeleton is parentless).

Edit:I use the Matrix*vector convention when concatenating the matrices above.

Thanks for the compliment. Hope this helps.

Share this post


Link to post
Share on other sites
Quote:
the head bone as a sibling of the two hip bones?

Not quite. Head would be a sibling of l_hip.

A common approach to multiple children is for each frame to have a pointer to one child and one sibling, either or both can be NULL.

When the hierarchy is being set up and a frame needs to add a new child frame:

- check if the frame already has a child.
- if not, set the new child as the child of the frame - done
- if it already has a child, see if the child has a sibling.
- if the child doesn't have a sibling, set the new child as a sibling of the child - done
- if the child has a sibling, check if the sibling has a sibling.
Loop:
- if the sibling doesn't have a sibling, set the new child as a sibling of the sibling - done
- if the sibling has a sibling, check if the sibling has a sibling.
Goto Loop

In the case you mention:

root
- root child = spine
-spine child = r_hip
- r_hip sibling = l_hip
- l_hip sibling = head

The recursive transform function is then something like:

void SetCombinedTransform( frame Frame, matrix parentMatrix )
{
Frame.CombinedTransform = Frame.Transform * parentMatrix;

if( Frame.Child ) SetCombinedTransform( Frame.Child, Frame.CombinedTransform )
if( Frame.Sibling ) SetCombinedTransform( Frame.Sibling, parentMatrix )
}


Share this post


Link to post
Share on other sites
My word some bloody good information there!!! I'll have to start digging in thanks chaps ;o)
****
I've dug in. I don't what to say really when seeing such good informative posts. Makes me wonder why some people are so keen to help others. Guess philanthropy is a real phenomena ;o)

clb:

Very, very nice way of doing it. Means I can avoid recursion if I've got that right. I'm going to try your method out as it means I can build the hierachy alot easier than the way I was. Thankyou so much.

buckeye:

My old confidant/guru/etc... :o) That's how I was thinking it could/should be done. Quite advanced for me though conceptually. I have difficulty visualising it that way. Guess I'll have to accept I've got a long way to go before I understand this as well as you! Damn fine post sir thanks. I'm going to re-read it until I fully understand it.

I've rated you guys up but as always I never see the rating move. I'll re-post when I've done some more work. Thanks!

[Edited by - adder_noir on August 29, 2010 1:17:52 AM]

Share this post


Link to post
Share on other sites
Ok I've begun the implementation. I had some issues getting this to work inside of a class but this has now worked. I'd appreciate it someone could throw a shot of the eye over it:

#ifndef MAIN_H_INCLUDED
#define MAIN_H_INCLUDED

struct bone
{
int myint;
};

class myClass
{
bone mybone[];
void init_bone(void)
{
bone mybone[] =
{
{1},
};
}
};

#endif // MAIN_H_INCLUDED



I want that variable mybone held as a data member, I do not want it created within the scope of a function of it will be lost when said function ends. Is it ok to define it like this? Thanks.

Share this post


Link to post
Share on other sites
First, the purpose for the type of frame implementation I described is simply to end up with a frame structure that's fixed - in size and members. That is, there're aren't any worries about how many children or siblings it refers to - there's either one or none of each. You can certainly use a different frame structure, using std::vector for children, etc., if you find it easier to use.

The usefulness of the class you've begun to describe depends entirely on how you intend to use it! [smile] Whether or not the data members go out of scope also depends entirely on how you create instances of that class.
Quote:
I do not want it created within the scope of a function of it will be lost when said function ends.

Depends on how you "create" it. Creation of objects within a function is a very common occurrence. What you need to be concerned with is which memory "space" you're using to create it.

void MyCreationFunction1()
{
MyClass boneThing; // created on stack
boneThing.boneNumber = 123;
}
// above - all is lost [sad]

void MyCreationFunction2()
{
MyClass boneThing; // with a proper copy constructor
boneThing.boneNumber = 123;
someGlobalStdVector.push_back(boneThing); // a copy is made on the heap
}
// the copy is in the vector!

void MyCreationFunction1()
{
MyClass *boneThing; // the [b]pointer[/b] is on the stack
boneThing = new MyClass; // the pointer points to the heap
boneThing->boneNumber = 123;
anotherGlobalStdVector.push_back(boneThing); // a copy of the pointer is made on the heap
}
// a pointer to a block of heap memory is in the vector!




In the above code, it's intended that the vectors are NOT local to the function. I.e., the vector does not go out of scope when the function returns.

Share this post


Link to post
Share on other sites
Awesome, thanks pal I need to dig into that one again cheers ;o)

***
Nice job buck, just got a load of that stuff to work. I'm going to probably settle now I understand it, for your method with the frame stuff then experiment with our other mate clb's gear later. I understand things alot better now.

God this stuff is hard! :oD

[Edited by - adder_noir on August 29, 2010 6:14:02 AM]

Share this post


Link to post
Share on other sites
Ok my set-up at the moment is going something like this:

virtual void load_soldier_hierachy(void)
{
D3DXMATRIX offset;

//////////////////////////////////////////////////////////////

D3DXMatrixTranslation(&offset, 0.0f, 0.0f, 0.0f);
root.jointOffset = offset;
root.child = &spine;
root.sibling = NULL;

//////////////////////////////////////////////////////////////

D3DXMatrixTranslation(&offset, 0.0f, 0.0f, 0.0f);
spine.jointOffset = offset;
spine.child = &head;
spine.sibling = &l_hip;

//////////////////////////////////////////////////////////////

D3DXMatrixTranslation(&offset, 0.0f, 0.0f, 0.0f);
l_hip.jointOffset = offset;
l_hip.child = &l_leg;
l_hip.sibling = &r_hip;

//////////////////////////////////////////////////////////////

D3DXMatrixTranslation(&offset, 0.0f, 0.0f, 0.0f);
r_hip.jointOffset = offset;
r_hip.child = &r_leg;
r_hip.sibling = NULL;

//////////////////////////////////////////////////////////////

return;
}



Once I've got it running like this I'm going to switch to clb's method i think. Just though I'd throw some code up in case anyone can see a glaring error in it. Only done the two joints right now still working on the rest!

I made the right hip's sibling pointer NULL. Although technically it IS l_hip but when the recursive function goes through it all by the time it hits r_hip all it's siblings have will have been updated so to prevent the risk of extra recursion I've made the last frame's sibling pointer NULL. That's because I decided to make the spine and the two hips of equal order in the hierachy. Really a spine rotation shouldn't alter the hips as there's a joint at the pelvis - the spine.

Is that right? Does anyone know what the hell I'm talking about?

Share this post


Link to post
Share on other sites
Can't quite remember where i heard it but the quote is something like "When you see trees, think recursion. When you seen recursion, think tree" Essentially any system with some type of hierarchical representation needs a way to perform operations on objects or hierarchies of those objects, and this is where recursion shines.

Understanding the data structure itself will give you a better idea of how and why it's used.

Share this post


Link to post
Share on other sites

This topic is 2665 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this