図面 (/)

技術 画像表示装置

出願人 三菱電機株式会社
発明者 櫻井智史
出願日 2010年2月23日 (11年3ヶ月経過) 出願番号 2012-501514
公開日 2013年6月17日 (7年11ヶ月経過) 公開番号 WO2011-104746
状態 特許登録済
技術分野 イメージ処理・作成 イメージ生成
主要キーワード モデル分割 幾何学的形 読込命令 保存単位 実行時処理 幾何学的距離 頂点インデックス 幾何学情報
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2013年6月17日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (20)

課題・解決手段

DD2により保存されている複数の分割データの中から、読込命令が示す分割データを読み込んで、その分割データをHDD2より高速に読み書きが可能なメモリ4に展開するデータ展開部31と、分割されたポリゴンモデル毎に、仮想空間内視点を考慮して、当該ポリゴンモデルに対する描画の詳細度を決定する詳細度決定部32と、メモリ4に展開されている分割データを参照して、詳細度決定部32により決定された詳細度に対応する頂点の数を有するポリゴンモデルを構築するとともに、読込対象の分割データを示す読込命令をデータ展開部31に出力するポリゴンモデル構築部33とを設ける。

概要

背景

コンピュータグラフィックスを用いて、インタラクティブアプリケーション構築するには、表示装置が画像をリアルタイムに表示して、その画像を利用者提示する必要がある。
利用者に提示される画像としては、コンピュータ内に記録されている画像のほか、その記録されている画像がコンピュータによって加工された加工画像や、記録された情報を用いて、コンピュータによって内部的に描画された画像などがある。

特に、3次元的な仮想空間内仮想物体を配置している環境(仮想環境)をコンピュータ内に構築し、コンピュータが、仮想視点から見た場合の仮想環境を描画して表示するには、仮想環境の3次元的な幾何学的形状や色などの多くの情報を用いて、投影処理などの複雑な処理をリアルタイムに行う必要がある。
しかし、描画される環境が複雑な場合や、コンピュータの処理性能が高くない場合には、上記の処理をリアルタイムに行うことは困難である。
なお、コンピュータ内の3次元仮想空間表現するデータ形式としては様々なものがあるが、ここでは、描画対象となる仮想物体や環境は、仮想空間内で互いに異なる位置にある3点を結んだ面で表される三角形ポリゴンで構成されるものとする。

従来の画像表示装置では、複雑な3次元仮想環境高速に描画する際に、LOD(Level Of Detail)技術が用いられている。
LOD技術は、描画対象となる3次元仮想環境を表す情報の一部を削減又は単純化することで、描画時間を短縮する技術である。

例えば、以下の特許文献1に開示されているLOD技術は、次のようなものである。
まず、表示対象物体を表すオリジナルポリゴンモデルを簡略化し、オリジナルのポリゴンモデルと一緒に簡略化したポリゴンモデルを補助記憶装置に記録する。
次に、表示対象の物体を描画する際、その描画結果に対する各モデル視覚的な寄与度予測し、ある閾値よりも寄与度が高いモデルについては、補助記憶装置からオリジナルのポリゴンモデルをメモリにロードして描画を行う。
一方、ある閾値よりも寄与度が低いモデルについては、補助記憶装置から簡略化したポリゴンモデルをメモリにロードして描画を行うことで、メモリの消費量と描画時間を節約している。

このようにして、オリジナルのポリゴンモデル又は簡略化したポリゴンモデルを適宜選択して描画を行う場合には、次のような不具合が発生することがある。
例えば、視点の移動などによって、オリジナルのポリゴンモデルと簡略化したポリゴンモデルの入れ替えが発生するとき、オリジナルのポリゴンモデルと簡略化したポリゴンモデルの形状が大きく異なっていると、ポリゴンモデルの変化が顕著に現れて、不自然さが目立ってしまうことがある。

このとき、ポリゴンモデルを選択する際の寄与度に関する閾値を高く設定すれば、上記の不自然さを緩和することができるが、オリジナルのポリゴンモデルを利用する割合が増えるため、描画の高速化やメモリ量の削減効果が減少することになる。
また、簡略化のレベルが異なる複数のポリゴンモデルを補助記憶装置に記録し、複数の閾値に応じて複数のポリゴンモデルを入れ替えるようにすれば、上記の不自然さを緩和することができるが、補助記憶装置に記録するポリゴンモデルのデータの量が大きく増加することになる。また、補助記憶装置に対するアクセス回数も大きく増えて、ボトルネックが発生することになる。

以下の非特許文献1には、特許文献1に開示されているLOD技術と異なる別のLOD技術として、View−Dependent Progressive Meshが開示されている。
View−Dependent Progressive Meshは、描画対象のポリゴンモデルのうち、描画結果に対して視覚的な寄与度が小さい部分のポリゴンの数を削減すると同時に、そのポリゴンの削減に伴う描画結果に与える影響が小さくなるように、残ったポリゴンの一部を変形するようにしている。これにより、描画結果である画像の品質を保ちつつ、描画の処理時間を短縮することができる。
また、ポリゴンの削減や、削減されたポリゴンの復元を1頂点単位で実行することができるため、常に必要最小限のポリゴン数で描画することができる。また、ポリゴン数の変化による描画対象の変形を目立ち難くすることができる。

しかし、View−Depent Progressive Meshの場合、描画対象のポリゴンモデルのモデル情報に加えて、ポリゴンの動的な増減に必要な情報を、高速に読み出しが可能なメモリなどの記憶装置に記録しておく必要がある。
一般的なコンピュータの構成では、高速に読み書き可能な記憶装置の容量は比較的小さいので、仮想環境の規模が大きい場合、ポリゴンモデルのモデル情報やポリゴンの動的な増減に必要な情報の全て記録しておくことは困難である。
特に、組み込み機器などの比較的性能が高くない端末においては、高速に読み書きが可能な記憶装置の容量が更に小さいため、情報量が多い3次元仮想環境に対して、View−Depent Progressive Meshを適用することは困難である。

概要

DD2により保存されている複数の分割データの中から、読込命令が示す分割データを読み込んで、その分割データをHDD2より高速に読み書きが可能なメモリ4に展開するデータ展開部31と、分割されたポリゴンモデル毎に、仮想空間内の視点を考慮して、当該ポリゴンモデルに対する描画の詳細度を決定する詳細度決定部32と、メモリ4に展開されている分割データを参照して、詳細度決定部32により決定された詳細度に対応する頂点の数を有するポリゴンモデルを構築するとともに、読込対象の分割データを示す読込命令をデータ展開部31に出力するポリゴンモデル構築部33とを設ける。

目的

この発明は上記のような課題を解決するためになされたもので、大量のデータを高速に読み書き可能な記憶装置が搭載されていなくてもLOD技術を適用して、複雑な3次元仮想環境を高速かつ高品質に描画することができる画像表示装置を得ることを目的とする

効果

実績

技術文献被引用数
1件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

次元物体表現しているポリゴンモデルを分割するモデル分割手段と、上記モデル分割手段により分割されたポリゴンモデル毎に、当該ポリゴンモデルを構成している1以上のポリゴンにおける既存の頂点から新たな頂点を生成し、新たな頂点を含む1以上のポリゴンモデルの頂点間論理的な接続関係木構造で表現されている頂点データを生成する頂点データ生成手段と、上記頂点データ生成手段により生成された頂点データを分割し、上記頂点データの分割データ記憶装置に保存するデータ保存手段と、上記記憶装置により保存されている複数の分割データの中から、読込命令が示す分割データを読み込んで、上記分割データを上記記憶装置より高速に読み書きが可能な記録媒体展開する一方、上記記録媒体に展開済みの分割データの中から、破棄命令が示す分割データを破棄するデータ展開手段と、上記モデル分割手段により分割されたポリゴンモデル毎に、仮想空間内視点を考慮して、当該ポリゴンモデルに対する描画の詳細度を決定する詳細度決定手段と、上記記録媒体に展開されている分割データを参照して、上記詳細度決定手段により決定された詳細度に対応する頂点の数を有するポリゴンモデルを構築するとともに、読込対象の分割データを示す読込命令及び破棄対象の分割データを示す破棄命令を上記データ展開手段に出力するポリゴンモデル構築手段と、上記ポリゴンモデル構築手段により構築されたポリゴンモデルを描画する描画手段とを備えた画像表示装置

請求項2

頂点データ生成手段は、新たな頂点を含む1以上のポリゴンモデルの頂点毎に、三次元位置を示す情報、論理的な接続関係がある頂点を示す情報及び描画対象の頂点であるか否かを示すアクティブフラグからなる頂点データを生成することを特徴とする請求項1記載の画像表示装置。

請求項3

データ保存手段は、頂点データの分割データを1つの保存単位として、各分割データを別々に上記記憶装置に保存することを特徴とする請求項1記載の画像表示装置。

請求項4

詳細度決定手段は、仮想空間内の視点を考慮して、モデル分割手段による分割前のポリゴンモデルの画像に対する分割後のポリゴンモデルの画像の寄与度を算出し、上記寄与度が高い程、分割後のポリゴンモデルに対する描画の詳細度を高い値に決定することを特徴とする請求項1記載の画像表示装置。

請求項5

詳細度決定手段は、仮想空間内の視点からモデル分割手段による分割後のポリゴンモデルが見える位置にあるか否か、上記視点から分割後のポリゴンモデルまでの距離、あるいは、上記視点から分割後のポリゴンモデルを見たときに当該ポリゴンモデルが分割前のポリゴンモデルの輪郭の一部を構成しているか否かを判断基準にして、分割前のポリゴンモデルの画像に対する分割後のポリゴンモデルの画像の寄与度を算出することを特徴とする請求項4記載の画像表示装置。

請求項6

ポリゴンモデル構築手段は、モデル分割手段により分割されたポリゴンモデル毎に、当該ポリゴンモデルにおける頂点の数が詳細度決定手段により決定された詳細度に対応する頂点の数と一致するように、記録媒体に展開されている分割データである頂点データ及び面データに含まれているアクティブフラグを更新することで、描画対象のポリゴンモデルを構築することを特徴とする請求項2記載の画像表示装置。

請求項7

ポリゴンモデル構築手段は、現在、記録媒体に展開されている分割データだけでは、詳細度決定手段により決定された詳細度に対応する頂点の数を有するポリゴンモデルを構築することが不可能な場合、他の分割データの読み込みを指示する読込指令をデータ展開手段に出力する一方、上記詳細度決定手段により決定された詳細度に対応する頂点の数を有するポリゴンモデルを構築する上で、余分な分割データが上記記録媒体に展開されている場合、余分な分割データの破棄を指示する破棄指令を上記データ展開手段に出力することを特徴とする請求項1記載の画像表示装置。

