Как преобразовать объект узла BVH в простой массив? - PullRequest
Новая
       105

Как преобразовать объект узла BVH в простой массив?

0 голосов
/ 05 мая 2020

Я работаю над трассировщиком лучей Opengl, который может загружать файлы obj и отслеживать их. Мое приложение загружает файл obj с помощью assimp, а затем отправляет все грани треугольника (вершины и индексы) во фрагментный шейдер, используя объекты хранилища шейдеров. Структура basi c собирается отобразить результаты в четырехугольник из фрагментного шейдера.

Когда я загружаю большие объекты (более 100 треугольников), компьютеру потребовалось много времени, чтобы сделать пересечениях, поэтому я начал создавать BVH-дерево, чтобы ускорить процесс. Мой BVH рекурсивно разделяет пространство на два выровненных по оси ограничивающих прямоугольников на основе средней медианы граней треугольников, содержащихся в AABB.

Мне удалось построить древовидную структуру BVH (на CPU), и теперь Я хочу преобразовать его в простой массив, а затем отправить его во фрагментный шейдер (в буфер хранения шейдера).

Это структура моего класса BVH. 

class BvhNode {

public:
    BBox bBox;
    vector<BvhNode> children;
    bool isLeaf;
    int depthOfNode;

    vector<glm::vec3> primitiveCoordinates;

    BvhNode() {}

    ~BvhNode() {}

    BvhNode(vector<glm::vec3> &primitiveCoordinates) {
        this->primitiveCoordinates = primitiveCoordinates;
    }

    void buildTree(vector<glm::vec3> &indicesPerFaces, int depth) {...}

    glm::vec3 calculateCenterofTriangle(glm::vec3 vec, glm::vec3 vec1, glm::vec3 vec2) {...}

    glm::vec3 getCoordinatefromIndices(float index) {...}

    BBox getBBox(vector<glm::vec3> &indices) {...}
};

Но сначала я хотел бы преобразовать его в простой массив, поскольку GLSL не поддерживает указатели. Я читал о том, что двоичное дерево можно преобразовать в массив (если, конечно, дерево готово). Я выдергиваю волосы. Как я могу перебрать весь узел, включая потомков, и, конечно, как заполнить его пустыми узлами (чтобы выполнить определение полного двоичного дерева)? Я начал писать метод, показанный ниже, но у меня возникла ошибка сегментации, когда я объявил переменную nodes как глобальную переменную. Я не знаю почему. 

vector<BvhNode> nodes; // it is a global variable

void putNodeIntoArray(BvhNode node) {

    nodes.push_back(node.children.at(0));
    nodes.push_back(node.children.at(1));
}

Думаю, когда я создаю дерево, мне нужно как-то подписывать каждый узел, где начинаются левый и правый дочерние элементы.

Любая помощь приветствуется.

1 Ответ

1 голос
/ 06 мая 2020

Один из способов размещения узлов двоичного дерева в массиве: для всех узлов в дереве, если данный узел имеет индекс массива i, его дочерние элементы находятся в индексах 2i + 1 и 2i + 2 (описано более подробно здесь ).

enter image description here

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

В псевдокоде: 

int current_index = 0;
node[] array = new node[2^n];
q nodes;
q.add(root);
while (!q.empty) {
   node current_node = q.front()
   array[current_index] = current_node;
   if (current_node.left != null)
      q.add(current_node.left);
   if (current_node.right != null)
      q.add(current_node.right);
   current_index++;
}

Если ваше дерево не является полным (чего, вероятно, не будет, но это зависит от вашего BVH реализации), вам нужно будет немного изменить это, чтобы правильно отслеживать индекс, который каждый узел должен go в. Это также будет тратить пространство, как описано в ссылке выше.

Вместо того, чтобы размещать узлы в порядок в ширину, их также можно расположить (более эффективно) в порядке глубины, как описано в Физический рендеринг здесь .

...