N 分木表現をデータサイズ小さくシリアライズしたい...
たとえば二分木(binary tree)ですと, 木構造を配列で表現は容易です.
implicit にする(木構造の情報の配列を持たない)ことも可能です.
レイトレでの BVH データ構造によく使われていました(~2015 年くらいまで. 今でも主流なんじゃろか)
implicit で, 子のノード数が固定な N 分木(e.g. 4 分木)などにも適用することができますが, 使われないノードが増えるなどして無駄が多くなります.
木構造を単純な 1D 配列にすることで, シリアライズや GPU での処理などがやりやすくなります.
しかし複数の子で構成される N 分木(多分木. たぶん... 木? ではない)ですとどうしたらよいでしょうか.
二重連鎖木
二重連鎖木というのがあります(child-sibling tree)など呼び名はさまざまのようです.
ただあんまり実生活や学校のデータ構造授業では取り扱われない... カモ?
これにより木構造を二分木で表現することができます.
配列表現
pxrUSD の USDC(バイナリ表現)で使っていて知りました.
流石に implicit に表現は無理ですが, child, sibling のビットと, ジャンプオフセット配列(次のノードへのオフセット)があれば木構造を復元できます!
pxrUSD のコードだとわかりにくい感がありますので, TinyUSDZ のコードを参考にするとよいでしょうか.
(child, sibling ビットは負の値で表現)
木構造から配列へのコンバートもそれほど難しくはありません. みなさんも考えてみてくださいネ.