JPH09326041A - 圧縮された幾何学形状三次元グラフィックス・データの圧縮解除のための方法及び装置 - Google Patents

Abstract

(57)【要約】 （修正有） 【課題】 描画命令として直接形成レンダリングハード
ウェアに渡されるようにする。 【解決手段】 データストリームからフィールド型を検
出する際、検出をイネーブルするデータを先行させ、フ
ィールド長又はフィールド正規化をデータストリームか
ら検出する際、検出をイネーブルするデータを先行さ
せ、データストリームからビット位置合せされたフィー
ルドを抽出し、最初の数値スケールに抽出したビット位
置合せされたフィールドを必要に応じ再正規化し、圧縮
解除された表面記述データを出力することにより、可変
長フィールドのデータストリームを圧縮解除する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、一般にグラフィックス
・データを圧縮解除することに関し、特に圧縮された三
次元幾何学データを圧縮解除する方法及び装置に関す
る。

【０００２】

【従来の技術】最新の三次元コンピュータ・グラフィッ
クスは、種々のグラフィック表現技術を用いて、三次元
オブジェクトを記述するために幾何学形状を広範囲に渡
って用いる。コンピュータ・グラフィックスは、コンピ
ュータ支援設計（“ＣＡＤ”）プログラムから仮想現実
感（バーチャル・リアリティ）ビデオ・ゲームの範囲に
わたるアプリケーションにおいて広い使用を見出す。オ
ブジェクトの複雑で滑らかな表面は、トリム型非均等有
理スプライン(trimmed non-uniform rational splines)
のような高レベル抽象化によって簡潔的に表わすことが
でき、かつしばしば詳細な表面幾何学形状は、テクスチ
ャ・マップを用いて表現できる。しかし、より現実感を
付加することは、、通常、三角形の、生幾何学形状(raw
geometry)を要求する。位置、カラー（色彩）、及びこ
れら三角形の通常の構成要素は、浮動小数点数として一
般に表現され、かつ孤立した三角形(isolated triangl
e) を記述することは、記憶空間の１００バイト以上を
要求することができる。理解できるように、例えば、コ
ンピュータ・ハード・ディスクまたはコンパクト・ディ
スク・リード・オンリ・メモリ（“ＣＤ−ＲＯＭ”）上
に記憶されるために三次元コンピュータ・グラフィック
ス・オブジェクトに対して実質的な空間が必要である。
同様に、例えば、ネットワーク、またはディスクから主
メモリにわたり、伝送されるためにそのようなオブジェ
クトに対してかなりの時間が必要である。

【０００３】幾何学形状圧縮は、一般的な空間−時間ト
レード・オフであり、かつメモリ／相互接続階層の全て
のレベルで利点を供給する。同様なシステム問題が二次
元画素イメージの記憶及び送信に対して存在する。種々
の損失が大きくかつ無損失圧縮及び圧縮解除技術が、記
憶空間及び送信時間における合成減少を有して、二次元
画素イメージに対して開発されている。残念ながら、従
来技術は、多角形（多辺形）低減技法を越えた、三次元
幾何学形状に適切な圧縮／圧縮解除技術を含まない。し
かしながら、１９９４年のプリンストン大学におけるシ
ョン・ダンスキン(John Danskin)による「Ｘグラフィッ
クス・プロトコルの圧縮」(Compressingthe X Graphics
Protocol) という題名の博士論文(Ph.D. thesis)は、
二次元幾何学形状に対する圧縮を記載している。適切な
圧縮は、コンピュータ・システムの高速主メモリに、キ
ャッシュ（格納）、または記憶することができる幾何学
形状の量をかなり増大することができる。分散型ネット
ワーク・アプリケーションでは、圧縮は、送信時間をか
なり低減することによって、共有バーチャル・リアリテ
ィ（“ＶＲ”）・ディスプレイ環境をインプリメント可
能にすることを支援できる。ほとんどの主要な機械計算
機援用設計（“ＭＣＡＤ”）ソフトウェア・パッケー
ジ、及び多くの動画モデリング・パッケージは、幾何学
形状を構成しかつ表現するために構成ソリッド幾何学形
状（“ＣＳＧ”）及び自由な形式のＮＵＲＢＳを用い
る。そのような技法を用いて、滑らかな表面の領域は、
トリム型ポリノミアル表面を結果として得られる高いレ
ベルに表現される。ハードウェア・レンダリングに対し
て、これらの表面は、一般に、レンダリング・ハードウ
ェアへの送信の前にソフトウェアを用いて三角形にプリ
テッセレートされる(pre-tessellated) 。そのようなソ
フトウェア・プリテッセレーション(pre-tesselation)
は、ハードウェアＮＵＲＢＳ(non-uniform rational B-
spline) レンダリングのある形式を支持するハードウェ
ア上でも行われる。しかしながら、ＮＵＲＢＳ幾何学形
状表現に関連付けられる多くの利点は、実時間レンダリ
ング以外のタスクに対してである。これらの非レンダリ
ング・タスクは、マシニング、インターチェンジ、及び
乱流のシミュレーションのような物理的解析に対する表
現を含む。ＮＵＲＢＳに対してトリミング曲線を正確に
表現することは、非常にデータを集中し、かつ圧縮技術
として、トリム型ＮＵＲＢＳは、少なくとも一般的なレ
ンダリング・テッセレーション密度ではプリテッセレー
トされた三角形よりも更にコンパクトでありえない。そ
して、全てのオブジェクトがＮＵＲＢＳによってコンパ
クトに表現されない（一部のオブジェクトがＮＵＲＢＳ
によってコンパクトに表現される）。自動車フードやジ
ェット・タービン・ブレードのような多くの機械的オブ
ジェクトは、ＮＵＲＢＳ表現が有利でありうる大きな、
滑らかな領域を有するけれども、多くのオブジェクト
は、そのような領域をもっておらずかつそのような表現
に向いていない。それゆえに、ＮＵＲＢＳがオブジェク
トをモデル化することにおいて多くのアプリケーション
を有すると同時に、圧縮された三角形は、アプリケーシ
ョン・オブジェクトの多くのクラスに対して遙にコンパ
クトである。

【０００４】フォト・リアリスティック・バッチ・レン
ダリングは、微細な幾何学形状の詳細をコンパクトに表
わすためにテキスチャ・マップ技術の広範囲な使用を長
くした。そのような技術は、カラー・テキスチャ・マッ
プ、通常のバンプ・マップ、及び変位マップを含むこと
ができる。テキスチャ・マッピングは、例えば、空の
雲、遠くの建物のような、遠背景における大きなオブジ
ェクトに対してよく機能する。より近い距離では、テキ
スチャは、例えば、広告掲示板、ペインティング、カー
ペット、大理石製の壁、等のような、ほとんどフラット
である三次元オブジェクトに対して最もよく機能する。
最近、レンダリング・ハードウェアは、テキスチャ・マ
ッピングを支持することを始めたし、かつ実時間レンダ
リング・エンジンもこれらの技術を適用することができ
る。しかしながら、テキスチャ・マッピングは、フラッ
トでない隣接するオブジェクトに対して品質の著しい損
失を結果として生ずる。一つの部分的な解は、テキスチ
ャされた多角形がオブザーバに面すべく常に旋回する
“サインボード”である。しかし、ステレオ、特にヘッ
ド・トラック型ＶＲステレオを考慮したときに、隣接す
るテキスチャは、フラットとして明らかに感知される。
これらの例では、隣接するオブジェクトのあまり詳細で
はないが完全な三次元多角形表現は、より現実的であろ
う。

【０００５】幾何学形状の多面体表現は、三次元ラスタ
ー・コンピュータ・グラフィックの分野で長く支持され
ている。そのような表現では、任意の幾何学形状は、頂
点(vertices)、エッジ(edges) 、及び面(faces) の一覧
表によって一般に表現されかつ指定される。Computer G
raphics: Principles and Practice, 2nd ed., Addison
-Wesley, 1990 においてJ. Foly, et al. によって指摘
されたように、ウィングドエッジ・データ構造(winged-
edge data structures) のような表現は、ディスプレイ
されるだけの幾何学形状の編集を支持すべく設計され
た。 これら表現の痕跡（なごり）は、交換フォーマ
ット、例えばWavefront OBJ として今日生き残ってい
る。理論的にコンパクトであるが、あるコンパクション
は、交換ファイルにおけるＡＳＣＩＩ（アスキー）デー
タ表現を用いることにより判読性の犠牲になる。不幸に
も、これらのフォーマットのほとんど（もしあれば）
は、レンダリング・ハードウェアに描画命令(drawing i
nstructions)として直接渡すことができない。そのよう
なフォーマットの別の歴史的痕跡は、早期レンダリング
・ハードウェアが受け入れうる一般のプリミティブ・フ
ォーム(general primitive form)の、Ｎ−面多角形の支
持体である。しかしながら、今日の高速レンダリング・
ハードウェアは、ハードウェアに提出される前に全ての
多角形幾何学形状が三角形に低減されることを要求す
る。三面以上を有する多角形は、プレーナー（平面）ま
たはコンベックス（凸面）のいずれかであることを一般
に保証することができない。四辺形がレンダリング・プ
リミティブとして受容されるならば、レンダリングの前
にそれらが一対の三角形に任意に分割されるということ
が受容されるべきである。

【０００６】近代グラフィックス言語は、通常、頂点デ
ータ構造のアレーとして、三次元三角形の収集の表現の
ために２値フォーマットを一般に指定する。それゆえ
に、ＰＨＩＧＳ ＰＬＵＳ、ＰＥＸ、ＸＧＬ、及びＯｐ
ｅｎＧＬへの提案された拡張は、このフォーマット・フ
ォームであり、かつ実行可能幾何学形状によって取られ
る記憶空間を画定する。“ジグザグ”または“スター”
ストリップスに三角形を分離または連鎖することは、こ
の分野で知られている。例えば、Ｉｒｉｓ−ＧＬ、ＸＧ
Ｌ、及びＰＥＸ５．２は、ジグザグからに、頂点毎に基
づき連鎖している星状の頂点へ切り替えることができる
汎用の三角形ストリップのフォームを画定するが、ＸＧ
Ｌ及びＰＥＸの頂点当たりの余分なヘッダ・ワードを犠
牲にする。再開始コードは、三角形の多重切断ストリッ
プスを頂点の１アレー内で指定させる。これらの言語で
は、全ての頂点コンポーネント（位置、カラー、ノーマ
ルズ(normals) ）は、３２ビット単精度ＩＥＥＥ浮動小
数点数、または６４ビット倍精度数によって指定されう
る。また、ＸＧＬ、ＩｒｉｓＧＬ、及びＯｐｅｎＧＬフ
ォーマットは、３２ビット整数サポートも供給する。Ｉ
ｒｉｓＧＬ及びＯｐｅｎＧＬフォーマットは、１６ビッ
ト整数として頂点位置コンポーネント入力をサポート
し、ノーマルズ及びカラーは、これらのいずれか並びに
８ビット・コンポーネントであることができる。実際に
は、位置、カラー、及びノーマルズは、視覚的品質にお
ける損失がほとんどなく３２ビット（単精度ＩＥＥＥ浮
動小数点）よりかなり少なく量子化される。そのような
ビット節約は、適切な数値解析サポートが存在するとい
うことを前提として、市販の三次元グラフィックス・ハ
ードウェアに用いられうる。しかしながら、圧縮され
た、三次元幾何学形状データを含んでいる、幾何学形状
データは、有用であるべく圧縮解除されなければならな
い。例えば、１９９５年８月４日に出願した、発明の名
称が「三次元グラフィックス・データの幾何学形状圧縮
のための方法及び装置」である本発明の出願人の特許出
願がそのような圧縮を開示している。

【０００７】

【発明が解決しようとする課題】それゆえに、圧縮され
た三次元幾何学形状を圧縮解除する方法及び装置の必要
性が存在する。圧縮解除は、出力データが描画命令とし
て直接レンダリング・ハードウェアにわたされうるよう
なものが好ましい。そして、三次元幾何学形状の圧縮解
除は、ハードウェア、ソフトウェア、またはそれらの組
合せを用いて実現可能であるべきである。本発明は、そ
のような圧縮解除を開示する。本発明の目的は、上記従
来の技術における問題点に鑑み、出力データが描画命令
として直接レンダリング・ハードウェアにわたされるよ
うに圧縮された三次元幾何学形状を圧縮解除する方法及
び装置を提供することである。

【０００８】

【課題を解決するための手段】本発明の上記目的は、可
変長フィールドのデータ・ストリームを圧縮解除する方
法であり、該データ・ストリームが該フィールドの圧縮
解除を三次元オブジェクトの非圧縮表面特性にガイドす
る、オプ・コード・ビット及び／又はタグ・ビットを含
んでいる、方法であって、（ａ）フィールド型をデータ
・ストリームから検出し、そのような検出をイネーブル
するデータは、先行するが該データ・ストリーム内でシ
ーケンシャルにすぐに先行する必要はない、（ｂ）フィ
ールド長及び／又はフィールド正規化をデータ・ストリ
ームから検出し、そのような検出をイネーブルするデー
タは、先行するが該データ・ストリーム内でシーケンシ
ャルにすぐに先行する必要はない、（ｃ）段階（ａ）及
び段階（ｂ）の少なくとも一つから得られた情報を用い
て、データ・ストリームからビット位置合わせされたフ
ィールドを抽出し、（ｄ）最初の数値スケールに抽出し
たビット位置合わせされたフィールドを必要に応じて再
正規化し、（ｅ）圧縮解除された表面記述データを出力
する段階を具備し、データは、オプションで汎用三角形
ストリップ・フォーマットである方法によって達成され
る。本発明の方法では、オプ・コードは、後続するフィ
ールドのセットの型に関する情報を表わし、該情報は、
（ｉ）頂点情報、（ｉｉ）位置情報、（ｉｉｉ）表面ノ
ーマル情報、（ｉｖ）カラー、（ｖ）テキスチャ・マッ
プ座標、（ｖｉ）表面材料特性、及び（ｖｉｉ）手順情
報、（ｖｉｉｉ）頂点情報、ノーマル指令及びカラー指
令以外の指令である手順情報からなるグループから選択
され、及び／又は、タグ・ビットは、（ａ）該タグ・ビ
ットが（ｉ）フィールド長、（ｉｉ）正規化、（ｉｉ
ｉ）そのようなフィールドが相対的か否か、（ｉｖ）そ
のようなフィールドが絶対的か否か、からなるグループ
から選択された少なくとも一つのフィールド特性を暗黙
的に記述する、及び（ｂ）該タグ・ビットが可変長を有
しかつ当該可変長についての情報並びに可能フィールド
内容情報を含み、該可変長は、該フィールド内容情報か
ら独立である、からなるグループから選択された少なく
とも一つの特性を有するように構成してもよい。

【０００９】本発明の方法では、段階（ｂ）でイネーブ
リング・データがすぐにシーケンシャルに始めないなら
ば、方法は、（ｂ−１）現行命令及び後続命令をデータ
・ストリームからフェッチし、（ｂ−２）後続命令の固
定数の最初のビットをフェッチし、かつ（ｂ−３）次い
で、現行命令に対して残りのビットをフェッチすること
を更に含むように構成してもよい。本発明の方法では、
（ｆ−１）その出力が（ｉ）後続データ・フィールドの
開始、（ｉｉ）該データ・フィールドの長さ、（ｉｉ
ｉ）実際のタグ・フィールド長、（ｉｖ）該フィールド
が相対的であるか否かの識別、（ｖ）該フィールドが絶
対的であるか否かの識別、及び（ｖｉ）再正規化を容易
にするための数値シフティング・オフセット情報を含ん
でいる該データ・フィールドに対する再正規化パラメー
タ、の少なくとも一つを識別するタグ・ルックアップ表
にタグ・ビットを供給し、（ｆ−２）タグ・ルックアッ
プ表出力がそのようなビット位置合わせされたフィール
ドが相対的であることを示すならば、フィールドの正規
化された値をフィールドの現行値に加え、（ｆ−３）タ
グ・ルックアップ表出力がそのようなビット位置合わせ
されたフィールドが絶対的であることを示すならば、該
フィールドの該正規化された値で該フィールドの現行値
を置換する段階を更に具備するように構成してもよい。

【００１０】本発明の方法では、次の後続命令がビット
位置合わせされたフィールドが解釈されるべき方法を変
更することかまたはタグ表の内容を変更することまたは
該ビット位置合わせされたフィールドの非変更データを
通過することであるならば、そのようにし、かつ、その
ような正規化ビット位置合わせされたフィールドがノー
マル情報を含むならば、タグ・フィールド・インデック
スは、該ノーマルの直線表現を得るためにルックアップ
表を通過するように構成してもよい。本発明の方法で
は、ビット位置合わせされたフィールドは、（ｉ）オブ
ジェクトの表面上のｘ、ｙ、ｚ座標位置、（ｉｉ）オブ
ジェクトに対する赤、緑、青のカラー情報、（ｉｉｉ）
オブジェクトに対する赤、緑、青及びアルファのカラー
情報、（ｉｖ）オブジェクトに対するシーケンシャル
赤、緑、青のカラー情報間の相違、及び（ｖ）オブジェ
クトに対するシーケンシャル赤、緑、青及びアルファの
カラー情報間の相違からなるグループから選択された少
なくとも一つの特性に関する情報を含むように構成して
もよい。

【００１１】本発明の方法では、オブジェクトは、
（ｉ）オブジェクトの位置の特性が直線ｘ、ｙ、ｚ座標
として表され、（ｉｉ）オブジェクトのカラーの特性が
少なくとも赤、緑、青、及びアルファ・コンポーネント
を有しているように表され、該カラーが（ａ）放射カラ
ー、（ｂ）環境カラー、（ｃ）散乱カラー、及び（ｄ）
鏡面カラーからなるグループからなる選択された少なく
とも一つのカラーを含み、（ｉｉｉ）オブジェクトのノ
ーマルの特性が直線Ｎｘ、Ｎｙ、及びＮｚベクトル係数
によって表され、（ｉｖ）オブジェクトのノーマルの特
性は、ノーマル表インデックスによって表されることか
らなるグループから選択された少なくとも一つの特性を
有し、オブジェクトの表面特性は、（ａ）位置、（ｂ）
ノーマル、（ｃ）カラー、（ｄ）テキスチャ・マップ座
標、及び（ｅ）オブジェクトの材料表面特性からなるグ
ループから選択された少なくとも一つの特性を含むよう
に構成してもよい。

