demoscene.jp Japanese demoscene portal

2412月/120

やさしいデータ配列 〜64k introのためのデータ配置〜

イントロダクション

こんにちは。
q^gorakubu(&nonoil)です。

これまで、gorakubu (& nonoil) は64k introをいくつか作ってきました。64k introというのは、ファイルサイズ64kbyte以下の実行ファイルのみから映像と音楽を作るカテゴリです。4k introよりも労力がかかり、Demoよりも見た目のクオリティも中々良くならないという不遇なカテゴリで、作品数もそれほど多くありません。逆に考えると作品数が少ない分、労働力を投下できれば比較的目立てるチャンスがあることを意味します。

さてこの64k introの姉妹カテゴリに相当する4k introと似ている点が多いのですが、一つだけ決定的に違う点があります。64k introでは しっかりとコンテンツを作成する必要があるのです。4k introですと、(殿上人クラスの作品は除き)アブストラクトなオブジェクトと、それっぽい音楽が鳴っていれば割と許される雰囲気があります。しかし、64k introとなると、十分なファイルサイズがあるため、どのくらい高精度/高密度/高物量なコンテンツを作ったかという点を注視される傾向にあります。もしこのような"量"を増やす方向を目指すのであれば、データをどのように配置するのがいいのかを一度ちゃんと考える必要があります。

64kのデータ配列

このような話をすると出てくるのが、「全てコードで作ればいいじゃん」という主張ですが、これはあまり的を得ていません。コードで生成するのは当然で、その生成するコンテンツの"タネになるデータ"をどうするかというのが正確な出発点です。

× コード -> コンテンツ
○ データ -> 展開コード -> コンテンツ

"タネになるデータ"としては以下のようなものがあります。

1. 補間元データ

