graphics - 用于视锥体剔除的松散八叉树 - 需要一些建议

Question

我正在我的引擎中实现动态对象的视锥体剔除，并且一直在尽可能地阅读有关“松散八叉树”的内容。不幸的是，大多数消息来源都很模糊，实际上只是很多人的帖子说他们有多好，并且他们给出了 O(1) 插入和删除，但没有解释其背后的任何逻辑。

我理解的主要原则是八分圆被视为大于实际大小，并且松散因子最多可达 2。这意味着可以根据对象的大小将对象插入到单个节点中。问题是很多文章不使用 2 的“k 因子”(可能是为了获得更紧密的配合)，因此失去了快速插入/删除的能力；相反，它们维护邻接结构，以便您可以遍历给定深度的所有节点并使用每个节点测试对象的中心。

我只需要一个粗略的剔除测试，我想要 O(1) 的插入时间，并且已经制定了计算对象应插入的深度(级别)的公式。但是，我找不到任何讨论根据对象的大小和位置计算精确节点的公式的文章。

我是否完全误解了算法，我是否在寻找一些不可能的东西？如果有人能给我指出任何好的论文或文章(我读过 http://tulrich.com/geekstuff/ )，那就太好了。

PS 可能值得一提的是，我使用的是存储在一维数组中的线性八叉树

感谢您的帮助

Answer 1

我在 gamedev 论坛上得到了答案。我正在寻找的方程实际上非常简单

int NodeIndex = 深度*(bb.centre.x/sceneBB.width);