【００１２】本発明の方法では、ノーマルのそれぞれ
は、単一インデックスによって所定の正規化されたノー
マルの表の中に表され、かつインデックスは、（ｉ）イ
ンデックスは、表されるべきノーマルの直線表現サイン
・ビットを備えているインデックス表現のビットを含
み、（ｉｉ）インデックスは、フォールドされたノーマ
ルが該フォールディング平面の既知の側面にあることを
確実にするように少なくとも一つのフォールディング平
面ｘ＝ｙ、ｘ＝ｚ、ｙ＝ｚによって表されるべきノーマ
ルの直線表現の絶対量の可能なフォールディングを指定
している少なくとも一つのビットを含み、（ｉｉｉ）イ
ンデックスは、ノーマルの経度情報及び緯度情報を表し
ているビットを含み、（ｉｖ）インデックスは、オクタ
ント情報のビット、セクスタント情報のビット、及びフ
ォールドされたノーマルの経度及び緯度についての情報
の追加フィールドを含むべく画定され、（ｖ）インデッ
クスは、ノーマルの経度情報及び緯度情報を表している
ビットを含み、及びオクタント情報のビット、セクスタ
ント情報のビット、及びフォールドされたノーマルの経
度及び緯度についての情報の追加フィールドを更に含
み、（ｖｉ）インデックスは、オクタント情報の３ビッ
ト、セクスタント情報の３ビット、及びフォールドされ
たノーマルの経度及び緯度についての情報の２つの追加
フィールドを含むべく画定され、（ｖｉｉ）インデック
スは、ノーマルの経度情報及び緯度情報を表しているビ
ットを含み、及びオクタント情報の３ビット、セクスタ
ント情報の３ビット、及びフォールドされたノーマルの
経度及び緯度についての情報の２つの追加フィールドを
更に含む、ことからなるグループから選択された少なく
とも一つの特性を有するように構成してもよい。本発明
の方法では、圧縮解除されるべきデータ・ストリーム
は、データが汎用三角形メッシュを画定している線形フ
ォーマットに変換された、頂点を有している複数の三角
形を画定している三次元三角形データとして表されたオ
ブジェクトからもたらされ、表面特性の個々のものが量
子化され、可変長圧縮が表面特性のシーケンシャルなも
のの間の相違に適用されるように構成してもよい。本発
明の方法では、現行ビット位置合わせされたフィールド
がメッシュ・バッファに配置されるべきであるならば、
該現行ビット位置合わせされたフィールドのコピーをメ
ッシュ・バッファに配置し、かつビット位置合わせされ
たフィールドがメッシュ・バッファ基準を含むならば、
ビット位置合わせされたフィールドに対する古い正規化
された値をアクセスする段階を更に含むように構成して
もよい。

【００１３】また、本発明の上記目的は、オプ・コード
・ビット及び／又はタグ・ビットを含み、その表面が表
面特性を画定する三次元オブジェクトを表している圧縮
データを含み、そのフィールドが長さにおいて変化する
ことができる、データ・ストリームを圧縮解除する、中
央処理装置（ＣＰＵ）及び当該ＣＰＵに結合されたメモ
リを含んでいるコンピュータ・システムに使用可能な、
システムであって、データ・ストリームを受け取りかつ
すぐ後に続くフィールドのデータ・ストリーム・フィー
ルド情報における先行しているが、すぐにシーケンシャ
ルに先行していることを必要としない、フィールドから
検出すべくプログラムされた検出器装置と、フィールド
情報は、フィールド型及びフィールド長及び／又はフィ
ールド正規化を含んでおり、検出器装置によって検出さ
れた少なくともあるデータを受け取りかつデータ・スト
リームからビット位置合わせされたフィールドを抽出す
べくプログラムされた抽出器装置とを備えているシステ
ムによって達成される。

【００１４】本発明のシステムでは、（ｉ）タグ・フィ
ールド開始位置、（ｉｉ）実際のタグ・フィールド長、
（ｉｉｉ）フィールドが相対的であるか否かの識別、
（ｉｖ）フィールドが絶対的であるか否かの識別、及び
（ｖ）数値シフティング・オフセット情報からなるグル
ープから選択された少なくとも一部分の情報を供給す
る、データ・ストリームの少なくとも一部を検出器装置
から受け取るべく結合された、ルックアップ表を更に含
み、データ・ストリームに含まれたビット・ライン・フ
ィールドは、個々のビットに位置合わせされるように構
成してもよい。本発明のシステムでは、（ｉ）データ・
ストリームに含まれた新しく入力するデータを調整する
第１段階と、新しく入力するデータにデータ・ストリー
ムに含まれる残っている古いデータを調整する第２段階
とを含む多段バレル・シフタ装置、（ｉｉ）データ・ス
トリームを受け取るべく結合されたインターフェイス回
路装置、（ｉｉｉ）インターフェイス回路の出力に結合
されかつデータ・ストリームを圧縮解除する三次元グラ
フィックス・デコンプレッサ、（ｉｖ）圧縮解除された
データ・ストリームを受け取りかつ出力すべく結合され
た、三次元グラフィックス・レンダリング装置からなる
グループから選択された少なくとも一つの装置を更に含
み、多段バレル・シフタ装置、インターフェイス回路装
置、三次元グラフィックス・デコンプレッサ、及び三次
元グラフィックス・レンダリング装置の少なくとも二つ
は、一つの集積回路に組み込まれるように構成してもよ
い。

【００１５】本発明のシステムでは、オプ・コードは、
後続するフィールドのセットの型に関する情報を表わ
し、該情報は、（ｉ）頂点情報、（ｉｉ）位置情報、
（ｉｉｉ）表面ノーマル情報、（ｉｖ）カラー、（ｖ）
テキスチャ・マップ座標、（ｖｉ）表面材料特性、及び
（ｖｉｉ）手順情報、（ｖｉｉｉ）頂点情報、ノーマル
指令及びカラー指令以外の指令である手順情報からなる
グループから選択され、及び／又は、タグ・ビットは、
（ａ）該タグ・ビットが（ｉ）フィールド長、（ｉｉ）
正規化、（ｉｉｉ）そのようなフィールドが相対的か否
か、（ｉｖ）そのようなフィールドが絶対的か否か、か
らなるグループから選択された少なくとも一つのフィー
ルド特性を暗黙的に記述する、及び（ｂ）該タグ・ビッ
トが可変長を有しかつ当該可変長についての情報並びに
可能フィールド内容情報を含み、該可変長は、該フィー
ルド内容情報から独立である、からなるグループから選
択された少なくとも一つの特性を有し、オプ・コード・
ビット及び／又はタグ・ビットの少なくともあるもの
は、フィールドの圧縮解除を三次元オブジェクトの非圧
縮表面特性の中にガイドするように構成してもよい。本
発明のシステムでは、オブジェクトは、（ｉ）位置、
（ｉｉ）ノーマル、（ｉｉｉ）カラー、（ｉｖ）テキス
チャ・マップ座標、及び（ｖ）オブジェクトの材料表面
特性からなるグループから選択された少なくとも一つの
特性を含んでいる表面特性を有し、及び／又はオブジェ
クトは、（ｉ）オブジェクトの位置の特性が直線ｘ、
ｙ、ｚ座標として表され、（ｉｉ）オブジェクトのカラ
ーの特性が少なくとも赤、緑、青、及びアルファ・コン
ポーネントを有しているように表され、該カラーが
（ａ）放射カラー、（ｂ）環境カラー、（ｃ）散乱カラ
ー、及び（ｄ）鏡面カラーからなるグループからなる選
択された少なくとも一つのカラーを含み、（ｉｉｉ）オ
ブジェクトのノーマルの特性が直線Ｎｘ、Ｎｙ、及びＮ
ｚベクトル係数によって表され、（ｉｖ）オブジェクト
のノーマルの特性は、ノーマルのルックアップ表の中に
インデックスによって表され、（ｖ）位置、（ｖｉ）ノ
ーマル、（ｖｉｉ）カラー、（ｖｉｉｉ）テキスチャ・
マップ座標、及び（ｉｘ）材料表面特性からなるグルー
プから選択された少なくとも一つの特性を含むように構
成してもよい。

【００１６】本発明のシステムでは、ノーマルのルック
アップ表は、所定の正規化されたノーマルを含み、かつ
ノーマルのそれぞれは、所定の正規化されたノーマルの
ルックアップ表の中に単一インデックスによって表さ
れ、インデックスは、（ｉ）当該インデックスは、表現
されるべきノーマルの直線表現サイン・ビットを備えて
いるインデックス表現のビットを含み、（ｉｉ）インデ
ックスは、フォールドされたノーマルが該フォールディ
ング平面の既知の側面上にあることを確実にするように
少なくとも一つのフォールディング平面ｘ＝ｙ、ｘ＝
ｚ、ｙ＝ｚによって表されるべきノーマルの直線表現の
絶対量の可能なフォールディングを指定している少なく
とも一つのビットを含み、（ｉｉｉ）インデックスは、
ノーマルの経度情報及び緯度情報を表しているビットを
含み、（ｉｖ）インデックスは、オクタント情報のビッ
ト、セクスタント情報のビット、及びフォールドされた
ノーマルの経度及び緯度についての情報の追加フィール
ドを含むべく画定され、（ｖ）インデックスは、ノーマ
ルの経度情報及び緯度情報を表しているビットを含み、
及びオクタント情報のビット、セクスタント情報のビッ
ト、及びフォールドされたノーマルの経度及び緯度につ
いての情報の追加フィールドを更に含み、（ｖｉ）イン
デックスは、オクタント情報の３ビット、セクスタント
情報の３ビット、及びフォールドされたノーマルの経度
及び緯度についての情報の２つの追加フィールドを含む
べく画定され、（ｖｉｉ）インデックスは、ノーマルの
経度情報及び緯度情報を表しているビットを含み、及び
オクタント情報の３ビット、セクスタント情報の３ビッ
ト、及びフォールドされたノーマルの経度及び緯度につ
いての情報の２つの追加フィールドを更に含む、ことか
らなるグループから選択された少なくとも一つの特性を
有するように構成してもよい。本発明のシステムでは、
圧縮解除されるべきデータ・ストリームは、データが汎
用三角形メッシュを画定している線形フォーマットに変
換された、頂点を有している複数の三角形を画定してい
る三次元三角形データとして表されたオブジェクトから
もたらされ、表面特性の個々のものが量子化され、可変
長圧縮が表面特性のシーケンシャルなものの間の相違に
適用されるように構成してもよい。

【００１７】

【作用】本発明による圧縮解除に対して、三次元幾何学
形状は、線形ストリームにおける頂点の各場合に１／３
三角形と２三角形との間の平均を指定させる、汎用の三
角形メッシュとしてまず表される。個々の位置、カラー
及びノーマルズは、個々の位置、カラー、及びノーマル
ズに適用される可変長圧縮で、量子化される。量子化さ
れた値は、頂点トラバーザル順序を供給すべく近隣の間
で符号化されるデルタ（Δ）圧縮であり、かつメッシュ
・バッファ参照が生成される。デルタ−位置、デルタ−
ノーマルズ及びデルタ−カラーのヒストグラムが生成さ
れて、その後に可変長ハフマン・タグ・カラー、並びに
デルタ−位置、デルタ−ノーマルズ及びデルタ−カラー
が生成される。圧縮された出力２値ストリームは、出力
ハフマン表初期化、順序付けされた頂点トラバーザル
ズ、出力タグ、及びデルタ−位置、デルタ−ノーマルズ
及びデルタ−カラーを含む。そのように圧縮された三次
元幾何学形状データの圧縮解除は、ハードウェア、ソフ
トウェア、またはそれぞれの組合せでインプリメントさ
れうる。圧縮解除装置は、圧縮されたデータ・ビット及
び入力データの大きさを表している信号を受け取る入力
ＦＩＦＯを含む。ＦＩＦＯ出力は、入力ブロック状態マ
シン及び入力ブロックに結合される。入力ブロック及び
入力ブロック状態マシンからの出力は、バレル・シフタ
装置に結合される。また、入力ブロック出力は、状態マ
シンへ出力するハフマン表にも入力される。また、状態
マシン出力は、その出力がタグ・デコーダに結合される
データ経路コントローラ、及びバレル・シフタ装置から
の出力を受け取るノーマル・プロセッサにも結合され
る。また、圧縮解除装置は、バレル・シフタ装置からの
出力を受け取る位置／カラー・プロセッサも含む。ノー
マル・プロセッサ及び位置／カラー・プロセッサからの
出力は、フォーマット・コンバータにマルチプレクスさ
れる。

【００１８】フォーマット・コンバータへの出力を生成
するデータ・ストリームにおける命令に対して、圧縮解
除装置は、フォーマット・コンバータに送られるノーマ
ルに対するビットと並列にタグ・デコーダへ送られる１
２ビット・タグを生成する。リードバック(read-back)
経路は、圧縮解除装置の内部状態をリードバックするた
めに用いられる。圧縮解除装置は、次の手順を実行す
る： （１）次の命令の残り、及び後続する命令の最初の８ビ
ットをフェッチする； （２）タグ表を用いて、あらゆる圧縮値フィールドを全
精度に拡張する； （３Ａ）値が相対的であれば、現行の値に加える；さも
なければ、置換する； （３Ｂ）メッシュ・バッファ参照であれば、古い値をア
クセスする； （３Ｃ）他の指令であれば、ハウスキーピングを行う； （４）ノーマルであれば、全値を得るためにＲＯＭ表を
通してインデックスをわたす； （５）汎用三角形ストリップ形における値を次の段階へ
出力する。 三角形データの圧縮解除されたストリームは、次いで、
従来のレンダリング・パイプラインにパスされうるし、
そこでそれが完全浮動小数点精度で処理することがで
き、その後ディスプレイされるかまたはさもなくば用い
られる。本発明の他の特徴及び利点は、添付した図面に
関連して、好ましい実施例が詳細に示される以下の説明
から明らかであろう。

【００１９】

【実施例】本発明によるグラフィックス・デコンプレッ
サは、三次元グラフィックス・オブジェクトを圧縮解除
する。そのような幾何学形状の三次元圧縮は、例えば、
ネットワークにわたる、圧縮された三次元幾何学形状を
送るのに必要な時間における低減、並びに、例えば、Ｃ
Ｄ−ＲＯＭ、等の幾何学形状が記憶されうる空間の低減
を許容する。圧縮された三次元グラフィックスの圧縮解
除を説明する前に、本発明が実行されうる環境全体を、
図１を参照して説明する。図１は、三次元圧縮幾何学形
状データがその上で送信され、かつ受信端でソフトウェ
ア、ハードウェア、またはそれぞれの組合せを用いて圧
縮解除されうる汎用のネットワークを示す。勿論、本発
明による三次元グラフィックス圧縮の圧縮解除は、例え
ば、メモリ、ＣＤ−ＲＯＭ、等に記憶される圧縮データ
のような、ネットワークを介さないで与えられる圧縮デ
ータで実行されうる。図１に示すように、三次元グラフ
ィックス・データのソース（発生源）１０は、その処理
されかつ圧縮された出力が、一つ以上のターゲット・ク
ライアントまたはデコーダ・システム４０に一つ以上の
ネットワーク３０にわたり結合されるサーバまたはエン
コーダ・システム２０に結合されうる。ネットワーク
は、同種(homogeneous) 、異種(heterogeneous) 、また
は二地点間(point-to-point)でありうる。

【００２０】サーバ２０は、関連主メモリ７０を伴う中
央処理装置それ自体（“ＣＰＵ”）６０、メッシュ・バ
ッファ８０、圧縮アルゴリズムを含みうるメモリ部分９
０、及びリード・オンリー・メモリ（“ＲＯＭ”）の領
域１００を含む中央処理ユニット５０を含む。代替的
に、本発明による圧縮は、ソフトウェアとは反対にハー
ドウェアにおいても実行されうる。アタッチメント１
（添付省略）は、上記参照特許出願に記載されたような
圧縮アルゴリズムを一覧表として示しているコードのコ
ピーである。また、サーバ２０は、一つ以上のＣＤ−Ｒ
ＯＭｓを含みうる、記憶ディスク装置８０への記憶のた
めにその圧縮された出力データがディスク・レイアウト
装置７０によって構成される、三次元グラフィックス圧
縮装置６０も含む。サーバは、ネットワーク・インター
フェイス装置１１０を介してネットワーク３０にわたり
通信する。当業者は、サーバ２０が圧縮されたデータに
対する複数のクライアント−デコーダ要求間を仲裁する
(arbitrating) ための機構を含みうるということに注目
するであろう。１９９５年８月４日に出願した、発明の
名称が「三次元グラフィックス・データの幾何学形状圧
縮のための方法及び装置」である本発明の出願人の特許
出願に記載されたように、三次元幾何学形状データの損
失が大きい圧縮は、ディスプレイされたオブジェクトの
品質における損失がほとんどなく、６：１〜１０：１の
比率を生成することができる。

【００２１】この明細書の以下の部分は、本発明による
圧縮解除の理解を容易にするために、上記参照特許出願
に示された、圧縮を説明する。ネットワーク環境におい
て、受信端で、デコーダ・システム４０は、ネットワー
ク・インターフェイス装置１２０、三次元グラフィック
ス・データを圧縮解除し、かつその出力が三次元グラフ
ィックス・レンダリング装置１４０に結合される、本発
明による、装置１３０を含む。システム４０は、デコー
ダ・システム４０は、ＣＰＵ１６０、メモリ１７０、１
８０が含みうる圧縮解除ソフトウェアの部分、及びＲＯ
Ｍ１９０を含む中央処理システム１５０を更に含みう
る。圧縮された三次元グラフィックスは、ソフトウェ
ア、ハードウェア、または各組合せを用いて有利に圧縮
解除されうる。デコーダ４０からの圧縮解除出力は、視
聴者(viewer)２００、または圧縮解除されたグラフィッ
クスを要求している別のシステムに更に結合されうる。
勿論、装置４０は、本発明により予め圧縮された、三次
元グラフィックスが圧縮解除のために、記憶装置８２、
ディスクまたはＣＤ−ＲＯＭ８４、等、から結合されう
る、スタンドアロン装置でありうる。装置４０は、例え
ば、コンピュータまたはワークステーションを含みう
る。ここで、三次元グラフィックス圧縮装置６０が本発
明の出願人の上記特許出願に記載されたように機能する
ことを想定すると、三角形データは、汎用三角形メッシ
ュにまず変換される。記憶媒体８０の所与の固定された
容量に対して、三角形メッシュ・データ構造は、三角形
データの準最適表現(near-optimal representation) で
ある。好ましい実施例では、三次元グラフィックス・オ
ブジェクトは、変換後のそのフォーマットが各線形スト
リップ頂点を、平均して、約１／３三角形から２三角形
に特定させる、三次元三角形データとして表されうる。
更に、そのような三角形ストリップ構造は、頂点アレー
・データ構造にわたる単一モノトニック走査によって圧
縮された幾何学形状の抽出を許容する。図２は、汎用三
角形メッシュ・データ構造、及び表面幾何学形状の汎用
メッシュ・バッファ表現を示す。そのようなメッシュ・
データ構造は、それ自体を線形ストリップに制限するこ
とにより、汎用三角形ストリップ・フォーマットが空間
において２のポテンシャル・ファクタ(potential facto
r of two) を無駄にするけれども、三次元幾何学形状圧
縮に用いられうる。図２に示した幾何学形状は、例え
ば、一つの三角形ストリップによって表わすることがで
きるが、多くの内部頂点がストリップに二度現れる。

