(57)【特許請求の範囲】
【請求項１】
辺によって接続された複数の頂点によって形成された複数のポリゴンを含む初期三次元（３Ｄ）グラフィックス画像のポリゴンリダクションを最適化するコンピュータ実施方法であって、
前記初期３Ｄグラフィックス画像から第１のセットの頂点及び辺を除去し、前記第１のセットの頂点及び辺を除去した結果として、前記初期３Ｄグラフィックス画像より少ないポリゴンを含む第１の３Ｄグラフィックス画像を生成すること、
前記初期３Ｄグラフィックス画像を複数の部分にセグメント化すること、
前記初期３Ｄグラフィックス画像の前記複数の部分のそれぞれを、前記第１の３Ｄグラフィックス画像の対応する部分と比較すること、
前記比較に基づいて、前記初期３Ｄグラフィックス画像の前記複数の部分と、前記第１の３Ｄグラフィックス画像の前記対応する部分との差を特定すること、
前記初期３Ｄグラフィックス画像の前記複数の部分のうち第１の部分と、前記第１の３Ｄグラフィックス画像の前記対応する部分からの第２の部分との差に基づいて、前記第１の３Ｄグラフィックス画像の前記第２の部分から第２のセットの頂点及び辺を除去すること、
前記初期３Ｄグラフィックス画像の前記複数の部分のうち第３の部分と、前記第１の３Ｄグラフィックス画像の前記対応する部分からの第４の部分との差に基づいて、前記第１の３Ｄグラフィックス画像の前記第４の部分から第３のセットの頂点及び辺を除去することを備え、
前記第４の部分から除去される頂点及び辺の量は、前記第２の部分から除去される頂点及び辺の量より大きい、方法。
【請求項２】
前記第１の３Ｄグラフィックス画像の前記第２の部分から前記第２のセットの頂点及び辺を除去することは、前記初期３Ｄグラフィックス画像から前記第１のセットの頂点及び辺を除去することと比較してより低いレベルのポリゴンリダクションを導入する、請求項１に記載の方法。
【請求項３】
前記第１の３Ｄグラフィックス画像の前記第２の部分から前記第２のセットの頂点及び辺を除去することは、前記初期３Ｄグラフィックス画像から前記第１のセットの頂点及び辺を除去することと比較してより高いレベルのポリゴンリダクションを導入する、請求項１に記載の方法。
【請求項４】
前記第１の３Ｄグラフィックス画像の前記第２の部分から前記第２のセットの頂点及び辺を除去することは、複数の所定のポリゴンリダクションプロセスのうち１つに基づく、請求項２に記載の方法。
【請求項５】
前記第１の３Ｄグラフィックス画像の前記第２の部分から前記第２のセットの頂点及び辺を除去することは、複数のポリゴンリダクションプロセスから選択される、請求項３に記載の方法。
【請求項６】
前記初期３Ｄグラフィックス画像から前記第１のセットの頂点及び辺を除去することは、ポリゴンの割当量にしたがって実行され、
前記方法は、前記ポリゴンの割当量を前記複数の部分に再分配することを更に備える、請求項１に記載の方法。
【請求項７】
前記再分配することは、誤差範囲に基づいて前記ポリゴンの割当量を再配分することを含む、請求項６に記載の方法。
【請求項８】
前記初期３Ｄグラフィックス画像の前記複数の部分のうち第４の部分と、前記第１の３Ｄグラフィックス画像の前記対応する部分からの第５の部分との差に基づいて、前記第１の３Ｄグラフィックス画像の前記第５の部分から頂点及び辺を除去しないと特定することを更に備える、請求項１に記載の方法。
【請求項９】
辺によって接続された複数の頂点によって形成された複数のポリゴンを含む初期三次元（３Ｄ）グラフィックス画像のポリゴンリダクションを最適化する画像処理装置であって、
前記初期３Ｄグラフィックス画像を複数の部分にセグメント化し、
前記初期３Ｄグラフィックス画像から第１のセットの頂点及び辺を除去し、前記初期３Ｄグラフィックス画像より少ないポリゴンを含む第１の３Ｄグラフィックス画像を生成し、
前記初期３Ｄグラフィックス画像の前記複数の部分のそれぞれを、前記第１の３Ｄグラフィックス画像の対応する部分と比較し、
前記比較に基づいて、前記初期３Ｄグラフィックス画像の前記複数の部分と、前記第１の３Ｄグラフィックス画像の前記対応する部分との差を特定し、
前記初期３Ｄグラフィックス画像の前記複数の部分のうち第１の部分と、前記第１の３Ｄグラフィックス画像の前記対応する部分からの第２の部分との差に基づいて、前記第１の３Ｄグラフィックス画像の前記第２の部分から第２のセットの頂点及び辺を除去し、
前記初期３Ｄグラフィックス画像の前記複数の部分のうち第３の部分と、前記第１の３Ｄグラフィックス画像の前記対応する部分からの第４の部分との差に基づいて、前記第１の３Ｄグラフィックス画像の前記第４の部分から第３のセットの頂点及び辺を除去する
ように構成されたプロセッサを備え、
前記第４の部分から除去される頂点及び辺の量は、前記第２の部分から除去される頂点及び辺の量より大きい、画像処理装置。
【請求項１０】
前記初期３Ｄグラフィックス画像又は前記第１の３Ｄグラフィックス画像のうちの少なくとも１つを表示するように構成されたディスプレイを更に備える、請求項９に記載の画像処理装置。
【請求項１１】
前記第１の３Ｄグラフィックス画像の前記第２の部分から前記第２のセットの頂点及び辺を除去することは、前記初期３Ｄグラフィックス画像から前記第１のセットの頂点及び辺を除去することと比較してより低いレベルのポリゴンリダクションを導入する、請求項９に記載の画像処理装置。
【請求項１２】
前記第１の３Ｄグラフィックス画像の前記第２の部分から前記第２のセットの頂点及び辺を除去することは、前記初期３Ｄグラフィックス画像から前記第１のセットの頂点及び辺を除去することと比較してより高いレベルのポリゴンリダクションを導入する、請求項９に記載の画像処理装置。
【請求項１３】
前記プロセッサは、前記初期３Ｄグラフィックス画像の前記複数の部分のうち第４の部分と、前記第１の３Ｄグラフィックス画像の前記対応する部分からの第５の部分との差に基づいて、前記第１の３Ｄグラフィックス画像の前記第５の部分から頂点及び辺を除去しないと特定することを実行するように更に構成される、請求項９に記載の画像処理装置。
【請求項１４】
請求項１乃至８のうちいずれか１項に記載の方法をコンピュータに実行させるコンピュータプログラム。
【請求項１５】
請求項１４に記載のコンピュータプログラムを記憶したコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概してコンピュータグラフィックスに関し、より詳細には、三次元グラフィックス画像のポリゴンリダクション（polygon reduction）を最適化するコンピュータ実施方法に関する。本発明は、対応する画像処理装置及びコンピュータプログラム製品にも関する。
【背景技術】
【０００２】
人工コンピュータグラフィックス（ＣＧ：ｃｏｍｐｕｔｅｒ  ｇｒａｐｈｉｃｓ）環境の作成及びインタラクティブ視覚化は、コンピュータグラフィックスの分野での重要な用途である。ＣＡＤ、アーキテクチャー・ウォークスルー（architectural walkthrough）、シミュレーション、医療視覚化、及びコンピュータゲーム等の多くの用途は、インタラクティブナビゲーションを含み、すなわち、毎秒１０フレームを超えるレートでコンピュータモデル／画面の至る所を移動することが可能である。
【０００３】
インタラクティブコンピュータグラフィックスの分野内の共通の傾向は、ＣＧデータセット量の増大である。大きなＣＧデータセットは、プロセスを早めるのに使用される特別なグラフィックスシステムを必要とする。しかし、現在のハイエンドコンピュータハードウェアを用いる場合であっても、インタラクティブ速度でレンダリングすることができないモデルが存在する。ＣＧデータのサイズ及びセカンダリコンピュータメモリのサイズは、それに関連するハードウェアの発展よりも速い速度で増大しているため、コンピュータハードウェアの発展が、説明した課題を解決する可能性は低い。
【０００４】
ＣＧデータは多くの場合、三角形メッシュ、又は更により一般的には複数のポリゴンを使用して表現される。これらのメッシュは通常、表示又はシミュレーション性能に向けて最適化されない。大半の用途では、初期メッシュは通常、最適化されたもので置換することができ、最適化されたものは、はるかに少ない数の面を有する近似である得るか、又は上述したような特定の用途により合うようにする他の特性を含み得る。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
計算速度の低下を回避するために、多くの場合、少数の三角形／ポリゴンを有する三次元ＣＧデータを事前に作成する自動技法が利用される。しかし、ポリゴンリダクションに自動化プロセスを利用するに当たり、望ましくない視覚誤差が生じることがある。一般に、特定のＣＧデータセットを担当するグラフィカルデザイナーが次に、視覚的に魅力的であるが、それでもなおポリゴンが低減されたＣＧデータセットを達成するのに適する調整を手作業で行わなければならない。したがって、ポリゴンリダクションプロセスの更なる自動化のために、コストを低減し、可能な場合にはより最適化されたポリゴン低減ＣＧデータセットを達成可能なことが望ましい。
【課題を解決するための手段】
【０００６】
本発明の第１の態様によれば、上記は少なくとも部分的に、初期三次元グラフィックス画像のポリゴンリダクションを最適化するコンピュータ実施方法によって軽減され、本方法は、第１のポリゴンリダクションプロセスを実行することであって、その結果、初期三次元グラフィックス画像のポリゴン低減表現である第１の三次元グラフィックス画像が生成される、第１のポリゴンリダクションプロセスを実行することと、第１の三次元グラフィックス画像を初期三次元グラフィックス画像と比較することと、第１の三次元グラフィックス画像と初期三次元グラフィックス画像との比較の結果に基づいて、視覚誤差メトリックを特定することと、視覚誤差メトリックが所定の誤差範囲外である場合、第２のポリゴンリダクションプロセスを実行することであって、その結果、初期三次元グラフィックスオブジェクトのポリゴン低減表現である第２の三次元グラフィックス画像が生成される、第２のポリゴンリダクションプロセスを実行することとを含む。
【０００７】
本発明により、ポリゴンリダクションプロセスを実行する際に出現する視覚誤差の識別を自動化することが可能であり、したがって、例えば、結果として生成される視覚的に魅力的なポリゴン低減画像を達成するために必要な手作業労働量を最小化することにより、コストを低減するという利点が生じる。これは、「原」画像と初期ポリゴンリダクションプロセスから生成される画像との差を特定することによって達成される本発明によるものである。比較／特定の結果である視覚誤差メトリックが、所定の誤差範囲を超える（又は下回る）場合、結果として生成される画像（例えば、コンピュータ画面に表示される）が所望の「品質レベル」によりよく一致するように、ポリゴンリダクションを再び繰り返すために、ポリゴンリダクションプロセスに調整が行われる（すなわち、第２のポリゴンリダクションプロセス）。
【０００８】
本発明との関連において、視覚誤差メトリックが、三次元画像の単一の「ビュー」及び複数の異なる「ビュー」に基づき得ることを理解されたい。三次元画像の複数のビューを用いる場合、複数のビューは、例えば、ビューから独立した単一の視覚誤差メトリックに統合若しくは蓄積してもよく、又は三次元画像の複数のビューのそれぞれ（又は少なくとも一部）に、ビュー依存の別個の視覚誤差メトリックを用いて表してもよい。
【０００９】
誤差範囲は、例えば、結果として生成される画像の所望の視覚的外観に基づき得、且つ／又は所定のポリゴンリダクション比率（すなわち、ポリゴン数に関連して初期画像を結果として生成される画像と比較する場合）若しくは結果として生成される画像の「ポリゴンの割当量」と組み合わせ得る。
【００１０】
一般に、初期、第１、及び第２の三次元グラフィックス画像は、３Ｄコンピュータグラフィックス画像を形成する複数のポリゴンを含むポリゴン画像である。上述したように、三次元コンピュータグラフィックスは、例えば、リアルタイム視覚化、コンピュータゲーム、ＣＡＤ関連ソフトウェア等に関連して使用され得る。
【００１１】
さらに、本発明に伴う例示的な利点は、原画像及び／又はポリゴン低減画像内の「問題エリア」をピンポイント可能なことに関する。そのような利点は、あまり厳密ではなく高速の視覚誤差メトリックの導入可能性を提供し、それにより、より高速の反復初期結果が与えられ、これは次に、選択された（すなわち、第２の）ポリゴンリダクションプロセスの完全版に複数回通されることによって更に改良される。
【００１２】
好ましい実施形態では、第２のポリゴンリダクションプロセスは、第１のポリゴンリダクションプロセスと比較してより低いレベルのポリゴンリダクションを導入する。したがって、視覚誤差メトリックが所定の誤差範囲を超える場合、第２のポリゴンリダクションプロセスが選択され、第１のポリゴンリダクションプロセスを使用して最初に達成されたほど「ハード」にはポリゴン数を低減しない。
【００１３】
しかし、代替として、第２のポリゴンリダクションプロセスは代わりに、第１のポリゴンリダクションプロセスと比較してより高いレベルのポリゴンリダクションを導入し得る。したがって、逆に、所定の視覚誤差メトリックが、望ましい（又は期待される）値よりも低いと識別される場合、より高いレベルのポリゴンリダクション（すなわち、第１の画像と比較して、第２の画像に関してポリゴンの数が少なくなる）を達成するように構成される第２のポリゴンリダクションプロセスを選択することが可能であり得る。
【００１４】
上記に基づいて、本発明による方法を１回だけ実行してもよく、又は複数回繰り返してもよいことを理解されたい（しかし、必ずしもそうである必要はない）。例えば、第２の画像と初期画像結果との比較により、誤差範囲外の視覚誤差メトリックが生じる場合、結果として生成される画像を提供するポリゴンリダクションプロセスの選択／構成に関して、更なる調整を行い得る。
【００１５】
好ましくは、第２のポリゴンリダクションプロセスは、複数の所定のポリゴンリダクションプロセスから選択される。いずれの場合でも、「ポリゴンリダクションプロセス」という表現は、広義に解釈されるべきであり、例えば、完全に異なるタイプのポリゴンリダクションプロセスを適用し得るとともに、特定（例えば、プロプライエタリ）のポリゴンリダクションプロセスを、ポリゴンリダクションのレベルに関して構成することが可能である。
【００１６】
好ましい実施形態では、本方法は、三次元グラフィックス画像を複数の部分にセグメント化することを更に含み、視覚誤差メトリックの特定は、三次元グラフィックス画像の複数の部分のそれぞれ（及び場合によっては画像の複数の異なるビュー）に対して実行される。そのような一実施形態では、例えば、初期、第１、及び第２の三次元グラフィックス画像のうちの１つである三次元グラフィックス画像は、複数のサブセクションに細分され、視覚誤差メトリックは各サブセクションで特定される。それにより、ポリゴンリダクションプロセスの選択は、その特定の部分の誤差の「深刻度」に基づいて適宜行うことができ、例えば、異なる「タイプ」（又は構成）のポリゴンリダクションプロセスを、画像の２つの隣接して配置される部分に選択し得る。任意の数の部分をグラフィックス画像から選択し得る。本発明によれば、追加（又は代替）として、セグメントは「クラスタ化技法」に基づいて形成し得、その場合、「誤差エリア」が隣接誤差に基づいて形成される。
【００１７】
本発明の可能な実施形態では、視覚誤差メトリックをユーザに提供し、（次に）ユーザ調整視覚誤差メトリックを受信することも更に可能であり得、視覚誤差メトリックを提供すること及びユーザ調整視覚誤差メトリックを受信することは、第２のポリゴンリダクションプロセスを実行する前に実行される。したがって、そのような追加により、例えば、第２の（調整）ポリゴンリダクションプロセスを実行する前に、例えば、ポリゴン最適化プロセスを実行するユーザに視覚誤差メトリックを視覚化することが可能であり得る。そのような視覚化により、ユーザは、例えば、視覚誤差メトリックに手作業で調整を行うことができ、したがって、三次元画像の特定の特徴のユーザの事前知識（例えば、ゲーム内の将来の配置又はより大きな誤差を許容可能なエリア）を使用可能なことを提供し、それにより、ポリゴンリダクションプロセスを更に最適化する。
【００１８】
本発明の別の態様によれば、三次元グラフィックスオブジェクトのポリゴンリダクションを最適化する画像処理装置が提供され、本装置は、第１のポリゴンリダクションプロセスを実行する手段であって、その結果、初期三次元グラフィックス画像のポリゴン低減表現である第１の三次元グラフィックス画像が生成される、第１のポリゴンリダクションプロセスを実行する手段と、第１の三次元グラフィックス画像を初期三次元グラフィックス画像と比較する手段と、第１の三次元グラフィックス画像と初期三次元グラフィックス画像との比較の結果に基づいて、視覚誤差メトリックを特定する手段と、視覚誤差メトリックが所定の誤差範囲外である場合、第２のポリゴンリダクションプロセスを実行する手段であって、その結果、初期三次元グラフィックスオブジェクトのポリゴン低減表現である第２の三次元グラフィックス画像が生成される、第２のポリゴンリダクションプロセスを実行する手段とを備える。本発明のこの態様は、上述した利点と同様の利点を提供する。
【００１９】
一実施形態では、画像処理装置は、コンピュータ画面への初期、第１、及び第２の三次元グラフィックス画像のうちの少なくとも１つの表示を可能にするように更に構成される。
【００２０】
本発明は、好ましくは、上述した画像処理方法をコンピュータに実行させるプログラムを記憶するコンピュータ可読記憶媒体で提供される。
本発明の更なる態様によれば、三次元グラフィックスオブジェクトのポリゴンリダクションを最適化するように構成される画像処理装置を制御するコンピュータプログラム手段を記憶したコンピュータ可読媒体を備えるコンピュータプログラム製品が提供され、本コンピュータプログラム製品は、第１のポリゴンリダクションプロセスを実行するコードであって、その結果、初期三次元グラフィックス画像のポリゴン低減表現である第１の三次元グラフィックス画像が生成される、第１のポリゴンリダクションプロセスを実行するコードと、第１の三次元グラフィックス画像を初期三次元グラフィックス画像と比較するコードと、第１の三次元グラフィックス画像と初期三次元グラフィックス画像との比較の結果に基づいて、視覚誤差メトリックを特定するコードと、視覚誤差メトリックが所定の誤差範囲外である場合、第２のポリゴンリダクションプロセスを実行するコードであって、その結果、初期三次元グラフィックスオブジェクトのポリゴン低減表現である第２の三次元グラフィックス画像が生成される、第２のポリゴンリダクションプロセスを実行するコードとを含む。本発明のこの態様も、本発明の前の態様に関連して上述した利点と同様の利点を提供する。
【００２１】
画像処理装置は、好ましくは、サーバ、汎用コンピュータ、マイクロプロセッサ、又は任意の他のタイプの計算装置である。同様に、コンピュータ可読媒体は、リムーバブル不揮発性ランダムアクセスメモリ、ハードディスクドライブ、フロッピー（登録商標）ディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、ＵＳＢメモリ、ＳＤメモリカード、又は当分野で既知の同様のコンピュータ可読媒体のうちの１つを含む任意のタイプのメモリ装置であり得る。
【００２２】
一実施形態では、上述した様式と同様に、コンピュータプログラム製品は、コンピュータ画面への初期、第１、又は第２の三次元グラフィックス画像のうちの少なくとも１つの表示を可能にするように更に構成される。
【００２３】
本発明の更なる特徴及び利点は、添付の特許請求の範囲及び以下の説明を研究すると明らかになろう。本発明の範囲から逸脱せずに、本発明の異なる特徴を組み合わせて、以下に記載される実施形態以外の実施形態を作成し得ることを当業者は認識する。
【００２４】
本発明の様々な態様は、その特定の特徴及び利点を含め、以下の詳細な説明及び添付図面から容易に理解されよう。
【図面の簡単な説明】
【００２５】
【図１ａ】元の三次元グラフィックス画像及びポリゴン低減三次元グラフィックス画像の一例を示す。
【図１ｂ】元の三次元グラフィックス画像及びポリゴン低減三次元グラフィックス画像の一例を示す。
【図２】本発明の現在好ましい実施形態による概念的な画像処理システムを示す。
【図３】本発明の一実施形態による方法ステップのフローチャートを示す。
【図４】本発明による方法の異なるプロセスでの三次元グラフィックス画像を示す。
【発明を実施するための形態】
【００２６】
これより、本発明について、本発明の現在好ましい実施形態が示される添付図面を参照して以下により完全に説明する。しかし、本発明は、多くの異なる形態で実施し得、本明細書に記載される実施形態に限定されるものとして解釈されるべきではなく、むしろ、これらの実施形態は、完璧さ及び完全さのために提供されており、本発明の範囲を当業者に十分に伝達するものである。全体を通して、同様の参照符号は同様の要素を指す。
【００２７】
三次元グラフィックスアクセラレータ（three-dimensional graphics accelerator）を有するシステムでは、アプリケーションプログラムは、三次元グラフィックス画像の表面上の点に対応する情報を含む三次元ジオメトリデータを生成する。これらの点はポリゴンの頂点として使用可能であり、結ばれた場合、グラフィックス画像の表面を形成するようにレンダリングされる。通常、アプリケーションプログラムは、三次元ジオメトリデータをグラフィックスアクセラレータに転送し、符号化されたポリゴンを、例えばコンピュータ画面上にレンダリングする。
【００２８】
三次元頂点を結んで、グラフィックス画像の表現を形成するプロセスは、ポリゴンメッシュ（polygon mesh）の作成と呼ばれることがある。図１ａ及び図１ｂは、そのようなポリゴンメッシュにタイル化された（tiled）、「うさぎ」の形態の例示的な三次元グラフィックス画像の２つの異なるバージョンを示す。うさぎの第１のバージョン１０２は多数の複数のポリゴンによって表現され、一方、うさぎの第２のバージョン１０４は、うさぎの第１のバージョン１０２と比較してより少数のポリゴンによって表現される。ポリゴンリダクションプロセスは通常、メッシュモデル１０２を構成する頂点及び辺を除去することによって行われ、異なるレベルのポリゴンリダクションを、所定の所望比率（すなわち、低減画像と比べた原画像）に基づいて、ピクセルベースで、又は特定の画像（又はオブジェクト）のポリゴンの数（polygon budget）に基づいて選択し得る。
【００２９】
上述したように、本発明は、一般的には、特に原画像と、原画像のポリゴン低減表現との差に基づいて生成される視覚誤差メトリック（visual error metric）を考慮に入れて、初期三次元グラフィックス画像（initial three-dimensional graphics image）のポリゴンリダクションを最適化するコンピュータ実施方法に関する。したがって、原画像は、うさぎの第１のバージョン１０２に対応することができ、一方、ポリゴン低減表現は、うさぎの第２のバージョン１０４に対応することができる。
【００３０】
本発明の一般概念は通常、汎用プロセッサ（例えば、ユーザ制御のパーソナルコンピュータ）と、専用プロセッサと、処理構成要素を含む回路と、分散処理構成要素群と、処理するように構成された分散コンピュータ群等とを含む画像処理装置で実施し得る。プロセッサは、データ若しくは信号の処理を行うため、又はメモリに記憶されたコンピュータコードを実行するための任意の数のハードウェア構成要素であり得るか、又はそのような任意の数のハードウェア構成要素を含み得る。メモリは、本説明に記載される様々な方法を完了するか、又は促進するためのデータ及び／又はコンピュータコードを記憶する１つ又は複数の装置であり得る。メモリは、揮発性メモリ又は不揮発性メモリを含み得る。メモリは、データベース構成要素、オブジェクトコード構成要素、スクリプト構成要素、又は本説明の様々なアクティビティをサポートする任意の他のタイプの情報構造を含み得る。例示的な一実施形態によれば、任意の分散又はローカルメモリ装置を、本説明のシステム及び方法と共に利用し得る。例示的な一実施形態によれば、メモリは、プロセッサに通信可能に接続され（例えば、回路、又は任意の他の有線、無線、若しくはネットワーク接続を介して）、本明細書に記載の１つ又は複数のプロセスを実行するコンピュータコードを含む。
【００３１】
しかし、図２に提供される概念図に示されるように、本発明による画像処理装置の一般的な機能は、追加及び／又は代替として、例えば、画像処理システム２００によって分散環境で提供し得る。そのような一実施形態では、画像処理システム２００は、インターネット２０６を介してサーバ／データベース装置２０４に接続されたユーザ制御の計算装置２０２（例えば、ユーザ制御のパーソナルコンピュータ）を備えるように構成し得る。したがって、本発明の概念を実行するリソースは通常、計算装置２０２及びサーバ／データベース装置２０４との間で分割し得る。
【００３２】
ユーザ制御の計算装置２０２側でのハードウェア制約を更に低減するために、本発明により、本発明の概念によって提供される機能をユーザ／顧客に、例えば「オンデマンド（on-demand）」で提供することが可能である。一例として、元の三次元グラフィックス画像に基づいてポリゴン低減画像を生成したいユーザは、計算装置２０２に示されるユーザインタフェースを通して、サーバ２０４で実行中のポリゴンリダクション最適化のコンピュータ実施にアクセスし得る。代替的には、計算装置２０２には、原画像を生成するソフトウェア（例えば、３Ｄスタジオマックス（３Ｄ  Ｓｔｕｄｉｏ  Ｍａｘ）、マヤ（Ｍａｙａ）等）を提供し得、計算装置２０２で実行中のソフトウェアは、サーバ２０４で実行中の本発明の概念のコンピュータ実施にアクセス／対話する（例えば、ＡＰＩにより、「オンデマンド」で、加入して、固定サービス等として）ように構成される。
【００３３】
本発明の概念を実行するに当たり、図３及び図４を更に参照すると、プロセスは、例えば、計算装置２０２のユーザによって制御される結合画像処理システム２００の形態の画像処理装置を用いて、初期、すなわち元の三次元グラフィックス画像／オブジェクトとして表現される単一の（１つ又は複数の）三次元グラフィックス画像４０２を受信すること（Ｓ０）で開始される。初期画像４０２の受信に続き、第１のポリゴンリダクションプロセスが実行され（Ｓ１）、その結果、初期三次元グラフィックス画像４０２のポリゴン低減表現である第１の三次元グラフィックス画像４０４が生成される。上述したように、第１のポリゴンリダクションプロセスは、目標とするポリゴンの割当量を有する「ハイエンド（high-end）」プロセスであってもよく、又は第１の三次元グラフィックス画像４０４内の問題エリアを識別するより「ローエンド（low- end）」のプロセスであってもよい。
【００３４】
したがって、第１のポリゴンリダクションプロセスを実行するステップに続き、第１の三次元グラフィックス画像４０４が、初期三次元グラフィックス画像４０２と比較され（Ｓ２）、例えば、処理済み画像４０４と原画像４０２とのそれぞれの差を示す「比較画像」４０６を生成する。比較画像４０６は、視覚誤差メトリックの特定（Ｓ３）に使用し得る。上述したように、視覚誤差メトリックは、三次元グラフィックス画像の単一のビュー及び複数のビューに対して特定し得る。
【００３５】
単一又は複数の視覚誤差メトリックの特定に続き、視覚誤差メトリックが所定の誤差範囲外であると判断される場合、プロセスは、（１つ又は複数の）視覚誤差メトリックを考慮に入れて、第２のポリゴンリダクションプロセスを実行すること（Ｓ４）によって続き、第２のポリゴンリダクションプロセスは少なくとも部分的に、第１のポリゴンリダクションプロセスと異なり、違いは、特定される視覚誤差メトリックに依存する。例えば、完全に異なるポリゴンリダクションプロセスを選択してもよく、又はポリゴンリダクションを実行するアルゴリズムを調整し得る。
【００３６】
本発明の概念との関連において、視覚誤差メトリックは「エリア」依存であり得、例えば、「誤差クラスタ」を特定することが可能であり得る。換言すれば、第１の三次元グラフィックス画像４０４の他のエリアよりも広い第１の三次元グラフィックス画像４０４の幾つかのエリア（すなわち、部分）が、初期三次元グラフィックス画像４０２とは異なるか否かを判断することが可能であり得る。したがって、これらの問題エリアには、第２のポリゴンリダクションプロセスを実行する際、より多いポリゴンの割当量を与え得る。特定の問題エリア及び所望のポリゴンの割当量の可能な再分配についての情報を含む視覚誤差メトリックを、第２のポリゴンリダクションにメタデータとして提供し得る。
【００３７】
プロセスは、例えば、反復が所定の最大に達し、且つ／又は視覚誤差メトリックが所定の誤差範囲内に入ることを含む停止条件に達するまで幾つかの回数、反復し得、その結果、初期三次元グラフィックス画像４０２のポリゴン低減表現である第２の三次元グラフィックス画像４０８が生成される。
【００３８】
上記説明での所定の誤差及び図４に関連して、プロセスが、初期三次元グラフィックス画像４０２と初期三次元グラフィックス画像４０２のポリゴン低減表現（すなわち、第１及び／又は第２の三次元グラフィックス画像４０４、４０８）との差を低減するために反復されることが示される。しかし、プロセスを初期三次元グラフィックス画像と結果として生成される三次元グラフィックス画像との「誤差を増大」させるために反復してもよいことを理解されたい。したがって、結果として生成される画像が「あまりに良すぎる」場合、初期画像と結果として生成される画像との差（すなわち、誤差）を増大させ、それにより、結果として生成される画像を、初期画像の表現に使用されるポリゴン数に関して更に低減できるようにすることが望ましいことがある。
【００３９】
アルゴリズムの観点から、ポリゴンリダクション最適化は通常、少なくとも２つの反復のフィードバックループとして実施し得る。したがって、本発明のプロセスは、擬似コードを例示する以下によって示し得る。
・ＲｕｎＲｅｄｕｃｅｒＲｅｄｕｃｔｉｏｎ（）
・Ｄｏ
・ＭｅａｓｕｒｅＶｉｅｗＤｅｐｅｎｄｅｎｔＥｒｒｏｒ（）
・ＦｅｅｄｂａｃｋＶｉｅｗＤｅｐｅｎｄｅｎｔＥｒｒｏｒＩｎｔｏＷｅｉｇｈｔｉｎｇ（）
・ＲｕｎＲｅｄｕｃｅｒＲｅｄｕｃｔｉｏｎ（）
・ＵｎｔｉｌＲｅａｃｈｅｄＣｕｔｏｆｆ（）
上述したように、カットオフは、
・特定の反復数、
・特定数の三角形に達すること、及び／又は
・特定の品質レベルに達すること
のうちの任意又は組み合わせであり得る。
【００４０】
まとめると、本発明は、初期三次元グラフィックス画像のポリゴンリダクションを最適化するコンピュータ実施方法に関し、本方法は、第１のポリゴンリダクションプロセスを実行することであって、その結果、初期三次元グラフィックス画像のポリゴン低減表現である第１の三次元グラフィックス画像が生成される、第１のポリゴンリダクションプロセスを実行することと、第１の三次元グラフィックス画像を初期三次元グラフィックス画像と比較することと、第１の三次元グラフィックス画像と初期三次元グラフィックス画像との比較の結果に基づいて、視覚誤差メトリックを特定することと、視覚誤差メトリックが所定の誤差範囲外である場合、第２のポリゴンリダクションプロセスを実行することであって、その結果、初期三次元グラフィックスオブジェクトのポリゴン低減表現である第２の三次元グラフィックス画像が生成される、第２のポリゴンリダクションプロセスを実行することとを含む。
【００４１】
本発明により、ポリゴンリダクションプロセスを実行する際に出現する視覚誤差の識別を自動化することが可能であり、したがって、例えば、視覚的に魅力的な画像を達成するために必要な手作業労働量を最小化することにより、コストを低減するという利点が生じる。
【００４２】
本開示は、様々な動作を達成する、任意の機械可読媒体上の方法、システム、及びプログラム製品を意図する。本開示の実施形態は、既存のコンピュータプロセッサを使用して実施してもよく、本実施形態の目的で若しくは他の目的で組み込まれた適切なシステムの専用コンピュータプロセスによって実施してもよく、又はハードワイヤードシステムによって実施してもよい。本開示の範囲内の実施形態は、記憶された機械実行可能命令又はデータ構造を搬送するか、又は有する機械可読媒体を備えるプログラム製品を含む。そのような機械可読媒体は、汎用若しくは専用コンピュータ又はプロセッサを有する他の機械によってアクセス可能な任意の利用可能な媒体とすることができる。例として、そのような機械可読媒体は、ＲＡＭ、ＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、ＣＤ−ＲＯＭ、若しくは他の光ディスク記憶装置、磁気ディスク記憶装置若しくは他の磁気記憶装置、又は機械実行可能命令若しくはデータ構造の形態の所望のプログラムコードを搬送若しくは記憶するために使用することができ、汎用若しくは専用コンピュータ又はプロセッサを有する他の機械によってアクセス可能な任意の他の媒体を含むことができる。情報がネットワーク又は別の通信接続（ハードワイヤード、無線、又はハードワイヤード若しくは無線の組み合わせ）を介して機械に転送又は提供される場合、機械は適宜、接続を機械可読媒体として認識する。したがって、任意のそのような接続は適宜、機械可読媒体と呼ばれる。上記の組み合わせも機械可読媒体の範囲内に含まれる。機械実行可能命令は、例えば、汎用コンピュータ、専用コンピュータ、又は専用処理機械に特定の機能又は機能群を実行させる命令及びデータを含む。
【００４３】
図は特定の順序の方法ステップを示すことがあるが、ステップの順序は示される順序と異なってもよい。また、２つ以上のステップを同時に又は部分的に同時に実行してもよい。そのような変形形態は、選ばれるソフトウェア及びハードウェアシステムと、設計者の選択とに依存する。全てのそのような変形形態は本開示の範囲内にある。同様に、ソフトウェア実装形態は、ルールに基づく論理と、様々な接続ステップ、処理ステップ、比較ステップ、及び判断ステップを達成する他の論理を使用する標準プログラミング技法を用いて達成することができる。さらに、本発明について、本発明の特定の例示的な実施形態を参照して説明したが、多くの異なる代替形態、変更形態等が当業者には明らかになろう。開示される実施形態に対する変形形態は、特許請求される本発明を実施する際、図面、本開示、及び添付の特許請求の範囲の研究から当業者によって理解され実行することができる。さらに、特許請求の範囲では、「備える」という用語は、他の要素又はステップを除外しない。
【図１ａ】
0006324393.tif 000002
【図１ｂ】
0006324393.tif 000003
【図２】
0006324393.tif 000004
【図３】
0006324393.tif 000005
【図４】
0006324393.tif 000006