(57)【特許請求の範囲】
【請求項１】
対象物体に係る輪郭座標情報を収容するメモリと、
前記対象物体の立体モデルのポリゴン数が低減するようにポリゴンの統合を行うポリゴン統合部と、
統合により変形するポリゴンの代表点座標を算出する代表点算出部と、
前記輪郭座標情報と、算出した前記代表点座標に基づいて、前記ポリゴン統合部によるポリゴンの統合が可能か否かを判定する統合判定部を含み、
前記統合判定部は、統合後のポリゴンの全代表点が対象物体の輪郭座標上に存在する場合に統合可能と判定し、いずれかの前記代表点が対象物体の輪郭座標上に存在しない場合に統合不可と判定する、画像生成装置。
【請求項２】
前記ポリゴン統合部は、隣接する２つの頂点を統合させることによりポリゴンの統合を行う、請求項１記載の画像生成装置。
【請求項３】
前記代表点は、統合頂点座標及び統合後ポリゴンの重心座標である、請求項２記載の画像生成装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、コンピュータグラフィックスなどにおいて用いられる、対象物体の立体モデルを表すポリゴンを削除して画像を生成する装置並びに三次元画像生成方法に関する。特に、三次元スキャナなどにより対象となる物体の輪郭点の三次元座標値を抽出し、該輪郭点を全て接続することにより求めたポリゴンメッシュからなる原型立体モデルを算出し、該初期立体モデルのポリゴン数を削減して得られた簡略化立体モデルをディスプレイに表示する装置並びに方法に関する。
【０００２】
【従来の技術】
従来のＣＡＤシステムなどにおいて設計されるモデルは、モデルを元に製品が作られる性質上細部に亘ってモデリングされる必要がある。一方、ＣＧなどで要求されるモデルは、高速描写可能なモデルであることが望ましく、細部に亘るモデリングは一般に最終的なＣＧ画像に描画されない冗長なポリゴンを含んでいるため、ＣＧでの描画に適しているとはいえない。そのため、ＣＡＤシステムでは描画されない冗長なポリゴンを除去して、１フレームあたりの描画時間を短縮することが有効である。そこで、ＣＧモデルの高速描画を行うために冗長なポリゴンを除去し、複数のポリゴンを統合する装置が提案されていた。
【０００３】
例えば、"COMPUER GRAPHICS Proceedings, Annual Conference Series, 1993"でHuges Hppe et.al.が発表した"Mesh Optimization"に示された従来のポリゴンメッシュ最適化手法について説明する。
【０００４】
図１３は、ワイングラスの立体モデル６を下から見た斜視図である。図において立体モデル６は、ワイングラスを三次元レーザスキャナにより抽出したモデル表面のドットパターンを相互に結びつけることにより、ポリゴン７、８などからなる線図の三次元画像をディスプレイ９上に表示したものである。この多数のポリゴンを該ポリゴンメッシュ最適化手法で統合した三次元画像の斜視図を図１４に示す。
【０００５】
図１５は、該ポリゴンメッシュ最適化手法の工程図である。図において、対象物体を表す立体モデル１は、図１３の立体モデル６のポリゴンメッシュの一部である。該手法では、立体モデル１に対して、（ｉ，ｊ）の辺を消去する辺消去２、（ｉ，ｊ）の辺を再分割する辺分割３、（ｉ，ｊ）の辺の位置を入れ替える辺交換４、のいずれかの処理を適用することによりポリゴンを変形する。ここで、辺消去２の統合頂点ｈは、立体モデル１の（ｉ，ｊ）辺５の中点である。この中点は頂点ｉと頂点ｊを統合する統合頂点として利用され、合計１０個のポリゴンから２個のポリゴンを削除していた。
【０００６】
上記ポリゴンメッシュ最適化工程においては、立体モデル１表面の全てのドットについて、ドットからポリゴン面への最小距離を求め、それらを総和した量、及び、ポリゴンの頂点の総数、及び、ポリゴンメッシュの滑らかさを表す量によって、ポリゴンメッシュの最適化の程度を表すエネルギーの値を定義し、辺消去２により頂点ｉ，ｊを頂点ｈに統合することにより、該エネルギーの値が減少するか否かを調べ、減少する場合には、統合頂点ｈを有効なものとしていた。
【０００７】
また、該辺消去２により、該エネルギーの値が減少しない場合には、辺分割３によって、該エネルギーの値が減少するか否かを調べ、減少する場合には、該辺分割３を有効なものとしていた。
【０００８】
さらに、該辺分割３により、該エネルギーの値が減少しない場合には、辺交換４によって、該エネルギーの値が減少するか否かを調べ、減少する場合には、該辺分割３を有効なものとしていた。
【０００９】
更に、該辺分割３により、該エネルギーの値が減少しない場合には、変形を棄却していた。
【００１０】
該ポリゴンメッシュ最適化工程においては、図１３の立体モデル６の全体に渡って、前記ポリゴンメッシュ変形処理を実行し、該エネルギーが減少しなくなった時点で、変形処理を終了する。
【００１１】
例えば、対象物体の三次元原画像の１６８６４ドットを４０５９頂点で結びつける８０７３平面の三角形ポリゴンメッシュを初期値として、エネルギー最小化に基づき隣接ポリゴンを統合し、２６２頂点と５１５平面の三角形ポリゴンメッシュで簡略化した場合、DEC uniprocessor Alpha  workstation を用いた実験では、４４．５分の処理時間を要していた。また、ポリゴンメッシュの最適化の程度を表すエネルギーのパラメータの設定によりポリゴンメッシュの削減率を決定していた。
【００１２】
【発明が解決しようとする課題】
上記のような従来の三次元画像の生成手法では、立体モデルの表面の全てのドットに対するドットの座標とポリゴン面との距離の総和、及び、ポリゴンの頂点の総数、及び、ポリゴンメッシュの滑らかさを表す量によって、定義されるエネルギーの値を算出しながら、辺消去、辺分割、辺交換の３つのポリゴンメッシュ変形処理のうち最適なものを決定し、不要なポリゴンを削減するものとなっているため、変形処理の試行回数が増加し、その結果、ドットの座標とポリゴン面との距離の総和、及び、ポリゴン頂点の総数、及び、ポリゴンメッシュの滑らかさを表す量によって定義されるエネルギー値の演算回数が増大して、バッチ処理並びにリアルタイムの三次元画像の生成に膨大な時間を費やすという欠点があった。一方、隣接するポリゴンの両法線ベクトルすなわちポリゴン面に垂直な両ベクトルの角度差を算出して、この両法線ベクトルの角度差が所定の閾値以下である場合には、両ポリゴンを統合する従来の手法では、統合するポリゴン面座標と三次元スキャナや立体の６面図などにより抽出したモデル表面の座標とを直接対比していないために、三次元モデルの各部に必要な表現精度を維持することができないという問題があった。
【００１３】
この発明は、上述のような課題を解決するためになされたもので、第１の目的は、三次元画像の作成を容易に行うことが可能な画像生成装置を提供することにある。また、この発明の第２の目的は、ポリゴン数を削除可能な画像生成装置および画像作成方法並びに画像作成プログラム記憶媒体を提供することにある。さらに、この発明の第３の目的は、ポリゴン数の削除をより高速に処理する画像生成装置を提供することにある。さらにまた、この発明の第４の目的は、立体モデルの曲率に応じた表現精度でポリゴン数を削除する画像生成装置を提供することにある。
【００１４】
【課題を解決するための手段】
この発明に係る画像生成装置においては、対象物体に係る輪郭座標情報を収容するメモリと、前記対象物体をポリゴンで構成する立体モデルのポリゴンをその数が低減するように統合するポリゴン統合装置と、前記対象物体をポリゴンで構成する立体モデルのポリゴンをその数が低減するように統合した場合に作成されるポリゴン面が前記輪郭座標近傍内に位置するか否かを判定する統合判定装置を含むものである。
【００１５】
また、対象物体に係る輪郭座標情報と、該対象物体をポリゴンにより構成する立体モデルの該ポリゴンの頂点座標情報とを記憶するメモリ装置と、前記対象物体をポリゴンで構成する立体モデルのポリゴンをその数が低減するように統合するポリゴン統合装置と、対象物体をポリゴンで構成する立体モデルのポリゴンをその数が低減するように統合した場合に作成されるポリゴンの代表点座標情報と前記輪郭座標情報とから該ポリゴンの統合が統合基準を満たすか否かを判定する統合判定装置を含むものである。
【００１６】
さらに、対象物体の原型立体モデルを所定の倍率に拡大または縮小することにより得られる輪郭座標情報及び前記対象物体をポリゴンで構成する立体モデルの頂点座標情報を記憶するメモリ装置と、前記対象物体をポリゴンで構成する立体モデルのポリゴンをその数が低減するように統合するポリゴン統合装置と、前記対象物体をポリゴンで構成する立体モデルのポリゴンをその数が低減するように統合した場合に作成されるポリゴンの代表点座標情報を前記立体モデルが前記倍率後の原型立体モデルと同スケールになるように変換してなる情報と前記輪郭座標情報とから該ポリゴンの統合が統合基準を満たすか否かを判定する統合判定装置と、を含むものである。
【００１７】
前記倍率を対象物体の原型立体モデルの各部の曲率に応じ変更することを特徴とする。
【００１８】
前記ポリゴン統合装置は、ポリゴンの２頂点または３頂点を統合する、若しくは、ポリゴンの再配置によって統合することを特徴とする。
【００１９】
前記対象物体に係る輪郭座標情報は、原型立体モデルの輪郭座標情報、または前記対象物体をポリゴンにより構成する立体モデルの輪郭座標情報であることを特徴とする。
【００２０】
前記輪郭座標情報はボクセル空間内の対応するボクセルに記憶し、前記統合基準は前記代表点座標情報に対応するボクセルの情報により判定することを特徴とする。
【００２１】
前記代表点座標情報は、前記統合した場合に作成されるポリゴン面内の点であることを特徴とする。
【００２２】
前記代表点座標情報は、前記統合した場合に作成されるポリゴンの頂点または重心点であることを特徴とする。
【００２３】
この発明に係る画像生成方法は、対象物体に係る輪郭座標情報を収容するメモリと、前記対象物体をポリゴンで構成する立体モデルのポリゴンをその数が低減するように統合するポリゴン統合装置と、前記対象物体をポリゴンで構成する立体モデルのポリゴンをその数が低減するように統合した場合に作成されるポリゴン面が前記輪郭座標近傍内に位置するか否かを判定する統合判定装置と、を含み、前記対象物体をポリゴンで構成してなる立体モデルのポリゴンを統合により削減する画像生成方法であって、前記対象物体に係る輪郭座標情報を準備し、前記対象物体をポリゴンで構成する立体モデルのポリゴンをその数が低減するように統合した場合に作成されるポリゴン面が、前記対象物体に係る輪郭座標近傍内に位置するか否かを判定し、前記ポリゴン面が前記輪郭座標近傍内に位置すると判定した場合に、前記統合したポリゴンを採用することを特徴とする。
【００２４】
この発明に係る画像生成方法は、対象物体に係る輪郭座標情報と、該対象物体をポリゴンにより構成する立体モデルの該ポリゴンの頂点座標情報とを記憶するメモリ装置と、前記対象物体をポリゴンで構成する立体モデルのポリゴンをその数が低減するように統合するポリゴン統合装置と、前記対象物体をポリゴンで構成する立体モデルのポリゴンをその数が低減するように統合した場合に作成されるポリゴンの代表点座標情報と前記輪郭座標情報とから該ポリゴンの統合が統合基準を満たすか否かを判定する統合判定装置と、を含み、前記対象物体をポリゴンで構成してなる立体モデルのポリゴンを統合により削減する画像生成方法であって、前記対象物体に係る輪郭座標情報を準備し、前記対象物体をポリゴンで構成する立体モデルのポリゴンをその数が低減するように統合した場合に作成されるポリゴンの代表点座標情報と前記対象物体に係る輪郭座標情報とから該ポリゴンの統合が統合基準を満たすか否かを判定し、前記統合基準を満たす場合に前記統合したポリゴンを採用することを特徴とする。
【００２５】
この発明に係る画像生成方法は、対象物体の原型立体モデルを所定の倍率に拡大または縮小することにより得られる輪郭座標情報及び前記対象物体をポリゴンで構成する立体モデルの頂点座標情報を記憶するメモリ装置と、前記対象物体をポリゴンで構成する立体モデルのポリゴンをその数が低減するように統合するポリゴン統合装置と、前記対象物体をポリゴンで構成する立体モデルのポリゴンをその数が低減するように統合した場合に作成されるポリゴンの代表点座標情報を前記立体モデルが前記倍率後の原型立体モデルと同スケールになるように変換してなる情報と前記輪郭座標情報とから該ポリゴンの統合が統合基準を満たすか否かを判定する統合判定装置と、を含み、前記対象物体をポリゴンで構成してなる立体モデルのポリゴンを統合により削減する画像生成方法であって、対象物体の原型立体モデルを所定の倍率に拡大または縮小することにより得られる輪郭座標情報を準備し、前記対象物体をポリゴンで構成する立体モデルのポリゴンをその数が低減するように統合した場合に作成されるポリゴンの代表点座標情報と前記輪郭座標情報とから該ポリゴンの統合が統合基準を満たすか否かを判定し、前記統合基準を満たす場合に前記統合したポリゴンを採用することを特徴とする。
【００２６】
前記ポリゴンの統合は、ポリゴンの２頂点または３頂点を統合する、若しくは、ポリゴンの再配置によって統合することを特徴とする。
【００２７】
この発明に係る画像生成プログラムを記憶した記憶媒体は、対象物体に係る輪郭座標情報を準備するステップと、前記対象物体をポリゴンで構成する立体モデルのポリゴンをその数が低減するように統合した場合に作成されるポリゴン面が、前記対象物体に係る輪郭座標近傍内に位置するか否かを判定するステップと、前記ポリゴン面が前記輪郭座標近傍内に位置すると判定した場合に、前記統合したポリゴンを採用するステップと、を含むことを特徴とする。
【００２８】
この発明に係る画像生成プログラムを記憶した記憶媒体は、対象物体に係る輪郭座標情報を準備するステップと、前記対象物体をポリゴンで構成する立体モデルのポリゴンをその数が低減するように統合した場合に作成されるポリゴンの代表点座標情報と前記対象物体に係る輪郭座標情報とから該ポリゴンの統合が統合基準を満たすか否かを判定するステップと、前記統合基準を満たす場合に前記統合したポリゴンを採用するステップと、を含むことを特徴とする。
【００２９】
この発明に係る画像生成プログラムを記憶した記憶媒体は、対象物体の原型立体モデルを所定の倍率に拡大または縮小することにより得られる輪郭座標情報を準備するステップと、前記対象物体をポリゴンで構成する立体モデルのポリゴンをその数が低減するように統合した場合に作成されるポリゴンの代表点座標情報と前記輪郭座標情報とから該ポリゴンの統合が統合基準を満たすか否かを判定するステップと、前記統合基準を満たす場合に前記統合したポリゴンを採用するステップと、を含むことを特徴とする。
【００３０】
【発明の実施の形態】
この発明の画像生成装置について図面を参照して説明する。特に制限はないが、この発明は対象物体の立体モデルを生成する三次元モデリングシステム用に構成されている。
【００３１】
図１はこの発明の実施の形態１である画像生成装置２０のブロック図である。図において、画像生成装置２０は、多数のポリゴンにより構成される対象物体の原型立体モデルを、原型立体モデルの輪郭面近傍に、ポリゴン面を保持するという制約条件の基に、ポリゴンを削減し、原型立体モデルを近似する小数のポリゴンで構成される簡略化立体モデルを得ることができる。
【００３２】
図において、画像生成装置２０は、原型立体モデルの輪郭面上のドットの座標に対応する輪郭座標情報を記憶する輪郭情報メモリ装置２２を有する。
【００３３】
ここで輪郭面上のドットとは、所定の単位間隔でサンプルした、輪郭面上の点の集合のことである。
【００３４】
立体モデルを構成する各ポリゴンの頂点座標及びそれらの接続関係を表すポリゴンメッシュ情報を記憶するポリゴンメッシュメモリ装置２４を有する。
【００３５】
ポリゴンメッシュより、所定の方法で隣接する２つの頂点を選択し、選択された２つの頂点を１つの頂点に統合する頂点統合試行装置２６を有する。
【００３６】
頂点の統合により変形する変形ポリゴンを抽出し、該変形ポリゴンの各ポリゴン面上のサンプル点を代表点として算出する、代表点算出装置２８を有する。
【００３７】
代表点情報、輪郭座標情報を用いて、頂点の統合によるポリゴン削減処理が妥当か否かを判定する統合判定装置３０を有する。
【００３８】
頂点統合基準を満たす場合には、ポリゴンメッシュより、前記、選択された２頂点と他の１頂点からなるポリゴンを全て消去し、さらに、選択された２頂点を、前記統合頂点に置き換えるポリゴン削減装置３２を含む。
【００３９】
まず、三次元スキャナ装置３４により、対象物体の輪郭表面の各ドットの座標を取得し、これを輪郭情報メモリ装置２２に記憶する。さらに、各ドットを頂点とする三角形ポリゴンメッシュからなる初期ポリゴンメッシュを生成し、これを、ポリゴンメッシュメモリ２４に記憶する。なお、本実施の形態の対象物体には、実物体やコンピュータ上の仮想物体を含むものである。
【００４０】
前記輪郭座標情報は、三次元空間を表す配列であるボクセルメモリや、輪郭点の座標値のリストメモリとして記憶することができるが、ここでは、ボクセルメモリで記憶するものとする。
【００４１】
ボクセルメモリは、例えば、立体モデルの幅×高さ×奥行きのサイズの三次元配列メモリである。該配列メモリ全体をボクセルメモリ、またはボクセル空間、配列の各要素をボクセル、配列の各要素の値をボクセル値と呼ぶ。横方向にｘ、奥行き方向にｙ、高さ方向にｚの位置のボクセルをボクセル（ｘ，ｙ，ｚ）とすると、ボクセル（ｘ，ｙ，ｚ）と三次元空間中の点（ｘ，ｙ，ｚ）は１対１に対応する。
【００４２】
輪郭座標情報は、原型立体モデルの輪郭面上のドットの集合を（Ｘｉ，Ｙｉ，Ｚｉ），ｉ＝１，・・，ｎとするとき、ボクセル（Ｘｉ，Ｙｉ，Ｚｉ），ｉ＝１，・・・，ｎの値を「１」とし、それ以外のボクセルの値を「０」にすることによって記憶する。ここでボクセル値「１」のボクセルを輪郭ボクセルと定義する。
【００４３】
この構成により、初期値のポリゴンメッシュを簡略化する際に、原型立体モデルの輪郭面上の各ドットとポリゴン面との距離の計算を省略することができる。
【００４４】
頂点統合試行装置２６は、ポリゴンメッシュを構成するポリゴンから、所定の順序で、隣接する２つの頂点を選択し、選択した２つの頂点を統合した１つの頂点、例えば、２つの頂点の平均点（中点）に統合する。
【００４５】
さらに、代表点算出装置２８は、頂点の統合によって変形する各ポリゴン面上の代表点の座標を算出する。例えば、統合頂点座標、および各変形ポリゴンの３頂点の重心座標、を算出する。
【００４６】
頂点の統合判定装置３０は、前記代表点の各座標に対応するボクセル値を輪郭情報メモリ装置２２から読み出し、読み出した各ボクセル値が「１」もしくは「０」かを判定する。各ボクセル値の全てについて判定結果が「１」の時は、代表点のすべてが、いずれかの輪郭点に一致することになり、統合基準を満たすことになる。一方、各ボクセル値のうち、少なくとも１つの判定結果が「０」の場合は、統合基準を満たさないこととなる。
【００４７】
頂点統合基準を満たすと判定された場合には、ポリゴン削減装置３２により、統合前のポリゴンメッシュより、選択された２頂点と他の１つの頂点により構成される全てのポリゴンを削除し、さらに、選択された２頂点を統合頂点に書き替えることで、ポリゴンメッシュを簡略化することができる。
【００４８】
一方、統合基準を満たさない場合は算出した統合頂点を破棄する。
【００４９】
この結果、原型立体モデルの表現精度が劣化することを防止することができる。
【００５０】
ここで、原型立体モデルは、初期立体モデルまたは前記対象物体をポリゴンにより構成する立体モデルの前段の立体モデルでもよい。
【００５１】
このようなポリゴンメッシュの簡略化処理を上記の処理を、ポリゴンメッシュ上の全ての隣接する２頂点について繰り返し、ポリゴンの数が減少しなくなった時点でポリゴンの削減処理を終了させることができる。
【００５２】
この簡略化された、もしくは、簡略途上の三次元画像を表示装置３６に表示させることができる。
【００５３】
図２は上記ボクセル空間５０の斜視図である。図において、ボクセル空間５０は、Ｘ，ＹおよびＺ座標で指定する立体モデル５２をデジタル情報で収容する。本実施の形態では、ボクセル空間を立方形状のメモリ空間に構成したが、立方形状の他に立体モデル５２を収容できる手段であれば円柱形状や円錐形状のボクセル空間を用いてもよいことは勿論である。
【００５４】
図３は立体モデル５２をＡ−Ａ面で切断した座標Ｘ−Ｚの断面図である。立体モデル５２の輪郭５８交差するとボクセル空間５０のボクセル５６にはボクセル値「１」が記憶され、他の輪郭５８と交差しないボクセル５６にはボクセル値「０」が記憶されている。この断面を拡大したものを図４に示す。
【００５５】
図４は、立体モデル５２の輪郭５８上に位置する初期値ポリゴンの頂点ａ，ｂ，ｃ，ｄ、該頂点からなる初期値ポリゴン面、頂点ｂ，ｃを統合した統合頂点ｅ、頂点統合により変形させた新たなポリゴン面の拡大図である、ポリゴンの削減は、統合頂点ｅ、および、頂点統合後のポリゴンの各重心ｆ，ｇの全てが、斜線で示したボクセル値「１」のボクセル内にあれば統合基準を満たすものとして、もとのポリゴン面を新しいポリゴン面に変形し、そうでない場合には、統合基準を満たさないものとして、変形を行わないように構成されている。このように構成された三次元画像生成装置は、立体モデルの輪郭上の各ドットと、変形後の新しいポリゴン面との距離を演算する必要もないので、極めて高速なポリゴン削減処理を実行することができる。例えば、初期値が６６，９３９個のポリゴン頂点で１３３，８６４個の三角形ポリゴンを含むポリゴンメッシュを等倍の縮尺でボクセル空間に記憶してから、１，３３０個のポリゴンに削減した三次元の画像処理をコンピュータでシミュレーションした場合、４０秒の処理時間で図５の三次元の画像を生成することができる。
【００５６】
図６は本実施の形態によるポリゴンメッシュを削減する画像生成の行程図である。図左側の立体モデル５２は輪郭に沿って生成された複数の頂点６０を有する三角形のポリゴンメッシュで構成され、図左側に示すポリゴンメッシュは、ａ頂点６０とｂ頂点６０を結ぶ三角形の１辺の中点ｃを新たな統合頂点６２として、統合頂点６２もポリゴン７０から７６の重心６４もそれぞれ立体モデル５２の輪郭５８が位置するボクセル値１のボクセルに位置する。一方、図７左側の立体モデル５２は図６と同様に輪郭に沿って生成された複数の頂点６０を有する三角形ポリゴンメッシュで構成され、図７左側に示すポリゴンメッシュは、ａ頂点６０とｂ頂点６０を結ぶ三角形の１辺の中点ｃを新たな統合頂点６２としてポリゴンを統合しているが、立体モデルの曲率の大きい部分の太線で示すポリゴン７７は、その重心６４が立体モデル５２の輪郭５８から外れてボクセル値０のボクセルに位置しているため、統合基準を満たさない。したがって、ポリゴンの統合頂点６２または重心６４が位置するボクセル値を読出すだけで統合基準を満たすか否かを判断できるため、従来の立体モデルの輪郭面上のドットと統合した場合のポリゴン面との距離演算結果が閾値を越えるか否かを判定する必要がなくポリゴン削除処理を高速に処理することができる。また、曲率が小さな立体モデルの場合は重心６４の判定を省略しても統合頂点６２がボクセル値「１」のボクセル空間に位置するか否かを判定するだけで表現精度の高い三次元画像を生成することができる。
【００５７】
上記実施の形態では、原型立体モデルを等倍の縮尺でボクセル空間に記憶させたが、図８に示すボクセル空間のように、原型立体モデル５２を所定の倍率で拡大または縮小してから、ボクセルに記憶してもよい。
【００５８】
このとき該倍率をＳとすれば、Ｓ＜１のときは、輪郭点（Ｘｉ，Ｙｉ，Ｚｉ），ｉ，＝１，・・・，ｎに対して、ボクセル（ＳｘＸｉ，ＳｘＹｉ，ＳｘＺｉ），ｉ＝１，・・・，ｎの値を「１」とし、それ以外のボクセルの値を「０」にすることによって記憶する。
【００５９】
Ｓ＞１の場合は、元の単位間隔の１／Ｓ倍の間隔で輪郭点をサンプルし直したものを改めて（Ｘｉ，Ｙｉ，Ｚｉ），ｉ＝１，・・・，ｎとした後、ボクセル（ＳｘＸｉ，ＳｘＹｉ，ＳｘＺｉ），ｉ＝１，・・・，ｎの値を「１」とし、それ以外のボクセルの値を「０」にすることによって記憶する。
【００６０】
図８はこの発明の実施の形態３である画像生成装置のボクセル空間の断面図である。図において、画像生成装置は、三次元スキャナなどにより抽出した原型立体モデルを等倍または所定の倍率で拡大または縮小して求められた輪郭座標情報を記憶する第１のメモリ領域８２内のボクセル空間９１を含み、ポリゴンの頂点座標情報を第２のメモリ領域８４から読みだして、このポリゴンの少なくとも１つの頂点を変位させた統合頂点座標の位置に対応する輪郭座標情報を第１のメモリ領域８２のボクセル９１から読出して、統合基準を満たすか否かを統合判定装置３０で判定させ、統合頂点が統合基準を満たす場合は、ポリゴン削減装置３２で、統合頂点からなるポリゴンを採用し、ポリゴン数を削減することができる。前記統合判定装置においては、前記倍率をＳ、代表点の集合を（Ｕｉ，Ｖｉ，Ｗｉ），ｉ＝１，・・・，ｍとするとき、ボクセル（ＳｘＵｉ，ＳｘＶｉ，ＳｘＷｉ），ｉ＝１，・・・，ｍの値がすべて「１」のとき、統合基準を満たすものとする。例えば、幅１００ドット×高さ１００ドット×奥行き１００ドットの立体モデルを２分の１に縮小した場合、輪郭座標を表すボクセル空間は幅５０ボクセル×高さ５０ボクセル×奥行き５０ボクセルとなる。このように縮小ボクセル空間を用いた場合、頂点統合基準が緩和される結果、立体モデルをより少ない数のポリゴンに簡略化することができる。
【００６１】
一方、拡大ボクセル空間を用いた場合には、より近似精度の高い簡略化ポリゴンを求めることができる。
【００６２】
ここで、縮小率を変えることにより、簡略化されたポリゴンの数を変えることができる。図９は初期値の三次元配列を２分の１の倍率で縮尺したポリゴンメッシュの斜視図である。このポリゴンメッシュの初期値は１０６，８２６個のポリゴン頂点を２１３，６４８個の三角形ポリゴンで構成したポリゴンメッシュであり、このポリゴンメッシュを１／２の縮尺でボクセル空間に記憶してから、１，６８０個のポリゴンに削減する画像処理をコンピュータでシミュレーションした結果、５０秒の処理時間で画像を生成することができる。本実施の形態によって、立体モデルの各部の曲率が小さいものであれば、表現精度を劣化させることなく、立体モデルをより少ない数のポリゴンで近似する簡略化されたポリゴンメッシュを得ることができる。
【００６３】
上記実施の形態では、立体モデルの縮尺倍率を一律に定めたが、この発明の実施の形態４である画像生成装置では、精細な立体モデルの三次元画像を生成する場合、例えば、図９に示す人形の鼻の形状部分を倍率１の尺度で処理し、比較的平らな面の耳の内側や底面を倍率１／２若しくは１／３の尺度で処理することにより高速で且つ表現精度の高い画像を生成することができる。
【００６４】
さらに、前記倍率は、ｘ軸方向、ｙ軸方向、ｚ軸方向に、それぞれ異なる値を用いてもよい。
【００６５】
また、この発明の実施の形態５である画像生成装置では、図７右側の簡略化したポリゴンメッシュの太線のポリゴン７７の統合頂点６２と重心６４が立体モデル５２の輪郭ボクセルに存在するか否かを判定して、画像生成を行ってもよいことは勿論である。
【００６６】
さらに、この発明の実施の形態６である画像生成装置では、図２に示すボクセル空間５０にデジタル情報で収容した立体モデル５２と、この立体モデル５２に近似するポリゴンメッシュのポリゴン面１００が、輪郭ボクセル内に存在するか否かを判定することができる。図１０は画像生成装置のブロック図である。図示するワークステーション８６は、ボクセル空間５０と接続させ、このボクセル空間５０内に収容された立体モデル５２の輪郭座標情報を記憶させることができ、ポリゴンメッシュを構成する多角形ポリゴン面１００が立体モデル５２の輪郭ボクセルに位置するか否かを判定しながら、画像を生成することができる。
【００６７】
図１１のフローチャートはこの発明の実施の形態７である画像生成の工程を示すものである。
【００６８】
図において、画像生成は、まず、初期ポリゴンメッシュ算出処理１０１では、入力された立体モデルの輪郭面上の各ドットを全て結ぶことによって、三角形ポリゴンメッシュの初期値を生成する。次に、輪郭座標設定処理１０２では、原型立体モデルと簡略化立体モデルとの近似誤差パラメータにもとづいて倍率を定め、該倍率に基づいて原型立体モデルを拡大または縮小し、該拡大または縮小された原型立体モデルの輪郭を、例えば、輪郭面上の各ドットの座標に対応するボクセルのボクセル値を「１」、それ以外のボクセルのボクセル値を「０」とすることによって、ボクセルメモリに記憶する。
【００６９】
頂点選択処理１０３では、ポリゴンメッシュの各頂点より、所定の方法で、同一ポリゴン内の隣接する２つの頂点を選び、頂点統合試行処理１０４において、該２頂点を統合する１つの頂点、例えば、２頂点の中心点に統合する。
【００７０】
さらに、代表点算出処理１０５では、統合前のポリゴンのうち、頂点統合により変形する変形ポリゴンを抽出し、該変形ポリゴン面上のサンプル点を代表点として算出する。例えば、統合頂点座標、および各変形ポリゴンの重心点座標を算出する。
【００７１】
頂点統合判定処理１０６では、前記代表点のそれぞれについて、それぞれの座標に対応するボクセル値を、輪郭座標情報を記憶したボクセルメモリより読み出し、ボクセル値が「１」か否かを調べ、前記、代表点の全てに対するボクセル値が「１」の場合には頂点統合基準を満たすものとし、少なくとも１つのボクセル値が「０」の場合には統合基準を満たさないものとする。
【００７２】
頂点統合基準を満たす場合には、ポリゴン削減処理１０７において、ポリゴンメッシュより、前記選択された２頂点と他の１頂点からなるポリゴンを全て消去し、さらに、選択された２頂点を、前記統合頂点に置き換え、ポリゴンメッシュを書き換える。
【００７３】
一方、頂点統合基準を満たさない場合には、統合頂点を破棄し、ポリゴンメッシュ情報を書き替えない。
【００７４】
終了判定処理１０８では、ある段階のポリゴンメッシュに対して、該ポリゴンメッシュ上の隣接する２頂点の全ての組合せについて、頂点統合基準が満たされない場合には、それ以上、ポリゴンを削減できないものと判断し、処理を終了する。あるいは、ポリゴン数があるしきい値以下になった時点で、処理を終了してもよい。さらに、この発明の実施の形態８である上記画像生成方法を実行するプログラムを磁気ディスク装置、光ディスク装置、フロッピィディスクなどのデジタル情報が記憶できる媒体に記憶し、ＣＡＤシステムやゲーム装置用カセットに供給することができる。つまり、複数のポリゴンの頂点６０のボクセル情報と立体モデルの輪郭ボクセル情報をメモリ装置２２に記憶するステップと、該ポリゴンを統合する統合頂点ボクセル情報６２に対応する輪郭５８のボクセル情報をメモリ装置２２から読出してボクセル値「１」または「０」の統合基準を満たすか否かを判定するステップと、統合頂点６２が統合基準を満たす場合はメモリ装置２２の内容を統合頂点６２のボクセル情報に書換えるステップと、書換えられたボクセル情報「１」に基づきポリゴンからなる線図をディスプレイ４２に表示させるステップとを含む画像生成プログラムを記憶させることができる。
【００７５】
図１２はこの発明の他の実施の形態である６角形のポリゴンで構成するポリゴンメッシュの斜視図である。ポリゴンメッシュの複数の統合頂点６２とポリゴン面１００を立体モデル５２の輪郭５８に対応させて、統合基準を満たすか否かを判断して生成されたものである。したがって、この発明のポリゴンは、上述した三角形ポリゴンの他に三次元の画像を表現できるポリゴンメッシュを構成できる手段であれば、４角形、６角形、８角形などの多角形で構成できることは勿論である。
【００７６】
上記実施の形態では、隣接する２つのポリゴン頂点をポリゴンメッシュメモリ２４から読み出して１つの統合頂点を形成したが、多角形ポリゴンメッシュを簡略化できる手段であれば統合する２つの頂点の他に、３つの頂点でも４つの頂点でも頂点の平均点に統合頂点を形成でき、また、図１５の辺分割３や同図の辺変換４のように多角形ポリゴンを再配置することもできる。この様な構成によっても上記と同様の効果を奏する。さらに、立体モデルの表面各部の輝度または色を形成する画素値に対応する領域、例えば、対象物体のモデルが人形の場合に黒色の目や肌色の頬にそれぞれ対応する輝度またはパレット色に分割された相互に異なる表面領域が統合されないように、目と頬の部分を覆うような多角形ポリゴンの形成を禁止する追加の統合基準を定めることができる。したがって、統合判定装置はこの追加の統合基準に基づいて、統合基準を満たすか否かを判定することができる。この様な構成によりポリゴンに動きを与える動画処理を自然な表現で実行させることができる。
【００７７】
また、上記実施の形態では、ポリゴンメッシュの全体に対して統合頂点を定めて不要なポリゴンを削除したが、ポリゴンが削除できる手段であればポリゴンメッシュの簡略化は、立体モデル形状の対称性を考慮してポリゴンを統合することができる。すなわち、対象物体が人形のような左右対称の立体モデルの場合は、顔面の左右を対称にするために、例えば、右側面の顔と左側面の顔を同等のポリゴンメッシュで構成することができる。この対象性を利用して右側のポリゴンメッシュを簡略化してから、左側に写像する座標計算を施して左側のポリゴンメッシュに転写することができる。この様な構成により、顔面部分の簡略化処理を約半分の処理時間で完了させることができる。
【００７８】
【発明の効果】
この発明は、以上説明したように構成されているので、以下の効果を奏する。
【００７９】
立体モデルの輪郭ボクセルとポリゴンの代表点座標を比較して統合基準を満たすか否かを判定するので、演算変数が激減し画像の表現精度を劣化させずに画像生成を高速処理することができる。
【００８０】
立体モデルの輪郭もポリゴンの頂点もボクセル情報に変換して記憶し、両者が一致するか否かを判定するので、頂点、輪郭の座標演算やベクトルの生成も不要となるので、画像生成の処理が短時間で完了させることができる。
【００８１】
立体モデルを所定の倍率で圧縮記憶したので、ボクセル数を低減することができ、これにより演算変数が激減するので画像生成の処理が短時間で完了させることができる。
【００８２】
立体モデルの各部の曲率に応じて倍率を変化させるため、画像生成が短時間で且つ表現精度の高い画像を生成することができる。
【００８３】
ポリゴン面の所定の点が立体モデルの輪郭ボクセルに位置するか否かを判定するので、より表現精度の高いポリゴンメッシュを変形処理することができる。
【図面の簡単な説明】
【図１】  この発明の実施の形態を示す画像生成装置のブロック図である。
【図２】  この発明のボクセル空間の斜視図である。
【図３】  この発明のボクセル空間の断面図である。
【図４】  この発明の断面ボクセル空間の拡大図である。
【図５】  この発明の実施の形態の画像生成装置で生成した画像の斜視図である。
【図６】  この発明の実施の形態を示す画像生成の工程図である。
【図７】  この発明の実施の形態を示す画像生成の工程図である。
【図８】  この発明の実施の形態を示す画像生成の工程図である。
【図９】  この発明の実施の形態の画像生成装置で生成した画像の斜視図である。
【図１０】  この発明の実施の形態を示す画像生成装置のブロック図である。
【図１１】  この発明の実施の形態を示す画像生成方法のフローチャート図である。
【図１２】  この発明の他の実施の形態の画像生成装置で生成した画像の斜視図である。
【図１３】  従来の初期値のポリゴンメッシュの斜視図である。
【図１４】  従来の簡略化ポリゴンメッシュの斜視図である。
【図１５】  従来のポリゴンメッシュの変形方法を示す工程図である。従来の初期値のポリゴンメッシュの斜視図である。
【符号の説明】
２０  画像生成装置、２２  輪郭情報メモリ装置、２４  ポリゴンメッシュメモリ、２６  頂点統合試行装置、２８  代表点算出装置、３０  統合判定装置、３２  ポリゴン削減装置、３４  三次元スキャナ装置、３６  表示装置、５０  ボクセル空間、５２  立体モデル、５６  ボクセル、５８  輪郭、６０  頂点、６２  統合頂点、６４  重心、７７  ポリゴン、８２  第１のメモリ領域、８４
第２のメモリ領域、１００  ポリゴン面。
【図１】
0003973273.tif 000002
【図２】
0003973273.tif 000003
【図３】
0003973273.tif 000004
【図４】
0003973273.tif 000005
【図５】
0003973273.tif 000006
【図６】
0003973273.tif 000007
【図７】
0003973273.tif 000008
【図８】
0003973273.tif 000009
【図９】
0003973273.tif 000010
【図１０】
0003973273.tif 000011
【図１１】
0003973273.tif 000012
【図１２】
0003973273.tif 000013
【図１３】
0003973273.tif 000014
【図１４】
0003973273.tif 000015
【図１５】
0003973273.tif 000016