Bone parent indices to linked list

morando (163)
I have an array of bone parent indices (as intgers), where root bone is tagged as -1, bone can have only one parent.
At some point i need to traverse thru all children of some arbitrary bone (leaving others untouched) but this seems tough to do with this setup.
I cannot come up with algorithm to create linked list like hierarchy from this , with old DX9 API in their animation system we have structure like this:

1
2
3
4
5
 
struct D3DXFRAME { // bone
... // some irrelevant data members
D3DXFRAME* pFrameSibling;
D3DXFRAME* pFrameFirstChild;
};


where i can simply use recursion to achieve what i want.

Any pointers?
keskiverto (10402)
These D3DXFRAMEs probably form a tree. Each frame knows its next sibling (if it has any) and its first child (if it has any). Remember: siblings are the children of same parent.

A traditional singly linked list has
1
2
3
4
 
struct Node {
  //Foo data;
  Node * next;
};

Compare 'next' and 'pFrameSibling'.

You would use a traditional list by having a pointer to the first node: Node * head = ...
Compare 'head' and 'pFrameFirstChild'.

morando (163)
I cannot wrap my head how to do it.
I got this far, but it fails to print:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
 
#include <iostream>
#include <vector>

struct Bone
{
	int myInx;
	Bone* sibling;
	Bone* child;
};

std::vector<int> parentInx;

void buildTree(Bone* head)
{
	Bone* ptr = nullptr;
	// find first child
	for(std::size_t i = 1; i < parentInx.size(); ++i)
	{
		if(head->myInx == parentInx[i])
		{
			head->child = new Bone;
			head->child->myInx = i;
			ptr = head->child;
			break;
		}
	}

	if(!ptr)
		return;

	// find sibling
	for(std::size_t i = 1; i < parentInx.size(); ++i)
	{
		if(ptr->myInx != i && ptr->myInx == parentInx[i])
		{
			ptr->sibling = new Bone;
			ptr->sibling->myInx = i;
			//ptr = ptr->sibling;
			break;
		}
	}

	if(ptr)
	{
		buildTree(ptr);
	}
}

void printBones(Bone* ptr) 
{
	if(ptr)
	{
		std::cout << ptr->myInx << std::endl;
	}

	if(ptr->sibling)
		printBones(ptr->sibling);

	if(ptr->child)
		printBones(ptr->child);
}

int main()
{
        // this is "legit" bones parent indices
	parentInx.resize(47);
	parentInx[0]  = -1;
	parentInx[1]  = 0;
	parentInx[2]  = 1;
	parentInx[3]  = 2;
	parentInx[4]  = 3;
	parentInx[5]  = 4;
	parentInx[6]  = 5;
	parentInx[7]  = 2;
	parentInx[8]  = 7;
	parentInx[9]  = 8;
	parentInx[10] = 9;
	parentInx[11] = 2;
	parentInx[12] = 11;
	parentInx[13] = 12;
	parentInx[14] = 13;
	parentInx[15] = 14;
	parentInx[16] = 15;
	parentInx[17] = 15;
	parentInx[18] = 15;
	parentInx[19] = 15;
	parentInx[20] = 14;
	parentInx[21] = 20;
	parentInx[22] = 21;
	parentInx[23] = 22;
	parentInx[24] = 23;
	parentInx[25] = 24;
	parentInx[26] = 25;
	parentInx[27] = 23;
	parentInx[28] = 27;
	parentInx[29] = 28;
	parentInx[30] = 23;
	parentInx[31] = 30;
	parentInx[32] = 31;
	parentInx[33] = 14;
	parentInx[34] = 33;
	parentInx[35] = 34;
	parentInx[36] = 35;
	parentInx[37] = 36;
	parentInx[38] = 37;
	parentInx[39] = 38;
	parentInx[40] = 36;
	parentInx[41] = 40;
	parentInx[42] = 41;
	parentInx[43] = 36;
	parentInx[44] = 43;
	parentInx[45] = 44;
	parentInx[46] = 2;

	Bone* head = new Bone;
	head->myInx = 0;
	head->sibling = nullptr;
	head->child = nullptr;
	buildTree(head);

	printBones(head);

	return 0;
}
keskiverto (10402)
You have a tree. Most of the nodes have only one child and no siblings.
Index 0 is the root
Index 2 has children 3, 7, 11, and 46. Thus 3 is the first child of 2 and there is a list: 3->7->11->46
3 has 4 as child. 4 has 5 as child. 5 has 6 as child. 6 has no children.
7 has 8 as child. 8 has 9 as child. 9 has 10 as child. 10 has no children.
11 has 12 as child. 12 has 13 as child. 13 has 14 as child.
14 has children 15, 20, and 33.
15 has children 16, 17, 18, and 19.

