いろいろな近傍探索

sphを実装するときにいろいろな近傍探索の方法を調べたので、知ったものをまとめておきます。

１．グリッドサーチ

空間をグリッドに区切って高速化をします。

https://qiita.com/kodai100/items/d1ddb3f86ba5dccccf9f

こちらで説明されています。

２．Cell-Linked-List

正式名称不明。CompactHashと調べたほうがいいかもしれません。

モートンオーダーを使用したりして１からさらに高速化します。

論文https://cg.informatik.uni-freiburg.de/publications/2011_CGF_dataStructuresSPH.pdf

３．Compressed Neighbor List

こちらも正式名称不明。論文の名前をそのままのっけてみました。

論文https://cg.informatik.uni-freiburg.de/publications/2019_CGF_CompressedNeighbors.pdf

正直２との違いがわかりません。ただ新しいです。2019年！

２はモートンオーダーを使う上にCompactHashingたる操作をしていますが、１にモートンオーダーを使うだけでも高速化になるのではないかと思います。

１，２，３いずれもソートをする必要があります。

せっかくなのでソートもまとめてみます。ただし並列化できるもののみです。

１．バイトニックソート(BitonicSort)

近傍探索では１番人気です。調べるだけでたくさん情報が出てきます。

２．基数ソート(RadixSort)

論文では人気なイメージです。あくまでもイメージ

３．マージソート(MargeSort)

CPUのイメージがありましたが、並列化できるようです。たぶん

バイトニックソートは最適化が施された実装

https://github.com/toropippi/BitonicSort_ComputeShader

があるので、何も考えずにバイトニックソートを使うのもありだと思います。

言い忘れていましたがUnityで実装してます。

https://arxiv.org/ftp/arxiv/papers/1511/1511.03404.pdf

で速度が比較されていますが、読みとり方に自信がないので内容には触れないでおきます。