ボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形
【課題】ボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形の技術を提供する。
【解決手段】情報がユーザから受け取られ、この場合、その情報は、オリジナルメッシュがどのように変形されるかを示す。その後、オリジナルメッシュは、その情報と、オリジナルメッシュから生成されたボリュメトリックグラフへの体積微分演算子の適用とに基づいて、変形される。
【解決手段】情報がユーザから受け取られ、この場合、その情報は、オリジナルメッシュがどのように変形されるかを示す。その後、オリジナルメッシュは、その情報と、オリジナルメッシュから生成されたボリュメトリックグラフへの体積微分演算子の適用とに基づいて、変形される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メッシュ変形の技術に関する。
【背景技術】
【０００２】
メッシュ変形（ｍｅｓｈ ｄｅｆｏｒｍａｔｉｏｎ）は、コンピュータモデリングおよびアニメーションの様々な応用例において役立つ。例えば、メッシュ変形は、アーティストが３次元（３−Ｄ）キャラクタの様式化されたボディ形状および変形を形作るのを手助けするのに役立つ。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかし、しなやかで非常に誇張された動作を実行するキャラクタに見出されるような大規模な変形は、今日も課題として残されている。既存のメッシュ変形技法は、不自然な体積変化を伴う信じがたい結果をしばしば生み出す。
【課題を解決するための手段】
【０００４】
この要約は、以下の詳細な説明においてさらに説明される概念の抜粋を簡潔な形式で紹介するために提供される。この要約は、特許請求される主題の主要な特徴または必須の特徴を特定することを意図しておらず、特許請求される主題の範囲を決定する際の助けとして使用されることも意図していない。
【０００５】
上記の事柄に鑑みて、ボリュメトリックグラフ・ラプラシアン（ｖｏｌｕｍｅｔｒｉｃｇｒａｐｈ Ｌａｐｌａｃｉａｎ：体積グラフラプラシアン）を使用する大規模メッシュ変形が説明される。一態様では、情報がユーザから受け取られ、この場合、その情報は、オリジナルメッシュ（元のメッシュ）がどのように変形されるかを示す。その後、オリジナルメッシュは、その情報と、オリジナルメッシュから生成されたボリュメトリックグラフ（体積グラフ）への体積微分演算子（ｖｏｌｕｍｅｔｒｉｃｄｉｆｆｅｒｅｎｔｉａｌ ｏｐｅｒａｔｏｒ）の適用とに基づいて、変形される。
【０００６】
図面において、構成要素の参照番号の左端の数字は、その構成要素が最初に出現した特定の図面を識別する。
【図面の簡単な説明】
【０００７】
【図１】ボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形のための例示的なシステムを示す図である。
【図２】従来の大規模メッシュ変形とボリュメトリックグラフ・ラプラシアン１１４を使用する大規模メッシュ変形との例示的な比較を示す図である。
【図３】例示的な大規模捻り変形結果を示す図である。
【図４】例示的な大規模曲げ変形結果を示す図である。
【図５】例示的なボリュメトリックグラフを示す図である。
【図６】ボリュメトリックグラフを構成するための例示的な操作を示す図である。
【図７】ボリュメトリックグラフにおける辺連結の例示的なタイプを示す図である。
【図８】例示的な曲線ベースの変形を示す図である。
【図９】一様、辺長の逆数、および熱核（平方距離の減衰指数関数）重み付け方式を含む重み付け方式の例示的な比較を示す図である。
【図１０】ボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形と比較された従来の大規模メッシュ変形技法の例示的な比較を示す図である。
【図１１】ボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形のための例示的な手順を示す図である。
【図１２】ボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形が完全または部分的に実施され得る適切なコンピューティング環境の一例を示す図である。
【発明を実施するための形態】
【０００８】
〈概要〉
ボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形は、ボリュメトリックグラフ・ラプラシアンを使用する、３−Ｄメッシュ上での大規模変形のための新規な技法を提供する。入力メッシュの内側の体積を表すグラフが、最初に構成される。グラフは、入力メッシュの内部のソリッドメッシング（ｓｏｌｉｄｍｅｓｈｉｎｇ）を形成する必要がない（体積ラプラス演算子（ｖｏｌｕｍｅｔｒｉｃ Ｌａｐｌａｃｉａｎ ｏｐｅｒａｔｏｒ）は、表面内部をメッシュすることなく、ボリュメトリックグラフに適用されることができる）。グラフの辺は、体積内の近隣点を単純に接続する。グラフのラプラシアンは、グラフ内の各点とその近隣点の平均との差として、ボリュメトリックディテール（体積詳細）を符号化する。変形中にこれらのボリュメトリックディテールを保存することが、体積の不自然な変化を防止する体積制約を課す。また、グラフ内には、メッシュの外側の近距離にある点も含まれる。これは、局所自己交差（ｌｏｃａｌｓｅｌｆ−ｉｎｔｅｒｓｅｃｔｉｏｎ）を回避する上で助けとなる。ボリュメトリックディテールの保存は、２次エネルギー関数（ｑｕａｄｒｉｃｅｎｅｒｇｙ ｆｕｎｃｔｉｏｎ）によって表される。２次エネルギー関数を最小化することが、最小２乗の意味において詳細を保存し、誤差を変形されたメッシュの全体にわたって一様に分散させる。２次エネルギー関数は、表面位置、詳細、または滑らかさを含む従来の制約とも組み合わされることができ、疎線形系（ｓｐａｒｓｅｌｉｎｅａｒ ｓｙｓｔｅｍ）を解くことによって効率的に最小化することができる。
【０００９】
図１から図１１を参照して以下でより詳細に説明されるように、ボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形が、２−Ｄ曲線ベースの変形システムにおいて実施され、初心者も熟練ユーザも等しく十分に満足できる変形を僅かな労力で生み出すことを可能にする。この新規なメッシュ変形技法は、３−Ｄモデルのスケルトンおよび基本姿勢を入力として必要とせず、広い範囲にわたるしなやかな変形を扱うことができる。一実施では、ボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形のためのシステムは、２−Ｄアニメキャラクタのしなやかで誇張された変形を３−Ｄメッシュに適用するために利用される。
【００１０】
〈例示的なシステム〉
必ずしも必要ではないが、ボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形は、パーソナルコンピュータなどのコンピューティングデバイスによって実行されるコンピュータプログラム命令という一般的な文脈において説明される。プログラムモジュールは一般に、特定のタスクを実行し、または特定の抽象データ型を実施する、ルーチン、プログラム、オブジェクト、コンポーネント、データ構造などを含む。システムおよび方法は、上述の文脈において説明されるが、これ以降で説明される行為および動作は、ハードウェアで実施されてもよい。
【００１１】
図１は、ボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形のための例示的なシステム１００を示している。この実施では、システム１００は、汎用コンピューティングデバイス１０２を含む。コンピューティングデバイス１０２は、パーソナルコンピュータ、ラップトップ、サーバ、および／またはハンドヘルドもしくはモバイルコンピューティングデバイス（例えば、セルラ電話、携帯情報端末）など、任意のタイプのコンピューティングデバイスを表す。
【００１２】
コンピューティングデバイス１０２は、プログラムモジュール１０４と、プログラムデータ１０６とを含む。プログラムモジュール１０４は、（ボリュメトリックグラフ・ラプラシアンを使用する）大規模メッシュ変形モジュール１０８（これ以降、しばしば「変形モジュール１０８」と呼ばれる）と、オペレーティングシステムなどのその他のプログラムモジュール１１０とを含む。変形モジュール１０８は、３−Ｄメッシュ１１６（オリジナルメッシュ：元のメッシュ）から生成されたボリュメトリックグラフ・ラプラシアン（ＶＧＬ）１１４上で大規模メッシュ変形１１２を生じさせるために、新規な技法を実施する。変形モジュール１０８は、ＶＧＬを利用して、ボリュメトリックディテールを３−Ｄ体積内の各点とグラフ内のその近隣点の平均との差として表す。ＶＧＬは、変形モジュール１０８が、差分領域（ｄｉｆｆｅｒｅｎｔｉａｌｄｏｍａｉｎ）技法を使用して表面詳細を保存することを可能にし、それによって、最小２乗最小化を用いて誤差を全体的に分散させることによって、視覚的に満足できる変形結果１１２を生み出す。メッシュ１１６の表面上の代わりに体積領域内で作業することによって、変形モジュール１０８は、ＶＧＬを利用して、効率的に体積制約を課し、それによって、不自然な体積変化および局所自己交差を回避する。
【００１３】
図２は、従来の大規模メッシュ変形と、ボリュメトリックグラフ・ラプラシアン１１４を使用する大規模メッシュ変形との例示的な比較を示している。より具体的には、画像２０２は、例示的なオリジナルメッシュ１１６を示す。画像２０４は、従来のポアソン編集メッシュ変形（Ｐｏｉｓｓｏｎｅｄｉｔｉｎｇ ｍｅｓｈ ｄｅｆｏｒｍａｔｉｏｎ）技法を使用してオリジナルメッシュ１１６を変形した例示的な結果を示す。画像２０６は、ボリュメトリックグラフ・ラプラシアン１１４を使用したオリジナルメッシュ１１６の大規模メッシュ変形の例示的な結果を示す。画像２０４の例に示されるように、ポアソンメッシュ編集を使用したオリジナルメッシュ１１６の変形は、特にモデルの右腿において不自然な収縮を引き起こす。
【００１４】
ボリュメトリックグラフ・ラプラシアン１１４を使用する場合、変形モジュール１０８は、２次エネルギー関数によって体積制約を表す。変形モジュール１０８は公式には、疎線形系によってこの関数を最小化し、その関数を（例えば、表面位置、表面詳細、表面の滑らかさに対する）その他の表面制約と組み合わせる。ボリュメトリックグラフ・ラプラシアン１１４を三角メッシュ（ｔｒｉａｎｇｕｌａｒｍｅｓｈ）に適用するため、変形モジュール１０８は最初に、ボリュメトリックグラフ１１８を構成するが、ボリュメトリックグラフは、オリジナルメッシュ１１６の点と、メッシュ１１６の内側に存在する単純格子（ｓｉｍｐｌｅｌａｔｔｉｃｅ）（グラフの内側）から以下で説明されるように導出される点とを含む。グラフの辺は、これらの点を接続する。これらのグラフの辺は、オリジナルメッシュ１１６の辺の上位集合である。グラフは、メッシュ１１６の内部のメッシング（四面体またはその他の有限要素への体積テッセレーション（ｖｏｌｕｍｅｔｒｉｃｔｅｓｓｅｌｌａｔｉｏｎ））を形成する必要がない。
【００１５】
ユーザは、オリジナルメッシュ１１６上の有限の点の集合１２０（１つまたは複数の制御曲線（ｃｏｎｔｒｏｌｃｕｒｖｅ））を識別することによって、変形を指定する。指定された点１２０は、曲線を定義し、これらの点１２０が結果の変形においてどこに移動するかを表す。例示的な説明の目的で、指定された点１２０は、この例では、曲線を識別する。変形モジュール１０８は、表面詳細を維持し、体積をほぼ保存しながら、指定された点１２０を指定された移動先に写像するために、最小値を取る２次エネルギー関数を生成する。
【００１６】
このようにして、変形モジュール１０８は、表面内部をメッシュすることなく、体積微分演算子をボリュメトリックグラフ１１８に適用することによって、大規模メッシュ変形の問題を解決する。対照的に、従来の微分手法は、表面演算子のみを考えた。表面から立体にこれらの演算子を拡張する素朴な方法は、物体内部の四面体メッシュにわたってそれらを定義することである。しかし、複雑な物体をソリッドメッシュすることは、困難なことで有名である。既存のメッシュ変形技法は一般に、幾何学的形状を再メッシュし、その連結度を混乱させ、それによって、メッシュ変形の共通要件を破る。ソリッドメッシングも、（例えば、四面体は反転しない、各内部頂点はその近隣点のビジュアルハル（ｖｉｓｕａｌｈｕｌｌ）内に留まるといった）多くの制約を伴う。そのような制約は、従来のメッシュ変形技法が、内部点を経済的に分散させ、局所自己交差を防止するために（システム１００によって実行される）「外部シェル（ｅｘｔｅｒｉｏｒｓｈｅｌｌ）」を追加することを、計算的に非実用的なものにする。
【００１７】
ボリュメトリックグラフ１１８を変形し、２−Ｄ曲線（指定された点１２０のそれぞれの部分）からの変形を実行する、変形モジュール１０８の例示的な動作が、今から説明される。
【００１８】
〈ボリュメトリックグラフの例示的な変形〉
Ｍ＝（Ｖ，Ｋ）を変形の対象とする三角メッシュ１１６とすると、Ｖは、ｎ個の点位置の集合（すなわち、オリジナルメッシュ１１６の点集合）、Ｖ＝｛ｐi∈Ｒ3｜１≦ｉ≦ｎ｝であり、Ｋは、すべての点連結度（ｖｅｒｔｅｘ ｃｏｎｎｅｃｔｉｖｉｔｙ）情報を含む抽象単体複体（ａｂｓｔｒａｃｔｓｉｍｐｌｉｃｉａｌ ｃｏｍｐｌｅｘ）である。例示的な説明の目的で、そのような点連結度情報は、「その他のデータ」１２２のそれぞれ部分として示される。Ｋには、頂点｛ｉ｝と、辺｛ｉ，ｊ｝と、面｛ｉ，ｊ，ｋ｝の３つのタイプが存在する。
【００１９】
〈抽象グラフ上でのラプラシアン変形〉
Ｇ＝（Ｐ，Ｅ）がグラフであると仮定すると、Ｐは、Ｎ個の点位置の集合、Ｐ＝｛ｐi∈Ｒ3｜１≦ｉ≦Ｎ｝であり、Ｅ＝｛｛ｉ，ｊ｝｜ｐiはｐjに接続される｝は、辺の集合である。グラフのラプラシアンは、多様体上のラプラス演算子に類似している。ラプラシアンは、グラフＧ内の各点ｐiと、その近隣点の１次結合との差
【００２０】
【数１】
【００２１】
を計算し、Ｎ（ｉ）＝｛ｊ｜｛ｉ，ｊ｝∈Ｅ｝は、隣接辺、ｗijは、点ｐjの重み、δiは、グラフＧ内の点ｐiのラプラス座標である。ＬGは、グラフＧのラプラス演算子と呼ばれる。重みｗijは、正数であり、Σj∈N(i)ｗij＝１を満足する。最も単純な重み付けは、一様な重み付け、ｗij＝１／｜Ｎ（ｉ）｜である。（変形モジュール１０８は、以下の「ボリュメトリックグラフの例示的な変形」と題するセクションで説明されるように、より複雑な重み付け方式を実施する）。
【００２２】
変形を制御するため、Ｎ個のメッシュ頂点の部分集合である制御曲線（すなわち、指定された点１２０）ｑi、ｉ∈｛１，．．．，ｍ｝として、入力変形位置がある。変形モジュール１０８は、グラフ内の各点ｉに関する新しい（変形された）ラプラス座標δ’iを計算するために、これらの指定された制御曲線を利用する。メッシュ頂点ｐ’iの変形された位置（例えば「その他のデータ」１２２を参照）は、その後、次の２次最小化問題を解くことによって得られる。
【００２３】
【数２】
【００２４】
式（２）の第１項は、局所的な細部の保存を表し、第２項は、ユーザによって直接指定された頂点１２０の位置を制約する。パラメータαは、これら２つの目的のバランスを取る。
【００２５】
変形されたラプラス座標は、次のように計算され、
δ’i＝Ｔiδi
ここで、δiは、式（１）で定義される静止姿勢のラプラス座標であり、Ｔiは、そのラプラス座標を変形姿勢に変換する。この実施では、異方性スケーリング（ａｎｉｓｏｔｒｏｐｉｃ ｓｃａｌｉｎｇ）を含む汎用変換Ｔiは、強力であり過ぎ、局所的な細部に「適合しない（ｆｉｔ ａｗａｙ）」ことがあり得る。これに対処するため、変形モジュール１０８は、Ｔiを回転と同方性スケールに制限する。
【００２６】
頂点の部分集合ｑiの変形された位置を与えると、よく知られた方法が、Ｔiを得るために使用されることができる。この実施では、変形モジュール１０８は、以下の「ボリュメトリックグラフの例示的な変形」と題するセクションで説明される方法を利用する。この方法は、局所変換を指定された変形領域からメッシュ全体に伝播させ（大規模メッシュ変形１１２を引き起こし）、変形部位から離れたその物自体に向かって変換を混合する。
【００２７】
グラフが三角メッシュである場合、グラフラプラシアンは、メッシュラプラシアンと一致する（この例では、メッシュまたは表面ラプラシアンが、オリジナルメッシュのラプラシアンである）。表面詳細を符号化するためにメッシュラプラシアンを使用すると、詳細な幾何学的構造は、広い範囲の編集操作にわたって保存される。しかし、大規模変形の場合、そのような方法は、不自然な体積変化（例えば、図３の画像（ａ）を参照）および／または局所自己交差（例えば、図４の画像（ａ）を参照）を呈する。
【００２８】
図３は、例示的な大規模な捻り変形結果を示している。より具体的には、図３の画像（ａ）は、ラプラシアン表面（Ｌａｐｌａｃｉａｎｓｕｒｆａｃｅ）に基づいた例示的な大規模な捻り変形を示す。図３の画像（ｂ）は、ポアソンメッシュに基づいた例示的な大規模な捻り変形を示す。画像（ｃ）は、変形モジュール１０８のＶＧＬ操作に基づいた例示的な大規模な捻り変形を示す。
【００２９】
図４は、例示的な大規模な曲げ変形結果を示している。より具体的には、図４の画像（ａ）は、ラプラシアン表面に基づいた例示的な大規模な曲げ変形を示す。図４の画像（ｂ）は、ポアソンメッシュに基づいた例示的な大規模な曲げ変形を示す。画像（ｃ）は、変形モジュール１０８のＶＧＬ操作に基づいた例示的な大規模な曲げ変形を示す。
【００３０】
オリジナルメッシュ１１６が不自然な体積変化および／または局所自己交差を減少させるように、変形モジュール１０８が、ボリュメトリックグラフ１１８を構成することによってどのように体積制約を課すかについて今から説明する。
【００３１】
〈ボリュメトリックグラフの例示的な構成〉
変形モジュール１０８は、大きな体積変化および局所自己交差を回避するが、大域的な自己交差の除去を保証しない。この実施では、大域的な自己交差は、ユーザによって対処される。変形モジュール１０８は、２つのタイプの中間グラフである内側グラフ（ｉｎｓｉｄｅｇｒａｐｈ）および外側グラフ（ｏｕｔｓｉｄｅ ｇｒａｐｈ）を利用して、ボリュメトリックグラフ１１８を構築する。内側グラフＧinは、メッシュ１１６の内部体積を満たし、大きな体積変化を防止し、一方、外側グラフＧoutは、局所自己交差を防止する。
【００３２】
図５は、例示的なボリュメトリックグラフ１１８を示している。より具体的には、ボリュメトリックグラフ５０２は、例示的なＧinを示し、ボリュメトリックグラフ５０４は、例示的なＧoutを示す。
【００３３】
Ｇinを得るための１つの方法は、表面メッシュ１１６の内部体積を四面体分割（ｔｅｔｒａｈｅｄｒａｌｉｚｅ）することである。しかし、四面体メッシュ生成は一般に、実施するのが相当に困難であり、高い計算コストがかかるうえ、言うまでもなく、そのようなメッシュ生成は一般に、堅実な方式で実施するのが困難である（例えば、モデルが複雑だと、一般に不恰好な四面体を生成する）。表面メッシュ１１６の内部体積を四面体分割する代わりに、変形モジュール１０８は、制限のより少ないボリュメトリックグラフを生成するために、相当に単純化された操作を実施する。
【００３４】
図６は、ボリュメトリックグラフ１１８を構成するための例示的なステップを示している。より具体的には、図６に示されたこの実施では、変形モジュール１０８は、次のようにしてボリュメトリックグラフ１１８を生成する。
【００３５】
・各頂点をその法線の反対方向にある距離だけずらすことによって、メッシュＭの内側シェル（ｉｎｎｅｒｓｈｅｌｌ）Ｍinを構成する。これは、例えば、図６の画像（ａ）に示されている。
【００３６】
・ＭinおよびＭを体心立法（ＢＣＣ：ｂｏｄｙ−ｃｅｎｔｅｒｅｄ ｃｕｂｉｃ）格子に埋め込む。外側の格子ノードを取り除く。これらの例示的な操作の結果は、例えば、図６の画像（ｂ）に示されている。
【００３７】
・Ｍ、Ｍin、および格子ノードの間の辺連結を構築する。この操作の結果は、例えば、図６の画像（ｃ）に示されている。
【００３８】
・辺消去（ｅｄｇｅ ｃｏｌｌａｐｓｅ）を使用してグラフを簡素化し、グラフを平滑化する。この操作の結果は、例えば、図６の画像（ｄ）に示されている。
【００３９】
この実施では、内側シェルＭinの目的は、格子サンプリング操作によって見落とされることがある（例えば、猫の尻尾のような）細い特徴内にさえも、内部点が挿入されるよう保証することである。内側シェルを計算するため、変形モジュール１０８は、簡略化エンベロープ（ｓｉｍｐｌｉｆｉｃａｔｉｏｎｅｎｖｅｌｏｐｅ）に基づいた操作を利用する。各反復において、変形モジュール１０８は、各頂点をその法線ベクトルとは反対に平均辺長の分数だけ動かすことを試みる。頂点を動かした後、変形モジュール１０８は、その隣接三角形を互いの交差およびモデルの残りとの交差についてテストする。交差が見出されない場合、これらの操作の結果が受け入れられる。それ以外の場合、操作の結果は拒絶され、頂点は元に戻される。すべての頂点が所望の距離だけ動かされたとき、またはもはや動かされ得ないとき、反復は終了する。
【００４０】
図７は、ボリュメトリックグラフにおける辺連結の例示的なタイプを示している。より具体的には、図７の画像（ａ）は、例示的な境界辺を示している。図７の画像（ｂ）は、例示的な内部辺を示している。これらの例に照らして、ＢＣＣ格子は、直交グリッドのすべての点とセルの中心とにノードを含むことが分かる（例えば、画像（ｂ））。ノード位置は、２つのインタレースグリッド（ｉｎｔｅｒｌａｃｅｄｇｒｉｄ）に属すると見なされ得る。この格子は、自然界では所望の剛性を有する結晶構造として生じる。この実施では、平均辺長を等しくするために、大きな間隔が設定される。
【００４１】
３つのタイプの辺連結が、初期ボリュメトリックグラフ１１８を形成する。第１に、変形モジュール１０８は、Ｍ内の各頂点をＭin内の対応する頂点に連結する（例えば、図６の画像（ａ））。各プリズム面のより短い対角線も同様に含められる。第２に、変形モジュール１０８は、ＢＣＣ格子の各内部ノードを他のインタレースグリッド内の８つの最近隣点と連結する（例えば、図７の画像（ｂ））。第３に、変形モジュール１０８は、ＭinとＢＣＣ格子のノードを連結する。Ｍinと交差し、Ｍin内に少なくとも１つのノードを有する、ＢＣＣ格子の各辺について、変形モジュール１０８は、Ｍin内のＢＣＣ格子ノードを、この交差に最も近いＭin内の点に連結する。
【００４２】
変形モジュール１０８は、グラフをより一様にするために、初期グラフ上で簡略化および平滑化操作を実施する。この目的で、変形モジュール１０８は、グラフ１１８の辺を長さの昇順で評価する。辺の長さが閾値（Ｍの平均辺長の半分）より小さい場合、それは辺の中点に縮小する。簡略化の後、数回の平滑化反復（発明者らの実施では３回）が実行され、各点がその近隣点の平均に動かされる。この実施では、簡略化も平滑化も、Ｍの頂点には適用されない。
【００４３】
外側グラフＧoutを構成するため（ボリュメトリックグラフ１１８の生成操作の一部）、変形モジュール１０８は、このボリュメトリックグラフを構成するために先に説明された、法線方向にずらす反復的方法（ｉｔｅｒａｔｉｖｅｎｏｒｍａｌ−ｏｆｆｓｅｔ ｍｅｔｈｏｄ）を利用するが、Ｍoutを形成するには、表面の内側ではなく外側に向かう。変形モジュール１０８は、ＭとＭinの間と同様に、ＭとＭoutの間の連結を構築する。
【００４４】
この実施では、ＧinおよびＧoutは共に、ユーザによって直接見られることのない（それぞれ「その他のデータ」１２２で表される）中間データ構造であり、ユーザ対話の後で廃棄されることに留意されたい。これらのデータ構造は、メッシュ表面の変形を制約するためにのみ役立つ。ＭinおよびＭoutとそれら自体との交差ならびにＭとの交差が、特に曲率の高い領域を含むメッシュ上で生じることがあり得るが、そのような交差は、対話システム１００において困難を引き起こさない。
【００４５】
ボリュメトリックグラフの例示的な変形
元の表面の詳細を保存することと体積を制約することの間のバランスを取るため、変形モジュール１０８は、式（２）のエネルギー関数の次の汎用形式への変更を利用し、
【００４６】
【数３】
【００４７】
ここで、グラフＧ内の最初のｎ個の点は、メッシュＭに属する。ＬMは、離散メッシュラプラス演算子である。Ｇ’は、Ｍに属する辺を取り除くことによって形成される、Ｇのサブグラフである。オリジナルメッシュＭ上の点について、ε’i（１≦ｉ≦ｎ）は、変形された座標系におけるメッシュラプラス座標である。ボリュメトリックグラフＧ’内の点について、δ’i（１≦ｉ≦Ｎ）は、変形された座標系におけるグラフラプラス座標である。したがって、エネルギーは、表面詳細の保存と、ユーザ選択の変形位置（指定された点１２０）の強制と、ボリュメトリックディテール／剛性の保存とに対応する、３つの項に分解される。
【００４８】
βは、表面詳細とボリュメトリックディテールの間のバランスを取る。変形モジュール１０８は、
【００４９】
【数４】
【００５０】
となる
【００５１】
【数５】
【００５２】
を指定する。係数ｎ／Ｎは、重みがボリュメトリックグラフの格子密度に対して鈍感となるように、重みを正規化する。この正規化によれば、
【００５３】
【数６】
【００５４】
は、体積を保存し、自己交差を防止する。この実施では、０．１＜α＜１であり、αは正規化されない。これは、制約強度は、メッシュ点の総数に対する制約点の数に依存するのが望ましいからである。この実施では、αは、デフォルトで０．２に設定される。
【００５５】
一代替実施形態では、式（３）の体積制約は、２次平滑エネルギー（ｑｕａｄｒｉｃｓｍｏｏｔｈｎｅｓｓ ｅｎｅｒｇｙ）と組み合わされる（主眼が幾何学的に相当細かいモデルを変形することである場合、これは行われない）。
【００５６】
〈局所変換の例示的な伝播〉
静止座標系におけるラプラス座標εiおよびδiを、変形された座標系における新しいラプラス座標ε’iおよびδ’iに移す、局所変換Ｔiを得るために、変形モジュール１０８は、ＷＩＲＥ変形操作を実施する。これらの操作では、変形モジュール１０８は、曲線１２０を形成するメッシュ頂点の系列を選択する。その後、これらの選択されたメッシュ頂点は、新しい状態に変形される。この曲線は、変形を制御し、ｑiを定義する（例えば、図８の画像（ａ）を参照）。
【００５７】
図８は、例示的な曲線ベースの変形を示している。より具体的には、図８の画像（ａ）は、例示的なオリジナルメッシュ１１６と、例示的な制御曲線８０２とを示す。図８の画像（ｂ）は、０（例えば、フィールド８０４−より暗いシェーディング）および１（例えば、フィールド８０６−より明るいシェーディング）の例示的な強度フィールドを示す。図８の画像（ｃ）は、図１の変形モジュール１０８の曲線ベースの変形操作から生成された、例示的な変形されたメッシュを示す。
【００５８】
制御曲線（例えば、制御曲線８０２）は、曲線上の頂点が変形される範囲のみを指定する。伝播アルゴリズムを利用する変形モジュール１０８は、最初に近隣グラフ点（制御点の１リングメッシュ近隣点）がどこまで変形するかを決定し、次に曲線点における局所変換を推測し、最後にメッシュ全体にわたって変換を伝播させる（例えば、変形されたメッシュ１１２を生じさせる）。これらの操作は、ｑiのメッシュ近隣点を発見し、ＷＩＲＥを使用してそれらの変形された位置を得ることによって、開始する。より具体的には、Ｃ（ｕ）およびＣ’（ｕ）をそれぞれ、弧長ｕ∈［０，１］によってパラメータ化された、元の制御曲線および変形された制御曲線とする。近隣点ｐ∈Ｒ3を与え、ｕp∈［０，１］を、ｐと曲線Ｃ（ｕ）の間の距離を最小化するパラメータ値とする。変形は、ＣがＣ’に写像され、近くの点も同様に動いて
ｐ’＝Ｃ’（ｕp）＋Ｒ（ｕp）（ｓ（ｕp）（ｐ−Ｃ（ｕp）））
となるように、ｐをｐ’に写像する。この式において、Ｒ（ｕ）は、Ｃ上の接ベクトルｔ（ｕ）を取り、ｔ（ｕ）×ｔ’（ｕ）の周りで回転させることによって、それをＣ’上の対応する接ベクトルｔ’（ｕ）に写像する、３×３回転行列である。ｓ（ｕ）は、スケール係数である。それは、各曲線頂点において、Ｃ’内のその隣接辺の長さの和をＣ内のこの長さの和で割った比として計算され、その後、線形補間によってｕにわたって連続的に定義される。
【００５９】
制御曲線上の各点およびその１リング近隣点の変形された座標が、これで決定される。この時点で、変形モジュール１０８の操作は、制御曲線上の各点におけるＴiを計算することに進む。変形モジュール１０８は、法線と、この法線による１つの辺ベクトルの直投影（ｐｅｒｐｅｎｄｉｃｕｌａｒｐｒｏｊｅｃｔｉｏｎ）としての接ベクトルとを計算することによって、回転を定義する。法線は、メッシュ点ｉの周りの面法線（ｆａｃｅｎｏｒｍａｌ）の面面積によって重み付けされた線形結合として計算される。回転は、四元数（ｑｕａｔｅｒｎｉｏｎ）として表され、これは、回転角が１８０度より小さいことを意味する。Ｔiのスケール係数は、ｓ（ｕp）によって与えられる。
【００６０】
その後、変換は、変形箇所から離れるにつれて減衰する変形強度フィールドｆ（ｐ）（例えば、図８の画像（ｂ）を参照）を介して、制御曲線からすべてのグラフ点ｐに伝播させられる。一定、線形、かつガウス形の強度フィールドが、選択されることができ、これは、ｐから曲線までの最短辺経路（離散測地距離（ｄｉｓｃｒｅｔｅｇｅｏｄｅｓｉｃ ｄｉｓｔａｎｃｅ））に基づいている。
【００６１】
一実施では、変形モジュール１０８は、ｐに最も近い制御曲線上の点ｑpからの回転およびスケーリングをｐに割り当てることによって、簡単な伝播方式を実施する。より滑らかな結果は、最も近い頂点の代わりに制御曲線上のすべての頂点にわたって重み付け平均を計算することによって得られる。距離の逆数
【００６２】
【数７】
【００６３】
または
【００６４】
【数８】
【００６５】
などのガウス関数によって重み付けを行う。そのようなガウス関数は、システム１００において良好に機能する。
【００６６】
【数９】
【００６７】
は、ｐからｑまでの離散測地距離を表す。項σは、ガウス形の幅を制御する。複数の曲線間の重み付けも、四元数およびスケールが複数の曲線にわたって累積されることを除いて同様である。
【００６８】
点ｐにおける最終変換行列は、
【００６９】
【数１０】
【００７０】
であり、ここで、
【００７１】
【数１１】
【００７２】
は、ｐの重み付け平均変換である。この公式は、強度フィールドを使用して、その変換を恒等変換と単純に混合する。したがって、ラプラス座標は、変形の影響領域の外では、それらの元の（静止）状態に接近する。
【００７３】
従来の伝播方式とは対照的に、変形モジュール１０８によって実施される伝播方式は、各グラフ頂点の変換を計算し、その変換を頂点のラプラス座標に適用する。加えて、いくつかの従来の技法は一般に、各三角形の変換を計算し、それを三角形の頂点に適用する。しかし、各三角形を独立に変換することは、メッシュ内の近隣三角形からそれを切断する。ポアソン式は、各三角形の向きおよびスケールを最小２乗の意味で保存するように、三角形を一緒につなぎ戻す。これの体積領域への拡張は、四面体メッシュを必要とする。
【００７４】
変形箇所において変換を計算し、その変換を変形箇所から遠く伝播させる代わりに、従来のメッシュ変形技法は、点の局所近傍を静止状態から変形された状態に移す未知の最小２乗最適変換を定義することによって、追加の自由度を導入する。定義された変換は一般に、局所詳細の喪失を防止するために、回転およびスケーリングに制限される。２次のままであり、したがって、容易に解くことができるシステムの場合、回転は、小角近似（ｓｍａｌｌ−ａｎｇｌｅａｐｐｒｏｘｉｍａｔｉｏｎ）を使用して定義される。この従来の技法は、大規模な変形に対しては貧弱な近似を提供し、その後、より複雑な反復的改善を必要とする。
【００７５】
〈例示的な重み付け方式〉
メッシュラプラシアンＬMについて、変形モジュール１０８は、余接重み（ｃｏｔａｎｇｅｎｔ ｗｅｉｇｈｔ）
ｗij∝（ｃｏｔαij＋ｃｏｔβij）
を用いる重み付け方式を利用し、ここで、αij＝∠（ｐi，ｐj-1，ｐj）、βij＝∠（ｐi，ｐj+1，ｐj）である。
【００７６】
グラフラプラシアンＬG'について、変形モジュール１０８は、２次プログラミング問題を解くことによって重みを計算する。各グラフ頂点ｉについて独立に、変形モジュール１０８は、重みｗijを得るために、次の問題を解く（明瞭にするため、下付き文字ｉは削除されている）。
【００７７】
【数１２】
【００７８】
上記の式を参照すると、第１のエネルギー項は、最小の大きさのラプラス座標を生成する重みを得ようとする。第２の項は、スケール依存のアンブレラ作用素（ｕｍｂｒｅｌｌａｏｐｅｒａｔｏｒ）に基づいており、この作用素は、辺長に反比例する重みを選ぶ（ｐｒｅｆｅｒ）。パラメータλは、これら２つの目的のバランスを取り、一方、パラメータξは、小さな重みを防止する。この実施では、λおよびξは共に、０．０１に等しく設定される。
【００７９】
図９は、一様（ａ）、辺長の逆数（ｂ）、および熱核（ｈｅａｔ ｋｅｒｎｅｌ）（平方距離の減衰指数関数）（ｃ）を含む、重み付け方式の例示的な比較を示している。これらの例示的な比較に示されるように、画像（ｄ）に示されるシステム１００の変形モジュールによって実施される重み付け方式は、その他の重み付け方式からの結果よりも滑らかかつ一様である。
【００８０】
〈例示的な２次エネルギー最小化〉
新しいラプラス座標を与えると、変形モジュール１０８は、次の式を解くことによって、式（３）の２次エネルギーを最小化する。
ＬM（ｐ’i）＋βＬG'（ｐ’i）＝ε’i＋βδ’i，ｉ∈１，．．．，ｎ
βＬG'（ｐ’i）＝βδ’i，ｉ∈ｎ＋１，．．．，Ｎ
αｐ’i＝αｑ’i，ｉ∈１，．．．，ｍ
これは、疎線形系、Ａｘ＝ｂである。行列Ａは、変形前のグラフにのみ依存するが、ｂは、現在のラプラス座標および位置制約にも依存する。したがって、Ａは、変形モジュール１０８が、メッシュまたはグラフと制御点とを取り換えない限り固定されるが、ｂは、対話的変形の間常に変化する。したがって、変形モジュール１０８は、ＬＵ分解（ＬＵｄｅｃｏｍｐｏｓｉｔｉｏｎ）を使用して、Ａ-1を事前計算し、Ａ-1ｂを得るために、動的に後退代入（ｂａｃｋ ｓｕｂｓｔｉｔｕｔｉｏｎ）ステップを実行する。
【００８１】
〈例示的な多重解像度操作〉
多重解像度（ｍｕｌｔｉ−ｒｅｓｏｌｕｔｉｏｎ）編集が、特に超大規模モデルについて、微分方法を加速するために使用されることができる。例えば、図２のスタンフォードアルマジロ（Ｓｔａｎｆｏｒｄａｒｍａｄｉｌｌｏ）モデルは、１７０Ｋの頂点を含む。変形モジュール１０８は、そのモデルのボリュメトリックグラフを生成するとき、線形系において解かれるべき頂点としての変数をほぼ６倍多く生成する。そのような大規模システムを解くことは、対話的システムにとって、計算的にコストが高い。一実施では、計算コストを減少させるため、変形モジュール１０８は、より少数の頂点（例えば、アルマジロの場合は１５Ｋ）を有する簡略化されたメッシュを生成する。その後、ボリュメトリックグラフ１１８が、簡略化されたメッシュから生成される。メッシュの簡略化表現を変形した後、変形モジュール１０８は、変形された高解像度メッシュを得るために、詳細を追加し戻す。
【００８２】
〈２−Ｄ曲線からの例示的な変形〉
システム１００の対話の基本モードは、次のようである。ユーザは最初に、最短辺（ダイクストラ（Ｄｉｊｋｓｔｒａ））経路によって連結されるメッシュ頂点の系列を選択することによって、メッシュ表面１１６上で制御曲線１２０を指定する。この３−Ｄ曲線は、その後に編集され得る２−Ｄ曲線を得るために、１つまたは複数の平面（射影平面）に射影される。編集後、変更された２−Ｄ曲線は、変形された制御曲線を得るために、３−Ｄに射影し戻され、その制御曲線が、先のセクションの変形の基礎を形成する。
【００８３】
〈例示的な曲線射影〉
元の制御曲線を与えると、変形モジュール１０８は、元の制御曲線の平均法線および主ベクトルに基づいて、自動的に射影平面を選択する。変形モジュール１０８は、曲線の頂点にわたる主成分分析（ＰＣＡ：ｐｒｉｎｃｉｐａｌｃｏｍｐｏｎｅｎｔ ａｎａｌｙｓｉｓ）からの最大固有値に対応する２つの固有ベクトルとして主ベクトルを計算する。大部分の場合、平均法線と第１の主ベクトルの外積が、満足のゆく平面を提供する。平均法線ベクトルの長さが、閉平面曲線（ｃｌｏｓｅｄｐｌａｎａｒ ｃｕｒｖｅ）用として小さい場合、２つの主ベクトルが代わりに利用される。この実施では、ユーザは、射影を直接選択することも、またはシステム１００によって選択された射影を変更することもできる。
【００８４】
〈例示的な曲線編集〉
射影２−Ｄ曲線は、編集を複雑にするオリジナルメッシュ１１６から、幾何学的詳細を継承する。多重解像度曲線編集は、Ｂスプライン曲線用の１つの解法を提供する。変形モジュール１０８は、ラプラス座標に基づいて離散曲線用の編集操作を実施する。曲線頂点のラプラス座標は、頂点の位置と頂点の２つの隣接点の平均位置との間の差であり、終端頂点の場合は単一隣接点との間の差である。
【００８５】
編集される離散２−Ｄ曲線が、Ｃで示される。３次Ｂスプライン曲線Ｃbが、Ｃの低周波数を表す、Ｃに対する最小２乗適合（ｌｅａｓｔ−ｓｑｕａｒｅｓｆｉｔ）として、最初に計算される。その後、Ｃdで示されるＣbの離散バージョンが、比例弧長写像（ｐｒｏｐｏｒｔｉｏｎａｌ ａｒｃ−ｌｅｎｇｔｈ ｍａｐｐｉｎｇ）を使用して、Ｃの各頂点をＣbに写像することによって計算される。単純なＢスプライン曲線Ｃbが、これで都合よく編集されることができる。編集後、変形モジュール１０８は、変更されたＢスプライン曲線Ｃ’bと、新しい離散バージョンＣ’dとを得る。これらの曲線は、ユーザの所望の変形を示すが、元の曲線の詳細を欠いている。元の曲線の詳細を回復するため、変形モジュール１０８は、Ｃの各頂点において、その位置をＣdからＣ’dに写像する一意な回転およびスケーリングを識別する。この変換をＣ上のラプラス座標に適用することと、単純な曲線グラフにわたって（第２の点制約項を持たない）式（２）を解くことが、新しい曲線Ｃ’の生成をもたらす。この新しい曲線は、Ｃの詳細を保存するが、ユーザの粗いスケール変更に従う。基本的に、これは、メッシュを変形するための局所変換「伝播」の自明なバージョンであるが、曲線の場合は、それは、点毎に独立に定義されることができ、伝播される必要がない。
【００８６】
このアルゴリズムは、曲線類似（ｃｕｒｖｅ ａｎａｌｏｇｙ）として提出され、すなわち、１対の元の曲線ＣsおよびＣ’sと、目標曲線Ｃを与えると、ＣとＣ’の間の関係がＣsとＣ’sの間の関係に類似するように、新しい曲線Ｃ’を生成する。従来のメッシュ変形操作は、頂点を直接変換することができるが、変形モジュール１０８は、頂点の対応する差分座標を、曲線全体にわたってより一様に分散された誤差に変換する。
【００８７】
最初に、Ｃbは、曲線の端点に２つのノット（ｋｎｏｔ）を有する。ユーザは、より詳細なレベルで編集を実行するために、ノットを追加することができる。システム１００は、２つの編集モードをサポートし、一方は、元の曲線Ｃbに対する粗いスケールの適合を操作し、他方は、まったく新しい曲線をスケッチする。後者の場合、スケッチされた曲線と制御曲線の間の対応は、デフォルトでは、弧長によって達成される。この実施では、ユーザが、２つの曲線の間の一連の対応点を指定することもできる。
【００８８】
〈２−Ｄアニメからの例示的な変形再標的化〉
一実施では、システム１００が２−Ｄアニメの変形を３−Ｄメッシュ１１２に再標的化（ｒｅ−ｔａｒｇｅｔ）することは、システム１００の２−Ｄスケッチベースの変形の例示的な直接の応用である。この目的で、ユーザは、メッシュ１１６上で１つまたは複数の３−Ｄ制御曲線１２０を、それらの射影平面と共に指定し、各曲線について、メッシュ１１６の変形を推進するのに使用されるアニメ画像系列内の一連の２−Ｄ曲線１２０を指定する。
【００８９】
図９は、２−Ｄ画像からの変形再標的化のための例示的な３−Ｄおよび２−Ｄ制御曲線指定を示している。より具体的には、制御曲線の組９０２（すなわち、９０２−１ａから９０２−３ｂ）は、３−Ｄメッシュ上で指定され、制御曲線の組９０４（すなわち、９０４−１ａから９０４−３ｂ）は、２−Ｄ画像上で指定される。（例示的な説明の目的で、２−Ｄおよび３−Ｄ制御曲線は、図１の指定された点１２０として示されている）。
【００９０】
Ｃiが３−Ｄ制御曲線９０２の射影であり、アニメ系列内のそれに対応する曲線９０４がＣi,j、ｊ∈｛１，．．．，ｋ｝であると仮定する。インデックスｉは、腕および脚などのモデルの異なる部分を動かす、異なる制御曲線に対応する。インデックスｊは、フレームインデックスであり、同じ制御曲線は、各フレーム毎に対応するアニメ曲線を有する。変形モジュール１０８は、Ｃiを連続するＣi,jに写像する変形系列を自動的に導出する。これらの変形操作に関して、あらゆるフレームで最初から変形を生成する必要はない。一実施では、ユーザは、すべてのフレーム系列について制御曲線を指定する代わりに、僅か数個の主要フレームを選択し、選択された主要フレームについてのみアニメ制御曲線を指定してもよい。変形モジュール１０８は、主要フレーム間を補間するために、差分座標に基づいて自動補間操作を実施する。例えば、同じ連結度を有する２つのメッシュＭおよびＭ’が存在すると仮定する。これら２つのメッシュは、２つの主要フレームにおける変形されたメッシュ１１２を表す。
【００９１】
変形モジュール１０８は、２つのメッシュ上の各頂点のラプラス座標を計算することによって開始する。変形モジュール１０８は、各頂点ｐの局所近傍における回転およびスケーリングを計算し、ラプラス座標をＭにおける位置からＭ’に移す（例えば、「ボリュメトリックグラフの例示的な変形」と題する上記のセクションを参照）。変換をＴpによって示す。恒等変換からＴpへの各変換を経時的に補間することによって、ＭからＭ’へと滑らかに変化するラプラス座標を得る。この時点で、変形モジュール１０８は、ＭからＭ’へのメッシュの系列を提供するために、式（２）を解く。
【００９２】
２−Ｄアニメ曲線は、変形された曲線がどのように単一平面に射影されるかを指定するに過ぎず、平面に垂直な形状は指定されずに残される。この点に鑑みて、システム１００は、ユーザが、必要であれば、これらの追加の自由度を指定するために、その他の射影平面を選択することを可能にする。
【００９３】
図１０は、システム１００のボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形と比較された、従来の大規模メッシュ変形技法のさらなる例示的な比較を示している。より具体的には、上の行は、左から右に、オリジナルメッシュの画像と、変形を編集するポアソンメッシュの結果を示す例示的な画像と、ボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形の例示的な結果を示す画像とをそれぞれ示している。第２または下の行は、上の行の直上の画像に関連付けられた変形領域の拡大部分を示している。すなわち、列（ａ）の画像は、オリジナルメッシュ１１６と関連付けられ、列（ｂ）の画像は、ポアソンメッシュ編集を使用して変形されたオリジナルメッシュの結果に対応し、列（ｃ）の画像は、システム１００のボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形を使用して変形されたオリジナルメッシュの結果に対応する。
【００９４】
〈例示的な手順〉
図１１は、ボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形のための例示的な手順１１００を示している。解説および例示的な説明の目的で、この手順の動作は、図１の構成要素に関して説明される。構成要素の参照番号の左端の数字は、その構成要素が最初に出現した特定の図面を識別する。加えて、図１１は、特定の順序で手順１１００の動作を提示するが、手順の任意の特定のブロックに関連付けられた動作は、異なる順序で実施されてもよい。例えば、ブロック１１０４の動作は、ブロック１１０２の動作の前に実施されてもよいなどである。
【００９５】
ブロック１１０２において、変形モジュール１０８は、オリジナルメッシュ１１６からボリュメトリックグラフ１１８を構成する。一実施では、変形モジュール１０８は、中間的な内側および外側グラフデータ構造を使用して、ボリュメトリックグラフを構成する。内側グラフは、オリジナルメッシュ１１６の内側に存在するように構成された単純格子である。内側グラフは、オリジナルメッシュの点と、導出された点とを含み、大規模メッシュ変形操作中の大きな体積変化を防止するために、変形モジュール１０８によって使用される。一実施では、変形モジュール１０８は、オリジナルメッシュの各頂点をその法線とは反対の方向にずらす簡略化エンベロープを使用して、内側グラフを構成する。一実施では、変形モジュール１０８は、オリジナルメッシュの各頂点をオリジナルメッシュの表面の外側に向かって反復的にずらすことによって、局所自己交差を防止するように、外側グラフを構成する。変形モジュール１０８は、ボリュメトリックグラフを生成するために、内側および外側グラフと、変形の対象とされるオリジナルメッシュ１１６との間の連結を構築する。
【００９６】
ブロック１１０４において、変形モジュール１０８は、ユーザが、１組の３−Ｄ制御曲線１２０を指定することを可能にする。各３−Ｄ制御曲線は、オリジナルメッシュ１１６上の１組の点を識別する。一実施では、変形モジュール１０８は、表示デバイス上にユーザインタフェース（ＵＩ）を提示する。オリジナルメッシュ１１６の３−Ｄ表示が、ＵＩによってユーザに提示される。マウスまたはその他のタイプのポインティングデバイスを使用して、ユーザは、３−Ｄ制御曲線１２０を定義するオリジナルメッシュ１１６上の１組の点を選択する。
【００９７】
ブロック１１０６において、変形モジュール１０８は、ユーザが、変形された制御曲線１２４を生成するために、３−Ｄ制御曲線１２０をそれぞれの２−Ｄ制御曲線１２０として編集することを可能にする。変形された制御曲線１２４は、オリジナルメッシュ１１６がどのように変形されるかを示す。この実施では、ユーザは、次のようにして、オリジナルメッシュ１１６がどのように変形されるかを指定する。変形モジュール１０８は、指定された３−Ｄ制御曲線１２０をＵＩ内の射影平面上に２−Ｄ制御曲線１２０として射影する。ユーザは、提供されたＵＩを使用して、射影された２−Ｄ制御曲線１２０を操作することによって、オリジナルメッシュ１１６を変形する。これは、３−Ｄ制御曲線１２０内の指定された点が、定義された変形の結果として、どこに動かされるかを示す。例えば、一実施では、ユーザは、マウスおよび／またはグラフィックスペンなどのポインティングデバイスを用いて２−Ｄ制御曲線を選択することによって、射影された２−Ｄ制御曲線を操作し、２−Ｄ制御曲線１２０を変更する。例えば、ユーザは、目標曲線（すなわち、変形）を表す新しい曲線を引き、ＵＩなどによって２−Ｄ曲線上に提示されるＢスプライン制御点を使用して、２−Ｄ曲線を直接編集することもできる。
【００９８】
ブロック１１０８において、変形モジュール１０８は、グラフ内の各点とその近隣点の平均との間の差としてボリュメトリックディテールを符号化するように、ボリュメトリックグラフ１１８のラプラシアン（すなわち、ボリュメトリックグラフ・ラプラシアン１１４）を生成する。これらのボリュメトリックディテールは、体積の不自然な変化を防止する体積制約を課すために、変形操作中に利用される。これらのボリュメトリックディテールは、オリジナルメッシュ１１６の外側の近距離にある点も含み、それらは、体積の局所自己交差を実質的に防止するために、変形操作中に使用される。
【００９９】
ブロック１１１０において、変形モジュール１０８は、変形された制御曲線１２４に基づいて、オリジナルメッシュ１１６を変形する。このようにして、システム１００は、ユーザが大規模メッシュ変形を生成することを可能にする、曲線ベースの変形システムを提供する。
【０１００】
〈例示的な動作環境〉
図１２は、ボリュメトリックグラフラ・プラシアンを使用する大規模メッシュ変形が完全または部分的に実施され得る、適切なコンピューティング環境の一例を示している。例示的なコンピューティング環境１２００は、図１の例示的なシステムおよび図１１の例示的な動作にとって適切なコンピューティング環境の一例に過ぎず、本明細書で説明されたシステムおよび方法の使用範囲または機能に関するどのような限定も示唆しようとするものではない。コンピューティング環境１２００は、コンピューティング環境１２００に示された構成要素のいずれか１つまたは組み合わせに関して、どのような依存性または必要性も有さないと解釈されるべきである。
【０１０１】
本明細書で説明された方法およびシステムは、多数のその他の汎用または専用コンピューティングシステム、環境、または構成と共に動作可能である。使用に適し得るよく知られたコンピューティングシステム、環境、および／または構成の例は、パーソナルコンピュータ、サーバコンピュータ、マルチプロセッサシステム、マイクロプロセッサベースシステム、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、および上記のシステムまたはデバイスのいずれかを含む分散コンピューティング環境などを、これらに限定することなく含む。フレームワークのコンパクト版またはサブセット版が、ハンドヘルドコンピュータまたはその他のコンピューティングデバイスなど、リソースが限られたクライアントで実施されてもよい。本発明は、必ずしも必要ではないが、通信ネットワークを介して結合されるリモート処理デバイスによってタスクが実行される、分散コンピューティング環境で実施されることができる。分散コンピューティング環境では、プログラムモジュールは、ローカルおよびリモート両方のメモリ記憶デバイスに配置されてよい。
【０１０２】
図１２を参照すると、ボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形を提供する例示的なシステムは、例えば図１のシステム１００を実施する、コンピュータ１２１０の形態の汎用コンピューティングデバイスを含む。コンピュータ１２１０の構成要素は、処理ユニット１２２０、システムメモリ１２３０、およびシステムメモリを含む様々なシステム構成要素を処理ユニット１２２０に結合するシステムバス１２２１を、これらに限定することなく含むことができる。システムバス１２２１は、メモリバスまたはメモリコントローラ、周辺バス、および様々なバスアーキテクチャのいずれかを使用するローカルバスを含む、複数のタイプのバス構造のいずれかとすることができる。限定することなく例を挙げると、そのようなアーキテクチャは、業界標準アーキテクチャ（ＩＳＡ）バス、マイクロチャネルアーキテクチャ（ＭＣＡ）バス、拡張業界標準アーキテクチャ（ＥＩＳＡ）バス、ビデオ電子規格協会（ＶＥＳＡ）ローカルバス、およびメザニンバスとしても知られる周辺コンポーネント相互接続（ＰＣＩ）バスを含むことができる。
【０１０３】
コンピュータ１２１０は一般に、様々なコンピュータ可読媒体を含む。コンピュータ可読媒体は、揮発性および不揮発性媒体、着脱可能および固定式媒体を含む、コンピュータ１２１０によってアクセス可能な任意の利用可能な媒体とすることができる。限定することなく例を挙げると、コンピュータ可読媒体は、コンピュータ記憶媒体および通信媒体を含むことができる。コンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、またはその他のデータなどの情報を記憶するための任意の方法または技法で実施された、揮発性および不揮発性、着脱可能および固定式媒体を含む。コンピュータ記憶媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ、もしくはその他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）、もしくはその他の光ディスク記憶、磁気カセット、磁気テープ、磁気ディスク記憶、もしくはその他の磁気記憶デバイス、または所望の情報を記憶するのに使用でき、コンピュータ１２１０によってアクセス可能なその他の任意の媒体を、これらに限定することなく含む。
【０１０４】
通信媒体は一般に、コンピュータ可読命令、データ構造、プログラムモジュール、またはその他のデータを、搬送波またはその他のトランスポート機構などの変調データ信号中に具現し、任意の情報伝達媒体を含む。「変調データ信号」という用語は、信号中に情報を符号化するような仕方で設定または変更された１つまたは複数の特徴を有する信号を意味する。限定することなく例を挙げると、通信媒体は、有線ネットワークまたは直接配線接続などの有線媒体、ならびに音響、ＲＦ、赤外線、およびその他の無線媒体などの無線媒体を含む。上記の任意のものの組み合わせも、コンピュータ可読媒体の範囲内に含まれるべきである。
【０１０５】
システムメモリ１２３０は、読み取り専用メモリ（ＲＯＭ）１２３１およびランダムアクセスメモリ（ＲＡＭ）１２３２などの、揮発性および／または不揮発性メモリの形態のコンピュータ記憶媒体を含む。起動中などにコンピュータ１２１０内の要素間で情報を伝送する助けをする基本ルーチンを含む基本入出力システム１２３３（ＢＩＯＳ）は一般に、ＲＯＭ１２３１に記憶される。ＲＡＭ１２３２は一般に、処理ユニット１２１０から直ちにアクセス可能な、かつ／または処理ユニット１２１０が現在それに基づいて動作している、データおよび／またはプログラムモジュールを含む。限定することなく例を挙げると、図１２は、オペレーティングシステム１２３４、アプリケーションプログラム１２３５、その他のプログラムモジュール１２３６、およびプログラムデータ１２３７を示している。
【０１０６】
コンピュータ１２１０は、その他の着脱可能／固定式、揮発性／不揮発性コンピュータ記憶媒体も含むことができる。例としてのみ挙げると、図１２は、固定式の不揮発性磁気媒体からの読み取りまたはそうした媒体への書き込みを行うハードディスクドライブ１２４１、着脱可能な不揮発性磁気ディスク１２５２からの読み取りまたはそうしたディスクへの書き込みを行う磁気ディスクドライブ１２５１、およびＣＤ−ＲＯＭまたはその他の光媒体などの着脱可能な不揮発性光ディスク１２５６からの読み取りまたはそうしたディスクへの書き込みを行う光ディスクドライブ１２５５を示している。例示的な動作環境で使用され得るその他の着脱可能／固定式、揮発性／不揮発性コンピュータ記憶媒体は、磁気テープカセット、フラッシュメモリカード、デジタル多用途ディスク、デジタルビデオテープ、ソリッドステートＲＡＭ、およびソリッドステートＲＯＭなどを、これらに限定することなく含む。ハードディスクドライブ１２４１は一般に、インタフェース１２４０などの固定式メモリインタフェースを介してシステムバス１２２１に接続され、磁気ディスクドライブ１２５１および光ディスクドライブ１２５５は一般に、インタフェース１２５０などの着脱可能メモリインタフェースによってシステムバス１２２１に接続される。
【０１０７】
上で説明された図１２に示されるドライブおよびそれに関連するコンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、およびその他のデータの記憶を、コンピュータ１２１０に提供する。図１２では、例えば、ハードディスクドライブ１２４１は、オペレーティングシステム１２４４、アプリケーションプログラム１２４５、その他のプログラムモジュール１２４６、およびプログラムデータ１２４７を記憶するとして示されている。これらの構成要素は、オペレーティングシステム１２３４、アプリケーションプログラム１２３５、その他のプログラムモジュール１２３６、およびプログラムデータ１２３７と同じであることも、または異なることもできることに留意されたい。オペレーティングシステム１２４４、アプリケーションプログラム１２４５、その他のプログラムモジュール１２４６、およびプログラムデータ１２４７は、それらが少なくとも異なるコピーであることを示すために、ここでは異なる番号を与えられている。
【０１０８】
ユーザは、キーボード１２６２、および一般にマウス、トラックボール、またはタッチパッドと呼ばれるポインティングデバイス１２６１などの入力デバイスを介して、コンピュータ１２１０にコマンドおよび情報を入力することができる。その他の入力デバイス（図示されず）は、マイクロフォン、ジョイスティック、グラフィックスペンおよびパッド、衛星放送受信アンテナ、またはスキャナなどを含むことができる。上記およびその他の入力デバイスはしばしば、システムバス１２２１に結合されるユーザ入力インタフェース１２６０を介して処理ユニット１２２０に接続されるが、パラレルポート、ゲームポート、またはユニバーサルシリアルバス（ＵＳＢ）などのその他のインタフェースおよびバス構造によって接続されてもよい。
【０１０９】
モニタ１２９１またはその他のタイプの表示デバイスも、ビデオインタフェース１２９０などのインタフェースを介して、システムバス１２２１に接続される。モニタに加えて、コンピュータは、プリンタ１２９６およびオーディオデバイス１２９７などのその他の周辺出力デバイスも含むことができ、それらは、出力周辺インタフェース１２９５を介して接続されることができる。
【０１１０】
コンピュータ１２１０は、リモートコンピュータ１２８０などの１つまたは複数のリモートコンピュータへの論理コネクションを使用して、ネットワーク環境で動作する。リモートコンピュータ１２８０は、パーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ピアデバイス、またはその他の共通ネットワークノードであってよく、その具体的な実装に応じて、コンピュータ１２１０に関連して上で説明された要素の多くまたは全部を含むことができるが、図１２には、メモリ記憶デバイス１２８１のみが示されている。図１２に示された論理コネクションは、ローカルエリアネットワーク（ＬＡＮ）１２７１およびワイドエリアネットワーク（ＷＡＮ）１２７３を含むが、その他のネットワークを含んでもよい。そのようなネットワーク環境は、オフィス、企業規模のコンピュータネットワーク、イントラネット、およびインターネットにおいて一般的である。
【０１１１】
ＬＡＮネットワーク環境で使用される場合、コンピュータ１２１０は、ネットワークインタフェースまたはアダプタ１２７０を介して、ＬＡＮ１２７１に接続される。ＷＡＮネットワーク環境で使用される場合、コンピュータ１２１０は一般に、インターネットなどのＷＡＮ１２７３を介して通信を確立するためのモデム１２７２またはその他の手段を含む。モデム１２７２は、内蔵でもまたは外付けでもよく、ユーザ入力インタフェース１２６０またはその他の適切な機構を介して、システムバス１２２１に接続されることができる。ネットワーク環境では、コンピュータ１２１０に関連して示されたプログラムモジュールまたはその部分は、リモートメモリ記憶デバイスに記憶されることができる。限定することなく例を挙げると、図１２は、メモリデバイス１２８１上に存在するとして、リモートアプリケーションプログラム１２８５を示している。示されたネットワークコネクションは、例示的なものであり、コンピュータ間の通信リンクを確立するその他の手段が使用されてもよい。
【０１１２】
〈結論〉
従来の差分領域メッシュ変形技法は、メッシュが変形される際に、表面詳細を保存するが、そのような既存の技法は一般に、変形が大規模である場合、好ましくないピンチング（ｐｉｎｃｈｉｎｇ）および交差アーチファクトを生み出す。図１のシステム１００は、ボリュメトリックグラフ・ラプラシアンによって表されるボリュメトリックディテールを保存することによって、これらの問題に対処する。この解決策は、複雑な物体をソリッドメッシュする複雑さを回避する。ボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形のためのシステムおよび方法は、構造的特徴および／または方法的操作および動作に特有の言葉で説明されたが、添付の特許請求の範囲において確定される実施は、必ずしも説明された特定の特徴または動作に限定されないことは理解されよう。むしろ、システム１００の特定の特徴および操作は、特許請求される主題を実施する例示的な形態として開示されている。
【技術分野】
【０００１】
本発明は、メッシュ変形の技術に関する。
【背景技術】
【０００２】
メッシュ変形（ｍｅｓｈ ｄｅｆｏｒｍａｔｉｏｎ）は、コンピュータモデリングおよびアニメーションの様々な応用例において役立つ。例えば、メッシュ変形は、アーティストが３次元（３−Ｄ）キャラクタの様式化されたボディ形状および変形を形作るのを手助けするのに役立つ。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかし、しなやかで非常に誇張された動作を実行するキャラクタに見出されるような大規模な変形は、今日も課題として残されている。既存のメッシュ変形技法は、不自然な体積変化を伴う信じがたい結果をしばしば生み出す。
【課題を解決するための手段】
【０００４】
この要約は、以下の詳細な説明においてさらに説明される概念の抜粋を簡潔な形式で紹介するために提供される。この要約は、特許請求される主題の主要な特徴または必須の特徴を特定することを意図しておらず、特許請求される主題の範囲を決定する際の助けとして使用されることも意図していない。
【０００５】
上記の事柄に鑑みて、ボリュメトリックグラフ・ラプラシアン（ｖｏｌｕｍｅｔｒｉｃｇｒａｐｈ Ｌａｐｌａｃｉａｎ：体積グラフラプラシアン）を使用する大規模メッシュ変形が説明される。一態様では、情報がユーザから受け取られ、この場合、その情報は、オリジナルメッシュ（元のメッシュ）がどのように変形されるかを示す。その後、オリジナルメッシュは、その情報と、オリジナルメッシュから生成されたボリュメトリックグラフ（体積グラフ）への体積微分演算子（ｖｏｌｕｍｅｔｒｉｃｄｉｆｆｅｒｅｎｔｉａｌ ｏｐｅｒａｔｏｒ）の適用とに基づいて、変形される。
【０００６】
図面において、構成要素の参照番号の左端の数字は、その構成要素が最初に出現した特定の図面を識別する。
【図面の簡単な説明】
【０００７】
【図１】ボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形のための例示的なシステムを示す図である。
【図２】従来の大規模メッシュ変形とボリュメトリックグラフ・ラプラシアン１１４を使用する大規模メッシュ変形との例示的な比較を示す図である。
【図３】例示的な大規模捻り変形結果を示す図である。
【図４】例示的な大規模曲げ変形結果を示す図である。
【図５】例示的なボリュメトリックグラフを示す図である。
【図６】ボリュメトリックグラフを構成するための例示的な操作を示す図である。
【図７】ボリュメトリックグラフにおける辺連結の例示的なタイプを示す図である。
【図８】例示的な曲線ベースの変形を示す図である。
【図９】一様、辺長の逆数、および熱核（平方距離の減衰指数関数）重み付け方式を含む重み付け方式の例示的な比較を示す図である。
【図１０】ボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形と比較された従来の大規模メッシュ変形技法の例示的な比較を示す図である。
【図１１】ボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形のための例示的な手順を示す図である。
【図１２】ボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形が完全または部分的に実施され得る適切なコンピューティング環境の一例を示す図である。
【発明を実施するための形態】
【０００８】
〈概要〉
ボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形は、ボリュメトリックグラフ・ラプラシアンを使用する、３−Ｄメッシュ上での大規模変形のための新規な技法を提供する。入力メッシュの内側の体積を表すグラフが、最初に構成される。グラフは、入力メッシュの内部のソリッドメッシング（ｓｏｌｉｄｍｅｓｈｉｎｇ）を形成する必要がない（体積ラプラス演算子（ｖｏｌｕｍｅｔｒｉｃ Ｌａｐｌａｃｉａｎ ｏｐｅｒａｔｏｒ）は、表面内部をメッシュすることなく、ボリュメトリックグラフに適用されることができる）。グラフの辺は、体積内の近隣点を単純に接続する。グラフのラプラシアンは、グラフ内の各点とその近隣点の平均との差として、ボリュメトリックディテール（体積詳細）を符号化する。変形中にこれらのボリュメトリックディテールを保存することが、体積の不自然な変化を防止する体積制約を課す。また、グラフ内には、メッシュの外側の近距離にある点も含まれる。これは、局所自己交差（ｌｏｃａｌｓｅｌｆ−ｉｎｔｅｒｓｅｃｔｉｏｎ）を回避する上で助けとなる。ボリュメトリックディテールの保存は、２次エネルギー関数（ｑｕａｄｒｉｃｅｎｅｒｇｙ ｆｕｎｃｔｉｏｎ）によって表される。２次エネルギー関数を最小化することが、最小２乗の意味において詳細を保存し、誤差を変形されたメッシュの全体にわたって一様に分散させる。２次エネルギー関数は、表面位置、詳細、または滑らかさを含む従来の制約とも組み合わされることができ、疎線形系（ｓｐａｒｓｅｌｉｎｅａｒ ｓｙｓｔｅｍ）を解くことによって効率的に最小化することができる。
【０００９】
図１から図１１を参照して以下でより詳細に説明されるように、ボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形が、２−Ｄ曲線ベースの変形システムにおいて実施され、初心者も熟練ユーザも等しく十分に満足できる変形を僅かな労力で生み出すことを可能にする。この新規なメッシュ変形技法は、３−Ｄモデルのスケルトンおよび基本姿勢を入力として必要とせず、広い範囲にわたるしなやかな変形を扱うことができる。一実施では、ボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形のためのシステムは、２−Ｄアニメキャラクタのしなやかで誇張された変形を３−Ｄメッシュに適用するために利用される。
【００１０】
〈例示的なシステム〉
必ずしも必要ではないが、ボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形は、パーソナルコンピュータなどのコンピューティングデバイスによって実行されるコンピュータプログラム命令という一般的な文脈において説明される。プログラムモジュールは一般に、特定のタスクを実行し、または特定の抽象データ型を実施する、ルーチン、プログラム、オブジェクト、コンポーネント、データ構造などを含む。システムおよび方法は、上述の文脈において説明されるが、これ以降で説明される行為および動作は、ハードウェアで実施されてもよい。
【００１１】
図１は、ボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形のための例示的なシステム１００を示している。この実施では、システム１００は、汎用コンピューティングデバイス１０２を含む。コンピューティングデバイス１０２は、パーソナルコンピュータ、ラップトップ、サーバ、および／またはハンドヘルドもしくはモバイルコンピューティングデバイス（例えば、セルラ電話、携帯情報端末）など、任意のタイプのコンピューティングデバイスを表す。
【００１２】
コンピューティングデバイス１０２は、プログラムモジュール１０４と、プログラムデータ１０６とを含む。プログラムモジュール１０４は、（ボリュメトリックグラフ・ラプラシアンを使用する）大規模メッシュ変形モジュール１０８（これ以降、しばしば「変形モジュール１０８」と呼ばれる）と、オペレーティングシステムなどのその他のプログラムモジュール１１０とを含む。変形モジュール１０８は、３−Ｄメッシュ１１６（オリジナルメッシュ：元のメッシュ）から生成されたボリュメトリックグラフ・ラプラシアン（ＶＧＬ）１１４上で大規模メッシュ変形１１２を生じさせるために、新規な技法を実施する。変形モジュール１０８は、ＶＧＬを利用して、ボリュメトリックディテールを３−Ｄ体積内の各点とグラフ内のその近隣点の平均との差として表す。ＶＧＬは、変形モジュール１０８が、差分領域（ｄｉｆｆｅｒｅｎｔｉａｌｄｏｍａｉｎ）技法を使用して表面詳細を保存することを可能にし、それによって、最小２乗最小化を用いて誤差を全体的に分散させることによって、視覚的に満足できる変形結果１１２を生み出す。メッシュ１１６の表面上の代わりに体積領域内で作業することによって、変形モジュール１０８は、ＶＧＬを利用して、効率的に体積制約を課し、それによって、不自然な体積変化および局所自己交差を回避する。
【００１３】
図２は、従来の大規模メッシュ変形と、ボリュメトリックグラフ・ラプラシアン１１４を使用する大規模メッシュ変形との例示的な比較を示している。より具体的には、画像２０２は、例示的なオリジナルメッシュ１１６を示す。画像２０４は、従来のポアソン編集メッシュ変形（Ｐｏｉｓｓｏｎｅｄｉｔｉｎｇ ｍｅｓｈ ｄｅｆｏｒｍａｔｉｏｎ）技法を使用してオリジナルメッシュ１１６を変形した例示的な結果を示す。画像２０６は、ボリュメトリックグラフ・ラプラシアン１１４を使用したオリジナルメッシュ１１６の大規模メッシュ変形の例示的な結果を示す。画像２０４の例に示されるように、ポアソンメッシュ編集を使用したオリジナルメッシュ１１６の変形は、特にモデルの右腿において不自然な収縮を引き起こす。
【００１４】
ボリュメトリックグラフ・ラプラシアン１１４を使用する場合、変形モジュール１０８は、２次エネルギー関数によって体積制約を表す。変形モジュール１０８は公式には、疎線形系によってこの関数を最小化し、その関数を（例えば、表面位置、表面詳細、表面の滑らかさに対する）その他の表面制約と組み合わせる。ボリュメトリックグラフ・ラプラシアン１１４を三角メッシュ（ｔｒｉａｎｇｕｌａｒｍｅｓｈ）に適用するため、変形モジュール１０８は最初に、ボリュメトリックグラフ１１８を構成するが、ボリュメトリックグラフは、オリジナルメッシュ１１６の点と、メッシュ１１６の内側に存在する単純格子（ｓｉｍｐｌｅｌａｔｔｉｃｅ）（グラフの内側）から以下で説明されるように導出される点とを含む。グラフの辺は、これらの点を接続する。これらのグラフの辺は、オリジナルメッシュ１１６の辺の上位集合である。グラフは、メッシュ１１６の内部のメッシング（四面体またはその他の有限要素への体積テッセレーション（ｖｏｌｕｍｅｔｒｉｃｔｅｓｓｅｌｌａｔｉｏｎ））を形成する必要がない。
【００１５】
ユーザは、オリジナルメッシュ１１６上の有限の点の集合１２０（１つまたは複数の制御曲線（ｃｏｎｔｒｏｌｃｕｒｖｅ））を識別することによって、変形を指定する。指定された点１２０は、曲線を定義し、これらの点１２０が結果の変形においてどこに移動するかを表す。例示的な説明の目的で、指定された点１２０は、この例では、曲線を識別する。変形モジュール１０８は、表面詳細を維持し、体積をほぼ保存しながら、指定された点１２０を指定された移動先に写像するために、最小値を取る２次エネルギー関数を生成する。
【００１６】
このようにして、変形モジュール１０８は、表面内部をメッシュすることなく、体積微分演算子をボリュメトリックグラフ１１８に適用することによって、大規模メッシュ変形の問題を解決する。対照的に、従来の微分手法は、表面演算子のみを考えた。表面から立体にこれらの演算子を拡張する素朴な方法は、物体内部の四面体メッシュにわたってそれらを定義することである。しかし、複雑な物体をソリッドメッシュすることは、困難なことで有名である。既存のメッシュ変形技法は一般に、幾何学的形状を再メッシュし、その連結度を混乱させ、それによって、メッシュ変形の共通要件を破る。ソリッドメッシングも、（例えば、四面体は反転しない、各内部頂点はその近隣点のビジュアルハル（ｖｉｓｕａｌｈｕｌｌ）内に留まるといった）多くの制約を伴う。そのような制約は、従来のメッシュ変形技法が、内部点を経済的に分散させ、局所自己交差を防止するために（システム１００によって実行される）「外部シェル（ｅｘｔｅｒｉｏｒｓｈｅｌｌ）」を追加することを、計算的に非実用的なものにする。
【００１７】
ボリュメトリックグラフ１１８を変形し、２−Ｄ曲線（指定された点１２０のそれぞれの部分）からの変形を実行する、変形モジュール１０８の例示的な動作が、今から説明される。
【００１８】
〈ボリュメトリックグラフの例示的な変形〉
Ｍ＝（Ｖ，Ｋ）を変形の対象とする三角メッシュ１１６とすると、Ｖは、ｎ個の点位置の集合（すなわち、オリジナルメッシュ１１６の点集合）、Ｖ＝｛ｐi∈Ｒ3｜１≦ｉ≦ｎ｝であり、Ｋは、すべての点連結度（ｖｅｒｔｅｘ ｃｏｎｎｅｃｔｉｖｉｔｙ）情報を含む抽象単体複体（ａｂｓｔｒａｃｔｓｉｍｐｌｉｃｉａｌ ｃｏｍｐｌｅｘ）である。例示的な説明の目的で、そのような点連結度情報は、「その他のデータ」１２２のそれぞれ部分として示される。Ｋには、頂点｛ｉ｝と、辺｛ｉ，ｊ｝と、面｛ｉ，ｊ，ｋ｝の３つのタイプが存在する。
【００１９】
〈抽象グラフ上でのラプラシアン変形〉
Ｇ＝（Ｐ，Ｅ）がグラフであると仮定すると、Ｐは、Ｎ個の点位置の集合、Ｐ＝｛ｐi∈Ｒ3｜１≦ｉ≦Ｎ｝であり、Ｅ＝｛｛ｉ，ｊ｝｜ｐiはｐjに接続される｝は、辺の集合である。グラフのラプラシアンは、多様体上のラプラス演算子に類似している。ラプラシアンは、グラフＧ内の各点ｐiと、その近隣点の１次結合との差
【００２０】
【数１】
【００２１】
を計算し、Ｎ（ｉ）＝｛ｊ｜｛ｉ，ｊ｝∈Ｅ｝は、隣接辺、ｗijは、点ｐjの重み、δiは、グラフＧ内の点ｐiのラプラス座標である。ＬGは、グラフＧのラプラス演算子と呼ばれる。重みｗijは、正数であり、Σj∈N(i)ｗij＝１を満足する。最も単純な重み付けは、一様な重み付け、ｗij＝１／｜Ｎ（ｉ）｜である。（変形モジュール１０８は、以下の「ボリュメトリックグラフの例示的な変形」と題するセクションで説明されるように、より複雑な重み付け方式を実施する）。
【００２２】
変形を制御するため、Ｎ個のメッシュ頂点の部分集合である制御曲線（すなわち、指定された点１２０）ｑi、ｉ∈｛１，．．．，ｍ｝として、入力変形位置がある。変形モジュール１０８は、グラフ内の各点ｉに関する新しい（変形された）ラプラス座標δ’iを計算するために、これらの指定された制御曲線を利用する。メッシュ頂点ｐ’iの変形された位置（例えば「その他のデータ」１２２を参照）は、その後、次の２次最小化問題を解くことによって得られる。
【００２３】
【数２】
【００２４】
式（２）の第１項は、局所的な細部の保存を表し、第２項は、ユーザによって直接指定された頂点１２０の位置を制約する。パラメータαは、これら２つの目的のバランスを取る。
【００２５】
変形されたラプラス座標は、次のように計算され、
δ’i＝Ｔiδi
ここで、δiは、式（１）で定義される静止姿勢のラプラス座標であり、Ｔiは、そのラプラス座標を変形姿勢に変換する。この実施では、異方性スケーリング（ａｎｉｓｏｔｒｏｐｉｃ ｓｃａｌｉｎｇ）を含む汎用変換Ｔiは、強力であり過ぎ、局所的な細部に「適合しない（ｆｉｔ ａｗａｙ）」ことがあり得る。これに対処するため、変形モジュール１０８は、Ｔiを回転と同方性スケールに制限する。
【００２６】
頂点の部分集合ｑiの変形された位置を与えると、よく知られた方法が、Ｔiを得るために使用されることができる。この実施では、変形モジュール１０８は、以下の「ボリュメトリックグラフの例示的な変形」と題するセクションで説明される方法を利用する。この方法は、局所変換を指定された変形領域からメッシュ全体に伝播させ（大規模メッシュ変形１１２を引き起こし）、変形部位から離れたその物自体に向かって変換を混合する。
【００２７】
グラフが三角メッシュである場合、グラフラプラシアンは、メッシュラプラシアンと一致する（この例では、メッシュまたは表面ラプラシアンが、オリジナルメッシュのラプラシアンである）。表面詳細を符号化するためにメッシュラプラシアンを使用すると、詳細な幾何学的構造は、広い範囲の編集操作にわたって保存される。しかし、大規模変形の場合、そのような方法は、不自然な体積変化（例えば、図３の画像（ａ）を参照）および／または局所自己交差（例えば、図４の画像（ａ）を参照）を呈する。
【００２８】
図３は、例示的な大規模な捻り変形結果を示している。より具体的には、図３の画像（ａ）は、ラプラシアン表面（Ｌａｐｌａｃｉａｎｓｕｒｆａｃｅ）に基づいた例示的な大規模な捻り変形を示す。図３の画像（ｂ）は、ポアソンメッシュに基づいた例示的な大規模な捻り変形を示す。画像（ｃ）は、変形モジュール１０８のＶＧＬ操作に基づいた例示的な大規模な捻り変形を示す。
【００２９】
図４は、例示的な大規模な曲げ変形結果を示している。より具体的には、図４の画像（ａ）は、ラプラシアン表面に基づいた例示的な大規模な曲げ変形を示す。図４の画像（ｂ）は、ポアソンメッシュに基づいた例示的な大規模な曲げ変形を示す。画像（ｃ）は、変形モジュール１０８のＶＧＬ操作に基づいた例示的な大規模な曲げ変形を示す。
【００３０】
オリジナルメッシュ１１６が不自然な体積変化および／または局所自己交差を減少させるように、変形モジュール１０８が、ボリュメトリックグラフ１１８を構成することによってどのように体積制約を課すかについて今から説明する。
【００３１】
〈ボリュメトリックグラフの例示的な構成〉
変形モジュール１０８は、大きな体積変化および局所自己交差を回避するが、大域的な自己交差の除去を保証しない。この実施では、大域的な自己交差は、ユーザによって対処される。変形モジュール１０８は、２つのタイプの中間グラフである内側グラフ（ｉｎｓｉｄｅｇｒａｐｈ）および外側グラフ（ｏｕｔｓｉｄｅ ｇｒａｐｈ）を利用して、ボリュメトリックグラフ１１８を構築する。内側グラフＧinは、メッシュ１１６の内部体積を満たし、大きな体積変化を防止し、一方、外側グラフＧoutは、局所自己交差を防止する。
【００３２】
図５は、例示的なボリュメトリックグラフ１１８を示している。より具体的には、ボリュメトリックグラフ５０２は、例示的なＧinを示し、ボリュメトリックグラフ５０４は、例示的なＧoutを示す。
【００３３】
Ｇinを得るための１つの方法は、表面メッシュ１１６の内部体積を四面体分割（ｔｅｔｒａｈｅｄｒａｌｉｚｅ）することである。しかし、四面体メッシュ生成は一般に、実施するのが相当に困難であり、高い計算コストがかかるうえ、言うまでもなく、そのようなメッシュ生成は一般に、堅実な方式で実施するのが困難である（例えば、モデルが複雑だと、一般に不恰好な四面体を生成する）。表面メッシュ１１６の内部体積を四面体分割する代わりに、変形モジュール１０８は、制限のより少ないボリュメトリックグラフを生成するために、相当に単純化された操作を実施する。
【００３４】
図６は、ボリュメトリックグラフ１１８を構成するための例示的なステップを示している。より具体的には、図６に示されたこの実施では、変形モジュール１０８は、次のようにしてボリュメトリックグラフ１１８を生成する。
【００３５】
・各頂点をその法線の反対方向にある距離だけずらすことによって、メッシュＭの内側シェル（ｉｎｎｅｒｓｈｅｌｌ）Ｍinを構成する。これは、例えば、図６の画像（ａ）に示されている。
【００３６】
・ＭinおよびＭを体心立法（ＢＣＣ：ｂｏｄｙ−ｃｅｎｔｅｒｅｄ ｃｕｂｉｃ）格子に埋め込む。外側の格子ノードを取り除く。これらの例示的な操作の結果は、例えば、図６の画像（ｂ）に示されている。
【００３７】
・Ｍ、Ｍin、および格子ノードの間の辺連結を構築する。この操作の結果は、例えば、図６の画像（ｃ）に示されている。
【００３８】
・辺消去（ｅｄｇｅ ｃｏｌｌａｐｓｅ）を使用してグラフを簡素化し、グラフを平滑化する。この操作の結果は、例えば、図６の画像（ｄ）に示されている。
【００３９】
この実施では、内側シェルＭinの目的は、格子サンプリング操作によって見落とされることがある（例えば、猫の尻尾のような）細い特徴内にさえも、内部点が挿入されるよう保証することである。内側シェルを計算するため、変形モジュール１０８は、簡略化エンベロープ（ｓｉｍｐｌｉｆｉｃａｔｉｏｎｅｎｖｅｌｏｐｅ）に基づいた操作を利用する。各反復において、変形モジュール１０８は、各頂点をその法線ベクトルとは反対に平均辺長の分数だけ動かすことを試みる。頂点を動かした後、変形モジュール１０８は、その隣接三角形を互いの交差およびモデルの残りとの交差についてテストする。交差が見出されない場合、これらの操作の結果が受け入れられる。それ以外の場合、操作の結果は拒絶され、頂点は元に戻される。すべての頂点が所望の距離だけ動かされたとき、またはもはや動かされ得ないとき、反復は終了する。
【００４０】
図７は、ボリュメトリックグラフにおける辺連結の例示的なタイプを示している。より具体的には、図７の画像（ａ）は、例示的な境界辺を示している。図７の画像（ｂ）は、例示的な内部辺を示している。これらの例に照らして、ＢＣＣ格子は、直交グリッドのすべての点とセルの中心とにノードを含むことが分かる（例えば、画像（ｂ））。ノード位置は、２つのインタレースグリッド（ｉｎｔｅｒｌａｃｅｄｇｒｉｄ）に属すると見なされ得る。この格子は、自然界では所望の剛性を有する結晶構造として生じる。この実施では、平均辺長を等しくするために、大きな間隔が設定される。
【００４１】
３つのタイプの辺連結が、初期ボリュメトリックグラフ１１８を形成する。第１に、変形モジュール１０８は、Ｍ内の各頂点をＭin内の対応する頂点に連結する（例えば、図６の画像（ａ））。各プリズム面のより短い対角線も同様に含められる。第２に、変形モジュール１０８は、ＢＣＣ格子の各内部ノードを他のインタレースグリッド内の８つの最近隣点と連結する（例えば、図７の画像（ｂ））。第３に、変形モジュール１０８は、ＭinとＢＣＣ格子のノードを連結する。Ｍinと交差し、Ｍin内に少なくとも１つのノードを有する、ＢＣＣ格子の各辺について、変形モジュール１０８は、Ｍin内のＢＣＣ格子ノードを、この交差に最も近いＭin内の点に連結する。
【００４２】
変形モジュール１０８は、グラフをより一様にするために、初期グラフ上で簡略化および平滑化操作を実施する。この目的で、変形モジュール１０８は、グラフ１１８の辺を長さの昇順で評価する。辺の長さが閾値（Ｍの平均辺長の半分）より小さい場合、それは辺の中点に縮小する。簡略化の後、数回の平滑化反復（発明者らの実施では３回）が実行され、各点がその近隣点の平均に動かされる。この実施では、簡略化も平滑化も、Ｍの頂点には適用されない。
【００４３】
外側グラフＧoutを構成するため（ボリュメトリックグラフ１１８の生成操作の一部）、変形モジュール１０８は、このボリュメトリックグラフを構成するために先に説明された、法線方向にずらす反復的方法（ｉｔｅｒａｔｉｖｅｎｏｒｍａｌ−ｏｆｆｓｅｔ ｍｅｔｈｏｄ）を利用するが、Ｍoutを形成するには、表面の内側ではなく外側に向かう。変形モジュール１０８は、ＭとＭinの間と同様に、ＭとＭoutの間の連結を構築する。
【００４４】
この実施では、ＧinおよびＧoutは共に、ユーザによって直接見られることのない（それぞれ「その他のデータ」１２２で表される）中間データ構造であり、ユーザ対話の後で廃棄されることに留意されたい。これらのデータ構造は、メッシュ表面の変形を制約するためにのみ役立つ。ＭinおよびＭoutとそれら自体との交差ならびにＭとの交差が、特に曲率の高い領域を含むメッシュ上で生じることがあり得るが、そのような交差は、対話システム１００において困難を引き起こさない。
【００４５】
ボリュメトリックグラフの例示的な変形
元の表面の詳細を保存することと体積を制約することの間のバランスを取るため、変形モジュール１０８は、式（２）のエネルギー関数の次の汎用形式への変更を利用し、
【００４６】
【数３】
【００４７】
ここで、グラフＧ内の最初のｎ個の点は、メッシュＭに属する。ＬMは、離散メッシュラプラス演算子である。Ｇ’は、Ｍに属する辺を取り除くことによって形成される、Ｇのサブグラフである。オリジナルメッシュＭ上の点について、ε’i（１≦ｉ≦ｎ）は、変形された座標系におけるメッシュラプラス座標である。ボリュメトリックグラフＧ’内の点について、δ’i（１≦ｉ≦Ｎ）は、変形された座標系におけるグラフラプラス座標である。したがって、エネルギーは、表面詳細の保存と、ユーザ選択の変形位置（指定された点１２０）の強制と、ボリュメトリックディテール／剛性の保存とに対応する、３つの項に分解される。
【００４８】
βは、表面詳細とボリュメトリックディテールの間のバランスを取る。変形モジュール１０８は、
【００４９】
【数４】
【００５０】
となる
【００５１】
【数５】
【００５２】
を指定する。係数ｎ／Ｎは、重みがボリュメトリックグラフの格子密度に対して鈍感となるように、重みを正規化する。この正規化によれば、
【００５３】
【数６】
【００５４】
は、体積を保存し、自己交差を防止する。この実施では、０．１＜α＜１であり、αは正規化されない。これは、制約強度は、メッシュ点の総数に対する制約点の数に依存するのが望ましいからである。この実施では、αは、デフォルトで０．２に設定される。
【００５５】
一代替実施形態では、式（３）の体積制約は、２次平滑エネルギー（ｑｕａｄｒｉｃｓｍｏｏｔｈｎｅｓｓ ｅｎｅｒｇｙ）と組み合わされる（主眼が幾何学的に相当細かいモデルを変形することである場合、これは行われない）。
【００５６】
〈局所変換の例示的な伝播〉
静止座標系におけるラプラス座標εiおよびδiを、変形された座標系における新しいラプラス座標ε’iおよびδ’iに移す、局所変換Ｔiを得るために、変形モジュール１０８は、ＷＩＲＥ変形操作を実施する。これらの操作では、変形モジュール１０８は、曲線１２０を形成するメッシュ頂点の系列を選択する。その後、これらの選択されたメッシュ頂点は、新しい状態に変形される。この曲線は、変形を制御し、ｑiを定義する（例えば、図８の画像（ａ）を参照）。
【００５７】
図８は、例示的な曲線ベースの変形を示している。より具体的には、図８の画像（ａ）は、例示的なオリジナルメッシュ１１６と、例示的な制御曲線８０２とを示す。図８の画像（ｂ）は、０（例えば、フィールド８０４−より暗いシェーディング）および１（例えば、フィールド８０６−より明るいシェーディング）の例示的な強度フィールドを示す。図８の画像（ｃ）は、図１の変形モジュール１０８の曲線ベースの変形操作から生成された、例示的な変形されたメッシュを示す。
【００５８】
制御曲線（例えば、制御曲線８０２）は、曲線上の頂点が変形される範囲のみを指定する。伝播アルゴリズムを利用する変形モジュール１０８は、最初に近隣グラフ点（制御点の１リングメッシュ近隣点）がどこまで変形するかを決定し、次に曲線点における局所変換を推測し、最後にメッシュ全体にわたって変換を伝播させる（例えば、変形されたメッシュ１１２を生じさせる）。これらの操作は、ｑiのメッシュ近隣点を発見し、ＷＩＲＥを使用してそれらの変形された位置を得ることによって、開始する。より具体的には、Ｃ（ｕ）およびＣ’（ｕ）をそれぞれ、弧長ｕ∈［０，１］によってパラメータ化された、元の制御曲線および変形された制御曲線とする。近隣点ｐ∈Ｒ3を与え、ｕp∈［０，１］を、ｐと曲線Ｃ（ｕ）の間の距離を最小化するパラメータ値とする。変形は、ＣがＣ’に写像され、近くの点も同様に動いて
ｐ’＝Ｃ’（ｕp）＋Ｒ（ｕp）（ｓ（ｕp）（ｐ−Ｃ（ｕp）））
となるように、ｐをｐ’に写像する。この式において、Ｒ（ｕ）は、Ｃ上の接ベクトルｔ（ｕ）を取り、ｔ（ｕ）×ｔ’（ｕ）の周りで回転させることによって、それをＣ’上の対応する接ベクトルｔ’（ｕ）に写像する、３×３回転行列である。ｓ（ｕ）は、スケール係数である。それは、各曲線頂点において、Ｃ’内のその隣接辺の長さの和をＣ内のこの長さの和で割った比として計算され、その後、線形補間によってｕにわたって連続的に定義される。
【００５９】
制御曲線上の各点およびその１リング近隣点の変形された座標が、これで決定される。この時点で、変形モジュール１０８の操作は、制御曲線上の各点におけるＴiを計算することに進む。変形モジュール１０８は、法線と、この法線による１つの辺ベクトルの直投影（ｐｅｒｐｅｎｄｉｃｕｌａｒｐｒｏｊｅｃｔｉｏｎ）としての接ベクトルとを計算することによって、回転を定義する。法線は、メッシュ点ｉの周りの面法線（ｆａｃｅｎｏｒｍａｌ）の面面積によって重み付けされた線形結合として計算される。回転は、四元数（ｑｕａｔｅｒｎｉｏｎ）として表され、これは、回転角が１８０度より小さいことを意味する。Ｔiのスケール係数は、ｓ（ｕp）によって与えられる。
【００６０】
その後、変換は、変形箇所から離れるにつれて減衰する変形強度フィールドｆ（ｐ）（例えば、図８の画像（ｂ）を参照）を介して、制御曲線からすべてのグラフ点ｐに伝播させられる。一定、線形、かつガウス形の強度フィールドが、選択されることができ、これは、ｐから曲線までの最短辺経路（離散測地距離（ｄｉｓｃｒｅｔｅｇｅｏｄｅｓｉｃ ｄｉｓｔａｎｃｅ））に基づいている。
【００６１】
一実施では、変形モジュール１０８は、ｐに最も近い制御曲線上の点ｑpからの回転およびスケーリングをｐに割り当てることによって、簡単な伝播方式を実施する。より滑らかな結果は、最も近い頂点の代わりに制御曲線上のすべての頂点にわたって重み付け平均を計算することによって得られる。距離の逆数
【００６２】
【数７】
【００６３】
または
【００６４】
【数８】
【００６５】
などのガウス関数によって重み付けを行う。そのようなガウス関数は、システム１００において良好に機能する。
【００６６】
【数９】
【００６７】
は、ｐからｑまでの離散測地距離を表す。項σは、ガウス形の幅を制御する。複数の曲線間の重み付けも、四元数およびスケールが複数の曲線にわたって累積されることを除いて同様である。
【００６８】
点ｐにおける最終変換行列は、
【００６９】
【数１０】
【００７０】
であり、ここで、
【００７１】
【数１１】
【００７２】
は、ｐの重み付け平均変換である。この公式は、強度フィールドを使用して、その変換を恒等変換と単純に混合する。したがって、ラプラス座標は、変形の影響領域の外では、それらの元の（静止）状態に接近する。
【００７３】
従来の伝播方式とは対照的に、変形モジュール１０８によって実施される伝播方式は、各グラフ頂点の変換を計算し、その変換を頂点のラプラス座標に適用する。加えて、いくつかの従来の技法は一般に、各三角形の変換を計算し、それを三角形の頂点に適用する。しかし、各三角形を独立に変換することは、メッシュ内の近隣三角形からそれを切断する。ポアソン式は、各三角形の向きおよびスケールを最小２乗の意味で保存するように、三角形を一緒につなぎ戻す。これの体積領域への拡張は、四面体メッシュを必要とする。
【００７４】
変形箇所において変換を計算し、その変換を変形箇所から遠く伝播させる代わりに、従来のメッシュ変形技法は、点の局所近傍を静止状態から変形された状態に移す未知の最小２乗最適変換を定義することによって、追加の自由度を導入する。定義された変換は一般に、局所詳細の喪失を防止するために、回転およびスケーリングに制限される。２次のままであり、したがって、容易に解くことができるシステムの場合、回転は、小角近似（ｓｍａｌｌ−ａｎｇｌｅａｐｐｒｏｘｉｍａｔｉｏｎ）を使用して定義される。この従来の技法は、大規模な変形に対しては貧弱な近似を提供し、その後、より複雑な反復的改善を必要とする。
【００７５】
〈例示的な重み付け方式〉
メッシュラプラシアンＬMについて、変形モジュール１０８は、余接重み（ｃｏｔａｎｇｅｎｔ ｗｅｉｇｈｔ）
ｗij∝（ｃｏｔαij＋ｃｏｔβij）
を用いる重み付け方式を利用し、ここで、αij＝∠（ｐi，ｐj-1，ｐj）、βij＝∠（ｐi，ｐj+1，ｐj）である。
【００７６】
グラフラプラシアンＬG'について、変形モジュール１０８は、２次プログラミング問題を解くことによって重みを計算する。各グラフ頂点ｉについて独立に、変形モジュール１０８は、重みｗijを得るために、次の問題を解く（明瞭にするため、下付き文字ｉは削除されている）。
【００７７】
【数１２】
【００７８】
上記の式を参照すると、第１のエネルギー項は、最小の大きさのラプラス座標を生成する重みを得ようとする。第２の項は、スケール依存のアンブレラ作用素（ｕｍｂｒｅｌｌａｏｐｅｒａｔｏｒ）に基づいており、この作用素は、辺長に反比例する重みを選ぶ（ｐｒｅｆｅｒ）。パラメータλは、これら２つの目的のバランスを取り、一方、パラメータξは、小さな重みを防止する。この実施では、λおよびξは共に、０．０１に等しく設定される。
【００７９】
図９は、一様（ａ）、辺長の逆数（ｂ）、および熱核（ｈｅａｔ ｋｅｒｎｅｌ）（平方距離の減衰指数関数）（ｃ）を含む、重み付け方式の例示的な比較を示している。これらの例示的な比較に示されるように、画像（ｄ）に示されるシステム１００の変形モジュールによって実施される重み付け方式は、その他の重み付け方式からの結果よりも滑らかかつ一様である。
【００８０】
〈例示的な２次エネルギー最小化〉
新しいラプラス座標を与えると、変形モジュール１０８は、次の式を解くことによって、式（３）の２次エネルギーを最小化する。
ＬM（ｐ’i）＋βＬG'（ｐ’i）＝ε’i＋βδ’i，ｉ∈１，．．．，ｎ
βＬG'（ｐ’i）＝βδ’i，ｉ∈ｎ＋１，．．．，Ｎ
αｐ’i＝αｑ’i，ｉ∈１，．．．，ｍ
これは、疎線形系、Ａｘ＝ｂである。行列Ａは、変形前のグラフにのみ依存するが、ｂは、現在のラプラス座標および位置制約にも依存する。したがって、Ａは、変形モジュール１０８が、メッシュまたはグラフと制御点とを取り換えない限り固定されるが、ｂは、対話的変形の間常に変化する。したがって、変形モジュール１０８は、ＬＵ分解（ＬＵｄｅｃｏｍｐｏｓｉｔｉｏｎ）を使用して、Ａ-1を事前計算し、Ａ-1ｂを得るために、動的に後退代入（ｂａｃｋ ｓｕｂｓｔｉｔｕｔｉｏｎ）ステップを実行する。
【００８１】
〈例示的な多重解像度操作〉
多重解像度（ｍｕｌｔｉ−ｒｅｓｏｌｕｔｉｏｎ）編集が、特に超大規模モデルについて、微分方法を加速するために使用されることができる。例えば、図２のスタンフォードアルマジロ（Ｓｔａｎｆｏｒｄａｒｍａｄｉｌｌｏ）モデルは、１７０Ｋの頂点を含む。変形モジュール１０８は、そのモデルのボリュメトリックグラフを生成するとき、線形系において解かれるべき頂点としての変数をほぼ６倍多く生成する。そのような大規模システムを解くことは、対話的システムにとって、計算的にコストが高い。一実施では、計算コストを減少させるため、変形モジュール１０８は、より少数の頂点（例えば、アルマジロの場合は１５Ｋ）を有する簡略化されたメッシュを生成する。その後、ボリュメトリックグラフ１１８が、簡略化されたメッシュから生成される。メッシュの簡略化表現を変形した後、変形モジュール１０８は、変形された高解像度メッシュを得るために、詳細を追加し戻す。
【００８２】
〈２−Ｄ曲線からの例示的な変形〉
システム１００の対話の基本モードは、次のようである。ユーザは最初に、最短辺（ダイクストラ（Ｄｉｊｋｓｔｒａ））経路によって連結されるメッシュ頂点の系列を選択することによって、メッシュ表面１１６上で制御曲線１２０を指定する。この３−Ｄ曲線は、その後に編集され得る２−Ｄ曲線を得るために、１つまたは複数の平面（射影平面）に射影される。編集後、変更された２−Ｄ曲線は、変形された制御曲線を得るために、３−Ｄに射影し戻され、その制御曲線が、先のセクションの変形の基礎を形成する。
【００８３】
〈例示的な曲線射影〉
元の制御曲線を与えると、変形モジュール１０８は、元の制御曲線の平均法線および主ベクトルに基づいて、自動的に射影平面を選択する。変形モジュール１０８は、曲線の頂点にわたる主成分分析（ＰＣＡ：ｐｒｉｎｃｉｐａｌｃｏｍｐｏｎｅｎｔ ａｎａｌｙｓｉｓ）からの最大固有値に対応する２つの固有ベクトルとして主ベクトルを計算する。大部分の場合、平均法線と第１の主ベクトルの外積が、満足のゆく平面を提供する。平均法線ベクトルの長さが、閉平面曲線（ｃｌｏｓｅｄｐｌａｎａｒ ｃｕｒｖｅ）用として小さい場合、２つの主ベクトルが代わりに利用される。この実施では、ユーザは、射影を直接選択することも、またはシステム１００によって選択された射影を変更することもできる。
【００８４】
〈例示的な曲線編集〉
射影２−Ｄ曲線は、編集を複雑にするオリジナルメッシュ１１６から、幾何学的詳細を継承する。多重解像度曲線編集は、Ｂスプライン曲線用の１つの解法を提供する。変形モジュール１０８は、ラプラス座標に基づいて離散曲線用の編集操作を実施する。曲線頂点のラプラス座標は、頂点の位置と頂点の２つの隣接点の平均位置との間の差であり、終端頂点の場合は単一隣接点との間の差である。
【００８５】
編集される離散２−Ｄ曲線が、Ｃで示される。３次Ｂスプライン曲線Ｃbが、Ｃの低周波数を表す、Ｃに対する最小２乗適合（ｌｅａｓｔ−ｓｑｕａｒｅｓｆｉｔ）として、最初に計算される。その後、Ｃdで示されるＣbの離散バージョンが、比例弧長写像（ｐｒｏｐｏｒｔｉｏｎａｌ ａｒｃ−ｌｅｎｇｔｈ ｍａｐｐｉｎｇ）を使用して、Ｃの各頂点をＣbに写像することによって計算される。単純なＢスプライン曲線Ｃbが、これで都合よく編集されることができる。編集後、変形モジュール１０８は、変更されたＢスプライン曲線Ｃ’bと、新しい離散バージョンＣ’dとを得る。これらの曲線は、ユーザの所望の変形を示すが、元の曲線の詳細を欠いている。元の曲線の詳細を回復するため、変形モジュール１０８は、Ｃの各頂点において、その位置をＣdからＣ’dに写像する一意な回転およびスケーリングを識別する。この変換をＣ上のラプラス座標に適用することと、単純な曲線グラフにわたって（第２の点制約項を持たない）式（２）を解くことが、新しい曲線Ｃ’の生成をもたらす。この新しい曲線は、Ｃの詳細を保存するが、ユーザの粗いスケール変更に従う。基本的に、これは、メッシュを変形するための局所変換「伝播」の自明なバージョンであるが、曲線の場合は、それは、点毎に独立に定義されることができ、伝播される必要がない。
【００８６】
このアルゴリズムは、曲線類似（ｃｕｒｖｅ ａｎａｌｏｇｙ）として提出され、すなわち、１対の元の曲線ＣsおよびＣ’sと、目標曲線Ｃを与えると、ＣとＣ’の間の関係がＣsとＣ’sの間の関係に類似するように、新しい曲線Ｃ’を生成する。従来のメッシュ変形操作は、頂点を直接変換することができるが、変形モジュール１０８は、頂点の対応する差分座標を、曲線全体にわたってより一様に分散された誤差に変換する。
【００８７】
最初に、Ｃbは、曲線の端点に２つのノット（ｋｎｏｔ）を有する。ユーザは、より詳細なレベルで編集を実行するために、ノットを追加することができる。システム１００は、２つの編集モードをサポートし、一方は、元の曲線Ｃbに対する粗いスケールの適合を操作し、他方は、まったく新しい曲線をスケッチする。後者の場合、スケッチされた曲線と制御曲線の間の対応は、デフォルトでは、弧長によって達成される。この実施では、ユーザが、２つの曲線の間の一連の対応点を指定することもできる。
【００８８】
〈２−Ｄアニメからの例示的な変形再標的化〉
一実施では、システム１００が２−Ｄアニメの変形を３−Ｄメッシュ１１２に再標的化（ｒｅ−ｔａｒｇｅｔ）することは、システム１００の２−Ｄスケッチベースの変形の例示的な直接の応用である。この目的で、ユーザは、メッシュ１１６上で１つまたは複数の３−Ｄ制御曲線１２０を、それらの射影平面と共に指定し、各曲線について、メッシュ１１６の変形を推進するのに使用されるアニメ画像系列内の一連の２−Ｄ曲線１２０を指定する。
【００８９】
図９は、２−Ｄ画像からの変形再標的化のための例示的な３−Ｄおよび２−Ｄ制御曲線指定を示している。より具体的には、制御曲線の組９０２（すなわち、９０２−１ａから９０２−３ｂ）は、３−Ｄメッシュ上で指定され、制御曲線の組９０４（すなわち、９０４−１ａから９０４−３ｂ）は、２−Ｄ画像上で指定される。（例示的な説明の目的で、２−Ｄおよび３−Ｄ制御曲線は、図１の指定された点１２０として示されている）。
【００９０】
Ｃiが３−Ｄ制御曲線９０２の射影であり、アニメ系列内のそれに対応する曲線９０４がＣi,j、ｊ∈｛１，．．．，ｋ｝であると仮定する。インデックスｉは、腕および脚などのモデルの異なる部分を動かす、異なる制御曲線に対応する。インデックスｊは、フレームインデックスであり、同じ制御曲線は、各フレーム毎に対応するアニメ曲線を有する。変形モジュール１０８は、Ｃiを連続するＣi,jに写像する変形系列を自動的に導出する。これらの変形操作に関して、あらゆるフレームで最初から変形を生成する必要はない。一実施では、ユーザは、すべてのフレーム系列について制御曲線を指定する代わりに、僅か数個の主要フレームを選択し、選択された主要フレームについてのみアニメ制御曲線を指定してもよい。変形モジュール１０８は、主要フレーム間を補間するために、差分座標に基づいて自動補間操作を実施する。例えば、同じ連結度を有する２つのメッシュＭおよびＭ’が存在すると仮定する。これら２つのメッシュは、２つの主要フレームにおける変形されたメッシュ１１２を表す。
【００９１】
変形モジュール１０８は、２つのメッシュ上の各頂点のラプラス座標を計算することによって開始する。変形モジュール１０８は、各頂点ｐの局所近傍における回転およびスケーリングを計算し、ラプラス座標をＭにおける位置からＭ’に移す（例えば、「ボリュメトリックグラフの例示的な変形」と題する上記のセクションを参照）。変換をＴpによって示す。恒等変換からＴpへの各変換を経時的に補間することによって、ＭからＭ’へと滑らかに変化するラプラス座標を得る。この時点で、変形モジュール１０８は、ＭからＭ’へのメッシュの系列を提供するために、式（２）を解く。
【００９２】
２−Ｄアニメ曲線は、変形された曲線がどのように単一平面に射影されるかを指定するに過ぎず、平面に垂直な形状は指定されずに残される。この点に鑑みて、システム１００は、ユーザが、必要であれば、これらの追加の自由度を指定するために、その他の射影平面を選択することを可能にする。
【００９３】
図１０は、システム１００のボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形と比較された、従来の大規模メッシュ変形技法のさらなる例示的な比較を示している。より具体的には、上の行は、左から右に、オリジナルメッシュの画像と、変形を編集するポアソンメッシュの結果を示す例示的な画像と、ボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形の例示的な結果を示す画像とをそれぞれ示している。第２または下の行は、上の行の直上の画像に関連付けられた変形領域の拡大部分を示している。すなわち、列（ａ）の画像は、オリジナルメッシュ１１６と関連付けられ、列（ｂ）の画像は、ポアソンメッシュ編集を使用して変形されたオリジナルメッシュの結果に対応し、列（ｃ）の画像は、システム１００のボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形を使用して変形されたオリジナルメッシュの結果に対応する。
【００９４】
〈例示的な手順〉
図１１は、ボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形のための例示的な手順１１００を示している。解説および例示的な説明の目的で、この手順の動作は、図１の構成要素に関して説明される。構成要素の参照番号の左端の数字は、その構成要素が最初に出現した特定の図面を識別する。加えて、図１１は、特定の順序で手順１１００の動作を提示するが、手順の任意の特定のブロックに関連付けられた動作は、異なる順序で実施されてもよい。例えば、ブロック１１０４の動作は、ブロック１１０２の動作の前に実施されてもよいなどである。
【００９５】
ブロック１１０２において、変形モジュール１０８は、オリジナルメッシュ１１６からボリュメトリックグラフ１１８を構成する。一実施では、変形モジュール１０８は、中間的な内側および外側グラフデータ構造を使用して、ボリュメトリックグラフを構成する。内側グラフは、オリジナルメッシュ１１６の内側に存在するように構成された単純格子である。内側グラフは、オリジナルメッシュの点と、導出された点とを含み、大規模メッシュ変形操作中の大きな体積変化を防止するために、変形モジュール１０８によって使用される。一実施では、変形モジュール１０８は、オリジナルメッシュの各頂点をその法線とは反対の方向にずらす簡略化エンベロープを使用して、内側グラフを構成する。一実施では、変形モジュール１０８は、オリジナルメッシュの各頂点をオリジナルメッシュの表面の外側に向かって反復的にずらすことによって、局所自己交差を防止するように、外側グラフを構成する。変形モジュール１０８は、ボリュメトリックグラフを生成するために、内側および外側グラフと、変形の対象とされるオリジナルメッシュ１１６との間の連結を構築する。
【００９６】
ブロック１１０４において、変形モジュール１０８は、ユーザが、１組の３−Ｄ制御曲線１２０を指定することを可能にする。各３−Ｄ制御曲線は、オリジナルメッシュ１１６上の１組の点を識別する。一実施では、変形モジュール１０８は、表示デバイス上にユーザインタフェース（ＵＩ）を提示する。オリジナルメッシュ１１６の３−Ｄ表示が、ＵＩによってユーザに提示される。マウスまたはその他のタイプのポインティングデバイスを使用して、ユーザは、３−Ｄ制御曲線１２０を定義するオリジナルメッシュ１１６上の１組の点を選択する。
【００９７】
ブロック１１０６において、変形モジュール１０８は、ユーザが、変形された制御曲線１２４を生成するために、３−Ｄ制御曲線１２０をそれぞれの２−Ｄ制御曲線１２０として編集することを可能にする。変形された制御曲線１２４は、オリジナルメッシュ１１６がどのように変形されるかを示す。この実施では、ユーザは、次のようにして、オリジナルメッシュ１１６がどのように変形されるかを指定する。変形モジュール１０８は、指定された３−Ｄ制御曲線１２０をＵＩ内の射影平面上に２−Ｄ制御曲線１２０として射影する。ユーザは、提供されたＵＩを使用して、射影された２−Ｄ制御曲線１２０を操作することによって、オリジナルメッシュ１１６を変形する。これは、３−Ｄ制御曲線１２０内の指定された点が、定義された変形の結果として、どこに動かされるかを示す。例えば、一実施では、ユーザは、マウスおよび／またはグラフィックスペンなどのポインティングデバイスを用いて２−Ｄ制御曲線を選択することによって、射影された２−Ｄ制御曲線を操作し、２−Ｄ制御曲線１２０を変更する。例えば、ユーザは、目標曲線（すなわち、変形）を表す新しい曲線を引き、ＵＩなどによって２−Ｄ曲線上に提示されるＢスプライン制御点を使用して、２−Ｄ曲線を直接編集することもできる。
【００９８】
ブロック１１０８において、変形モジュール１０８は、グラフ内の各点とその近隣点の平均との間の差としてボリュメトリックディテールを符号化するように、ボリュメトリックグラフ１１８のラプラシアン（すなわち、ボリュメトリックグラフ・ラプラシアン１１４）を生成する。これらのボリュメトリックディテールは、体積の不自然な変化を防止する体積制約を課すために、変形操作中に利用される。これらのボリュメトリックディテールは、オリジナルメッシュ１１６の外側の近距離にある点も含み、それらは、体積の局所自己交差を実質的に防止するために、変形操作中に使用される。
【００９９】
ブロック１１１０において、変形モジュール１０８は、変形された制御曲線１２４に基づいて、オリジナルメッシュ１１６を変形する。このようにして、システム１００は、ユーザが大規模メッシュ変形を生成することを可能にする、曲線ベースの変形システムを提供する。
【０１００】
〈例示的な動作環境〉
図１２は、ボリュメトリックグラフラ・プラシアンを使用する大規模メッシュ変形が完全または部分的に実施され得る、適切なコンピューティング環境の一例を示している。例示的なコンピューティング環境１２００は、図１の例示的なシステムおよび図１１の例示的な動作にとって適切なコンピューティング環境の一例に過ぎず、本明細書で説明されたシステムおよび方法の使用範囲または機能に関するどのような限定も示唆しようとするものではない。コンピューティング環境１２００は、コンピューティング環境１２００に示された構成要素のいずれか１つまたは組み合わせに関して、どのような依存性または必要性も有さないと解釈されるべきである。
【０１０１】
本明細書で説明された方法およびシステムは、多数のその他の汎用または専用コンピューティングシステム、環境、または構成と共に動作可能である。使用に適し得るよく知られたコンピューティングシステム、環境、および／または構成の例は、パーソナルコンピュータ、サーバコンピュータ、マルチプロセッサシステム、マイクロプロセッサベースシステム、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、および上記のシステムまたはデバイスのいずれかを含む分散コンピューティング環境などを、これらに限定することなく含む。フレームワークのコンパクト版またはサブセット版が、ハンドヘルドコンピュータまたはその他のコンピューティングデバイスなど、リソースが限られたクライアントで実施されてもよい。本発明は、必ずしも必要ではないが、通信ネットワークを介して結合されるリモート処理デバイスによってタスクが実行される、分散コンピューティング環境で実施されることができる。分散コンピューティング環境では、プログラムモジュールは、ローカルおよびリモート両方のメモリ記憶デバイスに配置されてよい。
【０１０２】
図１２を参照すると、ボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形を提供する例示的なシステムは、例えば図１のシステム１００を実施する、コンピュータ１２１０の形態の汎用コンピューティングデバイスを含む。コンピュータ１２１０の構成要素は、処理ユニット１２２０、システムメモリ１２３０、およびシステムメモリを含む様々なシステム構成要素を処理ユニット１２２０に結合するシステムバス１２２１を、これらに限定することなく含むことができる。システムバス１２２１は、メモリバスまたはメモリコントローラ、周辺バス、および様々なバスアーキテクチャのいずれかを使用するローカルバスを含む、複数のタイプのバス構造のいずれかとすることができる。限定することなく例を挙げると、そのようなアーキテクチャは、業界標準アーキテクチャ（ＩＳＡ）バス、マイクロチャネルアーキテクチャ（ＭＣＡ）バス、拡張業界標準アーキテクチャ（ＥＩＳＡ）バス、ビデオ電子規格協会（ＶＥＳＡ）ローカルバス、およびメザニンバスとしても知られる周辺コンポーネント相互接続（ＰＣＩ）バスを含むことができる。
【０１０３】
コンピュータ１２１０は一般に、様々なコンピュータ可読媒体を含む。コンピュータ可読媒体は、揮発性および不揮発性媒体、着脱可能および固定式媒体を含む、コンピュータ１２１０によってアクセス可能な任意の利用可能な媒体とすることができる。限定することなく例を挙げると、コンピュータ可読媒体は、コンピュータ記憶媒体および通信媒体を含むことができる。コンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、またはその他のデータなどの情報を記憶するための任意の方法または技法で実施された、揮発性および不揮発性、着脱可能および固定式媒体を含む。コンピュータ記憶媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ、もしくはその他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）、もしくはその他の光ディスク記憶、磁気カセット、磁気テープ、磁気ディスク記憶、もしくはその他の磁気記憶デバイス、または所望の情報を記憶するのに使用でき、コンピュータ１２１０によってアクセス可能なその他の任意の媒体を、これらに限定することなく含む。
【０１０４】
通信媒体は一般に、コンピュータ可読命令、データ構造、プログラムモジュール、またはその他のデータを、搬送波またはその他のトランスポート機構などの変調データ信号中に具現し、任意の情報伝達媒体を含む。「変調データ信号」という用語は、信号中に情報を符号化するような仕方で設定または変更された１つまたは複数の特徴を有する信号を意味する。限定することなく例を挙げると、通信媒体は、有線ネットワークまたは直接配線接続などの有線媒体、ならびに音響、ＲＦ、赤外線、およびその他の無線媒体などの無線媒体を含む。上記の任意のものの組み合わせも、コンピュータ可読媒体の範囲内に含まれるべきである。
【０１０５】
システムメモリ１２３０は、読み取り専用メモリ（ＲＯＭ）１２３１およびランダムアクセスメモリ（ＲＡＭ）１２３２などの、揮発性および／または不揮発性メモリの形態のコンピュータ記憶媒体を含む。起動中などにコンピュータ１２１０内の要素間で情報を伝送する助けをする基本ルーチンを含む基本入出力システム１２３３（ＢＩＯＳ）は一般に、ＲＯＭ１２３１に記憶される。ＲＡＭ１２３２は一般に、処理ユニット１２１０から直ちにアクセス可能な、かつ／または処理ユニット１２１０が現在それに基づいて動作している、データおよび／またはプログラムモジュールを含む。限定することなく例を挙げると、図１２は、オペレーティングシステム１２３４、アプリケーションプログラム１２３５、その他のプログラムモジュール１２３６、およびプログラムデータ１２３７を示している。
【０１０６】
コンピュータ１２１０は、その他の着脱可能／固定式、揮発性／不揮発性コンピュータ記憶媒体も含むことができる。例としてのみ挙げると、図１２は、固定式の不揮発性磁気媒体からの読み取りまたはそうした媒体への書き込みを行うハードディスクドライブ１２４１、着脱可能な不揮発性磁気ディスク１２５２からの読み取りまたはそうしたディスクへの書き込みを行う磁気ディスクドライブ１２５１、およびＣＤ−ＲＯＭまたはその他の光媒体などの着脱可能な不揮発性光ディスク１２５６からの読み取りまたはそうしたディスクへの書き込みを行う光ディスクドライブ１２５５を示している。例示的な動作環境で使用され得るその他の着脱可能／固定式、揮発性／不揮発性コンピュータ記憶媒体は、磁気テープカセット、フラッシュメモリカード、デジタル多用途ディスク、デジタルビデオテープ、ソリッドステートＲＡＭ、およびソリッドステートＲＯＭなどを、これらに限定することなく含む。ハードディスクドライブ１２４１は一般に、インタフェース１２４０などの固定式メモリインタフェースを介してシステムバス１２２１に接続され、磁気ディスクドライブ１２５１および光ディスクドライブ１２５５は一般に、インタフェース１２５０などの着脱可能メモリインタフェースによってシステムバス１２２１に接続される。
【０１０７】
上で説明された図１２に示されるドライブおよびそれに関連するコンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、およびその他のデータの記憶を、コンピュータ１２１０に提供する。図１２では、例えば、ハードディスクドライブ１２４１は、オペレーティングシステム１２４４、アプリケーションプログラム１２４５、その他のプログラムモジュール１２４６、およびプログラムデータ１２４７を記憶するとして示されている。これらの構成要素は、オペレーティングシステム１２３４、アプリケーションプログラム１２３５、その他のプログラムモジュール１２３６、およびプログラムデータ１２３７と同じであることも、または異なることもできることに留意されたい。オペレーティングシステム１２４４、アプリケーションプログラム１２４５、その他のプログラムモジュール１２４６、およびプログラムデータ１２４７は、それらが少なくとも異なるコピーであることを示すために、ここでは異なる番号を与えられている。
【０１０８】
ユーザは、キーボード１２６２、および一般にマウス、トラックボール、またはタッチパッドと呼ばれるポインティングデバイス１２６１などの入力デバイスを介して、コンピュータ１２１０にコマンドおよび情報を入力することができる。その他の入力デバイス（図示されず）は、マイクロフォン、ジョイスティック、グラフィックスペンおよびパッド、衛星放送受信アンテナ、またはスキャナなどを含むことができる。上記およびその他の入力デバイスはしばしば、システムバス１２２１に結合されるユーザ入力インタフェース１２６０を介して処理ユニット１２２０に接続されるが、パラレルポート、ゲームポート、またはユニバーサルシリアルバス（ＵＳＢ）などのその他のインタフェースおよびバス構造によって接続されてもよい。
【０１０９】
モニタ１２９１またはその他のタイプの表示デバイスも、ビデオインタフェース１２９０などのインタフェースを介して、システムバス１２２１に接続される。モニタに加えて、コンピュータは、プリンタ１２９６およびオーディオデバイス１２９７などのその他の周辺出力デバイスも含むことができ、それらは、出力周辺インタフェース１２９５を介して接続されることができる。
【０１１０】
コンピュータ１２１０は、リモートコンピュータ１２８０などの１つまたは複数のリモートコンピュータへの論理コネクションを使用して、ネットワーク環境で動作する。リモートコンピュータ１２８０は、パーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ピアデバイス、またはその他の共通ネットワークノードであってよく、その具体的な実装に応じて、コンピュータ１２１０に関連して上で説明された要素の多くまたは全部を含むことができるが、図１２には、メモリ記憶デバイス１２８１のみが示されている。図１２に示された論理コネクションは、ローカルエリアネットワーク（ＬＡＮ）１２７１およびワイドエリアネットワーク（ＷＡＮ）１２７３を含むが、その他のネットワークを含んでもよい。そのようなネットワーク環境は、オフィス、企業規模のコンピュータネットワーク、イントラネット、およびインターネットにおいて一般的である。
【０１１１】
ＬＡＮネットワーク環境で使用される場合、コンピュータ１２１０は、ネットワークインタフェースまたはアダプタ１２７０を介して、ＬＡＮ１２７１に接続される。ＷＡＮネットワーク環境で使用される場合、コンピュータ１２１０は一般に、インターネットなどのＷＡＮ１２７３を介して通信を確立するためのモデム１２７２またはその他の手段を含む。モデム１２７２は、内蔵でもまたは外付けでもよく、ユーザ入力インタフェース１２６０またはその他の適切な機構を介して、システムバス１２２１に接続されることができる。ネットワーク環境では、コンピュータ１２１０に関連して示されたプログラムモジュールまたはその部分は、リモートメモリ記憶デバイスに記憶されることができる。限定することなく例を挙げると、図１２は、メモリデバイス１２８１上に存在するとして、リモートアプリケーションプログラム１２８５を示している。示されたネットワークコネクションは、例示的なものであり、コンピュータ間の通信リンクを確立するその他の手段が使用されてもよい。
【０１１２】
〈結論〉
従来の差分領域メッシュ変形技法は、メッシュが変形される際に、表面詳細を保存するが、そのような既存の技法は一般に、変形が大規模である場合、好ましくないピンチング（ｐｉｎｃｈｉｎｇ）および交差アーチファクトを生み出す。図１のシステム１００は、ボリュメトリックグラフ・ラプラシアンによって表されるボリュメトリックディテールを保存することによって、これらの問題に対処する。この解決策は、複雑な物体をソリッドメッシュする複雑さを回避する。ボリュメトリックグラフ・ラプラシアンを使用する大規模メッシュ変形のためのシステムおよび方法は、構造的特徴および／または方法的操作および動作に特有の言葉で説明されたが、添付の特許請求の範囲において確定される実施は、必ずしも説明された特定の特徴または動作に限定されないことは理解されよう。むしろ、システム１００の特定の特徴および操作は、特許請求される主題を実施する例示的な形態として開示されている。
【特許請求の範囲】
【請求項１】
オリジナルメッシュがどのように変形されるかを示す情報をユーザから受け取るステップと、
前記情報と、前記オリジナルメッシュから生成されたボリュメトリックグラフに適用される体積微分演算子とに基づいて、前記オリジナルメッシュを変形するステップと、
を含むことを特徴とするコンピュータ実施方法。
【請求項２】
前記情報は、前記オリジナルメッシュに関して指定された１つまたは複数のそれぞれの３−Ｄ制御曲線から導出される１つまたは複数の２−Ｄ制御曲線であることを特徴とする請求項１に記載の方法。
【請求項３】
前記情報は、前記オリジナルメッシュの変形を表すためにユーザによって指定された１つまたは複数の新しい２−Ｄ制御曲線であることを特徴とする請求項１に記載の方法。
【請求項４】
前記オリジナルメッシュを変形するステップは、前記オリジナルメッシュの表面内部をソリッドメッシュすることとは独立であることを特徴とする請求項１に記載の方法。
【請求項５】
前記体積微分演算子は、前記ボリュメトリックグラフ・ラプラシアンであることを特徴とする請求項１に記載の方法。
【請求項６】
前記体積微分演算子は、前記ボリュメトリックグラフ・ラプラシアンであり、前記ボリュメトリックグラフ・ラプラシアンは、ボリュメトリックグラフ内の複数の点のうちの各点と各点の近隣点の体積平均との体積差として前記オリジナルメッシュのボリュメトリックディテールを符号化することを特徴とする請求項１に記載の方法。
【請求項７】
前記体積微分演算子は、前記ボリュメトリックグラフ・ラプラシアンであり、前記ボリュメトリックグラフ・ラプラシアンは、前記オリジナルメッシュを変形したときに体積の不自然な変化を防止する体積制約を課すようにボリュメトリックディテールを符号化し、前記ボリュメトリックディテールは、前記オリジナルメッシュの外側の点と、前記オリジナルメッシュの内側の点からなる単純格子構造とを含むことを特徴とする請求項１に記載の方法。
【請求項８】
ユーザが前記オリジナルメッシュの表面上で１つまたは複数の３−Ｄ制御曲線を指定することを可能にするステップと、
前記１つまたは複数の３−Ｄ制御曲線の少なくとも１つに対応するそれぞれ２−Ｄ制御曲線を前記ユーザに提示するステップと、
前記ユーザが変形に応じた前記２−Ｄ制御曲線に関連付けられた１組の点の動きを指定するために前記２−Ｄ制御曲線を変更することを可能にするステップと、
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項９】
内側および外側グラフ構造を生成するステップであって、前記内側グラフ構造は、前記オリジナルメッシュの内側に存在するように構成された第１の格子であり、前記外側グラフ構造は、前記オリジナルメッシュの外側に存在するように構成された第２の格子であるステップと、
前記内側グラフ構造と前記外側グラフ構造の間の連結を構築するステップと、
前記外側グラフ構造の詳細を前記オリジナルメッシュと連結するステップと、
による、前記ボリュメトリックグラフを生成するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項１０】
内側および外側グラフ構造を生成するステップであって、前記内側グラフ構造は、前記オリジナルメッシュの内側に存在するように構成された第１の格子であり、前記外側グラフ構造は、前記オリジナルメッシュの外側に存在するように構成された第２の格子であるステップと、
前記内側グラフ構造に基づいた情報を使用して、前記オリジナルメッシュに関連付けられた大規模メッシュ変形操作中の大きな体積変化を防止するステップと、
前記外側グラフ構造に基づいた情報に基づいて、前記オリジナルメッシュに関連付けられた大規模メッシュ変形操作中の頂点の自己局所交差を回避するステップと、
による、前記ボリュメトリックグラフを生成するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項１１】
前記オリジナルメッシュを変形するステップは、前記オリジナルメッシュに関連付けられた元の表面詳細の保存と、ユーザ選択の変形位置と、前記ボリュメトリックグラフ・プラシアンによって指定されるボリュメトリックディテールの保存とのバランスを取るステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項１２】
ユーザインタフェースをユーザに提示するステップであって、前記ユーザインタフェースが３−Ｄメッシュを表示するステップと、
前記ユーザが前記３−Ｄメッシュに関する３−Ｄ制御曲線を指定することを可能にするステップと、
前記３−Ｄ制御曲線を２−Ｄ制御曲線として平面上に射影するステップと、
前記ユーザが前記３−Ｄメッシュの目標変形を指定する変更された制御曲線を生成するように前記２−Ｄ制御曲線を編集することを可能にするステップと、
前記３−Ｄメッシュから導出されたボリュメトリックグラフ・ラプラシアンと前記変更された制御曲線とに基づいて、前記３−Ｄメッシュを変形するステップと、
を含むことを特徴とするコンピュータ実施方法。
【請求項１３】
前記ユーザが前記２−Ｄ制御曲線を編集することを可能にするステップは、前記ユーザに新しい曲線を生成する機会を提示するステップであって、前記新しい曲線は、前記変更された制御曲線であるステップをさらに含むことを特徴とする請求項１２に記載の方法。
【請求項１４】
前記ユーザが前記２−Ｄ制御曲線を編集することを可能にするステップは、前記２−Ｄ制御曲線上にＢスプライン制御点を提示するステップであって、前記Ｂスプライン制御点は、前記２−Ｄ制御曲線の形状およびサイズを操作するために選択可能であるステップをさらに含むことを特徴とする請求項１２に記載の方法。
【請求項１５】
前記３−Ｄメッシュを変形するステップは、
前記３−Ｄメッシュの頂点に基づいてボリュメトリックグラフを生成するステップであって、前記ボリュメトリックグラフは、前記３−Ｄメッシュに関連付けられた表面の内側の頂点からなる単純格子と、前記表面の外側の頂点とを含むステップと、
前記ボリュメトリックグラフ内の複数の点のうちの各点と前記点に隣接する点の平均との差としてボリュメトリックディテールを符号化するために、前記ボリュメトリックグラフ・ラプラシアンを決定するステップと、
をさらに含むことを特徴とする請求項１２に記載の方法。
【請求項１６】
前記３−Ｄメッシュを変形するステップは、前記３−Ｄメッシュの内側に形成された単純格子からの情報を使用して、前記オリジナルメッシュの大規模メッシュ変形中の大きな体積変化を防止するステップをさらに含むことを特徴とする請求項１２に記載の方法。
【請求項１７】
前記３−Ｄメッシュを変形するステップは、前記３−Ｄメッシュの前記表面の外側に生成されたグラフからの情報を使用して、前記オリジナルメッシュの大規模メッシュ変形中の体積の自己交差を防止するステップをさらに含むことを特徴とする請求項１２に記載の方法。
【請求項１８】
前記３−Ｄメッシュを変形するステップは、前記３−Ｄメッシュに関連付けられた元の表面詳細の保存と、ユーザ選択の変形位置と、前記ボリュメトリックグラフ・ラプラシアンによって指定されるボリュメトリックディテールの保存とのバランスを取るステップをさらに含むことを特徴とする請求項１２に記載の方法。
【請求項１９】
前記オリジナルメッシュの複数の頂点のうちの各頂点を前記頂点の法線とは反対の方向に反復的にずらす簡略化エンベロープを使用して、前記３−Ｄメッシュの内側に単純格子グラフ構造を生成するステップと、
前記オリジナルメッシュの各頂点を前記オリジナルメッシュに対応する表面の外側方向に反復的にずらすことによって、外側グラフを生成するステップであって、前記外側グラフは、前記３−Ｄメッシュの外側の頂点を含むステップと、
ボリュメトリックグラフを生成するために、前記内側および外側グラフと前記オリジナルメッシュとの間に連結を構築するステップと、
をさらに含むことを特徴とする請求項１２に記載の方法。
【請求項２０】
辺消去および平滑化操作を使用して、前記ボリュメトリックグラフを簡略化するステップをさらに含むことを特徴とする請求項１９に記載の方法。
【請求項１】
オリジナルメッシュがどのように変形されるかを示す情報をユーザから受け取るステップと、
前記情報と、前記オリジナルメッシュから生成されたボリュメトリックグラフに適用される体積微分演算子とに基づいて、前記オリジナルメッシュを変形するステップと、
を含むことを特徴とするコンピュータ実施方法。
【請求項２】
前記情報は、前記オリジナルメッシュに関して指定された１つまたは複数のそれぞれの３−Ｄ制御曲線から導出される１つまたは複数の２−Ｄ制御曲線であることを特徴とする請求項１に記載の方法。
【請求項３】
前記情報は、前記オリジナルメッシュの変形を表すためにユーザによって指定された１つまたは複数の新しい２−Ｄ制御曲線であることを特徴とする請求項１に記載の方法。
【請求項４】
前記オリジナルメッシュを変形するステップは、前記オリジナルメッシュの表面内部をソリッドメッシュすることとは独立であることを特徴とする請求項１に記載の方法。
【請求項５】
前記体積微分演算子は、前記ボリュメトリックグラフ・ラプラシアンであることを特徴とする請求項１に記載の方法。
【請求項６】
前記体積微分演算子は、前記ボリュメトリックグラフ・ラプラシアンであり、前記ボリュメトリックグラフ・ラプラシアンは、ボリュメトリックグラフ内の複数の点のうちの各点と各点の近隣点の体積平均との体積差として前記オリジナルメッシュのボリュメトリックディテールを符号化することを特徴とする請求項１に記載の方法。
【請求項７】
前記体積微分演算子は、前記ボリュメトリックグラフ・ラプラシアンであり、前記ボリュメトリックグラフ・ラプラシアンは、前記オリジナルメッシュを変形したときに体積の不自然な変化を防止する体積制約を課すようにボリュメトリックディテールを符号化し、前記ボリュメトリックディテールは、前記オリジナルメッシュの外側の点と、前記オリジナルメッシュの内側の点からなる単純格子構造とを含むことを特徴とする請求項１に記載の方法。
【請求項８】
ユーザが前記オリジナルメッシュの表面上で１つまたは複数の３−Ｄ制御曲線を指定することを可能にするステップと、
前記１つまたは複数の３−Ｄ制御曲線の少なくとも１つに対応するそれぞれ２−Ｄ制御曲線を前記ユーザに提示するステップと、
前記ユーザが変形に応じた前記２−Ｄ制御曲線に関連付けられた１組の点の動きを指定するために前記２−Ｄ制御曲線を変更することを可能にするステップと、
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項９】
内側および外側グラフ構造を生成するステップであって、前記内側グラフ構造は、前記オリジナルメッシュの内側に存在するように構成された第１の格子であり、前記外側グラフ構造は、前記オリジナルメッシュの外側に存在するように構成された第２の格子であるステップと、
前記内側グラフ構造と前記外側グラフ構造の間の連結を構築するステップと、
前記外側グラフ構造の詳細を前記オリジナルメッシュと連結するステップと、
による、前記ボリュメトリックグラフを生成するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項１０】
内側および外側グラフ構造を生成するステップであって、前記内側グラフ構造は、前記オリジナルメッシュの内側に存在するように構成された第１の格子であり、前記外側グラフ構造は、前記オリジナルメッシュの外側に存在するように構成された第２の格子であるステップと、
前記内側グラフ構造に基づいた情報を使用して、前記オリジナルメッシュに関連付けられた大規模メッシュ変形操作中の大きな体積変化を防止するステップと、
前記外側グラフ構造に基づいた情報に基づいて、前記オリジナルメッシュに関連付けられた大規模メッシュ変形操作中の頂点の自己局所交差を回避するステップと、
による、前記ボリュメトリックグラフを生成するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項１１】
前記オリジナルメッシュを変形するステップは、前記オリジナルメッシュに関連付けられた元の表面詳細の保存と、ユーザ選択の変形位置と、前記ボリュメトリックグラフ・プラシアンによって指定されるボリュメトリックディテールの保存とのバランスを取るステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項１２】
ユーザインタフェースをユーザに提示するステップであって、前記ユーザインタフェースが３−Ｄメッシュを表示するステップと、
前記ユーザが前記３−Ｄメッシュに関する３−Ｄ制御曲線を指定することを可能にするステップと、
前記３−Ｄ制御曲線を２−Ｄ制御曲線として平面上に射影するステップと、
前記ユーザが前記３−Ｄメッシュの目標変形を指定する変更された制御曲線を生成するように前記２−Ｄ制御曲線を編集することを可能にするステップと、
前記３−Ｄメッシュから導出されたボリュメトリックグラフ・ラプラシアンと前記変更された制御曲線とに基づいて、前記３−Ｄメッシュを変形するステップと、
を含むことを特徴とするコンピュータ実施方法。
【請求項１３】
前記ユーザが前記２−Ｄ制御曲線を編集することを可能にするステップは、前記ユーザに新しい曲線を生成する機会を提示するステップであって、前記新しい曲線は、前記変更された制御曲線であるステップをさらに含むことを特徴とする請求項１２に記載の方法。
【請求項１４】
前記ユーザが前記２−Ｄ制御曲線を編集することを可能にするステップは、前記２−Ｄ制御曲線上にＢスプライン制御点を提示するステップであって、前記Ｂスプライン制御点は、前記２−Ｄ制御曲線の形状およびサイズを操作するために選択可能であるステップをさらに含むことを特徴とする請求項１２に記載の方法。
【請求項１５】
前記３−Ｄメッシュを変形するステップは、
前記３−Ｄメッシュの頂点に基づいてボリュメトリックグラフを生成するステップであって、前記ボリュメトリックグラフは、前記３−Ｄメッシュに関連付けられた表面の内側の頂点からなる単純格子と、前記表面の外側の頂点とを含むステップと、
前記ボリュメトリックグラフ内の複数の点のうちの各点と前記点に隣接する点の平均との差としてボリュメトリックディテールを符号化するために、前記ボリュメトリックグラフ・ラプラシアンを決定するステップと、
をさらに含むことを特徴とする請求項１２に記載の方法。
【請求項１６】
前記３−Ｄメッシュを変形するステップは、前記３−Ｄメッシュの内側に形成された単純格子からの情報を使用して、前記オリジナルメッシュの大規模メッシュ変形中の大きな体積変化を防止するステップをさらに含むことを特徴とする請求項１２に記載の方法。
【請求項１７】
前記３−Ｄメッシュを変形するステップは、前記３−Ｄメッシュの前記表面の外側に生成されたグラフからの情報を使用して、前記オリジナルメッシュの大規模メッシュ変形中の体積の自己交差を防止するステップをさらに含むことを特徴とする請求項１２に記載の方法。
【請求項１８】
前記３−Ｄメッシュを変形するステップは、前記３−Ｄメッシュに関連付けられた元の表面詳細の保存と、ユーザ選択の変形位置と、前記ボリュメトリックグラフ・ラプラシアンによって指定されるボリュメトリックディテールの保存とのバランスを取るステップをさらに含むことを特徴とする請求項１２に記載の方法。
【請求項１９】
前記オリジナルメッシュの複数の頂点のうちの各頂点を前記頂点の法線とは反対の方向に反復的にずらす簡略化エンベロープを使用して、前記３−Ｄメッシュの内側に単純格子グラフ構造を生成するステップと、
前記オリジナルメッシュの各頂点を前記オリジナルメッシュに対応する表面の外側方向に反復的にずらすことによって、外側グラフを生成するステップであって、前記外側グラフは、前記３−Ｄメッシュの外側の頂点を含むステップと、
ボリュメトリックグラフを生成するために、前記内側および外側グラフと前記オリジナルメッシュとの間に連結を構築するステップと、
をさらに含むことを特徴とする請求項１２に記載の方法。
【請求項２０】
辺消去および平滑化操作を使用して、前記ボリュメトリックグラフを簡略化するステップをさらに含むことを特徴とする請求項１９に記載の方法。
【図１】
【図６】
【図７】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図８】
【図９】
【図１０】
【図６】
【図７】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図８】
【図９】
【図１０】
【公開番号】特開２０１２−１７８１７６（Ｐ２０１２−１７８１７６Ａ）
【公開日】平成２４年９月１３日（２０１２．９．１３）
【国際特許分類】
【出願番号】特願２０１２−１１３０６１（Ｐ２０１２−１１３０６１）
【出願日】平成２４年５月１７日（２０１２．５．１７）
【分割の表示】特願２００８−５１８４５９（Ｐ２００８−５１８４５９）の分割
【原出願日】平成１８年６月２２日（２００６．６．２２）
【出願人】（５０００４６４３８）マイクロソフト コーポレーション (3,165)
【Ｆターム（参考）】
【公開日】平成２４年９月１３日（２０１２．９．１３）
【国際特許分類】
【出願日】平成２４年５月１７日（２０１２．５．１７）
【分割の表示】特願２００８−５１８４５９（Ｐ２００８−５１８４５９）の分割
【原出願日】平成１８年６月２２日（２００６．６．２２）
【出願人】（５０００４６４３８）マイクロソフト コーポレーション (3,165)
【Ｆターム（参考）】
[ Back to top ]