14

私は Haskell Raytracer で遊んでいて、現在、階層を格納するために単純なバイナリ ツリーを強調する BVH 実装を使用しています。

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

ここで、Dimension はX、YまたはZ(より高速なトラバーサルに使用) であり、AABB は軸に沿ったバウンディング ボックスのタイプです。これはかなりうまく機能していますが、できるだけ早くこれを取得したいと思っています。したがって、私の次のステップ (C/C++ を使用する場合) は、このツリーを使用して、ノードが配列に格納される平坦化された表現を構築することです。「左」の子はすぐにその親ノードと親の右の子のインデックスに従います。親と一緒に保存されるので、次のようなものがあります。

data LinearNode
   = LinearNode Dimension Int AABB
   | LinearLeaf AnyPrim AABB

data LinearBvh
   = MkLinearBvh (Array Int LinearNode)

私はまだこれを実際に試していませんでしたが、LinearNodeインスタンスを UArray に格納することもInt、正しい子のインデックスをFloat、単一の UArray 内の AABB (間違っていた場合は訂正してください)。また、2 つの配列を使用すると、キャッシュの一貫性が低下します。したがって、基本的には、ツリーを効率的に保存して、トラバーサルのパフォーマンスを向上させる方法を探しています。それはあるはずです

  • コンパクト
  • 良好な地域特性を持つ
  • 最近のGHCコンパイラで動作
  • 可能な限り少ない間接化を通過する必要があります（「サンク」を通過してもパフォーマンスは向上しないため、「ボックス化されていない」タイプが役立つと思います）
4

3 に答える 3

4

私があなたを正しく理解していれば、ユーザー定義型のボックス化されていない配列が必要ですか? その場合は、ループ融合もサポートするベクター パッケージをチェックしてください。High-Performance 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 に答える