(57)【特許請求の範囲】
【請求項１】
３次元イメージングシステムに含まれるテクスチャリングシステムであって、
画像をテクスチャする際に用いるために、低下していく解像の異なるレベルの階層的に連続したミップマップを備えたミップマップデータを記憶するためのメモリ手段（２２）と、
必要なミップマップデータのタイプと、前記データをそこから取り出すことになる１つ又は複数のミップマップのレベルとを示す入力データを受け取るための入力手段（２６）と、
前記入力手段と前記メモリ手段とに接続され、前記入力データに従って、必要なミップマップデータをメモリから検索する制御手段（２４）と、
メモリから検索されたミップマップデータの部分を記憶し、選択されたミップマップレベルと関連づけるための、前記制御手段に連結されているキャッシュ手段（３０；６０）と、
前記キャッシュ手段に連結されていて、前記キャッシュ手段内に保持されているミップマップの一連の階層において次に下位のミップマップの部分を生成するための、下位レベルのミップマップ生成器手段（３６；６６）と、
ミップマップの１つのレベルからミップマップデータを受け取るために前記キャッシュ手段に連結され、及び、一連の前記階層において次に下位のミップマップからミップマップデータを受け取るとともに、受け取った二つのミップマップレベルからの入力テクセルから出力テクセルを補間するために前記下位レベルミップマップ生成器に連結されているトリリニア補間器手段（３４；６４）と、
を備えているテクスチャリングシステム。
【請求項２】
前記メモリ手段内に圧縮された形態で記憶されているミップマップデータを解凍するための解凍手段（３２；６２）を含んでいることを特徴とする請求項１に記載のテクスチャリングシステム。
【請求項３】
前記解凍手段（３２；６２）は、前記キャッシュ手段に連結されている入力と、前記トリリニア補間器手段と前記下位レベルミップマップ生成器手段の両方に連結されている出力とに接続されていることを特徴とする請求項２に記載のテクスチャリングシステム。
【請求項４】
並行に配置されている４つのキャッシュ手段（６０）と４つの解凍圧縮手段（６２）とがあることを特徴とする請求項２又は３の何れかに記載のテクスチャリングシステム。
【請求項５】
前記キャッシュ手段（６０）と前記解凍手段（６２）との間に、異なるキャッシュの出力を前記解凍手段の内の選択された１つに割当てるための割当て手段（８２）を更に備えていることを特徴とする請求項２、３又は４の何れかに記載のテクスチャリングシステム。
【請求項６】
前記下位レベルのミップマップ生成器手段は、前記キャッシュ手段内に保持されているミップマップからの１６個のテクセルで演算して、４個のテクセルを次に下位であるミップマップからのものとして提供する４つの補間器を備えていることを特徴とする請求項１乃至５の何れかに記載のテクスチャリングシステム。
【請求項７】
３次元イメージングで用いられるテクスチャリングの方法において、  画像をテクスチャする際に用いるために、低下していく解像の異なるレベルの階層的に連続したミップマップを備えたミップマップデータをメモリに記憶する段階と、
必要なミップマップデータのタイプと、前記データをそこから取り出すことになる１つ又は複数のミップマップのレベルを示す入力データを受け取る段階と、
前記入力データに従って、必要な前記ミップマップデータをメモリから検索する段階と、
メモリから検索されたミップマップデータの部分をキャッシュに記憶し、選択されたミップマップレベルと関連づける段階と、
前記キャッシュ手段に保持されているミップマップの一連の階層において、次に下位のミップマップの部分をリアルタイムに生成する段階と、
前記キャッシュに記憶されているミップマップレベル及びリアルタイムに生成された一連の階層において次に下位のミップマップからの入力テクセルから出力テクセルを補間する段階と、
を含んでいる方法。
【発明の詳細な説明】
【０００１】
（発明の属する技術分野）
本発明は、コンピュータディスプレイで使われるような３次元（３Ｄ）イメージングシステムで使用するためのテクスチャリングシステムに関する。そのようなテクスチャリングシステムは、例えば、コンピュータゲームのディスプレイに用いられる。
【０００２】
（従来技術）
以下の従来技術に関する参考文献及び資料は、本技術の背景に関する更なる情報を提供するものである。その中の幾つかは、適宜、以下の明細書中に下記参考文献番号で引用されている。
【０００３】
（１）Ｅ．Ｃａｔｍｕｌｌによる「曲面コンピュータディスプレイ用のサブディビジョンアルゴリズム」ＰｈＤ学位論文、ユタ州ソルトレーク大学、コンピュータ科学部、レポートＵＴＥＣ−Ｃｓｃ−７４−１３３、１９７４年１２月。
【０００４】
（２）Ｊ．Ｆ．Ｂｌｉｎｎ及びＭ．Ｅ．Ｎｅｗｅｌｌによる「コンピュータ生成イメージにおけるテクスチャ及び反射」ＣＡＣＭ、１９（１０）１９７６年１０月、５４２−５４７。
【０００５】
（３）Ｇ．Ｗｏｌｂｅｒｇによる「デジタルイメージワーピング」ＩＥＥＥコンピュータソサエティ出版、カリフォルニア州ロスアラミトス、１９９０年。
【０００６】
（４）Ｌ．Ｗｉｌｌｉａｍｓによる「ピラミッド状パラメトリック」ＳｉＧＧＲＡＰＨ  ８３、１−１１ページ。
【０００７】
（５）ビデオロジックの「アポカリプス３Ｄｘデータ」英国キングスラングレイ、ビデオロジックから入手可能。
【０００８】
（６）マイクロソフト社の「テクスチャ及びレンダリングエンジン圧縮（ＴＲＥＣ）」マイクロソフト技術概要、インターネットアドレス  ｗｗｗ．ｍｉｃｒｏｓｏｆｔ．ｃｏｍ／ｈｗｄｅｖ／ｄｅｖｄｅｓ／ｗｈｎｔｒｅｃ．ｈｔｍ。
【０００９】
（７）Ａ．Ｃ．Ｂｅｅｒｓ、Ｍ．Ａｇｒａｗａｌａ、Ｎ．Ｃｈａｄｄｈａによる「圧縮されたテクスチャからのレンダリング」１９９６年、コンピュータグラフィクス年次総会、３７３ページ。
【００１０】
（８）Ｚ．Ｓ．Ｈａｋｕｒａ、Ａ．Ｇｕｐｔａによる「テクスチャマッピングのためのキャシュアーキテクチャの設計及び分析」コンピュータアーキテクチャニュース第２５巻第２号、１０８−１２０ページ、１９９７年５月。
【００１１】
（９）米国特許ＵＳ−Ａ−５，６１２，７４７「リアルタイムビデオコーダにおけるベクトル量子化キャッシングのための方法及び装置」。
【００１２】
（１０）英国特許出願ＧＢ−Ａ−２，２９７，８８６「３Ｄイメージのテクスチャリング及びシェーディング」出願人：ビデオロジック社。
【００１３】
（１１）Ｒ．Ｍ．Ｇｒａｙによる「ベクトル量子化」ＩＥＥＥ会報、１９８０年１月、４−２０ページ。
【００１４】
（１２）Ｊ．Ｋｏｅｇｅｌ  Ｂｕｆｏｒｄによる「マルチメディアシステム」アディソンウーズレイ出版社、１９９４年。
【００１５】
（１３）Ｆ．Ｆｏｌｅｙ及びＡ．ｖａｎＤａｍによる「コンピュータグラフィクスの基本及び実践」アディソンウーズレイ出版社、１９９０年。
【００１６】
（１４）マイクロソフト社「ダイレクトＸ  ６．０  ＳＤＫドキュメンテーション」米国レッドモンド、マイクロソフト通り１、マイクロソフト社、インターネットアドレス：  ｗｗｗ．ｍｉｃｒｏｓｏｆｔ．ｃｏｍ／ｄｉｒｅｃｔｘ。
【００１７】
（発明の背景）
コンピュータベースの画像は、一般的に、画素即ちピクセルの列で形成されている。表示される各表面は、一般的には三角形であるポリゴン内のピクセルにより表される。表面には「テクスチャマッピング」として知られるオペレーションにより、カラー、テクスチャ、及び／又はシェーディングが与えられる。テクスチャはピクセルの列として記憶され、それを便宜上テクセル（テクスチャピクセル）と呼ぶ。従って「テクスチャマッピング」は、２Ｄ（二次元）配列のテクセルを３Ｄ（３次元）シーン内の表面を表す別の２Ｄ配列ピクセル上にマッピングすることを含む。この技術は、Ｃａｔｍｕｌｌ（参考文献１）により開発され、Ｂｌｉｎｎ及びＮｅｗｅｌｌ（参考文献２）により改良された。透視テクスチャマッピングには、その透視が最終画像に正しく現れるように、テクスチャマップを回転する段階と変換する段階とが含まれている。テクスチャマッピングは、オブジェクトの表面に写実的な仕上げを付与することにより、シーンのリアリズムを高める。例えば、マーブルテクスチャを、像の表面へマッピングすると、像はマーブルで作られたような外観が与えられる。大きなシーンでは、シーン内に存在している全ての異なるテクスチャを表示するために、多数の異なるテクスチャビットマップが必要となる。
【００１８】
上記のように、通常３Ｄシーンは、多数のポリゴン又は三角形で表示される。ポリゴンをテクスチャで満たすために、その表面上の各ピクセルを用いてテクスチャマップ内のテクセルの座標が計算される。テクスチャマップ内の計算されたテクセルに最も近いテクセルを用いて、最終的に表示されるピクセルがシェードされる。これは、ポイントサンプリングと呼ばれる。替りに、バイリニアフィルタリング又はバイリニア補間を用いてテクスチャされた画像の質を高めることもできる。バイリニアフィルタリングでは、そこから２Ｄピクセルが３Ｄ面上にマップされることになるテクスチャマップ内のポイントが、サブピクセル精度に対して計算される。次に、ピクセルカラーを更に正確に表示するため、テクスチャマップ内でこの計算された位置に最も近い４個のピクセルをブレンドするのに、バイリニアフィルタリング又は補間が用いられる。これは、添付の図１に示されており、テクセルＡ、Ｂ、Ｃ、Ｄはブレンドされて、二次元画像平面上のポイントＸにおけるピクセルのテクセル値が与えられる。このバイリニア、即ち２軸のフィルタリング（又は補間）のオペレーションは、参考文献３でも述べられている。
【００１９】
トリリニア（３軸）フィルタリングは、最も近い４個のピクセルを、２つの異なるミップマップレベル（参考文献４）で同様に処理する。このことは、本出願の図２に示されている。ミップマップは、解像が連続的に半減されるようにフィルタを掛けることにより前処理された、オリジナルテクスチャマップのコピーである。本明細書では、ＭＩＰはＭＵＬＴＵＭ  ＩＮ  ＰＡＲＶＯ（ｍｕｃｈ  ｉｎ  ａ  ｓｍａｌｌ  ｐｌａｃｅ）の略である。これは、最終画像のサイズが１ピクセルになるまで繰り返され（これは、テクスチャが四角形でそのサイズが２の累乗であることを前提としている）るので、ミップマップが階層的に続くことになる。図３は、１２８×１２８の解像におけるブリックテクスチャの例を、これに関わる下位のミップマップレベルと共に示したものである。ミップマップを、ピラミッドとして考えることもできる。
【００２０】
テクスチャフィルタリングには、テクスチャをサンプリングする際に、エイリアシングの発生を減じる効果がある。エイリアシングに関する更なる情報に関しては、参考文献３を参照されたい。
【００２１】
３Ｄ画像の生成では、計算負荷が増大する。シーンがより写実的になり、画像がリアルタイムに応答することが求められるほど、ゲーム及び計算機支援設計（ＣＡＤ）アプリケーションの動画化された３Ｄ画像は、処理能力に関して益々費用が嵩むものになっている。シーン内のポリゴン構造の幾何学形状を決定するためには、多数の浮動小数点計算が必要であり、そのポリゴンを満たしてシェードするためには、多数の算術演算が必要である。これらの演算をソフトウェアの何倍も効果的に、実行できる専用ハードウェアが、入手可能（参考文献５）である。記憶されているデータベースへのアクセスも、性能に対する制限要因である。専用ハードウェア内のローカルメモリは、あらゆるメモリアクセスのボトルネックの影響を減じることができる。テクスチャマッピングは、特に、ディスプレイ上にマップされる全ピクセルのために多くのテクスチャピクセルが読み取られるフィルタリング（即ち、補間）演算の実行時には、メモリ負荷が増大する。
【００２２】
従って、２Ｄテクスチャマップデータのサイズは、より小さなメモリスペース内に配置できるように、テクスチャ圧縮によって小さくされる。必要なメモリが小さくなれば、システムの低コスト化につながる。オリジナルのテクスチャマップは、圧縮されたデータを解凍することにより取り出すことができる。３Ｄシーンが写実的になるほど、テクスチャマップは大きくなり、数も増すので、テクスチャの圧縮を利用することが重要になる。マイクロソフト社からのテクスチャ及びレンダリングエンジン圧縮（ＴＲＥＣ、参考文献６）を含め幾つかの方式が既に開発されている。圧縮されたテクスチャから画像をレンダリングする技術について最初に論じたのはＢｅｅｒｓ（参考文献７）である。
【００２３】
この時点で、システム設計者が利用できる様々なタイプのメモリを考えて、画定するのは都合がよい。先の「ローカルメモリ」という用語は、メモリ制御半導体デバイス又は回路の近くに配置されている固体半導体メモリを指している。又「内部メモリ」という用語は、言及されている特定の半導体デバイス内に配置されているメモリのことである。更に「外部メモリ」は、半導体デバイスの外部のあらゆるメモリを指す。ローカルメモリはＤＲＡＭベースであってもよい。ＤＲＡＭはＤｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙの頭文字をとったものであり、固体半導体である。同期型ＤＲＡＭ（ＳＤＲＡＭ）は、データアクセスが、クロック信号と同期して動作するようにすることができる。ＳＤＲＡＭは、そのパイプライン化アーキテクチャの故にＤＲＡＭよりも高いアクセスバンド幅機能を有するが、コスト高である。ローカルメモリ及び内部メモリはＤＲＡＭ又はＳＤＲＡＭベースであってもよい。外部メモリは、半導体でも、ハードディスクのような大容量記憶装置アレイであってもよい。半導体メモリは非常にコスト高であり、コンピュータシステム全体のコストの内の大きな割合を占める。
【００２４】
ＤＲＡＭは多重化アドレスバスを通してアドレス指定され、即ち、個々のデータ項目にアクセスするのに必要なアドレスは、２つの部分で記憶装置へ送信される。ＤＲＡＭ装置内のコアメモリアレイは、長方形マトリックスであり、行制御ラインと列制御ラインが同時に起動されるときに、１つのデータ項目がアドレス指定される。これは、別々の行と列のアドレスを必要とする。連続するアクセスの間に行アドレスが変わらなければ、列アドレスだけを送信すればよい。ＤＲＡＭアレイ内の１行のデータは１つのページとして知られている。アクセスの間に行アドレスが変わらなければ、そのアクセスは「ページ内にある」と言われる。この「ページ内にある」アクセスは、２ページ以上に亘るアクセスよりも遙かに早いので、メモリシステム設計者はアクセスのバーストを１ページ内に収めようと努力している。ＳＤＲＡＭのようなある種の記憶装置は、性能を向上させるために、複数のメモリバンクを利用している。各メモリバンクは自分のページを開くことができるので、ページをめくることなく別々のメモリ領域にデータアクセスすることができる。
【００２５】
メモリ性能を高めるために用いられる技術の１つは、全ての外部メモリアクセスの結果が、別々の内部メモリ内に記憶される「メモリキャッシング」である。この内部メモリには、外部メモリよりも早くアクセスできる。特定のメモリアクセスの結果が既にキャッシュ内にあれば、外部メモリに代わってキャッシュが読み出しされる。これは、外部メモリへの通信量を減らす効果があるので、そのメモリの「バンド幅」要件が少なくなる。メモリシステムバンド幅要件は、そのシステムのコストに直接関ることが多い。バンド幅が固定されているシステムでは、バンド幅要件が増大するとシステム全体の性能が低下することもある。
【００２６】
テクスチャリングは、全てのテクスチャをメモリから検索しなければならないので、３Ｄイメージングの中でも最も機能集約的なプロセスである。先に説明し図１及び２に示しているように、トリリニア及びバイリニアフィルタリング（補間）のような技術では、ディスプレイ上に投射される全てのピクセル毎に、８個ものテクスチャピクセル又はテクセルを、メモリから検索する必要がある。従って、テクスチャリングには、メモリへの非常に高いバンド幅のパスが必要である。テクスチャキャッシングを使えば、テクスチャリングバンド幅要件を減らし、システムの性能を高めることができる。最適性能目標は、１回の処理パイプラインクロックサイクルで、必要な全てのテクセルを読み取り可能にすることである。テクスチャアクセスの性能を高めるためにキャッシュを使う効果に関して、幾つかの研究（参考文献８）が既に行われている。Ｈａｋｕｒａは、テクスチャマッピンググラフィクスに対してキャッシュがどれほど高い効果を上げることができるかを示し、有効メモリ対バンド幅比は、あるキャッシング戦略を使うことで、３分の１から１５分の１に小さくできると結論している。
【００２７】
先に示したように、テクスチャマッピングは、３Ｄオブジェクトの表面上に高い詳細レベルのものをマッピングすることにより、３Ｄ画像品質を高めるのに用いられる。これは、オブジェクトの幾何学形状を複雑にすることなく行われるべきである。しかしながら、テクスチャマッピングは、エイリアシングを含む様々な目に見えるアーティファクト（参考文献１３）を作り出す。最終画像の品質を高めるためにバイリニアフィルタリング（参考文献３）が用いられるが、バイリニアフィルタリングでは解決できない、デプスエイリアシングを含む多くのアーティファクトが残る。デプスエイリアシングは、オブジェクトが視点から遠ざかるにつれて、テクスチャが圧縮される結果である。ミップマップ（参考文献４）を使えば、この形態のエイリアシングを解決することができるが、なおミップバンディングと呼ばれる問題が残る。ミップバンディングは、テクスチャが或る詳細レベルから別のレベルへ変わる際に、ミップマップ間での遷移期間の間に起こる。これは、例えば、前景では道路上に現れても、遠くなると消失するようなものである。連続するミップマップは道路に沿って用いられ、１つのミップマップから次のミップマップへの遷移を見ることができる。先に述べたように、この問題は、ミップマップ間の詳細レベルを補間するトリリニアフィルタリング（参考文献４）のアプリケーションを使えば解決できる。
【００２８】
トリリニアフィルタリングの最良の形態は、それがピクセル毎ベースで実行されるというものである。これは、最終的オンスクリーンピクセルを作り出すために、８個のテクスチャピクセル（テクセル）を必要とする。これらのテクセルはメモリ内のどこにでも配置され得るので、しばしば８個別々のメモリ読み取りが必要となる。２つのミップレベルの間でトリリニアフィルタリングが実行されると、１つのミップマップ位置から４つのメモリ読み取りが起こり、別のミップマップ位置から４つのメモリ読み取りが起こる。システムメモリテクスチャリングの方がより一般的であるが、テクスチャは、通常はローカルメモリ内に保存されている。これらのメモリはバンド幅が限定されており、多数の異なるアプリケーションに関して、メモリへのリソースとして働くように求められることが多い。セットアップパラメータ、デプス情報及びディスプレイ情報は、一般的にローカルメモリ内に記憶され、システムアプリケーションは、一般的にシステムメモリから実行される。８個の各メモリの、ピクセル毎の読み出しは、一般的に多くのメモリシステムの能力を越えている。このため、ミップマップ間のページ変更に加えて、これは、適切な３Ｄ機能を達成し得ないこともよくある。
【００２９】
トリリニアテクスチャアクセスシステムに必要なメモリバンド幅は、各テクスチャフィルタリング演算に必要なメモリアクセスの数と、アプリケーションによって要求されるピクセルスループット性能とによって決まる。式１は、テクスチャのバンド幅がどのように決定されるかを示している。この式は、ページブレイクのバンド幅がどのように考慮されねばならないかについても示している。
Bandwidthtexture＝（（Accessespixel×Widthmemory）＋（Accessespage_break×Widthmemory））
×Throughputpixel                ・・・・・式（１）
但し、Bandwidthtextureはメモリから要求されるテクスチャのバンド幅で、bytes/sで測定される。これは、メモリが供給できるメモリバンド幅ではない。
【００３０】
Accessespixelは、１ピクセル当たりの平均メモリアクセス数である。正しいデータ幅であっても、必要なすべてのテクセルが必ずしも１つのアクセスで読み取られ得るわけではない。
【００３１】
Accessespage_breakは、１ピクセル当たりのページブレイクで失われた平均メモリアクセススロット数である。ＳＤＲＡＭを用いると、１つのページブレイクには、少なくとも８個のアクセススロットが必要である。
【００３２】
Widthmemoryはメモリデータバスの幅であり、bytesで測定される。これは、１クロックサイクルで４個のテクセルが確実に読み取りできるようにするためには、少なくとも８バイト（６４ビット）なければならない。
【００３３】
Throughputpixelはアプリケーションに要求されるピクセルスループットであり、pixels/sで測定される。最新のアプリケーションでは、約100Mpixels/sである。
【００３４】
１ピクセル当たりの平均アクセスは、フィルタリング演算に必要な全データを検索するのに必要な個々のメモリアクセスの回数である。６４ビットのメモリバスを用いる場合、４個の１６ビットテクセルが必要であり、それらが同じデータワード内に存在すれば、最大のスループットが得られる。残念ながら、いつもこうとは限らず、テクスチャデータが２つ又は４つの別のワード内に存在することも多い。式２は、１つのテクスチャ演算に関し、変動するアクセス数を考慮してどのようにＡｃｃｅｓｓｅｓｐｉｘｅｌを算出するかを示している。
Accessestexture＝((Percentagesingle x1)+(Percentagedouble x2)+(Percentagequadruple x4)xMipmaps)/ Factorcompression                      ・・・・・式（２）
但し、Percentagesingleは、１つのメモリアクセスで検索可能な１つのミップマップアクセスのパーセンテージである。
【００３５】
Percentagedoubleは、２つのメモリアクセスで検索可能な１つのミップマップアクセスのパーセンテージである。
【００３６】
Percentagequadrupleは、４つのメモリアクセスで検索可能な１つのミップマップアクセスのパーセンテージである。
【００３７】
Mipmapsは、フィルタ演算に含まれるミップマップの数である。
【００３８】
Factorcompressionは、テクスチャが圧縮される場合の、圧縮係数である。
【００３９】
平均アクセス数は、全データが、１回か、２回か、４回のアクセスで検索される可能性を考慮して計算される。又、式はフィルタリング演算に必要なミップマップ数も考慮し、トリリニアフィルタリングは２回だが、バイリニアフィルタリングは一回だけである。式は又、平均アクセス数が、圧縮により線形にどのように減少するかを示している。明らかに、フェッチするデータが少なければ必要なメモリアクセスは少なくなり、全データが同じデータワード内に存在している可能性が大きくなる。
【００４０】
式１は、テクスチャキャッシュを用いたとしても、物理的メモリバンド幅要件は、どのような現実的なメモリシステムの範囲も越えていることを示している。このため、記憶されるテクスチャの物理的サイズを縮小し、それに伴いメモリコストも削減するためばかりではなく、そのメモリから転送されるテクスチャデータの量をも低減するために、テクスチャ圧縮が採用されている。
【００４１】
式２は、圧縮係数がメモリアクセス数にどのように影響を与えるかを示している。テクスチャがメモリから読み出された後リアルタイムで解凍するのに、高性能の専用ハードウェアを用いることもできる。これまでに、ベクトル量子化（ＶＱ、参考文献１１）や、カラールックアップテーブル（ＣＬＵＴ）又はパレット化（参考文献１２）や、離散コサイン変換（ＤＣＴ）（参考文献１２）及び幾つかの所有権の設定された技術（参考文献６、１２）を含む多くのテクスチャ圧縮技術が試みられてきた。しかし、それぞれ問題がある。ＶＱ及びパレット化のテクスチャ圧縮技術は、２つのメモリ読み取り又は大きな内部データキャッシュを必要とし、品質に限界がある。ＤＣＴは、大量の解凍ロジックを必要とし、シリコンの予算が限定されていれば実現できない。多くの所有権の設定された技術は限定された圧縮比と品質しか提供しない。式１が示すように、これらの技術は、トリリニアフィルタリングのバンド幅要件の一部しか解決しない。
【００４２】
異なるメモリバンク間で継続的にスワップするメモリアクセスストリームは、性能に大きな影響を与えることができる。式１は、ページブレイクが、テクスチャフィルタリングの性能に対して、全体として如何に支配的であるかを示している。トリリニアフィルタリングでは、ミップマップの数がしばしば２つ以上のメモリページに亘るので、ページブレイクは特に問題となる。
【００４３】
３Ｄイメージング技術は、しばしば、専用ハードウェアの解だけしか用いることのできないような高レベルの性能を要求する。このことにより、しばしば特別なシリコンチップの開発が必要となる。チップには、しばしば、テクスチャマッピング以外にも、全ての幾何学形状処理、ポリゴンセットアップ、画像投射、照度計算、フォギング計算、陰面除去及びディスプレイ制御を実行することが求められる。従って、３Ｄ画像の生成における各ステージは、全処理が同じシリコンダイ上に載せられるようにできるだけ小さく作ることが重要である。トリリニアフィルタリング演算は、広いメモリバンド幅を必要とするだけでなく、大量のロジック、従って広いシリコン領域でだけ実行することができる。必要なロジック、従ってコストが最少となるよう制限する最適な解を求めることが重要である。
【００４４】
先に述べたことから明らかなように、メモリ、スピード及びチップの構造の簡易さの要件は非常に重要で、３Ｄイメージング、特にテクスチャマッピングでは全てに課されるものである。高品質でリアルタイムのイメージングを達成しようとすれば、要件に見合う入手可能なあらゆる技術を使っても、制約はなお非常に厳しい。
【００４５】
（発明の概要）
本発明はその様々な態様を上記独立請求項で定義しているが、以下それについて説明する。有益な特徴については同じく従属請求項で述べている。
【００４６】
以下、本発明の好適な実施例を、図面を参照しながら説明する。これらの実施例では、トリリニアテクスチャフィルタリングの効率は、上位レベルミップマップから下位レベルテクスチャミップマップをオンザフライで生成し、高いメモリバンド幅要件に合う手段としてテクスチャキャッシングとテクスチャ解凍を用いることにより改善される。個別のメモリアクセスで下位レベルのミップマップを読む必要を無くすことで、ページブレイクの問題は解消し、性能が向上する。
【００４７】
更に詳しく述べると、この好適なテクスチャリングシステムは、画像をテクスチャリングする際に用いるためのミップマップデータを記憶するためのメモリを備えており、このミップマップデータは、低下していく解像の異なるレベルの階層的に連続したミップマップを備えている。必要なミップマップデータのタイプと、データをそこから取り出すことになる１つ又は複数のミップマップのレベルを表示する入力で、データが受信される。コントローラは、入力データに従って必要とされるミップマップデータをメモリから検索し、そのデータはキャッシュ内に記憶される。下位レベルミップマップ生成器は、一連の階層内ですぐ下にあるミップマップの部分を生成し、その部分のミップマップはキャッシュ内に保持される。トリリニア補間器は、キャッシュからは、１つのレベルのミップマップからミップマップデータを受け取り、下位レベルミップマップ生成器からは、更に一段低いレベルのミップマップからデータを受け取り、１つの出力テクセルを、２つのミップマップレベルからの入力テクセルから補間する。
【００４８】
ある種のデータ圧縮方式は、必要な量の解凍されたデータを提供し、下位レベルのミップマップを生成するのに用いられるフィルタリングアルゴリズムを緊密に支持することによって、オンザフライで下位ミップマップを生成するのにうまく適合する。これらの技法は、ハードウェアのオーバーヘッドを最小化しながら、３Ｄレンダリングされる画像の性能と品質を高めるのに用いることができる。
【００４９】
ある好適な実施例では、テクスチャデータが任意の圧縮されたコードで示されており、その中では選択された圧縮コード値が基本カラーを定め、別の圧縮されたコード値が、基本カラーの選択された重み付き平均により形成することができる中間カラーを定め、この対応するコード値は、選択された基本カラーのコード値の重み付き平均でもある。下位レベルミップマップ生成器は、圧縮されたコード値で演算して、出力テクセルを複数の入力テクセルから補間する。
【００５０】
（好適な実施例の詳細な説明）
以下、本発明を附随図面を参照しながら例を使って詳細に説明する。
【００５１】
図４は、本発明によるテクスチャリングシステムの特定の実施例を示す。テクスチャリングシステム２０は、イメージングシステム全体として用いられているメモリの一部を成すメモリシステム２２を備えており、このメモリシステム２２はメモリコントローラー２４により既知の方法で制御されている。メモリ２２はとりわけ圧縮されているテクスチャマップを保持し、メモリコントローラー２４を通過するメモリ出力は、テクスチャマップの要求された部分からの圧縮されたテクスチャで構成されている。何れの表面であれ必要なテクスチャを定義するパラメータは、入力２６で受信され、テクスチャアドレス生成器２８に与えられ、所望のテクスチャが配置されているメモリ２２の部分をアドレス指定する。圧縮されたテクスチャは、メモリコントローラー２４によりメモリから検索され、テクスチャキャッシュ３０内に保持される。検索されたテクスチャは、表示される表面のタイプを示す特定のテクスチャタイプに相当することになる。例えば、これはレンガ壁の一部かもしれないし、道路の表面であるかもしれない。先に述べたように、この表面テクスチャは、ミップマップの形態で、実際には圧縮されたミップマップの形態で保持されることになり、観察者からの表面の距離を考慮すると、用いられているミップマップは、表面の前の次にあるミップマップであろう。
【００５２】
テクスチャキャッシュ３０からの出力は解凍ユニット３２に与えられ、解凍ユニット３２はテクスチャ値を解凍又はデコードし、解凍されたテクセルを提供する。解凍されたテクセルは、次に、トリリニア補間器３４と、テクスチャキャッシュ３０内に保持されているミップマップに相当する、次に下位にあるミップマップの相当部分を生成するための生成器３６の両方に与えられる。生成器３６の出力も、トリリニア補間器３４に与えられる。従って、補間器は、トリリニア補間器が図２に示されているように実行できるように、考慮中の表面ポイントの前のミップマップ及び背後のミップマップからテクセルを受け取る。トリリニア補間器は出力３８でトリリニア・テクスチャされたピクセルを提供する。
【００５３】
従って、作動時、テクスチャアドレス生成器２８は８個のトリリニアテクセルのアドレスをテクスチャキャッシュ３０へ送り、次にテクスチャキャッシュ３０は、メモリ２２から関連する圧縮されたテクスチャデータをフェッチする。圧縮ユニット（ＤＵ）３２は、次に、圧縮データからの１６個の上位レベルミップマップテクセルを解凍する。４個が必要な上位レベルテクセルとして選択され、下位レベルミップマップテクスチャを生成するために、１６個すべてが下位ミップマップ生成器３６に利用される。これは、後に述べるように、４個の上位レベルテクセルが、各下位レベルテクセルを生成するために用いられることになるからである。これらの上位レベル及び下位レベルのミップマップは、次にトリリニア補間器３４が使って、１つのトリリニアピクセルを生成する。この技法を働かせるには１６個ものテクセルが必要で、圧縮されていなければ広いメモリバンド幅を示すことになるが、圧縮されていれば、ページブレイクを最小にして、メモリバンド幅がかなり改良される。
【００５４】
下位レベルのミップマップは、１クロックサイクルで、１６個の上位レベルテクセルを取り、４個の下位レベルテクセルを生成することができる４つの並行なフィルタ又は補間器４０によって生成される。図５は、このプロセスを示している。１６個のオリジナルテクセルから４個がデコードされて、４個の上位レベルテクセルが生成され、直接トリリニアフィルタリングに用いられる。これら１６個は、それぞれ４個のピクセルを含む４象限に分割され、次に４つのデジタルローパスフィルタに掛けられ、トリリニアフィルタリングに必要な４個の下位レベルミップマップテクセルが生成される。このフィルタリングアルゴリズムは、式３で示される。
Lower-level color value0＝（upper0+upper1+upper4+upper5）/ 4
Lower-level color value1＝（upper2+upper3+upper6+upper7）/ 4
Lower-level color value2＝（upper8+upper9+upper12+upper13）/ 4
Lower-level color value3＝（upper10+upper11+upper14+upper15）/ 4
・・・・・式（３）
実際の数値を式１及び式２に当てはめると、トリリニアフィルタリングのコストを求めることができる。従来のシステムでは、解凍した場合、各トリリニアピクセル毎に、１ピクセル当たり平均２ページブレイクとして、６４ビットデータの４つのアクセスが必要であると決められていた。この場合、毎秒１００Ｍピクセルを生成しなければならないシステムでは、全体のバンド幅要件は、毎秒１６ギガバイトとなる。そのような性能は容認できないが、例えテクスチャデータがキャッシュ及され、かつ圧縮される場合でも、要求されるバンド幅は、それほど良く（毎秒１３．２ギガバイト）はない。しかし、本発明による図４の生成器３６で下位ミップマップを「オンザフライ」で生成することにより、倍のページブレイクが除去されれば、バンド幅は容認可能なレベルにまで低減される。このシステムの、キャッシュされ圧縮されたテクスチャのバンド幅要件は、毎秒わずか２００メガバイトのオーダーである。１００メガヘルツで機能する６４ビットのメモリシステムのピークバンド幅容量は毎秒８００メガバイトなので、必要な毎秒２００メガバイトは十分許容範囲内にある。実際、本発明を実施している下位レベルのミップマップ構成システムは、予備のバンド幅を取っておくことができるので、それを他に利用することもできるであろう。
【００５５】
つまり、３Ｄイメージングシステムの一部として用いられるように設計されている図４のテクスチャリングシステムは、画像をテクスチャリングする際に用いるミップマップデータを記憶するためのメモリ２２を含んでおり、そのミップマップデータは、低下していく解像の異なるレベルの階層的に連続したミップマップを備えている。入力２６は、必要なミップマップデータのタイプと、データをそこから取り出すことになる１つ又は複数のミップマップのレベルを示す入力データを受け取る。コントローラ２４は、入力データに従って、必要なミップマップデータをメモリから検索するために、入力と、メモリとに接続されている。キャッシュ３０は、メモリから検索され、選択されたミップマップレベルに関連しているミップマップデータの部分を記憶するために、コントローラに接続されている。トリリニア補間器３４は、ミップマップの１つのレベル、即ちデータが必要とされている２つのレベルの内の上位のレベルからミップマップデータを受け取り、且つ、出力テクセルを２つのミップマップレベルからの入力テクセルから補間するために、キャッシュに接続されている。本発明によれば、テクスチャリングシステムは、キャッシュとトリリニア補間器との間に接続されている下位レベルのミップマップ生成器３６も含んでおり、部分がキャッシュに保持されているミップマップのすぐ下のミップマップの部分（一連の階層において）をリアルタイムで生成する。
【００５６】
図４に示されている本発明の実施例は、完全なトリリニア補間ピクセルを構築するために必要な全てのデータを呼び戻すため、１つのキャッシュ３０と１つの解凍ユニット（ＤＵ）３２が如何に求められているかを示している。しかし、フィルターのアルゴリズムが２つ又は４つの追加データワードからデータを必要とする場合には、問題がある。図６は、悪い状況のケースを示している。タイルに分割され、各タイルが１つの圧縮されたデータワードにより提供されるテクスチャピクセルを示しているようなテクスチャビットマップを考えてみよう。この例では、データワードは１６個のテクスチャピクセルを含んでいる。図６の太線枠のボックスは、タイルを表す。この例では、フィルターアルゴリズムには、４つの個別の圧縮されたデータワードからのテクスチャピクセルが必要である。１つのキャッシュ／解凍システムに対し、この最悪ケースの状況では、４つのキャッシュ読み取りと、それに伴って最小４クロックサイクルとが必要となる。別々の２つのデータワードが必要な場合、程度はよいが、なおこの問題は残る。
【００５７】
４つのキャッシュと４つのＤＵの構成だと、圧縮データがどこにあっても、１クロックサイクルで必要な全てのデータを提供するすることができる。図７は、そのような「４部式キャッシュ」装置を備えた本発明の第２実施例のブロック図である。図７のテクスチャリングシステムは、図４のシステムに似ているので、違いだけを詳細に説明する。図７の第２実施例では、メモリシステム２２と入力２６とは、図４のものと同じである。この場合、テクスチャアドレス生成器２８は、最大４つのタイルの出力が必要な状況に対処するために、４つの出力を有している。４つの出力はそれぞれにテクスチャアドレス１から４を提供し、これらは、参照番号６０で示されるテクスチャキャッシュ１から４に与えられる。これらのキャッシュは、４つのタイルそれぞれからテクセルを受け取ることができるように、アービタ５８を通してメモリコントローラー２４との間で交信する。これらのテクセルは４つのキャッシュ内に保持され、キャッシュは４つのキャッシュされた圧縮テクスチャ、即ちキャッシュされた圧縮テクスチャ１から４をそれぞれ出力する。
【００５８】
４つのキャッシュ６０の出力は、それぞれが図４の解凍ユニットと同様の４つの解凍ユニット６２に、それぞれ与えられる。各解凍ユニット６２は、その解凍されたデータを、上位及び下位のデコードユニット６８、７０と、更に下位レベルのミップマップフィルタ６６とに与える。上位及び下位のデコードユニット６８、７０の出力はそれぞれトリリニア補間器６４に与えられる。
【００５９】
作動時、各キャッシュ６０は、キャッシュワードのサイズと各キャッシュワードを表すテクスチャアドレスの下位の２つのビットとに基づいて、メモリの異なるセグメントに対して責任を負う。この方法では、１つのキャッシュが、完全なトリリニアピクセルに２つ以上のデータワードを提供するのに呼び出されることのないことが保証できる。
【００６０】
下位レベルのミップマップを上位のミップマップから生成できなければ、上位マップ用に４つと下位マップ用に４つという、８つのキャッシュ及びＤＵが必要となる。従って、下位レベルのミップマップを必要なときにオンザフライで生成できれば、性能を高めると同時に、ロジック（シリコン領域）を節約できる。圧縮と結び付けると、必要なデータ総量を大幅に減じることもできる。
【００６１】
但し、下位レベルのミップマップは、なおメモリ内に記憶されている。それらは、見る者から更に遠く離れているピクセルに必要である。しかし、トリリニア補間では、それらの存在を無視し、生成器６２を使って処理されているピクセルに必要なそれらのテクセルを再生成すると、より効率的であることがわかる。
【００６２】
下位レベルのミップマップを圧縮された上位レベルのミップマップから生成することの主要な利点の１つは、発生し得るロジック最適化の量である。ロジックが少ないほど、ハードウェアは小さくて済むし、コストは下がる。最適化のそのような領域の一つは、キャッシュと解凍ユニットである。
【００６３】
４部キャッシュシステムのキャッシュ６０は、効果的にメモリマップされ、即ち、先に述べたように、各キャッシュがテクスチャメモリの個々のタイルに関するデータを保持する。しかし、ＤＵ６２は、必ずしもメモリマップされる必要はない。ＤＵのメモリマッピングには、ＤＵそれぞれが特定のキャッシュと関連付けられる必要がある。このことは、更に、最良ケースの状況を提供するためには、１サイクルで、各ＤＵが少なくとも４つの下位レベルテクセル並びに４つの上位レベルテクセルを生成できることが必要となる。全てのタイルが１つのデータワードから来る最良ケースの状況が図８に示されている。
【００６４】
各ＤＵが、必要なリソースに基づいてダイナミックに再割当されるようにすることにより、幾つかのハードウェアの最適化が起こって、必要なハードウェアのサイズを劇的に小さくできる。２つ以上のユニットが４つの並行な上位レベルテクセルを提供する必要はなく、３つ以上のユニットが２つの並行な上位レベルテクセルを提供する必要はなく、どのユニットも２つ以上の下位レベルテクセルを提供する必要はないことがわかった。
【００６５】
図９は、これらの最適化が、修正された４部のキャッシュシステム内でどのように適合されているかを示している。図９の修正された装置は、図７の装置と類似しているので、違いのみを述べることとする。違うのは、４つのキャッシュ６０の出力と４つの解凍ユニット６２の入力との間に接続されている解凍ユニット（ＤＵ）アロケータ８２と、それに対応して、上位及び下位のデコードユニット６８、７０に入れ替わって、４つのＤＵ６２及びフィルタ６６両方の出力と、トリリニア補間器６４への入力との間に接続されているデアロケータ８４とが含まれているところである。各ＤＵ６２は同一のものではなく、第１ＤＵは４つの並列な上位レベルテクセルを提供することができるし、第２ＤＵは２つの並列な上位レベルテクセルを提供することができるし、第３及び第４ＤＵはそれぞれ唯１つの上位レベルテクセルを提供することができる。ＤＵ割り当てユニット８２は、テクスチャアドレスの構成に基づいて、どのＤＵ６２が必要とされているかを決定する。各ＤＵの登録された出力と、各ＤＵからのテクスチャ出力の多重化の両方で、ロジックの減少が起こる。ここでは、デアロケーションユニット８４が、上位及び下位デコードユニット６８、７０から引き継いで、ダイナミックに再割当られたリソースデータを、最初にテクセルを要求したデータパスへ返す。４つの下位レベルミップマップテクセルにフィルタを掛けるのに用いられる演算も簡素化されている。
【００６６】
出力が、デアロケータ８４によりデアロケート（割当解除）されたものとして示されているが、このことは、トリリニアフィルタ６４の出力が取り扱われる方式に依存して必ずしも必要なことではない。これは実施上の細目であり、当業者には自明であろう。
【００６７】
ロジック最適化のもう一つの領域は、下位レベルのミップマップを生成するフィルタ４０（図５）である。圧縮方式が、ＶＱ又はパレット化（上記参照）にあるような、コードブックを探索するためのインデックスを用いる様式であれば、この場合は下位ミップマップの生成が容易にできるような方法でテクスチャ構成要素を配列することができる。つまり、コードブックエントリが、そのカラー範囲に亘って解凍テクスチャを均等にサンプリングすることによって生成される場合、新しい下位レベルミップマップを生成するのに、インデックス自体を、ミップマップフィルタへの入力として用いることができる。その結果できるインデックスは、フィルタが掛けられたテクスチャと等価な最も近いコードブックを指すことになる。インデックス（圧縮されたテクスチャ）上でのフィルタリング演算のビット幅は、フィルタが解凍されたテクスチャに与えられた場合よりもかなり少ない。
【００６８】
そのような構成が図１０に示されている。これは、勿論図９の修正を含んでいるが、図７がベースになっている。
【００６９】
図１０は、フィルタ６６が解凍ユニット６２内にどのように現れているかを示している。各解凍ユニット６２は、アロケータ８２の出力に接続されているインデックス探索セクション９２を有しており、インデックスを提供し、そのインデックスにはフィルタ６６によりフィルタが掛けられ、その後、対応するコードブック部分を見つけるためにフィルタが掛けられたインデックスが用いられるコードブック探索セクション９４に与えられる。
【００７０】
図１１は、圧縮されたコード値とそれらが示すカラーとの間の関係を図で示している。図は、２次元平面上で可能な全てのカラーを示す色の三角形の一部であることを想定している。２つのカラーＣ１及びＣ２は基本カラーを意味する。それらは線の端を定め、その線上には他の中間色Ｃ１１からＣ１ｉまでがある。従って、これら他のカラーは、カラーＣ１及びＣ２の適切な重み付き平均を取ることにより形成することができる。カラーＣ１１からＣ１ｉに対するコード値も、カラーＣ１及びＣ２のコード値の平均を取ることにより、同様に定めることができる。
【００７１】
中間色を作り出す一般的な方法は、カラーＣ１及びＣ２の圧縮されたコード値を使って開始し、カラー当たり１６又は２４ビット必要なシステムの精度で、カラーＣ１及びＣ２の実際のカラー値を決めるものである。次に重み付け平均が１６又は２４のカラー値に実施され、決められる。しかし、カラーとそのコード値の関係が上に述べた方法で決められる場合、先ずコード値の平均を取り、次に平均コード値を変換し、最も近い使用可能なカラーを得ることができることが分かっている。このことは、平均を取る演算では、１６又はそれ以上のビットのデータが処理されるのではなく、利用する際に異なる圧縮されたコード値を決めるのに必要なわずか２又は３程度のビットが処理可能であればよいということになる。
【００７２】
この下位のミップマップ最適化技法を、ＤｉｒｅｃｔＸ圧縮テクスチャ（参考文献１４）に適用することもできる。ここでは、２つの基本カラーと、インデックスにより示された補間された中間値とが、均等に離れて配置されている。図１２は、２ビットのインデックスがどのように１６ビットのテクスチャカラーにマップされるかを示している。１６ビット値に替えて、２ビットのインデックス自体にフィルタを掛けることができることがわかる。このことは、ロジックが少なく、従って全体のコストが低いことを示している。
【００７３】
要約すれば、画像をテクスチャリングする際に用いるためのテクスチャデータを生成する図示方法は、先ず、任意の圧縮されたコードによりテクスチャデータを表示する段階を備えており、選択された圧縮コード値は両基本カラーを定め、他の圧縮されたコード値は、基本カラーの選択された重み付け平均値により形成することのできるカラーを定め、この対応するコード値は、選択された基本カラーのコード値の重み付け平均値でもある。次に、出力テクセルが複数の入力テクセルから補間されるが、補間段階は、圧縮コード値を使って行われる。コード値は続いて解凍され、実際のカラー値が与えられる。
【００７４】
この方法は、図示されている下位レベルのミップマップ生成器内での利用以外にも、他の目的で利用することもできる。圧縮されたコードが実際のカラーに対応する線形関係を有するならば、圧縮された形態で保持されている中間色を生成する必要がある場合には何時でも、本方法を用いることができる。特に、メモリ２２内に保持されているミップマップの最初の生成時に用いることができる。
【００７５】
以上、説明、図示してきた本発明の実施例は、既知のシステムに様々な改良点を提供する。特に、テクスチャ圧縮キャッシュを使う場合、トリリニアフィルタリングに対しメモリバンド幅を効果的に利用することができる。必要に応じて、圧縮された上位レベルのミップマップデータから下位レベルのミップマップデータを生成することにより、ページブレイクを越えるアクセスが低減する。４部キャッシュ配列を用いると、クロック周期当たり１つのトリリニアフィルタが掛けられたピクセルが保証される。解凍ロジックの演算は、ダイナミック解凍リソース割当を用いることにより改善される。最後に、下位レベルのミップマップ生成と解凍ロジックを統合すると、システムのオーバーヘッドが比較的低くなる。
【００７６】
以上、現在好適な実施例を取り上げ、本発明を説明し図示してきたが、これらのシステムには多くの修正を加え得ることが、理解頂けるであろう。
【図面の簡単な説明】
【図１】  イメージングシステム内のテクスチャマップのバイリニアフィルタリングを示す図である。
【図２】  図１と同様の、イメージングシステム内のテクスチャマップのトリリニアフィルタリングを示す図である。
【図３】  一連のミップマップを示している。
【図４】  本発明によるイメージングシステムの一部分を示す概略ブロック図である。
【図５】  図４の実施例のオペレーションを示す図である。
【図６】  最悪ケースシナリオにおけるテクスチャワードの記憶状態を示す図である。
【図７】  図４と同様な、４つのキャッシュと４つの解凍ユニットを並行に用いている本発明の第２実施例の概略ブロック図である。
【図８】  最良ケースシナリオにおけるテクスチャワードの記憶状態を、図６と同様の方法で示す図である。
【図９】  図７の実施例を修正したブロック図であり、ここでは解凍ユニットはダイナミックに再割り当てされる。
【図１０】  図７のもう１つの、回路を修正したブロック図である。
【図１１】  圧縮されたテクスチャコードに、補間をどのように直接適用できるかを示す図である。
【図１２】  圧縮されたテクスチャコードに、補間をどのように直接適用できるかを示す図である。
【図１】
0004410940.tif 000002
【図２】
0004410940.tif 000003
【図３】
0004410940.tif 000004
【図４】
0004410940.tif 000005
【図５】
0004410940.tif 000006
【図６】
0004410940.tif 000007
【図７】
0004410940.tif 000008
【図８】
0004410940.tif 000009
【図９】
0004410940.tif 000010
【図１０】
0004410940.tif 000011
【図１１】
0004410940.tif 000012
【図１２】
0004410940.tif 000013