用于视锥体剔除的松散八叉树 - 需要一些建议
我正在我的引擎中实现动态对象的视锥体剔除，并且一直在尽可能地阅读有关“松散八叉树”的内容。不幸的是，大多数消息来源都很模糊，实际上只是很多人的帖子说他们有多好，并且他们给出了 O(1) 插入和删除，但没有解释其背后的任何逻辑。
我理解的主要原则是八分圆被视为大于实际大小，并且松散因子最多可达 2。这意味着可以根据对象的大小将对象插入到单个节点中。问题是很多文章不使用 2 的“k 因子”（可能是为了获得更紧密的配合），因此失去了快速插入/删除的能力；相反，它们维护邻接结构，以便您可以遍历给定深度的所有节点并使用每个节点测试对象的中心。
我只需要一个粗略的剔除测试，我想要 O(1) 插入时间，并制定了计算对象应插入的深度（级别）的公式。但是，我找不到任何讨论根据对象的大小和位置计算精确节点的公式的文章。
我是否完全误解了该算法？我是否在寻找不可能的东西？如果有人能给我指出任何好的论文或文章（我读过 http://tulrich.com/geekstuff/) 那么那就太好了。
PS 可能值得一提的是，我正在使用存储在一维数组中的线性八叉树
感谢您的帮助
I am implementing frustum culling for dynamic objects into my engine and have been reading as mush as I can about "loose octrees". Unfortunately most sources are quite vague and really it's just lots of posts of people saying how good they are and that they gave O(1) insertion and deletion but without explaining any of the logic behind it.
I understand the main principles that the octants are treated as being larger than they are and that the loose factor can go up to 2. This means that an object can be inserted into a single node based on it's size. The trouble is that alot of the articles don't use a "k-factor" of 2 (probably to get a tighter fit) and therefore lose the fast insertion/deletion; instead they maintain an adjacency structure so you can traverse all nodes at a given depth and test the centre of the object with each node.
I only need a rough culling test and I'd like to have the O(1) insertion time and have worked out the formula for calculating the depth (level) that an object should be inserted. However I cannot find any articles that discuss a formula to calculate an exact node from the size and position of an object.
Have I totally misunderstood the algorithm and am I looking for something that isn't possible? If anyone can point me to any good papers or articles (I've read http://tulrich.com/geekstuff/) then that would be great.
PS It may be worth mentioning that I am using a linear octree stored in a 1D array
Thanks for any help
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我在gamedev论坛上得到了答案。我正在寻找的方程实际上非常简单
int NodeIndex = height*(bb.centre.x / sceneBB.width);
I got the answer on the gamedev forum. The equation I was looking for was actually really simple
int NodeIndex = depth*(bb.centre.x / sceneBB.width);
您不是指八叉树中的多维搜索吗？空间填充曲线怎么样？
You didn't mean a multidimensional search in an octree? What about a space-filling-curve?