技術分野

0001

この発明は、3次元的な幾何学情報を使用して、画像を表示する画像表示装置に関するものである。

背景技術

0002

コンピュータグラフィックスを用いて、インタラクティブアプリケーション構築するには、表示装置が画像をリアルタイムに表示して、その画像を利用者提示する必要がある。
利用者に提示される画像としては、コンピュータ内に記録されている画像のほか、その記録されている画像がコンピュータによって加工された加工画像や、記録された情報を用いて、コンピュータによって内部的に描画された画像などがある。

0003

特に、3次元的な仮想空間内仮想物体を配置している環境(仮想環境)をコンピュータ内に構築し、コンピュータが、仮想視点から見た場合の仮想環境を描画して表示するには、仮想環境の3次元的な幾何学的形状や色などの多くの情報を用いて、投影処理などの複雑な処理をリアルタイムに行う必要がある。
しかし、描画される環境が複雑な場合や、コンピュータの処理性能が高くない場合には、上記の処理をリアルタイムに行うことは困難である。
なお、コンピュータ内の3次元仮想空間表現するデータ形式としては様々なものがあるが、ここでは、描画対象となる仮想物体や環境は、仮想空間内で互いに異なる位置にある3点を結んだ面で表される三角形ポリゴンで構成されるものとする。

0004

従来の画像表示装置では、複雑な3次元仮想環境高速に描画する際に、LOD(Level Of Detail)技術が用いられている。
LOD技術は、描画対象となる3次元仮想環境を表す情報の一部を削減又は単純化することで、描画時間を短縮する技術である。

0005

例えば、以下の特許文献1に開示されているLOD技術は、次のようなものである。
まず、表示対象物体を表すオリジナルポリゴンモデルを簡略化し、オリジナルのポリゴンモデルと一緒に簡略化したポリゴンモデルを補助記憶装置に記録する。
次に、表示対象の物体を描画する際、その描画結果に対する各モデル視覚的な寄与度予測し、ある閾値よりも寄与度が高いモデルについては、補助記憶装置からオリジナルのポリゴンモデルをメモリにロードして描画を行う。
一方、ある閾値よりも寄与度が低いモデルについては、補助記憶装置から簡略化したポリゴンモデルをメモリにロードして描画を行うことで、メモリの消費量と描画時間を節約している。

0006

このようにして、オリジナルのポリゴンモデル又は簡略化したポリゴンモデルを適宜選択して描画を行う場合には、次のような不具合が発生することがある。
例えば、視点の移動などによって、オリジナルのポリゴンモデルと簡略化したポリゴンモデルの入れ替えが発生するとき、オリジナルのポリゴンモデルと簡略化したポリゴンモデルの形状が大きく異なっていると、ポリゴンモデルの変化が顕著に現れて、不自然さが目立ってしまうことがある。

0007

このとき、ポリゴンモデルを選択する際の寄与度に関する閾値を高く設定すれば、上記の不自然さを緩和することができるが、オリジナルのポリゴンモデルを利用する割合が増えるため、描画の高速化やメモリ量の削減効果が減少することになる。
また、簡略化のレベルが異なる複数のポリゴンモデルを補助記憶装置に記録し、複数の閾値に応じて複数のポリゴンモデルを入れ替えるようにすれば、上記の不自然さを緩和することができるが、補助記憶装置に記録するポリゴンモデルのデータの量が大きく増加することになる。また、補助記憶装置に対するアクセス回数も大きく増えて、ボトルネックが発生することになる。

0008

以下の非特許文献1には、特許文献1に開示されているLOD技術と異なる別のLOD技術として、View−Dependent Progressive Meshが開示されている。
View−Dependent Progressive Meshは、描画対象のポリゴンモデルのうち、描画結果に対して視覚的な寄与度が小さい部分のポリゴンの数を削減すると同時に、そのポリゴンの削減に伴う描画結果に与える影響が小さくなるように、残ったポリゴンの一部を変形するようにしている。これにより、描画結果である画像の品質を保ちつつ、描画の処理時間を短縮することができる。
また、ポリゴンの削減や、削減されたポリゴンの復元を1頂点単位で実行することができるため、常に必要最小限のポリゴン数で描画することができる。また、ポリゴン数の変化による描画対象の変形を目立ち難くすることができる。

0009

しかし、View−Depent Progressive Meshの場合、描画対象のポリゴンモデルのモデル情報に加えて、ポリゴンの動的な増減に必要な情報を、高速に読み出しが可能なメモリなどの記憶装置に記録しておく必要がある。
一般的なコンピュータの構成では、高速に読み書き可能な記憶装置の容量は比較的小さいので、仮想環境の規模が大きい場合、ポリゴンモデルのモデル情報やポリゴンの動的な増減に必要な情報の全て記録しておくことは困難である。
特に、組み込み機器などの比較的性能が高くない端末においては、高速に読み書きが可能な記憶装置の容量が更に小さいため、情報量が多い3次元仮想環境に対して、View−Depent Progressive Meshを適用することは困難である。

0010

特開2004−213641号公報

先行技術

0011

Hoppe, H., “View dependent refinement of progressive meshes,” Proc. of International Conference on Computer Graphics and Interactive Techniques, pp. 189-198, 1997.

0012

従来の画像表示装置は以上のように構成されているので、描画対象となる3次元仮想環境を表す情報の一部を削減又は単純化するLOD技術を適用すれば、描画時間を短縮することができる。しかし、LOD技術を適用する場合、オリジナルのポリゴンモデルと簡略化したポリゴンモデルの入れ替えが発生するときに生じるモデル変化に伴う不自然さを解消するには、大量のデータ(例えば、簡略化のレベルが異なる複数のポリゴンモデルや、ポリゴンの動的な増減に必要な情報など)を高速に読み書きすることが可能な記憶装置を搭載する必要がある。そのため、大量のデータを高速に読み書き可能な記憶装置が搭載されていない組み込み機器や一般的なコンピュータでは、LOD技術を適用することができない場合があるなどの課題があった。

0013

この発明は上記のような課題を解決するためになされたもので、大量のデータを高速に読み書き可能な記憶装置が搭載されていなくてもLOD技術を適用して、複雑な3次元仮想環境を高速かつ高品質に描画することができる画像表示装置を得ることを目的とする。

0014

この発明に係る画像表示装置は、3次元物体を表現しているポリゴンモデルを分割するモデル分割手段と、モデル分割手段により分割されたポリゴンモデル毎に、当該ポリゴンモデルを構成している1以上のポリゴンにおける既存の頂点から新たな頂点を生成し、新たな頂点を含む1以上のポリゴンモデルの頂点間論理的な接続関係木構造で表現されている頂点データを生成する頂点データ生成手段と、頂点データ生成手段により生成された頂点データを分割し、その頂点データの分割データを記憶装置に保存するデータ保存手段と、その記憶装置により保存されている複数の分割データの中から、読込命令が示す分割データを読み込んで、その分割データを上記記憶装置より高速に読み書きが可能な記録媒体展開する一方、その記録媒体に展開済みの分割データの中から、破棄命令が示す分割データを破棄するデータ展開手段と、モデル分割手段により分割されたポリゴンモデル毎に、仮想空間内の視点を考慮して、当該ポリゴンモデルに対する描画の詳細度を決定する詳細度決定手段と、その記録媒体に展開されている分割データを参照して、詳細度決定手段により決定された詳細度に対応する頂点の数を有するポリゴンモデルを構築するとともに、読込対象の分割データを示す読込命令及び破棄対象の分割データを示す破棄命令をデータ展開手段に出力するポリゴンモデル構築手段とを設け、描画手段がポリゴンモデル構築手段により構築されたポリゴンモデルを描画するようにしたものである。

0015

この発明によれば、3次元物体を表現しているポリゴンモデルを分割するモデル分割手段と、モデル分割手段により分割されたポリゴンモデル毎に、当該ポリゴンモデルを構成している1以上のポリゴンにおける既存の頂点から新たな頂点を生成し、新たな頂点を含む1以上のポリゴンモデルの頂点間の論理的な接続関係が木構造で表現されている頂点データを生成する頂点データ生成手段と、頂点データ生成手段により生成された頂点データを分割し、その頂点データの分割データを記憶装置に保存するデータ保存手段と、その記憶装置により保存されている複数の分割データの中から、読込命令が示す分割データを読み込んで、その分割データを上記記憶装置より高速に読み書きが可能な記録媒体に展開する一方、その記録媒体に展開済みの分割データの中から、破棄命令が示す分割データを破棄するデータ展開手段と、モデル分割手段により分割されたポリゴンモデル毎に、仮想空間内の視点を考慮して、当該ポリゴンモデルに対する描画の詳細度を決定する詳細度決定手段と、その記録媒体に展開されている分割データを参照して、詳細度決定手段により決定された詳細度に対応する頂点の数を有するポリゴンモデルを構築するとともに、読込対象の分割データを示す読込命令及び破棄対象の分割データを示す破棄命令をデータ展開手段に出力するポリゴンモデル構築手段とを設け、描画手段がポリゴンモデル構築手段により構築されたポリゴンモデルを描画するように構成したので、大量のデータを高速に読み書き可能な記憶装置が搭載されていなくてもLOD技術を適用して、複雑な3次元仮想環境を高速かつ高品質に描画することができる効果がある。

図面の簡単な説明

0016

この発明の実施の形態1による画像表示装置を示す構成図である。
ポリゴンモデル、頂点データ及び面データの一例を示す説明図である。
モデル分割部11によるポリゴンモデルの分割例を示す説明図である。
前処理部1におけるデータ生成部12の処理内容を示すフローチャートである。
ブロック単位のポリゴンモデルがデータ生成部12の処理に伴って変化する様子を示す説明図である。
図5(a)のポリゴンモデルから生成される頂点データ及び面データを示す説明図である。
データ生成部12の処理に伴って変化する頂点の論理的な接続関係を示す説明図である。
データ生成部12により頂点データ及び面データの更新処理が一度行われた後の頂点データ及び面データを示す説明図である。
データ生成部12による処理終了後の面データを示す説明図である。
前処理部1におけるソート部13の処理内容を示すフローチャートである。
(a)はソート部13により頂点インデックス更新される前の頂点の論理的な接続関係を示し、(b)はソート部13により頂点インデックスが更新される後の頂点の論理的な接続関係を示し、(c)はソート部13により頂点が3分割された状態を示す説明図である。
図11(c)に示す木構造の頂点を表現するデータ構造の一例を示す説明図である。
頂点インデックス(頂点参照配列)が更新された面データを示す説明図である。
インデックスが更新された面データを示す説明図である。
連面を示す面インデックスが更新された頂点データを示す説明図である。
ソート部13により変換された面データを示す説明図である。
集合1に属する頂点データ及び面データがファイル1としてHDD2に記録され、集合2に属する頂点データ及び面データがファイル2としてHDD2に記録され、集合3に属する頂点データ及び面データがファイル3としてHDD2に記録されている例を示す説明図である。
詳細度決定部32による描画の詳細度の決定処理を説明する説明図である。
実行時処理部3におけるポリゴンモデル構築部33の処理内容を示すフローチャートである。
メモリ4に展開されている集合1,2に属する頂点データ及び面データを示す説明図である。
実行時処理部3における描画処理部34の処理内容を示すフローチャートである。

