[戻る]

高速なソフトウェアスプライトの実装

ソフトウェアスプライトとは、 ハードウェアを利用せず、 CPU で直接ピクセル単位で描画するスプライトのことです。 従来、スプライト機能は、 ハードウェアアクセラレート無しでは実現できない機能でしたが、 近年の CPU 速度の向上に伴い、 ソフトウェアベースで十分に実用的なものが実装できるようになってきました。 この文書では、ソフトウェアスプライトを実装する際、 どのような高速化アプローチが考えられるか、 どれぐらいの速度が出せるか等々についてまとめます。
注)1999/03/26 時点の情報に基づいた内容です。現状とは合致しない可能性があります。

この当時 DirectX のバージョンはまだ 3 で、 GPU やドライバの実装の品質が非常に悪い時代でした。 ローエンド GPU の実装は特に問題が大きく、 スプライト描画一つをとっても、カラーキーと呼ばれる透過色さえも処理できない GPU がありました。 当時このような問題を完全に回避する方法は、CPU によるソフトウェアスプライトを利用することでした。

高速なソフトウェアスプライトが必要になるケース

OS やハードウェア環境を越えて動作するクロスプラットフォームなゲームを作る場合、 描画周りで、特定の OS 環境でのみ提供される API を利用することはできません。 OpenGL のようなクロスプラットフォームなグラフィクス API を利用する方法も一つですが、 現実にはそのような API が存在しない環境も存在します(例えば家庭用ゲーム機の SDK など)。

真のクロスプラットフォームを実現するには、 すべてのグラフィクス処理をソフトウェアで行う必要が生じます。 それはとても大変なことのようにも思えますが、 2D ゲーム向けのスプライト描画機能のみであれば、 実装はそこまで大変なことではなく、 十分に最適化すれば、用途次第では十分なパフォーマンスも得られます。

高速なソフトウェアスプライトの実装

ソフトウェアスプライトは、ハードウェアアクセラレートによるスプライトに比べて、 莫大な処理負荷がかかります。 高速な動作を実現するには、注意深い最適化が必要になります。
ソフトウェアスプライトのボトルネック=メモリアクセス
ソフトウェアスプライトは、 単純に言ってしまえば、 「転送元の画像を読み取って、転送先のメモリに書き込む」 だけの処理で、 ボトルネック要因は、ほぼメモリのアクセス速度のみです。 近年、メモリのアクセスの速度向上は、CPU の速度向上に比べて非常に低く、 ボトルネックになりがちです。

メモリアクセスがなぜ重いか
メモリから読み出し、メモリに書き込む。 この単純な過程で一体どのような事が起こっているのか? Pentium 系列の CPU に限定し、 手元にある資料から、最悪の事態をシミュレートしてみます。
メモリ読み出し時のペナルティ
一次キャッシュにヒットしている場合、メモリ読み出しは 1 クロックで終了します。 一次キャッシュは、Pentium で 16KB です。 256 x 256 dot 256 色で 64KB の容量になることを考えると、16KB のキャッシュは非常に狭く、 かなりの頻度で一次キャッシュミスが発生します。 この時 3 クロックのペナルティがあるようです。

二次キャッシュは、256KB 以上あります。 二次キャッシュミスはペナルティが大きく、 最低でも 7 クロックのペナルティです。 (Pentium Pro 系列では、アウトオブオーダー実行により、 キャッシュミスによるストールの最中でも他の実行可能な命令を先行実行できるので、 影響を最小限に抑える事ができるようです。)

メモリ書き込み時のペナルティ
メモリへの書き込み命令は 1 クロックで終了します。 しかし実際には内部のライトバッファにデータが蓄積され、 遅延してメモリに書き込まれます。 ライトバッファは 4 段用意されていますが、 一度に多数のメモリ書き込みを行うとすぐに満タンになります。 満タンになると、次の書き込み命令は待たされます。

最悪のケース = メモリ読み出しとメモリ書き込みのペナルティが複合
最悪のケースは、メモリ読み出しとメモリ書き込みが複合する場合に発生します。 ライトバッファにデータを蓄積させた状態でメモリ読み出しを行う時、 メモリ内容の整合性を保つため、 ライトバッファの内容が書き出されるまで読み出し側が待つという、 大規模なストールが発生します。 同時にキャッシュミスも発生すると、ストール時間はますます大きくなります。

ソフトウェアスプライトは、 メモリを読み出してメモリに書き込む処理を集中して行うので、 上記の最悪ケースが多発する傾向があります。

重複描画の回避が重要
メモリアクセスしないことには、 スプライトは描画できません。 そして最大のボトルネックはメモリアクセスです。 どうすればいいんだ? という話になります。

解決のカギは、 重複描画の回避です。

スプライトが不透明であると仮定すると、 一度描画済みとなったピクセルは、 それ以降の描画をキャンセルしてもかまいません。 画面上のピクセル数は有限です。 スプライトを描画すればするほど、 描画済みピクセルが増えていき、 後続の描画のピクセルをキャンセル可能な機会が増え、 コストは低くなります。 画面全体のピクセルが描画済みとなってしまえば、 以降の描画は全キャンセル可能なので、コストはゼロになります。

