Groups

Chapter 13

The Ray Tracer Challenge: A Test-Driven Guide to Your First 3D Renderer (Pragmatic Bookshelf)

シーングラフを作る。

Tree 構造

シーングラフといっても処理を複雑にしないよう、実際には Graph ではなく Tree 構造を用いる。今回の目的に合致する Tree は

• 各 Node が持つ情報は Shape によって異なる
• root を除く各 Node は親 Node へのリンクを持つ
• Tree を構成する Node は任意の数の子 Node を持つ
• Node に対して子 Node(sub tree) を加えることが可能

となる。

これを Rust で実現することを考える。

Rust で Tree を作るとなると、Node に持たせる情報は Generics を使ってユーザが決められるようにすることが多い。全 Node が同一の情報を持つのであれば問題ないが、今回のように、この Node は Sphere, あの Node は Cylinder といったように Node ごとに持たせる情報を変えたい場合には使えない。もちろん、enum を使えば可能ではあるが、その場合全ての Node のサイズがとり得る最大のものになってしまい、大規模な Tree には向かない。

なので、今回は Node のメンバに trait object である Shape を持たせることにした。trait object はコンパイル時にサイズがわからないので boxing する。

    shape: Box<dyn Shape>,

他、Shape の種類によらず共通して持つ必要のある情報は Node に持たせる。具体的には Transform と親 Node へのリンクがそれにあたる。

結果として Node のメンバは以下のようになった。

pub struct Node {
    /// 親 Node
    parent: Option<NonNull<Node>>,
    /// 親 Node の座標系への変換
    transform: Transform,
    /// 本体
    shape: Box<dyn Shape>,
}

ここで親 Node へのリンクである parent はポインタを使用する。

親 Node へのリンク

Rust での Tree 構造の実現方法を調べると簡単なのは親 Node へのリンクを持たないものになる。常に root からトラバースするのであれば、親 Node へのリンクも不要。そうでない場合に親 Node へのリンクを持つようにすると、ownership まわりが複雑になる。一番自然なのは親 Node が子 Node を所有する。となると、子 Node から 親 Node へのリンクは循環参照を避けるためにも ownership を持たない形にしなくてはならない。

ownership を持たない参照を実現するために最初は Weak を使ってみたけれど、そのためには Rc::downgrade() で Weak を作れるよう、Node を Rc で包まなくてはならない。また Rc だと owner が複数ある可能性からコンパイル時に borrow check が行えず、そのままでは read only になってしまう。それを避けようとするとさらに RefCell を使うことになり、Rc<RefCell<Node>> とややこしい。

これ自体は Rust のイディオムのようなものだから我慢するという選択肢もあるけれど、親 Node へのリンクが欲しいだけの割にどうにも大仰な感じがする。root 以外の Node の owner は 親 Node のみという点は変わらないわけだし、子 Node が親 Node より長生きしてリンクが無効になることもない。なので、代わりにポインタを使った方がすっきり書けそうな感じがした。C や C++ に毒されすぎと言われそうな気もするが。

親 Node へのリンクにポインタを使うのであれば、親 Node のアドレスが変わってしまっては困る。なので Node を直接 move できないようにする。具体的には常に Box<Node> の形で使うようにする。これなら Node 自体は heap に確保され Box を move しても Node のアドレスは変わらない。というわけで、new() の時点で boxing してしまう。

    pub fn new(shape: Box<dyn Shape>) -> Box<Self> {
        Box::new(Node {
            parent: None,
            transform: Transform::identity(),
            shape,
        })
    }

Node のメンバは private だから外で直接 Node を作ることはできず、必ず new() で作ることになり、boxing されている。

問題は Node を作ってしまうと、 shape が元々何であったか(Sphere, Cube, etc)がわからなくなってしまい、固有の操作が行えなくなってしまうことだが、今回は一部例外を除き Node を作る前に設定を終えておくことで対処する。

子 Node の追加

先に挙げた Node は子 Node を保持するメンバを持っていない。これは Sphere 等は常に Leaf Node で子 Node を持たないことによる。そこで子 Node を持つ Shape として別途 Group を用意する。

pub struct Group {
    /// 子 Node
    children: Vec<Box<Node>>,
}

何だか Vec で heap を使っているのに、更に Box まで使っていると無駄っぽいが、子 Node に加える前後で Node のアドレスを変えないようにするためなので我慢する。

子 Node を加えるには add_child() を使用するが、これは Group のメソッドではなく Shape に用意する。これは Node から add_child() できるようにするため。そうしないと子 Node に親 Node のポインタをセットできない。

    pub fn add_child(&mut self, mut child: Box<Node>) {
        child.parent = NonNull::new(&mut *self);
        self.shape.add_child(child);
    }

なので、Shape の add_child() を直接呼ぶことはない。とはいえ、現在 Group 以外の Node に add_child() を呼ぶと panic してしまうため、Error を返すくらいはしたい。

その他

Node に Transform 移した際、transform_mut() で新しい Transform をセットするのではなく、 set_transform() で設定するようにした。前者は &mut な Transform を得るのに対し、後者はセットする Transform を引数にとる。
こうした理由は Transform をセットしたタイミングに合わせて他の処理をする場合に備えるため。

例えば、現在は法線ベクトルを求める normal_at() の中で行う World -> local 変換は各 Node の変換を root に向かってたどることで実現しているが、毎回これでは効率が悪い。対応策として各 Node には World 変換をキャッシュとして持たせることが考えられるが、Transform セットのタイミングでこのキャッシュは invalid なものになってしまう。となるとキャッシュの更新なり、キャッシュが無効である旨を示すフラグのセットなりを行う必要がある。transform_mut() ではそれができないため set 用のメソッドに変更した。

Rust で hoge というメンバに対する getter, setter は hoge() と hoge_mut() とすることが多いようだが、上記要求には対応できない。こうしたときに Rust ならこうするというパターンがあるのだろうか。
hoge は set_hoge()、hogera は hogera_mut() を使うなんて面倒で仕方ない。

雑感

Node の実装方針が本当にこれで良かったのか今でも自信がない。Rust による Tree の実装を色々と見てみたが、parent へのリンクを持たないとか、Node は全て同一の構造とか、Node は root からのみ追加可能で中間 Node に対して部分木を追加しないとか、子 Node の数は固定とか、どれも限定的な使用法を想定しているものばかりで、これぞ決定版と思えるものにはついぞめぐり会えなかった。そのため、今回の用途に適用しようとすると、そのままではどれも使えなかった。

他にも Box<Node> とそのメンバである Box<Shape> はライフサイクルが一致するため、別々に heap の allocation をするのではなく、一回の allocation で両方合わせたサイズの heap を確保して Node と Shape に分配したいと思ってしまうが、Rust ではどのようにすれば良いのか分からない。

賢い人ならこの程度のことはすぐに解決できるのかもしれないが、ちょっと自分には無理だった。Rust は頭の良い人しか使ってはいけない言語なのかも。Haskell みたいに。

印象として実行時に自由な編集を許すタイプのプログラムを Rust で作ろうとすると、多大な困難を伴う感じがする。そういった意味では今回の raytracer なんてかわいいものだが、3D CG のモデリングツールを Rust で作るといったときにはどんな感じになるのだろう。 他、自由に構造をいじれるグラフ構造の実装なんて考えたくもない。Typed Arena だと全 Node の lifetime が同じになってしまうので、グラフの一部を削除とかはしづらいし。