(57)【要約】計算機使用環境において双３次スプライン表面を生成するためのシステムと方法が提供される。この方法の１つの操作は、実質的に矩形の構造を有する制御メッシュを生成すること（１５０）である。更なる操作は、各々の制御点に対してテンソル積Ｂ−スプライン基底関数を制御メッシュから推察すること（１５２）である。次いで、表面が基底関数と制御メッシュとに基づいて計算される（１５４）。
2006523891.tif 000002
【特許請求の範囲】
【請求項１】
計算機環境において双３次スプライン表面を定義する方法であって、
実質的に矩形の構造を有する制御メッシュを生成する工程と、
各々の制御点に対するテンソル積Ｂ−スプライン基底関数を前記制御メッシュから推察する工程と、
前記基底関数と前記制御メッシュに基づいて前記表面を計算する工程と、
を含む方法。
【請求項２】
規則の１つの非階層的集合を用いて、各々の制御点について前記基底関数を決定する工程を更に含む、請求項１に記載の方法。
【請求項３】
計算機環境において双３次スプライン表面のメッシュを局所的に洗練課する方法であって、
実質的に矩形の構造を有する制御メッシュを定義する工程と、
前記制御メッシュの事前画像に制御点を挿入する工程と、
前記双３次スプライン表面が幾何学的に変更されないように、前記制御点及びその近傍の制御点のデカルト座標を計算する工程と、
を含む方法。
【請求項４】
前記制御点の前記デカルト座標を計算する前記工程が、
前記制御メッシュにより要求されるよりも少ないノットを有する基底関数を分割する工程と、
基底関数が、前記制御メッシュにより要求されるよりも多いノットを有する位置の前記制御メッシュに制御点を追加する工程と、
を更に含む、請求項３に記載の方法。
【請求項５】
ゼロのノット・インターバルを持つ制御点の１つ以上の隣接する部分行を挿入することにより、前記表面に鋭さの特徴を生成して、鋭い折り目を生成する工程を更に含む、請求項３に記載の方法。
【請求項６】
ノット・インターバルが小さい１つ以上の制御点の隣接する部分行を挿入することにより、前記表面に鋭さの特徴を生成して、鋭さの少ない折り目を生成する工程を更に含む、請求項３に記載の方法。
【請求項７】
単一の表面に併合されることが望まれる制御メッシュを有する２つの表面を提供する工程と、
近接した共通のエッジを有するよう前記２つの表面を配置する工程と、
ノット・インターバルの列が前記２つの表面の共通の境界エッジに沿って一致するように、前記２つの表面の制御メッシュ上での局所洗練とノット・インターバルの調整とを実行する工程と、
前記共通の境界に沿って前記２つの表面の前記制御点を結合する工程と、
を更に含む、請求項３に記載の方法。
【請求項８】
計算機環境において任意のトポロジーの制御メッシュに局所洗練を提供するために制御メッシュを細分する方法であって、
局所洗練が望まれる異常点を選択する工程と、
前記洗練操作が表面全体に伝搬することを防止するために、Ｔ−ジャンクション制御点を用いる工程と、
を含む方法。
【請求項９】
計算機環境において制御メッシュに局所洗練を提供する双３次スプライン表面を定義する方法であって、
スプライン制御メッシュに関連するノット・インターバルを特定する工程と、
前記ノット・インターバルに基づいて局所ノット座標系を課す工程と、
制御点について基底関数を生成するために、前記制御点に対する局所ノット・ベクトルを推察する工程と、
前記双３次スプライン表面を変更することなく、前記制御メッシュへ単一の制御点を挿入する工程と、
を含む方法。
【請求項１０】
単一の制御点を挿入する前記工程が、前記双３次スプライン表面を変更することなく、前記制御メッシュへ単一の制御点を挿入し、Ｔ−ジャンクションで終了する制御点の部分行を許容する工程を更に含む、請求項９に記載の方法。
【請求項１１】
局所ノット座標系を課す前記工程が、各々の制御点Ｐｉの事前画像に局所ノット座標（ｓｉ，ｔｉ）を割り当てる工程を更に含む、請求項９に記載の方法。
【請求項１２】
計算機環境において任意のトポロジーの制御メッシュに局所洗練を提供するために、３次スプライン制御メッシュを細分する方法であって、
任意のトポロジーの前記３次スプライン制御メッシュに局所ノット座標系を課す工程と、
前記３次スプライン制御メッシュのエッジに対するノット・インターバルを特定する工程と、
前記３次スプライン制御メッシュにＴ−ジャンクションを挿入する工程と、
前記Ｔ−ジャンクションに対するノット・ベクトルを推測する工程と、
前記ノット・ベクトルを用いて、前記Ｔ−ジャンクションに対する基底関数を定義する工程と、
を含む方法。
【請求項１３】
Ｔ−ジャンクションを挿入する前記工程が、前記３次スプライン制御メッシュにおける面の対向するエッジのノット・インターバルの和が等しいことを要求する工程を更に含む、請求項１２に記載の方法。
【請求項１４】
Ｔ−ジャンクションを挿入する前記工程が、前記３次スプライン制御メッシュにおける面の対向するエッジのノット・インターバルの和が等しいとき、面の対向するエッジ上のＴ−ジャンクションが前記面の対向するエッジ上のＴ−ジャンクションに接続されることを要求する工程を更に含む、請求項１２に記載の方法。
【請求項１５】
エンド・ユーザーが見ることができるシェイディングを前記３次スプライン・メッシュに適用する工程を更に含む、請求項１２に記載の方法。
【請求項１６】
ゼロのノット・インターバルを持つ制御点の複数の隣接する行を挿入することにより、前記スプライン制御メッシュに鋭さの特徴を生成する工程を更に含む、請求項１２に記載の方法。
【請求項１７】
前記の挿入された制御点の配置と前記ノット・インターバルの調整とにより、前記鋭さの特徴を制御する工程を更に含む、請求項１６に記載の方法。
【請求項１８】
Ｔ−スプラインからベジェ・パッチを抽出する方法であって、
全てのＴ−ジャンクションを２つのベイに延ばすことにより、全てのベジェ領域を識別する工程と、
各々のベジェ領域が制御点の４×４グリッドにより囲まれるように局所ノット挿入を実行する工程と、
ゼロのノット・インターバルのペアが隣接するベジェ領域の各ペアを分離するように、前記局所ノット挿入に対するノット・インターバルを選択する工程と、
を含む方法。
【請求項１９】
整列されないノット・ベクトルを有する少なくとも２つのＢ−スプライン表面を単一のＴ−スプラインに併合する方法であって、
第１のＢ−スプライン制御メッシュと第２のＢ−スプライン制御メッシュとを識別する工程と、
エッジと交差する前記第２のＢ−スプライン制御メッシュでのノット・ベクトルと整列するように構成された前記エッジ上の追加の制御点に対する前記第１のＢ−スプライン制御メッシュでの位置を識別する工程と、
前記第１の制御メッシュでの各々の識別された位置にオフセット制御点を挿入する工程と、
前記２つのＢ−スプラインを結合してＴ−スプラインを生成するために、前記第１のＢ−スプライン制御メッシュの前記制御点を前記第２のメッシュからの対応するノット・ベクトルと結合する工程と、
を含む方法。
【請求項２０】
エッジと交差する前記第１のＢ−スプライン制御メッシュでのノット・ベクトルと整列するように構成された前記エッジ上の追加の制御点に対する前記第２のＢ−スプライン制御メッシュでの位置を識別する工程と、
前記第２のＢ−スプライン制御メッシュでの各々の識別された位置にオフセット制御点を挿入する工程と、
前記２つのＢ−スプラインを結合してＴ−スプラインを生成するために、前記第２のＢ−スプライン制御メッシュの前記制御点を前記第１のメッシュからの対応するノット・ベクトルと結合する工程と、
を更に含む、請求項１９に記載の方法。
【請求項２１】
各々の識別された位置にオフセット制御点を挿入する前記工程が、Ｃ２併合を提供するために、共有する境界に沿って３重ノット・インターバルを挿入する工程を更に含む、請求項１９に記載の方法。
【請求項２２】
計算機環境において任意の次数の局所的に洗練可能なテンソル積スプライン表面を定義する方法であって、
実質的に矩形の構造を有する制御メッシュを定義する工程と、
前記制御メッシュから各制御点に対するテンソル積Ｂ−スプライン基底関数を推測する工程と、
前記基底関数と前記制御メッシュとに基づいて前記表面を計算する工程と、
を含む方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全体的に、局所洗練の表現が可能な、モデル化された表面の定義に関する。
背景技術
表面のモデル化は、コンピュータ・グラフィックス、コンピュータ支援設計（ＣＡＤ）、コンピュータ支援幾何学設計（ＣＡＧＤ）、コンピュータ・アニメーションにおける基本的業務である。表面は一般的に、ポリゴンのメッシュ又は区分された多項式のパッチにより近似される。その単純性により、ポリゴンのメッシュは表面を近似するための一般的な方法であり、多くのアプリケーションに対して適切である。ポリゴンのメッシュの１つの欠点は、それらが本来的にファセット化され、そのアプリケーションの要求を満たすのに充分な小ささにファセットを作成するために、多数のポリゴンが必要とされることである。
【０００２】
対照的に、平滑面の一般的な表現は、テンソル積Ｂ−スプライン表面である。Ｂ−スプライン表面の制御点は矩形のグリッドにトポロジー的に配置されることが必要である。Ｂ−スプライン表面は、ベジェ形式で表わすことができる幾つかのパラメータ表面のパッチから成る。Ｂ−スプライン表面の顕著な利点は、各々の構成する表面パッチが、その隣り合うパッチと共に、自動的にＣｎ−１であることであり、ここでｎは基底関数の次数である。
【０００３】
構成要素である表面パッチが始まって終わるパラメータ値はノットと呼ばれ、ノットの非減少シーケンスはノット・ベクトルと呼ばれる。Ｂ−スプライン表面の定義は、助変数方程式の各々のパラメータに対して１つずつの、２つのノット・ベクトルを含む。均一なＢ−スプライン表面では、与えられたノット・ベクトルにおけるノットの各々のペアの間の差異は一定である。不均一Ｂ−スプラインは、そのような制約を持たない。有理Ｂ−スプライン表面は、制御点に重みが割り当てられたものである。重みは追加の表面制御を提供し、モデルでの鋭い折り目付けを可能にして、Ｂ−スプライン表面が２次曲面を表示できるようにする。不均一有理Ｂ−スプライン表面は、頭文字を取ってＮＵＲＢＳ表面と呼ばれている。
【０００４】
ＮＵＲＢＳ制御グリッドの洗練は、１つ又はそれ以上の新しいノット値がノット・ベクトルに挿入されるノット挿入と呼ばれる手続を通して達成される。ノット挿入は表面を変化させないが、設計者がそのモデルを取り扱えるようにする一層多くの制御点を提供する。ＮＵＲＢＳ制御点は、トポロジー的に矩形グリッドになければならないので、ノット挿入によって制御点の１つ以上の行全体が制御グリッドに追加される。これらの新しい行の制御点のデカルト座標は、隣り合う幾つかの制御点と共に、この洗練操作が表面を変化させないように見いだされ得る。不都合なことに、ＮＵＲＢＳ表面の矩形グリッド・トポロジーを単純に満たすように、各々の所望の新しい制御点に対する制御点の行全体を追加することは、表面のモデル化の複雑性を極端に増加させる。
【０００５】
表面の洗練は、幾つかの用途を有し且つ価値のある操作である。まず第１に、洗練により、設計者はモデルにおいて更なる詳細が求められる表面領域に追加の制御点を挿入することができる。例えば、ＮＵＲＢＳを用いて人間の耳をモデル化するためには、頬をモデル化するためよりも多くの制御点を必要とする。第２に、制御グリッドが洗練される都度、制御グリッドはそれが定義するＮＵＲＢＳ表面のよりよい近似になる。このように、繰り返して洗練を実行することにより、制御グリッドは任意に正確な表面の表現となることができ、それは描画に適したものである。第３に、ノット挿入を用いて、ＮＵＲＢＳを含むベジェ・パッチの制御点を計算することができる。第４に、ノット挿入を用いて、鋭い特徴をＮＵＲＢＳ表面に追加することができる。一般的に、ＮＵＲＢＳ表面はＣｎ−１連続であり、ここでｎは表面の次数である。しかしながら、ノット・ベクトルにｒ個の同一のノットが存在する場合は、そのノット値において、表面はＣｎ−ｒである。従って、立方体のＮＵＲＢＳ表面での３重ノットは、Ｃ０折り目を許容する。均一なＢ−スプライン表面は、１つでもノットが挿入されると均一なＢ−スプライン表面ではなくなるので、任意のノット挿入を許容しない。（ノット挿入の後も均一であるならば）均一なＢ−スプライン表面に対して可能な唯一のノット挿入は、隣り合うノットの各々のペアの間の中間に同時にノットを挿入することであり、これはノット２重化と呼ばれる処理である。均一なＢ−スプラインは２つ以上の同一のノットをサポートすることができないので、均一なＢ−スプライン表面は常にＣｎ−１連続であり、Ｃ０折り目を課すことができない。
【０００６】
ノット挿入用のアルゴリズムが幾つか存在する。オスロ・アルゴリズムは、スプラインの洗練された空間からサブ・スペースへの、Ｂ−スプライン・ベースの変換を定義するために、いわゆる離散Ｂ−スプラインを計算する。他のノット挿入の方法はベームのアルゴリズムであって、それはＢ−スプライン係数に直接作用する。更に、ノット挿入のための発展しつつある原理のような数学的洞察が開発されている。
【０００７】
ノット挿入の逆操作であるノット除去がＮＵＲＢＳ上で実行可能である。比較すると、ノット挿入は表面を修正しないのに対し、ノット除去は一般的に表面を改変する。従って、ノット除去は通常は近似を含む。ノット除去の１つの動機はデータ圧縮である。この問題は、許容誤差を受けるノット数を最小化することである。ノット除去の他の用途は形状の適正化である。連続性のオーダーはノット除去により増加され得る。
【０００８】
ＮＵＲＢＳ表面の全ての制御点が矩形のグリッドにトポロジー的に配置されなければならないとの要求は、重大な欠点である。これが欠点である少なくとも３つの理由がある。第１に、任意のトポロジーの表面は、モデルを個々のＮＵＲＢＳパッチの集合に分割するだけで、ＮＵＲＢＳ表面を用いて表わすことができる。隣りあうパッチは、幾何学的連続条件を用いて、明らかに縫い合わせられる。図２は、７つのＮＵＲＢＳ表面からなる手のモデルを示す。隣りあうＮＵＲＢＳ表面が正確には接合していない穴を示すために、図３では小矩形領域が拡大されている。そのようなギャップの存在は、モデルが変形されるたびに、広げられたギャップを補修しなければならない可能性のあるモデル設計者に負担をかける。
【０００９】
この制約が重大である第２の理由は、多数のＮＵＲＢＳ制御点はトポロジー的な制約を満たす以外に何の目的も果たさないことを典型的には意味するからである。ＮＵＲＢＳ制御点は重要な幾何学的情報を担わない。不必要な制御点は、設計者に一層多くのデータを取り扱うことを求めるばかりではなく、表面に不要なリップルを導入することができるので、設計者にとって重大な迷惑物である。図１は、ＮＵＲＢＳ頭部モデルを示す。設計者は、不要なリップルを除去するよう努力しながらＮＵＲＢＳ制御点を微調整するのに多くの時間を浪費することになる。暗いＮＵＲＢＳ制御点は（本発明で以下に示されるように）不要なものであり、モデル設計者により所望される制御点を含めた結果として追加されたものであり、制御点の追加の列を生じることになる。
【００１０】
矩形グリッドの制約が問題である第３の理由は、ＮＵＲＢＳ制御グリッドに単一の制御点を挿入することが不可能なのではなく、単一のノット挿入が実行される度に制御点の列全体が追加されなければならないことである。これは、１つの制御点の挿入がその制御グリッドへの列全体の挿入を必要とするので、ＮＵＲＢＳ表面の実際の局所的洗練は不可能であることを意味する。
【００１１】
ＮＵＲＢＳに関連する問題を解決することの複雑さを更に説明するために、この問題を解決する１つの試みをここで紹介する。２００１年８月に、アルマズ・バケノフはブリガム・ヤング大学で「Ｔ−スプライン：Ｔ−ジャンクションとのテンソル積Ｂ−スプライン表面」と題する修士論文を完成した。詳細な説明において後に記載する本発明の発明者であるトーマス・Ｗ・セダーバーグはアルマズ・バケノフの論文の助言者であった。バケノフの論文は、ＮＵＲＢＳに関連する問題の解決の初期の試みを表わす。特に、トーマス・Ｗ・セダーバーグは、この問題と１９９９年から２００３年まで格闘した。このように、バケノフの論文で記述されたＴ−スプラインの観念と本発明で以下に記述される概念との、Ｔ−スプラインと呼ばれる２つの顕著に異なる概念があるという僅かに紛らわしい状況に面している。
【００１２】
特に、バケノフ論文で表わされるＴ−スプラインの観念は、それを殆ど無用にする限界を含んでいる。最も顕著には、バケノフ論文で記述されたＴ−スプラインは、線形方程式の潜在的に巨大なシステムという解なしには、ＮＵＲＢＳに関連する問題を解決することが不可能であるが、それに対しては解が多くの場合存在しない。これらの理由から、バケノフ論文に含まれるＴ−スプラインの観念には実際的な価値がない。
【００１３】
全ての制御点が矩形グリッド内部に存在することを求める、ＮＵＲＢＳのトポロジー的制約を受けない表面定式化が幾つか提案されてきた。本議論に最も関係する、任意トポロジー表面定式化は再分割表面と呼ばれる。キャットマル・クラーク再分割表面は、実のところ、Ｂ−スプライン表面の一般化である。キャットマル・クラーク表面の制御点がトポロジー的に矩形グリッドに存在する場合、その表面は均一な双３次Ｂ−スプライン表面に縮退する。同様に、ドゥー・サビン再分割表面は、均一な双４次Ｂ−スプライン表面を任意のトポロジーの制御グリッドに一般化する。
【００１４】
キャットマル・クラーク表面の洗練は、均一な双３次Ｂ−スプライン表面に対するノット２重化の観念に基づいており、非４側面表面と非結合４頂点とを扱うために特別な規則が導入された。洗練の各工程で、面の数は４倍だけ増加する。洗練を繰り返すことにより、制御グリッドは限界面を一層詳しく近似する。
【００１５】
キャットマル・クラーク表面に伴う問題は、均一なＢ−スプライン表面に基づいているので、鋭いＣ０の特徴を表わすことができないことである。しかしながら、そのような特徴の近傍で洗練の規則を変更することによって再分割表面に鋭さの特徴、辺、折り目、隅を定義するための幾つかの方法が提案されている。
【００１６】
他の一層重大な問題は、キャットマル・クラーク表面の局所的洗練が不可能なことである。実際、ＮＵＲＢＳ表面に対する最も単純な洗練操作が制御点の単一の列を挿入することである状況では、キャットマル・クラーク表面については全洗練操作のみが定義され、制御点の数は各々の洗練工程において大まかには４倍だけ増加する。
【００１７】
発明の概要
計算機を用いて双３次スプライン表面を生成するためのシステムと方法が提供される。この方法の１つの操作は、実質的に矩形の構造を有する制御メッシュを定義することである。更なる操作は、制御点毎にテンソル積Ｂ−スプライン基底関数を制御メッシュから推察することである。次いで、基底関数と制御メッシュに基づいて表面を計算することができる。
【００１８】
本発明の追加の特徴と利点は、本発明の特徴を例示する添付図面を参照して考察される以下の詳細な説明から明らかとなるであろう。
詳細な説明
図に示される例示の実施の形態を参照し、ここでは実施の形態を記述するために特定の用語が用いられる。しかしながら、理解されるように、それによって本発明の範囲の限定を意図してはいない。ここで示される発明的特徴の変形と更なる修正や、ここで説明される本発明の原理の追加的応用は、当該技術の当業者であって開示を得た者が想到するものであり、本発明の範囲内にあると見なされるべきである。
【００１９】
本発明のシステムと方法は、Ｔ−スプラインと呼ばれる不均一Ｂ−スプライン表面（ＮＵＲＢＳ）の一般化と改善を提供する。ＮＵＲＢＳ表面の主要な問題は、ＮＵＲＢＳ制御点はトポロジー的に矩形グリッドに存在しなければならないので、しばしば、大部分のＮＵＲＢＳ制御点は、矩形グリッドのトポロジーを満たす以外には、何の目的にも寄与しないということである。そのような制御点は、重要な幾何学的情報を含まないので、不要であるとする。Ｔ−スプラインは、不要な制御点の数を最小化することができるＮＵＲＢＳ表面の一般化である。更に、Ｔ−スプラインは、双３次スプライン表面が幾何学的に変形されないように制御メッシュに制御点を挿入することができる。
【００２０】
Ｔ−メッシュ（又はＴ−スプライン制御メッシュ）とＮＵＲＢＳ制御メッシュとの間の１つの違いは、Ｔ−スプラインによって制御点の行を終了させることができることである。従って、行は多くの点又は単一の点を含むことができる。部分行における最終の制御点はＴ−ジャンクションと呼ばれる。Ｔ−ジャンクションは、図１３のａ及びｄの矩形グリッドに対して、図１３のｂ及びｃに見ることができる。図５のｂは、Ｔ−スプラインを用いるときに図５のａのＮＵＲＢＳの頭のモデルにおける不要な制御点が取り除かれ又は回避されるＴ−スプラインの他の例を示している。Ｔ−スプライン表面モデルはＮＵＲＢＳモデルと幾何学的に等価であるが、Ｔ−スプラインの表現は等価なＮＵＲＢＳモデルよりも少ない制御点を用いて形成されることが多い。
【００２１】
Ｔ−スプライン制御グリッドはＴ−ジャンクションを許容するので、制御点の線はＮＵＲＢＳのように全制御グリッドを横切る必要がない。言いかえれば、Ｔ−ジャンクションはＴ−スプラインが局所的に洗練可能であることを許容し、制御点の列全体又は行全体を伝搬することなく、制御点を制御グリッドに挿入することができる。
【００２２】
Ｔ−スプラインは、局所的洗練や、単一のギャップ無しモデルに対する異なるノット・ベクトルを有する幾つかのＢ−スプライン表面の併合のような、矛盾のないフレームワーク内の多くの価値ある操作をサポートする。この詳細な説明は次数３のＴ−スプラインに焦点を合わせているが、これは多重ノットのないときのＣ２である。しかしながら、Ｔ−スプラインの使用は任意の次数に拡張することができる。Ｔ−ＮＵＲＣＣ（Ｔ−ジャンクションを有する不均一有理キャットマル・クラーク表面）は、Ｔ−スプライン及びキャットマル・クラーク表面の「上位集合」である。従って、Ｔ−ＮＵＲＣＣも本開示において検討される。更に、Ｔ−ＮＵＲＣＣのためのモデリング・プログラムは、特別な場合として、任意のＮＵＲＢＳ又はキャットマル・クラークのモデルを取り扱うことができる。
【００２３】
Ｔ−ＮＵＲＣＣは、キャットマル・クラーク型制御グリッドの真の局所的洗練を可能にする。これは、追加の制御の提供又は一層円滑なモザイクの生成が必要なところのみに個々の制御点を挿入することができ、そのような挿入がその表面又はその限界表面の幾何形状を変更しないことを意味する。Ｔ−ＮＵＲＣＣは、静的洗練規則を用いており、異常点や特徴以外のところではＣ２である。この詳細な説明も、Ｔ−ＮＵＲＣＣ（Ｔ−ジャンクションを有する不均一有理キャットマル・クラーク表面）と呼ばれる、局所的に洗練可能な細分表面を提示する。Ｔ−ＮＵＲＣＣでは、異常点に隣接する表面が洗練を伝搬することなく洗練されることができ、極度に湾曲した表面も局所的に洗練されることができる。Ｔ−スプラインにおけるように、詳細に対する一層精密な制御を提供するために、個々の制御点もＴ−ＮＵＲＣＣに挿入され得る。Ｔ−ＮＵＲＣＣは、キャットマル・クラーク表面とＮＵＲＢＳとの一般化である。
【００２４】
図６は、Ｔ−ＮＵＲＣＣ局所洗練、全体的に洗練されたキャットマル・クラーク表面よりも遙かに経済的であるＴ−ＮＵＲＣＣモザイクを如何に可能にするかを示している。図６の４面体のＴ−ＮＵＲＣＣは２４９６個の面を有する。この４面体に対する大域的に洗練されたキャットマル・クラーク表面は、同じ精密さを達成するために、３９３２１６個の表面を必要とする。
【００２５】
図２に再度戻ると、この図は７つのＢ−スプライン表面からなる手のモデルを示している。隣接するＢ−スプライン表面が正確には合致しない穴を拡大するよう、図３では小矩形領域が強調されている。そのようなギャップの存在は、モデルが変形されるときには何時も、拡大されたギャップを補修しなければならないモデル設計者に負担をかけることになる。図３はＮＵＲＢＳを用いて生成されたギャップを示し、図４は、ギャップのないＴ−スプラインへ変換された後の、したがって補修の必要性を除去したモデルを示している。こうして、Ｔ−スプラインとＴ−ＮＵＲＣＣは、キャットマル・クラーク表面が均一３次Ｂ−スプラインをベースとするモデルに拡張するのと同じ気密性を、幾つかのＮＵＲＢＳ表面からなるモデルに吹き込むことができる。Ｔ−スプラインは、Ｔ−ジャンクション制御点の存在を許容するＮＵＲＢＳ表面の強化である。
【００２６】
図７は本発明の基本的特徴を示しており、その概要を提供する。計算機環境において双３次スプライン表面を定義するための方法が提供される。この方法の１つの操作は、ブロック１５０において、実質的に矩形の構造で制御メッシュを生成する。他の操作は、ブロック１５２において、制御メッシュから制御点毎のテンソル積Ｂ−スプライン基底関数を推察する。更なる操作は、ブロック１５４において、基底関数と制御メッシュに基づいて表面を計算する。基底関数は、一組の非階層的な規則を用いて各制御点に対して決定され得る。
【００２７】
制御メッシュの洗練は、制御メッシュにより定義される表面を変更することなく制御メッシュに制御点を追加するプロセスである。議論したように、ＮＵＲＢＳ表面に対する洗練の最も単純な形式は、制御グリッドに対する制御点の行全体の追加を必要とする。対称的に、本発明により、モデル設計者は単一の制御点でＴ−スプラインの制御グリッドを洗練することを可能にする。簡単に言えば、制御点の追加前に存在したような表面は変更されない。ＮＵＲＢＳのような従来知られた表面は、単一の新しい制御点の追加をサポートしない。この問題は以下で更に詳細に説明される。本発明はここまで一般的な用語で議論してきたが、この後は本発明の一層技術的な記述が続く。
【００２８】
ノット・インターバル
ノット・インターバルは、ノットの情報を担う目的でＴ−スプライン制御グリッドの各エッジに割り当てられた負でない数である。図８に示される３次Ｂ−スプライン曲線では、制御ポリゴンの各エッジに付けられたｄｉの値がノット・インターバルである。各ノット・インターバルは、ノット・ベクトルにおける２つの連続したノットの間の差である。非周期的曲線については、終了条件ノット・インターバルが、制御ポリゴンの各端に隣接する「仮想」エッジに割り当てられる（この場合にはｄ−１及びｄ５）。制御ポリゴンの最初と最後のエッジを除く全てのエッジについては、各エッジのノット・インターバルは、エッジが写像される曲線セグメントのパラメータ長さである。曲線に対するノット・インターバルを変えることなく、任意の定数をネット・ベクトルのノットに加えることができる。このようにして、ノット・インターバルが与えられてノット・ベクトルが推論される必要がある場合に、ノット原点を選択することができる。
【００２９】
Ｔ−スプライン及びＴ−ＮＵＲＣＣの制御グリッドのエッジには、ノット・インターバルが同様に付けられる。Ｔ−ＮＵＲＣＣ制御メッシュは矩形のグリッドではないので、ノット・インターバルによって「局所」ノット座標系を表面に課すことができる。図９は、ＮＵＲＣＣ制御グリッドの正規のサブグリッドを示す。この領域に局所ノット座標系を課し、それにより以下のように制御点に対する基底関数を決定することができる。第１に、局所ノット座標（ｄ０，ｅ０）に
【００３０】
【数１】
2006523891.tif 000003
【００３１】
を（任意に）割り当てる。この正規のサブグリッドに対する局所ノット・ベクトルは、
【００３２】
【数２】
2006523891.tif 000004
【００３３】
であり、ここで
【００３４】
【数３】
2006523891.tif 000005
【００３５】
である。この局所ノット座標系に関する制御点
【００３６】
【数４】
2006523891.tif 000006
【００３７】
についての極ラベルは、
【００３８】
【数５】
2006523891.tif 000007
【００３９】
であり、この正規サブグリッドにより定義される表面は、
【００４０】
【数６】
2006523891.tif 000008
【００４１】
である。ここで、
【００４２】
【数７】
2006523891.tif 000009
【００４３】
は｛ｄ｝上の３次Ｂ−スプライン基底関数であり、
【００４４】
【数８】
2006523891.tif 000010
【００４５】
は｛ｅ｝上の３次Ｂ−スプライン基底関数である。上付き文字３は順番ではなく次数を表わす。
Ｔ−スプライン
Ｔ−スプライン表面に対する制御グリッドはＴ−メッシュと呼ばれる。Ｔ−メッシュが矩形グリッドを形成するならば、Ｔ−スプラインはＢ−スプライン表面に縮退する。Ｔ−メッシュは、基本的には、Ｔ−ジャンクションを許容する矩形グリッドである。Ｔ−メッシュでの各エッジの事前画像は、定数ｓ（ｓ−エッジと呼ばれる）又は定数ｔ（ｔ−エッジと呼ばれる）の線分である。Ｔ−ジャンクションは、１つのｓ−エッジと２つのｔ−エッジ、又は、１つのｔ−エッジと２つのｓ−エッジにより共有される頂点である。
【００４６】
ノット・インターバルはＴ−メッシュにおける各エッジに割り当てられる。図１０は（ｓ，ｔ）パラメータ空間におけるＴ−メッシュの一部の事前画像を示し、ここで、ｄｉ及びｅｉはノット・インターバルを表わす。ノット・インターバルは、任意の表面の一方の辺に沿う全てのノット・インターバルの和が、反対側の辺のノット・インターバルの和と等しくなければならないという関係により制約される。例えば、図１０では、表面Ｆ１上ではｅ３＋ｅ４＝ｅ６＋ｅ７であり、表面Ｆ２上ではｄ６＋ｄ７＝ｄ９である。
【００４７】
本発明の発明者は、Ｔ−メッシュ上のノット・インターバルから局所ノット座標系を推測することが可能であることを認識した。ノット座標系を課すために、事前画像がパラメータ領域（ｓ，ｔ）＝（０，０）に対する原点として機能する制御点を最初に選択することができる。図１０の例については、（ｓ０，ｔ０）はノットの原点であるとすることができる。
【００４８】
【数９】
2006523891.tif 000011
【００４９】
Ｔ−メッシュに対する１つの追加の規則は、或る面の１つのエッジ上のＴ−ジャンクションが該面の対向するエッジ上のＴ−ジャンクションと正式に接続されることができ（それによって当該面は２つの表面に分割され）るならば、当該エッジはＴ−メッシュに含まれなければならない、ということである。正式とは、各面の対向する辺上のノット・ベクトルの和が常に等しくなければならないことを意味する。このように、ｅ３＝ｅ６であり、従ってｅ４＝ｅ７である場合、且つその場合にのみ、水平な線が面Ｆ１を分割するために必要である。
【００５０】
ノット座標系は、Ｔ−スプライン表面に対する明示的な数式を書く際に用いられる。つまり、
【００５１】
【数１０】
2006523891.tif 000012
【００５２】
であり、
【００５３】
【数１１】
2006523891.tif 000013
【００５４】
は、その重みがＷｉであり、そのデカルト座標が（ｘｉ／ｗｉ，ｙｉ／ｗｉ，ｚｉ／ｗｉ）であるＰ４における制御点である。同様に、その表面上の点のデカルト座標は、
【００５５】
【数１２】
2006523891.tif 000014
【００５６】
で与えられる。基底関数Ｂｉ（ｓ，ｔ）は、
【００５７】
【数１３】
2006523891.tif 000015
【００５８】
によって与えられ、図１１に示すように、Ｎ［ｓｉ０，ｓｉ１，ｓｉ２，ｓｉ３，ｓｉ４］（ｓ）は、ノット・ベクトル
【００５９】
【数１４】
2006523891.tif 000016
【００６０】
に関連する３次Ｂ−スプライン基底関数であり、Ｎ［ｔｉ０，ｔｉ１，ｔｉ２，ｔｉ３，ｔｉ４］（ｔ）は、ノット・ベクトル
【００６１】
【数１５】
2006523891.tif 000017
【００６２】
に関連する３次Ｂ−スプライン基底関数である。
有理Ｂ−スプラインにおけるように、設計者は追加の形状制御を得るために自由に重みｗｉを調整することができる。後述するように、重みは発明者らの新しい局所洗練アルゴリズムにおいて重要な役割を果たす。すなわち、洗練前に重みが全て１であるＴ−スプラインは、洗練後には幾つかの重みが１に等しくなくなるが、それでも
【００６３】
【数１６】
2006523891.tif 000018
【００６４】
が成り立つ。
【００６５】
【数１７】
2006523891.tif 000019
【００６６】
Ｔ−スプラインの局所洗練
Ｔ−スプラインに対して制御点を挿入するための本発明の動作の１つの実施の形態の概観を以下に記述する。認識されるように、本発明の他の実施の形態が存在し、本発明は計算機的に同等で異なる形式でも実施され得る。表面及びそれに関連する制御メッシュは一般にデカルト座標で計算される。しかしながら、極座標系、曲線座標系又は他の公知の座標系の１つのような他の座標系を用いることができる。基底関数の洗練は、このアルゴリズムにおいて重要な役割を果たすので、最初に考察される。次に、Ｔ−スプラインの観念が導入される。この概念は局所洗練アルゴリズムで用いられる。
【００６７】
基底関数の洗練
【００６８】
【数１８】
2006523891.tif 000020
【００６９】
Ｔ−スプライン基底関数Ｂ（ｓ，ｔ）は、ｓ又はｔにおいてノット挿入を受けることができ、それによって、ｓ又はｔを２つのスケーリングされた基底関数に分割し、それらの基底関数の和が元の関数となる。これらの得られたスケーリングされた基底関数への更なる挿入は一組のスケーリングされた基底関数を生じ、それらの和が元の関数となる。
【００７０】
例えば、図１２のａは、Ｔ−スプライン基底関数Ｂ１に対するノット・ベクトルを示し、図１２のｂは図１２のａのノット・ベクトルの洗練を示す。（５）〜（８）の適切な適用により、
【００７１】
【数１９】
2006523891.tif 000021
【００７２】
を得ることができる。
Ｔ−スプライン空間
【００７３】
【数２０】
2006523891.tif 000022
【００７４】
マトリックスＭ１、２は次のようにして見いだされる。Ｐ（ｓ，ｔ）は（１）により与えられ、
【００７５】
【数２１】
2006523891.tif 000023
【００７６】
が成り立つ。（９）で記述したように、各々のＢ＿ｉ（ｓ，ｔ）は、
【００７７】
【数２２】
2006523891.tif 000024
【００７８】
の線形結合として記述されることができる。すなわち
【００７９】
【数２３】
2006523891.tif 000025
【００８０】
である。洗練された表面は初期の表面と等価であることを必要とする。すなわち、
【００８１】
【数２４】
2006523891.tif 000026
【００８２】
である。この要件は、
【００８３】
【数２５】
2006523891.tif 000027
【００８４】
が成り立てば満足される。つまり、（１０）におけるＭ１，２の行ｊ及び列ｉでの要素は
【００８５】
【数２６】
2006523891.tif 000028
【００８６】
である。このように、Ｓｉ⊂Ｓｊと仮定して、Ｓｉの任意のＴ−スプラインをＳｊの等価なＴ−スプラインに写像する変換マトリックスＭｉｊを見いだすことができる。
Ｔ−スプラインの下位空間の定義Ｓｉ⊂Ｓｊは、Ｓｉの事前画像が持つ全ての制御点をＳｊの事前画像が有するということ以上を意味する。これは、他の制御点をも追加することなしには、現存するＴ−メッシュに所与の制御点を追加することが不可能なことがあるからである。局所洗練の章は、なぜ洗練であるかの洞察を提示し、Ｔ−スプラインに対する局所洗練アルゴリズムを提示する。勿論、これにより、所与のＴ−スプライン空間の有効な超空間を計算できるようになる。
【００８７】
局所洗練方法
Ｔ−スプライン局所洗練は、Ｔ−スプライン表面の形状を変更することなくＴ−メッシュに１つ以上の制御点を挿入することを意味する。この手続は局所ノット挿入とも呼ばれる。Ｔ−メッシュへの制御点の追加は、隣接する基底関数にノットを挿入することを伴うからである。
【００８８】
洗練アルゴリズムの本実施の形態は、トポロジー相と幾何学相という２つの相を有する。トポロジー相は、必要とされる制御点に加えて、どの制御点を挿入しなければならないかを識別する。必要とされる全ての新しい制御点が識別されると、Ｔ−スプライン空間についての章で示された線形変換を用いて、洗練されたＴ−メッシュに対するデカルト座標と重みが計算される。ここで、アルゴリズムのトポロジー相を説明する。
【００８９】
この議論の理解における重要な概念は、Ｔ−スプラインにおいては基底関数とＴ−メッシュが如何に緊密に結合されるかに留意することである。すなわち、全ての制御点について、対応する基底関数が存在し、各基底関数のノット・ベクトルは規則１によって定義される。この発明においては、基底関数は一時的にＴ−メッシュから分離される。これが意味するところは、計算方法の期間には、規則１に違反する基底関数の存在が許容され、基底関数が付されない制御点が一時的に存在するということにある。
【００９０】
ここでの議論は、洗練アルゴリズムの期間に起こり得る３つの可能な違反を区別する。
違反１．  そのときのＴ−メッシュに対して規則１により指示されるノットを基底関数が失っている。
違反２．  そのときのＴ−メッシュに対して規則１により指示されないノットを基底関数が有する。
違反３．  制御点が、それに関連する基底関数を持たない。
【００９１】
違反がない場合、Ｔ−スプラインは有効である。違反が存在する場合、アルゴリズムは更なる違反が存在しなくなるまで、違反を１つずつ解決する。次に、有効な超空間が見いだされる。
【００９２】
本発明の局所洗練アルゴリズムのトポロジー相は、以下の工程を含む。
１．  全ての必要とされる制御点をＴ−メッシュに挿入する。
２．  いずれかの基底関数が違反１を犯す場合、その基底関数への必要なノット挿入を実行する。
３．  いずれかの基底関数が違反２を犯す場合、適切な制御点をＴ−メッシュに追加する。
４．  違反が無くなるまで、工程２と３を繰り返す。違反１及び２の全ての場合の解決は、自動的に違反３の全ての場合を解決する。
【００９３】
例によって、本方法を説明する。図１４のａは、１つの制御点Ｐ２を挿入すべき初期のＴ−メッシュを示す。図１４のａのＴ−メッシュは有効なので、違反は存在しない。しかし、どの基底関数をも変更することなく、Ｔ−メッシュにＰ２を挿入する場合（図１４のｂ）、幾つかの違反が導入される。Ｐ２はノット座標（ｓ３，ｔ２）を有するので、４つの基底関数が違反１を犯すことになる。具体的には、４つの基底関数は（ｓ１，ｔ２）、（ｓ２，ｔ２）、（ｓ４，ｔ２）及び（ｓ５，ｔ２）を中心とする。これらの違反を解決するためには、基底関数洗練の章で議論したように、これらの基底関数の各々にｓ３においてノットを挿入しなければならない。（ｓ２，ｔ２）を中心とする基底関数は、Ｎ［ｓ０，ｓ１，ｓ２，ｓ４，ｓ５］（ｓ）Ｎ［ｔ０，ｔ１，ｔ２，ｔ３，ｔ４］（ｔ）である。この基底関数のｓノット・ベクトルにノットｓ＝ｓ３を挿入すると、当該基底関数は２つのスケーリングされた基底関数、すなわち、（７）で与えられる、（ｓ３−ｓ０）／（ｓ４−ｓ０）Ｎ［ｓ０，ｓ１，ｓ２，ｓ３，ｓ４］（ｓ）Ｎ［ｔ０，ｔ１，ｔ２，ｔ３，ｔ４］（ｔ）（図１４のｃ）及び（ｓ４−ｓ３）／（ｓ４−ｓ１）Ｎ［ｓ１，ｓ２，ｓ３，ｓ４，ｓ５］（ｓ）Ｎ［ｔ０，ｔ１，ｔ２，ｔ３，ｔ４］（ｔ）（図１４のｄ）に分割される。
【００９４】
図１４のｃにおける基底関数（ｓ３−ｓ０）／（ｓ４−ｓ０）Ｎ［ｓ０，ｓ１，ｓ２，ｓ３，ｓ４］（ｓ）Ｎ［ｔ０，ｔ１，ｔ２，ｔ３，ｔ４］（ｔ）は規則１を満足する。同様に、（ｓ１，ｔ２）、（ｓ４，ｔ２）及び（ｓ５，ｔ２）を中心とする混合関数の洗練は、全て規則１を満足する。しかしながら、図１４のｄに示す基底関数ｄ２Ｎ［ｓ１，ｓ２，ｓ３，ｓ４，ｓ５］（ｓ）Ｎ［ｔ０，ｔ１，ｔ２，ｔ３，ｔ４］（ｔ）のｔノット・ベクトルは違反２を犯す。これは、当該基底関数のｔノット・ベクトルが［ｔ０，ｔ１，ｔ２，ｔ３，ｔ４］（ｔ）であるが、規則１はｔ３においてはノットを要求しないからである。この問題は、底関数を洗練することによっては修復されないが、追加の制御点をＴ−メッシュに追加することで違反を解決することができる。
【００９５】
必要とされる制御点は図１４のｅにおけるＰ３である。この制御点の挿入は違反２の状況を解決するが、新しく違反１の状況を生成する。図１４のｆに示すように、（ｓ２，ｔ３）を中心とする混合関数は、規則１によって必要とされるｓ３を含まないｓノット・ベクトルを有する。当該ノット・ベクトルにｓ３を挿入することは問題を解決し、規則１の更なる違反は存在しない。
【００９６】
基底関数洗練と制御点の挿入は、Ｔ−メッシュに元々存在した、又は、工程１で追加されたノット値を含まなければならないので、この方法は終了する。最悪の場合にはこのアルゴリズムは、表面全体と交差するよう制御点の全ての部分行に拡張される。実際には、このアルゴリズムは、典型的には、ユーザが挿入したい制御点を超える追加の新しい制御点を殆ど必要としない。
【００９７】
局所ノット挿入は特徴の生成に有用である。例えば、図１５に示すように、ゼロのノット・インターバルを持つ制御点の幾つかの隣接する行を挿入することにより、ダートをＴ−スプラインに導入することができる。値ゼロの２つの隣接するノット・インターバルを持つことにより、局所３重ノットが導入され、表面は当該ノットにおいて局所的にＣ０になる。折り目の形状は、挿入された制御点の配置により制御される。折り目は、図１５のゼロのノット・インターバルを小さなゼロでないノット・インターバルで置換することにより、鋭さを低減させることができる。
【００９８】
Ｔ−スプラインのＢ−スプライン表面への変換
この洗練アルゴリズムは、Ｔ−スプライン空間の章で議論された変換マトリックスＭ１，ｎを計算することにより、Ｓ１におけるＴ−スプラインをＳｎにおける等価なＢ−スプライン表面に変換することを容易にする。
【００９９】
標準Ｔ−スプラインは、全ての重みｗｉ＝１であれば
【０１００】
【数２７】
2006523891.tif 000029
【０１０１】
が成立するスプラインである。これは、式（２）の分母が同じく１に等しいことを意味する。このため、基底関数は単位の分割を提供し、Ｔ−スプラインは多項式である。つまり、Ｔ−スプラインが標準であるための必要十分条件の代数的表現は、Ｍ１，ｎの各々の行の和が１になることである。
【０１０２】
挿入アルゴリズムは驚くような結果、すなわち、全ての重みがｗｉ＝１である訳ではないが
【０１０３】
【数２８】
2006523891.tif 000030
【０１０４】
が成り立つＴ−スプラインを生むことができる。このＴ−スプラインを準標準Ｔ−スプラインと呼ぶことができる。図１６は、準標準Ｔ−スプラインの２つの簡単な例を示している。幾つかのエッジの隣の整数（１及び２）はノット・インターバルである。準標準Ｔ−スプライン空間Ｓは、
【０１０５】
【数２９】
2006523891.tif 000031
【０１０６】
が成り立つが、全部のｗｉが１であるわけではないＳの幾つかの要素が存在する空間である。非標準Ｔ−スプライン空間は、
【０１０７】
【数３０】
2006523891.tif 000032
【０１０８】
である要素が存在しない空間である。これらの定義は、標準、準標準又は非標準のいずれかである有理（全ての重みが１とは限らない）Ｔ−スプラインの観念を許容するので、より精密なものである。区別は、どの形式のＴ−スプライン空間に属するかに基づいてなされる。
【０１０９】
図１７は、計算機環境においてメッシュを制御するために局所洗練を提供する双３次Ｔ−スプライン空間を定義するための方法の実施の形態の概要を示している。この方法に含まれる１つの操作は、ブロック２５０において、スプライン制御メッシュに関連するノット・インターバルを特定する。他の操作は、ブロック２５２において、ノット・インターバルに基づいて局所ノット座標系を課す。制御点に対する局所ノット・ベクトルは、ブロック２５４において、制御点に対する基底関数を生成するために推察される。更なる操作は、ブロック２５６において、表面を変更することなく制御メッシュに１つの制御点を挿入する。この制御点の挿入により、特別な制御点であるＴ−ジャンクションで終了する制御点の部分行を挿入することができる。
【０１１０】
ベジェ・パッチの抽出
Ｔ−スプラインを含むパッチをベジェ形式で表わすことは有益である。これは、モザイクに割れ目が現われないようにするために、各Ｔ−ジャンクションをモザイクでの三角の頂点に写像しなければならないという僅かな修正をしてモザイク法を適用するからである。
【０１１１】
標準Ｔ−スプラインを含むベジェ・パッチの領域は、図１８に示すように、全てのＴ−スプラインを２つのベイだけ延ばすことで決定される。図１８のｂの矩形はベジェ領域である。この理由は、各の制御点の基底関数に対するノット・ベクトルを考察することにより理解することができる。
【０１１２】
【数３１】
2006523891.tif 000033
【０１１３】
Ｂ−スプラインのＴ−スプラインへの併合
この章は、異なるノット・ベクトルを持つ２つのＢ−スプライン表面を単一のＴ−スプラインに如何に併合するかを検討する。幾何学的モデル化では、図２の手のように、異なるノット・ベクトルを有する異なるＢ−スプライン表面によってオブジェクトの一部が独立にモデル化されることが多い。図２０はこの問題を図示している。制御グリッドは異なるノット・ベクトルを超えて定義される。制御グリッドを単一のＢ−スプラインに併合するには、制御グリッドが同じ共通のノット・ベクトルを有することが必要であり、従って、併合が進められる前にノット挿入がまず実行されなければならない。しかしながら、図２０のｃが示すように、それに必要なノット挿入は制御点の行数を大幅に増加させ得る。それに続いて、追加の表面がこれら２つの表面に併合されるならば、ノット線の数は更に増大する。
【０１１４】
制御点を急増させることなく、２つのＮＵＲＢＳ表面を単一の表面に併合させる問題の１つの従来の解は、１９９８年にトーマス・Ｗ・セダーバーグにより導入された３次ＮＵＲＳＳの使用である。３次ＮＵＲＳＳは、面の対向するエッジ上の異なるノット・インターバルを許容するので、２つのＮＵＲＢＳ制御グリッドを、ノット線を伝搬することなく単一の制御グリッドに併合することができる。図２１は、異なるノット・ベクトルを有する２つの同等なＢースプライン・シリンダを併合した結果を示している。不都合なことに、任意のＮＵＲＳＳ表現は２つのシリンダの接続部に見苦しい隆起を導入する。ＮＵＲＳＳを用いて併合問題を解決しようとする試みの失敗がＴ−スプラインの生成を動機付ける助けとなった。
【０１１５】
Ｔ−スプラインを用いる手順が図２２に示される。Ｃｎ併合（ｎ∈｛−１，０，１，２｝）に対しては、１つのパッチ上の制御点のｎ＋１個の列が、他のパッチ上の制御点のｎ＋１個の列に対応する。最初に図２２のａのＣ０併合を考察する。まず、各Ｂ−スプラインは、図示されるように、共有する境界に沿って３重のノット（２重のノット・インターバル）を有する。Ｃ０併合については、制御点の一つの列が併合後に共有される。２つのＴ−スプラインに対するノット・インターバルが当該共通列に沿って異なれば、制御点は境界エッジに沿って配置されるので、ノット・インターバルは一致する。この例では、赤のＢ−スプライン上のノット・インターバルは１、３、２、２であり、青のＢ−スプライン上のノット・インターバルは２、１、４、１である。図示するような、直ぐに接続されるべき列に沿った各制御グリッドにオフセット制御点を挿入した後、制御点の共通列はノット・インターバル１、１、１、１、２、１、１を有する。
【０１１６】
このプロセスでは、典型的には、併合されるべき制御点は僅かに異なるデカルト座標を有する。例えば、赤のパッチ上のＡは青パッチ上のＡと僅かに異なる。併合される制御点の位置を決定するためには、これら２つの位置の平均を取るだけでよい。
【０１１７】
Ｃ２併合が図２２のｂに示されている。基本的な考え方はＣ０併合と同じである。違いは、図示されるように、４つのノット・インターバルａ，ｂ，ｃ，ｄが２つの表面の間で対応しなければならないということである。また、３列の制御点が図示のように併合されなければならない。図２３はＣ０及びＣ１併合の結果を示す。図４は、人間の手のＮＵＲＢＳモデルでのこの併合の能力の応用を示している。これはＣ０併合である。
【０１１８】
Ｔ−ＮＵＲＣＣ
Ｔ−ＮＵＲＣＣは、制御グリッドにＴ−ジャンクションを有し且つＴ−スプライン概念を用いたＮＵＲＣＣ（不均一有理キャットマル・クラーク表面）である。ＮＵＲＣＣはテンソル積不均一Ｂ−スプライン表面の一般化である。すなわち、異常点がなく、全ての表面が４辺形であり、各面の対向するエッジ上のノット・インターバルが等しい場合、ＮＵＲＣＣは不均一Ｂ−スプライン表面に縮退する。また、ＮＵＲＣＣはキャットマル・クラーク表面の一般化である。すなわち、全てのノット・インターバルが等しいならば、ＮＵＲＣＣはキャットマル・クラーク表面に縮退する。同様に、Ｔ−ＮＵＲＣＣはＴ−スプライン、キャットマル・クラーク表面及び３次ＮＵＲＢＳ表面の一般化である。
【０１１９】
ＮＵＲＣＣは、各々の４辺の面の対向するエッジが同じノット・インターバルを有するという制約を強制し、また、ＮＵＲＣＣは静的洗練規則を有する。また、この理由により、ＮＵＲＣＣは局所洗練ができる。
【０１２０】
各々の４辺の面の対向するエッジが同じノット・インターバルを持つことを要求するならば、ＮＵＲＣＣに対する洗練規則はＮＵＲＳＳに対する洗練規則と同じである。これらの洗練規則は１９９８年のトーマス・Ｗ・セダーバーグにおいて検討されている。
【０１２１】
ここで、異常点の近傍で局所洗練を実行するためにＴ−ジャンクションを如何に用いることができるかを検討する。検討を単純化するために、全ての異常点は少なくとも４つの面によって分離され、全ての面は４辺形である。これらの基準は、必要であれば、幾つかの大域的洗練工程を実行することにより充足され得る。その後、全ての洗練を局所的に実行することができる。例えば、ＮＵＲＣＣ制御グリッドの任意の適宜な大きさの正規のサブ・グリッドは、先に検討したように、局所ノット挿入を受けることができる。また、異常点に近い洗練を該異常点の近傍に閉じこめることができる。
【０１２２】
異常点の近傍での局所洗練を如何に実行するかを説明するために、Ｔ−スプラインでの単一（４価）の頂点の近傍で局所ノット挿入を実行するための方法を説明する。図２４を参照すると、洗練は黒の制御グリッドから始まる。次いで、全ての制御点を行１、行２、列３、列４の順に挿入するために、先に定義された手順を用いることは正当である。次に、同様の順序等で、追加の制御点を正当に挿入する。生成されるのは、１つの中央制御点の直ぐ近傍での局所洗練である。この洗練スキームは任意の比率ρで面を分割することができる。４価の点に対しては、単にＢ−スプライン・ノット挿入を行っているだけなので、ρを変化することは限界表面を変化させない。しかしながら、このスキームを異常点に適用した場合、ρは形状パラメータとして機能する。図２５はρを変えた影響を示す。
【０１２３】
ここで、孤立した異常点でのＴ−ＮＵＲＣＣに対する局所洗練規則を提示する。図２６を参照すると、ノット・インターバルｄｉは、ノット・インターバルρｄｉと（１−ρ）ｄｉとに分割される。異常点に隣接する他のノット・インターバルに対しても同様である。ρ＝１／２であって、全ての初期ノット・インターバルが等しいならば、局所洗練を用いて得られた限界表面はキャットマル・クラーク表面と等価である。
【０１２４】
小文字はノット・インターバルを指し、大文字は点を指す。頂点Ａ、Ｂ、Ｃ、Ｄ、Ｑ、Ｒ、Ｓ、Ｔは洗練前の初期制御点である。洗練後、これらの頂点はプライム記号で表わされる新しい頂点Ａ’、Ｂ’、Ｃ’、Ｄ’、Ｑ’、Ｒ’によって置換される。
【０１２５】
【数３２】
2006523891.tif 000034
【０１２６】
が成り立つ。３つの形のエッジ点Ｅ、Ｈ及びＧが存在する。ここで、
【０１２７】
【数３３】
2006523891.tif 000035
【０１２８】
であり、ただし、
【０１２９】
【数３４】
2006523891.tif 000036
【０１３０】
である。エッジ点Ｈ１は
【０１３１】
【数３５】
2006523891.tif 000037
【０１３２】
で表され、エッジ点Ｇ１は
【０１３３】
【数３６】
2006523891.tif 000038
【０１３４】
で表される。
５つの異なる形の頂点が存在する。これらはＡ、Ｂ、Ｑ、Ｄ、Ｒを置換したものである。Ａ、Ｂ、Ｑ、Ｄ、Ｒでの新しい頂点をＡ’、Ｂ’、Ｑ’、Ｄ’、Ｒ’で表わす。そうすると、
【０１３５】
【数３７】
2006523891.tif 000039
【０１３６】
であり、ｎは価であり、ｍｉ＝（ｈｉ−１＋ｈｉ＋１）（ｈｉ−２＋ｈｉ＋２）／２であり、ｆｉ＝ｈｉ−１ｈｉ＋２である。更に、
【０１３７】
【数３８】
2006523891.tif 000040
【０１３８】
が成り立つ。
そのような異常点での局所洗練は、４工程の局所洗練を受けたＴ−ＮＵＲＣＣを示す図６に示されている。黄色の点は４つのＴ−ジャンクションを強調する。この局所的に洗練されたメッシュは、大域的キャットマル・クラーク洗練を用いたときよりも２けた少ない面を有する。
【０１３９】
この検討が仮定したのは、異常頂点は少なくとも４つの面により分割されるということであり、これは幾つかの事前の大域的洗練工程を実行することにより達成され得る。そのような初期大域的洗練工程を必要としない局所洗練規則を導出することは可能であるが、考察すべき追加の特別な場合が存在する。
【０１４０】
異常点から離れると、ゼロのノット・インターバルが連続性を低下させることを除いて、ＮＵＲＣＣはＣ２である。全てのエッジが同じノット・インターバル値を有する異常点では、３価の場合に対する固有解析がλ１＝１＞λ２＝λ３＞λ４＞．．．であることを示す。ただし、例えば
【０１４１】
【数３９】
2006523891.tif 000041
【０１４２】
である。これは、３価の場合に対しては、ρ（０＜ρ＜１）の任意の正当値について表面はＧ１であることの解析的証明を与える。同様の結果を５価に対して得ることができる。更に価が高い場合には、記号代数表現は扱いにくくなるが、ρの特定値のサンプリングは、Ｇ１条件が満足されない場合を明かしてはいない。異常点の近傍のエッジに対するノット・インターバルが等しくなければ、経験的な証拠はＧ１を示唆する。
【０１４３】
Ｔ−スプライン及びＴ−ＮＵＲＣＣは真の局所洗練を許容する。表面の形状を変化させることなく制御点を追加することができ、（ゼロの値を有するノット・インターバルが存在しなければ）新しい制御点を移動させることができ、表面はＣ２のままである。Ｔ−ＮＵＲＣＣはＮＵＲＢＳとキャットマル・クラーク表面を一般化するので、Ｔ−ＮＵＲＣＣに基づくモデル化問題は、特別な場合として任意のＮＵＲＢＳ又はキャットマル・クラークのモデルを取り扱うことができる。
【０１４４】
本発明を、双３次Ｂ−スプライン表面を用いて説明してきた。しかしながら、本発明は、任意の次数のＢ−スプライン表面を用いて同様に具体化することができる。本発明で説明された概念は当業者が任意の次数のＴ−スプラインを誘導することができるようにするが、これは直接的な実行である。偶数次のＴ−スプラインと奇数次のＴ−スプラインとの間の１つの差違は、偶数次のＴ−スプラインに対してはノット・インターバルは制御点に関連し、奇数次のＴ−スプラインに対してはノット・インターバルは制御グリッドのエッジに関連するということである。
【０１４５】
本発明の１つの追加の用途は、Ｔ−ＮＵＲＣＣを用いて、２つのＴ−ＮＵＲＣＣの交点、又は、双３次ＮＵＲＢＳ表面又はＴ−スプラインのようなＴ−ＮＵＲＣＣの任意の特別な場合の交点に対する継ぎ目のない表現を提供することである。
【０１４６】
理解されるように、上で参照した構成は、本発明の原理についての応用の例である。当業者には明らかなように、特許請求の範囲に記載された発明の原理と概念から逸脱することなく、多数の変形を行うことができる。
【図面の簡単な説明】
【０１４７】
【図１】人間の頭のＮＵＲＢＳモデルの斜視図である。
【図２】人間の手のＮＵＲＢＳモデルを描いた図である。
【図３】図２の手のＮＵＲＢＳモデルにおける、隣りあう表面が正確には接合していない穴を描いた図である。
【図４】本発明の実施の形態を用いた、Ｔ−スプラインを用いて補正された図２の人間の手のＮＵＲＢＳモデルの２つの表面を描いた図である。
【図５】ＮＵＲＢＳ表面としてモデル化された頭と、本発明の実施形態においてＴ−スプライン表面としてモデル化された頭とを示す図である。
【図６】Ｔ−ＮＵＲＣＣ局所洗練を用いて洗練した、キャットマル・クラーク・メッシュの実施の形態を描いた図である。
【図７】計算環境において双３次スプライン表面を定義するための方法の実施の形態を示すフローチャートである。
【図８】ノット・ベクトルを伴う３次Ｂ−スプライン曲線の例を示す図である。
【図９】ａ及びｂは、ノット・インターバルでラベル付けされたＮＵＲＢＳ制御メッシュの領域を示す図である。
【図１０】（ｓ，ｔ）パラメータ空間におけるＴ−メッシュの一部の事前画像の実施の形態を示す図である。
【図１１】基底関数Ｂｉ（ｓ，ｔ）に対するノット・ラインを示す図である。
【図１２】本発明の実施の形態におけるＢｉ（ｓ，ｔ）の洗練のサンプルを示す図である。
【図１３】Ｔ−スプライン空間のネスト化されたシーケンスの実施の形態を示す図である。
【図１４】ａ〜ｆは、本発明の実施の形態における局所的洗練例を示す図である。
【図１５】本発明の実施の形態におけるＴ−メッシュでのダートの挿入を示す図である。
【図１６】本発明の実施の形態における準標準Ｔ−スプラインを描いた図である。
【図１７】計算機環境において制御メッシュの局所洗練を提供する双３次スプライン表面を定義する方法の実施の形態を示すフローチャートである。
【図１８】本発明の実施の形態におけるＴ−メッシュの事前画像でのベジェ領域を示す図である。
【図１９】ａ及びｂは、局所的ノット挿入を用いたベジェ制御点の生成を示す図である。
【図２０】２つのＢ−スプラインの併合を示す図である。
【図２１】３次元ＮＵＲＳＳを用いた２つのＢ−スプラインの併合と、該併合により生じる問題を示す図である。
【図２２】本発明の実施の形態におけるＴ−スプラインを用いた２つのＢ−スプラインの併合を示す図である。
【図２３】本発明の実施の形態における、Ｂ−スプライン、Ｃ０Ｔ−スプライン及びＣ１Ｔ−スプラインを用いた２つの表面の併合の結果を示す図である。
【図２４】４価制御点についてのＴ−スプラインを用いた局所的洗練を示す図である。
【図２５】ｎ価制御点についてのＴ−スプラインを用いた局所的洗練を示す図である。
【図２６】パラメータρの影響を示すＴ−ＮＵＲＣＣを描いた図であり、上左の制御グリッドの限界表面はρ＝０．１であり、上右はρ＝０．５であり、下右はρ＝０．９である。
【図１】
2006523891.tif 000042
【図２】
2006523891.tif 000043
【図３】
2006523891.tif 000044
【図４】
2006523891.tif 000045
【図５】
2006523891.tif 000046
【図６】
2006523891.tif 000047
【図７】
2006523891.tif 000048
【図８】
2006523891.tif 000049
【図９】
2006523891.tif 000050
【図１０】
2006523891.tif 000051
【図１１】
2006523891.tif 000052
【図１２】
2006523891.tif 000053
【図１３】
2006523891.tif 000054
【図１４】
2006523891.tif 000055
【図１５】
2006523891.tif 000056
【図１６】
2006523891.tif 000057
【図１７】
2006523891.tif 000058
【図１８】
2006523891.tif 000059
【図１９】
2006523891.tif 000060
【図２０】
2006523891.tif 000061
【図２１】
2006523891.tif 000062
【図２２】
2006523891.tif 000063
【図２３】
2006523891.tif 000064
【図２４】
2006523891.tif 000065
【図２５】
2006523891.tif 000066
【図２６】
2006523891.tif 000067
【国際調査報告】
2006523891.tif 000068
2006523891.tif 000069