Re: [boost] Boost.ntree_container (bi_tree, quad_tree, oct_tree, etc ptr containers) Is there any interest in this?

Subject: Re: [boost] Boost.ntree_container (bi_tree, quad_tree, oct_tree, etc ptr containers) Is there any interest in this?
From: Dan Walters (dan_at_[hidden])
Date: 2012-03-08 18:47:57

Hi Joel,

Thanks for the interest and the feedback.

Your comments regarding moving entities are interesting. Supporting this
well would be a great feature although I think there is a huge risk in
making this library too feature-full and a more tightly defined library
would be much more flexible. For a game, you may want your static objects
to be stored separately to your moving objects. This is how the major
physics libraries do it I think. Note that if you are using soft bodies or
other physical simulations, then your physical library would do all the
spacial management for you and so you wouldn't need your own spacial
container anyway.

For moving objects, depending on how they move, how frequently, etc. will
determine the best choice of container, and a tree may not be it. I think
it is useful to define the tree structure as being a fixed interval
container, with dimensions to the power of two as this gives the fastest
and most fundamental type of tree (as I understand).

In practical terms, the tree would represent AABB of size 2^n and would be
accessed using integers.

I hadn't thought about memory management strategies. I had assumed a
ptr_container style container would be the most useful but actually std
style containers make a lot of sense also.

Best wishes,

Dan

2012/3/8 Klaim - Joël Lamotte <mjklaim_at_[hidden]>

> Hi,
>
> as a game developer I would say "yes" it is interesting to me but that
> depends a lot on the 'details' :
>
> If it doesn't support well moving entities (fast change of leaf content in
> the tree), then it isn't very interesting for (soft) real-time simulations
> (whatever the point of simulation).
> So do you plan on supporting this? Your interface don't suggest any way to
> insert or remove something from the tree.
>
> I assume that "tunnels" space partition would be off topic?
>
> What would the tree contain? Points? Spheres? Other kind of volumes?
> (axis-aligned box, oriented box, pyramids, etc)?
> Or maybe you want the user to provide data and a (set of) collision check
> function(s) or something similar?
>
> Would there be different memory management strategies proposed?
> Allowing fixed 'capacity' with no memory allocation/deallocation - and flat
> as a boost::flat_map - would be interesting to game devs, even if you
> provide custom allocators.
>
> That being said, I'm not a specialist in the domain, so I hope experts will
> ask more meaningful questions than mine.
> My 2 cents.
>
>
> Side note: if I had a generic container to partition space, I would also
> use it in AI too.
> Having several different and specialized representation of the same space
> is very helpful in games but space efficiency becomes a big concern when we
> do this.
>
> Joël Lamotte
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost