OctreeにVoxel化した情報をストアする

voxel情報をOctreeに格納する方法について考えます。

voxelが消費する容量

voxelの解像度に対して消費する容量は3乗比で増加するわけですが、数字にすると分かりやすいと思います。5123までを表にしてみました。

階層 一辺の分解能 voxelの数
L9 1 1
L8 2 8
L7 4 64
L6 8 512
L5 16 4096(4K)
L4 32 32768(32K)
L3 64 262114(256K)
L2 128 2097152(2M)
L1 256 16777216(16M)
L0 512 134217728(128M)

Sparce Voxel Octreeの構造

Sparce Voxel Octreeの構造は、大きく分けて二つのバッファに分かれます。
構造体配列として使用するノード情報格納用のバッファ(node-pool)と、末端のvoxel値を格納する3Dテクスチャ(brick-pool)です。末端のvoxel値を格納する3Dテクスチャは3x3x3のサイズで確保されます(brick)。voxel値のtri-linearフィルタリングを行うため、この中に2x2x2のvoxel情報を書き込みます。周辺は隣接voxelとのフィルタリングのために存在しますので、SVO構築が終了したあとに、隣接voxelとvoxel値の平均化処理を行います。
node-poolはoctreeのノード情報を確保します。ノード情報は構造体で、node-poolは構造体配列となります。ひとつのノードには、8個の子ノードもしくはbrickを指すためのポインタ値を格納します。そのほかにも、下位ノードをフィルタリングした情報を中間ノードで保持しておく場合は、その情報を保持するためのbrickを保持します。ちなみに、L0にbrickを確保した場合は一辺の分解能は1024になるので、10243のvoxel gridの代わりとみなすことが出来ます。

つまりvoxelで保持する値のうち、tri-linearフィルタリングされた値をサンプリングする必要があるものはbrickを用いて格納し、そうでないものはノードに直接書き込めばいいのです。brickに書き込んだ値は、tri-linearフィルタリングのために値のコピーが必要になる上に、格納するvoxel情報に対して約3.4倍の容量が必要になります。非常に効率が悪い気もしますが、これ以上に空間が疎である場合には高効率なのです。

rasterizerで作られたvoxelをliner-bufferに格納する

SVOを構築する場合は、pixel shaderからポリゴンをvoxelizeした結果を、いったん配列に書き出します。直接SVOを構築することは不可能ではありませんが、効率上の問題があります。この際にOpenGLではインデックスのincrement/decrement専用のatomicを用いることが出来ます(ARB_shader_atomic_counters拡張)。DirectXでも同様のatomic演算はもちろん可能ですが、OpenGLに実装された、このatomicは専用のバッファをBindするので、通常のatomic演算よりも早そうです。時間があったら数字を取ってみたいと思います。

Sparce Voxel Octreeの構築

Octreeの構築には、大きく分けて3ステップに分かれます。

  1. pixel shaderで出力したvoxel fragmentごとにスレッドを起動します。
    子ノードの構築を行う階層で、構築が必要なノードににマークを行います。
  2. 構築を行う階層のノードごとにスレッドを起動します。
    マークが付いているノードは、node-poolより8つの子のノードを確保します。
    確保した子ノードのインデックス情報をノードに記録してoctreeに連結します。
  3. 子階層のノードごとにスレッドを起動します。
    確保された子ノード初期化します。

この3ステップを9回繰り返せば、5123のoctreeの生成が出来るはずです。
octreeの上層は、あらかじめ用意しておいても大きな数ではないので、上から4層ぐらい(1から4096まで)は適応型の分割を行わなくても問題ないはずです。従って、5回で最終レベルのノードまで構築可能です。
処理1のノードに対するマークは、ノード情報の特定の位置のbitに書き込む様にすれば、atomic命令が必要ありません。従って多数のスレッドでvoxel fragmentリストを処理して、同時に同じvoxelにマーク処理を行っても問題ありません。
処理2はマークされているノードを処理します。スレッドのIDから自分が担当するノードを割り出して、マークされていれば、node-poolから8個連続で子ノードを確保します。確保したら、確保した場所のインデックスをノードに格納します。
処理3も、スレッドのIDから自分が担当する子ノードを割り出して、該当ノードを初期化します。確保自体は完了しているので初期化処理のみです。

処理2と処理3が分かれているのには理由があります。
処理2では、実際にnode-poolから確保した子ノードのメモリには一切アクセスしていません。管理用のインデックスをatomic_addするだけです。ここでもしも確保した8個のノードに対してアクセスを行えば、UAVへのアクセスが頻繁になります。したがって、これを処理3で行うようにします。当然ながら処理3で実際の初期化を行うので、1や2の処理に比べるとUAVへのアクセスは頻繁なものになりますが、その分多数のスレッドが起動して、メモリアクセスのレイテンシィを隠蔽します。

brickに対するvoxel値の書き込み

