(57)【要約】  インタラクティブ用途のＣＧ処理にも適用でき、かつ、入力ポリゴンモデルの頂点データのロードに関するメモリアクセス量を低減する。  ポリゴンを描画することでコンピュータグラフィックス画像を生成する画像生成装置（１００）であって、ポリゴンを構成する頂点の頂点データのうち、座標データをロードする座標データロード部（１０３）と、ロードされた座標データを異なる座標系に変換する座標変換部（１０４）と、変換されて得られる変換済み座標データを用いて、ポリゴンが描画の対象となるか否かを判定するポリゴン消去判定部（１０５）と、有効と判定されたポリゴンを構成する頂点は有効であると判定する頂点消去判定部（１０６）と、有効と判定された頂点のみに対応する形態データをロードする形態データロード部（１０７）と、ロードされた形態データと変換済み座標データとを用いてポリゴンを描画するポリゴン描画処理部（１０８）とを備える。
2008126392.tif 000002
【特許請求の範囲】
【請求項１】
ポリゴンを描画することでコンピュータグラフィックス画像を生成する画像生成装置であって、
ポリゴンを構成する頂点の情報を示す頂点データのうち、前記頂点の位置を示す座標データをロードする座標データロード手段と、
前記座標データロード手段によりロードされた前記座標データを異なる座標系に変換する座標変換手段と、
前記座標変換手段により変換されて得られる変換済み座標データを用いて前記ポリゴンが描画の対象であるか否かを判定することで、前記ポリゴンを構成する頂点が有効であるか否かを判定する判定手段と、
前記判定手段により有効と判定された頂点のみに対応する前記頂点データのうち前記座標データ以外の情報を示す形態データをロードする形態データロード手段と、
前記形態データロード手段によりロードされた形態データと前記変換済み座標データとを用いてポリゴンを描画するポリゴン描画手段とを備える
ことを特徴とする画像生成装置。
【請求項２】
前記座標変換手段による座標変換と、前記判定手段によるポリゴン判定及び頂点判定とは、前記座標データが１つロードされるたびにパイプラインで処理される
ことを特徴とする請求項１記載の画像生成装置。
【請求項３】
前記判定手段は、
前記変換済み座標データを用いて前記ポリゴンが描画の対象であるか否かを判定し、前記ポリゴンが描画の対象であるか否かを示すポリゴン有効フラグを出力するポリゴン判定部と、
共有の頂点を含む複数のポリゴンの、ポリゴン有効フラグの論理和演算を行うことで、前記頂点が有効であるか否かを判定する頂点判定部とを有する
ことを特徴とする請求項１記載の画像生成装置。
【請求項４】
前記画像生成装置は、さらに、
頂点が無効であることを示すように予め設定された中間結果フラグを保持する第１バッファを備え、
前記判定手段は、
前記変換済み座標データを用いて前記ポリゴンが描画の対象であるか否かを判定し、前記ポリゴンが描画の対象であるか否かを示すポリゴン有効フラグを出力するポリゴン判定部と、
前記ポリゴン有効フラグと、前記ポリゴン有効フラグに対応するポリゴンを構成する頂点の前記中間結果フラグとの論理和演算を行い、前記第１バッファに保持される中間結果フラグを更新することで、前記頂点が有効であるか否かを判定する頂点判定部とを有する
ことを特徴とする請求項１記載の画像生成装置。
【請求項５】
前記頂点判定部は、前記中間結果フラグと前記ポリゴン有効フラグとの論理和演算を行うことで、前記中間結果フラグの値が変更した場合に、頂点が有効であることを示す頂点有効フラグを出力し、
前記形態データロード手段は、前記頂点有効フラグを受け取ったときに、前記頂点有効フラグに対応する前記形態データをロードする
ことを特徴とする請求項４記載の画像生成装置。
【請求項６】
前記頂点判定部は、さらに、前記中間結果フラグの値が変更した場合、当該中間結果フラグを用いる論理和演算を行うことを停止する
ことを特徴とする請求項５記載の画像生成装置。
【請求項７】
前記座標データロード手段は、前記複数の座標データのみを格納する領域から前記座標データをロードし、
前記形態データロード手段は、前記複数の形態データのみを格納する領域から前記形態データをロードする
ことを特徴とする請求項１記載の画像生成装置。
【請求項８】
前記座標変換手段は、前記座標データをワールド座標系及びディスプレイ座標系に変換し、
前記判定手段は、前記ワールド座標系に変換された変換済み座標データを用いて実行されるクリッピング判定、及び、前記ディスプレイ座標系に変換された変換済み座標データを用いて実行されるカリング判定の少なくとも１つを行うことで、前記ポリゴンが有効であるか否かを判定し、有効であると判定されたポリゴンを構成する頂点を有効であると判定する
ことを特徴とする請求項１記載の画像生成装置。
【請求項９】
ポリゴンを描画することでコンピュータグラフィックス画像を生成する画像生成方法であって、
ポリゴンを構成する頂点の情報を示す頂点データのうち、前記頂点の位置を示す座標データをロードする座標データロードステップと、
前記座標データロードステップでロードされた前記座標データを異なる座標系に変換する座標変換ステップと、
前記座標変換ステップで変換されて得られる変換済み座標データを用いて前記ポリゴンが描画の対象であるか否かを判定することで、前記ポリゴンを構成する頂点が有効であるか否かを判定する判定ステップと、
前記判定ステップで有効と判定された頂点のみに対応する前記頂点データのうち前記座標データ以外の情報を示す形態データをロードする形態データロードステップと、
前記形態データロードステップでロードされた形態データと前記変換済み座標データとを用いてポリゴンを描画するポリゴン描画ステップとを含む
ことを特徴とする画像生成方法。
【請求項１０】
ポリゴンを描画することでコンピュータグラフィックス画像を生成する集積回路であって、
ポリゴンを構成する頂点の情報を示す頂点データのうち、前記頂点の位置を示す座標データをロードする座標データロード手段と、
前記座標データロード手段によりロードされた前記座標データを異なる座標系に変換する座標変換手段と、
前記座標変換手段により変換されて得られる変換済み座標データを用いて前記ポリゴンが描画の対象であるか否かを判定することで、前記ポリゴンを構成する頂点が有効であるか否かを判定する判定手段と、
前記判定手段により有効と判定された頂点のみに対応する前記頂点データのうち前記座標データ以外の情報を示す形態データをロードする形態データロード手段と、
前記形態データロード手段によりロードされた形態データと前記変換済み座標データとを用いてポリゴンを描画するポリゴン描画手段とを備える
ことを特徴とする集積回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータグラフィックス技術に関し、コンピュータグラフィックス画像を生成する画像生成装置及び画像生成方法に関するものである。
【背景技術】
【０００２】
コンピュータグラフィックス（ＣＧ：Ｃｏｍｐｕｔｅｒ  Ｇｒａｐｈｉｃｓ）画像を生成する処理は計算負荷が大きいため、リアルタイムで画像生成処理を行う情報処理装置では、中央演算処理装置（ＣＰＵ：Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）とは別に画像生成処理を専用で行う画像生成装置（グラフィックス処理ユニット）を備えている。【０００３】
図１は、従来の画像生成装置が行う画像生成方法の、一般的な処理を示すフローチャートである。【０００４】
従来の一般的な画像生成装置は、まず、入力ポリゴンモデルの頂点データを情報記憶装置（メモリ）からロードする（Ｓ１０１）。なお、頂点データは、頂点の位置を示す座標データと、座標データ以外のデータである形態データとからなる。次に、頂点データのうち座標データについてワールド座標への座標変換処理を行う（Ｓ１０２）。さらに、ワールド座標からディスプレイ座標への座標変換処理を行う（Ｓ１０３）。そして、変換座標データを用いて、ロードした頂点データから構成されるポリゴン毎に、ポリゴンが可視空間に入っているか否かを判定するクリッピング判定あるいはポリゴンが視点から見て表示すべき面を向いているか否かを判定するカリング判定により、ポリゴン描画が有効かどうかの判定を行う（Ｓ１０４）。有効であると判定されたポリゴンについてのみ、ロードした頂点データを用いてポリゴン描画処理を行う（Ｓ１０５）。以上の処理が全てのポリゴンについて終了したかを判定し（Ｓ１０６）、終了していない場合（Ｓ１０６で「継続」）、各処理（Ｓ１０１〜Ｓ１０５）が繰り返される。全てのポリゴンについて終了した場合（Ｓ１０６で「完了」）、画像生成装置は描画された画像を出力する。【０００５】
以上のような画像生成装置の例として、特許文献１及び特許文献２に開示されている技術がある。【０００６】
特許文献１は、シーンのカットなどが予め決まっている非インタラクティブ用途向けの技術を示している。特許文献１に示される技術では、描画に不要なデータを予め削減する。これにより、データをロードするためのメモリアクセス量を削減することができる。【０００７】
特許文献２は、入力ポリゴンデータのロード専用のデータキャッシュを備える技術を示している。特許文献２に示す技術は、一度ロードした頂点データを専用のデータキャッシュに記憶させておくことで、同じ頂点データを参照する場合は再ロードしない。これにより、メモリアクセス量を削減することができる。
【特許文献１】特開２００１−２０９３６９号公報
【特許文献２】特開２００１−１９５６０３号公報
【非特許文献１】コンピュータグラフィックス  ＣＧ−ＡＲＴＳ協会出版（第３４頁、第１００頁）
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、上記従来の画像生成装置では、入力ポリゴンモデルの頂点データを保持するメモリからグラフィックス処理ユニットへのメモリアクセス量が増大し、単位時間あたりの限界メモリアクセスデータ量であるメモリバンド幅を圧迫するという課題がある。【０００９】
具体的には、上記従来の画像生成装置では、入力ポリゴンモデルの頂点について座標データ及び形態データをメモリからグラフィックス処理ユニットへロードする。その後にクリッピング判定及びカリング判定を行っているため、ポリゴンの描画が有効であるかどうかに関わらず入力ポリゴンモデルの全ての頂点データをロードする必要がある。これにより、メモリからグラフィックス処理ユニットへのメモリアクセス量が増大し、メモリバンド幅を圧迫する。【００１０】
なお、特許文献１に示す技術では、ロードする頂点データの量を削減することができるため、非インタラクティブ用途に限定すれば課題を解決することが可能である。しかしながら、特許文献１には、ユーザの操作が加わるインタラクティブ用途のＣＧ処理に用いることができないという課題がある。【００１１】
また、特許文献２に示す技術では、同じ頂点データを参照する場合は再ロードしないことでメモリアクセス量を低減することができる。しかしながら、少なくとも１回は、ポリゴン描画が有効であるかどうかに関わらず頂点データをロードしてしまうため、上記課題の解決方法としては不十分である。【００１２】
以上のように、上記の課題を解決するための方法は存在しておらず、例えば、低メモリバンド幅の情報処理装置で入力ポリゴン数の多い高精細なポリゴン描画処理をリアルタイムで行うことは非常に困難であった。【００１３】
そこで、本発明は、インタラクティブ用途のＣＧ処理にも適用でき、かつ、入力ポリゴンモデルの頂点データのロードに関するメモリアクセス量を低減することができる、画像生成装置及び画像生成方法を提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記の課題を解決するために、本発明の画像生成装置は、ポリゴンを描画することでコンピュータグラフィックス画像を生成する画像生成装置であって、ポリゴンを構成する頂点の情報を示す頂点データのうち、前記頂点の位置を示す座標データをロードする座標データロード手段と、前記座標データロード手段によりロードされた前記座標データを異なる座標系に変換する座標変換手段と、前記座標変換手段により変換されて得られる変換済み座標データを用いて前記ポリゴンが描画の対象であるか否かを判定することで、前記ポリゴンを構成する頂点が有効であるか否かを判定する判定手段と、前記判定手段により有効と判定された頂点のみに対応する前記頂点データのうち前記座標データ以外の情報を示す形態データをロードする形態データロード手段と、前記形態データロード手段によりロードされた形態データと前記変換済み座標データとを用いてポリゴンを描画するポリゴン描画手段とを備える。【００１５】
これにより、頂点データのうち従来は全ての形態データをロードしていたのに対して、ポリゴン描画に必要な形態データのみをロードすることができる。また、ポリゴン描画が実行されるか否かをロードした座標データから検出することができる。よって、非インタラクティブ用途だけでなく、インタラクティブ用途のＣＧ処理にも適用でき、かつ、入力ポリゴンモデルの頂点データのロードに関するメモリアクセス量を低減することができる。【００１６】
また、前記座標変換手段による座標変換と、前記判定手段によるポリゴン判定及び頂点判定とは、前記座標データが１つロードされるたびにパイプラインで処理されてもよい。【００１７】
これにより、低メモリバンド幅の情報処理装置で、入力ポリゴン数の多い高精細なポリゴン描画処理をリアルタイムで行うことができる。【００１８】
また、前記判定手段は、前記変換済み座標データを用いて前記ポリゴンが描画の対象であるか否かを判定し、前記ポリゴンが描画の対象であるか否かを示すポリゴン有効フラグを出力するポリゴン判定部と、共有の頂点を含む複数のポリゴンの、ポリゴン有効フラグの論理和演算を行うことで、前記頂点が有効であるか否かを判定する頂点判定部とを有してもよい。【００１９】
また、前記画像生成装置は、さらに、頂点が無効であることを示すように予め設定された中間結果フラグを保持する第１バッファを備え、前記判定手段は、前記変換済み座標データを用いて前記ポリゴンが描画の対象であるか否かを判定し、前記ポリゴンが描画の対象であるか否かを示すポリゴン有効フラグを出力するポリゴン判定部と、前記ポリゴン有効フラグと、前記ポリゴン有効フラグに対応するポリゴンを構成する頂点の前記中間結果フラグとの論理和演算を行い、前記第１バッファに保持される中間結果フラグを更新することで、前記頂点が有効であるか否かを判定する頂点判定部とを有してもよい。【００２０】
これにより、論理和演算を実行するだけで頂点が有効であるか否かを判定することができるので、頂点判定に関わる処理量を低減することができる。【００２１】
また、前記頂点判定部は、前記中間結果フラグと前記ポリゴン有効フラグとの論理和演算を行うことで、前記中間結果フラグの値が変更した場合に、頂点が有効であることを示す頂点有効フラグを出力し、前記形態データロード手段は、前記頂点有効フラグを受け取ったときに、前記頂点有効フラグに対応する前記形態データをロードしてもよい。【００２２】
これにより、頂点が有効であると判定されるたびに、当該頂点に対応する形態データをロードすることができるので、メモリバンド幅を圧迫することを低減することができる。【００２３】
また、前記頂点判定部は、さらに、前記中間結果フラグの値が変更した場合、当該中間結果フラグを用いる論理和演算を行うことを停止してもよい。【００２４】
これにより、一度、有効であると判定された頂点に対して、再度、頂点判定が行われることを防ぐことができ、処理量を低減することができる。【００２５】
また、前記座標データロード手段は、前記複数の座標データのみを格納する領域から前記座標データをロードし、前記形態データロード手段は、前記複数の形態データのみを格納する領域から前記形態データをロードしてもよい。【００２６】
これにより、必ず全てをロードしなければならない座標データと、必要に応じてロードする形態データとを分離して格納しておくことで、一度のメモリアクセスでメモリアドレスが連続する領域のデータを一括して多くロードするバーストメモリアクセスによって頂点データをロードする場合に、座標データとともに不要と判定された形態データまでロードしてしまうことを防ぐことができ、メモリアクセス効率を高めることができる。【００２７】
また、具体的には、前記座標変換手段は、前記座標データをワールド座標系及びディスプレイ座標系に変換し、前記判定手段は、前記ワールド座標系に変換された変換済み座標データを用いて実行されるクリッピング判定、及び、前記ディスプレイ座標系に変換された変換済み座標データを用いて実行されるカリング判定の少なくとも１つを行うことで、前記ポリゴンが有効であるか否かを判定し、有効であると判定されたポリゴンを構成する頂点を有効であると判定してもよい。【００２８】
また、本発明は、画像生成装置として実現することができるだけではなく、画像生成装置を構成する各処理手段をステップとする画像生成方法として実現することもできる。【００２９】
さらに、本発明は、集積回路としても実現することができ、ポリゴンを描画することでコンピュータグラフィックス画像を生成する集積回路であって、ポリゴンを構成する頂点の情報を示す頂点データのうち、前記頂点の位置を示す座標データをロードする座標データロード手段と、前記座標データロード手段によりロードされた前記座標データを異なる座標系に変換する座標変換手段と、前記座標変換手段により変換されて得られる変換済み座標データを用いて前記ポリゴンが描画の対象であるか否かを判定することで、前記ポリゴンを構成する頂点が有効であるか否かを判定する判定手段と、前記判定手段により有効と判定された頂点のみに対応する前記頂点データのうち前記座標データ以外の情報を示す形態データをロードする形態データロード手段と、前記形態データロード手段によりロードされた形態データと前記変換済み座標データとを用いてポリゴンを描画するポリゴン描画手段とを備える。
【発明の効果】
【００３０】
本発明によれば、メモリからグラフィックス処理ユニットへの、入力ポリゴンモデルの頂点データのロードに関するメモリアクセス量を大幅に低減することができる。これにより例えば、低メモリバンド幅の情報処理装置で入力ポリゴン数の多い高精細なポリゴン描画処理をリアルタイムで行うことができる。
【図面の簡単な説明】
【００３１】
【図１】図１は、従来の画像生成装置の動作を示すフローチャートである。
【図２】図２は、本実施の形態の画像生成装置の構成を示すブロック図である。
【図３】図３は、本実施の形態の画像生成装置への入力データを示す図である。
【図４】図４は、ポリゴン消去判定を示す図である。
【図５】図５は、本実施の形態の画像生成装置の動作を示すフローチャートである。
【図６】図６は、ポリゴンストリップ形式の処理の流れを示す図である。
【図７】図７は、ポリゴンストリップ形式に適応した画像生成装置の各処理部でのデータの流れを示す図である。
【図８】図８は、ポリゴンファン形式の処理の流れを示す図である。
【図９】図９は、ポリゴンファン形式に適応した画像生成装置の各処理部でのデータの流れを示す図である。
【図１０】図１０は、ポリゴンメッシュ形式の処理の流れを示す図である。
【図１１】図１１は、ポリゴンメッシュ形式に適応した画像生成装置の各処理部でのデータの流れを示す図である。
【図１２】図１２は、本実施の形態の画像生成装置を備える情報処理装置の構成を示すブロック図である。
【符号の説明】
【００３２】
１００  画像生成装置
１０１  ホストインターフェース
１０２  制御部
１０３  座標データロード部
１０４  座標変換部
１０５  ポリゴン消去判定部
１０６  頂点消去判定部
１０７  形態データロード部
１０８  ポリゴン描画処理部
１０９  メモリインターフェース
１１０  変換座標バッファ
１１１  頂点消去判定バッファ
２００、１００８  メモリ
２０１  入力データ
２０２  描画命令リスト
２０３  頂点データリスト
２０４  描画命令
２０５、５０１、７０１、９０１  座標データリスト
２０６、５０２、７０２、９０２  形態データリスト
２０７、５０４、７０４、９０４  座標データ
２０８  形態データ
３０１  視点
３０２  ビューボリューム
３０３  ディスプレイ面
３０４、３０５、３０６  ポリゴン
４０１  ポリゴンストリップ
４０２、６０２、８０２  タイムチャート
５０３、７０３、９０３  出力画像
５０５、５０６、５１０、７０５、７０６、７０７、７１２、９０５、９０６、９１０  変換済み座標データ
５０７、５０８、７０８、７１０、９０７  ポリゴン描画有効フラグ
５０９、７１１、９０９  頂点有効フラグ
５１１、７１３、９１１  頂点データ
６０１  ポリゴンファン
７０９、９０８  中間結果フラグ
８０１  ポリゴンメッシュ
１０００  情報処理装置
１００１  集積回路
１００２  ＣＰＵ
１００３  グラフィックス処理ユニット
１００４  メモリコントローラ
１００５  ディスプレイコントローラ
１００６  ＣＰＵバス
１００７  メモリバス
１００９  ディスプレイ
【発明を実施するための最良の形態】
【００３３】
以下、本発明の実施の形態について、図面を参照しながら説明する。【００３４】
本実施の形態の画像生成装置は、頂点がポリゴン描画に必要とされるか否かを判定し、必要と判定された頂点のみに対応する形態データをロードし、ロードしたデータを用いてポリゴンを描画することでコンピュータグラフィックス画像を生成する装置である。【００３５】
図２は、本実施の形態の画像生成装置の構成を示すブロック図である。同図の画像生成装置１００は、ポリゴン描画に関する入力データ２０１を保持するメモリ２００から必要なデータを読み出すことにより、ポリゴン描画を実行する装置である。まず、メモリ２００が格納する入力データ２０１について説明する。【００３６】
図３は、本実施の形態の画像生成装置への入力データを示す図である。同図に示すように、入力データ２０１は、描画命令リスト２０２と、入力ポリゴンモデルの頂点データリスト２０３とで構成される。【００３７】
描画命令リスト２０２は、ポリゴン描画命令に関する様々な情報を示す描画命令２０４を含む。図３に示すように、描画命令２０４は、入力ポリゴンの表現形式（ポリゴンストリップ、ポリゴンファン及びポリゴンメッシュなど）、各パラメータのロード設定（各種データのアドレス設定）、及び、描画オプションなどを示す。【００３８】
頂点データリスト２０３は、入力ポリゴンモデルの頂点データのリストであり、座標データリスト２０５と形態データリスト２０６とで構成される。なお、頂点データとは、ポリゴンを構成する頂点の情報を示すデータであり、座標データと形態データとからなる。【００３９】
図３に示すように、頂点データリスト２０３は、座標データリスト２０５と形態データリスト２０６とへ分割してそれぞれ別のメモリ領域に格納してもよい。これにより、一度のメモリアクセスでメモリアドレスが連続する領域のデータを一括して多くロードするバーストメモリアクセスによって頂点データリスト２０３をロードする場合に、座標データとともに不要と判定された形態データまでロードしてしまうことを防ぐことができ、メモリアクセス効率を高めることができる。【００４０】
座標データリスト２０５は、入力ポリゴンモデルの各頂点の位置を示す座標データ２０７のリストである。【００４１】
形態データリスト２０６は、各頂点の座標データ以外の情報を示す形態データ２０８のリストである。図３には、一例として、各頂点の法線データ、カラーデータ、及び、テクスチャ座標データを示す。【００４２】
図２の画像生成装置１００は、ホストインターフェース１０１と、制御部１０２と、座標データロード部１０３と、座標変換部１０４と、ポリゴン消去判定部１０５と、頂点消去判定部１０６と、形態データロード部１０７と、ポリゴン描画処理部１０８と、メモリインターフェース１０９と、変換座標バッファ１１０と、頂点消去判定バッファ１１１とを備える。【００４３】
ホストインターフェース１０１は、ＣＰＵから入力される描画開始の指示を制御部１０２へと伝える。【００４４】
制御部１０２は、描画開始の指示を受け取るとメモリバスを介してメモリインターフェース１０９から描画命令リスト２０２をロードして、描画命令２０４を座標データロード部１０３及び形態データロード部１０７に伝える。【００４５】
座標データロード部１０３は、描画命令２０４に従って頂点データリスト２０３のうち座標データリスト２０５にアクセスし、頂点毎の座標データ２０７をロードして座標変換部１０４へ出力する。【００４６】
座標変換部１０４は、入力された座標データ２０７に対して座標変換処理を行い、変換済み座標データをポリゴン消去判定部１０５へ出力する。座標変換処理とは、座標データ２０７をワールド座標及びディスプレイ座標に変換することである。【００４７】
ポリゴン消去判定部１０５は、変換済み座標データを用いてポリゴンが描画の対象であるか否か、すなわち、ポリゴン描画が有効かどうかを示すフラグ（以下、ポリゴン描画有効フラグ）を生成する。具体的には、まず、ポリゴン消去判定部１０５は、変換済み座標データを変換座標バッファ１１０へ格納する。これは、ポリゴン描画が有効か否かの判定（以下、ポリゴン消去判定）には、複数の変換済み座標データが必要となるためである。そして、判定対象のポリゴンを構成する頂点の変換済み座標データを変換座標バッファ１１０から取り出して、ポリゴン消去判定を行う。そして、判定結果に基づいてポリゴン描画有効フラグを生成して、頂点消去判定部１０６へと出力する。ポリゴン描画有効フラグは、対応するポリゴンが有効であれば真、対応するポリゴンが無効であれば偽を示す。ポリゴン消去判定の具体例については、ポリゴンの表現形式毎に後述する。【００４８】
頂点消去判定部１０６は、ポリゴン描画有効フラグを用いて頂点が有効かどうかを示すフラグ（以下、頂点有効フラグ）を生成する。具体的には、まず、頂点消去判定部１０６は、ポリゴン消去判定部１０５から出力されたポリゴン描画有効フラグ又はこのポリゴン描画有効フラグを用いて生成される中間的な頂点消去判定結果を示すフラグ（以下、中間結果フラグ）を頂点消去判定バッファ１１１へ格納する。これは、頂点消去判定には、複数のポリゴン描画有効フラグ又は中間結果フラグが必要となるためである。そして、判定対象の頂点を含むポリゴンのポリゴン描画有効フラグ、又は判定対象の頂点の中間結果フラグを頂点消去判定バッファ１１１から取り出して、頂点が有効であるか否かを判定する。そして、判定結果に基づいて頂点有効フラグを生成して、形態データロード部１０７へと出力する。頂点有効フラグ及び中間結果フラグは、対応する頂点が有効であれば真、対応する頂点が無効であれば偽を示す。【００４９】
形態データロード部１０７は、描画命令２０４に従って頂点データリスト２０３のうち形態データリスト２０６にアクセスし、形態データ２０８のロードを行う。具体的には、形態データロード部１０７は、頂点消去判定部１０６から出力された頂点有効フラグを参照することで、有効な頂点データについてのみ形態データのロードを行い、変換済み座標データと合わせてポリゴン描画処理部１０８へと出力する。【００５０】
ポリゴン描画処理部１０８は、入力された頂点データ（変換済み座標データ及び形態データ）を用いてポリゴン描画処理を行い、ポリゴン画像を生成する。ポリゴン描画処理は、コンピュータグラフィックス処理で用いられる一般的な処理により実行される。ポリゴン描画処理部１０８は、メモリインターフェース１０９を介して生成したポリゴン画像をメモリへと出力する。【００５１】
メモリインターフェース１０９は、画像生成装置１００が備える各処理部とメモリ２００との間でデータのやり取りを行う。【００５２】
変換座標バッファ１１０は、座標変換部１０４で変換された変換済み座標データを保持する。変換座標バッファ１１０は、ポリゴン消去判定部１０５における判定処理の対象となるポリゴンが複数の頂点（本実施の形態では３つの頂点）で構成されるために、一時的に変換済み座標データを保持するためのバッファである。また、ポリゴン描画処理部１０８における描画処理でも変換済み座標データを用いるために、変換済み座標データを保持するためのバッファである。【００５３】
頂点消去判定バッファ１１１は、ポリゴン描画有効フラグ又は中間結果フラグを保持する。【００５４】
続いて、ポリゴン消去判定部１０５が行うポリゴン消去判定について説明する。図４は、ポリゴン消去判定を説明するための図である。ポリゴン消去判定とは、複数の頂点から構成されるポリゴンが画像生成時に用いられるか否かを判定する処理である。【００５５】
ポリゴン消去判定では、視点３０１を原点とした座標系（ディスプレイ座標系）へ変換した座標データを用いる。ポリゴン消去判定は、クリッピング判定及びカリング判定により行う。【００５６】
クリッピング判定は、非特許文献１に記載されている方法のように、ポリゴンが可視空間を表す六面体であるビューボリューム３０２の中に入っているかどうかを判定する処理である。ポリゴンを構成する頂点のうち全ての頂点の座標がビューボリューム３０２の外に存在していればポリゴン描画は無効となる。例えば、ポリゴン３０５のように完全にビューボリューム３０２の外に存在するポリゴンは、クリッピング判定により描画が無効となる。【００５７】
一方、カリング判定では、ビューボリューム３０２の中に入っているポリゴンについて視点から見たときのポリゴン面が表向きかどうかを判定する。カリング判定は、非特許文献１に記載されている方法のように、ポリゴンを構成する頂点の座標から面法線ベクトルを求め視点方向ベクトルとの内積の符号を確認することでポリゴンの表裏を判定することができる。視点３０１から見て裏向きであればポリゴン描画は無効となる。例えば、ポリゴン３０６のようにポリゴン面が視点３０１から見て裏向きであるポリゴンはカリング判定により描画が無効となる。【００５８】
ポリゴン３０４のように、クリッピング判定及びカリング判定で無効と判断されなかったポリゴンについてのみディスプレイ面３０３に投影して描画することができる有効なポリゴンと判定する。【００５９】
続いて、本実施の形態の画像生成装置の動作について説明する。【００６０】
図５は、本実施の形態の画像生成装置の動作を示すフローチャートである。本実施の形態の画像生成処理は、まず、ホストインターフェース１０１を介してＣＰＵから描画命令を制御部１０２が受け取ることで開始する。【００６１】
制御部１０２からの指示に基づいて、座標データロード部１０３は、入力ポリゴンモデルの頂点データのうち座標データのロードを行う（Ｓ２０１）。座標変換部１０４は、ロードされた座標データをワールド座標及びディスプレイ座標へと変換する（Ｓ２０２）。ポリゴン消去判定部１０５は、判定対象のポリゴンを構成する頂点の変換済み座標データを用いてポリゴン消去判定を行う（Ｓ２０３）。頂点消去判定部１０６は、判定対象の頂点を含むポリゴンのポリゴン消去判定結果を用いて頂点消去判定を行う（Ｓ２０４）。判定対象の頂点を含む全てのポリゴンについてのポリゴン消去判定結果で、１つ以上のポリゴン描画が有効であった場合、判定対象の頂点は有効な頂点データであると判定する（Ｓ２０４で「頂点が有効」）。全部のポリゴン描画が無効であった場合は無効な頂点データであると判定する（Ｓ２０４で「頂点が無効」）。形態データロード部１０７は、頂点消去判定部１０６により生成された頂点消去判定結果を参照して、有効とされた頂点データについてのみその形態データのロードを行う（Ｓ２０５）。ロードした形態データと該当する頂点の変換済み座標データとを合わせてポリゴン描画処理部１０８へと出力する。ポリゴン描画処理部１０８は、形態データロード部１０７から受け取った頂点データ（変換済み座標データ及び形態データ）を用いてポリゴン描画処理を行う（Ｓ２０６）。以上の処理が全てのポリゴンについて終了したかを判定し（Ｓ２０７）、終了していない場合（Ｓ２０７で「継続」）、各処理（Ｓ２０１〜Ｓ２０６）が繰り返される。全てのポリゴンについて終了した場合（Ｓ２０７で「完了」）、画像生成装置１００は描画された画像を出力する（Ｓ２０８）。【００６２】
以上のようにして、本実施の形態の画像生成装置は、頂点データのうち全ての座標データをロードするのに対して、形態データについては、有効な頂点と判定された頂点に対応する形態データのみをロードする。これにより、入力ポリゴンデータのロードに関するメモリアクセス量を低減することができる。また、本実施の形態の画像生成装置は、画像の描画処理と並行して、頂点がポリゴン描画に必要であるか否かを判定するため、インタラクティブ用途にも適用することができる。【００６３】
以下では、ポリゴンの表現形式に基づいて、より具体的に本実施の形態の画像生成装置について説明する。ここでは、ポリゴンストリップ、ポリゴンファン及びポリゴンメッシュの３つの表現形式について説明する。【００６４】
（ポリゴンストリップ形式）
まず、入力ポリゴンモデルがポリゴンストリップ形式で構成されている場合について説明する。【００６５】
図６は、入力ポリゴンモデルがポリゴンストリップ形式で構成されている場合の処理の流れを示す図である。ポリゴンストリップ形式は、頂点を共有しながら連続でポリゴンを描画する形式である。同図に示すように、ポリゴンストリップ４０１のポリゴンＰｊ（ｊ＝０〜６）は、頂点Ｖｊ、Ｖｊ＋１、Ｖｊ＋２の３点から構成される。また、ポリゴンストリップ４０１の頂点データは、Ｖ０→Ｖ１→Ｖ２→Ｖ３→Ｖ４→Ｖ５→Ｖ６→Ｖ７→Ｖ８の順で指定される。なお、図６に示す例においては、ポリゴンＰ０、Ｐ１及びＰ６が有効なポリゴンであるとする。【００６６】
タイムチャート４０２は、座標データのロードから頂点有効フラグの生成（頂点判定処理）までの処理の流れを示すタイムチャートである。以下では、タイムチャート４０２に沿ってポリゴンストリップ形式の処理の流れを説明する。【００６７】
座標データロード部１０３は、頂点データの指定順に、頂点データのうち座標データＭｉ（ｉ＝０〜８）のロードを順次行い、座標変換部１０４へ出力する。座標変換部１０４は、座標データロード部１０３から受け取った頂点Ｖｉの座標データＭｉについてそれぞれ座標変換を行う。これにより、変換済み座標データＤｉをポリゴン消去判定部１０５に出力する。ポリゴン消去判定部１０５は、入力された変換済み座標データＤｉを変換座標バッファ１１０に保持させる。【００６８】
ポリゴン消去判定部１０５は、ポリゴン消去判定をＰ０→Ｐ１→Ｐ２→Ｐ３→Ｐ４→Ｐ５→Ｐ６の順に行う。ポリゴン消去判定部１０５は、ポリゴンＰｊについてのポリゴン消去判定を行うときに、ポリゴンＰｊを構成する頂点Ｖｊ、Ｖｊ＋１、Ｖｊ＋２の変換済み座標データＤｊ、Ｄｊ＋１、Ｄｊ＋２が揃うまで、座標変換部１０４が生成した変換済み座標データを保持させる。変換済み座標データが揃ったときに変換済み座標データを用いてポリゴン消去判定を行い、ポリゴン描画有効フラグＦＰｊ（ポリゴンが有効であれば真、無効であれば偽）を生成する。【００６９】
頂点消去判定部１０６は、頂点消去判定をＶ０→Ｖ１→Ｖ２→Ｖ３→Ｖ４→Ｖ５→Ｖ６→Ｖ７→Ｖ８の順に行う。頂点消去判定部１０６は、頂点Ｖｉについての頂点消去判定を行うときに、頂点Ｖｉを含むポリゴンＰｉ−２、Ｐｉ−１及びＰｉのポリゴン描画有効フラグＦＰｉ−２、ＦＰｉ−１、ＦＰｉ（存在しないポリゴン番号のポリゴン描画有効フラグは偽として扱う）の論理和演算を行う。すなわち、頂点Ｖｉが有効であるか否かを示す頂点有効フラグＦＶｉは、以下の式１に基づいて算出される。【００７０】
ＦＶｉ＝ＦＰｉ−２‖ＦＰｉ−１‖ＦＰｉ    ・・・（式１）【００７１】
なお、頂点消去判定部１０６は、ポリゴン描画有効フラグＦＰｉ−２、ＦＰｉ−１、ＦＰｉが揃うまで、ポリゴン消去判定部１０５が生成したポリゴン描画有効フラグ又はその中間的な論理和を頂点消去判定バッファ１１１に保持させる。例えば、頂点Ｖ２については、頂点Ｖ２が含まれるポリゴンＰ０、Ｐ１及びＰ２のうちＰ０及びＰ１についてポリゴン描画が有効であるため、有効な頂点データと判定する。一方、頂点Ｖ４については、頂点Ｖ４が含まれるポリゴンＰ２、Ｐ３及びＰ４のいずれもポリゴン描画が無効であるため、無効な頂点データと判定する。【００７２】
形態データロード部１０７は、頂点消去判定部１０６により有効と判定された頂点Ｖ０、Ｖ１、Ｖ２、Ｖ３、Ｖ６、Ｖ７及びＶ８について頂点消去判定の順に形態データのロードを行い、該当する頂点の変換済み座標データと合わせてポリゴン描画処理部１０８へ出力する。ポリゴン描画処理部１０８は、これらの頂点データを受け取ってポリゴン描画処理を行う。【００７３】
なお、以上の処理は、パイプライン形式で実行される。すなわち、図６のタイムチャート４０２で示すように、頂点Ｖ０から順に、座標データのロードを行い、ロードした座標データを変換することで変換済み座標データを生成する。そして、頂点Ｖ２に対応する変換済み座標データＤ２を生成して初めて、ポリゴン消去判定及び頂点消去判定が実行できる。以降、座標データがロードされる毎に、座標変換、ポリゴン消去判定及び頂点消去判定が実行される。以下では、パイプライン形式で上述した処理が実行される様子を、本実施の形態の画像生成装置１００の、各処理部でのデータの流れに基づいて説明する。【００７４】
図７は、ポリゴンストリップ形式に適応した画像生成装置の、各処理部でのデータの流れを示す図である。同図に示すように、メモリ２００上にポリゴンストリップの座標データリスト５０１及び形態データリスト５０２が配置されているとする。さらに、メモリ２００は、ポリゴン描画処理部１０８で描画された出力画像５０３も保持する。【００７５】
座標データロード部１０３は、メモリ２００上の座標データリスト５０１にアクセスして、座標データ５０４を順次ロードして座標変換部１０４へ出力する。【００７６】
座標変換部１０４は、座標データ５０４から変換済み座標データ５０５を計算してポリゴン消去判定部１０５へ出力する。【００７７】
ポリゴン消去判定部１０５は、変換済み座標データ５０５を変換座標バッファ１１０へと格納する。上述したように本実施の形態では、ポリゴンは３つの頂点で構成されるため、変換座標バッファ１１０は、３つの変換済み座標データ５０６を格納することができる。変換座標バッファ１１０は、ＦＩＦＯ（Ｆｉｒｓｔ  Ｉｎ  Ｆｉｒｓｔ  Ｏｕｔ）形式で制御され、入力される座標データを順次格納する。ポリゴン消去判定に用いる必要がなくなった座標データについては、変換座標バッファ１１０から削除され、有効な頂点に対応する変換済み座標データについては形態データロード部１０７に出力される。【００７８】
ポリゴン消去判定部１０５は、変換座標バッファ１１０に格納される変換済み座標データを用いて、クリッピング判定及びカリング判定を実行することにより、ポリゴンが有効であるか否かを判定する。そして、判定結果に基づいて、ポリゴン描画有効フラグ５０７を頂点消去判定部１０６に出力する。【００７９】
頂点消去判定部１０６は、ポリゴン描画有効フラグ５０７を頂点消去判定バッファ１１１へと格納する。頂点消去判定バッファ１１１も、ＦＩＦＯ形式で制御され、格納されているポリゴン描画有効フラグ５０８へ新しいポリゴン描画有効フラグを登録するとき、古いポリゴン描画有効フラグから順に削除する。頂点消去判定部１０６は、ポリゴン描画有効フラグ５０８を用いて頂点有効フラグ５０９を生成する。頂点有効フラグ５０９は、上述したように式１を用いて生成される。頂点消去判定部１０６は、生成した頂点有効フラグ５０９を形態データロード部１０７へと出力する。【００８０】
なお、頂点消去判定バッファ１１１は、判定対象となる頂点が含まれる全てのポリゴン（図７では３つ）のポリゴン描画有効フラグのみを保持するように制御されている。これは、ポリゴンストリップ形式では頂点の指定順にポリゴンが描画され、かつ、頂点消去判定バッファ１１１がＦＩＦＯ形式で制御されるためである。したがって、頂点消去判定部１０６は、常に頂点消去判定バッファ１１１に格納されるポリゴン描画有効フラグ５０８（図７では２つ）の論理和演算を行うことで、頂点有効フラグを生成することができる。【００８１】
形態データロード部１０７は、頂点有効フラグ５０９を参照して有効な頂点であるときのみ、メモリ２００上の形態データリスト５０２にアクセスして該当する頂点の形態データをロードする。さらに、該当頂点の変換済み座標データ５１０を変換座標バッファ１１０から受け取り、形態データと合わせて頂点データ５１１としてポリゴン描画処理部１０８へ出力する。【００８２】
ポリゴン描画処理部１０８は、頂点データ５１１を用いてポリゴン描画処理を行い、メモリ２００上の出力画像５０３を生成する。【００８３】
以上のように、変換座標バッファ１１０及び頂点消去判定バッファ１１１をＦＩＦＯ形式で制御することにより、座標データのロード処理と、座標変換処理と、ポリゴン消去判定処理と、頂点消去判定処理と、形態データのロード処理と、ポリゴン描画処理とをパイプライン形式で制御することができる。【００８４】
これにより、メモリ２００へのアクセス量を大幅に低減することができ、メモリバンド幅を圧迫することがなくなる。よって、高精細なポリゴン描画処理をリアルタイムで実現することができる。【００８５】
（ポリゴンファン形式）
続いて、入力ポリゴンモデルがポリゴンファン形式で構成されている場合について説明する。【００８６】
図８は、入力ポリゴンモデルがポリゴンファン形式で構成されている場合の処理の流れを示す図である。ポリゴンファン形式は、上述のポリゴンストリップ形式と同様に、頂点を共有しながら連続でポリゴンを描画する形式である。開始頂点が全てのポリゴンで共有される点がポリゴンストリップ形式と異なる。同図に示すように、ポリゴンファン６０１のポリゴンＰｊ（ｊ＝０〜４）は、頂点Ｖ０、Ｖｊ＋１、Ｖｊ＋２の３点から構成される。また、ポリゴンファン６０１の頂点データはＶ０→Ｖ１→Ｖ２→Ｖ３→Ｖ４→Ｖ５→Ｖ６の順で指定される。なお、図８においては、ポリゴンＰ０及びＰ４が有効なポリゴンであるとする。【００８７】
タイムチャート６０２は、座標データのロードから頂点有効フラグの生成までの、処理の流れを示すタイムチャートである。以下では、タイムチャート６０２に沿ってポリゴンファン形式の処理の流れについて説明する。【００８８】
座標データロード部１０３は、上記ポリゴンストリップの処理と同様に、上記頂点データの指定順に頂点データのうち座標データＭｉ（ｉ＝０〜６）のロードを行い、座標変換部１０４へ出力する。座標変換部１０４は、座標データロード部１０３から受け取った頂点Ｖｉ（ｉ＝０〜６）の座標データについてそれぞれ座標変換を行う。これにより、変換済み座標データＤｉをポリゴン消去判定部１０５に出力する。ポリゴン消去判定部１０５は、入力された変換済み座標データＤｉを変換座標バッファ１１０に保持させる。【００８９】
ポリゴン消去判定部１０５は、ポリゴン消去判定をＰ０→Ｐ１→Ｐ２→Ｐ３→Ｐ４の順に行う。ポリゴン消去判定部１０５は、ポリゴンＰｊについてのポリゴン消去判定を行うときに、ポリゴンＰｊを構成する頂点Ｖ０、Ｖｊ、Ｖｊ＋１の変換済み座標データＤ０、Ｄｊ、Ｄｊ＋１が揃うまで、座標変換部１０４が生成した変換済み座標データを保持させる。変換済み座標データが揃ったときに変換済み座標データを用いてポリゴン消去判定を行い、ポリゴン描画有効フラグＦＰｊ（ポリゴンが有効であれば真、無効であれば偽）を生成する。【００９０】
頂点消去判定部１０６は、頂点消去判定をＶ０→Ｖ１→Ｖ２→Ｖ３→Ｖ４→Ｖ５→Ｖ６の順に行う。頂点消去判定部１０６は、開始頂点Ｖ０と、開始頂点Ｖ０を除く頂点Ｖｉ（ｉ＝１〜６）とについて、それぞれ異なる条件式を用いて頂点消去判定を行う。【００９１】
開始頂点Ｖ０の頂点消去判定では、いずれか１つのポリゴン描画有効フラグＦＰｊが真となった場合に、開始頂点Ｖ０は有効であると判定する。開始頂点Ｖ０が有効であるか否かを示す頂点有効フラグＦＶ０は、以下の式２に示す条件式に基づいて生成される。【００９２】
ＦＶ０＝（∃ｊ）（ＦＰｊ）    ・・・（式２）【００９３】
より具体的には、頂点有効フラグＦＶ０は、式３に示す論理和演算を行うことで算出される。【００９４】
ＦＶ０＝ＦＶ０‖ＦＰｊ    ・・・（式３）【００９５】
頂点消去判定部１０６は、ポリゴン描画有効フラグの論理和を中間結果フラグ（式３の右辺のＦＶ０）として、頂点消去判定バッファ１１１に保持させる。中間結果フラグが真となった時点で、開始頂点Ｖ０は有効な頂点データであると判定する。中間結果フラグが最後まで真にならなかった場合は、開始頂点Ｖ０は無効な頂点データであると判定する。【００９６】
開始頂点Ｖ０を除く頂点Ｖｉを含むポリゴンＰｉ−２及びＰｉ−１のポリゴン描画有効フラグＦＰｉ−２及びＦＰｉ−１（存在しないポリゴン番号のポリゴン描画有効フラグは偽として扱う）の論理和演算を行う。すなわち、開始頂点Ｖ０を除く頂点Ｖｉが有効であるか否かを示す頂点有効フラグＦＶｉは、以下の式４に基づいて生成される。【００９７】
ＦＶｉ＝ＦＰｉ‖ＦＰｉ−１    ・・・（式４）【００９８】
なお、頂点消去判定部１０６は、ポリゴン描画有効フラグＦＰｉ−２及びＦＰｉ−１が揃うまで、ポリゴン消去判定部１０５が生成したポリゴン描画有効フラグ又はその中間的な論理和を頂点消去判定バッファ１１１に保持させる。例えば、頂点Ｖ２については、頂点Ｖ２が含まれるポリゴンＰ０及びＰ１のうちＰ０についてポリゴン描画が有効であるため、有効な頂点データと判定する。一方、頂点Ｖ３については、頂点Ｖ３が含まれるポリゴンＰ１及びＰ２のいずれもポリゴン描画が無効であるため、無効な頂点データと判定する。【００９９】
形態データロード部１０７は、頂点消去判定部１０６により有効と判断された頂点Ｖ０、Ｖ１、Ｖ２、Ｖ５及びＶ６について、頂点消去判定の順に形態データのロードを行い、該当する頂点の変換済み座標データと合わせてポリゴン描画処理部１０８へ出力する。ポリゴン描画処理部１０８は、これらの頂点データを受け取ってポリゴン描画処理を行う。【０１００】
なお、以上の処理は、ポリゴンストリップ形式の場合と同様に、パイプライン形式で実行される。すなわち、図８のタイムチャート６０２で示すように、頂点Ｖ０から順に、座標データのロードを行い、ロードした座標データを変換することで変換済み座標データを生成する。そして、頂点Ｖ２に対応する変換済み座標データを生成して初めて、ポリゴン消去判定及び頂点消去判定が実行される。以降、座標データがロードされるたびに、座標変換、ポリゴン消去判定及び頂点消去判定が実行される。以下では、パイプライン形式で上述した処理が実行される様子を、本実施の形態の画像生成装置１００の、各処理部でのデータの流れに基づいて説明する。【０１０１】
図９は、ポリゴンファン形式に適応した画像生成装置の、各処理部でのデータの流れを示す図である。同図に示すように、メモリ２００上にポリゴンファンの座標データリスト７０１及び形態データリスト７０２が配置されているとする。さらに、メモリ２００は、ポリゴン描画処理部１０８が出力する出力画像７０３も保持する。【０１０２】
座標データロード部１０３は、メモリ２００上の座標データリスト７０１にアクセスして座標データ７０４を順次ロードして座標変換部１０４へ出力する。【０１０３】
座標変換部１０４は、座標データ７０４から変換済み座標データ７０５を計算してポリゴン消去判定部１０５へ出力する。【０１０４】
ポリゴン消去判定部１０５は、変換済み座標データ７０５を変換座標バッファ１１０へと格納する。変換座標バッファ１１０は、ポリゴンファン６０１の開始頂点Ｖ０の変換済み座標データ７０６と、開始頂点Ｖ０を除く頂点Ｖｉの変換済み座標データ７０７とを格納する。変換済み座標データ７０６は、ポリゴンファンの処理中は保持される。開始頂点以外の新しい変換済み座標データは、変換済み座標データ７０７として順次格納され、古い変換済み座標データから順に、不要となったら変換座標バッファ１１０から削除される。なお、変換座標バッファ１１０の変換済み座標データ７０７が保持される領域はＦＩＦＯ形式で制御される。【０１０５】
ポリゴン消去判定部１０５は、変換済み座標データ７０６及び７０７を用いてクリッピング判定及びカリング判定を実行することにより、ポリゴンが有効であるか否かを判定する。そして、判定結果に基づいて、ポリゴン描画有効フラグ７０８を生成して頂点消去判定部１０６へと出力する。【０１０６】
頂点消去判定部１０６は、ポリゴン描画有効フラグ７０８を頂点消去判定バッファ１１１へと格納する。頂点消去判定バッファ１１１は、ポリゴンファン開始頂点の中間結果フラグ７０９と、開始頂点以外の頂点消去判定に使用するポリゴン描画有効フラグ７１０とを格納する。頂点消去判定バッファ１１１は、ポリゴンファン開始頂点の中間結果フラグ７０９を、ポリゴンファンの処理中は保持する。ポリゴン描画有効フラグ７１０へ新しいポリゴン描画有効フラグを登録するとき、古いポリゴン描画有効フラグから順に削除する。なお、頂点消去判定バッファ１１１のポリゴン描画有効フラグ７１０が保持される領域はＦＩＦＯ形式で制御される。【０１０７】
頂点消去判定部１０６は、ポリゴンファン開始頂点の頂点消去判定を行う場合、ポリゴンファン描画開始時に中間結果フラグ７０９は偽に初期化する。以降、ポリゴン描画有効フラグ７０８を受け取るたびに、式３に基づいて中間結果フラグ７０９と新しいポリゴン描画有効フラグ７０８との論理和演算を行うことで、中間結果フラグ７０９を更新する。更新の結果、中間結果フラグ７０９が初めて偽から真に変わったときに、頂点有効フラグ７１１を真として生成して形態データロード部１０７へと出力する。【０１０８】
開始頂点以外の頂点消去判定を行う場合、ポリゴン描画有効フラグ７１０の論理和演算を行うことで、頂点有効フラグ７１１を生成して形態データロード部１０７へと出力する。【０１０９】
なお、頂点消去判定バッファ１１１は、ポリゴンファンの開始頂点の中間結果フラグと、判定対象となる頂点が含まれる全てのポリゴン（図９では２つ）のポリゴン描画有効フラグのみとを保持するように制御されている。これは、ポリゴンファン形式では、ポリゴンストリップ形式と同様に頂点の指定順にポリゴンが描画され、かつ、頂点消去判定バッファ１１１のポリゴン描画有効フラグが保持される領域がＦＩＦＯ形式で制御されるためである。したがって、頂点消去判定部１０６は、常に頂点消去判定バッファ１１１に格納されるポリゴン描画有効フラグ７１０（図９では２つ）の論理和演算を行うことで、頂点有効フラグを生成することができる。【０１１０】
形態データロード部１０７は、頂点有効フラグ７１１を参照して有効な頂点であるときのみ、メモリ２００上の形態データリスト７０２にアクセスして該当頂点の形態データをロードする。さらに、該当頂点の変換済み座標データ７１２を変換座標バッファ１１０から受け取り、形態データと合わせて頂点データ７１３としてポリゴン描画処理部１０８へ出力する。【０１１１】
ポリゴン描画処理部１０８は、頂点データ７１３を用いてポリゴン描画処理を行い、メモリ２００上の出力画像７０３を生成する。【０１１２】
以上のように、開始頂点を除いた頂点に対応する変換済み座標データ７０７及びポリゴン描画有効フラグ７１０を、ＦＩＦＯ形式で制御したバッファに格納させることで、座標データのロード処理と、座標変換処理と、ポリゴン消去判定処理と、頂点消去判定処理と、形態データのロード処理と、ポリゴン描画処理とをパイプライン形式で制御することができる。【０１１３】
これにより、メモリ２００へのアクセス量を大幅に低減することができ、メモリバンド幅を圧迫することがなくなる。よって、高精細なポリゴン描画処理をリアルタイムで実現することができる。【０１１４】
（ポリゴンメッシュ形式）
図１０は、入力ポリゴンモデルがポリゴンメッシュ形式で構成されている場合の処理の流れを示す図である。ポリゴンメッシュ形式は、内部の多くのポリゴンで頂点の共有が行われるものの、上記のポリゴンストリップ及びポリゴンファンとは異なり、ポリゴン単位で頂点の指定が行われる形式である。【０１１５】
同図に示すように、ポリゴンメッシュ８０１の頂点データは、例えば、Ｐ０（Ｖ０、Ｖ１、Ｖ２）→Ｐ１（Ｖ２、Ｖ１、Ｖ３）→Ｐ２（Ｖ２、Ｖ３、Ｖ４）→Ｐ３（Ｖ４、Ｖ３、Ｖ５）→Ｐ４（Ｖ４、Ｖ５、Ｖ６）→Ｐ５（Ｖ７、Ｖ０、Ｖ２）→Ｐ６（Ｖ７、Ｖ２、Ｖ８）→Ｐ７（Ｖ８、Ｖ２、Ｖ４）→Ｐ８（Ｖ８、Ｖ４、Ｖ９）→Ｐ９（Ｖ９、Ｖ４、Ｖ６）の順で指定される（ポリゴンメッシュは自由度の高い形式であり必ずしもこの順番で指定されるとは限らない）。なお、図１０に示す例においては、ポリゴンＰ０、Ｐ１、Ｐ５、Ｐ６、Ｐ７及びＰ８が有効なポリゴンであり、ポリゴンＰ２、Ｐ３、Ｐ４及びＰ９が無効なポリゴンであるとする。【０１１６】
タイムチャート８０２は、座標データのロードから頂点有効フラグの生成（頂点判定処理）までの処理の流れを示すタイムチャートである。以下では、タイムチャート８０２に沿ってポリゴンメッシュ形式の処理の流れについて説明する。【０１１７】
座標データロード部１０３は、頂点データの指定順に、頂点データのうち座標データＭｉ（ｉ＝０〜９）のロードを行い、座標変換部１０４へと渡す。ここで、ポリゴンメッシュ上の同じ頂点の座標データを重複してロードするのを防ぐため、変換座標バッファ１１０で変換済み座標データが保持されている頂点についてはロードをしない。【０１１８】
座標変換部１０４は、座標データロード部１０３から受け取った頂点Ｖｉの座標データについてそれぞれ座標変換を行い、変換済み座標データＤｉを座標データの入力順に生成する。【０１１９】
ポリゴン消去判定部１０５は、入力された変換済み座標データＤｉを変換座標バッファ１１０に保持させる。さらに、ポリゴン消去判定をＰ０→Ｐ１→Ｐ２→Ｐ３→Ｐ４→Ｐ５→Ｐ６→Ｐ７→Ｐ８→Ｐ９の順に行う。ポリゴン消去判定部１０５は、ポリゴンＰｊ（ｊ＝０〜９）についてのポリゴン消去判定を行うときに、ポリゴンＰｊを構成する頂点Ｖｋ、Ｖｌ、Ｖｍ（ｋ、ｌ、ｍ＝０〜９）の変換済み座標データＤｋ、Ｄｌ、Ｄｍが揃うまで、座標変換部１０４が生成した変換済み座標データを保持させる。変換済み座標データが揃ったときに変換済み座標データを用いてポリゴン消去判定を行い、ポリゴン描画有効フラグＦＰｊ（ポリゴンが有効であれば真、無効であれば偽）を生成する。【０１２０】
ここで、ポリゴンメッシュ形式の場合は同じ頂点が別のポリゴンと共有することが多いため、上記のポリゴンＰｊのポリゴン消去判定後も、近傍のポリゴン消去判定を行っている期間（一例として図１０のタイムチャート８０２に示すポリゴン描画有効フラグＦＰｊを求めている期間）は、変換済み座標データＤｋ、Ｄｌ、Ｄｍを保持しておく。座標データロード部１０３は、変換済み座標データが保持されている頂点の座標データをロードせず、ポリゴン消去判定部１０５は、保持されている変換済み座標データを再度ポリゴン消去判定に用いる。【０１２１】
例えば、ポリゴンＰ８についてのポリゴン消去判定を行うときは、ポリゴンＰ８を構成する頂点Ｖ８、Ｖ４、Ｖ９のうち、座標データロード部１０３は、頂点Ｖ９の座標データＭ９をロードし、座標変換部１０４は変換済み座標データＤ９を生成する。これに対して、頂点Ｖ８、Ｖ４については変換済み座標データＤ８、Ｄ４がすでに変換座標バッファ１１０に保持されているので、座標データロード部１０３は、頂点Ｖ８、Ｖ４の座標データをロードせず、座標変換部１０４は変換済み座標データＤ８、Ｄ４の生成を行わない。ポリゴン消去判定部１０５は、新たに生成された変換済み座標データＤ９と、すでに保持されている変換済み座標データＤ８、Ｄ４とを用いてポリゴン消去判定を行う。【０１２２】
頂点消去判定部１０６は、ポリゴン描画有効フラグＦＰｊを用いて、頂点Ｖｉについて頂点消去判定を行う。すなわち、以下の式５に示すように、頂点Ｖｉが含まれる、いずれかのポリゴンのポリゴン描画有効フラグＦＰｊが真となれば、頂点Ｖｉの頂点有効フラグＦＶｉも真とする。【０１２３】
ＦＶｉ＝（∃ｊ）（ＦＰｊ＆（Ｖｉ∈Ｐｊ））    ・・・（式５）【０１２４】
具体的には、頂点消去判定部１０６は、頂点Ｖｉ（ｉ＝０〜９）についての頂点消去判定を行うとき、はじめに頂点有効フラグＦＶｉを偽に初期化しておく。頂点消去判定部１０６は、ポリゴン消去判定部１０５が生成したポリゴン描画有効フラグＦＰｊをＰ０→Ｐ１→Ｐ２→Ｐ３→Ｐ４→Ｐ５→Ｐ６→Ｐ７→Ｐ８→Ｐ９の順に受け取り、それぞれポリゴンＰｊ（ｊ＝０〜９）を構成する頂点Ｖｋ、Ｖｌ、Ｖｍ（ｋ、ｌ、ｍ＝０〜９）の中間結果フラグＦＶｋ、ＦＶｌ、ＦＶｍとの論理和演算を行い、中間結果フラグＦＶｋ、ＦＶｌ、ＦＶｍを更新する（更新は頂点が指定された順番、すなわちＦＶｋ→ＦＶｌ→ＦＶｍの順に行う）。すなわち、中間結果フラグＦＶｋ（ＦＶｌ、ＦＶｍも同様）は、ポリゴン描画有効フラグＦＰｊを受け取るたびに、以下の式６に基づいて算出される。【０１２５】
ＦＶｋ＝ＦＶｋ‖（ＦＰｊ＆（Ｖｋ∈Ｐｊ））    ・・・（式６）【０１２６】
例えば、ポリゴン消去判定部１０５がポリゴンＰ８のポリゴン描画有効フラグＦＰ８を生成した場合について説明する。頂点消去判定部１０６は、ポリゴンＰ８を構成する頂点Ｖ８、Ｖ４、Ｖ９について、それぞれ中間結果フラグＦＶ８、ＦＶ４、ＦＶ９とポリゴン描画有効フラグＦＰ８との論理和演算を行い、中間結果フラグＦＶ８、ＦＶ４、ＦＶ９を更新する。中間結果フラグＦＶｉが偽から真となった時点で、その頂点は有効な頂点データであると判定する。図１０の例では、Ｖ０→Ｖ１→Ｖ２→Ｖ３→Ｖ７→Ｖ８→Ｖ４→Ｖ９の順に有効な頂点データであると判定される。上記のポリゴン消去判定結果による中間結果フラグＦＶｉが最後まで真にならなかった頂点Ｖ５及びＶ６は、無効な頂点データであると判定される。【０１２７】
形態データロード部１０７は、頂点消去判定部１０６により有効と判断された頂点Ｖ０、Ｖ１、Ｖ２、Ｖ３、Ｖ７、Ｖ８、Ｖ４、Ｖ９について頂点消去判定の順に形態データのロードを行い、該当する頂点の変換済み座標データと合わせてポリゴン描画処理部１０８へ出力する。ポリゴン描画処理部１０８は、これらの頂点データを受け取ってポリゴン描画処理を行う。【０１２８】
以上のように、入力ポリゴンモデルがポリゴンメッシュ形式で表現される場合であっても、ポリゴン描画処理に必要な場合にのみ、形態データがロードされる。これにより、全てのデータをロードする場合に比べてメモリアクセスを低減することができる。【０１２９】
以下では、上述した処理が実行される様子を、本実施の形態の画像生成装置１００の、各処理部でのデータの流れに基づいて説明する。【０１３０】
図１１は、ポリゴンメッシュ形式に適応した画像生成装置の、各処理部でのデータの流れを示す図である。同図に示すように、メモリ２００上にポリゴンメッシュの座標データリスト９０１及び形態データリスト９０２が配置されているとする。さらに、メモリ２００は、ポリゴン描画処理部１０８が出力する出力画像９０３も保持する。【０１３１】
座標データロード部１０３は、メモリ２００上の座標データリスト９０１にアクセスして座標データ９０４をロードして座標変換部１０４へ出力する。ここで、ポリゴンメッシュ上の同じ頂点の座標データを重複してロードしないよう、変換座標バッファ１１０で変換済み座標データが保持されている頂点についてはロードをしない。【０１３２】
座標変換部１０４は、座標データ９０４から変換済み座標データ９０５を計算してポリゴン消去判定部１０５へ出力する。【０１３３】
ポリゴン消去判定部１０５は、変換済み座標データ９０５を変換座標バッファ１１０へと格納する。変換座標バッファ１１０は、登録可能な数だけ変換済み座標データ９０６を登録する。登録可能な数に達したときに新たな変換済み座標データを登録する場合、最も参照が古い頂点の変換済み座標データを変換座標バッファ１１０から削除する。ポリゴン消去判定部１０５は、変換済み座標データ９０６を用いてポリゴン描画有効フラグ９０７を生成して頂点消去判定部１０６へと出力する。【０１３４】
頂点消去判定部１０６は、ポリゴン描画有効フラグ９０７から生成される中間結果フラグを頂点消去判定バッファ１１１へと格納する。頂点消去判定バッファ１１１は、登録可能な数（変換座標バッファ１１０への変換済み座標データ数と同数）だけ中間結果フラグ９０８を登録する。登録可能な数に達したときに新たな中間結果フラグを登録する場合、最も参照が古い頂点の中間結果フラグを頂点消去判定バッファ１１１から削除する。頂点消去判定部１０６は、ポリゴンメッシュ描画開始時に中間結果フラグ９０８は全て偽に初期化される。以降、新しいポリゴン描画有効フラグ９０７を受け取るたびに、式６に基づいて該当ポリゴンに含まれる頂点の中間結果フラグ９０８との論理和演算を行うことで、中間結果フラグ９０８を更新する。更新結果が初めて偽から真に変わったときに、該当頂点が真であることを示す頂点有効フラグ９０９を生成して形態データロード部１０７へと出力する。【０１３５】
形態データロード部１０７は、頂点有効フラグ９０９を参照して有効な頂点であるときのみ、メモリ２００上の形態データリスト９０２にアクセスして該当頂点の形態データをロードする。該当頂点の変換済み座標データ９１０を変換座標バッファ１１０から受け取り、合わせて頂点データ９１１としてポリゴン描画処理部１０８へ出力する。【０１３６】
ポリゴン描画処理部１０８は、頂点データ９１１を用いてポリゴン描画処理を行い、メモリ２００上の出力画像９０３を生成する。【０１３７】
以上のように、入力ポリゴンモデルがポリゴンメッシュ形式で表現される場合であっても、ポリゴン描画処理に必要な場合にのみ、形態データがロードされる。これにより、全てのデータをロードする場合に比べてメモリアクセスを低減することができる。【０１３８】
本実施の形態の画像生成装置及び画像生成方法によれば、入力ポリゴンモデルの頂点データのうち座標データ以外の形態データについては、頂点消去判定で頂点が有効と判断されたものについてのみ行われる。これにより、メモリからグラフィックス処理ユニットへの、入力ポリゴンモデルの頂点データのロードに関するメモリアクセス量を大幅に低減することができ、低メモリバンド幅の情報処理装置で入力ポリゴン数の多い高精細なポリゴン描画処理をリアルタイムで行うことができる。【０１３９】
以上、本発明の画像生成装置及び画像生成方法について、実施の形態に基づいて説明したが、本発明は、この実施の形態に限定されるものではない。本発明の趣旨を逸脱しない限り、当業者が思いつく各種変形を実施の形態に施したものも本発明の範囲内に含まれる。【０１４０】
例えば、入力ポリゴンモデルの表現形式についても、上記で示した形式の混在形式や四角形ストリップやラインストリップなど他の表現形式が含まれてもよい。【０１４１】
なお、図１１のデータフローは、入力ポリゴンモデルがポリゴンメッシュ形式の場合のデータフローとして説明したが、ポリゴンストリップ形式やポリゴンファン形式、もしくはそれらの混在形式の場合でも同様のデータフローで処理をすることができる。【０１４２】
また、ポリゴン消去判定部１０５は、クリッピング判定及びカリング判定を用いているが、描画オプションによってどちらか一方しか用いなくともよい。【０１４３】
また、クリッピング判定として、３次元空間内の任意の平面を境界とした消去判定が含まれてもよいし、ディスプレイ面３０３上の任意の領域を境界とした消去判定が含まれてもよい。【０１４４】
また、カリング判定として、ディスプレイ面３０３に投影したときに１ドットに満たないポリゴンの消去判定や、ビューボリューム３０２内の他のポリゴン描画によって視点３０１から全く見えなくなるポリゴンの消去判定が含まれてもよい。【０１４５】
また、本実施の形態では、頂点消去判定部１０６は、判定対象の頂点Ｖｉが含まれるポリゴンの、ポリゴン描画有効フラグＦＰｊの論理和をとって頂点有効フラグＦＶｉを生成する方法を用いている。この方法には、ポリゴン消去判定部１０５から判定対象の頂点Ｖｉが含まれるポリゴンの、ポリゴン描画有効フラグＦＰｊが全て得られてから、頂点有効フラグＦＶｉを生成する方法と、上記ポリゴン描画有効フラグＦＰｊを逐次頂点有効フラグＦＶｉの中間結果との論理和をとって更新し、論理和が偽から真にとなったときに頂点有効フラグＦＶｉを真として生成する方法がありうる。本実施の形態では、ポリゴンストリップ形式の頂点及びポリゴンファン形式の開始頂点以外頂点が前者の方法、ポリゴンファンの開始頂点及び上記ポリゴンメッシュの頂点が後者の方法に該当するが、入力ポリゴンモデルの表現形式に関わらずそのどちらを用いてもよい。【０１４６】
また、ポリゴンメッシュ形式では、中間結果フラグが偽から真になった場合は、以降、頂点消去判定部１０６は、真である中間結果フラグを用いた論理和演算を行うことを停止してもよい。例えば、頂点消去判定バッファ１１１から、真となった中間結果フラグを削除することで、削除された中間結果フラグとポリゴン描画有効フラグとの論理和演算を行うことを停止することができる。【０１４７】
例えば、図２の画像生成装置１００に含まれる座標データロード部１０３、座標変換部１０４などの各ブロックは一部又は全部を並列化してもよいし、複数のブロックを１つのブロックに統合してもよい。【０１４８】
また、本発明は、図２の画像生成装置１００を含む情報処理装置として実現することができる。【０１４９】
図１２は、図２の画像生成装置を含む情報処理装置の構成を示すブロック図である。同図に示す情報処理装置１０００は、集積回路１００１と、メモリ１００８と、ディスプレイ１００９とを備える。【０１５０】
集積回路１００１は、例えば、システムＬＳＩなどであり、ＣＰＵ１００２と、グラフィックス処理ユニット１００３（図２の画像生成装置）と、メモリコントローラ１００４と、ディスプレイコントローラ１００５と、ＣＰＵバス１００６と、メモリバス１００７とを備える。【０１５１】
ＣＰＵ１００２は、描画命令リスト２０２及び頂点データリスト２０３を、メモリバス１００７とメモリコントローラ１００４とを介してメモリ１００８に格納する。また、ＣＰＵバス１００６を介して描画の指示をグラフィックス処理ユニット１００３へ伝える。【０１５２】
グラフィックス処理ユニット１００３は、メモリバス１００７とメモリコントローラ１００４とを介してメモリ１００８から描画命令リスト２０２及び頂点データリスト２０３にアクセスして、上述した画像生成処理を行う。生成した画像は、メモリバス１００７とメモリコントローラ１００４とを介してメモリ１００８に格納する。メモリ１００８に格納された生成画像は、ディスプレイコントローラ１００５を介してディスプレイ１００９へと出力される。【０１５３】
なお、ＣＰＵ１００２による、頂点データリスト２０３のメモリ１００８への格納については、頂点データリスト２０３を、必ずロードされる座標データリスト２０５と、頂点消去判定結果によってはロードされない形態データリスト２０６とへ分割してそれぞれ別のメモリ領域に格納してもよい。これにより、メモリバス１００７およびメモリコントローラ１００４がバーストメモリアクセスによりメモリ１００８上の頂点データリスト２０３をロードする場合に、座標データとともに不要と判定された形態データまでロードしてしまうことを防ぐことができ、メモリアクセス効率を高めることができる。【０１５４】
また、図１１の集積回路１００１のＣＰＵ１００２、グラフィックス処理ユニット１００３などの各機能ブロックは個別に集積回路化してもよいし、一部又は全部を含むように１つの集積回路としてもよい。集積回路１００１には、ＡＶ（Ａｕｄｉｏ  Ｖｉｓｕａｌ）処理ユニットやストリーミング処理ユニットなど他の機能ブロックが含んでいてもよい。メモリ１００８は、集積回路１００１の内部に搭載してもよいし、集積回路１００１の内部、外部を問わず複数個搭載してもよい。【０１５５】
また、本実施の形態では、画像生成装置を集積回路として実施した例を示したが、汎用プロセッサー上のプログラムによって実現してもよいし、製造後にハードウェア構成を変更することが可能なＦＰＧＡ（Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）や集積回路内部の回路セルの接続や設定を再構成可能なリコンフィギュラブル・プロセッサーを利用して実現してもよい。【０１５６】
また、本発明は、上記のプログラムを記録したコンピュータ読み取り可能なＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ−Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）などの記録媒体として実現したり、そのプログラムを示す情報、データ又は信号として実現したりすることもできる。そして、それらプログラム、情報、データ及び信号は、インターネット等の通信ネットワークを介して配信してもよい。
【産業上の利用可能性】
【０１５７】
本発明の画像生成方法及び画像生成装置は、グラフィックス描画機能を搭載する様々な電子機器、例えば、携帯電話、ＰＤＡ（Ｐｅｒｓｏｎａｌ  Ｄｉｇｉｔａｌ  Ａｓｓｉｓｔａｎｔ）、デジタルテレビ、カーナビゲーションシステム、家庭用ゲーム機、パーソナルコンピュータ等において用いることができる。
【図１】
2008126392.tif 000003
【図２】
2008126392.tif 000004
【図３】
2008126392.tif 000005
【図４】
2008126392.tif 000006
【図５】
2008126392.tif 000007
【図６】
2008126392.tif 000008
【図７】
2008126392.tif 000009
【図８】
2008126392.tif 000010
【図９】
2008126392.tif 000011
【図１０】
2008126392.tif 000012
【図１１】
2008126392.tif 000013
【図１２】
2008126392.tif 000014
【手続補正書】
【提出日】平成21年10月9日(2009.10.9)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータグラフィックス技術に関し、コンピュータグラフィックス画像を生成する画像生成装置及び画像生成方法に関するものである。
【背景技術】
【０００２】
コンピュータグラフィックス（ＣＧ：Ｃｏｍｐｕｔｅｒ  Ｇｒａｐｈｉｃｓ）画像を生成する処理は計算負荷が大きいため、リアルタイムで画像生成処理を行う情報処理装置では、中央演算処理装置（ＣＰＵ：Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）とは別に画像生成処理を専用で行う画像生成装置（グラフィックス処理ユニット）を備えている。
【０００３】
図１は、従来の画像生成装置が行う画像生成方法の、一般的な処理を示すフローチャートである。
【０００４】
従来の一般的な画像生成装置は、まず、入力ポリゴンモデルの頂点データを情報記憶装置（メモリ）からロードする（Ｓ１０１）。なお、頂点データは、頂点の位置を示す座標データと、座標データ以外のデータである形態データとからなる。次に、頂点データのうち座標データについてワールド座標への座標変換処理を行う（Ｓ１０２）。さらに、ワールド座標からディスプレイ座標への座標変換処理を行う（Ｓ１０３）。そして、変換座標データを用いて、ロードした頂点データから構成されるポリゴン毎に、ポリゴンが可視空間に入っているか否かを判定するクリッピング判定あるいはポリゴンが視点から見て表示すべき面を向いているか否かを判定するカリング判定により、ポリゴン描画が有効かどうかの判定を行う（Ｓ１０４）。有効であると判定されたポリゴンについてのみ、ロードした頂点データを用いてポリゴン描画処理を行う（Ｓ１０５）。以上の処理が全てのポリゴンについて終了したかを判定し（Ｓ１０６）、終了していない場合（Ｓ１０６で「継続」）、各処理（Ｓ１０１〜Ｓ１０５）が繰り返される。全てのポリゴンについて終了した場合（Ｓ１０６で「完了」）、画像生成装置は描画された画像を出力する。
【０００５】
以上のような画像生成装置の例として、特許文献１及び特許文献２に開示されている技術がある。
【０００６】
特許文献１は、シーンのカットなどが予め決まっている非インタラクティブ用途向けの技術を示している。特許文献１に示される技術では、描画に不要なデータを予め削減する。これにより、データをロードするためのメモリアクセス量を削減することができる。
【０００７】
特許文献２は、入力ポリゴンデータのロード専用のデータキャッシュを備える技術を示している。特許文献２に示す技術は、一度ロードした頂点データを専用のデータキャッシュに記憶させておくことで、同じ頂点データを参照する場合は再ロードしない。これにより、メモリアクセス量を削減することができる。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００１−２０９３６９号公報
【特許文献２】特開２００１−１９５６０３号公報
【非特許文献】
【０００９】
【非特許文献１】コンピュータグラフィックス  ＣＧ−ＡＲＴＳ協会出版（第３４頁、第１００頁）
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、上記従来の画像生成装置では、入力ポリゴンモデルの頂点データを保持するメモリからグラフィックス処理ユニットへのメモリアクセス量が増大し、単位時間あたりの限界メモリアクセスデータ量であるメモリバンド幅を圧迫するという課題がある。
【００１１】
具体的には、上記従来の画像生成装置では、入力ポリゴンモデルの頂点について座標データ及び形態データをメモリからグラフィックス処理ユニットへロードする。その後にクリッピング判定及びカリング判定を行っているため、ポリゴンの描画が有効であるかどうかに関わらず入力ポリゴンモデルの全ての頂点データをロードする必要がある。これにより、メモリからグラフィックス処理ユニットへのメモリアクセス量が増大し、メモリバンド幅を圧迫する。
【００１２】
なお、特許文献１に示す技術では、ロードする頂点データの量を削減することができるため、非インタラクティブ用途に限定すれば課題を解決することが可能である。しかしながら、特許文献１には、ユーザの操作が加わるインタラクティブ用途のＣＧ処理に用いることができないという課題がある。
【００１３】
また、特許文献２に示す技術では、同じ頂点データを参照する場合は再ロードしないことでメモリアクセス量を低減することができる。しかしながら、少なくとも１回は、ポリゴン描画が有効であるかどうかに関わらず頂点データをロードしてしまうため、上記課題の解決方法としては不十分である。
【００１４】
以上のように、上記の課題を解決するための方法は存在しておらず、例えば、低メモリバンド幅の情報処理装置で入力ポリゴン数の多い高精細なポリゴン描画処理をリアルタイムで行うことは非常に困難であった。
【００１５】
そこで、本発明は、インタラクティブ用途のＣＧ処理にも適用でき、かつ、入力ポリゴンモデルの頂点データのロードに関するメモリアクセス量を低減することができる、画像生成装置及び画像生成方法を提供することを目的とする。
【課題を解決するための手段】
【００１６】
上記の課題を解決するために、本発明の画像生成装置は、ポリゴンを描画することでコンピュータグラフィックス画像を生成する画像生成装置であって、ポリゴンを構成する頂点の情報を示す頂点データのうち、前記頂点の位置を示す座標データをロードする座標データロード手段と、前記座標データロード手段によりロードされた前記座標データを異なる座標系に変換する座標変換手段と、前記座標変換手段により変換されて得られる変換済み座標データを用いて前記ポリゴンが描画の対象であるか否かを判定することで、前記ポリゴンを構成する頂点が有効であるか否かを判定する判定手段と、前記判定手段により有効と判定された頂点のみに対応する前記頂点データのうち前記座標データ以外の情報を示す形態データをロードする形態データロード手段と、前記形態データロード手段によりロードされた形態データと前記変換済み座標データとを用いてポリゴンを描画するポリゴン描画手段とを備える。
【００１７】
これにより、頂点データのうち従来は全ての形態データをロードしていたのに対して、ポリゴン描画に必要な形態データのみをロードすることができる。また、ポリゴン描画が実行されるか否かをロードした座標データから検出することができる。よって、非インタラクティブ用途だけでなく、インタラクティブ用途のＣＧ処理にも適用でき、かつ、入力ポリゴンモデルの頂点データのロードに関するメモリアクセス量を低減することができる。
【００１８】
また、前記座標変換手段による座標変換と、前記判定手段によるポリゴン判定及び頂点判定とは、前記座標データが１つロードされるたびにパイプラインで処理されてもよい。
【００１９】
これにより、低メモリバンド幅の情報処理装置で、入力ポリゴン数の多い高精細なポリゴン描画処理をリアルタイムで行うことができる。
【００２０】
また、前記判定手段は、前記変換済み座標データを用いて前記ポリゴンが描画の対象であるか否かを判定し、前記ポリゴンが描画の対象であるか否かを示すポリゴン有効フラグを出力するポリゴン判定部と、共有の頂点を含む複数のポリゴンの、ポリゴン有効フラグの論理和演算を行うことで、前記頂点が有効であるか否かを判定する頂点判定部とを有してもよい。
【００２１】
また、前記画像生成装置は、さらに、頂点が無効であることを示すように予め設定された中間結果フラグを保持する第１バッファを備え、前記判定手段は、前記変換済み座標データを用いて前記ポリゴンが描画の対象であるか否かを判定し、前記ポリゴンが描画の対象であるか否かを示すポリゴン有効フラグを出力するポリゴン判定部と、前記ポリゴン有効フラグと、前記ポリゴン有効フラグに対応するポリゴンを構成する頂点の前記中間結果フラグとの論理和演算を行い、前記第１バッファに保持される中間結果フラグを更新することで、前記頂点が有効であるか否かを判定する頂点判定部とを有してもよい。
【００２２】
これにより、論理和演算を実行するだけで頂点が有効であるか否かを判定することができるので、頂点判定に関わる処理量を低減することができる。
【００２３】
また、前記頂点判定部は、前記中間結果フラグと前記ポリゴン有効フラグとの論理和演算を行うことで、前記中間結果フラグの値が変更した場合に、頂点が有効であることを示す頂点有効フラグを出力し、前記形態データロード手段は、前記頂点有効フラグを受け取ったときに、前記頂点有効フラグに対応する前記形態データをロードしてもよい。
【００２４】
これにより、頂点が有効であると判定されるたびに、当該頂点に対応する形態データをロードすることができるので、メモリバンド幅を圧迫することを低減することができる。
【００２５】
また、前記頂点判定部は、さらに、前記中間結果フラグの値が変更した場合、当該中間結果フラグを用いる論理和演算を行うことを停止してもよい。
【００２６】
これにより、一度、有効であると判定された頂点に対して、再度、頂点判定が行われることを防ぐことができ、処理量を低減することができる。
【００２７】
また、前記座標データロード手段は、前記複数の座標データのみを格納する領域から前記座標データをロードし、前記形態データロード手段は、前記複数の形態データのみを格納する領域から前記形態データをロードしてもよい。
【００２８】
これにより、必ず全てをロードしなければならない座標データと、必要に応じてロードする形態データとを分離して格納しておくことで、一度のメモリアクセスでメモリアドレスが連続する領域のデータを一括して多くロードするバーストメモリアクセスによって頂点データをロードする場合に、座標データとともに不要と判定された形態データまでロードしてしまうことを防ぐことができ、メモリアクセス効率を高めることができる。
【００２９】
また、具体的には、前記座標変換手段は、前記座標データをワールド座標系及びディスプレイ座標系に変換し、前記判定手段は、前記ワールド座標系に変換された変換済み座標データを用いて実行されるクリッピング判定、及び、前記ディスプレイ座標系に変換された変換済み座標データを用いて実行されるカリング判定の少なくとも１つを行うことで、前記ポリゴンが有効であるか否かを判定し、有効であると判定されたポリゴンを構成する頂点を有効であると判定してもよい。
【００３０】
また、本発明は、画像生成装置として実現することができるだけではなく、画像生成装置を構成する各処理手段をステップとする画像生成方法として実現することもできる。
【００３１】
さらに、本発明は、集積回路としても実現することができ、ポリゴンを描画することでコンピュータグラフィックス画像を生成する集積回路であって、ポリゴンを構成する頂点の情報を示す頂点データのうち、前記頂点の位置を示す座標データをロードする座標データロード手段と、前記座標データロード手段によりロードされた前記座標データを異なる座標系に変換する座標変換手段と、前記座標変換手段により変換されて得られる変換済み座標データを用いて前記ポリゴンが描画の対象であるか否かを判定することで、前記ポリゴンを構成する頂点が有効であるか否かを判定する判定手段と、前記判定手段により有効と判定された頂点のみに対応する前記頂点データのうち前記座標データ以外の情報を示す形態データをロードする形態データロード手段と、前記形態データロード手段によりロードされた形態データと前記変換済み座標データとを用いてポリゴンを描画するポリゴン描画手段とを備える。
【発明の効果】
【００３２】
本発明によれば、メモリからグラフィックス処理ユニットへの、入力ポリゴンモデルの頂点データのロードに関するメモリアクセス量を大幅に低減することができる。これにより例えば、低メモリバンド幅の情報処理装置で入力ポリゴン数の多い高精細なポリゴン描画処理をリアルタイムで行うことができる。
【図面の簡単な説明】
【００３３】
【図１】図１は、従来の画像生成装置の動作を示すフローチャートである。
【図２】図２は、本実施の形態の画像生成装置の構成を示すブロック図である。
【図３】図３は、本実施の形態の画像生成装置への入力データを示す図である。
【図４】図４は、ポリゴン消去判定を示す図である。
【図５】図５は、本実施の形態の画像生成装置の動作を示すフローチャートである。
【図６】図６は、ポリゴンストリップ形式の処理の流れを示す図である。
【図７】図７は、ポリゴンストリップ形式に適応した画像生成装置の各処理部でのデータの流れを示す図である。
【図８】図８は、ポリゴンファン形式の処理の流れを示す図である。
【図９】図９は、ポリゴンファン形式に適応した画像生成装置の各処理部でのデータの流れを示す図である。
【図１０】図１０は、ポリゴンメッシュ形式の処理の流れを示す図である。
【図１１】図１１は、ポリゴンメッシュ形式に適応した画像生成装置の各処理部でのデータの流れを示す図である。
【図１２】図１２は、本実施の形態の画像生成装置を備える情報処理装置の構成を示すブロック図である。
【発明を実施するための形態】
【００３４】
以下、本発明の実施の形態について、図面を参照しながら説明する。
【００３５】
本実施の形態の画像生成装置は、頂点がポリゴン描画に必要とされるか否かを判定し、必要と判定された頂点のみに対応する形態データをロードし、ロードしたデータを用いてポリゴンを描画することでコンピュータグラフィックス画像を生成する装置である。
【００３６】
図２は、本実施の形態の画像生成装置の構成を示すブロック図である。同図の画像生成装置１００は、ポリゴン描画に関する入力データ２０１を保持するメモリ２００から必要なデータを読み出すことにより、ポリゴン描画を実行する装置である。まず、メモリ２００が格納する入力データ２０１について説明する。
【００３７】
図３は、本実施の形態の画像生成装置への入力データを示す図である。同図に示すように、入力データ２０１は、描画命令リスト２０２と、入力ポリゴンモデルの頂点データリスト２０３とで構成される。
【００３８】
描画命令リスト２０２は、ポリゴン描画命令に関する様々な情報を示す描画命令２０４を含む。図３に示すように、描画命令２０４は、入力ポリゴンの表現形式（ポリゴンストリップ、ポリゴンファン及びポリゴンメッシュなど）、各パラメータのロード設定（各種データのアドレス設定）、及び、描画オプションなどを示す。
【００３９】
頂点データリスト２０３は、入力ポリゴンモデルの頂点データのリストであり、座標データリスト２０５と形態データリスト２０６とで構成される。なお、頂点データとは、ポリゴンを構成する頂点の情報を示すデータであり、座標データと形態データとからなる。
【００４０】
図３に示すように、頂点データリスト２０３は、座標データリスト２０５と形態データリスト２０６とへ分割してそれぞれ別のメモリ領域に格納してもよい。これにより、一度のメモリアクセスでメモリアドレスが連続する領域のデータを一括して多くロードするバーストメモリアクセスによって頂点データリスト２０３をロードする場合に、座標データとともに不要と判定された形態データまでロードしてしまうことを防ぐことができ、メモリアクセス効率を高めることができる。
【００４１】
座標データリスト２０５は、入力ポリゴンモデルの各頂点の位置を示す座標データ２０７のリストである。
【００４２】
形態データリスト２０６は、各頂点の座標データ以外の情報を示す形態データ２０８のリストである。図３には、一例として、各頂点の法線データ、カラーデータ、及び、テクスチャ座標データを示す。
【００４３】
図２の画像生成装置１００は、ホストインターフェース１０１と、制御部１０２と、座標データロード部１０３と、座標変換部１０４と、ポリゴン消去判定部１０５と、頂点消去判定部１０６と、形態データロード部１０７と、ポリゴン描画処理部１０８と、メモリインターフェース１０９と、変換座標バッファ１１０と、頂点消去判定バッファ１１１とを備える。
【００４４】
ホストインターフェース１０１は、ＣＰＵから入力される描画開始の指示を制御部１０２へと伝える。
【００４５】
制御部１０２は、描画開始の指示を受け取るとメモリバスを介してメモリインターフェース１０９から描画命令リスト２０２をロードして、描画命令２０４を座標データロード部１０３及び形態データロード部１０７に伝える。
【００４６】
座標データロード部１０３は、描画命令２０４に従って頂点データリスト２０３のうち座標データリスト２０５にアクセスし、頂点毎の座標データ２０７をロードして座標変換部１０４へ出力する。
【００４７】
座標変換部１０４は、入力された座標データ２０７に対して座標変換処理を行い、変換済み座標データをポリゴン消去判定部１０５へ出力する。座標変換処理とは、座標データ２０７をワールド座標及びディスプレイ座標に変換することである。
【００４８】
ポリゴン消去判定部１０５は、変換済み座標データを用いてポリゴンが描画の対象であるか否か、すなわち、ポリゴン描画が有効かどうかを示すフラグ（以下、ポリゴン描画有効フラグ）を生成する。具体的には、まず、ポリゴン消去判定部１０５は、変換済み座標データを変換座標バッファ１１０へ格納する。これは、ポリゴン描画が有効か否かの判定（以下、ポリゴン消去判定）には、複数の変換済み座標データが必要となるためである。そして、判定対象のポリゴンを構成する頂点の変換済み座標データを変換座標バッファ１１０から取り出して、ポリゴン消去判定を行う。そして、判定結果に基づいてポリゴン描画有効フラグを生成して、頂点消去判定部１０６へと出力する。ポリゴン描画有効フラグは、対応するポリゴンが有効であれば真、対応するポリゴンが無効であれば偽を示す。ポリゴン消去判定の具体例については、ポリゴンの表現形式毎に後述する。
【００４９】
頂点消去判定部１０６は、ポリゴン描画有効フラグを用いて頂点が有効かどうかを示すフラグ（以下、頂点有効フラグ）を生成する。具体的には、まず、頂点消去判定部１０６は、ポリゴン消去判定部１０５から出力されたポリゴン描画有効フラグ又はこのポリゴン描画有効フラグを用いて生成される中間的な頂点消去判定結果を示すフラグ（以下、中間結果フラグ）を頂点消去判定バッファ１１１へ格納する。これは、頂点消去判定には、複数のポリゴン描画有効フラグ又は中間結果フラグが必要となるためである。そして、判定対象の頂点を含むポリゴンのポリゴン描画有効フラグ、又は判定対象の頂点の中間結果フラグを頂点消去判定バッファ１１１から取り出して、頂点が有効であるか否かを判定する。そして、判定結果に基づいて頂点有効フラグを生成して、形態データロード部１０７へと出力する。頂点有効フラグ及び中間結果フラグは、対応する頂点が有効であれば真、対応する頂点が無効であれば偽を示す。
【００５０】
形態データロード部１０７は、描画命令２０４に従って頂点データリスト２０３のうち形態データリスト２０６にアクセスし、形態データ２０８のロードを行う。具体的には、形態データロード部１０７は、頂点消去判定部１０６から出力された頂点有効フラグを参照することで、有効な頂点データについてのみ形態データのロードを行い、変換済み座標データと合わせてポリゴン描画処理部１０８へと出力する。
【００５１】
ポリゴン描画処理部１０８は、入力された頂点データ（変換済み座標データ及び形態データ）を用いてポリゴン描画処理を行い、ポリゴン画像を生成する。ポリゴン描画処理は、コンピュータグラフィックス処理で用いられる一般的な処理により実行される。ポリゴン描画処理部１０８は、メモリインターフェース１０９を介して生成したポリゴン画像をメモリへと出力する。
【００５２】
メモリインターフェース１０９は、画像生成装置１００が備える各処理部とメモリ２００との間でデータのやり取りを行う。
【００５３】
変換座標バッファ１１０は、座標変換部１０４で変換された変換済み座標データを保持する。変換座標バッファ１１０は、ポリゴン消去判定部１０５における判定処理の対象となるポリゴンが複数の頂点（本実施の形態では３つの頂点）で構成されるために、一時的に変換済み座標データを保持するためのバッファである。また、ポリゴン描画処理部１０８における描画処理でも変換済み座標データを用いるために、変換済み座標データを保持するためのバッファである。
【００５４】
頂点消去判定バッファ１１１は、ポリゴン描画有効フラグ又は中間結果フラグを保持する。
【００５５】
続いて、ポリゴン消去判定部１０５が行うポリゴン消去判定について説明する。図４は、ポリゴン消去判定を説明するための図である。ポリゴン消去判定とは、複数の頂点から構成されるポリゴンが画像生成時に用いられるか否かを判定する処理である。
【００５６】
ポリゴン消去判定では、視点３０１を原点とした座標系（ディスプレイ座標系）へ変換した座標データを用いる。ポリゴン消去判定は、クリッピング判定及びカリング判定により行う。
【００５７】
クリッピング判定は、非特許文献１に記載されている方法のように、ポリゴンが可視空間を表す六面体であるビューボリューム３０２の中に入っているかどうかを判定する処理である。ポリゴンを構成する頂点のうち全ての頂点の座標がビューボリューム３０２の外に存在していればポリゴン描画は無効となる。例えば、ポリゴン３０５のように完全にビューボリューム３０２の外に存在するポリゴンは、クリッピング判定により描画が無効となる。
【００５８】
一方、カリング判定では、ビューボリューム３０２の中に入っているポリゴンについて視点から見たときのポリゴン面が表向きかどうかを判定する。カリング判定は、非特許文献１に記載されている方法のように、ポリゴンを構成する頂点の座標から面法線ベクトルを求め視点方向ベクトルとの内積の符号を確認することでポリゴンの表裏を判定することができる。視点３０１から見て裏向きであればポリゴン描画は無効となる。例えば、ポリゴン３０６のようにポリゴン面が視点３０１から見て裏向きであるポリゴンはカリング判定により描画が無効となる。
【００５９】
ポリゴン３０４のように、クリッピング判定及びカリング判定で無効と判断されなかったポリゴンについてのみディスプレイ面３０３に投影して描画することができる有効なポリゴンと判定する。
【００６０】
続いて、本実施の形態の画像生成装置の動作について説明する。
【００６１】
図５は、本実施の形態の画像生成装置の動作を示すフローチャートである。本実施の形態の画像生成処理は、まず、ホストインターフェース１０１を介してＣＰＵから描画命令を制御部１０２が受け取ることで開始する。
【００６２】
制御部１０２からの指示に基づいて、座標データロード部１０３は、入力ポリゴンモデルの頂点データのうち座標データのロードを行う（Ｓ２０１）。座標変換部１０４は、ロードされた座標データをワールド座標及びディスプレイ座標へと変換する（Ｓ２０２）。ポリゴン消去判定部１０５は、判定対象のポリゴンを構成する頂点の変換済み座標データを用いてポリゴン消去判定を行う（Ｓ２０３）。頂点消去判定部１０６は、判定対象の頂点を含むポリゴンのポリゴン消去判定結果を用いて頂点消去判定を行う（Ｓ２０４）。判定対象の頂点を含む全てのポリゴンについてのポリゴン消去判定結果で、１つ以上のポリゴン描画が有効であった場合、判定対象の頂点は有効な頂点データであると判定する（Ｓ２０４で「頂点が有効」）。全部のポリゴン描画が無効であった場合は無効な頂点データであると判定する（Ｓ２０４で「頂点が無効」）。形態データロード部１０７は、頂点消去判定部１０６により生成された頂点消去判定結果を参照して、有効とされた頂点データについてのみその形態データのロードを行う（Ｓ２０５）。ロードした形態データと該当する頂点の変換済み座標データとを合わせてポリゴン描画処理部１０８へと出力する。ポリゴン描画処理部１０８は、形態データロード部１０７から受け取った頂点データ（変換済み座標データ及び形態データ）を用いてポリゴン描画処理を行う（Ｓ２０６）。以上の処理が全てのポリゴンについて終了したかを判定し（Ｓ２０７）、終了していない場合（Ｓ２０７で「継続」）、各処理（Ｓ２０１〜Ｓ２０６）が繰り返される。全てのポリゴンについて終了した場合（Ｓ２０７で「完了」）、画像生成装置１００は描画された画像を出力する（Ｓ２０８）。
【００６３】
以上のようにして、本実施の形態の画像生成装置は、頂点データのうち全ての座標データをロードするのに対して、形態データについては、有効な頂点と判定された頂点に対応する形態データのみをロードする。これにより、入力ポリゴンデータのロードに関するメモリアクセス量を低減することができる。また、本実施の形態の画像生成装置は、画像の描画処理と並行して、頂点がポリゴン描画に必要であるか否かを判定するため、インタラクティブ用途にも適用することができる。
【００６４】
以下では、ポリゴンの表現形式に基づいて、より具体的に本実施の形態の画像生成装置について説明する。ここでは、ポリゴンストリップ、ポリゴンファン及びポリゴンメッシュの３つの表現形式について説明する。
【００６５】
（ポリゴンストリップ形式）
まず、入力ポリゴンモデルがポリゴンストリップ形式で構成されている場合について説明する。
【００６６】
図６は、入力ポリゴンモデルがポリゴンストリップ形式で構成されている場合の処理の流れを示す図である。ポリゴンストリップ形式は、頂点を共有しながら連続でポリゴンを描画する形式である。同図に示すように、ポリゴンストリップ４０１のポリゴンＰｊ（ｊ＝０〜６）は、頂点Ｖｊ、Ｖｊ＋１、Ｖｊ＋２の３点から構成される。また、ポリゴンストリップ４０１の頂点データは、Ｖ０→Ｖ１→Ｖ２→Ｖ３→Ｖ４→Ｖ５→Ｖ６→Ｖ７→Ｖ８の順で指定される。なお、図６に示す例においては、ポリゴンＰ０、Ｐ１及びＰ６が有効なポリゴンであるとする。
【００６７】
タイムチャート４０２は、座標データのロードから頂点有効フラグの生成（頂点判定処理）までの処理の流れを示すタイムチャートである。以下では、タイムチャート４０２に沿ってポリゴンストリップ形式の処理の流れを説明する。
【００６８】
座標データロード部１０３は、頂点データの指定順に、頂点データのうち座標データＭｉ（ｉ＝０〜８）のロードを順次行い、座標変換部１０４へ出力する。座標変換部１０４は、座標データロード部１０３から受け取った頂点Ｖｉの座標データＭｉについてそれぞれ座標変換を行う。これにより、変換済み座標データＤｉをポリゴン消去判定部１０５に出力する。ポリゴン消去判定部１０５は、入力された変換済み座標データＤｉを変換座標バッファ１１０に保持させる。
【００６９】
ポリゴン消去判定部１０５は、ポリゴン消去判定をＰ０→Ｐ１→Ｐ２→Ｐ３→Ｐ４→Ｐ５→Ｐ６の順に行う。ポリゴン消去判定部１０５は、ポリゴンＰｊについてのポリゴン消去判定を行うときに、ポリゴンＰｊを構成する頂点Ｖｊ、Ｖｊ＋１、Ｖｊ＋２の変換済み座標データＤｊ、Ｄｊ＋１、Ｄｊ＋２が揃うまで、座標変換部１０４が生成した変換済み座標データを保持させる。変換済み座標データが揃ったときに変換済み座標データを用いてポリゴン消去判定を行い、ポリゴン描画有効フラグＦＰｊ（ポリゴンが有効であれば真、無効であれば偽）を生成する。
【００７０】
頂点消去判定部１０６は、頂点消去判定をＶ０→Ｖ１→Ｖ２→Ｖ３→Ｖ４→Ｖ５→Ｖ６→Ｖ７→Ｖ８の順に行う。頂点消去判定部１０６は、頂点Ｖｉについての頂点消去判定を行うときに、頂点Ｖｉを含むポリゴンＰｉ−２、Ｐｉ−１及びＰｉのポリゴン描画有効フラグＦＰｉ−２、ＦＰｉ−１、ＦＰｉ（存在しないポリゴン番号のポリゴン描画有効フラグは偽として扱う）の論理和演算を行う。すなわち、頂点Ｖｉが有効であるか否かを示す頂点有効フラグＦＶｉは、以下の式１に基づいて算出される。
【００７１】
ＦＶｉ＝ＦＰｉ−２‖ＦＰｉ−１‖ＦＰｉ    ・・・（式１）
【００７２】
なお、頂点消去判定部１０６は、ポリゴン描画有効フラグＦＰｉ−２、ＦＰｉ−１、ＦＰｉが揃うまで、ポリゴン消去判定部１０５が生成したポリゴン描画有効フラグ又はその中間的な論理和を頂点消去判定バッファ１１１に保持させる。例えば、頂点Ｖ２については、頂点Ｖ２が含まれるポリゴンＰ０、Ｐ１及びＰ２のうちＰ０及びＰ１についてポリゴン描画が有効であるため、有効な頂点データと判定する。一方、頂点Ｖ４については、頂点Ｖ４が含まれるポリゴンＰ２、Ｐ３及びＰ４のいずれもポリゴン描画が無効であるため、無効な頂点データと判定する。
【００７３】
形態データロード部１０７は、頂点消去判定部１０６により有効と判定された頂点Ｖ０、Ｖ１、Ｖ２、Ｖ３、Ｖ６、Ｖ７及びＶ８について頂点消去判定の順に形態データのロードを行い、該当する頂点の変換済み座標データと合わせてポリゴン描画処理部１０８へ出力する。ポリゴン描画処理部１０８は、これらの頂点データを受け取ってポリゴン描画処理を行う。
【００７４】
なお、以上の処理は、パイプライン形式で実行される。すなわち、図６のタイムチャート４０２で示すように、頂点Ｖ０から順に、座標データのロードを行い、ロードした座標データを変換することで変換済み座標データを生成する。そして、頂点Ｖ２に対応する変換済み座標データＤ２を生成して初めて、ポリゴン消去判定及び頂点消去判定が実行できる。以降、座標データがロードされる毎に、座標変換、ポリゴン消去判定及び頂点消去判定が実行される。以下では、パイプライン形式で上述した処理が実行される様子を、本実施の形態の画像生成装置１００の、各処理部でのデータの流れに基づいて説明する。
【００７５】
図７は、ポリゴンストリップ形式に適応した画像生成装置の、各処理部でのデータの流れを示す図である。同図に示すように、メモリ２００上にポリゴンストリップの座標データリスト５０１及び形態データリスト５０２が配置されているとする。さらに、メモリ２００は、ポリゴン描画処理部１０８で描画された出力画像５０３も保持する。
【００７６】
座標データロード部１０３は、メモリ２００上の座標データリスト５０１にアクセスして、座標データ５０４を順次ロードして座標変換部１０４へ出力する。
【００７７】
座標変換部１０４は、座標データ５０４から変換済み座標データ５０５を計算してポリゴン消去判定部１０５へ出力する。
【００７８】
ポリゴン消去判定部１０５は、変換済み座標データ５０５を変換座標バッファ１１０へと格納する。上述したように本実施の形態では、ポリゴンは３つの頂点で構成されるため、変換座標バッファ１１０は、３つの変換済み座標データ５０６を格納することができる。変換座標バッファ１１０は、ＦＩＦＯ（Ｆｉｒｓｔ  Ｉｎ  Ｆｉｒｓｔ  Ｏｕｔ）形式で制御され、入力される座標データを順次格納する。ポリゴン消去判定に用いる必要がなくなった座標データについては、変換座標バッファ１１０から削除され、有効な頂点に対応する変換済み座標データについては形態データロード部１０７に出力される。
【００７９】
ポリゴン消去判定部１０５は、変換座標バッファ１１０に格納される変換済み座標データを用いて、クリッピング判定及びカリング判定を実行することにより、ポリゴンが有効であるか否かを判定する。そして、判定結果に基づいて、ポリゴン描画有効フラグ５０７を頂点消去判定部１０６に出力する。
【００８０】
頂点消去判定部１０６は、ポリゴン描画有効フラグ５０７を頂点消去判定バッファ１１１へと格納する。頂点消去判定バッファ１１１も、ＦＩＦＯ形式で制御され、格納されているポリゴン描画有効フラグ５０８へ新しいポリゴン描画有効フラグを登録するとき、古いポリゴン描画有効フラグから順に削除する。頂点消去判定部１０６は、ポリゴン描画有効フラグ５０８を用いて頂点有効フラグ５０９を生成する。頂点有効フラグ５０９は、上述したように式１を用いて生成される。頂点消去判定部１０６は、生成した頂点有効フラグ５０９を形態データロード部１０７へと出力する。
【００８１】
なお、頂点消去判定バッファ１１１は、判定対象となる頂点が含まれる全てのポリゴン（図７では３つ）のポリゴン描画有効フラグのみを保持するように制御されている。これは、ポリゴンストリップ形式では頂点の指定順にポリゴンが描画され、かつ、頂点消去判定バッファ１１１がＦＩＦＯ形式で制御されるためである。したがって、頂点消去判定部１０６は、常に頂点消去判定バッファ１１１に格納されるポリゴン描画有効フラグ５０８（図７では２つ）の論理和演算を行うことで、頂点有効フラグを生成することができる。
【００８２】
形態データロード部１０７は、頂点有効フラグ５０９を参照して有効な頂点であるときのみ、メモリ２００上の形態データリスト５０２にアクセスして該当する頂点の形態データをロードする。さらに、該当頂点の変換済み座標データ５１０を変換座標バッファ１１０から受け取り、形態データと合わせて頂点データ５１１としてポリゴン描画処理部１０８へ出力する。
【００８３】
ポリゴン描画処理部１０８は、頂点データ５１１を用いてポリゴン描画処理を行い、メモリ２００上の出力画像５０３を生成する。
【００８４】
以上のように、変換座標バッファ１１０及び頂点消去判定バッファ１１１をＦＩＦＯ形式で制御することにより、座標データのロード処理と、座標変換処理と、ポリゴン消去判定処理と、頂点消去判定処理と、形態データのロード処理と、ポリゴン描画処理とをパイプライン形式で制御することができる。
【００８５】
これにより、メモリ２００へのアクセス量を大幅に低減することができ、メモリバンド幅を圧迫することがなくなる。よって、高精細なポリゴン描画処理をリアルタイムで実現することができる。
【００８６】
（ポリゴンファン形式）
続いて、入力ポリゴンモデルがポリゴンファン形式で構成されている場合について説明する。
【００８７】
図８は、入力ポリゴンモデルがポリゴンファン形式で構成されている場合の処理の流れを示す図である。ポリゴンファン形式は、上述のポリゴンストリップ形式と同様に、頂点を共有しながら連続でポリゴンを描画する形式である。開始頂点が全てのポリゴンで共有される点がポリゴンストリップ形式と異なる。同図に示すように、ポリゴンファン６０１のポリゴンＰｊ（ｊ＝０〜４）は、頂点Ｖ０、Ｖｊ＋１、Ｖｊ＋２の３点から構成される。また、ポリゴンファン６０１の頂点データはＶ０→Ｖ１→Ｖ２→Ｖ３→Ｖ４→Ｖ５→Ｖ６の順で指定される。なお、図８においては、ポリゴンＰ０及びＰ４が有効なポリゴンであるとする。
【００８８】
タイムチャート６０２は、座標データのロードから頂点有効フラグの生成までの、処理の流れを示すタイムチャートである。以下では、タイムチャート６０２に沿ってポリゴンファン形式の処理の流れについて説明する。
【００８９】
座標データロード部１０３は、上記ポリゴンストリップの処理と同様に、上記頂点データの指定順に頂点データのうち座標データＭｉ（ｉ＝０〜６）のロードを行い、座標変換部１０４へ出力する。座標変換部１０４は、座標データロード部１０３から受け取った頂点Ｖｉ（ｉ＝０〜６）の座標データについてそれぞれ座標変換を行う。これにより、変換済み座標データＤｉをポリゴン消去判定部１０５に出力する。ポリゴン消去判定部１０５は、入力された変換済み座標データＤｉを変換座標バッファ１１０に保持させる。
【００９０】
ポリゴン消去判定部１０５は、ポリゴン消去判定をＰ０→Ｐ１→Ｐ２→Ｐ３→Ｐ４の順に行う。ポリゴン消去判定部１０５は、ポリゴンＰｊについてのポリゴン消去判定を行うときに、ポリゴンＰｊを構成する頂点Ｖ０、Ｖｊ、Ｖｊ＋１の変換済み座標データＤ０、Ｄｊ、Ｄｊ＋１が揃うまで、座標変換部１０４が生成した変換済み座標データを保持させる。変換済み座標データが揃ったときに変換済み座標データを用いてポリゴン消去判定を行い、ポリゴン描画有効フラグＦＰｊ（ポリゴンが有効であれば真、無効であれば偽）を生成する。
【００９１】
頂点消去判定部１０６は、頂点消去判定をＶ０→Ｖ１→Ｖ２→Ｖ３→Ｖ４→Ｖ５→Ｖ６の順に行う。頂点消去判定部１０６は、開始頂点Ｖ０と、開始頂点Ｖ０を除く頂点Ｖｉ（ｉ＝１〜６）とについて、それぞれ異なる条件式を用いて頂点消去判定を行う。
【００９２】
開始頂点Ｖ０の頂点消去判定では、いずれか１つのポリゴン描画有効フラグＦＰｊが真となった場合に、開始頂点Ｖ０は有効であると判定する。開始頂点Ｖ０が有効であるか否かを示す頂点有効フラグＦＶ０は、以下の式２に示す条件式に基づいて生成される。
【００９３】
ＦＶ０＝（∃ｊ）（ＦＰｊ）    ・・・（式２）
【００９４】
より具体的には、頂点有効フラグＦＶ０は、式３に示す論理和演算を行うことで算出される。
【００９５】
ＦＶ０＝ＦＶ０‖ＦＰｊ    ・・・（式３）
【００９６】
頂点消去判定部１０６は、ポリゴン描画有効フラグの論理和を中間結果フラグ（式３の右辺のＦＶ０）として、頂点消去判定バッファ１１１に保持させる。中間結果フラグが真となった時点で、開始頂点Ｖ０は有効な頂点データであると判定する。中間結果フラグが最後まで真にならなかった場合は、開始頂点Ｖ０は無効な頂点データであると判定する。
【００９７】
開始頂点Ｖ０を除く頂点Ｖｉを含むポリゴンＰｉ−２及びＰｉ−１のポリゴン描画有効フラグＦＰｉ−２及びＦＰｉ−１（存在しないポリゴン番号のポリゴン描画有効フラグは偽として扱う）の論理和演算を行う。すなわち、開始頂点Ｖ０を除く頂点Ｖｉが有効であるか否かを示す頂点有効フラグＦＶｉは、以下の式４に基づいて生成される。
【００９８】
ＦＶｉ＝ＦＰｉ‖ＦＰｉ−１    ・・・（式４）
【００９９】
なお、頂点消去判定部１０６は、ポリゴン描画有効フラグＦＰｉ−２及びＦＰｉ−１が揃うまで、ポリゴン消去判定部１０５が生成したポリゴン描画有効フラグ又はその中間的な論理和を頂点消去判定バッファ１１１に保持させる。例えば、頂点Ｖ２については、頂点Ｖ２が含まれるポリゴンＰ０及びＰ１のうちＰ０についてポリゴン描画が有効であるため、有効な頂点データと判定する。一方、頂点Ｖ３については、頂点Ｖ３が含まれるポリゴンＰ１及びＰ２のいずれもポリゴン描画が無効であるため、無効な頂点データと判定する。
【０１００】
形態データロード部１０７は、頂点消去判定部１０６により有効と判断された頂点Ｖ０、Ｖ１、Ｖ２、Ｖ５及びＶ６について、頂点消去判定の順に形態データのロードを行い、該当する頂点の変換済み座標データと合わせてポリゴン描画処理部１０８へ出力する。ポリゴン描画処理部１０８は、これらの頂点データを受け取ってポリゴン描画処理を行う。
【０１０１】
なお、以上の処理は、ポリゴンストリップ形式の場合と同様に、パイプライン形式で実行される。すなわち、図８のタイムチャート６０２で示すように、頂点Ｖ０から順に、座標データのロードを行い、ロードした座標データを変換することで変換済み座標データを生成する。そして、頂点Ｖ２に対応する変換済み座標データを生成して初めて、ポリゴン消去判定及び頂点消去判定が実行される。以降、座標データがロードされるたびに、座標変換、ポリゴン消去判定及び頂点消去判定が実行される。以下では、パイプライン形式で上述した処理が実行される様子を、本実施の形態の画像生成装置１００の、各処理部でのデータの流れに基づいて説明する。
【０１０２】
図９は、ポリゴンファン形式に適応した画像生成装置の、各処理部でのデータの流れを示す図である。同図に示すように、メモリ２００上にポリゴンファンの座標データリスト７０１及び形態データリスト７０２が配置されているとする。さらに、メモリ２００は、ポリゴン描画処理部１０８が出力する出力画像７０３も保持する。
【０１０３】
座標データロード部１０３は、メモリ２００上の座標データリスト７０１にアクセスして座標データ７０４を順次ロードして座標変換部１０４へ出力する。
【０１０４】
座標変換部１０４は、座標データ７０４から変換済み座標データ７０５を計算してポリゴン消去判定部１０５へ出力する。
【０１０５】
ポリゴン消去判定部１０５は、変換済み座標データ７０５を変換座標バッファ１１０へと格納する。変換座標バッファ１１０は、ポリゴンファン６０１の開始頂点Ｖ０の変換済み座標データ７０６と、開始頂点Ｖ０を除く頂点Ｖｉの変換済み座標データ７０７とを格納する。変換済み座標データ７０６は、ポリゴンファンの処理中は保持される。開始頂点以外の新しい変換済み座標データは、変換済み座標データ７０７として順次格納され、古い変換済み座標データから順に、不要となったら変換座標バッファ１１０から削除される。なお、変換座標バッファ１１０の変換済み座標データ７０７が保持される領域はＦＩＦＯ形式で制御される。
【０１０６】
ポリゴン消去判定部１０５は、変換済み座標データ７０６及び７０７を用いてクリッピング判定及びカリング判定を実行することにより、ポリゴンが有効であるか否かを判定する。そして、判定結果に基づいて、ポリゴン描画有効フラグ７０８を生成して頂点消去判定部１０６へと出力する。
【０１０７】
頂点消去判定部１０６は、ポリゴン描画有効フラグ７０８を頂点消去判定バッファ１１１へと格納する。頂点消去判定バッファ１１１は、ポリゴンファン開始頂点の中間結果フラグ７０９と、開始頂点以外の頂点消去判定に使用するポリゴン描画有効フラグ７１０とを格納する。頂点消去判定バッファ１１１は、ポリゴンファン開始頂点の中間結果フラグ７０９を、ポリゴンファンの処理中は保持する。ポリゴン描画有効フラグ７１０へ新しいポリゴン描画有効フラグを登録するとき、古いポリゴン描画有効フラグから順に削除する。なお、頂点消去判定バッファ１１１のポリゴン描画有効フラグ７１０が保持される領域はＦＩＦＯ形式で制御される。
【０１０８】
頂点消去判定部１０６は、ポリゴンファン開始頂点の頂点消去判定を行う場合、ポリゴンファン描画開始時に中間結果フラグ７０９は偽に初期化する。以降、ポリゴン描画有効フラグ７０８を受け取るたびに、式３に基づいて中間結果フラグ７０９と新しいポリゴン描画有効フラグ７０８との論理和演算を行うことで、中間結果フラグ７０９を更新する。更新の結果、中間結果フラグ７０９が初めて偽から真に変わったときに、頂点有効フラグ７１１を真として生成して形態データロード部１０７へと出力する。
【０１０９】
開始頂点以外の頂点消去判定を行う場合、ポリゴン描画有効フラグ７１０の論理和演算を行うことで、頂点有効フラグ７１１を生成して形態データロード部１０７へと出力する。
【０１１０】
なお、頂点消去判定バッファ１１１は、ポリゴンファンの開始頂点の中間結果フラグと、判定対象となる頂点が含まれる全てのポリゴン（図９では２つ）のポリゴン描画有効フラグのみとを保持するように制御されている。これは、ポリゴンファン形式では、ポリゴンストリップ形式と同様に頂点の指定順にポリゴンが描画され、かつ、頂点消去判定バッファ１１１のポリゴン描画有効フラグが保持される領域がＦＩＦＯ形式で制御されるためである。したがって、頂点消去判定部１０６は、常に頂点消去判定バッファ１１１に格納されるポリゴン描画有効フラグ７１０（図９では２つ）の論理和演算を行うことで、頂点有効フラグを生成することができる。
【０１１１】
形態データロード部１０７は、頂点有効フラグ７１１を参照して有効な頂点であるときのみ、メモリ２００上の形態データリスト７０２にアクセスして該当頂点の形態データをロードする。さらに、該当頂点の変換済み座標データ７１２を変換座標バッファ１１０から受け取り、形態データと合わせて頂点データ７１３としてポリゴン描画処理部１０８へ出力する。
【０１１２】
ポリゴン描画処理部１０８は、頂点データ７１３を用いてポリゴン描画処理を行い、メモリ２００上の出力画像７０３を生成する。
【０１１３】
以上のように、開始頂点を除いた頂点に対応する変換済み座標データ７０７及びポリゴン描画有効フラグ７１０を、ＦＩＦＯ形式で制御したバッファに格納させることで、座標データのロード処理と、座標変換処理と、ポリゴン消去判定処理と、頂点消去判定処理と、形態データのロード処理と、ポリゴン描画処理とをパイプライン形式で制御することができる。
【０１１４】
これにより、メモリ２００へのアクセス量を大幅に低減することができ、メモリバンド幅を圧迫することがなくなる。よって、高精細なポリゴン描画処理をリアルタイムで実現することができる。
【０１１５】
（ポリゴンメッシュ形式）
図１０は、入力ポリゴンモデルがポリゴンメッシュ形式で構成されている場合の処理の流れを示す図である。ポリゴンメッシュ形式は、内部の多くのポリゴンで頂点の共有が行われるものの、上記のポリゴンストリップ及びポリゴンファンとは異なり、ポリゴン単位で頂点の指定が行われる形式である。
【０１１６】
同図に示すように、ポリゴンメッシュ８０１の頂点データは、例えば、Ｐ０（Ｖ０、Ｖ１、Ｖ２）→Ｐ１（Ｖ２、Ｖ１、Ｖ３）→Ｐ２（Ｖ２、Ｖ３、Ｖ４）→Ｐ３（Ｖ４、Ｖ３、Ｖ５）→Ｐ４（Ｖ４、Ｖ５、Ｖ６）→Ｐ５（Ｖ７、Ｖ０、Ｖ２）→Ｐ６（Ｖ７、Ｖ２、Ｖ８）→Ｐ７（Ｖ８、Ｖ２、Ｖ４）→Ｐ８（Ｖ８、Ｖ４、Ｖ９）→Ｐ９（Ｖ９、Ｖ４、Ｖ６）の順で指定される（ポリゴンメッシュは自由度の高い形式であり必ずしもこの順番で指定されるとは限らない）。なお、図１０に示す例においては、ポリゴンＰ０、Ｐ１、Ｐ５、Ｐ６、Ｐ７及びＰ８が有効なポリゴンであり、ポリゴンＰ２、Ｐ３、Ｐ４及びＰ９が無効なポリゴンであるとする。
【０１１７】
タイムチャート８０２は、座標データのロードから頂点有効フラグの生成（頂点判定処理）までの処理の流れを示すタイムチャートである。以下では、タイムチャート８０２に沿ってポリゴンメッシュ形式の処理の流れについて説明する。
【０１１８】
座標データロード部１０３は、頂点データの指定順に、頂点データのうち座標データＭｉ（ｉ＝０〜９）のロードを行い、座標変換部１０４へと渡す。ここで、ポリゴンメッシュ上の同じ頂点の座標データを重複してロードするのを防ぐため、変換座標バッファ１１０で変換済み座標データが保持されている頂点についてはロードをしない。
【０１１９】
座標変換部１０４は、座標データロード部１０３から受け取った頂点Ｖｉの座標データについてそれぞれ座標変換を行い、変換済み座標データＤｉを座標データの入力順に生成する。
【０１２０】
ポリゴン消去判定部１０５は、入力された変換済み座標データＤｉを変換座標バッファ１１０に保持させる。さらに、ポリゴン消去判定をＰ０→Ｐ１→Ｐ２→Ｐ３→Ｐ４→Ｐ５→Ｐ６→Ｐ７→Ｐ８→Ｐ９の順に行う。ポリゴン消去判定部１０５は、ポリゴンＰｊ（ｊ＝０〜９）についてのポリゴン消去判定を行うときに、ポリゴンＰｊを構成する頂点Ｖｋ、Ｖｌ、Ｖｍ（ｋ、ｌ、ｍ＝０〜９）の変換済み座標データＤｋ、Ｄｌ、Ｄｍが揃うまで、座標変換部１０４が生成した変換済み座標データを保持させる。変換済み座標データが揃ったときに変換済み座標データを用いてポリゴン消去判定を行い、ポリゴン描画有効フラグＦＰｊ（ポリゴンが有効であれば真、無効であれば偽）を生成する。
【０１２１】
ここで、ポリゴンメッシュ形式の場合は同じ頂点が別のポリゴンと共有することが多いため、上記のポリゴンＰｊのポリゴン消去判定後も、近傍のポリゴン消去判定を行っている期間（一例として図１０のタイムチャート８０２に示すポリゴン描画有効フラグＦＰｊを求めている期間）は、変換済み座標データＤｋ、Ｄｌ、Ｄｍを保持しておく。座標データロード部１０３は、変換済み座標データが保持されている頂点の座標データをロードせず、ポリゴン消去判定部１０５は、保持されている変換済み座標データを再度ポリゴン消去判定に用いる。
【０１２２】
例えば、ポリゴンＰ８についてのポリゴン消去判定を行うときは、ポリゴンＰ８を構成する頂点Ｖ８、Ｖ４、Ｖ９のうち、座標データロード部１０３は、頂点Ｖ９の座標データＭ９をロードし、座標変換部１０４は変換済み座標データＤ９を生成する。これに対して、頂点Ｖ８、Ｖ４については変換済み座標データＤ８、Ｄ４がすでに変換座標バッファ１１０に保持されているので、座標データロード部１０３は、頂点Ｖ８、Ｖ４の座標データをロードせず、座標変換部１０４は変換済み座標データＤ８、Ｄ４の生成を行わない。ポリゴン消去判定部１０５は、新たに生成された変換済み座標データＤ９と、すでに保持されている変換済み座標データＤ８、Ｄ４とを用いてポリゴン消去判定を行う。
【０１２３】
頂点消去判定部１０６は、ポリゴン描画有効フラグＦＰｊを用いて、頂点Ｖｉについて頂点消去判定を行う。すなわち、以下の式５に示すように、頂点Ｖｉが含まれる、いずれかのポリゴンのポリゴン描画有効フラグＦＰｊが真となれば、頂点Ｖｉの頂点有効フラグＦＶｉも真とする。
【０１２４】
ＦＶｉ＝（∃ｊ）（ＦＰｊ＆（Ｖｉ∈Ｐｊ））    ・・・（式５）
【０１２５】
具体的には、頂点消去判定部１０６は、頂点Ｖｉ（ｉ＝０〜９）についての頂点消去判定を行うとき、はじめに頂点有効フラグＦＶｉを偽に初期化しておく。頂点消去判定部１０６は、ポリゴン消去判定部１０５が生成したポリゴン描画有効フラグＦＰｊをＰ０→Ｐ１→Ｐ２→Ｐ３→Ｐ４→Ｐ５→Ｐ６→Ｐ７→Ｐ８→Ｐ９の順に受け取り、それぞれポリゴンＰｊ（ｊ＝０〜９）を構成する頂点Ｖｋ、Ｖｌ、Ｖｍ（ｋ、ｌ、ｍ＝０〜９）の中間結果フラグＦＶｋ、ＦＶｌ、ＦＶｍとの論理和演算を行い、中間結果フラグＦＶｋ、ＦＶｌ、ＦＶｍを更新する（更新は頂点が指定された順番、すなわちＦＶｋ→ＦＶｌ→ＦＶｍの順に行う）。すなわち、中間結果フラグＦＶｋ（ＦＶｌ、ＦＶｍも同様）は、ポリゴン描画有効フラグＦＰｊを受け取るたびに、以下の式６に基づいて算出される。
【０１２６】
ＦＶｋ＝ＦＶｋ‖（ＦＰｊ＆（Ｖｋ∈Ｐｊ））    ・・・（式６）
【０１２７】
例えば、ポリゴン消去判定部１０５がポリゴンＰ８のポリゴン描画有効フラグＦＰ８を生成した場合について説明する。頂点消去判定部１０６は、ポリゴンＰ８を構成する頂点Ｖ８、Ｖ４、Ｖ９について、それぞれ中間結果フラグＦＶ８、ＦＶ４、ＦＶ９とポリゴン描画有効フラグＦＰ８との論理和演算を行い、中間結果フラグＦＶ８、ＦＶ４、ＦＶ９を更新する。中間結果フラグＦＶｉが偽から真となった時点で、その頂点は有効な頂点データであると判定する。図１０の例では、Ｖ０→Ｖ１→Ｖ２→Ｖ３→Ｖ７→Ｖ８→Ｖ４→Ｖ９の順に有効な頂点データであると判定される。上記のポリゴン消去判定結果による中間結果フラグＦＶｉが最後まで真にならなかった頂点Ｖ５及びＶ６は、無効な頂点データであると判定される。
【０１２８】
形態データロード部１０７は、頂点消去判定部１０６により有効と判断された頂点Ｖ０、Ｖ１、Ｖ２、Ｖ３、Ｖ７、Ｖ８、Ｖ４、Ｖ９について頂点消去判定の順に形態データのロードを行い、該当する頂点の変換済み座標データと合わせてポリゴン描画処理部１０８へ出力する。ポリゴン描画処理部１０８は、これらの頂点データを受け取ってポリゴン描画処理を行う。
【０１２９】
以上のように、入力ポリゴンモデルがポリゴンメッシュ形式で表現される場合であっても、ポリゴン描画処理に必要な場合にのみ、形態データがロードされる。これにより、全てのデータをロードする場合に比べてメモリアクセスを低減することができる。
【０１３０】
以下では、上述した処理が実行される様子を、本実施の形態の画像生成装置１００の、各処理部でのデータの流れに基づいて説明する。
【０１３１】
図１１は、ポリゴンメッシュ形式に適応した画像生成装置の、各処理部でのデータの流れを示す図である。同図に示すように、メモリ２００上にポリゴンメッシュの座標データリスト９０１及び形態データリスト９０２が配置されているとする。さらに、メモリ２００は、ポリゴン描画処理部１０８が出力する出力画像９０３も保持する。
【０１３２】
座標データロード部１０３は、メモリ２００上の座標データリスト９０１にアクセスして座標データ９０４をロードして座標変換部１０４へ出力する。ここで、ポリゴンメッシュ上の同じ頂点の座標データを重複してロードしないよう、変換座標バッファ１１０で変換済み座標データが保持されている頂点についてはロードをしない。
【０１３３】
座標変換部１０４は、座標データ９０４から変換済み座標データ９０５を計算してポリゴン消去判定部１０５へ出力する。
【０１３４】
ポリゴン消去判定部１０５は、変換済み座標データ９０５を変換座標バッファ１１０へと格納する。変換座標バッファ１１０は、登録可能な数だけ変換済み座標データ９０６を登録する。登録可能な数に達したときに新たな変換済み座標データを登録する場合、最も参照が古い頂点の変換済み座標データを変換座標バッファ１１０から削除する。ポリゴン消去判定部１０５は、変換済み座標データ９０６を用いてポリゴン描画有効フラグ９０７を生成して頂点消去判定部１０６へと出力する。
【０１３５】
頂点消去判定部１０６は、ポリゴン描画有効フラグ９０７から生成される中間結果フラグを頂点消去判定バッファ１１１へと格納する。頂点消去判定バッファ１１１は、登録可能な数（変換座標バッファ１１０への変換済み座標データ数と同数）だけ中間結果フラグ９０８を登録する。登録可能な数に達したときに新たな中間結果フラグを登録する場合、最も参照が古い頂点の中間結果フラグを頂点消去判定バッファ１１１から削除する。頂点消去判定部１０６は、ポリゴンメッシュ描画開始時に中間結果フラグ９０８は全て偽に初期化される。以降、新しいポリゴン描画有効フラグ９０７を受け取るたびに、式６に基づいて該当ポリゴンに含まれる頂点の中間結果フラグ９０８との論理和演算を行うことで、中間結果フラグ９０８を更新する。更新結果が初めて偽から真に変わったときに、該当頂点が真であることを示す頂点有効フラグ９０９を生成して形態データロード部１０７へと出力する。
【０１３６】
形態データロード部１０７は、頂点有効フラグ９０９を参照して有効な頂点であるときのみ、メモリ２００上の形態データリスト９０２にアクセスして該当頂点の形態データをロードする。該当頂点の変換済み座標データ９１０を変換座標バッファ１１０から受け取り、合わせて頂点データ９１１としてポリゴン描画処理部１０８へ出力する。
【０１３７】
ポリゴン描画処理部１０８は、頂点データ９１１を用いてポリゴン描画処理を行い、メモリ２００上の出力画像９０３を生成する。
【０１３８】
以上のように、入力ポリゴンモデルがポリゴンメッシュ形式で表現される場合であっても、ポリゴン描画処理に必要な場合にのみ、形態データがロードされる。これにより、全てのデータをロードする場合に比べてメモリアクセスを低減することができる。
【０１３９】
本実施の形態の画像生成装置及び画像生成方法によれば、入力ポリゴンモデルの頂点データのうち座標データ以外の形態データについては、頂点消去判定で頂点が有効と判断されたものについてのみ行われる。これにより、メモリからグラフィックス処理ユニットへの、入力ポリゴンモデルの頂点データのロードに関するメモリアクセス量を大幅に低減することができ、低メモリバンド幅の情報処理装置で入力ポリゴン数の多い高精細なポリゴン描画処理をリアルタイムで行うことができる。
【０１４０】
以上、本発明の画像生成装置及び画像生成方法について、実施の形態に基づいて説明したが、本発明は、この実施の形態に限定されるものではない。本発明の趣旨を逸脱しない限り、当業者が思いつく各種変形を実施の形態に施したものも本発明の範囲内に含まれる。
【０１４１】
例えば、入力ポリゴンモデルの表現形式についても、上記で示した形式の混在形式や四角形ストリップやラインストリップなど他の表現形式が含まれてもよい。
【０１４２】
なお、図１１のデータフローは、入力ポリゴンモデルがポリゴンメッシュ形式の場合のデータフローとして説明したが、ポリゴンストリップ形式やポリゴンファン形式、もしくはそれらの混在形式の場合でも同様のデータフローで処理をすることができる。
【０１４３】
また、ポリゴン消去判定部１０５は、クリッピング判定及びカリング判定を用いているが、描画オプションによってどちらか一方しか用いなくともよい。
【０１４４】
また、クリッピング判定として、３次元空間内の任意の平面を境界とした消去判定が含まれてもよいし、ディスプレイ面３０３上の任意の領域を境界とした消去判定が含まれてもよい。
【０１４５】
また、カリング判定として、ディスプレイ面３０３に投影したときに１ドットに満たないポリゴンの消去判定や、ビューボリューム３０２内の他のポリゴン描画によって視点３０１から全く見えなくなるポリゴンの消去判定が含まれてもよい。
【０１４６】
また、本実施の形態では、頂点消去判定部１０６は、判定対象の頂点Ｖｉが含まれるポリゴンの、ポリゴン描画有効フラグＦＰｊの論理和をとって頂点有効フラグＦＶｉを生成する方法を用いている。この方法には、ポリゴン消去判定部１０５から判定対象の頂点Ｖｉが含まれるポリゴンの、ポリゴン描画有効フラグＦＰｊが全て得られてから、頂点有効フラグＦＶｉを生成する方法と、上記ポリゴン描画有効フラグＦＰｊを逐次頂点有効フラグＦＶｉの中間結果との論理和をとって更新し、論理和が偽から真になったときに頂点有効フラグＦＶｉを真として生成する方法がありうる。本実施の形態では、ポリゴンストリップ形式の頂点及びポリゴンファン形式の開始頂点以外頂点が前者の方法、ポリゴンファンの開始頂点及び上記ポリゴンメッシュの頂点が後者の方法に該当するが、入力ポリゴンモデルの表現形式に関わらずそのどちらを用いてもよい。
【０１４７】
また、ポリゴンメッシュ形式では、中間結果フラグが偽から真になった場合は、以降、頂点消去判定部１０６は、真である中間結果フラグを用いた論理和演算を行うことを停止してもよい。例えば、頂点消去判定バッファ１１１から、真となった中間結果フラグを削除することで、削除された中間結果フラグとポリゴン描画有効フラグとの論理和演算を行うことを停止することができる。
【０１４８】
例えば、図２の画像生成装置１００に含まれる座標データロード部１０３、座標変換部１０４などの各ブロックは一部又は全部を並列化してもよいし、複数のブロックを１つのブロックに統合してもよい。
【０１４９】
また、本発明は、図２の画像生成装置１００を含む情報処理装置として実現することができる。
【０１５０】
図１２は、図２の画像生成装置を含む情報処理装置の構成を示すブロック図である。同図に示す情報処理装置１０００は、集積回路１００１と、メモリ１００８と、ディスプレイ１００９とを備える。
【０１５１】
集積回路１００１は、例えば、システムＬＳＩなどであり、ＣＰＵ１００２と、グラフィックス処理ユニット１００３（図２の画像生成装置）と、メモリコントローラ１００４と、ディスプレイコントローラ１００５と、ＣＰＵバス１００６と、メモリバス１００７とを備える。
【０１５２】
ＣＰＵ１００２は、描画命令リスト２０２及び頂点データリスト２０３を、メモリバス１００７とメモリコントローラ１００４とを介してメモリ１００８に格納する。また、ＣＰＵバス１００６を介して描画の指示をグラフィックス処理ユニット１００３へ伝える。
【０１５３】
グラフィックス処理ユニット１００３は、メモリバス１００７とメモリコントローラ１００４とを介してメモリ１００８から描画命令リスト２０２及び頂点データリスト２０３にアクセスして、上述した画像生成処理を行う。生成した画像は、メモリバス１００７とメモリコントローラ１００４とを介してメモリ１００８に格納する。メモリ１００８に格納された生成画像は、ディスプレイコントローラ１００５を介してディスプレイ１００９へと出力される。
【０１５４】
なお、ＣＰＵ１００２による、頂点データリスト２０３のメモリ１００８への格納については、頂点データリスト２０３を、必ずロードされる座標データリスト２０５と、頂点消去判定結果によってはロードされない形態データリスト２０６とへ分割してそれぞれ別のメモリ領域に格納してもよい。これにより、メモリバス１００７およびメモリコントローラ１００４がバーストメモリアクセスによりメモリ１００８上の頂点データリスト２０３をロードする場合に、座標データとともに不要と判定された形態データまでロードしてしまうことを防ぐことができ、メモリアクセス効率を高めることができる。
【０１５５】
また、図１１の集積回路１００１のＣＰＵ１００２、グラフィックス処理ユニット１００３などの各機能ブロックは個別に集積回路化してもよいし、一部又は全部を含むように１つの集積回路としてもよい。集積回路１００１には、ＡＶ（Ａｕｄｉｏ  Ｖｉｓｕａｌ）処理ユニットやストリーミング処理ユニットなど他の機能ブロックが含んでいてもよい。メモリ１００８は、集積回路１００１の内部に搭載してもよいし、集積回路１００１の内部、外部を問わず複数個搭載してもよい。
【０１５６】
また、本実施の形態では、画像生成装置を集積回路として実施した例を示したが、汎用プロセッサー上のプログラムによって実現してもよいし、製造後にハードウェア構成を変更することが可能なＦＰＧＡ（Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）や集積回路内部の回路セルの接続や設定を再構成可能なリコンフィギュラブル・プロセッサーを利用して実現してもよい。
【０１５７】
また、本発明は、上記のプログラムを記録したコンピュータ読み取り可能なＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ−Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）などの記録媒体として実現したり、そのプログラムを示す情報、データ又は信号として実現したりすることもできる。そして、それらプログラム、情報、データ及び信号は、インターネット等の通信ネットワークを介して配信してもよい。
【産業上の利用可能性】
【０１５８】
本発明の画像生成方法及び画像生成装置は、グラフィックス描画機能を搭載する様々な電子機器、例えば、携帯電話、ＰＤＡ（Ｐｅｒｓｏｎａｌ  Ｄｉｇｉｔａｌ  Ａｓｓｉｓｔａｎｔ）、デジタルテレビ、カーナビゲーションシステム、家庭用ゲーム機、パーソナルコンピュータ等において用いることができる。
【符号の説明】
【０１５９】
１００  画像生成装置
１０１  ホストインターフェース
１０２  制御部
１０３  座標データロード部
１０４  座標変換部
１０５  ポリゴン消去判定部
１０６  頂点消去判定部
１０７  形態データロード部
１０８  ポリゴン描画処理部
１０９  メモリインターフェース
１１０  変換座標バッファ
１１１  頂点消去判定バッファ
２００、１００８  メモリ
２０１  入力データ
２０２  描画命令リスト
２０３  頂点データリスト
２０４  描画命令
２０５、５０１、７０１、９０１  座標データリスト
２０６、５０２、７０２、９０２  形態データリスト
２０７、５０４、７０４、９０４  座標データ
２０８  形態データ
３０１  視点
３０２  ビューボリューム
３０３  ディスプレイ面
３０４、３０５、３０６  ポリゴン
４０１  ポリゴンストリップ
４０２、６０２、８０２  タイムチャート
５０３、７０３、９０３  出力画像
５０５、５０６、５１０、７０５、７０６、７０７、７１２、９０５、９０６、９１０  変換済み座標データ
５０７、５０８、７０８、７１０、９０７  ポリゴン描画有効フラグ
５０９、７１１、９０９  頂点有効フラグ
５１１、７１３、９１１  頂点データ
６０１  ポリゴンファン
７０９、９０８  中間結果フラグ
８０１  ポリゴンメッシュ
１０００  情報処理装置
１００１  集積回路
１００２  ＣＰＵ
１００３  グラフィックス処理ユニット
１００４  メモリコントローラ
１００５  ディスプレイコントローラ
１００６  ＣＰＵバス
１００７  メモリバス
１００９  ディスプレイ
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ポリゴンを描画することでコンピュータグラフィックス画像を生成する画像生成装置であって、
ポリゴンを構成する頂点の情報を示す頂点データのうち、前記頂点の位置を示す座標データをロードする座標データロード手段と、
前記座標データロード手段によりロードされた前記座標データを異なる座標系に変換する座標変換手段と、
前記座標変換手段により変換されて得られる変換済み座標データを用いて前記ポリゴンが描画の対象であるか否かを判定することで、前記ポリゴンを構成する頂点が有効であるか否かを判定する判定手段と、
前記判定手段により有効と判定された頂点のみに対応する前記頂点データのうち前記座標データ以外の情報を示す形態データをロードする形態データロード手段と、
前記形態データロード手段によりロードされた形態データと前記変換済み座標データとを用いてポリゴンを描画するポリゴン描画手段とを備える
ことを特徴とする画像生成装置。
【請求項２】
前記座標変換手段による座標変換と、前記判定手段によるポリゴン判定及び頂点判定とは、前記座標データが１つロードされるたびにパイプラインで処理される
ことを特徴とする請求項１記載の画像生成装置。
【請求項３】
前記判定手段は、
前記変換済み座標データを用いて前記ポリゴンが描画の対象であるか否かを判定し、前記ポリゴンが描画の対象であるか否かを示すポリゴン有効フラグを出力するポリゴン判定部と、
共有の頂点を含む複数のポリゴンの、ポリゴン有効フラグの論理和演算を行うことで、前記頂点が有効であるか否かを判定する頂点判定部とを有する
ことを特徴とする請求項１記載の画像生成装置。
【請求項４】
前記画像生成装置は、さらに、
頂点が無効であることを示すように予め設定された中間結果フラグを保持する第１バッファを備え、
前記判定手段は、
前記変換済み座標データを用いて前記ポリゴンが描画の対象であるか否かを判定し、前記ポリゴンが描画の対象であるか否かを示すポリゴン有効フラグを出力するポリゴン判定部と、
前記ポリゴン有効フラグと、前記ポリゴン有効フラグに対応するポリゴンを構成する頂点の前記中間結果フラグとの論理和演算を行い、前記第１バッファに保持される中間結果フラグを更新することで、前記頂点が有効であるか否かを判定する頂点判定部とを有する
ことを特徴とする請求項１記載の画像生成装置。
【請求項５】
前記頂点判定部は、前記中間結果フラグと前記ポリゴン有効フラグとの論理和演算を行うことで、前記中間結果フラグの値が変更した場合に、頂点が有効であることを示す頂点有効フラグを出力し、
前記形態データロード手段は、前記頂点有効フラグを受け取ったときに、前記頂点有効フラグに対応する前記形態データをロードする
ことを特徴とする請求項４記載の画像生成装置。
【請求項６】
前記頂点判定部は、さらに、前記中間結果フラグの値が変更した場合、当該中間結果フラグを用いる論理和演算を行うことを停止する
ことを特徴とする請求項５記載の画像生成装置。
【請求項７】
前記座標データロード手段は、前記複数の座標データのみを格納する領域から前記座標データをロードし、
前記形態データロード手段は、前記複数の形態データのみを格納する領域から前記形態データをロードする
ことを特徴とする請求項１記載の画像生成装置。
【請求項８】
前記座標変換手段は、前記座標データをワールド座標系及びディスプレイ座標系に変換し、
前記判定手段は、前記ワールド座標系に変換された変換済み座標データを用いて実行されるクリッピング判定、及び、前記ディスプレイ座標系に変換された変換済み座標データを用いて実行されるカリング判定の少なくとも１つを行うことで、前記ポリゴンが有効であるか否かを判定し、有効であると判定されたポリゴンを構成する頂点を有効であると判定する
ことを特徴とする請求項１記載の画像生成装置。
【請求項９】
ポリゴンを描画することでコンピュータグラフィックス画像を生成する画像生成方法であって、
ポリゴンを構成する頂点の情報を示す頂点データのうち、前記頂点の位置を示す座標データをロードする座標データロードステップと、
前記座標データロードステップでロードされた前記座標データを異なる座標系に変換する座標変換ステップと、
前記座標変換ステップで変換されて得られる変換済み座標データを用いて前記ポリゴンが描画の対象であるか否かを判定することで、前記ポリゴンを構成する頂点が有効であるか否かを判定する判定ステップと、
前記判定ステップで有効と判定された頂点のみに対応する前記頂点データのうち前記座標データ以外の情報を示す形態データをロードする形態データロードステップと、
前記形態データロードステップでロードされた形態データと前記変換済み座標データとを用いてポリゴンを描画するポリゴン描画ステップとを含む
ことを特徴とする画像生成方法。
【請求項１０】
ポリゴンを描画することでコンピュータグラフィックス画像を生成する集積回路であって、
ポリゴンを構成する頂点の情報を示す頂点データのうち、前記頂点の位置を示す座標データをロードする座標データロード手段と、
前記座標データロード手段によりロードされた前記座標データを異なる座標系に変換する座標変換手段と、
前記座標変換手段により変換されて得られる変換済み座標データを用いて前記ポリゴンが描画の対象であるか否かを判定することで、前記ポリゴンを構成する頂点が有効であるか否かを判定する判定手段と、
前記判定手段により有効と判定された頂点のみに対応する前記頂点データのうち前記座標データ以外の情報を示す形態データをロードする形態データロード手段と、
前記形態データロード手段によりロードされた形態データと前記変換済み座標データとを用いてポリゴンを描画するポリゴン描画手段とを備える
ことを特徴とする集積回路。
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】全図
【補正方法】変更
【補正の内容】
【図１】
2008126392.tif 000015
【図２】
2008126392.tif 000016
【図３】
2008126392.tif 000017
【図４】
2008126392.tif 000018
【図５】
2008126392.tif 000019
【図６】
2008126392.tif 000020
【図７】
2008126392.tif 000021
【図８】
2008126392.tif 000022
【図９】
2008126392.tif 000023
【図１０】
2008126392.tif 000024
【図１１】
2008126392.tif 000025
【図１２】
2008126392.tif 000026
【国際調査報告】
2008126392.tif 000027
2008126392.tif 000028