(57)【要約】  【課題】  同じ表示情報を繰り返し読み出す処理を不要にして処理の高速化を図ることができる描画装置を提供する。  【解決手段】  プリフェッチバッファ１０８は、メインＲＡＭ２５から、ソート後の構造体インスタンスを順次読み込み、読み込んだ順番で構造体インスタンスを出力するＦＩＦＯ構造のバッファである。リサイクルバッファ１１０は、次の描画サイクルでも使用される（再利用できる）構造体インスタンスを格納するＦＩＦＯ構造のバッファである。デプスコンパレータ１１２は、プリフェッチバッファ１０８から取り出した構造体インスタンスに含まれるデプス値と、リサイクルバッファ１１０から取り出した構造体インスタンスに含まれるデプス値と、を比較して、より奥に表示されるべき構造体インスタンスを選択して、後段に出力する。【選択図】  図４
2011159306.tif 000002
【特許請求の範囲】
【請求項１】
それぞれが複数のピクセルから構成される平行な複数のラインを、そのラインに垂直な方向に並べて構成されるスクリーンに、外部に配置されたメモリから読み出した、グラフィック要素の表示情報に基づいて、スクリーンイメージを表示するための描画を行う描画装置において、
前記スクリーンを構成する前記ピクセルのうち所定数分のピクセル情報を格納可能であって、格納した前記ピクセル情報を前記スクリーンイメージを表示するために出力し、出力した前記ピクセル情報が格納されていた位置に、前記スクリーンイメージを表示するための新たなピクセル情報を格納する第１バッファと、
前記表示情報に基づく前記ピクセル情報が前記第１バッファに格納された後に、当該表示情報に基づく他のピクセル情報を前記第１バッファに格納するために、当該表示情報が再利用可能なときに、当該表示情報を格納する第２バッファと、を備える描画装置。
【請求項２】
前記メモリから読み出した前記表示情報に含まれる表示深度情報と、前記第２バッファから出力される前記表示情報に含まれる表示深度情報と、を比較し、予め定められた規則に従って、いずれかの前記表示情報を選択して先に出力する比較手段と、
前記比較手段から出力された前記表示情報に基づいて前記ピクセル情報を生成し、前記生成したピクセル情報を新たなピクセル情報として前記第１バッファに書き込む書き込み手段と、をさらに備える請求項１記載の描画装置。
【請求項３】
前記メモリから読み出した前記表示情報を格納する第３バッファをさらに備え、
前記比較手段は、前記第３バッファから出力される前記表示情報に含まれる表示深度情報と、前記第２バッファから出力される前記表示情報に含まれる表示深度情報と、を比較し、前記予め定められた規則に従って、いずれかの前記表示情報を選択して先に出力する、請求項２記載の描画装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、フレームバッファを使用せずに品質の高い三次元イメージの表示を可能とする描画装置及びその関連技術に関する。
【背景技術】
【０００２】
従来では、三次元イメージを表示する場合、１フレーム以上のイメージデータを描画することが可能なフレームバッファやビデオメモリを、画像生成装置に実装するのが一般的であった（特開平６−３４８８６１号公報、特開平７−２８２２７０号公報）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平６−３４８８６１号公報
【特許文献２】特開平７−２８２２７０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、画像生成装置にフレームバッファ等を実装しようとすると、少なくとも一つのイメージ全体を格納する容量のメモリが必要不可欠となり、コストが高くなる。高品質の三次元イメージを表示するために、ダブルバッファ方式を採用すると、少なくとも二つのフレームバッファを格納可能な容量のメモリが必要となるため、更にコストが高くなる。
【０００５】
一方、二次元イメージを表示する場合は、必ずしもフレームバッファは必要なく、ラインバッファでも十分である。しかし、ラインバッファを用いて、三次元イメージを表示しようとすると、従来の画像生成装置の描画能力では、描画可能なポリゴンの数が限られてくる等、見る者が満足するような品質の高い表示を行うことが困難である。
【０００６】
そこで、本発明は、少ない記憶容量の、描画のためのバッファを用いながらも、品質の高い三次元イメージの表示を可能とする描画装置及びその関連技術を提供することを目的とする。
【０００７】
また、本発明の他の目的は、少ない記憶容量の、描画のためのバッファを用いながらも、半透明合成を可能として、より品質の高い三次元イメージの表示を可能とする描画装置及びその関連技術を提供することである。
【０００８】
さらに、本発明の他の目的は、インタレーススキャンによる表示を行う場合においても、少ない記憶容量の、描画のためのバッファを用いながらも、品質の高い三次元イメージの表示を可能とする描画装置及びその関連技術を提供することである。
【課題を解決するための手段】
【０００９】
本発明の第１の観点によれば、描画装置は、それぞれが複数のピクセルから構成される平行な複数のラインを、そのラインに垂直な方向に並べて構成されるスクリーンに、多角形状のグラフィック要素を含むグラフィック要素ごとの表示情報に基づいて、前記グラフィック要素の組み合わせからなるスクリーンイメージを表示するための描画を行う描画装置であって、前記表示情報に含まれる、前記グラフィック要素の前記ラインに垂直な方向の位置を示す座標が、昇順あるいは降順のいずれかで並ぶように、前記グラフィック要素ごとの前記表示情報を並べ替えるソート手段と、前記ソート手段が並べ替えた前記表示情報を順番に読み出して、読み出した前記表示情報に基づいて、対応する前記グラフィック要素の描画を実行する描画手段と、を備える。
【００１０】
この構成によれば、グラフィック要素のラインに垂直な方向の位置を示す座標が、昇順あるいは降順のいずれかで並ぶように、グラフィック要素ごとの表示情報を並べ替えている（ソート）。従って、ソート後の表示情報を順番に読み出して、描画処理を行うだけでよいため、描画のたびに、全ての表示情報の中から、そのとき描画すべき表示情報を検索する処理が不要になり、処理を高速化できる。以上の結果、１フレーム以上のイメージを格納するための大容量のバッファ（フレームバッファ等）を実装する必要は必ずしもなく、より容量の小さいバッファ（ラインバッファや、１ラインに満たないピクセルを描画するピクセルバッファ等）を実装した場合であっても、多くのグラフィック要素を組み合わせたスクリーンイメージの表示が可能になる。特に、二次元イメージ表示のための描画処理と比較して、高い処理能力が必要な三次元イメージ表示のための描画処理にも好適である。
【００１１】
ここで、昇順とは、小さいほうから大きいほうへの順に並べることを意味し、降順とは、大きいほうから小さいほうへの順に並べることを意味する。
【００１２】
上記描画装置において、前記描画手段は、前記スクリーンを構成する前記ピクセルのうち第１の所定数分のピクセル情報を格納可能であって、格納した前記ピクセル情報を前記スクリーンイメージを表示するために出力し、出力した前記ピクセル情報が格納されていた位置に、前記スクリーンイメージを表示するための新たなピクセル情報を格納する第１バッファ（例えば、図１のラインバッファＬＢ１，ＬＢ２に相当）と、第２の所定数分の前記グラフィック要素の前記表示情報を格納可能であって、前記表示情報に基づく前記ピクセル情報が前記第１バッファに格納された後に、当該表示情報に基づく他のピクセル情報を前記第１バッファに格納するために、当該表示情報が再利用可能なときに、再利用のために送られてくる順番で、当該表示情報を格納し、前記第１バッファが前記新たなピクセル情報を格納する期間が到来したときに、格納した順番で前記表示情報を出力する第２バッファ（例えば、図１のリサイクルバッファ１１０に相当）と、前記ソート手段が並べ替えた順番で読み出された前記表示情報のうち、前記第１バッファに格納すべき期間が到来した前記新たなピクセル情報を生成するための前記表示情報に含まれる表示深度情報と、前記第２バッファから出力される前記表示情報に含まれる表示深度情報と、を比較し、予め定められた規則に従って、いずれかの前記表示情報を選択して先に出力する比較手段と、前記比較手段から出力された前記表示情報に基づいて前記ピクセル情報を生成し、前記生成したピクセル情報を前記第１バッファに書き込む書き込み手段と、を含む。
【００１３】
この構成によれば、第１バッファへの新たなピクセル情報の書き込み（新たなピクセルの描画）のために、表示情報が再利用可能な場合は、その表示情報は、第２バッファに格納される。このため、同じ表示情報を使用する新たなピクセルの描画のたびに、ソート後の全ての表示情報が格納されたメモリから、その同じ表示情報を繰り返し読み出す処理が不要になって、より処理の高速化を図ることができる。
【００１４】
また、比較手段を設けて、ソート手段が並べ替えた順番で新たに読み出された表示情報と、再利用のための第２バッファに格納された表示情報と、の描画順序（つまり、これら表示情報に基づくピクセルの描画順序）を判定している。このため、判定終了後に、再利用可能な表示情報を第２バッファに送って順番に格納するだけで、第２バッファには、再利用可能な表示情報について、適切な描画順序で表示情報が格納される。このように、第２バッファには、再利用可能な表示情報について適切な描画順序で格納されているところ、これらは、ソート手段が並べ替えた順番で新たに読み出された表示情報との間で、さらに描画順序が判定されるので、常に適切な描画順序での描画が可能となる。
【００１５】
上記描画装置において、複数の前記グラフィック要素を表示する場合であって、その複数のグラフィック要素の前記座標が同じ場合、前記ソート手段は、その複数のグラフィック要素に対しては、前記表示情報に含まれる表示深度情報が示す表示深度の昇順あるいは降順のいずれかで前記表示情報を並べる。
【００１６】
この構成によれば、複数のグラフィック要素を表示する場合であって、その複数のグラフィック要素の座標が同じ場合、スクリーンを構成する各ラインにおいて、表示深度の昇順あるいは降順のいずれかで表示情報が並べられる。従って、各ラインにおいて、表示情報に基づくグラフィック要素は、表示深度の大きいもの順あるいは小さいもの順のいずれかで描画される。表示深度の昇順で表示情報を並べる場合は、グラフィック要素は、表示深度が小さいもの順で描画されるので、仮に表示深度が大きいグラフィック要素の描画処理が間に合わなかった場合でも、表示後の見た目の印象を良くすることができる。一方、表示深度の降順で表示情報を並べる場合は、グラフィック要素は、表示深度が大きいもの順で描画されるので、半透明合成を適切に行うことができる。何故ならば、半透明のグラフィック要素の描画色は、当該グラフィック要素の奥にあるグラフィック要素の描画色に依存するため、グラフィック要素を奥から順に描画する必要がある。
【００１７】
この描画装置において、複数の前記グラフィック要素が、前記スクリーンの先頭ラインに表示すべきピクセルを含む場合、前記ソート手段は、その複数のグラフィック要素に対しては、前記座標の大小に関係なく、前記表示深度の昇順あるいは降順のいずれかで前記表示情報を並べる。
【００１８】
この構成によれば、複数のグラフィック要素が、スクリーンの先頭ラインに表示すべきピクセルを含む場合、それらの座標に関係なく、つまり、それらの座標を同一とみなして、表示深度の昇順あるいは降順のいずれかで表示情報が並べられる。従って、先頭ラインにおいて、表示情報に基づくグラフィック要素は、表示深度の大きいもの順あるいは小さいもの順のいずれかで描画される。表示情報を表示座標順（グラフィック要素の、ラインに垂直な方向の位置を示す座標順）でソートし、表示座標の同じものについては表示深度順でソートする場合、先頭ラインの描画においては、必ずしも表示深度の昇順または降順での描画が保証されないが、この構成によれば、先頭ラインから表示深度順での描画を行うことが可能となる。表示深度の昇順で並べる効果及び降順で並べる効果は上記と同様である。
【００１９】
上記描画装置において、前記ソート手段は、所定数分の前記グラフィック要素の前記表示情報の並べ替えが完了するたびに、その旨を前記描画手段に通知し、前記描画手段は、前記ソート手段からの前記通知を受けて、並べ替えが完了した前記表示情報を順次読み出す。
【００２０】
この構成によれば、表示情報のソートが確定するたびに、その都度、その旨の通知がなされるので、描画手段は、全表示情報のソートの完了を待つことなく、逐次、表示情報を読み込むことができる。
【００２１】
この描画装置において、前記所定数分の前記グラフィック要素の前記表示情報は、１つ分の前記グラフィック要素の前記表示情報である。
【００２２】
この構成によれば、１つ分のグラフィック要素のソートが確定するたびに、その旨の通知がなされるので、描画手段は、ソートが確定したグラフィック要素の表示情報をソート完了直後から読み込むことができる。
【００２３】
上記描画装置において、前記描画手段は、第１バッファ及び第２バッファに加えて、さらに、第３バッファ（例えば、図１のプリフェッチバッファ１０８に相当）を含み、この第３バッファは、第３の所定数分の前記グラフィック要素の前記表示情報を格納可能であって、前記ソート手段が並べ替えた順番で読み出される前記表示情報を、読み出された順番で格納し、前記第１バッファに格納すべき期間が到来した前記新たなピクセル情報を生成するための前記表示情報を格納された順番で出力し、前記比較手段は、前記第３バッファから出力される前記表示情報に含まれる表示深度情報と、再利用のために送られてきた順番で格納された前記第２バッファから出力される前記表示情報に含まれる表示深度情報と、を比較し、前記予め定められた規則に従って、いずれかの前記表示情報を選択して先に出力する。
【００２４】
この構成によれば、第３バッファが設けられ、この第３バッファは、ソート手段がソートした順番での表示情報の入力タイミングと比較手段への表示情報の出力タイミングとの緩衝機構である。これにより、ソート手段がソートした順番での表示情報の入力の、描画手段にとっての待ち時間を削減できる。
【００２５】
上記描画装置において、前記予め定められた規則は、前記比較の結果、大きい前記表示深度を示す前記表示深度情報を含む前記表示情報を選択することである。
【００２６】
この構成によれば、グラフィック要素は、表示深度の大きいもの順で描画される。その結果、半透明合成を適切に行うことができる。
【００２７】
上記描画装置において、前記ソート手段が並べ替えを実行する際の前記グラフィック要素の前記座標は、前記グラフィック要素の頂点の座標であって、最も大きい座標あるいは最も小さい座標のいずれかである。
【００２８】
この構成によれば、全てのグラフィック要素に対して同じ条件でソートができるので、正しい描画順序で描画を行うことができる。
【００２９】
上記描画装置において、前記第１バッファは、少なくとも１つの前記ラインを構成する複数の前記ピクセル情報を格納するバッファである。
【００３０】
この構成によれば、フレームバッファを使用する場合よりもコストを低く抑えることができる。また、１ラインに満たないピクセルを格納するピクセルバッファを使用する場合よりも簡素な回路構成で（簡単な制御で）描画を実現できる。
【００３１】
上記描画装置において、前記ソート手段は、前記表示情報の並べ替えを、ヒープソートにより実行する。
【００３２】
この構成によれば、表示情報のソートが１つずつ確定されるので、ソートの確定のたびに、その旨を通知する機構を容易に実現できる。また、全表示情報のソートに必要な時間のバラツキを少なくできる。
【００３３】
上記描画装置において、前記ソート手段は、前記グラフィック要素としてのポリゴンを表示するための前記表示情報と、前記グラフィック要素としてのスプライトを表示するための前記表示情報と、で独立して前記並べ替えを実行する。
【００３４】
この構成によれば、ポリゴンのための表示情報と、スプライトのための表示情報と、の形式及びサイズが異なっている場合でも容易にソートが可能であり、表示情報を格納するためのメモリ領域の使用効率も高まる。
【００３５】
この描画装置において、前記描画手段は、前記ソート手段が並べ替えた前記ポリゴンのための前記表示情報と、前記ソート手段が並べ替えた前記スプライトのための前記表示情報と、を前記ソート手段による並べ替えの規則に準じてマージソートするマージソート手段をさらに含む。
【００３６】
この構成によれば、ポリゴン及びスプライトが独立してソートされた場合であっても、描画処理の前にポリゴンのための表示情報群とスプライトのための表示情報群がマージソートされるため、適切な描画処理が可能となる。
【００３７】
本発明の第２の観点によると、描画装置は、それぞれが複数のピクセルから構成される平行な複数のラインを、そのラインに垂直な方向に並べて構成されるスクリーンに、多角形状のグラフィック要素を含むグラフィック要素ごとの表示情報に基づいて、インタレーススキャンにより前記グラフィック要素の組み合わせからなるスクリーンイメージを表示するための描画を行う描画装置であって、偶数フィールドを表示するために、前記グラフィック要素ごとの表示情報を、第１の規則に従って並べ替え、かつ、奇数フィールドを表示するために、前記グラフィック要素ごとの表示情報を、第２の規則に従って並べ替えるソート手段と、前記奇数フィールドを表示する場合、その表示のために前記ソート手段が並べ替えた前記表示情報を順番に読み出して、読み出した前記表示情報に基づいて、対応する前記グラフィック要素の描画を実行し、かつ、前記偶数フィールドを表示する場合、その表示のために前記ソート手段が並べ替えた前記表示情報を順番に読み出して、読み出した前記表示情報に基づいて、対応する前記グラフィック要素の描画を実行する描画手段と、を備え、前記第１の規則は、前記表示情報に含まれる、前記グラフィック要素の前記ラインに垂直な方向の位置を示す座標が、昇順あるいは降順のいずれかで並ぶように、前記グラフィック要素ごとの前記表示情報を並べ替える際に、前記座標が、スキャンする奇数ライン又はその１つ前の偶数ラインを示す前記グラフィック要素については、当該グラフィック要素の前記座標が同一であるとして、前記表示情報に含まれる表示深度情報が示す表示深度の昇順あるいは降順のいずれかで前記表示情報を並べることであり、前記第２の規則は、前記表示情報に含まれる、前記グラフィック要素の前記座標が、昇順あるいは降順のいずれかで並ぶように、前記グラフィック要素ごとの前記表示情報を並べ替える際に、前記座標が、スキャンする偶数ライン又はその１つ前の奇数ラインを示す前記グラフィック要素については、前記座標が同一であるとして、前記表示情報に含まれる表示深度情報が示す表示深度の昇順あるいは降順のいずれかで前記表示情報を並べることである。
【００３８】
この構成によれば、第１の観点による発明と同様の作用効果を奏することに加えて、次の作用効果を奏する。インタレーススキャンによってスクリーンイメージが表示される場合、表示座標（グラフィック要素の、ラインに垂直な方向の位置を示す座標）が飛び越し走査により飛び越されたラインを示す表示情報と、表示座標が描画対象のラインを示す表示情報とが、表示対象ラインの描画処理において共に読み出される。したがって、これらの表示情報の示す表示座標を同じ値とみなし、表示深度順にソートを行うことにより、インタレーススキャンの場合でも表示深度順での描画処理が保証される。表示深度の昇順で並べる効果及び降順で並べる効果は上記と同様である。
【００３９】
以上の結果、インタレーススキャンによる表示を行う場合においても、少ない記憶容量の、描画のためのバッファ（第１バッファ）を用いながらも、品質の高い三次元イメージの表示を実現できる。
【００４０】
上記描画装置において、前記描画手段は、前記スクリーンを構成する前記ピクセルのうち第１の所定数分のピクセル情報を格納可能であって、格納した前記ピクセル情報を前記スクリーンイメージを表示するために出力し、出力した前記ピクセル情報が格納されていた位置に、前記スクリーンイメージを表示するための新たなピクセル情報を格納する第１バッファと、第２の所定数分の前記グラフィック要素の前記表示情報が格納可能であって、前記表示情報に基づく前記ピクセル情報が前記第１バッファに格納された後に、当該表示情報に基づく他のピクセル情報を前記第１バッファに格納するために、当該表示情報が再利用可能なときに、再利用のために送られてくる順番で、当該表示情報を格納し、前記第１バッファが前記新たなピクセル情報を格納する期間が到来したときに、格納した順番で前記表示情報を出力する第２バッファと、前記奇数フィールドを表示する場合、その表示のために前記ソート手段が並べ替えた順番で読み出された前記表示情報のうち、前記第１バッファに格納すべき期間が到来した前記新たなピクセル情報を生成するための前記表示情報に含まれる前記表示深度情報と、前記第２バッファから出力される前記表示情報に含まれる前記表示深度情報と、を比較し、予め定められた規則に従って、いずれかの前記表示情報を選択して先に出力し、前記偶数フィールドを表示する場合、その表示のために前記ソート手段が並べ替えた順番で読み出された前記表示情報のうち、前記第１バッファに格納すべき期間が到来した前記新たなピクセル情報を生成するための前記表示情報に含まれる前記表示深度情報と、前記第２バッファから出力される前記表示情報に含まれる前記表示深度情報と、を比較し、前記予め定められた規則に従って、いずれかの前記表示情報を選択して先に出力する比較手段と、前記比較手段から出力された前記表示情報に基づいて前記ピクセル情報を生成し、前記生成したピクセル情報を前記第１バッファに書き込む書き込み手段と、を含む。
【００４１】
この構成によれば、第１の観点による発明に加えた第２バッファ及び比較手段と同様の第２バッファ及び比較手段を有している。このため、その場合と同様の作用効果を奏する。
【００４２】
上記描画装置において、複数の前記グラフィック要素が、前記スクリーンの先頭ラインに表示すべきピクセルを含む場合、前記ソート手段は、前記第１の規則及び前記第２の規則を適用せず、その複数のグラフィック要素に対しては、前記表示深度の昇順あるいは降順のいずれかで前記表示情報を並べる。
【００４３】
この構成によれば、第１の観点による発明に加えた、複数のグラフィック要素がスクリーンの先頭ラインに表示すべきピクセルを含む場合の並べ替えの規則と同じ規則を有している。このため、その場合と同様の作用効果を奏する。
【００４４】
上記描画装置において、前記ソート手段は、所定数分（好ましくは、１つ分）の前記グラフィック要素の前記表示情報の並べ替えが完了するたびに、その旨を前記描画手段に通知し、かつ、前記奇数フィールドを表示するための前記並べ替えを、当該奇数フィールドを表示する直前の垂直ブランキング期間の開始直後に実行開始し、前記偶数フィールドを表示するための前記並べ替えを、当該偶数フィールドを表示する直前の垂直ブランキング期間の開始直後に実行開始する。
【００４５】
ソートが確定する毎にその旨を通知することにより、描画手段はソートの完了を待たずに描画処理を行うことが可能であるが、さらにこの構成によれば、垂直ブランキング期間の開始直後にソートが実行開始されるので、ソート前の演算処理のために余裕を持ったより十分な時間を確保できる。
【００４６】
本発明の新規な特徴は、請求の範囲に記載されている。しかしながら、発明そのもの及びその他の特徴と効果は、添付図面を参照して具体的な実施例の詳細な説明を読むことにより容易に理解される。
【図面の簡単な説明】
【００４７】
【図１】図１（ａ）は、本発明の実施の形態によるＹＳＵ１９が実行するソートルール１を説明するための、スクリーンＳＣＲに表示されたポリゴン＃０〜＃７の例示図である。図１（ｂ）は、ソートルール１に従ったソートの例示図である。
【図２】図２（ａ）は、ＹＳＵ１９が実行するソートルール２を説明するための、スクリーンＳＣＲに表示されたポリゴン＃０〜＃７の例示図である。図２（ｂ）は、ソートルール２に従ったソートの例示図である。
【図３】図３（ａ）は、ＹＳＵ１９が実行するソートルール３を説明するための、スクリーンＳＣＲに表示されたポリゴン＃０〜＃７の例示図である。図３（ｂ）は、ソートルール３に従ったソートの例示図である。
【図４】図４は、本発明の実施の形態によるＲＰＵ１９の前段部分の説明図である。
【図５】図５（ａ）は、ＲＰＵ９のプリフェッチバッファ１０８、リサイクルバッファ１１０、及びデプスコンパレータ１１２の処理を説明するための、スクリーンＳＣＲに表示されたポリゴンの例示図である。図５（ｂ）は、ＲＰＵ９による描画処理の前処理としてのＹＳＵ１９によるソーティング結果の例示図である。
【図６】図６（ａ）は、図５（ａ）のラインＬｃの１つ前のラインの表示のための描画が終了した直後の、プリフェッチバッファ１０８及びリサイクルバッファ１１０の格納状態を示す図である。図６（ｂ）は、ポリゴン＃１，＃２及び＃４の対応するピクセルをラインＬｃに描画する際のポリゴン構造体インスタンスの流れを示す図である。図６（ｃ）は、ポリゴン＃１，＃２及び＃４の対応するピクセルをラインＬｃに描画する際のポリゴン構造体インスタンスの流れを示す図である。図６（ｄ）は、ポリゴン＃１，＃２及び＃４の対応するピクセルをラインＬｃに描画する際のポリゴン構造体インスタンスの流れを示す図である。図６（ｅ）は、ラインＬｃの表示のための描画が終了した直後の、プリフェッチバッファ１０８及びリサイクルバッファ１１０の格納状態を示す図である。
【図７】図７（ａ）は、図５（ｂ）のポリゴン構造体インスタンス＃０，＃３，＃１及び＃２がプリフェッチバッファ１０８に格納された状態を示す図である。図７（ｂ）は、図５（ａ）のポリゴン＃０及び＃３の対応するピクセルをラインＬａに描画する際のポリゴン構造体インスタンスの流れを示す図である。図７（ｃ）は、図５（ａ）のポリゴン＃０及び＃３の対応するピクセルをラインＬａに描画する際のポリゴン構造体インスタンスの流れを示す図である。図７（ｄ）は、ポリゴン＃０及び＃３の表示最終ラインＬｂの描画に至るまでのポリゴン構造体インスタンスの流れを示す図である。図７（ｅ）は、ポリゴン＃０及び＃３の表示最終ラインＬｂの描画でのポリゴン構造体インスタンスの流れを示す図である。
【図８】図８は、インタレーススキャンによる表示を行う場合のＹＳＵ１９によるソートルール４の説明図である。
【図９】図９（ａ）は、インタレーススキャンによる表示を行う場合のソート処理をモード１のタイミングで行う場合の説明図である。図９（ｂ）は、インタレーススキャンによる表示を行う場合のソート処理をモード２のタイミングで行う場合の説明図である。
【図１０】図１０は、本発明の実施の形態によるマルチメディアプロセッサ１の内部構成を示すブロック図である。
【図１１】図１１は、図１０のマルチメディアプロセッサ１によるグラフィックス処理の流れの概要を示すフローチャートである。
【図１２】図１２は、図１０のＲＰＵ９の内部構成を示すブロック図である。
【図１３】図１３は、テクスチャマッピングモードのポリゴン構造体の構成を示す図である。
【図１４】図１４は、テクスチャアトリビュート構造体の構成を示す図である。
【図１５】図１５は、グーローシェーディングモードのポリゴン構造体の構成を示す図である。
【図１６】図１６（ａ）は、シザリングディセーブル時のスプライト構造体の構成を示す図である。図１６（ｂ）は、シザリングイネーブル時のスプライト構造体の構成を示す図である。
【図１７】図１７は、スライサ１１８による、グーローシェーディングモードのポリゴンに対する処理の説明図である。
【図１８】図１８は、スライサ１１８による、テクスチャマッピングモードのポリゴンに対する処理の説明図である。
【図１９】図１９は、スライサ１１８によるスプライトに対する処理の説明図である。
【図２０】図２０は、ピクセルディザ１２２によるディザリングの説明図である。
【図２１】図２１は、バイリニアフィルタ１３０によるバイリニアフィルタリングの説明図である。
【図２２】図２２は、図１０のＹＳＵ１９による配列ＡのＹソート完了後のヒープ構造を示す図である。
【図２３】図２３は、図２２のヒープ構造のメインＲＡＭ２５への格納方法の説明図である。
【図２４】図２４は、図１０のＹＳＵ１９によるポリゴン構造体配列のＹソート処理の全体的な流れの一例を示すフローチャートである。
【図２５】図２５は、図２４のステップＳ２１のヒープ構築処理の流れの一例を示すフローチャートである。
【図２６】図２６は、ダウンヒープ処理の流れの一例を示すフローチャートである。
【図２７】図２７は、順位比較処理の流れの一例を示すフローチャートである。
【発明を実施するための形態】
【００４８】
以下、本発明の実施の形態について、図面を参照しながら説明する。なお、図中、同一または相当部分については同一の参照符号を付してその説明を援用する。数式中「・」は乗算を意味する。
【００４９】
まず、本発明の実施の形態による３次元イメージ表示のための描画処理の原理を説明する。本実施の形態では、描画処理の前処理として、後述のＹソーティングユニット（以下、「ＹＳＵ」と呼ぶ。）１９によるソート（「Ｙソート」と呼ぶこともある。）処理が実行される。ソートの対象は、構造体配列の各要素である。構造体配列は、二次元空間に投影された三次元立体の各面の形状を表すための多角形状のグラフィック要素であるポリゴンのための構造体配列（以下、「ポリゴン構造体配列」と呼ぶ。）と、スクリーンに平行な矩形状のグラフィック要素であるスプライトのための構造体配列（以下、「スプライト構造体配列」と呼ぶ。）と、が後述のメインＲＡＭ（ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ）２５に用意される。ポリゴン構造体配列の要素は、「ポリゴン構造体インスタンス」であり、スプライト構造体配列の要素は、「スプライト構造体インスタンス」である。ただし、両者を区別して説明する必要がないときは、単に「構造体インスタンス」と呼ぶこともある。
【００５０】
ポリゴン構造体配列に格納された各ポリゴン構造体インスタンスは、ポリゴンごとの表示情報（スクリーンにおける頂点座標、テクスチャマッピングモードでのテクスチャパターンに関する情報及びグーローシェーディングモードでのカラーデータ（ＲＧＢのカラーコンポーネント）を含む。）であり、１つのポリゴン構造体インスタンスに１つのポリゴンが対応している。スプライト構造体配列に格納された各スプライト構造体インスタンスは、スプライトごとの表示情報（スクリーンにおける座標及びテクスチャパターンに関する情報を含む。）であり、１つのスプライト構造体インスタンスに１つのスプライトが対応している。これらについては、後で詳述する。
【００５１】
以下、ＹＳＵ１９によるソートルール１，２及び３について説明するが、その前に座標系について説明する。ディスプレイ装置（図示せず）への実際の表示に用いられる二次元座標系をスクリーン座標系と呼ぶ。本実施の形態では、スクリーン座標系は、水平方向２０４８ピクセル×垂直方向１０２４ピクセルの２次元ピクセル配列から構成される。座標原点は左上にあり、水平右方向がＸ軸の正、垂直下方向がＹ軸の正に相当する。ただし、実際に表示される領域は、スクリーン座標系の全空間ではなく一部の空間である。この表示領域をスクリーンと呼ぶことにする。
【００５２】
図１（ａ）は、ＹＳＵ１９が実行するソートルール１を説明するための、スクリーンＳＣＲに表示されたポリゴン＃０〜＃７の例示図である。図１（ｂ）は、ソートルール１に従ったソートの例示図である。図１（ｂ）に示すように、ポリゴン構造体配列ＰＳには、図１（ａ）のポリゴン＃０〜＃７に対応するポリゴン構造体インスタンス＃０〜＃７が格納されている。なお、対応するポリゴン及びポリゴン構造体インスタンスには、同一の参照符号を付している。
【００５３】
ＹＳＵ１９は、ポリゴン＃０〜＃７のＹ座標が小さい順に、各ポリゴン構造体インスタンス＃０〜＃７を並べ替える。この場合、ポリゴンの３頂点のＹ座標のうち、最も小さいＹ座標（以下、「最小Ｙ座標」と呼ぶ。）が、この並べ替えで用いるポリゴンのＹ座標とする。
【００５４】
このソートの結果、図１（ｂ）の右側に示すように、最小Ｙ座標が小さい順に、各ポリゴン構造体インスタンス＃０〜＃７が並べ替えられる。
【００５５】
以上のように、最小Ｙ座標が小さい順に、各ポリゴン構造体インスタンスを並べ替えることをソートルール１と呼ぶ。
【００５６】
ただし、最小Ｙ座標が同一である複数のポリゴンも存在しうる。この場合は、ソートルール２に従う。
【００５７】
図２（ａ）は、ＹＳＵ１９が実行するソートルール２を説明するための、スクリーンＳＣＲに表示されたポリゴン＃０〜＃７の例示図である。図２（ｂ）は、ソートルール２に従ったソートの例示図である。図２（ａ）に示すように、スクリーンＳＣＲにおいて、ポリゴン＃０、＃１、及び＃７の最小Ｙ座標は、共に「Ｙｓ」であり同一である。この場合、ＹＳＵ１９は、各ポリゴン構造体インスタンス＃０、＃１、及び＃７に含まれるデプス値が大きい順に、各ポリゴン構造体インスタンス＃０、＃１、及び＃７を並べ替える。
【００５８】
このソートの結果、図２（ｂ）の右側に示すように、ポリゴン構造体インスタンス＃０、＃１、及び＃７については、デプス値が大きい順に並べ替えられている。
【００５９】
デプス値（「表示深度情報」と呼ぶこともある。）は、描画対象のピクセルが重なった場合、どのピクセルを先に描画するかを示す情報であり、その値が大きいほど先に（奥に）描画され、その値が小さいほど後で（手前に）描画される。つまり、デプス値が大きいほどスクリーンＳＣＲの奥に表示することが示され、小さいほど手前に表示することが示される。
【００６０】
以上のように、最小Ｙ座標が同じである複数のポリゴンについては、デプス値が大きい順に、各ポリゴン構造体インスタンスを並べることがソートルール２である。
【００６１】
ただし、ＹＳＵ１９は、スクリーンＳＣＲの先頭ラインに表示されるピクセルを持つ複数のポリゴンについては、最小Ｙ座標が異なっている場合でも、それらが同一であるとみなして、ソートルール１ではなく、ソートルール２に従って、各ポリゴン構造体インスタンスの並べ替えを行う。つまり、スクリーンＳＣＲの先頭ラインに表示されるピクセルを持つポリゴンが複数存在する場合は、最小Ｙ座標が同一であるとみなして（つまり、最小Ｙ座標の値に関係なく）、デプス値が大きい順に並べ替えられる。これをソートルール３と呼ぶことにする。
【００６２】
図３（ａ）は、ＹＳＵ１９が実行するソートルール３を説明するための、スクリーンＳＣＲに表示されたポリゴン＃０〜＃７の例示図である。図３（ｂ）は、ソートルール３に従ったソートの例示図である。図３（ａ）に示すように、スクリーンＳＣＲの先頭ラインに表示されるピクセルを持つポリゴン＃２、＃５、及び＃７の最小Ｙ座標は、異なっている。この場合、ＹＳＵ１９は、ポリゴン＃２、＃５、及び＃７の最小Ｙ座標が同一であるとみなして、各ポリゴン構造体インスタンス＃２、＃５、及び＃７に含まれるデプス値が大きい順に、各ポリゴン構造体インスタンス＃２、＃５、及び＃７を並べ替える。
【００６３】
このソートの結果、図３（ｂ）の右側に示すように、ポリゴン構造体インスタンス＃２、＃５、及び＃７については、デプス値が大きい順に並べ替えられている。
【００６４】
以上のように、先頭ラインに表示されるピクセルを持つ複数のポリゴンについては、最小Ｙ座標が異なっている場合でも、ソートルール１ではなく、最小Ｙ座標が同一であるとみなして、ソートルール２に従い、デプス値の大きい順に、各ポリゴン構造体インスタンスを並べ替えることがソートルール３である。
【００６５】
上記のソートルール１〜３は、スプライト構造体配列の各スプライト構造体インスタンスを並べ替える際にも適用される。ここで、スプライトの最小Ｙ座標は、スプライトの４頂点のＹ座標のうち、最も小さいＹ座標である。
【００６６】
後で詳述するが、本実施の形態では、ポリゴン構造体のサイズは、１２８ビットであり、スプライト構造体のサイズは、６４ビットである。このように、ポリゴンとスプライトでは、構造体のサイズが異なるので、構造体インスタンスの並べ替えは、ポリゴン構造体配列とスプライト構造体配列とで、それぞれ別個に行われる。
【００６７】
ここで、ソートルール１によるソートを行う効果を説明する。比較のため、各ラインの描画のたびに、該当ラインに描画すべきポリゴン構造体インスタンス及びスプライト構造体インスタンスを、全ポリゴン構造体インスタンス及び全スプライト構造体インスタンスから検索して、描画処理を行うことを想定する。この比較例では、各ラインの描画のたびに、全ポリゴン構造体インスタンス及び全スプライト構造体インスタンスからの検索処理が必要となり、高速処理ができず、多くのポリゴン及びスプライトの表示ができない場合も発生して、十分な三次元イメージの表示が不可能な場合もある。
【００６８】
この点、本実施の形態のように、最小Ｙ座標が小さい順に、各ポリゴン構造体インスタンス及び各スプライト構造体インスタンスを予めソートしておくことにより、ソート後の各ポリゴン構造体インスタンス及び各スプライト構造体インスタンスを順番に読み出して、描画処理を行うだけでよい。この際に、最小Ｙ座標が描画対象位置のＹ座標より大きい構造体インスタンスがソート済みの構造体配列より読み出された場合に、そのラインの描画処理を停止することにより、不要な構造体インスタンスの検索処理を全く行わずに済む。その結果、比較例のような検索処理が不要になって、処理の高速化を図ることができ、多くのポリゴン及びスプライトの表示が可能になって、十分な三次元イメージの表示が可能になる。
【００６９】
但し、本実施の形態では、ピクセルを格納するバッファに対する描画処理を水平ライン単位で行っているので、対象となる水平ラインに描画すべきピクセルを持つポリゴン及びスプライトの構造体インスタンスを、水平ライン毎に順番に読み出して処理する必要がある。
【００７０】
そこで、本実施の形態においては、後述するように、複数ラインに跨るポリゴン及びスプライトの構造体インスタンスを再利用することにより、それらをメモリから毎回取得することを避ける機構、新たにメモリから読み出した構造体インスタンスと再利用のためのバッファに格納された構造体インスタンスとの描画順序を判定する機構、及び全てのピクセルを描画し終えた構造体インスタンスを再利用のためのバッファに格納せずに破棄する機構を備える。
【００７１】
上記のように、表示先頭ラインでの複数グラフィック要素（ポリゴン、スプライト）の描画や、同じラインで最小Ｙ座標が同一の複数グラフィック要素の描画の場合に、ソートルール２及び３を追加したのは、各ラインにおいて、必ず、デプス値が大きいものから描画されるようにするためである。本実施の形態においては、ソート済みの構造体配列から読み出された構造体インスタンスのデプス値と、再利用のためのバッファから読み出された構造体インスタンスのデプス値とを比較し、より大きいデプス値を持つ構造体インスタンスを先に描画する機構を備えているので、ソートルール２及び３の追加によって、全ての構造体インスタンスに対して、必ずデプス値が大きいものから描画を行うことを保証できる。
【００７２】
このように、各ラインにおいて、デプス値の大きい、より奥に表示されるべきグラフィック要素から先に描画処理を行うようにしたのは、半透明合成を実現するためである。奥に描画されるべき不透明のグラフィック要素が、手前に描画されるべき半透明のグラフィック要素の後に描画された場合、透けて見えるべき両者が重なった部分の描画を正しく処理することができない。このため、各ラインにおいて、デプス値の大きい、より奥に表示されるべきグラフィック要素から先に描画処理を行うのである。
【００７３】
さて、ＹＳＵ１９によるソート後の各構造体インスタンスは、メインＲＡＭ２５から、後述のレンダリングプロセッシングユニット（以下、「ＲＰＵ」と呼ぶ。）９に読み込まれ、描画処理に利用される。この描画処理の前段の処理を説明する。ここで、本実施の形態では、後述のラインバッファＬＢ１あるいはＬＢ２にデータを書き込むことを描画と呼ぶ。各ラインバッファＬＢ１及びＬＢ２は、スクリーンの１ラインに対応したピクセルのデータを格納する。
【００７４】
図４は、本発明の実施の形態によるＲＰＵ１９の前段部分の説明図である。図４に示すように、ＲＰＵ１９は、その前段部分に、プリフェッチバッファ１０８、リサイクルバッファ１１０、及びデプスコンパレータ１１２を含む。
【００７５】
プリフェッチバッファ１０８は、メインＲＡＭ２５から、ソート後の構造体インスタンスを順次読み込み、読み込んだ順番で構造体インスタンスを出力するＦＩＦＯ（ｆｉｒｓｔ−ｉｎ  ｆｉｒｓｔ−ｏｕｔ）構造のバッファである。つまり、プリフェッチバッファ１０８には、ＹＳＵ１９により並べ替えられた順番で構造インスタンスが格納される。そして、格納された構造インスタンスは、対応するポリゴンあるいはスプライトの表示のための描画サイクルにおいて、格納された順番で出力される。プリフェッチバッファ１０８は、メインＲＡＭ２５からの入力タイミングとデプスコンパレータ１１２への出力タイミングの緩衝機構として用意されている。これは、メインＲＡＭ２５は、ＲＰＵ１９以外の機能ユニットと共有されているため、メインＲＡＭ２５からのデータ取得に待ち時間が発生し得るためである。
【００７６】
リサイクルバッファ１１０は、次の描画サイクルでも使用される（つまり、再利用できる）構造体インスタンスを格納するＦＩＦＯ構造のバッファである。従って、リサイクルバッファ１１０に格納された構造体インスタンスは、次の描画サイクルで使用される。１描画サイクルは、１ラインの表示を行うための描画期間である。つまり、１描画サイクルは、ラインバッファＬＢ１あるいはＬＢ２のいずれかに、対応するラインの表示のために必要な全てのデータの描画が行われる期間である。
【００７７】
デプスコンパレータ１１２は、プリフェッチバッファ１０８から取り出した構造体インスタンスに含まれるデプス値と、リサイクルバッファ１１０から取り出した構造体インスタンスに含まれるデプス値と、を比較して、より大きなデプス値を持つ（つまり、より奥に表示されるべき）構造体インスタンスを選択して、後段に出力する。
【００７８】
この場合、選択された構造体インスタンスが、次の描画サイクルでも使用される（つまり、次のラインの描画にも使用される）場合は、後段に出力されるとともに、リサイクルバッファ１１０にも出力され書き込まれる。ただし、選択された構造体インスタンスが、次の描画サイクルで使用されない（つまり、次のラインの描画には使用されない）場合は、後段に出力されるだけで、リサイクルバッファ１１０には書き込まれない。
【００７９】
従って、リサイクルバッファ１１０には、現ラインの描画に使用される構造体インスタンスであって、次ラインの描画にも使用される構造体インスタンスのみが、デプス値の大きい順に格納される。以下、具体例を挙げながら説明する。
【００８０】
図５（ａ）は、ＲＰＵ９のプリフェッチバッファ１０８、リサイクルバッファ１１０、及びデプスコンパレータ１１２の処理を説明するための、スクリーンＳＣＲに表示されたポリゴンの例示図である。図５（ｂ）は、ＲＰＵ９による描画処理の前処理としてのＹＳＵ１９によるソーティング結果の例示図である。
【００８１】
図６（ａ）は、図５（ａ）のラインＬｃの１つ前のラインの表示のための描画が終了した直後の、プリフェッチバッファ１０８及びリサイクルバッファ１１０の格納状態を示す図、図６（ｂ）〜図６（ｄ）は、ポリゴン＃１，＃２及び＃４に含まれる、ラインＬｃに対応するピクセルを描画する際のポリゴン構造体インスタンスの流れを示す図、図６（ｅ）は、ラインＬｃへの表示のための描画が終了した直後の、プリフェッチバッファ１０８及びリサイクルバッファ１１０の格納状態を示す図、である。
【００８２】
図６（ａ）に示すように、図５（ａ）のラインＬｃの１つ前のラインの表示のための描画が終了した直後では、プリフェッチバッファ１０８には、図５（ｂ）に示したソート後の並びの順で、ポリゴン構造体インスタンス＃４，＃７，＃６及び＃５が格納され、リサイクルバッファ１１０には、デプス値が大きい順番で、ポリゴン構造体インスタンス＃１及＃２が格納されている。なお、ポリゴン構造体インスタンス＃０及び＃３は、ラインＬｃに表示されないため、リサイクルバッファ１１０には格納されていない。
【００８３】
そして、図６（ｂ）に示すように、デプスコンパレータ１１２は、プリフェッチバッファ１０８の先頭のポリゴン構造体インスタンス＃４と、リサイクルバッファ１１０の先頭のポリゴン構造体インスタンス＃１と、に含まれるデプス値を比較し、デプス値が大きいポリゴン構造体インスタンス＃１を選択して、後段に出力するとともに、ポリゴン構造体インスタンス＃１は、リサイクルバッファ１１０に送られる。なぜなら、ポリゴン＃１は、次のラインにも表示されため、次の描画サイクルでも利用されるからである。この場合、ポリゴン構造体インスタンス＃４は、デプスコンパレータ１１２に選択されていないので、プリフェッチバッファ１０８のリードポインタは、次に進まず、ポリゴン構造体インスタンス＃４を指したままである。
【００８４】
次に、図６（ｃ）に示すように、デプスコンパレータ１１２は、プリフェッチバッファ１０８の先頭のポリゴン構造体インスタンス＃４と、リサイクルバッファ１１０の先頭のポリゴン構造体インスタンス＃２と、に含まれるデプス値を比較し、デプス値が大きいポリゴン構造体インスタンス＃４を選択して、後段に出力するとともに、ポリゴン構造体インスタンス＃４は、リサイクルバッファ１１０に送られる。なぜなら、ポリゴン＃４は、次のラインにも表示されため、次の描画サイクルでも利用されるからである。この場合、ポリゴン構造体インスタンス＃２は、デプスコンパレータ１１２に選択されていないので、リサイクルバッファ１１０のリードポインタは、次に進まず、ポリゴン構造体インスタンス＃２を指したままである。
【００８５】
そして、図６（ｄ）に示すように、デプスコンパレータ１１２は、リサイクルバッファ１１０の先頭のポリゴン構造体インスタンス＃２を読み込んで、後段に出力するとともに、ポリゴン構造体インスタンス＃２は、リサイクルバッファ１１０に送られる。なぜなら、ポリゴン＃２は、次のラインにも表示されるため、次の描画サイクルでも利用されるからである。
【００８６】
以上の結果、ラインＬｃの表示のための描画が終了した直後では、リサイクルバッファ１１０には、次のラインの描画に利用されるポリゴン構造体インスタンス＃１，＃４及び＃２が、デプス値の大きい順に格納される。なお、ラインＬｃには、ポリゴン＃７は表示されないため、図６（ｅ）において、ポリゴン構造体インスタンス＃７は、プリフェッチバッファ１０８から読み出されない。
【００８７】
図７（ａ）は、図５（ｂ）のポリゴン構造体インスタンス＃０，＃３，＃１及び＃２がプリフェッチバッファ１０８に格納された状態を示す図、図７（ｂ）及び図７（ｃ）は、図５（ａ）のポリゴン＃０及び＃３に含まれる、ラインＬａに対応するピクセルを描画する際のポリゴン構造体インスタンスの流れを示す図、図７（ｄ）は、ポリゴン＃０及び＃３の表示最終ラインＬｂに至るまでのポリゴン構造体インスタンスの流れを示す図、図７（ｅ）は、ポリゴン＃０及び＃３の表示最終ラインＬｂでのポリゴン構造体インスタンスの流れを示す図、である。
【００８８】
図７（ａ）に示すように、図５（ａ）の先頭ラインＬａへの表示のための描画の前に、プリフェッチバッファ１０８には、図５（ｂ）に示したソート後のポリゴン構造体インスタンスが、その並びの順で格納される。
【００８９】
そして、図７（ｂ）に示すように、プリフェッチバッファ１０８の先頭のポリゴン構造体インスタンス＃０が、デプスコンパレータ１１２に読み込まれ、デプスコンパレータ１１２は、このポリゴン構造体インスタンス＃０を後段に出力するとともに、ポリゴン構造体インスタンス＃０は、リサイクルバッファ１１０に送られ格納される。なぜなら、ポリゴン＃０は、次のラインにも表示されため、次の描画サイクルでも利用されるからである。なお、プリフェッチバッファ１０８には、メインＲＡＭ２５から読み出されたポリゴン構造体インスタンス＃４が書き込まれる。
【００９０】
次に、図７（ｃ）に示すように、プリフェッチバッファ１０８の先頭のポリゴン構造体インスタンス＃３が、デプスコンパレータ１１２に読み込まれ、後段に出力されるとともに、ポリゴン構造体インスタンス＃３は、リサイクルバッファ１１０に送られ格納される。なぜなら、ポリゴン＃３も、次のラインに表示されため、次の描画サイクルでも利用されるからである。なお、プリフェッチバッファ１０８には、メインＲＡＭ２５から読み出されたポリゴン構造体インスタンス＃７が書き込まれる。
【００９１】
先頭ラインＬａの表示のための描画が終了すると、次のラインの表示のための描画をすべく、図７（ｄ）に示すように、デプスコンパレータ１１２は、リサイクルバッファ１１０から、ポリゴン構造体インスタンス＃０を読み出して、後段に出力するとともに、ポリゴン構造体インスタンス＃０は、リサイクルバッファ１１０に送られ格納される。なぜなら、ポリゴン＃０は、引き続き次のラインに表示されるため、次の描画サイクルでも利用されるからである。続いて、デプスコンパレータ１１２は、リサイクルバッファ１１０から、ポリゴン構造体インスタンス＃３を読み出して、後段に出力するとともに、ポリゴン構造体インスタンス＃３は、リサイクルバッファ１１０に送られ格納される。なぜなら、ポリゴン＃３もまた、引き続き次のラインに表示されるため、次の描画サイクルでも利用されるからである。このような処理が、ポリゴン＃０及び＃３の描画が終了するまで繰り返される。なお、ポリゴン＃１は未だ表示されないため、プリフェッチバッファ１０８からは読み出されない。
【００９２】
そして、図７（ｅ）に示すように、ラインＬｂへポリゴン＃０及び＃３を表示するための描画処理では、デプスコンパレータ１１２は、リサイクルバッファ１１０から、ポリゴン構造体インスタンス＃０を読み出して、後段に出力するが、ポリゴン構造体インスタンス＃０は、リサイクルバッファ１１０には送られない。なぜなら、ポリゴン＃０は、次のラインでは表示されず不要だからである。続いて、デプスコンパレータ１１２は、リサイクルバッファ１１０から、ポリゴン構造体インスタンス＃３を読み出して、後段に出力するが、ポリゴン構造体インスタンス＃３は、リサイクルバッファ１１０に送られない。なぜなら、ポリゴン＃３もまた、次のラインには表示されず不要だからである。
【００９３】
上記では、ポリゴンのみをスクリーンＳＣＲに表示する場合を例に挙げたため、プリフェッチバッファ１０８に読み込まれる構造体インスタンスは、ポリゴン構造体インスタンスのみであった。しかし、後述するように、ソート後のポリゴン構造体インスタンスと、ソート後のスプライト構造体インスタンスと、はソートルール１〜３に従ってマージソートされるため、マージソート後の構造体インスタンスが、プリフェッチバッファ１０８に格納されることになる。従って、ポリゴン及びスプライトの双方を表示する場合は、ソートルール１〜３に従った順番で、プリフェッチバッファ１０８に、各構造体インスタンスが格納され、上記のような処理が行われる。
【００９４】
以上のように、デプスコンパレータ１１２及びリサイクルバッファ１１０を設け、次の描画サイクルで利用する構造体インスタンスを、デプス値の大きい順に格納していった。これにより、ＹＳＵ１９によるソートルール１のソートを行うにもかかわらず、各ラインにおいて、必ず、デプス値の大きいグラフィック要素（ポリゴン、スプライト）から描画処理が行われる。
【００９５】
さて、上記のソートルール１〜３は、ノンインタレーススキャンによる表示を行う場合に限らず、インタレーススキャンによる表示を行う場合にも、同様に適用される。ただし、インタレーススキャンの場合は、ソートルール１〜３だけでなく、次のようなソートルール４をさらに加えることが望ましい。
【００９６】
インタレーススキャンの場合でも、上記ソートルール１〜３が適用される。ただし、奇数フィールドを表示するためのソートでは、奇数ラインに表示されるポリゴンの最小Ｙ座標及び／又はその奇数ラインの１つ前の偶数ラインに表示されるポリゴンの最小Ｙ座標とが同一であるとみなして、ソートルール２によるソートを行う。ただし、先頭の奇数ラインは除く。なぜなら、その１つ前の偶数ラインが存在しないからである。一方、偶数フィールドを表示するためのソートでは、偶数ラインに表示されるポリゴンの最小Ｙ座標及び／又はその偶数ラインの１つ前の奇数ラインに表示されるポリゴンの最小Ｙ座標とが同一であるとみなして、ソートルール２によるソートを行う。このようなソートをソートルール４と呼ぶ。
【００９７】
図８は、インタレーススキャンによる表示を行う場合のＹＳＵ１９によるソートルール４の説明図である。図８に示すように、スクリーンＳＣＲに、ポリゴン＃０〜＃３を表示する場合を想定し、まず、奇数フィールドを表示するためのソート処理を考える。図中、上から第二番目の奇数ラインに注目する。
【００９８】
この場合、ソートルール４によれば、第二番目の奇数ラインに初めて表示されるポリゴン＃２の最小Ｙ座標とその１つ前の偶数ラインに初めて表示されるポリゴン＃１の最小Ｙ座標と、が同一であるとみなして、デプス値の大きい順に、ポリゴン構造体インスタンス＃２、次にポリゴン構造体インスタンス＃１と並べられる。
【００９９】
図８の例では、ソートルール１〜４によるソートの結果、奇数フィールドの表示のために、ポリゴン構造体インスタンスは、＃０、＃２、＃１、及び＃３の順番で並べ替えられる。ちなみに、ソートルール１〜３のみでは、ポリゴン構造体インスタンスは、＃０、＃１、＃２、及び＃３の順番で並べ替えられる。
【０１００】
次に、偶数フィールドを表示するためのソート処理を考え、図中、一番上の偶数ラインに注目する。この場合、ソートルール４によれば、一番上の偶数ラインに初めて表示されるポリゴン＃１の最小Ｙ座標とその１つ前の奇数ラインに初めて表示されるポリゴン＃０の最小Ｙ座標と、が同一であるとみなして、デプス値の大きい順に、ポリゴン構造体インスタンス＃１、次にポリゴン構造体インスタンス＃０と並べられる。
【０１０１】
図８の例では、ソートルール１〜４によるソートの結果、偶数フィールドの表示のために、ポリゴン構造体インスタンスは、＃１、＃０、＃３、及び＃２の順番で並べ替えられる。ちなみに、ソートルール１〜３のみでは、ポリゴン構造体インスタンスは、＃０、＃１、＃２、及び＃３の順番で並べ替えられる。
【０１０２】
上記ソートルール４は、ソートルール１〜３に加えて、スプライト構造体配列の各スプライト構造体インスタンスを並べ替える際にも適用される。
【０１０３】
ここで、インタレーススキャンの場合に、ソートルール４を追加した理由を説明する。図８において、ソートルール１〜３のみでソートを行う場合を想定する。この場合、ポリゴン構造体インスタンス＃０，＃１，＃２及び＃３という順番で、最小Ｙ座標が小さい順にソートが行われる。すると、奇数フィールドを表示する場合、例えば、図中、上から第一番目の奇数ラインの描画が終了した直後では、プリフェッチバッファ１０８の先頭には、ポリゴン構造体インスタンス＃１が、リサイクルバッファ１１０の先頭には、ポリゴン構造体インスタンス＃０がある。従って、図中、上から第二番目の奇数ラインの描画を行う際、ポリゴン＃１，＃２及び＃０という順番で描画が行われる。このように、この奇数ラインでは、デプス値が大きい順に、描画が行われなくなる。
【０１０４】
ソートルール４を追加することにより、奇数フィールドを表示する場合、ポリゴン構造体インスタンス＃０，＃２，＃１及び＃３という順番に並べ替えが行われる。すると、奇数フィールドを表示する場合、例えば、図中、上から第一番目の奇数ラインの描画が終了した直後では、プリフェッチバッファ１０８の出口には、ポリゴン構造体インスタンス＃２が、リサイクルバッファ１１０の出口には、ポリゴン構造体インスタンス＃０がある。従って、図中、上から第二番目の奇数ラインの描画を行う際、ポリゴン＃２，＃１及び＃０という順番で、デプス値の大きい順に描画処理が実行される。
【０１０５】
以上のことは、偶数フィールドを表示する際にも言える。
【０１０６】
さて、インタレーススキャンによる表示を行うためのソート処理においては、ソートを実行するタイミングによって、奇数フィールド用のソート処理と偶数フィールド用のソート処理を行うタイミングが異なる。そこで、本実施の形態では、モード１とモード２の二つのソートのモードが用意されている。これらを図面を用いて説明する。
【０１０７】
図９（ａ）は、インタレーススキャンによる表示を行う場合のソート処理をモード１のタイミングで行う場合の説明図、図９（ｂ）は、インタレーススキャンによる表示を行う場合のソート処理をモード２のタイミングで行う場合の説明図、である。
【０１０８】
図９（ａ）に示すように、モード１では、ＹＳＵ１９は、偶数フィールドＢが表示される前に表示される奇数フィールドＡの表示中に、当該偶数フィールドＢを表示するためのソートＢを行う。従って、偶数フィールドＢのための、ポリゴン構造体配列やスプライト構造体配列に代入する値（つまり各構造体インスタンスの値）の計算Ｂ及びソートＢの双方の処理は、当該偶数フィールドＢの１つ前に表示される奇数フィールドＡの表示中に全て完了しなければならない。なぜなら、計算Ｂの結果に基づいて、ソートＢが行われるからである。
【０１０９】
同様に、モード１では、ＹＳＵ１９は、奇数フィールドＡが表示される前に表示される偶数フィールドＢの表示中に、当該奇数フィールドＡを表示するためのソートＡを行う。従って、奇数フィールドＡのための、ポリゴン構造体配列やスプライト構造体配列に代入する値の計算Ａ及びソートＡの双方の処理は、当該奇数フィールドＡの１つ前に表示される偶数フィールドＢの表示中に全て完了しなければならない。なぜなら、計算Ａの結果に基づいて、ソートＡが行われるからである。
【０１１０】
一方、モード２では、図９（ｂ）に示すように、ＹＳＵ１９は、直前の垂直ブランキング期間中及び奇数フィールドＡの表示中に、当該奇数フィールドＡのためのソートＡを実行する。奇数フィールドＡのための計算Ａは、当該奇数フィールドＡの１つ前の偶数フィールドＢの表示中に行われる。同様に、モード２では、ＹＳＵ１９は、直前の垂直ブランキング期間中及び偶数フィールドＢの表示中に、当該偶数フィールドＢのためのソートＢを実行する。偶数フィールドＢのための計算Ｂは、当該偶数フィールドＢの１つ前の奇数フィールドＡの表示中に行われる。
【０１１１】
従って、モード２では、奇数フィールドＡの表示中に、奇数フィールドＡのためのソートＡと偶数フィールドＢのための計算Ｂとを並列に実行することができ、また、偶数フィールドＢの表示中に、偶数フィールドＢのためのソートＢと奇数フィールドＡのための計算Ａとを並列に実行することができる。その結果、計算Ａ及びＢのための期間を十分に確保できる。
【０１１２】
本実施の形態では、全構造体インスタンスのソートの完了を待つことなく、順位の高いものから構造体インスタンスが１つ確定するたびに、その都度、ＲＰＵ９に構造体インスタンスが読み込まれ、描画処理を行うことができる機能が用意されている。具体的には、ソートされるポリゴン構造体配列のソート済みポリゴン構造体インスタンスが確定するたび、ＹＳＵ１９からＲＰＵ９にパルス信号ＰＰＬ（後述）が伝達され、ＲＰＵ９は、このパルス信号ＰＰＬの数をカウントし、カウント値を超えない範囲の数のポリゴン構造体インスタンスをメインＲＡＭ２５から読み出す。また、スプライト構造体配列のソート及び読み出しについても、同様の機能が用意されている。このため、モード２のように、表示中のフィールドに対する各構造体インスタンスのソートを、直前の垂直ブランキング期間及びフィールド表示中に実行できる。
【０１１３】
順位の高いものから１つずつ構造体インスタンスを送り出すことができるソート技法の一例として、本実施の形態では、ヒープソートを採用している。また、ヒープソートを採用する他の利点として、ソート性能が安定している、すなわちソートに必要な時間にばらつきが少ないことが挙げられる。
【０１１４】
図１０は、本発明の実施の形態によるマルチメディアプロセッサ１の内部構成を示すブロック図である。図１０に示すように、このマルチメディアプロセッサは、外部メモリインタフェース３、ＤＭＡＣ（ｄｉｒｅｃｔ  ｍｅｍｏｒｙ  ａｃｃｅｓｓ  ｃｏｎｔｒｏｌｌｅｒ）４、中央演算処理装置（以下、「ＣＰＵ」と呼ぶ。）５、ＣＰＵローカルＲＡＭ７、レンダリングプロセッシングユニット（以下、「ＲＰＵ」と呼ぶ。）９、カラーパレットＲＡＭ１１、サウンドプロセシングユニット（以下、「ＳＰＵ」と呼ぶ。）１３、ＳＰＵローカルＲＡＭ１５、ジオメトリエンジン（以下、「ＧＥ」と呼ぶ。）１７、Ｙソーティングユニット（以下、「ＹＳＵ」と呼ぶ。）１９、外部インタフェースブロック２１、メインＲＡＭアクセスアービタ２３、メインＲＡＭ２５、Ｉ／Ｏバス２７、ビデオＤＡＣ（ｄｉｇｉｔａｌ  ｔｏ  ａｎａｌｏｇ  ｃｏｎｖｅｒｔｅｒ）２９、オーディオＤＡＣブロック３１、及びＡ／Ｄコンバータ（以下、「ＡＤＣ」と呼ぶ。）３３を具備する。メインＲＡＭ２５及び外部メモリ５０を区別して説明する必要がないときは、「メモリＭＥＭ」と表記する。
【０１１５】
ＣＰＵ５は、メモリＭＥＭに格納されたプログラムを実行して、各種演算やシステム全体の制御を行う。また、ＣＰＵ５は、ＤＭＡＣ４にプログラム及びデータの転送要求を行うこともできるし、ＤＭＡＣ４を介さずに、外部メモリインタフェース３及び外部バス５１を通じて、外部メモリ５０から直接プログラムコードをフェッチし、外部メモリ５０に直接データアクセスを行うこともできる。
【０１１６】
グラフィックス処理に関するＣＰＵ５の処理として、メモリＭＥＭに格納されたプログラムを実行して、各オブジェクト及び各スプライトの拡大・縮小、回転、及び／又は平行移動のパラメータ、視点座標（カメラ座標）、並びに視線ベクトルの算出等を行う。ここで、１または複数のポリゴンから構成され、同じ拡大・縮小、回転、及び平行移動の変換が適用される単位を「オブジェクト」と呼ぶ。
【０１１７】
Ｉ／Ｏバス２７は、ＣＰＵ５をバスマスタとするシステム制御用のバスであり、バススレイブである各機能ユニット（外部メモリインタフェース３、ＤＭＡＣ４、ＲＰＵ９、ＳＰＵ１３、ＧＥ１７、ＹＳＵ１９、外部インタフェースブロック２１、及びＡＤＣ３３）の制御レジスタ及びローカルＲＡＭ７，１１，１５へのアクセスに用いられる。このようにして、これらの機能ユニットは、Ｉ／Ｏバス２７を通じて、ＣＰＵ５により制御される。
【０１１８】
ＣＰＵローカルＲＡＭ７は、ＣＰＵ５専用のＲＡＭであり、サブルーチンコールや割り込み時におけるデータの退避などを行うためのスタック領域、及びＣＰＵ５のみが扱う変数の格納領域等として使用される。
【０１１９】
本発明の特徴の１つであるＲＰＵ９は、ポリゴン及びスプライトから構成される三次元イメージをリアルタイムに生成する。具体的には、ＲＰＵ９は、ＹＳＵ１９によるソート済みの、ポリゴン構造体配列の各構造体インスタンス及びスプライト構造体配列の各構造体インスタンスを、メインＲＡＭ２５から読み出し、上述したデプスコンパレータ１１２等による処理及び後述する様々な処理を実行して、スクリーンのスキャンに合わせて水平ラインごとにイメージを生成する。生成されたイメージは、コンポジットビデオ信号波形を示すデータストリームに変換され、ビデオＤＡＣ２９に出力される。また、ＲＰＵ９は、ＤＭＡＣ４に対して、ポリゴン及びスプライトのテクスチャパターンデータの取り込みのためのＤＭＡ転送要求を行う機能を有する。ＲＰＵ９については、後で詳述する。
【０１２０】
テクスチャパターンデータとは、ポリゴンまたはスプライトに貼り付けられる２次元の画素配列データであり、各画素データは、カラーパレットＲＡＭ１１のエントリを指定するための情報の一部である。このように、本実施の形態では、カラーの指定には、間接指定方式を採用する。以降、テクスチャパターンデータの画素を「テクセル」と呼称し、スクリーンに表示されるイメージを構成する画素を指す「ピクセル」とは区別して使用する。従って、テクスチャパターンデータは、テクセルデータの集合である。
【０１２１】
ビデオＤＡＣ２９は、アナログのビデオ信号を生成するためのデジタル／アナログ変換器である。ビデオＤＡＣ２９は、ＲＰＵ９から入力されたデータストリームをアナログのコンポジットビデオ信号に変換し、ビデオ信号出力端子（図示せず）からテレビジョンモニタ等（図示せず）に出力する。
【０１２２】
カラーパレットＲＡＭ１１は、本実施の形態では５１２色すなわち５１２エントリのカラーパレットからなる。ＲＰＵ９は、テクスチャパターンデータに含まれるテクセルデータをカラーパレットのエントリを指定するインデックスの一部として、カラーパレットＲＡＭ１１を参照し、テクスチャパターンデータを、カラーデータ（ＲＧＢのカラーコンポーネント）に変換する。
【０１２３】
ＳＰＵ１３は、ＰＣＭ（ｐｕｌｓｅ  ｃｏｄｅ  ｍｏｄｕｌａｔｉｏｎ）波形データ（以下、「ウェーブデータ」と呼ぶ。）、アンプリチュードデータ、及びメインボリュームデータを生成する。具体的には、ＳＰＵ１３は、最大６４チャンネル分のウェーブデータを生成して時分割多重化するとともに、最大６４チャンネル分のエンベロープデータを生成してチャンネルボリュームデータと乗算し、アンプリチュードデータを時分割多重化する。そして、ＳＰＵ１３は、メインボリュームデータ、時分割多重化されたウェーブデータ、及び時分割多重化されたアンプリチュードデータを、オーディオＤＡＣブロック３１に出力する。また、ＳＰＵ１３は、ＤＭＡＣ４に対して、ウェーブデータ及びエンベロープデータの取り込みのためのＤＭＡ転送要求を行う機能を有する。
【０１２４】
オーディオＤＡＣブロック３１は、ＳＰＵ１３から入力されたウェーブデータ、アンプリチュードデータ、及びメインボリュームデータをそれぞれアナログ信号に変換し、結果をアナログ乗算して、アナログオーディオ信号を生成する。このアナログオーディオ信号は、オーディオ信号出力端子（図示せず）からテレビジョンモニタ等（図示せず）のオーディオ入力端子（図示せず）に出力される。
【０１２５】
ＳＰＵローカルＲＡＭ１５は、ＳＰＵ１３がウェーブ再生及びエンベロープ生成を行う際に用いるパラメータ（例えば、ウェーブデータやエンベロープデータの格納アドレスやピッチ情報など）を格納する。
【０１２６】
ＧＥ１７は、三次元イメージを表示するための幾何演算を実行する。具体的には、ＧＥ１７は、行列積、ベクトルアフィン変換、ベクトル直交変換、透視投影変換、頂点明度／ポリゴン明度計算（ベクトル内積）、及びポリゴン裏面カリング処理（ベクトル外積）などの演算を実行する。
【０１２７】
本発明の特徴の１つであるＹＳＵ１９は、メインＲＡＭ２５に格納されているポリゴン構造体配列の各構造体インスタンス及びスプライト構造体配列の各構造体インスタンスを、ソートルール１〜４に従ってソートする。この場合、ポリゴン構造体配列とスプライト構造体配列とで、別個にソートが行われる。
【０１２８】
外部メモリインタフェース３は、外部バス５１を介して、外部メモリ５０からのデータの読み出し、及び外部メモリ５０へのデータの書き込みを司る。この場合、外部メモリインタフェース３は、図示しないＥＢＩ優先順位テーブルに従って、ＣＰＵ５及びＤＭＡＣ４からの外部バスアクセス要求要因（外部バス５１へのアクセスを要求する要因）を調停して、いずれか１つの外部バスアクセス要求要因を選択する。そして、選択した外部バスアクセス要求要因に対して外部バス５１へのアクセスを許可する。ＥＢＩ優先順位テーブルは、ＣＰＵ５からの複数種類の外部バスアクセス要求要因及びＤＭＡＣ４からの外部バスアクセス要求要因の優先順位を定めたテーブルである。
【０１２９】
外部バスアクセス要求要因として、ＣＰＵ５に含まれる図示しないＩＰＬ（ｉｎｉｔｉａｌ  ｐｒｏｇｒａｍ  ｌｏａｄｅｒ）によるブロック転送要求、ＣＰＵ５によるデータアクセス要求、ＣＰＵ５による命令フェッチ要求、及びＤＭＡＣ４によるＤＭＡ要求がある。
【０１３０】
ＤＭＡＣ４は、メインＲＡＭ２５と、外部バス５１に接続された外部メモリ５０と、の間でＤＭＡ転送を行う。この場合、ＤＭＡＣ４は、図示しないＤＭＡ優先順位テーブルに従って、ＣＰＵ５、ＲＰＵ９、及びＳＰＵ１３からのＤＭＡ転送要求要因（ＤＭＡ転送を要求する要因）を調停して、いずれか１つのＤＭＡ転送要求要因を選択する。そして、外部メモリインタフェース３に対して、ＤＭＡ要求を行う。ＤＭＡ優先順位テーブルは、ＣＰＵ５、ＲＰＵ９、及びＳＰＵ１３からのＤＭＡ要求要因の優先順位を定めたテーブルである。
【０１３１】
ＳＰＵ１３のＤＭＡ要求要因として、（１）ウェーブデータをウェーブバッファに転送すること、（２）エンベロープデータをエンベロープバッファに転送すること、がある。ウェーブバッファ及びエンベロープバッファは、それぞれメインＲＡＭ２５上に設定されるウェーブデータ及びエンベロープデータのテンポラリ格納領域である。なお、ＳＰＵ１３の２つのＤＭＡ要求要因間の調停は、ＳＰＵ１３内のハードウェア（図示せず）で行われ、ＤＭＡＣ４は関知しない。
【０１３２】
ＲＰＵ９のＤＭＡ要求要因として、テクスチャパターンデータをテクスチャバッファに転送すること、がある。テクスチャバッファは、メインＲＡＭ２５上に設定されるテクスチャパターンデータのテンポラリ格納領域である。
【０１３３】
ＣＰＵ５のＤＭＡ要求要因として、（１）仮想記憶管理においてページミスが発生した場合のページ転送、（２）アプリケーションプログラム等が要求するデータ転送、がある。なお、ＣＰＵ５内で複数のＤＭＡ転送要求が同時に発生した場合は、その調停はＣＰＵ５で実行されるソフトウェアにて行われ、ＤＭＡＣ４は関知しない。
【０１３４】
ＤＭＡＣ４は、ＬＺ７７アルゴリズムに基づくデータ伸張機能を備えており、ＣＰＵ５によるＤＭＡ転送要求に対して、外部メモリ５０に格納された圧縮データを伸張しながらＤＭＡ転送することが可能である。
【０１３５】
外部インタフェースブロック２１は、周辺装置５４とのインタフェースであり、２４チャンネルのプログラマブルなデジタル入出力（Ｉ／Ｏ）ポートを含む。２４チャンネルのＩ／Ｏポートの各々は、４チャンネル分のマウスインタフェース機能、４チャンネル分のライトガンインタフェース機能、２チャンネル分の汎用タイマ／カウンタ、１チャンネル分の調歩同期式シリアルインタフェース機能、１チャンネル分の汎用パラレル／シリアル変換ポート機能のうち１または複数に内部接続されている。
【０１３６】
ＡＤＣ３３は、４チャンネルのアナログ入力ポートに接続され、これらを介して、アナログ入力装置５２から入力されたアナログ信号をデジタル信号に変換する。例えば、マイク音声等のアナログ入力信号をサンプリングしてデジタルデータに変換する。
【０１３７】
メインＲＡＭアクセスアービタ２３は、機能ユニット（ＣＰＵ５、ＲＰＵ９、ＧＥ１７、ＹＳＵ１９、ＤＭＡＣ４、及び外部インタフェースブロック２１（汎用パラレル／シリアル変換ポート）からのメインＲＡＭ２５へのアクセス要求を調停して、いずれかの機能ユニットにアクセス許可を出す。
【０１３８】
メインＲＡＭ２５は、ＣＰＵ５のワーク領域、変数格納領域、および仮想記憶管理領域等として利用される。また、メインＲＡＭ２５は、ＣＰＵ５が他の機能ユニットに受け渡すデータの格納領域、ＲＰＵ９及びＳＰＵ１３が外部メモリ５０からＤＭＡによって取得したデータの格納領域、ＧＥ１７及びＹＳＵ１９の入力データ及び出力データの格納領域等としても使用される。
【０１３９】
外部バス５１は、外部メモリ５０にアクセスするためのバスである。ＣＰＵ５およびＤＭＡＣ４から、外部メモリインタフェース３を介してアクセスされる。外部バス５１のアドレスバスは、３０ビットから成り、最大で１Ｇバイト（＝８Ｇビット）の外部メモリ５０を接続することができる。外部バス５１のデータバスは、１６ビットから成り、８ビット又は１６ビットのデータバス幅を持つ外部メモリ５０を接続できる。異なるデータバス幅を持つ外部メモリを同時に接続可能であり、アクセスする外部メモリによってデータバス幅を自動的に切り替える機能が備えられる。
【０１４０】
次に、マルチメディアプロセッサ１によるグラフィックス処理の概要を説明する。
【０１４１】
図１１は、図１０のマルチメディアプロセッサ１によるグラフィックス処理の流れの概要を示すフローチャートである。図１１に示すように、ステップＳ１にて、ＣＰＵ５は、各オブジェクト（１または複数のポリゴンから構成され、同じ拡大・縮小、回転、及び平行移動の変換が適用される単位）及び各スプライトの拡大・縮小、回転、及び平行移動のパラメータを算出する。算出されたパラメータから、各オブジェクト及び各スプライトに対し、拡大・縮小、回転、及び平行移動のための変換行列が生成される。これらの変換行列は、各オブジェクト及び各スプライトのローカルな座標系（ローカル座標系）から、全てのオブジェクト及び全てのスプライトを統一の座標系で表現する直交座標系（ワールド座標系）への変換に用いられる。
【０１４２】
また、ＣＰＵ５は、視点（カメラ）座標、対象点座標、及び視線ベクトルの更新等を行う。これらのパラメータから、ワールド座標系から視点を中心とした直交座標系（ビュー座標系）への変換行列が生成される。
【０１４３】
ステップＳ２にて、ＧＥ１７は、各オブジェクト及び各スプライトに対し、拡大・縮小、回転、及び平行移動のための変換行列が複数存在する場合、それらの変換行列の行列積を求めることにより、複数の変換行列を単一の変換行列に合成する。さらに、ＧＥ１７は、合成された変換行列と、座標系変換のための変換行列と、の行列積を求めて、オブジェクト頂点座標配列、オブジェクト法線ベクトル配列、及びスプライト座標を変換するための変換行列をそれぞれ合成する。
【０１４４】
ステップＳ３にて、ＧＥ１７は、合成された変換行列を用い、オブジェクト頂点座標配列、オブジェクト法線ベクトル配列、及びスプライト座標の幾何変換を行う。また、ＧＥ１７は、変換後のオブジェクト法線ベクトル配列と光源ベクトルとの内積を演算し、オブジェクトの各頂点または面（ポリゴン）の明度を算出する。このような幾何変換及びライティングの結果は、ポリゴン構造体配列及びスプライト構造体配列に格納される。
【０１４５】
ステップＳ４にて、ＲＰＵ９による描画処理が行われる前に、ＹＳＵ１９は、ソートルール１〜４に従って、ポリゴン構造体インスタンスおよびスプライト構造体インスタンスをソートする。
【０１４６】
ステップＳ５にて、ＲＰＵ９は、ＹＳＵ１９によるソート後のポリゴン構造体インスタンスおよびスプライト構造体インスタンスを読み出すとともに、テクスチャマッピングモードのポリゴン及びスプライトの属性を示すテクスチャアトリビュート構造体インスタンスを読み出しつつ、各水平表示ラインのピクセルデータ列を生成する。また、テクスチャマッピングモードのポリゴン及びスプライトのピクセルデータ列生成には、これらに貼り付けるテクスチャパターンデータを、外部メモリ５０から読み出すことが必要とされる。このようなピクセルデータ列生成処理を「ラスタライジング」と呼ぶ。
【０１４７】
本実施の形態では、ポリゴンの描画モードとして、テクスチャマッピングを用いて描画を行うテクスチャマッピングモードと、グーローシェーディングを用いてポリゴンの描画を行うグーローシェーディングモードと、を実装している。テクスチャマッピングは、二次元の格子状に並べられたテクセルのパターンをポリゴン表面に貼り付ける描画手法である。グーローシェーディングは、少ない個数のポリゴンで擬似的に滑らかな曲面を表現するために用いられるスムーズシェーディングの一種である。グーローシェーディングでは、独立に指定されたポリゴンの頂点色を直線補完することでポリゴン内の各ピクセルの描画色を求める。
【０１４８】
また、ＲＰＵ９は、シザリングを実行する。シザリングとは、ポリゴン及びスプライトのピクセルデータ列生成時に、指定されたビューポートの領域からはみ出している部分を切り取って表示しないようにする処理である。生成されたピクセルデータ列は、ＲＰＵ９内のラインバッファＬＢ１あるいはＬＢ２に書き込まれるが、この際に書き込みピクセルが半透明色に設定されている場合、ラインバッファ内のピクセルのカラーと書き込みピクセルのカラーを混ぜ合わせるカラーブレンディングが行われる。
【０１４９】
ステップＳ６にて、ＲＰＵ９は、ラインバッファＬＢ１あるいはＬＢ２から表示対象の各ピクセルの情報を読み出し、同期信号及びカラーバースト信号等を追加してコンポジットビデオ信号のデジタルデータストリームを生成する。生成されたデータストリームは、ビデオＤＡＣ２９に入力され、ビデオＤＡＣ２９からは、アナログのコンポジットビデオ信号が出力される。
【０１５０】
次に、ＲＰＵ９の詳細を説明する。
【０１５１】
図１２は、図１０のＲＰＵ９の内部構成を示すブロック図である。図１２に示すように、ＲＰＵ９は、ＲＰＵ内メインＲＡＭアクセスアービタ１００、ポリゴンプリフェッチャ１０２、スプライトプリフェッチャ１０４、マージソータ１０６、プリフェッチバッファ１０８、リサイクルバッファ１１０、デプスコンパレータ１１２、バーテックスソータ１１４、バーテックスエキスパンダ１１６、スライサ１１８、ピクセルステッパ１２０、ピクセルディザ１２２、テクセルマッパ１２４、テクスチャキャッシュブロック１２６、バイリニアフィルタ１３０、カラーブレンダ１３２、ラインバッファブロック１３４、ビデオエンコーダ１３６、ビデオタイミングジェネレータ１３８、メモリマネージャ１４０、及びＤＭＡＣインタフェース１４２を含む。ラインバッファブロック１３４は、各々スクリーンの１水平ラインに対応するラインバッファＬＢ１及びＬＢ２を含む。なお、図１２では、説明の便宜のため、カラーパレットＲＡＭ１１をＲＰＵ９に含めて記載している。
【０１５２】
ＲＰＵ内メインＲＡＭアクセスアービタ１００は、ポリゴンプリフェッチャ１０２、スプライトプリフェッチャ１０４、及びメモリマネージャ１４０からメインＲＡＭ２５へのアクセス要求を調停して、いずれかにアクセス要求の許可を出す。許可されたアクセス要求は、メインＲＡＭアクセスアービタ２３に出力され、マルチメディアプロセッサ１内の他の機能ユニットからのアクセス要求との間で調停が行われる。
【０１５３】
ポリゴンプリフェッチャ１０２は、メインＲＡＭ２５から、ＹＳＵ１９によるソート後の各ポリゴン構造体インスタンスを取り込む。ポリゴンプリフェッチャ１０２には、ＹＳＵ１９から、パルスＰＰＬが入力される。ＹＳＵ１９は、ソートにおいて順位の高いものからポリゴン構造体インスタンスが１つ確定するたびに、パルスＰＰＬを出力する。従って、ポリゴンプリフェッチャ１０２は、ポリゴン構造体配列の全ポリゴン構造体インスタンスのうち、いくつのポリゴン構造体インスタンスのソートが完了したかを知ることができる。
【０１５４】
このため、ポリゴンプリフェッチャ１０２は、全ポリゴン構造体インスタンスのソートの完了を待つことなく、順位の高いものからポリゴン構造体インスタンスが１つ確定するたびに、その都度、ポリゴン構造体インスタンスを取得できる。その結果、フレームの表示中に、当該フレームのためのポリゴン構造体インスタンスのソートを行うことができる。また、インタレーススキャンによる表示を行う場合にも、前述のモード２（図９（ｂ）参照）を用いることにより、フィールドの表示中に当該フィールドのためのソートを行っても、正しい描画結果が得られる。なお、ポリゴンプリフェッチャ１０２は、ビデオタイミングジェネレータ１３８からの垂直走査カウント信号ＶＣから、フレームおよびフィールドの切り替わりを知ることができる。
【０１５５】
スプライトプリフェッチャ１０４は、メインＲＡＭ２５から、ＹＳＵ１９によるソート後の各スプライト構造体インスタンスを取り込む。スプライトプリフェッチャ１０４には、ＹＳＵ１９から、パルスＳＰＬが入力される。ＹＳＵ１９は、ソートにおいて順位の高いものからスプライト構造体インスタンスが１つ確定するたびに、パルスＳＰＬを出力する。従って、スプライトプリフェッチャ１０４は、スプライト構造体配列の全スプライト構造体インスタンスのうち、いくつのスプライト構造体インスタンスのソートが完了したかを知ることができる。
【０１５６】
このため、スプライトプリフェッチャ１０４は、全スプライト構造体インスタンスのソートの完了を待つことなく、順位の高いものからスプライト構造体インスタンスが１つ確定するたびに、その都度、スプライト構造体インスタンスを取得できる。その結果、フレームの表示中に、当該フレームのためのスプライト構造体インスタンスのソートを行うことができる。また、インタレーススキャンによる表示を行う場合にも、前述のモード２（図９（ｂ）参照）を用いることにより、フィールドの表示中に当該フィールドのためのソートを行っても、正しい描画結果が得られる。なお、スプライトプリフェッチャ１０４は、ビデオタイミングジェネレータ１３８からの垂直走査カウント信号ＶＣから、フレームおよびフィールドの切り替わりを知ることができる。
【０１５７】
ここで、ポリゴン構造体、テクスチャアトリビュート構造体、およびスプライト構造体の構成について詳しく説明する。
【０１５８】
図１３は、テクスチャマッピングモードのポリゴン構造体の例示図である。図１３に示すように、本実施の形態では、このポリゴン構造体は、１２８ビットで構成されている。このポリゴン構造体のメンバＴｙｐｅは、ポリゴンの描画モードを示し、テクスチャマッピングモードのポリゴンに対しては「０」が設定される。メンバＡｙ，Ａｘ，Ｂｙ，Ｂｘ，Ｃｙ及びＣｘは、それぞれ、ポリゴンの、頂点ＡのＹ座標、頂点ＡのＸ座標、頂点ＢのＹ座標、頂点ＢのＸ座標、頂点ＣのＹ座標、及び頂点ＣのＸ座標を示す。これらのＹ座標及びＸ座標は、スクリーン座標系の値である。
【０１５９】
メンバＢｗ，Ｃｗ，Ｌｉｇｈｔ及びＴｓｅｇｍｅｎｔは、それぞれ、ポリゴンの、頂点Ｂのパースペクティブコレクト用パラメータ（＝Ａｚ／Ｂｚ）、頂点Ｃのパースペクティブコレクト用パラメータ（＝Ａｚ／Ｃｚ）、明度、及びテクスチャパターンデータの格納位置情報を示す。
【０１６０】
メンバＴａｔｔｒｉｂｕｔｅ，Ｍａｐ，Ｆｉｌｔｅｒ，Ｄｅｐｔｈ及びＶｉｅｗｐｏｒｔは、それぞれ、テクスチャアトリビュート構造体のインデックス、テクスチャパターンデータのフォーマット種別、バイリニアフィルタリングあるいはニアレストネイバーのいずれかを示すフィルタリングモード、デプス値、及びシザリングのビューポート指定情報を示す。バイリニアフィルタリング及びニアレストネイバーについては後述する。
【０１６１】
以上が、テクスチャマッピングモードのポリゴン構造体の各メンバの内容であり、１つのポリゴン構造体のインスタンス（ポリゴン構造体に代入された値）により１つのポリゴンが定義される。
【０１６２】
図１４は、テクスチャアトリビュート構造体の例示図である。図１４に示すように、本実施の形態では、このテクスチャアトリビュート構造体は、３２ビットで構成されている。このテクスチャアトリビュート構造体のメンバＷｉｄｔｈ，Ｈｅｉｇｈｔ，Ｍ，Ｎ，Ｂｉｔ及びＰａｌｅｔｔｅは、それぞれ、テクスチャの幅（単位：テクセル数）より「１」小さい値、テクスチャの高さ（単位：テクセル数）より「１」小さい値、「Ｗｉｄｔｈ」の上位からのマスクビット数、「Ｈｅｉｇｈｔ」の上位からのマスクビット数、カラーモード（１ピクセル当りのビット数−１）、及びパレットブロックナンバを示す。カラーパレットの５１２色のエントリは、選択されたカラーモードに応じて複数のブロックに分割されており、メンバＰａｌｅｔｔｅにより、使用するパレットブロックが示される。
【０１６３】
テクスチャアトリビュート構造体のインスタンスは、描画ポリゴン毎に１つずつ用意されるものではなく、６４個のテクスチャアトリビュート構造体インスタンスが、テクスチャマッピングモードの全ポリゴン構造体インスタンス及び全スプライト構造体インスタンスで共有される。
【０１６４】
図１５は、グーローシェーディングモードのポリゴン構造体の例示図である。図１５に示すように、本実施の形態では、グーローシェーディングモードのポリゴン構造体は、１２８ビットで構成されており、メンバＡｘ（１１ビット），Ａｙ（１０ビット），Ｂｘ（１１ビット），Ｂｙ（１０ビット），Ｃｘ（１１ビット），Ｃｙ（１０ビット），Ａｃ（１５ビット），Ｂｃ（１５ビット），Ｃｃ（１５ビット），Ｄｅｐｔｈ（１２ビット），Ｖｉｅｗｐｏｒｔ（２ビット）及びＮａｌｐｈａ（３ビット）を有する。
【０１６５】
メンバＴｙｐｅは、ポリゴンの描画モードを示し、グーローシェーディングモードのポリゴンに対しては「１」が設定される。メンバＡｙ，Ａｘ，Ｂｙ，Ｂｘ，Ｃｙ及びＣｘは、それぞれ、ポリゴンの、頂点ＡのＹ座標、頂点ＡのＸ座標、頂点ＢのＹ座標、頂点ＢのＸ座標、頂点ＣのＹ座標、及び頂点ＣのＸ座標を示す。これらのＹ座標及びＸ座標は、スクリーン座標系の値である。
【０１６６】
メンバＡｃ，Ｂｃ，及びＣｃは、それぞれ、ポリゴンの、頂点Ａのカラーデータ（ＲＧＢ各５ビット）、頂点Ｂのカラーデータ（ＲＧＢ各５ビット）、及び頂点Ｃのカラーデータ（ＲＧＢ各５ビット）を示す。
【０１６７】
メンバＤｅｐｔｈ，Ｖｉｅｗｐｏｒｔ及びＮａｌｐｈａは、それぞれ、デプス値、シザリングのビューポート指定情報、及びアルファブレンディングで使用する（１−α）を示す。（１−α）は透明度を示し、「０００（二進数）」が透明度０％、すなわち完全不透明を表し、「１１１（二進数）」が透明度８７．５％を表す。
【０１６８】
以上が、グーローシェーディングモードのポリゴン構造体の各メンバの内容であり、１つのポリゴン構造体のインスタンス（ポリゴン構造体に代入された値）により１つのポリゴンが定義される。
【０１６９】
図１６（ａ）は、シザリングディセーブル時のスプライト構造体の例示図、図１６（ｂ）は、シザリングイネーブル時のスプライト構造体の例示図である。図１６（ａ）に示すように、本実施の形態では、シザリングディセーブル時のスプライト構造体は、６４ビットで構成されている。このスプライト構造体のメンバＡｘ及びＡｙは、それぞれ、スプライトの左上のＸ座標及びＹ座標を示す。これらのＹ座標及びＸ座標は、スクリーン座標系の値である。
【０１７０】
メンバＤｅｐｔｈ，Ｆｉｌｔｅｒ及びＴａｔｔｒｉｂｕｔｅは、それぞれ、デプス値、フィルタリングモード（バイリニアフィルタリングあるいはニアレストネイバー）、及びテクスチャアトリビュート構造体のインデックスを示す。メンバＺｏｏｍＸ，ＺｏｏｍＹ及びＴｓｅｇｍｅｎｔは、それぞれ、Ｘ軸方向のスプライト拡大率（拡縮率）、Ｙ軸方向のスプライト拡大率（拡縮率）、及びテクスチャパターンデータの格納位置情報を示す。
【０１７１】
図１６（ｂ）に示すように、本実施の形態では、シザリングイネーブル時のスプライト構造体は、６４ビットで構成されている。このスプライト構造体のメンバＡｘ及びＡｙは、それぞれ、スプライトの左上のＸ座標及びＹ座標を示す。これらのＹ座標及びＸ座標は、スクリーン座標系の値である。
【０１７２】
メンバＤｅｐｔｈ，Ｓｃｉｓｓｏｒ，Ｖｉｅｗｐｏｒｔ，Ｆｉｌｔｅｒ及びＴａｔｔｒｉｂｕｔｅは、それぞれ、デプス値、シザリング適用フラグ、シザリングのビューポート指定情報、フィルタリングモード（バイリニアフィルタリングあるいはニアレストネイバー）、及びテクスチャアトリビュート構造体のインデックスを示す。メンバＺｏｏｍＸ，ＺｏｏｍＹ及びＴｓｅｇｍｅｎｔは、それぞれ、Ｘ軸方向のスプライト拡大率（拡縮率）、Ｙ軸方向のスプライト拡大率（拡縮率）、及びテクスチャパターンデータの格納位置情報を示す。
【０１７３】
シザリングイネーブル時のスプライト構造体においては、シザリングディセーブル時のスプライト構造体に比べ、Ｘ座標及びＹ座標のビット数がそれぞれ１ビット少ない。シザリングイネーブル時にスプライトがスクリーンに配置される際には、後述のバーテックスエキスパンダ１１６によって、Ｘ座標に５１２ピクセル分のオフセット、Ｙ座標に２５６ピクセル分のオフセットが加えられる。また、デプス値のビット数も１ビット少ないが、シザリングイネーブル時には、後述のテクセルマッパ１２４によって、構造体に格納されているデプス値のＬＳＢ側に１ビットの「０」が付加され、シザリングディセーブル時と同様に８ビットのデプス値として扱われる。
【０１７４】
以上が、シザリングディセーブル時及びシザリングイネーブル時のスプライト構造体の各メンバの内容であり、１つのスプライト構造体のインスタンス（スプライト構造体に代入された値）により１つのスプライトが定義される。スプライトのテクスチャアトリビュート構造体の構成は、図１４のポリゴンのテクスチャアトリビュート構造体の構成と同じである。テクスチャアトリビュート構造体のインスタンスは、描画スプライト毎に１つずつ用意されるものではなく、６４個のテクスチャアトリビュート構造体インスタンスが、テクスチャマッピングモードの全ポリゴン構造体インスタンス及び全スプライト構造体インスタンスで共有される。
【０１７５】
図１２に戻って、マージソータ１０６は、ポリゴンプリフェッチャ１０２及びスプライトプリフェッチャ１０４から、それぞれ、ポリゴン構造体インスタンス及びそれに付随するテクスチャアトリビュート構造体インスタンス、並びに、スプライト構造体インスタンス及びそれに付随するテクスチャアトリビュート構造体インスタンスを受け取り、上述したＹＳＵ１９によるソートルール１〜４と同じソートルール１〜４に従って、マージソートを実行し、結果をプリフェッチバッファ１０８に送出する。
【０１７６】
つまり、マージソータ１０６は、ソートルール１〜４に従って、ポリゴン構造体インスタンスを選択した場合、テクスチャマッピングモードのポリゴンについては、ポリゴン構造体インスタンスをポリゴン／スプライトデータＰＳＤ（１２８ビット）として、それに付随するテクスチャアトリビュート構造体インスタンスをテクスチャアトリビュート構造体インスタンスＴＡＩ（３２ビット）として、プリフェッチバッファ１０８に出力する。
【０１７７】
また、マージソータ１０６は、ソートルール１〜４に従って、ポリゴン構造体インスタンスを選択した場合、グーローシェーディングモードのポリゴンについては、ポリゴン構造体インスタンスをポリゴン／スプライトデータＰＳＤ（１２８ビット）として、テクスチャアトリビュート構造体インスタンスＴＡＩ（３２ビット）の全ビットを「０」として、プリフェッチバッファ１０８に出力する。
【０１７８】
一方、マージソータ１０６は、ソートルール１〜４に従って、スプライト構造体インスタンスを選択した場合、スプライト構造体インスタンスをポリゴン／スプライトデータＰＳＤ（１２８ビット）として、それに付随するテクスチャアトリビュート構造体インスタンスをテクスチャアトリビュート構造体インスタンスＴＡＩ（３２ビット）として、プリフェッチバッファ１０８に出力する。ただし、この場合のポリゴン／スプライトデータＰＳＤは、有効データがＬＳＢから詰められ、上位６４ビットは「０」を示す。
【０１７９】
上で詳述したプリフェッチバッファ１０８は、マージソータ１０６から、マージソート後の構造体インスタンス（つまり、ポリゴン／スプライトデータＰＳＤ及びテクスチャアトリビュート構造体インスタンスＴＡＩ）を順次読み込み、読み込んだ順番で構造体インスタンスを出力するＦＩＦＯ（ｆｉｒｓｔ−ｉｎ  ｆｉｒｓｔ−ｏｕｔ）構造のバッファである。つまり、プリフェッチバッファ１０８には、マージソータ１０６により並べ替えられた順番で構造インスタンスが格納される。そして、格納された構造インスタンスは、対応するポリゴンあるいはスプライトの表示のための描画サイクルにおいて、格納された順番で出力される。なお、プリフェッチバッファ１０８は、ビデオタイミングジェネレータ１３８からの垂直走査カウント信号ＶＣから、描画中の水平ラインを知ることができる。つまり、描画サイクルの切り替わりを知ることができる。本実施の形態では、例えば、プリフェッチバッファ１０８は、物理的にはリサイクルバッファ１１０とバッファを共有することが可能であり、リサイクルバッファ１１０のエントリ数を含め、（１２８ビット＋３２ビット）×１２８エントリとする。
【０１８０】
上で詳述したリサイクルバッファ１１０は、次の描画サイクルでも使用される（つまり、再利用できる）構造体インスタンス（つまり、ポリゴン／スプライトデータＰＳＤ及びテクスチャアトリビュート構造体インスタンスＴＡＩ）を、スライサ１１８から受け取って格納するＦＩＦＯ構造のバッファである。従って、リサイクルバッファ１１０に格納された構造体インスタンスは、次の描画サイクルで使用される。本実施の形態では、例えば、リサイクルバッファ１１０は、物理的にはプリフェッチバッファ１０８とバッファを共有することが可能であり、プリフェッチバッファ１０８のエントリ数を含め、（１２８ビット＋３２ビット）×１２８エントリとする。
【０１８１】
上で詳述したデプスコンパレータ１１２は、プリフェッチバッファ１０８の先頭の構造体インスタンスに含まれるデプス値と、リサイクルバッファ１１０の先頭の構造体インスタンスに含まれるデプス値と、を比較して、より大きなデプス値を持つ（つまり、より奥に表示されるべき）構造体インスタンスを選択して、後段に出力する。この場合、デプスコンパレータ１１２は、選択した構造体インスタンスがポリゴン構造体インスタンスの場合は、バーテックスソータ１１４へ出力し、スプライト構造体インスタンスの場合は、バーテックスエキスパンダ１１６に出力する。また、デプスコンパレータ１１２は、選択した構造体インスタンスをスライサ１１８に出力する。なお、デプスコンパレータ１１２は、ビデオタイミングジェネレータ１３８からの垂直走査カウント信号ＶＣから、描画中の水平ラインを知ることができる。つまり、描画サイクルの切り替わりを知ることができる。
【０１８２】
バーテックスエキスパンダ１１６は、受け取ったスプライト構造体インスタンスに含まれる、スプライトの左上の頂点座標（Ａｘ，Ａｙ）、Ｙ軸方向の拡大率ＺｏｏｍＹ、及びＸ軸方向の拡大率ＺｏｏｍＸ、並びに、当該スプライト構造体インスタンスに付随するテクスチャアトリビュート構造体インスタンスに含まれる、テクスチャの幅より「１」小さい値Ｗｉｄｔｈ及び高さより「１」小さい値Ｈｅｉｇｈｔに基づいて、当該スプライトの頂点の座標（スクリーン座標系におけるＸＹ座標およびＵＶ座標系におけるＵＶ座標）を算出し、ポリゴン／スプライト共通データＣＩ（２０８ビット）としてスライサ１１８へ出力する。ただし、ポリゴン／スプライト共通データＣＩの後述のフィールドＷＧ＊（＊＝０，１，２）は、常に「０ｘ００４０」（＝１．０）として出力される。バーテックスエキスパンダ１１６が出力するポリゴン／スプライト共通データＣＩの構造（形式）は、バーテックスソータ１１４が出力するポリゴン／スプライト共通データＣＩの構造（形式）と同じである。
【０１８３】
バーテックスエキスパンダ１１６は、受け取ったスプライト構造体インスタンスに含まれる、スプライトの左上の頂点座標（Ａｘ，Ａｙ）、Ｙ軸方向の拡大率ＺｏｏｍＹ、及びＸ軸方向の拡大率ＺｏｏｍＸ、並びに、当該スプライト構造体インスタンスに付随するテクスチャアトリビュート構造体インスタンスに含まれる、テクスチャの幅より「１」小さい値Ｗｉｄｔｈ及び高さより「１」小さい値Ｈｅｉｇｈｔに基づいて、当該スプライトの頂点の座標（スクリーン座標系におけるＸＹ座標およびＵＶ座標系におけるＵＶ座標）を算出し、ポリゴン／スプライト共通データＣＩ（２０８ビット）としてスライサ１１８へ出力する。ただし、ポリゴン／スプライト共通データＣＩの後述のフィールドＷＧ＊（＊＝０，１，２）は、常に「０ｘ００４０」（＝１．０）として出力される。バーテックスエキスパンダ１１６が出力するポリゴン／スプライト共通データＣＩの構造（形式）は、バーテックスソータ１１４が出力するポリゴン／スプライト共通データＣＩの構造（形式）と同じである。
【０１８４】
ここで、スクリーン座標系は上述の通りである。ＵＶ座標系は、テクスチャを構成する各テクセルが、ポリゴンあるいはスプライトにマッピングされる態様で配置される二次元直交座標系である。
【０１８５】
バーテックスソータ１１４は、受け取ったポリゴン構造体インスタンス及びそれに付随するテクスチャアトリビュート構造体インスタンスから、ポリゴンの各頂点のパラメータ（ＸＹＵＶ座標、パースペクティブコレクト用パラメータ、及びカラーデータ）を取得及び算出し、各頂点のパラメータをＹ座標が小さい順に並べ替えて、ポリゴン／スプライト共通データＣＩとしてスライサ１１８へ出力する。頂点の出現順は、早いほうから頂点０、頂点１、及び頂点２とする。
【０１８６】
つまり、テクスチャマッピングモードでは、バーテックスソータ１１４は、演算結果、つまり、各頂点０〜２のパラメータ（ＸＹ座標、パースペクティブコレクト後のＵＶ座標、及びパースペクティブコレクト用パラメータ）を、ポリゴン／スプライト共通データＣＩとして、スライサ１１８に出力する。
【０１８７】
また、グーローシェーディングモードでは、バーテックスソータ１１４は、演算結果、つまり、各頂点０〜２のパラメータ（ＸＹ座標、及びカラーデータ）を、ポリゴン／スプライト共通データＣＩとして、スライサ１１８に出力する。
【０１８８】
バーテックスソータ１１４が出力するポリゴン／スプライト共通データＣＩの構成（形式）は、バーテックスエキスパンダ１１６が出力するポリゴン／スプライト共通データＣＩの構成（形式）と同じである。
【０１８９】
バーテックスソータ１１４及びバーテックスエキスパンダ１１６が出力するポリゴン／スプライト共通データＣＩの構成を説明する。ポリゴン／スプライト共通データＣＩは、フィールドＦ（１ビット），ＷＧ＊（各１６ビット），ＶＲ＊（各１６ビット），ＵＢ＊（各１６ビット），Ｙ＊（各１０ビット）及びＸ＊（各１１ビット）からなる（計２０８ビット）。＊＝０，１，２であり、頂点を示す。
【０１９０】
フィールドＦは、ポリゴン／スプライト共通データＣＩが、ポリゴンについてのものであるか、スプライトについてのものであるか、を示すフラグフィールドである。従って、バーテックスソータ１１４は、ポリゴンを示す「１」をフィールドＦに格納する。一方、バーテックスエキスパンダ１１６は、スプライトを示す「０」をフィールドＦに格納する。
【０１９１】
バーテックスエキスパンダ１１６から出力されるポリゴン／スプライト共通データＣＩでは、フィールドＶＲ＊，ＵＢ＊，Ｙ＊及びＸ＊は、それぞれ頂点＊のＶ座標、Ｕ座標、Ｙ座標、及びＸ座標である。この場合、フィールドＷＧ＊には、「０ｘ００４０」（＝１．０）が格納される。上述したように、頂点＊の出現順は、早いほうから頂点０、頂点１、及び頂点２である。
【０１９２】
バーテックスソータ１１４から出力される、テクスチャマッピングの対象であるポリゴン／スプライト共通データＣＩでは、フィールドＷＧ＊，ＶＲ＊，ＵＢ＊，Ｙ＊及びＸ＊は、それぞれ頂点＊のパースペクティブコレクト用パラメータ、パースペクティブコレクト済みＶ座標、パースペクティブコレクト済みＵ座標、Ｙ座標、及びＸ座標である。
【０１９３】
バーテックスソータ１１４から出力される、グーローシェーディングの対象であるポリゴン／スプライト共通データＣＩでは、フィールドＷＧ＊，ＶＲ＊，ＵＢ＊，Ｙ＊及びＸ＊は、それぞれ頂点＊の緑成分、赤成分、青成分、Ｙ座標、及びＸ座標である。
【０１９４】
図１７〜図１９を用いてスライサ１１８の動作を説明する。図１７は、スライサ１１８による、グーローシェーディングモードのポリゴンに対する処理の説明図である。図１７に示すように、スライサ１１８は、与えられたポリゴン／スプライト共通データＣＩにより定義されるポリゴン（三角形）と、描画対象の水平ラインと、の交点のＸＹ座標（Ｘｓ，Ｙｓ）及び（Ｘｅ，Ｙｅ）を求める。ここで、ポリゴンに対しては、描画対象の水平ラインと交わらない辺が存在する側の交点を終端（Ｘｅ，Ｙｅ）とし、当該辺が存在しない側の交点を始端（Ｘｓ，Ｙｓ）とする。
【０１９５】
そして、スライサ１１８は、描画Ｙ座標ＹｒがＹ０≦Ｙｒ＜Ｙ１の範囲では、頂点０のＲＧＢ値（ＶＲ０，ＷＧ０，ＵＢ０）及び頂点２のＲＧＢ値（ＶＲ２，ＷＧ２，ＵＢ２）に基づいて、直線補間により、交点始端のＲＧＢ値（Ｒｓ，Ｇｓ，Ｂｓ）を算出するとともに、頂点０のＲＧＢ値（ＶＲ０，ＷＧ０，ＵＢ０）及び頂点１のＲＧＢ値（ＶＲ１，ＷＧ１，ＵＢ１）に基づいて、直線補間により、交点終端のＲＧＢ値（Ｒｅ，Ｇｅ，Ｂｅ）を算出する。また、スライサ１１８は、描画Ｙ座標ＹｒがＹ１≦Ｙｒ≦Ｙ２の範囲では、頂点０のＲＧＢ値（ＶＲ０，ＷＧ０，ＵＢ０）及び頂点２のＲＧＢ値（ＶＲ２，ＷＧ２，ＵＢ２）に基づいて、直線補間により、交点始端のＲＧＢ値（Ｒｓ，Ｇｓ，Ｂｓ）を算出するとともに、頂点１のＲＧＢ値（ＶＲ１，ＷＧ１，ＵＢ１）及び頂点２のＲＧＢ値（ＶＲ２，ＷＧ２，ＵＢ２）に基づいて、直線補間により、交点終端のＲＧＢ値（Ｒｅ，Ｇｅ，Ｂｅ）を算出する。
【０１９６】
そして、スライサ１１８は、ΔＲ、ΔＧ、ΔＢ及びΔＸｇを算出する。ここで、ΔＲ、ΔＧ、ΔＢは、描画対象の水平ラインにおけるΔＸｇあたりのＲ、Ｇ、Ｂそれぞれの変化量であり、ΔＸｇは、描画対象の水平ラインにおける１ピクセルあたりのＸ座標の変化量である。ΔＸｇは、「＋１」または「−１」のいずれかとなる。
【０１９７】
ΔＲ＝（Ｒｅ−Ｒｓ）／（Ｘｅ−Ｘｓ）
ΔＧ＝（Ｇｅ−Ｇｓ）／（Ｘｅ−Ｘｓ）
ΔＢ＝（Ｂｅ−Ｂｓ）／（Ｘｅ−Ｘｓ）
ΔＸｇ＝（Ｘｅ−Ｘｓ）／│Ｘｅ−Ｘｓ│
【０１９８】
スライサ１１８は、デプスコンパレータ１１２から受け取った構造体インスタンスと共に、算出したＸｓ，Ｒｓ，Ｇｓ，Ｂｓ，Ｘｅ，ΔＲ，ΔＧ，ΔＢ及びΔＸｇを、ピクセルステッパ１２０へ送出する。また、スライサ１１８は、バーテックスソータ１１４から受け取ったポリゴン／スプライト共通データＣＩが、次の描画サイクルでも使用される場合は、リサイクルバッファ１１０に、デプスコンパレータ１１２から受け取った構造体インスタンスを書き込む。なお、ビデオタイミングジェネレータ１３８からの垂直走査カウント信号ＶＣ及びポリゴンの頂点座標から、次の描画サイクルでの使用の有無を知ることができる。
【０１９９】
図１８は、スライサ１１８による、テクスチャマッピングモードのポリゴンに対する処理の説明図である。図１８に示すように、スライサ１１８は、与えられたポリゴン／スプライト共通データＣＩにより定義されるポリゴン（三角形）と、描画対象の水平ラインと、の交点座標である始端（Ｘｓ，Ｙｓ）及び終端（Ｘｅ，Ｙｅ）を求める。この点は、グーローシェーディングモードのポリゴンに対する処理と同じである。
【０２００】
ここで、パースペクティブコレクト機能について説明する。透視投影変換された三次元イメージを表現するテクスチャマッピングにおいて、スクリーン上の描画ピクセルに対応するテクセルを、ポリゴンの各頂点座標に対応する、ＵＶ空間のテクスチャの各頂点座標の単なる線形補完によって求めると、マッピングされたイメージが歪んでしまうことがある。この歪みを解消するのがパースペクティブコレクト機能であり、具体的には、以下のような処理が行われる。
【０２０１】
ポリゴンの各頂点Ａ，Ｂ，ＣをＵＶ空間へ写像したときの座標を、（Ａｕ，Ａｖ），（Ｂｕ，Ｂｖ），（Ｃｕ，Ｃｖ）とする。また、各頂点Ａ，Ｂ，Ｃのビュー座標を（Ａｘ，Ａｙ，Ａｚ），（Ｂｘ，Ｂｙ，Ｂｚ），（Ｃｘ，Ｃｙ，Ｃｚ）とする。そして、（Ａｕ／Ａｚ，Ａｖ／Ａｚ，１／Ａｚ），（Ｂｕ／Ｂｚ，Ｂｖ／Ｂｚ，１／Ｂｚ），（Ｃｕ／Ｃｚ，Ｃｖ／Ｃｚ，１／Ｃｚ）の線形補間によって求められた値（ｕ／ｚ，ｖ／ｚ，１／ｚ）のｕ／ｚに１／ｚの逆数を乗じた値ｕおよびｖ／ｚに１／ｚの逆数を乗じた値ｖ、つまり（ｕ，ｖ）をテクセル座標（Ｕ，Ｖ）としてテクセルデータを取得することにより、透視投影変換後の正確なテクスチャマッピングを実現する。ここで、ビュー座標とは、ビュー座標系の座標である。ビュー座標系は、ＸＹＺの三軸から成る三次元直交座標系であり、視点を原点とし、視線をＺ軸の正とする。
【０２０２】
本実施の形態では、１／Ａｚ，１／Ｂｚ，１／Ｃｚを頂点毎に設定する代りに、それぞれの値にＡｚを掛け合わせた値、すなわち、Ａｚ／Ａｚ（＝Ａｗ），Ａｚ／Ｂｚ（＝Ｂｗ），Ａｚ／Ｃｚ（＝Ｃｗ）をポリゴン構造体に設定する（図１３参照）。但し、頂点Ａに対するパラメータＡｗは常に「１」となるため、ポリゴン構造体には設定しない。
【０２０３】
従って、本実施の形態では、（Ａｕ・Ａｗ，Ａｖ・Ａｗ，Ａｗ），（Ｂｕ・Ｂｗ，Ｂｖ・Ｂｗ，Ｂｗ），（Ｃｕ・Ｃｗ，Ｃｖ・Ｃｗ，Ｃｗ）の線形補間によって求められた値（ｕ・ｗ，ｖ・ｗ，ｗ）のｕ・ｗに１／ｗを乗じた値ｕおよびｖ・ｗに１／ｗを乗じた値ｖ、つまり（ｕ，ｖ）をテクセル座標（Ｕ，Ｖ）としてテクセルデータを取得することにより、透視投影変換後の正確なテクスチャマッピングを実現する。
【０２０４】
このことを念頭においた上で、スライサ１１８は、描画Ｙ座標ＹｒがＹ０≦Ｙｒ＜Ｙ１の範囲では、頂点０の（ＵＢ０，ＶＲ０，ＷＧ０）、及び頂点２の（ＵＢ２，ＶＲ２，ＷＧ２）に基づいて、直線補間により、交点始端の（Ｕｓ，Ｖｓ，Ｗｓ）を算出するとともに、頂点０の（ＵＢ０，ＶＲ０，ＷＧ０）、及び頂点１の（ＵＢ１，ＶＲ１，ＷＧ１）に基づいて、直線補間により、交点終端の（Ｕｅ，Ｖｅ，Ｗｅ）を算出する。また、スライサ１１８は、描画Ｙ座標ＹｒがＹ１≦Ｙｒ≦Ｙ２の範囲では、頂点０の（ＵＢ０，ＶＲ０，ＷＧ０）、及び頂点２の（ＵＢ２，ＶＲ２，ＷＧ２）に基づいて、直線補間により、交点始端の（Ｕｓ，Ｖｓ，Ｗｓ）を算出するとともに、頂点１の（ＵＢ１，ＶＲ１，ＷＧ１）、及び頂点２の（ＵＢ２，ＶＲ２，ＷＧ２）に基づいて、直線補間により、交点終端の（Ｕｅ，Ｖｅ，Ｗｅ）を算出する。
【０２０５】
このことを、頂点間のＹ座標がＢｙ≦Ａｙ＜Ｃｙであり、描画Ｙ座標ＹｒがＹ１≦Ｙｒ≦Ｙ２の範囲である場合を例に挙げて説明する。そうすると、スライサ１１８は、頂点０の（ＵＢ０，ＶＲ０，ＷＧ０）＝（Ｂｕ・Ｂｗ，Ｂｖ・Ｂｗ，Ｂｗ）、及び頂点２の（ＵＢ２，ＶＲ２，ＷＧ２）＝（Ｃｕ・Ｃｗ，Ｃｖ・Ｃｗ，Ｃｗ）に基づいて、直線補間により、交点始端の（Ｕｓ，Ｖｓ，Ｗｓ）を算出するとともに、頂点１の（ＵＢ１，ＶＲ１，ＷＧ１）＝（Ａｕ・Ａｗ，Ａｖ・Ａｗ，Ａｗ）、及び頂点２の（ＵＢ２，ＶＲ２，ＷＧ２）＝（Ｃｕ・Ｃｗ，Ｃｖ・Ｃｗ，Ｃｗ）に基づいて、直線補間により、交点終端の（Ｕｅ，Ｖｅ，Ｗｅ）を算出する。
【０２０６】
次に、スライサ１１８は、ΔＵ、ΔＶ、ΔＷ及びΔＸｔを算出する。ここで、ΔＵ、ΔＶ、ΔＷは、描画対象の水平ラインにおけるΔＸｔあたりのＵ座標（＝ｕ・ｗ）、Ｖ座標（＝ｖ・ｗ）、パースペクティブコレクト用パラメータＷ（＝ｗ）それぞれの変化量であり、ΔＸｔは、描画対象の水平ラインにおける１ピクセルあたりのＸ座標の変化量である。ΔＸｔは、「＋１」または「−１」のいずれかとなる。
【０２０７】
ΔＵ＝（Ｕｅ−Ｕｓ）／（Ｘｅ−Ｘｓ）
ΔＶ＝（Ｖｅ−Ｖｓ）／（Ｘｅ−Ｘｓ）
ΔＷ＝（Ｗｅ−Ｗｓ）／（Ｘｅ−Ｘｓ）
ΔＸｔ＝（Ｘｅ−Ｘｓ）／│Ｘｅ−Ｘｓ│
【０２０８】
スライサ１１８は、デプスコンパレータ１１２から受け取った構造体インスタンスと共に、算出したＸｓ，Ｕｓ，Ｖｓ，Ｗｓ，Ｘｅ，ΔＵ，ΔＶ，ΔＷ及びΔＸｔを、ピクセルステッパ１２０へ送出する。また、スライサ１１８は、バーテックスソータ１１４から受け取ったポリゴン／スプライト共通データＣＩが、次の描画サイクルでも使用される場合は、リサイクルバッファ１１０に、デプスコンパレータ１１２から受け取った構造体インスタンスを書き込む。なお、ビデオタイミングジェネレータ１３８からの垂直走査カウント信号ＶＣ及びポリゴンの頂点座標から、次の描画サイクルでの使用の有無を知ることができる。
【０２０９】
図１９は、スライサ１１８によるスプライトに対する処理の説明図である。図１９に示すように、スライサ１１８は、与えられたポリゴン／スプライト共通データＣＩにより定義されるスプライト（矩形）と、描画対象の水平ラインと、の交点座標（Ｘｓ，Ｙｓ）及び（Ｘｅ，Ｙｅ）を求める。ここで、スプライトに対しては、先に描画される側の交点を始端（Ｘｓ，Ｙｓ）とし、後に描画される側の交点を終端（Ｘｅ，Ｙｅ）とする。
【０２１０】
スプライトの各頂点０，１，２，３をＵＶ空間へ写像したときの座標は、（ＵＢ０，ＶＲ０），（ＵＢ１，ＶＲ１），（ＵＢ２，ＶＲ２），（ＵＢ３，ＶＲ３）である。ここで、ＵＢ３，ＶＲ３はスライサ１１８に入力されないが、それぞれ下記のようにスライサ１１８内で求められる。
【０２１１】
ＵＢ３＝ＵＢ１
ＶＲ３＝ＶＲ２
【０２１２】
スライサ１１８は、頂点０の（ＵＢ０，ＶＲ０）及び頂点２の（ＵＢ２，ＶＲ２）に基づいて、直線補間により、交点始端のＵＶ座標（Ｕｓ，Ｖｓ）を算出するとともに、頂点１の（ＵＢ１，ＶＲ１）及び頂点３の（ＵＢ３，ＶＲ３）に基づいて、直線補間により、交点終端のＵＶ座標（Ｕｅ，Ｖｅ）を算出する。
【０２１３】
そして、スライサ１１８は、ΔＵおよびΔＶを算出する。ここで、ΔＵ、ΔＶは、描画対象の水平ラインにおけるΔＸｓあたりのＵ座標、Ｖ座標それぞれの変化量である。ΔＸｓは、描画対象の水平ラインにおける１ピクセルあたりのＸ座標の変化量であるが、常に「１」となるので、算出は行わない。
【０２１４】
ΔＵ＝（Ｕｅ−Ｕｓ）／（Ｘｅ−Ｘｓ）
ΔＶ＝（Ｖｅ−Ｖｓ）／（Ｘｅ−Ｘｓ）
ΔＸｓ＝（Ｘｅ−Ｘｓ）／│Ｘｅ−Ｘｓ│＝１
【０２１５】
スライサ１１８は、デプスコンパレータ１１２から受け取った構造体インスタンスと共に、算出したＸｓ，Ｕｓ，Ｖｓ，Ｘｅ，ΔＵ，ΔＶ及びΔＸｓを、ピクセルステッパ１２０へ送出する。また、スライサ１１８は、バーテックスエキスパンダ１１６から受け取ったポリゴン／スプライト共通データＣＩが、次の描画サイクルでも使用される場合は、リサイクルバッファ１１０に、デプスコンパレータ１１２から受け取った構造体インスタンスを書き込む。なお、ビデオタイミングジェネレータ１３８からの垂直走査カウント信号ＶＣ及びスプライトの頂点座標から、次の描画サイクルでの使用の有無を知ることができる。
【０２１６】
ここで、スライサ１１８は、ポリゴン／スプライト共通データＣＩのフィールドＦから、ポリゴンおよびスプライトの別を認識でき、ポリゴン構造体インスタンスのメンバＴｙｐｅから、グーローシェーディング及びテクスチャマッピングの別を認識できる。
【０２１７】
図１２に戻って、ピクセルステッパ１２０は、グーローシェーディングモードのポリゴンについては、スライサ１１８から与えられたパラメータ（Ｘｓ，Ｒｓ，Ｇｓ，Ｂｓ，Ｘｅ，ΔＲ，ΔＧ，ΔＢ及びΔＸｇ）から、描画対象ピクセルの描画Ｘ座標とＲＧＢ値を求め、（１−α）値とともにピクセルディザ１２２に送出する。具体的には、ピクセルステッパ１２０は、交点の始端（描画開始端）Ｘｓの赤成分Ｒｓに、１ピクセル当たりの赤成分の変化量ΔＲを順次加えていき、各ピクセルの赤成分ＲＸを求める。この処理を、交点の終端（描画終了端）Ｘｅに到達するまで行う。緑成分ＧＸ及び青成分ＢＸについても同様である。また、交点の始端ＸｓにΔＸｓを順次加えていき、描画Ｘ座標Ｘｒを求める。なお、Ｘ＝０〜｜Ｘｅ−Ｘｓ｜であり、整数である。
【０２１８】
ＲＸ＝ΔＸｇ・ΔＲ・Ｘ＋Ｒｓ
ＧＸ＝ΔＸｇ・ΔＧ・Ｘ＋Ｇｓ
ＢＸ＝ΔＸｇ・ΔＢ・Ｘ＋Ｂｓ
Ｘｒ＝ΔＸｓ・Ｘ＋Ｘｓ
【０２１９】
ピクセルステッパ１２０は、求めた各ピクセルのＲＧＢ値（ＲＸ，ＧＸ，ＢＸ）、並びに描画Ｘ座標Ｘｒを、（１−α）値並びにデプス値（Ｄｅｐｔｈ）とともに、ピクセルディザ１２２に出力する。
【０２２０】
また、ピクセルステッパ１２０は、テクスチャマッピングモードのポリゴンについては、スライサ１１８から与えられたパラメータ（Ｘｓ，Ｕｓ，Ｖｓ，Ｗｓ，Ｘｅ，ΔＵ，ΔＶ，ΔＷ及びΔＸｔ）から、描画対象ピクセルをＵＶ空間へ写像したときの座標（Ｕ，Ｖ）を求める。具体的には、ピクセルステッパ１２０は、交点の始端（描画開始端）Ｘｓのパースペクティブコレクト用パラメータＷｓに、１ピクセル当たりのパースペクティブコレクト用パラメータの変化量ΔＷを順次加えていき、各ピクセルのパースペクティブコレクト用パラメータＷＸを求める。この処理を、交点の終端（描画終了端）Ｘｅに到達するまで行う。なお、Ｘ＝０〜｜Ｘｅ−Ｘｓ｜であり、整数である。
【０２２１】
ＷＸ＝ΔＸｔ・ΔＷ・Ｘ＋Ｗｓ
【０２２２】
ピクセルステッパ１２０は、交点の始端（描画開始端）ＸｓのＵ座標（＝ｕ・ｗ）Ｕｓに、１ピクセル当たりのＵ座標の変化量ΔＵを順次加えていき、求めた値にＷＸの逆数を掛け合わせ、各ピクセルのＵ座標ＵＸを求める。この処理を、交点の終端（描画終了端）Ｘｅに到達するまで行う。Ｖ座標（＝ｖ・ｗ）ＶＸについても同様である。また、交点の始端ＸｓにΔＸｓを順次加えていき、描画Ｘ座標Ｘｒを求める。なお、Ｘ＝０〜｜Ｘｅ−Ｘｓ｜であり、整数である。
【０２２３】
ＵＸ＝（ΔＸｔ・ΔＵ・Ｘ＋Ｕｓ）・（１／ＷＸ）
ＶＸ＝（ΔＸｔ・ΔＶ・Ｘ＋Ｖｓ）・（１／ＷＸ）
Ｘｒ＝ΔＸｓ・Ｘ＋Ｘｓ
【０２２４】
ピクセルステッパ１２０は、求めた各ピクセルのＵＶ座標（ＵＸ，ＶＸ）並びに描画Ｘ座標Ｘｒを、スライサ１１８から受け取った構造体インスタンス（テクスチャマッピングのポリゴン構造体インスタンス及びテクスチャアトリビュート構造体インスタンス）とともにテクセルマッパ１２４に出力する。
【０２２５】
さらに、ピクセルステッパ１２０は、スプライトについては、スライサ１１８から与えられたスプライトのパラメータ（Ｘｓ，Ｕｓ，Ｖｓ，Ｘｅ，ΔＵ，ΔＶ及びΔＸｓ）から描画対象ピクセルをＵＶ空間へ写像したときの座標（Ｕ，Ｖ）を求める。具体的には、ピクセルステッパ１２０は、交点の始端（描画開始端）ＸｓのＵ座標Ｕｓに、１ピクセル当たりのＵ座標の変化量ΔＵを順次加えていき、各ピクセルのＵ座標ＵＸを求める。この処理を、交点の終端（描画終了端）Ｘｅに到達するまで行う。Ｖ座標ＶＸについても同様である。また、交点の始端ＸｓにΔＸｓ、すなわち「１」を順次加えていき、描画Ｘ座標Ｘｒを求める。なお、Ｘ＝０〜｜Ｘｅ−Ｘｓ｜であり、整数である。
【０２２６】
ＵＸ＝ΔＸｓ・ΔＵ・Ｘ＋Ｕｓ
ＶＸ＝ΔＸｓ・ΔＶ・Ｘ＋Ｖｓ
Ｘｒ＝Ｘ＋Ｘｓ
【０２２７】
ピクセルステッパ１２０は、求めた各ピクセルのＵＶ座標（ＵＸ，ＶＸ）、並びに描画Ｘ座標Ｘｒを、スライサ１１８から受け取った構造体インスタンス（スプライト構造体インスタンス及びテクスチャアトリビュート構造体インスタンス）とともにテクセルマッパ１２４に出力する。
【０２２８】
ピクセルディザ１２２は、ピクセルステッパ１２０から与えられたＲＧＢ値の小数部にノイズを加え、マッハバンドを目立たなくするディザリングを実行する。なお、ピクセルディザ１２２は、ディザリング後のピクセルのＲＧＢ値を、描画Ｘ座標Ｘｒ，（１−α）値，及びデプス値とともにカラーブレンダ１３２に出力する。
【０２２９】
図２０は、ピクセルディザ１２２によるディザリングの説明図である。図２０に示すように、ディザパターンは、２×２の格子状のピクセルブロックを単位としてＲＰＵ９の制御レジスタ（図示せず）に設定される。描画ピクセルのスクリーン座標系ＸＹ座標のＬＳＢの値によって、４つのパターン「００」，「０１」，「１０」，「１１」のどれが適用されるかが決定される。
【０２３０】
各パターンは２ビットの大きさで、ＲＧＢ値のそれぞれの小数部に加算される。加算の結果、整数部へのキャリーが発生する場合には、キャリーが整数部に加算される。実際に表示色として用いられる部分はＲＧＢ値の整数部であるので、ディザパターンとして設定した値が全て同じでない限り、色の境界部にノイズが現れ、マッハバンドを目立たなくする。
【０２３１】
図１２に戻って、テクセルマッパ１２４は、テクスチャアトリビュート構造体のメンバＦｉｌｔｅｒが「０」を示している場合には座標（ＵＸ，ＶＸ）の近傍４つのテクセルデータを指し示す４組のワードアドレスＷＡＤとビットアドレスＢＡＤを、メンバＦｉｌｔｅｒが「１」を示している場合には座標（ＵＸ，ＶＸ）に最も近い１つのテクセルデータを指し示す１組のワードアドレスＷＡＤとビットアドレスＢＡＤを算出して出力する。また、メンバＦｉｌｔｅｒが「０」を示している場合には、バイリニアフィルタリングにおける各テクセルの係数部に相当するバイリニアフィルタパラメータＢＦＰを算出して出力する。更に、シザリングイネーブル時のスプライトと、シザリングディセーブル時のスプライトと、ポリゴンとで互いに異なるデプス値（メンバＤｅｐｔｈ）の形式を統一して出力する。
【０２３２】
テクスチャキャッシュブロック１２６は、テクセルマッパ１２４から出力されたワードアドレスＷＡＤ、ビットアドレスＢＡＤ、構造体インスタンスのメンバＴｓｅｇｍｅｎｔから、各テクセルのアドレスを算出する。算出されたアドレスが指し示すテクセルデータが既にキャッシュに格納されている場合、格納されているテクセルデータ及びアトリビュート構造体のメンバＰａｌｅｔｔｅから、カラーパレットＲＡＭ１１のエントリを選択するインデックスを生成し、カラーパレットＲＡＭ１１に出力する。
【０２３３】
一方、当該テクセルデータが、キャッシュに格納されていない場合は、テクスチャキャッシュブロック１２６は、メモリマネージャ１４０に対して、テクセルデータの取得指示を出す。メモリマネージャ１４０は、メインＲＡＭ２５から該当するテクスチャパターンデータを取得して、テクスチャキャッシュブロック１２６のキャッシュに格納する。また、メモリマネージャ１４０は、マージソータ１０６からの指示で、後段で必要になるテクスチャパターンデータを、外部メモリ５０から取得して、メインＲＡＭ２５に格納する。
【０２３４】
この際、メモリマネージャ１４０は、テクスチャマッピングモードのポリゴン用のテクスチャパターンデータについては、１ポリゴンにマッピングされるデータ全体を一括して取得し、メインＲＡＭ２５に格納するのに対し、スプライト用のテクスチャパターンデータについては、１スプライトにマッピングされるデータをライン単位で取得し、メインＲＡＭ２５に格納する。これは、描画対象の水平ラインに含まれるピクセル群をＵＶ空間に写像すると、ポリゴンの場合はＵＶ空間中のあらゆる直線上に写像される可能性があるのに対し、スプライトの場合はＵ軸に平行な直線上にのみ写像されるからである。
【０２３５】
本実施の形態では、テクスチャキャッシュブロック１２６のキャッシュは、６４ビット×４エントリとし、ブロック置換アルゴリズムは、ＬＲＵ（ｌｅａｓｔ  ｒｅｃｅｎｔｌｙ  ｕｓｅｄ）とする。
【０２３６】
カラーパレットＲＡＭ１１は、テクスチャキャッシュブロック１２６から入力されたテクセルデータとメンバＰａｌｅｔｔｅとが連接されたインデックスが示すエントリに含まれるＲＧＢ値及び半透明合成のための（１−α）値を、バイリニアフィルタ１３０に出力する。バイリニアフィルタパラメータＢＦＰ、デプス値、及び描画Ｘ座標Ｘｒについては、そのままバイリニアフィルタ１３０に出力される。
【０２３７】
バイリニアフィルタ１３０は、バイリニアフィルタリングを実行する。テクスチャマッピングにおいて、最も単純なピクセル描画色の算出方法は、ＵＶ空間に写像されたピクセル座標（ＵＸ，ＶＸ）に最も近いテクセル座標に位置するテクセルのカラーデータを取得し、取得したカラーデータからピクセルの描画色を算出する方法である。この手法を「ニアレストネイバー」と呼ぶ。
【０２３８】
但し、隣り合うピクセルをＵＶ空間に写像した際の２点間の距離が１テクセル分の距離より極めて小さい場合、すなわち、スクリーン上でテクスチャが大きく拡大されてマッピングされる場合には、ニアレストネイバーではテクセルの境界が明瞭に表示されてしまうため、粗いモザイク状のテクスチャマッピングとなってしまう。このような問題を解消する手法として、バイリニアフィルタリングを実行する。
【０２３９】
図２１は、バイリニアフィルタ１３０によるバイリニアフィルタリングの説明図である。図２１に示すように、バイリニアフィルタ１３０は、ＵＶ空間に写像されたピクセル座標（ＵＸ，ＶＸ）の近傍４テクセルのＲＧＢ値及び（１−α）値の加重平均を算出し、ピクセルの描画色を決定する。これにより、テクセルのカラーが滑らかに補完され、マッピング結果におけるテクセルの境界が目立たなくなる。具体的には、バイリニアフィルタリングは次式（バイリニアフィルタリングの式）により実行される。ただし、次式において、「ｕ」はＵ座標ＵＸの小数部、「ｖ」はＶ座標ＶＸの小数部、「ｎｕ」は（１−ｕ）、「ｎｖ」は（１−ｖ）、である。
【０２４０】
Ｒ＝Ｒ０・ｎｕ・ｎｖ＋Ｒ１・ｕ・ｎｖ＋Ｒ２・ｎｕ・ｖ＋Ｒ３・ｕ・ｖ
Ｇ＝Ｇ０・ｎｕ・ｎｖ＋Ｇ１・ｕ・ｎｖ＋Ｇ２・ｎｕ・ｖ＋Ｇ３・ｕ・ｖ
Ｂ＝Ｂ０・ｎｕ・ｎｖ＋Ｂ１・ｕ・ｎｖ＋Ｂ２・ｎｕ・ｖ＋Ｂ３・ｕ・ｖ
Ａ＝Ａ０・ｎｕ・ｎｖ＋Ａ１・ｕ・ｎｖ＋Ａ２・ｎｕ・ｖ＋Ａ３・ｕ・ｖ
【０２４１】
ここで、Ｒ０，Ｒ１，Ｒ２及びＲ３は、それぞれ、上記４テクセルのＲ値であり、Ｇ０，Ｇ１，Ｇ２及びＧ３は、それぞれ、上記４テクセルのＧ値であり、Ｂ０，Ｂ１，Ｂ２及びＢ３は、それぞれ、上記４テクセルのＢ値であり、Ａ０，Ａ１，Ａ２及びＡ３は、それぞれ、上記４テクセルの（１−α）値である。
【０２４２】
バイリニアフィルタ１３０は、算出したピクセルのＲＧＢ値並びにＡ値（つまり（１−α）値）を、デプス値並びに描画Ｘ座標Ｘｒとともに、カラーブレンダ１３２に出力する。
【０２４３】
図１２を参照して、カラーブレンダ１３２の説明の前に、ラインバッファブロック１３４について説明する。ラインバッファブロック１３４は、ラインバッファＬＢ１及びＬＢ２を含み、一方のラインバッファが表示用に使用されているときは、他方のラインバッファが描画用に使用され、表示用と描画用とを交互に切り替えて使用するダブルバッファ方式を採用する。表示用に使用されているラインバッファＬＢ１あるいはＬＢ２は、ビデオタイミングジェネレータ１３８からの水平走査カウント信号ＨＣ及び垂直走査カウント信号ＶＣに従って、ピクセルごとのＲＧＢ値を、ビデオエンコーダ１３６に出力する。
【０２４４】
カラーブレンダ１３２は、半透明合成を実行する。具体的には、次の通りである。カラーブレンダ１３２は、ピクセルディザ１２２あるいはバイリニアフィルタ１３０から与えられたピクセルのＲＧＢ値及び（１−α）値と、描画対象のラインバッファＬＢの描画対象ピクセル位置（描画Ｘ座標Ｘｒが示すピクセル）に格納されているＲＧＢ値とを用い、次式により、アルファブレンディングを実行し、結果を同じラインバッファＬＢの描画対象ピクセル位置に書き込む。
【０２４５】
Ｒｂ＝Ｒｆ・（１−αｒ）＋Ｒｒ
Ｇｂ＝Ｇｆ・（１−αｒ）＋Ｇｒ
Ｂｂ＝Ｂｆ・（１−αｒ）＋Ｂｒ
αｂ＝αｆ・（１−αｒ）＋αｒ
【０２４６】
ここで、「１−αｒ」は、ピクセルディザ１２２あるいはバイリニアフィルタ１３０から与えられた（１−α）値である。「Ｒｒ」、「Ｇｒ」及び「Ｂｒ」は、それぞれ、ピクセルディザ１２２あるいはバイリニアフィルタ１３０から与えられたＲＧＢ値である。「Ｒｆ」、「Ｇｆ」及び「Ｂｆ」は、それぞれ、描画用に使用されているラインバッファＬＢの描画対象ピクセル位置から取得したＲＧＢ値である。一般的なアルファブレンディングのアルゴリズムにおいては、上式のＲｒ，Ｇｒ，およびＢｒの項は、それぞれＲｒ・αｒ、Ｇｒ・αｒ、およびＢｒ・αｒとなるが、本実施の形態では、予めＲｒ・αｒ，Ｇｒ・αｒ，およびＢｒ・αｒの計算結果をＲｒ、Ｇｒ、およびＢｒとして用意しておくことにより、演算回路の簡略化を行っている。
【０２４７】
ビデオエンコーダ１３６は、表示用に使用されているラインバッファＬＢ１あるいはＬＢ２から入力されたＲＧＢ値と、ビデオタイミングジェネレータ１３８から入力されたタイミング情報（複合同期信号ＳＹＮ、複合ブランキング信号ＢＬＫ、バーストフラグ信号ＢＳＴ、及びライン交番信号ＬＡ等）と、を信号ＶＳに対応したコンポジットビデオ信号を表すデータストリームＶＤに変換する。信号ＶＳは、テレビジョン方式（ＮＴＳＣやＰＡＬ等）を指示する信号である。
【０２４８】
ビデオタイミングジェネレータ１３８は、入力されるクロックを基に、水平走査カウント信号ＨＣ及び垂直走査カウント信号ＶＣ、並びに、複合同期信号ＳＹＮ、複合ブランキング信号ＢＬＫ、バーストフラグ信号ＢＳＴ、及びライン交番信号ＬＡ等のタイミング信号を生成する。水平走査カウント信号ＨＣは、システムクロックの１周期毎にカウントアップされ、１水平ラインのスキャンが終了すると、リセットされる。また、垂直走査カウント信号ＶＣは、１／２水平ラインのスキャンが終了するたびにカウントアップされ、１フレームあるいは１フィールドのスキャンが終了すると、垂直走査カウント信号ＶＣはリセットされる。
【０２４９】
さて、次に、図１０のＹＳＵ１９によるソート処理の詳細を図面を参照しながら説明する。上述したように、ＹＳＵ１９によるソート処理で採用するソート手法は、ヒープソートである。
【０２５０】
上記のように、ポリゴン構造体配列のソート処理とスプライト構造体配列のソート処理とは別個に行われる。しかし、それぞれにおいて、同じソート処理が実行されるので、後述の図２２及び図２３において、配列およびその要素は、ポリゴン構造体配列のソート処理の場合には、それぞれポリゴン構造体配列およびポリゴン構造体インスタンスを指し、スプライト構造体配列のソート処理の場合には、それぞれスプライト構造体配列およびスプライト構造体インスタンスを指す。
【０２５１】
一般に、配列の要素は、値を代入するための、インデックスが付された変数（入れ物）として定義されたり、あるいは、インデックスが付された変数に代入された値そのものとして定義されたりする。本実施の形態では、両者を区別する必要があるときは、変数（入れ物）としての配列の要素を「要素」、その変数に代入された値を「要素値」又は「要素の値」と呼ぶ。
【０２５２】
図２２は、図１０のＹＳＵ１９による配列Ａのヒープ構築後のヒープ構造を示す図である。図２２では、配列Ａの要素数を１０個とし、Ｙソート前の要素Ａ［０］〜Ａ［９］の要素値をそれぞれ要素値ｅｖ０〜ｅｖ９と表す。
【０２５３】
図２２を参照して、本実施の形態におけるヒープ構造は、二分木の構造を持ち、１つの親に対して２つの子が接続される。但し、ヒープ構造の末端においては、子を１つしか持たない親が存在する場合がある。親は子に対して高い順位を持つが、２つの子の間の順位については、特にルールは定められていない。
【０２５４】
ここで、順位とは、ソートルール１〜４（ノンインタレーススキャンの場合はソートルール１〜３）で定められる構造体インスタンス間（ポリゴン構造体配列のＹソートの場合にはポリゴン構造体インスタンス間、スプライト構造体配列のＹソートの場合にはスプライト構造体インスタンス間）の優先順位を指す。つまり、順位とは、ソートルール１〜４（ノンインタレーススキャンの場合はソートルール１〜３）で定められる要素値間（ポリゴン構造体配列のＹソートの場合にはポリゴン構造体配列の要素値間、スプライト構造体配列のＹソートの場合にはスプライト構造体配列の要素値間）の優先順位を指す。木構造の上位ほど順位が高いので、図２２の例では、要素値ｅｖ３が最も順位の高い要素値である。
【０２５５】
メインＲＡＭ２５へのヒープ構造の格納方法を説明する。一般的なヒープ構造の場合、最も順位の高い親の要素値から順に、メモリ上の配列の先頭から格納される。ヒープソートにおいては、ソート結果が１つずつ確定するため、一般的には、メモリ領域を効率的に用いるために、順位が確定した要素値は、ヒープ構造の末端の子の要素値と入れ替えられて格納される。従って、最も順位の高い親の要素値は、配列の末尾に格納されて、ヒープ構造から切り離される。これに対して、本実施の形態では、一般的な順序とは逆の順序で、ヒープ構造をメモリ上の配列に格納する。この点を、図２２のヒープ構造を例に挙げながら説明する。
【０２５６】
図２３は、図２２のヒープ構造のメインＲＡＭ２５への格納方法の説明図である。図２３（ａ）及び図２２に示すように、本実施の形態のヒープ構造においては、最も順位の高い親の要素値から順に、メインＲＡＭ２５上の配列Ａの末尾から格納される。そして、図２３（ｂ）に示すように、順位が確定し配列Ａの末尾Ａ［９］に格納された最も順位の高い親の要素値ｅｖ３と、配列Ａの先頭Ａ［０］に格納されたヒープ構造の末端の子の要素値ｅｖ５と、が入れ替えられ、要素値ｅｖ３が格納された先頭の要素Ａ［０］は、ヒープ構造から切り離される。理由は次の通りである。
【０２５７】
上記のように、ＹＳＵ１９は、順位（ソート結果）が１つ確定する度にパルス信号（ポリゴンの場合パルス信号ＰＰＬ、スプライトの場合パルス信号ＳＰＬ）の１パルスをＲＰＵ９に出力する。これらのパルス信号を受けて、ＲＰＵ９は、順位が確定した要素値、つまり、順位が確定した構造体インスタンスを、配列の先頭から読み出して描画処理を行う。このため、一般的な順序とは逆の順序で、ヒープ構造をメインＲＡＭ２５上の配列に格納する。
【０２５８】
配列の１要素のサイズについて説明する。配列の１要素のサイズは、ポリゴン構造体とスプライト構造体とで異なる。ポリゴン構造体の場合、配列の１要素（１個のポリゴン構造体インスタンス）は１６バイトで構成され、スプライト構造体の場合、配列の１要素（１個のスプライト構造体インスタンス）は８バイトで構成される（図１３、図１５、及び図１６参照）。但し、ポリゴン構造体インスタンスとスプライト構造体インスタンスとは別々の配列に格納されるため、メインＲＡＭ２５上の同じ配列内に異なるサイズの要素が混在することはない。また、ＹＳＵ１９は、ポリゴン構造体配列のソートとスプライト構造体配列のソートとを独立に行う。
【０２５９】
次に、ＹＳＵ１９によるポリゴン構造体配列のＹソート処理をフローチャートを用いて説明する。ＹＳＵ１９によるスプライト構造体配列のＹソート処理は、ポリゴン構造体配列のＹソート処理と同様の流れで行われるので説明を省略する。
【０２６０】
図２４は、図１０のＹＳＵ１９によるポリゴン構造体配列のＹソート処理の全体的な流れの一例を示すフローチャートである。なお、図２４及び後述の図２５〜図２７において、特に明示しない限り、配列というときは、ポリゴン構造体配列を指す。
【０２６１】
図２４を参照して、ステップＳ２０にて、ＹＳＵ１９は、配列のソートの開始前に、ソート対象となる当該配列の先頭アドレスをＹＳＵ１９内の制御レジスタ「Ｐｏｌｙｇｏｎ＿Ａｒｒａｙ＿ＹＳＵ＿Ｂａｓｅ＿Ａｄｄｒｅｓｓ」（図示せず）から取得し、かつ、当該配列の要素数「ｓ」をＹＳＵ１９内の制御レジスタ「Ｎｕｍｂｅｒ＿ｏｆ＿Ｓｏｒｔｅｄ＿Ｐｏｌｙｇｏｎｓ」（図示せず）から取得する。なお、図２２及び図２３の例では、ｓ＝１０である。
【０２６２】
ちなみに、スプライト構造体配列のソートを行う場合には、当該スプライト構造体配列の先頭アドレスをＹＳＵ１９内の制御レジスタ「Ｓｐｒｉｔｅ＿Ａｒｒａｙ＿ＹＳＵ＿Ｂａｓｅ＿Ａｄｄｒｅｓｓ」（図示せず）から取得し、かつ、当該スプライト構造体配列の要素数「ｓ＃」をＹＳＵ１９内の制御レジスタ「Ｎｕｍｂｅｒ＿ｏｆ＿Ｓｏｒｔｅｄ＿Ｓｐｒｉｔｅｓ」（図示せず）から取得する。
【０２６３】
次のステップＳ２１にて、ＹＳＵ１９は、ヒープ構造を構築する（ヒープ構築処理）。ヒープ構築処理の詳細は後述する。この処理の完了後、配列全体がヒープ構造となり、それぞれの要素の接続において、親の要素の順位が子の要素の順位より高いことが保証される。したがって、ヒープ構築処理後、最も順位の高い親、すなわち「根（ｒｏｏｔ）」の親の要素の順位は、配列の全要素中で最も高いことが確定する。
【０２６４】
以降、ＹＳＵ１９は、順位の高いものから要素が１つ確定するたびに、「根」の親の要素の値と、ヒープ構造の末端の子の要素の値と、を交換する（入れ替える）。これは、順位の確定した「根」の親の要素をヒープ構造から切り離し、メインＲＡＭ２５上の配列の先頭から順に整列させることを意味する。
【０２６５】
従って、ＹＳＵ１９は、ステップＳ２１の次のステップＳ２２にて、最も順位の高い要素として確定した親の要素の値、つまり要素［ｓ−１］の値と、ヒープ構造の末端の子の要素の値、つまり要素［０］の値と、を交換するために、変数ｉに「０」を設定し、続くステップＳ２３にて、要素［０］の値と要素［ｓ−１］の値とを交換する。つまり、要素［０］の値を要素［ｓ−１］へ、要素［ｓ−１］の値を要素［０］へ、代入する。この交換後、要素［０］はヒープ構造から切り離される。なお、図２２及び図２３の例では、要素Ａ［０］の値ｅｖ５と要素Ａ［９］の値ｅｖ３とが交換される。
【０２６６】
ステップＳ２７の後のステップＳ２３においては、ＹＳＵ１９は、その時のヒープ構造における最も順位の高い要素として確定した親の要素の値、つまり要素［ｓ−１］の値と、その時のヒープ構造の末端の子の要素の値、つまりインクリメント後（ステップＳ２５）の要素［ｉ］の値と、を交換する。つまり、要素［ｉ］の値を要素［ｓ−１］へ、要素［ｓ−１］の値を要素［ｉ］へ、代入する。この交換後、要素［ｉ］はヒープ構造から切り離される。
【０２６７】
続くステップＳ２４にて、ＹＳＵ１９は、１個の要素の順位確定を通知すべく、パルス信号ＰＰＬの１パルスをＲＰＵ９に出力する。ちなみに、スプライト構造体配列のソートの場合には、パルス信号ＳＰＬの１パルスをＲＰＵ９に出力する。次のステップＳ２５にて、ＹＳＵ１９は、変数ｉの値をインクリメントする。従って、変数ｉは常にヒープ構造の末端を指し示すように設定される。これは、インクリメント前の要素［ｉ］がヒープ構造から切り離され、インクリメント後の要素［ｉ］が新たにヒープ構造の末端となったことを意味する。
【０２６８】
ステップＳ２５で変数ｉをインクリメントした後の値が「ｓ−１」と同じ場合は、ソートが完了していないヒープ構造に含まれる要素は、要素［ｓ−１］のみということになる。これは、全ての要素値のソートが完了したことを意味する。従って、ＹＳＵ１９は、ステップＳ２６にて、ｉ＝ｓ−１と判断したときは、ステップＳ２８に進んで、最後の要素値の順位確定を示すパルス信号ＰＰＬ（スプライトの場合はパルス信号ＳＰＬ）を１パルス出力し、Ｙソート処理を終了する。
【０２６９】
一方、ＹＳＵ１９は、ステップＳ２６にて、変数ｉが「ｓ−１」と等しくないと判断したときは、Ｙソート処理が完了していないので、ステップＳ２７に進む。
【０２７０】
この時点では、ステップＳ２３の交換処理により、ヒープ構造の末端の子の要素の値が「根」の親の位置に格納されているため、ヒープ構造は崩れている。この状態からヒープ構造を再構築するために、ステップＳ２７にて、ＹＳＵ１９は、「ダウンヒープ処理」を行う。ここでは、「根」の親から順に、いずれかの子の要素の順位が親の要素より高い場合に、子の要素の値と親の要素の値とを入れ替え、入れ替えた後の子の要素を新たな親の要素として、同じ処理をヒープ構造の末端まで行う処理を「ダウンヒープ処理」と呼称する。ダウンヒープ処理の詳細は後述する。
【０２７１】
ステップＳ２７では、要素［ｓ−１］を処理開始時の親とし、「ｓ−ｉ」をヒープ構造の要素数とするダウンヒープ処理を行う。ダウンヒープ処理完了に伴い、ヒープ構造が再構築される。したがって、ステップＳ２７終了後の「根」の親は、その時点のヒープ構造で最も高い順位であることが確定する。その後、ステップＳ２３に戻って、ソート処理が継続される。
【０２７２】
図２５は、図２４のステップＳ２１のヒープ構築処理の流れの一例を示すフローチャートである。図２５を参照して、ステップＳ４０にて、ＹＳＵ１９は、変数ｊに「０」を設定する。変数ｊは、ダウンヒープ処理における最初の子の要素を指し示すものであり、初期状態では、ヒープ構造全体の末端の要素、すなわち要素［０］を指し示す。
【０２７３】
続くステップＳ４１にて、ＹＳＵ１９は、要素［ｊ］の親の要素［ｐ］を特定する。親の要素［ｐ］のインデックス「ｐ」は、以下の計算式により算出される。次式において、「ｓ」はヒープ構造全体の要素数である。但し、右辺の除算の商は常に整数で得られるものとし、剰余は切り捨てる。
【０２７４】
ｐ＝ｓ−（ｓ−ｊ）／２
【０２７５】
ステップＳ４２にて、ＹＳＵ１９は、ステップＳ４１で特定した親の要素［ｐ］を親とし、「ｓ」をヒープ構造全体の要素数とするダウンヒープ処理を行う。ダウンヒープ処理の詳細は後述する。
【０２７６】
ステップＳ４２のダウンヒープ処理完了後、ステップＳ４３にて、ＹＳＵ１９は、変数ｊの値をインクリメントする。そして、ステップＳ４４にて、ＹＳＵ１９は、インクリメント後の変数ｊの値が「ｓ−１」より小さければ、ステップＳ４１へ戻る。一方、インクリメント後の変数ｊの値が「ｓ−１」に等しければ、ＹＳＵ１９は、ヒープ構築処理を終了し、図２４のステップＳ２２に進む。
【０２７７】
図２６は、ダウンヒープ処理の流れの一例を示すフローチャートである。このダウンヒープ処理は、図２４のステップＳ２７及び図２５のステップＳ４２において実行される。
【０２７８】
図２６を参照して、ステップＳ６０にて、ＹＳＵ１９は、親の要素のインデックスと、対象となるヒープ構造の要素数とから、親に対する子の個数がいくつであるかを特定する。ＹＳＵ１９は、親の要素のインデックスを「ｐ」とし、対象となるヒープ構造の要素数を「ｓ」としたときに、２（ｓ−ｐ）の値が「ｓ」より小さい場合には子の個数が２個、「ｓ」と同じ場合には子の個数が１個、「ｓ」より大きい場合には子の個数が０個であるとする。
【０２７９】
ステップＳ６１において、ＹＳＵ１９は、子の個数が「０」と判定すると、ダウンヒープ処理を終了する。また、ステップＳ６２にて、ＹＳＵ１９は、子の個数が「１」と判定すると、ステップＳ６３に進んで、その１つの子を親との比較対象として設定し、ステップＳ６６に進む。一方、ステップＳ６２にて、ＹＳＵ１９は、子の個数が「１」でない、つまり、「２」と判定すると、ステップＳ６４に進む。
【０２８０】
ステップＳ６４では、ＹＳＵ１９は、子の個数が「２」であるので、どちらの子がより順位が高いかを判定するために、順位比較処理を行う。順位比較処理の詳細は後述する。そして、ステップＳ６５にて、ＹＳＵ１９は、順位比較処理の結果、順位の高い方の子を親との比較対象として設定し、ステップＳ６６に進む。
【０２８１】
ステップＳ６３の後あるいはステップＳ６５の後のステップＳ６６では、ＹＳＵ１９は、比較対象に設定された子の要素と、親の要素との順位比較処理を行う。比較処理の結果、ステップＳ６７にて、ＹＳＵ１９が親の順位が高いと判定した場合、そこでダウンヒープ処理は終了する。一方、子の順位が高いと判定した場合、ステップＳ６８にて、ＹＳＵ１９は、比較対象の子の要素の値と、親の要素の値とを交換する。交換後、ステップＳ６９にて、ＹＳＵ１９は、値が交換された子の要素（つまり、交換前の親の要素の値を格納している要素）を、新たな親として設定し、ステップＳ６０に戻る。
【０２８２】
図２７は、順位比較処理の流れの一例を示すフローチャートである。この順位比較処理は、図２６のステップＳ６４及びＳ６６において実行される。順位比較処理では、ソートルール１〜４（ノンインタレーススキャンの場合はソートルール１〜３）に基づいて、２つのポリゴン構造体インスタンス間で順位を比較する。つまり、順位比較処理では、ソートルール１〜４（ノンインタレーススキャンの場合はソートルール１〜３）に基づいて、配列の２つの要素間で順位を比較する。ここで、比較対象の２つの要素（ポリゴン構造体インスタンス）をそれぞれ要素「Ａ」及び「Ｂ」と表記する。
【０２８３】
ステップＳ８０にて、ＹＳＵ１９は、要素「Ａ」及び「Ｂ」ごとに、最小Ｙ座標と描画先頭ライン（描画上端ライン）のＹ座標と、を比較する。この例では、比較対象の要素「Ａ」及び「Ｂ」は、ポリゴン構造体インスタンスであるので、メンバＡｙ，Ｂｙ及びＣｙ（図１３及び図１５参照）のうち最も小さな値が、最小Ｙ座標として扱われる。ちなみに、比較対象の要素「Ａ」及び「Ｂ」が、スプライト構造体インスタンスである場合、シザリングイネーブル時はメンバＡｙの値＋２５６が、シザリングディセーブル時はメンバＡｙの値そのものが、最小Ｙ座標として扱われる（図１６参照）。
【０２８４】
ステップＳ８１にて、ＹＳＵ１９は、要素「Ａ」の最小Ｙ座標のみが、描画先頭ラインのＹ座標以下であると判断した場合、すなわち、要素「Ａ」に基づくポリゴンのみが、描画先頭ラインと交わるか、あるいは、描画先頭ラインより上にあると判断した場合、ステップＳ８２に進み、要素「Ａ」の順位が高いと判定し、順位比較処理を終了する（ソートルール１）。
【０２８５】
ステップＳ８３にて、ＹＳＵ１９は、要素「Ｂ」の最小Ｙ座標のみが、描画先頭ラインのＹ座標以下であると判断した場合、すなわち、要素「Ｂ」に基づくポリゴンのみが、描画先頭ラインと交わるか、あるいは、描画先頭ラインより上にあると判断した場合、ステップＳ８４に進み、要素「Ｂ」の順位が高いと判定し、順位比較処理を終了する（ソートルール１）。
【０２８６】
要素「Ａ」及び「Ｂ」の双方の最小Ｙ座標が、描画先頭ラインのＹ座標以下である場合は、要素「Ａ」及び「Ｂ」のそれぞれに基づくポリゴンが、描画先頭ラインと交わるか、あるいは、描画先頭ラインより上にあることを意味する。要素「Ａ」及び「Ｂ」の双方の最小Ｙ座標が描画先頭ラインより上にある場合、要素「Ａ」及び「Ｂ」に基づくポリゴンは、スクリーンに描画されないため、ソートルール１によって判定される順位は描画結果に影響を与えない。この点、スプライトについても同様である。
【０２８７】
従って、ステップＳ８５にて、ＹＳＵ１９は、要素「Ａ」及び「Ｂ」の双方の最小Ｙ座標が描画先頭ラインのＹ座標以下であると判断した場合、つまり、要素「Ａ」及び「Ｂ」に基づく双方のポリゴンが、描画先頭ラインと交わっていると判断した場合、ステップＳ８６に進んで、要素「Ａ」及び「Ｂ」間の順位を、最小Ｙ座標の比較でなく、デプス値の比較により定める（ソートルール３）。
【０２８８】
この場合、ポリゴン構造体にメンバＤｅｐｔｈがあり（図１３及び図１５参照）、この値の大小により順位が判定される。スプライトの場合も同様であり、スプライト構造体のメンバＤｅｐｔｈの値の大小により順位が判定される（図１６参照）。メンバＤｅｐｔｈのビット数は、ポリゴン構造体と、シザリングイネーブル時のスプライト構造体と、シザリングディセーブル時のスプライト構造体と、で異なるが、ＹＳＵ１９が比較するのは、同一フォーマットの構造体インスタンス同士であるため、単純にメンバＤｅｐｔｈの値を比較するだけで大小判定を行うことができる。
【０２８９】
ステップＳ８６に続くステップＳ８７にて、ＹＳＵ１９は、デプス値の比較の結果、要素「Ａ」のデプス値が、要素「Ｂ」のデプス値以上であると判断した場合、ステップＳ８８に進んで、要素「Ａ」の順位が高いと判定し、順位比較処理を終了する。一方、ＹＳＵ１９は、デプス値の比較の結果、要素「Ａ」のデプス値が、要素「Ｂ」のデプス値より小さいと判断した場合、ステップＳ８９に進んで、要素「Ｂ」の順位が高いと判定し、順位比較処理を終了する。
【０２９０】
一方、ステップＳ８５において、ＹＳＵ１９は、要素「Ａ」及び「Ｂ」の双方の最小Ｙ座標が、描画先頭ラインのＹ座標より大きいと判定した場合、ステップＳ９０に進んで、双方の最小Ｙ座標同士を比較する。但し、インタレーススキャンモードでの順位比較処理においては、描画対象となるフィールドのライン上にある最小Ｙ座標の値と、その１つ前のフィールドのライン上にある、１つ小さい最小Ｙ座標の値と、が同じであるとして、比較を行う（ソートルール４）。一方、ノンインタレーススキャンモードでの順位比較処理においては、単純に最小Ｙ座標の大小が比較される。
【０２９１】
そして、ステップＳ９１にて、ＹＳＵ１９は、要素「Ａ」及び「Ｂ」の双方の最小Ｙ座標が同じであると判定した場合、ステップＳ８６に進んで、デプス値の比較により、要素「Ａ」及び「Ｂ」の順位を判定する（ソートルール２）。一方、ステップＳ９１にて、ＹＳＵ１９が、要素「Ａ」及び「Ｂ」の最小Ｙ座標が異なると判定した場合、ステップＳ９２に進む。
【０２９２】
ステップＳ９２では、ＹＳＵ１９は、要素「Ａ」の最小Ｙ座標が、要素「Ｂ」の最小Ｙ座標より小さいと判断した場合、ステップＳ９３に進んで、要素「Ａ」の順位が高いと判定して、順位比較処理を終了する（ソートルール１）。一方、ＹＳＵ１９は、要素「Ａ」の最小Ｙ座標が、要素「Ｂ」の最小Ｙ座標以上であると判断した場合、ステップＳ９４に進んで、要素「Ｂ」の順位が高いと判定して、順位比較処理を終了する（ソートルール１）。
【０２９３】
なお、図２４〜図２７において、ポリゴン構造体配列のＹソート処理を例に挙げて説明したが、同様の処理が、スプライト構造体配列のＹソート処理でも行われる。
【０２９４】
さて、以上のように、本実施の形態によれば、グラフィック要素（ポリゴン、スプライト）の最小Ｙ座標が、昇順（小から大の順）で並ぶように、つまり、グラフィック要素の出現順で、グラフィック要素ごとの構造体インスタンスを並べ替えている（ソート）。また、１度描画で用いられた構造体インスタンスは、リサイクルバッファに格納され、描画対象ラインのＹ座標が当該構造体インスタンスの最大Ｙ座標（ポリゴンについては３頂点のＹ座標のうち最も大きいＹ座標、スプライトについては４頂点のＹ座標のうち最も大きいＹ座標）を超えるまで再利用される。
【０２９５】
従って、ソート後の構造体インスタンスを順番に読み出して、描画処理を行うだけでよいため、描画のたびに、全ての構造体インスタンスの中から、そのとき描画すべき構造体インスタンスを検索する処理が不要になり、処理を高速化できる。以上の結果、１フレーム以上のイメージを格納するための大容量のバッファ（フレームバッファ等）を実装する必要は必ずしもなく、より容量の小さいバッファ（ラインバッファや、１ラインに満たないピクセルを描画するピクセルバッファ等）を実装した場合であっても、多くのグラフィック要素を組み合わせた三次元イメージの表示が可能になる。
【０２９６】
一般的な技術により、ラインバッファあるいはピクセルバッファに描画を行おうとすると、１ラインごとあるいは所定数のピクセルごとに、全構造体インスタンスの中から、描画対象の構造体インスタンスを検索しなければならないが、本実施の形態では、ＹＳＵ１９により、予め、最小Ｙ座標の昇順で（つまりグラフィック要素の出現順で）ソートが行われているため、そのような検索処理が不要になる。また、そのような検索処理を行っていたのでは、多くのグラフィック要素を組み合わせた三次元イメージの表示が困難になる。ちなみに、フレームバッファを実装するときは、１フレーム分のイメージを格納できるので、そもそも、そのような検索処理は不要で、デプス値の大きいものから順に描画していけばよい。
【０２９７】
また、本実施の形態によれば、ラインバッファＬＢ１あるいはＬＢ２への新たなピクセル情報の書き込み（新たなピクセルの描画）のために、構造体インスタンスが再利用可能な場合は、その構造体インスタンスは、リサイクルバッファ１１０に格納される。このため、同じ構造体インスタンスを使用する新たなピクセルの描画のたびに、ソート後の全ての構造体インスタンスが格納されたメインＲＡＭ２５から、その同じ構造体インスタンスを繰り返し読み出す処理が不要になって、より処理の高速化を図ることができる。
【０２９８】
また、デプスコンパレータ１１２を設けて、ＹＳＵ１９が並べ替えた順番で新たに読み出された構造体インスタンスと、再利用のためのリサイクルバッファ１１０に格納された構造体インスタンスと、の描画順序（つまり、これら構造体インスタンスに基づくピクセルの描画順序）を判定している。このため、判定終了後に、再利用可能な構造体インスタンスをリサイクルバッファ１１０に送って順番に格納するだけで、リサイクルバッファ１１０には、再利用可能な構造体インスタンスについて、適切な描画順序で（つまり、デプス値が大きいものが先頭に来る順で）構造体インスタンスが格納される。このように、リサイクルバッファ１１０には、再利用可能な構造体インスタンスについて適切な描画順序で格納されているところ、これらは、ＹＳＵ１９が並べ替えた順番で新たに読み出された構造体インスタンスとの間で、さらに描画順序が判定されるので、常に適切な描画順序での（つまり、デプス値が大きいもの順での）描画が可能となる。
【０２９９】
さらに、本実施の形態によれば、複数のグラフィック要素を表示する場合であって、その複数のグラフィック要素の最小Ｙ座標が同じ場合、ソートルール２が適用され、スクリーンを構成する各ラインにおいて、デプス値の降順（大から小の順）で構造体インスタンスが並べられる。従って、各ラインにおいて、構造体インスタンスに基づくグラフィック要素は、デプス値の大きいもの順で描画される。
【０３００】
ここで、構造体インスタンスを最小Ｙ座標の小さいもの順でソートし（ソートルール１）、最小Ｙ座標の同じものについてはデプス値の大きいもの順でソートする場合（ソートルール２）、つまり、ソートルール１及び２のみでは、表示先頭ラインの描画においては、必ずしもデプス値の大きいもの順での描画が保証されない。
【０３０１】
しかし、本実施の形態では、複数のグラフィック要素が、スクリーンの先頭ラインに表示すべきピクセルを含む場合、ソートルール３が適用され、それらの最小Ｙ座標に関係なく、つまり、それらの最小Ｙ座標を同一とみなして、デプス値の降順で構造体インスタンスが並べられる。従って、先頭ラインにおいても、構造体インスタンスに基づくグラフィック要素は、デプス値の大きいもの順で描画される。
【０３０２】
以上の結果、全ラインにおいて、グラフィック要素は、必ずデプス値が大きいもの順で描画されるので、半透明合成を適切に行うことができる。何故ならば、半透明のグラフィック要素の描画色は、当該グラフィック要素の奥にあるグラフィック要素の描画色に依存するため、グラフィック要素を奥から順に描画する必要がある。
【０３０３】
さらに、本実施の形態によれば、プリフェッチバッファ１０８が設けられ、このプリフェッチバッファ１０８は、ＹＳＵ１９がソートした順番での構造体インスタンスの入力タイミングとデプスコンパレータ１１２への構造体インスタンスの出力タイミングとの緩衝機構である。これにより、ＹＳＵ１９がソートした順番での構造体インスタンスの入力の、ＲＰＵ９にとっての待ち時間を削減できる。
【０３０４】
さらに、本実施の形態によれば、ラインバッファＬＢ１，ＬＢ２を実装しているので、フレームバッファを使用する場合よりもコストを低く抑えることができるし、また、１ラインのピクセル数に満たない数のピクセルデータを格納するピクセルバッファを使用する場合よりも簡素な回路構成で（簡単な制御で）描画を実現できる。
【０３０５】
さらに、本実施の形態によれば、ポリゴン構造体インスタンスと、スプライト構造体インスタンスと、で別個にソートを行っているので、ポリゴン構造体インスタンスと、スプライト構造体インスタンスと、の形式及びサイズが異なっている場合でも容易にソートが可能であり、構造体インスタンスを格納するためのメモリ領域の使用効率も高まる。
【０３０６】
このように、ポリゴン構造体インスタンス及びスプライト構造体インスタンスが独立してソートされた場合であっても、マージソータ１０６を設けることで、描画処理の前にポリゴン構造体インスタンス群とスプライト構造体インスタンス群がマージソートされるため、適切な描画処理が可能となる。
【０３０７】
さらに、本実施の形態によれば、ノンインタレーススキャンのみならず、インタレーススキャンにも対応している。具体的には次の通りである。
【０３０８】
インタレーススキャンによってイメージが表示される場合、最小Ｙ座標が飛び越し走査により飛び越されたラインを示す構造体インスタンスと、最小Ｙ座標が描画対象のラインを示す構造体インスタンスとが、表示対象ラインの描画処理において共に読み出される。したがって、これらの構造体インスタンスの示す最小Ｙ座標を同じ値とみなし、デプス値の大きいもの順にソートを行うことにより、インタレーススキャンの場合でもデプス値の大きいもの順での描画処理が保証される。そこで、奇数フィールド表示のときと偶数フィールド表示のときとで異なるソートを行うソートルール４を設けている。
【０３０９】
以上の結果、ノンインタレーススキャンのみならず、インタレーススキャンによる表示を行う場合においても、デプス値の大きいものから描画されるので、適切な半透明合成を実現できる。
【０３１０】
さらに、本実施の形態によれば、ＹＳＵ１９は、ソートにおいて順位の高いものから構造体インスタンスが１つ確定するたびに、その都度、パルスＰＰＬ，ＳＰＬを、ＲＰＵ９に出力する。このため、ＹＳＵ９は、全構造体インスタンスのソートの完了を待つことなく、逐次、構造体インスタンスを読み込むことができる。さらに、表示中のフィールドに対する各構造体インスタンスのソートを、直前の垂直ブランキング期間あるいは当該フィールド表示中に実行開始することにより、ソート前の演算のために余裕を持ったより十分な時間を確保できる。
【０３１１】
特に、上述のモード２においては、垂直ブランキング期間の開始直後にソートを実行しているので、ソート前の演算のために余裕を持ったより十分な時間を確保できる（図９（ａ）参照）。
【０３１２】
さらに、本実施の形態によれば、ＹＳＵ１９が実装するソート技法は、ヒープソートであるため、構造体インスタンスのソート結果が１つずつ確定され、ソート結果の確定のたびに、パルスＰＰＬ，ＳＰＬを出力する機構を容易に実現できる。また、全構造体インスタンスのソートに必要な時間のバラツキを少なくできる。
【０３１３】
さらに、本実施の形態によれば、ソートルール１〜４において、対象の座標を最小Ｙ座標としている。このため、全てのグラフィック要素に対して同じ条件でソートができるので、正しい描画順序で描画を行うことができる。
【０３１４】
なお、本発明は、上記の実施の形態に限られるものではなく、その要旨を逸脱しない範囲で種々の態様において実施することが可能であり、例えば、以下のような変形も可能である。
【０３１５】
（１）上記では、カラーブレンダ１３２による半透明合成を行っているため、各ラインにおいて、グラフィック要素（ポリゴン、スプライト）は、デプス値が大きいものから先に描画した。しかし、半透明合成を行わない場合は、デプス値が小さいものから描画することが好ましい。なぜなら、デプス値が小さい、より手前に表示されるべきグラフィック要素から先に描画することにより、描画能力や１ラインに描画するグラフィック要素の数が多すぎる等の理由により、仮に、１ラインに描画すべき全てのグラフィック要素の描画が、表示までに間に合わなかった場合でも、デプス値が大きい、より奥に表示されるべきグラフィック要素から先に描画する場合と比較して、表示後の見た目の印象が良くなるからである。また、デプス値が小さいグラフィック要素から描画することにより、より奥に表示されるべきグラフィック要素については、既に描画されたグラフィック要素と重なる部分については、描画が不要であるため、処理の高速化を図ることができるからである。
【０３１６】
（２）上記では、描画のため、スクリーンの１ライン分のデータを格納可能なラインバッファＬＢ１，ＬＢ２をＲＰＵ９内に設けた。ただし、１ライン分より少ないピクセル数分のデータを格納する２つのピクセルバッファをＲＰＵ９内に設けることもできる。また、Ｋ（Ｋは２以上の整数）ライン分のデータを格納可能な２つのバッファをＲＰＵ９内に設けることもできる。
【０３１７】
（３）上記では、ＲＰＵ９において、ダブルバッファ方式を採用したが、シングルバッファ方式を採用することもできるし、３以上のバッファを使用する方式を採用することもできる。
【０３１８】
（４）上記では、プリフェッチバッファ１０８の記憶容量とリサイクルバッファ１１０の記憶容量とを同一にする例を挙げたが、異ならせることもできる。
【０３１９】
（５）上記では、ＹＳＵ１９は、１つのポリゴン構造体インスタンスのソートが確定するたびに、パルスＰＰＬを出力したが、所定数のポリゴン構造体インスタンスのソートが確定するたびに、パルスＰＰＬを出力することもできる。パルスＳＰＬについても同様である。
【０３２０】
（６）上記では、テクスチャデータの色の指定に、カラーパレットを用いる間接指定方式を採用したが、各テクセルの色を直接指定する直接指定方式を採用することもできる。
【０３２１】
以上、本発明を実施例により詳細に説明したが、当業者にとっては、本発明が本願中に説明した実施例に限定されるものではないということは明らかである。本発明は、請求の範囲の記載により定まる本発明の趣旨及び範囲を逸脱することなく修正及び変更態様として実施することができる。従って、本願の記載は、例示説明を目的とするものであり、本発明に対して何ら制限的な意味を有するものではない。
【図１】
2011159306.tif 000003
【図２】
2011159306.tif 000004
【図３】
2011159306.tif 000005
【図４】
2011159306.tif 000006
【図５】
2011159306.tif 000007
【図６】
2011159306.tif 000008
【図７】
2011159306.tif 000009
【図８】
2011159306.tif 000010
【図９】
2011159306.tif 000011
【図１０】
2011159306.tif 000012
【図１１】
2011159306.tif 000013
【図１２】
2011159306.tif 000014
【図１３】
2011159306.tif 000015
【図１４】
2011159306.tif 000016
【図１５】
2011159306.tif 000017
【図１６】
2011159306.tif 000018
【図１７】
2011159306.tif 000019
【図１８】
2011159306.tif 000020
【図１９】
2011159306.tif 000021
【図２０】
2011159306.tif 000022
【図２１】
2011159306.tif 000023
【図２２】
2011159306.tif 000024
【図２３】
2011159306.tif 000025
【図２４】
2011159306.tif 000026
【図２５】
2011159306.tif 000027
【図２６】
2011159306.tif 000028
【図２７】
2011159306.tif 000029