3

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

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

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

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

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

谢谢你的帮助

4

2 回答 2

2

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

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

于 2011-03-18T15:17:42.560 回答
1

您不是说在八叉树中进行多维搜索吗?那么空间填充曲线呢?

于 2011-03-14T12:11:45.030 回答