JP5518967B2 - グラフィック・パフォーマンス改善のための方法、装置およびコンピュータ・プログラム・プロダクト - Google Patents

Description

本発明は、デジタル表現されたグラフィックに、より詳細にはデジタル表現されたグラフィックを生成するパフォーマンスの改善のための方法、装置およびコンピュータ・プログラム・プロダクトに関する。

コンピュータ・グラフィックのようなデジタル表現されたグラフィックは継続的にパフォーマンスを改善してきている。1980年代および1990年代には、グラフィック・アクセラレータをもつ、コンピュータおよびゲーム・コンソール用ディスプレイ・アダプターが現れ、グラフィック生成において中央処理装置（CPU）の負荷を軽減した。最初はディスプレイ・アダプターは2Dグラフィックの加速をもたらしたが、結局はディスプレイ・アダプターは加速3Dグラフィックのサポートをも含むようになった。現代のディスプレイ・アダプターは、しばしばグラフィック処理ユニット（GPU: graphics processing unit）と称される処理ユニットを使う。

3Dグラフィックの複雑さのため、今日のGPUはその処理パワーのかなりの部分を3Dグラフィックに関係する計算を実行するために使う。

ディスプレイ・アダプターに関する継続的な問題はパフォーマンスである。常に、より高いフレーム・レート（毎秒レンダリングされる画面画像数）、より高い解像度およびより高い画像品質を要求する新たなアプリケーションやゲームが登場し、その結果、各画面画像はできるだけ短い時間でレンダリングされることが要求される。換言すれば、パフォーマンスを上げることは常に重要だということである。

パフォーマンスを上げるために知られている一つの方法は、より高いクロック・スピードを可能にする、パイプライニングするまたは並列計算を活用することによってGPUの処理パワーを上げることである。しかしながら、これはしばしばより多くの発熱につながり、結果として電力消費が多くなり、GPUを冷ますためのファンの雑音が大きくなる。電力消費と発熱はモバイル装置にとっては重要な制約となり、ボトルネックとなる。さらに、各GPUのクロック・スピードには限界がある。

したがって、依然として、デジタル表現されたグラフィックにおけるパフォーマンスを改善する能力が不十分であるという問題がある。

上記に鑑み、本発明の一つの目的は、上で論じた問題を解決するまたは少なくとも軽減することである。

第一の側面によれば、本発明は、デジタル表現されたグラフィックの生成のパフォーマンスを改善する方法によって実現される。本方法は：基本プリミティブの第一の表現を受領し；バーテックス位置決定に関連付けられた命令の組を提供し；前記基本プリミティブの前記第一の表現に対して、有界算術（bounded arithmetic）を使って前記命令の組を実行して、前記基本プリミティブの第二の表現を提供し；前記基本プリミティブの前記第二の表現を選別（culling）プロセスにかけることを含む。基本プリミティブに対して選別を実行することは、基本プリミティブおよび基本プリミティブの表現がグラフィック・パイプラインの最初に破棄され得、これがパフォーマンスの利得につながるという点で有利である。さらに、完全にレンダリングされた画像において見えない表面の大半は前記プロセスにおいて後段に転送されず、これもパフォーマンスの利得につながる。換言すれば、全基本プリミティブに対して選別を実行することは、見えない表面の大半のテッセレーション（tessellation）が避けられ、これがパフォーマンスの利得につながるという点で有利である。

コンピュータ・グラフィックでは、バーテックス（vertex）は、空間内のある位置に関連付けられたデータを含む。たとえば、バーテックスは、プリミティブのコーナーに関連付けられた全データであってもよい。バーテックスは、三つの空間座標のみならず、色、反射属性、テクスチャおよび表面法線といった、オブジェクトを正しくレンダリングするために必要な他のグラフィック情報とも関連付けられる。

バーテックスの接続された集合が、プリミティブを定義するために使用できる。プリミティブ（primitive）は、たとえば、三角形、四角形、多角形〔ポリゴン〕または他の幾何学的な形であってもよく、あるいはまた、プリミティブは空間内の面または点であってもよい。三角形として表現されるプリミティブは、たとえば三つのバーテックスをもち、四角形は四つのバーテックスをもつ。

本方法は、前記基本プリミティブの前記第一の表現から少なくとも一つのバーテックスを選択し、前記少なくとも一つのバーテックスの第一の表現に対して、バーテックス位置決定に関連付けられた命令の組を実行して、前記少なくとも一つのバーテックスの第二の表現を提供し、前記少なくとも一つのバーテックスの前記第二の表現を選別プロセスにかけることを含んでいてもよく、前記選別プロセスの帰結は、前記少なくとも一つのバーテックスを選別するという決定および前記少なくとも一つのバーテックスを選別しないという決定のうちの一つを含み、前記選別プロセスの帰結が前記少なくとも一つのバーテックスを選別するという決定を含む場合に：基本プリミティブの第一の表現を受領する前記段階；バーテックス位置決定に関連付けられた命令の組を提供する前記段階；前記基本プリミティブの前記第一の表現に対して、有界算術を使って前記命令の組を実行して、前記基本プリミティブの第二の表現を提供する前記段階；および前記基本プリミティブの前記第二の表現を選別プロセスにかける前記段階を実行する。これは、パフォーマンス利得につながるので、有利である。たとえば、前記選別プロセスの帰結が、前記少なくとも一つのバーテックスを選別しないという決定である場合には、前記第一の側面による方法に比べて、キャパシティ的に高価でない方法を与える。

本方法は、前記基本プリミティブの前記第二の表現を囲むバウンディング・ボリュームを決定し；前記バウンディング・ボリュームを選別プロセスにかけることを含みうる。これは、あらかじめ設定された限界が与えられる必要がなく、バウンディング・ボリュームが自動的に決定されるという点で有利である。