【００２２】図２において、汎用三角形ストリップは、
次のように画定されうる。ここで、Ｒは、再開始を示
し、Ｏは、最古の置換(replace oldest)を示し、Ｍは、
中間の置換(replace middle)を示し、トレーリング・レ
ターｐは、メッシュ・バッファへのプッシュを示す。大
文字の後に続く数字は、頂点番号であり、負の数字は、
−１が最も新しくプッシュされた頂点を示すような、メ
ッシュ・バッファ・リファレンスである。 Ｒ６，Ｏ１，Ｏ７，Ｏ２，Ｏ３，Ｍ４，Ｍ８，Ｏ５，Ｏ
９，Ｏ１０，Ｍ１１ Ｍ１７，Ｍ１６，Ｍ９，Ｏ１５，Ｏ８，Ｏ７，Ｍ１４，
Ｏ１３，Ｍ６ Ｏ１２，Ｍ１８，Ｍ１９，Ｍ２０，Ｍ１４，Ｏ２１，Ｏ
１５，Ｏ２２，Ｏ１６，Ｏ２３，Ｏ１７，Ｏ２４，Ｍ３
０，Ｍ２９，Ｍ２８，Ｍ２２，Ｏ２１，Ｍ２０，Ｍ２
７，Ｏ２６，Ｍ１９，Ｏ２５，Ｏ１８ 同じ命名法を用いて、汎用三角形メッシュは、次のよう
に画定されうる： Ｒ６ｐ，Ｏ１，Ｏ７ｐ，Ｏ２，Ｏ３，Ｍ４，Ｍ８ｐ，Ｏ
５，Ｏ９ｐ，Ｏ１０，Ｍ１１，Ｍ１７ｐ，Ｍ１６ｐ，Ｍ
−３，Ｏ１５ｐ，Ｏ−５，Ｏ６，Ｍ１４ｐ，Ｏ１３ｐ，
Ｍ９，Ｏ１２，Ｍ１８ｐ，Ｍ１９ｐ，Ｍ２０ｐ，Ｍ−
５，Ｏ２１ｐ，Ｏ−７，Ｏ２２ｐ，Ｏ−９，Ｏ２３，Ｏ
−１０，Ｏ−７，Ｍ３０，Ｍ２９，Ｍ２８，Ｍ−１，Ｏ
−２，Ｍ−３，Ｍ２７，Ｏ２６，Ｍ−４，Ｏ２５，Ｏ−
５ 頂点リファレンスは、有利に、完全頂点仕様(full vert
ex specification) よりもかなりコンパクト（例えば、
より少ないビットで表される）にすることができるとい
うことに注目すべきである。三次元幾何学形状圧縮は、
古い頂点（例えば、上記トレーリング文字“ｐ”を有す
る頂点）をメッシュ・バッファ・メモリ８０に関連付け
られたキューの中に明確にプッシュする（図１参照）。
これらの古い頂点は、古い頂点が再び望ましいときに後
で明確に参照される。このアプローチは、ほぼあらゆる
形状の不規則メッシュを支持する精密制御(fine contro
l)を供給する。バッファ・メモリ８０は、有限の長さを
有し、かつ実際には、４−ビット・インデックスを必要
とする、１６の最大固定キュー長が好ましい実施例にお
いて用いられる。三次元グラフィックスの圧縮に関し
て、用語“メッシュ・バッファ”は、このキューを参照
し、表現“汎用三角形メッシュ”は、汎用三角形ストリ
ップとメッシュ・バッファ・リファレンスとの組合せを
参照する。

【００２３】メッシュ・バッファ８０の固定サイズは、
１６の独自のリファレンスよりも長いあらゆるラン（走
行）をブレーク・アップ（分割）するために圧縮された
幾何学形状に対して全テッセレータズ／リ・ストリッパ
ーズ(tessellators/re-strippers) を必要とする。しか
しながら、幾何学形状圧縮が一般にユーザ・レベルにお
いて直接的にプログラムされるのではなく複雑なテッセ
レータズ／リフォーマッターズ(reformatters)、非面倒
(non-onerous) な制限による。１６の古い頂点は、冗長
幾何学形状の約９４％までの再仕様(re-specification)
を回避することを許容することが事実できる。また、図
２は、表面幾何学形状の一般のメッシュ・バッファ表現
の一例でもある。幾何学形状圧縮言語は、汎用三角形ス
トリップの４つの頂点置換符号；具体的には、最古の置
換、中間の置換、時計方向再開始、及び反時計方向再開
始を支持する。更に、言語は、この頂点がメッシュ・バ
ッファの中にプッシュされるべきか否かを示すべく各頂
点ヘッダにおいて追加ビットを加える。一実施例では、
メッシュ・バッファ・リファレンス指令は、どの古い頂
点が ２ビット頂点置換符号と共に、再リファレンスさ
れるべきであるかを示すべく４−ビット・フィールドを
有する。メッシュ・バッファ・リファレンス指令は、メ
ッシュ・バッファ・プッシュ・ビットを含まない；古い
頂点は、一度だけリサイクルすることができる。

【００２４】実際には、幾何学形状は、純粋な位置デー
タをほとんど含んでいないし、かつ一般に、また、ノー
マル、及び／又はカラー、及び／又はテキスト・マップ
座標は、頂点毎に指定される。従って、メッシュ・バッ
ファ８０へのエントリは、ノーマル及びカラー及び／又
はテキスト・マップ座標を特に含んでいる、全ての関連
頂点毎情報(associated per-vertex information) に対
する記憶を含む。最大記憶空間効率に対して、頂点がデ
ータ・ストリームにおいて指定されるときには、頂点毎
ノーマル及び／又はカラー情報は、位置情報で直接束ね
られるのが好ましい。そのような包束(bundling)は、二
つの状態ビットによって制御されるのが好ましい：頂点
を有するバンドル・ノーマルズ（ＢＮＶ）、及び頂点を
有するバンドル・カラー（ＢＣＶ）。図８は、他の中に
ビットを含んでいる指令構造を示す。頂点がメッシュ・
バッファの中にプッシュされたときには、その束ねられ
たノーマル及び／又はカラーがプッシュされたならばこ
れらのビットも同様に制御する。上記参照特許出願に記
載された圧縮技術は、三角形に限定されないし、かつベ
クトル及びドットも圧縮されうるということに注目すべ
きである。例えば、線は、置換ビットがＭＯＶＥ及びＤ
ＲＡＷであるような、三角形のサブセットである。次い
で、出力頂点は、他の頂点が最近、先に省略された頂点
である、線の一つの終点を表わす頂点である。ドットに
対して、置換ビットは、ＤＲＡＷであり、かつ出力頂点
は、頂点である。ＣＰＵ５２がメッシュ・バッファ・リ
ファレンス指令を実行するときに、この処理は、逆転さ
れる。即ち、２ビットは、ノーマル及び／又はカラーが
受け継がれるか、またはメッシュ・バッファ記憶装置８
０から読み取られるか、または現行ノーマルまたは現行
カラーから取得されるべきかを指定する。ソフトウェア
５８は、これら二つの現行値を設定するための明確な指
令を含むのが好ましい。しかしながら、明確な“設定現
行ノーマル”指令が、アクティブなＢＮＶ状態ビットを
有する、メッシュ・バッファ・リファレンスを後続する
ときに、この規則に対する例外が存在する。この情況で
は、前者は、表面幾何学形状におけるハード・エッジの
コンパクト表現を許容すべく、メッシュ・バッファ・ノ
ーマルを無効にする。また、類似のセマンティックスも
カラーに対して画定され、表面カラーにおけるハード・
エッジのコンパクト表現を許容する。二つの追加状態ビ
ットは、頂点のストリームが三角形に変換されるときに
ノーマル及びカラーの解釈を制御する。三角形にわたる
複製ノーマル（ＲＮＴ）ビットは、三角形を完成する最
終頂点のノーマルが三角形全体にわたり複製されるべき
であることを表わす。三角形にわたる複製カラー（ＲＣ
Ｔ）ビットは、図８の指令構造に示されるように、同様
に画定される。

【００２５】ここでイメージｘｙｚ位置の圧縮を説明す
る。３２ビットＩＥＥＥ浮動小数点数に関連付けられた
８ビット指数の使用は、大きさにおいてサブ・アトミッ
ク粒子から数十億光年までの範囲を位置に許容する。し
かし、所与のモザイク形状オブジェクト(tessellated o
bject)に対して、現行モデリング・マトリックスによっ
てちょうど一度だけ指数が実際に指定され、かつオブジ
ェクト幾何学形状は、２４ビット固定点仮数(fixed-poi
nt mantissa)だけを用いて所与のモデリング空間内に効
果的に記載される。多くの場合、視覚的受容のためにか
なり少ない数ビットを必要とすしかつ、幾何学形状圧縮
言語は、１ビットに至るまでの位置データの変数量子化
を支持するのが好ましい。他の極端では、経験的視覚検
査並びに半導体ハードウェア・インプリメンテーション
の考察は、位置のコンポーネント当たり１６ビット以下
の精度がほとんど全ての場合に必要であるということを
示す。

【００２６】しかしながら、オブジェクト当たりのロー
カル・モデリング空間の位置及びスケールは、全３２ビ
ットまたは６４ビット浮動小数点座標によって指定され
るということを想定する。十分な数値ケアを用いて、複
数のそのようなモデリング空間は、１６ビット以上の位
置精度を有するシームレス幾何学形状座標システムを形
成すべく一緒に組合せられうる。殆どの幾何学形状は、
ローカルである。それゆえに、各オブジェクトに対する
１６ビット（またはそれ以下）モデリング空間内で、汎
用メッシュ・バッファ・ストリームの隣接頂点間の差
（Δ）は、たいてい有効（重要度）において１６ビット
以下である。所望ならば、幾何学形状のバッチにおける
近隣位置Δのビット長を表しているヒストグラムを構築
しうるし、かつこのヒストグラムに基づき頂点をコンパ
クトに表わすために可変長コードを割り当てうる。記述
するように、カスタマイズされたハフマン符号化は、幾
何学形状圧縮における位置Δを符号化するために用いる
のが好ましい。ここで、赤−青−緑−アルファ（“ＲＢ
ＧＡ”）カラーの圧縮を説明する。カラー・データは、
位置と同様に処理されるが、より小さい最大精度で処理
される。それゆえに、ＲＧＢαカラー・データは、
（１．０が１００％反射率を表わすような）絶対線形反
射率値である１２ビットの符号なし小数コンポーネント
にまず量子化される。追加パラメータは、カラー・デー
タを１２ビット以下のあらゆる量に効果的（有効）に量
子化させる。例として、図６に示すように、カラーは、
５−５−５ＲＧＢカラー空間内に全てありうる。オプシ
ョナル・αフィールドは、図８に示したカラーαプレゼ
ント（“ＣＡＰ”）状態ビットによって制御される。最
終レンダード画像(final rendered image)上で個別画素
カラーは、量子化された頂点カラー間にまだ挿入され、
また一般にライティング(lighting)の対象でもある。

【００２７】実際には、同じΔ−符号化は、カラー・コ
ンポーネント及び位置に対して用いられうる。カラー・
データ圧縮の領域は、幾何学形状圧縮と従来画像圧縮が
最も類似した問題に直面したところである。しかしなが
ら、フォーカスにおける差の原因で、多くの高度画像圧
縮技術が幾何学形状カラー圧縮に対して回避されうる。
例えば、ＪＰＥＧ画像圧縮標準は、幾何学形状圧縮に対
して行うことができない圧縮解除データのビューイング
に関する仮定（想定）に依存する。例えば、画像圧縮で
は、画素は、完全に直交（矩形）アレイで現われ、かつ
ビューしたときに、各画素が可視角度の狭い範囲の限界
を定めるということが先に知られている。対照的に、幾
何学形状圧縮では、視聴者とラスタ化された幾何学形状
の間の関係は、予想不可能である。画像圧縮では、視聴
者の目の上に表示された画素の空間周波数は、たいてい
人間の視覚システムのカラー鋭敏さよりも高いというこ
とが知られている。この理由で、カラーは、ＵＶカラー
・コンポーネントがＹ（強度）コンポーネントよりも低
い空間周波数で表現することができるようにＹＵＶ空間
に一般に変換される。通常、サブ・サンプルＵＶコンポ
ーネントを表しているディジタル・ビットは、二つ以上
の画素の間で分配される。しかしながら、視聴者の眼に
対する幾何学形状の固定表示スケールが存在しないの
で、幾何学形状圧縮は、これを利用することができな
い。更に、圧縮三角形頂点が汎用三角形メッシュの４つ
から８つまたはそれ以上の頂点に連結されると仮定する
と、頂点にわたるカラー情報の“half（半分）”を共有
する一定した方法が存在しない。同様な議論は、離散余
弦変換（ＤＣＴ）のような、従来の画像圧縮に用いられ
る更に複雑な変形に適用される。これらの変換は、画素
値の正則または正規（矩形・直交）サンプリングを想定
し、かつ圧縮解除の間中に多量のランダム・アクセスを
必要とする。

【００２８】擬似カラー・ルックアップ表を用いること
は、この分野で知られているが、そのような表は、固定
最大サイズを要求し、かつ実時間処理に対する相対的に
高価な資源を表しうる。擬似カラー・インデックスがあ
る一定の場面(scenes)に対してわずかに高い圧縮率をも
たらしうると同時に、ＲＧＢモデルは、更に一般化され
かつインプリメントするのにかなり安い。ＲＧＢモデル
では、ＲＧＢ値は、線形反射値として表される。理論的
に、照明(lighting)の全効果を予め知ることができるな
らば、ＲＧＢコンポーネントが非線形、または知覚的線
形空間（ガンマ補正空間(gamma corrected space) とも
称される）で表現されていたならば、一つ以上の表現ビ
ットを落すことができる。実際には、照明効果は、予測
可能でない傾向があり、かつ非線形光線から線形光線へ
のオン・ザ・フライ変換は、かなりのハードウェア資源
を必要とする。

【００２９】ここで表面ノーマル(normals) の圧縮を説
明する。従来、８ビット・カラー強度を決定するために
計算において９６ビット・ノーマル（３つの３２ビット
ＩＥＥＥ浮動小数点数）が用いられる。理論的に、９６
ビットの情報は、単位球の表面上に均等に拡がる、２⁹⁶
の異なるノーマルを表わすために用いることができる。
結果として得られた非常に高い精度は、２^-46 ラジアン
毎にあらゆる方向に突出しているノーマルを表わす。し
かし、ＩＥＥＥ浮動小数点正規化ノーマルに対して、指
数ビットは、有効的に用いられない。拘束Ｎ_X ² ＋Ｎ_y
² ＋Ｎ_z ² ＝１を想定すると、Ｎ_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 ² ＋Ｔ_1,0 ² ＋Ｔ_2,0 ² ＝１、等。

【００３３】ノーマル変換の間、浮動小数点演算ハード
ウェアは、最大コンポーネントの精度まで全ての加法ア
ーギュメントを効果的に切り捨てる。結果は、スケール
保存モデリング・オリエンテーション・マトリックスに
よって変換が行われる正規化ノーマルに対して、変換さ
れたノーマル値の数値精度は２〜３の特別な場合を除い
た全てにおいて２４ビット固定点精度未満(no more tha
n 24-bit fixed-pointaccuracy)まで低減される。比較
すると、２４ビット・ノーマル・コンポーネントでさえ
も、修正されたハブル天体望遠鏡よりも高いアンギュラ
精度を供給しうるし、かつ実際には、あるシステムは、
１６ビット・ノーマル・コンポーネントだけを利用す
る。１６ビット・ノーマル・コンポーネントによる実験
的テストでは、ノーマル間の０．０１ラジアンのアンギ
ュラ密度からの結果（例えば、単位球上に分散された約
１００，０００のノーマル）は、より高い精度の表現か
ら視覚的に識別可能ではない。直線空間では、これらの
ノーマルは、高い表現精度をまだ要求し、かつ実際に
は、一つのサイン及び一つのガード・ビットを含んでい
る１６ビット・コンポーネントは、よい設計選択を表わ
す。これは、ノーマルを表わすために４８ビットをまだ
必要とするが、しかし１００，０００の指定ノーマルだ
けに興味があるので、理論的に単一１７ビット・インデ
ックスは、これらのノーマルのどれかを表しうる。

【００３４】ここで、インデックスとしてのノーマルの
使用、及び供給された合成利点(resultant advantages)
を説明する。単位球上のノーマルのインデックスを
Ｎ_X 、Ｎ _y 、Ｎ_z 値に戻して変換する一方法は、たぶん
メモリ７０に装填されている表の、表ルックアップによ
ってである。表サイズは、可能的に大きいけれども、必
要サイズは、単位球に存在する４８通りのシンメトリ
（対称性）を利用することによって実質的に低減するこ
とができる。より特定的には、図３に示すように、単位
球は、サイン・ビットによる８つのクォドラントにおけ
るサイン・ビットによって対称である。ノーマル表現ビ
ットの３つをノーマルのｘｙｚコンポーネントの３つの
サイン・ビットにすることによって、単位球の１／８を
表わすことだけが次いで必要である。単位球の各オクタ
ントは、平面ｘ＝ｙ、ｘ＝ｚ、及びｙ＝ｚについて折り
曲げることによって６つの同一コンポーネントに分割す
ることができる。６つの可能なセクスタント(sextants)
は、表現されたままの球の１／４８だけを残す、別の３
ビットで符号化される。

【００３５】上記シンメトリを用いることは、８×６＝
４８のファクタでルックアップ表サイズを低減する。１
００，０００エントリを記憶する代わりに、ルックアッ
プ表は、ＲＯＭ５９（図１参照）内にたぶん記憶され
る、オン・チップＲＯＭルックアップ表であるべく十分
に小さいサイズの、約２，０００エントリだけを記憶す
る必要がある。ルックアップ表の中にインデックスする
ことは、先に記載された二つの３ビット・フィールドに
加えられたときに全ての３つのノーマル・コンポーネン
トを記載するために１７ビット・フィールドを結果とし
て生ずる、１１のアドレス・ビットを必要とする有限セ
ットの単位ノーマルを表わすことは、単位球の表面上に
点を位置決めすることに等しい。完全に均等なアンギュ
ラー密度分布が多くの数の点に対して存在しないにもか
かわらず、多くの近最適分布が存在する。理論的に、上
述した型の４８通りシンメトリは、三次元幾何学形状圧
縮解除装置１３０に関連付けられた圧縮解除ルックアッ
プ表に用いることができる（図１参照）。しかしなが
ら、複数の更なる拘束は、符号化の異なる選択を要求す
る。第１に、スケーラブル密度分布が望まれる、例え
ば、“０”までの更に下位のアドレス・ビットをルック
アップ表に設定することは、単位球上にかなり均等なノ
ーマル密度を結果としてまだ生ずるような分布。さもな
ければ、全ての符号化密度に対して異なるルックアップ
表が必要である。第２に、Δ符号化可能分布は、幾何学
形状の隣接頂点が、単位球の表面で隣接するノーマルを
統計的に有することにおいて望ましい。単位球表面の二
次元空間上の隣接位置は、二次元オフセットによって最
も簡潔に符号化される。そのようなメートル(metric)が
存在するような分布を有することが望ましい。そして、
ノーマル符号化処理に関連付けられた計算費用が極めて
重要ではないけれども、より低い符号化費用を有してい
る分布がそれでもなお好ましい。

