すぐに隣接するボクセルの数を数える方法は？

Question

私はボクセルのいくつかが満たされている3Dグリッド（ボクセル）を持っていますが、ボクセルのいくつかは満たされていません。 3Dグリッドはまばらに塗りつぶされているので、塗りつぶしたボクセルの座標（x、y、z）を持つfilledVoxelsというセットがあります。私がしようとしていることは、各塗りつぶしボクセルがどれくらいであるか、隣り合うボクセルがどれだけ満たされているかを知ることです。ここ

は一例であり：

• 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の隣人を持つすべてのボクセルのリストを取得したいと思います。

Answer 1

あなたはすべてのノードが、それが全てで満たされたのボクセルが含まれているかどうかを指定するフラグが含まれているoctreeにあなたのボクセル空間を変換することができます。

ノードに塗りつぶしたボクセルが含まれていない場合は、その子孫のいずれかを確認する必要はありません。

Answer 2

グリッドに対応するルックアップテーブルを1つずつ保持することができますので、IsFullVoxel()を使用して一度確認した後、値をこのグリッドに入れてください。行進している各ボクセルについて、ルックアップテーブルの値が有効かどうかを確認し、IsFullVoxel()と呼ぶだけです。

あなたはどちらか、すべての隣接ボクセルを反復処理IsFullVoxel()またはLUTを使用して避けることができないように思える大藤。先験的な情報があれば助けになるかもしれません。たとえば、最大x個の隣接ボクセルがあることが分かっていた場合、または各方向に隣接するボクセルが最大でy個あることが分かっていた場合などです。例えば、あなたが5から6の隣人を持つボクセルを探しているのを知っているならば、あなたは7人の完全な隣人または22人の空の隣人を見つけた後で止めることができます。

私は機能IsFullVoxel()は、ボクセルがいっぱいになった場合はtrueを返す存在すると仮定しています。

Answer 3

あなたの質問はあまり明確ではありません。私はあなたがちょうど満たされたポイントのリストを持っていると仮定しています。その場合には、このはあなたがそれを反復処理する必要があるため、非常に低速になるだろう（あるいは、そのようなkd-treeようなツリー構造のいくつかの種類を使用していますが、これはまだO(log n)になります）。あなたは（グリッドが大きすぎるではない、すなわち）、ちょうどboolsの3D配列を作ることができれば

。 3D配列の26個のルックアップは、それほど時間がかかりません（ルックアップの数を減らす方法はありません）。

実は、今、私はそれについて考えることを、あなたはそれlong型（64ビット）の3次元配列作ることができます。各64ビットブロックは64（4×4×4）個のボクセルを保持する。ブロックの途中でボクセルの隣人をチェックしているときは、64ビットの読み込みを行うことができます（これははるかに高速です）。

Answer 4

あなたの反復における移動のほとんどが隣人にした場合、あなたがステップを作った前にあなただけのチェックをものに戻って見ていないことにより、約25％のご確認を減らすことができます。

Answer 5

あなたの検索のそれぞれが遅い場合、私は言うだろう（O（サイズ））は、バイナリ順序付けられたリストの検索（O（ログ（サイズ）））で、それを最適化する必要があります。

定数26は、あまり心配しません。あなたがよりスマートに反復するなら、あなたは何かをキャッシュして26 - > 10か何かを持つことができると私は思うが、アプリケーション全体をプロファイリングして、それがボトルネックであることを決定しなければ、

Answer 6

ilyaが述べているように、26近隣のルックアップを回避する方法はあまりありません。あなたは、特定の隣人が満たされているかどうかを効率的に特定する上で最大の利益を得なければなりません。ブルートフォースの解が本質的にO（N^2）であることを考えると、その領域で得られる可能性は非常に高いです。あなたの効率的な空間データ型の

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 

、KD-ツリーは、Zifreが示唆されているように、良いかもしれません：あなたは少なくとも一度はすべて満たされたボクセルを反復処理する必要があるので、私は次のようなアプローチを取るでしょうアイディア。いずれにしても、訪問したボクセルをビンニングすることで検索スペースを削減したいと考えています。

Answer 7

あなたがここにZ-order curve便利な概念を見つけることができます。それはあなたが（ある条件付きで）あなたが現在照会しているポイントの周りにデータのスライディングウィンドウを維持することができるので、次のポイントに移動するときに、すでに実行したクエリの多くを捨てる必要はありません。

Answer 8

必要なルックアップの回数を削減する方法はありますか？

最低でも、ボクセルごとに個以上、個のルックアップを実行する必要があります。それが最小であるため、ボクセルごとに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); 

それはあなたもそうincrementNeighborsを書く必要がありますさらに重要なのは0

にすべての配列要素を設定しますので、あなたはinitializeCountArrayを書く必要があります配列の外側ではインクリメントされません。わずかな速度の増加は、インテリアのすべてのボクセルに対して上記のアルゴリズムを実行してから、片側に隣人が存在しないことを理解している変更されたincrementNeighbrsルーチンを使用して、すべての外側エッジボクセルに対して別々の実行を行います。

このアルゴリズムは、ボクセルごとに1つのルックアップと、ボクセル当たり最大26バイトの加算をもたらす。あなたのボクセル空間が疎な場合、これは非常に少ない（相対的な）追加をもたらすでしょう。ボクセル空間が非常に密集している場合は、アルゴリズムを逆にすることを検討してください。各エントリーの配列を26の値に初期化してから、ボクセルが存在しないときは近傍を減らしてください。

配列には、特定のボクセル（つまり、いくつのネイバーがありますか）の結果が存在します。ボクセル2,3,5がどれだけ多くあるかを知る必要がある場合は、countArray [2] [3] [5]のバイトを見てください。

アレイはボクセルごとに1バイトを消費します。スペースを少なくして、バイトをパックすることで速度を少し上げることもできます。

データの詳細を知っている方が良いアルゴリズムがあります。例えば、非常にまばらなボクセル空間は、オクツリーから大きく恩恵を受けるでしょう。ここでは、内部に塗りつぶしたボクセルがないことを既に知っているときに大きなブロックの参照をスキップできます。しかし、これらのアルゴリズムのほとんどは、行列を満たすためにボクセルごとに少なくとも1回のルックアップを必要としますが、複数の操作を実行している場合は、この1つの操作以上の利点があります。