c++ - 我在哪里存储八叉树中的形状？

Question

到目前为止，关于设计决策的一些背景知识......我开发了一个可以存储点的八叉树结构。我选择根据某个基本体素大小来限制“世代”的递归。仅当将点添加到该节点时才会创建子节点。这不是一个动态的图形应用程序——这个八叉树和其中的对象是静态的，因此无需担心提高性能的预处理。

现在，我想在我的八叉树中添加“形状”——特别是由三角形组成的表面网格。这些三角形的顶点与八叉树中存储的点不对应。如何将这些形状存储在八叉树中？我看到两个选项...

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

我见过的大多数关于八叉树的帖子都假设 Alt1，但他们从未解释过原因。Alt2 对我来说更有意义，只会为那些位于节点边界上的形状创建额外的工作。为什么 Alt1 更可取？

编辑：为了澄清，我使用的实现语言是 C++，所以我更喜欢该语言的示例实现，但问题与语言无关。对不起，如果这是不正确的标签使用。

Edit2：虽然与形状存储问题没有直接关系，但此链接对问题背后的八叉树遍历进行了很好的讨论。我认为它可能会帮助任何有兴趣研究这个问题的人。

---

更新：四年后，Alt2 最终变得更容易实现，但速度很慢，因为存储在更高八叉树级别的大三角形在每次遍历八叉树时都要进行测试——在我的例子中，这意味着成百上千次不必要的测试。我最终修改了我的代码以使用R*-Tree 变体，这很容易实现并且速度大大加快。

Answer 1

ALT1 是正确的。鉴于您想限制节点中对象（三角形）的最大数量，您需要细分将包含许多三角形的节点。这不可避免地会导致在多个节点中有一个三角形，除非您想细分三角形以使它们完全适合八叉树节点（这取决于您的应用程序，我通常不建议这样做，例如，对于光线跟踪，通常确实不这样做） .

作为一个反例，想象一下 ALT2 包含一个斯坦福兔子的详细模型，它站在一个大三角形上。大三角形会阻止将根节点细分为子节点，因此您的八叉树将与没有八叉树一样好。

或者，您必须将大三角形保留在根节点中，并将其细分为包含其余较小兔子三角形的子节点。不仅在叶节点中而且在其他节点中都有三角形可能会使八叉树遍历复杂化（但这也取决于您的应用程序）。如果我们坚持使用光线追踪场景，要找到光线和三角形最近的交点，您必须检查一个节点和所有子节点才能找到最近的交点，并且您必须跟踪光线到下一个节点，在所有树级别上同时地。另一方面，如果您的几何体仅在叶子中，您可以按照光线访问叶子的顺序测试叶子中的三角形（同时跟踪已经测试过的三角形以避免两次测试相同的三角形）。

Answer 2

这更多地参考了我更熟悉的四叉树，但它们是八叉树的二维等价物；所以它可能适用。

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

因此，考虑到这一点，我认为您展示的 ALT2 图像没有任何问题。但是我对为什么你总是看到 ALT1 图像的假设是插入未占用单元格时的默认方法是细分然后插入。

Answer 3

我有一个简单的 C++ 八叉树实现。该实现将节点细分为八个子节点，就好像该特定节点中存在多个点一样。现在我想对表面网格数据使用相同的八叉树，我的意思是我想在八叉树数据结构中存储完整的几何信息。除此之外，我还有从 .stl 文件中提取的三角形信息。

我的问题与几年前 Phlucious 提出的问题几乎相似，但我不明白对他问题的完整讨论。