我该将形状存储在八叉树的哪里？

Question

一些关于设计决策的背景... 我已经开发了一个可以存储点的八叉树结构。我选择基于特定基础体素大小限制“代数”递归。只有在添加点到该节点时，才会创建子节点。这 不是 一个动态图形应用程序 - 这个八叉树和其中的对象都是静态的，因此预处理以提高性能不是一个问题。

现在，我想在我的八叉树中添加“形状” - 具体来说，由三角形组成的表面网格。这些三角形的顶点不对应于存储在八叉树中的点。如何在八叉树中存储这些形状？我看到两个选项...

灰色节点是“空的”，因为它们没有形状。在替代方案1中，形状存储在它们相交的每个节点中 - 即，节点1a包含shape1，4c和4d共享shape2。在替代方案2中，形状仅存储在它们相交的最小节点中 - 即，节点1a包含shape1，节点4包含shape2。

我看到的大多数八叉树帖子都假定Alt1，但他们从未解释过为什么。Alt2对我来说更有意义，并且只会为驻留在节点边界上的那些形状创建额外的工作。为什么Alt1更可取？

编辑：为了澄清，我的实现语言是C ++，因此我更喜欢该语言的示例实现，但该问题与语言无关。如果标签使用不正确，请原谅。

编辑2：虽然与形状存储的问题无直接关系，但this link有一个关于八叉树遍历的良好讨论，这是问题背后的原因。我认为这可能有助于任何对此问题感兴趣的人。

---

更新：四年后，Alt2的实现变得更加容易，但是由于存储在更高的八叉树层级上的大三角形每次遍历八叉树时都会被测试，因此非常缓慢 - 在我的情况下，这意味着数百到数千个不必要的测试。最终我改进了代码，使用了R*树变体，这很容易实现，并且速度显著提高。

- Phlucious

---

+1 我觉得这个问题很有趣，而且表述清晰（但我完全不知道答案，提前说一下）。假设C++标签的原因是您希望提出可行的寻址方案建议，那么您可能需要在问题中澄清这一点，尽管我猜想有人可能会用Forth回答，并且您可能会轻松地剖析它。按照现有的写法，它可以独立于语言标签存在。 - WhozCraig

Alt1的原因是它具有隐含的精度。八叉树AABB测试比每个三角形测试执行得更快。因此，具有同一网格的多个注册的细粒度八叉树将允许更快的查询。就复杂性而言，相当于log n与n的比较。但另一方面，它比Alt2更占用内存。此外，对于非静态几何体，更新比Alt2更昂贵。总体而言，您选择哪种细分取决于您处理的场景类型。对象数量和可变性起着相等的作用（以及内存）。 - meandbug

@WhozCraig：包含C++标志只是因为这是我的实现语言，任何示例代码都最好使用该语言理解。你说得对，问题本身与语言无关。 - Phlucious

@Phlucious，为什么不考虑使用K-D-Tree呢？对于这样的应用程序来说，它似乎更加优化。http://en.wikipedia.org/wiki/K-d_tree - meandbug

@user3405291 我实现了一个稀疏八叉树，只有在需要时才实例化节点，因此我没有注意到两者之间内存使用的显着变化。我的数据也是静态的，因此我可以通过一种动态环境无法维护的方式对R * -tree进行空间优化。我无法评论一般情况。 - Phlucious

Answer 1

ALT1是正确的。考虑到你想限制节点中对象（三角形）的最大数量，你需要对包含许多三角形的节点进行细分。这不可避免地导致单个三角形存在于多个节点中，除非你想将三角形细分以完美适配八叉树节点（这取决于你的应用程序，我通常不建议这样做，例如对于光线追踪通常不这样做）。

以反例为例，想象一下ALT2包含一个详细的斯坦福兔子模型，站在一个大三角形上。大三角形会阻止根节点被划分成子节点，因此你的八叉树就像没有八叉树一样。

否则，你将不得不保留大三角形在根节点中，并将其细分为包含其余较小兔子三角形的子节点中。将三角形放置在叶节点和其他节点中可能会使八叉树遍历变得复杂（但这也取决于你的应用程序）。如果我们坚持光线追踪场景，在找到光线和三角形的最近交点时，你必须检查一个节点和所有子节点，以找到最近的交点，并且你必须跟踪光线到下一个节点移动，在所有树级别上同时进行。另一方面，如果你的几何形状仅存在于叶节点中，你可以按照光线访问它们的顺序测试叶节点中的三角形（同时跟踪已经测试过的三角形以避免重复测试）。

- the swine

---

感谢您的有趣回复。在您的情况下，所有叶节点是否处于相同的深度级别？如果是这样，那么我认为光线跟踪算法无论如何都需要遍历每个级别，以便跳过树中空的高级节点（及其子节点）。如果不是，那么无论如何您都必须遍历每个级别，对吗？ - Phlucious

@Phlucious 它们可以处于不同的层级，否则八叉树将退化为常规网格，并且可以使用3DDDA光栅化来遍历节点。至于访问更高层次的节点，这并不完全正确，您始终知道射线从节点的哪一侧退出，并且可以准备指向共享给定侧面的相邻节点的指针（初始化指针一次，多次使用）。然后，仅使用八叉树结构查找射线起点，然后所有遍历都是简单的跳转到相邻节点。 - the swine

有道理。在多个级别存储叶节点时，当顶点相距几个节点时（例如，在您的大三角形兔子示例中），如何确定形状相交的叶节点？我不明白一个大节点如何存储指向其“西”邻居的指针，当存在两个较小的“西”节点时。 - Phlucious

@Phlucious 通过分离轴定理（SAT），可以很容易地实现节点-三角形相交。对于轴对齐的节点，它易于实现且速度较快。至于“西”指针，它要么存储指向同一级别的“西”节点的指针，并在经过该节点后找到下一个叶节点，要么备选地存储指针的“位图”，映射到其墙上，并基于光线射出的“像素”来继续遍历。 - the swine

Answer 2

这更多是关于四叉树的参考，我更熟悉它们，但它们是八叉树的二维等效物;因此可能适用。

插入的一般方法：四叉树的每个内部节点都有一个容量，即四叉树象限可以容纳的最大“对象”数。如果达到容量，您将进行细分，然后将所有“对象”插入其相应的子象限。您还将达到一个点，在该点上，一个或多个“对象”跨越多个子象限;在插入/查询时要小心这种情况。通常，节点容量被选择为支持更快的插入或查询。

因此，考虑到这一点，我认为您呈现的ALT2图像没有任何问题。但是，我假设您总是看到ALT1图像的原因是在未占用的单元格中插入时的默认方法是进行细分，然后插入。

- Justin