実施例

0017

以下、この発明をより詳細に説明するために、この発明を実施するための形態について、添付の図面に従って説明する。
実施の形態1.
図1はこの発明の実施の形態1による画像表示装置を示す構成図である。
図1において、前処理部1はモデル分割部11、データ生成部12、ソート部13及びデータ保存部14から構成されており、モデル分割部11、データ生成部12、ソート部13及びデータ保存部14は、例えばCPUを実装している半導体集積回路、あるいは、ワンチップマイコンなどから構成されている。
前処理部1は3次元物体を表現しているポリゴンモデルを分割し、分割後のポリゴンモデル毎に、当該ポリゴンモデルを構成している1以上のポリゴンにおける既存の頂点から新たな頂点を生成し、新たな頂点を含む1以上のポリゴンモデルの頂点間の論理的な接続関係が木構造で表現されている頂点データを生成する処理を実施する。
また、前処理部1は頂点データを分割して、その頂点データの分割データをHDD2に記録する処理を実施する。

0018

HDD2は前処理部1により生成された頂点データの分割データを記録する大容量の補助記憶装置である。
図1では、大容量の補助記憶装置としてHDD2を使用している例を示しているが、補助記憶装置はHDD2に限るものではなく、例えば、フラッシュメモリなど、容量が大きい任意の記憶媒体を用いるようにしてもよい。

0019

ここで、ポリゴンモデルは、仮想空間内において、互いに異なる位置に存在している3点を接続している3本の線分によって囲まれる面の集合として表される形状であり、3本の線分によって囲まれる面は「ポリゴン」と呼ばれる。
また、ポリゴンを構成する3つの点は「ポリゴンの頂点」、ポリゴンの頂点を結ぶ3本の線分は「ポリゴンの辺」と呼ばれる。
ポリゴンモデルを表現するデータ構造は様々であるが、この実施の形態1では、一意の頂点インデックスと3次元位置からなる頂点データの集合と、一意の面インデックスとポリゴンの3頂点への参照情報からなる面データの集合とを有するデータを取り扱うものとする。

0020

図2はポリゴンモデル、頂点データ及び面データの一例を示す説明図である。
(a)は2次元に投影されているポリゴンモデルを示しており、ポリゴンの9つの頂点を“1”から“9”までの頂点インデックスを付けて表している。
また、各頂点を結ぶ線分に囲まれているポリゴンが“1”から“10”までの面インデックス(頂点のインデックスと区別するために、面のインデックスは括弧で括っている)を付けて表している。
(b)は(a)のポリゴンモデルを構成する頂点データを示しており、1つのカラムが1つの頂点を表し、各カラムが一意の頂点インデックスと、xyz軸で定義される直交座標系内の3次元位置(X,Y,Z)とを保有している。

0021

また、(c)はポリゴンの面を表す面データを示しており、1つのカラムが1つのポリゴン面を表し、各カラムが一意の面インデックスと、三角形のポリゴンを構成する3つの頂点の参照情報として、3つの頂点インデックスとを保有している。
この実施の形態1では、三角形のポリゴンモデルとしているが、前処理部1が任意の3次元形状を現すデータをポリゴンモデルに変換する手段を備えることで、任意の3次元オブジェクトを入力して、その3次元オブジェクトのデータをポリゴンモデルに変換するようにしてもよい。また、ポリゴンモデルは3次元以外の次元数を有する仮想空間内にあるものでもよい。

0022

実行時処理部3はデータ展開部31、詳細度決定部32、ポリゴンモデル構築部33及び描画処理部34から構成されており、詳細度決定部32、ポリゴンモデル構築部33及び描画処理部34は、例えばCPUを実装している半導体集積回路、ワンチップマイコン、あるいは、GPU(Graphics Processing Unit)などから構成されている。
実行時処理部3はHDD2により記録されている複数の分割データを読み込んで、その分割データをHDD2より高速に読み書きが可能な記録媒体であるメモリ4に展開する処理を実施し、また、前処理部1により分割されたポリゴンモデル毎に、仮想空間内の視点を考慮して、当該ポリゴンモデルに対する描画の詳細度を決定する処理を実施する。
また、実行時処理部3はメモリ4に展開済みの分割データを参照して、描画の詳細度に対応する頂点の数を有するポリゴンモデルを構築し、そのポリゴンモデルの画像を画像表示部5に表示する処理を実施する。

0023

メモリ4はHDD2より記憶容量が小さいが、HDD2より高速に読み書きが可能な記録媒体であり、例えば、RAMなどが該当する。
画像表示部5は実行時処理部3の描画処理によってポリゴンモデルを表示するディスプレイなどの出力装置である。

0024

前処理部1のモデル分割部11は3次元物体を表現しているポリゴンモデルを入力するインタフェース(例えば、LANなどのネットワークからポリゴンモデルを入力する場合、LANカードなどのネットワーク機器)を備えており、そのポリゴンモデルをブロック(互いの距離が近い1以上のポリゴンの集合)単位に分割する処理を実施する。なお、モデル分割部11はモデル分割手段を構成している。

0025

前処理部1のデータ生成部12はモデル分割部11により分割されたポリゴンモデル毎に、当該ポリゴンモデルを構成している1以上のポリゴンにおける既存の頂点から新たな頂点を生成し、新たな頂点を含む1以上のポリゴンモデルの頂点間の論理的な接続関係が木構造で表現されている頂点データを生成するとともに、1以上のポリゴンの各面に関する面データを生成する処理を実施する。
ここで、頂点データは、詳細は後述するが、図6に示すように、新たな頂点を含む1以上のポリゴンモデルの頂点毎に、当該頂点を識別する頂点インデックス、当該頂点の三次元位置を示す位置情報、当該頂点と論理的な接続関係がある頂点を示す接続情報、当該頂点が描画対象の頂点であるか否かを示すアクティブフラグなどから構成されている。
また、面データは、新たな頂点を含む1以上のポリゴンモデルの面毎に、当該面を識別する面インデックス、当該面を構成している頂点を示す頂点情報、当該面が描画対象の面であるか否かを示すアクティブフラグなどから構成されている。

0026

前処理部1のソート部13はデータ生成部12により生成された頂点データの頂点インデックス及び面データの頂点インデックスを更新する処理や、その頂点データを分割して、その頂点データの分割データを出力する処理を実施する。
前処理部1のデータ保存部14はソート部13から出力された頂点データの分割データをHDD2に保存する処理を実施する。
なお、ソート部13及びデータ保存部14からデータ保存手段が構成されている。

0027

実行時処理部3のデータ展開部31はHDD2により保存されている複数の分割データの中から、ポリゴンモデル構築部33から出力された読込命令が示す分割データを読み込んで、その分割データをメモリ4に展開する一方、そのメモリ4に展開済みの分割データの中から、ポリゴンモデル構築部33から出力された破棄命令が示す分割データを破棄する処理を実施する。なお、データ展開部31はデータ展開手段を構成している。

0028

実行時処理部3の詳細度決定部32は仮想空間内の視点を示す視点情報を入力するインタフェース(例えば、LANなどのネットワークからポリゴンモデルを入力する場合、LANカードなどのネットワーク機器)を備えており、前処理部1のモデル分割部11により分割されたポリゴンモデル毎に、その視点情報が示す仮想空間内の視点を考慮して、当該ポリゴンモデルに対する描画の詳細度を決定する処理を実施する。
即ち、詳細度決定部32は仮想空間内の視点から分割後のポリゴンモデルが見える位置にあるか否か、仮想空間内の視点から分割後のポリゴンモデルまでの距離、あるいは、仮想空間内の視点から分割後のポリゴンモデルを見たときに当該ポリゴンモデルが分割前のポリゴンモデル(前処理部1に与えられたポリゴンモデル)の輪郭の一部を構成しているか否かなどを判断基準にして、分割前のポリゴンモデルの画像に対する分割後のポリゴンモデルの画像の寄与度を算出し、その寄与度が高い程、当該ポリゴンモデルに対する描画の詳細度を高い値に決定する処理を実施する。
なお、詳細度決定部32は詳細度決定手段を構成している。

0029

実行時処理部3のポリゴンモデル構築部33は前処理部1のモデル分割部11により分割されたポリゴンモデル毎に、当該ポリゴンモデルにおける頂点の数が詳細度決定部32により決定された詳細度に対応する頂点の数と一致するように、メモリ4に展開されている分割データに含まれている頂点データ及び面データのアクティブフラグを更新することで、描画対象のポリゴンモデルを構築する処理を実施する。
また、ポリゴンモデル構築部33は読込対象の分割データを示す読込命令及び破棄対象の分割データを示す破棄命令をデータ展開部31に出力する処理を実施する。即ち、現在、メモリ4に展開されている分割データだけでは、詳細度決定部32により決定された詳細度に対応する頂点の数を有するポリゴンモデルを構築することが不可能な場合、他の分割データの読み込みを指示する読込指令をデータ展開部31に出力する一方、詳細度決定部32により決定された詳細度に対応する頂点の数を有するポリゴンモデルを構築する上で、余分な分割データがメモリ4に展開されている場合、余分な分割データの破棄を指示する破棄指令をデータ展開部31に出力する処理を実施する。
なお、ポリゴンモデル構築部33はポリゴンモデル構築手段を構成している。

0030

実行時処理部3の描画処理部34はポリゴンモデル構築部33により構築されたポリゴンモデル(ポリゴンモデル構築部33による更新後のアクティブフラグが、描画対象である旨を示している頂点からなるポリゴンモデル)の画像を、例えば内部のビデオRAM上に描画して、その画像を画像表示部5に出力する処理を実施する。なお、描画処理部34は描画手段を構成している。

0031

図1では、画像表示装置の構成要素である前処理部1、HDD2、実行時処理部3、メモリ4及び画像表示部5のそれぞれが専用のハードウェアで構成されているものを想定しているが、画像表示装置の構成要素である前処理部1及び実行時処理部3がコンピュータで構成される場合、前処理部1及び実行時処理部3の処理内容が記述されているプログラムを当該コンピュータのメモリに格納し、当該コンピュータのCPUが当該メモリに格納されているプログラムを実行するようにしてもよい。

