(57)【特許請求の範囲】
【請求項１】
可変長フィールドのデータ・ストリームの伸張方法であって、
該データ・ストリームは、前記フィールドの伸張を三次元オブジェクトの非圧縮表面特性へ導くオプ・コード・ビット及び／又はタグ・ビットを含み、
（ａ）前記データ・ストリーム内で、必ずしも直前には限られない先行の検出を有効とするデータを有する前記データ・ストリームから、フィールド型を検出し、
（ｂ）前記データ・ストリーム内で、必ずしも直前には限られない先行の検出を有効とするデータを有する前記データ・ストリームから、フィールド長、及び／又は、フィールド正規化を検出し、
（ｃ）段階（ａ）及び段階（ｂ）のうちの少なくとも一つから得られた情報を使用し、前記データ・ストリームからビット位置合わせされたフィールドを抽出し、
（ｄ）抽出された前記ビット位置合わせされたフィールドを、必要に応じて本来の数値スケールに再正規化し、
（ｅ）選択的に汎用三角形ストリップ・フォーマットデータであるような伸張された表面記述データを出力する、
ことを含む方法。
【請求項２】
請求項１に記載の方法において、
前記オプ・コード・ビットは、後続するフィールドの組の型に関する情報を表わし、前記情報は、（ｉ）頂点情報、（ｉｉ）位置情報、（ｉｉｉ）表面法線情報、（ｉｖ）カラー、（ｖ）テキスチャ・マップ座標、（ｖｉ）表面材料属性、（ｖｉｉ）手順情報、（ｖｉｉｉ）頂点コマンド、法線コマンド、カラーコマンドのうちの何れか以外のコマンドである手順情報、からなるグループから選択され、及び／又は、
前記タグ・ビットは、（ａ）前記タグ・ビットが（ｉ）フィールド長、（ｉｉ）正規化、（ｉｉｉ）上記フィールドは相対的か否か、（ｉｖ）上記フィールドは絶対的か否か、からなるグループから選択された、少なくとも一つのフィールド特性を暗黙的に記述していること、及び、（ｂ）前記タグ・ビットが可変長を有し、可能なフィールドコンテンツ情報および前記可変長についての情報を含み、前記可変長は前記フィールドコンテンツ情報から独立していること、からなるグループから選択された、少なくとも一つの特性を有することを特徴とする方法。
【請求項３】
請求項１又は２に記載の方法において、
段階（ｂ）で前記有効データが直ちに連続して進行しない場合、
（ｂ−１）現行の命令及び後続する命令を前記データ・ストリームから取り出し、
（ｂ−２）前記後続する命令の、最初の固定ビット列を取り出し、
（ｂ−３）その後、前記現行の命令に対する残りのビット列を取り出す、
ことを更に含む方法。
【請求項４】
請求項１乃至３の何れかに記載の方法において、
（ｆ−１）その出力が（ｉ）後続するデータ・フィールドの開始、（ｉｉ）前記データ・フィールドの長さ、（ｉｉｉ）現行のタグ・フィールド長、（ｉｖ）前記フィールドが相対的であるか否かの識別、（ｖ）前記フィールドが絶対的であるか否かの識別、及び、（ｖｉ）再正規化を容易にするための数値シフト・オフセット情報を含む該データ・フィールドに対する再正規化パラメータ、の少なくとも一つを識別するタグ・ルックアップ・テーブルに前記タグ・ビットを供給し、
（ｆ−２）前記タグ・ルックアップ・テーブル出力が、上記ビット位置合わせされたフィールドが相対的であることを示すならば、前記フィールドの正規化された値を前記フィールドの現行値に加え、
（ｆ−３）前記タグ・ルックアップ・テーブル出力が、上記ビット位置合わせされたフィールドが絶対的であることを示すならば、前記フィールドの前記正規化された値で前記フィールドの現行値を置換する
段階を更に含む方法。
【請求項５】
請求項３又は４に記載の方法において、
次に後続する命令が、前記ビット位置合わせされたフィールドが解釈されるべき方法を変更すること、又は、前記タグ・ルックアップ・テーブルのコンテンツを変更すること、又は、前記ビット位置合わせされたフィールドにおける非変更データを通過させること、であるならば、これらを実行し、
上記正規化されたビット位置合わせされたフィールドが法線情報を含むならば、タグ・フィールド・インデックスは、前記ルックアップ・テーブルを経て、前記法線の直線表現を得ることを特徴とする方法。
【請求項６】
請求項１乃至５の何れかに記載の方法において、
前記ビット位置合わせされたフィールドは、（ｉ）前記オブジェクトの前記表面上のｘ、ｙ、ｚ座標位置、（ｉｉ）前記オブジェクトに対する赤、緑、青のカラー情報、（ｉｉｉ）前記オブジェクトに対する赤、緑、青及びアルファのカラー情報、（ｉｖ）前記オブジェクトに対して連続する赤、緑、青のカラー情報の間の相違、及び（ｖ）前記オブジェクトに対して連続する赤、緑、青及びアルファのカラー情報の間の相違、からなるグループから選択された少なくとも一つの特性に関する情報を含む方法。
【請求項７】
請求項１乃至６の何れかに記載の方法において、
前記オブジェクトは、
（ｉ）前記オブジェクトの位置の特性が直線ｘ、ｙ、ｚ座標として表され、
（ｉｉ）前記オブジェクトのカラーの特性が少なくとも赤、緑、青、及びアルファ要素を含むように表され、前記カラーは、少なくとも、（ａ）放射カラー、（ｂ）環境カラー、（ｃ）散乱カラー、及び（ｄ）鏡面反射カラーからなるグループから選択され、
（ｉｉｉ）前記オブジェクトの法線の特性が直線Ｎｘ、Ｎｙ、及びＮｚベクトル係数によって表され、
（ｉｖ）前記オブジェクトの法線の特性は、法線テーブルインデックスによって表され、前記オブジェクトの表面特性は、（ａ）位置、（ｂ）法線、（ｃ）カラー、（ｄ）テキスチャ・マップ座標、及び（ｅ）材料表面属性、からなるグループから選択された少なくとも一つの特性を含む、
からなるグループから選択された少なくとも一つの特性を有する方法。
【請求項８】
請求項７に記載の方法において、
前記法線のそれぞれは、単一インデックスによって所定の正規化された法線のテーブルの中に表され、前記インデックスは、（ｉ）前記インデックスは、表されるべき法線の直線表現サイン・ビットからなるインデックス表現のビット列を含み、（ｉｉ）前記インデックスは、折り曲げられた法線が前記折り曲げられた面の既知の側面にあることを確実にするように少なくとも一つの折り曲げられた面ｘ＝ｙ、ｘ＝ｚ、ｙ＝ｚによって表されるべき法線の直線表現の絶対量の可能な折り曲げを指定している少なくとも一つのビットを含み、（ｉｉｉ）前記インデックスは、前記法線の経度情報及び緯度情報を表しているビット列を含み、（ｉｖ）前記インデックスは、オクタント情報のビット列、セクスタント情報のビット列、及び前記折り曲げられた法線の経度及び緯度についての情報の追加フィールドを含むよう規定され、（ｖ）前記インデックスは、前記法線の経度情報及び緯度情報を表しているビット列を含み、及び、オクタント情報のビット列、セクスタント情報のビット列、及び折り曲げられた法線の経度及び緯度についての情報の追加フィールドを更に含み、（ｖｉ）前記インデックスは、オクタント情報の３ビット、セクスタント情報の３ビット、及び前記折り曲げられた法線の経度及び緯度についての情報の２つの追加フィールドを含むよう規定され、（ｖｉｉ）前記インデックスは、前記法線の経度情報及び緯度情報を表しているビット列を含み、及び、オクタント情報の３ビット、セクスタント情報の３ビット、及び前記折り曲げられた法線の経度及び緯度についての情報の２つの追加フィールドを更に含む、ことからなるグループから選択された少なくとも一つの特性を有する方法。
【請求項９】
請求項１乃至８の何れかに記載の方法において、
伸張されるべき前記データ・ストリームは、データが汎用三角形メッシュを規定している線形フォーマットに変換された、頂点を有する複数の三角形を規定している三次元三角形データとして表された前記オブジェクトからもたらされ、前記個々の表面特性が量子化され、可変長圧縮が、連続する前記表面特性の間の相違に適用される方法。
【請求項１０】
請求項１乃至９の何れかに記載の方法において、
現行のビット位置合わせされたフィールドがメッシュ・バッファに配置されるべきであるならば、前記現行のビット位置合わせされたフィールドのコピーを前記メッシュ・バッファに配置し、
前記ビット位置合わせされたフィールドがメッシュ・バッファ参照を含むならば、前記ビット位置合わせされたフィールドに対する古い正規化された値にアクセスすることを更に含む方法。
【請求項１１】
オプ・コード・ビット及び／又はタグ・ビットを含み、その表面が表面特性を規定する三次元オブジェクトを表している圧縮データを含み、そのフィールドは可変長であるデータ・ストリームを伸張するための、中央処理装置（ＣＰＵ）及び該ＣＰＵに結合されたメモリを含むコンピュータ・システムで使用可能なシステムであって、
前記データ・ストリームを受け取り、前記データ・ストリーム内で、必ずしも直前には限られない先行フィールドから、フィールド型、フィールド長、及び／又は、フィールド正規化を含むフィールド情報であって、直ぐ後に続くフィールドのフィールド情報を検出するようプログラムされた検出器ユニットと、
前記検出器ユニットによって検出された少なくともいくつかのデータを受け取り、前記データ・ストリームからビット位置合わせされたフィールドを抽出するようプログラムされた抽出器ユニットと、
を備えたことを特徴とするシステム。
【請求項１２】
請求項１１に記載のシステムであって、
（ｉ）タグ・フィールド開始位置、（ｉｉ）現行のタグ・フィールド長、（ｉｉｉ）前記フィールドが相対的であるか否かの識別、（ｉｖ）前記フィールドが絶対的であるか否かの識別、及び（ｖ）数値シフト・オフセット情報、からなるグループから選択された少なくとも一断片の情報を提供する、前記データ・ストリームの少なくとも一部を前記検出器ユニットから受け取るために結合された、ルックアップ・テーブルを更に含み、
前記データ・ストリームに含まれたビット・ライン・フィールドは、個々のビット列に位置合わせされるシステム。
【請求項１３】
請求項１１又は１２に記載のシステムであって、
（ｉ）前記データ・ストリームに含まれた新しく入力するデータを調整する第１段階と、前記データ・ストリームに含まれる残りの古いデータに、前記新しく入力するデータを調整する第２段階とを含む多段バレル・シフタ・ユニット、（ｉｉ）前記データ・ストリームを受け取るために結合されたインターフェイス回路ユニット、（ｉｉｉ）前記インターフェイス回路の出力に結合され、前記データ・ストリームを伸張する三次元グラフィックス伸張器、（ｉｖ）伸張されたデータ・ストリームを受け取り、出力するために結合された、三次元グラフィックス描画ユニット、からなるグループから選択された少なくとも一つのユニットを更に含み、
前記多段バレル・シフタ・ユニット、前記インターフェイス回路ユニット、前記三次元グラフィックス伸張器、及び前記三次元グラフィックス描画ユニットの少なくとも二つは、一つの集積回路に組み込まれることを特徴とするシステム。
【請求項１４】
請求項１１乃至１３の何れかに記載のシステムにおいて、
前記オプ・コード・ビットは、後続するフィールドの組の型に関する情報を表わし、前記情報は、（ｉ）頂点情報、（ｉｉ）位置情報、（ｉｉｉ）表面法線情報、（ｉｖ）カラー、（ｖ）テキスチャ・マップ座標、（ｖｉ）表面材料属性、及び（ｖｉｉ）手順情報、（ｖｉｉｉ）頂点コマンド、法線コマンド、カラーコマンドのうちの何れか以外のコマンドである手順情報、からなるグループから選択され、及び／又は、
前記タグ・ビットは、（ａ）前記タグ・ビットが（ｉ）フィールド長、（ｉｉ）正規化、（ｉｉｉ）上記フィールドは相対的か否か、（ｉｖ）上記フィールドは絶対的か否か、からなるグループから選択された少なくとも一つのフィールド特性を暗黙的に記述していること、及び、（ｂ）前記タグ・ビットが可変長を有し、可能なフィールドコンテンツ情報および前記可変長についての情報を含み、前記可変長は前記フィールド内容情報から独立していること、からなるグループから選択された少なくとも一つの特性を有し、
少なくともいくつかの前記オプ・コード・ビット及び／又は前記タグ・ビットは、前記フィールドの伸張を三次元オブジェクトの非圧縮表面特性に導くことを特徴とするシステム。
【請求項１５】
請求項１１乃至１４の何れかに記載のシステムにおいて、
前記オブジェクトは、（ｉ）位置、（ｉｉ）法線、（ｉｉｉ）カラー、（ｉｖ）テキスチャ・マップ座標、及び（ｖ）前記オブジェクトの材料表面属性からなるグループから選択された少なくとも一つの特性を含んでいる前記表面特性を有し、及び／又は、
前記オブジェクトは、（ｉ）オブジェクトの位置の特性が直線ｘ、ｙ、ｚ座標として表され、（ｉｉ）前記オブジェクトのカラーの特性が少なくとも赤、緑、青、及びアルファ要素を含むように表され、前記カラーは、少なくとも、（ａ）放射カラー、（ｂ）環境カラー、（ｃ）散乱カラー、及び（ｄ）鏡面反射カラーからなるグループから選択され、（ｉｉｉ）前記オブジェクトの法線の特性が直線Ｎｘ、Ｎｙ、及びＮｚベクトル係数によって表され、（ｉｖ）前記オブジェクトの法線の特性は、前記法線のルックアップ・テーブルの中にインデックスによって表され、（ｖ）位置、（ｖｉ）法線、（ｖｉｉ）カラー、（ｖｉｉｉ）テキスチャ・マップ座標、及び（ｉｘ）材料表面属性からなるグループから選択された少なくとも一つの特性を含むシステム。
【請求項１６】
請求項１５に記載のシステムにおいて、
法線の前記ルックアップ・テーブルは、所定の正規化された法線を含み、前記法線のそれぞれは、所定の正規化された法線の前記ルックアップ・テーブルの中に単一インデックスによって表され、前記インデックスは、（ｉ）前記インデックスは、表されるべき法線の直線表現サイン・ビットからなるインデックス表現のビット列を含み、（ｉｉ）前記インデックスは、折り曲げられた法線が前記折り曲げられた面の既知の側面にあることを確実にするように少なくとも一つの折り曲げられた面ｘ＝ｙ、ｘ＝ｚ、ｙ＝ｚによって表されるべき法線の直線表現の絶対量の可能な折り曲げを指定している少なくとも一つのビットを含み、（ｉｉｉ）前記インデックスは、前記法線の経度情報及び緯度情報を表しているビット列を含み、（ｉｖ）前記インデックスは、オクタント情報のビット列、セクスタント情報のビット列、及び前記折り曲げられた法線の経度及び緯度についての情報の追加フィールドを含むよう規定され、（ｖ）前記インデックスは、前記法線の経度情報及び緯度情報を表しているビット列を含み、及び、オクタント情報のビット列、セクスタント情報のビット列、及び折り曲げられた法線の経度及び緯度についての情報の追加フィールドを更に含み、（ｖｉ）前記インデックスは、オクタント情報の３ビット、セクスタント情報の３ビット、及び前記折り曲げられた法線の経度及び緯度についての情報の２つの追加フィールドを含むよう規定され、（ｖｉｉ）前記インデックスは、前記法線の経度情報及び緯度情報を表しているビット列を含み、及び、オクタント情報の３ビット、セクスタント情報の３ビット、及び折り曲げられた法線の経度及び緯度についての情報の２つの追加フィールドを更に含む、ことからなるグループから選択された少なくとも一つの特性を有するシステム。
【請求項１７】
請求項１１乃至１６の何れかに記載のシステムにおいて、
伸張されるべき前記データ・ストリームは、データが汎用三角形メッシュを規定している線形フォーマットに変換された、頂点を有する複数の三角形を規定している三次元三角形データとして表された前記オブジェクトからもたらされ、前記個々の表面特性が量子化され、可変長圧縮が、連続する前記表面特性の間の相違に適用されるシステム。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、一般にグラフィックス・データを圧縮解除することに関し、特に圧縮された三次元幾何学データを圧縮解除する方法及び装置に関する。
【０００２】
【従来の技術】
最新の三次元コンピュータ・グラフィックスは、種々のグラフィック表現技術を用いて、三次元オブジェクトを記述するために幾何学形状を広範囲に渡って用いる。コンピュータ・グラフィックスは、コンピュータ支援設計（“ＣＡＤ”）プログラムから仮想現実感（バーチャル・リアリティ）ビデオ・ゲームの範囲にわたるアプリケーションにおいて広い使用を見出す。オブジェクトの複雑で滑らかな表面は、トリム型非均等有理スプライン(trimmed non-uniform rational splines)のような高レベル抽象化によって簡潔的に表わすことができ、かつしばしば詳細な表面幾何学形状は、テクスチャ・マップを用いて表現できる。しかし、より現実感を付加することは、、通常、三角形の、生幾何学形状(raw geometry)を要求する。位置、カラー（色彩）、及びこれら三角形の通常の構成要素は、浮動小数点数として一般に表現され、かつ孤立した三角形(isolated triangle) を記述することは、記憶空間の１００バイト以上を要求することができる。
理解できるように、例えば、コンピュータ・ハード・ディスクまたはコンパクト・ディスク・リード・オンリ・メモリ（“ＣＤ−ＲＯＭ”）上に記憶されるために三次元コンピュータ・グラフィックス・オブジェクトに対して実質的な空間が必要である。同様に、例えば、ネットワーク、またはディスクから主メモリにわたり、伝送されるためにそのようなオブジェクトに対してかなりの時間が必要である。
【０００３】
幾何学形状圧縮は、一般的な空間−時間トレード・オフであり、かつメモリ／相互接続階層の全てのレベルで利点を供給する。同様なシステム問題が二次元画素イメージの記憶及び送信に対して存在する。種々の損失が大きくかつ無損失圧縮及び圧縮解除技術が、記憶空間及び送信時間における合成減少を有して、二次元画素イメージに対して開発されている。残念ながら、従来技術は、多角形（多辺形）低減技法を越えた、三次元幾何学形状に適切な圧縮／圧縮解除技術を含まない。しかしながら、１９９４年のプリンストン大学におけるション・ダンスキン(John Danskin)による「Ｘグラフィックス・プロトコルの圧縮」(Compressing the X Graphics Protocol) という題名の博士論文(Ph.D. thesis)は、二次元幾何学形状に対する圧縮を記載している。
適切な圧縮は、コンピュータ・システムの高速主メモリに、キャッシュ（格納）、または記憶することができる幾何学形状の量をかなり増大することができる。分散型ネットワーク・アプリケーションでは、圧縮は、送信時間をかなり低減することによって、共有バーチャル・リアリティ（“ＶＲ”）・ディスプレイ環境をインプリメント可能にすることを支援できる。
ほとんどの主要な機械計算機援用設計（“ＭＣＡＤ”）ソフトウェア・パッケージ、及び多くの動画モデリング・パッケージは、幾何学形状を構成しかつ表現するために構成ソリッド幾何学形状（“ＣＳＧ”）及び自由な形式のＮＵＲＢＳを用いる。そのような技法を用いて、滑らかな表面の領域は、トリム型ポリノミアル表面を結果として得られる高いレベルに表現される。ハードウェア・レンダリングに対して、これらの表面は、一般に、レンダリング・ハードウェアへの送信の前にソフトウェアを用いて三角形にプリテッセレートされる(pre-tessellated) 。そのようなソフトウェア・プリテッセレーション(pre-tesselation) は、ハードウェアＮＵＲＢＳ(non-uniform rational B-spline) レンダリングのある形式を支持するハードウェア上でも行われる。
しかしながら、ＮＵＲＢＳ幾何学形状表現に関連付けられる多くの利点は、実時間レンダリング以外のタスクに対してである。これらの非レンダリング・タスクは、マシニング、インターチェンジ、及び乱流のシミュレーションのような物理的解析に対する表現を含む。ＮＵＲＢＳに対してトリミング曲線を正確に表現することは、非常にデータを集中し、かつ圧縮技術として、トリム型ＮＵＲＢＳは、少なくとも一般的なレンダリング・テッセレーション密度ではプリテッセレートされた三角形よりも更にコンパクトでありえない。そして、全てのオブジェクトがＮＵＲＢＳによってコンパクトに表現されない（一部のオブジェクトがＮＵＲＢＳによってコンパクトに表現される）。自動車フードやジェット・タービン・ブレードのような多くの機械的オブジェクトは、ＮＵＲＢＳ表現が有利でありうる大きな、滑らかな領域を有するけれども、多くのオブジェクトは、そのような領域をもっておらずかつそのような表現に向いていない。それゆえに、ＮＵＲＢＳがオブジェクトをモデル化することにおいて多くのアプリケーションを有すると同時に、圧縮された三角形は、アプリケーション・オブジェクトの多くのクラスに対して遙にコンパクトである。
【０００４】
フォト・リアリスティック・バッチ・レンダリングは、微細な幾何学形状の詳細をコンパクトに表わすためにテキスチャ・マップ技術の広範囲な使用を長くした。そのような技術は、カラー・テキスチャ・マップ、通常のバンプ・マップ、及び変位マップを含むことができる。テキスチャ・マッピングは、例えば、空の雲、遠くの建物のような、遠背景における大きなオブジェクトに対してよく機能する。より近い距離では、テキスチャは、例えば、広告掲示板、ペインティング、カーペット、大理石製の壁、等のような、ほとんどフラットである三次元オブジェクトに対して最もよく機能する。最近、レンダリング・ハードウェアは、テキスチャ・マッピングを支持することを始めたし、かつ実時間レンダリング・エンジンもこれらの技術を適用することができる。
しかしながら、テキスチャ・マッピングは、フラットでない隣接するオブジェクトに対して品質の著しい損失を結果として生ずる。一つの部分的な解は、テキスチャされた多角形がオブザーバに面すべく常に旋回する“サインボード”である。しかし、ステレオ、特にヘッド・トラック型ＶＲステレオを考慮したときに、隣接するテキスチャは、フラットとして明らかに感知される。これらの例では、隣接するオブジェクトのあまり詳細ではないが完全な三次元多角形表現は、より現実的であろう。
【０００５】
幾何学形状の多面体表現は、三次元ラスター・コンピュータ・グラフィックの分野で長く支持されている。そのような表現では、任意の幾何学形状は、頂点(vertices)、エッジ(edges) 、及び面(faces) の一覧表によって一般に表現されかつ指定される。Computer Graphics: Principles and Practice, 2nd ed., Addison-Wesley, 1990 においてJ. Foly, et al. によって指摘されたように、ウィングドエッジ・データ構造(winged-edge data structures) のような表現は、ディスプレイされるだけの幾何学形状の編集を支持すべく設計された。    これら表現の痕跡（なごり）は、交換フォーマット、例えばWavefront OBJ として今日生き残っている。理論的にコンパクトであるが、あるコンパクションは、交換ファイルにおけるＡＳＣＩＩ（アスキー）データ表現を用いることにより判読性の犠牲になる。不幸にも、これらのフォーマットのほとんど（もしあれば）は、レンダリング・ハードウェアに描画命令(drawing instructions)として直接渡すことができない。
そのようなフォーマットの別の歴史的痕跡は、早期レンダリング・ハードウェアが受け入れうる一般のプリミティブ・フォーム(general primitive form)の、Ｎ−面多角形の支持体である。しかしながら、今日の高速レンダリング・ハードウェアは、ハードウェアに提出される前に全ての多角形幾何学形状が三角形に低減されることを要求する。三面以上を有する多角形は、プレーナー（平面）またはコンベックス（凸面）のいずれかであることを一般に保証することができない。四辺形がレンダリング・プリミティブとして受容されるならば、レンダリングの前にそれらが一対の三角形に任意に分割されるということが受容されるべきである。
【０００６】
近代グラフィックス言語は、通常、頂点データ構造のアレーとして、三次元三角形の収集の表現のために２値フォーマットを一般に指定する。それゆえに、ＰＨＩＧＳ  ＰＬＵＳ、ＰＥＸ、ＸＧＬ、及びＯｐｅｎＧＬへの提案された拡張は、このフォーマット・フォームであり、かつ実行可能幾何学形状によって取られる記憶空間を画定する。
“ジグザグ”または“スター”ストリップスに三角形を分離または連鎖することは、この分野で知られている。例えば、Ｉｒｉｓ−ＧＬ、ＸＧＬ、及びＰＥＸ５．２は、ジグザグからに、頂点毎に基づき連鎖している星状の頂点へ切り替えることができる汎用の三角形ストリップのフォームを画定するが、ＸＧＬ及びＰＥＸの頂点当たりの余分なヘッダ・ワードを犠牲にする。再開始コードは、三角形の多重切断ストリップスを頂点の１アレー内で指定させる。
これらの言語では、全ての頂点コンポーネント（位置、カラー、ノーマルズ(normals) ）は、３２ビット単精度ＩＥＥＥ浮動小数点数、または６４ビット倍精度数によって指定されうる。また、ＸＧＬ、ＩｒｉｓＧＬ、及びＯｐｅｎＧＬフォーマットは、３２ビット整数サポートも供給する。ＩｒｉｓＧＬ及びＯｐｅｎＧＬフォーマットは、１６ビット整数として頂点位置コンポーネント入力をサポートし、ノーマルズ及びカラーは、これらのいずれか並びに８ビット・コンポーネントであることができる。実際には、位置、カラー、及びノーマルズは、視覚的品質における損失がほとんどなく３２ビット（単精度ＩＥＥＥ浮動小数点）よりかなり少なく量子化される。そのようなビット節約は、適切な数値解析サポートが存在するということを前提として、市販の三次元グラフィックス・ハードウェアに用いられうる。
しかしながら、圧縮された、三次元幾何学形状データを含んでいる、幾何学形状データは、有用であるべく圧縮解除されなければならない。例えば、１９９５年８月４日に出願した、発明の名称が「三次元グラフィックス・データの幾何学形状圧縮のための方法及び装置」である本発明の出願人の特許出願がそのような圧縮を開示している。
【０００７】
【発明が解決しようとする課題】
それゆえに、圧縮された三次元幾何学形状を圧縮解除する方法及び装置の必要性が存在する。圧縮解除は、出力データが描画命令として直接レンダリング・ハードウェアにわたされうるようなものが好ましい。そして、三次元幾何学形状の圧縮解除は、ハードウェア、ソフトウェア、またはそれらの組合せを用いて実現可能であるべきである。本発明は、そのような圧縮解除を開示する。
本発明の目的は、上記従来の技術における問題点に鑑み、出力データが描画命令として直接レンダリング・ハードウェアにわたされるように圧縮された三次元幾何学形状を圧縮解除する方法及び装置を提供することである。
【０００８】
【課題を解決するための手段】
本発明の上記目的は、可変長フィールドのデータ・ストリームを圧縮解除する方法であり、該データ・ストリームが該フィールドの圧縮解除を三次元オブジェクトの非圧縮表面特性にガイドする、オプ・コード・ビット及び／又はタグ・ビットを含んでいる、方法であって、（ａ）フィールド型をデータ・ストリームから検出し、そのような検出をイネーブルするデータは、先行するが該データ・ストリーム内でシーケンシャルにすぐに先行する必要はない、（ｂ）フィールド長及び／又はフィールド正規化をデータ・ストリームから検出し、そのような検出をイネーブルするデータは、先行するが該データ・ストリーム内でシーケンシャルにすぐに先行する必要はない、（ｃ）段階（ａ）及び段階（ｂ）の少なくとも一つから得られた情報を用いて、データ・ストリームからビット位置合わせされたフィールドを抽出し、（ｄ）最初の数値スケールに抽出したビット位置合わせされたフィールドを必要に応じて再正規化し、（ｅ）圧縮解除された表面記述データを出力する段階を具備し、データは、オプションで汎用三角形ストリップ・フォーマットである方法によって達成される。
本発明の方法では、オプ・コードは、後続するフィールドのセットの型に関する情報を表わし、該情報は、（ｉ）頂点情報、（ｉｉ）位置情報、（ｉｉｉ）表面ノーマル情報、（ｉｖ）カラー、（ｖ）テキスチャ・マップ座標、（ｖｉ）表面材料特性、及び（ｖｉｉ）手順情報、（ｖｉｉｉ）頂点情報、ノーマル指令及びカラー指令以外の指令である手順情報からなるグループから選択され、及び／又は、タグ・ビットは、（ａ）該タグ・ビットが（ｉ）フィールド長、（ｉｉ）正規化、（ｉｉｉ）そのようなフィールドが相対的か否か、（ｉｖ）そのようなフィールドが絶対的か否か、からなるグループから選択された少なくとも一つのフィールド特性を暗黙的に記述する、及び（ｂ）該タグ・ビットが可変長を有しかつ当該可変長についての情報並びに可能フィールド内容情報を含み、該可変長は、該フィールド内容情報から独立である、からなるグループから選択された少なくとも一つの特性を有するように構成してもよい。
【０００９】
本発明の方法では、段階（ｂ）でイネーブリング・データがすぐにシーケンシャルに始めないならば、方法は、（ｂ−１）現行命令及び後続命令をデータ・ストリームからフェッチし、（ｂ−２）後続命令の固定数の最初のビットをフェッチし、かつ（ｂ−３）次いで、現行命令に対して残りのビットをフェッチすることを更に含むように構成してもよい。
本発明の方法では、（ｆ−１）その出力が（ｉ）後続データ・フィールドの開始、（ｉｉ）該データ・フィールドの長さ、（ｉｉｉ）実際のタグ・フィールド長、（ｉｖ）該フィールドが相対的であるか否かの識別、（ｖ）該フィールドが絶対的であるか否かの識別、及び（ｖｉ）再正規化を容易にするための数値シフティング・オフセット情報を含んでいる該データ・フィールドに対する再正規化パラメータ、の少なくとも一つを識別するタグ・ルックアップ表にタグ・ビットを供給し、（ｆ−２）タグ・ルックアップ表出力がそのようなビット位置合わせされたフィールドが相対的であることを示すならば、フィールドの正規化された値をフィールドの現行値に加え、（ｆ−３）タグ・ルックアップ表出力がそのようなビット位置合わせされたフィールドが絶対的であることを示すならば、該フィールドの該正規化された値で該フィールドの現行値を置換する段階を更に具備するように構成してもよい。
【００１０】
本発明の方法では、次の後続命令がビット位置合わせされたフィールドが解釈されるべき方法を変更することかまたはタグ表の内容を変更することまたは該ビット位置合わせされたフィールドの非変更データを通過することであるならば、そのようにし、かつ、そのような正規化ビット位置合わせされたフィールドがノーマル情報を含むならば、タグ・フィールド・インデックスは、該ノーマルの直線表現を得るためにルックアップ表を通過するように構成してもよい。
本発明の方法では、ビット位置合わせされたフィールドは、（ｉ）オブジェクトの表面上のｘ、ｙ、ｚ座標位置、（ｉｉ）オブジェクトに対する赤、緑、青のカラー情報、（ｉｉｉ）オブジェクトに対する赤、緑、青及びアルファのカラー情報、（ｉｖ）オブジェクトに対するシーケンシャル赤、緑、青のカラー情報間の相違、及び（ｖ）オブジェクトに対するシーケンシャル赤、緑、青及びアルファのカラー情報間の相違からなるグループから選択された少なくとも一つの特性に関する情報を含むように構成してもよい。
【００１１】
本発明の方法では、オブジェクトは、（ｉ）オブジェクトの位置の特性が直線ｘ、ｙ、ｚ座標として表され、（ｉｉ）オブジェクトのカラーの特性が少なくとも赤、緑、青、及びアルファ・コンポーネントを有しているように表され、該カラーが（ａ）放射カラー、（ｂ）環境カラー、（ｃ）散乱カラー、及び（ｄ）鏡面カラーからなるグループからなる選択された少なくとも一つのカラーを含み、（ｉｉｉ）オブジェクトのノーマルの特性が直線Ｎｘ、Ｎｙ、及びＮｚベクトル係数によって表され、（ｉｖ）オブジェクトのノーマルの特性は、ノーマル表インデックスによって表されることからなるグループから選択された少なくとも一つの特性を有し、オブジェクトの表面特性は、（ａ）位置、（ｂ）ノーマル、（ｃ）カラー、（ｄ）テキスチャ・マップ座標、及び（ｅ）オブジェクトの材料表面特性からなるグループから選択された少なくとも一つの特性を含むように構成してもよい。
【００１２】
本発明の方法では、ノーマルのそれぞれは、単一インデックスによって所定の正規化されたノーマルの表の中に表され、かつインデックスは、（ｉ）インデックスは、表されるべきノーマルの直線表現サイン・ビットを備えているインデックス表現のビットを含み、（ｉｉ）インデックスは、フォールドされたノーマルが該フォールディング平面の既知の側面にあることを確実にするように少なくとも一つのフォールディング平面ｘ＝ｙ、ｘ＝ｚ、ｙ＝ｚによって表されるべきノーマルの直線表現の絶対量の可能なフォールディングを指定している少なくとも一つのビットを含み、（ｉｉｉ）インデックスは、ノーマルの経度情報及び緯度情報を表しているビットを含み、（ｉｖ）インデックスは、オクタント情報のビット、セクスタント情報のビット、及びフォールドされたノーマルの経度及び緯度についての情報の追加フィールドを含むべく画定され、（ｖ）インデックスは、ノーマルの経度情報及び緯度情報を表しているビットを含み、及びオクタント情報のビット、セクスタント情報のビット、及びフォールドされたノーマルの経度及び緯度についての情報の追加フィールドを更に含み、（ｖｉ）インデックスは、オクタント情報の３ビット、セクスタント情報の３ビット、及びフォールドされたノーマルの経度及び緯度についての情報の２つの追加フィールドを含むべく画定され、（ｖｉｉ）インデックスは、ノーマルの経度情報及び緯度情報を表しているビットを含み、及びオクタント情報の３ビット、セクスタント情報の３ビット、及びフォールドされたノーマルの経度及び緯度についての情報の２つの追加フィールドを更に含む、ことからなるグループから選択された少なくとも一つの特性を有するように構成してもよい。
本発明の方法では、圧縮解除されるべきデータ・ストリームは、データが汎用三角形メッシュを画定している線形フォーマットに変換された、頂点を有している複数の三角形を画定している三次元三角形データとして表されたオブジェクトからもたらされ、表面特性の個々のものが量子化され、可変長圧縮が表面特性のシーケンシャルなものの間の相違に適用されるように構成してもよい。
本発明の方法では、現行ビット位置合わせされたフィールドがメッシュ・バッファに配置されるべきであるならば、該現行ビット位置合わせされたフィールドのコピーをメッシュ・バッファに配置し、かつビット位置合わせされたフィールドがメッシュ・バッファ基準を含むならば、ビット位置合わせされたフィールドに対する古い正規化された値をアクセスする段階を更に含むように構成してもよい。
【００１３】
また、本発明の上記目的は、オプ・コード・ビット及び／又はタグ・ビットを含み、その表面が表面特性を画定する三次元オブジェクトを表している圧縮データを含み、そのフィールドが長さにおいて変化することができる、データ・ストリームを圧縮解除する、中央処理装置（ＣＰＵ）及び当該ＣＰＵに結合されたメモリを含んでいるコンピュータ・システムに使用可能な、システムであって、データ・ストリームを受け取りかつすぐ後に続くフィールドのデータ・ストリーム・フィールド情報における先行しているが、すぐにシーケンシャルに先行していることを必要としない、フィールドから検出すべくプログラムされた検出器装置と、フィールド情報は、フィールド型及びフィールド長及び／又はフィールド正規化を含んでおり、検出器装置によって検出された少なくともあるデータを受け取りかつデータ・ストリームからビット位置合わせされたフィールドを抽出すべくプログラムされた抽出器装置とを備えているシステムによって達成される。
【００１４】
本発明のシステムでは、（ｉ）タグ・フィールド開始位置、（ｉｉ）実際のタグ・フィールド長、（ｉｉｉ）フィールドが相対的であるか否かの識別、（ｉｖ）フィールドが絶対的であるか否かの識別、及び（ｖ）数値シフティング・オフセット情報からなるグループから選択された少なくとも一部分の情報を供給する、データ・ストリームの少なくとも一部を検出器装置から受け取るべく結合された、ルックアップ表を更に含み、データ・ストリームに含まれたビット・ライン・フィールドは、個々のビットに位置合わせされるように構成してもよい。
本発明のシステムでは、（ｉ）データ・ストリームに含まれた新しく入力するデータを調整する第１段階と、新しく入力するデータにデータ・ストリームに含まれる残っている古いデータを調整する第２段階とを含む多段バレル・シフタ装置、（ｉｉ）データ・ストリームを受け取るべく結合されたインターフェイス回路装置、（ｉｉｉ）インターフェイス回路の出力に結合されかつデータ・ストリームを圧縮解除する三次元グラフィックス・デコンプレッサ、（ｉｖ）圧縮解除されたデータ・ストリームを受け取りかつ出力すべく結合された、三次元グラフィックス・レンダリング装置からなるグループから選択された少なくとも一つの装置を更に含み、多段バレル・シフタ装置、インターフェイス回路装置、三次元グラフィックス・デコンプレッサ、及び三次元グラフィックス・レンダリング装置の少なくとも二つは、一つの集積回路に組み込まれるように構成してもよい。
【００１５】
本発明のシステムでは、オプ・コードは、後続するフィールドのセットの型に関する情報を表わし、該情報は、（ｉ）頂点情報、（ｉｉ）位置情報、（ｉｉｉ）表面ノーマル情報、（ｉｖ）カラー、（ｖ）テキスチャ・マップ座標、（ｖｉ）表面材料特性、及び（ｖｉｉ）手順情報、（ｖｉｉｉ）頂点情報、ノーマル指令及びカラー指令以外の指令である手順情報からなるグループから選択され、及び／又は、タグ・ビットは、（ａ）該タグ・ビットが（ｉ）フィールド長、（ｉｉ）正規化、（ｉｉｉ）そのようなフィールドが相対的か否か、（ｉｖ）そのようなフィールドが絶対的か否か、からなるグループから選択された少なくとも一つのフィールド特性を暗黙的に記述する、及び（ｂ）該タグ・ビットが可変長を有しかつ当該可変長についての情報並びに可能フィールド内容情報を含み、該可変長は、該フィールド内容情報から独立である、からなるグループから選択された少なくとも一つの特性を有し、オプ・コード・ビット及び／又はタグ・ビットの少なくともあるものは、フィールドの圧縮解除を三次元オブジェクトの非圧縮表面特性の中にガイドするように構成してもよい。
本発明のシステムでは、オブジェクトは、（ｉ）位置、（ｉｉ）ノーマル、（ｉｉｉ）カラー、（ｉｖ）テキスチャ・マップ座標、及び（ｖ）オブジェクトの材料表面特性からなるグループから選択された少なくとも一つの特性を含んでいる表面特性を有し、及び／又はオブジェクトは、（ｉ）オブジェクトの位置の特性が直線ｘ、ｙ、ｚ座標として表され、（ｉｉ）オブジェクトのカラーの特性が少なくとも赤、緑、青、及びアルファ・コンポーネントを有しているように表され、該カラーが（ａ）放射カラー、（ｂ）環境カラー、（ｃ）散乱カラー、及び（ｄ）鏡面カラーからなるグループからなる選択された少なくとも一つのカラーを含み、（ｉｉｉ）オブジェクトのノーマルの特性が直線Ｎｘ、Ｎｙ、及びＮｚベクトル係数によって表され、（ｉｖ）オブジェクトのノーマルの特性は、ノーマルのルックアップ表の中にインデックスによって表され、（ｖ）位置、（ｖｉ）ノーマル、（ｖｉｉ）カラー、（ｖｉｉｉ）テキスチャ・マップ座標、及び（ｉｘ）材料表面特性からなるグループから選択された少なくとも一つの特性を含むように構成してもよい。
【００１６】
本発明のシステムでは、ノーマルのルックアップ表は、所定の正規化されたノーマルを含み、かつノーマルのそれぞれは、所定の正規化されたノーマルのルックアップ表の中に単一インデックスによって表され、インデックスは、（ｉ）当該インデックスは、表現されるべきノーマルの直線表現サイン・ビットを備えているインデックス表現のビットを含み、（ｉｉ）インデックスは、フォールドされたノーマルが該フォールディング平面の既知の側面上にあることを確実にするように少なくとも一つのフォールディング平面ｘ＝ｙ、ｘ＝ｚ、ｙ＝ｚによって表されるべきノーマルの直線表現の絶対量の可能なフォールディングを指定している少なくとも一つのビットを含み、（ｉｉｉ）インデックスは、ノーマルの経度情報及び緯度情報を表しているビットを含み、（ｉｖ）インデックスは、オクタント情報のビット、セクスタント情報のビット、及びフォールドされたノーマルの経度及び緯度についての情報の追加フィールドを含むべく画定され、（ｖ）インデックスは、ノーマルの経度情報及び緯度情報を表しているビットを含み、及びオクタント情報のビット、セクスタント情報のビット、及びフォールドされたノーマルの経度及び緯度についての情報の追加フィールドを更に含み、（ｖｉ）インデックスは、オクタント情報の３ビット、セクスタント情報の３ビット、及びフォールドされたノーマルの経度及び緯度についての情報の２つの追加フィールドを含むべく画定され、（ｖｉｉ）インデックスは、ノーマルの経度情報及び緯度情報を表しているビットを含み、及びオクタント情報の３ビット、セクスタント情報の３ビット、及びフォールドされたノーマルの経度及び緯度についての情報の２つの追加フィールドを更に含む、ことからなるグループから選択された少なくとも一つの特性を有するように構成してもよい。
本発明のシステムでは、圧縮解除されるべきデータ・ストリームは、データが汎用三角形メッシュを画定している線形フォーマットに変換された、頂点を有している複数の三角形を画定している三次元三角形データとして表されたオブジェクトからもたらされ、表面特性の個々のものが量子化され、可変長圧縮が表面特性のシーケンシャルなものの間の相違に適用されるように構成してもよい。
【００１７】
【作用】
本発明による圧縮解除に対して、三次元幾何学形状は、線形ストリームにおける頂点の各場合に１／３三角形と２三角形との間の平均を指定させる、汎用の三角形メッシュとしてまず表される。個々の位置、カラー及びノーマルズは、個々の位置、カラー、及びノーマルズに適用される可変長圧縮で、量子化される。量子化された値は、頂点トラバーザル順序を供給すべく近隣の間で符号化されるデルタ（Δ）圧縮であり、かつメッシュ・バッファ参照が生成される。デルタ−位置、デルタ−ノーマルズ及びデルタ−カラーのヒストグラムが生成されて、その後に可変長ハフマン・タグ・カラー、並びにデルタ−位置、デルタ−ノーマルズ及びデルタ−カラーが生成される。圧縮された出力２値ストリームは、出力ハフマン表初期化、順序付けされた頂点トラバーザルズ、出力タグ、及びデルタ−位置、デルタ−ノーマルズ及びデルタ−カラーを含む。
そのように圧縮された三次元幾何学形状データの圧縮解除は、ハードウェア、ソフトウェア、またはそれぞれの組合せでインプリメントされうる。圧縮解除装置は、圧縮されたデータ・ビット及び入力データの大きさを表している信号を受け取る入力ＦＩＦＯを含む。ＦＩＦＯ出力は、入力ブロック状態マシン及び入力ブロックに結合される。入力ブロック及び入力ブロック状態マシンからの出力は、バレル・シフタ装置に結合される。また、入力ブロック出力は、状態マシンへ出力するハフマン表にも入力される。また、状態マシン出力は、その出力がタグ・デコーダに結合されるデータ経路コントローラ、及びバレル・シフタ装置からの出力を受け取るノーマル・プロセッサにも結合される。また、圧縮解除装置は、バレル・シフタ装置からの出力を受け取る位置／カラー・プロセッサも含む。ノーマル・プロセッサ及び位置／カラー・プロセッサからの出力は、フォーマット・コンバータにマルチプレクスされる。
【００１８】
フォーマット・コンバータへの出力を生成するデータ・ストリームにおける命令に対して、圧縮解除装置は、フォーマット・コンバータに送られるノーマルに対するビットと並列にタグ・デコーダへ送られる１２ビット・タグを生成する。リードバック(read-back) 経路は、圧縮解除装置の内部状態をリードバックするために用いられる。圧縮解除装置は、次の手順を実行する：
（１）次の命令の残り、及び後続する命令の最初の８ビットをフェッチする；
（２）タグ表を用いて、あらゆる圧縮値フィールドを全精度に拡張する；
（３Ａ）値が相対的であれば、現行の値に加える；さもなければ、置換する；
（３Ｂ）メッシュ・バッファ参照であれば、古い値をアクセスする；
（３Ｃ）他の指令であれば、ハウスキーピングを行う；
（４）ノーマルであれば、全値を得るためにＲＯＭ表を通してインデックスをわたす；
（５）汎用三角形ストリップ形における値を次の段階へ出力する。
三角形データの圧縮解除されたストリームは、次いで、従来のレンダリング・パイプラインにパスされうるし、そこでそれが完全浮動小数点精度で処理することができ、その後ディスプレイされるかまたはさもなくば用いられる。
本発明の他の特徴及び利点は、添付した図面に関連して、好ましい実施例が詳細に示される以下の説明から明らかであろう。
【００１９】
【実施例】
本発明によるグラフィックス・デコンプレッサは、三次元グラフィックス・オブジェクトを圧縮解除する。そのような幾何学形状の三次元圧縮は、例えば、ネットワークにわたる、圧縮された三次元幾何学形状を送るのに必要な時間における低減、並びに、例えば、ＣＤ−ＲＯＭ、等の幾何学形状が記憶されうる空間の低減を許容する。
圧縮された三次元グラフィックスの圧縮解除を説明する前に、本発明が実行されうる環境全体を、図１を参照して説明する。
図１は、三次元圧縮幾何学形状データがその上で送信され、かつ受信端でソフトウェア、ハードウェア、またはそれぞれの組合せを用いて圧縮解除されうる汎用のネットワークを示す。勿論、本発明による三次元グラフィックス圧縮の圧縮解除は、例えば、メモリ、ＣＤ−ＲＯＭ、等に記憶される圧縮データのような、ネットワークを介さないで与えられる圧縮データで実行されうる。
図１に示すように、三次元グラフィックス・データのソース（発生源）１０は、その処理されかつ圧縮された出力が、一つ以上のターゲット・クライアントまたはデコーダ・システム４０に一つ以上のネットワーク３０にわたり結合されるサーバまたはエンコーダ・システム２０に結合されうる。ネットワークは、同種(homogeneous) 、異種(heterogeneous) 、または二地点間(point-to-point)でありうる。
【００２０】
サーバ２０は、関連主メモリ７０を伴う中央処理装置それ自体（“ＣＰＵ”）６０、メッシュ・バッファ８０、圧縮アルゴリズムを含みうるメモリ部分９０、及びリード・オンリー・メモリ（“ＲＯＭ”）の領域１００を含む中央処理ユニット５０を含む。代替的に、本発明による圧縮は、ソフトウェアとは反対にハードウェアにおいても実行されうる。アタッチメント１（添付省略）は、上記参照特許出願に記載されたような圧縮アルゴリズムを一覧表として示しているコードのコピーである。
また、サーバ２０は、一つ以上のＣＤ−ＲＯＭｓを含みうる、記憶ディスク装置８０への記憶のためにその圧縮された出力データがディスク・レイアウト装置７０によって構成される、三次元グラフィックス圧縮装置６０も含む。サーバは、ネットワーク・インターフェイス装置１１０を介してネットワーク３０にわたり通信する。当業者は、サーバ２０が圧縮されたデータに対する複数のクライアント−デコーダ要求間を仲裁する(arbitrating) ための機構を含みうるということに注目するであろう。
１９９５年８月４日に出願した、発明の名称が「三次元グラフィックス・データの幾何学形状圧縮のための方法及び装置」である本発明の出願人の特許出願に記載されたように、三次元幾何学形状データの損失が大きい圧縮は、ディスプレイされたオブジェクトの品質における損失がほとんどなく、６：１〜１０：１の比率を生成することができる。
【００２１】
この明細書の以下の部分は、本発明による圧縮解除の理解を容易にするために、上記参照特許出願に示された、圧縮を説明する。
ネットワーク環境において、受信端で、デコーダ・システム４０は、ネットワーク・インターフェイス装置１２０、三次元グラフィックス・データを圧縮解除し、かつその出力が三次元グラフィックス・レンダリング装置１４０に結合される、本発明による、装置１３０を含む。システム４０は、デコーダ・システム４０は、ＣＰＵ１６０、メモリ１７０、１８０が含みうる圧縮解除ソフトウェアの部分、及びＲＯＭ１９０を含む中央処理システム１５０を更に含みうる。圧縮された三次元グラフィックスは、ソフトウェア、ハードウェア、または各組合せを用いて有利に圧縮解除されうる。デコーダ４０からの圧縮解除出力は、視聴者(viewer)２００、または圧縮解除されたグラフィックスを要求している別のシステムに更に結合されうる。勿論、装置４０は、本発明により予め圧縮された、三次元グラフィックスが圧縮解除のために、記憶装置８２、ディスクまたはＣＤ−ＲＯＭ８４、等、から結合されうる、スタンドアロン装置でありうる。装置４０は、例えば、コンピュータまたはワークステーションを含みうる。
ここで、三次元グラフィックス圧縮装置６０が本発明の出願人の上記特許出願に記載されたように機能することを想定すると、三角形データは、汎用三角形メッシュにまず変換される。記憶媒体８０の所与の固定された容量に対して、三角形メッシュ・データ構造は、三角形データの準最適表現(near-optimal representation) である。好ましい実施例では、三次元グラフィックス・オブジェクトは、変換後のそのフォーマットが各線形ストリップ頂点を、平均して、約１／３三角形から２三角形に特定させる、三次元三角形データとして表されうる。
更に、そのような三角形ストリップ構造は、頂点アレー・データ構造にわたる単一モノトニック走査によって圧縮された幾何学形状の抽出を許容する。
図２は、汎用三角形メッシュ・データ構造、及び表面幾何学形状の汎用メッシュ・バッファ表現を示す。そのようなメッシュ・データ構造は、それ自体を線形ストリップに制限することにより、汎用三角形ストリップ・フォーマットが空間において２のポテンシャル・ファクタ(potential factor of two) を無駄にするけれども、三次元幾何学形状圧縮に用いられうる。図２に示した幾何学形状は、例えば、一つの三角形ストリップによって表わすることができるが、多くの内部頂点がストリップに二度現れる。
【００２２】
図２において、汎用三角形ストリップは、次のように画定されうる。ここで、Ｒは、再開始を示し、Ｏは、最古の置換(replace oldest)を示し、Ｍは、中間の置換(replace middle)を示し、トレーリング・レターｐは、メッシュ・バッファへのプッシュを示す。大文字の後に続く数字は、頂点番号であり、負の数字は、−１が最も新しくプッシュされた頂点を示すような、メッシュ・バッファ・リファレンスである。
Ｒ６，Ｏ１，Ｏ７，Ｏ２，Ｏ３，Ｍ４，Ｍ８，Ｏ５，Ｏ９，Ｏ１０，Ｍ１１
Ｍ１７，Ｍ１６，Ｍ９，Ｏ１５，Ｏ８，Ｏ７，Ｍ１４，Ｏ１３，Ｍ６
Ｏ１２，Ｍ１８，Ｍ１９，Ｍ２０，Ｍ１４，Ｏ２１，Ｏ１５，Ｏ２２，Ｏ１６，
Ｏ２３，Ｏ１７，Ｏ２４，Ｍ３０，Ｍ２９，Ｍ２８，Ｍ２２，Ｏ２１，Ｍ２０，
Ｍ２７，Ｏ２６，Ｍ１９，Ｏ２５，Ｏ１８
同じ命名法を用いて、汎用三角形メッシュは、次のように画定されうる：
Ｒ６ｐ，Ｏ１，Ｏ７ｐ，Ｏ２，Ｏ３，Ｍ４，Ｍ８ｐ，Ｏ５，Ｏ９ｐ，Ｏ１０，
Ｍ１１，Ｍ１７ｐ，Ｍ１６ｐ，Ｍ−３，Ｏ１５ｐ，Ｏ−５，Ｏ６，Ｍ１４ｐ，
Ｏ１３ｐ，Ｍ９，Ｏ１２，Ｍ１８ｐ，Ｍ１９ｐ，Ｍ２０ｐ，Ｍ−５，Ｏ２１ｐ，
Ｏ−７，Ｏ２２ｐ，Ｏ−９，Ｏ２３，Ｏ−１０，Ｏ−７，Ｍ３０，Ｍ２９，
Ｍ２８，Ｍ−１，Ｏ−２，Ｍ−３，Ｍ２７，Ｏ２６，Ｍ−４，Ｏ２５，Ｏ−５
頂点リファレンスは、有利に、完全頂点仕様(full vertex specification) よりもかなりコンパクト（例えば、より少ないビットで表される）にすることができるということに注目すべきである。
三次元幾何学形状圧縮は、古い頂点（例えば、上記トレーリング文字“ｐ”を有する頂点）をメッシュ・バッファ・メモリ８０に関連付けられたキューの中に明確にプッシュする（図１参照）。これらの古い頂点は、古い頂点が再び望ましいときに後で明確に参照される。このアプローチは、ほぼあらゆる形状の不規則メッシュを支持する精密制御(fine control)を供給する。バッファ・メモリ８０は、有限の長さを有し、かつ実際には、４−ビット・インデックスを必要とする、１６の最大固定キュー長が好ましい実施例において用いられる。三次元グラフィックスの圧縮に関して、用語“メッシュ・バッファ”は、このキューを参照し、表現“汎用三角形メッシュ”は、汎用三角形ストリップとメッシュ・バッファ・リファレンスとの組合せを参照する。
【００２３】
メッシュ・バッファ８０の固定サイズは、１６の独自のリファレンスよりも長いあらゆるラン（走行）をブレーク・アップ（分割）するために圧縮された幾何学形状に対して全テッセレータズ／リ・ストリッパーズ(tessellators/re-strippers) を必要とする。しかしながら、幾何学形状圧縮が一般にユーザ・レベルにおいて直接的にプログラムされるのではなく複雑なテッセレータズ／リフォーマッターズ(reformatters)、非面倒(non-onerous) な制限による。１６の古い頂点は、冗長幾何学形状の約９４％までの再仕様(re-specification)を回避することを許容することが事実できる。
また、図２は、表面幾何学形状の一般のメッシュ・バッファ表現の一例でもある。幾何学形状圧縮言語は、汎用三角形ストリップの４つの頂点置換符号；具体的には、最古の置換、中間の置換、時計方向再開始、及び反時計方向再開始を支持する。更に、言語は、この頂点がメッシュ・バッファの中にプッシュされるべきか否かを示すべく各頂点ヘッダにおいて追加ビットを加える。一実施例では、メッシュ・バッファ・リファレンス指令は、どの古い頂点が  ２ビット頂点置換符号と共に、再リファレンスされるべきであるかを示すべく４−ビット・フィールドを有する。メッシュ・バッファ・リファレンス指令は、メッシュ・バッファ・プッシュ・ビットを含まない；古い頂点は、一度だけリサイクルすることができる。
【００２４】
実際には、幾何学形状は、純粋な位置データをほとんど含んでいないし、かつ一般に、また、ノーマル、及び／又はカラー、及び／又はテキスト・マップ座標は、頂点毎に指定される。従って、メッシュ・バッファ８０へのエントリは、ノーマル及びカラー及び／又はテキスト・マップ座標を特に含んでいる、全ての関連頂点毎情報(associated per-vertex information) に対する記憶を含む。
最大記憶空間効率に対して、頂点がデータ・ストリームにおいて指定されるときには、頂点毎ノーマル及び／又はカラー情報は、位置情報で直接束ねられるのが好ましい。そのような包束(bundling)は、二つの状態ビットによって制御されるのが好ましい：頂点を有するバンドル・ノーマルズ（ＢＮＶ）、及び頂点を有するバンドル・カラー（ＢＣＶ）。図８は、他の中にビットを含んでいる指令構造を示す。頂点がメッシュ・バッファの中にプッシュされたときには、その束ねられたノーマル及び／又はカラーがプッシュされたならばこれらのビットも同様に制御する。
上記参照特許出願に記載された圧縮技術は、三角形に限定されないし、かつベクトル及びドットも圧縮されうるということに注目すべきである。例えば、線は、置換ビットがＭＯＶＥ及びＤＲＡＷであるような、三角形のサブセットである。次いで、出力頂点は、他の頂点が最近、先に省略された頂点である、線の一つの終点を表わす頂点である。ドットに対して、置換ビットは、ＤＲＡＷであり、かつ出力頂点は、頂点である。
ＣＰＵ５２がメッシュ・バッファ・リファレンス指令を実行するときに、この処理は、逆転される。即ち、２ビットは、ノーマル及び／又はカラーが受け継がれるか、またはメッシュ・バッファ記憶装置８０から読み取られるか、または現行ノーマルまたは現行カラーから取得されるべきかを指定する。ソフトウェア５８は、これら二つの現行値を設定するための明確な指令を含むのが好ましい。しかしながら、明確な“設定現行ノーマル”指令が、アクティブなＢＮＶ状態ビットを有する、メッシュ・バッファ・リファレンスを後続するときに、この規則に対する例外が存在する。この情況では、前者は、表面幾何学形状におけるハード・エッジのコンパクト表現を許容すべく、メッシュ・バッファ・ノーマルを無効にする。また、類似のセマンティックスもカラーに対して画定され、表面カラーにおけるハード・エッジのコンパクト表現を許容する。
二つの追加状態ビットは、頂点のストリームが三角形に変換されるときにノーマル及びカラーの解釈を制御する。三角形にわたる複製ノーマル（ＲＮＴ）ビットは、三角形を完成する最終頂点のノーマルが三角形全体にわたり複製されるべきであることを表わす。三角形にわたる複製カラー（ＲＣＴ）ビットは、図８の指令構造に示されるように、同様に画定される。
【００２５】
ここでイメージｘｙｚ位置の圧縮を説明する。３２ビットＩＥＥＥ浮動小数点数に関連付けられた８ビット指数の使用は、大きさにおいてサブ・アトミック粒子から数十億光年までの範囲を位置に許容する。しかし、所与のモザイク形状オブジェクト(tessellated object)に対して、現行モデリング・マトリックスによってちょうど一度だけ指数が実際に指定され、かつオブジェクト幾何学形状は、２４ビット固定点仮数(fixed-point mantissa)だけを用いて所与のモデリング空間内に効果的に記載される。多くの場合、視覚的受容のためにかなり少ない数ビットを必要とすしかつ、幾何学形状圧縮言語は、１ビットに至るまでの位置データの変数量子化を支持するのが好ましい。
他の極端では、経験的視覚検査並びに半導体ハードウェア・インプリメンテーションの考察は、位置のコンポーネント当たり１６ビット以下の精度がほとんど全ての場合に必要であるということを示す。
【００２６】
しかしながら、オブジェクト当たりのローカル・モデリング空間の位置及びスケールは、全３２ビットまたは６４ビット浮動小数点座標によって指定されるということを想定する。十分な数値ケアを用いて、複数のそのようなモデリング空間は、１６ビット以上の位置精度を有するシームレス幾何学形状座標システムを形成すべく一緒に組合せられうる。
殆どの幾何学形状は、ローカルである。それゆえに、各オブジェクトに対する１６ビット（またはそれ以下）モデリング空間内で、汎用メッシュ・バッファ・ストリームの隣接頂点間の差（Δ）は、たいてい有効（重要度）において１６ビット以下である。所望ならば、幾何学形状のバッチにおける近隣位置Δのビット長を表しているヒストグラムを構築しうるし、かつこのヒストグラムに基づき頂点をコンパクトに表わすために可変長コードを割り当てうる。記述するように、カスタマイズされたハフマン符号化は、幾何学形状圧縮における位置Δを符号化するために用いるのが好ましい。
ここで、赤−青−緑−アルファ（“ＲＢＧＡ”）カラーの圧縮を説明する。カラー・データは、位置と同様に処理されるが、より小さい最大精度で処理される。それゆえに、ＲＧＢαカラー・データは、（１．０が１００％反射率を表わすような）絶対線形反射率値である１２ビットの符号なし小数コンポーネントにまず量子化される。追加パラメータは、カラー・データを１２ビット以下のあらゆる量に効果的（有効）に量子化させる。例として、図６に示すように、カラーは、５−５−５ＲＧＢカラー空間内に全てありうる。オプショナル・αフィールドは、図８に示したカラーαプレゼント（“ＣＡＰ”）状態ビットによって制御される。最終レンダード画像(final rendered image)上で個別画素カラーは、量子化された頂点カラー間にまだ挿入され、また一般にライティング(lighting)の対象でもある。
【００２７】
実際には、同じΔ−符号化は、カラー・コンポーネント及び位置に対して用いられうる。カラー・データ圧縮の領域は、幾何学形状圧縮と従来画像圧縮が最も類似した問題に直面したところである。しかしながら、フォーカスにおける差の原因で、多くの高度画像圧縮技術が幾何学形状カラー圧縮に対して回避されうる。
例えば、ＪＰＥＧ画像圧縮標準は、幾何学形状圧縮に対して行うことができない圧縮解除データのビューイングに関する仮定（想定）に依存する。例えば、画像圧縮では、画素は、完全に直交（矩形）アレイで現われ、かつビューしたときに、各画素が可視角度の狭い範囲の限界を定めるということが先に知られている。対照的に、幾何学形状圧縮では、視聴者とラスタ化された幾何学形状の間の関係は、予想不可能である。
画像圧縮では、視聴者の目の上に表示された画素の空間周波数は、たいてい人間の視覚システムのカラー鋭敏さよりも高いということが知られている。この理由で、カラーは、ＵＶカラー・コンポーネントがＹ（強度）コンポーネントよりも低い空間周波数で表現することができるようにＹＵＶ空間に一般に変換される。通常、サブ・サンプルＵＶコンポーネントを表しているディジタル・ビットは、二つ以上の画素の間で分配される。しかしながら、視聴者の眼に対する幾何学形状の固定表示スケールが存在しないので、幾何学形状圧縮は、これを利用することができない。更に、圧縮三角形頂点が汎用三角形メッシュの４つから８つまたはそれ以上の頂点に連結されると仮定すると、頂点にわたるカラー情報の“half（半分）”を共有する一定した方法が存在しない。
同様な議論は、離散余弦変換（ＤＣＴ）のような、従来の画像圧縮に用いられる更に複雑な変形に適用される。これらの変換は、画素値の正則または正規（矩形・直交）サンプリングを想定し、かつ圧縮解除の間中に多量のランダム・アクセスを必要とする。
【００２８】
擬似カラー・ルックアップ表を用いることは、この分野で知られているが、そのような表は、固定最大サイズを要求し、かつ実時間処理に対する相対的に高価な資源を表しうる。擬似カラー・インデックスがある一定の場面(scenes)に対してわずかに高い圧縮率をもたらしうると同時に、ＲＧＢモデルは、更に一般化されかつインプリメントするのにかなり安い。
ＲＧＢモデルでは、ＲＧＢ値は、線形反射値として表される。理論的に、照明(lighting)の全効果を予め知ることができるならば、ＲＧＢコンポーネントが非線形、または知覚的線形空間（ガンマ補正空間(gamma corrected space) とも称される）で表現されていたならば、一つ以上の表現ビットを落すことができる。実際には、照明効果は、予測可能でない傾向があり、かつ非線形光線から線形光線へのオン・ザ・フライ変換は、かなりのハードウェア資源を必要とする。
【００２９】
ここで表面ノーマル(normals) の圧縮を説明する。従来、８ビット・カラー強度を決定するために計算において９６ビット・ノーマル（３つの３２ビットＩＥＥＥ浮動小数点数）が用いられる。理論的に、９６ビットの情報は、単位球の表面上に均等に拡がる、２96の異なるノーマルを表わすために用いることができる。結果として得られた非常に高い精度は、２-46 ラジアン毎にあらゆる方向に突出しているノーマルを表わす。
しかし、ＩＥＥＥ浮動小数点正規化ノーマルに対して、指数ビットは、有効的に用いられない。拘束ＮX 2 ＋Ｎy 2 ＋Ｎz 2 ＝１を想定すると、ＮX 、Ｎy 、またはＮz の少なくとも一つは、０．５から１．０の範囲でなければならない。レンダリングの間に、このノーマルは、複合モデリング・オリエンテーション・マトリックスによって変換される：
【００３０】
【数１】
Ｎ' x ＝ＮX ・Ｔ0,0 ＋Ｎy ・Ｔ0,1 ＋Ｎz ・Ｔ0,2 
Ｎ' y ＝Ｎx ・Ｔ1,0 ＋Ｎy ・Ｔ1,1 ＋Ｎz ・Ｔ1,2 
Ｎ' z ＝ＮX ・Ｔ2,0 ＋Ｎy ・Ｔ2,1 ＋Ｎz ・Ｔ2,2 
【００３１】
照明がワールド・コーディネートで実行されるような一般的インプリメンテーションを想定すると、ビュー変換は、ノーマルの処理に含まれない。ノーマルが事前正規化されているならば、ノーマルの冗長再正規化を回避するために、複合モデリング変換マトリックスＴは、スケール変更を分配するために一般に事前正規化される。それゆえに：
【００３２】
【数２】
Ｔ0,0 2 ＋Ｔ1,02 ＋Ｔ2,0 2 ＝１、等。
【００３３】
ノーマル変換の間、浮動小数点演算ハードウェアは、最大コンポーネントの精度まで全ての加法アーギュメントを効果的に切り捨てる。結果は、スケール保存モデリング・オリエンテーション・マトリックスによって変換が行われる正規化ノーマルに対して、変換されたノーマル値の数値精度は２〜３の特別な場合を除いた全てにおいて２４ビット固定点精度未満(no more than 24-bit fixed-point accuracy)まで低減される。
比較すると、２４ビット・ノーマル・コンポーネントでさえも、修正されたハブル天体望遠鏡よりも高いアンギュラ精度を供給しうるし、かつ実際には、あるシステムは、１６ビット・ノーマル・コンポーネントだけを利用する。１６ビット・ノーマル・コンポーネントによる実験的テストでは、ノーマル間の０．０１ラジアンのアンギュラ密度からの結果（例えば、単位球上に分散された約１００，０００のノーマル）は、より高い精度の表現から視覚的に識別可能ではない。直線空間では、これらのノーマルは、高い表現精度をまだ要求し、かつ実際には、一つのサイン及び一つのガード・ビットを含んでいる１６ビット・コンポーネントは、よい設計選択を表わす。これは、ノーマルを表わすために４８ビットをまだ必要とするが、しかし１００，０００の指定ノーマルだけに興味があるので、理論的に単一１７ビット・インデックスは、これらのノーマルのどれかを表しうる。
【００３４】
ここで、インデックスとしてのノーマルの使用、及び供給された合成利点(resultant advantages)を説明する。単位球上のノーマルのインデックスをＮX 、Ｎy 、Ｎz 値に戻して変換する一方法は、たぶんメモリ７０に装填されている表の、表ルックアップによってである。表サイズは、可能的に大きいけれども、必要サイズは、単位球に存在する４８通りのシンメトリ（対称性）を利用することによって実質的に低減することができる。
より特定的には、図３に示すように、単位球は、サイン・ビットによる８つのクォドラントにおけるサイン・ビットによって対称である。ノーマル表現ビットの３つをノーマルのｘｙｚコンポーネントの３つのサイン・ビットにすることによって、単位球の１／８を表わすことだけが次いで必要である。単位球の各オクタントは、平面ｘ＝ｙ、ｘ＝ｚ、及びｙ＝ｚについて折り曲げることによって６つの同一コンポーネントに分割することができる。６つの可能なセクスタント(sextants)は、表現されたままの球の１／４８だけを残す、別の３ビットで符号化される。
【００３５】
上記シンメトリを用いることは、８×６＝４８のファクタでルックアップ表サイズを低減する。１００，０００エントリを記憶する代わりに、ルックアップ表は、ＲＯＭ５９（図１参照）内にたぶん記憶される、オン・チップＲＯＭルックアップ表であるべく十分に小さいサイズの、約２，０００エントリだけを記憶する必要がある。ルックアップ表の中にインデックスすることは、先に記載された二つの３ビット・フィールドに加えられたときに全ての３つのノーマル・コンポーネントを記載するために１７ビット・フィールドを結果として生ずる、１１のアドレス・ビットを必要とする
有限セットの単位ノーマルを表わすことは、単位球の表面上に点を位置決めすることに等しい。完全に均等なアンギュラー密度分布が多くの数の点に対して存在しないにもかかわらず、多くの近最適分布が存在する。理論的に、上述した型の４８通りシンメトリは、三次元幾何学形状圧縮解除装置１３０に関連付けられた圧縮解除ルックアップ表に用いることができる（図１参照）。
しかしながら、複数の更なる拘束は、符号化の異なる選択を要求する。第１に、スケーラブル密度分布が望まれる、例えば、“０”までの更に下位のアドレス・ビットをルックアップ表に設定することは、単位球上にかなり均等なノーマル密度を結果としてまだ生ずるような分布。さもなければ、全ての符号化密度に対して異なるルックアップ表が必要である。第２に、Δ符号化可能分布は、幾何学形状の隣接頂点が、単位球の表面で隣接するノーマルを統計的に有することにおいて望ましい。単位球表面の二次元空間上の隣接位置は、二次元オフセットによって最も簡潔に符号化される。そのようなメートル(metric)が存在するような分布を有することが望ましい。そして、ノーマル符号化処理に関連付けられた計算費用が極めて重要ではないけれども、より低い符号化費用を有している分布がそれでもなお好ましい。
【００３６】
上記参照特許出願による圧縮は、単位球の一つのセクスタント内のアンギュラ空間に正則グリッドを有している分布を用いる。そのように、モノリシックな１１ビット・インデックスよりも、セクスタント内の全てのノーマルは、二つの６ビット直交アンギュラ・アドレスで有利に表現される。次いで、この構成は、先のビット総数を１８ビットに改訂する。位置及びカラーの場合のように、ノーマルの更なる量子化が受容されたならば、これらの６ビット・インデックスは、より少ないビットまで低減することができ、それゆえに１８から少なくとも６ビットまでのどれかを用いて絶対ノーマルを表わすことができる。しかしながら、以下に説明するように、この空間は、ノーマルの高品質表現に必要なビット数を更に低減するためにΔ−符号化されるのが好ましい。
ここでノーマル符号化パラメータ化を説明する。単位半径球上の点は、θがｙ軸についての角度、φがｙ＝０平面からの経方向角度であるような、角θ及びφにより極座標を用いてパラメータ化される。式（１）は、次のように直交座標と極座標の間のマッピングを支配する：
【００３７】
【数３】
ｘ＝ｃｏｓθ・ｃｏｓφ    ｙ＝ｓｉｎφ    ｚ＝ｓｉｎθ・ｃｏｓφ  （１）
【００３８】
球上の点は、オクタントによってまず折り曲げられ、次いで６つのセクスタントの一つにｘｙｚの分類順に折り曲げられる。全ての表符号化は、半球によって境界をつけられた領域における正のオクタントで行われる：
【００３９】
【数４】
ｘ≧ｚ              ｚ≧ｙ                ｙ≧０
【００４０】
図３に示すように、説明した三角形形状パッチは、θでは０からπ／４ラジアンまで、φでは０から最大０．６１５４７９７０９ラジアンまで実行する。
量子化された角度は、ｎが０から６までの範囲にある、二つのｎビット整数θn ハット（＾）、φn ハット（＾）によって表される。所与のｎに対して、インデックスθとφの間の関係は：
【００４１】
【数５】
0003884509.tif 000002
【００４２】
式（２）は、どのようにθn ハット（＾）、φn ハット（＾）の値が、次いで、式（１）を介して直線ノーマル座標コンポーネントに変換できる、極座標θ及びφに変換できるかを示す。
処理を逆向きにするために、例えば、所与のノーマルＮをθn ハット（＾）、φn ハット（＾）に符号化するために、式（２）を単に反転することはできない。その代わり、Ｎは、標準オクタント及びセクスタントにまず折り曲げられなければならず、Ｎ’を結果として生ずる。次いで、Ｎ’は、セクスタントにおける全量子化ノーマルを点在させなければならない。固定ｎに対して、最大（最隣接ユニティ）ドット・プロダクトを結果として生ずるθn ハット（＾）、φn ハット（＾）は、Ｎの適切な符号化を画定する。例えば、φを設定するために表を通してインデックスし（索引を付け）、そしてθの中にジャンプさせるような、θn ハット（＾）、φn ハット（＾）の正しい値を見出す、より有効な方法が存在する。
この重大な局面にあたって、絶対ノーマルの完全ビット・フォーマットを付与することができる。上位３ビットは、オクタントを指定し、次の３ビットは、セクスタント、そして最後の二つのｎビット・フィールドは、θn ハット（＾）、φn ハット（＾）を指定する。３ビット・セクスタント・フィールドは、図３に示される２進（バイナリ）コードである、６つの値の一つを取る。
更なる詳細を次に示す。標準パッチの角（コーナー）における３つのノーマルは、６、８、及び１２倍のように、倍増表現される。セクスタント・フィールドの二つの未使用値を採り入れることによって、これらのノーマルは、２６の特別ノーマルとして独自に符号化することができる。
ノーマルのこの表現は、少なくともセクスタント内で、Δ符号化に従い、ある追加ワークを伴うけれども、これは、共通エッジを共有するセクスタントに拡張することができる。二つのノーマル間のΔコードは、単にθn ハット（＾）、φn ハット（＾）における差、具体的には、Δθn ハット（＾）、Δφn ハット（＾）である。
【００４３】
上記参照特許出願では、通常のハフマン・アルゴリズムの変形を有する、圧縮タグが用いられる。
ハフマン圧縮アルゴリズムは、それらの記号の発生統計量の頻度（周波数）（例えば、ヒストグラム）と共に、表されるべき一組の記号を取り入れる。記号が指定した頻度（周波数）で発生すると想定して、これから、これらの記号を近最小合計ビット数で表させる、可変長の、独自に識別可能なビット・パターンが生成される。
ＪＰＥＧを含む、多くの圧縮技術は、後続する可変長データ・フィールドの長さを表わすためのタグとして独自の記号を生成する。このデータ・フィールドは、一般に指定長デルタ値である。それゆえに、最後の２進ストリームは、それぞれがその長さがその固有タグ記号に関連付けられるデータ・フィールドによってすぐに後続される、（自己記述長）可変長タグ記号から構成される。
参照特許出願では、幾何学形状圧縮に対する２進フォーマットは、位置、ノーマル、及びカラー・データ・フィールドを表わすためにこの技術を用いる。幾何学形状圧縮に対して、これらの＜ｔａｇ，ｄａｔａ＞フィールドは、より一般的なコンピュータ命令セット・オプ−コード(op-code) フィールドによってすぐに先行される。これらのフィールドは、可能な追加オペランド・ビットと共に、幾何学形状命令として参照される（表される）（図４〜図１５参照）。
従来、圧縮されるべき各値は、それ自身の関連ラベルが割り当てられ、例えば、ｘｙｚΔ位置は、３つのタグ値ペアによって表される。しかし、Δｘｙｚ値は、相関関係でないので、より密で、より簡素な、表現を達成することができる。一般に、ｘｙｚΔの統計的ポイントは、空間の全ての方向を均等にポイントする。それゆえに、ｎが最大のΔを表わすために必要なビットの数であるならば、統計的に他の二つのΔ値は、それらの表現に対してｎ−１．４ビットの平均を必要とする。従って、実際には、単一フィールド長タグは、Δｘ、Δｙ、及びΔｚのビット長を表わすために用いうる。
残念ならが、このアプローチを用いることは、コンピュータ当たり一つのビット以上よりも幾分少なくセーブするために別のハフマン技術を利用することを阻止する。しかしながら、インプリメントされた実施例は、（Δｙ及びΔｚに対して）二つの追加タグ・フィールドを指定しなくてもよいことによってこの欠点を圧迫する。更なる利点は、所望ならば、単一タグ・フィールドを用いることがハードウェア圧縮解除エンジンに並列で全ての３つのフィールドを圧縮解除させるということである。
【００４４】
同様なアーギュメントがＲＧＢα値のΔ’ｓに対して保持され、従って、単一のフィールド長タグは、Ｒ、Ｇ、Ｂ及び、もし存在すれば、αフィールドのビット長を表わすために用いられる。
また、絶対及びΔノーマルは、単一タグによって指定することができる単一値（ｎ）によってパラメータ化される。高速で、低コストのハードウェア・インプリメンテーションを容易にするために、ハフマン・タグ・フィールドの長さは、比較的小さな値である、６ビットに制限されうる。６４エントリ・タグ・ルックアップ表は、１クロック・サイクルにおけるタグの復号を許容する。一つの表は、位置に対して存在し、別の表は、ノーマルに対して存在し、更に別の表は、カラー（及びオプションとして、テクスチャ座標に対しても）存在する。各表は、タグ・フィールドの長さ、データ・フィールドの長さ、データ正規化係数、及び絶対／相対ビットを含む。
適正なハードウェア・インプリメンテーションに対して、さらに別の厄介な問題に対処しなければならない。以下に説明するように、全ての命令は、８ビット・ヘッダ、及び可変長本体に分解され、本体長を決定するために十分な情報がヘッダに存在している。しかし、ヘッダ情報を処理すべくハードウェア時間を与えるために先の命令の本体の前に、一つの命令のヘッダは、データ・ストリームに配置されなければならない。例えば、シーケンス．．．Ｂ０  Ｈ１Ｂ１  Ｈ２Ｂ２  Ｈ３．．．は、Ｈ１  Ｂ０  Ｈ２  Ｂ１  Ｈ３  Ｂ２．．．として符号化されなければならない。
【００４５】
ここで、図４〜図１５に関して、上記参照特許出願に開示された幾何学形状圧縮命令セットを説明する。図４は、バンドリング(bundling)・ビット（ＢＮＶ及びＢＣＶ）によって、ハフマン圧縮Δ符号化位置、並びに可能なノーマル及び／又はカラーを指定する頂点指令を示す。二つの更なるビットは、頂点置換コード（ＲＥＰ）を指定し、かつ別のビットは、この頂点を押し出しているメッシュ・バッファを制御する（ＭＢＰ）。
図５に示すように、ノーマル指令は、新たな現行ノーマルを指定し、かつ図６に示したカラー指令は、新たな現行カラーを示す。ノーマル指令及びカラー指令は、それぞれΔ値のハフマン符号化を用いる。
メッシュ・バッファ参照指令構造を図７に示す。メッシュ・バッファ参照指令構造は、１６の最近に押し出された頂点（及び関連ノーマル及び／又はカラー）のいずれかを次の頂点として参照させる（示させる）。図６に更に示すように、Ａ  ２ビット頂点置換（“ＲＥＰ”）コードもまた指定される。
図８は、５つの状態ビット、ＲＮＴ，ＲＣＴ，ＢＮＶ，ＢＣＶ，及びＣＡＰを更新するセット状態命令を示す。
図９は、３つのハフマン復号表（位置、ノーマル、またはカラー）の一つで指定されるエントリ値にエントリをセットするために用いられる、セット表指令を示す。
図１０は、幾何学形状圧縮によって直接的に制御されない更なるグラフィックス情報にイン・ラインを更新させる、パススルー（通過(passthrough) ）指令を示す。
図１１は、ビット・ストリーム内のフィールドを３２ビット・ワード境界に位置合わせさせる可変長ノップ（“ＶＮＯＰ”）指令を示す。これは、位置合わせされたフィールドを一般のＣＰＵ５２により実行時間で有効にパッチさせる。
図１２、１３、１４、及び１５は、タグ及びΔ位置データ構造、タグ及びΔノーマル・データ構造、及びタグ及びΔカラー・データ構造をそれぞれ示す。図１２及び図１５では、ｘ、ｙ、ｚの絶対値が用いられるか、またはｘ、ｙ、及びｚのデルタ値が用いられる。
勿論、他の命令セットは、三次元幾何学形状を圧縮するために代わりに用いられうる。
圧縮解除に対する圧縮に必要な時間の割合い（比率）は、重要であることができる。実際に、オフ・ライン・イメージ圧縮が圧縮解除よりもたぶん６０回以上も多くの回数を費やすことは、受容可能であるが、しかし実時間ビデオ会議に対しては、割合い（比率）は、１にすべきである。
【００４６】
有利には、幾何学形状圧縮は、この実時間要求事項を有さない。幾何学形状がオン・ザ・フライで構築されたとしても、ほとんどの幾何学形状生成技術、例えば、ＣＳＧは、幾何学形状を表示するために必要な時間よりも多い時間を要求する。また、映画に見られるような連続画像とは異なり、幾何学形状圧縮のほとんどのアプリケーションでは、圧縮三次元オブジェクトが廃棄される前に多くのシーケンス・フレームに対して表示される。三次元オブジェクトが動画化を要求するならば、動画は、モデリング・マトリックスで一般に行われる。事実ＣＤベース・ゲースに対して、オブジェクトが、カスタマ−ユーザによって数億回も圧縮解除されうることは、もっともらしいが、著作会社(authoring company) によって一度だけ圧縮される。
ある他の圧縮システムのように、幾何学形状圧縮アルゴリズムは、圧縮時間対圧縮率トレード・オフを有することができる。所与の品質ターゲット・レベルに対して、圧縮に対する許容時間が増大すると、幾何学形状圧縮システムによって達成される圧縮率は、増大する。合成圧縮三次元オブジェクトの品質に対して対応“ノブ(knob)”が存在し、品質ノブが低いと、達成される圧縮がよくなる。
審美的かつ主観的判断は、幾何学形状圧縮に適用されうる。ある三次元オブジェクトは、ノーマル及び／又は位置のターゲット量子化が多少低減されるときに悪く見えはじめ、他のオブジェクトは、大量の量子化でも視覚的に変わりえない。圧縮は、可視アーティファクト（人工産物）を時々もたらすことができるが、他の場合には、品質が必ずしも低下するとは限らないが、オブジェクトを違って見せるだけでありうる。出願人による一つの実験では、象のイメージは、イメージ・ノーマルが更に量子化されると、さらに皺のような皮膚を有して、実際により現実的に見えはじめる。一度モデルが生成されかつ圧縮されると、システム・レベルで三次元クリップ−アートとして用いられるべく、それはライブラリの中に入れることができる。
【００４７】
幾何学形状圧縮の多くの態様は、汎用であると同時に、上述した幾何学形状圧縮命令セットは、低コスト、高速ハードウェア・インプリメンテーションを許容すべくある程度適合される。（ソフトウェア圧縮解除のためにだけ設計された幾何学形状圧縮フォーマットは、幾分異なるということが理解される。）。ワンパス連続処理、限定ローカル記憶要求、タグ・ルックアップ（従来のハミング・ビット連続処理とは反対に）、及びシフト、加算の使用、及びほとんどの演算段階を達成するためのルックアップにより、説明した幾何学形状圧縮命令セットは、ハードウェア・インプリメンテーションに対して特に修正可能である。
図１６は、本圧縮解除発明が用いられうる、上記参照特許出願に記載された、幾何学形状圧縮アルゴリズム・ルーチンにおける方法段階を概説しているフローチャートである。そのようなルーチンは、メモリ８０に記憶されかつＣＰＵ６０の制御下で実行されうる（図１参照）。
段階２００では、オブジェクトは、位置、ノーマル、及びカラーに対する量子化しきい値と共に、圧縮されるべき三角形の明示グループによって表される。段階２１０では、連結性のトポロジー的分析が行われ、かつハード・エッジは、そのような情報が既に存在していないならば、ノーマル及び／又はカラーで印を付けられる。
段階２２０では、頂点横断順序及びメッシュ・バッファ参照が生成され、かつ段階２３０では、Δ位置、Δノーマル、及びΔカラーのヒストグラムズが生成される。段階２４０では、分離可変長ハフマン・タグ・コードがヒストグラムズに基づいてΔ位置、Δノーマル、及びΔカラーに対して割り当てられる。
段階２５０では、２進出力ストリームがハフマン表初期化をまず出力することによって生成され、その後で頂点が順番に横断される。適当なタグ及びΔ’ｓが全ての値に対して出力される。
【００４８】
出願人は、位置及びノーマルの圧縮を支持し、かつ全汎用三角形ストリップを生成するが、しかし全メッシュファイング(full meshifying) ・アルゴリズムをインプリメントしないウェーブフロントＯＢＪフォーマット・コンプレッサを実現した。更なる実施例は、圧縮表の微細構造更新を含む、可変精度幾何学形状を探る。現行コンプレッサは、テッセレータに既に知られた幾何学形状詳細を計算する時間を拡大し、かつ結果的に圧縮された幾何学形状を直接生成することが望ましい。しかしながら、その現在非最適状態であっても、出願人のソフトウェアは、多くの場合に約３，０００三角形／秒を圧縮することができる。
本発明は、図１のユーザ端末における、三次元圧縮幾何学形状を圧縮解除することに指図される。アタッチメント２（添付省略）は、本発明による、圧縮解除アルゴリズムの一覧表である。簡潔に、一般に、本発明による適用可能幾何学形状圧縮解除アルゴリズムは、次のように概略されうる：
（１）次の命令の残り、及び以下に続く命令の最初の８ビットをフェッチする；
（２）タグ表を用いて、あらゆる圧縮値フィールドを全精度まで拡大する；
（３Ａ）値が相対的であれば、現行値に加える；さもなくば、置換する；
（３Ｂ）メッシュ・バッファ・リファレンスであれば、古い値をアクセスする；
（３Ｃ）他の指令であれば、ハウスキーピングを行う。
（４）ノーマルであれば、全値を得るためにインデックスをＲＯＭ表を通してパスする。
（５）汎用三角形ストリップ形における値を次の段階へ出力する。
好ましい実施例では、出願人のデコンプレッサのソフトウェア実施例は、約１０，０００三角形／秒の速度で圧縮された幾何学形状をうまく圧縮解除する。本発明による圧縮解除の簡略化された全体ブロック図を図１７に示す。本発明によるデコンプレッサのハードウェア・インプリメンテーションは、数千万の三角形／秒の範囲において圧縮解除することができ、その速度は、実質的に拡張されうる。
圧縮解除を説明する前に、図１８〜図２９及び以下の表１に示すような、非圧縮及び圧縮イメージ結果を試験しかつ比較することは、有用である。図１８〜図２４は、同じベース・オブジェクト、トリケラトプスを示すが、位置及びノーマルで異なる量子化しきい値を有する。図１８は、名称Ｐ９６／Ｎ９６で示される、９６ビット位置及び９６ビット・ノーマルを用いている、最初の全浮動小数点表現である。図１９及び図２９は、それぞれ単に位置的量子化Ｐ３６／Ｎ９６及びＰ２４／Ｎ９６の効果を示し、図２１及び図２２は、ノーマル量子化、Ｐ９６／Ｎ１８及びＰ９６／Ｎ１２だけを示す。図２３及び図２４は、結合量子化、Ｐ４８／Ｎ１８及びＰ３０／Ｎ３６を示す。
図２５〜図２９は、ガリオン（Ｐ３０／Ｎ１２）、ダッジ・バイパー（Ｐ３６／Ｎ１４）、’５７シェビーの二つのビュー（Ｐ３３／Ｎ１３）、及び虫（Ｐ３９／Ｎ１５）を含む、異なるオブジェクトに対する量子化された結果だけを示す。
オブジェクトを拡大ズームすることなく、２４ビットよりも上の位置量子化は、実質的に重要な可視効果を有さない。ノーマル量子化が低減されると、表面上の鏡のような強調(specular highlights) の位置は、多少オフセットされる。しかしながら、そのような変化が、少なくとも１２ビット／ノーマル以上の、品質における低減であるということは、視覚的に自明ではない。量子化パラメータは、オブジェクトと共に写真に撮られ、そしてさもなければ、出願人でさえも、オリジナルと同じオブジェクトの最も圧縮されたバージョンとを識別することができない。
【００４９】
表１は、これらのオブジェクトに対する圧縮及び他の統計量を要約する。カラム１は、問題のオブジェクトを示し、カラム２は、Δ’ｓの数を表し、カラム３は、Δストリップ長を表わす。４番目のカラムは、頂点当たりのシステム・オーバヘッドを表わす（オーバヘッドは、位置タグ／データ、及びノーマル・タグ／データを越えた全てのものである）。“ｘｙｚ  ｑｕａｎｔ”カラムは、量子化しきい値を示し、そして６番目のカラムは、ビット数／ｘｙｚを示す。“Ｂｉｔｓ／ｔｒｉ”９番目カラムは、三角形当たりのビットを示す。
表１の結果は、括弧で示される、推定メッシュ・バッファ結果を除き、測定された実圧縮データである。実メッシュ・バッファ結果は、その出願人のプロトタイプ・ソフトウェア・コンプレッサが全メッシファイング・アルゴリズムをまだインプリメントしていないので、存在しない。（括弧で示した）推定は、メッシュ・バッファにおいて４６％ヒット率を想定する。
表１では、最右カラムは、既存の実行可能な幾何学形状フォーマットにわたり達成された圧縮率性能を示す。圧縮された幾何学形状の合計バイト計数が明白な数であるけれども、圧縮率を示すことにおいてある想定がオブジェクトの非圧縮実行可能表現についてなされなければならない。出願人は、表１に対して“最初の大きさ”(original size) のデータを算出するために浮動小数点値によって表される位置及びノーマルの両方を有する、最適化された汎用三角形ストリップを想定した。
単なる１６ビット固定点単一ストリップ表現の効果を示すために、表１は、また、ＯｐｅｎＧＬのモードに対するビット計数も示す。示したように、平均ストリップ長は、２〜３の範囲で減少した。もしあれば、市販製品は、汎用三角形ストリップをほとんど利用せず、それゆえに、表１は、可能なメモリ空間セービングをかなり控えめに表している。
【００５０】
【表１】
0003884509.tif 000003
【００５１】
【表２】
0003884509.tif 000004
【００５２】
確実に統計的変化が圧縮率に関してオブジェクト間に存在すると同時に、一般的な傾向は、それでもなお示される。量子化ノブ（Ｐ４８／Ｎ１８）の最高品質のセッティングを用いて圧縮するときに、圧縮率は、一般に約６である。率がそれに近づくと、ほとんどのオブジェクトは、可視量子化アーティファクト（人工産物）を表し始める。
三次元幾何学形状圧縮アルゴリズムは、実時間ハードウェア、またはソフトウェアで実現されうるということが上述から理解されるであろう。重要なのは、三次元レンダリング・ハードウェアが本発明による幾何学形状圧縮解除装置を含んでいるならば、アプリケーション幾何学形状は、圧縮されたフォーマットでメモリに記憶されうる。更に、データ伝送は、圧縮されたフォーマットを用いうるし、それゆえに、共有仮想現実表示環境を含む、グラフィックス加速器システムに対する有効帯域幅を改良する。合成圧縮は、主（１次）メモリにおける幾何学形状キャッシュ可能性の量を実質的に増大することができる。
図３０は、図１に示したディコンプレッサ装置１３０の詳細ブロック図である。図３０に示すように、装置１３０は、その入力が制御信号及び好ましくは３２ビットまたは６４ビット・データ・ストリームを含む圧縮解除入力先入れ先出しレジスタ（“ＦＩＦＯ”）２００を含み、それらの信号及びデータ・ストリームは、インターフェイス装置１２０（図１参照）の加速器ポート・データＦＩＦＯ（“ＡＰＤＦ”）からくるのが好ましい。インターフェイス１２０のＡＰＤＤ部分は、装置１３０に入力データ・ストリームの大きさの信号を送るコントローラを含む。ＦＩＦＯ２００は、入力ブロック状態マシン２２０及び入力ブロック２１０に出力を供給し、状態マシン２２０及び入力ブロック装置２１０は、互いに通信している。
【００５３】
ブロック２１０からの出力は、バレル・シフタ装置２４０及びハフマン表セット２３０に結合され、ハフマン・ルックアップからの出力は、状態マシン２２０に結合される。状態マシン２２０内のＯｐｃｏｄｅ（オプコード）は、ハフマン表２３０によって供給された値を処理しかつバレル・シフタ装置２４０にデータを出力する。また、状態マシン２２０は、タグ・デコーダ装置２９４に好ましくは１２ビット幅信号を出力しかつバレル・シフタ装置２４０及びノーマル・プロセッサ２７０、及び位置／カラー・プロセッサ２８０にデータを出力する、データ・パス・コントローラ２６０に出力を供給する。
バレル・シフタ装置２４０は、ノーマル・プロセッサ２７０及び位置／カラー・プロセッサ２８０に出力する。プロセッサ２７０及び２８０からの出力は、フォーマット・コンバータ２９２に供給される好ましくは４８ビット幅信号に出力マルチプレクサ装置２９０によってマルチプレクスされる。圧縮解除装置１３０は、フォーマット・コンバータ２９２に送られる、（ノーマルに対して）３２ビットまたは４８ビットのいずれかと並列でタグ・デコーダ２９４に送られる好ましくは１２ビット・タグを生成する。これらのデータ・ストリームは、フォーマット・コンバータ２９２への出力を生成する命令を供給する。好ましくは３２ビット・リードバック(read-back) 経路は、装置の状態をリードバックするために用いられる。
下記の表２は、好ましい実施例における圧縮解除装置１３０を実現するために用いるインターフェイス信号を示す：
【００５４】
【表３】
0003884509.tif 000005
【００５５】
下記の表３は、好ましい実施例における装置１３０によって供給される出力データ・フォーマットを示す。ここで説明するように、頂点、メッシュ・バッファ・リファレンス、及びパススルー命令は、圧縮解除装置１３０からのトランザクションを生成する。頂点及びメッシュ・バッファ・リファレンス命令は、フォーマット・コンバータにデータを送り、かつそれぞれは、コンポーネント・データを後続する、現行頂点に対する頂点置換方針を示しているヘッダを生成する。これらの命令のそれぞれは、位置データを常に生成し、かつ状態レジスタの値により、カラーまたはノーマル・データを含みうる。ノーマル・コンポーネントの３つの全ては、並列に送られ、各位置及びカラー・コンポーネントは、別々に送られるのが好ましい。パススルー命令は、好ましくは３２ビットのデータを収集（コレクション）バッファに送る。
【００５６】
【表４】
0003884509.tif 000006
【００５７】
図３１は、図３０に示した入力ブロック２１０の詳細ブロック図である。好ましくは、６４ビット入力レジスタ３００は、レジスタ３００に装填されるときに３２ビットまたは６４ビットで、インターフェイス１３０のＡＰＤＦ部分からデータを受け取る。レジスタ３００は、その出力がレジスタ３３０を通ってマージ装置３４０にパスする第１のバレル・シフタ３２０にマルチプレクサ３１０を介して一度に好ましくは３２ビットを出力する。マージ装置３４０からの６４ビット出力は、データ・レジスタ３５０に入力され、その出力の一部は、第２のバレル・シフタ３６０への入力としてリターンされる。第２のバレル・シフタ３６０からの出力は、レジスタ３７０を通してパスされかつマージ装置３４０へも入力される。第１のバレル・シフタ３２０は、第２のバレル・シフタ３６０を通してデータ・レジスタ３５０からリサイクルされるビット位置合わせデータ・ストリームの末端にデータを位置合わせする。第２のバレル・シフタ３６０は、データ・レジスタ３５０から使用済みビットをシフト・オフする。
図３２は、図３０に示したバレル・シフタ装置２４０の詳細ブロック図である。概観で、バレル・シフタ装置２４０は、可変長位置、カラー、及びノーマル・インデックス・コンポーネントをそれらの固定点精度まで拡張する。装置２１０及び／又は２２０から装置２４０へのデータは、その出力が画定オプコードとして示されるレジスタ４００及び／又はデータ装置４１０、４２０、４３０、４４０、４５０、及び４６０に入力され、マルチプレクサ装置４７０に入力される。
【００５８】
マルチプレクサ装置４７０では、入力Ａは、頂点命令のＸコンポーネントに用いられ、入力Ｂは、セット・ノーマル命令及びセット・カラー命令の第１のコンポーネントに用いられ、かつ入力Ｃは、頂点及びセット・カラー命令の残っているコンポーネントに用いられる。装置４８０は、ｔａｇ＿ｌｅｎデータを受け取りかつ、その出力が次いでｄａｔａ＿ｌｅｎデータを受け取るべく結合されるバレル・シフタ・ライト・レジスタ５００に入力される、レジスタ４９０へ出力すべく結合されたバレル・シフタ・レフト・レジスタ４８０を更に含む。レジスタ５００は、シフトｄａｔａを受け取るべく結合されかつその出力が、ｖ＿ｄａｔａを出力する、レジスタ５２０に結合されるマスク装置５１０に出力する。データ・ブロック４６０の出力は、その出力が、ｐｔ＿ｄａｔａを出力する、第２のレジスタ５４０に結合されるレジスタ５３０に結合される。
ハフマン表２３０（図３０参照）内の適切な表は、ｔａｇ＿ｌｅｎ、ｄａｔａ＿ｌｅｎ、及びシフトを装置４８０、５００及び５１０にそれぞれ供給する。バレル・シフタ・レフト装置４８０は、０から６ビットだけ左に入力データをシフトし（ｔａｇ＿ｌｅｎ）、それゆえにハフマン・タグをシフト・オフする。対照的、バレル・シフタ・ライト・レジスタ５００は、０から１６ビットだけ右にデータをシフトし（１６−ｄａｔａ＿ｌｅｎ）、サインがデータを拡張し、それゆえに、データをその全サイズにさせる。マスク装置５１０は、正しい量子化レベルにデータをクランプするために下位“シフト”ビットをマスク・オフする。
図３３は、図３０に示した位置／カラー・プロセッサ装置２８０のより詳細なブロック図を示す。プロセッサ装置２８０は、最終位置及びカラー・コンポーネント値を生成する。図３０及び図３２に示したように、プロセッサ装置２８０は、バレル・シフタ装置２４０、特にその中のマスク装置５１０、から好ましくは１６ビット値（ｖ＿ｄａｔａ）を受け取る。
【００５９】
ハフマン表２３０からのａｂｓ＿ｒｅｌビットが相対的(relative)にセットされたならば、入力データは、結合器装置６００によってに適切な現行記憶データに加えられる。新しい値は、マルチプレクサ６１０を通過し、かつレジスタ６２０に戻り記憶され、かつ図３０に示すように、出力マルチプレクサ２９０に沿って送られる。しかし、ａｂｓ＿ｒｅｌビットが絶対的(absolute)に設定されたならば、入力データは、加算器６００をバイパスし、レジスタ６２０にラッチされ、かつまた出力マルチプレクサ２９０に送り出される。
図３３に示すように、位置／カラー・プロセッサ装置２８０は、レジスタ６２０への入力を受け取るべく結合される位置／カラー・メッシュ・バッファ６３０を更に含む。メッシュ・バッファ６３０からの出力は、その出力がｘ、ｙ、ｚ、ｒ、ｇ、ｂ及びαの現行値(current values)を反映する、集合的に６４０で示された、マルチプレクサ・ゲートに結合される。集合的に６５０として示された、レジスタ・セットは、その出力が加算器６００に結合されるマルチプレクサ６６０の入力にこれらの現行値を供給する。プロセッサ装置２８０は、バレル・シフタ装置２４０からのｐｔ＿ｄａｔａを受取りかつ出力するレジスタ６７０を更に含む。
【００６０】
図３０に示すように、ノーマル・プロセッサ装置２７０は、また、出力マルチプレクサ２９０にデータを出力する。図３４は、ノーマル・プロセッサ装置２７０を含んでいるサブユニットを詳細に示す。図３０及び図３２に示したように、ノーマル・プロセッサ装置２７０は、３つの分離コンポーネント、即ち、セクスタント／オクタント、ｕ及びｖ、またはバレル・シフタ装置２４０のマスク装置５１０からの符号化されたΔｕ及びΔｖコンポーネント、として１８ビット・ノーマル・インデックスを受取る。値がΔ値（相対的）であるならば、Δｕ及びΔｖは、対応加算器７１０によって現行ｕ及びｖ値に加えられる。中間値は、記憶されかつまたデコーダ−フォールド−ロム(decoder-fold-rom)装置２７２（図３５参照）に関連付けられたフォールド(fold)装置８００にパスされる。
図３４に示すように、ノーマル・プロセッサ装置２７０は、対応オクタント、セクスタント、ｕ及びｖ値、ｃｕｒｒ＿ｏｃｔ、ｃｕｒｒ＿ｓｅｘｔ、ｃｕｒｒ＿ｕ、及びｃｕｒｒ＿ｖ値を保持するレジスタ７１２、７１４、７１６、７１８、７２０、７２２、７２４、７２６を更に含む。また、装置２７０に存在するのは、マルチプレクサ７４０、７４２、７４４、７４６、７４８、７５０、７５２、７５４、７５６、７５８及び７６０、１の補数装置７７０、７７２、対応ｖ、ｕ及びｕｖ情報を保持するラッチ−フリップフロップ装置７８０、７８２、７８４、更なる加算器７９０、７９２、及びｃｕｒｒ＿ｎｏｒｍａｌ入力コンポーネントを受け取るべく結合されたノーマル・メッシュ・バッファ７９４である。
図３４及び３５に関して、絶対基準(absolute reference)に対して、ｕ及びｖ値は、フォールド装置８００に直接パスされる。インデックスのオクタント及びセクスタント部分は、装置２７２内の、デコーダ８１０に送られる。デコーダ８１０は、（定数を選択する）マルチプレクサ８２０、並びに、コンポーネントを再順序付けし、かつ（２の補数装置８５０、８５２、８５４を用いて）サインを逆にするマルチプレクサ８４０、８４２、８４４、８６０、８６２、８６４を制御する。
【００６１】
フォールド装置８００は、ノーマル・ルックアップ表ＲＯＭ８３０へのアドレスを計算するために、装置２７０からの、ノーマル・インデックスのｕ及びｖコンポーネントを用いる。装置２７０からの、オクタント及びセクスタント・フィールドは、ＲＯＭルックアップ表８３０から出力されるコンポーネントのサイン及び順番を決定するデコーダ８１０を駆動する。また、デコーダ８１０は、ノーマルＲＯＭルックアップ表８３０に含まれない特別の場合のノーマルを処理する。
図３６は、図３３及び／又は図３４に示したような、メッシュ・バッファへのインターフェイスを示す。好ましい実施例では、メッシュ・バッファ７９４は、レジスタ・ファイル及び現行位置へのポインタとしてインプリメントされる。データは、現行位置ポインタの位置におけるメッシュ・バッファＦＩＦＯに入力される。しかしながら、１６の位置のいずれかへのランダム・アクセスは、このポインタをインデックシング・オフ(indexing off)することによってＦＩＦＯからデータを読み出すときに許容される：アドレス＝（ｃｕｒｒ＿ｌｏｃ＿ｐｔｒ−インデックス）ｍｏｄ１６。
図３７は、ホフマン表、例えば、図３０の表２３０へのインターフェイスを示す。ホフマン表は、圧縮データに先行しているホフマン・タグを復号するために用いる。３つのホフマン表が用いられる：各表が６４のエントリを保持しているのが好ましく、位置に対して一つ、カラーに対して一つ、ノーマル・データに対して一つ。
【００６２】
図３８は、ホフマン表における位置及びカラー・データのエントリに対して好ましいフォーマットを示し、図３９は、ノーマル表エントリに対する好ましいフォーマットを示す。圧縮データ・ストリームにホフマン表を装填するための命令フォーマットは、後で説明する。
複数の命令は、図３０に示した、フォーマット変換器２９２に対するデータを生成し、かつフォーマット変換器がデータを正確に処理できるように、適当なタグがこのデータに対して生成されなければならない。以下に示す、表４は、異なるデータ・コンポーネントに対して生成されるタグを示す。二つのタグを示すコンポーネントは、ランチ(launch)・ビットを設定しうるし、第２のタグは、設定されたランチ・ビットを有する値を示す。
【００６３】
【表５】
0003884509.tif 000007
【００６４】
入力ブロック状態マシン２２０（図３０参照）は、圧縮解除装置の処理状態に関する情報を保持する６ビット状態レジスタを含むのが好ましい。好ましい実施例では、次の状態ビットが定義される：
ビット５：  ｔｅｘ−カラーの代わりのテキスチャ値
ビット４：  ｒｎｔ−頂点当たりの複製（再現）ノーマル
ビット３：  ｒｃｔ−頂点当たりの複製（再現）カラー
ビット２：  ｂｎｖ−頂点にバンドルされたノーマル
ビット１：  ｂｃｖ−頂点にバンドルされたカラー
ビット０：  ｃａｐ−アルファ（α）を含むカラー
【００６５】
位置／カラー・プロセッサ装置２８０（図３０及び図３３参照）は、現行位置コンポーネント、Ｘ、Ｙ、及びＺを含み、かつ頂点命令によってのみ更新される、３つの１６ビット・レジスタ、ｃｕｒｒ＿ｘ、ｃｕｒｒ＿ｙ、及びｃｕｒｒ＿ｚを含むのが好ましい。
【００６６】
ノーマル・プロセッサ装置２７０（図３０及び図３４）は、現行ノーマルを含む、３つの６ビット・レジスタ、ｃｕｒｒ＿ｏｃｔ、ｃｕｒｒ＿ｓｅｘｔ、ｃｕｒｒ＿ｕ、及びｃｕｒｒ＿ｖを含むのが好ましい。第１のレジスタは、３ビットセクスタット及びオクタント・フィールドを保持し、かつ残り２つのレジスタは、ノーマルに対するｕ及びｖ座標を含む。これらの値は、セット・ノーマル命令を用いて書き込まれるか、またはそれらは、ｂｎｖビットが状態レジスタに設定されるならば頂点命令によって更新される。
位置／カラー・プロセッサ２８０は、現行カラー・コンポーネント、赤、緑、青及びアルファ（α）を含む、４つの１６ビット・レジスタ、ｃｕｒｒ＿ｒ、ｃｕｒｒ＿ｇ、ｃｕｒｒ＿ｂ、ｃｕｒｒ＿ａを更に含むのが好ましい。これらのコンポーネントは、ｓｅ５ｔカラー命令を用いて設定されるか、またはそれらは、ｂｃｖビットが状態レジスタに設定されるならば頂点命令によって更新される。好ましい実施例では、アルファは、キャップ・ビットが状態レジスタに設定されるときにだけ有効である。テスト・ビットは、赤及び緑だけが有効である場合のような、テキスチャ・コンポーネントを処理するときに設定される。
【００６７】
ここで、本発明による圧縮解除をインプリメントする命令セットを説明する。図４０は、頂点命令フォーマット、頂点を表わすために可変長ハフマン・符号化を用いる命令を示す。位置情報は、この命令に常に存在する。
0003884509.tif 000008
【００６８】
図４０を参照すると、位置データは、可変長ハフマン・タグ（０から６ビット）に続いて、Δ値または絶対値のいずれかである、Ｘ、Ｙ、及びＺコンポーネントについて同じ長さの３つのデータ・フィールドを含む。位置ハフマン表におけるエントリに対するｄａｔａ＿ｌｅｎフィールドは、Ｘ、Ｙ、及びＺフィールドのそれぞれの長さを与え、ｔａｇ＿ｌｅｎエントリは、タグの長さを与え、ａｂｓ＿ｒｅｌエントリは、データが絶対データであるかまたは先の頂点に相関するかを告げる。ハフマン表からのシフト・エントリは、データに対する量子化レベル（後続しているゼロの数）を与える。
ｂｎｖビットが状態レジスタに設定されたならば、ノーマルが含まれる。符号化されたノーマルは、Δｕ及びΔｖに対する二つの可変長データ・フィールド、またはｕ及びｖに対する二つの可変長フィールドを後続するセクスタント及びオクタント（６ビット）に対する固定長フィールドのいずれかを後続するハフマン・タグを有する。前者の符号化は、ノーマルのデルタ符号化に対してであり、後者の符号化は、絶対符号化に対してである。ノーマル・ハフマン表からのｄａｔａ＿ｌｅｎ、ｔａｇ＿ｌｅｎ、ａｂｓ＿ｒｅｌ、及びシフト・フィールドは、位置表からのエントリと同様に用いられる。
【００６９】
図４１は、頂点コンポーネント・データ・フォーマットを示す。状態レジスタのｂｃｖビットがセットされたならば、カラーは、頂点を伴って含まれる。カラーは、３つまたは４つのフィールドを用いて位置に類似して符号化されるが、しかしどのようにフィールドが用いられるかは、タグ表によって決定される。絶対的であるとタグ付けされたならば、ｘ、ｙ、ｚ、ｒ、ｇ、ｒデータが用いられる。絶対ノーマルは、セクスタント及びオクタント・フィールドで用いられる。しかしながら、タグ表が相対的を示すならば、デルタ・ノーマルが用いられ、かつそれは、緯度及び経度データを送るために十分である（例えば、ここでｕ及びｖとしても参照される、θ及びΦ）。
図４１を更に参照すると、ハフマン・タグは、Ｒ、Ｇ、及びＢに対して３つの同長フィールドにより後続される。状態レジスタのキャップ・ビットは、αに対する追加フィールドが含まれるか否かということを示す。カラー・ハフマン表からのｄａｔａ＿ｌｅｎ、ｔａｇ＿ｌｅｎ、ａｂｓ＿ｒｅｌ、及びシフト・フィールドは、位置及びノーマル表からのエントリに対するのと同様に用いられる。
【００７０】
頂点命令セットの状態は、次に示すようである：
0003884509.tif 000009
0003884509.tif 000010
【００７１】
図４２は、セット・ノーマル命令に対するフォーマットを示す。セット・ノー
マル命令は、現行ノーマル・レジスタの値を設定する。ノーマル・データは、ここの、示された、頂点命令におけるノーマル・データと同様に符号化される。セット・ノーマル命令の状態は、次の通りである：
0003884509.tif 000011
【００７２】
図４３は、現行カラー・レジスタの値を設定する命令である、セット・カラー命令を示す。頂点命令におけるカラー・データの符号化は、カラー・データの符号化に類似する。セット・カラー命令の状態は、次のようである：
0003884509.tif 000012
【００７３】
図４４は、メッシュ・バッファ基準命令に対する好ましいフォーマットである。この命令は、メッシュ・バッファにおけるエントリからのデータを次の頂点としてフォーマット変換器へ送り出させる。図４４に関して、インデックスは、送るべきメッシュ・バッファからのエントリを示す。メッシュ・バッファにおける最新のエントリは、インデックス０を有し、かつ最古のものは、インデックス１５を有する。ＲＥＰ、頂点命令に対する上述した置換ポリシーは、メッシュ・バッファ基準命令に対して用いられたものと同じである。メッシュ・バッファ基準命令に対する状態は、次の通りである：
0003884509.tif 000013
【００７４】
図４５は、ビットを圧縮解除装置状態レジスタに設定するセット状態命令を示す。セット状態命令に対する状態は、次の通りである：
１．次のｏｐｃｏｄｅをラッチする；１１ビットだけバレル・シフタ２をシフトする。
２．マージする；命令を分枝する
【００７５】
図４６は、ハフマン表エントリを設定するセット表命令を示す。表選択は、次の通り：
００−位置表
０１−カラー表
１０−ノーマル表
１１−未画定
【００７６】
タグ長は、アドレスから導出される。エントリ・フィールドの９ビットは、ハフマン表エントリの絶対／相対ビット、データ長、及びシフト量フィールドに対応する。（ハフマン表エントリの好ましいフォーマットは、前述した。）セット表命令の状態は、次の通りである：
0003884509.tif 000014
表５は、好ましいハフマン表充填コードを示す。
【００７７】
【表６】
0003884509.tif 000015
【００７８】
図４７は、パススルー・データを圧縮データ・ストリームにおいて符号化させるパススルー命令を示す。命令の長さは、６４ビットであるのが好ましい。６４ビット・バウンダリーに後続パススルー命令を位置合わせすることは、符号化されたストリームにおけるパススルー・データのパッチングを許容する。パススルー命令に対する状態は、次の通りである：
0003884509.tif 000016
【００７９】
図４７は、データ・ストリームにおける０ビットの変数を符号化する、可変長ＮＯＰ（“ＶＮＯＰ”）命令を示す。図４７に示した５ビット・カウントは、その後に続く０ビットの数を指定する。この命令は、データ・ストリームの開始に暗黙的に用いられる。この命令は、また、データ・ストリームを３２ビットまたは６４ビット・バウンダリー、または後のパッチングのために、符号化領域にパッドする（埋め込む）ためにも用いられうる。この命令の状態は、次の通り：
0003884509.tif 000017
【００８０】
図４９は、その状態が次に示すような、スキップ８命令を示す：
0003884509.tif 000018
【００８１】
圧縮解除システムにおける単一点でデータ・ストリームを圧縮解除しないで装置間の帯域幅要求を低減することが有利でありうるということが理解される。本発明は、並列に処理されうる所与の数のデータ・ワードの到着を助言する追加指令を供給することによってインプリメントを供給することによってデータ・ストリームの並列圧縮解除を供給することができる。
本発明は、マーク・ビットの存在によってそのような並列の機会の存在を認識することができ、かつ並列圧縮解除に対して、そこでの状態数(stated number) のデータ・ワードの発生がシステム内の他のプロセッサにシャトルされる。更に、並列処理に対して権利が無い次のデータに到着すべくデータ・ストリームにおける所与の数のワードを先にジャンプさせることを許容できる。
また、本発明は、圧縮解除された三次元オブジェクトを見ることにおいてあらゆる突然の知覚空隙を取り除くためにモーフィング・ケイパビリティを供給することもできる。圧縮解除されたデータ・ストリーム内では、実際に存在するかまたは先に圧縮解除された頂点の線形または他の補間（内挿）として頂点を指定することが可能である。例えば、三次元オブジェクトが虎であると想定する。遠距離では、虎の口には歯が存在しないが、近距離では、歯が存在する。本発明は、虎との距離が短くなると、歯が成長し、歯無し虎と歯有り虎との間の突然の変化のシーンがないようなシームレス・トランザクションを提供することができる。変更及び変形は、特許請求の範囲によって画定されるような本発明の対象及び精神から逸脱することなく開示された実施例に対してなされうる。
【００８２】
【発明の効果】
本発明の方法は、可変長フィールドのデータ・ストリームを圧縮解除する方法であり、該データ・ストリームが該フィールドの圧縮解除を三次元オブジェクトの非圧縮表面特性にガイドする、オプ・コード・ビット及び／又はタグ・ビットを含んでいる、方法であって、（ａ）フィールド型をデータ・ストリームから検出し、そのような検出をイネーブルするデータは、先行するが該データ・ストリーム内でシーケンシャルにすぐに先行する必要はない、（ｂ）フィールド長及び／又はフィールド正規化をデータ・ストリームから検出し、そのような検出をイネーブルするデータは、先行するが該データ・ストリーム内でシーケンシャルにすぐに先行する必要はない、（ｃ）段階（ａ）及び段階（ｂ）の少なくとも一つから得られた情報を用いて、データ・ストリームからビット位置合わせされたフィールドを抽出し、（ｄ）最初の数値スケールに抽出したビット位置合わせされたフィールドを必要に応じて再正規化し、（ｅ）圧縮解除された表面記述データを出力する段階を具備し、データは、オプションで汎用三角形ストリップ・フォーマットであるので、出力データが描画命令として直接レンダリング・ハードウェアにわたされるように圧縮された三次元幾何学形状を圧縮解除することができる。
また、本発明のシステムは、オプ・コード・ビット及び／又はタグ・ビットを含み、その表面が表面特性を画定する三次元オブジェクトを表している圧縮データを含み、そのフィールドが長さにおいて変化することができる、データ・ストリームを圧縮解除する、中央処理装置（ＣＰＵ）及び当該ＣＰＵに結合されたメモリを含んでいるコンピュータ・システムに使用可能な、システムであって、データ・ストリームを受け取りかつすぐ後に続くフィールドのデータ・ストリーム・フィールド情報における先行しているが、すぐにシーケンシャルに先行していることを必要としない、フィールドから検出すべくプログラムされた検出器装置と、フィールド情報は、フィールド型及びフィールド長及び／又はフィールド正規化を含んでおり、検出器装置によって検出された少なくともあるデータを受け取りかつデータ・ストリームからビット位置合わせされたフィールドを抽出すべくプログラムされた抽出器装置とを備えているので、出力データが描画命令として直接レンダリング・ハードウェアにわたされるように圧縮された三次元幾何学形状を圧縮解除することができる。
【図面の簡単な説明】
【図１】本発明による、受信端で、圧縮された三次元幾何学形状がその上で圧縮解除のために送信されうる、一般化されたネットワーク・システムを示す図である。
【図２】一般化された三角形状メッシュ・データ構造、及び表面幾何学形状の一般化されたメッシュ・バッファ表現を示す図である。
【図３】本発明による、表ルック−アップ・サイズにおける４８の低減方法を供給すべく用いられる、単位球における６方向単一ビット及び８方向オクタント（八分儀）対称を示す図である。
【図４】本発明による、幾何学形状圧縮命令セットにおける頂点指令を示す図である。
【図５】本発明による、幾何学形状圧縮命令セットにおけるノーマル指令を示す図である。
【図６】本発明による、幾何学形状圧縮命令セットにおけるカラー指令を示す図である。
【図７】本発明による、幾何学形状圧縮命令セットにおけるメッシュ・バッファ参照指令を示す図である。
【図８】本発明による、幾何学形状圧縮命令セットにおけるセット状態指令を示す図である。
【図９】本発明による、幾何学形状圧縮命令セットにおけるセットテーブル指令命令を示す図である。
【図１０】本発明による、幾何学形状圧縮命令セットにおけるパス・スルー指令命令を示す図である。
【図１１】本発明による、幾何学形状圧縮命令セットにおける可変長ノー・オペレーション（ｎｏ−ｏｐ）指令命令を示す図である。
【図１２】本発明による、タグ及びΔ−位置データ構造を示す図である。
【図１３】本発明による、代替のタグ及びΔ−ノーマル・データ構造を示す図である。
【図１４】本発明による、別の代替のタグ及びΔ−ノーマル・データ構造を示す図である。
【図１５】本発明による、タグ及びΔ−カラー・データ構造を示す図である。
【図１６】本発明による、幾何学形状圧縮アルゴリズムにおける方法ステップスのフローチャートである。
【図１７】本発明による、デコンプレッサ・ハードウェアの簡略ブロック図である。
【図１８】異なる条件下で圧縮されたオブジェクトをディスプレー上に表示した中間調画像を示す写真である。
【図１９】異なる条件下で圧縮されたオブジェクトをディスプレー上に表示した中間調画像を示す写真である。
【図２０】異なる条件下で圧縮されたオブジェクトをディスプレー上に表示した中間調画像を示す写真である。
【図２１】異なる条件下で圧縮されたオブジェクトをディスプレー上に表示した中間調画像を示す写真である。
【図２２】異なる条件下で圧縮されたオブジェクトをディスプレー上に表示した中間調画像を示す写真である。
【図２３】異なる条件下で圧縮されたオブジェクトをディスプレー上に表示した中間調画像を示す写真である。
【図２４】異なる条件下で圧縮されたオブジェクトをディスプレー上に表示した中間調画像を示す写真である。
【図２５】異なる条件下で圧縮されたオブジェクトをディスプレー上に表示した中間調画像を示す写真である。
【図２６】異なる条件下で圧縮されたオブジェクトをディスプレー上に表示した中間調画像を示す写真である。
【図２７】異なる条件下で圧縮されたオブジェクトをディスプレー上に表示した中間調画像を示す写真である。
【図２８】異なる条件下で圧縮されたオブジェクトをディスプレー上に表示した中間調画像を示す写真である。
【図２９】異なる条件下で圧縮されたオブジェクトをディスプレー上に表示した中間調画像を示す写真である。
【図３０】本発明による、デコンプレッサ装置の詳細全体ブロック図である。
【図３１】図３０に示した入力ブロック図の詳細全体ブロック図である。
【図３２】図３０に示したバレル・シフタ装置の詳細ブロック図である。
【図３３】図３０に示した位置／カラー・プロセッサ装置の詳細ブロック図である。
【図３４】図３０に示したノーマル・プロセッサ装置の詳細ブロック図である。
【図３５】図３４のノーマル・プロセッサ装置に関連付けられたデコーダ、フォールド、及びＲＯＭルック−アップ・コンポーネントを示している詳細ブロック図である。
【図３６】図３３及び／又は図３４に示したような、メッシュ・バッファへのインターフェイスを示しているブロック図である。
【図３７】本発明による、ハフマン表へのインターフェイスを示す図である。
【図３８】本発明による、ハフマン表データのエントリに対する好ましいフォーマットを示す図である。
【図３９】本発明による、ハフマン表データのエントリに対する好ましいフォーマットを示す図である。
【図４０】本発明による、頂点命令を示す図である。
【図４１】本発明による、頂点コンポーネント・データ・フォーマットを示す図である。
【図４２】本発明による、セット・ノーマル指令に対するフォーマットを示す図である。
【図４３】本発明による、セット・カラー指令を示す図である。
【図４４】本発明による、メッシュ・バッファ参照指令を示す図である。
【図４５】本発明による、セット状態指令を示す図である。
【図４６】本発明による、セット・テーブル指令を示す図である。
【図４７】本発明による、パススルー指令を示す図である。
【図４８】本発明による、可変長ＮＯＰ指令を示す図である。
【図４９】本発明による、スキップ８指令を示す図である。
【符号の説明】
１０  三次元グラフィックス発生源
２０  サーバ
３０  ネットワーク
４０  デコーダ
５０  中央処理装置
６０  ＣＰＵ
７０  関連主メモリ、ディスク・レイアウト装置
８０  メッシュ・バッファ、記憶ディスク装置
９０  メモリ部分
１００  ＲＯＭ
１１０、１２０  ネットワーク・インターフェイス
１３０  三次元グラフィックス圧縮解除装置
１４０  三次元グラフィックス・レンダラー
１５０  中央処理システム
１６０  ＣＰＵ
１７０  メモリ
１８０  メモリ部分
１９０  ＲＯＭ
２００  ディスプレイ
【図１】
0003884509.tif 000019
【図２】
0003884509.tif 000020
【図３】
0003884509.tif 000021
【図４】
0003884509.tif 000022
【図５】
0003884509.tif 000023
【図６】
0003884509.tif 000024
【図７】
0003884509.tif 000025
【図８】
0003884509.tif 000026
【図９】
0003884509.tif 000027
【図１０】
0003884509.tif 000028
【図１１】
0003884509.tif 000029
【図１２】
0003884509.tif 000030
【図１３】
0003884509.tif 000031
【図１４】
0003884509.tif 000032
【図１５】
0003884509.tif 000033
【図１６】
0003884509.tif 000034
【図１７】
0003884509.tif 000035
【図１８】
0003884509.tif 000036
【図１９】
0003884509.tif 000037
【図２０】
0003884509.tif 000038
【図２１】
0003884509.tif 000039
【図２２】
0003884509.tif 000040
【図２３】
0003884509.tif 000041
【図２４】
0003884509.tif 000042
【図２５】
0003884509.tif 000043
【図２６】
0003884509.tif 000044
【図２７】
0003884509.tif 000045
【図２８】
0003884509.tif 000046
【図２９】
0003884509.tif 000047
【図３０】
0003884509.tif 000048
【図３１】
0003884509.tif 000049
【図３２】
0003884509.tif 000050
【図３３】
0003884509.tif 000051
【図３４】
0003884509.tif 000052
【図３５】
0003884509.tif 000053
【図３６】
0003884509.tif 000054
【図３７】
0003884509.tif 000055
【図３８】
0003884509.tif 000056
【図３９】
0003884509.tif 000057
【図４０】
0003884509.tif 000058
【図４１】
0003884509.tif 000059
【図４２】
0003884509.tif 000060
【図４３】
0003884509.tif 000061
【図４４】
0003884509.tif 000062
【図４５】
0003884509.tif 000063
【図４６】
0003884509.tif 000064
【図４７】
0003884509.tif 000065
【図４８】
0003884509.tif 000066
【図４９】
0003884509.tif 000067