【００３６】上記参照特許出願による圧縮は、単位球の
一つのセクスタント内のアンギュラ空間に正則グリッド
を有している分布を用いる。そのように、モノリシック
な１１ビット・インデックスよりも、セクスタント内の
全てのノーマルは、二つの６ビット直交アンギュラ・ア
ドレスで有利に表現される。次いで、この構成は、先の
ビット総数を１８ビットに改訂する。位置及びカラーの
場合のように、ノーマルの更なる量子化が受容されたな
らば、これらの６ビット・インデックスは、より少ない
ビットまで低減することができ、それゆえに１８から少
なくとも６ビットまでのどれかを用いて絶対ノーマルを
表わすことができる。しかしながら、以下に説明するよ
うに、この空間は、ノーマルの高品質表現に必要なビッ
ト数を更に低減するためにΔ−符号化されるのが好まし
い。ここでノーマル符号化パラメータ化を説明する。単
位半径球上の点は、θがｙ軸についての角度、φがｙ＝
０平面からの経方向角度であるような、角θ及びφによ
り極座標を用いてパラメータ化される。式（１）は、次
のように直交座標と極座標の間のマッピングを支配す
る：

【００３７】

【数３】 ｘ＝ｃｏｓθ・ｃｏｓφ ｙ＝ｓｉｎφ ｚ＝ｓｉｎθ・ｃｏｓφ （１）

【００３８】球上の点は、オクタントによってまず折り
曲げられ、次いで６つのセクスタントの一つにｘｙｚの
分類順に折り曲げられる。全ての表符号化は、半球によ
って境界をつけられた領域における正のオクタントで行
われる：

【００３９】

【数４】 ｘ≧ｚ ｚ≧ｙ ｙ≧０

【００４０】図３に示すように、説明した三角形形状パ
ッチは、θでは０からπ／４ラジアンまで、φでは０か
ら最大０．６１５４７９７０９ラジアンまで実行する。
量子化された角度は、ｎが０から６までの範囲にある、
二つのｎビット整数θ _n ハット（＾）、φ_n ハット
（＾）によって表される。所与のｎに対して、インデッ
クスθとφの間の関係は：

【００４１】

【数５】

【００４２】式（２）は、どのようにθ_n ハット
（＾）、φ_n ハット（＾）の値が、次いで、式（１）を
介して直線ノーマル座標コンポーネントに変換できる、
極座標θ及びφに変換できるかを示す。処理を逆向きに
するために、例えば、所与のノーマルＮをθ_n ハット
（＾）、φ_n ハット（＾）に符号化するために、式
（２）を単に反転することはできない。その代わり、Ｎ
は、標準オクタント及びセクスタントにまず折り曲げら
れなければならず、Ｎ’を結果として生ずる。次いで、
Ｎ’は、セクスタントにおける全量子化ノーマルを点在
させなければならない。固定ｎに対して、最大（最隣接
ユニティ）ドット・プロダクトを結果として生ずるθ_n
ハット（＾）、φ_n ハット（＾）は、Ｎの適切な符号化
を画定する。例えば、φを設定するために表を通してイ
ンデックスし（索引を付け）、そしてθの中にジャンプ
させるような、θ _n ハット（＾）、φ_n ハット（＾）の
正しい値を見出す、より有効な方法が存在する。この重
大な局面にあたって、絶対ノーマルの完全ビット・フォ
ーマットを付与することができる。上位３ビットは、オ
クタントを指定し、次の３ビットは、セクスタント、そ
して最後の二つのｎビット・フィールドは、θ_n ハット
（＾）、φ_n ハット（＾）を指定する。３ビット・セク
スタント・フィールドは、図３に示される２進（バイナ
リ）コードである、６つの値の一つを取る。更なる詳細
を次に示す。標準パッチの角（コーナー）における３つ
のノーマルは、６、８、及び１２倍のように、倍増表現
される。セクスタント・フィールドの二つの未使用値を
採り入れることによって、これらのノーマルは、２６の
特別ノーマルとして独自に符号化することができる。ノ
ーマルのこの表現は、少なくともセクスタント内で、Δ
符号化に従い、ある追加ワークを伴うけれども、これ
は、共通エッジを共有するセクスタントに拡張すること
ができる。二つのノーマル間のΔコードは、単にθ_n ハ
ット（＾）、φ _n ハット（＾）における差、具体的に
は、Δθ_n ハット（＾）、Δφ_n ハット（＾）である。

【００４３】上記参照特許出願では、通常のハフマン・
アルゴリズムの変形を有する、圧縮タグが用いられる。
ハフマン圧縮アルゴリズムは、それらの記号の発生統計
量の頻度（周波数）（例えば、ヒストグラム）と共に、
表されるべき一組の記号を取り入れる。記号が指定した
頻度（周波数）で発生すると想定して、これから、これ
らの記号を近最小合計ビット数で表させる、可変長の、
独自に識別可能なビット・パターンが生成される。ＪＰ
ＥＧを含む、多くの圧縮技術は、後続する可変長データ
・フィールドの長さを表わすためのタグとして独自の記
号を生成する。このデータ・フィールドは、一般に指定
長デルタ値である。それゆえに、最後の２進ストリーム
は、それぞれがその長さがその固有タグ記号に関連付け
られるデータ・フィールドによってすぐに後続される、
（自己記述長）可変長タグ記号から構成される。参照特
許出願では、幾何学形状圧縮に対する２進フォーマット
は、位置、ノーマル、及びカラー・データ・フィールド
を表わすためにこの技術を用いる。幾何学形状圧縮に対
して、これらの＜ｔａｇ，ｄａｔａ＞フィールドは、よ
り一般的なコンピュータ命令セット・オプ−コード(op-
code) フィールドによってすぐに先行される。これらの
フィールドは、可能な追加オペランド・ビットと共に、
幾何学形状命令として参照される（表される）（図４〜
図１５参照）。従来、圧縮されるべき各値は、それ自身
の関連ラベルが割り当てられ、例えば、ｘｙｚΔ位置
は、３つのタグ値ペアによって表される。しかし、Δｘ
ｙｚ値は、相関関係でないので、より密で、より簡素
な、表現を達成することができる。一般に、ｘｙｚΔの
統計的ポイントは、空間の全ての方向を均等にポイント
する。それゆえに、ｎが最大のΔを表わすために必要な
ビットの数であるならば、統計的に他の二つのΔ値は、
それらの表現に対してｎ−１．４ビットの平均を必要と
する。従って、実際には、単一フィールド長タグは、Δ
ｘ、Δｙ、及びΔｚのビット長を表わすために用いう
る。残念ならが、このアプローチを用いることは、コン
ピュータ当たり一つのビット以上よりも幾分少なくセー
ブするために別のハフマン技術を利用することを阻止す
る。しかしながら、インプリメントされた実施例は、
（Δｙ及びΔｚに対して）二つの追加タグ・フィールド
を指定しなくてもよいことによってこの欠点を圧迫す
る。更なる利点は、所望ならば、単一タグ・フィールド
を用いることがハードウェア圧縮解除エンジンに並列で
全ての３つのフィールドを圧縮解除させるということで
ある。

【００４４】同様なアーギュメントがＲＧＢα値のΔ’
ｓに対して保持され、従って、単一のフィールド長タグ
は、Ｒ、Ｇ、Ｂ及び、もし存在すれば、αフィールドの
ビット長を表わすために用いられる。また、絶対及びΔ
ノーマルは、単一タグによって指定することができる単
一値（ｎ）によってパラメータ化される。高速で、低コ
ストのハードウェア・インプリメンテーションを容易に
するために、ハフマン・タグ・フィールドの長さは、比
較的小さな値である、６ビットに制限されうる。６４エ
ントリ・タグ・ルックアップ表は、１クロック・サイク
ルにおけるタグの復号を許容する。一つの表は、位置に
対して存在し、別の表は、ノーマルに対して存在し、更
に別の表は、カラー（及びオプションとして、テクスチ
ャ座標に対しても）存在する。各表は、タグ・フィール
ドの長さ、データ・フィールドの長さ、データ正規化係
数、及び絶対／相対ビットを含む。適正なハードウェア
・インプリメンテーションに対して、さらに別の厄介な
問題に対処しなければならない。以下に説明するよう
に、全ての命令は、８ビット・ヘッダ、及び可変長本体
に分解され、本体長を決定するために十分な情報がヘッ
ダに存在している。しかし、ヘッダ情報を処理すべくハ
ードウェア時間を与えるために先の命令の本体の前に、
一つの命令のヘッダは、データ・ストリームに配置され
なければならない。例えば、シーケンス．．．Ｂ０ Ｈ
１Ｂ１ Ｈ２Ｂ２ Ｈ３．．．は、Ｈ１ Ｂ０ Ｈ２
Ｂ１ Ｈ３ Ｂ２．．．として符号化されなければなら
ない。

【００４５】ここで、図４〜図１５に関して、上記参照
特許出願に開示された幾何学形状圧縮命令セットを説明
する。図４は、バンドリング(bundling)・ビット（ＢＮ
Ｖ及びＢＣＶ）によって、ハフマン圧縮Δ符号化位置、
並びに可能なノーマル及び／又はカラーを指定する頂点
指令を示す。二つの更なるビットは、頂点置換コード
（ＲＥＰ）を指定し、かつ別のビットは、この頂点を押
し出しているメッシュ・バッファを制御する（ＭＢ
Ｐ）。図５に示すように、ノーマル指令は、新たな現行
ノーマルを指定し、かつ図６に示したカラー指令は、新
たな現行カラーを示す。ノーマル指令及びカラー指令
は、それぞれΔ値のハフマン符号化を用いる。メッシュ
・バッファ参照指令構造を図７に示す。メッシュ・バッ
ファ参照指令構造は、１６の最近に押し出された頂点
（及び関連ノーマル及び／又はカラー）のいずれかを次
の頂点として参照させる（示させる）。図６に更に示す
ように、Ａ ２ビット頂点置換（“ＲＥＰ”）コードも
また指定される。図８は、５つの状態ビット、ＲＮＴ，
ＲＣＴ，ＢＮＶ，ＢＣＶ，及びＣＡＰを更新するセット
状態命令を示す。図９は、３つのハフマン復号表（位
置、ノーマル、またはカラー）の一つで指定されるエン
トリ値にエントリをセットするために用いられる、セッ
ト表指令を示す。図１０は、幾何学形状圧縮によって直
接的に制御されない更なるグラフィックス情報にイン・
ラインを更新させる、パススルー（通過(passthrough)
）指令を示す。図１１は、ビット・ストリーム内のフ
ィールドを３２ビット・ワード境界に位置合わせさせる
可変長ノップ（“ＶＮＯＰ”）指令を示す。これは、位
置合わせされたフィールドを一般のＣＰＵ５２により実
行時間で有効にパッチさせる。図１２、１３、１４、及
び１５は、タグ及びΔ位置データ構造、タグ及びΔノー
マル・データ構造、及びタグ及びΔカラー・データ構造
をそれぞれ示す。図１２及び図１５では、ｘ、ｙ、ｚの
絶対値が用いられるか、またはｘ、ｙ、及びｚのデルタ
値が用いられる。勿論、他の命令セットは、三次元幾何
学形状を圧縮するために代わりに用いられうる。圧縮解
除に対する圧縮に必要な時間の割合い（比率）は、重要
であることができる。実際に、オフ・ライン・イメージ
圧縮が圧縮解除よりもたぶん６０回以上も多くの回数を
費やすことは、受容可能であるが、しかし実時間ビデオ
会議に対しては、割合い（比率）は、１にすべきであ
る。

【００４６】有利には、幾何学形状圧縮は、この実時間
要求事項を有さない。幾何学形状がオン・ザ・フライで
構築されたとしても、ほとんどの幾何学形状生成技術、
例えば、ＣＳＧは、幾何学形状を表示するために必要な
時間よりも多い時間を要求する。また、映画に見られる
ような連続画像とは異なり、幾何学形状圧縮のほとんど
のアプリケーションでは、圧縮三次元オブジェクトが廃
棄される前に多くのシーケンス・フレームに対して表示
される。三次元オブジェクトが動画化を要求するなら
ば、動画は、モデリング・マトリックスで一般に行われ
る。事実ＣＤベース・ゲースに対して、オブジェクト
が、カスタマ−ユーザによって数億回も圧縮解除されう
ることは、もっともらしいが、著作会社(authoring com
pany) によって一度だけ圧縮される。ある他の圧縮シス
テムのように、幾何学形状圧縮アルゴリズムは、圧縮時
間対圧縮率トレード・オフを有することができる。所与
の品質ターゲット・レベルに対して、圧縮に対する許容
時間が増大すると、幾何学形状圧縮システムによって達
成される圧縮率は、増大する。合成圧縮三次元オブジェ
クトの品質に対して対応“ノブ(knob)”が存在し、品質
ノブが低いと、達成される圧縮がよくなる。審美的かつ
主観的判断は、幾何学形状圧縮に適用されうる。ある三
次元オブジェクトは、ノーマル及び／又は位置のターゲ
ット量子化が多少低減されるときに悪く見えはじめ、他
のオブジェクトは、大量の量子化でも視覚的に変わりえ
ない。圧縮は、可視アーティファクト（人工産物）を時
々もたらすことができるが、他の場合には、品質が必ず
しも低下するとは限らないが、オブジェクトを違って見
せるだけでありうる。出願人による一つの実験では、象
のイメージは、イメージ・ノーマルが更に量子化される
と、さらに皺のような皮膚を有して、実際により現実的
に見えはじめる。一度モデルが生成されかつ圧縮される
と、システム・レベルで三次元クリップ−アートとして
用いられるべく、それはライブラリの中に入れることが
できる。

【００４７】幾何学形状圧縮の多くの態様は、汎用であ
ると同時に、上述した幾何学形状圧縮命令セットは、低
コスト、高速ハードウェア・インプリメンテーションを
許容すべくある程度適合される。（ソフトウェア圧縮解
除のためにだけ設計された幾何学形状圧縮フォーマット
は、幾分異なるということが理解される。）。ワンパス
連続処理、限定ローカル記憶要求、タグ・ルックアップ
（従来のハミング・ビット連続処理とは反対に）、及び
シフト、加算の使用、及びほとんどの演算段階を達成す
るためのルックアップにより、説明した幾何学形状圧縮
命令セットは、ハードウェア・インプリメンテーション
に対して特に修正可能である。図１６は、本圧縮解除発
明が用いられうる、上記参照特許出願に記載された、幾
何学形状圧縮アルゴリズム・ルーチンにおける方法段階
を概説しているフローチャートである。そのようなルー
チンは、メモリ８０に記憶されかつＣＰＵ６０の制御下
で実行されうる（図１参照）。段階２００では、オブジ
ェクトは、位置、ノーマル、及びカラーに対する量子化
しきい値と共に、圧縮されるべき三角形の明示グループ
によって表される。段階２１０では、連結性のトポロジ
ー的分析が行われ、かつハード・エッジは、そのような
情報が既に存在していないならば、ノーマル及び／又は
カラーで印を付けられる。段階２２０では、頂点横断順
序及びメッシュ・バッファ参照が生成され、かつ段階２
３０では、Δ位置、Δノーマル、及びΔカラーのヒスト
グラムズが生成される。段階２４０では、分離可変長ハ
フマン・タグ・コードがヒストグラムズに基づいてΔ位
置、Δノーマル、及びΔカラーに対して割り当てられ
る。段階２５０では、２進出力ストリームがハフマン表
初期化をまず出力することによって生成され、その後で
頂点が順番に横断される。適当なタグ及びΔ’ｓが全て
の値に対して出力される。

【００４８】出願人は、位置及びノーマルの圧縮を支持
し、かつ全汎用三角形ストリップを生成するが、しかし
全メッシュファイング(full meshifying) ・アルゴリズ
ムをインプリメントしないウェーブフロントＯＢＪフォ
ーマット・コンプレッサを実現した。更なる実施例は、
圧縮表の微細構造更新を含む、可変精度幾何学形状を探
る。現行コンプレッサは、テッセレータに既に知られた
幾何学形状詳細を計算する時間を拡大し、かつ結果的に
圧縮された幾何学形状を直接生成することが望ましい。
しかしながら、その現在非最適状態であっても、出願人
のソフトウェアは、多くの場合に約３，０００三角形／
秒を圧縮することができる。本発明は、図１のユーザ端
末における、三次元圧縮幾何学形状を圧縮解除すること
に指図される。アタッチメント２（添付省略）は、本発
明による、圧縮解除アルゴリズムの一覧表である。簡潔
に、一般に、本発明による適用可能幾何学形状圧縮解除
アルゴリズムは、次のように概略されうる： （１）次の命令の残り、及び以下に続く命令の最初の８
ビットをフェッチする； （２）タグ表を用いて、あらゆる圧縮値フィールドを全
精度まで拡大する； （３Ａ）値が相対的であれば、現行値に加える；さもな
くば、置換する； （３Ｂ）メッシュ・バッファ・リファレンスであれば、
古い値をアクセスする； （３Ｃ）他の指令であれば、ハウスキーピングを行う。 （４）ノーマルであれば、全値を得るためにインデック
スをＲＯＭ表を通してパスする。 （５）汎用三角形ストリップ形における値を次の段階へ
出力する。 好ましい実施例では、出願人のデコンプレッサのソフト
ウェア実施例は、約１０，０００三角形／秒の速度で圧
縮された幾何学形状をうまく圧縮解除する。本発明によ
る圧縮解除の簡略化された全体ブロック図を図１７に示
す。本発明によるデコンプレッサのハードウェア・イン
プリメンテーションは、数千万の三角形／秒の範囲にお
いて圧縮解除することができ、その速度は、実質的に拡
張されうる。圧縮解除を説明する前に、図１８〜図２９
及び以下の表１に示すような、非圧縮及び圧縮イメージ
結果を試験しかつ比較することは、有用である。図１８
〜図２４は、同じベース・オブジェクト、トリケラトプ
スを示すが、位置及びノーマルで異なる量子化しきい値
を有する。図１８は、名称Ｐ９６／Ｎ９６で示される、
９６ビット位置及び９６ビット・ノーマルを用いてい
る、最初の全浮動小数点表現である。図１９及び図２９
は、それぞれ単に位置的量子化Ｐ３６／Ｎ９６及びＰ２
４／Ｎ９６の効果を示し、図２１及び図２２は、ノーマ
ル量子化、Ｐ９６／Ｎ１８及びＰ９６／Ｎ１２だけを示
す。図２３及び図２４は、結合量子化、Ｐ４８／Ｎ１８
及びＰ３０／Ｎ３６を示す。図２５〜図２９は、ガリオ
ン（Ｐ３０／Ｎ１２）、ダッジ・バイパー（Ｐ３６／Ｎ
１４）、’５７シェビーの二つのビュー（Ｐ３３／Ｎ１
３）、及び虫（Ｐ３９／Ｎ１５）を含む、異なるオブジ
ェクトに対する量子化された結果だけを示す。オブジェ
クトを拡大ズームすることなく、２４ビットよりも上の
位置量子化は、実質的に重要な可視効果を有さない。ノ
ーマル量子化が低減されると、表面上の鏡のような強調
(specular highlights) の位置は、多少オフセットされ
る。しかしながら、そのような変化が、少なくとも１２
ビット／ノーマル以上の、品質における低減であるとい
うことは、視覚的に自明ではない。量子化パラメータ
は、オブジェクトと共に写真に撮られ、そしてさもなけ
れば、出願人でさえも、オリジナルと同じオブジェクト
の最も圧縮されたバージョンとを識別することができな
い。

