我有一个八叉树，它存储基于体素的流体。当我模拟流体时，我需要访问当前节点周围的叶子，我该如何实现这样的搜索？
您可以假设节点存储指向其父节点的指针。（也许需要其他数据？）
问问题
2507 次
1 回答
7
假设每个八叉树节点还在八叉树（及其深度）中保存其 3D 索引 [1]。
- 为查询节点的邻居节点生成 3D 索引（只需在每个维度中增加/减少查询节点的 3D 索引）。
- 对于每个潜在的邻居，从根开始遍历八叉树，使用生成的 3D 索引来选择在每个具有子节点的节点处采用哪条路径。
如果当前节点只有在更高深度的邻居（八叉树不完整/完美），则在 2. 中完成的遍历将在八叉树中小于或等于查询节点深度的最大可达深度处停止。
如果节点持有指向其父节点的指针，则 2. 可以通过首先找到当前节点及其每个邻居的最低公共祖先（这是通过在其 3D 索引中找到最长公共二进制前缀来完成）并开始遍历仅从该祖先节点到达邻居。
[1]：3D索引就是八叉树中节点的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...
于 2014-02-02T17:16:03.127 回答