brickは3Dテクスチャの一部を3x3x3だけ確保して、ひとつのbrickとして使用します(下図の緑色部分)。ひとつのbrickには、2x2x2voxel分の情報を格納します(下図の赤色の部分)。3Dテクスチャのtri-linearフィルタリングで、隣接するvoxelと正しく値が補完されるようにするためです。従って、論理的に保持している2x2x2voxelの一つに値を書き込む場合は、実際に保持している3x3x3voxelの中の該当する4voxelに値を書き込む必要があります。他のvoxelと重複して値を書き込むことになるので、値を正規化するための係数も保持する必要があります。voxelから値をサンプリングする際は、内部の赤色の領域のみサンプリングします。これより外は、他のbrickが保持すべき情報です。

隣接するbrick

brick同士の、”論理的な”隣接は、下図の通りです。隣接した面のbrickが1voxel分重複します。この重複した部分は、互いの対応するvoxelの値を平均化して同じ値を保持しておくことで、赤い領域のどの位置をサンプリングしても、tri-linearで補完された値が連続した正しい値を返すことを保障します。この平均化の処理は以下のように行います。

  1. まず”右”のbrickに重複している”左”のvoxel9個の値を、対応する右側のvoxelに加算します。
  2. 次は”右”のvoxelから”左”のvoxelに値をコピーします。
  3. 以上の処理をXYZの各軸で行うことで隣接voxelの値の平均化を行うことが出来ます。

加算のたびに値の正規化を行うと、角のvoxelは3回も正規化を行うことになるので、正規化は別の機会で行います。

voxelのアドレスの記述方法

voxelのアドレスは、離散的なユークリッド座標で記述するのがもっとも一般的だと思います。5123までvoxelを構築する場合はXYZ各軸でで9bitが必要です。XYZの情報を32bitに格納するとすると、XYZWを10:10:10:2として、10243まで格納できるようにして、Wの2bitはvoxel構築時のフラグとして使用するという手が考えられます。
ひとつのoctreeのノードが保持する8個の子ノードとアドレスの位置関係を下図に示します。

このように、octreeの8個のvoxelは各軸の分解能が2のユークリッド空間とみなすことが出来ます。また、XYZの各座標の同じ桁のbitを集めると、そのレベルにおける所属するoctreeの位置を示します。たとえば5123まであるoctreeで、XYZの各々の9bit目を集めると、一番根元の8分木における、所属する子ノードを示します。従って、先ほどのXYZW10:10:10:2という格納方法の他に、X.10,Y.10,Z.10,X.9,Y.9,Z.9,X.8,Y.8,Z.8,…と各軸のbit位置ごとに格納しておくと、該当レベルにおける自分の所属する子ノードの位置が、シフトとマスクの演算で迅速にが分かるかも知れません。

Sparce Voxel Octreeの構築 – 2階層同時に構築する

OpenGL Insightsで行われていたSVOの構築は、1階層のOctreeを構築するのに、大きく分けて3回のスレッド起動が必要でした。L4からL0を構築するとすれば、計15回のパスが必要です。もうすこし効率化できないでしょうか。ためしに2レベルを同時に構築することを検討してみます。

  1. 分割する際のマーク処理を2階層分行うようにします。8bitあれば分割後さらに必要になる孫ノードの位置を記述することが可能になります。
    これはノードのどこかに、atomic_or命令でこの8bitを構築すれば可能です。
  2. 子ノードと孫ノードの確保は、8bitのフラグが0かどうかを判断して、0以外ならばbit数を数えて最大9個のノードを一気に確保してしまいます。
    その後、親ノードにアドレス格納して子ノードをリンクするところまで行っておきます。孫ノードは連続で確保されているのでアドレスを格納しません。
  3. 最後に孫ノードの数+1でスレッドを起動して、ひとつのスレッドは子ノードの初期化を行います。残りのスレッドは子ノードのアドレスと格納されている8bitのフラグから、自分が初期化するべき孫ノードの位置を計算して、子ノードにリンクして初期化します。孫ノードのアドレスはがアサインされていないスレッド(8bitのフラグの該当bitが0のスレッド)は、子ノードの該当ポインタをnullで初期化します。

この方法ならば計5回行わなければならなかったSVO構築パスを3回に減らすことが出来ます。末端であるL0の構築パスはすべてbrickを確保するので、どのみち別の処理が必要です。従って4回を2回にすると言ったほうが適切かもしれません。問題点は、ノード上に8bitのフラグを格納する場所を確保する必要があるのと、部分的にoctreeが構築されている状態ですと適用できません。8bitのフラグを格納する場所はともかくとして、部分的にSVOが構築されていて、そこに付け加える形でのSVO構築が必要ならば、オリジナルの実装のほうが良いと思います。

Sparce Voxel Octreeの構築 – 3レベル分の構築情報を中間生成する

