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