58 #include <OpenMesh/Tools/VDPM/VHierarchy.hh>
71 n_roots_(0), tree_id_bits_(0)
78 set_num_roots(
unsigned int _n_roots)
83 while (n_roots_ > ((
unsigned int) 0x00000001 << tree_id_bits_))
92 return add_node(VHierarchyNode());
97 add_node(
const VHierarchyNode &_node)
99 nodes_.push_back(_node);
101 return VHierarchyNodeHandle(
int(nodes_.size() - 1));
107 make_children(VHierarchyNodeHandle &_parent_handle)
109 VHierarchyNodeHandle lchild_handle = add_node();
110 VHierarchyNodeHandle rchild_handle = add_node();
112 VHierarchyNode &parent = node(_parent_handle);
113 VHierarchyNode &lchild = node(lchild_handle);
114 VHierarchyNode &rchild = node(rchild_handle);
116 parent.set_children_handle(lchild_handle);
117 lchild.set_parent_handle(_parent_handle);
118 rchild.set_parent_handle(_parent_handle);
120 lchild.set_index(VHierarchyNodeIndex(parent.node_index().tree_id(tree_id_bits_), 2*parent.node_index().node_id(tree_id_bits_), tree_id_bits_));
121 rchild.set_index(VHierarchyNodeIndex(parent.node_index().tree_id(tree_id_bits_), 2*parent.node_index().node_id(tree_id_bits_)+1, tree_id_bits_));
126 node_handle(VHierarchyNodeIndex _node_index)
128 if (_node_index.is_valid(tree_id_bits_) !=
true)
129 return InvalidVHierarchyNodeHandle;
131 VHierarchyNodeHandle node_handle = root_handle(_node_index.tree_id(tree_id_bits_));
132 unsigned int node_id = _node_index.node_id(tree_id_bits_);
133 unsigned int flag = 0x80000000;
135 while (!(node_id & flag)) flag >>= 1;
138 while (flag > 0 && is_leaf_node(node_handle) !=
true)
142 node_handle = rchild_handle(node_handle);
146 node_handle = lchild_handle(node_handle);
156 is_ancestor(VHierarchyNodeIndex _ancestor_index, VHierarchyNodeIndex _descendent_index)
158 if (_ancestor_index.tree_id(tree_id_bits_) != _descendent_index.tree_id(tree_id_bits_))
161 unsigned int ancestor_node_id = _ancestor_index.node_id(tree_id_bits_);
162 unsigned int descendent_node_id = _descendent_index.node_id(tree_id_bits_);
164 if (ancestor_node_id > descendent_node_id)
167 while (descendent_node_id > 0)
169 if (ancestor_node_id == descendent_node_id)
171 descendent_node_id >>= 1;