配置されたパラメトリック曲線の階層的バウンディング
【課題】相互作用およびリアルタイム描画におけるテセレーションにおいては利用される、配置されたパラメトリック曲線の階層的バウンディング方法を提供する。
【解決手段】パラメトリック曲線から導出された座標フレームを用いてパラメトリック曲線をバウンディングする段階と、前記座標フレームにおける配置ベクトルをバウンディングする段階とを備える。
【解決手段】パラメトリック曲線から導出された座標フレームを用いてパラメトリック曲線をバウンディングする段階と、前記座標フレームにおける配置ベクトルをバウンディングする段階とを備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、概してグラフィックス処理に係り、詳しくは、相互的、リアルタイム、およびオフライン／フィルム描画等の描画システムのテセレーションに係る。
【背景技術】
【０００２】
現代のグラフィックスプロセッサは、多くの小さな三角形に曲線をテセレーションするための専用ハードウェアを含む。ＤｉｒｅｃｔＸ１１アプリケーションプログラミングインタフェース（「ＤＸ１１」）（ＡＰＩ）は、ハルシェーダ、固定機能テセレータ、およびドメインシェーダという３つの新しい段階をグラフィックスパイプラインに加えてテセレーションをサポートしている。ハルシェーダは、パッチごとに一度、および制御ポイントごとに一度実行され、通常は、テセレーション係数の計算および制御ポイントベースの変更に利用されている。固定機能テセレータは、テセレーション係数を入力として利用して、入力プリミティブのドメインにおける大きな頂点位置のセットおよび頂点間の接続情報を生成する。接続情報により多くの小さな三角形が生成される。ドメインシェーダは、テセレータが頂点位置を生成するたびに一度実行される。通常のドメインシェーダの用途は、パラメトリック曲線の位置および法線を、例えば一式の制御ポイント、重心座標および詳細なテクスチャを入力として利用して評価することである。出力は、一式の属性で定義される、配置された頂点である。属性の１つは位置であるが、シェーダはさらに、配置頂点の法線／接線／二重接線／テクスチャ座標／色／透明性その他の属性を算出することもできる。
【図面の簡単な説明】
【０００３】
【図１】コーナ制御ポイントおよびベクトルｂおよびｔを示しており、パッチのコーナ間にベクトルを形成することでＯＢＢ軸を導出することができる。
【図２】上の行の２つの離散配置ピークを有する三次多項式をバウンディングする２５のステップを経て形成されるバウンドの一例を示しており、軸がベジエ曲線の制御ポイントにより決定されるＡＡＢＢを利用する左画像およびＯＢＢを利用する右画像が示され、下の行により配置シェーダにパーリンノイズが加えられている。
【図３】同じ数のサブディビジョンを有するＡＡＢＢ対ＯＢＢバウンディングの三次元の一例を示す。
【図４】左端の画像が正規化前の通常のパッチを示し、中間画像では各制御ポイントが正規化されて単位球体にマッピングされており、最後に右端の画像が、パッチの正規化された保守的なバウンドである法線の錐体によりバウンディングされる投影を示すような、通常のパッチの通常のバウンディング法を示している。
【図５】ＴおよびＢが示す２つのパラメトリック導関数についてバウンディング錐体が与えられた場合に、Ｔ内の任意のベクトルよびＢ内の任意のベクトルの外積をバウンディングする錐体が導出されてＮとして示されることを示している。
【図６】ボックスサイズを、１６個のサブディビジョンステップの実行によりソート基準としてバウンディングするスクリーンスペースを利用する２つの異なるビューを示し、その結果サブディビジョンの密度に生じる差異を示している。
【図７】本発明の一実施形態における配置ベジエ曲線（Bezier surface）パッチのバウンディングおよびバウンディングアルゴリズムを示すフローチャートである。
【図８】一実施形態における配置ベジエパッチのＯＢＢを見つけることにより、配置パッチのバウンドを計算するより詳細なフローを示すフロー図である。
【図９】制御ポイントを利用してベースパッチのＯＢＢを定義する一実施形態を示すフローチャートである。
【図１０】正規化された法線を見つける一実施形態を示すフローチャートである。
【図１１】正規化された法線を見つける別の実施形態を示すフローチャートである。
【図１２】本発明の一実施形態のハードウェアを示す。
【発明を実施するための形態】
【０００４】
ドメインシェーダ評価の数を低減させることで、グラフィックスパイプラインのその段階で必要となる計算リソースが低減される。これは、最終画像に貢献しないパッチをカリングすることにより行うことができる。このカリング処理を効率的に行うべく、配置曲線の階層的バウンドを計算するアルゴリズムを利用することができる。
【０００５】
さらにタイルベースの描画アーキテクチャにおいては、入力プリミティブのバウンドが、入力プリミティブをタイルへと効率的にソートするために必要となる。「バウンディングボリューム」とは、ボックスまたは球体といった、別のオブジェクトを包含する、ボリュームを有するオブジェクトのことである。ドメインシェーダはプログラム可能であるので、出力位置の保守的且つタイトなバウンドを提供することが難しく、これにより、生成された小さな三角形を個々にタイルにソートする必要が生じる。この処理により、タイルキューにおいてメモリ要件が増加して、利用帯域幅が増加し、パッチのプリミティブレベルにおけるオクルージョンカリング処理の効率性が下がる。
【０００６】
この代わりに、これらバウンドは、ユーザが指定するパラメータを利用せずに、ドメインシェーダのみに基づきオンザフライで（ブロック１２）計算することもできる（図７参照）。次いで、プリミティブをより小さなサブパッチへと分割して階層を生成する際にこのバウンドを適合的に改良してよい。一実施形態では、アルゴリズムにより、効率的な正規のバウンディング、配置テクスチャの配向されたバウンディングボックスおよび最小最大ミップマップ階層を利用して、動的配置パラメトリック曲線の保守的且つタイトなバウンディングが実行される（例えばベジエパッチ等）。パッチをカリングする（ブロック１６）。カリングしない場合には、プリミティブをテセレーションおよびドメインシェーディングにかける（ブロック１８）。
【０００７】
パッチをテセレータに送信する必要がないので、一部の実施形態ではパッチにおいてドメインシェーダおよびテセレータ処理の両方が低減しうる。入力パッチをカリングする場合には、一部の実施形態ではテセレーションもドメインシェーディングも行わなくてよい場合もある。同様に、サブパッチをカリングする場合には、一部の実施形態ではこれ以上そのサブパッチに処理を行わないようにすることもできる。そうではない場合には、サブパッチをテセレーションして、ドメインシェーディングにかける。
【０００８】
二重曲線（bi-cubic）ベジエパッチのコレクションは、滑らかな曲線を生成するために行われることの多い描画プリミティブである。公知のアルゴリズムを利用して、カットマル−クラークサブディビジョン曲線をこれらのパラメトリックパッチのコレクションへと変換して、且つ、再帰的なサブディビジョンプロセスの限界面を忠実に近似することができる。通常、高い解像度のテクスチャからの配置をパッチの法線ベクトルの方向に加えることで、最終的な曲線の詳細を増加させている。
【０００９】
配置を有するベジエパッチは、ＡＰＩの描画においてドメインシェーダで利用されてよい。ベジエパッチは、その制御ポイントによりコンパクトに表され、このパラメトリック曲線表現は、（再帰的なサブディビジョン曲線とは異なり）並列に効率的に評価することができる。
【００１０】
ベジエパッチｐ（ｕ，ｖ）は、パラメトリック曲線であり、つまり、２つのパラメトリック座標ｕおよびｖで定義される曲線である。「ベースパッチ」という用語は、まだ配置されていないベジエパッチのことであり、最終的に配置された曲線と区別される。パラメトリック座標（ｕ，ｖ）の配置ベジエパッチを評価するドメインシェーダは、ベースパッチ位置ｐ（ｕ，ｖ）、ベースパッチの正規化された法線
および（通常は）テクスチャからとった配置値ｔ（ｕ，ｖ）を算出する。配置がベースパッチの法線方向に行われている場合には、ドメインシェーダ（モデルビュープロジェクションマトリックスで乗算される前）は、以下のようになる。
【数１】
【００１１】
ｄ（ｕ，ｖ）をモデルビュープロジェクションマトリックスＭで乗算すると、均一な座標でクリップスペース位置ｑが以下のように得られる。
【数２】
【００１２】
正規化されたデバイス座標は、ｓｘ＝ｑｘ／ｑｗおよびｓｙ＝ｑｙ／ｑｗで与えられる。
【００１３】
パラメトリックドメインにおけるｑ（ｕ，ｖ）の保守的なバウンドは、ａ＜＝ｕ＜＝ｂである場合、ｃ＜＝ｖ＜＝ｄとなってよい。
【００１４】
次に、ｐ（ｕ，ｖ）のバウンディング方法を説明する。ベジエパッチは、凸形状のハル特性を有し、その制御ポイントを利用することで簡単にバウンディングすることができる。ベジエパッチについて軸が合わせられたバウンディングボックス（ＡＡＢＢ）を見つけることで、１制御ポイントについて３つの最小処理および３つの最大処理を行うことができる。
【００１５】
ベジエサブディビジョン処理を繰り返すことで、分割されたパッチの制御ポイントケージは、急速にその下にあるベースパッチに向かって収束する。さらに各ステップで元のパッチがｐＡおよびｐＢの２つに再帰的に分割される場合には、ｐＡを生成するために必要となるド・カステリョ処理ステップにより、ｐＢの制御ポイントが副産物として生成される。これは効率的な実装といえよう。
【００１６】
べースパッチ定義された軸の制御ポイントから、配向されたバウンディングボックス（ＯＢＢ）の軸を導出することができる。このボックスは、ＡＡＢＢよりもタイトにベースパッチを包含することができる。同一の反復における分割で生じた２つのパッチ各々について、両ベースパッチ、正規のパッチ、および配置テクスチャおよびルックアップを改良する。図７のブロック１２に示す配置曲線のバウンドを計算するのに利用されるステップを示す図８を参照すると、ベースパッチがある軸沿いにベジエサブディビジョン法を利用して分割されている。ブロック１４に示すベースパッチのバウンディングには、ＯＢＢ軸を制御ポイントから見つけ、全ての制御ポイントをこれらの軸に投影する処理が含まれる。各軸沿いの最小および最大値は、制御ポイントを全て含むＯＢＢを導出するべく配置されており、ベジエパッチの凸形状のハル特性は、曲線がこのＯＢＢに含まれていることを意味している。
【００１７】
次にブロック１５に示すように、配置の最小および最大値を、最小／最大テクスチャ階層で探す。そしてダイアモンド１９で配置がゼロであるか判断する。配置がゼロである場合には、モデルビュープロジェクションをパッチのバウンディングボックスの８つのコーナに適用して（ブロック２０）、バウンドを戻す（ブロック２３）。配置がゼロではない場合には、モデルビュープロジェクション変換を行う（ブロック２０）前に以下にＴＰＡＴＣＨおよびＮＰＡＴＣＨと称して説明される技術の一方を利用して正規のバウンディングをブロック２１で行い、バウンドを戻す（ブロック２３）。最後にブロック２３でモデルビュープロジェクション変換を行う。
【００１８】
ベジエパッチにおいては、コーナ制御ポイント間のベクトル（図１）を合計して２つの軸を得る（図９のブロック２４）。（ｍ＋１）ｘ（ｎ＋１）制御ポイントを有するパッチを想定すると、４つのコーナ制御ポイントＣ０，０、ｃｍ，０，ｃ０，ｎ、およびｃｍ，ｎとなり、以下の２つのベクトルが形成される。
【数３】
【数４】
ｔおよびｂは、それぞれｕおよびｖのパラメトリック方向において適切な平均勾配として考えることができる。これらは直交しない。これらの外積（図９のブロック２６）によって第３の軸「ｎ＝ｂのｔとの外積」が生じる。直交する座標系を形成するべく、ｘ＝ｔ、ｙ＝ｔのｎとの外積、およびｚ＝ｎと設定することで、各ベクトルを正規化する（図９のブロック２８）。最終的に生じる座標系は、
となる。これにより、殆どのケースでＡＡＢＢを利用するときと比べてバウンディングボックスのサイズが低減する。制御ポイントケージに基づいて、より精密なＯＢＢ適合スキームを導出することもできるが、実際には、上述した簡単な方法で、曲線をタイトにバウンディングするＯＢＢの軸を生成することができる。ＡＡＢＢおよびＯＢＢによるバウンディング間の品質の差異は、曲線について図２で強調表示されており、ベジエパッチについて図３で強調表示されている。不完全なケースについては単にＡＡＢＢを利用する。以下に示すように、ＯＢＢ軸も正規のバウンディングアルゴリズムで非常に有用である。
【００１９】
ドメインにおいてパッチ法線
をバウンディングすることは、ベース位置ｐ（ｕ，ｖ）のバウンディングよりもかなり難易度が高い。法線方向は、ベースパッチｐ（ｕ，ｖ）の２つのパラメトリック導関数の外積として計算される。
【００２０】
ベジエ曲線のテンソル積の標準記法に従って、ベジエパッチｐ（ｕ，ｖ）：Ｒ２？Ｒ３が以下のように定義される。
【数５】
上の式においてｃｉ，ｊは制御ポイント、ｍおよびｎはパラメトリック座標ｕおよびｖそれぞれにおけるパッチの度合いを示す。Ｂｉ（ｕ）およびＢｊ（ｖ）は、バーンスタイン多項式である。
【００２１】
偏導関数は以下のように表すことができる。
【数６】
【数７】
ここでは以下が成り立つ。
【数８】
【数９】
【００２２】
ａｉ，ｊ、およびｂｉ，ｊは、ベースパッチの制御ポイント間の（スケーリングされた）差異を表すのでベクトルである。曲線法線（正規化前のもの）は、以下のように定義される。
【数１０】
【００２３】
正規化された法線は以下のようにして求められる。
【数１１】
【００２４】
ｐ（ｕ，ｖ）の二重次数がパラメトリック座標の（ｍ，ｎ）である場合には、第一次パラメトリック導関数は（ｍ−１，ｎ）次および（m，ｎ−１）次である。以下に示すように、パッチの外積をとった後のパッチの二重次数は、（ｍ＋ｎ−１，ｍ＋ｎ−１）となる。従って、双三次ベジエパッチの法線方向を表すパッチによって、二重次数（５，５）を正確に表現する必要が出てくる。
【００２５】
配置を適用するには正規化された法線が必要となる。正規化処理（数式１１）では、副式
を正確に表すために二重次数２（ｍ＋ｎ−１，ｍ＋ｎ−１）が必要となる。双三次ベジエパッチでは、これらの項を、二重次数（１０，１０）ベジエパッチとして正確に表すことができる。多くの場合、この処理は高価なので不可能である（１１・１１＝１２１制御ポイント）。最後に、逆数平方根が、バーンスタイン多項式では正確に表すことができない。加えて、オペランドが法線の長さの二乗であることから、逆数平方根のオペランドは常にゼロ以上ではなくてはならない。この条件を満たさない場合には、ｉｎｆまたはＮａＮが生じうる。従って
のバウンディングされた表現は、厳密にゼロを超える値ではなくてはならない。３つの二乗された項（実数）の合計の平方根がゼロ以上であるべきであることから、一見これは些細なことに思われる。しかし、バウンディングのために制御ポイントケージのバウンディングボックスを利用する実際のケースでは、全ての制御ポイントが正の値をとることは保証できないので、難しい。
【００２６】
以下に、上述した問題の殆どが回避されている法線のバウンディングアルゴリズムを示す。まとめると、法線のベクトルベジエパッチを、パラメトリック導関数から導出して（図１０のブロック３２）、その制御ポイントを単位球体に投影して（図１０のブロック３４）、単位球体におけるその立体角をＯＢＢ座標フレームにバウンディングすることで（図１０のブロック３６）、正規化された法線の保守的なバウンドが得られる。これを法線のバウンディング法ＮＰＡＴＣＨと称する。
【００２７】
法線が以下として定義されたことを想起されたい。
【数１２】
【００２８】
以下はバーンスタイン多項式の積についての公式である。
【数１３】
【００２９】
これを利用すると、数式１２は以下のように表される。
【数１４】
これは、制御ベクトルｖｐ，ｑを有する二重次数（ｍ＋ｎ−１，ｍ＋ｎ−１）のパッチであり、以下のように表すことができる。
【数１５】
【００３０】
パッチにおいてベースパッチの法線を保守的にバウンディングするには、正規化後の法線が単位長を有するという事実を用いることができる。従って制御ベクトルｖｐ，ｑを正規化して、それらを単位球体上のポイントとして表すこととする。
【００３１】
これらバウンドを導出する手っ取り早い方法としては、パッチの法線の近似値であるＯＢＢ座標フレームにおける
軸を利用して、任意の正規化された制御ポイントと
軸との間の最小スカラー積を単に計算する、というものがある。これにより、正規化された方向を包含する錐体の半角のコサイン値が求まる。これは図４に示されている。
【００３２】
双三次ベジエパッチにおいては、ｖｐ，ｑの算出には、１４４個の外積が含まれる。２項式の係数は、小さなルックアップテーブルで予め計算しておくことができる。
【００３３】
しかし、方向がパラメトリック座標に対応する全ての相関が失われることになる。この方法がどのくらいタイトであるかは、非正規の法線が許容範囲内で良好にバウンディングされているか否かにかかっており、これは大きなドメインでは難しくなり、サブドメインが縮小されると容易となる。
【００３４】
より粗いバウンドは、２つの接する錐体を第一次パラメトリック導関数パッチ
の制御ポイントから形成することで、これよりも手っ取り早く得ることができる（数式６および７を参照のこと）。この導関数パッチの制御ポイントは、単位球体上で正規化およびバウンディングされて（図４を参照のこと）、２つの錐体
が形成される。錐体Ｔは、正規化された軸
および半角αｔにより定義される。
【００３５】
錐体ＴおよびＢ同士が重ならない場合には、２つのベクトルについて可能性のある全ての外積をバウンディングする錐体Ｎ
を、各ＴおよびＢから１つずつ構築することができる。軸
は、ｔ×ｂの方向にあり、その半角θは、
【数１６】
で与えられる。 ここで
が、
および
にそれぞれ平行な錐体の軸の間の２つの角度のうちの小さいものに相当する。錐体Ｎは、パッチの全ての正規化された法線をバウンディングする。錐体Ｔ、Ｂ，およびＮを図５に示す。
【００３６】
上述した
および
軸を、錐体ＴおよびＢの軸として利用して、錐体の角度は、パラメトリック導関数のパッチの制御ポイントから錐体ＴおよびＢについて見つけることができる（図１１のブロック４０）。円錐角のコサイン
は単に、
軸とタンジェントパッチからの任意の正規化された制御ポイントとの最小ドット積である。
【００３７】
正規の錐体は、錐体ＴおよびＢの外積の計算により導出される（図１１のブロック４２）。ＯＢＢ座標フレームで表される正規化された法線のバウンドは以下のようになる。
【数１７】
ここで、θは、正規な錐体Ｎの錐体の半角である。等式
を利用することで、三角関数を利用せずとも正規な円錐角を利用して正規化された法線のバウンドを導出することができる（図１１のブロック４４）。この方法をＴＰＡＴＣｈと称する。
【００３８】
２つの接する錐体同士が重ならないように注意を払う必要がある。錐体は、
となる場合に重なり、与えられたαｔ＜ｐｉ、αｂ＜ｐｉ、およびβ＜ｐｉは以下のように書き直すことができる。
【数１８】
【００３９】
この条件が満たされる場合、あるいは、
である場合には、ＯＢＢ座標フレームの単位ボックスを戻す。単位ボックスは２つの極限の頂点（−１，−１，−１）および（＋１，＋１，＋１）を有する。しかし、ＯＢＢ座標フレームがローカル曲線接点、従法線、およびベースパッチの法線の近似から計算されることから、この事象が生じることは、曲線がきついパッチを除いては稀である。
【００４０】
テクスチャルックアップのバウンディング法には、２つの他のミップマップ階層を維持する必要がある。第１のミップマップ階層は、各テクスチャフットプリントおよびレベルの最大配置値を格納し、第２のミップマップ階層は、フットプリントの最小配置値を格納する。概してパラメトリック間隔が低減するとテクスチャバウンドも低減する。
【００４１】
配置ベクトルの最後のバウンドである
は、テクスチャルックアップ［ｔｍｉｎ，ｔｍａｘ］からの間隔を、各軸に沿って正規化された法線ベクトルの間隔倍したものである。表記
を利用して間隔が定義されており、ここで
は下限であり、
は上限であり、２つの間隔の乗算を以下に示す。
【数１９】
【００４２】
従ってｏのｘ成分の間隔のバージョンは以下のようになる。
【数２０】
上式は他の成分についても当てはまる。テクスチャ配置が厳密に正の値である場合には、数式２０をさらに最適化することができる。
【００４３】
殆どのドメインシェーダの最終ステップは、クリップスペースへのマトリックス変換であり、ｑについての取得バウンドの残りの部分はモデルビュープロジェクションマトリックスであり、これはパラメトリックドメインには依存せず、定数とみなすことができる。この、定数であるマトリックスは、配置されたパッチｄから得られるＯＢＢの８つのコーナで簡単に乗算することができ、これによりクリップスペース位置ｑのバウンドが生成される（最終ステップは、予めテセレーションされたソートおよびレイトレーシング用の階層バウンドを利用する場合には不要である）。
【００４４】
パッチに対して最初に粗い分割を行う場合には、一部の実施形態でサブドメインのバウンディングボックスの優先キューを維持することができる。例えばこの代わりに、各サブパッチを、各サブパッチが、ボリューム、表面積、あるいは投影面積等において「十分小さくなるまで」、複数のより小さいサブパッチに分割することができる。以下の各分割ステップでは、キューの最上位エレメントをとりこれをさらに分割して、分割されたボックスをキューに挿入して戻す。
【００４５】
正確なソート基準はアプリケーションに応じて変わり、バウンディングボックスのスクリーンスペースの範囲、深さの値、またはビューフラスタム・カリングのための円台の平面を交差する優先ボックスを含んでよい。図６は、ビューに応じた分割基準を示す。
【００４６】
ビューフラスタム・カリングでは、ＯＢＢコーナ（クリップスペースにおける）を、円台の平面を基準としてテストする。分割基準は、カメラの円台をまたぐサブパッチを優先するよう設計されており、これによりクリップ平面外における配置を効率的にカリングすることができる。パッチのクリップテスト結果も、パッチ全体を完全にビューフラスタム内に収めるように利用することができ、これにより、パッチから形成される三角形のクリップテストをしなくてよい場合もでてくる。
【００４７】
粗い深さのバッファが与えられている場合、サブパッチは、そのバウンディングボックスが既に描画されたプリミティブにより全体的に閉塞されている場合にカリングすることができる。利用される分割基準は、カメラにより近いサブパッチを先ず処理して、パイプラインのラスター処理に送ることでｚカリングの可能性を高める、というものであってよい。
【００４８】
バックフェースカリングは、幾何学上の法線を配置の後に効率的にバウンディングすることが難しいことから、最も難しい種類のカリングである。しかしテセレーション率、正規のバウンドおよびタイトな配置間隔が与えられる場合、配置された曲線法線を導出することができる。さらに分割基準は、法線のばらつきが高い対象パッチに対して適合させることでき、サブパッチのバックフェースカリングの確率を上げることができる。
【００４９】
配置されたベジエパッチのバウンディング表現を計算した後で、予めテセレーションしたタイルへのソートにバウンドを利用することができる。タイルの重なりは、最大のスクリーンスペースを有するバウンディングボックスの階層的分割により低減させることができる。
【００５０】
レイトレーシングが行われる環境では、分割基準は各ＯＢＢの表面積全体を低減させるように適合され、これは表面積における経験則が加速データ構造を構築することと類似している。衝突検知においては、低減されたＯＢＢのボリュームに対して分割基準を適合させる。
【００５１】
階層的なバウンディングボリュームは、カリングにおいて、および、タイルへのソートおよびレイトレーシングにおいて利用可能である。ここで説明する方法を利用することで、電子データをディスプレイに表示するための視覚可能な形態に変換することができる。
【００５２】
ＤＸ−１１テセレーションパイプライン段階を効率的にサポートするべく、タイリングアーキテクチャにおいては、テセレーションおよびドメインシェーディングを行う前に、配置された曲線のバウンドが必要となる。これらのバウンドは、配置されたベジエパッチをテセレーションを行う必要なくビンする（つまり、プリミティブをタイル特定キューへソートすること）ために利用することができる。その後、テセレーションおよびドメインシェーディングを、必要に応じて必要なときに行う。階層的なバウンドの利用はビニング、ビューフラスタム・カリング、オクルージョンカリング、およびバックフェースカリングに有用である。
【００５３】
ここで説明するグラフィックス処理技術は、様々なハードウェアアーキテクチャに実装することができる。例えばグラフィックス機能はチップセット内に集積することができる。あるいは、別個のグラフィックスプロセッサを利用することもできる。また別の実施形態では、グラフィックス機能は汎用プロセッサ（マルチコアプロセッサを含む）により実装されてもよい。
【００５４】
図１２に示すコンピュータシステム１３０は、バス１０４によりチップセットコアロジック１１０に連結されたハードドライブ１３４および取り外し可能媒体１３６を含んでよい。キーボードおよびマウス１２０、あるいはその他の従来のコンポーネントは、チップセットコアロジックへバス１０８を介して連結されていてよい。一実施形態でコアロジックは、グラフィックスプロセッサ１１２に、バス１０５およびメインのホストプロセッサ１００を介して連結されてよい。グラフィックスプロセッサ１１２はさらに、バス１０６を介してフレームバッファ１１４に連結されてよい。フレームバッファ１１４は、バス１０７によりディスプレイスクリーン１１８に連結されてよい。一実施形態では、グラフィックスプロセッサ１１２は、シムド（ＳＩＭＤ）アーキテクチャを利用するマルチスレッド、マルチコアの並列プロセッサであってよい。
【００５５】
ソフトウェア実装の場合には、関連コードを任意の適切な半導体、磁気、または光学メモリに（例えば、メインメモリ１３２、またはグラフィックスプロセッサ内の利用可能なメモリに）格納してよい。従って一実施形態では、図７から図１１に示すシーケンスを実行するコードを、機械またはコンピュータ可読媒体（例えばメモリ１３２またはグラフィックスプロセッサ１１２）に格納することができ、一実施形態においてはプロセッサ１００またはグラフィックスプロセッサ１１２により実行可能であってよい。
【００５６】
図８から図１１はフローチャートである。一部の実施形態では、これらフローチャートに示したシーケンスはハードウェア、ソフトウェア、またはファームウェアにより実装することができる。ソフトウェアによる実施形態では、半導体メモリ、磁気メモリ、または光学メモリ等のコンピュータ可読媒体を利用して命令を格納し、プロセッサにより実行されると、図８から図１１に示すフローチャートのうち１以上に示されるシーケンスを実行してよい。
【００５７】
本明細書において「一実施形態」「１つの実施形態」といった言い回しは、その実施形態との関連で記載された特定の特徴、構造、または特性が、本発明の範囲内である少なくとも１つの実装例に含まれていることを意味する。従って「一実施形態」「１つの実施形態」といった言い回しは必ずしも同じ実施形態を表さない。さらに特定の特徴、構造、または特性は、例示された特定の実施形態以外の他の適切な形態で実装することもでき、本願の請求項にはこれら全ての形態が含まれるものとする。
【００５８】
本発明を限られた数の実施形態に関して説明してきたが、当業者にとってはこれに基づく数多くの変形例が明らかである。添付請求項は、本発明の真の精神および範囲内に含まれるこれら全ての変形例および変更例を含むことを意図している。
【技術分野】
【０００１】
本願は、概してグラフィックス処理に係り、詳しくは、相互的、リアルタイム、およびオフライン／フィルム描画等の描画システムのテセレーションに係る。
【背景技術】
【０００２】
現代のグラフィックスプロセッサは、多くの小さな三角形に曲線をテセレーションするための専用ハードウェアを含む。ＤｉｒｅｃｔＸ１１アプリケーションプログラミングインタフェース（「ＤＸ１１」）（ＡＰＩ）は、ハルシェーダ、固定機能テセレータ、およびドメインシェーダという３つの新しい段階をグラフィックスパイプラインに加えてテセレーションをサポートしている。ハルシェーダは、パッチごとに一度、および制御ポイントごとに一度実行され、通常は、テセレーション係数の計算および制御ポイントベースの変更に利用されている。固定機能テセレータは、テセレーション係数を入力として利用して、入力プリミティブのドメインにおける大きな頂点位置のセットおよび頂点間の接続情報を生成する。接続情報により多くの小さな三角形が生成される。ドメインシェーダは、テセレータが頂点位置を生成するたびに一度実行される。通常のドメインシェーダの用途は、パラメトリック曲線の位置および法線を、例えば一式の制御ポイント、重心座標および詳細なテクスチャを入力として利用して評価することである。出力は、一式の属性で定義される、配置された頂点である。属性の１つは位置であるが、シェーダはさらに、配置頂点の法線／接線／二重接線／テクスチャ座標／色／透明性その他の属性を算出することもできる。
【図面の簡単な説明】
【０００３】
【図１】コーナ制御ポイントおよびベクトルｂおよびｔを示しており、パッチのコーナ間にベクトルを形成することでＯＢＢ軸を導出することができる。
【図２】上の行の２つの離散配置ピークを有する三次多項式をバウンディングする２５のステップを経て形成されるバウンドの一例を示しており、軸がベジエ曲線の制御ポイントにより決定されるＡＡＢＢを利用する左画像およびＯＢＢを利用する右画像が示され、下の行により配置シェーダにパーリンノイズが加えられている。
【図３】同じ数のサブディビジョンを有するＡＡＢＢ対ＯＢＢバウンディングの三次元の一例を示す。
【図４】左端の画像が正規化前の通常のパッチを示し、中間画像では各制御ポイントが正規化されて単位球体にマッピングされており、最後に右端の画像が、パッチの正規化された保守的なバウンドである法線の錐体によりバウンディングされる投影を示すような、通常のパッチの通常のバウンディング法を示している。
【図５】ＴおよびＢが示す２つのパラメトリック導関数についてバウンディング錐体が与えられた場合に、Ｔ内の任意のベクトルよびＢ内の任意のベクトルの外積をバウンディングする錐体が導出されてＮとして示されることを示している。
【図６】ボックスサイズを、１６個のサブディビジョンステップの実行によりソート基準としてバウンディングするスクリーンスペースを利用する２つの異なるビューを示し、その結果サブディビジョンの密度に生じる差異を示している。
【図７】本発明の一実施形態における配置ベジエ曲線（Bezier surface）パッチのバウンディングおよびバウンディングアルゴリズムを示すフローチャートである。
【図８】一実施形態における配置ベジエパッチのＯＢＢを見つけることにより、配置パッチのバウンドを計算するより詳細なフローを示すフロー図である。
【図９】制御ポイントを利用してベースパッチのＯＢＢを定義する一実施形態を示すフローチャートである。
【図１０】正規化された法線を見つける一実施形態を示すフローチャートである。
【図１１】正規化された法線を見つける別の実施形態を示すフローチャートである。
【図１２】本発明の一実施形態のハードウェアを示す。
【発明を実施するための形態】
【０００４】
ドメインシェーダ評価の数を低減させることで、グラフィックスパイプラインのその段階で必要となる計算リソースが低減される。これは、最終画像に貢献しないパッチをカリングすることにより行うことができる。このカリング処理を効率的に行うべく、配置曲線の階層的バウンドを計算するアルゴリズムを利用することができる。
【０００５】
さらにタイルベースの描画アーキテクチャにおいては、入力プリミティブのバウンドが、入力プリミティブをタイルへと効率的にソートするために必要となる。「バウンディングボリューム」とは、ボックスまたは球体といった、別のオブジェクトを包含する、ボリュームを有するオブジェクトのことである。ドメインシェーダはプログラム可能であるので、出力位置の保守的且つタイトなバウンドを提供することが難しく、これにより、生成された小さな三角形を個々にタイルにソートする必要が生じる。この処理により、タイルキューにおいてメモリ要件が増加して、利用帯域幅が増加し、パッチのプリミティブレベルにおけるオクルージョンカリング処理の効率性が下がる。
【０００６】
この代わりに、これらバウンドは、ユーザが指定するパラメータを利用せずに、ドメインシェーダのみに基づきオンザフライで（ブロック１２）計算することもできる（図７参照）。次いで、プリミティブをより小さなサブパッチへと分割して階層を生成する際にこのバウンドを適合的に改良してよい。一実施形態では、アルゴリズムにより、効率的な正規のバウンディング、配置テクスチャの配向されたバウンディングボックスおよび最小最大ミップマップ階層を利用して、動的配置パラメトリック曲線の保守的且つタイトなバウンディングが実行される（例えばベジエパッチ等）。パッチをカリングする（ブロック１６）。カリングしない場合には、プリミティブをテセレーションおよびドメインシェーディングにかける（ブロック１８）。
【０００７】
パッチをテセレータに送信する必要がないので、一部の実施形態ではパッチにおいてドメインシェーダおよびテセレータ処理の両方が低減しうる。入力パッチをカリングする場合には、一部の実施形態ではテセレーションもドメインシェーディングも行わなくてよい場合もある。同様に、サブパッチをカリングする場合には、一部の実施形態ではこれ以上そのサブパッチに処理を行わないようにすることもできる。そうではない場合には、サブパッチをテセレーションして、ドメインシェーディングにかける。
【０００８】
二重曲線（bi-cubic）ベジエパッチのコレクションは、滑らかな曲線を生成するために行われることの多い描画プリミティブである。公知のアルゴリズムを利用して、カットマル−クラークサブディビジョン曲線をこれらのパラメトリックパッチのコレクションへと変換して、且つ、再帰的なサブディビジョンプロセスの限界面を忠実に近似することができる。通常、高い解像度のテクスチャからの配置をパッチの法線ベクトルの方向に加えることで、最終的な曲線の詳細を増加させている。
【０００９】
配置を有するベジエパッチは、ＡＰＩの描画においてドメインシェーダで利用されてよい。ベジエパッチは、その制御ポイントによりコンパクトに表され、このパラメトリック曲線表現は、（再帰的なサブディビジョン曲線とは異なり）並列に効率的に評価することができる。
【００１０】
ベジエパッチｐ（ｕ，ｖ）は、パラメトリック曲線であり、つまり、２つのパラメトリック座標ｕおよびｖで定義される曲線である。「ベースパッチ」という用語は、まだ配置されていないベジエパッチのことであり、最終的に配置された曲線と区別される。パラメトリック座標（ｕ，ｖ）の配置ベジエパッチを評価するドメインシェーダは、ベースパッチ位置ｐ（ｕ，ｖ）、ベースパッチの正規化された法線
および（通常は）テクスチャからとった配置値ｔ（ｕ，ｖ）を算出する。配置がベースパッチの法線方向に行われている場合には、ドメインシェーダ（モデルビュープロジェクションマトリックスで乗算される前）は、以下のようになる。
【数１】
【００１１】
ｄ（ｕ，ｖ）をモデルビュープロジェクションマトリックスＭで乗算すると、均一な座標でクリップスペース位置ｑが以下のように得られる。
【数２】
【００１２】
正規化されたデバイス座標は、ｓｘ＝ｑｘ／ｑｗおよびｓｙ＝ｑｙ／ｑｗで与えられる。
【００１３】
パラメトリックドメインにおけるｑ（ｕ，ｖ）の保守的なバウンドは、ａ＜＝ｕ＜＝ｂである場合、ｃ＜＝ｖ＜＝ｄとなってよい。
【００１４】
次に、ｐ（ｕ，ｖ）のバウンディング方法を説明する。ベジエパッチは、凸形状のハル特性を有し、その制御ポイントを利用することで簡単にバウンディングすることができる。ベジエパッチについて軸が合わせられたバウンディングボックス（ＡＡＢＢ）を見つけることで、１制御ポイントについて３つの最小処理および３つの最大処理を行うことができる。
【００１５】
ベジエサブディビジョン処理を繰り返すことで、分割されたパッチの制御ポイントケージは、急速にその下にあるベースパッチに向かって収束する。さらに各ステップで元のパッチがｐＡおよびｐＢの２つに再帰的に分割される場合には、ｐＡを生成するために必要となるド・カステリョ処理ステップにより、ｐＢの制御ポイントが副産物として生成される。これは効率的な実装といえよう。
【００１６】
べースパッチ定義された軸の制御ポイントから、配向されたバウンディングボックス（ＯＢＢ）の軸を導出することができる。このボックスは、ＡＡＢＢよりもタイトにベースパッチを包含することができる。同一の反復における分割で生じた２つのパッチ各々について、両ベースパッチ、正規のパッチ、および配置テクスチャおよびルックアップを改良する。図７のブロック１２に示す配置曲線のバウンドを計算するのに利用されるステップを示す図８を参照すると、ベースパッチがある軸沿いにベジエサブディビジョン法を利用して分割されている。ブロック１４に示すベースパッチのバウンディングには、ＯＢＢ軸を制御ポイントから見つけ、全ての制御ポイントをこれらの軸に投影する処理が含まれる。各軸沿いの最小および最大値は、制御ポイントを全て含むＯＢＢを導出するべく配置されており、ベジエパッチの凸形状のハル特性は、曲線がこのＯＢＢに含まれていることを意味している。
【００１７】
次にブロック１５に示すように、配置の最小および最大値を、最小／最大テクスチャ階層で探す。そしてダイアモンド１９で配置がゼロであるか判断する。配置がゼロである場合には、モデルビュープロジェクションをパッチのバウンディングボックスの８つのコーナに適用して（ブロック２０）、バウンドを戻す（ブロック２３）。配置がゼロではない場合には、モデルビュープロジェクション変換を行う（ブロック２０）前に以下にＴＰＡＴＣＨおよびＮＰＡＴＣＨと称して説明される技術の一方を利用して正規のバウンディングをブロック２１で行い、バウンドを戻す（ブロック２３）。最後にブロック２３でモデルビュープロジェクション変換を行う。
【００１８】
ベジエパッチにおいては、コーナ制御ポイント間のベクトル（図１）を合計して２つの軸を得る（図９のブロック２４）。（ｍ＋１）ｘ（ｎ＋１）制御ポイントを有するパッチを想定すると、４つのコーナ制御ポイントＣ０，０、ｃｍ，０，ｃ０，ｎ、およびｃｍ，ｎとなり、以下の２つのベクトルが形成される。
【数３】
【数４】
ｔおよびｂは、それぞれｕおよびｖのパラメトリック方向において適切な平均勾配として考えることができる。これらは直交しない。これらの外積（図９のブロック２６）によって第３の軸「ｎ＝ｂのｔとの外積」が生じる。直交する座標系を形成するべく、ｘ＝ｔ、ｙ＝ｔのｎとの外積、およびｚ＝ｎと設定することで、各ベクトルを正規化する（図９のブロック２８）。最終的に生じる座標系は、
となる。これにより、殆どのケースでＡＡＢＢを利用するときと比べてバウンディングボックスのサイズが低減する。制御ポイントケージに基づいて、より精密なＯＢＢ適合スキームを導出することもできるが、実際には、上述した簡単な方法で、曲線をタイトにバウンディングするＯＢＢの軸を生成することができる。ＡＡＢＢおよびＯＢＢによるバウンディング間の品質の差異は、曲線について図２で強調表示されており、ベジエパッチについて図３で強調表示されている。不完全なケースについては単にＡＡＢＢを利用する。以下に示すように、ＯＢＢ軸も正規のバウンディングアルゴリズムで非常に有用である。
【００１９】
ドメインにおいてパッチ法線
をバウンディングすることは、ベース位置ｐ（ｕ，ｖ）のバウンディングよりもかなり難易度が高い。法線方向は、ベースパッチｐ（ｕ，ｖ）の２つのパラメトリック導関数の外積として計算される。
【００２０】
ベジエ曲線のテンソル積の標準記法に従って、ベジエパッチｐ（ｕ，ｖ）：Ｒ２？Ｒ３が以下のように定義される。
【数５】
上の式においてｃｉ，ｊは制御ポイント、ｍおよびｎはパラメトリック座標ｕおよびｖそれぞれにおけるパッチの度合いを示す。Ｂｉ（ｕ）およびＢｊ（ｖ）は、バーンスタイン多項式である。
【００２１】
偏導関数は以下のように表すことができる。
【数６】
【数７】
ここでは以下が成り立つ。
【数８】
【数９】
【００２２】
ａｉ，ｊ、およびｂｉ，ｊは、ベースパッチの制御ポイント間の（スケーリングされた）差異を表すのでベクトルである。曲線法線（正規化前のもの）は、以下のように定義される。
【数１０】
【００２３】
正規化された法線は以下のようにして求められる。
【数１１】
【００２４】
ｐ（ｕ，ｖ）の二重次数がパラメトリック座標の（ｍ，ｎ）である場合には、第一次パラメトリック導関数は（ｍ−１，ｎ）次および（m，ｎ−１）次である。以下に示すように、パッチの外積をとった後のパッチの二重次数は、（ｍ＋ｎ−１，ｍ＋ｎ−１）となる。従って、双三次ベジエパッチの法線方向を表すパッチによって、二重次数（５，５）を正確に表現する必要が出てくる。
【００２５】
配置を適用するには正規化された法線が必要となる。正規化処理（数式１１）では、副式
を正確に表すために二重次数２（ｍ＋ｎ−１，ｍ＋ｎ−１）が必要となる。双三次ベジエパッチでは、これらの項を、二重次数（１０，１０）ベジエパッチとして正確に表すことができる。多くの場合、この処理は高価なので不可能である（１１・１１＝１２１制御ポイント）。最後に、逆数平方根が、バーンスタイン多項式では正確に表すことができない。加えて、オペランドが法線の長さの二乗であることから、逆数平方根のオペランドは常にゼロ以上ではなくてはならない。この条件を満たさない場合には、ｉｎｆまたはＮａＮが生じうる。従って
のバウンディングされた表現は、厳密にゼロを超える値ではなくてはならない。３つの二乗された項（実数）の合計の平方根がゼロ以上であるべきであることから、一見これは些細なことに思われる。しかし、バウンディングのために制御ポイントケージのバウンディングボックスを利用する実際のケースでは、全ての制御ポイントが正の値をとることは保証できないので、難しい。
【００２６】
以下に、上述した問題の殆どが回避されている法線のバウンディングアルゴリズムを示す。まとめると、法線のベクトルベジエパッチを、パラメトリック導関数から導出して（図１０のブロック３２）、その制御ポイントを単位球体に投影して（図１０のブロック３４）、単位球体におけるその立体角をＯＢＢ座標フレームにバウンディングすることで（図１０のブロック３６）、正規化された法線の保守的なバウンドが得られる。これを法線のバウンディング法ＮＰＡＴＣＨと称する。
【００２７】
法線が以下として定義されたことを想起されたい。
【数１２】
【００２８】
以下はバーンスタイン多項式の積についての公式である。
【数１３】
【００２９】
これを利用すると、数式１２は以下のように表される。
【数１４】
これは、制御ベクトルｖｐ，ｑを有する二重次数（ｍ＋ｎ−１，ｍ＋ｎ−１）のパッチであり、以下のように表すことができる。
【数１５】
【００３０】
パッチにおいてベースパッチの法線を保守的にバウンディングするには、正規化後の法線が単位長を有するという事実を用いることができる。従って制御ベクトルｖｐ，ｑを正規化して、それらを単位球体上のポイントとして表すこととする。
【００３１】
これらバウンドを導出する手っ取り早い方法としては、パッチの法線の近似値であるＯＢＢ座標フレームにおける
軸を利用して、任意の正規化された制御ポイントと
軸との間の最小スカラー積を単に計算する、というものがある。これにより、正規化された方向を包含する錐体の半角のコサイン値が求まる。これは図４に示されている。
【００３２】
双三次ベジエパッチにおいては、ｖｐ，ｑの算出には、１４４個の外積が含まれる。２項式の係数は、小さなルックアップテーブルで予め計算しておくことができる。
【００３３】
しかし、方向がパラメトリック座標に対応する全ての相関が失われることになる。この方法がどのくらいタイトであるかは、非正規の法線が許容範囲内で良好にバウンディングされているか否かにかかっており、これは大きなドメインでは難しくなり、サブドメインが縮小されると容易となる。
【００３４】
より粗いバウンドは、２つの接する錐体を第一次パラメトリック導関数パッチ
の制御ポイントから形成することで、これよりも手っ取り早く得ることができる（数式６および７を参照のこと）。この導関数パッチの制御ポイントは、単位球体上で正規化およびバウンディングされて（図４を参照のこと）、２つの錐体
が形成される。錐体Ｔは、正規化された軸
および半角αｔにより定義される。
【００３５】
錐体ＴおよびＢ同士が重ならない場合には、２つのベクトルについて可能性のある全ての外積をバウンディングする錐体Ｎ
を、各ＴおよびＢから１つずつ構築することができる。軸
は、ｔ×ｂの方向にあり、その半角θは、
【数１６】
で与えられる。 ここで
が、
および
にそれぞれ平行な錐体の軸の間の２つの角度のうちの小さいものに相当する。錐体Ｎは、パッチの全ての正規化された法線をバウンディングする。錐体Ｔ、Ｂ，およびＮを図５に示す。
【００３６】
上述した
および
軸を、錐体ＴおよびＢの軸として利用して、錐体の角度は、パラメトリック導関数のパッチの制御ポイントから錐体ＴおよびＢについて見つけることができる（図１１のブロック４０）。円錐角のコサイン
は単に、
軸とタンジェントパッチからの任意の正規化された制御ポイントとの最小ドット積である。
【００３７】
正規の錐体は、錐体ＴおよびＢの外積の計算により導出される（図１１のブロック４２）。ＯＢＢ座標フレームで表される正規化された法線のバウンドは以下のようになる。
【数１７】
ここで、θは、正規な錐体Ｎの錐体の半角である。等式
を利用することで、三角関数を利用せずとも正規な円錐角を利用して正規化された法線のバウンドを導出することができる（図１１のブロック４４）。この方法をＴＰＡＴＣｈと称する。
【００３８】
２つの接する錐体同士が重ならないように注意を払う必要がある。錐体は、
となる場合に重なり、与えられたαｔ＜ｐｉ、αｂ＜ｐｉ、およびβ＜ｐｉは以下のように書き直すことができる。
【数１８】
【００３９】
この条件が満たされる場合、あるいは、
である場合には、ＯＢＢ座標フレームの単位ボックスを戻す。単位ボックスは２つの極限の頂点（−１，−１，−１）および（＋１，＋１，＋１）を有する。しかし、ＯＢＢ座標フレームがローカル曲線接点、従法線、およびベースパッチの法線の近似から計算されることから、この事象が生じることは、曲線がきついパッチを除いては稀である。
【００４０】
テクスチャルックアップのバウンディング法には、２つの他のミップマップ階層を維持する必要がある。第１のミップマップ階層は、各テクスチャフットプリントおよびレベルの最大配置値を格納し、第２のミップマップ階層は、フットプリントの最小配置値を格納する。概してパラメトリック間隔が低減するとテクスチャバウンドも低減する。
【００４１】
配置ベクトルの最後のバウンドである
は、テクスチャルックアップ［ｔｍｉｎ，ｔｍａｘ］からの間隔を、各軸に沿って正規化された法線ベクトルの間隔倍したものである。表記
を利用して間隔が定義されており、ここで
は下限であり、
は上限であり、２つの間隔の乗算を以下に示す。
【数１９】
【００４２】
従ってｏのｘ成分の間隔のバージョンは以下のようになる。
【数２０】
上式は他の成分についても当てはまる。テクスチャ配置が厳密に正の値である場合には、数式２０をさらに最適化することができる。
【００４３】
殆どのドメインシェーダの最終ステップは、クリップスペースへのマトリックス変換であり、ｑについての取得バウンドの残りの部分はモデルビュープロジェクションマトリックスであり、これはパラメトリックドメインには依存せず、定数とみなすことができる。この、定数であるマトリックスは、配置されたパッチｄから得られるＯＢＢの８つのコーナで簡単に乗算することができ、これによりクリップスペース位置ｑのバウンドが生成される（最終ステップは、予めテセレーションされたソートおよびレイトレーシング用の階層バウンドを利用する場合には不要である）。
【００４４】
パッチに対して最初に粗い分割を行う場合には、一部の実施形態でサブドメインのバウンディングボックスの優先キューを維持することができる。例えばこの代わりに、各サブパッチを、各サブパッチが、ボリューム、表面積、あるいは投影面積等において「十分小さくなるまで」、複数のより小さいサブパッチに分割することができる。以下の各分割ステップでは、キューの最上位エレメントをとりこれをさらに分割して、分割されたボックスをキューに挿入して戻す。
【００４５】
正確なソート基準はアプリケーションに応じて変わり、バウンディングボックスのスクリーンスペースの範囲、深さの値、またはビューフラスタム・カリングのための円台の平面を交差する優先ボックスを含んでよい。図６は、ビューに応じた分割基準を示す。
【００４６】
ビューフラスタム・カリングでは、ＯＢＢコーナ（クリップスペースにおける）を、円台の平面を基準としてテストする。分割基準は、カメラの円台をまたぐサブパッチを優先するよう設計されており、これによりクリップ平面外における配置を効率的にカリングすることができる。パッチのクリップテスト結果も、パッチ全体を完全にビューフラスタム内に収めるように利用することができ、これにより、パッチから形成される三角形のクリップテストをしなくてよい場合もでてくる。
【００４７】
粗い深さのバッファが与えられている場合、サブパッチは、そのバウンディングボックスが既に描画されたプリミティブにより全体的に閉塞されている場合にカリングすることができる。利用される分割基準は、カメラにより近いサブパッチを先ず処理して、パイプラインのラスター処理に送ることでｚカリングの可能性を高める、というものであってよい。
【００４８】
バックフェースカリングは、幾何学上の法線を配置の後に効率的にバウンディングすることが難しいことから、最も難しい種類のカリングである。しかしテセレーション率、正規のバウンドおよびタイトな配置間隔が与えられる場合、配置された曲線法線を導出することができる。さらに分割基準は、法線のばらつきが高い対象パッチに対して適合させることでき、サブパッチのバックフェースカリングの確率を上げることができる。
【００４９】
配置されたベジエパッチのバウンディング表現を計算した後で、予めテセレーションしたタイルへのソートにバウンドを利用することができる。タイルの重なりは、最大のスクリーンスペースを有するバウンディングボックスの階層的分割により低減させることができる。
【００５０】
レイトレーシングが行われる環境では、分割基準は各ＯＢＢの表面積全体を低減させるように適合され、これは表面積における経験則が加速データ構造を構築することと類似している。衝突検知においては、低減されたＯＢＢのボリュームに対して分割基準を適合させる。
【００５１】
階層的なバウンディングボリュームは、カリングにおいて、および、タイルへのソートおよびレイトレーシングにおいて利用可能である。ここで説明する方法を利用することで、電子データをディスプレイに表示するための視覚可能な形態に変換することができる。
【００５２】
ＤＸ−１１テセレーションパイプライン段階を効率的にサポートするべく、タイリングアーキテクチャにおいては、テセレーションおよびドメインシェーディングを行う前に、配置された曲線のバウンドが必要となる。これらのバウンドは、配置されたベジエパッチをテセレーションを行う必要なくビンする（つまり、プリミティブをタイル特定キューへソートすること）ために利用することができる。その後、テセレーションおよびドメインシェーディングを、必要に応じて必要なときに行う。階層的なバウンドの利用はビニング、ビューフラスタム・カリング、オクルージョンカリング、およびバックフェースカリングに有用である。
【００５３】
ここで説明するグラフィックス処理技術は、様々なハードウェアアーキテクチャに実装することができる。例えばグラフィックス機能はチップセット内に集積することができる。あるいは、別個のグラフィックスプロセッサを利用することもできる。また別の実施形態では、グラフィックス機能は汎用プロセッサ（マルチコアプロセッサを含む）により実装されてもよい。
【００５４】
図１２に示すコンピュータシステム１３０は、バス１０４によりチップセットコアロジック１１０に連結されたハードドライブ１３４および取り外し可能媒体１３６を含んでよい。キーボードおよびマウス１２０、あるいはその他の従来のコンポーネントは、チップセットコアロジックへバス１０８を介して連結されていてよい。一実施形態でコアロジックは、グラフィックスプロセッサ１１２に、バス１０５およびメインのホストプロセッサ１００を介して連結されてよい。グラフィックスプロセッサ１１２はさらに、バス１０６を介してフレームバッファ１１４に連結されてよい。フレームバッファ１１４は、バス１０７によりディスプレイスクリーン１１８に連結されてよい。一実施形態では、グラフィックスプロセッサ１１２は、シムド（ＳＩＭＤ）アーキテクチャを利用するマルチスレッド、マルチコアの並列プロセッサであってよい。
【００５５】
ソフトウェア実装の場合には、関連コードを任意の適切な半導体、磁気、または光学メモリに（例えば、メインメモリ１３２、またはグラフィックスプロセッサ内の利用可能なメモリに）格納してよい。従って一実施形態では、図７から図１１に示すシーケンスを実行するコードを、機械またはコンピュータ可読媒体（例えばメモリ１３２またはグラフィックスプロセッサ１１２）に格納することができ、一実施形態においてはプロセッサ１００またはグラフィックスプロセッサ１１２により実行可能であってよい。
【００５６】
図８から図１１はフローチャートである。一部の実施形態では、これらフローチャートに示したシーケンスはハードウェア、ソフトウェア、またはファームウェアにより実装することができる。ソフトウェアによる実施形態では、半導体メモリ、磁気メモリ、または光学メモリ等のコンピュータ可読媒体を利用して命令を格納し、プロセッサにより実行されると、図８から図１１に示すフローチャートのうち１以上に示されるシーケンスを実行してよい。
【００５７】
本明細書において「一実施形態」「１つの実施形態」といった言い回しは、その実施形態との関連で記載された特定の特徴、構造、または特性が、本発明の範囲内である少なくとも１つの実装例に含まれていることを意味する。従って「一実施形態」「１つの実施形態」といった言い回しは必ずしも同じ実施形態を表さない。さらに特定の特徴、構造、または特性は、例示された特定の実施形態以外の他の適切な形態で実装することもでき、本願の請求項にはこれら全ての形態が含まれるものとする。
【００５８】
本発明を限られた数の実施形態に関して説明してきたが、当業者にとってはこれに基づく数多くの変形例が明らかである。添付請求項は、本発明の真の精神および範囲内に含まれるこれら全ての変形例および変更例を含むことを意図している。
【特許請求の範囲】
【請求項１】
配置されたパラメトリック曲線をバウンディングする方法であって、
前記パラメトリック曲線から導出された座標フレームを用いてパラメトリック曲線をバウンディングする段階と、
前記座標フレームにおける配置ベクトルをバウンディングする段階と
を備える方法。
【請求項２】
配置された前記パラメトリック曲線の階層的バウンドを計算する段階を備える請求項１に記載の方法。
【請求項３】
アプリケーションが定義する優先メトリックにより前記パラメトリック曲線をより小さなサブパッチに分割するときに、バウンドを適合的に改良する段階を備える請求項２に記載の方法。
【請求項４】
前記バウンディングには、位置、法線、およびテクスチャに関するバウンドを改良することが含まれる請求項３に記載の方法。
【請求項５】
アプリケーションが定義する閾値に達するまでベジエ分割を繰り返し適用する段階を備える請求項４に記載の方法。
【請求項６】
コーナ制御ポイントのベクトル間の平均をとって２つの軸を得て、前記２つの軸の外積をとり、各ベクトルを正規化してオブジェクト指向のバウンディングボックス座標フレームを形成する段階を備える請求項１に記載の方法。
【請求項７】
パラメータ導関数から正規のベクトルベジエパッチを導出して、単位球体上に制御ポイントを投影して、オブジェクト指向のバウンディングボックス座標フレームの単位球体上に立体角をバウンディングして前記パッチにベースパッチの正規化された法線のバウンドを与える段階を備える請求項６に記載の方法。
【請求項８】
ベースパッチの正規化された法線のバウンドを導出するために錐体を利用する段階を備える請求項６に記載の方法。
【請求項９】
１つのパラメトリック方向における導関数から第１の錐体を形成して、異なるパラメトリック方向における導関数から第２の錐体を形成して、前記座標フレームにおける前記第１の錐体および前記第２の錐体の外積を計算することで第３の錐体を形成する段階を備える請求項６に記載の方法。
【請求項１０】
サブパッチのカリング、テセレーション、およびドメインシェーディングを行う段階を備える請求項１に記載の方法。
【請求項１１】
取得した前記バウンドを利用することで、スクリーンスペースのタイルに、より高次のプリミティブをソートする段階を備える請求項１に記載の方法。
【請求項１２】
レイトレーシング用にバウンディングボリューム階層を構築する段階を備える請求項１に記載の方法。
【請求項１３】
前記曲線をコンピュータディスプレイに表示可能な視覚形態に変換する段階を備える請求項１に記載の方法。
【請求項１４】
プロセッサと、
前記プロセッサに連結されて、パラメトリック曲線を、前記パラメトリック曲線から導出された座標フレームを用いてバウンディングして、前記座標フレームにおける配置ベクトルをバウンディングするストレージと
を備える装置。
【請求項１５】
配置された前記パラメトリック曲線のバウンディングから生じる画像を表示するディスプレイを備える請求項１４に記載の装置。
【請求項１６】
前記ストレージは、配置された前記パラメトリック曲線の階層バウンドを計算する命令を格納する請求項１４に記載の装置。
【請求項１７】
前記ストレージは、アプリケーションが定義する優先メトリックにより前記パラメトリック曲線をより小さなサブパッチに分割するときに、バウンドを適合的に改良する命令を格納する請求項１６に記載の装置。
【請求項１８】
前記ストレージは、位置、法線、およびテクスチャに関するバウンドを改良する命令を格納する請求項１６に記載の装置。
【請求項１９】
前記ストレージは、アプリケーションが定義する閾値に達するまでベジエ分割を繰り返し適用する命令を格納する請求項１８に記載の装置。
【請求項２０】
前記ストレージは、コーナ制御ポイントのベクトル間の平均をとって２つの軸を得て、前記２つの軸の外積をとり、各ベクトルを正規化してオブジェクト指向のバウンディングボックス座標フレームを形成する命令を格納する請求項１４に記載の装置。
【請求項１】
配置されたパラメトリック曲線をバウンディングする方法であって、
前記パラメトリック曲線から導出された座標フレームを用いてパラメトリック曲線をバウンディングする段階と、
前記座標フレームにおける配置ベクトルをバウンディングする段階と
を備える方法。
【請求項２】
配置された前記パラメトリック曲線の階層的バウンドを計算する段階を備える請求項１に記載の方法。
【請求項３】
アプリケーションが定義する優先メトリックにより前記パラメトリック曲線をより小さなサブパッチに分割するときに、バウンドを適合的に改良する段階を備える請求項２に記載の方法。
【請求項４】
前記バウンディングには、位置、法線、およびテクスチャに関するバウンドを改良することが含まれる請求項３に記載の方法。
【請求項５】
アプリケーションが定義する閾値に達するまでベジエ分割を繰り返し適用する段階を備える請求項４に記載の方法。
【請求項６】
コーナ制御ポイントのベクトル間の平均をとって２つの軸を得て、前記２つの軸の外積をとり、各ベクトルを正規化してオブジェクト指向のバウンディングボックス座標フレームを形成する段階を備える請求項１に記載の方法。
【請求項７】
パラメータ導関数から正規のベクトルベジエパッチを導出して、単位球体上に制御ポイントを投影して、オブジェクト指向のバウンディングボックス座標フレームの単位球体上に立体角をバウンディングして前記パッチにベースパッチの正規化された法線のバウンドを与える段階を備える請求項６に記載の方法。
【請求項８】
ベースパッチの正規化された法線のバウンドを導出するために錐体を利用する段階を備える請求項６に記載の方法。
【請求項９】
１つのパラメトリック方向における導関数から第１の錐体を形成して、異なるパラメトリック方向における導関数から第２の錐体を形成して、前記座標フレームにおける前記第１の錐体および前記第２の錐体の外積を計算することで第３の錐体を形成する段階を備える請求項６に記載の方法。
【請求項１０】
サブパッチのカリング、テセレーション、およびドメインシェーディングを行う段階を備える請求項１に記載の方法。
【請求項１１】
取得した前記バウンドを利用することで、スクリーンスペースのタイルに、より高次のプリミティブをソートする段階を備える請求項１に記載の方法。
【請求項１２】
レイトレーシング用にバウンディングボリューム階層を構築する段階を備える請求項１に記載の方法。
【請求項１３】
前記曲線をコンピュータディスプレイに表示可能な視覚形態に変換する段階を備える請求項１に記載の方法。
【請求項１４】
プロセッサと、
前記プロセッサに連結されて、パラメトリック曲線を、前記パラメトリック曲線から導出された座標フレームを用いてバウンディングして、前記座標フレームにおける配置ベクトルをバウンディングするストレージと
を備える装置。
【請求項１５】
配置された前記パラメトリック曲線のバウンディングから生じる画像を表示するディスプレイを備える請求項１４に記載の装置。
【請求項１６】
前記ストレージは、配置された前記パラメトリック曲線の階層バウンドを計算する命令を格納する請求項１４に記載の装置。
【請求項１７】
前記ストレージは、アプリケーションが定義する優先メトリックにより前記パラメトリック曲線をより小さなサブパッチに分割するときに、バウンドを適合的に改良する命令を格納する請求項１６に記載の装置。
【請求項１８】
前記ストレージは、位置、法線、およびテクスチャに関するバウンドを改良する命令を格納する請求項１６に記載の装置。
【請求項１９】
前記ストレージは、アプリケーションが定義する閾値に達するまでベジエ分割を繰り返し適用する命令を格納する請求項１８に記載の装置。
【請求項２０】
前記ストレージは、コーナ制御ポイントのベクトル間の平均をとって２つの軸を得て、前記２つの軸の外積をとり、各ベクトルを正規化してオブジェクト指向のバウンディングボックス座標フレームを形成する命令を格納する請求項１４に記載の装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１１−２３８２１３（Ｐ２０１１−２３８２１３Ａ）
【公開日】平成２３年１１月２４日（２０１１．１１．２４）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１１−８４８３５（Ｐ２０１１−８４８３５）
【出願日】平成２３年４月６日（２０１１．４．６）
【出願人】（５９１００３９４３）インテル・コーポレーション (1,101)
【Ｆターム（参考）】
【公開日】平成２３年１１月２４日（２０１１．１１．２４）
【国際特許分類】
【出願番号】特願２０１１−８４８３５（Ｐ２０１１−８４８３５）
【出願日】平成２３年４月６日（２０１１．４．６）
【出願人】（５９１００３９４３）インテル・コーポレーション (1,101)
【Ｆターム（参考）】
[ Back to top ]