【００４９】表１は、これらのオブジェクトに対する圧
縮及び他の統計量を要約する。カラム１は、問題のオブ
ジェクトを示し、カラム２は、Δ’ｓの数を表し、カラ
ム３は、Δストリップ長を表わす。４番目のカラムは、
頂点当たりのシステム・オーバヘッドを表わす（オーバ
ヘッドは、位置タグ／データ、及びノーマル・タグ／デ
ータを越えた全てのものである）。“ｘｙｚ ｑｕａｎ
ｔ”カラムは、量子化しきい値を示し、そして６番目の
カラムは、ビット数／ｘｙｚを示す。“Ｂｉｔｓ／ｔｒ
ｉ”９番目カラムは、三角形当たりのビットを示す。表
１の結果は、括弧で示される、推定メッシュ・バッファ
結果を除き、測定された実圧縮データである。実メッシ
ュ・バッファ結果は、その出願人のプロトタイプ・ソフ
トウェア・コンプレッサが全メッシファイング・アルゴ
リズムをまだインプリメントしていないので、存在しな
い。（括弧で示した）推定は、メッシュ・バッファにお
いて４６％ヒット率を想定する。表１では、最右カラム
は、既存の実行可能な幾何学形状フォーマットにわたり
達成された圧縮率性能を示す。圧縮された幾何学形状の
合計バイト計数が明白な数であるけれども、圧縮率を示
すことにおいてある想定がオブジェクトの非圧縮実行可
能表現についてなされなければならない。出願人は、表
１に対して“最初の大きさ”(original size) のデータ
を算出するために浮動小数点値によって表される位置及
びノーマルの両方を有する、最適化された汎用三角形ス
トリップを想定した。単なる１６ビット固定点単一スト
リップ表現の効果を示すために、表１は、また、Ｏｐｅ
ｎＧＬのモードに対するビット計数も示す。示したよう
に、平均ストリップ長は、２〜３の範囲で減少した。も
しあれば、市販製品は、汎用三角形ストリップをほとん
ど利用せず、それゆえに、表１は、可能なメモリ空間セ
ービングをかなり控えめに表している。

【００５０】

【表１】 表１ ────────────────────────────────── Obj. #Δ's Δstp ovrhd/ xyz bits/ normname Ien. vertex quant xyz quant tricer- 6,039 15.9 7.5 48 30.8 18 atops tricer- 6,039 15.9 7.5 30 17.8 12 atops galleon 5,577 12.1 7.5 30 21.9 12 Viper 58,203 23.8 7.5 36 20.1 14 57 31,782 12.9 7.5 33 17.3 13 Chevy insect 263,783 3.0 7.5 39 22.8 15

【００５１】

【表２】 表１の続き ────────────────────────────────── Obj. bits/ bits/ org'l size comp.size comp.name norm tri (bytes) (bytes) ratio tricer- 16.8 55.9 179,704 42,190 4.3x atops (35.0) (26,380) (6.9x) tricer- 11.0 36.0 179,704 27,159 6.7x atops (24.4) (18,368) (9.8x) galleon 10.8 41.0 169,064 28,536 6.0x (27.2) (18,907) (9.0x) Viper 10.9 37.5 1,698,116 272,130 6.8x (25.0) (181,644) (9.4x) 57 10.9 35.8 958,160 141,830 6.8x Chevy (24.3) (96,281) (10.0x) insect 11.0 51.5 9,831,528 1,696,283 5.8x (33.9) (1,115,534) (8.9x)

【００５２】確実に統計的変化が圧縮率に関してオブジ
ェクト間に存在すると同時に、一般的な傾向は、それで
もなお示される。量子化ノブ（Ｐ４８／Ｎ１８）の最高
品質のセッティングを用いて圧縮するときに、圧縮率
は、一般に約６である。率がそれに近づくと、ほとんど
のオブジェクトは、可視量子化アーティファクト（人工
産物）を表し始める。三次元幾何学形状圧縮アルゴリズ
ムは、実時間ハードウェア、またはソフトウェアで実現
されうるということが上述から理解されるであろう。重
要なのは、三次元レンダリング・ハードウェアが本発明
による幾何学形状圧縮解除装置を含んでいるならば、ア
プリケーション幾何学形状は、圧縮されたフォーマット
でメモリに記憶されうる。更に、データ伝送は、圧縮さ
れたフォーマットを用いうるし、それゆえに、共有仮想
現実表示環境を含む、グラフィックス加速器システムに
対する有効帯域幅を改良する。合成圧縮は、主（１次）
メモリにおける幾何学形状キャッシュ可能性の量を実質
的に増大することができる。図３０は、図１に示したデ
ィコンプレッサ装置１３０の詳細ブロック図である。図
３０に示すように、装置１３０は、その入力が制御信号
及び好ましくは３２ビットまたは６４ビット・データ・
ストリームを含む圧縮解除入力先入れ先出しレジスタ
（“ＦＩＦＯ”）２００を含み、それらの信号及びデー
タ・ストリームは、インターフェイス装置１２０（図１
参照）の加速器ポート・データＦＩＦＯ（“ＡＰＤ
Ｆ”）からくるのが好ましい。インターフェイス１２０
のＡＰＤＤ部分は、装置１３０に入力データ・ストリー
ムの大きさの信号を送るコントローラを含む。ＦＩＦＯ
２００は、入力ブロック状態マシン２２０及び入力ブロ
ック２１０に出力を供給し、状態マシン２２０及び入力
ブロック装置２１０は、互いに通信している。

【００５３】ブロック２１０からの出力は、バレル・シ
フタ装置２４０及びハフマン表セット２３０に結合さ
れ、ハフマン・ルックアップからの出力は、状態マシン
２２０に結合される。状態マシン２２０内のＯｐｃｏｄ
ｅ（オプコード）は、ハフマン表２３０によって供給さ
れた値を処理しかつバレル・シフタ装置２４０にデータ
を出力する。また、状態マシン２２０は、タグ・デコー
ダ装置２９４に好ましくは１２ビット幅信号を出力しか
つバレル・シフタ装置２４０及びノーマル・プロセッサ
２７０、及び位置／カラー・プロセッサ２８０にデータ
を出力する、データ・パス・コントローラ２６０に出力
を供給する。バレル・シフタ装置２４０は、ノーマル・
プロセッサ２７０及び位置／カラー・プロセッサ２８０
に出力する。プロセッサ２７０及び２８０からの出力
は、フォーマット・コンバータ２９２に供給される好ま
しくは４８ビット幅信号に出力マルチプレクサ装置２９
０によってマルチプレクスされる。圧縮解除装置１３０
は、フォーマット・コンバータ２９２に送られる、（ノ
ーマルに対して）３２ビットまたは４８ビットのいずれ
かと並列でタグ・デコーダ２９４に送られる好ましくは
１２ビット・タグを生成する。これらのデータ・ストリ
ームは、フォーマット・コンバータ２９２への出力を生
成する命令を供給する。好ましくは３２ビット・リード
バック(read-back) 経路は、装置の状態をリードバック
するために用いられる。下記の表２は、好ましい実施例
における圧縮解除装置１３０を実現するために用いるイ
ンターフェイス信号を示す：

【００５４】

【表３】 表２ ────────────────────────────────── 信号名 信号 Ｉ／Ｏ 説 明 id data ６４ Ｉ ＡＰＤＦからのデータ入力 id tag １２ Ｉ 入力上のデータはＡＰＤＦから 有効である fd stall １ Ｉ フォーマット・コンバータから のストール信号 di busy １ Ｏ 状態レジスタへのビジィ信号 di faf １ Ｏ ＦＩＦＯ−ほぼ−完全信号−対 −入力ＦＩＦＯ df data ４８ Ｏ フォーマル・コンバータへの データ出力 df tag １２ Ｏ タグ・デコーダへのタグ出力 du context ３２ Ｏ ＵＰＡセクションへのコンテ キスト出力

【００５５】下記の表３は、好ましい実施例における装
置１３０によって供給される出力データ・フォーマット
を示す。ここで説明するように、頂点、メッシュ・バッ
ファ・リファレンス、及びパススルー命令は、圧縮解除
装置１３０からのトランザクションを生成する。頂点及
びメッシュ・バッファ・リファレンス命令は、フォーマ
ット・コンバータにデータを送り、かつそれぞれは、コ
ンポーネント・データを後続する、現行頂点に対する頂
点置換方針を示しているヘッダを生成する。これらの命
令のそれぞれは、位置データを常に生成し、かつ状態レ
ジスタの値により、カラーまたはノーマル・データを含
みうる。ノーマル・コンポーネントの３つの全ては、並
列に送られ、各位置及びカラー・コンポーネントは、別
々に送られるのが好ましい。パススルー命令は、好まし
くは３２ビットのデータを収集（コレクション）バッフ
ァに送る。

【００５６】

【表４】表３ ────────────────────────コンポーネント フォーマット ヘッダ ３２． 位置 ｓ．１５ カラー ｓ．１５ ノーマル ｓ１．１４（ｘ３）パススルー ３２．

【００５７】図３１は、図３０に示した入力ブロック２
１０の詳細ブロック図である。好ましくは、６４ビット
入力レジスタ３００は、レジスタ３００に装填されると
きに３２ビットまたは６４ビットで、インターフェイス
１３０のＡＰＤＦ部分からデータを受け取る。レジスタ
３００は、その出力がレジスタ３３０を通ってマージ装
置３４０にパスする第１のバレル・シフタ３２０にマル
チプレクサ３１０を介して一度に好ましくは３２ビット
を出力する。マージ装置３４０からの６４ビット出力
は、データ・レジスタ３５０に入力され、その出力の一
部は、第２のバレル・シフタ３６０への入力としてリタ
ーンされる。第２のバレル・シフタ３６０からの出力
は、レジスタ３７０を通してパスされかつマージ装置３
４０へも入力される。第１のバレル・シフタ３２０は、
第２のバレル・シフタ３６０を通してデータ・レジスタ
３５０からリサイクルされるビット位置合わせデータ・
ストリームの末端にデータを位置合わせする。第２のバ
レル・シフタ３６０は、データ・レジスタ３５０から使
用済みビットをシフト・オフする。図３２は、図３０に
示したバレル・シフタ装置２４０の詳細ブロック図であ
る。概観で、バレル・シフタ装置２４０は、可変長位
置、カラー、及びノーマル・インデックス・コンポーネ
ントをそれらの固定点精度まで拡張する。装置２１０及
び／又は２２０から装置２４０へのデータは、その出力
が画定オプコードとして示されるレジスタ４００及び／
又はデータ装置４１０、４２０、４３０、４４０、４５
０、及び４６０に入力され、マルチプレクサ装置４７０
に入力される。

【００５８】マルチプレクサ装置４７０では、入力Ａ
は、頂点命令のＸコンポーネントに用いられ、入力Ｂ
は、セット・ノーマル命令及びセット・カラー命令の第
１のコンポーネントに用いられ、かつ入力Ｃは、頂点及
びセット・カラー命令の残っているコンポーネントに用
いられる。装置４８０は、ｔａｇ＿ｌｅｎデータを受け
取りかつ、その出力が次いでｄａｔａ＿ｌｅｎデータを
受け取るべく結合されるバレル・シフタ・ライト・レジ
スタ５００に入力される、レジスタ４９０へ出力すべく
結合されたバレル・シフタ・レフト・レジスタ４８０を
更に含む。レジスタ５００は、シフトｄａｔａを受け取
るべく結合されかつその出力が、ｖ＿ｄａｔａを出力す
る、レジスタ５２０に結合されるマスク装置５１０に出
力する。データ・ブロック４６０の出力は、その出力
が、ｐｔ＿ｄａｔａを出力する、第２のレジスタ５４０
に結合されるレジスタ５３０に結合される。ハフマン表
２３０（図３０参照）内の適切な表は、ｔａｇ＿ｌｅ
ｎ、ｄａｔａ＿ｌｅｎ、及びシフトを装置４８０、５０
０及び５１０にそれぞれ供給する。バレル・シフタ・レ
フト装置４８０は、０から６ビットだけ左に入力データ
をシフトし（ｔａｇ＿ｌｅｎ）、それゆえにハフマン・
タグをシフト・オフする。対照的、バレル・シフタ・ラ
イト・レジスタ５００は、０から１６ビットだけ右にデ
ータをシフトし（１６−ｄａｔａ＿ｌｅｎ）、サインが
データを拡張し、それゆえに、データをその全サイズに
させる。マスク装置５１０は、正しい量子化レベルにデ
ータをクランプするために下位“シフト”ビットをマス
ク・オフする。図３３は、図３０に示した位置／カラー
・プロセッサ装置２８０のより詳細なブロック図を示
す。プロセッサ装置２８０は、最終位置及びカラー・コ
ンポーネント値を生成する。図３０及び図３２に示した
ように、プロセッサ装置２８０は、バレル・シフタ装置
２４０、特にその中のマスク装置５１０、から好ましく
は１６ビット値（ｖ＿ｄａｔａ）を受け取る。

【００５９】ハフマン表２３０からのａｂｓ＿ｒｅｌビ
ットが相対的(relative)にセットされたならば、入力デ
ータは、結合器装置６００によってに適切な現行記憶デ
ータに加えられる。新しい値は、マルチプレクサ６１０
を通過し、かつレジスタ６２０に戻り記憶され、かつ図
３０に示すように、出力マルチプレクサ２９０に沿って
送られる。しかし、ａｂｓ＿ｒｅｌビットが絶対的(abs
olute)に設定されたならば、入力データは、加算器６０
０をバイパスし、レジスタ６２０にラッチされ、かつま
た出力マルチプレクサ２９０に送り出される。図３３に
示すように、位置／カラー・プロセッサ装置２８０は、
レジスタ６２０への入力を受け取るべく結合される位置
／カラー・メッシュ・バッファ６３０を更に含む。メッ
シュ・バッファ６３０からの出力は、その出力がｘ、
ｙ、ｚ、ｒ、ｇ、ｂ及びαの現行値(current values)を
反映する、集合的に６４０で示された、マルチプレクサ
・ゲートに結合される。集合的に６５０として示され
た、レジスタ・セットは、その出力が加算器６００に結
合されるマルチプレクサ６６０の入力にこれらの現行値
を供給する。プロセッサ装置２８０は、バレル・シフタ
装置２４０からのｐｔ＿ｄａｔａを受取りかつ出力する
レジスタ６７０を更に含む。

【００６０】図３０に示すように、ノーマル・プロセッ
サ装置２７０は、また、出力マルチプレクサ２９０にデ
ータを出力する。図３４は、ノーマル・プロセッサ装置
２７０を含んでいるサブユニットを詳細に示す。図３０
及び図３２に示したように、ノーマル・プロセッサ装置
２７０は、３つの分離コンポーネント、即ち、セクスタ
ント／オクタント、ｕ及びｖ、またはバレル・シフタ装
置２４０のマスク装置５１０からの符号化されたΔｕ及
びΔｖコンポーネント、として１８ビット・ノーマル・
インデックスを受取る。値がΔ値（相対的）であるなら
ば、Δｕ及びΔｖは、対応加算器７１０によって現行ｕ
及びｖ値に加えられる。中間値は、記憶されかつまたデ
コーダ−フォールド−ロム(decoder-fold-rom)装置２７
２（図３５参照）に関連付けられたフォールド(fold)装
置８００にパスされる。図３４に示すように、ノーマル
・プロセッサ装置２７０は、対応オクタント、セクスタ
ント、ｕ及びｖ値、ｃｕｒｒ＿ｏｃｔ、ｃｕｒｒ＿ｓｅ
ｘｔ、ｃｕｒｒ＿ｕ、及びｃｕｒｒ＿ｖ値を保持するレ
ジスタ７１２、７１４、７１６、７１８、７２０、７２
２、７２４、７２６を更に含む。また、装置２７０に存
在するのは、マルチプレクサ７４０、７４２、７４４、
７４６、７４８、７５０、７５２、７５４、７５６、７
５８及び７６０、１の補数装置７７０、７７２、対応
ｖ、ｕ及びｕｖ情報を保持するラッチ−フリップフロッ
プ装置７８０、７８２、７８４、更なる加算器７９０、
７９２、及びｃｕｒｒ＿ｎｏｒｍａｌ入力コンポーネン
トを受け取るべく結合されたノーマル・メッシュ・バッ
ファ７９４である。図３４及び３５に関して、絶対基準
(absolute reference)に対して、ｕ及びｖ値は、フォー
ルド装置８００に直接パスされる。インデックスのオク
タント及びセクスタント部分は、装置２７２内の、デコ
ーダ８１０に送られる。デコーダ８１０は、（定数を選
択する）マルチプレクサ８２０、並びに、コンポーネン
トを再順序付けし、かつ（２の補数装置８５０、８５
２、８５４を用いて）サインを逆にするマルチプレクサ
８４０、８４２、８４４、８６０、８６２、８６４を制
御する。

