python - What library for octrees or kd-trees?

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)

Answer

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.