8
\$\begingroup\$

Are there any robust performant libraries for indexing objects?

Objects would have bounds themselves, rather than being represented by points; and an object could therefore be in more than one compartment if the index divides things in fixed sized partitions.

It would need frustum culling and visiting objects hit by a ray as well as neighbourhood searches.

I can find lots of articles showing the math for the component parts, often as algebra rather than simple C, but nothing that puts it all together (apart from perhaps Ogre, although apparently PyOrge doesn't expose the octree). Surely hobby game makers don't all have to make their own spartial indices?

(I am sitting down writing my own sphere-sphere, sphere-ray, ray-aabb, cone-aabb, cone-fustrum, aabb-fustrum and octree implementation; surely there is a better way i.e. someone has already done this and make a nice package?!?!)

(Python or C/C++ w/bindings preferred)

Improve this question
\$\endgroup\$

4 Answers 4

Reset to default
10
\$\begingroup\$

Surely hobby game makers don't all have to make their own octrees?

Unless they are using something larger (like Ogre, or another physics/rendering engine), many do. An octree is a fairly simple structure to implement, and there's a lot of tradeoffs:

  • Is the octree intrusive or not? If it's intrusive you get better cache performance, but larger structures.
  • If it's not intrusive, does it store pointers or some kind of safe handle?
  • Is it stored flat or with child pointers?
  • How type-safe is it? If it uses templates, it'll be a lot safer with minimal runtime overhead, but much harder to bind to Python.
  • Any octree with spatial querying is going to have to include some kind of vector/point/ray type, and anything with frustum culling is going to include a frustum and matrix math routines. Is writing the code to interface that to the dozen matrix/vector classes you've already dragged in from all the other libraries you're using actually less work than just writing the base octree you want?
  • Is it thread-safe?

That being said, there are plenty of octree implementations online. Just don't assume grabbing one of them is going to save you much work, and don't assume there's One True Way to make any data structure other than an array.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Nice insight! I wonder how it is for KD trees, what I've seen from them is they are pretty though to implement (there are a lot of tricky detail to take into account). Maybe someone knows more about this? \$\endgroup\$
    – Nef
    Jan 8, 2011 at 16:32
  • \$\begingroup\$ Are kd-trees actually tougher to implement? I think they're tougher to reason about, especially without drawing pictures, because they divide the geometry in a less intuitive way. But the basic building / querying algorithms aren't really any longer or less explored than the octree. \$\endgroup\$
    – user744
    Jan 8, 2011 at 22:06
  • 2
    \$\begingroup\$ An Octree is actually just a special case KD-tree. With fixed position splitting planes. Implementing KD-trees you will need some way to find your "best" axis splitting offset per node. \$\endgroup\$
    – void
    Mar 21, 2011 at 14:18
2
\$\begingroup\$

To be fair, the linked Python Octree was posted in 2006, so Python-Ogre may very well have exposed the Octree class by now.

However, looking through the Ogre sources, I can see two Octree implementations: one in Plugins/OctreeSceneManager/OgreOctree.h and one in Plugins/OctreeZone/OgreOctreeZoneOctree.h.

If you point me at the one you're needing exposed, I'll put it on my todo list for my own, hand-written Python wrapper (it's available on bitbucket, linked in my profile.)

Anyway, good luck. :D

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ thats a very kind offer; I ahem already wrote my own though. \$\endgroup\$
    – Will
    Mar 21, 2011 at 13:53
1
\$\begingroup\$

I found some code for a Python octree implementation here, by simply googling 'octree python'. ;D

It is not library dependent (though originally written for PyOgre) and is well commented.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ One thing I have found in pure-Python octrees is that the additional overhead for function calls for tree traversal quickly dominates your runtime and makes them worse than simple searches in lists, for any amount of objects you could process in pure-Python anyway. That particular example also looks very unoptimized. \$\endgroup\$
    – user744
    Jan 8, 2011 at 16:22
  • \$\begingroup\$ Whilst that's a nice bit of code to digest if you were to make your own octree, out of the box that octree lacks all the features - ray and fustrum intersection for example - that I cited in the question. In fact, it doesn't even have nearest neighbour search. I wonder what they use that octtree for, if they can put data in but not query it other than by exact point? And it stores points, rather than things with bounds. I list all these shortcomings because this is indicative of all the python octrees I've found on the web; maybe others can find a fuller octree on google? I can't :( \$\endgroup\$
    – Will
    Jan 9, 2011 at 10:13
1
\$\begingroup\$

After unsuccessfully trying a couple of the packages mentioned above I found RTree, which is a wrapper around libspatialindex.

Improve this answer
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged .