(57)【要約】【課題】  伸縮主導型のメッシュパラメータ化を実行する方法を提供すること。【解決手段】  伸縮主導型のメッシュパラメータ化を実行する方法であって、スペクトル分析を計算してメッシュをパラメータ化するステップと、伸縮最適化計算を反復し、初期パラメータ化をさらに最適化するステップとを備えることを特徴とする方法。【選択図】  図１ 
2006012147.tif 000002
【特許請求の範囲】
【請求項１】
スペクトル分析を計算してメッシュをパラメータ化するステップと、
伸縮最適化計算を反復し、前記初期パラメータ化をさらに最適化するステップと
を備えたことを特徴とする伸縮主導型のメッシュパラメータ化を実行する方法。
【請求項２】
前記スペクトル分析によって複数の点間のマニホールドに沿った測地的な距離を計算することを特徴とする請求項１に記載の伸縮主導型のメッシュパラメータ化を実行する方法。
【請求項３】
高速なマッチング方法を使用して測地的な距離を計算することを特徴とする請求項２に記載の伸縮主導型のメッシュパラメータ化を実行する方法。
【請求項４】
前記測地的な距離に多次元のスケーリングを適用し、同様なペアごとの距離を有する、低次元空間に埋め込まれた点の集合を検出するステップをさらに備えたことを特徴とする請求項２に記載の伸縮主導型のメッシュパラメータ化を実行する方法。
【請求項５】
サーフェスのスペクトル分析を計算して初期パラメータ化を提供するステップと、
伸縮最適化計算を反復し、前記初期パラメータ化をさらに最適化するステップと
を備えたことを特徴とする伸縮主導型のメッシュパラメータ化を実行する方法。
【請求項６】
伸縮を閾値と比較するステップをさらに備えたことを特徴とする請求項５に記載の伸縮主導型のメッシュパラメータ化を実行する方法。
【請求項７】
前記伸縮が前記閾値より小さい場合に前記計算を停止するステップをさらに備えたことを特徴とする請求項５に記載の伸縮主導型のメッシュパラメータ化を実行する方法。
【請求項８】
サーフェスを分割し、スペクトルクラスタリングによって複数のチャートにチャート化するステップを備えたことを特徴とする伸縮主導型のメッシュパラメータ化を実行する方法。
【請求項９】
前記スペクトルクラスタリングは、大きな固有値を使用してサーフェスを分割するステップを含むことを特徴とする請求項８に記載の伸縮主導型のメッシュパラメータ化を実行する方法。
【請求項１０】
前記スペクトルクラスタリングは、スペクトル分析を使用して複数の代表的な頂点を計算するステップをさらに含むことを特徴とする請求項９に記載の伸縮主導型のメッシュパラメータ化を実行する方法。
【請求項１１】
前記複数の代表的な頂点を使用して複数のチャートを成長させるステップをさらに備えたことを特徴とする請求項９に記載の伸縮主導型のメッシュパラメータ化を実行する方法。
【請求項１２】
サーフェスのスペクトル分析から固有値をランク付けする手段と、
上位ｎ個の固有値と上位ｎ個の固有ベクトルとを選択する手段と、
メッシュの頂点について複数のｎ次元埋め込み座標を計算する手段と、
前記複数のｎ次元埋め込み座標の代表を設定する手段と、
互いに近すぎると認識された複数の前記代表を削除する手段と、
前記メッシュをｍ個の要素に分割する手段と
を備えたことを特徴とする伸縮主導型のメッシュパラメータ化を実行する方法。
【請求項１３】
グラフカットによって、対応する複数のチャート間の境界を最適化するステップを備えたことを特徴とするテクスチャマップを作成する方法。
【請求項１４】
前記グラフカットのステップは、スペクトルクラスタリングによってチャートを第１の領域と第２の領域に分割するステップをさらに含むことを特徴とする請求項１３に記載のテクスチャマップを作成する方法。
【請求項１５】
前記グラフカットのステップは、第３の中間領域を生成するステップをさらに含むことを特徴とする請求項１４に記載のテクスチャマップを作成する方法。
【請求項１６】
前記第３の中間領域は、前記第１の領域と前記第２の領域との境界に沿って構成されることを特徴とする請求項１５に記載のテクスチャマップを作成する方法。
【請求項１７】
前記チャートの境界は、前記第１の領域で決定する埋め込みと前記第２の領域で決定する埋め込みとの間で隣接する三角形のＧＤＤがバランスをとるように選択されることを特徴とする請求項１４に記載のテクスチャマップを作成する方法。
【請求項１８】
前記チャートの境界は
【数１】
2006012147.tif 000022
の形をとる埋め込みの歪みを評価するＧＤＤバランスの基準を使用して選択されることを特徴とする請求項１７に記載のテクスチャマップを作成する方法。
【請求項１９】
前記チャートの境界は、２面角の大きな複数のエッジによる滑らかなカットを備えることを特徴とする請求項１４に記載のテクスチャマップを作成する方法。
【請求項２０】
前記複数の滑らかなエッジは、
【数２】
2006012147.tif 000023
を利用して選択されることを特徴とする請求項１９に記載のテクスチャマップを作成する方法。
【請求項２１】
前記チャートの境界は、第１の形
【数３】
2006012147.tif 000024
をとる第１項と第２の形
【数４】
2006012147.tif 000025
をとる第２項との重み付きの和によって選択されることを特徴とする請求項１４に記載のテクスチャマップを作成する方法。
【請求項２２】
前記第１項は、定数を乗じることで重み付けし、前記第２項は、１から定数を引いた値を乗じることで重み付けすることを特徴とする請求項１４に記載のテクスチャマップを作成する方法。
【請求項２３】
伸縮の基準を満足するまで複数のチャートの各チャートを再帰的に改善するステップを備えたことを特徴とする伸縮主導型のメッシュパラメータ化を実行する方法。
【請求項２４】
伸縮を代行する方法によって複数のチャートを生成するようにチャート化するステップを備えたことを特徴とするテクスチャマップを作成する方法。
【請求項２５】
前記複数のチャートの前記伸縮を最適化するステップは、第１の複数のチャートを生成するステップを含むことを特徴とする請求項２４に記載のテクスチャマップを作成する方法。
【請求項２６】
前記複数のチャートの前記伸縮を最適化するステップは、最適化にはその他の複数のチャートが最適化に必要か否かを判断するように繰り返し実行するステップを含むことを特徴とする請求項２４に記載のテクスチャマップを作成する方法。
【請求項２７】
導かれた伸縮のパラメータ化を最適化するステップは、前記伸縮を閾値と比較するステップをさらに含むことを特徴とする請求項２６に記載のテクスチャマップを作成する方法。
【請求項２８】
前記導かれた伸縮のパラメータ化が閾値より小さい場合、最適化を終了することを特徴とする請求項２７に記載のテクスチャマップを作成する方法。
【請求項２９】
サーフェスのスペクトル分析から生成された複数の固有値λiと対応する複数の固有ベクトルを（λ1≧λ2≧．．．≧λN）となるようにランク付けするステップと、
λn／λn+1の値が最大になるような上位ｎ個の固有値の集合と固有ベクトルの集合とを選択するステップと、
複数のメッシュの各頂点ｉについてｎ次元の埋め込み座標の集合を計算するステップと、
前記ｎ個の埋め込み座標のそれぞれについて、最大の座標値をとる第１の頂点と最大の座標値をとる第２の頂点とを検出し、前記最大の座標値をとる第１の頂点と前記最大の座標値をとる第２の頂点とを第１の複数の２ｎ個の代表点として設定するステップと、
前記複数の代表点で互いに非常に近い点のそれぞれを削除し、ｍ≦２ｎであるｍ個の代表点からなる第２の集合を生成するステップと、
サーフェスのスペクトル分析で計算した前記測地的な距離を使用して前記代表点の周囲のチャートを同時に成長させ、前記メッシュをｍ個の要素に分割するステップと
を備えたことを特徴とするスペクトル分析によるチャート化を実行する方法。
【請求項３０】
スペクトル分析によるモデルの歪みを構成するステップと、
前記モデルの前記歪みに関するクラスタリングを実行するステップと
を備えたことを特徴とする伸縮主導型のメッシュパラメータ化を実行する方法。
【請求項３１】
信号に関する演繹的知識に基づいてサーフェスを複数のチャートに分割するステップを備えたことを特徴とするチャート化の方法。
【請求項３２】
前記分割するステップは、複数の頂点間のペアごとの信号距離を計算するステップに基づくことを特徴とする請求項３１に記載のチャート化の方法。
【請求項３３】
前記複数の頂点間の前記複数のペアごとの信号距離は、パスに沿って隣接する点の複数のペア間の複数の信号差の合計であることを特徴とする請求項３２に記載のチャート化の方法。
【請求項３４】
前記信号は、カラーであることを特徴とする請求項３１に記載のチャート化の方法。
【請求項３５】
前記複数の頂点間の前記複数のペアごとの信号距離は、測地的な距離と信号距離との組み合わせであることを特徴とする請求項３４に記載のチャート化の方法。
【請求項３６】
前記測地的な距離と信号距離との組み合わせは
【数５】
2006012147.tif 000026
で表されることを特徴とする請求項３５に記載のチャート化の方法。
【請求項３７】
複数の点間でマニホールドに沿った信号距離を計算することによってスペクトル分析を計算してメッシュをパラメータ化するステップを備えたことを特徴とする伸縮主導型のメッシュパラメータ化を実行する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、コンピュータグラフィックスの生成に関する。特に、実質的に２次元での３次元オブジェクトのレンダリングに関する。
【背景技術】
【０００２】
テクスチャを３次元サーフェスにマップするためのコンピュータグラフィック技術は、ソフトウェアおよびハードウェアにおいて開発され、実装されてきた。こうした従来の実装では、通常は、メッシュ構造で定義された長方形のテクスチャサンプルを、レンダリングするサーフェスにマップする。
【０００３】
【特許文献１】米国特許出願第１０／１３８，２８９号，"System and Method for Providing Signal-Specialized Paramaterization"
【特許文献２】米国特許出願第１０／１３８，７５１号，"System and Method for Optimizing Geometric Stretch of a Paramaterization Scheme"
【発明の開示】
【発明が解決しようとする課題】
【０００４】
こうしたテクスチャサンプルまたはマップは、一定の限界を示す傾向があり、このようなマップからレンダリングされる画像の品質に影響する恐れがある。
【課題を解決するための手段】
【０００５】
読者の基本的な理解が得られるように、本開示の概要について以下に簡単に説明する。以下に示す解決手段は、本開示の広義の概要ではない。また、本発明の重要／不可欠な要素を特定せず、本発明の範囲を限定しない。唯一の目的は、後述の実施形態に関する説明の準備として、本明細書に開示するいくつかの概念を簡略化した形で示すことである。
【０００６】
本実施例では、３次元オブジェクトを２次元にレンダリングする方法を提供する。通常は、輪郭をマップするオブジェクト上に１つまたは複数のグリッドを配置する。オブジェクトのサーフェスは多くのサブサーフェス（それぞれに独自のグリッドを配置する）に分割でき、サーフェスの標高の変化に応じて伸縮の歪み（ｓｔｒｅｔｃｈ  ｄｉｓｔｏｒｔｉｏｎ）を小さくするようにできる。
【０００７】
本実施例では、Ｉｓｏ−Ｃｈａｒｔと呼ばれる完全自動の方法を提供し、任意のメッシュに関するテクスチャアトラス（ｔｅｘｔｕｒｅ  ａｔｌａｓｅｓ）を作成できる。この例では、チャートをパラメータ化する場合（たとえば歪みの測定）だけでなく、チャートを作成する場合にも伸縮を考慮する。出力されるアトラスは、ユーザーが指定する定数で伸縮の限界を指定し、ユーザーはその伸縮に照らしてチャートの数を調整できる。
【０００８】
本発明の多くの付帯機能は、添付の図面と共に以下の詳細な説明を参照することでよりより深く理解され、明らかになるであろう。
【０００９】
本特許または出願には、カラーで描かれた少なくとも１枚の図面が含まれる。カラーの図面を伴う本特許または特許出願広報のコピーは、請求あり次第、必要な料金を支払うことで事務所から提供される。上記およびその他の機能と利点については、添付の図面を参照しながら以下の実施形態の説明を読むことでより深く理解できるであろう。
【００１０】
添付の図面において、同じ参照番号は同種の要素を示している。
【発明を実施するための最良の形態】
【００１１】
添付の図面と共に下記で提供される詳細な説明は、本実施例の説明として意図されており、本発明を構成または利用できる唯一の形態を示すものではない。以下の説明は、図示された実施例に関連つけながら、本発明の機能および本発明を構成し、操作する一連のステップを示している。示された一連の操作およびステップは例示的なものであること、およびその順序を変更しても同じ結果が得られることは、当業者には言うまでもない。同等の機能およびシーケンスは、本発明の別の実施例で実現することもできる。
【００１２】
本実施例は、本明細書では２次元のコンピュータグラフィックスシステムにおける実装として説明され、図示されているが、説明されているシステムは例として示されており、限定を意味するものではない。当業者には言うまでもないが、本発明は、コンピュータグラフィックスなどで生成される３次元モデルを含むさまざまな画像生成システムで利用するのに適している。
【００１３】
（序論）
提示する実施例には、複数のチャートを使用して任意のメッシュをパラメータ化する方法（「メッシュのパラメータ化」）が含まれる。チャートに分解し、各チャートをパラメータ化するステップは、自動化でき、頂点間の測地的な距離の行列に関するスペクトル分析の概念とパラメータ化の伸縮に基づくことができる。
【００１４】
メッシュのパラメータ化は、３次元グラフィックスのレンディション（ｒｅｎｄｉｔｉｏｎ）に利用できる。多くの信号を、法線、カラー、あるいはシェーディングのパラメータを含む３次元グラフィックスのレンダリングで使用でき、３次元サーフェスに関連付けてリアルな画像を作成することができる。特に、「テクスチャマップ」を使用してサーフェスのテクスチャを記述すると、よりリアルな画像に作り直すことができる。
【００１５】
以下に説明する例では、最小限のテクスチャサンプルを使用して忠実に表現するためのテクスチャマップを自動的に生成する方法を提供する。また、以下で説明する実施例は、テクスチャ合成、ジオメトリ圧縮、再メッシュ（ｒｅｍｅｓｈｉｎｇ）など、多くの幾何学的な処理に適用できる。
【００１６】
この種の分解は、マップ領域の選択の仕方によって伸縮を最小にする傾向がある。このように、画像をコンピュータグラフィックのレンダリング用にモデル化する上で、任意のメッシュからテクスチャ画像への１つの展開によって、再生される画像に歪みの大きな領域が生じる可能性がある。したがって、一般にメッシュは、チャートの集合に分割される。このチャートの集合によって、テクスチャアトラスを構成する。各チャートには、テクスチャドメインの領域ごとに一連のパラメータが割り当てられ、これらのパラメータ化は、集合的にアトラスを作成する。
【００１７】
Ｉｓｏ−Ｃｈａｒｔと呼ばれる完全自動の方法によって、任意のメッシュに関するテクスチャアトラスを作成できる。この方法では、チャートをパラメータ化する場合（たとえば変形を測定する場合）だけでなく、チャートを構成する場合にも伸縮を考慮する。出力されるアトラスは、ユーザーが指定する定数で伸縮の限界を課すことができるので、ユーザーはその伸縮に照らしてチャートの数を調整できる。
【００１８】
スペクトル分析を使用した伸縮主導型のメッシュパラメータ化のアプローチは、１）局所計量テンソル（ｌｏｃａｌ  ｍｅｔｒｉｃ  ｔｅｎｓｏｒ）のトレースの表面積分に基づく、伸縮を最小にするパラメータ化、および２）メッシュの頂点のペア間の平方された測地的な距離の行列の固有分析に基づく「ｉｓｏｍａｐ」またはＭＤＳ（「ｍｕｌｔｉ−ｄｉｍｅｎｓｉｏｎａｌ  ｓｃａｌｉｎｇ（多次元スケーリング）」）の２つの技術を組み合わせている。通常、わずか数回の繰り返しによる非線形の伸縮最適化要求がＭＤＳパラメータ化に適用され、伸縮の小さいアトラスが得られる。２つのパラメータ化の間に見られる密接な関係によって、ＭＤＳに基づくスペクトルクラスタリング（ｓｐｅｃｔｒａｌ  ｃｌｕｓｔｅｒｉｎｇ）を適用してメッシュを伸縮の小さいチャートに分割できる。グラフカットアルゴリズムを適用してチャートの境界を最適化し、伸縮をさらに最小化し、シャープなフィーチャを描き、蛇行を防ぐ。
【００１９】
スペクトル分析を使用した伸縮主導型のメッシュパラメータ化の方法は、チャート数が少なく、伸縮の小さなテクスチャアトラスを迅速に作成する傾向があり、幾何学的な再メッシュのようなアプリケーションに有効である。別の実施例では、１つの拡張、すなわち信号専用のアトラスの作成について説明しており、サーフェス信号の効率的なサンプリングを傾向があり、チャートの構成における信号の伸縮を考慮することで、より優れたテクスチャマップを作成する傾向がある。
【００２０】
パラメータ化は、テクスチャマッピング、モーフィング、編集、再メッシュ、圧縮など、多くの幾何学処理アルゴリズムで使用できる。任意のメッシュをパラメータ化するために、テクスチャアトラスを作成してもよい。モデル化するターゲットサーフェスは、通常はまずチャートの集合に分割され（いわゆるチャート化）、このチャートがパラメータ化され、テクスチャドメインに圧縮される（ｐａｃｋｅｄ）。
【００２１】
特に、テクスチャアトラスを作成するステップには、サーフェスにメッシュを適用してよりリアルな画像を作成しようとした場合に、距離がどの程度縮まったか、あるいは「伸縮」したかに関する考察を含めることができる。
【００２２】
テクスチャアトラスから再作成される最終的な画像の歪みは、さまざまな方法で修正でき、最小化できる。１つの方法には、テクスチャアトラスにおけるチャートの適切な選択が含まれる。別の方法では、アトラスにおけるチャートの数を変更できる。このように、ターゲットサーフェスをチャートに分割する方法は、３次元オブジェクトの外観を２次元にレンダリングする場合に有効である。
【００２３】
３Ｄサーフェスは２Ｄ平面と等角（ｉｓｏｍｅｔｒｉｃ）ではないので、パラメータ化によって歪みが発生する。角度や領域がどの程度維持されるか、あるいはパラメータの距離がサーフェス上でどの程度伸縮、あるいは縮まったかなど、さまざまな方法で歪みを評価できる。スペクトル分析を使用した伸縮主導型のメッシュパラメータ化は、距離の歪み、特にサーフェス上の局所的な距離の平均および最悪の伸縮を評価する幾何学的な伸縮の定義に注目する。
【００２４】
伸縮を最小化するには、通常、非線形の最適化を利用する。伸縮の最小化は低速になる傾向があり、チャートのコンパクトさと平面性とに基づいてはっきりとしたフィーチャまたはクラスタをカットする、関連のない発見的方法を優先してチャートを構成する場合、伸縮が軽視される傾向がある。これは、チャートの伸縮を最小にする埋め込みの計算にコストがかかる場合正しく、あらゆるチャート分割についてこの計算を行っても全く役に立たない傾向があるためである。
【００２５】
これを改善するために、ＩｓｏＭａｐと呼ばれる非線形次元収縮が適用される。ＩｓｏＭａｐは、メッシュ上の２頂点間の測地的な（ｇｅｏｄｅｓｉｃ）距離の歪みを最小にする傾向がある。こうした適用への鍵となるのは、測地的な距離の歪みと伸縮は全く別々に定義されているにもかかわらず密接に関連するという事実である。ＩｓｏＭａｐは、このようにアトラスを生成するときに２つの機能を提供する傾向がある。ＩｓｏＭａｐは、スペクトル分析と呼ばれる効果的な方法を提供し、パラメータ化されても伸縮の小さい幾何学的に意味のある大きな要素（動物の付属器官など）に分解する。また、ＩｓｏＭａｐでは、余分な計算をせずに各要素の初期パラメータ化を計算できる。実際に、通常は伸縮を最小化するための適切な開始点が提供され、数回の繰り返しによる非線形伸縮最適化で迅速に収束し、「折りたたみ（ｆｏｌｄｏｖｅｒｓ）」の問題を容易に除去できる。
【００２６】
スペクトル分析を使用した伸縮主導型のメッシュパラメータ化の機能は、測地的な距離の行列のスペクトル分析に基づいてクラスタに分割する伸縮主導型のチャート化の方法である。ユーザーは、伸縮の限界を指定すると同時に、通常は少ないチャート数を維持することができる。こうしたスペクトル分析により、同時にチャートの伸縮の小さいパラメータ化が迅速に実現する。グラフカットを使用してチャートの境界を最適化し、容量の基準を変更して測地的な距離の歪みとその結果の伸縮を考慮することで、２つの基準の間に見られる関係を解明できる。スペクトル分析を使用した伸縮主導型のメッシュパラメータ化は、幾何学的な要素が周期構造（管状構造）をとる場合に、「専用のスペクトルクラスタリング」を使用することで一般により適切なチャートを作成する。最後に、このアプローチは信号専用のアトラスの作成に一般化される。スペクトル分析を使用した伸縮主導型のメッシュパラメータ化は、そのチャートの分割およびパラメータ化を特定の信号に適応させる最初の方法であり、法線マップまたはカラーマップなどの特定の信号に適応する。
【００２７】
（プロセスの概要）
図１は、スペクトル分析を使用した伸縮主導型のメッシュパラメータ化を示すブロック図である。スペクトル分析を使用した伸縮主導型のメッシュパラメータ化のアプローチは、トップダウンの伸縮主導型の方法と考えることができる。ブロック１０１でサーフェスとユーザー指定の伸縮の値が指定されると、ブロック１０２でサーフェスのスペクトル分析が計算され、初期パラメータ化が提示される。ブロック１０２については、後の「サーフェスのスペクトル分析」の項でさらに詳しく説明する。ブロック１０３で、数回の繰り返しによる従来の伸縮最適化が実行される。ブロック１０４で、計算されたパラメータ化が閾値より小さい場合は、プロセスが停止する。ブロック１０５で、スペクトルクラスタリングを実行してサーフェスをチャートに分割する。ブロック１０６で、グラフカット技術を使用してチャート境界の最適化を実行する。ブロック１０７で、伸縮の基準を満足するまでチャートが再帰的に分割される。
【００２８】
このプロセスの結果は、パラメータ化によって伸縮の限界を指定したチャートの集合である。チャートの位相は、明示的にチェックする必要はなく、伸縮主導型のプロセスによって最終的にすべてのチャートが位相的（ｔｏｐｏｌｏｇｉｃａｌ）ディスクに確実に細分され、それ以外の場合、パラメータ化の伸縮は無限である。パラメータ化のドメインが、それ自体と重複せず、その典型的に稀な場合においては細分しないようにさせるチェックが行われる。後処理のステップとして、小さなチャートをマージ（ｍｅｒｇｅｄ）したチャートのパラメータ化による伸縮がユーザー指定の伸縮の値を下回る場合、こうしたチャートが共にマージされる。
【００２９】
歪みは、幾何学的伸縮または信号の伸縮に関する２つのノルム（ｎｏｒｍｓ）を使用して限界を設定する。Ｌ２ノルムは（γ２ｍａｘ＋γ２ｍｉｎ）／２をサーフェス上で積分し、全体の平方根をとったものである。Ｌ∞ノルムはサーフェス全体のｍａｘ｛γｍａｘ，１／γｍｉｎ｝を最大にする。ただし、γｍａｘとγｍｉｎは、サーフェス上のスカラー関数であり、任意の点におけるテクスチャ空間からモデルまたは信号空間へのアフィンマッピング（ａｆｆｉｎｅ  ｍａｐｐｉｎｇ）のヤコビアン行列式の唯一の最大値と最小値である。Ｌ∞ノルムの収縮１／γｍｉｎを含めることは、アンダーサンプリングにペナルティーを科すための修正である。幾何学的伸縮または信号の伸縮に関する２つのノルムを使用した歪みの限界設定については、参考として本明細書に引用する２００２年５月１日に出願された特許文献１に説明されている。
【００３０】
図２は、うさぎのモデルをチャート化し、パラメータ化した結果を示している。ウサギのモデル２０１用に作成されたＩｓｏ−Ｃｈａｒｔアトラス２００を示している。図に示すように、ウサギのサーフェスは１５の大きなチャートに分割され、平面化した場合に通常は従来の方法より伸縮が小さくなる（Ｌ２＝１．０１、Ｌ∞＝２．２６）。図のように、頭、耳、体などのモデルの要素は大きなチャートに分解される。この例では、計算には約１分かかる。
【００３１】
（チャート化とパラメータ化）
チャート化とパラメータ化には、サーフェスのスペクトル分析の適用、スペクトル分析による伸縮の減少、サーフェスのスペクトルクラスタリング、最適なパラメータ境界の計算、中間領域の埋め込み、管形状のスペクトルクラスタリング、実装、および信号専用のアトラス作成が含まれる。
【００３２】
（サーフェスのスペクトル分析）
このプロセスは、従来の次元収縮法ＩｓｏＭａｐ（アイソメトリックフィーチャマッピング（ｉｓｏｍｅｔｒｉｃ  ｆｅａｔｕｒｅ  ｍａｐｐｉｎｇ））に基づいている。高次元の点の集合が与えられると、ＩｓｏＭａｐは隣接する点間の一連のホップ（ｈｏｐｓ）としてのマニホールドに沿った測地的な距離を計算する。次に、こうした測地的な距離にＭＤＳ（ｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌ  ｓｃａｌｉｎｇ：多次元のスケーリング）を適用し、２点間の距離が同じ低次元空間に埋め込まれた点の集合を検出する。
【００３３】
このＩｓｏＭａｐの適用は、「サーフェスのスペクトル分析」と呼ばれており、その計算の概要については以下で説明する。Ｎ個の頂点ｘｉを有するサーフェスが指定された場合は次のようになる。ただし、各ｘｉは３Ｄ空間の位置である。
【００３４】
・サーフェスの頂点間の測地的な距離の平方の対称行列ＤＮを計算する。
【００３５】
・次に、ＤＮに２重中心化（ｄｏｕｂｌｅ  ｃｅｎｔｅｒｉｎｇ）と標準化を適用し、ＢＮ＝−（１／２）ＪＮＤＮＪＮを求める。ただし、ＪＮはＪＮ＝Ｉ−（１／Ｎ）ｌｌＴ（Ｉは単位行列、ｌは長さＮの１つのベクトル）で定義されるＮ×Ｎの中心化行列である。これによって、計算された点の集合の重心を原点にするという制約が発生する。  
・ＢＮの固有値λｉ、および対応する固有ベクトルｖｉ（ｉ＝１，２，．．．，Ｎ）を計算する。  
・元のサーフェスの各頂点ｉについて、その新しい空間への埋め込みは、そのｊ番目の成分が
【００３６】
【数１】
2006012147.tif 000003
【００３７】
で指定されるＮ次元ベクトルｙｉである。
【００３８】
ＢＮの固有値λｉと対応する固有ベクトル
【００３９】
【数２】
2006012147.tif 000004
【００４０】
（ｉ＝１，２，．．．，Ｎ）は、サーフェスの形状のスペクトル分解を構成する。ベクトルｙｉは、歪曲したモデルを表しており、元の頂点ｘｉと１対１対応である。大きな固有値に対応する固有ベクトルは、サーフェス上の全体的な低周波数のフィーチャを表し、小さな固有値に対応する固有ベクトルは、サーフェス上の高周波数の細部を表す。高エネルギー、低周波数のコンポーネントをチャート化およびパラメータ化の基盤と考えるのが自然である。
【００４１】
Ｎ個の頂点を伴うサーフェス全体を表現するにはＮ個の固有値が必要であるが、通常はその中の少数がエネルギーを支配する。図２に示すうさぎのモデルでは、上位５個の固有値がエネルギーの平方の８５％以上を占める。つまり、
【００４２】
【数３】
2006012147.tif 000005
【００４３】
である。したがって、ｎ（＜＜Ｎ）個の非常に大きな固有値と、対応する固有ベクトルのみが計算され、すべてのベクトルに関するｎ次元の埋め込みが導かれる。
【００４４】
このｎ次元の埋め込みの歪みは、すべての頂点に関する測地的な距離の歪みの合計として計算できる。各頂点ｉについて、埋め込みによるその測地的な距離の歪み（「ＧＤＤ」）は次のように定義される。
【００４５】
【数４】
2006012147.tif 000006
【００４６】
ただし、
【００４７】
【数５】
2006012147.tif 000007
【００４８】
は頂点ｉのｎ次元の埋め込み座標であり、ｄｇｅｏ（ｉ，ｊ）は頂点ｉとｊとの測地的な距離である。この定義は、三角形の３つの頂点の歪みを平均することで頂点から三角形に拡張でき、後述の「最適なパーティション境界の計算」の項で使用される。
【００４９】
ｎ＝２の場合に、サーフェスのスペクトル分析により、すべての頂点に関するＧＤＤの平方和を最小にするサーフェスのパラメータ化が導かれる。したがって、サーフェスのスペクトル分析は、チャート化のための分解とパラメータ化との２つの問題に同時に適用できる。
【００５０】
多角形モデルのサーフェス点間の測地的な距離を計算するには、Ｏ（Ｎ２  ｌｇ  Ｎ）で動作し、メッシュトライアングルをカットするパスが可能なので、通常はＤｉｊｋｓｔｒａグラフ検索法よりさらに正確な結果を得る従来の最も高速のマッチング方法が使用される。
【００５１】
（スペクトル分析と伸縮）
ＧＤＤを最小にするパラメータ化と伸縮を最小にするパラメータ化とは、いずれも距離の歪みに注目している。やはりＧＤＤは、さまざまな点で伸縮とは異なる。ＧＤＤは、局所的でなく全体的である。つまり、１つの点のヤコビアン行列によって導かれる局所的な伸縮でなく、サーフェス全体で任意にかけ離れた頂点間の距離を考慮する。ＧＤＤは、比率ベースでなく差異ベースである。つまり、単位長さの正接ベクトルがどれだけ伸縮したかでなく、元の距離とパラメータの距離との差異にペナルティーを科している。さらに、ＧＤＤは、連続的でなく離散的である。つまり、２頂点間の距離の歪みのみを考慮しており、各三角形や各方向の伸縮は考慮しない。
【００５２】
スペクトル分析の離散性（２頂点間のみについて距離の歪みを測定する）は、トライアングルフリップ（ｔｒｉａｎｇｌｅ  ｆｌｉｐｓ）に関する問題の原因となる。本発明のスペクトル分析と伸縮とを計算するプロセスによって、単純な解決が得られる。トライアングルフリップは無限の伸縮を発生すると定義されているが、本発明のアルゴリズムは、通常、伸縮がユーザー閾値を超えるチャートを分割するので、任意の有限の閾値を指定することで最終的なアトラスにフリップがないことが保証される。
【００５３】
スペクトル分析では、通常、一般的な非線形最適化でなく低次元の固有値問題の解決を必要とする。この計算は、以下で説明する「ランドマーク（ｌａｎｄｍａｒｋ）」拡張をさらに使用することで高速化できる。伸縮とＧＤＤとの相違にもかかわらず、スペクトル分析によって通常は伸縮が小さくなるという効果がある。
【００５４】
（サーフェスのスペクトルクラスタリング）
スペクトル分析によって導かれるパラメータ化がユーザーの伸縮の閾値を満足しない場合、複数の小さなチャートに分割される。動物の頭、耳、足、尾など、モデルの全体的なフィーチャは大きな固有値に対応することを想起し、このようなフィーチャを使用して分割する。スペクトル分析の結果を使用していくつかの代表的な頂点が計算される。次に、「サーフェスのスペクトルクラスタリング」と呼ばれる方法で、こうした代表的な頂点を中心として同時にチャートが構成される。このプロセスは次のようになる。  
１．  固有値λｉと、対応する固有ベクトル
【００５５】
【数６】
2006012147.tif 000008
【００５６】
をサーフェスのスペクトル分析から（λ１≧λ２≧．．．≧λＮ）のようにランク付けする。  
２．  λｎ／λｎ＋１が最大になるような上位ｎ個の固有値と固有ベクトルを選択する。
３．  メッシュの各頂点ｉについて、そのｎ次元の埋め込み座標
【００５７】
【数７】
2006012147.tif 000009
【００５８】
を計算する。  
４．  ｎ個の埋め込み座標のそれぞれについて、座標値が最大と最小の２つの頂点を検出し、これを２ｎ個の代表点として設定する。  
５．  互いに非常に近い代表点を除去し、ｍ（≦２ｎ）個の代表点を得る。  
６．  サーフェスのスペクトル分析で計算した測地的な距離を使用して、代表点の周囲にチャートを同時に構成することで、メッシュをｍ個の要素に分割する。
【００５９】
ステップ２は、結果としてエネルギーと固有値の数を関連付ける曲線の「屈曲部」を検出する相対エラーの閾値を与える。ｎの値は形状の複雑さの尺度である。つまり、ｎ＜３はほとんど平坦な形状を表し、ｎが大きい場合はかなり細かい複雑な形状を表す。残りのＮ−ｎ個の固有値を除去し、高周波数の細部を無視して分割結果のチャート数が多すぎないようにする。本実装では、さらにｎ≦１０に制限されており（「実装の詳細」の項を参照）、結果として最大サブチャート数が制限される。
【００６０】
ステップ４でさまざまな次元から計算された代表点は近くて冗長な場合があるので、ステップ５でこれを削除する。距離の閾値として、入力メッシュの平均エッジ長の１０倍を使用する。ステップ６で、三角形から代表点までの測地的な距離が、三角形の３つの頂点と代表点との測地的な距離の平均として計算される。
【００６１】
（最適なパーティション境界の計算）
チャートを分割した後で、チャート間の境界が最適化される。チャートの境界は、１）曲率の大きな領域をぎざぎざになりすぎずにカットする、２）境界を設定するチャートの埋め込みの歪みを最小にするという２つの目標に適合する必要がある。
【００６２】
第１の目標には、チャートのコンパクトさを表すさまざまな測定値を最小にしながら、２面角の大きいエッジに沿った最短距離のチャートカットを選択する従来の方法で対処している。メッシュのパラメータ化に適用する概念である従来のグラフカット法を使用してメッシュを分解する。第２の目標は、伸縮を最小にする分割に関連する。
【００６３】
第２の目標には、グラフカット（ｇｒａｐｈ  ｃｕｔ）の問題のような最適境界値問題を公式化することで対処できる。簡潔にするために、サーフェスを２つに分割する場合について説明する。３つ以上に分割する場合は、隣接するチャートのそれぞれについてさらに考察する。
【００６４】
図３は、グラフカット（ｇｒａｐｈ  ｃｕｔ）の問題として最適なパーティション境界の検出を示している。境界を検出するときに、形状３００は３つの要素、すなわち外側の領域３０１（赤）、３０２（青）、中間の領域３０３（緑）に分解される。グラフ３０４は、中間の領域３０３について作成されている。２つのチャート３０２と３０１との間の最適な境界を求める。初期分割は、サーフェスのスペクトルクラスタリングを使用して生成される。中間の領域３０３は、最初の分割境界のいずれかの側に領域を拡張することで生成される。中間の領域のサイズは、分割されないパッチ（ｐａｔｃｈ）の領域全体に比例する。すべての例に３０％を使用する。ここで、ファジークラスタリングとファジーカット（ｆｕｚｚｙ  ｃｌｕｓｔｅｒｉｎｇ  ａｎｄ  ｃｕｔｓ）による従来の階層メッシュ分解の方法の拡張を使用して、中間の領域３０３から方向のないフローネットワークグラフ（ｆｌｏｗ  ｎｅｔｗｏｒｋ  ｇｒａｐｈ）３０５を構成する。この方法では、メッシュの隣接する２つの三角形ｆｉとｆｊ間の「容量」は次のように定義される。  
ｃ（ｆｉ，ｆｊ）＝αｃａｎｇ（ｆｉ，ｆｊ）＋（１−α）ｃｄｉｓｔｏｒｔ（ｆｉ，ｆｊ）
（２）
【００６５】
数式（２）の第１項は、２面角の大きなエッジに沿ったぎざぎざのないカットという第１の目標に対応する。これは次のようにして得られる。
【００６６】
【数８】
2006012147.tif 000010
【００６７】
ただし、ｄａｎｇ（ｆｉ，ｆｊ）は（１−ｃｏｓαｉｊ）、αｉｊは三角形ｆｉとｆｊの法線間の角度、ａｖｇ（ｄａｎｇ）は隣接する三角形間の平均角距離である。
【００６８】
式（２）の第２項は埋め込みの歪みを評価し、次のように定義される。
【００６９】
【数９】
2006012147.tif 000011
【００７０】
ｄｄｉｓｔｏｒｔ（ｆｉ，ｆｊ）＝｜ＧＤＤＡ（ｆｉ）−ＧＤＤＢ（ｆｉ）｜＋｜ＧＤＤＡ（ｆｊ）−ＧＤＤＢ（ｆｊ）｜      （５）
【００７１】
ただし、ＧＤＤＡ（ｆｉ）とＧＤＤＢ（ｆｉ）は、それぞれ外側の領域３０２または３０１によって導かれる埋め込みによる三角形ｆｉのＧＤＤであり、ａｖｇ（ｄｄｉｓｔｏｒｔ）は、隣接するすべての三角形ペアにわたる平均のｄｄｉｓｔｏｒｔ（ｆｉ，ｆｊ）である。このｃｄｉｓｔｏｒｔ（ｆｉ，ｆｊ）の定義により、隣接する三角形のＧＤＤが外側の領域３０２と３０１とで指定される埋め込み間でバランスをとる境界エッジが選択される。換言すれば、不要な歪みを発生する三角形の不適切な辺にカットを適用しないようにする必要がある。
【００７２】
図４は、さまざまなグラフカットの機能の比較を示している。重みパラメータαは、２つの目標のバランスを調整する。α＝１に設定すると、シャープな（ｓｈａｒｐ）フィーチャを伴うモデルに対して適切な結果が得られる。中間の領域で２面角がなだらかに変化する形状の場合に、最短のカットになる傾向がある（４０１）。しかし、この分割によって右のチャートに非常に大きな伸縮が発生する。したがって、ユーザー指定の閾値４０４を満足するには再分割する必要がある。
【００７３】
一方、α＝０に設定するとＧＤＤは最小になり（４０２）、チャートの増大は回避されるが、境界はぎざぎざになる。α＝０．５、つまり両方の組み合わせを４０３に示す。パラメータ化の伸縮は４０２より若干大きいが、多くの適用例で滑らかな境界が得られるのが望ましい。
【００７４】
（Ｌａｎｄｍａｒｋ  ＩｓｏＭａｐによる中間領域の埋め込み）
図４に戻り、最適な分割を計算するには、分割されていないチャートに関する２つの埋め込み、すなわち、サイドＡ（３０２）に対応するものと、サイドＢ（３０１）に対応するものが必要である。こうした２つの埋め込みによってＧＤＤＡとＧＤＤＢとが定義される。サブチャート、「コア（ｃｏｒｅ）」、Ａ、Ｂのいずれにも中心の領域Ｃ（３０３）の内部の頂点は含まれない。したがって、ＡまたはＢのみのスペクトル分析を使用してＣの頂点の埋め込み座標は計算されない。Ｃのどの三角形がＡと結合し、どの三角形がＢと結合するかはまだわからないので、結局は他のサブチャートに挿入される三角形による過度に歪んだ各サブチャートの埋め込みは、回避する必要がある。Ｌａｎｄｍａｒｋ  ＩｓｏＭａｐと呼ばれるＩｓｏＭａｐの拡張によって、各コアの埋め込みだけを暗黙的に与えられた中間の領域と、各コアの頂点に対するＣの頂点の測地的な距離の関係を埋め込む。
【００７５】
ＡにはＮＡ個の頂点があると仮定する。サーフェスのスペクトル分析を実行した後に、ｎＡ個の固有値λｉと対応する固有ベクトル
【００７６】
【数１０】
2006012147.tif 000012
【００７７】
が存在している。Ａ内にあるすべての頂点のｎＡ次元の埋め込みは、次に示すｎＡ×ＮＡ型行列ＬＡの列を構成する。
【００７８】
【数１１】
2006012147.tif 000013
【００７９】
Ａの外部にある頂点ｐは、ｐからＡ内にある頂点までの既知の測地的な距離を制約として使用することで、そのｎＡ次元の埋め込み空間に配置できる。これと同じ概念により、ＧＰＳにおける有限数の距離の測定値を使用して、地理的な位置を特定する。ＡはｐからＡ内にある頂点までの距離の平方の列ベクトルを表すとする。ｎＡ次元の埋め込み座標
【００８０】
【数１２】
2006012147.tif 000014
【００８１】
は次の式で計算できる。
【００８２】
【数１３】
2006012147.tif 000015
【００８３】
ただし、
【００８４】
【数１４】
2006012147.tif 000016
【００８５】
は
【００８６】
【数１５】
2006012147.tif 000017
【００８７】
の列平均、
【００８８】
【数１６】
2006012147.tif 000018
【００８９】
は次に示すＬＡの疑似逆行列の転置である。
【００９０】
【数１７】
2006012147.tif 000019
【００９１】
ここで、Ａによって導かれる埋め込みにおけるＣ内のすべての頂点のＧＤＤが計算され、Ｂについても同様に処理される。
【００９２】
（管形状専用のスペクトルクラスタリング）
図５は、スペクトルクラスタリングによってウサギの耳の形を５つのチャートに分割する様子を示している。特に、この図は、管形状の分割を説明している。列ａ（５０１）は一般的なスペクトルクラスタリングを示しており（「サーフェスのスペクトルクラスタリング」の項で説明する）、列ｂ〜ｄ（５０２、５０３、５０４）は第１、第２、第３の固有値に基づく２元のクラスタリングを示している。ｎ個の主要な固有値が指定された場合に、サーフェスのスペクトルクラスタリングによって形状は最大２ｎ個のチャートに分割される。これは、複雑な形状に対しては適切に機能するが、ｎ≦３の単純な形状に対しては生成するチャート数が多くなりすぎる場合がある。５０１に示すように、スペクトルクラスタリングによってうさぎの耳は５つのチャートに分割される。過剰な分割を回避するために、ここでは前述の方法でなく第１の埋め込み座標に従ってチャートを２つに細分する。このアプローチは、多くの場合に機能するが、一般的なメッシュによくある管／筒状の突起に対しては理想的ではない。
【００９３】
別の方法５０４では、距離の行列の主要な固有対（ｅｉｇｅｎｐａｉｒｓ）を使用して、環状配置（ｃｙｃｌｉｃ  ｄｉｓｔｒｉｂｕｔｉｏｎｓ）によるデータ点を検出し、分割できることを確認する。次の管形状に関する発見的方法は、その固有値λｉが次の条件を満たす場合に有効であることが証明されている。  
・
【００９４】
【数１８】
2006012147.tif 000020
【００９５】
、すなわち上位３つの固有値で形状を適切に表現する。  
・λ１／λ２＞３、つまり形状は十分に長い。  
・λ２／λ３＜２、つまり形状は環状である。  
・λ３／λ４＞３、つまり第４の固有値は急速に減少し、無視できる。
【００９６】
形状が筒／管と認識される限り、それを２つのサブチャートに分割できる。第２、第３の次元は循環軸（ｃｙｃｌｉｃ  ａｘｅｓ）と見なすことができる。（短い方の循環軸に対応する）第３の主要な次元に従って形状を分割すると、より平坦なパッチが生成される。５０４に示すように、第３のコンポーネントを使用した結果から、第１、第２のコンポーネントを使用する（５０２、５０３）より自然な分割が得られる。
【００９７】
チャート全体の細分のプロセスは、次のように要約できる。上位３つの固有値に含まれるエネルギーが９０％未満の場合は、「一般的な」スペクトルクラスタリングを実行する（上記の「サーフェスのスペクトルクラスタリング」で説明している）。それ以外の場合に、管状のチャートにはこの項で説明する「専用の」スペクトルクラスタリングを実行する。その他のすべての場合には、最大の固有値に対応する１つの埋め込み座標を使用して２元のスペクトルクラスタリングを実行する。通常、唯一の２元でないチャートの細分が実行され（初回の繰り返しで）、その後に２元の細分を実行する。
【００９８】
（詳細な実装）
純粋な伸縮主導型のチャート化およびパラメータ化アルゴリズムは高価であり、特にモデルの頂点の数が増大する。計算を高速化するために、最後の項に示すようにＬａｎｄｍａｒｋ  ＩｓｏＭａｐのプロセスを使用して中間の領域内の頂点用の埋め込み座標を計算する。Ｌａｎｄｍａｒｋ  ＩｓｏＭａｐは、ランドマークポイント（ｌａｎｄｍａｒｋ  ｐｏｉｎｔｓ）としてｑ個の頂点を選択する（ただし、ｑ＜＜Ｎ）。測地的な距離の平方によるＮ×Ｎ型の行列を計算する代わりに、ＤＮ、ｑ×Ｎ型の行列Ｄｑ，Ｎを計算し、各頂点からランドマークポイントまでの距離のみを測定する。サーフェスのスペクトル分析を使用してｑ個のランドマークポイントの埋め込み座標を計算する。残りの頂点は「Ｌａｎｄｍａｒｋ  ＩｓｏＭａｐによる中間領域の埋め込み」の項で説明する方法で計算できる。
【００９９】
ランドマークポイントを選択するために、２次のエラーメトリック（ｅｒｒｏｒ  ｍｅｔｒｉｃ）に基づくハーフエッジ折りたたみ操作（ｈａｌｆ  ｅｄｇｅ  ｃｏｌｌａｐｓｅ  ｏｐｅｒａｔｉｏｎｓ）を実行することでモデルを簡素化してもよい。プログレッシブメッシュ（Ｐｒｏｇｒｅｓｓｉｖｅ  ｍｅｓｈｅｓ）を使用すると、ユーザーはゼロから各チャートを簡素化する必要がなくなる。十分な頂点分割が実行され、ＰＭに記録され、チャート内の十分なランドマークポイントが得られる。
【０１００】
ここでは、すべてのチャートに対してｑ＝１００ランドマークポイントを使用する。これで、大きなチャートについても処理を高速化できる。チャートの頂点数が１００未満の場合は、単純にそのすべてをランドマークポイントに指定する。ランドマークの埋め込みは、完全な分析より大きな伸縮を示すが、これは大きなチャートで伸縮が大きいものに対してのみであり、改善が必要である。チャートのサイズに無関係なｑのランドマークの埋め込みは、高速であり、通常は妥当な発見的方法である。
【０１０１】
上位１０個の固有値は、通常、テストモデルにおけるエネルギーの平方の９５％以上を占めるので、プロセスを高速化する別の方法は、サーフェススペクトル分析の上位１０個の固有値のみについて計算することである。要約すると、測地的な距離はＯ（ｑＮ  ｌｏｇＮ）に縮小され、スペクトル分解はＯ（ｑ２）になる。
【０１０２】
（信号専用アトラスの作成）
これまで、幾何学的な伸縮を使用してチャート化とパラメータ化を操作してきた。スペクトル分析を使用した伸縮主導型のメッシュパラメータ化のＩｓｏ−Ｃｈａｒｔは、できるだけコンパクトなテクスチャを使用して所定のサーフェス信号を表現する、信号専用のパラメータ化を生成するように一般化することもできる。
【０１０３】
スペクトル分析を使用した伸縮主導型のメッシュパラメータ化のＩｓｏ−Ｃｈａｒｔは、頂点間のペアごとの信号距離を計算することで、サーフェス信号に拡張されることができる。２つの頂点ｉとｊおよびその間の測地的なパスが指定されると、その間の信号距離はそのパスに沿って隣接する点のペア間の信号差の合計で定義できる。信号距離の行列にスペクトル分析を適用すると、これを維持するパラメータ化が作成され、したがってスペクトル分析を使用した伸縮主導型のメッシュパラメータ化のＩｓｏ−Ｃｈａｒｔは、幾何学的な歪みに適用した前述のプロセスと同じ方法で信号の歪みに関連付けられる。
【０１０４】
テクスチャカラーのように一般的な信号は、基盤となるジオメトリよりはるかに大きなバリエーションを示す可能性がある。信号距離を使用したサーフェスのスペクトル分析によって、通常は過剰な分割の原因となり得る多くの主要な固有値を伴う複雑な埋め込みが生成される。このことによって、参考として本明細書に引用する２００２年５月１日に出願された特許文献２に説明されている幾何学的伸縮と信号の伸縮との組み合わせが実現する。本明細書で得られる解決は、測地的な距離と信号距離の同様の組み合わせを使用した距離を定義する。
【０１０５】
【数１９】
2006012147.tif 000021
【０１０６】
ただし、ｄｓｉｇ（ｉ，ｊ）はｉとｊとの信号距離である。通常は、β＝０．５で適切な結果が得られる。
【０１０７】
図６は、本出願に記載のシステムおよび方法を実装できる例示的なコンピューティング環境６００を示している。例示的なコンピューティング環境６００は、コンピューティングシステムの１つの例にすぎず、本出願で説明する例をこの特定のコンピューティング環境に限定する意図はない。
【０１０８】
コンピューティング環境６００は、他のさまざまな汎用または専用のコンピューティングシステム構成に適用できる。周知のコンピューティングシステムの例には、パーソナルコンピュータ、ハンドヘルドまたはラップトップ装置、マイクロプロセッサベースのシステム、マルチプロセッサシステム、セットトップボックス、プログラム可能な家庭用電子機器、ゲーム機、家庭用電子機器、携帯電話、ＰＤＡなどが含まれるが、これらに限定はされない。
【０１０９】
コンピュータ６００には、汎用コンピューティングシステムがコンピューティング装置６０１の形で含まれる。コンピューティング装置６０１のコンポーネントには、１つまたは複数のプロセッサ（ＣＰＵ、ＧＰＵ、マイクロプロセッサなどを含む）またはプロセッサ６０７、システムメモリ６０９、さまざまなシステムコンポーネントを接続するシステムバス６０８が含まれる。
【０１１０】
プロセッサ６０７は、コンピューティング装置６０１の動作を制御し、その他の電子機器やコンピューティング装置（図示せず）と通信するさまざまなコンピュータ実行可能命令を処理する。システムバス６０８は、メモリバスまたはメモリコントローラ、周辺バス、アクセラレータグラフィックポート、プロセッサバスまたはローカルバスを含む任意の数の各種バス構造を表す。
【０１１１】
システムメモリ６０９には、ランダムアクセスメモリ（ＲＡＭ：ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ）などの揮発性メモリ、および／または読み取り専用メモリ（ＲＯＭ：ｒｅａｄ  ｏｎｌｙ  ｍｅｍｏｒｙ）などの不揮発性メモリの形をとるコンピュータ読み取り可能な媒体が含まれる。基本入出力システム（ＢＩＯＳ：ｂａｓｉｃ  ｉｎｐｕｔ／ｏｕｔｐｕｔ  ｓｙｓｔｅｍ）はＲＯＭに格納される。ＲＡＭには、通常は１台または複数台のプロセッサ６０７から直ちにアクセスでき、かつ／またはプロセッサ６０７で現在操作しているデータおよび／またはプログラムモジュールが格納される。
【０１１２】
マスストレージ装置６０４は、コンピューティング装置６０１に接続するか、バスに接続してコンピューティング装置に組み込むことができる。こうしたマスストレージ装置６０４には、取り外し可能な不揮発性の磁気ディスク（たとえば「フロッピー（登録商標）ディスク」）６０５に対する読み出しと書き込みを行う磁気ディスクドライブ、ＣＤ−ＲＯＭディスクなど６０６の取り外し可能な不揮発性の光ディスクに対する読み出しおよび／または書き込みを行う光ディスクドライブが含まれる。コンピュータ読み取り可能な媒体６０５、６０６は、一般に、コンピュータ読み取り可能な命令、データ構造、プログラムモジュールなどを実施し、フロッピー（登録商標）ディスク、ＣＤ、ポータブルメモリスティックなどで提供される。Ｉｓｏ−Ｃｈａｒｔのプロセスは、１つまたは複数のコンピュータ読み取り可能な媒体とシステムメモリ６０９または同等の場所に常駐する。
【０１１３】
例としてオペレーティングシステム、１つまたは複数のアプリケーションプログラム、その他のプログラムモジュール、およびプログラムデータを含む任意の数のプログラムモジュールは、ハードディスク６１０、マスストレージ装置６０４、ＲＯＭおよび／またはＲＡＭ  ６０９に格納できる。こうしたオペレーティングシステム、アプリケーションプログラム、その他のプログラムモジュール、およびプログラムデータ（またはその組み合わせ）には、本明細書で説明するシステムおよび方法の実施形態を含めてもよい。
【０１１４】
表示装置６０２は、ビデオアダプタ６１１などのインターフェイスを介してシステムバス６０８に接続できる。ユーザーは、キーボード、ポインティングデバイス、ジョイスティック、ゲームパッド、シリアルポートなど、任意の数のさまざまな入力装置６０３を介してコンピューティング装置６０１にインターフェイス接続できる。これらの入力装置および他の入力装置は、多くの場合にシステムバス６０８に接続された入力／出力インターフェイス６１２を介してプロセッサ６０７に接続するが、パラレルポート、ゲームポート、および／またはＵＳＢ（ｕｎｉｖｅｒｓａｌ  ｓｅｒｉａｌ  ｂｕｓ）のような他のインターフェイスやバス構造によって接続してもよい。
【０１１５】
コンピューティング装置６０１は、１つまたは複数のローカルエリアネットワーク（ＬＡＮ：ｌｏｃａｌ  ａｒｅａ  ｎｅｔｗｏｒｋ）、ワイドエリアネットワーク（ＷＡＮ：ｗｉｄｅ  ａｒｅａ  ｎｅｔｗｏｒｋ）などを介した１台または複数台のリモートコンピュータへの接続を使用したネットワーク環境で動作できる。コンピューティング装置６０１は、ネットワークアダプタ６１３、あるいはモデム、ＤＳＬ、ＩＳＤＮインターフェイスなどを介してネットワーク６１４に接続する。
【０１１６】
プログラムの命令を格納する記憶装置をネットワーク全域に分散できることは当業者には言うまでもない。たとえば、リモートコンピュータには適応型計測（ａｄａｐｔｉｖｅ  ｉｎｓｔｒｕｍｅｎｔａｔｉｏｎ）の実行時監視および分析ソフトウェアなどのツールを格納してもよい。ローカルコンピュータまたはターミナルコンピュータは、リモートコンピュータにアクセスし、ソフトウェアの一部またはすべてをダウンロードしてプログラムを実行してもよい。あるいは、ローカルコンピュータは必要に応じてソフトウェアの一部をダウンロードすることもできる。一部のソフトウェア命令をローカル端末で実行し、一部をリモートコンピュータ（あるいはコンピュータネットワーク）で実行することで、分散処理を行うこともできる。当業者には周知の従来の技術を使用して、ソフトウェア命令の一部またはすべてを専用の回路で実行してもよいことは、言うまでもない。
【０１１７】
上の例からわかるように、サーフェス上の点間の測地的な距離の行列に関するスペクトル分析は、アトラス生成におけるモデルのチャートへの分割とこうしたチャートのパラメータ化という２つの問題を同時に解決する高速で単純で効果的な方法を提供する傾向がある。本方法は、測地的な距離でなく信号距離を考慮して特定の信号に関するアトラスを最適化するように単純に一般化することもできる。説明したように、スペクトル分析によって伸縮が小さくなる傾向があり、引き続き伸縮を最小化するための開始点が得られる。最終的に、幾何学再メッシュおよびテクスチャマップ作成における従来の技術の結果を改善する伸縮主導型のアトラス生成機能が提供される。
【図面の簡単な説明】
【０１１８】
【図１】スペクトル分析を使用した伸縮主導型のメッシュパラメータ化を示すブロック図である。
【図２】うさぎのモデルをチャート化し、パラメータ化した結果を示す図である。
【図３】グラフカット（ｇｒａｐｈ  ｃｕｔ）の問題のように、最適なパーティション境界の検出を示す図である。
【図４】さまざまなグラフカット機能の比較を示す図である。
【図５】管形状を分割する例として、スペクトルクラスタリングによってウサギの耳の形を５つのチャートに分割する様子を示す図である。
【図６】本出願で説明するシステムおよび方法を実装できる例示的なコンピューティング環境６００を示す図である。
【符号の説明】
【０１１９】
２００  Ｉｓｏ−Ｃｈａｒｔアトラス
２０１  ウサギのモデル
３００  形状
３０１、３０２  外側の領域
３０３  中間の領域
３０４  グラフ
３０５  フローネットワークグラフ
【図１】
2006012147.tif 000027
【図６】
2006012147.tif 000028
【図２】
2006012147.tif 000029
【図３】
2006012147.tif 000030
【図４】
2006012147.tif 000031
【図５】
2006012147.tif 000032
【外国語明細書】
2006012147000001.pdf