
Geometry : 
Subject: [ggl] space partitioning
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 20100911 07:02:27
Simonson, Lucanus J wrote:
> Adam Wulkiewicz wrote:
>>> We should steer the discussion of design away from focusing on what
>>> is wrong and make constructive suggestions about what good
>>> alternatives might be. Then we can discuss how various design
>>> options meet the design goals Adam may have, which is a much more
>>> interesting conversation.
>>
>> Maby I'll describe the original idea. There may be a lot of different
>> tree structures so I'd like to design a generic tree template which
>> might be used as an internal structure of various containers. This
>> tree should probably be the intrusive container. Base node structure
>> I've used has 4 pointers:
>>
>> struct node
>> {
>> node *next;
>> node *parent;
>> node *previous_sibling;
>> node *last_descendant;
>> };
>
> Sorry, the design doesn't make sense to me. I don't see the point of any of these four pointers. Why wouldn't the node just have an array of N child nodes? Why a base class not and not a template parameter and traits? If you are inheriting without a virtual destructor people will ask why. I can't see any answer. Inheritance requires a strong rationale in boost and Liskov substitution principle gets thrown around a lot. You never explained how your is_leaf and is_node traits work, but I see no obvious mechanism.
The original idea was presented in "Game programming gems 4" by Bill
Budge from Electronic Arts. This tree is intended to be a multipurpose
generic tree which enables to traverse it in various ways. The original
node has this structure:
template <typename T>
struct node
{
/*four pointers*/
T value;
/*methods*/
};
I just thought, I'll do intrusive container. User musn't use
inheritance. He must just implement some traits and may use arbitrary
node e.g. described above. The inheritance is not required.
Deriving tree from node is not required. It was used in the original
idea but tree may be just a container with pointer to root node and all
iterators may work on nodes instead of trees.
Pros:
 preorder iterator uses one redirection  next pointer,
 postorder iterator iterates in constant time,
 tree traversing doesn't require recursion, use of implicitly defined
stack or skipping the nodes (the exception is levelorder iterator but
it's used rarely),
 node may have arbitrary number of children nodes.
Cons:
 children iterator is slower than in the case if node has just array of
pointers to children nodes and it isn't random_access_iterator,
 inserting in topbottom building algorithm may have nonconstant
complexity. If the node is inserted from the back, last_descendant
pointers of parent nodes must be updated. Worst case scenario is if
someone puts the node behind the root's last_descendant, all parents
must be updated (but the user may build bottomup or insert nodes from
right to left in topdown algorithm).
The structure of the node:
next points to the node next in preorder iteration.
previous_sibling points to the node if parent node has only one child.
previous_sibling of the first child points to the last child.
last_descendant of leaf node points to this node.
If we have a tree
a
/ \
b d
/ /\
c e f g
pointers points to:
this  a b c d e f g
parent  0 a b a d d d
next  b c d e f g 0
previous_sibling  a d c b g e f
last_descendant  g c c g e f g
Default node's values:
void init(node *n)
{
n>parent = null_ptr;
n>next = null_ptr;
n>previous_sibling = n;
n>last_descendant = n;
}
Navigational functions has constant complexity:
node * next(node * n)
{
return n>next;
}
// next node in preorder iteration
node * next(node * n)
{
return n>next;
}
// previous node in preorder iteration or
// next node in postorder iteration from right to left
node * previous(node * n)
{
node *parent = n>parent;
if ( parent )
return parent>next == n ?
parent :
n>previous_sibling>last_descendant;
else
return null_ptr;
}
node * first_child(node *n)
{
node *next = n>next;
return (next && (next>parent == n)) ? next : null_ptr;
}
node * last_child(node *n)
{
node *child = first_child(n);
return child ? child>preious_sibling : null_ptr;
}
node * next_sibling(node *n)
{
node *sibling = n>last_descendant>next;
return (sibling && (sibling>parent != n>parent)) ?
null_ptr : sibling;
}
node * previous_sibling(node *n)
{
node *parent = n>parent;
return (parent && (parent>next != n)) ?
n>previous_sibling : null_ptr;
}
bool is_root(node *n) { return !n>parent; }
bool is_leaf(node *n) { return n>last_descendant == n; }
Spacial index will be used mainly for search and be updated rarely.
Moreover, preorder traverse algorithm will be used.
But spacial index should have children random access iterator because
e.g. in quadtree or kdtree there are often checks of certain nodes e.g.
left or right. One of the nodes may even not be created. In the node
which have previously described structure there must have been some flag
describing which one child is it.
Recursion is slower than iteration and uses more memory. And there may
be a tree with large number of children. Take e.g. this node:
template <typename T, size_t D>
struct n_tree_node
{
boost::array<n_tree_node*, static_pow<2, D>::ret> children;
T value;
}
The number of pointers in ndimensional quadtree is 2^n, so for octree
we have node with 8 pointers, 4d  16 etc.
There is an overhead when using both types of nodes. Maby some hybrid of
these two nodes would give us children random iterator and fast
preorder iterator. But then the node may be large.
Regards,
Adam
Geometry list run by mateusz at loskot.net