c++ - 如何向下遍历四叉树以获得最底层的节点(3D、C++、DX11)

Question

我正在为我的 3d 地形创建一个四叉树，因为我只需要担心 Z 轴和 X 轴，我在思考如何在创建树后实际向下移动时遇到了一些麻烦。

我已经创建了树，它们作为 QuadNode 对象存储在我的 QuadTree 对象中。每个 QuadNode 代表四叉树的一个“四边形”。它获取地形并确定是否需要 segmentation 为新节点，直到找到最底层的节点并且每个节点有足够数量的顶点。

我在每个节点对象中都存储了一个顶点/索引缓冲区，但它们只有在到达最底部的节点时才会被填充。所以我试图获取的缓冲区(以获取要绘制的缓冲区)就在树的底部。

现在我可以用一棵从根开始只有 4 个节点的基本树来相当简单地做到这一点，但是随着树变得越来越大，我感到困惑。这是一个演示图像

我存储

• 四叉树中有多少层(可能有助于搜索，比如遍历到第 6 层)
  • 节点总数

缓冲区存储在最底部的节点中。有没有人有示例函数或伪代码，说明我如何创建一个函数来遍历给定特定级别 的树，它会为我提供该级别的节点？或者有更好的方法吗？

Answer 1

虽然这不是我要找的东西，但我发现这是你遍历底部节点的方式，而且似乎很适合我想做的事情

How to iterating a Quad/Oct tree

void drawQuadtreeNodes()
{
    drawNode(quadtree->getRoot());
}

void drawNode(QuadNode * node)
{
    if (node->hasNodes) {
        drawNode(node->nodes[0]);
        drawNode(node->nodes[1]);
        drawNode(node->nodes[2]);
        drawNode(node->nodes[3]);
    }
    else {
        //bottom node
    }
}