(57)【要約】  領域分割描画装置（１００）は、複数の単位ポリゴンの各々に対して、スクリーン座標（１３５）を用いて、当該単位ポリゴンを含む第１領域を計算し、描画領域が分割された複数の分割領域のうち、当該第１領域の少なくとも一部を含む分割領域を判定し、各単位ポリゴンに、当該単位ポリゴンを含む第１領域の少なくとも一部を含む分割領域が対応付けられたテーブルであるポリゴン別領域テーブル（１３６）を生成するテーブル生成部（１１３）と、ポリゴン別領域テーブル（１３６）を参照することで、各分割領域が対応付けられている単位ポリゴンである描画対象単位ポリゴンを判定する判定部（１２１）と、複数の分割領域の各々に対して、描画対象単位ポリゴンの頂点処理及びラスタライザ処理を行う領域描画部（１２２）とを備える。
2014087572.tif 000002
【特許請求の範囲】
【請求項１】
描画領域に描画される対象である、各々が１又は複数のポリゴンを含む複数の単位ポリゴンを示す描画コマンドを取得するコマンド取得部と、
前記描画コマンドで示される複数の単位ポリゴンの各々に対して、当該単位ポリゴンの三次元空間における頂点座標を二次元平面のスクリーン座標に変換する座標変換部と、
前記複数の単位ポリゴンの各々に対して、前記スクリーン座標を用いて、前記二次元平面において当該単位ポリゴンを含む第１領域を計算し、前記描画領域が分割された複数の分割領域のうち、当該第１領域の少なくとも一部を含む分割領域を算出し、前記複数の単位ポリゴンに対する当該算出結果を用いて、各単位ポリゴンに、当該単位ポリゴンを含む第１領域の少なくとも一部を含む分割領域が対応付けられたテーブルである領域テーブルを生成するテーブル生成部と、
前記領域テーブルを参照することで、前記複数の分割領域の各々に対して、前記複数の単位ポリゴンのうち、当該分割領域が対応付けられている単位ポリゴンである描画対象単位ポリゴンを判定する判定部と、
前記複数の分割領域の各々に対して、前記描画対象単位ポリゴンの頂点処理及びラスタライザ処理を行う領域描画部とを備える
領域分割描画装置。
【請求項２】
前記領域テーブルは固定数の複数のエントリを含み、
前記テーブル生成部は、前記複数のエントリの各々に、単位ポリゴンに対応する前記第１領域の少なくとも一部を含む分割領域を示す領域情報を格納し、
前記テーブル生成部は、前記複数の単位ポリゴンの数が、前記固定数より多い場合には、
前記複数の単位ポリゴンを、各々が１以上の単位ポリゴンを含む前記固定数のグループに分割し、
前記固定数のグループの各々に対して、前記スクリーン座標を用いて、前記二次元平面において当該グループに含まれる複数の単位ポリゴンを含む第２領域を計算し、前記複数の分割領域のうち、当該第２領域の少なくとも一部を含む分割領域を算出し、
前記固定数のグループに対する当該算出結果を用いて、各グループに、当該グループに含まれる複数の単位ポリゴンを含む第２領域の少なくとも一部を含む分割領域が対応付けられたテーブルである前記領域テーブルを生成し、
前記判定部は、前記領域テーブルを参照することで、前記複数の分割領域の各々に対して、前記複数の単位ポリゴンのうち、当該分割領域が対応付けられているグループに含まれる単位ポリゴンである前記描画対象単位ポリゴンを判定する
請求項１に記載の領域分割描画装置。
【請求項３】
前記テーブル生成部は、
前記複数の単位ポリゴンのいずれかを、処理対象単位ポリゴンとして順次選択し、
選択された処理対象単位ポリゴン毎に、当該処理対象単位ポリゴンに対する前記領域情報を生成するとともに、当該領域情報を前記複数のエントリのうち前記領域情報が保持されていないエントリに格納し、
新たな単位ポリゴンの領域情報をエントリに格納する際に、当該領域情報を格納することにより、前記領域テーブルに格納される領域情報の数が前記固定数を超えるか否かを判定し、
前記領域情報の数が前記固定数を超える場合には、前記複数のエントリのいずれかである選択エントリに格納されている前記領域情報と、前記新たな単位ポリゴンの領域情報とを用いて、前記選択エントリに格納されている前記領域情報に対応する単位ポリゴンと、前記新たな単位ポリゴンとを含む前記第２領域を計算し、
計算された前記第２領域の少なくとも一部を含む分割領域を示す前記領域情報を、前記選択エントリに格納する
請求項２に記載の領域分割描画装置。
【請求項４】
前記テーブル生成部は、
前記複数の単位ポリゴンのいずれかを、処理対象単位ポリゴンとして順次選択し、
選択された処理対象単位ポリゴン毎に、当該処理対象単位ポリゴンに対する前記領域情報を生成するとともに、当該領域情報を前記複数のエントリのうち前記領域情報が保持されていないエントリに格納し、
新たな単位ポリゴンの領域情報をエントリに格納する際に、当該領域情報を格納することにより、前記領域テーブルに格納される領域情報の数が前記固定数を越えるか否かを判定し、
前記領域情報の数が前記固定数を超える場合には、前記複数のエントリに含まれる第１エントリ及び第２エントリに格納されている二つの領域情報を用いて、前記第１エントリに格納されている前記領域情報に対応する単位ポリゴンと、前記第２エントリに格納されている前記領域情報に対応する単位ポリゴンとを含む前記第２領域を計算し、
計算された前記第２領域の少なくとも一部を含む分割領域を示す前記領域情報を、前記第１エントリに格納し、
前記新たな単位ポリゴンの前記領域情報を前記第２エントリに格納する
請求項２に記載の領域分割描画装置。
【請求項５】
前記第１領域は、前記単位ポリゴンの全てを含む最小の矩形領域である
請求項２〜４のいずれか１項に記載の領域分割描画装置。
【請求項６】
前記領域情報は、前記第１領域の頂点のうち対角となる頂点を示す情報である
請求項５に記載の領域分割描画装置。
【請求項７】
前記領域情報は、各々が１以上の前記分割領域を含む単位領域毎に１ビットが対応付けられている、予め定められたビット数の情報であり、
前記１ビットは、当該１ビットに対応付けられている前記単位領域が、当該エントリに対応する単位ポリゴンに対応する前記第１領域の少なくとも一部を含むか否かを示す
請求項２〜４のいずれか１項に記載の領域分割描画装置。
【請求項８】
前記領域情報は、
前記第１領域の頂点のうち対角となる頂点を含む分割領域を示す第１情報と、
各々が複数の前記分割領域を含む単位領域毎に１ビットが対応付けられている、予め定められたビット数の第２情報とを含み、
前記１ビットは、対応付けられている前記単位領域が、当該エントリに対応する単位ポリゴンに対応する前記第１領域の少なくとも一部を含むか否かを示し、
前記判定部は、前記複数の分割領域の各々に対して、前記複数の単位ポリゴンのうち、前記第１情報により当該分割領域が対応付けられており、かつ、前記第２情報により当該分割領域を含む単位領域が対応付けられている単位ポリゴンを、前記描画対象単位ポリゴンに判定する
請求項５に記載の領域分割描画装置。
【請求項９】
前記座標変換部は、さらに、前記複数の単位ポリゴンの各々に対して、前記スクリーン座標を用いて、当該単位ポリゴンの少なくとも一部が前記描画領域に表示される有効単位ポリゴンか、当該単位ポリゴンの全てが前記描画領域に表示されない無効単位ポリゴンかを判定し、
前記テーブル生成部は、前記処理対象単位ポリゴンが無効単位ポリゴンである場合、当該処理対象単位ポリゴンが無効単位ポリゴンであることを示す前記領域情報を前記エントリに格納し、
前記判定部は、前記領域テーブルにおいて、前記領域情報が、前記処理対象単位ポリゴンが無効単位ポリゴンであることを示す場合、当該処理対象単位ポリゴンを描画対象から除外する
請求項２〜８のいずれか１項に記載の領域分割描画装置。
【請求項１０】
前記座標変換部は、さらに、前記スクリーン座標を用いて、クリッピング処理を行うことで、前記単位ポリゴンを複数の分割単位ポリゴンに分割し、
前記テーブル生成部は、前記処理対象単位ポリゴンに対してクリッピング処理が行われた場合、前記複数の分割単位ポリゴンの全てを含む前記第１領域を計算し、
計算された前記第１領域の少なくとも一部を含む分割領域を示す前記領域情報を、前記複数のエントリのうちの一つに格納する
請求項２〜９のいずれか１項に記載の領域分割描画装置。
【請求項１１】
前記テーブル生成部は、前記描画コマンドに含まれる前記複数の単位ポリゴンのデータの順序に従い、前記複数の単位ポリゴンを、処理対象単位ポリゴンとして順次選択し、
前記判定部は、前記順序を用いて、前記複数の単位ポリゴンと、前記複数のエントリに格納されている複数の前記領域情報とを対応付ける
請求項２に記載の領域分割描画装置。
【請求項１２】
前記テーブル生成部は、前記描画コマンドに含まれる前記複数の単位ポリゴンに与えられた固有の識別番号に従い、前記複数の単位ポリゴンを、処理対象単位ポリゴンとして順次選択し、
前記判定部は、前記識別番号を用いて、前記複数の単位ポリゴンと、前記複数のエントリに格納されている複数の前記領域情報とを対応付ける
請求項２に記載の領域分割描画装置。
【請求項１３】
前記座標変換部は、さらに、前記複数の単位ポリゴンの各々に対して、前記スクリーン座標を用いて、当該単位ポリゴンの少なくとも一部が前記描画領域に表示される有効単位ポリゴンか、当該単位ポリゴンの全てが前記描画領域に表示されない無効単位ポリゴンかを判定し、
前記テーブル生成部は、さらに、前記複数の単位ポリゴンのうち、前記有効単位ポリゴンが連続する数、及び前記無効単位ポリゴンが連続する数をカウントし、当該有効単位ポリゴンが連続する数、及び当該無効単位ポリゴンが連続する数を示すポリゴン属性テーブルを生成し、
前記判定部は、
さらに、前記ポリゴン属性テーブルを参照して、前記複数の単位ポリゴンの各々が前記有効単位ポリゴンであるか、前記無効単位ポリゴンであるかを判定し、
前記領域テーブルを参照することで、前記複数の分割領域の各々に対して、前記有効単位ポリゴンのうち、当該分割領域が対応付けられている単位ポリゴンである前記描画対象単位ポリゴンを判定する
請求項２〜１２のいずれか１項に記載の領域分割描画装置。
【請求項１４】
前記単位ポリゴンは、複数のポリゴンを含むポリゴン群であり、
前記テーブル生成部は、前記領域テーブルとして、（ｉ）各ポリゴン群に、当該ポリゴン群を含む第１領域の少なくとも一部を含む分割領域が対応付けられたテーブルである第１領域テーブルと、（ｉｉ）各ポリゴンに、当該ポリゴンを含む第１領域の少なくとも一部を含む分割領域が対応付けられたテーブルである第２領域テーブルとを生成し、
前記判定部は、前記複数の分割領域の各々に対して、
前記第１領域テーブルを参照することで、前記複数のポリゴン群のうち、当該分割領域が対応付けられているポリゴン群である描画対象ポリゴン群を判定し、
前記第２領域テーブルを参照することで、前記描画対象ポリゴン群に含まれる複数のポリゴンのうち、当該分割領域が対応付けられているポリゴンである描画対象ポリゴンを判定し、
前記領域描画部は、前記複数の分割領域の各々に対して、前記描画対象ポリゴンの頂点処理及びラスタライザ処理を行う
請求項２に記載の領域分割描画装置。
【請求項１５】
描画領域に描画される対象である、各々が１又は複数のポリゴンを含む複数の単位ポリゴンを示す描画コマンドを取得するコマンド取得ステップと、
前記描画コマンドで示される複数の単位ポリゴンの各々に対して、当該単位ポリゴンの三次元空間における頂点座標を二次元平面のスクリーン座標に変換する座標変換ステップと、
前記複数の単位ポリゴンの各々に対して、前記スクリーン座標を用いて、前記二次元平面において当該単位ポリゴンを含む第１領域を計算し、前記描画領域が分割された複数の分割領域のうち、当該第１領域の少なくとも一部を含む分割領域を算出し、前記複数の単位ポリゴンに対する当該算出結果を用いて、各単位ポリゴンに、当該単位ポリゴンを含む第１領域の少なくとも一部を含む分割領域が対応付けられたテーブルである領域テーブルを生成するテーブル生成ステップと、
前記領域テーブルを参照することで、前記複数の分割領域の各々に対して、前記複数の単位ポリゴンのうち、当該分割領域が対応付けられている単位ポリゴンである描画対象単位ポリゴンを判定する判定ステップと、
前記複数の分割領域の各々に対して、前記描画対象単位ポリゴンの頂点処理及びラスタライザ処理を行う領域描画ステップとを含む
領域分割描画方法。
【請求項１６】
請求項１５記載の領域分割描画方法をコンピュータに実行させるための
プログラム。
【請求項１７】
描画領域に描画される対象である、各々が１又は複数のポリゴンを含む複数の単位ポリゴンを示す描画コマンドを取得するコマンド取得部と、
前記描画コマンドで示される複数の単位ポリゴンの各々に対して、当該単位ポリゴンの三次元空間における頂点座標を二次元平面のスクリーン座標に変換する座標変換部と、
前記複数の単位ポリゴンの各々に対して、前記スクリーン座標を用いて、前記二次元平面において当該単位ポリゴンを含む第１領域を計算し、前記描画領域が分割された複数の分割領域のうち、当該第１領域の少なくとも一部を含む分割領域を算出し、前記複数の単位ポリゴンに対する当該算出結果を用いて、各単位ポリゴンに、当該単位ポリゴンを含む第１領域の少なくとも一部を含む分割領域が対応付けられたテーブルである領域テーブルを生成するテーブル生成部と、
前記領域テーブルを参照することで、前記複数の分割領域の各々に対して、前記複数の単位ポリゴンのうち、当該分割領域が対応付けられている単位ポリゴンである描画対象単位ポリゴンを判定する判定部と、
前記複数の分割領域の各々に対して、前記描画対象単位ポリゴンの頂点処理及びラスタライザ処理を行う領域描画部とを備える
集積回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、三次元グラフィックスの描画処理に関し、特に、描画領域が分割された複数の分割領域毎に処理を行う領域分割描画装置に関する。
【背景技術】
【０００２】
三次元グラフィックスの描画処理において、描画領域を複数の矩形領域（ブロック又はタイル）に分割して処理する方式が知られている。この方式では、矩形領域のためのメモリとして高速アクセス可能な内部メモリが用いられる。これにより、ラスタライザが矩形領域のメモリにアクセスしている間は、外部メモリへのアクセスが発生しないので、メモリ帯域及び消費電力が低減される（例えば、特許文献１）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特表２０１１−５１５７５１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
このような、領域分割を行う領域分割描画装置では、描画処理に用いる中間データのデータ量を削減することが望まれている。【０００５】
そこで、本発明は、領域分割を行う領域分割描画装置であって、描画処理に用いる中間データのデータ量を削減できる領域分割描画装置を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の一態様に係る領域分割描画装置は、描画領域に描画される対象である、各々が１又は複数のポリゴンを含む複数の単位ポリゴンを示す描画コマンドを取得するコマンド取得部と、前記描画コマンドで示される複数の単位ポリゴンの各々に対して、当該単位ポリゴンの三次元空間における頂点座標を二次元平面のスクリーン座標に変換する座標変換部と、前記複数の単位ポリゴンの各々に対して、前記スクリーン座標を用いて、前記二次元平面において当該単位ポリゴンを含む第１領域を計算し、前記描画領域が分割された複数の分割領域のうち、当該第１領域の少なくとも一部を含む分割領域を算出し、前記複数の単位ポリゴンに対する当該算出結果を用いて、各単位ポリゴンに、当該単位ポリゴンを含む第１領域の少なくとも一部を含む分割領域が対応付けられたテーブルである領域テーブルを生成するテーブル生成部と、前記領域テーブルを参照することで、前記複数の分割領域の各々に対して、前記複数の単位ポリゴンのうち、当該分割領域が対応付けられている単位ポリゴンである描画対象単位ポリゴンを判定する判定部と、前記複数の分割領域の各々に対して、前記描画対象単位ポリゴンの頂点処理及びラスタライザ処理を行う領域描画部とを備える。【０００７】
なお、これらの包括的または具体的な態様は、システム、方法、集積回路、コンピュータプログラムまたはコンピュータ読み取り可能なＣＤ−ＲＯＭなどの記録媒体で実現されてもよく、システム、方法、集積回路、コンピュータプログラムおよび記録媒体の任意な組み合わせで実現されてもよい。
【発明の効果】
【０００８】
本発明は、領域分割を行う領域分割描画装置であって、描画処理に用いる中間データのデータ量を削減できる領域分割描画装置を提供できる。
【図面の簡単な説明】
【０００９】
【図１】図１は、比較例に係る領域分割描画装置の構成を示すブロック図である。
【図２】図２は、実施の形態１に係る領域分割描画装置の構成を示すブロック図である。
【図３】図３は、実施の形態１に係る領域分割描画装置の構成を示すブロック図である。
【図４Ａ】図４Ａは、実施の形態１に係る分割領域の一例を示す図である。
【図４Ｂ】図４Ｂは、実施の形態１に係る分割領域の一例を示す図である。
【図５】図５は、実施の形態１に係る領域分割描画方法のフローチャートである。
【図６】図６は、実施の形態１に係るディスプレイリスト及びポリゴンデータの具体例を示す図である。
【図７Ａ】図７Ａは、実施の形態１に係る座標変換処理を説明するための図である。
【図７Ｂ】図７Ｂは、実施の形態１に係る座標変換処理を説明するための図である。
【図８Ａ】図８Ａは、実施の形態１に係るクリッピング処理を説明するための図である。
【図８Ｂ】図８Ｂは、実施の形態１に係るクリッピング処理を説明するための図である。
【図９】図９は、実施の形態１に係るポリゴン別領域テーブル生成処理を説明するための図である。
【図１０】図１０は、実施の形態１に係るポリゴン別領域テーブル生成処理を説明するための図である。
【図１１Ａ】図１１Ａは、実施の形態１に係るポリゴンの一例を示す図である。
【図１１Ｂ】図１１Ｂは、実施の形態１に係る領域情報の計算方法を説明するための図である。
【図１２】図１２は、実施の形態１に係るポリゴン別領域テーブル生成処理の動作を示すフローチャートである。
【図１３Ａ】図１３Ａは、実施の形態１に係るポリゴンの一例を示す図である。
【図１３Ｂ】図１３Ｂは、実施の形態１に係るポリゴン別領域テーブルの一例を示す図である。
【図１４】図１４は、実施の形態１に係る統合処理の動作を示すフローチャートである。
【図１５Ａ】図１５Ａは、実施の形態１に係る統合処理時のポリゴン別領域テーブルを示す図である。
【図１５Ｂ】図１５Ｂは、実施の形態１に係る統合処理を説明するための図である。
【図１５Ｃ】図１５Ｃは、実施の形態１に係る統合処理時のポリゴン別領域テーブルを示す図である。
【図１６Ａ】図１６Ａは、実施の形態１に係る統合処理時のポリゴン別領域テーブルを示す図である。
【図１６Ｂ】図１６Ｂは、実施の形態１に係る統合処理を説明するための図である。
【図１６Ｃ】図１６Ｃは、実施の形態１に係る統合処理を説明するための図である。
【図１６Ｄ】図１６Ｄは、実施の形態１に係る統合処理時のポリゴン別領域テーブルを示す図である。
【図１７Ａ】図１７Ａは、実施の形態１に係る統合処理時のポリゴン別領域テーブルを示す図である。
【図１７Ｂ】図１７Ｂは、実施の形態１に係る統合処理時のポリゴン別領域テーブルを示す図である。
【図１７Ｃ】図１７Ｃは、実施の形態１に係る統合処理時のポリゴン別領域テーブルを示す図である。
【図１７Ｄ】図１７Ｄは、実施の形態１に係る統合処理時のポリゴン別領域テーブルを示す図である。
【図１７Ｅ】図１７Ｅは、実施の形態１に係る統合処理時のポリゴン別領域テーブルを示す図である。
【図１７Ｆ】図１７Ｆは、実施の形態１に係る統合処理時のポリゴン別領域テーブルを示す図である。
【図１８】図１８は、実施の形態１に係る判定処理の動作を示すフローチャートである。
【図１９】図１９は、実施の形態２に係る領域分割描画装置の構成を示すブロック図である。
【図２０】図２０は、実施の形態２に係る領域分割描画方法のフローチャートである。
【図２１】図２１は、実施の形態２に係るポリゴン属性テーブル生成処理を説明するための図である。
【図２２】図２２は、実施の形態２に係るポリゴン属性テーブルを用いた判定処理の動作を示すフローチャートである。
【図２３Ａ】図２３Ａは、実施の形態３に係るバウンダリビットを説明するための図である。
【図２３Ｂ】図２３Ｂは、実施の形態３に係るポリゴン別領域テーブルの一例を示す図である。
【図２４】図２４は、実施の形態３に係る、統合処理後のバウンダリボックスの一例を示す図である。
【図２５Ａ】図２５Ａは、実施の形態３に係るバウンダリビットを説明するための図である。
【図２５Ｂ】図２５Ｂは、実施の形態３に係るバウンダリビットを説明するための図である。
【図２５Ｃ】図２５Ｃは、実施の形態３に係るバウンダリビットを説明するための図である。
【図２６】図２６は、実施の形態３に係るバウンダリボックスの一例を示す図である。
【図２７】図２７は、実施の形態３に係るポリゴン別領域テーブルの別の例を示す図である。
【図２８】図２８は、実施の形態３に係る判定処理の動作を示すフローチャートである。
【図２９】図２９は、実施の形態４に係る領域分割描画装置の構成を示すブロック図である。
【図３０】図３０は、実施の形態４に係る領域分割描画方法のフローチャートである。
【図３１】図３１は、実施の形態４に係るポリゴン群の一例を示す図である。
【図３２】図３２は、実施の形態４に係るポリゴン群別領域テーブルの一例を示す図である。
【図３３】図３３は、実施の形態４に係るポリゴン群判定処理の動作を示すフローチャートである。
【発明を実施するための形態】
【００１０】
（本発明の基礎となった知見）
本発明者は、従来の技術において、以下の問題が生じることを見出した。
【００１１】
描画領域を複数の矩形領域に分割して処理する方式では、複数の矩形領域を処理するために、シーンに含まれるポリゴンのロード回数が矩形領域の数の回数必要になってしまうという領域分割描画特有の課題がある。
【００１２】
この課題を解決するために、分割領域（矩形領域）ごとに可視ポリゴンのリストを保持しておき当該分割領域を描画する時に当該分割領域の可視ポリゴンリストのみを参照するという方法を用いることができる。以下、この方法について説明する。
【００１３】
図１は、本発明の比較例に係る領域分割描画装置３００を示すブロック図である。
【００１４】
図１に示す領域分割描画装置３００は、ポリゴン形状処理部３１０と、ラスタライザ処理部３２０とを備える。
【００１５】
ポリゴン形状処理部３１０は、コマンド取得部３１１と、座標変換部３１２と、ポリゴン領域計算部３１３と、リスト保持部３１４とを備える。
【００１６】
コマンド取得部３１１は、ディスプレイリスト保持部３０１に保持されているディスプレイリスト３３１をフェッチし、当該ディスプレイリスト３３１を描画コマンド３３４にデコードする。
【００１７】
座標変換部３１２は、描画コマンド３３４で示される描画対象のポリゴンの形状を示す頂点座標３３２Ａをポリゴンデータ保持部３０２からフェッチし、当該頂点座標３３２Ａを座標変換することによりスクリーン座標３３５を生成する。
【００１８】
ポリゴン領域計算部３１３は、スクリーン座標３３５を用いて、カリング処理によりポリゴンの可視と不可視とを選別する。次に、ポリゴン領域計算部３１３は、可視と判定されたポリゴンに対して、分割領域ごとに当該ポリゴンが可視かどうかを判定し、分割領域ごとに可視のポリゴンを示す領域別ポリゴンリスト３３６を生成する。
【００１９】
リスト保持部３１４は、領域別ポリゴンリスト３３６を保持する。
【００２０】
以上により、ポリゴン形状処理部３１０は、シーン内のすべてのポリゴンに関し、ラスタライザ処理まで行わず、領域別ポリゴンリスト３３６を生成する処理までを行う。領域別ポリゴンリスト３３６は、分割領域ごとに属する可能性のあるポリゴンを示すリストである。
【００２１】
ラスタライザ処理部３２０は、ポリゴンリスト取得部３２１と、領域描画部３２２とを備える。ポリゴンリスト取得部３２１は、ポリゴン形状処理部３１０により生成された領域別ポリゴンリスト３３６を取得する。
【００２２】
領域描画部３２２は、分割領域毎に、領域別ポリゴンリスト３３６で示される処理対象の分割領域で可視であるポリゴンのポリゴンデータ３３２Ｂのロードし、当該ポリゴンデータ３３２Ｂに対して頂点処理及びラスタライザ処理を行い、当該処理により得られた画素データ３３７を外部メモリへ転送する。
【００２３】
領域別ポリゴンリスト３３６には、当該分割領域で可視と判定されたポリゴンを示す情報が保持される。領域描画部３２２は、ポリゴンデータ保持部３０２から未変換のポリゴン情報と、該ポリゴンを構成する頂点アトリビュートデータとを含むポリゴンデータ３３２Ｂをフェッチし、当該ポリゴンデータ３３２Ｂに対して頂点処理、ラスタライズ処理及び転送処理を行う。この際、分割領域のためのメモリとして、高速アクセス可能な描画用内蔵メモリを用いることで、αブレンドによる画素のリード及びライトは当該描画用内蔵メモリに対して行われる。これにより、外部メモリへのアクセスが発生しないので、メモリ帯域の低減及び消費電力の低減などの効果を得ることができる。
【００２４】
このように、本比較例に係る領域分割描画装置３００では、ポリゴン形状処理部３１０が、分割領域ごとに可視となるポリゴンを示す領域別ポリゴンリスト３３６を作成及び保持する。これにより、ラスタライザ処理時には不要なポリゴンデータのロードを行うことなく、領域分割描画処理を実現することができる。
【００２５】
しかしながら、この比較例の構成では、分割領域毎にポリゴンの情報が保持されている。これにより、シーン内に大量の可視ポリゴンが存在する場合には、領域別ポリゴンリスト３３６を生成及び保持するためのメモリ領域のサイズが大きくなるという課題があることを本発明者は見出した。
【００２６】
極端な例では、ポリゴンが全分割領域に跨るような場合には、領域別ポリゴンリスト３３６の全領域に当該ポリゴンの情報が登録される。よって、最悪の場合、領域別ポリゴンリスト３３６は、分割領域数×全ポリゴン数だけの情報を保持する必要がある。このように、大量のメモリ領域が必要である。
【００２７】
また、この領域別ポリゴンリスト３３６のためのメモリ領域のサイズは、ポリゴン形状処理部３１０による処理を実際に行ってみないと確定できない。これにより、予め確保しているメモリ領域を超えるような可視ポリゴンが存在するシーンに対しては領域分割描画処理を中断せざるをえないという課題があることを本発明者は見出した。
【００２８】
本発明の一態様に係る領域分割描画装置は、描画領域に描画される対象である、各々が１又は複数のポリゴンを含む複数の単位ポリゴンを示す描画コマンドを取得するコマンド取得部と、前記描画コマンドで示される複数の単位ポリゴンの各々に対して、当該単位ポリゴンの三次元空間における頂点座標を二次元平面のスクリーン座標に変換する座標変換部と、前記複数の単位ポリゴンの各々に対して、前記スクリーン座標を用いて、前記二次元平面において当該単位ポリゴンを含む第１領域を計算し、前記描画領域が分割された複数の分割領域のうち、当該第１領域の少なくとも一部を含む分割領域を算出し、前記複数の単位ポリゴンに対する当該算出結果を用いて、各単位ポリゴンに、当該単位ポリゴンを含む第１領域の少なくとも一部を含む分割領域が対応付けられたテーブルである領域テーブルを生成するテーブル生成部と、前記領域テーブルを参照することで、前記複数の分割領域の各々に対して、前記複数の単位ポリゴンのうち、当該分割領域が対応付けられている単位ポリゴンである描画対象単位ポリゴンを判定する判定部と、前記複数の分割領域の各々に対して、前記描画対象単位ポリゴンの頂点処理及びラスタライザ処理を行う領域描画部とを備える。
【００２９】
この構成によれば、当該領域分割描画装置は、単位ポリゴン毎に、当該単位ポリゴンに対応する第１領域に含まれる分割領域を示す領域テーブルを作成し、領域分割描画の際に当該領域テーブルを参照して、処理対象の分割領域に対して、処理対象の単位ポリゴンを判定できる。これにより、例えば、分割領域毎に処理対象の単位ポリゴンを示すテーブルを用いる場合に比べ、大量の描画対象の単位ポリゴンが存在する場合における、テーブルのデータ量を低減できる。
【００３０】
例えば、前記領域テーブルは固定数の複数のエントリを含み、前記テーブル生成部は、前記複数のエントリの各々に、単位ポリゴンに対応する前記第１領域の少なくとも一部を含む分割領域を示す領域情報を格納し、前記テーブル生成部は、前記複数の単位ポリゴンの数が、前記固定数より多い場合には、前記複数の単位ポリゴンを、各々が１以上の単位ポリゴンを含む前記固定数のグループに分割し、前記固定数のグループの各々に対して、前記スクリーン座標を用いて、前記二次元平面において当該グループに含まれる複数の単位ポリゴンを含む第２領域を計算し、前記複数の分割領域のうち、当該第２領域の少なくとも一部を含む分割領域を算出し、前記複数のグループに対する当該算出結果を用いて、各グループに、当該グループに含まれる複数の単位ポリゴンを含む第２領域の少なくとも一部を含む分割領域が対応付けられたテーブルである前記領域テーブルを生成し、前記判定部は、前記領域テーブルを参照することで、前記複数の分割領域の各々に対して、前記複数の単位ポリゴンのうち、当該分割領域が対応付けられているグループに含まれる単位ポリゴンである前記描画対象単位ポリゴンを判定してもよい。
【００３１】
この構成によれば、当該領域分割描画装置は、大量の描画対象の単位ポリゴンが存在する場合でも、予め定められたデータ量の領域テーブルを生成することができる。
【００３２】
例えば、前記テーブル生成部は、前記複数の単位ポリゴンのいずれかを、処理対象単位ポリゴンとして順次選択し、選択された処理対象単位ポリゴン毎に、当該処理対象単位ポリゴンに対する前記領域情報を生成するとともに、当該領域情報を前記複数のエントリのうち前記領域情報が保持されていないエントリに格納し、新たな単位ポリゴンの領域情報をエントリに格納する際に、当該領域情報を格納することにより、前記領域テーブルに格納される領域情報の数が前記固定数を超えるか否かを判定し、前記領域情報の数が前記固定数を超える場合には、前記複数のエントリのいずれかである選択エントリに格納されている前記領域情報と、前記新たな単位ポリゴンの領域情報とを用いて、前記選択エントリに格納されている前記領域情報に対応する単位ポリゴンと、前記新たな単位ポリゴンとを含む前記第２領域を計算し、計算された前記第２領域の少なくとも一部を含む分割領域を示す前記領域情報を、前記選択エントリに格納してもよい。
【００３３】
例えば、前記テーブル生成部は、前記複数の単位ポリゴンのいずれかを、処理対象単位ポリゴンとして順次選択し、選択された処理対象単位ポリゴン毎に、当該処理対象単位ポリゴンに対する前記領域情報を生成するとともに、当該領域情報を前記複数のエントリのうち前記領域情報が保持されていないエントリに格納し、新たな単位ポリゴンの領域情報をエントリに格納する際に、当該領域情報を格納することにより、前記領域テーブルに格納される領域情報の数が前記固定数を越えるか否かを判定し、前記領域情報の数が前記固定数を超える場合には、前記複数のエントリに含まれる第１エントリ及び第２エントリに格納されている二つの領域情報を用いて、前記第１エントリに格納されている前記領域情報に対応する単位ポリゴンと、前記第２エントリに格納されている前記領域情報に対応する単位ポリゴンとを含む前記第２領域を計算し、計算された前記第２領域の少なくとも一部を含む分割領域を示す前記領域情報を、前記第１エントリに格納し、前記新たな単位ポリゴンの前記領域情報を前記第２エントリに格納してもよい。
【００３４】
この構成によれば、当該領域分割描画装置は、描画順序が隣接した単位ポリゴンの領域情報を一つのエントリに格納することができる。一般的に描画順序が隣接する単位ポリゴンは比較的描画位置が近いことが多いため、当該領域分割描画装置は、領域情報の精度を向上できる。
【００３５】
例えば、前記第１領域は、前記単位ポリゴンの全てを含む最小の矩形領域であってもよい。
【００３６】
この構成によれば、当該領域分割描画装置は、領域情報のデータ量を削減できる。
【００３７】
例えば、前記領域情報は、前記第１領域の頂点のうち対角となる頂点を示す情報であってもよい。
【００３８】
この構成によれば、当該領域分割描画装置は、領域情報のデータ量を削減できる。
【００３９】
例えば、前記領域情報は、各々が１以上の前記分割領域を含む単位領域毎に１ビットが対応付けられている、予め定められたビット数の情報であり、前記１ビットは、当該１ビットが対応付けられている前記単位領域が、当該エントリに対応する単位ポリゴンに対応する前記第１領域の少なくとも一部を含むか否かを示す。
【００４０】
この構成によれば、当該領域分割描画装置は、複数の単位ポリゴンが固定数のグループに分割に分割された場合に、領域情報において不要な領域が指定されることを抑制できる。
【００４１】
例えば、前記領域情報は、前記第１領域の頂点のうち対角となる頂点を含む分割領域を示す第１情報と、各々が複数の前記分割領域を含む単位領域毎に１ビットが対応付けられている、予め定められたビット数の第２情報とを含み、前記１ビットは、対応付けられている前記単位領域が、当該エントリに対応する単位ポリゴンに対応する前記第１領域の少なくとも一部を含むか否かを示し、前記判定部は、前記複数の分割領域の各々に対して、前記複数の単位ポリゴンのうち、前記第１情報により当該分割領域が対応付けられており、かつ、前記第２情報により当該分割領域を含む単位領域が対応付けられている単位ポリゴンを、前記描画対象単位ポリゴンに判定してもよい。
【００４２】
この構成によれば、当該領域分割描画装置は、複数の単位ポリゴンが固定数のグループに分割に分割された場合に、領域情報において不要な領域が指定されることを抑制できるとともに、領域指定の精度の低下を抑制できる。
【００４３】
例えば、前記座標変換部は、さらに、前記複数の単位ポリゴンの各々に対して、前記スクリーン座標を用いて、当該単位ポリゴンの少なくとも一部が前記描画領域に表示される有効単位ポリゴンか、当該単位ポリゴンの全てが前記描画領域に表示されない無効単位ポリゴンかを判定し、前記テーブル生成部は、前記処理対象単位ポリゴンが無効単位ポリゴンである場合、当該処理対象単位ポリゴンが無効単位ポリゴンであることを示す前記領域情報を前記エントリに格納し、前記判定部は、前記領域テーブルにおいて、前記領域情報が、前記処理対象単位ポリゴンが無効単位ポリゴンであることを示す場合、当該処理対象単位ポリゴンを描画対象から除外してもよい。
【００４４】
この構成によれば、判定部は、領域テーブルに含まれる各エントリが、どの単位ポリゴンに対応しているかを容易に判定できる。
【００４５】
例えば、前記座標変換部は、さらに、前記スクリーン座標を用いて、クリッピング処理を行うことで、前記単位ポリゴンを複数の分割単位ポリゴンに分割し、前記テーブル生成部は、前記処理対象単位ポリゴンに対してクリッピング処理が行われた場合、前記複数の分割単位ポリゴンの全てを含む前記第１領域を計算し、計算された前記第１領域の少なくとも一部を含む分割領域を示す前記領域情報を、前記複数のエントリのうちの一つに格納してもよい。
【００４６】
この構成によれば、当該領域分割描画装置は、クリッピング処理により分割された複数の単位ポリゴンの領域情報を一つのエントリに格納することができる。
【００４７】
例えば、前記テーブル生成部は、前記描画コマンドに含まれる前記複数の単位ポリゴンのデータの順序に従い、前記複数の単位ポリゴンを、処理対象単位ポリゴンとして順次選択し、前記判定部は、前記順序を用いて、前記複数の単位ポリゴンと、前記複数のエントリに格納されている複数の前記領域情報とを対応付けてもよい。
【００４８】
この構成によれば、判定部は、領域テーブルに含まれる各エントリが、どの単位ポリゴンに対応しているかを容易に判定できる。
【００４９】
例えば、前記座標変換部は、さらに、前記複数の単位ポリゴンの各々に対して、前記スクリーン座標を用いて、当該単位ポリゴンの少なくとも一部が前記描画領域に表示される有効単位ポリゴンか、当該単位ポリゴンの全てが前記描画領域に表示されない無効単位ポリゴンかを判定し、前記テーブル生成部は、さらに、前記複数の単位ポリゴンのうち、前記有効単位ポリゴンが連続する数、及び前記無効単位ポリゴンが連続する数をカウントし、当該有効単位ポリゴンが連続する数、及び当該無効単位ポリゴンが連続する数を示すポリゴン属性テーブルを生成し、前記判定部は、さらに、前記ポリゴン属性テーブルを参照して、前記複数の単位ポリゴンの各々が前記有効単位ポリゴンであるか、前記無効単位ポリゴンであるかを判定し、前記領域テーブルを参照することで、前記複数の分割領域の各々に対して、前記有効単位ポリゴンのうち、当該分割領域が対応付けられている単位ポリゴンである前記描画対象単位ポリゴンを判定してもよい。
【００５０】
この構成によれば、有効単位ポリゴンの領域情報のみが領域テーブルに格納される。これにより、当該領域分割描画装置は、領域テーブルのデータ量を削減できる。
【００５１】
例えば、前記単位ポリゴンは、複数のポリゴンを含むポリゴン群であり、前記テーブル生成部は、前記領域テーブルとして、（ｉ）各ポリゴン群に、当該ポリゴン群を含む第１領域の少なくとも一部を含む分割領域が対応付けられたテーブルである第１領域テーブルと、（ｉｉ）各ポリゴンに、当該ポリゴンを含む第１領域の少なくとも一部を含む分割領域が対応付けられたテーブルである第２領域テーブルとを生成し、前記判定部は、前記複数の分割領域の各々に対して、前記第１領域テーブルを参照することで、前記複数のポリゴン群のうち、当該分割領域が対応付けられているポリゴン群である描画対象ポリゴン群を判定し、前記第２領域テーブルを参照することで、前記描画対象ポリゴン群に含まれる複数のポリゴンのうち、当該分割領域が対応付けられているポリゴンである描画対象ポリゴンを判定し、前記領域描画部は、前記複数の分割領域の各々に対して、前記描画対象ポリゴンの頂点処理及びラスタライザ処理を行ってもよい。
【００５２】
この構成によれば、当該領域分割描画装置は、ポリゴン群単位の判定と、ポリゴン単位の判定とを用いることで、判定処理の処理量を低減できる。
【００５３】
なお、これらの包括的または具体的な態様は、システム、方法、集積回路、コンピュータプログラムまたはコンピュータ読み取り可能なＣＤ−ＲＯＭなどの記録媒体で実現されてもよく、システム、方法、集積回路、コンピュータプログラムおよび記録媒体の任意な組み合わせで実現されてもよい。
【００５４】
以下、本発明の一態様に係る領域分割描画装置について、図面を参照しながら具体的に説明する。
【００５５】
なお、以下で説明する実施の形態は、いずれも本発明の一具体例を示すものである。以下の実施の形態で示される数値、形状、材料、構成要素、構成要素の配置位置及び接続形態、ステップ、ステップの順序などは、一例であり、本発明を限定する主旨ではない。また、以下の実施の形態における構成要素のうち、最上位概念を示す独立請求項に記載されていない構成要素については、任意の構成要素として説明される。
【００５６】
（実施の形態１）
本実施の形態に係る領域分割描画装置は、複数のポリゴンの各々に対して、複数の分割領域のうち、当該ポリゴンを含む分割領域を判定し、各ポリゴンに当該ポリゴンに含まれる分割領域が対応付けられたテーブルであるポリゴン別領域テーブルを生成する。そして、当該領域分割描画装置は、複数の分割領域毎に、複数のポリゴンのうち、ポリゴン別領域テーブルにおいて、処理対象の分割領域が対応付けられているポリゴンである処理対象ポリゴンを判定する。
【００５７】
これにより、当該領域分割描画装置は、例えば、分割領域毎に処理対象のポリゴンを示すテーブルを用いる場合に比べ、大量の描画対象のポリゴンが存在する場合における、テーブルのデータ量を低減できる。
【００５８】
まず、本実施の形態に係る領域分割描画装置の基本構成を説明する。
【００５９】
図２は、本実施の形態に係る領域分割描画装置１００の構成を示すブロック図である。図２に示す領域分割描画装置１００は、コマンド取得部１１１と、座標変換部１１２と、テーブル生成部１１３と、判定部１２１と、領域描画部１２２とを備える。
【００６０】
コマンド取得部１１１は、描画領域に描画される対象である複数のポリゴンを示す描画コマンド１３１を取得する。
【００６１】
座標変換部１１２は、描画コマンド１３１で示された複数のポリゴンの各々に対して、当該ポリゴンの三次元空間における頂点座標を含むポリゴンデータ１３２を取得し、当該頂点座標を二次元平面のスクリーン座標１３５に変換する。
【００６２】
テーブル生成部１１３は、複数のポリゴンの各々に対して、当該ポリゴンのスクリーン座標１３５を用いて、二次元平面において当該ポリゴンを含む第１領域を計算する。次に、テーブル生成部１１３は、描画領域が分割された複数の分割領域のうち、第１領域の少なくとも一部を含む分割領域を算出する。次に、テーブル生成部１１３は、複数のポリゴンに対する算出結果を用いて、各ポリゴンに、当該ポリゴンを含む第１領域の少なくとも一部を含む分割領域が対応付けられたテーブルであるポリゴン別領域テーブル１３６を生成する。
【００６３】
判定部１２１は、ポリゴン別領域テーブル１３６を参照することで、複数の分割領域の各々に対して、複数のポリゴンのうち、処理対象の分割領域が対応付けられているポリゴンである描画対象ポリゴンを判定する。
【００６４】
領域描画部１２２は、分割領域毎に、描画対象ポリゴンに対して頂点処理及びラスタライザ処理を行うことで画素データ１３７を生成する。
【００６５】
以下、領域分割描画装置１００の具体的な構成を説明する。
【００６６】
図３は、本実施の形態に係る領域分割描画装置１００の構成を示すブロック図である。
【００６７】
図３に示す領域分割描画装置１００は、ポリゴン形状処理部１１０と、領域別ポリゴン描画部１２０とを備える。
【００６８】
ポリゴン形状処理部１１０は、各ポリゴンに、当該ポリゴンに対応する分割領域が対応付けられたテーブルであるポリゴン別領域テーブル１３６を生成する。領域別ポリゴン描画部１２０は、ポリゴン別領域テーブル１３６を用いて、分割領域毎に描画処理を行う。
【００６９】
ポリゴン形状処理部１１０は、コマンド取得部１１１Ａと、座標変換部１１２と、テーブル生成部１１３と、テーブル保持部１１４と、分割領域設定部１１５とを備える。領域別ポリゴン描画部１２０は、コマンド取得部１１１Ｂと、判定部１２１と、領域描画部１２２と、描画領域設定部１２３とを備える。
【００７０】
分割領域設定部１１５は、矩形の分割領域のサイズ及び分割数を設定する。図４Ａ及び図４Ｂを用いて、領域分割描画処理の流れを説明する。領域分割描画処理では、最終描画領域４０１が、最終描画領域４０１よりも小さいサイズの複数の分割領域４０２（０〜３１）に分割される。そして、分割領域４０２ごとに描画処理が行われる。図４Ａは、最終描画領域４０１を、横８分割かつ縦４分割の計３２分割した場合の例を示す。
【００７１】
一般的には分割領域４０２のデータと同サイズの内部メモリ領域４０３が領域描画先として用いられる。よって、各分割領域の描画処理中において、画素データへのアクセスとして、内部メモリ領域４０３へのアクセスのみが行われる。つまり、最終描画領域４０１のデータが保持されている外部メモリへのアクセスは発生しない。また、各分割領域４０２の描画処理が完了するたびに、処理済の分割領域４０２のデータが、最終描画領域４０１の対応する位置のデータとして外部メモリへ転送される。このため、内部メモリ領域４０３には分割領域４０２のデータを包含するサイズ以上のサイズが必須となる。
【００７２】
ここで、最終描画領域４０１の幅をＷ、高さをＨ、分割領域の幅をＢＷ、高さをＢＨとすると、横方向に配置される分割領域４０２の数ＸＮＵＭはＣＥＩＬ（Ｗ／ＢＷ）で計算され、縦方向に配置される分割領域４０２の数ＹＮＵＭはＣＥＩＬ（Ｈ／ＢＨ）で計算される。
【００７３】
図４Ａは、Ｗ＝８×ＢＷ、Ｈ＝４×ＢＨが成り立つ状態の分割例を示しており、ＸＮＵＭ＝８、ＹＮＵＭ＝４である。一方、図４ＢはＷ＝８×ＢＷ＋α（α＜ＢＷ）、Ｈ＝４×ＢＨ＋β（β＜ＢＨ）の場合の分割例を示しており、ＸＮＵＭ＝９、ＹＮＵＭ＝５である。
【００７４】
図４Ｂのように最終描画領域４０１の幅Ｗが分割領域４０２の幅ＢＷで割り切れない場合、領域８、１７、２６、３５及び４４は、横方向にＢＷ−αだけ、領域３６〜４４は縦方向ＢＨ−βだけ最終描画領域４０１を超えてしまう。よって、最終描画領域４０１への転送として、端数部分を考慮した部分領域の転送が行われる必要がある。
【００７５】
なお、分割領域設定部１１５による、分割領域４０２のサイズ及び分割数の設定方法は、任意でよい。例えば、分割領域４０２のサイズ及び分割数の少なくとも一方が予め定められていてもよい。分割領域設定部１１５は、設定した分割領域４０２のサイズ（ＢＷ、ＢＨ）及び分割数（ＸＮＵＭ、ＹＮＵＭ）をテーブル生成部１１３に出力する。
【００７６】
図５は、領域分割描画装置１００による領域分割描画処理のフローチャートである。
【００７７】
コマンド取得部１１１Ａ及び１１１Ｂは、図２に示すコマンド取得部１１１に対応する。また、ディスプレイリスト保持部１０１は、複数の描画コマンド１３１を含むディスプレイリストを保持している。ポリゴンデータ保持部１０２は、複数のポリゴンのポリゴンデータ１３２を保持している。
【００７８】
まず、コマンド取得部１１１Ａは、ディスプレイリスト保持部１０１に保持されるディスプレイリストに含まれる描画コマンド１３１を取得し、当該描画コマンド１３１を解釈する（Ｓ１０１）する。この描画コマンド１３１は、ポリゴンデータ１３２へのポインタを含む。
【００７９】
具体的には、図６に示すように、描画コマンド１３１は、（１）ポリゴンを描画し表示するのに必要な描画コンテキストの情報、（２）ポリゴンデータのアドレスを示す情報、（３）ポリゴンの頂点数を示す情報、及び、（４）ポリゴンの描画開始を示す情報などを含む。また、描画コマンド群であるディスプレイリストには、ポリゴンデータ１３２へのアドレス設定が含まれる。このように、一般的な構成では、ポリゴンデータ１３２は、ディスプレイリストとは別のメモリ領域に分離されて格納されている。
【００８０】
コマンド取得部１１１Ａは、ポリゴンの描画開始を示す描画開始コマンド４１１をフェッチし、その旨を座標変換部１１２に通知する。
【００８１】
次に、座標変換部１１２は、描画コマンド１３１で描画開始が指定された複数のポリゴンの各々を構成する頂点座標１３２Ａをロードし、当該頂点座標１３２Ａをスクリーン座標１３５に変換する（Ｓ１０２）。具体的には、座標変換部１１２は、描画開始コマンド４１１の前に配置されたポリゴンデータのアドレスを参照し、当該アドレスに格納されているポリゴンデータ１３２のうち、頂点座標１３２Ａをロードする。
【００８２】
ここで、ポリゴンデータ１３２は、頂点のデータとして、三次元空間における位置座標を示す頂点座標１３２Ａのほかに、属性データ１３２Ｂ（アトリビュートデータ）を含む。属性データ１３２Ｂは、頂点色、法線及びテクスチャ座標を示す情報を含む。また、頂点座標１３２Ａは通常三次元空間における位置（ｘ、ｙ、ｚ）で表現される。座標変換部１１２は、当該三次元位置をスクリーン座標の二次元位置（Ｘ、Ｙ）に変換する。
【００８３】
座標変換処理は一般的な３Ｄグラフィックスにおける既知技術であるが、図７Ａ及び図７Ｂを用いて概略を説明する。
【００８４】
頂点座標１３２Ａにおいて、ポリゴン三角形Ｐ０、Ｐ１、Ｐ２は、三次元空間上の位置座標であるモデル座標系（ｘ、ｙ、ｚ）で示される。座標変換部１１２は、当該頂点座標１３２Ａで示される点Ｐ０、Ｐ１、Ｐ２を、三次元空間上の視点位置Ｃが原点であり、かつ視線方向が−ｚ’であるカメラ座標系（ｘ’、ｙ’、ｚ’）における点Ｐ０’、Ｐ１’、Ｐ２’に変換する。さらに、座標変換部１１２は、点Ｐ０’、Ｐ１’、Ｐ２’をスクリーンに投影する射影変換を行うことにより、スクリーン座標系（Ｘ、Ｙ）における点ＳＰ０、ＳＰ１、ＳＰ２（スクリーン座標１３５）を算出する。
【００８５】
スクリーン座標１３５は最終描画領域のどの位置にポリゴンが存在するかを示す。よって、このスクリーン座標１３５は、ポリゴンがどの分割領域に属するのかを判定するために使用できる。座標変換部１１２は、ポリゴンを構成する複数の頂点のスクリーン座標１３５をテーブル生成部１１３に送る。
【００８６】
また、座標変換部１１２は、カリング処理自体は行わずカリング判定のみを行う。ポリゴンを構成する全ての頂点が最終描画領域からはみ出す場合に、当該ポリゴンは最終的にラスタライズされず不要となる。カリング処理とは、この不要なポリゴン自体を、座標変換の段階で消去する処理である。なお、ポリゴンを消去するとは、ポリゴンを描画対象から除外することである。
【００８７】
また、カリング判定は、ポリゴンを構成する全ての頂点が最終描画領域からはみ出すかどうかの判定のみを行う処理である。つまり、座標変換部１１２は、スクリーン座標１３５を用いて、複数のポリゴンの各々に対して、当該ポリゴンの少なくとも一部が描画領域に表示される有効ポリゴンか、当該ポリゴンの全てが描画領域に表示されない無効ポリゴンかを判定する。
【００８８】
また、座標変換部１１２はカリング対象となったポリゴンに対して無効フラグを付加し、当該ポリゴンのスクリーン座標１３５とともに無効フラグをテーブル生成部１１３に送る。
【００８９】
また、座標変換部１１２は、上記処理以外にクリッピング処理を行ってもよい。クリッピング処理とは、ポリゴンを構成する頂点のうち一部が、（１）視点位置Ｃよりも後方にある場合、又は（２）最終描画領域からはみ出す場合に、はみ出し部分をカットすることでポリゴンを視野内の領域に収める既知の処理である。
【００９０】
以下、クリッピング処理に関して説明する。図８Ａ及び図８Ｂはクリッピング処理を表した図である。カメラ座標系の頂点Ｐ２’が視点位置よりも後方にある（Ｚ’座標が負になる）場合、単純に射影変換を適用した結果の座標ＳＰ２は、図８Ａに示すように正しいスクリーン座標１３５に変換されない。そこで、図８Ｂに示すように、座標変換部１１２は、射影変換の前に、視点位置よりも前方にあるＺ’座標でポリゴンを構成する辺を切る。これにより正しいスクリーン座標への変換が可能となる。
【００９１】
この例では、座標変換部１１２は、Ｚ’座標が負である頂点Ｐ２’と接続されている辺Ｐ１’Ｐ２’及び辺Ｐ０’Ｐ２’と、Ｚ’＝Ｎ（Ｎ＞０）平面との交点ＣＰ０’、ＣＰ１’を計算する。次に、座標変換部１１２は、ＣＰ０’、ＣＰ１’に対し射影変換を適用することでスクリーン座標ＳＣＰ０、ＳＣＰ１を導出する。このように座標変換部１１２は、二つのポリゴンＳＰ０、ＳＰ１、ＳＣＰ０、及びポリゴンＳＰ０、ＳＣＰ０、ＳＣＰ１を生成する。つまり、座標変換部１１２は、スクリーン座標１３５を用いて、クリッピング処理を行うことで、ポリゴンを複数の分割ポリゴンに分割する。
【００９２】
クリッピング処理により一つのポリゴンが複数のポリゴンに分割された場合、座標変換部１１２は、分割された複数のポリゴンに対し、当該複数のポリゴンが同一のポリゴンから生成されたものであることを示すクリッピング状態フラグを付加する。そして、座標変換部１１２は、一つのポリゴンから分割された複数のポリゴンのスクリーン座標１３５の組を当該クリッピング状態フラグとともに、テーブル生成部１１３に送る。
【００９３】
なお、クリッピング分割の結果、ポリゴンを構成する全ての頂点が最終描画領域からはみ出す場合にはカリング判定時と同様に、座標変換部１１２は、当該ポリゴンを消去せずに、無効フラグとともに当該ポリゴンのスクリーン座標１３５をテーブル生成部１１３に送る。
【００９４】
また、前述のとおり、ポリゴンデータ１３２は、頂点座標１３２Ａだけでなく、テクスチャ参照座標、頂点カラー、及び頂点法線ベクトル等の属性データ１３２Ｂを含む。座標変換部１１２は、ポリゴンデータ１３２のうちスクリーン座標の計算に必要な頂点座標１３２Ａだけをロードしてもよいし、組となっている属性データ１３２Ｂも一緒にロードしてもよい。ただし、属性データ１３２Ｂが一緒にロードされる場合には、ロードに要する時間及びメモリアクセス量はその分増加する。また、座標変換処理自体はμコード等のプログラムで実現してもよいし、ハードワイアードで実現してもよい。
【００９５】
次に、テーブル生成部１１３は、ポリゴンごとのスクリーン座標１３５と、分割領域の数及びサイズとを用いて、当該ポリゴンが属する領域情報を計算し、各ポリゴンに領域情報を対応付けたテーブルであるポリゴン別領域テーブル１３６を生成する（Ｓ１０３）。領域情報とは、ポリゴンが属する分割領域を示す情報であり、例えば、バウンダリボックスを示す情報である。バウンダリボックスとは、ポリゴン全体を含む最小の矩形である。なお、領域情報は、ポリゴンを含む第１領域を示す情報であればよく、バウンダリボックス以外を示す情報であってもよい。また、領域情報は、例えば、第１領域の少なくとも一部を含む分割領域を示す情報である。
【００９６】
以下、図９を用いてこの処理を説明する。
【００９７】
最終描画領域４０１が横８個、縦４個の分割領域に分割される場合、０から３１までの領域ＩＤを持つ３２個の分割領域が存在する。図９において、ポリゴン４２１を構成する３点の頂点４２２Ａ〜４２２Ｃはそれぞれ領域ＩＤ３、２５、２１の分割領域に属している。ポリゴン４２１のバウンダリボックス４２３は、頂点４２２Ａ〜４２２Ｃを含む最小の矩形である。また、バウンダリボックス４２３を構成する四つの頂点のうち、対角をなす頂点４２４及び頂点４２５は、領域ＩＤ１、２９を持つ分割領域に存在する。テーブル生成部１１３は、領域情報として、この頂点４２４及び頂点４２５が含まれる二つの領域ＩＤを、ポリゴン別領域テーブル１３６に格納する。
【００９８】
なお、図９は領域ＩＤを一次元で管理した例であるが、図１０に示すように、横方向及び縦方向の二次元の領域ＩＤで、バウンダリボックス４２３が管理されてもよい。図１０では、バウンダリボックス４２３は、（ＸＩＤ、ＹＩＤ）＝（１、０）、（５、３）で表される。
【００９９】
以下、図１１Ａ及び図１１Ｂを用いてさまざまなポリゴンのパターンにおける領域情報の計算方法を説明する。
【０１００】
ポリゴン４３１の頂点は、全て最終描画領域４０１内に存在する。この場合、領域情報は、ポリゴン４３１を含む矩形領域の最小及び最大の領域ＩＤである（０、０）（３、２）の組で表される。
【０１０１】
ポリゴン４３２の全ての頂点は、同一の分割領域に属している。この場合、領域情報は、ポリゴン４３２を含む矩形領域の最小及び最大の領域ＩＤである（６、３）（６、３）の組で表される。
【０１０２】
ポリゴン４３３の一部の頂点は、最終描画領域４０１の外に存在する。この場合、領域情報は、最終描画領域４０１に含まれる最小及び最大の領域ＩＤである（３、３）（４、３）の組で表される。
【０１０３】
ポリゴン４３４の全ての頂点は、最終描画領域４０１の外に存在する。この場合、ポリゴン４３４には、当該ポリゴン４３４が描画対象外であることを示す無効フラグが付加されている。テーブル生成部１１３は、処理対象ポリゴンに無効フラグが付加されている場合（処理対象ポリゴンが無効ポリゴンである場合）、処理対象ポリゴンが無効ポリゴンであることを示す領域情報をポリゴン別領域テーブル１３６に含まれるエントリに格納する。具体的には、テーブル生成部１１３は、無効フラグが付加されているポリゴンの領域情報の最小領域ＩＤに、分割領域の最大領域ＩＤ値（７、３）を設定し、最大領域ＩＤに分割領域の最小領域ＩＤ値（０、０）を設定する。つまり、テーブル生成部１１３は、無効ポリゴンの領域情報として、当該ポリゴンが分割領域のいずれにも属さないことを示す情報を設定する。
【０１０４】
ポリゴン４３５〜４３７は、クリッピング処理により一つのポリゴンが分割されることにより得られた分割ポリゴンである。この場合、領域情報は、各分割ポリゴンのバウンダリボックスの和集合を示す。
【０１０５】
具体的には、図１１Ａに示す例では、ポリゴン４３５のバウンダリボックスは（５、０）（７、０）であり、ポリゴン４３６のバウンダリボックスは（５、０）（７、０）であり、ポリゴン４３７のバウンダリボックスは（５、０）（７、１）である。よって、クリッピング分割前のポリゴンに対するバウンダリボックスは（５、０）（７、１）である。
【０１０６】
ポリゴン４３８は三角形ではなく、一つの頂点で構成される点プリミティブである。また、ポリゴン４３９は、２個の頂点で構成される線プリミティブである。どちらも三角形プリミティブと同様にポリゴンを囲む矩形を計算すればよい。しかしながら、点及び線プリミティブの描画に対して、３Ｄグラフィックスの標準ＡＰＩ（アプリケーションプログラミングインタフェース）規格であるＯｐｅｎＧＬＥＳの仕様では、点のサイズを変更するＡＰＩ、及び、線の幅を変更するＡＰＩが存在する。このため、頂点座標だけではバウンダリボックスを計算できず、上記ＡＰＩで設定される点のサイズ、及び線の幅といったコンテキストを加味したバウンダリボックスの計算が必要となる。例えば、図１１Ａのように、半径を持つ点の領域情報は、当該半径を加味したバウンダリボックスである（６、１）（７、３）の組が設定される必要がある。また、線幅を持つ線の領域情報は、当該線幅を考慮したバウンダリボックスである（４、０）（５、１）の組が設定される必要がある。
【０１０７】
ただし、この領域情報を厳密に計算する必要性はなく、真の領域を包含していることが保証されていれば計算量を少なくするために簡易的なバウンダリボックスが領域情報として設定されてもよい。
【０１０８】
例えば、点プリミティブであるポリゴン４３８に対して、テーブル生成部１１３は、円からバウンダリボックスを計算するのではなく、中心となる頂点座標１３２Ａに半径を加減算した４点をバウンダリボックスの四つの頂点として用いても構わない。
【０１０９】
また、線プリミティブであるポリゴン４３９に対して、テーブル生成部１１３は、図１１Ａのように回転つきの矩形を計算するのではなく、線を構成する二つの頂点座標のそれぞれに線幅を加減算することで計８点を計算し、当該８点を用いて、バウンダリボックスを計算してもよい。
【０１１０】
図１２は、テーブル生成部１１３におけるポリゴン別領域テーブル１３６の生成処理（図５のＳ１０３）のフローチャートである。ただし、図１２では、点及び線プリミティブにおける半径、及び線幅は考慮していない。
【０１１１】
まず、テーブル生成部１１３は、描画対象の複数のポリゴンのうちいずれかを処理対象ポリゴンとして選択する（Ｓ１２１）。テーブル生成部１１３は、描画コマンド１３１において複数のポリゴンの情報が配置されている順番に従い、先に配置されているポリゴンから順次ポリゴンを選択する。
【０１１２】
次に、テーブル生成部１１３は、座標変換部１１２から、処理対象ポリゴンのスクリーン座標１３５と、無効フラグと、クリッピング状態フラグとを取得する（Ｓ１２２）。
【０１１３】
次に、テーブル生成部１１３は、ポリゴンのプリミティブに応じて有効な頂点を選択する（Ｓ１２３）。具体的には、点プリミティブのポリゴンの場合、１頂点のみが有効なスクリーン座標であるため、以降のバウンダリボックスの計算では他の無効なスクリーン座標２点は参照されない。同様に、線プリミティブのポリゴンの場合、２頂点が有効なスクリーン座標として選択され、三角形プリミティブのポリゴンの場合、３頂点を有効なスクリーン座標として選択される。
【０１１４】
次に、テーブル生成部１１３は、無効フラグを参照し、処理対象ポリゴンが有効ポリゴンであるか無効ポリゴンであるかを判定する。また、テーブル生成部１１３は、クリッピング状態フラグを参照し、処理対象ポリゴンがクリッピングにより分割された分割ポリゴンか否かを判定する（Ｓ１２４）。
【０１１５】
処理対象ポリゴンが無効ポリゴンであり、かつ、分割ポリゴンでない場合（Ｓ１２４でＹｅｓ）、テーブル生成部１１３は、領域情報の最小領域ＩＤとして、複数の分割領域の最大の領域ＩＤ（ＭａｘＩＤ）を設定し、領域情報の最大領域ＩＤとして複数の分割領域の最小の領域ＩＤ（ＭｉｎＩＤ）を設定する（Ｓ１２５）。これにより、当該領域情報は存在しない領域を示す。すなわち、領域情報は、ポリゴンがどの分割領域にも属さないことを示す。なお、最小領域ＩＤ＞最大領域ＩＤとなる領域情報が設定されることで、同様の効果を実現できる。
【０１１６】
次に、テーブル生成部１１３は、設定された領域情報（最小領域ＩＤ及び最小領域ＩＤ）をポリゴン別領域テーブル１３６に含まれる一つのエントリに格納する（Ｓ１２８）。
【０１１７】
このように、テーブル生成部１１３は、処理対象ポリゴンが無効ポリゴンである場合、当該処理対象ポリゴンが無効ポリゴンであることを示す領域情報をエントリに格納する。また、判定部１２１は、ポリゴン別領域テーブル１３６において、領域情報が、処理対象ポリゴンが無効ポリゴンであることを示す場合、当該処理対象ポリゴンを描画対象から除外する。
【０１１８】
一方、処理対象ポリゴンが有効ポリゴン又は分割ポリゴンである場合（Ｓ１２４でＮｏ）、テーブル生成部１１３は、処理対象ポリゴンを囲む矩形の最小座標及び最大座標を計算する。具体的には、処理対象ポリゴンが分割ポリゴンでない場合には、テーブル生成部１１３は、有効な頂点のスクリーン座標１３５を用いて、処理対象ポリゴンを囲む矩形の最小座標及び最大座標を計算する。そして、テーブル生成部１１３は、分割領域の数及びサイズを用いて、計算された最小座標及び最大座標の各々が含まれる分割領域の領域ＩＤを求める。そして、テーブル生成部１１３は、最小座標が含まれる分割領域の領域ＩＤを最小領域ＩＤに設定し、最大座標が含まれる分割領域の領域ＩＤを最大領域ＩＤに設定する（Ｓ１２６）。なお、最小座標又は最大座標が最終描画領域４０１外に存在する場合には、テーブル生成部１１３は、最終描画領域４０１内の、最小座標又は最大座標に最近傍の位置の座標に当該最小座標又は最大座標を補正する。
【０１１９】
また、処理対象ポリゴンが分割ポリゴンである場合には、テーブル生成部１１３は、無効を示す領域ＩＤを領域情報（最大領域ＩＤ及び最小領域ＩＤ）として設定する。
【０１２０】
次に、テーブル生成部１１３は、クリッピング状態フラグを参照し、処理対象ポリゴンがクリッピングにより分割された分割ポリゴンか否かを判定する（Ｓ１２７）。
【０１２１】
処理対象ポリゴンが分割ポリゴンでない場合（Ｓ１２７でＮｏ）、テーブル生成部１１３は、ステップＳ１２６で算出した最小領域ＩＤ及び最大領域ＩＤを、ポリゴン別領域テーブル１３６に含まれる一つのエントリに格納する（Ｓ１２８）。
【０１２２】
一方、処理対象ポリゴンが分割ポリゴンである場合（Ｓ１２７でＹｅｓ）、テーブル生成部１１３は、処理対象ポリゴンがクリッピング開始時の分割ポリゴンか否かを判定する（Ｓ１２９）。処理対象ポリゴンがクリッピング開始時の分割ポリゴンである場合（Ｓ１２９でＹｅｓ）、初期値として、処理対象ポリゴンの最小領域ＩＤ及び最大領域ＩＤがそのまま保持される。
【０１２３】
一方、処理対象ポリゴンがクリッピング開始時を除くクリッピング処理中の分割ポリゴンである場合（Ｓ１２９でＮｏ）、テーブル生成部１１３は、先の分割ポリゴン（例えば、クリッピング開始時の分割ポリゴン）の最小領域ＩＤ及び最大領域ＩＤを、処理対象の分割ポリゴンの最小領域ＩＤ及び最大領域ＩＤを用いて更新する（Ｓ１３０）。この処理は、先の分割ポリゴンのバウンダリボックスと、処理対象の分割ポリゴンのバウンダリボックスとの和集合を計算する処理に相当する。具体的には、テーブル生成部１１３は、先の分割ポリゴンの最小領域ＩＤと、処理対象の分割ポリゴンの最小領域ＩＤとのうち小さいほうを選択し、選択した最小領域ＩＤを、更新後の最小領域ＩＤに設定する。また、テーブル生成部１１３は、先の分割ポリゴンの最大領域ＩＤと、処理対象の分割ポリゴンの最大領域ＩＤとのうち大きいほうを選択し、選択した最大領域ＩＤを、更新後の最大領域ＩＤに設定する。
【０１２４】
次に、テーブル生成部１１３は、処理対象ポリゴンがクリッピング終了時の分割ポリゴンであるか否かを判定する（Ｓ１３１）。処理対象ポリゴンがクリッピング終了時の分割ポリゴンでない場合（Ｓ１３１でＮｏ）、テーブル生成部１１３は、分割前のポリゴンを構成する他の分割ポリゴンをまだ参照する必要がある。よって、テーブル生成部１１３は、次のポリゴンを処理対象ポリゴンとして選択し（Ｓ１２１）、ステップＳ１２２以降の処理を実行する。
【０１２５】
一方、処理対象ポリゴンがクリッピング終了時の分割ポリゴンである場合（Ｓ１３１でＹｅｓ）、その時点で保持されている最小領域ＩＤと最大領域ＩＤとの組は、分割前の一つのポリゴンのバウンダリボックスを示す。よって、テーブル生成部１１３は、この最小領域ＩＤ及び最大領域ＩＤを、ポリゴン別領域テーブル１３６に含まれる一つのエントリに格納する（Ｓ１３２）。
【０１２６】
このように、テーブル生成部１１３は、処理対象ポリゴンに対してクリッピング処理が行われた場合、複数の分割ポリゴンの全てを含む第１領域を計算し、計算された第１領域の少なくとも一部を含む分割領域を示す領域情報を、複数のエントリのうちの一つに格納する。
【０１２７】
ステップＳ１２８又はステップＳ１３２の後、テーブル生成部１１３は、統合処理を行う（Ｓ１３３）。なお、この統合処理については後述する。
【０１２８】
上記の処理が描画対象の全てのポリゴンに対して完了していない場合（Ｓ１３４でＮｏ）、次のポリゴンが選択され（Ｓ１２１）、選択されたポリゴンに対してステップＳ１２２以降の処理が実行される。
【０１２９】
以下、統合処理（Ｓ１３３）について説明する。
【０１３０】
図１３Ａは、描画対象のポリゴンの一例を示す図である。図１３Ｂは、その場合のポリゴン別領域テーブル１３６を示す図である。
【０１３１】
上記のように計算された領域情報は、ポリゴン別領域テーブル１３６に登録される。ここで、ポリゴン別領域テーブル１３６は固定数（ＴＭＡＸ）のエントリを有するテーブルである。元のポリゴンがＴＭＡＸ以下の場合は、図１３Ｂに示すように、一つのエントリにつき元の１個のポリゴンの領域情報が保持される。一方、ポリゴン数がＴＭＡＸを超える場合には、一つのエントリに複数のポリゴンの領域情報を保持する必要がある。
【０１３２】
図１４は、統合処理（Ｓ１３３）のフローチャートである。また、図１５Ａ〜図１５Ｃは、この統合処理を説明するための図である。なお、以下では、説明を簡潔にするためにＴＭＡＸ＝８であり、複数のポリゴンには、その入力順にポリゴン０、ポリゴン１、・・・と昇順のポリゴン番号が付加される場合を説明する。
【０１３３】
まず、テーブル生成部１１３は、処理対象ポリゴンのポリゴン番号がＴＭＡＸより大きいか否かを判定する（Ｓ１４１）。
【０１３４】
ポリゴン番号がＴＭＡＸ以下の場合（Ｓ１４１でＮｏ）、テーブル生成部１１３は、統合処理を行なわず、一つのエントリにつき一つのポリゴンの領域情報を、エントリ０から昇順に格納する（図１５Ａ）。
【０１３５】
一方、ポリゴン数がＴＭＡＸを超える場合（Ｓ１４１でＹｅｓ）、テーブル生成部１１３は統合処理を行う。例えば、ポリゴン８が入力された場合、ポリゴン数がエントリ数を超えてしまうため一つのエントリにつき一つのポリゴンの領域情報を保持することができない。まず、テーブル生成部１１３は、統合先のエントリを選択する（Ｓ１４２）。例えば、テーブル生成部１１３は、領域情報に対応するポリゴンの数である登録ポリゴン数が最も少なく、かつ最もエントリ番号が小さいエントリ０を選択する。
【０１３６】
次に、テーブル生成部１１３は、選択したエントリに保持されている領域情報で示されるバウンダリボックスと、処理対象ポリゴンのバウンダリボックスとを統合する（Ｓ１４３）。具体的には、テーブル生成部１１３は、エントリ０に保持されているポリゴン０（ポリゴン４４１）の領域情報を読み出し、ポリゴン０のバウンダリボックスと、処理対象のポリゴン８（ポリゴン４４２）のバウンダリボックスとの和集合であるバウンダリボックス４４３を算出する。
【０１３７】
次に、テーブル生成部１１３は、算出したバウンダリボックス４４３を示す領域情報を、統合後の領域情報としてエントリ０に再格納する（Ｓ１４４）。
【０１３８】
さらに、ポリゴン９が登録される場合、テーブル生成部１１３は、登録ポリゴン数が１個であるエントリ１を選択し（Ｓ１４２）、登録されているポリゴン１の領域情報を読み出す。そして、テーブル生成部１１３は、ポリゴン９のバウンダリボックスとポリゴン１のバウンダリボックスとの和集合を計算し（Ｓ１４３）、計算により得られた統合後のバウンダリボックスの領域情報をエントリ１に再格納する（Ｓ１４４）。
【０１３９】
すなわち、処理対象ポリゴンＮが登録される場合、テーブル生成部１１３は、エントリ（Ｎ％ＴＭＡＸ）に保持されている領域情報で示されるバウンダリボックスと、ポリゴンＮのバウンダリボックスとの和集合を計算し、計算により得られた統合後のバウンダリボックスを示す領域情報を、エントリ（Ｎ％ＴＭＡＸ）に再格納する。これにより、大量のポリゴンの領域情報を、予め定められた固定容量のポリゴン別領域テーブル１３６に保持することが可能となる。
【０１４０】
このように、テーブル生成部１１３は、ポリゴンの数が、固定数ＴＭＡＸより多い場合には、複数のポリゴンを、各々が１以上のポリゴンを含むＴＭＡＸ個のグループに分割する。そして、テーブル生成部１１３は、ＴＭＡＸ個のグループの各々に対して、スクリーン座標を用いて、二次元平面において当該グループに含まれる複数のポリゴンを含む第２領域を計算する。次に、テーブル生成部１１３は、複数の分割領域のうち、当該第２領域の少なくとも一部を含む分割領域を判定する。次に、テーブル生成部１１３は、各グループに、当該グループに対応する第２領域の少なくとも一部を含む分割領域が対応付けられたテーブルであるポリゴン別領域テーブル１３６を生成する。この場合、判定部１２１は、複数の分割領域毎に、複数のポリゴンのうち、ポリゴン別領域テーブル１３６において、処理対象の分割領域が対応付けられているグループに含まれるポリゴンである描画対象ポリゴンを判定する。
【０１４１】
より具体的には、テーブル生成部１１３は、複数のポリゴンのいずれかを、処理対象ポリゴンとして順次選択する。そして、テーブル生成部１１３は、選択された処理対象ポリゴン毎に、当該処理対象ポリゴンに対する領域情報を生成するとともに、当該領域情報を複数のエントリのうち領域情報が保持されていないエントリに格納する。また、テーブル生成部１１３は、新たなポリゴンの領域情報をエントリに格納する際に、当該領域情報を格納することにより、ポリゴン別領域テーブル１３６に格納される領域情報の数が固定数ＴＭＡＸを超えるか否かを判定する。テーブル生成部１１３は、領域情報の数が固定数ＴＭＡＸを超える場合には、複数のエントリのいずれかである選択エントリに格納されている領域情報と、新たなポリゴンの領域情報とを用いて、選択エントリに格納されている領域情報に対応するポリゴンと、新たなポリゴンとを含む第２領域を計算する。次に、テーブル生成部１１３は、計算された第２領域の少なくとも一部を含む分割領域を示す領域情報を、選択エントリに格納する。
【０１４２】
なお、ここでは複数のポリゴンには、その入力順にポリゴン０、ポリゴン１、・・・と昇順のポリゴン番号が付加される場合を説明したが、ポリゴンごとに、入力順に依存しない固有の識別番号Ｎが与えられていてもよい。この場合には以下のような処理が行われる。
【０１４３】
まず、テーブル生成部１１３は、処理対象ポリゴンの識別番号ＮがＴＭＡＸより大きいか否かを判定する。識別番号ＮがＴＭＡＸ以下の場合、テーブル生成部１１３は、統合処理を行なわず、一つのエントリにつき一つのポリゴンの領域情報を格納する。例えば、テーブル生成部１１３は、処理対象ポリゴンの領域情報を、識別番号Ｎと同じエントリ番号のエントリに格納する。
【０１４４】
一方、識別番号ＮがＴＭＡＸより大きい場合、テーブル生成部１１３は統合処理を行う。例えば、テーブル生成部１１３は、エントリ（Ｎ％ＴＭＡＸ）に保持されている領域情報で示されるバウンダリボックスと、識別番号Ｎのポリゴンのバウンダリボックスとの和集合を計算し、計算により得られた統合後のバウンダリボックスを示す領域情報を、エントリ（Ｎ％ＴＭＡＸ）に再格納する。
【０１４５】
これにより、大量のポリゴンの領域情報を、予め定められた固定容量のポリゴン別領域テーブル１３６に保持することが可能となる。
【０１４６】
なお、統合処理における領域情報の格納エントリの選択方法はこれに限ったものではない。
【０１４７】
なお、テーブル生成部１１３は、統合処理において、入力順序が連続している複数のポリゴンの領域情報を一つのエントリに保持してもよい。以下、この場合の動作を説明する。
【０１４８】
前述の統合処理では、互いに無関係なポリゴンの領域情報が統合される場合がある。これにより、統合後の領域情報の精度が悪くなりやすいという課題がある。一方、テーブル生成部１１３は、入力順序が連続している複数のポリゴンの領域情報を統合することで、表示位置が比較的近いポリゴンの領域情報を統合することができる。これにより、統合後の領域情報の精度劣化を抑えることができる。
【０１４９】
具体的には、テーブル生成部１１３は、ポリゴン数がＴＭＡＸを超える場合、超えた分に関しては一つのエントリに連続した二つのポリゴンの領域情報を保持するような統合処理を行う。さらに元のポリゴンがＴＭＡＸ×２個を超える場合、テーブル生成部１１３は、超えた分に関しては一つのエントリに連続した４ポリゴンの領域情報を保持するような統合処理を行う。さらにポリゴンがＴＭＡＸ×２Ｎを超える場合、超えた分に関しては一つのエントリに連続した２（Ｎ＋１）個のポリゴンの領域情報を保持するような統合処理を行う。
【０１５０】
図１６Ａ〜図１６Ｄ及び図１７Ａ〜図１７Ｆは、この統合処理を説明するための図である。なお、以下では、説明を簡潔にするために、ＴＭＡＸ＝８であり、複数のポリゴンには、その入力順にポリゴン０、ポリゴン１、・・・と昇順のポリゴン番号が付加される場合を説明する。また、ポリゴン数がＴＭＡＸ以下の場合、一つのエントリにつき一つのポリゴンの領域情報が、エントリ０から昇順に格納される。
【０１５１】
図１６Ａは、ポリゴン数が８個の場合のポリゴン別領域テーブル１３６を示す図である。図１６Ａに示す状態から、ポリゴンがさらに入力されてくるとポリゴン数が９個になり、ポリゴン数がエントリ数より多くなる。そこで、図１６Ｂに示すように、テーブル生成部１１３は、ポリゴン０（ポリゴン４５１：最初に入力されたポリゴン）のバウンダリボックス（（０、０）（３、２））と、ポリゴン１（ポリゴン４５２：２番目に入力されたポリゴン）のバウンダリボックス（（４、０）（４、０））とをポリゴン別領域テーブル１３６から読み出し、この二つのバウンダリボックス和集合であるバウンダリボックス４５３（（０、０）（４、２））を計算する。そして、テーブル生成部１１３は、計算したバウンダリボックス４５３を示す領域情報をマージ領域情報としてエントリ０に格納する。
【０１５２】
次に、テーブル生成部１１３は、図１６Ｃに示すように、新規入力されたポリゴン８（ポリゴン４５４）のバウンダリボックス（（０、０）（１、１））と、その次に入力されたポリゴン９（ポリゴン４５５）のバウンダリボックス（（０、１）（１、２））との和集合であるバウンダリボックス４５６（（０、０）（１、２））を計算し、バウンダリボックス４５６を示す領域情報を新規領域情報としてエントリ１に格納する。これにより、図１６Ｄに示すポリゴン別領域テーブル１３６が生成される。
【０１５３】
すなわち、テーブル生成部１１３は、ポリゴン数がエントリ数を超えた場合には、既に登録済みの二つのエントリ内容を一つのエントリにマージするとともに、マージしたポリゴンの数であるマージ数と同数の新規入力ポリゴンの領域情報の和集合を計算し、空いたエントリに格納する。これにより、ポリゴン数がエントリ数より多い場合であっても、領域情報を溢れさせることなく保持することができる。
【０１５４】
さらに、図１６Ｄの状態からポリゴン１０が登録される場合には、既にエントリ１にはマージ数と同数の２個のポリゴンの領域情報が保持されているため、テーブル生成部１１３は、次のマージ対象のエントリとしてエントリ２とエントリ３とを選択する。つまり、テーブル生成部１１３は、マージ数が最も少ない二つのエントリをマージ対象のエントリとして選択する。そして、テーブル生成部１１３は、選択した二つのエントリの領域情報をマージし、マージ後の領域情報をエントリ２に格納するとともに、新規ポリゴン１０の領域情報をエントリ３に格納する。
【０１５５】
さらに、ポリゴン１１が登録される場合、エントリ３にはまだ一つのポリゴンの領域情報しか登録されていないため、テーブル生成部１１３は、ポリゴン１０のバウンダリボックスとポリゴン１１のバウンダリボックスとの和集合を計算し、計算結果をエントリ３に格納しなおす。
【０１５６】
さらに、テーブル生成部１１３は、ポリゴン１２を登録するときには、エントリ３には既にマージ数と同じ二つのポリゴンの領域情報が保持されているため、次のマージ対象のエントリとしてエントリ４及びエントリ５を選択する。そして、テーブル生成部１１３は、選択したエントリの領域情報をマージし、マージ後の領域情報をエントリ４に格納するとともに、新規ポリゴン１２の領域情報をエントリ５に格納する。
【０１５７】
以上の処理を繰り返すと、図１７Ａに示すように全エントリの各々に二つのポリゴンの領域情報が格納される。テーブル生成部１１３は、この状態からさらにポリゴン１６を登録するときには、エントリ０及びエントリ２のバウンダリボックスを読み出し、読み出した二つのバウンダリボックスをマージする。そして、テーブル生成部１１３は、エントリ０に４個のポリゴン０〜３のマージ領域情報を格納するとともに、ポリゴン１６の領域情報をエントリ２に格納する（図１７Ｂ）。この状態から、テーブル生成部１１３は、エントリ２に、４個の新規ポリゴン１６〜１９のマージ領域情報を格納することができる。
【０１５８】
テーブル生成部１１３は、新規ポリゴン２０〜２３を登録する場合には、エントリ４及びエントリ６の領域情報をマージすることで４個のポリゴン４〜７のマージ領域情報を生成し、当該マージ領域情報をエントリ４に格納するとともに、エントリ６に新規ポリゴン２０〜２３の領域情報を格納する（図１７Ｃ）。ポリゴン数が２４個の時点で、エントリ番号が２×ｋ（ｋ＝０、１、２、３）のエントリには４個のポリゴンのマージ領域情報が保持され、２×ｋ＋１のエントリには２個のポリゴンのマージ領域情報が保持される。
【０１５９】
テーブル生成部１１３は、さらにポリゴン２４を登録するときには、まだ４個のポリゴンの領域情報が保持されていない、２個のポリゴンのマージ領域情報が保持されているエントリ（２×ｋ＋１）をマージ対象のエントリとして選択する。すなわち、テーブル生成部１１３は、エントリ１及びエントリ３の領域情報をマージすることで４個のポリゴン４〜７のマージ領域情報を生成し、当該マージ領域情報をエントリ１に格納するとともに、ポリゴン２４の領域情報をエントリ３に格納する（図１７Ｄ）。この状態から、テーブル生成部１１３は、エントリ３に、４個のポリゴン２４〜２７のマージ領域情報を格納することができる。
【０１６０】
テーブル生成部１１３は、新規ポリゴン２８〜３１を登録する場合には、エントリ５及びエントリ７の領域情報をマージすることで４個のポリゴン１２〜１５のマージ領域情報を生成し、当該マージ領域情報をエントリ５に格納するとともに、エントリ７に新規ポリゴン２８〜３１のマージ領域情報を格納する（図１７Ｅ）。図１７Ｅに示す状態では、全エントリの各々に４個のポリゴンの領域情報が格納されている。
【０１６１】
テーブル生成部１１３は、この状態からさらにポリゴン３２を登録するときには、エントリ０及びエントリ４の領域情報をマージすることで８個のポリゴン０〜７のマージ領域情報を生成し、当該マージ領域情報をエントリ０に格納するとともに、ポリゴン３２の領域情報をエントリ４に格納する（図１７Ｆ）。
【０１６２】
以上のように、テーブル生成部１１３は、新たなポリゴンの領域情報をエントリに格納する際に、当該領域情報を格納することにより、ポリゴン別領域テーブル１３６に格納される領域情報の数が固定数ＴＭＡＸを越えるか否かを判定する。領域情報の数が固定数ＴＭＡＸを超える場合には、テーブル生成部１１３は、複数のエントリに含まれる第１エントリ及び第２エントリに格納されている二つの領域情報を用いて、第１エントリに格納されている領域情報に対応するポリゴンと、第２エントリに格納されている領域情報に対応するポリゴンとを含む第２領域を計算する。次に、テーブル生成部１１３は、計算された第２領域の少なくとも一部を含む分割領域を示す領域情報を第１エントリに格納し、新たなポリゴンの領域情報を第２エントリに格納する。
【０１６３】
このように、テーブル生成部１１３は、マージした結果がポリゴン入力順になるように統合処理を行う。これにより、テーブル生成部１１３は、ポリゴンの局所性を生かすことができるので、精度劣化の少ないポリゴン別領域テーブル１３６を生成することができる。このポリゴン別領域テーブル１３６は、判定部１２１で使用される。
【０１６４】
再度、図３及び図５を用いて説明を行う。
【０１６５】
ポリゴン別領域テーブル１３６が生成された後（Ｓ１０３の後）、描画領域設定部１２３は、複数の分割領域から処理対象の分割領域を選択する（Ｓ１０４）。領域分割描画処理では、分割領域ごとにラスタライズを行うため、描画領域設定部１２３は、現在の処理対象の分割領域を示す情報を出力する。
【０１６６】
以下では、分割領域を示す情報として、テーブル生成部１１３が使用した領域ＩＤが利用される場合を例に説明する。図１０において、左上の分割領域を処理対象とする場合、描画領域設定部１２３は（ＸＩＤ、ＹＩＤ）＝（０、０）を設定し、右下の分割領域を処理対象とする場合（ＸＩＤ、ＹＩＤ）＝（７、３）を設定する。そして、描画領域設定部１２３は、判定部１２１に処理対象の分割領域を示す領域ＩＤを送る。
【０１６７】
コマンド取得部１１１Ｂは、ポリゴンデータ１３２へのポインタを含む描画コマンド１３１を取得する。コマンド取得部１１１Ａがポリゴンの描画開始コマンド４１１をフェッチし、その旨を座標変換部１１２に通知するのに対し、コマンド取得部１１１Ｂは、ポリゴンの描画開始コマンド４１１をフェッチし、その旨を判定部１２１に通知する点のみが異なる。
【０１６８】
判定部１２１は、ポリゴン別領域テーブル１３６を用いて、処理対象の分割領域に含まれるポリゴンを判定する（Ｓ１０５）。具体的には、判定部１２１は、ポリゴン別領域テーブル１３６を参照して、処理対象の分割領域内に各ポリゴンが存在するかどうかを判定し、領域外と判定されたポリゴンを消去する。
【０１６９】
ここで、座標変換部１１２が処理したポリゴンの順序及び個数と、判定部１２１が処理するポリゴンの順序及び個数は一致している必要がある、又は、ポリゴンの個数がテーブル生成時と描画時とで一致しており、かつテーブル生成時と描画時とで同一のポリゴンに対しては同一の識別番号が与えられている必要がある。以下、判定部１２１及び領域描画部１２２の動作（Ｓ１０５及びＳ１０６）を図１８のフローチャートを用いて説明する。
【０１７０】
まず、判定部１２１は、処理対象のポリゴンＮを選択する（Ｓ１６１）。具体的には、判定部１２１は、描画領域設定部１２３及びコマンド取得部１１１Ｂとからそれぞれ処理対象の分割領域を示す領域ＩＤ（ＸＩＤ、ＹＩＤ）と、ポリゴンＮ（０≦Ｎ＜全ポリゴン数）を示す情報とを取得する。
【０１７１】
次に、判定部１２１は、ポリゴンの処理順序を示すポリゴン番号Ｎを用いて、又は、ポリゴンごとに固有の識別番号Ｎを用いて、ポリゴン別領域テーブル１３６に含まれる、当該ポリゴンＮの領域情報が保持されているエントリのエントリ番号を計算する（Ｓ１６２）。この計算方法は、テーブル生成部１１３における統合処理の方法に依存する。例えば、統合処理の一例として最初に紹介した方法に基づくと、ポリゴンＮの領域情報はエントリ（Ｎ％ＴＭＡＸ）に保持されている。つまり、判定部１２１は、テーブル生成部１１３の処理手順に従い、処理対象のポリゴンの領域情報が保持されているエントリを特定する。具体的には、テーブル生成部１１３は、描画コマンド１３１に含まれる複数のポリゴンのデータの順序に従い、複数のポリゴンを、処理対象ポリゴンとして順次選択する。判定部１２１は、上記順序を用いて、複数のポリゴンと、複数のエントリに格納されている複数の領域情報とを対応付ける。または、テーブル生成部１１３は、描画コマンド１３１に含まれる複数のポリゴンに与えられた固有の識別番号Ｎに従い、複数の単位ポリゴンを、処理対象単位ポリゴンとして順次選択する。判定部１２１は、識別番号Ｎを用いて、複数のポリゴンと、複数のエントリに格納されている複数の領域情報とを対応付ける。
【０１７２】
次に、判定部１２１は、ポリゴン別領域テーブル１３６に含まれる、ステップＳ１６２で計算したエントリ番号のエントリから、処理対象のポリゴンの領域情報を取得する（Ｓ１６３）。ここでは、領域情報は二次元のバウンダリボックスを示し、具体的には、当該バウンダリボックスの最小領域ＩＤ（ｍｉｎＸＩＤ、ｍｉｎＹＩＤ）と最大領域ＩＤ（ｍａｘＸＩＤ、ｍａｘＹＩＤ）とを含む。
【０１７３】
次に、判定部１２１は、バウンダリボックス内に処理対象の分割領域が存在するか否かを判定する（Ｓ１６４）。具体的には、ｍｉｎＸＩＤ≦ＸＩＤ≦ｍａｘＸＩＤかつｍｉｎＹＩＤ≦ＹＩＤ≦ｍａｘＹＩＤを満たしていれば、処理対象の分割領域内にポリゴンＮが存在する。
【０１７４】
ポリゴンＮが処理対象の分割領域に含まれない場合（Ｓ１６４でＮｏ）、ポリゴンＮにラスタライズを行う必要がないため、判定部１２１は、当該ポリゴンＮに対する処理を行わないと判定し、ポリゴンＮを消去する（Ｓ１６５）。つまり、判定部１２１は、ポリゴンＮを、処理対象の分割領域の描画対象から除外する。
【０１７５】
一方、ポリゴンＮが処理対象の分割領域に含まれる場合（Ｓ１６４でＹｅｓ）、判定部１２１は、ポリゴンＮがラスタライズ処理の対象である可能性があるため、ポリゴンＮを描画対象であると判定し、その旨を領域描画部１２２に通知する（Ｓ１６６）。
【０１７６】
そして、領域描画部１２２は、描画対象のポリゴンに対して描画処理を行う（Ｓ１０６Ａ）。具体的には、領域描画部１２２は、描画対象のポリゴンのポリゴンデータ１３２をロードし、頂点処理、ラスタライザ処理、及び最終描画領域への転送処理を行う。すなわち、領域描画部１２２は、判定部１２１により描画対象と判定されたポリゴンに対して頂点座標だけではなく必要な頂点アトリビュートまで全てロードし、しかるべき頂点処理を行い、最終的に当該分割領域にラスタライズ処理を行う。
【０１７７】
このように、判定部１２１と領域描画部１２２とは並列に動作する。つまり、判定部１２１は、あるポリゴンの描画処理中に、後続のポリゴンに対する判定処理を行う。
【０１７８】
上記の処理が全てのポリゴンに対して完了していない場合（Ｓ１６７でＮｏ）、次のポリゴンが選択され（Ｓ１６１）、選択されたポリゴンに対してステップＳ１６２以降の処理が実行される。
【０１７９】
また、領域描画部１２２は、処理対象の分割領域に対して描画対象と判定されたポリゴンを全てラスタライズし終わったあとに、最終描画領域における処理対象の分割領域に対応するメモリ領域にラスタライズ結果である画素データ１３７を転送する。
【０１８０】
上記の処理（Ｓ１０４〜Ｓ１０６）が全ての分割領域に対して完了していない場合（Ｓ１０７でＮｏ）、次の分割領域が選択され（Ｓ１０４）、選択された分割領域に対してステップＳ１０５以降の処理が実行される。
【０１８１】
このように、ポリゴン形状処理部１１０は、描画対象の１フレーム（シーン）に対し、ポリゴン別領域テーブル１３６を生成する処理を１回だけ行う。また、領域別ポリゴン描画部１２０は、生成されたポリゴン別領域テーブル１３６を参照して、描画処理（Ｓ１０５及びＳ１０６）を分割領域の数だけ行う。
【０１８２】
以上により、本実施の形態に係る領域分割描画装置１００は、ポリゴンが属する領域情報を計算し、各ポリゴンに領域情報を対応付けたテーブルであるポリゴン別領域テーブル１３６を作成する。そして、領域分割描画装置１００は、領域分割描画処理の際にポリゴン別領域テーブル１３６を参照して、各ポリゴンが処理対象の分割領域内に存在するかどうかを判定する。領域分割描画装置１００は、処理対象の分割領域内と判定されたポリゴンに対してのみポリゴンデータをロードし、頂点処理、ラスタライザ処理及び転送処理を行う。これにより、領域分割描画装置１００は、大量の可視ポリゴンが存在する場合でも予め確保したメモリ領域サイズを超えることなく領域分割描画処理を行うことができる。その結果、メモリ帯域を大きく低減することができる。
【０１８３】
（実施の形態２）
本実施の形態では、実施の形態１に係る領域分割描画装置１００の変形例を説明する。
【０１８４】
図１９は、本実施の形態に係る領域分割描画装置２００の構成を示す図である。図２０は、領域分割描画装置２００による領域分割描画処理のフローチャートである。なお、図３及び図５と同じ要素については同じ符号を用い、説明を省略する。
【０１８５】
図１９に示す領域分割描画装置２００は、ポリゴン形状処理部２１０が備えるテーブル生成部２１３及びテーブル保持部２１４と、領域別ポリゴン描画部２２０が備える判定部２２１との機能が、図３に示すテーブル生成部１１３、テーブル保持部１１４及び判定部１２１と異なる。
【０１８６】
図２０に示すように、座標変換処理（Ｓ１０２）の後、テーブル生成部２１３は、ポリゴン別領域テーブル２３６を生成する（Ｓ２０３）。ここで、テーブル生成処理（Ｓ２０３）において、以下の点が、実施の形態１と異なる。テーブル生成部２１３は、無効フラグが付加されていないポリゴンに対してのみ領域情報の算出を行い、算出した領域情報をポリゴン別領域テーブル２３６に格納する。つまり、テーブル生成部２１３は、無効フラグが付加されているポリゴンに対しては領域情報の算出及びポリゴン別領域テーブル２３６への格納を行わない。
【０１８７】
次に、テーブル生成部２１３は、ポリゴン属性テーブル２３７を生成する（Ｓ２０８）。具体的には、テーブル生成部２１３は、各ポリゴンに無効フラグが付加されているか否かに応じて、各ポリゴンが無効フラグであるか有効フラグであるかを示すポリゴン属性を判定する。そして、テーブル生成部２１３は、ポリゴン属性を用いて、連続する同一のポリゴン属性のポリゴンの数をカウントし、ポリゴン属性が変わるたびにポリゴン属性テーブルの一つのエントリに、ポリゴン属性と、同一属性のポリゴンが連続する数との組を格納する。
【０１８８】
また、テーブル保持部２１４は、ポリゴン別領域テーブル２３６及びポリゴン属性テーブル２３７を保持する。
【０１８９】
以下、ステップＳ２０８の動作を、図２１を用いて説明する。座標変換部１１２から入力される情報５０１は、ポリゴン０〜８のスクリーン位置と無効フラグとの組である。ポリゴン０、１、６、７、８は、無効フラグが付加されていないので、有効ポリゴンであり、ポリゴン属性５０２は有効である。また、ポリゴン２、３、４、５は無効フラグが付加されているため、全ての分割領域において描画対象にならない無効ポリゴンであり、ポリゴン属性５０２は無効である。
【０１９０】
テーブル生成部２１３は、図２１に示すように有効ポリゴン０、１、６、７、８に対してのみ領域情報の計算し、当該領域情報をポリゴン別領域テーブル２３６に含まれるエントリへ格納する。一方、テーブル生成部２１３は、無効ポリゴン２、３、４、５に対しては領域情報の計算及びエントリへの登録を行わない。
【０１９１】
テーブル生成部２１３は、同一のポリゴン属性５０２がいくつ連続して続くのかを数えるカウンタを有し、（１）ポリゴン属性が切り替わるたび、（２）カウント値が、属性カウンタが保持可能な上限値になるたび、又は、（３）全ポリゴンを処理し終えた場合に、ポリゴン属性テーブルの一つのエントリに属性情報及び属性カウンタ値の組を格納する。ここで、属性情報は、無効ポリゴン又は有効ポリゴン（無効又は有効）を示す情報である。また、属性カウンタは、対応するポリゴン属性のポリゴンが連続して入力された数を示す。
【０１９２】
このように、テーブル生成部２１３は、複数のポリゴンのうち、有効ポリゴンが連続する数、及び無効ポリゴンが連続する数をカウントし、当該有効ポリゴンが連続する数、及び当該無効ポリゴンが連続する数を示すポリゴン属性テーブル２３７を生成する。
【０１９３】
図２１の例では、有効ポリゴンがポリゴン０、１と２個続き、ポリゴン属性５０２が無効に切り替わるときにポリゴン属性テーブル２３７のエントリ０に「有効、２」が格納される。次に、無効ポリゴンがポリゴン２、３、４、５と４個続き、ポリゴン属性５０２が有効に切り替わるときに、ポリゴン属性テーブル２３７のエントリ１に「無効、４」が格納される。そして有効ポリゴンがポリゴン６、７、８と３個続き全てのポリゴンが処理された後に、ポリゴン属性テーブル２３７のエントリ２に「有効、３」が格納される。
【０１９４】
このように、ポリゴン別領域テーブル２３６とは別にポリゴン属性テーブル２３７が生成されることにより、本来領域管理が不要である無効ポリゴンの領域情報のために、ポリゴン別領域テーブル２３６のエントリが用いられないようにできる。また、ポリゴン別領域テーブル２３６に、有効ポリゴンのみの領域情報を格納することで、上述した統合処理が発生しにくくなる。これにより、領域情報の精度の劣化を抑制することができる。
【０１９５】
また、このポリゴン属性テーブル２３７は判定部２２１で使用される。
【０１９６】
判定部２２１は、ポリゴン属性テーブル２３７を参照して、各ポリゴンが描画対象であるか否かを判定する（Ｓ２０９）。また、判定部２２１は、描画対象でないと判定したポリゴンを消去する。つまり、判定部２２１は、分割領域に依存せずに非描画となるポリゴンを消去する。すなわち、判定部２２１は、カリング対象となるポリゴン、及び、クリッピング処理により全頂点が最終描画領域外となるポリゴンなどを消去する。
【０１９７】
図２２は、このステップＳ２０９の処理の詳細を示すフローチャートである。
【０１９８】
まず、判定部２２１は、ポリゴン属性テーブル２３７の最初のエントリを選択する（Ｓ２２１）。具体的には、判定部２２１は、選択対象のエントリのエントリ番号ＥＮＴＲＹＩＤを０に初期化する。
【０１９９】
次に、判定部２２１は、選択したエントリ（ＥＮＴＲＹＩＤ＝０）から、属性情報及び属性カウンタ値を取得する（Ｓ２２２）。
【０２００】
次に、判定部２２１は、処理対象のポリゴンを選択する（Ｓ２２３）。次に、判定部２２１は、取得した属性情報が有効を示すか無効を示すかを判定する（Ｓ２２４）。
【０２０１】
属性情報が有効を示す場合（Ｓ２２４でＹｅｓ）、判定部２２１は、処理対象のポリゴンを有効ポリゴンと判定する（Ｓ２２５）。また、有効ポリゴンと判定されたポリゴンに対してのみ、図２０に示すステップＳ１０４以降の処理が行われる。
【０２０２】
一方、属性情報が無効を示す場合（Ｓ２２４でＮｏ）、判定部２２１は、処理対象のポリゴンを無効ポリゴンと判定し、この時点で当該ポリゴンを消去する（Ｓ２２６）。
【０２０３】
ステップＳ２２５又はＳ２２６の後、判定部２２１は、属性カウンタ値を１デクリメントする（Ｓ２２７）。
【０２０４】
次に、判定部２２１は、属性カウンタ値が０であるか否かを判定する（Ｓ２２８）。すなわち、判定部２２１は、ポリゴン属性の切り替わりが発生する否かを判定する。
【０２０５】
属性カウンタ値が０でない場合（Ｓ２２８でＮｏ）、同一属性がまだ続くため、判定部２２１は、次のポリゴンを選択し（Ｓ２２３）、選択したポリゴンに対してステップＳ２２４以降の処理を行う。
【０２０６】
一方、属性カウンタ値が０の場合（Ｓ２２８でＹｅｓ）、かつ、ポリゴン属性テーブル２３７に含まれる有効な全てのエントリに対する処理が終了していない場合（Ｓ２２９でＮｏ）、ポリゴン属性の切り替わりであるため、判定部２２１は、次のエントリを選択する（Ｓ２３０）。具体的には、判定部２２１は、ＥＮＴＲＹＩＤを１進める。そして、判定部２２１は、新たに選択されたエントリに対して、ステップＳ２２２以降の処理を行う。
【０２０７】
一方、ステップＳ２２９において、ポリゴン属性テーブル２３７に含まれる全てのエントリに対する処理が終了した場合、判定部２２１は、ポリゴン属性テーブル２３７を用いた判定処理（Ｓ２０９）を終了し、有効と判定されたポリゴンを用いてステップＳ１０４以降の処理を行う。
【０２０８】
このように、判定部２２１は、ポリゴン属性テーブル２３７を参照して、複数のポリゴンの各々が有効ポリゴンであるか、無効ポリゴンであるかを判定する。次に、判定部２２１は、ポリゴン別領域テーブル２３６を参照することで、複数の分割領域の各々に対して、有効ポリゴンのうち、当該分割領域が対応付けられているポリゴンである描画対象ポリゴンを判定する。
【０２０９】
以上により、本実施の形態に係る領域分割描画装置２００は、有効ポリゴンの領域情報のみを計算し、当該有効ポリゴンの領域情報のみをポリゴン別領域テーブル２３６に格納する。また、領域分割描画装置２００は、同一属性が連続するポリゴンの数を、無効か有効かを示す属性情報に対応付けてポリゴン属性テーブル２３７に格納する。領域分割描画装置２００は、領域分割描画の際にまずポリゴン属性テーブル２３７を参照して無効ポリゴンを消去し、その後、ポリゴン別領域テーブル２３６を参照して各分割領域に対する描画処理を行う。具体的には、領域分割描画装置２００は、各ポリゴンが処理対象の分割領域内に存在するか否かを判定し、分割領域内に存在すると判定したポリゴンに対してのみ、ポリゴンデータをロードする処理、頂点処理、ラスタライザ処理、及び転送処理を行う。
【０２１０】
このように、領域分割描画装置２００は、ポリゴン別領域テーブル２３６に無効ポリゴンの領域情報を保持しない。これにより、領域分割描画装置２００は、大量の可視ポリゴンが存在する場合における統合処理の発生を低減できるので、当該統合処理による領域情報の精度の低下を抑制できる。また、上述した実施の形態１と同様に、領域分割描画装置２００は、予め確保したメモリ領域サイズを超えることなく領域分割描画を行うことができる。これにより、領域分割描画装置２００は、メモリ帯域を低減することができる。
【０２１１】
（実施の形態３）
上記実施の形態１では、ポリゴンが属する分割領域を示す情報としてバウンダリボックスを用いる例を説明した。本実施の形態では、分割情報としてバウンダリビットを用いる例を説明する。
【０２１２】
図２３Ａは、横８個、縦４個の分割領域に分割された最終描画領域を示す図である。この場合、０から３１までの領域ＩＤを持つ３２個の分割領域が存在する。また、ポリゴン４６１は、領域ＩＤ６、７、１４、１５の領域を含む領域４７１に含まれる。ポリゴン４６２は、領域ＩＤ１６、１７、２４、２５の領域を含む領域４７２に含まれる。
【０２１３】
図２３Ｂは、図２３Ａに示す場合のポリゴン別領域テーブル１３６の例を示す図である。図２３Ｂに示すように、各ポリゴンに対応するエントリには、分割情報としてバウンダリビットが格納される。ここで、バウンダリビットとは、分割領域と同じ数のビット数の情報であり、各分割領域に１ビットが対応付けられている情報である。この例では、分割領域は３２個存在するので、バウンダリビットは３２ビットの情報である。また、各１ビットは、当該１ビットが対応付けられている分割領域が、当該エントリに対応するポリゴンを含むか否かを示す。言い換えると、各１ビットは、当該１ビットが対応付けられている分割領域が、当該エントリに対応するポリゴンに対応する第１領域を含むか否かを示す。ここで、第１領域とは、ポリゴンを含む領域である。
【０２１４】
また、この例では、１ビット情報が「１」の場合、分割領域がポリゴンを含むことを示し、１ビット情報が「０」の場合、分割領域がポリゴンを含まないことを示す。
【０２１５】
なお、ここでは、１つの分割領域毎に、１ビットが対応付けられている例を述べたが、各々が複数の分割領域を含む単位領域毎に、１ビットが対応付けられてもよい。なお、この詳細は後述する。
【０２１６】
以下、バウンダリビットを用いる場合の統合処理について説明する。バウンダリビットを用いる場合には、テーブル生成部１１３は、統合対象の二つのバウンダリビットの和を算出することで、統合後のバウンダリビットを算出する。このように、バウンダリビットを用いることで、バウンダリボックスを用いる場合に比べて、演算量を低減できる。
【０２１７】
また、バウンダリビットを用いることで、統合処理において、ポリゴンを含む領域が不必要に大きく設定されてしまうことを防ぐことができる。図２４は、図２３Ａに示す例において、バウンダリボックスを用いた統合処理を行った場合のポリゴン４６１及び４６２を含む領域４７３の例を示す図である。図２４に示すように、２つのポリゴン４６１及び４６２が離れて配置されている場合には、バウンダリボックスを用いた場合には、２つのポリゴン４６１及び４６２を含む領域４７３が大きく設定されてしまう。一方、バウンダリビットを用いた場合には、図２３Ａに示す領域４７１及び４７２がそのまま、統合後のポリゴン４６１及び４６２を含む領域として設定される。このように、バウンダリビットを用いることで、分割領域の描画処理において、不必要なポリゴンが描画対象と判定されることを防止できる。
【０２１８】
また、バウンダリビットのビット数は、予め定められたビット数に固定されることが好ましい。言い換えると、バウンダリビットのビット数は、分割領域の数が変わった場合でも一定である。以下では、バウンダリビットのビット数を、縦８個、横８個の６４ビットに固定する場合の例を説明する。
【０２１９】
図２５Ａは、縦８個、横８個の６４個の分割領域を含む最終描画領域を示す図である。この場合、６４ビットの各１ビットに一つの分割領域が対応付けられる。つまり、一つの単位領域に一つの分割領域が含まれる。
【０２２０】
図２５Ｂは、縦１６個、横８個の１２８個の分割領域を含む最終描画領域を示す図である。この場合、６４ビットの各１ビットに、縦２個の分割領域が対応付けられる。つまり、一つの単位領域に二つの分割領域が含まれる。具体的には、縦８ビットの各１ビットに縦２つの分割領域が対応付けられる。
【０２２１】
図２５Ｃは、縦１６個、横３２個の５１２個の分割領域を含む最終描画領域を示す図である。この場合、６４ビットの各１ビットに、縦２個、横４個の８個の分割領域が対応付けられる。つまり、一つの単位領域に８つの分割領域が含まれる。具体的には、縦８ビットの各１ビットに縦２つの分割領域が対応付けられ、横８ビットの各１ビットに４つの分割領域が対応付けられる。
【０２２２】
このように、バウンダリビットのビット数を固定することにより、領域情報のデータ量が増加することを抑制できる。また、テーブル生成部１１３は、描画対象のポリゴン数及び分割領域の数に存在せず、予め定められたデータ量の領域テーブルを生成することができる。
【０２２３】
ただし、バウンダリビットの１ビットに複数の分割領域を対応付ける場合に、バウンダリボックスを用いる場合に比べて、ポリゴンが含まれる領域の設定の精度が低下するという問題がある。
【０２２４】
図２６は、バウンダリボックスで示されるポリゴン４６４が含まれる領域４７５を示す図である。この領域４７５を、図２５Ｂに示すバウンダリビットで示される領域４７４と比較すると、バウンダリビットで示される領域４７４は、バウンダリボックスで示される領域４７５に比べて広く、領域４７４には余分な領域が含まれている。
【０２２５】
このように、バウンダリビットを用いる場合は、統合処理後により適切な領域を設定できる。一方で、バウンダリボックスを用いることで、分割領域の数に依存せず、領域設定の精度を維持できる。なお、バウンダリボックスを示す情報のデータ量は、分割領域の数が増加した場合に増加する可能性があるものの、その増加量は、バウンダリビットのデータ量の増加量に比べて十分に少ない。
【０２２６】
このような、各情報の長所を共に利用するために、ポリゴン別領域テーブル１３６に含まれる各領域情報は、バウンダリビットと、バウンダリボックスを示す情報との両方を含んでもよい。図２７は、領域情報が、バウンダリビットとバウンダリボックスを示す情報との両方を含む場合のポリゴン別領域テーブル１３６の一例を示す図である。
【０２２７】
また、図２８は、この場合の判定部１２１及び領域描画部１２２の動作を示すフローチャートである。図２８に示す処理は、図１８に示す処理に対して、ステップＳ１６３ＡがステップＳ１６３と異なる。また、ステップＳ１６４の代わりにステップＳ１６４Ａ及びＳ１６４Ｂを含む。なお、図１８と同様の処理に関しては、説明は省略する。
【０２２８】
ステップ１６３Ａおいて、判定部１２１は、ポリゴン別領域テーブル１３６に含まれる処理対象のポリゴンの領域情報を取得する。この領域情報には、バウンダリビットと、バウンダリボックスを示す情報とが含まれる。
【０２２９】
次に、判定部１２１は、バウンダリボックス内に処理対象の分割領域が存在するか否かを判定する（Ｓ１６４Ａ）。なお、具体的な処理内容は、実施の形態１のステップＳ１６４と同様である。
【０２３０】
処理対象の分割領域がバウンダリボックスに含まれる場合（Ｓ１６４ＡでＹｅｓ）、判定部１２１は、バウンダリビットで示される領域内に処理対象の分割領域が含まれるか否かを判定する（Ｓ１６４Ｂ）。具体的には、判定部１２１は、処理対象の分割領域に対応する１ビット情報が「１」の場合、当該分割領域がバウンダリビットで示される領域内に含まれると判定し、処理対象の分割領域に対応する１ビット情報が「０」の場合、当該分割領域がバウンダリビットで示される領域内に含まれないと判定する。
【０２３１】
バウンダリビットで示される領域内に処理対象の分割領域が含まれる場合（Ｓ１６４ＢでＹｅｓ）、判定部１２１は、処理対象のポリゴンを描画対象であると判定する（Ｓ１６６）。
【０２３２】
一方、処理対象の分割領域がバウンダリボックスに含まれない場合（Ｓ１６４ＡでＮｏ）、又は、バウンダリビットで示される領域内に処理対象の分割領域が含まれない場合（Ｓ１６４ＢでＮｏ）、判定部１２１は、処理対象のポリゴンを消去する（Ｓ１６５）。
【０２３３】
なお、ステップＳ１６４Ａ及びＳ１６４Ｂの順序はこの順序でなくてもよい。例えば、ステップＳ１６４ＢがステップＳ１６４Ａの先に行われてもよいし、一部の処理が同時に行われてもよい。
【０２３４】
このように、判定部１２１は、複数の分割領域の各々に対して、複数のポリゴンのうち、バウンダリボックスを示す第１情報により当該分割領域が対応付けられており、かつ、バウンダリビット（第２情報）により当該分割領域が対応付けられているポリゴンを、描画対象ポリゴンに判定する。
【０２３５】
これにより、当該領域分割描画装置は、統合処理後により適切な領域を設定できるとともに、分割領域の数に依存せず、領域設定の精度を維持できる。
【０２３６】
（実施の形態４）
本実施の形態では、ポリゴン別領域テーブル１３６に加え、ポリゴン群別領域テーブル６３６を用いる例について説明する。
【０２３７】
図２９は、本実施の形態に係る領域分割描画装置６００の構成を示す図である。図３０は、領域分割描画装置６００による領域分割描画処理のフローチャートである。なお、図３及び図５と同じ要素については同じ符号を用い、説明を省略する。
【０２３８】
図２９に示す領域分割描画装置６００は、ポリゴン形状処理部６１０が備えるテーブル生成部６１３及びテーブル保持部６１４と、領域別ポリゴン描画部６２０が備える判定部６２１との機能が、図３に示すテーブル生成部１１３、テーブル保持部１１４及び判定部１２１と異なる。図３０に示す処理は、図５に示す処理に対して、ステップＳ６０１及びＳ６０２が追加されている。また、ステップＳ１０５ＡがステップＳ１０５と異なる。
【０２３９】
図３０に示すように、ポリゴン別領域テーブルの生成処理（Ｓ１０３）の後、テーブル生成部６１３は、ポリゴン群別領域テーブル６３６を生成する（Ｓ６０１）。
【０２４０】
図３１は、ポリゴン群の一例を示す図である。図３１に示すポリゴン群４８５は、４つのポリゴン４８１〜４８４を含む。ここで、ポリゴン群とは、例えば、一つのオブジェクトに対応し、当該オブジェクトに含まれる複数のポリゴンの集合である。つまり、ポリゴン群は、近接（又は隣接）して配置される複数のポリゴンを含む。
【０２４１】
図３２は、ポリゴン群別領域テーブル６３６の一例を示す図である。図３２に示すようにポリゴン群別領域テーブル６３６は、複数のエントリを含む。なお、エントリの数は１以上であればよい。各エントリは、一つのポリゴン群に対応し、対応するポリゴン群の領域情報と、当該ポリゴン群に含まれるポリゴンの数を含む。
【０２４２】
なお、ポリゴンの統合処理が行われる場合には、各エントリは、上記ポリゴンの数の代わり、又は上記ポリゴンの数に加えて、エントリの数を含んでもよい。ここでエントリの数とは、ポリゴン群に含まれるポリゴンがポリゴン別領域テーブル１３６において割り当てられているエントリの数である。
【０２４３】
また、ここでは、一つのポリゴン群に対する処理のみを説明するが、ポリゴン群は複数であってもよい。また、複数のポリゴン群に対する処理として、上述した複数のポリゴンに対する処理と同様の処理（統合処理等）を行ってもよい。
【０２４４】
また、ここでは、実施の形態１と同様に領域情報としてバウンダリボックスを示す情報を用いる例を示すが、上記実施の形態３と同様に、バウンダリビットが用いられてもよいし、これらの両方が用いられてもよい。
【０２４５】
例えば、テーブル生成部６１３は、ポリゴン群別領域テーブル６３６に含まれる、ポリゴン群４８５に含まれる複数のポリゴン４８１〜４８４の領域情報を用いて、統合処理と同様の方法により、ポリゴン群４８５の領域情報（バウンダリボックス４９５）を算出する。
【０２４６】
なお、バウンダリビットを用いる場合には、複数のポリゴン４８１〜４８４が含まれる領域４９１〜４９４をあわせた領域が、ポリゴン群４８５の領域情報で示される。
【０２４７】
次に、描画領域設定部１２３は、複数の分割領域から処理対象の分割領域を選択する（Ｓ１０４）。
【０２４８】
次に、判定部６２１は、ポリゴン群別領域テーブル６３６を用いて、処理対象の分割領域に含まれるポリゴン群を判定する（Ｓ６０２）。具体的には、判定部６２１は、ポリゴン群別領域テーブル６３６を参照して、処理対象の分割領域内に各ポリゴン群が存在するかどうかを判定し、領域外と判定されたポリゴン群を消去する。
【０２４９】
以下、図３３を用いて、ポリゴン群別領域テーブル６３６を用いた判定処理（Ｓ６０２）について説明する。図３３は、ポリゴン群別領域テーブル６３６を用いた判定処理（Ｓ６０２）のフローチャートである。
【０２５０】
まず、判定部６２１は、処理対象のポリゴン群を選択する（Ｓ６１１）。次に、判定部６２１は、ポリゴン群別領域テーブル６３６に含まれる、処理対象のポリゴン群の領域情報を取得する（Ｓ６１２）。
【０２５１】
次に、判定部６２１は、領域情報で示される領域（バウンダリボックス）内に処理対象の分割領域が存在するか否かを判定する（Ｓ６１３）。
【０２５２】
処理対象のポリゴン群が処理対象の分割領域に含まれない場合（Ｓ６１３でＮｏ）、判定部６２１は、当該ポリゴン群に対する処理を行わないと判定し、当該ポリゴン群を消去する（Ｓ６１５）。
【０２５３】
一方、処理対象のポリゴン群が処理対象の分割領域に含まれる場合（Ｓ６１３でＹｅｓ）、判定部６２１は、当該ポリゴン群を描画対象であると判定する（Ｓ６１４）。
【０２５４】
上記の処理が全てのポリゴン群に対して完了していない場合（Ｓ６１６でＮｏ）、次のポリゴン群が選択され（Ｓ６１１）、選択されたポリゴン群に対してステップＳ６１２以降の処理が実行される。
【０２５５】
上記の処理が全てのポリゴン群に対して完了した場合（Ｓ６１６でＹｅｓ）、次に、図３０のステップＳ１０５Ａが行われる。
【０２５６】
ステップＳ１０５Ａでは、判定部６２１は、ポリゴン別領域テーブル１３６を用いて、描画対象と判定されたポリゴン群に含まれるポリゴンのうち描画対象のポリゴンを判定する。なお、この処理は、判定対象のポリゴンが描画対象と判定されたポリゴン群に含まれるポリゴンである点を除き、実施の形態１のステップＳ１０５（図１８）と同様である。
【０２５７】
ただし、ポリゴン群単位でデータが消去された場合には、図１８のステップＳ１６２において、ポリゴン別領域テーブル１３６に含まれる、処理対象のポリゴンの領域情報が保持されているエントリのエントリ番号を計算できない場合がある。これに対して、判定部６２１は、ポリゴン群別領域テーブル６３６に含まれる、ポリゴン群に含まれるポリゴンの数（又はエントリの数）を用いることで、処理対象のポリゴンの領域情報が保持されているエントリのエントリ番号を計算することができる。
【０２５８】
以上により、テーブル生成部６１３は、領域テーブルとして、（ｉ）各ポリゴン群に、当該ポリゴン群を含む第１領域の少なくとも一部を含む分割領域が対応付けられたテーブルであるポリゴン群別領域テーブル６３６（第１領域テーブル）と、（ｉｉ）各ポリゴンに、当該ポリゴンを含む第１領域の少なくとも一部を含む分割領域が対応付けられたテーブルであるポリゴン別領域テーブル１３６（第２領域テーブル）とを生成する。
【０２５９】
判定部６２１は、複数の分割領域の各々に対して、（ｉ）ポリゴン群別領域テーブル６３６を参照することで、複数のポリゴン群のうち、当該分割領域が対応付けられているポリゴン群である描画対象ポリゴン群を判定し、（ｉｉ）ポリゴン別領域テーブル１３６を参照することで、描画対象ポリゴン群に含まれる複数のポリゴンのうち、当該分割領域が対応付けられているポリゴンである描画対象ポリゴンを判定する。
【０２６０】
領域描画部１２２は、複数の分割領域の各々に対して、描画対象ポリゴンの頂点処理及びラスタライザ処理を行う。
【０２６１】
なお、上記説明では、判定部６２１は、全てのポリゴン群に対する判定を行った後に、描画対象と判定されたポリゴン群に含まれる全てのポリゴンに対する判定を行っているが、ポリゴン群が描画対象と判定されるごとに、当該ポリゴン群に含まれるポリゴンに対する判定を行ってもよい。つまり、判定部６２１は、ポリゴン群に対する判定と、当該ポリゴン群に含まれるポリゴンに対する判定とを、ポリゴン群単位で繰り返し行ってもよい。
【０２６２】
以上のように、領域分割描画装置６００は、ポリゴン群単位で大まかな判定を行った後に、ポリゴン単位で判定を行うことにより、判定処理の処理量を低減できる。
【０２６３】
また、ここでは、ポリゴン群別領域テーブル６３６及びポリゴン別領域テーブル１３６の両方が用いられる例を説明したが、ポリゴン群別領域テーブル６３６のみが用いられてもよい。また、ポリゴン群別領域テーブル６３６のみを用いる場合の処理は、実施の形態１の説明において、「ポリゴン」を「ポリゴン群」と置き換えた場合の処理と同様であるため、詳細な説明は省略する。ポリゴン群別領域テーブル６３６のみが用いられる場合、ポリゴン別領域テーブル１３６のみが用いられる場合に比べて、当該テーブルの容量及び生成処理の処理量を低減できるが、分割領域に含まれるポリゴンの判定の精度は低下する。
【０２６４】
ここで、１又は複数のポリゴンを含む単位を単位ポリゴンと定義する。つまり、単位ポリゴンは、一つのポリゴン又はポリゴン群である。この場合、上記各実施の形態における「ポリゴン」又は「ポリゴン群」を「単位ポリゴン」と置き換えることが可能である。
【０２６５】
以上、本発明の実施の形態に係る領域分割描画装置について説明したが、本発明は、この実施の形態に限定されるものではない。
【０２６６】
また、上記実施の形態に係る領域分割描画装置に含まれる各処理部は典型的には集積回路であるＬＳＩとして実現される。これらは個別に１チップ化されてもよいし、一部又は全てを含むように１チップ化されてもよい。
【０２６７】
また、集積回路化はＬＳＩに限るものではなく、専用回路又は汎用プロセッサで実現してもよい。ＬＳＩ製造後にプログラムすることが可能なＦＰＧＡ（Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）、又はＬＳＩ内部の回路セルの接続や設定を再構成可能なリコンフィギュラブル・プロセッサを利用してもよい。
【０２６８】
なお、上記各実施の形態において、各構成要素は、専用のハードウェアで構成されるか、各構成要素に適したソフトウェアプログラムを実行することによって実現されてもよい。各構成要素は、ＣＰＵまたはプロセッサなどのプログラム実行部が、ハードディスクまたは半導体メモリなどの記録媒体に記録されたソフトウェアプログラムを読み出して実行することによって実現されてもよい。
【０２６９】
さらに、本発明は上記プログラムであってもよいし、上記プログラムが記録された非一時的なコンピュータ読み取り可能な記録媒体であってもよい。また、上記プログラムは、インターネット等の伝送媒体を介して流通させることができるのは言うまでもない。
【０２７０】
また、上記で用いた数字は、全て本発明を具体的に説明するために例示するものであり、本発明は例示された数字に制限されない。
【０２７１】
また、ブロック図における機能ブロックの分割は一例であり、複数の機能ブロックを一つの機能ブロックとして実現したり、一つの機能ブロックを複数に分割したり、一部の機能を他の機能ブロックに移してもよい。また、類似する機能を有する複数の機能ブロックの機能を単一のハードウェア又はソフトウェアが並列又は時分割に処理してもよい。
【０２７２】
また、上記のステップが実行される順序は、本発明を具体的に説明するために例示するためのものであり、上記以外の順序であってもよい。また、上記ステップの一部が、他のステップと同時（並列）に実行されてもよい。
【０２７３】
以上、一つまたは複数の態様に係る領域分割描画装置について、実施の形態に基づいて説明したが、本発明は、この実施の形態に限定されるものではない。本発明の趣旨を逸脱しない限り、当業者が思いつく各種変形を本実施の形態に施したものや、異なる実施の形態における構成要素を組み合わせて構築される形態も、一つまたは複数の態様の範囲内に含まれてもよい。
【産業上の利用可能性】
【０２７４】
本発明は、省メモリ及び省帯域が要求される組み込み機器に用いられるグラフィックス表示方式として有用である。例えば、本発明は、携帯電話、及びテレビ等に適用できる。
【符号の説明】
【０２７５】
１００、２００、３００、６００  領域分割描画装置
１０１、３０１  ディスプレイリスト保持部
１０２、３０２  ポリゴンデータ保持部
１１０、２１０、３１０、６１０  ポリゴン形状処理部
１１１、１１１Ａ、１１１Ｂ、３１１  コマンド取得部
１１２、３１２  座標変換部
１１３、２１３、６１３  テーブル生成部
１１４、２１４、６１４  テーブル保持部
１１５  分割領域設定部
１２０、２２０、６２０  領域別ポリゴン描画部
１２１、２２１、６２１  判定部
１２２、３２２  領域描画部
１２３  描画領域設定部
１３１、３３４  描画コマンド
１３２、３３２Ｂ  ポリゴンデータ
１３２Ａ、３３２Ａ  頂点座標
１３２Ｂ  属性データ
１３５、３３５  スクリーン座標
１３６、２３６  ポリゴン別領域テーブル
１３７、３３７  画素データ
２３７  ポリゴン属性テーブル
３１３  ポリゴン領域計算部
３１４  リスト保持部
３２０  ラスタライザ処理部
３２１  ポリゴンリスト取得部
３３１  ディスプレイリスト
３３６  領域別ポリゴンリスト
４０１  最終描画領域
４０２  分割領域
４０３  内部メモリ領域
４１１  描画開始コマンド
４２１、４３１、４３２、４３３、４３４、４３５、４３６、４３７、４３８、４３９、４４１、４４２、４５１、４５２、４５４、４５５、４６１、４６２、４６４、４８１、４８２、４８３、４８４  ポリゴン
４２２Ａ、４２２Ｂ、４２２Ｃ、４２４、４２５  頂点
４２３、４４３、４５３、４５６、４９５  バウンダリボックス
４７１、４７２、４７３、４７４、４７５、４９１、４９２、４９３、４９４  領域
４８５  ポリゴン群
５０１  情報
５０２  ポリゴン属性
６３６  ポリゴン群別領域テーブル
【図１】
2014087572.tif 000003
【図２】
2014087572.tif 000004
【図３】
2014087572.tif 000005
【図４Ａ】
2014087572.tif 000006
【図４Ｂ】
2014087572.tif 000007
【図５】
2014087572.tif 000008
【図６】
2014087572.tif 000009
【図７Ａ】
2014087572.tif 000010
【図７Ｂ】
2014087572.tif 000011
【図８Ａ】
2014087572.tif 000012
【図８Ｂ】
2014087572.tif 000013
【図９】
2014087572.tif 000014
【図１０】
2014087572.tif 000015
【図１１Ａ】
2014087572.tif 000016
【図１１Ｂ】
2014087572.tif 000017
【図１２】
2014087572.tif 000018
【図１３Ａ】
2014087572.tif 000019
【図１３Ｂ】
2014087572.tif 000020
【図１４】
2014087572.tif 000021
【図１５Ａ】
2014087572.tif 000022
【図１５Ｂ】
2014087572.tif 000023
【図１５Ｃ】
2014087572.tif 000024
【図１６Ａ】
2014087572.tif 000025
【図１６Ｂ】
2014087572.tif 000026
【図１６Ｃ】
2014087572.tif 000027
【図１６Ｄ】
2014087572.tif 000028
【図１７Ａ】
2014087572.tif 000029
【図１７Ｂ】
2014087572.tif 000030
【図１７Ｃ】
2014087572.tif 000031
【図１７Ｄ】
2014087572.tif 000032
【図１７Ｅ】
2014087572.tif 000033
【図１７Ｆ】
2014087572.tif 000034
【図１８】
2014087572.tif 000035
【図１９】
2014087572.tif 000036
【図２０】
2014087572.tif 000037
【図２１】
2014087572.tif 000038
【図２２】
2014087572.tif 000039
【図２３Ａ】
2014087572.tif 000040
【図２３Ｂ】
2014087572.tif 000041
【図２４】
2014087572.tif 000042
【図２５Ａ】
2014087572.tif 000043
【図２５Ｂ】
2014087572.tif 000044
【図２５Ｃ】
2014087572.tif 000045
【図２６】
2014087572.tif 000046
【図２７】
2014087572.tif 000047
【図２８】
2014087572.tif 000048
【図２９】
2014087572.tif 000049
【図３０】
2014087572.tif 000050
【図３１】
2014087572.tif 000051
【図３２】
2014087572.tif 000052
【図３３】
2014087572.tif 000053
【手続補正書】
【提出日】平成26年1月31日(2014.1.31)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
描画領域に描画される対象である、各々が１又は複数のポリゴンを含む複数の単位ポリゴンを示す描画コマンドを取得するコマンド取得部と、
前記描画コマンドで示される複数の単位ポリゴンの各々に対して、当該単位ポリゴンの三次元空間における頂点座標を二次元平面のスクリーン座標に変換する座標変換部と、
前記複数の単位ポリゴンの各々に対して、前記スクリーン座標を用いて、前記二次元平面において当該単位ポリゴンを含む第１領域を計算し、前記描画領域が分割された複数の分割領域のうち、当該第１領域の少なくとも一部を含む分割領域を算出し、前記複数の単位ポリゴンに対する当該算出結果を用いて、各単位ポリゴンに、当該単位ポリゴンを含む第１領域の少なくとも一部を含む分割領域が対応付けられたテーブルである領域テーブルを生成するテーブル生成部と、
前記領域テーブルを参照することで、前記複数の分割領域の各々に対して、前記複数の単位ポリゴンのうち、当該分割領域が対応付けられている単位ポリゴンである描画対象単位ポリゴンを判定する判定部と、
前記複数の分割領域の各々に対して、前記描画対象単位ポリゴンの頂点処理及びラスタライザ処理を行う領域描画部とを備え、
前記領域テーブルは固定数の複数のエントリを含み、
前記テーブル生成部は、前記複数のエントリの各々に、単位ポリゴンに対応する前記第１領域の少なくとも一部を含む分割領域を示す領域情報を格納し、
前記テーブル生成部は、前記複数の単位ポリゴンの数が、前記固定数より多い場合には、
前記複数の単位ポリゴンを、各々が１以上の単位ポリゴンを含む前記固定数のグループに分割し、
前記固定数のグループの各々に対して、前記スクリーン座標を用いて、前記二次元平面において当該グループに含まれる複数の単位ポリゴンを含む第２領域を計算し、前記複数の分割領域のうち、当該第２領域の少なくとも一部を含む分割領域を算出し、
前記固定数のグループに対する当該算出結果を用いて、各グループに、当該グループに含まれる複数の単位ポリゴンを含む第２領域の少なくとも一部を含む分割領域が対応付けられたテーブルである前記領域テーブルを生成し、
前記判定部は、前記領域テーブルを参照することで、前記複数の分割領域の各々に対して、前記複数の単位ポリゴンのうち、当該分割領域が対応付けられているグループに含まれる単位ポリゴンである前記描画対象単位ポリゴンを判定する
領域分割描画装置。
【請求項２】
（削除）
【請求項３】
前記テーブル生成部は、
前記複数の単位ポリゴンのいずれかを、処理対象単位ポリゴンとして順次選択し、
選択された処理対象単位ポリゴン毎に、当該処理対象単位ポリゴンに対する前記領域情報を生成するとともに、当該領域情報を前記複数のエントリのうち前記領域情報が保持されていないエントリに格納し、
新たな単位ポリゴンの領域情報をエントリに格納する際に、当該領域情報を格納することにより、前記領域テーブルに格納される領域情報の数が前記固定数を超えるか否かを判定し、
前記領域情報の数が前記固定数を超える場合には、前記複数のエントリのいずれかである選択エントリに格納されている前記領域情報と、前記新たな単位ポリゴンの領域情報とを用いて、前記選択エントリに格納されている前記領域情報に対応する単位ポリゴンと、前記新たな単位ポリゴンとを含む前記第２領域を計算し、
計算された前記第２領域の少なくとも一部を含む分割領域を示す前記領域情報を、前記選択エントリに格納する
請求項１に記載の領域分割描画装置。
【請求項４】
前記テーブル生成部は、
前記複数の単位ポリゴンのいずれかを、処理対象単位ポリゴンとして順次選択し、
選択された処理対象単位ポリゴン毎に、当該処理対象単位ポリゴンに対する前記領域情報を生成するとともに、当該領域情報を前記複数のエントリのうち前記領域情報が保持されていないエントリに格納し、
新たな単位ポリゴンの領域情報をエントリに格納する際に、当該領域情報を格納することにより、前記領域テーブルに格納される領域情報の数が前記固定数を越えるか否かを判定し、
前記領域情報の数が前記固定数を超える場合には、前記複数のエントリに含まれる第１エントリ及び第２エントリに格納されている二つの領域情報を用いて、前記第１エントリに格納されている前記領域情報に対応する単位ポリゴンと、前記第２エントリに格納されている前記領域情報に対応する単位ポリゴンとを含む前記第２領域を計算し、
計算された前記第２領域の少なくとも一部を含む分割領域を示す前記領域情報を、前記第１エントリに格納し、
前記新たな単位ポリゴンの前記領域情報を前記第２エントリに格納する
請求項１に記載の領域分割描画装置。
【請求項５】
前記第１領域は、前記単位ポリゴンの全てを含む最小の矩形領域である
請求項１、３及び４のいずれか１項に記載の領域分割描画装置。
【請求項６】
前記領域情報は、前記第１領域の頂点のうち対角となる頂点を示す情報である
請求項５に記載の領域分割描画装置。
【請求項７】
前記領域情報は、各々が１以上の前記分割領域を含む単位領域毎に１ビットが対応付けられている、予め定められたビット数の情報であり、
前記１ビットは、当該１ビットに対応付けられている前記単位領域が、当該エントリに対応する単位ポリゴンに対応する前記第１領域の少なくとも一部を含むか否かを示す
請求項１、３及び４のいずれか１項に記載の領域分割描画装置。
【請求項８】
前記領域情報は、
前記第１領域の頂点のうち対角となる頂点を含む分割領域を示す第１情報と、
各々が複数の前記分割領域を含む単位領域毎に１ビットが対応付けられている、予め定められたビット数の第２情報とを含み、
前記１ビットは、対応付けられている前記単位領域が、当該エントリに対応する単位ポリゴンに対応する前記第１領域の少なくとも一部を含むか否かを示し、
前記判定部は、前記複数の分割領域の各々に対して、前記複数の単位ポリゴンのうち、前記第１情報により当該分割領域が対応付けられており、かつ、前記第２情報により当該分割領域を含む単位領域が対応付けられている単位ポリゴンを、前記描画対象単位ポリゴンに判定する
請求項５に記載の領域分割描画装置。
【請求項９】
前記座標変換部は、さらに、前記複数の単位ポリゴンの各々に対して、前記スクリーン座標を用いて、当該単位ポリゴンの少なくとも一部が前記描画領域に表示される有効単位ポリゴンか、当該単位ポリゴンの全てが前記描画領域に表示されない無効単位ポリゴンかを判定し、
前記テーブル生成部は、前記処理対象単位ポリゴンが無効単位ポリゴンである場合、当該処理対象単位ポリゴンが無効単位ポリゴンであることを示す前記領域情報を前記エントリに格納し、
前記判定部は、前記領域テーブルにおいて、前記領域情報が、前記処理対象単位ポリゴンが無効単位ポリゴンであることを示す場合、当該処理対象単位ポリゴンを描画対象から除外する
請求項１及び３〜８のいずれか１項に記載の領域分割描画装置。
【請求項１０】
前記座標変換部は、さらに、前記スクリーン座標を用いて、クリッピング処理を行うことで、前記単位ポリゴンを複数の分割単位ポリゴンに分割し、
前記テーブル生成部は、前記処理対象単位ポリゴンに対してクリッピング処理が行われた場合、前記複数の分割単位ポリゴンの全てを含む前記第１領域を計算し、
計算された前記第１領域の少なくとも一部を含む分割領域を示す前記領域情報を、前記複数のエントリのうちの一つに格納する
請求項１及び３〜９のいずれか１項に記載の領域分割描画装置。
【請求項１１】
前記テーブル生成部は、前記描画コマンドに含まれる前記複数の単位ポリゴンのデータの順序に従い、前記複数の単位ポリゴンを、処理対象単位ポリゴンとして順次選択し、
前記判定部は、前記順序を用いて、前記複数の単位ポリゴンと、前記複数のエントリに格納されている複数の前記領域情報とを対応付ける
請求項１に記載の領域分割描画装置。
【請求項１２】
前記テーブル生成部は、前記描画コマンドに含まれる前記複数の単位ポリゴンに与えられた固有の識別番号に従い、前記複数の単位ポリゴンを、処理対象単位ポリゴンとして順次選択し、
前記判定部は、前記識別番号を用いて、前記複数の単位ポリゴンと、前記複数のエントリに格納されている複数の前記領域情報とを対応付ける
請求項１に記載の領域分割描画装置。
【請求項１３】
前記座標変換部は、さらに、前記複数の単位ポリゴンの各々に対して、前記スクリーン座標を用いて、当該単位ポリゴンの少なくとも一部が前記描画領域に表示される有効単位ポリゴンか、当該単位ポリゴンの全てが前記描画領域に表示されない無効単位ポリゴンかを判定し、
前記テーブル生成部は、さらに、前記複数の単位ポリゴンのうち、前記有効単位ポリゴンが連続する数、及び前記無効単位ポリゴンが連続する数をカウントし、当該有効単位ポリゴンが連続する数、及び当該無効単位ポリゴンが連続する数を示すポリゴン属性テーブルを生成し、
前記判定部は、
さらに、前記ポリゴン属性テーブルを参照して、前記複数の単位ポリゴンの各々が前記有効単位ポリゴンであるか、前記無効単位ポリゴンであるかを判定し、
前記領域テーブルを参照することで、前記複数の分割領域の各々に対して、前記有効単位ポリゴンのうち、当該分割領域が対応付けられている単位ポリゴンである前記描画対象単位ポリゴンを判定する
請求項１及び３〜１２のいずれか１項に記載の領域分割描画装置。
【請求項１４】
前記単位ポリゴンは、複数のポリゴンを含むポリゴン群であり、
前記テーブル生成部は、前記領域テーブルとして、（ｉ）各ポリゴン群に、当該ポリゴン群を含む第１領域の少なくとも一部を含む分割領域が対応付けられたテーブルである第１領域テーブルと、（ｉｉ）各ポリゴンに、当該ポリゴンを含む第１領域の少なくとも一部を含む分割領域が対応付けられたテーブルである第２領域テーブルとを生成し、
前記判定部は、前記複数の分割領域の各々に対して、
前記第１領域テーブルを参照することで、前記複数のポリゴン群のうち、当該分割領域が対応付けられているポリゴン群である描画対象ポリゴン群を判定し、
前記第２領域テーブルを参照することで、前記描画対象ポリゴン群に含まれる複数のポリゴンのうち、当該分割領域が対応付けられているポリゴンである描画対象ポリゴンを判定し、
前記領域描画部は、前記複数の分割領域の各々に対して、前記描画対象ポリゴンの頂点処理及びラスタライザ処理を行う
請求項１に記載の領域分割描画装置。
【請求項１５】
描画領域に描画される対象である、各々が１又は複数のポリゴンを含む複数の単位ポリゴンを示す描画コマンドを取得するコマンド取得ステップと、
前記描画コマンドで示される複数の単位ポリゴンの各々に対して、当該単位ポリゴンの三次元空間における頂点座標を二次元平面のスクリーン座標に変換する座標変換ステップと、
前記複数の単位ポリゴンの各々に対して、前記スクリーン座標を用いて、前記二次元平面において当該単位ポリゴンを含む第１領域を計算し、前記描画領域が分割された複数の分割領域のうち、当該第１領域の少なくとも一部を含む分割領域を算出し、前記複数の単位ポリゴンに対する当該算出結果を用いて、各単位ポリゴンに、当該単位ポリゴンを含む第１領域の少なくとも一部を含む分割領域が対応付けられたテーブルである領域テーブルを生成するテーブル生成ステップと、
前記領域テーブルを参照することで、前記複数の分割領域の各々に対して、前記複数の単位ポリゴンのうち、当該分割領域が対応付けられている単位ポリゴンである描画対象単位ポリゴンを判定する判定ステップと、
前記複数の分割領域の各々に対して、前記描画対象単位ポリゴンの頂点処理及びラスタライザ処理を行う領域描画ステップとを含み、
前記領域テーブルは固定数の複数のエントリを含み、
前記テーブル生成ステップでは、前記複数のエントリの各々に、単位ポリゴンに対応する前記第１領域の少なくとも一部を含む分割領域を示す領域情報を格納し、
前記テーブル生成ステップでは、前記複数の単位ポリゴンの数が、前記固定数より多い場合には、
前記複数の単位ポリゴンを、各々が１以上の単位ポリゴンを含む前記固定数のグループに分割し、
前記固定数のグループの各々に対して、前記スクリーン座標を用いて、前記二次元平面において当該グループに含まれる複数の単位ポリゴンを含む第２領域を計算し、前記複数の分割領域のうち、当該第２領域の少なくとも一部を含む分割領域を算出し、
前記固定数のグループに対する当該算出結果を用いて、各グループに、当該グループに含まれる複数の単位ポリゴンを含む第２領域の少なくとも一部を含む分割領域が対応付けられたテーブルである前記領域テーブルを生成し、
前記判定ステップでは、前記領域テーブルを参照することで、前記複数の分割領域の各々に対して、前記複数の単位ポリゴンのうち、当該分割領域が対応付けられているグループに含まれる単位ポリゴンである前記描画対象単位ポリゴンを判定する
領域分割描画方法。
【請求項１６】
請求項１５記載の領域分割描画方法をコンピュータに実行させるための
プログラム。
【請求項１７】
描画領域に描画される対象である、各々が１又は複数のポリゴンを含む複数の単位ポリゴンを示す描画コマンドを取得するコマンド取得部と、
前記描画コマンドで示される複数の単位ポリゴンの各々に対して、当該単位ポリゴンの三次元空間における頂点座標を二次元平面のスクリーン座標に変換する座標変換部と、
前記複数の単位ポリゴンの各々に対して、前記スクリーン座標を用いて、前記二次元平面において当該単位ポリゴンを含む第１領域を計算し、前記描画領域が分割された複数の分割領域のうち、当該第１領域の少なくとも一部を含む分割領域を算出し、前記複数の単位ポリゴンに対する当該算出結果を用いて、各単位ポリゴンに、当該単位ポリゴンを含む第１領域の少なくとも一部を含む分割領域が対応付けられたテーブルである領域テーブルを生成するテーブル生成部と、
前記領域テーブルを参照することで、前記複数の分割領域の各々に対して、前記複数の単位ポリゴンのうち、当該分割領域が対応付けられている単位ポリゴンである描画対象単位ポリゴンを判定する判定部と、
前記複数の分割領域の各々に対して、前記描画対象単位ポリゴンの頂点処理及びラスタライザ処理を行う領域描画部とを備え、
前記領域テーブルは固定数の複数のエントリを含み、
前記テーブル生成部は、前記複数のエントリの各々に、単位ポリゴンに対応する前記第１領域の少なくとも一部を含む分割領域を示す領域情報を格納し、
前記テーブル生成部は、前記複数の単位ポリゴンの数が、前記固定数より多い場合には、
前記複数の単位ポリゴンを、各々が１以上の単位ポリゴンを含む前記固定数のグループに分割し、
前記固定数のグループの各々に対して、前記スクリーン座標を用いて、前記二次元平面において当該グループに含まれる複数の単位ポリゴンを含む第２領域を計算し、前記複数の分割領域のうち、当該第２領域の少なくとも一部を含む分割領域を算出し、
前記固定数のグループに対する当該算出結果を用いて、各グループに、当該グループに含まれる複数の単位ポリゴンを含む第２領域の少なくとも一部を含む分割領域が対応付けられたテーブルである前記領域テーブルを生成し、
前記判定部は、前記領域テーブルを参照することで、前記複数の分割領域の各々に対して、前記複数の単位ポリゴンのうち、当該分割領域が対応付けられているグループに含まれる単位ポリゴンである前記描画対象単位ポリゴンを判定する
集積回路。
【国際調査報告】
2014087572.tif 000054
2014087572.tif 000055
2014087572.tif 000056
2014087572.tif 000057