ポリゴンレンダラ - その2

こないだやり始めたやつの続き。今回ばかりは実行効率重視なので実装にも注意しながらやらないといけない。今日は前回決めた座標系で与えられるポリゴンの頂点座標を効率的に保持する方法について。

3  3次元モデルのデータ構造

まず、座標変換なんかのごちゃごちゃした話に突っ込む前に、モデルのデータ構造を考えておく。

もっとも簡単なデータ構造は、頂点の座標を与えた面でモデルを構成するというものである。

面もあとのために法線ベクトルが計算できないといけないので、単純な三角形が最小単位になっているのが簡単でいい。しかし、そうやって複雑な面形状を表現しようとすると、複数の三角形の頂点がまったく同じ座標になる、ということが起こる。そうでないと面が連続しないので当たり前なんだけど、さっきの座標変換を考えると重複が多くて機械的にやると無駄な計算をすることになる。

今回はそれなりに実行効率を考えて作りたい。ということでちょっと工夫する。

といってもまたMathematicaのパクリをやるんだけど、Mathematicaには6.0からGraphicsComplexというオブジェクトが追加された。それは

GraphicsComplex[{pt1,pt2,...},data]

というような構造をしている。引数のひとつ目は座標の値が並んでいる。その後ろにはMathematicaのグラフィクスプリミティブが入るんだけど、そのプリミティブ、たとえばPolygonやSphereといったものの本来座標が入る位置に、整数が指定される。

例えば三角形をPolygonで表現すると

Polygon[{{0.0, 0.0, 0.0}, {1.0, 0.0, 0.0}, {0.0, 0.0, 1.0}}]

などとなるけど、GraphicsComplexの中では

GraphicsComplex[{{0.0, 0.0, 0.0}, {1.0, 0.0, 0.0}, {0.0, 0.0, 1.0}},Polygon[{1,2,3}]]

となって、このふたつは同じものを表す。つまり、GraphicsComplexの中ではプリミティブは最初に並んでいる座標のインデクス値を保持するように変更される。これだけでは何がうれしいのかわからないけど、ふたつの接している三角形を考える。

ひとつの表現は単にふたつをリストにする。

{Polygon[{{0.0, 0.0, 0.0}, {1.0, 0.0, 0.0}, {0.0, 0.0, 1.0}}],
   Polygon[{{0.0, 0.0, 1.0}, {1.0, 0.0, 0.0}, {1.0, 0.0, 1.0}}]}

あるいはPolygonオブジェクトはもう少し融通が利いて

Polygon[{{{0.0, 0.0, 0.0}, {1.0, 0.0, 0.0}, {0.0, 0.0, 1.0}},
           {{0.0, 0.0, 1.0}, {1.0, 0.0, 0.0}, {1.0, 0.0, 1.0}}}]

としてもかまわない。これがGraphicsComplexでは

GraphicsComplex[{{0.0, 0.0, 0.0}, {1.0, 0.0, 0.0}, {0.0, 0.0, 1.0}, {1.0, 0.0, 1.0}},
    {Polygon[{1,2,3}], Polygon[{3,2,4}]}]

となって、頂点座標の重複が避けられる。

最初みたときは、なんだかMathematicaらしくない形式だな、と思った。例えば座標のインデクス値はもちろん整数でなければならず、たとえ小数以下が0でも実数が入るとエラーを起こして描画されない。動作が型に依存して、あまり美しくない。

しかし、この形式は描画の高速化にはけっこう貢献するはずである。PlotやPlot3Dなどを使って関数をプロットする場合は5.0ではPlotがプリミティブに分解して描画していたが、6.0からはプリミティブを並べて描画するのではなく、GraphicsComplexオブジェクトが生成されるようになった。

実はこういうフラットな形式（ただ単に座標の値が1次元に並んでいるだけ）は、人間が見たり書いたりするのは苦痛だけど、実装のとき高速化できる可能性がある。たとえば、ずっとまえFFTのルーチンの速さにほんとかよ、と思ったvDSPの関数群が使える可能性がある。それによってどのくらい速くなるかは、実装のときのお楽しみ。

さて、どちらかといえばGraphicsComplexはユーザが手で書く、というよりはそういったプロット関数に自動生成させるのが普通で、GraphicsComplexをプリミティブの集合に変換はできるけど、プリミティブの集合をGraphicsComplexに変換する手段は提供されていない（一般のプリミティブの集合から共通する座標を取り出すのは組み合わせ爆発が起こる可能性があるからかな）。

ということで今回はこれをパクろう。座標変換は最初の座標列に対して行うだけでいい。これをどうObjective-Cのオブジェクトに展開するか、というのはもう少し詳細を詰め手からにしよう。オブジェクト設計に入るにはまだちょっと早い。

Mathematicaの場合、使えるプリミティブに制限はないのでかんたんだけど、今回のようなObjective-Cで実装しよう、などというときにはそれでは荷が重すぎる。プリミティブはポリゴンだけ、それも三角形か、すべての頂点が同一平面内にあることが保証された多角形だけにしよう。ひとつのGraphicsComplexの中で色や反射率を変えることはせず、違う色にしたければ別のGraphicsComplexを並列することにする。そうするとMathematicaの仕様とは違ってしまう（Mathematicaはもっと複雑な構造を許している）けど。

Mathematicaを使わずにGraphicsComplexを生成するのはどうするか、という問題はあるけど、とりあえず最初はMathematicaを使って作ることにする。本来ならBlenderやなんかのデータとかVRMLとかを読み込めるようにするべきなんだろうけど、そんなことしてたら他に何もできなくなってしまうし、だいいちそんな大袈裟なものではないので、またあとで考えよう。