(57)【要約】  ３Ｄコンピュータグラフィックスシステムにおいて、画像をレンダリングするために使用される複数の頂点に関するデータブロックである頂点パラメータデータを圧縮する方法及び装置を実現する。各頂点に関するデータは、少なくとも１つのパラメータに関する複数のバイトデータを含む。パラメータは、Ｘ、Ｙ及びＺ座標、並びにテクスチャリング及びシェーディングのためのさらなる座標を含む。複数のバイトデータを個々のバイトに分割し、各頂点に関する対応するバイト位置を有するバイトを互いにグループ化して、複数のバイトブロックを形成する。１つの実施形態では、バイトブロックの少なくとも１つを、このバイトブロック内の少なくとも１つのバイトをバイト原点として記憶し、バイトブロック内の残りのバイトの各々を、バイト原点の１つとの差分値として記憶することにより圧縮する。第２の実施形態では、少なくとも１つのバイトブロックを、このバイトブロック内の固有バイトを識別し、この固有バイトの少なくとも１つをＲＡＷバイト原点としてバイトデルタテーブルに記憶し、残りの固有バイトを、バイトデルタテーブル内に先行するバイト又はバイト原点との差分値として記憶し、このバイトデルタテーブルを参照することによってバイトブロック内のバイトを符号化するバイトインデックスを形成することにより圧縮する。このようにして圧縮した頂点パラメータデータを展開するための展開手段も提供する。これらの展開手段は、データストリームを読み取る必要なく圧縮データにランダムにアクセスすることができる。【選択図】図６
2013541755.tif 000002
【特許請求の範囲】
【請求項１】
３Ｄコンピュータグラフィックスシステムにおいて頂点パラメータデータを圧縮する方法であって、前記頂点パラメータデータが、複数の頂点に関するデータブロックを含み、前記各頂点に関するデータが、少なくとも１つのパラメータに関する複数のバイトデータを含み、
前記複数のバイトデータを個々のバイトに分割するステップと、
前記複数の頂点に関する前記データからの対応するバイト位置を有するバイトを互いにグループ化して複数のバイトブロックを形成するステップと、
第１の圧縮アルゴリズムを使用して前記バイトブロックの少なくとも１つを圧縮するステップと、
を含み、前記圧縮アルゴリズムが、バイトブロック内の少なくとも１つのバイトをバイト原点として記憶し、前記バイトブロック内の残りのバイトの各々を前記原点の１つとの差分値として記憶するステップを含む、
ことを特徴とする方法。
【請求項２】
前記圧縮ステップが、前記第１の圧縮アルゴリズムを使用して第１のバイトブロックを圧縮し、第２の圧縮アルゴリズムを使用して第２のバイトブロックを圧縮するステップを含む、
ことを特徴とする請求項１に記載の方法。
【請求項３】
頂点の各パラメータについての前記頂点パラメータデータが符号ビットを含み、前記方法が、前記分割ステップの前に前記符号ビットを最下位バイトに移動させるステップをさらに含む、
ことを特徴とする請求項１又は請求項２に記載の方法。
【請求項４】
前記バイトブロック内の最も値の小さなバイトがバイト原点として選択される、
ことを特徴とする請求項１に記載の方法。
【請求項５】
前記圧縮ステップが、バイトブロック内の複数のバイトを別個のバイト原点として記憶し、前記バイトブロック内の残りのバイトの各々を前記バイト原点の１つとの差分値として記憶するステップを含む、
ことを特徴とする請求項１から請求項４のいずれかに記載の方法。
【請求項６】
前記圧縮ステップが、バイトブロック内の最小数のバイトを、所定値よりも小さな前記差分値の全てに必要なバイト原点として記憶するステップを含む、
ことを特徴とする請求項５に記載の方法。
【請求項７】
前記圧縮ステップが、
ａ）バイトブロックからの第１のバイト及び第２のバイトを、バイト範囲を定める最大バイト値及び最小バイト値として記憶するステップと、
ｂ）後続のバイト値をチェックし、該後続のバイト値が前記バイト範囲外にある場合、前記最大バイト値又は最小バイト値を前記後続のバイト値に置き換えて、最新の最大バイト値及び最小バイト値、並びに最新のバイト範囲を形成するステップと、
ｃ）前記バイト範囲を定めるのに必要なビット数が所定のビット数を超えるまで、前記バイトブロック内の各後続のバイトに対してステップｂ）を繰り返すステップと、その後、
ｄ）前記バイト範囲を、前記所定のビット数又はそれ以下を使用して各々定義可能な２つのバイト範囲に分割するステップと、
ｅ）各後続のバイト値をチェックし、該後続のバイト値が前記バイト範囲の全ての外にある場合、前記範囲の１つの前記最大バイト値又は最小バイト値を前記後続のバイト値に置き換えて、最新の最大バイト値及び最小バイト値、並びに最新のバイト範囲を形成するステップと、
ｆ）バイト範囲を定めるのに必要なビット数が前記所定のビット数を超えるまで、前記バイトブロック内の各後続のバイトに対してステップｅ）を繰り返した後、前記バイトブロック内の前記バイトが全てバイト範囲に入るまでステップｅ）を繰り返すステップと、
をさらに含み、前記バイトブロック内のバイト範囲の数が、前記圧縮ステップで使用されるバイト原点の数に対応する、
ことを特徴とする請求項１から請求項６のいずれかに記載の方法。
【請求項８】
ステップｆ）の後に、２つのバイト範囲をマージして、マージされたバイト範囲を形成するステップをさらに含む、
ことを特徴とする請求項７に記載の方法。
【請求項９】
前記３Ｄコンピュータグラフィックスシステムが、タイルベースの３Ｄコンピュータグラフィックスシステムである、
ことを特徴とする請求項１から請求項８のいずれかに記載の方法。
【請求項１０】
前記圧縮ステップの後に、前記バイトブロックをマージして圧縮データブロックを形成するステップをさらに含む、
ことを特徴とする請求項１から請求項９のいずれかに記載の方法。
【請求項１１】
３Ｄコンピュータグラフィックスシステムにおいて頂点パラメータデータを圧縮するための装置であって、前記頂点パラメータデータが、複数の頂点に関するデータブロックを含み、前記各頂点に関するデータが、少なくとも１つのパラメータに関する複数のバイトデータを含み、
前記複数のバイトデータを個々のバイトに分割し、前記複数の頂点に関する前記データからの対応するバイト位置を有するバイトを互いにグループ化して複数のバイトブロックを形成するように構成された分割手段と、
圧縮アルゴリズムを使用して前記バイトブロックの少なくとも１つを圧縮するように構成された圧縮手段と、
を備え、前記圧縮アルゴリズムが、バイトブロック内の少なくとも１つのバイトをバイト原点として記憶し、前記バイトブロック内の残りのバイトの各々を前記原点の１つとの差分値として記憶するステップを含む、
ことを特徴とする装置。
【請求項１２】
３Ｄコンピュータグラフィックスシステムにおいて圧縮頂点パラメータデータを展開して展開データを提供する方法であって、各頂点に関する前記展開データが、少なくとも１つのパラメータに関する複数のバイトデータを含み、各パラメータに関する前記圧縮頂点パラメータデータが、圧縮データの複数の別個のバイトブロックを含み、各バイトブロックが、必要とされる複数のランダム順に選択された頂点からの前記複数のバイトデータの対応するバイト位置を有するバイトに関するデータを含み、
前記必要とされる頂点の頂点毎の圧縮データを圧縮データブロッカーブロックから読み取るステップと、
各バイトブロックのヘッダ内に示される展開アルゴリズムを使用して各バイトブロックを展開し、展開バイトブロックを提供するステップと、
各頂点に関する前記展開バイトブロックからの前記バイトを互いにマージすることにより、前記頂点パラメータデータを再構築するステップと、
を含むことを特徴とする方法。
【請求項１３】
３Ｄコンピュータグラフィックスシステムにおいて頂点パラメータデータを展開するための装置であって、各頂点に関する前記展開データが、少なくとも１つのパラメータに関する複数のバイトデータを含み、各パラメータに関する圧縮頂点パラメータデータが、圧縮データの複数の別個のバイトブロックを含み、各バイトブロックが、必要とされる複数のランダム順に選択された頂点からの前記複数のバイトデータの対応するバイト位置を有するバイトに関するデータを含み、
各バイトブロックのヘッダ内に示される各バイトブロックのための展開アルゴリズムを決定して、前記必要とされる選択された頂点の頂点毎の圧縮データを圧縮データブロックから読み取り、前記展開アルゴリズムを使用して前記バイトブロックを展開し、展開バイトブロックを提供するように構成された展開手段と、
各頂点に関する前記展開バイトブロックからの前記バイトを互いにマージすることにより、前記頂点パラメータデータを再構築するように構成されたマージ手段と、
を備えることを特徴とする装置。
【請求項１４】
３Ｄコンピュータグラフィックスシステムにおいて頂点パラメータデータを圧縮する方法であって、前記頂点パラメータデータが、複数の頂点に関するデータブロックを含み、前記各頂点に関するデータが、少なくとも１つのパラメータに関する複数のバイトデータを含み、
前記複数のバイトデータを個々のバイトに分割するステップと、
前記各頂点に関するデータからの対応するバイト位置を有するバイトを互いにグループ化して複数のバイトブロックを形成するステップと、
圧縮アルゴリズムを使用して、前記バイトブロックの少なくとも１つを圧縮するステップと、
を含み、前記圧縮アルゴリズムが、
バイトブロック内の固有バイトを識別するステップと、
前記固有バイトの少なくとも１つを、バイトデルタテーブルにＲＡＷバイト原点として記憶するステップと、
残りの固有バイトを、前記バイトデルタテーブルに、先行するバイト又は前記バイト原点との差分値として記憶するステップと、
前記バイトデルタテーブルを参照することにより、前記バイトブロック内の前記バイトを符号化するバイトインデックスを形成するステップと、
を含む、
ことを特徴とする方法。
【請求項１５】
前記固有バイトのうちの最初のものを、バイトデルタテーブルにＲＡＷバイト原点として記憶するステップと、
後続のバイトと先行するバイト又は先行するバイト原点との差分値が所定値よりも小さい場合、前記後続のバイトを前記差分値として記憶するステップと、
後続のバイトと前記先行するバイト又は先行するバイト原点との前記差分値が前記所定値に等しいか又はそれ以上の場合、前記後続のバイトをさらなるＲＡＷバイト原点として記憶するステップと、
をさらに含むことを特徴とする請求項１４に記載の方法。
【請求項１６】
前記バイトデルタテーブルが、該バイトデルタテーブル内の前記後続のデータがＲＡＷバイト原点であるか、それとも差分値であるかを示す少なくとも１つの制御ビットを含む、
ことを特徴とする請求項１４又は請求項１５に記載の方法。
【請求項１７】
前記圧縮ステップの後に、前記バイトブロックをマージして圧縮データブロックを形成するステップをさらに含む、
請求項１４から請求項１６のいずれかに記載の方法。
【請求項１８】
３Ｄコンピュータグラフィックスシステムにおいて頂点パラメータデータを圧縮するための装置であって、前記頂点パラメータデータが、複数の頂点に関するデータブロックを含み、前記各頂点に関するデータが、少なくとも１つのパラメータに関する複数のバイトデータを含み、
前記複数のバイトデータを個々のバイトに分割し、各頂点に関するデータからの対応するバイト位置を有するバイトを互いにグループ化して複数のバイトブロックを形成するように構成された分割手段と、
圧縮アルゴリズムを使用して、前記バイトブロックの少なくとも１つを圧縮するように構成された圧縮手段と、
を備え、前記圧縮アルゴリズムが、
バイトブロック内の固有バイトを識別するステップと、
前記固有バイトの少なくとも１つを、バイトデルタテーブルにＲＡＷバイト原点として記憶するステップと、
残りの固有バイトを、前記バイトデルタテーブルに、先行するバイト又は前記バイト原点との差分値として記憶するステップと、
前記バイトデルタテーブルを参照することにより、前記バイトブロック内の前記バイトを符号化するバイトインデックスを形成するステップと、
を含む、
ことを特徴とする装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、タイルベースの３次元コンピュータグラフィックシステムにおけるパラメータデータの無損失圧縮のための方法及び装置に関する。
【背景技術】
【０００２】
技術が急速に発達するにつれ、３次元コンピュータ生成画像の複雑さも同じペースで増している。人間の動きなどの非常に複雑な３Ｄオブジェクトのコンピュータモデルも、頂点及び三角形メッシュを使用して容易に構築することができる。その後、この種の３Ｄモデルを３Ｄコンピュータグラフィックシステムに送り、コンピュータ画面上に３Ｄ動画を生成することができる。コンピュータ生成３Ｄ動画は、３Ｄコンピュータゲーム、ナビゲーションツール及びコンピュータ支援工学設計ツールにおいて広く使用されている。
【０００３】
３Ｄコンピュータグラフィックシステムは、より複雑なグラフィック及びさらなる高速表示を求める絶え間ない要求に対処する必要がある。表示モデルの詳細さが増すにつれ、ますます多くの図形要素及び頂点が使用されるようになる。また、特にプログラム可能なシェーダ言語を使用したテクスチャリング及びシェーディング技術が発達するにつれ、頂点データにますます多くの情報が関連付けられるようになる（頂点パラメータデータ）。場合によっては、頂点パラメータデータサイズが、頂点毎に約１００個の３２ビットワードとなることもあり、画像のレンダリングには１００万個の頂点が存在することもある。従って、３Ｄレンダリングにおける頂点パラメータデータのためのメモリ空間は、容易に数百ＭＢに達する可能性がある。
【０００４】
３Ｄコンピュータグラフィックスシステムが処理する必要がある頂点パラメータデータの量に起因して、システム性能は、多くの場合、頂点パラメータデータのメモリ帯域幅により制限される。このことは、レンダリングを行うためにプリミティブからの頂点が必要な場合に、内部メモリに書き込まれた頂点パラメータデータが異なるタイルに関して複数回読み取られることがあるタイルベースの３Ｄコンピュータグラフィックスシステムに特に当てはまる。３Ｄコンピュータグラフィックスシステムの性能にとっては、３Ｄレンダリングで使用される頂点パラメータを圧縮することにより頂点パラメータデータの帯域幅を低減することが非常に有益と思われる。
【０００５】
当業者には周知のように、タイルベースの３Ｄコンピュータグラフィックスシステムは、レンダリング面をｎ×ｍ個の複数の画素タイルに分割する。三角形、線又は点などのプリミティブは、このプリミティブに重なるタイルに関してのみ処理される。図１に、タイルベースの３Ｄコンピュータグラフィックスシステムにおけるタイル処理のために行われる主なステップを示す。
【０００６】
３Ｄレンダリングでは、プリミティブがいくつかの共有頂点を含み、同じような場所のプリミティブが時間的に連続して到着することがある。頂点パラメータデータのためのメモリアクセスをより効率的にするために、タイルベースの３Ｄコンピュータグラフィックスシステムは、プリミティブの周囲にタイルの境界ボックスを定め、この境界ボックス内のタイル及びこれらのタイルが含むプリミティブに基づいて、到来するプリミティブの数を制限することができる。これにより、これらのタイルに重なるプリミティブからの頂点パラメータデータをプリミティブブロックにグループ化できるようになる。プリミティブは、これらのプリミティブブロックを指示するインデックスにより構築される。頂点パラメータデータのバッファサイズを制御するために、通常、プリミティブブロックに含まれる頂点及びプリミティブの最大数には、例えば３２個の頂点及び６４個のプリミティブなどの制限がある。図２に、プリミティブブロックからのデータ構造を示す。先頭には、図２の２０のように、頂点数及びプリミティブ数などのプリミティブブロック内の頂点パラメータデータの定義に使用されるプリミティブブロックヘッダワードが存在する。プリミティブブロックヘッダワードの後には、図２の２１のように、プリミティブブロック内の数多くの頂点からの頂点パラメータデータが続く。
【０００７】
このスキームでは、３Ｄレンダリング中に、一部のタイルがプリミティブブロックからのプリミティブの一部を参照し、その他のタイル内ではその他のプリミティブを参照することができる。プリミティブブロック内の頂点パラメータデータにアクセスするには、データストリームからプリミティブブロックにランダムアクセスする必要がある。また、プリミティブブロック内の頂点パラメータデータは、異なるタイル内のレンダリングにとっても必要な場合があり、従って頂点パラメータデータは、１度書き込まれて複数回読み取られることがある。
【０００８】
３Ｄ頂点パラメータデータ圧縮アルゴリズムの一般的要件は、高速、無損失圧縮、そして圧縮アルゴリズム及び展開アルゴリズム自体が使用するメモリ空間が最小となることである。この理由は、集積回路の狭いシリコン面積内に高速で高品質の３Ｄコンピュータグラフィックスシステムを実装することが要求されるからである。
【０００９】
タイルベースの３Ｄコンピュータグラフィックスシステムでは、頂点パラメータデータ圧縮アルゴリズムのさらなる要件として、圧縮データストリームからランダムデータアクセスができること、及び展開アルゴリズムが高速かつ単純であることが挙げられる。
【００１０】
ハフマン符号化／復号などの一般的な無損失圧縮アルゴリズムには、圧縮を行うために一般サイズのデータバッファを必要とするものもある。このことは、シリコン面積が限られた３Ｄコンピュータグラフィックスシステムには適していない。ランレングス符号化は、圧縮に追加のデータバッファを必要としないが、他のエントロピー符号化アルゴリズムと同様に、ビデオ表示内の色データストリームなどの連続的にアクセスされるデータストリームに対してデータ圧縮を行う。タイルベースの３Ｄコンピュータグラフィックスシステムで使用した場合、プリミティブブロックの全体的な頂点パラメータデータストリームを展開して初めていずれかの頂点データにアクセスできるようになる。このことは、特にプリミティブブロックが、多くのタイルをカバーする大きな三角形を含み、たとえプリミティブブロックからの頂点をわずかしか使用しない場合であっても全体的な頂点パラメータデータストリームが何度も展開される場合には、タイルベースのレンダリングにとって極めて非効率的である。
【００１１】
通常、３Ｄコンピュータグラフィックスシステムでは、頂点パラメータデータ値が、３２ビット浮動小数点値として記憶される。浮動小数点頂点データ値に固定小数点表現を使用することにより、プリミティブブロック内の頂点データを良好に圧縮することができる。浮動小数点値は、整数、及び固定小数点フォーマットの一定数の分数ビットによって表すことができる。この方法では、精度は低くなるものの、頂点からのＸ及びＹ座標データに対してはうまく機能することができる。コンピュータグラフィックス画面上の表示解像度は、わずかなピクセル単位に固定されるので、画面上にレンダリングされるプリミティブからのＸ及びＹ座標は、元の浮動小数点値から解像度が限られた画面値に変換される。
【００１２】
奥行きＺ、ＲＨＷ及びテクスチャ座標セットなどのその他の頂点パラメータデータでは、３Ｄ表示パイプラインを通じて高精度のデータを維持する必要がある。これらの頂点パラメータデータの表現精度が低いと、レンダリング画像内にアーチファクトが生じることがある。
【００１３】
頂点データ圧縮アルゴリズムによっては、頂点の幾何学的位置に従って頂点パラメータデータ値を圧縮するものもある。例えば、三角形メッシュ内の原点としてある頂点が選択され、完全な頂点パラメータデータ値の代わりに、頂点パラメータデータと原点頂点からのパラメータデータとの間の差分値（デルタ値）が記憶される。このデルタ値は、整数、又はデータストリームを圧縮する範囲を縮小した固定小数点値によって表すことができる。この種のアルゴリズムは、頂点間の頂点パラメータデータ値が限られた範囲内にある三角形メッシュからの頂点に対してはうまく機能する。圧縮比は、デルタ値を表すのに必要なビット数に関連する。多くの場合、長い三角形の帯などの三角形メッシュは、プリミティブブロック内に、頂点データ値の範囲が大きな頂点を含む可能性がある。この場合、デルタ値を記憶するために多くのビットが必要となるので、圧縮が不可能となる。
【００１４】
タイルベースの３Ｄコンピュータグラフィックスシステムにおける頂点パラメータデータのメモリ帯域幅を低減するために、入力ストリームからの全てのプリミティブは、画面外のもの、後ろ向きのもの、クリップされたもの、又は小さすぎて表示できないものなどのあらゆるプリミティブを除去するように事前処理される。事前処理後、残りのプリミティブは、一定の頂点数のプリミティブブロックにマージされ、３Ｄ処理のために内部パラメータメモリに書き込まれる。従って、プリミティブブロック内の頂点が単一の三角形メッシュに属することは保証されず、プリミティブブロック内の頂点パラメータデータ値の範囲が広すぎて、頂点原点からのデルタ値では圧縮できないことがある。
【発明の概要】
【課題を解決するための手段】
【００１５】
本発明の好ましい実施形態は、３Ｄコンピュータグラフィックスの頂点パラメータデータ圧縮に使用できる無損失圧縮方法及びシステムを含む。これらの方法及びシステムは、グラフィックスの頂点パラメータデータをより小さなメモリ空間に記憶できるようにし、従ってグラフィックス装置のメモリ要件を軽減する。本発明は、単純、高速、かつ記憶バッファ要件が非常に限られたアルゴリズムを使用することができる。また、これらのアルゴリズムは、圧縮後に固定サイズの頂点パラメータデータを有し、これによりプリミティブブロックデータストリーム内の圧縮頂点データのランダムアクセスが可能になり、このことはタイルベースの３Ｄコンピュータグラフィックスシステムにおいて特に有益である。
【００１６】
第１の態様では、本発明は、３Ｄコンピュータグラフィックスシステムにおいて頂点パラメータデータを圧縮する方法であって、この頂点パラメータデータは、複数の頂点に関するデータブロックを含み、各頂点に関するデータは、少なくとも１つのパラメータに関する複数のバイトデータを含み、
複数のバイトデータを個々のバイトに分割するステップと、
各頂点に関するデータからの対応するバイトを互いにグループ化して複数のバイトブロックを形成するステップと、
圧縮アルゴリズムを使用してバイトブロックを圧縮するステップと、
を含む方法を提供する。
【００１７】
本明細書で使用する「対応するバイト」という用語は、複数のバイトデータ内のバイト位置を意味する。従って、各頂点の特定のパラメータを表すデータ値の最上位バイト（ＭＳＢ）をグループ化してＭＳＢのバイトブロックを形成する。同様に、このパラメータのデータ値の各々の最下位バイト（ＬＳＢ）をグループ化して別のバイトブロックを形成する。本発明者は、グラフィックスの頂点パラメータデータには、複数のバイト値のうちの対応する個々のバイト間に、完全な複数のバイト値間に存在する相関性よりも強い相関性が存在することが多く、従って圧縮の余地が大きいことを見出した。異なるバイトブロックは、その内容に依存して異なる圧縮アルゴリズムを使用して圧縮することができる。例えば、バイトブロック内のバイトが全て等しい場合、このバイトブロックを、広い値の範囲にわたってバイトが分散している場合よりも効率的に圧縮することができる。
【００１８】
頂点パラメータデータは、典型的には３２ビット浮動小数点データなどの浮動小数点データであるが、固定小数点値データにも本発明を同様に適用することができる。
【００１９】
頂点パラメータは、例えば、Ｘ、Ｙ及びＺ座標、並びにＲＨＷ及びテクスチャ座標Ｕ、Ｖ、Ｓ及びＴとすることができる。
【００２０】
適切な圧縮アルゴリズムを決定できるように、バイトブロックを圧縮するステップは、バイトブロックの内容を評価し、このバイトブロックの内容に基づいて圧縮アルゴリズムを選択するステップを含むことが好ましい。評価ステップは、バイトブロック内の固有バイトの数を求め、これらの固有バイトの分散を特定するステップを含むことが好ましい。
【００２１】
頂点の各パラメータの頂点パラメータデータが符号ビットを含む場合、方法は、分割ステップの前に符号ビットを最下位バイトに移動させるステップをさらに含む。通常はＭＳＢの方がＬＳＢよりも強い相関性を有し、従って符号ビットをＬＳＢに移動させるステップは、ＭＳＢバイトブロックの圧縮性を高める一方で、ＬＳＢバイトブロックの圧縮性には有意に影響を与えないので、このステップは有益である。
【００２２】
圧縮ステップは、第１の圧縮アルゴリズムを使用して第１のバイトブロックを圧縮し、第２の圧縮アルゴリズムを使用して第２のバイトブロックを圧縮するステップを含むことができる。
【００２３】
１つの好ましい圧縮法は、バイトブロック内の少なくとも１つのバイトをバイト原点として記憶するステップと、バイトブロック内の残りのバイトの各々を、バイト原点との差分値として記憶するステップとを含む。バイトブロック内の最も値の小さなバイトをバイト原点として選択することが好ましい。
【００２４】
この方法は、バイトブロック内の複数のバイトを別個のバイト原点として記憶するステップと、バイトブロック内の残りのバイトの各々を、バイト原点の１つとの差分値として記憶するステップとを含むことが好ましい。複数のバイト原点を使用することにより、単一のバイト原点のみを使用して圧縮できないデータを圧縮できるようになる。
【００２５】
圧縮ステップは、バイトブロック内の最小数のバイトを、所定値よりも小さな差分値の全てにとって必要なバイト原点として記憶するステップを含むことが好ましい。グラフィックスシステムにより設定される最大数のバイト原点が存在して、この最大数に達するとともに差分値が依然として所定値を超えている場合には、異なる圧縮スキームを使用しなければならないようにしてもよい。
【００２６】
所定値を下回る差分値を有するデータブロックを圧縮するために使用できるバイト原点を計算できるように、バイトブロック内のバイトデータは、降順又は昇順で並べ換えられることが好ましい。本発明の方法は、各頂点のパラメータバイトデータが圧縮のために到着した場合、最初の個別のステップにおいてバイトブロックを並べ換える必要なくバイト原点を識別する。
【００２７】
圧縮ステップは、
ａ）バイトブロックからの第１のバイト及び第２のバイトを、バイト範囲を定める最大バイト値及び最小バイト値として記憶するステップと、
ｂ）後続のバイト値をチェックし、この後続のバイト値がバイト範囲外にある場合、最大バイト値又は最小バイト値を後続のバイト値に置き換えて、最新の最大バイト値及び最小バイト値、並びに最新のバイト範囲を形成するステップと、
ｃ）バイト範囲を定めるのに必要なビット数が所定のビット数を超えるまで、バイトブロック内の各後続のバイトに対してステップｂ）を繰り返すステップと、その後、
ｄ）バイト範囲を、所定のビット数又はそれ以下を使用して各々定義可能な２つのバイト範囲に分割するステップと、
ｅ）各後続のバイト値をチェックし、この後続のバイト値がバイト範囲の全ての外にある場合、これらの範囲の１つの最大バイト値又は最小バイト値を後続のバイト値に置き換えて、最新の最大バイト値及び最小バイト値、並びに最新のバイト範囲を形成するステップと、
ｆ）バイト範囲を定めるのに必要なビット数が所定のビット数を超えるまで、バイトブロック内の各後続のバイトに対してステップｅ）を繰り返した後、バイトブロック内のバイトが全てバイト範囲に入るまでステップｅ）を繰り返すステップと、
をさらに含み、バイトブロック内のバイト範囲の数が、圧縮ステップで使用されるバイト原点の数に対応することが好ましい。
【００２８】
方法は、ステップｆ）の後に、２つのバイト範囲をマージして、マージされたバイト範囲を形成するステップをさらに含むことが好ましい。
【００２９】
圧縮ステップは、バイトブロック内の各固有バイトをバイトテーブルに記憶し、このバイトテーブルを参照することにより、バイトブロック内のバイトを符号化するバイトインデックスを形成するステップを含むことができる。
【００３０】
圧縮ステップは、
バイトブロック内の固有バイトを識別するステップと、
固有バイトの少なくとも１つを、バイトデルタテーブルにＲＡＷバイト原点として記憶するステップと、
残りの固有バイトを、バイトデルタテーブルに、先行するバイト又はバイト原点との差分値として記憶するステップと、
バイトデルタテーブルを参照することにより、バイトブロック内のバイトを符号化するバイトインデックスを形成するステップと、
を含むことができる。
【００３１】
圧縮ステップは、
固有バイトのうちの最初のものを、バイトデルタテーブルにＲＡＷバイト原点として記憶するステップと、
後続のバイトと先行するバイト又は先行するバイト原点との差分値が所定値よりも小さい場合、後続のバイトを差分値として記憶するステップと、
後続のバイトと先行するバイト又は先行するバイト原点との差分値が所定値に等しいか又はそれ以上の場合、後続のバイトをさらなるＲＡＷバイト原点として記憶するステップと、
をさらに含むことができる。
【００３２】
複数の固有バイトをＲＡＷバイト原点として記憶することができ、残りのバイトの各々を、これらのＲＡＷバイト原点の１つとの差分値として記憶することができる。この場合、バイトデルタテーブルは、バイトデルタテーブル内の後続のデータがＲＡＷバイト原点であるか、それとも差分値であるかを示す制御ビットを含むことができる。
【００３３】
３Ｄコンピュータグラフィックスシステムは、タイルベースの３Ｄコンピュータグラフィックスシステムである。本発明は、データを全て展開する必要なく圧縮データへのランダムアクセスを可能にするので、タイルベースのシステムにとって特に有利である。
【００３４】
方法は、圧縮ステップの後に、バイトブロックをマージして圧縮データブロックを形成するステップをさらに含むことが好ましい。
【００３５】
別の態様では、本発明は、３Ｄコンピュータグラフィックスシステムにおいて頂点パラメータデータを圧縮するための装置であって、この頂点パラメータデータは、複数の頂点に関するデータブロックを含み、各頂点に関するデータは、少なくとも１つのパラメータに関する複数のバイトデータを含み、
複数のバイトデータを個々のバイトに分割し、各頂点に関するデータからの対応するバイトを互いにグループ化して複数のバイトブロックを形成するように構成された分割手段と、
圧縮アルゴリズムを使用して、バイトブロックの少なくとも１つを圧縮するように構成された圧縮手段と、
を備える装置を提供する。
【００３６】
この装置は、バイトブロックの内容を評価して、このバイトブロックの内容に基づいて圧縮アルゴリズムを選択するように構成された評価手段をさらに備えることができる。
【００３７】
頂点の各パラメータの頂点パラメータデータは符号ビットを含むことができ、この結果、装置は、分割手段によるデータの分割前に符号ビットを最下位バイトに移動させるように構成された符号ビット移動手段をさらに備えることができる。
【００３８】
さらに別の態様では、本発明は、３Ｄコンピュータグラフィックスシステムにおいて頂点パラメータデータを展開する方法であって、各頂点に関する展開データが、少なくとも１つのパラメータに関する複数のバイトデータを含み、各パラメータに関する圧縮頂点パラメータデータが、圧縮データの複数の別個のバイトブロックを含み、各バイトブロックが、複数の頂点からの複数のバイトデータの対応するバイトに関するデータを含み、
各バイトブロックのヘッダ内に示される展開アルゴリズムを使用して各バイトブロックを展開し、展開バイトブロックを提供するステップと、
各頂点に関する展開バイトブロックからのバイトを互いにマージすることにより、頂点パラメータデータを再構築するステップと、
を含む方法を提供する。
【００３９】
展開方法は、基本的に圧縮処理の逆である。従って、展開方法は、圧縮データの性質に依存して、
ａ）圧縮バイトデータストリームから複数のバイト原点値を読み取るステップと、
ｂ）圧縮データから差分値を読み取り、圧縮データからバイト原点のインデックスを読み取り、差分値を対応するバイト原点に加算して元のバイトデータを再構築するステップと、
ｃ）後続のデータがＲＡＷバイトであるか、それとも差分値であるかを示す制御ビットを読み取り、差分値をＲＡＷバイト原点に加算して固有バイト値を形成することにより、圧縮バイトデータストリームから固有バイトテーブルを構築するステップと、
ｄ）圧縮データからインデックス値を読み取り、対応する固有バイトテーブルエントリを元のバイトデータとして取得するステップと、
ｅ）バイトブロックをマージするステップ後、符号ビットを最下位バイトから最上位バイトに移動させるステップと、
のうちの１つ又はそれ以上をさらに含むことができる。
【００４０】
さらに別の態様では、本発明は、３Ｄコンピュータグラフィックスシステムにおいて電子頂点パラメータデータを展開するための装置であって、各頂点に関する展開データが、少なくとも１つのパラメータに関する複数のバイトデータを含み、各パラメータに関する圧縮頂点パラメータデータが、圧縮データの複数の別個のバイトブロックを含み、各バイトブロックが、複数の頂点からの複数のバイトデータの対応するバイトに関するデータを含み、
各バイトブロックのヘッダ内に示される各バイトブロックのための展開アルゴリズムを決定し、この展開アルゴリズムを使用してバイトブロックを展開し、展開バイトブロックを提供するように構成された展開手段と、
各頂点に関する展開バイトブロックからのバイトを互いにマージすることにより、頂点パラメータデータを再構築するように構成されたマージ手段と、
を備える装置を提供する。
【００４１】
この装置は、
ａ）圧縮バイトデータストリームから複数のバイト原点値を読み取る手段と、
ｂ）圧縮データから差分値を読み取り、圧縮データからバイト原点のインデックスを読み取り、差分値を対応するバイト原点に加算して元のバイトデータを再構築する手段と、
ｃ）後続のデータがＲＡＷバイトであるか、それとも差分値であるかを示す制御ビットを読み取り、差分値をＲＡＷバイト原点に加算して固有バイト値を形成することにより、圧縮バイトデータストリームから固有バイトテーブルを構築する手段と、
ｄ）圧縮データからインデックス値を読み取り、対応する固有バイトテーブルエントリを元のバイトデータとして取得する手段と、
ｅ）バイトブロックをマージするステップ後、符号ビットを最下位バイトから最上位バイトに移動させる手段と、
のうちの１つ又はそれ以上をさらに備えることができる。
【００４２】
本発明におけるアルゴリズムを使用して圧縮された頂点パラメータデータは固定サイズであるため、３Ｄコンピュータグラフィックスシステムが局所的なタイル領域内でレンダリングを行うために必要とする選択された頂点のパラメータデータのみを展開することが可能である。このことは、画像全体を展開する必要性を避けることによってメモリ帯域幅を節約するので、タイルベースのレンダリング３Ｄコンピュータグラフィックスシステムにとって大きな利点である。
【００４３】
以下、添付図面を参照しながら本発明の好ましい実施形態を詳細に説明する。
【図面の簡単な説明】
【００４４】
【図１】タイルベースの３Ｄコンピュータグラフィックスシステムにおけるタイル処理のために行われる主なステップの概観を示す図である。
【図２】タイルベースの３Ｄコンピュータグラフィックスシステムにおけるプリミティブブロックのデータ構造の概観を示す図である。
【図３】３Ｄコンピュータグラフィックスレンダリングに使用される頂点に関連するデータを示す図である。
【図４】Ｚ値のバイトデータ分布を示す図である。
【図５】Ｚ値のバイトデルタ値分布を示す図である。
【図６】バイトブロック圧縮ユニットの好ましい実施形態の概観を示す図である。
【図７】３２ビット浮動小数点頂点パラメータデータブロックの圧縮ユニットの好ましい実施形態の概観を示す図である。
【図８】圧縮頂点パラメータデータブロックの展開ユニットの好ましい実施形態の概観を示す図である。
【発明を実施するための形態】
【００４５】
図３では、Ｘ座標、Ｙ座標、奥行きＺ、並びにテクスチャリング及びシェーディングに使用するＲＨＷを含む、頂点パラメータデータの典型的なデータ構造を確認することができる。任意にＵ、Ｖ及びＳ、Ｔで示すいくつかのテクスチャ座標セットが存在することができる。
【００４６】
Ｘ、Ｙ、Ｚ、ＲＨＷ、並びにテクスチャ座標Ｕ、Ｖ、Ｓ及びＴの頂点パラメータデータの値は、ＩＥＥＥの浮動小数点フォーマットである。ＩＥＥＥの浮動小数点の値は３２ビット（４バイト）を有し、８ビットが指数部に、２３ビットが仮数部に、そして１ビットが符号に使用される。
【００４７】
アプリケーションの入力データストリームからのプリミティブは、タイルベースの３Ｄコンピュータグラフィックスシステムによって時間的に連続して受け取られ、事前処理の後、プリミティブブロックにグループ化される。従って、プリミティブブロック内のプリミティブは、大部分が同じ三角形メッシュからのものである。頂点パラメータデータタイプのデータ分布が、プリミティブブロック内で完全にランダムになる可能性は低い。
【００４８】
あるオブジェクトをモデル化するためにアプリケーションが使用する三角形メッシュからは、頂点からのＸ及びＹ座標値が、表示画面上の限られた範囲内にあるはずである。通常、奥行き値Ｚは、モデルからの３Ｄ面を内挿した結果であり、従って互いに段階的に変化する値である可能性が非常に高い。一般に、頂点パラメータデータの値間の段階的変化は、ＲＨＷ及びテクスチャ座標データなどのテクスチャリング及びシェーディングに使用されるデータに当てはまる。
【００４９】
コンピュータグラフィックス画面の表示解像度はわずかなピクセル単位に固定され、画面上にレンダリングされるプリミティブからのＸ及びＹ座標は限られた範囲内にあるので、元の浮動小数点値からのＸ値及びＹ値に精度の低い固定小数点フォーマットを使用してパラメータデータ空間を節約することができる。表１に、１６ビットの固定小数点フォーマットを使用して、１０個の頂点を含むプリミティブブロック内のＸ及びＹ座標を表した頂点パラメータデータの例を示す。
2013541755.tif 000003
表１：プリミティブブロックからの頂点データ
【００５０】
典型的なタイルベースの３Ｄコンピュータグラフィックスシステムでは、プリミティブブロック内の各頂点について頂点パラメータデータが順次出力される。このデータ配列は、３Ｄレンダリング段階において、特にタイルをレンダリングするために全ての頂点が必要とは限らないタイルベースのレンダリングに対して頂点パラメータデータへのアクセスを容易にする。表１に示す１０個の頂点のプリミティブブロックでは、頂点パラメータデータが、「Ｘ０，Ｙ０，Ｚ０，ＲＨＷ０，Ｕ０，Ｖ０，Ｓ０，Ｔ０，Ｘ１，Ｙ１，Ｚ１，ＲＨＷ１，Ｕ１，Ｖ１，Ｓ１，Ｔ１，…Ｘ９，Ｙ９，Ｚ９，ＲＨＷ９，Ｕ９，Ｖ９，Ｓ９，Ｔ９」として出力される。
【００５１】
精度要件が高いので、表１に示す３２ビット浮動小数点値の頂点パラメータデータには、０バイト値がほとんど無い。頂点パラメータデータ成分の３２ビット値の間のバイトデータ分布には、データ圧縮アルゴリズムに不可欠な明確なパターンは存在しない。例えば、表１に示すプリミティブブロックからの頂点Ｚのデータのデータブロックは、「３Ｆ  ７５  ８Ｆ  Ｂ４  ３Ｆ  ７６  ＥＣ  Ｃ８  ３Ｆ  ７４  ８Ｆ  ＤＦ  ３Ｆ  ７６  ＥＣ  Ｅ４  ３Ｆ  ７３  ８Ｆ  Ｂ４  ３Ｆ  ７４  ＣＡ  ８Ｆ  ３Ｆ  ７６  Ｃ９  ２Ｄ  ３Ｆ  ７１  ８Ｆ  ＤＦ  ３Ｆ  ７２  ＣＢ  ７９  ３Ｆ  ６Ｄ  ＣＡ  ８Ｆ」である。データ分布のランダム性により、３Ｄコンピュータグラフィックスシステムからの頂点パラメータデータブロックの高い圧縮結果を達成することは困難である。
【００５２】
バイトブロック
表１のデータから１つ気付くことは、列内のデータのほとんどに関して最上位バイトＭＳＢが非常に類似しており、場合によっては同じこともある点である。表１に示す１０個の頂点では、Ｚ、ＲＨＷ、Ｖ、Ｓ及びＴにおいてＭＳＢが同じである。ＵにおけるＭＳＢでも、共通バイト値が０ｘＢＦ、０ｘ３Ｆ、及び０ｘＢＥの３つしか存在しない。列内の値では、最下位バイトＬＳＢからのデータ分布は非常にランダムである。
【００５３】
図４に、３ＤコンピュータゲームからのレンダリングにおけるＺデータからの、３２ビットのＩＥＥＥ値の中の４バイトのデータ分布を示す。図４では、水平軸は、バイト値を８で除算したものであり、垂直軸は、同じ範囲内にバイト値を有する頂点のパーセンテージである。バイト０は３２ビット値からの最下位バイトＬＳＢであり、バイト３は最上位バイトＭＳＢである。図４に４０３で示すように、ＭＳＢバイト（バイト３）のデータ分布は、あるバイト範囲内にほぼ１００％存在しており、このことは、Ｚ値からのＭＳＢバイトのほとんどが同じ値であることを意味する。図４には、バイト２のデータ分布を４０２として示しており、このデータ分布では、バイト値の７０％があるバイト範囲内に存在する。最下位バイトのバイト１及びバイト０のデータ分布は、図４の４０１及び４００のように非常にランダムである。
【００５４】
また、図５に、各バイトのデルタ値の分布を図４と同様に示す。デルタ値とは、プリミティブブロックの２番目の頂点から開始して各バイトに関して計算した、現在の頂点のバイト値とプリミティブブロック内の前の頂点からのバイト値との間の差分のことである。図５の５０３及び５０２におけるバイト３及びバイト２のデルタ値の分布は、９０％を超えるピークを有する。バイト１では、デルタ値の分布に６０％のピークが存在し、最下位バイト（バイト０）の分布のみが依然として非常にランダムである。
【００５５】
頂点パラメータデータ分布の分析から、最上位バイトは良好な圧縮比を有すると予想されるのに対し、最下位バイトは、圧縮アルゴリズムにうまく応答する可能性が低い。
【００５６】
本発明の第１の態様の実施形態では、全ての圧縮アルゴリズムが、３２ビット浮動小数点値データブロック全体を圧縮するのではなく、全ての頂点パラメータデータ成分の４つの個々のバイトデータブロックに対して別個に作用する。このように、これらの圧縮アルゴリズムは、３２ビット浮動小数点データブロックをうまく圧縮できなくても、ＭＳＢバイトのデータ分布を利用してバイトブロックを圧縮することができる。
【００５７】
３Ｄレンダリング処理において頂点パラメータデータがアクセスされると、各バイトを別個に展開した後で、元の３２ビット頂点パラメータデータ値が再構築される。各バイトブロックはヘッダワードを含み、この中にブロック内の頂点数が含まれる。
【００５８】
バイトブロックベースの圧縮は非常に柔軟性があり、精度の低い固定小数点値データブロックにも適用することができ、例えば、１６ビットの固定小数点表現は２つのバイトブロックを有し、２４ビット表現は３つのバイトブロックを有する。精度が２倍の浮動小数点値では、６４ビット及び８つのバイトブロックが存在する。
【００５９】
符号ビットの移動
ＩＥＥＥの浮動小数点値は３２ビットを有し、８ビットが指数部に、２３ビットが仮数部に、そして１ビットが符号に使用される。符号ビットは最上位ビットを占め、従って最上位バイトは、符号のための１つの先頭ビット及び指数部のための７ビットを有する。指数部が同じで符号が異なる２つの浮動小数点値では、ＭＳＢバイト値が１２８ジャンプすることが容易に理解できる。表１の頂点０及び頂点４からのＵのＭＳＢバイトで分かるように、０ｘＢＦ２５Ａ７０８と０ｘ３Ｆ２５Ａ７０８という２つの値は同じ指数部０ｘ７Ｅを有するが、一方は正の値であり、一方は負の値である。バイトデータ分布の分析から、最上位バイト（バイト３）はうまく圧縮される可能性が非常に高い。従って、指数部の値のデータ分布の特徴を、負の値における符号ビットの変動から保護すべきである。
【００６０】
本発明の第２の態様の実施形態は、テクスチャ座標のような、正の値と負の値が混在している可能性がある頂点パラメータデータ成分のデータブロックを圧縮する前に、３２ビット浮動小数点値の符号ビットをビット３１からビット１に移動させる。
【００６１】
符号ビットを移動させた後には、上記の例からの２つのバイト３の値０ｘＢＦ及び０ｘ３Ｆは、表２に示すように同じ０ｘ７Ｅになる。表１の１０個の頂点からのＵ値のバイト３のバイト値間の最大距離は、表２のように１２８から１に低減し、従って結果的に圧縮性能が向上するようになる。
2013541755.tif 000004
表２：Ｕの符号ビットを移動した後のプリミティブブロックからの頂点データ
【００６２】
最下位バイトのデータ分布は非常にランダムであり、良好な圧縮結果が得られることは予想されず、従って符号ビットをＬＳＢバイト０の最下位に移動させても、全体的な圧縮比に有意な影響を与えることはない。
【００６３】
展開後には、符号ビットをビット１からビット３１に戻して、元の３２ビット浮動小数点値を再構築する。
【００６４】
この符号ビットを移動させて圧縮性能を向上させる方法は、固定小数点フォーマット及び倍精度浮動小数点フォーマットなどの、異なるバイト数で表されるその他のフォーマットの値にも適用することができる。
【００６５】
固有バイト
本発明の第３の態様の実施形態では、バイトデータブロックからのバイト値が全く同じ場合、圧縮ヘッダデータ内の１バイト、及び圧縮バイトブロックが固有バイトフォーマットであることを示す圧縮ヘッダ内のビットフラグしか必要としない。
【００６６】
いくつかの頂点パラメータデータ値のＭＳＢでは、固有バイトフォーマットを使用できる可能性が非常に高い。表２に示す１０個の頂点では、Ｚ、ＲＨＷ、Ｖ、Ｓ及びＴのＭＳＢ（バイト３）が全く同じであり、固有バイト法を使用して圧縮することができる。これらの場合、圧縮データ内には、バイト３内の１０個のバイトの代わりに、元のデータの１０％である１つのバイトしか出力されない。
【００６７】
好ましい実施形態では、頂点パラメータデータのバイトブロックからの現在のバイト値がバイトブロック内の前のバイト値と重複していないか比較される。前のバイト値のいずれとも一致しない場合、現在のバイトが共通バイトとして保持される。バイトデータブロック内に共通バイト値が１つしか存在しない場合、固有バイトを圧縮バイトデータとして記憶し、バイトデータブロック内の全てのバイトデータを置き換える。
【００６８】
３Ｄ処理における展開時には、バイトデータブロックが固有バイトフォーマットである場合、全ての頂点のバイト値に固有バイト値が使用される。この固有バイト法は、バイトデータブロックの圧縮にとって非常に効率的であるが、バイト値が全く同じバイトデータブロックに限られる。
【００６９】
バイトデルタブロック
バイトデータブロックからのバイト値が全く同じとは限らない場合、固有バイトフォーマットを使用してバイトデータブロックを圧縮することはできない。しかしながら、場合によっては、バイトデータブロックからのバイト値が大きく異ならず、従ってバイトデータブロック内のバイト値が限られた範囲内に存在することもある。
【００７０】
本発明の第４の態様の実施形態では、バイトデータブロックからの最小バイト値をバイト原点として使用して、データ範囲が限られたバイトデータブロックを、バイトデルタブロックを使用して圧縮することができる。バイトデータブロック内の各バイトに関して、圧縮バイトデータブロック内に、バイト値自体の代わりにデルタ値（バイト値とバイト原点値の差分）を出力する。
【００７１】
デルタ値に必要なビット数は、バイトデータブロック内のバイト値の範囲に依存する。好ましい実施形態では、圧縮ヘッダ内に最小バイト値がバイト原点として保持される。バイトデータブロック内の全てのデルタ値は正の値となり、従って符号ビットは必要ない。
【００７２】
８ビットでは、バイト値の範囲が［０，２５５］に固定される。バイトデータブロックからのデルタ値の範囲を、８ビット未満を使用して表すことができる場合、バイトデルタブロックアルゴリズムを使用してこのバイトデータブロックを圧縮することができる。
【００７３】
表３に、バイトブロック内のデルタ値を表すのに必要なビット数を示す。
2013541755.tif 000005
表３：デルタ範囲に必要なビット数
【００７４】
好ましい実施形態では、デルタ値のビット数が、８ビットのバイト原点値とともに圧縮ヘッダに記憶される。バイトデータブロックからの各バイトのデルタ値は、ビット数が固定された圧縮データとして出力される。プリミティブブロック内の頂点からのバイトデータ値の圧縮バイトデルタブロックは、バイト原点値にデルタ値を加算することによって容易に展開して元のバイト値を再構築することができる。
【００７５】
表２の１０個の頂点のＵの３２ビット値からのバイト３を例にとる。符号ビットを移動させた後のバイト３は、「０ｘ７Ｅ，０ｘ７Ｅ，０ｘ７Ｅ，０ｘ７Ｅ，０ｘ７Ｅ，０ｘ７Ｄ，０ｘ７Ｄ，０ｘ７Ｅ，０ｘ７Ｄ，０ｘ７Ｄ」である。固有バイト法を使用してバイト３のバイトデータブロックを圧縮することはできない。０ｘ７Ｅ及び０ｘ７Ｄという２つの共通バイト値が存在する。
【００７６】
最小バイト値は０ｘ７Ｄであり、最大バイト値は０ｘ７Ｅである。最大値と最小値の間の距離は１であり、１ビットのデルタ値を使用して表すことができる。
【００７７】
圧縮データは以下の通りである。
バイト原点は、「７Ｄ」の８ビットである。
圧縮バイトデルタブロックは、プリミティブブロック内の１０個の頂点の各バイトにつき１ビットであり、「１１１１１００１００」の１０ビットである。
【００７８】
この総圧縮データはバイト原点を含むのでバイトデルタブロックは１８ビットであり、これは元々の８０ビットのバイトブロックの２２．５％である。
【００７９】
展開時には、圧縮ヘッダから、Ｕのバイト３がデルタブロック圧縮フォーマットであり、デルタブロックのビット数がバイト毎に１ビットであることが分かる。この圧縮ヘッダデータからは、８ビットのバイト原点も読み取られる。
【００８０】
３Ｄ処理でアクセスされる頂点Ｕの値からのバイト３のブロック内の各バイトに関し、圧縮デルタブロックから１ビットのデルタ値が読み取られる。このデルタ値が原点バイトに加算されて元のバイトデータが再構築される。
【００８１】
頂点パラメータデータを圧縮する従来技術のスキームで説明したアルゴリズムは、頂点パラメータデータと頂点原点からのパラメータデータとの間の全値のデルタ値を使用する。多くの場合、３２ビット浮動小数点フォーマットの頂点パラメータ成分からのデルタ値は、はるかに大きな範囲内にあり、浮動小数点値のデルタの整数表現には多くのビットが必要になり、従って圧縮性能が低下する場合がある。圧縮では、デルタ値に固定小数点フォーマット表現を使用することができるが、これにより圧縮及び展開アルゴリズムの複雑さが増す。
【００８２】
本発明におけるバイトデータブロックアルゴリズムは、従来技術で説明したアルゴリズムとは異なり、個々のバイトデータブロックに基づくものである。図５で分かるように、バイトデータブロックでは、バイトデルタブロックを使用して表される可能性が大きく高まる。ＭＳＢバイト３及び２では、デルタ値の９０パーセント超が［０，７］の範囲内にある。バイト１でも、デルタ値の６０パーセントが［０，７］の範囲内にある。提示するバイトデルタブロックアルゴリズムを使用した圧縮性能の改善は、従来技術で説明したアルゴリズムに優る。バイトデルタブロックアルゴリズムの圧縮及び展開の演算は、８ビットの整数表現範囲内における整数の加算及び減算のみであり、従ってこのアルゴリズムは非常に高速かつ効率的であり、コンピュータハードウェア内での実装が容易である。このアルゴリズムは、３Ｄコンピュータグラフィックスシステム、特にタイルベースの３Ｄコンピュータグラフィックスシステムにおける頂点パラメータデータの圧縮に使用するのに適している。
【００８３】
複数の原点を含むバイトデルタブロック
表２の１０個の頂点からのＶのバイト１の値が「０ｘ７６，０ｘ７６，０ｘＦＢ，０ｘＦＢ，０ｘ７６，０ｘ８５，０ｘ７６，０ｘＦＢ，０ｘＦＢ，０ｘ８５」であることに注目する。
【００８４】
０ｘ７６、０ｘＦＢ及び０ｘ８５という３つの共通バイト値が存在する。これらの３つの共通バイトにおける最大バイト０ｘＦＢと最小バイト０ｘ７６の間の距離は０ｘ８５であり、これは８ビット整数としてしか表すことができない。この場合、デルタブロックアルゴリズムを使用してバイト１を圧縮することはできない。
【００８５】
３つの共通バイト値をさらに分析すると、０ｘ７６と０ｘ８５の間の距離は０ｘＦであり、これは４ビットのデルタ値を使用して表すことができる。従って、２つの別個の範囲内の４ビットのデルタ値を使用して全体のバイトデータブロックを表すことができる。
【００８６】
本発明の第５の態様の実施形態では、複数のバイト原点を含むデルタブロックを使用して、バイトデータブロックのデータを圧縮することができる。
【００８７】
上記の例からの２つの範囲のバイト原点は、０ｘ７６及び０ｘＦＢである。デルタ値がいずれの原点に基づくものであるかを示すために、各圧縮バイトに１つの追加ビットが必要である。バイト１の圧縮データは以下のようになる。
２つの原点は、「７６ＦＢ」の１６ビットである。
４ビットをデルタ値とし、１ビットをバイト原点インデックスとする頂点毎に５ビットの圧縮デルタブロックデータは、１０個の頂点では５０ビットとなる。プリミティブブロック内の１０個の頂点のバイト１の圧縮データは、「００００  ０，００００  ０，００００  １，００００  １，００００  ０，１１１１  ０，００００  ０，００００  １，００００  １，１１１１  ０」の５０ビットである。
【００８８】
バイト原点及びバイトインデックスブロックデータを含む総圧縮出力データは６６ビットであり、これは元々の８０ビットのバイトデータブロックの８２．５％である。
【００８９】
展開時には、圧縮ヘッダから、Ｖのバイト１がデルタブロック圧縮フォーマットであり、バイト原点の数が２であり、デルタブロックのビット数がバイト毎に４ビットであることが分かる。この圧縮ヘッダデータからは、各々８ビットのバイト原点も読み取られる。
【００９０】
３Ｄ処理でアクセスされる頂点Ｖの値からの各バイト１に関し、最初に１ビットのバイト原点インデックスが読み取られ、その後、圧縮デルタブロックからの４ビットのデルタ値が読み取られる。このデルタ値が、バイト原点インデックスによって示されるバイト原点に加算されて元のバイトデータが再構築される。
【００９１】
別の例として、２０個の頂点からのバイトデータブロックを、「０ｘ０３、０ｘ５Ｂ、０ｘ０３、０ｘ５４、０ｘＦ２、０ｘ５４、０ｘ０３、０ｘ０Ａ、０ｘ５Ｂ、０ｘ５Ｂ、０ｘ０３、０ｘＦ２、０ｘＥＣ、０ｘ０Ａ、０ｘＦ２、０ｘ０Ａ、０ｘ０Ａ、０ｘ３３、０ｘ０Ａ、０ｘ０３」とする。
【００９２】
「０ｘ０３、０ｘ５Ｂ、０ｘ５４、０ｘＦ２、０ｘ０Ａ、０ｘＥＣ、及び０ｘ３３」という７つの共通バイト値が存在する。これらの７つの共通バイトにおける最大バイト０ｘＦ２と最小バイト０ｘ０３の間の距離は０ｘＥＦであり、これは８ビットの整数としてしか表すことができない。この場合、１つのバイト原点を有するデルタブロックアルゴリズムを使用してバイトブロックを圧縮することはできない。
【００９３】
７つの共通バイトにおける最大バイト０ｘＦ２とバイト０ｘ５４の間の距離は０ｘ９Ｅであり、これは８ビットの整数としてしか表すことができない。７つの共通バイトにおけるバイト０ｘ５Ｂと最小バイト０ｘ０３の間の距離は０ｘ５８であり、これは７ビットの整数としてしか表すことができない。バイト原点のインデックスのための１つの追加ビットが必要であることを考慮すると、２つのバイト原点を含むデルタブロックアルゴリズムによってこのバイトブロックを圧縮することはできない。
【００９４】
７つの共通バイト値をさらに分析すると、０ｘ０３と０ｘ０Ａの間の距離は０ｘ７であり、これは３ビットのデルタ値を使用して表すことができる。０ｘ５Ｂと０ｘ５４の間の距離も０ｘ７であり、０ｘＦ２と０ｘＥＣの間の距離は０ｘ６である。従って、４つの別個の範囲内の３ビットのデルタ値を使用して全体のバイトデータブロックを表すことができる。
【００９５】
上記の例からの４つの範囲のバイト原点は、０ｘ０３、０ｘ５４、０ｘＥＣ及び０ｘ３３である。デルタ値がいずれの原点に基づくものであるかを示すために、各圧縮バイトに２つの追加ビットが必要である。バイトデータブロックの圧縮データは、以下のようになる。
４つのバイト原点は、「０３５４ＥＣ３３」の３２ビットである。
３ビットをデルタ値とし、２ビットをバイト原点インデックスとする頂点毎に５ビットの圧縮デルタブロックは、２０個の頂点で１００ビットとなる。プリミティブブロック内の２０個の頂点の圧縮バイトデータは、「０００  ００，１１１  ０１，０００  ００，０００  ０１，１１０  １０，０００  ０１，０００  ００，１１１  ００，１１１  ０１，１１１  ０１，０００  ００，１１０  １０，０００  １０，１１１  ００，１１０  １０，１１１  ００，１１１  ００，０００  １１，１１１  ００，０００  ００」の１００ビットである。
【００９６】
バイト原点及びバイトインデックスブロックを含む総圧縮出力データは１３２ビットであり、これは元々の１６０ビットのバイトブロックの８２．５％である。
【００９７】
展開時には、圧縮ヘッダから、バイトデータブロックがデルタブロック圧縮フォーマットであり、バイト原点の数が４であり、デルタブロックのビット数がバイト毎に３ビットであることが分かる。この圧縮ヘッダデータからは、各々８ビットのバイト原点も読み取られる。
【００９８】
３Ｄ処理でアクセスされる２０個の頂点値からの各バイトに関し、最初に２ビットのバイト原点インデックスが読み取られ、その後、圧縮デルタブロックからの３ビットのデルタ値が読み取られる。このデルタ値が、バイト原点インデックスによって示されるバイト原点に加算されて元のバイトデータが再構築される。
【００９９】
デルタブロックアルゴリズムの圧縮比は、バイトデータブロックのデルタ値を表すのに必要なビット数に依存する。複数のバイト原点を使用して、最大バイト値と最小バイト値の距離を８ビット未満で表すことができない場合、デルタブロックアルゴリズムによってバイトブロックを圧縮することはできない。
【０１００】
バイト値の範囲
デルタブロックアルゴリズムを使用してバイトデータブロックを圧縮するには、プリミティブブロック内のバイト値の範囲を知る必要がある。バイト値の範囲を８ビット未満のデルタ値で表すことができる場合、デルタブロックアルゴリズムを使用することができる。
【０１０１】
バイト値の範囲を求めるための理想的な方法は、全てのバイト値を昇順又は降順に並べ換えることである。最大バイト値と最小バイト値の間のデルタ値が８ビット未満の場合には、１つの原点を含むデルタブロック圧縮を使用する。それ以外の場合には、全範囲を、最大値と最小値の間の距離が等しい複数の部分範囲に分割する。デルタ値及びバイト原点インデックスを含めてバイトデータ範囲を８ビット未満で表すことができる場合、複数のバイト原点を含むデルタブロック圧縮を使用してバイトデータブロックを圧縮することができる。
【０１０２】
バイトデータブロックからのバイト値を並べ換えるには、全バイトブロックのバイトデータ値のための記憶空間が必要である。これにより、コンピュータハードウェア内に実装する場合に余分なコストが加わるようになる。
【０１０３】
本発明の第６の態様の実施形態では、バイトデータを並べ換えることなく、また余分な記憶領域を使用することなくバイトデータブロックから複数のバイト値範囲を導出する方法を以下のように説明する。
【０１０４】
プリミティブブロック内の入力された頂点パラメータデータからバイトデータが到来すると、最小及び最大バイト値、並びにこの範囲のデルタ値に必要なビット数を使用して、バイト値の範囲が記憶される。入力された頂点パラメータデータブロックからの新たなバイトが既存の範囲に対してチェックされ、このバイトが範囲内にあるか否かが判定される。バイトが既存の範囲外にある場合、この範囲の最小値又は最大値のいずれかを置き換えることによって範囲が更新され、この範囲のデルタ値に必要なビット数も更新される。
【０１０５】
この新たなバイト値により、バイト範囲内のデルタ値のビット数が所定の最大ビット数よりも大きくなった場合、新たな範囲を追加して最初の範囲のデルタ値を最大ビット数内に保つ。後続のバイトも、上述した方法と同じ方法を使用して２つの範囲に対してチェックされる。この処理は、例えば４つのバイト原点では４つのバイト範囲のように、範囲数がバイト原点数の限界に達するまで継続される。バイトデータブロックを、バイト範囲内のデルタ値の所定の最大ビット数で表すことができる場合、デルタブロックアルゴリズムを使用してバイトデータブロックを圧縮することができる。
【０１０６】
バイト値の範囲のマージ
評価処理の終了時に、所定の最大デルタビット数の範囲内に２又はそれ以上のバイトデータブロックの範囲が存在する場合、これらの範囲を互いにマージできる可能性が依然として存在する。例えば、６ビットのデルタ値を有する範囲が２つ存在する場合、これらの範囲を、７ビットのデルタを有する１つの範囲にマージすることができる。この例では、２つのバイト原点の場合に６ビットのデルタ＋１バイトの原点インデックスが必要となる代わりに、１つの原点の場合に７ビットが必要となる。圧縮デルタブロックサイズは同じであるが、後者の場合の第２のバイト原点のための８ビットが節約され、従って終了時に可能な場合には、範囲を互いにマージすることが好ましい。
【０１０７】
このバイトデルタブロックアルゴリズムは、３Ｄコンピュータグラフィックス、特にタイルベースの３Ｄコンピュータグラフィックスシステムにおける頂点パラメータデータの圧縮のための単純で高速かつ効率的な圧縮アルゴリズムである。説明しているバイト範囲評価方法を使用することにより、入力された頂点パラメータデータが到来した時に、バイトデータブロックの範囲を容易に求めることができる。この方法は、３Ｄコンピュータグラフィックスハードウェアパイプライン内に実装することができ、バイトデータブロックを並べ換えるために大きなデータ記憶領域を必要としない。頂点パラメータデータ及びその他の種類のバイトデータブロックに対して圧縮及び展開演算を効率的に実行することができる。
【０１０８】
本発明のバイトデルタブロックアルゴリズムを使用して圧縮される頂点データのサイズは、バイト毎に固定のビット数であり、デルタ値のための固定ビット数及びバイト原点インデックスのための固定ビット数を含む。バイトデルタブロックアルゴリズムのその他の利点は、３Ｄ処理において圧縮データブロックから圧縮頂点パラメータデータにランダムにアクセスできる点である。圧縮頂点パラメータデータはサイズが固定されているので、圧縮頂点パラメータデータの位置を容易に計算することができる。従って、全プリミティブブロックの頂点パラメータデータをいちいち展開する必要はなく、タイルをレンダリングするのに必要な頂点パラメータデータのみを圧縮データブロックから読み取って展開する。
【０１０９】
共通バイトテーブル
頂点パラメータデータブロックの一部からのバイト値の性質は多様であるため、固有バイト又はバイトデルタブロックアルゴリズムを使用してデータブロックを全て圧縮できるわけではない。
【０１１０】
一例として、プリミティブブロック内の１０個の頂点からのバイト値を、「０ｘ０３，０ｘ５Ｂ，０ｘＦ２，０ｘ５Ｂ，０ｘ０３，０ｘ０３，０ｘＥＣ，０ｘＦ２，０ｘ３３，０ｘ０３」とする。共通バイト内の最大バイト０ｘＦ２とバイト０ｘ５Ｂの間の距離は０ｘ９７であり、これは８ビットの整数としてしか表すことができない。共通バイト内の０ｘ５Ｂと最小バイト０ｘ０３の間の距離は０ｘ５８であり、これは７ビットの整数としてしか表すことができない。バイト原点のインデックスのために１つの追加ビットが必要である。このバイトブロックは、４つのバイト原点０ｘ０３、０ｘ５Ｂ、０ｘＥＣ及び０ｘ３３を含むデルタブロックアルゴリズムによってしか圧縮することができない。０ｘＦ２と０ｘＥＣの間の距離０ｘ６を表すために３ビットのデルタ値が必要であり、バイト原点のインデックスのために２つの追加ビットが必要である。圧縮データサイズは、４×８ビットのバイト原点に圧縮データの１０×（３＋２）ビットを加えたものであり、合計で８２ビットである。従って、バイトデルタブロックアルゴリズムを使用してこのバイトデータブロックを圧縮することはできない。
【０１１１】
共通バイト数が限られている場合、共通バイトテーブルを使用して共通バイト値を記憶することができる。本発明の第７の態様の実施形態では、バイトデータブロックからの共通バイト値を共通バイトテーブル内に保持することができる。バイトデータブロックを圧縮するために、バイトデータブロック内の各バイトに関し、圧縮バイトデータブロック内にバイト値自体の代わりに共通バイトテーブルへのインデックスを出力する。
【０１１２】
テーブルインデックスに必要なビット数は、共通バイトテーブル内のエントリ数に依存する。共通バイトテーブル内のエントリ数が圧縮ヘッダに記憶されている場合、プリミティブブロックの展開時に、共通バイトテーブルのデータサイズ及びテーブルインデックスのために必要なビット数を容易に求めることができる。
【０１１３】
上記の例として、バイトデータブロックを、「０ｘ０３，０ｘ５Ｂ，０ｘＦ２，０ｘ５Ｂ，０ｘ０３，０ｘ０３，０ｘＥＣ，０ｘＦ２，０ｘ３３，０ｘ０３」とする。このバイトブロックは、５つの共通バイト値０ｘ０３，０ｘ５Ｂ，０ｘＦ２，０ｘＥＣ及び０ｘ３３を有する。これらの５つの共通バイト値を、バイトデータブロックの共通バイトテーブルに記憶することができ、各頂点における圧縮バイトデータに関して、この共通バイトテーブルに３ビットのインデックスが出力される。
【０１１４】
バイトテーブルは、「Ｕ０３５ＢＦ２ＥＣ３３」の４０ビットである。
プリミティブブロック内の１０個の頂点の圧縮バイトデータは、「０００  ００１  ０１０  ００１  ０００  ０００  ０１１  ０１０  １００  ０００」の３０ビットである。
【０１１５】
合計圧縮出力データは共通バイトテーブルを含み、バイトインデックスブロックは７０ビットであり、これは元々の８０ビットのバイトブロックの８７．５％である。
【０１１６】
展開時には、圧縮ヘッダから、バイトデータブロックが共通バイトテーブルフォーマットであること、共通バイトテーブル内のエントリ数が５であることが分かる。最初に圧縮ヘッダから共通バイトテーブルのバイト値が読み取られて共通バイトテーブルが形成される。
【０１１７】
３Ｄ処理でアクセスされる各頂点データについて、圧縮データブロックから３ビットのテーブルインデックスが読み取られる。次に、このテーブルインデックスを使用して、プリミティブブロック内の元のバイトデータのバイト値を共通バイトテーブル内で参照する。
【０１１８】
共通バイトテーブルの圧縮比は、バイトデータブロックからの共通バイト値の数に依存する。この共通バイト値の数により、共通バイトテーブルサイズ及びテーブルインデックスのビット数が決まる。好ましい実施形態では、共通バイトテーブルの最大エントリを、例えば１６又は３２のように事前に定めることができ、従ってテーブルインデックスの最大ビット数はそれぞれ４又は５となる。
【０１１９】
総圧縮データサイズは、共通バイトテーブルサイズに、頂点パラメータデータバイトブロック内の各バイトのテーブルインデックスを足したものになる。バイトデータブロックからの共通バイト値の数が多い場合、共通バイトテーブルのデータサイズ及び頂点のテーブルインデックスが、バイトデータブロックの元のデータサイズを上回ることがある。この場合、共通バイトテーブルアルゴリズムによってバイトデータブロックを圧縮することはできない。
【０１２０】
共通バイトデルタテーブル
共通バイトテーブルアルゴリズムの圧縮データサイズは、共通バイトテーブルのサイズに依存する。共通バイトテーブル内のエントリ数は、バイトデータブロックからの共通バイト値の数によって決まり、このエントリ数は変更することができない。共通バイトテーブルサイズを縮小するための唯一の方法は、共通バイトテーブルに代わる表現法を使用することである。
【０１２１】
一例として、１０個の頂点を有するプリミティブブロック内のバイトデータブロックからのバイト値を、「０ｘ３５，０ｘ５Ｂ，０ｘ９９，０ｘ３５，０ｘ０４，０ｘＤ２，０ｘＤ２，０ｘ５Ｂ，０ｘ３５，０ｘ３７」とする。
【０１２２】
６つの共通バイト値０ｘ３５、０ｘ５Ｂ、０ｘ９９、０ｘ０４、０ｘＤ２及び０ｘ３７が存在する。これらの共通バイトを、［０ｘ０４，０ｘ３７］、［０ｘ５Ｂ，０ｘ５Ｂ］、及び［０ｘ９９，０ｘＤ２］という３つの範囲内に配置して、これらの範囲内に６ビットのデルタ値が入るようにすることができる。これらの３つのバイト原点には、頂点毎に２ビットが必要であり、これによりこのバイトデータブロックは、バイトデルタブロックアルゴリズムに適さないものとなる。
【０１２３】
共通バイトテーブルアルゴリズムを使用するには、共通バイトテーブルのデータサイズが、４８ビットに、各頂点におけるテーブルインデックスの３ビットを足したものになる。合計データサイズは７８ビットとなり、これは元のデータサイズの８０ビットとほぼ同じである（９７．５％）。
【０１２４】
緻密な調査により、共通バイト値はほとんど異なるが、バイト値は、［０ｘ０４，０ｘＤ２］の全体的範囲内にほぼ均等に分布することが分かる。共通バイトテーブル内のバイト数は数が非常に限られているので、共通バイトテーブル内のバイト値を容易に昇順に並べ換えることができる。
【０１２５】
並べ換え後、上記の例における共通バイト値は、「０ｘ０４，０ｘ３５，０ｘ３７，０ｘ５Ｂ，０ｘ９９，０ｘＤ２」となる。共通バイトデルタテーブルを「０ｘ０４，０ｘ３１，０ｘ０２，０ｘ２４，０ｘ３Ｅ，０ｘ３９」とし、最初のエントリ０ｘ０４を８ビットのＲＡＷバイト値とし、残りをバイトデルタテーブルへのデルタ値及び１０個の頂点のための３０ビットのテーブルインデックスとして形成することができ、これは元の８０ビットのバイトデータブロックのデータの８５％である。
【０１２６】
本発明の第８の態様の実施形態では、共通バイト値を昇順に並べ換えて、最初の８ビットのＲＡＷバイト値及びビット数が固定されたデルタ値を含む共通バイトデルタテーブルを形成することができる。
【０１２７】
好ましい実施形態では、最初にバイトデータブロックからの共通バイト値を並べ換え、次に表３の値までの距離値を参照することにより、デルタ値に必要なビット数を導出する。共通バイトテーブル内のエントリ毎のサイズが８ビット未満である場合、この共通バイトテーブルは、共通バイトデルタテーブルに置き換えられる。
【０１２８】
圧縮時には、共通バイトデルタテーブル内のエントリ数が、デルタ値に使用されるビット数とともに圧縮ヘッダに記憶される。共通バイトデルタテーブル内のエントリは、後にビット数が固定されたデルタ値を伴う先頭の８ビットのバイト値として記憶される。
【０１２９】
展開時には、圧縮ヘッダから、バイトデータブロックが共通バイトデルタテーブルフォーマットであることが分かる。圧縮ヘッダからは、共通バイトデルタテーブル内のエントリ数及びデルタ値のビット数が最初に読み取られる。共通バイトデルタテーブル内のデルタ値が読み戻されて、元の８ビットのバイト値エントリを有する共通バイトテーブルが再構築される。
【０１３０】
共通バイトテーブル内のエントリ数から、各頂点における共通バイトデルタテーブルインデックスに使用されるビット数が分かる。圧縮バイトデータブロックから、頂点の頂点パラメータバイトデータのためのテーブルインデックスを読み取って、再構築された共通バイトテーブルから元のバイト値を参照することができる。
【０１３１】
上記の例のバイトデータブロックでは、バイトデルタテーブル内のエントリ数が６であり、共通バイトデルタテーブル内のデルタ値のビット数も６である。この場合３ビットであるテーブルエントリ数から、テーブルインデックスに使用されるビット数を容易に求めることができる。
【０１３２】
展開時に共通バイトテーブルを再構築するために、まず共通バイトデルタテーブルからの最初のバイト値が０ｘ０４として読み取られる。次にビットデルタ値が０ｘ３１としてフェッチされ、これがバイト値０ｘ０４に加算され、従って元のバイト０ｘ３５が再構築される。別のデルタ値０ｘ０２が前のバイト０ｘ３５に加算され、元のバイト０ｘ３７が形成される。その後、共通バイトデルタテーブルからの全てのデルタ値を使用して、デルタ値を前のバイトに加算することにより元のバイト値が再構築される。終了時には、共通バイトテーブル全体が、「０ｘ０４，０ｘ３５，０ｘ３７，０ｘ５Ｂ，０ｘ９９，０ｘＤ２」として再構築される。
【０１３３】
３Ｄ処理においてアクセスされる各頂点に関し、圧縮データブロックから、頂点パラメータバイトデータブロックのための３ビットのテーブルインデックス値が読み取られる。次にテーブルインデックスを使用して共通バイトテーブル内の元のバイト値が参照され、プリミティブブロック内の頂点パラメータバイトデータが再構築される。
【０１３４】
制御コードを含む共通バイトデルタテーブル
本発明の第９の態様の実施形態では、共通バイトデルタテーブル内に１ビットの制御コードを導入して、共通バイトデルタテーブル内にデルタ値とＲＡＷバイト値が混在できるようにすることができる。共通バイトデルタテーブル内の各エントリに関し、このエントリがデルタ値であるか、それともＲＡＷバイト値であるかを、例えばＲＡＷバイトの場合には０、デルタ値の場合には１を示す１ビットの制御コードが存在する。共通バイトデルタテーブル内の最初のエントリは常にＲＡＷバイト値であるため、最初のエントリには制御コードビットは不要である。
【０１３５】
共通デルタバイトテーブル内にデルタ値とＲＡＷバイト値が混在することは、テーブルからの２つの共通バイト値間の距離が大きすぎて８ビット未満のデルタ値で表せない場合に共通バイトテーブルサイズを縮小するために有用な特徴である。
【０１３６】
一例として、３２個の頂点を有するプリミティブブロックからの頂点パラメータバイトデータブロックを、「０ｘ０３，０ｘ６Ｂ，０ｘ０３，０ｘ４７，０ｘ０７，０ｘＦ２，０ｘＦ１，０ｘＦ２，０ｘ４７，０ｘ０３，０ｘ０Ａ，０ｘ０３，０ｘ０Ａ，０ｘ６Ｂ，０ｘ６Ｂ，０ｘ４７，０ｘ０３，０ｘ０Ａ，０ｘＦ２，０ｘＦ２，０ｘＥＣ，０ｘＥＣ，０ｘＥＤ，０ｘ０Ａ，０ｘＦ２，０ｘ０Ａ，０ｘ０３，０ｘ０Ａ，０ｘ３３，０ｘ０Ａ，０ｘ０３，０ｘ０３」とする。
【０１３７】
０ｘ０３、０ｘ６Ｂ、０ｘ４７、０ｘ０７、０ｘＦ２、０ｘＦ１、０ｘ０Ａ、０ｘＥＣ、０ｘＥＤ、及び０ｘ３３という１０個の共通バイト値が存在する。これらの共通バイトを、［０ｘ０３，０ｘ３３］、［０ｘ４７，０ｘ６Ｂ］、及び［０ｘＥＣ，０ｘＦ２］という３つの範囲内に配置して、６ビットのデルタ値を範囲として有するようにすることができる。これらの３つのバイト原点には、頂点毎に２ビットが必要であり、これによりこのバイトデータブロックは、バイトデルタブロック圧縮に適さないものとなる。
【０１３８】
共通バイトテーブルアルゴリズムを使用するには、バイトテーブルのデータサイズが、８０ビットに、各頂点におけるテーブルインデックスの４ビットを足したものになる。合計データサイズは８０＋４×３２＝２０８ビットとなり、これは元のデータサイズの２５６ビットの８１．２５％である。
【０１３９】
並べ換え後、共通バイト値は、「０ｘ０３，０ｘ０７，０ｘ０Ａ，０ｘ３３，０ｘ４７，０ｘ６Ｂ，０ｘＥＣ，０ｘＥＤ，０ｘＦ１，０ｘＦ２」となる。共通バイト値のデルタブロックは、「０ｘ０３，０ｘ０４，０ｘ０３，０ｘ２９，０ｘ１４，０ｘ２４，０ｘ８１，０ｘ０１，０ｘ０４，０ｘ０１」である。これから明らかなように、バイト値０ｘ６Ｂと０ｘＥＣの間の距離は０ｘ８１であり、大きすぎて８ビット未満のデルタ値では表せない。従って、共通バイトデルタテーブルアルゴリズムを使用してこのバイトデータブロックを圧縮することはできない。
【０１４０】
共通バイトテーブル内の共通バイト値に、制御コードを使用してデルタ値をＲＡＷバイト値と混合するアルゴリズムを適用することにより、大きなデルタ０ｘ３３，０ｘ４７，０ｘ６Ｂ及び０ｘＥＣを有するバイト値を、最初のバイト０ｘ０３と同様にＲＡＷバイトで表すことができる。残りのバイトは、３ビットのデルタ値を使用して表すことができる。
【０１４１】
ＲＡＷバイトのための制御ビットを含む共通バイトデルタテーブルは、「０３，１  ４，１  ３，０  ３３，０  ４７，０  ６Ｂ，０  ＥＣ，１  １，１  ４，１  １」となる。
【０１４２】
混合された共通バイトデルタテーブルの出力は、０ｘ０３、０ｘ３３、０ｘ４７、０ｘ６Ｂ及びＯｘＥＣという５つのＲＡＷバイトからなる。各々が３ビットの４、３、１、４及び１という５つのデルタ値に加え、テーブル内の最初のエントリを除く全てのエントリのための９ビットの制御ビットも存在する。制御コードを含む共通バイトデルタテーブルでは、総圧縮データサイズが５×８＋５×３＋９＝６４ビットになる。３２個の頂点のテーブルインデックスのための１２８ビットを加算すると、総圧縮バイトデータサイズは１９２ビットとなり、これは元の２５６ビットのバイトデータサイズの７５％である。共通バイトテーブルアルゴリズムと比較すると、制御コードを使用して、上記の例からのバイトデータブロックの共通バイトデルタテーブル内でＲＡＷバイト値をデルタ値と混合することにより、圧縮比が６．２５％上昇している。
【０１４３】
好ましい実施形態では、バイトデータブロックの共通バイトデルタテーブル内のエントリ数が、圧縮時にデルタ値に使用されるビット数とともに圧縮ヘッダに記憶される。上記の例におけるバイトデータブロックでは、共通バイトデルタテーブル内のエントリ数が１０であり、デルタ値のビット数が３ビットである。圧縮ヘッダ内には、共通バイトデルタテーブルがＲＡＷバイト値と混在していることを示す１ビットのフラグも存在する。
【０１４４】
展開時には、圧縮ヘッダから、バイトデータブロックが共通バイトデルタテーブルフォーマットであり、共通バイトデルタテーブル内のエントリ数が１０であり、デルタのビット数が３であることが分かる。この圧縮ヘッダからは、共通バイトデルタテーブルが、デルタ値がＲＡＷバイト値と混合されており、最初のエントリを除く各テーブルエントリのための制御ビットが含まれていることも分かる。テーブルインデックスに使用されるビット数は、テーブルエントリ数から、頂点毎に４ビットのテーブルインデックスであると容易に求めることができる。
【０１４５】
共通バイトテーブルを再構築するために、バイトデルタテーブルの最初のバイト値が、上記の例では０ｘ０３として読み取られる。次に、１ビットの制御コードが読み取られて、次の値が８ビットのＲＡＷバイトであるか、それとも３ビットのデルタ値であるかが判定される。好ましい実施形態では、制御コード０がＲＡＷバイトを意味し、制御コード１がデルタ値を意味する。デルタ値の場合には、これが前のバイト値に加算されて、元のバイトが共通バイトテーブルのエントリとして形成される。
【０１４６】
上記の例では、３Ｄ処理でアクセスされるプリミティブブロックからの各頂点データに関し、頂点パラメータバイトデータブロックのための３ビットのテーブルインデックスが圧縮バイトデータブロックから読み取られ、これを使用して、再構築された共通バイトテーブルからプリミティブブロック内の元のバイト値が参照される。
【０１４７】
上述したように、共通バイトテーブルインデックスのビット数は、共通バイトテーブル内のエントリ数に関連する固定数である。プリミティブブロック内の頂点の圧縮頂点パラメータバイトデータには、圧縮バイトデータブロック内の頂点の圧縮バイトデータの位置を計算することによってアクセスすることができる。
【０１４８】
共通バイトテーブルアルゴリズムは、特にデータ分布が異なりすぎて、固有バイト及びバイトデルタブロックアルゴリズムを使用して圧縮できない場合に、頂点パラメータバイトデータブロックを圧縮するための効率的な圧縮アルゴリズムである。提示した共通バイトテーブルアルゴリズムは、共通バイトデルタテーブル及びデルタ値をＲＡＷバイトと混合するための制御コードの方法によって拡張され、既存のデータ圧縮アルゴリズムよりも優れた小型の最適化された共通バイトテーブルという利点を有する。共通バイトテーブルアルゴリズムの性能が強化される。
【０１４９】
特定の実施形態では、圧縮処理が２パスで行われる。第１のパスでは、プリミティブブロックからの入力された頂点パラメータバイトデータブロックを読み取って、入力バイトデータブロック内の共通バイト数及びバイト値範囲などの、バイトデータブロックの統計データを収集する。バイトデータブロックからの最初のバイトは、共通バイトテーブル内の最初のエントリとして記憶される。バイトデータブロックの２番目のバイト以降については、各バイトデータが圧縮ユニットに入ると、これらを共通バイトテーブル内のバイト値と比較する。共通バイトテーブルからのバイトデータが一致しなかった場合、このバイト値を共通バイトテーブルに新たなエントリとして追加する。
【０１５０】
同時に、バイト値の範囲が、最小及び最大バイト値、並びにこの範囲内のデルタ値に必要なビット数を使用して記憶される。２番目のバイト以降、入力された頂点パラメータデータブロックからの全てのバイトを既存の範囲に対してチェックし、そのバイトが範囲内にあるか否かを判定する。バイトが既存の範囲外にある場合、上述したように、範囲の最小値又は最大値のいずれかを置き換えて、範囲内のデルタ値に必要なビット数も更新することにより、この範囲を更新する。
【０１５１】
第１のパスの終了時に入力バイトデータブロックから全てのバイトデータが読み取られると、共通バイト数及び共通バイトテーブル内のエントリが分かる。第１のパス後には、バイト値の範囲、及びこのバイト値の範囲内のデルタ値を表すのに必要なビット数も分かる。第２のパスにおけるバイトデータブロック圧縮のための全ての統計情報が形成される。
【０１５２】
特定の実施形態において、３Ｄコンピュータグラフィックスシステムにおける頂点パラメータバイトデータブロックの圧縮ユニットを図６に示す。３Ｄコンピュータグラフィックスシステムの圧縮ユニットに、プリミティブブロック内の頂点パラメータデータからのバイトデータブロック６０１が入力される。この入力された頂点パラメータデータブロックは、統計データを収集する第１のパス後に記憶することができ、又はハードウェア実装では、これを再び読み取って追加の記憶領域を避けることができる。
【０１５３】
図６の６０２のように、入力バイトデータブロックの共通バイト数をチェックする。バイトデータブロック内に固有バイト値が１つしか存在しない場合、固有バイトアルゴリズム６０３を使用してバイトデータブロックを圧縮する。バイトデータブロック内に複数の共通バイト値が存在する場合、第１のパスで生成されたバイト値範囲が、これらの範囲内にビット数が制限されたデルタ値を使用してバイト値を表している可能性をチェックする６０４。デルタ値のビット数及びバイト原点インデックスのビット数が８ビット未満の場合、バイトデルタブロックアルゴリズムを使用してこのバイトデータブロックを圧縮することができる。バイトデルタブロックデータへの圧縮前に、最適化された表現を得るために、バイトデータブロックの範囲を範囲のマージの可能性について調べる６０５。範囲をマージした後に、１つのバイト原点６０７、又は通常は最大４つのバイト原点６０８、６０９及び６１０である複数のバイト原点を使用してバイトデータブロックを圧縮する。
【０１５４】
固有バイトアルゴリズム又はバイトデルタブロックアルゴリズムのいずれを使用してもバイトデータブロックを圧縮できない場合、第１のパスで生成された共通バイトテーブル内の所定の最大エントリ数の値に対して共通バイト数をチェックする。好ましい実施形態では、共通バイト数が３２以下の場合、図６の６１１において、このバイトデータブロックに共通バイトテーブル圧縮アルゴリズムを適用する。
【０１５５】
バイトデータブロックのテーブルインデックスに必要なビット数は、共通バイトテーブル内のエントリ数に依存し、この数は、バイトデータブロックに関して一定の数である。圧縮比は、テーブルインデックスに必要なビット数及び共通バイトテーブルのサイズに依存する。共通バイトテーブルのサイズは、エントリ数に８ビットを乗算したものである。共通バイトデルタテーブルのサイズは、図６のデルタテーブル内のデルタ値のビット数６１２を使用して、第１のパスで生成された共通バイトテーブル内の共通バイト値から計算される。共通バイトデルタテーブルサイズを最小化する必要がある場合、１ビットの制御コードを使用する。デルタテーブルサイズがＲＡＷバイトテーブルのサイズよりも小さい場合には、圧縮に共通バイトデルタテーブルアルゴリズム６１４を使用する。その他の場合には、共通バイトテーブルアルゴリズム６１５を使用してバイトデータブロックを圧縮する。
【０１５６】
共通バイトデルタテーブルサイズ及びプリミティブブロック内の全ての頂点のテーブルインデックスを含む総圧縮データサイズが、元のバイトデータブロックのサイズよりも小さい場合には、共通バイトデルタテーブルアルゴリズムを使用してバイトデータブロックを圧縮する６１６。その他の場合には、バイトデータブロックを圧縮せずにＲＡＷバイトデータブロックとして出力する６１８。同様に、共通バイトテーブルサイズ及びプリミティブブロック内の全ての頂点のテーブルインデックスを含む合計圧縮データサイズが、元のバイトデータブロックのサイズよりも小さい場合には、共通バイトテーブルアルゴリズムを使用してバイトデータブロックを圧縮する６１７。その他の場合には、バイトデータブロックを圧縮せずにＲＡＷバイトデータブロックとして出力する６１８。
【０１５７】
特定の実施形態では、共通バイト値の数が、３２などの所定の閾値よりも大きい場合６１１、バイトデータブロックをＲＡＷバイトデータブロックとして出力する６１８。
【０１５８】
圧縮頂点パラメータのデータ構造
上述したように、圧縮頂点パラメータデータは、圧縮ヘッダデータ及び圧縮頂点データという２つの部分からなる。各頂点パラメータバイトデータブロックのための圧縮ヘッダデータは、圧縮フォーマット、固有バイト値、バイト原点値、及び共通バイトテーブル又は共通バイトデルタテーブルのデータを含む。圧縮頂点データは、バイトデータブロックの圧縮フォーマットに依存して、各頂点に関して一定のサイズである。
【０１５９】
表４に、本発明における圧縮アルゴリズムの圧縮頂点パラメータデータ構造を示す。
2013541755.tif 000006
表４：圧縮フォーマット及び圧縮データサイズ
【０１６０】
圧縮後、圧縮ヘッダデータには、圧縮ユニットによってバイトデータブロックの圧縮フォーマット及び表４に示す他の圧縮ヘッダデータが書き込まれる。表４に示す各圧縮フォーマットの圧縮頂点パラメータデータは、別個の圧縮頂点データブロック内に出力される。
【０１６１】
プリミティブブロック内の三角形の３Ｄ処理において頂点パラメータが必要な場合、最初に頂点パラメータデータの各バイトの圧縮ヘッダデータから圧縮フォーマットを読み取る。表４に示す圧縮フォーマットに従って、追加のヘッダデータを読み取ることもできる。
【０１６２】
バイトデータブロックがＲＡＷバイトフォーマットである場合、圧縮ヘッダからの追加データは存在せず、圧縮頂点データブロック内に各頂点の８ビットのバイトデータが出力される。展開時には、頂点パラメータデータのバイトが必要な場合、この８ビットのバイトデータが読み取られる。
【０１６３】
バイトデータブロックが固有バイトフォーマットである場合、圧縮ヘッダ内に８ビットの固有バイト値が出力され、全てのバイト値が圧縮ヘッダ内の固有バイト値と同じであるため、圧縮頂点データブロック内には出力は存在しない。展開時には、プリミティブブロック内の全ての頂点について、８ビットの固有バイトデータが頂点パラメータバイトデータとして使用される。
【０１６４】
バイトデータブロックがデルタブロックフォーマットである場合、圧縮ヘッダ内に、バイト原点数、バイト原点値及びデルタ値のビット数に関する追加データが存在する。圧縮頂点データブロック内に、頂点パラメータデータの各バイトのデルタ値が出力される。複数のバイト原点の場合、圧縮頂点データブロック内にバイト原点インデックスも出力される。デルタ値及びバイト原点インデックス値は、圧縮ヘッダ内に示されるように、プリミティブブロック内の全ての頂点に関して一定のビット数である。展開時には、圧縮ヘッダから、バイト原点数、デルタビット数及びバイト原点値が読み取られる。３Ｄレンダリングでアクセスされる各頂点パラメータバイトデータに関しては、圧縮頂点パラメータバイトデータブロックから固定サイズのデルタ値が読み取られる。複数のバイト原点の場合には、圧縮頂点パラメータバイトデータブロックから頂点のバイト原点インデックス値も読み取られる。このバイト原点インデックスによって示されるバイト原点値にデルタ値が追加されて、元のバイトデータが再構築される。
【０１６５】
バイトデータブロックが共通バイトテーブルフォーマットである場合、圧縮ヘッダ内に、共通バイトテーブル内のエントリ数及びバイト値に関する追加データが存在する。表４に示すように、圧縮頂点データブロック内に、頂点パラメータデータの各バイトのためのテーブルインデックス値が出力される。このテーブルインデックス値は、圧縮ヘッダ内に示されるように、共通バイトテーブル内のエントリ数に依存してプリミティブブロック内の全ての頂点に関して一定のビット数である。展開時には、圧縮ヘッダから、共通バイトテーブルのエントリ数及びバイト値が読み取られる。３Ｄレンダリングでアクセスされる各頂点パラメータバイトデータに関しては、圧縮頂点パラメータバイトデータブロックから固定サイズのテーブルインデックス値が読み取られ、共通バイトテーブルから元のバイト値が参照される。
【０１６６】
バイトデータブロックが共通バイトデルタテーブルフォーマットである場合、圧縮ヘッダ内に、共通バイトデルタテーブル内のエントリ数、デルタ値のビット数、共通バイトデルタテーブル内でデルタ値をＲＡＷバイト値と混合するための制御コードが存在するかどうかを示す１ビットのフラグに関する追加データが存在する。圧縮ヘッダ内には、共通バイトデルタテーブルの合計サイズも出力され、従って展開時には、表４に示すように、圧縮ヘッダから共通バイトデルタテーブルのデータを正しく読み取ることができる。共通バイトテーブルフォーマットの場合と同様に、圧縮頂点データブロック内には、頂点パラメータデータの各バイトのテーブルインデックス値が出力される。このテーブルインデックス値は、圧縮ヘッダ内に示されるように、共通バイトデルタテーブル内のエントリ数に依存してプリミティブブロック内の全ての頂点に関して一定のビット数である。展開時には、圧縮ヘッダから、共通バイトデルタテーブルのエントリ数、デルタ値のビット数及び制御コード存在フラグが読み取られる。次に、圧縮ヘッダから固定ビット数のデルタ値が読み取られて、共通バイトテーブル内の前のバイトに加算される。制御コードを使用している場合には、これを最初に読み取って、後続のエントリがデルタ値であるか、それとも８ビットのＲＡＷバイト値であるかを判定する。共通バイトテーブルは、共通バイトデルタテーブルを復号することにより形成することができる。
【０１６７】
共通バイトテーブルフォーマットと同様に、３Ｄレンダリングでアクセスされる各頂点パラメータバイトデータに関しては、圧縮頂点パラメータバイトデータブロックから固定サイズのテーブルインデックス値が読み取られて、共通バイトデルタテーブルから再構築された共通バイトテーブルから元のバイト値が参照される。
【０１６８】
頂点パラメータデータブロックの圧縮及び展開
特定の実施形態において、３Ｄコンピュータグラフィックスシステムにおける３２ビット浮動小数点頂点パラメータデータブロックのための圧縮ユニットを図７に示す。プリミティブブロックからの頂点パラメータデータブロック７０１が３Ｄコンピュータグラフィックスシステムに到来すると、図７の７０２において、３２ビット浮動小数点フォーマット値の符号ビットを最上位ビットから最下位ビットに移動させる。次に、この浮動小数点頂点パラメータデータブロックを４つのバイトデータブロックに分離して、圧縮ユニット７０３、７０４、７０５及び７０６内で別個に圧縮する。図７の７０７のように、４つのバイトデータブロックからの全ての頂点についての圧縮データを互いにマージして、プリミティブブロック内に圧縮頂点パラメータデータを形成する。
【０１６９】
特定の実施形態において、３Ｄコンピュータグラフィックスシステムにおける圧縮頂点パラメータデータブロックのための展開ユニットを図８に示す。プリミティブブロックからの圧縮頂点パラメータデータブロック８０１が３Ｄコンピュータグラフィックスシステムに到来すると、表４に示す圧縮ヘッダ内の各バイトの圧縮フォーマットに従って、頂点の圧縮頂点パラメータデータを、４バイトの頂点パラメータデータのための４つのデータに分割する。各バイトの４つのデータを、展開ユニット８０２、８０３、８０４及び８０５内で別個に展開する。この４つのバイトからの全ての頂点についての展開データを互いにマージした後、図８の８０６において、３２ビット浮動小数点フォーマット値の符号ビットを最下位ビットから最上位ビットに移動させる。最後に、図８の８０７のように、プリミティブブロック内の全ての頂点についての３２ビットの頂点パラメータデータを再構築する。
【０１７０】
図６、図７及び図８に示すように、本発明の好ましい実施形態における圧縮及び展開処理は、コンピュータハードウェア内に実装して、３Ｄコンピュータグラフィックスシステムパイプライン、特にタイルベースのレンダリングに組み込むことができる。圧縮ユニット内でアルゴリズムを組み合わせることにより、３Ｄコンピュータグラフィックスシステムからの頂点パラメータデータブロックの圧縮性能が高くなる。３Ｄゲームからの頂点パラメータデータブロックに対する実験では、９０％を超える時間にわたって上記のアルゴリズムの１つを使用して頂点パラメータバイトデータブロックを圧縮できることが示された。提示したアルゴリズムを使用して、３Ｄコンピュータグラフィックスシステムにおける頂点パラメータデータブロックのデータを全体として４０％削減できると予想される。
【０１７１】
提示した方法による頂点パラメータデータの圧縮の実現に加え、その他の利点も存在する。
【０１７２】
元の頂点パラメータデータからの情報損失はなく、この提示したアルゴリズムは全く無損失の圧縮法である。これらの圧縮アルゴリズムは、高品質レンダリング画像を必要とする３Ｄコンピュータグラフィックスシステムにおける頂点パラメータデータの圧縮に適している。
【０１７３】
これらの圧縮アルゴリズムでは、バイトデルタブロックアルゴリズムにおけるバイト原点、及び共通バイトテーブルアルゴリズムにおけるバイトテーブル又はバイトデルタテーブルのために、限られた構成可能記憶メモリ空間しか必要としない。提示したアルゴリズムは、３Ｄコンピュータグラフィックスハードウェア内への実装にとってコスト効率が高い。
【０１７４】
これらのアルゴリズムでは複雑な計算が必要なく、アルゴリズムからの圧縮及び展開の演算が単純かつ高速である。これらのアルゴリズムは、高速３Ｄコンピュータグラフィックスレンダリングの生成において使用することができる。
【０１７５】
これらの圧縮アルゴリズムを使用すると、圧縮データのサイズが、プリミティブブロック内の全ての頂点に関して一定のビット数になるため、プリミティブブロック内のあらゆる頂点からの圧縮頂点データにランダムアクセスすることができる。この特徴は、タイルベースの３Ｄコンピュータグラフィックスハードウェアシステムにおける頂点パラメータデータの圧縮にとって特に有益である。この場合、タイルベースの３Ｄコンピュータグラフィックスシステムにおいて、プリミティブブロックからのプリミティブが多くのタイルをカバーすることができる。タイル内のレンダリングに全ての頂点が必要でない場合もあり、従ってレンダリング処理中に頂点パラメータデータブロックにランダムアクセスが可能であることが非常に望ましい。
【０１７６】
エントロピー符号化などの圧縮アルゴリズムの従来技術で説明したように、いずれかの頂点パラメータデータにアクセスできるようになるには、データブロック全体を展開する必要がある。このことは、タイルベースの３Ｄコンピュータグラフィックスシステムの性能、特に多くのタイルをカバーするプリミティブブロックに大きな影響を与え、全体的なプリミティブブロックの頂点パラメータデータを何度も展開する必要がある。
【０１７７】
本発明の圧縮アルゴリズムは、圧縮データブロック内の頂点パラメータデータに対するランダムアクセスを可能にし、従って３Ｄレンダリング処理において、レンダリングのタイル内で使用される頂点の展開データのみがフェッチされ展開される。本発明の圧縮アルゴリズムは、性能の高さに関して従来の圧縮アルゴリズムに優る利点を有し、タイルベースの３Ｄコンピュータグラフィックスシステムがこれを使用して、圧縮データブロックから頂点パラメータデータを選択的にフェッチすることができる。
【符号の説明】
【０１７８】
６０１  バイトデータストリーム
６０２  固有バイト
６０４  デルタビット及び原点インデックスビット＜８
６０５  範囲をマージ
６０６  １つの原点
６０８  ２つの原点
６０３  固有バイト
６０７  １つの原点のデルタストリーム
６０９  ２つの原点のデルタストリーム
６１０  ３つ又は４つの原点のデルタストリーム
６１１  固有バイト≦３２
６１２  デルタテーブルサイズ
６１３  デルタテーブルサイズ＜バイトテーブルサイズ
６１４  デルタサイズ＜ＲＡＷバイト
６１５  デルタサイズ＜ＲＡＷバイト
６１６  共通バイトデルタテーブル
６１７  共通バイトテーブル
６１８  ＲＡＷバイト
【図１】
2013541755.tif 000007
【図２】
2013541755.tif 000008
【図３】
2013541755.tif 000009
【図４】
2013541755.tif 000010
【図５】
2013541755.tif 000011
【図６】
2013541755.tif 000012
【図７】
2013541755.tif 000013
【図８】
2013541755.tif 000014
【国際調査報告】
2013541755.tif 000015
2013541755.tif 000016