L2のサイズは1283個です。L2ひとつあたりに所属するL0の数は最大64個です。L2ひとつあたり64bit確保すると16MByteのメモリが必要になります。この16MByteのバッファの各bitにL0の存在情報を記録するようにします。pixel shaderでvoxel fragmentを書き出す際に、この存在情報バッファにatomic_orを使って、構築が必要なvoxel位置のbitをマークするようにします。この存在情報バッファを基に各階層を構築します。

  1. L4の構築は、存在情報バッファの値を64個読み込むことで構築できます。
  2. L3の構築は、存在情報バッファの値を8個読み込むことで構築できます。
  3. L2の構築は、存在情報バッファの値が0かどうかを確認すれば構築できます。
  4. L1の構築は、存在情報バッファの値の該当8bitが0かどうかを確認すれば構築できます。
  5. L0の構築は、存在情報バッファの値の該当bitが0かどうかを確認すれば構築できます。

この場合で一番問題になりそうなのはL4の構築です。64*8byteで512byteものアクセスが必要になってしまいます。一方で、L4を事前に用意するとノードひとつあたり32Byteと仮定すれば1MByte必要になります。ノードの大きさによりますが、L4まで事前に用意しても問題ないかもしれません。やや強引ですが、そうすればL4構築の問題はなくなります。
L3の構築には総計256Kのスレッドを適切なブロックごとに起動すれば、存在情報バッファへのアクセスのキャッシュのヒット率も良くなるので、すばやく構築できると思われます。L2も同様に構築することが出来ます。
L1の構築には総計16Mのスレッドが必要です。L1ノードの確保はL2の構築と同時に行ってしまったほうが良いかもしれません。存在情報は既にあるので、L2構築時に必要なL1の個数は分かっています。従ってL2ノードと同時にL1ノードも連続したアドレスで確保してしまいます。L2にはL1のアドレスを記述しませんが、L2のアドレス自身から確保されたL1のアドレスを知ることが出来ます。

L0の構築の際には、L2のブロックごとに連続したbrick-poolを確保できるのが一番好ましいと思われます。空間的に近いvoxelがbrick-pool内でも近接していれば、voxelの読み出しや、書き換え時にキャッシュヒットを期待することが出来ます。したがってL2の構築後に、該当L2以下で必要な数のbrickを確保して、L2のノードのどこかに先頭のインデックスを記録しておきます。各々が使用するL0のインデックスは、共有しているL2存在情報のbitを数えることで相対オフセットを計算することが出来るはずです。bitを数える処理が煩雑そうなので、group shared buffer内にL2ブロックごとにカウンターを用意し、atomic_add命令で相対インデックスを作った方が良いかもしれません。

この処理をDirectXのComputeShaderで行うならば、

  1. L3の確保~L0確保まで
    L2の数でスレッド起動。L3ごとにL2以下のノード数を調べるためのカウンタを用意する。
    (例:256スレッドで32個のL3の処理を行う場合は、groupshared uintを32個確保する)
    担当L2ごとに存在情報テーブルから64Bitを8bitごとに非0かをチェックする。
    これで必要なL2とL1のノードの数が分かる。これをカウンタにInterlockedAddで加算する。

    GroupMemoryBarrier

    各L2グループの先頭のスレッドのみ動作させる。
    カウンタの値より、必要なL3とL2とL1の数が分かるので、node-poolより連続で確保。
    L4にL3をリンクして、L3の最低限の初期化を行う。
    先ほどのgourpshared uintのカウンタに、L2以下で使用できるnode-poolの先頭のインデックスを書き込む。

    GroupMemoryBarrier

    再びL2ノードごとに動作させる。
    L2以降で必要なノード数は分かっているので、groupsharedのカウンタにInterlockedAddを行い、L2とL1のノードを確保する。
    L2を初期化。
    存在情報テーブルから該当L2の64Bitのbit数を数える。(countbits()命令)
    担当のL2以下で必要なL0の数が分かるので、brick-poolより連続で確保。
    L2のどこかに確保したbrickの先頭アドレスを保存。

  2. L1の初期化とL0リンク
    L1の数でスレッドを起動。該当するL2ごとに相対アドレス生成用のカウンタを二つ用意する。
    (例:256スレッドで32個のL2の処理を行う場合は、groupshared のuintを64個確保する)
    node-poolからのL1の確保は済んでいる。
    L1を確保する際は、相対アドレス生成用のカウンタ[0]をInterlockedAddしてL2のアドレスからオフセットさせる。
    L2にL1をリンクして、L1のノード初期化を行う。

    L0のリンク処理。L1が担当する8bit分のL0存在情報からL0をリンクする。
    L0を確保する際は相対アドレス生成用のカウンタ[1]をInterlockedAddして相対アドレスを計算し、L2が保持しているbrickの先頭アドレスに加算してL0のアドレスとする。
    L0をL1にリンクする。
    L0の初期化は3Dテクスチャのクリアで行うのでここでは行わない。(行うと極めて非効率)

こんな感じでしょうか。L3の構築はL2構築の途中で行うようにしてみました。Computeと中間生成バッファを使用しますが、をおそらく論文の実装よりは早くなると思います。

References
Interactive Indirect Illumination Using Voxel Cone Tracing[Cyril et al. PG2011]
OpenGL Insights

OctreeにVoxel化した情報をストアする」への1件のフィードバック

  1. 名無しさんあじゃじゃしたー/通りすがり

    この項に限らず他の投稿も含め、ありがたいです。大変参考になります

    返信

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中