(57)【要約】３Ｄ単位ベクトルを表すデータを圧縮・解凍する方法及び装置が提供される。Ｘ、Ｙ及びＺ成分は、ベクトルデータから導出され、多くの可能性のある八分円対からベクトルが存在する八分円が判断される。次いで、ベクトルが倍率によって拡大縮小され、圧縮データ値が、八分円対データ及び拡大縮小ベクトルデータから導出される。
2005533306.tif 000002
【特許請求の範囲】
【請求項１】
３Ｄ単位ベクトルを表すデータを圧縮する方法であって、
ａ）ベクトルからＸ、Ｙ及びＺ成分を求め、
ｂ）八分円対のどの八分円にベクトルが入っているかを求めて、八分円対データを導出し、
ｃ）前記ベクトルを倍率によって拡大縮小し、
ｄ）圧縮データ値を導出して、前記八分円対データ及び前記拡大縮小ベクトルデータから前記ベクトルを表わす、
ステップを含むことを特徴とする方法。
【請求項２】
前記ステップｂ）において、前記八分円対データを求めるために、前記Ｘ、Ｙ及びＺ成分の符号を用いることを特徴とする請求項１に記載の３Ｄ単位ベクトルを表すデータを圧縮する方法。
【請求項３】
前記拡大縮小ステップを、前記Ｘ及びＹ成分に適用することを特徴とする請求項１又は請求項２に記載の３Ｄ単位ベクトルを表すデータを圧縮する方法。
【請求項４】
前記圧縮データ値が、前記八分円対データと、前記Ｚ成分の符号と組み合わされた、前記拡大縮小されたＸ及びＹ成分とから導出されることを特徴とする請求項３に記載の３Ｄ単位ベクトルを表すデータを圧縮する方法。
【請求項５】
３Ｄ単位ベクトルを表すデータを圧縮する装置であって、
ａ）前記ベクトルからＸ、Ｙ及びＺ成分を求める手段と、
ｂ）複数の八分円対のどの八分円に前記ベクトルが入っているかを求めることによって八分円対データを導出する手段と、
ｃ）前記ベクトルデータ値を拡大縮小する手段と、
ｄ）圧縮データ値を導出して、前記八分円対データ及び前記拡大縮小ベクトルデータから前記ベクトルを表わす手段と、
を備えた装置。
【請求項６】
前記八分円対データを求めるために、前記Ｘ、Ｙ及びＺ成分の符号を用いることを特徴とする請求項５に記載の３Ｄ単位ベクトルを表すデータを圧縮する装置。
【請求項７】
前記拡大縮小手段が、前記倍率を前記Ｘ及びＹ成分に適用することを特徴とする請求項５又は請求項６に記載の３Ｄ単位ベクトルを表すデータを圧縮する装置。
【請求項８】
前記圧縮データ値が、前記八分円対データと、前記Ｚ成分の符号と組み合わされた、前記拡大縮小されたＸ及びＹ成分とから導出されることを特徴とする請求項５に記載の３Ｄ単位ベクトルを表すデータを圧縮する装置。
【請求項９】
３つのフィールドからなる圧縮データから３Ｄ単位ベクトルを表すデータを解凍する方法であって、
ａ）前記第１領域に格納されたデータから、４つの八分円対のうち１つを特定し、
ｂ）第２及び第３領域から第１及び第２データ値を抽出し、
ｃ）前記八分円対のどの八分円に前記ベクトルが入っているかを求め、
ｄ）前記八分円の選択に応じてＸ、Ｙ及びＺ成分を導出し、
ｅ）前記Ｘ、Ｙ及びＺ成分を正規化して単位ベクトルを導出する、
ステップからなる方法。
【請求項１０】
３つのフィールドの圧縮データから３Ｄ単位ベクトルを表すデータを解凍する装置であって、
ａ）前記第１領域に格納されたデータから、４つの八分円対のうち１つを特定する手段と、
ｂ）前記第２及び第３領域からそれぞれ第１及び第２データ値を抽出する手段と、
ｃ）前記特定された八分円対のどの八分円に前記ベクトルが入っているかを求める手段と、
ｄ）前記八分円の選択に応じてＸ、Ｙ及びＺ成分を導出する手段と、
ｅ）前記Ｘ、Ｙ及びＺ成分を正規化して単位ベクトルを導出する手段と、
を備えた装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データを圧縮し解凍するための方法及び装置に関する。本発明の実施形態は、コンピュータ・グラフィックス・システムにおいて、具体的には、３次元コンピュータ・グラフィックスの分野に有用な形式のコンピュータ・グラフィックス・システムにおいて特に有用であり、ピクセルごとの表面法線をテクスチャ内に格納するもののような、「バンプ・マッピング」アルゴリズムを使用することによって、詳細を他の滑らかな表面に適用するためのものである。
【背景技術】
【０００２】
バンプ・マッピングの概念は、Ｂｌｉｎｎによる「Ｓｉｍｕｌａｔｉｏｎ  ｏｆ  Ｗｒｉｎｋｌｅｄ  Ｓｕｒｆａｃｅｓ」（ＳＩＧＧＲＡＰＨ  １９７８年、ｐｐ２８６−２９２）において導入された。一般に、光線の入射方向と表面法線すなわち所定の点において表面に垂直なベクトルの関数を用いて行われる、計算された表面の陰影付けは、その表面の配向、同様に粗さに関する重要な手がかりを与えてくれる。ピクセルごとに計算された表面法線を変えることに起因する陰影付けの変化のために、Ｂｌｉｎｎのバンプ・マッピングは、他の場合には数学的に滑らかな表面に、粗い外見（隆起）を与える。この方法は、表面の補間されたピクセル毎の法線を修正するために、テクスチャ・マッピングを用いて摂動ベクトルを得る。
【０００３】
「Ｅｆｆｉｃｉｅｎｔ  Ｂｕｍｐ  Ｍａｐｐｉｎｇ  Ｈａｒｄｗａｒｅ」（ＳＩＧＧＲＡＰＨ、ｐｐ３０３−３０６、１９９７年及び米国特許第５，９４９，４２４号）において、Ｐｅｅｒｃｙ他は、「摂動」法線ベクトルをテクスチャ・データ内に直接格納した、より効果的な方法を考案した。これらの法線は、ローカル接線の座標系に関連して定められた。各光ベクトルは、ローカル接線の空間座標系に関連する座標で表されなければならない。
【０００４】
テクスチャのサイズ、及びテクスチャリング中に消費されるメモリ帯域幅は、コンピュータ・グラフィックスにおいて重要な要因であるので、欧州特許ＥＰ１００４０９４号は、表面法線のストレージ犠牲を３つの座標値（ＸＹＺ）から２つの値だけに減少させ、これによりストレージ空間及びテクスチャリング帯域幅の節約をもたらすプロセスを説明する。この方法は、表面法線が、ローカル表面座標空間内に定められた単位ベクトルであるという事実を利用するものである。図１ａに示されるように、単位法線は、主として、単一の半球内にあるように制限される。
【０００５】
ローカル接線空間系に代わる方法として、表面法線方向をオブジェクトのローカル座標空間内に定めることができる。このことは、オブジェクトの異なる領域についてのバンプ・テクスチャの一部を再利用することが難しいという欠点を有するが、補間された光ベクトルを計算するのがより手軽であり、頂点ごとのローカル接線座標系をモデル内に格納する必要性がないという利点を有する。例えば、ＷＯ９５２７２６８号における技術は、この手法で開始するが、次に、バンプマップ陰影付けを速くするためにベクトル量子化を用いる。
【０００６】
ローカル座標空間方法を用いる場合には、１つの半球にわたって全体的に広がるローカル接線空間系と違って、ここでは、表面法線方向が、単位半径の球の表面を横切って、任意に全ての方向に分散される（図１ｂを参照されたい）。ＥＰ１００４０９４号に記載される表面法線圧縮方法は、半球間で選択するために付加的なビットを用いることによって拡張することができるが、多くの可能なデータ・エンコード・パターンが無駄になるので、これは理想的なものでない。
【０００７】
バンプマップ・テクスチャにおける保存用ではないが、Ｄｅｅｒｉｎｇによる「Ｇｅｏｍｅｔｒｙ  Ｃｏｍｐｒｅｓｓｉｏｎ」、ＳＩＧＧＲＡＰＨ、ｐｐ１３−２０、１９９５年は、単位半径球のあらゆる八分円内の６つの領域を特定することによって、３次元単位ベクトルを１８ビットに圧縮する方法を説明する。残念なことに、１８ビットは、一般的に好ましいサイズが８又は１６ビットであるコンピュータ・テクスチャリング装置におけるテクスチャ・ストレージには不便なサイズである。例えば、１６ビットに適合されるように、この方法の精度の一部を低減させることも可能であるが、この方法は、多数のテスト及びかなり費用のかかる三角関数を必要とする。現代の３次元テクスチャリング・システムは、１秒あたり１０億のテクスチャリング動作のオーダーで計算できることが必要なので、これらの解凍動作が比較的手軽であることが重要である。
【発明の開示】
【０００８】
本発明の好ましい実施形態は、三次元単位ベクトルをテクスチャに格納するためと、コンピュータ３Ｄグラフィックスシステムのテクスチャリング・陰影付けエンジンにおける解凍の容易さとの両方のために最適化された形態の３Ｄ単位ベクトルを格納する方法及び装置を提供する。それらは、表面法線を表すローカル接線空間及びローカル座標空間方法の両方をサポートすることができる。最終的に、好ましい方法は、ＥＰ１００４０９４号に表わされた代表的ビットのより効果的な使用を実現する。
本発明は、添付の請求項においてより正確に定められ、それについて以下に説明する。
ここで、単なる例として、付属の図面を参照しながら、本発明の実施形態を詳細に説明する。
【発明を実施するための最良の形態】
【０００９】
本発明の１つの実施形態は、２つの主たる態様を有する。第１に、これは、コンピュータ・メモリ内の記憶に適した圧縮２進エンコード化フォーマットで、単位半径球上の点の組から選択された３次元ベクトルを表すことができる。第２に、これは、圧縮されたフォーマットを元の３次元単位ベクトルに変換することができる。本発明の実施形態を説明する最も明らかな方法は、とられることとなる手法である解凍プロセスを示すことである。
【００１０】
可能な単位ベクトルの球面（例えば、図１ｂ）が、正八面体（図１ｃ）に「縮小される」。これは、八分円に分けられ、次に該八分円は、対にされて４つの「八分円対」を形成する。好ましい実施形態において、これらの対は、「八分円対」内の全てのベクトルが、Ｘ成分について同じ符号を有し、同様にＹ成分について同じ符号を有するように選択される。Ｚ成分の符号は、対のどの八分円にベクトルがあるかを区別する。このように、エンコードされた値は、ベクトルがどの「八分円対」にあるかを特定し、該「八分円対」領域の内部のベクトルを見つけるために、２つの値Ｕ及びＶが用いられる。これらのＵ及びＶの値は、［０．．．１］の範囲の値のエンコードになると考えることができる。
図２に示されるように、好ましい実施形態において、各々の３次元単位ベクトルは、１６ビット値としてエンコードされる。各々の値は、３つのフィールド、すなわち２ビットの「八分円対特定子」１０、７ビットのＵパラメータ１１、及び７ビットのＶパラメータ１２からなる。Ｕ及びＶパラメータについての他のビット数の選択肢を選択することができる。
【００１１】
図３は、解凍装置の概要を示す。「八分円対特定子」１０が、デコード・ユニット２０に供給される。デコード・ユニット２０は、入力値を解釈して一対の数値符号フラグを生成し、この一対の数値符号フラグは、デコードされたベクトルのＸ及びＹ成分に適用される。「大きさ加算及び試験」ユニット２１が、Ｕ及びＶの値１１及び１２を加算し、その合計を１２７（「１．０」の論理値の値に等しく、７ビットのＵ及びＶ値の合計の可能な最大値の半分である）と比較する。デコード・ユニット２０は、合計の結果と、その結果に基づいた、該合計が１２７より上かどうかを示すフラグとの両方を出力する。次に、フラグを用いて、「八分円対」内のどの２つの八分円内にベクトルが位置しているかを求める。
【００１２】
割当てユニット２２は、ユニット２０から符号ビットの対を、そしてユニット２１から大きさの比較結果を取得し、それらを元のＵ及びＶの値１１及び１２と組み合わせて、ベクトル｛Ｘ’Ｙ’Ｚ’｝を生成する。このベクトルは、法線ベクトルと同じ方向であるが、単位長さではない。ユニット２３が、ベクトル｛Ｘ’Ｙ’Ｚ’｝の長さの逆数を計算し、これを拡大縮小ユニット２４に送る。次に、拡大縮小ユニットは、逆数を用いてベクトルを拡大縮小し、単位ベクトルの結果２５を生成する。
【００１３】
ここで、Ｃ言語のような疑似コード表記法を用いて、これらの種々のユニットの内部演算を説明する。
ユニット２０は、「八分円対」特定子１０すなわちＯＰＩに基づいて、２つの符号フラグすなわちＸｓｉｇｎ及びＹｓｉｇｎを生成する。これは、ハードウェアにおける自明な演算であり、次のコード：
2005533306.tif 000003
によって説明される。
Ｘｓｉｇｎ及びＹｓｉｇｎフラグを用いて、値Ｘ及びＹが正であるか負であるかを示す。
【００１４】
ユニット２１は、ＵとＶの合計と、単一のビット・フラグ、ＷＯとを生成して、どの八分円対の八分円にデータが属するかを特定する。これは以下のように表すことができる。
2005533306.tif 000004
当業者であれば、ハードウェアにおいて、好ましい実施形態における入力パラメータの範囲を［０．．１２７］と仮定すると、ｕ及びｖ値の合計の上位ビットを選択するための比較及び割当量は、［０．．２５４］の範囲にわたることを理解するであろう。
【００１５】
ユニット２２は、次のような、最初の非単位長さベクトルを生成する。
2005533306.tif 000005
好ましい実施形態において、Ｘ’及びＹ’の値は、符号＋絶対値フォーマット（２の補数ではない）を用いるので、否定し、その後に〔Ｘ´、Ｙ´、Ｚ´〕ベクトルの長さの二乗を計算するのがより手軽である。
【００１６】
ユニット２３は、最初のベクトル長の逆数を擬似浮動小数点２進数で計算する。ユニット２３は、成分の二乗を合計することによって、最初にベクトル長の二乗を計算する、すなわち、
ＬｅｎｇｔｈＳＱ＝Ｘ´*Ｘ´＋Ｙ´*Ｙ´＋Ｚ´*Ｚ´
である。
入力値の範囲及び行われた計算のために、二乗された長さの可能な範囲は制限されることが認識されるであろう。好ましい実施形態において、この範囲は、５３７７から１６１２９までを包含し、よって１４ビットで表すことができる。
【００１７】
次に、この二乗された長さの平方根の逆数が、当該技術分野において周知の何らかの方法を用いて、擬似浮動小数点形式で計算される。図４を参照すると、好ましい実施形態において、正規化シフタ５０を用いてこの計算を行って、最高で１０ビットが選択されることになる入力を、偶数ビットから左にシフトさせることができる。最も有効な「１」ビットは、２つの最も有効なビット位置のいずれかにあることに留意されたい。１０ビットの結果５１は、〔２５６，１０２３〕の範囲にある固定小数点の数を有効に表し、次に、これを用いて参照テーブル５２にアクセスする。この参照テーブルは、適切な２の累乗を乗算した５２への入力の平方根の逆数に対応する範囲（１０２３-0.5、１／１６）にある１１ビットの固定小数点の結果を戻す。
【００１８】
この結果は、２で除算された正規化シフト量と再結合され（５３）、付加的なシフトに追加され（５４）、それは、擬似浮動小数点の形態の、最初の平方和の逆数平方根を構成する。例示的な実施形態において、付加的なシフト値は、８である。この値は、結果の大きさ、参照テーブルから出力されることになる有効なビットの数、及び最終的な正規化ベクトルのために必要とされる精度のビット数が可能になるように選択される。
最終的に、ユニット２４は、擬似浮動小数点の値（すなわち、乗算の後に続くシフト及び切捨てに対応する）にＸ´、Ｙ´及びＺ´成分の各々を乗算して、７分数ビットを有する範囲〔−１、１〕の符号付８ビット固定小数点値を表す正規化された結果を得る。
【００１９】
説明のため、図５は、Ｕ及びＶに各々３ビットが割り当てられただけの例示的な実施形態に関する通常の位置の分布を示す。比較として、図６は、ほぼ等価な数のストレージ・ビットを用いる、欧州特許第１００４０９４号において既に説明された方法の適合バージョンについての点の分布を示す。見られるように、ストレージは均一でなく、密集してもいない。
【００２０】
図７は、Ｕ及びＶの値の対応するグリッドを有する球のたった１つの八分円対についての分布を示す。
解凍プロセスの反対、すなわち圧縮は、本質的に、逆に動作する説明されたプロセスである。このことは、図８に関連して説明される。（好ましくは）単位ベクトルＶ１００が解析され（１０１）、Ｘ、Ｙ、及びＺ成分の符号が抽出されて、単位ベクトルがどの八分円内にあるかが判断される。Ｘ及びＹ成分の符号を用いて、ＯＰＩエンコーディング１０２を構成する。ベクトルの倍率が計算され（１０３）、Ｖ１〔Ｚ〕＝１２７−Ｖ１〔Ｘ〕−Ｖ１〔Ｙ〕となる。倍率がＸ及びＹの値に適用される（１０４）。Ｚ成分の符号を仮定する。次に、Ｕ及びＶ成分が、拡大縮小されたＸ及びＹ値から計算される（１０５）。
【００２１】
解凍プロセスにおける丸め／切り捨て近似のために、「隣接する」エンコード化の一部を試すことによって、より「近い」合致を見出すことが可能である。この手続きは、以下の「Ｃ」コードによって説明される。
【００２２】
2005533306.tif 000006
【００２３】
2005533306.tif 000007
【００２４】
2005533306.tif 000008
【００２５】
「ＭｅａｓｕｒｅＡｎｇｌｅ」ルーチンは、以下のようにして角度を正確に計算するか、
2005533306.tif 000009
又は以下のようなより簡単な表記でより手軽に計算することができる。
2005533306.tif 000010
【００２６】
ＤＰ関数は、以下のようにして普通の内積を計算する。
2005533306.tif 000011
【００２７】
この技術は、単位ベクトルの減少されたコストストレージを要求するバンプマッピング以外の用途にも有用であることに注目されたい。Ｄｅｅｒｉｎｇによって説明されたような頂点幾何学の圧縮は、こうした用途の１つである。
【図面の簡単な説明】
【００２８】
【図１ａ】接線空間バンプ・マッピング法に必要とされる単位法線の範囲を示す。
【図１ｂ】ローカル座標空間法に要求される、より大きい範囲を示す。
【図１ｃ】正八面体に圧縮された範囲を示す。
【図２】本発明の実施形態における単位ベクトルの１６ビットエンコーディングへの好ましいビットの割当てを示す。
【図３】本発明を具体化する解凍方法及び装置を示す。
【図４】ベクトル長の逆数を計算する図３のステップの方法及び装置の詳細を示す。
【図５】２つの３ビット値を用いる本発明の実施形態において表すことができる可能な法線位置の分布を示す。
【図６】その分布が図５に示されている本発明の実施形態において用いられるのとほぼ等しい数のストレージビットを用いる公知のデータ圧縮・検索方法に関する可能な法線位置の分布を示す。
【図７】球の１つのみの八分円対に関する図５の分布と、３ビット値の対応するグリッドとを示す。
【図８】３Ｄベクトルを「等価な」パック形式に変換するための圧縮装置を示す。
【図１ａ】
2005533306.tif 000012
【図１ｂ】
2005533306.tif 000013
【図１ｃ】
2005533306.tif 000014
【図２】
2005533306.tif 000015
【図３】
2005533306.tif 000016
【図４】
2005533306.tif 000017
【図５】
2005533306.tif 000018
【図６】
2005533306.tif 000019
【図７】
2005533306.tif 000020
【図８】
2005533306.tif 000021
【国際調査報告】
2005533306.tif 000022
2005533306.tif 000023
2005533306.tif 000024