如何在Haskell中快速生成BVH表示法

Question

我正在使用 Haskell Raytracer，并且目前使用 BVH 实现来应用存储层次结构的朴素二叉树。

data TreeBvh
   = Node Dimension TreeBvh TreeBvh AABB
   | Leaf AnyPrim AABB

Dimension 是 X、Y 或 Z（用于更快地遍历），AABB 是我的轴对齐边界框的类型。这个代码已经运行得相当不错了，但我真的很想尽可能快地运行它。所以我的下一步（在使用 C/C++ 时）是使用这棵树构建一个扁平化表示，其中节点存储在数组中，"left" 子节点紧随其父节点，父节点的右子节点的索引与父节点一起存储，因此我有这样的东西：

data LinearNode
   = LinearNode Dimension Int AABB
   | LinearLeaf AnyPrim AABB

data LinearBvh
   = MkLinearBvh (Array Int LinearNode)

我还没有真正地尝试过这个，但我担心性能仍然不够好，因为我不能在 UArray 中存储 LinearNode 实例，也不能将索引右侧子节点的 Int 与组成 AABB 的 Float 值一起存储在单个 UArray 中（如果我理解有误，请纠正我）。而使用两个数组会导致糟糕的缓存协调性。所以我基本上正在寻找一种有效地存储我的树的方法，以便可以期望遍历具有良好的性能。它应该：

• 紧凑
• 具有良好的局部特性
• 与最新版本的 GHC 编译器兼容
• 尽可能少地经过间接访问（通过“thunk”传递无法提高性能，因此我认为“非装箱”类型会有所帮助）

- Waldheinz

---

标记一下，我想看看比我更懂的人怎么说。不过这是个好问题，所以加1。 - Robert Massaioli

我真的不明白为什么你标记了我的问题？ - Waldheinz

啊，好的，我也会收藏这个问题的。 :-) - Waldheinz

@John：我已经这样做了，我花费了大约50%的周期来遍历树，这对于我的简单场景来说有点太多了。 - Waldheinz

@waldheinz 没有运行副本，我无法测试，但我敢打赌添加严格性和 {-# UNPACK #-} pragma 会有很大帮助。 - Thomas M. DuBuisson

Answer 1

如果我理解正确，您想要用户定义类型的非装箱数组？如果是这样，请查看vector包，它还支持循环融合。值得查看高性能Haskell幻灯片

- snk_kid

---

向量包看起来很有吸引力，您能否给出一些代码示例，概述LinearNode和LinearBvh类型的外观？我需要为LinearNode实现Storable，对吗？ - Waldheinz

@Waldheinz，您不需要使用可存储向量，这些向量是为 FFI C 互操作而设计的（但仍然可以使用它们）。您需要为 Data.Vector.Unboxed 和 Storable 的可存储版本实现 Unbox 类型类的实例。文档中有一个示例：http://hackage.haskell.org/packages/archive/vector/0.7.0.1/doc/html/Data-Vector-Unboxed.html，该包的教程在此处：http://haskell.org/haskellwiki/Numeric_Haskell:_A_Vector_Tutorial。 - snk_kid

请注意，此风格将成对的非框箱向量转换为非框箱向量的配对。我倾向于认为这不会影响缓存，但OP提出了一个问题。另一种方法是为自适应值实现非框箱实例：http://hackage.haskell.org/package/adaptive-containers - sclv

Answer 2

我应该指出，Haskell 在给程序员提供选择内存数据布局方面并不是很好。你可能会对以“Van Emde Boas 树”方式在缓存中以平坦数组的形式存储树感兴趣。它应该可以工作，但谁知道呢。 :)（无耻地自推：我曾经做过类似的努力；我使用了 ATS 编程语言的一些高级类型系统特性，使光线追踪器更加安全和快速；请在此处查看代码：http://code.google.com/p/ats-miscellanea/ -- 不幸的是，我还没有走得太远）

- Artyom Shalkhakov

Answer 3

你所提出的想法早在多年前就被发现了，它被称为边界间隔层次结构（BIH）。

- Engineer

---

我知道BIH，但我真的不知道这个答案如何符合我的问题。我正在寻找一种BVH的高效内存表示方法。如果我有一个BIH，我可能会询问一个高效的表示方法，但现在是关于BVH的。 - Waldheinz

抱歉，我没有仔细阅读你的问题，当时已经很晚了。我只看到“左”子节点紧随其父节点，就认为你在谈论BIH所使用的隐式轴排序方式，以极大地提高性能。您是否有任何不想使用BIH而选择BVH的原因？它们在大多数情况下只是BVH的定性改进，尽管显然必须考虑到您的要求。 - Engineer

其实我已经转向使用kd-tree了，因为在我的经验中，它在通过静态场景追踪大量光线时表现最佳。不过，我仍在寻找一种好的方法来表示它在内存中（通常是每个节点8个字节或类似的方式）。 - Waldheinz

"静态场景"是关键词，我同意您选择KD树（假设您使用SAH？）。这是RLE类型方法优于其他方法的一个好处......内存消耗绝对最小（取决于场景的碎片化程度）。当然，在地形高度图vscan射线投射器之外很难应用这种方法。祝好运。 - Engineer