(57)【要約】【課題】複数の分割領域を結合して、シーンデータを再構築することにより、シーンデータのサイズを低減する方法を提供する。【解決手段】方法は、表示画面が分割された第１分割領域毎に、第１分割領域に少なくとも一部が配置される図形を示す図形インデックス、及び図形の描画に用いられる設定パラメータを有する第１シーンデータに基づいて、第１分割領域毎に、第１分割領域に対応するシーンデータサイズ、又は第１分割領域に配置される図形数を並べた表を作成し、表内の順番に並ぶ第１分割領域のシーンデータサイズの和、又は図形数の和が、基準値以下になるように、一の第１分割領域又は結合された複数の第１分割領域により形成される第２分割領域を生成し、第１シーンデータに基づいて、図形インデックス及び設定パラメータが第２分割領域毎に並べられた第２シーンデータを生成する。【選択図】図５
2015215847.tif 000002
【特許請求の範囲】
【請求項１】
表示画面が分割された第１分割領域毎に、前記第１分割領域に少なくとも一部が配置される図形を示す図形インデックス、及び図形の描画に用いられる設定パラメータを有する第１シーンデータに基づいて、前記第１分割領域毎に、前記第１分割領域に対応するシーンデータサイズ、又は前記第１分割領域に配置される図形数を、並べた表を作成し、
前記表内の順番に並ぶ前記第１分割領域のシーンデータサイズの和、又は図形数の和が、基準値以下になるように、一の前記第１分割領域又は結合された複数の前記第１分割領域により形成される第２分割領域を生成し、
前記第１シーンデータに基づいて、図形インデックス及び設定パラメータが前記第２分割領域毎に並べられた第２シーンデータを生成する方法。
【請求項２】
前記第１シーンデータは、図形インデックスによって示される図形が有する頂点数を有しており、前記第１シーンデータに基づいて、前記第１分割領域毎に、前記第１分割領域に対応するシーンデータサイズ、又は、前記第１分割領域に配置される図形を形成する頂点数、又は前記第１分割領域に配置される図形数を、並べた表を作成し、
前記表内の順番に並ぶ前記第１分割領域のシーンデータサイズの和、又は頂点数の和、又は図形数の和が、基準値以下になるように、一の前記第１分割領域又は結合された複数の前記第１分割領域により形成される第２分割領域を生成し、
前記第１シーンデータに基づいて、図形インデックス及び設定パラメータが前記第２分割領域毎に並べられた第２シーンデータを生成する請求項１に記載の方法。
【請求項３】
表示画面が分割された第１分割領域毎に、前記第１分割領域に少なくとも一部が配置される図形を示す図形インデックス、及び図形の描画に用いられる設定パラメータを有する第１シーンデータを読み込む読み込み部と、
前記第１シーンデータに基づいて、前記第１分割領域毎に、前記第１分割領域に対応するシーンデータサイズ、又は前記第１分割領域に配置される図形数を、並べた表を作成する第１処理部と、
前記表内の順番に並ぶ前記第１分割領域のシーンデータサイズの和、又は図形数の和が、基準値以下になるように、一の前記第１分割領域又は結合された複数の前記第１分割領域により形成される第２分割領域を生成する第２処理部と、
前記第１シーンデータに基づいて、図形インデックス及び設定パラメータが前記第２分割領域毎に並べられた第２シーンデータを生成する第３処理部と、
を備える回路。
【請求項４】
前記第１シーンデータは、図形インデックスによって示される図形が有する頂点数を有しており、
第１処理部は、第１シーンデータに基づいて、前記第１分割領域毎に、前記第１分割領域に対応するシーンデータサイズ、又は、前記第１分割領域に配置される図形を形成する頂点数、又は前記第１分割領域に配置される図形数を、並べた表を作成し、
第２処理部は、表内の順番に並ぶ前記第１分割領域のシーンデータサイズの和、又は頂点数の和、又は図形数の和が、基準値以下になるように、一の前記第１分割領域又は結合された複数の前記第１分割領域により形成される第２分割領域を生成し、
第３処理部は、前記第１シーンデータに基づいて、図形インデックス及び設定パラメータが前記第２分割領域毎に並べられた第２シーンデータを生成する請求項３に記載の回路。
【請求項５】
表示画面が分割された第１分割領域毎に、前記第１分割領域に少なくとも一部が配置される図形を示す図形インデックス、及び図形の描画に用いられる設定パラメータを有する第１シーンデータに基づいて、前記第１分割領域毎に、前記第１分割領域に対応するシーンデータサイズ、又は前記第１分割領域に配置される図形数を、並べた表を作成し、
前記表内の順番に並ぶ前記第１分割領域のシーンデータサイズの和、又は図形数の和が、基準値以下になるように、一の前記第１分割領域又は結合された複数の前記第１分割領域により形成される第２分割領域を生成し、
前記第１シーンデータに基づいて、図形インデックス及び設定パラメータが前記第２分割領域毎に並べられた第２シーンデータを生成する各ステップを、コンピュータに実行させるプログラム。
【請求項６】
前記第１シーンデータは、図形インデックスによって示される図形が有する頂点数を有しており、前記第１シーンデータに基づいて、前記第１分割領域毎に、前記第１分割領域に対応するシーンデータサイズ、又は、前記第１分割領域に配置される図形を形成する頂点数、又は前記第１分割領域に配置される図形数を、並べた表を作成し、
前記表内の順番に並ぶ前記第１分割領域のシーンデータサイズの和、又は頂点数の和、又は図形数の和が、基準値以下になるように、一の前記第１分割領域又は結合された複数の前記第１分割領域により形成される第２分割領域を生成し、
前記第１シーンデータに基づいて、図形インデックス及び設定パラメータが前記第２分割領域毎に並べられた第２シーンデータを生成する請求項５に記載のプログラム。
【請求項７】
表示画面が分割された第１分割領域毎に、前記第１分割領域に少なくとも一部が配置される図形を示す図形インデックス、及び図形の描画に用いられる設定パラメータを有する第１シーンデータに基づいて、前記第１分割領域毎に、前記第１分割領域に対応するシーンデータサイズ、又は前記第１分割領域に配置される図形数を、並べた表を作成し、
前記表内の順番に並ぶ前記第１分割領域のシーンデータサイズの和、又は図形数の和が、基準値以下になるように、一の前記第１分割領域又は結合された複数の前記第１分割領域により形成される第２分割領域を生成し、
前記第１シーンデータに基づいて、図形インデックス及び設定パラメータが前記第２分割領域毎に並べられた第２シーンデータを生成し、
前記第２シーンデータに基づいて、表示画面に図形を描画する描画方法。
【請求項８】
表示画面が分割された第１分割領域毎に、前記第１分割領域に少なくとも一部が配置される図形を示す図形インデックス、及び図形の描画に用いられる設定パラメータを有する第１シーンデータを読み込む読み込み部と、
前記第１シーンデータに基づいて、前記第１分割領域毎に、前記第１分割領域に対応するシーンデータサイズ、又は前記第１分割領域に配置される図形数を、並べた表を作成する第１処理部と、
前記表内の順番に並ぶ前記第１分割領域のシーンデータサイズの和、又は図形数の和が、基準値以下になるように、一の前記第１分割領域又は結合された複数の前記第１分割領域により形成される第２分割領域を生成する第２処理部と、
前記第１シーンデータに基づいて、図形インデックス及び設定パラメータが前記第２分割領域毎に並べられた第２シーンデータを生成する第３処理部と、
前記第２シーンデータに基づいて、表示画面に図形を描画する第４処理部と、
を備える描画装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、シーンデータを再構築する方法、回路、プログラム、描画方法及び描画装置システムに関する。
【背景技術】
【０００２】
三次元グラフィックスの描画を実現するハードウェア構成の一つとして、表示画面を複数の分割領域に分割し、この分割領域毎に三次元グラフィックスを描画することがある。
【０００３】
分割領域としては、例えば、表示画面を縦方向に複数に分割したスキャンライン、又は、表示画面を複数のタイル状に分割したタイルが挙げられる。
【０００４】
分割領域を採用した描画装置は、表示画面が分割された分割領域毎に、分割領域に少なくとも一部が配置される図形を示す図形インデックス、及び図形の描画に用いられる設定パラメータ等を有するシーンデータに基づいて描画する。具体的には、分割領域単位で描画に必要なシーンデータを読み込み、分割領域内部の描画に用いる図形情報等が作成されて、分割領域内部の描画が行われる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】国際公開第２００６／１３２１９４号
【特許文献２】国際公開第０１／０７５８０３号
【特許文献３】特開２００２−２０８０２６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
例えば、一つの図形が、複数の分割領域に跨って描画される場合があり、分割領域単位で描画に必要な部分が読み込まれた各シーンデータには、同じ図形を示す図形インデックスが含まれる。
【０００７】
また、分割領域単位で描画に必要な部分が読み込まれたシーンデータには、分割領域毎に同じ図形の描画に用いられる設定パラメータが含まれる場合があるので、分割領域毎のシーンデータに同じ設定パラメータが含まれることになる。
【０００８】
このように、シーンデータには重複する情報が含まれるので、シーンデータのサイズが大きくなり、シーンデータを記憶する記憶容量が大きくなるという問題があった。
【０００９】
本明細書では、複数の分割領域を結合して、シーンデータを再構築することにより、シーンデータのサイズを低減する方法を提供することを課題とする。
【００１０】
また、本明細書では、複数の分割領域を結合して、シーンデータを再構築することにより、シーンデータのサイズを低減する回路を提供することを課題とする。
【００１１】
また、本明細書では、複数の分割領域を結合して、シーンデータを再構築することにより、シーンデータのサイズを低減するプログラムを提供することを課題とする。
【００１２】
また、本明細書では、複数の分割領域を結合して、シーンデータを再構築することにより、シーンデータのサイズを低減し、再構築したシーンデータに基づいて、表示画面に図形を描画する描画方法を提供することを課題とする。
【００１３】
更に、本明細書では、複数の分割領域を結合して、シーンデータを再構築することにより、シーンデータのサイズを低減し、再構築したシーンデータに基づいて、表示画面に図形を描画する描画装置を提供することを課題とする。
【課題を解決するための手段】
【００１４】
本明細書に開示する方法の一形態によれば、表示画面が分割された第１分割領域毎に、上記第１分割領域に少なくとも一部が配置される図形を示す図形インデックス、及び図形の描画に用いられる設定パラメータを有する第１シーンデータに基づいて、上記第１分割領域毎に、上記第１分割領域に対応するシーンデータサイズ、又は上記第１分割領域に配置される図形数を、並べた表を作成し、上記表内の順番に並ぶ上記第１分割領域のシーンデータサイズの和、又は図形数の和が、基準値以下になるように、一の上記第１分割領域又は結合された複数の上記第１分割領域により形成される第２分割領域を生成し、上記第１シーンデータに基づいて、図形インデックス及び設定パラメータが上記第２分割領域毎に並べられた第２シーンデータを生成する。
【００１５】
本明細書に開示する回路の一形態によれば、表示画面が分割された第１分割領域毎に、上記第１分割領域に少なくとも一部が配置される図形を示す図形インデックス、及び図形の描画に用いられる設定パラメータを有する第１シーンデータを読み込む読み込み部と、上記第１シーンデータに基づいて、上記第１分割領域毎に、上記第１分割領域に対応するシーンデータサイズ、又は上記第１分割領域に配置される図形数を、並べた表を作成する第１処理部と、上記表内の順番に並ぶ上記第１分割領域のシーンデータサイズの和、又は図形数の和が、基準値以下になるように、一の上記第１分割領域又は結合された複数の上記第１分割領域により形成される第２分割領域を生成する第２処理部と、上記第１シーンデータに基づいて、図形インデックス及び設定パラメータが上記第２分割領域毎に並べられた第２シーンデータを生成する第３処理部と、を備える。
【００１６】
本明細書に開示するプログラムの一形態によれば、表示画面が分割された第１分割領域毎に、上記第１分割領域に少なくとも一部が配置される図形を示す図形インデックス、及び図形の描画に用いられる設定パラメータを有する第１シーンデータに基づいて、上記第１分割領域毎に、上記第１分割領域に対応するシーンデータサイズ、又は上記第１分割領域に配置される図形数を、並べた表を作成し、上記表内の順番に並ぶ上記第１分割領域のシーンデータサイズの和、又は図形数の和が、基準値以下になるように、一の上記第１分割領域又は結合された複数の上記第１分割領域により形成される第２分割領域を生成し、上記第１シーンデータに基づいて、図形インデックス及び設定パラメータが上記第２分割領域毎に並べられた第２シーンデータを生成する各ステップを、コンピュータに実行させる。
【００１７】
本明細書に開示する描画方法の一形態によれば、表示画面が分割された第１分割領域毎に、上記第１分割領域に少なくとも一部が配置される図形を示す図形インデックス、及び図形の描画に用いられる設定パラメータを有する第１シーンデータに基づいて、上記第１分割領域毎に、上記第１分割領域に対応するシーンデータサイズ、又は上記第１分割領域に配置される図形数を、並べた表を作成し、上記表内の順番に並ぶ上記第１分割領域のシーンデータサイズの和、又は図形数の和が、基準値以下になるように、一の上記第１分割領域又は結合された複数の上記第１分割領域により形成される第２分割領域を生成し、上記第１シーンデータに基づいて、図形インデックス及び設定パラメータが上記第２分割領域毎に並べられた第２シーンデータを生成し、上記第２シーンデータに基づいて、表示画面に図形を描画する。
【００１８】
本明細書に開示する描画装置の一形態によれば、表示画面が分割された第１分割領域毎に、上記第１分割領域に少なくとも一部が配置される図形を示す図形インデックス、及び図形の描画に用いられる設定パラメータを有する第１シーンデータを読み込む読み込み部と、上記第１シーンデータに基づいて、上記第１分割領域毎に、上記第１分割領域に対応するシーンデータサイズ、又は上記第１分割領域に配置される図形数を、並べた表を作成する第１処理部と、上記表内の順番に並ぶ上記第１分割領域のシーンデータサイズの和、又は図形数の和が、基準値以下になるように、一の上記第１分割領域又は結合された複数の上記第１分割領域により形成される第２分割領域を生成する第２処理部と、上記第１シーンデータに基づいて、図形インデックス及び設定パラメータが上記第２分割領域毎に並べられた第２シーンデータを生成する第３処理部と、上記第２シーンデータに基づいて、表示画面に図形を描画する第４処理部と、を備える。
【発明の効果】
【００１９】
上述した本明細書に開示する方法の一形態によれば、シーンデータのサイズを低減できる。
【００２０】
上述した本明細書に開示する回路の一形態によれば、シーンデータのサイズを低減できる。
【００２１】
上述した本明細書に開示するプログラムの一形態によれば、シーンデータのサイズを低減できる。
【００２２】
上述した本明細書に開示する描画方法の一形態によれば、サイズを低減したシーンデータに基づいて描画できる。
【００２３】
上述した本明細書に開示する描画装置の一形態によれば、サイズを低減したシーンデータに基づいて描画できる。
【００２４】
本発明の目的及び効果は、特に請求項において指摘される構成要素及び組み合わせを用いることによって認識され且つ得られるだろう。
【００２５】
前述の一般的な説明及び後述の詳細な説明の両方は、例示的及び説明的なものであり、特許請求の範囲に記載されている本発明を制限するものではない。
【図面の簡単な説明】
【００２６】
【図１】本明細書に開示する描画装置の第１実施形態を示す図である。
【図２】描画装置に入力される第１シーンデータを説明する図である。
【図３】スキャンラインに描画する各図形を示す図である。
【図４】スキャンラインごとの第１シーンデータを示す図である。
【図５】第１実施形態の描画装置の動作を説明するフローチャートである。
【図６】第１実施形態の描画装置の動作の要部を説明するフローチャート（その１）である。
【図７】表Ｔ１を説明する図である。
【図８】第１実施形態の描画装置の動作の要部を説明するフローチャート（その２）である。
【図９】表Ｔ２を説明する図である。
【図１０】第２シーンデータを説明する図である。
【図１１】第２シーンデータのスキャンラインに描画する各図形を示す図である。
【図１２】第２実施形態の描画装置の動作の要部を説明するフローチャート（その１）である。
【図１３】表Ｔ１を説明する図である。
【図１４】第２実施形態の描画装置の動作の要部を説明するフローチャート（その２）である。
【図１５】表Ｔ２を説明する図である。
【図１６】第３実施形態の描画装置の動作の要部を説明するフローチャート（その１）である。
【図１７】表Ｔ１を説明する図である。
【図１８】第３実施形態の描画装置の動作の要部を説明するフローチャート（その２）である。
【図１９】表Ｔ２を説明する図である。
【発明を実施するための形態】
【００２７】
以下、本明細書で開示する描画装置の好ましい第１実施形態を、図を参照して説明する。但し、本発明の技術範囲はそれらの実施形態に限定されず、特許請求の範囲に記載された発明とその均等物に及ぶものである。
【００２８】
図１は、本明細書に開示する描画装置の第１実施形態を示す図である。
【００２９】
本実施形態の描画装置１は、表示画面を複数の分割領域に分割し、この分割領域毎に三次元グラフィックスを描画する。
【００３０】
具体的には、描画装置１は、外部から第１シーンデータを入力し、複数の分割領域を結合して第１シーンデータを再構築した新たな第２シーンデータを生成し、第２シーンデータに基づいて、表示画面（図示せず）に図形を描画する。なお、第１シーンデータは、描画装置１が生成しても良い。
【００３１】
分割領域としては、例えば、表示画面を縦方向に複数に分割したスキャンライン、又は、表示画面を複数のタイル状に分割したタイルが挙げられる。本実施形態では、分割領域としてスキャンラインを用いるが、分割領域として、他の形状を有する領域を用いても良い。
【００３２】
まず、描画装置１に対して、第１シーンデータを生成して出力する第１シーンデータ生成部２について、以下に説明する。
【００３３】
第１シーンデータ生成部２は、個々の図形に着目した第１シーンデータ２１を生成し、描画装置１の記憶部２０に格納する。第１シーンデータ２１は、スキャンラインに少なくとも一部が配置される図形を示す図形インデックス、及び図形の描画に用いられる設定パラメータを有する。
【００３４】
図２は、描画装置に入力される第１シーンデータを説明する図である。
【００３５】
第１シーンデータ２１は各設定パラメータへの設定値と、描画する図形を示す図形インデックスと、図形が配置されるスキャンラインを示すスキャンライン識別子を含んでいる。各設定パラメータへの設定値と、描画する図形を示す図形インデックスと、図形が配置されるスキャンラインを示すスキャンライン識別子等の第１シーンデータ２１が有する情報を、以下、図形記述情報ともいう。図形記述情報は、描画命令ともいわれる。図形を描画するための座標、色等の図形情報は、図形記述情報と共に、シーンデータに含まれていても良い。又は、図形情報を、シーンデータとは別に、後述する描画装置１のレンダリング部３０へ入力しても良い。
【００３６】
以下、図２を参照して、第１シーンデータ２１について説明する。
【００３７】
図２に示す第１シーンデータ２１では、図形インデックスに先立って設定値を設定する設定パラメータが図形の描画に適用される。図２に示す例では、設定パラメータＡへの設定値を設定値０、設定パラメータＢへの設定値を設定値０、設定パラメータＣへの設定値を設定値０とした。図形０〜図形３には、設定パラメータＡ，Ｂ，Ｃとして、それぞれ設定値０が適用される。
【００３８】
図２に示す例では、図形インデックスとして、図形０〜図形３が示されている。そして、これらの図形インデックスに続いて読み込まれるスキャンライン識別子によって、個々の図形インデックスで示される図形が配置されるスキャンラインが特定される。図２に示す第１シーンデータ２１の例では、図形インデックス「図形０」に、スキャンライン識別子「スキャンライン０」が続いている。これは、「図形０」が、スキャンライン０に含まれることを示している。また、図形インデックス「図形１」に、スキャンライン識別子「スキャンライン２」及び「スキャンライン３」が続いている。これは、「図形１」が、スキャンライン２及びスキャンライン３に含まれることを示している。
【００３９】
図３は、スキャンラインに描画する各図形を示す図である。
【００４０】
図３は、スキャンライン０〜３に描画される図形０〜図形４を図示している。図形０は、スキャンライン０に含まれる。図形１は、スキャンライン２及びスキャンライン３に含まれる。図形２は、スキャンライン０及びスキャンライン１に含まれる。図形３は、スキャンライン１〜スキャンライン３に含まれる。図形４は、スキャンライン０〜スキャンライン３に含まれる。図３に示す例では、各図形は、三角形であるが、図形の形状は他の形状であっても良い。表示画面に描画される三次元グラフィックスは、複数の三角形（ポリゴン）が組み合わせて形成され得る。
【００４１】
図４は、スキャンラインごとの第１シーンデータを示す図である。
【００４２】
図４は、第１シーンデータ２１に含まれる各図形記述情報を、スキャンライン毎にソートした個別シーンデータ２１ａ〜２１ｄである。図４に示す各個別シーンデータ２１ａ〜２１ｄには、同一の設定パラメータが含まれている。また、複数のスキャンラインに跨って描画される図形の図形インデックスは、複数の個別シーンデータに含まれている。従って、個別シーンデータには重複する図形記述情報が含まれるので、シーンデータのサイズが大きくなり、シーンデータを記憶する記憶容量が大きくなる要因となり得る。
【００４３】
記憶部２０は、上述した第１シーンデータ２１を記憶する。また、記憶部２０は、第１シーンデータ２１が再構築された第２シーンデータ２２、及び第２シーンデータ２２のスキャンライン内部を描画する画素データである表示用画素データ２３を記憶する。
【００４４】
シーンデータ結合部１０は、記憶部２０が記憶する第１シーンデータ２１を読み出し、複数のスキャンラインを結合して第１シーンデータが再構築された新たな第２シーンデータを生成する。
【００４５】
シーンデータ結合部１０は、第１シーンデータ２１を読み込む読み込み部１１と、第１シーンデータ２１に基づいて、スキャンライン毎に、スキャンラインに配置される図形数を並べた表Ｔ１を作成する第１処理部１２を有する。また、シーンデータ結合部１０は、表Ｔ１内の順番に並ぶスキャンラインの図形数の和が、基準値以下になるように、一のスキャンライン又は結合された複数のスキャンラインにより形成される第２のスキャンラインを生成する第２処理部１３を有する。更に、シーンデータ結合部１０は、第１シーンデータ２１に基づいて、図形インデックス及び設定パラメータが第２のスキャンライン毎に並べられた第２シーンデータ２２を生成する第３処理部１４を有する。第３処理部１４は、生成した第２シーンデータ２２を記憶部２０に格納する。シーンデータ結合部１０の動作については、更に後述する。
【００４６】
レンダリング部３０は、シーンデータ読み出し部３１と、画素情報生成部３２と、表示判定部３３と、表示データ出力部３４を有する。シーンデータ読み出し部３１は、上述した第２のスキャンライン単位の第２シーンデータ２２を第２のスキャンライン毎に順次に読み出す。画素情報生成部３２は、読み出された第２のシーンデータ及び図形情報に基づいて、画素情報の生成及びテクスチャ情報に基づく演算処理を行う。画素情報生成部３２の処理で得られた画素データについて、表示判定部３３により、Ｚテストやステンシルテスト等の処理が行われる。これらのテスト処理により、個々の画素について表示するか否かが判定される。表示判定部３３によって表示対象と判定された画素データは、表示用画素データ２３として、表示データ出力部３４を介して記憶部２０に格納される。表示画面（図示せず）のスキャンラインには、表示用画素データ２３に対応する図形が描画される。
【００４７】
シーンデータ読み出し部３１は、第２のスキャンライン単位の第２シーンデータ２２を記憶するシーンデータキャッシュ３１ａを有する。シーンデータ読み出し部３１が読み出した第２シーンデータは、シーンデータキャッシュ３１ａに記憶される。
【００４８】
画素情報生成部３２は、図形毎の辺の式、座標及び色等の図形を描画するための図形情報（セットアップデータ）を記憶する図形キャッシュ３２ａを有する。図形キャッシュ３２ａの記憶容量は、第２のスキャンラインに含まれる最大の図形数に対応する。第２処理部１３の処理で用いられる上記基準値は、第２のスキャンライン単位に含まれる最大の図形数に対応するように決定される。例えば、図形キャッシュに記憶できる図形数が最大で３つだとすると、図形キャッシュ３２ａには、図形の辺の式及び色等の図形情報が３つの図形分が記録できる。図形情報は、式及び色の情報なので、図形キャッシュ３２ａの記憶容量は、数バイト程度の大きさである。図形キャッシュ３２ａの記憶容量が大きい程、一回で描画できるスキャンラインの数が増加するが、図形キャッシュ３２ａの記憶回路のコストが増加する。図形キャッシュ３２ａの記憶容量は、描画処理速度とコストとの兼ね合いで決定され得る。
【００４９】
また、画素情報生成部３２は、図形毎の頂点の座標及び色、テクスチャ座標等の図形を描画するための図形情報（セットアップデータ）を記憶する頂点キャッシュ３２ｂを有する。
【００５０】
本実施形態のシーンデータ結合部１０は、回路を用いて形成されているが、シーンデータ結合部１０の動作は、所定のプログラムをコンピュータが実行することにより実現しても良い。この所定のプログラムは、コンピュータ記録媒体に記録可能である。
【００５１】
次に、上述した描画装置１の動作を、図５に示すフローチャートを参照しながら、以下に説明する。
【００５２】
まず、ステップＳ１０において、シーンデータ結合部１０の読み込み部１１は、記憶部２０の第１シーンデータ２１を読み込む。
【００５３】
次に、図５のステップＳ１２において、シーンデータ結合部１０の第１処理部１２は、第１シーンデータ２１に基づいて、スキャンライン毎に、スキャンラインに配置される図形数を並べた表Ｔ１を作成する。ステップＳ１２の動作を、図６及び図７を参照して、以下に説明する。
【００５４】
まず、図６のステップＳ３０において、第１処理部１２は、スキャンラインに含まれる図形数を記憶する配列ＬｉｓｔＡ[ｎ]の初期化を行う。ここで、スキャンライン識別子を示す変数ｎは、０〜Ｎ−１（Ｎはスキャンラインの数）の整数である。この描画装置１の動作の説明では、説明を簡単にするため、Ｎ＝４とする。
【００５５】
次に、ステップＳ３２〜ステップＳ３６の間で、第１処理部１２は、第１シーンデータ２１が有する全ての図形に対して、その図形がどのスキャンラインに含まれるのかを調べて、スキャンライン毎に含まれる図形数を求める。
【００５６】
例えば、図形０に対しては、スキャンライン０に含まれるので、ステップＳ３４において、ＬｉｓｔＡ[０]＝ＬｉｓｔＡ[０]＋１という処理が行われる。また、図形１は、スキャンライン２及びスキャンライン３に含まれるので、ステップＳ３４において、ＬｉｓｔＡ[２]＝ＬｉｓｔＡ[２]＋１、ＬｉｓｔＡ[３]＝ＬｉｓｔＡ[３]＋１という処理が行われる。
【００５７】
第１処理部１２は、配列ＬｉｓｔＡ[ｎ]に基づいて、表Ｔ１を作成する。
【００５８】
図７は、表Ｔ１を説明する図である。
【００５９】
表Ｔ１は、スキャンライン０が４つの図形を含み、スキャンライン１が３つの図形を含み、スキャンライン２が３つの図形を含み、スキャンライン３が２つの図形を含むことを示す。
【００６０】
以上が、図５のステップＳ１２の説明である。
【００６１】
次に、図５のステップＳ１４において、シーンデータ結合部１０の第２処理部１３は、表Ｔ１内の順番に並ぶスキャンラインの図形数の和が、基準値以下になるように、一のスキャンライン又は結合された複数のスキャンラインを並べた表Ｔ２を作成する。ステップＳ１４の動作を、図８及び図９を参照して、以下に説明する。
【００６２】
まず、図８のステップＳ４０において、第２処理部１３は、スキャンライン識別子を示す変数ｎに対して、初期値ゼロを設定する。
【００６３】
次に、第２処理部１３は、全てのスキャンラインに対して、ステップＳ４２〜ステップＳ５８の間の処理を行う。
【００６４】
ステップＳ４４において、第２処理部１３は、変数ｉに対して、初期値１を設定し、スキャンラインの図形数を示すＤａｔａＳｉｚｅに対して、初期値ゼロを設定する。
【００６５】
次に、ステップＳ４６において、第２処理部１３は、スキャンラインの図形数を示すＤａｔａＳｉｚｅを求める。１回目の処理では、ｎ＝０、ｉ＝１であるので、ＤａｔａＳｉｚｅ＝ＬｉｓｔＡ[０]＝４となる。
【００６６】
次に、ステップＳ４７において、ＬｉｓｔＢ[ｎ]に対して、スキャンライン識別子ｎで示されるスキャンラインが、他のスキャンラインの結合先のスキャンラインであることを示す識別子０ｘＦＦＦＦＦＦＦＦが格納される。一方、後述するが、スキャンライン識別子ｎで示されるスキャンラインが、結合先のスキャンラインと結合される側のスキャンラインである場合には、ＬｉｓｔＢ[ｎ]には、結合先のスキャンライン識別子が格納される。１回目の処理では、ｎ＝０であるので、ＬｉｓｔＢ[０]＝０ｘＦＦＦＦＦＦＦＦとなる。
【００６７】
次に、第２処理部１３は、ステップＳ４８〜ステップＳ５４の間の処理を、ＤａｔａＳｉｚｅが基準値ＣＳＩＺＥを超えるまで繰り返す。ステップＳ４８の時点で、Ｄａｔａｓｉｚｅが基準値ＣＳＩＺＥを超えていれば、ステップＳ５６に進む。基準値ＣＳＩＺＥは、一のスキャンライン又は複数のスキャンラインが結合されて形成される第２のスキャンラインに含まれる最大の図形数に対応する。ここで、基準値ＣＳＩＺＥは８とした。
【００６８】
ステップＳ５０において、１回目の処理では、ｎ＝０、ｉ＝１、ＤａｔａＳｉｚｅ＝４であるので、ＬｉｓｔＢ[１]＝０、ｉ＝２となる。スキャンライン識別子ｎ＋１で示されるスキャンラインが、結合先のスキャンラインと結合される側のスキャンラインなので、ＬｉｓｔＢ[ｎ＋１]には、結合先のスキャンライン識別子が格納される。図９に示す表Ｔ２は、ＬｉｓｔＢ[ｎ]に基づいて形成される。
【００６９】
次に、ステップＳ５２において、第２処理部１３は、表Ｔ１内の順番に並ぶスキャンラインの図形数の和を求める。１回目の処理では、スキャンライン０の図形数を記憶するＤａｔａＳｉｚｅと、スキャンライン１の図形数との和を求めるので、ＤａｔａＳｉｚｅ＝Ｄａｔａｓｉｚｅ＋ＬｉｓｔＡ[１]＝７となる。
【００７０】
図９の表Ｔ１に示すように、スキャンライン０及びスキャンライン１の図形数の和は７となり、基準値ＣＳＩＺＥ以下であるので、まず、スキャンライン０及びスキャンライン１が結合されることになる。
【００７１】
図９に示す表Ｔ２は、表Ｔ１内の順番に並ぶスキャンラインの図形数の和が、基準値以下になるように、一のスキャンライン又は結合された複数のスキャンラインを並べたものである。
【００７２】
表Ｔ２において、スキャンライン０は、他のスキャンラインの結合先のスキャンラインであるであるので、０ｘＦＦＦＦＦＦＦＦが格納される。スキャンライン１は、スキャンライン０に結合される側のスキャンラインであるので、結合先のスキャンライン識別子０が格納される。
【００７３】
ここで、ＤａｔａＳｉｚｅ＝７≦ＣＳＩＺＥ＝８なので、ステップＳ５０に戻る。
【００７４】
次に、ステップＳ５０において、２回目の処理では、ｎ＝０、ｉ＝２であるので、ＬｉｓｔＢ[２]＝２、ｉ＝３となる。
【００７５】
次に、ステップＳ５２において、第２処理部１３は、表Ｔ１内の順番に並ぶスキャンラインの図形数の和を求める。２回目の処理では、スキャンライン０の図形数とスキャンライン１の図形数とのスキャンライン２の図形数と和を求めるので、ＤａｔａＳｉｚｅ＝ＤａｔａＳｉｚｅ＋ＬｉｓｔＡ[２]＝１０となる。図９の表Ｔ１に示すように、スキャンライン０〜スキャンライン２の図形数の和は１０となり、基準値ＣＳＩＺＥを超えるので、スキャンライン２は、ここでは、他のスキャンラインとは結合されない。従って、最初の第２のスキャンラインは、スキャンライン０及びスキャンライン１が結合されて構築されることになる。
【００７６】
ここで、ＤａｔａＳｉｚｅ＝１０＞ＣＳＩＺＥ＝８なので、ステップＳ５６に進む。
【００７７】
次に、ステップＳ５６において、第２処理部１３は、変数ｎと変数ｉとの和を求める。ここでは、ｎ＝０、ｉ＝２なので、ｎ＝０＋２＝２となる。
【００７８】
ここで、ｎ＝２＜４なので、スキャンラインＳ４４に戻る。
【００７９】
ステップＳ４４において、第２処理部１３は、変数ｉに対して、初期値１を設定し、スキャンラインの図形数を示すＤａｔａＳｉｚｅに対して、初期値ゼロを設定する。
【００８０】
次に、ステップＳ４６において、第２処理部１３は、スキャンラインの図形数を示すＤａｔａＳｉｚｅを求める。２回目の処理では、ｎ＝２、ｉ＝１であるので、ＤａｔａＳｉｚｅ＝ＬｉｓｔＡ[２]＝３となる。
【００８１】
次に、ステップＳ４７において、ＬｉｓｔＢ[ｎ]に対して、スキャンライン識別子ｎで示されるスキャンラインが、他のスキャンラインの結合先のスキャンラインであることを示す識別子０ｘＦＦＦＦＦＦＦＦが格納される。２回目の処理では、ｎ＝２であるので、ＬｉｓｔＢ[２]＝０ｘＦＦＦＦＦＦＦＦとなる。
【００８２】
次に、第２処理部１３は、ステップＳ４８〜ステップＳ５４の間の処理を、ＤａｔａＳｉｚｅが基準値ＣＳＩＺＥを超えるまで繰り返す。
【００８３】
ステップＳ５０において、１回目の処理では、ｎ＝２、ｉ＝１、ＤａｔａＳｉｚｅ＝３であるので、ＬｉｓｔＢ[３]＝２、ｉ＝２となる。
【００８４】
次に、ステップＳ５２において、第２処理部１３は、表Ｔ１内の順番に並ぶスキャンラインの図形数の和を求める。１回目の処理では、スキャンライン２の図形数とスキャンライン３の図形数との和を求めるので、ＤａｔａＳｉｚｅ＝ＤａｔａＳｉｚｅ＋ＬｉｓｔＡ[３]＝５となる。図９の表Ｔ１に示すように、スキャンライン２及びスキャンライン３の図形数の和は、５となり、基準値以下であるので、スキャンライン２及びスキャンライン３が結合されることになる。
【００８５】
表Ｔ２において、スキャンライン２は、他のスキャンラインの結合先のスキャンラインであるであるので、０ｘＦＦＦＦＦＦＦＦが格納される。スキャンライン３は、スキャンライン２に結合される側のスキャンラインであるので、結合先のスキャンライン識別子２が格納される。
【００８６】
ここで、全てのスキャンラインに対して処理が終了したので、動作が終了する。このようにして、図９に示す表Ｔ２が作成される。
【００８７】
以上が、図５のステップＳ１４の説明である。
【００８８】
次に、図５のステップＳ１６において、第２処理部１３は、図９に示す表Ｔ２に基づいて、一のスキャンライン又は結合された複数のスキャンラインにより形成される第２のスキャンラインを生成する。
【００８９】
図９の表Ｔ３は、結合された複数のスキャンラインにより形成される第２のスキャンライン０及び第２のスキャンライン１を示す。
【００９０】
第２のスキャンライン０は、スキャンライン０とスキャンライン１とが結合して形成される。第２のスキャンライン１は、スキャンライン２とスキャンライン３とが結合して形成される。
【００９１】
次に、図５のステップＳ１８において、シーンデータ結合部１０の第３処理部１４は、第１シーンデータ２１に基づいて、図形インデックス及び設定パラメータが第２のスキャンライン毎に並べられた第２シーンデータ２２を生成する。
【００９２】
図１０は、第２シーンデータを説明する図である。
【００９３】
まず、第３処理部１４は、第２のスキャンライン０及び第２のスキャンライン１に基づいて、個別の第２のシーンデータ２２ａ及び第２のシーンデータ２２ｂを生成する。個別の第２のシーンデータ２２ａは、スキャンライン０に対応する個別シーンデータ２１ａとスキャンライン１に対応する個別シーンデータ２１ｂとが結合されて形成される。重複される図形記述情報は１つにまとめられるので、シーンデータサイズが低減する。
【００９４】
同様に、個別の第２のシーンデータ２２ｂは、スキャンライン２に対応する個別シーンデータ２１ｃとスキャンライン３に対応する個別シーンデータ２１ｄとが結合されて形成される。
【００９５】
そして、第３処理部１４は、個別の第２のシーンデータ２２ａと第２のシーンデータ２２ｂを結合して、第２シーンデータ２２を生成する。
【００９６】
次に、図５のステップＳ２０において、描画装置１のレンダリング部３０は、第２シーンデータ２２に基づいて、表示画面（図示せず）に図形を描画する。
【００９７】
図１１は、第２シーンデータのスキャンラインに描画する各図形を示す図である。
【００９８】
第２シーンデータ２２に基づいて、第２のスキャンライン０に図形２を描画する時には、図形キャッシュ３２ａに図形２の図形情報が記憶される。第２のスキャンライン０には、図形２の全体が含まれるので、図形２の描画処理は、第２のスキャンライン０内部の描画処理で行うことができる。
【００９９】
このように、本実施形態の描画装置１によれば、図形キャッシュ３２ａに記憶された図形２の図形情報を用いて、図形２の全体を一度で描画することができる。従って、本実施形態の描画装置１によれば、図形の描画速度を向上することができる。
【０１００】
一方、図３に示すように、第１シーンデータ２１に基づいて図形２を描画する時には、図形２は、スキャンライン０及びスキャンライン１に跨って含まれていたので、図形２の描画処理は、スキャンライン０内部の描画処理と、スキャンライン１内部の描画処理とに分かれて行われていた。
【０１０１】
本実施形態の描画装置１では、図形４は、第２シーンデータ２２に基づいて、第２のスキャンライン０と第２のスキャンライン１との２つのスキャンライン内部の描画処理により描画される。一方、図３に示すように、第１シーンデータ２１に基づいて図形４を描画する時には、スキャンライン０〜スキャンライン３内部の４つの描画処理に分かれて行われていた。
【０１０２】
本実施形態の描画装置１では、図形１及び図形３についても、第２のスキャンラインに基づいて描画できるので、本実施形態の描画装置１によれば、図形の描画速度を向上することができる。
【０１０３】
上述した本実施形態の本実施形態の描画装置１によれば、スキャンラインが含む図形数に基づいて、複数のスキャンラインを結合して第２のスキャンラインを形成して、シーンデータを再構築するので、シーンデータのサイズを低減できる。
【０１０４】
なお、上述した実施形態では、第２のスキャンラインは、二つのスキャンラインが結合されて形成されていたが、第２のスキャンラインは、一つのスキャンラインに含まれる図形数によっては、一つのスキャンラインにより形成される場合もある。また、一つのスキャンラインに含まれる図形数によっては、第２のスキャンラインは、三つ以上のスキャンラインが結合して形成される場合もある。
【０１０５】
また、本実施形態の描画装置１によれば、図形キャッシュ３２ａの記憶容量に対応した図形数の図形の図形情報を用いて、スキャンライン内部を描画するので、処理速度が向上する。
【０１０６】
次に、上述した描画装置の第２実施形態及び第３実施形態を、図１２〜図１９を参照しながら以下に説明する。他の実施形態について特に説明しない点については、上述の第１実施形態に関して詳述した説明が適宜適用される。また、同一の構成要素には同一の符号を付してある。
【０１０７】
以下、本明細書で開示する描画装置の好ましい第２実施形態を、図１２〜図１５を参照して説明する。
【０１０８】
シーンデータサイズを用いて分割領域を再構築する
本実施形態の描画装置では、シーンデータ結合部１０の第１処理部１２及び第２処理部１３の動作が、上述した第１実施形態とは異なっている。
【０１０９】
具体的には、第１処理部１２は、第１シーンデータ２１に基づいて、スキャンライン毎に、スキャンラインに対応するシーンデータサイズを並べた表Ｔ１を作成する。また、第２処理部１３は、表Ｔ１内の順番に並ぶスキャンラインのシーンデータサイズの和が、基準値以下になるように、一のスキャンライン又は結合された複数のスキャンラインにより形成される第２のスキャンラインを生成する。
【０１１０】
レンダリング部３０のシーンデータキャッシュ３１ａの記憶容量は、第２のスキャンラインに含まれる最大のシーンデータサイズに対応する。第２処理部１３の処理で用いられる上記基準値は、第２のスキャンラインの最大のシーンデータサイズに対応するように決定される。シーンデータキャッシュ３１ａの記憶容量が大きい程、一回で描画できるスキャンラインの数が増加するが、シーンデータキャッシュ３１ａの記憶回路のコストが増加する。シーンデータキャッシュ３１ａの記憶容量は、描画処理速度とコストとの兼ね合いで決定され得る。
【０１１１】
図５のステップＳ１２における第１処理部１２の処理を、図１２及び図１３を参照して、以下に説明する。
【０１１２】
まず、図１２のステップＳ６０において、第１処理部１２は、変数ＰＣに初期値ゼロを設定する。
【０１１３】
次に、ステップＳ６２において、第１処理部１２は、スキャンラインに対応するシーンデータサイズを記憶する配列ＬｉｓｔＡ[ｎ]の初期化を行う。ここで、スキャンライン識別子を示す変数ｎは、０〜Ｎ−１（Ｎはスキャンラインの数）の整数である。この描画装置の動作の説明では、説明を簡単にするため、Ｎ＝４とする。
【０１１４】
次に、ステップＳ６４〜ステップＳ７２の間で、第１処理部１２は、第１シーンデータ２１が有する全ての図形記述情報に基づいて、スキャンライン毎にスキャンラインに対応するシーンデータサイズを求める。
【０１１５】
ステップＳ６６において、第１処理部１２は、図形記述情報が、設定パラメータであるか、又は、図形インデックスであるかを判断する。
【０１１６】
図形記述情報が、設定パラメータである場合には、ステップＳ６８に進む。ステップＳ６８において、第１処理部１２は、変数ＰＣと、一の設定パラメータのサイズｄとの和を求めて、変数ＰＣに代入する。ここで、一の設定パラメータのサイズｄを４バイトとする。そして、ステップＳ７２に進む。
【０１１７】
一方、図形記述情報が、図形インデックスである場合には、ステップＳ７０に進む。ステップＳ７０において、第１処理部１２は、配列ＬｉｓｔＡ[ｎ]と、一の図形インデックスのサイズｃとの和を求めて、配列ＬｉｓｔＡ[ｎ]に代入する。ここで、図形インデックスのサイズｃを４バイトとする。そして、ステップＳ７２に進む。
【０１１８】
ステップＳ６４〜ステップＳ７２の間の処理が終了した時点では、変数ＰＣは、３つの設定パラメータ分のサイズである１２バイトが代入される。また、配列ＬｉｓｔＡ[０]には、スキャンライン０に４つの図形インデックスが含まれるので、１６バイトが代入される。配列ＬｉｓｔＡ[１]には、スキャンライン１に３つの図形インデックスが含まれるので、１２バイトが代入される。配列ＬｉｓｔＡ[２]には、スキャンライン２に３つの図形インデックスが含まれるので、１２バイトが代入される。配列ＬｉｓｔＡ[３]には、スキャンライン３に２つの図形インデックスが含まれるので、８バイトが代入される。
【０１１９】
次に、第１処理部１２は、全てのスキャンラインに対して、ステップＳ７４〜ステップＳ７８の間の処理を繰り返す。
【０１２０】
ステップＳ７６において、第１処理部１２は、スキャンライン毎に配列ＬｉｓｔＡ[ｎ]と変数ＰＣとの和を求めて、配列ＬｉｓｔＡ[ｎ]に代入する。
【０１２１】
シーンデータ結合部１０の第１処理部１２は、配列ＬｉｓｔＡ[ｎ]に基づいて、表Ｔ１を作成する。
【０１２２】
図１３は、表Ｔ１を説明する図である。
【０１２３】
表Ｔ１は、スキャンライン０が２８バイトのシーンデータサイズを有し、スキャンライン１が２４バイトのシーンデータサイズを有し、スキャンライン２が２８バイトのシーンデータサイズを有し、スキャンライン３が２０バイトのシーンデータサイズを有すことを示す。
【０１２４】
以上が、図５のステップＳ１２の説明である。
【０１２５】
次に、図５のステップＳ１４における第２処理部１３の処理を、図１４及び図１５を参照して、以下に説明する。
【０１２６】
まず、図１４のステップＳ８０において、第２処理部１３は、スキャンライン識別子を示す変数ｎに対して、初期値ゼロを設定する。
【０１２７】
次に、第２処理部１３は、全てのスキャンラインに対して、ステップＳ８２〜ステップＳ９８の間の処理を行う。
【０１２８】
ステップＳ８４において、第２処理部１３は、変数ｉに対して、初期値１を設定し、スキャンラインに対応するシーンデータサイズを示すＤａｔａＳｉｚｅに対して、初期値ゼロを設定する。
【０１２９】
次に、ステップＳ８６において、第２処理部１３は、スキャンラインに対応するシーンデータサイズを示すＤａｔａＳｉｚｅを求める。１回目の処理では、ｎ＝０、ｉ＝１であるので、ＤａｔａＳｉｚｅ＝ＬｉｓｔＡ[０]＝２８となる。
【０１３０】
次に、ステップＳ８７において、ＬｉｓｔＢ[ｎ]に対して、スキャンライン識別子ｎで示されるスキャンラインが、他のスキャンラインの結合先のスキャンラインであることを示す識別子０ｘＦＦＦＦＦＦＦＦが格納される。一方、後述するが、スキャンライン識別子ｎで示されるスキャンラインが、結合先のスキャンラインと結合される側のスキャンラインである場合には、ＬｉｓｔＢ[ｎ]には、結合先のスキャンライン識別子が格納される。１回目の処理では、ｎ＝０であるので、ＬｉｓｔＢ[０]＝０ｘＦＦＦＦＦＦＦＦとなる。
【０１３１】
次に、第２処理部１３は、ステップＳ８８〜ステップＳ９４の間の処理を、ＤａｔａＳｉｚｅが基準値ＣＳＩＺＥを超えるまで繰り返す。ステップＳ８８の時点で、Ｄａｔａｓｉｚｅが基準値ＣＳＩＺＥを超えていれば、ステップＳ９６に進む。基準値ＣＳＩＺＥは、一のスキャンライン又は複数のスキャンラインが結合されて形成される第２のスキャンラインに含まれる最大のシーンデータサイズに対応する。ここで、基準値ＣＳＩＺＥは６４バイトとした。
【０１３２】
ステップＳ９０において、１回目の処理では、ｎ＝０、ｉ＝１、ＤａｔａＳｉｚｅ＝２８であるので、ＬｉｓｔＢ[１]＝０、ｉ＝２となる。スキャンライン識別子ｎ＋１で示されるスキャンラインが、結合先のスキャンラインと結合される側のスキャンラインなので、ＬｉｓｔＢ[ｎ＋１]には、結合先のスキャンライン識別子が格納される。図１５に示す表Ｔ２は、ＬｉｓｔＢ[ｎ]に基づいて形成される。
【０１３３】
次に、ステップＳ９２において、第２処理部１３は、表Ｔ１内の順番に並ぶスキャンラインに対応するシーンデータサイズを求める。１回目の処理では、スキャンライン０に対応するシーンデータサイズを記憶するＤａｔａＳｉｚｅと、スキャンライン１に対応するシーンデータサイズとの和を求めるので、Ｄａｔａｓｉｚｅ＝ＤａｔａＳｉｚｅ＋ＬｉｓｔＡ[１]＝５２となる。
【０１３４】
図１５の表Ｔ１に示すように、スキャンライン０及びスキャンライン１に対応するシーンデータサイズの和は５２となり、基準値ＣＳＩＺＥ以下であるので、まず、スキャンライン０及びスキャンライン１が結合されることになる。
【０１３５】
図１５に示す表Ｔ２は、表Ｔ１内の順番に並ぶスキャンラインに対応するシーンデータサイズの和が、基準値以下になるように、一のスキャンライン又は結合された複数のスキャンラインを並べたものである。
【０１３６】
表Ｔ２において、スキャンライン０は、他のスキャンラインの結合先のスキャンラインであるであるので、０ｘＦＦＦＦＦＦＦＦが格納される。スキャンライン１は、スキャンライン０に結合される側のスキャンラインであるので、結合先のスキャンライン識別子０が格納される。
【０１３７】
ここで、ＤａｔａＳｉｚｅ＝５２≦ＣＳＩＺＥ＝６４なので、ステップＳ９０に戻る。
【０１３８】
次に、ステップＳ９０において、２回目の処理では、ｎ＝０、ｉ＝２であるので、ＬｉｓｔＢ[２]＝２、ｉ＝３となる。
【０１３９】
次に、ステップＳ９２において、第２処理部１３は、表Ｔ１内の順番に並ぶスキャンラインの図形数の和を求める。２回目の処理では、スキャンライン０に対応するシーンデータサイズとスキャンライン１に対応するシーンデータサイズとのスキャンライン２に対応するシーンデータサイズと和を求めるので、ＤａｔａＳｉｚｅ＝ＤａｔａＳｉｚｅ＋ＬｉｓｔＡ[２]＝７６となる。図１５の表Ｔ１に示すように、スキャンライン０〜スキャンライン２に対応するシーンデータサイズの和は７６となり、基準値ＣＳＩＺＥを超えるので、スキャンライン２は、ここでは、他のスキャンラインとは結合されない。従って、最初の第２のスキャンラインは、スキャンライン０及びスキャンライン１が結合されて構築されることになる。
【０１４０】
ここで、ＤａｔａＳｉｚｅ＝７６＞ＣＳＩＺＥ＝６４なので、ステップＳ９６に進む。
【０１４１】
次に、ステップＳ９６において、第２処理部１３は、変数ｎと変数ｉとの和を求める。ここでは、ｎ＝０、ｉ＝２なので、ｎ＝０＋２＝２となる。
【０１４２】
ここで、ｎ＝２＜４なので、スキャンラインＳ８４に戻る。
【０１４３】
ステップＳ８４において、第２処理部１３は、変数ｉに対して、初期値１を設定し、スキャンラインに対応するシーンデータサイズを示すＤａｔａＳｉｚｅに対して、初期値ゼロを設定する。
【０１４４】
次に、ステップＳ８６において、第２処理部１３は、スキャンラインの図形数を示すＤａｔａＳｉｚｅを求める。２回目の処理では、ｎ＝２、ｉ＝１であるので、ＤａｔａＳｉｚｅ＝ＬｉｓｔＡ[２]＝３となる。
【０１４５】
次に、ステップＳ８７において、ＬｉｓｔＢ[ｎ]に対して、スキャンライン識別子ｎで示されるスキャンラインが、他のスキャンラインの結合先のスキャンラインであることを示す識別子０ｘＦＦＦＦＦＦＦＦが格納される。２回目の処理では、ｎ＝２であるので、ＬｉｓｔＢ[２]＝０ｘＦＦＦＦＦＦＦＦとなる。
【０１４６】
次に、第２処理部１３は、ステップＳ８８〜ステップＳ９４の間の処理を、ＤａｔａＳｉｚｅが基準値ＣＳＩＺＥを超えるまで繰り返す。
【０１４７】
ステップＳ９０において、１回目の処理では、ｎ＝２、ｉ＝１、Ｄａｔａｓｉｚｅ＝３であるので、ＬｉｓｔＢ[３]＝２、ｉ＝２となる。
【０１４８】
次に、ステップＳ９２において、第２処理部１３は、表Ｔ１内の順番に並ぶスキャンラインに対応するシーンデータサイズの和を求める。１回目の処理では、スキャンライン２に対応するシーンデータサイズとスキャンライン３に対応するシーンデータサイズとの和を求めるので、ＤａｔａＳｉｚｅ＝ＤａｔａＳｉｚｅ＋ＬｉｓｔＡ[３]＝５４となる。図１５の表Ｔ１に示すように、スキャンライン２及びスキャンライン３に対応するシーンデータサイズの和の和は、５４となり、基準値以下であるので、スキャンライン２及びスキャンライン３が結合されることになる。
【０１４９】
表Ｔ２において、スキャンライン２は、他のスキャンラインの結合先のスキャンラインであるので、０ｘＦＦＦＦＦＦＦＦが格納される。スキャンライン３は、スキャンライン２に結合される側のスキャンラインであるので、結合先のスキャンライン識別子２が格納される。
【０１５０】
ここで、全てのスキャンラインに対して処理が終了したので、動作が終了する。このようにして、図１５に示す表Ｔ２が作成される。
【０１５１】
以上が、図５のステップＳ１４の説明である。
【０１５２】
上述した本実施形態の描画装置によれば、スキャンラインに対応するシーンデータサイズに基づいて、複数のスキャンラインを結合して第２のスキャンラインを形成して、シーンデータを再構築するので、シーンデータのサイズを低減できる。
【０１５３】
また、本実施形態の描画装置によれば、シーンデータキャッシュ３１ａの記憶容量に対応したシーンデータサイズの図形の図形情報を用いて、スキャンライン内部を描画するので、処理速度が向上する。
【０１５４】
以下、本明細書で開示する描画装置の好ましい第３実施形態を、図１６〜図１９を参照して説明する。
【０１５５】
本実施形態の描画装置では、シーンデータ結合部１０の第１処理部１２及び第２処理部１３の動作が、上述した第１実施形態とは異なっている。また、第１シーンデータ２１は、図形インデックスによって示される図形が有する頂点数を有している。図形インデックスによって示される図形が有する頂点数は、個別の図形記述情報として第１シーンデータ２１に含まれていても良い。または、第１シーンデータ２１が有する図形インデックスに対して、頂点数が対応するようにして、図形インデックスが、頂点数の情報を含むようにしても良い。具体的には、図形インデックスが三角形であれば、頂点数が３であり、図形インデックスが四角形であれば、頂点数が４となる。
【０１５６】
第１処理部１２は、第１シーンデータ２１に基づいて、スキャンライン毎に、スキャンラインに配置される図形を形成する頂点数を並べた表Ｔ１を作成する。また、第２処理部１３は、表Ｔ１内の順番に並ぶスキャンラインの頂点数の和が、基準値以下になるように、一のスキャンライン又は結合された複数のスキャンラインにより形成される第２のスキャンラインを生成する。
【０１５７】
レンダリング部３０の頂点キャッシュ３２ｂの記憶容量は、第２のスキャンラインに含まれる最大の図形の頂点数に対応する。第２処理部１３の処理で用いられる上記基準値は、第２のスキャンラインに含まれる最大の頂点数に対応するように決定される。例えば、頂点キャッシュに記憶できる頂点数が最大で９つだとすると、頂点キャッシュ３２ｂは、頂点毎の座標及び色、テクスチャ座標を９つ分記録できるということになる。図形情報は、図形毎の頂点の座標及び色、テクスチャ座標等の情報なので、頂点キャッシュ３２ｂの記憶容量は、数バイト程度の大きさである。頂点キャッシュ３２ｂの記憶容量が大きい程、一回で描画できるスキャンラインの結合数が増加するが、頂点キャッシュ３２ｂの記憶回路のコストが増加する。頂点キャッシュ３２ｂの記憶容量は、描画処理速度とコストとの兼ね合いで決定され得る。
【０１５８】
図５のステップＳ１２における第１処理部１２の処理を、図１２及び図１３を参照して、以下に説明する。
【０１５９】
まず、図１６のステップＳ１００において、第１処理部１２は、スキャンラインに配置される図形を形成する頂点数を記憶する配列ＬｉｓｔＡ[ｎ]の初期化を行う。ここで、スキャンライン識別子を示す変数ｎは、０〜Ｎ−１（Ｎはスキャンラインの数）の整数である。この描画装置の動作の説明では、説明を簡単にするため、Ｎ＝４とする。
【０１６０】
次に、ステップＳ１０２〜ステップＳ１０６の間で、第１処理部１２は、第１シーンデータ２１が有する全ての図形に対して、その図形がどのスキャンラインに含まれるのかを調べて、スキャンライン毎に配置される図形を形成する頂点数を求める。
【０１６１】
ステップＳ１０４では、スキャンラインｎに配置される一の図形に対して、配列ＬｉｓｔＡ[ｎ]と一の図形の頂点数ａとの和が求められて、配列ＬｉｓｔＡ[ｎ]に代入される。本実施形態では、全ての図形は三角形なので、頂点数ａは３である。
【０１６２】
例えば、スキャンライン０に配置される図形は、図形０と、図形２と、図形３と、図形４の４つである。全て三角形であるので、一の図形の頂点数は３である。スキャンライン０に配置される図形を形成する頂点数は、４×３＝１２となる。同様に計算して、スキャンライン１に配置される図形を形成する頂点数は９であり、スキャンライン２に配置される図形を形成する頂点数は９であり、スキャンライン３に配置される図形を形成する頂点数は６である。
【０１６３】
第１処理部１２は、配列ＬｉｓｔＡ[ｎ]に基づいて、表Ｔ１を作成する。
【０１６４】
図１７は、表Ｔ１を説明する図である。
【０１６５】
表Ｔ１は、スキャンライン０が１２の頂点数を含み、スキャンライン１が９の頂点数を含み、スキャンライン２が９の頂点数を含み、スキャンライン３が６の頂点数を含むことを示す。
【０１６６】
以上が、図５のステップＳ１２の説明である。
【０１６７】
次に、図５のステップＳ１４における第２処理部１３の処理を、図１８及び図１９を参照して、以下に説明する。
【０１６８】
まず、図１８のステップＳ１１０において、第２処理部１３は、スキャンライン識別子を示す変数ｎに対して、初期値ゼロを設定する。
【０１６９】
次に、第２処理部１３は、全てのスキャンラインに対して、ステップＳ１１２〜ステップＳ１２８の間の処理を行う。
【０１７０】
ステップＳ１１４において、第２処理部１３は、変数ｉに対して、初期値１を設定し、スキャンラインに配置される図形を形成する頂点数を示すＤａｔａＳｉｚｅに対して、初期値ゼロを設定する。
【０１７１】
次に、ステップＳ１１６において、第２処理部１３は、スキャンラインに配置される図形を形成する頂点数を示すＤａｔａＳｉｚｅを求める。１回目の処理では、ｎ＝０、ｉ＝１であるので、ＤａｔａＳｉｚｅ＝ＬｉｓｔＡ[０]＝１２となる。
【０１７２】
次に、ステップＳ１１７において、ＬｉｓｔＢ[ｎ]に対して、スキャンライン識別子ｎで示されるスキャンラインが、他のスキャンラインの結合先のスキャンラインであることを示す識別子０ｘＦＦＦＦＦＦＦＦが格納される。一方、後述するが、スキャンライン識別子ｎで示されるスキャンラインが、結合先のスキャンラインと結合される側のスキャンラインである場合には、ＬｉｓｔＢ[ｎ]には、結合先のスキャンライン識別子が格納される。１回目の処理では、ｎ＝０であるので、ＬｉｓｔＢ[０]＝０ｘＦＦＦＦＦＦＦＦとなる。
【０１７３】
次に、第２処理部１３は、ステップＳ１１８〜ステップＳ１２４の間の処理を、ＤａｔａＳｉｚｅが基準値ＣＳＩＺＥを超えるまで繰り返す。ステップＳ１１８の時点で、ＤａｔａＳｉｚｅが基準値ＣＳＩＺＥを超えていれば、ステップＳ１２６に進む。基準値ＣＳＩＺＥは、一のスキャンライン又は複数のスキャンラインが結合されて形成される第２のスキャンラインに含まれる最大の図形を形成する頂点数に対応する。ここで、基準値ＣＳＩＺＥは２４とした。
【０１７４】
ステップＳ１２０において、１回目の処理では、ｎ＝０、ｉ＝１、ＤａｔａＳｉｚｅ＝１２であるので、ＬｉｓｔＢ[１]＝０、ｉ＝２となる。スキャンライン識別子ｎ＋１で示されるスキャンラインが、結合先のスキャンラインと結合される側のスキャンラインなので、ＬｉｓｔＢ[ｎ＋１]には、結合先のスキャンライン識別子が格納される。図１９に示す表Ｔ２は、ＬｉｓｔＢ[ｎ]に基づいて形成される。
【０１７５】
次に、ステップＳ１２２において、第２処理部１３は、表Ｔ１内の順番に並ぶスキャンラインに配置される図形を形成する頂点数の和を求める。１回目の処理では、スキャンライン０に配置される図形を形成する頂点数を記憶するＤａｔａｓｉｚｅと、スキャンライン１に配置される図形を形成する頂点数との和を求めるので、ＤａｔａＳｉｚｅ＝Ｄａｔａｓｉｚｅ＋ＬｉｓｔＡ[１]＝２１となる。
【０１７６】
図１９の表Ｔ１に示すように、スキャンライン０及びスキャンライン１の図形数の和は２１となり、基準値ＣＳＩＺＥ以下であるので、まず、スキャンライン０及びスキャンライン１が結合されることになる。
【０１７７】
図１９に示す表Ｔ２は、表Ｔ１内の順番に並ぶスキャンラインに配置される図形を形成する頂点数の和が、基準値以下になるように、一のスキャンライン又は結合された複数のスキャンラインを並べたものである。
【０１７８】
表Ｔ２において、スキャンライン０は、他のスキャンラインの結合先のスキャンラインであるであるので、０ｘＦＦＦＦＦＦＦＦが格納される。スキャンライン１は、スキャンライン０に結合される側のスキャンラインであるので、結合先のスキャンライン識別子０が格納される。
【０１７９】
ここで、ＤａｔａＳｉｚｅ＝２１≦ＣＳＩＺＥ＝２４なので、ステップＳ１２０に戻る。
【０１８０】
次に、ステップＳ１２０において、２回目の処理では、ｎ＝０、ｉ＝２であるので、ＬｉｓｔＢ[２]＝２、ｉ＝３となる。
【０１８１】
次に、ステップＳ１２２において、第２処理部１３は、表Ｔ１内の順番に並ぶスキャンラインに配置される図形を形成する頂点数の和を求める。２回目の処理では、スキャンライン０に配置される図形を形成する頂点数とスキャンライン１に配置される図形を形成する頂点数とのスキャンライン２に配置される図形を形成する頂点数と和を求めるので、ＤａｔａＳｉｚｅ＝ＤａｔａＳｉｚｅ＋ＬｉｓｔＡ[２]＝３０となる。図１９の表Ｔ１に示すように、スキャンライン０からスキャンライン２の図形数の和は３０となり、基準値ＣＳＩＺＥを超えるので、スキャンライン２は、ここでは、他のスキャンラインとは結合されない。従って、最初の第２のスキャンラインは、スキャンライン０及びスキャンライン１が結合されて構築されることになる。
【０１８２】
ここで、ＤａｔａＳｉｚｅ＝３０＞ＣＳＩＺＥ＝２４なので、ステップＳ１２６に進む。
【０１８３】
次に、ステップＳ１２６において、第２処理部１３は、変数ｎと変数ｉとの和を求める。ここでは、ｎ＝０、ｉ＝２なので、ｎ＝０＋２＝２となる。
【０１８４】
ここで、ｎ＝２＜４なので、スキャンラインＳ１１４に戻る。
【０１８５】
ステップＳ１１４において、第２処理部１３は、変数ｉに対して、初期値１を設定し、スキャンラインに配置される図形を形成する頂点数を示すＤａｔａＳｉｚｅに対して、初期値ゼロを設定する。
【０１８６】
次に、ステップＳ１１６において、第２処理部１３は、スキャンラインに配置される図形を形成する頂点数を示すＤａｔａＳｉｚｅを求める。２回目の処理では、ｎ＝２、ｉ＝１であるので、ＤａｔａＳｉｚｅ＝ＬｉｓｔＡ[２]＝９となる。
【０１８７】
次に、ステップＳ１１７において、ＬｉｓｔＢ[ｎ]に対して、スキャンライン識別子ｎで示されるスキャンラインが、他のスキャンラインの結合先のスキャンラインであることを示す識別子０ｘＦＦＦＦＦＦＦＦが格納される。２回目の処理では、ｎ＝２であるので、ＬｉｓｔＢ[２]＝０ｘＦＦＦＦＦＦＦＦとなる。
【０１８８】
次に、第２処理部１３は、ステップＳ１１８〜ステップＳ１２４の間の処理を、Ｄａｔａｓｉｚｅが基準値ＣＳＩＺＥを超えるまで繰り返す。
【０１８９】
ステップＳ１２０において、１回目の処理では、ｎ＝２、ｉ＝１、ＤａｔａＳｉｚｅ＝３であるので、ＬｉｓｔＢ[３]＝２、ｉ＝２となる。
【０１９０】
次に、ステップＳ１２２において、第２処理部１３は、表Ｔ１内の順番に並ぶスキャンラインに配置される図形を形成する頂点数の和を求める。１回目の処理では、スキャンライン２に配置される図形を形成する頂点数とスキャンライン３に配置される図形を形成する頂点数との和を求めるので、ＤａｔａＳｉｚｅ＝ＤａｔａＳｉｚｅ＋ＬｉｓｔＡ[３]＝１５となる。図１９の表Ｔ１に示すように、スキャンライン２及びスキャンライン３に配置される図形を形成する頂点数の和は、１５となり、基準値以下であるので、スキャンライン２及びスキャンライン３が結合されることになる。
【０１９１】
表Ｔ２において、スキャンライン２は、他のスキャンラインと結合される側のスキャンラインであるので、０ｘＦＦＦＦＦＦＦＦが格納される。スキャンライン３は、スキャンライン２に結合される側のスキャンラインであるので、結合先のスキャンライン識別子２が格納される。
【０１９２】
ここで、全てのスキャンラインに対して処理が終了したので、動作が終了する。このようにして、図１９に示す表Ｔ２が作成される。
以上が、図５のステップＳ１４の説明である。
【０１９３】
上述した本実施形態の描画装置によれば、スキャンラインに配置される図形を形成する頂点数に基づいて、複数のスキャンラインを結合して第２のスキャンラインを形成して、シーンデータを再構築するので、シーンデータのサイズを低減できる。
【０１９４】
また、本実施形態の描画装置によれば、頂点キャッシュ３２ｂの記憶容量に対応した頂点数の図形の図形情報を用いて、スキャンライン内部を描画するので、処理速度が向上する。
【０１９５】
本発明では、上述した実施形態のシーンデータを再構築する方法、回路、プログラム、描画方法及び描画装置は、本発明の趣旨を逸脱しない限り適宜変更が可能である。また、一の実施形態が有する構成要件は、他の実施形態にも適宜適用することができる。
【０１９６】
例えば、上述した各実施形態では、図形０〜図形４に対して、同じ設定パラメータ及び同じ設定値が用いられていたが、設定パラメータ又は設定値は同じで無くても良い。
【０１９７】
ここで述べられた全ての例及び条件付きの言葉は、読者が、発明者によって寄与された発明及び概念を技術を深めて理解することを助けるための教育的な目的を意図する。ここで述べられた全ての例及び条件付きの言葉は、そのような具体的に述べられた例及び条件に限定されることなく解釈されるべきである。また、明細書のそのような例示の機構は、本発明の優越性及び劣等性を示すこととは関係しない。本発明の実施形態は詳細に説明されているが、その様々な変更、置き換え又は修正が本発明の精神及び範囲を逸脱しない限り行われ得ることが理解されるべきである。
【符号の説明】
【０１９８】
１    描画装置
２    第１シーンデータ生成部
１０    シーンデータ結合部
１１    読み込み部
１２    第１処理部
１３    第２処理部
１４    第３処理部
２０    記憶部
２１    第１シーンデータ
２２    第２シーンデータ
２３    表示用画素データ
３０    レンダリング部
３１    シーンデータ読み出し部
３１ａ    シーンデータキャッシュ
３２    画素情報生成部
３２ａ    図形キャッシュ
３２ｂ    頂点キャッシュ
３３    表示判定部
３４    表示データ出力部
【図１】
2015215847.tif 000003
【図２】
2015215847.tif 000004
【図３】
2015215847.tif 000005
【図４】
2015215847.tif 000006
【図５】
2015215847.tif 000007
【図６】
2015215847.tif 000008
【図７】
2015215847.tif 000009
【図８】
2015215847.tif 000010
【図９】
2015215847.tif 000011
【図１０】
2015215847.tif 000012
【図１１】
2015215847.tif 000013
【図１２】
2015215847.tif 000014
【図１３】
2015215847.tif 000015
【図１４】
2015215847.tif 000016
【図１５】
2015215847.tif 000017
【図１６】
2015215847.tif 000018
【図１７】
2015215847.tif 000019
【図１８】
2015215847.tif 000020
【図１９】
2015215847.tif 000021