主にカーブデータなどを生成するときに使われます。直線、スプライン曲線を('キーフレーム,そのキーフレームが持つ値,(ハンドルの値))の配列の形で所持しておき、実行時にフレーム数からそのフレームでの値を計算します。introでなくても制御が非常にしやすいため様々な分野で用いられています。Catmull–Rom曲線などはハンドル制御の値は使わず、通過点を指定するだけでそれらしい曲線を出力するため64k introでは人気です。データの展開はデモの実行中に行われるのが一般的です。

2. 操作手順データ

主にテクスチャ、メッシュデータを生成するときに使われます。当然ですが、ddsファイルやfbxファイルはピクセルデータ/メッシュデータをほぼそのままの形で持っているためファイルサイズが大きすぎ、introに入れて使うことは出来ません。しかし、それらのコンテンツ製作過程でデザイナーが入力した値を記録しておきその値からテクスチャ、メッシュデータを生成するようにしておき、intro本体には製作過程で入力した値を格納しておき、ロード時に展開するような事はできそうです。"(0,10)に移動して、(20,20)に向かって直線を引く"とか、"この面とこの面を選択して0.2だけ押しだす"などなど。一般に流布しているフォーマットではSVGフォーマットが近いです。

3. 計算式データ

オブジェクトの移動パスや、カメラパス、時間で変化するuniform変数、スクリーンエフェクトの設定値などの、アニメーションデータは前述のカーブデータの出力を利用する事が多いかと思います。しかし、カーブデータは割とサイズヘビーなデータ構造で、カーブの量が増えてくると重荷になってきます。例えば[0,2π] の範囲のsin()をスプラインで表現しようとすると、15個の(x,y)データが必要になります。32bit浮動小数で表現していた場合は、960bitも消費します。さらにマズイのは、少しだけ変形したようなsin()、~位相を変えた、振幅を変えたなど~ であってもsin()の形をしたカーブデータを作るたびに毎回960bit消費するという点です。大量のオブジェクトが動くようなintroではこの手法が限界に達するのは目に見えます。sin()をハードコードすればsin()だけに関しては話は終わりますが、似たようなよく使われる演算(三角関数、指数関数などなど)が必要になるたびにハードコードするのは後述する理由からできるだけ避けたいです。
これを解消するために、gorakubu(&nooil)ではデータ志向な解決方法を採用しています。つまり特定の演算を(オペレータID, パラメータ)という形にしてデータとして扱えるようにしてます。これだけだとオペレータの種類だけしか表現の幅は増えませんが、オペレータ同士を連結できるようにする、つまりオペレーターの出力を他のオペレータの入力として扱えるようにすると、爆発的に表現できる幅が広がります。先人が作ったものが色々あるので詳しくはそれらを調べると面白いかもしれません。(例1,例2)

データ中心にすることの7つのメリット

コンテンツをデータはほどほどでコードで作るか、コードは最小にしてデータドリブン的にするかの方針は、トレードオフであり趣味的な部分であるというような扱いを受けている気がしています。しかし私見ですが、コード、特にアプリケーション側のコードは極限まで減らすべきです。コードを減らし、データドリブン的にすることのメリットをリスト化しました。

1. 分業化がしやすくなる。

言わずもながですが、コンテンツ担当をコーディング担当と別の人間を充てることが可能になります。

2. 全体の製作コストが下がる。

データを外部に持たせる形にすると、再コンパイルと確認のための再起動の作業が必要がなくなるため、コンテンツ修正のイテレーション速度を上げることができます。この点は一人でやっている場合でも恩恵を受ける事が出来ます。

3. 製作速度が安定する。

コードベースでコンテンツを作るのに比べて、専用ツールの方が着想がコンスタントに湧きやすいでしょう。さらに普段使い慣れたDCCツール用にプラグインを書けばさらに安定するでしょう。

4. 見飽きてるものを見なくて済む。

「全てコード」論はフラクタル図形とかジュリア集合とかキューブの塊とかスパイクボールとかを想定してるかもしれません。個人的意見ですが、割と見飽きてきました。

5. コンテンツの追加削除が容易になる。重複を取り除きやすい。

コードで作ってしまった場合は、追加削除に労力がかかります。またコードに存在する重複は、重複が大きな部分だとわかりやすい(関数単位とか)のですが、計算の一部(加算とか)だとわかりづらいですし、重複してもワザワザ関数に抜き出そうとういう気にはなりません。仮に抜き出したとして、インライン展開されたら同じ結果ですし、インライン展開を抑制すると呼び出しのサイズのオーバーヘッドが気になってきます。

6. というかElevated(4k intro)ですら スクリプトデータを持っていた。

んすよ。

7. コードよりもデータの方が圧縮のチャンスがある。

今回の主題です。実行ファイルを圧縮するパッカーと呼ばれるツールがあります。64k用にはkkrunchyが一番有名です。kkrunchyは、圧縮をかける際にコードがより縮みやすいように.textセクションに対してフィルター処理を行います。一方で.rdataセクションに対しては特にそのような処理は行われません。これはパッカーから見て圧縮対象の特徴がわかるか(x86コードである事はわかる)、わからないか(どのような特徴を持ったデータが格納されているかは不明)の違いがあるためです。逆にデモを作る側から見ると、コードへはフィルター処理を自前で行う事ができませんが、データに対してはある程度の特徴がわかるのでフィルターをかけることができます。またkkrunchyのフィルターは一律同じものが適用されますが、デモ側のデータに自分でフィルターを書ける場合は、データ列毎にその特徴にあったフィルターを作成する事ができます。このようにデモを作る側から見ると、コードよりデータの方がより圧縮効率へ関われる機会が多い事がアドバンテージになります。
(kkrunchyのソースコードに手を入れればそのあたりを自分用に改良できなくはなさそうですが。)

最小64k環境

実験用のプロジェクト一式をアップロードしました。
簡単な説明は以下です。

intro_main.cpp:
イントロ用のコードが載っていると考えてください。実際はMessageBoxを表示した後にExitProcess()するだけの実行ファイルが生成されます。巨大な配列introDataに一回触れているのはコードサイズの最適化で配列が消されるのを抑制するためです。
data.h:
イントロ用のデータが入っていると考えてください。巨大な配列が一つ定義されています。
filter_main.cpp:
データ生成、フィルター処理、introビルドの機能が入っています。このファイルの#ifをいじる事で、ファイルサイズがどのように変わるかをみます。

実際にVCからビルドするのはfilterプロジェクトの方で、実行するとデータ配列が生成され、msbuildが起動しintroプロジェクトのビルドが行われます。VC2012が入っている必要があります。(msbuildのパスが違う場合は適当に書き換えてください。)
filter_mainにはデータを作る関数群と、データに対してフィルターを掛ける関数群があります。それぞれを一つずつ組み合わせることで、最終的なデータが生成されます。これらを組み合わせて、どのようなデータが圧縮が効きやすいのか、どのようなデータにはどのような フィルターが効果的なのかを経験的に知ろうというのが目的です(ゆるふわ定性論議)。以下の項目は、filter_main.cpp上に同じ文がコメントで挿入されています。

■検証(1) ランダムな値を一定間隔で埋める

まずはランダムな値で埋めてみます。

  • (1-1)
    ランダムな値で埋めたものが最も縮まないデータなのでこれを圧縮率の基準にする事とします。
  • (1-2)
    浮動小数を[0,1)の範囲に限定すると指数部が同じような値に偏るため、圧縮が効くようです。
  • (1-3)(1-4)(1-5)(1-6)(1-7)(1-8)
    半分のビットが立っているビットマスクをかけると、ほぼ半分のデータ量になりました。そのマスクの間隔は、2bit,4bit,8bit,16bit,32bitどの間隔であっても変わりはありません。またビット幅は狭い方がその分だけ縮むこともわかります。
  • (1-9)
    浮動小数の上位16bitに対してマスクをかけています。これは、IEEE 754形式の 浮動小数では、符号部、指数部、仮数部の上位7bitを切り取ることに相当します。仮数部の精度は元々の23bitから7bitに落ちますが、上位16bitにマスクをかけた浮動小数そのものは普通の浮動小数として評価でき、元の浮動小数と大して値として差がない事がわかります。展開用のコードが不要である事も魅力の一つです。(1-2)と比べて情報量は半分なはずなのにそれ以上に減っているのは仮数部が浮動小数の値域に比べて非常に限られた値のみを扱っているため( [0,1)の範囲のみ )です。浮動小数の上位16bitに対していマスクをかけるのはintroでは定石的な手法です。整数へのキャスト時に値が落ちるのを防ぐために、16bit目に+1をする場合もあります。16bit固定である必要はないので、精度がほとんど要らない場合はより多くマスクをかけたり、少し精度が必要な場合は少なめにマスクをかけるなどすると良いです。仮数部と、指数部への値の割り当てをコントロールしたい場合は、このあたりを参照するといいです。
  • (1-10)
    (1-9) の考えをさらに進め、隙間の0をなくした場合です。多少は減るようですが、あまりインパクトは無さそうです。展開用のコードが余計に必要になる事と、開発時のデバッグが少し難しくなるデメリットの方が大きいかもしれません。また この結果から可変長配列ではなく固定長配列であっても、サイズはそれほど影響を受けずらい事がわかります。

■検証(2) 単一データで埋める

次に、単純なデータに対して、圧縮率がどのように変化するか見てみます。

  • 最高値と最低値は2倍差がありますが、圧縮率を見ると全て0.1%以下でほぼ扱いは同じと考えて良さそうです。
  • 0埋めが一番低い数値となっているのは、kkrunchyが8k以上の長さの0のみで埋まったbit列に対して特別なエンコードを行っているためです。
  • 定数値の繰り返しであれば、ほとんどコストがかからないことが分かりました。

■検証(3)階段状に埋める

次に、データにある程度規則性を持たせることにします。具体的には、整数値データを徐々に増えるようにしてみます。

ランダムな値よりもかなり縮む事がわかります。この事からkkrunchy内部では何らかの予測を行い、予測通りにデータが動いた場合は 、少ないビットで表現できているということがわかります。

■検証(4) 固定小数化する。

浮動小数は、0付近に多めにビットが割り当てられています。値が2倍になる毎に精度が半分になるため7bitしか仮数部がない状態ですと、その偏りが気になる事があるかもしれません。そのような時は、固定小数化(次のアドベントカレンダーはその話題!)を検討すると良いかもしれません。1bit違いの平均間隔は空いてしまいますが、全体の偏りはなくなるため、割り当てるbitを減らす事ができます。座標を指定するなどの用途ではなく、大まかに何分割したいという要望がある箇所では固定小数化をするといいかもしれません。

■検証(5)  整数、浮動小数。ソートする。

値の並びが重要でない場合は、値をソートしておくと縮みやすくなります。意外と出番はないのですが、上述の演算子のオペレータ番号などはソートを行って格納しています。値域が広くなるほど、連続する数が減るほど圧縮率が極端に悪くなるのがわかります。順番そのものが重要でない場合はソートしておきましょう。浮動小数も、同じ指数部が連続する可能性が上がるため縮みます。

■検証(6) 整数、浮動小数。差分を取っておく。

似たような数値を出すとサイズが減少する事から、もう少し工夫をしてみます。具体的には、前の数値との差分を保存するという方法を試してみます。検証(5)のようにソートしたあとの配列に対して行えば整数の場合はほとんどが0もしくは1が連続しますし、浮動小数の場合も0付近に集中するため指数部が同じような値ばかりになることが予想されます。浮動小数の場合は、差分の精度は絶対値の精度よりも低くても元の値に復元できる(正負を跨ぐ場合は除く)ので、より攻めたい場合は差分の精度を減らす事も考えるといいでしょう。ここではやっていませんが、そのような精度の調整は決め打ちではなく、ランタイムで適応的に行う事が可能なので、それも試みるといいかもしれません。

差分を保存すると軒並みサイズが減少する事がわかります。さらに特筆すべきは、(6-6) と(6-8)で圧縮率が5倍弱も違う点です。これから、保存される値が狭い範囲(今回は0付近)に密集すると圧縮率が向上する事がわかります。

■検証(7) 浮動小数。何らかのモデルから予測を行い、差分を保存する。

差分を0付近に密集させる事がポイントのようなので、単純に差分を取るだけはなくもうすこし工夫をします。具体的には、『値の変化の速度はほとんどかわらないだろう』という仮定を置いてその予想値との差分を取るようにします。コードにすると、次のような形です。

const float32 curSpeed  = curValue - prevValue;
const float32 nextValue = curValue + curSpeed;
const float32 error     = trueNextValue - nextValue;

さらにこの考えを推し進めて、『値の変化の加速度はほとんどかわらないだろう』と仮定を置いてその予想値との差分をとるようにするのもいいかもしれません。コードにすると次のような形になります。

const float32 curSpeed  = curValue - prvValue;
const float32 prvSpeed  = prvValue - prvPrvValue;
const float32 accel     = curSpeed - prvSpeed;
const float32 nextSpeed = curSpeed + accel;
const float32 nextValue = curValue + nextSpeed;
const float32 error     = trueNextValue - nextValue;

元になる数列が三角関数から生成されたためかなり予測が正確になるという点もありますが、かなり縮みました。特徴のあるデータに対してなんらかのモデルを作成し、その予測の差分を出力するという形がかなり効くようです。

■検証(8) 浮動小数。SoA化する

デモは3次元的なデータを扱う事が多いです。素直な扱いをすると、三次元データの配列を用意する(Array of Structure)事が多いかと思います。しかし例えばカーブデータなどの場合は、(x,y,z)の各軸毎に分離しておくと、次の値がかなり予測しやすくなります(XYZのお互いの値が影響しあうようなデータもあるかもしれませんが、大半の場合は各軸で独立した動きになると思います)。もともとAoSだったものをSoA(Structure Of Array)にした上で検証7のような事をやると縮みます。

× struct { float x,y,z; }vec3s[] = {...};
○ vec3s_x[] = {...}: vec3s_y[] = {...}; × vec3s_z[] = {...}:

■検証(9) 浮動小数。仮数部を分離する。

これまでの浮動小数は値をそのまま保存していました。しかし浮動小数は、これまで出してきたようなフィルターを通したとしても、仮数部と(指数部+符号部)では変動の大きさが異なります。仮数部はかなり変動が大きく前回の値からの予測が難しく、(指数部+符号)は変動が小さくかなりの精度で予測できるはずです。いくつかフィルターを通したあとでかなり落ちついたデータに対しての最後の仕上げとして、この二つに分離して出力したりすると良さそうです。

まとめ

これらをまとめると以下のようになります。

  • 固定長配列であっても、利用しない個所を0で埋めるような対処でもそれなりに縮む。長さを記録しておいても良い。
  • 値が単調増加/減少するようなデータであれば、kkrunchy側で勝手に予測して縮めてくれる。
  • 省いてもあまりデータが変動しないbitは、状況により0で埋めておくとその分だけ縮めてくれる。
  • 値の順序には意味がないようなデータの場合は、値の順番にソートしておくと良い。
  • 値域(変数が利用可能な範囲ではなく実際に利用する値域)が狭い方が縮む。
  • 浮動小数で大きな値を表現するためにbitを多く消費するよりも、固定小数化をして消費するビットを減らす。
  • 何らかのモデルを用いてデータの特徴から次の値を予測できるならば、その予測との差分を保存する形の方が縮む。
  • Vec3など関連性のないデータ隣接するデータよりも、各要素の配列(SoA)にするとより縮む。
  • ある程度フィルターを掛けておとなしくなった浮動小数データに対しては変動の激しい仮数部を分離して仕上げる。
  • (符号部+指数部)と仮数部に分離したら(符号部+指数部)はさらにその差分を出力するようにする。

最後に

いかがでしたでしょうか。64k introは特段マジックでも何でもないということがわかっていただけたと思います。全部が全部ではないですが9割9分以上の64k作品は多大な労働力投下の賜、小さな事の積み重ねの結果だと思っています(たまに出てくる天才作品もありますが、それを最初から目指すのはたぶん正しくないです)。静かに淡々とチマチマとやるのが苦にならないタイプの人には向いてるのではないかと思います。2ヵ月後はたぶん無理でも1,2年後に超大作64k introを日本の誰かがリリースするのを心待ちにしています。

告知!!!

現在デモグループ gorakubu では来夏リリース予定の次期Demo(≠intro)を開発するメンバーを募集しています。募集要項は以下です。

1.  3D GFXな人

  • 必須事項
    • 何らかのDCCツールを使いこなせること
    • モデリング・テクスチャリング・ライティング・アニメーションが一通り行えること
  • あるといい事
    • デモに対して興味があること
    • ライティングに関してある程度知識がある
    • 有機物が得意である

2. コンポーザー

  • 必須事項
    • 何らかのDTMツールを使いこなせること
    • 多少のリテイクに耐えられること
  • あるといい事
    • デモに対して興味がある。

少しでも興味が向いたら、Twitter or  メール or Skypeにて連絡を下さい。お待ちしております。

Comments (0) Trackbacks (0)

No comments yet.


Leave a comment

Trackbacks are disabled.