(57)【要約】【課題】デジタル表示グラフィックスを生成する性能を改善することを目的とする。【解決手段】コンパイル中に、可能である場合には、プログラム可能カリングユニットの区間の境界が計算される。変数毎に、区間の境界は、コンパイル中に計算され、最適化されたカリングプログラムを生成するために、他のメタデータと共に境界が使用される。可能でない場合には、仮定が行われてもよく、仮定がコードをコンパイルするために使用されてもよい。仮定が無効であることがわかった場合、新たな仮定が行われてもよく、或る実施例では、コードは再コンパイルされてもよい。【選択図】図１
2011134326.tif 000002
【特許請求の範囲】
【請求項１】
実行前に、プログラム可能カリングユニットが決定可能な境界を有するか否かを決定し、
そうである場合、変数毎に、前記コードを通じてコンパイル時に前記境界をトラッキングすることを有する方法。
【請求項２】
スカラ命令を生成するために区間命令についての情報を使用することを含む、請求項１に記載の方法。
【請求項３】
データを使用することは、トラッキングされた区間の境界を使用することを含む、請求項２に記載の方法。
【請求項４】
前記境界がコンパイル時に決定できなかった場合、コンパイル時に前記区間の境界の仮定を行うことを含む、請求項１に記載の方法。
【請求項５】
１つ以上の境界を片側の境界に簡略化することを含む、請求項１に記載の方法。
【請求項６】
実行時に前記仮定を再評価することを含む、請求項４に記載の方法。
【請求項７】
前記仮定が有効であると決定された場合、前記コードを実行することを含む、請求項６に記載の方法。
【請求項８】
前記仮定が有効でないと決定された場合、新たな仮定を行い、前記新たな仮定で前記コードをコンパイルすることを含む、請求項６に記載の方法。
【請求項９】
前記新たな仮定が機能しない場合、区間の境界を使用せずに前記コードをコンパイルすることを含む、請求項８に記載の方法。
【請求項１０】
前記境界をトラッキングすることは、境界付きの演算を使用して命令を評価することを含む、請求項１に記載の方法。
【請求項１１】
境界付きの演算を使用して命令を評価することは、区間演算、アフィン演算又はテーラーの演算のうち１つを使用することを含む、請求項１０に記載の方法。
【請求項１２】
コンパイル中に、プログラム可能カリングユニットが計算可能な境界を有するか否かを決定し、
そうである場合、変数毎に、コンパイル中に前記コードを通じて前記境界をトラッキングする
ようにコンピュータにより実行される命令を格納したコンピュータ可読媒体。
【請求項１３】
スカラ命令を生成するために区間命令についての情報を使用する命令を更に格納した、請求項１２に記載の媒体。
【請求項１４】
データとして、トラッキングされた区間の境界を使用する命令を更に格納した、請求項１３に記載の媒体。
【請求項１５】
前記区間の境界がコンパイル時に計算できなかった場合、コンパイル時に前記区間の境界の仮定を行う命令を更に格納した、請求項１２に記載の媒体。
【請求項１６】
１つ以上の双方側の区間の境界を片側の区間の境界に簡略化する命令を更に格納した、請求項１２に記載の媒体。
【請求項１７】
実行時に前記仮定を再評価する命令を更に格納した、請求項１５に記載の媒体。
【請求項１８】
前記仮定が有効であると決定された場合、前記コードを実行する命令を更に格納した、請求項１７に記載の媒体。
【請求項１９】
前記仮定が有効でないと決定された場合、新たな仮定を行い、前記新たな仮定で前記コードをコンパイルする命令を更に格納した、請求項１７に記載の媒体。
【請求項２０】
前記新たな仮定が有効でない場合、区間の境界を使用せずに前記コードをコンパイルする命令を更に格納した、請求項１７に記載の媒体。
【請求項２１】
プログラム可能カリングユニットと、前記プログラム可能カリングユニットに結合されたコンパイラとを有する装置であって、
前記コンパイラは、前記プログラム可能カリングユニットが計算可能な境界を有するか否かを決定し、そうである場合、変数毎に、コンパイル中に前記コードを通じて前記境界をトラッキングする装置。
【請求項２２】
前記装置は、ディスプレイアダプタである、請求項２１に記載の装置。
【請求項２３】
前記コンパイラは、前記区間の境界が計算できなかった場合、コンパイル時に前記区間の境界の仮定を行う、請求項２１に記載の装置。
【請求項２４】
コントローラを含む、請求項２３に記載の装置。
【請求項２５】
前記コントローラは、実行時に前記仮定を再評価する、請求項２４に記載の装置。
【請求項２６】
前記コントローラは、前記仮定が有効であると決定された場合、前記コードを実行する、請求項２５に記載の装置。
【請求項２７】
前記コンパイラは、前記仮定が有効でないと決定された場合、新たな仮定を行い、前記新たな仮定で前記コードをコンパイルする、請求項２５に記載の装置。
【請求項２８】
前記コンパイラは、前記新たな仮定が有効でない場合、境界を使用せずに前記コードをコンパイルする、請求項２７に記載の装置。
【請求項２９】
前記コンパイラは、区間の命令についての情報を使用してスカラ命令を生成する、請求項２１に記載の装置。
【請求項３０】
前記コンパイラは、区間の境界を使用してスカラ命令を生成する、請求項２９に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概してデジタル表示グラフィックスに関し、特にデジタル表示グラフィックスを生成する性能の改善に関する。
【背景技術】
【０００２】
1980年代及び1990年代に、グラフィックアクセラレータを備えたコンピュータ及びゲームコンソールのディスプレイアダプタが現れ、グラフィック生成においける中央処理装置（CPU：Central  Processing  Unit）の負担を軽減している。まず、ディスプレイアダプタは2Dグラフィックスの高速化を提供してきたが、最終的には、3Dグラフィックスの高速化のサポートも含んでいる。現在のディスプレイアダプタは、グラフィック処理装置（GPU：graphics  processing  unit）としばしば呼ばれる処理装置を使用する。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
3Dグラフィックスの複雑性のため、GPUは、3Dグラフィックスに関する計算を実行するために、かなりの量の処理能力を使用する。常に、高フレームレート（１秒毎の処理されるスクリーン画像）、高解像度及び高画質を必要とする新たなアプリケーション及びゲームが存在するため、各スクリーン画像ができるだけ短い時間で処理されるという要件をもたらしている。換言すると、常に、性能を向上させることが重要である。
【０００４】
性能は、高クロック速度、パイプライン化又は並列計算の利用を可能にすることで、GPUの処理能力を増加させることにより、向上し得る。しかし、このことは、しばしば多くの熱を生成し、多くの電力消費及びGPUを冷却する高いファンの雑音を生じる。更に、各GPUのクロック速度に制限が存在する。
【０００５】
本発明は、デジタル表示グラフィックスを生成する性能を改善することを目的とする。
【課題を解決するための手段】
【０００６】
本発明の方法は、
実行前に、プログラム可能カリングユニットが決定可能な境界を有しているか否かを決定し、
そうである場合、変数毎に、前記コードを通じてコンパイル時に前記境界をトラッキングすることを有することを特徴とする。
【発明の効果】
【０００７】
本発明の実施例によれば、デジタル表示グラフィックスを生成する性能を改善することが可能になる。
【図面の簡単な説明】
【０００８】
【図１】本発明の実施例において異なるエンティティがディスプレイアダプタでどのように相互作用するかを示すブロック図
【図２】図１のディスプレイアダプタで使用される異なるプログラム間の関係を示す概略ブロック図
【図３】図１のディスプレイアダプタでタイルをカリングするために区間演算が使用可能である例
【図４ａ】図１のディスプレイアダプタで実行可能なカリング処理のフローチャート
【図４ｂ】図１のディスプレイアダプタで実行可能なカリング処理のフローチャート
【図５】図１のディスプレイアダプタを使用した典型的な汎用コンピュータの全体アーキテクチャ
【図６ａ】図１のディスプレイアダプタでの入力値の例外の場合を示すディスプレイ画面
【図６ｂ】図６ａの入力値を示すグラフ
【図７ａ】図１のディスプレイアダプタで使用可能なテクスチャの例示的な透視図
【図７ｂ】図１のディスプレイアダプタで使用可能なテクスチャの例示的な透視図
【図８ａ】図１のディスプレイアダプタで使用可能なテクスチャの例示的な画面
【図８ｂ】図１のディスプレイアダプタで使用可能なテクスチャの例示的な画面
【図８ｃ】図１のディスプレイアダプタで使用可能なテクスチャの例示的な画面
【図８ｄ】図１のディスプレイアダプタで使用可能なテクスチャの例示的な画面
【図９】一実施例のフローチャート
【発明を実施するための形態】
【０００９】
コンパイル中に、可能である場合には、プログラム可能カリングユニットの区間の境界が計算される。変数毎に、区間の境界は、コンパイル中に計算され、最適化されたカリングプログラムを生成するために、他のメタデータと共に境界が使用される。可能でない場合には、仮定が行われてもよく、仮定がコードをコンパイルするために使用されてもよい。仮定が無効であることがわかった場合、新たな仮定が行われてもよく、或る実施例では、コードは再コンパイルされてもよい。
【００１０】
図１を参照すると、ディスプレイアダプタ100は、図５に示す接続された中央処理装置（CPU：central  processing  unit）570により指示される通りに、ポリゴン（多角形）を設定する役目をするポリゴン設定ブロックを含んでもよい。如何なるポリゴンが使用されてもよいが、一般的に三角形が使用される。ポリゴン毎に、タイル・ラスタライザ（tile  rasterizer）104は、処理されるポリゴンを１つ以上のタイル（tile）に分割する。各タイルは、ポリゴンで少なくとも部分的に重なる。一般的に、タイルは、フラグメント（fragment）のグループである。一実施例では、タイルは、複数のフラグメントを含む２次元の矩形である。これらのフラグメントのそれぞれは、画素（ピクセル）に対応し、画素を処理するため及び画素がスクリーン上に処理されるべきか否かをテストするために必要な全てのデータを含む。タイルの一般的なサイズは8×8フラグメントであるが、如何なるタイルのサイズも本発明の範囲内にある。
【００１１】
階層的深さカリングブロック106は、深さのバッファリングに基づくカリング（culling）である階層的深さのカリング（hierarchical  depth  culling）を実行する。ここでは、タイルが深さのバッファの内容によりカバーされているか否かを証明するために、保守的なテスト（conservative  test）が実行されてもよい。換言すると、このテストは、ビューア（閲覧者）の観点から、タイルのポリゴンを完全にカバーする他の処理されたオブジェクトが存在するか否かを決定する。当てはまる場合には、全体のタイルがカリングされてもよい（すなわち、少ない処理のため選び出される、例えば、スキップされる）。このことは、或る実施例では性能の利得を生じ得る。階層的深さのカリングは、プログラム可能カリングユニット108のカリングの前又は後に実行されてもよい。このユニットは、固定的な機能でもよい。これは、一実施例では置換可能なプログラムを実行しないことを意味する。
【００１２】
プログラム可能カリングユニット108では、置換可能カリングモジュール（replaceable  culling  module）としても知られる置換可能カリングプログラム118に従ってカリングが実行される。このカリングプログラム118の詳細及びその効果は、以下に図４ａを参照して詳細に説明する。
【００１３】
フラグメント・ラスタライザ（fragment  rasterizer）110では、プログラム可能カリングユニット108により処理されたタイルは、ポリゴンに重なるフラグメントに分割される。これらのフラグメントのそれぞれは、画素に対応し、画素を処理するため及び画素がスクリーン上に処理されるべきか否かをテストするために必要なデータを含む。フラグメントデータは、ラスタ位置、深さ、色、テクスチャ座標、ステンシル、アルファ（混合に用いられる）等を含んでもよい。画素毎に、複数のフラグメントのサンプルが存在してもよい。
【００１４】
フラグメントプログラムユニット112では、フラグメント・ラスタライザから出力されたフラグメントは、フラグメントプログラム120を使用して処理される。このユニットの目的は、前に評価された色とテクスチャとの合成、ぼやけ（fog）のような効果の追加、可能な場合には処理される必要のないフラグメントの識別（すなわち、フラグメントのカリング）のようなタスクを実行することである。
【００１５】
テクスチャユニット114は、例えば、１次元、２次元、３次元、４次元及びキューブマップテクスチャ（cube  map  texture）を使用して、テクスチャを検索するために使用され、これらをプログラム可能カリングユニット108及びフラグメントプログラムユニット112に提供する。
【００１６】
混合／深さ／アルファユニット116は、フラグメントプログラムユニット112から提供されたフラグメントを使用し、フラグメントが目的のバッファに書き込まれる前に、深さのテスト、アルファのテスト及び混合を実行する。
【００１７】
図２に示す結合プログラム又はコンパイラプログラム222は、プログラム可能カリングユニット108で使用されるカリングプログラム118と、フラグメントプログラムユニット112で使用されるフラグメントプログラム120とを自動的に生成するために使用されてもよい。任意選択で、プログラマは、個々のカリング及びフラグメントプログラム118、120を記述してもよい。
【００１８】
一例として、元々はフラグメントプログラムとして使用するために記述された結合プログラム222の擬似コードセグメント(1)について検討する。
【００１９】
【数１】
2011134326.tif 000003
このプログラムは、DP3命令を使用した結果（d）への光（I）ベクトルと法線（n）ベクトル（normal  vector）との間のドット積を計算することによる基本的な拡散光を実行する。n及びIベクトルはフラグメント毎に変化する。KIL命令は、表面法線が光に直面していない全てのフラグメントを終了させる（dが0未満であることにより示される）。TEX2D命令は、cへの２次元テクスチャの検索を実行する。最後に、結果（d)が拡散物質係数（c）で乗算される。
【００２０】
KIL命令は、フラグメントの全体のタイルをカリングする機会である。しかし、これを行うためには、KIL命令の条件が全体のタイルで満たされていることが保守的に証明されていなければならない。この例では、DP3命令を保守的に評価することが可能でなければならない。この理由は、KIL命令はDP3命令の結果に依存するからである。更に、全体のタイルの入力（この場合では法線n及び光Iのベクトル）の保守的な境界を見つけることが可能でなければならない。この理由は、DP3命令はこれらの値に依存するからである。
【００２１】
この保守的な評価のチェーンを実施するために、プログラム可能カリングユニットは、フラグメントプログラムユニットと同じ命令セットに基づく。しかし、フラグメントを処理するときに一般的であるような、命令へのソース及び宛先レジスタとしての浮動小数点変数の代わりに、区間が使用され、命令は区間演算の原理を使用して実施される。簡単な例として、標準的なADD命令について検討する。
【００２２】
【数２】
2011134326.tif 000004
対応するプログラム可能カリングユニットの区間命令では、オペランドは、区間
【００２３】
【数３】
2011134326.tif 000005
により置換される。例えば、区間
【００２４】
【数４】
2011134326.tif 000006
は、以下のように定義される。
【００２５】
【数５】
2011134326.tif 000007
プログラム可能カリングユニットのADD命令は、以下のようになる。
【００２６】
【数６】
2011134326.tif 000008
ただし、区間加算演算は、以下のように実施される。
【００２７】
【数７】
2011134326.tif 000009
以上のように、区間加算の結果は、“法線（normal）”の加算の全ての可能な結果を含む。或いは、より正式には、
【００２８】
【数８】
2011134326.tif 000010
及び
【００２９】
【数９】
2011134326.tif 000011
を前提として、
【００３０】
【数１０】
2011134326.tif 000012
が当てはまる。従って、これは保守的に正確である。同様に、フラグメントプログラム命令セットの各命令の動作が再定義される。
【００３１】
区間命令の使用に加えて、入力も区間として定義されてもよい。従って、フラグメントの全体のタイルで補間された量の保守的な境界を計算することが可能でなければならない。ここでは区間演算が使用されるが、全体のタイルを表す如何なる適切な演算が使用されてもよい点に留意すべきである。例えば、本発明の範囲内で、アフィン演算又はテーラーの演算が同様に使用されてもよい。
【００３２】
前述の理由で、カリングプログラム118は、結合プログラム(1)から自動的に導かれ得る。導かれたカリングプログラムは以下のようになる。
【００３３】
【数１１】
2011134326.tif 000013
更に、ここでは、フラグメントプログラム120が、結合プログラム220と同じように結合プログラム(1)から導かれる。フラグメントプログラムは以下のようになる。
【００３４】
【数１２】
2011134326.tif 000014
フラグメントの全体のタイルで、図３に示すように、その法線330の入力区間334が
【００３５】
【数１３】
2011134326.tif 000015
であり、
その光ベクトル332の区間336が
【００３６】
【数１４】
2011134326.tif 000016
であることが決定されたことを想定する。z座標は0であると想定する。これにより、この例が簡単になる。これらの区間表現の間のドット積は、
【００３７】
【数１５】
2011134326.tif 000017
になる。従って、
【００３８】
【数１６】
2011134326.tif 000018
は、せいぜい
【００３９】
【数１７】
2011134326.tif 000019
になり得ることが結論付けられ得る。この値は完全に0未満であるため、図２を参照して前述したカリングプログラムでは、この全体のタイルは、以下に図４ａを参照して詳細に説明するように、各フラグメントのフラグメントプログラムを実行することなくカリングされ得る。これは、本発明の或る実施例における性能の利得の源である。
【００４０】
図４ａは、図１のディスプレイアダプタ100で実行され得るカリング処理のフローチャートを示している。この処理が開始すると、処理されるポリゴンが選択される。処理するタイルを選択するステップ440において、タイルが選択される。選択されたタイルは、ポリゴンで少なくとも部分的に重なる。次に、カリングプログラムを実行するステップ452において、カリングプログラムが実行される。
【００４１】
この実施例では、カリングプログラムが入力値を要求すると、処理は、カリングプログラムに入力値を提供するステップ454aに続く。入力値は、何らかの方法でタイルの全てのフラグメントを表す特性に関する値である。例えば、入力値は、法線、位置座標、光ベクトル、色、テクスチャ座標等でもよい。この実施例では、要求された入力値は、区間演算を使用して計算される。換言すると、入力値は、図４ｂを参照して説明する‘プッシュ’機構ではなく、‘プル’機構に従って必要な場合にのみ計算される。カリングプログラムの結果は、現在処理されているタイルがカリングされるべきであるか否かである。これは、厳密に決定されてもよい。これにより、タイルの領域において、現在のポリゴンが最終的に処理される画像に全く寄与しない場合にのみ、タイルがカリングされる。或いは、不可逆カリング（lossy  culling）が実行されてもよい。これにより、タイルの領域において、最終的に処理される画像への現在のポリゴンの寄与が特定の閾値より下である場合に、タイルがカリングされる。
【００４２】
カリングプログラムが処理を終了すると、処理は、カリング条件の真の条件判断のステップ456に続く。このステップにおいて、カリングプログラムの出力に従って、現在処理されているタイルでカリングが実行されるべきか否かが決定される。カリングが実行される場合、処理は、命令セットAを実行するステップ460に続く。そうでない場合、処理は、命令セットBを実行するステップ460に続く。一実施例では、カリング条件が偽である場合、タイルは、複数の小さいタイルに分割され、処理は、処理するタイルを選択するステップ440に戻る。これは、更に小さいタイルに対して連続的に繰り返され、階層的な多レベルのカリング処理を実施してもよい。
【００４３】
カリングプログラムはまた、カリング条件以外の結果を出力してもよい。これらの結果は、更なる処理のためにグラフィックスのパイプラインを後退（send  down）させてもよい。このような実施例の例は、階層的深さカリングユニット106（図１）及びプログラム可能カリングユニット108（図１）の順序を逆にすることを含む。プログラム可能カリングユニットは、タイルにおける深さの値の境界又は区間を計算し、この区間は、階層的深さカリングユニットに送信される。階層的深さカリングユニットは、プログラムにより計算された深さの値に基づいてカリングを実行する。
【００４４】
命令セットAを実行するステップ458において、タイルの一部（典型的にはフラグメントの一部）について命令セットAが実行される。典型的には、フラグメントは、処理される三角形に重なるタイルの全ての画素を併せてカバーする。
【００４５】
命令セットBを実行するステップ460において、タイルの一部（典型的にはフラグメントの一部）について命令セットBが実行される。典型的には、これは、タイルの段階の後のフラグメントの処理の通常処理である。
【００４６】
典型的には、命令セットAは、命令セットBより要求が低く、カリング条件が真であると決定されたときに、タイルについて処理される命令数の低減を生じる。その結果、性能の向上を生じる。一実施例では、命令セットAは空であり、かなりの処理の低減（すなわち、性能の向上）をもたらす。ステップ462においてタイルが存在しなくなるまで、フローは続く。
【００４７】
図４ｂは、図４ａを参照して説明した処理と基本的に同様の処理を示している。処理するタイルを選択するステップ440、カリングプログラムを実行するステップ452、カリング条件の真の条件判断のステップ456、命令セットAを実行するステップ458、命令セットBを実行するステップ460及び更なるタイルの条件判断のステップ462は、全て図４ａの対応するステップと同等である。
【００４８】
しかし、入力値をカリングプログラムに提供するステップ454bは、ここでは、カリングプログラムが実行される前に処理される。このステップにおいて、この実施例では区間演算を使用して、全ての関係する入力値が計算され、カリングプログラムがこれらの値にアクセスできるように提供される。これは、入力値の計算に対するプッシュ’機構を実装する。
【００４９】
図５は、図１のディスプレイアダプタを使用した典型的な汎用コンピュータ583の全体アーキテクチャを示している。コンピュータは、ソフトウェア命令を実行可能なコントローラ570（CPU等）を有する。コントローラ570は、揮発性メモリ571（ダイナミックランダムアクセスメモリ（RAM）等）と、ディスプレイアダプタ500とに接続されている。或る実施例では、ディスプレイアダプタ500は、図１のディスプレイアダプタ100と同じでもよい。次に、ディスプレイアダプタ500は、ディスプレイ576（モニタ等）に接続されている。コントローラ570は、固定記憶装置573（ハードドライブ又はフラッシュメモリ等）と、光学的記憶装置574（CD、DVD、HD-DVD又はBlu-rayのような光学的媒体のリーダ及び／又はライタ等）にも接続されている。ネットワークインタフェース581も、ネットワーク582（ローカルエリアネットワーク、広域ネットワーク（例えばインターネット）、無線ローカルエリアネットワーク又は無線メトロポリタンエリアネットワーク等）へのアクセスを提供するため、コントローラ570に接続されている。周辺機器インタフェース577を通じて、CPU570は、マウス578、キーボード579又は他の周辺機器（ジョイスティック、プリンタ、スキャナ等を含む）と通信することができる。
【００５０】
本発明を具現するために汎用コンピュータが前述されているが、本発明は、デジタルグラフィックス（特に3Dグラフィックス）が利用される如何なる環境（例えば、ゲームコンソール、移動電話、モバイルインターネット装置（MID：mobile  Internet  device）、MP3プレイヤ等）にも同様に具現され得る点に留意すべきである。如何なるコンピュータアーキテクチャが使用されてもよい。
【００５１】
前述の命令セットの１つの実装では、入力値は、区間演算を使用して計算されてもよい。カリングプログラムは、フラグメントの全体のタイルで実行されてもよい。しかし、これを行うために、変化する（又は補間された）入力の境界区間（bounding  interval）も計算される必要がある。
【００５２】
まず、変化する属性の値は、補間を使用してタイルの全ての四隅で計算される。次に、これらの４つの値の境界区間が計算され、以下のように呼ばれる。
【００５３】
【数１８】
2011134326.tif 000020
三角形の頂点における変化する属性の境界区間も計算され、以下のように呼ばれる。
【００５４】
【数１９】
2011134326.tif 000021
タイルでの変化する属性の最終的な境界区間は、以下のように計算可能である。
【００５５】
【数２０】
2011134326.tif 000022
例えば、タイルに重なる全てのフラグメントを考慮することによる、区間を計算する他の方法も存在する。
【００５６】
最終的に、図６ａに示す例外の場合が処理されてもよい。ここでは、三角形685での透視的に正確な補間（perspective  correct  interpolation）がチェッカーボードのテクスチャ686の形式で示されている。理解できるように、テクスチャは投影線687で鏡映されている。投影線687は、無限に大きい場合に三角形685の水平線が投影される線である。この鏡映効果は、透視的に正確な補間で使用される分割により生じる逆投影の形式である。ここで、何らかの変化する属性の境界区間が、投影線に重なるタイル688で計算されることが望まれる。
【００５７】
図６ｂは、透視的に正確な補間関数690と、タイル688の四隅が補間されるときに取得される値691a-dとを示している。これらの四隅の境界区間692は明らかに不正確である。この理由は、この関数が投影線で無限大に近づくときに、この境界区間はこの区間での関数690の全ての値を含まないからである。
【００５８】
この例外の場合は、投影線に重なるタイルの境界区間として
【００５９】
【数２１】
2011134326.tif 000023
を
【００６０】
【数２２】
2011134326.tif 000024
に設定することにより処理されてもよい。この実施例では、三角形に実際に重なるタイルのみが横断し、透視的に正確な重心座標が補間を行うために使用される。
【００６１】
タイルの隅について透視的に正確な重心座標を計算するときに、問題のあるタイルは容易に検出可能である。透視的に正確な重心座標は、有理関数として表現され、いずれかのタイルの隅について分母がゼロ未満である場合、タイルは投影線を横断する。
【００６２】
N次元のテクスチャの検索は以下のように実行される。一般的な概念は、所与の領域でのテクスチャデータの境界区間を計算する高速且つ効率的な手段を提供することにある。この例の残りは、２次元のテクスチャのみを検討するが、一般化は容易である。
【００６３】
まず、区間に基づくテクスチャの検索の対象となる各テクスチャの２つのミップマップ・ピラミッド（mipmap  pyramid）を計算する。図７ａ及び７ｂに示すように、各要素（例えば、ミップマップの要素793）は、図７ａに示すようにピラミッドにおけるそのすぐ下の４つの対応するテクセル（texel）（例えば、要素794a-d）の成分毎の最小値、又は図７ｂに示すように成分毎の最大値として計算される。最終結果は、境界区間のミップマップ・ピラミッドとして認識されてもよい。この種類の事前計算は、標準的なミップマップが自動生成される方法と同様にして、ドライバにより容易に扱われ得る。
【００６４】
テクスチャの検索を実行するときに、テクスチャ座標区間である、軸に整列した境界ボックスでのテクスチャデータの境界区間を計算することを考える。まず、以下のように適切なミップマップレベルを計算する。
【００６５】
【数２３】
2011134326.tif 000025
ただし、
【００６６】
【数２４】
2011134326.tif 000026
は、正規化されていない整数テクスチャ座標（すなわち、これらはテクスチャの次元を含む）の２次元区間である。これらは、
【００６７】
【数２５】
2011134326.tif 000027
がi∈{x,y}について切り捨てられ、
【００６８】
【数２６】
2011134326.tif 000028
が切り上げられるように概数で表される。
【００６９】
このミップマップレベルに変換されるときに、tは如何なる次元においても１つのテクセル幅より大きくならず、最も大きい次元において1/2テクセルである。従って、図８ａ〜ｄに示すように、テクスチャ座標区間の４つの可能な場合を得る。通常の線形補間に使用されるアクセス方式では、
【００７０】
【数２７】
2011134326.tif 000029
の左下隅のテクセルを有するテクセル796から2×2のテクセルの正方形を常にサンプリングする。テクスチャの検索の結果は、テクスチャ座標区間に実際に重なるテクセルの色の境界として計算される。すなわち、図８ａ〜ｃの参照符号795で示される斜線のテクセルを破棄する。ミップマップ変換されたtは、最も近い整数座標に概算されるため、この重複のテストは、単に最終ビットを比較することにより、非常に効率的に実施され得る。基本的には、テクスチャの検索処理は、通常の“３本線（trilinearly）の”フィルタリングされたテクスチャの検索と同じくらい高コストである。最大の違いは、２つの隣接するレベルではなく、２つの異なるミップマップ・ピラミッドにおける同じレベルからサンプリングする必要がある点であり、線形補間を使用するのではなく、境界として最終結果を計算する点である。この方式は、クランプ（clamp）、繰り返し及び鏡映繰り返し（mirrored  repeat）のような異なる種類のラッピングモード（wrapping  mode）を固有にサポートする。適切なラッピングモードは、ミップマップレベルの計算の後に単に区間座標に適用され、予想結果を取得してもよい。
【００７１】
一実施例では、カリングプログラムで実際に使用されるミップマップレベルのみが生成されてもよい。この最適化は、例えば順番に依存しない透明処理（order  independent  transparency）のようなスクリーン空間で行われるアルゴリズムにとって特に重要である。この場合、基準レベルのテクスチャ及びスクリーン上のタイルに対応するミップマップレベルのみを必要としていることを事前に認識している。最小及び最大の深さの値は、例えば、階層的深さカリングユニットに存在してもよい。また、最小及び最大の色が圧縮目的で既に計算されている可能性もあり（しかし、可能性は小さい）、そうでない場合、これらを計算する必要がある。
【００７２】
最小／最大のミップマップ・ピラミッドは、２次元のテクスチャと同じ手法を使用して、キューブマップについて計算される。エッジでは、ミップマップの色は、エッジの双方側の４つのテクセルの最小値又は最大値として計算され、隅では、ミップマップの色は、その隅から発散する全ての３つの側での４つのテクセルの最小値又は最大値と結合される。従って、エッジの反対側のテクセルは、高いミップマップレベルで同じ色を共有する。同様に、隅の３つのテクセルも共通の色を共有する。
【００７３】
このミップマップ・ピラミッドは、キューブの一方側のみにアクセスして、保守的なキューブマップの検索を行うために使用されてもよい。まず、主軸の区間に基づく等価なものを計算する。テクスチャ座標区間を
【００７４】
【数２８】
2011134326.tif 000030
としたとき、
【００７５】
【数２９】
2011134326.tif 000031
と
【００７６】
【数３０】
2011134326.tif 000032
とが同じ符号を有し、
【００７７】
【数３１】
2011134326.tif 000033
が最大化される軸として、主軸iを定義する。
【００７８】
【数３２】
2011134326.tif 000034
と
【００７９】
【数３３】
2011134326.tif 000035
とが全ての軸で異なる符号を有する場合、主軸は見つからない。しかし、これは、原点がテクスチャ座標区間内にある場合にのみ生じ得る。この場合、テクスチャ座標区間は、全体のキューブマップに投影する。これは、最高のミップマップレベルを選択し、任意のキューブマップ面をサンプリングすることにより処理されてもよい。
【００８０】
主軸が見つかると、テクスチャ座標区間は、キューブマップの対応する側に投影される。投影は、２つの残りの軸のそれぞれの境界を別々に投影することにより行われる。xが主軸であり、yが境界を投影したいと思う軸である例について検討する。境界を計算するために投影しなければならない極値点及びテクスチャ座標区間の６つの可能な場合が存在する（区間はy軸を横断しない点に留意すべきである。この理由は、この場合にはx軸が主軸ではないからである）。テクスチャ座標区間の符号を調べ、参照テーブルを通じて極値点を取得すれば十分である。
【００８１】
極値点は、残りの２つの軸について投影され、２次元投影された座標区間を形成する。この区間は、前述の２次元の場合について説明した方法と同様に、ミップマップレベルを計算し、２次元テクスチャ検索を実行するために使用される。
【００８２】
性能の改善のために、カリングのシェーダー（cull  shader）で行われる作業量を低減し、計算された境界の堅さ（tightness）を増加させることが望ましい。一般的に、最適化されたスカラ命令を生成するために、区間命令についてのメタデータが使用される。メタデータは区間の境界でもよく、境界のどちらの側が必要であるかについての情報でもよく、どのような動作が実行されるべきかについてのハイレベルな情報でもよい。例えば、乗算の代わりに２乗が実行されるべきか否かについての情報は、最適化されたスカラ命令を生成するために使用可能なメタデータの種類の例である。次に、境界は、コンパイル時にコードを通じてトラッキング（track）され、変数毎及び命令毎の境界を計算してもよい。これらの境界は、コードをより効率的にすることを可能にする。
【００８３】
従って、図９のブロック910において、カリングプログラム118が受信され、静的な入力境界の分析を受ける。一実施例では、境界は、アプリケーションプログラムインタフェース標準に基づいてもよい。
【００８４】
このような標準の一例は、特定の種類の入力の予想値を含む。境界はまた、制約、変数の種類、データの種類に基づいてもよい。例えば、変数の種類は、正の符号なし整数でもよい。データの種類は、ゼロと１との間の範囲内でなければならない値でもよい。これらの境界は、正確であることが知られている。このような境界が存在しない場合、境界は、プラス及びマイナスの無限大でもよい。
【００８５】
これらの境界は、コンパイル時に区間毎にカリングプログラムを評価し、変数毎に可能な境界を決定するために使用されてもよい。コンパイル時の境界を制限するために、既知の数学的結果が適用されてもよい。数例として、絶対値が常に正であり、サイン及びコサインが-1と1との間の範囲にあり、クランプ演算が可能な値の範囲を制限するという事実を含む。従って、コードは、区間の範囲内でコンパイル時に実行されてもよい。結果は、カリングプログラムの命令毎の有効な値の範囲である。
【００８６】
集められた区間は、より効率的な区間演算評価コードを生成するために低レベルで使用されてもよい。より効率的な区間演算評価コードは、或る実施例では実行時の性能を改善し得る。例えば、区間乗算における２つのオペランドが負ではないということを認識することは、実行時の区間評価のコストを10の命令から2つのみの命令に低減する。従って、このコンパイル時の分析は、カリングプログラムの長さを低減し、性能を改善し得る。静的な入力境界の分析は、入力境界と共に、区間の中間表現を提供する。
【００８７】
無限大ではない境界が決定できず、プラス及びマイナスの無限大の初期設定の境界が使用されたとしても、“無限大”の境界をトラッキングすることに依然として利点が存在し得る。実際には、カリングプログラムは１つ以上の入力を有する。これらの入力の全て又は一部について、より厳しい境界が或る場合に決定されてもよい。例えば、y=sin(x)であり、xがカリングプログラムへの入力であることを検討する。プラス及びマイナス無限大の間にx以外の境界が使用されない場合、コードを通じてこの境界をトラッキングすることが依然として有用になり得る。例えば、sin(x)の出力は、常に範囲[-1,1]の範囲内に制限される。この範囲は、プログラムの他の演算を簡単にするためにトラッキングされてもよい。
【００８８】
或る実施例では、ブロック912における動的な入力境界の仮定が使用されてもよい。これは、性能を改善するために特定領域の知識に基づく仮定の使用を含む。例えば、特定領域の知識は、テクスチャが通常では0〜1の範囲にあるという事実を含んでもよい。動的な仮定は、静的な境界を更に改良するために行われてもよい。
【００８９】
一例として、テクスチャの読み取り結果は、一般的にはコンパイル時に全く未知でもよい。しかし、ほとんどのテクスチャは符号なしの正規化された値として格納されるため、値が0と1との範囲内にあるという仮定を行うことが合理的である。或る実施例では、シェーダーのコンパイラは、入力フォーマットに基づいて合理的な仮定を自動的に行い、高速なカリングプログラムを生成するためにこの情報を使用してもよい。高速なコードのパスは、実際に入力が仮定された範囲内にある限り有効である。
【００９０】
しかし、例えば浮動小数点面がシェーダーに対して行われることになった場合、ゼロから１の範囲の仮定は違反する可能性がある。実行時に、シェーダー実行機構は、誤った仮定を認識し、訂正したカリングのシェーダーを要求してもよい。これは、望ましい場合には、訂正されたものが利用可能になるまで、その特定のシェーダーのカリングをスキップすることにより、非同期的に行われてもよい。複数のステップでデグラデーション（規模縮小）が実行されてもよい。テクスチャの場合、浮動小数点のような表現が負の値を表し得るとしても、ほとんどの画像は負でない値のみを含む。ゼロから１の範囲を違反することは、データが少なくともゼロと無限大とにより束縛されることを意味し、これは依然として全てが未知のデータであるものより性能上の利点を提供する。
【００９１】
動的な入力境界の仮定からの出力は、同様に、区間の中間表現と、或る実施例では動的な入力境界の仮定により補われた入力境界とである。
【００９２】
ブロック914において、境界は、変数毎の境界を計算するために、コンパイル時にコードを通じてトラッキングされる。これらの境界は、より効率的なコードを生成することを可能にする。コードはコンパイル時に実行され、各命令は、可能な入力及び出力の範囲を決定するために分析される。この処理は、静的な動的な入力境界の開始で始まり、前方に広める。
【００９３】
ブロック914の出力は、区間の中間表現と、命令毎の境界とである。ブロック916において、或る実施例では、片側の境界について最適化が行われてもよい。或る場合には、結果の上限境界又は下限境界のみが必要である。命令は、片側としての出力を生成するようにタグ付けされてもよい。この片側のタグは、可能な限り情報を後方に広める。
【００９４】
ブロック916の出力は、区間の中間表現と、境界と、側面情報（下、上、又は下と上との双方）とである。
【００９５】
次に、ブロック918において、区間の中間表現は、最適化されたスカラ中間表現に変換される。境界情報及び側面情報は、それぞれの区間命令を最適化されたスカラ命令のシーケンスに置換するために使用されてもよい。従って、それぞれの区間命令をスカラ命令の一般的なシーケンスにより単純に置換する代わりに、スカラ命令によりサポートされる程度を制限するために、境界が使用されてもよい。例えば、区間乗算の入力範囲が厳密に負でないことが分かっている場合、命令は、負でない数でのみ動作するように最適化されたスカラ命令の短いシーケンスにより置換されてもよい。
【００９６】
最後に、ブロック920において、スカラ中間表現は、無効コードの除去、ベクトル化及びコード生成のような標準的なコンパイラの最適化に使用される。実行可能コードは、ブロック920の後に出力され、フローはコンパイル時から実行時に遷移する。
【００９７】
実行時に、ブロック926に示すように、動的な仮定が再評価される。928で決定された仮定が有効である場合、ブロック930に示すように、カリングプログラムが実行されてもよい。
【００９８】
そうでない場合、様々な選択肢が検討されてもよい。例えば、カリングが実行されないことが決定されてもよい。或いは、より一般的な仮定を備えた新たなカリングプログラムが要求されてもよい。更に他の選択肢として、ブロック932に示すように、より一般的な仮定で予めコンパイルされたカリングプログラムが実行されてもよい。複数の予めコンパイルされたプログラムが存在する場合には、現在の仮定を満たす最も制限のある入力の仮定を有するものが選択されてもよい。
【００９９】
或る実施例では、アフィン演算又はテーラーの演算のような他の境界のある演算が使用されてもよい。これらの場合、入力／出力境界は、選択された演算に適した高次元の表現により置換されてもよい。
【０１００】
或る実施例では、図９に示すシーケンスは、ソフトウェアにより実施されてもよい。このような場合、シーケンスは、コンピュータ可読媒体に格納された命令に具現されてもよい。その媒体は、例えば、半導体記憶装置、光学記憶装置又は磁気記憶装置でもよい。命令は、コントローラ又はプロセッサを含むコンピュータにより実行される。例えば、コントローラ及びプロセッサは、図５のCPU570又はディスプレイアダプタ500の一部でもよい。命令を格納する記憶装置は、例えば、メモリ571又は記憶装置573若しくは574でもよい。
【０１０１】
ここに記載したグラフィック処理技術は、様々なハードウェアアーキテクチャで実施されてもよい。例えば、グラフィック機能は、チップセット内に統合されてもよい。或いは、別個のグラフィックプロセッサが使用されてもよい。更に他の実施例として、グラフィック機能は、複数コアプロセッサを含む汎用プロセッサにより実施されてもよい。
【０１０２】
この明細書を通じて“一実施例”又は“実施例”に言及することは、実施例に関して記載した特定の機能、構造又は特徴が本発明に含まれる少なくとも１つの実装に含まれることを意味する。従って、“一実施例”又は“実施例”という用語が現れることは、必ずしも同じ実施例を示すとは限らない。更に、特定の機能、構造又は特徴は、図示の特定の実施例以外の他の適切な形式で実施されてもよく、全てのこのような形式は、本願の特許請求の範囲内に含まれ得る。
【０１０３】
本発明について限られた数の実施例に関して説明したが、当業者はこれから複数の変更及び変形を認識する。特許請求の範囲は、本発明の真の要旨及び範囲内に入るこのような変更及び変形をカバーすることを意図する。
【符号の説明】
【０１０４】
100  ディスプレイアダプタ
102  ポリゴン設定
104  タイル・ラスタライザ
106  階層的深さカリングブロック
108  プログラム可能カリングユニット
110  フラグメント・ラスタライザ
112  フラグメントプログラムユニット
114  テクスチャユニット
116  混合／深さ／アルファユニット
118  カリングプログラム
120  フラグメントプログラム
【図１】
2011134326.tif 000036
【図２】
2011134326.tif 000037
【図３】
2011134326.tif 000038
【図４ａ】
2011134326.tif 000039
【図４ｂ】
2011134326.tif 000040
【図５】
2011134326.tif 000041
【図６ａ】
2011134326.tif 000042
【図６ｂ】
2011134326.tif 000043
【図７ａ】
2011134326.tif 000044
【図７ｂ】
2011134326.tif 000045
【図８ａ】
2011134326.tif 000046
【図８ｂ】
2011134326.tif 000047
【図８ｃ】
2011134326.tif 000048
【図８ｄ】
2011134326.tif 000049
【図９】
2011134326.tif 000050