1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

N 分木(多分木)を二重連鎖木にしてオフセット配列表現するメモ

Last updated at Posted at 2022-11-12

N 分木表現をデータサイズ小さくシリアライズしたい...

たとえば二分木(binary tree)ですと, 木構造を配列で表現は容易です.

implicit にする(木構造の情報の配列を持たない)ことも可能です.
レイトレでの BVH データ構造によく使われていました(~2015 年くらいまで. 今でも主流なんじゃろか)
implicit で, 子のノード数が固定な N 分木(e.g. 4 分木)などにも適用することができますが, 使われないノードが増えるなどして無駄が多くなります.

木構造を単純な 1D 配列にすることで, シリアライズや GPU での処理などがやりやすくなります.

しかし複数の子で構成される N 分木(多分木. たぶん... 木? :thinking: ではない)ですとどうしたらよいでしょうか.

二重連鎖木

二重連鎖木というのがあります(child-sibling tree)など呼び名はさまざまのようです.

ただあんまり実生活や学校のデータ構造授業では取り扱われない... カモ?

これにより木構造を二分木で表現することができます.

配列表現

pxrUSD の USDC(バイナリ表現)で使っていて知りました.

流石に implicit に表現は無理ですが, child, sibling のビットと, ジャンプオフセット配列(次のノードへのオフセット)があれば木構造を復元できます!

pxrUSD のコードだとわかりにくい感がありますので, TinyUSDZ のコードを参考にするとよいでしょうか.

(child, sibling ビットは負の値で表現)

木構造から配列へのコンバートもそれほど難しくはありません. みなさんも考えてみてくださいネ.

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?