34

I've been searching high and low (mostly on google) for a fast, efficient, templated (ie. with STL-like properties) octree implementation, without success. I want to use this in the context of a 3D scene graph.

Does such a thing exist, or do people generally roll their own? I'm hoping my friends at stackoverflow will know where to find one.

3
  • Generally I feel like, if you want the fastest solution, you have to roll your own because the use cases vary wildly, from octrees storing points, octrees storing elements with sizes, loose octrees that more efficiently store elements with sizes, SVOs for voxel data, octrees that use SPFP, octrees that use DPFP, octrees that use integers to exploit more bitwise operations, etc. etc. etc. The list goes on and on and if you found a single generic octree that satisfied all possible criteria very efficiently, it would probably be horrific to use.. like a policy class template...
    – user4842163
    Jan 23, 2018 at 12:17
  • ... with 16 different policies to specify as template parameters, e.g., at which point just using such a clunky thing might take more time than rolling your own or finding a simple but efficient example of something more narrowly applicable which is closer to your needs and tweaking it as necessary. Generic data structures tend to work well for simpler things like std::vector abstracting the idea of a variable-sized dynamic array with little/no performance penalty (only reason I can think of anyone wanting something else [...]
    – user4842163
    Jan 23, 2018 at 12:18
  • [...] is if they want a different reallocation/reserving policy, like being able to control how much memory the vector reallocates when it's full, or using smaller than 64-bit integers to store size and capacity) -- very fussy stuff. But as you get towards more complex structures like spatial indexes, and especially data structures that tend to come in a wide variety of shapes and sizes based on the domain in which they're used, it becomes pretty unwieldy to try to search for general-purpose thing that's perfect, since at that point "general-purpose" and "made-for-my-purpose" are incompatible.
    – user4842163
    Jan 23, 2018 at 12:22

3 Answers 3

15
1
  • 24
    GPL code isn't really meant to be used by others. At least not in the real world. ;) Jun 17, 2015 at 15:45
10

Also recently released: http://www.openvdb.org/

A volume hierarchy format by Dreamworks.

0
8

Check this one out: http://svn.pointclouds.org/pcl/trunk/octree/

Updated link: https://github.com/PointCloudLibrary/pcl/tree/master/octree

4
  • Thanks. Interesting, but seems to be undocumented.
    – Robinson
    May 11, 2011 at 12:21
  • My mistake. Found the documentation: docs.pointclouds.org/group__octree.html.
    – Robinson
    May 11, 2011 at 12:27
  • Also, there's a test/test_octree.cpp to look at for usage.
    – Lou Franco
    May 11, 2011 at 12:52
  • 3
    Some idea on how to use it without including and compiling the whole point cloud library?
    – linello
    May 2, 2012 at 10:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.