0032

ここで、図4は前処理部1におけるデータ生成部12の処理内容を示すフローチャートである。
また、図10は前処理部1におけるソート部13の処理内容を示すフローチャートである。
図19は実行時処理部3におけるポリゴンモデル構築部33の処理内容を示すフローチャートである。
また、図21は実行時処理部3における描画処理部34の処理内容を示すフローチャートである。

0033

次に動作について説明する。
前処理部1のモデル分割部11は、3次元物体を表現しているポリゴンモデルを入力すると、そのポリゴンモデルをブロック(互いの距離が近い1以上のポリゴンの集合)単位に分割する。
図3はモデル分割部11によるポリゴンモデルの分割例を示す説明図である。
図3(a)は分割前のポリゴンモデルを示し、図3(b)は分割後のポリゴンモデルを示している。図3(b)において、破線が各ブロックの境界を表している。

0034

図3の例では、ポリゴンモデルの表面を単純な格子状に分割しているが、例えば、各ブロックに含まれるポリゴンの頂点の数が等しくなるように区切るなど、任意の区切り方で分割するようにしてもよい。
また、与えられたポリゴンモデルを分割することによってポリゴン面が分断されるなど、各ポリゴンの形状に変化が起こり得る場合には、予め、各ポリゴンの辺が分断面と一致するように、ポリゴンの頂点や面を加工するなどの処理(ポリゴンの形状の変化を防止する処理)を行うようにしてもよい。

0035

前処理部1のデータ生成部12は、モデル分割部11がポリゴンモデルをブロック単位に分割すると、ブロック単位のポリゴンモデル毎に、当該ポリゴンモデルを構成している1以上のポリゴンにおける既存の頂点から新たな頂点を生成し、新たな頂点を含む1以上のポリゴンモデルの頂点間の論理的な接続関係が木構造で表現されている頂点データを生成する。
以下、データ生成部12の処理内容を具体的に説明する。

0036

まず、データ生成部12は、初期状態の頂点データと面データを生成する。
即ち、データ生成部12は、ブロック単位のポリゴンモデル毎に、当該ポリゴンモデルを構成している1以上のポリゴンにおける既存の頂点を“葉”とする木構造の頂点データを生成するとともに、1以上のポリゴンの各面に関する面データを生成する(図4のステップST1)。
ここで、図5はブロック単位のポリゴンモデルがデータ生成部12の処理に伴って変化する様子を示す説明図である。
図5において、1〜14は後述する頂点インデックスを示し、(1)〜(10)は後述する面インデックスを示している。
また、図6図5(a)のポリゴンモデルから生成される頂点データ及び面データを示す説明図である。

0037

