Реордер траверса BVH нод в моём алгоритме обхода BVH деревьев
Спасибо Кайлу Маклахлену @id491583 за его вчерашнюю ссылку в комментариях к моему посту на слайды Тошии Хачисуки за 2015 год о траверсе BVH деревьев с помощью запечённых хит и мисс ссылок.
Данный способ траверса в слайдах Тошии адресуется некой бумаге Smits 98, я сегодня из любопытсва погуглил кто ещё цитировал Smits 98 в своих работах, и наткнулся на эту Чехо-Немецко-Интеловскую бумагу 2011 года:
Цитата параграфа, в котором упоминается Smits 98:
For BVHs, Smits [1998] proposed an approach in which each node contained a so-called “skip node pointer” that specified which node to traverse next if the ray missed the current node. This approach was later used for a GPU implementation by Torres et al. [2009]. While elegant, this method imposes the same traversal order for all rays, leading to some rays traversing the hierarchy “back-to front” (which in turn can lead to a significant increase in box and primitive tests). This can be avoided by having each node store a different skip pointer for different ray orientations [Boulos and Haines 2006], but the amount of additional storage required for this traversal algorithm makes this approach impractical.
Перевод на русский:
Для BVH деревьев, Смитс [1998] предложил подход, в котором каждая нода содержала так называемый «указатель на пропуск ноды», определяющий, какую ноду следует пройти дальше, если луч пропускает текущую ноду (*Мой комментарий: вчера, этот пропуск я помечал как (f) ложь вернувшуюся из ноды, в контексте BVH означающую, что луч не попал в бокс ноды). Этот подход позже был использован в реализации на графическом процессоре Торресом и др. [2009]. Хотя этот метод элегантен, он накладывает одинаковый порядок обхода для всех лучей, что приводит к тому, что некоторые лучи проходят иерархию «сзади вперед» (что, в свою очередь, может привести к значительному увеличению количества проверок боксов и примитивов). Этого можно избежать, если каждая нода будет хранить свой указатель на пропуск для разных ориентаций луча [Булос и Хейнс 2006], но объем дополнительной памяти, необходимой для этого алгоритма обхода, делает этот подход непрактичным.
Фраза "он накладывает одинаковый порядок обхода для всех лучей" подтвердила мои опасения, что мой алгоритм тоже мог быть подвержен этому недостатку, для примера, это означало бы, что луч, который проходит через все боксы BVH дерева, из-за определённого алгоритмом порядка траверса мог начинать тестировать луч на пересечение сначала с боксом задней части BVH меша, что может быть неэффективно в случае если мы ищем только одно самое ближайшее пересечение с треугольниками меша, так как самое ближайшее пересечение с наибольшей долей вероятности произойдёт с передними относительно луча треугольниками, а не с задними.
Но! Мой алгоритм имеет туз в рукаве, которого не было у способа с запечёнными ссылками Smits 1998 -- я то могу ноды переставлять местами прямо во время работы алгоритма. :)
В примере прошлого поста, мы меняли ноду вернувшую (t) правду на её ветви таким образом:
i = 0
[*0]
i = 2
[-1, 1, *2]
А что, если... мы приостановим работу алгоритма, и не начнём тестировать ноду 2, а в момент добавления нод 1 и 2 сразу начнём их тестировать на возвращаемую ими правду или ложь? :) Ведь тестировать нам их придётся в любом случае, но если мы сделаем это сейчас, в момент добавления нод в массив индексов, и если обе ноды вернут правду, мы можем сравнить какой бокс этих нод был ближе к лучу, и на основе этого сравнения поменять индексы нод в массиве местами.
Скажем, тест выявил, что бокс ноды 1 был ближе к лучу чем бокс ноды 2: тогда меняем индексы местами!
Было:
i = 2
[-1, 1, *2]
Стало:
i = 2
[-1, 2, *1]
И теперь мы можем продолжить работу алгоритма, который начнёт с ближайшей ноды 1, что с высокой долей вероятности приведёт к более быстрому нахождению пересекаемого треугольника и остановит поиск, никогда не затрагивая ноду 2 и все её ветви. :)
Tarasenkov 2026 : Smits 1998 = 1 : 0 😄