快速、模板化的 C++ 八叉树实现

Question

我一直在（主要是通过Google）搜索快速、高效、带有STL类似特性的模板化八叉树实现，但一直没有找到。我想在3D场景图的上下文中使用它。

这样的东西是否存在，或者人们通常自己开发呢？我希望在stackoverflow上的朋友们能知道哪里可以找到。

- Robinson

---

一般来说，如果你想要最快的解决方案，你必须自己动手实现，因为使用情况千差万别，从存储点的八叉树、存储大小元素的八叉树、更高效地存储大小元素的松散八叉树、用于体素数据的SVO、使用SPFP的八叉树、使用DPFP的八叉树、使用整数以利用更多位运算的八叉树等等。列表可以继续下去，如果你找到了一个单一的通用八叉树，它能够非常高效地满足所有可能的标准，那么它可能会非常难以使用，就像一个策略类模板一样。 - user4842163

使用16个不同的策略作为模板参数进行指定，例如，在哪个点上仅使用这样笨重的东西可能比自己编写或找到一个更窄适用范围但更接近您需求的简单而有效的示例，并根据需要进行调整。 通用数据结构往往对于像std::vector这样的简单事物很有效，将可变大小的动态数组的想法抽象出来，几乎没有性能损失（我想到的唯一原因是有人想要其他东西[...] - user4842163

如果他们想要不同的重新分配/保留策略，比如能够控制向量在满时重新分配多少内存，或者使用小于64位整数来存储大小和容量等，这些都是非常琐碎的事情。但是当你接近更复杂的结构，比如空间索引，特别是数据结构，往往基于它们所用的领域而呈现出各种各样的形状和大小时，试图寻找完美的通用工具就变得相当笨拙了，因为此时“通用”和“为我的目的而制作”的概念是不兼容的。 - user4842163

Answer 1

• http://nomis80.org/code/octree.html

  这是我最喜欢的。它是GPL许可证并有自己的主页，因此适合他人使用。它有Doxygen文档，并且作者会回答问题。

• http://www.flipcode.com/archives/Octree_Implementation.shtml

  这个实现没有模板。它在代码中有比我看到的其他任何实现都多的注释，所以如果你试图找出八叉树如何工作，这可能更有用。

- Janus Troelsen

---

GPL代码并不是真的为他人使用而设计的，至少在现实世界中不是这样。 ;) - Brandon Kohn

Answer 2

最近还发布了一个由梦工厂开发的体积层次格式：http://www.openvdb.org/

- Jeroen Baert

---

哇！非常感谢您的提示。 - mojovski

Answer 3

请检查这个链接：http://svn.pointclouds.org/pcl/trunk/octree/

更新后的链接：https://github.com/PointCloudLibrary/pcl/tree/master/octree

- Lou Franco

---

谢谢。很有趣，但似乎没有文档记录。 - Robinson

我的错误。找到了文档：http://docs.pointclouds.org/group__octree.html。 - Robinson

此外，还有一个test/test_octree.cpp文件可供使用。 - Lou Franco

如何在不包括和编译整个点云库的情况下使用它？ - linello