2

この問題に遭遇したとき、nVidia (「効率的なスパース ボクセル オクトリー」)の人々がボクセルのことを行っていたように、スパース オクトリーの実装を作成するのに苦労していました。

octree のリーフがどこにあるかを示す byte 型 (8 ビットのみ) のビットフィールドがあります (1 はリーフを意味し、0 はリーフがないことを意味し、8 つのノードが接続されている --> 8 ビット)。私が今やりたいことは、葉の位置の配列を返すことです。私の現在の実装では、while ループを使用して、LSB が設定されているかどうかを確認しています。入力はその後 1 シフトされます。だからここに私がそれを行う方法があります：

int leafposition = _leafmask & _validmask;
int[] result = new int[8]; 
int arrayPosition = 0;
int iteration = 0;
while ( leafposition > 0 )
{
   iteration++; //nodes are not zero-indexed ... ?
   if ( (leafposition & 1) == 1 ) // LSB set?
   {
     result.SetValue( iteration, arrayPosition );
     arrayPosition++;
   };
   leafposition = leafposition >> 1;
}
return result;

これは見栄えがよくなく、気になる点が 2 つあります。

  • この while ループは for ループを模倣しています
  • 結果の配列は 8 つの値よりも小さくなる可能性が高いですが、サイズ変更にはコストがかかります

結果[2,4,6]は 42 のようになると思い(0010 1010)ます。

まだ読みやすい、よりエレガントなソリューションを提供できる人はいますか?

結果

以前に実装した octree リーフ カウントの関数を使用して、配列を適切なサイズに設定しています。

4

3 に答える 3

5

コードの簡潔さを追求する場合は、これを使用します。

int[] result = new int[8]; 
byte leafposition = 42;
int arrayPosition = 0;
for (int iteration = 0; iteration < 8; ++iteration)
    if ((leafposition & (1 << iteration)) != 0)
        result[arrayPosition++] = iteration + 1;   // one-indexed

パフォーマンスを追求する場合は、事前に入力された配列 (256 エントリ) を使用します。これは、(コンパイル時に) 静的に生成することも、(メソッドを初めて呼び出す前に) 遅延的に生成することもできます。

int[][] leaves =
{
    /* 00000000 */ new int[] { },
    /* 00000001 */ new int[] { 1 },
    /* 00000010 */ new int[] { 2 },
    /* 00000011 */ new int[] { 1, 2 },
    /* 00000100 */ new int[] { 3 },
    /* 00000101 */ new int[] { 1, 3 },
    /* 00000110 */ new int[] { 2, 3 },
    /* 00000111 */ new int[] { 1, 2, 3 },
    /* 00001000 */ new int[] { 4 },
    /* 00001001 */ new int[] { 1, 4 },
    /* ... */
};

byte leafposition = 42;
int[] result = leaves[leafposition];

編集：ルックアップテーブルを使用していて、1回限りの初期化（その後の多くの使用で償却される）に余裕がある場合は、（ソースコードを肥大化させるのではなく）動的に作成することをお勧めします。LINQ のサンプル コードを次に示します。代わりにループ バージョンを使用できます。

int[][] leaves = new int[256][];
for (int i = 0; i < 256; ++i)
    leaves[i] = Enumerable.Range(0, 8)
                          .Where(b => (i & (1 << b)) != 0)
                          .Select(b => b + 1)
                          .ToArray();
于 2013-05-19T17:52:04.443 に答える
0

どうですか、

public static IEnumerable<int> LeafPositions(byte octet)
{
    for (var i = 1; octet > 0; octet >>= 1, i++)
    {
        if ((octet & 1) == 1)
        {
            yield return i;
        }
    }
}

または、私の意見では読みやすいです。

IEnumerable<int> LeafPositions(byte octet)
{
    if ((octet & 1) == 1) yield return 1;
    if ((octet & 2) == 2) yield return 2;
    if ((octet & 4) == 4) yield return 3;
    if ((octet & 8) == 8) yield return 4;
    if ((octet & 16) == 16) yield return 5;
    if ((octet & 32) == 32) yield return 6;
    if ((octet & 64) == 64) yield return 7;
    if ((octet & 128) == 128) yield return 8;
}

というか極端に行く

IEnumerable<int> LeafPositions(byte octet)
{
    switch (octet)
    {
        case 1:
            yield return 1;
            break;

        case 2:
            yield return 2;
            break;

        case 3:
            yield return 1;
            yield return 2;
            break;

        ...

        case 255:
            yield return 1;
            yield return 2;
            yield return 3;
            yield return 4;
            yield return 5;
            yield return 6;
            yield return 7;
            yield return 8;
            break;
    }

    yield break;
}
于 2015-06-16T09:18:47.833 に答える
0

__builtin_ffs を使用する C スタイルのソリューションを次に示します。

int arrayPosition = 0;
unsigned int tmp_bitmap = original_bitfield;        
while (tmp_bitmap > 0) {
    int leafposition = __builtin_ffs(tmp_bitmap) - 1;
    tmp_bitmap &= (tmp_bitmap-1);
    result[arrayPosition++] = leafposition;
}
于 2015-05-30T06:47:47.777 に答える