(57)【要約】【課題】コンピュータ・システムにおいて二次元テクスチャ座標を算出するシステムにおいてメモリサイズ及び回路サイズの問題を解決する。【解決手段】  二次元テクスチャ座標(u,v)を求め、前記座標u及びvを用いて2つのランダム値の一次元区間を2個生成し、前記ランダム値の一次元区間2個を結合して、4つのランダム値の二次元区間を1個生成し、前記テクスチャ座標(u,v)及び前記4つのランダム値の二次元区間に応じて、ランダム値を生成し、前記ランダム値と前記入力テクスチャ座標(u,v)を結合して、変換された前記二次元テクスチャ座標(u’,v’)を得る。【選択図】図１
2008033848.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータ・システムにおいて二次元テクスチャ座標を算出するシステムであって、
二次元テクスチャ座標(u,v)を求める第1手段と、
前記座標u及びvを用いて2つのランダム値の一次元区間を2個生成する第2手段と、
前記ランダム値の一次元区間2個を結合して、4つのランダム値の二次元区間を1個生成する第3手段と、
前記テクスチャ座標(u,v)及び前記4つのランダム値の二次元区間に応じて、ランダム値を生成する第4手段と、
前記ランダム値と前記入力されたテクスチャ座標(u,v)を結合して、変換された前記二次元テクスチャ座標(u’,v’)を得る第5手段と、
を備えたシステム。
【請求項２】
請求項１において、
前記第2手段が、u又はv座標のいずれかを入力して2つのランダム値(u0,u1)及び(v0,v1)の前記一次元区間を得る、分離しているが同様な乱数発生器2個を具備しており、
前記第3手段が、前記ランダム値(u0,u1)及び(v0,v1)の一次元区間2個を結合して二次元区間[(u0,v0),(u1,v1)]を得るシステム。
【請求項３】
請求項１において、
前記第2手段が、
u又はv座標のいずれか（以下、“t”と称することもある。）を入力して2つのランダム値(u0,u1)及び(v0,v1)の一次元区間を得る手段であって、分離しているが同様な乱数発生器2個を備えており、ここで各乱数発生器は、
2つの数値TA及びTBを前記入力値“t”から算出する手段であって、TBが1未満の浮動小数値でありTA＋TBが1に等しいものと、
前記値TBをランダム値TTに投影する手段と、
2つの数値TTA及びTTBを前記値TTから算出する手段であって、TTBが1未満の浮動小数値でありTTA＋TTBが1に等しいものと、
ランダム値を生成する手段であって、前記パラメータの集合{TA,TTA}及び{TA,TTA+1}を用いる結果として2つのランダム値T1及びT2を生成するものと、
を具備し、
前記第3手段が、
ランダム値(u0,u1)及び(v0,v1)の一次元区間2個を結合して、二次元区間[(u0,v0),(u1,v1)]を得る手段であって、
一定の整数値であって以下“magic_mask”と称するものを用いる手段と、
2つの新規の数値であって以下“maskA”及び“maskB”と称するものを、前記2つのランダム値u0及びu1を用いて算出する手段と、
ランダム値を算出する手段であって、4組の入力{u0,v0,maskA},
{u0,v1,maskA}, {u1,v0,maskB}, 及び{u1,v1,maskB}を用いる結果としてランダム値R1, R2, R3, 及びR4を得るものと、
を具備するもの
を備え、
前記第5手段が、
UUB及びVVBを前記乱数発生器から得る手段であって、事前に指定された値TTBは、前記座標uが前記乱数発生器の入力として用いられた場合はUUBに等しく、また同様に、前記乱数発生器が前記座標vを入力として用いられた場合はVVBに等しいものと、
加重ランダム値を算出する手段であって、4組の入力{R1,
UUB, VVB}, {R2, UUB-1.0, VVB}, {R3, UUB, VVB-1.0}, 及び{R4,
UUB-1.0, VVB-1.0}を用いる結果として4つの加重値r1, r2, r3及びr4を得るものと、
ランダム値RVを、r1, r2, r3, r4,
UUB, 及びVVBを入力として用いて算出する手段で、双一次補間モジュールを具備するものであって、r1, r2, r3及びr4が補間された値であり、UUB及びVVBが補間用パラメータであるものと、
を備え、
前記システムが、
前記ランダム値の生成を制御する手段であって、
前記入力座標(u,v)を変更する手段と、
前記出力値RVを変更する手段と、
を具備するもの
をさらに備え、
前記第5手段が、前記RVと前記入力座標(u,v)とを結合して前記出力(u’,v’)を得る手段である、
システム。
【請求項４】
請求項１において、
前記システムが、
前記ランダム値の生成を制御する手段であって、
前記入力座標(u,v)を変更する手段であって、各入力u及びvについて、スケーリング、トランスレーション、及びクランピング演算を行い、スケーリング及びトランスレーション係数及びクランピング動作タイプを得る手段を具備するものと、
前記出力値RVを変更する手段であって、スケーリング及びトランスレーション演算を行い、スケーリング係数及びクランピング動作タイプを得る手段を具備するものと、
を具備するもの
をさらに備え、
前記第2手段が、
u又はv座標のいずれか（以下、“t”と称することもある。）を入力して2つのランダム値(u0,u1)及び(v0,v1)の一次元区間を得る手段であって、分離しているが同様な乱数発生器2個を備えており、ここで各乱数発生器は、
2つの数値TA及びTBを前記入力値“t”から算出する手段であって、TBが1未満の浮動小数値でありTA＋TBが1に等しいものと、
前記値TBをランダム値TTに投影する手段であって、
以下magic_shift1と称する一定値を得る手段と、
TBを前記区間[0,magic_shift1]内に投影する結果としてTTを得る手段と、
を具備するものと、
2つの数値TTA及びTTBを前記値TTから算出する手段であって、TTBが1未満の浮動小数値でありTTA＋TTBが1に等しいものと、
ランダム値を生成する手段であって、前記パラメータの集合{TA,TTA}及び{TA,TTA+1}を用いる結果として2つのランダム値T1及びT2をそれぞれ生成するものであって、
以下“magic_mask”, “magic_shift1”, 及び“magic_shift2”と称する一定値を定義して使用する手段と、
以下“maskT”と称する擬似ランダム値を、D値(TA又はTA+1のいずれかに対応した値)を用いて算出する手段と、
TA又はTA+1のいずれかを用い、且つ値TTA及び事前に算出した値“maskT”を用いて乱数Rを算出する手段と、
を具備するものと、
を備え、
前記第3手段が、
ランダム値(u0,u1)及び(v0,v1)の一次元区間2個を結合して、二次元区間[(u0,v0),(u1,v1)]を得る手段であって、
以下“magic_mask”と称する定数を得る手段と、
2つの新規の数値であって以下“maskA”及び“maskB”と称するものを、前記2つのランダム値u0及びu1を用いて算出する手段と、
独立して4回使用されるランダム値を算出する手段であって、4組の入力{u0,v0,maskA}, {u0,v1,maskA},
{u1,v0,maskB}, 及び{u1,v1,maskB}を用いる結果としてランダム値R1, R2, R3, 及びR4を得るものと、
を具備するもの
を備え、
前記第5手段が、
UUB及びVVBを前記乱数発生器から得る手段であって、事前に指定された数値TTBは、前記座標uが前記乱数発生器の入力として用いられた場合はUUBに等しく、また同様に、前記乱数発生器が前記座標vを入力として用いられた場合はVVBに等しいものと、
独立して4回使用される重ランダム値を算出する手段であって、4組の入力{R1, UUB, VVB}, {R2, UUB-1.0, VVB},
{R3, UUB, VVB-1.0}及び{R4, UUB-1.0, VVB-1.0}を用いる結果として4つの加重値r1, r2, r3, 及びr4を得るものと、
ランダム値RVを、r1, r2, r3, r4,
UUB, 及びVVBを入力として用い、また双一次補間モジュールを用いて算出する手段であって、r1, r2, r3及びr4が補間された値であり、UUB及びVVBが補間用パラメータであるものと、
UUB及びVVBを変更して双一次補間動作を制御する手段と、
前記ランダム値RVと前記入力座標(u,v)とを結合して出力(u’,v’)を得る手段と、
を備えたシステム。
【請求項５】
請求項１において、
前記第2手段が、
u又はv座標のいずれか（以下、“t”と称することもある。）を入力して2つのランダム値(u0,u1)及び(v0,v1)の一次元区間を得る、分離しているが同様な乱数発生器2個を用いて2つのランダム値の一次元区間を2個生成する手段であり、ここで各乱数発生器は、
2つの数値TA及びTBを前記入力値“t”から算出する手段であって、TBが1未満の浮動小数値でありTA＋TBが1に等しいものと、
前記値TBをランダム値TTに投影する手段であって、
以下“magic_shift1”と称する一定値を得る手段と、
TBを前記区間[0,magic_shift1]内に投影する結果としてTTを得る手段であって、単一のマルチプレクサを具備してTT =
TB*magic_shift1を計算するものと、
を具備するものと、
2つの数値TTA及びTTBを前記値TTから算出する手段であって、TTBが1未満の浮動小数値でありTTA＋TTBが1に等しいものと、
ランダム値を生成する手段であって、前記パラメータの集合{TA,TTA}及び{TA,TTA+1}を用いる結果として2つのランダム値T1及びT2をそれぞれ生成するものであって、
以下“magic_shift1”, “magic_mask”, 及び“magic_shift2”と称する一定値を得る手段と、
以下の値、すなわち以下“maskT”と称する擬似ランダム値を、TTA又はTTA+1のいずれかを入力として用いて算出する手段であり、“ifステートメント論理回路”、マルチプレクサ、及び論理右ビットシフト演算子(>>)を具備し、
もし、Dと表示され且つTTA又はTTA+1のいずれかに等しい前記入力値が、厳密に“magic_shift1”より低ければ、以下の値を算出し、
maskT = magic_mask>>(TA*magic_shift2)
さもなくば、以下の値を算出するものと、
maskT = magic_mask>>((TA+1)*magic_shift2);
Dと表示され且つTA又はTA+1のいずれかに等しい入力値及び“maskT”を入力として用いて乱数Rを算出する手段であって、“ifステートメント論理回路”、マルチプレクサ、及びビット論理演算子“XOR”(^で表す)を具備し、
もし、Dが“magic_shift1”より低ければ、以下の値を算出し、
R = ((1+TTA)*magic_shift2)^maskT
さもなくば、次の値を算出するものと、
R = ((1)*magic_shift2)^maskT
を具備するものと、
を備え、
前記第3手段が、
ランダム値(u0,u1)及び(v0,v1)の一次元区間2個を結合して、二次元区間[(u0,v0),(u1,v1)]を得る手段であって、
“magic_mask”を得る手段と、
以下“maskA”及び“maskB”と称する以下の2つの値を、前記2つのランダム値u0及びu1を用いて算出する手段であって、各maskの算出は、単一の論理右ビットシフト演算子を具備し、入力値“t”について次の計算をするものと、
mask = (magic_mask>>t)
ここで、“t”はu0又はu1のいずれかに等しく結果として得られる値“mask“t”は、それぞれ“maskA”又は“maskB”のいずれかに等しくなるものとし、
ランダム値を算出する手段であって、4組の入力{u0,v0,maskA},
{u0,v1,maskA}, {u1,v0,maskB}, 及び{u1,v1,maskB}を用いる結果としてランダム値R1, R2, R3, 及びR4を得るものであって、加算器及びビット論理XOR (^)演算子を具備し、各入力{s,t,mask}について次の値を算出するものと、
R=(s+t)^mask
を備え、
前記第5手段が、
UUB及びVVBを前記乱数発生器から得る手段であって、事前に指定された数値TTBは、前記座標uが前記乱数発生器の入力として用いられた場合はUUBに等しく、また同様に、前記乱数発生器が前記座標vを入力として用いられた場合はVVBに等しいものと、
独立して4回使用される加重ランダム値を算出する手段であって、4組の入力{R1, UUB, VVB}, {R2, UUB-1.0, VVB},
{R3, UUB, VVB-1.0}, 及び{R4, UUB-1.0, VVB-1.0}を用いる結果として4つの加重値r1, r2, r3, 及びr4を得るものであり、各モジュールが加算器及びマルチプレクサを具備し、各入力{R,a,b}について次の値を算出するものと、
r = R*(a+b)
ランダム値RVを、r1, r2, r3, r4,
UUB, 及びVVBを入力として用い、また双一次補間モジュールを用いて算出する手段であって、r1, r2, r3, 及びr4が補間された値であり、UUB及びVVBが補間用パラメータであるものであって、
UUB及びVVBを変更して双一次補間動作を制御する手段であって、
前記区間[0,1]におけるUUB及びVVBが定義されているときUUB及びVVBをUUB’及びVVB’にマッピングする参照テーブルと、
双一次補間動作用のパラメータとしてUUB’及びVVB’を用いて双一次補間を算出する手段と、
を具備したものと、
を備え、
前記システムが、
前記ランダム値の生成を制御する手段であって、
前記入力座標(u,v)を変更するために、各入力u及びvについて、スケーリング、トランスレーション、及びクランピング演算を行い、加算器、マルチプレクサ、及びクランピング回路で構成されたものと、スケーリング及びトランスレーション係数及びクランピング動作タイプを得る手段と、を具備するものと
前記出力値RVを変更する手段であって、スケーリング演算を行い、マルチプレクサで構成されたものと、スケーリング係数及びクランピング動作タイプを得る手段と、を具備するものと、
をさらに備え、
前記第5手段が、前記RVと前記入力座標(u,v)とを結合して出力(u’,v’)を得る手段であり、
2つの加算器及び2つの“ifステートメント論理回路”を具備し、独立してu’及びv’座標を以下のように求める：
もし(u>0) ならば u’=u+RV さもなくば
u’=u-RV
もし(v>0) ならば v’=v+RV さもなくば
v’=v-RV
システム。
【請求項６】
テクスチャ座標(u,v)を得る第1手段と、
前記テクスチャ座標(u,v)を一次元テクスチャ座標(t)に投影する第2手段と、
メモリに格納された一次元テクスチャ画像を、前記一次元テクスチャ座標(t)を用いてアクセスして獲得する第3手段と、
前記一次元テクスチャ画像を用いて二次元テクスチャ画像を生成する第4手段と、
を備えた二次元テクスチャ画像を生成するシステム。
【請求項７】
請求項６において、
前記第2手段が、
2つの関数G1及びG2を複数の固定関数から選択する手段と、
あらゆる実関数、以下Fと称する、を表す参照テーブルを定義する手段と、
前記関数G1、G2、及びFを結合する手段と、
を備えたシステム。
【請求項８】
請求項６において、
前記第2手段が、
2つの関数G1及びG2を、{u, v, u+v, u-v, u^2, v^2, sqrt(u2+v2),
u+v+sqrt(u2+v2), u+v-sqrt(u2+v2), min(u,v), max(u,v), constant}に等しい関数G(u,v)から選択する手段であって、“sqrt”は数学関数である平方根であり、x^2はxの二乗(xのx倍)であるものと、
あらゆる実関数で以下Fと称するものを表す参照テーブルを定義する手段と、
前記関数G1、G2、及びFを結合する手段であって、
G1を参照テーブルFのの入力として用い、これによりF(G1(u,v))を算出する手段と、参照テーブルの出力とG2を用いて、参照テーブルの出力とG2との積を算出して、結果として値値F(G1 (u,v))*G2(u.v)を得る手段と、
を具備するものと、
を備え、
前記第3手段が、一次元テクスチャ画像F(G1
(u,v))*G2(u.v)を用いるシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、擬似ランダム・テクスチャ・パターンの生成に関する。一次元テクスチャ画像が、二次元画像テクスチャを生成するフレームワークとして用いられる。より正確には、二次元テクスチャ画像に一次元テクスチャを投影する特殊な投影法を用いて二次元画像テクスチャが生成される。
【背景技術】
【０００２】
コンピュータ・グラフィックスにおいては、幾何学的なオブジェクトが二次元表示システムに表示される。結果として得られる画像の現実性を向上させるため、幾何学図形はテクスチャと組み合わされることが多い。テクスチャは画像として、あるいはパターンとして、オブジェクトの表面に塗られているように見える。例えば、二次元表示システム上に山を描くには、四辺形を形状として使用し、山の画像をテクスチャとして使用することができる。山の画像はテクスチャ座標を用いて形状に加えることができる。形状の各ポイント毎に、1つのテクスチャ座標が定義される。このテクスチャ座標は、画像の中の配置をも定義する。幾何学空間と画像空間との対応付けはテクスチャ・マッピングと呼ばれている。従来のコンピュータ・グラフィックス・システムにおいては、幾何学的なオブジェクトが描画され、二次元表示システム上のポイントに対応するオブジェクトの各ポイントについて、対応するテクスチャ座標を使用することにより、テクスチャ画像におけるポイントを決定し、その結果或る色が得られる。そして、この色が表示されるのである。この説明は、非常に簡略化したものである。テクスチャリング及びテクスチャマッピングはコンピュータ・グラフィックスにおいて一般的な技術である。例えば、非特許文献[非特許文献1]参照。この技術を、以下、静的二次元テクスチャと称する。
【０００３】
あるオブジェクトに二次元テクスチャ画像をマッピングすることはコンピュータ・グラフィックスにおいて徹底的に使用されており、非常に有効である。とはいえ、オブジェクトによっては、この技術が最適のものではないこともある。例えば、壁を考えてみると、どこも同じパターンを示しており、微々たる変化があるだけ、すなわち、煉瓦とモルタルで出来た壁は同じ煉瓦・モルタルをどこでも示しているように見える、しかし注意深く見ると違いが見えてくる（例えば、モルタルが多少厚いなど）。このような、反復性があるが異なるパターンを生成するには、二次元テクスチャに対する代替手段（あるいは、拡張手段）が存在する。それは、プロシージャル・テクスチャと呼ばれるものである。静的二次元画像を使用する代わりに、ある関数（プロシージャ）を用いて擬似ランダムパターンをいくつか生成する。プロシージャル・テクスチャ技術の説明は非特許文献2（D. Ebert等「テクスチャリング及びモデリング：プロシージャル手法」）に記載されている。この技術を、以下、プロシージャル・テクスチャと称する。なお、プロシージャル・テクスチャは二次元テクスチャと組み合わせて使用することができる。プロシージャル関数が入力テクスチャ座標に摂動を与えた後、摂動された入力座標が使用され、二次元テクスチャ画像を用いた出力色が定義される。
【０００４】
静的及びプロシージャルの両技術において、与えられた入力テクスチャ座標(u, v)毎に出力色を定義するためにさまざまな計算が行われる。静的二次元テクスチャでは、主に、テクスチャ座標を画像空間の或るポイントにマッピングすることにより或る色を定義するためのマッピング機能で構成され、また、プロシージャル関数としては、例えば入力座標(u,v)を(u’,v’)にマッピングする特別な関数が定義されており、その後、(u’,v’)がテクスチャ・マッピング機能に使用される。
【０００５】
この書面では、静的二次元テクスチャとプロシージャル・テクスチャとの中間に存在するテクスチャリングの新規技術を提案し、さらに、新規のテクスチャ・マッピング技術も提案する。この新規技術は以下のように要約できる。或る入力テクスチャ座標(u,v)が与えられると、まず、雑音関数を用いて(u,v)に摂動を与え、(u’,v’)を得た後、特別のマッピング・ユニットが二次元テクスチャ座標(u’,v’)を一次元テクスチャ座標(t)にマッピングする。次に、この一次元テクスチャ座標を用いて一次元テクスチャ画像が指定される。
【０００６】
この新しい技術を使用することにより、興味深いテクスチャを得ることができる。それは、異なる二つの種類に分類することができる。
【０００７】
摂動が与えられない場合には、通常の幾何学的テクスチャが得られる。このようなテクスチャの例としては、例えば、グレア（けばけばしさ）、フレア（ゆらめき）、ハロー（円光）、又は薄い織物の表面の反復的モチーフ（四角、丸等）。特定の二次元から一次元へのマッピング機能に関する特許文献は見つからなかった。
【０００８】
摂動が使用された場合には、木や大理石のような自然に見えるテクスチャが得られる。摂動モジュールを用いて得られる視覚的な結果は、非特許文献2（D. Ebert等「テクスチャリング及びモデリング：プロシージャル手法」）で提案されている結果に近い。この書面で提案されているものは、摂動モジュールに基づくものである。このモジュールの動作は特許文献（K. Perlin 「雑音対応方法及び装置」）W0 01/39126 A1（特許文献1）で提案された雑音関数にどことなく類似している。入力及び出力は類似しているが、出力値を得る手段が異なっている。雑音関数は三つのステップに依存している。例えば、何らかのハッシュ値を計算し、グラディエントを計算し、これらの値を補間して一つの値を得る。本発明の一実施例は、これらのステップの変形例によるものである。ハッシュ値の計算は置換表に依存しており、ハッシュ値はグラディエントを計算するのに使用される。本発明の好適な実施例の一つは、表やグラディエントを使用せず、非常に簡単な乱数発生とこれらの乱数の重み付け関数によるものである。本発明の別の実施例は補間手法を参照しており、摂動のパラメータ化を増大し、ひいては結果として得られるテクスチャの見栄えを向上させる特定の回路を提案している。全ての実施例を組み合わせると特許文献W0 01/39126 A1(特許文献1)で提案された雑音モジュールとは異なるモジュールを規定することになる。
【０００９】
他の同様なモジュールは、特許文献（K. Perlin  「Perlinノイズ用基準」米国特許番号第6,867,776 B2号(特許文献2)に規定されている。W0
01/39126 A1(特許文献1)と同様に、ハッシュ値及びグラディエントが使用されている。本発明の好適な一実施例は、ハッシュ値及びグラディエントを使用しないが、重み付けランダム値に基づいている。特許文献2に記載された方法は双一次補間を用いていないが、代わりに球面カーネルと呼ばれる関数を用いている。
【００１０】
【特許文献１】Perlin Kenneth, 「雑音対応方法及び装置」国際公開番号第WO 01/39126 A1号
【特許文献２】Perlin Kenneth, 「Perlinノイズ用基準」米国特許番号第6,867,776 B2号
【非特許文献１】J.D. Foly, A. Van Dam, S.K. Feiner, 及びJ.F. Hugues「コンピュータ・グラフィックス：原理と実践」第2版, ADDISON-WESLY, ISBN: 0-201-84840-6,1995.
【非特許文献２】D. Ebert等「テクスチャリング及びモデリング：プロシージャル手法」第3版, Morgan Kaufmann Publishers, ISBN1-55860-848-6, 2003
【発明の開示】
【発明が解決しようとする課題】
【００１１】
コンピュータ・グラフィックスにおいては、二次元テクスチャ画像を作成し表示するとき、テクスチャ・ユニットというモジュールを使用するのが一般的である。これは、二次元座標(u,v)、いわゆるテクスチャ座標を用いて、メモリに格納された二次元画像の特定の位置にアクセスするインデックスを計算するものである。インデックス計算には、膨大な計算が必要であり、二次元画像を格納することはメモリの観点から費用がかかる。この技術は静的、すなわちメモリに格納された二次元画像次第で様々な画像結果を得るための構成パラメータが非常に少ないものである。
【００１２】
木、石等といった、いわゆるナチュラル・テクスチャ用には、プロシージャル・テクスチャと呼ばれる別の手法がある。しかし、プロシージャル・テクスチャを作成するには、プログラム制御可能な回路（フラグメントシェーダと呼ばれる）が必要であることが多い。このような汎用のプログラム制御可能なハードウェア回路は通常グラフィックチップの重要な部分をなしており、ハードウェアの大きさの観点から非常に大きいものである。
【００１３】
開示された発明の関心事はナチュラル・テクスチャ、又は擬似ランダム反復性テクスチャの生成であり、さらには幾何学的な規則性を示すテクスチャ（例えば、グレア、フレア、ハロー、又は薄い織物の表面に印刷された反復的モチーフ）の生成である。静的二次元テクスチャ及びプロシージャルテクスチャは共に、このようなテクスチャを作成することができる。提案された発明では、二次元テクスチャ画像を生成するためにギャップを埋めることを提案する。これは、完全に静的な二次元テクスチャとプロシージャル・テクスチャとの間のトレードオフである。この書面で開示されている一連の回路はいくつかの構成パラメータを提供するが、静的二次元テクスチャよりも高い柔軟性（但し、フラグメントシェーダにおいて定義されているプロシージャル・テクスチャよりは低い柔軟性）を、フラグメント・シェーダよりも（また、静的二次元テクスチャよりも）ずっと小さい回路規模で可能にする。
【課題を解決するための手段】
【００１４】
メモリサイズ及び回路規模の要件の問題を解決するために使用するシステムは次のように分解することができる。前節で列挙した問題を解決するため、三つの手段が組み合わされたものが使われる。
【００１５】
二次元テクスチャの代わりに一次元テクスチャを使用し、メモリサイズの要件を緩和する。
入力二次元テクスチャ座標を摂動する専用の回路を使用し、結果として得られる二次元テクスチャにおいて目に見える変形を行う。
【００１６】
専用のマッピング回路で設定(変更)可能なものを使用し、摂動された二次元テクスチャ座標を一次元出力テクスチャ座標にマッピングし、これをメモリに格納された一次元テクスチャ画像のアドレス指定に用いる。
【００１７】
第1の態様：プロシージャル一次元擬似ランダム・パターン生成
本発明の第1の態様が対象とするのは、コンピュータ・システムにおいて二次元テクスチャ座標を算出するシステムであって、二次元テクスチャ座標(u,v)を求める第1手段と、前記座標u及びvを用いて2つのランダム値の一次元区間(interval)を2個生成する第2手段と、前記ランダム値の一次元区間2個を結合して、4つのランダム値の二次元区間を1個生成する第3手段と、前記テクスチャ座標(u,v)及び前記4つのランダム値の二次元区間に応じて、ランダム値を生成する第4手段と、前記ランダム値と前記入力テクスチャ座標(u,v)を結合して、変換された前記二次元テクスチャ座標(u’,v’)を得る第5手段と、を備えたことを特徴とするシステムである。
【００１８】
本発明の第1の態様の好適な例の一つは、上記において、前記第2手段が、u又はv座標のいずれかを入力して2つのランダム値(u0,u1)及び(v0,v1)の前記一次元区間を得る、分離しているが同様な（identical）乱数発生器2個を具備しており、前記第3手段が、前記ランダム値(u0,u1)及び(v0,v1)の一次元区間2個を結合して二次元区間[(u0,v0),(u1,v1)]を得ることを特徴としたシステムである。
【００１９】
本発明の第1の態様の好適な一例は、上記において、前記第2手段が、u又はv座標のいずれか（以下、“t”と称することもある。）を入力して2つのランダム値(u0,u1)及び(v0,v1)の一次元区間を得る手段であって、分離しているが同様な乱数発生器2個を備えており、ここで各乱数発生器は、2つの数値TA及びTBを前記入力値“t”から算出する手段であって、TBが1未満の浮動小数値でありTA＋TBが1に等しいものと、前記値TBをランダム値TTに投影する手段と、2つの数値TTA及びTTBを前記値TTから算出する手段であって、TTBが1未満の浮動小数値でありTTA＋TTBが1に等しいものと、ランダム値を生成する手段であって、前記パラメータの集合{TA,TTA}及び{TA,TTA+1}を用いる結果として2つのランダム値T1及びT2を生成するものと、を具備し、前記第3手段が、ランダム値(u0,u1)及び(v0,v1)の一次元区間2個を結合して、二次元区間[(u0,v0),(u1,v1)]を得る手段であって、一定の整数値であって以下“magic_mask”と称するものを用いる手段と、2つの新規の数値であって以下“maskA”及び“maskB”と称するものを、前記2つのランダム値u0及びu1を用いて算出する手段と、ランダム値を算出する手段であって、4組の入力{u0,v0,maskA}, {u0,v1,maskA},
{u1,v0,maskB}, 及び{u1,v1,maskB}を用いる結果としてランダム値R1, R2, R3, 及びR4を得るものと、を具備するものを備え、前記第5手段が、UUB及びVVBを前記乱数発生器から得る手段であって、事前に指定された値TTBは、前記座標uが前記乱数発生器の入力として用いられた場合はUUBに等しく、また同様に、前記乱数発生器が前記座標vを入力として用いられた場合はVVBに等しいものと、加重ランダム値を算出する手段であって、4組の入力{R1, UUB, VVB}, {R2, UUB-1.0, VVB}, {R3, UUB, VVB-1.0}, 及び{R4, UUB-1.0, VVB-1.0}を用いる結果として4つの加重値r1, r2, r3及びr4を得るものと、ランダム値RVを、r1, r2, r3, r4, UUB, 及びVVBを入力として用いて算出する手段で、双一次補間モジュールを具備するものであって、r1,
r2, r3及びr4が補間された値であり、UUB及びVVBが補間用パラメータであるものと、を備え、前記システムが、前記ランダム値の生成を制御する手段であって、前記入力座標(u,v)を変更する手段と、前記出力値RVを変更する手段と、を具備するものをさらに備え、前記第5手段が、前記RVと前記入力座標(u,v)とを結合して前記出力(u’,v’)を得る手段であるシステムである。
【００２０】
本発明の第1の態様の好適な一例は、上記のいずれかにおいて、前記システムが、前記ランダム値の生成を制御する手段であって、前記入力座標(u,v)を変更する手段であって、各入力u及びvについて、スケーリング、トランスレーション、及びクランピング演算を行い、スケーリング及びトランスレーション係数及びクランピング動作タイプを得る手段を具備するものと、前記出力値RVを変更する手段であって、スケーリング及びトランスレーション演算を行い、スケーリング係数及びクランピング動作タイプを得る手段を具備するものと、を具備するものをさらに備え、前記第2手段が、u又はv座標のいずれか（以下、“t”と称することもある。）を入力して2つのランダム値(u0,u1)及び(v0,v1)の一次元区間を得る手段であって、分離しているが同様な乱数発生器2個を備えており、ここで各乱数発生器は、2つの数値TA及びTBを前記入力値“t”から算出する手段であって、TBが1未満の浮動小数値でありTA＋TBが1に等しいものと、前記値TBをランダム値TTに投影する手段であって、以下magic_shift1と称する一定値を得る手段と、TBを前記区間[0,magic_shift1]内に投影する結果としてTTを得る手段と、を具備するものと、2つの数値TTA及びTTBを前記値TTから算出する手段であって、TTBが1未満の浮動小数値でありTTA＋TTBが1に等しいものと、ランダム値を生成する手段であって、前記パラメータの集合{TA,TTA}及び{TA,TTA+1}を用いる結果として2つのランダム値T1及びT2をそれぞれ生成するものであって、以下“magic_mask”, “magic_shift1”, 及び“magic_shift”と称する一定値を定義して使用する手段と、以下“maskT”と称する擬似ランダム値を、D値(TA又はTA+1のいずれかに対応した値)を用いて算出する手段と、TA又はTA+1のいずれかを用い、且つ値TTA及び事前に算出した値“maskT”を用いて乱数Rを算出する手段と、を具備するものと、を備え、前記第3手段が、ランダム値(u0,u1)及び(v0,v1)の一次元区間2個を結合して、二次元区間[(u0,v0),(u1,v1)]を得る手段であって、以下“magic_mask”と称する定数を得る手段と、2つの新規の数値であって以下“maskA”及び“maskB”と称するものを、前記2つのランダム値u0及びu1を用いて算出する手段と、独立して4回使用されるランダム値を算出する手段であって、4組の入力{u0,v0,maskA}, {u0,v1,maskA}, {u1,v0,maskB}, 及び{u1,v1,maskB}を用いる結果としてランダム値R1, R2, R3, 及びR4を得るものと、を具備するものを備え、前記第5手段が、UUB及びVVBを前記乱数発生器から得る手段であって、事前に指定された数値TTBは、前記座標uが前記乱数発生器の入力として用いられた場合はUUBに等しく、また同様に、前記乱数発生器が前記座標vを入力として用いられた場合はVVBに等しいものと、独立して4回使用される重ランダム値を算出する手段であって、4組の入力{R1, UUB, VVB}, {R2, UUB-1.0, VVB},
{R3, UUB, VVB-1.0}及び{R4, UUB-1.0, VVB-1.0}を用いる結果として4つの加重値r1, r2, r3, 及びr4を得るものと、ランダム値RVを、r1, r2, r3, r4, UUB, 及びVVBを入力として用い、また双一次補間モジュールを用いて算出する手段であって、r1,
r2, r3及びr4が補間された値であり、UUB及びVVBが補間用パラメータであるものと、UUB及びVVBを変更して双一次補間動作を制御する手段と、前記ランダム値RVと前記入力座標(u,v)とを結合して出力(u’,v’)を得る手段と、を備えたシステムである。
【００２１】
本発明の第1の態様の好適な一実施例は、上記のいずれかにおいて、前記第2手段が、u又はv座標のいずれか（以下、“t”と称することもある。）を入力して2つのランダム値(u0,u1)及び(v0,v1)の一次元区間を得る、分離しているが同様な乱数発生器2個を用いて2つのランダム値の一次元区間を2個生成する手段であり、ここで各乱数発生器は、2つの数値TA及びTBを前記入力値“t”から算出する手段であって、TBが1未満の浮動小数値でありTA＋TBが1に等しいものと、前記値TBをランダム値TTに投影する手段であって、以下“magic_shift1”と称する一定値を得る手段と、TBを前記区間[0,magic_shift1]内に投影する結果としてTTを得る手段であって、単一のマルチプレクサを具備してTT = TB*magic_shift1を計算するものと、を具備するものと、2つの数値TTA及びTTBを前記値TTから算出する手段であって、TTBが1未満の浮動小数値でありTTA＋TTBが1に等しいものと、ランダム値を生成する手段であって、前記パラメータの集合{TA,TTA}及び{TA,TTA+1}を用いる結果として2つのランダム値T1及びT2をそれぞれ生成するものであって、以下“magic_shift1”, “magic_mask”, 及び“magic_shift2”と称する一定値を得る手段と、以下の値、すなわち以下“maskT”と称する擬似ランダム値を、TTA又はTTA+1のいずれかを入力として用いて算出する手段であり、“ifステートメント論理回路”、マルチプレクサ、及び論理右ビットシフト演算子(>>)を具備し、もし、Dと表示され且つTTA又はTTA+1のいずれかに等しい前記入力値が、厳密に“magic_shift1”より低ければ、以下の値を算出し、
maskT = magic_mask>>(TA*magic_shift2)
さもなくば、以下の値を算出するものと、
maskT = magic_mask>>((TA+1)*magic_shift2);
Dと表示され且つTA又はTA+1のいずれかに等しい入力値及び“maskT”を入力として用いて乱数Rを算出する手段であって、“ifステートメント論理回路”、マルチプレクサ、及びビット論理演算子“XOR”(^で表す)を具備し、もし、Dが“magic_shift1”より低ければ、以下の値を算出し、R = ((1+TTA)*magic_shift2)^maskT
さもなくば、次の値を算出するものと、R = ((1)*magic_shift2)^maskTを具備するものと、
を備え、前記第3手段が、ランダム値(u0,u1)及び(v0,v1)の一次元区間2個を結合して、二次元区間[(u0,v0),(u1,v1)]を得る手段であって、 “magic_mask”を得る手段と、以下“maskA”及び“maskB”と称する以下の2つの値を、前記2つのランダム値u0及びu1を用いて算出する手段であって、各maskの算出は、単一の論理右ビットシフト演算子を具備し、入力値“t”について次の計算をするものと、mask =
(magic_mask>>t)ここで、“t”はu0又はu1のいずれかに等しく結果として得られる値“mask”は、それぞれ“maskA”又は“maskB”のいずれかに等しくなるものとし、ランダム値を算出する手段であって、4組の入力{u0,v0,maskA}, {u0,v1,maskA},
{u1,v0,maskB}, 及び{u1,v1,maskB}を用いる結果としてランダム値R1, R2, R3, 及びR4を得るものであって、加算器及びビット論理XOR (^)演算子を具備し、各入力{s,t,mask}について次の値を算出するものと、R=(s+t)^maskを備え、前記第5手段が、UUB及びVVBを前記乱数発生器から得る手段であって、事前に指定された数値TTBは、前記座標uが前記乱数発生器の入力として用いられた場合はUUBに等しく、また同様に、前記乱数発生器が前記座標vを入力として用いられた場合はVVBに等しいものと、独立して4回使用される加重ランダム値を算出する手段であって、4組の入力{R1, UUB, VVB}, {R2, UUB-1.0, VVB},
{R3, UUB, VVB-1.0}, 及び{R4, UUB-1.0, VVB-1.0}を用いる結果として4つの加重値r1, r2, r3, 及びr4を得るものであり、各モジュールが加算器及びマルチプレクサを具備し、各入力{R,a,b}について次の値r = R*(a+b)を算出するものと、ランダム値RVを、r1, r2, r3, r4, UUB, 及びVVBを入力として用い、また双一次補間モジュールを用いて算出する手段であって、r1,
r2, r3, 及びr4が補間された値であり、UUB及びVVBが補間用パラメータであるものであって、UUB及びVVBを変更して双一次補間動作を制御する手段であって、前記区間[0,1]におけるUUB及びVVBが定義されているときUUB及びVVBをUUB’及びVVB’にマッピングする参照テーブルと、双一次補間動作用のパラメータとしてUUB’及びVVB’を用いて双一次補間を算出する手段と、を具備したものと、を備え、前記システムが、前記ランダム値の生成を制御する手段であって、前記入力座標(u,v)を変更するために、各入力u及びvについて、スケーリング、トランスレーション、及びクランピング演算を行い、加算器、マルチプレクサ、及びクランピング回路で構成されたものと、スケーリング及びトランスレーション係数及びクランピング動作タイプを得る手段と、を具備するものと、前記出力値RVを変更する手段であって、スケーリング演算を行い、マルチプレクサで構成されたものと、スケーリング係数及びクランピング動作タイプを得る手段と、を具備するものと、をさらに備え、前記第5手段が、前記RVと前記入力座標(u,v)とを結合して出力(u’,v’)を得る手段であり、2つの加算器及び2つの“ifステートメント論理回路”を具備し、独立してu’及びv’座標を以下のように求める：もし(u>0)
ならば u’=u+RV さもなくば u’=u-RV、もし(v>0) ならば v’=v+RV さもなくば v’=v-RV、システムである。
【００２２】
第2の態様：一次元テクスチャ画像及び設定可能な二次元から一次元へのマッピング関数を用いた二次元テクスチャ画像生成
【００２３】
本発明の第2の態様が対象とするのは、テクスチャ座標(u,v)を得る第1手段と、前記テクスチャ座標(u,v)を一次元テクスチャ座標(t)に投影する第2手段と、メモリに格納された一次元テクスチャ画像を、前記一次元テクスチャ座標(t)を用いてアクセスして獲得する第3手段と、前記一次元テクスチャ画像を用いて二次元テクスチャ画像を生成する第4手段と、を備えたことを特徴とする、二次元テクスチャ画像を生成するシステムである。本発明の第2の態様の好適な一例が対象とするのは、上記において、前記第2手段が、2つの関数G1及びG2を複数の固定関数から選択する手段と、あらゆる実関数、以下Fと称する、を表す参照テーブルを定義する手段と、前記関数G1、G2、及びFを結合する手段と、を備えたシステムである。
【００２４】
本発明の第2の態様の好適な例は、上記において、前記第2手段が、2つの関数G1及びG2を、{u, v, u+v, u-v, u^2, v^2, sqrt(u2+v2),
u+v+sqrt(u2+v2), u+v-sqrt(u2+v2), min(u,v), max(u,v), constant}に等しい関数G(u,v)から選択する手段であって、“sqrt”は数学関数である平方根であり、x^2はxの二乗(xのx倍)であるものと、あらゆる実関数で以下Fと称するものを表す参照テーブルを定義する手段と、前記関数G1、G2、及びFを結合する手段であって、G1を参照テーブルFのの入力として用い、これによりF(G1(u,v))を算出する手段と、参照テーブルの出力とG2を用いて、参照テーブルの出力とG2との積を算出して、結果として値値F(G1 (u,v))*G2(u.v)を得る手段と、を具備するものと、を備え、前記第3手段が、一次元テクスチャ画像F(G1 (u,v))*G2(u.v)を用いるシステムである。
【発明の効果】
【００２５】
本発明は、新しい一連の簡単な関数に基づく新しいグラフィック回路であって、グラフィック・チップに回路として容易に実装可能なものを提供することが出来る。
本発明は、新しいグラフィック回路であって、バッファ・アクセス無しに従来のテクスチャ関連技術より少ない動作でメモリのコストを削減することが可能なものを提供することが出来る。
本発明は、一次元入力テクスチャ画像から二次元テクスチャ画像を与えるシステムを提供することが出来、設定を変えれば、二次元テクスチャ画像が興味深い視覚的な特性、例えば擬似的なランダム性（でたらめさ）、反復性等、いわゆるナチュラル・テクスチャ（木、大理石等）に見られる特性だけでなく、幾何学的な特徴（グレア、ハロー、薄い織物の表面に印刷されたモチーフ等）を有するテクスチャも表示することが出来る。
【発明を実施するための最良の形態】
【００２６】
従来のテクスチャ・ユニット（コンピュータ・グラフィックスにおいては周知のユニット）は通常次のような役割を担っている。或る入力テクスチャ座標(u,v)が与えられると、出力色RGBA（赤、緑、青、及びアルファ）を生成するために、さまざまな計算が行われる。RGBAにおいて、アルファは一般的に透明性を示している。「課題を解決する手段」の節で説明した三つの手段は、組み合わせると完全なテクスチャ・ユニットを成す。入力二次元テクスチャ座標(u,v)が与えられると、出力色RGBAが生成される。図1は、提案された手段をモジュールに分解した様子を示している。第１段階では、(u,v)座標を摂動し、結果として(u’,v’)を得る。第2段階では、二次元座標(u,v)を一次元座標tにマッピングし、最終段階では、一次元座標tを一次元テクスチャ画像を含む参照テーブルにおけるインデックスとして使用する。図1は、開示された発明を2つのモジュールに分解した様子を示している。入力二次元テクスチャ座標(u,v)が与えられると、モジュール1000（摂動部）が(u,v)を変更し、結果として(u’,v’)を得た後、これらが二次元座標を一次元座標tに対応付けるモジュール3000 CMapの入力として使用される。この一次元座標は、されにモジュール5000における一次元テクスチャ参照テーブルにおけるインデックスとして使用される。
【００２７】
第1の態様：プロシージャル一次元擬似ランダム・パターン生成
モジュール1000：PERTUBATER 
発明の第1の態様は入力二次元テクスチャ座標(u,v)の摂動に関する。Pertubaterモジュールは、コンピュータ・システムにおいて二次元テクスチャ座標を算出するシステムであって、二次元テクスチャ座標(u,v)を求める第1手段と、前記座標u及びvを用いて2つのランダム値の一次元区間を2個生成する第2手段と、前記ランダム値の一次元区間2個を結合して、4つのランダム値の二次元区間を1個生成する第3手段と、前記テクスチャ座標(u,v)及び前記4つのランダム値の二次元区間に応じて、ランダム値を生成する第4手段と、前記ランダム値と前記入力テクスチャ座標(u,v)を結合して、変換された前記二次元テクスチャ座標(u’,v’)を得る第5手段と、を備えたことを特徴とするシステムである。
【００２８】
第1手段がu及びvを求める。第2手段がu及びvを得て2個の一次元区間を生成する。第3手段が、一次元区間2個を結合して4つのランダム値の二次元区間を得る。第4手段が、二次元区間値を得てランダム値を生成する。第5手段が、ランダム値と入力テクスチャ座標(u,v)を結合して、二次元テクスチャ座標を摂動した(u’,v’)を得る。
【００２９】
第1のシステムでは、いずれかの先行するモジュールからの通常のバス入力について説明した。第2のシステムは、2つ乱数発生器で構成された汎用モジュールである。この汎用モジュールにおいては、乱数発生器の数が使用される。例えば、2回、1回目は入力uを用い、2回目は入力vを用いる。4つのランダム値が生成される。このとき、(u0, u1)はuを入力とし、(v0,
v1)はvを入力とするものである。図2は、モジュール1000 Perturbaterをサブモジュールに分解した様子を示している。以下、これらの各サブモジュールについて説明する。
【００３０】
モジュール1100：random1D
random1Dモジュールは、モジュール1000内で2回インスタンス化される。また、座標u及びvについて別々に使用される。或る入力座標tが与えられると、このモジュールのタスクは2つのランダム値及び浮動小数値を生成し、これらは後にそれぞれ、random2Dモジュール(1200)及びランダム結合（randomCombiner）モジュール(1300)で使用される。ランダム値の生成を担当するモジュールは、以下、pseudoRandomGenerator1Dと称する（このモジュールはモジュールrandom1D内で2回インスタンス化され、random1Dモジュールが2回インスタンス化されるので、このモジュールのインスタンスが合計で4つ存在することになる)。
【００３１】
モジュールpseudoRandomGenerator1Dの機能は以下の通りである。これは、3つの“magic”数を使用する。これらの数が単に符号なしの整数であり興味深いビット表現を有していると定義すれば十分である。第1のmagic数は“magic mask”と称することとし、符号なしの長い値(32ビット)である。他の2つを以下、“magic_shift1”及び“magic_shift2”と称することとし、それぞれ4ビット値及び8ビット値である。3つのmagic数は全て定数である。提案されるビット長は、説明のために示されたものである。開示された発明を大幅に変更すれば、他のビット長も選択することが出来る。これらのビット長を使用する主な利点は、このモジュールの超小型化（ハードウエアの観点で）である。
【００３２】
まず、入力パラメータt(u又はvに等しいもの)が2つの値、TA及びTBに、但し、TBが1未満であり、TA+TBがtに等しくなるように分解される。値TAは、以下のように定義されるmaskTと呼ばれる値を生成するのに使用される。
【００３３】
MaskT= (magic_mask >>
((TA*magic_shift2)&0xF))&0xF (1)
ここで、&はビットのAND演算であり、&0xFは最初の4ビット(最下位)が考慮される、言い換えれば、maskTは4ビット値であり、このことがこの関数を非常に小さな回路で実現可能にしている。明確さのために&0xFと書くが、実際のハードウェア実装においては、この演算は適正な回路実装により暗黙的に定義することが出来る。
【００３４】
一方、(すなわち、平行して)、別の回路を用いて値TBを区間[0, magic_shift1]に投影し、この投影の結果が値TTである。
TT = (TB)*magic_shift1.  (2)
同様に、値TTが2つの部分、TTA及びTTBに分解されるが、このとき、TTBが1未満であり、TTA+TTBがTTに等しくなる。値TTBは、モジュールrandomCombiner(1300)において使用される。
【００３５】
値TTAは、事前に計算されたmaskT（式(1)参照）と共に、実際に乱数を発生するのに使用される。次に、TTAに対応するランダム値は以下のように定義される：
t0=((((1+TTA)*magic_shift2)&0xF)^MaskT)&0xF       (3)
【００３６】
出力は、4ビット値として定義される乱数（むろん、擬似乱数）である。モジュール1100 Random1Dは実際に2つのランダム値を、与えられた入力座標tについて生成する。この理由は、入力座標tをランダム空間の区間にマッピングしたいからである。このモジュールの目的は、2つのランダム値を定義することであって、t及びその周辺の区間が投影されるランダム空間に或る区間を定義することではない。言い換えれば、ランダム値は各tの値について生成されるべきではなく、むしろ或るランダム区間がtに隣接している区間に対して定義されるべきである。
【００３７】
区間を生成する場合は、連続性を考慮すべきであり、もし、或る与えられた入力値についてランダム空間における区間[R0,R1]が生成されるならば、次の区間は[R1,R2]でなければならないということを保証しなければならない。式(3)から分かるように、値TTは区間[0,
magic_shift1]内にある。一定の連続性を保証するためには、TTAが値“magic_shift1”に等しいケースを特別のプロシージャが扱うべきである。TTAが値“magic_shift1”以上である場合には、式(1)及び(3)がそれぞれ以下のようになる：
MaskT= (magic_mask >>
(((TA+1)*magic_shift2)&0xF))&0xF     (1’)
t0=((((1)*magic_shift2)&0xF)^MaskT)&0xF                    (3’)
先に言及したように、非常に小さなビット幅で十分である。
【００３８】
モジュールpseudoRandomGenerator1Dの好適な例は、前記第2手段が、u又はv座標のいずれか（以下、“t”と称することもある。）を入力して2つのランダム値(u0,u1)及び(v0,v1)の一次元区間を得る、分離しているが同様な乱数発生器2個を用いて2つのランダム値の一次元区間を2個生成する手段であり、ここで各乱数発生器は、2つの数値TA及びTBを前記入力値“t”から算出する手段であって、TBが1未満の浮動小数値でありTA＋TBが1に等しいものと、前記値TBをランダム値TTに投影する手段であって、以下“magic_shift1“t”と称する一定値を得る手段と、TBを前記区間[0,magic_shift1]内に投影する結果としてTTを得る手段であって、単一のマルチプレクサを具備してTT = TB*magic_shift1を計算するものと、を具備するものと、2つの数値TTA及びTTBを前記値TTから算出する手段であって、TTBが1未満の浮動小数値でありTTA＋TTBが1に等しいものと、ランダム値を生成する手段であって、前記パラメータの集合{TA,TTA}及び{TA,TTA+1}を用いる結果として2つのランダム値T1及びT2をそれぞれ生成するものであって、以下“magic_shift1”, “magic_mask”, 及び“magic_shift2”と称する一定値を得る手段と、以下の値、すなわち以下“maskT”と称する擬似ランダム値を、TTA又はTTA+1のいずれかを入力として用いて算出する手段であり、“ifステートメント論理回路”、マルチプレクサ、及び論理右ビットシフト演算子(>>)を具備し、もし、Dと表示され且つTTA又はTTA+1のいずれかに等しい前記入力値が、厳密に“magic_shift1”より低ければ、以下の値を算出し、
maskT = magic_mask>>(TA*magic_shift2)
さもなくば、以下の値を算出するものと、
maskT = magic_mask>>((TA+1)*magic_shift2);
Dと表示され且つTA又はTA+1のいずれかに等しい入力値及び“maskT”を入力として用いて乱数Rを算出する手段であって、“ifステートメント論理回路”、マルチプレクサ、及びビット論理演算子“XOR”(^で表す)を具備し、もし、Dが“magic_shift1”より低ければ、以下の値R =
((1+TTA)*magic_shift2)^maskTを算出し、さもなくば、次の値R =
((1)*magic_shift2)^maskTを算出するものと、を具備するものと、を備え、前記第3手段が、ランダム値(u0,u1)及び(v0,v1)の一次元区間2個を結合して、二次元区間[(u0,v0),(u1,v1)]を得る手段であって、
“magic_mask”を得る手段と、以下“maskA”及び“maskB”と称する以下の2つの値を、前記2つのランダム値u0及びu1を用いて算出する手段であって、各maskの算出は、単一の論理右ビットシフト演算子を具備し、入力値“t”について次の計算をするものと、mask =
(magic_mask>>t)
ここで、“t”はu0又はu1のいずれかに等しく結果として得られる値“mask”は、それぞれ“maskA”又は“maskB”のいずれかに等しくなるものとし、ランダム値を算出する手段であって、4組の入力{u0,v0,maskA}, {u0,v1,maskA},
{u1,v0,maskB}, 及び{u1,v1,maskB}を用いる結果としてランダム値R1, R2, R3, 及びR4を得るものであって、加算器及びビット論理XOR (^)演算子を具備し、各入力{s,t,mask}について次の値R=(s+t)^maskを算出するものと、を備え、前記第5手段が、UUB及びVVBを前記乱数発生器から得る手段であって、事前に指定された数値TTBは、前記座標uが前記乱数発生器の入力として用いられた場合はUUBに等しく、また同様に、前記乱数発生器が前記座標vを入力として用いられた場合はVVBに等しいものと、独立して4回使用される加重ランダム値を算出する手段であって、4組の入力{R1, UUB, VVB}, {R2, UUB-1.0, VVB},
{R3, UUB, VVB-1.0}, 及び{R4, UUB-1.0, VVB-1.0}を用いる結果として4つの加重値r1, r2, r3, 及びr4を得るものであり、各モジュールが加算器及びマルチプレクサを具備し、各入力{R,a,b}について次の値r = R*(a+b)を算出するものと、ランダム値RVを、r1, r2, r3, r4, UUB, 及びVVBを入力として用い、また双一次補間モジュールを用いて算出する手段であって、r1,
r2, r3, 及びr4が補間された値であり、UUB及びVVBが補間用パラメータであるものであって、UUB及びVVBを変更して双一次補間動作を制御する手段であって、前記区間[0,1]におけるUUB及びVVBが定義されているときUUB及びVVBをUUB’及びVVB’にマッピングする参照テーブルと、双一次補間動作用のパラメータとしてUUB’及びVVB’を用いて双一次補間を算出する手段と、を具備したものと、を備え、前記システムが、前記ランダム値の生成を制御する手段であって、前記入力座標(u,v)を変更するために、各入力u及びvについて、スケーリング、トランスレーション、及びクランピング演算を行い、加算器、マルチプレクサ、及びクランピング回路で構成されたものと、スケーリング及びトランスレーション係数及びクランピング動作タイプを得る手段と、を具備するものと、前記出力値RVを変更する手段であって、スケーリング演算を行い、マルチプレクサで構成されたものと、スケーリング係数及びクランピング動作タイプを得る手段と、を具備するものと、をさらに備え、前記第5手段が、前記RVと前記入力座標(u,v)とを結合して出力(u’,v’)を得る手段であり、2つの加算器及び2つの“ifステートメント論理回路”を具備し、独立してu’及びv’座標を以下のように求めるものである：
もし(u>0) ならば u’=u+RV さもなくば
u’=u-RV
もし(v>0) ならば v’=v+RV さもなくば
v’=v-RV。
【００３９】
図2に示すように、モジュールrandom1Dの出力は乱数(t0,t1)の区間及び値TTBである。このモジュールは、u又はvを入力として用いて2回インスタンス化される。入力値がuである場合、出力はタプル(u0,u1,UUB)であり、入力値がvである場合、出力タプルは(v0,v1,VVB)である。ランダム区間[u0,u1]及び[v0,v1]がモジュール1200 (random2D)の入力として用いられ、値UUB及びVVBがモジュール1300 (randomCombiner)において用いられる。
【００４０】
モジュール1200：random2D
このモジュールの入力は2つのランダム値の区間[u0,u1]及び[v0,v1]である。一次元区間を生成するために使用する手段により、区間[u0,u1]及び[v0,v1]が無相関であることは明らかである。Random2Dモジュールは4つの新しいランダム値を2つの一次元入力区間[u0,u1]及び[v0,v1]を用いて生成する役割を担っている。
【００４１】
この回路の好適な実施例は、非常に小さな回路の4つのインスタンスを使用することであり、ここでは、各回路が1つのランダム値を異なる一連の入力値から生成する。この回路を、以下、pseudoRandomGenerator2Dと称する。
【００４２】
random2Dモジュールは、まず、この回路用に4セットの入力として、{u0, v0, maskA}, {u0, v1, maskA}, {u1, v0, maskB}, 及び{u1, v1, maskB}と定義されるものを生成する。値maskA及びmaskBもまた、単一の論理右ビットシフト演算を用いて4ビット値として表すことが出来る。これらのマスク値を計算する好適な実施例は、以下のプロシージャを実装した回路であればよい：
【００４３】
maskA= ((magic_mask>>(u0)))&0xF;                  
maskB= ((magic_mask>>(u1)))&0xF;                  
【００４４】
maskA及びmaskBの値を計算した後、回路pseudoRandomGenerator2Dの4つのインスタンスを一連の入力パラメータ{u0,v0,maskA}, {u0,v1,maskA}, {u1,v0,maskB}, 及び{u1,v1,maskB}と平行して使用する。この回路の好適な実施例は、加算器と、ビットシフトとXOR演算子とで構成され、各演算が4ビット値で定義されているため、結果として非常に小さい回路規模になる。
【００４５】
モジュールrandom2Dの好適な例は：定数magic_maskを使用する手段と、2つの新しい4ビット数であって、以下、maskA及びmaskBと称するものを、2つのランダム値u0及びu1を用いて計算し、このとき、各マスク演算は単一の論理右ビットシフト演算(4ビット)で構成され、入力値tについて次の値mask = (magic_mask>>t)&0xFを計算する手段であって：ここで、tはu0又はu1に等しく、結果として得られる4ビット値はそれぞれmaskA又はmaskBに等しくなるようなものと、4回独立して使用される4ビットのランダム値を、4セットの入力{u0,v0,maskA}, {u0,v1,maskA},
{u1,v0,maskB}, 及び{u1,v1,maskB}を用いて計算し、結果として4ビットのランダム値R1, R2, R3, 及びR4を得るものであり、各モジュールが加算器及びビット論理演算子XOR(^)で構成され各入力{s,t,mask}について以下の値R=((s+t)^mask)&0xFを計算する手段であって：ここで、Rは4ビットのランダム値であるものを備えている。
【００４６】
4ビットのランダム値{R1, R2, R3,
R4}はモジュール1400 randomCombinerにおいて使用される。
【００４７】
モジュール1300：randomCombiner
このモジュールの入力は、モジュール1200 random2Dからのランダム値R1, R2, R3, 及びR4並びにモジュール1100 random1Dの2つのインスタンスからのUUB及びVVBである。このモジュールの役割は、最終的なランダム値であって、最初の入力座標(u, v)を摂動するのに使用されるものを生成することである。最終的なランダム値RVの生成は、2つの主要ステップに分解することが出来る。
【００４８】
まず、重み付け関数がR1, R2, R3, 及びR4に適用され、結果として4つの新しいランダム値r1, r2, r3, 及びr4が得られる。重み付け関数の好適な実施例は、4セットの異なる入力で同様な回路を4回使用し、重み付け関数を符号付の距離関数として定義することである。この関数rの選択は重要である。
【００４９】
特許文献WO 01/39126 A1においては、この関数の代わりに、いわゆるグラディエント計算を用いている。グラディエント関数の使用が意味するのは、与えられたハッシュコード（言い換えれば、参照テーブルを用いて連続した置換により得られたある種の乱数）について、或る特定のグラディエントが計算され、結果として加重値が得られることである。ハッシュコードはグラディエントを定義するためのみに使用される、すなわち、どの入力値を加算又は減算するかを示すが、ハッシュコードそのものの値は実際のグラディエントの計算には使用されない。同様に、グラディエントの計算は、引用された特許文献WO 01/39126 A1において提案された回路で4回実行され、結果として4つの加重値が得られる。
【００５０】
randomCombinerの目的は、グラディエント計算と同様であるが、その手段及び得られた値の意味は全く異なる。本発明においては、重み付け関数の好適な実施例は単純化した符号付の距離関数に基づいている。第1の主な違いは、符号付の距離関数を計算する回路を実装するには、ifステートメントやビット比較を、特許文献WO 01/39126 A1で提案された回路のようには、必要としないことである。2つの入力が与えられると、符号付の距離が直接求められた後、符号付の距離値が各ランダム値に重みを付ける重み付けの値として使用される。グラディエント関数の場合においては、ハッシュコードを復号しなければならず、入力値からの選択をしなければならず、選択された値の中には無効にしなければならないものもあり、ハッシュコードによっては選択された値が結合（加算）される。乱数の尺度は入力値の選択を行うときに導入され、ハッシュコードに依存する。ハッシュコードの値は最終的なグラディエントの計算には使用されない。
【００５１】
この最後の文が主な違いの1つを説明している。すなわち、本発明では、ランダム値が重み付けされる値であり、重み付けする値は符号付の距離関数として計算される。符号付の距離関数を実装する好適な実施例は、2つの入力値A及びB、1つの加算器、及び値A+Bを出力する回路(以下、SignedDistanceと称する。)として定義される。4つのランダム値R1, R2, R3, 及びR4に重み付けするため、回路SignedDistanceは、4セットの入力{R1, UUB, VVB}, {R2, UUB-1.0, VVB},
{R3, UUB, VVB-1.0}, 及び{R4, UUB-1.0, VVB-1.0}で4回使用される。三重項{r, a, b}においては、a及びbの特定の選択により単純化された符号付の距離を定義することができ、a+bと表すことが出来る。
【００５２】
重み付け回路の好適な例は、SignedDistance回路に重み付け計算を含めることであり、以下、randomWeighting回路と改称する。この回路は、モジュール1300
randomCombinerにおいて、4セットの入力{R1,
UUB, VVB}, {R2, UUB-1.0, VVB}, {R3, UUB, VVB-1.0}, 及び{R4,
UUB-1.0, VVB-1.0}で4回繰り返される。randomWeighting回路の各インスタンスは、加算器及びマルチプレクサで構成され、新しいランダム値r = R*(a+b)の値を定める。.
【００５３】
なお、Rは4ビット値であり、a及びbは2つの浮動小数値であることに留意する。浮動小数を16ビットを用いて定義すれば、良い結果（すなわち、最終画像中に目に見える不自然さが無いこと）を得るのに十分である。値Rは、何らかの、好ましくは区間[-1, 1]内の、浮動小数値に変換することができる。Rが4ビット値であることから、この変換は簡単（たった16の可能性ある浮動小数値のみ）である。提案されたビット幅は、品質と回路規模の間の良いトレードオフを提供している。
【００５４】
4つのrandomWeighting回路は、4つの加重ランダム値r1, r2, r3, 及びr4を出力する。モジュール1300 randomCombinerの第2の主要なステップは、重み付けされた雑音値r1, r2, r3, 及びr4を双一次補間を用いて補間することである。双一次補間に使用されるパラメータはUUB及びVVBから導き出す。
【００５５】
特許文献WO 01/39126 A1においては、同様な手法が提案されている。パラメータとして2つの値を用いて、グラディエントに対して双一次補間を行っている。明確化のため、以下の比較においては、sを入力パラメータの1つとし、s’をsが変更された値であってグラディエントの補間に使用されるものであるとする。特許文献WO 01/39126 A1においては、参照テーブルを用いてsがs’に対応付けられる。参照テーブルは、二次多項式関数、いわゆるイーズ曲線を含んでいる。このマッピングの目的は、双一次補間の結果の連続性を高めることであると主張されている。さらに、多項式関数の選択肢が固定されているため、テーブルのプロパティ（内容のビット幅及びテーブルエントリのビット幅）は固定されている。
【００５６】
この書面で開示される発明においても、参照テーブルが使用される。しかしながら、参照テーブルの入力は、定義により区間[0, 1]における16ビットの浮動小数値であるから、より精度が高い。本発明における参照テーブルの目的は、必ずしも双一次補間の結果の連続性を高めることではない。その目的は、結果として得られるテクスチャの見栄えを制御する（ユーザのための）手段を提供することが重要であるため、より総合的なものである。この意味で、参照テーブルは、外部データを用いてこのテーブルを初期化できるような回路に定義されている。初期化とは、誰か(ユーザ)があらゆる事前計算された関数を参照テーブルにロードすることが出来るという意味である。この可能性を提供することにより、開示された発明は柔軟性及び設定変更の可能性を大いに向上させ、テクスチャ・パターンのより豊富な種類が得られるようにする。関数の例としては、定数関数、バイアス関数、利得関数、三角関数及び多項式関数が挙げられるが、これに限定されるものではない。
【００５７】
前述の参照テーブルは入力パラメータUUB及びVVBをUUB’及びVVB’に変換する。これらの値は、次に双一次補間を行うために使用される。UUB’は(r1,r2)及び(r3,r4)を直線的に補間し、結果として2つの値を得て、これらの2つの値がVVB’を用いて補間される。最終結果はランダム値RVである。
【００５８】
最後のステップは、初期座標(u,v)をランダム値RVで摂動することである。このステップは摂動座標モジュール(1500)によって行われる。本発明の好適な実施例の一つは、単にu及びvに対して、それぞれu及びvの符号に従ってRVを加算するか減算するものである。このような例を定義する回路は、2つのifステートメント論理回路と、2つの否定演算子、及び2つの加算器で構成され、以下の計算を行う：
もし(u>0) ならば u’=u+RV さもなくば
u’=u-RV
もし(v>0) ならば v’=v+RV さもなくば
v’=v-RV
【００５９】
摂動された座標(u’,v’)は、次にモジュール3000で使用される。
ランダム値の生成を制御するのに好適な例は、一連のスケーリング、トランスレーション、及びクランピング演算を使用するものである。これは、2つの異なる制御、事前制御と事後制御に分解することが出来る。第1の制御は、ランダム値を計算する前に入力座標(u, v)に適用されるが、事後制御は出力値RVに対して適用される。 
【００６０】
事前制御のためのスケーリング及びトランスレーション演算は、好適な例において加算器及びマルチプレクサとして実装され、各入力座標u及びvについて、tと総称される値を(t+translation)*scaleとして計算する。ここで、translation及びscaleがどこか別の場所で（一般的にはユーザによって）定義された何らかの値である。一般的に、結果として得られる値はその後従来のクランピング演算を用いてクランプされ、出力値が区間[0, 1]内になるようになる。クランピング演算は、コンピュータ・グラフィックスにおいて周知のクランピング演算であり、開示された発明において新規発明には含まれていない。クランピング演算の例はいくつかあるが、エッジ演算、リピート関数、及びミラー関数が含まれる。
【００６１】
事後制御動作は事前制御動作と同様であるが、出力値RVに適用される点が異なる。好適な実施例の一つは、事後演算を、値RV*scaleを計算するマルチプレクサとして実装し、ここで、scaleはどこか別の場所で定義される（一般的にはユーザ定義）別の値とする。同様なクランピング演算が、結果として得られる値にも行われ、結果が確実に区間[0,1]内に収まるようにする。
【００６２】
第2の態様：一次元テクスチャ画像及び設定可能な二次元から一次元へのマッピング関数を用いた二次元テクスチャ画像生成
この書面に開示された発明の第2の態様は、図1に示したモジュール3000に相当する。このモジュールはCoordinates Mapping、略してCMap、と呼ばれる。名前が示しているように、このモジュールの役割は二次元入力座標(u,
v)(雑音モジュールの出力(u’,v’)からの可能性あり)を一次元テクスチャ座標(t)にマッピングすることである。
【００６３】
発明の第2の態様は基本的に、
テクスチャ座標(u,v)を得る第1手段と、
前記テクスチャ座標(u,v)を一次元テクスチャ座標(t)に投影する第2手段と、メモリに格納された一次元テクスチャ画像を、前記一次元テクスチャ座標(t)を用いてアクセスして獲得する第3手段と、前記一次元テクスチャ画像を用いて二次元テクスチャ画像を生成する第4手段と、を備えたことを特徴とする、二次元テクスチャ画像を生成するシステムを対象としている。
【００６４】
第1手段は、u及びvを得る。第2手段は、テクスチャ座標(u,v)を一次元テクスチャ座標(t)に投影する。第3手段は、一次元テクスチャ座標(t)を用いて一次元テクスチャ画像にアクセスしてこれを獲得する。第4手段は、一次元テクスチャ画像を用いて二次元テクスチャ画像を生成する。
【００６５】
第2の態様の好適な一例は、上記のシステムにおいて、前記第2手段が、2つの関数G1及びG2を複数の固定関数から選択する手段と、あらゆる実関数、以下Fと称する、を表す参照テーブルを定義する手段と、前記関数G1、G2、及びFを結合する手段と、を備えたものを対象としている。
【００６６】
第2の態様の好適な例は、上記のシステムにおいて、前記第2手段が、2つの関数G1及びG2を、{u, v, u+v, u-v, u^2, v^2, sqrt(u2+v2),
u+v+sqrt(u2+v2), u+v-sqrt(u2+v2), min(u,v), max(u,v), constant}に等しい関数G(u,v)から選択する手段であって、“sqrt”は数学関数である平方根であり、x^2はxの二乗(xのx倍)であるものと、あらゆる実関数で以下Fと称するものを表す参照テーブルを定義する手段と、前記関数G1、G2、及びFを結合する手段であって、G1を参照テーブルFのの入力として用い、これによりF(G1(u,v))を算出する手段と、参照テーブルの出力とG2を用いて、参照テーブルの出力とG2との積を算出して、結果として値値F(G1 (u,v))*G2(u.v)を得る手段と、を具備するものと、を備え、前記第3手段が、一次元テクスチャ画像F(G1 (u,v))*G2(u.v)を用いるものを対象としている。
【００６７】
上記手段の好適な例は、合計4つの加算器と、3つのマルチプレクサと、平方根演算子とを使用した非常に小さな回路である。この回路の主な利点は、以下、Mapと称し、二次元点(u,v)を一次元点tに対応付けるマッピング関数を定義することである。このマッピングは、3つの関数の合成であり、一般的に次のように表現することが出来る：        
F(G1(u,v))*G2(u,v),                                        (4)
ここで、G1及びG2は一連の固定関数の中から選択され、Fは参照テーブルである。好適な実施例における代表的な一連の固定関数には以下の関数が含まれる。
【００６８】
(5)
| G(u,v) = u                                      (5a)
| G(u,v) = v                                      (5b)
| G(u,v) = u^2                                    (5c)
| G(u,v) = v^2                                    (5d)
| G(u,v) = u^2+v^2                                (5e)
| G(u,v) = sqrt(u^2+v^2)                          (5f)
| G(u,v) = u+v+sqrt(u^2+v^2)                      (5g)
| G(u,v) = u+v-sqrt(u^2+v^2)                      (5h)
| G(u,v) = min(u,v)                               (5i)
| G(u,v) = max(u,v)                               (5j)
| G(u,v)  = constant                              (5k)
【００６９】
この固定関数のセットを実装する回路は、5つの加算器、2つのマルチプレクサ、及び平方根演算子を含んでいる。主な利点は、参照テーブルへの入力の選択肢の多様性、及び結果の多様性である。もちろん、この多様性は完全にプログラマブルな回路（すなわち、フラグメントシェーダ）よりもかなり低いが、いくつかのケースでは十分である。それは、コンピュータ・グラフィックスにおいてコンテクストのテクスチャリングに頻繁に使用される数学関数のいくつかを表現することができるからである。
【００７０】
例えば、式(5e)及び(5f)は距離関数を表現しているが、従って、適切な参照テーブルを用いれば、全ての可能性の或る、ガウス関数及びその他全ての距離を基にした関数を実現することができる。可能性のある一連の関数で距離関数に基づくものは、次の参考資料（C. Blanc 尾及び C. Schlick. 「ソフトオブジェクト用拡張フィールド関数」 Implicit Surfaces'95, Eurographics/ACM SIGGRAPH Workshop, 頁21-32, 1995年）を参照できる。
【００７１】
式(5h)-(5i)及び(5g)-(5j)は周知の関数min/maxを、様々な連続性のレベルで定義している。集合理論的関数のより詳細な説明には、次の参考資料を用いることが出来る。（A. Pasko, V. Adzhiev, A. Sourin, 及び V.
Savchenko. 「幾何学モデリングにおける関数表記：概念、実装及び応用」The Visual
Computer, 11(8):429-446, 1995年）なお、集合理論的演算のみを使用したいと望む場合には、恒等関数を参照テーブルにロードし、G2は定数1に設定すればよい。別の一般的な関数は、いわゆる正規関数であり、u/sqrt(u^2+v^2)と表現される。この関数は、開示された実施例を用い、sqrt(u^2+v^2)に等しいG1、uに等しいG2、及び事前に抽出された関数1/xが設定された参照テーブルに相当する参照テーブルを選択すれば、求めることが出来る。
【００７２】
モジュール3000 CMapを実装する回路の好適な実施例は、式(5a)から(5k)で表現された関数の集合である。これは、回路規模と柔軟性の間の良いトレードオフとなる。回路規模が重大な問題でない場合には、他の固定関数を追加することにより柔軟性を向上させることが出来るのは明らかである。また、ハードウェア規模が大きな問題でないならば、いくつかの他の構成により投影関数を拡張することが出来ることも明らかである。例えば、提案された実施例は、F2(F(G1(u,v))*G2(u,v))*G3(u,v)に拡張することができ、ここでF2及びG3の可能性としては、新しい2つの回路であって固定関数の新規の集合或いは新規テーブルを定義するものである。
【００７３】
開示された発明の最終ステップは、式(4)で定義された値(t)を用いて、一次元テクスチャ画像におけるインデックスを計算し、結果としてRGBA色を得ることである。インデックス計算の好適な実施例には、コンピュータ・グラフィックス及びテクスチャ関連技術における通常の技術が含まれる。インデックス計算は開示された発明の請求の範囲の一部ではない。
【００７４】
この書面に開示された本発明の端的な拡張は、単一の値tの代わりに2つの出力値t_rgb及びt_aを生成することである。これにより、RGB色及びA(アルファ)値をそれぞれ別々にインデックス付けすることができ、自由度を向上させることが出来る。この拡張の好適な例は、二次元クランプドテクスチャ座標(u,v)を一次元テクスチャ座標(t)に投影する手段であって、4つの関数G1_rgb, G2_rgb, G1_a, 及びG2_aを、いくつかの固定関数の中から選択する手段であって、固定関数としては、{u,v,u+v,u-v,u^2,v^2,sqrt(u2+v2),
u+v+sqrt(u2+v2), u+v-sqrt(u2+v2), min(u,v), max(u,v)}に等しいG(u,v)であって、sqrtは数学的関数である平方根、及びx^2はxの二乗(xのx倍)を含むものであるが、これに限定されず、5つの加算器と、2つのマルチプレクサと1つの平方根演算子を備えたものと、2つの参照テーブルであって、以下、F_rgb及びF_aに対応するあらゆる実数を提示するものと、
一方で関数G1_rgb, G2_rgb, 及びF_rgbを結合し、他方でG1_a, G2_a, 及びF_aを結合する手段であって、参照テーブルF_rgbの入力としてG1_rgbを求め、これによりF_rgb (G1_rgb (u,v))を計算する手段と、G2_rgbを求め、参照テーブルの出力とG2_rgbとの積を計算し、結果として値F_rgb(G1_rgb (u,v))* G2_rgb
(u,v)を1つのマルチプレクサを用いて求める手段と、参照テーブルF_aの入力としてG1_aを求め、これによりF_a(G1_a(u,v))を計算する手段と、G2_aを求め、参照テーブルの出力とG2_aとの積を計算し、結果として値F_a(G1_rgb (u,v))* G2_a
(u,v)を1つのマルチプレクサを用いて求める手段と、を備えたものと、で構成される。
【００７５】
この好適な例を使用すれば、ほんの僅かなハードウェアの変更、すなわち、追加の参照テーブル1つ、追加のマルチプレクサ1つ、及び入力関数G1_rgb, G2_rgb, G1_a, 及びG2_aを選択する手段の拡張.によって、RGB及びAに別々の処理を施すことができる
【実施例１】
【００７６】
図3に示す例は、本明細書において開示された発明により結果として得られる画像の一例である。マッピング関数の様々な選択の様子が示されている。入力の幾何学図形は四辺形であり、左下角のテクスチャ座標(u0, v0)が(-1,-1)に等しく、右上角のテクスチャ座標(u1, v1)が(1, 1)に等しく、u座標は画像の中の横軸に沿っている。一次元テクスチャ画像は2色の配列である。第1の色は白であり、第2の色は黒である。この初期設定を用いて3つの画像が生成される。マッピング関数が変わるだけである。マッピング関数の一般形は以下の通りである：            Map(u,v)=F(G1(u,v))*G2(u,v)
【００７７】
第1の画像では、固定関数G1をG1(u,v) = uと定義し、第2の固定関数G2をG2(u,v)=1と定義し、関数F(参照テーブル)をF(x) = x (恒等関数)と定義している。従って、最終的な関数は、Map(u,v)=uである。テクスチャ画像が黒と白の2色しか含まないことを思い出せば、予測可能な結果は灰色のグラディエントである。uが0に等しければ、結果として得られる色は白であり、uが1に等しければ、結果は黒であり、その中間では、中間色は灰色である。
【００７８】
第2の画像では、固定関数G1をG1(u,v)=u^2+v^2と定義し、第2の固定関数G2をG2(u,v)=u^2と定義し、関数F(参照テーブル)をF(x)=1/x (逆関数)と定義している。結果は、関数u^2/(u^2/v^2)に対応した灰色のグラディエントである。
【００７９】
最後の画像では、固定関数G1をG1(u,v)=sqrt(u^2+v^2)と定義し、第2の固定関数G2をG2(u,v)=1と定義し、関数F(参照テーブル)をポテンシャル関数と定義している。関数G1が四辺形の中心までの距離であることに注目すれば、距離がゼロに等しいとき、ポテンシャルは1に等しくなり、中心までの距離が増加するにつれてゼロまで低下することから、結果として放射状の灰色のグラディエントが得られる。
【実施例２】
【００８０】
図4に示す例は、開示された発明により結果として得られる画像の一例である。1つのマッピング関数が選択され、様々なランダム摂動が与えられている。入力の幾何学図形は四辺形であり、左下角のテクスチャ座標(u0, v0)が(-1,-1)に等しく、右上角のテクスチャ座標(u1, v1)が(1, 1)に等しく、u座標は画像の中の横軸に沿っている。一次元テクスチャ画像は2色の配列である。第1の色は白であり、第2の色は黒である。3つの画像を生成するため、同じマッピング関数が使用され、それは次の通りである：Map(u,v)=u
第1の画像では、摂動が与えられていない。結果が図3における第1の画像と同様であることが分かる。第2及び第3の画像では、摂動が与えられているが、異なる倍率が事前制御及び事後制御演算に設定されている。
【産業上の利用可能性】
【００８１】
本発明の回路は、三次元コンピュータ・グラフィック・チップに適用できる。
【図面の簡単な説明】
【００８２】
【図１】図１は、開示された発明を2つのモジュールに分解した様子を示している。二次元入力テクスチャ座標(u,v)が与えられると、モジュール1000 (Perturbater)が(u,v)を変換し、結果として(u’,v’)を得て、これらが次にモジュール3000 CMapの入力として使用され、二次元座標から一次元座標tにマッピングされる。その後、この一次元座標がモジュール5000の一次元テクスチャ参照テーブルのインデックスとして使用される。
【図２】図２は、モジュール1000 Perturbaterをサブモジュールに分解した様子を示している。2つの同一モジュールrandom1D、1つのrandom2Dモジュール、1つのrandomCombiner、及び最後に1つのperturbCoordinatesモジュールに分解される。
【図３】図３は、開示された発明の結果として得られる画像の一例を示している。マッピング関数の様々な選択肢を説明している。
【図４】図４は、開示された発明の結果として得られる画像の一例を示している。1つのマッピング関数が選択され、様々な摂動が与えられている。
【図１】
2008033848.tif 000003
【図２】
2008033848.tif 000004
【図３】
2008033848.tif 000005
【図４】
2008033848.tif 000006
【外国語明細書】
Title of the Invention
A COMPUTER GRAPHICS CIRCUIT AND A 3-DIMENSIONAL
COMPUTER GRAPHICS APPARATUS USING THE CIRCUIT FOR GENERATING 2D PSEUDO RANDOM
TEXTURE PATTERN USING 1D TEXTURE IMAGE APPLIED ON 3D OBJECTS DISPAYED ON A 2D
DISPLAY SYSTEM
Field of the Invention
The present invention relates to the generation of
pseudo random texture pattern. A 1D texture image is used as framework to
generate a 2D image texture. More precisely, the 2D image texture is created
using by a special projection that projects the 1D texture onto a 2D texture
image
Description of the Related Art
In computer graphics, geometrical objects are
displayed on 2D display system. To improve the realism of the resulting image,
geometrical are often combined with a texture. A texture can be seen as an
image, or a pattern, that is painted on the surface of this object. For
instance, to visualize a mountain on a 2D display system, one can use a
quadrangle for the geometry, and can use an image of a mountain as a texture.
The mountain image is attached to the geometry using texture coordinates. For
each point of the geometry, a texture coordinate is defined. This texture
coordinate defines also a location in the image. The correspondence between the
geometry space and the image space is called texture mapping. In a traditional
computer graphic system, the geometrical object is rendered, and for each point
of object which corresponds to a point on a 2D display system, the
corresponding texture coordinate is used to determine a point in the texture
image, resulting in a color. Then, this color is displayed. This explanation is
very simplified. The texturing and texture mapping is a common technique in
computer graphics. See for instance the non-patent document [Non-patent
Document 1]. This technique will be referred hereafter as static 2D texture.
Mapping 2D texture image on an object is
intensively used in computer graphics and very powerful. Nevertheless, for some
objects, this technique may not be the most appropriated one. For instance,
considering a wall, it exhibits the same pattern everywhere, with slight
modifications, i.e. a wall made of bricks and mortar seems to exhibit the same
brick/mortar everywhere, but when looking closer, differences appear (mortar
more or less thick for instance). To generate such repetitive but different
pattern, an alternative to (or an extension of) 2D texture exist. It is called
Procedural texture. Instead of using a static 2D image, a function (procedure)
is used to generate some pseudo random patterns. Description of the procedural
texture technique can be found in the non-patent document 2 “D. Ebert et al. texturing and modeling: a
procedural approach”. This technique will be referred
hereafter as procedural texture. Note that the procedural texture can be used
in combination with the static 2D texture. The procedural function perturbs the
input texture coordinate, and the perturbed input coordinates are then used to
define the output color using a 2D texture image.
In both techniques, static and procedural, for
every given input texture coordinate (u, v) several calculation are performed
in order to define an output color. For static 2D texture, it consists mainly
in a mapping function that maps the texture coordinate to a point in the image
space and therefore defining a color, and for procedural function, a special
function is defined that maps for instance the input coordinates (u,v) to (u’,v’), and then, (u’,v’) is used in the texture mapping function. 
In this document, we propose a novel technique for
texturing that is in between the static 2D texture and the procedural texture,
while proposing a new texture mapping technique. This novel technique can be
summarized as follows. Given an input texture coordinate (u,v), a perturbation
is first applied to (u,v) using a noise function, resulting in (u’,v’), and then a special mapping unit maps
the 2D texture coordinates (u’,v’) to a 1D texture coordinate (t). This 1D texture coordinate is then
used to address a 1D texture image. 
Using this new technique, interesting textures can
be obtained. It can be separated in two different kind. 
When perturbation is not applied, regular
geometrical textures can be obtained. Examples of such texture are for instance
glare, flare, halo, or repetitive motifs on a tissue (square, round etc…). No patent document related to specific 2D to 1D mapping functions
could be found.
When the perturbation is used, natural looking
texture such as wood or marble can be obtained. The visual results, obtained
using the perturbation module, are close to the results proposed in the
non-patent document 2 “D. Ebert et al. Texturing and modeling: a procedural approach”. The technique proposed in this document using is based on a
perturbation module. The behavior of this module is somehow similar to the
noise function proposed in the patent document “K.
Perlin, Method and appartus for noise”, W0 01/39126 A1
(patent document 1). Although the input and the output are similar, the means
to obtain the output value are different. The noise function relies on three
steps; e.g. computing some hash values, computing several gradient values and
interpolating these values into a single value. One embodiment of the present
invention relies on several modifications of these steps. The hash value
calculations rely on permutation table, and hash values are used to calculate
gradient values. One prefer embodiment of the present invention do not use
table nor gradient. It relies on very simple random number generation and
weighting functions of these random numbers. Another embodiment of the present
invention refers to the interpolation method, where a specific circuit is
proposed to increase the parameterization of the perturbation, and thus the
visual appearance of the resulting texture. All the embodiments combined
together define a module that it different from the noise module proposed in
the patent document W0 01/39126 A1 (Patent document 1).
Another similar module is defined in the patent
document “K. Perlin, Standard for Perlin noise”, USP No. 6,867,776 B2 (patent document 2). In a similar way as in
the W0 01/39126 A1 (patent document 1), hash values and gradient values. One
preferred embodiment of the invention does not use hash and gradient values,
but is based on weighting random values. The method described in patent
document 2 does not use bilinear interpolation but replace it with a function
called spherical Kernel.
References:
Patent Document 1: Perlin Kenneth, “Method and apparatus for noise”,
International Publication Number WO 01/39126 A1   
Patent Document 2: Perlin Kenneth, “Standard for Perlin noise”, USP No.
6,867,776 B2
Non-Patent Document 1 : J.D. Foly,
A. Van Dam, S.K. Feiner, and J.F. Hugues. Computer Graphics: Principles and
Practices. Second Edition, ADDISON-WESLY, ISBN: 0-201-84840-6,1995.
Non-Patent Document 2: D. Ebert et al. Texturing and modeling: a procedural approach, third edition,
Morgan Kaufmann Publishers, ISBN 1-55860-848-6, 2003
Disclosure of the Invention
The Problems to be solved by the
Invention
It is usual that in computer graphics, to create
and display a 2D texture images, a module, called Texture Unit is used. It uses
a 2D coordinate (u,v), so-called texture coordinates, to calculate an index to
access a specific location of a 2D image stored  in memory. The index
calculation requires a large amount of calculation and to store the 2D image is
expensive in terms of memory. This technique is static, i.e. very few
configuration parameters exist to obtain different resulting images depending
on the 2D image store in memory.
For so-called natural texture, such as wood, stone
etc, there exists another approach called procedural texture. But to create
procedural texture, programmable circuit (called fragment shader) is often
needed. Such general purpose programmable hardware circuit represents usually
an important part of a graphic chip and is very large in terms of hardware
size.
The interest
of the disclosed invention is in generating natural texture, or pseudo random
repetitive textures, and also textures that presents geometrical regularity
(such as glare, flare, halo, or regular motifs printed on a tissue for
instance). Both static 2D image texture and procedural texture can create such
textures. The proposed invention proposes to fill a gap for generating 2D
texture image. It is a trade-off between completely static 2D Texture and
procedural texture. The set of circuits disclosed in this document offers
several configuration parameters that permit a greater flexibility than static
2D texture (but less flexible than procedural texture defined in a fragment
shader), with a circuit size much smaller than fragment shader (and also static
2D texture).
The Means for solving the above Problems
The systems used to solve the problems of memory
size and circuit size requirement can be decomposed as follows. To solve the
problems enumerated in the previous section, three means, combined together are
used:
A 1D texture is used instead of a 2D texture to
reduce the memory size requirement.
A specific circuit for perturbing the input 2D
texture coordinate is used to introduce deformations that will be visible in
the resulting 2D texture image.
A specific but configurable mapping circuits that
maps the perturbed 2D input texture coordinate to a 1D output texture coordinate,
that will be used for addressing the 1D texture image stored in memory.
Aspect 1: Procedural 1D pseudo random pattern
generation
First aspect of the present invention directs to a
system for computing a 2D texture coordinate in a computer system comprising:
a means for obtaining a 2D texture coordinate
(u,v);
a means for generating two 1D intervals of two
random values using the coordinate u and v; 
a means for combining the two 1D intervals of
random values to a 2D interval of four random values;
a means for generating a random value depending on
the texture coordinate (u,v) and the 2D interval of four values; and 
a means for combining the random value with the
input texture coordinates (u,v) resulting in (u’,v’), perturbed the 2D texture coordinate.
A prefeered embodiment of the first aspect of the
present invention is a system in accordance with the above, wherein:
the means for generating two 1D intervals of two
random values using the coordinate u and v comprising,
two separate but identical random number
generators with either u or v coordinate as input resulting in the 1D intervals
of two random values (u0,u1) and (v0,v1); and
the means for combining the two 1D intervals of
random values to a 2D interval of four random values combines the two 1D intervals
of random values (u0,u1) and the (v0,v1) to a 2D interval [(u0,v0),(u1,v1)].
A prefeered embodiment of the first aspect of the
present invention is a system in accordance with any one of the above, wherein:
the means for generating two 1D intervals of two
random values using the coordinate u and v comprising two separate but
identical random number generators with either u or v coordinate as input
(hereinafter also referred as “t”) resulting in the 1D intervals of two random values (u0,u1) and (v0,v1),
wherein each of the random number generators comprising:
a means for computing two numbers TA and TB from
the input value “t”, where TB
is a float value lower than one and TA+TB is equal to one; 
a means for projecting the value TB to a random
value TT;
a means for computing two numbers TTA and TTB from
the value TT, where TTB is a float value lower than one and TTA+TTB is equal to
one; and 
a means for generating a random value using the
set of parameters {TA,TTA} and {TA,TTA+1} resulting in two random values T1 and
T2;
the means for combining the two 1D intervals of
random values to a 2D interval of four random values is a means for combining
the two 1D intervals of random values (u0,u1) and (v0,v1) to a 2D interval
[(u0,v0),(u1,v1)] and comprising:
a means for using a constant integer value called
hereafter “magic_mask”;
a means for calculating two new number called
hereafter “maskA” and “maskB” using the two random values u0 and
u1; and
a means for calculating random values using four
sets of inputs {u0,v0,maskA}, {u0,v1,maskA}, {u1,v0,maskB} and {u1,v1,maskB}
resulting in the random values R1, R2, R3, and R4;
the means for combining the random value to the
input texture coordinates (u,v) resulting in (u’,v’) comprising:
a means for obtaining UUB and VVB from the random
number generator, where previously named value TTB is equal to UUB when the
coordinate u is used as input of the random number generator, and
correspondingly VVB when the random number generator is used using v coordinate
as input;
a means for calculating a weighted random value
using the four set of inputs {R1, UUB, VVB}, {R2, UUB-1.0, VVB}, {R3, UUB,
VVB-1.0} and {R4, UUB-1.0, VVB-1.0} resulting in four weighted values r1, r2,
r3 and r4; and
a means for calculating a random value RV using
the r1, r2, r3, r4, UUB and VVB as inputs, comprising bilinear interpolation
module, wherein r1, r2, r3 and r4 are the interpolated values and UUB and VVB
are as parameters for the interpolation;
the system further comprising a means for
controlling the generation of the random value comprising:
a means for modifying the input coordinates (u,v);
and 
a means for modifying the out value RV;
the means for combining the random value with the
input texture coordinates (u,v) resulting in (u’,v’) is a means for combining the RV with the input coordinates (u,v)
to produce the output (u’,v’).
A prefeered embodiment of the first aspect of the
present invention is a system in accordance with any one of the above:
the system further comprising a means for controlling
the generation of the random value comprising:
a means for modifying the input coordinates (u,v)
comprising for each input u and v:
a scaling, a translation and a clamping operation
and 
a means for obtain the scaling and translation
factors and the clamping operation type,
a means for modifying the out value RV comprising:
a scaling and a clamping operation and
a means for obtaining the scaling factor and the
clamping operation,
the means for generating two 1D intervals of two
random values using the coordinate u and v comprising two separate but
identical random number generator with either u and v coordinate as input
(refers after as t) resulting in the 1D intervals of two random values (u0,u1)
and (v0,v1), wherein the random number generator comprising:
a means for computing two numbers TA and TB from
the input value t, where TB is a float value lower than one and TA+TB is equal
to  one, 
a means for projecting the value TB to a random
value TT comprising:
a means for obtaining a constant value called
hereafter magic_shift1, and
a means for projecting TB in the interval
[0,magic_shift1] resulting in TT,
a means for defining two numbers TTA and TTB using
the value TT, wherein TTB is a float value lower than one and TTA+TTB is equal
to one,
a means for generating a random value using the
set of parameters {TA, TTA} and {TA, TTA+1}, resulting in two random values T1
and T2 ,respectively, comprising:
a means for defining and use constant values
called hereafter magic_mask,magic_shift1 and magic_shift2,
a means for calculating a pseudo random value
using D value (corresponding either to TA or TA+1), called hereafter maskT, and
a means for calculating a random number R using
either TA or TA+1, and using the value TTA and the previously computed value
maskT,
the means for combining the two 1D intervals of
random values to a 2D interval of four random values is a means for combining
the two 1D intervals of random values (u0,u1) and (v0,v1) to a 2D interval
[(u0,v0), (u1,v1)] and comprising:
a means for obtaing the constant number
magic_mask,
a means for calculating two new number called
hereafter maskA and maskB using the two random values u0 and u1, and
a means for calculate a random value used four
times independently using the four sets of inputs {u0, v0, maskA}, {u0, v1,
maskA}, {u1, v0, maskB} and {u1, v1, maskB} resulting in the random values R1,
R2, R3, and R4, 
the a means for combining the random value with
the input texture coordinates (u,v) resulting in (u’,v’) comprising:
a means for obtaining UUB and VVB from the random
number generator, where previously named value TTB is equal to UUB when the
coordinate u is used as input of the random number generator, and
correspondingly VVB when the random number generator is used using v coordinate
as input,
a means for calculating a weighted random value
used four times using the four set of inputs {R1,UUB,VVB}, {R2,UUB-1.0,VVB},
{R3,UUB,VVB-1.0} and {R4,UUB-1.0,VVB-1.0} resulting in four weighted values r1,
r2, r3 and r4,
a means for calculating a random value RV using
r1, r2, r3, r4 and UUB and VVB as inputs and bilinear interpolation module,
where r1, r2, r3 and r4 are the interpolated values and UUB and VVB are as
parameters for the interpolation comprising:
a means for modifying UUB and VVB to control the bilinear
interpolation behavior,
a means for combining the random value RV with the
input coordinates (u,v) to produce the output (u’,v’).
A prefeered embodiment of the first aspect of the
present invention is a system in accordance with any one of the above,the means
for generating two 1D intervals of two random values using the coordinate u and
v is a means for generating two 1D intervals of two random values using two
separate but identical random number generators with either u or v coordinate
as input (hereinafter called as “t”) resulting in the 1D intervals of two random values (u0,u1) and
(v0,v1), where each of the number generators comprising:
a means for computing two numbers TA and TB using
the input value t, where TB is a float value lower than one and TA+TB is equal
to one; 
a means for projecting the value TB to a random
value TT comprising:
a means for obtaining a constant value called
hereafter “magic_shift1”; and
a means for projecting the TB in the interval
[0,magic_shift1] resulting in TT comprising a single multiplexer and
calculating TT = TB*magic_shift1;
a means for computing two numbers, TTA and TTB,
using the value TT, where TTB is a float value lower than one and TTA+TTB is
equal to one,
a means for generating a random value using the set
of parameters {TA,TTA} and {TA,TTA+1}, resulting in two random values T1 and T2
comprising:
a means for obtaining constant values the “magic_shift1”, “magic_mask”, and “magic_shift2”,
a means for calculating a following value, a
pseudo random value, using either TTA or TTA+1 as input, called hereafter “maskT”, comprising a “if statement logic circuit”, a multiplexer
and a logic right bit shift operation (>>):
maskT = magic_mask>>(TA*magic_shift2)
if the input value, noted D and either equal to
TTA or TTA+1, is strictly lower than magic_shift1, and calculating the value;
and otherwise calculating the following value:
maskT=magic_mask>>((TA+1)*magic_shift2);
a means for calculateing a random number R using
the input value, noted D and either equal to TTA or TTA+1, and maskT as input
comprising a “if statement logic circuit”, a multiplier and the bit-logic operator “XOR” (noted ^) and calculating the value 
R = ((1+TTA)*magic_shift2)^maskT, 
if D is lower than magic_shift1, and the value,
and  
R = ((1)*magic_shift2)^maskT, otherwise,
the means for combining the two 1D intervals of
random values to a 2D interval of four random values is a means for combining
the two 1D intervals of random values (u0,u1) and (v0,v1) to a 2D interval
[(u0,v0),(u1,v1)] and comprising:
a means for obtaining the “magic_mask”;
a means for calculating two following values
called hereafter maskA and maskB using the two random values u0 and u1, where
each mask calculation comprises a single logic right bit shift operation and
calculating for an input value “t”: 
mask = (magic_mask>>t)
wherein
“t” is either equal to u0 or u1
and the resulting value “mask”
is equal either to maskA or maskB, respectively;
a means for calculating a random value using the
four sets of inputs {u0,v0,maskA}, {u0,v1,maskA}, {u1,v0,maskB} and
{u1,v1,maskB} resulting in the random values R1, R2, R3, and R4, comprising an
adder and a bit logic XOR (^) operation and calculating the value for each
input {s,t,mask}:
R=(s+t)^mask
the means for combining the random value to the
input texture coordinates (u,v) and the 2D interval of four values comprising:
a means for obtaining UUB and VVB from the random
number generator, where previously named value TTB is equal to UUB when the
coordinate u is used as input of the random number generator, and
correspondingly VVB when the random number generator is used using v coordinate
as input,
a means for calculating a weighted random value
used four times using the four set of inputs {R1,UUB,VVB}, {R2,UUB-1.0,VVB},
{R3,UUB,VVB-1.0} and {R4,UUB-1.0,VVB-1.0} resulting in four weighted values
r1,r2,r3 and r4, where each module comprises an adder and a multiplexed and
calculating the value for each input {R,a,b}:
r = R*(a+b)
a means for calculating a random value RV using
r1,r2,r3,r4 and UUB and VVB as inputs and bilinear interpolation module, where
r1,r2,r3 and r4 are the interpolated values and UUB and VVB are as parameters
for the interpolation comprising:
a means for modifying UUB and VVB to control the
bilinear interpolation behavior comprising a look-up table that maps UUB and
VVB to UUB’ and VVB’, with UUB
and VVB in the interval [0,1] by definition; and 
a means for computing bilinear interpolation using
the values UUB’ and VVB’ as
parameters for the bilinear interpolation;
a means for controlling a generation of the random
value comprising:
a means for modifying  the input coordinates
(u,v) comprising for each input u and v:
a scaling, a translation and a clamping operation
comprising an adder, a multiplexer and a clamping circuit,
a means for obtain the scaling and translation
factors and the clamping operation type,
a means for modifying the out value RV comprising:
a scaling operation comprising a multiplexer, and 
a means for obtain the scaling factor and the
clamping operation type,
the means for combining the random value with the
input texture coordinates (u,v) resulting in (u’,v’) is a means for combining RV with the input coordinates (u,v) to
produce the output (u’,v’)
comprising two adders and two if statement logic circuit and calculating
independently the u’ and v’
coordinates as:
if(u>0) then u’=u+RV
otherwise u’=u-RV
if(v>0) then v’=v+RV
otherwise v’=v-RV
Aspect 2: 2D texture image generation using 1D
texture image and a configurable 2D to 1D mapping function
A second aspect of the present invention directs
to a system for generating a 2D texture image comprising:
a means for obtaining a texture coordinate (u,v);
a means for projecting the texture coordinate
(u,v) to a 1D texture coordinate (t);
a means for accessing and obtaining a 1D texture
image stored in memory using the 1D texture coordinate (t); and 
a means for generating a 2D texture image using
the 1D texture image.
A preferred embodiment of the second aspect of the
present invention directsto a system in accordance with the above wherein
the means for projecting the texture coordinate
(u,v) to a 1D texture coordinate (t) comprising:
a means for selecting two functions G1, and G2
among several fixed functions;
a means for defining a look up table representing
any real function,  hereafter called as F; and 
a means for combining the functions the G1, the
G2, and the F.
A preferred embodiment of the second aspect of the
present invention directsto a system in accordance with the above wherein the
means for projecting the texture coordinate (u,v) to a 1D texture coordinate
(t) comprising:
a means for selecting two functions G1, and G2,
from the function G(u,v) equal to {u, v, u+v, u-v, u^2, v^2, sqrt(u2+v2),
u+v+sqrt(u2+v2), u+v-sqrt(u2+v2), min(u,v), max(u,v), constant}, where “sqrt” is the mathematical function square
root, and x^2 means x power 2 (x times x);
a means for defining a look up table representing
any real function, hereafter called as F;
a means for combining the functions the G1, the G2
and the F comprising:
a means for using the G1 as input of the look up
table F, thus calculating F (G1 (u,v)); and
a means for using the G2 to calculate the product
of the output of the look up table with the G2, resulting in the value F (G1
(u,v))* G2 (u,v);
the means for accessing a 1D texture image stored
in memory using the 1D texture coordinate F(G1(u,v)*G2(u,v).
The
effects of the present invention
The present invention can provide a new graphic circuit
based on a new set of simple functions that can be implemented easily as a
circuit in a graphic chip.  
The
present invention can provide a new graphic circuit that can save memory cost,
without buffer accesses and fewer operations than traditional texture related
techniques.
The present
invention can provide a system for rendering 2D texture images from a 1D input
texture image, and with different of configuration, the 2D texture image can
exhibits interesting visual properties such as pseudo randomness, repetitively
etc…,
properties that can be found in so-called natural textures (wood, marble etc),
but also textures with geometry aspects (glare, halo, printed motifs on tissue
etc.) 
The Best Mode of the Invention
A traditional texture unit (well known unit in
Computer Graphics) has usually the following role. Given an input texture
coordinate (u,v), different calculation are performed in order to generate an
output color RGBA (Red, Green, Blue and Alpha). In the RGBA, the Alpha
generally indicates transparency. The three systems described in the section “Means for solving the problem”, combined
together define a full texture unit. Given an input 2D texture coordinate
(u,v), an output color RGBA is generated. Figure 1 shows the decomposition into
modules of the proposed means. The first stage is to perturb the (u,v)
coordinates, resulting in (u’,v’). The second stage is to map the 2D coordinate (u,v) to a 1D
coordinate t, and the final stage is to use the 1D coordinate t as an index in
a look up table containing the 1D texture image.  Figure 1 shows
decomposition in two modules of the disclosed invention. Given a 2D input
texture coordinate (u,v), the module 1000 (Perturbater) modifies (u,v),
resulting in (u’,v’), that are
then used as input in the module 3000 CMap, that maps the 2D coordinate to a 1D
coordinate t. This 1D coordinate is then used as index in the module 5000 1D
Texture Look up Table.
Aspect 1: Procedural 1D pseudo random pattern
generation
Module 1000: Perturbater
The first aspect of the invention relate the
perturbation of input 2D texture coordinates (u,v). The Perturbater module, a
system for computing a 2D texture coordinate in a computer system, comprising:
a means for obtaining a 2D texture coordinate
(u,v);
a means for generating two 1D intervals of two
random values using the coordinate u and v; 
a means for combining the two 1D intervals of
random values to a 2D interval of four random values;
a means for generating a random value depending on
the texture coordinate (u,v) and the 2D interval of four values; and 
a means for combining the random value with the
input texture coordinates (u,v) resulting in (u’,v’), perturbed the 2D texture coordinate.
The means for obtaining a 2D texture coordinate
(u,v) obtains the u and v. The  means for generating two 1D intervals of
two random values using the coordinate u and v, obtains the u and v and
generates the two 1D intervals. The means for combining the two 1D intervals of
random values to a 2D interval of four random values, combines the two 1D
intervals to obtain the 2D interval of four random values.  The means for
generating a random value depending on the texture coordinate (u,v) and the 2D
interval of four values obtain the 2D interval value and gererates the random
value.  The means for combining the random value with the input texture
coordinates (u,v) resulting in (u’,v’), combines the random value with the input texture coodinates (u,v)
and obtain the perturbed the 2D texture coordinate, (u’,v’).
The first system described a usual bus input from
some preceding modules. 
The second system is a general module composed of
2 random number generators. In this general module, the random generator number
is used, e.g., two times, one time with the input u and the second with the
input v. Four random values are generated, (u0, u1) with u as input, and (v0,
v1) with v as input. Figure 2 shows the decomposition into sub modules of the
module 1000 Perturbater.  In the following, we describe each of these sub
modules.
Module 1100: random1D. 
The random1D module is instantiated two times in
the module 1000. It is used separately on u and v coordinates. Given an input
coordinate t, the task of this module is to generate two random values and a
floating value that will be used later respectively in the random2D module
(1200) and in the randomCombiner module (1300). The module responsible for
generating the random value is called hereafter pseudoRandomGenerator1D (this
module is instantiated two times in the module random1D, so in total, four
instance of this module exists as the random1D module is instantiated two
times).
The functionality of the module
pseudoRandomGenerator1D is as follows. It uses three “magic” numbers. It is sufficient to define these numbers are simple
unsigned integer values, with an interesting bit representation. The first
magic number is called “magic mask” and is an unsigned long value (32 bits). The two others are called
hereafter “magic_shift1” and “magic_shift2” and are respectively a 4 bit
value and an 8 bit value. All three magic numbers are constants. The proposed
bit length is given for illustration purpose. Other bit length can be chose
with modifying drastically the disclosed invention. Main advantage of using
these bit length is the extreme small size (in terms of Hardware) of this
module.
First, the input parameter t (either equal to u or
v) is decomposed into two values, TA and TB such as TB is lower than one, and
TA+TB is equal to t. The value TA is used to generate a value called maskT,
defined as follows:
MaskT= (magic_mask >>
((TA*magic_shift2)&0xF))&0xF (1)
Where & is the bit-and operation, and &0xF
means that the first four bits (lowest) are considered; in other words, it
maskT is a 4 bits value, which allow to implement this function as a very small
circuit. We explicitly write &0xF for sack of clarity, but in actual
hardware implementation, this operation can be implicitly defined with proper
circuit implementation.
Meanwhile (i.e. in parallel), another circuit is
used to project the value TB in the interval [0, magic_shift1], and the result
of the projection is a value TT. 
TT = (TB)*magic_shift1.  (2)
Similarly, the value TT is decomposed into two
parts, TTA and TTB such as TTB is lower than one, and TTA+TTB is equal to TT.
The value TTB will be used in the module randomCombiner (1300) module. 
The value TTA is used to actually generate the
random number, together with previously computed maskT (see eq. 1). The random
value corresponding to TTA is then defined as follows:
t0=((((1+TTA)*magic_shift2)&0xF)^MaskT)&0xF       (3)
The output is a random number (obviously pseudo
random number) defined as a four bits value. 
The module 1100 Random1D actually generates 2
random values for a given input coordinates t. The reason is that we wish to
map the input coordinate t to an interval in random space. The aim of this module
is to define two random values than define an interval in random space where t
and its neighboring interval will be projected to. In other words, it means
that a random value should not be generated for each value of t, but rather a
random interval should be defined upon t neighboring interval. 
When generating the interval, continuity should be
considered and one should insure that if for a given input value the interval
in random space [R0,R1] is generated, then the next interval must be [R1,R2].
As one can see in the eq. (3), the value TT is in the interval [0,
magic_shift1]. In order to insure a certain continuity, a special procedure
should handle the case when TTA is equal to “magic_shift1”.  When TTA is greater or equal to the value magic_shift1, then
equations (1) and (3) becomes respectively:
MaskT= (magic_mask >>
(((TA+1)*magic_shift2)&0xF))&0xF     (1’)
t0=((((1)*magic_shift2)&0xF)^MaskT)&0xF                    (3’)
As mentioned earlier, very small bit width are
sufficient. A preferred embodiment of the module pseudoRandomGenerator1D
comprises:
the means for generating two 1D intervals of two
random values using the coordinate u and v is a means for generating two 1D
intervals of two random values using two separate but identical random number
generators with either u or v coordinate as input (hereinafter called as “t”) resulting in the 1D intervals of two
random values (u0,u1) and (v0,v1), where each of the number generators
comprising:
a means for computing two numbers TA and TB using
the input value t, where TB is a float value lower than one and TA+TB is equal
to one; 
a means for projecting the value TB to a random
value TT comprising:
a means for obtaining a constant value called
hereafter “magic_shift1”; and
a means for projecting the TB in the interval
[0,magic_shift1] resulting in TT comprising a single multiplexer and
calculating TT = TB*magic_shift1;
a means for computing two numbers, TTA and TTB,
using the value TT, where TTB is a float value lower than one and TTA+TTB is
equal to one,
a means for generating a random value using the
set of parameters {TA,TTA} and {TA,TTA+1}, resulting in two random values T1
and T2 comprising:
a means for obtaining constant values the “magic_shift1”, “magic_mask”, and “magic_shift2”,
a means for calculating a following value, a
pseudo random value, using either TTA or TTA+1 as input, called hereafter “maskT”, comprising a “if statement logic circuit”, a multiplexer
and a logic right bit shift operation (>>):
maskT = magic_mask>>(TA*magic_shift2)
if the input value, noted D and either equal to
TTA or TTA+1, is strictly lower than magic_shift1, and calculating the value;
and otherwise calculating the following value:
maskT=magic_mask>>((TA+1)*magic_shift2);
a means for calculateing a random number R using
the input value, noted D and either equal to TTA or TTA+1, and maskT as input
comprising a “if statement logic circuit”, a multiplier and the bit-logic operator “XOR” (noted ^) and calculating the value 
R = ((1+TTA)*magic_shift2)^maskT, 
if D is lower than magic_shift1, and the value,
and  
R = ((1)*magic_shift2)^maskT, otherwise,
the means for combining the two 1D intervals of
random values to a 2D interval of four random values is a means for combining
the two 1D intervals of random values (u0,u1) and (v0,v1) to a 2D interval
[(u0,v0),(u1,v1)] and comprising:
a means for obtaining the “magic_mask”;
a means for calculating two following values
called hereafter maskA and maskB using the two random values u0 and u1, where
each mask calculation comprises a single logic right bit shift operation and
calculating for an input value “t”: 
mask = (magic_mask>>t)
wherein
“t” is either equal to u0 or u1
and the resulting value “mask”
is equal either to maskA or maskB, respectively;
a means for calculating a random value using the
four sets of inputs {u0,v0,maskA}, {u0,v1,maskA}, {u1,v0,maskB} and
{u1,v1,maskB} resulting in the random values R1, R2, R3, and R4, comprising an
adder and a bit logic XOR (^) operation and calculating the value for each
input {s,t,mask}:
R=(s+t)^mask
the means for combining the random value to the
input texture coordinates (u,v) and the 2D interval of four values comprising:
a means for obtaining UUB and VVB from the random
number generator, where previously named value TTB is equal to UUB when the
coordinate u is used as input of the random number generator, and
correspondingly VVB when the random number generator is used using v coordinate
as input,
a means for calculating a weighted random value
used four times using the four set of inputs {R1,UUB,VVB}, {R2,UUB-1.0,VVB},
{R3,UUB,VVB-1.0} and {R4,UUB-1.0,VVB-1.0} resulting in four weighted values
r1,r2,r3 and r4, where each module comprises an adder and a multiplexed and
calculating the value for each input {R,a,b}:
r = R*(a+b)
a means for calculating a random value RV using
r1,r2,r3,r4 and UUB and VVB as inputs and bilinear interpolation module, where
r1,r2,r3 and r4 are the interpolated values and UUB and VVB are as parameters
for the interpolation comprising:
a means for modifying UUB and VVB to control the bilinear
interpolation behavior comprising a look-up table that maps UUB and VVB to UUB’ and VVB’, with UUB and VVB in the interval
[0,1] by definition; and 
a means for computing bilinear interpolation using
the values UUB’ and VVB’ as
parameters for the bilinear interpolation;
a means for controlling a generation of the random
value comprising:
a means for modifying  the input coordinates
(u,v) comprising for each input u and v:
a scaling, a translation and a clamping operation
comprising an adder, a multiplexer and a clamping circuit,
a means for obtain the scaling and translation
factors and the clamping operation type,
a means for modifying the out value RV comprising:
a scaling operation comprising a multiplexer, and 
a means for obtain the scaling factor and the
clamping operation type,
the means for combining the random value with the
input texture coordinates (u,v) resulting in (u’,v’) is a means for combining RV with the input coordinates (u,v) to
produce the output (u’,v’)
comprising two adders and two if statement logic circuit and calculating
independently the u’ and v’
coordinates as:
if(u>0) then u’=u+RV
otherwise u’=u-RV
if(v>0) then v’=v+RV
otherwise v’=v-RV
As shown in Fig. 2, the output of the module
random1D are an interval of random number (t0,t1), and the value TTB. This
module is instantiated two times, using either u or v as input. In the case
that the input value is u, the output is the tuple (u0,u1,UUB), and in the case
v is used as input, the output tuple is (v0,v1,VVB). The random intervals
[u0,u1] and [v0,v1] are used as inputs of the module 1200 (random2D) and the
values UUB and VVB are used in the module 1300 (randomCombiner).
Module 1200: random2D. 
The inputs of this module are two interval of
random values [u0,u1] and [v0,v1].  It is clear that due to the means used
to generate the 1D intervals, the interval [u0,u1] and [v0,v1] are
uncorrelated. The Random2D module is responsible for generating 4 new random
values using the two 1D input intervals [u0,u1] and [v0,v1]. 
A preferred embodiment for this circuit is to use
4 instances of a very small circuit, where each circuit will generate a single
random value, with different sets of input values. This circuit is referred
hereafter as pseudoRandomGenerator2D.
The random2D module first generates 4 set of
inputs for this circuit defined as {u0, v0, maskA}, {u0, v1, maskA}, {u1, v0,
maskB} and {u1, v1, maskB}. The values maskA and maskB can also be implemented
as 4 bit value using a single logic right bit shift operation. A preferred embodiment
for calculating these masks can be a circuit implementing the following
procedure:
maskA= ((magic_mask>>(u0)))&0xF;                  
maskB= ((magic_mask>>(u1)))&0xF;                  
After calculating the maskA and maskB values, four
instances of the circuit pseudoRandomGenerator2D are used in parallel with the
set of input parameters {u0,v0,maskA}, {u0,v1,maskA}, {u1,v0,maskB} and
{u1,v1,maskB}. A preferred embodiment of this circuit comprises an adder, a
bit-shift and an XOR operation, each operation being defined with 4 bit values,
resulting in a very small circuit size. 
A preferred embodiment of the module random2D
comprises:
a means for using the constant number magic_mask,
a means for calculating two new 4 bit numbers
called hereafter maskA and maskB using the two random values u0 and u1, where
each mask calculation comprises a single logic right bit shift operation (4
bits) and calculating for an input value t the value:
mask = (magic_mask>>t)&0xF
with t either equal to u0 or u1 and the resulting
4 bit value is respectively equal either to maskA or maskB,
a means for calculating a 4 bit random value used
four times independently using the four sets of inputs {u0,v0,maskA},
{u0,v1,maskA}, {u1,v0,maskB} and {u1,v1,maskB} resulting in the 4 bit random
values R1,R2,R3,R4  where each module comprises an adder and a bit logic
XOR (^) operation and calculating the value for each input {s,t,mask}:
R=((s+t)^mask)&0xF
With R
a 4 bit random value.
The 4 bit random value {R1, R2, R3, R4} are used
in the module 1400 randomCombiner. 
Module 1300: randomCombiner.
The input of this module are the random values R1,
R2, R3, and R4 from the module  1200 random2D and UUB and VVB from the two
instances of the module 1100 random1D. This module is responsible for
generating the final random value that will be used to perturb the initial
input coordinates (u, v). The generation of the final random value RV can be
decomposed into two main steps. 
First a weighing function is applied to R1, R2, R3
and R4 resulting in 4 new random values r1, r2, r3, and r4. A preferred
embodiment for the weighting function is to use a four times a similar circuit,
with the four different set of inputs, and to define the weighting function as
a signed distance function. The choice of this function is critical.
In the patent document WO 01/39126 A1, this
function is replaced with a so-called gradient calculation. The usage of a
gradient function implies that for a given hash code (in other word a kind of
random number obtained by successive permutations using look up tables), a
certain gradient value is computed, resulting in a weighted value. The hash
code is used only to define the gradient value; i.e. it indicates which input
values to add or to subtract, but the value of the hash code itself is not used
in the actual calculation of the gradient value. Similarly, the calculation of
a gradient value is performed four times in the circuit proposed in the cited
patent document WO 01/39126 A1, resulting in four weighted values. 
Although the aim of the randomCombiner is similar
to the gradient calculation, the means and the meaning of the obtained values
are completely different. In the present invention, a prefer embodiment of the
weighting function is based on a simplified signed distance function. The first
major difference is to implement a circuit computing a signed distance function
do not requires if statement / bit comparison as in the circuit proposed in the
patent document WO 01/39126 A1, and also it is simpler. Given two inputs, the
signed distance is directly evaluated, and then the signed distance value is
used as weighting value to weight each random value. In the case of gradient
function, given a set of inputs, the hash code has to be decoded, a selection
from the input values has to be made, some selected values must be negated, and
depending on the hash code, the selected values are combined (added). The
randomness is introduced when performing the selection of the input values
depending on the hash code. The value of the hash code is not used in the final
calculation of the gradient.
This last sentence describes one of the major
differences; in the present invention, the random value is the value that will
be weighted, and the weighting value is calculated as signed distance function.
A preferred embodiment to implement a signed distance function is defined as a
circuit (referred hereafter as SignedDistance) with 2 input values A and B, a
single adder, and outputting the value A+B. To weight the four random values
R1, R2, R3 and R4 the circuit SignedDistance is used four times with the four
set of inputs {R1, UUB, VVB}, {R2, UUB-1.0, VVB}, {R3, UUB, VVB-1.0} and {R4,
UUB-1.0, VVB-1.0}. In the triplet {r, a, b}, the specific choice of a and b
allows one to define a simplified signed distance and can be expressed as a+b .
A preferred embodiment of the weighting circuit is
to include the weighting calculation in the SignedDistance circuit, re-named
here after randomWeighting circuit. This circuit is duplicated four times in
the module 1300 randomCombiner, with the four set of inputs {R1, UUB, VVB},
{R2, UUB-1.0, VVB}, {R3, UUB, VVB-1.0} and {R4, UUB-1.0, VVB-1.0}. Each
instance of the randomWeighting circuit includes an adder and a multiplexer and
evaluates the new random value r = R*(a+b).
Note that R is a 4 bit value, and a and b are two
float values. To define floats using 16 bit are sufficient to obtain good
result (i.e. without visible artifacts in the final image) . The value R can be
converted to some float values, preferably in the interval [-1, 1]. As R is a 4
bits value, this conversion is straightforward (only 16 possible float values).
The proposed bit width offers a good tradeoff between quality and circuit size.
The four randomWeighting circuits output four
weighted random values r1, r2, r3 and r4. 
The second main step of the module 1300
randomCombiner is to interpolate the weighted noise values r1,r2,r3 and r4
using a bilinear interpolation. The parameters used for the bilinear
interpolation are derived from UUB and VVB. 
In the patent document WO 01/39126 A1, a similar
scheme is proposed. A bilinear interpolation is performed on the gradient
values using as parameters two values. For sack of clarity in the following
comparison, let s be one of the input parameter, and s’
be the modified value of s that will be used to interpolate the gradient
values. In the patent document WO 01/39126 A1, s is mapped to s’ using a look up table. The look up table contains a second order
polynomial function, a so-called ease curve. It is claimed that the aim of this
mapping is increase the continuity of the result of the bilinear interpolation.
Furthermore, as the choice of the polynomial function is fixed, the properties
of the table (bit width for the content and bit width for the table entry) are
fixed.
In the invention disclosed in this document, a
look up table is also used. Nevertheless, the input of the look up table is of
greater accuracy, as it is a 16 bit float value, in the interval [0, 1] by
definition. The aim of the look up table in the present invention is not
necessarily to increase the continuity in the bilinear interpolation. The aim
is far more general, as it is important to provide a mean (for the user) to
control the appearance of the resulting texture. In this sense, the look-up
table is defined in a circuit, where external data can be used to initialize
this table. By initialization, we mean that someone (a user) can load any
pre-computed function in the look-up table. By offering this possibility, the
disclosed invention greatly increases the flexibility and configurability, and
permits to obtain a larger variety of texture pattern. Examples of functions
include but are not restricted to constant function, bias function, gain
function, trigonometric and polynomial functions for instance. 
The previously described look up table transforms
the input parameters UUB and VVB to UUB’ and VVB’. These values are then used to perform a bilinear interpolation.
UUB’ linearly interpolates (r1,r2) and (r3,r4),
resulting in 2 values, these two values are interpolated using VVB’. The final result is a random value RV.
The last step is to perturb the initial
coordinates (u,v) with the random value RV. One preferred embodiment of the
present invention is to simply add or subtract RV to u and to v depending
respectively on the sign of u and of v. A circuit defining such embodiment
comprises, two if statement logic circuit, two negate operations and two
adders, and calculates:
if(u>0) then u’=u+RV
otherwise u’=u-RV
if(v>0) then v’=v+RV
otherwise v’=v-RV
The perturbed coordinates (u’,v’) are then used in the module 3000.
A preferred embodiment for controlling the
generation of the random value is to be used a set of scaling, translation and
clamping operation. It can be decomposed in two different control, a
pre-control and post control. While the first control is applied to the input
coordinates (u, v) before calculating the random value, the post control is
applied to the output value RV. 
The scaling and translation operation for the
pre-control is implemented in the preferred embodiment as an adder and a
multiplexer, calculating for each input coordinate u and v the values, referred
generically as t, (t+translation)*scale, where translation and scale are some
values defined somewhere else (typically by the user). Typically, the resulting
value is then clamped using traditional clamping operations such that the
output value is in the interval [0, 1]. Clamping operations are well known
clamping operations in computer graphics and are not included as new invention
in the disclosed invention. Examples of clamping operations are edge function,
repeat function, and mirror function among several.
The post-control operation is similar to the
pre-control operation, with the difference that it is applied to the output
value RV. A preferred embodiment is to implement the post-operation as
multiplexer, calculating the value RV*scale, where scale is another value
defined somewhere else (typically user defined). Similar clamping operations
are performed on the resulting value, insuring that the resulting is in the
interval [0,1].
Second aspect of
the invention: 2D texture image generation using 1D texture image and a
configurable 2D to 1D mapping function
The second aspect of the invention disclosed in
this document corresponds to the module 3000 shown in Figure 1. The module is
called as Coordinates Mapping, CMap for short. As its name indicates, this
module is responsible for mapping the 2D input coordinates (u, v) (possibly
from the output of the noise module (u’,v’), to a 1D texture coordinate (t). 
The second aspect of the invention basically
directs to a system for generating a 2D texture image comprising:
a means for obtaining a texture coordinate (u,v);
a means for projecting the texture coordinate (u,v)
to a 1D texture coordinate (t);
a means for accessing and obtaining a 1D texture
image stored in memory using the 1D texture coordinate (t); and 
a means for generating a 2D texture image using
the 1D texture image.
The means for obtaining a texture coordinate (u,v)
obtains the u and v.  The means for projecting the texture coordinate
(u,v) to a 1D texture coordinate (t) projects the the texture coordinate (u,v)
to a 1D texture coordinate (t).  The means for accessing and obtaining a
1D texture image stored in memory using the 1D texture coordinate (t) access
and obtain the 1D texture image using the 1D texture coordinate (t).  The
means for generating a 2D texture image using the 1D texture image generates
the 2D texture image using the 1D texture image.
A preferred embodiment of the second aspect
directs to a system described the above wherein:
the means for projecting the texture coordinate
(u,v) to a 1D texture coordinate (t) comprising:
a means for selecting two functions G1, and G2
among several fixed functions;
a means for defining a look up table representing
any real function,  hereafter called as F; and 
a means for combining the functions the G1, the
G2, and the F.
A preferred embodiment of the second aspect
directs to a system described the above, wherein:
the means for projecting the texture coordinate
(u,v) to a 1D texture coordinate (t) comprising:
a means for selecting two functions G1, and G2,
from the function G(u,v) equal to {u, v, u+v, u-v, u^2, v^2, sqrt(u2+v2),
u+v+sqrt(u2+v2), u+v-sqrt(u2+v2), min(u,v), max(u,v), constant}, where “sqrt” is the mathematical function square
root, and x^2 means x power 2 (x times x);
a means for defining a look up table representing
any real function, hereafter called as F;
a means for combining the functions the G1, the G2
and the F comprising:
a means for using the G1 as input of the look up
table F, thus calculating F (G1 (u,v)); and
a means for using the G2 to calculate the product
of the output of the look up table with the G2, resulting in the value F (G1
(u,v))* G2 (u,v);
the means for accessing a 1D texture image stored
in memory using the 1D texture coordinate F(G1(u,v)*G2(u,v).
A preferred embodiment of the above mean is a very
small circuit, using in total 4 adders, 3 multiplexers and a square root
operator. The main benefit of this circuit is it defines a mapping function,
called hereafter Map, that maps a 2D point (u,v) on a 1D point t. This mapping
is a composition of three functions, and can be expressed in general as:
F(G1(u,v))*G2(u,v),                                        (4)
Where G1 and G2 are chosen in a set of fixed
functions, and F is a look up table. A representative set of fixed functions
includes in a preferred embodiment the following function:
(5)
| G(u,v) = u                                   (5a)
| G(u,v) = v                                               (5b)
| G(u,v) = u^2                                             (5c)
| G(u,v) = v^2                                             (5d)
| G(u,v) = u^2+v^2                                         (5e)
| G(u,v) = sqrt(u^2+v^2)                          (5f)
| G(u,v) = u+v+sqrt(u^2+v^2)                               (5g)
| G(u,v) = u+v-sqrt(u^2+v^2)                               (5h)
| G(u,v) = min(u,v)                                        (5i)
| G(u,v) = max(u,v)                                        (5j)
| G(u,v)  = constant                                       (5k)
A circuit implementing can this set of fixed
functions includes 5 adders, 2 multiplexers and a square root operator. The
major advantage is the variety in choice of the input to look up table, and the
variety of the result. Of course, this variety is much lower lower than a fully
programmable circuit (i.e. fragment shader), but it is sufficient in several
case as several mathematical functions frequently used in computer graphics in
a texturing context can be expressed. 
For
instance, equations 5e and 5f expressed a distance function, and thus, with a
proper look up table, all the potential, Gaussian and any other distance based
functions can be implemented. For a set of possible functions based on distance
functions, one can see the following reference “C.
Blanc and C. Schlick. Extended field functions for soft objects. Implicit
Surfaces'95, Eurographics/ACM SIGGRAPH Workshop, pages 21-32, 1995.”
Equations
5h-5i and 5g-5j defines the well know functions min/max with different level of
continuity. For more details description on set-theoretic functions, the
following reference can be used “A. Pasko, V. Adzhiev,
A. Sourin, and V. Savchenko. Function representation in geometric modelling:
concept, implementation and applications. The Visual Computer, 11(8):429-446,
1995.” Note that if one wants to use only a
set-theoretic operation, then the identity function can be loaded in the look
up table, and G2 can be set to the constant 1.
Another
common function is a so-called norm function, expressed as u/sqrt(u^2+v^2).
This function can be evaluated using the disclosed embodiment while choosing G1
equal sqrt(u^2+v^2),  G2 equal to u, and the look up table, corresponding
to the look up table, set with the pre-sampled function 1/x.
The preferred embodiment of the circuit
implementing the module 3000 CMap is the set of functions described in
equations 5a to 5k. It provides a good trade-off between circuit size and
flexibility. It is obvious that other fixed functions can be added to increase
this flexibility, if circuit size is not a critical matter. It is also obvious
that if the hardware size is not a critical matter, the projection function can
be extended by several other compositions. For instance, the proposed
embodiment can be extended to F2(F(G1(u,v))*G2(u,v))*G3(u,v), F2 and G3 are
possibly two new circuits defining either a new set of fixed functions, or a
new table.
The last step in the disclosed invention is to use
the value (t) defined in eq. (4) to compute an index in a 1D texture image,
resulting in an RGBA color.  A preferred embodiment of the index
calculation includes usual techniques in computer graphics and in texture
related technique. Index calculation is not part of the claims of the disclosed
invention. 
A straightforward extension of this invention
disclosed in this document is to generate two output values t_rgb and t_a,
instead of a single value t. This allows to index respectively an RGB color and
an A (alpha) value separately, resulting in an improved flexibility. A preferred
embodiment of this extension comprises:
means for project a 2D clamped texture coordinate
(u,v) to a 1D texture coordinate (t) comprising:
a means for selecting four functions G1_rgb,
G2_rgb, G1_a and G2_a, among several fixed functions comprising but not
restricted to G(u,v) equal to {u,v,u+v,u-v,u^2,v^2,sqrt(u2+v2),
u+v+sqrt(u2+v2), u+v-sqrt(u2+v2), min(u,v), max(u,v)}, where sqrt is the
mathematical function square root, and x^2 means x power 2 (x times x),
comprising 5 adders, 2 multiplexers and one square root operators;
a means for defining two look up tables
representing any real function, corresponding hereafter to F_rgb and F_a;
a means for combining the functions G1_rgb, G2_rgb
and F_rgb on one side and on the other side to combine G1_a, G2_a and F_a
comprising:
a means for obtaining G1_rgb as input of the look
up table F_rgb, thus calculating F_rgb (G1_rgb (u,v));
a means for obtaining G2_rgb to calculate the
product of the output of the look up table with G2_rgb, resulting in the value
F_rgb(G1_rgb (u,v))* G2_rgb (u,v) using a single multiplexer;
a means for obtaining G1_a as input of the look up
table F_a, thus calculating F_a(G1_a(u,v));
a means for obtaining G2_a to calculate the
product of the output of the look up table with G2_a, resulting in the value
F_a(G1_rgb (u,v))* G2_a (u,v) using a single multiplexer.
Using this preferred embodiment, separate
treatment can be performed on RGB and A, with a very small hardware changes,
i.e. an additional look up table, an additional multiplexer and an extension of
the means to select the input functions G1_rgb,G2_rgb,G1_a and G2_a.
Example 1:
The example shown in Fig 3 is an example of resulting image than can be obtained with the
disclosed invention. It illustrates difference choices for the mapping
functions. The input geometry is a quadrangle, where the lower left corner has
a texture coordinate (u0, v0) equal to (-1,-1), and the upper right corner has
a texture coordinate (u1, v1) equal to (1, 1), and the u coordinate is along
the horizontal axis in the image. The 1D texture image is defined as an array
of 2 colors. The first color is white, and the second color is black. This
initial setting is used to generate the 3 images. Only the mapping function
changes. The general form of the mapping function is:
Map(u,v)
= F(G1(u,v))*G2(u,v) 
For the first image, the fixed function G1 defined
as G1(u,v) = u; the second fixed function G2 is defined as G2(u,v)=1, and the
function F (look up table), is defined as F(x) = x (identity function). Therefore,
the final function is Map(u,v)=u. Recalling that the texture image is contains
only 2 color, black and white, the predictable result is a grey gradient. When
u is equal to 0, the resulting color is white, and when the u is equal to 1,
the result is black; in-between, the intermediate color is a grey color.
For the second image the fixed function G1 defined
as G1(u,v) = u^2+v^2; the second fixed function G2 is defined as G2(u,v)=u^2,
and the function F (look up table), is defined as F(x) = 1/x (inverse
function). The result is a grey gradient corresponding to the function
u^2/(u^2/v^2).
For the last image, the fixed function G1 defined
as G1(u,v) = sqrt(u^2+v^2); the second fixed function G2 is defined as
G2(u,v)=1, and the function F (look up table) as potential function. Note that
the function G1 is the distance to the center of the quadrangle, then, when the
distance is equal to zero, the potential is equal to 1, and it drops to zero as
the distance to the center increases, resulting in the radial grey gradient.
Example 2:
The example shown in Fig 4 is an example of resulting image than can be obtained with the
disclosed invention. One mapping function has been chosen and different random
perturbations are applied. The input geometry is a quadrangle, where the lower
left corner has a texture coordinate (u0, v0) equal to (-1,-1), and the upper
right corner has a texture coordinate (u1,v1) equal to (1, 1), and the u
coordinate is along the horizontal axis in the image. The 1D texture image is
defined as an array of 2 colors. The first color is white, and the second color
is black. To generate the three images, the same mapping function as been used,
and is equal to 
Map(u,v)
= u
For the first image, no perturbation is applied.
As one can see, the result is similar to the first image of Fig. 3. In the
second and third images, a perturbation is applied, with different scaling
factors set to the pre-control and post-control operations.
Industrial Applicability
The circuit
of the present invention is applicable for 3D Computer Graphic chips. 
The Brief Description of the Drawings
Figure 1 shows decomposition in two modules of the
disclosed invention. Given a 2D input texture coordinate (u,v), the module 1000
(Perturbater) modifies (u,v), resulting in (u’,v’), that are then used as input in the module 3000 CMap, that maps
the 2D coordinate to a 1D coordinate t. This 1D coordinate is then used as
index in the module 5000 1D Texture Look up Table.
Figure 2 shows decomposition into sub-modules of
the module 1000 Perturbater. It is decomposed into two identical modules
random1D, a single random2D module, a randomCombiner and finally a
perturbCoordinate module.
Figure 3 is an example of resulting image than can
be obtained with the disclosed invention. It illustrates difference choices for
the mapping functions.
Figure 4 is an example of resulting image than can
be obtained with the disclosed invention. One mapping function has been chosen
and different random perturbations are applied.
Claims 
A system for computing a 2D texture coordinate in
a computer system comprising:
a means for obtaining a 2D texture coordinate
(u,v);
a means for generating two 1D intervals of two
random values using the coordinate u and v; 
a means for combining the two 1D intervals of
random values to a 2D interval of four random values;
a means for generating a random value depending on
the texture coordinate (u,v) and the 2D interval of four values; and 
a means for combining the random value with the
input texture coordinates (u,v) resulting in (u’,v’), perturbed the 2D texture coordinate.
A system in accordance with claim 1 wherein:
the means for generating two 1D intervals of two
random values using the coordinate u and v comprising,
two separate but identical random number
generators with either u or v coordinate as input resulting in the 1D intervals
of two random values (u0,u1) and (v0,v1); and
the means for combining the two 1D intervals of
random values to a 2D interval of four random values combines the two 1D intervals
of random values (u0,u1) and the (v0,v1) to a 2D interval [(u0,v0),(u1,v1)].
A system in accordance with claim 1 wherein:
the means for generating two 1D intervals of two
random values using the coordinate u and v comprising two separate but identical
random number generators with either u or v coordinate as input (hereinafter
also referred as “t”) resulting
in the 1D intervals of two random values (u0,u1) and (v0,v1), wherein each of
the random number generators comprising:
a means for computing two numbers TA and TB from
the input value “t”, where TB
is a float value lower than one and TA+TB is equal to one; 
a means for projecting the value TB to a random
value TT;
a means for computing two numbers TTA and TTB from
the value TT, where TTB is a float value lower than one and TTA+TTB is equal to
one; and 
a means for generating a random value using the
set of parameters {TA,TTA} and {TA,TTA+1} resulting in two random values T1 and
T2;
the means for combining the two 1D intervals of
random values to a 2D interval of four random values is a means for combining
the two 1D intervals of random values (u0,u1) and (v0,v1) to a 2D interval
[(u0,v0),(u1,v1)] and comprising:
a means for using a constant integer value called
hereafter “magic_mask”;
a means for calculating two new number called
hereafter “maskA” and “maskB” using the two random values u0 and
u1; and
a means for calculating random values using four
sets of inputs {u0,v0,maskA}, {u0,v1,maskA}, {u1,v0,maskB} and {u1,v1,maskB}
resulting in the random values R1, R2, R3, and R4;
the means for combining the random value to the
input texture coordinates (u,v) resulting in (u’,v’) comprising:
a means for obtaining UUB and VVB from the random
number generator, where previously named value TTB is equal to UUB when the
coordinate u is used as input of the random number generator, and
correspondingly VVB when the random number generator is used using v coordinate
as input;
a means for calculating a weighted random value
using the four set of inputs {R1, UUB, VVB}, {R2, UUB-1.0, VVB}, {R3, UUB,
VVB-1.0} and {R4, UUB-1.0, VVB-1.0} resulting in four weighted values r1, r2,
r3 and r4; and
a means for calculating a random value RV using
the r1, r2, r3, r4, UUB and VVB as inputs, comprising bilinear interpolation
module, wherein r1, r2, r3 and r4 are the interpolated values and UUB and VVB
are as parameters for the interpolation;
the system further comprising a means for
controlling the generation of the random value comprising:
a means for modifying the input coordinates (u,v);
and 
a means for modifying the out value RV;
the means for combining the random value with the
input texture coordinates (u,v) resulting in (u’,v’) is a means for combining the RV with the input coordinates (u,v)
to produce the output (u’,v’).
A system in accordance with claim 1 wherein:
the system further comprising a means for
controlling the generation of the random value comprising:
a means for modifying the input coordinates (u,v)
comprising for each input u and v:
a scaling, a translation and a clamping operation
and 
a means for obtain the scaling and translation
factors and the clamping operation type,
a means for modifying the out value RV comprising:
a scaling and a clamping operation and
a means for obtaining the scaling factor and the
clamping operation,
the means for generating two 1D intervals of two
random values using the coordinate u and v comprising two separate but
identical random number generator with either u and v coordinate as input
(refers after as t) resulting in the 1D intervals of two random values (u0,u1)
and (v0,v1), wherein the random number generator comprising:
a means for computing two numbers TA and TB from
the input value t, where TB is a float value lower than one and TA+TB is equal
to  one, 
a means for projecting the value TB to a random
value TT comprising:
a means for obtaining a constant value called
hereafter magic_shift1, and
a means for projecting TB in the interval
[0,magic_shift1] resulting in TT,
a means for defining two numbers TTA and TTB using
the value TT, wherein TTB is a float value lower than one and TTA+TTB is equal
to one,
a means for generating a random value using the
set of parameters {TA, TTA} and {TA, TTA+1}, resulting in two random values T1
and T2 ,respectively, comprising:
a means for defining and use constant values
called hereafter magic_mask,magic_shift1 and magic_shift2,
a means for calculating a pseudo random value
using D value (corresponding either to TA or TA+1), called hereafter maskT, and
a means for calculating a random number R using
either TA or TA+1, and using the value TTA and the previously computed value
maskT,
the means for combining the two 1D intervals of
random values to a 2D interval of four random values is a means for combining
the two 1D intervals of random values (u0,u1) and (v0,v1) to a 2D interval
[(u0,v0), (u1,v1)] and comprising:
a means for obtaining the constant number
magic_mask,
a means for calculating two new number called
hereafter maskA and maskB using the two random values u0 and u1, and
a means for calculate a random value used four
times independently using the four sets of inputs {u0, v0, maskA}, {u0, v1,
maskA}, {u1, v0, maskB} and {u1, v1, maskB} resulting in the random values R1,
R2, R3, and R4, 
the a means for combining the random value with
the input texture coordinates (u,v) resulting in (u’,v’) comprising:
a means for obtaining UUB and VVB from the random
number generator, where previously named value TTB is equal to UUB when the
coordinate u is used as input of the random number generator, and
correspondingly VVB when the random number generator is used using v coordinate
as input,
a means for calculating a weighted random value
used four times using the four set of inputs {R1,UUB,VVB}, {R2,UUB-1.0,VVB},
{R3,UUB,VVB-1.0} and {R4,UUB-1.0,VVB-1.0} resulting in four weighted values r1,
r2, r3 and r4,
a means for calculating a random value RV using
r1, r2, r3, r4 and UUB and VVB as inputs and bilinear interpolation module,
where r1, r2, r3 and r4 are the interpolated values and UUB and VVB are as parameters
for the interpolation comprising:
a means for modifying UUB and VVB to control the
bilinear interpolation behavior,
a means for combining the random value RV with the
input coordinates (u,v) to produce the output (u’,v’).
A system in accordance with claim 1, wherein 
the means for generating two 1D intervals of two
random values using the coordinate u and v is a means for generating two 1D
intervals of two random values using two separate but identical random number
generators with either u or v coordinate as input (hereinafter called as “t”) resulting in the 1D intervals of two
random values (u0,u1) and (v0,v1), where each of the number generators
comprising:
a means for computing two numbers TA and TB using
the input value t, where TB is a float value lower than one and TA+TB is equal
to one; 
a means for projecting the value TB to a random
value TT comprising:
a means for obtaining a constant value called
hereafter “magic_shift1”; and
a means for projecting the TB in the interval
[0,magic_shift1] resulting in TT comprising a single multiplexer and
calculating TT = TB*magic_shift1;
a means for computing two numbers, TTA and TTB,
using the value TT, where TTB is a float value lower than one and TTA+TTB is
equal to one,
a means for generating a random value using the
set of parameters {TA,TTA} and {TA,TTA+1}, resulting in two random values T1
and T2 comprising:
a means for obtaining constant values the “magic_shift1”, “magic_mask”, and “magic_shift2”,
a means for calculating a following value, a pseudo
random value, using either TTA or TTA+1 as input, called hereafter “maskT”, comprising a “if statement logic circuit”, a multiplexer
and a logic right bit shift operation (>>):
maskT = magic_mask>>(TA*magic_shift2)
if the input value, noted D and either equal to
TTA or TTA+1, is strictly lower than magic_shift1, and calculating the value;
and otherwise calculating the following value:
maskT=magic_mask>>((TA+1)*magic_shift2);
a means for calculating a random number R using
the input value, noted D and either equal to TTA or TTA+1, and maskT as input
comprising a “if statement logic circuit”, a multiplier and the bit-logic operator “XOR” (noted ^) and calculating the value 
R = ((1+TTA)*magic_shift2)^maskT, 
if D is lower than magic_shift1, and the value, and 
R = ((1)*magic_shift2)^maskT, otherwise,
the means for combining the two 1D intervals of
random values to a 2D interval of four random values is a means for combining
the two 1D intervals of random values (u0,u1) and (v0,v1) to a 2D interval
[(u0,v0),(u1,v1)] and comprising:
a means for obtaining the “magic_mask”;
a means for calculating two following values
called hereafter maskA and maskB using the two random values u0 and u1, where
each mask calculation comprises a single logic right bit shift operation and
calculating for an input value “t”: 
mask = (magic_mask>>t)
wherein
“t” is either equal to u0 or u1
and the resulting value “mask”
is equal either to maskA or maskB, respectively;
a means for calculating a random value using the
four sets of inputs {u0,v0,maskA}, {u0,v1,maskA}, {u1,v0,maskB} and
{u1,v1,maskB} resulting in the random values R1, R2, R3, and R4, comprising an
adder and a bit logic XOR (^) operation and calculating the value for each
input {s,t,mask}:
R=(s+t)^mask
the means for combining the random value to the
input texture coordinates (u,v) and the 2D interval of four values comprising:
a means for obtaining UUB and VVB from the random
number generator, where previously named value TTB is equal to UUB when the
coordinate u is used as input of the random number generator, and
correspondingly VVB when the random number generator is used using v coordinate
as input,
a means for calculating a weighted random value
used four times using the four set of inputs {R1,UUB,VVB}, {R2,UUB-1.0,VVB},
{R3,UUB,VVB-1.0} and {R4,UUB-1.0,VVB-1.0} resulting in four weighted values
r1,r2,r3 and r4, where each module comprises an adder and a multiplexed and
calculating the value for each input {R,a,b}:
r = R*(a+b)
a means for calculating a random value RV using
r1,r2,r3,r4 and UUB and VVB as inputs and bilinear interpolation module, where
r1,r2,r3 and r4 are the interpolated values and UUB and VVB are as parameters
for the interpolation comprising:
a means for modifying UUB and VVB to control the
bilinear interpolation behavior comprising a look-up table that maps UUB and
VVB to UUB’ and VVB’, with UUB
and VVB in the interval [0,1] by definition; and 
a means for computing bilinear interpolation using
the values UUB’ and VVB’ as
parameters for the bilinear interpolation;
a means for controlling a generation of the random
value comprising:
a means for modifying  the input coordinates
(u,v) comprising for each input u and v:
a scaling, a translation and a clamping operation
comprising an adder, a multiplexer and a clamping circuit,
a means for obtain the scaling and translation
factors and the clamping operation type,
a means for modifying the out value RV comprising:
a scaling operation comprising a multiplexer, and 
a means for obtain the scaling factor and the clamping
operation type,
the means for combining the random value with the
input texture coordinates (u,v) resulting in (u’,v’) is a means for combining RV with the input coordinates (u,v) to
produce the output (u’,v’)
comprising two adders and two if statement logic circuit and calculating
independently the u’ and v’
coordinates as:
if(u>0) then u’=u+RV
otherwise u’=u-RV
if(v>0) then v’=v+RV
otherwise v’=v-RV
6.A system for generating a 2D texture image
comprising:
a means for obtaining a texture coordinate (u,v);
a means for projecting the texture coordinate
(u,v) to a 1D texture coordinate (t);
a means for accessing and obtaining a 1D texture
image stored in memory using the 1D texture coordinate (t); and 
a means for generating a 2D texture image using the
1D texture image.
7. A system in accordance with the claim 6,
wherein
the means for projecting the texture coordinate
(u,v) to a 1D texture coordinate (t) comprising:
a means for selecting two functions G1, and G2
among several fixed functions;
a means for defining a look up table representing
any real function,  hereafter called as F; and 
a means for combining the functions the G1, the
G2, and the F.
8.   A system in accordance
with the claim 6, wherein
the means for projecting the texture coordinate
(u,v) to a 1D texture coordinate (t) comprising:
a means for selecting two functions G1, and G2,
from the function G(u,v) equal to {u, v, u+v, u-v, u^2, v^2, sqrt(u2+v2),
u+v+sqrt(u2+v2), u+v-sqrt(u2+v2), min(u,v), max(u,v), constant}, where “sqrt” is the mathematical function square
root, and x^2 means x power 2 (x times x);
a means for defining a look up table representing
any real function, hereafter called as F;
a means for combining the functions the G1, the G2
and the F comprising:
a means for using the G1 as input of the look up
table F, thus calculating F (G1 (u,v)); and
a means for using the G2 to calculate the product
of the output of the look up table with the G2, resulting in the value F (G1
(u,v))* G2 (u,v);
the means for accessing a 1D texture image stored
in memory using the 1D texture coordinate F(G1(u,v))*G2(u,v).
To solve the problems of memory size and circuit
size requirement is attained by a  system for computing a 2D texture
coordinate in a computer system comprising: a means for obtaining a 2D texture
coordinate (u,v); a means for generating two 1D intervals of two random values
using the coordinate u and v; a means for combining the two 1D intervals of
random values to a 2D interval of four random values; a means for generating a
random value depending on the texture coordinate (u,v) and the 2D interval of
four values; and a means for combining the random value with the input texture
coordinates (u,v) resulting in (u’,v’), perturbed the 2D texture coordinate and so on. Selected Figure is
Figure 1.
2008033848.tif 000007
2008033848.tif 000008
2008033848.tif 000009
2008033848.tif 000010