最適化
以前のプログラムでは点が多すぎて処理がかなり重かったため、近くにある点などを排除して、データの最適化を行いました。
ちょっとスカスカになってしまいましたが、フレームレートは少し回復しました。
最適化の方法は、４次元の格子を用意してそれぞれの点がどのグリットの中に入っているのかを調べます。そして、既にそのグリットの中に点があったら、それ以上点を保存しないように、つまり一つのグリットに一つの点しか入らないようにします。
これが意外に難しかったです。なぜかと言うと、各座標100個のグリットの配列を取ったとしても２次元の場合なら100×100で10000個の配列ですみますが、４次元の場合だと実に100の４乗、１億=100Mもの配列を必要とします。もしint(４バイト)なんかで取ってしまうと全部で400Mバイトの配列になります。このぐらいならまだ最近のマシンだと大丈夫かもしれませんが、さらに200個とか取ろうとすると200^4=16億=1.6G、intだと6.4Gバイトです。
これを解決するために構造体のビットフィールドというものを使いました。具体的には
typedef struct
{
unsigned b0 : 1;
unsigned b1 : 1;
：
：
unsigned b30 : 1;
unsigned b31 : 1;
} BIT32;
このような構造体を用意し、これを使って配列を組むことで400Mバイトの配列でもその32倍の数の配列を確保できます。つまり100^4が800^4まで多くなるのです。もちろんこれはビットなので0か1しか保存できませんが、そこに点があるか・ないかということが分かればいいのでそれで十分です。
