キャッシュサイズを50％に減少させる方法 [入門]

2015/4/6

Tag: C++,Compression,tips

はじめまして、開発部のVladimirです。
今回のDFTalkでは、最近取り組んでいたプロジェクトの中から、簡単で役に立ちそうな事を書いてみたいと思います。

はじめに

今回のプロジェクトは、DF独自のキャッシュファイルをこねこねし、できるだけ効率的な書き出しと読み込みに対応させる、といった内容でした。既存ライブラリーより良い物を作る事は難しいと思うかもしれませんが、そのライブラリーを特殊に設計することで、まだ改善出来る余地があります。

ここで主にmayaのalembicキャッシュと比較してみました。 alembicはデータロスを避けるように設計されています。
ただzlib等の圧縮の場合、読み込みスピードに大きな影響が出てしまうことが分かりました。

そのため、ロッシー圧縮の良い手法を考えてみました。

floatから符号なしshortへの変換

例として、DDM で計算された破壊のシーンを見てみましょう。　シミュレーションはかなり重いので、各ポイントの３Ｄのワールド位置をキャッシュするメリットがあります。

キャッシュされたデータはポイントの３Ｄ座標のarray、つまり、浮動少数点数(フロ－ト)のarrayです。

基本的なデスクトップパソコンが用いているfloatはIEEEの基準に従っています。

詳細を省略させていただきますが、興味のある方はコチラを参照してください。

このfloatは32ビットを用います。最初のビットはマイナス・プラス数を分割しています。
次の8ビットは指数部で、かなり大きい数字と小さい数字を示すことができます。
最後の23ビットは細かい数字を示しています。

こういった仕組みで、精度と示されているレンジが高い為、現在のパソコンが用いるfloatの基準タイプになっていました。

当然、科学的な応用に対しては、精度が高すぎると言うことはありえません。
しかし、ビジュアルや映像系の応用に対しても、同じことが言えるのでしょうか。

人間の視覚が認識できるディテールは科学実験で計測されている物ほど細かくはありません。

floatが示す範囲は必要最低限を満たしていれば、それ以上は省略できるbitsがあるのではないかと思います。

まず、floatデータはhalf floatにキャストすれば適切なのか検証してみます。

そのタイプは半分のスペースでfloatに比べると半分の精度になります。
データにある数値は１単位であれば、half floatの精度は0.0005になります。
1000単位以上の数値は0.5の精度になります！

普通のシーンにあるポイント座標は1000を超えないと仮定しても、その精度で質の差は目立ちます。
なぜなら、必要のない 1000以上の数値と細かすぎる数値はhalf float
に示されているので、ＣＧや個人のニーズに対して16ビットが効率的に使われていません。

では、簡単にその16ビットを使用上データロスの少ない圧縮方法を見ていきましょう。
以下の要領で行います。

●まず、シーンのバウンディングボックスを計算します。

//p = array of xyz world coordinate
void computeBoundingBox(int nVertices, float &p, MFloatPoint &min, MFloatPoint &max) {
  min.x = p[0];
  min.y = p[1];
  min.z = p[2];
  max = min;

  for (int i = 1; i < nVertices; i++) {
    if (p[3*i] < min.x) min.x = p[3*i]; else if (p[3*i] > max.x) max.x = p[3*i];
    if (p[3*i+1] < min.y) min.y = p[3*i+1]; else if (p[3*i+1] > max.y) max.y = p[3*i+1];
    if (p[3*i+2] < min.z) min.z = p[3*i+2]; else if (p[3*i+2] > max.z) max.z = p[3*i+2];
  }
}

●そして、座標のデータをバウンディングボックスのなかでノーマライズして、65535(shortのため、2の16乗-1)をかけて、結果をキャストします。

void compress(int nVertices, float &p, MFloatPoint &min, MFloatPoint &max, unsigned short &compressedP) {
  float invDelta[3] = {1.0f/(max.x-min.x), 1.0f/(max.y-min.y), 1.0f/(max.z-min.z)};
  #pragma omp parallel for
  for (int i = 0; i< nVertices; i++) {
    p[3*i] = (p[3*i] - min.x)*invDelta[0];
    p[3*i+1] = (p[3*i+1] - min.y)*invDelta[1];
    p[3*i+2] = (p[3*i+2] - min.z)*invDelta[2];

    //すべてのポイントデータは[0,1]の範囲に示されているようになります。
    compressedP[3*i] = (unsigned short)(p[3*i]*65535);
    compressedP[3*i+1] = (unsigned short)(p[3*i+1]*65535);
    compressedP[3*i+2] = (unsigned short)(p[3*i+2]*65535);
  }
}

つまり、「0,1」の範囲が65535の解像度に分裂されているので、視覚的に認識できない差で元々のデータを半分のスペースで格納できます。
しかも、符号なしshort ⇔ floatの変換は軽いです！

同様に、ノーマライズされたデータを255にかけると符号なしcharに変換できます。精度が非常に悪いのは当然ですが、比較するため一応その結果を準備しておきました。

	Float (4 bytes)
	Unsigned short (2 bytes)
	Unsigned char(1 byte)

三つの動画のうち上の二つを比較するとほとんど差がみられませんでした。また、一番下の動画は精度が悪くなっていることが分かります。つまり、今回の2バイトへ圧縮する手法は、比較的良い精度を保つ事が分かりました。

おまけ

参考として、uncompressのコードも載せておきます。

void uncompress(int nVertices, float &p, MFloatPoint &min, MFloatPoint &max, unsigned short &compressedP) {
  float delta[3] = {max.x-min.x, max.y-min.y, max.z-min.z};
  #pragma omp parallel for
  for (int i = 0; i < nVertices; i++) {
    p[3*i] = (((float)compressedP[3*i]/65535.0f) * delta[0]) + min.x;
    p[3*i+1] = (((float)compressedP[3*i+1]/65535.0f) * delta[1]) + min.y;
    p[3*i+2] = (((float)compressedP[3*i+2]/65535.0f) * delta[2]) + min.z;
  }
}

※免責事項※
本記事内で公開している全ての手法の有用性、安全性について、当方は一切の保証を与えるものではありません。
これらの手法を使用したことによって引き起こる直接的、間接的な損害に対し、当方は一切責任を負うものではありません。
自己責任でご活用ください