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

注）1999/03/26 時点の情報に基づいた内容です。現状とは合致しない可能性があります。

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

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

• ソフトウェアスプライトのボトルネック＝メモリアクセス

近年、メモリのアクセスの速度向上は、CPU の速度向上に比べて非常に低く、 ボトルネックになりがちです。

ソフトウェアスプライトは、 単純に言ってしまえば、 「転送元の画像を読み取って、転送先のメモリに書き込む」 だけの処理で、 ボトルネック要因は、ほぼメモリのアクセス速度のみです。


• メモリアクセスがなぜ重いか

メモリから読み出し、メモリに書き込む。 この単純な過程で一体どのような事が起こっているのか？ Pentium 系列の CPU に限定し、 手元にある資料から、最悪の事態をシミュレートしてみます。


• メモリ読み出し時のペナルティ

一次キャッシュにヒットしている場合、1 クロックで読み出しは終了します。 一次キャッシュは、Pentium で 16KB です。 大量のデータをランダムにアクセスするようなテクスチャーマッピング 処理等においては、16KB ではまず足りません（256*256 , 256 色で 64KB ですから）。 かなりの頻度で一次キャッシュにミスヒットします。 この時 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 の部分を調べて描画すれば OK です。

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

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


• 実装結果とスペック

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

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

• 3D グラフィクスアクセラレータの世界でもメモリアクセスがボトルネック

ここまでは 2D スプライトの話ですが、 3D ポリゴンの描画でも、同じ問題が起きています。

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

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

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


• PowerVR シリーズのアプローチ

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

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

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

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

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

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