八叉树邻居搜索 [英] Octree neighbour search

问题描述

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

您可以假设节点存储指向其父节点的指针（也许需要其他数据？）

解决方案

假设每个八叉树节点也在八叉树（及其深度）中保存其3D索引[1]。

1. 为查询节点的邻居节点生成3D索引（简单地增加/减少每个维度中查询节点的3D索引）。


2. 对于每个潜在的邻居，遍历从根的八叉树，使用生成的3D索引来选择在每个节点带有子节点的路径。

如果当前节点只有较高的深度（八叉树不完整/完美）的邻居，2中的遍历将停留在小于或等于查询节点深度的八叉树中的最大可达深度。

如果节点持有指向父节点的指针，则可以通过首先找到当前节点的最低共同祖先来进行改进，它的每个邻居（这是通过在其3D索引中找到最长的公共二进制前缀来完成的），并且仅从这个祖先节点开始遍历到达邻居。

[ 1]：3D索引只是八叉树节点的x / y / z坐标。例如，根的八个子元素具有1个二进制数字的三维索引（这些节点位于八叉树位置的深度1）：0/0/0，1/0/0，0/1/0，1/1 / 0，...根的六十四个大孩子有三维索引，具有2个二进制数字（这些节点位于八叉树的深度2）：00/00/00，01/00/00，10 / 00/00，11/00/00，00/01/00，01/00/00 ...

I have an octree, that stores a voxel-based fluid. When I simulate the fluid, I need to access the leaves around the current node, how can I implement such a search?

You can assume the node stores a pointer to its parent node.(Perhaps other data is needed?)

解决方案

Assuming each octree node also holds its 3D index[1] in the octree (and its depth).

1. Generate the 3D indices for the neighbor nodes of the query node (simply increment/decrement the 3D index of the query node in each dimension).
2. For each potential neighbor, traverse the octree from the root, using the generated 3D indices to choose which path to take at each node with children.

In case the current node has neighbors at higher depth only (the octree is not complete/perfect), the traversal done in 2. will stop at the maximum reachable depth in the octree that is less or equal than the depth of the query node.

If the nodes hold a pointer to their parents, 2. can be improved by first finding the lowest common ancestor of the current node and each of its neighbors (this is done by finding the longest common binary prefix in their 3D indices) and starting the traversal to reach the neighbor only from this ancestor node.

[1]: The 3D index is simply the x/y/z coordinates of the node in the octree. For instance, the eight children of the root have 3D indices with 1 binary digit (these node are at located depth 1 in the octree): 0/0/0, 1/0/0, 0/1/0, 1/1/0, ... The sixty-four grand-children of the root have 3D indices with 2 binary digits (these nodes are located at depth 2 in the octree): 00/00/00, 01/00/00, 10/00/00, 11/00/00, 00/01/00, 01/00/00...

这篇关于八叉树邻居搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！