つまり、多少のオーバーヘッドを伴ってもかまわないので、 重複描画回避の仕組みを導入し、 所定の時間内に画面全体を塗りつぶせるだけの速度が出せれば、 十分に実用的なソフトウェアスプライトが実現できるということです。

遮蔽マスクという概念を導入
重複描画を回避するため、遮蔽マスクという概念を導入します。 これは、描画済みピクセルを 0、未描画ピクセルを 1 とするビット列で、 画面の全ピクセルに 1 対 1 対応するものを用意します。

遮蔽マスクは、32bit の整数型で扱い、32 ピクセルの遮蔽を一括管理します。 遮蔽マスクへのアクセス自体が、メモリアクセスを伴いますが、 32 ピクセルを一括で処理できるので、そのコストは比較的小さくなります。

遮蔽マスクの加工は、ビット単位の論理演算で行います。 スプライトのビットパターンに対応する遮蔽マスクと、 描画先の遮蔽マスクの間で論理演算を行うことで、 実際に描画が必要なピクセルの位置を示すマスクを得ることができます。

例えば、描画元のマスク(非透明色の部分のビットが 1)が、
SrcMask = 0001 1111 1001 1010
として、描画先のマスク(未描画部分のビットが 1)が、
DstMask = 0000 1111 1111 0000
とした場合、描画の必要がある部分を示すビット列は、論理積を取って、
AndMask = 0000 1111 1001 0000
となります。あとはビットが 1 の部分を調べて描画すれば目的は達成されます。

AndMask が 0x0000 なら、描画を完全にキャンセルできます。 AndMask が 0xFFFF なら、全ピクセルを遮蔽チェック無しで描画できます。 AndMask がそれ以外の場合は、立っているビットを検査しながら、 必要なピクセルに対する描画を行います。

AndMask を 4 ビットずつ切り出して、ジャンプテーブルのオフセットとし、 16 通りの専用描画ルーチンに飛ぶと言ったアプローチも考えられます。 (ただしジャンプした方が有利かどうかは、CPU アーキテクチャを考慮した上で判断が必要です。)

実装結果とスペック
上記の方法を実装した結果、PentiumMMX 233MHz にて、 32*32 スプライトが 1300枚/60fps ほどのスペックが出せました。 シューティングゲームなら、 怒首領蜂ぐらいのものが、CPU 処理のみで余裕で動く水準です。

余談:同じ問題は 3D でも当てはまります

3D グラフィクスアクセラレータの世界でもメモリアクセスがボトルネック
ここまでは 2D スプライトの話ですが、 3D ポリゴンの描画でも、同じ問題が起きています。

3D グラフィクスアクセラレータの性能を計る指標として(1999年)現在定着しているのが、
「ピクセルフィルレートが幾らか?」
「60fpsで画面を何回塗りつぶせるのか?」
「秒間何ポリゴン描けるか?」
というような値です。
「次の PS は秒間何ポリゴン出せるらしいぞ」
といったようにです。

ところが最近になって、 これらの塗りつぶし速度による性能評価自体が、 方向転換を余儀なくされているようです。

3D グラフィクスアクセラレータの世界でも、これまで述べてきた事同様に、 メモリアクセス速度の問題が大きく立ちはだかり始めたのです。 これからは、3D グラフィクスアクセラレータの性能指標として、 ピクセルフィルレートではなく、
いかに重複描画をうまく回避できるか?
いかにメモリアクセスを回避できるか?
が重要になってきます。

PowerVR シリーズのアプローチ
無駄なメモリアクセスの回避をコンセプトに設計された典型的なハードウェアに、 PowerVR シリーズが挙げられます。 確か、Direct3D 初期の混沌とした時期に出てきたハードだったと記憶しています。 あまりにも先見性に富み過ぎていた為、 DirectX と相性が悪く、実にドリームキャストが登場するまで 日陰者を余儀なくされてしまった可哀相なやつですが、 コイツは本当は凄いやつなのです。

ちょっと脱線して PowerVR について書きます。

私も正確には把握していないのですが、 PowerVR は 32*32 ピクセル単位で画面を細かく分割し、 この分割区画に対して個別に複数の描画チップが並列処理を行っています。

32*32 ピクセル分の処理をするだけの小さなローカルメモリが描画チップに実装されているわけですが、 このローカルメモリは小さいゆえに、 冒頭で述べた Pentium で言う所の一次キャッシュヒットを維持したような状態にあり、 非常に高速な処理が可能です。

そして、32*32 ピクセル内部の処理では、テクスチャーデータ等を読みに行くことはしません。 なぜなら、外部のメモリを読みに行くことは、メモリアクセスによる負荷を生じるからです。 代わりに何をやっているのかというと、 32*32 内の各ピクセルに描画するデータを、 どこのメモリから読んでくればいいのかだけを決定しています。 これが全て決定してから、初めて描画の為のメモリアクセスを試みます。 その結果、メモリアクセスは 1 ピクセル当たり 1 回キリとなるわけです。 従来重いとされた Z バッファ処理も、高速ローカルメモリでラクラクこなします。

ただし、半透明処理だけは奥から合成する必要がある為、遮蔽が効かず、 内部で特殊処理されるため、苦手な処理になっているようです。 ドリームキャストが半透明が遅いと言われるのはこのためです。


1999/03/26 初出
文責: よっしん

[戻る]