Как искать (возможно, несколько) узлов в двоичном дереве, где все предыдущие родительские узлы соответствуют критериям? - PullRequest
Новая
       68

Как искать (возможно, несколько) узлов в двоичном дереве, где все предыдущие родительские узлы соответствуют критериям?

2 голосов
/ 05 февраля 2020

Я пишу трассировщик пути в Golang, и недавно я добавил поддержку треугольников и файлов OBJ. Я использую алгоритм пересечения Мёллера – Трумборе для проверки пересечений, но когда модель имеет много треугольников, рендеринг замедляется. Решением для этого является использование BVH, которые являются двоичными деревьями. Прочитав о BVH, я столкнулся с использованием AABB (ограничивающие прямоугольники по оси), потому что их легко построить и легко проверить на пересечения. Например, давайте построим двухуровневую BVH для модели с 10 треугольниками. Вместо того, чтобы проверять луч на пересечение с каждым из этих треугольников, я просто проверяю на пересечение с верхней ограничительной рамкой. Если он не пересекается, я знаю, что он не пересекается ни с одним треугольником в модели, но если это произойдет, я хочу проверить на пересечение на более низком уровне. Если луч пересекается, скажем, с левой ограничительной рамкой, я знаю, что мой треугольник находится в этой рамке, и теперь я могу перебирать треугольники внутри него.

Допустим, у меня есть модель с 50 треугольниками и Я построил BVH так: 

                            50 tris  <--- the ray intersects with this bounding box
                            |
                            |
                           / \
                          /   \
                         /     \
                        /       \
                       /         \
                 25 tris         25 tris   <--- the ray intersects with both bounding boxes
                   |                 |
                   |                 |
                  / \               / \
                 /   \             /   \
                /     \           /     \
           12 tris  13 tris   12 tris  13 tris  <--- leaves
           ^                               ^
           |                               |
the ray intersects with this bb       and this bb

Теперь есть проблема: луч пересекается с двумя листьями. Я попытался рекурсивно проверить пересечения BVH следующим образом: 

// here's my BVH struct:

type BVH struct {
    left, right *BVH
    leaves      []Triangle
    bounds      AABB
    last        bool
}

func testBVH(tree *BVH, level int, r Ray, tMin, tMax float64) []Triangle {
    temp := []Triangle{}
    if tree == nil {
        return nil
    }
    if tree.last {
        return tree.leaves
    } else if level > 1 {
        if tree.left.bounds.hit(r, tMin, tMax) {
            temp = testBVH(tree.left, level-1, r, tMin, tMax)
        }
        if tree.right.bounds.hit(r, tMin, tMax) {
            tr := testBVH(tree.right, level-1, r, tMin, tMax)
            for i := 0; i < len(tr); i++ {
                temp = append(temp, tr[i])
            }
        }
    }
    return temp
}

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

monkey with BVH

И та же модель без каких-либо BVH:

monkey without BVH

Он пытается найти треугольники там, где есть пересечение с двумя или более ограничивающими прямоугольниками по лучу. Я проверил, и с генерацией BVH все в порядке, поэтому проблема заключается в поиске двоичного дерева. Как правильно проверять пересечения с BVH?

1 Ответ

1 голос
/ 05 февраля 2020

Хорошо, проблема была в самой структуре дерева. Я изменил листья, чтобы они имели два элемента, и изменил функцию testBVH, чтобы она выглядела так: 

func testBVH(tree *BVH, level int, r Ray, tMin, tMax float64) [][2]Leaf {
    temp := [][2]Leaf{}
    if tree == nil {
        return nil
    }
    if tree.last {
        if tree.bounds.hit(r, tMin, tMax) {
            return append(temp, tree.leaves)
        }
        return temp
    } else if level > 0 {
        if tree.left.bounds.hit(r, tMin, tMax) {
            temp = testBVH(tree.left, level-1, r, tMin, tMax)
        }
        if tree.right.bounds.hit(r, tMin, tMax) {
            tr := testBVH(tree.right, level-1, r, tMin, tMax)
            temp = append(temp, tr...)
        }
    }
    return temp
}

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

...