Построение kd-дерева в cuda

Question

Например, у меня есть массив (x, y) точек, и я хочу организовать их в kd-tree

Построение kd-дерева включает в себя сортировку и вычисление ограничивающих рамок. Эти алгоритмы прекрасно работают на CUDA, но есть ли способ построить kd-дерево, используя как можно больше потоков?

Я думаю, что должны быть некоторые уловки:

Обычно kd-tree реализуется с помощью рекурсии, но, насколько мне известно, у процессоров CUDA нет аппаратного стека, поэтому рекурсии следует избегать.

Как эффективно построить kd-дерево в Cuda?

Answer 1

Возможно, вы захотите взглянуть на следующие документы:

• обход стека KD-Tree для высокопроизводительной трассировки лучей GPU

• Конструкция дерева KD в реальном времени на графическом оборудовании

Они могут помочь вам в этом. Найдите их в Google, и вы найдете их в Интернете.