与哈希表相比，树形结构的最大优势似乎也不存在于GPU上。
我们不喜欢重新分配内存的图形，因此我们通常在VRAM中过度分配内存只是为了能够重用数据结构。因此，二叉树的属性（提高内存效率）似乎与GPU应用程序无关。
用于缓存的数据一致性似乎也不成立。对于GPU生成的树，异步性使得很难保证逻辑上接近的值也彼此接近地存储在基础内存中。因此，无论如何，您最终还是会跳来跳去。
在哈希表中实施某些GPU友好的启发式方法也比在树中实施起来容易得多。例如，将哈希查找的数量限制为固定的数量（例如20），并使用相同的逻辑来防止扭曲执行不同的分支代码。从本质上讲，您始终可以检查20个潜在的碰撞，只需将结果插入包含该键的单元格即可。在树中，遍历数据结构更多地依赖于数据本身，而不是数据结构。
那么为什么八叉树比哈希表使用更多呢？
#1 楼
我写Chipmunk2D物理引擎的2美分是，当您有很多大小相同的对象时，空间哈希非常有用。 10年前，我有一个演示，在Core 2 Duo上实时运行了20k交互粒子。如果您对其进行了调整，那么空间散列对此非常有用。我之后将空间散列替换为二进制AABB树作为默认结构。它远非完美，但比没有调整的一般情况下的空间散列要快。向其中添加时间分量也更加容易，因此我可以逐步更新一组潜在的冲突。在所有这些都准备就绪的情况下，我对空间哈希进行速度更快的唯一测试是具有数千个粒子且没有静态几何图形的测试。
对于八叉树... Meh，我从不使用他们。基本的四叉树/八叉树并不能真正满足实际数据以及您可以使用的其他BVH的过多需求。基本的AABB树几乎一样简单，而且方式更有效。
评论
$ \ begingroup $
“具有空间哈希的对象是具有数千个粒子且没有静态几何的对象”，这真是我正在研究的，这意味着我的直觉是正确的！
$ \ endgroup $
– Makogan
18/12/14在22:36
#2 楼
这里有很多东西。“阅读论文时”。什么论文？如果本文的主题是关于空间分割结构以外的其他内容，则可以使用任何已知的基本概念都可以转换为其他结构的方法。还是很难说。
“例如，对于跟踪八叉树的光线，未命中会导致您遍历二叉树子结构，即O（nlogn），而哈希表是O（n）” 。在这种情况下，大O表示法毫无意义。当您谈论依赖于实现细节的事情时，您正在以特定的规模处理特定的技术。 O（nlogn）算法可能比O（n）算法慢得多，对于今天的“ n”来说，它一直在发生。尽管您可能会说，在10年内可能会发生变化，但是确实如此，但是在同一10年内，您的GPU可能看起来完全不同，因此无论如何都需要改变现有技术的算法。这很常见，如果您查看GPU算法（尤其是GPU仍在不断发展）
八卦是什么？什么哈希表？那里有很多选择。例如“ ...因为它们除了散列位置外在内存中不需要任何逻辑位置”。只有在没有哈希冲突的情况下才是真的，是吗？如果发生冲突，则无论使用哪种策略（探测列表或链表），都需要在线程之间进行同步，因此在GPU上实现构建并不是那么容易。相反，对于八叉树，如果您想按照建议的方式“过度分配”，则可以分配一棵完整的树，然后索引将同样仅取决于位置。实际上，如果您做一些数学运算，您会发现在这种情况下，八叉树只是使网格模糊的一种方式（例如，将van Ende Boas布局与Morton顺序的网格进行比较...很好的练习）。 br />我还有很多话要说，但让我在这里追逐。
特别是对于光线追踪，八进制和哈希表都不是那么受欢迎。 AABB的BVH是必经之路。
Octrees优于散列网格的主要优点是您的单元格分辨率可以适应几何形状。网格不会，您必须选择一个像元大小，并且在场景的某些部分可能会太小，而在其他某些部分可能会太大。细节。由于幼稚的八叉树太深/不够宽，因此在实践中可能永远不要使用。如果说一个八叉树“更大”，例如说一个4x4x4网格，其中每个非空单元格中嵌套有4x4x4网格，那么您将创建所谓的分层网格。因此，网格和八叉树在频谱上存在，八叉树是最“深”的，网格是最“浅”的（仅一个级别，场景中全局为单个网格），层次网格可以在两者之间进行交易>这可能会有所帮助！ http://www.realtimerendering.com/Real-Time_Rendering_4th-Real-Time_Ray_Tracing.pdf;）
评论
$ \ begingroup $
通过将可能发生的冲突的数量限制为已知的数量（例如20），并在标志上使用原子操作，就可以很好地避免哈希冲突，而无需进行大的同步。使用像体素全局照明生成的紧凑八叉树那样的基于八叉树的算法，您需要2个单独的着色器，分别在一个循环中调用每个像素以实现内存分配。而“普通”八叉树（您可以基于固定函数知道索引的八叉树）会创建很多无用的内存，届时3D卷可能会更好。
$ \ endgroup $
– Makogan
18/12/6在1:18
$ \ begingroup $
另外，我认为您在解释渐进复杂性时交换了复杂性，由于硬件的可变性，渐进复杂性在现代算法中不是问题
$ \ endgroup $
– Makogan
18/12/6在1:19
评论
因为八叉树比我想的哈希表更容易编写？与哈希表相比，树如何更容易编写？哈希表是一维结构，八叉树是映射到一维存储阵列上的4维结构。我都写过，哈希表比八叉树简单得多。
Imo的主要好处在于使用树结构生成的层次结构。这样一来，如果射线不与任何上层框相交，则已经修剪了大量节点。相反，网格需要检查与所有相交单元格的交集。这个答案解释得很好。 gamedev.stackexchange.com/questions/69776 / ...
迈克·阿克顿（Mike Acton）最近做了相关的演讲：)查看@mike_acton的推文：twitter.com/mike_acton/status/1062458276812451840?s=09
@gallickgunner这一次只能一次有效地找到存储数据的树中的区域。但是，大多数效果都需要对多个相邻区域进行采样（AO，发射，漫反射....）。哈希表更好。您可以使用散列的mipmap模仿树的层次结构。它为您提供完全相同的层次结构和完全相同的渐近计算时间。