(57)【特許請求の範囲】
【請求項１】
表示画面に含まれる図形の図形インデックス、又は該図形に適用される設定パラメータを含む図形記述情報を、前記表示画面が分割された領域毎に判別する判別部と、
判別された前記領域毎の図形記述情報のデータサイズを集計する集計部と、
集計された前記データサイズに基づき、各領域の図形記述情報を書き込むメモリの先頭アドレスを、前記各領域の図形記述情報が前記メモリの連続する記憶領域に記憶されるように決定するアドレス決定部と、
前記メモリに前記領域毎の図形記述情報が書き込まれる際に、書き込まれる前記領域毎の図形記述情報のデータサイズから、前記メモリに割り当てられた所定の記憶領域のサイズを超えるオーバーフローが発生するか否かを判定する判定部と、
前記オーバーフローが発生すると判定された場合、オーバーフロー発生対象の表示画面が分割された領域のデータサイズを記憶する初期値記憶部と、
前記オーバーフローが発生しないと判定された場合、決定された前記先頭アドレスから順に、前記領域毎の図形記述情報を前記メモリに書き込み、前記オーバーフローが発生すると判定された場合、書き込みを停止し、図形記述情報の読み出しが行われて前記メモリに空きができたときに前記初期値記憶部に記憶されたデータサイズを用いて、前記オーバーフロー発生対象の領域から書き込み処理を再開する書き込み部と、
を備える描画処理装置。
【請求項２】
前記判別部は、
前記書き込み部が前記書き込み処理を再開する場合、判別前の図形記述情報を用いて、再度判別処理を行う請求項１記載の描画処理装置。
【請求項３】
前記書き込み部による書き込みアドレスは、
書き込み対象領域のデータサイズ−前記メモリのサイズ×（前記メモリへの書き込み処理を停止するまでの書き込み回数−１）＋前記メモリの先頭アドレス
である請求項１又は２記載の描画処理装置。
【請求項４】
表示画面に含まれる図形の図形インデックス、又は該図形に適用される設定パラメータを含む図形記述情報を、前記表示画面が分割された領域毎に判別し、
判別された前記領域毎の図形記述情報のデータサイズを集計し、
集計された前記データサイズに基づき、各領域の図形記述情報を書き込むメモリの先頭アドレスを、前記各領域の図形記述情報が前記メモリの連続する記憶領域に記憶されるように決定し、
前記メモリに前記領域毎の図形記述情報が書き込まれる際に、書き込まれる前記領域毎の図形記述情報のデータサイズから、前記メモリに割り当てられた所定の記憶領域のサイズを超えるオーバーフローが発生するか否かを判定し、
前記オーバーフローが発生すると判定された場合、オーバーフロー発生対象の表示画面が分割された領域のデータサイズを記憶部に記憶し、
前記オーバーフローが発生しないと判定された場合、決定された前記先頭アドレスから順に、前記領域毎の図形記述情報を前記メモリに書き込み、前記オーバーフローが発生すると判定された場合、書き込みを停止し、図形記述情報の読み出しが行われて前記メモリに空きができたときに前記記憶部に記憶されたデータサイズを用いて、前記オーバーフロー発生対象の領域から書き込み処理を再開する処理をコンピュータが実行する描画処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、タイル型アーキテクチャを用いる描画処理装置及び描画処理方法に関する。
【背景技術】
【０００２】
三次元グラフィックの描画を実現するハードウェア構成の一つとして、タイル型アーキテクチャがある。このタイル型アーキテクチャは、表示画面を複数の小領域（タイル）に分割し、このタイルごとに三次元グラフィックスを描画する。
【０００３】
タイル型アーキテクチャを用いる描画処理装置では、ハードウェア内部にタイル領域分のバッファを備える。このバッファには、タイル単位で内部の描画に必要なシーンデータが読み込みまれる。描画処理装置は、タイル毎のシーンデータに基づいて、タイル内部の描画を行う。
【０００４】
描画処理装置は、このバッファを用いることで、元シーンデータを記憶したメモリとのアクセス無しに描画を行うことが可能になり、このメモリへのメモリアクセスを大幅に削減することができる。
【０００５】
タイル型アーキテクチャの描画処理装置では、グラフィックスデータを一時的に記憶しておくキャッシュを効率的に利用することができる。なお、各タイルに対応するシーンデータには、そのタイル内部に少なくとも一部が描画される図形を示す図形インデックスやその図形の描画に関する設定パラメータなどが含まれる。以降では、シーンデータに含まれる図形インデックスや設定パラメータへの設定値などをまとめて図形記述情報と称する。
【０００６】
このようなタイル単位のシーンデータは、個々の図形に着目して生成されたシーンデータをタイル毎にソートすることによって生成される。従来のソート処理で生成されたタイル単位のシーンデータは、各タイルに含まれる図形にかかわる図形記述情報の記憶場所をポインタで示すリスト構造を用いて表されている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特表２００３−５２９８５９号公報
【特許文献２】特開２００３−２９６７４７号公報
【特許文献３】特表２００５−５２６５１７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
ところで、上述した従来技術では、タイル単位のシーンデータがリスト構造を有している。したがって、従来のタイル単位のシーンデータを、例えば外部メモリに記憶した場合に、上述したリスト構造で示される図形インデックスや設定値パラメータのアドレスは、メモリのメモリ空間において離散的に分布する。
【０００９】
このため、描画処理装置は、個々のタイル内の描画処理の際に、このリスト構造に従って、図形インデックスや設定値パラメータをメモリの様々な記憶領域から読み出していた。このとき、描画処理装置がアクセスするメモリのアドレスには連続性がないため、バーストアクセスのように効率的なメモリアクセスを実現することが困難だった。
【００１０】
本件開示の装置および方法は、個々のタイルに対応するタイル単位のシーンデータを、効率的なメモリアクセスが可能なように記憶させることができる描画処理装置および描画処理方法を提供することを目的とする。
【課題を解決するための手段】
【００１１】
開示の一態様における描画処理装置は、表示画面に含まれる図形の図形インデックス、又は該図形に適用される設定パラメータを含む図形記述情報を、前記表示画面が分割された領域毎に判別する判別部と、判別された前記領域毎の図形記述情報のデータサイズを集計する集計部と、集計された前記データサイズに基づき、各領域の図形記述情報を書き込むメモリの先頭アドレスを、前記各領域の図形記述情報が前記メモリの連続する記憶領域に記憶されるように決定するアドレス決定部と、前記メモリに前記領域毎の図形記述情報が書き込まれる際に、書き込まれる前記領域毎の図形記述情報のデータサイズから、前記メモリに割り当てられた所定の記憶領域のサイズを超えるオーバーフローが発生するか否かを判定する判定部と、前記オーバーフローが発生すると判定された場合、オーバーフロー発生対象の表示画面が分割された領域のデータサイズを記憶する初期値記憶部と、前記オーバーフローが発生しないと判定された場合、決定された前記先頭アドレスから順に、前記領域毎の図形記述情報を前記メモリに書き込み、前記オーバーフローが発生すると判定された場合、書き込みを停止し、図形記述情報の読み出しが行われて前記メモリに空きができたときに前記初期値記憶部に記憶されたデータサイズを用いて、前記オーバーフロー発生対象の領域から書き込み処理を再開する書き込み部と、を備える。
【発明の効果】
【００１２】
開示の技術によれば、個々のタイルに対応するタイル単位のシーンデータを、効率的なメモリアクセスが可能なように記憶させることができる。
【図面の簡単な説明】
【００１３】
【図１】実施例における描画処理装置の構成の一例を示すブロック図。
【図２】シーンデータ生成部で生成されるシーンデータの一例を示す図。
【図３】タイル毎にソートされたシーンデータの一例を示す図。
【図４】実施例におけるソート部の構成の一例を示すブロック図。
【図５】タイルバッファに保持されるデータの一例を示す図。
【図６】設定値保持部に保持されるデータの一例を示す図。
【図７】実施例における描画制御処理の一例を示すフローチャート。
【図８】判別処理（その１）の一例を示すフローチャート。
【図９】判別処理（その２）の一例を示すフローチャート。
【図１０】切替制御処理の一例を示すフローチャート。
【図１１】集計処理の一例を示すフローチャート。
【図１２】初期化後の各設定値の一例を示す図。
【図１３】Ｘ３入力後の各設定値の一例を示す図。
【図１４】Ｘ６入力後の各設定値の一例を示す図。
【図１５】Ｘ１０入力後の各設定値の一例を示す図。
【図１６】Ｘ１３入力後の各設定値の一例を示す図。
【図１７】シーンカウント終了時の各設定値の一例を示す図。
【図１８】アドレス決定処理の一例を示すフローチャート。
【図１９】アドレス決定後のタイルバッファの例を示す図。
【図２０】書き込み処理（その１）の一例を示すフローチャート。
【図２１】書き込み処理（その２）の一例を示すフローチャート。
【図２２】書き込み処理の概要を説明するための図。
【図２３】三角形１の書き込み処理の終了時の各設定値の一例を示す図。
【図２４】三角形２の書き込み処理時の各設定値の一例を示す図。
【図２５】オーバーフロー発生時の各設定値の一例を示す図。
【図２６】オーバーフロー後の各設定値の一例を示す図。
【図２７】２回目の書き込み処理開始時の各設定値の一例を示す図。
【図２８】タイル２の三角形２の書き込み時における各設定値の一例を示す図。
【図２９】２回目の書き込み終了時の各設定値の一例を示す図。
【図３０】実施例における描画処理装置のハードウェア構成の一例を示すブロック図。
【発明を実施するための形態】
【００１４】
以下、図面に基づいて、実施例について詳細に説明する。
【００１５】
［実施例］
以下に説明する実施例の描画処理装置では、タイル型アーキテクチャを用いる。タイルとは、表示画面を複数に分割した領域をいう。
【００１６】
＜描画処理装置の構成＞
図１は、実施例における描画処理装置の構成の一例を示すブロック図である。図１に示す描画処理装置では、シーンデータ生成部１０１と、メモリ１０２と、レンダリング部１０３と、ソート部１１０とを備える。
【００１７】
シーンデータ生成部１０１は、個々の図形に着目したシーンデータを生成し、メモリ１０２に記憶する。図１に示す例では、メモリ１０２に記憶されたシーンデータに符号１０５を付す。
【００１８】
ソート部１１０は、シーンデータ１０５を読み出して、タイルを単位としてソートする処理を行う。この並べ替え処理によって得られたタイル単位のシーンデータは、メモリ１０２に記憶される。
【００１９】
図１に示すソート部１１０は、読込部１１１と、判別部１１２と、切替制御部１１３と、集計部１１４と、アドレス決定部１１５と、メモリ書込部１１６と、オーバーフロー判定部１１７と、退避／復帰部１１８と、初期値保持部１１９とを備える。なお、図１に示す例では、メモリ１０２に記憶されたタイル単位のシーンデータに符号１０６を付す。ソート部１１０の詳細な処理は後述する。
【００２０】
レンダリング部１０３は、シーンデータ読出部１３１と、画素情報生成／演算部１３２と、表示判定部１３３と、表示データ出力処理部１３４とを備える。
【００２１】
シーンデータ読出部１３１は、上述したタイル単位のシーンデータ１０６をタイルごとに順次に読み出す。
【００２２】
画素情報生成／演算部１３２は、シーンデータ読出部１３１により読み出されたシーンデータに基づいて、画素情報の生成およびテクスチャ情報に基づく演算処理を行う。
【００２３】
表示判定部１３３は、画素情報生成／演算部１３２の処理で得られた画素データに対し、Ｚテストやステンシルテストなどの処理を行う。これらのテスト処理により、個々の画素について表示するか否かが判定される。
【００２４】
表示データ出力処理部１３４は、表示判定部１３３によって表示対象と判定された画素データを、メモリ１０２に記憶する。図１に示す例では、メモリ１０２に記憶された表示用画素データに符号１０７を付す。
【００２５】
図１に示すタイル単位のシーンデータ１０６には、各タイルのシーンデータが含まれる。各タイルのシーンデータが、メモリ１０２の記憶領域において、連続的に配置されていれば、シーンデータ読出部１３１は、これらのシーンデータをバースト的に読み出すことができ、メモリアクセスを効率化することができる。
【００２６】
例えば、レンダリング部１０３による描画領域に含まれる各タイルのシーンデータを、メモリ１０２から一括して読み出して、順次に各タイルの描画処理に利用することができる。
【００２７】
以下、ソート部１１０によって、各タイルのシーンデータをメモリ１０２の記憶領域に連続的に記憶する方法について説明する。
【００２８】
図２は、シーンデータ生成部１０１で生成されるシーンデータの一例を示す図である。シーンデータは、図形記述情報として、各設定パラメータへの設定値と、描画する図形を示す図形インデックスと、図形が配置されるタイルを示すタイル識別子とを含む。設定パラメータは、図形に適用されるパラメータを示す。図２に示す符号「Ｘ０」、「Ｘ１」、・・・は、シーンデータに含まれる個々の図形記述情報に対応する。
【００２９】
図２に示す例では、設定パラメータＡ，Ｂ，Ｃへの設定値をそれぞれ「設定Ａ−ｋ」、「設定Ｂ−ｋ」、「設定Ｃ−ｋ」のように示す。これらの設定値は、例えば、設定パラメータの種類を示す符号「Ａ」、「Ｂ」、「Ｃ」と組み合わせられた番号ｋによって区別される。この番号ｋは、例えば、シーンデータにおける設定値の出現順を示す。
【００３０】
また、図２に示す例では、図形インデックスの一例として、三角形１、三角形２などが示される。これらの図形インデックスに続いて読み込まれるタイル識別子によって、個々の図形インデックスで示される図形が配置されるタイルが特定される。
【００３１】
図２に示すシーンデータの例では、図形インデックス「三角形１」に、タイル番号「Ｔｉｌｅ０」、「Ｔｉｌｅ１」が続いている。これは、「三角形１」が、タイル０とタイル１とに含まれることを表す。以降では、タイル識別子としてタイル番号を用いる例を説明する。
【００３２】
また、図２に示すシーンデータでは、図形インデックスに先立って設定値が設定された設定パラメータが図形の描画に適用される。図２に示す三角形１、２には、設定パラメータＡ，Ｂ，Ｃとして、共通して、「設定Ａ−０」、「設定Ｂ−０」、「設定Ｃ−０」が適用される。
【００３３】
図３は、タイル毎にソートされたシーンデータの一例を示す図である。図２に示すシーンデータに含まれる各図形記述情報は、図３に示すように、ソート部１１０によりタイル毎にソートされる。タイル毎にソートされた図形記述情報を含むタイル単位のシーンデータの長さは、それぞれ異なる。
【００３４】
したがって、描画範囲に連続して並んでいる各タイルに対応するシーンデータの長さを見積もっておけば、これらのシーンデータを、メモリ１０２の連続する記憶領域に記憶することができる。
【００３５】
図１に示すソート部１１０の読込部１１１は、メモリ１０２のシーンデータ１０５から図形記述情報を順次読み込む。
【００３６】
判別部１１２は、順次に読み込まれる図形記述情報について、後述する判別処理を行うことにより、各タイルに対応するシーンデータに含まれる図形記述情報を判別する。例えば、判別部１１２は、表示画面に含まれる図形の図形インデックス、又はこの図形に適用される設定パラメータを含む図形記述情報を、表示画面が分割されたタイル毎に判別する。この判別結果は、切替制御部１１３を介して、集計部１１４あるいはメモリ書込部１１６に出力される。
【００３７】
集計部１１４は、切替制御部１１３から取得した判別結果の図形記述情報に対し、タイル毎の図形記述情報のデータサイズを集計する処理を行う。集計部１１４は、各タイルに対応するシーンデータに含まれる図形記述情報のデータサイズの総和を得ることができる。
【００３８】
アドレス決定部１１５は、集計部１１４により集計されたデータサイズに基づき、各タイルの図形記述情報を書き込む先頭アドレスを、各タイルの図形記述情報がメモリ１０２の連続する記憶領域に記憶されるように決定する。アドレス決定部１１５は、各タイルに対応するシーンデータが、例えば、タイル番号順に、メモリ１０２の記憶領域において連続して配置されるように、それぞれの先頭アドレスを決定することができる。
【００３９】
オーバーフロー判定部１１７は、タイル毎の図形記述情報がメモリ書込部１１６により書き込まれる際、メモリ１０２でオーバーフローが発生するかを判定する。オーバーフローとは、メモリ１０２の所定の記憶領域に全てデータが書き込まれ、これ以上データを書き込むことができない状態を言う。オーバーフロー判定部１１７は、各タイルの先頭アドレスに基づいて、メモリ１０２内のタイル単位のシーンデータ１０６に割り当てられたサイズを超えるか否かのオーバーフロー判定を行う。
【００４０】
オーバーフロー判定部１１７は、オーバーフローが発生すると判定した場合、メモリ書込部１１６に対し、オーバーフローが発生する場合には書き込み処理を停止するよう指示する。
【００４１】
また、オーバーフロー判定部１１７は、オーバーフローが発生すると判定した場合、退避／復帰部１１８に初期値を退避するよう指示する。初期値とは、オーバーフローが発生すると判定されたタイルの集計値（データサイズ）である。
【００４２】
また、オーバーフロー判定部１１７は、メモリ書込部１１６から、書き込み対象のタイル単位のシーンデータ１０６の領域が空いたことを通知されると、退避／復帰部１１８に書き込み処理の再開を通知する。
【００４３】
退避／復帰部１１８は、オーバーフロー判定部１１７により退避を指示された場合、オーバーフロー対象のタイルについて、集計部１１４により集計されたデータサイズの初期値を初期値保持部１１９に記憶する。初期値保持部１１９は、例えば初期値退避レジスタである。
【００４４】
退避／復帰部１１８は、書き込み処理が再開される場合には、初期値保持部１１９に退避した初期値を集計部１１４の集計値に復帰させる。書き込み処理の再開は、例えば、オーバーフロー判定部１１７により指示される。
【００４５】
初期値保持部１１９は、退避／復帰部１１８により所定のタイルの集計値（データサイズ）の初期値などを記憶する。
【００４６】
上述したようにして、各タイルに対応するシーンデータの記憶領域の先頭アドレスが決定された後に、切替制御部１１３は、再び、読み込み部１１１にシーンデータ１０５の読み込みを行うよう指示する。
【００４７】
切替制御部１１３は、再度読み込まれた図形記述情報について、判別処理で得られた判別結果を、メモリ書込部１１６に出力する。また、切替制御部１１３は、メモリ書込時も、タイルのデータサイズの集計値を更新するため、集計部１１４にも判別結果を出力する。
【００４８】
メモリ書込部１１６は、各タイルに対応して決定された先頭アドレスで示された記憶領域に、判別結果で示された図形記述情報を順次書き込む。メモリ書込部１１６は、オーバーフロー判定部１１７により指示を受けるまで、このようなメモリ書込み処理を行う。これにより、各タイルに対応するシーンデータを、メモリ１０２の連続した記憶領域に記憶することができる。
【００４９】
メモリ書込部１１６は、オーバーフロー判定部１１７によりオーバーフローが発生すると指示された場合、予め設定されたメモリサイズを超えないように図形記述情報の書き込みを行う。メモリ書込部１１６は、メモリサイズを超える場合は、書き込み処理を停止する。
【００５０】
メモリ書込部１１６は、シーンデータ読出部１３１によりシーンデータの読み出しが行われ、タイル単位のシーンデータ１０６の記憶領域に空きが出た場合、オーバーフロー判定部１１７に対してその旨を通知する。
【００５１】
メモリ書込部１１６は、オーバーフロー対象のタイルに対応するシーンデータを、復帰された初期値を用いてメモリ１０２に書き込む。
【００５２】
上述したようにメモリサイズを制限する理由は、ソート後のシーンデータのデータサイズは、タイル毎に記憶するため、シート前と比べてデータサイズが大きくなり、メモリのサイズが大きくなってしまうからである。
【００５３】
そこで、ソート後のシーンデータを記憶するメモリのサイズを制限したいという要求がある。実施例によれば、ソート後のシーンデータを記憶するメモリ１０２の所定領域に対してオーバーフロー判定を行うことで、メモリサイズを制限する場合であっても、適切な描画処理を行うことができるようになる。オーバーフロー判定処理や書き込み再開処理については、具体例を用いて後述する。
【００５４】
＜ソート部の構成＞
次に、ソート部の簡易的なハードウェアについて説明する。図４は、実施例におけるソート部１１０の構成の一例を示すブロック図である。図４に示す例では、図１に示す構成と同様のものは同じ符号を付す。以下、ソート部１１０について主に説明する。
【００５５】
図４に示す判別部１１２は、ソート制御部１２１と、図形番号カウンタ１２２と、図形番号保持部１２３と、適用特定部とを備える。また、適用特定部は、設定値保持部１２５と、追加検出部１２６とを備える。
【００５６】
ソート制御部１２１は、読込部１１１がメモリ１０２のシーンデータ１０５から読み出した図形記述情報の種類を判定する。ソート制御部１２１は、図形記述情報の種類に応じて、図形番号カウンタ１２２、図形番号保持部１２３、設定値保持部１２５および追加検出部１２６の動作を制御する。
【００５７】
図形番号カウンタ１２２は、ソート制御部１２１からの指示に応じて、読み込み済みのシーンデータにおける最新の図形インデックスに対応する図形番号を生成する。
【００５８】
図形番号保持部１２３は、例えばレジスタなどであり、ソート制御部１２１からの指示に応じて、図形番号カウンタ１２２で生成された図形番号を指定されたタイル番号に対応して保持する。
【００５９】
設定値保持部１２５は、例えばバッファなどであり、ソート制御部１２１から出力される各設定パラメータへの設定値を保持する。また、設定値保持部１２５は、新たな設定値を保持するごとに、設定値が保持された設定パラメータに対応して、図形番号カウンタ１２２で生成された図形番号を保持する。
【００６０】
追加検出部１２６は、ソート制御部１２１からの指示に応じて、図形番号保持部１２３の情報と、設定値保持部１２５の情報とを参照し、指定されたタイル番号の図形記述情報に追加する設定パラメータを検出する。
【００６１】
一方、各タイルの図形記述情報に含まれるべき図形インデックスは、ソート制御部１２１により、後述するようにしてシーンデータから判別される。
【００６２】
また、図４に示す集計部１１４は、サイズ加算部１２７と、集計値保持部１２８とを備える。集計値保持部１２８は、各タイル番号に対応して、タイル単位のシーンデータに含まれる図形記述情報のデータ長を示す集計値を保持する。
【００６３】
サイズ加算部１２７は、切替制御部１１３を介して取得した判別結果に含まれる図形記述情報の種類に対応するデータ長の増分を、指定されたタイル番号に対応する集計値に加算する。
【００６４】
なお、図形番号保持部１２３と集計値保持部１２８とを、タイル番号に対応する保持領域を備えたタイルバッファ１２９に統合してもよい。
【００６５】
図５は、タイルバッファ１２９に保持されるデータの一例を示す図である。図５に示す例では、各タイルを示すタイル番号に対応して、データサイズの集計値Ｄと、そのタイルに含まれるとされた最新の図形を示す図形番号ＮＴとが保持される。図５に示す例では、集計値Ｄおよび図形番号ＮＴに、タイル番号を示す添え字を付す。
【００６６】
図６は、設定値保持部１２５に保持されるデータの一例を示す図である。図６に示す例では、設定パラメータＡ，Ｂ，Ｃに対応して、それぞれへの最新の設定値Ａ−ｎａ，Ｂ−ｎｂ，Ｃ−ｎｃと、これらの設定値が有効になる図形番号ＮＰＡ，ＮＰＢ，ＮＰＣとが保持される。なお、図６に示す例では、各設定パラメータへの設定値を、シーンデータにおいて同種の設定値の中での出現順を示す番号(ｎａ，ｎｂ，ｎｃ)を付して区別する。また、設定パラメータの種類は、例に挙げられた数より多くても、少なくても構わない。
【００６７】
＜描画制御処理＞
次に、実施例における描画制御処理について説明する。図７は、実施例における描画制御処理の一例を示すフローチャートである。図７に示すステップＳ１０１で、判別部１１２や集計部１１４などは、シーンカウント処理を行う。シーンカウント処理とは、タイル毎の図形記述情報のデータサイズを集計する処理である。
【００６８】
ステップＳ１０２で、アドレス決定部１１５は、集計されたデータサイズに基づき、各領域の図形記述情報を書き込むメモリの先頭アドレスを、各タイルの図形記述情報がメモリ１０２の連続する記憶領域に記憶されるように決定する。
【００６９】
ステップＳ１０３で、メモリ書込部１１６、オーバーフロー判定部１１７などは、タイル毎の図形記述情報の書き込み処理を行う。このとき、メモリ書込部１１６は、メモリ１０２の所定領域以外の領域に書き込まないように制御される。次に、各処理の詳細な処理について説明する。
【００７０】
《判別処理》
次に、シーンカウント処理内の、図形記述情報の判別処理について説明する。図８は、判別処理（その１）の一例を示すフローチャートである。図９は、判別処理（その２）の一例を示すフローチャートである。
【００７１】
ステップＳ２０１で、ソート制御部１２１は、初期化として、図形番号カウンタ１２２の計数値と、タイルバッファ１２９および設定値保持部１２５の内容とをクリアする。
【００７２】
Ｓ２０２で、ソート制御部１２１は、読込部１１１によりメモリ１０２のシーンデータ１０５から読み込まれた図形記述情報を順次に受け取る。
【００７３】
ステップＳ２０３で、ソート制御部１２１は、取得した図形記述情報が設定パラメータの設定値であるか否かを判定する。設定パラメータの設定値であれば（ステップＳ２０３−ＹＥＳ）ステップＳ２０４に進み、設定パラメータの設定値でなければ（ステップＳ２０３−ＮＯ）ステップＳ２０６に進む。
【００７４】
ステップＳ２０４で、ソート制御部１２１は、この設定値と、このときの図形番号カウンタ１２２の計数値で示される図形番号とを設定値保持部１２５に保持する。
【００７５】
ステップＳ２０５で、ソート制御部１２１は、図形記述情報の読み込みが終了したかを判定する。読み込みが終了していれば（ステップＳ２０５−ＹＥＳ）判別処理を終了し、読み込みが終了していなければ（ステップＳ２０５−ＮＯ）ステップＳ２０２に戻る。
【００７６】
ステップＳ２０６で、ソート制御部１２１は、取得した図形記述情報が図形インデックスであるか否かを判定する。図形インデックスであれば（ステップＳ２０６−ＹＥＳ）ステップＳ２０７に進み、図形インデックスでなければ（ステップＳ２０６−ＮＯ）図９に示すステップＳ２１１に進む。
【００７７】
ステップＳ２０７で、ソート制御部１２１は、図形番号カウンタ１２２に保持される図形番号を更新する。
【００７８】
図９に示すステップＳ２１１で、ソート制御部１２１は、取得した図形記述情報がタイル番号であるか否かを判定する。タイル番号であれば（ステップＳ２１１−ＹＥＳ）ステップＳ２１２に進み、タイル番号でなければ（ステップＳ２１１−ＮＯ）判別処理を終了する。
【００７９】
ステップＳ２１２で、ソート制御部１２１は、取得したタイル番号で示されるタイルが、このタイル番号に先立って取得した図形インデックスの配置先であると判断する。この場合に、ソート制御部１２１は、上述した図形インデックスについての判別結果の出力に先立って、追加検出部１２６に、対応する図形に適用すべき設定パラメータの検出を指示する。追加検出部１２６は、ソート制御部１２１からの指示に応じて、タイルバッファ１２９の図形番号保持部１２３から上述したタイル番号に対応する図形番号ＮＴを読み出す。その後、追加検出部１２６は、各設定パラメータの中から上述したタイル番号のタイルの図形記述情報に追加するべき設定値があるものを検出する。
【００８０】
ステップＳ２１３で、追加検出部１２６は、設定パラメータの一つを選択的に示すパラメータ番号ｉを初期化する。
【００８１】
ステップＳ２１４で、追加検出部１２６は、パラメータ番号ｉの設定パラメータｉに対応して設定値保持部１２５に保持された図形番号ＮＰｉを読み出す。
【００８２】
ステップＳ２１５で、追加検出部１２６は、そして、この図形番号ＮＰｉが、上述したタイル番号に対応する図形番号ＮＴ以上であるか否かを判定する。条件を満たせば（ステップＳ２１５−ＹＥＳ）ステップＳ２１６に進み、条件を満たさなければ（ステップＳ２１５−ＮＯ）ステップＳ２１７に進む。
【００８３】
ステップＳ２１６で、追加検出部１２６は、設定パラメータｉを、タイル番号のタイルの図形記述情報に追加するべきであると判断する。この場合に、追加検出部１２６により、上述したタイル番号とこのパラメータ番号ｉとを含む判別結果が切替制御部１１３に通知される。
【００８４】
ステップＳ２１７で、追加検出部１２６は、全ての設定パラメータについて処理を行ったか否かを判定する。全設定パラメータの処理が終了していれば（ステップＳ２１７−ＹＥＳ）ステップＳ２１９に進み、全設定パラメータの処理が終了していなければ（ステップＳ２１７−ＮＯ）ステップＳ２１８に進む。
【００８５】
ステップＳ２１８で、追加検出部１２６は、パラメータ番号ｉを更新して、次の設定パラメータについての処理を行う。
【００８６】
なお、上述した説明では、個々の設定パラメータの識別にパラメータ番号ｉを用いたが、設定パラメータの識別子として設定パラメータ名を用いることもできる。
【００８７】
ステップＳ２１９で、ソート制御部１２１は、上述したタイル番号と最新の図形インデックスとを含む判別結果を切替制御部１１３に通知する。
【００８８】
ステップＳ２２０で、ソート制御部１２１は、タイルバッファ１２９の図形番号保持部１２３のタイル番号に対応する図形番号を更新する。ステップＳ２２０の処理後は、図８に示すステップＳ２０５に進む。
【００８９】
判別部１１２により、読込部１１１によって読み込まれた図形記述情報について上述した処理を行うことにより、シーンデータに含まれる個々の図形記述情報をタイル毎に分類することができる。
【００９０】
《切替制御》
次に、切替制御部１１３の処理について説明する。図１０は、切替制御処理の一例を示すフローチャートである。
【００９１】
ステップＳ３０１で、切替制御部１１３は、判別部１１２から判別結果を受け取る。ステップＳ３０２で、切替制御部１１３は、判別部１１２から判別結果を受け取るごとに、データサイズの集計中であるか否かを判定する。データサイズの集計中であれば（ステップＳ３０２−ＹＥＳ）、ステップＳ３０３に進み、データサイズの集計中でなければ（ステップＳ３０２−ＮＯ）、ステップＳ１０３に進む。
【００９２】
ステップＳ３０３で、切替制御部１１３は、シーンデータの長さを見積もる処理（Ｓ１０１、Ｓ１０２）が行われている間は、データサイズの集計中であると判定し、判別部から取得した判別結果をそのまま集計部１１４に出力する。
【００９３】
集計部１１４は、上述したシーンデータの長さを見積もる処理の際に、読込部１１１による読み込み処理および判別部１１２による判別処理と並行して動作する。
【００９４】
《集計処理》
次に、集計部１１４の処理について説明する。図１１は、集計処理の一例を示すフローチャートである。
【００９５】
ステップＳ４０１で、集計部１１４は、タイルバッファ１２９の集計値保持部１２８の内容をクリアして初期化する。
【００９６】
ステップＳ４０２で、集計部１１４は、切替制御部１１３を介して判別結果を受け取る。
【００９７】
ステップＳ４０３で、集計部１１４は、判別結果を取得する毎に、判別結果に初出のタイル番号が含まれているか否かを判定する。初出のタイル番号があれば（ステップＳ４０３−ＹＥＳ）ステップＳ４０４に進み、初出のタイル番号がなければ（ステップＳ４０３−ＮＯ）ステップＳ４０５に進む。
【００９８】
ステップＳ４０４で、サイズ加算部１２７は、この初出のタイル番号に対応して集計値保持部１２８にタイル開始命令のデータ長Ｌｔｓを加算する。
【００９９】
ステップＳ４０５で、サイズ加算部１２７は、上述した判別結果が設定パラメータの追加を示すものであるか否かを判定する。例えば、判別結果に設定パラメータの識別子が含まれていれば、設定パラメータの追加を示す。
【０１００】
設定パラメータの識別子が含まれていれば（ステップＳ４０５）ステップＳ４０６に進み、設定パラメータの識別子が含まれていなければ（ステップＳ４０５−ＮＯ）ステップＳ４０７に進む。
【０１０１】
ステップＳ４０６で、サイズ加算部１２７は、設定パラメータへの設定値のデータ長Ｌｐｖを、判別結果に含まれるタイル番号の集計値に加算する。なお、各設定パラメータのデータ長がそれぞれ異なる場合には、サイズ加算部１２７は、設定パラメータの識別子に対応して異なるデータ長Ｌｐｖを加算することができる。
【０１０２】
ステップＳ４０７で、サイズ加算部１２７は、上述した判別結果が図形インデックスの追加を示すものであるか否かを判定する。例えば、判別結果に図形インデックスが含まれている場合に、図形インデックスの追加を示す。
【０１０３】
図形インデックスが含まれていれば（ステップＳ４０７−ＹＥＳ）ステップＳ４０８に進み、図形インデックスが含まれていなければ（ステップＳ４０７−ＮＯ）ステップＳ４０９に進む。
【０１０４】
ステップＳ４０８で、サイズ加算部１２７は、図形インデックスのデータ長Ｌｉｎを、判別結果に含まれるタイル番号の集計値に加算する。
【０１０５】
ステップＳ４０９で、サイズ加算部１２７は、読込部１１１によるシーンデータの読み込みが完了したか否かを判定する。読み込みが完了していれば（ステップＳ４０９−ＹＥＳ）ステップＳ４１０に進み、読み込みが完了していなければ（ステップＳ４０９−ＮＯ）ステップＳ４０２に戻り、新たな判別結果に基づく集計処理を行う。なお、ステップ４０５、Ｓ４０６の設定パラメータについての処理と、ステップＳ４０７、Ｓ４０８の図形インデックスについての処理とは、順不同である。
【０１０６】
上述したステップＳ４０２〜ステップＳ４０９の処理は、シーンデータに含まれる全ての図形記述情報に対応する判別結果について、繰り返して行われる。
【０１０７】
ステップＳ４１０で、この集計処理が完了したときに、集計部１１４は、集計値保持部１２８に各タイル番号に対応して保持された集計値を、それぞれのタイルに対応するシーンデータの長さの見積もり結果として出力し、処理を終了する。
【０１０８】
≪シーンカウントによる更新の具体例≫
次に、シーンデータの長さの見積もり処理による、設定値保持部１２５、タイルバッファ１２９、図形番号保持部１２３の更新について図２のシーンデータを例にして説明する。説明を簡単にするため、図２の各データは、８ｂｙｔｅのデータとする。設定値保持部１２５は、バッファなどで実現でき、図形番号保持部１２３は、レジスタなどで実現できる。
【０１０９】
（１）初期化
図８のステップＳ２０１の処理により、設定値保持部１２５、タイルバッファ１２９、図形番号保持部１２３について、全て０で初期化される。図１２は、初期化後の各設定値の一例を示す図である。
【０１１０】
（２）図形入力前の設定値の処理
図１３は、Ｘ３入力後の各設定値の例を示す図である。図１３に示すように、該当する設定値保持部１２５のパラメータの設定値が更新される。図形は、未だ入力されていないので、図形番号は０のままとなる（Ｘ３まで終了）。
【０１１１】
（３）初めて図形が入力された場合の処理
図１４は、Ｘ６入力後の各設定値の一例を示す図である。図形１（三角形１）が入力された時は、図形番号保持部１２３が１に更新される。タイル位置が入力された時は、Ｔｉｌｅ０では図形が初めて入力されたので、設定値保持部１２５の各設定の図形番号と、タイルバッファ１２９の図形番号とが比較される（Ｓ２１５）。
【０１１２】
比較の結果、各設定値用の図形番号と各タイル用の図形番号とが同一であるため、設定値の更新が必要と判定される。したがって、図１４に示すように、Ｔｉｌｅ０のカウント値は、ＴｉｌｅＳｔａｒｔ命令（８ｂｙｔｅ）（Ｓ４０４）と、各設定の合計サイズ（８ｂｙｔｅ×３）（Ｓ４０６）と、図形を示すインデックス（８ｂｙｔｅ）の合計４０ｂｙｔｅ（０ｘ２８）（Ｓ４０８）とがタイルバッファ１２９に記憶される。Ｔｉｌｅ１も同様に更新される（Ｘ６まで終了）。
【０１１３】
（４）一度図形が入力された場合の処理
図１５は、Ｘ１０入力後の各設定値の一例を示す図である。図形２（三角形２）のタイル位置が入力された時、Ｔｉｌｅ０，Ｔｉｌｅ１については設定値保持部１２５の図形番号よりもＴｉｌｅ０，１の図形番号の方が大きいため、更新された設定は無いと判定される。よって、図形のインデックス（８ｂｙｔｅ）のみがカウントされる。Ｔｉｌｅ２については最初の図形のため、ＴｉｌｅＳｔａｒｔ命令と各設定の合計サイズと、図形インデックスの合計４０ｂｙｔｅが記憶される（Ｘ１０まで終了）。
【０１１４】
（５）設定値更新後に図形が入力された場合の処理
図１６は、Ｘ１３入力後の各設定値の一例を示す図である。設定Ｃ−１が入力された後に図形３（三角形３）が入力される。設定Ｃの図形番号とＴｉｌｅ２の図形番号が同一の為、設定Ｃの更新が必要と判定される。従って、設定Ｃ（８ｂｙｔｅ）と図形インデックス（８ｂｙｔｅ）との合計１６ｂｙｔｅがＴｉｌｅ２のカウント値に加算される（Ｘ１３まで終了）。
【０１１５】
（６）シーンカウント終了時
図１７は、シーンカウント終了時の各設定値の一例を示す図である。図１７に示すように各タイルでの集計値の処理が終了する。図１７に示す例では、タイル０では、「０ｘ３０」のデータサイズが見積もられ、タイル２では、「０ｘ３８」のデータサイズが見積もられる。
【０１１６】
《アドレス決定処理》
上述した見積もり結果（図１７参照）に基づいて、アドレス決定部１１５は、以下のようにして、各タイルに対応するシーンデータを記憶するために用いるメモリ１０２の記憶領域の先頭アドレスを決定する。
【０１１７】
図１８は、アドレス決定処理の一例を示すフローチャートである。図１８に示す例では、所定のベースアドレスを先頭アドレスとするメモリ１０２の記憶領域に、各タイルのシーンデータを連続的に記憶するように、各タイルに対応する記憶領域の先頭アドレスを決定する。
【０１１８】
ステップＳ５０１で、アドレス決定部１１５は、タイル番号ｊを初期化する。ステップＳ５０２で、アドレス決定部１１５は、上述したベースアドレスをタイル番号ｊの先頭アドレスＡＤｓ(ｊ)に設定する。
【０１１９】
ステップＳ５０３で、アドレス決定部１１５は、タイル番号ｊに対応して集計値保持部１２８に保持されたデータサイズの集計値Ｄｊを読み出す。
【０１２０】
ステップＳ５０４で、アドレス決定部１１５は、読み出した集計値Ｄｊを、タイル番号ｊの先頭アドレスＡＤｓ(ｊ)に加算して、タイル番号ｊ＋１の先頭アドレスＡＤｓ(ｊ＋１)を算出する。
【０１２１】
ステップＳ５０５で、アドレス決定部１１５は、タイル番号ｊを更新する。
【０１２２】
ステップＳ５０６で、アドレス決定部１１５は、このタイル番号ｊで示されるタイルが最後のタイルであるか否かを判定する。最後のタイルであれば（ステップＳ５０６−ＹＥＳ）決定処理を終了し、最後のタイルでなければ（ステップＳ５０６−ＮＯ）ステップＳ５０３に戻って、更新されたタイル番号ｊで示されるタイルに対応する先頭アドレスの算出処理を行う。
【０１２３】
≪アドレス決定処理の具体例≫
アドレス決定部１１５は、シーンカウント処理で求めたタイルバッファ１２９のサイズカウント値（集計値）を元に、タイル毎のシーンデータの先頭アドレスを算出する。算出方法は、Ｔｉｌｅ０のカウント値を読み出し、値を一時レジスタに退避し、次にＴｉｌｅ０のサイズカウントに０を書き込む。
【０１２４】
アドレス決定部１１５は、次のタイルのシーンデータサイズであるＴｉｌｅ１のカウント値を読み出し、値を一時レジスタに退避し、Ｔｉｌｅ０のカウント値をＴｉｌｅ１に書き込む。さらに、アドレス決定部１１５は、Ｔｉｌｅ２のサイズカウント値を読み出し、値を一時レジスタに退避し、Ｔｉｌｅ０とＴｉｌｅ１のカウント値の合計値をＴｉｌｅ２に書き込む。最後に、アドレス決定部１１５は、Ｔｉｌｅ０〜Ｔｉｌｅ２のカウント値の合計値をＴｉｌｅ３に書き込む。
【０１２５】
図１９は、アドレス決定後のタイルバッファの例を示す図である。図１９に示す例では、各タイルのカウント値は以下の通りである。
Ｔｉｌｅ１にＴｉｌｅ０の値を代入→０ｘ３０
Ｔｉｌｅ２にＴｉｌｅ０＋Ｔｉｌｅ１を代入→０ｘ３０＋０ｘ３０＝０ｘ６０
Ｔｉｌｅ３にＴｉｌｅ０＋Ｔｉｌｅ１＋Ｔｉｌｅ２を代入→０ｘ３０＋０ｘ３０＋０ｘ３８＝０ｘ９８
上述したように、アドレス決定後のタイルバッファ１２９の値は、各タイルの書き込み先頭アドレスを表す。なお、ベースアドレスは、「０ｘ２００００＿００００」であるとする。ベースアドレスは、書き込み先領域の先頭アドレスである。
【０１２６】
《書き込み処理》
次に、上述したようにして各タイルについて決定された先頭アドレスに基づいて、判別部１１２によってタイル毎に判別された図形記述情報をメモリ１０２に書き込む処理について説明する。書き込み処理では、メモリ１０２でオーバーフローが発生しないように制御しつつ、メモリ１０２への書き込みを行う。
【０１２７】
図２０は、書き込み処理（その１）の一例を示すフローチャートである。図２１は、書き込み処理（その２）の一例を示すフローチャートである。図２０、２１に示す処理は、タイル毎のシーンデータのソートが終了してから行われる。
【０１２８】
ステップＳ６０１で、オーバーフロー判定部１１７は、タイルバッファ１２９への書き込み回数ＷＮを１に設定する。ＷＮは、メモリ１０２への書き込み処理を停止するまでの書き込み回数でもある。例えば、１回目の書き込み停止までの書き込み回数ＷＮは１であり、２回目の書き込み停止までの書き込み回数ＷＮは２である。
【０１２９】
ステップＳ６０２で、オーバーフロー判定部１１７は、オーバーフローフラグをｆａｌｓｅに設定する。ステップＳ６０３で、判別部１１２は、設定値保持部１２５をクリアする。
【０１３０】
ステップＳ６０４で、判別部１１２は、読込部１１１により読み込まれた図形記述情報が、設定パラメータの設定値か、図形インデックスかを判定する。設定値であればステップＳ６０５に進み、図形インデックスであれば図２１に示すステップＳ６０６に進む。
【０１３１】
ステップＳ６０５で、判別部１１２は、どの設定パラメータのための設定値かを判定し、この設定値と、現在の図形番号とを設定値保持部１２５に保持する。
【０１３２】
ステップＳ６０６で、オーバーフロー判定部１１７は、図形インデックスが描画されるタイルのタイル番号をｋに設定し、タイルｋの集計値ＳＣ［ｋ］＜書き込み先領域サイズ×ＷＮであるか否かを判定する。ＳＣ［ｋ］は、タイルバッファ１２９のタイルｋの集計値を表す。書き込み先領域サイズは、メモリ１０２のタイル単位のシーンデータ１０６に割り当てられた領域のサイズを表す。
【０１３３】
この条件を満たせば（ステップＳ６０６−ＹＥＳ）ステップＳ６０７に進み、この条件を満たさなければ（ステップＳ６０６−ＮＯ）書き込みを停止させ、ステップＳ６２０に進む。
【０１３４】
ステップＳ６０７で、オーバーフロー判定部１１７は、ＳＣ［ｋ＋１］≧書き込み先領域サイズ×（ＷＮ−１）であるか否かを判定する。この条件を満たせば（ステップＳ６０７−ＹＥＳ）、ステップＳ６０８に進み、この条件を満たさなければ（ステップＳ６０７−ＮＯ）、書き込みを停止させ、ステップＳ６２０に進む。
【０１３５】
ステップＳ６０８で、オーバーフロー判定部１１７は、タイルｋにおける最初の図形か否かを判定する。最初の図形であれば（ステップＳ６０８−ＹＥＳ）ステップＳ６０９に進み、最初の図形でなければ（ステップＳ６０８−ＮＯ）ステップＳ６１１に進む。
【０１３６】
ステップＳ６０９で、オーバーフロー判定部１１７は、ＳＣ［ｋ＋１］＞書き込み先領域サイズ×ＷＮであるか否かを判定する。この条件を満たせば（ステップＳ６０９−ＹＥＳ）ステップＳ６１０に進み、この条件を満たさなければ（ステップＳ６０９−ＮＯ）ステップＳ６１１に進む。
【０１３７】
ステップＳ６１０で、オーバーフロー判定部１１７は、オーバーフローフラグをｔｒｕｅに設定し、初期値を退避するよう退避／復帰部１１８に指示する。退避／復帰部１１８は、この指示により、そのタイルの番号ｋと、ＳＣ［ｋ］とを初期値保持部１１９に退避する。退避されたタイル番号Ｒｋはｋになり、退避された集計値（初期値）ＳＣｋはＳＣ［ｋ］になる。
【０１３８】
ステップＳ６１１で、メモリ書込部１１６は、タイルｋは、初めて出てきたタイル番号かを判定する。初出のタイル番号であれば（ステップＳ６１１−ＹＥＳ）ステップＳ６１２に進み、初出のタイル番号でなければ（ステップＳ６１１−ＮＯ）ステップＳ６１３に進む。
【０１３９】
ステップＳ６１２で、メモリ書込部１１６は、メモリ１０２に、タイルｋの開始情報を書き込む。例えば、タイルの開始情報は、タイル開始命令の情報である。
【０１４０】
ステップＳ６１３で、メモリ書込部１１６は、設定値保持部１２５の所定の設定パラメータの図形番号ＮＰｉ≧タイルバッファ１２９のタイルｋの図形番号ＮＴであるか否かを判定する。ＮＰｉ≧ＮＴであれば（ステップＳ６１３−ＹＥＳ）ステップＳ６１４に進み、ＮＰｉ≧ＮＴでなければ（ステップＳ６１３−ＮＯ）ステップＳ６１５に進む。
【０１４１】
ステップＳ６１４で、メモリ書込部１１６は、設定パラメータの設定値をメモリ１０２に書き込む。このときの書き込みアドレスは、以下のアドレスとする。
アドレス（ＷｒｉｔｅＡｄｄｒｅｓｓ）＝ＳＣ［ｋ］−書き込み先領域サイズ×（ＷＮ−１）＋ベースアドレス  ・・・式（１）
ベースアドレスとは、メモリ１０２のタイル単位のシーンデータ１０６の領域の最初のアドレスである。
【０１４２】
ステップＳ６１５で、集計部１１４は、各設定値のサイズＬｐｖを、該当タイルｋのＳＣ［ｋ］に加算する。
【０１４３】
ステップＳ６１６で、判別部１１２は、全設定パラメータについて処理したかを判定する。全設定パラメータの処理が終了していれば（ステップＳ６１６−ＹＥＳ）ステップＳ６１７に進み、全設定パラメータの処理が終了していなければ（ステップＳ６１６−ＮＯ）ステップＳ６１３に戻り、他の設定パラメータで同様の処理を行う。
【０１４４】
ステップＳ６１７で、メモリ書込部１１６は、取得した図形インデックスをメモリ１０２に書き込む。このときの書き込みアドレスは、式（１）を用いて算出されたアドレスとする。
【０１４５】
ステップＳ６１８で、集計値１１４は、図形インデックスのサイズＬｉｎを、該当タイルｋのＳＣ［ｋ］に加算する。シーンデータの書き込み時には、タイルバッファ１２９の値は、該当タイルの書き込みが終わった図形記述情報の書き込みアドレスを表す。よって、集計部１１４は、Ｓ６１５や、Ｓ６１８でタイルバッファの値を更新する。
【０１４６】
ステップＳ６１９で、判別部１１２は、図形番号保持部１２３に保持された、該当タイルｋの図形番号を最新の値に更新する。
【０１４７】
ステップＳ６２０で、判別部１１２は、図形が描画されるタイル全てで処理をしたかを判定する。全タイルで処理が終了すれば（ステップＳ６２０−ＹＥＳ）図２０に示すステップＳ６２１に進み、全タイルで処理が終了していなければ（ステップＳ６２０−ＮＯ）ステップＳ６０６に戻り、他のタイルｋで処理される。例えばタイル番号ｋに１を加算して処理を行えばよい。
【０１４８】
ステップＳ６２１で、判別部１１２は、全シーンデータについて処理をしたかを判定する。全シーンデータで処理が終了すれば（ステップＳ６２１−ＹＥＳ）ステップＳ６２２に進み、全シーンデータが終了していなければ（ステップＳ６２１−ＮＯ）ステップＳ６０３に戻り、同様の処理を行う。
【０１４９】
ステップＳ６２２で、オーバーフロー判定部１１７は、オーバーフラグが「ｔｒｕｅ」であるかを判定する。オーバーフラグが「ｔｒｕｅ」であれば（ステップＳ６２２−ＹＥＳ）ステップＳ６２３に進み、オーバーフラグが「ｔｒｕｅ」でなければ（ステップＳ６２２−ＮＯ）ソート後のシーンデータの書き込みを全て終えたので、書き込み処理が終了される。
【０１５０】
ステップＳ６２３で、オーバーフロー判定部１１７は、初期値の復帰を退避／復帰部１１８に指示する。退避／復帰部１１８は、この指示を受けると、タイルバッファ１２９のタイル番号Ｒｋの集計値をＳＣｋに初期化する。また、オーバーフロー判定部１１７は、ＷＮに１を加算する。ステップＳ６２３の処理が終了すると、ステップＳ６０２に戻り、メモリ１０２に空きが出た場合に書き込み処理が再開される。
【０１５１】
《書き込み処理の具体例》
次に、書き込み処理の具体例について説明する。まず、書き込み処理の概要を説明する。図２２は、書き込み処理の概要を説明するための図である。図２２に示す例では、オーバーフローが発生するタイルを判定し、そのオーバーフロー発生対象のタイルの値を元の値（初期値）に戻すという処理を行う。
【０１５２】
図２２に示す１回目のタイルバッファ書き込み処理では、タイル２の途中までメモリ１０２に書き込むことができる。タイル２の途中以降は、メモリ１０２への書き込みがされないので、タイルバッファ１２９の更新をする必要がない。
【０１５３】
ここで、図２２に示す符号ａｒ１は、通常通り更新する領域を示し、符号ａｒ２は、タイルバッファ１２９の更新の必要がない領域を示す。図２２に示すシーンデータを書き出せる領域とは、タイル単位のシーンデータ１０６の記憶領域を表す。
【０１５４】
１回目のタイルバッファ書き込み処理終了後では、タイル３以降のタイルバッファ１２９の集計値は初期値のままである。
【０１５５】
図２２に示す２回目のタイルバッファ書き込み処理では、メモリ１０２の領域に空きが出た場合に、タイル２の途中からタイル４の途中までシーンデータをメモリ１０２に書き込むことができる。このとき、タイル２のタイルバッファ１２９の集計値と、図形番号とを初期値に戻す。
【０１５６】
２回目のタイルバッファ書き込み処理終了後では、タイル５のタイルバッファ１２９の集計値は初期値のままである。
【０１５７】
図２２に示す３回目のタイルバッファ書き込み処理では、メモリ１０２の領域に空きが出た場合に、タイル４の途中からシーンデータをメモリ１０２に書き込むことができる。このとき、タイル４のタイルバッファ１２９の集計値と、図形番号とを初期値に戻す。
【０１５８】
３回目のタイルバッファ書き込み処理終了後では、全てのタイルのタイルバッファの値が更新される。
【０１５９】
次に、書き込み処理時の各設定値の更新と、メモリ１０２の更新とについて、図２を用いて具体的に説明する。説明を簡単にするため、図２に示す各データは、全て８ｂｙｔｅのデータとする。
【０１６０】
（１）三角形１の書き込み処理
図２３は、三角形１の書き込み処理の終了時の各設定値の一例を示す図である。以降に示す例では、メモリ１０２の書き込み先領域サイズは、例えば０ｘ８０とし、また、ベースアドレスを０ｘ０７８０＿００００とする。
【０１６１】
今回の書き込み処理は、１回目のタイルバッファ書き込み処理なので、ＷｒｉｔｅＡｄｄｒｅｓｓ＝０ｘ０７８０＿００００のアドレスからソート後のシーンデータが書き込まれる。
【０１６２】
なお、タイル０、１において、三角形１は最初の図形なので、オーバーフロー判定が行われるが、オーバーフローは発生しないと判定される。
【０１６３】
（２）三角形２の書き込み処理
次に、三角形２の書き込みを行う。Ｔｉｌｅ２において、三角形２は最初の図形なので、オーバーフローの判定が行われる。オーバーフロー判定部１１７は、Ｔｉｌｅ２のタイルバッファ１２９を初めて更新する前に、次のＴｉｌｅ（Ｔｉｌｅ３）のタイルバッファ１２９の値（ＳＣ［３］）を参照する。
【０１６４】
オーバーフロー判定部１１７は、ＳＣ［３］の値が以下の条件を満たしていれば、書き込み先領域のオーバーフローが起きると判定する。
ＳＣ［ｋ＋１］＞書き込み先領域サイズ×ＷＮ
ＳＣ［ｋ＋１］：次タイルのタイルバッファの集計値
ＷＮ：タイルバッファ書き込み回数
図２４は、三角形２の書き込み処理時の各設定値の一例を示す図である。図２４に示すように、Ｔｉｌｅ２においては、０ｘ００００＿００９８（タイル３の集計値）＞０ｘ８０×１であるため、オーバーフローと判定される。
【０１６５】
オーバーフローと判定された場合、オーバーフローが発生した位置（Ｔｉｌｅ２という情報）とそのＴｉｌｅでのタイルバッファの初期値（ＳＣ［２］＝０ｘ００００_００６０）とが、初期値退避レジスタに退避される。初期値退避レジスタは、例えば初期値保持部１１９である。図形番号保持部１２３は、最新の図形インデックス「２」を保持する。
【０１６６】
（３）オーバーフロー時
書き込み時には、オーバーフロー判定部１１７は、タイルバッファ１２９の更新後のアドレスが、書き込み先領域内であるかを判定する。メモリ１０２のタイル単位のシーンデータ１０６の領域は（０ｘ００≦領域＜０ｘ８０）であり、Ｔｉｌｅ２の三角形２のアドレスは０ｘ８０になる。よって、メモリ１０２に、Ｔｉｌｅ２の三角形２の情報を書き込むことはできない。
【０１６７】
図２５は、オーバーフロー発生時の各設定値の一例を示す図である。図２５に示すように、予め用意されたメモリ１０２の領域全てに、シーンデータが書き込まれている。また、図２５に示すように、データを書き込むことができない場合は、タイルバッファ１２９の値は、更新されない。したがって、タイルバッファ１２９におけるＴｉｌｅ２の集計値は、０ｘ７８となり、集計値のカウントが停止される。
【０１６８】
（４）オーバーフロー後の設定値の更新
ソート部１１０は、三角形２以降もシーンデータを読み出して、書き込み処理を実行するが、メモリ１０２に空き領域が無いため、メモリ１０２への書き込みや、タイルバッファ１２９の更新を行わない。
【０１６９】
図２６は、オーバーフロー後の各設定値の一例を示す図である。図２６に示す例では、１回目のシーンデータ１０５の読み出し後の設定値保持部１２５や、タイルバッファ１２９の状態を示す。図２６に示すように、タイルバッファ１２９の集計値は、オーバーフロー時から更新されない。
【０１７０】
（５）２回目の書き込み処理の開始時
１回目の書き込み処理が終わったら、初期値退避レジスタに保存されている値を用いて、タイルバッファ１２９のＴｉｌｅ２の値を初期値に戻す。
【０１７１】
図２７は、２回目の書き込み処理開始時の各設定値の一例を示す図である。図２７に示すように、２回目の書き込み処理における開始位置を、初期値保持部１１９に保持しておくことで、既に書き込みの完了しているＴｉｌｅ０，１の処理を省略することができる。初期値保持部１１９は、処理開始位置を記憶するレジスタを有する。
【０１７２】
（６）２回目の書き込み処理実行
次に、２回目のソート処理、書き込み処理が実行される。１回目と同様にして、ソート部１１０は、シーンデータ１０５の最初から順番に読み出しを行う。２回目のソート時には、（０ｘ８０≦タイルバッファ内の集計値＜０ｘ１００）の条件を満たす場合のみ、ソート部１１０は、ソート後のシーンデータの書き込みを行う。書き込み時のアドレスは、式（１）により求められる。
【０１７３】
なお、この例では、タイル単位のシーンデータ１０６の記憶領域が２つの記憶領域を有し、２つの記憶領域を用いて順に、ソート後のシーンデータを書き込む例について説明するが、記憶領域は１つでも、３つ以上であってもよい。２回目の書き込み処理で用いる記憶領域のベースアドレスを０ｘ０８０００＿００００とする。また、タイル単位のシーンデータ１０６の記憶領域が１つの場合には、このベースアドレスは、０ｘ０７８０＿００００となる。
【０１７４】
ソート部１１０は、（０ｘ８０≦タイルバッファ内の集計値＜０ｘ１００）の場合に書き込みが行われる。よって、ＷｒｉｔｅＡｄｄｒｅｓｓの値が、（０ｘ０８００＿００００≦ＷｒｉｔｅＡｄｄｒｅｓｓ＜０ｘ０８００＿００８０）の範囲にあるときに書き込み処理が行われる。
【０１７５】
ソート部１１０は、２回目の書き込み処理で、三角形２を入力し、メモリ１０２に書き込んだとする。この場合、設定値保持部１２５と、タイルバッファ１２９の各設定値は図２８の通りとなる。
【０１７６】
図２８は、タイル２の三角形２の書き込み時における各設定値の一例を示す図である。図２８に示すように、タイルバッファ１２９のタイル２の集計値は、「０ｘ００００＿００８０」に更新され、図形番号も「２」に更新される。また、メモリ１０２には、０ｘ０８００＿００００のアドレスに、三角形２の図形記述情報が記憶される。なお、処理開始位置よりも前のタイルであるＴｉｌｅ０，１の更新は行われない。
【０１７７】
（７）２回目の書き込み終了時
その後、ソート部１１０は、オーバーフロー判定を行いながら、シーンデータ１０５が終了するまでデータを読み出す。この場合、２回目のオーバーフローの発生は判定されずに、ソート後のシーンデータが全てメモリ１０２に書き込まれる。
【０１７８】
図２９は、２回目の書き込み終了時の各設定値の一例を示す図である。図２９に示す例は、最終的な設定値保持部１２５と、タイルバッファ１２９との値を示す。また、図２９に示すメモリ１０２の２つ目の記憶領域を示す。
【０１７９】
以上、実施例によれば、個々のタイルに対応するタイル単位のシーンデータを、効率的なメモリアクセスが可能なように記憶させることができる。例えば、実施例によれば、複数回のソートを実行する事で、タイル単位のシーンデータを作成することができ、オーバーフロー判定を効率よく行うことで、メモリサイズを削減することができる。
【０１８０】
図３０は、実施例における描画処理装置のハードウェア構成の一例を示すブロック図である。図３０に示す描画処理装置は、制御部２０２、主記憶部２０４、補助記憶部２０６、通信部２０８、及び記録媒体Ｉ／Ｆ部２１０を少なくとも有する。各部は、バスを介して相互にデータ送受信可能に接続されている。
【０１８１】
制御部２０２は、コンピュータの中で、各装置の制御やデータの演算、加工を行うＣＰＵ（Central Processing Unit）である。また、制御部２０２は、主記憶部２０４や補助記憶部２０６に記憶されたプログラムを実行する演算装置であり、通信部２０８や各記憶部からデータを受け取り、演算、加工した上で、出力部や各記憶部に出力する。
【０１８２】
また、制御部２０２は、例えば補助記憶部２０６に記憶されるソートプログラムを実行することで、上述したソート機能を果たす。また、制御部２０２は、上述のソート部１１０によるソート処理を行うソート処理回路であってもよい。ソート処理回路は、例えば１又は複数の集積回路であり、ＡＳＩＣ（Application Specific Integrated Circuit）などでもよい。
【０１８３】
主記憶部２０４は、ＲＯＭ（Read Only Memory）やＲＡＭ（Random Access Memory）などであり、制御部２０２が実行する基本ソフトウェアであるＯＳやアプリケーションソフトウェアなどのプログラムやデータを記憶又は一時保存する記憶装置である。主記憶部２０４は、例えば上述したメモリ１０２であってもよい。
【０１８４】
補助記憶部２０６は、ＨＤＤ（Hard Disk Drive）などであり、アプリケーションソフトウェアなどに関連するデータを記憶する記憶装置である。また、補助記憶部２０６は、記録媒体２１２などから取得したソート処理プログラムや、シーンデータなどを記憶しておいてもよい。
【０１８５】
通信部２０８は、有線又は無線などのネットワークを通じて通信を行う。記録媒体Ｉ／Ｆ（インターフェース）部２１０は、ＵＳＢ（Universal Serial Bus）などのデータ伝送路を介して接続された記録媒体２１２（例えば、フラッシュメモリなど）と描画処理装置とのインターフェースである。
【０１８６】
また、記録媒体２１２に、所定のプログラムを格納し、この記録媒体２１２に格納されたプログラムは記録媒体Ｉ／Ｆ部２１０を介して描画処理装置にインストールされる。インストールされた所定のプログラムは、描画処理装置により実行可能となる。
【０１８７】
なお、上記描画処理装置の構成は、上記以外にも一般的なコンピュータの構成を有する。例えば、描画処理装置は、入力部や表示部を備えてもよい。
【０１８８】
以上、実施例について詳述したが、この実施例に限定されるものではなく、特許請求の範囲に記載された範囲内において、上記実施例以外にも種々の変形及び変更が可能である。
【０１８９】
また、実施例の描画処理装置は、ＰＣ（Personal Computer）、スマートフォンなどの携帯端末、タブレットＰＣ、カーナビゲーションシステム内の情報処理装置などに適用できる。
【０１９０】
なお、以上の実施例に関し、さらに以下の付記を開示する。
（付記１）
表示画面に含まれる図形の図形インデックス、又は該図形に適用される設定パラメータを含む図形記述情報を、前記表示画面が分割された領域毎に判別する判別部と、
判別された前記領域毎の図形記述情報のデータサイズを集計する集計部と、
集計された前記データサイズに基づき、各領域の図形記述情報を書き込むメモリの先頭アドレスを、前記各領域の図形記述情報が前記メモリの連続する記憶領域に記憶されるように決定するアドレス決定部と、
前記メモリでオーバーフローが発生するか否かを判定する判定部と、
前記オーバーフローが発生すると判定された場合、オーバーフロー発生対象の領域のデータサイズを記憶する初期値記憶部と、
前記オーバーフローが発生しないと判定された場合、決定された前記先頭アドレスから順に、前記領域毎の図形記述情報を前記メモリに書き込み、前記オーバーフローが発生すると判定された場合、書き込みを停止し、前記メモリに空きができたときに前記初期値記憶部に記憶されたデータサイズを用いて、前記オーバーフロー発生対象の領域から書き込み処理を再開する書き込み部と、
を備える描画処理装置。
（付記２）
前記判別部は、
前記書き込み部が前記書き込み処理を再開する場合、判別前の図形記述情報を用いて、再度判別処理を行う付記１記載の描画処理装置。
（付記３）
前記メモリは、複数のメモリ領域を有し、
前記書き込み部は、
前記複数のメモリ領域に対して順に前記図形記述情報を書き込む付記１又は２記載の描画処理装置。
（付記４）
前記書き込み部による書き込みアドレスは、
書き込み対象領域のデータサイズ−前記メモリのサイズ×（前記メモリへの書き込み処理を停止するまでの書き込み回数−１）＋前記メモリの先頭アドレス
である付記１乃至３いずれか一項に記載の描画処理装置。
（付記５）
表示画面に含まれる図形の図形インデックス、又は該図形に適用される設定パラメータを含む図形記述情報を、前記表示画面が分割された領域毎に判別し、
判別された前記領域毎の図形記述情報のデータサイズを集計し、
集計された前記データサイズに基づき、各領域の図形記述情報を書き込むメモリの先頭アドレスを、前記各領域の図形記述情報が前記メモリの連続する記憶領域に記憶されるように決定し、
前記メモリでオーバーフローが発生するか否かを判定し、
前記オーバーフローが発生すると判定された場合、オーバーフロー発生対象のタイルの先頭アドレスを記憶部に記憶し、
前記オーバーフローが発生しないと判定された場合、決定された前記先頭アドレスから順に、前記領域毎の図形記述情報を前記メモリに書き込み、前記オーバーフローが発生すると判定された場合、書き込みを停止し、前記メモリに空きができたときに前記記憶された先頭アドレスを用いて、前記オーバーフロー発生対象の領域から書き込み処理を再開する処理をコンピュータが実行する描画処理方法。
【符号の説明】
【０１９１】
１０２  メモリ
１１０  ソート部
１１２  判別部
１１４  集計部
１１５  アドレス決定部
１１７  オーバーフロー判定部
１１６  メモリ書込部
１１８  退避／復帰部
１１９  初期値保持部
２０２  制御部
２０４  主記憶部
【図１】
0005910310.tif 000002
【図２】
0005910310.tif 000003
【図３】
0005910310.tif 000004
【図４】
0005910310.tif 000005
【図５】
0005910310.tif 000006
【図６】
0005910310.tif 000007
【図７】
0005910310.tif 000008
【図８】
0005910310.tif 000009
【図９】
0005910310.tif 000010
【図１０】
0005910310.tif 000011
【図１１】
0005910310.tif 000012
【図１２】
0005910310.tif 000013
【図１３】
0005910310.tif 000014
【図１４】
0005910310.tif 000015
【図１５】
0005910310.tif 000016
【図１６】
0005910310.tif 000017
【図１７】
0005910310.tif 000018
【図１８】
0005910310.tif 000019
【図１９】
0005910310.tif 000020
【図２０】
0005910310.tif 000021
【図２１】
0005910310.tif 000022
【図２２】
0005910310.tif 000023
【図２３】
0005910310.tif 000024
【図２４】
0005910310.tif 000025
【図２５】
0005910310.tif 000026
【図２６】
0005910310.tif 000027
【図２７】
0005910310.tif 000028
【図２８】
0005910310.tif 000029
【図２９】
0005910310.tif 000030
【図３０】
0005910310.tif 000031