ソフトウェアによる高速なアルファブレンド

Posts

高性能なグラフィックスカードが普及した今の環境では、ハードウェアでアルファブレンドを行うのが当たり前になったので、昔は豊富だったソフトウェアによるアルファブレンドに関する情報が減ったように思う。

そこで、アルファブレンドを実装する際に調べた高速化テクニックや、陥りがちな落とし穴についてまとめておくことにした。

何故、ハードウェアで出来ることをわざわざソフトウェアで実装するのかというと API への依存度を下げるため。DirectDraw を使っていたときは何から何まで API に頼っていたので、GDI へ移行する際に描画処理のほとんどを書き直すことになったが、ソフトウェアでのレンダリングに切り替えた後に行った Direct2D への移行はスムーズに行えた。

アルファブレンドの計算式

転送元を src、転送先を dst、アルファ値を A とした場合、以下のような式で求めることができる。

srcA + dst(1 - A)

A は 0 ～ 1 の範囲を取る係数。これを C/C++ で書くと、

out = src * a + dst * (1 - a);

となる。アルファ値は小数なので a は float または double 型で表現される。

アルファ値の整数化

浮動小数を含んだ演算はコストが高いので、ピクセルと同じように 0 ～ 255 の範囲に収まる整数として扱うようにする。

out = src * a / 255 + dst * (255 - a) / 255;

ピクセルフォーマットが ARGB のときはアルファ値が整数で保持されているので、そういう面でも都合が良い。

式の最適化

アルファ値を整数化したことによって除算が増えてしまったので、式を変換して除算回数を減らす。

srcA + dst(1 - A)

元の式にある括弧を展開した後、

srcA + dst - dstA

共通項 A でくくりだす。

(src - dst)A + dst

これをプログラムに直すと、

out = ((src - dst) * a / 255) + dst;

除算の回数が減っているのが分かる。

式を変換したことによる影響

変換後の式が正しく実装できているのか検証するため、変換前の式と同じ結果になるのか調べてみたところ、dst の値が src より大きいときにズレが生じていた。

どこでズレが発生しているのか分からなかったので、各式に src = 0, dst = 127, a = 127 を入れた時の演算過程を 1 ステップ毎に追うことにした。

  src *   a / 255 + dst * (255 -   a) / 255
= 0   * 127 / 255 + 127 * (255 - 127) / 255
= 0   * 127 / 255 + 127 * 128         / 255
= 0         / 255 + 16256             / 255
= 0               + 63
= 63

  ((src - dst) *   a / 255) + dst
= ((0   - 127) * 127 / 255) + 127
= (-127        * 127 / 255) + 127
= (-16129            / 255) + 127
= -63                       + 127
= 64

変換後の式は演算途中で値が負になり、それを除算した時に誤差が生じていた。C/C++ における浮動小数から整数への変換は「0 への丸め」になるので、正の場合は小さく、負の場合は大きくなる。

floor 関数を使えば「切り捨て」になるので変換前の式と同じ結果を得ることができるが、関数の呼び出しはコストが高すぎて最適化の意味がなくなってしまう。

除算をシフト演算に変更

プログラム高速化の定番といえば乗除算のシフト演算置き換え。

out = ((src - dst) * a >> 8) + dst;

ビットシフトは 256 による除算なので 255 で除算していた時とは異なる結果にはなるが、誤差が最大± 1 の範囲に収まるのでトレードオフとしては悪くない。

この誤差が問題になるのは src に最大輝度、アルファ値に完全不透明を指定したときで、

  src *   a / 256
= 255 * 255 / 256
= 65025     / 256
= 254

輝度が最大値に達しなくなる。

例えば、ビジュアルノベルでキャラクター登場演出にアルファブレンドを使った場合、演出が終わって完全不透明な状態になっても表示は微妙に暗くなるので、背景などの近くの表示物に明るい部分があると暗さが目立ってしまうかもしれない。

ただ、パフォーマンスチューニングの関係で、完全に不透明の場合はアルファブレンド演算が入っていない高速な単純転送に切り替えていたので、この誤差に対して特別な対応をする必要はなかった。

if      ( a == 0 )
{
    // 完全に透明なので何もしない
}
else if ( a == 255 )
{
    // 完全に不透明なので単純転送
    // 以下転送処理
}
else
{
    // 以下アルファブレンド付き転送処理
}

パック演算化

説明を簡略化するために src や dst といった表記を使ってはいるが、ピクセルは RGB の 3 要素から構成されているので、実際は 3 回の演算が必要になる。この演算負荷を少しでも減らすためにパック演算を行う。

8 ビット同士の演算結果は 16 ビット内に収まるので、32 ビットの精度があれば 8 ビットの演算を同時に 2 つ行うことができる。

ピクセルフォーマットが XRGB だった場合、32 ビットを 16 ビット単位で分割すると各下位バイトに来るのは R と B なので、0x00ff00ff でマスクをとれば R と B を同時に演算することができる。

rb = dst & 0xff00ff;
g  = dst & 0x00ff00;
rb += ((src & 0xff00ff) - rb) * a >> 8;
g  += ((src & 0x00ff00) - g ) * a >> 8;
out = (rb & 0xff00ff) | (g & 0x00ff00);

最適化を積み上げてきたこともあって、この式は「アルファ値の整数化」にある式と比べて 2 倍程速かった。

テーブル化

16 ビットカラー (High Color) が主流だった頃、予め全アルファブレンド結果をルックアップテーブルに入れておいて演算は行わないという手法が使われていた。

ピクセルフォーマットが R5G5B5 の場合、各要素は最大 5 ビットなので 32 通り、アルファ値を 32 段階で持った時のブレンドの組み合わせは 32 x 32 x 32 で 32768 通り、5 ビットを格納できる最小サイズは 1 バイトなのでテーブルのサイズは約 33KB になる。

この手法はビット数が少ないから成り立っていたのであって、24 ビットカラーで同じことをやろうとするとテーブルサイズが大きくなりすぎて使い物にならない。当時はテーブルが消費するメモリ量が問題視されることもあったが、大きすぎるテーブルは CPU キャッシュとの相性が良くないので、今の環境でもあまり良いアプローチとは言えない。

最適化する上での注意点

まず、重要なのはアルファブレンドの結果が正しいのか検証すること。処理が高速になっても結果が間違っていたら意味がない。速くないが正確に計算するデバッグ版を作っておき、それと結果が一致するのかテストを行う処理を挟んでおくと早い段階で間違いに気づくことができる。

もう一つは必ずベンチマークを取ること。CPU やコンパイラの技術は日々進化し続けているので、速いと思い込んで書いたコードが実は遅かった、なんてことが起きる。現在の CPU は複雑なので、キャッシュやパイプラインの影響によって、書いたコードが実際どれくらいの速度で実行されるのか予想するのが難しい。

CPU とアセンブラに詳しい人ならコンパイラが吐き出したコードを眺めて最適化するのもありかもしれないが、自分は簡単なアセンブリしか読めないので、素直にベンチマークを取るようにしている。