本方法は、テッセレーション・プロセスを実行することを含みうる。ここで、前記テッセレーション・プロセスは、前記選別プロセスの帰結に基づく。よって、選別はテッセレーションの前に実行される。選別後にテッセレーションを実行することは、より少数の基本プリミティブがテッセレーションされるのでパフォーマンスの利得につながり、よって有利である。前記選別プロセスは、第二の表現がかけられる選別プロセスおよび／または前記バウンディング・ボリュームがかけられる選別プロセスであることができる。

本方法は、前記選別プロセスが置換可能であることを含みうる。前記選別プロセスがたとえばユーザーによって修正されてもよいという点で有利である。前記選別プロセスが置換可能であるということは、第一の側面の全実施形態に当てはまる。

本方法は、有界算術が、テイラー算術（Taylor arithmetic）、区間算術（interval arithmetic）およびアフィン算術（affine arithmetic）の群からの少なくとも一つであることを含みうる。これは、本方法が柔軟であり、種々の型の有界算術をサポートし、一つの型の有界算術に制約されないという点で有利である。テッセレーションにおいてよく使われる曲面および細分方式がしばしば多項式に基づくので、テイラー・モデルを使うことが好ましい。もう一つの利点は、多項式計算はテイラー・モデル（十分高い次数であるとする）によって厳密に表現でき、このことが非常に緊密な（tight）限界につながるということである。

本方法は、前記バウンディング・ボリュームの決定がさらに、前記第二の表現の最小および最大を計算することを含むということを含みうる。これは、バウンディング・ボリュームを決定するためのパフォーマンス効率のよい方法であるという点で有利である。

本方法は、前記第二の表現が、位置限界（positional bound）および法線限界（normal bound）の群のうちの少なくとも一つであるということを含みうる。位置限界および法線限界は、たとえば基本プリミティブの第一の表現の位置または範囲を決定するために使用されうる。さらなる利点は、位置限界および法線限界が自動的に決定されるということである。

本方法は、前記命令の組を実行することがさらに：バーテックス位置決定に関連付けられた前記命令の組から第二の命令の組を導出し、前記第二の命令の組を実行して法線限界を与えることを含むということを含みうる。これは、前記第二の組の命令が自動的に導出され、さらに法線限界が自動的に計算されるという点で有利である。

本方法は、前記バウンディング・ボリュームを前記選別プロセスにかけることがさらに、前記バウンディング・ボリュームをビュー錐台選別（view frustum culling）にかける、前記バウンディング・ボリュームを裏面選別（back-face culling）にかけるおよび前記バウンディング・ボリュームを隠蔽選別（occlusion culling）にかけることのうちの少なくとも一つを実行することを含むということを含みうる。この利点は、多くの異なる選別技法が適用可能であるということである。

本方法は、前記第二の表現（位置限界または法線限界である）を前記選別プロセスにかけることがさらに、前記位置限界をビュー錐台選別にかける、前記位置限界または前記法線限界を裏面選別にかけるおよび前記位置限界を隠蔽選別にかけることのうちの少なくとも一つを実行することを含むということを含みうる。この利点は、多くの異なる選別技法が適用可能であるということである。

本方法は、前記選別プロセスの帰結が前記基本プリミティブを破棄するという決定およびテッセレーション因子の一つを含むということを含みうる。基本プリミティブを破棄することは、レンダリングすべき基本プリミティブが一つ少なくなるということを含意し、それはパフォーマンスを高めるので、有利である。

本方法は、前記選別プロセスの帰結がテッセレーション因子を含む場合に、テッセレーション・プロセスを実行することを含みうる。これは、テッセレーションされないまたはより少なくテッセレーションされる基本プリミティブ毎についてパフォーマンスの利得があるという点で有利である。前記選別プロセスの帰結が前記基本プリミティブを破棄するという決定である場合、テッセレーション・プロセスは実行されない。

第二の側面によれば、本発明は、デジタル表現されたグラフィックを生成するよう適応された装置であって、デジタル表現されたグラフィックの生成のパフォーマンスを改善する回路を有する装置によって実現される。前記回路は：基本プリミティブの第一の表現を受領し；バーテックス位置決定に関連付けられた命令の組を提供し；前記基本プリミティブの前記第一の表現に対して、有界算術を使って前記命令の組を実行して、前記基本プリミティブの第二の表現を提供し；前記基本プリミティブの前記第二の表現を選別プロセスにかけるよう適応されている。

本発明の第二の側面は、本発明の第一の側面の特徴のいずれに対応する特徴のいかなる組み合わせを用いて具現されることもできることを注意しておく。

第一の側面の利点は、第二の側面にも等しく当てはまる。

第三の側面によれば、本発明は、コンピュータ可読記憶媒体上に記憶され、プロセッサ上で実行されたときに本発明の第一の側面に基づく方法を実行するコンピュータ・プログラム・コードを有するコンピュータ・プログラム・プロダクトによって実現される。第一の側面の利点は、第三の側面にも等しく当てはまる。

本発明の他の目的、特徴および利点は、以下の詳細な開示から、付属の請求項から、また図面から、明白となるであろう。

一般に、請求項において使われているすべての用語は、本稿において明示的に他の定義がされているのでない限り、当該技術分野におけるその通常の意味に従って解釈されるべきである。「ある／該［要素、装置、コンポーネント、手段、段階など］」というあらゆる言及は、そうでないとの明示的な陳述がない限り、そのような要素、装置、コンポーネント、手段、段階などの少なくとも一つのインスタンスに言及するオープンなものとして解釈されるべきである。本稿に開示されるどの方法のステップも、明示的に述べられているのでない限り、開示されている厳密な順序で実行される必要はない。