If you want to create the tree by iterating the parentInx, then you do need function that adds a node to the tree:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
void insert( Bone * tree, int newindex, int parent )
{
  // search from tree a node X that has index 'parent' (could be a recursive function)

  if ( nullptr == X->child )
  {
    // add new node with newindex as X->child
  }
  else
  {
    Bone * Y = X->child;
    Bone * Z = Y->sibling;
    while ( Z ) {
      Y = Z;
      Z = Y->sibling;
    }
    // add new node with newindex as Y->sibling
  }
}
Last edited on
morando (163)
Sorry for reply this late, but i still have problem with this.
Code so far:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
 
#include <iostream>
#include <vector>

struct Bone
{
	int myInx; 

	Bone* sibling;
	Bone* child;
};

std::vector<int>  vParentIndices;

void buildTree( Bone * X)
{
	int inx = -1;
	// search from tree a node X that has index 'parent' (could be a recursive function)
	for(std::size_t i = 0; i < vParentIndices.size(); ++i)
	{
		if(vParentIndices[i] == X->myInx)
		{
			inx = i;
		}
	}

	if(inx == -1)
		return;

	if ( nullptr == X->child )
	{
		// add new node with newindex as X->child
		Bone* p = new Bone;
		p->myInx = inx;
		p->child = nullptr;
		p->sibling = nullptr;
		X->child = p;
	}
	else
	{
		Bone * Y = X->child;
		Bone * Z = Y->sibling;
		while ( Z ) 
		{
			Y = Z;
			Z = Y->sibling;
		}
		// add new node with newindex as Y->sibling
		if(!Z)
		{
			Bone* p = new Bone;
			p->myInx = inx;
			p->child = nullptr;
			p->sibling = nullptr;
			Z = p;
		}
	}

	buildTree(X->child);
}

void printTree(Bone* tree)
{
	if(tree)
	{
		std::cout << tree->myInx << std::endl;
	}
	if(tree->sibling)
		printTree(tree->sibling);
	if(tree->child)
		printTree(tree->child);
}

int main()
{
	vParentIndices.push_back(-1);
	vParentIndices.push_back(0);
	vParentIndices.push_back(1);
	vParentIndices.push_back(2);
	vParentIndices.push_back(3);
	vParentIndices.push_back(4);
	vParentIndices.push_back(5);
	vParentIndices.push_back(2);
	vParentIndices.push_back(7);
	vParentIndices.push_back(8);
	vParentIndices.push_back(9);
	vParentIndices.push_back(2);
	vParentIndices.push_back(11);
	vParentIndices.push_back(12);
	vParentIndices.push_back(13);
	vParentIndices.push_back(14);
	vParentIndices.push_back(15);
	vParentIndices.push_back(15);
	vParentIndices.push_back(15);
	vParentIndices.push_back(15);
	vParentIndices.push_back(14);
	vParentIndices.push_back(20);
	vParentIndices.push_back(21);
	vParentIndices.push_back(22);
	vParentIndices.push_back(23);
	vParentIndices.push_back(24);
	vParentIndices.push_back(25);
	vParentIndices.push_back(23);
	vParentIndices.push_back(27);
	vParentIndices.push_back(28);
	vParentIndices.push_back(23);
	vParentIndices.push_back(30);
	vParentIndices.push_back(31);
	vParentIndices.push_back(14);
	vParentIndices.push_back(33);
	vParentIndices.push_back(34);
	vParentIndices.push_back(35);
	vParentIndices.push_back(36);
	vParentIndices.push_back(37);
	vParentIndices.push_back(38);
	vParentIndices.push_back(36);
	vParentIndices.push_back(40);
	vParentIndices.push_back(41);
	vParentIndices.push_back(36);
	vParentIndices.push_back(43);
	vParentIndices.push_back(44);
	vParentIndices.push_back(2);

	Bone* root = new Bone;
	root->myInx = 0;
	root->child = nullptr;
	root->sibling = nullptr;
	buildTree(root);

	printTree(root);

	return 0;
}
keskiverto (10402)
There are multiple issues in your code.

Lets start with adding a bit of convenient syntactic sugar:
1
2
3
4
5
6
7
8
9
 
struct Bone
{
	int myInx;
	Bone* sibling;
	Bone* child;

	Bone( int index ) : myInx(index), sibling(nullptr), child(nullptr) {}
	~Bone() { delete child; delete sibling; }
};


Do some work in the main():
1
2
3
4
5
6
7
8
9
10
11
 
int main()
{
  std::vector<int> vParentIndices { -1, 0, 1, 2, 3, 4, 5, 2 }; // non-global
  std::unique_ptr<Bone> root( new Bone( 0 ) );
  for ( size_t i = 1; i < vParentIndices.size(); ++i )
  {
    insertBone( root.get(), i, vParentIndices[i] );
  }
  printTree( root.get() );
  return 0;
}

(There is room for optimization by mapping the created bones.)


You have:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
		Bone * Y = X->child;
		Bone * Z = Y->sibling;
		while ( Z ) 
		{
			Y = Z;
			Z = Y->sibling;
		}
