自作3D描画ライブラリ(未完成)で工夫した点 #GPU

概要

最近3D描画&物理エンジンを作成しているのですが、要点をまとめます。

作成したライブラリは Cells というもので、四面体分割を用いてシミュレーション用途に耐えうる正確性と、リアルタイム描画に耐えうる高速性の両立を図ります。(編集時点で未完成、あと依然超重い)

Cells の特徴は以下の通り。

光線を歪曲させることができる
屈折の表現が正確
非ユークリッド空間を自然に扱える
四次元へ接続できる(多分)
メモリ外の内容(インターネット上の動画像など)を自然に導入できる
Unityやその他のツールと一応接続できる
物体が十分に静止していれば当たり判定が高速である
すり抜けが起きない
物体が原理的に交差・貫通できない
非凸面多面体は凸面多面体に分割して扱う必要がある
流体力学を自然に導入できる

これらは凡そ、面(ポリゴン)ではなく立体(四面体)を描画するというコンセプトから来ています。
これ故、空間に対して描画したり、空間内の光線を操作したりすることが容易になります。

空間の性質を扱うことができるのでシミュレーションとして使いやすいですが、その反面描画処理が最適化し難いので、これを克服できるよう努めました。(結果としてはそんなに速くはありません)

進捗

構造は全部できた。後実装だけだけど、量がやばい。
少しづつ実装頑張ります。

手順

実装済みでテストやったところもあるけど、八割予定で書いてるから今後変わるかも。

1. 四面体分割

Cells では、空間が四面体の集合として扱われます。

四面体以外の物体は何らかの形で四面体に分ける必要があります。デフォルトでは自動でドロネー四面体分割が行われて点群の凸包のみが扱われるので、非凸多面体を扱うときは適宜分割してやる必要があります。

ただ、身の回りの人工物をきちんと観察してみると、その部品一つ一つは凸包として扱っても十分であることが多いように思うので、要はきちんと部品に分けて制作すれば大丈夫です。

世の中には既存の頂点だけでは四面体に分割できない立体というものも存在します(例えば三角柱のそれぞれの矩形面に同じ向きの対角線で切込みを入れ、上面の三角形を少し捻った立体)が、それらは諦めてどこかに頂点を追加して分割して下さい。

2. カメラの設置

カメラも四面体で出来ているので、他の立体と同じように用意しておきます。

五胞体で出来ているカメラもあって、三次元空間をそのまま写すことが出来ますが、全CPU動作なので死ぬ。

遠赤外線カメラもあるけど、全CPU動作なので死ぬ。

紫外線カメラもあるけど、紫外線のテクスチャって太陽の画像ぐらいしかなくって使えない。

3. 四面体の接続

分割されてできた四面体たちを、なんとかしてつなぎ合わせる必要があります。

物理演算ができる空間にあれば、空気や真空が物理エンジンの効果で勝手に空間を満たしてくれますが、そうでない場合はそれぞれ自分で繋げる必要があります。非ユークリッド空間に空気や電磁場が存在するとは確定できないからね。繋げ方わからないし。

ちなみに空気や真空を置かない場合でも、磁場や電場、重力場を設定することもできるので、なにかに使えるかも。五胞体でできた磁場カメラや電場カメラもあります。

var field = EuclidElectromagneticField.Get();
var obj1 = Tetrahedron.Empty((1, 0, 0.5), color: Color.White);
var obj2 = Tetrahedron.Empty((1, 0, -0.5), color: Color.Red);
var cam = Camera.Get((0, 0, 0), number: 0);
var air = Air.Default;
Join((CoElectromagneticField)field, (CoPolyhedron)obj1);
Join((CoElectromagneticField)field, (CoPolyhedron)obj2);
Join((CoElectromagneticField)field, (CoPolyhedron)cam);
Join((CoElectromagneticField)field, (CoAir)air);

4. 四面体の調整

各フレームごとに、必要があれば四面体の高さが再計算されます。というか、四面体が動かされるごとに再計算されます。

高さがなくなったら衝突が起きているということなので抗力に関する処理が呼び出され、元の四面体は消滅します。
衝突した先が空気だったり壊れやすかった場合は、相手が勝手に分裂(空気やヒッグス場の場合はドロネー分割、固体の場合は相手による)します。

液体の場合は体積も計算され、差分が排出されたり吸収されたりします。
処理できなかった場合は抗力を働かせたり、自己分裂して新たな液相や真空を生成したりしますが、重いので液体は扱わないようにしよう。

5. 描画

カメラを時間上に置くと、カメラが描画要請を発して、要請がイテレーターとなって各四面体を描画します。

カメラを時間に置かないといけないのは、それぞれ四面体は本当にただの空間上の物体なので、デフォルトだと時間に従って動くことが出来ないからです。

四面体に分割された空間はつまり辺が四つのグラフなので、要請がこれをイテレートします。
要請のあった三角形に含まれない頂点の位置によってこの要請が何個の隣接する(グラフにおける)頂点(つまり四面体(ややこしい))に伝播するかが決定されます。

四面体が各隣接する四面体からの描画結果をまとめるので、四面体の一存でその先の空間を別空間にするとか、非ユークリッドにするとかを決定できます。
なのでどこでもドアとか四次元ポケットとかも、四面体がそうしようと思ったら可能なのです。

var window = Window.Get();
var time = Time.Current;
Join((CoGraphicArea)field, (CoCamera)cam);
Join((CoTime)time, (CoCamera)cam);

最適化

処理の集中

実際に四面体それぞれに描画処理を任せてたら最適化も何もあったもんじゃないので、四面体は仮想的なビットに対する操作のみを指定して、これをカメラがまとめて処理するようになってます。

実際に四面体の裁量で行えることは、

描画に必要なデータ(どの四面体に要請を伝播させるか)の決定。
色のテクスチャによる変換。

で、テクスチャは予め環境に登録しておく必要があります。

四面体に渡されるデータはRenderingOperationの形で渡されるのでこれに定義されている演算子を駆使してデータを加工します。

たとえば画像を乗算するならこんな感じ。

using RO = RenderingOperation;
RO Render(RO ro)
{
    var tex = StaticTexture("<<path>>");
    ro[..] = ro[..] * tex[..];
}

これが処理を示すコードとツリー構造に変換され、カメラに集約されます。

レイヤー生成

カメラに集められた四面体の処理内容は、処理内容とデータが異なったノードからなる木構造になるので、処理内容ごとにレイヤーを生成し、データをそれぞれのレイヤー向けに配列した後これをまるごとGPUに転写して処理します。

テクスチャは読み込む際に合成して一枚にするかどうかを選択できます。あとMetalやOpenGL向けに勝手にフォーマット変換されるほか、ミップマップも自動で生成します。

ここで、四面体の中に鏡面反射などを行うものがあるとグラフが閉じてしまって無限ループになるんじゃないかという懸念だったり、そもそもうまくレイヤーに分割できないんじゃないかという懸念があるわけですが、反射によって再び四面体を参照する必要がある場合、つまり演算の木構造の子が親を参照しなければならない場合、親のコピーが自身の孫となることでこれを解決します。
木の深さには制限があるので無限ループすることはありません。

また、二つの四面体が一つの四面体を子として参照してしまう自体も想定されるのですが、この場合も亦、子のコピーが扱われるのでやはり大丈夫です。

つまり意地でも木構造が維持されるということです。

これによって四面体は三角形として描画され、先の強制維持木構造によって四面体の描画領域は分割されているので、出力画像は膨大な三角形の集合ということになります。

各三角形を強制的に別の色に染めるとこんな感じになります。

最後に

早く完成させたい。