Boost logo

Geometry :

Subject: [ggl] space partitioning
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2010-09-10 19:17:57

Simonson, Lucanus J wrote:
> Simonson, Lucanus J wrote:
>> Adam Wulkiewicz wrote:
>>> Barend Gehrels wrote:
>>>> hi Adam,
>>>>> Yes, I'm using the old version, thanks. But I don't know if I'll
>>>>> make corrections now. It seems that dynamic self balancing spacial
>>>>> index is desirable. What do you think about it?
>>>> I don't know, it (whether or not self balancing) is probably
>>>> dependent on the situation and should ideally be configurable.
>>>> It is of course no problem not making the corrections instantly, I
>>>> however cannot have a thorough look then (this is usually how I do
>>>> it, walking through). At least the main program should compile, and
>>>> I can use the old version, the last time it was sent in two mails,
>>>> can you send one consistent (compiling) set again?
>>> Hi,
>>> Sorry that I haven't written to you sooner. I'd like to show you
>>> something else instead of kd-tree.
>>> The community said that spacial index should work like std::set and
>>> even if I feel different the first data structure should be
>>> implemented this way. The spacial index may be e.g. a dynamic
>>> AABBTree. Leaf and internal nodes should be different classes
>>> derived from one Node class and created by allocator or possibly two
>>> different allocators defined by the user.
>>> I've implemented a generic tree which I'd like to use as a base of
>>> this container. I've taken the idea from "Game programming gems 4"
>>> but my version is an intrusive container without memory allocation.
>>> It's not the 'final' container it's just an implementation of some
>>> needed algorithms and iterators. Users could use this generic tree
>>> class to build their own trees.
>>> I had two designs in mind. First one was the tree which contains
>>> pointer to root. The tree structure would be defined only by nodes.
>>> Nodes could be manipulated only by use of the tree class and an
>>> iterator to node:
>>> child_iterator begin_child(Iter nodeit)
>>> void push_back_child(node *n, Iter nodeit)
>>> tree t;
>>> node *n = (node*)create_internal_node();
>>> t.push_back(n);
>>> n = (node*)create_leaf_node();
>>> t.push_back_child(n, t.root());
>>> The second one is a tree derived from node, which I've chosen. The
>>> main drawbacks are that the tree creation isn't intuitive, there is
>>> more pointers casting and in this case the tree isn't a container
>>> actually:
>>> node *n = (node*)create_internal_node();
>>> tree *t = (tree*)n;
>>> n = create_leaf_node();
>>> t.push_back_child((tree*)n);
>> This syntax isn't technially "legal" because the C++ standard says
>> that the results of casting a pointer of base type to a pointer of
>> derived type if the object pointed to is of base type is undefined.
>> That means there is no guarentee that the code will do what you
>> expect even if it compiles. In reality it does compile and usually
>> does what you expect, but it is against boost coding standards to do
>> with sort of thing. I'm not sure what type your
>> create_internal_node() returns, but I assume it is not tree*. I also
>> don't think the public interface should provide access to internal
>> nodes, but regardless, the design of the internals cannot rely on
>> undefined behavior.
> In addition to relying on undefined behavior it is also poor design. The first design looks better. Tree should not inherit from node. Tree should have-a node member named "root" or something similarly clear. That member should probably be private and no public interface of tree should include reference to node type. Node could even be decared as a private sub-class of tree to keep people's hands off of it and make it eaiser to implement by allowing it to share the template parameters of tree.
> I don't think that internal_node and leaf_node should inherit from a base node class either. Instead let the node contain a union of leaf* and node* in an array (perhaps of size two but could be made template parameter) and a bitfield that indicates whether each element in the array of union is leaf type or node type. Dynamic polymporism is overkill and wasteful of both memory and runtime for this application and I can't really see any benefit to having a common base class for leaves and nodes. Ideally the leaf type would be a template parameter and no requirement about base classes placed upon it.
> 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;

Various types of trees may be created using this node, all navigation
algorithms has constant complexity, pre-order iterator is very fast (one
redirection), post-order and child iterators are fast. Tree container
works on objects of node class. Node may have arbitrary structure. User
must only implement some node traits and pass it to the tree template.

To define leaf and internal nodes one may derive from some basic node
and wrapp the creation and manipulation of two types of nodes inside
some container(e.g. AABBTree). Following code presents how to create
nodes and manipulate them inside two containers (generic tree and some
container using it) not the real internals of any of them.

// user defined types
struct node { node *n1, *n2, *n3, *n4; };
struct node_traits { /*...*/ };

struct internal_node : public node {/*...*/};
struct leaf_node : public node {/*...*/};

// tree creation
typedef node_algorithms<node_traits> na;

node *root = create_internal_node();
leaf_node *l = create_leaf_node();
na::push_back_as_child(root, l);

// pre order iteration
for(node *n = root; n; n = na::next(n))
   if ( na::is_leaf(n) )
     leaf_node *ln = static_cast<leaf_node*>(n);
     // do something
     internal_node *in = static_cast<internal_node*>(n);
     // do something

The nodes might have different structure e.g.:

struct leaf;
struct node;

struct node_base
   union next_
     leaf *l;
     node *n;
   } next;

   node *parent;

   union previous_sibling_
     leaf *l;
     node *n;
   } previous_sibling;

   struct are_leafs_
     unsigned char next : 1;
     unsigned char previous_sibling : 1;
   } are_leafs;

template <typename T>
struct node : public node_base
   leaf *last_descendant;
   T value;

template <typename T>
struct leaf : public node_base
   // leaf node's last descendant is equal to this pointer
   // so it musn't be stored in this case
   T value;

But I think the previous design is more 'elegant' and effective.


Geometry list run by mateusz at