kdtree - 効率的なストレージのためのボクセル データのリパック

Question

3D ボクセル データがあり、メモリ効率と高速アクセスのために再パッケージ化したいと考えています。データは、セルごとに 1 つの整数値の通常の octree で生成されます。残念ながらデータはまばらではありませんが、同じ値を持つセルは接続されているはずです。

Example for one slice:
[11122]
[11223]
[12222]
[44444]

私の現在の考えは、kD ツリーを使用することです。できれば左にバランスがとれていますが、これを生成するための効率的なアルゴリズムがあるかどうかはわかりません。私はいくつかのアイデアを持っていますが、これがすでにアルゴリズムを確立している問題の1つであるか、少なくともグーグルで検索できる名前であることを望んでいました.

Answer 1

もう 1 つのリンク: http://www.openvdb.org/。なぜ私は質問をした後にこれを見つけたのですか？スーパーマーケットで何かを頼んだのに、隣に立っていることに気付くようなものです。

ボクセル ボリュームを 2D 平面のスタックに変換し、各平面は値が次に高い平面に変化する時点を保存します。そうすれば、ボクセル データは垂直方向にのみ圧縮されますが、今のところ「十分」のようです。時間があれば、他のデータ構造の数値 (スペース要件とパフォーマンス) を計算します。