深度に対する粗いソート
このブログポストは、Aras Pranckevicius氏のRough Sorting by Depth(2014)を、原著者の許可を得て翻訳・公開したものです。全ての権利は、原著者にあります。
要約: floatの上位ビットいくつかをintegerとしてソートをせよ。
グラフィックスでは、(透過オブジェクトのために)後ろから前の方であったり、(効果的に遮蔽を行うために)前から後ろオブジェクトをソートする。他にもさまざまなデータ(グローバルなレイヤー、マテリアル、などなど)でソートしたいと思うだろう。Christer Ericsonは、まさにこれについて素晴らしいポストをした。
次の文は、コメントにある質問だ。
深度値は全てfloatで持っていて、それらをキーとして使いたい。キーの一部として使えるように、floatをビット(もしくはinteger)にエンコードする最も良い方法はなんだろうか。
“最も良い方法"を答えるのは難しいが、単にいくつかの上位ビットを取ることは単純ではあるが、きちんとした解法だ。
浮動小数には、そのビットをintegerとして解釈すると、大きな浮動小数であればintegerとしても大きな数値になるという素晴らしい性質がある。つまり、floatをintegerとして扱い、まさにそれを比較すればそれで大丈夫なのだ(正負が同じであれば)。詳細はBruce Dawsonのブログ投稿を参照せよ。
floatのレイアウトがこのようになっているので、小数部の下位のビットを切り落としても、ただいくらか精度が落ちるだけだ。“前から後ろへのソート"のようなものために、必要なのは荒いソートだけだ。事実、同じマテリアルを持つオブジェクトも同時に描画したい場合はなどは離散化されたソートは都合がいい。
とにかく、例として10ビット取ってみる。全ての数値は正であることを前提とするなら(“カメラからの距離"でソートするならとても普通の前提だ)、正負ビットは常に0であるので無視することができる。最終的に、9ビットをソートに使うことになる。
{% highlight c++ %} // Taking highest 10 bits for rough sort for positive floats. // Sign is always zero, so only 9 bits in the result are used. // 0.01 maps to 240; 0.1 to 247; 1.0 to 254; 10.0 to 260; // 100.0 to 267; 1000.0 to 273 etc. unsigned DepthToBits (float depth) { union { float f; unsigned i; } f2i; f2i.f = depth; unsigned b = f2i.i » 22; // take highest 10 bits return b; } {% endhighlight %}
これがそのコードだ。それらのビットをソート用のキーにし、何かをソートする。
Q: 負のfloatに関しては？
DepthToBits関数に負の数値を入れてた場合、間違った順序になってしまう。integerに変換したら、負の浮動小数は正の浮動小数よりも大きくなってしまう。そのためソートもおかしくなってしまう。
{% highlight c++ %} -10.0 -> 772 -1.0 -> 766 -0.1 -> 759 0.1 -> 247 1.0 -> 254 10.0 -> 260 {% endhighlight %}
入力されたビットにある変換を施すことで、floatを正であっても負であっても完全にソート可能なintegerにすることができる。Michael Herfはそれに関するアーティクルを上げた。次のコードは彼のトリックにより正の数も負の数も扱える(10ビットを全てを使うことになるが)。
{% highlight c++ %} unsigned FloatFlip(unsigned f) { unsigned mask = -int(f » 31) | 0x80000000; return f ^ mask; }
// Taking highest 10 bits for rough sort for positive floats. // 0.01 maps to 752; 0.1 to 759; 1.0 to 766; 10.0 to 772; // 100.0 to 779 etc. Negative numbers go similarly in 0..511 range. unsigned DepthToBits (float depth) { union { float f; unsigned i; } f2i; f2i.f = depth; f2i.i = FloatFlip(f2i.i); // flip bits to be sortable unsigned b = f2i.i » 22; // take highest 10 bits return b; } {% endhighlight %}
Q.なぜビットが必要なのか？単にfloatをソートするのはダメなのか？
距離だけでソートしたくないときもあるのだ。マテリアル、メッシュ、その他色々なものでもソートしたくなるのだ(詳細はChristerの投稿で)。
とても限られた深度のビットで前から後ろにソートすることは次のような素晴らしい効果がある。どうしても範囲内にオブジェクトを"バケットする(※訳注:バケットソートより)“ことになるので、それぞれの範囲内でソートされ、ステートの変更を減らすことができる。
ソートされるデータをタイトに小さなinteger値にパックすると、極単純な比較演算子を書いたり(二つの数値を比較するだけだ)、基数ソートを使うことができるようになる。