(57)【要約】      （修正有）【課題】グラフィックスパイプラインのラスタステージにおいて、開始タイルのラスタライズを加速する方法を提供する。【解決手段】本方法は、生成された画像をクリップするウィンドウを画成するステップと、グラフィックスプロセッサのラスタステージでラスタライズするためのグラフィックスプリミティブを受け取るステップと、を含む。ウィンドウに関連する２分探索を実行して、グラフィックスプリミティブの少なくとも部分的なカバー範囲を有する開始タイルを決定する。開始タイルは複数のピクセルを含む。開始タイルに基づいて、ラスタステージは、グラフィックスプリミティブの少なくとも部分的なカバー範囲を有する複数の隣接タイルを生成することによって、グラフィックスプリミティブをラスタライズする。【選択図】図７
2008102904.tif 000002
【特許請求の範囲】
【請求項１】
グラフィックスプリミティブを含むポリゴン記述を生成するセットアップユニットと、
前記セットアップユニットへ結合されたラスタユニットであって、前記グラフィックスプリミティブをラスタライズする該ラスタユニットと、
を備え、
前記ラスタユニットが、クリッピングウィンドウに関連する２分探索を実行して、前記グラフィックスプリミティブの少なくとも部分的なカバー範囲を有する開始タイルであって複数のピクセルを含む該開始タイルを決定し、前記ラスタユニットが、前記開始タイルに基づいて、前記グラフィックスプリミティブの少なくとも部分的なカバー範囲を有する複数の隣接タイルを生成することによって、前記グラフィックスプリミティブをラスタライズする、グラフィックスプロセッサユニット。
【請求項２】
前記グラフィックスプリミティブの一部分が前記ウィンドウの外側に存在する、請求項１に記載のグラフィックスプロセッサユニット。
【請求項３】
前記２分探索が、前記ウィンドウの第１のエッジ上で実行され、続いて前記ウィンドウの第２のエッジ上で実行される、請求項１に記載のグラフィックスプロセッサユニット。
【請求項４】
前記ラスタステージ内にあって、前記２分探索を実施するステッパユニットを更に備える、請求項１に記載のグラフィックスプロセッサユニット。
【請求項５】
前記ステッパユニットが、前記グラフィックスプリミティブの前の一部分の同時実行可能なラスタライズと重複するように前記２分探索を並列に実行する、請求項４に記載のグラフィックスプロセッサユニット。
【請求項６】
粗いラスタユニットと、
微細なラスタユニットと、
を更に備え、
前記ステッパユニットが、前記粗いラスタユニット内に実装され、前記微細なラスタユニットが、第２レベルのラスタライズを実行して、前記グラフィックスプリミティブを少なくとも部分的にカバーする複数のタイルから、カバーされたピクセルを決定する、請求項５に記載のグラフィックスプロセッサユニット。
【請求項７】
システムメモリと、
前記システムメモリへ結合された中央プロセッサユニットと、
前記中央プロセッサユニットへ通信可能に結合されたグラフィックスプロセッサユニットと、
グラフィックスプリミティブを含むポリゴン記述を生成するセットアップユニットと、
前記セットアップユニットへ結合されたラスタユニットであって、前記グラフィックスプリミティブをラスタライズする該ラスタユニットと、
を備え、
前記ラスタユニットが、クリッピングウィンドウに関連する２分探索を実行して、前記グラフィックスプリミティブの少なくとも部分的なカバー範囲を有する開始タイルであって複数のピクセルを含む該開始タイルを決定し、前記ラスタユニットが、前記開始タイルに基づいて、前記グラフィックスプリミティブの少なくとも部分的なカバー範囲を有する複数の隣接タイルを生成することによって、前記グラフィックスプリミティブをラスタライズする、
コンピュータシステム。
【請求項８】
前記グラフィックスプリミティブの一部分が前記ウィンドウの外側に存在する、請求項７に記載のコンピュータシステム。
【請求項９】
前記２分探索が前記ウィンドウの第１のエッジ上で実行され、続いて前記ウィンドウの第２のエッジ上で実行される、請求項８に記載のコンピュータシステム。
【請求項１０】
前記ラスタステージ内にあるステッパユニットであって、前記２分探索を実施する該ステッパユニットを更に備え、
前記２分探索が、前記グラフィックスプリミティブの前の部分の同時実行可能なラスタライズと重複して並列に実行される、請求項９に記載のコンピュータシステム。
【請求項１１】
粗いラスタユニットと、
微細なラスタユニットと、
を更に備え、
前記ステッパユニットが、前記粗いラスタユニット内に実装され、前記微細なラスタユニットが、第２レベルのラスタライズを実行して、前記グラフィックスプリミティブを少なくとも部分的にカバーする複数のタイルから、カバーされたピクセルを決定する、請求項１０に記載のコンピュータシステム。
【発明の詳細な説明】
【発明の分野】
【０００１】
[001]本発明は、広く、ハードウェア加速型のグラフィックスコンピュータシステムに関するものである。
【発明の背景】
【０００２】
[002]コンピュータ性能の最近の進歩によって、グラフィックシステムは、パーソナルコンピュータ、ホームビデオゲームコンピュータ、ハンドヘルドデバイス等を使用して、一層現実的なグラフィカル画像を提供することが可能になってきた。このようなグラフィックシステムでは、多数の手続きを実行して、グラフィックプリミティブをシステムスクリーンへ「レンダリング」、即ち描画する。「グラフィックプリミティブ」は、グラフィックピクチャの基本的成分、例えば、頂点、ポリゴン等である。レンダリングされる画像は、これらのグラフィックプリミティブの組み合わせで形成される。多くの手続きを利用して、３Ｄグラフィックスレンダリングを実行することもある。
【０００３】
[003]特化されたグラフィックス処理ユニット（例えば、ＧＰＵ（グラフィックスプロセッサユニット）等）が、グラフィックスレンダリング手続きを実行する際に要求される計算を最適化するために、開発されてきている。ＧＰＵは、高速演算を目的として構成されており、典型的には、一つ以上のレンダリングパイプラインを組み込んでいる。各パイプラインは、多数のハードウェアベースの機能ユニットを含む。これらの機能ユニットは、グラフィックス命令／データの高速実行用に最適化されている。この場合に、命令／データは、パイプラインのフロントエンドへ供給され、計算結果はパイプラインのバックエンドに出願する。ＧＰＵのハードウェアベース機能ユニット、キャッシュメモリ、ファームウェア等は、低レベルグラフィックスプリミティブ（例えば、「点」、「線」、「三角形」等を含む）について演算を行ない、レンダリングされたリアルタイム３Ｄ画像を作り出すように最適化されている。
【０００４】
[004]レンダリングされたリアルタイム３Ｄ画像は、ラスタ表示技術を使用して生成される。ラスタ表示技術は、コンピュータグラフィックスシステムで広く使用されており、一般的には、グラフィックスプリミティブによって、画像を構成する格子状の複数のピクセルに影響を与えるメカニズムを意味する。各プリミティブについて、典型的なラスタライズシステムは、一般的に、ピクセルからピクセルへ進み、そのプリミティブの寄与に応じて、「レンダリング」すべきか否か、即ち、所与のピクセルをフレームバッファ又はピクセルマップへ書き込むべきか否かを決定する。これは、次に、各ピクセルを表現する表示バッファへ、どのようにデータを書き込むかを決定する。
【０００５】
[005]プリミティブ内にある全てのピクセルをカバーするように、ピクセルからピクセルへと移動するための種々の探索アルゴリズムが開発されてきている。探索アルゴリズムは、クリッピングウィンドウを考慮する必要がある。このクリッピングウィンドウ内で、画像を構成するプリミティブがレンダリングされる。
【０００６】
[006]一般的に、クリッピングウィンドウは、画像の可視領域を表すために使用されるデータ構造（三角形のデータ構造、ウィンドウクリッププレーン、等）を有する。ＧＰＵは、グラフィックプリミティブを適切にクリップするために、クリッピング情報を維持するための専用のハードウェア及び／又はソフトウェアを有する。視処理（Viewing）、投射（Perspective)、及びクリッピングのステージは、受け取った各ポリゴンの頂点及び稜線に対する多くの算術演算を必要とする。
【０００７】
[007]クリッピングウィンドウ内に部分的にのみ存在するプリミティブをラスタライズする場合に、問題が存在する。典型的な従来技術の解決法は、プリミティブを単一方向にラスタライズして、カバーされたピクセルを生成することを伴う。このような従来技術の単一方向の解決法は、一定の方向においてラインごとにピクセルを生成することを伴う。従来の解決法は、クリッピングウィンドウの一つのエッジで始まり、プリミティブに遭遇するまでクリッピングウィンドウを横切って全探索し、ラスタライズのラインが完了するまでプリミティブを横切って進む。これはプリミティブの稜線を発見するために、画像を横切る連続的な移動を必要とする。プリミティブの稜線がクリッピングウィンドウの外側にあるとき、従来の解決法は、開始エッジから進み、プリミティブの可視領域（例えば、クリッピングウィンドウの内部の部分）へ進むまで、プリミティブを横切って探索しなければならない。
【０００８】
[008]このように、大量の作業及び対応する多数のクロックサイクルが、画像内で最終的にはレンダリングされないピクセルをラスタライズすることに消費される。このことは、全体的な３Ｄレンダリング処理の性能に対して非常に大きな負の影響を与える。この性能に対する負の影響は、クリッピングウィンドウの外側に大部分の区域を有するプリミティブ（例えば、シャドウイングアプリケーションで多く見られる長くて薄い三角形）の場合に顕著となる。
【０００９】
[009]したがって、必要とされるグラフィックスレンダリングハードウェア、及びそのレンダリングハードウェアによって消費されるクロックサイクルが、生成される画像に関連するピクセルを生成することに生産的に利用されることを確実にするラスタライズ処理の必要性が存在する。
【発明の概要】
【００１０】
[010]本発明の実施形態は、必要とされるグラフィックスレンダリングハードウェア、及び当該レンダリングハードウェアによって消費されるクロックサイクルが、生成されるウィンドウクリップ画像に関連するピクセルを生成することに生産的に利用されることを確実にするラスタライズ処理方法、及びシステムを提供する。
【００１１】
[011]一実施形態において、本発明は、グラフィックスパイプライン（例えば、ＧＰＵ）のラスタステージで、開始タイルの加速されたラスタライズ方法として実現される。本方法は、生成された画像をクリップするウィンドウを画成するステップと、グラフィックスプロセッサのラスタステージでラスタライズするためのグラフィックスプリミティブを受け取るステップと、を含む。ウィンドウに関連した２分探索を実行して、グラフィックスプリミティブの少なくとも部分的なカバー範囲を有する開始タイルを決定する。開始タイルに基づいて、ラスタステージは、グラフィックスプリミティブの少なくとも部分的なカバー範囲を有する複数の近隣タイルを生成することによって、グラフィックスプリミティブをラスタライズする。開始タイル及び近隣タイルの各々は、或る数のピクセルを含む（例えば、１６×１６ピクセル、３２×３２ピクセルなど）。
【００１２】
[012]２分探索は、グラフィックスプリミティブ（例えば、三角形、四辺形、線など）と交差するウィンドウのエッジに沿った特定のタイル（例えば、開始タイル）を、各ステップで当該エッジに沿った候補の開始タイルの範囲の半分を除外することによって、発見するアルゴリズムを含む。例えば、２分探索は、範囲の中央地点を発見し、所望の開始タイルが中央地点の前又は後に来るかどうかを決定する比較を行い、同じようにして残りの半分を探索し、開始タイルを突き止めるまで同じような処理を続ける。
【００１３】
[013]この方法で、本発明の実施形態は、クリッピングウィンドウの内側に存在するグラフィックスプリミティブの稜線を突き止める探索時間を、より困難な場合（例えば、グラフィックスプリミティブの大部分がクリッピングウィンドウの外側に存在する場合）において、１００倍以上加速する。したがって、加速された探索時間によって、２分探索処理を、後続のラスタライズオペレーションと並列又は重複して実行し、それによってリアルタイム３Ｄグラフィックスレンダリングの効率を大きく向上することができる。
【発明の詳細な説明】
【００１４】
[014]以下、本発明を、添付の図面の図において、例示として、限定するものとしてではなく、説明する。これら図面において、類似の参照符号は同様の要素を指している。
【００１５】
[022]ここで、本発明の好ましい実施形態を詳細に参照する。実施形態の例を、添付の図面に図示する。本発明を、好ましい実施形態に関して説明するが、これら実施形態は、当該実施形態へ本発明を限定することを意図していないことが理解されるであろう。反対に、本発明は、添付の特許請求の範囲によって定められる本発明の精神及び範囲の中に含まれる代替、修正、及び均等物をカバーすることを意図している。更に、本発明の実施形態の下記の詳細な説明においては、本発明を十分に理解させるために、多数の具体的詳細部分を説明する。しかしながら、本発明は、これらの具体的詳細部分がなくても実施可能であることが、当業者によって認識されるであろう。他の例においては、本発明の実施形態の様相を、不必要なほどに不明瞭にしないよう、周知の方法、手続き、構成要素、及び回路について詳細に説明していない。
【００１６】
（表記法及び用語）
[023]下記の詳細な説明の幾つかの部分は、手続き、ステップ、論理ブロック、処理、及びコンピュータメモリ内のデータビットに対する演算に関する他の記号表現によって呈示してある。これらの記述及び表現は、データ処理技術の当業者によって使用される手段であり、当業者の成果の内容を他の当業者へ最も効果的に伝達するものである。手続き、コンピュータの実行ステップ、論理ブロック、処理等は、本明細書において、及び一般的に、所望の結果へ導くステップ又は命令の首尾一貫したシーケンスであると考えられる。ステップは、物理量の物理的操作を必要とするものである。通常、必ずしもそうではないが、これらの量は、記憶、転送、結合、比較、及びコンピュータシステム内で操作可能な電気又は磁気信号の形態をとる。時には、一般的に使用されることを主な理由として、これらの信号をビット、値、要素、記号、文字、項、数等で参照することが便利であることが分かっている。
【００１７】
[024]しかしながら、これら及び類似の用語の全てが、適切な物理量に関連づけられるべきであること、及びこれらの量へ適用される単に便宜的なラベルであることを、留意すべきである。下記の説明から明らかであるように、特に別途言及しない限り、本発明の全体を通して、「処理」又は「アクセス」又は「実行」、又は「記憶」又は「レンダリング」等の用語を利用した説明は、コンピュータシステム（例えば、図１のコンピュータシステム１００）、又は類似の電子コンピューティングデバイスのアクション及びプロセスを意味することを理解されたい。これらコンピュータシステム又は類似の電子コンピューティングデバイスは、コンピュータシステムのレジスタ及びメモリ内で物理（電子）量として表現されたデータを操作して、コンピュータシステムメモリ又はレジスタ又は他のこのような情報記憶、伝送、又は表示デバイス内の物理量として同じように表現された他のデータへ変換する。
【００１８】
＜コンピュータシステムプラットフォーム＞
[025]図１は、本発明の一実施形態に係るコンピュータシステム１００を示している。コンピュータシステム１００は、本発明の実施形態に従った基本的なコンピュータシステムの構成要素を描いたものであり、あるハードウェアベース及びソフトウェアベースの機能のために実行プラットフォームを提供するものである。一般的に、コンピュータシステム１００は、少なくとも一つのＣＰＵ１０１、システムメモリ１１５、及び少なくとも一つのグラフィックスプロセッサユニット（ＧＰＵ）１１０を備える。ＣＰＵ１０１は、ブリッジ構成要素／メモリコントローラ（図示されず）を介してシステムメモリ１１５へ結合可能であるか、ＣＰＵ１０１の内部にあるメモリコントローラ（図示されず）を介してシステムメモリ１１５へ直接結合可能である。ＧＰＵ１１０は、ディスプレイ１１２へ結合されている。一つ以上の追加のＧＰＵを、オプションとして、システム１００へ結合し、その計算能力を更に向上することができる。ＧＰＵ１１０は、ＣＰＵ１０１及びシステムメモリ１１５に結合されている。システム１００は、例えば、デスクトップコンピュータシステム又はサーバコンピュータシステムとして実現可能であり、専用グラフィックスレンダリングＧＰＵ１１０へ結合された強力な汎用ＣＰＵ１０１を有する。このような実施形態においては、周辺バス、専門グラフィックスメモリ、Ｉ／Ｏデバイス等を付加する構成要素が含まれていてもよい。同様に、システム１００は、ハンドヘルドデバイス（例えば、携帯電話等）又はセットトップビデオゲームコンソールデバイス、例えば、Ｍｉｃｒｏｓｏｆｔ  Ｃｏｒｐｏｒａｔｉｏｎ  ｏｆ  Ｒｅｄｍｏｎｄ，Ｗａｓｈｉｎｇｔｏｎから入手可能なＸｂｏｘ（登録商標）、又は  Ｓｏｎｙ  Ｃｏｍｐｕｔｅｒ  Ｅｎｔｅｒｔａｉｎｍｅｎｔ  Ｃｏｒｐｏｒａｔｉｏｎ  ｏｆ  Ｔｏｋｙｏ，Ｊａｐａｎから入手可能なＰｌａｙＳｔａｔｉｏｎ３（登録商標）として実現可能である。
【００１９】
[026]ＧＰＵ１１０は、別個の構成要素、コネクタ（例えば、ＡＧＰスロット、ＰＣＩ−Ｅｘｐｒｅｓｓスロット等）を介してコンピュータシステム１００へ結合されるように設計された別個のグラフィックスカード、別個の集積回路ダイ（例えば、マザーボードに直接取り付けられる）、又はコンピュータシステムチップセットの構成要素（図示されず）をもつダイ内に含められた集積ＧＰＵとして、実現可能であることを理解されたい。更に、ローカルグラフィックスメモリ１１４を、ＧＰＵ１１０用に高帯域幅グラフィックスデータストレージとして含めてもよい。
【００２０】
＜本発明の実施形態＞
[027]図２は、本発明の一実施形態に従ってグラフィックスプリミティブ２０１及びクリッピングウィンドウ２０２を描いた図である。図２に示すように、グラフィックスプリミティブ２０１は、クリッピングウィンドウ２０２と交差するが、大部分はクリッピングウィンドウ２０２の外側にある。
【００２１】
[028]グラフィックスプリミティブ２０１（ここでは三角形のグラフィックスプリミティブ）、及びクリッピングウィンドウ２０２は、ＧＰＵのグラフィックスパイプラインのラスタライズで問題となる典型的な場合を示している。グラフィックスプリミティブ（例えば、三角形、四辺形、線等）をラスタライズするときに、ＧＰＵ（例えば、ＧＰＵ１１０）のラスタライズハードウェアは、所与の三角形（例えば、三角形２０１）内で、どこからラスタライズ処理を開始するかを決定する必要がある。ＧＰＵは、そのラスタライズ処理のために開始点を決定する必要がある。
【００２２】
[029]一般的には、ラスタライズ処理は、三角形２０１によって影響、接触、及び／又はカバーされる画像を構成するピクセルの２Ｄ格子（及びクリッピングウィンドウ２０２を構成するピクセルの格子）の構成ピクセルを訪問するように、三角形２０１を探索することを伴う。多くの様々な探索パターンをＧＰＵのラスタライズ機能によって使用して、どのピクセルが三角形２０１によってカバーされるかを系統的に決定することができる。
【００２３】
[030]これら様々な探索パターンは、一般的に、三角形２０１によってカバーされる連続ピクセルが略順番に評価される点で、共通の特徴を有している。例えば、一実施形態では、ピクセルは、前後左右、左から右、又は右から左へ線形に走査されるように検査される（例えば、一時に一つの行、一時に一つの列など）。或いは、一実施形態では、犂耕パターンの探索を使用することができる。ここで、「犂耕」とは、農夫が畑を耕すか収穫するときのように、一つの軸に沿って、各パスが更に直交軸に沿って移動につれて、往復するように操作することによって、２Ｄ区域の全てのピクセルを訪問する探索パターンを意味する。
【００２４】
[031]ＧＰＵ１１０によって実現される探索パターンの型がどのようなものであれ、三角形２０１のピクセルをラスタライズする開始点を決定する必要がある。三角形（又は他の型のグラフィックスプリミティブ）がクリッピングウィンドウ２０２の中に完全に含まれる場合、開始点の選択は容易である。開始点の決定は、例えば、三角形の頂点の一つを開始点として使用することを含むであろう。頂点がクリップ境界ボックスの中に存在せず、開始点として通常使用される境界ボックスの隅が三角形の外側にあるときに、困難が生じる。
【００２５】
[032]一実施形態では、ＧＰＵ１１０は、その探索パターンにおいて、タイル、即ちピクセルのグループを利用する。例えば、探索のラインは、その探索のラインに沿った連続タイル（例えば、８×８ピクセル、１６×１６ピクセル、３２×３２ピクセルなど）をＧＰＵ１１０が横切って進むことを伴うであろう。三角形と交差する最初のタイルが開始点となる。或いは、ＧＰＵ１１０は、複数のサンプル点から構成されるタイルを利用することができる。その場合、各ピクセルは、４個、８個、１６個等のサンプル点を含む。
【００２６】
[033]本発明の実施形態は、より問題となる場合を処理するのに特に適している。このような場合として、クリップされるグラフィックスプリミティブ、例えば、三角形２０１が、クリッピングウィンドウ２０２によって部分的にクリップされる場合がある。例えば、三角形の大部分がクリッピングウィンドウ２０２の外側にある場合、三角形の境界ボックスがスクリーンの大きな区域をカバーしても、実際には三角形の小さな部分のみがスクリーンの内部にあることもある。このことは、三角形２０１の小さな部分２０３がクリッピングウィンドウ２０２の上部に見えるが、三角形２０１の境界ボックス２０５はクリッピングウィンドウ２０２の上部の大部分をカバーするものとして、図２に示してある。
【００２７】
[034]本発明の実施形態は、クリッピングウィンドウ２０２の中にある三角形２０１の部分２０３をラスタライズするために開始タイルを迅速に発見することができる。従来技術において、ラスタライズ処理は、三角形の境界ボックスの遠い左エッジから横断を開始して、クリッピングウィンドウ２０２の左エッジへ到達し、次にウィンドウ２０２の上部を横切って、三角形２０１に遭遇するまでスクリーンの上部をタイルごとに横断しなければならない。これは、非常な無駄な時間を生じさせる。なぜなら、ＧＰＵのラスタライザは、三角形に遭遇する前に、スクリーン幅の半分を超えて横断するからである。従来技術の解決法は、三角形の一部を実際に含むタイルに遭遇するまで、典型的には、スクリーンの上部を横断することによって、全てのタイルを検査する必要があった。対照的に、本発明の実施形態は、加速された開始タイル探索アルゴリズムを実現する。このアルゴリズムは、ＧＰＵサイクル又はラスタライズハードウェアを無駄にすることなく開始タイルを迅速に特定する。
【００２８】
[035]更に図２を参照する。一実施形態では、加速された開始タイルラスタライズ処理は、グラフィックスパイプライン（例えば、ＧＰＵ１１０）のラスタステージにおいて実施される。例えば、三角形２０１を含む場合、生成された画像をクリップするクリッピングウィンドウ２０２が画成され、ラスタステージでラスタライズされるグラフィックスプリミティブ２０１が受け取られると、２分探索が実施されて、開始タイルが迅速に特定される。２分探索は、クリッピングウィンドウを構成するタイル（例えば、１０２４×７６８、１６００×１２００、１９２０×１２００など）を探索して開始タイルを決定する点で、クリッピングウィンドウに関連する。前述したように、開始タイルは、三角形２０１の少なくとも部分的なカバー範囲を有する。開始タイルに基づいて、ラスタステージは、探索のラインに沿って複数のタイルを生成することによって、三角形２０１をラスタライズする。これらのタイルの各々は、三角形２０１を少なくとも部分的にカバーするか接触する。
【００２９】
[036]図３は、本発明の実施形態によって実行されるように三角形２０１をラスタライズする２分探索を示す図である。２分探索は、三角形２０１と交差するクリッピングウィンドウ２０２のエッジに沿った特定のタイル（例えば、開始タイル）を、各ステップで当該エッジに沿った候補の開始タイルの範囲の半分を除外することによって、発見するマルチステップアルゴリズムを含む。例えば、図３の実施形態においては、２分探索は、探索のライン３０１を含むタイルの範囲の中央地点を発見し、所望の開始タイルが中央地点の前又は後に来るかを決定するための比較を行い、次に残りの半分を同じように探索し、開始タイルが突き止められるまで同じように反復する。各ステップにおいて、残りの範囲が半分に分割され、２分探索アルゴリズムは所望の開始タイルに近づいて行く。このことは、図３に示してある。即ち、中央地点の線３０５によって示されるように、２分探索は最初の中央地点を検査し、所望の開始タイルが右にあることを決定し、線３０６で示されるように、第２の中央地点を検査し、開始タイルが更に右にあることを決定し、以下同様に行なう。
【００３０】
[037]このようにして、本発明の実施形態によって実現されるように、探索のラインに沿った２分探索は、クリッピングウィンドウの内側にあるグラフィックスプリミティブの稜線（例えば、三角形２０１の部分２０３）を突き止めるための探索時間を、困難な場合（例えば、グラフィックスプリミティブの大部分がクリッピングウィンドウの外側にある場合）に、１００倍以上加速する。したがって、加速された探索時間によって、２分探索処理を後続のラスタライズオペレーションと並列又は重複して実行することが可能となり、これによってリアルタイム３Ｄグラフィックスレンダリングの効率が大きく向上される。更に、加速された探索時間によって、必要とされるグラフィックスレンダリングハードウェア、及び当該レンダリングハードウェアによって消費されるクロックサイクルが、空のピクセルを横切って進む無駄な動作ではなく、ウィンドウによってクリップされた画像に関連したピクセルを生成することに生産的に利用されることが確実になる。
【００３１】
[038]本発明の実施形態によって実現されるように、２分探索は、対数的な性質をもち、ｌｏｇｎの時間で実行されることに留意されたい。具体的には、所望の開始タイルを返却するため、１＋ｌｏｇ２Ｎ回の反復が必要である。ここで、Ｎは探索のラインに沿ったタイルの総数に対応する（例えば、１９２０×１２００ウィンドウ又は画像の上部エッジに沿って、６０個の３２×３２タイルが存在する）。２分探索は、従来技術の順次探索よりも相当に速い。順次探索の場合、所望の開始タイルがランダムに分布するときに、平均でＮ／２回の比較が必要であり、テストされる最後のタイルが開始タイルである最悪のケースでは、Ｎ回の比較が必要である。
【００３２】
[039]図４は、本発明の一実施形態に従って特定のタイル又は特定のピクセルが三角形２０１の左、右、又は内部にあるかどうかを決定するためにＧＰＵ１１０によって評価される頂点方程式の演算を示す図である。一実施形態では、三角形２０１の頂点に基づく頂点方程式を使用して、三角形２０１の稜線の位置を計算する。これらの頂点方程式は、探索のラインに沿った所与のピクセルが、三角形２０１の左、右、又は内部にあるか否かを示す。したがって、例えば、稜線方程式は、探索のラインの一部分４０１上のピクセル（又は、タイル、サンプルなど）が三角形２０１の左にあり、探索のラインの一部分４０２上のピクセルが三角形２０１の内部にあり、探索のラインの一部分４０３上のピクセルが三角形２０１の右にあることを示すであろう。
【００３３】
[040]本実施形態は、ウィンドウ２０２の上部エッジに沿った２分探索を実行することに関して説明されているが、本発明の実施形態は、ウィンドウ２０２の複数のエッジに沿って２分探索を実行できることに留意されたい。これによって、グラフィックスプリミティブがウィンドウ２０２の左エッジ、右エッジ、又は底の外に延在する場合に、２分探索を効率的に進行することが可能となる。例えば、一実施形態では、第１のエッジ（例えば、ウィンドウ２０２の上部又は底のエッジ）上で２分探索を実行し、続いて第２のエッジ（例えば、ウィンドウ２０２の左又は右のエッジ）上で実行して、所望の開始タイルを最も効率的に突き止めることができる。
【００３４】
[041]図５は、本発明の一実施形態に従って、開始タイル５０１が２分探索によって突き止められる様子、及び連続した隣接タイルが三角形２０１について反復される様子を示す図である。前述したように、２分探索が使用されて、クリッピングウィンドウ２０２の内部にある三角形２０１の部分について開始タイル５０１が突き止められる。続いて、図示するように、開始タイル５０１に基づき探索のラインに沿った複数のタイルを生成することによって、三角形２０１の残りがラスタライズされる。続いて生成されたタイルの各々は、三角形２０１の少なくとも部分的なカバー範囲を有する。図５の実施形態が犂耕探索パターンを示していることに留意されたい。
【００３５】
[042]したがって、前述したように、加速された探索時間によって、後続のラスタライズオペレーションと並行又は重複して２分探索処理を実行することが可能となる。例えば、一度、開始タイル５０１が突き止められると、２分探索アルゴリズムは、三角形２０１の残りがラスタライズされるときに、後続のグラフィックスプリミティブのために後続の開始タイルを突き止めることに進むことができる。後続の開始タイルを突き止める２分探索は、三角形２０１の残りのタイルが切り出されているときと同時に発生することが可能である。この機能の重複は、一つのラスタライズ機能（例えば、開始タイルの探索）が、後続のラスタライズ機能（例えば、三角形からの複数タイルのラスタライズ）が進行している間に終了ように、グラフィックスハードウェアが遊休状態にならないようにする。
【００３６】
[043]図６は、本発明の一実施形態に従ったタイル６０１の寸法を示す図である。図６に示すように、タイル６０１は、コーナー６０２〜６０５を含む。所与のアプリケーションの特定の要件に応じて、タイル６０１は２分探索の際にコーナー６０２〜６０５の何れか一つで評価可能である。一実施形態では、タイルは最も尤度の高いエッジ、例えば、２分探索処理の間にグラフィックスプリミティブと最初に交差するであろうエッジ６０７に沿って評価される。例えば、タイルのエッジ６０７を、前述した三角形稜線方程式に従って評価し、前述したように、２分探索の次の中央地点が左、右、上方、又は下方にあるかどうかを決定する。
【００３７】
[044]本発明の実施形態が、複数のピクセルをもつタイルに加えて、個々のピクセルに対して、更にはピクセルの内部のサンプルの配列に対して、処理可能であること、及びタイルのサイズが、特定のアプリケーションのニーズ（例えば、グラフィックスドライバによってプログラム可能である、等）に応じて、カスタマイズ可能であることに留意されたい。更に、探索されるべき所与のクリッピングウィンドウのエッジの数、探索されるべき第１及び第２のクリッピングウィンドウのエッジ、及び評価されるべきタイルのエッジ又はコーナーが、特定のアプリケーションのニーズ（例えば、グラフィックスドライバによってプログラム可能である、など）に応じて、プログラム可能であることにも留意されたい。
【００３８】
[045]図７は、本発明の一実施形態に係るＧＰＵ１１０の内部構成要素の図を示す。図７に示すように、ＧＰＵ１１０は、セットアップエンジン７０１及びラスタライザユニット７０２を備えている。本実施形態では、本発明の機能が、ラスタライザユニット７０２のハードウェア及びソフトウェアの内部に実装されている。一般的に、ラスタライザユニット７０２は、セットアップエンジン７０１から受け取られた頂点ベースの記述を、稜線ベースの記述へ変換するように機能する。続いて、ラスタライザユニット７０２は、これらの稜線の記述を、実際のピクセル記述を構成する充填領域（例えば、ピクセル領域、ピクセルの部分サンプル等）へ変換する。続いて、ピクセル記述はＧＰＵ１１０内の他のユニットへ渡され、更なる処理及びレンダリングが行われる。
【００３９】
[046]一実施形態において、ラスタライザユニット７０２は、微細なラスタ構成要素７０３、及び粗いラスタ構成要素７０４を有する。ステッパユニット７０５は、粗いラスタ構成要素７０４内に実装されており、前述したような加速された開始タイル探索機能を実施する。開始タイルが特定されると、粗いラスタユニット７０３は、タイルの格子を迅速に探索して、注目するタイル（プリミティブによってカバーされるタイル）を特定する。注目するタイルが特定されると、微細なラスタ構成要素７０３が、プリミティブによってカバーされるピクセルを個々に特定する。したがって、このような実施形態では、ステッパ７０５は所望の開始タイルを特定し、粗いラスタ構成要素７０４はタイルを使用することによってピクセルの格子を迅速に探索し、微細なラスタ構成要素７０３は粗いラスタ構成要素７０４によって生成された情報を使用し、プリミティブによってカバーされたピクセルを個々に特定することによって、微細粒度のラスタライズを実現する。
【００４０】
[047]更に図７を参照する。ＧＰＵ１１０は更にキャッシュメモリ７２１を有する。キャッシュメモリ７２１は、使用頻度が最も高いグラフィックスレンダリングデータのために高速低待ち時間記憶を実現するように機能する。このようなデータは、典型的には、テクスチャ情報、頂点情報、色等を含む。キャッシュメモリ７２１は、ローカルグラフィックスメモリ１１４へ結合されるように示されている。キャッシュメモリ７２１は一つ以上のキャッシュメンテナンスメカニズムを利用して、ローカルグラフィックスメモリ１１４との一貫性を維持する。矢印７４０は、ＧＰＵ１１０とシステムメモリ（例えば、図１に示したメモリ１１５）との間の通信経路を示している。
【００４１】
[048]以上の本発明の特定の実施形態に関する記述は、例示及び説明を目的として呈示したものである。これらの記述は、本発明の全てを包括することは意図しておらず、開示されたそのままの形態へ本発明を限定することも意図しておらず、上記の教示に照らして、多くの修正及び変形が想定され得る。これら実施形態は、本発明の原理及びその実用的応用を最良に説明し、それによって当業者が、想定される特定の使用に適した様々な修正によって本発明及び様々な実施形態を最良に利用することができるように、選択して説明したものである。本発明の範囲は、本明細書に添付された特許請求の範囲及びその均等物によって定められることが意図されている。
【図面の簡単な説明】
【００４２】
【図１】本発明の一実施形態に係るコンピュータシステムを示す図である。
【図２】本発明の一実施形態に従ってグラフィックスプリミティブ及びクリッピングウィンドウ２０２を描いた図である。
【図３】本発明の実施形態によって実行されるように三角形２０１をラスタライズするための２分探索を示す図である。
【図４】本発明の一実施形態に従って、特定のタイル又は特定のピクセルが三角形の左、右、又は内部にあるかどうかを決定するために、ＧＰＵによって評価される頂点方程式の演算を示す図である。
【図５】本発明の一実施形態に従って、開始タイルが２分探索によって突き止められる様子、及び連続したタイルが三角形から反復される様子を示す図である。
【図６】本発明の一実施形態に係るタイルの寸法を示す図である。
【図７】本発明の一実施形態に係るＧＰＵの内部構成要素を示す図である。
【符号の説明】
【００４３】
１００…コンピュータシステム、１０１…中央プロセッサユニット（ＣＰＵ）、１１０…グラフィックスプロセッサユニット（ＧＰＵ）、１１２…ディスプレイ、１１４…ローカルグラフィックスメモリ、１１５…システムメモリ、７０１…セットアップエンジン、７０２…ラスタライザユニット、７０３…微細なラスタ構成要素、７０４…粗いラスタ構成要素、７０５…ステッパ、７２１…キャッシュメモリ。
【図１】
2008102904.tif 000003
【図２】
2008102904.tif 000004
【図３】
2008102904.tif 000005
【図４】
2008102904.tif 000006
【図５】
2008102904.tif 000007
【図６】
2008102904.tif 000008
【図７】
2008102904.tif 000009
【外国語明細書】
2008102904000001.pdf