図6(a)は、データ生成部12が図5(a)に示す1つのブロックのポリゴンモデルが与えられたとき、そのポリゴンモデルから生成する木構造の頂点データを示している。
頂点データにおける1つのカラムが1つの頂点を表しており、各カラムは、以下の(1)〜(5)の情報から構成されている。
(1)当該頂点を識別する頂点インデックス(例えば、1〜9の数字
(2)当該頂点の三次元位置(X,Y,Z)を示す位置情報
(3)当該頂点と論理的な接続関係がある頂点を示す接続情報(当該頂点の親ノードに相当する頂点を示す頂点インデックスと、当該頂点の子ノードに相当する頂点を示す頂点インデックス)
ただし、この段階では、既存の頂点から新たな頂点を生成していないため(新たな頂点の生成処理は後述する)、親ノードや子ノードに相当する頂点が存在しておらず、図6(a)には、親ノードや子ノードに相当する頂点が無い旨を示す“−1”が接続情報に代入されている。

0038

(4)後述する木構造生成の過程で削減されるポリゴン面である関連面を特定する面インデックス
ただし、この段階では、削減されているポリゴン面が存在しないので、関連面を特定する面インデックスには、“−1”が代入されている。
(5)当該頂点が描画対象の頂点であるか否かを示すアクティブフラグ(アクティブフラグが“1”(アクティブ)の場合、当該頂点が実行時処理部3で描画されることを示し、アクティブフラグが“0”(非アクティブ)の場合、当該頂点が実行時処理部3で描画されないことを示しているが、この段階では、全てのアクティブフラグが“1”(アクティブ)に初期化される)

0039

図6(b)は、データ生成部12が図5(a)に示す1つのブロックのポリゴンモデルが与えられたとき、そのポリゴンモデルから生成する面データを示している。
面データには、入力されたブロックに含まれているポリゴンの面と同数のカラムが生成され、1つのカラムが1つの面を表している。
頂点データの各カラムは、以下の(1)〜(3)の情報から構成されている。
(1)当該面を識別する面インデックス(例えば、1〜10の数字)
(2)当該面を構成している3つの頂点を示す頂点インデックス(頂点参照配列)
(3)当該面が描画対象の面であるか否かを示すアクティブフラグ(アクティブフラグが“1”(アクティブ)の場合、当該面が実行時処理部3で描画されることを示し、アクティブフラグが“0”(非アクティブ)の場合、当該面が実行時処理部3で描画されないことを示しているが、この段階では、削減されているポリゴン面が存在しないので、全てのアクティブフラグが“1”(アクティブ)に初期化される)

0040

以降、アクティブフラグが“1”である頂点、面を、アクティブな頂点、アクティブな面と称し、アクティブフラグが“0”である頂点、面を、非アクティブな頂点、非アクティブな面と称する。

0041

図7はデータ生成部12の処理に伴って変化する頂点の論理的な接続関係を示す説明図である。
特に図7(a)は図6(a)の頂点データが示す各頂点の論理的な接続関係を示している。
図6(a)の頂点データにおける各頂点(頂点インデックスが“1”〜“9”の頂点)には、上述したように、親ノード及び子ノードに相当する頂点が存在していないので、他の頂点と接続されていない。
図7では、アクティブな頂点は、白く塗り潰された円で表し、非アクティブな頂点は、斜線で塗り潰された円で表している。

0042

データ生成部12は、初期状態の頂点データと面データを生成すると、その頂点データにおけるアクティブな頂点の数と予め設定されている閾値を比較する。
ここでの閾値は、予め設定される任意の数値であるが、前処理部1に与えられるポリゴンモデルが図3のように四角形のブロックに分割される場合には、当該ブロックの頂点数に相当する“4”が閾値として設定される。
また、前処理部1に与えられるポリゴンモデルが五角形のブロックに分割される場合には、当該ブロックの頂点数に相当する“5”が閾値として設定される。
ただし、閾値は、任意に設定されるものであり、ブロックが四角形であっても、“4”に限定されるものではなく、例えば、“5”や“6”などの数値(ただし、ブロックに含まれている1以上のポリゴンの頂点の数より少ない数値)であってもよい。

0043

データ生成部12は、アクティブな頂点の数が予め設定されている閾値より大きければ、以下のステップST3の処理に移行し、アクティブな頂点の数が閾値以下であれば、処理を終了する(ステップST2)。
この段階では、全ての頂点(頂点インデックスが“1”〜“9”の頂点)がアクティブな頂点であるため、アクティブな頂点の数が閾値より大きく、以下のステップST3の処理に移行する。

0044

データ生成部12は、アクティブな頂点の数が閾値より大きい場合、頂点データに含まれている全てのアクティブな頂点の中から、任意の2個の頂点(以下、「ペア」と称する)を順番に取り出し、当該ブロックに対する当該ペアの重要度評価値として算出する(ステップST3)。
アクティブな頂点における全てのペアについて重要度を算出するため、例えば、アクティブな頂点が9個存在する場合、9C2=36組のペアについて重要度を算出する。
ペアとなる2個の頂点の重要度の尺度としては、例えば、ペアとなる2個の頂点間の幾何学的距離や、ペアとなる2個の頂点のうちの1頂点を削減した場合に生じるポリゴンモデルの変形量などを用いることができる。
なお、ペアの重要度を算出する際、重要度の計算時間や精度を考慮して、適正な尺度を選択するようにしてもよい。

0045

データ生成部12は、全てのペアの重要度を評価値として算出すると、最も評価値が低いペアを特定し、そのペアを構成する2個の頂点のアクティブフラグを“0”にして、その2個の頂点を非アクティブな頂点に変更する。
例えば、図5(a)の頂点7と頂点8のペアにおける評価値が最も低い場合、頂点7と頂点8のアクティブフラグを“0”にして、頂点7と頂点8を非アクティブな頂点にする(図7(b)を参照)。

0046

また、データ生成部12は、そのペアを構成する2個の頂点のうち、いずれか一方の頂点と同じ位置にアクティブな頂点を新たに1つ生成し、頂点データにおける最大値の頂点インデックス(図6(a)の例では、“9”)に“1”を加えた“10”の頂点インデックスを新たな頂点インデックスとして、その頂点データに追加する(図8(a)を参照)。
図8はデータ生成部12により頂点データ及び面データの更新処理が一度行われた後の頂点データ及び面データを示す説明図である。

0047

図5(b)では、頂点7と同じ位置にアクティブな頂点10を生成している例を示しているが、頂点8と同じ位置にアクティブな頂点10を生成するようにしてもよい。
頂点7と頂点8のいずれの位置を選択するかについては特に限定するものではないが、例えば、頂点7と同じ位置にアクティブな頂点10を生成する場合のポリゴンモデルの密度と、頂点8と同じ位置にアクティブな頂点10を生成する場合のポリゴンモデルの密度とを計算し、ポリゴンモデルの密度が高くなる方を選択するようにしてもよい。
また、頂点7と同じ位置にアクティブな頂点10を生成する場合のポリゴンモデルの変形量と、頂点8と同じ位置にアクティブな頂点10を生成する場合のポリゴンモデルの変形量とを計算し、ポリゴンモデルの変形量が小さくなる方を選択するようにしてもよい。

0048

また、ここでは、データ生成部12が、ペアを構成する2個の頂点のうち、いずれか一方の頂点と同じ位置にアクティブな頂点を新たに1つ生成しているが、これに限るものではなく、例えば、2個の頂点の平均値を示す位置や、ポリゴンモデルの変形量が最も小さくなる位置にアクティブな頂点を新たに1つ生成するようにしてもよい。

0049

データ生成部12は、例えば、頂点7と頂点8を非アクティブな頂点にすると、面データを参照して、頂点7と頂点8の両方を頂点としているポリゴンの面を検索し、その面のアクティブフラグを“0”にして、その面を非アクティブな面に変更する。
図5(a)の例では、ポリゴンの面(4)と面(8)を非アクティブな面にしている(図8(b)を参照)。

0050

データ生成部12は、アクティブフラグを更新して、新たな頂点インデックスを追加すると、頂点データと面データの更新処理を実施する(ステップST4)。
具体的には、頂点データにおいて、図8(a)に示すように、“10”の頂点インデックスが付与されている頂点10の位置情報の欄には、頂点10の三次元位置(x10,y10,z10)を記録し、頂点10の子ノードの欄には、頂点7と頂点8の頂点インデックスを記録し、頂点10の関連面の欄には、非アクティブになった面(4)と面(8)の面インデックスを記録する。
また、非アクティブになった頂点7及び頂点8の親ノードの欄には、頂点10の頂点インデックスを記録する。
なお、頂点10のアクティブフラグとして“1”、頂点7と頂点8のアクティブフラグとして“0”を記録する。

0051

面データにおいて、図8(b)に示すように、“10”の面インデックスが付与されている面(10)を構成している頂点を示す欄には、元々記録されている非アクティブになった頂点8の頂点インデックスの前に、頂点10の頂点インデックスを記録する。
また、頂点7又は頂点8を頂点に含んでいた面(2)、面(5)、面(6)、面(7)及び面(9)において、面を構成している頂点を示す欄には、頂点7又は頂点8の頂点インデックスの前に、頂点10の頂点インデックスを記録する。

0052

図7(b)はデータ生成部12によりステップST3,ST4の処理が一度行われた後の頂点の論理的な接続関係を示しており、図7(b)では、頂点10が新たに生成されて、アクティブな頂点から非アクティブな頂点に更新された頂点7と頂点8の親ノードとして、頂点10が接続されている様子を示している。

0053

データ生成部12は、頂点データと面データの更新処理を実施すると、ステップST2の処理に戻り、アクティブな頂点の数が閾値以下になるまで、ステップST2〜ST4の処理を繰り返し実施する。
詳細な処理は省略するが、図5(c)はデータ生成部12によりステップST3,ST4の処理が二度行われた後のポリゴンモデルを示している。ここでは、頂点2と頂点5から新たに頂点11が生成されている。
図7(c)はデータ生成部12によりステップST3,ST4の処理が二度行われた後の頂点の論理的な接続関係を示しており、図7(c)では、頂点11が新たに生成されて、アクティブな頂点から非アクティブな頂点に更新された頂点2と頂点5の親ノードとして、頂点11が接続されている様子を示している。

0054

図5(d)はデータ生成部12によりステップST3,ST4の処理が五度行われた後のポリゴンモデルを示している(アクティブな頂点の数が閾値と等しくなった時点のポリゴンモデル)。
図7(d)はデータ生成部12によりステップST3,ST4の処理が五度行われた後の頂点の論理的な接続関係を示している。
図9はデータ生成部12による処理終了後の面データを示す説明図であり、図5(d)及び図7(d)に対応している。

0055

前処理部1のソート部13は、データ生成部12が頂点データを生成すると、その頂点データの頂点インデックスや、面データの頂点インデックスを更新する処理を実施するほか、その頂点データを分割して、その頂点データの分割データをデータ保存部14に出力する処理を実施する。
以下、ソート部13の処理内容を具体的に説明する。

0056

ソート部13は、次の3つのルールにしたがって、データ生成部12により生成された頂点データの頂点インデックスを更新する(図10のステップST11)。
[ルール1]
根となる頂点に対して、ユニークな整数を頂点インデックスとして付与する。
[ルール2]
根以外の頂点に対して、根の頂点インデックスの最大値及び親ノードの頂点インデックスよりも大きい頂点インデックスを付与する。また、同じ親ノードが接続されている子ノードである複数の頂点に対しては、子ノード同士で隣り合った整数を頂点インデックスとして付与する。
[ルール3]
各頂点がポリゴンモデルの形状に寄与する度合いを算出し(例えば、データ生成部12により算出された評価値)、その度合いが高い頂点ほど、小さな頂点インデックスを付与する。

0057

図11(a)はソート部13により頂点インデックスが更新される前の頂点の論理的な接続関係を示しており、図11(b)はソート部13により頂点インデックスが更新される後の頂点の論理的な接続関係を示している。
図11(a)が示す頂点の論理的な接続関係は、図7(d)が示す頂点の論理的な接続関係(データ生成部12による処理終了後の頂点の論理的な接続関係)と同じであり、データ生成部12の処理が終了した時点では、アクティブな頂点(根となる頂点)の個数が4個である。
4個のアクティブな頂点については、ルール1,3が適用されることで、図11(b)に示すように、頂点インデックスが“1”、“11”、“12”、“14”から“1”、“2”、“3”、“4”に更新されている。

0058

10個の非アクティブな頂点については、ルール2が適用されることで、4個のアクティブな頂点の頂点インデックスより大きな頂点インデックスに更新されている。
また、非アクティブな頂点に接続されている子ノード(非アクティブな頂点)については、その親ノードである非アクティブな頂点の頂点インデックスより大きな頂点インデックスに更新されている。
さらに、同じ親ノードが接続されている複数の子ノード(非アクティブな頂点)に対しては、子ノード同士で隣り合った整数を頂点インデックスに更新されている。
10個の非アクティブな頂点についても、ルール3が適用される。
これにより、例えば、3個のアクティブな頂点に接続されている6個の非アクティブな頂点の頂点インデックスは、“2”、“5”、“3”、“6”、“4”、“13”から“11”、“12”、“9”、“10”、“5”、“6”に更新されている。
また、非アクティブな頂点に接続されている4個の非アクティブな頂点の頂点インデックスは、“9”、“10”、“7”、“8”から“7”、“8”、“13”、“14”に更新されている。

0059

ソート部13は、頂点データの頂点インデックスを更新すると、予め設定された閾値を用いて、その頂点データを複数の集合に分割する(ステップST12)。
例えば、頂点データを3つの集合に分割する場合、2つの閾値が設定され、頂点データを5つの集合に分割する場合、4つの閾値が設定される。
この実施の形態1では、説明の便宜上、頂点データを3つの集合に分割するものとして、2つの閾値が設定されているものとする。
このとき、2つの閾値として、任意の数値が設定されるが、例えば、頂点1〜4を集合1に分類し、頂点5〜10を集合2に分類し、頂点11〜14を集合3に分類する場合、閾値として、“4”と“10”が設定される。
なお、2つの閾値は、ポリゴンモデルの頂点の数に応じて動的に変更するようにしてもよい。

0060

ソート部13は、例えば、2つの閾値が設定され、2つの閾値が“4”と“10”である場合、頂点データのうち、頂点インデックスが“4”以下の頂点(“1”、“2”、“3”、“4”の頂点インデックスが付与されている頂点)に係る頂点データを集合1(集合インデックスが“1”の集合)に分類する。
また、頂点データのうち、頂点インデックスが“4”より大きく、かつ、“10”以下の頂点(“5”、“6”、“7”、“8”、“9”、“10”の頂点インデックスが付与されている頂点)に係る頂点データを集合2(集合インデックスが“2”の集合)に分類する。
さらに、頂点データのうち、頂点インデックスが“10”より大きい頂点(“11”、“12”、“13”、“14”の頂点インデックスが付与されている頂点)に係る頂点データを集合3(集合インデックスが“3”の集合)に分類する。
ただし、ソート部13は、木構造の根となる頂点については全て同じ集合(集合インデックスが“1”の集合)に属するように分類する。このため、図11の例では、1つの閾値が“4”に設定される。

0061

ソート部13は、頂点データを複数の集合に分割すると、各頂点の頂点インデックスを、集合インデックスと、当該頂点が属している集合内でユニークな頂点インデックスとの組み合わせからなるインデックス(集合インデックス−集合内頂点インデックス)に更新する。
例えば、集合1に属している頂点の頂点インデックスについては、“1”、“2”、“3”、“4”から“1−1”、“1−2”、“1−3”、“1−4”に更新されている。
また、集合2に属している頂点の頂点インデックスについては、“5”、“6”、“7”、“8”、“9”、“10”から“2−1”、“2−2”、“2−3”、“2−4”、“2−5”、“2−6”に更新されている。
さらに、集合3に属している頂点の頂点インデックスについては、“11”、“12”、“13”、“14”から“3−1”、“3−2”、“3−3”、“3−4”に更新されている。

0062

ここで、図12図11(c)に示す木構造の頂点を表現するデータ構造の一例を示す説明図である。
図12に示すデータは、各頂点を識別する頂点インデックス、頂点の三次元位置を示す位置情報、親ノードを示す頂点インデックス、子ノードを示す頂点インデックス、関連面を示す面インデックス、アクティブフラグから構成されている。

0063

ソート部13は、頂点インデックスを更新すると、更新後の頂点インデックスに合わせて、面データに含まれている頂点インデックス(頂点参照配列)を更新する(ステップST13)。
ここで、図13は頂点インデックス(頂点参照配列)が更新された面データを示す説明図である。
図9及び図13に示すように、例えば、面インデックスが“1”の頂点参照配列に記録されている“1”の頂点インデックスは“1−1”に置き換えられ、“13”の頂点インデックスは“2−2”に置き換えられ、“9”の頂点インデックスは“2−3”に置き換えられ、“4”の頂点インデックスは“2−1”に置き換えられている。
面インデックスが“2”〜“10”の頂点参照配列に記録されている頂点インデックスについても、同様にして置き換えられる。

0064

ソート部13は、面データに含まれている頂点インデックス(頂点参照配列)を更新すると、ポリゴンモデルの各面が属する集合を決定して、各面を識別する面インデックスを更新する(ステップST14)。
具体的には、以下のようにして、ポリゴンモデルの各面が属する集合を決定する。
ここで、図14は面インデックスが更新された面データを示す説明図である。
[集合1]
面データに含まれている3つの頂点参照配列1,2,3の全てにおいて、集合1に属する頂点インデックスが1つ以上記録されている面は、集合1に属するものと決定する。
図13の例では、面インデックスが“6”と“9”の面は、3つの頂点参照配列1,2,3の全てにおいて、集合1に属する頂点インデックスが1つ以上記録されているので、集合1に分類されている(図14を参照)。

0065

[集合2]
集合1に属している面以外の面であって、3つの頂点参照配列1,2,3の全てにおいて、集合1に属する頂点インデックス、または、集合2に属する頂点インデックスが記録されている面は、集合2に属するものと決定する。
図13の例では、面インデックスが“1”、“2”、“3”、“5”、“10”の面は、3つの頂点参照配列1,2,3の全てにおいて、集合1に属する頂点インデックス、または、集合2に属する頂点インデックスが記録されているので、集合2に分類されている(図14を参照)。

0066

[集合3]
集合1又は集合2に属している面以外の面は、集合3に属するものと決定する。
図13の例では、面インデックスが“4”、“7”、“8”の面は、集合1,2に属していないので、集合3に分類されている(図14を参照)。

0067

ソート部13は、ポリゴンモデルの各面が属する集合を決定すると、図14に示すように、各面の面インデックスを、集合インデックスと、当該面が属している集合内でユニークな面インデックスとの組み合わせからなるインデックス(集合インデックス−集合内面インデックス)に更新する。
例えば、集合1に属している面の面インデックスについては、“6”、“9”から“1−1”、“1−2”に更新されている。
また、集合2に属している面の面インデックスについては、“1”、“3”、“2”、“5”、“10”から“2−1”、“2−2”、“2−3”、“2−4”、“2−5”に更新されている。
さらに、集合3に属している面の面インデックスについては、“7”、“4”、“8”から“3−1”、“3−2”、“3−3”に更新されている。

0068

ソート部13は、面インデックスを更新すると、更新後の面インデックスに合わせて、頂点データに含まれている関連面を示す面インデックスを更新する。
ここで、図15は関連面を示す面インデックスが更新された頂点データを示す説明図である。
図12及び図15に示すように、例えば、頂点インデックスが“1−2”の関連面に記録されている“7”の面インデックスは“3−1”に置き換えられ、頂点インデックスが“1−4”の関連面に記録されている“1”と“3”の面インデックスは“2−1”と“2−2”に置き換えられている。
他の面インデックスについても、同様にして置き換えられている。

0069

最後に、ソート部13は、面データをHDD2に対する保存形式に合わせて整形する(ステップST15)。
即ち、ソート部13は、図14に示す面データを図16に示す面データに変換する。
図16はソート部13により変換された面データを示す説明図である。
面データの保存形式は、各面の面インデックスと、頂点参照1−1〜1−3と、頂点参照2−1〜2−3と、頂点参照3−1〜3−3と、アクティブフラグとから構成されている。

0070

各面の面インデックスとアクティブフラグは、図14の面インデックスとアクティブフラグがコピーされたものである。
頂点参照1−1〜1−3は、図14の頂点参照配列1〜3に記録されている頂点インデックスの中に、集合1に属している頂点インデックスが1つ以上ある場合、その中で最も大きい頂点インデックスがコピーされたものである。
例えば、面インデックスが“1−1”の頂点参照1−1には、図14の頂点参照配列1に記録されている“1−1”がコピーされ、頂点参照1−2には、図14の頂点参照配列2に記録されている“1−2”がコピーされ、頂点参照1−3には、図14の頂点参照配列3に記録されている“1−4”がコピーされている。

0071

頂点参照2−1〜2−3は、図14の頂点参照配列1〜3に記録されている頂点インデックスの中に、集合2に属している頂点インデックスが1つ以上ある場合、その中で最も大きい頂点インデックスがコピーされたものである。
例えば、面インデックスが“1−1”の頂点参照2−1には、図14の頂点参照配列1において、集合2に属している頂点インデックスがないため“−1”が記録されている。
頂点参照2−2には、図14の頂点参照配列2において、集合2に属している頂点インデックスがないため“−1”が記録されている。
頂点参照1−3には、図14の頂点参照配列3に記録されている“2−2”と“2−4”のうち、大きい方の“2−4”がコピーされている。

0072

頂点参照3−1〜3−3は、図14の頂点参照配列1〜3に記録されている頂点インデックスの中に、集合3に属している頂点インデックスが1つ以上ある場合、その中で最も大きい頂点インデックスがコピーされたものである。
例えば、面インデックスが“1−1”の頂点参照3−1には、図14の頂点参照配列1において、集合3に属している頂点インデックスがないため“−1”が記録されている。
また、頂点参照3−2には、図14の頂点参照配列2に記録されている“3−1”がコピーされ、頂点参照3−3には、図14の頂点参照配列3に記録されている“3−3”がコピーされている。

0073

前処理部1のデータ保存部14は、ソート部13から出力された頂点データ及び面データの分割データをHDD2に保存する処理を実施する。
即ち、データ保存部14は、ソート部13から出力された集合単位の頂点データ及び面データを1つの保存単位として、各集合を別々にHDD2に記録する。
このように、頂点データ及び面データの集合毎に、ファイルなどの論理的な1つの纏まりとすることで、実行時処理部3がHDD2に記録されている各集合に対してランダムアクセスする際、一様に一定の時間内で各集合を読み出すことが可能になる。

0074

ここで、図17は集合1に属する頂点データ及び面データがファイル1としてHDD2に記録され、集合2に属する頂点データ及び面データがファイル2としてHDD2に記録され、集合3に属する頂点データ及び面データがファイル3としてHDD2に記録されている例を示す説明図である。
図17において、○の中の数字は頂点インデックスを示し、その頂点インデックスが付されている頂点のデータ(図15における1カラム分のデータ)が記録されている。
また、□の中の数字は面インデックスを示し、その面インデックスが付されている面のデータ(図16における1カラム分のデータ)が記録されている。
なお、図17では、モデル分割部11によりブロック単位に分割されたポリゴンモデルのうち、1つのブロックのデータだけを図示しているが、実際には、全てのブロックのデータがHDD2に記録される。

0075

実行時処理部3のデータ展開部31は、前処理部1における頂点データ及び面データの記録処理が完了すると、HDD2に記録されている集合単位の頂点データ及び面データの中から、ポリゴンモデル構築部33から出力された読込命令が示す頂点データ及び面データの読み込みを行う。
この段階では、ポリゴンモデル構築部33から出力される読込命令は、集合1に属する頂点データ及び面データの読み込みを指示する命令であり、HDD2から集合1に属する頂点データ及び面データの読み込みを行う。

0076

詳細は後述するが、集合1に属する頂点データ及び面データだけでは、詳細度決定部32により決定される詳細度に対応する頂点の数を有するポリゴンモデルを構築することが不可能な場合、さらに、ポリゴンモデル構築部33から集合2に属する頂点データ及び面データの読み込みを指示する読込命令や、集合3に属する頂点データ及び面データの読み込みを指示する読込命令が出力される。
データ展開部31は、ポリゴンモデル構築部33から集合2に属する頂点データ及び面データの読み込みを指示する読込命令を受けると、HDD2から集合2に属する頂点データ及び面データの読み込みを行い、ポリゴンモデル構築部33から集合3に属する頂点データ及び面データの読み込みを指示する読込命令を受けると、HDD2から集合3に属する頂点データ及び面データの読み込みを行う。

0077

データ展開部31は、上記のようにして、HDD2から集合1に属する頂点データ及び面データの読み込みを行うと、HDD2より高速に読み書きが可能なメモリ4に対して、集合1に属する頂点データ及び面データを展開する。
なお、詳細は後述するが、データ展開部31は、ポリゴンモデル構築部33から破棄命令を受けると、メモリ4に展開済みの頂点データ及び面データの中から、その破棄命令が示す頂点データ及び面データを破棄する。

0078

実行時処理部3の詳細度決定部32は、仮想空間内の視点を示す視点情報が与えられると、前処理部1のモデル分割部11により分割されたポリゴンモデル毎に、その視点情報が示す仮想空間内の視点を考慮して、当該ポリゴンモデルに対する描画の詳細度を決定する。
即ち、詳細度決定部32は、仮想空間内の視点から分割後のポリゴンモデルが見える位置にあるか否か、仮想空間内の視点から分割後のポリゴンモデルまでの距離、あるいは、仮想空間内の視点から分割後のポリゴンモデルを見たときに当該ポリゴンモデルが分割前のポリゴンモデル(前処理部1に与えられたポリゴンモデル)の輪郭の一部を構成しているか否かなどを判断基準にして、分割前のポリゴンモデルの画像に対する分割後のポリゴンモデルの画像の寄与度を算出し、その寄与度が高い程、当該ポリゴンモデルに対する描画の詳細度を高い値に決定する。

0079

ここで、図18は詳細度決定部32による描画の詳細度の決定処理を説明する説明図である。
例えば、透視投影を用いて、3次元仮想空間を描画する場合、図18(a)に示すように、描画対象のブロックが仮想空間内の視点から近い位置に存在していれば(仮想空間内の視点からの距離が短い場合)、図18(b)に示すように、描画対象のブロックの画像は大きく描画されることになる。
このため、描画対象のブロックの画像は、全ブロック(前処理部1に与えられたポリゴンモデル)の描画結果に対する寄与度が大きくなるので、描画対象のブロックの画像を詳細に描画しなければ、全ブロックの描画結果の劣化が大きくなる。
そこで、描画対象のブロックが仮想空間内の視点から近い位置に存在している程、そのブロックに対する描画の詳細度を高い値に決定し、そのブロックに含まれるポリゴンの頂点の個数を多くする。

0080

一方、図18(c)に示すように、描画対象のブロックが仮想空間内の視点から遠い位置に存在していれば(仮想空間内の視点からの距離が長い場合)、図18(d)に示すように、描画対象のブロックの画像は小さく描画されることになる。
このため、描画対象のブロックの画像は、全ブロック(前処理部1に与えられたポリゴンモデル)の描画結果に対する寄与度が小さくなるので、そのブロックの画像を粗く描画しても、全ブロックの描画結果の劣化が小さくなる。
そこで、描画対象のブロックが仮想空間内の視点から遠い位置に存在している程、そのブロックに対する描画の詳細度を低い値に決定し、そのブロックに含まれるポリゴンの頂点の個数を少なくする。

0081

図18の例では、仮想空間内の視点から描画対象のブロックまでの距離を判断基準にして、当該ブロックの描画の詳細度を決定する(詳細度は、視点から当該ブロックまでの距離と反比例する値に決定する)ものについて示しているが、これに限るものではなく、例えば、仮想空間内の視点から描画対象のブロックが見える位置にあるか否かを判断基準にして、当該ブロックの描画の詳細度を決定するようにしてもよい。
即ち、仮想空間内の視点から描画対象のブロックが見える位置に存在している場合、当該ブロックの画像は、全ブロック(前処理部1に与えられたポリゴンモデル)の描画結果に対する寄与度が大きくなるので、描画対象のブロックの画像を詳細に描画しなければ、全ブロックの描画結果の劣化が大きくなる。
一方、仮想空間内の視点から描画対象のブロックが見えない位置に存在している場合、当該ブロックの画像は、全ブロック(前処理部1に与えられたポリゴンモデル)の描画結果に対する寄与度がゼロになる。

0082

そこで、仮想空間内の視点から描画対象のブロックが見える位置に存在している場合、そのブロックに対する描画の詳細度を高い値に決定し、そのブロックに含まれるポリゴンの頂点の個数を多くする。
一方、仮想空間内の視点から描画対象のブロックが見える位置に存在していない場合、そのブロックに対する描画の詳細度を低い値(または、0値)に決定し、そのブロックに含まれるポリゴンの頂点の個数を少なくする。

0083

また、仮想空間内の視点から描画対象のブロックを見たときに、当該ブロックが他のブロックに遮蔽されているか否かを判断基準にして、当該ブロックの描画の詳細度を決定するようにしてもよい。
仮想空間内の視点から描画対象のブロックを見たときに、当該ブロックが他のブロックに遮蔽されていない場合、当該ブロックが視界内に存在していれば、当該ブロックを見ることができる。このため、当該ブロックの画像は、全ブロック(前処理部1に与えられたポリゴンモデル)の描画結果に対する寄与度が大きくなるので、描画対象のブロックの画像を詳細に描画しなければ、全ブロックの描画結果の劣化が大きくなる。
一方、仮想空間内の視点から描画対象のブロックを見たときに、当該ブロックが他のブロックに遮蔽されている場合、当該ブロックを見ることができない。このため、当該ブロックの画像は、全ブロックの描画結果に対する寄与度がゼロになる。

0084

そこで、仮想空間内の視点から描画対象のブロックを見たときに、当該ブロックが他のブロックに遮蔽されていない場合、描画対象のブロックに対する描画の詳細度を高い値に決定し、当該ブロックに含まれるポリゴンの頂点の個数を多くする。
一方、仮想空間内の視点から描画対象のブロックを見たときに、当該ブロックが他のブロックに遮蔽されている場合、描画対象のブロックに対する描画の詳細度を低い値(または、0値)に決定し、当該ブロックに含まれるポリゴンの頂点の個数を少なくする。

0085

また、仮想空間内の視点から描画対象のブロックを見たときに、当該ブロックが全ブロック(前処理部1に与えられたポリゴンモデル)の輪郭の一部を構成しているか否かを判断基準にして、当該ブロックの描画の詳細度を決定するようにしてもよい。
仮想空間内の視点から描画対象のブロックを見たときに、当該ブロックが全ブロックの輪郭の一部を構成している場合、当該ブロックの画像は、全ブロックの描画結果に対する寄与度が大きくなるので(輪郭が変われば、ポリゴンモデルの形状が変化するので、輪郭の一部を構成している場合、寄与度が大きくなる)、描画対象のブロックの画像を詳細に描画しなければ、全ブロックの描画結果の劣化が大きくなる。
一方、仮想空間内の視点から描画対象のブロックを見たときに、当該ブロックが全ブロックの輪郭の一部を構成していない場合、当該ブロックの画像は、全ブロックの描画結果に対する寄与度が小さくなるので、描画対象のブロックの画像を粗く描画しても、全ブロックの描画結果の劣化が小さくなる。

0086

そこで、仮想空間内の視点から描画対象のブロックを見たときに、当該ブロックが全ブロックの輪郭の一部を構成している場合、描画対象のブロックに対する描画の詳細度を高い値に決定し、当該ブロックに含まれるポリゴンの頂点の個数を多くする。
一方、仮想空間内の視点から描画対象のブロックを見たときに、当該ブロックが全ブロックの輪郭の一部を構成していない場合、描画対象のブロックに対する描画の詳細度を低い値に決定し、当該ブロックに含まれるポリゴンの頂点の個数を少なくする。

0087

描画の詳細度を決定する際の判断基準として、その他、当該ブロックや視点の移動速度などを用いてもよい。
様々な判断基準を組み込むことで、全ブロックの画像に対する各ブロックの寄与度の推定精度を高めるようにしてもよい。

0088

実行時処理部のポリゴンモデル構築部33は、詳細度決定部32が詳細度を決定すると、モデル分割部11により分割されたブロック毎に、そのブロックに含まれているポリゴンモデルにおける頂点の数が、詳細度決定部32により決定された詳細度に対応する頂点の数と一致するように、メモリ4に展開されている頂点データ及び面データのアクティブフラグを更新することで、描画対象のポリゴンモデルを構築する。
以下、ポリゴンモデル構築部33の処理内容を具体的に説明する。

0089

ポリゴンモデル構築部33は、モデル分割部11により分割されたブロック単位に以下の処理を繰り返し実施して、全てのブロックに対して同様の処理を実施する。
ポリゴンモデル構築部33は、メモリ4に展開されている任意のブロックの頂点データを参照して、アクティブな頂点の数を把握し、アクティブな頂点の数が詳細度決定部32により決定された詳細度に対応する頂点の数と一致しているか否かを判定する。
なお、ポリゴンモデル構築部33は、上述したように、最初に、集合1に属する頂点データ及び面データの読み込みを指示する読込命令をデータ展開部31に出力することで、集合1に属する頂点データ及び面データがメモリ4に展開されるようにするが、ここでは、集合1に属する頂点データだけでは、詳細度決定部32により決定された詳細度に対応する頂点の数分だけ、アクティブな頂点の数が得られないために、既に、集合2に属する頂点データ及び面データの読み込みを指示する読込命令についてもデータ展開部31に出力して、集合2に属する頂点データ及び面データについてもメモリ4に展開されているものとする。

0090

図20はメモリ4に展開されている集合1,2に属する頂点データ及び面データを示す説明図である。
図20において、○はポリゴンモデルの頂点を示し、□はポリゴンモデルの面を示している。
また、アクティブな頂点及び面は、白く塗り潰されており、非アクティブな頂点及び面は、斜線で塗り潰されている。

0091

図20(a)の例では、アクティブな頂点の数が4個であるため、詳細度決定部32により決定された詳細度に対応する頂点の数(頂点の数は、詳細度決定部32により決定された詳細度が高い程、大きな値となる(詳細度に比例した値となる))が4個であれば、アクティブな頂点の数と詳細度に対応する頂点の数が一致していると判断する。
一方、詳細度決定部32により決定された詳細度に対応する頂点の数が4個でなければ、アクティブな頂点の数と詳細度に対応する頂点の数が一致していないと判断する。

0092

ポリゴンモデル構築部33は、アクティブな頂点の数と詳細度に対応する頂点の数が一致していないと判断すると、アクティブな頂点の数が詳細度に対応する頂点の数と一致するように、メモリ4に展開されている頂点データ及び面データのアクティブフラグを更新する(図19のステップST21)。
例えば、詳細度に対応する頂点の数が5個である場合、アクティブな頂点の数が1個不足しているので、図20(b)に示すように、アクティブな頂点の数を1個増やして、アクティブな頂点の数を詳細度に対応する頂点の数と一致させる。

0093

図20(a)から図20(b)への更新は、下記の手順で行う。
まず、ポリゴンモデル構築部33は、アクティブな頂点の中で、最も小さい頂点インデックスが付与されている子ノードが接続されている頂点を探索し、その頂点を非アクティブな頂点に変更する。
図20(a)の例では、頂点インデックスが“2−1”の頂点が接続されている頂点インデックスが“1−4”の頂点を非アクティブな頂点に変更している。
次に、ポリゴンモデル構築部33は、頂点インデックスが“1−4”の頂点に接続されている子ノード(頂点インデックスが“2−1”と“2−2”の頂点)をアクティブな頂点に変更して、アクティブな頂点の数を全体で1つ増加させる。
ただし、頂点インデックスの大小の判定は、最初に集合インデックスの大小を比較して判定し、集合インデックスが等しい場合は、集合内頂点インデックスの大小を比較して判定する。

0094

ポリゴンモデル構築部33は、頂点インデックスが“1−4”の頂点を非アクティブな頂点に変更すると、その非アクティブになった頂点の関連面を参照し、該当する面のアクティブフラグを更新することで、該当する面をアクティブな面に変更する。
図20(b)の例では、面インデックスが“2−1”と“2−2”の面をアクティブな面に変更している。
ここでは、アクティブな頂点の数を1個増やすことで、詳細度に対応する頂点の数に一致させるものについて示したが、詳細度に対応する頂点の数が6個以上であれば、更に、アクティブな頂点の数を増やすことで、詳細度に対応する頂点の数に一致するように更新する。
ただし、アクティブな頂点の数が、詳細度に対応する頂点の数に足りていない場合でも、アクティブな頂点の数が最大値になると(アクティブな頂点の全てが、子ノードが接続されていない頂点となった場合)、これ以上、アクティブな頂点の数を増やすことができないので、アクティブフラグの更新処理を終了する。

0095

ここまでは、アクティブな頂点の数を増やすものについて示したが、アクティブな頂点の数が、詳細度に対応する頂点の数より多い場合、アクティブな頂点の数を減らして、アクティブな頂点の数を詳細度に対応する頂点の数と一致させる。
説明の便宜上、図20(b)が更新前の頂点データ及び面データであり、図20(a)が更新後の頂点データ及び面データであるものとする。
また、詳細度に対応する頂点の数が4個であるものとする。

0096

図20(b)から図20(a)への更新は、下記の手順で行う。
まず、ポリゴンモデル構築部33は、アクティブな頂点の中で、親ノードが接続されている頂点であって、頂点インデックスが最も大きい頂点を探索し、その頂点を非アクティブな頂点に変更する。
図20(b)の例では、頂点インデックスが“2−1”と“2−2”の頂点を非アクティブな頂点に変更している。
次に、ポリゴンモデル構築部33は、頂点インデックスが“2−1”と“2−2”の頂点に接続されている親ノード(頂点インデックスが“1−4”の頂点)をアクティブな頂点に変更して、アクティブな頂点の数を全体で1つ減少させる。

0097

ポリゴンモデル構築部33は、頂点インデックスが“1−4”の頂点をアクティブな頂点に変更すると、そのアクティブになった頂点の関連面を参照し、該当する面のアクティブフラグを更新することで、該当する面を非アクティブな面に変更する。
図20(b)の例では、面インデックスが“2−1”と“2−2”の面を非アクティブな面に変更している。
ここでは、アクティブな頂点の数を1個減らすことで、詳細度に対応する頂点の数に一致させるものについて示したが、詳細度に対応する頂点の数が3個以下であれば、更に、アクティブな頂点の数を減らすことで、詳細度に対応する頂点の数に一致するように更新する。
ただし、アクティブな頂点の数が、詳細度に対応する頂点の数より多い場合でも、アクティブな頂点の数が最小値になると(アクティブな頂点の全てが、親ノードが接続されていない頂点となった場合)、これ以上、アクティブな頂点の数を減らすことができないので、アクティブフラグの更新処理を終了する。

0098

なお、アクティブな頂点の数と、詳細度決定部32により決定された詳細度に対応する頂点の数とが大きく異なる場合、一度のステップST21の処理で、頂点数が等しくなるまで、アクティブフラグの更新処理を繰り返すと、処理量が多くなったり、出力される画像内で物体の変形が顕著に現れたりすることがあるため、アクティブフラグの更新処理を一度に行わず、次回の処理に持ち越すようにしてもよい。

0099

ポリゴンモデル構築部33は、メモリ4に展開されている頂点データ及び面データのアクティブフラグの更新処理を行うと、メモリ4に展開されている頂点データ及び面データのデータ量が適切であるか否かを判定する(ステップST22)。
例えば、ステップST21において、アクティブな頂点の数が最大値になるまで更新処理を実施しても、アクティブな頂点の数が、詳細度決定部32により決定された詳細度に対応する頂点の数より少ない場合、メモリ4に展開されている頂点データ及び面データのデータ量が少ないと判断する。
一方、例えば、集合1,2に属している頂点データ及び面データがメモリ4に展開されているとき、更新後のアクティブな頂点の全てが集合1に属している場合(この場合、集合2に属している頂点データ及び面データは余分なデータである)、メモリ4に展開されている頂点データ及び面データのデータ量が多いと判断する。

0100

ポリゴンモデル構築部33は、メモリ4に展開されている頂点データ及び面データのデータ量が適切である場合、当該ブロックに対する更新処理を終了して、別のブロックに対する更新処理を同様に実施する。
ポリゴンモデル構築部33は、メモリ4に展開されている頂点データ及び面データのデータ量が不足している場合(現在、メモリ4に展開されている頂点データ及び面データだけでは、詳細度に対応する頂点の数を有するポリゴンモデルを構築することが不可能な場合)、現在、集合1に属している頂点データ及び面データがメモリ4に展開されていれば、集合2に属している頂点データ及び面データの読み込みを指示する読込命令をデータ展開部31に出力する(ステップST23)。
あるいは、現在、集合1と集合2に属している頂点データ及び面データがメモリ4に展開されていれば、集合3に属している頂点データ及び面データの読み込みを指示する読込命令をデータ展開部31に出力する(ステップST23)。

0101

ポリゴンモデル構築部33は、メモリ4に展開されている頂点データ及び面データのデータ量が多過ぎる場合(詳細度に対応する頂点の数を有するポリゴンモデルを構築する上で、余分な分割データがメモリ4に展開されている場合)、現在、集合1,2,3に属している頂点データ及び面データがメモリ4に展開されているとき、集合1,2に属している頂点データ及び面データだけで、詳細度に対応する頂点の数を有するポリゴンモデルを構築することができれば、集合3に属している頂点データ及び面データの破棄を指示する破棄命令をデータ展開部31に出力する(ステップST23)。
あるいは、現在、集合1,2に属している頂点データ及び面データがメモリ4に展開されているとき、集合1に属している頂点データ及び面データだけで、詳細度に対応する頂点の数を有するポリゴンモデルを構築することができれば、集合2に属している頂点データ及び面データの破棄を指示する破棄命令をデータ展開部31に出力する(ステップST23)。

0102

なお、ポリゴンモデル構築部33がメモリ4に展開されている頂点データ及び面データのデータ量が適切であるか否かを判定する際、使用可能なメモリ4の余り量や、視点の移動を予測して、将来的に必要性が高いデータ量を推測し、その推測結果を考慮して判定するようにしてもよい。

0103

実行時処理部3の描画処理部34は、ポリゴンモデル構築部33がアクティブフラグを更新してポリゴンモデルを構築すると、そのポリゴンモデル(ポリゴンモデル構築部33による更新後のアクティブフラグが、描画対象である旨を示している頂点からなるポリゴンモデル)の画像を、例えば内部のビデオRAM上に描画して、その画像を画像表示部5に出力する。
以下、描画処理部34の処理内容を具体的に説明する。

0104

描画処理部34は、全てのブロックにおいて、全てのアクティブな面を参照するまで、以下のステップST32〜ST35の処理を繰り返し実施する(ステップST31)。
描画処理部34は、現在、メモリ4に展開されている面データ(図16を参照)が、集合1に属している面データだけであれば、その面データに含まれている頂点参照1−1〜1−3を参照して、描画対象のポリゴンの面を構成する3個の頂点を確認する(ステップST32)。
また、メモリ4に展開されている面データが、集合1と集合2に属している面データであれば、その面データに含まれている頂点参照2−1〜2−3を参照して、描画対象のポリゴンの面を構成する3個の頂点を確認する(ステップST32)。
また、メモリ4に展開されている面データが、集合1と集合2と集合3に属している面データであれば、その面データに含まれている頂点参照3−1〜3−3を参照して、描画対象のポリゴンの面を構成する3個の頂点を確認する(ステップST32)。

0105

ただし、面データに含まれている頂点参照に“−1”が記録されている場合、参照先が存在しないため、集合インデックスが1つ小さい頂点参照を参照する(例えば、頂点参照3−1を参照したとき、頂点参照3−1に“−1”が格納されていれば、頂点参照2−1を参照し、また、頂点参照2−2を参照したとき、頂点参照2−2に“−1”が格納されていれば、頂点参照1−2を参照する)。
例えば、図20(a)に示すような頂点データ及び面データがメモリ4に展開されている場合において、アクティブな面である面インデックス“1−1”の面を描画対象とする際には、頂点参照1−1、1−2、2−3を参照して(集合1,2に属する面データが展開されているが、頂点参照2−1と2−2には、“−1”が格納されているため、頂点参照1−1、1−2を参照する)、描画対象のポリゴンの面を構成する3個の頂点が、頂点インデックスが“1−1”、“1−2”、“2−4”の頂点であることを確認する。

0106

描画処理部34は、描画対象のポリゴンの面を構成する3個の頂点を確認すると、3個の頂点のアクティブフラグを参照して(図15を参照)、3個の頂点の全てが、アクティブな頂点であるか否かを判定する(ステップST33)。
描画処理部34は、描画対象のポリゴンの面を構成する3個の頂点の中に、非アクティブな頂点が含まれている場合、非アクティブな頂点の親ノードに相当する頂点のアクティブフラグを参照して(ステップST34)、その頂点がアクティブな頂点であるか否かを判定する(ステップST33)。

0107

図20(a)の例では、頂点インデックスが“2−4”の頂点が非アクティブであるため、その頂点の親ノードに相当する頂点(頂点インデックスが“2−2”の頂点)のアクティブフラグを参照する。
頂点インデックスが“2−2”の頂点は、非アクティブな頂点であるため、更に、その頂点の親ノードに相当する頂点(頂点インデックスが“1−4”の頂点)のアクティブフラグを参照する。
頂点インデックスが“1−4”の頂点は、アクティブな頂点であるため、ステップST35の処理に移行する。
ただし、メモリ4に展開されている現在の頂点データ及び面データが、図20(a)から図20(b)に更新されている場合には、頂点インデックスが“2−2”の頂点は、アクティブな頂点であるため、頂点インデックスが“1−4”の頂点のアクティブフラグを参照することなく、ステップST35の処理に移行する。

0108

描画処理部34は、上記のようにして、3個のアクティブな頂点(メモリ4に展開されている現在の頂点データ及び面データが、図20(a)の場合には頂点インデックスが“1−1”、“1−2”、“1−4”の頂点、メモリ4に展開されている現在の頂点データ及び面データが、図20(a)から図20(b)に更新されている場合には頂点インデックスが“1−1”、“1−2”、“2−2”の頂点)を見つけると、頂点データに含まれている位置情報を参照して、3個のアクティブな頂点の三次元位置(X,Y,Z)を特定し、その三次元位置(X,Y,Z)を用いて、3個のアクティブな頂点からなる3角形ポリゴンを、例えば内部のビデオRAM上に描画する(ステップST35)。

0109

描画処理部34は、全てのブロックにおいて、全てのアクティブな面を参照することで(ステップST31)、アクティブな頂点からなる全ポリゴンを描画すると、その描画結果であるポリゴンモデル(前処理部1に与えられたポリゴンモデル)の画像を画像表示部5に出力する(ステップST36)。
これにより、画像表示部5には、ポリゴンモデルの画像が表示される。
なお、ポリゴンの3次元位置と視点の位置姿勢から画像を描画する処理については、一般的なポリゴン描画に用いられる任意の処理を利用するようにしてよい。

0110

以上で明らかなように、この実施の形態1によれば、3次元物体を表現しているポリゴンモデルを分割するモデル分割部11と、モデル分割部11により分割されたポリゴンモデル毎に、当該ポリゴンモデルを構成している1以上のポリゴンにおける既存の頂点から新たな頂点を生成し、新たな頂点を含む1以上のポリゴンモデルの頂点間の論理的な接続関係が木構造で表現されている頂点データを生成するデータ生成部12と、データ生成部12により生成された頂点データを分割して、その頂点データの分割データを出力するソート部13と、ソート部13から出力された頂点データの分割データをHDD2に保存するデータ保存部14と、HDD2により保存されている複数の分割データの中から、読込命令が示す分割データを読み込んで、その分割データをHDD2より高速に読み書きが可能なメモリ4に展開する一方、メモリ4に展開済みの分割データの中から、破棄命令が示す分割データを破棄するデータ展開部31と、モデル分割部11により分割されたポリゴンモデル毎に、仮想空間内の視点を考慮して、当該ポリゴンモデルに対する描画の詳細度を決定する詳細度決定部32と、メモリ4に展開されている分割データを参照して、詳細度決定部32により決定された詳細度に対応する頂点の数を有するポリゴンモデルを構築するとともに、読込対象の分割データを示す読込命令及び破棄対象の分割データを示す破棄命令をデータ展開部31に出力するポリゴンモデル構築部33とを設け、描画処理部34がポリゴンモデル構築部33により構築されたポリゴンモデルを描画するように構成したので、大量のデータを高速に読み書き可能な記憶装置が搭載されていなくてもLOD技術を適用して、複雑な3次元仮想環境を高速かつ高品質に描画することができる効果を奏する。

0111

即ち、この実施の形態1によれば、大容量のHDD2に保存されている全ての頂点データ及び面データの分割データ(集合単位の頂点データ及び面データ)のうち、データ展開部31がポリゴンモデル構築部33の指示の下、必要な一部の分割データ(描画の詳細度に対応する頂点の数を有するポリゴンモデルを構築することが可能な分のデータ)のみをメモリ4に展開するようにしているので、先行技術であるProgressive Meshよりも、大幅にメモリ4の消費量を低減することができる効果を奏する。

0112

なお、この実施の形態1では、前処理部1に与えられるポリゴンモデルが、頂点の三次元位置(X,Y,Z)を示す位置情報を含む頂点データと、ポリゴンの面を構成する頂点を示す頂点情報を含む面データとから構成されているものを示したが、頂点データ及び面データが、例えば、頂点及び面の法線や、面を塗り潰す際に用いるテクスチャなど、画像を描画する際に利用可能な情報を付加的に保有していてもよい。

0113

この発明は、3次元的な幾何学情報を使用して、複雑な3次元仮想環境を高速かつ高品質に描画することができる画像表示装置に適している。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