// assert: Z is null, Y is not null
		if(!Z) // unnecessary check
		{
			Bone* p = new Bone;
			p->myInx = inx;
			p->child = nullptr;
			p->sibling = nullptr;
// We made a constructor for Bone to avoid long repeated code like the above

			Z = p; // Z is just a pointer, not part of the tree.
			// Y->sibling = new Bone( inx );
		}


The search:
1
2
3
4
 
Bone * findBone( Bone * root, int index )
{
  // return bone that has myInx==index, or nullptr, if the tree has no such bone
}



And the showdown:
1
2
3
4
5
6
7
8
9
10
11
12
13
 
void printTree(Bone* tree)
{
	if(tree)
	{
		std::cout << tree->myInx << std::endl;
	}
// what if tree is null ?

	if(tree->sibling) // printTree checks for null
		printTree(tree->sibling);
	if(tree->child) // printTree checks for null
		printTree(tree->child);
}
morando (163)
Thank you very much. :)

Now i need to figure out how to free all that allocated memory.

I don't know if i want to use unique pointer as i might wish to store some pointer to it elsewhere so i can modify its data.

EDIT:
Ok, i made every pointer shared_ptr so i dont need to worry about freeing memory, is this ok?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
 
#include <iostream>
#include <vector>
#include <memory>

struct Bone
{
	int myInx;
	std::shared_ptr<Bone> sibling;
	std::shared_ptr<Bone> child;

	Bone( int index ) : myInx(index), sibling(nullptr), child(nullptr) {}
	~Bone() { }//delete child; delete sibling; }
};

std::vector<int>  vParentIndices;

void insertBone(std::shared_ptr<Bone> X, int newindex, int parent)
{
	if(vParentIndices[newindex] == parent)
	{
		if(X->child == nullptr)
		{
			X->child = std::make_shared<Bone>(newindex);//new Bone(newindex);
		}
		else
		{
			std::shared_ptr<Bone> Y = X->child;
			std::shared_ptr<Bone> Z = Y->sibling;
			while ( Z ) 
			{
				Y = Z;
				Z = Y->sibling;
			}

			Y->sibling = std::make_shared<Bone>(newindex);//new Bone( newindex );
		}
	}
}

void printTree(std::shared_ptr<Bone> tree)
{
	if(tree)
	{
		std::cout << tree->myInx << std::endl;
		if(tree->sibling)
			printTree(tree->sibling);
		if(tree->child)
			printTree(tree->child);
	}
}

int main()
{
	vParentIndices.push_back(-1);
	vParentIndices.push_back(0);
	vParentIndices.push_back(1);
	vParentIndices.push_back(2);
	vParentIndices.push_back(3);
	vParentIndices.push_back(4);
	vParentIndices.push_back(5);
	vParentIndices.push_back(2);
	vParentIndices.push_back(7);
	vParentIndices.push_back(8);
	vParentIndices.push_back(9);
	vParentIndices.push_back(2);
	vParentIndices.push_back(11);
	vParentIndices.push_back(12);
	vParentIndices.push_back(13);
	vParentIndices.push_back(14);
	vParentIndices.push_back(15);
	vParentIndices.push_back(15);
	vParentIndices.push_back(15);
	vParentIndices.push_back(15);
	vParentIndices.push_back(14);
	vParentIndices.push_back(20);
	vParentIndices.push_back(21);
	vParentIndices.push_back(22);
	vParentIndices.push_back(23);
	vParentIndices.push_back(24);
	vParentIndices.push_back(25);
	vParentIndices.push_back(23);
	vParentIndices.push_back(27);
	vParentIndices.push_back(28);
	vParentIndices.push_back(23);
	vParentIndices.push_back(30);
	vParentIndices.push_back(31);
	vParentIndices.push_back(14);
	vParentIndices.push_back(33);
	vParentIndices.push_back(34);
	vParentIndices.push_back(35);
	vParentIndices.push_back(36);
	vParentIndices.push_back(37);
	vParentIndices.push_back(38);
	vParentIndices.push_back(36);
	vParentIndices.push_back(40);
	vParentIndices.push_back(41);
	vParentIndices.push_back(36);
	vParentIndices.push_back(43);
	vParentIndices.push_back(44);
	vParentIndices.push_back(2);

	std::shared_ptr<Bone> root = std::make_shared<Bone>(0);
	for ( size_t i = 1; i < vParentIndices.size(); ++i )
	{
		insertBone( root, i, vParentIndices[i] );
	}
	printTree( root );

	return 0;
}


Thank you again. :)

EDIT2:
I am very tired, i see that i made some errors:
calling this:
 
 
insertBone( root, i, vParentIndices[i] );


but checking :
 
 
if(vParentIndices[newindex] == parent)


which are the same, i dont need this check?
Last edited on
Topic archived. No new replies allowed.