如何在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)

我还没有真正尝试过这个,但我担心性能仍然低于标准,因为我不能将LinearNode实例存储在UArray中,也不能将Int正确子项的索引与组成该Float值的值一起存储.单个UArray中的AABB(如果我弄错了,请纠正我).使用两个阵列意味着缓存一致性差.所以我基本上都在寻找一种有效存储树的方法,因此我可以期待良好的遍历性能.它应该是

• 紧凑
• 具有良好的地方特性
• 与最近的GHC编译器合作
• 应尽可能小的间接(尽管"thunk"无法帮助表现,所以"unboxed"类型会让我觉得有帮助)

Answer 1

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