(57)【要約】シェーディングにより生成するコンピュータグラフィックス方法であって、Ａ．対象物の画像との関連において、画像の少なくとも一部分の明度レベルにおける変化を表現している、オペレータにより提供されるシェーディング情報を受け取るステップと、Ｂ．更新幾何学的モデルの少なくとも１つの幾何学的特徴を決定するために使用されるシェーディング情報に応じて、対象物の更新幾何学的モデルを生成するステップと、Ｃ．更新幾何学的モデルにより定義されるように対象物の画像を表示するステップと、を含み、Ｄ．前記方法は、任意の階層的細分割曲面、ポリゴンメッシュ、またはＮＵＲＢＳ曲面のデジタル入力により作動できる。【選択図】図１３
2009521062.tif 000002
【特許請求の範囲】
【請求項１】
三次元（３Ｄ）対象物の表面の少なくとも一部分の幾何形状を表現する幾何学的モデルを、画像平面上に投影された前記対象物を表現する、前記対象物の二次元（２Ｄ）画像に関連してオペレータによるシェーディングにより生成するコンピュータによる製図方法であって、
Ａ．前記対象物の前記画像との関連において、前記画像の少なくとも一部分の明度レベルにおける変化を表現している、前記オペレータにより提供されるシェーディング情報を受け取り、
Ｂ．更新幾何学的モデルの少なくとも１つの幾何学的特徴を決定するために使用される前記シェーディング情報に応じて、前記対象物の前記更新幾何学的モデルを生成し、
Ｃ．前記更新幾何学的モデルにより定義されたように、前記対象物の前記画像を表示し、さらに、
Ｄ．前記方法は、任意の階層的細分割曲面、ポリゴンメッシュ、またはＮＵＲＢＳ曲面のデジタル入力により作動できる、
ことを特徴とする、製図方法。
【請求項２】
いったん細分割曲面が生成され、ユーザーに表示されると、２Ｄモデルビューと整合される、
ことを特徴とする、請求項１記載の方法。
【請求項３】
前記２Ｄモデルビューは、格子の隅と、格子の幅と高さと、ピクセルサイズと、カメラから対象物への変換とについての情報を含む、
ことを特徴とする、請求項２記載の方法。
【請求項４】
前記２Ｄモデルビューを利用して、前記ユーザーは照明方向を設定し、入力パラメータとシェードを調整し、それにより選択されたピクセルの強度を修正するか、または予めシェーディングされたピクセルの集合をロードし、次にこの情報は整形アルゴリズムに利用され、
前記パラメータは、（ａ）前記修正領域においてどの程度の細分割が起きるかに対する影響と、（ｂ）前記幾何学的修正がどの程度目立つかに対する影響、のいずれかを含むことができる、
ことを特徴とする、請求項３記載の方法。
【請求項５】
前記整形アルゴリズムは、前記表面に対する正確な幾何学的変更を決定し、
追加的表面基本形状が、前記シェーディング領域における細分割を介して、十分な詳細が存在することを確実にするために必要な場合に追加され、
前記２Ｄ設定において要求された前記変化を３Ｄにおいて反映する高さフィールドが決定され、次に前記細分割曲面は、前記決定された高さの値を反映するように変更され、
それにより、更に変更、保存、または所望の出力表面タイプに変換できる、整形された、階層的細分割曲面という結果になり、
表面基本形状は、三角形、四角形、または他の多角形のいずれかを含むことができる、
ことを特徴とする、請求項４記載の方法。
【請求項６】
基盤となる細分割曲面を作成し、
２Ｄシェードビューを表示し、
ユーザーが照明、シェーディングを設定し、パラメータを調整できるようにし、
整形処理を実行し、それにより３Ｄ細分割曲面を生成し、
前記整形処理は、
前記表面上に詳細を導入し、
前記表面に対して新しい高さパラメータを決定し、
前記細分割曲面を整形し、さらに、
前記パラメータは、（ａ）前記修正領域においてどの程度の細分割が起きるかに対する影響および、（ｂ）前記幾何学的修正がどの程度目立つかに対する影響、のいずれかを含むことができる、
ことを特徴とする、請求項１記載の方法。
【請求項７】
メッシュ表現またはＮＵＲＢＳ曲面のいずれかを含む入力を受け取り、
前記入力がまだ階層的細分割曲面でない場合は、前記入力を階層的細分割曲面に変換し、
前記階層的細分割曲面上でシェーディングと整形を実行する、
ことを特徴とする、請求項６記載の方法。
【請求項８】
前記表面に詳細を追加するために適合細分割を利用し、変化を前記表面のすべてのレベルに伝播するために分析と合成を利用し、それにより、詳細の選択されたレベルでの修正を可能にする、
ことを特徴とする、請求項７記載の方法。
【請求項９】
階層的細分割曲面ライブラリを提供する、
ことを特徴とする、請求項６記載の方法。
【請求項１０】
前記ＳＢＳ処理に起因する前記細分割曲面モデルを、別の表面タイプに変換する、
ことを特徴とする、請求項９の方法。
【請求項１１】
【数１】
2009521062.tif 000307
ここで、Ｉは前記ピクセル（ｕ，ｖ）における前記離散強度であって、ｌは無限に離れたシミュレートされた光源の方向を指し示す単位ベクトルであり、Ｈは関連する高さフィールドであり、ＣＨは関連する高さフィールドＨを有する曲面の曲率を表わし、λは平滑係数であり、合計は、前記投影曲面の内部と交差する前記モデルビューにおけるピクセル上において実行される式により与えられる関数を最小化する、上記の式により、前記モデルビュー上の高さ増分Γの集合を生成するように構成される選択された整形操作を適用する、
ことを特徴とする、請求項６記載の方法。
【請求項１２】
前記高さ増分Γの集合は、前記関数が、
【数２】
2009521062.tif 000308
の前記非制約最小化に縮小されるように、その対応する高さ値が、前記整形アルゴリズムにより変更できる、各ピクセルまたは接続領域に対して１つの入力を含むベクトルｘに縮小でき、前記最小化を実行するために使用される前記方法は、信頼領域法である、
ことを特徴とする、請求項１１記載の方法。
【請求項１３】
前記モデルビューにおいて見られるように、前記投影曲面全体に対して前記計算を行う必要がないように、前記投影曲面の内部と交差する、前記モデルビューにおけるすべてのピクセル上の合計から、それを修正ピクセルの近傍と交差させることにより、Ｑと称される縮小された集合上のみの合計への縮小を更に含む、
ことを特徴とする、請求項１２記載の方法。
【請求項１４】
前記信頼領域法は、下記の二次関数
【数３】
2009521062.tif 000309
ここで、
2009521062.tif 000310
はｆの勾配ベクトルであり、
2009521062.tif 000311
はｆのヘッシアン行列である式により、まず前記関数を第１モデル化し、
次に、
2009521062.tif 000312
の領域で、ある
2009521062.tif 000313
に対して前記モデルＦを最小化する、
ことを特徴とする、請求項１２記載の方法。
【請求項１５】
前記最小化を実践するために利用される前記方法は、特殊疎行列乗算を伴うCG-Steihaug法であり、
テスト値は、結果としての最小点ｘ１から構築され、下記の
【数４】
2009521062.tif 000314
であり、
ρが１に近ければ、Ｆは信頼領域内でｆに対して良好なモデルと考えられ、前記信頼領域の中心はｘ１に移動され、前記信頼領域の半径は増大され、一方、ρが１から離れていれば、前記信頼領域の半径は減少され、
前記処理は、前記信頼領域においてＦに対する最小値が求まるまで繰り返され、
前記処理を終了するための前記基準は、
2009521062.tif 000315
が、ｆの極小値が達成された前記現在の信頼領域の中心において十分に小さいかどうか、である、
ことを特徴とする、請求項１４記載の方法。
【請求項１６】
前記方法を、コンピュータ援用デザイン（ＣＡＤ）システム、コンピュータグラフィックスシステム、または幾何形状を作成、表示、操作、またはモデル化するように作動するソフトウェアアプリケーションのいずれかと相互作動が可能なように適合されたコンピュータソフトウェアプラグイン製品として実装する、
ことを特徴とする、請求項１５記載の方法。
【請求項１７】
前記プラグイン製品の機能は、
２Ｄ描画機能と、シェーディング、光制御、パラメータ調整、シェーディング情報に基づく表面形状の更新、光方向、および入力パラメータ、アンドゥ／リドゥ機能をモディファイヤの内部にロードおよび保存する機能を有するシェーディングツールと、
マスキング技術を利用して、更新する領域を選択するツールと、
標準細分割曲面操作の集合を有する選択ツールと、のいずれかを含み、
前記パラメータは、前記修正領域においてどの程度の細分割が起きるかに対する影響（ａ）および前記幾何学的修正がどの程度目立つかに対する影響（ｂ）のいずれかを含むことができる、
ことを特徴とする、請求項１６記載の方法。
【請求項１８】
ポリゴンメッシュまたはＮＵＲＢＳ曲面上で、前記ＳＢＳ処理を、まず細分割曲面の特性に変換、またはそれを使用することなくできる能力を更に含む、
ことを特徴とする、請求項１０記載の方法。
【請求項１９】
大きく、複雑なメッシュを、インタラクティブな性能で表示する能力を更に含む、
ことを特徴とする、請求項１０記載の方法。
【請求項２０】
表面全体にわたり任意にトリミングする能力を更に含む、
ことを特徴とする、請求項１０記載の方法。
【請求項２１】
輪郭線を描いて、前記ＳＢＳモデル化処理との関連において使用できる初期３Ｄ形状を生成する能力を更に含む、
ことを特徴とする、請求項１０記載の方法。
【請求項２２】
三次元対象物の表面の少なくとも一部分の幾何形状を表現する幾何学的モデルを、前記対象物を画像平面上に投影されたものとして表現する、前記対象物の二次元画像との関連におけるオペレータによるシェーディングにより生成するコンピュータグラフィックスシステムであって、
Ａ．前記画像の少なくとも一部分の明度レベルにおける変化を表現している、前記オペレータにより提供されるシェーディング情報を受け取るように構成されるオペレータ入力装置と、
Ｂ．前記オペレータ入力装置から前記シェーディング情報を受け取り、それに応じて、前記対象物の更新された幾何学的モデルを生成するように構成され、前記シェーディング情報を使用して、前記更新幾何学的モデルの少なくとも１つの幾何学的特徴を決定するように構成されるモデルジェネレータと、
Ｃ．前記対象物の画像を、前記更新幾何学的モデルにより定義されるように表示するように構成される対象物表示装置と、を備え、
Ｄ．前記システムは、任意の階層的細分割曲面、ポリゴンメッシュ、またはＮＵＲＢＳ曲面を容認できる、
ことを特徴とする、コンピュータグラフィックスシステム。
【請求項２３】
人間が使用可能な入力装置と、人間が認識できる表示を生成するように作動できる表示装置とを備えるコンピュータグラフィックスシステム内で実行可能なコンピュータプログラム製品であって、
前記コンピュータプログラム製品は、前記コンピュータグラフィックスシステムにより実行でき、コンピュータ読取可能媒体上にコード化されるコンピュータソフトウェアコード命令を含み、
前記コンピュータプログラム製品は、前記コンピュータグラフィックスシステム内で動作可能で、三次元対象物の表面の少なくとも一部分の幾何形状を表現する幾何学的モデルを、前記対象物を画像平面上に投影されたものとして表現する、前記対象物の二次元画像との関連におけるオペレータによるシェーディングにより生成でき、前記コンピュータプログラム製品は、
Ａ．前記画像の少なくとも一部分の明度レベルにおける変化を表現している、オペレータが入力装置を使用することにより提供されるシェーディング情報を受け取るように作動可能な第１コンピュータソフトウェアコード手段と、
Ｂ．前記オペレータ入力装置から前記シェーディング情報を受け取り、それに応じて、前記対象物の更新された幾何学的モデルを生成するように作動でき、前記シェーディング情報を使用して、前記更新幾何学的モデルの少なくとも１つの幾何学的特徴を決定するように作動可能なモデル・ジェネレータ・コンピュータ・ソフトウェア・コード手段と、
Ｃ．前記コンピュータグラフィックスシステムが、表示装置上に、前記更新幾何学的モデルにより定義されるように、前記対象物の画像を表示できるように構成される対象物表示コンピュータソフトウェアコード手段と、を備え、
Ｄ．前記コンピュータプログラム製品は、任意の階層的細分割曲面、ポリゴンメッシュ、またはＮＵＲＢＳ曲面を容認するように作動できる、
ことを特徴とする、コンピュータプログラム製品。
【請求項２４】
信頼領域ニュートン−ＣＧ法を使用することにより最小化するステップを更に含む、
ことを特徴とする、請求項１４記載の方法。
【請求項２５】
残差を利用して、前記関数、その勾配およびそのヘッシアンを得る、
ことを特徴とする、請求項２４記載の方法。
【請求項２６】
計算は、ＡＰＩと共に、またはその中へ統合される、
ことを特徴とする、請求項１４記載の方法。
【請求項２７】
計算は、コンピュータ・ソフトウェア・アプリケーション・プラグインと共に、またはその中へ統合される、
ことを特徴とする、請求項１４記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータグラフィックス、コンピュータ援用幾何学的設計などの分野に関し、特に、二次元画像のシェーディングにより、対象物の三次元形状をモデル化する、改善されたシステムおよび技術に関する。
【背景技術】
【０００２】
コンピュータグラフィックス、コンピュータ援用幾何学的設計などにおいては、アーティスト、製図者など（ここでは、「オペレータ」と総称する）は、コンピュータに維持される対象物の三次元モデルを、対象物の二次元ビューを定める線から生成しようと試みる。従来、コンピュータグラフィックス装置は、三次元モデルを、例えば、対象物の輪郭および／または断面を含む種々の二次元線画から生成し、そのような線に多数の操作を施して、三次元空間における二次元曲面を生成する。そして、そのような曲面のパラメータおよび制御点を修正して、対象物の結果としてのモデルの形状を補正または修正していた。対象物に対する三次元モデルが生成された後は、多数の方向のいずれからもそれを見る、または表示できる。
【０００３】
ロボットビジョンまたはマシンビジョン（ここでは、「マシンビジョン」と総称される）と通常称される人工知能の分野においては、「シェーディングからの形成化」と称される方法を使用して、カメラにより記録されたような対象物の１つまたは複数の二次元画像から、実在する対象物の三次元モデルを生成する。一般的には、マシンビジョンにおいては、画像上に記録された対象物のタイプは、最初はマシンにより知られてなく、生成される対象物のモデルは、例えば、マシンまたは他の装置により、画像上で示される対象物のタイプの特定を容易にするために一般的には使用される。
【０００４】
シェーディングからの形成化方法においては、モデル化される対象物が光源により照らされ、写真機またはビデオカメラのようなカメラにより、画像が記録され、その画像から対象物がモデル化される。光源の方向、カメラの位置、および対象物に対する画像平面は既知であることが仮定されている。更に、対象物の表面の反射特性もまた既知であることが仮定されている。正投影技術を使用して、対象物の表面を画像平面上に投影することも更に仮定されている。つまり、画像を画像平面上に記録する、明示されていないカメラは、無限の焦点距離を有することが仮定されている。画像平面は、ｘ、ｙ座標軸を表現し（つまり、画像平面上の任意の点は、座標（ｘ，ｙ）により特定できる）、そしてｚ軸は、画像平面に直交する。その結果、画像平面上に投影できる対象物の曲面上の任意の点は、座標（ｘ，ｙ，ｚ）により表現できる。画像平面上に投影される対象物の画像は、二次元定義域
2009521062.tif 000003
上での画像照射関数Ｉ（ｘ，ｙ）により表現され、一方、対象物の形状は、定義域
2009521062.tif 000004
上の高さ関数ｚ（ｘ，ｙ）により与えられる。
【０００５】
画像照射関数Ｉ（ｘ，ｙ）は、画像内での各点（ｘ，ｙ）における対象物の明度を表現している。シェーディングからの形成化方法では、定義域におけるすべての点（ｘ，ｙ）に対してＩ（ｘ，ｙ）が与えられれば、対象物の形状は、ｚ（ｘ，ｙ）で与えられて決定される。
【０００６】
対象物の二次元画像に適用されるシェーディングにより、対象物の三次元モデルを生成する改善された方法およびシステムを提供することは望ましいことであろう。
【発明の開示】
【０００７】
本発明は、シェーディングにより、対象物の三次元モデルを生成する改善された方法およびシステムを提供する。
【０００８】
本発明の１つの形態は、同一所有されている米国特許第６，７２４，３８３号明細書に記載されているシェーディングによる形成化（ＳＢＳ）のシステムおよび方法を改善する。
【０００９】
本発明の別の形態は、本発明に従う、シェーディングによる形成化（ＳＢＳ）モデラにおいて実装できる特別な整形技術、方法、およびアルゴリズムに関し、特別には、有利に信頼領域法を利用する方法とアルゴリズムに関する。
【発明を実施するための最良の形態】
【００１０】
・関連出願への相互参照
本特許出願は、共有されている、２００４年３月５日付けで出願した、継続中の米国出願番号第１０／７９５，７０４号明細書（代理人整理番号  ＭＥＮＴ−００３Ｄ１）の一部継続出願である。上記出願は、１９９８年２月２０日付けで出願した、米国出願番号第０９／０２７，１７５号（代理人整理番号  ＭＥＮＴ−００３）の分割出願であって、１９９７年２月２１日付けで出願した、米国仮出願第６０／０３８，８８８号明細書（代理人整理番号  ＭＥＮＴ−００３−ＰＲ）の利益を主張するものである。上記３つの出願を参考文献として参照により本願明細書に引用する。
また、本発明は、２００５年１２月２０日付けで出願した、米国仮出願第６０／７５２，２３０号明細書（代理人整理番号  ＭＮＴＬ−１０６−ＰＲ）、及び、２００６年８月２４日付けで出願した、米国仮出願第６０／８２３，４６４号明細書（代理人整理番号  ＭＥＮＴ−０８９−Ｂ−ＰＲ）の利益を主張するものである。これらの２つの出願も参考文献として参照により本願明細書に引用する。
さらに、ここで引用する、いずれも許可された、２００１年５月９日付けで出願した、米国出願番号第０９／８５２，９０６号明細書（ＭＥＮＴ−０６０）、及び、２００２年２月１日付けで出願した、米国出願番号第１０／０６２，１９２号明細書（ＭＥＮＴ−０６２）も共有されている。
本発明のこれらの、および他の形態、実施形態、実行、実装、および例は、次のような節／項に分けられている下記の詳細な説明において記載される。
Ｉ．発明を実装できるデジタル処理環境
ＩＩ．ＳＢＳモデラ
ＩＩＩ．ＳＢＳモデラの改善
３．１  序章
３．２  ＳＢＳシェーディングおよび整形処理
３．３  表面処理の改善
３．４  追加的整形アルゴリズム
３．５  ＳＢＳ  Ｃ＋＋  ＡＰＩ
３．６  プロトタイプ：３ｄｓ  ｍａｘ用ＳＢＳプラグイン
３．７  ＳＢＳの拡張
ＩＶ．ＳＢＳモデラ内で実装される整形方法およびアルゴリズム
４．１  序章
４．２  ラスタライゼーション
４．３  最小化される関数の縮小
４．４  信頼領域ニュートン−ＣＧ法
４．５  信頼領域モデルの計算
４．６  信頼領域モデルの最小化
４．７  信頼領域ニュートン−ＣＧ法の収束
Ｖ．一般化された方法のフローチャート
【００１１】
Ｉ．発明を実装できるデジタル処理環境
本発明の特別な例と実施形態を説明する前に、下記に、本発明が実装および実行できる基盤となるデジタル処理構造および環境についての、図１〜図４と関連して読むべき検討を示す。
【００１２】
当業者は、本発明を、動画または他の動的表示における表示に対するように、画像の生成および合成に利用できるということを理解するであろう。ここで説明する技術は、コンピュータグラフィックスシステムの一部として実行することができ、そこにおいて、ピクセル値が画像内のピクセルに対して生成される。ピクセル値は、シミュレートされたカメラの画像平面上に記録される場面における点を表現している。基盤となるコンピュータグラフィックスシステムは、本発明の方法のような、ある選択された方法を使用して、画像に対してピクセル値を生成するように構成できる。
【００１３】
下記の詳細な説明は、これらの技術に従う方法、構造、システム、およびコンピュータソフトウェア製品の例を示している。当業者には、記載される方法およびシステムが、ソフトウェア、ハードウェア、またはソフトウェアとハードウェアの組合せにおいて、スタンドアロン構成またはネットワークを介して、Microsoft Windows、Linux、またはUnixのような従来のオペレーティングシステムに従って（またはエミュレーションにより）作動する、パーソナルコンピュータ（ＰＣ）または等価の装置のような従来のコンピュータ装置を使用して実装できるということが理解されよう。従って、ここで説明される種々の処理形態および手段は、適切に構成されたデジタル処理装置または装置のネットワークの、ソフトウェアおよび／またはハードウェア構成要素において実装できる。処理は連続して、または並行して実行でき、および特殊用途または再構成可能ハードウェアを使用して実装できる。
【００１４】
例として、ここに添付されている図１は、そのようなコンピュータグラフィックス処理を実行できる例としてのコンピュータシステム１０を示している。図１を参照すると、１つの実施形態におけるコンピュータシステム１０は、プロセッサモジュール１１と、キーボード１２Ａおよび／またはマウス１２Ｂのようなオペレータ入力構成要素を含むオペレータインタフェース要素（または、一般的に、オペレータ入力要素１２として特定されるデジタイジングタブレットまたは他の類似要素）と、ビデオ表示装置１３のようなオペレータ出力要素を含む。例としてのコンピュータシステム１０は、従来の格納プログラムコンピュータアーキテクチャであってよい。プロセッサモジュール１１は、例えば、１つまたは複数のプロセッサと、メモリと、ディスクおよび／またはテープ格納要素（分離しては図示されていない）のような大容量格納装置を含むことができ、そこに提供されるデジタルデータと関連する処理および格納動作を実行する。オペレータ入力要素１２は、オペレータが処理のための情報を入力することを可能にするために提供できる。ビデオ表示装置１３は、スクリーン１４上に、プロセッサモジュール１１により生成された出力情報をオペレータに表示するために提供でき、出力情報には、オペレータが処理のために入力できるデータや、オペレータが処理を制御するために入力できる情報が、処理中に生成された情報と共に含まれる。プロセッサモジュール１１は、種々のアプリケーションプログラム用の情報が、種々の「ウィンドウ」を使用して表示される、いわゆる「グラフィカルユーザーインタフェース」（「ＧＵＩ」）を使用して、ビデオ表示装置１３による表示のための情報を生成できる。
【００１５】
コンピュータシステム１０は、オペレータから入力情報を受け取るためのキーボード１２Ａとマウス１２Ｂや、オペレータに出力情報を表示するためのビデオ表示装置１３のような特別な構成要素を含んで示されているが、コンピュータシステム１０は、図１に示されているものに加えて、またはそれらの代わりに多様な構成要素を含むことができるということは理解されよう。
【００１６】
更に、プロセッサモジュール１１は、全体としては参照番号１４により特定される１つまたは複数のネットワークポートを含むことができ、ネットワークポートは、コンピュータネットワーク内のコンピュータシステム１０に接続する通信リンクに接続されている。ネットワークポートにより、コンピュータシステム１０は情報を、ネットワーク内の他のコンピュータシステムおよび他の装置に送信でき、また、それらから情報を受信することができる。例えば、クライアント−サーバーパラダイムに従って構成された典型的なネットワークにおいては、ネットワーク内におけるあるコンピュータシステムはサーバーとして指定され、他のクライアントコンピュータシステムによる処理のためにデータおよびプログラム（総称して「情報」）を格納し、それにより、クライアントコンピュータシステムは便利に情報を共有できる。特別なサーバーにより維持された情報へアクセスする必要のあるクライアントコンピュータシステムは、サーバーがネットワークを介してそこに情報をダウンロードできるようにする。データの処理後は、クライアントコンピュータシステムはまた、処理されたデータを格納のためにサーバーに戻す。コンピュータシステム（上記のサーバーおよびクライアントを含む）に加えて、ネットワークはまた、例えば、プリンタ、ファクシミリ装置、デジタルオーディオまたはビデオ格納装置および配布装置など、ネットワーク内で接続された種々のコンピュータシステム間で共有できる装置を含んでもよい。ネットワーク内でコンピュータシステムを相互接続する通信リンクは、従来のように、ワイヤ、光ファイバー、またはコンピュータシステム間で信号を搬送するための他の媒体を含む、任意の便利な情報搬送媒体を備えてもよい。コンピュータシステムは、通信リンクを介して転送されるメッセージにより、ネットワーク上で情報を転送し、各メッセージは、情報と、そのメッセージを受信する装置を特定する識別子を含む。
【００１７】
図に示されているコンピュータシステム１０に加えて、本発明に従う方法、装置、またはソフトウェア製品は、図２に例として示されている（例えば、ネットワークシステム１００）ような、従来のＰＣ１０２、ラップトップ１０４、手持ち、または携帯コンピュータ１０６を含む、スタンドアロンであろうが、ネットワーク化されていようが、携帯型であろうが、固定されていようが、または、インターネットまたは他のネットワーク１０８を介して、そしてその結果サーバー１１０と格納装置１２０を含むことができる、幅広い範囲の従来のコンピュータ装置およびシステムの何れにおいても作動できる。
【００１８】
従来のコンピュータソフトウェアおよびハードウェアの実行と同調して、本発明に従って構成されたソフトウェアアプリケーションは、例えば、図２と図３に示されているようなＰＣ１０２内で作動でき、プログラム指令は、ＲＯＭまたはＣＤ  ＲＯＭ１１６（図３）、磁気ディスク、または他の格納装置１２０から読み込まれ、ＣＰＵ１１８による実行のためにＲＡＭ１１４にロードできる。データは、従来のキーボード、スキャナー、マウス、デジタイジングタブレット、または他の要素１０３を含む任意の知られている装置または手段を介してシステムに入力できる。
【００１９】
当業者は、ここで記述される本発明の方法形態が、ＡＳＩＣ製造業者には知られているＡＳＩＣ構築技術を使用して、ここで記述される処理を実行するために特別に構築された特定用途向け集積回路（ＡＳＩＣ）のようなハードウェア要素において実行できることは理解されよう。ＡＳＩＣの種々の形態が、多数の製造業者から利用できるが、現在利用可能なＡＳＩＣは、この特許出願において記述される機能は提供しない。そのような製造業者には、共にカリフォルニアのSanta Claraにある、Intel CorporationとNVIDIA Corporationがある。従来のＡＳＩＣの実際の半導体要素および等価集積回路は、本発明の一部ではないので、ここでは詳細には検討しない。
【００２０】
当業者はまた、ＡＳＩＣまたは他の従来の集積回路または半導体要素が、ここで、より詳細に記述される本発明の教示を使用して、下記に、より詳細に検討される本発明の方法を実行し、図４に示されているように、処理システム１０２内で、シェーディングによる形成化モジュール１５０を実践できるような方法で実践できるということも理解するであろう。下記に記述されるシステムと技術によれば、シェーディングによる形成化モジュール１５０は、下記のサブモジュール、シェーディング情報入力モジュール１５０ａ、モデルジェネレータモジュール１５０ｂ、および表示出力モジュール１５０ｃの１つまたは複数を含むことができる。シェーディングによる形成化モジュール１５０はまた、全体として四角形１５０ｄに「ツール／ＡＰＩ／プラグイン」として示されている、ここで記述される他の構成要素を含むことができる。図４に更に示されているように、シェーディングによる形成化モジュール１５０の出力は、表示可能な画像、デジタル的に更新された幾何学的モデル、細分割曲面など、多数の異なる形式で提供できる。
【００２１】
当業者はまた、本発明の方法形態が、ワークステーションおよびパーソナルコンピュータ（ＰＣ）のような、ワークステーションまたはＰＣオペレーティングシステムおよび本発明に従って構成されたコンピュータプログラム製品のコマンド群のもとで作動する、市場で入手可能なデジタル処理システム内で実行できることも理解されよう。「コンピュータプログラム製品」という用語は、コンピュータ読取可能媒体上でコード化されたコンピュータ読取可能プログラム指令の任意の集合を含むことができる。コンピュータ読取可能媒体は、それに制限されるわけではないが、コンピュータハードディスク、コンピュータフロッピーディスク、コンピュータ読取可能フラッシュドライブ、コンピュータ読取可能ＲＡＭまたはＲＯＭ要素、または、デジタル情報をコード化、格納、または提供する任意の他の既知の手段を、ワークステーション、ＰＣ、または他のデジタル処理装置またはシステムに局在する、またはそれらから離れているかに拘わらずに含む、コンピュータ読取可能要素の任意の形態を含むことができる。コンピュータ読取要素および媒体の種々の形態は、コンピューティング技術においてはよく知られているので、その選択は、実践する者に任される。いずれにせよ、本発明は、コンピュータシステムがピクセル値を計算できるように作動可能であり、このピクセル値は、グラフィックカードまたは表示コントローラのような従来の要素であってよいコンピュータシステム内のハードウェア要素により使用されて、表示制御電子的出力を生成できる。従来のグラフィックカードおよび表示コントローラは、コンピューティング技術においてよく知られており、必ずしも、本発明の一部ではないので、その選択は実践する者に任される。
【００２２】
ＩＩ．ＳＢＳモデラ
図５は、オペレータなどにより、任意の時点におけるその作成の所与の状態における対象物の二次元画像に適用されるシェーディングにより、対象物の三次元モデルを生成する、本発明に従って構築されるコンピュータグラフィックスシステムを示している。図５を参照すると、コンピュータグラフィックスシステムは、プロセッサモジュール２０１と、１つまたは複数のオペレータ入力装置２０２と、１つまたは複数の表示装置２０３を含む。表示装置２０３は、典型的には、フレームバッファ、ビデオ表示端子のようなものを含み、それらは、表示スクリーン上に、情報を、テキストおよび／またはグラフィックの形式でオペレータに表示する。コンピュータグラフィックスシステム２００のオペレータ入力装置２０２は、典型的には、デジタイジングタブレット２０５と連係して典型的に使用されるペン２０４と、トラックボールまたはマウス装置２０６を含む。一般的には、ペン２０４とデジタイジングタブレットは、いくつかのモードにおいてオペレータにより使用される。１つのモードにおいては、本発明との関連において特に有効であるが、ペン２０４とデジタイジングタブレットは、コンピュータグラフィックスシステムへ、更新シェーディング情報を提供するために使用される。他のモードにおいては、ペンとデジタイジングタブレットは、例えば、表面トリミングのための線画のような従来のコンピュータグラフィックス情報、および他の情報をコンピュータグラフィックスシステム２００に入力して、それによりシステム２００が従来のコンピュータグラフィックス操作を行えるようにするために使用される。トラックボールまたはマウス装置２０６は、カーソルまたはポインタをスクリーン上で、オペレータがペンとデジタイジングタブレットにより入力を提供できる画面内の特別な点に移動するために使用できる。コンピュータグラフィックスシステム２００はまた、オペレータがテキスト入力をシステム２００に提供するために使用できるキーボード（図示せず）も含むことができる。
【００２３】
プロセッサモジュール２０１は、一般的には、１つまたは複数のマイクロプロセッサの形状であってよいプロセッサとメインメモリを含み、一般的には、１つまたは複数のディスク格納装置を含む大容量格納サブシステムを含む。メモリおよびディスク格納装置は、一般的には、プロセッサにより処理されるデータとプログラム（まとめて「情報」）を格納し、プロセッサにより生成された処理データを格納する。プロセッサモジュールは、オペレータ入力装置２０２と表示装置２０３への接続を含み、オペレータ入力装置２０２を介してオペレータにより入力された情報を受け取り、入力情報を処理し、処理された情報をメモリおよび／または大容量格納サブシステムに格納する。更に、プロセッサモジュールは、ビデオ表示情報を提供でき、この情報は、オペレータへの表示のための表示装置への、メモリおよびディスク格納装置により生成された処理データと共に、それらから得られる情報の一部を形成できる。プロセッサモジュール２０１はまた、ハードコピー出力の生成を容易にするプリンタのようなハードコピー出力装置、情報の伝達を容易にするための、公衆電話システムへの、および／またはコンピュータネットワークにおいてシステム２００を接続するためのモデムおよび／またはネットワークインタフェース（図示せず）などへの接続（これも図示せず）も含むことができる。
【００２４】
コンピュータグラフィックスシステム２００は、ペンとデジタイジングタブレット、およびマウスを介して、オペレータにより提供された入力から、三次元対象物の初期のそしてその後の形状を定義する情報を生成し、その情報は、オペレータへの表示のための、対応する対象物の二次元画像を生成するために使用でき、それにより、対象物のモデルを生成できる。コンピュータグラフィックスシステム２００により表示される画像は、照明方向から照明され、画像面上に投影される対象物の画像を表現しており、この対象物は、照明方向と画像平面に関する空間位置と回転方向と、オペレータにより選択されたスケーリングおよび／またはズーム設定を有している。モデル生成処理において使用される初期モデルは、半球または楕円形状を定義するモデルのような、コンピュータグラフィックスシステムそれ自身により提供される複数のデフォルトモデルの１つであってよい。または、初期モデルは、ペン２０４とデジタイジングタブレット２０５を使用して、画像平面の少なくとも１つのピクセルの初期シェーディングを提供することによりオペレータにより提供されてもよい。初期モデルがオペレータにより提供されると、画像平面上のピクセルの１つが選択されて、対象物に対する初期表面断片の「基準」部分を提供し、基準初期表面断片部分は、画像平面に関して、選択された空間位置、回転方向、および高さ値を有し、コンピュータグラフィックスシステムは、画像平面上の他のピクセルに適用されたシェーディング（もしあれば）に関連する表面断片（もしあれば）の残りに対する初期モデルを決定する。１つの実施形態において、基準初期表面断片部分は、オペレータがシェーディングを施す画像平面上の第１ピクセルに対する表面断片の部分として選択される。更に、この実施形態においては、基準初期表面断片部分は画像平面に平行になるように決定され、それにより、基準初期表面断片部分に垂直なベクトルは、画像平面に直交し、基準初期表面断片部分は、オペレータにより選択された高さ値を有する。いずれの場合も、コンピュータグラフィックスシステムは、初期モデルの画像を表示し、その画像は、特別な照明方向から照明され、画像平面上に投影される初期モデルに関連する対象物のシェーディングを定義する。
【００２５】
オペレータは、マウスとペンとデジタイジングタブレットを使用して、初期対象物の画像の更新シェーディングを提供し、および／または画像平面上の隣接領域をシェーディングすることにより対象物を拡張し、コンピュータグラフィックスシステム２００は、オペレータにより提供された更新シェーディングに基づいて、対象物の形状を表現する更新モデルを生成する。シェーディングを更新するときに、オペレータは、画像平面上の特別な点に施されるシェーディングの量を増やすまたは減らすことができる。更に、オペレータは、マウスまたはトラックボールとペンとデジタイジングタブレットを使用して、モデルにより定義された対象物の表面表現のトリミングのような、画像と関連する従来のコンピュータグラフィックス操作を行うことができる。コンピュータグラフィックスシステム２００は、オペレータにより提供された更新シェーディングと、他のコンピュータグラフィックス情報を使用して、対象物の形状を定義する更新モデルを生成し、更に、更新モデルから、オペレータへの表示のための二次元画像を、それぞれの空間位置、回転方向、および、オペレータにより選択されたスケーリングおよび／またはズーム設定から生成できる。オペレータが、更新モデルにより表現される対象物の形状が満足できるものと判断したときは、オペレータは、コンピュータグラフィックスシステム２００に、最終対象物の形状を定義する更新モデルを格納させることができる。一方、オペレータが更新モデルにより表現される対象物の形状が満足できないものと判断した場合は、オペレータはコンピュータグラフィックスシステム２００と協働して、必要に応じて、三次元回転、平行移動、およびスケーリングまたはズーミングを使用する処理において、シェーディングと他のコンピュータグラフィックス情報を更に更新できる。シェーディングと他のコンピュータグラフィックス情報が更新されると、コンピュータグラフィックスシステム２００はモデル情報を更新し、その情報は、オペレータにより選択される回転方向、平行移動または空間位置設定、およびスケールおよび／またはズーム設定から、対象物の二次元画像を提供するために再び使用される。これらの操作は、オペレータが対象物の形状が満足なものと判断するまで続けることができ、その時点で、コンピュータグラフィックスシステム２００は、その更新されたモデルを、最終対象物を表現するものとして格納する。
【００２６】
対象物の形状を決定するときにコンピュータグラフィックスシステム２００により実行される詳細な操作は、図６〜図１１と関連して説明する。図６を参照すると、コンピュータグラフィックスシステム２００の操作においては、対象物の画像は、所定数の行と列を有するモザイク状のピクセル２２１（ｉ，ｊ）に形成される二次元画像平面２２０に投影されることを仮定している。画像平面２２０は、行がｘ方向に延伸し、列がｙ方向に延伸しているｘ、ｙデカルト平面を定義する。形成される対象物の表面の投影は、図６においては参照番号２２２により特定されているが、正投影であり、カメラの「目」の方向はｘ、ｙ画像平面に直交するｚ方向である。画像平面上の各点は、ここでは、
2009521062.tif 000005
かつ
2009521062.tif 000006
であって、Ｎが列の最大数（添え字ｉは画像平面内の列の範囲）であり、Ｍが列の最大数（添え字ｊは画像平面内の行の範囲）である
2009521062.tif 000007
により表現される画素、または「ピクセル」に対応している。図６に示されている例としての画像平面２２０においては、列数Ｎは８であり、行数Ｍは９である。画像平面２２０をオペレータに示すために使用される表示装置２０３がラスター走査装置の場合は、行は、画像を表示するために装置により使用される走査線に対応する。各ピクセル
2009521062.tif 000008
は座標系の特別な点（ｘｉ，ｙｊ）に対応し、Ｍ×Ｎは画像の解像度を特定する。更に、コンピュータグラフィックスシステム１０は、対象物が方向
2009521062.tif 000009
、ここで、
2009521062.tif 000010
はベクトルである方向を有する光源により照明され、対象物の表面はランベルト面であることを仮定している。明示されていないカメラは、その画像平面は画像平面２２０により表現されているが、「ＣＡＭＥＲＡ」と記されている矢印により表現されているように、画像平面２２０に直交する方向から画像平面２２０を見ると仮定されている。
【００２７】
上述したように、コンピュータグラフィックスシステム２００は、モデル化される対象物の、少なくとも非常に小さな部分の対象物を、初期モデルとして初期化する。各ピクセル
2009521062.tif 000011
に対して、ピクセル上に投影される対象物の部分の高さを定義する高さ値ｚ（ｘ，ｙ）は既知であり、下記の
【数１】
2009521062.tif 000012
ここで、
2009521062.tif 000013
は、「定義域
2009521062.tif 000014
におけるすべての点（ｘ，ｙ）」を意味し、定義域
2009521062.tif 000015
は画像平面２２０である式のように高さフィールドＨ（ｘ，ｙ）として定義される。更に各ピクセル
2009521062.tif 000016
に対して、その上に投影される基本初期対象物の表面の部分の法線ｎ（ｘ，ｙ）もまた既知であり、下記の
【数２】
2009521062.tif 000017
のような法線フィールドＮ（ｘ，ｙ）として定義される。図６において、画像平面２２０の１つのピクセル上に投影される対象物の表面２２２に関連する法線は、「ｎ」と記されている矢印により表現される。
【００２８】
コンピュータグラフィックスシステム２００が、画像平面２２０上の画像として表示装置２０３上でオペレータに対して表示される、初期モデルにより定義される対象物を表現する画像を表示した後、オペレータは、ペン２０４とデジタイジングタブレット２０５（図５）を使用して、画像のシェーディングを更新することにより、画像の修正を開始できる。コンピュータグラフィックスシステムにより表示される初期モデルの画像はそれ自身が、初期モデルにより定義され、所定の照明方向から照明され、画像平面上に投影される対象物の形状を表現するためにシェーディングされるということは理解されよう。画像平面上の各ピクセル
2009521062.tif 000018
は、ピクセル
2009521062.tif 000019
における画像の相対明度を表現し、逆に、ピクセルの相対シェーディングを表現する関連強度値Ｉ（ｘ，ｙ）（ここでは、「ピクセル値」とも称される）を有する。各ピクセル
2009521062.tif 000020
に対する初期ピクセル値が、画像平面２２０上の位置（ｘ，ｙ）におけるそれぞれのピクセル
2009521062.tif 000021
の画像強度値または明度を表現するＩ０（ｘ，ｙ）により与えられ、シェーディング後のピクセル値がＩ１（ｘ，ｙ）により表現されると、オペレータは、好ましくは、各ピクセル値に対して、
【数３】
2009521062.tif 000022
ここで、∫Ｉ（∫Ｉ＞０）は選択された所定の境界値である式が成り立ち、それにより、式（２．０３）が各ピクセルに対して満たされれば、対象物の形状は、オペレータにより提供されるシェーディングに基づいて更新できるように、画像に対するシェーディングを更新する。
【００２９】
オペレータがピクセルに対するシェーディングを更新した後、コンピュータグラフィックスシステム１０は、対象物に対する更新形状の生成において、２つの一般的操作を行う。特に、コンピュータグラフィックスシステム２００は、
（ｉ）まず、シェーディングが更新された各ピクセル
2009521062.tif 000023
に対して、それぞれの新しい法線ベクトルｎ１（ｘ，ｙ）を決定し、
（ｉｉ）更新法線ベクトルｎ１（ｘ，ｙ）を生成後、新しい高さ値ｚ（ｘ，ｙ）を決定する。
【００３０】
コンピュータグラフィックスシステム１０は、シェーディングが更新されたときに、これらの操作（ｉ）と（ｉｉ）をシェーディングが更新された各ピクセル
2009521062.tif 000024
に対して実行し、それにより、新しい法線ベクトルフィールドＮ（ｘ，ｙ）と高さフィールドＨ（ｘ，ｙ）を提供する。ピクセル
2009521062.tif 000025
に対する法線ベクトルｎ１（上記の（ｉ）の説明）のシェーディングに関連して、コンピュータグラフィックスシステム２００により実行される操作は、図７と図８と関連して説明し、各ピクセル
2009521062.tif 000026
に対する高さ値ｚ（ｘ，ｙ）（上記の（ｉｉ）の項目）の更新に関連して実行される操作は、図９と図１０と関連して説明する。
【００３１】
最初に図７を参照すると、オペレータによりシェーディングが更新された後の、参照番号２３０で特定される対象物の一部が示されている。下記においては、対象物２３０の表面上の点値ｚ（ｘ，ｙ）に対して、記号「ｎ１」で特定されている矢印により特定される更新法線ベクトルが決定されるということを仮定している。記号「ｎ０」で特定される法線ベクトルは、更新前の表面に対する法線を表現している。照明方向は、記号「Ｌ」で特定される矢印に対応するベクトルから延伸している線により表現されている。具体的には、「Ｌ」は、その方向が、対象物を照明する光源からの照明方向に基づき、その大きさは、光源により提供される、対象物上の照明の大きさを表現している照明ベクトルを表現している。その場合、更新に基づいて、可能な新しい法線ベクトルの集合は、
【数４】
2009521062.tif 000027
により定義される円錐２３１の表面上に存在、つまり、照明ベクトルとの点乗積に対するベクトルの集合は、オペレータにより提供されるシェーディングの更新後のピクセルに対するピクセル値「Ｉ」に対応する。更に、法線ベクトルｎ１は、すべての法線ベクトルの場合と同様に、好ましくは値「１」の所定の大きさの値を有するように正規化されているので、更新法線ベクトルは下記の
【数５】
2009521062.tif 000028
ここで、「
2009521062.tif 000029
」は更新法線ベクトルｎ１の大きさを示す式に対応する大きさを有する。
【００３２】
式（２．０４）と式（２．０５）とはベクトルの集合と、それぞれのベクトルの大きさを定義し、その１つは、点ｚ（ｘ，ｙ）における更新された対象物に対する更新法線ベクトルである。コンピュータグラフィックスシステム２００は、適切な更新法線ベクトルｎ１として、ベクトルの集合から１つのベクトルを下記のようにして選択する。上述したように、更新法線ベクトルは、円錐２３１の表面に存在する。元々の法線ベクトルｎ０と照明ベクトルＬが平行でない場合は、それら（つまり、元々の法線ベクトルｎ０と照明ベクトルＬ）は平面を定義するということは明白である。これは、照明ベクトルＬが対象物２３０上に当たる点ｚ（ｘ，ｙ）と、対象物２３０上の法線ベクトルｎ０の原点が同一点であり、照明ベクトルの最後尾と元々の法線ベクトルｎ０先頭部が２つの追加点を提供し、これは、点ｚ（ｘ，ｙ）と共に、平面を定義するには十分であるからである。その結果、参照番号２３２に特定される、照明ベクトルＬと先行法線ベクトルｎ０の両者がその上に存在する平面が構築されると、その平面２３２は、図７において線３３により表現されている、２本の線に沿って円錐と交差する。線２３３の１本は、元々の法線ベクトルｎ０に向かう照明ベクトルＬの側である円錐２３１の表面上に存在し、他方の線２３３は、法線ベクトルｎ０から遠ざかる照明ベクトルＬの側である円錐２３１の表面上に存在し、正確な更新法線ベクトルｎ１は、以前の法線ベクトルｎ０に向かう照明ベクトルＬの側である円錐２３１上の線により定義される。
【００３３】
これらの観察に基づくと、更新法線ベクトルの方向は、式（２．０４）と下記から決定できる。以前の法線ベクトルｎ０と照明ベクトルＬは平面２３２を形成するので、それらのクロス乗積、「ｎ０×Ｌ」は、平面２３２に直交するベクトルを定義する。その結果、更新法線ベクトルｎ１もまた平面２３２内に存在するので、更新法線ベクトルｎ１と、以前の法線ベクトルｎ０と照明ベクトルＬの間のクロス乗積により定義されるベクトルとの点乗積は、値ゼロを有する、つまり、
【数６】
2009521062.tif 000030
となる。
【００３４】
更に、以前のシェーディングと更新シェーディングにより提供されるピクセル値Ｉ０とＩ１の間の差は、∫Ｉ（上記の式（２．０３））により境界を定められ、以前の法線ベクトルｎ０と更新法線ベクトルｎ１の間の角度δもまた、ある最大正値∫δにより境界を定められる。その結果、式（２．０６）は、
【数４】
2009521062.tif 000031
として書き直せる。
【００３５】
これは、図８において図示されている。図８は、図７において示されている円錐２３２の一部と、更新法線ベクトルｎ１と、参照番号２３４により特定される、更新法線ベクトルｎ１がその中に存在することを制約される、以前の法線ベクトルからの最大角∫δを表現する領域を示している。
【００３６】
コンピュータグラフィックスシステム２００（図５）は、オペレータにより提供されるシェーディングに基づいて、画像平面２２０内の各ピクセル
2009521062.tif 000032
に対する更新法線ベクトルｎ１を生成し、それにより、更新ベクトルフィールドＮ（ｘ，ｙ）を生成する。コンピュータグラフィックスシステム２００が、ピクセルに対して更新法線ベクトルを生成した後、そのピクセルに対して新しい高さ値ｚ（ｘ，ｙ）を生成でき、それにより、更新シェーディングに基づいて高さフィールドＨ（ｘ，ｙ）を更新する。高さ値ｚ（ｘ，ｙ）の更新と関連して、コンピュータグラフィックスシステム２００により実行される操作は、図９と図１０と関連して説明する。図９は、図６に示されている画像平面２２０に対する例としての更新シェーディングを示している。図９に示されている画像平面２２０に対して、ピクセル
2009521062.tif 000033
には座標が与えられ、行は、１から８のその両端の数を含む範囲の数により特定され、列は、ＡからＩのその両端の文字を含む範囲の文字により特定される。図９に示されているように、更新シェーディングにおいては、
2009521062.tif 000034
から
2009521062.tif 000035
、
2009521062.tif 000036
から
2009521062.tif 000037
、および
2009521062.tif 000038
から
2009521062.tif 000039
のピクセルはすべて修正されており、コンピュータグラフィックスシステム２００は、更新高さフィールドＨ（ｘ，ｙ）におけるピクセルに対する更新高さ値として、それらに対して更新高さ値ｈ（ｘ，ｙ）を生成することになる。これを達成するために、コンピュータグラフィックスシステム２００は、下記に説明するいくつかの操作を実行して、垂直方向、水平方向、および２つの対角線方向に沿ってシェーディングが修正された各ピクセル
2009521062.tif 000040
に対して高さ値を生成し、４つの高さ値（つまり、垂直、水平、および２つの対角線方向に沿う高さ値）の平均として、ピクセルに対する最終高さ値を生成する。
【００３７】
更新高さ値の生成において、コンピュータグラフィックスシステム２００により実行される操作は、画像平面２２０における修正されたピクセルの１つ、つまり、方向の１つに沿う、つまり水平方向に沿うピクセル
2009521062.tif 000041
との関連において説明する。他の方向との関連において実行される操作と、シェーディングが更新された他のピクセルは、当業者には明白であろう。更新高さ値の生成において、コンピュータグラフィックスシステム２００はBezier-Bernstein内挿を利用し、Bezier-Bernstein内挿は、次元「ｎ」の曲線Ｐ（ｔ）を下記の
【数８】
2009521062.tif 000042
として定義する。ここで、ｔは０と１のその両端を含む区間上の数値パラメータであり、ベクトルＢｉ（成分（ｂｉｘ，ｂｉｙ，ｂｉｚ）により定義される）は、曲線Ｐ（ｔ）に対する「ｎ＋１」個の制御点を定義し、制御点Ｂ０とＢｎは曲線の端点を含む。端点における曲線Ｐ（ｔ）の接線は、ベクトルＢ０Ｂ１とＢｎ−１Ｂｎに対応する。１つの実施形態において、コンピュータグラフィックスシステム２００は、立体Bezier-Bernstein内挿
【数９】
2009521062.tif 000043
を使用して、更新高さ値を生成する。点Ｂ０、Ｂ１、Ｂ２、およびＢ３は立体曲線Ｐｎ＝３（ｔ）に対する制御点である。
【００３８】
ピクセル
2009521062.tif 000044
に対する更新高さ値ｈ１の決定に適用される式（２．０９）は、
【数１０】
2009521062.tif 000045
に対応する。
【００３９】
式（２．１０）から、ｔ＝０に対しては、ピクセル
2009521062.tif 000046
に対する更新高さ値ｈ１は、ピクセル
2009521062.tif 000047
に対する高さ値であるｈａに対応し、ｔ＝１に対しては、ピクセル
2009521062.tif 000048
に対する更新高さ値ｈ１は、ピクセル
2009521062.tif 000049
に対する高さ値であるｈｂに対応する。一方、０または１以外の値を有するｔに対しては、更新高さ値ｈ１は、ピクセル
2009521062.tif 000050
と
2009521062.tif 000051
の高さ値ｈａとｈｂと、制御点Ｂ１とＢ２に対する高さ値の関数である。
【００４０】
上述したように、ｎ次曲線Ｐ（ｔ）に対しては、端点Ｂ０とＢ１における接線は、ベクトルＢ０Ｂ１とＢｎ−１Ｂｎに対応する。その結果、図１０に示されている曲線Ｐｎ＝３（ｔ）に対しては、端点Ｂ０と隣接する制御点Ｂ１により定義されるベクトルＢ１Ｂ０は、端点Ｂ０において曲線Ｐｎ＝３（ｔ）に接し、端点Ｂ３と隣接する制御点Ｂ２により定義されるベクトルＢ２Ｂ３は、端点Ｂ３において曲線に接する接線である。従って、ベクトルＢ１Ｂ０はピクセル
2009521062.tif 000052
において法線ベクトルｎａに直交し、ベクトルＢ２Ｂ３は、ピクセル
2009521062.tif 000053
において法線ベクトルｎｂに直交する。その結果、
【数１１】
2009521062.tif 000054
となり、
【数１２】
2009521062.tif 000055
となる。
【００４１】
水平方向（図９参照）における更新高さ値ｈ１の決定に対して、ベクトルの形式である式（２．１０）は、次元「ｘ」と「ｚ」（「ｚ」次元は画像平面に直交している）のそれぞれに対して下記の
【数１３】
2009521062.tif 000056
および
【数１４】
2009521062.tif 000057
ここで、数式（２．１３）と数式（２．１４）とのｘとｚの下付き文字は、数式（２．１０）におけるそれぞれのベクトルに対する、それぞれｘとｚとの成分を示している式を誘導する。式（２．１３）と（２．１４）とに対しては、高さ値のｚ成分の値ｈ１ｚのみが分かっておらず、「ｘ」成分の値ｈ１ｘは、この場合はピクセル
2009521062.tif 000058
である、その高さ値が決定されるピクセルの位置の関数となることは理解されよう。更に、式（２．１２）は、下記の２つの
【数１５】
2009521062.tif 000059
と
【数１６】
2009521062.tif 000060
ここで、式（２．１５）と（２．１６）とにおける下付き文字ｘ、ｙ、およびｚは、式（２．１２）におけるそれぞれのベクトルに対する、それぞれｘ、ｙ、およびｚ成分を示している式を誘導する。
【００４２】
更に、上述したように、曲線Ｐｎ＝３（ｔ）に対して更なる制約があり、特に、更新法線ｎ１は、ピクセル
2009521062.tif 000061
に対応する点において、曲線に対して垂直とならなければならないという制約がある。図１０におけるベクトルＢ０１２Ｂ１２３がピクセル
2009521062.tif 000062
に対応する点において曲線に接するならば、そのｚ成分は更新高さ値に対応する点ｈ１もまたベクトルＢ０１２Ｂ１２３上に存在する。その結果、
【数１７】
2009521062.tif 000063
と
【数１８】
2009521062.tif 000064
となる。図１０に示されている凸型組合せに基づくと、
【数１９】
2009521062.tif 000065
と
【数２０】
2009521062.tif 000066
になり、これは
【数２１】
2009521062.tif 000067
と
【数２２】
2009521062.tif 000068
という結果になる。式（２．１７）と式（２．１９）と式（２．２１）とを組み合わせると、
【数２３】
2009521062.tif 000069
になり、この結果、それぞれのベクトルのｘとｚ成分に対しては、
【数２４】
2009521062.tif 000070
となる。同様に、式（２．１８）と式（２．２０）と式（２．２２）とに対しては、それぞれのベクトルのｘとｚ成分に対して、
【数２５】
2009521062.tif 000071
となる。
【００４３】
８個の式（２．１３）から式（２．１６）、式（２．２４）および式（２．２５）はすべて、それぞれのｘとｚ成分において一次元的であることは理解されよう。式（２．１３）から式（２．１６）、式（２．２４）および式（２．２５）に対しては、６個の未知の値がある、つまり、パラメータｔの値、ベクトルＢ１のｘとｚ成分の値（つまり、ｂ１ｘとｂ１ｚの値）、ベクトルＢ２のｘとｚ成分の値（つまり、ｂ２ｘとｂ２ｚの値）、そして、ピクセル
2009521062.tif 000072
に対する点Ｐｎ＝３（ｔ）へのベクトルｈ１のｚ成分（つまり、ｈ１ｚの値）が未知である。（２．１３）から（２．１６）、（２．２４）および（２．２５）の８個の式は、当業者には明白な方法により、未知の値を決定できる連立方程式に対しては十分である。
【００４４】
コンピュータグラフィックスシステム２００は、上記の操作を水平方向（「ｘ」座標軸に対応）に関連して実行すると共に、垂直および２つの対角線方向のそれぞれに対して、上記の操作に類似する対応する操作を実行して、ピクセル
2009521062.tif 000073
に対する更新高さベクトルｈ１を決定する。４方向すべてに対して更新高さベクトルを決定した後、コンピュータグラフィックスシステム２００は、それらを平均する。更新高さベクトルの平均のｚ成分は、対象物に対する更新モデルの高さ値に対応する。
【００４５】
コンピュータグラフィックスシステム２００により実行される操作は、図１１Ａと図１１Ｂとのフローチャートと関連して説明する。一般的には、オペレータはコンピュータグラフィックスシステムによりモデル化される対象物の画像を頭の中に描いているであろうことは予想される。図１１Ａと図１１Ｂとを参照すると、対象物に対する初期モデルが決定され（ステップ２５０）、コンピュータグラフィックスシステムは、所定の照明方向に基づいて、表示方向が画像平面（図６で示されている基準画像平面２０）に対応するようにして、その二次元画像をオペレータに対して表示する（ステップ２５１）。上述したように、初期モデルは、コンピュータグラフィックスシステムにより提供される半球や楕円のようなデフォルトの形状、またはオペレータにより提供される形状を定義できる。いずれの場合も、形状は、初期法線ベクトルフィールドＮ（ｘ、ｙ）と高さフィールドＨ（ｘ、ｙ）を定義して、画像における各ピクセルに対する法線ベクトルと高さ値を定義する。コンピュータグラフィックスシステム２００が初期モデルを表示した後、オペレータは、本発明に関連するシェーディングモードを含む複数の操作モードの１つを、消去およびトリミングのような複数の従来のコンピュータグラフィックスモードの１つ共に選択できる（ステップ２５２）。オペレータがシェーディングモードを選択した場合は、オペレータは、例えば、システムのペンおよびデジタイジングタブレットにより二次元画像のシェーディングを更新する（ステップ２５３）。オペレータがステップ２５３で画像にシェーディングを適用している間、コンピュータグラフィックスシステム２００はそのシェーディングをオペレータに表示できる。オペレータにより適用されるシェーディングは、好ましくは、所定の照明方向から照明され、コンピュータグラフィックスシステム２００により表示される画像平面上に投影される最終対象物のシェーディングの表現である。
【００４６】
オペレータがステップ２５３においてピクセルに対するシェーディングを更新すると、コンピュータグラフィックスシステム２００は、対象物のモデルに対する更新を生成する。更新モデルの生成において、コンピュータグラフィックスシステム２００はまず、図７と８に関連して上記したように、画像内の各ピクセルに対して更新法線ベクトルを決定し、それにより、対象物に対する更新法線ベクトルフィールドを提供する（ステップ２５４）。その後、コンピュータグラフィックスシステム２００は、画像内の各ピクセルに対して、図９と図１０とに関連して上記したように、更新高さ値を決定し、それにより、対象物に対する更新高さフィールドを提供する（ステップ２５５）。
【００４７】
更新法線ベクトルフィールドと更新高さフィールドを生成して、対象物の更新モデルを提供した後、コンピュータグラフィックスシステム２００は、オペレータにより選択された（ステップ２５７）、画像の回転、平行移動、およびスケーリングおよび／またはズーミングの処理において、オペレータにより選択されたように（ステップ２５６）、更新モデルの画像を、１つまたは複数の方向およびズームでオペレータに対して表示する。オペレータが更新モデルは満足できるものと判断した場合（ステップ２５８）、これは、例えば、更新モデルが、オペレータが頭に描いていた、モデル化される対象物の画像と一致した場合であるが、オペレータは、更新モデルを対象物の最終モデルとしてコンピュータグラフィックスシステム２００に保存させることができる（ステップ２５９）。一方、オペレータがステップ２５７で、更新モデルが満足できるものではないと判断した場合は、オペレータはコンピュータグラフィックスシステム２００をステップ２５１に戻すことができる。
【００４８】
ステップ２５２に戻って、オペレータがそのステップで、消去モードまたはトリミングモードのような従来の操作モードのような別の操作モードを選択した場合は、コンピュータグラフィックスシステムは、オペレータによりコンピュータグラフィックスシステム２００に提供された消去情報またはトリミングおよび他の従来のコンピュータグラフィック情報に基づいてモデルを更新するためにステップ２６０までの一連のステップを行う。コンピュータグラフィックスシステムは、ステップ２５７までの一連のステップを行って、更新モデルに基づく対象物の画像を表示する。オペレータが、更新モデルが満足できるものと判断した場合（ステップ１０８）は、オペレータは、更新モデルを、対象物の最終モデルとしてコンピュータグラフィックスシステム２００に保存させることができる（ステップ２５９）。一方、オペレータがステップ２５７で更新モデルが満足できるものではないと判断した場合は、オペレータはコンピュータグラフィックスシステム２００をステップ２５１に戻すことができる。
【００４９】
オペレータは、対象物の画像のシェーディングを更新するとき（ステップ２５３）、または他のコンピュータグラフィック情報を提供するとき（ステップ２６０）に、コンピュータグラフィックスシステム２００にステップ２５１、２５３から２５７、および２６０を実行させることができ、コンピュータグラフィックスシステム２００は、ステップ２５４と２５５において、更新法線ベクトルフィールドおよび更新高さフィールドを、またはステップ２６０において従来のコンピュータグラフィック成分を生成し、それにより、対象物の更新モデルを定義する。オペレータがステップ２５８で更新モデルが、オペレータが頭に描いていた対象物の画像に対応すると判断した場合、または満足できるものと判断した場合は、オペレータは、コンピュータグラフィックスシステム２００に、更新法線ベクトルフィールドと更新高さフィールドを格納させ、対象物の最終モデルを定義させることができる（ステップ２５９）。
【００５０】
本発明は、多数の利点を提供する。特に、本発明は、会話型コンピュータグラフィックスシステムを提供し、それにより、アーティストのようなオペレータは、対象物の所望の形状を想像でき、対象物に対するシェーディングが、特別な照明方向から照明され、特別な視覚方向（画像平面の位置により定義される方向）から見たときの対象物においてどのように現れるかを想像できる。オペレータが所望の形状に対応するあるシェーディング入力を提供した後、コンピュータグラフィックスシステムは対象物のモデルを、シェーディングに基づいて更新されたようにオペレータに表示する。オペレータはモデルを最終対象物として容認でき、またはシェーディングを更に更新でき、それによりコンピュータグラフィックスシステムは対象物のモデルを更に更新する。本発明に従って構築されたコンピュータグラフィックスシステムは、シェーディングからの形成化方法に従って作動する従来技術のシステムにおいては必要であった偏微分方程式を解く必要を回避する。
【００５１】
本発明の更なる利点は、生成される対象物のモデルに対する階層的な表現の使用を容易にするということである。その結果、例えば、オペレータがコンピュータグラフィックスシステム２００に、対象物のスケールを拡大、または対象物をズームインし、それにより、より高い解像度を提供させると、画像の複数のピクセルは、より低い解像度では単一のピクセルと関連付けられていた画像の部分を表示するようになるということは理解されよう。この場合、オペレータがより高い解像度の画像のシェーディングを更新すると、コンピュータグラフィックスシステムは、上記のようにシェーディングが更新される、より高い解像度の各ピクセルに対する法線ベクトルと高さ値を生成し、それにより、高められた解像度における更新シェーディングに関連するモデルの部分を生成および／または更新する。より高い解像度のモデルの更新部分は、より低い解像度で以前に定義されていたモデルの特別な部分に関連付けられ、それにより、格納できる階層的表現を提供する。その結果、モデルにより定義された対象物は、基盤となる表面の表現における、より高い解像度に対応する詳細レベルを継承することになる。対応する操作は、オペレータがコンピュータグラフィックスシステム２００に対象物のスケールを減少または対象物をズームアウトし、それにより、より低い解像度を提供できるようにすれば実行することができる。
【００５２】
図５〜図１１に関連して上記したように、多数の変形および修正をコンピュータグラフィックスシステム２００に行うことができるということは理解されよう。例えば、コンピュータグラフィックスシステム２００は、対象物のモデル情報、つまり、法線ベクトルフィールド情報および高さフィールド情報を、オペレータにより提供されたシェーディングの多数の更新に対して保持でき、それ（つまりシステム２００）は、それぞれの更新に対して対象物のモデルを表示するために使用できる。これにより、オペレータは、例えば、それぞれの更新を通しての対象物の進展を見ることができるようにするために、それぞれのモデルの画像を見ることができる。更に、これにより、オペレータは、更新対象であったベースとして、以前の更新からのモデルに戻ることができる。これにより、オペレータは、例えば、特別なモデルにおける異なるシェーディングに基づく対象物のツリーを生成できる。
【００５３】
更に、コンピュータグラフィックスシステム１０は、Bezier-Bernstein内挿を利用して更新高さフィールドｈ（ｘ、ｙ）を決定するように説明したが、例えば、テイラー（Taylor）多項式およびＢスプラインのような内挿の他の形式もまた使用できるということは理解されよう。更に、表面表現の複数の形式を本発明で使用できる。実際、コンピュータグラフィックスシステム２００により使用されるモデル生成方法は、一般的な適用であるので、すべての自由な形式の表面表現が、例えば、三角形、四角形、および／または五角形から構成される区分的線形表面と共に使用できる。
【００５４】
更に、コンピュータグラフィックスシステム２００は、正投影と単一光源を利用するとして説明したが、透視投影を含む他の形式の投影および複数の光源を使用できるということは理解されよう。
【００５５】
更に、コンピュータグラフィックスシステム２００は、対象物の形状を、対象物の画像のシェーディングにより提供すると説明したが、それはまた、ペン２０４とデジタイジングタブレットの適切な操作モードを介して、トリミングや消去のようなコンピュータグラフィックス操作も提供できるということは理解されよう。
【００５６】
更に、コンピュータグラフィックスシステムは、対象物のモデルを、対象物の表面はランベルト面であることを仮定して生成すると説明したが、対象物の画像のレンダリングを行うときに、対象物に対して他の表面処理も使用できるということは理解されよう。
【００５７】
本発明によるシステムは、その如何なる部分も適切なプログラムで制御できる特別用途のハードウェアまたは汎用コンピュータシステム、またはその任意の組合せからその全体を、または一部を構築できるということは理解されよう。如何なるプログラムも、その全体または部分的に、従来の方法でシステムの一部を含むことができ、またはシステム上に格納でき、またはネットワークを介して、または他の従来の方法で情報を伝達する機構を介して、システムにその全体、または一部を提供できる。更に、システムは、システムに直接接続できる、またはネットワークを介して、または従来の方法で情報を伝達できる機構を介して情報を伝達できるオペレータ入力要素（図示せず）を使用してオペレータにより提供された情報により操作でき、および／または制御できるということは理解されよう。
【００５８】
ＩＩＩ．ＳＢＳモデラの改善
３．１  序章
上記のシステムと技術は、大きな発展を遂げた。３．２節ではＳＢＳシェーディングと整形処理の簡潔な要約を説明する。３．３節から３．７節では、ＳＢＳシェーディングと整形処理に対する具体的な拡張と他の改善を説明する。
【００５９】
３．２  ＳＢＳシェーディングおよび整形処理
図１２は、ＳＢＳシェーディングと整形サイクル３００を示すフロー図を示している。
【００６０】
ステップ３０１：階層的細分割曲面と、ポリゴンメッシュと、非一様有理Ｂスプライン（ＮＵＲＢＳ）曲面がシェーディングによる形成化（ＳＢＳ）への入力表面としてサポートされる。ＳＢＳの内部アルゴリズムは、階層的細分割曲面の特性を使用し、そのため、後者の２つのタイプのそれぞれは、シェーディングが始まる前に細分割曲面に変換される。
【００６１】
ステップ３０２：細分割曲面がいったん定位置に置かれ、ユーザーに表示されると、それは、格子の隅、格子の幅および高さ、ピクセルサイズ、およびカメラから対象物への変換についての情報を含む２Ｄモデルビューと整合される。
【００６２】
ステップ３０３〜ステップ３０５：２Ｄモデルビューを使用して、ユーザーは照明方向を設定し、入力パラメータを調整し、シェーディングを行う、つまり、選択されたピクセルの強度を修正、または前以てシェーディングされたピクセルの集合をロードする。この情報は、整形アルゴリズム３０６に渡される。
【００６３】
ステップ３０６〜ステップ３０９：整形アルゴリズム３０６は、表面に対して行う正確な幾何学的変更を決定する。必要であれば、より多くの表面基本形が、十分な詳細が存在していることを確実にするために、シェーディングの領域における細分割を介して追加される（ステップ３０７）。２Ｄ設定で要求された変更を３Ｄで反映する高さフィールドが求められ（ステップ３０８）、細分割曲面は、それがこれらの高さを反映するように変更される（ステップ３０９）。
【００６４】
結果は、更に変形でき（ステップ３０２〜ステップ３０９）、格納でき（ステップ３１０）、または所望の出力表面タイプに変換できる整形階層的細分割曲面となる。
【００６５】
３．３  表面処理の改善
上記のＩＩ節で説明したＳＢＳシステムおよび技術は、ＮＵＲＢＳ曲面の処理用に設計されている。ここで説明されるシステムと技術は、任意の階層的細分割曲面、ポリゴンメッシュ、またはＮＵＲＢＳ曲面を容認するためにＳＢＳを拡張する。入射メッシュは、まだそれが階層的細分割曲面でない場合は、階層的細分割曲面に変換され、結果としての細分割曲面は、それに対しＳＢＳシェーディングと整形サイクルが実行されるものとなる。適合細分割を使用して、曲面へ詳細を追加し、分析と合成を使用して、その変化を曲面のすべてのレベルに伝達し、詳細の指定されたレベルでの修正を可能にする。method images（登録商標）の階層的細分割曲面（ＨＳＤＳ）ライブラリは、必要なすべての細分割サポートを提供する。ＨＳＤＳライブラリの特徴は、本発明特許出願の所有者により所有されている特許に記載されている。ＳＢＳ処理に起因する細分割曲面モデルは、所望するのであれば別の表面タイプに変換できる。このようにして、ＳＢＳは、入射および出射メッシュタイプの両者の選択における柔軟性を可能にし、そのアルゴリズムにおいて階層的細分割特性を利用する。
【００６６】
３．４  追加的整形アルゴリズム
連続であると仮定されている関心対象の表面は、ビューイング平面上に正投影される。この投影は、関連する高さフィールドを有し、その強度は、ランベルト反射マップを有する１つの光源により決定され、それにより、高さフィールドＨを有する所与の表面のモデルビューにおける点（ｕ，ｖ）における離散強度Ｉは下記の
【数２６】
2009521062.tif 000074
ここで、ＮＨは表面に対する離散法線であり、λは、無限に遠くにある光源の方向を指し示す単位ベクトルである式により定義される。
【００６７】
投影表面上の選択されたピクセルの強度は、シェーディングまたは前以て定義されたピクセルの集合をロードすることにより変更される。ＳＢＳ整形アルゴリズムは、シェーディングにより決定された形状を求める。１つの解決法には、Bezier-Bernstein多項式が含まれる。モデルビューにおける２Ｄシェーディングを、表面上の３Ｄ形状として解釈するための新しい技術が、ここでＳＢＳにおいて実践され、この節の残りの部分で説明される。
【００６８】
ここで記載される技術は、下記の
【数２７】
2009521062.tif 000075
ここで、ＣＨは関連する高さフィールドＨを有する曲面の曲率を示し、λは平滑係数と称される定数で、合計は、投影曲面の内部と交差するモデルビュー内のピクセルに渡り実行される式を最小化する、モデルビュー全体にわたる高さ増分Γの集合を生成する。
【００６９】
Ｐを、強度を修正されたモデルビューにおけるピクセルの集合とする。この集合は、修正ピクセルの集合と称される。一連の簡略化により、関数（３．０２）を、
【数２８】
2009521062.tif 000076
とまとめられるピクセルに縮小できる。更に、高さ増分Γの集合を、各ピクセルに対して１つの入力を含むベクトルｘ、または対応する高さ値がアルゴリズムにより変更できる接続領域に縮小できる。Γのサイズは、投影曲面の高さフィールドのサイズに整合する。ベクトルｘは、潜在的にはるかに小さい集合である、Γにおける固有非ゼロ高さ増分の数に基づいてサイズを縮小する。そして、関数（３．０２）は、
【数２９】
2009521062.tif 000077
の非制約最小化に縮小できる。
【００７０】
縮小された関数は、最小化するための計算上の負荷がより少ないが、これは、モデルビューにおけるすべてのピクセルの代わりに、修正されたピクセルの近傍で合計を求めるだけでよいことと、最小化問題の規模は、Γのサイズからｘの長さに縮小されることの両者の理由による。
【００７１】
関数（３．０３）を最小化するために使用される方法は、信頼領域法である。まず、関数は、下記の
【数３０】
2009521062.tif 000078
ここで、
2009521062.tif 000079
はｆの勾配ベクトルであり、
2009521062.tif 000080
はｆのヘッシアン行列である二次関数によりモデル化される。そして、モデルＦは、ある
2009521062.tif 000081
に対して、
2009521062.tif 000082
である領域において最小化される。最小化を行うために使用される方法は、特殊疎行列乗算を有するCG-Steihaug法である。テスト値は、結果としての最小点ｘ１から構築され、
【数３１】
2009521062.tif 000083
である。
【００７２】
ρが１に近ければ、Ｆは信頼領域内で、ｆに対する良好なモデルであると考えられる。信頼領域の中心は、ｘ１に移動され、信頼領域の半径は増大する。ρが１から離れていれば、信頼領域の半径は減少する。この処理は繰り返され、つまり、新しい信頼領域におけるＦに対して最小値が求められる。処理を停止する基準は、現在の信頼領域の中心において、
2009521062.tif 000084
が十分に小さい、つまり、ｆの極小値が達成されたかどうかということである。この方法は収束することが証明できる。
【００７３】
３．５  ＳＢＳ  Ｃ＋＋  ＡＰＩ
Ｃ＋＋アプリケーションプログラミングインタフェース（ＡＰＩ）は、最近、ＳＢＳに対して開発されてきた。Ｃ＋＋  ＡＰＩは上記のmental matter（登録商標）ライブラリ上で機能し、連結時にlibmentalmatter.libを要求する。mental matterライブラリは、ＳＢＳライブラリの内部で開始され、終了する。
【００７４】
３つの主要ＳＢＳクラス
miSbs_surface
miSbs_ogl_view
miSbs_solver
がある。これらのクラスへのアクセスと作成方法は、miSbs_moduleより提供される。
【００７５】
miSbs_moduleの初期化は無条件であり、最初にクラスにアクセスするときに行われる。miSbs_moduleのインスタンスはその静的メソッドgetにより返される。terminateメソッドはライブラリをアンロードするときに呼び出さなければならない。ＳＢＳは、create_surfaceメソッドを介して、miSbs_surfaceオブジェクトにラップされているmental matterライブラリのmiCapi_cl_subsurfクラスからのオブジェクトを使用する。プラグインライタは、ＳＢＳ  ＡＰＩにmiCapi_cl_subsurfのインスタンス、またはmiGeoBoxの形式のモザイク状のメッシュを提供する。別の可能性は、表面を提供しないことであり、その場合は、ライブラリは、空の細分割曲面を保持するラッパーを作成する。miSbs_moduleクラスにおける他のメソッドは、creat_viewerとget_solverを含む。
【００７６】
miSbs_surfaceクラスは、miSbs_solverへのコールにおいて、ＳＢＳ整形アルゴリズムへのアクセス、およびmiSbs_ogl_viewにおいて、表示および相互作用のために使用される。miSbs_surface実装は、miSbs_moduleのcreate_surfaceメソッドを使用してインスタンス化され、destroyメソッドにより破壊される。miSbs_surfaceクラスの他のメソッドは、get_subsurfと、get_depthと、convert（メッシュ指標をsurf指標へ、またはsurf指標から変換する）を含む。他の関連するクラスは、積分の速度を速めるために提供される。例えば、miSbsMax_meshは、3ds max（登録商標）メッシュを、miSbs_surfaceオブジェクトに、およびmiSbs_surfaceオブジェクトから変換する技術的詳細を隠す。
【００７７】
miSbs_ogl_viewクラスは、miSbs_surfaceのインスタンスを表示するために使用される。miSbs_ogl_view実装は、miSbs_moduleのcreate_viewerメソッドを使用してインスタンス化され、destroyメソッドにより破壊される。miSbs_ogl_viewエンティティは、所与のmiSbs_surfaceインスタンスへのリファレンスを維持していない。そのメッシュ表現（おそらく簡略化された）と、OpenGL（登録商標） contexts and triangle strip buffersのような補助データに関連するデータを保持するのみである。miSbs_ogl_viewクラスのメソッドは、set_settingsとupdateを、メッシュ頂点と面の２Ｄ投影の周りのメソッドの集合と共に含む。これらは、get_face_in_pixel、get_vtxs_in_face、get_vtx_pixels、get_2d_distance_from_vtx、get_face_color、set_face_color、reset_face_colors、set_pixel_buffer、get_pixels_noとcopy_pixel_bufferを含む。追加的helperクラスmiSbs-wind32_viewportは、既存のウィンドウ上でフックアップされるように提供される。それは、基本リフレッシュおよびメッセージ取扱い機能を提供する。
【００７８】
miSbs_solverと称される第３クラスは、ＡＰＩ内で呈示されてＳＢＳ操作を実行する。それは、静的、無状態インスタンスとして実践され、miSbs_moduleのget_solverメソッドを介してアクセスされる。そのメソッドは、get_default_settingsと、udpdate（２Ｄシェーディングから３Ｄ形状を決定する主要アルゴリズム）と、cancelを含む。
【００７９】
３．６  プロトタイプ：3ds max（登録商標）用ＳＢＳプラグイン
ＳＢＳは、Autodesk（登録商標）/discreet（登録商標）からの3ds max（登録商標）に対するモディファイヤとして最近、実装された。モディファイヤにより、アーティストは、単純なブラシにより3ds maxビューポイント上で直接２ＤにおいてシェーディングすることによりＳＢＳモデル化を実行できる。ＳＢＳモデル化ライブラリのすべての機能は、プラグインにおいて入手可能である。図１３は、3ds maxにおけるSBS Modifierのスクリーンショット３５０を示している。
【００８０】
プラグイン機能は、
基本２Ｄペイントパッケージとシェーディングをロードおよび保存する機能を有するシェーディングツールと、
光制御と、
シェーディング情報と、光方向と、入力パラメータに基づく表面形状の更新と、
モディファイヤの内部のアンドゥ／リドゥと、
更新（マスキング）する領域を選択するツールと、
標準細分割曲面操作機能を有する選択ツールを含む。
【００８１】
３．７  ＳＢＳの拡張
上記のシステムと技術は、多数の方法で補強できると考えられる。例えば、これらのシステムと技術は、下記を含むように修正できる。
【００８２】
Mesh-Based SBS：最初に、細分割曲面の特性に変換、および／または細分割曲面の特性を使用することなく、ＳＢＳ処理をポリゴンメッシュ上で行う機能。
【００８３】
Real-Time Mesh Display：会話形式で、大きく、複雑なメッシュを表示する機能。他の修正には、ビュー依存簡略化およびカスタムメッシュ操作を含むことができる。
【００８４】
Trimming：表面全体を任意にトリミングする機能。
【００８５】
Creasing：表面全体に任意にしわを付ける機能。
【００８６】
Shape from Contour Lines：ＳＢＳモデル化処理を完成するためのツールとしての、輪郭線を描いて、初期３Ｄ形状を作成する機能。
【００８７】
NURBS-Based SBS：ＳＢＳ処理を、非一様有理Ｂスプライン（ＮＵＲＢＳ）上で起動する機能。
【００８８】
ＩＶ．ＳＢＳモデラ内で実装される整形方法およびアルゴリズム
４．１  序章
シェーディングによる形成化（ＳＢＳ）処理の目標は、二次元（２Ｄ）シェーディングを、三次元（３Ｄ）形状として解釈することである。ここでは、これを達成するための多数の技術とシステムが説明される。ここでの説明の目的のために、グレースケールシェーディングがビューイング平面上への、表面の投影に対して既に行われていることと、基盤となる表面は連続であることと、投影表面のグレースケール強度は、数学的に記載できることが仮定されている。Ｈは、ビューイングウィンドウ内で見ることができる表面の一部と関連する、カメラ空間内の高さ値を表わし、
2009521062.tif 000085
は、表面に与えられた照明条件λ表わし、ＣＨは、曲面の曲率を表わすとする。ＳＢＳシェーディングアルゴリズムは、高さ値Ｈに加算され、下記の
【数３２】
2009521062.tif 000086
ここで、λは平滑化係数と称される正の定数で、積分は、ビューイングウィンドウ内の投影表面の領域全体にわたり行われる関数を最小化する増分Γを求めようとする。理想的な結果は、強度がシェーディングの強度と整合する、λにより決定された平滑性を有する表面高さの新しい集合である。２Ｄシェーディングは、３Ｄ修正という結果になる。
【００８９】
ＳＢＳ処理は、効率的で、基盤となる表面の連続性を乱さないような方法で行わなければない。理論的設定から計算上の設定へ移行するためには、次節で検討するディスクレタイズ(discretize)が必要となる。
【００９０】
４．２  ラスタライゼーション
ＳＢＳに対する解を求めるためには、問題は、適宜に説明され、離散計算のためにラスター化されなければならない。
【００９１】
４．２．１  モデルビュー
ビューイングウィンドウは、整数値座標（ｕ，ｖ）と、対応するカメラ空間座標（ｘ，ｙ）を有するピクセルの直交格子Ｍとしてラスター化される。このラスター化されたものは、「モデルビュー」と称される。
【００９２】
ラスターピクセルの近傍
2009521062.tif 000087
は、ピクセルそれ自身を含み、｜ｕ０−ｕ｜≦１と｜ｖ０−ｖ｜≦１となるようなすべてのピクセル
2009521062.tif 000088
として定義される。ピクセルの集合Ａの近傍は、nbhd（Ａ）として表わされる。ピクセルは、ピクセルがＡのメンバーであれば集合Ａの境界上にあると定義されるが、その隣の１つまたは２つ以上はＡ内にない。Ａの境界は、∂Ａと表わされる。Ａの内部は、
2009521062.tif 000089
と定義され、符号「＼」は、集合の減算を表わす。モデルビューの内部のピクセルは、９個のピクセルを含む近傍を有している。
【００９３】
４．２．２  表面の投影
ＳＢＳアルゴリズムは、ビューイング平面上への、表面の正投影を仮定している。Ｓは、投影表面と交差するモデルビュー内のピクセルの集合を表わしている。表面の高さフィールドは、Ｈで表わされるが、Ｓ内のピクセル上で定義され、カメラ空間における表面の高さを含む。Ｈ（ｕ，ｖ）は、モデルビュー内のピクセル（ｕ，ｖ）において見ることができる表面の部分の浮動小数点高さである。
【００９４】
４．２．３  第１導関数
モデルビュー内のラスター点は、それらの垂直方向および水平方向距離が等しくなるように、つまり、モデルビューピクセルは正方形で、同じサイズとなるように配置されていると仮定されている。しかし、ここで説明しているシステムと技術は、非正方形ピクセルに関しても実装できるということに留意されたい。非正方形ピクセルは、例えば、ＳＢＳのメッシュに基づく実装において使用できる。その場合、投影基本形頂角は、ピクセルの定義に使用できる。
【００９５】
∫をカメラ空間における、近傍ラスター点間の浮動小数点幅（高さ）とする。高さフィールドＨを有する表面のｕ方向における離散第１導関数は、関心対象の点に跨る２個のピクセルにわたる単純な勾配公式に基づき、
【数３３】
2009521062.tif 000090
と定義される。
【００９６】
同様に、ｖ方向における離散第１導関数は、
【数３４】
2009521062.tif 000091
と定義される。
【００９７】
４．２．４  表面法線
高さフィールドＨを有する表面に対する離散法線は、
【数３５】
2009521062.tif 000092
と定義され、表面接ベクトル＜１、０、Ｄ１Ｈ（ｕ，ｖ）＞と＜０、１、Ｄ２Ｈ（ｕ，ｖ）＞とのクロス積である。
【００９８】
４．２．５  照明条件と強度
ＳＢＳにおいては、照明条件は、１つの光源によるランベルト面であると仮定されている。しかし、別の照明モデルを使用すること、および／または複数の照明源を使用することも可能である。光源は、光の方向を指し示す単位ベクトルλにより記載され、無限に遠くにある。高さフィールドＨを有する所与の表面の離散強度Ｉと光ベクトルλは、
【数３６】
2009521062.tif 000093
で定義される。
【００９９】
この数式は、０．０（黒）と１．０（白）の間のスカラー値を生成し、光源に面している表面の領域は、面していない部分よりも明るいことを暗に意味している。
【０１００】
４．２．６  第２導関数
高さフィールドＨを有する表面の離散第２導関数は、代替の数式
【数３７】
2009521062.tif 000094
と、
【数３８】
2009521062.tif 000095
を、ｕおよびｖ方向それぞれにおける離散第１導関数に対して使用することに基づいている。ｕ方向における第２導関数は、
【数３９】
2009521062.tif 000096
と定義される。同様に、
【数４０】
2009521062.tif 000097
と、
【数４１】
2009521062.tif 000098
であり、ここで、
【数４２】
2009521062.tif 000099
である。
【０１０１】
４．２．７  曲率
高さフィールドＨを有する曲面の離散曲率は、非負スカラー
【数４３】
2009521062.tif 000100
として定義される。
【０１０２】
４．２．８  最小化対象の離散関数
関数（４．０１）の打切りバージョンは、離散強度および曲率の定義を使用して作成できる。それらの式は近傍ピクセル値に依存するので、モデルビューの内部と、投影表面の内部の両者にあるピクセルのみが、関心対象領域に含まれていると考えられる。関数（４．０１）の離散バージョンは
【数４４】
2009521062.tif 000101
ここで、λは平滑係数と称される正の定数であり、Γは、投影表面Ｓ上で定義される高さ増分の集合である式として定義される。
2009521062.tif 000102
に対して、Γ（ｕ，ｖ）＝０．０の条件が課せられ、それにより、モデルビュー上へのその投影の境界における、またはモデルビューのエッジにおける表面上のアーティファクトが回避される。
【０１０３】
４．３  最小化される関数の縮小
この節では、関数（４．１０）は、
2009521062.tif 000103
におけるすべてのピクセルではなく、ユーザーにより強度が修正されたピクセルの近傍におけるピクセルにわたる合計を含むことのみが必要であることが示される。更に、関数の規模は、提案された高さ増分を、よりコンパクトな方法で表現することにより縮小されることが示される。
【０１０４】
４．３．１  修正ピクセル
下記の
【数４５】
2009521062.tif 000104
を、ユーザーが強度を修正したモデルビューにおけるピクセルの集合とする。Ｐは「修正ピクセル」の集合と称され、近傍情報が強度を計算するために必要なので、
【数４６】
2009521062.tif 000105
が仮定されている。
【０１０５】
４．３．２  ビューコード
ビューコードは、計算における縮小の発展を支援する。ビューコードはピクセルを、提案された高さ増分で分類する。パスと接続された集合の表記がビューコードの構築には必要となる。ピクセル（ｕ０，ｖ０）からピクセル（ｕｊ，ｖｊ）へのパスは、ピクセルの任意のシーケンス
【数４７】
2009521062.tif 000106
として定義され、それにより、
【数４８】
2009521062.tif 000107
となる。集合Ａは、
2009521062.tif 000108
ならば集合Ｂの接続成分であり、各
2009521062.tif 000109
に対して、Ａに完全に含まれる（ｕ０，ｖ０）から（ｕ１，ｖ１）のパスがある。ビューコードは、高さ増分ΓはＳ＼Ｐの接続成分上では定数であることを仮定している。表面アーティファクトを回避するために、この定数は、接続成分が、
2009521062.tif 000110
と交差するならば０．０と仮定されている。
【０１０６】
Ｔ＝（Ｔ−１，Ｔ０，Ｔ１，．．．，Ｔｎ−１）を、Ｓ＼Ｐの分割とし、Ｔ−１を、
2009521062.tif 000111
と交差するすべての接続成分の和集合とし、０≦ｉ＜ｎに対するＴｉを、Ｓ＼Ｐの接続成分で、それを適切に含むものがないという意味で最大である接続成分とする。そうすると、増分の集合Γは、多くとも（ｍ＋ｎ）の固有非ゼロ値を、修正ピクセルに対して１つ、各Ｔｉに対して１つ有し、それによりｉ≠−１である。
【０１０７】
「ビューコード」は、
【数４９】
2009521062.tif 000112
と定義される。これは、例えば、０≦Ｖ（ｕ０，ｖ０）＜ｍであれば、（ｕ０，ｖ０）は修正ピクセルであることが分かる。また、Ｖ（ｕ０，ｖ０）＝−１であれば、ピクセルＶ（ｕ０，ｖ０）は２Ｄシェーディング情報の結果として変更されない。これは、ビューコードが割り当てられていないピクセル、つまり、モデルビュー上への表面の投影上にないピクセルについても当てはまる。
【０１０８】
４．３．３  関数ピクセルと計算における第１縮小
表面の断面の高さを、一定量だけ移動させても、その断面の内部の強度または曲率は変化しない。各Ｔｉにおけるピクセルは、一定量だけ移動され、ＴはＳ＼Ｐの分割であるので、
【数５０】
2009521062.tif 000113
が成り立つ可能なピクセルは、
2009521062.tif 000114
に含まれる。下記の
【数５１】
2009521062.tif 000115
ここで、ｑｉはモデルビューにおけるピクセル（ｕｉ，ｖｉ）を表わす式を仮定する。Ｑは「関数ピクセル」の集合と称され、関数（４．１０）は、ここでは、
【数５２】
2009521062.tif 000116
と縮小され、ここでＫは、集合
【数５３】
2009521062.tif 000117
上の
【数５４】
2009521062.tif 000118
の合計であり、定数である。
【０１０９】
４．３．４  増分ベクトルと計算における第２縮小
Γには、最大（ｍ＋ｎ）の固有非ゼロ高さ増分があるので、最小化される関数は、ビューコードにより特定されるように、それらの増分の関数であることのみが必要である。下記の
【数５５】
2009521062.tif 000119
ここで、ｘｉはＶ（ｕ，ｖ）＝ｉとなるような、すべてのピクセルに対するΓの増分値であるとする。ｘは「増分ベクトル」と称される。
【数５６】
2009521062.tif 000120
に対して、
【数５７】
2009521062.tif 000121
とする。すると、関数（４．１０）は、
【数５８】
2009521062.tif 000122
の最小化に縮小される。
【０１１０】
４．３．５  目的関数
関数（４．１３）と関数（４．１６）とは組み合わせて下記の関数を形成することができ、その関数は最小化されるときは、関数（４．１０）の最小化と等価になる。
【数５９】
2009521062.tif 000123
ここで最小化はまた、非制約であってもよい。関数（４．１７）は、整形アルゴリズムにより最小化される離散関数の最終バージョンである。この関数は「目的関数」と称され、その大きさは（ｍ＋ｎ）である。
【０１１１】
４．４  信頼領域ニュートン−ＣＧ法
４．４．１  概要
ＳＢＳは信頼領域ニュートン−ＣＧ法を使用して目的関数（関数（４．１７））を最小化する。信頼領域法の主要な思想は、関数に対して二次式モデルを構成し、「信頼領域」内でモデル関数を最小化して、ある基準に従って信頼領域を調整し、新しい信頼領域内でモデル関数を最小化して、その領域を再び調整、更に再び最小化して、・・・ということである。ある制限が与えられると、そのような方法は、元の関数の極小値に対応する点に収束することが保証される。
【０１１２】
増分ベクトルに集中化された目的関数の信頼領域域モデル
【数６０】
2009521062.tif 000124
は、
【数６１】
2009521062.tif 000125
であり、ここで、
2009521062.tif 000126
は勾配ベクトル
【数６２】
2009521062.tif 000127
であり、
2009521062.tif 000128
はヘッシアン行列
【数６３】
2009521062.tif 000129
である。信頼領域ニュートン−ＣＧという名称における「ニュートン」という名前は、ヘッシアン行列がモデルで使用されるという事実から来ている。他の、普通は正の定符号行列を代わりに使用でき、その場合は、ニュートンは名前から落ちる。ＳＢＳの場合、ヘッシアン行列の使用は便利であり、より弱い収束条件の使用が可能になる。
【０１１３】
2009521062.tif 000130
が十分に小さい場合、つまり、ある収束閾値よりも小さい場合は、極小値オフ（off）がｘ０において起こり、処理は終了したと結論される。そうでない場合は、モデルＦ０は、ある正数Δ０に対する円形信頼領域
2009521062.tif 000131
において、下記に説明するCG-Steihaug法を介して最小化される。ｐ０を、信頼領域においてモデルの最小化が起きた結果としての増分ベクトルとする。
2009521062.tif 000132
が、収束閾値よりも小さい場合は、ｆの極小値がｘ０＋ｐ０で起こり、処理は終了したと結論される。それ以外では、テスト値
【数６４】
2009521062.tif 000133
を計算する。ρ０が閾値を超えると、実際の縮小と予想される縮小は、お互いに若干近くなり、信頼領域の中心は、ｘ１＝ｘ０＋ｐ０に移動される。それ以外では、信頼領域の中心はｘ１＝ｘ０に留まる。ρ０が１に近ければ、Ｆ０は信頼領域内においてｆに対する良好なモデルと考えられ、半径は増大する。ρ０が１から離れれば、信頼領域の半径は減少する。新しい領域の半径はΔ１と表示され、ｘ１に集中化された新しいモデルＦ１が構築され、最小化処理が繰り返される。
2009521062.tif 000134
は０との近さをテストされる。十分に近くない場合は、処理は、
2009521062.tif 000135
が収束閾値以下になるまで再び繰り返される。ｆの極小値は、ｘｉ＋ｐｉにおいて求められる。モデルをどのように計算するか（特に、ｆ、
2009521062.tif 000136
、
2009521062.tif 000137
をどのように求めるか）についての詳細は５節で、CG-Steihaug法に必要な計算は６節で、そして、
2009521062.tif 000138
の収束についての検討は７節で行う。
【０１１４】
４．４．２  擬似コード
図１４は、説明した技術の擬似コードのリストを示している。
【０１１５】
４．５  信頼領域モデルの計算
この節の目標は、信頼領域法に対して使用される二次式モデルである関数（４．１８）の計算を支援するツールを構築することである。特に、ｆ（ｘ）、
2009521062.tif 000139
、および
2009521062.tif 000140
に対する式を求めるために残差が使用される。
【０１１６】
４．５．１  関数、勾配、およびヘッシアンを取得するための残差の使用
2009521062.tif 000141
であることを思い起こして、関数（４．１８）の残差を０≦ｉ＜ｔに対して、
2009521062.tif 000142
のように定義する。関数（４．１８）の残差ベクトルを、次のように第１、第２、第３、および第４種の残差すべての結合と定義する。
【数６５】
2009521062.tif 000143
ここで、残差ベクトルのノルムの平方は、強度と曲率に分解される。
【数６６】
2009521062.tif 000144
その結果、
【数６７】
2009521062.tif 000145
となる。実際、残差は、上記の式が真であるように選択された。ｆの勾配とヘッシアンに対する式もまた残差から導出できる。
【数６８】
2009521062.tif 000146
とすると、
【数６９】
2009521062.tif 000147
となる。その結果、
【数７０】
2009521062.tif 000148
である。同様な導出が、ヘッシアンに対する下記の式という結果になり、
【数７１】
2009521062.tif 000149
ここで、
2009521062.tif 000150
は、以前に定義したように残差勾配ベクトルであり、
2009521062.tif 000151
は残差ヘッシアン、
【数７２】
2009521062.tif 000152
である。簡単な式が下記の
【数７３】
2009521062.tif 000153
と、
【数７４】
2009521062.tif 000154
のそれぞれに対して、残差式を分解し、その導関数を取ることにより導出される。ビューコードは計算を簡略化するために使用される。結果としての式は、これらの２つの値が、既知の値の小さな集合上を除いて０でなければならないことを示している。この情報は、
2009521062.tif 000155
と、
2009521062.tif 000156
とを求め、その結果、ｆ（ｘ）、
2009521062.tif 000157
、および、
2009521062.tif 000158
を求めるために使用できる。その最終的な結果は、信頼領域モデル関数（関数（４．１８））を計算する簡単な方法である。
【０１１７】
４．５．２  第１種の残差
強度に対する式は、第１種の残差を、０≦ｉ＜ｔに対して、
【数７５】
2009521062.tif 000159
と書くことで使用できる。偏微分をするために商法則を使用すると、
【数７６】
2009521062.tif 000160
と、
【数７７】
2009521062.tif 000161
という結果になる。式（４．３１）と式（４．３２）との主要部分は、より処理し易い形式に分解できる。
【数７８】
2009521062.tif 000162
の定義に鎖法則を使用することができ、
【数７９】
2009521062.tif 000163
が得られ、
【数８０】
2009521062.tif 000164
の偏微分を計算することにより、
【数８１】
2009521062.tif 000165
という結果になる。式（４．３３）と式（４．３４）とは、Ｄ１Ｈｘ（ｑｉ）の偏微分とＤ１Ｈｘ（ｑｉ）に対する式を求めることにより更に分解できる。下記の
【数８２】
2009521062.tif 000166
ここで、Ｖはビューコードである式を呼び出す。ｕ方向における離散第１導関数の定義により、下記の
【数８３】
2009521062.tif 000167
ここで、δ１はラスター点（１，０）である式が与えられ、これは、
【数８４】
2009521062.tif 000168
を意味する。同様に、下記の
【数８５】
2009521062.tif 000169
ここで、δ２はラスター点（０，１）である式が与えられる。ビューコードにより、
【数８６】
2009521062.tif 000170
が与えられる。ここで、第１種の残差に対する第１および第２偏微分の式が可能な限り分解されたので、今度は、その微小部分を使用して、鎖を遡って計算する。式（４．３８）を式（４．３６）と式（４．３７）とに代入して、
【数８７】
2009521062.tif 000171
と、
【数８８】
2009521062.tif 000172
とを計算する。そしてこれらを、式（４．３３）と式（４．３４）とに代入して、
【数８９】
2009521062.tif 000173
と、
【数９０】
2009521062.tif 000174
とを計算する。最後に、結果を式（４．３１）と式（４．３２）とに代入して所望するように、
【数９１】
2009521062.tif 000175
と、
【数９２】
2009521062.tif 000176
とを計算する。特に、
【数９３】
2009521062.tif 000177
および、
【数９４】
2009521062.tif 000178
であることに留意されたい。
【０１１８】
４．５．３  第２、第３、および第４種の残差
第２種の残差は、０≦ｉ＜ｔに対して、
【数９５】
2009521062.tif 000179
であり、それにより、
【数９６】
2009521062.tif 000180
が与えられる。上記の計算に対して式（４．３８）を使用して、
【数９７】
2009521062.tif 000181
および、
【数９８】
2009521062.tif 000182
であることに留意されたい。第３種の残差は、０≦ｉ＜ｔに対して、
【数９９】
2009521062.tif 000183
であり、
【数１００】
2009521062.tif 000184
が与えられる。上記の計算に対して式（４．３８）を使用して、
【数１０１】
2009521062.tif 000185
および、
【数１０２】
2009521062.tif 000186
であることに留意されたい。第４種の残差は、０≦ｉ＜ｔに対して、
【数１０３】
2009521062.tif 000187
であり、ここで、
【数１０４】
2009521062.tif 000188
であり、
【数１０５】
2009521062.tif 000189
が与えられる。上記の計算に対して式（４．３８）を使用して、
【数１０６】
2009521062.tif 000190
および、
【数１０７】
2009521062.tif 000191
であることに留意されたい。第１、第２、第３、および第４の残差に対して、つまり、０≦ｉ＜４ｔに対して、
【数１０８】
2009521062.tif 000192
および、
【数１０９】
2009521062.tif 000193
であることに留意されたい。
【０１１９】
４．６  信頼領域モデルの最小化：CG-Steihaug法
４．６．１  概要
信頼領域ニュートン−ＣＧ法における各ステップにおいて、ＳＢＳは、CG-Steihaug法を使用して、信頼領域におけるモデル関数の最小値を求める。共役勾配法は、一次連立方程式Ａｘ＝−ｂ、ここでＡは対称行列である方程式を解こうとする。問題は、下記のように再公式化でき、
【数１１０】
2009521062.tif 000194
これにより問題は、φ（ｘ）の最小化という問題になる。ステップｉにおける、ｆに対する信頼領域モデルＦｉを、
【数１１１】
2009521062.tif 000195
として呼び出す。φ（ｘ）、Ａ、およびｂは、信頼領域法の立場から、下記の
【数１１２】
2009521062.tif 000196
【数１１３】
2009521062.tif 000197
および、
【数１１４】
2009521062.tif 000198
と表現できる。Ａは実際には対称であることに留意されたい。上記の観点から、CG-Steihaug法により最小化される関数は、
【数１１５】
2009521062.tif 000199
であり、ＣＧ法は、共役勾配（ＣＧ）の表記を使用して、φ（ｘ）の最小値に収束するベクトル列を構築する。所与のｉに対して、ベクトル集合
【数１１６】
2009521062.tif 000200
は、すべてのｋ≠１に対して、
【数１１７】
2009521062.tif 000201
ならば、行列Ａに関して共役（ＣＧにおける「Ｃ」）と称される。信頼領域法のステップｉにおいてそのような集合Ｄが与えられると、ｐｉ，ｊ＝０とｊ≧０に対して下記の
【数１１８】
2009521062.tif 000202
ここで、ａｉ，ｊは、
【数１１９】
2009521062.tif 000203
に沿う、φ（ｘ）の一次元最小化因子である数列ｐｉ，ｕを定義する。数列ｐｉ，ｊは、最大（ｍ＋ｎ）（以前のように、（ｍ＋ｎ）が目的関数の大きさの場合）ステップで、所望の最小値ｐｉに収束する。ここでの目標は、どのようにして集合Ｄを構築し、各ｊ≧０に対してａｉ，ｊをどのように求めるかである。
【０１２０】
【数１２０】
2009521062.tif 000204
とする。言い換えれば、最小値を探す第１方向を、最も急峻な降下方向として選択する。これは、勾配（ＣＧにおける「Ｇ」）により決定される方向である。系の残差はｒ（ｘ）＝Ａｘ＋ｂとして定義され、次の探す方向を決定する各ステップにおいて使用される。ｐｉ，０＝０なので、ステップ０における残差は、ｊ≧０に対してｒｉ，０＝ｂであり、
【数１２１】
2009521062.tif 000205
である。ｊ≧０に対して、ｄｉ，ｊ＋１を、
【数１２２】
2009521062.tif 000206
ここで、
【数１２３】
2009521062.tif 000207
であるように定義する。βｉ，ｊ＋１に対するそのような選択は、すべてのｋ＜ｊ＋１に対して、
【数１２４】
2009521062.tif 000208
となるようなｄｉ，ｊ＋１の結果になり、それにより、集合Ｄが各ｊに対して共役であることが保証される。
【０１２１】
最小化因子αｉ，ｊを計算するために、項同士の乗算を行い、αの冪数に従って整理することにより、φｐｉ，ｊ＋αｄｉ，ｊに沿う式を求める。
【数１２５】
2009521062.tif 000209
ここで、Ｋはαに関して定数である。次に、αについての導関数を求める。
【数１２６】
2009521062.tif 000210
上記の量を０に等しいと置いて、臨界点
【数１２７】
2009521062.tif 000211
を求める。臨界点が最小値に対応することを確実にするために、第２導関数を計算して、関数の凹性を求める。
【数１２８】
2009521062.tif 000212
上記の量が正かどうかは分からない。
【数１２９】
2009521062.tif 000213
の場合も後で扱うが、導関数は、
【数１３０】
2009521062.tif 000214
であることを仮定し続けている。αｉ，ｊに対する式は、各ｊ＞０に対して、
【数１３１】
2009521062.tif 000215
という事実を使用して、より良好な方法で書くことができ、ｋ＜ｊのすべてに対しては、帰納法によりある事実が証明される。ｊ＝１に対しては、
【数１３２】
2009521062.tif 000216
である。ここでｋ＜ｊ−１に対して、
【数１３３】
2009521062.tif 000217
を仮定する。すると、ｋ＜ｊ−１に対して、
【数１３４】
2009521062.tif 000218
であり、ここで、帰納法仮説により、
【数１３５】
2009521062.tif 000219
であり、Ｄの共役性により、
【数１３６】
2009521062.tif 000220
である。ここでｋ＝ｊ−１の場合を扱うと、
【数１３７】
2009521062.tif 000221
である。従って、各ｊ＞０に対して、
【数１３８】
2009521062.tif 000222
がｋ＜ｊのすべてに対して成り立つ。ここで、αｉ，ｊに対する新しい式は、
【数１３９】
2009521062.tif 000223
と表わされる。要約すると、CG-SteihaugＳ法は、信頼領域ニュートン−ＣＧ法においてステップｉにおいて使用され、信頼領域において、モデル関数の最小値が起こる点を求める。これを行うために、３つの数列が使用される。それは、ｄｉ，ｊ、ｒｉ，ｊ、およびｐｉ，ｊである。ｄｉ，ｊは、共役勾配方向ベクトルの数列であり、ｒｉ，ｊは残差の数列であり、ｐｉ，ｊは、所望の最小値ｐｉに収束する。ｄｉ，ｊの共役性は、最大（ｍ＋ｎ）ステップでの収束を保証する。
【０１２２】
数列の開始時の量は、ｐｉ，０＝０、ｒｉ，０＝−▽ｆ（ｘｉ）＝ｂ、およびｄｉ，０＝−▽ｆ（ｘｉ）＝ｂである。数列における後続する項は、ヘルパー式
【数１４０】
2009521062.tif 000224
と、
【数１４１】
2009521062.tif 000225
とを使用して与えられ、
【数１４２】
2009521062.tif 000226
【数１４３】
2009521062.tif 000227
および、
【数１４４】
2009521062.tif 000228
である。この時点までは、説明された方法は標準ＣＧ法である。数列ｐｉ，ｊは、残差がある閾値以下になるまで生成される。ＣＧ法のSteihaug変形は、
【数１４５】
2009521062.tif 000229
の場合を考慮しており、これは計算されたαｉ，ｊが最小値に対応するという仮定に反することになり、モデルの最小値は、関心対象、つまり所与の信頼領域の外側で求まる。これらの場合を扱うために、２つの追加的停止基準が追加される。
【数１４６】
2009521062.tif 000230
または、
【数１４７】
2009521062.tif 000231
であるならば、信頼境界と方向ｄｉ，ｊの交差点は、最終点ｐｉとして割り当てられる。ｐｉ，０＝０であるならば、各ｊ＞０に対して、
【数１４８】
2009521062.tif 000232
であり、信頼領域境界との交差点の解を返すことが、境界に到達したときに数列ができる最善のことであることを意味している。そして、信頼領域法は、ｐｉを使用してテスト値を計算する。この結果に依存して、解は十分良好に見えるか、または信頼領域法は、信頼領域ｘｉ＋１の中心が、ｘｉと同じか、ｘｉ＋ｐｉに移動されて、反復ｉ＋１に入るかのいずれかである。
【０１２３】
４．６．２  擬似コード
続く擬似コードにおいて、点の数列ｐｉ，ｊは、ｍｉｎ＿ｐｔと表わされ、方向の数列はｄｉ，ｊは方向により表わされ、残差の数列ｒｉ，ｊは残差により表わされる。「ａドットｂ」はａＴｂを表わすために使用される。
【０１２４】
４．６．３  疎行列乗算
CG-Steihaug法の各反復において、遥かに多くの手間がかかる演算は、Ａの方向ベクトルとの乗算である。目的関数の残差の観点からのＡに対する下記の式を呼び出す。
【数１４９】
2009521062.tif 000233
ここで、各ｉに対して、
【数１５０】
2009521062.tif 000234
とする。（ａｉ）ｊ，ｋをＡｉの（ｊ，ｋ）要素、ｅｉを長さ（ｍ＋ｎ）のベクトルとし、
【数１５１】
2009521062.tif 000235
が成り立つとする。ｄは信頼領域法の固定ステップにおいて、CG-Steihaug法により構築された共役方向ベクトルの１つとする。すると、
【数１５２】
2009521062.tif 000236
となり、（ｊ，ｋ）の各対に対して１回、つまり、（ｍ＋ｎ）２回の乗算を必要とする。しかし計算は、式（４．５３）と式（４．５４）とを使用することにより、より効率的に行うことができる。これらの式は、各ｉに対して、（ａｉ）ｊ，ｋは、ｊとｋが共に、
【数１５３】
2009521062.tif 000237
に含まれるときに限って非ゼロであることを示している。従って、それぞれのｉとｋに対して、
【数１５４】
2009521062.tif 000238
となり、これはＯ（１）乗算において計算できる。従って、全体の規模は、（ｍ＋ｎ）２から（ｍ＋ｎ）に減少される。
【０１２５】
４．７  信頼領域ニュートン−ＣＧ法の収束
信頼領域法により構築された数列ｘｉは、
【数１５５】
2009521062.tif 000239
を、ｉ→∞のとき、下記の条件が成立すれば満たす。
・信頼領域法の各ステップｉにおいて、最小化アルゴリズムにより構築されたｐｉは、ある定数
2009521062.tif 000240
に対して、
【数１５６】
2009521062.tif 000241
を満たす。
・最小化アルゴリズムにより構築された数列ｐｉは、ある定数ｃ２≧１に対して、
【数１５７】
2009521062.tif 000242
を満たす。
・信頼領域の中心を移動する閾値は、区間（０，１／４）に含まれる。
・ｆは、レベル集合
2009521062.tif 000243
、つまり、ある定数
2009521062.tif 000244
に対して、
【数１５８】
2009521062.tif 000245
が、ｆ（ｘ）≦ｆ（ｘ０）となるようにすべてのｘに対して成り立つ集合に対して、下方から境界を区切られる。
・Ｌは、境界を区切られる、つまり、ある定数
2009521062.tif 000246
に対して、
【数１５９】
2009521062.tif 000247
となる。
・すべてのｉ≧０に対して、
【数１６０】
2009521062.tif 000248
となるようなある定数
2009521062.tif 000249
が存在する。
・ｆはＬ上でリプシッツ連続微分可能、つまり、任意の
2009521062.tif 000250
に対して、
【数１６１】
2009521062.tif 000251
となるようなある定数
2009521062.tif 000252
が存在する。上記に主張された条件のそれぞれを下記で証明する。
【０１２６】
４．７．１  モデル推定
ＳＢＳは、CG-Steihaug法をそれぞれのステップｉにおいて使用して、信頼領域におけるモデルＦｉの最小値に対応する点
【数１６２】
2009521062.tif 000253
を求める。ステップｉにおいて、コーシー点（ｐｃ）ｉは、
【数１６３】
2009521062.tif 000254
として定義され、ここで、
【数１６４】
2009521062.tif 000255
が成り立つ。その結果、
【数１６５】
2009521062.tif 000256
となる。CG-Steihaug法により、
【数１６６】
2009521062.tif 000257
が与えられる。その結果、
【数１６７】
2009521062.tif 000258
となる。
【０１２７】
４．７．２  モデル最小値の境界
任意のｊに対して、CG-Steihaugアルゴリズムにより計算されたｐｉ，ｊが信頼領域の外部となる場合は、それは内部のベクトルと置換され、アルゴリズムはその値を返すので、
2009521062.tif 000259
である。
【０１２８】
４．７．３  信頼領域中心移動閾値範囲
閾値に対する範囲を強制して、信頼領域の中心を移動することは、それを適切に設定することである。擬似コードにおいては、移動閾値は、
2009521062.tif 000260
に設定される。
【０１２９】
４．７．４  レベル集合のｆの下方境界
【数１６８】
2009521062.tif 000261
を呼び出す。定義により、各ｑｉに対して、
【数１６９】
2009521062.tif 000262
であり、選択によりλ＞０である。従って、すべての
2009521062.tif 000263
に対してｆ（ｘ）≧０であり、従って、ｘに対してもｆ（ｘ）≦ｆ（ｘ０）となる。
【０１３０】
４．７．５  レベル集合の境界
【数１７０】
2009521062.tif 000264
および、
【数１７０】
2009521062.tif 000265
ここで、δ１＝（１，０）とする。ｈを
【数１７１】
2009521062.tif 000266
で定義し、ｖを
【数１７２】
2009521062.tif 000267
で定義し、すべてのｘに対してｈ（ｘ）≦ｆ（ｘ）であり、従って、
2009521062.tif 000268
となるようなｃ４＞０が存在し、ｔ＞ｃ４が、ｈ（ｔｘ）＞ｆ（ｘ０）を暗示するので、
2009521062.tif 000269
であり、ｔ＞ｃ４がｆ（ｔｘ）＞ｆ（ｘ０）を暗示し、ｆ（ｔｘ）≦ｆ（ｘ０）が、
2009521062.tif 000270
およびｔ≦ｃ４、つまり、所望するように、
2009521062.tif 000271
であることを暗示していることを意味する。
【０１３１】
任意のスカラーｓ＞０と各ｊに対して、
【数１７３】
2009521062.tif 000272
ここで、ｋｊはｓに関しての定数であり、それは、
【数１７４】
2009521062.tif 000273
ここで、ｋはｓに関しての定数である式を暗示する。任意のスカラーｔ＞０に対して、ｈｘ（ｔ）＝ｈ（ｔｘ）とする。すると、
【数１７５】
2009521062.tif 000274
となり、ｈは平方の和であるからｈ≧０である。増分ベクトルｔｘが与えられれば、
【数１７６】
2009521062.tif 000275
がすべてに対して成り立つ場合のみｈ（ｔｘ）＝０となる。これは、増分ベクトルは、投影表面の境界上では０であることが要求されるので、ｔｘがゼロベクトルであることを暗示している。ｕ方向における投影表面を通る任意のピクセル線は、境界上では０でなければならず、
【数１７７】
2009521062.tif 000276
なので、０から変化できない。
2009521062.tif 000277
およびｔ＞０なので、ｈｘ（ｔ）＞０であり、これは、
【数１７８】
2009521062.tif 000278
を暗示している。ここで、
【数１７９】
2009521062.tif 000279
および、
【数１８０】
2009521062.tif 000280
とする。すると、任意のｔ＞ｃ４および
2009521062.tif 000281
に対して、
【数１８１】
2009521062.tif 000282
であり、これは、
【数１８２】
2009521062.tif 000283
を暗示している。
【０１３２】
４．７．６  ヘッシアンの境界
信頼領域ニュートン−ＣＧ法においては、ｘｉ＋1に対して２つの可能性がある。ｘｉ＋1＝ｘｉであって、その場合はｆ（ｘｉ＋1）＝ｆ（ｘｉ）であり、またはｘｉ＋1＝ｘｉ＋ｐｉであり、ここにおいてｐｉはCG-Steihaug法に起因する点である。後者の場合は、モデルテスト値
【数１８３】
2009521062.tif 000284
が信頼領域の中心を移動する閾値よりも大きい場合のみ容認される。閾値は（０，１／４）において選択され、従って、信頼領域の中心が移動されると、ρｉ＞０となる。CG-Steihaug法は信頼領域におけるモデルを最小化するので、
【数１８４】
2009521062.tif 000285
が保証され、それはρｉの分母が非負であることを暗示している。ρｉ≧０ならば、
【数１８５】
2009521062.tif 000286
である。従って、すべてのｉ≧０に対して、
【数１８６】
2009521062.tif 000287
であり、それはＬがすべてのｘｉを含むことを意味している。主張された条件がＬ上で証明されると、それはすべてのｘｉに対しても証明される。ｆとその偏微分のすべては連続である。コンパクト集合［０，ｃ４］（ｃ４は、上記に計算されたＬ上の境界である）上では、ｆとその導関数のすべては境界が区切られている。各ｉとｊ≧０、および＜（ｍ＋ｎ）に対して、
【数１８７】
2009521062.tif 000288
がすべてのｘに対して、
2009521062.tif 000289
となるように成り立ち、従って、
【数１８８】
2009521062.tif 000290
となるような定数ｋｉ，ｊが存在する。
【０１３３】
４．７．７  ｆのリプシッツ連続微分可能性
ｋｉ，ｊを前節と同様にし、
2009521062.tif 000291
とする。ｉを固定して、
【数１８９】
2009521062.tif 000292
【数１９０】
2009521062.tif 000293
および、
【数１９１】
2009521062.tif 000294
とする。すると、
【数１９２】
2009521062.tif 000295
となる。これは、
【数１９３】
2009521062.tif 000296
が各ｉに対してリプシッツ連続であることを示し、それは、
【数１９４】
2009521062.tif 000297
であることを示している。
【０１３４】
４．８  表記
図１６Ａと図１６Ｂとは、参照の利便性のために、本発明の形態によるシステムと技術を記載するために使用される数学的表記の一覧を示している表５００ａと表５００ｂとを記載している。
【０１３５】
Ｖ．一般化された方法のフローチャート
図１７〜図２２は、三次元（３ｄ）対象物の表面の少なくとも一部分の幾何形状を表現する幾何学的モデルを、画像平面上に投影された対象物を表現する、対象物の二次元（２ｄ）画像との関連におけるオペレータによるシェーディングにより生成する、本発明の上記に検討した態様に従う、一般化された方法６００と、補助的方法６２０、６４０、６６０、６８０、および７００を例示する一連のフローチャートを示している。
【０１３６】
図１７に示されている一般化された方法６００は下記のステップを含む。
【０１３７】
ステップ６０１：対象物の画像との関連において、画像の少なくとも一部分の明度レベルにおける変化を表現している、オペレータにより提供されるシェーディング情報を受け取る。
【０１３８】
ステップ６０２：更新幾何学的モデルの少なくとも１つの幾何学的特徴を決定するために使用されるシェーディング情報に応じて、対象物の更新幾何学的モデルを生成する。
【０１３９】
ステップ６０３：更新幾何学的モデルにより定義されたように、対象物の画像を表示する。
【０１４０】
上記で検討したように、一般化された方法６００は、任意の階層的細分割曲面、ポリゴンメッシュ、またはＮＵＲＢＳ曲面のデジタル入力に基づいて作動できる。
【０１４１】
一般化された方法６００は、図１８に示されている補助的方法６２０を含み、補助的方法６２０は、下記のステップを含む。
【０１４２】
ステップ６２１：いったん細分割曲面が生成され、ユーザーに表示されると、細分割曲面を、格子の隅と、格子の幅と高さと、ピクセルサイズと、カメラから対象物への変換についての情報を含む２ｄモデルビューと整合する。
【０１４３】
ステップ６２２：２ｄモデルビューを利用して、照明方向を設定し、入力パラメータとシェードを調整し、それにより、選択されたピクセルの強度を修正するか、または予めシェーディングされたピクセルの集合をロードする。
【０１４４】
この情報は、整形アルゴリズムにより利用される。パラメータは、修正領域においてどの程度の細分割が起きるかに対する影響（ａ）および幾何学的修正がどの程度目立つかに対する影響（ｂ）のいずれかを含むことができる。
【０１４５】
ステップ６２３：表面に対する正確な幾何学的変更を決定し、シェーディングの領域において、細分割を介して、必要であれば表面基本形状を追加して、十分な詳細が存在することを確実にし、３Ｄにおいて、２Ｄ設定において要求された変化を反映する高さフィールドを決定し、細分割曲面を変更して決定された高さ値を反映し、それにより、整形された、階層的細分割曲面という結果になり、この細分割曲面は更に変更、保存、または所望の出力表面タイプに変換できる。表面基本形状は、三角形、四角形、または他の多角形のいずれかを含むことができる。
【０１４６】
一般化された方法６００は、図１９に示されている補助的方法６４０を含み、補助的方法６４０は、下記のステップを含む。
【０１４７】
ステップ６４１：基盤となる細分割曲面を作成する。
【０１４８】
ステップ６４２：２Ｄシェードビューを表示する。
【０１４９】
ステップ６４３：ユーザーが照明、シェーディングを設定し、パラメータを調整できるようにする。
【０１５０】
ステップ６４４：（ａ）詳細を表面上に導入し、（ｂ）表面に対して新しい高さパラメータを決定し、（ｃ）細分割曲面を整形することを含む整形処理を実行して、それにより３Ｄ細分割曲面を生成する。パラメータは、（ａ）修正領域においてどの程度の細分割が起きるかに対する影響および（ｂ）幾何学的修正がどの程度目立つかに対する影響のいずれかを含むことができる。
【０１５１】
一般化された方法６００はまた、図２０に示されている補助的方法６６０を含み、補助的方法６６０は、下記のステップを含む。
【０１５２】
ステップ６６１：メッシュ表現またはＮＵＲＢＳ曲面のいずれかを含む入力を受け取る。
【０１５３】
ステップ６６２：まだ階層的細分割曲面になっていなければ、入力を階層的細分割曲面に変換する。
【０１５４】
ステップ６６３：階層的細分割曲面に対し、シェーディングと整形を実行する。
【０１５５】
ステップ６６４：曲面に詳細を追加するために適合細分割を利用し、変化を曲面のすべてのレベルに伝播するために分析および合成を利用し、それにより、詳細の選択されたレベルでの修正を可能にする。
【０１５６】
ステップ６６５：階層的細分割曲面ライブラリを提供する。
【０１５７】
ステップ６６６：所望するのであれば、ＳＢＳ処理の結果としての細分割曲面モデルを、別の表面タイプに変換する。
【０１５８】
一般化された方法６００はまた、図２１に示されている補助的方法６８０を含み、補助的方法６８０は、下記のステップを含む。
【０１５９】
ステップ６８１：
【数１９５】
2009521062.tif 000298
ここで、Ｉはピクセル（ｕ，ｖ）における離散強度であり、λは、無限に遠くに離れたシミュレートされた光源の方向を指し示す単位ベクトルであり、Ｈは、関連する高さフィールドであり、ＣＨは、高さフィールドＨに関連する曲面の曲率を表わし、λは平滑係数であり、合計は、投影曲面の内部と交差するモデルビューにおけるピクセル上で行われる式により与えられる関数を最小化する、モデルビュー上の高さ増分集合Γを生成するように構成される選択された整形操作を適用する。
【０１６０】
ステップ６８２：関数を、
【数１９６】
2009521062.tif 000299
の非制約最小化に縮小し、ここで最小化を実行するために使用される方法は、信頼領域法である。
【０１６１】
ステップ６８３：投影表面の内部と交差する、モデルビューにおけるすべてのピクセル上の合計から、それを修正ピクセルの近傍と交差させることにより、Ｑと称される縮小された集合上のみでの合計への縮小を実行し、それにより、計算は、モデルビューにおいて見られるように、投影表面全体で行う必要がなくなる。
【０１６２】
一般化された方法６００はまた、図２２に示されている下記の補助的方法７００を含み、補助的方法７００は、下記のステップを含む。
【０１６３】
ステップ７０１：二次関数
【数１９７】
2009521062.tif 000300
ここで、
2009521062.tif 000301
はｆの勾配ベクトルであり、
2009521062.tif 000302
は、ｆのヘッシアン行列である式により関数をモデル化する。
【０１６４】
ステップ７０２：モデルＦを選択された領域で最小化する。この例においては、選択された領域は、ある
2009521062.tif 000303
に対して、
2009521062.tif 000304
である。
【０１６５】
ステップ７０３：特殊疎行列乗算を伴うCG-Steihaug法を利用することにより最小化を実践する。
【０１６６】
ステップ７０４：結果としての最小値点ｘ１から、
【数１９８】
2009521062.tif 000305
であって、ここで、ρが１に近ければ、Ｆは信頼領域内で、ｆに対して良好なモデルと考えられ、信頼領域の中心はｘ１へ移動され、信頼領域の半径は増大し、または、ρが１から遠く離れていれば、信頼領域の半径は減少する式で表わされるテスト値を構築する。
【０１６７】
ステップ７０５：信頼領域において、ｆに対する最小値が、確立された基準に基づいて求められるまで処理を繰り返す。この例においては、処理を停止する基準は、
2009521062.tif 000306
が、ｆの極小値が達成された現在の信頼領域の中心において、十分に小さいかどうかである。
【０１６８】
上述した一般化された方法と補助的方法は、コンピュータ援用設計（ＣＡＤ）システム、コンピュータグラフィックスシステム、または幾何形状を作成、表示、操作、またはモデル化できるソフトウェアアプリケーションのいずれかと相互作動が可能なように適合されたコンピュータソフトウェアプラグイン製品として実装できるということに留意されたい。プラグイン製品の機能は、２ｄ描画機能と、シェーディング、光制御、パラメータ調整、シェーディング情報に基づく表面形状の更新、光方向、および入力パラメータ、アンドゥ／リドゥ機能をモディファイヤの内部にロードおよび保存する機能を有するシェーディングツールと、マスキング技術を利用して、更新する領域を選択するツールと、標準細分割曲面操作の集合を有する選択ツールのいずれかを含むことができ、パラメータは、（ａ）修正領域においてどの程度の細分割が起きるかに対する影響および（ｂ）幾何学的修正がどの程度目立つかに対する影響、のいずれかを含むことができる。
【０１６９】
更に、上述したように、一般化された方法と補助的方法は、最初に細分割曲面の特性に変換、またはそれを使用することなく、ポリゴンメッシュまたはＮＵＲＢＳ曲面上で、ＳＢＳ処理を行う機能を有することができる。この方法と補助的方法は、大きく、複雑なメッシュを会話形式で表示する機能と、曲面全体にわたって任意にトリミングする機能と、ＳＢＳモデル化処理と連係して使用可能な、初期３ｄ形状を生成するために、輪郭線を描画する機能も更に含むことができる。
【０１７０】
上記の説明は、当業者が本発明を行うことができるようにする詳細を含むが、説明は本質的に例としてであって、その多数の修正と変形が、これらの教示の恩恵を受けた当業者には明白であるということを認識されたい。従って、本明細書における本発明は、ここに付随する請求項によってのみ定義され、請求項は、従来技術により容認される程度に広く解釈されるように意図されている。
【図面の簡単な説明】
【０１７１】
本発明は、特に付随する請求項により示される。本発明の上記のおよび更なる利点は、添付された図面と連係する下記の説明を参照することでより良好に理解されよう。
【図１】本発明の形態を展開することができる例としてのデジタル処理環境の構成要素を例示する一連の図である。
【図２】本発明の形態を展開することができる例としてのデジタル処理環境の構成要素を例示する一連の図である。
【図３】本発明の形態を展開することができる例としてのデジタル処理環境の構成要素を例示する一連の図である。
【図４】本発明の形態を展開することができる例としてのデジタル処理環境の構成要素を例示する一連の図である。
【図５】オペレータなどにより、任意の時点におけるその作成の所与の状態における対象物の二次元画像に適用されるシェーディングにより、対象物の三次元モデルを生成する、本発明に従って構築されるコンピュータグラフィックスシステムを示している。
【図６】図５に示されているコンピュータグラフィックスシステムにより、任意の時点におけるその作成の所与の状態における対象物の二次元画像に適用されるシェーディングにより、対象物のモデルの更新を決定するときに実行される動作を理解するために有効な一連の図である。
【図７】図５に示されているコンピュータグラフィックスシステムにより、任意の時点におけるその作成の所与の状態における対象物の二次元画像に適用されるシェーディングにより、対象物のモデルの更新を決定するときに実行される動作を理解するために有効な一連の図である。
【図８】図５に示されているコンピュータグラフィックスシステムにより、任意の時点におけるその作成の所与の状態における対象物の二次元画像に適用されるシェーディングにより、対象物のモデルの更新を決定するときに実行される動作を理解するために有効な一連の図である。
【図９】図５に示されているコンピュータグラフィックスシステムにより、任意の時点におけるその作成の所与の状態における対象物の二次元画像に適用されるシェーディングにより、対象物のモデルの更新を決定するときに実行される動作を理解するために有効な一連の図である。
【図１０】図５に示されているコンピュータグラフィックスシステムにより、任意の時点におけるその作成の所与の状態における対象物の二次元画像に適用されるシェーディングにより、対象物のモデルの更新を決定するときに実行される動作を理解するために有効な一連の図である。
【図１１Ａ】本発明に関連する、コンピュータグラフィックスシステムとオペレータにより実行される動作を示すフローチャートである。
【図１１Ｂ】本発明に関連する、コンピュータグラフィックスシステムとオペレータにより実行される動作を示すフローチャートである。
【図１２】本発明によるＳＢＳシステム内のデータフローを示す図を示している。
【図１３】３ｄｓ  ｍａｘにおける、ＳＢＳモディファイヤのスクリーンショット３５０を示す図である。
【図１４】本発明の形態による、ＳＢＳ技術の擬似コード実装を示す図である。
【図１５】本発明の形態による、ＳＢＳ技術の擬似コード実装を示す図である。
【図１６Ａ】本発明の説明において使用される数学的表記法のリストを提供するテーブルを示す図である。
【図１６Ｂ】本発明の説明において使用される数学的表記法のリストを提供するテーブルを示す図である。
【図１７】本発明の種々の形態による、一般化された方法と補助的方法の一連のフローチャートである。
【図１８】本発明の種々の形態による、一般化された方法と補助的方法の一連のフローチャートである。
【図１９】本発明の種々の形態による、一般化された方法と補助的方法の一連のフローチャートである。
【図２０】本発明の種々の形態による、一般化された方法と補助的方法の一連のフローチャートである。
【図２１】本発明の種々の形態による、一般化された方法と補助的方法の一連のフローチャートである。
【図２２】本発明の種々の形態による、一般化された方法と補助的方法の一連のフローチャートである。
【図１】
2009521062.tif 000316
【図２】
2009521062.tif 000317
【図３】
2009521062.tif 000318
【図４】
2009521062.tif 000319
【図５】
2009521062.tif 000320
【図６】
2009521062.tif 000321
【図７】
2009521062.tif 000322
【図８】
2009521062.tif 000323
【図９】
2009521062.tif 000324
【図１０】
2009521062.tif 000325
【図１１Ａ】
2009521062.tif 000326
【図１１Ｂ】
2009521062.tif 000327
【図１２】
2009521062.tif 000328
【図１３】
2009521062.tif 000329
【図１４】
2009521062.tif 000330
【図１５】
2009521062.tif 000331
【図１６Ａ】
2009521062.tif 000332
【図１６Ｂ】
2009521062.tif 000333
【図１７】
2009521062.tif 000334
【図１８】
2009521062.tif 000335
【図１９】
2009521062.tif 000336
【図２０】
2009521062.tif 000337
【図２１】
2009521062.tif 000338
【図２２】
2009521062.tif 000339
【国際調査報告】
2009521062.tif 000340