Как пройти по дереву четырехугольников, чтобы получить узлы самого нижнего уровня (3D, C++, DX11)

Я создаю четырехугольное дерево для своего трехмерного ландшафта, так как мне нужно беспокоиться только об осях Z и X, и у меня возникают проблемы с тем, как на самом деле перемещаться вниз после создания дерева.

Я создал дерево, и они хранятся в моем объекте QuadTree как объекты QuadNode. Каждый QuadNode представляет собой Quad дерева квадрантов. Он берет ландшафт и выясняет, нужно ли его подразделять на новые узлы, пока не найдет узлы самого нижнего уровня и не будет достаточного количества вершин на узел.

Я сохранил буфер вершин/индексов в каждом объекте узла, но они заполняются только после достижения самых нижних узлов. Таким образом, буферы, которые я пытаюсь получить (чтобы заставить буферы рисовать), находятся прямо в нижней части дерева.

Теперь я могу сделать это довольно просто с базовым деревом, которое имеет всего 4 узла от корня, но по мере того, как дерево становится больше, я запутался. Вот изображение для демонстрации

введите здесь описание изображения

я храню

  • How many levels are in the quad tree (to perhaps help with searching, like traverse to level 6)
    • The total node count

Буферы хранятся в самых нижних узлах. Есть ли у кого-нибудь пример функции или псевдокода, как я могу создать функцию для обхода дерева с учетом определенного уровня, и она даст мне узлы для этого уровня? Или есть лучший подход?


c++ directx-11 terrain quadtree
person kbz    schedule 06.09.2017    source источник
comment
Количество узлов на уровне будет 4^n + 4^(n-1) + 4^(n-2) и так далее до n == 0. Итак, на уровне 2 у вас будет 4^2 + 4^1 + 4^0 = 21. На уровне 3 у вас будет 21 + 4^3 = 85. На уровне 4 у вас будет 85 + 4^4 = 341 и так далее.   -  person    schedule 18.01.2018

Ответы (1)


arrow_upward
2
arrow_downward

Хотя это не то, что я ищу, я обнаружил, что именно так вы переходите к нижним узлам и, похоже, хорошо работает для того, что я хочу сделать

Как выполнить итерацию дерева Quad/Oct

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
    }
}
person kbz    schedule 07.09.2017