-------------------------------------------------- From: "Mathias Gaunard" <mathias.gaunard@ens-lyon.org> Sent: Tuesday, October 07, 2008 5:52 PM To: <boost@lists.boost.org> Subject: [boost] Geometry and spatial indexes, my opinion
Hi,
Wanting to code a simple 3D virtual world, I looked into the recent spatial indexes SOC work, which depends on the proposed geometry library.
I have to admit I was fairly disappointed. So I'm going to put some critics, some quite harsh maybe, along with some ramblings about what I would have liked to have. Note that I am no geometry or space indexing expert, so what I say may be perfectly silly.
For starters, I think those libraries should be dimension agnostic and generic. Geometry not only has a strong 2D bias, but the documentation also says geometry::box only works with point_xy (and point_ll). Since it is used everywhere in spatial index, that means it's unusable on 3D.
Hi Mathias, I just wanted to say something here about dimensional agnosticism. I don't think this is necessarily the way to go. There are a couple of reasons that I say this. The more trivial point is that higher than 3D geometry isn't likely to be supported and isn't of much practical use anyway. The second point is on the basis of coordinate frameworks. While I agree that any library shouldn't necessarily be limited to 2D, I don't think that you should lose the notions of what type of coordinate frame you are working in. So while you may be able to have 0, 1, or 2 to describe agnostically the dimension in the framework you want, the descriptions of what those dimensions are is lost. For example, you may have an algorithm which is designed to work in Cartesian coordinates in 2D (or 3D). You may have another algorithm which requires points in Polar (Spherical) coordinates. Another might want cylindrical coordinates to be optimal. Then there are algorithms which require translation of points into parametric coordinates to perform some logic optimally. If you have points which are agnostic to dimension, how can you distinguish 0,1,2 from x,y,z or r, theta, phi? The constraints imposed by these concepts are rather that when given a point of some dimensionality you need to be able to determine the type of coordinate frame that the point is describing. I've been working on a generative geometry library which includes support for these distinctions via conceptually enforced interfaces and traits.
The geometry documentation doesn't clearly state what a geometry::box is. Is it (assuming 2D) any rectangle or only axis-aligned rectangles? In case it is just any rectangle, it mind be interesting to introduce a new type for axis-aligned ones, which can always be defined from two points whatever the dimension (well, at least it seems enough for 3D, I'm not good at projecting in other dimensions to see if that'd work). I suppose the spatial index interface expects axis-aligned boxes, so it's fairly important to clarify what we're talking about.
Apart from that, there is also lots of point_xy-dependent code in spatial indexes. Also the quadtree implementation isn't dimension agnostic in particular (it should have 2^n children nodes, and not 4). I don't really get why it uses shared_ptr everywhere either (is it supposed to support COW or something?)
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 believe there is no need to clutter the interface with a lot of functions, most algorithms can be implemented generically as free functions. Giving a read-only tree interface to all spatial indexes ought to be enough to implement all algorithms. A spatial index, after all (correct me if I'm wrong), is nothing else but a tree that partitions space, where every node defines a partition of space that includes all of its children (which might overlap or not). Subtrees should be full-fledged spatial indexes (so that I can perform a search in a subtree), albeit read-only. Apart from that they should allow insertion and removal of object => value pairs.
Quadtrees and r-trees should be fairly easy to work with: they both partition space into axis-aligned boxes (which are even cubes in quadtrees).
As for allowing all kinds of objects to be stored instead of just points, that should be possible by using generic distance and intersection functions. The real difference is that the same object could eventually be in multiple places in the tree, because it spans over multiple space partitions. Whenever you put an object in the tree or split a partition, however, it would be necessary to calculate in which partitions to put the object, whereas with points you only have to find the one partition.
Of course, some cases can be specialized and optimized, like axis-aligned boxes in a R-tree, which can directly be used as partitions and thus never span across multiple ones. I find it weird having a different interface for R-trees and Quadtrees. Indeed, one can only put points in a quadtree while in a r-tree you can put boxes as well. A generic approach allowing to put any object with boxes specialized seems like a better approach to me.
About geometry, I think there should be more basic objects. While it is true polygons and multipolygons (polyhedrons) are enough to represent everything in 3D space, having rays, segments, triangles, quads, circles, spheres, squares, rectangles, cubes, cuboids (boxes), planes, half-planes and more, with ability to compute all intersections and distances, would be the most practical thing for 3D development. I do not know how to organize this in a really dimension-agnostic manner, however.
This certainly makes sense, though I think starting with points, segments and polylines/polygons give sufficient primitives to do most basic geometry operations. These could of course be specialized into classes as you have described.
In a nutshell, I think the spatial indexes design and how geometry can help it ought to be discussed.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost