(57)【特許請求の範囲】
【請求項１】
汎用演算処理装置と、画像処理用演算処理装置と、を有する画像生成装置であって、
前記画像処理用演算処理装置は、画像を生成する画像生成手段を有し、
前記汎用演算処理装置は、
３次元画像を構成する複数の３次元オブジェクトの要素データの入力を受け付ける入力手段と、
入力された要素データを階層的に表したシーングラフを作成するシーングラフ作成手段と、
前記シーングラフを走査して、シーングラフのノードに割り当てられた要素データを、前記画像生成手段に出力する走査手段と、
を有し、
前記シーングラフ作成手段は、前記シーングラフを構成するノードに対して描画優先度を付加し、
前記走査手段は、ノードに付加された描画優先度が、所定の優先度以上である場合に、そのノードに割り当てられた要素データを前記画像生成手段に出力し、
前記所定の優先度は、決められた時間内に前記画像生成手段が画像生成処理を完了できるよう定められた値である
ことを特徴とする画像生成装置。
【請求項２】
３次元画像を構成する複数の３次元オブジェクトの要素データの入力を受け付ける入力手段と、
入力された要素データを階層的に表したシーングラフを作成するシーングラフ作成手段と、
前記シーングラフを走査して、シーングラフのノードに割り当てられた要素データを、画像生成手段に出力する走査手段と、
を有し、
前記シーングラフ作成手段は、前記シーングラフを構成するノードに対して描画優先度を付加し、
前記走査手段は、ノードに付加された描画優先度が、所定の優先度以上である場合に、そのノードに割り当てられた要素データを前記画像生成手段に出力し、
前記描画優先度は、他のオブジェクトとの関連性に基づいて決定される
ことを特徴とする画像生成装置。
【請求項３】
３次元画像を構成する複数の３次元オブジェクトの要素データの入力を受け付ける入力手段と、
入力された要素データを階層的に表したシーングラフを作成するシーングラフ作成手段と
前記シーングラフを走査して、シーングラフのノードに割り当てられた要素データを、画像生成手段に出力する走査手段と、
を有し、
前記走査手段は、前記画像生成手段に出力した要素データが有するデータ量を計測する計測手段を有し、前記画像生成手段に出力した要素データが有するデータ量が、所定の閾値を超えた場合は、それ以降に走査されたノードに割り当てられた要素データを前記画像生成手段に出力しない
ことを特徴とする画像生成装置。
【請求項４】
汎用演算処理装置と、画像処理用演算処理装置を有する情報処理装置が行う画像生成方法であって、
前記汎用演算処理装置が、３次元画像を構成する複数の３次元オブジェクトの要素データの入力を受け付けるステップと、
前記汎用演算処理装置が、入力された要素データを階層的に表したシーングラフであって、シーングラフを構成するノードに描画優先度が付加されたシーングラフを作成するステップと、
前記汎用演算処理装置が、作成されたシーングラフを走査して、ノードに付加された描画優先度が、所定の優先度以上である場合に、そのノードに割り当てられた要素データを、前記画像処理用演算処理装置に出力するステップと、
前記画像処理用演算処理装置が、要素データから画像を生成するステップと、
を含み、
前記所定の優先度は、決められた時間内に前記画像処理用演算処理装置による前記要素データから画像を生成するステップを完了できるよう定められた値である
ことを特徴とする画像生成方法。
【請求項５】
画像を生成する画像生成手段を有する情報処理装置が、
３次元画像を構成する複数の３次元オブジェクトの要素データの入力を受け付けるステップと、
入力された要素データを階層的に表したシーングラフであって、シーングラフを構成するノードに描画優先度が付加されたシーングラフを作成するステップと、
作成されたシーングラフを走査して、ノードに付加された描画優先度が、所定の優先度以上である場合に、そのノードに割り当てられた要素データを、前記画像生成手段に出力するステップと、
を含み、
前記描画優先度は、他のオブジェクトとの関連性に基づいて決定される
ことを特徴とする画像生成方法。
【請求項６】
画像を生成する画像生成手段を有する情報処理装置が、
３次元画像を構成する複数の３次元オブジェクトの要素データの入力を受け付けるステ
ップと、
入力された要素データを階層的に表したシーングラフを作成するステップと、
作成されたシーングラフを走査して、ノードに割り当てられた要素データを、前記画像生成手段に出力するステップと、
前記画像生成手段に出力した要素データが有するデータ量を計測するステップと、
を含み、
前記要素データを前記画像生成手段に出力するステップでは、前記画像生成手段に出力した要素データが有するデータ量が所定の閾値を超えた場合は、それ以降に走査されたノードに割り当てられた要素データを前記画像生成手段に出力しない
ことを特徴とする画像生成方法。
【請求項７】
汎用演算処理装置と、画像処理用演算処理装置を有する情報処理装置に、
前記汎用演算処理装置が、３次元画像を構成する複数の３次元オブジェクトの要素データの入力を受け付けるステップと、
前記汎用演算処理装置が、入力された要素データを階層的に表したシーングラフであって、シーングラフを構成するノードに描画優先度が付加されたシーングラフを作成するステップと、
前記汎用演算処理装置が、作成されたシーングラフを走査して、ノードに付加された描画優先度が、所定の優先度以上である場合に、そのノードに割り当てられた要素データを、前記画像処理用演算処理装置に出力するステップと、
を実行させる画像生成プログラムであって、
前記所定の優先度は、前記画像処理用演算処理装置による画像を生成する処理が決められた時間内に完了できるよう定められた値である
ことを特徴とする画像生成プログラム。
【請求項８】
画像を生成する画像生成手段を有する情報処理装置に、
３次元画像を構成する複数の３次元オブジェクトの要素データの入力を受け付けるステップと、
入力された要素データを階層的に表したシーングラフであって、シーングラフを構成するノードに描画優先度が付加されたシーングラフを作成するステップと、
作成されたシーングラフを走査して、ノードに付加された描画優先度が、所定の優先度以上である場合に、そのノードに割り当てられた要素データを、前記画像生成手段に出力するステップと、
を実行させる画像生成プログラムであって、
前記描画優先度は、他のオブジェクトとの関連性に基づいて決定される
ことを特徴とする画像生成プログラム。
【請求項９】
画像を生成する画像生成手段を有する情報処理装置に、
３次元画像を構成する複数の３次元オブジェクトの要素データの入力を受け付けるステップと、
入力された要素データを階層的に表したシーングラフを作成するステップと、
作成されたシーングラフを走査して、ノードに割り当てられた要素データを、前記画像生成手段に出力するステップと、
前記画像生成手段に出力した要素データが有するデータ量を計測するステップと、
を実行させる画像生成プログラムであって、
前記要素データを前記画像生成手段に出力するステップでは、前記画像生成手段に出力した要素データが有するデータ量が所定の閾値を超えた場合は、それ以降に走査されたノードに割り当てられた要素データを前記画像生成手段に出力しない
ことを特徴とする画像生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３次元コンピュータグラフィックスにおける画像生成技術に関する。
【背景技術】
【０００２】
３次元コンピュータグラフィックス（以下、３ＤＣＧという）は、仮想３次元空間において管理される３次元オブジェクトを、計算によってコンピュータのスクリーン平面に投影して描画を行う技術である。
【０００３】
３ＤＣＧでは多くの演算資源が必要となるため、最近ではＣＰＵ（中央演算処理装置）で全ての処理を行うのではなく、３ＤＣＧの描画処理を行うための専用のハードウェアであるＧＰＵ（Graphic Processor Unit）とＣＰＵとを併用して３ＤＣＧを描画している。
【０００４】
以下、３ＤＣＧの描画処理について簡単に説明する。なお、この描画処理はＣＰＵとＧＰＵによる流れ作業（パイプライン処理）で行われ、処理の機能別に５つのステージから構成される。図１２はパイプラインの構成を示す。ここでは、それぞれのステージの頭文字を取って、各ステージをＧ，Ｔ，Ｘ，Ｓ，Ｄと呼ぶ。以下、各ステージについて説明する。
【０００５】
Ｇ（Generation）：シーングラフの作成
まず、表示したい３次元オブジェクトのデータをファイル等から入力として受け取り、所定のデータ構造にしたがってメモリ上に構築（あるいは更新）する。このデータ構造はモデルを階層的にグループ化した木構造であることが一般的で、このメモリ上のモデルデータはシーングラフと呼ばれる。シーングラフの作成は、ＣＰＵによって行われる。
【０００６】
Ｔ（Traversal）：表示データの抽出
構築されたシーングラフを順番に走査して、３次元オブジェクトの画像データを以降のパイプラインに渡す。昨今のシステムでは、一般に、ここでＣＰＵからＧＰＵへ描画コマンドおよび頂点データが転送される。
【０００７】
Ｘ（Transformation, Xformation）：頂点変換
３次元モデルの座標を、２次元スクリーン座標系に投影する座標変換処理を行う。Ｘステージでは、座標変換に加えて各頂点の明るさも計算する。ＸステージはＧＰＵによって行われることが一般的である。
【０００８】
Ｓ（Scan conversion）：塗りつぶし
スクリーン座標に投影された３次元オブジェクトの頂点の内部に存在する画素に対して、画素値（色）および明るさを計算する。また、３次元オブジェクトごとに奥行きも計算し、最終的に一番手前となるオブジェクトが表示されるようにする。計算結果は、フレームメモリ上に画像データとして書き込まれる。Ｓステージは、ＧＰＵによって行われることが一般的である。
【０００９】
Ｄ（Display）：描画
フレームメモリ上の画像データを読み出し、ビデオ信号としてディスプレイ装置などに対して出力する。
【００１０】
このようなシーングラフを用いてパイプライン処理で３ＤＣＧの描画を行う際に、次のような拡張が提案されている（特許文献１）。特許文献１では、画面奥に位置するオブジ
ェクトから順番に描画する処理を高速化するために、ノードに描画順序を表すデータを付与したシーングラフを用いて、シーングラフのトラバース量を減らしている。
【特許文献１】特開２００５−２５０７９９号公報
【非特許文献１】柿本正憲，「グラフィックス・ハードウェア  ＯｐｅｎＧＬアーキテクチャの基礎」，可視化情報学会講習会「可視化フロンティア」，ｐｐ．７２−９４，ＩＳＢＮ４−９０６４９７−２８−４，２００４年
【発明の開示】
【発明が解決しようとする課題】
【００１１】
しかしながら、上記のような従来技術の場合には、下記のような問題が生じていた。すなわち、ＣＰＵで行われる処理がＧ，Ｔステージまでで、Ｘ，Ｓ，ＤステージがＧＰＵによって実行される場合、実際に３ＤＣＧが描画されるまでにどれだけの時間がかかるかをＣＰＵ側のソフトウェアによって制御できない。
【００１２】
一方、３ＤＣＧの描画処理においても、決められた時間内に描画結果を得ることが要求される場合がある。このようにリアルタイムでの表示が要求されるシステムにおいては、シーングラフに格納されている全てのオブジェクトを描画しようとすると、リアルタイム表示に間に合わない場合があるという問題がある。
【００１３】
本発明は上記実情に鑑みてなされたものであって、その目的とするところは、リアルタイム要求を満足できる画像生成のための技術を提供することにある。
【課題を解決するための手段】
【００１４】
上記目的を達成するために本発明では、以下の手段または処理によって３次元画像の生成を行う。
【００１５】
本発明の第一の態様は、画像生成装置であって、入力手段、シーングラフ作成手段および走査手段を有する。
【００１６】
入力手段は、３次元画像を構成する複数の３次元オブジェクトの要素データの入力を受け付ける。
【００１７】
シーングラフ作成手段は、入力された３次元オブジェクトの要素データからシーングラフを作成する。シーングラフは、３次元オブジェクトの要素データを元に階層的にグループ化されたデータ構造である。このデータ構造の階層は、木構造によって表されることが好適である。シーングラフの各ノードには、３次元オブジェクトの要素データが格納される。なお、３次元オブジェクトの要素データには、オブジェクトの頂点座標を示す形状データや、オブジェクトの色・質感・透明度などを表す属性情報が含まれる。
【００１８】
走査手段は、シーングラフを走査して、ノードに割り当てられた要素データを、画像を生成する画像生成手段へと出力する。このようにして画像生成手段に出力された要素データを元に、画像生成手段が画像生成処理を行うことで、３次元画像が生成される。
【００１９】
ここで、本発明の第一の態様におけるシーングラフ作成手段は、シーングラフを構成するノードに対して描画優先度を設定してシーングラフを作成する。そして、走査手段は、ノードに設定された描画優先度が、所定の優先度以上である場合に、そのノードに割り当てられた要素データを、画像生成手段に出力する。すなわち、ノードに設定された描画優先度が所定の優先度以上であればそのノードのオブジェクトを描画し、所定の優先度よりも低い場合にはそのノードのオブジェクトを描画しない。
【００２０】
このように、シーングラフのノードに描画優先度を設定し、所定の優先度以上のノードのオブジェクトのみを描画することによって、描画処理の量を制御し、リアルタイム要求を満たすことが可能となる。
【００２１】
また、本発明の第二の態様は、画像生成装置であって、入力手段、シーングラフ作成手段および走査手段を有する。第一の態様と同様に、入力手段は３次元画像を構成する複数の３次元オブジェクトの要素データの入力を受け付け、シーングラフ作成手段が、入力された３次元オブジェクトの要素データからシーングラフを作成する。そして、走査手段が、シーングラフを走査して、ノードに割り当てられた３次元オブジェクトの要素データを、画像生成手段に出力することで画像を生成する。
【００２２】
ここで、本発明の第二の態様における走査手段は、画像生成手段に出力した要素データのデータ量を計測する計測手段を有し、画像生成手段に出力したデータ量が所定の閾値を超えた場合は、それ以降に走査されたノードに割り当てられた要素データを画像生成手段に出力しない。
【００２３】
このように、所定のデータ量以上の描画が行われた場合には、それ以上の描画を行わないように描画するデータ量を制限することで、リアルタイム要求を満たすことが可能となる。
【００２４】
なお、本発明は、上記処理の少なくとも一部を含む画像生成方法、または、かかる方法を実現するためのプログラムとして捉えることもできる。上記手段および処理の各々は可能な限り互いに組み合わせて本発明を構成することができる。
【発明の効果】
【００２５】
本発明によれば、リアルタイム要求を満足する画像生成が可能となる。
【発明を実施するための最良の形態】
【００２６】
以下に図面を参照して、この発明の好適な実施の形態を例示的に詳しく説明する。
【００２７】
（第１の実施形態）
＜概要＞
図１は、本実施形態に係る画像生成装置のハードウェア構成を示す図である。画像生成装置１は、ＣＰＵ１０，ＲＡＭなどの主記憶装置１１，ハードディスク装置等の補助記憶装置１２，グラフィックボード１３を有し、ディスプレイなどの出力装置２が接続されている。グラフィックボード１３は、ＧＰＵ１３１とフレームメモリ１３２から構成される。画像生成装置１は、補助記憶装置１２等からデータ入力があり、ＣＰＵ１０が主記憶装置１１上にロードされたアプリケーションプログラムを実行し、画像処理のためのデータをＧＰＵ１３１に送る。ＧＰＵ１３１がフレームメモリ１３２に画像データを書き込むことで、出力装置２に画像が表示される。
【００２８】
図２は、本実施形態に係る画像生成装置１の機能ブロックを示す図である。画像生成装置１の機能は、入力部３，シーングラフ作成部４，走査部５，画像生成部６から構成される。
【００２９】
入力部３は、３次元モデルのデータを受け付ける。３次元モデルのデータは、３次元画像を構成する複数の３次元オブジェクトの要素データから構成される。入力部３は、ハードディスク装置やＣＤ−ＲＯＭなどの外部記憶装置からＣＰＵがデータを読み出すことで実現されても良い。また、入力部３は、ＬＡＮやインターネットなどのネットワークからＣＰＵがデータを受信することで実現されても良い。
【００３０】
シーングラフ作成部４は、入力された３次元モデルデータから、階層構造を有するシーングラフを主記憶装置１１上に構築する。走査部５は、シーングラフを走査して、ノードに対応する描画コマンドや要素データを画像生成部６に送る。シーングラフ作成部４および走査部５は、ＣＰＵ１０がアプリケーションプログラムを実行することによって実現される。シーングラフ作成部４および走査部５の詳細については後述する。
【００３１】
画像生成部６は、走査部５から送られた描画コマンドおよび要素データに基づいてレンダリング処理を行う。具体的には、座標変換処理（Ｘ）、塗りつぶし処理（Ｓ）、表示処理（Ｄ）を行うことによって、フレームメモリ１３２に画像データを書き込む。フレームメモリ１３２に書き込まれた画像データは出力装置２によって表示される。画像生成部６の処理は、ＧＰＵ１３１によって実行される。
【００３２】
＜シーングラフ＞
次に、シーングラフ作成部４が作成するシーングラフについて説明する。図３は、シーングラフの構造の一例を示す図である。このシーングラフは、自動車のモデルを表現したものである。図３のように、シーングラフは３次元オブジェクトを階層的にグループ化した木構造を有するデータ構造であることが一般的である。シーングラフの各ノードには、各オブジェクトの形状や表面属性、モデル変換（位置、姿勢、拡大縮小）に関する情報（要素データ）が含まれている。
【００３３】
図３では、自動車はボディ、シャシー、エンジンを有することが示されている。さらに、ボディはドア、フロントガラス、バンパーを有することが示されている。また、シャシーは２つの車軸を有し、各車軸は２つタイヤを有することが示されている。
【００３４】
ここで、各パーツの３次元位置は親ノードに対して相対的に表現される。パーツの位置は行列演算によって計算することができるので、シーングラフを走査する際にこの行列演算を行いつつ走査することによって、各パーツの位置を効率的に求めることができる。
【００３５】
なお、入力された３次元モデルデータの全てをシーングラフとして構築する必要はなく、スクリーン座標に投影したときに出力画像外に位置するオブジェクトはシーングラフから取り除いて構わない。このように表示に関係しないオブジェクト（ノード）を削除する処理は、カリング処理と呼ばれ、高速化の手法の一つである。
【００３６】
本実施形態におけるシーングラフ作成部４は、各ノードに対して形状データ、表面属性データだけでなく、描画優先度に関する情報を付加してシーングラフを作成する。各ノード（オブジェクト）に対する描画優先度は、入力される３次元画像データ中に格納されていても良い。また、各ノードに対する描画優先度は、シーングラフ作成部４が他のオブジェクトとの関連性に基づいて決定しても良い。図４、図５は、描画優先度を付加したシーングラフの例を示す図である。図４は、全てのノードに明示的に描画優先度を付加した例である。なお、本実施形態では、描画優先度はその値が小さいほど優先度が高いことを意味する。図５は、ノードに描画優先度が付加されていない場合には、そのノードの親ノードの描画優先度を継承するという規則を導入した場合のシーングラフの例である。図５において、描画優先度が括弧内に表示されているノードは、描画優先度を親ノードから継承していることを示す。
【００３７】
このように、描画優先度は各ノードに対応づけられていれば具体的にはどのようにノードに対して付加されても構わない。
【００３８】
＜トラバース（走査）＞
図６は、シーングラフをトラバースする処理を説明する図である。図６において、ノードの横に示された番号は、トラバースされる順序を示す番号である。このように、シーングラフのトラバースは、深さ優先で行う。すなわち、ノードが子ノードを有する場合には、子ノードを走査し、全ての子ノードに対して走査が終わってから、兄弟ノードを走査する。
【００３９】
走査部５は、上記のようにシーングラフを走査して、３ＤＣＧライブラリを介して、各ノードに対応するオブジェクトの画像データを画像生成部６に出力する。シーングラフに対応した３ＤＣＧライブラリとしては、ＳＧＩ社のOpen Inventor（登録商標）や、Sun Microsystems社のJava（登録商標）3Dが挙げられる。このようにして、画像生成装置１は
画像を生成する。
【００４０】
ここで、走査部５は、決められた時間内に描画処理を完了できるように、特定のオブジェクトのみを描画する。まず、走査部５は、シーングラフの走査の際に、優先度を設定される。そして、シーングラフの走査中に、ノードに付加された描画優先度と、指定された優先度を比較して、ノードに付加された描画優先度が指定された優先度と同じか優先度が高ければ、そのノードに割り当てられた３次元オブジェクトの要素データを画像生成部６に送る。逆に、ノードに付加された描画優先度が、指定された優先度よりも低い場合には、そのノードに割り与えられた要素データを画像生成部６に出力しない。
【００４１】
なお、走査部５から画像生成部６への要素データの出力には、オブジェクトの描画を行うコマンドの出力と、描画属性を変更するコマンドの出力とが存在する。本実施形態において、ノードが有する描画優先度が所定の優先度より低い場合には、描画を行うコマンドの出力のみを抑制することが好ましい。描画属性の変更は、次のノードの描画の際に引き継がれるものであるため、描画属性変更コマンドの出力まで抑制した場合には、意図したとおりの画像が生成されなくなってしまうためである。
【００４２】
＜動作例＞
図７は、画像生成装置１の動作例を示すフローチャートである。以下、図７を用いて画像生成装置１の動作例について説明する。まず、画像生成装置１は、入力部３を介して、処理の対象となる３次元画像データを読み込む（Ｓ１０）。次に、シーングラフ作成部４が、シーングラフを主記憶装置１１上に構築する（Ｓ１１）。この際、入力された３次元画像データを構成する各３次元オブジェクトの描画優先度を、シーングラフの各ノードに対して付加する。すなわち、シーングラフ作成部４は、図４に示すような各ノードに対して描画優先度が付加されたシーングラフを作成する。
【００４３】
次に、走査部５がシーングラフを走査する際に、描画判定の閾値となる優先度が設定される（Ｓ１２）。ここでは、優先度として「３」（値が小さいほど優先度が高い）が指定されたとする。そして、走査部５は、シーングラフの走査を行う（Ｓ１３）。走査部５が、シーングラフのノードに到達したときに、そのノードに付加された描画優先度が、Ｓ１２で走査部５に指定された優先度以上であるか判定する（Ｓ１４）。ノードに付加された描画優先度が、指定された優先度以上である場合（Ｓ１４−ＹＥＳ）には、そのノードの要素データを処理するコマンドをライブラリを介して画像生成部６に出力する（Ｓ１５）。ノードに付加された描画優先度が、指定された優先度よりも低い場合には（Ｓ１４−ＮＯ）には、そのノードに対する処理は行われない。そして、全てのノードの走査が終了したか判定し（Ｓ１６）、終了していない場合にはＳ１３に進みシーングラフの走査を続行する。
【００４４】
図８は、走査部５が行う走査処理の具体例を説明する図である。なお、図８では、走査部５に指定された優先度が「３」である場合を例にとって説明する。図８には、各ノード
に付加された描画優先度が示されている。
【００４５】
ノード８１には描画優先度として「２」が設定されており、これは走査部５に指定された優先度「３」よりも高いので、ノード８１の要素データは画像生成部６に出力される。すなわち、ノード８１は描画される。ノード８２の描画優先度は「３」であり、指定された優先度「３」と同じであるため、ノード８２も描画される。同様に、ノード８３も描画される。ノード８４は、描画優先度が「５」であり、指定された優先度「３」よりも低いため、ノード８４は描画されない。
【００４６】
このように、優先度に基づいて、それぞれのノードを描画するか否かを判定しつつ、走査部５がシーングラフの走査を行う。図８において、黒く塗りつぶされているノードが描画の対象となるノードである。
【００４７】
＜実施形態の効果＞
このように、走査部５がシーングラフを走査して３次元オブジェクトの要素データを画像生成部６に出力する際に、所定の優先度以上のノードのみを出力の対象とすることで、描画するデータ量をＣＰＵ側で制御することが可能となる。すなわち、リアルタイム表示要求の程度に応じた優先度を用いて走査を行うことで、リアルタイム要求を満たしつつ３ＤＣＧの描画を行うことが可能となる。
【００４８】
（第２の実施形態）
次に、本発明の第２の実施形態について説明する。第２の実施形態は第１の実施形態と基本的に同様であるため、主に異なる部分についてのみ説明する。
【００４９】
図９は、第２の実施形態に係る画像生成装置１の機能ブロックを示す図である。第１の実施形態との違いは、走査部５が、データ量計測部５１を有する点である。データ量計測部５１は、走査部５が画像生成部６に対して出力した要素データのデータ量を計測する。ここで要素データの量として、３次元オブジェクトの数が用いられても良く、３次元オブジェクトが有する頂点の数が用いられても良い。
【００５０】
本実施形態においては、シーングラフ作成部４は、シーングラフの各ノードに優先度を付加せずにシーングラフを作成する。走査部５は、シーングラフを走査して、各ノードの要素データを画像生成部６に出力する。この際、データ量計測部５１は、画像生成部６に出力した要素データのデータ量をカウント（計測）していく。そして、画像生成部６に出力したデータ量が所定の閾値を超えた場合には、それ以降は画像生成部６に対して要素データを出力しない。
【００５１】
図１０は、画像生成装置１の動作例を示すフローチャートである。まず、画像生成装置１は、３次元画像データを読み込む（Ｓ２０）。次に、シーングラフ作成部４が、シーングラフを主記憶装置１１上に構築する（Ｓ２１）。
【００５２】
そして、データ量計測部５１のデータ量カウンタをリセット（０に初期化）する（Ｓ２２）。また、走査部５に対して、最大描画データ量を設定する（Ｓ２３）。ここでは最大描画データ量として、頂点数１００が指定されたとする。
【００５３】
走査部５は、シーングラフの走査を行い（Ｓ２４）、各ノードに割り当てられた要素データを画像生成部６に出力する（Ｓ２５）。この際、データ量計測部５１は、画像生成部６に出力した要素データのデータ量（ここでは頂点数）を、データ量カウンタに足し込む（Ｓ２６）。そして、データ量カウンタが、Ｓ２３で設定された最大描画データ量を超えたか否か判定し（Ｓ２７）、最大描画データ量を超えている場合（Ｓ２７−ＹＥＳ）には
、画像生成処理を終了する。データ量カウンタが最大描画データ量を超えていない場合（Ｓ２７−ＮＯ）には、Ｓ２８に進みシーングラフの全ノードを走査したか否か判定し、終了していない場合にはＳ２４に進みシーングラフの走査を続行する。
【００５４】
このように、本実施形態においては、描画する３次元オブジェクトのデータ量が所定の値を超えた場合には、それ以降の描画を抑制することでリアルタイム要求を満足することが可能となる。
【００５５】
（第３の実施形態）
本発明の第３の実施形態は、走査部５が、各ノードの優先度と描画データ量の両方に基づいて、描画するノードを決定する。すなわち、第３の実施形態は、上記の第１および第２の実施形態を組み合わせたものである。
【００５６】
図１１は、本実施形態における画像生成装置１の動作例を示すフローチャートである。まず、画像生成装置１は、入力部３を介して、処理の対象とする３次元画像データを読み込む（Ｓ３０）。次に、シーングラフ作成部４が、シーングラフを主記憶装置１１上に構築する（Ｓ３１）。この際、入力された３次元画像を構成する各３次元オブジェクトの描画優先度を、シーングラフの各ノードに対して付加する。
【００５７】
次に、走査部５がシーングラフを走査する際に描画判定の閾値となる優先度が設定される（Ｓ３２）。また、データ量計測部５１のデータ量カウンタをリセット（０に初期化）し、走査部５に対して最大描画データ量が設定される（Ｓ３２）。
【００５８】
そして、走査部５がシーングラフの走査を行う（Ｓ３３）。走査部５が、シーングラフのノードに到達したときに、そのノードに付加された描画優先度が、Ｓ３２で走査部５に設定された優先度以上であるか否かを判定する（Ｓ３４）。そのノードに付加された描画優先度が、設定された優先度以上である場合（Ｓ３４−ＹＥＳ）は、そのノードの割り当てられた要素データを処理するコマンドをライブラリを介して画像生成部６に出力する（Ｓ３５）。この際、データ量計測部５１は、画像生成部６に出力した要素データのデータ量を、データ量カウンタに足し込む（Ｓ３６）。そして、データ量カウンタが、Ｓ３２で設定された最大描画データ量を超えたか否かを判定し（Ｓ３７）、最大描画データ量を超えている場合（Ｓ３７−ＹＥＳ）には、画像生成処理を終了する。データ量カウンタが最大描画データ量を超えていない場合（Ｓ３７−ＮＯ）には、Ｓ３８に進みシーングラフの全ノードを走査したか否か判定し、終了していない場合にはＳ３３に進みシーングラフの走査を続行する。
【００５９】
このように、本実施形態では、所定の優先度以上のノードに対してのみ描画処理を行い、さらに実際に描画したデータの量を計測し所定のデータ量以上の描画を行わないことで、リアルタイム表示に対する要求をより確実に満足することが可能となる。
【図面の簡単な説明】
【００６０】
【図１】第１の実施形態に係る画像生成装置のハードウェア構成を示す図である。
【図２】第１の実施形態に係る画像生成装置の機能ブロックを示す図である。
【図３】シーングラフを模式的に示した図である。
【図４】描画優先度を付加したシーングラフの例を示す図である。
【図５】描画優先度を付加したシーングラフの例を示す図である。
【図６】シーングラフを走査（トラバース）する処理を示す図である。
【図７】第１の実施形態における画像生成処理の流れを示すフローチャートである。
【図８】第１の実施形態における走査処理を説明する図である。
【図９】第２の実施形態に係る画像生成装置の機能ブロックを示す図である。
【図１０】第２の実施形態における画像生成処理の流れを示すフローチャートである。
【図１１】第３の実施形態における画像生成処理の流れを示すフローチャートである。
【図１２】従来技術による画像描画処理のパイプライン処理を説明する図である。
【符号の説明】
【００６１】
１      画像生成装置
２      出力装置
３      入力部
４      シーングラフ作成部
５      走査部
５１    データ量計測部
６      画像生成部
１０    ＣＰＵ
１１    主記憶装置
１２    補助記憶装置
１３    グラフィックボード
１３１  ＧＰＵ
１３２  フレームメモリ
【図１】
0004847226.tif 000002
【図２】
0004847226.tif 000003
【図３】
0004847226.tif 000004
【図４】
0004847226.tif 000005
【図５】
0004847226.tif 000006
【図６】
0004847226.tif 000007
【図７】
0004847226.tif 000008
【図８】
0004847226.tif 000009
【図９】
0004847226.tif 000010
【図１０】
0004847226.tif 000011
【図１１】
0004847226.tif 000012
【図１２】
0004847226.tif 000013