Обход граничащей объемной иерархии в шейдерах - PullRequest
Новая
       134

Обход граничащей объемной иерархии в шейдерах

4 голосов
/ 02 апреля 2019

Я работаю над трассировщиком путей, используя вулканские вычислительные шейдеры.Я реализовал дерево, представляющее иерархию ограничивающего объема .Идея BVH состоит в том, чтобы минимизировать количество объектов, на которых необходимо выполнить тест пересечения лучей.

# 1 Наивная реализация

Моя первая реализацияочень быстрый, он проходит по дереву до одного листа дерева BVH.Однако луч может пересекать несколько листьев.Этот код приводит к тому, что некоторые треугольники не отображаются (хотя они должны). 

int box_index = -1;

for (int i = 0; i < boxes_count; i++) {
    // the first box has no parent, boxes[0].parent is set to -1
    if (boxes[i].parent == box_index) {
        if (intersect_box(boxes[i], ray)) {
            box_index = i;
        }
    }
}

if (box_index > -1) {
    uint a = boxes[box_index].ids_offset;
    uint b = a + boxes[box_index].ids_count;

    for (uint j = a; j < b; j++) {
        uint triangle_id = triangle_references[j];
        // triangle intersection code ...
    }
}

# 2 Многоуровневая реализация

Мои вторые учетные записи реализацииза то, что несколько листьев могут пересекаться.Однако эта реализация на 36x медленнее, чем реализация # 1 (хорошо, я пропускаю некоторые тесты пересечения в # 1, но все же ...). 

bool[boxes.length()] hits;
hits[0] = intersect_box(boxes[0], ray);

for (int i = 1; i < boxes_count; i++) {
    if (hits[boxes[i].parent]) {
        hits[i] = intersect_box(boxes[i], ray);
    } else {
        hits[i] = false;
    }
}

for (int i = 0; i < boxes_count; i++) {
    if (!hits[i]) {
        continue;
    }

    // only leaves have ids_offset and ids_count defined (not set to -1)
    if (boxes[i].ids_offset < 0) {
        continue;
    }

    uint a = boxes[i].ids_offset;
    uint b = a + boxes[i].ids_count;

    for (uint j = a; j < b; j++) {
        uint triangle_id = triangle_references[j];
        // triangle intersection code ...
    }
}

Эта разница в производительности сводит меня с ума.Кажется, что только одно утверждение типа if(dynamically_modified_array[some_index]) оказывает огромное влияние на производительность.Я подозреваю, что компилятор SPIR-V или GPU больше не может делать свою магию оптимизации?Итак, вот мои вопросы:

  1. Действительно ли это проблема оптимизации?

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

  3. Существует ли стандартный способ реализации запросов дерева BVH в шейдерах?

1 Ответ

3 голосов
/ 03 апреля 2019

После некоторых копаний я нашел решение. Важно понимать, что дерево BVH не исключает возможности оценки всех листьев.

Реализация № 3 ниже, использует ссылки попадания и пропуска. Ящики должны быть отсортированы таким образом, чтобы в худшем случае все они запрашивались в правильном порядке (поэтому достаточно одного цикла). Однако ссылки используются для пропуска узлов, которые не нужно оценивать. Когда текущий узел является листовым узлом, выполняются фактические треугольные пересечения.

  • ссылка удара ~ к какому узлу перейти в случае попадания (зеленый внизу)
  • ссылка мисс ~, к какому узлу перейти в случае пропуска (красный внизу)
* +1012 *BVH tree evaluation order

Изображение взято с здесь . Соответствующая статья и исходный код также есть на странице профессора Тошии Хачисуки . Эта же концепция также описана в этой статье, упомянутой в слайдах .

# 3 Дерево BVH с ссылками Hit и Miss

Мне пришлось расширить данные, которые передаются в шейдер с помощью ссылок. Кроме того, для правильного хранения дерева потребовалось некоторое автономное переключение. Сначала я попытался использовать цикл while (цикл до box_index_next равен -1), что снова привело к безумному замедлению. В любом случае, работает достаточно быстро: 

int box_index_next = 0;

for (int box_index = 0; box_index < boxes_count; box_index++) {
    if (box_index != box_index_next) {
        continue;
    }

    bool hit = intersect_box(boxes[box_index], ray);
    bool leaf = boxes[box_index].ids_count > 0;

    if (hit) {
        box_index_next = boxes[box_index].links.x; // hit link
    } else {
        box_index_next = boxes[box_index].links.y; // miss link
    }

    if (hit && leaf) {
        uint a = boxes[box_index].ids_offset;
        uint b = a + boxes[box_index].ids_count;

        for (uint j = a; j < b; j++) {
            uint triangle_id = triangle_references[j];
            // triangle intersection code ...
        }
    }
}

Этот код примерно в 3 раза медленнее, чем быстрая, но некорректная реализация # 1. Это несколько ожидаемо, теперь скорость зависит от реального дерева, а не от оптимизации GPU. Рассмотрим, например, вырожденный случай, когда треугольники выровнены вдоль оси: луч в одном и том же направлении может пересекаться со всеми треугольниками, тогда необходимо оценить все листья дерева.

Prof. Тошия Хатисука предлагает дальнейшую оптимизацию для таких случаев в своих полях (стр. 36 и далее): один хранит несколько версий дерева BVH, пространственно отсортированных по x, -x, y, -y, z и - г. Для обхода необходимо выбрать правильную версию на основе луча. Тогда можно прекратить обход, как только треугольник с листа пересекается, поскольку все оставшиеся узлы, которые необходимо посетить, будут пространственно позади этого узла (с точки зрения луча).

...