(57)【要約】  ＨＤＤ２により保存されている複数の分割データの中から、読込命令が示す分割データを読み込んで、その分割データをＨＤＤ２より高速に読み書きが可能なメモリ４に展開するデータ展開部３１と、分割されたポリゴンモデル毎に、仮想空間内の視点を考慮して、当該ポリゴンモデルに対する描画の詳細度を決定する詳細度決定部３２と、メモリ４に展開されている分割データを参照して、詳細度決定部３２により決定された詳細度に対応する頂点の数を有するポリゴンモデルを構築するとともに、読込対象の分割データを示す読込命令をデータ展開部３１に出力するポリゴンモデル構築部３３とを設ける。
2011104746.tif 000002
【特許請求の範囲】
【請求項１】
３次元物体を表現しているポリゴンモデルを分割するモデル分割手段と、上記モデル分割手段により分割されたポリゴンモデル毎に、当該ポリゴンモデルを構成している１以上のポリゴンにおける既存の頂点から新たな頂点を生成し、新たな頂点を含む１以上のポリゴンモデルの頂点間の論理的な接続関係が木構造で表現されている頂点データを生成する頂点データ生成手段と、上記頂点データ生成手段により生成された頂点データを分割し、上記頂点データの分割データを記憶装置に保存するデータ保存手段と、上記記憶装置により保存されている複数の分割データの中から、読込命令が示す分割データを読み込んで、上記分割データを上記記憶装置より高速に読み書きが可能な記録媒体に展開する一方、上記記録媒体に展開済みの分割データの中から、破棄命令が示す分割データを破棄するデータ展開手段と、上記モデル分割手段により分割されたポリゴンモデル毎に、仮想空間内の視点を考慮して、当該ポリゴンモデルに対する描画の詳細度を決定する詳細度決定手段と、上記記録媒体に展開されている分割データを参照して、上記詳細度決定手段により決定された詳細度に対応する頂点の数を有するポリゴンモデルを構築するとともに、読込対象の分割データを示す読込命令及び破棄対象の分割データを示す破棄命令を上記データ展開手段に出力するポリゴンモデル構築手段と、上記ポリゴンモデル構築手段により構築されたポリゴンモデルを描画する描画手段とを備えた画像表示装置。
【請求項２】
頂点データ生成手段は、新たな頂点を含む１以上のポリゴンモデルの頂点毎に、三次元位置を示す情報、論理的な接続関係がある頂点を示す情報及び描画対象の頂点であるか否かを示すアクティブフラグからなる頂点データを生成することを特徴とする請求項１記載の画像表示装置。
【請求項３】
データ保存手段は、頂点データの分割データを１つの保存単位として、各分割データを別々に上記記憶装置に保存することを特徴とする請求項１記載の画像表示装置。
【請求項４】
詳細度決定手段は、仮想空間内の視点を考慮して、モデル分割手段による分割前のポリゴンモデルの画像に対する分割後のポリゴンモデルの画像の寄与度を算出し、上記寄与度が高い程、分割後のポリゴンモデルに対する描画の詳細度を高い値に決定することを特徴とする請求項１記載の画像表示装置。
【請求項５】
詳細度決定手段は、仮想空間内の視点からモデル分割手段による分割後のポリゴンモデルが見える位置にあるか否か、上記視点から分割後のポリゴンモデルまでの距離、あるいは、上記視点から分割後のポリゴンモデルを見たときに当該ポリゴンモデルが分割前のポリゴンモデルの輪郭の一部を構成しているか否かを判断基準にして、分割前のポリゴンモデルの画像に対する分割後のポリゴンモデルの画像の寄与度を算出することを特徴とする請求項４記載の画像表示装置。
【請求項６】
ポリゴンモデル構築手段は、モデル分割手段により分割されたポリゴンモデル毎に、当該ポリゴンモデルにおける頂点の数が詳細度決定手段により決定された詳細度に対応する頂点の数と一致するように、記録媒体に展開されている分割データである頂点データ及び面データに含まれているアクティブフラグを更新することで、描画対象のポリゴンモデルを構築することを特徴とする請求項２記載の画像表示装置。
【請求項７】
ポリゴンモデル構築手段は、現在、記録媒体に展開されている分割データだけでは、詳細度決定手段により決定された詳細度に対応する頂点の数を有するポリゴンモデルを構築することが不可能な場合、他の分割データの読み込みを指示する読込指令をデータ展開手段に出力する一方、上記詳細度決定手段により決定された詳細度に対応する頂点の数を有するポリゴンモデルを構築する上で、余分な分割データが上記記録媒体に展開されている場合、余分な分割データの破棄を指示する破棄指令を上記データ展開手段に出力することを特徴とする請求項１記載の画像表示装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、３次元的な幾何学情報を使用して、画像を表示する画像表示装置に関するものである。
【背景技術】
【０００２】
コンピュータグラフィックスを用いて、インタラクティブなアプリケーションを構築するには、表示装置が画像をリアルタイムに表示して、その画像を利用者に提示する必要がある。
利用者に提示される画像としては、コンピュータ内に記録されている画像のほか、その記録されている画像がコンピュータによって加工された加工画像や、記録された情報を用いて、コンピュータによって内部的に描画された画像などがある。【０００３】
特に、３次元的な仮想空間内に仮想物体を配置している環境（仮想環境）をコンピュータ内に構築し、コンピュータが、仮想視点から見た場合の仮想環境を描画して表示するには、仮想環境の３次元的な幾何学的形状や色などの多くの情報を用いて、投影処理などの複雑な処理をリアルタイムに行う必要がある。
しかし、描画される環境が複雑な場合や、コンピュータの処理性能が高くない場合には、上記の処理をリアルタイムに行うことは困難である。
なお、コンピュータ内の３次元仮想空間を表現するデータ形式としては様々なものがあるが、ここでは、描画対象となる仮想物体や環境は、仮想空間内で互いに異なる位置にある３点を結んだ面で表される三角形ポリゴンで構成されるものとする。【０００４】
従来の画像表示装置では、複雑な３次元仮想環境を高速に描画する際に、ＬＯＤ（Ｌｅｖｅｌ  Ｏｆ  Ｄｅｔａｉｌ）技術が用いられている。
ＬＯＤ技術は、描画対象となる３次元仮想環境を表す情報の一部を削減又は単純化することで、描画時間を短縮する技術である。【０００５】
例えば、以下の特許文献１に開示されているＬＯＤ技術は、次のようなものである。
まず、表示対象の物体を表すオリジナルのポリゴンモデルを簡略化し、オリジナルのポリゴンモデルと一緒に簡略化したポリゴンモデルを補助記憶装置に記録する。
次に、表示対象の物体を描画する際、その描画結果に対する各モデルの視覚的な寄与度を予測し、ある閾値よりも寄与度が高いモデルについては、補助記憶装置からオリジナルのポリゴンモデルをメモリにロードして描画を行う。
一方、ある閾値よりも寄与度が低いモデルについては、補助記憶装置から簡略化したポリゴンモデルをメモリにロードして描画を行うことで、メモリの消費量と描画時間を節約している。【０００６】
このようにして、オリジナルのポリゴンモデル又は簡略化したポリゴンモデルを適宜選択して描画を行う場合には、次のような不具合が発生することがある。
例えば、視点の移動などによって、オリジナルのポリゴンモデルと簡略化したポリゴンモデルの入れ替えが発生するとき、オリジナルのポリゴンモデルと簡略化したポリゴンモデルの形状が大きく異なっていると、ポリゴンモデルの変化が顕著に現れて、不自然さが目立ってしまうことがある。【０００７】
このとき、ポリゴンモデルを選択する際の寄与度に関する閾値を高く設定すれば、上記の不自然さを緩和することができるが、オリジナルのポリゴンモデルを利用する割合が増えるため、描画の高速化やメモリ量の削減効果が減少することになる。
また、簡略化のレベルが異なる複数のポリゴンモデルを補助記憶装置に記録し、複数の閾値に応じて複数のポリゴンモデルを入れ替えるようにすれば、上記の不自然さを緩和することができるが、補助記憶装置に記録するポリゴンモデルのデータの量が大きく増加することになる。また、補助記憶装置に対するアクセス回数も大きく増えて、ボトルネックが発生することになる。【０００８】
以下の非特許文献１には、特許文献１に開示されているＬＯＤ技術と異なる別のＬＯＤ技術として、Ｖｉｅｗ−Ｄｅｐｅｎｄｅｎｔ  Ｐｒｏｇｒｅｓｓｉｖｅ  Ｍｅｓｈが開示されている。
Ｖｉｅｗ−Ｄｅｐｅｎｄｅｎｔ  Ｐｒｏｇｒｅｓｓｉｖｅ  Ｍｅｓｈは、描画対象のポリゴンモデルのうち、描画結果に対して視覚的な寄与度が小さい部分のポリゴンの数を削減すると同時に、そのポリゴンの削減に伴う描画結果に与える影響が小さくなるように、残ったポリゴンの一部を変形するようにしている。これにより、描画結果である画像の品質を保ちつつ、描画の処理時間を短縮することができる。
また、ポリゴンの削減や、削減されたポリゴンの復元を１頂点単位で実行することができるため、常に必要最小限のポリゴン数で描画することができる。また、ポリゴン数の変化による描画対象の変形を目立ち難くすることができる。【０００９】
しかし、Ｖｉｅｗ−Ｄｅｐｅｎｔ  Ｐｒｏｇｒｅｓｓｉｖｅ  Ｍｅｓｈの場合、描画対象のポリゴンモデルのモデル情報に加えて、ポリゴンの動的な増減に必要な情報を、高速に読み出しが可能なメモリなどの記憶装置に記録しておく必要がある。
一般的なコンピュータの構成では、高速に読み書き可能な記憶装置の容量は比較的小さいので、仮想環境の規模が大きい場合、ポリゴンモデルのモデル情報やポリゴンの動的な増減に必要な情報の全て記録しておくことは困難である。
特に、組み込み機器などの比較的性能が高くない端末においては、高速に読み書きが可能な記憶装置の容量が更に小さいため、情報量が多い３次元仮想環境に対して、Ｖｉｅｗ−Ｄｅｐｅｎｔ  Ｐｒｏｇｒｅｓｓｉｖｅ  Ｍｅｓｈを適用することは困難である。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２００４−２１３６４１号公報
【非特許文献】
【００１１】
【非特許文献１】Hoppe, H., “View dependent refinement of progressive meshes,” Proc. of International Conference on Computer Graphics and Interactive Techniques, pp. 189-198, 1997.
【発明の概要】
【００１２】
従来の画像表示装置は以上のように構成されているので、描画対象となる３次元仮想環境を表す情報の一部を削減又は単純化するＬＯＤ技術を適用すれば、描画時間を短縮することができる。しかし、ＬＯＤ技術を適用する場合、オリジナルのポリゴンモデルと簡略化したポリゴンモデルの入れ替えが発生するときに生じるモデル変化に伴う不自然さを解消するには、大量のデータ（例えば、簡略化のレベルが異なる複数のポリゴンモデルや、ポリゴンの動的な増減に必要な情報など）を高速に読み書きすることが可能な記憶装置を搭載する必要がある。そのため、大量のデータを高速に読み書き可能な記憶装置が搭載されていない組み込み機器や一般的なコンピュータでは、ＬＯＤ技術を適用することができない場合があるなどの課題があった。
【００１３】
この発明は上記のような課題を解決するためになされたもので、大量のデータを高速に読み書き可能な記憶装置が搭載されていなくてもＬＯＤ技術を適用して、複雑な３次元仮想環境を高速かつ高品質に描画することができる画像表示装置を得ることを目的とする。
【００１４】
この発明に係る画像表示装置は、３次元物体を表現しているポリゴンモデルを分割するモデル分割手段と、モデル分割手段により分割されたポリゴンモデル毎に、当該ポリゴンモデルを構成している１以上のポリゴンにおける既存の頂点から新たな頂点を生成し、新たな頂点を含む１以上のポリゴンモデルの頂点間の論理的な接続関係が木構造で表現されている頂点データを生成する頂点データ生成手段と、頂点データ生成手段により生成された頂点データを分割し、その頂点データの分割データを記憶装置に保存するデータ保存手段と、その記憶装置により保存されている複数の分割データの中から、読込命令が示す分割データを読み込んで、その分割データを上記記憶装置より高速に読み書きが可能な記録媒体に展開する一方、その記録媒体に展開済みの分割データの中から、破棄命令が示す分割データを破棄するデータ展開手段と、モデル分割手段により分割されたポリゴンモデル毎に、仮想空間内の視点を考慮して、当該ポリゴンモデルに対する描画の詳細度を決定する詳細度決定手段と、その記録媒体に展開されている分割データを参照して、詳細度決定手段により決定された詳細度に対応する頂点の数を有するポリゴンモデルを構築するとともに、読込対象の分割データを示す読込命令及び破棄対象の分割データを示す破棄命令をデータ展開手段に出力するポリゴンモデル構築手段とを設け、描画手段がポリゴンモデル構築手段により構築されたポリゴンモデルを描画するようにしたものである。
【００１５】
この発明によれば、３次元物体を表現しているポリゴンモデルを分割するモデル分割手段と、モデル分割手段により分割されたポリゴンモデル毎に、当該ポリゴンモデルを構成している１以上のポリゴンにおける既存の頂点から新たな頂点を生成し、新たな頂点を含む１以上のポリゴンモデルの頂点間の論理的な接続関係が木構造で表現されている頂点データを生成する頂点データ生成手段と、頂点データ生成手段により生成された頂点データを分割し、その頂点データの分割データを記憶装置に保存するデータ保存手段と、その記憶装置により保存されている複数の分割データの中から、読込命令が示す分割データを読み込んで、その分割データを上記記憶装置より高速に読み書きが可能な記録媒体に展開する一方、その記録媒体に展開済みの分割データの中から、破棄命令が示す分割データを破棄するデータ展開手段と、モデル分割手段により分割されたポリゴンモデル毎に、仮想空間内の視点を考慮して、当該ポリゴンモデルに対する描画の詳細度を決定する詳細度決定手段と、その記録媒体に展開されている分割データを参照して、詳細度決定手段により決定された詳細度に対応する頂点の数を有するポリゴンモデルを構築するとともに、読込対象の分割データを示す読込命令及び破棄対象の分割データを示す破棄命令をデータ展開手段に出力するポリゴンモデル構築手段とを設け、描画手段がポリゴンモデル構築手段により構築されたポリゴンモデルを描画するように構成したので、大量のデータを高速に読み書き可能な記憶装置が搭載されていなくてもＬＯＤ技術を適用して、複雑な３次元仮想環境を高速かつ高品質に描画することができる効果がある。
【図面の簡単な説明】
【００１６】
【図１】この発明の実施の形態１による画像表示装置を示す構成図である。
【図２】ポリゴンモデル、頂点データ及び面データの一例を示す説明図である。
【図３】モデル分割部１１によるポリゴンモデルの分割例を示す説明図である。
【図４】前処理部１におけるデータ生成部１２の処理内容を示すフローチャートである。
【図５】ブロック単位のポリゴンモデルがデータ生成部１２の処理に伴って変化する様子を示す説明図である。
【図６】図５（ａ）のポリゴンモデルから生成される頂点データ及び面データを示す説明図である。
【図７】データ生成部１２の処理に伴って変化する頂点の論理的な接続関係を示す説明図である。
【図８】データ生成部１２により頂点データ及び面データの更新処理が一度行われた後の頂点データ及び面データを示す説明図である。
【図９】データ生成部１２による処理終了後の面データを示す説明図である。
【図１０】前処理部１におけるソート部１３の処理内容を示すフローチャートである。
【図１１】（ａ）はソート部１３により頂点インデックスが更新される前の頂点の論理的な接続関係を示し、（ｂ）はソート部１３により頂点インデックスが更新される後の頂点の論理的な接続関係を示し、（ｃ）はソート部１３により頂点が３分割された状態を示す説明図である。
【図１２】図１１（ｃ）に示す木構造の頂点を表現するデータ構造の一例を示す説明図である。
【図１３】頂点インデックス（頂点参照配列）が更新された面データを示す説明図である。
【図１４】面インデックスが更新された面データを示す説明図である。
【図１５】関連面を示す面インデックスが更新された頂点データを示す説明図である。
【図１６】ソート部１３により変換された面データを示す説明図である。
【図１７】集合１に属する頂点データ及び面データがファイル１としてＨＤＤ２に記録され、集合２に属する頂点データ及び面データがファイル２としてＨＤＤ２に記録され、集合３に属する頂点データ及び面データがファイル３としてＨＤＤ２に記録されている例を示す説明図である。
【図１８】詳細度決定部３２による描画の詳細度の決定処理を説明する説明図である。
【図１９】実行時処理部３におけるポリゴンモデル構築部３３の処理内容を示すフローチャートである。
【図２０】メモリ４に展開されている集合１，２に属する頂点データ及び面データを示す説明図である。
【図２１】実行時処理部３における描画処理部３４の処理内容を示すフローチャートである。
【発明を実施するための形態】
【００１７】
以下、この発明をより詳細に説明するために、この発明を実施するための形態について、添付の図面に従って説明する。
実施の形態１．
図１はこの発明の実施の形態１による画像表示装置を示す構成図である。
図１において、前処理部１はモデル分割部１１、データ生成部１２、ソート部１３及びデータ保存部１４から構成されており、モデル分割部１１、データ生成部１２、ソート部１３及びデータ保存部１４は、例えばＣＰＵを実装している半導体集積回路、あるいは、ワンチップマイコンなどから構成されている。
前処理部１は３次元物体を表現しているポリゴンモデルを分割し、分割後のポリゴンモデル毎に、当該ポリゴンモデルを構成している１以上のポリゴンにおける既存の頂点から新たな頂点を生成し、新たな頂点を含む１以上のポリゴンモデルの頂点間の論理的な接続関係が木構造で表現されている頂点データを生成する処理を実施する。
また、前処理部１は頂点データを分割して、その頂点データの分割データをＨＤＤ２に記録する処理を実施する。
【００１８】
ＨＤＤ２は前処理部１により生成された頂点データの分割データを記録する大容量の補助記憶装置である。
図１では、大容量の補助記憶装置としてＨＤＤ２を使用している例を示しているが、補助記憶装置はＨＤＤ２に限るものではなく、例えば、フラッシュメモリなど、容量が大きい任意の記憶媒体を用いるようにしてもよい。
【００１９】
ここで、ポリゴンモデルは、仮想空間内において、互いに異なる位置に存在している３点を接続している３本の線分によって囲まれる面の集合として表される形状であり、３本の線分によって囲まれる面は「ポリゴン」と呼ばれる。
また、ポリゴンを構成する３つの点は「ポリゴンの頂点」、ポリゴンの頂点を結ぶ３本の線分は「ポリゴンの辺」と呼ばれる。
ポリゴンモデルを表現するデータ構造は様々であるが、この実施の形態１では、一意の頂点インデックスと３次元位置からなる頂点データの集合と、一意の面インデックスとポリゴンの３頂点への参照情報からなる面データの集合とを有するデータを取り扱うものとする。
【００２０】
図２はポリゴンモデル、頂点データ及び面データの一例を示す説明図である。
（ａ）は２次元に投影されているポリゴンモデルを示しており、ポリゴンの９つの頂点を“１”から“９”までの頂点インデックスを付けて表している。
また、各頂点を結ぶ線分に囲まれているポリゴンが“１”から“１０”までの面インデックス（頂点のインデックスと区別するために、面のインデックスは括弧で括っている）を付けて表している。
（ｂ）は（ａ）のポリゴンモデルを構成する頂点データを示しており、１つのカラムが１つの頂点を表し、各カラムが一意の頂点インデックスと、ｘｙｚ軸で定義される直交座標系内の３次元位置（Ｘ，Ｙ，Ｚ）とを保有している。
【００２１】
また、（ｃ）はポリゴンの面を表す面データを示しており、１つのカラムが１つのポリゴン面を表し、各カラムが一意の面インデックスと、三角形のポリゴンを構成する３つの頂点の参照情報として、３つの頂点インデックスとを保有している。
この実施の形態１では、三角形のポリゴンモデルとしているが、前処理部１が任意の３次元形状を現すデータをポリゴンモデルに変換する手段を備えることで、任意の３次元オブジェクトを入力して、その３次元オブジェクトのデータをポリゴンモデルに変換するようにしてもよい。また、ポリゴンモデルは３次元以外の次元数を有する仮想空間内にあるものでもよい。
【００２２】
実行時処理部３はデータ展開部３１、詳細度決定部３２、ポリゴンモデル構築部３３及び描画処理部３４から構成されており、詳細度決定部３２、ポリゴンモデル構築部３３及び描画処理部３４は、例えばＣＰＵを実装している半導体集積回路、ワンチップマイコン、あるいは、ＧＰＵ（Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）などから構成されている。
実行時処理部３はＨＤＤ２により記録されている複数の分割データを読み込んで、その分割データをＨＤＤ２より高速に読み書きが可能な記録媒体であるメモリ４に展開する処理を実施し、また、前処理部１により分割されたポリゴンモデル毎に、仮想空間内の視点を考慮して、当該ポリゴンモデルに対する描画の詳細度を決定する処理を実施する。
また、実行時処理部３はメモリ４に展開済みの分割データを参照して、描画の詳細度に対応する頂点の数を有するポリゴンモデルを構築し、そのポリゴンモデルの画像を画像表示部５に表示する処理を実施する。
【００２３】
メモリ４はＨＤＤ２より記憶容量が小さいが、ＨＤＤ２より高速に読み書きが可能な記録媒体であり、例えば、ＲＡＭなどが該当する。
画像表示部５は実行時処理部３の描画処理によってポリゴンモデルを表示するディスプレイなどの出力装置である。
【００２４】
前処理部１のモデル分割部１１は３次元物体を表現しているポリゴンモデルを入力するインタフェース（例えば、ＬＡＮなどのネットワークからポリゴンモデルを入力する場合、ＬＡＮカードなどのネットワーク機器）を備えており、そのポリゴンモデルをブロック（互いの距離が近い１以上のポリゴンの集合）単位に分割する処理を実施する。なお、モデル分割部１１はモデル分割手段を構成している。
【００２５】
前処理部１のデータ生成部１２はモデル分割部１１により分割されたポリゴンモデル毎に、当該ポリゴンモデルを構成している１以上のポリゴンにおける既存の頂点から新たな頂点を生成し、新たな頂点を含む１以上のポリゴンモデルの頂点間の論理的な接続関係が木構造で表現されている頂点データを生成するとともに、１以上のポリゴンの各面に関する面データを生成する処理を実施する。
ここで、頂点データは、詳細は後述するが、図６に示すように、新たな頂点を含む１以上のポリゴンモデルの頂点毎に、当該頂点を識別する頂点インデックス、当該頂点の三次元位置を示す位置情報、当該頂点と論理的な接続関係がある頂点を示す接続情報、当該頂点が描画対象の頂点であるか否かを示すアクティブフラグなどから構成されている。
また、面データは、新たな頂点を含む１以上のポリゴンモデルの面毎に、当該面を識別する面インデックス、当該面を構成している頂点を示す頂点情報、当該面が描画対象の面であるか否かを示すアクティブフラグなどから構成されている。
【００２６】
前処理部１のソート部１３はデータ生成部１２により生成された頂点データの頂点インデックス及び面データの頂点インデックスを更新する処理や、その頂点データを分割して、その頂点データの分割データを出力する処理を実施する。
前処理部１のデータ保存部１４はソート部１３から出力された頂点データの分割データをＨＤＤ２に保存する処理を実施する。
なお、ソート部１３及びデータ保存部１４からデータ保存手段が構成されている。
【００２７】
実行時処理部３のデータ展開部３１はＨＤＤ２により保存されている複数の分割データの中から、ポリゴンモデル構築部３３から出力された読込命令が示す分割データを読み込んで、その分割データをメモリ４に展開する一方、そのメモリ４に展開済みの分割データの中から、ポリゴンモデル構築部３３から出力された破棄命令が示す分割データを破棄する処理を実施する。なお、データ展開部３１はデータ展開手段を構成している。
【００２８】
実行時処理部３の詳細度決定部３２は仮想空間内の視点を示す視点情報を入力するインタフェース（例えば、ＬＡＮなどのネットワークからポリゴンモデルを入力する場合、ＬＡＮカードなどのネットワーク機器）を備えており、前処理部１のモデル分割部１１により分割されたポリゴンモデル毎に、その視点情報が示す仮想空間内の視点を考慮して、当該ポリゴンモデルに対する描画の詳細度を決定する処理を実施する。
即ち、詳細度決定部３２は仮想空間内の視点から分割後のポリゴンモデルが見える位置にあるか否か、仮想空間内の視点から分割後のポリゴンモデルまでの距離、あるいは、仮想空間内の視点から分割後のポリゴンモデルを見たときに当該ポリゴンモデルが分割前のポリゴンモデル（前処理部１に与えられたポリゴンモデル）の輪郭の一部を構成しているか否かなどを判断基準にして、分割前のポリゴンモデルの画像に対する分割後のポリゴンモデルの画像の寄与度を算出し、その寄与度が高い程、当該ポリゴンモデルに対する描画の詳細度を高い値に決定する処理を実施する。
なお、詳細度決定部３２は詳細度決定手段を構成している。
【００２９】
実行時処理部３のポリゴンモデル構築部３３は前処理部１のモデル分割部１１により分割されたポリゴンモデル毎に、当該ポリゴンモデルにおける頂点の数が詳細度決定部３２により決定された詳細度に対応する頂点の数と一致するように、メモリ４に展開されている分割データに含まれている頂点データ及び面データのアクティブフラグを更新することで、描画対象のポリゴンモデルを構築する処理を実施する。
また、ポリゴンモデル構築部３３は読込対象の分割データを示す読込命令及び破棄対象の分割データを示す破棄命令をデータ展開部３１に出力する処理を実施する。即ち、現在、メモリ４に展開されている分割データだけでは、詳細度決定部３２により決定された詳細度に対応する頂点の数を有するポリゴンモデルを構築することが不可能な場合、他の分割データの読み込みを指示する読込指令をデータ展開部３１に出力する一方、詳細度決定部３２により決定された詳細度に対応する頂点の数を有するポリゴンモデルを構築する上で、余分な分割データがメモリ４に展開されている場合、余分な分割データの破棄を指示する破棄指令をデータ展開部３１に出力する処理を実施する。
なお、ポリゴンモデル構築部３３はポリゴンモデル構築手段を構成している。
【００３０】
実行時処理部３の描画処理部３４はポリゴンモデル構築部３３により構築されたポリゴンモデル（ポリゴンモデル構築部３３による更新後のアクティブフラグが、描画対象である旨を示している頂点からなるポリゴンモデル）の画像を、例えば内部のビデオＲＡＭ上に描画して、その画像を画像表示部５に出力する処理を実施する。なお、描画処理部３４は描画手段を構成している。
【００３１】
図１では、画像表示装置の構成要素である前処理部１、ＨＤＤ２、実行時処理部３、メモリ４及び画像表示部５のそれぞれが専用のハードウェアで構成されているものを想定しているが、画像表示装置の構成要素である前処理部１及び実行時処理部３がコンピュータで構成される場合、前処理部１及び実行時処理部３の処理内容が記述されているプログラムを当該コンピュータのメモリに格納し、当該コンピュータのＣＰＵが当該メモリに格納されているプログラムを実行するようにしてもよい。
【００３２】
ここで、図４は前処理部１におけるデータ生成部１２の処理内容を示すフローチャートである。
また、図１０は前処理部１におけるソート部１３の処理内容を示すフローチャートである。
図１９は実行時処理部３におけるポリゴンモデル構築部３３の処理内容を示すフローチャートである。
また、図２１は実行時処理部３における描画処理部３４の処理内容を示すフローチャートである。
【００３３】
次に動作について説明する。
前処理部１のモデル分割部１１は、３次元物体を表現しているポリゴンモデルを入力すると、そのポリゴンモデルをブロック（互いの距離が近い１以上のポリゴンの集合）単位に分割する。
図３はモデル分割部１１によるポリゴンモデルの分割例を示す説明図である。
図３（ａ）は分割前のポリゴンモデルを示し、図３（ｂ）は分割後のポリゴンモデルを示している。図３（ｂ）において、破線が各ブロックの境界を表している。
【００３４】
図３の例では、ポリゴンモデルの表面を単純な格子状に分割しているが、例えば、各ブロックに含まれるポリゴンの頂点の数が等しくなるように区切るなど、任意の区切り方で分割するようにしてもよい。
また、与えられたポリゴンモデルを分割することによってポリゴン面が分断されるなど、各ポリゴンの形状に変化が起こり得る場合には、予め、各ポリゴンの辺が分断面と一致するように、ポリゴンの頂点や面を加工するなどの処理（ポリゴンの形状の変化を防止する処理）を行うようにしてもよい。
【００３５】
前処理部１のデータ生成部１２は、モデル分割部１１がポリゴンモデルをブロック単位に分割すると、ブロック単位のポリゴンモデル毎に、当該ポリゴンモデルを構成している１以上のポリゴンにおける既存の頂点から新たな頂点を生成し、新たな頂点を含む１以上のポリゴンモデルの頂点間の論理的な接続関係が木構造で表現されている頂点データを生成する。
以下、データ生成部１２の処理内容を具体的に説明する。
【００３６】
まず、データ生成部１２は、初期状態の頂点データと面データを生成する。
即ち、データ生成部１２は、ブロック単位のポリゴンモデル毎に、当該ポリゴンモデルを構成している１以上のポリゴンにおける既存の頂点を“葉”とする木構造の頂点データを生成するとともに、１以上のポリゴンの各面に関する面データを生成する（図４のステップＳＴ１）。
ここで、図５はブロック単位のポリゴンモデルがデータ生成部１２の処理に伴って変化する様子を示す説明図である。
図５において、１〜１４は後述する頂点インデックスを示し、（１）〜（１０）は後述する面インデックスを示している。
また、図６は図５（ａ）のポリゴンモデルから生成される頂点データ及び面データを示す説明図である。
【００３７】
図６（ａ）は、データ生成部１２が図５（ａ）に示す１つのブロックのポリゴンモデルが与えられたとき、そのポリゴンモデルから生成する木構造の頂点データを示している。
頂点データにおける１つのカラムが１つの頂点を表しており、各カラムは、以下の（１）〜（５）の情報から構成されている。
（１）当該頂点を識別する頂点インデックス（例えば、１〜９の数字）
（２）当該頂点の三次元位置（Ｘ，Ｙ，Ｚ）を示す位置情報
（３）当該頂点と論理的な接続関係がある頂点を示す接続情報（当該頂点の親ノードに相当する頂点を示す頂点インデックスと、当該頂点の子ノードに相当する頂点を示す頂点インデックス）
ただし、この段階では、既存の頂点から新たな頂点を生成していないため（新たな頂点の生成処理は後述する）、親ノードや子ノードに相当する頂点が存在しておらず、図６（ａ）には、親ノードや子ノードに相当する頂点が無い旨を示す“−１”が接続情報に代入されている。
【００３８】
（４）後述する木構造生成の過程で削減されるポリゴン面である関連面を特定する面インデックス
ただし、この段階では、削減されているポリゴン面が存在しないので、関連面を特定する面インデックスには、“−１”が代入されている。
（５）当該頂点が描画対象の頂点であるか否かを示すアクティブフラグ（アクティブフラグが“１”（アクティブ）の場合、当該頂点が実行時処理部３で描画されることを示し、アクティブフラグが“０”（非アクティブ）の場合、当該頂点が実行時処理部３で描画されないことを示しているが、この段階では、全てのアクティブフラグが“１”（アクティブ）に初期化される）
【００３９】
図６（ｂ）は、データ生成部１２が図５（ａ）に示す１つのブロックのポリゴンモデルが与えられたとき、そのポリゴンモデルから生成する面データを示している。
面データには、入力されたブロックに含まれているポリゴンの面と同数のカラムが生成され、１つのカラムが１つの面を表している。
頂点データの各カラムは、以下の（１）〜（３）の情報から構成されている。
（１）当該面を識別する面インデックス（例えば、１〜１０の数字）
（２）当該面を構成している３つの頂点を示す頂点インデックス（頂点参照配列）
（３）当該面が描画対象の面であるか否かを示すアクティブフラグ（アクティブフラグが“１”（アクティブ）の場合、当該面が実行時処理部３で描画されることを示し、アクティブフラグが“０”（非アクティブ）の場合、当該面が実行時処理部３で描画されないことを示しているが、この段階では、削減されているポリゴン面が存在しないので、全てのアクティブフラグが“１”（アクティブ）に初期化される）
【００４０】
以降、アクティブフラグが“１”である頂点、面を、アクティブな頂点、アクティブな面と称し、アクティブフラグが“０”である頂点、面を、非アクティブな頂点、非アクティブな面と称する。
【００４１】
図７はデータ生成部１２の処理に伴って変化する頂点の論理的な接続関係を示す説明図である。
特に図７（ａ）は図６（ａ）の頂点データが示す各頂点の論理的な接続関係を示している。
図６（ａ）の頂点データにおける各頂点（頂点インデックスが“１”〜“９”の頂点）には、上述したように、親ノード及び子ノードに相当する頂点が存在していないので、他の頂点と接続されていない。
図７では、アクティブな頂点は、白く塗り潰された円で表し、非アクティブな頂点は、斜線で塗り潰された円で表している。
【００４２】
データ生成部１２は、初期状態の頂点データと面データを生成すると、その頂点データにおけるアクティブな頂点の数と予め設定されている閾値を比較する。
ここでの閾値は、予め設定される任意の数値であるが、前処理部１に与えられるポリゴンモデルが図３のように四角形のブロックに分割される場合には、当該ブロックの頂点数に相当する“４”が閾値として設定される。
また、前処理部１に与えられるポリゴンモデルが五角形のブロックに分割される場合には、当該ブロックの頂点数に相当する“５”が閾値として設定される。
ただし、閾値は、任意に設定されるものであり、ブロックが四角形であっても、“４”に限定されるものではなく、例えば、“５”や“６”などの数値（ただし、ブロックに含まれている１以上のポリゴンの頂点の数より少ない数値）であってもよい。
【００４３】
データ生成部１２は、アクティブな頂点の数が予め設定されている閾値より大きければ、以下のステップＳＴ３の処理に移行し、アクティブな頂点の数が閾値以下であれば、処理を終了する（ステップＳＴ２）。
この段階では、全ての頂点（頂点インデックスが“１”〜“９”の頂点）がアクティブな頂点であるため、アクティブな頂点の数が閾値より大きく、以下のステップＳＴ３の処理に移行する。
【００４４】
データ生成部１２は、アクティブな頂点の数が閾値より大きい場合、頂点データに含まれている全てのアクティブな頂点の中から、任意の２個の頂点（以下、「ペア」と称する）を順番に取り出し、当該ブロックに対する当該ペアの重要度を評価値として算出する（ステップＳＴ３）。
アクティブな頂点における全てのペアについて重要度を算出するため、例えば、アクティブな頂点が９個存在する場合、９Ｃ２＝３６組のペアについて重要度を算出する。
ペアとなる２個の頂点の重要度の尺度としては、例えば、ペアとなる２個の頂点間の幾何学的距離や、ペアとなる２個の頂点のうちの１頂点を削減した場合に生じるポリゴンモデルの変形量などを用いることができる。
なお、ペアの重要度を算出する際、重要度の計算時間や精度を考慮して、適正な尺度を選択するようにしてもよい。
【００４５】
データ生成部１２は、全てのペアの重要度を評価値として算出すると、最も評価値が低いペアを特定し、そのペアを構成する２個の頂点のアクティブフラグを“０”にして、その２個の頂点を非アクティブな頂点に変更する。
例えば、図５（ａ）の頂点７と頂点８のペアにおける評価値が最も低い場合、頂点７と頂点８のアクティブフラグを“０”にして、頂点７と頂点８を非アクティブな頂点にする（図７（ｂ）を参照）。
【００４６】
また、データ生成部１２は、そのペアを構成する２個の頂点のうち、いずれか一方の頂点と同じ位置にアクティブな頂点を新たに１つ生成し、頂点データにおける最大値の頂点インデックス（図６（ａ）の例では、“９”）に“１”を加えた“１０”の頂点インデックスを新たな頂点インデックスとして、その頂点データに追加する（図８（ａ）を参照）。
図８はデータ生成部１２により頂点データ及び面データの更新処理が一度行われた後の頂点データ及び面データを示す説明図である。
【００４７】
図５（ｂ）では、頂点７と同じ位置にアクティブな頂点１０を生成している例を示しているが、頂点８と同じ位置にアクティブな頂点１０を生成するようにしてもよい。
頂点７と頂点８のいずれの位置を選択するかについては特に限定するものではないが、例えば、頂点７と同じ位置にアクティブな頂点１０を生成する場合のポリゴンモデルの密度と、頂点８と同じ位置にアクティブな頂点１０を生成する場合のポリゴンモデルの密度とを計算し、ポリゴンモデルの密度が高くなる方を選択するようにしてもよい。
また、頂点７と同じ位置にアクティブな頂点１０を生成する場合のポリゴンモデルの変形量と、頂点８と同じ位置にアクティブな頂点１０を生成する場合のポリゴンモデルの変形量とを計算し、ポリゴンモデルの変形量が小さくなる方を選択するようにしてもよい。
【００４８】
また、ここでは、データ生成部１２が、ペアを構成する２個の頂点のうち、いずれか一方の頂点と同じ位置にアクティブな頂点を新たに１つ生成しているが、これに限るものではなく、例えば、２個の頂点の平均値を示す位置や、ポリゴンモデルの変形量が最も小さくなる位置にアクティブな頂点を新たに１つ生成するようにしてもよい。
【００４９】
データ生成部１２は、例えば、頂点７と頂点８を非アクティブな頂点にすると、面データを参照して、頂点７と頂点８の両方を頂点としているポリゴンの面を検索し、その面のアクティブフラグを“０”にして、その面を非アクティブな面に変更する。
図５（ａ）の例では、ポリゴンの面（４）と面（８）を非アクティブな面にしている（図８（ｂ）を参照）。
【００５０】
データ生成部１２は、アクティブフラグを更新して、新たな頂点インデックスを追加すると、頂点データと面データの更新処理を実施する（ステップＳＴ４）。
具体的には、頂点データにおいて、図８（ａ）に示すように、“１０”の頂点インデックスが付与されている頂点１０の位置情報の欄には、頂点１０の三次元位置（ｘ１０，ｙ１０，ｚ１０）を記録し、頂点１０の子ノードの欄には、頂点７と頂点８の頂点インデックスを記録し、頂点１０の関連面の欄には、非アクティブになった面（４）と面（８）の面インデックスを記録する。
また、非アクティブになった頂点７及び頂点８の親ノードの欄には、頂点１０の頂点インデックスを記録する。
なお、頂点１０のアクティブフラグとして“１”、頂点７と頂点８のアクティブフラグとして“０”を記録する。
【００５１】
面データにおいて、図８（ｂ）に示すように、“１０”の面インデックスが付与されている面（１０）を構成している頂点を示す欄には、元々記録されている非アクティブになった頂点８の頂点インデックスの前に、頂点１０の頂点インデックスを記録する。
また、頂点７又は頂点８を頂点に含んでいた面（２）、面（５）、面（６）、面（７）及び面（９）において、面を構成している頂点を示す欄には、頂点７又は頂点８の頂点インデックスの前に、頂点１０の頂点インデックスを記録する。
【００５２】
図７（ｂ）はデータ生成部１２によりステップＳＴ３，ＳＴ４の処理が一度行われた後の頂点の論理的な接続関係を示しており、図７（ｂ）では、頂点１０が新たに生成されて、アクティブな頂点から非アクティブな頂点に更新された頂点７と頂点８の親ノードとして、頂点１０が接続されている様子を示している。
【００５３】
データ生成部１２は、頂点データと面データの更新処理を実施すると、ステップＳＴ２の処理に戻り、アクティブな頂点の数が閾値以下になるまで、ステップＳＴ２〜ＳＴ４の処理を繰り返し実施する。
詳細な処理は省略するが、図５（ｃ）はデータ生成部１２によりステップＳＴ３，ＳＴ４の処理が二度行われた後のポリゴンモデルを示している。ここでは、頂点２と頂点５から新たに頂点１１が生成されている。
図７（ｃ）はデータ生成部１２によりステップＳＴ３，ＳＴ４の処理が二度行われた後の頂点の論理的な接続関係を示しており、図７（ｃ）では、頂点１１が新たに生成されて、アクティブな頂点から非アクティブな頂点に更新された頂点２と頂点５の親ノードとして、頂点１１が接続されている様子を示している。
【００５４】
図５（ｄ）はデータ生成部１２によりステップＳＴ３，ＳＴ４の処理が五度行われた後のポリゴンモデルを示している（アクティブな頂点の数が閾値と等しくなった時点のポリゴンモデル）。
図７（ｄ）はデータ生成部１２によりステップＳＴ３，ＳＴ４の処理が五度行われた後の頂点の論理的な接続関係を示している。
図９はデータ生成部１２による処理終了後の面データを示す説明図であり、図５（ｄ）及び図７（ｄ）に対応している。
【００５５】
前処理部１のソート部１３は、データ生成部１２が頂点データを生成すると、その頂点データの頂点インデックスや、面データの頂点インデックスを更新する処理を実施するほか、その頂点データを分割して、その頂点データの分割データをデータ保存部１４に出力する処理を実施する。
以下、ソート部１３の処理内容を具体的に説明する。
【００５６】
ソート部１３は、次の３つのルールにしたがって、データ生成部１２により生成された頂点データの頂点インデックスを更新する（図１０のステップＳＴ１１）。
［ルール１］
根となる頂点に対して、ユニークな整数を頂点インデックスとして付与する。
［ルール２］
根以外の頂点に対して、根の頂点インデックスの最大値及び親ノードの頂点インデックスよりも大きい頂点インデックスを付与する。また、同じ親ノードが接続されている子ノードである複数の頂点に対しては、子ノード同士で隣り合った整数を頂点インデックスとして付与する。
［ルール３］
各頂点がポリゴンモデルの形状に寄与する度合いを算出し（例えば、データ生成部１２により算出された評価値）、その度合いが高い頂点ほど、小さな頂点インデックスを付与する。
【００５７】
図１１（ａ）はソート部１３により頂点インデックスが更新される前の頂点の論理的な接続関係を示しており、図１１（ｂ）はソート部１３により頂点インデックスが更新される後の頂点の論理的な接続関係を示している。
図１１（ａ）が示す頂点の論理的な接続関係は、図７（ｄ）が示す頂点の論理的な接続関係（データ生成部１２による処理終了後の頂点の論理的な接続関係）と同じであり、データ生成部１２の処理が終了した時点では、アクティブな頂点（根となる頂点）の個数が４個である。
４個のアクティブな頂点については、ルール１，３が適用されることで、図１１（ｂ）に示すように、頂点インデックスが“１”、“１１”、“１２”、“１４”から“１”、“２”、“３”、“４”に更新されている。
【００５８】
１０個の非アクティブな頂点については、ルール２が適用されることで、４個のアクティブな頂点の頂点インデックスより大きな頂点インデックスに更新されている。
また、非アクティブな頂点に接続されている子ノード（非アクティブな頂点）については、その親ノードである非アクティブな頂点の頂点インデックスより大きな頂点インデックスに更新されている。
さらに、同じ親ノードが接続されている複数の子ノード（非アクティブな頂点）に対しては、子ノード同士で隣り合った整数を頂点インデックスに更新されている。
１０個の非アクティブな頂点についても、ルール３が適用される。
これにより、例えば、３個のアクティブな頂点に接続されている６個の非アクティブな頂点の頂点インデックスは、“２”、“５”、“３”、“６”、“４”、“１３”から“１１”、“１２”、“９”、“１０”、“５”、“６”に更新されている。
また、非アクティブな頂点に接続されている４個の非アクティブな頂点の頂点インデックスは、“９”、“１０”、“７”、“８”から“７”、“８”、“１３”、“１４”に更新されている。
【００５９】
ソート部１３は、頂点データの頂点インデックスを更新すると、予め設定された閾値を用いて、その頂点データを複数の集合に分割する（ステップＳＴ１２）。
例えば、頂点データを３つの集合に分割する場合、２つの閾値が設定され、頂点データを５つの集合に分割する場合、４つの閾値が設定される。
この実施の形態１では、説明の便宜上、頂点データを３つの集合に分割するものとして、２つの閾値が設定されているものとする。
このとき、２つの閾値として、任意の数値が設定されるが、例えば、頂点１〜４を集合１に分類し、頂点５〜１０を集合２に分類し、頂点１１〜１４を集合３に分類する場合、閾値として、“４”と“１０”が設定される。
なお、２つの閾値は、ポリゴンモデルの頂点の数に応じて動的に変更するようにしてもよい。
【００６０】
ソート部１３は、例えば、２つの閾値が設定され、２つの閾値が“４”と“１０”である場合、頂点データのうち、頂点インデックスが“４”以下の頂点（“１”、“２”、“３”、“４”の頂点インデックスが付与されている頂点）に係る頂点データを集合１（集合インデックスが“１”の集合）に分類する。
また、頂点データのうち、頂点インデックスが“４”より大きく、かつ、“１０”以下の頂点（“５”、“６”、“７”、“８”、“９”、“１０”の頂点インデックスが付与されている頂点）に係る頂点データを集合２（集合インデックスが“２”の集合）に分類する。
さらに、頂点データのうち、頂点インデックスが“１０”より大きい頂点（“１１”、“１２”、“１３”、“１４”の頂点インデックスが付与されている頂点）に係る頂点データを集合３（集合インデックスが“３”の集合）に分類する。
ただし、ソート部１３は、木構造の根となる頂点については全て同じ集合（集合インデックスが“１”の集合）に属するように分類する。このため、図１１の例では、１つの閾値が“４”に設定される。
【００６１】
ソート部１３は、頂点データを複数の集合に分割すると、各頂点の頂点インデックスを、集合インデックスと、当該頂点が属している集合内でユニークな頂点インデックスとの組み合わせからなるインデックス（集合インデックス−集合内頂点インデックス）に更新する。
例えば、集合１に属している頂点の頂点インデックスについては、“１”、“２”、“３”、“４”から“１−１”、“１−２”、“１−３”、“１−４”に更新されている。
また、集合２に属している頂点の頂点インデックスについては、“５”、“６”、“７”、“８”、“９”、“１０”から“２−１”、“２−２”、“２−３”、“２−４”、“２−５”、“２−６”に更新されている。
さらに、集合３に属している頂点の頂点インデックスについては、“１１”、“１２”、“１３”、“１４”から“３−１”、“３−２”、“３−３”、“３−４”に更新されている。
【００６２】
ここで、図１２は図１１（ｃ）に示す木構造の頂点を表現するデータ構造の一例を示す説明図である。
図１２に示すデータは、各頂点を識別する頂点インデックス、頂点の三次元位置を示す位置情報、親ノードを示す頂点インデックス、子ノードを示す頂点インデックス、関連面を示す面インデックス、アクティブフラグから構成されている。
【００６３】
ソート部１３は、頂点インデックスを更新すると、更新後の頂点インデックスに合わせて、面データに含まれている頂点インデックス（頂点参照配列）を更新する（ステップＳＴ１３）。
ここで、図１３は頂点インデックス（頂点参照配列）が更新された面データを示す説明図である。
図９及び図１３に示すように、例えば、面インデックスが“１”の頂点参照配列に記録されている“１”の頂点インデックスは“１−１”に置き換えられ、“１３”の頂点インデックスは“２−２”に置き換えられ、“９”の頂点インデックスは“２−３”に置き換えられ、“４”の頂点インデックスは“２−１”に置き換えられている。
面インデックスが“２”〜“１０”の頂点参照配列に記録されている頂点インデックスについても、同様にして置き換えられる。
【００６４】
ソート部１３は、面データに含まれている頂点インデックス（頂点参照配列）を更新すると、ポリゴンモデルの各面が属する集合を決定して、各面を識別する面インデックスを更新する（ステップＳＴ１４）。
具体的には、以下のようにして、ポリゴンモデルの各面が属する集合を決定する。
ここで、図１４は面インデックスが更新された面データを示す説明図である。
［集合１］
面データに含まれている３つの頂点参照配列１，２，３の全てにおいて、集合１に属する頂点インデックスが１つ以上記録されている面は、集合１に属するものと決定する。
図１３の例では、面インデックスが“６”と“９”の面は、３つの頂点参照配列１，２，３の全てにおいて、集合１に属する頂点インデックスが１つ以上記録されているので、集合１に分類されている（図１４を参照）。
【００６５】
［集合２］
集合１に属している面以外の面であって、３つの頂点参照配列１，２，３の全てにおいて、集合１に属する頂点インデックス、または、集合２に属する頂点インデックスが記録されている面は、集合２に属するものと決定する。
図１３の例では、面インデックスが“１”、“２”、“３”、“５”、“１０”の面は、３つの頂点参照配列１，２，３の全てにおいて、集合１に属する頂点インデックス、または、集合２に属する頂点インデックスが記録されているので、集合２に分類されている（図１４を参照）。
【００６６】
［集合３］
集合１又は集合２に属している面以外の面は、集合３に属するものと決定する。
図１３の例では、面インデックスが“４”、“７”、“８”の面は、集合１，２に属していないので、集合３に分類されている（図１４を参照）。
【００６７】
ソート部１３は、ポリゴンモデルの各面が属する集合を決定すると、図１４に示すように、各面の面インデックスを、集合インデックスと、当該面が属している集合内でユニークな面インデックスとの組み合わせからなるインデックス（集合インデックス−集合内面インデックス）に更新する。
例えば、集合１に属している面の面インデックスについては、“６”、“９”から“１−１”、“１−２”に更新されている。
また、集合２に属している面の面インデックスについては、“１”、“３”、“２”、“５”、“１０”から“２−１”、“２−２”、“２−３”、“２−４”、“２−５”に更新されている。
さらに、集合３に属している面の面インデックスについては、“７”、“４”、“８”から“３−１”、“３−２”、“３−３”に更新されている。
【００６８】
ソート部１３は、面インデックスを更新すると、更新後の面インデックスに合わせて、頂点データに含まれている関連面を示す面インデックスを更新する。
ここで、図１５は関連面を示す面インデックスが更新された頂点データを示す説明図である。
図１２及び図１５に示すように、例えば、頂点インデックスが“１−２”の関連面に記録されている“７”の面インデックスは“３−１”に置き換えられ、頂点インデックスが“１−４”の関連面に記録されている“１”と“３”の面インデックスは“２−１”と“２−２”に置き換えられている。
他の面インデックスについても、同様にして置き換えられている。
【００６９】
最後に、ソート部１３は、面データをＨＤＤ２に対する保存形式に合わせて整形する（ステップＳＴ１５）。
即ち、ソート部１３は、図１４に示す面データを図１６に示す面データに変換する。
図１６はソート部１３により変換された面データを示す説明図である。
面データの保存形式は、各面の面インデックスと、頂点参照１−１〜１−３と、頂点参照２−１〜２−３と、頂点参照３−１〜３−３と、アクティブフラグとから構成されている。
【００７０】
各面の面インデックスとアクティブフラグは、図１４の面インデックスとアクティブフラグがコピーされたものである。
頂点参照１−１〜１−３は、図１４の頂点参照配列１〜３に記録されている頂点インデックスの中に、集合１に属している頂点インデックスが１つ以上ある場合、その中で最も大きい頂点インデックスがコピーされたものである。
例えば、面インデックスが“１−１”の頂点参照１−１には、図１４の頂点参照配列１に記録されている“１−１”がコピーされ、頂点参照１−２には、図１４の頂点参照配列２に記録されている“１−２”がコピーされ、頂点参照１−３には、図１４の頂点参照配列３に記録されている“１−４”がコピーされている。
【００７１】
頂点参照２−１〜２−３は、図１４の頂点参照配列１〜３に記録されている頂点インデックスの中に、集合２に属している頂点インデックスが１つ以上ある場合、その中で最も大きい頂点インデックスがコピーされたものである。
例えば、面インデックスが“１−１”の頂点参照２−１には、図１４の頂点参照配列１において、集合２に属している頂点インデックスがないため“−１”が記録されている。
頂点参照２−２には、図１４の頂点参照配列２において、集合２に属している頂点インデックスがないため“−１”が記録されている。
頂点参照１−３には、図１４の頂点参照配列３に記録されている“２−２”と“２−４”のうち、大きい方の“２−４”がコピーされている。
【００７２】
頂点参照３−１〜３−３は、図１４の頂点参照配列１〜３に記録されている頂点インデックスの中に、集合３に属している頂点インデックスが１つ以上ある場合、その中で最も大きい頂点インデックスがコピーされたものである。
例えば、面インデックスが“１−１”の頂点参照３−１には、図１４の頂点参照配列１において、集合３に属している頂点インデックスがないため“−１”が記録されている。
また、頂点参照３−２には、図１４の頂点参照配列２に記録されている“３−１”がコピーされ、頂点参照３−３には、図１４の頂点参照配列３に記録されている“３−３”がコピーされている。
【００７３】
前処理部１のデータ保存部１４は、ソート部１３から出力された頂点データ及び面データの分割データをＨＤＤ２に保存する処理を実施する。
即ち、データ保存部１４は、ソート部１３から出力された集合単位の頂点データ及び面データを１つの保存単位として、各集合を別々にＨＤＤ２に記録する。
このように、頂点データ及び面データの集合毎に、ファイルなどの論理的な１つの纏まりとすることで、実行時処理部３がＨＤＤ２に記録されている各集合に対してランダムアクセスする際、一様に一定の時間内で各集合を読み出すことが可能になる。
【００７４】
ここで、図１７は集合１に属する頂点データ及び面データがファイル１としてＨＤＤ２に記録され、集合２に属する頂点データ及び面データがファイル２としてＨＤＤ２に記録され、集合３に属する頂点データ及び面データがファイル３としてＨＤＤ２に記録されている例を示す説明図である。
図１７において、○の中の数字は頂点インデックスを示し、その頂点インデックスが付されている頂点のデータ（図１５における１カラム分のデータ）が記録されている。
また、□の中の数字は面インデックスを示し、その面インデックスが付されている面のデータ（図１６における１カラム分のデータ）が記録されている。
なお、図１７では、モデル分割部１１によりブロック単位に分割されたポリゴンモデルのうち、１つのブロックのデータだけを図示しているが、実際には、全てのブロックのデータがＨＤＤ２に記録される。
【００７５】
実行時処理部３のデータ展開部３１は、前処理部１における頂点データ及び面データの記録処理が完了すると、ＨＤＤ２に記録されている集合単位の頂点データ及び面データの中から、ポリゴンモデル構築部３３から出力された読込命令が示す頂点データ及び面データの読み込みを行う。
この段階では、ポリゴンモデル構築部３３から出力される読込命令は、集合１に属する頂点データ及び面データの読み込みを指示する命令であり、ＨＤＤ２から集合１に属する頂点データ及び面データの読み込みを行う。
【００７６】
詳細は後述するが、集合１に属する頂点データ及び面データだけでは、詳細度決定部３２により決定される詳細度に対応する頂点の数を有するポリゴンモデルを構築することが不可能な場合、さらに、ポリゴンモデル構築部３３から集合２に属する頂点データ及び面データの読み込みを指示する読込命令や、集合３に属する頂点データ及び面データの読み込みを指示する読込命令が出力される。
データ展開部３１は、ポリゴンモデル構築部３３から集合２に属する頂点データ及び面データの読み込みを指示する読込命令を受けると、ＨＤＤ２から集合２に属する頂点データ及び面データの読み込みを行い、ポリゴンモデル構築部３３から集合３に属する頂点データ及び面データの読み込みを指示する読込命令を受けると、ＨＤＤ２から集合３に属する頂点データ及び面データの読み込みを行う。
【００７７】
データ展開部３１は、上記のようにして、ＨＤＤ２から集合１に属する頂点データ及び面データの読み込みを行うと、ＨＤＤ２より高速に読み書きが可能なメモリ４に対して、集合１に属する頂点データ及び面データを展開する。
なお、詳細は後述するが、データ展開部３１は、ポリゴンモデル構築部３３から破棄命令を受けると、メモリ４に展開済みの頂点データ及び面データの中から、その破棄命令が示す頂点データ及び面データを破棄する。
【００７８】
実行時処理部３の詳細度決定部３２は、仮想空間内の視点を示す視点情報が与えられると、前処理部１のモデル分割部１１により分割されたポリゴンモデル毎に、その視点情報が示す仮想空間内の視点を考慮して、当該ポリゴンモデルに対する描画の詳細度を決定する。
即ち、詳細度決定部３２は、仮想空間内の視点から分割後のポリゴンモデルが見える位置にあるか否か、仮想空間内の視点から分割後のポリゴンモデルまでの距離、あるいは、仮想空間内の視点から分割後のポリゴンモデルを見たときに当該ポリゴンモデルが分割前のポリゴンモデル（前処理部１に与えられたポリゴンモデル）の輪郭の一部を構成しているか否かなどを判断基準にして、分割前のポリゴンモデルの画像に対する分割後のポリゴンモデルの画像の寄与度を算出し、その寄与度が高い程、当該ポリゴンモデルに対する描画の詳細度を高い値に決定する。
【００７９】
ここで、図１８は詳細度決定部３２による描画の詳細度の決定処理を説明する説明図である。
例えば、透視投影を用いて、３次元仮想空間を描画する場合、図１８（ａ）に示すように、描画対象のブロックが仮想空間内の視点から近い位置に存在していれば（仮想空間内の視点からの距離が短い場合）、図１８（ｂ）に示すように、描画対象のブロックの画像は大きく描画されることになる。
このため、描画対象のブロックの画像は、全ブロック（前処理部１に与えられたポリゴンモデル）の描画結果に対する寄与度が大きくなるので、描画対象のブロックの画像を詳細に描画しなければ、全ブロックの描画結果の劣化が大きくなる。
そこで、描画対象のブロックが仮想空間内の視点から近い位置に存在している程、そのブロックに対する描画の詳細度を高い値に決定し、そのブロックに含まれるポリゴンの頂点の個数を多くする。
【００８０】
一方、図１８（ｃ）に示すように、描画対象のブロックが仮想空間内の視点から遠い位置に存在していれば（仮想空間内の視点からの距離が長い場合）、図１８（ｄ）に示すように、描画対象のブロックの画像は小さく描画されることになる。
このため、描画対象のブロックの画像は、全ブロック（前処理部１に与えられたポリゴンモデル）の描画結果に対する寄与度が小さくなるので、そのブロックの画像を粗く描画しても、全ブロックの描画結果の劣化が小さくなる。
そこで、描画対象のブロックが仮想空間内の視点から遠い位置に存在している程、そのブロックに対する描画の詳細度を低い値に決定し、そのブロックに含まれるポリゴンの頂点の個数を少なくする。
【００８１】
図１８の例では、仮想空間内の視点から描画対象のブロックまでの距離を判断基準にして、当該ブロックの描画の詳細度を決定する（詳細度は、視点から当該ブロックまでの距離と反比例する値に決定する）ものについて示しているが、これに限るものではなく、例えば、仮想空間内の視点から描画対象のブロックが見える位置にあるか否かを判断基準にして、当該ブロックの描画の詳細度を決定するようにしてもよい。
即ち、仮想空間内の視点から描画対象のブロックが見える位置に存在している場合、当該ブロックの画像は、全ブロック（前処理部１に与えられたポリゴンモデル）の描画結果に対する寄与度が大きくなるので、描画対象のブロックの画像を詳細に描画しなければ、全ブロックの描画結果の劣化が大きくなる。
一方、仮想空間内の視点から描画対象のブロックが見えない位置に存在している場合、当該ブロックの画像は、全ブロック（前処理部１に与えられたポリゴンモデル）の描画結果に対する寄与度がゼロになる。
【００８２】
そこで、仮想空間内の視点から描画対象のブロックが見える位置に存在している場合、そのブロックに対する描画の詳細度を高い値に決定し、そのブロックに含まれるポリゴンの頂点の個数を多くする。
一方、仮想空間内の視点から描画対象のブロックが見える位置に存在していない場合、そのブロックに対する描画の詳細度を低い値（または、０値）に決定し、そのブロックに含まれるポリゴンの頂点の個数を少なくする。
【００８３】
また、仮想空間内の視点から描画対象のブロックを見たときに、当該ブロックが他のブロックに遮蔽されているか否かを判断基準にして、当該ブロックの描画の詳細度を決定するようにしてもよい。
仮想空間内の視点から描画対象のブロックを見たときに、当該ブロックが他のブロックに遮蔽されていない場合、当該ブロックが視界内に存在していれば、当該ブロックを見ることができる。このため、当該ブロックの画像は、全ブロック（前処理部１に与えられたポリゴンモデル）の描画結果に対する寄与度が大きくなるので、描画対象のブロックの画像を詳細に描画しなければ、全ブロックの描画結果の劣化が大きくなる。
一方、仮想空間内の視点から描画対象のブロックを見たときに、当該ブロックが他のブロックに遮蔽されている場合、当該ブロックを見ることができない。このため、当該ブロックの画像は、全ブロックの描画結果に対する寄与度がゼロになる。
【００８４】
そこで、仮想空間内の視点から描画対象のブロックを見たときに、当該ブロックが他のブロックに遮蔽されていない場合、描画対象のブロックに対する描画の詳細度を高い値に決定し、当該ブロックに含まれるポリゴンの頂点の個数を多くする。
一方、仮想空間内の視点から描画対象のブロックを見たときに、当該ブロックが他のブロックに遮蔽されている場合、描画対象のブロックに対する描画の詳細度を低い値（または、０値）に決定し、当該ブロックに含まれるポリゴンの頂点の個数を少なくする。
【００８５】
また、仮想空間内の視点から描画対象のブロックを見たときに、当該ブロックが全ブロック（前処理部１に与えられたポリゴンモデル）の輪郭の一部を構成しているか否かを判断基準にして、当該ブロックの描画の詳細度を決定するようにしてもよい。
仮想空間内の視点から描画対象のブロックを見たときに、当該ブロックが全ブロックの輪郭の一部を構成している場合、当該ブロックの画像は、全ブロックの描画結果に対する寄与度が大きくなるので（輪郭が変われば、ポリゴンモデルの形状が変化するので、輪郭の一部を構成している場合、寄与度が大きくなる）、描画対象のブロックの画像を詳細に描画しなければ、全ブロックの描画結果の劣化が大きくなる。
一方、仮想空間内の視点から描画対象のブロックを見たときに、当該ブロックが全ブロックの輪郭の一部を構成していない場合、当該ブロックの画像は、全ブロックの描画結果に対する寄与度が小さくなるので、描画対象のブロックの画像を粗く描画しても、全ブロックの描画結果の劣化が小さくなる。
【００８６】
そこで、仮想空間内の視点から描画対象のブロックを見たときに、当該ブロックが全ブロックの輪郭の一部を構成している場合、描画対象のブロックに対する描画の詳細度を高い値に決定し、当該ブロックに含まれるポリゴンの頂点の個数を多くする。
一方、仮想空間内の視点から描画対象のブロックを見たときに、当該ブロックが全ブロックの輪郭の一部を構成していない場合、描画対象のブロックに対する描画の詳細度を低い値に決定し、当該ブロックに含まれるポリゴンの頂点の個数を少なくする。
【００８７】
描画の詳細度を決定する際の判断基準として、その他、当該ブロックや視点の移動速度などを用いてもよい。
様々な判断基準を組み込むことで、全ブロックの画像に対する各ブロックの寄与度の推定精度を高めるようにしてもよい。
【００８８】
実行時処理部のポリゴンモデル構築部３３は、詳細度決定部３２が詳細度を決定すると、モデル分割部１１により分割されたブロック毎に、そのブロックに含まれているポリゴンモデルにおける頂点の数が、詳細度決定部３２により決定された詳細度に対応する頂点の数と一致するように、メモリ４に展開されている頂点データ及び面データのアクティブフラグを更新することで、描画対象のポリゴンモデルを構築する。
以下、ポリゴンモデル構築部３３の処理内容を具体的に説明する。
【００８９】
ポリゴンモデル構築部３３は、モデル分割部１１により分割されたブロック単位に以下の処理を繰り返し実施して、全てのブロックに対して同様の処理を実施する。
ポリゴンモデル構築部３３は、メモリ４に展開されている任意のブロックの頂点データを参照して、アクティブな頂点の数を把握し、アクティブな頂点の数が詳細度決定部３２により決定された詳細度に対応する頂点の数と一致しているか否かを判定する。
なお、ポリゴンモデル構築部３３は、上述したように、最初に、集合１に属する頂点データ及び面データの読み込みを指示する読込命令をデータ展開部３１に出力することで、集合１に属する頂点データ及び面データがメモリ４に展開されるようにするが、ここでは、集合１に属する頂点データだけでは、詳細度決定部３２により決定された詳細度に対応する頂点の数分だけ、アクティブな頂点の数が得られないために、既に、集合２に属する頂点データ及び面データの読み込みを指示する読込命令についてもデータ展開部３１に出力して、集合２に属する頂点データ及び面データについてもメモリ４に展開されているものとする。
【００９０】
図２０はメモリ４に展開されている集合１，２に属する頂点データ及び面データを示す説明図である。
図２０において、○はポリゴンモデルの頂点を示し、□はポリゴンモデルの面を示している。
また、アクティブな頂点及び面は、白く塗り潰されており、非アクティブな頂点及び面は、斜線で塗り潰されている。
【００９１】
図２０（ａ）の例では、アクティブな頂点の数が４個であるため、詳細度決定部３２により決定された詳細度に対応する頂点の数（頂点の数は、詳細度決定部３２により決定された詳細度が高い程、大きな値となる（詳細度に比例した値となる））が４個であれば、アクティブな頂点の数と詳細度に対応する頂点の数が一致していると判断する。
一方、詳細度決定部３２により決定された詳細度に対応する頂点の数が４個でなければ、アクティブな頂点の数と詳細度に対応する頂点の数が一致していないと判断する。
【００９２】
ポリゴンモデル構築部３３は、アクティブな頂点の数と詳細度に対応する頂点の数が一致していないと判断すると、アクティブな頂点の数が詳細度に対応する頂点の数と一致するように、メモリ４に展開されている頂点データ及び面データのアクティブフラグを更新する（図１９のステップＳＴ２１）。
例えば、詳細度に対応する頂点の数が５個である場合、アクティブな頂点の数が１個不足しているので、図２０（ｂ）に示すように、アクティブな頂点の数を１個増やして、アクティブな頂点の数を詳細度に対応する頂点の数と一致させる。
【００９３】
図２０（ａ）から図２０（ｂ）への更新は、下記の手順で行う。
まず、ポリゴンモデル構築部３３は、アクティブな頂点の中で、最も小さい頂点インデックスが付与されている子ノードが接続されている頂点を探索し、その頂点を非アクティブな頂点に変更する。
図２０（ａ）の例では、頂点インデックスが“２−１”の頂点が接続されている頂点インデックスが“１−４”の頂点を非アクティブな頂点に変更している。
次に、ポリゴンモデル構築部３３は、頂点インデックスが“１−４”の頂点に接続されている子ノード（頂点インデックスが“２−１”と“２−２”の頂点）をアクティブな頂点に変更して、アクティブな頂点の数を全体で１つ増加させる。
ただし、頂点インデックスの大小の判定は、最初に集合インデックスの大小を比較して判定し、集合インデックスが等しい場合は、集合内頂点インデックスの大小を比較して判定する。
【００９４】
ポリゴンモデル構築部３３は、頂点インデックスが“１−４”の頂点を非アクティブな頂点に変更すると、その非アクティブになった頂点の関連面を参照し、該当する面のアクティブフラグを更新することで、該当する面をアクティブな面に変更する。
図２０（ｂ）の例では、面インデックスが“２−１”と“２−２”の面をアクティブな面に変更している。
ここでは、アクティブな頂点の数を１個増やすことで、詳細度に対応する頂点の数に一致させるものについて示したが、詳細度に対応する頂点の数が６個以上であれば、更に、アクティブな頂点の数を増やすことで、詳細度に対応する頂点の数に一致するように更新する。
ただし、アクティブな頂点の数が、詳細度に対応する頂点の数に足りていない場合でも、アクティブな頂点の数が最大値になると（アクティブな頂点の全てが、子ノードが接続されていない頂点となった場合）、これ以上、アクティブな頂点の数を増やすことができないので、アクティブフラグの更新処理を終了する。
【００９５】
ここまでは、アクティブな頂点の数を増やすものについて示したが、アクティブな頂点の数が、詳細度に対応する頂点の数より多い場合、アクティブな頂点の数を減らして、アクティブな頂点の数を詳細度に対応する頂点の数と一致させる。
説明の便宜上、図２０（ｂ）が更新前の頂点データ及び面データであり、図２０（ａ）が更新後の頂点データ及び面データであるものとする。
また、詳細度に対応する頂点の数が４個であるものとする。
【００９６】
図２０（ｂ）から図２０（ａ）への更新は、下記の手順で行う。
まず、ポリゴンモデル構築部３３は、アクティブな頂点の中で、親ノードが接続されている頂点であって、頂点インデックスが最も大きい頂点を探索し、その頂点を非アクティブな頂点に変更する。
図２０（ｂ）の例では、頂点インデックスが“２−１”と“２−２”の頂点を非アクティブな頂点に変更している。
次に、ポリゴンモデル構築部３３は、頂点インデックスが“２−１”と“２−２”の頂点に接続されている親ノード（頂点インデックスが“１−４”の頂点）をアクティブな頂点に変更して、アクティブな頂点の数を全体で１つ減少させる。
【００９７】
ポリゴンモデル構築部３３は、頂点インデックスが“１−４”の頂点をアクティブな頂点に変更すると、そのアクティブになった頂点の関連面を参照し、該当する面のアクティブフラグを更新することで、該当する面を非アクティブな面に変更する。
図２０（ｂ）の例では、面インデックスが“２−１”と“２−２”の面を非アクティブな面に変更している。
ここでは、アクティブな頂点の数を１個減らすことで、詳細度に対応する頂点の数に一致させるものについて示したが、詳細度に対応する頂点の数が３個以下であれば、更に、アクティブな頂点の数を減らすことで、詳細度に対応する頂点の数に一致するように更新する。
ただし、アクティブな頂点の数が、詳細度に対応する頂点の数より多い場合でも、アクティブな頂点の数が最小値になると（アクティブな頂点の全てが、親ノードが接続されていない頂点となった場合）、これ以上、アクティブな頂点の数を減らすことができないので、アクティブフラグの更新処理を終了する。
【００９８】
なお、アクティブな頂点の数と、詳細度決定部３２により決定された詳細度に対応する頂点の数とが大きく異なる場合、一度のステップＳＴ２１の処理で、頂点数が等しくなるまで、アクティブフラグの更新処理を繰り返すと、処理量が多くなったり、出力される画像内で物体の変形が顕著に現れたりすることがあるため、アクティブフラグの更新処理を一度に行わず、次回の処理に持ち越すようにしてもよい。
【００９９】
ポリゴンモデル構築部３３は、メモリ４に展開されている頂点データ及び面データのアクティブフラグの更新処理を行うと、メモリ４に展開されている頂点データ及び面データのデータ量が適切であるか否かを判定する（ステップＳＴ２２）。
例えば、ステップＳＴ２１において、アクティブな頂点の数が最大値になるまで更新処理を実施しても、アクティブな頂点の数が、詳細度決定部３２により決定された詳細度に対応する頂点の数より少ない場合、メモリ４に展開されている頂点データ及び面データのデータ量が少ないと判断する。
一方、例えば、集合１，２に属している頂点データ及び面データがメモリ４に展開されているとき、更新後のアクティブな頂点の全てが集合１に属している場合（この場合、集合２に属している頂点データ及び面データは余分なデータである）、メモリ４に展開されている頂点データ及び面データのデータ量が多いと判断する。
【０１００】
ポリゴンモデル構築部３３は、メモリ４に展開されている頂点データ及び面データのデータ量が適切である場合、当該ブロックに対する更新処理を終了して、別のブロックに対する更新処理を同様に実施する。
ポリゴンモデル構築部３３は、メモリ４に展開されている頂点データ及び面データのデータ量が不足している場合（現在、メモリ４に展開されている頂点データ及び面データだけでは、詳細度に対応する頂点の数を有するポリゴンモデルを構築することが不可能な場合）、現在、集合１に属している頂点データ及び面データがメモリ４に展開されていれば、集合２に属している頂点データ及び面データの読み込みを指示する読込命令をデータ展開部３１に出力する（ステップＳＴ２３）。
あるいは、現在、集合１と集合２に属している頂点データ及び面データがメモリ４に展開されていれば、集合３に属している頂点データ及び面データの読み込みを指示する読込命令をデータ展開部３１に出力する（ステップＳＴ２３）。
【０１０１】
ポリゴンモデル構築部３３は、メモリ４に展開されている頂点データ及び面データのデータ量が多過ぎる場合（詳細度に対応する頂点の数を有するポリゴンモデルを構築する上で、余分な分割データがメモリ４に展開されている場合）、現在、集合１，２，３に属している頂点データ及び面データがメモリ４に展開されているとき、集合１，２に属している頂点データ及び面データだけで、詳細度に対応する頂点の数を有するポリゴンモデルを構築することができれば、集合３に属している頂点データ及び面データの破棄を指示する破棄命令をデータ展開部３１に出力する（ステップＳＴ２３）。
あるいは、現在、集合１，２に属している頂点データ及び面データがメモリ４に展開されているとき、集合１に属している頂点データ及び面データだけで、詳細度に対応する頂点の数を有するポリゴンモデルを構築することができれば、集合２に属している頂点データ及び面データの破棄を指示する破棄命令をデータ展開部３１に出力する（ステップＳＴ２３）。
【０１０２】
なお、ポリゴンモデル構築部３３がメモリ４に展開されている頂点データ及び面データのデータ量が適切であるか否かを判定する際、使用可能なメモリ４の余り量や、視点の移動を予測して、将来的に必要性が高いデータ量を推測し、その推測結果を考慮して判定するようにしてもよい。
【０１０３】
実行時処理部３の描画処理部３４は、ポリゴンモデル構築部３３がアクティブフラグを更新してポリゴンモデルを構築すると、そのポリゴンモデル（ポリゴンモデル構築部３３による更新後のアクティブフラグが、描画対象である旨を示している頂点からなるポリゴンモデル）の画像を、例えば内部のビデオＲＡＭ上に描画して、その画像を画像表示部５に出力する。
以下、描画処理部３４の処理内容を具体的に説明する。
【０１０４】
描画処理部３４は、全てのブロックにおいて、全てのアクティブな面を参照するまで、以下のステップＳＴ３２〜ＳＴ３５の処理を繰り返し実施する（ステップＳＴ３１）。
描画処理部３４は、現在、メモリ４に展開されている面データ（図１６を参照）が、集合１に属している面データだけであれば、その面データに含まれている頂点参照１−１〜１−３を参照して、描画対象のポリゴンの面を構成する３個の頂点を確認する（ステップＳＴ３２）。
また、メモリ４に展開されている面データが、集合１と集合２に属している面データであれば、その面データに含まれている頂点参照２−１〜２−３を参照して、描画対象のポリゴンの面を構成する３個の頂点を確認する（ステップＳＴ３２）。
また、メモリ４に展開されている面データが、集合１と集合２と集合３に属している面データであれば、その面データに含まれている頂点参照３−１〜３−３を参照して、描画対象のポリゴンの面を構成する３個の頂点を確認する（ステップＳＴ３２）。
【０１０５】
ただし、面データに含まれている頂点参照に“−１”が記録されている場合、参照先が存在しないため、集合インデックスが１つ小さい頂点参照を参照する（例えば、頂点参照３−１を参照したとき、頂点参照３−１に“−１”が格納されていれば、頂点参照２−１を参照し、また、頂点参照２−２を参照したとき、頂点参照２−２に“−１”が格納されていれば、頂点参照１−２を参照する）。
例えば、図２０（ａ）に示すような頂点データ及び面データがメモリ４に展開されている場合において、アクティブな面である面インデックス“１−１”の面を描画対象とする際には、頂点参照１−１、１−２、２−３を参照して（集合１，２に属する面データが展開されているが、頂点参照２−１と２−２には、“−１”が格納されているため、頂点参照１−１、１−２を参照する）、描画対象のポリゴンの面を構成する３個の頂点が、頂点インデックスが“１−１”、“１−２”、“２−４”の頂点であることを確認する。
【０１０６】
描画処理部３４は、描画対象のポリゴンの面を構成する３個の頂点を確認すると、３個の頂点のアクティブフラグを参照して（図１５を参照）、３個の頂点の全てが、アクティブな頂点であるか否かを判定する（ステップＳＴ３３）。
描画処理部３４は、描画対象のポリゴンの面を構成する３個の頂点の中に、非アクティブな頂点が含まれている場合、非アクティブな頂点の親ノードに相当する頂点のアクティブフラグを参照して（ステップＳＴ３４）、その頂点がアクティブな頂点であるか否かを判定する（ステップＳＴ３３）。
【０１０７】
図２０（ａ）の例では、頂点インデックスが“２−４”の頂点が非アクティブであるため、その頂点の親ノードに相当する頂点（頂点インデックスが“２−２”の頂点）のアクティブフラグを参照する。
頂点インデックスが“２−２”の頂点は、非アクティブな頂点であるため、更に、その頂点の親ノードに相当する頂点（頂点インデックスが“１−４”の頂点）のアクティブフラグを参照する。
頂点インデックスが“１−４”の頂点は、アクティブな頂点であるため、ステップＳＴ３５の処理に移行する。
ただし、メモリ４に展開されている現在の頂点データ及び面データが、図２０（ａ）から図２０（ｂ）に更新されている場合には、頂点インデックスが“２−２”の頂点は、アクティブな頂点であるため、頂点インデックスが“１−４”の頂点のアクティブフラグを参照することなく、ステップＳＴ３５の処理に移行する。
【０１０８】
描画処理部３４は、上記のようにして、３個のアクティブな頂点（メモリ４に展開されている現在の頂点データ及び面データが、図２０（ａ）の場合には頂点インデックスが“１−１”、“１−２”、“１−４”の頂点、メモリ４に展開されている現在の頂点データ及び面データが、図２０（ａ）から図２０（ｂ）に更新されている場合には頂点インデックスが“１−１”、“１−２”、“２−２”の頂点）を見つけると、頂点データに含まれている位置情報を参照して、３個のアクティブな頂点の三次元位置（Ｘ，Ｙ，Ｚ）を特定し、その三次元位置（Ｘ，Ｙ，Ｚ）を用いて、３個のアクティブな頂点からなる３角形ポリゴンを、例えば内部のビデオＲＡＭ上に描画する（ステップＳＴ３５）。
【０１０９】
描画処理部３４は、全てのブロックにおいて、全てのアクティブな面を参照することで（ステップＳＴ３１）、アクティブな頂点からなる全ポリゴンを描画すると、その描画結果であるポリゴンモデル（前処理部１に与えられたポリゴンモデル）の画像を画像表示部５に出力する（ステップＳＴ３６）。
これにより、画像表示部５には、ポリゴンモデルの画像が表示される。
なお、ポリゴンの３次元位置と視点の位置姿勢から画像を描画する処理については、一般的なポリゴン描画に用いられる任意の処理を利用するようにしてよい。
【０１１０】
以上で明らかなように、この実施の形態１によれば、３次元物体を表現しているポリゴンモデルを分割するモデル分割部１１と、モデル分割部１１により分割されたポリゴンモデル毎に、当該ポリゴンモデルを構成している１以上のポリゴンにおける既存の頂点から新たな頂点を生成し、新たな頂点を含む１以上のポリゴンモデルの頂点間の論理的な接続関係が木構造で表現されている頂点データを生成するデータ生成部１２と、データ生成部１２により生成された頂点データを分割して、その頂点データの分割データを出力するソート部１３と、ソート部１３から出力された頂点データの分割データをＨＤＤ２に保存するデータ保存部１４と、ＨＤＤ２により保存されている複数の分割データの中から、読込命令が示す分割データを読み込んで、その分割データをＨＤＤ２より高速に読み書きが可能なメモリ４に展開する一方、メモリ４に展開済みの分割データの中から、破棄命令が示す分割データを破棄するデータ展開部３１と、モデル分割部１１により分割されたポリゴンモデル毎に、仮想空間内の視点を考慮して、当該ポリゴンモデルに対する描画の詳細度を決定する詳細度決定部３２と、メモリ４に展開されている分割データを参照して、詳細度決定部３２により決定された詳細度に対応する頂点の数を有するポリゴンモデルを構築するとともに、読込対象の分割データを示す読込命令及び破棄対象の分割データを示す破棄命令をデータ展開部３１に出力するポリゴンモデル構築部３３とを設け、描画処理部３４がポリゴンモデル構築部３３により構築されたポリゴンモデルを描画するように構成したので、大量のデータを高速に読み書き可能な記憶装置が搭載されていなくてもＬＯＤ技術を適用して、複雑な３次元仮想環境を高速かつ高品質に描画することができる効果を奏する。
【０１１１】
即ち、この実施の形態１によれば、大容量のＨＤＤ２に保存されている全ての頂点データ及び面データの分割データ（集合単位の頂点データ及び面データ）のうち、データ展開部３１がポリゴンモデル構築部３３の指示の下、必要な一部の分割データ（描画の詳細度に対応する頂点の数を有するポリゴンモデルを構築することが可能な分のデータ）のみをメモリ４に展開するようにしているので、先行技術であるＰｒｏｇｒｅｓｓｉｖｅ  Ｍｅｓｈよりも、大幅にメモリ４の消費量を低減することができる効果を奏する。
【０１１２】
なお、この実施の形態１では、前処理部１に与えられるポリゴンモデルが、頂点の三次元位置（Ｘ，Ｙ，Ｚ）を示す位置情報を含む頂点データと、ポリゴンの面を構成する頂点を示す頂点情報を含む面データとから構成されているものを示したが、頂点データ及び面データが、例えば、頂点及び面の法線や、面を塗り潰す際に用いるテクスチャなど、画像を描画する際に利用可能な情報を付加的に保有していてもよい。
【産業上の利用可能性】
【０１１３】
この発明は、３次元的な幾何学情報を使用して、複雑な３次元仮想環境を高速かつ高品質に描画することができる画像表示装置に適している。
【図１】
2011104746.tif 000003
【図２】
2011104746.tif 000004
【図３】
2011104746.tif 000005
【図４】
2011104746.tif 000006
【図５】
2011104746.tif 000007
【図６】
2011104746.tif 000008
【図７】
2011104746.tif 000009
【図８】
2011104746.tif 000010
【図９】
2011104746.tif 000011
【図１０】
2011104746.tif 000012
【図１１】
2011104746.tif 000013
【図１２】
2011104746.tif 000014
【図１３】
2011104746.tif 000015
【図１４】
2011104746.tif 000016
【図１５】
2011104746.tif 000017
【図１６】
2011104746.tif 000018
【図１７】
2011104746.tif 000019
【図１８】
2011104746.tif 000020
【図１９】
2011104746.tif 000021
【図２０】
2011104746.tif 000022
【図２１】
2011104746.tif 000023
【国際調査報告】
2011104746.tif 000024
2011104746.tif 000025