本発明の他の特徴および利点は、付属の図面の参照のもとに、現在のところ好ましい実施形態の以下の詳細な記述から明白となるであろう。

Berz, M., and Hoffst¨atter, G., Computation and Application of Taylor Polynomials with Interval Remainder Bounds, 『Reliable Computing』, 4, 1, 73-97, 1998 Hungerb¨uhler, R., and Garloff, J., Bounds for the Range of a Bivariate Polynomial over a Triangle, 『Reliable Computing』, 4, 1, 3-13, 1998

従来技術に基づくディスプレイ・アダプターにおいて種々のエンティティがどのように相互作用するかを示すブロック図である。 本発明のある実施形態において装置内の種々のエンティティがどのように相互作用しうるかを示すブロック図である。 本発明のある実施形態を示すブロック図である。 本発明のある実施形態を示すブロック図である。 本発明のある実施形態を示すブロック図である。 本発明のある実施形態を示すブロック図である。 本発明のある実施形態を示すブロック図である。 本発明のある実施形態を示すブロック図である。 本発明のある実施形態を示すブロック図である。 図２ａ〜ｄの装置において実行できる基本プリミティブ選別プロセスを示すフローチャートである。 図２ａ〜ｄの装置において実行できる基本プリミティブ選別プロセスを示すフローチャートである。 図３ａ〜ｂの基本プリミティブ選別プロセスを示す概略図である。 図２ａ〜ｄの装置を具現する典型的な汎用コンピュータの全体的なアーキテクチャを示す図である。

本発明は、本発明のある種の実施形態を示す付属の図面を参照しつつ以下により十全に記述される。しかしながら、本発明は、数多くの異なる形において具現されうるものであり、本稿に記載される実施形態に限定されると解釈すべきではない。これらの実施形態は、本開示が十全であり完備となり、本発明の範囲を当業者に十全に伝えるべく例として与えられているものである。同様の参照符号は全体を通じて同様の要素を指す。

図１は、当業者には既知の従来式のディスプレイ・アダプターにおける種々のエンティティがどのように相互作用するかを示すブロック図である。従来技術に基づくディスプレイ・アダプターは、テッセレータ（tessellator）１２０、バーテックス・シェーダー（vertex shader）１３０、三角形通過ユニット（triangle traversal unit）１４０およびフラグメント・シェーダー（fragment shader）１５０を含みうる。従来技術に基づくディスプレイのこれらのエンティティは当業者にはよく知られている。

テッセレータ１２０への入力１１０は基本プリミティブであり、これは三角形、四角形または他の幾何学的な形であってもよい。テッセレーションは、多くの、より小さな、しばしば接続されたプリミティブが生成されることを含意する。たとえば、基本三角形（すなわち基本プリミティブ）がテッセレータ１２０において基本三角形を覆う100×100の、より小さな、接続された三角形に分割される。これらのより小さな三角形のバーテックスの位置は、バーテックス・シェーダー・ユニット１３０において計算でき、それにより曲がった表面が形成される。

種々の型のテッセレーションが存在する。たとえば、一様テッセレーション（uniform tessellation）、部分テッセレーション（fractional tessellation）および適応テッセレーション（adaptive tessellation）である。

バーテックス・シェーダー・ユニット１３０は、テッセレータ１２０から全バーテックスについての重心座標（barycentric coordinates）を受信し、たとえばバーテックスの位置p(u,v)を重心座標(u,v)の関数として計算する。

三角形通過ユニット１４０は、接続されたコントローラによって指示されるようにポリゴンをセットアップすることを受け持つ。いかなる多角形でも使用できるが、三角形が一般に使用される。各ポリゴンについて、三角形通過ユニット１４０は、レンダリングされるべきポリゴンを一つまたは複数のタイルに分割する。ここで、各タイルには少なくとも部分的には前記ポリゴンが重なる。一般に、タイルは、フラグメントの群である。タイルは、いくつかのフラグメントを含む二次元長方形である。これらのフラグメントのそれぞれがピクセルに対応し、そのピクセルをレンダリングするためおよびそのピクセルが画面上にレンダリングされるべきかどうかを試験するために要求される全データを含む。タイルの一般的なサイズは８×８フラグメントであるが、任意のタイル・サイズが本発明の範囲内である。

三角形通過ユニット１４０のもう一つの重要なタスクは、レンダリングされる幾何学的プリミティブ（たとえば三角形）内にあるフラグメントを見出すことである。これは、当業者には既知の多様な技法を使ってできる。

フラグメント・シェーダー１５０は、このユニットに渡される各フラグメントについてフラグメント・シェーダー・プログラムを実行する。これらのフラグメントのそれぞれがピクセルに対応し、そのピクセルをレンダリングするためおよびそのピクセルが画面上にレンダリングされるべきかどうかを試験するために要求される全データを含む。フラグメント・データは、ラスタ位置、奥行き（depth）、色、テクスチャ座標、ステンシル、アルファ（ブレンディングのために使用される）などを含む。一つ一つの全ピクセルについて、複数のフラグメント・サンプルが存在してもよい。

フラグメントはさらに処理される。これはたとえば、以前に評価された色をテクスチャと組み合わせる、また霧のような効果を加える、また可能な場合にはレンダリングされる必要のないフラグメントを識別する、すなわちフラグメント選別のためである。

フラグメント・シェーダー１５０はさらに、フラグメントが目標バッファに書き込まれる前に、奥行き試験、アルファ試験およびブレンディングを実行してもよい。

従来技術に基づくディスプレイ・アダプターからの出力１５０はディスプレイ上に表示されうる。

ここから、本発明について述べる。

