[PureECS] 自作CollisionSystemに使えそうなリンク集
執筆時点でPureECSにはまだCollisionSystemは搭載されていません。Collisionを利用するにはHybridECSを利用することになりますが、作っているプロジェクトがPureECSを利用するものなので、いろいろ調査してみました。今のところ自作する方針でいますが、もし同じようなことを考えている人がいれば、つまらないものですが共有できればと思って記事にしてみます。理解不足、更新情報やほかの研究で何かありましたら、コメントいただけると非常に助かります。
ある程度まとまった先行研究例
以下のサンプルはCPUの並列処理を利用したものとなっています。もしGPUを利用したCollisionSystemを構築するならばGPUとCPU間のデータ輸送速度を考慮すべきだ、とも作者は指摘しています。実際に作ってみないことには何も言えませんが、相当量のEntityを扱うにはGPUで処理するほうがパフォーマンスが発揮できそうな気がします。
Physics in Pure ECS(PhilSA)
https://forum.unity.com/threads/sources-available-physics-in-pure-ecs.531716/
※執筆時点でMeshInstanceRendererがUnity側で機能していない(廃止？)ためサンプルを実行しても球体が描写されません。開発者のアップデートを待つか、自作のレンダリングシステムを実装する必要があります。
以下のサンプルはPureECSの基本的な点にも触れられているので、ECSを始めたばかりでも理解しやすいと思います。Collsion自体はもっとも簡単な球体を採用しているので拡張性はあまりないでしょう。しかしやりたいことはこういうことです。
【Unity】PureECSの衝突判定周りについて解説してみる(@mao_ 2018年10月12日)
https://qiita.com/mao_/items/ad8a09a9c6403a2e84cf
計算量を削減する空間分割法
空間分割による計算量の節約は避けられないことでしょう。多くの文献がスタート地点にしていることは“総当たりによる計算”は重過ぎるという点です。【衝突しないことが自明である計算過程はスキップする】をいかに効率よく行うかを考えた結果として空間分割が提唱されてきたわけです。空間分割はレンダラ関係で登場する機会が多いのですが、おそらくCollisionSystemに組み込むことでも恩恵を得られることでしょう。
さて、空間分割の方法ですが、最適解は存在しません。OctreeやKD-Treeといろいろな方法が考案されていますが、それぞれ短所長所が指摘されています。自身のプロジェクトが求めるパフォーマンスを勘案し、採用する空間分割法を決める必要があります。
BVHのはなし(Shinji Ogaki, 24/Dec/2018)
https://shinjiogaki.github.io/bvh/
以下はレイトレーシング関係ですが、空間分割について参考になる文献です。
実践QBVH(Shuichi Hayashi, Sep 1, 2013)
https://www.slideshare.net/ssuser2848d3/qbv
レイトレ空間構造入門(Toru Matsuoka, Sep 1, 2013)
https://www.slideshare.net/torumatsuoka148/ss-25793897
衝突判定でつかえるかもしれないアルゴリズム
衝突判定にどんなアルゴリズムを採用するかは良く考えたほうがいいでしょう。円や球体しか登場しないという前提を作ればかなり安価にシステムを構築できると思いますが、そのような前提はゲーム開発において実現可能範囲を自ら狭めてしまいます。一方で登場するコライダー形状を増やしすぎると計算過程が複雑になりすぎる恐れもあります（球とカプセルの衝突、カプセルと矩形の衝突、球と球の衝突...登場する形状N個を線形探索して衝突計算を切り替える必要がある←ちょっと極端だと思いますが）。
このリンク集を作成している時点で、私自身はどういう形で衝突検出を行うかはまったく答えが出せていません。しかし考慮しておいたほうがいい点は以下の通りでしょう。
１．コライダー形状を限定するか、もしくはどんなコライダー形状でも機能するようにするか（←処理速度とトレードオフになるでしょう）
２．並列処理に持ち込みやすいか
３．どこまでの精度低下を許容できるか
自分はPureECSにおいてGPUによる衝突判定を取らざる負えない状況にあるため、２が最重要となっています。JobSystemだけでの運用を考えたとしても重要性は変わらないでしょう。この並列処理に持ち込みやすいを言い換えると“参照を取らない”ということと同じです。参照を取れないことで問題になってくることはいくつか想像されます。例えば、シーンに存在するMonoBehavierなオブジェクトとECSオブジェクトの衝突判定、とかでしょうか（←MonoBehavierなオブジェクトのレイヤー情報、衝突面法線、衝突ワールド座標などにアクセスできない、もしくはこれらのデータを値としてメソッドに渡しておく必要がある）。
ゲームつくろー！< 衝突判定編 (○×（まるぺけ）つくろーどっとコム)
http://marupeke296.com/COL_main.html
※おそらくもっとも網羅的にあたり判定に説明しています。2D3Dともに解説があり、単純なコライダー形状の衝突について理解しやすい文献です。
情報メディア実験 物理エンジンを使ったアプリケーション開発：GJKアルゴリズム(Makoto Fujisawa)
http://slis.tsukuba.ac.jp/~fujisawa.makoto.fu/lecture/iml/text/gjk.html
GJKアルゴリズムについて調べたことのまとめ(@eisoku9618 2018年11月19日)
https://qiita.com/eisoku9618/items/5460de2cb5fd812561bf
GJK アルゴリズム 説明 - ぽんこつでばいす(あるけ 2008年02月01日)
http://angra.blog31.fc2.com/blog-entry-115.html
※上記のGJKアルゴリズムの後にJohnson's Distanceというアルゴリズムでめり込み具合を算出できるようです。反発具合の再現に利用できるかもしれません。
GJKアルゴリズムのデメリット（←作ってみないことにはわからないので、あくまで予想です）
GJKアルゴリズムは単体(simplex)を辿って衝突判定を行うため、どんなコライダー形状でも適用できるというメリットがあります。一方で考えられるデメリットも存在します。何度も言いますが作ってみないことにはわかりませんので、あくまで予想です。
１．壁や地面など大きいコライダーとの衝突判定はうまく行えない可能性
２．コライダー形状を表す情報はコライダーによってサイズが異なる
３．GPUに渡す情報量が多くなりすぎる
１はどちらかというと空間分割の問題点かもしれません。壁や地面など範囲の大きいコライダーは複数のコライダーに接している可能性があり、必ずしも接しているコライダーの原点が最近点とは限りません。原点距離によって空間分割を行っていると、接しているにも関わらず衝突計算がスキップされてしまうという事態が起こります。場合によっては壁や地面などの衝突判定は別システムにするべきかもしれません。
２はバッファサイズの設定が煩雑になるリスクを抱えているでしょう。GPUには固定長配列を渡す必要があり、(対象Entity)*(コライダー形状のVector3配列)の長さをあらかじめバッファとして確保する必要があります。 執筆しながら気が付きましたが、おそらく杞憂です。対象Entityのpositionさえわかればコライダーの頂点座標は簡単に計算できます。GPU側でコライダーの頂点座標を計算・プールしておけば問題ないでしょう。つまりGPUに最低限渡す必要がありそうなものは、①Entityのposition ②コライダーの頂点座標配列 ③衝突判定を行う相手Entityのposition ④当たったか当たってないかを記録するバッファ(←GPUからデータが戻ってきた際に利用) 、といった具合になりそうです。
３は冒頭で紹介したPhilSA氏が指摘しているようにデータ輸送速度の問題にも絡んでくるでしょう。またGPUで利用できる形に配列を変換するコストがどこかで生じる可能性もあります。
何度も言いますが、作ってみないことにはなんとも言えないことが多いです。作りつつ検証すべき点が多いでしょう。ちょっとしたプランをメモのような形で文字にしてみましたが、考えがすっきりして何となく自作CollisionSystemの方針が見えてきたように思います。
さて、....作るか。