14

我正在使用 Haskell Raytracer，目前使用 BVH 实现，它强调一个幼稚的二叉树来存储层次结构，

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

其中 Dimension 是X, Yor Z（用于更快的遍历）并且 AABB 是我的轴对齐边界框类型。这工作得相当好，但我真的很想尽可能快地做到这一点。所以我的下一步（当使用 C/C++ 时）将使用这棵树来构建一个扁平化的表示，其中节点存储在一个数组中，“左”子节点立即跟随它的父节点和父节点的右子节点的索引与父母一起存储，所以我有这样的事情：

data LinearNode
   = LinearNode Dimension Int AABB
   | LinearLeaf AnyPrim AABB

data LinearBvh
   = MkLinearBvh (Array Int LinearNode)

我还没有真正尝试过这个，但我担心性能仍然会低于标准，因为我不能将LinearNode实例存储在 UArray 中，我也不能将Int索引正确的孩子与Float构成的值一起存储AABB 在单个 UArray 中（如果我弄错了，请纠正我）。并且使用两个数组意味着糟糕的缓存一致性。所以我基本上是在寻找一种有效存储我的树的方法，这样我就可以期待良好的遍历性能。应该是

  • 袖珍的
  • 具有良好的局部性
  • 使用最新的 GHC 编译器
  • 应该通过尽可能少的间接（尽管“thunk”不能帮助提高性能，所以“未装箱”类型会有所帮助）
4

3 回答 3

4

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

于 2011-02-22T13:03:58.527 回答
2

我真的应该指出，Haskell 并不擅长为程序员提供一种在内存中选择数据布局的方法。

您可能有兴趣以缓存不注意的方式将树存储在平面数组中（“Van Emde Boas 树”）。它应该工作，但谁知道。:)

（无耻插件：我前段时间做过类似的努力；我使用了 ATS 编程语言的一些高级类型系统功能，使光线追踪器更安全、更快；请参阅此处的代码：http ://code.google .com/p/ats-miscellanea/ ——不幸的是，我还没有走多远）

于 2011-02-22T14:12:22.260 回答
0

您提出的建议是几年前发现的，称为边界间隔层次结构（BIH）。

于 2011-11-09T14:02:21.090 回答