八叉树邻居搜索

Question

我有一个八叉树，用于存储基于体素的流体。当我模拟流体时，我需要访问当前节点周围的叶子节点，如何实现这样的搜索？

您可以假设该节点存储了指向其父节点的指针。(也许需要其他数据?)

- akaltar

Answer 1

假设每个八叉树节点还保存其在八叉树中的三维索引（和深度）[1]。

1. 为查询节点的相邻节点生成三维索引（仅在每个维度上递增/递减查询节点的三维索引即可）。
2. 对于每个潜在的相邻节点，从根开始遍历八叉树，使用生成的三维索引选择在每个具有子节点的节点处应采取哪条路径。

如果当前节点仅具有更高深度的相邻节点（八叉树不完全/完美），则2中执行的遍历将停止在八叉树中最大可到达深度，该深度小于或等于查询节点的深度。

如果节点保存其父节点指针，则可以通过首先找到当前节点及其每个相邻节点的最近公共祖先（这是通过查找它们的三维索引中最长的公共二进制前缀来完成的），并从该祖先节点开始遍历以仅到达相邻节点来改善2。

[1]：三维索引只是八叉树节点的x/y/z坐标。例如，根节点的八个子节点具有带有1个二进制数字的3D索引（这些节点位于八叉树中的深度1处）：0/0/0、1/0/0、0/1/0、1/1/0... 根节点的64个孙节点具有带有2个二进制数字的3D索引（这些节点位于八叉树中的深度2处）：00/00/00、01/00/00、10/00/00、11/00/00、00/01/00、01/00/00...

- user3146587