Geometry Boost List: [ggl] space partitioning

Subject: [ggl] space partitioning
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2010-08-16 07:24:17

Hi,

My name is Adam Wulkiewicz and I'd like to take a part in GGL evolution 
by implement space partitioning data structures. Those who are 
subscribers of Boost mailing list know the situation. I've moved the 
discusion from there.

W dniu 2010-08-16 10:04, Barend Gehrels napisal(a):
 > hi Adam,
 >
 >
 >
 >>> Le 15/08/2010 11:07, Adam Wulkiewicz a ?crit :
 >>>
 >>>> It strongly depends on used algorithm if you need it or not. If 
you use
 >>>> some kind of internal, temporary objects you need it.
 >>>> See e.g.
 >>>> http://www.cgg.cvut.cz/members/havran/ARTICLES/ingo06rtKdtree.pdf or
 >>>> http://kesen.realtimerendering.com/Intel-EG07.pdf=
 >>>
 >>> I may be missing something here, but I don't see why the temporary
 >>> objects in question cannot be stored on the execution stack.
 >>
 >> Implementing dynamic memory allocation on the stack could be quite
 >> tricky.
 >
 > Thanks for the links.
 >
 > In Boost.Geometry we do not allocate dynamic memory ourselves; all
 > polygons, rings, lines, multi-polygons etc are stored as an std::
 > container, which can be selected at compile-time by the library user (as
 > a template-template-parameter). Besides that it is not part of the
 > concept so library users might select another solution.
 >
 > Don't know if this is possible in this case, but if it is possible, I
 > would prefer that approach.

I think it's possible that we misunderstood each other. I'll clarify.

The simplest form of tree's nodes structure will be a std::vector (like 
in the heap). For point kd-tree we may have nodes which are our points, 
possibly with some kind of additional data. But for volumetric objects, 
nodes must specify splitting planes positions and we must store a 
conteiner of objects in each leaf node (e.g. std::vector). In both cases 
memory is allocated on the heap e.g. by std::allocator. Btw, in the 
second example we end up with half of tree nodes containing empty 
vectors because objects are stored in leafs so different internal 
structure should be used.

In the first article we have an algorithm creating kd-tree for 
volumetric objects using Surface Area Heuristic. The container 
(std::vector) of split candidates is generated at the beginning of 
building process, sorted and passed to the recursive build function. 
It's possible that on each recursive step some objects will overlap the 
splitting plane. New bounds on both sided of the plane are calculated 
and new split candidates are generated (std::vector), sorted and merged 
with split candidates for each node. In addition, we must pass proper 
objects to the left and right child nodes so we have to create 
std::vectors of children nodes' objects each time or use one container 
created at the beginning (just like for split candidates) insert newly 
created objects (copies of objects overlapping the splitting plane) and 
rearrange the ranges of this container in order to pass iterators 
defining those ranges. These all std::vector objects are created on the 
stack but memory is allocated on the heap.

And (as far as I know) there is not possible to dynamically allocate 
memory on the stack. There might be some kind of fixed-size container 
(e.g. boost::array) and std::vector used if number of objects exceeds 
this fixed-size container's size. There might be some kind of allocator 
which does it. But I don't know if this is what you had in mind. If you 
thought of that temporary containers objects should be created on the 
stack in the building process there is no problem, but the memory will 
still be allocated on the heap.

And yes, all of these containers and allocators may be specified by the 
user.

Regards,
Adam