3

3D グリッド (ボクセル) があり、ボクセルの一部が塗りつぶされ、一部が塗りつぶされていません。3D グリッドはまばらに塗りつぶされているためfilledVoxels、塗りつぶされたボクセルの座標 (x、y、z) のセットを取得しました。私がやろうとしているのは、塗りつぶされたボクセルごとに、隣接するボクセルがいくつも塗りつぶされているかを調べることです。

次に例を示します。

  • FilledVoxels には、ボクセル (1, 1, 1)、(1, 2, 1)、および (1, 3, 1) が含まれます。
  • したがって、ネイバー カウントは次のようになります。
    • (1,1,1) には 1 つの近傍があります
    • (1,2,1) には 2 つの近傍があります
    • (1,3,1) には 1 つの近傍があります。

今、私はこのアルゴリズムを持っています:

voxelCount = new Map<Voxel, Integer>();

for (voxel v in filledVoxels)
  count = checkAllNeighbors(v, filledVoxels);
  voxelCount[v] = count;
end

checkAllNeighbors() は、周囲の 26 個のボクセルすべてを調べます。したがって、合計で 26*filledVoxels.size() ルックアップを実行していますが、これはかなり遅いです。

必要なルックアップの数を減らす方法はありますか? 上記の例を見ると、同じボクセルを数回チェックしていることがわかります。そのため、巧妙なキャッシングでルックアップを取り除くことができるかもしれません。

これが何らかの形で役立つ場合、ボクセルはボクセル化された 3D サーフェスを表します (ただし、穴が開いている可能性があります)。私は通常、5 つまたは 6 つの隣接ボクセルを持つすべてのボクセルのリストを取得したいと考えています。

4

8 に答える 8

2

それぞれのルックアップが遅い場合（O（size））、順序付きリスト（O（log（size）））でのバイナリ検索によって最適化する必要があります。

定数26、私はあまり心配しません。よりスマートに反復する場合は、何かをキャッシュして26-> 10か何かにすることができますが、アプリケーション全体のプロファイルを作成し、それがボトルネックであることが断固としてわかっていない限り、他のことに集中します。

于 2009-06-14T17:26:58.517 に答える
2

ilya が述べているように、26 回の近隣検索を回避するためにできることはあまりありません。特定の隣人が満たされているかどうかを効率的に特定することで、最大の利益を得る必要があります。ブルート フォース ソリューションが本質的に O(N^2) であることを考えると、その領域で得られる可能性のある多くの根拠があります。すべての塗りつぶされたボクセルを少なくとも 1 回反復する必要があるため、次のようなアプローチをとります。

voxelCount = new Map<Voxel, Integer>();
visitedVoxels = new EfficientSpatialDataType();

for (voxel v in filledVoxels)
  for (voxel n in neighbors(v))
    if (visitedVoxels.contains(n))
      voxelCount[v]++;
      voxelCount[n]++;
    end
  next
  visitedVoxels.add(v);
next

効率的な空間データ型については、Zifre が提案したように、kd ツリーが良い考えかもしれません。いずれにせよ、訪問したボクセルをビニングして検索スペースを減らしたいと思うでしょう。

于 2009-06-15T20:22:34.857 に答える
1

ここでは、 Z オーダー曲線が便利な概念であることがわかります。これにより、(特定の条件付きで) 現在クエリを実行しているポイント周辺のデータのスライディング ウィンドウを保持できるため、次のポイントに移動するときに、既に実行したクエリの多くを破棄する必要がなくなります。 .

于 2009-06-16T15:12:56.167 に答える
1

繰り返しの移動のほとんどが隣人に対するものである場合、ステップを実行する前にチェックしたものを振り返らないことで、チェックを約 25% 減らすことができます。

于 2009-06-13T22:14:48.113 に答える
1

一度に 1 つずつボクセルに沿って行進している場合は、グリッドに対応するルックアップ テーブルを保持できます。これにより、使用して一度チェックした後IsFullVoxel()、このグリッドに値を入力できます。行進している各ボクセルについて、ルックアップ テーブルの値が有効かどうかを確認し、そうでない場合にのみ呼び出すIsFullVoxel()ことができます。

IsFullVoxel()OTOHまたはLUTを使用して、隣接するすべてのボクセルを反復することは避けられないようです。もう少し先験的な情報があれば、それは役立つかもしれません。たとえば、隣接する塗りつぶされたボクセルが最大で x 個あることがわかっている場合、または各方向に隣接する塗りつぶされたボクセルが最大で y 個あることがわかっている場合です。たとえば、5 ～ 6 個の隣接ボクセルを探していることがわかっている場合、7 個の完全な隣接ボクセルまたは 22 個の空の隣接ボクセルが見つかったら停止できます。

IsFullVoxel()ボクセルがいっぱいの場合に true を返す関数が存在すると仮定しています。

于 2009-06-13T17:09:36.413 に答える
0

必要なルックアップの数を減らす方法はありますか?

少なくとも、ボクセルごとに少なくとも1 回のルックアップを実行する必要があります。これが最小であるため、ボクセルごとに 1 回のルックアップのみを実行するアルゴリズムは、要件を満たします。

単純なアイデアの 1 つは、配列を初期化して各ボクセルのカウントを保持し、次に各ボクセルを見て、配列内のそのボクセルの近傍をインクリメントすることです。

疑似 C は次のようになります。

#define MAXX 100
#define MAXY 100
#define MAXZ 100

int x, y, z
char countArray[MAXX][MAXY][MAXZ];

initializeCountArray(MAXX, MAXY, MAXZ);  // Set all array elements to 0

for(x=0; x<MAXX; x++)
   for(y=0;y<MAXY;y++)
      for(z=0;z<MAXZ;z++)
         if(VoxelExists(x,y,z))
            incrementNeighbors(x,y,z);

すべての配列要素を 0 に設定するように initializeCountArray を記述する必要があります。

さらに重要なことに、配列の外でインクリメントしないように、incrementNeighbors も記述する必要があります。ここでのわずかな速度の増加は、内側のすべてのボクセルに対してのみ上記のアルゴリズムを実行し、次に、一方の側に隣接がないことを理解する修正された incrementNeighbrs ルーチンを使用して、すべての外側のエッジ ボクセルに対して個別に実行することです。

このアルゴリズムでは、ボクセルごとに 1 回の検索が行われ、ボクセルごとに最大 26 バイトの追加が行われます。ボクセル空間がまばらな場合、(相対的な) 加算はほとんどありません。ボクセル空間が非常に密集している場合は、アルゴリズムを逆にすることを検討してください。つまり、配列をエントリごとに 26 の値に初期化し、ボクセルが存在しない場合は近隣をデクリメントします。

与えられたボクセルの結果 (つまり、いくつの隣接ボクセルがあるか?) が配列に存在します。ボクセル 2、3、5 に隣接するボクセルの数を知る必要がある場合は、countArray[2][3][5] のバイトを見てください。

配列は、ボクセルごとに 1 バイトを消費します。バイトをパッキングすることで、使用するスペースを減らし、速度を少し上げることができます。

データの詳細がわかっている場合は、より優れたアルゴリズムがあります。たとえば、非常にまばらなボクセル空間は、内部に塗りつぶされたボクセルがないことが既にわかっている場合に、ルックアップの大きなブロックをスキップできる octree から大きな恩恵を受けます。ただし、これらのアルゴリズムのほとんどは、マトリックスを埋めるためにボクセルごとに少なくとも 1 回のルックアップを必要としますが、複数の操作を実行している場合は、この 1 回の操作よりも多くの利点があります。

于 2010-10-12T19:28:22.893 に答える