(57)【特許請求の範囲】
【請求項１】
制御ポイントに基づき数学関数を評価するためにコンピュータ、専用ハードウェア又は計算機により実行される方法であって、
数学関数を識別するステップと、
前記数学関数を評価するための値を受信するステップと、
前記値に対する数学オペレーションを行うことによって、前記数学関数を複数の区間にわたり定義させる各区間を識別するステップと、
前記値に基づき少なくとも１つの参照テーブルを決定し、各区間が１つの多項式関数によって近似される当該区間毎に１つの制御ポイントを前記参照テーブルから検索するステップであって、取り得る可能性のある組み合わせの中から前記数学関数に合致する特定の制御ポイントの組を前記値に基づき選択される当該ステップと、
前記参照テーブルからの制御ポイントを、他の参照テーブルからの制御ポイントと入れ替えることにより、前記区間を近似する多項式関数の係数を生成するステップと、
隣接区間の制御ポイントを用いて前記区間にわたる補間処理がなされ、前記区間全体が１つの近似関数であらわされるステップと、
前記数学関数に関する前記近似関数を前記値に対して評価するステップと、
を含むことを特徴とする方法。
【請求項２】
前記制御ポイントがＢスプライン制御ポイントであることを特徴とする請求項１に記載の方法。
【請求項３】
前記制御ポイントをメモリにおける複数の前記参照テーブル内に記憶するステップを含み、前記参照テーブルの数が、前記多項式関数の次数以上であり、その結果、各テーブルから１つの制御ポイントを検索することによって前記数学関数を評価するのに要する全部の数の制御ポイントを同時に検索することができる請求項１又は２に記載の方法。
【請求項４】
前記制御ポイントは、前記近似関数上に存在しない値である、請求項１に記載の方法。
【請求項５】
前記補間処理は、線形補間を用いて実行されることを特徴とする請求項１に記載の方法。
【請求項６】
Ｂスプライン制御ポイントからのＢスプライン表現を導き、且つde Casteljau評価手法の使用を可能にするために当該Ｂスプライン表現をベジエ表現にマッピングするステップを更に含むことを特徴とする請求項２に記載の方法。
【請求項７】
前記近似関数を評価する前に前記多項式関数から一次線形の項を除去するとともに、前記評価の後で前記一次線形項を再適用するステップを更に含むことを特徴とする請求項１〜６のいずれか１項に記載の方法。
【請求項８】
制御ポイントが検索される前記参照テーブル内の位置が参照インデックス値によって定義され、
複数の参照テーブルのそれぞれから１つの制御ポイントを検索するとき、当該検索された制御ポイントが前記インデックス値によって指定された位置で前記数学関数を評価するのに充分であるように前記参照インデックス値を操作し、
そして要求オーダーで評価ユニットに対して前記制御ポイントを提示するために、前記検索された制御ポイントの少なくとも１つの所定のビットを他の制御ポイントのビットと入れ替える、請求項１〜７のいずれか１項に記載の方法。
【請求項９】
制御ポイントに基づき数学関数を評価する装置であって、
数学関数を識別する手段と、
前記数学関数を評価するための値を受信する手段と、
前記値に対する数学オペレーションを行うことによって、前記数学関数を複数の区間にわたり定義させる各区間を識別する手段と、
前記値に基づき少なくとも１つの参照テーブルを決定し、各区間が１つの多項式関数によって近似される当該区間毎に１つの制御ポイントを前記参照テーブルから検索する手段であって、取り得る可能性のある組み合わせの中から前記数学関数に合致する特定の制御ポイントの組を前記値に基づき選択し、
前記参照テーブルからの制御ポイントを、他の参照テーブルからの制御ポイントと入れ替えることにより、前記区間を近似する多項式関数の係数を生成する手段、
隣接区間の制御ポイントを用いて前記区間にわたる補間処理がなされ、前記区間全体が１つの近似関数であらわされる手段と、 前記数学関数に関する前記近似関数を前記値に対して評価する手段と、
を備えたことを特徴とする装置。
【請求項１０】
前記制御ポイントがＢスプライン制御ポイントであることを特徴とする請求項９に記載の装置。
【請求項１１】
前記制御ポイントを記憶するメモリ内の参照テーブルの数が、評価される前記多項式関数の次数以上であり、その結果、各テーブルから１つの制御ポイントを検索することによって前記数学関数を評価するのに要する全部の数の制御ポイントを同時に検索することができる請求項９又は１０に記載の装置。
【請求項１２】
前記制御ポイントは、前記近似関数上に存在しない値である、請求項９に記載の装置。
【請求項１３】
前記補間処理は、前記線形補間を用いて実行されることを特徴とする請求項９に記載の装置。
【請求項１４】
Ｂスプライン制御ポイントからのＢスプライン表現を導き、且つde Casteljau評価手法の使用を可能にするために当該Ｂスプライン表現をベジエ表現にマッピングする手段を更に備えたことを特徴とする請求項１０に記載の装置。
【請求項１５】
前記近似関数を評価する前に前記多項式関数から一次線形の項を除去するとともに、前記評価の後で前記一次線形項を再適用する手段を更に備えたことを特徴とする請求項９〜１４のいずれか１項に記載の装置。
【請求項１６】
制御ポイントが読み出される前記参照テーブル内の位置が参照インデックス値によって定義され、
複数の参照テーブルのそれぞれから１つの制御ポイントを検索するとき、当該検索された制御ポイントが前記インデックス値によって指定された位置で前記数学関数を評価するのに充分であるように前記参照インデックス値を操作する手段と、
そして要求オーダーで評価ユニットに対して前記制御ポイントを提示するために、前記検索された制御ポイントの少なくとも１つの所定のビットを他の制御ポイントのビットと入れ替える手段と、を更に備えたことを特徴とする請求項９〜１５のいずれか１項に記載の装置。
【発明の詳細な説明】
【背景技術】
【０００１】
幾つかのＣＰＵの浮動小数点ユニット（装置）、特に最新グラフィックス・チップにおいては、浮動小数点数の数学関数を計算する必要がある。これらの関数は、典型的には連続関数であり、且つ「逆数」（即ちｆ（ｘ）＝１／ｘ）、「逆平方根」（即ちｆ（ｘ）＝１／√ｘ）、底２の対数（即ちｆ（ｘ）＝lnｘ／ln２）、底２のべき関数（即ち、ｆ（ｘ）＝２x）、サイン(sin)、コサイン(cos)などの関数を含み得る。例えば、Microsoft（Ｒ） Direct Ｘ グラフィック仕様の指令セットにおける数学関数形式の部分などは、様々なＣＰＵでの命令として様々な形式で表現されている。
【０００２】
実行を簡略化するために、これら関数の多くによって、動き(behaviour)のパターンを繰り返して利用することがある。例えば、コサインやサインは明らかである。しかし、この動きは、[２n,２n+1）のあらゆる間隔のそれぞれで繰り返す逆数とともに、且つ[２n,２n+2）の間隔上で繰り返す逆平方根とともにみられるものである。このような領域は、入力された浮動小数点の指数の簡単な整数オペレーションを通じて常に抽出できる。また、評価をする上での困難な点は、非常に減縮された(reduced)数値の範囲で関数を評価するような減縮を行うことである。一般性を失うことなく、そのようなreduce関数に対する入力値を、例えば[0,1]領域のｘ′の値（典型的には固定小数点）にマップできるものと仮定する。また、出力値は同様の形式であるものと仮定する。
【０００３】
当業者においては、このようなreduce関数を計算する幾つかの方法が知られている。最もシンプルなシステムは直接的なテーブル参照によるものである。入力精度としてＮビット、特に出力精度としてＭビットが与えられたとき、テーブルはＭビットそれぞれに対して２N個のエントリー含むだろう。その入力値は、テーブル内で最も近いエントリーにマップされ、そして結果が得られる。しかしながら、小さなテーブルを除くあらゆる場合で、これはコスト高であり且つ一般的には不正確なオプションである。
【０００４】
コスト高を軽減するために用いられる１つのアプローチは、テーブルのデータを圧縮することであり、そのようなスキーマは米国特許６３３００００において逆計算として用いられていた。しかしながら、このスキーマは汎用的に適用することが難しく、更に、圧縮レベルを大きくすることができない。
【０００５】
別のアプローチとしては、適度に正確な結果をもたらす小さな参照テーブルを用いて、ニュートン・ラプソンによる反復演算処理を適用し、数値の精度を改善していくことが挙げられる。このようなスキーマを使えば、精度は、ビットの数の点からみて、各反復演算で倍精度となるのが一般的であろう。Turkowskiは、逆平方根を計算するために「Graphics Gems V(ISBN 0-12-543455-3)」の中でそのような方法を記載している。２6個のエントリーの場合で言えば、参照テーブルは初期推定値Ｒ0を生じさせ、その後、評価を行う２つのニュートン・ラプソン反復演算ステップの使用によって改善される。
【０００６】
0005563193.tif 000002
同様に、テキサス・インスツルメントの「TMS320C3x User's Guide」は、｀逆数´及び｀逆平方根´の例を開示する。実際、それは、参照テーブルとともに効果的に実施し、非常に適した初期推定値で開始し、精度を改善する反復処理に単純に依存する。
【０００７】
ニュートン・ラプソンなどの反復改善処理を用いる手法で問題となることの一つは、結果に収束するために補足的な数学的演算（浮動小数点又は整数のいずれか）が要求されるということである。これは、乗算器又は加算器を備えたＣＰＵ内で繰り返しステップが実行されるときは問題とはならないが、専用ハードウェア装置内に特別の回路を含むようなときはコスト高になる。
【０００８】
また別のアプローチとしては、関数を評価するために、３又は４つ程度の項を用いて、関数を評価するべき級数を使用することである。このアプローチの場合、微分係数ｋの重みバージョンが定数として記憶され、且つその関数が、
0005563193.tif 000003
又は、少ない掛け算で同等に言えば、
0005563193.tif 000004
として評価される。
このような実行に関する明らかな候補としては、サイン(sin)、コサイン(cos)を含む。実際、Microsoft（Ｒ） Direct Ｘ仕様は、サイン(sin)、コサイン(cos)を用いた例を開示する。
【０００９】
単一関数を有するときの問題の一つは、膨大な数の項を持つことなしに、関数の完全なドメインにわたって精度を維持することが困難であるということである。これの単純な救済手段は、テーブルアプローチを再度使用すること、且つその関数に対して分割近似をすることである。本手法はこの分野では周知であり、幾つかの改善方法が示唆されている。例えば、Detrey and de Dinechin による”Table-based polynomials for fast hardware function evaluation”又はWalters and Schulteによる”Efficient Function Approximation Using Truncates Multipliers and Squarers”である。本手法においては、関数のドメインは、それぞれにテーブルエントリーを有する２N個のセクションに分割される。各エントリーｉは、必要なべき級数の定数（即ち、Ｃ0i,Ｃ1i,…Ｃki）を記憶し、それら定数はセクション内の曲線を記述する。実際問題として、近似関数は、一般的には１次（線形）、２次又は３次関数となろう。Ｎ＝３、即ちほんの８個のセクションを有する２次スキームの単純な例は、図１（Ａ）に図示されている。このケースの参照テーブルとして考えられるものを以下に示す。
【００１０】
0005563193.tif 000005
注：ハードウェア実行の場合、必要に応じて、Ｃ0i値がすべて０．５に調整され、本ビットが定数であることから評価のコストを減少させる。
【００１１】
これらの値に関する相対エラーをプロットしたのが図１（Ｂ）である。
【００１２】
入力関数値ｘ′（ｘ′∈[０,１））を与えたとき、要求されるテーブルエントリーは、
0005563193.tif 000006
を計算することによって特定される。ハードウェア又はソフトウェア条件において、これはｘ′の上位Ｎビットの固定小数点表示をとることを簡略化させる。α∈[０,１）でのパラメータ補間は、
0005563193.tif 000007
として計算される。これは、まさにｘ′値の残り、即ち、最小有効ビットを抽出することである。次に、関数は、以下で計算される（または、上述した別の方法である因数分解による）。
0005563193.tif 000008
本例はものすごい精度でないかもしれないが、後述する幾つかの組合わせを通じて改善され得るものである。
１．テーブルエントリーの数Ｎを増加する。
２．高次多項式を使用する。
３．記憶値の精度を上げる。
前記評価で用いられる乗算器及び加算器の実際の大きさは重要であり、且つ実行コストと精度のトレードオフを意味する。
【００１３】
本スキームの別の有利性は、ハードウェア解決の場合、幾つかの異なる関数が同じ多項式型の評価ハードウェアを共有することであろう。つまり、
0005563193.tif 000009
が再利用される。もちろん、それぞれ特定の関数がそれ自身の参照テーブルを必要とし、セットアップし、さらに装置を終了させることになる。
【００１４】
ここで、Ｎは、上述した単純な参照テーブルのために必要とされる値よりもはるかに小さい値であるが、ｋ２N個のデータ値の総数を要求する。他の懸念事項の一つとしては、セクションが区分されているので、関数全体が連続するように精度に対する注意が払われなければならない。即ち、１つのセクションにおける計算された最終点が、次のセクションの開始点に一致するように評価される。また、セグメントにわたる微分係数にはあまり大きな不連続性がないことが望ましい。
【００１５】
コンピュータ・グラフィックスの場合、滑らかな面及び曲線が、パラメトリックスプライン(spline)又はcubic CatmullRomを用いて頻繁にモデル化される。これらのシステムに対する良い紹介は、Watt and Watt[ISBNO-201-54412-1]による’Advanced Animation and Rendering Techniques' で見つけられる。スプラインシステムは「制御ポイント」を使用し、数次（典型的には３次）の区分多項式である曲線又は面のローカルパス(local path)をコントロールする。幾つかのスプラインは補間し、つまり曲線が実際には制御ポイントを通って通過するのであるが、汎用表示システムの中の２つであるベジエ及び（一様）Ｂスプライン曲線の場合は、曲線が制御ポイントの位置に従う傾向はあるものの、近似であって普通は制御ポイントを通ることがない。
【００１６】
図２において、一連の制御ポイント（符号１で示されるものの１つ）が複数の線で結ばれて示されている。次に、一様Ｂスプライン曲線の経路が符号２で定義されている。一様Ｂスプライン曲線の特に有利な点は、区分セクションにわたって曲線及びその微分係数の両方において連続性を確保することが明らかであるということにある。他方、このスプラインの評価は、ベジエの均等におけるde Casteljauアルゴリズムを用いて上手く実行され得ることである。（’Advanced Animation and Rendering Techniques' を参照のこと）。グラフィックスの場合、スプラインは２Ｄ又は３Ｄ曲線であるのが一般的ではあるが、１次元の範囲に減少することは可能である。
【００１７】
（本発明の概要）
多項式関数を参照テーブルに記憶することは、多項式の係数の点からみると大きなメモリ量を要することがわかった（これは、特に高次の多項式にあてはまる。）。要求されるメモリを減少するために、同じ多項式曲線が少ない記憶データで表現できるならそれは有益である。
【００１８】
本発明の好ましい実施形態は、曲線を定義するために制御ポイントを記憶し、そして計算ブロックを使ってその制御ポイントをオペレーションすることによって多項式の係数を生成して多項式曲線を記述し、記憶すべきデータ数を減少させる。本発明の実施形態は、多項式を定義する多項式係数を記憶するよりも、制御ポイントから多項式係数を生成することができる単一の制御ポイントを記憶できるという効果をもたらす。その結果、メモリ容量の削減がデバイスコストを減少させるので、コンピュータによる装置、グラフィックス・チップ、又は多項式関数を使用することが要求される専用ハードウェアは本発明の恩恵を受けることになる。
【００１９】
大きくみると、本発明は参照テーブルを用いて数学関数を評価するための方法及び装置に関し、前記テーブルに記憶される値が曲線の制御ポイントを表している。
本発明の好ましい実施形態は、重要な係数で多項式曲線を表すために参照テーブルに記憶する必要のあるデータ量を減らし、その結果、要求されるメモリサイズを減少させる。また、区分セクション間の境界を越えた連続性（微分係数を含む）を維持する。
【００２０】
好ましい実施形態は、関数を表すために２次又はおそらく３次のＢスプライン区分曲線を用い、３個（２次）又は４（３次）個までの係数によって参照テーブルのサイズを減少させることができる。それは、１番目、３番目及びもっと高次の微分係数（即ち、Ｃli…Ｃki）に関連した定数係数を記憶するための必要性を除去することによってこれを達成する。代わりに、単一の値である一様Ｂスプライン制御ポイントが、参照テーブルの「セクションごと」に記憶される。そして、隣接の制御ポイント値と協力して特定のセクションに区分曲線を定義することで足りる。本システムは曲線の端点を処理するために補助値Ｋを要求する。Ｋは近似の次数（即ち、２次の場合はＫ＝２を意味する）である。そして、本発明は２N＋Ｋ個の値を記憶することを要求することになるのだが、それはＫ２Nからすれば意味のある削減になっている。
【００２１】
定数項Ｃ0iが曲線上に存在するのが一般的な従来の解決手段とは異なり、本発明で記憶された値は一般には定数項Ｃ0iが曲線上に存在しない。
【００２２】
幾つかの隣接する制御ポイント値（即ち、２次表現では３個、３次表現では４個）が曲線セグメントを評価するために並行してアクセスされるので、このデータを効率的に取得する手段が要求される。本発明の場合、これは、１つの「２N＋Ｋエントリー」参照テーブルを幾つかの小さな参照テーブルで置き換えることによって実現される。２次近似の場合で言えば、これは２つの「２N-2個のエントリー」と２つの「２N-2＋１個のエントリー」テーブルで構成され、これにより各テーブルは４番目の値ごとに記憶する。３次近似で言えば、３つのテーブルは２N-2＋１個のエントリーをもつことになるだろう。
【発明を実施するための最良の形態】
【００２３】
本発明の好ましい実施形態は、添付の図面を参照することによって例示の方法で詳細に説明されるだろう。
本発明の好ましい実施形態は、汎用コンピュータ、専用ハードウェア、又は計算器で実行される。
好ましい実施形態において、逆数、逆平方根、底２の対数、及び底２のべき関数を含む基本的関数がサポートされる。この集合を拡張することが明らかであることは当業者であれば理解するだろう。本システムの概略構成を図３を参照しながら説明する。
【００２４】
好ましくは、評価のために要求された関数の識別（２１）とともに、浮動小数点値が入力される（２０）。次に、この値がオペレーションされ（２２）、関数が自己相似(self-similar)となる区間を抽出する。そして、これは、自己相似区間内の浮動小数点の位置を定義するために初期値ｘ′（２５）を与える。そして区間を符号化し識別する（２６）。これは、普通は、浮動小数点値の単純ビットオペレーション、及び／又は浮動小数点の指数に対する整数演算に関係する。「逆数」及び「逆平方根」の処理タイプの説明は、上述したとおりである。特に、逆数（簡略化のために零やぴったり２乗などの特殊ケースは無視）、浮動小数点数の８ビット指数及び符号ビットが区間を特定し、そして重要な仮数ビット（先頭の１を無視）がｘ′値を形成する。他の関数の要求は当業者であれば明らかであろう。
【００２５】
次に、ｘ′値が２つの要素に分けられる（２６）。つまり、自己相似の区間が幾つのセクションに分けられるかを定義する「インデックス」と、ｘ′値のための関連セクションとである。前記インデックスは参照テーブル内を参照するために用いられ、セクションのｘ′値の部分を表す、領域[０,１）の「アルファ」値が２次（又は３次）関数を評価するために用いられる。従来技術のところで述べたように、これは明らかなオペレーションである。この点に関しては、本発明と典型的な従来の解決手段とには相違はない。
【００２６】
ここでは、インデックス値は、４０ａ,４０ｂ,４０ｃ,４０ｄの４つの方法に調整され、それらは４つの参照テーブルのそれぞれに基づいてアクセスされる。そこで実行される計算は以下のとおりである。
40a:     IndexOut = floor((IndexIn + 3) / 4);
40b:     IndexOut = floor((IndexIn + 2) / 4);
40c:     IndexOut = floor((IndexIn + 1) / 4);
40d:     IndexOut = floor((IndexIn    ) / 4);
【００２７】
当業者であれば、「４で割る」及び「フロアー(floor)」のオペレーションは、単に明らかなビット選択オペレーションである。IndexOut値は、曲線に関する制御ポイントの参照テーブルにおける位置を表す。
【００２８】
好ましい実施形態において、幾つかの異なる数学関数が実行され、そして、テーブル０（４１ａ）,テーブル１（４１ｂ）,テーブル２（４１ｃ）,テーブル４（４１ｄ）のそれぞれが、実際に可能性としてありうる組合わせの参照テーブルを記憶する。各集合における特定のテーブルが関数選択値２１によって選択される。また、４０ａ,４０ｂ,４０ｃ,４０ｄによって生成されたインデックスが各テーブルに供給され、参照値が「回転」ユニット４２に出力される。
【００２９】
２次の実施形態の場合、テーブル０及びテーブル１は、関数ごとに２N-2＋１個のエントリー、及び他のペアでは２N-2個のエントリーを有する（３次の実施形態の場合、テーブル２は関数ごとに特別のエントリーも有するだろう。）。好ましい実施形態の場合、この関数で６４個のセクションのときＮは６となるだろうが、この値は代替実施形態で変化され得るだろう。
【００３０】
次に、制御ポイント値が「回転」ユニットによって操作され、セクション内で関数を表す多項式を記述する係数を生成する。「回転」ユニットは、少なくともペアの重要なビットをインデックスから取り出し、テーブルから供給された値を以下のように「回転」する。
【００３１】
In0 = Table0Result;
In1 = Table1Result;
In2 = Table2Result;
In3 = Table3Result;
//
// If No rotation required...
//
If (Bottom2IndexBits == ｀00´) THEN
OutA = In0;
OutB = In1;
OutC = In2;
OPTIONAL_OutD = In3;  //  Cubic only
//
// Else if rotate one place...
//
ElSEIF(Bottom2IndexBits == ｀01´) THEN
OutA = In1;
OutB = In2;
OutC = In3;
OPTIONAL_OutD = In0;  //  Cubic only
ElSEIF(Bottom2IndexBits == ｀10´) THEN
OutA = In2;
OutB = In3;
OutC = In0;
OPTIONAL_OutD = In1;  //  Cubic only
ELSE
OutA = In3;
OutB = In0;
OutC = In1;
OPTIONAL_OutD = In2;  //  Cubic only
ENDIF
【００３２】
乗算器を用いたハードウェアにおいてこの機能性が実現される。
２次の実施形態の場合、セクション内の関数を記述する多項式は２次多項式であり、ＡからＣが”Ｂスプライン評価”ユニット４３へ供給される。３次の実施形態の場合、さらにＤ値（４５）が生成され、供給される。
【００３３】
詳細については後述するが、Ｂスプライン評価ユニットは、３（又は４）個の供給値Ａ,Ｂ,Ｃ（且つ、オプションとしてＤ）、及びユニット２７で生成されるアルファ値を受け取ると、補間された結果を生成する。
【００３４】
Ｂスプライン評価”ユニット４３の出力はユニット５０に供給され、ユニット５０では区間値が操作され、そして結果５１を生み出す補間関数と組合わせられる。逆数の場合（再度、簡略化のために零やぴったり２乗などの特殊ケースは無視するが）、ＩＥＥＥ８ビットの指数出力は、“１２７ − Input_exponent − １”に設定され、Ｂスプラインユニットの出力が仮数を形成するために用いられる。
【００３５】
Ｂスプライン評価ユニット４３の２次の実施形態の詳細は、図４を参照することによってより詳しく説明されるだろう。本ユニットは、当業者では既知のde Casteljau評価とともに、Ｂスプライン表現からベジエ表現までの変換を組合わせる。数学的には、この組合わせは、以下のように要約される。
0005563193.tif 000010
【００３６】
好ましい実施形態において、これらは、入力Ａ及び入力Ｂを総和する’加算及び２による除算’ユニット（１００）で実現される。整数／固定小数点演算で行うので、実際、これはまさにビットの明白な’リネーミング(renaming)’であるので、２による除算は’無演算（no operation）’である。同様に、’引き算及び除算’ユニット（１０１）は、（Ｂ−Ａ）／２を計算する。ユニット（１０２）では、α値でこの結果を縮小・拡大する（αは[０,１）区間に属することを思い出して欲しい）。最後に、ユニット（１０３）で、ユニット（１０２）の結果をユニット（１００）の結果と加算して、中間値”Ｔ1”をつくる。この値がＡとＢの間に存在することに注意すべきである。
【００３７】
同様に、中間値“Ｔ2”が以下のようにしてつくられる。すなわち、ユニット（１０４）がＣからＢを差し引き、（且つその結果を半分にする）、そしてユニット（１０５）にその値を送信し、ユニット（１０５）はαで拡大・縮小する。次に、ユニット（１０６）において、この結果にＢを加算させる。
【００３８】
中間値“Ｔ1”及び“Ｔ2”は、同様の方法で線形補間される。すなわち、ユニット（１０７）は、“Ｔ1”及び“Ｔ2”の差を計算し、ユニット（１０８）でαによってその値を拡大・縮小する。最後に、この結果は、ユニット（１０９）で“Ｔ1”と加算され、結果を作り出す（１１０）。
【００３９】
本実施形態の記載では、各演算の正確な精度を記載していないが、評価されるにちがいない全ての関数の入力及び出力に関する要求精度に応じて設定することができる。本プロセスの記載の中には、簡単な説明で終わっているものもある。上述したde Casteljau評価の方法はとても数学的に安定したものであり、そのために本システムは式１又は式１ａで示した多項式形式よりも、エラーに対する許容度がより大きいといえる。この場合、結果は常に制御ポイントの凸包（convex hull）内にあるだろう。
【００４０】
第２の好ましい実施形態では、式１において、例えば単純な二次近似式が与えられる。すなわち、
0005563193.tif 000011
である。
上記式の項は、de Casteljauの実施形態で用いられる以下のものと同様である。
0005563193.tif 000012
【００４１】
このスキームの有利な点は、ハードウェアを介してより短い’クリティカル・パス(critical path)’が存在することが挙げられる。
別の実施形態において、乗算ユニットは切断乗数を使用し、システムのコストを減少するために平方する。
【００４２】
別の実施形態の場合、制御ポイント値を評価する前に、自明な１次線形の項を初期関数から除去する。次に、リニアー(linear)評価の後で、正しい結果を得るためにこの自明な１次関数が再適用される。線形関数が選択され、その結果、その線形関数はハードウェアに取るに足らないコストのみを加える（即ち、どんな乗数も要求しない）。これの有利なところは、意味あるマージンによって参照テーブルに記憶されるビット数を減少させることである。例えば、逆数用に選択された関数は、f(x)=1-x であり、“log”又はsin(x)用に選択された関数は、f(x)=x である。
【００４３】
制御ポイントを記憶するための初期値を定義する。
上述したように、従来技術とは異なり、参照テーブル内に記憶される２N＋Ｋ制御ポイント値は一般的にはその関数の曲線上には存在しない。これらの点にとって正しい値を定義できるようにすることは重要であることから、これらの値を計算する方法を概要説明する。
【００４４】
第１の方法は、最適な適合制御値を計算する手段として、特異値分解（Singular Value Decomposition:ＳＶＤ）の標準数値演算技術を用いる（例えば、”Numerical Recipes in C”. ISBN 0 521 43108 5を参照）。一実施例においてｘ′がＪビットであると仮定すると、関数は２H個の一様に展開された位置（Ｎ＜Ｈ≦Ｊ）で評価される。これらの２H個の値を含むベクトルが構成される。また、２H個の行と２N＋Ｋ個の列が構成され、各行が対応の位置で曲線を評価するために制御ポイントのそれぞれに適用されなければならない重み値をあらわす。２次の近似によって、行の最大３個の項目が非零値をもち、すべての重み値が零以上、且つ行が正確に一つの値に総計されるだろう。
【００４５】
次に、２N＋Ｋ個の制御ポイント値を作り出すために、ＳＶＤ技術を用いて行列を「擬似」逆数化し、そしてベクトルによって積算する。ＨがＪに近くなる程、最終関数の精度が高くなるが、ＳＶＤがＮ3オーダーのオーダーアルゴリズムであるので、Ｈは慎重に選択されるべきである。このやり方の有利な点の一つは、擬似逆数がＳＶＤによってひとたび計算されると、それは幾つかの関数に関する制御ポイントを計算するために用いられ得ることである。
【００４６】
第２の方法は、最新ウェブレット理論の’リフティング’技術を使用する（"Building Your Own Wavelets at Home" Sweldens and Schroderを参照）。このタイプのアルゴリズムは、Ｎ ｌｏｇＮのオーダーであり、非常に速くなる可能性を有するのであるが、ＳＶＤアプローチよりも僅かに精度は悪くなるかもしれない。実際、これは大したことないらしい。ＳＶＤ技術と同様に、２H（＋ 一方側での付加領域）個の組の関数のサンプルがとられる。２次システムの場合、これらは以下の手順を用いて２N＋２個に徐々に減少される。
【００４７】
最新のサンプル集合における各奇数の位置（２ｉ＋１）で、
Sample[2i+1] = (Sample[2i] + Sample[2i+2])/2 - Sample[2i+1];  を計算する。
最新のサンプル集合における各偶数の位置（２ｉ）で、
Sample[2i] = (Sample[2i-1] + Sample[2i+1])/4 + Sample[2i];  を計算する。
奇数のサンプル値を捨てる。
【００４８】
これは、要求された数のポイントが残るまで反復される。両極端の一方側で追加のサンプルポイントが要求されるか、またはサンプル値の範囲外のアクセスを止めるために上記式が調整されなければならないことに留意すべきである。
【００４９】
第３の方法は、非常に単純であり、その範囲のすべてのポイントのエラーを減少することを試みないが、２次近似のためのアクセス可能な結果を生み出している。それは、２次ベジエ曲線の中間点が１／４Ａ＋１／２Ｂ＋１／４Ｃによって与えられるという事実に基づいている。我々はＡ及びＣが曲線上に存在することを知っているので、それらの値を計算することができるし、その結果、制御ポイントＢについて解くこともできる。制御ポイントＢは、そのセグメントに関するＬＵＴに記憶される値である。
【００５０】
記憶値及び関数ユニットの精度の定義：
ハードウェア実施例において、記憶テーブルのデータのサイズ、及び乗算器及び加算器／減算器の幅はシステムのコストにとって重大である。これらの値は、要求された出力値の精度に関する最小コストを実現するために調整され得る。非常に単純な手順は、以下のようになる。
参照テーブルに記憶されるデータの幅は、多かれ少なかれ、出力値の要求精度によって直接、定義される。なぜなら、これらの値は大抵、出力結果として同じ大きさであり、それゆえ同じ精度にちがいない。
【００５１】
次に、これは加算器及び減算器１００,１０１,１０４の入力サイズを近似的に決定する。しかしながら、Ａ，Ｂ，Ｃ値の最大及び最小の差異を評価することによって幾つかの省略がなされる。減算器１０１,１０４、その後の乗算器１０２,１０５のサイズを減少するために上記Ａ，Ｂ，Ｃ値を使用することができる。これら乗算器のサイズはアルファの精度の選択に依存し、アルファは全関数の要求精度に依存する。しかしながら、乗算器の出力からＬＳＢの幾つかを廃棄することによって幾つかの省略を行うこともできる。次に、この処理は１０７,１０８,１０９で形成される最終の線形補間器のために反復される。あるいはまた、コストを縮小するために切断乗数を用いることができる。
【００５２】
初期推定値の精度が得られると、精度をテストするために全入力値の完全テストを実施することができる。もしもこのテストをパスすると、関数ユニットの様々な精度を小さくすることが可能となり、格安実装を見つけるためにその精度を再テストできる。
また、このスキームはコンピュータ・グラフィックスにおける’ガンマ収集’を実施するために用いられるだろう。
【００５３】
当業者であれば、本発明の実施形態が、すべての多項式係数を記憶することよりも多項式係数を生成することができる制御ポイントを記憶することによって、多項式関数を記憶するために要するメモリを小さくすることは明らかであろう。その結果、たった１つの制御ポイントが、多項式を定義する多数からなる係数（２次であれば３個、３次であれば４個など）よりも、区間の各セクションのために記憶される。制御ポイントは、多項式係数を生成するために操作される。１つの制御ポイントでの小さな変化が、曲線での複雑な変化を生み出すので付加的な利点がもたらされる。これとは対照的に、このような曲線での変化が、完全に異なる係数の組によってあらわされるだろう。
【００５４】
本発明は、多項式関数を用いることでデバイスにとってのメモリ要求を小さくすることに向けられている。入力関数を操作し、区間やインデックスやアルファ値を定義するステップは、多項式の評価と同様に既知のシステムにとっても共通である。つまり、システムの任意の展開を本発明の融通性を維持したメモリとともに組合わして行うことができる。
【図面の簡単な説明】
【００５５】
【図１】８個の区分セクションによって表され／近似される関数グラフを示す図である。
【図２】関連する制御ポイントの組で単純な一様Ｂスプライン曲線を示した図である。
【図３】区分２次（又は最適には３次）近似を用いて関数を評価する本発明の好ましい実施形態における概略図である。
【図４】Ｂスプライン評価装置を示す図である。
【図１】
0005563193.tif 000013
【図２】
0005563193.tif 000014
【図３】
0005563193.tif 000015
【図４】
0005563193.tif 000016