本発明に基づくデジタル表現されたグラフィックを生成するよう適応された装置の種々の実施形態について、以下で図２を参照しつつ述べる。本装置は、デジタル表現されたグラフィックの生成のパフォーマンスを改善する回路を有する。前記装置は、ディスプレイ・アダプターとして具現されてもよく、以下ではディスプレイ・アダプターと称される。

図２ａは、本発明に基づくディスプレイ・アダプター２０５の実施形態を示すブロック図である。ディスプレイ・アダプター２０５は、基本プリミティブ選別回路２１２をなす、デジタル表現されたグラフィックの生成のパフォーマンスを改善する回路を有する。

基本プリミティブ選別回路２１２への入力２１０は、基本プリミティブの第一の表現である。コンピュータ・グラフィックの分野における幾何学的プリミティブは、通例、システムが扱える、たとえば描画または記憶することのできる原子的な幾何学的オブジェクトと解釈される。他のすべてのグラフィック要素はこれらのプリミティブから構築される。

基本プリミティブは、多くの、より小さな、三角形のような幾何学的プリミティブに分割〔テッセレーション〕できる好適な幾何学的表現である。基本プリミティブは分割されていない。基本プリミティブの例は、三角形、四角形、直線、曲線、ベジェ面などである。

ポリゴンは、接続されたバーテックスの組を使って定義される。たとえば三角形は三つのバーテックスを有し、四角形は四つのバーテックスを有する。コンピュータ・グラフィックでは、バーテックスは、三つの空間座標のみならず、色、反射属性、テクスチャおよび面法線といった、オブジェクトを正しくレンダリングするために必要な他のグラフィック情報とも関連付けられる。

基本プリミティブの第一の表現は、属性の集合であってもよい。属性の集合は、たとえば、制御点、バーテックス位置、法線、テクスチャ座標などの群からの一つであってもよい。たとえば、三角形は、三つのバーテックス位置を使って記述でき、四角形ポリゴンは四つのバーテックス位置を使って記述できる。各バーテックス位置は、法線およびテクスチャ座標といった、他の属性と関連付けられていてもよい。もう一つの例は、ベジェ三角形またはパッチであり、これは一組のバーテックス位置および制御点を使って記述できる。

基本プリミティブ選別ユニット２１２において、選別は、基本プリミティブに対して、および基本プリミティブの表現に対して実行される。基本選別ユニットからの出力２２２は、基本プリミティブが破棄されるべきであるということであってもよい。別の実施例では、出力２２２は、テッセレーション因子が生成されるということであってもよい。テッセレーション因子は、基本プリミティブが破棄されるべきであることを指示する値に設定されてもよい。あるいはまた、テッセレーション因子は、基本プリミティブが破棄されることができないことを示す値に設定されてもよい。さらに、テッセレーション因子は、基本プリミティブがテッセレーションされるべきではない、粗くテッセレーションされるべきである、あるいは低レートでテッセレーションされるべきであることを示す値に設定されてもよい。

基本プリミティブ選別の詳細および効果については、図３ａおよび図３ｂとの関連でさらに後述する。

ディスプレイ・アダプター２０５からの出力２２４はディスプレイ上に表示されうる。

もう一つの実施形態では、図２ｂを参照するに、ディスプレイ・アダプター２０５は、基本プリミティブ選別ユニット２１２およびテッセレータ２１４を有する。テッセレータ２１４は、図１を参照して上記したテッセレータ１２０と同様の型であってもよい。

基本プリミティブ選別ユニット２１２、基本プリミティブ選別ユニット２１２への入力２１０およびディスプレイ・アダプター２０５からの出力２２４は図２ａとの関連で前述した。

テッセレータ２１４が基本プリミティブ選別ユニット２１２から、基本プリミティブと、該基本プリミティブがテッセレーションされるべきではないことを示すテッセレーション因子とを受け取る場合、テッセレータは基本プリミティブをテッセレーションしない。

テッセレータ２１４が基本プリミティブ選別ユニット２１２から、基本プリミティブを受け取るが、該基本プリミティブがテッセレーションされるべきではないことを示すテッセレーション因子を受け取らない場合は、テッセレータ２１４は基本プリミティブをテッセレーションする。

図２ｃは、本発明のある実施形態において、ディスプレイ・アダプター２０５内の種々のエンティティがどのように相互作用しうるかを示すブロック図である。ディスプレイ・アダプター２０５は、基本プリミティブ選別ユニット２１２、テッセレータ２１４、バーテックス・シェーダー２１６、三角形通過ユニット２１８およびフラグメント・シェーダー２２０を有する。エンティティ２１４、２１６、２１８および２２０は、図１を参照して前述したのと同様の型であってもよい。

基本プリミティブ選別ユニット２１２、基本プリミティブ選別ユニット２１２への入力２１０およびディスプレイ・アダプター２０５からの出力２２４は図２ａとの関連で前述した。

さらにもう一つの実施形態では、図２ｄを参照するに、ディスプレイ・アダプター２０５は、基本プリミティブ選別ユニット２１２、テッセレータ２１４、バーテックス・シェーダー２１６、三角形通過ユニット２１８、プログラム可能選別ユニット（PCU: programmable culling unit）２２６およびフラグメント・シェーダー２２０を有する。エンティティ２１４、２１６、２１８および２２０は、図１を参照して前述したのと同じまたは同様の型であってもよい。基本プリミティブ選別ユニット２１２、基本プリミティブ選別ユニット２１２への入力２１０およびディスプレイ・アダプター２０５からの出力２２４は図２ａとの関連で前述した。

プログラム可能選別ユニット２２６では、選別は、置換可能な選別モジュールとしても知られる置換可能な選別プログラムに従って実行される。選別プログラムの詳細および効果は、非公開のスウェーデン特許出願SE0700162-1においてより詳細に説明されており、その内容はここに参照によって組み込まれる。

