PlayStation（以下PS1と略す）で採用された高速化技術オーダリングテーブル。この考え方は今でも十分高速化に貢献する考え方です。今回はこの仕組みを説明していきます。

オーダリングテーブル（Ordering Table）は PS1 の基幹描画システムとして実装されました。略して OT と記載されることも多いです。直訳すると注文表となりますが、これは描画の順番を登録したテーブルなのです。PS1 は各処理毎の描画指示を一旦全て OT に格納します。そして、全ての描画指示が完了された時点で、所謂 Flush が指定されます。すると、PS1 のシステムは OT の内容に従って一気に実際の描画を行っていきます。

OTに描画の指示を格納する際は、XYZ 座標の Z 値の大きい順にリストが生成されます。そして、最後のまとめて描画では、そのリストの大きい順から描画を行っていきます。これでそのオブジェクト（三角形）は、遠い程先に描画されることになります。これが Z ソート（Z オーダー）という 3D 描画の仕組みとなります。

現在は Z バッファというドット単位で 3D 描画を行う方式しか残っていません。Z ソートは三角形の 3点に奥行きの差があるため、面が交差した際に重なりがおかしくなるため、Z バッファだけが生き残っています。当時のハードでは Z バッファを採用するほど処理能力が高くないため、苦肉の策として Z ソートを採用し、その処理速度を上げるために OT が採用されたのです。

上記のように主に 3D 描画の高速化のために採用された OT ですが、2D でも実は十分役に立ちます。それはダブルバッファ等で最後にまとめて描画する場合に、やはり OT で描画指示を積んでおいてから、最後にまとめて描画すると効率が良いためです。また、2D であっても奥行きを表現する俯瞰見下ろし型の視点では、OT を Y の値の大きい順に並べることで、重ね合わせを正しく表現することが可能となります。

実は私が制作しているマップエディタのオブジェクト描画に、この OT に似た方式を採用しています。今時の PC はリストの並べ替えもほぼ一瞬で終わってしまうため、OT そのもののような処理は行ってはいないですが、1980年代の PC やゲーム機でなら、この OT の仕組みを採用することで、処理速度を稼ぐことが出来たりします。

また、巨大なリストに対してある値が含まれているかの検索で、普通に検索を行うとやたらと遅くなってしまいますが、これも OT の考え方でデータを振り分けておくと、一気に高速化する事ができます。このあたりのテクニックは C# List.Contains の高速化で説明してありますので興味があれば参照してみてください。簡単に説明すると Y 座標毎にリスト分解して Y に対応したリストで X を探すという処理となっています。

上記の高速化は C# ですが、この OT の仕組みは言語や機種を問わず採用することが出来ます。Z80 の場合は、例えば画面が 40x25 というサイズだとすると、25個分のリストエントリポインタを用意しておき、Y 座標に応じたリストに X の値を繋げていくだけです。C# のような List の仕組みがなくても、片方向リストは自分で作ることが出来ますから、言語を問わないのです。リスト構造に関してはこちらを参照してください。