Boost.ntree_container (bi_tree, quad_tree, oct_tree, etc ptr containers) Is there any interest in this?
Hi all, I am proposing adding spacial containers for efficiently storing and accessing data of a spacial nature in fixed size trees. n-tree data structures would be useful where data relates to a 1D, 2D or 3D location, providing n-array searching of an n-array volume. N-tree data structures are commonly used in 3d applications, and are rarely particularly specialized. Their use is fundamental however they are frequently written by application programmers, due to a lack of free open source implementations (to the limit of my research). Their sophistication, like any container, is slim but easy to get wrong and beyond the ability and time contraints that should be assumed of the application programmer. It is a flexible and standard enough concept that a single implementation can be expected to meet a majority of requirements. I think there is the opportunity to create a solid implementation of templated n-tree pointer containers. The ntree container would be a tree representing an narray of elements with all dimensions being the same and being a power of two. The tree is memory efficient where areas within the volume are not occupied, and so "branches" and "leaves" are not created. The tree is well suited to geometrical operations such as ray picking or plane culling of the volume. An n-tree structure could be used in the place of any sparely populated n dimensional array where memory saving is the objective. The existing libraries I have found are licensed under GNU licenses. A ntree container should implement: get reset overloaded (array style) operators Optional implementations: views - a subset object representing an area or volume within the tree for accelerated access to a group of leaves that are positioned near to each other raycasting plane culling (getting leaves within a set of planes) etc. Is there interest in such a library? Many thanks, Dan
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
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@gmail.com>
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
On Fri, Mar 9, 2012 at 00:47, Dan Walters <dan@mcro.org> wrote:
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.
I don't consider allowing adding/removing values in a tree in a very short time (or at least in a predictable time) a feature addition. Also, I don't see in your interface how do you populate the tree?
For a game, you may want your static objects to be stored separately to your moving objects.
It depends (on the game). Basically, static objects might be still needed in the same tree than moving objects if there are possible interractions (physics, graphics or not).
This is how the major physics libraries do it I think.
I'm not sure, but I guess it would allow some kind of optimizations.
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.
That's why i'm not interested in it as a replacement for other libraries. However it can be really useful when you need to get a space partionning container with specific data that have nothing to do with graphics or physics. I have such use case for a game, so maybe your library would be fit, maybe not.
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).
It's only about removing an object then reinsert it in the tree, with an optimization to no-operation if the operation is detected as unnecessary (the entity is still in the same leaf). That's how most game quadtree and octree work. I'm not talking about applying physics, only space partition and efficiency of the remove/insert algorithm.
In practical terms, the tree would represent AABB of size 2^n and would be accessed using integers.
That was my understanding, but what would the leaves contain? Also, what would the integers represent? Is it too early to ask for an example of use you might have think about?
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.
As I said, if you want to target (soft) real time simulation (including most kind of games), you need it to be very fast and very stable on memory. Boost libraries aren't guaranteed to be "very fast" but most are fast enough, and the new containers are now solving problems specific to constrains we have with simulations. For this particular problem, something that would behave like a std::map would be "interesting" to some game developers but wouldn't be interesing for most, mainly because of the cost of insertion/remove of leafs (allocation/deallocation). However, if you manage to get something that behave like a boost::flat_map ( http://www.boost.org/doc/libs/1_49_0/doc/html/container/non_standard_contain... ) then it would be very interesting even in hard constrained context because the user can reserve memory from the beginning and never make it grow(allocate) or shrink (deallocate). If the insertion and remove is fast or constant, then it becomes very useful. The std::map-like version would be enough for me to use it, while the flat version would allow me to not pay the node allocation/deallocation cost each time I have to manipulate the map, with moving entities. Allowing custom allocator is, I think, basic requirement for any generic container to be accepted in boost. Hope it helps. Joël Lamotte
I think this is a very good idea. What about other kinds of spatial containers like r-trees or kd-trees? How would you represent the objects within the tree? Are they points, boxes, arbitrary geometric objects? Does the container play well with existing geometry libraries, like boost.geometry? On 03/08/2012 11:13 PM, Dan Walters wrote:
Hi all,
I am proposing adding spacial containers for efficiently storing and accessing data of a spacial nature in fixed size trees.
n-tree data structures would be useful where data relates to a 1D, 2D or 3D location, providing n-array searching of an n-array volume. N-tree data structures are commonly used in 3d applications, and are rarely particularly specialized. Their use is fundamental however they are frequently written by application programmers, due to a lack of free open source implementations (to the limit of my research). Their sophistication, like any container, is slim but easy to get wrong and beyond the ability and time contraints that should be assumed of the application programmer. It is a flexible and standard enough concept that a single implementation can be expected to meet a majority of requirements. I think there is the opportunity to create a solid implementation of templated n-tree pointer containers.
The ntree container would be a tree representing an narray of elements with all dimensions being the same and being a power of two. The tree is memory efficient where areas within the volume are not occupied, and so "branches" and "leaves" are not created. The tree is well suited to geometrical operations such as ray picking or plane culling of the volume. An n-tree structure could be used in the place of any sparely populated n dimensional array where memory saving is the objective.
The existing libraries I have found are licensed under GNU licenses.
A ntree container should implement:
get reset overloaded (array style) operators
Optional implementations:
views - a subset object representing an area or volume within the tree for accelerated access to a group of leaves that are positioned near to each other
raycasting plane culling (getting leaves within a set of planes) etc.
Is there interest in such a library?
Many thanks,
Dan
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Karsten wrote on Friday, March 9, 2012 at 21:16:04:
What about other kinds of spatial containers like r-trees or kd-trees?
by the way i have a ready implementation of kd trees (if anyone is interested): http://programmizm.sourceforge.net/blog/2011/a-practical-implementation-of-k... -- Pavel P.S. if you notice a grammar mistake or weird phrasing in my message please point it out
On Mar 9, 2012 6:14 AM, "Dan Walters" <dan683@ <dan683@gmail.com>gmail.com<dan683@gmail.com>> wrote:
Hi all,
I am proposing adding spacial containers for efficiently storing and accessing data of a spacial nature in fixed size trees.
Hi all, This thread is long over, but I've been meaning to write something on it for so long. I wrote a kd-tree library for generic purpose. It may not sound like much, but this library has (i believe) truly unique features : first of all, erasing really works in amortized time (on most libraries out there it does not -- and that's when they even propose erasing), secondly the kd-tree is the only one i know that is capable of self-balancing. These 2 features combined with the fact that the library is very template based, and support any number of dimensions (that can even be determined at runtime) makes it really a general purpose library. It as nearest neighbor iterators, region (or bisection) iterators, and a not so common but useful operation: a mapping iterator which maps all n dimensions into 1 effectively making the iterator behave as a usual multiset iterator, on 1 particular chosen dimension. My future goal is to one day feel satisfied enough by the maturity of the library to submit the library to Boost for integration. Sadly i haven't reached that stage yet. For those who are interested to try it out, you can pull the origin/master branch from the library (the release package is stable but the code is a bit old now) . It had burgeoning (and therefore incomplete) documentation with some obvious mistakes. http://spatial.sourceforge.net/ And I'm still regularly modifying the interface so it is far from being mature. But one day... It will. Cheers, Sylvain
On Thu, Apr 26, 2012 at 6:08 PM, Sylvain Bougerel < sylvain.bougerel.devel@gmail.com> wrote:
On Mar 9, 2012 6:14 AM, "Dan Walters" <dan683@ <dan683@gmail.com>gmail.com<dan683@gmail.com>> wrote:
Hi all,
I am proposing adding spacial containers for efficiently storing and accessing data of a spacial nature in fixed size trees.
Hi all,
This thread is long over, but I've been meaning to write something on it for so long.
I wrote a kd-tree library for generic purpose. It may not sound like much, but this library has (i believe) truly unique features : first of all, erasing really works in amortized time (on most libraries out there it does not -- and that's when they even propose erasing), secondly the kd-tree is the only one i know that is capable of self-balancing.
These 2 features combined with the fact that the library is very template based, and support any number of dimensions (that can even be determined at runtime) makes it really a general purpose library.
It as nearest neighbor iterators, region (or bisection) iterators, and a not so common but useful operation: a mapping iterator which maps all n dimensions into 1 effectively making the iterator behave as a usual multiset iterator, on 1 particular chosen dimension.
My future goal is to one day feel satisfied enough by the maturity of the library to submit the library to Boost for integration. Sadly i haven't reached that stage yet.
For those who are interested to try it out, you can pull the origin/master branch from the library (the release package is stable but the code is a bit old now) . It had burgeoning (and therefore incomplete) documentation with some obvious mistakes.
http://spatial.sourceforge.net/
And I'm still regularly modifying the interface so it is far from being mature. But one day... It will.
I think this could be really exciting to have in Boost. Unfortunately, I don't think I can offer much feedback at the moment, but definitely keep (at least) me posted on noteworthy developments. I'm particularly interested in what your interface will look like. - Jeff
participants (7)
-
Dan Walters -
Dan Walters -
Jeffrey Lee Hellrung, Jr. -
Karsten Ahnert -
Klaim - Joël Lamotte -
pavel -
Sylvain Bougerel