【００６１】フォールド装置８００は、ノーマル・ルッ
クアップ表ＲＯＭ８３０へのアドレスを計算するため
に、装置２７０からの、ノーマル・インデックスのｕ及
びｖコンポーネントを用いる。装置２７０からの、オク
タント及びセクスタント・フィールドは、ＲＯＭルック
アップ表８３０から出力されるコンポーネントのサイン
及び順番を決定するデコーダ８１０を駆動する。また、
デコーダ８１０は、ノーマルＲＯＭルックアップ表８３
０に含まれない特別の場合のノーマルを処理する。図３
６は、図３３及び／又は図３４に示したような、メッシ
ュ・バッファへのインターフェイスを示す。好ましい実
施例では、メッシュ・バッファ７９４は、レジスタ・フ
ァイル及び現行位置へのポインタとしてインプリメント
される。データは、現行位置ポインタの位置におけるメ
ッシュ・バッファＦＩＦＯに入力される。しかしなが
ら、１６の位置のいずれかへのランダム・アクセスは、
このポインタをインデックシング・オフ(indexing off)
することによってＦＩＦＯからデータを読み出すときに
許容される：アドレス＝（ｃｕｒｒ＿ｌｏｃ＿ｐｔｒ−
インデックス）ｍｏｄ１６。図３７は、ホフマン表、例
えば、図３０の表２３０へのインターフェイスを示す。
ホフマン表は、圧縮データに先行しているホフマン・タ
グを復号するために用いる。３つのホフマン表が用いら
れる：各表が６４のエントリを保持しているのが好まし
く、位置に対して一つ、カラーに対して一つ、ノーマル
・データに対して一つ。

【００６２】図３８は、ホフマン表における位置及びカ
ラー・データのエントリに対して好ましいフォーマット
を示し、図３９は、ノーマル表エントリに対する好まし
いフォーマットを示す。圧縮データ・ストリームにホフ
マン表を装填するための命令フォーマットは、後で説明
する。複数の命令は、図３０に示した、フォーマット変
換器２９２に対するデータを生成し、かつフォーマット
変換器がデータを正確に処理できるように、適当なタグ
がこのデータに対して生成されなければならない。以下
に示す、表４は、異なるデータ・コンポーネントに対し
て生成されるタグを示す。二つのタグを示すコンポーネ
ントは、ランチ(launch)・ビットを設定しうるし、第２
のタグは、設定されたランチ・ビットを有する値を示
す。

【００６３】

【表５】 表４ ───────────────────────────── コンポーネント タグ ヘッダ ０ｘ０２０ Ｘ ０ｘ０１１ Ｙ ０ｘ０１２ Ｚ ０ｘ０１３／０ｘ４１３ Ｎｘ／Ｎｙ／Ｎｚ ０ｘ０１８／０ｘ４１８ Ｒ ０ｘ０１４ Ｇ ０ｘ０１５ Ｂ ０ｘ０１６／０ｘ４１６ Ａ ０ｘ０１７／０ｘ４１７ Ｕ ０ｘ０ｃ０／０ｘ４ｃ０ Ｖ ０ｘ０１ｃ／０ｘ４１ｃ

【００６４】入力ブロック状態マシン２２０（図３０参
照）は、圧縮解除装置の処理状態に関する情報を保持す
る６ビット状態レジスタを含むのが好ましい。好ましい
実施例では、次の状態ビットが定義される： ビット５： ｔｅｘ−カラーの代わりのテキスチャ値 ビット４： ｒｎｔ−頂点当たりの複製（再現）ノーマ
ル ビット３： ｒｃｔ−頂点当たりの複製（再現）カラー ビット２： ｂｎｖ−頂点にバンドルされたノーマル ビット１： ｂｃｖ−頂点にバンドルされたカラー ビット０： ｃａｐ−アルファ（α）を含むカラー

【００６５】位置／カラー・プロセッサ装置２８０（図
３０及び図３３参照）は、現行位置コンポーネント、
Ｘ、Ｙ、及びＺを含み、かつ頂点命令によってのみ更新
される、３つの１６ビット・レジスタ、ｃｕｒｒ＿ｘ、
ｃｕｒｒ＿ｙ、及びｃｕｒｒ＿ｚを含むのが好ましい。

【００６６】ノーマル・プロセッサ装置２７０（図３０
及び図３４）は、現行ノーマルを含む、３つの６ビット
・レジスタ、ｃｕｒｒ＿ｏｃｔ、ｃｕｒｒ＿ｓｅｘｔ、
ｃｕｒｒ＿ｕ、及びｃｕｒｒ＿ｖを含むのが好ましい。
第１のレジスタは、３ビットセクスタット及びオクタン
ト・フィールドを保持し、かつ残り２つのレジスタは、
ノーマルに対するｕ及びｖ座標を含む。これらの値は、
セット・ノーマル命令を用いて書き込まれるか、または
それらは、ｂｎｖビットが状態レジスタに設定されるな
らば頂点命令によって更新される。位置／カラー・プロ
セッサ２８０は、現行カラー・コンポーネント、赤、
緑、青及びアルファ（α）を含む、４つの１６ビット・
レジスタ、ｃｕｒｒ＿ｒ、ｃｕｒｒ＿ｇ、ｃｕｒｒ＿
ｂ、ｃｕｒｒ＿ａを更に含むのが好ましい。これらのコ
ンポーネントは、ｓｅ５ｔカラー命令を用いて設定され
るか、またはそれらは、ｂｃｖビットが状態レジスタに
設定されるならば頂点命令によって更新される。好まし
い実施例では、アルファは、キャップ・ビットが状態レ
ジスタに設定されるときにだけ有効である。テスト・ビ
ットは、赤及び緑だけが有効である場合のような、テキ
スチャ・コンポーネントを処理するときに設定される。

【００６７】ここで、本発明による圧縮解除をインプリ
メントする命令セットを説明する。図４０は、頂点命令
フォーマット、頂点を表わすために可変長ハフマン・符
号化を用いる命令を示す。位置情報は、この命令に常に
存在する。 （ＲＥＰ）頂点置換ポリシーは、次のようである： ００−時計方向に再スタートする ０１−反時計方向に再スタートする １０−中間を置換する １１−最古を置換する （Ｍ）− メッシュ・バッファをプッシュする： ０−プッシュしない １−プッシュする

【００６８】図４０を参照すると、位置データは、可変
長ハフマン・タグ（０から６ビット）に続いて、Δ値ま
たは絶対値のいずれかである、Ｘ、Ｙ、及びＺコンポー
ネントについて同じ長さの３つのデータ・フィールドを
含む。位置ハフマン表におけるエントリに対するｄａｔ
ａ＿ｌｅｎフィールドは、Ｘ、Ｙ、及びＺフィールドの
それぞれの長さを与え、ｔａｇ＿ｌｅｎエントリは、タ
グの長さを与え、ａｂｓ＿ｒｅｌエントリは、データが
絶対データであるかまたは先の頂点に相関するかを告げ
る。ハフマン表からのシフト・エントリは、データに対
する量子化レベル（後続しているゼロの数）を与える。
ｂｎｖビットが状態レジスタに設定されたならば、ノー
マルが含まれる。符号化されたノーマルは、Δｕ及びΔ
ｖに対する二つの可変長データ・フィールド、またはｕ
及びｖに対する二つの可変長フィールドを後続するセク
スタント及びオクタント（６ビット）に対する固定長フ
ィールドのいずれかを後続するハフマン・タグを有す
る。前者の符号化は、ノーマルのデルタ符号化に対して
であり、後者の符号化は、絶対符号化に対してである。
ノーマル・ハフマン表からのｄａｔａ＿ｌｅｎ、ｔａｇ
＿ｌｅｎ、ａｂｓ＿ｒｅｌ、及びシフト・フィールド
は、位置表からのエントリと同様に用いられる。

【００６９】図４１は、頂点コンポーネント・データ・
フォーマットを示す。状態レジスタのｂｃｖビットがセ
ットされたならば、カラーは、頂点を伴って含まれる。
カラーは、３つまたは４つのフィールドを用いて位置に
類似して符号化されるが、しかしどのようにフィールド
が用いられるかは、タグ表によって決定される。絶対的
であるとタグ付けされたならば、ｘ、ｙ、ｚ、ｒ、ｇ、
ｒデータが用いられる。絶対ノーマルは、セクスタント
及びオクタント・フィールドで用いられる。しかしなが
ら、タグ表が相対的を示すならば、デルタ・ノーマルが
用いられ、かつそれは、緯度及び経度データを送るため
に十分である（例えば、ここでｕ及びｖとしても参照さ
れる、θ及びΦ）。図４１を更に参照すると、ハフマン
・タグは、Ｒ、Ｇ、及びＢに対して３つの同長フィール
ドにより後続される。状態レジスタのキャップ・ビット
は、αに対する追加フィールドが含まれるか否かという
ことを示す。カラー・ハフマン表からのｄａｔａ＿ｌｅ
ｎ、ｔａｇ＿ｌｅｎ、ａｂｓ＿ｒｅｌ、及びシフト・フ
ィールドは、位置及びノーマル表からのエントリに対す
るのと同様に用いられる。

【００７０】頂点命令セットの状態は、次に示すようで
ある： １．次のｏｐｃｏｄｅをラッチする；Ｘを出力する；ｐ
ｔａｇ＿ｌｅｎ＋ｐｄａｔａ＿ｌｅｎ−ｐｑｕａｎｔ＋
２だけバレル・シフト右装置５００（図３２参照）をシ
フトする。 ２．マージする；ヘッダを出力する。 ３．Ｙを出力する；ｐｄａｔａ＿ｌｅｎ−ｐｑｕａｎｔ
だけバレル・シフタ右装置５００（図３２参照）をシフ
トする。 ４．マージする ５．Ｚを出力する；ｐｄａｔａ＿ｌｅｎ−ｐｑｕａｎｔ
だけバレル・シフタ右装置５００（図３２参照）をシフ
トする。 ６．マージする ａ．（ｂｎｖ）であれば ｉ． （絶対ノーマル）であれば、７へ行く、 ｉｉ．さもなければ、９へ行く。／＊相対ノーマル＊／ ｂ．さもなくば（ｒｎｔ）ならば、２１へ行く、 ｃ．さもなくば（ｂｃｖ）ならば、１３へ行く、 ｅ．さもなくばマージする；次の命令へ分枝する。 ７．次のｏｐｃｏｄｅをラッチする；セクスタント／オ
クタントを出力する；ｎｔａｇ ｌｅｎ＋６だけバレル
・シフト右装置５００（図３２参照）をシフトする。 ８．マージする。 ９．Ｕを出力する。 ａ．（絶対ノーマル）であれば、ｎｄａｔａ＿ｌｅｎ−
ｎｑｕａｎｔだけバレル・シフト右装置５００（図３２
参照）をシフトする。 ｂ．さもなくば／＊相対ノーマル＊／、次のｏｐｃｏｄ
ｅをラッチする；ｎｔａｇ＿ｌｅｎ＋ｎｄａｔａ＿ｌｅ
ｎ−ｎｑｕａｎｔだけＢｓ２をシフトする １０．マージする。 １１．Ｖを出力する。 １２．マージする。 ａ．（ｂｃｖ）であれば、１３へ行く、 ｂ．さもなくば（ｒｃｔ）ならば、２２へ行く、 ｃ．さもなくばマージする；次の命令へ分枝する。 １３．次のｏｐｃｏｄｅをラッチする；Ｒを出力する；
ｃｔａｇ＿ｌｅｎ＋ｃｄａｔａ＿ｌｅｎ−ｃｑｕａｎｔ
だけバレル・シフト右装置５００（図３２参照）をシフ
トする。 １４．マージする。 １５．Ｇを出力する；ｃｄａｔａ＿ｌｅｎ−ｃｑｕａｎ
ｔだけバレル・シフタ右装置５００（図３２参照）をシ
フトする。 １６．マージする；（ｔｅｘ）であれば、次の命令へ分
枝する。 １７．Ｂを出力する；ｃｄａｔａ＿ｌｅｎ−ｃｑｕａｎ
ｔだけバレル・シフタ右装置５００（図３２参照）をシ
フトする。 １８．マージする；（^- ｃａｐ）であれば、次の命令へ
分枝する。 １９．Ａを出力する；ｃｄａｔａ＿ｌｅｎ−ｃｑｕａｎ
ｔだけバレル・シフタ右装置５００（図３２参照）をシ
フトする。 ２０．マージする；次に命令へ分枝する。 ２１．ｃｕｒｒ＿ｎｏｒｍａｌを出力する。 ａ．（ｂｃｖ）であれば、１３へ行く、 ｂ．さもなくば（ｒｃｔ）ならば、２２へ行く、 ｃ．さもなくばマージする；次の命令へ分枝する。 ２２．ｃｕｒｒ＿ｒを出力する。 ２３．ｃｕｒｒ＿ｇを出力する。（ｔｅｘ）であれば、
マージする；次の命令に分枝する ２４．ｃｕｒｒ＿ｂを出力する。（^- ｃａｐ）であれ
ば、マージする；次の命令へ分枝する。 ２５．ｃｕｒｒ＿ａを出力する。マージする；次の命令
へ分枝する。

【００７１】図４２は、セット・ノーマル命令に対する
フォーマットを示す。セット・ノーマル命令は、現行ノ
ーマル・レジスタの値を設定する。ノーマル・データ
は、ここの、示された、頂点命令におけるノーマル・デ
ータと同様に符号化される。セット・ノーマル命令の状
態は、次の通りである： （絶対ノーマル）であれば １．次のｏｐｃｏｄｅをラッチする；セクスタント／オ
クタントを出力する；ｎｔａｇ＿ｌｅｎ＋８だけバレル
・シフト右装置５００（図３２参照）をシフトする。 ２．マージする。 ３．Ｕを出力する；ｎｄａｔａ＿ｌｅｎ−ｎｑｕａｎｔ
だけバレル・シフタ右装置５００（図３２参照）をシフ
トする。 ４．マージする。 ５．Ｖを出力する；ｎｄａｔａ＿ｌｅｎ＋ｎｑｕａｎｔ
だけバレル・シフタ右装置５００（図３２参照）をシフ
トする。 ６．マージする；次の命令へ分枝する。 さもなくば／＊相対ノーマル＊／ １．次のｏｐｃｏｄｅをラッチする；ｄＵを出力する；
ｎ＿ｔａｇ＿ｌｅｎ＋ｎｄａｔａ＿ｌｅｎ−ｎｑｕａｎ
ｔだけバレル・シフト右装置５００（図３２参照）をシ
フトする。 ２．マージする。 ３．ｄＶを出力する；ｎｄａｔａ＿ｌｅｎ−ｎｑｕａｎ
ｔだけバレル・シフタ右装置５００（図３２参照）をシ
フトする。 ４．マージする；次の命令へ分枝する。

【００７２】図４３は、現行カラー・レジスタの値を設
定する命令である、セット・カラー命令を示す。頂点命
令におけるカラー・データの符号化は、カラー・データ
の符号化に類似する。セット・カラー命令の状態は、次
のようである： １．次のｏｐｃｏｄｅをラッチする；Ｒを出力する；ｃ
ｔａｇ＿ｌｅｎ＋ｃｄａｔａ＿ｌｅｎ−ｃｑｕａｎｔ＋
２だけバレル・シフト右装置５００（図３２参照）をシ
フトする。 ２．マージする。 ３．Ｇを出力する；ｃｄａｔａ＿ｌｅｎ−ｃｑｕａｎｔ
だけバレル・シフタ右装置５００（図３２参照）をシフ
トする。 ４．マージする。（ｔｅｘ）ならば、次の命令へ分枝す
る。 ５．Ｂを出力する；ｃｄａｔａ＿ｌｅｎ−ｃｑｕａｎｔ
だけバレル・シフタ右装置５００（図３２参照）をシフ
トする。 ６．マージする；（^- ｃａｐ）であれば、次の命令へ分
枝する。 ７．Ａを出力する；ｃｄａｔａ＿ｌｅｎ−ｃｑｕａｎｔ
だけバレル・シフタ右装置５００（図３２参照）をシフ
トする。 ８．マージする；次の命令へ分枝する。

【００７３】図４４は、メッシュ・バッファ基準命令に
対する好ましいフォーマットである。この命令は、メッ
シュ・バッファにおけるエントリからのデータを次の頂
点としてフォーマット変換器へ送り出させる。図４４に
関して、インデックスは、送るべきメッシュ・バッファ
からのエントリを示す。メッシュ・バッファにおける最
新のエントリは、インデックス０を有し、かつ最古のも
のは、インデックス１５を有する。ＲＥＰ、頂点命令に
対する上述した置換ポリシーは、メッシュ・バッファ基
準命令に対して用いられたものと同じである。メッシュ
・バッファ基準命令に対する状態は、次の通りである： １．次のｏｐｃｏｄｅをラッチする；ヘッダ(Header)を
出力する；９だけバレル・シフト右装置５００（図３２
参照）をシフトする。 ２．メッシュ・バッファからＸを出力する。 ３．メッシュ・バッファからＹを出力する。 ４．メッシュ・バッファからＺを出力する。 ａ．（ｂｎｖまたはｒｎｔ）ならば５へ行く、 ｂ．さもなければ（ｂｃｖまたはｒｃｔ）ならば６へ行
く、 ｃ．さもなければマージする；次の命令へ分枝する。 ５．（ｂｎｖ）ならば、メッシュ・バッファからノーマ
ルを出力し、さもなければ（ｒｎｔ）ならばｃｕｒｒ＿
ｎｏｒｍａｌを出力する。 ａ．（ｂｎｖまたはｒｃｔ）ならば６へ行く、 ｂ．さもなければマージする；次の命令へ分枝する。 ６．（ｂｃｖ）ならば、メッシュ・バッファからＲを出
力し、さもなければ、（ｒｃｔ）ならばｃｕｒｒ＿ｒを
出力する。 ７．（ｂｃｖ）ならば、メッシュ・バッファからＧを出
力し、さもなければ、（ｒｃｔ）ならばｃｕｒｒ＿ｇを
出力する。（ｔｅｘ）ならば、マージする；次の命令へ
分枝する。 ８．（ｂｃｖ）ならば、メッシュ・バッファからＢを出
力し、さもなければ、（ｒｃｔ）ならばｃｕｒｒ＿ｂを
出力する。（^- ｃａｐ）ならば、マージする；次の命令
へ分枝する。 ９．（ｂｃｖ）ならば、メッシュ・バッファからＡを出
力し、さもなければ、（ｒｃｔ）ならばｃｕｒｒ＿ａを
出力する。マージする；次の命令へ分枝する。

【００７４】図４５は、ビットを圧縮解除装置状態レジ
スタに設定するセット状態命令を示す。セット状態命令
に対する状態は、次の通りである： １．次のｏｐｃｏｄｅをラッチする；１１ビットだけバ
レル・シフタ２をシフトする。 ２．マージする；命令を分枝する

【００７５】図４６は、ハフマン表エントリを設定する
セット表命令を示す。表選択は、次の通り： ００−位置表 ０１−カラー表 １０−ノーマル表 １１−未画定

