(57)【特許請求の範囲】
【請求項１】
３次元グラフィックスモデルを構成する複数のオブジェクトを表示する描画装置であって、
前記３次元グラフィックスモデルの大きさに対する各オブジェクトの大きさの比に合わせて、各オブジェクトを構成するジオメトリプリミティブの数を削減するリダクション手段と、
ジオメトリプリミティブの数を削減したオブジェクトを用いてオクルージョン判定を行う判定手段と、
前記複数のオブジェクトのうちオクルードされていないと判定されたオブジェクトを、前記オクルージョン判定に用いたジオメトリプリミティブの数より多くのジオメトリプリミティブを用いて表示する表示手段と
を備えることを特徴とする描画装置。
【請求項２】
３次元グラフィックスモデルを構成する複数のオブジェクトを表示する描画装置であって、
前記３次元グラフィックスモデルを包含する図形の大きさと各オブジェクトを包含する図形の大きさの比に基いて各オブジェクトを構成するジオメトリプリミティブの目標数を決定し、各オブジェクトのジオメトリプリミティブの数を該目標数まで削減するリダクション手段と、
ジオメトリプリミティブの数を削減したオブジェクトを用いてオクルージョン判定を行う判定手段と、
前記複数のオブジェクトのうちオクルードされていないと判定されたオブジェクトを、前記オクルージョン判定に用いたジオメトリプリミティブの数より多くのジオメトリプリミティブを用いて表示する表示手段と
を備えることを特徴とする描画装置。
【請求項３】
３次元グラフィックスモデルを構成する複数のオブジェクトを表示する描画装置であって、
前記３次元グラフィックスモデルを包含する球の半径と各オブジェクトを包含する球の半径の比に基いて各オブジェクトを構成するジオメトリプリミティブの目標数を決定し、各オブジェクトのジオメトリプリミティブの数を該目標数まで削減するリダクション手段と、
ジオメトリプリミティブの数を削減したオブジェクトを用いてオクルージョン判定を行う判定手段と、
前記複数のオブジェクトのうちオクルードされていないと判定されたオブジェクトを、前記オクルージョン判定に用いたジオメトリプリミティブの数より多くのジオメトリプリミティブを用いて表示する表示手段と
を備えることを特徴とする描画装置。
【請求項４】
３次元グラフィックスモデルを構成する複数のオブジェクトを表示するコンピュータのためのプログラムを記録した記録媒体であって、
前記３次元グラフィックスモデルの大きさに対する各オブジェクトの大きさの比に合わせて、各オブジェクトを構成するジオメトリプリミティブの数を削減し、
ジオメトリプリミティブの数を削減したオブジェクトを用いてオクルージョン判定を行い、
前記複数のオブジェクトのうちオクルードされていないと判定されたオブジェクトを、前記オクルージョン判定に用いたジオメトリプリミティブの数より多くのジオメトリプリミティブを用いて表示する
処理を前記コンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項５】
３次元グラフィックスモデルを構成する複数のオブジェクトを表示するコンピュータのためのプログラムを記録した記録媒体であって、
前記３次元グラフィックスモデルを包含する図形の大きさと各オブジェクトを包含する図形の大きさの比に基いて各オブジェクトを構成するジオメトリプリミティブの目標数を決定し、
各オブジェクトのジオメトリプリミティブの数を前記目標数まで削減し、
ジオメトリプリミティブの数を削減したオブジェクトを用いてオクルージョン判定を行い、
前記複数のオブジェクトのうちオクルードされていないと判定されたオブジェクトを、前記オクルージョン判定に用いたジオメトリプリミティブの数より多くのジオメトリプリミティブを用いて表示する
処理を前記コンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項６】
３次元グラフィックスモデルを構成する複数のオブジェクトを表示するコンピュータのためのプログラムを記録した記録媒体であって、
前記３次元グラフィックスモデルを包含する球の半径と各オブジェクトを包含する球の半径の比に基いて各オブジェクトを構成するジオメトリプリミティブの目標数を決定し、
各オブジェクトのジオメトリプリミティブの数を前記目標数まで削減し、
ジオメトリプリミティブの数を削減したオブジェクトを用いてオクルージョン判定を行い、
前記複数のオブジェクトのうちオクルードされていないと判定されたオブジェクトを、前記オクルージョン判定に用いたジオメトリプリミティブの数より多くのジオメトリプリミティブを用いて表示する
処理を前記コンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コンピュータ上に構築された３次元グラフィックスモデルを描画する描画装置に関する。
【０００２】
【従来の技術】
今日、機械系ＣＡＤ（computer-aided design ）システム、グラフィックスゲーム、アニメーション、ウォークスルー等の仮想現実感システムのような様々な分野において、３次元コンピュータグラフィックス（３ＤＣＧ）が用いられている。
【０００３】
３ＤＣＧを高速に描画する従来の方法の１つとして、オクルージョンカリング（occlusion culling ）法が知られている（USP 5,751,291 May/1998 Olsen et al., USP 5,613,050 Mar/1997 Hochmuth et al. ）。この方法では、描画対象の物体のＣＧモデル（オブジェクト）を直方体等の基本図形で覆い、その基本図形をオブジェクトの代わりに用いて、各基本図形が他の基本図形にオクルードされているか否かを判定する。
【０００４】
ここで、他の図形にオクルードされているとは、他の図形の影になって隠されている状態を意味する。オクルードされている基本図形内のオブジェクトの描画を省略することで、描画が高速化される。
【０００５】
【発明が解決しようとする課題】
しかしながら、上述した従来のオクルージョンカリング法には、次のような問題がある。
【０００６】
この方法では、オブジェクトを直方体等の基本図形で覆うため、複雑な形状のオブジェクトの場合には、一方が他方の影になるような状況を見逃したり、逆に、影にならないオブジェクトの描画を省略したりすることが多くなると考えられる。このため、比較的単純な形状のオブジェクトを扱うウォークスルーのようなシステムに向いている方法であるといえる。
【０００７】
しかし、機械系の設計現場では、しばしば、数１０万ポリゴンからなる複雑な形状のオブジェクトが現れることがあり、基本図形に基づくオクルージョンカリング法では、正確な描画が期待できない。そこで、多数のポリゴンからなる３Ｄモデルを高速に描画し、コンピュータ画面の更新レートを上げ、モデルの回転、移動等をスムースに行うことが可能なオクルージョンカリング法が望まれる。
【０００８】
本発明の課題は、機械系ＣＡＤのような複雑な形状を扱うＣＧシステムにおいて、より正確かつ高速にオクルージョンカリングを行う描画装置を提供することである。
【０００９】
【課題を解決するための手段】
図１は、本発明の描画装置の原理図である。本発明の第１の原理によれば、描画装置は、形状情報格納手段１、テーブル手段２、仮想画像格納手段３、判定手段４、およびオクルージョンカリング手段５を備え、複数のオブジェクトを表示する。
【００１０】
形状情報格納手段１は、複数のオブジェクトの形状情報を格納し、テーブル手段２は、複数のオブジェクトと仮想的に一対一に対応付けられた複数の色情報を格納する。仮想画像格納手段３は、形状情報格納手段１およびテーブル手段２の情報に基づいて描画された仮想色画像情報を格納する。判定手段４は、仮想色画像情報を走査してオクルージョン判定を行い、オクルージョンカリング手段５は、複数のオブジェクトのうち、オクルードされていると判定されたオブジェクトの表示を省略する。
【００１１】
テーブル手段２には、オブジェクトの識別情報と色情報の一対一の対応関係が格納される。オブジェクトと仮想的に対応付けられた色情報は、実際にオブジェクトを表示するための色情報ではなく、オクルージョン判定のためにオブジェクトを仮想的に描画するための色情報である。この仮想的な色情報を用いて描画された仮想色画像情報は、実際に画面に表示されることはない。
【００１２】
判定手段４は、仮想画像格納手段３に格納された仮想色画像情報をピクセル単位で走査して色情報を抽出し、テーブル手段２を参照して、抽出された色情報に対応するオブジェクトを認識する。そして、それらのオブジェクトをオクルードされていないオブジェクトと判定し、他のオブジェクトをオクルードされているオブジェクトと判定する。オクルージョンカリング手段５は、オクルードされていると判定されたオブジェクトを非表示にする。
【００１３】
本発明の第１の原理のポイントは、各オブジェクトに一意に付与された色情報を用いて画像情報を生成し、その画像情報に基づいてオクルージョン判定を行うことである。
【００１４】
このような描画装置によれば、オブジェクトを覆う基本図形を用いるのではなく、オブジェクト自身の形状を用いるため、より厳密なオクルージョン判定を行うことができる。また、各オブジェクトに一意に付与された色情報を用いて描画された画像情報を走査することにより、高速に判定を行うことができる。
【００１５】
また、本発明の第２の原理によれば、描画装置は、判定手段４、リダクション手段６、および表示手段７を備え、３次元グラフィックスモデルを構成する複数のオブジェクトを表示する。
【００１６】
リダクション手段６は、３次元グラフィックスモデルの大きさに対する各オブジェクトの大きさの比に合わせて、各オブジェクトを構成するジオメトリプリミティブ（geometry primitive）の数を削減し、判定手段４は、ジオメトリプリミティブの数を削減したオブジェクトを用いてオクルージョン判定を行う。表示手段７は、複数のオブジェクトのうち、オクルードされていないと判定されたオブジェクトを、オクルージョン判定に用いたジオメトリプリミティブの数より多くのジオメトリプリミティブを用いて表示する。
【００１７】
ジオメトリプリミティブは、オブジェクトの表面の一部を表す幾何データであり、例えば、三角形ポリゴンがこれに対応する。リダクション手段６は、各オブジェクトについて、ジオメトリプリミティブの数を削減したモデルを生成する。判定手段４は、リダクション手段６が生成したモデルを用いてオクルージョン判定を行い、表示手段７は、オクルードされていないと判定されたオブジェクトを、例えば、削減される前のジオメトリプリミティブを用いて表示する。
【００１８】
本発明の第２の原理のポイントは、各オブジェクトのジオメトリプリミティブの数を削減してオクルージョン判定を行うことである。
このような描画装置によれば、ジオメトリプリミティブの数が削減されてオブジェクトの形状が簡単化されるため、オクルージョン判定を高速に行うことができる。また、ジオメトリプリミティブの数を削減したモデルの形状は、元のオブジェクトの形状を反映しているため、厳密に判定を行うことができる。
【００１９】
例えば、図１の形状情報格納手段１、テーブル手段２、および仮想画像格納手段３は、後述する図３のＲＡＭ（ランダムアクセスメモリ）２７に対応し、図１の判定手段４、オクルージョンカリング手段５、およびリダクション手段６は、図３のＣＰＵ（中央処理装置）２３に対応し、図１の表示手段７は、図３のグラフィックス処理装置２５およびグラフィックディスプレイ２６に対応する。
【００２０】
【発明の実施の形態】
以下、図面を参照しながら、本発明の実施の形態を詳細に説明する。
本実施形態においては、あるオブジェクトが他のオブジェクトにオクルードされているか否かを判定するために、各オブジェクトにそれぞれ異なる仮想的な色情報（virtual color ）を付与し、その色を用いてオブジェクトをビットマップ上に描画する。そして、ビットマップ上の色を走査することで、あるオブジェクトが他のオブジェクトにオクルードされているか否かを判定する。
【００２１】
このようなオクルージョンカリング判定によれば、オブジェクトを覆う基本図形を用いるのではなく、オブジェクト自身の形状を用いるため、より厳密な判定を行うことができる。また、各オブジェクトに一意に付与された色をビットマップ上で走査することにより、高速に判定を行うことができる。
【００２２】
仮想的な色情報の描画を数フレームに１回のみ行うことで、オクルージョンカリングがさらに効率化される。また、仮想的な色情報の描画用のモデルとして、ポリゴンリダクションを行ったモデルを使用することで、オクルージョンカリングがさらに高速化される。
【００２３】
図２は、機械系ＣＡＤ等で作成したアセンブリモデルを高速に描画するための描画装置の構成図である。図２の描画装置は、形状・アセンブリ情報記憶部１１、位置・姿勢情報更新部１２、オクルージョンカリング判定部１３、描画部１４、およびポリゴンリダクション計算部１５を備える。
【００２４】
形状・アセンブリ情報記憶部１１は、オブジェクトを表現するための頂点集合、オブジェクト間のアセンブリ関係を表現する親子関係、位置、姿勢、関節関係等の図形情報を記憶する。位置・姿勢情報更新部１２は、オブジェクトが動いたときに、オブジェクトの位置・姿勢を表す各頂点の位置の時間に対する変動量を計算する。
【００２５】
オクルージョンカリング判定部１３は、各オブジェクトを仮想的な色情報で描画し、その結果をビットマップに取り出して、ビットマップ上に現れている色を検出する。これにより、他のオブジェクトの影にならずに表に現れているオブジェクト（オクルードされていないオブジェクト）を抽出し、それらのオブジェクトに印を付ける。
【００２６】
描画部１４は、オクルージョンカリング判定部１３が印を付けたオブジェクトのみを、数サイクルにわたって描画する。ポリゴンリダクション計算部１５は、オブジェクトのポリゴン数を段階的に削減し、ポリゴン数を削減したオブジェクトを位置・姿勢情報更新部１２に入力する。これらのオブジェクトは、オクルージョンカリングの判定を高速化するために用いられる。
【００２７】
図３は、図２の描画装置を情報処理装置（コンピュータ）を用いて構成した例を示している。図３の情報処理装置は、データ入力装置２１、インタフェース（Ｉ／Ｆ）２２、２４、ＣＰＵ（中央処理装置）２３、グラフィックス処理装置２５、グラフィックディスプレイ２６、ＲＡＭ（ランダムアクセスメモリ）２７、および記憶装置２８を備える。
【００２８】
ＣＰＵ２３は、オブジェクトの移動に伴う位置・姿勢の更新（座標変換）、オクルージョンカリング、ポリゴンリダクション、計算結果を表示するための演算、オブジェクトの動きをグラフィカルに表示するための演算、その他のあらゆる論理演算等を行う。空間内でオブジェクトの位置・姿勢を更新する処理は、オブジェクトの座標系を他の座標系に変換する処理とみなすことができるため、このような処理は、しばしば、オブジェクトの座標変換と呼ばれる。
【００２９】
記憶装置２８には、作業環境、オブジェクトの形状データ、アセンブリデータ、それらの初期位置、描画アルゴリズムの実行モジュール（プログラム）、オブジェクトの動きをグラフィカルに表示するための実行モジュール等の必要なデータおよび実行モジュールが格納される。記憶装置２８としては、例えば、磁気ディスク装置、光ディスク装置、光磁気ディスク（magneto-optical disk）装置等が用いられる。
【００３０】
ＲＡＭ２７は、形状データ・アセンブリデータメモリ３１、座標変換データメモリ３２、仮想色情報メモリ３３、オクルージョンカリングメモリ３４、ポリゴンリダクションメモリ３５、および配列テーブルメモリ３６を含む。
【００３１】
形状データ・アセンブリデータメモリ３１には、ＣＰＵ２３により記憶装置２８から呼び出された作業環境およびオブジェクトのデータが保持され、座標変換データメモリ３２には、データ入力装置２１を介して入力されたオブジェクトの移動指令データを用いてＣＰＵ２３が算出したオブジェクトの形状データが保持される。
【００３２】
仮想色情報メモリ３３には、オクルージョンカリングを行うために各オブジェクトにそれぞれ異なる仮想色を割り付けたときの描画結果が、ビットマップとして保持される。オクルージョンカリングメモリ３４には、仮想色情報メモリ３３のビットマップ上に描画されている色を持ったオブジェクトが、他のいかなるオブジェクトにもオクルードされていない「表」の状態であることを示すフラグが保持される。
【００３３】
ポリゴンリダクションメモリ３５には、各オブジェクトのポリゴン数を削減したモデルが常駐している。ＣＧシステムにおけるオブジェクトは、通常、三角形ポリゴンのようなジオメトリプリミティブの集合により形成される。
【００３４】
ポリゴンリダクションメモリ３５内のモデルは、オブジェクトを形成する各ジオメトリプリミティブの真の色（true color）、頂点座標、法線ベクトル等の図形情報を含んでいる。ポリゴンリダクションにおいて最も高いレベルのデータは、元々のオブジェクトのジオメトリプリミティブデータであり、低いレベルのデータは、この元々のジオメトリプリミティブデータから段階的に生成される。
【００３５】
配列テーブルメモリ３６には、オブジェクトの識別情報と仮想色との一対一の対応関係が保持される。この配列テーブルメモリ３６を参照することで、各オブジェクトに対応する仮想色を取得したり、各仮想色に対応するオブジェクトの識別情報を取得したりすることができる。
【００３６】
データ入力装置２１は、Ｉ／Ｆ２２を介して、作業環境、アセンブリモデルに含まれるオブジェクトの位置・姿勢、移動指令データ等をＣＰＵ２３に送る。ＣＰＵ２３は、ＲＡＭ２７および記憶装置２８にアクセスしながら、各オブジェクトの位置・姿勢の更新、ポリゴンリダクション、オクルージョンカリング等の処理を行う。
【００３７】
グラフィックス処理装置２５は、例えば、グラフィックスボードであり、画像情報を一時的に蓄積する複数のフレームバッファと、それらのフレームバッファをスワップして画像情報をグラフィックディスプレイ２６に送るスワッピング機構とを含む。
【００３８】
オクルージョンカリングが行われると、フレームバッファ上では、Ｉ／Ｆ２４を介して送られてきたオクルージョンカリングメモリ３４およびポリゴンリダクションメモリ３５の情報に基づき、表の状態にあるオブジェクトのみの画像情報が展開される。そして、その画像情報は、スワッピング機構によりグラフィックディスプレイ２６に送られて、画面に表示される。
【００３９】
図２の形状・アセンブリ情報記憶部１１は図３の記憶装置２８に対応し、図２の描画部１４は、図３のグラフィックス処理装置２５およびグラフィックディスプレイ２６に対応する。また、図２の位置・姿勢情報更新部１２、オクルージョンカリング判定部１３、およびポリゴンリダクション計算部１５は、図３の記憶装置２８に格納された実行モジュールに対応する。
【００４０】
図４は、図３の情報処理装置にプログラムとデータを供給することのできるコンピュータ読み取り可能な記録媒体を示している。処理に必要なプログラムとデータが可搬記録媒体４１に格納されている場合、それらの情報はＲＡＭ２７にロードされた後、ＣＰＵ２３により使用される。可搬記録媒体４１としては、メモリカード、フロッピーディスク、ＣＤ−ＲＯＭ（compact disk read only memory ）、光ディスク、光磁気ディスク等、任意のコンピュータ読み取り可能な記録媒体が用いられる。
【００４１】
また、処理に必要なプログラムとデータがネットワークで接続された外部のデータベース４２に格納されている場合、それらの情報は回線を介してＲＡＭ２７にロードされた後、ＣＰＵ２３により使用される。
【００４２】
図５は、図３の描画装置による描画処理のフローチャートである。まず、ＣＰＵ２３は、記憶装置２８から形状データ・アセンブリデータメモリ３１に、表示するアセンブリモデルに含まれるオブジェクトの形状データ、アセンブリデータ、および初期位置を読み込む（ステップＳ１）。次に、読み込まれた各オブジェクトに対して任意のポリゴンリダクションアルゴリズムを適用して、一般にポリゴン数をＭ段階に削減したモデルを作成し、ポリゴンリダクションメモリ３５に格納する（ステップＳ２）。
【００４３】
ポリゴンリダクションアルゴリズムとしては、例えば、２次誤差メトリック（quadric error metric）を用いたアルゴリズムが用いられる（Michael Garland and Paul S. Heckbert, “Surface Simplification Using Quadric Error Metrics, ”Proceedings of SIGGRAPH 1997, pp.209-216, 1997. ）。
【００４４】
図６は、初期ポリゴン数が数千程度のオブジェクト（ソファ）の形状モデルを４段階に削減した例を示している。ここでは、描画レベル（level of detail ，ＬＯＤ）がレベル０のモデルが元々のオブジェクトに対応し、レベル１、レベル２、レベル３とレベルが低くなるに従って、ポリゴン数が減少している。
【００４５】
次に、ＣＰＵ２３は、データ入力装置２１から入力された移動指令データに従って、読み込まれたオブジェクトの位置と姿勢を微少量だけ変化させ、変更された形状データを座標変換データメモリ３２に格納する（ステップＳ３）。ユーザがオブジェクトの動きを指定する場合、マウス等の入力装置でオブジェクトをインタラクティブに動かすことにより、移動指令データが入力される。また、システムが自動的にオブジェクトの動きを生成する場合は、所定のアルゴリズムにより移動指令データが生成される。
【００４６】
次に、グラフィックス処理装置２５内のフレームバッファ上で、各オブジェクトをそれぞれ異なる仮想的な色で描画し、表示画面に対応するビットマップを生成する（ステップＳ４）。次に、生成されたビットマップを仮想色情報メモリ３３に読み込み、そのビットマップを走査して、描画されている色を抽出する。そして、配列テーブルメモリ３６を参照して、抽出された色に対応するオブジェクトを認識し、オクルージョンカリングメモリ３４内のそれらのオブジェクトのフラグを立てる。
【００４７】
図７は、このようなオクルージョンカリング判定の例を示している。図７においては、ＬＯＤがレベル１の４つのオブジェクトＡ、Ｂ、Ｃ、Ｄに、それぞれ異なる仮想色ＶＣ１、ＶＣ２、ＶＣ３、ＶＣ４が割り振られている。これらのオブジェクトを視点Ｐから矢印の方向に向かって眺めたときの状態を、フレームバッファ上に描画したとする。
【００４８】
このとき、視点Ｐから見えるオブジェクトは、オブジェクトＡとオブジェクトＢの一部（ソファの左半分）のみである。オブジェクトＣとオブジェクトＤはともに他のオブジェクトの影に隠れており、フレームバッファ上に現れることはない。したがって、生成されたビットマップからは、２つの仮想色ＶＣ１、ＶＣ２と背景色が抽出される。
【００４９】
ここで、背景色を常に白とし、この色を他のオブジェクトの仮想色に割り振らないことにすれば、オブジェクトと仮想色は常に一対一対応の関係にある。したがって、この瞬間にはオブジェクトＡとオブジェクトＢの２つのみが見えており、オブジェクトＣとオブジェクトＤの２つは他のオブジェクトにオクルードされていると結論できる。そこで、ＣＰＵ２３は、オブジェクトＡとオブジェクトＢのフラグを立て、オブジェクトＣとオブジェクトＤのフラグを伏せる。
【００５０】
次に、ＣＰＵ２３は、オクルージョンカリングメモリ３４内でフラグの立っているオブジェクトを抽出し、グラフィックス処理装置２５は、それらを元々の色でフレームバッファに描画して、グラフィックディスプレイ２６に表示する（ステップＳ５）。そして、描画装置は、ステップＳ３〜Ｓ５からなるループ処理を繰り返すことで、アセンブリモデルが動的に変化する様子を表示する。
【００５１】
オクルージョンカリング判定に用いられたフレームバッファ上の仮想色は、判定が終了した時点で消去され、ディスプレイ上に表示されることはない。実際にディスプレイ上に表示されるのは、表の状態にあると判定されたオブジェクトのみである。
【００５２】
例えば、図７のようなオクルージョンカリング判定の次の瞬間の描画状態は、図８に示すようになる。図８においては、表の状態にあるオブジェクトＡとオブジェクトＢのみが、初期ポリゴン数に対応するレベル０で描画されている。
【００５３】
次に、各オブジェクトが微少量だけ移動すると、描画状態は図９に示すように変化する。図９においては、オブジェクトＣとオブジェクトＤは、依然としてオクルードされているため、描画する必要はない。したがって、描画されるのは、図７において表の状態と判定されたオブジェクトＡとオブジェクトＢのみである。
【００５４】
このように、オクルージョンカリング判定の結果は、オブジェクトの移動量が微少である限り、数サイクルの間は正しいと推定できる。そこで、図５のステップＳ４のオクルージョンカリング判定は、Ｎを与えられた正の整数として、Ｎループに１回の割合で行われる。この場合、仮想色による描画はＮループに１回のみ行えばよいため、これを毎回行う場合に比べて、処理が効率化される。
【００５５】
また、図７の仮想色による描画においては、オブジェクトのＬＯＤ（レベル１）を図８、９に示した実際のＬＯＤ（レベル０）より低く設定している点が本実施形態の特徴である。その理由は、仮想色による描画は単にオクルージョンカリングの判定を行うことのみを目的とするため、レベル０の精細ポリゴンを使って描画する必要がないからである。
【００５６】
そこで、描画装置は、ポリゴンリダクションとオクルージョンカリングとを上述したように融合させて処理を行っている。これにより、オクルージョンカリング判定の速度が増すとともに、全体としてオブジェクトの描画速度が向上する。
【００５７】
図７、８、９においては、各ソファが１つのオブジェクトとして扱われているが、１つのソファが複数の部品から構成されている場合は、各部品を１つのオブジェクトとして扱って、同様のオクルージョンカリングが行われる。
【００５８】
図１０および図１１は、図３の描画装置による描画処理のより詳細なフローチャートである。ここでは、グラフィックス処理装置２５は、フレームバッファとしてダブルバッファを用いて描画を行うものとする。
【００５９】
まず、ＣＰＵ２３は、ループ回数を表す制御変数Ｉに１を代入して（図１０のステップＳ１１）、各オブジェクトを構成するジオメトリプリミティブのデータを形状データ・アセンブリデータメモリ３１に入力する（ステップＳ１２）。
【００６０】
次に、それらのジオメトリプリミティブの各頂点に座標変換を施し、絶対座標系から見た座標値を計算して、座標変換データメモリ３２に格納する（ステップＳ１３）。そして、ステップＳ１４〜Ｓ２０において通常の描画処理（true-color display）のループ処理を行い、この処理をＮ回繰り返す度に１回の割合で、図１１の仮想色描画処理（virtual-color display ）を行う。
【００６１】
ここでは、まず、ＩをＮで割ったときの剰余を求め、それが０であるか否かをチェックする（ステップＳ１４）。剰余が０であれば、正射影または透視法射影の射影変換を行い（図１１のステップＳ２１）、各オブジェクトの仮想色情報をフレームバッファに蓄積する（ステップＳ２２）。これにより、各ジオメトリプリミティブの仮想色がピクセル情報とともにフレームバッファに蓄積される。
【００６２】
このとき、グラフィックス処理装置２５は、画面をｘｙ平面で表し、奥行方向をｚ軸で表して、ｚ方向に重複している点（ｘｙ座標値が同じ点）の前後関係を判定する。この判定は、既存のグラフィックスライブラリによる描画処理ではよく知られており、通常、ハードウェアにより高速に行われる。そして、最も手前にある点の色が、対応するピクセルの色として格納される。
【００６３】
この仮想色による描画は、通常、ＬＯＤを低いレベルに設定したモデルで行われ、特殊なシェーディング（shading ）処理は一切施されない。したがって、所謂、ベタ塗りの状態で描画される。
【００６４】
また、描画処理の前処理において、ｒｇｂ値（それぞれ、０〜２５５の整数）の３つの整数の組合せを、仮想色の識別情報として辞書順に各オブジェクトに割り付けておく。これにより、最大で１６，７７７，２１６（＝２５６×２５６×２５６）色の異なった仮想色をオブジェクトに割り付けることができる。これらの仮想色の識別情報とオブジェクトの対応関係は、配列テーブルメモリ３６に格納される。
【００６５】
次に、ＣＰＵ２３は、フレームバッファの各ピクセルの仮想色情報を仮想色情報メモリ３３に読み出し（ステップＳ２３）、仮想色情報メモリ３３上のピクセルを走査して、ピクセル上に現れている仮想色の識別情報を取り出す。そして、その識別情報をもとに配列テーブルメモリ３６を参照し、オクルージョンカリングメモリ３４において、それらの仮想色を有するオブジェクトのフラグを１に設定する（ステップＳ２４）。また、他のオブジェクトのフラグを０に設定する
（ステップＳ２５）。
【００６６】
次に、仮想色情報が書き込まれたフレームバッファを、一旦、完全にクリアし、２つのバッファのスワッピングをスキップする（ステップＳ２６）。したがって、仮想色による画像は表示されず、画面上には、前のループで描画された画像がそのまま残ることになる。
【００６７】
次に、ライティング（lighting）／シェーディングの設定を行い（図１０のステップＳ１５）、正射影または透視法射影の射影変換を行う（ステップＳ１６）。そして、各オブジェクトのフラグを比較し、その値が１であるオブジェクトのみについて、ジオメトリプリミティブの真の色とピクセル情報をフレームバッファに蓄積する（ステップＳ１７）。
【００６８】
次に、グラフィックス処理装置２５は、２つのバッファをスワップし（ステップＳ１８）、蓄積された情報を画面上に表示する（ステップＳ１９）。この真の色による描画では、ステップＳ２２の仮想色による描画の場合より高いレベルのＬＯＤを有するモデルが用いられる。
【００６９】
そして、Ｉ＝Ｉ＋１とおいて、ステップＳ１２以降の処理を繰り返す。これにより、Ｎフレームの表示が行われる毎に１回のオクルージョンカリング判定が行われ、その判定結果に基づいて次のＮフレームが表示される。
【００７０】
次に、ステップＳ１７、Ｓ２４で描画に用いられるモデルのポリゴン数を決定するポリゴンリダクションの基準について説明する。ポリゴンリダクションの基本アルゴリズムとして、例えば、上述した２次誤差メトリックを用いたアルゴリズムを用いることができる。
【００７１】
このとき、できるだけアセンブリモデル全体の形状を保ちながら、それを構成する各オブジェクトのポリゴン数を削減し、結果としてアセンブリモデルの総ポリゴン数を有効に削減することが望ましい。例えば、図１２のアセンブリモデルＢ０は、オブジェクトＢ１、Ｂ２、Ｂ３、Ｂ４、Ｂ５、Ｂ６から構成されており、アセンブリモデルＢ０のポリゴン数を効率良く削減することが求められる。
【００７２】
そこで、図１２において、各オブジェクトＢｉ（ｉ＝１，．．．，６）の初期ポリゴン数をＰｉとし、オブジェクトＢｉを包含する球の半径をＲｉとし、アセンブリモデルＢ０を包含する球の半径をＲ０として、目標とする削減ポリゴン数Ｑｉを次式により決定する。
Ｑｉ＝α×Ｐｉ×（Ｒｉ／Ｒ０）                                （１）
ここで、αは、０≦α≦１なる実数パラメータであり、ＬＯＤが低くなるに従って、小さく設定される。（１）式によれば、目標ポリゴン数Ｑｉは、オブジェクトＢｉの包含球の半径とアセンブリモデルＢ０の包含球の半径の比に基づいて決定される。言い換えれば、目標ポリゴン数Ｑｉは、オブジェクトＢｉの大きさとアセンブリモデルＢ０の大きさの比に基づいて決定されることになる。
【００７３】
したがって、（１）式を用いて目標ポリゴン数を算出することにより、アセンブリモデルの中で相対的に小さくて目立たないオブジェクトのポリゴン数を、他のオブジェクトに比べて大きく削減することができる。このようなオブジェクトのポリゴン数の変化は全体の形状に大きな影響を与えないので、アセンブリモデルの形状が大きく損なわれることはなく、有効にポリゴン数が削減される。
【００７４】
例えば、ネジやボルト等のオブジェクトは、その大きさの割には多数のポリゴンで構成されることが多い。アセンブリモデルがこのような部品のオブジェクトを含む場合、（１）式によりポリゴンリダクションを行うことで、これらの部品のポリゴン数が有効に削減され、処理が高速化される。
【００７５】
こうして、ＬＯＤ毎にポリゴン数が削減された各オブジェクトの情報は、ポリゴンリダクションメモリ３５に格納され、フレームバッファに描画する際に用いられる。
【００７６】
ここで、ポリゴンリダクションを行う前の元々のアセンブリモデルのＬＯＤをレベル０とし、（１）式でα＝１．０とおいてポリゴン数を削減したアセンブリモデルのＬＯＤをレベル１とする。このとき、図１０のステップＳ１７における真の色の描画をレベル０で行い、図１１のステップＳ２４における仮想色の描画をレベル１で行うことにより、オクルージョンカリングが高速に実行され、効率の良い３Ｄ描画が可能となる。
【００７７】
より一般的には、（１）式のαの値を複数用意しておき、ＬＯＤを多段階に設定することができる。例えば、レベル０、レベルＩ、レベルＪ（０＜Ｉ＜Ｊ）の３段階のＬＯＤが設定された場合、アセンブリモデルをインタラクティブに動かしているときは、真の色の描画をレベルＩで行い、仮想色の描画をレベルＪで行う。また、アセンブリモデルが静止しているときは、真の色の描画をレベル０で行う。
【００７８】
ところで、（１）式では、包含球の半径の比に基づいて目標ポリゴン数を決定しているが、代わりに、包含球の表面積や体積の比に基づいて目標ポリゴン数を決定してもよい。また、包含球の代わりに、オブジェクトやアセンブリモデルを包含する立方体や直方体等の他の図形を用い、それらの大きさの比に基づいて目標ポリゴン数を決定してもよい。
【００７９】
さらに、オブジェクトやアセンブリモデルの大きさを表す指標が存在する場合、それらの指標に基づいて目標ポリゴン数を決定することもできる。また、オブジェクトが他のジオメトリプリミティブから構成される場合も、同様にして、目標とするジオメトリプリミティブの数を決定することができる。
【００８０】
以上説明した実施形態においては、主として、機械系ＣＡＤのアセンブリモデルの描画処理について説明したが、グラフィックスゲーム、アニメーション、ウォークスルー等の他の３ＤＣＧの分野においても、同様のオクルージョンカリングを行うことができる。
【００８１】
また、オクルージョンカリング判定において、仮想色による描画を行う代わりに、各オブジェクトに一意の識別情報を付与し、その識別情報を用いてオブジェクトを描画したビットマップを生成してもよい。この場合も、仮想色の場合と同様にして、ビットマップ上の識別情報を走査することで、あるオブジェクトが他のオブジェクトにオクルードされているか否かを判定することができる。
【００８２】
【発明の効果】
本発明によれば、３ＤＣＧシステムにおいて、オブジェクト自身の形状を用いてビットマップ上でオクルージョンカリング判定を行うため、正確かつ高速にオクルージョンカリングを行うことができる。これにより、３ＤＣＧの品質が向上することが期待される。
【図面の簡単な説明】
【図１】本発明の描画装置の原理図である。
【図２】描画装置の構成図である。
【図３】情報処理装置の構成図である。
【図４】記録媒体を示す図である。
【図５】第１の描画処理のフローチャートである。
【図６】ポリゴンリダクションを示す図である。
【図７】オクルージョンカリングを示す図である。
【図８】オクルージョンカリング後の描画を示す図である。
【図９】オブジェクトの移動を示す図である。
【図１０】第２の描画処理のフローチャート（その１）である。
【図１１】第２の描画処理のフローチャート（その２）である。
【図１２】オブジェクトを包含する球を示す図である。
【符号の説明】
１  形状情報格納手段
２  テーブル手段
３  仮想画像格納手段
４  判定手段
５  オクルージョンカリング手段
６  リダクション手段
７  表示手段
１１  形状・アセンブリ情報記憶部
１２  位置・姿勢情報更新部
１３  オクルージョンカリング判定部
１４  描画部
１５  ポリゴンリダクション計算部
２１  データ入力装置
２２、２４  インタフェース
２３  ＣＰＵ
２５  グラフィックス処理装置
２６  グラフィックディスプレイ
２７  ＲＡＭ
２８  記憶装置
３１  形状データ・アセンブリデータメモリ
３２  座標変換データメモリ
３３  仮想色情報メモリ
３４  オクルージョンカリングメモリ
３５  ポリゴンリダクションメモリ
３６  配列テーブルメモリ
４１  可搬記録媒体
４２  データベース
【図１】
0003711273.tif 000002
【図２】
0003711273.tif 000003
【図３】
0003711273.tif 000004
【図４】
0003711273.tif 000005
【図５】
0003711273.tif 000006
【図６】
0003711273.tif 000007
【図７】
0003711273.tif 000008
【図８】
0003711273.tif 000009
【図９】
0003711273.tif 000010
【図１０】
0003711273.tif 000011
【図１１】
0003711273.tif 000012
【図１２】
0003711273.tif 000013