(57)【特許請求の範囲】
【請求項１】
三次元図形データに応じて画像をレンダリングするレンダリング装置であって、
（ａ）前記レンダリング装置が前記三次元図形データを受け取ることができる経路であって、前記三次元図形データが、ポリゴン・データとさらにテクスチャを定義するテクスチャ・データを含み、前記テクスチャ・データがテクスチャ・サイズ・データおよび組になったパターン・データを含み、各組の前記パターン・データがテクスチャを異なる解像度で表わし、前記テクスチャ・データは、前記パターン・データから構成され、
（ｂ）レンダリング・スクリーンの画素に対応する第１のメモリ・セルを含む画素・深さバッファと、
（ｃ）前記レンダリング・スクリーンの画素に対応する第２のメモリ・セルを含む参照バッファと、
（ｄ）前記ポリゴン・データと前記テクスチャ・サイズ・データだけを使用して初期ラスタ化操作を実行して、前記レンダリング・スクリーンの各画素にテクスチャ識別子、テクスチャ解像度を示し、整数部分と少数部分とを含む実数の層深さ値およびテクスチャ座標を生成し参照バッファ内に記憶し、テクスチャ識別子、レンダリング・スクリーン画素ごとに参照バッファに記憶された層深さおよびテクスチャ座標に応じて、前記画像をレンダリングするために必要なパターン・データを識別し、前記画像をレンダリングするのに必要であると識別された前記パターン・データを、前記経路を介して獲得し、前記バッファとの間のデータ転送速度よりも低いデータ転送速度を有する経路を介して獲得した前記パターン・データを使って前記画像を表す画像データを生成するレンダリング・エンジンと
を含むレンダリング装置であって、
前記レンダリング・エンジンは、
前記層深さ値の少数部分が０のとき、前記層深さ値の整数部分によって示された１つの組の前記パターン・データ間の第１の層内補間を実行して、前記画像データを引き出すテクスチャ色値を生成し、
前記層深さ値の少数部分が０以外のとき、前記第１の層内補間と、前記１つの組よりも高いレベルの解像度を有する別の組のパターン・データ間の第２の層内補間と、前記第１層内補間と前記第２の層内補間によって生成された結果の間の層間補間を実行して、前記画像データを引き出す前記テクスチャ色値を生成する
ことを特徴とするレンダリング装置。
【請求項２】
前記パターン・データを、ピラミッド形データ構造で記憶するテクスチャ・メモリ
をさらに含み、
前記ピラミッド形データ構造は、
前記テクスチャを異なる解像度で表す前記パターン・データの各組に、記憶する層
を含み、
前記パターン・データの組のうちの１組は前記テクスチャを最も高い解像度で表わすこと
を特徴とする請求項１に記載のレンダリング装置。
【請求項３】
前記レンダリング・エンジンは、初期ラスタ化操作を、さらに実行することによって、前記レンダリング・スクリーンのそれぞれの画素の輝度係数を生成し、
前記輝度係数は、前記参照バッファの前記第２のメモリ・セルのうちの１つに、さらに記憶され、
前記第２のメモリ・セルのうちの１つは、前記レンダリング・スクリーンの前記画素の１つに対応すること
を特徴とする請求項２に記載のレンダリング装置。
【請求項４】
前記パターン・データは、
方形タイルに配列されたテクスチャ画素
に属し、
前記装置は、
前記テクスチャのタイル・ロード・リスト
をさらに含み、
前記タイル・ロード・リストは、
各前記タイルごとのエントリ
を含み、
前記レンダリング・エンジンは、
前記画像をレンダリングするために必要な前記パターン・データを識別したときに、前記参照バッファからテクスチャ座標を読み取って、前記画像をレンダリングするために必要なパターン・データがある前記タイルの一つを識別し、前記タイルの一つに関する前記タイル・ロード・リスト内のエントリを、前記画像をレンダリングするために、前記タイルの一つのパターン・データが必要であることを示すロード状態に設定すること
を特徴とする請求項２に記載のレンダリング装置。
【請求項５】
前記レンダリング・エンジンは、
前記画像をレンダリングするのに必要な前記パターン・データを獲得するときに、
前記テクスチャの前記タイル・ロード・リストを検査して、ロード状態に設定された前記エントリを識別し、
前記タイル・ロード・リスト内のエントリが、ロード状態に設定されていると識別された各前記タイルの前記パターン・データを獲得し、
前記パターン・データを獲得した各前記タイルのタイル・ロード・リスト内のエントリを、ロード状態から存在状態に変更し、
存在状態が、前記タイルの一つの前記パターン・データが獲得されたことを示すこと
を特徴とする請求項４に記載のレンダリング装置。
【請求項６】
前記パターン・データは、
方形タイルに配列されたテクスチャ画素
に属し、
さらに、前記レンダリング装置は、
前記テクスチャのタイル・ロード・リスト
を含み、
前記タイル・ロード・リストは、
各前記タイルの１つの前記パターン・データを獲得したことを示すエントリ
を含み、
前記レンダリング・エンジンは、
前記ピラミッド形データ構造における１つの前記層に１つの前記タイルの前記パターン・データを獲得するとき、前記タイル・ロード・リストを検査して、前記層の１つの直下の層にあるタイルであって、前記タイルの一つのパターン・データを合成することができるソース・タイルの１つのパターン・データが獲得されているかどうかを判定し、
前記ソース・タイルの前記パターン・データから、前記タイルの一つの前記パターン・データを合成すること
を特徴とする請求項２に記載のレンダリング装置。
【請求項７】
前記パターン・データは、
方形タイルに配列されたテクスチャ画素
に属し、
前記レンダリング・エンジンは、
前記ピラミッド形データ構造の最上層を構成するタイルの一つの前記パターン・データを、前記経路を介してロードすることによって前記画像をレンダリングするために必要な前記パターン・データの初期部分を獲得し、
前記タイルの一つを、前記ピラミッド形データ構造で記憶し、
前記ピラミッド形データ構造に現存する前記パターン・データから、前記画像データを生成し、
より高い解像度で前記画像をレンダリングするためにパターン・データを必要とする前記ピラミッド形データ構造の前記タイルを識別し、
前記識別したタイルのパターン・データを獲得し、
前記画像データをより高い解像度で再生する
ことを特徴とする請求項２に記載のレンダリング装置。
【請求項８】
前記レンダリング・エンジンは、前記画像をより高い解像度でレンダリングするために、パターン・データを必要とする前記タイルを識別し、前記識別したタイルの前記パターン・データを獲得し、前記画像をより高い解像度で再生するルーチンを、最低解像度の前記レンダリング・スクリーンの画素から、最高解像度の前記レンダリング・スクリーンへの順番に、１つの前記レンダリング・スクリーンの画素それぞれに対して、最良解像度の画像データが得られるまで、順次、繰り返して実行すること
を特徴とする請求項７に記載のレンダリング装置。
【請求項９】
前記レンダリング・エンジンは、
（ｅ）前記経路を介した前記パターン・データのローディングと、
（ｆ）前記パターン・データの合成のいずれか一方によって、前記画像をレンダリングするために必要な前記パターン・データ
を獲得すること
を特徴とする請求項１に記載のレンダリング装置。
【請求項１０】
三次元図形データに応じて画像を、コンピュータによりレンダリングする方法であって、前記画像がレンダリング・スクリーンの画素に対応する画像データによって表わされ、前記三次元図形データが、ポリゴン・データとさらにテクスチャを定義するテクスチャ・データとを含み、前記テクスチャ・データが、テクスチャ・サイズ・データおよび組になったパターン・データとを含み、前記各組のパターン・データが前記テクスチャを異なる解像度で表し、前記テクスチャ・データは、前記パターン・データから構成され、
（ａ）前記ポリゴン・データと、前記テクスチャ・サイズ・データとを受け取る段階と、
（ｂ）前記レンダリング・スクリーン前記画素ごとに、前記ポリゴン・データと、前記テクスチャ・サイズ・データとを使って、テクスチャ識別子、テクスチャ解像度を示す層深さ値およびテクスチャ座標を生成して記憶する初期ラスタ化操作を実行する段階と、
（ｃ）前記レンダリング・スクリーン画素ごとに記憶した前記テクスチャ識別子、前記層深さおよび前記テクスチャ座標に応じて、前記画像をレンダリングするために必要な前記パターン・データを識別するパターン・データ識別操作を実行する段階と、
（ｄ）パターン・データ識別操作によって、前記画像をレンダリングするために必要であると識別されたパターン・データを獲得するパターン・データ獲得操作を実行する段階と、
（ｅ）前記パターン・データ獲得操作によって獲得された前記パターン・データを使用して、前記画像を表す前記画像データを生成する最終ラスタ化操作を実行する段階と、
（ｆ）初期ラスタ化操作を実行する段階は、整数部分と少数部分を有する実数として層深さ値を生成し、
（ｇ）最終ラスタ化操作を実行する段階は、さらに、
（ｇ−１）前記層深さ値の少数部分が０のときに、前記層深さ値の整数部分によって識別された１つの組のパターン・データ間の第１の層内補間を実行して、テクスチャ色値から画像データを導き出す段階と、
（ｇ−２）層深さ値の少数部分が０でないときに、前記第１の層内補間を実行して、前記組よりも高いレベルの解像度を有する別の組のパターン・データ間の第２の層内補間操作を実行し、前記第１層内補間と前記第２の層内補間操作によって生成された結果の間で層間補間を実行して、テクスチャ色値から前記画像データを導き出すこと
を前記コンピュータに実行させること
を特徴とする画像レンダリング方法。
【請求項１１】
（ｈ）テクスチャ・メモリを提供する段階と、
（ｉ）テクスチャ・メモリに、前記パターン・データ獲得操作によって獲得されたパターン・データをピラミッド形データ構造で記憶する段階と
を含み、
前記ピラミッド形データ構造は、
前記テクスチャを異なる解像度で表す前記パターン・データの組がそれぞれ記憶された層
を含み、
前記パターン・データの組のうちの１組が前記テクスチャを最も高い解像度で表すこと
を特徴とする請求項１０に記載の画像レンダリング方法。
【請求項１２】
（ｂ）前記初期ラスタ化操作は、
前記レンダリング・スクリーン画素の１つの画素の輝度係数を生成し、
前記輝度係数は、前記レンダリング・スクリーン前記画素のうちの１つの画素の前記テクスチャ識別子、前記層深さ値および前記テクスチャ座標とともに記憶されること
を特徴とする請求項１１に記載の画像レンダリング方法。
【請求項１３】
前記パターン・データは、方形タイルに配列されたテクスチャ画素に属し、
前記方法は、
（ｊ）前記テクスチャのタイル・ロード・リストを提供する段階を含み、前記タイル・ロード・リストは各タイルのエントリ
をさらに含み、
（ｃ）前記データ・パターン識別操作は、
テクスチャ座標を読み取って、前記画像をレンダリングするのに必要なパターン・データがある前記タイルの一つを識別する段階と、
前記タイルの一つのタイル・ロード・リスト内のエントリを、前記タイルの一つの前記パターン・データが前記画像をレンダリングするために必要とすることを示すロード状態に設定する段階と
を含む
ことを特徴とする請求項１１に記載の画像レンダリング方法。
【請求項１４】
（ｄ）前記パターン・データ獲得操作は、
前記テクスチャの前記タイル・ロード・リストを検査して、ロード状態に設定されたエントリを識別する段階と、
前記タイル・ロード・リスト内のエントリがロード状態に設定されていると識別された前記各タイルの前記パターン・データを獲得する段階と、
前記パターン・データを獲得した前記各タイルの前記タイル・ロード・リスト内のエントリを、ロード状態から、前記各タイルの前記パターン・データを獲得したことを示す存在状態に変更する段階と
を含むことを特徴とする請求項１３に記載の画像レンダリング方法。
【請求項１５】
前記パターン・データは、方形タイルに配列されたテクスチャ画素に属し、
前記方法は、
（ｎ）前記テクスチャのタイル・ロード・リストを提供する段階を含み、前記タイル・ロード・リストは各前記タイルのエントリ
を含み、
前記エントリは、
前記タイルの１つの前記パターン・データが前記ピラミッド形データ構造で存在することを示す状態
を有し、
（ｄ）前記パターン・データ獲得操作は、
前記ピラミッド形データ構造の１層にある１つのタイルの前記パターン・データを獲得するために実行され、前記タイル・ロード・リストを検査して、前記層の直下にある層にあるソース・タイルの前記パターン・データが前記ピラミッド形データ構造に存在し、前記ソース・タイルが、前記タイルの一つの前記パターン・データを合成することができるタイルであるかどうかを判定する段階と、
前記ソース・タイルの前記パターン・データが前記ピラミッド形データ構造に存在するときに、前記ソース・タイルの前記パターン・データから前記タイルの一つの前記パターン・データを合成する段階と
を含むこと
を特徴とする請求項１１に記載の画像レンダリング方法。
【請求項１６】
前記パターン・データは、
方形タイルに配列されたテクスチャ画素
に属し、
前記ピラミッド形データ構造の最上層を構成する前記タイルの一つのパターン・データを受け取って、前記ピラミッド形データ構造に記憶し、前記パターン・データ識別動作を実行する前に、前記ピラミッド形データ構造に現存する前記パターン・データから前記画像データを生成する最終ラスタ化操作を実行し、
（ｃ）前記パターン・データ識別操作は、より高い解像度で前記画像をレンダリングするために前記パターン・データが必要な前記ピラミッド形データ構造のタイルを識別し、
前記方法は、前記パターン・データ獲得操作の後で、前記最終ラスタ化操作をさらに繰り返して、前記画像データをさらに高い解像度で再生する段階
を含むこと
を特徴とする請求項１１に記載の画像レンダリング方法。
【請求項１７】
（ｂ）前記最終ラスタ化操作、（ｃ）前記パターン・データ識別操作および（ｄ）前記パターン・データ獲得操作を、最低解像度の前記レンダリング・スクリーンの画素から、最高解像度の前記レンダリング・スクリーンへの順番に、１つの前記レンダリング・スクリーンの画素それぞれに対して、最良解像度の画像データが得られるまで、順次、繰り返して実行すること
を特徴とする請求項１６に記載の画像レンダリング方法。
【請求項１８】
（ｄ）前記パターン・データ獲得操作は、
パターン・データのロード、または
パターン・データの合成のうちの１つによって、前記画像をレンダリングするのに必要な前記パターン・データを獲得する段階
を前記コンピュータに実行させること
を特徴とする請求項１０に記載の画像レンダリング方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、三次元図形データに応じて画像をレンダリングする方法および装置に関し、特に、データ転送速度が制限されたネットワークなどの環境において三次元図形データに応じて画像をレンダリングする方法および装置に関する。
【０００２】
【従来の技術】
パーソナル・コンピュータと、テレビ・ゲームなどの図形処理装置の処理能力の向上により、三次元コンピュータ・グラフィックス（三次元画像）が次第に普及してきている。三次元画像を含むコンテンツを送るために、インターネットが次第に利用されるようになっている。家庭用パーソナル・コンピュータ（ＰＣ）のユーザは、インターネットから三次元図形データをダウンロードし、ブラウザを利用してコンテンツをレンダリングし、表示し、対話することができる。
【０００３】
三次元画像のレンダリング技術は、長期間にわたって開発されてきた。最新の技術は、家庭用ＰＣで使用されているグラフィックス・アダプタに差し込むことができる拡張ハードウェアで実施されてきた。ＰＣとグラフィックス・ハードウェアの性能を高めることにより、複雑な画像をレンダリングすることができる。しかしながら、三次元図形データのソースがデータ転送速度の制限されたネットワークであるときは、画像データによって表わされる画像が複雑だと三次元図形データのダウンロードに長い時間がかかる。インターネットは、このようなネットワークの一例である。ネットワークに接続されたクライアント・コンピュータ上で動作する既知のブラウザ・プログラムは、サーバから三次元図形データを実質上すべてダウンロードしてからでないと、三次元図形データに応じた画像を表示するのに必要な図形レンダリング計算を実行し始めることができない。その結果、ユーザは、画像が表示し始めるまでにローディング時間の大部分を待たなければならない。従来の三次元図形レンダリングプログラムの処理構造では、そのようなプログラムが画像を表示し始めるまでに長い遅延が生じていた。
【０００４】
三次元画像では、１つまたは複数の三次元オブジェクトが占める三次元空間が定義される。また、三次元空間内の各オブジェクトの基準点の位置も定義される。各オブジェクトの形は、オブジェクトの表面を覆う１組のポリゴンで定義される。たとえば、立方体は、それぞれ立方体の面の１つと一致する６つの正方形ポリゴン（正方形）で定義することができる。それぞれのポリゴンに関して、サイズ、形および座標が定義される。さらに、色と反射率を定義することもできる。しかしながら、オブジェクトの表面のすべてまたは一部分がパターン化されている場合は、面を表すポリゴンを多数の副ポリゴンに分割して、それらの副ポリゴンに異なる色と反射率を割り当てることによってパターンを表すことができるようにしなければならない。これにより、オブジェクトを表わすのに必要なデータの量が事実上増える。
【０００５】
したがって、オブジェクトの面を基本パターニング以上にレンダリングする場合は、面の外観をテクスチャを利用して定義することが好ましい。テクスチャは、基本ビットマップから複雑な画像まで任意の複雑さのパターンを表す１組のデータである。この１組のデータは、たとえばパターンを定義する画像マップ・データを含む。外観がテクスチャによって定義されたオブジェクトの面の一部分を表すポリゴンは、テクスチャを使ってタイル表示される。テクスチャを使用すると、複雑な面の外観を持つオブジェクトを、多数のポリゴンを使って面を表現するのに必要なデータよりも少ないデータで表現することができる。
【０００６】
三次元オブジェクトが占める三次元空間が、コンピュータ・モニタ画面などの二次元画面上の画像として表示されるときは、まず、視点が、ユーザによって選択されるかまたは画像データによって定義される。また、１つまたは複数の光源を定義したり選択したりすることができる。視点と三次元空間の間にあるレンダリング・スクリーンと呼ばれる仮想平面も定義される。レンダリング・スクリーンは、画像を表示するために使用される画素数に対応することが好ましい配列の画素（ピクセル）に分割される。たとえば、画像をＮＴＳＣ方式のＴＶまたはＶＧＡコンピュータ表示装置の画面に表示させる場合は、レンダリング・スクリーンを６４０×４８０の画素に分割することが好ましい。次に、レンダリングプログラムは、レンダリング・スクリーンを構成する各画素の色値を計算する。各画素の色値は、通常、赤色値、緑色値および青色値を含む。一方、輝度や色差などの様々な色値が使用されることがある。次に、画素の色値に応じて画像が表示される。これは、たとえば、色値を三次元画像拡張ハードウェアからコンピュータのグラフィックス・アダプタのビデオ・メモリに転送することによって行うことができる。
【０００７】
いわゆるにＺバッファを使用する従来の三次元図形レンダリングプログラムは、次のように動作することができる。
１．ローディング段階：ネットワークを介したサーバまたはローカル・ファイルから１組の完全な画像データがロードされる。
２．幾何学的段階：ポリゴンのレンダリング・スクリーンへの投影を計算する。これらの計算の結果は、視点から見たそれぞれのポリゴンの各頂点の深さを示す深さ値を含む。
３．ラスタ化段階：陰付き面や隠れ面の削除操作を実行する。投影するポリゴンをレンダリング・スクリーンの画素に対応するオブジェクト画素に変換し、それぞれのオブジェクト画素に関して１組の色値を計算するラスタ化操作を実行する。オブジェクトが三次元なので、レンダリング・スクリーンの所与の画素上に複数のポリゴンが投影されることがある。その結果、ポリゴンがレンダリング・スクリーン上で重なる場合には、複数のオブジェクト画素の色値と深さ値が生成される。色値と深さ値は、レンダリング・スクリーンの画素に対応する記憶位置を有する画素および深さバッファに記憶される。この位置決めプロセスにおいて、所与のレンダリング・スクリーンの画素に複数のオブジェクト画素が生成されるときは、オブジェク画素のどれが目に見えるかを決定するために深さ値が比較される。最も小さな深さ値に対応する色値と深さ値だけ、すなわち目に見えるオブジェクト画素の色値と深さ値だけが、画素バッファおよび深さバッファに記憶される。この操作により、隠れ面（すなわち、視点から見ることができない面）が有効に除去される。
４．表示段階：幾何学段階とラスタ化段階ですべてのポリゴンを処理した後、表示のために画素バッファの内容が出力される。
【０００８】
ラスタ化段階では、シェーディング操作により、それぞれのオブジェクト画素の色値が計算される。また、このステップでは、それぞれの画素の１組の輝度係数を計算し、画素のオリジナル色値にそれぞれの輝度係数を掛けて画素の色値を得る。１組の輝度係数は、通常、赤、緑および青の輝度係数も含む。輝度係数は、照明の作用を定義し、オブジェクト画素があるオブジェクト画素のポリゴンの材料特性と、各光源の色と位置と方向、および視点の位置と方向に依存する。輝度係数を計算するためには、既に様々な方法がある。ポリゴンのオリジナル色は、ポリゴンの特性を定義する図形データの一部である。ポリゴンのオリジナル色は、ダイレクト色や、前述のようなテクスチャとして定義することができる。ダイレクト色を使用するときは、ダイレクト色自体がオリジナル色として使用される。ポリゴン上にテクスチャをマッピングするとき、テクスチャを表わすパターン・データからポリゴンの各オブジェクト画素のオリジナル色が計算される。
【０００９】
各オブジェクト画素のオリジナル色を定義するテクスチャのパターン・データは、次のように決定される。
１．レンダリング・スクリーンのそれぞれの画素座標（Ｘ、Ｙ）について、関連するテクスチャ座標（ｓ、ｔ）を計算する。
２．画素の色は、テクスチャ座標（ｓ、ｔ）上かまたはその近くにある１つまたは複数のテクスチャ画素のパターン・データからアクセスまたは補間される。
【００１０】
最も簡単な実施例では、各オブジェクト画素の色値として、テクスチャの１組のパターン・データが適用される。この場合も、各組のパターン・データは、通常、赤、緑および青のパターン・データを含む。しかしながら、この単純なテクスチャ・サンプリング方法は、しばしば、望ましくないブロック・パターンやモワレ・パターンを生成する。テクスチャを表わす複数のパターン・データの間の補間によって１組の単一色値を計算するためには、一般に、テクスチャ・フィルタリング技術が利用される。たとえば、いわゆるMultum in Parvo（ＭＩＰ）マップは、テクスチャ画像をマルチ解像度ピラミッド形データ形式で記憶する。各オブジェクト画素の色を定義する１組の色値は、２段階の補間を利用して生成される。最初の補間操作は、同じレベルのパターン・データの間の２つのレベル上で、いわゆる層内補間が実行される。同じレベルのパターン・データ間の隣り合った２つのレベルのそれぞれについて、２つの層内補間操作が実行される。次に、２の層内補間操作の結果の間で、層間補間操作が実行される。プロセス全体は、トリリニア補間（tri-linear interpolation）と呼ばれる。
【００１１】
従来の三次元図形レンダリングプログラムは、ローディング段階ですべてのテクスチャデータを受け取らなければならない。しかしながら、すべてのテクスチャが、最終的にレンダリングされる画像になるわけではない。後面にあって切り取られたポリゴン上のテクスチャは、ラスタ化段階で処理されず、邪魔されたポリゴンに適用されるテクスチャから得られたオブジェクト画素は、隠れ面除去操作において破棄されるため、最終画像では存在しない。また、単一の高い解像度のビットマップとしてテクスチャを提供する従来の技術は、レンダリング時間を長くする。これは、テクスチャをマッピングするポリゴンが、視点から遠くにあるかまたは視点に対して斜めの角度にあるときは、高解像度テクスチャを生成するのに必要なビットマップ・データの多くは余分になることがあるためである。このような場合は、もっと低い解像度のテクスチャで十分である。従来の三次元図形レンダリングプログラムを使用して、従来のローディング段階でテクスチャをロードする前に画像をレンダリングするのに必要なテクスチャとテクスチャ解像度を決定することは、このとき幾何学形状がまだ計算されていないため不可能である。その結果、従来の三次元図形レンダリングプログラムは、ロード段階の間に、すべてのテクスチャをその最も高い解像度でロードすることを必要とする。
【００１２】
ポリゴンの数は、通常、テクスチャのサイズよりもレンダリング時間に及ぼす影響が大きい。したがって、アプリケーションは、一般に、ポリゴンの数を少なくしテクスチャの使用を増やすことによって、現実的でかつ自然な三次元画像を提供するのに必要な計算能力を減少させようとしている。しかしながら、これを行うとき、特にネットワーク環境では、大量のテクスチャ・データによりローディング時間が長くなる。
【００１３】
【発明が解決しようとする課題】
本発明は、三次元図形データに応じて画像をレンダリングするレンダリング装置を提供する。
【００１４】
【課題を解決するための手段】
このレンダリング装置は、レンダリング装置が三次元図形データを受け取ることができる入力経路と、画素・深さバッファと、参照バッファと、レンダリング・エンジンとを含む。三次元図形データは、ポリゴン・データと、さらにテクスチャを定義するテクスチャ・データとを含む。テクスチャ・データは、テクスチャ・サイズ・データと、組になったパターン・データを含む。各組のパターン・データは、テクスチャを異なる解像度で表わす。パターン・データは、テクスチャ・データの大部分を構成する。画素・深さバッファと参照バッファは、レンダリング・スクリーンの画素に対応する第１のメモリ・セルと第２のメモリ・セルをそれぞれ含む。レンダリング・エンジンは、ポリゴンとテクスチャ・サイズ・データだけを使用して初期ラスタ化操作を実行し、レンダリング・スクリーンのそれぞれの画素のためのテクスチャ識別子、テクスチャ解像度を示す層深さ値、およびテクスチャ座標を生成し、参照バッファに記憶する。レンダリング・エンジンは、また、レンダリング・スクリーンのそれぞれの画素ごとに参照バッファに記憶されたテクスチャ識別子、層深さ値およびテクスチャ座標に応じて、画像をレンダリングするのに必要なパターン・データを識別する。レンダリング・エンジンは、画像をレンダリングするのに必要と識別されたパターン・データを経路を介して獲得する。最終的に、レンダリング・エンジンは、経路を介して獲得したパターン・データを使用して、画像を表わす画像データを生成する。経路は、レンダリング・エンジンとバッファの間のデータ転送速度よりも実質上低いデータ転送速度を有する。
【００１５】
レンダリング装置は、さらに、パターン・データをピラミッド形データ構造で記憶するテクスチャ・メモリを含むことがある。ピラミッド形データ構造は、テクスチャを異なる解像度で表わすパターン・データの組をそれぞれ記憶する層を含む。パターン・データの組のうちの１つの組は、テクスチャを最も高い解像度で表わす。
【００１６】
画像をレンダリングするのに必要なパターン・データは、経路からパターン・データをロードするか、あるいはより高い解像度でテクスチャを表わす１組のパターン・データのパターン・データからパターン・データを合成することによって得ることができる。
【００１７】
層深さ値は、整数部分と少数部分を有する実数でもよい。層深さ値の少数部分が０のとき、レンダリング・エンジンは、層深さ値の整数部分によって示されるパターン・データの組のうちの１組のパターン・データ間の第１の層内補間を実行して、画像データを導き出すテクスチャ色値を生成する。一方、層深さ値の少数部分が０でないとき、レンダリング・エンジンは、第１の層内補間と、複数の組のうちの１組よりも高いレベルの解像度を有する別の組のパターン・データ間の第２の層内補間と、第１と第２の層内補間によって生成された結果の間の層間補間とを実行して、画像データを導き出すテクスチャ色値を生成する。
【００１８】
本発明は、また、三次元図形データに応じて画像をレンダリングする方法を提供する。画像は、レンダリング・スクリーンの画素に対応する画像データによって表わされる。三次元図形データは、ポリゴン・データを含み、さらにテクスチャを定義するテクスチャ・データを含む。テクスチャ・データは、テクスチャ・サイズ・データと、組になったパターン・データを含む。各組のパターン・データは、異なる解像度でテクスチャを表わす。パターン・データは、テクスチャ・データの大部分を構成する。この方法において、ポリゴン・データとテクスチャ・サイズ・データが受け取られる。レンダリング・スクリーンの画素のそれぞれについて、初期ラスタ化操作を実行する。初期ラスタ化操作は、ポリゴン・データとテクスチャ・サイズ・データを使用して実行され、テクスチャ識別子、テクスチャ解像度を示す層深さ値およびテクスチャ座標を生成し記憶する。パターン・データ識別操作は、レンダリング・スクリーン画素のそれぞれに関して記憶されたテクスチャ識別子、層深さ値およびテクスチャ座標に応じて実行される。パターン・データ識別操作は、画像をレンダリングするのに必要なパターン・データを識別する。次に、パターン・データ獲得操作を実行する。この操作により、パターン・データ識別操作によって画像をレンダリングするのに必要と認識されたパターン・データが獲得される。次に、最終ラスタ化操作を実行する。ここで、パターン・データ獲得操作によって獲得したパターン・データを使用して、画像を表わす画像データが生成される。
【００１９】
本発明は、三次元図形データに応じて画像を生成するための新しい処理装置とレンダリング方法を提供することによってスクリーン上に画像が表示されるまで待たなければならない時間を大幅に短縮する。本発明によるレンダリング装置および方法において、テクスチャを表わすパターン・データは、初期ラスタ化操作が完了するまで得られない。パターン・データは、ローディングによって、あるいはピラミッド形データ構造においてより高い解像度の層のパターン・データから合成することによって得られる。パターン・データを獲得する前に初期ラスタ化操作を実行することは、画像をレンダリングするために、画像を必要な解像度でレンダリングするのに必要なテクスチャの一部分を定義するパターン・データを獲得するだけでよいことを意味する。この方法において、サーバからロードしたり合成したりしなければならないパターン・データ数が少なくなり、それにより待機時間も減少する。
【００２０】
本発明によるレンダリング装置は、パターン・データなしに実行される初期のレンダリング操作によって生成される中間結果を保持する参照バッファを含む。これにより、パターン・データの獲得とテクスチャ画素の色値の補間を延期することができる。参照バッファの内容を使用することによって、必要なパターン・データだけがロードされるので、本発明によりパターン・データを効率的に得ることができる。本発明は、また、後で説明するような「最良解像度」と「漸進的解像度」の２つの代替表示方法を提供する。
【００２１】
【発明の実施例】
本発明は、インターネットなどのネットワークのようにデータ転送速度が制限された環境で使用するように意図された画像レンダリング装置とその方法に関する。図１は、本発明によるレンダリング装置１００のブロック図である。このレンダリング装置は、たとえば、コンピュータ１０２の中にある。実際の実施例において、レンダリング装置は、コンピュータ内にあるグラフィックス・カード（図示せず）の一部を形成することがある。あるいは、レンダリング装置は、コンピュータに差し込まれるか、あるいはコンピュータのグラフィックス・カードに接続されたハードウェア・アクセサリである。
【００２２】
コンピュータ１０２は、入出力ポート１０４を介して、ネットワーク１０６のクライアントとして接続される。入出力ポートは、レンダリング装置とコンピュータの他の要素が接続されたバス１０８に直接または間接に接続される。ネットワーク、入出力ポートおよびバスは、レンダリング装置が１つまたは複数のテクスチャを定義するテクスチャ・データを含む三次元図形データを受け取る経路を構成する。
【００２３】
また、図示したように、バス１０８には、レンダリング装置１００によって生成されたレンダリング・スクリーンの画素の最終色値を表示用にモニタ１５０に送るビデオ出力ポート１１６が接続される。
【００２４】
また、ネットワーク１０６には、三次元図形データを集合的に記憶するメモリ１１２および１１４を含むサーバ１１０も接続される。メモリ１１２は、三次元図形のオブジェクトの面の位置を定義するポリゴン・データを記憶する。メモリ１１４は、１つまたは複数の面に適用されるテクスチャを定義するテクスチャ・データを記憶する。テクスチャの外観を定義するパターン・データは、テクスチャ・データの大部分を構成する。また、テクスチャ・データは、テクスチャの高さや幅などのデータを含む。
【００２５】
さらに追加または代替として、三次元図形データを、コンピュータ１０２に記憶することもできる。この場合、メモリ１１２および１１４と同等な記憶部が、コンピュータ内にあってバス１０８に直接または間接に接続されたハード・ディスクなどのメモリ（図示せず）内に配置される。たとえば、サーバ１１０からロードされた三次元画像を、コンピュータのハード・ディスクに記憶することができる。この場合、ハードディスクとバスは、レンダリング装置が１つまたは複数のテクスチャを定義するテクスチャ・データを含む三次元図形データを受け取る経路を構成する。
【００２６】
レンダリング装置１００において、レンダリング・エンジン１２０は、バス１０８に接続される。レンダリング・エンジンは、レンダリングプログラム１２２を実行し、三次元図形データに応じてレンダリング操作を行う。レンダリング操作により、二次元画像を指定する１組の画素データが生成される。レンダリング・エンジンは、本発明による方法を実行する。レンダリング・エンジンは、マイクロプロセッサ、デジタル信号プロセッサ、１つまたは複数の特定用途向け集積回路または汎用集積回路を使って構成することができ、本明細書に記載した処理の実行を可能にする読取り専用メモリやランダム・アクセス・メモリなどの他の要素を含んでもよい。
【００２７】
レンダリング装置１００は、さらに、画素・深さバッファ１２４と参照バッファ１２６を含む。画素・深さバッファと参照バッファは、直接またはバス１０８を介してあるいは他の何らかの装置によってレンダリング・エンジン１２０に接続される。レンダリング・エンジンとバッファの間のデータ転送速度は、三次元図形データを、経路を介して、すなわちネットワーク１０６またはコンピュータのハード・ドライブから受け取る転送速度よりも実質上大きい。
【００２８】
画素・深さバッファ１２４と参照バッファ１２６はそれぞれ、マルチバイト記憶セルからそれぞれ構成されることが好ましい。それぞれのセルは、レンダリング・スクリーンの１つの画素に対応することが好ましい。レンダリング・エンジン１２０によってそれぞれのレンダリング操作が実行される間、画素・深さバッファは、最初に深さバッファとして機能し、次に画素バッファとして機能する。通常、従来のレンダリング装置も、深さバッファと画素バッファを含むが、従来の装置は、隠れ面除去操作を実行するときに同時にバッファを使用するため、単一のバッファを両方の機能に使用することはできない。本発明によるレンダリング装置では、深さバッファと画素バッファを同時に使用する必要がないため、両方のバッファの機能を、物理メモリの単一部分で実行することができる。本発明によるレンダリング装置１００は、参照バッファ１２６を使用して、以下で詳細に説明するように、テクスチャ計算によって生成された中間結果を記憶する。
【００２９】
レンダリング装置１００は、また、バス１０８に接続されたテクスチャ・データ・メモリ１３０を含む。テクスチャ・データ・メモリは、複数のページに分割され、その例を１３２に示す。１つのテクスチャのテクスチャ・データは、それぞれのページに記憶される。テクスチャ・データ・メモリの各ページは、テクスチャを表わすテクスチャ・データのサブセットを記憶するセクションに分割される。図１に示した例において、ページ１３２は、最大層深さメモリ１３３、ピラミッド形パターン・データ記憶機構１３４、タイル・ロード・リスト１３６、タイル・ピッチ・アレイ１３８、およびタイル・ベース・アレイ１４０を含む。
【００３０】
テクスチャを表わすパターン・データは、後で詳細に説明するマルチ解像度ピラミッド形データ構造で、ピラミッド形パターン・データ記憶機構１３４に記憶される。タイル・ロード・リスト１３６は、後で説明するように、テクスチャが分割された各タイルごとのエントリを含む。このエントリは、タイルのパターン・データの獲得状況、すなわちタイルのパターン・データを獲得したかどうか、あるいはそのようなパターン・データを獲得する必要があるかどうかを示す。タイル・ピッチ・アレイ１３８とタイル・ベース・アレイ１４０はそれぞれ、ピラミッド形データ構造の各層ごとのエントリを含む。タイル・ピッチ・アレイ内のエントリは、層のそれぞれの列のタイルの数を示す。タイル・ベース・アレイ内のエントリは、層の左上のタイルのタイル番号を示す。タイル・ベース・アレイは、タイルの総数を記憶する追加のエントリを含むこともある。テクスチャ・メモリの各ページに記憶されたテクスチャ・データについては、後で詳細に説明する。
【００３１】
図２は、各テクスチャを表わすパターン・データを記憶するマルチ解像度ピラミッド形データ構造２００の構造を示す。マルチ解像度ピラミッド形データ構造は、商標ＦｌａｓｈＰｉｘで販売されている従来の二次元図形システムに基づく。この二次元図形システムは、マルチ解像度ピラミッド形データ構造を使用して、写真などの二次元画像を表わすデータを記憶する。本発明によるレンダリング装置および方法では、各テクスチャのパターン・データは、テクスチャをそれぞれ異なる解像度で表わす組になったパターン・データが、いくつかの層に配列されたピラミッド形データ構造で記憶される。これらの層は、上の層から下の層に大きくなるように番号が付けられ、一番上の層が０である。ピラミッド形構造における層の位置は、層の層深さによって表される。最も低い解像度のパターン・データが記憶された最上層は、０の層深さを持つ。図２に示した例で、最高解像度のパターン・データが記憶された層の層深さは４である。しかしながら、ピラミッド形データ構造は、この例で示した数よりも多いかまたは少ない数の層を含むこともできる。
【００３２】
ピラミッド形データ構造２００の各層のパターン・データは、テクスチャを、その下の層のパターン・データがテクスチャを表わす解像度の２分の１の解像度で表し、その上の層のパターン・データがテクスチャを表わす解像度の２倍で表わす。
【００３３】
最も高い解像度でテクスチャを表わすパターン・データは、ピラミッド形データ構造２００の最も下の層２０２を構成する。通常は、最高解像度は、テクスチャのオリジナルの解像度と同じである。しかしながら、オリジナルの解像度がその用途に必要な最大の解像度よりも高い場合は、最高解像度は、オリジナルの解像度よりも小さいことがある。最下層における隣接した４つの画素のパターン・データが結合されて、最下層のすぐ上の層２０３において１画素のパターン・データを生成する。その結果、層２０３のパターン・データは、それぞれの方向に最下層パターン・データの２分の１の直線解像度でテクスチャを表す。層２０３のパターン・データの数は、最下層２０２のパターン・データの数の４分の１である。前述の結合プロセスは、すぐ下の層のパターン・データから残りの層２０４〜２０６の各層のパターン・データを生成するために実行される。
【００３４】
ピラミッド形データ構造２００の最上層２０６では、テクスチャは、横方向にａ個の画素と縦方向にｂ個の画素のアレイのパターン・データによって表される。好ましい実施例では、ａ＝ｂ＝６４である。ピラミッド形データ構造２００は、ＭＩＰデータ構造などの従来のピラミッド形データ構造と異なることに注意されたい。ピラミッド形データ構造２００では、最上層に１つのタイルのパターン・データが記憶される。従来のピラミッド形データ構造では、最上層に１つの画素のパターン・データが記憶される。
【００３５】
最上層２０６よりも下のピラミッド形データ構造２００の各層は、それぞれａ×ｂの画素のアレイからなるタイルに分割することができる。そのタイルの例を２１０で示す。タイルは、パターン・データを獲得する単位である。前述のように、パターン・データは、サーバ１１０からタイル単位でロードされ、追加または代替としてクライアント・コンピュータ１０２内にあるメモリ（図示せず）から転送されることもある。ピラミッド形データ構造２００の各層は、４D個のタイルに分割され、ここで、Ｄは層の層深さであり、最上層２０６が０の層深さである。
【００３６】
各層のパターン・データは、通常、テクスチャを表わす画像マップを構成する。しかしながら、たとえば、パターン・データがネットワーク１０６を介してレンダリング装置に転送されるとき、画像マップ・データは送信時間を短縮するために圧縮されることがある。たとえば、画像マップ・データを圧縮して送信用のパターン・データを生成するためにＪＰＥＧ圧縮を使用することができる。しかしながら、圧縮されたパターン・データは、ピラミッド形データ構造で記憶される前にビットマップ形式に拡張される。
【００３７】
パターン・データは、ピラミッド形データ構造２００の層２０２〜２０６のそれぞれに記憶される。層２０２〜２０６はそれぞれ、整数、すなわち０、１、２、．．．、ｎの層深さＤを有する。しかしながら、後でより詳細に説明するように、レンダリング・エンジン１２０が、所与のオブジェクト画素に適用するテクスチャの最適解像度を計算するとき、この計算で生成される層深さは実数であり、すなわち、層深さは、整数部分の他に少数部分を持つことができる。そのような層深さは、ピラミッド形データ構造の物理層と一致しない。この場合、レンダリング・エンジン１２０は、非整数の層深さを持つ層のパターン・データを計算する。そのようなパターン・データは、層深さＤの整数部分と等しい整数の層深さＤLを持つ層に記憶されたパターン・データと、ＤG＝ＤL＋１の整数の層深さを持つ層に記憶されたパターン・データとの間の補間によって計算される。たとえば、レンダリング・エンジンは、２と３の層深さを持つ層のパターン・データ間の補間によって２．３の層深さを持つ層のパターン・データを計算する。
【００３８】
前述のように、参照バッファ１２６は、レンダリング・スクリーンの各画素ごとに実行された初期ラスタ化操作の結果を記憶する。この結果は、後で最終ラスタ化操作を実行するときに使用される。参照バッファは、ランダム・アクセス・メモリなどのメモリの一部分で実施することができる。メモリは、レンダリング・スクリーンの画素の１つにそれぞれ対応するセルに区分される。図３Ａと図３Ｂは、初期ラスタ化操作の結果を記憶するために、参照バッファ１２６のセルに使用される２つの代替データ構造の例を示す。セルに記憶される初期ラスタ化操作の結果は、ダイレクト色データでもテクスチャ・データでもよい。セルに記憶されたデータのタイプは、セルの第１のフィールド３０１に記憶されたビットの状態で示される。図３Ａは、初期ラスタ化操作によってダイレクト色データが生成されたときのセルのデータ構造の例を示す。図３Ｂは、初期ラスタ化操作がテクスチャ座標と輝度係数を生成するときのセルのデータ構造の例を示す。
【００３９】
初期ラスタ化操作において、レンダリング・スクリーンの画素が、テクスチャを適用しないポリゴン内にあるオブジェクト画素から得られるときは、前述のように、レンダリング・スクリーン画素の最終色値は、ポリゴンのダイレクト色にその輝度係数を掛けることによって得られる。この場合、初期ラスタ化操作がダイレクト色データを生成したことを示すために、第１のフィールド３０１に０が記憶される。掛算によって得た最終色値は、通常、赤色値、緑色値および青色値から構成される。赤色値、緑色値および青色値は、図３Ａに示したデータ構造を使用して、画素のセルのフィールド３０３のＲ、ＧおよびＢセクションにそれぞれ記憶される。セル３００に割り振られたメモリの残りの部分３０６は、テクスチャを適用するポリゴン内にあるオブジェクト画素からレンダリング・スクリーン画素を得るときに同じサイズのセルを使用することができるように予約され、データ構造は、図３Ｂに示したものである。
【００４０】
レンダリング・スクリーンの画素が、テクスチャを適用するポリゴン内にあるオブジェクト画素から得られるとき、図３Ｂに示したように、セル３００の第１のフィールド３０１に１が記憶される。セルの残りのフィールドに記憶されるデータは、次の通りである。すなわち、フィールド３１０は、画素に適用するテクスチャのテクスチャ・データを記憶した図１に示したテクスチャ・メモリ１３０のページを示すポインタまたはインデックスを記憶する。フィールド３１２は、図２に示したピラミッド形データ構造の一番下（最高解像度）の層２０２の画素に関して表されたテクスチャ座標（Ｓ，Ｔ）を記憶する。テクスチャ座標は、次のように、オブジェクト画素の座標（Ｘ、Ｙ）にポリゴンの投影マトリックスとテクスチャ・マッピング・マトリックスまたは関数（ｓ，ｔ）を適用することによって計算される。
Ｓ＝ｓ（Ｘ，Ｙ）
Ｔ＝ｔ（Ｘ，Ｙ）
【００４１】
フィールド３１４は、レンダリング・スクリーンの画素の最終色値を計算する際に使用するパターン・データを得る図２に示したピラミッド・データ構造の層を定義する層深さＤを記憶する。層深さＤは、次の方程式を使用して計算される。
【００４２】
【数１】
0004448210.tif 000002
ここで、Ｄmaxは、図２に示したピラミッド形データ構造２００の最下層２０２の層深さである。
【００４３】
最後に、フィールド３１６には画素の輝度係数が記憶される。この例では、フィールドのセクションＩＲ、ＩＢおよびＩＢにそれぞれ赤、緑および青の輝度係数が記憶される。
【００４４】
従来の三次元図形のレンダリングにおいて、テクスチャ座標（Ｓ，Ｔ）と層深さＤは、実数で計算される。そのすぐ後で、計算したパラメータを使って、層内補間と層間補間が行われ、レンダリング・スクリーンの各画素ごとの最終色値が生成される。しかしながら、本発明によるレンダリング装置とその方法において、初期ラスタ化操作の間に、テクスチャ座標（Ｓ，Ｔ）と層深さＤが計算される。初期ラスタ化操作は、パターン・データがまだロードされる前に実行される。最終ラスタ化操作の間に最終色値を計算するときに使用するために、初期ラスタ化操作の結果が参照バッファに記憶される。これは、必要なパターン・データが得られた後だけ実行される。
【００４５】
次に、図１、図２、図３、図４Ａおよび図４Ｂを参照して、本発明による方法と本発明によるレンダリング装置の操作について説明する。最初に、テクスチャ・データの少しの部分だけがサーバからロードされることに注意されたい。ほとんどのテクスチャ・データを構成するパターン・データの獲得は、初期ラスタ化操作が完了するまで延期される。次の説明では、三次元図形データがサーバ１１０に記憶され、ネットワーク１０６を介してロードされる例を参照する。三次元図形データがコンピュータ１０２に記憶されるとき、類似した操作が行われる。
【００４６】
最初に、図４Ａに示したフローチャートを参照して、レンダリング装置の方法と操作の概要を説明する。以下の説明を簡単にするために、テクスチャを適用するレンダリング・スクリーンの画素に適用される処理だけを説明する。処理は、ステップ４００から始まる。以下に、図４Ａの各ステップを示す。
ステップ４００：スタート
ステップ４０２：最初のローディング操作を実行する
ステップ４０４：幾何学計算を実行する
ステップ４０６：初期ラスタ化操作を実行する
ステップ４０８：パターン・データを獲得しなければならないピラミッド形データ構造のタイルを識別する。
ステップ４１０：第２回目のローディング操作を実行する
（ステップ４０８で識別されたタイルのパターン・データだけを獲得する）
ステップ４１２：レンダリング・スクリーンの各画素に関するテクスチャ色値が計算される
ステップ４１４：テクスチャ色値に輝度係数を乗じる
ステップ４１６：画素の最終色値に変換する
【００４７】
ステップ４０２において、最初のローディング操作が実行される。この場合、ポリゴン・データと各テクスチャの幅と高さの値がサーバからロードされる。各テクスチャの幅と高さの値は、テクスチャのテクスチャ・データの少しの部分でしかない。さらに、ポリゴン・データの数は比較的少ない。したがって、このステップの実行は短時間でできる。
【００４８】
ステップ４０４において、幾何学計算が実行される。
【００４９】
ステップ４０６において、初期ラスタ化操作が実行される。初期ラスタ化操作は、テクスチャのパターン・データなしに実行されるという点で従来のラスタ化操作とは異なる。初期ラスタ化操作は、画素・深さバッファ１２４を深さバッファとして使用する隠れ面除去操作を含む。隠れ面除去操作により、レンダリング・スクリーンの各画素に適用されるテクスチャが識別される。参照バッファ１２６内の画素のセルには、識別されたテクスチャのテクスチャ・データが記憶されるテクスチャ・メモリ１３０のページを示すポインタが記憶される。また、この段階では、レンダリング・スクリーンの各画素ごとに、隠れ面除去操作によって識別されたテクスチャの層深さＤとテクスチャ座標（Ｓ，Ｔ）、およびレンダリング・スクリーン画素の輝度係数が計算される。層深さ、テクスチャ座標および輝度係数は、参照バッファ内の画素セルにも記憶される。
【００５０】
ステップ４０８において、参照バッファ１２６に記憶されたテクスチャ座標と層深さを使って、画像をレンダリングするためにパターン・データを獲得しなければならないピラミッド形データ構造のタイルを識別する。
【００５１】
ステップ４１０で、第２のローディング操作が実行される。ここでは、ステップ４０８で識別されたタイルのパターン・データだけを獲得する。パターン・データは、サーバからそのデータをロードし、あるいはすぐ下の層すなわち次に高い解像度の層のパターン・データからのデータを合成することによって得られる。通常は、層を構成するタイルの一部だけのパターン・データを獲得する。さらに、より高い解像度の層の必須パターン・データを獲得すれば次に低い解像度の層のパターン・データを合成することができるので、ローディングによってパターン・データを獲得する低い解像度層のタイル部分は、ローディングによってパターン・データを獲得する高い解像度層のタイル部分よりも小さくてもよい。一般に、すべてのパターン・データよりも少ないデータしかロードしないため、このステップは、従来のローディング段階よりも高速に実行される。
【００５２】
ステップ４１２および４１４において、最終ラスタ化操作が実行される。ステップ４１２において、ステップ４１０で獲得したテクスチャ・タイルのパターン・データの補間によって、レンダリング・スクリーンの各画素に関する１組のテクスチャ色値が計算される。
【００５３】
ステップ４１２において、各画素ごとのテクスチャ色値に参照バッファ１２６から読み込まれた画素の輝度係数を掛けて画素に関して得た最終色値が、画素・深さバッファ１２４に記憶される。初期ラスタ化操作の間に、輝度係数が計算される。
【００５４】
ステップ４１４において、レンダリング・スクリーンの画素の最終色値が、モニタ１５０上に表示するのに適した信号に変換される。
【００５５】
ステップ４１６において、実行プログラムは終了する。
【００５６】
次に、図１、図２、図３および図４Ｂを参照して、本発明によるレンダリング装置の方法と操作をさらに詳細に説明する。ステップ４５０で、実行プログラムが始まる。
【００５７】
ステップ４５１および４５２において、最初のローディング操作が実行される。ここでは、パターン・データはロードされない。
【００５８】
ステップ４５１において、サーバ１１０内のメモリ１１２からポリゴンメッシュ・データがロードされる。ポリゴンメッシュ・データは、ポリゴンの面に適用されるテクスチャを指定するデータを含む。
【００５９】
ステップ４５２において、ポリゴンメッシュ・データによって指定された各テクスチャの幅と高さの値が、サーバ１１０のメモリ１１４からロードされる。テクスチャの幅と高さの値は、前述のテクスチャ・データの少しの部分にしかならない。このとき、テクスチャ・データの大部分を構成するパターン・データは、ロードされない。また、このステップにおいて、ポリゴンメッシュ・データによって指定された各テクスチャごとの幅と高さの値に応答して、テクスチャ初期化操作が実行される。この初期化操作において、幅と高さの値は、パターン・データを最終的に獲得したときに図２に示したマルチ解像度ピラミッド形データ構造がテクスチャのパターン・データを記憶するために使用する層数（Ｄmax＋１）を計算するために使用される。また、ピラミッド形データ構造のそれぞれの層の列内のタイル数と、各層の左上のタイルのタイル番号が計算されるかまたはルックアップ・テーブルから読み取られる。
【００６０】
Ｄmaxの値は、テクスチャ・メモリ１３０のテクスチャのページ１３２の１３３に記憶される。また、初期化操作により、前述の層の計算で得られた結果とテクスチャの高さと幅の値を利用して、テクスチャ・メモリのテクスチャのページに、各テクスチャごとのピラミッド形データ構造１３４、タイル・ロード・リスト１３６、タイル・ピッチ・アレイ１３８およびタイル・ベース・アレイ１４０が設定される。
【００６１】
タイル・ロード・リスト１３６は、ピラミッド形データ構造１３４内の各タイルごとのエントリを含む。このエントリは、タイルの獲得状況を表わす２ビット・コードを記憶する。タイルのローディング状況は、この開示において、文字Ｎ、ＬおよびＥによって表された３つの状態を有する。実際のレンダリング装置でのローディング状況は、前述の２ビット・コードによって表わされる。テクスチャ初期化操作により、各タイルへのエントリが、タイル用のパターン・データがテクスチャ用のピラミッド形データ構造内にないことを示す「Ｎ」に設定される。その後、パターン・データを獲得しなければならないタイルを識別する操作により、そのようなタイルのタイル・ローディング・リスト内のエントリが「Ｌ」に設定され、これは、前述の第２のローディング操作でそのタイルのパターン・データを獲得しなければならないことを示す。第２のローディング操作によって、パターン・データを獲得しピラミッド形データ構造で記憶してあるタイルのローディング・リストのエントリが「Ｅ」に設定され、これは、タイルのパターン・データがピラミッド形データ構造内にあり、画像のレンダリングに使用することができることを示す。
【００６２】
タイル・ピッチ・アレイ１３８とタイル・ベース・アレイ１４０はそれぞれ、ピラミッド形データ構造１３４の各層のエントリを含む。タイル・ピッチ・アレイ１３８のエントリは、層のタイル・ピッチを記憶する。タイル・ピッチは、層の列内のタイルの数である。タイル・ベース・アレイ１４０内のエントリは、層のタイル・ベースを記憶する。タイル・ベースは、層の左最上部のタイル番号である。
【００６３】
画素の寸法が、たとえば５１２×５１２画素などの２の累乗の正方形に配列されたテクスチャ画素のパターン・データによってテクスチャが定義されるとき、最上（最も低い解像度）の層２０６から始まるピラミッド形データ構造２００の層のタイル・ピッチの値は、１、４、１６、．．．４Dであり、ここで、Ｄは、層の層深さであり、最上層の層深さは０である。これと対応するタイル・ベースの値は、次の通りである。
【００６４】
【数２】
0004448210.tif 000003
ここでｋは、インデックス。
【００６５】
テクスチャが、寸法が２の累乗ではないアレイに配列されたテクスチャ画素のパターン・データによって定義されるとき、タイル・ピッチとタイル・ベースを生成するためにはさらに複雑な計算が必要になる。そのような計算は、必要に応じて、ステップ４５２で実行される。ステップ４５２が終了したとき、テクスチャのパターン・データは、まだ獲得されていないことに注意されたい。
【００６６】
ステップ４５３において、従来の幾何学段階の操作が実行される。ここでは、レンダリング・スクリーンへのポリゴンの投影が計算される。
【００６７】
ステップ４５４において、初期ラスタ化操作が実行される。ここでは、ステップ４５３で計算されたレンダリング・スクリーンへのポリゴンの投影が、オブジェクト画素に変換され、隠れ面除去に使用するために、それぞれのオブジェクト画素に関して深さの計算が行われる。深さの計算は、オブジェクト画素の深さ値を登録するために画素・深さバッファ１２４を使用することが好ましい。別法として、画素バッファと別の深さバッファを使用することもできる。オブジェクト画素が重なるときは、深さ値の最も小さなオブジェクト画素だけがバッファに登録され、それにより、隠れ面除去が実行される。
【００６８】
深さの計算により、レンダリング・スクリーンの各画素に対応するオブジェクト画素が定義される。テクスチャを適用するポリゴン内にあるオブジェクト画素に対応するレンダリング・スクリーンの画素について、参照バッファ１２６内の画素のセル３００のフィールド３０１が１に設定され、テクスチャ用のテクスチャ・データを記憶するテクスチャ・メモリ１３０のページのアドレスが、セルのフィールド３１０に入力される。色をダイレクト色計算で決定するポリゴン内にあるオブジェクト画素に対応するレンダリング・スクリーンの画素の場合は、参照バッファ１２６内の画素のセル３００のフィールド３０１が０に設定される。
【００６９】
参照バッファ１２６内のレンダリング・スクリーンの画素のセル３００のフィールド３０１に０で示されたように、テクスチャを適用しないポリゴン内にある各オブジェクト画素に対応するレンダリング・スクリーンの画素の場合は、従来のシェーディング計算が実行される。シェーディング計算は、画素に関する１組の色値を生成する。１組の色値における赤色値、緑色値および青色値が、参照バッファ内の画素のセルのフィールド３０２のＲ、ＧおよびＢのセクションにそれぞれ記憶される。
【００７０】
参照バッファ１２６内のレンダリング・スクリーン画素のセル３００のフィールド３０１の１で示したように、テクスチャを適用するポリゴン内にある各オブジェクト画素に対応するレンダリング・スクリーン画素の場合は、部分的なシェーディング計算が実行される。部分的なシェーディング計算により、その画素のテクスチャ座標（Ｓ，Ｔ）、層深さＤおよび輝度係数の値が生成される。テクスチャ座標は、フィールド３１２に記憶され、層深さはフィールド３１４に記憶され、赤、緑および青の輝度係数は、参照バッファ内の画素のセルのフィールド３１６のセクションＩＲ、ＩＧおよびＩＢにそれぞれ記憶される。
【００７１】
本発明は、２つの表示モード、すなわち最良解像度表示モードと漸進的解像度表示モードを提供する。最良解像度表示モードは、パターン・データの全ローディング時間を最小にする。漸進的解像度表示モードは、画像を最良解像度表示モードよりも迅速に表示する。しかしながら、漸進的解像度表示モードでは、テクスチャは、最初に低解像度で表示され、その後、各テクスチャが最適解像度で表示されるまで少しずつ高い解像度で表示される。表示モードは、ユーザ（図示せず）が選択することもできるし、三次元図形プログラムで定義することもできる。
【００７２】
ステップ４５５において、最良解像度表示モードが選択されたかどうかを判定するために検査が行われる。検査結果がＹＥＳの場合は、実行プログラムはステップ４６１に進み、最良解像度表示モードの処理が始まる。検査結果がＮＯの場合は、実行プログラムがステップ４７１に進み、漸進的解像度表示モードの処理が始まる。次に、最良解像度表示モードの処理について説明し、後で漸進的解像度表示モードの処理について説明する。
【００７３】
ステップ４６１において、図５Ａと図５Ｂを参照して詳細に説明するルーチンが、参照バッファ１２６内の画素のセル３００のフィールド３０１に１つを有するレンダリング・スクリーンの各画素に関して実行される。このフィールド内の１は、テクスチャを適用するポリゴン内にレンダリング・スクリーン画素に対応するオブジェクト画素があることを示す。このルーチンは、各テクスチャに関して、画像をレンダリングできるようにするために第２のローディング動作で獲得しなければならないパターン・データのテクスチャのピラミッド形データ構造１３４のタイルを識別する。ステップ４６１の実行が完了すると、獲得しなければならないパターン・データの各テクスチャのピラミッド形データ構造のすべてのタイルが識別され、テクスチャのタイル・ロード・リスト１３６内のこれらのタイルへのエントリが、すべて「Ｌ」に設定される。
【００７４】
ステップ４６２において、ページ１３２がテクスチャ・メモリ１３０内にある各テクスチャに関して、図６を参照して後で詳細に説明するルーチンを実行することによって、第２のローディング操作が実行される。このルーチンは、テクスチャ・データ・メモリ１３０のテクスチャのページ１３２に記憶されたタイル・ロード・リスト１３６を走査し、タイル・ロード・リストのエントリが「Ｌ」に設定されたタイルのパターン・データを獲得する。前述のように、各タイルごとのパターン・データは、ローディング、あるいは高い解像度のパターン・データ、すなわちピラミッド形データ構造のすぐ下の層からの合成によって獲得することができる。ステップ４６２の実行が終了したとき、画像をレンダリングするために必要なパターン・データはすべて、テクスチャ・メモリの各ページにピラミッド形データ構造で記憶され、対応するタイル・ロード・リスト内のこれらのタイルのエントリは、すべて「Ｅ」に設定される。
【００７５】
ステップ４６２が完了したとき、タイル・ロード・リスト内のほとんどの数のエントリが「Ｎ」に設定されたままでもよいことに注意されたい。そのようなエントリは、そのようなパターン・データが画像をレンダリングするためには必要でないために、対応するタイルのパターン・データを獲得しなかったことを示す。これにより、ステップ４６２を従来のロード段階よりも迅速に実行することができる。
【００７６】
ステップ４６３において、最終的なレンダリング操作が、参照バッファ１２６の画素のセル３００のフィールド３０１内に１があるレンダリング・スクリーンの各画素に関して、図７Ａを参照して後で詳細に説明するルーチンを実行することによって行われる。このルーチンは、ステップ４５４で最初に実行された部分的なシェーディング操作を完了するためにトリリニア補間を実行する。この補間により、ステップ４６２で獲得したパターン・データからの画素に関する１組のテクスチャ色値が計算される。トリリニア補間は、ピラミッド形データ構造の２つの層にあるパターン・データを使って行われる。２つの層は、参照バッファ１２６の画素のセル３００のフィールド３１４に記憶された実数の層深さを計算するのに使用される。次に、ルーチンは、ステップ４５４で参照バッファのレンダリング・スクリーン画素のセルのフィールド３１６に記憶されたそれぞれの輝度係数をテクスチャ色値に掛けて、画素に関する最終色値を生成する。最終色値は、画素バッファの画素の位置に記憶される。好ましい実施例において、画素・深さバッファ１２４は、画素バッファとして使用される。あるいは、深さバッファと無関係の画素バッファを使用することもできる。
【００７７】
ステップ４６４において、参照バッファ１２６内の画素のセル３００のフィールド３０１に０を有するレンダリング・スクリーンの各画素に関して、参照バッファの画素のセルのフィールド３０２に記憶された最終色値が、画素バッファ内の画素の位置に複写される。
【００７８】
最後に、ステップ４６５において、画素バッファ１２４に記憶された最終色値が、モニタ１５０に直接または間接に出力される。モニタは、画素バッファからの受け取った最終色値に応じてレンダリング画像を表示する。
【００７９】
次に、実行プログラムは、ステップ４８１に進み、ユーザ（図示せず）が入力値を入力したかどうかを判定するために検査を行う。たとえば、ユーザ入力は、視点を変更する入力値の入力である。これにより、新しいレンダリング操作を実行することが必要になる。検査結果がＮＯの場合、実行プログラムは、ステップ４８１に戻る。検査結果がＹＥＳの場合、実行プログラムはステップ４８２に進み、そこでユーザ入力によって影響を受けたパラメータが変更される。次に、実行プログラムは、ステップ４５３に戻り、新しいレンダリング操作が実行される。新しいレンダリング操作中に、パターン・データをまだ獲得していなかったタイルのパターン・データを獲得しなければならない場合があるが、通常は、先ほど説明したレンダリング操作で獲得したパターン・データの多くを再利用することができる。
【００８０】
次に、図４Ｂを参照して、漸進的解像度表示モードで実行される処理について説明する。ステップ４７１において、ステップ４５１でロードしたポリゴン・データによって指定された全テクスチャの最上タイルのパターン・データが、サーバ１１０からロードされる。各テクスチャの最上タイルのパターン・データは、テクスチャ・メモリ１３０のテクスチャのページ１３２においてピラミッド形データ構造１３４の適切な場所に記憶される。最も上のタイルのパターン・データは、最も低い解像度を有するそれぞれのテクスチャを表わす。次に、プログラムは、高い解像度タイルのパターン・データを獲得したときに、画像を最初に低い解像度のテクスチャを表示し、次に徐々に高い解像度のテクスチャを表示する解像度改善ループを実行する。解像度改善ループは、ステップ４７２〜４７７で構成される。
【００８１】
ステップ４７２において、図７Ｂを参照して後で詳細に説明するルーチンが、参照バッファ１２６のレンダリングのセル３００のフィールド３０１に１を有するレンダリング・スクリーンの各画素ごとに実行される。このルーチンは、バイリニア補間（bi-linear interpolation）とトリリニア補間を利用して、テクスチャのテクスチャ色値を生成する。テクスチャ色値には、参照バッファ１２６に記憶された輝度係数が掛けられ、レンダリング・スクリーン画素に関して得られた最終色値は、画素・深さバッファ１２４に記憶される。画素・深さバッファは、この操作において、画素バッファとして使用される。あるいは、深さバッファと別の画素バッファを使用することもできる。
【００８２】
ループの繰り返しにおいて、計算するテクスチャ色値のほとんどは、最適な解像度よりも小さい暫定的な値である。しかしながら、初期の繰り返しにより、最適な解像度を有するいくつかのテクスチャ色値を計算することができる。繰り返し回数が増えるにつれて、テクスチャ色値を最適の解像度で計算するレンダリング・スクリーン画素の数は増える。テクスチャ色値の解像度が高くになるつれて、画像にテクスチャを表示する解像度はさらに高くなる。
【００８３】
また、図７Ｂを参照して後で説明する処理によって、いくつかのタイルのタイル・ロード・リスト・エントリが「Ｌ」に設定される。そのようなエントリは、後のルーチンでステップ４７７を実行したときにパターン・データを獲得しなければならないタイルを示す。これらのパターン・データを獲得すると、ループの次の繰り返しでステップ４７２を実行するときに生成されるテクスチャ色値の解像度が高くなる。
【００８４】
ステップ４７３において、画素の参照バッファ・セル３００のフィールド３０１に０を有するレンダリング・スクリーンの各画素に関して、画素の参照バッファ・セルのフィールド３０２に記憶された最終色値が、画素バッファ１２４内の画素の場所に複写される。
【００８５】
ステップ４７４において、画素バッファ１２４に記憶されたレンダリング・スクリーンの画素に関する最終色値が、モニタ１５０に直接または間接に出力される。モニタは、最終色値に応じて画像を表示する。次に、実行プログラムは、ステップ４７５を介してステップ４７６に進む。ステップ４７５については、後で説明する。
【００８６】
ステップ４７６において、ステップ４７２を実行したときにタイル・ロード・リスト内のエントリが「Ｌ」に設定されているかどうかを判定するために、テクスチャ・メモリ１３０のページ１３２に記憶されたタイル・ロード・リスト１３６の検査が実行される。結果がＮＯの場合は、最良解像度で画像をレンダリングするのに必要なすべてのパターン・データが獲得されたことを示し、前述のように、処理はステップ４８１に進む。結果がＹＥＳの場合、実行プログラムは、ステップ４７７に進む。
【００８７】
ステップ４７７において、テクスチャ・メモリ１３０にページ１３２があるそれぞれのテクスチャに関して、図６を参照して後で詳細に説明するルーチンを実行することによって、第２のローディング操作が行われる。このルーチンは、テクスチャ・データ・メモリ１３０のテクスチャのページ１３２に記憶されたタイル・ロード・リスト１３６を走査し、タイル・ロード・リストのエントリが「Ｌ」に設定されたタイルのパターン・データを獲得する。前述のように、各タイルごとのパターン・データは、ロードするか、あるいは次に高い解像度の層すなわちピラミッド形データ構造におけるすぐ下にある層のパターン・データから合成することによって獲得することができる。ステップ４７７の実行が完了すると、パターン・データを獲得したタイルのタイル・ロード・リスト内のエントリが「Ｅ」に設定される。次に、実行プログラムは、ステップ４７２に戻る。
【００８８】
ステップ４７７が実行されるごとに、以前に獲得したパターン・データよりも高い解像度を有するパターン・データが獲得される。これにより、次にステップ４７２を実行したときに、よりきめ細やかでかつ高い解像度の画像の最終色値を生成することができる。ステップ４７２〜４７７からなるループは、最良解像度表示モードで提供されるのと同じ画像を生成するのに必要なタイルのパターン・データを獲得するまで繰り返される。そのような画像を提供するタイルのパターン・データの獲得が終わると、ステップ４７６で実行される検査の結果はＮＯとなる。
【００８９】
ステップ４７２〜４７７からなるループは、パターン・データ獲得ステップ４７７を含み、そのため、特に高い解像度パターン・データをロードするときに、実行に長い時間がかかることがある。したがって、ステップ４７５が、ループに含まれる。このステップにより、ユーザは、解像度改善ループを中断して、新しいパラメータを入力することができる。新しいパラメータは、たとえば視点の変更である。ステップ４７５において、ユーザ入力を受け取ったかどうかを判定するために検査が行われる。結果がＮＯの場合は、ユーザ入力を受け取っていないことを示し、実行プログラムは、解像度改善ループの次のステップであるステップ４７６に進む。結果がＹＥＳの場合は、解像度改善ループは実行を止め、実行プログラムはステップ４８２に進み、新しいユーザ・パラメータを受け取る。次に、実行プログラムはステップ４５３に戻り、新しいユーザ入力に応答してレンダリングプロセスが繰り返される。
【００９０】
図５Ａは、画像を最良解像度表示モードでレンダリングできるようにするためにパターン・データを獲得しなけばならないピラミッド形データ構造２００のタイルを識別するためにステップ４６１で実行されるルーチンの詳細を示す。図５Ａに示したルーチンは、レンダリング・スクリーンの各画素に関して実行されるが、最初に、画素の参照バッファ・セル３００のフィールド３０１の内容を検査する。フィールドが０を含む場合は、ステップ４５４で画素の最終色値が計算され、残りのルーチンが実行されないことを示す。したがって、実際には、このルーチンは、テクスチャを適用するポリゴン内にあるオブジェクト画素から得た画素上でのみ完全に実行される。
【００９１】
実行プログラムは、ステップ５００で始まる。ステップ５０２において、画素の参照バッファ・セル３００のフィールド３０１に１が記憶されているかどうかを判定するために検査が行われる。フィールド３０１内の１は、レンダリング・スクリーン画素が、テクスチャを適用するポリゴン内にあるオブジェクト画素に対応することを示す。検査結果がＮＯのとき、実行プログラムはステップ５４２に進み、そこで次のレンダリング・スクリーン画素を処理することができるように、画素アドレスが増分される。検査結果がＹＥＳのとき、実行プログラムはステップ５０４に進む。
【００９２】
ステップ５０４において、テクスチャ座標（Ｓ，Ｔ）と層深さＤの値が、参照バッファ１２６内のレンダリング・スクリーン画素のセル３００のフィールド３１２および３１４から読み込まれる。読み込まれる数量はすべて、浮動小数点または固定小数点の数量として表わすことができる実数である。
【００９３】
ステップ５０６において、ステップ５０４で読み込まれたＤの値が、テクスチャのＤmaxの値よりも大きいかどうかを判定するために検査が実行される。Ｄmaxの値は、セル３００のフィールド３１０に記憶されたアドレスによって示されたテクスチャ・メモリ１３０のページ１３２のセクション１３３から読み取られる。Ｄの値がＤmaxよりも大きいとき、パターン・データの最大解像度が低すぎて、レンダリングする画像において所望のテクスチャ解像度を提供できないことを示す。この場合、Ｄは、最大可能解像度すなわちＤmaxに設定される。検査結果がＹＥＳの場合、実行プログラムはステップ５０８に進み、そこで、ＤがＤmaxに設定され、次にステップ５１０に進む。検査結果がＮＯの場合は、実行プログラムは、ステップ５１０に直接進む。
【００９４】
ステップ５１０において、ステップ５０４で読み取られた層深さＤが、整数部分ＤLと少数部分Ｄfに分けられる。さらに、スケーリング・ファクタＳＦ＝Ｄmax−ＤLの値が計算される。
【００９５】
ステップ５１２において、層Ｄmaxのテクスチャ座標（Ｓ，Ｔ）を２SFで割って、層ＤLのテクスチャ座標（Ｓ，Ｔ）Lを獲得する。
【００９６】
ステップ５１４において、層ＤFのタイル・ピッチとタイル・ベースの値がそれぞれ、タイル・ピッチ・アレイ１３８とテクスチャ・メモリ１３０のテクスチャのページ１３２のタイル・ベース・アレイ１４０から読み取られ、変数ＷLとＢLに割り当てられる。テクスチャ・メモリ内のテクスチャのページは、参照バッファ１２６内の画素のセル３００のフィールド３１０に記憶されたアドレスによって示される。
【００９７】
ステップ５１６において、テクスチャ座標（Ｓ，Ｔ）Lが、整数部分（Ｓi、Ｔi）Lと少数部分（Ｓf，Ｔf）Lに分けられる。
【００９８】
ステップ５１８において、層ＤLのテクスチャ座標の整数部分（Ｓi，Ｔi）LがそれぞれＴＷLとＴＨLで割られ、商（Ｓr，Ｔr）Lが生成される。ここで、ＴＷLとＴＨLはそれぞれ、層ＤLの内のタイルの画素での幅と高さである。除算（Ｓb，Ｔb）Lの剰余は、ステップ５２４で実行されるサブルーチンと、ステップ５２０で識別されるタイルに適用するための局所座標の計算にも使用される。
【００９９】
ステップ５２０において、画像をレンダリングするのに必要なパターン・データが属する層ＤL内のタイルのタイル番号Ｎtilが、タイル・ベースＢL、その層のタイル・ピッチＷL、およびステップ５１８で計算した商から計算される。タイル番号Ｎtilは、タイル・ベースＢLと商（Ｓr）Lと、商（Ｔr）Lとタイル・ピッチＷLの積とを加えることによって、すなわち、Ｎtil＝ＢL＋（（Ｔr）L×ＷL）＋（Ｓr）Lの式から得られる。
【０１００】
ステップ５２２に、テクスチャ・メモリ１３０のページ１３２内のタイル・ロード・リスト１３６のステップ５２０で識別されたタイルＮtilのエントリが、「Ｌ」に設定され、画像をレンダリングするためにこのタイルのパターン・データを獲得しなければならないことを示す。テクスチャ・メモリのページは、参照バッファ１２６内の画素のセル３００のフィールド３１０に記憶されたアドレスによって示される。
【０１０１】
テクスチャ座標（Ｓ，Ｔ）Lが、ステップ５２０で識別されたタイルと１つまたは複数の隣り合ったタイルとの間の境界上の点を定義するとき、隣り合ったタイルのタイル・ロード・リスト内のエントリは、これらのタイルのパターン・データも獲得しなければならないことを示すために「Ｌ」に設定される。ステップ５２４において、図５Ｂに関して後で詳細に説明するサブルーチンが、ステップ５１８および５１６においてそれぞれ得られた剰余（Ｓb，Ｔb）Lと少数部分（Ｓf，Ｔf）Lを利用して実行される。サブルーチンは、座標（Ｓ，Ｔ）Lが、ステップ５２０で識別されたタイルと１つまたは複数の隣接するタイルとの間の境界上の点を定義するかどうかを確認し、必要に応じて、追加のタイルのタイル・ロード・リストのエントリを「Ｌ」に設定し、それにより、これらのタイルのパターン・データを獲得する。サブルーチンが終了したら、実行プログラムは、ステップ５２６に進む。
【０１０２】
参照バッファ１２６の画素のセル３００のフィールド３１４に記憶されたＤの値が整数の場合は、層ＤL内のパターン・データを利用した補間により、レンダリング・スクリーン画素のテクスチャ色値を決定することができる。通常は、Ｄの値が０でない少数部分を有する場合は、トリリニア補間を利用してテクスチャ色値を生成することが好ましい。さらに、トリリニア補間は、次の高い解像度の層ＤGのパターン・データを必要とする。層ＤGは、層ＤLよりも大きな層深さ、すなわちＤG＝ＤL＋１を有する。図５Ａに示したルーチンの残りの部分は、画像をレンダリングするためにパターン・データを獲得しなければならない高い解像度の層ＤG内のタイルのうちの少なくとも１つを識別する。
【０１０３】
ステップ５２６において、ステップ５１０で得られたＤfの値がゼロよりも大きいかどうか、すなわちＤの値が整数かどうかを判定するために検査される。検査結果がＮＯの場合は、実行プログラムはステップ５４２に進み、そこで、前述のように、レンダリング・スクリーン画素アドレスが増分される。検査結果がＹＥＳの場合は、ステップ５２８〜５４０が実行され、直線解像度が層ＤLの解像度の２倍の、層ＤLのすぐ下の層ＤGの１つまたは複数のタイルのタイル・ロード・リスト・エントリを「Ｌ」に設定する。層間補間で使用するために、次の低い層ＤGで識別された１つまたは複数のタイルのパターン・データが獲得される。
【０１０４】
ステップ５２８において、テクスチャ座標（Ｓ，Ｔ）Gを２倍して、層ＤG内のテクスチャ座標（Ｓ，Ｔ）Lが得られる。
【０１０５】
ステップ５３０〜５４０は、ステップ５３０〜５４０で使用した数量とステップ５３０〜５４０で計算された数量が層ＤLではなくで層ＤGに関係する点以外は、ステップ５１４〜５２４と実質上類似している。ステップ５３８において、層ＤG内の識別されたタイルＮtilのタイル・ロード・リスト１３６内のエントリが「Ｌ」に設定され、画像をレンダリングするためにタイルのパターン・データを獲得しなければならないことを示す。タイル・ロード・リストは、参照バッファ１２６の画素のセル３００のフィールド３１０に記憶されたアドレスによって示されたテクスチャ・メモリ１３０のページ１３２に記憶される。層ＤGのその他のタイルは、ステップ５４０で実行されるサブルーチンで選ばれることもある。サブルーチンの完了後に、実行プログラムは、ステップ５４２に進む。
【０１０６】
ステップ５４２において、画素アドレスが増分される。ステップ５４４において、レンダリング・スクリーン内の画素がすべて処理されたかどうかを判定するために検査が実行される。その結果がＹＥＳの場合は、実行プログラムはステップ５４６に進み、そこで、図４Ｂに示したメイン・ルーチンに戻る。検査結果がＮＯの場合、実行プログラムは、ステップ５０２に戻る。
【０１０７】
図５Ｂは、図５Ａに示した手順のステップ５２４で実行されるサブルーチンの詳細を示す。サブルーチンは、テクスチャ座標（Ｓ，Ｔ）Lが、ステップ５２０で識別されたタイルと１つまたは複数の隣接したタイルとの間の境界上の点を定義しているかどうかを判定し、定義している場合は、タイル・ロード・リスト内の隣接したタイルのエントリをマークする。ステップ５４０で実行されるサブルーチンは、類似しているがテクスチャ座標（Ｓ，Ｔ）Gに適用される。
【０１０８】
実行プログラムがステップ５５１で始まる。
【０１０９】
ステップ５５３において、テクスチャ座標（Ｓ，Ｔ）Lが、ステップ５２０で識別されたタイルの縦の縁上の点を定義しているかどうかを判定するために検査が行われる。そのような点は、識別されたタイルと横方向に隣接したタイルとの境界上にある。ステップ５１８で生成された剰余（Ｓb）LがＴＷL−１と等しいかどうかを判定するために検査が行われ、ステップ５１６で生成された座標ＳLの少数部分（Ｓf）Lが、０よりも大きいかどうかを判定するために検査が実行される。どちらかの検査の結果がＮＯの場合、実行プログラムは、ステップ５６１に進む。両方の検査の結果がＹＥＳの場合は、座標（Ｓ，Ｔ）Lによって定義された点が識別されたタイルの縦の縁上にあることを示し、実行プログラムはステップ５５５に進む。
【０１１０】
ステップ５５５において、タイル番号Ｎtil＋１を有するタイルのタイル・ロード・リスト内のエントリが「Ｌ」に設定される。その場合、実行プログラムはステップ５５７に進む。
【０１１１】
ステップ５５７において、座標（Ｓ，Ｔ）Lが、ステップ５２０で識別されたタイルの角上の点を定義しているかどうかを判定するために検査が行われる。そのような点は、識別されたタイルと縦横両方向の隣接したタイルとの境界上にある。ステップ５１８で生成された剰余（Ｔb）LがＴＨL−１と等しいかどうかを判定するために検査が行われ、ステップ５１６で生成された座標ＴLの少数部分（Ｔf）Lが、０よりも大きいかどうか判定するために検査が実行される。どちらかの検査結果がＮＯの場合、実行プログラムは、ステップ５６１に進む。両方の検査結果がＹＥＳの場合は、座標（Ｓ，Ｔ）Lによって定義された点が、識別されたタイルの角上にあることを示し、実行プログラムは、ステップ５５９に進む。
【０１１２】
ステップ５５９において、タイル番号Ｎtil＋ＷL＋１のタイルのタイル・ロード・リスト内のエントリが「Ｌ」に設定される。次に、実行プログラムは、ステップ５６１に進む。
【０１１３】
ステップ５６１において、座標（Ｓ，Ｔ）Lがステップ５２０で識別されたタイルの横の縁上の点を定義しているかどうかを判定するために検査が実行される。そのような点は、識別されたタイルと縦方向に隣接したタイルとの間の境界上にある。実行される検査は、ステップ５５７で実行されたものと同じであり、すなわち、ステップ５１８で生成された剰余（Ｔb）Lが、ＴＨL−１と等しいかどうか判定するために検査が行われ、ステップ５１６で生成された座標ＴLの少数部分（Ｔf）Lが０よりも大きいかどうかを判定するために検査が行われる。どちらかの検査結果がＮＯの場合、実行プログラムはステップ５６５に進み、メイン・ルーチンに戻る。両方の検査結果がＹＥＳの場合は、座標（Ｓ，Ｔ）Lによって定義された点が、識別されたタイルの横の縁上にあることを示し、実行プログラムはステップ５６３に進む。
【０１１４】
ステップ５６３において、タイル番号Ｎtil＋ＷLを有するタイルのタイル・ロード・リスト内のエントリが「Ｌ」に設定される。次に、実行プログラムはステップ５６５に進み、メイン・ルーチンに戻る。
【０１１５】
図６は、図４Ｂに示したルーチンのステップ４６２を実行するために使用することができるルーチンの例の詳細なフローチャートである。このルーチンは、テクスチャ・データ・メモリ１３０の各ぺージ１３２に記憶されたタイル・ロード・リスト１３６が、タイル・ロード・リスト・エントリが「Ｌ」に設定されたタイルのパターン・データを獲得するかどうかを検査し、パターン・データが獲得されたタイルのタイル・ロード・リスト・エントリを「Ｅ」に設定する。パターン・データは、合成またはローディングによって獲得される。このルーチンは、テクスチャ・データ・メモリ１３０のぺージ１３２にテクスチャ・データを記憶するテクスチャのそれぞれに関して実行される。図４Ｂに示したルーチンのステップ４６１が、参照バッファ１２６内の各セルに関して実行された後で、画像をレンダリングするためにパターン・データを獲得しなければならない各タイルごとのタイル・ロード・リスト内のエントリが「Ｌ」に設定される。
【０１１６】
実行プログラムは、ステップ６００から始まる。初めに、図２に示したピラミッド形データ構造における層に対応するタイル・ロード・リストの部分が、テクスチャ解像度が最も高い最下層に対応する部分から検査される。次の説明において、検査されるタイル・ロード・リスト部分に対応する層は、現在層と呼ばれる。現在層よりも小さい層深さを有する層は、次に高い層と呼ばれる。現在層よりも大きい層深さを有する層は、次に低い層と呼ばれる。
【０１１７】
ステップ６０２において、層深さインデックスｄの値が、最も下（最も高い解像度）の層の層深さであるＤmaxに設定される。
【０１１８】
ステップ６０４において、タイル・インデックスｔは、現在層のタイル・ベースの値であるＢdに設定される。
【０１１９】
ステップ６０６において、タイル・インデックスｔを有するタイルのタイル・ロード・リスト（図では、ＴＬＬとして略記された）内のエントリが「Ｌ」に設定されているかどうかを判定するために検査が行われる。検査結果がＮＯの場合は、タイルのパターン・データを獲得する必要がないことを示し、実行プログラムはステップ６１８に進む。検査結果がＹＥＳの場合、実行プログラムは、ステップ６０８に進む。
【０１２０】
ステップ６０８において、現在層を示す層深さインデックスｄが、図２に示したピラミッド形データ構造２００の最下層２０２の層深さＤmaxよりも小さいかどうかを判定するために検査が行われる。最下層に記憶されたパターン・データは、最下層のパターン・データを合成するために利用可能なそれよりも高い解像度パターン・データがないため、合成することができない。したがって、検査結果がＮＯの場合は、現在層が最下層であることを示し、実行プログラムはステップ６１０に進み、タイル・インデックスｔを有するタイルのパターン・データがロードされ、テクスチャ・メモリ１３０のテクスチャのページ１３２のピラミッド形データ構造１３４内のタイル・インデックスによって示された場所に記憶される。次に、実行プログラムは、後で説明するステップ６１６に進む。
【０１２１】
ステップ６０８の検査結果がＹＥＳの場合、実行プログラムはステップ６１２に進む。ＹＥＳの検査結果は、現在層が最下層よりも高いことを示し、それにより、現在層内のタイルのパターン・データが、層深さがｄ＋１である、次に低い層すなわち解像度が高い層にあるソース・タイルのパターン・データから合成することができる。パターン・データの合成は、パターン・データのロードよりも速いため、通常、パターン・データの合成が、パターン・データのロードよりも好ましい。
【０１２２】
ステップ６１２において、タイル・インデックスｔを有するタイルのソース・タイルのタイル・ロード・リスト内のエントリがすべて「Ｅ」に設定されているかどうかを判定するために検査が実行される。ソース・タイルは、現在層内のタイルのパターン・データを合成するためにパターン・データを使用することができる次に低い層にあるタイルである。そのような合成は、すべてのソース・タイルのタイル・ロード・リストのエントリに「Ｅ」によって示されたように、必要なすべてのソース・タイルのパターン・データがピラミッド形データ構造で存在する場合のみ実行される。次に低い層の４つのソース・タイルのパターン・データは、現在層のほとんどのタイルのパターン・データを合成するために必要とされる。しかしながら、現在層の右側と一番下の境界にあるタイルのパターン・データを合成するためには、２つのソース・タイルのパターン・データだけが必要となることがある。さらに、現在層の一番下の右側の角にあるタイルのパターン・データとして、１つのソース・タイルのパターン・データだけが使用されることもある。
【０１２３】
ステップ６１２の検査結果がＮ０の場合は、次に低い層に、現在層でタイル・インデックスｔを有するタイルを合成するためには不十分なパターン・データしかないことを示し、実行プログラムはステップ６１０に進む。ステップ６１０において、前述のように、タイル・インデックスｔを有するタイルのパターン・データがロードされる。検査結果がＹＥＳの場合、実行プログラムはステップ６１４に進む。
【０１２４】
ステップ６１４において、現在層のタイル・インデックスｔを有するタイルのパターン・データが、次に低い層のソース・タイルのパターン・データから合成される。合成されたパターン・データは、テクスチャ・メモリ１３０のテクスチャのページ１３２のピラミッド形データ構造１３４内のタイル・インデックスで示された場所に記憶される。次に、実行プログラムは、ステップ６１６に進む。
【０１２５】
ステップ６１６において、タイル・インデックスｔを有するタイルのタイル・ロード・リスト内のエントリが「Ｅ」に設定され、これは、ステップ６１４の合成またはステップ６１０のローディングによって獲得された結果、現在テクスチャのピラミッド形データ構造内にタイルのパターン・データが存在することを示す。
【０１２６】
ステップ６１８において、タイル・インデックスが増分される。
【０１２７】
ステップ６２０において、現在層のすべてのタイルのタイル・ロード・リストのエントリを検査したかどうかを判定するために検査が実行される。これは、タイル・インデックスの値が、次に低い層のタイル・ベースの値であるＢd+1より大きいかどうかを検査することによって行われる。現在層が最も下（最も高い解像度）の層のときは、タイル・ベース・アレイに記憶されたタイルの総数の値が、最下層よりも下の（存在しない）層のタイル・ベースとして使用される。検査結果がＮＯの場合は、実行プログラムがステップ６０６に戻り、したがって、現在層内の別のタイルのタイル・ロード・リストのエントリを検査することができる。検査結果がＹＥＳの場合は、現在層のすべての可能なパターン・データをすべて獲得したことを示し、実行プログラムはステップ６２２に進む。
【０１２８】
ステップ６２２において、層深さインデックスｄが、１だけ減分される。
【０１２９】
ステップ６２４において、現在層の層深さｄが、最も上（最低の解像度）の層の層深さである０よりも小さいかどうかを判定するために検査が行われる。検査結果がＮＯの場合、実行プログラムはステップ６０４に戻り、それにより次に高い層のパターン・データを獲得することができる。検査結果がＹＥＳの場合は、タイル・ロード・リストのエントリが「Ｌ」に設定されるすべてのタイルのパターン・データが獲得されたことを示し、実行プログラムはステップ６２６に進み、図４Ｂに示したルーチンに戻る。
【０１３０】
図７Ａは、最良解像度表示モードにおけるレンダリング・スクリーン画素の最終色値を生成するために、図４Ｂに示したメイン・ルーチンのステップ４６３で実行されるルーチンの詳細を示す。このルーチンは、画素の参照バッファ・セル３００のフィールド３０１に１を有するレンダリング・スクリーンの各画素に関して実行される。このフィールドの１は、レンダリング・スクリーン画素が、テクスチャを適用するポリゴン内にあるオブジェクト画素に対応することを示す。各レンダリング・スクリーン画素の最終色値は、ステップ４５４で計算された輝度係数に、ステップ４６２で獲得したパターン・データからトリリニア補間によって得たテクスチャ色値を掛けることによって得られる。実行プログラムが、ステップ７００で始まる。
【０１３１】
ステップ７０２において、このルーチンは、参照バッファ１２６内の画素のセル３００にアクセスして、テクスチャの座標Ｓ、Ｔと層深さＤを読み取る。これらのパラメータはすべて実数である。
【０１３２】
ステップ７０４において、ステップ７０２で読み取られたＤの値を有する層深さのテクスチャ色値を得る層間補間を実行するために使用されるピラミッド形データ構造の２つの層の層深さが決定される。前述のように、層は、層深さＤを一括する。層深さＤは、その整数部分ＤLと少数部分Ｄfに分けられる。さらに、ＤLは、１だけ増分され、ＤG（＝ＤL＋１）が得られる。２つの層の高い方の解像度は、層深さがＤGの層である。２つの層の低い方の解像度は、層深さがＤLの層である。
【０１３３】
ステップ７０６において、ＤGが最大層深さＤmaxよりも大きいかどうかを判定するために検査が実行される。検査結果がＮＯの場合、実行プログラムはステップ７１０に進む。検査結果がＹＥＳの場合は、実行プログラムはステップ７０８に進み、ＤLとＤGの両方がＤmaxに設定され、少数部分Ｄfがゼロに設定される。次に、実行プログラムはステップ７１０に進む。
【０１３４】
ステップ７１０において、テクスチャ座標（Ｓ，Ｔ）と層深さＤmaxを有する最も下（最も高い解像度）の層の座標のテクスチャ座標（Ｓ，Ｔ）が、層ＤL内のテクスチャ座標（Ｓ，Ｔ）Lに変換される。図５Ａのステップ５１０と５１２を参照して前に説明したプロセスを利用することができる。テクスチャ座標（Ｓ，Ｔ）Lによって定義された点の最も近くにある層ＤL内の画素が識別され、点（Ｓ，Ｔ）Lからの距離が計算される。次に、点（Ｓ，Ｔ）Lからの距離によって逆に重み付けされた識別済みテクスチャ画素のテクスチャ色値を使用して、最初の層内補間が実行される。最初の層内補間操作により、テクスチャ座標（Ｓ，Ｔ）Lにあるテクスチャ画素のテクスチャ色値Ｒ1、Ｇ1、Ｂ1が計算される。
【０１３５】
ステップ７１２において、少数部分Ｄfが０よりも大きいかどうかを判定するために検査が実行される。検査結果がＮＯの場合は、層間補間が必要ないことを示し、実行プログラムはステップ７１４に進み、テクスチャ色値Ｒ0、Ｇ0、Ｂ0がそれぞれ、ステップ７１０でそれぞれ計算されたテクスチャ色値Ｒ1、Ｇ1、Ｂ1の値に設定される。実行プログラムは、後で説明するステップ７２０に進む。検査結果がＹＥＳの場合は、層間補間が必要であることを示し、実行プログラムはステップ７１６に進む。
【０１３６】
ステップ７１６において、テクスチャ座標（Ｓ，Ｔ）は、層ＤG内のテクスチャ座標（Ｓ，Ｔ）Gに変換される。テクスチャ座標（Ｓ，Ｔ）Gによって定義された点の最も近くにある層ＤG内の画素が識別され、点（Ｓ，Ｔ）Gからの距離が計算される。次に、点（Ｓ，Ｔ）Gからの距離に従って逆に重み付けされた識別済みのテクスチャ画素のテクスチャ色値を使って、第２の層内補間操作が実行される。第２の層内補間操作により、テクスチャ座標（Ｓ，Ｔ）Gにあるテクスチャ画素のテクスチャ色値Ｒ2、Ｇ2、Ｂ2が計算される。
【０１３７】
ステップ７１８において、層間補間操作が実行され、層深さＤを有する層の座標（Ｓ，Ｔ）Dにあるテクスチャ画素のテクスチャ色値が生成される。この補間は、加重係数として、層ＤLのテクスチャ色値Ｒ1、Ｇ1、Ｂ1、層ＤGのテクスチャ色値Ｒ2、Ｇ2、Ｂ2、および層深さＤの少数部分Ｄfを使用する。層間補間操作により、テクスチャ色値Ｒ0、Ｇ0、Ｂ0が生成される。
【０１３８】
ステップ７２０において、レンダリング・スクリーン画素の輝度係数が、参照バッファ１２６の画素のセル３００のフィールド３１６から読み取られ、層間補間が必要かどうかによって、ステップ７１４かまたはステップ７１８で生成されたテクスチャ色値Ｒ0、Ｇ0、Ｂ0が掛けられる。得られた最終色値は、画素・深さバッファ１２４のレンダリング・スクリーン画素の場所に記憶される。
【０１３９】
実行プログラムは、ステップ７２２に進み、そこからメイン・ルーチンに戻る。
【０１４０】
図７Ｂは、漸進的解像度表示モードでレンダリング・スクリーン画素の最終色値を生成するために、図４Ｂに示したメイン・ルーチンのステップ４７２で実行されるルーチンの詳細を示す。このルーチンは、参照バッファ１２６の画素のセル３００のフィールド３０１に１を有するレンダリング・スクリーンの各画素ごとに実行される。このフィールド内の１は、その画素が、テクスチャを適用するポリゴン内にあるオブジェクト画素から得られるたことを示す。最終色値は、ステップ４５４で計算された輝度係数にテクスチャ色値を掛けることによって得られる。テクスチャ色値は、現在獲得済みのタイルのパターン・データ、すなわち、ステップ４７２〜４７７からなる解像度改善ループが実行される前にステップ４７１で獲得されたパターン・データと、解像度改善ループに続いてステップ４７１で獲得されたパターン・データとステップ４７７で獲得されたパターン・データからの補間によって得られる。現在獲得済みのタイルのパターン・データによって提供される解像度が、メイン・ルーチンのステップ４５４で計算された層深さＤに十分でない場合は、解像度改善ループは、必要な解像度を実現するためにパターン・データを必要とするタイルのタイル・ロード・リストのエントリを「Ｌ」に設定し、ステップ４７７を次に実行するときに獲得しなければならないパターン・データを示す。実行プログラムは、ステップ７５０から始まる。
【０１４１】
ステップ７５２、７５４、７５６および７５８は、図７Ａを参照して前に説明したステップ７０２、７０４、７０６および７０８と同じであり、ここでは再び説明しない。
【０１４２】
ステップ７６０〜７６６において、テクスチャのタイル・ロード・リスト内のエントリを検査して、テクスチャ座標（Ｓ，Ｔ）にあるテクスチャ画素のテクスチャ色値を補間するために使用できる最も高い解像度の現在獲得済みのタイルを見つける。テクスチャ座標（Ｓ，Ｔ）にあるテクスチャ画素のテクスチャ色値の補間に必要な層内のタイルの数は、前に説明したように、テクスチャ座標が、タイル内、２つのタイル間の境界または４つのタイル間の角にある点を定義するかどうかによって、１つ、２つまたは４つでもよい。タイル・ロード・リストの検査は、ピラミッド形データ構造の層ＤGに対応するタイル・ロード・リストの一部から始まる。層ＤGのタイル・ロード・リスト・エントリが、テクスチャ座標（Ｓ，Ｔ）においてテクスチャ画素のテクスチャ色値を補間するために必要な１つまたは複数のタイルのパターン・データが、その層に存在することを示す場合、テクスチャ色値は、これらのタイルのパターン・データから補間される。そうでない場合は、次に高いレベル（次に低い解像度）の層ＤG−１のタイル・ロード・リストのエントリが検査される。さらに高い層すなわちさらに低い解像度の層のタイル・ロード・リストのエントリが、必要なパターン・データを含む層が見つかるまで検査される。このルーチンが実行される前に最も上のタイルのパターン・データがメイン・ルーチンのステップ４７１でロードされるため、検査プロセスは、常に有効な結果で終了する。
【０１４３】
ステップ７６０において、層深さインデックスｄがＤGに設定される。ステップ７６２において、図５Ａを参照して前に説明したものと類似のルーチンが実行され、テクスチャ座標（Ｓ，Ｔ）に対応する現在層内のタイルが識別される。ステップ７６４において、ステップ７６２で識別されたすべてのタイルのタイル・ロード・リスト・エントリが、タイルのパターン・データが獲得済みでテクスチャのピラミッド形データ構造に記憶されたことを示す「Ｅ」に設定されているかどうかを判定するために検査が行われる。
【０１４４】
ステップ７６４の検査結果が、必要なパターン・データが現在層にないことを示すＮＯの場合は、実行プログラムはステップ７６６に進み、層インデックスが１だけ減分される。実行プログラムは、ステップ７６２に戻り、次に高いレベル（次に低い解像度）の層のタイル・ロード・リスト部分が検査される。検査結果がＹＥＳの場合は、現在層が、テクスチャ座標（Ｓ，Ｔ）にあるテクスチャ画素のテクスチャ色値の補間に必要なパターン・データを含むことを示し、実行プログラムはステップ７６８に進む。
【０１４５】
ステップ７６８において、変数Ｄ1は、層インデックスｄの現在値に設定される。変数Ｄ1の値は、タイル・ロード・リストの検査が終了した層の層深さを示す。
【０１４６】
ステップ７７０において、ステップ７６２で識別した層Ｄ1の１つまたは複数のタイルのパターン・データを使用して、層内補間操作が実行される。この補間操作は、図７Ａのステップ７１０を参照して前に説明した方法を使用して実行することができる。この補間操作により、テクスチャ座標（Ｓ，Ｔ）にあるテクスチャ画素のテクスチャ色値Ｒ1、Ｇ1、Ｂ1が生成される。
【０１４７】
Ｄ1がＤGよりも小さい場合、これは、メイン・ルーチンのステップ４５４で計算された層深さＤに関してテクスチャ色値が不十分な解像度で生成されたことを意味する。必要な解像度を実現するためには、追加のパターン・データを獲得する必要がある。したがって、ステップ７７２において、Ｄ1がＤGと等しいかどうかを判定するために検査が実行される。
【０１４８】
検査結果がＮＯの場合、実行プログラムはステップ７７４に進み、そこでテクスチャ色値Ｒ0、Ｇ0、Ｂ0が、ステップ７７０で計算されたテクスチャ色値Ｒ1、Ｇ1、Ｂ1の値にそれぞれ設定される。実行プログラムはステップ７７６に進み、そこで、テクスチャ座標（Ｓ，Ｔ）にあるテクスチャ画素のテクスチャ色値を補間するのに必要なＤ1＋１の層深さを有する層の１つまたは複数のタイルのタイル・ロード・リスト・エントリが「Ｌ」に設定される。この設定は、図４Ｂを参照して前に説明したメイン・ルーチンのステップ４７７を次に実行するときに、これらのタイルのパターン・データを獲得しなければならないことを示す。
【０１４９】
次に、実行プログラムは、後で説明するステップ７７８に進む。
【０１５０】
ステップ７７２で得られた検査結果がＹＥＳの場合、実行プログラムは、ステップ７８０に進む。ＹＥＳの結果は、Ｄ1がＤGと等しく、必要な解像度でテクスチャ座標（Ｓ，Ｔ）にあるテクスチャ画素のテクスチャ色値を補間するのに必要な１つまたは複数のタイルのパターン・データがピラミッド形データ構造内に存在することを示す。
【０１５１】
ステップ７８０において、層ＤL＝ＤG−１の１つまたは複数のタイルのパターン・データを使用して層内補間操作が実行される。この補間操作は、図７Ａのステップ７１０を参照して前に説明した法を使用して実行することができる。この補間操作により、層ＤL内のテクスチャ座標（Ｓ，Ｔ）Lにあるテクスチャ画素のテクスチャ色値Ｒ2、Ｇ2、Ｂ2が生成される。
【０１５２】
ステップ７８２において、ステップ７７０で生成された層ＤGのテクスチャ色値Ｒ1、Ｇ1、Ｂ1と、ステップ７８０で生成された層ＤLのテクスチャ色値Ｒ2、Ｇ2、Ｂ2との間で、層Ｄのテクスチャ座標（Ｓ，Ｔ）でのテクスチャ画素の層間補間が実行される。この補間は、加重係数として層深さＤの少数部分Ｄfを使用する。層間補間は、テクスチャ色値Ｒ0、Ｇ0、Ｂ0を生成する。
【０１５３】
ステップ７７８において、レンダリング・スクリーン画素の輝度係数が、参照バッファ１２６の画素のセル３００のフィールド３１６から読み取られ、ステップ７７０またはステップ７８２で生成されたテクスチャ色値Ｒ0、Ｇ0、Ｂ0が掛けられる。レンダリング・スクリーン画素の得られた最終色値は、画素・深さメモリ１２４内のレンダリング・スクリーン画素の場所に記憶される。
【０１５４】
次に、実行プログラムはステップ７８４に進み、そこからメイン・ルーチンに戻る。
【０１５５】
本発明は、ピラミッド形データ構造の層内のタイルを、従来の走査順序すなわち左から右、上から下の走査順序で配列した例を参照して説明した。しかしながら、層内のタイルの配列は重要ではなく、様々な配列を使用することができる。異なる配列を使用する場合は、それに従って、層の左上、右側の下の縁、下の右側の角にあるタイルに基準を変更しなければならない。
【００１５６】
以上、本発明の実施例について詳述したが、以下、本発明の各実施態様の例を示す。
（実施態様１）
三次元図形データに応じて画像をレンダリングするレンダリング装置であって、
（ａ）前記レンダリング装置が前記三次元図形データを受け取ることができる経路であって、前記三次元図形データが、ポリゴン・データとさらにテクスチャを定義するテクスチャ・データを含み、前記テクスチャ・データがテクスチャ・サイズ・データおよび組になったパターン・データを含み、各組の前記パターン・データがテクスチャを異なる解像度で表わし、前記パターン・データが前記テクスチャ・データの大部分を構成し、
（ｂ）レンダリング・スクリーンの画素に対応する第１のメモリ・セルを含む画素・深さバッファと、
（ｃ）前記レンダリング・スクリーンの画素に対応する第２のメモリ・セルを含む参照バッファと、
（ｄ）前記ポリゴン・データと前記テクスチャ・サイズ・データだけを使用して初期ラスタ化操作を実行して、前記レンダリング・スクリーンの各画素ごとにテクスチャ識別子、テクスチャ解像度を示す層深さ値およびテクスチャ座標を生成し参照バッファ内に記憶し、
テクスチャ識別子、レンダリング・スクリーン画素ごとに参照バッファに記憶された層深さおよびテクスチャ座標に応じて、前記画像をレンダリングするために必要なパターン・データを識別し、
前記画像をレンダリングするのに必要であると識別された前記パターン・データを前記経路を介して獲得し、
前記バッファとの間のデータ転送速度よりも実質上低いデータ転送速度を有する経路を介して獲得した前記パターン・データを使って前記画像を表す画像データを生成するレンダリング・エンジンと、
を含むことを特徴とするレンダリング装置。
（実施態様２）
前記パターン・データをピラミッド形データ構造で記憶するテクスチャ・メモリをさらに含み、前記ピラミッド形データ構造が、前記テクスチャを異なる解像度で表す前記パターン・データの各組に、記憶する層を含み、前記パターン・データの組のうちの１組は前記テクスチャを最も高い解像度で表わすことを特徴とする実施態様１に記載のレンダリング装置。
（実施態様３）
さらに、前記レンダリング・エンジンが実行する初期ラスタ化操作によって、前記レンダリング・スクリーンのそれぞれの画素の輝度係数が生成され、
さらに、前記輝度係数は、前記参照バッファの前記第２のメモリ・セルのうちの１つに記憶され、前記第２のメモリ・セルのうちの１つは前記レンダリング・スクリーンの前記画素の１つに対応することを特徴とする実施態様２に記載のレンダリング装置。
（実施態様４）
前記パターン・データは、方形タイルに配列されたテクスチャ画素に属し、前記装置は、さらに、前記テクスチャのタイル・ロード・リストを含み、前記タイル・ロード・リストは各前記タイルごとのエントリを含み、
前記レンダリング・エンジンが、前記画像をレンダリングするのに必要な前記パターン・データを識別したときに、
前記レンダリング・エンジンは、前記参照バッファからテクスチャ座標を読み取って前記画像をレンダリングするのに必要なパターン・データがある前記タイルの一つを識別し、
前記タイルの一つに関する前記タイル・ロード・リスト内のエントリを、前記画像をレンダリングするために、前記タイルの一つのパターン・データが必要であることを示すロード状態に設定する
ことを特徴とする実施態様２に記載のレンダリング装置。
（実施態様５）
前記レンダリング・エンジンが前記画像をレンダリングするのに必要な前記パターン・データを獲得するときに、
前記レンダリング・エンジンは、前記テクスチャの前記タイル・ロード・リストを検査してロード状態に設定された前記エントリを識別し、
前記タイル・ロード・リスト内のエントリがロード状態に設定されていると識別された各前記タイルの前記パターン・データを獲得し、
前記パターン・データを獲得した各前記タイルのタイル・ロード・リスト内のエントリをロード状態から存在状態に変更し、
存在状態が、前記タイルの一つの前記パターン・データが獲得されたことを示すことを特徴とする実施態様４に記載のレンダリング装置。
（実施態様６）
前記パターン・データは、方形タイルに配列されたテクスチャ画素に属し、
さらに、前記レンダリング装置は、前記テクスチャのタイル・ロード・リストを含み、前記タイル・ロード・リストは、各前記タイルの１つの前記パターン・データを獲得したことを示すエントリを含み、
前記レンダリング・エンジンは、前記ピラミッド形データ構造における１つの前記層に１つの前記タイルの前記パターン・データを獲得するとき、
前記レンダリング・エンジンは、前記タイル・ロード・リストを検査して、前記層の１つの直下の層にあるソース・タイルの１つのパターン・データが獲得されているかどうかを判定し、
前記ソース・タイルが、前記タイルの一つのパターン・データを合成することができる前記タイルであり、前記ソース・タイルの前記パターン・データから前記タイルの一つの前記パターン・データを合成する
ことを特徴とする実施態様２に記載のレンダリング装置。
（実施態様７）
前記パターン・データは、方形タイルに配列されたテクスチャ画素に属し、
前記レンダリング・エンジンは、前記ピラミッド形データ構造の最上層を構成するタイルの一つの前記パターン・データを前記経路を介してロードすることによって前記画像をレンダリングするのに必要な前記パターン・データの初期部分を獲得し、前記タイルの一つを前記ピラミッド形データ構造で記憶し、
前記レンダリング・エンジンは、前記ピラミッド形データ構造に現存する前記パターン・データから前記画像データを生成し、より高い解像度で前記画像をレンダリングするためにパターン・データを必要とする前記ピラミッド形データ構造の前記タイルを識別し、前記識別したタイルのパターン・データを獲得し、前記画像データをより高い解像度で再生する
ことを特徴とする実施態様２に記載のレンダリング装置。
（実施態様８）
前記レンダリング・エンジンは、前記画像をより高い解像度でレンダリングするためにパターン・データを必要とする前記タイルを識別し、
前記識別したタイルの前記パターン・データを獲得し、前記画像をより高い解像度で再生するルーチンを、前記画像データがすべて最良解像度で生成されるまで繰り返し実行し、前記画像データの最良解像度が、最高解像度よりも低い前記レンダリング・スクリーンの前記画素のサブセットに対応することを特徴とする実施態様７に記載のレンダリング装置。
（実施態様９）
前記レンダリング・エンジンは、（ａ）前記経路を介した前記パターン・データのローディングと、（ｂ）前記パターン・データの合成のいずれか一方によって、前記画像をレンダリングするために必要な前記パターン・データを獲得することを特徴とする実施態様１に記載のレンダリング装置。
（実施態様１０）
前記層深さ値は、整数部分と少数部分を有する実数であり、
前記層深さ値の少数部分が０のとき、前記レンダリング・エンジンが、前記層深さ値の整数部分によって示された１つの組の前記パターン・データ間の第１の層内補間を実行して、前記画像データを引き出すテクスチャ色値を生成し、
前記層深さ値の少数部分が０でないとき、前記レンダリング・エンジンは、前記第１の層内補間と、前記１つの組よりも高いレベルの解像度を有する別の組のパターン・データ間の第２の層内補間と、前記第１層内補間と前記第２の層内補間によって生成された結果の間の層間補間を実行して、前記画像データを引き出す前記テクスチャ色値を生成することを特徴とする実施態様１に記載のレンダリング装置。
（実施態様１１）
三次元図形データに応じて画像をレンダリングする方法であって、
前記画像がレンダリング・スクリーンの画素に対応する画像データによって表わされ、前記三次元図形データが、ポリゴン・データとさらにテクスチャを定義するテクスチャ・データとを含み、前記テクスチャ・データが、テクスチャ・サイズ・データおよび組になったパターン・データとを含み、前記各組のパターン・データが前記テクスチャを異なる解像度で表し、前記パターン・データが前記テクスチャ・データの大部分を構成し、
（ａ）前記ポリゴン・データと前記テクスチャ・サイズ・データを受け取る段階と、
（ｂ）前記レンダリング・スクリーン前記画素ごとに、前記ポリゴン・データと前記テクスチャ・サイズ・データを使って、テクスチャ識別子、テクスチャ解像度を示す層深さ値およびテクスチャ座標を生成して記憶する初期ラスタ化操作を実行する段階と、
（ｃ）前記レンダリング・スクリーン画素ごとに記憶した前記テクスチャ識別子、前記層深さおよび前記テクスチャ座標に応じてパターン・データ識別操作を実行する段階であって、前記パターン・データ識別操作は前記画像をレンダリングするのに必要な前記パターン・データを識別し、
（ｄ）パターン・データ識別操作によって、前記画像をレンダリングするのに必要であると識別されたパターン・データを獲得するパターン・データ獲得操作を実行する段階と、
（ｅ）前記パターン・データ獲得操作によって獲得された前記パターン・データを使用して前記画像を表す前記画像データを生成する最終ラスタ化操作を実行する段階と、
を含むことを特徴とする画像レンダリング方法。
（実施態様１２）
（ａ）テクスチャ・メモリを提供する段階と、
（ｂ）テクスチャ・メモリに、前記パターン・データ獲得操作によって獲得されたパターン・データをピラミッド形データ構造で記憶する段階と、
を含み、前記ピラミッド形データ構造は、前記テクスチャを異なる解像度で表す前記パターン・データの組がそれぞれ記憶された層を含み、前記パターン・データの組のうちの１組が前記テクスチャを最も高い解像度で表すことを特徴とする実施態様１１に記載の画像レンダリング方法。
（実施態様１３）
さらに、前記初期ラスタ化操作は、前記レンダリング・スクリーン画素の１つの画素の輝度係数を生成し、
前記輝度係数は、前記レンダリング・スクリーン前記画素のうちの１つの画素の、前記テクスチャ識別子、前記層深さ値および前記テクスチャ座標と共に記憶されることを特徴とする実施態様１２に記載の画像レンダリング方法。
（実施態様１４）
実施態様１２に記載の画像レンダリング方法であって、
（ａ）前記パターン・データは、方形タイルに配列されたテクスチャ画素に属し、
（ｂ）該方法は、さらに、前記テクスチャのタイル・ロード・リストを提供する段階とを含み、前記タイル・ロード・リストは各タイルごとのエントリを含み、
（ｃ）前記データ・パターン識別操作が、
テクスチャ座標を読み取って、前記画像をレンダリングするのに必要なパターン・データがある前記タイルの一つを識別する段階と、
前記タイルの一つのタイル・ロード・リスト内のエントリをロード状態に設定する段階とを含み、前記ロード状態は前記タイルの一つの前記パターン・データが前記画像をレンダリングするために必要とすることを示すことを特徴とする画像レンダリング方法。
（実施態様１５）
前記パターン・データ獲得操作は、
（ａ）前記テクスチャの前記タイル・ロード・リストを検査して、ロード状態に設定されたエントリを識別する段階と、
（ｂ）前記タイル・ロード・リスト内のエントリがロード状態に設定されていると識別された前記各タイルの前記パターン・データを獲得する段階と、
（ｃ）前記パターン・データを獲得した前記各タイルのタ前記イル・ロード・リスト内のエントリを、ロード状態から、前記各タイルの前記パターン・データを獲得したことを示す存在状態に変更する段階と、
を含むことを特徴とする実施態様１４に記載の画像レンダリング方法。
（実施態様１６）
実施態様１２に記載の画像レンダリング方法であって、
（ａ）前記パターン・データは、方形タイルに配列されたテクスチャ画素に属し、
（ｂ）さらに、該方法は前記テクスチャのタイル・ロード・リストを提供する段階を含み、前記タイル・ロード・リストは各前記タイルのエントリーを含み、前記エントリーは、前記タイルの１つの前記パターン・データが前記ピラミッド形データ構造で存在することを示す状態を有し、
（ｃ）前記パターン・データ獲得操作は前記ピラミッド形データ構造の１層にある１つのタイルの前記パターン・データを獲得するために実行され、
前記タイル・ロード・リストを検査して、前記層の直下にある層にあるソース・タイルの前記パターン・データが前記ピラミッド形データ構造に存在し、前記ソース・タイルが、前記タイルの一つの前記パターン・データを合成することができるタイルであるかどうかを判定する段階と、
前記ソース・タイルの前記パターン・データが前記ピラミッド形データ構造に存在するときに、前記ソース・タイルの前記パターン・データから前記タイルの一つの前記パターン・データを合成する段階と、
を含むことを特徴とする画像レンダリング方法。
（実施態様１７）
実施態様１２に記載の画像レンダリング方法であって、
（ａ）前記パターン・データは、方形タイルに配列されたテクスチャ画素に属し、
（ｂ）前記ピラミッド形データ構造の最上層を構成する前記タイルの一つのパターン・データを受け取って前記ピラミッド形データ構造に記憶し、前記パターン・データ識別動作を実行する前に、前記ピラミッド形データ構造に現存する前記パターン・データから前記画像データを生成する最終ラスタ化操作を実行し、
（ｃ）前記パターン・データ識別操作は、より高い解像度で前記画像をレンダリングするために前記パターン・データが必要な前記ピラミッド形データ構造のタイルを識別し、
（ｄ）さらに、該方法は前記パターン・データ獲得操作の後で、前記最終ラスタ化操作を繰り返して、前記画像データをさらに高い解像度で再生する段階と、
を含むことを特徴とする画像レンダリング方法。
（実施態様１８）
前記最終ラスタ化操作、前記パターン・データ識別操作および前記パターン・データ獲得操作を、前記画像データがすべて最良解像度で生成されるまで繰り返し、前記画像データの最良解像度は、最も高い解像度よりも低い前記レンダリング・スクリーンの前記画素のサブセットに対応することを特徴とする実施態様１７に記載の画像レンダリング方法。
（実施態様１９）
前記パターン・データ獲得操作は、（ａ）パターン・データのロード、または（ｂ）パターン・データの合成のうちの１つによって、前記画像をレンダリングするのに必要な前記パターン・データを獲得する段階を含むことを特徴とする実施態様１１に記載の画像レンダリング方法。
（実施態様２０）
実施態様１１に記載の画像レンダリング方法であって、
（ａ）初期ラスタ化操作を実行する段階は、整数部分と少数部分を有する実数として層深さ値を生成し、
（ｂ）最終ラスタ化操作を実行する段階は、さらに、
（ｂ−１）前記層深さ値の少数部分が０のときに、前記層深さ値の整数部分によって識別された１つの組のパターン・データ間の第１の層内補間を実行して、テクスチャ色値から画像データを導き出す段階と、
（ｂ−２）層深さ値の少数部分が０でないときに、前記第１の層内補間を実行して、前記組よりも高いレベルの解像度を有する別の組のパターン・データ間の第２の層内補間操作を実行し、前記第１層内補間と前記第２の層内補間操作によって生成された結果の間で層間補間を実行して、テクスチャ色値から前記画像データを導き出すことを特徴とする画像レンダリング方法。
【０１５７】
この開示は、本発明の実施例を詳細に説明しているが、本発明が、説明した厳密な実施例に制限されず、併記の特許請求の範囲によって定義された本発明の範囲内で様々な修正を行うことができることを理解されたい。
【図面の簡単な説明】
【図１】本発明によるレンダリング装置を含みレンダリング方法を実行する三次元図形レンダリングシステム構成のブロック図である。
【図２】本発明によるレンダリング装置および方法においてテクスチャのパターン・データを記憶するために使用されるマルチ解像度ピラミッド形データ構造を示す図である。
【図３Ａ】テクスチャ色値を使って画素の色値を直接計算する際、レンダリング・スクリーンの１つ画素に対応する参照バッファのセルのデータ構造を示す図である。
【図３Ｂ】テクスチャ色値を使って画素の色値を直接計算する際、レンダリング・スクリーンの１つ画素に対応する参照バッファのセルのデータ構造を示す図である。
【図４Ａ】  本発明による画像レンダリング方法を示す流れ図である。
【図４Ｂ】  本発明による画像レンダリング方法をより詳細に示す流れ図である。
【図５Ａ】  画像をレンダリングするためにロードまたは合成することによってパターン・データを獲得しなければならないタイルを示すサブルーチンの流れ図である。
【図５Ｂ】  テクスチャ画素がタイルの境界上にあるかどうかを判定し、もし境界上にある場合は、パターン・データを獲得しなければならない追加のタイルを示すサブルーチンの流れ図である。
【図６】  図５Ａに示したルーチンによって示されたタイルのパターン・データを獲得するためのサブルーチンの流れ図である。
【図７Ａ】  テクスチャ色値を補間して、最良解像度表示モードでレンダリング・スクリーンの画素の最終色値を生成するためのサブルーチンの流れ図である。
【図７Ｂ】  テクスチャ色値を補間して、漸進的解像度表示モードでレンダリング・スクリーンの画素の最終色値を生成するためのサブルーチンの流れ図である。
【符号の説明】
１００：レンダリング装置
１０２：コンピュータ
１０４：入出力ポート
１０６：ネットワーク
１０８：バス
１１２、１１４：メモリ
１１０：サーバ
１１６：ビデオ出力ポート
１２０：レンダリング・エンジン
１２２：レンダリングプログラム
１２４：画素・深さバッファ
１２６：参照バッファ
１３０：テクスチャ・データ・メモリ
１３２：ページ
１３３：最大層深さメモリ
１３４：ピラミッド形パターン・データ記憶機構
１３６：タイル・ロード・リスト
１３８：タイル・ピッチ・アレイ
１４０：タイル・ベース・アレイ
１５０：モニタ
【図１】
0004448210.tif 000004
【図２】
0004448210.tif 000005
【図３Ａ】
0004448210.tif 000006
【図３Ｂ】
0004448210.tif 000007
【図４Ａ】
0004448210.tif 000008
【図４Ｂ】
0004448210.tif 000009
【図５Ａ】
0004448210.tif 000010
【図５Ｂ】
0004448210.tif 000011
【図６】
0004448210.tif 000012
【図７Ａ】
0004448210.tif 000013
【図７Ｂ】
0004448210.tif 000014