(57)【特許請求の範囲】
【請求項１】
選択されたレベルで、それぞれの辺によって複数の隣接点に連結された少なくとも１つの点を含む複数の点を有するメッシュ表現によって定められた表面内に、前記メッシュ表現の頂点と、少なくとも１つの隣接点と、該頂点と該少なくとも１つの隣接点を相互接続する辺に関連して定められた特徴の表現を生成するシステムであって、
Ａ．複数のレベルで定められ、少なくとも１つのパラメータの値が前記メッシュの少なくとも２つのレベルで異なる値をとる、パラメータ化された細分則にもとづいて、少なくとも１つの重みベクトルを生成するように構成された重みベクトル生成モジュールと、
Ｂ．前記特徴の表現を生成するために、前記少なくとも１つの重みベクトルと、前記頂点と前記隣接点の位置を用いるように構成された特徴表現生成モジュールと、
を有し、
前記重みベクトル生成モジュールは、選択された数学関数によって関連づけられた少なくとも２つのレベルにおいて異なる値をとる、前記少なくとも１つのパラメータの値を用いるように構成され、
前記特徴は滑らかな特徴線であり、
前記滑らかな特徴線は、頂点と、２つの隣接点と、該頂点とそれぞれの該隣接点を相互接続する辺に関連して定められ、前記重みベクトル生成モジュールは、前記滑らかな特徴線がそれに沿うように定められる各前記辺と関連づけられたパラメータ値を有するパラメータ化された細分則を用いるように構成され、
前記メッシュは三角形メッシュを有し、該三角形メッシュでは、選択されたレベル「ｊ」において、頂点ｖq(０)が位置ｃj(０)にあり、隣接点ｖq(ｋ)（ｋ＝１，...，Ｋ）がそれぞれ位置ｃj(ｋ)にあり、前記重みベクトル生成モジュールは、
【数４】
0004253190.tif 000062
のように、次のより高いレベル「ｊ＋１」における頂点ｖq(０)の位置ｃj+1(０)と、隣接点ｖq(ｋ)の位置ｃj+1(ｋ)を関連づけるパラメータ化された細分則Ｓsc,T,K,Lを用いるように構成され、ここで、細分則Ｓsc,T,K,Lは、
【数５】
0004253190.tif 000063
によって与えられ、ここで、前記滑らかな特徴線は、それぞれの点ｖq(１)とｖq(Ｌ＋１)（Ｌ＋１≦Ｋ）と頂点ｖq(０)の間の辺に関連して定められ、ｓ1は点ｖq(１)と頂点ｖq(０)の間の辺と関連づけられたパラメータであり、ｓ2は点ｖq(Ｌ＋１)と頂点ｖq(０)の間の辺と関連づけられたパラメータであり、ｓ3＝(ｓ1＋ｓ2)／２であり、
【数６】
0004253190.tif 000064
である、システム。
【請求項２】
前記特徴の表現は、頂点と関連づけられた少なくとも１つの極限点によって定められ、
前記特徴表現生成モジュールは、
【数７】
0004253190.tif 000065
にしたがって、前記極限点の位置σ(ｑ)を求めるように構成され、ここで、ｌLP(ｓ1，ｓ2)は、
【数８】
0004253190.tif 000066
によって定められた極限点重み値のベクトルであり、ここで、
【数９】
0004253190.tif 000067
であり、ここで、Ｓsc,T,K,L（ｓ1（ｊ），ｓ2（ｊ））は、行列積の「ｊ」番目のレベルに対応する鋭さパラメータに対するＳsc,T,K,Lに対応し、ここで、左辺のＳsc,T,K,L,LP（ｓ1，ｓ2）の独立変数ｓ1とｓ2は、前記滑らかな特徴線の設定レベルにおける前記鋭さパラメータを示し、下付き文字「ＬＰ」は「極限点」を示し、
【数１０】
0004253190.tif 000068
であり、ここで、
【数１１】
0004253190.tif 000069
である、請求項１に記載のシステム。
【請求項３】
前記重みベクトル生成モジュールは、多項式近似法を用いて、極限点重みベクトルｌLPの近似を生成するように構成されている、請求項２に記載のシステム。
【請求項４】
前記重みベクトル生成モジュールは、対称的な場合には、多項式
【数１２】
0004253190.tif 000070
にしたがって、非対称的な場合には、多項式
【数１３】
0004253190.tif 000071
にしたがって、極限点重みベクトルｌLPの近似を生成するように構成され、ここで、係数ｂijは最小自乗法により求められ、パラメータｓ1とｓ2の値は選択された値にある、請求項３に記載のシステム。
【請求項５】
前記重みベクトル生成モジュールは、
【数１４】
0004253190.tif 000072
にしたがって、ｓ1とｓ2の値を選択するように構成され、ここで、「Ｎ」は選択された整数であり、インデックスｉ，ｊ＝０，．．．，Ｎ−１である、請求項４に記載のシステム。
【請求項６】
前記重みベクトル生成モジュールは、点
【数１５】
0004253190.tif 000073
を内挿するＭ次の多項式に関連して外挿近似法を用い、その後、点ｘ＝０における外挿によってこの多項式を計算して、極限点重みベクトルｌLPの近似を生成するように構成されている、請求項２に記載のシステム。
【請求項７】
前記重みベクトル生成モジュールは、Ｍ＝３となるように、前記外挿近似法を行うように構成されている、請求項６に記載のシステム。
【請求項８】
前記重みベクトル生成モジュールは、
【数１６】
0004253190.tif 000074
にしたがって、前記極限点重みベクトルの近似を生成するように構成され、ここで、「Ｊ」は所定の整数であり、ここで、
【数１７】
0004253190.tif 000075
であり、ここで、
【数１８】
0004253190.tif 000076
と、
【数１９】
0004253190.tif 000077
であり、ここで、ＩK+1は「Ｋ＋１」×「Ｋ＋１」の単位行列であり、ここで、
【数２０】
0004253190.tif 000078
である、請求項７に記載のシステム。
【請求項９】
前記特徴の表現は、頂点と関連づけられた、前記滑らかな特徴線に沿う接線ベクトルに
よって定められ、前記特徴表現生成モジュールは、
【数２１】
0004253190.tif 000079
にしたがって、接線ベクトルｅC（ｑ）を求めるように構成され、ここで、ｌC（ｓ1，ｓ2）は、
【数２２】
0004253190.tif 000080
によって定められた接線ベクトル重み値のベクトルであり、ここで、
【数２３】
0004253190.tif 000081
すなわち、ユークリッド・ノルムであり、ここで、
【数２４】
0004253190.tif 000082
であり、ここで、右辺の行ベクトルの２つのゼロでない成分が、行ベクトル中の位置「１」における「１」であり、位置Ｋ／２＋１における「負の１」であり、ここで、Ｓsc,T,K,L（ｓ1（ｊ），ｓ2（ｊ））は、行列積の「ｊ」番目のレベルに対応する鋭さパラメータに対するＳsc,T,K,Lに対応する、請求項１に記載のシステム。
【請求項１０】
前記重みベクトル生成モジュールは、多項式近似法を用いて、接線ベクトル重みベクトルｌCを生成するように構成されている、請求項９に記載のシステム。
【請求項１１】
前記重みベクトル生成モジュールは、反対称の場合に、多項式
【数２５】
0004253190.tif 000083
にしたがって、非対称の場合に、多項式
【数２６】
0004253190.tif 000084
にしたがって、接線ベクトル重みベクトルｌCの近似を生成するように構成され、ここで、係数ｂijは最小自乗法によって求められ、パラメータｓ1とｓ2の値は選択された値にある、請求項１０に記載のシステム。
【請求項１２】
前記重みベクトル生成モジュールは、
【数２７】
0004253190.tif 000085
にしたがって、ｓ1とｓ2の値を選択するように構成され、ここで、「Ｎ」は選択された整数であり、インデックスｉ，ｊ＝０，．．．，Ｎ−１である、請求項１１に記載のシステム。
【請求項１３】
前記重みベクトル生成モジュールは、点
【数２８】
0004253190.tif 000086
を内挿するＭ次の多項式に関連して外挿近似法を用い、その後、点ｘ＝０における外挿によってこの多項式を計算して、接線ベクトル重みベクトルｌCの近似を生成するように構成されている、請求項９に記載のシステム。
【請求項１４】
前記重みベクトル生成モジュールは、Ｍ＝３となるように、前記外挿近似法を行うよう
に構成されている、請求項１３に記載のシステム。
【請求項１５】
前記重みベクトル生成モジュールは、
【数２９】
0004253190.tif 000087
にしたがって、接線ベクトル重みベクトルｌCの近似を生成するように構成され、ここで、「Ｊ」は所定の整数であり、ここで、
【数３０】
0004253190.tif 000088
であり、ここで、ベクトルｖCは、
【数３１】
0004253190.tif 000089
によって与えられ、拡張係数ｄ（Ｋ）は、
【数３２】
0004253190.tif 000090
によって与えられ、
【数３３】
0004253190.tif 000091
と、
【数３４】
0004253190.tif 000092
であり、ここで、ＩK+1は「Ｋ＋１」×「Ｋ＋１」の単位行列であり、ここで、
【数３５】
0004253190.tif 000093
である、請求項１４に記載のシステム。
【請求項１６】
前記特徴の表現は、頂点と関連づけられた、前記滑らかな特徴線と交差する接線ベクトルによって定められ、前記特徴表現生成モジュールは、
【数３６】
0004253190.tif 000094
にしたがって、接線ベクトルｅC（ｑ）を求めるように構成され、ここで、ｌS（ｓ1，ｓ2）は、
【数３７】
0004253190.tif 000095
によって定められた接線ベクトル重み値のベクトルであり、ここで、
【数３８】
0004253190.tif 000096
すなわち、ユークリッド・ノルムであり、ここで、
【数３９】
0004253190.tif 000097
であり、ここで、Ｓsc,T,K,L（ｓ1（ｊ），ｓ2（ｊ））は、行列積の「ｊ」番目のレベルに対応する鋭さパラメータに対するＳsc,T,K,Lに対応する、請求項１に記載のシステム。
【請求項１７】
前記重みベクトル生成モジュールは、多項式近似法を用いて、接線ベクトル重みベクトルｌCを生成するように構成されている、請求項１６に記載のシステム。
【請求項１８】
前記重みベクトル生成モジュールは、反対称の場合に、多項式
【数４０】
0004253190.tif 000098
にしたがって、非対称の場合に、多項式
【数４１】
0004253190.tif 000099
にしたがって、接線ベクトル重みベクトルｌSの近似を生成するように構成され、ここで、係数ｂijは、最小自乗法によって求められ、パラメータｓ1とｓ2の値は、選択された値にある、請求項１７に記載のシステム。
【請求項１９】
前記重みベクトル生成モジュールは、
【数４２】
0004253190.tif 000100
にしたがって、ｓ1とｓ2の値を選択するように構成され、ここで、「Ｎ」は選択された整数であり、インデックスｉ，ｊ＝０，．．．，Ｎ−１である、請求項１８に記載のシステム。
【請求項２０】
前記重みベクトル生成モジュールは、点
【数４３】
0004253190.tif 000101
を内挿するＭ次の多項式に関連して外挿近似法を用い、その後、点ｘ＝０における外挿によってこの多項式を計算して、接線ベクトル重みベクトルｌSの近似を生成するように構成されている、請求項１５に記載のシステム。
【請求項２１】
前記重みベクトル生成モジュールは、Ｍ＝３となるように、前記外挿近似法を行うように構成されている、請求項２０に記載のシステム。
【請求項２２】
前記重みベクトル生成モジュールは、
【数４４】
0004253190.tif 000102
にしたがって、極限点重みベクトルの近似を生成するように構成され、ここで、「Ｊ」は所定の整数であり、ここで、
【数４５】
0004253190.tif 000103
であり、ここで、ベクトルｖSは、
【数４６】
0004253190.tif 000104
によって与えられ、拡張係数ｄ（Ｋ）は、
【数４７】
0004253190.tif 000105
によって与えられ、
【数４８】
0004253190.tif 000106
と、
【数４９】
0004253190.tif 000107
であり、ここで、ＩK+1は「Ｋ＋１」×「Ｋ＋１」の単位行列であり、ここで、
【数５０】
0004253190.tif 000108
である、請求項２１に記載のシステム。
【請求項２３】
選択されたレベルで、それぞれの辺によって複数の隣接点に連結された少なくとも１つの点を含む複数の点を有するメッシュ表現によって定められた表面内に、前記メッシュ表現の頂点と、少なくとも１つの隣接点と、該頂点と該少なくとも１つの隣接点を相互接続する辺に関連して定められた特徴の表現を生成するシステムであって、
Ａ．複数のレベルで定められ、少なくとも１つのパラメータの値が前記メッシュの少なくとも２つのレベルで異なる値をとる、パラメータ化された細分則にもとづいて、少なくとも１つの重みベクトルを生成するように構成された重みベクトル生成モジュールと、
Ｂ．前記特徴の表現を生成するために、前記少なくとも１つの重みベクトルと、前記頂点と前記隣接点の位置を用いるように構成された特徴表現生成モジュールと、
を有し、
前記重みベクトル生成モジュールは、選択された数学関数によって関連づけられた少なくとも２つのレベルにおいて異なる値をとる、前記少なくとも１つのパラメータの値を用いるように構成され、
前記特徴は滑らかな特徴線であり、
前記滑らかな特徴線は、頂点と、２つの隣接点と、該頂点とそれぞれの該隣接点を相互接続する辺に関連して定められ、前記重みベクトル生成モジュールは、前記滑らかな特徴線がそれに沿うように定められる各前記辺と関連づけられたパラメータ値を有するパラメータ化された細分則を用いるように構成され、
前記メッシュは四辺形メッシュを有し、この四辺形メッシュでは、選択されたレベル「ｊ」において、頂点ｖq（０）が位置ｃj（０）にあり、隣接点ｖq（ｋ）（ｋ＝１，．．．，２Ｋ）がそれぞれの位置ｃj（ｋ）にあり、前記重みベクトル生成モジュールは、
【数５１】
0004253190.tif 000109
のように、次のより高いレベル「ｊ＋１」における頂点ｖq（０）の位置ｃj+1（０）と隣接点ｖq（ｋ）の位置ｃj+1（ｋ）を関連づけるパラメータ化された細分則Ｓsc,Q,K,Lを用いるように構成され、ここで、細分則Ｓsc,Q,K,Lは、
【数５２】
0004253190.tif 000110
によって与えられ、ここで、前記滑らかな特徴線は、それぞれの点ｖq（１）とｖq（Ｌ＋１）（Ｌ＋１≦２Ｋ）と頂点ｖq（０）の間の辺と関連して定められ、ｓ1は点ｖq（１）と頂点ｖq（０）の間の辺と関連づけられたパラメータであり、ｓ2は点ｖq（Ｌ＋１）と頂点ｖq（０）の間の辺と関連づけられたパラメータであり、ｓ3＝（ｓ1＋ｓ2）／２である、システム。
【請求項２４】
前記特徴の表現は、頂点と関連づけられた少なくとも１つの極限点によって定められ、
前記特徴表現生成モジュールは、
【数５３】
0004253190.tif 000111
にしたがって、前記極限点の位置σ（ｑ）を求めるように構成され、ここで、ｌLP（ｓ1，ｓ2）は、
【数５４】
0004253190.tif 000112
によって定められた極限点重み値のベクトルであり、ここで、
【数５５】
0004253190.tif 000113
であり、ここで、Ｓsc,Q,K,L（ｓ1（ｊ），ｓ2（ｊ））は、行列積の「ｊ」番目のレベルに対応する鋭さパラメータに対するＳsc,Q,K,Lに対応し、ここで、左辺のＳsc,Q,K,L,LP（ｓ1，ｓ2）の独立変数ｓ1とｓ2は、前記滑らかな特徴線の設定レベルにおける鋭さパラメータを示し、下付きの文字「ＬＰ」は「極限点」を示し、
【数５６】
0004253190.tif 000114
である、請求項２３に記載のシステム。
【請求項２５】
前記重みベクトル生成モジュールは、多項式近似法を用いて、極限点重みベクトルｌLPの近似を生成するように構成されている、請求項２４に記載のシステム。
【請求項２６】
前記重みベクトル生成モジュールは、対称的な場合に、多項式
【数５７】
0004253190.tif 000115
にしたがって、非対称的な場合に、多項式
【数５８】
0004253190.tif 000116
にしたがって、極限点重みベクトルｌLPの近似を生成するように構成され、ここで、係数ｂijは、最小自乗法によって求められ、パラメータｓ1とｓ2の値は、選択された値にある、請求項２５に記載のシステム。
【請求項２７】
前記重みベクトル生成モジュールは、
【数５９】
0004253190.tif 000117
にしたがって、ｓ1とｓ2の値を選択するように構成され、ここで、「Ｎ」は選択された整数であり、インデックスｉ，ｊ＝０，．．．，Ｎ−１である、請求項２６に記載のシステム。
【請求項２８】
前記重みベクトル生成モジュールは、点
【数６０】
0004253190.tif 000118
を内挿するＭ次の多項式に関連して外挿近似法を用い、その後、点ｘ＝０における外挿によってこの多項式を計算して、極限点重みベクトルｌLPについての近似を生成するように構成されている、請求項２４に記載のシステム。
【請求項２９】
前記重みベクトル生成モジュールは、Ｍ＝３となるように、前記外挿近似法を行うように構成されている、請求項２８に記載のシステム。
【請求項３０】
前記重みベクトル生成モジュールは、
【数６１】
0004253190.tif 000119
にしたがって、極限点重みベクトル重みベクトルの近似を生成するように構成され、ここで、「Ｊ」は所定の整数であり、ここで、
【数６２】
0004253190.tif 000120
であり、ここで、
【数６３】
0004253190.tif 000121
と、
【数６４】
0004253190.tif 000122
であり、ここで、Ｉ2K+1は「２Ｋ＋１」×「２Ｋ＋１」の単位行列であり、ここで、
【数６５】
0004253190.tif 000123
である、請求項２９に記載のシステム。
【請求項３１】
前記特徴の表現は、頂点と関連づけられた、前記滑らかな特徴線に沿う接線ベクトルによって定められ、前記特徴表現生成モジュールは、
【数６６】
0004253190.tif 000124
にしたがって、接線ベクトルｅC（ｑ）を求めるように構成され、ここで、ｌC（ｓ1，ｓ2）は、
【数６７】
0004253190.tif 000125
によって定められた接線ベクトル重み値のベクトルであり、ここで、
【数６８】
0004253190.tif 000126
であり、ベクトルｖCは、
【数６９】
0004253190.tif 000127
として定められ、ここで、
【数７０】
0004253190.tif 000128
であり、ここで、拡張係数ｄ（Ｋ）は、
【数７１】
0004253190.tif 000129
によって与えられる、請求項２３に記載のシステム。
【請求項３２】
前記重みベクトル生成モジュールは、多項式近似法を用いて、前記接線ベクトル重みベクトルｌCを生成するように構成されている、請求項３１に記載のシステム。
【請求項３３】
前記重みベクトル生成モジュールは、反対称の場合に、多項式
【数７２】
0004253190.tif 000130
にしたがって、非対称の場合に、多項式
【数７３】
0004253190.tif 000131
にしたがって、接線ベクトル重みベクトルｌCの近似を生成するように構成され、ここで、係数ｂijは最小自乗法によって求められ、パラメータｓ1とｓ2の値は選択された値にある、請求項３２に記載のシステム。
【請求項３４】
前記重みベクトル生成モジュールは、
【数７４】
0004253190.tif 000132
にしたがって、ｓ1とｓ2の値を選択するように構成され、ここで、「Ｎ」は選択された整数であり、インデックスｉ，ｊ＝０，．．．，Ｎ−１である、請求項３３に記載のシステム。
【請求項３５】
前記重みベクトル生成モジュールは、点
【数７５】
0004253190.tif 000133
を内挿するＭ次の多項式に関連して外挿近似法を用い、その後、点ｘ＝０における外挿によってこの多項式を計算して、接線ベクトル重みベクトルｌCの近似を生成するように構成されている、請求項３１に記載のシステム。
【請求項３６】
前記重みベクトル生成モジュールは、Ｍ＝３となるように、前記外挿近似法を行うように構成されている、請求項３５に記載のシステム。
【請求項３７】
前記重みベクトル生成モジュールは、
【数７６】
0004253190.tif 000134
にしたがって、接線ベクトル重みベクトルｌCの近似を生成するように構成され、ここで、「Ｊ」は所定の整数であり、ここで、
【数７７】
0004253190.tif 000135
であり、ここで、ベクトルｖCは、
【数７８】
0004253190.tif 000136
によって与えられ、拡張係数ｄ（Ｋ）は、
【数７９】
0004253190.tif 000137
によって与えられ、
【数８０】
0004253190.tif 000138
と、
【数８１】
0004253190.tif 000139
であり、ここで、Ｉ2K+1は「２Ｋ＋１」×「２Ｋ＋１」の単位行列であり、ここで、
【数８２】
0004253190.tif 000140
である、請求項３６に記載のシステム。
【請求項３８】
前記特徴の表現は、頂点と関連づけられた、前記滑らかな特徴線を交差する接線ベクトルによって定められ、前記特徴表現生成モジュールは、
【数８３】
0004253190.tif 000141
にしたがって、接線ベクトルｅC（ｑ）を求めるように構成され、ここで、ｌC（ｓ1，ｓ2）は、
【数８４】
0004253190.tif 000142
によって定められた接線ベクトル重み値のベクトルであり、ここで、
【数８５】
0004253190.tif 000143
であり、ベクトルｖCは、
【数８６】
0004253190.tif 000144
として定められ、ここで、
【数８７】
0004253190.tif 000145
であり、ここで、拡張係数ｄ（Ｋ）は、
【数８８】
0004253190.tif 000146
によって与えられる、請求項２３に記載のシステム。
【請求項３９】
前記重みベクトル生成モジュールは、多項式近似法を用いて、接線ベクトル重みベクトルｌCの近似を生成するように構成されている、請求項３８に記載のシステム。
【請求項４０】
前記重みベクトル生成モジュールは、反対称の場合に、多項式
【数８９】
0004253190.tif 000147
にしたがって、非対称の場合に、多項式
【数９０】
0004253190.tif 000148
にしたがって、接線ベクトル重みベクトルｌSの近似を生成するように構成され、ここで、係数ｂijは最小自乗法によって求められ、パラメータｓ1とｓ2の値は選択された値にある、請求項３９に記載のシステム。
【請求項４１】
前記重みベクトル生成モジュールは、
【数９１】
0004253190.tif 000149
にしたがって、ｓ1とｓ2の値を選択するように構成され、ここで、「Ｎ」は選択された整数であり、インデックスｉ，ｊ＝０，．．．，Ｎ−１である、請求項４０に記載のシステム。
【請求項４２】
前記重みベクトル生成モジュールは、点
【数９２】
0004253190.tif 000150
を内挿するＭ次の多項式に関連して外挿近似法を用い、その後、点ｘ＝０における外挿によってこの多項式を計算して、接線ベクトル重みベクトルｌSの近似を生成するように構成されている、請求項３８に記載のシステム。
【請求項４３】
前記重みベクトル生成モジュールは、Ｍ＝３となるように、前記外挿近似法を行うように構成されている、請求項４２に記載のシステム。
【請求項４４】
前記重みベクトル生成モジュールは、
【数９３】
0004253190.tif 000151
にしたがって、極限点重みベクトルの近似を生成するように構成され、ここで、「Ｊ」は所定の整数であり、ここで、
【数９４】
0004253190.tif 000152
であり、ここで、ベクトルｖSは、
【数９５】
0004253190.tif 000153
によって与えられ、拡張係数ｄ（Ｋ）は、
【数９６】
0004253190.tif 000154
によって与えられ、
【数９７】
0004253190.tif 000155
と、
【数９８】
0004253190.tif 000156
であり、ここで、Ｉ2K+1は「２Ｋ＋１」×「２Ｋ＋１」の単位行列であり、ここで、
【数９９】
0004253190.tif 000157
である、請求項４３に記載のシステム。
【請求項４５】
選択されたレベルで、それぞれの辺によって複数の隣接点に連結された少なくとも１つの点を含む複数の点を有するメッシュ表現によって定められた表面内に、前記メッシュ表現の頂点と、少なくとも１つの隣接点と、該頂点と該少なくとも１つの隣接点を相互接続する辺と関連して定められた特徴の表現を生成するシステムを提供するコンピュータと関連づけて用いられるコンピュータプログラムであって、
Ａ．  前記コンピュータを、複数のレベルで定められ、少なくとも１つのパラメータの値が前記メッシュの少なくとも２つのレベルで異なる値をとる、パラメータ化された細分則にもとづいて、少なくとも１つの重みベクトルを生成することができるように構成された重みベクトル生成モジュールと、
Ｂ．  前記コンピュータを、前記特徴の表現を生成するために、前記少なくとも１つの重みベクトルと、前記頂点と前記隣接点の位置を用いることができるように構成された特徴表現生成モジュールと、
として機能させ、
前記重みベクトル生成モジュールは、選択された数学関数によって関連づけられた少なくとも２つのレベルにおいて異なる値をとる、前記少なくとも１つのパラメータの値を用いることができるように構成され、
前記特徴は滑らかな特徴線であり、
前記滑らかな特徴線は、頂点と、２つの隣接点と、該頂点とそれぞれの該隣接点を相互接続する辺と関連して定められ、前記重みベクトル生成モジュールは、前記滑らかな特徴線がそれに沿うように定められる各前記辺と関連づけられたパラメータ値を有するパラメータ化された細分則を用いることができるように構成され、
前記メッシュは三角形メッシュを有し、該三角形メッシュでは、選択されたレベル「ｊ」において、頂点ｖq(０)が位置ｃj(０)にあり、隣接点ｖq(ｋ)（ｋ＝１，...，Ｋ）がそれぞれ位置ｃj(ｋ)にあり、前記重みベクトル生成モジュールは、
【数１０３】
0004253190.tif 000158
のように、次のより高いレベル「ｊ＋１」における頂点ｖq(０)の位置ｃj+1(０)と、隣接点ｖq(ｋ)の位置ｃj+1(ｋ)を関連づけるパラメータ化された細分則Ｓsc,T,K,Lを用いることができるように構成され、ここで、細分則Ｓsc,T,K,Lは、
【数１０４】
0004253190.tif 000159
によって与えられ、ここで、前記滑らかな特徴線は、それぞれの点ｖq(１)とｖq(Ｌ＋１)（Ｌ＋１≦Ｋ）と頂点ｖq(０)の間の辺に関連して定められ、ｓ1は点ｖq(１)と頂点ｖq(０)の間の辺と関連づけられたパラメータであり、ｓ2は点ｖq(Ｌ＋１)と頂点ｖq(０)の間の辺と関連づけられたパラメータであり、ｓ3＝(ｓ1＋ｓ2)／２であり、
【数１０５】
0004253190.tif 000160
である、コンピュータプログラム。
【請求項４６】
前記特徴の表現は、頂点と関連づけられた少なくとも１つの極限点によって定められ、
前記特徴表現生成モジュールは、
【数１０６】
0004253190.tif 000161
にしたがって、前記極限点の位置σ(ｑ)を求めることができるように構成され、ここで、ｌLP(ｓ1，ｓ2)は、
【数１０７】
0004253190.tif 000162
によって定められた極限点重み値のベクトルであり、ここで、
【数１０８】
0004253190.tif 000163
であり、ここで、Ｓsc,T,K,L（ｓ1（ｊ），ｓ2（ｊ））は、行列積の「ｊ」番目のレベルに対応する鋭さパラメータに対するＳsc,T,K,Lに対応し、ここで、左辺のＳsc,T,K,L,LP（ｓ1，ｓ2）の独立変数ｓ1とｓ2は、前記滑らかな特徴線の設定レベルにおける前記鋭さパラメータを示し、下付き文字「ＬＰ」は「極限点」を示し、
【数１０９】
0004253190.tif 000164
であり、ここで、
【数１１０】
0004253190.tif 000165
である、請求項４５に記載のコンピュータプログラム。
【請求項４７】
前記重みベクトル生成モジュールは、多項式近似法を用いて、極限点重みベクトルｌLPの近似を生成することができるように構成されている、請求項４６に記載のコンピュータプログラム。
【請求項４８】
前記重みベクトル生成モジュールは、対称的な場合には、多項式
【数１１１】
0004253190.tif 000166
にしたがって、非対称的な場合には、多項式
【数１１２】
0004253190.tif 000167
にしたがって、極限点重みベクトルｌLPの近似を生成することができるように構成され、ここで、係数ｂijは最小自乗法により求められ、パラメータｓ1とｓ2の値は選択された値にある、請求項４７に記載のコンピュータプログラム。
【請求項４９】
前記重みベクトル生成モジュールは、
【数１１３】
0004253190.tif 000168
にしたがって、ｓ1とｓ2の値を選択することができるように構成され、ここで、「Ｎ」は選択された整数であり、インデックスｉ，ｊ＝０，．．．，Ｎ−１である、請求項４８に記載のコンピュータプログラム。
【請求項５０】
前記重みベクトル生成モジュールは、点
【数１１４】
0004253190.tif 000169
を内挿するＭ次の多項式に関連して外挿近似法を用い、その後、点ｘ＝０における外挿によってこの多項式を計算して、極限点重みベクトルｌLPの近似を生成することができるように構成されている、請求項４６に記載のコンピュータプログラム。
【請求項５１】
前記重みベクトル生成モジュールは、Ｍ＝３となるように、前記外挿近似法を行うことができるように構成されている、請求項５０に記載のコンピュータプログラム。
【請求項５２】
前記重みベクトル生成モジュールは、
【数１１５】
0004253190.tif 000170
にしたがって、前記極限点重みベクトルの近似を生成することができるように構成され、ここで、「Ｊ」は所定の整数であり、ここで、
【数１１６】
0004253190.tif 000171
であり、ここで、
【数１１７】
0004253190.tif 000172
と、
【数１１８】
0004253190.tif 000173
であり、ここで、ＩK+1は「Ｋ＋１」×「Ｋ＋１」の単位行列であり、ここで、
【数１１９】
0004253190.tif 000174
である、請求項５１に記載のコンピュータプログラム。
【請求項５３】
前記特徴の表現は、頂点と関連づけられた、前記滑らかな特徴線に沿う接線ベクトルによって定められ、前記特徴表現生成モジュールは、
【数１２０】
0004253190.tif 000175
にしたがって、接線ベクトルｅC（ｑ）を求めることができるように構成され、ここで、ｌC（ｓ1，ｓ2）は、
【数１２１】
0004253190.tif 000176
によって定められた接線ベクトル重み値のベクトルであり、ここで、
【数１２２】
0004253190.tif 000177
すなわち、ユークリッド・ノルムであり、ここで、
【数１２３】
0004253190.tif 000178
であり、ここで、右辺の行ベクトルの２つのゼロでない成分が、行ベクトル中の位置「１」における「１」であり、位置Ｋ／２＋１における「負の１」であり、ここで、Ｓsc,T,K,L（ｓ1（ｊ），ｓ2（ｊ））は、行列積の「ｊ」番目のレベルに対応する鋭さパラメータに対するＳsc,T,K,Lに対応する、請求項４５に記載のコンピュータプログラム。
【請求項５４】
前記重みベクトル生成モジュールは、多項式近似法を用いて、接線ベクトル重みベクトルｌCを生成することができるように構成されている、請求項５３に記載のコンピュータプログラム。
【請求項５５】
前記重みベクトル生成モジュールは、反対称の場合に、多項式
【数１２４】
0004253190.tif 000179
にしたがって、非対称の場合に、多項式
【数１２５】
0004253190.tif 000180
にしたがって、接線ベクトル重みベクトルｌCの近似を生成することができるように構成され、ここで、係数ｂijは最小自乗法によって求められ、パラメータｓ1とｓ2の値は選択された値にある、請求項５４に記載のコンピュータプログラム。
【請求項５６】
前記重みベクトル生成モジュールは、
【数１２６】
0004253190.tif 000181
にしたがって、ｓ1とｓ2の値を選択することができるように構成され、ここで、「Ｎ」は選択された整数であり、インデックスｉ，ｊ＝０，．．．，Ｎ−１である、請求項５５に記載のコンピュータプログラム。
【請求項５７】
前記重みベクトル生成モジュールは、点
【数１２７】
0004253190.tif 000182
を内挿するＭ次の多項式に関連して外挿近似法を用い、その後、点ｘ＝０における外挿によってこの多項式を計算して、接線ベクトル重みベクトルｌCの近似を生成することができるように構成されている、請求項５３に記載のコンピュータプログラム。
【請求項５８】
前記重みベクトル生成モジュールは、Ｍ＝３となるように、前記外挿近似法を行うことができるように構成されている、請求項５７に記載のコンピュータプログラム。
【請求項５９】
前記重みベクトル生成モジュールは、
【数１２８】
0004253190.tif 000183
にしたがって、接線ベクトル重みベクトルｌCの近似を生成することができるように構成され、ここで、「Ｊ」は所定の整数であり、ここで、
【数１２９】
0004253190.tif 000184
であり、ここで、ベクトルｖCは、
【数１３０】
0004253190.tif 000185
によって与えられ、拡張係数ｄ（Ｋ）は、
【数１３１】
0004253190.tif 000186
によって与えられ、
【数１３２】
0004253190.tif 000187
と、
【数１３３】
0004253190.tif 000188
であり、ここで、ＩK+1は「Ｋ＋１」×「Ｋ＋１」の単位行列であり、ここで、
【数１３４】
0004253190.tif 000189
である、請求項５８に記載のコンピュータプログラム。
【請求項６０】
前記特徴の表現は、頂点と関連づけられた、前記滑らかな特徴線と交差する接線ベクトルによって定められ、前記特徴表現生成モジュールは、
【数１３５】
0004253190.tif 000190
にしたがって、接線ベクトルｅC（ｑ）を求めることができるように構成され、ここで、ｌS（ｓ1，ｓ2）は、
【数１３６】
0004253190.tif 000191
によって定められた接線ベクトル重み値のベクトルであり、ここで、
【数１３７】
0004253190.tif 000192
すなわち、ユークリッド・ノルムであり、ここで、
【数１３８】
0004253190.tif 000193
であり、ここで、Ｓsc,T,K,L（ｓ1（ｊ），ｓ2（ｊ））は、行列積の「ｊ」番目のレベルに対応する鋭さパラメータに対するＳsc,T,K,Lに対応する、請求項４５に記載のコンピュータプログラム。
【請求項６１】
前記重みベクトル生成モジュールは、多項式近似法を用いて、接線ベクトル重みベクト
ルｌCを生成することができるように構成されている、請求項６０に記載のコンピュータプログラム。
【請求項６２】
前記重みベクトル生成モジュールは、反対称の場合に、多項式
【数１３９】
0004253190.tif 000194
にしたがって、非対称の場合に、多項式
【数１４０】
0004253190.tif 000195
にしたがって、接線ベクトル重みベクトルｌSの近似を生成することができるように構成され、ここで、係数ｂijは、最小自乗法によって求められ、パラメータｓ1とｓ2の値は、選択された値にある、請求項６１に記載のコンピュータプログラム。
【請求項６３】
前記重みベクトル生成モジュールは、
【数１４１】
0004253190.tif 000196
にしたがって、ｓ1とｓ2の値を選択することができるように構成され、ここで、「Ｎ」は選択された整数であり、インデックスｉ，ｊ＝０，．．．，Ｎ−１である、請求項６２に記載のコンピュータプログラム。
【請求項６４】
前記重みベクトル生成モジュールは、点
【数１４２】
0004253190.tif 000197
を内挿するＭ次の多項式に関連して外挿近似法を用い、その後、点ｘ＝０における外挿によってこの多項式を計算して、接線ベクトル重みベクトルｌSの近似を生成することができるように構成されている、請求項５９に記載のコンピュータプログラム。
【請求項６５】
前記重みベクトル生成モジュールは、Ｍ＝３となるように、前記外挿近似法を行うことができるように構成されている、請求項６４に記載のコンピュータプログラム。
【請求項６６】
前記重みベクトル生成モジュールは、
【数１４３】
0004253190.tif 000198
にしたがって、極限点重みベクトルの近似を生成することができるように構成され、ここで、「Ｊ」は所定の整数であり、ここで、
【数１４４】
0004253190.tif 000199
であり、ここで、ベクトルｖSは、
【数１４５】
0004253190.tif 000200
によって与えられ、拡張係数ｄ（Ｋ）は、
【数１４６】
0004253190.tif 000201
によって与えられ、
【数１４７】
0004253190.tif 000202
と、
【数１４８】
0004253190.tif 000203
であり、ここで、ＩK+1は「Ｋ＋１」×「Ｋ＋１」の単位行列であり、ここで、
【数１４９】
0004253190.tif 000204
である、請求項６５に記載のコンピュータプログラム。
【請求項６７】
選択されたレベルで、それぞれの辺によって複数の隣接点に連結された少なくとも１つの点を含む複数の点を有するメッシュ表現によって定められた表面内に、前記メッシュ表現の頂点と、少なくとも１つの隣接点と、該頂点と該少なくとも１つの隣接点を相互接続する辺と関連して定められた特徴の表現を生成するシステムを提供するコンピュータと関連づけて用いられるコンピュータプログラムであって、
Ａ．  前記コンピュータを、複数のレベルで定められ、少なくとも１つのパラメータの値が前記メッシュの少なくとも２つのレベルで異なる値をとる、パラメータ化された細分則にもとづいて、少なくとも１つの重みベクトルを生成することができるように構成された重みベクトル生成モジュールと、
Ｂ．  前記コンピュータを、前記特徴の表現を生成するために、前記少なくとも１つの重みベクトルと、前記頂点と前記隣接点の位置を用いることができるように構成された特徴表現生成モジュールと、
として機能させ、
前記重みベクトル生成モジュールは、選択された数学関数によって関連づけられた少なくとも２つのレベルにおいて異なる値をとる、前記少なくとも１つのパラメータの値を用いることができるように構成され、
前記特徴は滑らかな特徴線であり、
前記滑らかな特徴線は、頂点と、２つの隣接点と、該頂点とそれぞれの該隣接点を相互接続する辺と関連して定められ、前記重みベクトル生成モジュールは、前記滑らかな特徴線がそれに沿うように定められる各前記辺と関連づけられたパラメータ値を有するパラメータ化された細分則を用いることができるように構成され、
前記メッシュは四辺形メッシュを有し、この四辺形メッシュでは、選択されたレベル「ｊ」において、頂点ｖq（０）が位置ｃj（０）にあり、隣接点ｖq（ｋ）（ｋ＝１，．．．，２Ｋ）がそれぞれの位置ｃj（ｋ）にあり、前記重みベクトル生成モジュールは、
【数１５０】
0004253190.tif 000205
のように、次のより高いレベル「ｊ＋１」における頂点ｖq（０）の位置ｃj+1（０）と隣接点ｖq（ｋ）の位置ｃj+1（ｋ）を関連づけるパラメータ化された細分則Ｓsc,Q,K,Lを用いることができるように構成され、ここで、細分則Ｓsc,Q,K,Lは、
【数１５１】
0004253190.tif 000206
によって与えられ、ここで、前記滑らかな特徴線は、それぞれの点ｖq（１）とｖq（Ｌ＋１）（Ｌ＋１≦２Ｋ）と頂点ｖq（０）の間の辺と関連して定められ、ｓ1は点ｖq（１）と頂点ｖq（０）の間の辺と関連づけられたパラメータであり、ｓ2は点ｖq（Ｌ＋１）と頂点ｖq（０）の間の辺と関連づけられたパラメータであり、ｓ3＝（ｓ1＋ｓ2）／２である、コンピュータプログラム。
【請求項６８】
前記特徴の表現は、頂点と関連づけられた少なくとも１つの極限点によって定められ、
前記特徴表現生成モジュールは、
【数１５２】
0004253190.tif 000207
にしたがって、前記極限点の位置σ（ｑ）を求めることができるように構成され、ここで、ｌLP（ｓ1，ｓ2）は、
【数１５３】
0004253190.tif 000208
によって定められた極限点重み値のベクトルであり、ここで、
【数１５４】
0004253190.tif 000209
であり、ここで、Ｓsc,Q,K,L（ｓ1（ｊ），ｓ2（ｊ））は、行列積の「ｊ」番目のレベルに対応する鋭さパラメータに対するＳsc,Q,K,Lに対応し、ここで、左辺のＳsc,Q,K,L,LP（ｓ1，ｓ2）の独立変数ｓ1とｓ2は、前記滑らかな特徴線の設定レベルにおける鋭さパラメータを示し、下付きの文字「ＬＰ」は「極限点」を示し、
【数１５５】
0004253190.tif 000210
である、請求項６７に記載のコンピュータプログラム。
【請求項６９】
前記重みベクトル生成モジュールは、多項式近似法を用いて、極限点重みベクトルｌLPの近似を生成することができるように構成されている、請求項６８に記載のコンピュータプログラム。
【請求項７０】
前記重みベクトル生成モジュールは、対称的な場合に、多項式
【数１５６】
0004253190.tif 000211
にしたがって、非対称的な場合に、多項式
【数１５７】
0004253190.tif 000212
にしたがって、極限点重みベクトルｌLPの近似を生成することができるように構成され、ここで、係数ｂijは、最小自乗法によって求められ、パラメータｓ1とｓ2の値は、選択された値にある、請求項６９に記載のコンピュータプログラム。
【請求項７１】
前記重みベクトル生成モジュールは、
【数１５８】
0004253190.tif 000213
にしたがって、ｓ1とｓ2の値を選択することができるように構成され、ここで、「Ｎ」は選択された整数であり、インデックスｉ，ｊ＝０，．．．，Ｎ−１である、請求項７０に記載のコンピュータプログラム。
【請求項７２】
前記重みベクトル生成モジュールは、点
【数１５９】
0004253190.tif 000214
を内挿するＭ次の多項式に関連して外挿近似法を用い、その後、点ｘ＝０における外挿によってこの多項式を計算して、極限点重みベクトルｌLPについての近似を生成することができるように構成されている、請求項６８に記載のコンピュータプログラム。
【請求項７３】
前記重みベクトル生成モジュールは、Ｍ＝３となるように、前記外挿近似法を行うことができるように構成されている、請求項７２に記載のコンピュータプログラム。
【請求項７４】
前記重みベクトル生成モジュールは、
【数１６０】
0004253190.tif 000215
にしたがって、極限点重みベクトル重みベクトルの近似を生成することができるように構成され、ここで、「Ｊ」は所定の整数であり、ここで、
【数１６１】
0004253190.tif 000216
であり、ここで、
【数１６２】
0004253190.tif 000217
と、
【数１６３】
0004253190.tif 000218
であり、ここで、Ｉ2K+1は「２Ｋ＋１」×「２Ｋ＋１」の単位行列であり、ここで、
【数１６４】
0004253190.tif 000219
である、請求項７３に記載のコンピュータプログラム。
【請求項７５】
前記特徴の表現は、頂点と関連づけられた、前記滑らかな特徴線に沿う接線ベクトルによって定められ、前記特徴表現生成モジュールは、
【数１６５】
0004253190.tif 000220
にしたがって、接線ベクトルｅC（ｑ）を求めることができるように構成され、ここで、ｌC（ｓ1，ｓ2）は、
【数１６６】
0004253190.tif 000221
によって定められた接線ベクトル重み値のベクトルであり、ここで、
【数１６７】
0004253190.tif 000222
であり、ベクトルｖCは、
【数１６８】
0004253190.tif 000223
として定められ、ここで、
【数１６９】
0004253190.tif 000224
であり、ここで、拡張係数ｄ（Ｋ）は、
【数１７０】
0004253190.tif 000225
によって与えられる、請求項６７に記載のコンピュータプログラム。
【請求項７６】
前記重みベクトル生成モジュールは、多項式近似法を用いて、前記接線ベクトル重みベクトルｌCを生成することができるように構成されている、請求項７５に記載のコンピュータプログラム。
【請求項７７】
前記重みベクトル生成モジュールは、反対称の場合に、多項式
【数１７１】
0004253190.tif 000226
にしたがって、非対称の場合に、多項式
【数１７２】
0004253190.tif 000227
にしたがって、接線ベクトル重みベクトルｌCの近似を生成することができるように構成され、ここで、係数ｂijは最小自乗法によって求められ、パラメータｓ1とｓ2の値は選択された値にある、請求項７６に記載のコンピュータプログラム。
【請求項７８】
前記重みベクトル生成モジュールは、
【数１７３】
0004253190.tif 000228
にしたがって、ｓ1とｓ2の値を選択することができるように構成され、ここで、「Ｎ」は選択された整数であり、インデックスｉ，ｊ＝０，．．．，Ｎ−１である、請求項７７に記載のコンピュータプログラム。
【請求項７９】
前記重みベクトル生成モジュールは、点
【数１７４】
0004253190.tif 000229
を内挿するＭ次の多項式に関連して外挿近似法を用い、その後、点ｘ＝０における外挿によってこの多項式を計算して、接線ベクトル重みベクトルｌCの近似を生成することができるように構成されている、請求項７５に記載のコンピュータプログラム。
【請求項８０】
前記重みベクトル生成モジュールは、Ｍ＝３となるように、前記外挿近似法を行うことができるように構成されている、請求項７９に記載のコンピュータプログラム。
【請求項８１】
前記重みベクトル生成モジュールは、
【数１７５】
0004253190.tif 000230
にしたがって、接線ベクトル重みベクトルｌCの近似を生成することができるように構成され、ここで、「Ｊ」は所定の整数であり、ここで、
【数１７６】
0004253190.tif 000231
であり、ここで、ベクトルｖCは、
【数１７７】
0004253190.tif 000232
によって与えられ、拡張係数ｄ（Ｋ）は、
【数１７８】
0004253190.tif 000233
によって与えられ、
【数１７９】
0004253190.tif 000234
と、
【数１８０】
0004253190.tif 000235
であり、ここで、Ｉ2K+1は「２Ｋ＋１」×「２Ｋ＋１」の単位行列であり、ここで、
【数１８１】
0004253190.tif 000236
である、請求項８０に記載のコンピュータプログラム。
【請求項８２】
前記特徴の表現は、頂点と関連づけられた、前記滑らかな特徴線を交差する接線ベクトルによって定められ、前記特徴表現生成モジュールは、
【数１８２】
0004253190.tif 000237
にしたがって、接線ベクトルｅC（ｑ）を求めることができるように構成され、ここで、ｌC（ｓ1，ｓ2）は、
【数１８３】
0004253190.tif 000238
によって定められた接線ベクトル重み値のベクトルであり、ここで、
【数１８４】
0004253190.tif 000239
であり、ベクトルｖCは、
【数１８５】
0004253190.tif 000240
として定められ、ここで、
【数１８６】
0004253190.tif 000241
であり、ここで、拡張係数ｄ（Ｋ）は、
【数１８７】
0004253190.tif 000242
によって与えられる、請求項６７に記載のコンピュータプログラム。
【請求項８３】
前記重みベクトル生成モジュールは、多項式近似法を用いて、接線ベクトル重みベクトルｌCの近似を生成することができるように構成されている、請求項８２に記載のコンピュータプログラム。
【請求項８４】
前記重みベクトル生成モジュールは、反対称の場合に、多項式
【数１８８】
0004253190.tif 000243
にしたがって、非対称の場合に、多項式
【数１８９】
0004253190.tif 000244
にしたがって、接線ベクトル重みベクトルｌSの近似を生成することができるように構成され、ここで、係数ｂijは最小自乗法によって求められ、パラメータｓ1とｓ2の値は選択された値にある、請求項８３に記載のコンピュータプログラム。
【請求項８５】
前記重みベクトル生成モジュールは、
【数１９０】
0004253190.tif 000245
にしたがって、ｓ1とｓ2の値を選択することができるように構成され、ここで、「Ｎ」は選択された整数であり、インデックスｉ，ｊ＝０，．．．，Ｎ−１である、請求項８４に記載のコンピュータプログラム。
【請求項８６】
前記重みベクトル生成モジュールは、点
【数１９１】
0004253190.tif 000246
を内挿するＭ次の多項式に関連して外挿近似法を用い、その後、点ｘ＝０における外挿によってこの多項式を計算して、接線ベクトル重みベクトルｌSの近似を生成することができるように構成されている、請求項８２に記載のコンピュータプログラム。
【請求項８７】
前記重みベクトル生成モジュールは、Ｍ＝３となるように、前記外挿近似法を行うことができるように構成されている、請求項８６に記載のコンピュータプログラム。
【請求項８８】
前記重みベクトル生成モジュールは、
【数１９２】
0004253190.tif 000247
にしたがって、極限点重みベクトルの近似を生成することができるように構成され、ここで、「Ｊ」は所定の整数であり、ここで、
【数１９３】
0004253190.tif 000248
であり、ここで、ベクトルｖSは、
【数１９４】
0004253190.tif 000249
によって与えられ、拡張係数ｄ（Ｋ）は、
【数１９５】
0004253190.tif 000250
によって与えられ、
【数１９６】
0004253190.tif 000251
と、
【数１９７】
0004253190.tif 000252
であり、ここで、Ｉ2K+1は「２Ｋ＋１」×「２Ｋ＋１」の単位行列であり、ここで、
【数１９８】
0004253190.tif 000253
である、請求項８７に記載のコンピュータプログラム。
【請求項８９】
選択されたレベルで、それぞれの辺によって複数の隣接点に連結された少なくとも１つの点を含む複数の点を有するメッシュ表現によって定められた表面内に、前記メッシュ表現の頂点と、少なくとも１つの隣接点と、該頂点と該少なくとも１つの隣接点を相互接続する辺に関連して定められた特徴の表現を生成する方法であって、
Ａ．  重みベクトル生成モジュールが少なくとも１つの重みベクトルを生成する重みベクトル生成ステップであって、複数のレベルで定められ、少なくとも１つのパラメータの値が前記メッシュの少なくとも２つのレベルで異なる値をとる、パラメータ化された細分則にもとづいて、前記少なくとも１つの重みベクトルを生成する重みベクトル生成ステップと、
Ｂ．  特徴表現生成モジュールが前記特徴の表現を生成する特徴表現生成ステップであって、前記少なくとも１つの重みベクトルと、前記頂点と前記隣接点の位置を用いて前記特徴の表現を生成する特徴表現生成ステップと、
を有し、
前記重みベクトル生成ステップは、選択された数学関数によって関連づけられた少なくとも２つのレベルにおいて異なる値をとる、前記少なくとも１つのパラメータの値を用いるステップを含み、
前記特徴は滑らかな特徴線であり、
前記滑らかな特徴線は、頂点と、２つの隣接点と、該頂点とそれぞれの該隣接点を相互接続する辺に関連して定められ、前記重みベクトル生成ステップは、前記滑らかな特徴線がそれに沿うように定められる各前記辺と関連づけられたパラメータ値を有するパラメータ化された細分則を用いるステップを含み、
前記メッシュは三角形メッシュを有し、該三角形メッシュでは、選択されたレベル「ｊ」において、頂点ｖq(０)が位置ｃj(０)にあり、隣接点ｖq(ｋ)（ｋ＝１，...，Ｋ）がそれぞれ位置ｃj(ｋ)にあり、前記重みベクトル生成ステップは、
【数２０２】
0004253190.tif 000254
のように、次のより高いレベル「ｊ＋１」における頂点ｖq(０)の位置ｃj+1(０)と、隣接点ｖq(ｋ)の位置ｃj+1(ｋ)を関連づけるパラメータ化された細分則Ｓsc,T,K,Lを用いるステップを含み、ここで、細分則Ｓsc,T,K,Lは、
【数２０３】
0004253190.tif 000255
によって与えられ、ここで、前記滑らかな特徴線は、それぞれの点ｖq(１)とｖq(Ｌ＋１)（Ｌ＋１≦Ｋ）と頂点ｖq(０)の間の辺に関連して定められ、ｓ1は点ｖq(１)と頂点ｖq(０)の間の辺と関連づけられたパラメータであり、ｓ2は点ｖq(Ｌ＋１)と頂点ｖq(０)の間の辺と関連づけられたパラメータであり、ｓ3＝(ｓ1＋ｓ2)／２であり、
【数２０４】
0004253190.tif 000256
である、方法。
【請求項９０】
前記特徴の表現は、頂点と関連づけられた少なくとも１つの極限点によって定められ、
前記特徴表現生成ステップは、
【数２０５】
0004253190.tif 000257
にしたがって、前記極限点の位置σ(ｑ)を求めるステップを含み、ここで、ｌLP(ｓ1，ｓ2)は、
【数２０６】
0004253190.tif 000258
によって定められた極限点重み値のベクトルであり、ここで、
【数２０７】
0004253190.tif 000259
であり、ここで、Ｓsc,T,K,L（ｓ1（ｊ），ｓ2（ｊ））は、行列積の「ｊ」番目のレベルに対応する鋭さパラメータに対するＳsc,T,K,Lに対応し、ここで、左辺のＳsc,T,K,L,LP（ｓ1，ｓ2）の独立変数ｓ1とｓ2は、前記滑らかな特徴線の設定レベルにおける前記鋭さパラメータを示し、下付き文字「ＬＰ」は「極限点」を示し、
【数２０８】
0004253190.tif 000260
であり、ここで、
【数２０９】
0004253190.tif 000261
である、請求項８９に記載の方法。
【請求項９１】
前記重みベクトル生成ステップは、多項式近似法を用いて、極限点重みベクトルｌLPの近似を生成するステップを含む、請求項９０に記載の方法。
【請求項９２】
前記重みベクトル生成ステップは、対称的な場合には、多項式
【数２１０】
0004253190.tif 000262
にしたがって、非対称的な場合には、多項式
【数２１１】
0004253190.tif 000263
にしたがって、極限点重みベクトルｌLPの近似を生成するステップを含み、ここで、係数ｂijは最小自乗法により求められ、パラメータｓ1とｓ2の値は選択された値にある、請求項９１に記載の方法。
【請求項９３】
前記重みベクトル生成ステップは、
【数２１２】
0004253190.tif 000264
にしたがって、ｓ1とｓ2の値を選択するステップを含み、ここで、「Ｎ」は選択された整数であり、インデックスｉ，ｊ＝０，．．．，Ｎ−１である、請求項９２に記載の方法。
【請求項９４】
前記重みベクトル生成ステップは、点
【数２１３】
0004253190.tif 000265
を内挿するＭ次の多項式に関連して外挿近似法を用い、その後、点ｘ＝０における外挿によってこの多項式を計算して、極限点重みベクトルｌLPの近似を生成するステップを含む、請求項９０に記載の方法。
【請求項９５】
前記重みベクトル生成ステップは、Ｍ＝３となるように、前記外挿近似法を行うステップを含む、請求項９４に記載の方法。
【請求項９６】
前記重みベクトル生成ステップは、
【数２１４】
0004253190.tif 000266
にしたがって、前記極限点重みベクトルの近似を生成するステップを含み、ここで、「Ｊ」は所定の整数であり、ここで、
【数２１５】
0004253190.tif 000267
であり、ここで、
【数２１６】
0004253190.tif 000268
と、
【数２１７】
0004253190.tif 000269
であり、ここで、ＩK+1は「Ｋ＋１」×「Ｋ＋１」の単位行列であり、ここで、
【数２１８】
0004253190.tif 000270
である、請求項９５に記載の方法。
【請求項９７】
前記特徴の表現は、頂点と関連づけられた、前記滑らかな特徴線に沿う接線ベクトルによって定められ、前記特徴表現生成ステップは、
【数２１９】
0004253190.tif 000271
にしたがって、接線ベクトルｅC（ｑ）を求めるステップを含み、ここで、ｌC（ｓ1，ｓ2）は、
【数２２０】
0004253190.tif 000272
によって定められた接線ベクトル重み値のベクトルであり、ここで、
【数２２１】
0004253190.tif 000273
すなわち、ユークリッド・ノルムであり、ここで、
【数２２２】
0004253190.tif 000274
であり、ここで、右辺の行ベクトルの２つのゼロでない成分が、行ベクトル中の位置「１」における「１」であり、位置Ｋ／２＋１における「負の１」であり、ここで、Ｓsc,T,K,L（ｓ1（ｊ），ｓ2（ｊ））は、行列積の「ｊ」番目のレベルに対応する鋭さパラメータに対するＳsc,T,K,Lに対応する、請求項８９に記載の方法。
【請求項９８】
前記重みベクトル生成ステップは、多項式近似法を用いて、接線ベクトル重みベクトルｌCを生成するステップを含む、請求項９７に記載の方法。
【請求項９９】
前記重みベクトル生成ステップは、反対称の場合に、多項式
【数２２３】
0004253190.tif 000275
にしたがって、非対称の場合に、多項式
【数２２４】
0004253190.tif 000276
にしたがって、接線ベクトル重みベクトルｌCの近似を生成するステップを含み、ここで、係数ｂijは最小自乗法によって求められ、パラメータｓ1とｓ2の値は選択された値にある、請求項９８に記載の方法。
【請求項１００】
前記重みベクトル生成ステップは、
【数２２５】
0004253190.tif 000277
にしたがって、ｓ1とｓ2の値を選択するステップを含み、ここで、「Ｎ」は選択された整数であり、インデックスｉ，ｊ＝０，．．．，Ｎ−１である、請求項９９に記載の方法。
【請求項１０１】
前記重みベクトル生成ステップは、点
【数２２６】
0004253190.tif 000278
を内挿するＭ次の多項式に関連して外挿近似法を用い、その後、点ｘ＝０における外挿によってこの多項式を計算して、接線ベクトル重みベクトルｌCの近似を生成するステップを含む、請求項９７に記載の方法。
【請求項１０２】
前記重みベクトル生成ステップは、Ｍ＝３となるように、前記外挿近似法を行うステップを含む、請求項１０１に記載の方法。
【請求項１０３】
前記重みベクトル生成ステップは、
【数２２７】
0004253190.tif 000279
にしたがって、接線ベクトル重みベクトルｌCの近似を生成するステップを含み、ここで、「Ｊ」は所定の整数であり、ここで、
【数２２８】
0004253190.tif 000280
であり、ここで、ベクトルｖCは、
【数２２９】
0004253190.tif 000281
によって与えられ、拡張係数ｄ（Ｋ）は、
【数２３０】
0004253190.tif 000282
によって与えられ、
【数２３１】
0004253190.tif 000283
と、
【数２３２】
0004253190.tif 000284
であり、ここで、ＩK+1は「Ｋ＋１」×「Ｋ＋１」の単位行列であり、ここで、
【数２３３】
0004253190.tif 000285
である、請求項１０２に記載の方法。
【請求項１０４】
前記特徴の表現は、頂点と関連づけられた、前記滑らかな特徴線と交差する接線ベクトルによって定められ、前記特徴表現生成ステップは、
【数２３４】
0004253190.tif 000286
にしたがって、接線ベクトルｅC（ｑ）を求めるステップを含み、ここで、ｌS（ｓ1，ｓ2）は、
【数２３５】
0004253190.tif 000287
によって定められた接線ベクトル重み値のベクトルであり、ここで、
【数２３６】
0004253190.tif 000288
すなわち、ユークリッド・ノルムであり、ここで、
【数２３７】
0004253190.tif 000289
であり、ここで、Ｓsc,T,K,L（ｓ1（ｊ），ｓ2（ｊ））は、行列積の「ｊ」番目のレベルに対応する鋭さパラメータに対するＳsc,T,K,Lに対応する、請求項８９に記載の方法。
【請求項１０５】
前記重みベクトル生成ステップは、多項式近似法を用いて、接線ベクトル重みベクトルｌCを生成するステップを含む、請求項１０４に記載の方法。
【請求項１０６】
前記重みベクトル生成ステップは、反対称の場合に、多項式
【数２３８】
0004253190.tif 000290
にしたがって、非対称の場合に、多項式
【数２３９】
0004253190.tif 000291
にしたがって、接線ベクトル重みベクトルｌSの近似を生成するステップを含み、ここで、係数ｂijは、最小自乗法によって求められ、パラメータｓ1とｓ2の値は、選択された値にある、請求項１０５に記載の方法。
【請求項１０７】
前記重みベクトル生成ステップは、
【数２４０】
0004253190.tif 000292
にしたがって、ｓ1とｓ2の値を選択するステップを含み、ここで、「Ｎ」は選択された整数であり、インデックスｉ，ｊ＝０，．．．，Ｎ−１である、請求項１０６に記載の方法。
【請求項１０８】
前記重みベクトル生成ステップは、点
【数２４１】
0004253190.tif 000293
を内挿するＭ次の多項式に関連して外挿近似法を用い、その後、点ｘ＝０における外挿によってこの多項式を計算して、接線ベクトル重みベクトルｌSの近似を生成するステップを含む、請求項１０３に記載の方法。
【請求項１０９】
前記重みベクトル生成ステップは、Ｍ＝３となるように、前記外挿近似法を行うステップを含む、請求項１０８に記載の方法。
【請求項１１０】
前記重みベクトル生成ステップは、
【数２４２】
0004253190.tif 000294
にしたがって、極限点重みベクトルの近似を生成するステップを含み、ここで、「Ｊ」は所定の整数であり、ここで、
【数２４３】
0004253190.tif 000295
であり、ここで、ベクトルｖSは、
【数２４４】
0004253190.tif 000296
によって与えられ、拡張係数ｄ（Ｋ）は、
【数２４５】
0004253190.tif 000297
によって与えられ、
【数２４６】
0004253190.tif 000298
と、
【数２４７】
0004253190.tif 000299
であり、ここで、ＩK+1は「Ｋ＋１」×「Ｋ＋１」の単位行列であり、ここで、
【数２４８】
0004253190.tif 000300
である、請求項１０９に記載の方法。
【請求項１１１】
選択されたレベルで、それぞれの辺によって複数の隣接点に連結された少なくとも１つの点を含む複数の点を有するメッシュ表現によって定められた表面内に、前記メッシュ表現の頂点と、少なくとも１つの隣接点と、該頂点と該少なくとも１つの隣接点を相互接続する辺に関連して定められた特徴の表現を生成する方法であって、
Ａ．  重みベクトル生成モジュールが少なくとも１つの重みベクトルを生成する重みベクトル生成ステップであって、複数のレベルで定められ、少なくとも１つのパラメータの値が前記メッシュの少なくとも２つのレベルで異なる値をとる、パラメータ化された細分則にもとづいて、前記少なくとも１つの重みベクトルを生成する重みベクトル生成ステップと、
Ｂ．  特徴表現生成モジュールが前記特徴の表現を生成する特徴表現生成ステップであって、前記少なくとも１つの重みベクトルと、前記頂点と前記隣接点の位置を用いて前記特徴の表現を生成する特徴表現生成ステップと、
を有し、
前記重みベクトル生成ステップは、選択された数学関数によって関連づけられた少なくとも２つのレベルにおいて異なる値をとる、前記少なくとも１つのパラメータの値を用いるステップを含み、
前記特徴は滑らかな特徴線であり、
前記滑らかな特徴線は、頂点と、２つの隣接点と、該頂点とそれぞれの該隣接点を相互接続する辺に関連して定められ、前記重みベクトル生成ステップは、前記滑らかな特徴線がそれに沿うように定められる各前記辺と関連づけられたパラメータ値を有するパラメータ化された細分則を用いるステップを含み、
前記メッシュは四辺形メッシュを有し、この四辺形メッシュでは、選択されたレベル「ｊ」において、頂点ｖq（０）が位置ｃj（０）にあり、隣接点ｖq（ｋ）（ｋ＝１，．．．，２Ｋ）がそれぞれの位置ｃj（ｋ）にあり、前記重みベクトル生成ステップは、
【数２４９】
0004253190.tif 000301
のように、次のより高いレベル「ｊ＋１」における頂点ｖq（０）の位置ｃj+1（０）と隣接点ｖq（ｋ）の位置ｃj+1（ｋ）を関連づけるパラメータ化された細分則Ｓsc,Q,K,Lを用いるステップを含み、ここで、細分則Ｓsc,Q,K,Lは、
【数２５０】
0004253190.tif 000302
によって与えられ、ここで、前記滑らかな特徴線は、それぞれの点ｖq（１）とｖq（Ｌ＋１）（Ｌ＋１≦２Ｋ）と頂点ｖq（０）の間の辺と関連して定められ、ｓ1は点ｖq（１）と頂点ｖq（０）の間の辺と関連づけられたパラメータであり、ｓ2は点ｖq（Ｌ＋１）と頂点ｖq（０）の間の辺と関連づけられたパラメータであり、ｓ3＝（ｓ1＋ｓ2）／２である、方法。
【請求項１１２】
前記特徴の表現は、頂点と関連づけられた少なくとも１つの極限点によって定められ、
前記特徴表現生成ステップは、
【数２５１】
0004253190.tif 000303
にしたがって、前記極限点の位置σ（ｑ）を求めるステップを含み、ここで、ｌLP（ｓ1，ｓ2）は、
【数２５２】
0004253190.tif 000304
によって定められた極限点重み値のベクトルであり、ここで、
【数２５３】
0004253190.tif 000305
であり、ここで、Ｓsc,Q,K,L（ｓ1（ｊ），ｓ2（ｊ））は、行列積の「ｊ」番目のレベルに対応する鋭さパラメータに対するＳsc,Q,K,Lに対応し、ここで、左辺のＳsc,Q,K,L,LP（ｓ1，ｓ2）の独立変数ｓ1とｓ2は、前記滑らかな特徴線の設定レベルにおける鋭さパラメータを示し、下付きの文字「ＬＰ」は「極限点」を示し、
【数２５４】
0004253190.tif 000306
である、請求項１１１に記載の方法。
【請求項１１３】
前記重みベクトル生成ステップは、多項式近似法を用いて、極限点重みベクトルｌLPの近似を生成するステップを含む、請求項１１２に記載の方法。
【請求項１１４】
前記重みベクトル生成ステップは、対称的な場合に、多項式
【数２５５】
0004253190.tif 000307
にしたがって、非対称的な場合に、多項式
【数２５６】
0004253190.tif 000308
にしたがって、極限点重みベクトルｌLPの近似を生成するステップを含み、ここで、係数ｂijは、最小自乗法によって求められ、パラメータｓ1とｓ2の値は、選択された値にある、請求項１１３に記載の方法。
【請求項１１５】
前記重みベクトル生成ステップは、
【数２５７】
0004253190.tif 000309
にしたがって、ｓ1とｓ2の値を選択するステップを含み、ここで、「Ｎ」は選択された整数であり、インデックスｉ，ｊ＝０，．．．，Ｎ−１である、請求項１１４に記載の方法。
【請求項１１６】
前記重みベクトル生成ステップは、点
【数２５８】
0004253190.tif 000310
を内挿するＭ次の多項式に関連して外挿近似法を用い、その後、点ｘ＝０における外挿によってこの多項式を計算して、極限点重みベクトルｌLPについての近似を生成するステップを含む、請求項１１０に記載の方法。
【請求項１１７】
前記重みベクトル生成ステップは、Ｍ＝３となるように、前記外挿近似法を行うステップを含む、請求項１１６に記載の方法。
【請求項１１８】
前記重みベクトル生成ステップは、
【数２５９】
0004253190.tif 000311
にしたがって、極限点重みベクトル重みベクトルの近似を生成するステップを含み、ここで、「Ｊ」は所定の整数であり、ここで、
【数２６０】
0004253190.tif 000312
であり、ここで、
【数２６１】
0004253190.tif 000313
と、
【数２６２】
0004253190.tif 000314
であり、ここで、Ｉ2K+1は「２Ｋ＋１」×「２Ｋ＋１」の単位行列であり、ここで、
【数２６３】
0004253190.tif 000315
である、請求項１１７に記載の方法。
【請求項１１９】
前記特徴の表現は、頂点と関連づけられた、前記滑らかな特徴線に沿う接線ベクトルによって定められ、前記特徴表現生成ステップは、
【数２６４】
0004253190.tif 000316
にしたがって、接線ベクトルｅC（ｑ）を求めるステップを含み、ここで、ｌC（ｓ1，ｓ2）は、
【数２６５】
0004253190.tif 000317
によって定められた接線ベクトル重み値のベクトルであり、ここで、
【数２６６】
0004253190.tif 000318
であり、ベクトルｖCは、
【数２６７】
0004253190.tif 000319
として定められ、ここで、
【数２６８】
0004253190.tif 000320
であり、ここで、拡張係数ｄ（Ｋ）は、
【数２６９】
0004253190.tif 000321
によって与えられる、請求項１１１に記載の方法。
【請求項１２０】
前記重みベクトル生成ステップは、多項式近似法を用いて、前記接線ベクトル重みベクトルｌCを生成するステップを含む、請求項１１９に記載の方法。
【請求項１２１】
前記重みベクトル生成ステップは、反対称の場合に、多項式
【数２７０】
0004253190.tif 000322
にしたがって、非対称の場合に、多項式
【数２７１】
0004253190.tif 000323
にしたがって、接線ベクトル重みベクトルｌCの近似を生成するステップを含み、ここで、係数ｂijは最小自乗法によって求められ、パラメータｓ1とｓ2の値は選択された値にある、請求項１２０に記載の方法。
【請求項１２２】
前記重みベクトル生成ステップは、
【数２７２】
0004253190.tif 000324
にしたがって、ｓ1とｓ2の値を選択するステップを含み、ここで、「Ｎ」は選択された整数であり、インデックスｉ，ｊ＝０，．．．，Ｎ−１である、請求項１２１に記載の方法。
【請求項１２３】
前記重みベクトル生成ステップは、点
【数２７３】
0004253190.tif 000325
を内挿するＭ次の多項式に関連して外挿近似法を用い、その後、点ｘ＝０における外挿によってこの多項式を計算して、接線ベクトル重みベクトルｌCの近似を生成するステップを含む、請求項１１９に記載の方法。
【請求項１２４】
前記重みベクトル生成ステップは、Ｍ＝３となるように、前記外挿近似法を行うステップを含む、請求項１２３に記載の方法。
【請求項１２５】
前記重みベクトル生成ステップは、
【数２７４】
0004253190.tif 000326
にしたがって、接線ベクトル重みベクトルｌCの近似を生成するステップを含み、ここで、「Ｊ」は所定の整数であり、ここで、
【数２７５】
0004253190.tif 000327
であり、ここで、ベクトルｖCは、
【数２７６】
0004253190.tif 000328
によって与えられ、拡張係数ｄ（Ｋ）は、
【数２７７】
0004253190.tif 000329
によって与えられ、
【数２７８】
0004253190.tif 000330
と、
【数２７９】
0004253190.tif 000331
であり、ここで、Ｉ2K+1は「２Ｋ＋１」×「２Ｋ＋１」の単位行列であり、ここで、
【数２８０】
0004253190.tif 000332
である、請求項１２４に記載の方法。
【請求項１２６】
前記特徴の表現は、頂点と関連づけられた、前記滑らかな特徴線を交差する接線ベクトルによって定められ、前記特徴表現生成ステップは、
【数２８１】
0004253190.tif 000333
にしたがって、接線ベクトルｅC（ｑ）を求めるステップを含み、ここで、ｌC（ｓ1，ｓ2）は、
【数２８２】
0004253190.tif 000334
によって定められた接線ベクトル重み値のベクトルであり、ここで、
【数２８３】
0004253190.tif 000335
であり、ベクトルｖCは、
【数２８４】
0004253190.tif 000336
として定められ、ここで、
【数２８５】
0004253190.tif 000337
であり、ここで、拡張係数ｄ（Ｋ）は、
【数２８６】
0004253190.tif 000338
によって与えられる、請求項１１１に記載の方法。
【請求項１２７】
前記重みベクトル生成ステップは、多項式近似法を用いて、接線ベクトル重みベクトルｌCの近似を生成するステップを含む、請求項１２６に記載の方法。
【請求項１２８】
前記重みベクトル生成ステップは、反対称の場合に、多項式
【数２８７】
0004253190.tif 000339
にしたがって、非対称の場合に、多項式
【数２８８】
0004253190.tif 000340
にしたがって、接線ベクトル重みベクトルｌSの近似を生成するステップを含み、ここで、係数ｂijは最小自乗法によって求められ、パラメータｓ1とｓ2の値は選択された値にある、請求項１２７に記載の方法。
【請求項１２９】
前記重みベクトル生成ステップは、
【数２８９】
0004253190.tif 000341
にしたがって、ｓ1とｓ2の値を選択するステップを含み、ここで、「Ｎ」は選択された整数であり、インデックスｉ，ｊ＝０，．．．，Ｎ−１である、請求項１２８に記載の方法。
【請求項１３０】
前記重みベクトル生成ステップは、点
【数２９０】
0004253190.tif 000342
を内挿するＭ次の多項式に関連して外挿近似法を用い、その後、点ｘ＝０における外挿によってこの多項式を計算して、接線ベクトル重みベクトルｌSの近似を生成するステップを含む、請求項１２６に記載の方法。
【請求項１３１】
前記重みベクトル生成ステップは、Ｍ＝３となるように、前記外挿近似法を行うステップを含む、請求項１３０に記載の方法。
【請求項１３２】
前記重みベクトル生成ステップは、
【数２９１】
0004253190.tif 000343
にしたがって、極限点重みベクトルの近似を生成するステップを含み、ここで、「Ｊ」は所定の整数であり、ここで、
【数２９２】
0004253190.tif 000344
であり、ここで、ベクトルｖSは、
【数２９３】
0004253190.tif 000345
によって与えられ、拡張係数ｄ（Ｋ）は、
【数２９４】
0004253190.tif 000346
によって与えられ、
【数２９５】
0004253190.tif 000347
と、
【数２９６】
0004253190.tif 000348
であり、ここで、Ｉ2K+1は「２Ｋ＋１」×「２Ｋ＋１」の単位行列であり、ここで、
【数２９７】
0004253190.tif 000349
である、請求項１３１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全般的にコンピュータ・グラフィックスの分野に関し、特に、物体の表面を表現する細分表面上の滑らかな特徴線の生成に関する。
【背景技術】
【０００２】
一般に、コンピュータ・グラフィックスでは、物体は、特定のレベルのメッシュによって表現される表面として表現される。特定のレベルのメッシュは、辺により連結されている、三次元空間の１組の頂点または点からなる。辺は、三角形、四辺形などの形をとる多角形面を定める。あるコンピュータ・グラフィックスの操作では、現在の表現よりも高い解像度で表面の表現を生成することが望まれる。四辺形のメッシュによって定められる表面と関連して用いられるＣａｔｍｕｌｌ−Ｃｌａｒｋ表面細分法と、三角形のメッシュによって定められる表面と関連して用いられるＬｏｏｐ表面細分法を含め、現在の表現よりも高い解像度で表面の表現を生成するいくつかの一般的な方法が存在する。一般に、双方の方法は、次のより高い細分度のメッシュを生成するために、メッシュの特定のレベルで表面を定めるそれぞれの頂点において、それぞれの細分則を用いる。「細分表面」または「極限表面」と呼ばれるそれぞれの物体の表面は、細分度が無限大になったときに、メッシュによって定められるものとして理解される。
【０００３】
ある細分表面の特徴は、それぞれの表面を定めるメッシュ内の特徴線によって、定めることができる。特徴線は、鋭い折り目または滑らかな曲りの形をとりうる。滑らかな特徴線の場合、表面に接する平面に垂直なベクトルである法線ベクトルは、滑らかな特徴線を横切って連続的に変化する。他方、鋭い折り目の場合、法線ベクトルは、折り目を横切って不連続に変化し、実際、その折り目のところでは定義されない。しかしながら、滑らかな曲りの定義は、特定の細分度におけるメッシュ内の頂点を横切る曲りの鋭さを定めるために用いられる１つまたは複数のパラメータを用いて、鋭い折り目の定義から得ることができる。カリフォルニア州パサデナのカリフォルニア工科大学における１９９８年のＤ．Ｚｏｒｉｎによる博士論文「静的細分および多重解像度表面表現（Ｓｔａｔｉｏｎａｒｙ Ｓｕｂｄｉｖｉｓｉｏｎ Ａｎｄ Ｍｕｌｔｉ−Ｒｅｓｏｌｕｔｉｏｎ Ｓｕｒｆａｃｅ Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ）」は、パラメータを用いて、滑らかな特徴線を生成する方法を説明しているが、そこで説明されている方法では、表面のトポロジーのいくつかの頂点において滑らかでない表面でさえ、比較的質の低い表面になってしまう。ＡＣＭ ＳＩＧＧＲＡＰＨ １９９８におけるＳＩＧＧＲＡＰＨ９８会議議事録、会議年報集、８５から９４ページのＴ．ＤｅＲｏｓｅらの「キャラクタ・アニメーションにおける細分表面（Ｓｕｂｄｉｖｉｓｉｏｎ ｓｕｒｆａｃｅｓ ｉｎ ｃｈａｒａｃｔｏｒ ａｎｉｍａｔｉｏｎ）」は、ＡＣＭ ＳＩＧＧＲＡＰＨ １９９４におけるＳＩＧＧＲＡＰＨ ９４ 会議議事録、会議年報集のＨ．Ｈｏｐｐｅらの「小片円滑表面再構成（Ｐｉｅｃｅｗｉｓｅ Ｓｍｏｏｔｈ Ｓｕｒｆａｃｅ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ）」で説明されているように、鋭い折り目に対応する細分則を、選択された緻密度に至るまで適用し、その後、滑らかな内部点に対応する規則を適用することによって、滑らかな特徴線を生ずる方法を説明している。明確に異なる２つの種類の規則を適用することによって、その結果として得られる表面の効率的な評価が困難になる。
【発明の開示】
【０００４】
本発明は、細分表面内に滑らかな特徴線を生成する新規かつ改良されたシステムと方法を提供する。
【０００５】
簡単に要約すれば、本発明は、選択されたレベルにおいて、それぞれの辺によって複数の隣接点に連結された少なくとも１つの点を含む複数の点を有するメッシュ表現によって定められた表面内に、メッシュ表現内の頂点と、少なくとも１つの隣接点と、この頂点とこの少なくとも１つの隣接点を相互接続する辺と関連して定められる特徴の表現を生成するシステムを提供する。この特徴生成システムは、重みベクトル生成モジュールと、特徴表現生成モジュールを有する。重みベクトル生成モジュールは、複数のレベルで定められ、少なくとも１つのパラメータの値が、メッシュの少なくとも２つのレベルにおいて異なる値をとるパラメータ化された細分則にもとづいて、少なくとも１つの重みベクトルを生成するように構成される。特徴表現生成モジュールは、特徴の表現を生成するために、少なくとも１つの重みベクトルと、頂点およびその隣接点の位置を用いるように構成されている。
【０００６】
本発明の一実施態様は、細分表面内に滑らかな特徴線を生成するシステムを有する。
【０００７】
本発明は、添付されている特許請求の範囲において、特徴が指摘される。本発明の上記の利点およびその他の利点は、添付の図面と関連して行われる以下の説明を参照することによって、より良く理解できるであろう。
【発明を実施するための最良の形態】
【０００８】
図１は、本発明にしたがって構成された、細分表面と関連して滑らかな特徴線を生成するシステムを含むコンピュータ・グラフィックス・システム１０を示す。図１を参照すると、コンピュータ・グラフィックス・システムは、プロセッサ・モジュール１１と、１つまたは複数のオペレータ入力装置１２と、１つまたは複数の表示装置１３を含む。表示装置１３は、オペレータに対して、テキストおよび／または画像の形で表示スクリーン上に情報を表示するフレーム・バッファとビデオ表示端末のようなものを通常有する。コンピュータ・グラフィックス・システム１０のオペレータ入力装置１２は、ディジタル化タブレット１５とともに通常用いられるペン１４と、トラックボールまたはマウス装置１６を通常含む。一般に、ペン１４とディジタル化タブレットは、オペレータによって、いくつかのモードで用いられる。１つのモードでは、ペン１４とディジタル化タブレットは、コンピュータ・グラフィック・システムに、更新された明暗情報を出力するために用いられる。他のモードでは、ペンとディジタル化タブレットは、例えば、表面トリミングや他の情報のための線引きのような通常のコンピュータ・グラフィックス情報を、コンピュータ・グラフィックス・システム１０に入力し、これにより、システム１０が通常のコンピュータ・グラフィックス操作を行えるようにするために、オペレータによって用いられる。トラックボールまたはマウス装置１６は、オペレータが、ペンとディジタル化タブレットで入力できる、画面上の特定の点まで、スクリーンの上でカーソルまたはポインタを動かすために用いることができる。コンピュータ・グラフィックス・システム１０は、オペレータがシステム１０にテキスト入力を行うために用いることができるキーボード（不図示）もまた含めてもよい。
【０００９】
プロセッサ・モジュール１１は、１つまたは複数のマイクロプロセッサの形をとるプロセッサと、主メモリを一般に含み、１つまたは複数のディスク記憶装置を含む大容量記憶サブシステムを一般に含むだろう。メモリとディスク記憶装置は、プロセッサによって処理されるデータとプログラム（まとめて「情報」とする）を一般に保存し、プロセッサによって生成された処理データを保存する。プロセッサ・モジュールは、オペレータ入力装置１２と表示装置１３への接続を含み、オペレータ入力装置１２を介してオペレータによって入力された情報を受け取り、その入力情報を処理し、処理された情報をメモリおよび／または大容量記憶サブシステムに保存する。さらに、プロセッサ・モジュールは、メモリとディスク記憶装置から得た情報と、それによって生成された処理データの一部を形成するビデオ表示情報を、オペレータへの表示を行う表示装置に出力できる。プロセッサ・モジュール１１は、ハードコピー出力の生成を容易にするプリンタのようなハードコピー出力装置への接続（不図示）と、システム１０を、情報の転送を容易にする公衆電話システムおよび／またはコンピュータネットワークのようなものに接続するモデムおよび／またはネットワーク・インタフェース（これも不図示）もまた含んでいてもよい。
【００１０】
本発明は、三次元の細分表面内に滑らかな特徴線を生成するシステムを提供する。細分表面は、三次元のメッシュを形成するために、辺によって相互接続された制御点によって定められる。一般に、細分表面は、まず、特定の粗さまたは細かさのメッシュによって定められる。いくつかの方法のうちの１つを用いて、メッシュは、細分度が向上する一連のレベルを通して緻密にされ、細分表面は、細分度が無限に達すると極限になる。以下では、各メッシュレベルはインデックスで特定され、あるメッシュレベルがインデックス「ｊ」によって特定されると、次のより高い細分度のメッシュはインデックス「ｊ＋１」で特定される。細分表面は、細分度が無限大になるにつれてほぼ制御点になる、表面の「極限点」の位置と、関連する法線ベクトルの向きによってほぼ定められる。各法線ベクトルは、細分表面上のそれぞれの点における接面の向きを定め、それぞれの点において細分表面に接するベクトルの交差積によって定めることができる。
【００１１】
滑らかな特徴線生成システムによって行われる動作を説明する前に、このシステムで用いられる２つの表面細分法、すなわち、前記Ｌｏｏｐ表面細分法とＣａｔｍｕｌｌ‐Ｃｌａｒｋ表面細分法を説明するのは有益であろう。
【００１２】
Ｌｏｏｐ表面細分法を、図２および図３と関連して説明する。図２は、メッシュによった定められた表面の例と、それから得られた細分表面の一部を示し、図３は、この表面細分法を理解するのに有用なステンシルを示す。一般に、Ｌｏｏｐの表面細分法では、元のメッシュ中の各三角形の面は、次のより高い細分度のメッシュを定める複数の副面に分割される。次のより高い細分度のメッシュの頂点は、元のメッシュ内の頂点の位置の重み平均を用いて配置される。さらに詳しくいえば、図２を参照すると、位置ｃj（ｑ）に配置されている頂点ｖq（頂点ｖq＝ｖq（０））と、それぞれの位置ｃj（１）からｃj（Ｋ）における位置に配置されている複数すなわち「Ｋ」個の周囲の点ｖq（１）からｖq（Ｋ）（一般に、ｖq（ｋ））２１（１）から２１（Ｋ）（一般に参照番号２１（ｋ）によって特定されている）を含む、「ｊ」細分度におけるメッシュ２０が示されている。点ｖq（ｋ）２１（ｋ）は、辺によって頂点ｖqに接続されている、メッシュ２０内の点である。（頂点ｖqに接続されている点の数「Ｋ」のことをときどき頂点の「価数」と呼ぶことがある。）図３に示されているステンシルは、それぞれの頂点ｖqを囲んでいる点についてのインデックス「ｋ」の順序付けを理解するのに有用である。頂点ｖqに接続されている、メッシュ内の点ｖq（ｋ）のインデックスのセットをＮ（ｑ，ｊ）で示すと、次のより高い細分度「ｊ＋１」におけるメッシュは、位置ｃj+1（ｑ）に配置されている頂点ｖ′q２２（０）と、位置ｃj+1（ｌ）に配置され、頂点ｖ′q２２（０）に接続されている一群の周囲の点ｖ′q（ｌ）２２（ｌ）に対応する。より高い細分度のメッシュは、
【００１３】
【数１】
0004253190.tif 000002
【００１４】
によって求められる位置ｃj+1（ｑ）における頂点ｖ′q２２（０）と、
【００１５】
【数２】
0004253190.tif 000003
【００１６】
によって求められる位置ｃj+1（ｌ）における点ｖ′q（ｌ）２２（ｌ）を生成することによって構成される。ここで、重み付け因子ａ（Ｋ）は、
【００１７】
【数３】
0004253190.tif 000004
【００１８】
によって与えられる。式（１）と（２）は、次のように、細分行列ＳT,K（ここで、インデックス「Ｔ」は「三角形」を指す）を用いて、細分則を定める単一の式にまとめることができる。
【００１９】
【数４】
0004253190.tif 000005
【００２０】
これは成分ごとに、
【００２１】
【数５】
0004253190.tif 000006
【００２２】
として書くことができる。ここで、
【００２３】
【数６】
0004253190.tif 000007
【００２４】
であり、ここで、インデックス「ｌ」と「ｍ」は「０」から「Ｋ」までの範囲にあり、「Ｋ」を含む。
【００２５】
式（１）と（２）、または、同等な式（４）から（６）は、細分度「ｊ＋１」におけるメッシュに点を生成するために、細分度「ｊ」におけるメッシュ内の各点を頂点として選択することによって適用される。Ｌｏｏｐの表面細分法は、所望の細分度のメッシュを生成するために繰り返し適用される。式（２）は、この方法が頂点として点ｖq２１（０）に適用されたときに形成される点ｖ′q（ｌ）２２（ｌ）が、この方法が頂点として点ｖq（ｋ）２１（ｋ）に適用されたときに同じ位置になることを定めることが分かるであろう。
【００２６】
Ｌｏｏｐ表面細分法は、「ｊ＋１」レベルのメッシュを形成するために相互接続された、
（ｉ）レベル「ｊ」のメッシュ内の各点対に対する、および、一般に各点対の間のどこかの、次のより高い（「ｊ＋１」）細分度のメッシュ内の位置ｃj+1（ｌ）における１つの新しい点（上で説明した点ｖ′q（ｌ）を参照）と、
（ｉｉ）「ｊ」レベルのメッシュ内の各点に対する、および、一般に各点にいくらか近くの、「ｊ＋１」レベルのメッシュ内の位置ｃj+1（ｑ）における再配置された点（上で説明した頂点ｖ′qを参照）を生成することがわかるだろう。
【００２７】
Ｃａｔｍｕｌｌ‐Ｃｌａｒｋ細分法は、少数の隣接頂点を用いて滑らかな表面を生成する。Ｃａｔｍｕｌｌ‐Ｃｌａｒｋ表面細分法を、図４Ａから図４Ｅおよび図５と関連して説明する。図４Ａは、メッシュによって定められた表面の一例を示し、図４Ｂから図４Ｅは、図４Ａに示されている表面から得られる細分表面を生成するのに行われる操作を理解するのに有用である。図５は、表面細分法を理解するのに有用なステンシルを示しており、特に、この表面細分法が実行される頂点ｖq（頂点ｖq＝ｖq（０））を囲む点に対するインデックス「ｋ」の順序付けを理解するのに有用である。図４Ａを参照すると、この図は、４つの四辺形３１（１）から３１（４）からなるメッシュ３０を示している。各四辺形を面と呼ぶ。四辺形は、四辺形３１（１）から３１（４）のすべてに共通である点３２（０）と、他の点３２（１）から３２（８）によって定められている。一般に、Ｃａｔｍｕｌｌ‐Ｃｌａｒｋ表面細分法は、
（ｉ）各面に対して、面点３３（１）から３３（４）が、それぞれの面を定める点３２（ｐ）の平均として生成される面点生成ルーチン（図４Ｂを参照）と、
（ｉｉ）各辺に対して、新しい辺点３４（１）から３４（４）が、面の２つの新しい面点が隣接している元の辺の中間点の平均として生成される辺点生成ルーチン（図４Ｃを参照。面点生成ルーチンの間に生成された面点が白抜きの円として示されている）と、
（ｉｉｉ）頂点点３５が、元の頂点点に隣接する面に対してルーチン（ｉ）で生成された新しい面点の位置と、元の頂点点に入射する元の辺の中間点の位置と、元の頂点点の位置と、元の頂点点の価数に関連して生成される頂点点ルーチン（図４Ｄを参照。面点と辺点生成ルーチンの間に生成された面点および辺点が白抜きの円として示されている）と、
（ｉｖ）
（ａ）各新しい面点は、元の面を定める辺の辺点に接続され、
（ｂ）各新しい頂点点は、元の頂点点に入射する全ての元の辺の新しい辺点に接続されるメッシュ接続ステップ（図４Ｅを参照）を含めた一連のルーチンで実行される。
【００２８】
さらに詳しくいえば、Ｃａｔｍｕｌｌ‐Ｃｌａｒｋ細分法では、場所ｃj（ｑ）における頂点ｖqに対して、
（ｉ）Ｎe（ｑ，ｊ）によって、それに接続されている１次の隣接点ｃj（ｌ）（たとえば、点３２（０）に対して、点３２（２）と点３２（８））のインデックスのセットと、
（ｉｉ）Ｎf（ｑ，ｊ）によって、頂点ｃj（ｑ）と関連するレベル「ｊ」の面に関して、頂点ｃj（ｑ）の向かい側にある２次の隣接点（たとえば、点３２（０）に対して、点３２（１））のインデックスのセットを示して、次のより高い細分度「ｊ＋１」におけるメッシュが次のようにして形成される。面点生成ルーチンでは、面点は、次のようにして求められた位置ｃj+1（ｍi）において生成され、配置される。
【００２９】
【数７】
0004253190.tif 000008
【００３０】
辺点生成ルーチンでは、辺点は、次のようにして求められた位置ｃj+1（ｌi）において生成され、配置される。
【００３１】
【数８】
0004253190.tif 000009
【００３２】
頂点点生成ルーチンでは、新しい頂点点は、次のようにして求められた位置において生成され、配置される。
【００３３】
【数９】
0004253190.tif 000010
【００３４】
点ｃjのみで表わすという観点から、式（９）の最後の項を置換すると、
【００３５】
【数１０】
0004253190.tif 000011
【００３６】
一般に、四辺形のメッシュに対しては、このシステムは、式（９）のＫ＝３の場合を除いて、Ｃａｔｍｕｌｌ‐Ｃｌａｒｋ細分法を用いる。この場合、このシステムは、
【００３７】
【数１１】
0004253190.tif 000012
【００３８】
を用いる。ここで、γ＝３／３８である。式（１１）は、Ｋ＝３に対して、γ＝１／１２のかわりにγ＝３／３８であることを除き、γ＝１／４ＫであるＣａｔｍｕｌｌ‐Ｃｌａｒｋ細分法（式（９））に対応する。点ｃjのみで表わすという観点から（式（１０）と比較されたい）、
【００３９】
【数１２】
0004253190.tif 000013
【００４０】
である。これらの式は、細分行列ＳQ,K（ここで、インデックス「Ｑ」は「四辺形」を示す）を用いて細分則を定める単一の式によって、次のようにまとめることができる。
【００４１】
【数１３】
0004253190.tif 000014
【００４２】
これは、
【００４３】
【数１４】
0004253190.tif 000015
【００４４】
として成分で書くことができる。ここで、
【００４５】
【数１５】
0004253190.tif 000016
【００４６】
であり、ここで、インデックス「ｌ」と「ｍ」は「０」から「２Ｋ」までの範囲をとり、「２Ｋ」を含む。
【００４７】
上の説明から明らかなように、１つの「ｊ」番目の細分度における四辺形メッシュに適用されるＣａｔｍｕｌｌ‐Ｃｌａｒｋ表面細分法は、「ｊ」番目の細分度におけるメッシュと同数の点を有する、次に高い「ｊ＋１」番目の細分度における四辺形メッシュを生成するが、より高い（「ｊ＋１」）細分度における点は、「ｊ」番目のレベルにおける位置とは異なる位置にある。式（７）から（１２）、または、等価的な式（１３）から（１５）は、細分度「ｊ＋１」におけるメッシュに対する点を生成するために、細分度「ｊ」におけるメッシュ内の各点を頂点として選択することにより適用される。所望の任意の細分度のメッシュを生成するために、Ｃａｔｍｕｌｌ‐Ｃｌａｒｋ表面細分法を繰り返し適用できる。
【００４８】
細分表面内の鋭い折り目は、上で説明した表面細分式（三角形メッシュの場合には式（６）から（８）、四辺形メッシュの場合には式（１３）から（１５））を部分的に修正することによって生成される。これを、折り目が生じるそれぞれの頂点ｖq（ｖq＝ｖq（０））の両側における点についてのインデックス「ｋ」の順序付けを理解するのに有用なステンシルを示す図６と関連して説明する。折り目が生じるメッシュの辺に印をつけることによって、細分表面上の折り目の位置を定める一連の辺を定めることができる。三角形メッシュと四辺形メッシュの双方の場合のように、より高い「ｊ＋１」番目の細分度の頂点および点の位置ｃj+1を、「ｊ」番目のレベルの頂点および点の位置ｃjから、次のように細分行列ＳC（ここで、インデックス「Ｃ」は「折り目」を示す）を有する細分則を定める単一の式を用いて求めることできる。
【００４９】
【数１６】
0004253190.tif 000017
【００５０】
これは成分で、
【００５１】
【数１７】
0004253190.tif 000018
【００５２】
として書くことができる。ここで、
【００５３】
【数１８】
0004253190.tif 000019
【００５４】
であり、ここで、インデックス「ｌ」と「ｍ」は「０」から「２」までの範囲をとり、「２」を含む。この細分則は、細分表面が三角形メッシュと四辺形メッシュの双方によって定められる場合の折り目に対して用いることができる。
【００５５】
本発明は、細分表面内に滑らかな特徴線を生成するシステムと方法を提供する。鋭い折り目におけるように、滑らかな特徴線は、特徴線を定めることになる、所与のレベルの一連の辺を印すことによって定められる。滑らかな特徴線と関連づけられる辺が印される最低細分度は、滑らかな特徴線に対する設定レベル「ｊD」と呼ばれる。さらに、鋭さパラメータが、滑らかな特徴線に対する設定レベルｊD内に印されている各辺と関連づけられる。一実施形態では、鋭さパラメータの値は、区間［０，１］、すなわち、端の点を含めて「０」と「１」の間の実数の形をとる。辺が値「０」を有する鋭さパラメータを有するならば、その辺に沿う折り目は存在しない。他方、辺が値「１」を有する鋭さパラメータを有するならば、その辺は上述のように鋭い折り目の一部をなす。
【００５６】
一般に、滑らかな特徴線は、上述した細分則（三角形メッシュの場合には式（４）から（６）、四辺形メッシュの場合には式（１３）から（１５）を参照）を一般化した細分則を用いることによって得られる。細分則は、生成される滑らかな特徴線が交差する頂点の２つの側における鋭さパラメータのそれぞれの値である２つのパラメータｓ1とｓ2を用いる。細分表面の極限表面、すなわち、細分表面の極限点によって定められる表面は、滑らかな特徴線の近くでは滑らかである。すなわち、滑らかな特徴線と関連づけられた極限表面上の各点に対して、すなわち、点のそれぞれの側における鋭さパラメータの値が「１」以外である各点に対して、極限表面に垂直なベクトルの向きは絶えず変化する。しかしながら、鋭い折り目の場合にあたる、鋭さパラメータが値「１」を有するような点における極限表面に対しては、点のそれぞれの側に対する法線ベクトルの向きが異なるから、法線ベクトルは定められない。
【００５７】
コンピュータ・グラフィックス・システム１０が滑らかな特徴線の生成に関連して行う動作を、三角形メッシュを定める細分表面の場合、図７から１０と関連して、四辺形メッシュを定める細分表面の場合、図１１から１４と関連して説明する。双方の場合、滑らかな特徴線は、印されている辺に対応する線に近い細分表面の領域で、極限点の位置と、それぞれの極限点における法線ベクトルによって定められる。上記のように、法線ベクトルは、それぞれの極限点における２つの接線ベクトル、すなわち、それぞれの極限点において滑らかな特徴線に沿う接線ベクトルと、それぞれの極限点において滑らかな特徴線と交差する接線ベクトルの交差積に対応する。
【００５８】
図７を参照すると、この図は、インデックスが図に示されているようにつけられた頂点ｖq（頂点ｖq＝ｖq（０））と点ｖq（１）からｖq（Ｋ）を有する三角形メッシュによって定められた細分表面の一部を示している。滑らかな特徴線の一部を定める折り目が、辺ｖq（１）、ｖq（辺（１，０）として参照される）およびｖq、ｖq（Ｌ＋１）（辺（０，Ｌ＋１）として参照される）に沿って、点ｖq（１）、頂点ｖq、点ｖq（Ｌ＋１）を通るように、頂点がラベル付けされている。辺（１，０）と関連づけられた鋭さパラメータの値はｓ1として参照され、辺（０，Ｌ＋１）と関連づけられた鋭さパラメータの値はｓ2として参照される。辺（１，０）と（０，Ｌ＋１）は折り目を定める辺であると示されているので、鋭さパラメータの値はゼロではない。頂点ｖqにある他の辺と関連づけられた鋭さパラメータの値は「ゼロ」のこともあれば、ゼロでないこともある。一般に、式（４）（または、等価的な式（５））で記述されている細分則は、細分行列を用いて、それぞれの頂点の位置を求めるために用いることができる。
【００５９】
【数１９】
0004253190.tif 000020
【００６０】
ここで、式（６）におけるように、インデックス「１」と「ｍ］は「ゼロ」から「Ｋ」までの範囲にあり、かつ、「Ｋ」を含み、ｓ3＝（ｓ1＋ｓ2）／２、すなわち、辺（１，０）および（０，Ｌ＋１）と関連づけられたパラメータｓ1とｓ2の値の平均である。
【００６１】
接線ベクトルの向きが、不規則な頂点およびその近傍において、絶えず変化するようにするために、鋭さパラメータの値は、メッシュのレベルが高くなるにつれて徐々に小さくする。滑らかな特徴線の場合、メッシュのレベルが高くなるにつれて、鋭さパラメータの値を繰り返し更新すると、ゼロに近い値が得られる。そうすると、接線ベクトルの向きが、極限表面内で絶えず変化することになる。一実施形態では、鋭さパラメータｓ1とｓ2が、頂点の両側で同じ値「ｓ」を有する（すなわち、ｓ1＝ｓ2）ような頂点ｖqに対しては、鋭さパラメータ更新関数は、
【００６２】
【数２０】
0004253190.tif 000021
【００６３】
となる。すなわち、より高い「ｊ＋１」番目の細分度のメッシュにおける鋭さパラメータｓ1とｓ2の値ｓ（ｊ＋１）は、より低い（「ｊ番目」）レベルのメッシュにおける鋭さパラメータｓ1とｓ2の値ｓ（ｊ）の２乗である。他方、鋭さパラメータｓ1とｓ2の値が頂点の両側で一定ではない（すなわち、ｓ1≠ｓ2）ような頂点ｖqに対しては、鋭さパラメータ更新関数は、双方の鋭さパラメータｓ1とｓ2の値の関数である。一実施形態では、関数は、
【００６４】
【数２１】
0004253190.tif 000022
【００６５】
と、
【００６６】
【数２２】
0004253190.tif 000023
【００６７】
となるように選択され、二次スプラインに対応する線形組み合わせをほぼ提供する。
【００６８】
鋭さパラメータｓ1とｓ2の値はレベルごとに変わるので、滑らかな曲線の細分行列（Ｓsc,T,K,L（ｓ1，ｓ2））lm（式（１９））も細分度ごとに一定ではない。したがって、細分表面に対する極限点の位置と接線ベクトルの向きを求めるために従来用いられている固有値解析はここでは用いない。上で示唆したように、細分表面は、極限点および法線ベクトルの集合（または、等価的に、各法線ベクトルに対しての２つの接線ベクトル）によって定められ、これらは、式（４）をそのメッシュに対する設定レベル「ｊD」からレベルｊ＝∞まで繰り返し適用することによって生成される。設定レベルｊDは、細分表面内でそれぞれの滑らかな特徴線が定められる最低の細分度「ｊ」である。したがって、極限点の位置を求めるために、無限の細分行列
【００６９】
【数２３】
0004253190.tif 000024
【００７０】
が計算される。ここで、Ｓsc,T,K、L（ｓ1（ｊ），ｓ2（ｊ））は、式（２３）の右辺の行列積における「ｊ」番目のレベルに対応する鋭さパラメータに対して、式（１９）と関連して上で説明した細分行列である。式（２３）の左辺のＳsc,T,K、L,LP（ｓ1，ｓ2）に対して、独立変数ｓ1とｓ2は、滑らかな特徴線の設定レベルにおける鋭さパラメータ、すなわち、ｓ1＝ｓ1（ｊD）およびｓ2＝ｓ2（ｊD）を示し、下付き文字「ＬＰ」は「極限点」を示す。行列の乗算は交換則が成り立たないので、式（２３）における行列積中の因子の順序は重要である。式（２３）で、積中の因子の左から右への順序は、式（４）によって示唆されているように、左のｊ＝∞から右のｊ＝ｊDまで広がる。
【００７１】
行列積（式（２３））は、「Ｋ＋１」行を有する「Ｋ＋１」×「Ｋ＋１」の行列に収束し、各行を有する成分は、他の行の成分と同一で、同じ順序である。極限点の位置σ（ｑ）を求めるための重み値ｌLPのベクトルは、次のようにして得られる。
【００７２】
【数２４】
0004253190.tif 000025
【００７３】
ここで、ベクトルｖLPは、滑らかな特徴線が無い場合にはＬｏｏｐ細分法を用いて細分表面の極限点の位置を求めるのに用いられる重みのベクトルである。すなわち、
【００７４】
【数２５】
0004253190.tif 000026
【００７５】
である。ここで、
【００７６】
【数２６】
0004253190.tif 000027
【００７７】
であり、ここで、ａ（Ｋ）は式（３）で定められる。頂点ｖq（０）と関連づけられた極限点の位置σ（ｑ）は、細分表面内の滑らかな特徴線の設定レベルｊDに、または、その設定レベルより高い任意の細分度に対応するメッシュ中において、頂点ｖq（０）の位置ｃjD（ｑ）と、頂点ｖq（０）の周囲の隣接点ｖq（ｋ）の位置ｃjD（ｋ）（ｋ＝１，．．．，Ｋ）から、ｌLPの成分を重み値として用いることによって計算される。極限点重みベクトルｌLP（ｓ1，ｓ2）の成分は、成分ごとおよび価数ごとに６つの値を用いて、ｓ1とｓ2の２次多項式によって満足に近似できる。
【００７８】
Ｌ＝Ｋ／２ならば、対称性を考慮することにより、成分ごとの値の数を減らすことができる。この場合、極限点重みベクトルｌLPの成分は次の対称関係を満たす。
【００７９】
１．極限点重みベクトルｌLPの「ｉ」番目の成分は、ｌLPの「Ｋ＋２−ｉ」番目の成分に等しい。すなわち、ｉ＝Ｋ／２＋２，．．．，Ｋに対して、（ｌLP）i＝（ｌLP）K+2-iである。これは、細分行列（式（１９））が折り目線に関して折り返しても不変であるということの結果である。その結果、近似は、成分ｉ＝０，１，．．．，Ｋ／２＋１について生成する必要があるだけである。
【００８０】
２．さらに、細分行列（式（１９））はｓ1とｓ2において対称的であるので、（ｌLP（ｓ1，ｓ2））i＝（ｌLP（ｓ2，ｓ1））K/2+2-iであり、近似は、ｉ＝０，１，．．．，［Ｋ／４＋１］について生成する必要があるだけである。ここで、「［ｘ／ｙ］」は商「ｘ／ｙ；」中の最大整数を示す。
【００８１】
３．さらに、パラメータｓ1とｓ2の特定の値が相互交換されるならば、頂点ｖqは同じように振る舞うので、（ｌLP（ｓ1，ｓ2））0＝（ｌLP（ｓ2，ｓ1））0であり、近似は、ｓ1とｓ2中の対称的な２次多項式のみを用いて、すなわち、４つの係数を用いて行うことができる。
【００８２】
４．さらに、「Ｋ」が「４」の倍数ならば、上の点（１）および（２）から、（ｌLP（ｓ1，ｓ2））K/4+1＝（ｌLP（ｓ2，ｓ1））K/4+1である。したがって、これらの成分は、４つの係数を用いて対称的な２次の多項式を用いて近似できる。
一実施形態では、Ｌ＝Ｋ／２であるかどうかとは無関係に、多項式の近似は、最小二乗チェビシェフ近似法を用いて計算される。行列積（式（２３））はチェビシェフ多項式
【００８３】
【数２７】
0004253190.tif 000028
【００８４】
の根からなる、領域（ｓ1，ｓ2）内の格子の点において計算される。ここで、ｉ，ｊ＝０，．．．，Ｎ−１である。一実施形態では、「Ｎ」が「８」としてとられるので、式（２７）には「６４」個の標本点がある。対称的な場合（ｉ＝０またはＫ／４＋１）には、多項式
【００８５】
【数２８】
0004253190.tif 000029
【００８６】
非対称な場合（その他の「ｉ」）には、多項式
【００８７】
【数２９】
0004253190.tif 000030
【００８８】
に対する係数ｂij（対称的な場合にはｊ＝０，．．．，３、非対称的な場合にはｊ＝０，．．．，５）は、最小二乗法によって求められる。この演算では、コンピュータ・グラフィックス・システム１０は、行列積（式（２７）で定められているように、点（ｓ1，ｓ2）で計算された式（２３））を計算する。その後、Ｎ2個の多項式（式（２８）および／または（２９））のセットが、（ｓ1，ｓ2）領域内のそれぞれの点（式（２７））におけるｓ1とｓ2の値を用いて生成される。各多項式は、行列積の行のそれぞれの「ｉ」番目の成分に等しい。その後、コンピュータ・グラフィックス・システム１０は、最小二乗近似法を用いて、多項式中の係数ｂijの値を求める。係数ｂijの値が求められた後、これらは、式（２８）と（２９）を用いて、極限点重みベクトルｌLPの成分の値を生成するために用いられる。
【００８９】
最小２乗近似における誤差は、領域（ｓ1，ｓ2）にわたって振動的ふるまいを有し、この振動の振幅がこの領域にわたって一様に分布されているならば最小化される。これは、良く近似されている点に対して重み付けられた最小二乗法により課される制約を緩め、良く近似されていない点に対する制約をきつくすることにより行うことができる。重み付けられた最小二乗法では、上で説明した最小二乗法を用いて係数ｂijの値が計算された後、多項式（式（２８）および／または式（２９））が（ｓ1，ｓ2）領域内の各点で計算され、その値は、行列積（式（２３））のそれぞれの要素について生成された値と比較され、これらの間の差を反映する重み値が決定される。その後、この重み値は、係数ｂijの値の近似を不均一に制限するのに用いることができる。
【００９０】
図８は、Ｃプログラミング言語の形で、ｂ［Ｋ／２−２］［ｉ］［ｊ］のインデックス付けをした、Ｋ＝４，６，．．．，１６についての係数ｂijの表を示している。ここで、「ｉ」は、ｉ＝０，．．．，［Ｋ／４＋１］の範囲内の値をとる、極限点重みベクトルｌLPの成分のインデックスであり、「ｊ」は近似多項式の係数ｂijのインデックスである。
【００９１】
頂点ｖq（０）と関連づけられた極限点重みベクトルｌLPが上で説明したように生成された後、極限点重みベクトルｌLPは、頂点ｖq（０）と関連づけられた極限点の位置σ（ｑ）を次のように求めるために、頂点ｖq（０）の位置ｃj（ｑ）と、頂点ｖq（０）の近傍の点ｖq（ｋ）の位置ｃj（ｋ）（ｋ＝１，．．．，Ｋ）と一緒に次のように用いることできる。
【００９２】
【数３０】
0004253190.tif 000031
【００９３】
（ｌLP（ｓ1，ｓ2））iは、ｌLP（ｓ1，ｓ2）の「ｉ」番目の成分を示す。これは、滑らかな特徴線に対する設定レベルｊ＝ｊDと、設定レベルｊDより高い細分度における鋭さパラメータ値ｓ1とｓ2についての極限点重みベクトルｌLPに対応する。
【００９４】
一実施形態は、接線ベクトルを生成するのに用いる重み値のベクトルｌCとｌSについての良い近似を得るために、類似の多項式近似法を用いる。接線ベクトル重みベクトルｌCは、接線ベクトルを滑らかな特徴線に沿って生成するのに用いられ、接線ベクトル重みベクトルｌSは、それぞれの接線ベクトル重みベクトルが関連づけられている頂点ｖq（０）と関連づけられている極限点において滑らかな特徴線を横切って接線ベクトルを生成するのに用いられる。この方法では、ベクトルｌC（Ｊ）が次のようにして生成される。
【００９５】
【数３１】
0004253190.tif 000032
【００９６】
ここで、右辺の行ベクトルの２つのゼロでない成分は、行ベクトル中の位置「１」において「１」であり、位置Ｋ／２＋１において「負の１」であり、「・」はドット積を示す。式（３１）に従ってベクトルｌC（Ｊ）を生成した後、値は正規化され、極限がＪ→∞としてとられる。
【００９７】
【数３２】
0004253190.tif 000033
【００９８】
ベクトルｌC（式（３２））の成分は、図７に示すように、頂点ｖq（０）のそれぞれの位置と、頂点ｖq（０）の周囲の点ｖq（ｋ）（ｋ＝１，．．．，Ｋ）を乗ずるのに用いられる一連の重み値を形成する。これらの和が、頂点ｖq（０）と関連づけられた細分表面上の点における滑らかな特徴線に沿う接線ベクトルを定める。
【００９９】
極限点重みベクトルｌLPの成分の場合のように、接線ベクトル重みベクトルｌCの成分は、ｓ1とｓ2における多項式、この場合には三次の多項式により近似できる。したがって、接線ベクトル重みベクトルｌCの成分の近似は、成分当りおよび価数当り１０個までの数を用いることによって効率的に生成できる。Ｌ＝Ｋ／２ならば、対称性を考慮することによって、接線ベクトル重みベクトルｌCの成分を生成するのに用いられる多項式係数の数を減らすことができる。この場合、接線ベクトル重みベクトルｌCの成分は次の対称関係を満たす。
【０１００】
１．接線ベクトル重みベクトルｌCの「ｉ」番目の成分と、「ｋ＋２−ｉ」番目の成分が、ｉ＝Ｋ／２＋２，．．．，Ｋに対して等しい。すなわち、（ｌC）i＝（ｌC）K+2-iである。これは、折り目線に関して折り返されたときに細分行列（式（１９））が不変であることの結果である。結果として、近似は、成分ｉ＝０，１，．．．，Ｋ／２＋１について生成する必要があるのみである。
【０１０１】
２．さらに、（ｌC（ｓ1，ｓ2））i＝−（ｌC（ｓ2，ｓ1））K/2+2-iであるので、近似は、成分ｉ＝０，１，．．．，［Ｋ／４＋１］について生成する必要があるのみである。
【０１０２】
３．さらに、ｓ1とｓ2の特定の値が相互交換されるならば、頂点ｖqは、接線ベクトルの向きが逆であることを除き、同じようにふるまうので、（ｌC（ｓ1，ｓ2））0＝−（ｌC（ｓ2，ｓ1））0となる。この場合、近似は、４つの係数を用いる、ｓ1とｓ2における反対称３次多項式のみを用いて生成できる。
【０１０３】
４．さらに、「Ｋ」が「４」の倍数ならば、すぐ上の点（１）と（２）から、（ｌC（ｓ1，ｓ2））K/4+1＝−（ｌC（ｓ2，ｓ1））K/4+1である。したがって、４つの係数を用いる反対称多項式を用いて、これらの成分を近似できる。
一実施形態では、近似多項式もまた、上で説明した極限点近似と関連して用いたものに類似する最小二乗チェビシェフ近似法を用いて計算できる。式（３１）の行列積は、チェビシェフ多項式（式（２７））の根からなる、（ｓ1，ｓ2）領域内の格子の点において計算される。反対称（ｉ＝０またはＫ／４＋１）の場合には、多項式
【０１０４】
【数３３】
0004253190.tif 000034
【０１０５】
非対称（「ｉ」はそれ以外）の場合には、多項式
【０１０６】
【数３４】
0004253190.tif 000035
【０１０７】
の係数ｂij（反対称の場合にはｊ＝０，．．．，３、非対称の場合にはｊ＝０，．．．，９）は、上述したように最小二乗法を用いて求められる。
【０１０８】
滑らかな特徴線に沿って接線ベクトルを生成するのと類似するやり方（上の式（３１）から（３４）を参照）で、重み値のベクトルｌSが、滑らかな特徴線を交差する接線ベクトルを生成するのに用いられる。接線ベクトル重みベクトルｌSの成分は、頂点ｖq（０）と、頂点ｖq（０）の周囲の点ｖq（１）からｖq（Ｋ）の位置を乗ずるために用いられる一連の重み値を有する（図７を参照）。これらの和は、滑らかな特徴線を横切る接線ベクトルを有する。この方法では、ベクトルｌS（Ｊ）は次のようにして生成される。
【０１０９】
【数３５】
0004253190.tif 000036
【０１１０】
ベクトルｌS（Ｊ）は、接線ベクトル重みベクトルｌSを生成するために、式（３２）と関連して上で説明したのと類似のやり方で正規化され、極限がＪ→∞のように取られる。
【０１１１】
Ｌ＝Ｋ／２のとき、接線ベクトル重みベクトルｌSは、
【０１１２】
【数３６】
0004253190.tif 000037
【０１１３】
である。これは、ゼロである鋭さパラメータと関連づけられた滑らかな特徴線の場合におけるのと同じである。
【０１１４】
接線ベクトル重みベクトルｌSの成分は、鋭さパラメータｓ1とｓ2の三次多項式を用いてｌS（ｓ1，ｓ2）として近似できる。多項式の係数を生成するのに行われる演算は、滑らかな特徴線に沿って接線ベクトルを生成するのに用いられる接線ベクトル重みベクトルｌCについて上で説明した多項式の係数を生成するのに行われる演算に対応する（式（３１）から（３４））。
【０１１５】
図９は、Ｃプログラミング言語の形で、ｂ［Ｋ／２−２］［ｉ］［ｊ］をインデックス付けする、Ｋ＝４，６，．．．，１６に対する係数ｂijの表を示している。ここで、「ｉ」は、ｉ＝０，．．．，［Ｋ／４＋１］の範囲内の値をとる、ｌCの成分のインデックスであり、「ｊ」は、近似多項式の係数ｂijのインデックスである。
【０１１６】
上記のように、接線ベクトル重みベクトルｌC（＝ｌC（ｓ1，ｓ2））とｌS（＝ｌS（ｓ1，ｓ2））（ここで、ｓ1，ｓ2は、滑らかな特徴線に対する設定レベルｊ＝ｊDにおける鋭さパラメータ値である）が、頂点ｖq（０）の位置ｃj（ｑ）および隣接点ｖq（ｋ）の位置ｃj（ｋ）（ｋ＝１，．．．，Ｋ）と一緒に用いられる。特に、それぞれの接線ベクトル重みベクトルの成分が、頂点と隣接点の位置に重みをつけるために用いられ、その和は接線ベクトルを含む。すなわち、滑らかな特徴線に沿う接線ベクトルｅC（ｑ）と、滑らかな特徴線を交差する接線ベクトルｅS（ｑ）は、
【０１１７】
【数３７】
0004253190.tif 000038
【０１１８】
として生成される。ここで、ｌC（ｓ1，ｓ2）＝ｌCおよびｌS（ｓ1，ｓ2）＝ｌS（ここで、ｓ1とｓ2は、滑らかな特徴線についての設定レベルｊ＝ｊDにおける鋭さパラメータ値である）であり、インデックス０，．．．，Ｋが図７に示されている。
【０１１９】
ある場合には、極限点重みベクトルｌLPと接線ベクトル重みベクトルｌC、ｌSについての近似を生成するために多項式を用いることは実際的でない。たとえば、滑らかな特徴線の構成の数がある数を超えるならば、おのおのは異なる多項式の集合を要するので、多項式の数は、この方法を用いるのが実際的でない程度まで増加する。極限点重みベクトルｌLPと接線ベクトル重みベクトルｌC、ｌSについての近似を生成するかわりの方法は外挿を用いる。
【０１２０】
極限点重みベクトルｌLP（ｓ1，ｓ2）の近似を生成する外挿法は、インデックス「ｊ」の有限値に対する式（２３）の初めのいくつかの係数で始まる。以下では、滑らかな特徴線に対する設定レベルｊDがレベル「ゼロ」であると仮定するが、これは説明の一般性を制限するものではないことがわかるであろう。因子ｊ＝Ｊ，Ｊ−１，．．．，０ととることによって生成された行列積は、
【０１２１】
【数３８】
0004253190.tif 000039
【０１２２】
と、
【０１２３】
【数３９】
0004253190.tif 000040
【０１２４】
によって与えられる。ここで、極限Ｊ＝０の場合（この場合には、行列積を生成するのに因子はない）には、行列積Ｓsc,T,K,L,LP（０）（ｓ1，ｓ2）は大きさが「Ｋ＋１」×「Ｋ＋１」の単位行列である。極限点の位置σ（ｑ）を求めるための重み値ｌLPのベクトルが次のようにして得られる。
【０１２５】
【数４０】
0004253190.tif 000041
【０１２６】
ここで、νLPは、式（２８）および（２９）と関連して、上で定められている。
【０１２７】
【数４１】
0004253190.tif 000042
【０１２８】
によって行われる。ここで、ｌLP（Ｊ）は式（４０）で定められ、係数ｂjは、
【０１２９】
【数４２】
0004253190.tif 000043
【０１３０】
によって与えられる。この外挿法は、頂点が一定であろうが不定であろうが、任意の頂点について用いることができる。さらに、この方法は、それぞれの頂点を通る任意の形状の折り目と、それぞれの頂点についての価数「Ｋ」の任意の値について用いることができる。
【０１３１】
ある外挿法も、接線ベクトル重みベクトルｌCとｌSを生成するために用いることができる。一般に、この方法では、上述した行列積Ｓsc,T,K,L,LP（Ｊ）（ｓ1，ｓ2）（式（３８）と（３９））は、その後、
（１）接線ベクトル重みベクトルｌCが生成されるならば、ベクトルｖCによって乗ぜられ、接線ベクトル重みベクトルｌSが生成されるならば、ベクトルｖSによって乗ぜられ、
（２）（１）からの結果が、その後、それぞれの接線ベクトル重みベクトルを正規化された形で維持する拡張係数によって乗ぜられる。
接線ベクトル重みベクトルｌCとｌSの近似は、
【０１３２】
【数４３】
0004253190.tif 000044
【０１３３】
から生成される。ここで、ｄ（Ｋ）は拡張係数を表す。ベクトルｖCとｖSは、
【０１３４】
【数４４】
0004253190.tif 000045
【０１３５】
によって与えられ、拡張係数ｄ（Ｋ）は、滑らかな場合についての細分行列の固有値の１つの逆数、すなわち、
【０１３６】
【数４５】
0004253190.tif 000046
【０１３７】
である。接線ベクトル重みベクトルｌCとｌSの近似は、
【０１３８】
【数４６】
0004253190.tif 000047
【０１３９】
によって与えられる。ここで、係数ｂJは、式（４２）に与えられている形をとる。この外挿法は、あらゆる構成と関連して用いることができる。重みベクトルｌCを用いて生成された接線ベクトルは、ほぼ、頂点ｖq（０）と点ｖq（１）の間の辺［１，０］の方向に向けられ、重みベクトルｌSを用いて生成された接線ベクトルは、ほぼ、辺［１，０］に垂直に向けられる。細分表面内の所与のレベル「ｊ」に対する辺［１，０］と［０，Ｌ＋１］の間の角度は通常１８０度ではないが、レベル「ｊ」が無限に近づくと、その角度は１８０度に近づく。したがって、極限において、すなわち、「ｊ」が無限に近づくと、頂点ｖq（０）と関連づけられた極限点の一方の側の辺に沿う接線ベクトルは、同じ頂点と関連づけられた極限点の他方の側における辺に沿う接線ベクトルとは反対方向に近づく。同様に、頂点ｖq（０）と関連づけられた極限点の一方の側の辺と交差する接線ベクトルは、同じ頂点と関連づけられた極限点の他方の側における辺と交差する接線ベクトルとは反対方向に近づく。
【０１４０】
この背景で、三角形メッシュについての細分表面に対する極限点と接線ベクトルを生成するのに有用な重みベクトルｌLP、ｌC、ｌSの生成における、コンピュータ・グラフィックス・システム１０によって行われる動作を、図１０に示されているフローチャートと関連して説明する。この図を参照すると、コンピュータ・グラフィックス・システム１０は、式（１９）に関連して上で説明したように、細分行列Ｓsc,T,K,L（ｓ1（ｊ），ｓ2（ｊ））（ｊ＝０，１，２）をまず初期化する（ステップ１００）。その後、コンピュータ・グラフィックス・システム１０は、Ｊ＝２，３に対して、行列積Ｓsc,T,K,L,LP（Ｊ）（ｓ1，ｓ2）を生成する（ステップ１０１）。Ｊ＝１に対して、Ｓsc,T,K,L,LP（１）（ｓ1，ｓ2）＝Ｓsc,T,K,L（ｓ1，ｓ2）であり、上で示唆したように、Ｊ＝０に対して、Ｓsc,T,K,L,LP（０）（ｓ1，ｓ2）は「Ｋ＋１」×「Ｋ＋１」の単位行列である。
【０１４１】
コンピュータ・グラフィックス・システム１０が、行列積Ｓsc,T,K,L,LPを生成した後、それは、各行列積Ｓsc,T,K,L,LP（Ｊ）（ｓ1，ｓ2）（Ｊ＝０，１，２，３）の最初の行をとり、式（４１）の外挿式にしたがって、極限点重みベクトルｌLPについての成分ごとの近似を生成する（ステップ１０２）。さらに、コンピュータ・グラフィックス・システム１０は、式（４３）と関連して上で説明したように、ベクトルｌC（Ｊ）とｌS（Ｊ）（Ｊ＝０，１，２，３）を生成するために、行列積Ｓsc,T,K,L,LP（Ｊ）（ｓ1，ｓ2）、拡張係数ｄ（Ｋ）、ベクトルｖCとｖSを用いる（ステップ１０３）。Ｊ＝０に対して、それぞれの重みベクトルは、ｌC（０）＝ｖCおよびｌS（０）＝ｖSである。ステップ１０３に続いて、コンピュータ・グラフィックス・システム１０は、式（４６）にしたがって、接線ベクトル重みベクトルｌCとｌSについての近似を生成するために、ｌC（Ｊ）とｌS（Ｊ）を用いる（ステップ１０４）。極限点重みベクトルｌLPと接線ベクトル重みベクトルｌCとｌSが生成された後、極限点および接線ベクトルを上述のようにして生成でき（それぞれ、式（３０）と（３７）を参照）、法線ベクトルが、接線ベクトルの間の交差積として生成される（ステップ１０５）。
【０１４２】
四辺形メッシュによって定められる細分表面の場合に滑らかな特徴線を生成することと関連して、コンピュータ・グラフィックス・システム１０によって行われる動作を、図１１から１３および図１０のフローチャートと関連して説明する。図１１を参照すると、この図は、インデックスがこの図に示されているように付けられている頂点ｖq（頂点ｖq＝ｖq（０））および点ｖq（１）からｖq（２Ｋ）を有する三角形メッシュによって定められた細分表面の一部を示している。点ｖq（１）からｖq（Ｋ）は、頂点ｖqの１次の隣接点であり、点ｖq（Ｋ＋１）からｖq（２Ｋ）は、頂点ｖqの２次の隣接点であることがわかるであろう。頂点は、折り目が辺ｖq（１）、ｖq（これらは辺（１，０）として参照される）とｖq、ｖq（Ｌ＋１）（これらは辺（０，Ｌ＋１）として参照される）に沿って、点ｖq（１）、頂点ｖq（０）、点ｖq（Ｌ＋１）を通るように、ラベル付けされる。辺（１，０）と関連づけられた鋭さパラメータの値はｓ1として参照され、辺（０，Ｌ＋１）と関連づけられた鋭さパラメータの値はｓ2として参照される。一般に、式（１３）と（１４）に記述されている細分則は、式（１５）と関連して上で説明した細分行列のかわりに、細分行列
【０１４３】
【数４７】
0004253190.tif 000048
【０１４４】
を用いて、それぞれの頂点の位置を求めるために用いることができる。ここで、式（１９）のように、ｓ3＝（ｓ1＋ｓ2）／２であり、辺（１，０）と（０，Ｌ＋１）と関連づけられたパラメータｓ1とｓ2の値の平均である。
【０１４５】
三角形メッシュによって形成された細分表面の場合のように、それぞれの接線ベクトルの向きを種々の細分度における不規則な頂点およびその近傍において絶えず変化させるために、鋭さパラメータの値はメッシュの細分度が高くなるにつれて徐々に減らす。一実施形態では、コンピュータ・グラフィックス・システムは、四辺形メッシュによって定められている細分表面の場合に、三角形メッシュによって定められている細分表面の場合におけるのと同じように、鋭さパラメータの値を変化させる（上の式（２０）から（２２）を参照）。
【０１４６】
三角形メッシュによって定められる細分表面の場合のように、四辺形メッシュによって定められる細分表面の場合に頂点ｖq（０）と関連づけられた極限点の位置を求めるために、無限細分行列積
【０１４７】
【数４８】
0004253190.tif 000049
【０１４８】
が計算される。ここで、Ｓsc,Q,K,L（ｓ1（ｊ），ｓ2（ｊ））は、ｊ番目のレベルと関連づけられた鋭さパラメータ値ｓ1とｓ2についての式（４７）からの細分行列であり、インデックスｊDは滑らかな折り目の設定レベルを示す。式（４８）の左辺において、独立変数ｓ1とｓ2に対して、ｓ1＝ｓ1（ｊD）およびｓ2＝ｓ2（ｊD）である。三角形メッシュによって定められる細分表面の場合のように、式（４８）における行列積は、同一の行を有する行列に収束し、この場合に、各行はサイズが２Ｋ＋１である。頂点ｖq（０）と関連づけられた極限点の位置σ（ｑ）を求めるための重み値LPのベクトルが次のように得られる。
【０１４９】
【数４９】
0004253190.tif 000050
【０１５０】
ここで、ベクトルｖLPは、滑らかな特徴線が無い場合に、四辺形メッシュによって定められる細分表面の極限点の位置を求めるのに用いられる重みベクトルである。すなわち、
【０１５１】
【数５０】
0004253190.tif 000051
【０１５２】
ここで、式（５０）において、値「４」を有する「Ｋ」個の成分と、値「１」を有する「Ｋ」個の成分がある。
【０１５３】
行ベクトルｌLP（ｓ1，ｓ2）の成分ｌLP（ｓ1，ｓ2）i（ｉ＝０，．．．，２Ｋ）と、頂点ｖq（０）の位置ｃj（０）と、隣接点ｖq（ｉ）のｃj（ｉ）（ｉ＝１，．．．，２Ｋ）が、頂点ｖq（０）に関連する極限点の位置σ（ｑ）を決定するために次のように用いられる。
【０１５４】
【数５１】
0004253190.tif 000052
【０１５５】
三角形メッシュによって定められている細分表面の場合のように、極限点重みベクトルｌLP（ｓ1，ｓ2）の成分を、多項式展開を用いて近似できる。極限点重みベクトルｌLP（ｓ1，ｓ2）の成分を、成分ごとおよび価数ごとに６つの値を用いて、ｓ1とｓ2の二次多項式によって満足に近似できる。「Ｋ」の値が偶数であり、Ｌ＝Ｋ／２ならば、対称性を考慮することにより、成分ごとの値の数を減らすことができる。この場合、極限点重みベクトルｌLPの成分は次の対称関係を満たす。
【０１５６】
１．極限点重みベクトルｌLP（ｓ1，ｓ2）の「ｉ番目」の成分は、極限点重みベクトルｌLP（ｓ1，ｓ2）の「Ｋ＋２−ｉ」番目の成分に等しい。すなわち、ｉ＝２，．．．，Ｋ／２に対して、（ｌLP（ｓ1，ｓ2））i＝（ｌLP（ｓ1，ｓ2））K+2-1であり、極限点重みベクトルｌLP（ｓ1，ｓ2）の「ｉ」番目の成分は、極限点重みベクトルｌLP（ｓ1，ｓ2）の「３Ｋ＋１−ｉ」番目の成分に等しい。すなわち、ｉ＝Ｋ＋１，．．．，Ｋ＋Ｋ／２に対して、（ｌLP（ｓ1，ｓ2））i＝（ｌLP（ｓ1，ｓ2））3K+1-iである。
【０１５７】
２．ｉ＝１，．．．，Ｋ／２＋１に対して、（ｌLP（ｓ1，ｓ2））i＝（ｌLP（ｓ1，ｓ2））K/2+2-iであり、ｉ＝Ｋ＋１，．．．，Ｋ＋Ｋ／２＋１に対して、（ｌLP（ｓ1，ｓ2））i＝（ｌLP（ｓ1，ｓ2））2K+K/2+1-iである。
【０１５８】
３．（ｌLP（ｓ1，ｓ2））0＝（ｌLP（ｓ2，ｓ1））0である。
【０１５９】
４．「Ｋ」が「４」の倍数ならば、（ｌLP（ｓ1，ｓ2））K/4+1＝（ｌLP（ｓ2，ｓ1））K/4+1であり、「Ｋ」が「４」の倍数でないならば、（ｌLP（ｓ1，ｓ2））K+[K/4]+1＝（ｌLP（ｓ2，ｓ1））K+[K/4]+1である。
すぐ上で説明した対称関係が与えられると、ｉ＝０，．．．，［Ｋ／４］＋１およびｉ＝Ｋ＋１，．．．，Ｋ＋［Ｋ／４］＋１についての極限点重みベクトルｌLPに対する近似を生成することだけが必要であり、さらに、「Ｋ」の任意の偶数値に対してはｉ＝０について、「Ｋ」が「４」の倍数ならばｉ＝Ｋ／４＋１について、「Ｋ」が偶数であるが、「４」の倍数でなければｉ＝Ｋ＋［Ｋ／４］＋１について、対称的な多項式を用いることができる。
【０１６０】
三角形メッシュによって定められる細分表面の場合のように、一実施形態では、四辺形メッシュによって定められる細分表面の場合、Ｌ＝Ｋ／２かどうかとは無関係に、近似多項式が最小二乗チェビシェフ近似法を用いて計算される（上の式（２７）を参照）。この場合、対称的な場合には、多項式
【０１６１】
【数５２】
0004253190.tif 000053
【０１６２】
非対称的な場合には、多項式
【０１６３】
【数５３】
0004253190.tif 000054
【０１６４】
の係数ｂij（対称的な場合にはｊ＝０，．．．，３、非対称的な場合にはｊ＝０，．．．，５）が最小二乗法によって求められる。図１２は、Ｋ＝４、Ｌ＝２に対して、「ｉ」の値がｉ＝０；１；２；５の場合の係数ｂijの表を示している。係数ｂijが生成された後（式（５２）と（５３））、これらは、式（５１）と関連して上で説明したように、極限点σ（ｑ）の位置を生成するために用いられる極限点重みベクトルｌLPを、三角形メッシュによって定められる細分表面の場合とおなじように生成するために用いられる。
【０１６５】
四辺形メッシュによって定められている細分表面の場合の接線ベクトルは、三角形メッシュによって定められる細分表面の場合に接線ベクトルを生成するために用いられるのと同様な方法で生成される。一般に、この方法では、上述した行列積Ｓsc,Q,K,L,LP（Ｊ）（ｓ1，ｓ2）（式（４８））が生成され、その後、三角形メッシュの場合における接線ベクトル重みベクトルの場合のように、
（１）接線ベクトル重みベクトルｌCが生成されているならば、ベクトルｖCによって乗ぜられ、接線ベクトル重みベクトルｌSが生成されているならば、ベクトルｖSによって乗ぜられ、
（２）（１）からの結果が、その後、それぞれの接線ベクトルを正規化された形に維持する拡張係数によって乗ぜられる。
まず、ベクトルｌC（Ｊ）（ｓ1，ｓ2）とｌS（Ｊ）（ｓ1，ｓ2）が、
【０１６６】
【数５４】
0004253190.tif 000055
【０１６７】
として生成される。四辺形メッシュによって定められる細分表面の場合には、それぞれのベクトルｖCとｖSは、
【０１６８】
【数５５】
0004253190.tif 000056
【０１６９】
によって与えられ、拡張係数は、滑らかな内部頂点についての細分行列（式４７）の部分支配的な固有値の逆数として与えられる。
【０１７０】
【数５６】
0004253190.tif 000057
【０１７１】
ここで、ＡKは、
【０１７２】
【数５７】
0004253190.tif 000058
【０１７３】
によって定められる。
【０１７４】
接線ベクトル重みベクトルｌCとｌSは、接線ベクトルを次のように生成するために用いられる。
【０１７５】
【数５８】
0004253190.tif 000059
【０１７６】
ここで、インデックス付けは、図１１に示されている。
【０１７７】
三角形メッシュによって定められる細分表面の場合のように、四辺形メッシュによって定められる細分表面の場合には、接線ベクトル重みベクトルｌCを用いて生成され、頂点ｖq（０）について生成された接線ベクトルｅC（ｑ）は、頂点ｖq（０）と関連づけられた極限点を通る滑らかな特徴線にほぼ沿うように向けられ、接線ベクトル重みベクトルｌSを用いて生成された接線ベクトルｅS（ｑ）は、頂点ｖq（０）と関連づけられた極限点を通る滑らかな特徴線にほぼ垂直に向けられる。
【０１７８】
また、三角形メッシュによって定められる細分表面の場合のように、四辺形メッシュによって定められる細分表面の場合の接線ベクトル重みベクトルは、多項式近似を用いて近似できる。接線ベクトル重みベクトルｌC（ｓ1，ｓ2）とｌS（ｓ1，ｓ2）の成分は、一般に、成分ごとおよび価数ごとに１０個の値を用いて、ｓ1とｓ2における三次多項式により満足に近似できる。「Ｋ」の値が偶数であり、Ｌ＝Ｋ／２ならば、対称性を考慮することによって、成分ごとの値の数を減らすことができる。この場合、接線ベクトル重みベクトルｌCの成分は次の対称関係を満たす。
【０１７９】
１．接線ベクトル重みベクトルｌC（ｓ1，ｓ2）の「ｉ」番目の成分が、接線ベクトル重みベクトルｌC（ｓ1，ｓ2）の「Ｋ＋２−ｉ」番目の成分に等しい。すなわち、ｉ＝２，．．．，Ｋ／２に対して、（ｌC（ｓ1，ｓ2））i＝（ｌｃ（ｓ1，ｓ2））K+2-iであり、接線ベクトル重みベクトルｌC（ｓ1，ｓ2）の「ｉ」番目の成分が、接線ベクトル重みベクトルｌC（ｓ1，ｓ2）の「３Ｋ＋１−ｉ」番目の成分に等しい。すなわち、ｉ＝Ｋ＋１，．．．，Ｋ＋Ｋ／２に対して、（ｌC（ｓ1，ｓ2））i＝（ｌC（ｓ1，ｓ2））3K+1-iである。
【０１８０】
２．ｉ＝１，．．．，Ｋ／２＋１に対して、（ｌC（ｓ1，ｓ2））i＝−（ｌC（ｓ1，ｓ2））K/2+2-iであり、ｉ＝Ｋ＋１，．．．，Ｋ＋Ｋ／２＋１に対して、（ｌC（ｓ1，ｓ2））i＝−（ｌC（ｓ1，ｓ2））2K+K/2+1-iである。
【０１８１】
３．（ｌC（ｓ1，ｓ2））0＝−（ｌC（ｓ2，ｓ1））0である。
【０１８２】
４．「Ｋ」が「４」の倍数ならば、（ｌC（ｓ1，ｓ2））K/4+1＝−（ｌC（ｓ2，ｓ1））K/4+1であり、「Ｋ」が「４」の倍数でないならば、（ｌC（ｓ1，ｓ2））K+[K/4]+1＝−（ｌC（ｓ2，ｓ1））K+[K/4]+1である。
すぐ上で説明した対称関係が与えられると、ｉ＝０，．．．，［Ｋ／４］＋１およびｉ＝Ｋ＋１，．．．，Ｋ＋［Ｋ／４］＋１に対して近似を生成することだけが必要であり、さらに、「Ｋ」の任意の偶数値に対しｉ＝０について、「Ｋ」が「４」の倍数ならばｉ＝Ｋ／４＋１について、「Ｋ」が偶数であるが、「４」の倍数でなければｉ＝Ｋ＋［Ｋ／４］＋１について、反対称的な多項式も用いることができる。
【０１８３】
三角形メッシュによって定められる細分表面の場合のように、一実施形態では、近似多項式もまた、上述した極限点近似と関連して用いられたのと同じ最小二乗チェビシェフ近似法を用いて計算される。式（４８）行列積は、チェビシェフ多項式（式（２７））の根からなる、（ｓ1，ｓ2）領域内の格子の点において計算される。この場合、反対称的な場合には、多項式
【０１８４】
【数５９】
0004253190.tif 000060
【０１８５】
非対称的な場合には、多項式
【０１８６】
【数６０】
0004253190.tif 000061
【０１８７】
の係数ｂij（反対称的な場合にはｊ＝０，．．．，３、非対称的な場合にはｊ＝０，．．．，９）は、最小二乗法を用いて求められる。最小二乗法と関連して行われる演算は、三角形メッシュによって定められる細分表面の場合に上で説明したものに対応する。接線ベクトル重みベクトルｌSの成分は、鋭さパラメータｓ1とｓ2における三次多項式を用いて、ｌS（ｓ1，ｓ2）として近似できる。多項式の係数を生成するのに行われる演算は、滑らかな特徴線に沿って接線ベクトルを生成するのに用いられる接線ベクトル重みベクトルｌCについて上で説明した、多項式の係数を生成するのに行われる演算に対応する。図１３は、ｉ＝０；１；２；５に対応する、Ｋ＝４およびＬ＝２に対する係数ｂijの表を示している。
【０１８８】
接線ベクトル重みベクトルｌCとｌSが生成された後、これらは、式（５８）と関連して上で説明したように、接線ベクトルｅCとｅSを生成するために用いられる。
【０１８９】
三角形メッシュによって定められる細分表面の場合のように、ある場合には、極限点重みベクトルｌLPおよび接線ベクトル重みベクトルｌCとｌSについての近似を生成するために、多項式を用いることは実際的ではない。極限点重みベクトルｌLPおよび接線ベクトル重みベクトルｌCとｌSについての近似を生成するかわりの方法は、多項式外挿を用いる。この外挿法は，式３８から４６と関連して上で説明した方法と似ている。
【０１９０】
多項式外挿法を用いて、四辺形メッシュによって定められる細分表面についての極限点重みベクトルｌLPおよび接線ベクトル重みベクトルｌCとｌSを生成することと関連して、コンピュータ・グラフィックス・システム１０によって行われる動作は、三角形メッシュによって定められる細分表面について、図１０と関連して上で説明したものと似ており、その説明は、図１０を参照すべきである。
【０１９１】
このシステムは、多くの利点を有する。特に、本発明は、パラメータの値が、少なくともいくつかのレベルで変化する、同じくパラメータ化された細分則を各レベルで適用することによって、選択されたレベルにおける制御メッシュによって定められる表現から細分表面を生成するシステムを提供する。本発明は、滑らかな特徴線を定めるパラメータの値が少なくともいくつかのレベルで変化する、同じくパラメータ化された細分則を各レベルで用いて、細分表面内に滑らかな特徴線を生成することを特に提供する。結果として得られる細分表面は、比較的質が高く、効率的に計算できる。
【０１９２】
多くの変更と修正を、本明細書で説明したようなシステムに施してもよいことが理解できるだろう。たとえば、このシステムを三角形面と四辺形面のメッシュと関連して説明してきたが、このシステムは、種々の多角形構造の面を有するメッシュと関連して有用性を見出してもよいことが理解できるだろう。
【０１９３】
さらに、特定の細分則（式（１９）と（４６））について説明してきたが、他の細分則も有用性を見出すことができることが理解できるであろう。
【０１９４】
さらに、鋭さパラメータｓ1とｓ2を更新する方法を説明し、重みベクトルｌLP、ｌC、ｌSを近似する種々の方法を説明してきたが、他のパラメータ更新方法および近似方法にも有用性を見出だすことができることが理解できるであろう。
【０１９５】
さらに、本明細書で説明した外挿法と関連して、係数ｂJの数と、式（４１）と（４６）における総和についての上限（「３」）は、「３」次以外の多項式が外挿で用いられるならば、異なることがありうることが理解できるであろう。
【０１９６】
本発明によるシステムは、専用ハードウェア、汎用コンピュータ・システム、または、これらの組み合わせから全体または一部が構成され、その任意の部分を適切なプログラムによって制御してもよいことが理解できるであろう。任意のプログラムは、全体または一部において、従来の方法で、システムの一部を含み、または、システム上に保持され、または、全体としてまたは部分的に、従来の方法で情報を転送するネットワークまたはその他の機構を介してシステムへ提供してもよい。さらに、このシステムは、情報を従来の方法で転送するネットワークまたはその他の機構を介して、システムに直結でき、あるいは、システムへ情報を転送できるオペレータ入力要素（不図示）を用いて、オペレータによって入力された情報によって動作および／またはさもなければ制御するようにしてもよいことが理解できるであろう。
【０１９７】
以上の説明は、本発明の特定の実施形態に限定されている。しかしながら、本発明の利点のいくつかまたは全てを維持しながら、本発明に種々の変更と修正を行うことができることは明らかである。これらおよび他の変更および修正を、本発明の要旨および範囲内に含めることが、添付した特許請求の範囲の目的である。
【図面の簡単な説明】
【０１９８】
【図１】本発明にしたがって構成された、細分表面内に滑らかな特徴線を生成するシステムを含むコンピュータ・グラフィックス・システムを示す。
【図２】Ｌｏｏｐ表面細分法が適用されている表面を表現するメッシュを示す。
【図３】Ｌｏｏｐ表面細分法を理解するのに有用なステンシルを示す。
【図４】Ｃａｔｍｕｌｌ‐Ｃｌａｒｋ表面細分法が適用されている表面を表現するメッシュを示す。
【図５】Ｃａｔｍｕｌｌ‐Ｃｌａｒｋ表面細分法を理解するのに有用なステンシルを示す。
【図６】細分表面上に鋭い折り目を生成する方法を理解するのに有用なステンシルを示す。
【図７】三角形のメッシュによって定められた細分表面と関連して用いられる、滑らかな特徴線を生成する方法を理解するのに有用なステンシルを示す。
【図８】図７と関連して説明した、三角形のメッシュによって定められた表面と関連して用いられる方法で用いられる係数の表を示す。
【図９】図７と関連して説明した、三角形のメッシュによって定められた表面と関連して用いられる方法で用いられる係数の表を示す。
【図１０】図７と関連して説明した、三角形のメッシュによって定められた表面と関連して用いられる方法と関連して、コンピュータ・グラフィックス・システムによって行われる動作を説明するフローチャートを示す。
【図１１】四辺形のメッシュによって定められた細分表面と関連して用いられる、滑らかな特徴線を生成する方法を理解するのに有用なステンシルを示す。
【図１２】図１１と関連して説明した、四辺形のメッシュによって定められた表面と関連して用いられる方法で用いられる係数の表を示す。
【図１３】図１１と関連して説明した、四辺形のメッシュによって定められた表面と関連して用いられる方法で用いられる係数の表を示す。
【図１】
0004253190.tif 000350
【図２】
0004253190.tif 000351
【図３】
0004253190.tif 000352
【図４Ａ】
0004253190.tif 000353
【図４Ｂ】
0004253190.tif 000354
【図４Ｃ】
0004253190.tif 000355
【図４Ｄ】
0004253190.tif 000356
【図４Ｅ】
0004253190.tif 000357
【図５】
0004253190.tif 000358
【図６】
0004253190.tif 000359
【図７】
0004253190.tif 000360
【図８】
0004253190.tif 000361
【図９】
0004253190.tif 000362
【図１０】
0004253190.tif 000363
【図１１】
0004253190.tif 000364
【図１２】
0004253190.tif 000365
【図１３】
0004253190.tif 000366