【００７６】タグ長は、アドレスから導出される。エン
トリ・フィールドの９ビットは、ハフマン表エントリの
絶対／相対ビット、データ長、及びシフト量フィールド
に対応する。（ハフマン表エントリの好ましいフォーマ
ットは、前述した。）セット表命令の状態は、次の通り
である： １．次のｏｐｃｏｄｅをラッチする；アドレス及びエン
トリをハフマン表へ送る；２３ビットだけバレル・シフ
ト右装置をシフトする。 ２．マージする；次の命令へ分枝する 表５は、好ましいハフマン表充填コードを示す。

【００７７】

【表６】 表５ ───────────────────────────────────アドレス 充填されたエントリ タグ長 充填範囲 ０ｔｔｔｔｔｔ １ ６ ｔｔｔｔｔｔ １０ｔｔｔｔｔ ２ ５ ｔｔｔｔｔ０− ｔｔｔｔｔ１ １１０ｔｔｔｔ ４ ４ ｔｔｔｔ００− ｔｔｔｔ１１ １１１０ｔｔｔ ８ ３ ｔｔｔ０００− ｔｔｔ１１１ １１１１０ｔｔ １６ ２ ｔｔ００００− ｔｔ１１１１ １１１１１０ｔ ３２ １ ｔ０００００− ｔ１１１１１ １１１１１１０ ６４ ０ Ｅｎｔｉｒｅ ｔａｂｌｅ

【００７８】図４７は、パススルー・データを圧縮デー
タ・ストリームにおいて符号化させるパススルー命令を
示す。命令の長さは、６４ビットであるのが好ましい。
６４ビット・バウンダリーに後続パススルー命令を位置
合わせすることは、符号化されたストリームにおけるパ
ススルー・データのパッチングを許容する。パススルー
命令に対する状態は、次の通りである： １．次のｏｐｃｏｄｅをラッチする；アドレスを読取
り、３２だけバレル・シフト右装置５００（図３２参
照）をシフトする。 ２．マージする。 ３．データを出力し、３２だけバレル・シフト右装置５
００（図３２参照）をシフトする。 ４．マージする；次の命令へ分枝する。

【００７９】図４７は、データ・ストリームにおける０
ビットの変数を符号化する、可変長ＮＯＰ（“ＶＮＯ
Ｐ”）命令を示す。図４７に示した５ビット・カウント
は、その後に続く０ビットの数を指定する。この命令
は、データ・ストリームの開始に暗黙的に用いられる。
この命令は、また、データ・ストリームを３２ビットま
たは６４ビット・バウンダリー、または後のパッチング
のために、符号化領域にパッドする（埋め込む）ために
も用いられうる。この命令の状態は、次の通り： １．次のｏｐｃｏｄｅをラッチする；１３だけバレル・
シフト右装置５００（図３２参照）をシフトする。 ２．マージする。 ３．バレル・シフト右装置が“カウント”位置を読取
る； ４．マージする；次の命令へ分枝する。

【００８０】図４９は、その状態が次に示すような、ス
キップ８命令を示す： １．次のｏｐｃｏｄｅをラッチする；１６だけバレル・
シフト右装置５００（図３２参照）をシフトする。 ２．マージする；次の命令へ分枝する。

【００８１】圧縮解除システムにおける単一点でデータ
・ストリームを圧縮解除しないで装置間の帯域幅要求を
低減することが有利でありうるということが理解され
る。本発明は、並列に処理されうる所与の数のデータ・
ワードの到着を助言する追加指令を供給することによっ
てインプリメントを供給することによってデータ・スト
リームの並列圧縮解除を供給することができる。本発明
は、マーク・ビットの存在によってそのような並列の機
会の存在を認識することができ、かつ並列圧縮解除に対
して、そこでの状態数(stated number)のデータ・ワー
ドの発生がシステム内の他のプロセッサにシャトルされ
る。更に、並列処理に対して権利が無い次のデータに到
着すべくデータ・ストリームにおける所与の数のワード
を先にジャンプさせることを許容できる。また、本発明
は、圧縮解除された三次元オブジェクトを見ることにお
いてあらゆる突然の知覚空隙を取り除くためにモーフィ
ング・ケイパビリティを供給することもできる。圧縮解
除されたデータ・ストリーム内では、実際に存在するか
または先に圧縮解除された頂点の線形または他の補間
（内挿）として頂点を指定することが可能である。例え
ば、三次元オブジェクトが虎であると想定する。遠距離
では、虎の口には歯が存在しないが、近距離では、歯が
存在する。本発明は、虎との距離が短くなると、歯が成
長し、歯無し虎と歯有り虎との間の突然の変化のシーン
がないようなシームレス・トランザクションを提供する
ことができる。変更及び変形は、特許請求の範囲によっ
て画定されるような本発明の対象及び精神から逸脱する
ことなく開示された実施例に対してなされうる。

【００８２】

【発明の効果】本発明の方法は、可変長フィールドのデ
ータ・ストリームを圧縮解除する方法であり、該データ
・ストリームが該フィールドの圧縮解除を三次元オブジ
ェクトの非圧縮表面特性にガイドする、オプ・コード・
ビット及び／又はタグ・ビットを含んでいる、方法であ
って、（ａ）フィールド型をデータ・ストリームから検
出し、そのような検出をイネーブルするデータは、先行
するが該データ・ストリーム内でシーケンシャルにすぐ
に先行する必要はない、（ｂ）フィールド長及び／又は
フィールド正規化をデータ・ストリームから検出し、そ
のような検出をイネーブルするデータは、先行するが該
データ・ストリーム内でシーケンシャルにすぐに先行す
る必要はない、（ｃ）段階（ａ）及び段階（ｂ）の少な
くとも一つから得られた情報を用いて、データ・ストリ
ームからビット位置合わせされたフィールドを抽出し、
（ｄ）最初の数値スケールに抽出したビット位置合わせ
されたフィールドを必要に応じて再正規化し、（ｅ）圧
縮解除された表面記述データを出力する段階を具備し、
データは、オプションで汎用三角形ストリップ・フォー
マットであるので、出力データが描画命令として直接レ
ンダリング・ハードウェアにわたされるように圧縮され
た三次元幾何学形状を圧縮解除することができる。ま
た、本発明のシステムは、オプ・コード・ビット及び／
又はタグ・ビットを含み、その表面が表面特性を画定す
る三次元オブジェクトを表している圧縮データを含み、
そのフィールドが長さにおいて変化することができる、
データ・ストリームを圧縮解除する、中央処理装置（Ｃ
ＰＵ）及び当該ＣＰＵに結合されたメモリを含んでいる
コンピュータ・システムに使用可能な、システムであっ
て、データ・ストリームを受け取りかつすぐ後に続くフ
ィールドのデータ・ストリーム・フィールド情報におけ
る先行しているが、すぐにシーケンシャルに先行してい
ることを必要としない、フィールドから検出すべくプロ
グラムされた検出器装置と、フィールド情報は、フィー
ルド型及びフィールド長及び／又はフィールド正規化を
含んでおり、検出器装置によって検出された少なくとも
あるデータを受け取りかつデータ・ストリームからビッ
ト位置合わせされたフィールドを抽出すべくプログラム
された抽出器装置とを備えているので、出力データが描
画命令として直接レンダリング・ハードウェアにわたさ
れるように圧縮された三次元幾何学形状を圧縮解除する
ことができる。

【図面の簡単な説明】

【図１】本発明による、受信端で、圧縮された三次元幾
何学形状がその上で圧縮解除のために送信されうる、一
般化されたネットワーク・システムを示す図である。

【図２】一般化された三角形状メッシュ・データ構造、
及び表面幾何学形状の一般化されたメッシュ・バッファ
表現を示す図である。

【図３】本発明による、表ルック−アップ・サイズにお
ける４８の低減方法を供給すべく用いられる、単位球に
おける６方向単一ビット及び８方向オクタント（八分
儀）対称を示す図である。

【図４】本発明による、幾何学形状圧縮命令セットにお
ける頂点指令を示す図である。

【図５】本発明による、幾何学形状圧縮命令セットにお
けるノーマル指令を示す図である。

【図６】本発明による、幾何学形状圧縮命令セットにお
けるカラー指令を示す図である。

【図７】本発明による、幾何学形状圧縮命令セットにお
けるメッシュ・バッファ参照指令を示す図である。

【図８】本発明による、幾何学形状圧縮命令セットにお
けるセット状態指令を示す図である。

【図９】本発明による、幾何学形状圧縮命令セットにお
けるセットテーブル指令命令を示す図である。

【図１０】本発明による、幾何学形状圧縮命令セットに
おけるパス・スルー指令命令を示す図である。

【図１１】本発明による、幾何学形状圧縮命令セットに
おける可変長ノー・オペレーション(no-op) 指令命令を
示す図である。

【図１２】本発明による、タグ及びΔ−位置データ構造
を示す図である。

【図１３】本発明による、代替のタグ及びΔ−ノーマル
・データ構造を示す図である。

【図１４】本発明による、別の代替のタグ及びΔ−ノー
マル・データ構造を示す図である。

【図１５】本発明による、タグ及びΔ−カラー・データ
構造を示す図である。

【図１６】本発明による、幾何学形状圧縮アルゴリズム
における方法ステップスのフローチャートである。

【図１７】本発明による、デコンプレッサ・ハードウェ
アの簡略ブロック図である。

【図１８】異なる条件下で圧縮されたオブジェクトを示
す図である。

【図１９】異なる条件下で圧縮されたオブジェクトを示
す図である。

【図２０】異なる条件下で圧縮されたオブジェクトを示
す図である。

【図２１】異なる条件下で圧縮されたオブジェクトを示
す図である。

【図２２】異なる条件下で圧縮されたオブジェクトを示
す図である。

【図２３】異なる条件下で圧縮されたオブジェクトを示
す図である。

【図２４】異なる条件下で圧縮されたオブジェクトを示
す図である。

【図２５】異なる条件下で圧縮されたオブジェクトを示
す図である。

【図２６】異なる条件下で圧縮されたオブジェクトを示
す図である。

【図２７】異なる条件下で圧縮されたオブジェクトを示
す図である。

【図２８】異なる条件下で圧縮されたオブジェクトを示
す図である。

【図２９】異なる条件下で圧縮されたオブジェクトを示
す図である。

【図３０】本発明による、デコンプレッサ装置の詳細全
体ブロック図である。

【図３１】図３０に示した入力ブロック図の詳細全体ブ
ロック図である。

【図３２】図３０に示したバレル・シフタ装置の詳細ブ
ロック図である。

【図３３】図３０に示した位置／カラー・プロセッサ装
置の詳細ブロック図である。

【図３４】図３０に示したノーマル・プロセッサ装置の
詳細ブロック図である。

【図３５】図３４のノーマル・プロセッサ装置に関連付
けられたデコーダ、フォールド、及びＲＯＭルック−ア
ップ・コンポーネントを示している詳細ブロック図であ
る。

【図３６】図３３及び／又は図３４に示したような、メ
ッシュ・バッファへのインターフェイスを示しているブ
ロック図である。

【図３７】本発明による、ハフマン表へのインターフェ
イスを示す図である。

【図３８】本発明による、ハフマン表データのエントリ
に対する好ましいフォーマットを示す図である。

【図３９】本発明による、ハフマン表データのエントリ
に対する好ましいフォーマットを示す図である。

【図４０】本発明による、頂点命令を示す図である。

【図４１】本発明による、頂点コンポーネント・データ
・フォーマットを示す図である。

【図４２】本発明による、セット・ノーマル指令に対す
るフォーマットを示す図である。

【図４３】本発明による、セット・カラー指令を示す図
である。

【図４４】本発明による、メッシュ・バッファ参照指令
を示す図である。

【図４５】本発明による、セット状態指令を示す図であ
る。

【図４６】本発明による、セット・テーブル指令を示す
図である。

【図４７】本発明による、パススルー指令を示す図であ
る。

【図４８】本発明による、可変長ＮＯＰ指令を示す図で
ある。

【図４９】本発明による、スキップ８指令を示す図であ
る。

【符号の説明】

１０ 三次元グラフィックス発生源 ２０ サーバ ３０ ネットワーク ４０ デコーダ ５０ 中央処理装置 ６０ ＣＰＵ ７０ 関連主メモリ、ディスク・レイアウト装置 ８０ メッシュ・バッファ、記憶ディスク装置 ９０ メモリ部分 １００ ＲＯＭ １１０、１２０ ネットワーク・インターフェイス １３０ 三次元グラフィックス圧縮解除装置 １４０ 三次元グラフィックス・レンダラー １５０ 中央処理システム １６０ ＣＰＵ １７０ メモリ １８０ メモリ部分 １９０ ＲＯＭ ２００ ディスプレイ

─────────────────────────────────────────────────────

【手続補正書】

【提出日】平成８年１２月２０日

【手続補正１】

【補正対象書類名】明細書

【補正対象項目名】発明の名称

【補正方法】変更

【補正内容】

【発明の名称】 圧縮された幾何学形状三次元グ
ラフィックス・データの圧縮解除のための方法及び装置 ─────────────────────────────────────────────────────

【手続補正書】

【提出日】平成８年１２月２０日

【手続補正１】

【補正対象書類名】明細書

【補正対象項目名】図面の簡単な説明

【補正方法】変更

【補正内容】

【図面の簡単な説明】

【図１】本発明による、受信端で、圧縮された三次元幾
何学形状がその上で圧縮解除のために送信されうる、一
般化されたネットワーク・システムを示す図である。

【図２】一般化された三角形状メッシュ・データ構造、
及び表面幾何学形状の一般化されたメッシュ・バッファ
表現を示す図である。

【図３】本発明による、表ルック−アップ・サイズにお
ける４８の低減方法を供給すべく用いられる、単位球に
おける６方向単一ビット及び８方向オクタント（八分
儀）対称を示す図である。

【図４】本発明による、幾何学形状圧縮命令セットにお
ける頂点指令を示す図である。

【図５】本発明による、幾何学形状圧縮命令セットにお
けるノーマル指令を示す図である。

【図６】本発明による、幾何学形状圧縮命令セットにお
けるカラー指令を示す図である。

【図７】本発明による、幾何学形状圧縮命令セットにお
けるメッシュ・バッファ参照指令を示す図である。

【図８】本発明による、幾何学形状圧縮命令セットにお
けるセット状態指令を示す図である。

【図９】本発明による、幾何学形状圧縮命令セットにお
けるセットテーブル指令命令を示す図である。

【図１０】本発明による、幾何学形状圧縮命令セットに
おけるパス・スルー指令命令を示す図である。

【図１１】本発明による、幾何学形状圧縮命令セットに
おける可変長ノー・オペレーション（ｎｏ−ｏｐ）指令
命令を示す図である。

【図１２】本発明による、タグ及びΔ−位置データ構造
を示す図である。

【図１３】本発明による、代替のタグ及びΔ−ノーマル
・データ構造を示す図である。

【図１４】本発明による、別の代替のタグ及びΔ−ノー
マル・データ構造を示す図である。

【図１５】本発明による、タグ及びΔ−カラー・データ
構造を示す図である。

【図１６】本発明による、幾何学形状圧縮アルゴリズム
における方法ステップスのフローチャートである。

【図１７】本発明による、デコンプレッサ・ハードウェ
アの簡略ブロック図である。

【図１８】異なる条件下で圧縮されたオブジェクトをデ
ィスプレー上に表示した中間調画像を示す写真である。

【図１９】異なる条件下で圧縮されたオブジェクトをデ
ィスプレー上に表示した中間調画像を示す写真である。

【図２０】異なる条件下で圧縮されたオブジェクトをデ
ィスプレー上に表示した中間調画像を示す写真である。

【図２１】異なる条件下で圧縮されたオブジェクトをデ
ィスプレー上に表示した中間調画像を示す写真である。

【図２２】異なる条件下で圧縮されたオブジェクトをデ
ィスプレー上に表示した中間調画像を示す写真である。

【図２３】異なる条件下で圧縮されたオブジェクトをデ
ィスプレー上に表示した中間調画像を示す写真である。

【図２４】異なる条件下で圧縮されたオブジェクトをデ
ィスプレー上に表示した中間調画像を示す写真である。

【図２５】異なる条件下で圧縮されたオブジェクトをデ
ィスプレー上に表示した中間調画像を示す写真である。

【図２６】異なる条件下で圧縮されたオブジェクトをデ
ィスプレー上に表示した中間調画像を示す写真である。

【図２７】異なる条件下で圧縮されたオブジェクトをデ
ィスプレー上に表示した中間調画像を示す写真である。

【図２８】異なる条件下で圧縮されたオブジェクトをデ
ィスプレー上に表示した中間調画像を示す写真である。

【図２９】異なる条件下で圧縮されたオブジェクトをデ
ィスプレー上に表示した中間調画像を示す写真である。

【図３０】本発明による、デコンプレッサ装置の詳細全
体ブロック図である。

【図３１】図３０に示した入力ブロック図の詳細全体ブ
ロック図である。

【図３２】図３０に示したバレル・シフタ装置の詳細ブ
ロック図である。

【図３３】図３０に示した位置／カラー・プロセッサ装
置の詳細ブロック図である。

【図３４】図３０に示したノーマル・プロセッサ装置の
詳細ブロック図である。

【図３５】図３４のノーマル・プロセッサ装置に関連付
けられたデコーダ、フォールド、及びＲＯＭルック−ア
ップ・コンポーネントを示している詳細ブロック図であ
る。

【図３６】図３３及び／又は図３４に示したような、メ
ッシュ・バッファへのインターフェイスを示しているブ
ロック図である。

【図３７】本発明による、ハフマン表へのインターフェ
イスを示す図である。

【図３８】本発明による、ハフマン表データのエントリ
に対する好ましいフォーマットを示す図である。

【図３９】本発明による、ハフマン表データのエントリ
に対する好ましいフォーマットを示す図である。

【図４０】本発明による、頂点命令を示す図である。

【図４１】本発明による、頂点コンポーネント・データ
・フォーマットを示す図である。

【図４２】本発明による、セット・ノーマル指令に対す
るフォーマットを示す図である。

【図４３】本発明による、セット・カラー指令を示す図
である。

【図４４】本発明による、メッシュ・バッファ参照指令
を示す図である。

【図４５】本発明による、セット状態指令を示す図であ
る。

【図４６】本発明による、セット・テーブル指令を示す
図である。

【図４７】本発明による、パススルー指令を示す図であ
る。

【図４８】本発明による、可変長ＮＯＰ指令を示す図で
ある。

【図４９】本発明による、スキップ８指令を示す図であ
る。