図２ａのディスプレイ・アダプター２０５はさらに、基本プリミティブ探査ユニット２１１を有していてもよい（図２ｅを参照）。基本プリミティブ探査ユニット２１１は、基本プリミティブの少なくとも一つのバーテックスが選別されることができるかどうかを検査するよう構成される。前記少なくとも一つのバーテックスは、たとえば、基本プリミティブのバーテックスまたは基本プリミティブの中心であることができる。基本プリミティブの前記少なくとも一つのバーテックスが選別されることができない場合、そのことはその基本プリミティブが選別されることができないということを含意し、その場合、基本プリミティブ選別はキャパシティを要求するので、基本プリミティブ選別ユニット２１２において基本プリミティブ選別を実行しないほうがよい。

図２ｆに示されるように、図２ｂのディスプレイ・アダプター２０５はさらに、基本プリミティブ探査ユニット２１１を有していてもよい。さらに、図２ｃのディスプレイ・アダプター２０５が基本プリミティブ探査ユニット２１１を有していてもよい（図２ｇを参照）。図２ｄのディスプレイ・アダプター２０５が基本プリミティブ探査ユニットを有していてもよい（図２ｈを参照）。

図３ａは、図２ａ、２ｂ、２ｃおよび２ｄの基本プリミティブ選別ユニット２１２において実行されることのできる基本プリミティブ選別プログラムについてのフローチャートを示している。

ステップ３１０では、基本プリミティブの第一の表現が受領される。

ステップ３２０では、命令の組が提供される。提供された命令の組は、バーテックス位置決定と関連付けられる。バーテックス位置は、たとえば、バーテックス・シェーダー・ユニット２１６との関連で全バーテックスについての重心座標を使ってp(u,v)として計算される。前記命令の組は、バーテックス・シェーダー・ユニット２１６において実行できるバーテックス・シェーダー・プログラムから導かれるまたは取り出される。前記命令の組は、次いで、解析され、バーテックス位置を計算するために使われるすべての命令、算術命令が単離される。これらの命令は、有界算術、たとえばテイラー算術、区間算術、アフィン算術または当業者に既知の別の好適な算術に対して作用するよう再定義される。ある実施形態では、これらの命令は、（浮動小数点数ではなく）テイラー・モデルに対して作用するよう再定義され、新たな命令への入力がテイラー・モデルに再定義される。

後続のステップの理解を助けるため、テイラー・モデルの簡単な説明をしておく。

テイラー・モデルでは区間が使われ、区間について、次の記法が使用される：

u∈[u₀,u₁]としてn＋1回微分可能な関数f(u)を与えられると、fのテイラー・モデルはテイラー多項式T_fおよび区間残余項（＾付きのr_f）から構成される。ここでチルダ付きのfで記される、定義域u∈[u₀,u₁]上でのn次のテイラー・モデルは：

となる。ここで、

はテイラー多項式であり、

は区間残余項である。この表現がテイラー・モデルと呼ばれ、定義域u∈[u₀,u₁]上での関数fの保守的な囲い（enclosure）である。テイラー・モデルに対する算術演算子を定義することも可能であり、その結果も保守的な囲い（もう一つのテイラー・モデル）である。単純な例として、f＋gが計算され、これらの関数がテイラー・モデル

として表されるとする。すると、その和のテイラー・モデルは、

となる。乗算、正弦、対数、指数、逆数などのようなより複雑な演算子も導出できる。これらの演算子についての実装上の詳細は、非特許文献１に記載されている。

重心座標（barycentric coordinates）はテイラー・モデルとして：

と再定義されてもよい。

ステップ３３０では、提供された命令の組が、有界算術を使って、基本プリミティブの第一の表現に対して実行される。前記命令の組のこの実行の帰結は、基本プリミティブの第二の表現である。

基本プリミティブの前記第二の表現は、テイラー・モデルであってもよく、バーテックス位置属性の多項式近似であってもよい。より具体的には、ステップ３３０からの出力は、四つのテイラー・モデルである位置限界：

であってもよい。単一の成分、たとえばxについて、これは冪ベースで次のように表現できる：

（明確のため、残余項である＾付きのr_fは省略した）。

ステップ３３０において使われる有界算術は、たとえばテイラー算術、区間算術、アフィン算術または当業者に既知の他の好適な算術であってもよい。

ある実施形態では、前記基本プリミティブの前記第二の表現は法線限界であってもよい。パラメータ表現された面について、規格化していない法線、ベクトルnは：

として計算できる。すると法線限界、すなわち法線のテイラー・モデルは、

として計算される。

ある実施形態では、前記命令の組を実行するステップ３３０は、ステップ３３１を含む（図３ｂ参照）。ステップ３３１は、バーテックス位置決定に関連する前記命令の組から第二の命令の組を導出することを含む。前記第二の命令の組は、バーテックス・シェーダー・ユニット２１６において実行されるバーテックス・シェーダー・プログラムから取得され、それらの命令は解析され、バーテックス位置を計算するために使われるすべての命令、算術命令が単離される。それらの命令は（浮動小数点数ではなく）テイラー・モデルに対して作用するよう再定義され、新しい命令への入力がテイラー・モデルに再定義される。次いで第二の命令の組が、法線限界を与えるために実行される。

オブジェクトの集合についてのバウンディング・ボリューム（bounding volume）は、その集合中のオブジェクトの和集合を完全に含む閉じた体積である。バウンディング・ボリュームはさまざまな形、たとえば直方体または長方形のような箱形、球、円柱、ポリトープおよび凸包でありうる。

