Mathias Gaunard wrote:
Wanting to code a simple 3D virtual world, I looked into the recent spatial indexes SOC work, which depends on the proposed geometry library.
Your message has prompted me to finally have a look at Federico's spatial index work.
I don't really get what boost::spatial_index::spatial_index is for. It does nothing but forward everything to the last template parameter.
Instead of writing boost::spatial_index::spatial_index< point_type, value_type, boost::spatial_index::rtree<point_type, value_type>
index(args...);
I might as well write boost::spatial_index::rtree<point_type, value_type> index(args...);
Also, I think the spatial indexes do not provide enough operations. The only things they allow is putting point => value pairs, retrieving the value associated to a point in O(log n) time (I assume, complexity is not documented), and finding all values within a certain box (in O(log n) too?). Many things one typically wants to do with spatial indexes are not possible: - Iterate all (points, value) pairs in the index - Find the element closest (or k-closest) to some point in space or other element. - Find all elements within a certain range of some point in space or other element - Find the elements that intersect with a given object (ray tracing, for example, searches for an element that intersects with a ray and that is the closest to its source) - Consider only a part of the indexed space (e.g. an area delimited by a range/sphere or box) - Being able to index arbitrary objects and not just points - Traverse the spatial index as a tree
I certainly agree that all or most of those operations should be provided. My own observations: - insert should take a std::pair for consistency with the std::associative_containers. - Iteration over a (rectangular) range should involve iterators, not returning a std::deque. - The current find(box) results return only the value_type, not the point. - When I use integer coordinates I get lots of warnings because of /2.0 in the code. - Defaults should be provided (or, values should be chosen at runtime) for the "fiddle factors". - Performance is poor; worse than 10x slower than the code that I'm currently using. - Rectangle iteration for rtrees is much slower than that; I suspect there's either a complexity problem or a bug. - There is no need to use shared_ptr to point to child nodes; this is probably a major reason for the performance problem. - In the quadtree, the bounding boxes of parent and child nodes have common edges; this should be exploited to reduce the size of the node. I understand that this is "only" a GSoC project, but it's sad that Federico didn't keep in touch with this list while he was working on this code. We could have quickly pointed out problems like the above long before the "final report" stage. (I see no messages here between "Congratulations to the Successful Summer of CodeStudents!" on 20080422 and "Final report of GSOC project 'Spatial Indexes'" on 20080911.) I'm curious to know if Federico's GSoC mentor had reviewed at least the interface to the proposed class. Regards, Phil.