(57)【特許請求の範囲】
【請求項１】
複数の多角形で構成された３次元的な形状データとテクスチャを含む３次元モデルを圧縮する方法であって、
前記形状データを複数の部分形状データに分割する形状データ分割過程と、
前記分割された複数の部分形状データが前記テクスチャ上でどの領域に対応するかを示す領域データを生成する領域データ生成過程と、
前記部分形状データをより数の少ない複数の多角形で近似した圧縮部分形状データを生成する部分形状データ再構成過程と
を備えて、領域データに保持されている部分形状データの端面の形状と、圧縮部分形状データに保持されている部分形状データを近似した形状との２種類の形状に分けて３次元モデルを記述する３次元モデル圧縮方法。
【請求項２】
複数の多角形で構成された３次元的な形状データとテクスチャを含む３次元モデルを圧縮する方法であって、
前記形状データを複数の部分形状データに分割する形状データ分割過程と、
前記分割された複数の部分形状データが前記テクスチャ上でどの領域に対応するかを示す領域データを生成する領域データ生成過程と、
前記部分形状データをより数の少ない複数の多角形で近似した圧縮部分形状データを生成する部分形状データ再構成過程と
を備えて、領域データに保持されている部分形状データの端面の形状と、圧縮部分形状データに保持されている部分形状データを近似した形状との２種類の形状に分けて３次元モデルを記述するとともに、前記テクスチャを前記領域データの領域ごとに階層化して符号化する階層符号化過程を備えて、テクスチャと領域データとの２種類のデータを組み合わせて１つのデータに圧縮する３次元モデル圧縮方法。
【請求項３】
複数の多角形で構成された３次元的な形状データとテクスチャを含む３次元モデルを圧縮する方法であって、
前記形状データを複数の部分形状データに分割する形状データ分割過程と、
前記分割された複数の部分形状データが前記テクスチャ上でどの領域に対応するかを示す領域データを生成する領域データ生成過程と、
前記部分形状データをより数の少ない複数の多角形で近似した圧縮部分形状データを生成する部分形状データ再構成過程と
を備えて、領域データに保持されている部分形状データの端面の形状と、圧縮部分形状データに保持されている部分形状データを近似した形状との２種類の形状に分けて３次元モデルを記述するとともに、前記形状データ分割過程は、形状データを構成する複数の多角形の頂点間距離を基準にして形状データを複数の部分形状データに分割する３次元モデル圧縮方法。
【請求項４】
３次元的な形状データとテクスチャを含む３次元モデルから画像を生成する方法であって、
階層符号化されたテクスチャデータを入力し、復号化して複数のテクスチャと、前記複数のテクスチャの画素が有効な領域を示す複数のマスクデータを出力する復号化過程と、
前記複数のテクスチャと前記複数のマスクデータと複数の形状データを入力して、前記複数のマスクデータをマスクとしたテクスチャマッピングによって画像生成処理を行うマッピング過程と
を備えて、階層符号化されたテクスチャデータに含まれる各階層の輪郭の形状と、形状データに含まれる形状との２つの形状を反映した画像を生成する
３次元モデル画像生成方法。
【請求項５】
複数の多角形で構成された３次元的な形状データとテクスチャを含む３次元モデルを圧縮する装置であって、
前記形状データを複数の部分形状データに分割する形状データ分割手段と、
前記分割された複数の部分形状データが前記テクスチャ上でどの領域に対応するかを示す領域データを生成する領域データ生成手段と、
前記部分形状データをより数の少ない複数の多角形で近似した圧縮部分形状データを生成する部分形状データ再構成手段と
を備えた３次元モデル圧縮装置。
【請求項６】
複数の多角形で構成された３次元的な形状データとテクスチャを含む３次元モデルを圧縮する装置であって、
前記形状データを複数の部分形状データに分割する形状データ分割手段と、
前記分割された複数の部分形状データが前記テクスチャ上でどの領域に対応するかを示す領域データを生成する領域データ生成手段と、
前記部分形状データをより数の少ない複数の多角形で近似再構成する部分形状データ再構成手段と、
テクスチャを前記領域データの領域ごとに階層化して符号化する階層符号化手段を備えた３次元モデル圧縮装置。
【請求項７】
形状データ分割手段は、形状データを構成する複数の多角形の頂点間距離を基準にして形状データを複数の部分形状データに分割する
請求項５または請求項６記載の３次元モデル圧縮装置。
【請求項８】
３次元的な形状データとテクスチャを含む３次元モデルから画像を生成する装置であって、
階層符号化されたテクスチャデータを入力し、復号化して複数のテクスチャと、前記複数のテクスチャの画素が有効な領域を示す複数のマスクデータを出力する復号化手段と、
前記複数のテクスチャと前記複数のマスクデータと複数の形状データを入力して、前記複数のマスクデータをマスクとしたテクスチャマッピングによって画像生成処理を行うマッピング手段と
を備えた３次元モデル画像生成装置。
【請求項９】
請求項１〜請求項３の何れかの３次元モデル圧縮方法、または請求項４記載の３次元モデル画像生成方法を実行するのに必要なソフトウェアが書き込まれた記録媒体。
【請求項１０】
複数の多角形で構成された３次元的な形状データとテクスチャを含む３次元モデルを圧縮する装置であって、
前記形状データを複数の部分形状データに分割する形状データ分割手段と、
前記分割された複数の部分形状データが前記テクスチャ上でどの領域に対応するかを示す領域データを生成する領域データ生成手段と、
前記部分形状データをより数の少ない複数の多角形で近似した圧縮部分形状データを生成する部分形状データ再構成手段と、
前記圧縮部分形状データと前記領域データとを用いて画像を合成する画像合成手段と
を備えた画像合成装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ビデオゲーム機や産業用ＣＡＤなどの３次元コンピュータグラフィックスを使った画像生成で用いられる、３次元モデルを生成する技術に関するものであり、特に、あらかじめ与えられた３次元モデルを圧縮して、データ量が少なく、かつデータ量削減に伴う画像の劣化が少ない３次元モデルを生成する３次元モデル圧縮方法に関するものである。
【０００２】
【従来の技術】
従来より、物体の３次元的な形状データを用いて画像生成を行う３次元コンピュータグラフィックスの技術が盛んに研究されている。近年では、ビデオゲーム機やパーソナルコンピュータなどの家庭用の比較的安価な機器でも、３次元コンピュータグラフィックスの技術を用いた画像生成が盛んに行われるようになり、産業的にも非常に重要な技術の１つとなっている。
【０００３】
３次元コンピュータグラフィックスによる画像生成は、対象物の３次元的な形状や色の情報で構成される３次元モデルを生成するモデリングと、３次元モデルを用いて対象物の画像を生成するレンダリングとの、大きく２つのステップに分けることができる。
【０００４】
モデリングによって生成される３次元モデルの記述方法の１つとして、対象物表面の３次元的な形状を、複数の多角形の集まりによって近似表現したポリゴンモデルが広く用いられている。また、ポリゴンモデルを用いたレンダリング方法の１つとして、複数の多角形を任意の２次元平面に順次投影していき、多角形の集まりとして対象物画像を描画する方法が広く用いられている。
【０００５】
このようなポリゴンモデルを用いた画像生成では、より多くの多角形を用いることによって、細かな凹凸や滑らかな曲面を持つ対象物をより忠実に反映した画像を生成できるが、その反面、データ量が多くなるため、３次元モデルの記録・伝送時のコストが高くなる。逆に、多角形の数を減らすとデータ量は少なくなるが、生成される画像は粗く劣化の多い画像になるという傾向がある。
【０００６】
そこで近年、モデリング技術の１分野として、対象物表面の３次元座標値を緻密に計測することが可能な３次元計測機器などで得られた大量の多角形を用いた詳細なポリゴンモデルを入力とし、これを圧縮して、データ量が少なくかつデータ量の削減にともなう画像の劣化が少ない、効率の良い３次元モデルを生成する、３次元モデル圧縮技術が盛んに研究されている。
【０００７】
上記した従来の３次元モデル圧縮技術の一例としては、例えば「Ｈｕｇｕｅｓ  Ｈｏｐｐｅ，  ｅｔ  ａｌ：”Ｍｅｓｈ  Ｏｐｔｉｍｉｚａｔｉｏｎ”，  ＳＩＧＧＲＡＰＨ  ９３  Ｃｏｎｆｅｒｅｎｃｅ  Ｐｒｏｃｅｅｄｉｎｇｓ，
ｐｐ．１９−２６，  Ａｕｇｕｓｔ  １９９３」などがある。
【０００８】
これらの３次元モデル圧縮方法の一例では、詳細なポリゴンモデル中の複数の多角形を、より数の少ない多角形で近似再構成することによって、データ量を少なくしている。近似再構成の方法は、まず、近似前のポリゴンモデルと近似後のポリゴンモデルとの近似誤差を定量化する関数を定義しておき、近似前のポリゴンモデル中の多角形の全ての頂点について、１頂点を削減してより少ない多角形で近似した場合の近似誤差の増分を算出する。そして、近似誤差の増分が最も少ない頂点を選択して削減し、ポリゴンモデルの近似再構成を行う。さらに、１頂点の削減によるポリゴンモデルの近似を、あらかじめ与えられた条件に到達するまで繰り返すことにより、頂点数と多角形数の少ないポリゴンモデルを生成する。
【０００９】
この時、近似再構成による頂点数と多角形数の削減、すなわちデータ量の削減に対して、近似誤差の増分が最も少ない頂点、すなわち生成される画像の劣化が最も少ない頂点から順に削減していくため、結果として効率の良い３次元モデルを生成する圧縮方法と言える。
【００１０】
【発明が解決しようとする課題】
しかし、上記した従来のモデリング技術では、ポリゴンモデルの全ての頂点について、同じ近時誤差関数を用いた評価を行うが、生成される画像上で輪郭（対象物と背景や前景との境界）となる部分と、輪郭以外の部分とでは、近似誤差による誤差増分が同じであっても、輪郭部分の方が画像の劣化が目立つ場合が多いことから、生成される画像の劣化とデータ量の観点から必ずしも効率が良いとは言えない場合があるという問題点を有していた。
【００１１】
このような、生成された画像上で輪郭となる部分の劣化が目立つという問題は、先述した  Ｈｏｐｐｅらも”Ｖｉｅｗ−Ｄｅｐｅｎｄｅｎｔ  Ｒｅｆｉｎｅｍｅｎｔ  ｏｆ  Ｐｒｏｇｒｅｓｓｉｖｅ  Ｍｅｓｈｅｓ”（ＳＩＧＧＲＡＰＨ  ９７  Ｃｏｎｆｅｒｅｎｃｅ  Ｐｒｏｃｅｅｄｉｎｇｓ，  ｐｐ．１８９−１９８，  Ａｕｇｕｓｔ  １９９７）の中で指摘している。  Ｈｏｐｐｅらはこれに対処するために、詳細な３次元モデルと粗いモデルを階層的に記述して保持しておき、画像生成時に輪郭となる部分に詳細な３次元モデルを選択して使う方法を提案している。しかし、この方法は３次元モデルの圧縮が主眼ではなく、輪郭部の画質劣化は少ないがデータ量が多くなるという問題点を有している。
【００１２】
本発明は上記問題点に鑑み、データ量が少なくかつデータ量削減による画像の劣化が少ない、効率の良い３次元モデルを生成する３次元モデル圧縮方法を提供することを目的とする。
【００１３】
【課題を解決するための手段】
本発明の３次元モデル圧縮方法および３次元モデル画像生成方法は、対象物の形状や対象となる３次元モデルによっては、画像生成時に輪郭となる可能性が高い部位をあらかじめ想定できる場合があり、さらに３次元モデルと輪郭に相当する情報を組み合わせることにより３次元モデルを記述することを特徴とする。
【００１４】
この本発明によると、分割された部分形状データの境界部分の形状を、新たに生成した領域データとして記述することによって、部分形状データを近似再構成した場合の部分形状データの境界部分、すなわち画像生成時に輪郭となる可能性のある部分の画質の劣化を低減することが可能で、かつデータ量の少ない３次元モデルを生成する圧縮方法を実現できる。
【００１５】
【発明の実施の形態】
請求項１記載の３次元モデル圧縮方法は、複数の多角形で構成された３次元的な形状データとテクスチャを含む３次元モデルを圧縮する方法であって、前記形状データを複数の部分形状データに分割する形状データ分割過程と、前記分割された複数の部分形状データが前記テクスチャ上でどの領域に対応するかを示す領域データを生成する領域データ生成過程と、前記部分形状データをより数の少ない複数の多角形で近似した圧縮部分形状データを生成する部分形状データ再構成過程とを備えて、領域データに保持されている部分形状データの端面の形状と、圧縮部分形状データに保持されている部分形状データを近似した形状との２種類の形状に分けて３次元モデルを記述することを特徴とする。
【００１６】
請求項２記載の３次元モデル圧縮方法は、複数の多角形で構成された３次元的な形状データとテクスチャを含む３次元モデルを圧縮する方法であって、前記形状データを複数の部分形状データに分割する形状データ分割過程と、前記分割された複数の部分形状データが前記テクスチャ上でどの領域に対応するかを示す領域データを生成する領域データ生成過程と、前記部分形状データをより数の少ない複数の多角形で近似した圧縮部分形状データを生成する部分形状データ再構成過程とを備えて、領域データに保持されている部分形状データの端面の形状と、圧縮部分形状データに保持されている部分形状データを近似した形状との２種類の形状に分けて３次元モデルを記述するとともに、前記テクスチャを前記領域データの領域ごとに階層化して符号化する階層符号化過程を備えて、テクスチャと領域データとの２種類のデータを組み合わせて１つのデータに圧縮することを特徴とする。
【００１７】
請求項３記載の３次元モデル圧縮方法は、複数の多角形で構成された３次元的な形状データとテクスチャを含む３次元モデルを圧縮する方法であって、前記形状データを複数の部分形状データに分割する形状データ分割過程と、前記分割された複数の部分形状データが前記テクスチャ上でどの領域に対応するかを示す領域データを生成する領域データ生成過程と、前記部分形状データをより数の少ない複数の多角形で近似した圧縮部分形状データを生成する部分形状データ再構成過程とを備えて、領域データに保持されている部分形状データの端面の形状と、圧縮部分形状データに保持されている部分形状データを近似した形状との２種類の形状に分けて３次元モデルを記述するとともに、前記形状データ分割過程は、形状データを構成する複数の多角形の頂点間距離を基準にして形状データを複数の部分形状データに分割することを特徴とする。
【００１８】
請求項４記載の３次元モデル画像生成方法は、３次元的な形状データとテクスチャを含む３次元モデルから画像を生成する方法であって、階層符号化されたテクスチャデータを入力し、復号化して複数のテクスチャと、前記複数のテクスチャの画素が有効な領域を示す複数のマスクデータを出力する復号化過程と、前記複数のテクスチャと前記複数のマスクデータと複数の形状データを入力して、前記複数のマスクデータをマスクとしたテクスチャマッピングによって画像生成処理を行うマッピング過程とを備えて、階層符号化されたテクスチャデータに含まれる各階層の輪郭の形状と、形状データに含まれる形状との２つの形状を反映した画像を生成することを特徴とする。
【００１９】
請求項５記載の３次元モデル圧縮装置は、複数の多角形で構成された３次元的な形状データとテクスチャを含む３次元モデルを圧縮する装置であって、前記形状データを複数の部分形状データに分割する形状データ分割手段と、前記分割された複数の部分形状データが前記テクスチャ上でどの領域に対応するかを示す領域データを生成する領域データ生成手段と、前記部分形状データをより数の少ない複数の多角形で近似した圧縮部分形状データを生成する部分形状データ再構成手段とを備えたことを特徴とする。
【００２０】
請求項６記載の３次元モデル圧縮装置は、複数の多角形で構成された３次元的な形状データとテクスチャを含む３次元モデルを圧縮する装置であって、前記形状データを複数の部分形状データに分割する形状データ分割手段と、前記分割された複数の部分形状データが前記テクスチャ上でどの領域に対応するかを示す領域データを生成する領域データ生成手段と、前記部分形状データをより数の少ない複数の多角形で近似再構成する部分形状データ再構成手段と、テクスチャを前記領域データの領域ごとに階層化して符号化する階層符号化手段を備えたことを特徴とする。
【００２１】
請求項７記載の３次元モデル圧縮装置は、請求項５または請求項６において、形状データ分割手段は、形状データを構成する複数の多角形の頂点間距離を基準にして形状データを複数の部分形状データに分割することを特徴とする。
【００２２】
請求項８記載の３次元モデル画像生成装置は、３次元的な形状データとテクスチャを含む３次元モデルから画像を生成する装置であって、階層符号化されたテクスチャデータを入力し、復号化して複数のテクスチャと、前記複数のテクスチャの画素が有効な領域を示す複数のマスクデータを出力する復号化手段と、前記複数のテクスチャと前記複数のマスクデータと複数の形状データを入力して、前記複数のマスクデータをマスクとしたテクスチャマッピングによって画像生成処理を行うマッピング手段とを備えたことを特徴とする。
【００２３】
請求項９記載の記録媒体は、請求項１〜請求項３の何れかの３次元モデル圧縮方法、または請求項４記載の３次元モデル画像生成方法を実行するのに必要なソフトウェアが書き込まれたことを特徴とする。
【００２４】
以下、本発明の３次元モデル圧縮方法を具体的な実施の形態に基づいて説明する。
（実施の形態１）
図１は、本発明の（実施の形態１）における３次元モデル圧縮方法の処理手順の概略図である。
【００２５】
図１において、１１０は対象物の３次元的な形状をポリゴンモデルにより記述した形状データ、１１１は対象物のテクスチャであり、この２つにより対象物の３次元モデルを構成する。この（実施の形態１）では、テクスチャ１１１は対象物をある角度から撮像した画像であり、形状データ１１０はテクスチャ１１１の各画素に対応する物体表面上の３次元座標値を計測して得られた点を頂点とし、隣接する頂点を連結して得られたものであるとする。これら形状データ１１０とテクスチャ１１１は、いずれも記憶手段１０３にあらかじめ記憶されている。１００は形状データ分割手段であり、形状データ１１０を分割して複数の部分形状データ１１２ａ，１１２ｂを生成する。１０１は部分形状データ再構成手段であり、部分形状データ１１２ａ，１１２ｂ中の複数の多角形をより数の少ない多角形で近似再構成することにより、データ量の少ない圧縮部分形状データ１１３ａ，１１３ｂを生成し、記憶手段１０３に記憶する。１０２は領域データ生成手段であり、部分形状データ１１２ａ，１１２ｂの各領域が、テクスチャ１１１上でどこに対応するかを示す領域データを１１４を生成し、記憶手段１０３に記憶する。
【００２６】
以上のように構成された３次元モデル圧縮方法について、その処理動作を説明する。
図２は、形状データ１１０およびテクスチャ１１１で構成される３次元モデルの記述方法の例である。この例では、形状データ１１０は全体でｍ個の頂点を含むｎ個の三角形で構成され、ｉ番目の三角形Ｐ（ｉ）は３個の頂点（Ｖｉ１，Ｖｉ２，Ｖｉ３）で参照される点を頂点とし、ｊ番目の頂点Ｖ（ｊ）は、３次元座標値（ｘｉ，ｙｉ，ｚｉ）とテクスチャ１１１上の対応点の座標（ｕｉ，ｖｉ）で構成されること示している。また、テクスチャ１１１は、ＲＧＢ表色系画素のｗｕ×ｗｖの２次元配列であることを示している。
【００２７】
まず、この（実施の形態１）の３次元モデル圧縮方法における各手段の処理は、全てコンピュータのソフトウェアによって実現されるものであるとし、処理の起動や処理対象となる形状データ１１０およびテクスチャ１１１の指定は、ユーザーによって行われるものとする。処理が起動されると、形状データ分割手段１００は、形状データ１１０を記憶手段１０３より読み出し、複数の部分形状データ１１２ａ，１１２ｂを生成する。
【００２８】
形状データ分割手段１００での処理を、図１〜図４を用いて説明する。
図３は、形状データ分割手段での処理の図であり、図３（ａ）は図１の形状データ１１０の一部を拡大したもので、図２の形状データの例とも対応している。
【００２９】
形状データ分割手段１００は、形状データ１１０中の全ての三角形Ｐ（ｉ）について、三角形を構成する各頂点間の距離と、あらかじめ与えられたしきい値Ｔ１と比較し（図３（ａ））、しきい値より大きくなる三角形を形状データ１１０から削除する（図３（ｂ））。
【００３０】
次に、一部の三角形が削除された形状データから、三角形Ｐ（ｉ）と接する三角形が存在するか否かを走査していき、隣接する複数の三角形の集まりごとに分割することによって、図３（ｃ）の部分形状データを生成する。
【００３１】
図１の例では、この形状データの分割処理によって、２つの部分形状データ１１２ａ，１１２ｂが生成されたことを示している。
次に、領域データ生成手段１０２での処理を、図１および図４，図５を用いて説明する。
【００３２】
領域データ１１４は、ｗｕ×ｗｖ画素の２次元配列であるテクスチャ１１１のそれぞれの画素が、部分形状データ１１２ａ，１１２ｂのどちらに属するかを示す情報であることから、形状データの分割数を区別するのに必要なビット数のデータを要素としたｗｕ×ｗｖの２次元配列によって、領域データ１１４を表現することができる。この（実施の形態１）では部分形状データの数は２つであることから、要素データのビット数は１でよい。
【００３３】
図４は、形状データ分割手段１００により２つに分割された部分形状データａ（１１２ａ）および部分形状データｂ（１１２ｂ）を、図２と同様な形式で表現した例である。２つの部分形状データとテクスチャ１１１とは、部分形状データの頂点データを構成する（ｕａ，ｖａ）（ｕｂ，ｖｂ）により関連付けられている。これを図示したのが、図５の領域データ１１４の例である。
【００３４】
この（実施の形態１）では、テクスチャ１１１の各画素と形状モデル１１０の各頂点は１対１で対応しているものと仮定しているため、領域データ生成手段１０２における処理の手順は、２つの部分形状データの全ての頂点Ｖａ（ｊ），Ｖｂ（ｊ）を順に走査していき、頂点Ｖａ（ｊ）に対応する座標（ｕａｊ，ｖａｊ）の領域データに、「 領域ａ 」を意味する１ビットの値を記録し、頂点Ｖｂ（ｊ）に対応する座標（ｕｂｊ，ｖｂｊ）の領域データに、「 領域ｂ 」を意味する１ビットの値を記録するという処理を行う（図５（ｂ））。
【００３５】
最後に、部分形状データ再構成手段１０１での処理を図１および図６を用いて説明する。
部分形状データ再構成手段１０１は、部分形状データ１１２ａ，１１２ｂ中の複数の多角形をより数の少ない多角形で近似再構成することにより、データ量の少ない圧縮部分形状データ１１３ａ，１１３ｂを生成し、記憶手段１０３に記憶する処理を行う。
【００３６】
部分形状データ再構成手段での処理手順は、
・  １頂点に着目し、その隣接８頂点で囲まれた領域を近似する２つの大きな近似三角形を仮定する（ステップ１）と、
・  前記の２つの近似三角形が部分形状データ以外の頂点を含む場合、頂点の３次元座標値を新たに算出する（ステップ２）と、
・  前記の近似三角形と部分形状データとの近似誤差を、あらかじめ与えられた関数で算出して、近似誤差があらかじめ与えられたしきい値Ｔ２を超えるかどうかを判断する（ステップ３）と、
・  近似誤差がしきい値以下だった場合は、（ステップ１）で仮定した２つの大きな近似三角形で、部分形状データを再構成する（ステップ４）と
の（ステップ１）〜（ステップ４）の４つのステップを、部分形状データ内のすべての頂点に対して繰り返して行うことによって圧縮部分形状データを生成する。
【００３７】
図６を用いて上記の各ステップを説明する。頂点ｖｅに着目した場合、ｖｅに隣接する８つの頂点ｖａ，ｖｂ，ｖｃ，ｖｄ，ｖｆ，ｖｇ，ｖｈ，ｖｉで囲まれ、三角形ｐａ，ｐｂ，ｐｃ，ｐｄ，ｐｅ，ｐｆを含む領域について、より大きな２つの三角形ｐｇ，ｐｈを近似三角形として仮定する（ステップ１）。この時、近似三角形の頂点ｖｉは、もとの部分形状データには含まれていないため、近似三角形ｐｈの領域内にある部分形状データの頂点ｖｃ，ｖｅ，ｖｆ，ｖｇ，ｖｈの３次元座標値（ｘ，ｙ，ｚ）を用いて、外挿により新たにｖｉ’の３次元座標値を求める（ステップ２）。次に、近似三角形ｐｇ，ｐｈと部分形状データ中の三角形ｐａ〜ｐｆとの近似誤差を求めてしきい値Ｔ２との比較を行う。ここでは、近似誤差は部分形状データに含まれる各頂点ｖａ，ｖｂ，ｖｃ，ｖｄ，ｖｅ，ｖｆ，ｖｇ，ｖｈと近似三角形ｐｇ，ｐｈとの距離を用い、評価として、各近似誤差が全てしきい値Ｔ２以下であることとする（ステップ３）。前記のステップ３における近似誤差が、１つでもしきい値を超えた場合は近似再構成処理を行わず、逆に全てしきい値以下だった場合、部分形状モデル中の三角形ｐａ，ｐｂ，ｐｃ，ｐｄ，ｐｅ，ｐｆをｐｇ，ｐｈに置換えることにより、部分形状モデルの近似再構成を行う（ステップ４）。
【００３８】
ここで、前述した（ステップ４）において、もし近似再構成処理を行った場合は、三角形数で２／６、頂点数で５／８と、多くの部分形状データのデータ量を削減できることがわかる。
【００３９】
さらに上記の４つのステップを部分形状データの全ての頂点に対して行うことにより、圧縮部分形状データ１１３ａ，１１３ｂを生成し、記憶手段１０３に記憶する。
【００４０】
図７は、この（実施の形態１）の３次元モデル圧縮方法によって生成され、記憶手段１０３に記憶される圧縮された３次元モデルの例である。図２の入力となった３次元モデルと比較すると、テクスチャ１１１はそのままで、形状データは１１０が、領域データ１１４と、圧縮部分形状データ１１３ａ，１１３ｂに置き換わっているのがわかる。
【００４１】
これまで示してきたように、（実施の形態１）の３次元モデル圧縮方法によると、形状モデル１１０のデータ量に対して、圧縮部分形状データ１１３ａ，１１３ｂのデータ量を少なくすることが可能であり、特に、形状データ再構成手段１０１の処理によって、データ量を大幅に削減することが可能である。
【００４２】
また、領域データ１１４については新たに追加されることになるが、この（実施の形態１）では、領域データが１画素につき１ビットであるのに対し、形状データの１つ頂点データは多くの場合数十ビット以上ある事から、数十頂点に１つの頂点を削減することによって、領域データの追加によるデータ量増を相殺することができる。
【００４３】
以上のことから、（実施の形態１）の３次元モデル圧縮方法は、よりデータ量の少ない３次元モデルの生成が可能であると言える。
さらに、領域データ１１４の効果を明らかにするために、この（実施の形態１）における３次元モデル圧縮方法によって生成された３次元モデルを用いて、画像生成を行った場合について説明する。
【００４４】
図８は、この（実施の形態１）における３次元モデル圧縮方法によって新たに生成された３次元モデルを用いて、３次元コンピュータグラフィックによる画像生成を行う方法の処理手順の概略図である。
【００４５】
マスクデータ生成手段１０４は、記憶手段１０３より領域データ１１４を読み出して、マスクデータａ，ｂ（１１５ａ，１１５ｂ）を生成する。このマスクデータは、テクスチャ１１１と同じｗｕ×ｗｖの２次元配列であり、マスクデータａ（１１５ａ）は部分形状データ領域ａに対応する領域が”１”でそれ以外の部分が”０”、マスクデータｂ（１１５ｂ）は部分形状データ領域ｂに対応する領域が”１”でそれ以外の部分が”０”であるものとする。
【００４６】
テクスチャマッピング手段１０５は、テクスチャ１１１，マスクデータａ（１１５ａ），圧縮部分形状データ１１３ａの組と、テクスチャ１１１，マスクデータｂ（１１５ｂ），圧縮部分形状データ１１３ｂの組との、２組のデータを用いて合成画像１１６を生成する。この時、それぞれマスクデータが”１”の画素のテクスチャだけを画像としてマッピングするテクスチャマッピング（アルファ付きテクスチャマッピング）によってレンダリングを行い、合成画像１１６を生成する。このようにして得られた合成画像１１６は、領域データ１１４の形状、すなわち、部分形状データ１１２の端面の形状と、圧縮部分形状データ１１３の３次元的な形状との、２つの形状を反映したものとなっている。
【００４７】
アルファ付きテクスチャマッピングの技術は、「Ｄａｖｉｄ  Ｆ．  Ｒｏｇｅｒｓ  著：”実践コンピュータグラフィックス”（英題”Ｐｒｏｃｅｄｕｒａｌ  ｅｌｅｍｅｎｔｓ  ｆｏｒ  ｃｏｍｐｕｔｅｒ  ｇｒａｐｈｉｃｓ”）、山口富士夫監修、日刊工業新聞社出版  」などでも開示されている、３次元コンピュータグラフィックスの一般的な技術として一般的に広く知られた技術であり、ここでは詳細な説明は省略する。
【００４８】
ここで、この（実施の形態１）の３次元モデル圧縮方法における処理過程において、形状データの削減は、主に部分形状データ再構成手段の処理によって行われるため、形状データの削減による生成画像の劣化は、ほとんど部分形状データ再構成手段による処理で発生すると考えることができる。
【００４９】
一方、領域データは、部分形状データ再構成手段での近似再構成処理を行う前、すなわち形状データ削減による生成画像の劣化が起こる前の、部分形状データの端面の形状を保持している。特に領域データは、テクスチャ１画素に相当する形状を、この（実施の形態１）では１ビットで表現できたように、形状データに比べて非常に少ないデータ量で、詳細な形状を表現できることから、画像の劣化が目立ち易い輪郭部分の形状を記述するのに適していると言える。
【００５０】
したがって、もし画像生成時の輪郭部になる可能性が高い部分を、部分形状データの端面に一致することができれば、領域データによって輪郭部の詳細な形状を少ないデータ量で記述することができ、結果として、形状データの削減による画像の劣化を少ないデータ量に低減することが可能になる。
【００５１】
部分形状データの端面に相当する部分が画像生成時の輪郭部になる可能性が高い場合の例としては、図１の例のような、３次元計測で計測された複数の物体（人形と背景）を含む形状データや、鋭角的なエッジを持つ形状データなどがある。このような形状データは、この（実施の形態１）の形状データ分割手段での、三角形の頂点間距離がしきい値より大きい場合に分離する処理（図３（ａ）（ｂ））によって、複数物体の境界部分や、鋭角的なエッジの部分を端面とした部分形状データに分割される可能性が高い。さらに、物体の境界や鋭角的なエッジは、画像形成時の視点などの条件が変化した場合でも、画像生成時の輪郭となる可能性が一般的に高いと言える。以上のことから、特に前述した形状の場合、この（実施の形態１）による３次元モデル圧縮方法は、画像生成時の輪郭となる部分の劣化が少なく、かつデータ量の少ない３次元モデルを圧縮生成する方法であると言える。
【００５２】
以上のように（実施の形態１）によれば、前記形状データを複数の部分形状データに分割する形状データ分割手段１００と、前記分割された複数の部分形状データが前記テクスチャ上でどの領域に対応するかを示す領域データを生成する領域データ生成手段１０２と、前記部分形状データをより数の少ない複数の多角形で近似再構成する部分形状データ再構成手段１０１を備えたことにより、より少ないデータ量で、かつ画質の劣化が少ない３次元モデル生成することができ、特に、端面が開いた形状データなどに効率の良く３次元モデルを圧縮することができる。
【００５３】
なお、図１の処理はソフトウエアプログラムをコンピュータで実行することによって実現される。前記ソフトウエアプログラムには、形状データを複数の部分形状データに分割する形状データ分割過程と、分割された複数の部分形状データがテクスチャ上でどの領域に対応するかを示す領域データを生成する領域データ生成過程と、部分形状データをより数の少ない複数の多角形で近似再構成する部分形状データ再構成過程などが記述されており、前記コンピュータが形状データ分割過程を実行することによって形状データ分割手段１００が実現され、前記コンピュータが領域データ生成過程を実行することによって領域データ生成手段１０２が実現され、前記コンピュータが部分形状データ再構成過程を実行することによって部分形状データ再構成手段１０１が実現される。
【００５４】
同様に、図８の処理もソフトウエアプログラムをコンピュータで実行することによって実現され、ソフトウエアプログラムの各処理の過程を実行することによってマスクデータ生成手段１０４，テクスチャマッピング手段１０５が実現される。
【００５５】
このような図１または図８の処理のソフトウエアプログラムは、記録媒体に書き込んで市場に流通させることもできる。これは以下の実施の形態においても同様である。
【００５６】
（実施の形態２）
図９は、本発明の（実施の形態２）における３次元モデル圧縮方法の処理手順の概略図である。
【００５７】
図１と異なるのは、階層符号化手段１０６を設けたことと、階層符号化手段によって、テクスチャ１１１と領域データ１１４を符号化して記憶手段１０３に記憶する点であり、他の構成および各処理手段での処理は、本発明の（実施の形態１）と同様な処理を行う。
【００５８】
階層符号化手段１０６での処理は、テクスチャ１１１と領域データ１１４を入力とし、テクスチャ１１１を領域データ１１４に対応した２つの領域に分割階層化し、それぞれの領域内の画像にのみ着目して符号化を行うことによって、データ量の少ない圧縮テクスチャ１１７を生成して、記憶手段１０３に記憶する。
【００５９】
このような画像を階層符号化・復号化する方式や、それを実現する装置の詳細な構成については、特開平８−１１６５４３号や、栄藤らの研究報告「栄藤  稔他：”ＭＰＥＧ−４システム”、映像情報メディア学会誌、Ｖｏｌ．５１，Ｎｏ．１２，  ｐｐ．１９６６−１９７３，  １９９７」などで開示されている技術であるため、ここでは詳細な処理手順の説明は省略する。
【００６０】
上記した本発明の（実施の形態２）では、テクスチャと３次元形状データから生成した領域データという全く性質の異なるデータを組み合わせて階層符号化により圧縮することにより、それぞれ個別に圧縮した場合よりデータ量が少ない圧縮方法を実現していることから、新規性と有効性の高い方法であるといえる。
【００６１】
また、階層符号化の技術は、異なる対象物が１つの画像に写っている場合などに、それぞれを分離階層化して符号化することによって、符号化効率を上げる事が可能な技術として近年注目されているが、画像だけを用いて画像中の複数の対象物を自動で分離することは困難であり、従来は手作業で画像を分離するなどの処理が行われていた。これに対し、本発明の（実施の形態２）では、対象物の画像（テクスチャ）の以外に、３次元的な形状データを有しており、これを用いて領域データを生成することによって、画像の自動階層化を実現している点でも、新規性と有効性が高い方法である。
【００６２】
以上のように、この（実施の形態２）によれば、テクスチャと領域データを符号化する階層符号化手段を設けることにより、本発明の（実施の形態１）より、よりデータ量の少ない３次元モデルを生成することが可能である。
【００６３】
（実施の形態３）
図１０は、本発明の（実施の形態３）における３次元モデル画像生成方法の処理手順の概略図である。
【００６４】
図８と異なるのは、マスクデータ生成手段１０４の代わりに、復号化手段１０７を設けたことと、テクスチャデータ１１１ａ，１１１ｂおよびマスクデータ１１５ａ，１１５ｂは、復号化手段１０７によって、あらかじめ階層符号化された圧縮テクスチャ１１７を復号化して生成される点である。テクスチャマッピング手段１０５での処理は、図８の画像生成方法と同様な処理を行う。
【００６５】
復号化手段１０７での処理は、記憶手段１０３にあらかじめ階層符号化して記憶された圧縮テクスチャ１１７を入力として復号化処理を行う。ここで、階層符号化されたデータには、符号化の対象となる画像の領域を示す情報が含まれていることから、この領域情報をマスクデータ１１５として生成出力するとともに、画像であるテクスチャ１１１を復号化して出力する。
【００６６】
以上のように、この（実施の形態３）によれば、テクスチャを圧縮する方法として階層符号化を用いることによって、単純にテクスチャ圧縮の効果を得るだけでなく、階層符号化時に含まれる画像の領域情報をテクスチャマッピング時のマスク情報として用いることによって、本発明の（実施の形態１）（実施の形態２）の効果と同様に、データ量の少ない粗い形状モデルを用いて画像生成を行った場合でも、マスク情報に含まれる形状情報も含めた画像を生成できることから、少ないデータ量でより画像の劣化の少ない画像生成が可能となるという効果がある。
【００６７】
【発明の効果】
以上のように本発明は、複数の多角形で構成された３次元的な形状データとテクスチャを含む３次元モデルを圧縮する方法として、形状データを複数の部分形状データに分離した場合の端面の形状と、部分形状データを近似した粗い形状の、２種類の形状に分けて記述することによって、より少ないデータ量で、かつ画質の劣化が少ない３次元モデルを生成することが可能となるものである。
【図面の簡単な説明】
【図１】本発明の（実施の形態１）における３次元モデル圧縮方法の処理手順の概略図
【図２】同実施の形態における形状データおよびテクスチャの一例を示す図
【図３】同実施の形態における形状データ分割手段での処理手順の説明図
【図４】同実施の形態における部分形状データ及びテクスチャの一例を示す図
【図５】同実施の形態における領域データ生成手段での処理手順の説明図
【図６】同実施の形態における部分形状データ再構成手段での処理手順の説明図
【図７】同実施の形態における圧縮方法で生成された３次元モデルの一例を示す図
【図８】同実施の形態における圧縮方法で圧縮された３次元モデルを用いた画像生成の処理手順の概略図
【図９】本発明の（実施の形態２）における３次元モデル圧縮方法の処理手順の概略図
【図１０】本発明の（実施の形態３）における３次元モデル画像生成方法の処理手順の概略図
【符号の説明】
１００    形状データ分割手段
１０１    部分形状データ再構成手段
１０２    領域データ生成手段
１０３    記憶手段
１１０    形状データ
１１１    テクスチャ
１１２    部分形状データ
１１３    圧縮部分形状データ
１１４    領域データ
【図１】
0003618234.tif 000002
【図２】
0003618234.tif 000003
【図３】
0003618234.tif 000004
【図４】
0003618234.tif 000005
【図５】
0003618234.tif 000006
【図６】
0003618234.tif 000007
【図７】
0003618234.tif 000008
【図８】
0003618234.tif 000009
【図９】
0003618234.tif 000010
【図１０】
0003618234.tif 000011