ある実施形態では、前記基本プリミティブの前記第二の表現を囲むバウンディング・ボリュームが決定され（図３ｂ、ステップ３５０）、バウンディング・ボリュームが選別プロセスにかけられる。選別プロセスについては、ステップ３４０との関連でさらに述べる。

本発明のバウンディング・ボリュームは、緊密なバウンディング・ボリュームである。バウンディング・ボリュームが緊密（tight）であるとは、バウンディング・ボリュームの面積または体積ができる限り小さいが、それでも前記基本プリミティブの前記第二の表現を完全に囲んでいることを含意する。

ある実施形態では、バウンディング・ボリュームは、前記第二の表現の最小および最大を計算することによって決定される（ステップ３５１）。

前記基本プリミティブの前記第二の表現は、冪型のテイラー多項式であってもよい。

バウンディング・ボリュームを決定する一つの方法は、テイラー多項式の導関数を計算し、それにより前記第二の表現の最小および最大を見出すことによってであってもよい。

バウンディング・ボリュームを決定するもう一つの方法は、次のようなものであってもよい。テイラー多項式をベルンシュタイン形式に変換する。ベルンシュタイン基底の凸包属性のために多項式の実際の表面または曲線がベルンシュタイン基底において得られる制御点の凸包内にあることが保証されるという事実のため、バウンディング・ボリュームは、各次元において最小および最大の制御点値を見出すことによって計算される。式(3)をベルンシュタイン基底に変換すると、

となり、ここで、

は、三角形の定義域上での二変量の場合のベルンシュタイン多項式である。この変換は、非特許文献２に記載される次の公式：

を使って実行される。

バウンディング・ボックスを計算するため、単に各次元x,y,z,wについて全p_ijにわたる最小値および最大値が計算される。これがクリップ空間においてバウンディング・ボックス

を与える。ここで、各要素は区間であり、たとえば

である。

ステップ３４０では、基本プリミティブの前記第二の表現は、選別プロセスにかけられる。

選別は、見えないオブジェクトまたはオブジェクト部分を描画するのを避けるために実行される。

従来技術のGPUは、テッセレーションされたポリゴン上で選別を実行する。本発明は、選別を、テッセレーションがそもそも行われる前に実行する。これはパフォーマンスの利得につながる。

このアプローチでは、上記で導出された位置限界、法線限界およびバウンディング・ボリュームは、基本プリミティブに対して異なる選別技法を適用するために使われる。

ある実施形態では、前記位置限界または前記バウンディング・ボリュームを使ってビュー錐台選別が実行される（ステップ３４１、図３ｂ）。

ある実施形態では、前記法線限界、前記位置限界および前記バウンディング・ボリュームの群からの少なくとも一つを使って、裏面選別が実行される（ステップ３４２、図３ｂ）。

ある実施形態では、前記位置限界または前記バウンディング・ボリュームを使って、隠蔽選別が実行される（ステップ３４３、図３ｂ）。

ある実施形態では、ステップ３４１〜３４３の少なくとも一つが実行される。

以下に開示される選別技法は、限定するものと解釈すべきではなく、例として与えられるものである。当業者には、裏面選別、隠蔽選別およびビュー錐台選別が以下に述べるのとは異なるさまざまな技法を使って実行されうることは明らかである。

ビュー錐台選別は、見えるオブジェクト、すなわち現在のビュー錐台内に位置するオブジェクトだけが描画されるという事実に基づく選別技法である。ビュー錐台は、モデル化された世界において、画面上に現れうる空間領域として定義されうる。錐台の外のオブジェクトを描画することは、どうせ見えないので時間と資源の無駄になる。オブジェクトが完全にビュー錐台の外にあれば、そのオブジェクトは見えないので、破棄できる。

ある実施形態では、バウンディング・ボリュームの位置限界が、ビュー錐台の面に対して試験される。バウンディング・ボリューム（＾付きのb）は均一なクリップ空間にあるので、試験はクリップ空間において実行されてもよい。面‐ボックス試験のための標準的な最適化が使用されうる。その場合、バウンディング・ボリュームはバウンディング・ボックスであり、バウンディング・ボリュームの単一のコーナーだけが面方程式を評価するために使われる。その際、各面試験は、加算および比較に帰着する。たとえば、該ボリュームが左面の外側にあるかどうかの試験は、

を使って実行される。この試験は、位置限界

を使って実行されてもよい。これらの試験は時間および資源効率がよいので、ビュー錐台試験を最初の試験とすることは有利である。

裏面選別は、見る者と反対側を向いているオブジェクト、すなわち法線ベクトルが見る者と反対方向であるオブジェクトを破棄する。これらのオブジェクトは可視ではなく、よって描画する必要はない。

面上の点、ベクトルp(u,v)が与えられたとき、裏面選別は、一般に：
c＝p(u,v)・n(u,v) 式(8)
として計算される。ここで、ベクトルn(u,v)は(u,v)における法線ベクトルである。c＞0であれば、ベクトルp(u,v)は(u,v)のその特定の値については裏向きである。よって、この公式は、単一の法線しかもたない三角形全体を選別するために使用されることもできる。ドット積のテイラー・モデル（式(5)および式(8)参照）は：

と計算される。裏面選別ができるには、三角形領域全体にわたって

が成り立つ必要がある。チルダ付きのcに対する下限はここでもまた、ベルンシュタイン形の凸包属性を使って保守的に推定される。これは、区間

を与え、その三角形（これはこの時点ではまだテッセレーションされていない）は、

であれば選別されることができる。

別の実施形態では、裏面条件が満たされているかどうかを検査するために、法線について区間限界（interval bounds）が計算される。

上記試験は、位置限界

または代替的にバウンディング・ボリュームを使って実行されてもよい。

