(57)【要約】  キャッシュ資源を有効に利用することで、演算量を低減できる画像生成装置を提供する。  ポリゴンを描画することで、グラフィックス画像を生成する画像生成装置（７００）であって、頂点データのうち座標データをメモリ（２００）からロードし、ロードした座標データを座標変換する座標データ処理部（１３０）と、変換済み座標データを用いて頂点が描画の対象であるか否かを判定する判定部（１５０）と、形態データを格納するための形態データキャッシュ（７７０）と、頂点が描画の対象であると判定された場合で、かつ、形態データキャッシュ（７７０）に当該頂点の形態データが格納されていない場合には、メモリ（２００）から当該形態データをロードし、ロードした形態データを形態データキャッシュ（７７０）に格納する形態データ処理部（７６０）と、変換済み座標データと形態データとを用いて、ポリゴンを描画するポリゴン描画処理部（１８０）とを備える。
2010146828.tif 000002
【特許請求の範囲】
【請求項１】
ポリゴンを描画することで、グラフィックス画像を生成する画像生成装置であって、
ポリゴンを構成する頂点の情報を示す頂点データのうち、前記頂点の位置を示す座標データをメモリからロードし、ロードした座標データを座標変換することで、変換済み座標データを生成する座標処理部と、
前記座標処理部によって生成された変換済み座標データを用いて、前記変換済み座標データが示す頂点が描画の対象であるか否かを判定する判定部と、
前記頂点データのうち前記座標データ以外のデータである形態データを格納するための形態データキャッシュと、
前記判定部によって前記変換済み座標データが示す頂点が描画の対象であると判定された場合で、かつ、前記形態データキャッシュに当該頂点の前記形態データが格納されていない場合には、前記メモリから当該形態データをロードし、ロードした形態データを前記形態データキャッシュに格納する形態データ処理部と、
前記座標処理部によって生成された変換済み座標データと、前記形態データキャッシュに格納された形態データとを用いて、ポリゴンを描画するポリゴン描画処理部とを備える
画像生成装置。
【請求項２】
前記形態データキャッシュには、前記形態データが処理された演算済みの形態データが格納され、
前記形態データ処理部は、
前記判定部によって描画の対象であると判定された頂点の演算済みの形態データが、前記形態データキャッシュに格納されているか否かを判定する形態データ確認部と、
前記形態データ確認部によって前記演算済みの形態データが格納されていないと判定された場合に、前記メモリから前記頂点の形態データをロードする形態データロード部と、
前記形態データロード部によってロードされた形態データを処理することで、前記演算済みの形態データを生成し、生成した演算済みの形態データを前記形態データキャッシュに格納する形態データ演算部とを備える
請求項１記載の画像生成装置。
【請求項３】
前記判定部は、さらに、描画の対象であると判定した頂点のみを示す描画頂点リストを生成し、
前記形態データ確認部は、前記判定部によって生成された描画頂点リストが示す頂点の演算済みの形態データが、前記形態データキャッシュに格納されているか否かを判定する
請求項２記載の画像生成装置。
【請求項４】
前記画像生成装置は、さらに、
前記座標処理部によって生成された変換済み座標データを格納するための座標データキャッシュを備え、
前記判定部は、
前記座標データキャッシュに前記変換済み座標データが格納されている場合には、前記座標データキャッシュに格納されている変換済み座標データを用いて、当該変換済み座標データが示す頂点が描画の対象であるか否かを判定する
請求項１記載の画像生成装置。
【請求項５】
ポリゴンを描画することで、グラフィックス画像を生成する画像生成方法であって、
ポリゴンを構成する頂点の情報を示す頂点データのうち、前記頂点の位置を示す座標データをメモリからロードし、ロードした座標データを座標変換することで、変換済み座標データを生成する座標処理ステップと、
前記座標処理ステップにおいて生成された変換済み座標データを用いて、前記変換済み座標データが示す頂点が描画の対象であるか否かを判定する判定ステップと、
前記判定ステップにおいて前記変換済み座標データが示す頂点が描画の対象であると判定された場合で、かつ、前記形態データを格納するための形態データキャッシュに当該頂点の前記形態データが格納されていない場合には、前記メモリから当該形態データをロードし、ロードした形態データを前記形態データキャッシュに格納する形態データ処理ステップと、
前記座標処理ステップにおいて生成された変換済み座標データと、前記形態データキャッシュに格納された形態データとを用いて、ポリゴンを描画するポリゴン描画処理ステップとを含む
画像生成方法。
【請求項６】
ポリゴンを描画することで、グラフィックス画像を生成する集積回路であって、
ポリゴンを構成する頂点の情報を示す頂点データのうち、前記頂点の位置を示す座標データをメモリからロードし、ロードした座標データを座標変換することで、変換済み座標データを生成する座標処理部と、
前記座標処理部によって生成された変換済み座標データを用いて、前記変換済み座標データが示す頂点が描画の対象であるか否かを判定する判定部と、
前記頂点データのうち前記座標データ以外のデータである形態データを格納するための形態データキャッシュと、
前記判定部によって前記変換済み座標データが示す頂点が描画の対象であると判定された場合で、かつ、前記形態データキャッシュに当該頂点の前記形態データが格納されていない場合には、前記メモリから当該形態データをロードし、ロードした形態データを前記形態データキャッシュに格納する形態データ処理部と、
前記座標処理部によって生成された変換済み座標データと、前記形態データキャッシュに格納された形態データとを用いて、ポリゴンを描画するポリゴン描画処理部とを備える
集積回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータグラフィックス技術に関し、コンピュータグラフィックス画像を生成する画像生成技術に関するものである。
【背景技術】
【０００２】
コンピュータグラフィックス（ＣＧ：Ｃｏｍｐｕｔｅｒ  Ｇｒａｐｈｉｃｓ）画像を生成する処理は計算負荷が大きいため、リアルタイムで画像生成処理を行う情報処理装置では、中央演算処理装置（ＣＰＵ：Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）とは別に、画像生成処理を専用で行う画像生成装置（グラフィックス処理ユニット）を備えている。【０００３】
図１は、従来の一般的な画像生成装置が行う画像生成方法の処理を示すフローチャートである。【０００４】
従来の一般的な画像生成装置は、まず、入力ポリゴンモデルの頂点データを情報記憶装置（メモリ）からロードする（Ｓ１０１）。なお、頂点データは、頂点の位置を示す座標データと、座標データ以外のデータである形態データとからなる。次に、頂点データのうち座標データについてワールド座標への座標変換処理を行い、さらに、ワールド座標からディスプレイ座標への座標変換処理を行う（Ｓ１０２）。【０００５】
そして、変換座標データを用いて、ロードした頂点データから構成されるポリゴン毎に、ポリゴンが可視空間に入っているか否かを判定するクリッピング判定、あるいは、ポリゴンが視点から見て表示すべき面を向いているか否かを判定するカリング判定を行うことで、ポリゴン描画が有効かどうかの判定を行う（Ｓ１０３）。有効であると判定されたポリゴンについてのみ、ロードした頂点データのうち、座標データを除くデータ（形態データ）の処理を行う（Ｓ１０４）。【０００６】
そして、演算済みの頂点データを用いてポリゴン描画処理を行う（Ｓ１０５）。以上の処理が全てのポリゴンについて終了したかを判定し（Ｓ１０６）、終了していない場合（Ｓ１０６で「継続」）、各処理（Ｓ１０１〜Ｓ１０５）が繰り返される。全てのポリゴンについて終了した場合（Ｓ１０６で「完了」）、画像生成装置は、描画された画像を出力する（Ｓ１０７）。【０００７】
従来の一般的な画像生成方法は、上述したように、座標データに対する処理を行った後に、形態データに対する処理を行う。そして、上記のように、座標データと形態データとがセットになっているような頂点データを用いる場合には、座標データに対する処理を行う場合であっても、頂点データ、すなわち、座標データと形態データとの両方をロードする必要がある。したがって、本来は不要である形態データもロードしなければならないといった問題がある。また、形態データに対する処理を行う場合であっても、頂点データをロードする必要がある。したがって、本来は不要である座標データもロードしなければならないといった問題がある。【０００８】
したがって、特許文献１には、座標データと形態データとを分けて管理する技術が開示されている。これにより、不要な形態データ又は座標データがロードされてしまうことを防ぐことができる。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】国際公開第２００８／１２６３９２号
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、上記特許文献１では、メモリアクセス又は演算量が十分に低減されないという課題がある。例えば、キャッシュメモリを有効に利用することで、データのロード及びデータの演算の重複を避けて、メモリアクセス又は演算量を低減することができるが、特許文献１には、形態データを記憶しておく形態データキャッシュについて何も記載されていない。そして、この形態データキャッシュをうまく活用しなければ、形態データキャッシュの資源を有効に利用することができない。【００１１】
そこで、本発明は、形態データキャッシュの資源を有効に利用することで、メモリアクセス又は演算量を低減することができる画像生成装置、画像生成方法及び集積回路を提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記目的を達成するために、本発明に係る画像生成装置は、ポリゴンを描画することで、グラフィックス画像を生成する画像生成装置であって、ポリゴンを構成する頂点の情報を示す頂点データのうち、前記頂点の位置を示す座標データをメモリからロードし、ロードした座標データを座標変換することで、変換済み座標データを生成する座標処理部と、前記座標処理部によって生成された変換済み座標データを用いて、前記変換済み座標データが示す頂点が描画の対象であるか否かを判定する判定部と、前記頂点データのうち前記座標データ以外のデータである形態データを格納するための形態データキャッシュと、前記判定部によって前記変換済み座標データが示す頂点が描画の対象であると判定された場合で、かつ、前記形態データキャッシュに当該頂点の前記形態データが格納されていない場合には、前記メモリから当該形態データをロードし、ロードした形態データを前記形態データキャッシュに格納する形態データ処理部と、前記座標処理部によって生成された変換済み座標データと、前記形態データキャッシュに格納された形態データとを用いて、ポリゴンを描画するポリゴン描画処理部とを備える。【００１３】
これにより、描画に必要と判定された頂点の形態データのみが形態データキャッシュに格納されるので、描画に不要な頂点の形態データをキャッシュしなくて済み、形態データキャッシュの資源を有効に利用することができる。【００１４】
また、前記形態データキャッシュには、前記形態データが処理された演算済みの形態データが格納され、前記形態データ処理部は、前記判定部によって描画の対象であると判定された頂点の演算済みの形態データが、前記形態データキャッシュに格納されているか否かを判定する形態データ確認部と、前記形態データ確認部によって前記演算済みの形態データが格納されていないと判定された場合に、前記メモリから前記頂点の形態データをロードする形態データロード部と、前記形態データロード部によってロードされた形態データを処理することで、前記演算済みの形態データを生成し、生成した演算済みの形態データを前記形態データキャッシュに格納する形態データ演算部とを備えてもよい。【００１５】
これにより、演算済み形態データを形態データキャッシュに格納することで、形態データのロード及び演算済み形態データの生成処理が重複して実行されることを防止することができ、メモリアクセス及び演算量を低減することができる。【００１６】
また、前記判定部は、さらに、描画の対象であると判定した頂点のみを示す描画頂点リストを生成し、前記形態データ確認部は、前記判定部によって生成された描画頂点リストが示す頂点の演算済みの形態データが、前記形態データキャッシュに格納されているか否かを判定してもよい。【００１７】
これにより、描画頂点リストが示す頂点の形態データのみをロードすればよく、形態データをロードする、しないの判定を容易に実現することができる。【００１８】
また、前記画像生成装置は、さらに、前記座標処理部によって生成された変換済み座標データを格納するための座標データキャッシュを備え、前記判定部は、前記座標データキャッシュに前記変換済み座標データが格納されている場合には、前記座標データキャッシュに格納されている変換済み座標データを用いて、当該変換済み座標データが示す頂点が描画の対象であるか否かを判定してもよい。【００１９】
これにより、変換済み座標データをキャッシュに格納することで、座標データのロード及び変換済み座標データの生成処理が重複して実行されることを防止することができ、メモリアクセス及び演算量を低減することができる。【００２０】
なお、本発明は、画像生成装置として実現できるだけではなく、当該画像生成装置を構成する処理部をステップとする方法として実現することもできる。また、これらステップをコンピュータに実行させるプログラムとして実現してもよい。さらに、当該プログラムを記録したコンピュータ読み取り可能なＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ−Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）などの記録媒体、並びに、当該プログラムを示す情報、データ又は信号として実現してもよい。そして、それらプログラム、情報、データ及び信号は、インターネットなどの通信ネットワークを介して配信してもよい。【００２１】
また、上記の各画像生成装置を構成する構成要素の一部又は全部は、１個のシステムＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ：大規模集積回路）から構成されていてもよい。システムＬＳＩは、複数の構成部を１個のチップ上に集積して製造された超多機能ＬＳＩであり、具体的には、マイクロプロセッサ、ＲＯＭ及びＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）などを含んで構成されるコンピュータシステムである。
【発明の効果】
【００２２】
本発明に係る画像生成装置によれば、描画に不要な頂点の形態データをキャッシュしなくて済むので、形態データキャッシュを有効利用できるという効果が得られる。
【図面の簡単な説明】
【００２３】
【図１】図１は、従来の画像生成装置の動作を示すフローチャートである。
【図２】図２は、本実施の形態の画像生成装置の構成の一例を示すブロック図である。
【図３】図３は、本実施の形態の画像生成装置へ入力される入力データの一例を示す図である。
【図４】図４は、ポリゴン消去判定を説明するための図である。
【図５】図５は、本実施の形態の画像生成装置の動作の一例を示すフローチャートである。
【図６】図６は、本実施の形態の処理の流れを示す図である。
【図７】図７は、本実施の形態の処理における形態データアクセス頂点ＩＤの生成方法の一例を示すフローチャートである。
【図８】図８は、本実施の形態の変換済み座標データキャッシュ及び演算済み形態データキャッシュの構成の一例を示す図である。
【図９】図９は、本実施の形態の画像生成装置の各処理部でのデータの流れを示す図である。
【図１０Ａ】図１０Ａは、ポリゴンストリップ形式のポリゴン描画に、本実施の形態の画像生成装置を適用する場合のデータ変換例を示す図である。
【図１０Ｂ】図１０Ｂは、ポリゴンファン形式のポリゴン描画に、本実施の形態の画像生成装置を適用する場合のデータ変換例を示す図である。
【図１０Ｃ】図１０Ｃは、独立ポリゴン形式のポリゴン描画に、本実施の形態の画像生成装置を適用する場合のデータ変換例を示す図である。
【図１１】図１１は、本実施の形態の変形例に係る画像生成装置の構成の一例を示すブロック図である。
【図１２】図１２は、本実施の形態の変形例に係る画像生成装置の構成の別の一例を示すブロック図である。
【図１３】図１３は、本実施の形態の画像生成装置を備える情報処理装置の構成を示すブロック図である。
【発明を実施するための形態】
【００２４】
以下、本発明の実施の形態における画像生成装置及び画像生成方法について、図面を参照しながら説明する。
【００２５】
本発明の実施の形態における画像生成装置は、頂点がポリゴン描画に必要とされるか否かを判定し、必要と判定された頂点のみに対応する演算済み形態データが形態データキャッシュに記憶されているか否かを判断する。形態データキャッシュに記憶されていない場合には、形態データをメモリからロードした後に、ロードした形態データを処理することで、演算済み形態データを生成し、形態データキャッシュに記憶する。また、形態データキャッシュに記憶されている場合には、形態データキャッシュに記憶されている演算済み形態データを用いてポリゴンを描画する。
【００２６】
つまり、ポリゴン描画に必要とされた頂点のみに対応する演算済み形態データを形態データキャッシュにキャッシュすることで、形態データキャッシュの資源を有効に利用することができるという効果が得られる。
【００２７】
次に、本発明の実施の形態における画像生成装置の構成について説明する。
【００２８】
図２は、本実施の形態の画像生成装置１００の構成の一例を示すブロック図である。同図の画像生成装置１００は、ポリゴンを描画することで、グラフィックス画像を生成する装置である。具体的には、画像生成装置１００は、ポリゴン描画に関する入力データ２０１を保持するメモリ２００から必要なデータを読み出す（ロードする）ことにより、ポリゴン描画を実行する装置である。まず、メモリ２００が格納する入力データ２０１について、以下に説明する。
【００２９】
図３は、本実施の形態の画像生成装置１００へ入力される入力データ２０１の一例を示す図である。同図に示すように、入力データ２０１は、描画命令リスト２０２と、入力ポリゴンモデルの頂点データリスト２０３とから構成される。
【００３０】
描画命令リスト２０２は、ポリゴン描画命令に関する様々な情報を示す描画命令２０４を含む。図３に示すように、描画命令２０４は、入力ポリゴンの表現形式（ポリゴンストリップ、ポリゴンファン、ポリゴンメッシュ及び独立ポリゴンなど）、各パラメータのロード設定（各種データのアドレス設定）、及び、描画オプションなどを示す。
【００３１】
頂点データリスト２０３は、入力ポリゴンモデルの頂点データのリストであり、頂点ＩＤリスト２０５と、座標データリスト２０６と、形態データリスト２０７とから構成される。なお、頂点データとは、ポリゴンを構成する頂点の情報を示すデータであり、座標データと形態データとからなる。座標データとは、頂点の位置を示すデータである。形態データとは、座標データ以外のデータである。
【００３２】
図３に示すように、頂点データリスト２０３は、頂点ＩＤリスト２０５と、座標データリスト２０６と、形態データリスト２０７とへ分割して、それぞれ別のメモリ領域に格納してもよい。これにより、一度のメモリアクセスでメモリアドレスが連続する領域のデータを一括して多くロードするバーストメモリアクセスによって、頂点データリスト２０３をロードする場合に、座標データとともに不要と判定された形態データまでロードしてしまうことを防ぐことができ、メモリアクセス効率を高めることができる。
【００３３】
頂点ＩＤリスト２０５は、入力ポリゴンモデルの各頂点のＩＤを示す頂点ＩＤ２０８のリストである。頂点ＩＤ２０８は、頂点の座標データ及び形態データを紐付けするＩＤであり、各頂点ＩＤ２０８に対してそれぞれ座標データ及び形態データが存在する。頂点ＩＤ２０８は、例えば、描画命令２０４の頂点ＩＤアドレス設定が示すアドレス又はポインタが示す位置に格納されている。
【００３４】
座標データリスト２０６は、入力ポリゴンモデルの各頂点の位置を示す座標データ２０９のリストである。座標データ２０９は、１頂点あたり２〜４ワードで表現することができる。座標データ２０９は、例えば、描画命令２０４の座標データアドレス設定が示すアドレス又はポインタが示す位置に格納されている。
【００３５】
形態データリスト２０７は、各頂点の座標データ以外の情報を示す形態データ２１０のリストである。図３には、形態データ２１０の一例として、各頂点の法線データ、カラーデータ、及び、テクスチャ座標データを示すが、描画オプションによって増減があり、複雑なシーンの描画を行う場合は、形態データ２１０は、１頂点あたり数十ワードにもなる。形態データ２１０の法線データ、カラーデータ、及び、テクスチャ座標データはそれぞれ、描画命令２０４の法線データアドレス設定、カラーデータアドレス設定、及び、テクスチャ座標データアドレス設定が示すアドレス又はポインタが示す位置に格納されている。
【００３６】
図２の画像生成装置１００は、ホストインタフェース１１０と、制御部１２０と、座標データ処理部１３０と、変換済み座標データキャッシュ１４０と、判定部１５０と、形態データ処理部１６０と、演算済み形態データキャッシュ１７０と、ポリゴン描画処理部１８０と、メモリインタフェース１９０とを備える。
【００３７】
ホストインタフェース１１０は、ＣＰＵから入力される描画開始の指示を制御部１２０へと伝える。
【００３８】
制御部１２０は、描画開始の指示を受け取るとメモリバス（図示せず）及びメモリインタフェース１９０を介して、メモリ２００から描画命令リスト２０２をロードして、描画命令２０４を座標データチェック部１３１、座標データロード部１３２及び形態データロード部１６２に伝える。
【００３９】
座標データ処理部１３０は、頂点データのうち座標データ２０９をメモリ２００からロードし、ロードした座標データ２０９を座標変換することで、変換済み座標データを生成する。図２に示すように、座標データ処理部１３０は、座標データチェック部１３１と、座標データロード部１３２と、座標変換部１３３とを備える。
【００４０】
座標データチェック部１３１は、ポリゴンを構成する頂点の変換済み座標データが変換済み座標データキャッシュ１４０に格納されているか否かを判定する。具体的には、座標データチェック部１３１は、描画命令２０４に従って頂点データリスト２０３のうち頂点ＩＤリスト２０５にアクセスし、頂点ＩＤ２０８をロードする。そして、座標データチェック部１３１は、ロードした頂点ＩＤ２０８が示す頂点の変換済み座標データが、変換済み座標データキャッシュ１４０に格納されているか否かをチェックする。そして、座標データチェック部１３１は、変換済み座標データが格納されていない場合のみ、座標データロード部１３２へ頂点ＩＤ２０８を出力する。
【００４１】
座標データロード部１３２は、座標データチェック部１３１によって変換済み座標データが格納されていないと判定された場合に、メモリ２００から当該頂点の座標データ２０９をロードする。具体的には、座標データロード部１３２は、座標データチェック部１３１から頂点ＩＤ２０８を受け取った場合、描画命令２０４に従って頂点データリスト２０３のうち座標データリスト２０６にアクセスし、頂点毎の座標データ２０９をロードして、ロードした座標データ２０９を座標変換部１３３へ出力する。
【００４２】
座標変換部１３３は、座標データロード部１３２によってロードされた座標データを座標変換することで、変換済み座標データを生成する。具体的には、座標変換部１３３は、入力された座標データ２０９に対して座標変換処理を行い、変換済み座標データを変換済み座標データキャッシュ１４０へ出力する。座標変換処理とは、座標データ２０９をワールド座標及びディスプレイ座標に変換することである。つまり、変換済み座標データは、ディスプレイ座標において頂点の位置を示す座標データである。
【００４３】
変換済み座標データキャッシュ１４０は、座標データ処理部１３０によって生成された変換済み座標データを格納するためのキャッシュメモリである。変換済み座標データキャッシュ１４０は、座標データチェック部１３１から頂点ＩＤ２０８を受け取り、該当頂点の変換済み座標データが格納されていない場合は、座標データロード部１３２及び座標変換部１３３により変換済み座標データを要求して、座標変換部１３３から出力された変換済み座標データを格納する。また、変換済み座標データキャッシュ１４０は、該当頂点の変換済み座標データが存在している場合は、これらの処理を省略して、ポリゴン消去判定部１５１へ変換済み座標データを出力する。
【００４４】
判定部１５０は、座標データ処理部１３０によって生成された変換済み座標データを用いて、変換済み座標データが示す頂点が描画の対象であるか否かを判定する。図２に示すように、判定部１５０は、ポリゴン消去判定部１５１と、頂点消去判定部１５２と、形態データアクセス頂点ＩＤ生成部１５３とを備える。
【００４５】
ポリゴン消去判定部１５１は、変換済み座標データを用いてポリゴンが描画の対象であるか否か、すなわち、ポリゴン描画が有効かどうかを示すフラグ（以下、ポリゴン描画有効フラグ）を生成する。具体的には、まず、ポリゴン消去判定部１５１は、判定対象のポリゴンを構成する頂点の変換済み座標データを用いてポリゴン描画が有効か否かの判定（以下、ポリゴン消去判定）を行う。
【００４６】
そして、ポリゴン消去判定部１５１は、判定結果に基づいてポリゴン描画有効フラグを生成して、頂点消去判定部１５２へと出力する。ポリゴン描画有効フラグは、対応するポリゴンが有効であれば真、対応するポリゴンが無効であれば偽を示す。ポリゴン消去判定の具体例については後述する。
【００４７】
頂点消去判定部１５２は、ポリゴン描画有効フラグを用いて頂点が有効かどうかを示すフラグ（以下、頂点有効フラグ）を生成する。具体的には、まず、頂点消去判定部１５２は、ポリゴン消去判定部１５１から出力されたポリゴン描画有効フラグを用いて、ポリゴン消去判定対象のポリゴンを構成する頂点が有効であるか否かを判定する。そして、判定結果に基づいて頂点有効フラグを生成して、形態データアクセス頂点ＩＤ生成部１５３へ出力する。頂点有効フラグは、対応する頂点が有効であれば真、対応する頂点が無効であれば偽を示す。
【００４８】
形態データアクセス頂点ＩＤ生成部１５３は、頂点消去判定部１５２から出力された頂点有効フラグを参照して、有効な頂点データについてのみ、座標データチェック部１３１で用いた頂点ＩＤ２０８を形態データチェック部１６１へ出力する。
【００４９】
形態データ処理部１６０は、判定部１５０によって変換済み座標データが示す頂点が描画の対象であると判定された場合で、かつ、演算済み形態データキャッシュ１７０に当該頂点の演算済み形態データが格納されていない場合には、メモリ２００から形態データ２１０をロードし、ロードした形態データ２１０を処理することで、演算済み形態データを生成する。そして、形態データ処理部１６０は、生成した演算済み形態データを演算済み形態データキャッシュ１７０に格納する。図２に示すように、形態データ処理部１６０は、形態データチェック部１６１と、形態データロード部１６２と、形態データ演算部１６３とを備える。
【００５０】
形態データチェック部１６１は、判定部１５０によって描画の対象であると判定された頂点の演算済み形態データが、演算済み形態データキャッシュ１７０に格納されているか否かを判定する。具体的には、形態データチェック部１６１は、形態データアクセス頂点ＩＤ生成部１５３から出力された頂点ＩＤ２０８を取得して、取得した頂点ＩＤ２０８が示す頂点の演算済み形態データが演算済み形態データキャッシュ１７０に格納されているか否かをチェックする。そして、形態データチェック部１６１は、演算済み形態データが格納されていない場合のみ形態データロード部１６２へ頂点ＩＤ２０８を出力する。
【００５１】
形態データロード部１６２は、形態データチェック部１６１によって演算済み形態データが格納されていないと判定された場合に、メモリ２００から当該頂点の形態データ２１０をロードする。具体的には、形態データロード部１６２は、形態データチェック部１６１から頂点ＩＤ２０８を受け取った場合、描画命令２０４に従って頂点データリスト２０３のうち形態データリスト２０７にアクセスし、形態データ２１０をロードして、ロードした形態データ２１０を変換済み座標データとともに形態データ演算部１６３へ出力する。
【００５２】
形態データ演算部１６３は、形態データロード部１６２によってロードされた形態データ２１０を処理することで、演算済み形態データを生成し、生成した演算済み形態データを演算済み形態データキャッシュ１７０へ格納する。具体的には、形態データ演算部１６３は、入力された形態データ２１０に対して形態データ演算を行い、演算済み形態データを演算済み形態データキャッシュ１７０へ出力する。
【００５３】
形態データ演算とは、光源計算を行って演算済みのカラー値を求める演算処理、テクスチャ座標計算を行って演算済みのテクスチャ座標値を求める演算処理など、上記の座標変換処理以外の頂点データに対して行う演算処理のことを指す。演算済み形態データは、上記の座標変換処理以外の演算処理が実施された演算済みの形態データである。
【００５４】
演算済み形態データキャッシュ１７０は、演算済み形態データを格納するためのキャッシュメモリである。演算済み形態データキャッシュ１７０は、形態データチェック部１６１から頂点ＩＤ２０８を受け取り、該当頂点の演算済み形態データが格納されていない場合は、形態データロード部１６２及び形態データ演算部１６３により演算済み形態データを要求して、形態データ演算部１６３から出力された演算済み形態データを格納する。また、演算済み形態データキャッシュ１７０は、該当頂点の演算済み形態データが格納されている場合は、これらの処理を省略して、ポリゴン描画処理部１８０へ変換済み座標データと演算済み形態データとを出力する。
【００５５】
ポリゴン描画処理部１８０は、座標データ処理部１３０によって生成された変換済み座標データと、形態データ処理部１６０によって処理された演算済み形態データとを用いて、ポリゴンを描画する。具体的には、ポリゴン描画処理部１８０は、入力された頂点データ（変換済み座標データ及び演算済み形態データ）を用いてポリゴン描画処理を行い、ポリゴン画像を生成する。ポリゴン描画処理は、コンピュータグラフィックス処理で用いられる一般的な処理により実行される。ポリゴン描画処理部１８０は、メモリインタフェース１９０を介して生成したポリゴン画像をメモリ２００へと出力する。
【００５６】
メモリインタフェース１９０は、画像生成装置１００が備える各処理部とメモリ２００との間でデータのやり取りを行う。
【００５７】
続いて、ポリゴン消去判定部１５１が行うポリゴン消去判定について説明する。図４は、ポリゴン消去判定を説明するための図である。ポリゴン消去判定とは、複数の頂点から構成されるポリゴンが画像生成時に用いられるか否かを判定する処理である。
【００５８】
なお、本実施の形態では、ポリゴンは３つの頂点から構成される例について説明するが、ポリゴンは４つ以上の頂点から構成されてもよい。
【００５９】
コンピュータグラフィックスの描画処理においては、各フレームの描画開始時にシーンのカットとして、ユーザの原点を表す視点３０１と、ユーザの視点３０１から見たときの視界の３次元空間を表す六面体であるビューボリューム３０２とが、それぞれ座標値としてグラフィックス処理ユニット（本実施の形態における画像生成装置１００）に与えられる。
【００６０】
ポリゴン消去判定では、視点３０１を原点とした座標系（ディスプレイ座標系）へ変換した座標データ（変換済み座標データ）を用いる。ポリゴン消去判定は、クリッピング判定及びカリング判定により行う。
【００６１】
クリッピング判定は、ユーザの視界に存在するポリゴンのみ描画するために、各ポリゴンに含まれる頂点の変換済み座標データがビューボリューム３０２の中に入っているかどうかを判定する処理である。ポリゴンを構成する頂点のうち全ての頂点の座標がビューボリューム３０２の外に存在していれば、当該ポリゴンの描画は無効となる。つまり、ポリゴンを構成する頂点のうち１つでもビューボリューム３０２内に存在していれば、当該ポリゴンの描画は有効になる。例えば、ポリゴン３０５のように完全にビューボリューム３０２の外に存在するポリゴンは、クリッピング判定により描画が無効となる。
【００６２】
一方、カリング判定は、物体を構成するポリゴンのうち物体の外側（表面）を向いたポリゴンだけを描画するために、ビューボリューム３０２の中に入っているポリゴンについて視点から見たときのポリゴン面が表向きかどうかを判定する処理である。カリング判定は、ポリゴンを構成する頂点の座標から面の向きを表す面法線ベクトルＮを求め、ポリゴンから視点方向を向いた視点方向ベクトルＶとの内積Ｎ・Ｖの符号を確認することでポリゴンの表裏を判定することができる。
【００６３】
具体的には、視点３０１から見て裏向き（Ｎ・Ｖ＜０）であれば、ポリゴン描画は無効となる。例えば、ポリゴン３０６のようにポリゴン面が視点３０１から見て裏向きであるポリゴンは、カリング判定により描画が無効となる。
【００６４】
ポリゴン３０４のように、クリッピング判定及びカリング判定で無効と判断されなかったポリゴンについてのみ、ポリゴン消去判定部１５１は、ディスプレイ面３０３に投影して描画することができる有効なポリゴンと判定する。
【００６５】
以上が、本発明の実施の形態における画像生成装置１００の構成についての説明である。
【００６６】
次に、本発明の実施の形態における画像生成装置１００の動作について説明する。
【００６７】
図５は、本実施の形態の画像生成装置１００の動作の一例を示すフローチャートである。本実施の形態の画像生成処理は、まず、ホストインタフェース１１０を介してＣＰＵから描画命令２０４を制御部１２０が受け取ることで開始する。
【００６８】
制御部１２０からの指示に基づいて、座標データチェック部１３１は、入力ポリゴンモデルの頂点データのうち頂点ＩＤ２０８のロードを行う（Ｓ２０１）。続いて、座標データチェック部１３１は、変換済み座標データキャッシュ１４０に、ロードした頂点ＩＤ２０８を用いて問い合わせを行う（Ｓ２０２）。すなわち、座標データチェック部１３１は、ロードした頂点ＩＤ２０８が示す頂点の変換済み座標データが変換済み座標データキャッシュ１４０に格納されているか否かを確認する。
【００６９】
頂点ＩＤ２０８に対応する頂点の変換済み座標データが格納されていた場合（Ｓ２０２で「データ有り」）、メモリ２００からの当該頂点の座標データ２０９のロード及び座標変換処理は実行しない。これにより、座標データをキャッシュにより再利用できるので、ロード時間の短縮になるという効果が得られる。
【００７０】
また、頂点ＩＤ２０８に対応する頂点の変換済み座標データが存在しない場合（Ｓ２０２で「データ無し」）、メモリ２００からの当該頂点の座標データ２０９のロード及び座標変換処理を実行するために、座標データロード部１３２へ頂点ＩＤ２０８を出力する。
【００７１】
座標データロード部１３２は、入力ポリゴンモデルの頂点データのうち頂点ＩＤ２０８に対応する座標データ２０９のロードを行う（Ｓ２０３）。座標変換部１３３は、ロードされた座標データ２０９をワールド座標及びディスプレイ座標へ変換することで変換済み座標データを生成し、生成した変換済み座標データを変換済み座標データキャッシュ１４０へ格納する（Ｓ２０４）。
【００７２】
ポリゴン消去判定部１５１は、判定対象のポリゴンを構成する頂点の変換済み座標データを用いてポリゴン消去判定を行う（Ｓ２０５）。具体的には、ポリゴン消去判定部１５１は、図４を用いて説明したクリッピング判定及びカリング判定を行う。
【００７３】
頂点消去判定部１５２は、判定対象の頂点を含むポリゴンのポリゴン消去判定結果、例えば、ポリゴン有効フラグを用いて頂点消去判定を行う（Ｓ２０６）。判定対象のポリゴン消去判定結果で、ポリゴン描画が有効であった場合（Ｓ２０６で「頂点が有効」）、判定対象のポリゴンに含まれる頂点は有効な頂点データであると判定する。また、ポリゴン描画が無効であった場合（Ｓ２０６で「頂点が無効」）、無効な頂点データであると判定する。
【００７４】
形態データアクセス頂点ＩＤ生成部１５３は、頂点消去判定部１５２により生成された頂点消去判定結果、例えば、頂点有効フラグを参照して、有効とされた頂点データについてのみ頂点ＩＤ２０８を形態データチェック部１６１へ出力する（Ｓ２０７）。これにより、描画に不要な頂点の形態データをキャッシュしなくて済むので、演算済み形態データキャッシュ１７０を有効利用できる。なお、形態データアクセス頂点ＩＤ生成部１５３の詳細な動作については、後で説明する。
【００７５】
そして、形態データチェック部１６１は、演算済み形態データキャッシュ１７０に、形態データアクセス頂点ＩＤ生成部１５３から受け取った頂点ＩＤ２０８を用いて問い合わせを行う（Ｓ２０８）。頂点ＩＤ２０８に対応する頂点の演算済み形態データが存在した場合（Ｓ２０８で「データ有り」）、メモリ２００からの当該頂点の形態データ２１０のロード及び形態データ演算は実行しない。
【００７６】
頂点ＩＤ２０８に対応する頂点の演算済み形態データが存在しない場合（Ｓ２０８で「データ無し」）、メモリ２００からの当該頂点の形態データ２１０のロード及び形態データ演算を実行するために、形態データロード部１６２へ頂点ＩＤ２０８を出力する。
【００７７】
形態データロード部１６２は、入力ポリゴンモデルの頂点データのうち頂点ＩＤ２０８に対応する形態データ２１０のロードを行う（Ｓ２０９）。形態データ演算部１６３は、ロードされた形態データ２１０を用いて演算を行うことで演算済み形態データを生成し、生成した演算済み形態データを演算済み形態データキャッシュ１７０へ格納する（Ｓ２１０）。
【００７８】
ポリゴン描画処理部１８０は、演算済み形態データキャッシュ１７０から受け取った頂点データ（変換済み座標データ及び演算済み形態データ）を用いて、ポリゴン描画処理を行う（Ｓ２１１）。
【００７９】
以上の処理が全てのポリゴンについて終了したかを判定し（Ｓ２１２）、終了していない場合（Ｓ２１２で「継続」）、上記の各処理（Ｓ２０１〜Ｓ２１１）が繰り返される。全てのポリゴンについて終了した場合（Ｓ２１２で「完了」）、画像生成装置１００は、描画された画像を出力する（Ｓ２１３）。
【００８０】
以上のようにして、本実施の形態の画像生成装置１００は、変換済み座標データキャッシュ１４０へは全ての頂点ＩＤによるアクセスが発生するのに対して、演算済み形態データキャッシュ１７０へのアクセスは、有効な頂点と判定された頂点に対応するものだけに限られる。このため、ポリゴン描画に使用する必要最小限の頂点データによって、キャッシュメモリを割り当てることができ、キャッシュメモリの資源を有効に利用することができる。
【００８１】
これにより、従来の画像処理装置よりもさらに、入力ポリゴンデータのロードに関するメモリアクセス量及び演算量を低減することができる。また、本実施の形態の画像生成装置１００は、画像の描画処理と並行して、頂点がポリゴン描画に必要であるか否かを判定するため、インタラクティブ用途にも適用することができる。
【００８２】
以下では、より具体的に本発明の実施の形態の画像生成装置１００について説明する。ここでは、ポリゴンの表現形式がポリゴンメッシュの場合について説明する。
【００８３】
図６は、入力ポリゴンモデルがポリゴンメッシュ形式で構成されている場合の処理の流れを示す図である。ポリゴンメッシュ形式は、内部の多くのポリゴンで頂点の共有が行われる形式である。
【００８４】
同図に示すように、ポリゴンメッシュ４０１の頂点データは、例えば、Ｐ０（Ｖ０、Ｖ１、Ｖ２）→Ｐ１（Ｖ１、Ｖ３、Ｖ２）→Ｐ２（Ｖ２、Ｖ３、Ｖ４）→Ｐ３（Ｖ０、Ｖ２、Ｖ５）→Ｐ４（Ｖ５、Ｖ２、Ｖ６）→Ｐ５（Ｖ２、Ｖ４、Ｖ６）の順で指定される。なお、ポリゴンメッシュは自由度の高い形式であり、必ずしもこの順番で指定されるとは限らない。また、図６に示す例においては、ポリゴンＰ０、Ｐ３及びＰ４が有効なポリゴンであり、ポリゴンＰ１、Ｐ２及びＰ５が無効なポリゴンであるとする。
【００８５】
タイムチャート４０２は、頂点ＩＤのロードから演算済み形態データの生成までの処理の流れを示すタイムチャートである。以下では、タイムチャート４０２に沿ってポリゴンメッシュ形式の処理の流れについて説明する。
【００８６】
座標データチェック部１３１は、頂点データのうち頂点ＩＤ  Ｖｉ（ｉ＝０〜６）のロードを行い、ロードしたＶｉを用いて変換済み座標データキャッシュ１４０へ問い合わせを行う。
【００８７】
そして、該当頂点の変換済み座標データが無い場合、座標データロード部１３２は、頂点データのうち座標データＭｉのロードを行う。次に、座標変換部１３３は、ロードされた座標データＭｉの座標変換を行うことで、変換済み座標データＤｉを生成する。そして、座標変換部１３３は、変換済み座標データＤｉを変換済み座標データキャッシュ１４０へ格納する。
【００８８】
該当頂点の変換済み座標データＤｉがある場合は、ポリゴンメッシュ上の同じ頂点の座標データを参照することになるので重複して処理を行わない。図６の例では、頂点ＩＤは、Ｖ０→Ｖ１→Ｖ２→Ｖ１→Ｖ３→Ｖ２→Ｖ２→Ｖ３→Ｖ４→Ｖ０→Ｖ２→Ｖ５→Ｖ２→Ｖ６→Ｖ５→Ｖ２→Ｖ４→Ｖ６の順にロードされるが、座標データについての処理、すなわち、座標データのロード及び座標変換は、Ｖ０→Ｖ１→Ｖ２→Ｖ３→Ｖ４→Ｖ５→Ｖ６の順に行い、重複して問い合わせのあった頂点については、再処理を行わない。つまり、座標データのロード及び座標変換は、各頂点について１回のみ実行される。
【００８９】
例えば、図６に示すように、ポリゴンＰ１に含まれる頂点のうち、座標データＭ１及びＭ２はロードされず、したがって、座標データＭ１及びＭ２の座標変換（変換済み座標データＤ１及びＤ２の生成）は実行されない。なお、これらの処理は、ポリゴンＰ０の処理時に実行されている。
【００９０】
ポリゴン消去判定部１５１は、ポリゴンＰｊ（ｊ＝０〜５）を構成する頂点の変換済み座標データＤｉを変換済み座標データキャッシュ１４０から読み出して、読み出した変換済み座標データＤｉを用いてポリゴン描画有効フラグＦＰｊを生成する。なお、上述したように、ポリゴン描画有効フラグＦＰｊは、対応するポリゴンが有効であれば真（Ｔ）、対応するポリゴンが無効であれば偽（Ｆ）である。図６の例では、ポリゴン消去判定をＰ０→Ｐ１→Ｐ２→Ｐ３→Ｐ４→Ｐ５の順に行う。
【００９１】
頂点消去判定部１５２は、ポリゴン描画有効フラグＦＰｊを用いて、頂点Ｖｋ（ｋ＝０〜１５について頂点消去判定を行う。すなわち、以下の（式１）に示すように、頂点Ｖｋが含まれる、ポリゴンのポリゴン描画有効フラグＦＰｊが真となれば、頂点Ｖｋの頂点有効フラグＦＶｋも真とする。
【００９２】
ＦＶｋ＝（ＦＰｊ＆（Ｖｋ∈Ｐｊ））    ・・・（式１）
なお、頂点消去判定において、頂点Ｖｋは、頂点消去判定部１５２にｋ＋１番目に入力された頂点ＩＤが示す頂点である。例えば、頂点消去判定において頂点Ｖ０は、１番目に入力された頂点ＩＤが示す頂点、すなわち、ポリゴンＰ０を構成する頂点Ｖ０である。また、頂点Ｖ４は、５番目に入力された頂点ＩＤが示す頂点、すなわち、ポリゴンＰ１を構成する頂点Ｖ３である。
【００９３】
したがって、図６に示すように、頂点消去判定部１５２に入力された頂点の数だけ、頂点有効フラグＦＶｋが生成される。つまり、同じ頂点について複数の頂点有効フラグＦＶｋが生成される。
【００９４】
図６の例では、頂点消去判定部１５２は、頂点Ｖｋ（ｋ＝０〜１５）についての頂点消去判定を行うとき、ポリゴン消去判定部１５１が生成したポリゴン描画有効フラグＦＰｊをＴ→Ｆ→Ｆ→Ｔ→Ｔ→Ｆの順に受け取る。そして、頂点消去判定部１５２は、ポリゴンＰｊ（ｊ＝０〜５）を構成する頂点Ｖｋ（ｋ＝０〜１５）についてそれぞれ上記の（式１）に基づいて、頂点有効フラグＦＶｋが、Ｔ→Ｔ→Ｔ→Ｆ→Ｆ→Ｆ→Ｆ→Ｆ→Ｆ→Ｔ→Ｔ→Ｔ→Ｔ→Ｔ→Ｔ→Ｆ→Ｆ→Ｆの順に生成される。
【００９５】
形態データアクセス頂点ＩＤ生成部１５３は、頂点有効フラグＦＶｋを用いて、形態データチェック部１６１にアクセスする頂点ＩＤの生成を行う。図７に形態データアクセス頂点ＩＤの生成方法のフローチャートを示す。
【００９６】
まず、形態データアクセス頂点ＩＤ生成部１５３は、座標データ処理部１３０がロードして使用した元の頂点ＩＤを取得する（Ｓ３０１）。次に、形態データアクセス頂点ＩＤ生成部１５３は、該当頂点の頂点有効フラグＦＶｋが真かどうか判定する（Ｓ３０２）。
【００９７】
頂点有効フラグＦＶｋが真ならば（Ｓ３０２で「真」）、入力された頂点ＩＤを形態データアクセス頂点ＩＤとして出力する（Ｓ３０３）。頂点有効フラグＦＶｋが偽ならば（Ｓ３０２で「偽」）、入力された頂点ＩＤを出力しない。
【００９８】
すなわち、形態データアクセス頂点ＩＤ生成部１５３は、頂点有効フラグＦＶｋが真となる頂点についてのみ、頂点ＩＤを形態データチェック部１６１へ出力する。図６の例では、形態データチェック部１６１へ出力される頂点ＩＤは、Ｖ０→Ｖ１→Ｖ２→Ｖ０→Ｖ２→Ｖ５→Ｖ２→Ｖ６→Ｖ５の順に生成される。
【００９９】
以上のように、形態データアクセス頂点ＩＤ生成部１５３は、描画の対象であると判定された頂点のみを示す描画頂点リストを生成する機能を有する。描画頂点リストは、例えば、図６に示すような、Ｖ０→Ｖ１→Ｖ２→Ｖ０→Ｖ２→Ｖ５→Ｖ２→Ｖ６→Ｖ５として示されるリストである。
【０１００】
形態データチェック部１６１は、形態データアクセス頂点ＩＤ生成部１５３が生成した頂点ＩＤ  Ｖｉ（ｉ＝０〜６）を用いて、演算済み形態データキャッシュ１７０へ問い合わせを行う。言い換えると、形態データチェック部１６１は、描画頂点リストが示す頂点の演算済み形態データが、演算済み形態データキャッシュ１７０に格納されているか否かを判定する。
【０１０１】
そして、該当頂点の演算済み形態データが無い場合、形態データロード部１６２は、頂点データのうち形態データＮｉのロードを行う。次に、形態データ演算部１６３は、ロードされた形態データのＮｉの演算を行うことで、演算済み形態データＣｉを生成する。そして、形態データ演算部１６３は、演算済み形態データＣｉを演算済み形態データキャッシュ１７０へ格納する。
【０１０２】
該当頂点の演算済み形態データＣｉがある場合は、ポリゴンメッシュ上の同じ頂点の形態データを参照することになるので重複して処理を行わない。図６の例では、頂点ＩＤは、Ｖ０→Ｖ１→Ｖ２→Ｖ０→Ｖ２→Ｖ５→Ｖ２→Ｖ６→Ｖ５の順に生成されるが、形態データについての処理、すなわち、形態データのロード及び演算は、Ｖ０→Ｖ１→Ｖ２→Ｖ５→Ｖ６の順に行い、重複して問い合わせのあった頂点については再処理を行わない。つまり、形態データのロード及び演算は、各頂点について１回のみ実行される。
【０１０３】
例えば、図６に示すように、ポリゴンＰ３に含まれる頂点のうち、形態データＮ０及びＮ２はロードされず、したがって、形態データＮ０及びＮ２の演算（演算済み形態データＣ０及びＣ２の生成）は実行されない。なお、これらの処理は、ポリゴンＰ０の処理時に実行されている。
【０１０４】
図８は、変換済み座標データキャッシュ１４０及び演算済み形態データキャッシュ１７０の構成を示す図である。各キャッシュの構成は、キャッシュメモリをキャッシュラインという単位に分けて、キャッシュライン毎に一意なエントリ番号を割り当てる。図８に示すように、各キャッシュラインは、エントリ番号と、頂点ＩＤ（キャッシュタグ）と、参照カウンタと、キャッシュライン有効フラグと、キャッシュラインメモリとを含む。
【０１０５】
エントリ番号は、キャッシュ内のデータの紐付けを行うための識別子である。頂点ＩＤ（キャッシュタグ）は、キャッシュライン内で管理されている頂点を特定する頂点ＩＤである。参照カウンタは、現在データを参照している参照頂点数をカウントするカウンタである。キャッシュライン有効フラグは、キャッシュラインに有効なデータが格納されているかどうかを示すフラグ情報である。キャッシュラインメモリは、それぞれ変換済み座標データ又は演算済み形態データを格納するデータ格納部である。
【０１０６】
参照カウンタが０のときは、キャッシュラインが空とみなして新たな頂点ＩＤの登録を行うことができる。参照カウンタは、頂点ＩＤが必要とされる度に、具体的には、頂点ＩＤの問い合わせが実行される度に、インクリメントされる。逆に、参照カウンタは、対応する変換済み座標データ又は演算済み形態データを用いてポリゴンが描画される度にデクリメントされる。図８に示す例は、図６に示すポリゴンＰ０〜Ｐ５の処理が完了し、まだポリゴンの描画が行われていない場合のキャッシュについて示している。
【０１０７】
また、キャッシュライン有効フラグが偽（Ｆ）のときは、まだ有効なデータがキャッシュラインメモリに格納されていないので、キャッシュラインメモリからのデータのロードはブロックする。
【０１０８】
図８の各キャッシュ（変換済み座標データキャッシュ１４０又は演算済み形態データキャッシュ１７０）の動作を説明する。
【０１０９】
まず、キャッシュは、頂点ＩＤの問い合わせが発生すると、参照カウンタが０でないこと、及び、キャッシュライン有効フラグが真であることのいずれかの条件を満たしたキャッシュラインの頂点ＩＤを検索することで、同じ頂点ＩＤの値を持つキャッシュラインが存在するかどうか確認する。
【０１１０】
頂点ＩＤの値が同じキャッシュラインが存在する場合は、キャッシュは、該当キャッシュラインの参照カウンタを＋１して、データの再ロード及び再計算は行わない。頂点ＩＤの値が同じキャッシュラインが存在しない場合は、キャッシュは、参照カウンタが０のキャッシュラインを検索して、問い合わせのあった頂点ＩＤを登録し、参照カウンタを１に設定する。そして、キャッシュは、キャッシュライン有効フラグを偽（Ｆ）に設定して、データのロード及び演算が行われるのを待機する。そして、演算後のデータがキャッシュに入力されると、キャッシュは、演算後のデータをキャッシュラインメモリに格納して、キャッシュライン有効フラグを真（Ｔ）に設定する。
【０１１１】
次に、ポリゴン描画の問い合わせのあった頂点ＩＤのデータをキャッシュラインメモリからロードして、ロードが完了したら該当キャッシュラインの参照カウンタを−１する。
【０１１２】
上記で説明した動作を行う図８のキャッシュで、本発明の実施の形態の処理を実行した場合、変換済み座標データキャッシュ１４０へは、頂点ＩＤリスト全てのアクセスが発生するため、ポリゴン描画の有効無効に関わらず一度は各頂点の座標データの処理が行われ、キャッシュラインメモリへの格納が行われる。一方で、演算済み形態データキャッシュ１７０へは、描画に必要な頂点の頂点ＩＤでのみアクセスが発生するため、形態データの処理及びキャッシュラインメモリへの格納は、必要最小限にのみ実行される。したがって、キャッシュラインメモリの領域を有効に利用することができ、従来の画像処理装置に比べてメモリアクセス及び演算量を低減することができる。
【０１１３】
以下では、上述した処理が実行される様子を、本実施の形態の画像生成装置１００が備える各処理部でのデータの流れに基づいて説明する。
【０１１４】
図９は、本実施の形態の画像生成装置１００が備える各処理部でのデータの流れを示す図である。同図に示すように、メモリ２００上に、入力ポリゴンモデルの頂点ＩＤリスト５０１、座標データリスト５０２及び形態データリスト５０３が配置されているとする。さらに、メモリ２００は、ポリゴン描画処理部１８０が出力する出力画像５０４も保持する。
【０１１５】
座標データチェック部１３１は、メモリ２００上の頂点ＩＤリスト５０１にアクセスして、頂点ＩＤ５０５をロードする。そして、座標データチェック部１３１は、変換済み座標データキャッシュ１４０へ問い合わせを行い、該当頂点の変換済み座標データが無い場合は、頂点ＩＤ５０５を座標データロード部１３２へ出力する。
【０１１６】
座標データロード部１３２は、メモリ２００上の座標データリスト５０２にアクセスして、頂点ＩＤ５０５に該当する座標データ５０６をロードし、ロードした座標データ５０６を座標変換部１３３へ出力する。
【０１１７】
座標変換部１３３は、座標データ５０６を座標変換することで、変換済み座標データ５０７を生成し、生成した変換済み座標データ５０７を変換済み座標データキャッシュ１４０へ格納する。
【０１１８】
ポリゴン消去判定部１５１は、変換済み座標データキャッシュ１４０から判定対象のポリゴンの頂点の頂点ＩＤ及び変換済み座標データをデータ５０８として受け取り、ポリゴン描画有効フラグを生成する。そして、ポリゴン消去判定部１５１は、頂点ＩＤ、変換済み座標データ及びポリゴン描画有効フラグをデータ５０９として頂点消去判定部１５２へ出力する。
【０１１９】
頂点消去判定部１５２は、ポリゴン消去判定部１５１から出力された頂点ＩＤ、変換済み座標データ及びポリゴン描画有効フラグ（データ５０９）を用いて頂点有効フラグを生成する。そして、頂点消去判定部１５２は、頂点ＩＤ、変換済み座標データ及び頂点有効フラグをデータ５１０として形態データアクセス頂点ＩＤ生成部１５３へ出力する。
【０１２０】
形態データアクセス頂点ＩＤ生成部１５３は、頂点消去判定部１５２から出力された頂点ＩＤ、変換済み座標データ及び頂点有効フラグ（データ５１０）を参照する。そして、形態データアクセス頂点ＩＤ生成部１５３は、頂点有効フラグが真であるときのみ、頂点ＩＤ及び変換済み座標データをデータ５１１として、形態データチェック部１６１へ出力する。
【０１２１】
形態データチェック部１６１は、形態データアクセス頂点ＩＤ生成部１５３から出力されたデータ５１１の頂点ＩＤを用いて、演算済み形態データキャッシュ１７０へ問い合わせを行う。そして、形態データチェック部１６１は、該当頂点の演算済み形態データが無い場合は、データ５１１に含まれる頂点ＩＤ及び変換済み座標データをデータ５１２として形態データロード部１６２へ出力する。
【０１２２】
形態データロード部１６２は、メモリ２００上の形態データリスト５０３にアクセスして、頂点ＩＤ及び変換済み座標データ（データ５１２）の頂点ＩＤに該当する形態データをロードする。そして、形態データロード部１６２は、変換済み座標データ及びロードした形態データをデータ５１３として形態データ演算部１６３へ出力する。
【０１２３】
形態データ演算部１６３は、変換済み座標データ及び形態データ（データ５１３）を用いて、演算済み形態データ５１４を計算する。そして、形態データ演算部１６３は、演算済み形態データ５１４を演算済み形態データキャッシュ１７０へ格納する。
【０１２４】
ポリゴン描画処理部１８０は、演算済み形態データキャッシュ１７０から描画対象のポリゴンの頂点の変換済み座標データ及び演算済み形態データ（データ５１５）を受け取り、ポリゴン描画処理を行い、メモリ２００上の出力画像５０４を生成する。
【０１２５】
本実施の形態の画像生成装置及び画像生成方法によれば、入力ポリゴンモデルの頂点データのうち座標データ以外の形態データを保持する演算済み形態データキャッシュへアクセスは、頂点消去判定で頂点が有効と判断された頂点ＩＤについてのみ行われる。
【０１２６】
これにより、メモリからグラフィックス処理ユニット（画像生成装置）への、入力ポリゴンモデルの頂点データのロードに関するメモリアクセス量及び演算量を低減することができる。したがって、従来の画像処理装置に比べて、低メモリバンド幅、低演算能力の情報処理装置の場合でも、入力ポリゴン数の多い高精細なポリゴン描画処理をリアルタイムで行うことができる。
【０１２７】
以上が、本発明の実施の形態における画像生成装置の動作についての説明である。
【０１２８】
以上、本発明の画像生成装置及び画像生成方法について、上記の実施の形態に基づいて説明したが、本発明は、この実施の形態に限定されるものではない。本発明の趣旨を逸脱しない限り、当業者が思いつく各種変形を実施の形態に施したものや、実施の形態の変形例における構成要素を組み合わせて構築される形態も本発明の範囲内に含まれる。
【０１２９】
例えば、入力ポリゴンモデルの表現形式についても、上記で示したポリゴンメッシュ形式以外の他の表現形式が含まれてもよい。また、頂点ＩＤリストについても画像生成装置１００内部又は外部で生成してもよい。
【０１３０】
図１０Ａ〜図１０Ｃは、ポリゴンメッシュ形式以外の表現形式（ポリゴンストリップ、ポリゴンファン、独立ポリゴン）からポリゴンメッシュ形式への変換の一例を示したものである。
【０１３１】
ポリゴンストリップ６０１、ポリゴンファン６０２又は独立ポリゴン６０３の形式で与えられた頂点ＩＤリスト６０４、６０７又は６１０は、それぞれポリゴンメッシュ形式の頂点ＩＤリスト６０５、６０８又は６１１に変換することが可能である。また、予め指定された頂点ＩＤリストが存在しない場合（座標データ及び形態データは先頭メモリアドレスから順にロードされることになる）においても、それぞれポリゴンメッシュ形式の頂点ＩＤリスト６０６、６０９、６１２を生成することが可能である。
【０１３２】
なお、図１０Ａにおいて、頂点ＩＤリスト６０５及び６０６に示される矢印は、ポリゴンストリップ形式の場合の頂点リストと順番が逆転していることを意味する。
【０１３３】
また、上記の実施の形態では、頂点の座標データ及び形態データの紐付けに頂点ＩＤを用いたが、頂点ＩＤの代わりに頂点の座標データ及び形態データへのメモリアドレスポインタなど別のデータを用いてもよい。
【０１３４】
また、ポリゴン消去判定部１５１は、クリッピング判定及びカリング判定を用いているが、描画オプションによってどちらか一方しか用いなくともよい。
【０１３５】
また、クリッピング判定として、３次元空間内の任意の平面を境界とした消去判定が含まれてもよい。あるいは、ディスプレイ面３０３上の任意の領域を境界とした消去判定が含まれてもよい。
【０１３６】
また、カリング判定として、ディスプレイ面３０３に投影したときに１ドットに満たないポリゴンの消去判定や、ビューボリューム３０２内の他のポリゴン描画によって視点３０１から全く見えなくなるポリゴンの消去判定が含まれてもよい。
【０１３７】
また、図２の画像生成装置１００に含まれる各ブロックは、一部又は全部を並列化又はパイプライン処理化してもよいし、複数のブロックを１つのブロックに統合してもよい。
【０１３８】
また、図２の画像生成装置１００に含まれる座標データチェック部１３１や変換済み座標データキャッシュ１４０の機能は実施の形態によっては、形態データチェック部１６１や演算済み形態データキャッシュ１７０に含まれたり、省略したりしてもよい。
【０１３９】
また、図２の画像生成装置１００は、演算済み形態データキャッシュ１７０を備え、演算済み形態データを演算済み形態データキャッシュ１７０に格納する構成について示したが、メモリ２００から読み出した形態データをキャッシュに格納してもよい。つまり、図１１に示すように、演算後の形態データをキャッシュに格納せずに、演算前の形態データをキャッシュに格納してもよい。
【０１４０】
図１１は、本発明の実施の形態の変形例に係る画像生成装置７００の構成の一例を示すブロック図である。
【０１４１】
図１１に示すように、画像生成装置７００は、座標データ処理部１３０と、判定部１５０と、形態データ処理部７６０と、形態データキャッシュ７７０と、ポリゴン描画処理部１８０とを備える。なお、図２と同様の構成については、同じ参照符号を付している。
【０１４２】
座標データ処理部１３０は、頂点データのうち座標データをメモリ２００からロードし、ロードした座標データを座標変換することで、変換済み座標データを生成する。
【０１４３】
判定部１５０は、座標データ処理部１３０によって生成された変換済み座標データを用いて、変換済み座標データが示す頂点が描画の対象であるか否かを判定する。
【０１４４】
形態データ処理部７６０は、判定部１５０によって変換済み座標データが示す頂点が描画の対象であると判定された場合に、形態データをポリゴン描画処理部１８０へ出力する。
【０１４５】
具体的には、形態データ処理部７６０は、判定部１５０によって変換済み座標データが示す頂点が描画の対象であると判定された場合で、かつ、形態データキャッシュ７７０に当該頂点の形態データが格納されていない場合には、メモリ２００から形態データをロードし、ロードした形態データを形態データキャッシュ７７０に格納する。また、形態データ処理部７６０は、判定部１５０によって変換済み座標データが示す頂点が描画の対象であると判定された場合で、かつ、形態データキャッシュ７７０に当該頂点の形態データが格納されている場合には、当該形態データを形態データキャッシュ７７０からポリゴン描画処理部１８０へ出力させる。
【０１４６】
ポリゴン描画処理部１８０は、座標データ処理部１３０によって生成された変換済み座標データと、形態データキャッシュ７７０に格納された形態データとを用いて、ポリゴンを描画する。
【０１４７】
以上の構成に示すように、本発明の実施の形態の変形例に係る画像生成装置７００は、メモリ２００からロードした形態データをそのまま形態データキャッシュ７７０に格納する。これにより、メモリ２００へのアクセスを低減することができる。また、上記の画像生成装置７００は、形態データの演算が必要でない場合にも有効である。
【０１４８】
また、図１２に示すように、本発明に係る画像生成装置は、図１１に示す構成に、さらに、変換済み座標データキャッシュを備える構成とすることもできる。図１２は、本発明の実施の形態の変形例に係る画像生成装置８００の構成の別の一例を示すブロック図である。
【０１４９】
図１２に示すように、画像生成装置８００は、図１１に示す画像生成装置７００と比較して、さらに変換済み座標データキャッシュ１４０を備える点が異なっている。図２及び図１１と同じ構成については、同じ参照符号を付し、以下では説明を省略する。
【０１５０】
判定部１５０は、変換済み座標データキャッシュ１４０に変換済み座標データが格納されている場合には、変換済み座標データキャッシュ１４０に格納されている変換済み座標データを用いて、当該変換済み座標データが示す頂点が描画の対象であるか否かを判定する。
【０１５１】
また、本発明は、図２、図１１又は図１２の画像生成装置１００、７００又は８００を含む情報処理装置として実現することができる。
【０１５２】
図１３は、図２の画像生成装置１００を含む情報処理装置９００の構成を示すブロック図である。同図に示す情報処理装置９００は、集積回路９０１と、メモリ９０８と、ディスプレイ９０９とを備える。
【０１５３】
集積回路９０１は、例えば、システムＬＳＩなどであり、ＣＰＵ９０２と、グラフィックス処理ユニット９０３（図２の画像生成装置１００）と、メモリコントローラ９０４と、ディスプレイコントローラ９０５と、ＣＰＵバス９０６と、メモリバス９０７とを備える。
【０１５４】
ＣＰＵ９０２は、描画命令リスト２０２及び頂点データリスト２０３を、メモリバス９０７とメモリコントローラ９０４とを介してメモリ９０８に格納する。また、ＣＰＵバス９０６を介して描画の指示をグラフィックス処理ユニット９０３へ伝える。
【０１５５】
グラフィックス処理ユニット９０３は、メモリバス９０７とメモリコントローラ９０４とを介して、メモリ９０８に格納されている描画命令リスト２０２及び頂点データリスト２０３にアクセスして、上述した画像生成処理を行う。生成した画像は、メモリバス９０７とメモリコントローラ９０４とを介してメモリ９０８に格納する。メモリ９０８に格納された生成画像は、ディスプレイコントローラ９０５を介してディスプレイ９０９へと出力される。
【０１５６】
なお、ＣＰＵ９０２による、頂点データリスト２０３のメモリ９０８への格納については、頂点データリスト２０３を、必ずロードされる頂点ＩＤリスト２０５と、重複する場合はロードされない座標データリスト２０６と、頂点消去判定結果で頂点が無効又は重複する場合はロードされない形態データリスト２０７とへ分割して、それぞれ別のメモリ領域に格納してもよい。これにより、メモリバス９０７及びメモリコントローラ９０４がバーストメモリアクセスによりメモリ９０８上の頂点データリスト２０３をロードする場合に、座標データとともに不要と判定された形態データまでロードしてしまうことを防ぐことができ、メモリアクセス効率を高めることができる。
【０１５７】
また、図１３の集積回路９０１のＣＰＵ９０２、グラフィックス処理ユニット９０３などの各機能ブロックは個別に集積回路化してもよいし、一部又は全部を含むように１つの集積回路としてもよい。集積回路９０１には、ＡＶ（Ａｕｄｉｏ  Ｖｉｓｕａｌ）処理ユニットやストリーミング処理ユニットなど他の機能ブロックが含んでいてもよい。メモリ９０８は、集積回路９０１の内部に搭載してもよいし、集積回路９０１の内部、外部を問わず複数個搭載してもよい。
【０１５８】
なお、本発明の実施の形態の画像生成装置は、典型的には半導体集積回路であるＬＳＩとして実現される。これらは個別に１チップ化されてもよいし、一部又は全てを含むように１チップ化されても良い。ここではＬＳＩとしたが、集積度の違いにより、ＩＣ、システムＬＳＩ、スーパーＬＳＩ、ウルトラＬＳＩと呼称されることもある。
【０１５９】
また、集積回路化の手法はＬＳＩに限るものではなく、専用回路又は汎用プロセッサで実現しても良い。ＬＳＩ製造後に、プログラムすることが可能なＦＰＧＡ（Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）や、ＬＳＩ内部の回路セルの接続や設定を再構成可能なリコンフィギュラブル・プロセッサを利用してもよい。
【０１６０】
さらには、半導体技術の進歩又は派生する別技術によりＬＳＩに置き換わる集積回路化の技術が登場すれば、当然、その技術を用いて機能ブロックの集積化を行ってもよい。バイオ技術の適応などが可能性として有り得る。
【０１６１】
さらに加えて、本発明の実施の形態の画像生成装置を集積化した半導体チップと、画像を描画するためのディスプレイとを組み合せて、様々な用途に応じた描画機器を構成することができる。携帯電話やテレビ、デジタルビデオレコーダ、デジタルビデオカメラ、カーナビゲーション等における情報描画手段として、本発明を利用することが可能である。ディスプレイとしては、ブラウン管（ＣＲＴ：Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ）の他、液晶やＰＤＰ（プラズマディスプレイパネル）、有機ＥＬ（Ｅｌｅｃｔｒｏｌｕｍｉｎｅｓｃｅｎｃｅ）などのフラットディスプレイ、プロジェクターを代表とする投射型ディスプレイなどと組み合わせることが可能である。
【産業上の利用可能性】
【０１６２】
本発明の実施の形態の画像生成装置は、様々な用途に利用可能である。例えば、携帯電話や携帯音楽プレーヤー、デジタルカメラ、デジタルビデオカメラ等の電池駆動の携帯表示端末や、テレビ、デジタルビデオレコーダ、カーナビゲーション等の高解像度の情報表示機器におけるメニュー表示やＷｅｂブラウザ、エディタ、ＥＰＧ（Ｅｌｅｃｔｒｏｎｉｃ  Ｐｒｏｇｒａｍ  Ｇｕｉｄｅ）、地図表示等における情報表示手段として利用価値が高い。
【符号の説明】
【０１６３】
１００、７００、８００  画像生成装置
１１０  ホストインタフェース
１２０  制御部
１３０  座標データ処理部
１３１  座標データチェック部
１３２  座標データロード部
１３３  座標変換部
１４０  変換済み座標データキャッシュ
１５０  判定部
１５１  ポリゴン消去判定部
１５２  頂点消去判定部
１５３  形態データアクセス頂点ＩＤ生成部
１６０、７６０  形態データ処理部
１６１  形態データチェック部
１６２  形態データロード部
１６３  形態データ演算部
１７０  演算済み形態データキャッシュ
１８０  ポリゴン描画処理部
１９０  メモリインタフェース
２００、９０８  メモリ
２０１  入力データ
２０２  描画命令リスト
２０３  頂点データリスト
２０４  描画命令
２０５、５０１  頂点ＩＤリスト
２０６、５０２  座標データリスト
２０７、５０３  形態データリスト
２０８、５０５  頂点ＩＤ
２０９、５０６  座標データ
２１０  形態データ
３０１  視点
３０２  ビューボリューム
３０３  ディスプレイ面
３０４、３０５、３０６  ポリゴン
４０１  ポリゴンメッシュ
４０２  タイムチャート
５０４  出力画像
５０７  変換済み座標データ
５０８、５０９、５１０、５１１、５１２、５１３、５１５  データ
５１４  演算済み形態データ
６０１  ポリゴンストリップ
６０２  ポリゴンファン
６０３  独立ポリゴン
６０４、６０５、６０６、６０７、６０８、６０９、６１０、６１１、６１２  頂点ＩＤリスト
７７０  形態データキャッシュ
９００  情報処理装置
９０１  集積回路
９０２  ＣＰＵ
９０３  グラフィックス処理ユニット
９０４  メモリコントローラ
９０５  ディスプレイコントローラ
９０６  ＣＰＵバス
９０７  メモリバス
９０９  ディスプレイ
【図１】
2010146828.tif 000003
【図２】
2010146828.tif 000004
【図３】
2010146828.tif 000005
【図４】
2010146828.tif 000006
【図５】
2010146828.tif 000007
【図６】
2010146828.tif 000008
【図７】
2010146828.tif 000009
【図８】
2010146828.tif 000010
【図９】
2010146828.tif 000011
【図１０Ａ】
2010146828.tif 000012
【図１０Ｂ】
2010146828.tif 000013
【図１０Ｃ】
2010146828.tif 000014
【図１１】
2010146828.tif 000015
【図１２】
2010146828.tif 000016
【図１３】
2010146828.tif 000017
【手続補正書】
【提出日】平成22年10月25日(2010.10.25)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ポリゴンを描画することで、グラフィックス画像を生成する画像生成装置であって、
ポリゴンを構成する頂点の情報を示す頂点データのうち、前記頂点の位置を示す座標データをメモリからロードし、ロードした座標データを座標変換することで、変換済み座標データを生成する座標処理部と、
前記座標処理部によって生成された変換済み座標データを用いて、ポリゴンが描画の対象であるか否かを判定し、描画の対象であると判定されたポリゴンを構成する頂点を示す頂点リストを生成する判定部と、
前記頂点データのうち前記座標データ以外のデータである形態データを格納するための形態データキャッシュと、
前記形態データキャッシュに、前記判定部によって生成された頂点リストが示す頂点の前記形態データが格納されていない場合には、前記メモリから当該形態データをロードし、ロードした形態データを前記形態データキャッシュに格納する形態データ処理部と、
前記座標処理部によって生成された変換済み座標データと、前記形態データキャッシュに格納された形態データとを用いて、ポリゴンを描画するポリゴン描画処理部とを備える
画像生成装置。
【請求項２】
前記形態データキャッシュには、前記形態データが処理された演算済みの形態データが格納され、
前記形態データ処理部は、
前記判定部によって生成された頂点リストが示す頂点の演算済みの形態データが、前記形態データキャッシュに格納されているか否かを判定する形態データ確認部と、
前記形態データ確認部によって前記演算済みの形態データが格納されていないと判定された場合に、前記メモリから前記頂点の形態データをロードする形態データロード部と、
前記形態データロード部によってロードされた形態データを処理することで、前記演算済みの形態データを生成し、生成した演算済みの形態データを前記形態データキャッシュに格納する形態データ演算部とを備える
請求項１記載の画像生成装置。
【請求項３】
前記形態データキャッシュは、複数のキャッシュラインを含み、
前記複数のキャッシュラインのそれぞれは、
頂点のＩＤを示すキャッシュタグと、
前記キャッシュタグが示す頂点の演算済み形態データを格納するためのラインメモリと、
前記ラインメモリに格納されている演算済み形態データが有効であるか否かを示すフラグとを含み、
前記形態データ確認部は、前記頂点リストが示す頂点のＩＤが、有効であることを示すフラグに対応するキャッシュタグに格納されているか否かを判定し、
前記形態データロード部は、前記形態データ確認部によって格納されていないと判定された場合に、前記メモリから当該頂点の形態データをロードする
請求項２記載の画像生成装置。
【請求項４】
前記画像生成装置は、さらに、
前記座標処理部によって生成された変換済み座標データを格納するための座標データキャッシュを備え、
前記判定部は、
前記座標データキャッシュに前記変換済み座標データが格納されている場合には、前記座標データキャッシュに格納されている変換済み座標データを用いて、当該変換済み座標データが示す頂点が描画の対象であるか否かを判定する
請求項１記載の画像生成装置。
【請求項５】
ポリゴンを描画することで、グラフィックス画像を生成する画像生成方法であって、
ポリゴンを構成する頂点の情報を示す頂点データのうち、前記頂点の位置を示す座標データをメモリからロードし、ロードした座標データを座標変換することで、変換済み座標データを生成する座標処理ステップと、
前記座標処理ステップにおいて生成された変換済み座標データを用いて、ポリゴンが描画の対象であるか否かを判定し、描画の対象であると判定されたポリゴンを構成する頂点を示す頂点リストを生成する判定ステップと、
形態データを格納するための形態データキャッシュに、前記判定ステップにおいて生成された頂点リストが示す頂点の前記形態データが格納されていない場合には、前記メモリから当該形態データをロードし、ロードした形態データを前記形態データキャッシュに格納する形態データ処理ステップと、
前記座標処理ステップにおいて生成された変換済み座標データと、前記形態データキャッシュに格納された形態データとを用いて、ポリゴンを描画するポリゴン描画処理ステップとを含む
画像生成方法。
【請求項６】
ポリゴンを描画することで、グラフィックス画像を生成する集積回路であって、
ポリゴンを構成する頂点の情報を示す頂点データのうち、前記頂点の位置を示す座標データをメモリからロードし、ロードした座標データを座標変換することで、変換済み座標データを生成する座標処理部と、
前記座標処理部によって生成された変換済み座標データを用いて、ポリゴンが描画の対象であるか否かを判定し、描画の対象であると判定されたポリゴンを構成する頂点を示す頂点リストを生成する判定部と、
前記頂点データのうち前記座標データ以外のデータである形態データを格納するための形態データキャッシュと、
前記形態データキャッシュに、前記判定部によって生成された頂点リストが示す頂点の前記形態データが格納されていない場合には、前記メモリから当該形態データをロードし、ロードした形態データを前記形態データキャッシュに格納する形態データ処理部と、
前記座標処理によって生成された変換済み座標データと、前記形態データキャッシュに格納された形態データとを用いて、ポリゴンを描画するポリゴン描画処理部とを備える
集積回路。
【手続補正書】
【提出日】平成23年6月27日(2011.6.27)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータグラフィックス技術に関し、コンピュータグラフィックス画像を生成する画像生成技術に関するものである。
【背景技術】
【０００２】
コンピュータグラフィックス（ＣＧ：Ｃｏｍｐｕｔｅｒ  Ｇｒａｐｈｉｃｓ）画像を生成する処理は計算負荷が大きいため、リアルタイムで画像生成処理を行う情報処理装置では、中央演算処理装置（ＣＰＵ：Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）とは別に、画像生成処理を専用で行う画像生成装置（グラフィックス処理ユニット）を備えている。
【０００３】
図１は、従来の一般的な画像生成装置が行う画像生成方法の処理を示すフローチャートである。
【０００４】
従来の一般的な画像生成装置は、まず、入力ポリゴンモデルの頂点データを情報記憶装置（メモリ）からロードする（Ｓ１０１）。なお、頂点データは、頂点の位置を示す座標データと、座標データ以外のデータである形態データとからなる。次に、頂点データのうち座標データについてワールド座標への座標変換処理を行い、さらに、ワールド座標からディスプレイ座標への座標変換処理を行う（Ｓ１０２）。
【０００５】
そして、変換座標データを用いて、ロードした頂点データから構成されるポリゴン毎に、ポリゴンが可視空間に入っているか否かを判定するクリッピング判定、あるいは、ポリゴンが視点から見て表示すべき面を向いているか否かを判定するカリング判定を行うことで、ポリゴン描画が有効かどうかの判定を行う（Ｓ１０３）。有効であると判定されたポリゴンについてのみ、ロードした頂点データのうち、座標データを除くデータ（形態データ）の処理を行う（Ｓ１０４）。
【０００６】
そして、演算済みの頂点データを用いてポリゴン描画処理を行う（Ｓ１０５）。以上の処理が全てのポリゴンについて終了したかを判定し（Ｓ１０６）、終了していない場合（Ｓ１０６で「継続」）、各処理（Ｓ１０１〜Ｓ１０５）が繰り返される。全てのポリゴンについて終了した場合（Ｓ１０６で「完了」）、画像生成装置は、描画された画像を出力する（Ｓ１０７）。
【０００７】
従来の一般的な画像生成方法は、上述したように、座標データに対する処理を行った後に、形態データに対する処理を行う。そして、上記のように、座標データと形態データとがセットになっているような頂点データを用いる場合には、座標データに対する処理を行う場合であっても、頂点データ、すなわち、座標データと形態データとの両方をロードする必要がある。したがって、本来は不要である形態データもロードしなければならないといった問題がある。また、形態データに対する処理を行う場合であっても、頂点データをロードする必要がある。したがって、本来は不要である座標データもロードしなければならないといった問題がある。
【０００８】
したがって、特許文献１には、座標データと形態データとを分けて管理する技術が開示されている。これにより、不要な形態データ又は座標データがロードされてしまうことを防ぐことができる。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】国際公開第２００８／１２６３９２号
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、上記特許文献１では、メモリアクセス又は演算量が十分に低減されないという課題がある。例えば、キャッシュメモリを有効に利用することで、データのロード及びデータの演算の重複を避けて、メモリアクセス又は演算量を低減することができるが、特許文献１には、形態データを記憶しておく形態データキャッシュについて何も記載されていない。そして、この形態データキャッシュをうまく活用しなければ、形態データキャッシュの資源を有効に利用することができない。
【００１１】
そこで、本発明は、形態データキャッシュの資源を有効に利用することで、メモリアクセス又は演算量を低減することができる画像生成装置、画像生成方法及び集積回路を提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記目的を達成するために、本発明に係る画像生成装置は、ポリゴンを描画することで、グラフィックス画像を生成する画像生成装置であって、ポリゴンを構成する頂点の情報を示す頂点データのうち、前記頂点の位置を示す座標データをメモリからロードし、ロードした座標データを座標変換することで、変換済み座標データを生成する座標処理部と、前記座標処理部によって生成された変換済み座標データを用いて、前記変換済み座標データが示す頂点が描画の対象であるか否かを判定する判定部と、前記頂点データのうち前記座標データ以外のデータである形態データを格納するための形態データキャッシュと、前記判定部によって前記変換済み座標データが示す頂点が描画の対象であると判定された場合で、かつ、前記形態データキャッシュに当該頂点の前記形態データが格納されていない場合には、前記メモリから当該形態データをロードし、ロードした形態データを前記形態データキャッシュに格納する形態データ処理部と、前記座標処理部によって生成された変換済み座標データと、前記形態データキャッシュに格納された形態データとを用いて、ポリゴンを描画するポリゴン描画処理部とを備える。
【００１３】
これにより、描画に必要と判定された頂点の形態データのみが形態データキャッシュに格納されるので、描画に不要な頂点の形態データをキャッシュしなくて済み、形態データキャッシュの資源を有効に利用することができる。
【００１４】
また、前記形態データキャッシュには、前記形態データが処理された演算済みの形態データが格納され、前記形態データ処理部は、前記判定部によって描画の対象であると判定された頂点の演算済みの形態データが、前記形態データキャッシュに格納されているか否かを判定する形態データ確認部と、前記形態データ確認部によって前記演算済みの形態データが格納されていないと判定された場合に、前記メモリから前記頂点の形態データをロードする形態データロード部と、前記形態データロード部によってロードされた形態データを処理することで、前記演算済みの形態データを生成し、生成した演算済みの形態データを前記形態データキャッシュに格納する形態データ演算部とを備えてもよい。
【００１５】
これにより、演算済み形態データを形態データキャッシュに格納することで、形態データのロード及び演算済み形態データの生成処理が重複して実行されることを防止することができ、メモリアクセス及び演算量を低減することができる。
【００１６】
また、前記判定部は、さらに、描画の対象であると判定した頂点のみを示す描画頂点リストを生成し、前記形態データ確認部は、前記判定部によって生成された描画頂点リストが示す頂点の演算済みの形態データが、前記形態データキャッシュに格納されているか否かを判定してもよい。
【００１７】
これにより、描画頂点リストが示す頂点の形態データのみをロードすればよく、形態データをロードする、しないの判定を容易に実現することができる。
【００１８】
また、前記画像生成装置は、さらに、前記座標処理部によって生成された変換済み座標データを格納するための座標データキャッシュを備え、前記判定部は、前記座標データキャッシュに前記変換済み座標データが格納されている場合には、前記座標データキャッシュに格納されている変換済み座標データを用いて、当該変換済み座標データが示す頂点が描画の対象であるか否かを判定してもよい。
【００１９】
これにより、変換済み座標データをキャッシュに格納することで、座標データのロード及び変換済み座標データの生成処理が重複して実行されることを防止することができ、メモリアクセス及び演算量を低減することができる。
【００２０】
なお、本発明は、画像生成装置として実現できるだけではなく、当該画像生成装置を構成する処理部をステップとする方法として実現することもできる。また、これらステップをコンピュータに実行させるプログラムとして実現してもよい。さらに、当該プログラムを記録したコンピュータ読み取り可能なＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ−Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）などの記録媒体、並びに、当該プログラムを示す情報、データ又は信号として実現してもよい。そして、それらプログラム、情報、データ及び信号は、インターネットなどの通信ネットワークを介して配信してもよい。
【００２１】
また、上記の各画像生成装置を構成する構成要素の一部又は全部は、１個のシステムＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ：大規模集積回路）から構成されていてもよい。システムＬＳＩは、複数の構成部を１個のチップ上に集積して製造された超多機能ＬＳＩであり、具体的には、マイクロプロセッサ、ＲＯＭ及びＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）などを含んで構成されるコンピュータシステムである。
【発明の効果】
【００２２】
本発明に係る画像生成装置によれば、描画に不要な頂点の形態データをキャッシュしなくて済むので、形態データキャッシュを有効利用できるという効果が得られる。
【図面の簡単な説明】
【００２３】
【図１】図１は、従来の画像生成装置の動作を示すフローチャートである。
【図２】図２は、本実施の形態の画像生成装置の構成の一例を示すブロック図である。
【図３】図３は、本実施の形態の画像生成装置へ入力される入力データの一例を示す図である。
【図４】図４は、ポリゴン消去判定を説明するための図である。
【図５】図５は、本実施の形態の画像生成装置の動作の一例を示すフローチャートである。
【図６】図６は、本実施の形態の処理の流れを示す図である。
【図７】図７は、本実施の形態の処理における形態データアクセス頂点ＩＤの生成方法の一例を示すフローチャートである。
【図８】図８は、本実施の形態の変換済み座標データキャッシュ及び演算済み形態データキャッシュの構成の一例を示す図である。
【図９】図９は、本実施の形態の画像生成装置の各処理部でのデータの流れを示す図である。
【図１０Ａ】図１０Ａは、ポリゴンストリップ形式のポリゴン描画に、本実施の形態の画像生成装置を適用する場合のデータ変換例を示す図である。
【図１０Ｂ】図１０Ｂは、ポリゴンファン形式のポリゴン描画に、本実施の形態の画像生成装置を適用する場合のデータ変換例を示す図である。
【図１０Ｃ】図１０Ｃは、独立ポリゴン形式のポリゴン描画に、本実施の形態の画像生成装置を適用する場合のデータ変換例を示す図である。
【図１１】図１１は、本実施の形態の変形例に係る画像生成装置の構成の一例を示すブロック図である。
【図１２】図１２は、本実施の形態の変形例に係る画像生成装置の構成の別の一例を示すブロック図である。
【図１３】図１３は、本実施の形態の画像生成装置を備える情報処理装置の構成を示すブロック図である。
【発明を実施するための形態】
【００２４】
以下、本発明の実施の形態における画像生成装置及び画像生成方法について、図面を参照しながら説明する。
【００２５】
本発明の実施の形態における画像生成装置は、頂点がポリゴン描画に必要とされるか否かを判定し、必要と判定された頂点のみに対応する演算済み形態データが形態データキャッシュに記憶されているか否かを判断する。形態データキャッシュに記憶されていない場合には、形態データをメモリからロードした後に、ロードした形態データを処理することで、演算済み形態データを生成し、形態データキャッシュに記憶する。また、形態データキャッシュに記憶されている場合には、形態データキャッシュに記憶されている演算済み形態データを用いてポリゴンを描画する。
【００２６】
つまり、ポリゴン描画に必要とされた頂点のみに対応する演算済み形態データを形態データキャッシュにキャッシュすることで、形態データキャッシュの資源を有効に利用することができるという効果が得られる。
【００２７】
次に、本発明の実施の形態における画像生成装置の構成について説明する。
【００２８】
図２は、本実施の形態の画像生成装置１００の構成の一例を示すブロック図である。同図の画像生成装置１００は、ポリゴンを描画することで、グラフィックス画像を生成する装置である。具体的には、画像生成装置１００は、ポリゴン描画に関する入力データ２０１を保持するメモリ２００から必要なデータを読み出す（ロードする）ことにより、ポリゴン描画を実行する装置である。まず、メモリ２００が格納する入力データ２０１について、以下に説明する。
【００２９】
図３は、本実施の形態の画像生成装置１００へ入力される入力データ２０１の一例を示す図である。同図に示すように、入力データ２０１は、描画命令リスト２０２と、入力ポリゴンモデルの頂点データリスト２０３とから構成される。
【００３０】
描画命令リスト２０２は、ポリゴン描画命令に関する様々な情報を示す描画命令２０４を含む。図３に示すように、描画命令２０４は、入力ポリゴンの表現形式（ポリゴンストリップ、ポリゴンファン、ポリゴンメッシュ及び独立ポリゴンなど）、各パラメータのロード設定（各種データのアドレス設定）、及び、描画オプションなどを示す。
【００３１】
頂点データリスト２０３は、入力ポリゴンモデルの頂点データのリストであり、頂点ＩＤリスト２０５と、座標データリスト２０６と、形態データリスト２０７とから構成される。なお、頂点データとは、ポリゴンを構成する頂点の情報を示すデータであり、座標データと形態データとからなる。座標データとは、頂点の位置を示すデータである。形態データとは、座標データ以外のデータである。
【００３２】
図３に示すように、頂点データリスト２０３は、頂点ＩＤリスト２０５と、座標データリスト２０６と、形態データリスト２０７とへ分割して、それぞれ別のメモリ領域に格納してもよい。これにより、一度のメモリアクセスでメモリアドレスが連続する領域のデータを一括して多くロードするバーストメモリアクセスによって、頂点データリスト２０３をロードする場合に、座標データとともに不要と判定された形態データまでロードしてしまうことを防ぐことができ、メモリアクセス効率を高めることができる。
【００３３】
頂点ＩＤリスト２０５は、入力ポリゴンモデルの各頂点のＩＤを示す頂点ＩＤ２０８のリストである。頂点ＩＤ２０８は、頂点の座標データ及び形態データを紐付けするＩＤであり、各頂点ＩＤ２０８に対してそれぞれ座標データ及び形態データが存在する。頂点ＩＤ２０８は、例えば、描画命令２０４の頂点ＩＤアドレス設定が示すアドレス又はポインタが示す位置に格納されている。
【００３４】
座標データリスト２０６は、入力ポリゴンモデルの各頂点の位置を示す座標データ２０９のリストである。座標データ２０９は、１頂点あたり２〜４ワードで表現することができる。座標データ２０９は、例えば、描画命令２０４の座標データアドレス設定が示すアドレス又はポインタが示す位置に格納されている。
【００３５】
形態データリスト２０７は、各頂点の座標データ以外の情報を示す形態データ２１０のリストである。図３には、形態データ２１０の一例として、各頂点の法線データ、カラーデータ、及び、テクスチャ座標データを示すが、描画オプションによって増減があり、複雑なシーンの描画を行う場合は、形態データ２１０は、１頂点あたり数十ワードにもなる。形態データ２１０の法線データ、カラーデータ、及び、テクスチャ座標データはそれぞれ、描画命令２０４の法線データアドレス設定、カラーデータアドレス設定、及び、テクスチャ座標データアドレス設定が示すアドレス又はポインタが示す位置に格納されている。
【００３６】
図２の画像生成装置１００は、ホストインタフェース１１０と、制御部１２０と、座標データ処理部１３０と、変換済み座標データキャッシュ１４０と、判定部１５０と、形態データ処理部１６０と、演算済み形態データキャッシュ１７０と、ポリゴン描画処理部１８０と、メモリインタフェース１９０とを備える。
【００３７】
ホストインタフェース１１０は、ＣＰＵから入力される描画開始の指示を制御部１２０へと伝える。
【００３８】
制御部１２０は、描画開始の指示を受け取るとメモリバス（図示せず）及びメモリインタフェース１９０を介して、メモリ２００から描画命令リスト２０２をロードして、描画命令２０４を座標データチェック部１３１、座標データロード部１３２及び形態データロード部１６２に伝える。
【００３９】
座標データ処理部１３０は、頂点データのうち座標データ２０９をメモリ２００からロードし、ロードした座標データ２０９を座標変換することで、変換済み座標データを生成する。図２に示すように、座標データ処理部１３０は、座標データチェック部１３１と、座標データロード部１３２と、座標変換部１３３とを備える。
【００４０】
座標データチェック部１３１は、ポリゴンを構成する頂点の変換済み座標データが変換済み座標データキャッシュ１４０に格納されているか否かを判定する。具体的には、座標データチェック部１３１は、描画命令２０４に従って頂点データリスト２０３のうち頂点ＩＤリスト２０５にアクセスし、頂点ＩＤ２０８をロードする。そして、座標データチェック部１３１は、ロードした頂点ＩＤ２０８が示す頂点の変換済み座標データが、変換済み座標データキャッシュ１４０に格納されているか否かをチェックする。そして、座標データチェック部１３１は、変換済み座標データが格納されていない場合のみ、座標データロード部１３２へ頂点ＩＤ２０８を出力する。
【００４１】
座標データロード部１３２は、座標データチェック部１３１によって変換済み座標データが格納されていないと判定された場合に、メモリ２００から当該頂点の座標データ２０９をロードする。具体的には、座標データロード部１３２は、座標データチェック部１３１から頂点ＩＤ２０８を受け取った場合、描画命令２０４に従って頂点データリスト２０３のうち座標データリスト２０６にアクセスし、頂点毎の座標データ２０９をロードして、ロードした座標データ２０９を座標変換部１３３へ出力する。
【００４２】
座標変換部１３３は、座標データロード部１３２によってロードされた座標データを座標変換することで、変換済み座標データを生成する。具体的には、座標変換部１３３は、入力された座標データ２０９に対して座標変換処理を行い、変換済み座標データを変換済み座標データキャッシュ１４０へ出力する。座標変換処理とは、座標データ２０９をワールド座標及びディスプレイ座標に変換することである。つまり、変換済み座標データは、ディスプレイ座標において頂点の位置を示す座標データである。
【００４３】
変換済み座標データキャッシュ１４０は、座標データ処理部１３０によって生成された変換済み座標データを格納するためのキャッシュメモリである。変換済み座標データキャッシュ１４０は、座標データチェック部１３１から頂点ＩＤ２０８を受け取り、該当頂点の変換済み座標データが格納されていない場合は、座標データロード部１３２及び座標変換部１３３により変換済み座標データを要求して、座標変換部１３３から出力された変換済み座標データを格納する。また、変換済み座標データキャッシュ１４０は、該当頂点の変換済み座標データが存在している場合は、これらの処理を省略して、ポリゴン消去判定部１５１へ変換済み座標データを出力する。
【００４４】
判定部１５０は、座標データ処理部１３０によって生成された変換済み座標データを用いて、変換済み座標データが示す頂点が描画の対象であるか否かを判定する。図２に示すように、判定部１５０は、ポリゴン消去判定部１５１と、頂点消去判定部１５２と、形態データアクセス頂点ＩＤ生成部１５３とを備える。
【００４５】
ポリゴン消去判定部１５１は、変換済み座標データを用いてポリゴンが描画の対象であるか否か、すなわち、ポリゴン描画が有効かどうかを示すフラグ（以下、ポリゴン描画有効フラグ）を生成する。具体的には、まず、ポリゴン消去判定部１５１は、判定対象のポリゴンを構成する頂点の変換済み座標データを用いてポリゴン描画が有効か否かの判定（以下、ポリゴン消去判定）を行う。
【００４６】
そして、ポリゴン消去判定部１５１は、判定結果に基づいてポリゴン描画有効フラグを生成して、頂点消去判定部１５２へと出力する。ポリゴン描画有効フラグは、対応するポリゴンが有効であれば真、対応するポリゴンが無効であれば偽を示す。ポリゴン消去判定の具体例については後述する。
【００４７】
頂点消去判定部１５２は、ポリゴン描画有効フラグを用いて頂点が有効かどうかを示すフラグ（以下、頂点有効フラグ）を生成する。具体的には、まず、頂点消去判定部１５２は、ポリゴン消去判定部１５１から出力されたポリゴン描画有効フラグを用いて、ポリゴン消去判定対象のポリゴンを構成する頂点が有効であるか否かを判定する。そして、判定結果に基づいて頂点有効フラグを生成して、形態データアクセス頂点ＩＤ生成部１５３へ出力する。頂点有効フラグは、対応する頂点が有効であれば真、対応する頂点が無効であれば偽を示す。
【００４８】
形態データアクセス頂点ＩＤ生成部１５３は、頂点消去判定部１５２から出力された頂点有効フラグを参照して、有効な頂点データについてのみ、座標データチェック部１３１で用いた頂点ＩＤ２０８を形態データチェック部１６１へ出力する。
【００４９】
形態データ処理部１６０は、判定部１５０によって変換済み座標データが示す頂点が描画の対象であると判定された場合で、かつ、演算済み形態データキャッシュ１７０に当該頂点の演算済み形態データが格納されていない場合には、メモリ２００から形態データ２１０をロードし、ロードした形態データ２１０を処理することで、演算済み形態データを生成する。そして、形態データ処理部１６０は、生成した演算済み形態データを演算済み形態データキャッシュ１７０に格納する。図２に示すように、形態データ処理部１６０は、形態データチェック部１６１と、形態データロード部１６２と、形態データ演算部１６３とを備える。
【００５０】
形態データチェック部１６１は、判定部１５０によって描画の対象であると判定された頂点の演算済み形態データが、演算済み形態データキャッシュ１７０に格納されているか否かを判定する。具体的には、形態データチェック部１６１は、形態データアクセス頂点ＩＤ生成部１５３から出力された頂点ＩＤ２０８を取得して、取得した頂点ＩＤ２０８が示す頂点の演算済み形態データが演算済み形態データキャッシュ１７０に格納されているか否かをチェックする。そして、形態データチェック部１６１は、演算済み形態データが格納されていない場合のみ形態データロード部１６２へ頂点ＩＤ２０８を出力する。
【００５１】
形態データロード部１６２は、形態データチェック部１６１によって演算済み形態データが格納されていないと判定された場合に、メモリ２００から当該頂点の形態データ２１０をロードする。具体的には、形態データロード部１６２は、形態データチェック部１６１から頂点ＩＤ２０８を受け取った場合、描画命令２０４に従って頂点データリスト２０３のうち形態データリスト２０７にアクセスし、形態データ２１０をロードして、ロードした形態データ２１０を変換済み座標データとともに形態データ演算部１６３へ出力する。
【００５２】
形態データ演算部１６３は、形態データロード部１６２によってロードされた形態データ２１０を処理することで、演算済み形態データを生成し、生成した演算済み形態データを演算済み形態データキャッシュ１７０へ格納する。具体的には、形態データ演算部１６３は、入力された形態データ２１０に対して形態データ演算を行い、演算済み形態データを演算済み形態データキャッシュ１７０へ出力する。
【００５３】
形態データ演算とは、光源計算を行って演算済みのカラー値を求める演算処理、テクスチャ座標計算を行って演算済みのテクスチャ座標値を求める演算処理など、上記の座標変換処理以外の頂点データに対して行う演算処理のことを指す。演算済み形態データは、上記の座標変換処理以外の演算処理が実施された演算済みの形態データである。
【００５４】
演算済み形態データキャッシュ１７０は、演算済み形態データを格納するためのキャッシュメモリである。演算済み形態データキャッシュ１７０は、形態データチェック部１６１から頂点ＩＤ２０８を受け取り、該当頂点の演算済み形態データが格納されていない場合は、形態データロード部１６２及び形態データ演算部１６３により演算済み形態データを要求して、形態データ演算部１６３から出力された演算済み形態データを格納する。また、演算済み形態データキャッシュ１７０は、該当頂点の演算済み形態データが格納されている場合は、これらの処理を省略して、ポリゴン描画処理部１８０へ変換済み座標データと演算済み形態データとを出力する。
【００５５】
ポリゴン描画処理部１８０は、座標データ処理部１３０によって生成された変換済み座標データと、形態データ処理部１６０によって処理された演算済み形態データとを用いて、ポリゴンを描画する。具体的には、ポリゴン描画処理部１８０は、入力された頂点データ（変換済み座標データ及び演算済み形態データ）を用いてポリゴン描画処理を行い、ポリゴン画像を生成する。ポリゴン描画処理は、コンピュータグラフィックス処理で用いられる一般的な処理により実行される。ポリゴン描画処理部１８０は、メモリインタフェース１９０を介して生成したポリゴン画像をメモリ２００へと出力する。
【００５６】
メモリインタフェース１９０は、画像生成装置１００が備える各処理部とメモリ２００との間でデータのやり取りを行う。
【００５７】
続いて、ポリゴン消去判定部１５１が行うポリゴン消去判定について説明する。図４は、ポリゴン消去判定を説明するための図である。ポリゴン消去判定とは、複数の頂点から構成されるポリゴンが画像生成時に用いられるか否かを判定する処理である。
【００５８】
なお、本実施の形態では、ポリゴンは３つの頂点から構成される例について説明するが、ポリゴンは４つ以上の頂点から構成されてもよい。
【００５９】
コンピュータグラフィックスの描画処理においては、各フレームの描画開始時にシーンのカットとして、ユーザの原点を表す視点３０１と、ユーザの視点３０１から見たときの視界の３次元空間を表す六面体であるビューボリューム３０２とが、それぞれ座標値としてグラフィックス処理ユニット（本実施の形態における画像生成装置１００）に与えられる。
【００６０】
ポリゴン消去判定では、視点３０１を原点とした座標系（ディスプレイ座標系）へ変換した座標データ（変換済み座標データ）を用いる。ポリゴン消去判定は、クリッピング判定及びカリング判定により行う。
【００６１】
クリッピング判定は、ユーザの視界に存在するポリゴンのみ描画するために、各ポリゴンに含まれる頂点の変換済み座標データがビューボリューム３０２の中に入っているかどうかを判定する処理である。ポリゴンを構成する頂点のうち全ての頂点の座標がビューボリューム３０２の外に存在していれば、当該ポリゴンの描画は無効となる。つまり、ポリゴンを構成する頂点のうち１つでもビューボリューム３０２内に存在していれば、当該ポリゴンの描画は有効になる。例えば、ポリゴン３０５のように完全にビューボリューム３０２の外に存在するポリゴンは、クリッピング判定により描画が無効となる。
【００６２】
一方、カリング判定は、物体を構成するポリゴンのうち物体の外側（表面）を向いたポリゴンだけを描画するために、ビューボリューム３０２の中に入っているポリゴンについて視点から見たときのポリゴン面が表向きかどうかを判定する処理である。カリング判定は、ポリゴンを構成する頂点の座標から面の向きを表す面法線ベクトルＮを求め、ポリゴンから視点方向を向いた視点方向ベクトルＶとの内積Ｎ・Ｖの符号を確認することでポリゴンの表裏を判定することができる。
【００６３】
具体的には、視点３０１から見て裏向き（Ｎ・Ｖ＜０）であれば、ポリゴン描画は無効となる。例えば、ポリゴン３０６のようにポリゴン面が視点３０１から見て裏向きであるポリゴンは、カリング判定により描画が無効となる。
【００６４】
ポリゴン３０４のように、クリッピング判定及びカリング判定で無効と判断されなかったポリゴンについてのみ、ポリゴン消去判定部１５１は、ディスプレイ面３０３に投影して描画することができる有効なポリゴンと判定する。
【００６５】
以上が、本発明の実施の形態における画像生成装置１００の構成についての説明である。
【００６６】
次に、本発明の実施の形態における画像生成装置１００の動作について説明する。
【００６７】
図５は、本実施の形態の画像生成装置１００の動作の一例を示すフローチャートである。本実施の形態の画像生成処理は、まず、ホストインタフェース１１０を介してＣＰＵから描画命令２０４を制御部１２０が受け取ることで開始する。
【００６８】
制御部１２０からの指示に基づいて、座標データチェック部１３１は、入力ポリゴンモデルの頂点データのうち頂点ＩＤ２０８のロードを行う（Ｓ２０１）。続いて、座標データチェック部１３１は、変換済み座標データキャッシュ１４０に、ロードした頂点ＩＤ２０８を用いて問い合わせを行う（Ｓ２０２）。すなわち、座標データチェック部１３１は、ロードした頂点ＩＤ２０８が示す頂点の変換済み座標データが変換済み座標データキャッシュ１４０に格納されているか否かを確認する。
【００６９】
頂点ＩＤ２０８に対応する頂点の変換済み座標データが格納されていた場合（Ｓ２０２で「データ有り」）、メモリ２００からの当該頂点の座標データ２０９のロード及び座標変換処理は実行しない。これにより、座標データをキャッシュにより再利用できるので、ロード時間の短縮になるという効果が得られる。
【００７０】
また、頂点ＩＤ２０８に対応する頂点の変換済み座標データが存在しない場合（Ｓ２０２で「データ無し」）、メモリ２００からの当該頂点の座標データ２０９のロード及び座標変換処理を実行するために、座標データロード部１３２へ頂点ＩＤ２０８を出力する。
【００７１】
座標データロード部１３２は、入力ポリゴンモデルの頂点データのうち頂点ＩＤ２０８に対応する座標データ２０９のロードを行う（Ｓ２０３）。座標変換部１３３は、ロードされた座標データ２０９をワールド座標及びディスプレイ座標へ変換することで変換済み座標データを生成し、生成した変換済み座標データを変換済み座標データキャッシュ１４０へ格納する（Ｓ２０４）。
【００７２】
ポリゴン消去判定部１５１は、判定対象のポリゴンを構成する頂点の変換済み座標データを用いてポリゴン消去判定を行う（Ｓ２０５）。具体的には、ポリゴン消去判定部１５１は、図４を用いて説明したクリッピング判定及びカリング判定を行う。
【００７３】
頂点消去判定部１５２は、判定対象の頂点を含むポリゴンのポリゴン消去判定結果、例えば、ポリゴン有効フラグを用いて頂点消去判定を行う（Ｓ２０６）。判定対象のポリゴン消去判定結果で、ポリゴン描画が有効であった場合（Ｓ２０６で「頂点が有効」）、判定対象のポリゴンに含まれる頂点は有効な頂点データであると判定する。また、ポリゴン描画が無効であった場合（Ｓ２０６で「頂点が無効」）、無効な頂点データであると判定する。
【００７４】
形態データアクセス頂点ＩＤ生成部１５３は、頂点消去判定部１５２により生成された頂点消去判定結果、例えば、頂点有効フラグを参照して、有効とされた頂点データについてのみ頂点ＩＤ２０８を形態データチェック部１６１へ出力する（Ｓ２０７）。これにより、描画に不要な頂点の形態データをキャッシュしなくて済むので、演算済み形態データキャッシュ１７０を有効利用できる。なお、形態データアクセス頂点ＩＤ生成部１５３の詳細な動作については、後で説明する。
【００７５】
そして、形態データチェック部１６１は、演算済み形態データキャッシュ１７０に、形態データアクセス頂点ＩＤ生成部１５３から受け取った頂点ＩＤ２０８を用いて問い合わせを行う（Ｓ２０８）。頂点ＩＤ２０８に対応する頂点の演算済み形態データが存在した場合（Ｓ２０８で「データ有り」）、メモリ２００からの当該頂点の形態データ２１０のロード及び形態データ演算は実行しない。
【００７６】
頂点ＩＤ２０８に対応する頂点の演算済み形態データが存在しない場合（Ｓ２０８で「データ無し」）、メモリ２００からの当該頂点の形態データ２１０のロード及び形態データ演算を実行するために、形態データロード部１６２へ頂点ＩＤ２０８を出力する。
【００７７】
形態データロード部１６２は、入力ポリゴンモデルの頂点データのうち頂点ＩＤ２０８に対応する形態データ２１０のロードを行う（Ｓ２０９）。形態データ演算部１６３は、ロードされた形態データ２１０を用いて演算を行うことで演算済み形態データを生成し、生成した演算済み形態データを演算済み形態データキャッシュ１７０へ格納する（Ｓ２１０）。
【００７８】
ポリゴン描画処理部１８０は、演算済み形態データキャッシュ１７０から受け取った頂点データ（変換済み座標データ及び演算済み形態データ）を用いて、ポリゴン描画処理を行う（Ｓ２１１）。
【００７９】
以上の処理が全てのポリゴンについて終了したかを判定し（Ｓ２１２）、終了していない場合（Ｓ２１２で「継続」）、上記の各処理（Ｓ２０１〜Ｓ２１１）が繰り返される。全てのポリゴンについて終了した場合（Ｓ２１２で「完了」）、画像生成装置１００は、描画された画像を出力する（Ｓ２１３）。
【００８０】
以上のようにして、本実施の形態の画像生成装置１００は、変換済み座標データキャッシュ１４０へは全ての頂点ＩＤによるアクセスが発生するのに対して、演算済み形態データキャッシュ１７０へのアクセスは、有効な頂点と判定された頂点に対応するものだけに限られる。このため、ポリゴン描画に使用する必要最小限の頂点データによって、キャッシュメモリを割り当てることができ、キャッシュメモリの資源を有効に利用することができる。
【００８１】
これにより、従来の画像処理装置よりもさらに、入力ポリゴンデータのロードに関するメモリアクセス量及び演算量を低減することができる。また、本実施の形態の画像生成装置１００は、画像の描画処理と並行して、頂点がポリゴン描画に必要であるか否かを判定するため、インタラクティブ用途にも適用することができる。
【００８２】
以下では、より具体的に本発明の実施の形態の画像生成装置１００について説明する。ここでは、ポリゴンの表現形式がポリゴンメッシュの場合について説明する。
【００８３】
図６は、入力ポリゴンモデルがポリゴンメッシュ形式で構成されている場合の処理の流れを示す図である。ポリゴンメッシュ形式は、内部の多くのポリゴンで頂点の共有が行われる形式である。
【００８４】
同図に示すように、ポリゴンメッシュ４０１の頂点データは、例えば、Ｐ０（Ｖ０、Ｖ１、Ｖ２）→Ｐ１（Ｖ１、Ｖ３、Ｖ２）→Ｐ２（Ｖ２、Ｖ３、Ｖ４）→Ｐ３（Ｖ０、Ｖ２、Ｖ５）→Ｐ４（Ｖ５、Ｖ２、Ｖ６）→Ｐ５（Ｖ２、Ｖ４、Ｖ６）の順で指定される。なお、ポリゴンメッシュは自由度の高い形式であり、必ずしもこの順番で指定されるとは限らない。また、図６に示す例においては、ポリゴンＰ０、Ｐ３及びＰ４が有効なポリゴンであり、ポリゴンＰ１、Ｐ２及びＰ５が無効なポリゴンであるとする。
【００８５】
タイムチャート４０２は、頂点ＩＤのロードから演算済み形態データの生成までの処理の流れを示すタイムチャートである。以下では、タイムチャート４０２に沿ってポリゴンメッシュ形式の処理の流れについて説明する。
【００８６】
座標データチェック部１３１は、頂点データのうち頂点ＩＤ  Ｖｉ（ｉ＝０〜６）のロードを行い、ロードしたＶｉを用いて変換済み座標データキャッシュ１４０へ問い合わせを行う。
【００８７】
そして、該当頂点の変換済み座標データが無い場合、座標データロード部１３２は、頂点データのうち座標データＭｉのロードを行う。次に、座標変換部１３３は、ロードされた座標データＭｉの座標変換を行うことで、変換済み座標データＤｉを生成する。そして、座標変換部１３３は、変換済み座標データＤｉを変換済み座標データキャッシュ１４０へ格納する。
【００８８】
該当頂点の変換済み座標データＤｉがある場合は、ポリゴンメッシュ上の同じ頂点の座標データを参照することになるので重複して処理を行わない。図６の例では、頂点ＩＤは、Ｖ０→Ｖ１→Ｖ２→Ｖ１→Ｖ３→Ｖ２→Ｖ２→Ｖ３→Ｖ４→Ｖ０→Ｖ２→Ｖ５→Ｖ２→Ｖ６→Ｖ５→Ｖ２→Ｖ４→Ｖ６の順にロードされるが、座標データについての処理、すなわち、座標データのロード及び座標変換は、Ｖ０→Ｖ１→Ｖ２→Ｖ３→Ｖ４→Ｖ５→Ｖ６の順に行い、重複して問い合わせのあった頂点については、再処理を行わない。つまり、座標データのロード及び座標変換は、各頂点について１回のみ実行される。
【００８９】
例えば、図６に示すように、ポリゴンＰ１に含まれる頂点のうち、座標データＭ１及びＭ２はロードされず、したがって、座標データＭ１及びＭ２の座標変換（変換済み座標データＤ１及びＤ２の生成）は実行されない。なお、これらの処理は、ポリゴンＰ０の処理時に実行されている。
【００９０】
ポリゴン消去判定部１５１は、ポリゴンＰｊ（ｊ＝０〜５）を構成する頂点の変換済み座標データＤｉを変換済み座標データキャッシュ１４０から読み出して、読み出した変換済み座標データＤｉを用いてポリゴン描画有効フラグＦＰｊを生成する。なお、上述したように、ポリゴン描画有効フラグＦＰｊは、対応するポリゴンが有効であれば真（Ｔ）、対応するポリゴンが無効であれば偽（Ｆ）である。図６の例では、ポリゴン消去判定をＰ０→Ｐ１→Ｐ２→Ｐ３→Ｐ４→Ｐ５の順に行う。
【００９１】
頂点消去判定部１５２は、ポリゴン描画有効フラグＦＰｊを用いて、頂点Ｖｋ（ｋ＝０〜１５について頂点消去判定を行う。すなわち、以下の（式１）に示すように、頂点Ｖｋが含まれる、ポリゴンのポリゴン描画有効フラグＦＰｊが真となれば、頂点Ｖｋの頂点有効フラグＦＶｋも真とする。
【００９２】
ＦＶｋ＝（ＦＰｊ＆（Ｖｋ∈Ｐｊ））    ・・・（式１）
なお、頂点消去判定において、頂点Ｖｋは、頂点消去判定部１５２にｋ＋１番目に入力された頂点ＩＤが示す頂点である。例えば、頂点消去判定において頂点Ｖ０は、１番目に入力された頂点ＩＤが示す頂点、すなわち、ポリゴンＰ０を構成する頂点Ｖ０である。また、頂点Ｖ４は、５番目に入力された頂点ＩＤが示す頂点、すなわち、ポリゴンＰ１を構成する頂点Ｖ３である。
【００９３】
したがって、図６に示すように、頂点消去判定部１５２に入力された頂点の数だけ、頂点有効フラグＦＶｋが生成される。つまり、同じ頂点について複数の頂点有効フラグＦＶｋが生成される。
【００９４】
図６の例では、頂点消去判定部１５２は、頂点Ｖｋ（ｋ＝０〜１５）についての頂点消去判定を行うとき、ポリゴン消去判定部１５１が生成したポリゴン描画有効フラグＦＰｊをＴ→Ｆ→Ｆ→Ｔ→Ｔ→Ｆの順に受け取る。そして、頂点消去判定部１５２は、ポリゴンＰｊ（ｊ＝０〜５）を構成する頂点Ｖｋ（ｋ＝０〜１５）についてそれぞれ上記の（式１）に基づいて、頂点有効フラグＦＶｋが、Ｔ→Ｔ→Ｔ→Ｆ→Ｆ→Ｆ→Ｆ→Ｆ→Ｆ→Ｔ→Ｔ→Ｔ→Ｔ→Ｔ→Ｔ→Ｆ→Ｆ→Ｆの順に生成される。
【００９５】
形態データアクセス頂点ＩＤ生成部１５３は、頂点有効フラグＦＶｋを用いて、形態データチェック部１６１にアクセスする頂点ＩＤの生成を行う。図７に形態データアクセス頂点ＩＤの生成方法のフローチャートを示す。
【００９６】
まず、形態データアクセス頂点ＩＤ生成部１５３は、座標データ処理部１３０がロードして使用した元の頂点ＩＤを取得する（Ｓ３０１）。次に、形態データアクセス頂点ＩＤ生成部１５３は、該当頂点の頂点有効フラグＦＶｋが真かどうか判定する（Ｓ３０２）。
【００９７】
頂点有効フラグＦＶｋが真ならば（Ｓ３０２で「真」）、入力された頂点ＩＤを形態データアクセス頂点ＩＤとして出力する（Ｓ３０３）。頂点有効フラグＦＶｋが偽ならば（Ｓ３０２で「偽」）、入力された頂点ＩＤを出力しない。
【００９８】
すなわち、形態データアクセス頂点ＩＤ生成部１５３は、頂点有効フラグＦＶｋが真となる頂点についてのみ、頂点ＩＤを形態データチェック部１６１へ出力する。図６の例では、形態データチェック部１６１へ出力される頂点ＩＤは、Ｖ０→Ｖ１→Ｖ２→Ｖ０→Ｖ２→Ｖ５→Ｖ２→Ｖ６→Ｖ５の順に生成される。
【００９９】
以上のように、形態データアクセス頂点ＩＤ生成部１５３は、描画の対象であると判定された頂点のみを示す描画頂点リストを生成する機能を有する。描画頂点リストは、例えば、図６に示すような、Ｖ０→Ｖ１→Ｖ２→Ｖ０→Ｖ２→Ｖ５→Ｖ２→Ｖ６→Ｖ５として示されるリストである。
【０１００】
形態データチェック部１６１は、形態データアクセス頂点ＩＤ生成部１５３が生成した頂点ＩＤ  Ｖｉ（ｉ＝０〜６）を用いて、演算済み形態データキャッシュ１７０へ問い合わせを行う。言い換えると、形態データチェック部１６１は、描画頂点リストが示す頂点の演算済み形態データが、演算済み形態データキャッシュ１７０に格納されているか否かを判定する。
【０１０１】
そして、該当頂点の演算済み形態データが無い場合、形態データロード部１６２は、頂点データのうち形態データＮｉのロードを行う。次に、形態データ演算部１６３は、ロードされた形態データのＮｉの演算を行うことで、演算済み形態データＣｉを生成する。そして、形態データ演算部１６３は、演算済み形態データＣｉを演算済み形態データキャッシュ１７０へ格納する。
【０１０２】
該当頂点の演算済み形態データＣｉがある場合は、ポリゴンメッシュ上の同じ頂点の形態データを参照することになるので重複して処理を行わない。図６の例では、頂点ＩＤは、Ｖ０→Ｖ１→Ｖ２→Ｖ０→Ｖ２→Ｖ５→Ｖ２→Ｖ６→Ｖ５の順に生成されるが、形態データについての処理、すなわち、形態データのロード及び演算は、Ｖ０→Ｖ１→Ｖ２→Ｖ５→Ｖ６の順に行い、重複して問い合わせのあった頂点については再処理を行わない。つまり、形態データのロード及び演算は、各頂点について１回のみ実行される。
【０１０３】
例えば、図６に示すように、ポリゴンＰ３に含まれる頂点のうち、形態データＮ０及びＮ２はロードされず、したがって、形態データＮ０及びＮ２の演算（演算済み形態データＣ０及びＣ２の生成）は実行されない。なお、これらの処理は、ポリゴンＰ０の処理時に実行されている。
【０１０４】
図８は、変換済み座標データキャッシュ１４０及び演算済み形態データキャッシュ１７０の構成を示す図である。各キャッシュの構成は、キャッシュメモリをキャッシュラインという単位に分けて、キャッシュライン毎に一意なエントリ番号を割り当てる。図８に示すように、各キャッシュラインは、エントリ番号と、頂点ＩＤ（キャッシュタグ）と、参照カウンタと、キャッシュライン有効フラグと、キャッシュラインメモリとを含む。
【０１０５】
エントリ番号は、キャッシュ内のデータの紐付けを行うための識別子である。頂点ＩＤ（キャッシュタグ）は、キャッシュライン内で管理されている頂点を特定する頂点ＩＤである。参照カウンタは、現在データを参照している参照頂点数をカウントするカウンタである。キャッシュライン有効フラグは、キャッシュラインに有効なデータが格納されているかどうかを示すフラグ情報である。キャッシュラインメモリは、それぞれ変換済み座標データ又は演算済み形態データを格納するデータ格納部である。
【０１０６】
参照カウンタが０のときは、キャッシュラインが空とみなして新たな頂点ＩＤの登録を行うことができる。参照カウンタは、頂点ＩＤが必要とされる度に、具体的には、頂点ＩＤの問い合わせが実行される度に、インクリメントされる。逆に、参照カウンタは、対応する変換済み座標データ又は演算済み形態データを用いてポリゴンが描画される度にデクリメントされる。図８に示す例は、図６に示すポリゴンＰ０〜Ｐ５の処理が完了し、まだポリゴンの描画が行われていない場合のキャッシュについて示している。
【０１０７】
また、キャッシュライン有効フラグが偽（Ｆ）のときは、まだ有効なデータがキャッシュラインメモリに格納されていないので、キャッシュラインメモリからのデータのロードはブロックする。
【０１０８】
図８の各キャッシュ（変換済み座標データキャッシュ１４０又は演算済み形態データキャッシュ１７０）の動作を説明する。
【０１０９】
まず、キャッシュは、頂点ＩＤの問い合わせが発生すると、参照カウンタが０でないこと、及び、キャッシュライン有効フラグが真であることのいずれかの条件を満たしたキャッシュラインの頂点ＩＤを検索することで、同じ頂点ＩＤの値を持つキャッシュラインが存在するかどうか確認する。
【０１１０】
頂点ＩＤの値が同じキャッシュラインが存在する場合は、キャッシュは、該当キャッシュラインの参照カウンタを＋１して、データの再ロード及び再計算は行わない。頂点ＩＤの値が同じキャッシュラインが存在しない場合は、キャッシュは、参照カウンタが０のキャッシュラインを検索して、問い合わせのあった頂点ＩＤを登録し、参照カウンタを１に設定する。そして、キャッシュは、キャッシュライン有効フラグを偽（Ｆ）に設定して、データのロード及び演算が行われるのを待機する。そして、演算後のデータがキャッシュに入力されると、キャッシュは、演算後のデータをキャッシュラインメモリに格納して、キャッシュライン有効フラグを真（Ｔ）に設定する。
【０１１１】
次に、ポリゴン描画の問い合わせのあった頂点ＩＤのデータをキャッシュラインメモリからロードして、ロードが完了したら該当キャッシュラインの参照カウンタを−１する。
【０１１２】
上記で説明した動作を行う図８のキャッシュで、本発明の実施の形態の処理を実行した場合、変換済み座標データキャッシュ１４０へは、頂点ＩＤリスト全てのアクセスが発生するため、ポリゴン描画の有効無効に関わらず一度は各頂点の座標データの処理が行われ、キャッシュラインメモリへの格納が行われる。一方で、演算済み形態データキャッシュ１７０へは、描画に必要な頂点の頂点ＩＤでのみアクセスが発生するため、形態データの処理及びキャッシュラインメモリへの格納は、必要最小限にのみ実行される。したがって、キャッシュラインメモリの領域を有効に利用することができ、従来の画像処理装置に比べてメモリアクセス及び演算量を低減することができる。
【０１１３】
以下では、上述した処理が実行される様子を、本実施の形態の画像生成装置１００が備える各処理部でのデータの流れに基づいて説明する。
【０１１４】
図９は、本実施の形態の画像生成装置１００が備える各処理部でのデータの流れを示す図である。同図に示すように、メモリ２００上に、入力ポリゴンモデルの頂点ＩＤリスト５０１、座標データリスト５０２及び形態データリスト５０３が配置されているとする。さらに、メモリ２００は、ポリゴン描画処理部１８０が出力する出力画像５０４も保持する。
【０１１５】
座標データチェック部１３１は、メモリ２００上の頂点ＩＤリスト５０１にアクセスして、頂点ＩＤ５０５をロードする。そして、座標データチェック部１３１は、変換済み座標データキャッシュ１４０へ問い合わせを行い、該当頂点の変換済み座標データが無い場合は、頂点ＩＤ５０５を座標データロード部１３２へ出力する。
【０１１６】
座標データロード部１３２は、メモリ２００上の座標データリスト５０２にアクセスして、頂点ＩＤ５０５に該当する座標データ５０６をロードし、ロードした座標データ５０６を座標変換部１３３へ出力する。
【０１１７】
座標変換部１３３は、座標データ５０６を座標変換することで、変換済み座標データ５０７を生成し、生成した変換済み座標データ５０７を変換済み座標データキャッシュ１４０へ格納する。
【０１１８】
ポリゴン消去判定部１５１は、変換済み座標データキャッシュ１４０から判定対象のポリゴンの頂点の頂点ＩＤ及び変換済み座標データをデータ５０８として受け取り、ポリゴン描画有効フラグを生成する。そして、ポリゴン消去判定部１５１は、頂点ＩＤ、変換済み座標データ及びポリゴン描画有効フラグをデータ５０９として頂点消去判定部１５２へ出力する。
【０１１９】
頂点消去判定部１５２は、ポリゴン消去判定部１５１から出力された頂点ＩＤ、変換済み座標データ及びポリゴン描画有効フラグ（データ５０９）を用いて頂点有効フラグを生成する。そして、頂点消去判定部１５２は、頂点ＩＤ、変換済み座標データ及び頂点有効フラグをデータ５１０として形態データアクセス頂点ＩＤ生成部１５３へ出力する。
【０１２０】
形態データアクセス頂点ＩＤ生成部１５３は、頂点消去判定部１５２から出力された頂点ＩＤ、変換済み座標データ及び頂点有効フラグ（データ５１０）を参照する。そして、形態データアクセス頂点ＩＤ生成部１５３は、頂点有効フラグが真であるときのみ、頂点ＩＤ及び変換済み座標データをデータ５１１として、形態データチェック部１６１へ出力する。
【０１２１】
形態データチェック部１６１は、形態データアクセス頂点ＩＤ生成部１５３から出力されたデータ５１１の頂点ＩＤを用いて、演算済み形態データキャッシュ１７０へ問い合わせを行う。そして、形態データチェック部１６１は、該当頂点の演算済み形態データが無い場合は、データ５１１に含まれる頂点ＩＤ及び変換済み座標データをデータ５１２として形態データロード部１６２へ出力する。
【０１２２】
形態データロード部１６２は、メモリ２００上の形態データリスト５０３にアクセスして、頂点ＩＤ及び変換済み座標データ（データ５１２）の頂点ＩＤに該当する形態データをロードする。そして、形態データロード部１６２は、変換済み座標データ及びロードした形態データをデータ５１３として形態データ演算部１６３へ出力する。
【０１２３】
形態データ演算部１６３は、変換済み座標データ及び形態データ（データ５１３）を用いて、演算済み形態データ５１４を計算する。そして、形態データ演算部１６３は、演算済み形態データ５１４を演算済み形態データキャッシュ１７０へ格納する。
【０１２４】
ポリゴン描画処理部１８０は、演算済み形態データキャッシュ１７０から描画対象のポリゴンの頂点の変換済み座標データ及び演算済み形態データ（データ５１５）を受け取り、ポリゴン描画処理を行い、メモリ２００上の出力画像５０４を生成する。
【０１２５】
本実施の形態の画像生成装置及び画像生成方法によれば、入力ポリゴンモデルの頂点データのうち座標データ以外の形態データを保持する演算済み形態データキャッシュへアクセスは、頂点消去判定で頂点が有効と判断された頂点ＩＤについてのみ行われる。
【０１２６】
これにより、メモリからグラフィックス処理ユニット（画像生成装置）への、入力ポリゴンモデルの頂点データのロードに関するメモリアクセス量及び演算量を低減することができる。したがって、従来の画像処理装置に比べて、低メモリバンド幅、低演算能力の情報処理装置の場合でも、入力ポリゴン数の多い高精細なポリゴン描画処理をリアルタイムで行うことができる。
【０１２７】
以上が、本発明の実施の形態における画像生成装置の動作についての説明である。
【０１２８】
以上、本発明の画像生成装置及び画像生成方法について、上記の実施の形態に基づいて説明したが、本発明は、この実施の形態に限定されるものではない。本発明の趣旨を逸脱しない限り、当業者が思いつく各種変形を実施の形態に施したものや、実施の形態の変形例における構成要素を組み合わせて構築される形態も本発明の範囲内に含まれる。
【０１２９】
例えば、入力ポリゴンモデルの表現形式についても、上記で示したポリゴンメッシュ形式以外の他の表現形式が含まれてもよい。また、頂点ＩＤリストについても画像生成装置１００内部又は外部で生成してもよい。
【０１３０】
図１０Ａ〜図１０Ｃは、ポリゴンメッシュ形式以外の表現形式（ポリゴンストリップ、ポリゴンファン、独立ポリゴン）からポリゴンメッシュ形式への変換の一例を示したものである。
【０１３１】
ポリゴンストリップ６０１、ポリゴンファン６０２又は独立ポリゴン６０３の形式で与えられた頂点ＩＤリスト６０４、６０７又は６１０は、それぞれポリゴンメッシュ形式の頂点ＩＤリスト６０５、６０８又は６１１に変換することが可能である。また、予め指定された頂点ＩＤリストが存在しない場合（座標データ及び形態データは先頭メモリアドレスから順にロードされることになる）においても、それぞれポリゴンメッシュ形式の頂点ＩＤリスト６０６、６０９、６１２を生成することが可能である。
【０１３２】
なお、図１０Ａにおいて、頂点ＩＤリスト６０５及び６０６に示される矢印は、ポリゴンストリップ形式の場合の頂点リストと順番が逆転していることを意味する。
【０１３３】
また、上記の実施の形態では、頂点の座標データ及び形態データの紐付けに頂点ＩＤを用いたが、頂点ＩＤの代わりに頂点の座標データ及び形態データへのメモリアドレスポインタなど別のデータを用いてもよい。
【０１３４】
また、ポリゴン消去判定部１５１は、クリッピング判定及びカリング判定を用いているが、描画オプションによってどちらか一方しか用いなくともよい。
【０１３５】
また、クリッピング判定として、３次元空間内の任意の平面を境界とした消去判定が含まれてもよい。あるいは、ディスプレイ面３０３上の任意の領域を境界とした消去判定が含まれてもよい。
【０１３６】
また、カリング判定として、ディスプレイ面３０３に投影したときに１ドットに満たないポリゴンの消去判定や、ビューボリューム３０２内の他のポリゴン描画によって視点３０１から全く見えなくなるポリゴンの消去判定が含まれてもよい。
【０１３７】
また、図２の画像生成装置１００に含まれる各ブロックは、一部又は全部を並列化又はパイプライン処理化してもよいし、複数のブロックを１つのブロックに統合してもよい。
【０１３８】
また、図２の画像生成装置１００に含まれる座標データチェック部１３１や変換済み座標データキャッシュ１４０の機能は実施の形態によっては、形態データチェック部１６１や演算済み形態データキャッシュ１７０に含まれたり、省略したりしてもよい。
【０１３９】
また、図２の画像生成装置１００は、演算済み形態データキャッシュ１７０を備え、演算済み形態データを演算済み形態データキャッシュ１７０に格納する構成について示したが、メモリ２００から読み出した形態データをキャッシュに格納してもよい。つまり、図１１に示すように、演算後の形態データをキャッシュに格納せずに、演算前の形態データをキャッシュに格納してもよい。
【０１４０】
図１１は、本発明の実施の形態の変形例に係る画像生成装置７００の構成の一例を示すブロック図である。
【０１４１】
図１１に示すように、画像生成装置７００は、座標データ処理部１３０と、判定部１５０と、形態データ処理部７６０と、形態データキャッシュ７７０と、ポリゴン描画処理部１８０とを備える。なお、図２と同様の構成については、同じ参照符号を付している。
【０１４２】
座標データ処理部１３０は、頂点データのうち座標データをメモリ２００からロードし、ロードした座標データを座標変換することで、変換済み座標データを生成する。
【０１４３】
判定部１５０は、座標データ処理部１３０によって生成された変換済み座標データを用いて、変換済み座標データが示す頂点が描画の対象であるか否かを判定する。
【０１４４】
形態データ処理部７６０は、判定部１５０によって変換済み座標データが示す頂点が描画の対象であると判定された場合に、形態データをポリゴン描画処理部１８０へ出力する。
【０１４５】
具体的には、形態データ処理部７６０は、判定部１５０によって変換済み座標データが示す頂点が描画の対象であると判定された場合で、かつ、形態データキャッシュ７７０に当該頂点の形態データが格納されていない場合には、メモリ２００から形態データをロードし、ロードした形態データを形態データキャッシュ７７０に格納する。また、形態データ処理部７６０は、判定部１５０によって変換済み座標データが示す頂点が描画の対象であると判定された場合で、かつ、形態データキャッシュ７７０に当該頂点の形態データが格納されている場合には、当該形態データを形態データキャッシュ７７０からポリゴン描画処理部１８０へ出力させる。
【０１４６】
ポリゴン描画処理部１８０は、座標データ処理部１３０によって生成された変換済み座標データと、形態データキャッシュ７７０に格納された形態データとを用いて、ポリゴンを描画する。
【０１４７】
以上の構成に示すように、本発明の実施の形態の変形例に係る画像生成装置７００は、メモリ２００からロードした形態データをそのまま形態データキャッシュ７７０に格納する。これにより、メモリ２００へのアクセスを低減することができる。また、上記の画像生成装置７００は、形態データの演算が必要でない場合にも有効である。
【０１４８】
また、図１２に示すように、本発明に係る画像生成装置は、図１１に示す構成に、さらに、変換済み座標データキャッシュを備える構成とすることもできる。図１２は、本発明の実施の形態の変形例に係る画像生成装置８００の構成の別の一例を示すブロック図である。
【０１４９】
図１２に示すように、画像生成装置８００は、図１１に示す画像生成装置７００と比較して、さらに変換済み座標データキャッシュ１４０を備える点が異なっている。図２及び図１１と同じ構成については、同じ参照符号を付し、以下では説明を省略する。
【０１５０】
判定部１５０は、変換済み座標データキャッシュ１４０に変換済み座標データが格納されている場合には、変換済み座標データキャッシュ１４０に格納されている変換済み座標データを用いて、当該変換済み座標データが示す頂点が描画の対象であるか否かを判定する。
【０１５１】
また、本発明は、図２、図１１又は図１２の画像生成装置１００、７００又は８００を含む情報処理装置として実現することができる。
【０１５２】
図１３は、図２の画像生成装置１００を含む情報処理装置９００の構成を示すブロック図である。同図に示す情報処理装置９００は、集積回路９０１と、メモリ９０８と、ディスプレイ９０９とを備える。
【０１５３】
集積回路９０１は、例えば、システムＬＳＩなどであり、ＣＰＵ９０２と、グラフィックス処理ユニット９０３（図２の画像生成装置１００）と、メモリコントローラ９０４と、ディスプレイコントローラ９０５と、ＣＰＵバス９０６と、メモリバス９０７とを備える。
【０１５４】
ＣＰＵ９０２は、描画命令リスト２０２及び頂点データリスト２０３を、メモリバス９０７とメモリコントローラ９０４とを介してメモリ９０８に格納する。また、ＣＰＵバス９０６を介して描画の指示をグラフィックス処理ユニット９０３へ伝える。
【０１５５】
グラフィックス処理ユニット９０３は、メモリバス９０７とメモリコントローラ９０４とを介して、メモリ９０８に格納されている描画命令リスト２０２及び頂点データリスト２０３にアクセスして、上述した画像生成処理を行う。生成した画像は、メモリバス９０７とメモリコントローラ９０４とを介してメモリ９０８に格納する。メモリ９０８に格納された生成画像は、ディスプレイコントローラ９０５を介してディスプレイ９０９へと出力される。
【０１５６】
なお、ＣＰＵ９０２による、頂点データリスト２０３のメモリ９０８への格納については、頂点データリスト２０３を、必ずロードされる頂点ＩＤリスト２０５と、重複する場合はロードされない座標データリスト２０６と、頂点消去判定結果で頂点が無効又は重複する場合はロードされない形態データリスト２０７とへ分割して、それぞれ別のメモリ領域に格納してもよい。これにより、メモリバス９０７及びメモリコントローラ９０４がバーストメモリアクセスによりメモリ９０８上の頂点データリスト２０３をロードする場合に、座標データとともに不要と判定された形態データまでロードしてしまうことを防ぐことができ、メモリアクセス効率を高めることができる。
【０１５７】
また、図１３の集積回路９０１のＣＰＵ９０２、グラフィックス処理ユニット９０３などの各機能ブロックは個別に集積回路化してもよいし、一部又は全部を含むように１つの集積回路としてもよい。集積回路９０１には、ＡＶ（Ａｕｄｉｏ  Ｖｉｓｕａｌ）処理ユニットやストリーミング処理ユニットなど他の機能ブロックが含んでいてもよい。メモリ９０８は、集積回路９０１の内部に搭載してもよいし、集積回路９０１の内部、外部を問わず複数個搭載してもよい。
【０１５８】
なお、本発明の実施の形態の画像生成装置は、典型的には半導体集積回路であるＬＳＩとして実現される。これらは個別に１チップ化されてもよいし、一部又は全てを含むように１チップ化されても良い。ここではＬＳＩとしたが、集積度の違いにより、ＩＣ、システムＬＳＩ、スーパーＬＳＩ、ウルトラＬＳＩと呼称されることもある。
【０１５９】
また、集積回路化の手法はＬＳＩに限るものではなく、専用回路又は汎用プロセッサで実現しても良い。ＬＳＩ製造後に、プログラムすることが可能なＦＰＧＡ（Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）や、ＬＳＩ内部の回路セルの接続や設定を再構成可能なリコンフィギュラブル・プロセッサを利用してもよい。
【０１６０】
さらには、半導体技術の進歩又は派生する別技術によりＬＳＩに置き換わる集積回路化の技術が登場すれば、当然、その技術を用いて機能ブロックの集積化を行ってもよい。バイオ技術の適応などが可能性として有り得る。
【０１６１】
さらに加えて、本発明の実施の形態の画像生成装置を集積化した半導体チップと、画像を描画するためのディスプレイとを組み合せて、様々な用途に応じた描画機器を構成することができる。携帯電話やテレビ、デジタルビデオレコーダ、デジタルビデオカメラ、カーナビゲーション等における情報描画手段として、本発明を利用することが可能である。ディスプレイとしては、ブラウン管（ＣＲＴ：Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ）の他、液晶やＰＤＰ（プラズマディスプレイパネル）、有機ＥＬ（Ｅｌｅｃｔｒｏｌｕｍｉｎｅｓｃｅｎｃｅ）などのフラットディスプレイ、プロジェクターを代表とする投射型ディスプレイなどと組み合わせることが可能である。
【産業上の利用可能性】
【０１６２】
本発明の実施の形態の画像生成装置は、様々な用途に利用可能である。例えば、携帯電話や携帯音楽プレーヤー、デジタルカメラ、デジタルビデオカメラ等の電池駆動の携帯表示端末や、テレビ、デジタルビデオレコーダ、カーナビゲーション等の高解像度の情報表示機器におけるメニュー表示やＷｅｂブラウザ、エディタ、ＥＰＧ（Ｅｌｅｃｔｒｏｎｉｃ  Ｐｒｏｇｒａｍ  Ｇｕｉｄｅ）、地図表示等における情報表示手段として利用価値が高い。
【符号の説明】
【０１６３】
１００、７００、８００  画像生成装置
１１０  ホストインタフェース
１２０  制御部
１３０  座標データ処理部
１３１  座標データチェック部
１３２  座標データロード部
１３３  座標変換部
１４０  変換済み座標データキャッシュ
１５０  判定部
１５１  ポリゴン消去判定部
１５２  頂点消去判定部
１５３  形態データアクセス頂点ＩＤ生成部
１６０、７６０  形態データ処理部
１６１  形態データチェック部
１６２  形態データロード部
１６３  形態データ演算部
１７０  演算済み形態データキャッシュ
１８０  ポリゴン描画処理部
１９０  メモリインタフェース
２００、９０８  メモリ
２０１  入力データ
２０２  描画命令リスト
２０３  頂点データリスト
２０４  描画命令
２０５、５０１  頂点ＩＤリスト
２０６、５０２  座標データリスト
２０７、５０３  形態データリスト
２０８、５０５  頂点ＩＤ
２０９、５０６  座標データ
２１０  形態データ
３０１  視点
３０２  ビューボリューム
３０３  ディスプレイ面
３０４、３０５、３０６  ポリゴン
４０１  ポリゴンメッシュ
４０２  タイムチャート
５０４  出力画像
５０７  変換済み座標データ
５０８、５０９、５１０、５１１、５１２、５１３、５１５  データ
５１４  演算済み形態データ
６０１  ポリゴンストリップ
６０２  ポリゴンファン
６０３  独立ポリゴン
６０４、６０５、６０６、６０７、６０８、６０９、６１０、６１１、６１２  頂点ＩＤリスト
７７０  形態データキャッシュ
９００  情報処理装置
９０１  集積回路
９０２  ＣＰＵ
９０３  グラフィックス処理ユニット
９０４  メモリコントローラ
９０５  ディスプレイコントローラ
９０６  ＣＰＵバス
９０７  メモリバス
９０９  ディスプレイ
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ポリゴンを描画することで、グラフィックス画像を生成する画像生成装置であって、
ポリゴンを構成する頂点の情報を示す頂点データのうち、前記頂点の位置を示す座標データをメモリからロードし、ロードした座標データを座標変換することで、変換済み座標データを生成する座標処理部と、
前記座標処理部によって生成された変換済み座標データを用いて、ポリゴンが描画の対象であるか否かを判定し、描画の対象であると判定されたポリゴンを構成する頂点を示す頂点リストを生成する判定部と、
前記頂点データのうち前記座標データ以外のデータである形態データを格納するための形態データキャッシュと、
前記形態データキャッシュに、前記判定部によって生成された頂点リストが示す頂点の前記形態データが格納されていない場合には、前記メモリから当該形態データをロードし、ロードした形態データを前記形態データキャッシュに格納する形態データ処理部と、
前記座標処理部によって生成された変換済み座標データと、前記形態データキャッシュに格納された形態データとを用いて、ポリゴンを描画するポリゴン描画処理部とを備える
画像生成装置。
【請求項２】
前記形態データキャッシュには、前記形態データが処理された演算済みの形態データが格納され、
前記形態データ処理部は、
前記判定部によって生成された頂点リストが示す頂点の演算済みの形態データが、前記形態データキャッシュに格納されているか否かを判定する形態データ確認部と、
前記形態データ確認部によって前記演算済みの形態データが格納されていないと判定された場合に、前記メモリから前記頂点の形態データをロードする形態データロード部と、
前記形態データロード部によってロードされた形態データを処理することで、前記演算済みの形態データを生成し、生成した演算済みの形態データを前記形態データキャッシュに格納する形態データ演算部とを備える
請求項１記載の画像生成装置。
【請求項３】
前記形態データキャッシュは、複数のキャッシュラインを含み、
前記複数のキャッシュラインのそれぞれは、
頂点のＩＤを示すキャッシュタグと、
前記キャッシュタグが示す頂点の演算済み形態データを格納するためのラインメモリと、
前記ラインメモリに格納されている演算済み形態データが有効であるか否かを示すフラグとを含み、
前記形態データ確認部は、前記頂点リストが示す頂点のＩＤが、有効であることを示すフラグに対応するキャッシュタグに格納されているか否かを判定し、
前記形態データロード部は、前記形態データ確認部によって格納されていないと判定された場合に、前記メモリから当該頂点の形態データをロードする
請求項２記載の画像生成装置。
【請求項４】
前記画像生成装置は、さらに、
前記座標処理部によって生成された変換済み座標データを格納するための座標データキャッシュを備え、
前記判定部は、
前記座標データキャッシュに前記変換済み座標データが格納されている場合には、前記座標データキャッシュに格納されている変換済み座標データを用いて、当該変換済み座標データが示す頂点が描画の対象であるか否かを判定する
請求項１記載の画像生成装置。
【請求項５】
ポリゴンを描画することで、グラフィックス画像を生成する画像生成方法であって、
ポリゴンを構成する頂点の情報を示す頂点データのうち、前記頂点の位置を示す座標データをメモリからロードし、ロードした座標データを座標変換することで、変換済み座標データを生成する座標処理ステップと、
前記座標処理ステップにおいて生成された変換済み座標データを用いて、ポリゴンが描画の対象であるか否かを判定し、描画の対象であると判定されたポリゴンを構成する頂点を示す頂点リストを生成する判定ステップと、
形態データを格納するための形態データキャッシュに、前記判定ステップにおいて生成された頂点リストが示す頂点の前記形態データが格納されていない場合には、前記メモリから当該形態データをロードし、ロードした形態データを前記形態データキャッシュに格納する形態データ処理ステップと、
前記座標処理ステップにおいて生成された変換済み座標データと、前記形態データキャッシュに格納された形態データとを用いて、ポリゴンを描画するポリゴン描画処理ステップとを含む
画像生成方法。
【請求項６】
ポリゴンを描画することで、グラフィックス画像を生成する集積回路であって、
ポリゴンを構成する頂点の情報を示す頂点データのうち、前記頂点の位置を示す座標データをメモリからロードし、ロードした座標データを座標変換することで、変換済み座標データを生成する座標処理部と、
前記座標処理部によって生成された変換済み座標データを用いて、ポリゴンが描画の対象であるか否かを判定し、描画の対象であると判定されたポリゴンを構成する頂点を示す頂点リストを生成する判定部と、
前記頂点データのうち前記座標データ以外のデータである形態データを格納するための形態データキャッシュと、
前記形態データキャッシュに、前記判定部によって生成された頂点リストが示す頂点の前記形態データが格納されていない場合には、前記メモリから当該形態データをロードし、ロードした形態データを前記形態データキャッシュに格納する形態データ処理部と、
前記座標処理部によって生成された変換済み座標データと、前記形態データキャッシュに格納された形態データとを用いて、ポリゴンを描画するポリゴン描画処理部とを備える
集積回路。
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】全図
【補正方法】変更
【補正の内容】
【図１】
2010146828.tif 000018
【図２】
2010146828.tif 000019
【図３】
2010146828.tif 000020
【図４】
2010146828.tif 000021
【図５】
2010146828.tif 000022
【図６】
2010146828.tif 000023
【図７】
2010146828.tif 000024
【図８】
2010146828.tif 000025
【図９】
2010146828.tif 000026
【図１０Ａ】
2010146828.tif 000027
【図１０Ｂ】
2010146828.tif 000028
【図１０Ｃ】
2010146828.tif 000029
【図１１】
2010146828.tif 000030
【図１２】
2010146828.tif 000031
【図１３】
2010146828.tif 000032
【国際調査報告】
2010146828.tif 000033
2010146828.tif 000034