(57)【特許請求の範囲】
【請求項１】
複数のスキャンラインを有する描画領域に図形を描画する画像描画装置であって、
処理対象の前記スキャンラインに描画される図形を判定し、判定した前記図形を構成する各頂点を抽出する描画位置判定手段と、
前記処理対象のスキャンラインについて、抽出された頂点の座標情報を含む頂点情報を、前記描画領域に描画される図形の頂点の頂点情報が記憶される頂点情報メモリから読み出す頂点情報読み出し手段と、
読み出した前記頂点情報に基づいて、前記処理対象のスキャンラインの画像データを生成する画像生成手段と、
前記画像生成手段によって生成された前記画像データを記憶するラインバッファと、を有し、
前記頂点情報読み出し手段は、
前記頂点情報を一時記憶するキャッシュメモリと、
前記描画領域に描画される図形の頂点全てについて、前記キャッシュメモリに前記頂点情報が記憶される場合は前記キャッシュメモリの前記頂点情報が記憶されたアドレスを、前記頂点情報が記憶されない場合は記憶されていないことを示すフラグをそれぞれ記憶するキャッシュタグと、
前記キャッシュタグを参照し、読み出し対象の頂点情報について前記アドレスが記憶されている場合は前記キャッシュメモリの当該アドレスから前記頂点情報を読み出し、記憶されていない場合は前記頂点情報メモリから読み出した頂点情報を前記キャッシュメモリに記憶させそのアドレスを前記キャッシュタグに記憶する制御手段と、を有する画像描画装置。
【請求項２】
請求項１について、
前記描画位置判定手段は、さらに、前記頂点について、当該頂点が構成する前記図形が描画される前記スキャンラインのうち、処理順が後の前記スキャンラインを示す最終使用ライン情報を抽出し、
前記制御手段は、さらに、前記最終使用ライン情報が前記処理対象のスキャンラインを示す頂点情報を上書き可能にする画像描画装置。
【請求項３】
請求項２について、
前記キャッシュタグは、さらに、前記アドレスに加えてキープフラグを記憶し、
前記制御手段は、前記最終使用ライン情報が前記処理対象のスキャンラインを示す頂点情報の前記キープフラグを非保持を示す値に制御し、前記キープフラグの値が非保持を示す頂点情報を上書き可能にする画像描画装置。
【請求項４】
複数のスキャンラインを有する描画領域に図形を描画する画像描画装置であって、
処理対象の前記スキャンラインに描画される図形を判定し、判定した前記図形を構成し一部の頂点が複数の図形によって共有される各頂点を抽出すると共に、当該頂点が構成する前記図形が描画される前記スキャンラインのうち、処理順が最終の前記スキャンラインを示す最終使用ライン情報を頂点毎に抽出する描画位置判定手段と、
前記処理対象のスキャンラインについて、抽出された頂点の座標情報を含む頂点情報を、前記描画領域に描画される図形の頂点の頂点情報が記憶される頂点情報メモリから読み出す頂点情報読み出し手段と、
読み出した前記頂点情報に基づいて、前記処理対象のスキャンラインの画像データを生成する画像生成手段と、
前記画像生成手段によって生成された前記画像データを記憶するラインバッファと、を有し、
前記頂点情報読み出し手段は、
前記頂点情報を一時記憶するキャッシュメモリと、
前記頂点情報メモリから読み出した頂点情報を前記キャッシュメモリに記憶させ、前記キャッシュメモリへ記憶した前記頂点情報を読み出し、読み出した前記頂点情報の前記最終使用ライン情報が前記処理対象のスキャンラインと一致する場合に前記頂点情報を上書き可能にする制御手段と、
を有する画像描画装置。
【請求項５】
請求項１乃至４のいずれかにおいて、
前記画像描画装置は、さらに、
前記ラインバッファに生成された前記画像データを表示させる表示手段と、を有する画像描画装置。
【請求項６】
複数のスキャンラインを有する描画領域における図形の描画処理をコンピューターに実行させるコンピューター読み取り可能な画像描画プログラムにおいて、
前記描画処理は、
処理対象の前記スキャンラインに描画される図形を判定し、判定した前記図形を構成する各頂点を抽出する描画位置判定工程と、
前記処理対象のスキャンラインについて、抽出された頂点の座標情報を含む頂点情報を、前記描画領域に描画される図形の頂点の頂点情報が記憶される頂点情報メモリから読み出す頂点情報読み出し工程と、
読み出した前記頂点情報に基づいて、前記処理対象のスキャンラインの画像データを生成してラインバッファに記憶する画像生成工程と、を有し、
前記頂点情報読み出し工程は、
前記頂点情報が一時記憶されるキャッシュメモリに対するキャッシュタグであって、前記描画領域に描画される図形の頂点全てについて、前記キャッシュメモリに前記頂点情報が記憶される場合は前記キャッシュメモリの当該頂点情報が記憶されたアドレスが、前記頂点情報が記憶されない場合は記憶されていないことを示すフラグがそれぞれ記憶される前記キャッシュタグを参照し、読み出し対象の頂点情報について前記アドレスが記憶されている場合は前記キャッシュメモリの当該アドレスから前記頂点情報を読み出し、記憶されていない場合は前記頂点情報メモリから読み出した頂点情報を前記キャッシュメモリに記憶させそのアドレスを前記キャッシュタグに記憶する制御工程と、
を有する画像描画プログラム。
【請求項７】
複数のスキャンラインを有する描画領域における図形の描画処理をコンピューターに実行させるコンピューター読み取り可能な画像描画プログラムにおいて、
前記描画処理は、
処理対象の前記スキャンラインに描画される図形を判定し、判定した前記図形を構成し一部の頂点が複数の図形によって共有される各頂点を抽出すると共に、当該頂点が構成する前記図形が描画される前記スキャンラインのうち、処理順が最終の前記スキャンラインを示す最終使用ライン情報を頂点毎に抽出する描画位置判定工程と、
前記処理対象のスキャンラインについて、抽出された頂点の座標情報を含む頂点情報を、前記描画領域に描画される図形の頂点の頂点情報が記憶される頂点情報メモリから読み出す頂点情報読み出し工程と、
読み出した前記頂点情報に基づいて、前記処理対象のスキャンラインの画像データを生成してラインバッファに記憶する画像生成工程と、を有し、
前記頂点情報読み出し工程は、
前記頂点情報メモリから読み出した頂点情報を、前記頂点情報が一時記憶される前記キャッシュメモリに記憶させ、前記キャッシュメモリへ記憶した前記頂点情報を読み出し、読み出した前記頂点情報の前記最終使用ライン情報が前記処理対象のスキャンラインと一致する場合に前記頂点情報を上書き可能にする制御工程と、
を有する画像描画プログラム。
【請求項８】
複数のスキャンラインを有する描画領域に図形を描画する画像描画方法であって、
処理対象の前記スキャンラインに描画される図形を判定し、判定した前記図形を構成する各頂点を抽出する描画位置判定工程と、
前記処理対象のスキャンラインについて、抽出された頂点の座標情報を含む頂点情報を、前記描画領域に描画される図形の頂点の頂点情報が記憶される頂点情報メモリから読み出す頂点情報読み出し工程と、
読み出した前記頂点情報に基づいて、前記処理対象のスキャンラインの画像データを生成してラインバッファに記憶する画像生成工程と、を有し、
前記頂点情報読み出し工程は、
前記頂点情報が一時記憶されるキャッシュメモリに対するキャッシュタグであって、前記描画領域に描画される図形の頂点全てについて、前記キャッシュメモリに前記頂点情報が記憶される場合は前記キャッシュメモリの当該頂点情報が記憶されたアドレスが、前記頂点情報が記憶されない場合は記憶されていないことを示すフラグがそれぞれ記憶される前記キャッシュタグを参照し、読み出し対象の頂点情報について前記アドレスが記憶されている場合は前記キャッシュメモリの当該アドレスから前記頂点情報を読み出し、記憶されていない場合は前記頂点情報メモリから読み出した頂点情報を前記キャッシュメモリに記憶させそのアドレスを前記キャッシュタグに記憶する制御工程と、
を有する画像描画方法。
【請求項９】
複数のスキャンラインを有する描画領域に図形を描画する画像描画方法であって、
処理対象の前記スキャンラインに描画される図形を判定し、判定した前記図形を構成し一部の頂点が複数の図形によって共有される各頂点を抽出すると共に、当該頂点が構成する前記図形が描画される前記スキャンラインのうち、処理順が最終の前記スキャンラインを示す最終使用ライン情報を頂点毎に抽出する描画位置判定工程と、
前記処理対象のスキャンラインについて、抽出された頂点の座標情報を含む頂点情報を、前記描画領域に描画される図形の頂点の頂点情報が記憶される頂点情報メモリから読み出す頂点情報読み出し工程と、
読み出した前記頂点情報に基づいて、前記処理対象のスキャンラインの画像データを生成してラインバッファに記憶する画像生成工程と、を有し、
前記頂点情報読み出し工程は、
前記頂点情報メモリから読み出した頂点情報を、前記頂点情報が一時記憶される前記キャッシュメモリに記憶させ、前記キャッシュメモリへ記憶した前記頂点情報を読み出し、読み出した前記頂点情報の前記最終使用ライン情報が前記処理対象のスキャンラインと一致する場合に前記頂点情報を上書き可能にする制御工程と、
を有する画像描画方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像描画装置、画像描画プログラム、及び、画像描画方法に関する。
【背景技術】
【０００２】
３次元画像等を描画する画像描画装置は、例えば、図形の頂点情報に基づいて、２次元表示面上の図形情報を生成する（例えば、特許文献１−４参照。）。そして、描画装置は、生成した図形情報に基づいて、２次元表示面に表示する画像を生成する。例えば、画像描画装置は、画素の色を記憶するフレームバッファと、画素の奥行き（Ｚ値）を記憶するデプスバッファとを有している。
【０００３】
一般的な画像描画装置では、フレームバッファおよびデプスバッファは、表示面の画素数分のメモリサイズを必要とする。例えば、表示面が８００×６００画素で、１画素あたりのデータサイズ（色および奥行きの合計値）が８ｂｙｔｅであるとき、フレームバッファおよびデプスバッファは、合計で約３．７ＭＢのメモリサイズを必要とする。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平１１−３１２３６号公報
【特許文献２】特開平１０−２２２６９５号公報
【特許文献３】特開平９−１８００００号公報
【特許文献４】特開２０００−３００８１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
表示面の画素数分のデータを記憶するには、メモリサイズの大きなバッファ（フレームバッファおよびデプスバッファ）が必要である。例えば、メモリサイズの大きなフレームバッファ等を描画装置内にＳＲＡＭで形成したときには、回路面積およびコストが大幅に増加する。また、メモリサイズの大きなフレームバッファ等を描画装置の外部にＤＲＡＭで形成したときには、外部のＤＲＡＭに対するデータの入出力による消費電力の増加およびＤＲＡＭを別チップとして実装することによるコストの増加等の問題がある。
【０００６】
そこで、本発明では、画素のデータを記憶するバッファのメモリサイズを抑える画像描画装置、画像描画プログラム、及び、画像描画方法を提供する。
【課題を解決するための手段】
【０００７】
第１の側面は、複数のスキャンラインを有する描画領域に図形を描画する画像描画装置であって、処理対象の前記スキャンラインに描画される図形を判定し、判定した前記図形を構成する各頂点を抽出する描画位置判定手段と、前記処理対象のスキャンラインについて、抽出された頂点の座標情報を含む頂点情報を、前記描画領域に描画される図形の頂点の頂点情報が記憶される頂点情報メモリから読み出す頂点情報読み出し手段と、読み出した前記頂点情報に基づいて、前記処理対象のスキャンラインの画像データを生成する画像生成手段と、前記画像生成手段によって生成された前記画像データを記憶するラインバッファと、を有し、前記頂点情報読み出し手段は、前記頂点情報を一時記憶するキャッシュメモリと、前記描画領域に描画される図形の頂点全てについて、前記キャッシュメモリに前記頂点情報が記憶される場合に前記頂点情報が記憶されたアドレスを記憶するキャッシュタグと、前記キャッシュタグを参照し、読み出し対象の頂点情報について前記アドレスが記憶されている場合は前記キャッシュメモリの当該アドレスから前記頂点情報を読み出し、記憶されていない場合は前記頂点情報メモリから読み出した頂点情報を前記キャッシュメモリに記憶させそのアドレスを前記キャッシュタグに記憶する制御手段と、を有する。
【発明の効果】
【０００８】
第１の側面によれば、画素のデータを記憶するバッファのメモリサイズを抑えることができる。
【図面の簡単な説明】
【０００９】
【図１】本実施の形態例における画像表示装置の構成を表す例図である。
【図２】本実施形態における画像描画装置の一例を示す図である。
【図３】本実施の形態例におけるキャッシュタグの一例を表す図である。
【図４】本実施の形態例における画像描画装置の具体的な処理を表す図である。
【図５】２次元表示面に描画される図形の具体例の一例を表す図である。
【図６】図５の具体例に基づく最終使用ライン情報の一例を表す図である。
【図７】描画命令再構築部によって再構築された描画命令を表す例図である。
【図８】本実施の形態例における頂点情報キャッシュ部の構成を表す例図である。
【図９】図８の頂点情報キャッシュ部の処理を説明するフローチャート図である。
【図１０】図９のフローチャート図におけるアドレス決定処理（Ｓ１５）の詳細を説明するフローチャート図である。
【図１１】第１の実施の形態例におけるキャッシュタグの遷移の一例を表す図である。
【図１２】第２の実施の形態例におけるキャッシュタグ及びキャッシュメモリの状態の一例を表す図である。
【発明を実施するための形態】
【００１０】
以下、図面にしたがって本発明の実施の形態について説明する。ただし、本発明の技術的範囲はこれらの実施の形態に限定されず、特許請求の範囲に記載された事項とその均等物まで及ぶものである。
【００１１】
＜第１の実施の形態例＞
図１は、本実施の形態例における画像表示装置の構成を表す例図である。同図の画像表示装置は、例えば、バス１８を介して互いに接続された、グラフィックスコア１００、表示ユニット１１、外部入出力部１３、ビデオキャプチャ１４、ＣＰＵ１６、外部メモリ１８にアクセスする外部メモリ入出力部１７を有する。グラフィックスコア１００は、描画命令に基づいて画像データを生成し、表示ユニット１１を介して外部表示装置１２に表示させる。グラフィックスコア１００は、本実施の形態例における画像描画装置の一例を示す。
【００１２】
図２は、本実施形態における画像描画装置１００の一例を示す図である。画像描画装置１０は、例えば、３次元画像等を２次元表示面ＤＩＳに表示させる。同図の右図の２次元表示面ＤＩＳのように、画像描画装置１００は、例えば、２次元表示面ＤＩＳをＹ方向に分割したスキャンラインＹ０〜Ｙ１０毎に、画像データＧＤＡＴＡを生成する。なお、同図では、２次元表示面ＤＩＳをＹ方向に１１個に区分した各領域をスキャンラインとしているが、Ｘ方向に区分した領域であってもよいし、この例の区分数に限定されるものではない。
【００１３】
本実施の形態例における画像描画装置１００は、例えば、描画位置判定部１０、頂点読み出し部２０、画像生成部３０、ラインバッファ４００、表示回路５００を有する。ここで、画像描画装置１００の処理の概要を簡単に説明する。ラインバッファ４００は、スキャンラインの画像データＧＤＡＴＡを格納するバッファである。
【００１４】
描画位置判定部１０は、例えば、図形の描画命令と頂点情報とを受けて、２次元表示面ＤＩＳに描画される図形の描画位置を判定し、各スキャンラインについて、当該スキャンラインに描画される図形を構成する各頂点の頂点番号を抽出する。具体的に、描画位置判定部１０は、図形の各頂点の頂点情報に基づいて表示領域外の図形を除去し、描画対象の図形について所定方向（例えば、Ｙ方向）の描画範囲を算出する。例えば、描画位置判定部１０は、図形の頂点のうち、最小のＹ座標および最大のＹ座標をＹ方向の描画範囲として算出する。そして、描画位置判定部１０は、算出した図形のＹ方向の描画範囲をＹ座標領域に含むスキャンライン（描画スキャンライン範囲）を判定する。
【００１５】
続いて、描画位置判定部１０は、図形の描画命令ＶＣとその描画スキャンライン範囲を描画命令バッファ２１０に出力する。そして、描画位置判定部１０は、スキャンラインが選択されたときに、描画命令バッファ２１０に記憶された各図形とその描画スキャンライン範囲に基づいて、対象のスキャンラインに描画される図形を判定し、当該図形を構成する頂点情報を抽出する。
【００１６】
なお、頂点番号は、ユーザーまたは装置によって付与される番号であり、頂点が特定される固有の番号である。また、頂点番号は、番号に限定されるものではなく、頂点を識別可能な頂点識別情報、頂点ＩＤ等であってもよい。なお、本実施の形態例において、図形は三角形を示すが、三角形に限定されるものではない。
【００１７】
例えば、図２の２次元表示面ＤＩＳにおいて、例えば、描画位置判定部１０は、図形ＺＡを構成する頂点Ｐａ、Ｐｂ、Ｐｃのうち、最大のＹ座標である頂点ＰａのＹ座標、最小のＹ座標である頂点ＰｂのＹ座標を算出する。そして、描画位置判定部１０は、頂点ＰａのＹ座標と頂点ＰｂのＹ座標の範囲内にＹ座標領域を有するスキャンラインＹ１〜Ｙ６を判定する。これにより、スキャンラインＹ１〜Ｙ６に図形ＺＡが描画されることが判明する。図形ＺＢについても同様にして、描画対象のスキャンラインＹ１〜Ｙ４が検知される。図形ＺＡ、ＺＢの描画スキャンライン範囲は、描画命令ＶＣと共に、命令バッファ２１０に出力される。
【００１８】
そして、スキャンラインＹ１が選択されたときに、描画命令バッファ２１０に記憶された情報に基づいて、スキャンラインＹ１に図形ＺＡ、ＺＢが描画されることが検知される。これにより、スキャンラインＹ１について、図形ＺＡを構成する各頂点Ｐａ、Ｐｂ、Ｐｃの頂点番号と、図形ＺＢを構成する各頂点Ｐａ、Ｐｃ、Ｐｄの頂点番号とが抽出される。他のスキャンラインについても同様に、描画位置判定部１０によって頂点番号が抽出される。
【００１９】
続いて、頂点読み出し部２０は、処理対象のスキャンラインについて、抽出された頂点番号の頂点情報を頂点情報メモリ（外部メモリ１８）から読み出す。頂点情報は、例えば、頂点の座標情報と色情報とを含む。また、一般的に、頂点情報はデータ量が大きいことにより、外部メモリ１８等のメモリに格納される。そして、画像生成部３０は、外部メモリから読み出された頂点情報に基づいて図形の画像データＧＤＡＴＡを生成し、ラインバッファ４００に格納する。そして、処理対象のスキャンラインについて、当該スキャンラインに描画される全ての図形の画像データＧＤＡＴＡが生成され、ラインバッファ４００に格納されると、表示回路５００によって表示される。
【００２０】
図２の２次元表示面ＤＩＳの例によると、例えば、頂点読み出し部２０は、図形ＺＡの頂点Ｐａ、Ｐｂ、Ｐｃの頂点情報を外部メモリから読み出し、画像生成部３０は、読み出した頂点情報に基づいて図形ＺＡの画像データＧＤＡＴＡを生成し、スキャンラインＹ１のラインバッファ４００に格納する。図形ＺＢについても同様にして画像データＧＤＡＴＡが生成され、ラインバッファ４００に格納される。そして、スキャンラインＹ１のラインバッファ４００の画像データが表示回路５００によって表示される。
【００２１】
このように、本実施の形態例における画像描画装置１００は、２次元表示面ＤＩＳを分割したスキャンライン毎に、当該スキャンラインに描画される図形の頂点番号を抽出し、スキャンライン毎に画像データＧＤＡＴＡを生成する。このため、本実施の形態例における画像描画装置１００は、ラインバッファ４００のメモリサイズを、スキャンライン１つ分の画像データ量と同じサイズまで小さくできる。つまり、画像描画装置１００は、２次元表示面ＤＩＳの全体の画像データを生成してフレームバッファに格納する場合に対して、画像データＧＤＡＴＡを格納するバッファのメモリサイズを小さくできる。
【００２２】
ところで、スキャンライン毎に画像データＧＤＡＴＡを生成する画像描画装置１００では、図形単位ではなくスキャンライン単位に画像データＧＤＡＴＡを生成する。そのため、ある図形が描画される全てのスキャンラインの描画処理において、当該図形を構成する頂点の頂点情報が毎回、読み出される。図形がＸ個のスキャンラインに渡って描画される場合、同一の頂点情報が、Ｘ回、外部メモリから読み出される。即ち、図形単位に画像データを生成する場合、図形を構成する各頂点の頂点情報の読み出し回数は１回であるのに対し、スキャンライン毎に画像データを生成する場合、読み出し回数は、描画されるスキャンラインの数となる。
【００２３】
例えば、図２の例において、頂点Ｐａの頂点情報は、頂点Ｐａが構成する図形ＺＡがスキャンラインＹ１〜Ｙ６に描画されることから、スキャンラインＹ１〜Ｙ６の描画処理の毎に、つまり６回、読み出される。このように、スキャンライン毎に画像データＧＤＡＴＡを生成する画像描画装置１００では、画像データＧＤＡＴＡを格納するバッファのメモリサイズを小さくできる一方で、外部メモリ１８に格納される頂点情報の読み出し処理回数が増大し、効率的でない。
【００２４】
そこで、本実施の形態例における画像描画装置１００の頂点読み出し部２０は、キャッシュメモリを有し、頂点情報を一時的に格納する。これにより、読み出し対象の頂点情報がキャッシュメモリに格納されている間は、当該頂点情報を外部メモリ１８から読み出す必要がないため、外部メモリへ１８のアクセス回数が抑制され、処理が効率化される。このようなキャッシュメモリは、一般的に、キャッシュタグを介して制御される。
【００２５】
そして、本実施の形態例におけるキャッシュタグは、キャッシュメモリの各アドレスに対応してではなく、描画対象の図形の頂点全てに対応してキャッシュメモリのアドレスを有する。つまり、本実施の形態例におけるキャッシュタグは、キャッシュメモリの各アドレスに対応して当該アドレスに格納される頂点情報の頂点番号（頂点ＩＤ等）を記憶するのではなく、各頂点に対応して頂点情報がキャッシュメモリに記憶されている場合にそのアドレス情報を記憶する。
【００２６】
このため、頂点読み出し部２０は、キャッシュタグから頂点番号を検索することによってキャッシュヒット／ミスの判定を行う必要がなくなる。本実施の形態例におけるキャッシュタグには、読み出し対象の頂点情報について、キャッシュヒット／ミスを示すアドレス情報が常に記憶される。このため、頂点読み出し部２０は、キャッシュタグにおける対象の頂点情報に係るアドレス情報を、例えば、頂点番号や頂点ＩＤ等に基づいて直接参照することで、キャッシュヒット／ミスの判定を効率的に行うことができる。
【００２７】
このように、頂点読み出し部２０は、キャッシュタグを検索する必要がなく、キャッシュタグにおける対象の頂点情報に係るアドレス情報を直接参照することで、キャッシュヒット／ミスの判定を高速に行うことができる。また、頂点読み出し部２０は、キャッシュヒットの場合、同時に、対象の頂点情報が格納されるキャッシュメモリのアドレス情報を取得することができる。
【００２８】
一般的に、画像描画装置１００において一連の処理対象となる頂点総数は想定可能であり、キャッシュタグが各頂点に対応して情報を有する場合でも、そのデータ容量は想定範囲内に抑えられる。そのため、本実施の形態例のように、各頂点に対応する頂点番号をインデックスとするキャッシュタグを用いることができる。それに対して、プロセッサ等のキャッシュメモリは多量の情報を対象とするため、各情報をインデックスとするとキャッシュタグのデータ容量が肥大化してしまう。このため、本実施の形態例のように、画像処理に係る頂点情報を格納するキャッシュメモリのキャッシュタグについては、頂点番号をインデックスとすることが可能となる。
【００２９】
図３は、本実施の形態例におけるキャッシュタグＣＴ１の一例を表す図である。同図のように、キャッシュタグＣＴ１は、２次元表示面ＤＩＳに描画される図形の頂点全てについてそれぞれ情報を有する（逆引きキャッシュタグ）。
【００３０】
図３の例において、例えば、頂点番号０に基づいてキャッシュタグＣＴ１が参照されると、アドレス７番地が取得され、キャッシュヒットと判定される。キャッシュメモリＣＭ１のアドレス７番地には、頂点番号０の頂点情報が格納されている。一方、頂点番号１に基づいてキャッシュタグＣＴ１が参照されると、有効なアドレスが格納されていないことにより、キャッシュミスと判定される。このように、本実施の形態例におけるキャッシュタグＣＴ１によると、対象の頂点番号があるか否かが検索される必要なく、頂点番号に基づいて高速にキャッシュヒット／ミスが判定される。
【００３１】
図２の処理に戻り、また、描画位置判定部１０は、各頂点について、当該頂点が構成する図形が描画されるスキャンラインのうち、処理順が後のスキャンラインを示す最終使用ライン情報を頂点番号に対応して抽出する。例えば、図２に例において、頂点Ｐａの最終使用ラインは、頂点Ｐａが構成する図形ＺＡ、ＺＢが描画されるスキャンラインＹ１〜Ｙ６のうち、処理順が後のスキャンラインＹ６となる。最終使用ライン情報は、頂点読み出し部２０におけるキャッシュメモリの制御処理で用いられる。
【００３２】
具体的に、頂点読み出し部２０は、キャッシュメモリＣＭから削除する対象の頂点情報の判定時に、対象の頂点番号の最終使用ラインが処理対象のスキャンラインと一致する場合に、対応する頂点情報を削除対象とする。これは、対象の頂点番号の最終使用ラインが処理対象のスキャンラインと一致する場合、以降に処理されるスキャンラインにおいて、対象の頂点番号の頂点情報は使用されないことに因る。使用されない頂点情報はキャッシュメモリＣＭに保持されている必要がないため、削除対象とされる。
【００３３】
この結果、キャッシュメモリＣＭには、次回以降に処理対象となるスキャンラインで確実に読み出される頂点情報だけが保持される。これにより、キャッシュメモリＣＭのキャッシュヒット率が向上し、外部メモリへの読み出し処理の回数が抑制される。
【００３４】
続いて、図２で概要を述べた画像描画装置１００の各処理部の処理について、より具体的に説明する。
【００３５】
図４は、本実施の形態例における画像描画装置１００のより詳細な処理を説明する図である。同図において、図２と同じ処理部は、同じ引用番号が付加される。描画位置判定部１０は、例えば、図形の描画命令ＶＣと頂点情報ＶＩＮＦとに基づいて、ジオメトリ処理の一部を実施する。描画位置判定部１０は、例えば、頂点読み出し部１１０、頂点処理部１２０、図形作成部１３０、図形除去部１４０、描画領域判定部１５０および描画命令再構築部１６０を有する。
【００３６】
描画位置判定部１０は、例えば、頂点情報ＶＩＮＦのうち図形の座標情報ＶＩＮＦｃを読み出し、２次元表示面ＤＩＳの各スキャンラインに描画される図形を判定し、各スキャンラインに描画される図形を構成する各頂点の頂点番号を抽出する。頂点情報ＶＩＮＦは、例えば、図形の各頂点の３次元座標の情報（以下、座標情報と称する）、各頂点の色の情報、テクスチャ座標の情報および法線ベクトルの情報等を有している。なお、座標情報ＶＩＮＦｃは、例えば、２次元座標の情報でもよいし、図形の座標情報のみでもよい。
【００３７】
具体的に、頂点読み出し部１１０は、例えば、頂点情報ＶＩＮＦが格納されているメモリ（頂点情報メモリ）等から座標情報ＶＩＮＦｃを読み出し、読み出した座標情報ＶＩＮＦｃを頂点処理部１２０に出力する。頂点処理部１２０は、座標情報ＶＩＮＦｃに基づいて、回転等の座標に関する頂点処理を実施する。続いて、図形作成部１３０は、頂点処理部１２０による頂点処理の結果を、図形の情報に変換する。この例において、図形作成部１３０は、各図形について、３つの頂点（三角形の頂点）の情報を頂点処理の結果として受け、頂点処理の結果を三角形の情報に変換する。これにより、座標情報ＶＩＮＦｃに対応する図形の図形情報が生成される。
【００３８】
図形除去部１４０は、図形作成部１３０により生成された図形情報のうち、２次元表示面ＤＩＳに描画されない図形の図形情報を除去する。例えば、図形除去部１４０は、クリッピング処理やカリング処理を実施し、不要な図形情報を除去する。例えば、クリッピング処理では、図形除去部１４０は、表示領域外の図形を除去する。また、例えば、カリング処理では、図形除去部１４０は、図形の表裏判定を実施し、裏と判定した図形を除去する。なお、図形の裏を表示する設定のときには、図形除去部１４０は、例えば、裏であることを示すフラグ等の表裏情報を図形情報に追加する。
【００３９】
そして、図形除去部１４０は、２次元表示面ＤＩＳに描画される図形の図形情報を描画領域判定部１５０に出力する。図形情報は、例えば、図形の頂点番号、図形の２次元表示面ＤＩＳにおける座標を示す位置情報および図形の表裏情報を有している。
【００４０】
描画領域判定部１５０は、図形情報に基づいて、図形のＹ方向の描画範囲を算出する。例えば、描画領域判定部１５０は、図形を構成する各頂点の位置するＹ座標のうち、最小のＹ座標および最大のＹ座標をＹ方向の描画範囲として算出する。そして、描画領域判定部１５０は、算出した図形のＹ座標の描画範囲に基づいて、当該描画範囲をＹ座標領域に含むスキャンラインを判定することで、図形が描画されるスキャンラインを判定する。そして、描画領域判定部１５０は、図形の描画命令ＶＣとその描画スキャンライン範囲を描画命令バッファ２１０に出力する。
【００４１】
また、描画領域判定部１５０は、各頂点について、描画スキャンライン範囲に基づいて、最終使用ライン情報ＥＬを抽出する。具体的に、描画領域判定部１５０は、頂点が構成する図形の描画スキャンライン範囲のうち、処理順が最も後のスキャンラインを示す番号を最終使用ライン情報ＥＬとして抽出する。
【００４２】
ここで、描画領域判定部１５０の処理を具体例に基づいて説明する。
【００４３】
図５は、２次元表示面ＤＩＳに描画される図形の具体例の一例を表す図である。同図の２次元表示面ＤＩＳはスキャンラインＹ０〜Ｙ２１に区分される。同図において、２次元表示面ＤＩＳには４つの図形Ｚ０〜Ｚ３が描画される。図形Ｚ０を構成する頂点は頂点ｐ０、ｐ１、ｐ２であり、図形Ｚ１を構成する頂点は頂点ｐ０、ｐ２、ｐ３である。同様に、図形Ｚ２を構成する頂点は頂点ｐ０、ｐ３、ｐ４、図形Ｚ３を構成する頂点は頂点ｐ２、ｐ３、ｐ５である。この例において、それぞれの頂点ｐ０〜ｐ５に対応する頂点番号は０〜５である。
【００４４】
図５の例において、描画領域判定部１５０は、頂点ｐ０について、頂点ｐ０が構成する各図形Ｚ０〜Ｚ２のＹ座標の描画範囲を算出する。図形Ｚ０について、図形Ｚ０を構成する頂点ｐ０〜０２の位置するＹ座標（Ｙ１、Ｙ５、Ｙ１１）のうち、最小のＹ座標はＹ１であり、最大のＹ座標はＹ１１である。従って、図形Ｚ０のＹ座標の描画範囲としてＹ１〜Ｙ１１が算出される。同様にして、図形Ｚ１のＹ座標の描画範囲としてＹ１〜Ｙ１６、図形Ｚ２のＹ座標の描画範囲としてＹ１〜Ｙ１６、図形Ｚ３のＹ座標の描画範囲としてＹ１１〜Ｙ１９が算出される。
【００４５】
図６は、図５の具体例に基づく最終使用ライン情報ＥＬの一例を表す図である。前述したとおり、最終使用ライン情報ＥＬは、各頂点について、当該頂点が構成する図形が描画されるスキャンラインのうち、最も後に処理されるスキャンライン番号を有する。なお、本実施の形態例において、スキャンラインＹ０からスキャンラインＹ２１に順に処理が行われる。
【００４６】
例えば、頂点番号０について説明する。図５の具体例において、頂点番号０の頂点ｐ０が構成する図形Ｚ０〜Ｚ２のＹ座標の描画範囲は、それぞれＺ０（Ｙ１〜Ｙ１１）、Ｚ１（Ｙ１〜Ｙ１６）、Ｚ２（Ｙ１〜Ｙ１６）である。図形Ｚ０〜Ｚ２が描画されるスキャンラインＹ１〜Ｙ１６のうち、最も後に処理されるのはスキャンラインＹ１６である。従って、頂点ｐ０の最終使用ラインはＹ１６となる。同様にして、頂点番号１の頂点ｐ１の最終使用ラインもＹ１６となる。他の頂点についても同様にして、最終使用ラインが抽出される。
【００４７】
このようにして、描画領域判定部１５０の処理が行われ、図形の描画命令ＶＣとそのＹ座標の描画範囲、及び、最終使用ライン情報ＥＬが生成される。続いて、図４の処理の説明に戻り、描画命令再構築部１６０は、描画命令バッファ２１０に格納された図形の描画命令ＶＣとそのＹ座標の描画範囲を、スキャンラインに基づいて再構築する。具体的に、描画命令再構築部１６０は、図形の描画命令ＶＣを、スキャンライン単位に、当該スキャンラインに描画される図形の描画命令ＶＣが配置されるように再構築し、描画命令バッファ２２０に格納する。これにより、各スキャンラインについて、当該スキャンラインに描画される図形の描画命令ＶＣを有する情報が生成される。図形の描画命令ＶＣは各頂点の頂点番号が含まれるため、スキャンライン単位で当該スキャンラインに描画される図形の頂点番号が抽出されることになる。
【００４８】
図７は、描画命令再構築部１６０によって再構築された描画命令情報ＣＬ２を表す例図である。同図において、左図は再構築前、右図は再構築後の描画命令情報ＣＬ１、ＣＬ２を示す。同図の例では、描画命令情報に、図形の描画命令ＶＣに加え、描画設定情報が含まれる。左図の再構築前の描画命令情報ＣＬ１では、例えば、入力順に描画設定情報、図形の描画命令ＶＣとその描画範囲が配置される。それに対し、右図の再構築後の描画命令情報ＣＬ２では、スキャンライン単位に、当該スキャンラインにおける描画設定情報と、描画対象の図形の描画命令ＶＣが配置される。
【００４９】
具体的に、例えば、スキャンラインＹ１には図形Ｚ０〜図形Ｚ２が描画される。従って、図７の再構築後の描画命令情報ＣＬ２において、スキャンラインＹ１について、描画設定情報Ｘ、Ｙと図形Ｚ０〜図形Ｚ２の描画命令ＶＣとが対応するように配置される。これにより、スキャンラインＹ１に描画される図形の頂点番号が抽出される。同様にして、例えば、スキャンラインＹ１２には図形Ｚ１〜図形Ｚ３が描画される。従って、再構築後の情報において、スキャンラインＹ１２について、描画設情報定Ｘ、Ｙ、Ｚと図形Ｚ１〜図形Ｚ３の描画命令とが対応するように配置される。他のスキャンラインも同様である。
【００５０】
このように、描画位置判定部１０は、少なくとも座標情報を有する頂点情報ＶＩＮＦと描画命令ＶＣとに基づいて図形の描画範囲を判定し、各頂点について当該頂点が構成する図形が描画されるスキャンライン範囲を抽出する。これにより、スキャンライン毎に、当該スキャンラインに描画される図形を構成する頂点の頂点番号（描画命令ＶＣ）が抽出される。また、描画位置判定部１０は、各頂点について、当該頂点が構成する図形が描画されるスキャンライン範囲のうち、最も後に処理されるスキャンラインの番号を最終使用ライン情報ＥＬとして抽出する。
【００５１】
図４の処理の説明に戻り、続いて、頂点読み出し部２０は、処理対象のスキャンラインについて描画位置判定部１０によって抽出された描画命令ＶＣに基づいて、当該描画命令ＶＣが有する頂点番号の頂点情報ＶＩＮＦを読み出す。頂点読み出し部２０は、例えば、頂点情報読み出し部３１０、頂点情報キャッシュ部６１０、頂点処理部３２０、図形作成部３３０を有する。
【００５２】
具体的に、頂点情報読み出し部３１０は、処理対象のスキャンラインについて、描画位置判定部１０から当該スキャンラインに描画される図形の描画命令ＶＣを取得する。そして、頂点情報読み出し部３１０は、描画命令ＶＣが有する頂点番号に対応する頂点情報ＶＩＮＦを外部メモリである頂点情報メモリから読み出す。ただし、頂点番号に対応する頂点情報ＶＩＮＦがキャッシュメモリに格納されている場合、頂点情報ＶＩＮＦはキャッシュメモリから読み出される。
【００５３】
この外部メモリまたはキャッシュメモリからの頂点情報ＶＩＮＦの読み出し処理（頂点情報キャッシュ部６１０の処理）の詳細については、フローチャート図に基づいて後で説明する。先に、図４の処理について一通り説明する。
【００５４】
本実施の形態例において、キャッシュメモリには、頂点情報読み出し部３１０の後続の頂点処理部３２０による頂点処理が実施された頂点情報ＶＩＮＦが格納される。そのため、頂点情報読み出し部３１０は、対象の頂点情報ＶＩＮＦを外部メモリから読み出すと、頂点情報キャッシュ部６１０から出力されたキャッシュメモリの空きアドレスと共に、頂点処理部３２０に出力して頂点処理を行わせる。そして、図形作成部３３０は、頂点処理後の頂点情報ＶＩＮＦをキャッシュメモリの空きアドレスに格納すると共に、さらに図形情報への変換処理を行って画像生成部３０に出力する。
【００５５】
一方、対象の頂点情報ＶＩＮＦがキャッシュメモリから読み出される場合、頂点情報読み出し部３１０は、頂点情報キャッシュ部６１０から出力されたキャッシュメモリの読み出しアドレスを、頂点処理部３２０を経て図形作成部３３０に出力する。そして、図形作成部３３０は、キャッシュメモリの読み出しアドレスから頂点情報ＶＩＮＦを読み出し、図形情報への変換処理を行って画像生成部３０に出力する。
【００５６】
具体的に、頂点処理部３２０は、頂点情報ＶＩＮＦに基づいて頂点処理を実施する。頂点処理部３２０により実施される頂点処理には、例えば、回転等の座標に関する処理、ライティング、各頂点の色の計算、テクスチャ座標の計算および各頂点の法線ベクトルの計算等が含まれる。頂点処理が行われた頂点情報ＶＩＮＦは、空きアドレスと共に図形作成部３３０に入力される。
【００５７】
また、図形作成部３３０は、キャッシュメモリにおける頂点情報ＶＩＮＦの書き込み、読み出し処理を行うと共に、頂点情報ＶＩＮＦを図形の頂点情報ＶＩＮＦに変換して画像生成部３０に出力する。この例において、図形作成部３３０は、３つの頂点（三角形の頂点）の情報を頂点処理の結果として受け、三角形の図形情報に変換する。変換された頂点情報ＶＩＮＦは、例えば、図形の位置情報（２次元表示面ＤＩＳにおける座標）、図形の各辺の式の情報、色の情報、テクスチャ座標の情報、法線ベクトルの情報およびＺ方向の情報（奥行きの情報）等を有する。
【００５８】
続いて、画像生成部３０の処理について説明する。画像生成部３０は、例えば、図形作成部３３０から取得した図形の各頂点情報ＶＩＮＦに基づいて、ジオメトリ処理およびレンダリング処理を実施する。画像生成部３０は、例えば、画素生成部３４０、画素処理部３５０および画素除去部３６０を有する。
【００５９】
具体的に、画素生成部３４０は、図形作成部３３０から取得した図形の各頂点情報ＶＩＮＦに基づいて、画素情報を生成する。そして、画素生成部３４０は、画素情報を画素処理部３５０に出力する。画素処理部３５０は、画素生成部３４０から受けた画素情報及びテクスチャユニット３４５のテクスチャ情報に基づいて、色の計算やテクスチャ座標の計算等を画素単位で実施する。例えば、画素処理部３５０等は、スキャンラインの画素情報を生成する際に、処理対象のスキャンラインに係る設定情報等を参照する。設定情報は、例えば、図形の変換行列、反射率等の素材情報および光源の位置情報等である。
【００６０】
画素除去部３６０は、画素処理部３５０により処理された画素情報のうち、２次元表示面ＤＩＳに描画されない画素情報を除去する。ラインデプスバッファ４１０は、例えば、画素の奥行き（Ｚ値）を格納する。画素除去部３６０は、例えば、ラインデプスバッファ４１０に格納されているＺ値（画素の奥行き）に基づいてＺテストを実施し、不要な画素情報を除去する。なお、除去されずに残った画素情報は、描画対象のスキャンラインの画像データＧＤＡＴＡに対応する。画素除去部３６０は、スキャンラインの画像データＧＤＡＴＡをラインバッファ４００に格納する。
【００６１】
このようにして、処理対象のスキャンラインの画像データＧＤＡＴＡが生成され、表示回路５００を介して、図１の表示ユニット１１等に出力される。
【００６２】
ここで、前述した図４の頂点情報読み出し部３１０における外部メモリまたはキャッシュメモリからの頂点情報ＶＩＮＦの読み出し処理（頂点情報キャッシュ部６１０の処理）の詳細について説明する。頂点情報読み出し部３１０は、読み出し対象の頂点番号ＶＮ及びスキャンラインの開始情報ＳＳを頂点情報キャッシュ部６１０に出力する。
【００６３】
図８は、本実施の形態例における頂点情報キャッシュ部６１０の構成を表す例図である。頂点情報キャッシュ部６１０は、制御部６０６、キャッシュタグＣＴ、キャッシュメモリＣＭ、最終使用ライン情報バッファ６０１、アドレスＦＩＦＯ（Ｆｉｒｓｔ Ｉｎ Ｆｉｒｓｔ Ｏｕｔ）６０３、カウンタ６０４、セレクタ回路６０２を有する。
【００６４】
図８の制御部６０６は、最終使用ライン情報バッファ６０１の最終使用ライン情報ＥＬ、及び、アドレスＦＩＦＯ６０３またはカウンタ６０４から出力されるアドレス情報ａｄに基づいて、キャッシュタグＣＴにおける各種フラグ及びアドレス情報ａｄの制御処理を行う。また、制御部６０６は、頂点情報読み出し部３１０から処理対象のスキャンラインの開始情報ＳＳ及び頂点番号ＶＮを取得すると共に、頂点情報読み出し部３１０にキャッシュメモリＣＭの読み出しアドレスａｄ及び書き込み先アドレスａｄを出力する。また、キャッシュメモリＣＭは、図形作成部３３０から入力される読み出しアドレスａｄ及び書き込みアドレスａｄに基づいて、頂点情報ＶＩＮＦが入出力される。
【００６５】
キャッシュタグＣＴは、図３で前述したとおり、２次元表示面ＤＩＳに描画される図形の頂点全てについて、例えば、頂点番号に対応して、当該頂点番号に対応する頂点情報ＶＩＮＦがキャッシュメモリＣＭに格納される場合に、そのキャッシュメモリＣＭのアドレス情報を格納する。また、本実施の形態例のキャッシュタグＣＴは、図３に示すように、キャッシュメモリＣＭのアドレスに加えて、Ｅｍｐｔｙフラグ及びＫｅｅｐフラグを有する。Ｅｍｐｔｙフラグの値は、対応する頂点番号の頂点情報ＶＩＮＦがキャッシュメモリＣＭに格納されているか否かを示し（格納されていない場合、Ｔｒｕｅ）、Ｋｅｅｐフラグの値は、頂点情報ＶＩＮＦがキャッシュメモリＣＭに格納されている場合に、頂点情報ＶＩＮＦをキャッシュメモリＣＭに保持しておくか否かを示す（保持する場合、Ｔｒｕｅ）。
【００６６】
また、最終使用ライン情報バッファ６０１には、描画領域判定部１５０（図４）で抽出された最終使用ライン情報ＥＬが格納される。なお、最終使用ライン情報バッファ６０１には、処理対象のスキャンラインに描画される図形を構成する頂点について最終使用ライン情報ＥＬが保持されていてもよいし、全ての頂点について最終使用ライン情報ＥＬが保持されていてもよい。
【００６７】
また、アドレスＦＩＦＯ６０３には、キャッシュメモリＣＭに格納された頂点情報ＶＩＮＦがＮ個に達した後の、キャッシュメモリＣＭの空きアドレスがリストとして保持される。具体的に、キャッシュメモリＣＭから不要な頂点情報ＶＩＮＦが削除されたとき、制御部６０６によって、削除アドレスａｄがアドレスＦＩＦＯ６０３に追加される。また、キャッシュメモリＣＭに新たな頂点情報ＶＩＮＦが書き込まれるとき、アドレスＦＩＦＯ６０３の初めに追加されたアドレスａｄから順に、書き込みアドレスａｄとしてセレクタ回路６０２に出力される。
【００６８】
また、カウンタ６０４は、キャッシュメモリＣＭに格納される頂点情報ＶＩＮＦがＮ個に達するまでの間、キャッシュメモリＣＭに格納される頂点情報ＶＩＮＦの数をカウントすると共に、カウンタ値を書き込みアドレスａｄとしてセレクタ回路６０２に出力する。セレクタ回路６０２は、キャッシュメモリＣＭに格納された頂点情報ＶＩＮＦがＮ個に達するまでの間はカウンタ６０４から出力されるアドレスａｄを、達した後はアドレスＦＩＦＯ６０３から出力されたアドレスａｄを選択して、制御部６０６に出力する。
【００６９】
続いて、図８の頂点情報キャッシュ部６１０の処理の流れについて、フローチャート図に基づいて説明する。
【００７０】
図９は、図８の頂点情報キャッシュ部６１０の処理を説明するフローチャート図である。この処理において、頂点情報キャッシュ部６１０は、初期フラグＩｎｉｔｉａｌ（図８のセレクタ回路６０２に対応、１はカウンタ６０４、０はアドレスＦＩＦＯ６０３を選択することを示す）、カウンタＣＮＴ（図８のカウンタ６０４に対応）を有する。初期フラグＩｎｉｔｉａｌの初期値はキャッシュメモリに記憶される頂点情報ＶＩＮＦがＮ個に達していないことを示す１、カウンタＣＮＴの初期値はキャッシュメモリが空であることを示す０である（Ｓ１０）。全てのスキャンラインについて、工程Ｓ１１〜Ｓ２０の処理が行われる。
【００７１】
頂点情報キャッシュ部６１０の制御部６０６は、処理対象のスキャンラインに描画される図形の描画命令に基づいて頂点番号を取得する。そして、制御部６０６は、頂点番号に基づいてキャッシュタグＣＴを参照し、対象の頂点番号に対応するＥｍｐｔｙフラグをチェックする（Ｓ１１）。
【００７２】
ＥｍｐｔｙフラグがＦａｌｓｅのとき（Ｓ１２のＮＯ）、キャッシュメモリＣＭに対象の頂点情報ＶＩＮＦが格納されていることを示すため、キャッシュヒットと判定される。そのため、制御部６０６は、キャッシュヒット情報を頂点情報読み出し部３１０に送信する（Ｓ１４）。一方、ＥｍｐｔｙフラグがＴｒｕｅのとき（Ｓ１２のＹＥＳ）、キャッシュメモリＣＭに対象の頂点情報ＶＩＮＦが格納されていないことを示すため、キャッシュミスと判定される。そのため、制御部６０６は、キャッシュミス情報を頂点情報読み出し部３１０に送信する（Ｓ１３）。
【００７３】
続いて、制御部６０６は、キャッシュヒットの場合はキャッシュメモリＣＭからの頂点情報ＶＩＮＦの読み出しアドレスａｄ、キャッシュミスの場合はキャッシュメモリＣＭへの頂点情報ＶＩＮＦの書き込みアドレスａｄを決定する（Ｓ１５）。ここで、工程Ｓ１５について、次のフローチャート図に基づいて詳細に説明する。
【００７４】
図１０は、図９のフローチャート図におけるアドレス決定処理（Ｓ１５）の詳細を説明するフローチャート図である。
【００７５】
まず、キャッシュヒットの場合について説明する。キャッシュヒットの場合（Ｓ３０のＹＥＳ）、制御部６０６は、キャッシュタグＣＴに頂点番号に対応して格納されたアドレス情報ａｄを読み出し（Ｓ４２）、キャッシュヒット情報と共に頂点情報読み出し部３１０に出力する（Ｓ４３）。
【００７６】
次に、キャッシュミス情報の場合について説明する。キャッシュミスの場合（Ｓ３０のＮＯ）、制御部６０６は、頂点情報読み出し部３１０にキャッシュミス情報と共に、キャッシュメモリＣＭの空きアドレスがある場合に空きアドレスを渡す（Ｓ３１〜Ｓ４１）。
【００７７】
具体的に、制御部６０６は、まず、初期フラグＩｎｉｔｉａｌが１か否かを判定する（Ｓ３１）。初期フラグＩｎｉｔｉａｌが１の場合（Ｓ３１のＹＥＳ）、キャッシュメモリＣＭに格納された頂点情報の数が未だＮ個に達していないことを示す。この例において、キャッシュメモリＣＭに格納される頂点情報ＶＩＮＦの数がＮ個に達するまでの間、カウンタＣＮＴ値の示すアドレスａｄに頂点情報ＶＩＮＦが格納される。
【００７８】
そこで、制御部６０６は、キャッシュタグＣＴについて、対象の頂点番号のアドレスとしてカウンタＣＮＴの値（ａｄ）を格納すると共に、ＥｍｐｔｙフラグをＴｒｕｅからＦａｌｓｅに変更する（Ｓ３２）。続いて、制御部６０６は、当該アドレスａｄをキャッシュミス情報と共に頂点情報読み出し部３１０に出力する（Ｓ３３）。
【００７９】
続いて、制御部６０６は、カウンタＣＮＴの値がキャッシュメモリＣＭのアドレス最大値と一致するか否かを判定する（Ｓ３４）。一致する場合（Ｓ３４のＹＥＳ）、キャッシュメモリＣＭに格納される頂点情報ＶＩＮＦの数がＮ個に達したことを示す。そこで、制御部６０６は、初期フラグＩｎｉｔｉａｌを０に変更し（Ｓ３６）、以降の処理では、カウンタＣＮＴではなくアドレスＦＩＦＯに基づいて空きアドレスが取得されるように制御する。一方、カウンタＣＮＴの値がキャッシュメモリＣＭのアドレス最大値と一致しない場合（Ｓ３４のＮＯ）、キャッシュメモリＣＭに格納される頂点情報ＶＩＮＦの数が未だＮ個に達していないことを示す。そのため、制御部６０６は、初期フラグＩｎｉｔｉａｌの値を変更せず、カウンタＣＮＴの値をカウントアップする（Ｓ３５）。
【００８０】
工程Ｓ３１に戻り、初期フラグＩｎｉｔｉａｌが０であり（Ｓ３１のＮＯ）、キャッシュメモリＣＭに格納される頂点情報ＶＩＮＦの数がＮ個に達している場合、制御部６０６はアドレスＦＩＦＯ６０３から空きアドレスを取得する。具体的に、制御部６０６は、アドレスＦＩＦＯ６０３にアドレスが格納されているか否かを判定する（Ｓ３７）。アドレスＦＩＦＯ６０３が空の場合（Ｓ３７のＹＥＳ）、キャッシュメモリＣＭに空きがないことを示す。この場合、制御部６０６は、キャッシュメモリＣＭに頂点情報ＶＩＮＦを格納しない（Ｓ３８）。そのため、制御部６０６は、キャッシュミス情報のみを頂点情報読み出し部３１０に出力する。
【００８１】
一方、アドレスＦＩＦＯ６０３がアドレスを保持する場合（Ｓ３７のＮＯ）、制御部６０６は、アドレスＦＩＦＯ６０３から取得したアドレスをキャッシュメモリＣＭの空きアドレスａｄとして取得する（Ｓ３９）。このように、空きアドレスをアドレスＦＩＦＯ６０３に保持しておくことにより、制御部６０６は、キャッシュメモリＣＭの空きアドレスを取得するために、キャッシュメモリＣＭ及びキャッシュタグＣＴを検索する必要がない。制御部６０６は、アドレスＦＩＦＯ６０３からアドレスを読み出すだけで、キャッシュメモリＣＭの空きアドレスを取得することができる。これにより、キャッシュメモリＣＭの空きアドレスの取得処理が高速になり、処理全体のスループットが向上する。
【００８２】
続いて、制御部６０６は、キャッシュタグＣＴについて、対象の頂点番号のアドレス情報として、アドレスＦＩＦＯ６０３から取得したアドレスａｄを格納すると共に、ＥｍｐｔｙフラグをＴｒｕｅからＦａｌｓｅに変更する（Ｓ４０）。そして、制御部６０６は、当該アドレスａｄをキャッシュミス情報と共に頂点情報読み出し部３１０に出力する（Ｓ４１）。
【００８３】
このように、制御部６０６は、キャッシュヒットの場合、キャッシュヒット情報と共にキャッシュメモリＣＭの読み出しアドレスａｄを頂点情報読み出し部３１０に出力する。そして、図４で前述したとおり、図形作成部３３０によって、キャッシュメモリＣＭの読み出しアドレスａｄから頂点情報ＶＩＮＦが読み出される。
【００８４】
一方、制御部６０６は、キャッシュミスの場合、キャッシュミス情報と共に、キャッシュメモリＣＭに空きがある場合はキャッシュメモリＣＭへの書き込みアドレスａｄを頂点情報読み出し部３１０に出力する。そして、図４で前述したとおり、頂点情報ＶＩＮＦは外部メモリから読み出され、頂点処理が行われた頂点情報ＶＩＮＦが、図形作成部３０３によって、キャッシュメモリＣＭの書き込みアドレスａｄに格納される。
【００８５】
続いて、図９のフローチャート図の処理を、図５の具体例に基づいて説明する。
【００８６】
図１１は、図５の具体例に基づくキャッシュタグＣＴ１−１、ＣＴ１−２の遷移の一例を表す図である。同図において、キャッシュメモリＣＭには、頂点番号０、２〜４の頂点情報ＶＩＮＦが格納されており、キャッシュタグＣＴ１−１には、頂点情報ＶＩＮＦが格納されるキャッシュメモリＣＭのアドレスが頂点番号に対応して格納される。そして、キャッシュメモリＣＭに頂点情報ＶＩＮＦが格納されている頂点番号０、２〜４のＥｍｐｔｙフラグにはＦａｌｓｅ、頂点情報ＶＩＮＦが格納されていない頂点番号１、５のＥｍｐｔｙフラグにはＴｒｕｅが指定される。
【００８７】
図１１において、例えば、頂点番号０の頂点情報ＶＩＮＦを読み出す場合、制御部６０６はキャッシュタグＣＴ１−１を参照し、頂点番号０のＥｍｐｔｙフラグを参照する（図９のＳ１２）。この場合、頂点番号０のＥｍｐｔｙフラグがＦａｌｓｅであるためキャッシュヒットと判定され（図９のＳ１２のＮＯ）、キャッシュタグＣＴから読み出し対象のアドレス７番地が読み出され（図１０のＳ４２）、キャッシュヒット情報と共に（図９のＳ１４）頂点情報読み出し部３１０へ送信される（図１０のＳ４３）。そして、図形作成部３３０によって、キャッシュメモリの７番地から頂点情報ＶＩＮＦが読み出される。
【００８８】
一方、頂点番号１の頂点情報ＶＩＮＦを読み出す場合、キャッシュタグＣＴ１−１における頂点番号１のＥｍｐｔｙフラグはＴｒｕｅであるため、キャッシュミスと判定される（図９のＳ１２のＹＥＳ）。そのため、頂点情報キャッシュ部６１０は、初期フラグＩｎｉｔｉａｌが１の場合は（図１０のＳ３１のＹＥＳ）カウンタＣＮＴの値を（図１０のＳ３２、Ｓ３３）、初期フラグＩｎｉｔｉａｌが０の場合であって（図１０のＳ３１のＮＯ）、アドレスＦＩＦＯ６０３にアドレスがある場合は（図１０のＳ３７のＮＯ）、アドレスＦＩＦＯ６０３の初めに格納されたアドレスを、キャッシュメモリＣＭへの書き込みアドレスとして読み出す（図１０のＳ３９）。そして、アドレスはキャッシュミス情報と共に（図９のＳ１３）頂点情報読み出し部３１０へ送信される（図１０のＳ３３、Ｓ４１）。このとき、アドレスＦＩＦＯ６０３が空の場合（図１０のＳ３７のＹＥＳ）、キャッシュミス情報のみが出力される。
【００８９】
このように、本実施の形態例において、キャッシュタグＣＴ１−１は、それぞれの頂点について、キャッシュメモリＣＭに頂点情報ＶＩＮＦが格納されている場合にそのアドレスを格納する。このため、頂点情報読み出し部３１０は、キャッシュタグＣＴ１−１から頂点番号ＶＩＮＦを検索することなく、頂点番号に基づいてアドレスを逆引きすることで、キャッシュヒット／ミスの判定を高速に行い、キャッシュヒットの場合にキャッシュメモリＣＭにおける読み出しアドレスを高速に取得することができる。
【００９０】
ここで、図９のフローチャート図に戻り、続いて、キャッシュメモリＣＭにおける不要となる頂点情報ＶＩＮＦの削除処理（図９のＳ１６〜Ｓ２０）について説明する。キャッシュメモリＣＭへの書き込みアドレス、または、読み出しアドレスが決定すると（Ｓ１５）、頂点情報キャッシュ部６１０の制御部６０６は、続いて、対象の頂点番号の最終使用ラインを最終使用ライン情報バッファ６０１から読み出し（Ｓ１６）、処理対象のスキャンラインと最終使用ラインが一致するか否かを判定する（Ｓ１７）。
【００９１】
一致する場合（Ｓ１７のＹＥＳ）、処理対象のスキャンラインが、対象の頂点番号の頂点情報ＶＩＮＦが使用される最後のスキャンラインであることを示す。従って、制御部６０６は、キャッシュタグＣＴにおいて、当該頂点番号に対応するＫｅｅｐフラグを、保持しないことを示すＦａｌｓｅに変更する（Ｓ１９）。一方、一致しない場合（Ｓ１７のＮＯ）、対象の頂点番号の頂点情報ＶＩＮＦは、処理対象のスキャンラインの後で処理されるスキャンラインで使用されることを示す。従って、制御部６０６は、キャッシュタグＣＴにおける対象の頂点番号に対応するＫｅｅｐフラグを、保持を示すＴｒｕｅに変更する（Ｓ１８）。
【００９２】
そして、処理対象のスキャンラインに描画される全ての図形の描画命令について、工程Ｓ１１〜Ｓ１９を行うと、制御部６０６は、続いて、キャッシュメモリＣＭから不要な頂点情報ＶＩＮＦを削除する（Ｓ２０）。具体的に、制御部６０６は、キャッシュタグＣＴを参照し、ＫｅｅｐフラグがＦａｌｓｅ（保持しない）であって、ＥｍｐｔｙフラグがＦａｌｓｅ（キャッシュメモリに頂点情報が格納される）の頂点番号を検出する。即ち、キャッシュメモリＣＭに格納されており、次回以降に処理対象となるスキャンラインで使用されることのない頂点情報ＶＩＮＦが、削除対象の頂点情報ＶＩＮＦとして検出される。
【００９３】
また、制御部６０６は、キャッシュタグＣＴにおいて、頂点情報ＶＩＮＦを削除する対象の頂点番号のＥｍｐｔｙフラグをＦａｌｓｅからＴｒｕｅに変更し、キャッシュメモリＣＭにおける削除アドレスをアドレスＦＩＦＯ６０３に追加する。本実施の形態例における制御部６０６は、キャッシュタグＣＴのＥｍｐｔｙフラグの値に基づいてキャッシュヒット／ミス判定を行うため、頂点情報ＶＩＮＦの削除に当たり、キャッシュメモリＣＭの頂点情報ＶＩＮＦ及びキャッシュタグＣＴにおけるアドレスを削除する必要がない。
【００９４】
以上のように、図９、図１０のフローチャート図に基づいて、処理対象のスキャンラインについて、当該スキャンラインに描画される図形を構成する頂点の頂点情報ＶＩＮＦが読み出される。この処理が全てのスキャンラインについて行われる。
【００９５】
図９の工程Ｓ１６〜Ｓ２０の処理について、前述した図１１に基づいて具体的に説明する。図１１の例において、最終使用ライン情報バッファ６０１は前述した図６であり、図５の具体例に基づいて処理対象のスキャンラインがＹ１６である場合を例示する。図５において、スキャンラインＹ１６には図形Ｚ１〜Ｚ３が描画され、読み出し対象の頂点は頂点ｐ０、ｐ２〜ｐ５である。
【００９６】
図６の最終使用ライン情報ＥＬによると、頂点ｐ０、ｐ２〜ｐ５のうち、頂点ｐ０、ｐ４の最終使用ラインは処理対象のスキャンラインと同じＹ１６である（図９のＳ１７のＹＥＳ）。従って、制御部６０６は、図１１のキャッシュタグＣＴ１−１において、頂点番号０、４について頂点情報を読み出したとき、対応するＫｅｅｐフラグを保持しておく必要がないことを示すＦａｌｓｅに制御する（Ｓ１９）。また、制御部６０６は、最終使用ラインが処理対象のスキャンラインより後に処理されるスキャンラインを示す頂点番号２、３について、キャッシュタグＣＴ１−１において、対応するＫｅｅｐフラグを、保持を示すＴｒｕｅに制御する（Ｓ１８）。
【００９７】
そして、スキャンラインＹ１６に係る頂点の頂点情報ＶＩＮＦが全て読み出されたとき、制御部６０６は、図１１のキャッシュタグＣＴ１−２において、ＥｍｐｔｙフラグがＦａｌｓｅ、かつ、ＫｅｅｐフラグがＦａｌｓｅの頂点番号０、４について、ＥｍｐｔｙフラグをＴｒｕｅに制御する（Ｓ２０）。また、制御部６０６は、頂点番号０、４の頂点情報ＶＩＮＦが格納されていたキャッシュメモリＣＭのアドレス１番地、７番地をアドレスＦＩＦＯｆｌ（図８の６０３）に追加する。この例において、アドレスＦＩＦＯｆｌには、先にアドレス２番地、３番地が格納されている。
【００９８】
このように、制御部６０６は、最終使用ライン情報ＥＬに基づいて、キャッシュメモリＣＭに保持しておく必要のない頂点情報ＶＩＮＦを検出する。また、頂点番号に対応してキャッシュタグＣＴにＫｅｅｐフラグが設けられており、最終使用ラインが処理対象のスキャンラインと一致する頂点番号のＫｅｅｐフラグが制御されることにより、制御部６０６は、Ｋｅｅｐフラグを参照するだけで削除対象の頂点情報ＶＩＮＦを効率的に検出することができる。
【００９９】
また、制御部６０６は、キャッシュタグＣＴにおけるＥｍｐｔｙフラグを制御することで、擬似的にキャッシュメモリＣＭにおける頂点情報ＶＩＮＦを上書き可能にする制御を行う。これにより、例えば、キャッシュメモリＣＭからの頂点情報ＶＩＮＦの削除処理に時間を要する場合であっても、制御部６０６は高速に上書き可能制御を行うことができる。また、例えば、キャッシュタグＣＴにおけるＥｍｐｔｙフラグは、アドレス部よりも高速に書き換え可能なメモリで構成される。これにより、制御部６０６は、より高速に制御処理を行うことができる。
【０１００】
このように、制御部６０６は、最終使用ライン情報ＥＬに基づいて、保持しておく必要のない頂点情報ＶＩＮＦを確実に、且つ、高速に検出できると共に、キャッシュメモリＣＭにおける削除対象の頂点情報ＶＩＮＦの制御処理を高速に行うことができる。これにより、キャッシュメモリＣＭにおける頂点情報ＶＩＮＦの一連の制御処理が高速に行われる。
【０１０１】
以上説明してきたように、本実施の形態例における画像描画装置１００は、スキャンライン毎に、画像データＧＤＡＴＡを生成し、ラインバッファ４００に格納する。これにより、画像データＧＤＡＴＡを格納するラインバッファ４００は、２次元表示面ＤＩＳを分割したスキャンラインの１つ分のスキャンラインのサイズ分有していればよい。従って、本実施の形態例において、２次元表示面ＤＩＳの全体の画素のデータ（画像データ）を格納するフレームバッファに比べて、ラインバッファ４００のメモリサイズを小さくできる。
【０１０２】
また、本実施の形態例におけるキャッシュタグＣＴは、各頂点に対応してキャッシュメモリＣＭのアドレスを有する（逆引きキャッシュタグ）。これにより、画像描画装置１００は、キャッシュタグＣＴから対象の頂点の情報を検索する必要がなく、キャッシュタグＣＴにおける頂点のアドレス情報を直接参照することで高速にキャッシュヒット／ミスの判定を行うことができると共に、キャッシュヒットのとき、同時にキャッシュメモリＣＭのアドレスを取得できる。これにより、画像描画装置１００は、キャッシュヒットの場合にキャッシュメモリＣＭの読み出し対象のアドレスを高速に取得することができる。
【０１０３】
また、本実施の形態例における画像描画装置１００は、各頂点について、当該頂点が構成する図形が描画されるスキャンラインのうち、後に処理されるスキャンラインの情報を最終使用ライン情報として抽出する。そして、画像描画装置１００は、最終使用ラインが処理対象のスキャンラインを示す頂点の頂点情報ＶＩＮＦをキャッシュメモリＣＭから削除対象の頂点情報ＶＩＮＦとして検出する。これにより、画像描画装置１００は、最終使用ライン情報に基づいて、キャッシュメモリＣＭに保持しておく必要のない頂点情報ＶＩＮＦを確実に削除対象とし、キャッシュメモリＣＭ上で上書き可能に制御することができる。この結果、キャッシュメモリＣＭには次回以降に処理対象となるスキャンラインで使用される頂点情報ＶＩＮＦのみが保持され、キャッシュメモリＣＭのキャッシュヒット率が向上し、外部メモリへの読み出し処理回数が抑制される。
【０１０４】
また、本実施の形態例における画像描画装置１００は、キャッシュタグＣＴにＫｅｅｐフラグを設け、削除対象とする頂点情報ＶＩＮＦに対応する頂点番号のＫｅｅｐフラグを、保持しないことを示す値に制御しておく。これにより、画像描画装置１００は、削除対象の頂点情報ＶＩＮＦの検出時に、各頂点のＫｅｅｐフラグの値を参照するだけで、削除対象の頂点情報ＶＩＮＦを全て検出することができる。
【０１０５】
また、本実施の形態例における画像描画装置１００は、キャッシュタグＣＴにＥｍｐｔｙフラグを設ける。これにより、画像描画装置１００は、キャッシュヒット／ミスの判定を、キャッシュタグ６０２における対象の頂点のＥｍｐｔｙフラグをチェックすることによって簡易に行うことができる。このため、画像描画装置１００は、キャッシュメモリＣＭにおける頂点情報ＶＩＮＦを上書き可能にする制御を、Ｅｍｐｔｙフラグの制御によって実現できる。これにより、キャッシュメモリＣＭからの頂点情報ＶＩＮＦの削除処理、及び、キャッシュタグＣＴにおけるアドレス情報の削除処理に時間を要する場合であっても、高速、且つ、効率的に頂点情報ＶＩＮＦを上書き可能にする制御が行われる。
【０１０６】
さらに、本実施の形態例における画像描画装置１００は、キャッシュメモリＣＭの空きアドレスを格納するアドレスＦＩＦＯ６０３を有する。これにより、画像描画装置１００は、キャッシュメモリＣＭ及びキャッシュタグＣＴを検索することなく、キャッシュメモリＣＭの空きアドレスを効率的に取得することができる。これにより、キャッシュメモリＣＭの空きアドレスの取得処理が高速になる。
【０１０７】
なお、この例において、キャッシュタグＣＴはＫｅｅｐフラグを有し、画像描画装置１００は、Ｋｅｅｐフラグを制御することによって、削除対象の頂点情報ＶＩＮＦを検出する。しかしながら、Ｋｅｅｐフラグは必ずしも必要ではない。画像描画装置１００は、Ｋｅｅｐフラグを用いず、削除対象の頂点情報ＶＩＮＦの検出処理時に、頂点情報ＶＩＮＦを読み出した各頂点について最終使用ラインと処理対象のスキャンラインとを比較し、削除対象とするか否かを判定してもよい。
【０１０８】
＜第２の実施の形態例＞
第１の実施の形態例では、各頂点についてそれぞれ情報を有するキャッシュタグ（逆引きキャッシュタグ）を使用する場合において、最終使用ライン情報に基づいて、不要な頂点情報ＶＩＮＦをキャッシュメモリＣＭから削除する場合について例示した。しかし、このキャッシュメモリＣＭにおける削除方法は、キャッシュメモリＣＭの各アドレスに対応して当該アドレスに格納される頂点番号を有するキャッシュタグを用いる場合についても有効である。本実施の形態例におけるキャッシュタグＣＴ以外の構成については、第１の実施の形態例と同様である。
【０１０９】
図１２は、第２の実施の形態例におけるキャッシュタグＣＴ２−１、ＣＴ２−２及びキャッシュメモリＣＭ２−１、ＣＭ２−２の状態の一例を表す図である。同図上のキャッシュタグＣＴ２−１は、同図上のキャッシュメモリＣＭ２−１の各アドレスに対応して、当該アドレスに頂点情報ＶＩＮＦが格納される場合にその頂点番号を有する。例えば、キャッシュタグＣＴ２−１によると、キャッシュメモリＣＭ２−１の０番地に頂点番号２の頂点情報ＶＩＮＦが格納される。
【０１１０】
続いて、図９のフローチャート図で前述した、キャッシュメモリＣＭにおける不要な頂点情報ＶＩＮＦの削除処理（図９のＳ１６〜Ｓ２０）について、図１２の具体例に基づいて説明する。この例では、第１の実施の形態例と同様にして、図５の具体例に基づき、処理対象のスキャンラインがＹ１６、最終使用ライン情報ＥＬが図６である場合を例示する。
【０１１１】
図５の具体例において、スキャンラインＹ１６の処理では、頂点番号０、２〜４の頂点情報が読み出される。そして、各頂点番号に対応する最終使用ラインが読み出される（Ｓ１６）。そして、頂点番号０、４の最終使用ラインはＹ１６であり、処理対象のスキャンラインと一致するため（Ｓ１７のＹＥＳ）、対応するＫｅｅｐフラグがＦａｌｓｅに制御される（図９のＳ１７のＹＥＳ、Ｓ１９）。また、頂点番号１、３のＫｅｅｐフラグについては、Ｔｒｕｅに制御される（Ｓ１７のＮＯ、Ｓ１８）。
【０１１２】
そして、処理対象のスキャンラインＹ１６に係る頂点の頂点情報ＶＩＮＦが全て読み出されたとき、制御部６０６は、図１２のＣＴ２−２のように、ＥｍｐｔｙフラグがＦａｌｓｅ、かつ、ＫｅｅｐフラグがＦａｌｓｅの頂点番号０、４のＥｍｐｔｙフラグを、Ｔｒｕｅに制御する（Ｓ２０）。これにより、擬似的に、キャッシュメモリＣＭ２−２から頂点番号０、４の頂点情報ＶＩＮＦが削除される。
【０１１３】
このように、本実施の形態例においても、キャッシュメモリＣＭ２−２には、最終使用ライン情報ＥＬに基づいて、次回以降に処理対象となるスキャンラインで使用される頂点情報ＶＩＮＦのみが保持される。この結果、キャッシュメモリＣＭ２−２のキャッシュヒット率が向上し、外部メモリへの読み出し処理回数が抑制される。このように、最終使用ライン情報ＥＬに基づくキャッシュメモリＣＭから削除対象の頂点情報ＶＩＮＦの検出方法は、いずれの形態のキャッシュタグＣＴについても有効である。
【０１１４】
なお、本実施の形態例においても、Ｋｅｅｐフラグは必ずしも必要ではない。画像描画装置１００は、Ｋｅｅｐフラグを用いず、削除対象の頂点情報ＶＩＮＦの検出時に、頂点情報ＶＩＮＦを読み出した各頂点について最終使用ライン情報ＥＬと処理対象のスキャンラインとを比較し、削除対象とするか否かを判定してもよい。
【０１１５】
なお、本実施の形態例における画像描画処理は、コンピューター読み取り可能な記録媒体にプログラムとして記憶され、当該プログラムをコンピューターが読み出して実行することによって行われてもよい。
【０１１６】
以上の実施の形態をまとめると、次の付記のとおりである。
【０１１７】
（付記１）
複数のスキャンラインを有する描画領域に図形を描画する画像描画装置であって、
処理対象の前記スキャンラインに描画される図形を判定し、判定した前記図形を構成する各頂点を抽出する描画位置判定手段と、
前記処理対象のスキャンラインについて、抽出された頂点の座標情報を含む頂点情報を、前記描画領域に描画される図形の頂点の頂点情報が記憶される頂点情報メモリから読み出す頂点情報読み出し手段と、
読み出した前記頂点情報に基づいて、前記処理対象のスキャンラインの画像データを生成する画像生成手段と、
前記画像生成手段によって生成された前記画像データを記憶するラインバッファと、を有し、
前記頂点情報読み出し手段は、
前記頂点情報を一時記憶するキャッシュメモリと、
前記描画領域に描画される図形の頂点全てについて、前記キャッシュメモリに前記頂点情報が記憶される場合に前記頂点情報が記憶されたアドレスを記憶するキャッシュタグと、
前記キャッシュタグを参照し、読み出し対象の頂点情報について前記アドレスが記憶されている場合は前記キャッシュメモリの当該アドレスから前記頂点情報を読み出し、記憶されていない場合は前記頂点情報メモリから読み出した頂点情報を前記キャッシュメモリに記憶させそのアドレスを前記キャッシュタグに記憶する制御手段と、
を有する画像描画装置。
【０１１８】
（付記２）
付記１について、
前記描画位置判定手段は、さらに、前記頂点について、当該頂点が構成する前記図形が描画される前記スキャンラインのうち、処理順が後の前記スキャンラインを示す最終使用ライン情報を抽出し、
前記制御手段は、さらに、前記最終使用ライン情報が前記処理対象のスキャンラインを示す頂点情報を上書き可能にする画像描画装置。
【０１１９】
（付記３）
付記２について、
前記キャッシュタグは、さらに、前記アドレスに加えてキープフラグを記憶し、
前記制御手段は、前記最終使用ライン情報が前記処理対象のスキャンラインを示す頂点情報の前記キープフラグを非保持を示す値に制御し、前記キープフラグの値が非保持を示す頂点情報を上書き可能にする画像描画装置。
【０１２０】
（付記４）
付記２または３のいずれかにおいて、
前記キャッシュタグは、さらに、前記描画領域に描画される図形の頂点全てについて無効フラグを記憶し、
前記制御手段は、前記無効フラグを無効を示す値に制御することによって前記頂点情報を上書き可能にする画像描画装置。
【０１２１】
（付記５）
付記４において、
前記キャッシュタグにおける前記無効フラグと前記アドレスとは異なる記憶手段に記憶され、前記無効フラグが記憶される記憶手段は、前記アドレスが記憶される記憶手段よりもアクセス速度が速い画像描画装置。
【０１２２】
（付記６）
付記２乃至５のいずれかにおいて、
前記制御手段は、前記頂点情報を上書き可能にするときに当該頂点情報が記憶されたキャッシュメモリのアドレスを空きアドレスリストに追加し、前記読み出した頂点情報を前記キャッシュメモリに記憶させるときに当該空きアドレスリストから前記アドレスを取得する画像描画装置。
【０１２３】
（付記７）
複数のスキャンラインを有する描画領域に図形を描画する画像描画装置であって、
処理対象の前記スキャンラインに描画される図形を判定し、判定した前記図形を構成する各頂点を抽出すると共に、当該頂点が構成する前記図形が描画される前記スキャンラインのうち、処理順が後の前記スキャンラインを示す最終使用ライン情報を抽出する描画位置判定手段と、
前記処理対象のスキャンラインについて、抽出された頂点の座標情報を含む頂点情報を、前記描画領域に描画される図形の頂点の頂点情報が記憶される頂点情報メモリから読み出す頂点情報読み出し手段と、
読み出した前記頂点情報に基づいて、前記処理対象のスキャンラインの画像データを生成する画像生成手段と、
前記画像生成手段によって生成された前記画像データを記憶するラインバッファと、を有し、
前記頂点情報読み出し手段は、
前記頂点情報を一時記憶するキャッシュメモリと、
前記頂点情報メモリから読み出した頂点情報を前記キャッシュメモリに記憶させ、前記キャッシュメモリへ記憶した前記頂点情報を読み出し、読み出した前記頂点情報が前記最終使用ライン情報と一致する場合に前記頂点情報を上書き可能にする制御手段と、
を有する画像描画装置。
【０１２４】
（付記８）
付記１乃至７のいずれかにおいて、
前記画像描画装置は、さらに、
前記ラインバッファに生成された前記画像データを表示させる表示手段と、を有する画像描画装置。
【０１２５】
（付記９）
複数のスキャンラインを有する描画領域における図形の描画処理をコンピューターに実行させるコンピューター読み取り可能な画像描画プログラムにおいて、
前記描画処理は、
処理対象の前記スキャンラインに描画される図形を判定し、判定した前記図形を構成する各頂点を抽出する描画位置判定工程と、
前記処理対象のスキャンラインについて、抽出された頂点の座標情報を含む頂点情報を、前記描画領域に描画される図形の頂点の頂点情報が記憶される頂点情報メモリから読み出す頂点情報読み出し工程と、
読み出した前記頂点情報に基づいて、前記処理対象のスキャンラインの画像データを生成してラインバッファに記憶する画像生成工程と、を有し、
前記頂点情報読み出し工程は、
前記頂点情報が一時記憶されるキャッシュメモリに対するキャッシュタグであって、前記描画領域に描画される図形の頂点全てについて、前記キャッシュメモリに前記頂点情報が記憶される場合に当該頂点情報が記憶されたアドレスが記憶される前記キャッシュタグを参照し、読み出し対象の頂点情報について前記アドレスが記憶されている場合は前記キャッシュメモリの当該アドレスから前記頂点情報を読み出し、記憶されていない場合は前記頂点情報メモリから読み出した頂点情報を前記キャッシュメモリに記憶させそのアドレスを前記キャッシュタグに記憶する制御工程と、
を有する画像描画プログラム。
【０１２６】
（付記１０）
複数のスキャンラインを有する描画領域における図形の描画処理をコンピューターに実行させるコンピューター読み取り可能な画像描画プログラムにおいて、
前記描画処理は、
処理対象の前記スキャンラインに描画される図形を判定し、判定した前記図形を構成する各頂点を抽出すると共に、当該頂点が構成する前記図形が描画される前記スキャンラインのうち、処理順が後の前記スキャンラインを示す最終使用ライン情報を抽出する描画位置判定工程と、
前記処理対象のスキャンラインについて、抽出された頂点の座標情報を含む頂点情報を、前記描画領域に描画される図形の頂点の頂点情報が記憶される頂点情報メモリから読み出す頂点情報読み出し工程と、
読み出した前記頂点情報に基づいて、前記処理対象のスキャンラインの画像データを生成してラインバッファに記憶する画像生成工程と、を有し、
前記頂点情報読み出し工程は、
前記頂点情報メモリから読み出した頂点情報を、前記頂点情報が一時記憶されるキャッシュメモリに記憶させ、前記キャッシュメモリへ記憶した前記頂点情報を読み出し、読み出した前記頂点情報が前記最終使用ライン情報と一致する場合に前記頂点情報を上書き可能にする制御工程と、
を有する画像描画プログラム。
【０１２７】
（付記１１）
複数のスキャンラインを有する描画領域に図形を描画する画像描画方法であって、
処理対象の前記スキャンラインに描画される図形を判定し、判定した前記図形を構成する各頂点を抽出する描画位置判定工程と、
前記処理対象のスキャンラインについて、抽出された頂点の座標情報を含む頂点情報を、前記描画領域に描画される図形の頂点の頂点情報が記憶される頂点情報メモリから読み出す頂点情報読み出し工程と、
読み出した前記頂点情報に基づいて、前記処理対象のスキャンラインの画像データを生成してラインバッファに記憶する画像生成工程と、を有し、
前記頂点情報読み出し工程は、
前記頂点情報が一時記憶されるキャッシュメモリに対するキャッシュタグであって、前記描画領域に描画される図形の頂点全てについて、前記キャッシュメモリに前記頂点情報が記憶される場合に当該頂点情報が記憶されたアドレスが記憶される前記キャッシュタグを参照し、読み出し対象の頂点情報について前記アドレスが記憶されている場合は前記キャッシュメモリの当該アドレスから前記頂点情報を読み出し、記憶されていない場合は前記頂点情報メモリから読み出した頂点情報を前記キャッシュメモリに記憶させそのアドレスを前記キャッシュタグに記憶する制御工程と、
を有する画像描画方法。
【０１２８】
（付記１２）
複数のスキャンラインを有する描画領域に図形を描画する画像描画方法であって、
処理対象の前記スキャンラインに描画される図形を判定し、判定した前記図形を構成する各頂点を抽出すると共に、当該頂点が構成する前記図形が描画される前記スキャンラインのうち、処理順が後の前記スキャンラインを示す最終使用ライン情報を抽出する描画位置判定工程と、
前記処理対象のスキャンラインについて、抽出された頂点の座標情報を含む頂点情報を、前記描画領域に描画される図形の頂点の頂点情報が記憶される頂点情報メモリから読み出す頂点情報読み出し工程と、
読み出した前記頂点情報に基づいて、前記処理対象のスキャンラインの画像データを生成してラインバッファに記憶する画像生成工程と、を有し、
前記頂点情報読み出し工程は、
前記頂点情報メモリから読み出した頂点情報を、前記頂点情報が一時記憶されるキャッシュメモリに記憶させ、前記キャッシュメモリへ記憶した前記頂点情報を読み出し、読み出した前記頂点情報が前記最終使用ライン情報と一致する場合に前記頂点情報を上書き可能にする制御工程と、
を有する画像描画方法。
【符号の説明】
【０１２９】
１００：画像描画装置、１０：描画位置判定部、２０：頂点読み出し部、３０：画像生成部、３１０：頂点情報読み出し部、３２０：頂点処理部、３３０：図形作成部、３４０：画素生成部、３５０：画素処理部、３６０：画素除去部、４１０：ラインデプスバッファ、４００：ラインバッファ、５００：表示回路、３４５：テクスチャユニット、６１０：頂点キャッシュ部
【図１】
0005845910.tif 000002
【図２】
0005845910.tif 000003
【図３】
0005845910.tif 000004
【図４】
0005845910.tif 000005
【図５】
0005845910.tif 000006
【図６】
0005845910.tif 000007
【図７】
0005845910.tif 000008
【図８】
0005845910.tif 000009
【図９】
0005845910.tif 000010
【図１０】
0005845910.tif 000011
【図１１】
0005845910.tif 000012
【図１２】
0005845910.tif 000013