我在哪里将形状存储在八叉树中？
Phl*_*ous 12 c++ spatial-index data-structures octree
到目前为止,关于设计决策的一些背景......我开发了一种可以存储点的八叉树结构.我选择基于某个基本体素大小来限制"世代"的递归.只有在将点添加到该节点时才会创建子节点.这不是动态图形应用程序 - 这个八叉树及其中的对象是静态的,因此不需要考虑提高性能的预处理.
现在,我想在我的八叉树中添加"形状" - 特别是由三角形组成的表面网格.这些三角形的顶点不对应于存储在八叉树中的点.如何在八叉树中存储这些形状？我看到两个选择......
灰色节点是"空的",因为它们没有形状.在备选方案1中,形状存储在它们相交的每个节点中 - 即,节点1a包含shape1和4c和4d共享shape2.在备选方案2中,形状仅存储在它们相交的最小节点中 - 即,节点1a包含shape1而节点4包含shape2.
我见过的八角树上的大多数帖子都假设为Alt1,但他们从未解释过为什么.Alt2对我来说更有意义,只会为那些驻留在节点边界上的形状创建额外的工作.为什么Alt1更受欢迎？
编辑:为了澄清,我使用的实现语言是C++,所以我更喜欢该语言的示例实现,但问题是与语言无关.对不起,如果标签使用不正确.
编辑2:虽然与形状存储问题没有直接关系,但这个链接对问题背后的八叉树遍历有很好的讨论.我认为这可能有助于任何有兴趣研究这个问题的人.
更新:四年后,Alt2最终变得更容易实现,但速度非常慢,因为在八叉树的每次遍历中都会测试存储在较高八叉树级别的大三角形 - 在我的情况下,这意味着需要进行数百到数千次不必要的测试.我最后修改了我的代码以使用R*-Tree变体,这很容易实现并且速度更快.
ALT1 是正确的。鉴于您要限制节点中对象（三角形）的最大数量，您需要细分将包含许多三角形的节点。这不可避免地导致在多个节点中有一个三角形，除非您想细分三角形以使它们完美地适合八叉树节点（这取决于您的应用程序，我通常不建议这样做，例如对于光线跟踪，它确实通常不这样做） .
作为反例，想象一下 ALT2 包含一个斯坦福兔子的详细模型，它站在一个大三角形上。大三角形会阻止将根节点细分为子节点，因此您的八叉树将与没有八叉树一样好。
或者，您必须将大三角形保留在根节点中，并将其细分为包含其余较小兔子三角形的子节点。不仅在叶节点中而且在其他节点中都有三角形可能会使八叉树遍历复杂化（但这也取决于您的应用程序）。如果我们坚持使用光线追踪场景，要找到光线和三角形的最近交点，您必须检查一个节点和所有子节点才能找到最近的交点，并且您必须跟踪光线到三角形的移动下一个节点，在所有树级别上同时。另一方面，如果您的几何图形仅在叶子中，您可以按照光线访问它们的顺序测试叶子中的三角形（同时跟踪已经测试过的三角形以避免对同一三角形进行两次测试）。