2

現在、大まかに次のようにして「近隣グラフ」を作成しています。

for every voxel
  look at every other unseen voxel 
    check if neighbours

これはおおよそ n の 2 乗 (マイナス n) で実行されます。一定数のボクセルには許容できますが、リストが大きくなると明らかに時間がかかります。

別の素朴な解決策は、すべてを大きな 3D 配列またはハッシュマップに入れることです。これは O(n) で実行されますが、より多くのメモリを犠牲にします。

もっと速い方法はありますか？Googleで正しい検索用語を入力できないようです...

4

1 に答える 1

4

octreeやkd ツリー構造のような空間分割ツリーを見たいと思うかもしれません。これらの構造は通常、非常に効率的に構築でき (O(n) または O(n log n)、IIRC)、指定された境界ボックス内の最近傍または点を見つけるための非常に高速なルックアップを提供します。これらの構造の 1 つを使用すると、巨大な 3D 配列を作成するために大量のメモリを消費することなく、パフォーマンスが大幅に向上するはずです。

お役に立てれば！

于 2012-06-22T02:08:17.373 に答える