【符号の説明】 １０ 三次元グラフィックス発生源 ２０ サーバ ３０ ネットワーク ４０ デコーダ ５０ 中央処理装置 ６０ ＣＰＵ ７０ 関連主メモリ、ディスク・レイアウト装置 ８０ メッシュ・バッファ、記憶ディスク装置 ９０ メモリ部分 １００ ＲＯＭ １１０、１２０ ネットワーク・インターフェイス １３０ 三次元グラフィックス圧縮解除装置 １４０ 三次元グラフィックス・レンダラー １５０ 中央処理システム １６０ ＣＰＵ １７０ メモリ １８０ メモリ部分 １９０ ＲＯＭ ２００ ディスプレイ

───────────────────────────────────────────────────── フロントページの続き (72)発明者 アーロン エス ウィン アメリカ合衆国 カリフォルニア州 94301 パロ アルト 110 ブライアント ストリート 555

Claims (17)

【特許請求の範囲】
1. 【請求項１】 可変長フィールドのデータ・ストリーム
   を圧縮解除する方法であり、該データ・ストリームが該
   フィールドの圧縮解除を三次元オブジェクトの非圧縮表
   面特性にガイドする、オプ・コード・ビット及び／又は
   タグ・ビットを含んでいる、方法であって、（ａ）フィ
   ールド型を前記データ・ストリームから検出し、そのよ
   うな検出をイネーブルするデータは、先行するが該デー
   タ・ストリーム内でシーケンシャルにすぐに先行する必
   要はない、（ｂ）フィールド長及び／又はフィールド正
   規化を前記データ・ストリームから検出し、そのような
   検出をイネーブルするデータは、先行するが該データ・
   ストリーム内でシーケンシャルにすぐに先行する必要は
   ない、（ｃ）段階（ａ）及び段階（ｂ）の少なくとも一
   つから得られた情報を用いて、前記データ・ストリーム
   からビット位置合わせされたフィールドを抽出し、
   （ｄ）最初の数値スケールに抽出した前記ビット位置合
   わせされたフィールドを必要に応じて再正規化し、
   （ｅ）圧縮解除された表面記述データを出力する段階を
   具備し、前記データは、オプションで汎用三角形ストリ
   ップ・フォーマットであることを特徴とする方法。
2. 【請求項２】 前記オプ・コードは、後続するフィール
   ドのセットの型に関する情報を表わし、該情報は、
   （ｉ）頂点情報、（ｉｉ）位置情報、（ｉｉｉ）表面ノ
   ーマル情報、（ｉｖ）カラー、（ｖ）テキスチャ・マッ
   プ座標、（ｖｉ）表面材料特性、及び（ｖｉｉ）手順情
   報、（ｖｉｉｉ）頂点情報、ノーマル指令及びカラー指
   令以外の指令である手順情報からなるグループから選択
   され、及び／又は、 前記タグ・ビットは、（ａ）該タグ・ビットが（ｉ）フ
   ィールド長、（ｉｉ）正規化、（ｉｉｉ）そのようなフ
   ィールドが相対的か否か、（ｉｖ）そのようなフィール
   ドが絶対的か否か、からなるグループから選択された少
   なくとも一つのフィールド特性を暗黙的に記述する、及
   び（ｂ）該タグ・ビットが可変長を有しかつ当該可変長
   についての情報並びに可能フィールド内容情報を含み、
   該可変長は、該フィールド内容情報から独立である、か
   らなるグループから選択された少なくとも一つの特性を
   有することを特徴とする請求項１に記載の方法。
3. 【請求項３】 段階（ｂ）でイネーブリング・データが
   すぐにシーケンシャルに始めないならば、前記方法は、
   （ｂ−１）現行命令及び後続命令を前記データ・ストリ
   ームからフェッチし、（ｂ−２）前記後続命令の固定数
   の最初のビットをフェッチし、かつ（ｂ−３）次いで、
   前記現行命令に対して残りのビットをフェッチすること
   を更に含むことを特徴とする請求項１または２に記載の
   方法。
4. 【請求項４】 （ｆ−１）その出力が（ｉ）後続データ
   ・フィールドの開始、（ｉｉ）該データ・フィールドの
   長さ、（ｉｉｉ）実際のタグ・フィールド長、（ｉｖ）
   該フィールドが相対的であるか否かの識別、（ｖ）該フ
   ィールドが絶対的であるか否かの識別、及び（ｖｉ）再
   正規化を容易にするための数値シフティング・オフセッ
   ト情報を含んでいる該データ・フィールドに対する再正
   規化パラメータ、の少なくとも一つを識別するタグ・ル
   ックアップ表に前記タグ・ビットを供給し、 （ｆ−２）前記タグ・ルックアップ表出力がそのような
   ビット位置合わせされたフィールドが相対的であること
   を示すならば、前記フィールドの正規化された値を前記
   フィールドの現行値に加え、 （ｆ−３）前記タグ・ルックアップ表出力がそのような
   ビット位置合わせされたフィールドが絶対的であること
   を示すならば、該フィールドの該正規化された値で該フ
   ィールドの現行値を置換する段階を更に具備することを
   特徴とする請求項１〜３のいずれか一項に記載の方法。
5. 【請求項５】 次の後続命令が前記ビット位置合わせさ
   れたフィールドが解釈されるべき方法を変更することか
   または前記タグ表の内容を変更することまたは該ビット
   位置合わせされたフィールドの非変更データを通過する
   ことであるならば、そのようにし、かつ、 そのような正規化ビット位置合わせされたフィールドが
   ノーマル情報を含むならば、タグ・フィールド・インデ
   ックスは、該ノーマルの直線表現を得るために前記ルッ
   クアップ表を通過することを特徴とする請求項３または
   ４に記載の方法。
6. 【請求項６】 前記ビット位置合わせされたフィールド
   は、（ｉ）前記オブジェクトの前記表面上のｘ、ｙ、ｚ
   座標位置、（ｉｉ）前記オブジェクトに対する赤、緑、
   青のカラー情報、（ｉｉｉ）前記オブジェクトに対する
   赤、緑、青及びアルファのカラー情報、（ｉｖ）前記オ
   ブジェクトに対するシーケンシャル赤、緑、青のカラー
   情報間の相違、及び（ｖ）前記オブジェクトに対するシ
   ーケンシャル赤、緑、青及びアルファのカラー情報間の
   相違からなるグループから選択された少なくとも一つの
   特性に関する情報を含むことを特徴とする請求項１〜５
   のいずれか一項に記載の方法。
7. 【請求項７】 前記オブジェクトは、 （ｉ）前記オブジェクトの位置の特性が直線ｘ、ｙ、ｚ
   座標として表され、 （ｉｉ）前記オブジェクトのカラーの特性が少なくとも
   赤、緑、青、及びアルファ・コンポーネントを有してい
   るように表され、該カラーが（ａ）放射カラー、（ｂ）
   環境カラー、（ｃ）散乱カラー、及び（ｄ）鏡面カラー
   からなるグループからなる選択された少なくとも一つの
   カラーを含み、 （ｉｉｉ）前記オブジェクトのノーマルの特性が直線Ｎ
   ｘ、Ｎｙ、及びＮｚベクトル係数によって表され、（ｉ
   ｖ）前記オブジェクトのノーマルの特性は、ノーマル表
   インデックスによって表されることからなるグループか
   ら選択された少なくとも一つの特性を有し、前記オブジ
   ェクトの前記表面特性は、（ａ）位置、（ｂ）ノーマ
   ル、（ｃ）カラー、（ｄ）テキスチャ・マップ座標、及
   び（ｅ）前記オブジェクトの材料表面特性からなるグル
   ープから選択された少なくとも一つの特性を含むことを
   特徴とする請求項１〜６のいずれか一項に記載の方法。
8. 【請求項８】 前記ノーマルのそれぞれは、単一インデ
   ックスによって所定の正規化されたノーマルの表の中に
   表され、かつ前記インデックスは、（ｉ）前記インデッ
   クスは、表されるべきノーマルの直線表現サイン・ビッ
   トを備えているインデックス表現のビットを含み、（ｉ
   ｉ）前記インデックスは、フォールドされたノーマルが
   該フォールディング平面の既知の側面にあることを確実
   にするように少なくとも一つのフォールディング平面ｘ
   ＝ｙ、ｘ＝ｚ、ｙ＝ｚによって表されるべきノーマルの
   直線表現の絶対量の可能なフォールディングを指定して
   いる少なくとも一つのビットを含み、（ｉｉｉ）前記イ
   ンデックスは、前記ノーマルの経度情報及び緯度情報を
   表しているビットを含み、（ｉｖ）前記インデックス
   は、オクタント情報のビット、セクスタント情報のビッ
   ト、及びフォールドされたノーマルの経度及び緯度につ
   いての情報の追加フィールドを含むべく画定され、
   （ｖ）前記インデックスは、前記ノーマルの経度情報及
   び緯度情報を表しているビットを含み、及びオクタント
   情報のビット、セクスタント情報のビット、及びフォー
   ルドされたノーマルの経度及び緯度についての情報の追
   加フィールドを更に含み、（ｖｉ）前記インデックス
   は、オクタント情報の３ビット、セクスタント情報の３
   ビット、及びフォールドされたノーマルの経度及び緯度
   についての情報の２つの追加フィールドを含むべく画定
   され、（ｖｉｉ）前記インデックスは、前記ノーマルの
   経度情報及び緯度情報を表しているビットを含み、及び
   オクタント情報の３ビット、セクスタント情報の３ビッ
   ト、及びフォールドされたノーマルの経度及び緯度につ
   いての情報の２つの追加フィールドを更に含む、ことか
   らなるグループから選択された少なくとも一つの特性を
   有することを特徴とする請求項７に記載の方法。
9. 【請求項９】 圧縮解除されるべき前記データ・ストリ
   ームは、データが汎用三角形メッシュを画定している線
   形フォーマットに変換された、頂点を有している複数の
   三角形を画定している三次元三角形データとして表され
   た前記オブジェクトからもたらされ、前記表面特性の個
   々のものが量子化され、可変長圧縮が前記表面特性のシ
   ーケンシャルなものの間の相違に適用されることを特徴
   とする請求項１〜８のいずれか一項に記載の方法。
10. 【請求項１０】 現行ビット位置合わせされたフィール
    ドがメッシュ・バッファに配置されるべきであるなら
    ば、該現行ビット位置合わせされたフィールドのコピー
    を前記メッシュ・バッファに配置し、かつ前記ビット位
    置合わせされたフィールドがメッシュ・バッファ基準を
    含むならば、前記ビット位置合わせされたフィールドに
    対する古い正規化された値をアクセスする段階を更に含
    むことを特徴とする請求項１〜９のいずれか一項に記載
    の方法。
11. 【請求項１１】 オプ・コード・ビット及び／又はタグ
    ・ビットを含み、その表面が表面特性を画定する三次元
    オブジェクトを表している圧縮データを含み、そのフィ
    ールドが長さにおいて変化することができる、データ・
    ストリームを圧縮解除する、中央処理装置（ＣＰＵ）及
    び当該ＣＰＵに結合されたメモリを含んでいるコンピュ
    ータ・システムに使用可能な、システムであって、 前記データ・ストリームを受け取りかつすぐ後に続くフ
    ィールドの前記データ・ストリーム・フィールド情報に
    おける先行しているが、すぐにシーケンシャルに先行し
    ていることを必要としない、フィールドから検出すべく
    プログラムされた検出器装置と、前記フィールド情報
    は、フィールド型及びフィールド長及び／又はフィール
    ド正規化を含んでおり、 前記検出器装置によって検出された少なくともあるデー
    タを受け取りかつ前記データ・ストリームからビット位
    置合わせされたフィールドを抽出すべくプログラムされ
    た抽出器装置とを備えていることを特徴とするシステ
    ム。
12. 【請求項１２】 （ｉ）タグ・フィールド開始位置、
    （ｉｉ）実際のタグ・フィールド長、（ｉｉｉ）前記フ
    ィールドが相対的であるか否かの識別、（ｉｖ）前記フ
    ィールドが絶対的であるか否かの識別、及び（ｖ）数値
    シフティング・オフセット情報からなるグループから選
    択された少なくとも一部分の情報を供給する、前記デー
    タ・ストリームの少なくとも一部を前記検出器装置から
    受け取るべく結合された、ルックアップ表を更に含み、 前記データ・ストリームに含まれたビット・ライン・フ
    ィールドは、個々のビットに位置合わせされることを特
    徴と請求項１１に記載のシステム。
13. 【請求項１３】 （ｉ）前記データ・ストリームに含ま
    れた新しく入力するデータを調整する第１段階と、前記
    新しく入力するデータに前記データ・ストリームに含ま
    れる残っている古いデータを調整する第２段階とを含む
    多段バレル・シフタ装置、（ｉｉ）前記データ・ストリ
    ームを受け取るべく結合されたインターフェイス回路装
    置、（ｉｉｉ）前記インターフェイス回路の出力に結合
    されかつ前記データ・ストリームを圧縮解除する三次元
    グラフィックス・デコンプレッサ、（ｉｖ）圧縮解除さ
    れたデータ・ストリームを受け取りかつ出力すべく結合
    された、三次元グラフィックス・レンダリング装置から
    なるグループから選択された少なくとも一つの装置を更
    に含み、前記多段バレル・シフタ装置、前記インターフ
    ェイス回路装置、前記三次元グラフィックス・デコンプ
    レッサ、及び前記三次元グラフィックス・レンダリング
    装置の少なくとも二つは、一つの集積回路に組み込まれ
    ることを特徴とする請求項１１または１２に記載のシス
    テム。
14. 【請求項１４】 前記オプ・コードは、後続するフィー
    ルドのセットの型に関する情報を表わし、該情報は、
    （ｉ）頂点情報、（ｉｉ）位置情報、（ｉｉｉ）表面ノ
    ーマル情報、（ｉｖ）カラー、（ｖ）テキスチャ・マッ
    プ座標、（ｖｉ）表面材料特性、及び（ｖｉｉ）手順情
    報、（ｖｉｉｉ）頂点情報、ノーマル指令及びカラー指
    令以外の指令である手順情報からなるグループから選択
    され、及び／又は、 前記タグ・ビットは、（ａ）該タグ・ビットが（ｉ）フ
    ィールド長、（ｉｉ）正規化、（ｉｉｉ）そのようなフ
    ィールドが相対的か否か、（ｉｖ）そのようなフィール
    ドが絶対的か否か、からなるグループから選択された少
    なくとも一つのフィールド特性を暗黙的に記述する、及
    び（ｂ）該タグ・ビットが可変長を有しかつ当該可変長
    についての情報並びに可能フィールド内容情報を含み、
    該可変長は、該フィールド内容情報から独立である、か
    らなるグループから選択された少なくとも一つの特性を
    有し、前記オプ・コード・ビット及び／又は前記タグ・
    ビットの少なくともあるものは、前記フィールドの圧縮
    解除を三次元オブジェクトの非圧縮表面特性の中にガイ
    ドすることを特徴とする請求項１１〜１３のいずれか一
    項に記載のシステム。
15. 【請求項１５】 前記オブジェクトは、（ｉ）位置、
    （ｉｉ）ノーマル、（ｉｉｉ）カラー、（ｉｖ）テキス
    チャ・マップ座標、及び（ｖ）前記オブジェクトの材料
    表面特性からなるグループから選択された少なくとも一
    つの特性を含んでいる前記表面特性を有し、及び／又は
    前記オブジェクトは、（ｉ）前記オブジェクトの位置の
    特性が直線ｘ、ｙ、ｚ座標として表され、（ｉｉ）前記
    オブジェクトのカラーの特性が少なくとも赤、緑、青、
    及びアルファ・コンポーネントを有しているように表さ
    れ、該カラーが（ａ）放射カラー、（ｂ）環境カラー、
    （ｃ）散乱カラー、及び（ｄ）鏡面カラーからなるグル
    ープからなる選択された少なくとも一つのカラーを含
    み、（ｉｉｉ）前記オブジェクトのノーマルの特性が直
    線Ｎｘ、Ｎｙ、及びＮｚベクトル係数によって表され、
    （ｉｖ）前記オブジェクトのノーマルの特性は、前記ノ
    ーマルのルックアップ表の中にインデックスによって表
    され、（ｖ）位置、（ｖｉ）ノーマル、（ｖｉｉ）カラ
    ー、（ｖｉｉｉ）テキスチャ・マップ座標、及び（ｉ
    ｘ）材料表面特性からなるグループから選択された少な
    くとも一つの特性を含むことを特徴とする請求項１１〜
    １４のいずれか一項に記載のシステム。
16. 【請求項１６】 ノーマルの前記ルックアップ表は、所
    定の正規化されたノーマルを含み、かつ前記ノーマルの
    それぞれは、所定の正規化されたノーマルの前記ルック
    アップ表の中に単一インデックスによって表され、前記
    インデックスは、（ｉ）当該インデックスは、表現され
    るべきノーマルの直線表現サイン・ビットを備えている
    インデックス表現のビットを含み、（ｉｉ）前記インデ
    ックスは、フォールドされたノーマルが該フォールディ
    ング平面の既知の側面上にあることを確実にするように
    少なくとも一つのフォールディング平面ｘ＝ｙ、ｘ＝
    ｚ、ｙ＝ｚによって表されるべきノーマルの直線表現の
    絶対量の可能なフォールディングを指定している少なく
    とも一つのビットを含み、（ｉｉｉ）前記インデックス
    は、前記ノーマルの経度情報及び緯度情報を表している
    ビットを含み、（ｉｖ）前記インデックスは、オクタン
    ト情報のビット、セクスタント情報のビット、及びフォ
    ールドされたノーマルの経度及び緯度についての情報の
    追加フィールドを含むべく画定され、（ｖ）前記インデ
    ックスは、前記ノーマルの経度情報及び緯度情報を表し
    ているビットを含み、及びオクタント情報のビット、セ
    クスタント情報のビット、及びフォールドされたノーマ
    ルの経度及び緯度についての情報の追加フィールドを更
    に含み、（ｖｉ）前記インデックスは、オクタント情報
    の３ビット、セクスタント情報の３ビット、及びフォー
    ルドされたノーマルの経度及び緯度についての情報の２
    つの追加フィールドを含むべく画定され、（ｖｉｉ）前
    記インデックスは、前記ノーマルの経度情報及び緯度情
    報を表しているビットを含み、及びオクタント情報の３
    ビット、セクスタント情報の３ビット、及びフォールド
    されたノーマルの経度及び緯度についての情報の２つの
    追加フィールドを更に含む、ことからなるグループから
    選択された少なくとも一つの特性を有することを特徴と
    する請求項１５に記載のシステム。
17. 【請求項１７】 圧縮解除されるべき前記データ・スト
    リームは、データが汎用三角形メッシュを画定している
    線形フォーマットに変換された、頂点を有している複数
    の三角形を画定している三次元三角形データとして表さ
    れた前記オブジェクトからもたらされ、前記表面特性の
    個々のものが量子化され、可変長圧縮が前記表面特性の
    シーケンシャルなものの間の相違に適用されることを特
    徴とする請求項１１〜１６のいずれか一項に記載のシス
    テム。