data-structures - 在 cuda 中构建 kd 树

Question

例如，我有 (x,y) 点数组，我想在 kd-tree 中组织它们

构建 kd-tree 包括排序和计算边界框。这些算法在 CUDA 上运行良好，但是有没有办法使用尽可能多的线程来构建 kd-tree？

我认为应该有一些技巧:

通常，kd-tree 是通过递归实现的，但据我所知，CUDA 处理器没有硬件堆栈，因此应避免递归。

如何有效地在 Cuda 中构建 kd-tree？

Answer 1

您可能想查看以下论文:

用于高性能 GPU 光线追踪的无堆栈 KD 树遍历

图形硬件上的实时 KD 树构建

他们可能会帮助你。谷歌它们，你会发现它们在线可用。