Geometry Boost List: [ggl] space partitioning

Subject: [ggl] space partitioning
From: Simonson, Lucanus J (lucanus.j.simonson)
Date: 2010-09-14 13:48:10

Adam Wulkiewicz wrote:
> 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
> multi-purpose generic tree which enables to traverse it in various
> ways. The original node has this structure:

A good general tree is a lot of work in and of itself.  From your starting point it isn't clear that the tree you will come up with would even be good.  I think storing all those extra pointers is a huge waste of memory and am thoroughly unconvinced that the runtime advantage of caching these pointers in all the nodes of the tree would offset the runtime disadvantage of consuming so much more memory in the general case.  It is working in exactly the opposite direction from what I would consider good tree design.

Have a look at:
http://judy.sourceforge.net/examples/design_rule_checking.pdf

And http://judy.sourceforge.net/index.html

Judy is pretty clearly a lot of work.  It is LGPL, so you can't use it directly, but if you create a good tree *concept* and generic interface for specifying a tree data structure you don't need to implement anything more than the na?ve tree data structure yourself and can instead concentrate on the geometry aspect of the problem.  We would like to decouple the algorithms for spatial query from the data structures through generic programming.  Alternately you can provide a concept for spatial query data structure, a reference implementation and allow people to map things like the judy quad tree to that concept to specify superior spatial query data structures to be used with geometry algorithms that rely on them.  Crucially, the algorithms (like nearest neighbor search etc) should not be member functions of some query data structure class, but instead decoupled from the data structure using the spatial query concept as the abstraction.

So far you seem to be designing from the bottom up based on components you like, such as this game programming gems data structure.  I suggest defining what you want the interfaces to look like and what kinds of abstractions you want to provide (and why) then fill in low level detail.  Don't create abstractions for their own sake, recognize that there is a trade off between flexibility and ease of use.  If you just define a concept that existing spatial query data structures can be mapped to successfully and don't actually implement one yourself that would be a big win, with very little risk of creating something inferior to what everyone is already using.

Regards,
Luke