隠蔽選別は、隠蔽されるオブジェクトが破棄されることを含意する。以下では、バウンディング・ボックスについて隠蔽選別を記述するが、当業者には、他の型のバウンディング・ボリュームに対して隠蔽選別を実行することも可能であることは明らかである。

隠蔽選別技法は、奥行きバッファにおいて単一の追加レベルが使われる（8×8ピクセル・タイル）だけであるという点を除いて、階層的奥行きバッファリング（hierarchical depth buffering）とよく似ている。各タイルに、最大奥行き値Z^tile _maxが記憶される。これは、三角形をラスタ化するときに使われる、GPUにおける標準的な技法である。クリップ空間バウンディング・ボックスbは投影され、この軸整列されたボックスに重なるすべてのタイルが訪問される。各タイルにおいて、古典的な隠蔽選抜試験が実行される：Z^box _min≧Z^tile _max。これは、この比較が満たされた場合、そのボックスが現在のタイルのところで隠蔽されることを示す。ボックスの最小奥行きZ^box _minはクリップ空間バウンディング・ボックスから得られ、タイルの最大奥行きZ^tile _maxは階層的奥行きバッファ（これは現在のGPUにすでに存在している）から得られる。タイルが隠蔽されていないと見出されるとすぐに試験は打ち切ることができること、また、階層的奥行きバッファへのさらなるレベルの追加はストレートにできることを注意しておく。隠蔽選別試験は、テッセレーションされるべき三角形のバウンディング・ボックスの非常に安価な前置ラスタ化手段と見ることができる。これはタイル・ベースで作用するので、隠蔽問い合わせほど高価でない。

別の実施形態では、上記試験は、位置限界

を使って実行されてもよい。

ある実施形態では、選別プロセスは置換可能である。これは、基本プリミティブ選別ユニット２１２は、ユーザー定義された選別プロセスを与えられてもよいことを含意する。

選別プロセスを実行するステップ３４０（および３５０）は、種々の帰結をもちうる。ある実施形態では、選別プロセスの帰結は、基本プリミティブが破棄されるべきであるというものであってもよい。別の実施形態では、選別プロセスの帰結は、テッセレーション因子が生成されるというものであってもよい。このテッセレーション因子は、基本プリミティブが破棄されるべきであることを示す値に設定されてもよい。あるいはまた、テッセレーション因子は、基本プリミティブが破棄されることができないことを示す値に設定されてもよい。さらに、テッセレーション因子は、基本プリミティブがテッセレーションされるべきではないことを示す値に設定されてもよい。

ある実施形態では、選別プロセスを実行するステップ３４０（および３５０）ののち、選別プロセスの実行の結果がテッセレータ２１４に送られる。テッセレーション・プロセスが実行される（図３ｂ、ステップ３６０）。テッセレータ２１４が基本プリミティブと、該基本プリミティブがテッセレーションされるべきではないことを示すテッセレーション因子とを受け取る場合、テッセレータは基本プリミティブをテッセレーションしない。

テッセレータ２１４が、選別プロセスにおいて破棄されなかった基本プリミティブを受け取るが、該基本プリミティブがテッセレーションされるべきではないことを示すテッセレーション因子を受け取らない場合は、テッセレータ２１４は基本プリミティブをテッセレーションする。

図３ａおよび３ｂとの関連で述べたステップは、本発明の装置２０５において実行されてもよい。

図４は、図３ａおよび３ｂのステップの結果を示している。図４ａは、基本三角形４０５の形の基本プリミティブを描いている。図４ｂは、バーテックス・シェーダー・ユニット２１６（およびテッセレーション周波数）によって決定される基本三角形４０５にわたる結果として得られる生成された面４１０を示している。図４ｃでは、基本三角形４０５がテイラー形式（多項式４１５および区間残余４２０、４２５）で表されており、こうして面４１０の保守的な推定が得られている。図４ｄでは、テイラー多項式が、効率的な範囲制限（range bounding）のために、（凸包属性を使って）ベルンシュタイン形４３０に展開されている。図４ｅでは、区間残余項４２０、４２５がテイラー・モデルからベルンシュタイン限界４３０に加えられ、こうして保守的な面限界４４５、４５０が得られる。

図５は、図２のディスプレイ・アダプター２０５を具現する典型的な汎用コンピュータ５８３の全体的なアーキテクチャを示している。コンピュータ５８３は、ソフトウェア命令を実行できる、CPUのようなコントローラ５７０を有する。コントローラ５７０は、ランダム・アクセス・メモリ（RAM）のような揮発性メモリ５７１およびディスプレイ・アダプター５００に接続される。このディスプレイ・アダプターは図２のディスプレイ・アダプター２０５に対応する。ディスプレイ・アダプター５００は今度はCRTモニタ、LCDモニタなどといったディスプレイ５７６に接続される。コントローラ５７０は、ハード・ドライブまたはフラッシュ・メモリのような持続性記憶装置５７３およびCD,DVD,HD-DVDもしくはブルーレイのような光メディアの読み出しおよび／または書き込み器のような光学式記憶装置５７４にも接続されている。ローカル・エリア・ネットワーク、広域ネットワーク（たとえばインターネット）、無線ローカル・エリア・ネットワークまたは無線都市圏ネットワークのようなネットワーク５８２へのアクセスを提供するために、ネットワーク・インターフェース５８１もコントローラ５７０に接続されている。周辺インターフェース５７７、たとえばユニバーサル・シリアル・バス（universal serial bus）、無線ユニバーサル・シリアル・バス、ファイアワイヤ（firewire）、RS232シリアル、セントロニクス（Centronics）パラレル、PS/2の型のインターフェースを通じて、コントローラ５７０はマウス５７８、キーボード５７９またはジョイスティック、プリンタ、スキャナなどを含む他の任意の周辺機器と通信できる。

本発明を具現するために上記では汎用コンピュータが記載されているが、本発明は、デジタル・グラフィック、特に3Dグラフィックが利用されるいかなる環境においても、たとえばゲーム・コンソール、携帯電話、MP3プレーヤーなどにおいても、同様によく具現できる。

本発明はさらに、ずっと汎用のアーキテクチャにおいて具現されてもよい。該アーキテクチャは、たとえば、任意の型のプログラムを実行できる多くの小さなプロセッサ・コアからなっていてもよい。これは、よりハードウェア中心のGPUとは対照的に、一種のソフトウェアGPUを含意する。

本発明は、上記で、若干の実施形態を参照して述べてきた。しかしながら、当業者にはすぐ理解されるであろうように、上記に開示されたもの以外の実施形態も、付属の特許請求項によって定義される本発明の範囲内で、同様に可能である。

Claims (14)

1. デジタル表現されたグラフィックの生成方法であって：
   基本プリミティブの第一の表現を受領手段によって受領する段階と；
   前記バーテックス位置決定に関連する命令の組を再定義手段によって有界算術で作用するよう再定義する段階と；
   前記基本プリミティブの前記第一の表現に対して、実行手段によって有界算術を使って前記再定義された命令を実行して、前記基本プリミティブの第二の表現を提供する段階と；
   前記基本プリミティブの前記第二の表現を囲むバウンディング・ボリュームを決定手段によって決定する段階と；
   前記バウンディング・ボリュームを選別手段によって選別プロセスにかける段階とを含む、
   方法。
2. 請求項１記載の方法であって、さらに：
   前記基本プリミティブの前記第一の表現から少なくとも一つのバーテックスを選択手段によって選択する段階と、
   前記少なくとも一つのバーテックスの第一の表現に対して、実行手段によってバーテックス位置決定に関連する命令の組を実行して、前記少なくとも一つのバーテックスの第二の表現を提供する段階と、
   前記少なくとも一つのバーテックスの前記第二の表現を選別手段によって選別プロセスにかける段階とを含み、ここで、前記選別プロセスの結果は
   前記少なくとも一つのバーテックスを選別するという決定および
   前記少なくとも一つのバーテックスを選別しないという決定のうちの一つを含み、
   前記選別プロセスの結果が前記少なくとも一つのバーテックスを選別するという決定を含む場合に：
   基本プリミティブの第一の表現を受領する前記段階；
   バーテックス位置決定に関連する命令の組を提供する前記段階；
   前記基本プリミティブの前記第一の表現に対して、有界算術を使って前記命令の組を実行して、前記基本プリミティブの第二の表現を提供する前記段階；および
   前記基本プリミティブの前記第二の表現を選別プロセスにかける前記段階を実行する、
   方法。
3. 請求項１または２記載の方法であって、さらに、テッセレーション手段によってテッセレーション・プロセスを実行する段階を含み、ここで、前記テッセレーション・プロセスは、前記選別プロセスの結果に基づく、方法。
4. 前記選別プロセスが置換可能である、請求項１ないし３のうちいずれか一項記載の方法。
5. 前記有界算術が、テイラー算術、区間算術およびアフィン算術の群からの少なくとも一つである、請求項１ないし４のうちいずれか一項記載の方法。
6. 請求項１記載の方法であって、前記バウンディング・ボリュームを決定する段階がさらに、前記第二の表現の最小および最大を計算することを含む、方法。
7. 前記第二の表現が、位置限界および法線限界の群からの少なくとも一つである、請求項１ないし６のうちいずれか一項記載の方法。
8. 請求項１記載の方法であって、前記命令の組を実行する段階がさらに：
   バーテックス位置決定に関連する前記命令の組から第二の命令の組を導出する段階と、
   前記第二の命令の組を実行して法線限界を与える段階とを含む、
   方法。
9. 請求項１記載の方法であって、前記バウンディング・ボリュームを前記選別プロセスにかける段階がさらに、
   前記バウンディング・ボリュームをビュー錐台選別にかけること、
   前記バウンディング・ボリュームを裏面選別にかけること、および
   前記バウンディング・ボリュームを隠蔽選別にかけること、
   のうちの少なくとも一つを実行することを含む、方法。
10. 請求項７記載の方法であって、前記第二の表現を前記選別プロセスにかける段階がさらに、
    前記位置限界をビュー錐台選別にかけること、
    前記位置限界または前記法線限界を裏面選別にかけること、および
    前記位置限界を隠蔽選別にかけること、
    のうちの少なくとも一つを実行することを含む、
    方法。
11. 前記選別プロセスの結果が、
    前記基本プリミティブを破棄するという決定および
    テッセレーション因子
    の一つを含む、請求項１ないし１０のうちいずれか一項記載の方法。
12. 請求項１１記載の方法であって、前記選別プロセスの結果がテッセレーション因子を含む場合に、テッセレーション・プロセスを実行することをさらに含む、方法。
13. デジタル表現されたグラフィックを生成するよう適応された装置であって、デジタル表現されたグラフィックの生成のパフォーマンスを改善する回路を有する装置であって、前記回路は：
    基本プリミティブの第一の表現を受領し；
    バーテックス位置決定に関連する命令の組を有界算術で作用するよう再定義し；
    前記基本プリミティブの前記第一の表現に対して、有界算術を使って前記再定義された命令を実行して、前記基本プリミティブの第二の表現を提供し；
    前記基本プリミティブの前記第二の表現を囲むバウンディング・ボリュームを決定し；
    前記バウンディング・ボリュームを選別プロセスにかけるよう適応されている、
    装置。
14. コンピュータ可読記憶媒体上に記憶され、プロセッサに請求項１ないし１２のうちいずれか一項記載の方法を実行させるコンピュータ・プログラム。

Images