(57)【特許請求の範囲】
【請求項１】
３−Ｄシーンの２−Ｄ表示をレイトレーシングする方法であって、
プロセッサによって実行されるインストラクションを含むシェーダルーチンを実行するプロセッサにおいて、
光線の起点及び方向を定義するデータを含むデータ構造と、インスタンス化された光線を追跡すべき前記起点からの最大距離を示すクリッピング情報を提供することにより、シーンプリミティブ及びシーン加速構造の要素を含む幾何学的オブジェクトとの交差に関してテストする前記光線をインスタンス化するステップと、
前記インスタンス化された光線の交差テストを開始する前に、前記データ構造をコンピュータ可読媒体に記憶するステップと、
を含み、交差テスタにおいて、
前記コンピュータ可読媒体からの前記データ構造にアクセスして前記光線の起点及び目標を取得するステップと、
前記クリッピング情報により示される前記最大距離内にある幾何学的オブジェクトとのみの交差に関して前記光線をテストするステップと、
前記光線といずれかのテストされたシーンプリミティブとの間の識別された交差の指示を出力するステップと、
を含むことを特徴とする方法。
【請求項２】
シェーダルーチンを実行するプロセッサにおいて、前記１又はそれ以上のデフォルトの幾何学的オブジェクトを前記光線に関連付けるステップと、前記１又はそれ以上のデフォルトの幾何学的オブジェクトに関連する１つ以上の光線シェーダを実行させることによって、前記光線に関して識別された交差が前記最大距離内に存在しない場合、前記光線を前記１又はそれ以上のデフォルトオブジェクトと交差したものとして処理するステップとをさらに含む、
ことを特徴とする請求項１に記載の方法。
【請求項３】
前記１又はそれ以上のデフォルトの幾何学的オブジェクトが、光線ごとに光線固有のデフォルトオブジェクトの代用とすることができるグローバルデフォルトオブジェクトを含む、
ことを特徴とする請求項２に記載の方法。
【請求項４】
個々の光線の前記それぞれのクリッピング情報が、前記光線の起点情報を使用してラインセグメント定義を導き出すために使用できる３−Ｄ空間内の位置を示す情報を含む、
ことを特徴とする請求項１から請求項３のいずれか１項に記載の方法。
【請求項５】
前記シェーダルーチンが、複数の光線の前記インスタンス化ステップを実施し、前記光線データ構造が、前記複数の光線の定義データを含む、
ことを特徴とする請求項１から請求項４のいずれか１項に記載の方法。
【請求項６】
前記光線データ構造内に１又はそれ以上のフラグの組を提供するステップをさらに含み、フラグの各セットに対して、それぞれのフラグが、フラグの組ごとに、前記光線データ構造内で定義される少なくとも１つの光線に関連付けられ、個々のフラグが、
（１）交差された１つのオブジェクトが前記光線に関連するデフォルトオブジェクト以外である場合にのみ該関連する光線に対する交差が指示されるべきであるということ、
（２）前記デフォルトオブジェクトが前記光線によっていつ交差されたか、いつ前記光線が他のオブジェクトに交差していないことが判明したかについての指示が出力されるべきであるということ、
（３）交差テスト中に前記光線を前記交差テスタによって処理することを指示すること、
（４）シェーディングリソースが前記交差テスタによる出力のために望む指示の内容を指示すること、
を含む組から選択された１つを示すためのものである、
ことを特徴とする請求項１に記載の方法。
【請求項７】
前記光線データ構造が、前記クリッピング情報を表すデフォルトオブジェクト識別子をさらに含む、
ことを特徴とする請求項１から請求項６のいずれか１項に記載の方法。
【請求項８】
前記光線データ構造に記憶されたデータをどのように解釈すべきかを示すフラグの組を記憶するステップをさらに含む、
ことを特徴とする請求項１から請求項５のいずれか１項に記載の方法。
【請求項９】
前記交差テスタが、マルチスレッドＣＰＵにおいて実行されるスレッド、ともにパッケージ化された物理的に別個のコア、プロセッサ間通信のために結合された複数の物理的に異なる処理リソース、及び固定関数テストセルのうちの１又はそれ以上のいずれかを含む、
ことを特徴とする請求項１から請求項８のいずれか１項に記載の方法。
【請求項１０】
レイトレーシングのためのシステムであって、
複数の幾何学形状から構成される３−Ｄシーンの交差テスト中に識別される幾何学形状に関連する、光線の交差テストを制限する前記３−Ｄシーンのサブポーションを定義するデータを含む光線定義データを有するデータ構造を実行時にインスタンス化するシェーダルーチンのためのコンピュータ可読命令で構成された第１のプロセッサと、
前記データ構造を受け取り、前記３−Ｄシーンのサブポーション内に存在する前記３−Ｄシーンを構成する幾何学形状との交差に関して前記光線をテストし、前記光線と前記シーンを構成する形状との間に最も近い交差が存在する場合にはこの交差の指示を与える交差テスタと、
を含むことを特徴とするシステム。
【請求項１１】
前記データ構造が、前記ポーションを、光線の起点で開始して前記３−Ｄシーン内の別のポイントへ延びるラインセグメントとして定義するデータをさらに含む、
ことを特徴とする請求項１０に記載のシステム。
【請求項１２】
前記命令が、実行時に、デフォルトオブジェクトの幾何学形状を定義するデータを前記データ構造内でさらに提供し、前記３−Ｄシーンの前記サブポーション内で他の幾何学的オブジェクトが交差されなかったと判定された場合、前記交差テスタが、前記デフォルトオブジェクトが交差されたという指示を前記シェーダルーチンにさらに提供する、
ことを特徴とする請求項１０に記載のシステム。
【請求項１３】
前記シーンを構成する前記幾何学形状の部分が加速構造の要素により境界され、前記第１のプロセッサが、個々の光線を前記３−Ｄシーンのサブポーション内の前記加速構造の要素のみとテストするための命令でさらに構成される、
ことを特徴とする請求項１０に記載のシステム。
【請求項１４】
レイトレーシングの方法を実施するためのコンピュータ実行可能命令を記憶するコンピュータ可読媒体であって、前記方法が、
別の光線と３−Ｄシーンを構成するプリミティブとの交点に基づいて決定された起点を有する光線のインスタンス化を引き起こすステップと、
前記光線の、該光線に光線固有のクリッピング距離及びデフォルト交差オブジェクトを関連付けるデータ構造をコンピュータ可読媒体内に提供するステップと、
前記光線が、前記データ構造からアクセスされる前記光線の起点と、前記クリッピング距離内の前記光線の方向に沿ったポイントとの間で前記シーンを構成するいずれのプリミティブとも交差しないと判定するステップと、
前記判定ステップに応答して、前記光線が前記デフォルト交差オブジェクトに交差したという指示を戻すステップと、
を含むことを特徴とするコンピュータ可読媒体。
【請求項１５】
前記判定ステップが、前記複数のプリミティブの選択を各々が境界する階層的加速構造の要素を使用して、所与の要素により境界されたいずれかのプリミティブが前記クリッピング距離内に存在するかどうかを判定するステップと、存在しない場合、交差テスタが、前記要素により境界されたプリミティブ又はその他の要素のいずれかのさらなる交差テストを行わないようにするステップとをさらに含む、
ことを特徴とする請求項１４に記載のコンピュータ可読媒体。
【請求項１６】
プロセッサ上でシェーダルーチンの実行中において前記インスタンス化するステップがシェーダルーチンによって行われ、前記デフォルトオブジェクトが前記シーン内の光源であり、前記光線が、前記交点が前記光源から光を受光しないようになっているかどうかを判定するためのものである、
ことを特徴とする請求項１４に記載のコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
〔関連出願との相互参照〕
本出願は、２００９年９月８日に出願された「光線固有のクリッピングを使用したレイトレーシング」という名称の米国特許出願第１２／５５５，６７８号、及び２００８年９月９日に出願された「光線固有のクリッピングを使用したレイトレーシング」という名称の米国仮出願第６１／０９５，５７０号、及び２００８年９月２２日、２００８年１０月１日、及び２００９年４月２４日にそれぞれ出願された、全て「非再帰的レイトレーシングのためのシェーダＡＰＩ」という名称の米国仮出願第６１／０９９，１５２号、６１／１０１，８５４号、及び６１／１７２，４５３号からの優先権を主張するものであり、上記出願は全てその全体が引用により本明細書に組み入れられる。
【０００２】
以下の発明は、一般にコンピュータグラフィクスに関し、より詳細には、レイトレーシングを使用して３−Ｄシーンの２−Ｄ表現による描画を加速化することに関する。
【背景技術】
【０００３】
コンピュータグラフィクス技術では、レイトレーシングを使用して３−Ｄシーン記述からフォトリアリスティックな２−Ｄ画像を描画することが周知である。
【０００４】
通常、レイトレーシングでは、シーン内の構造体の表面を記述する三角形などの幾何プリミティブで構成されたシーン記述を取得する。このプリミティブを、プリミティブに当たる光がプリミティブの品質によってどのように影響を受けるかをコンピュータに指示するテクスチャ及びその他の情報に関連付けることができる。換言すれば、物理的環境モデルが作成され、このモデルを、人間にとってなじみのある写実的な状態の結果を生み出すように設計することができ、或いは望む通りの他の結果を実現するように設計することができる。レイトレーシングでは、シーンの要素と相互作用する光の物理的動作をモデル化することができるので、写実的な影及び照明効果を含むフォトリアリスティックな画像を作成することができる。しかしながら、レイトレーシングは計算が集中的なものになることも知られており、現在のところ、最先端のグラフィクスワークステーションでさえ、レイトレーシングを使用して複雑なシーンを描画するのにかなりの時間を必要とし、レイトレーシングを使用したリアルタイムな高品質及び高解像度の描画は依然として実現が難しい。
【０００５】
ほとんどの実際のシーンは光源を含む（より一般的には、例えばＸ線、赤外線などのいずれかの種類のエネルギー源のモデルを含むことができる）。この光源がシーン内のオブジェクトを照射する。通常、シーンは、シーンクリップ距離としても知られているシーン境界によって識別できる何らかの境界された領域内に定められるという点で、シーン記述は所定の限度に達する。次に、カメラ又はその他の起点から光線を発して、（例えば、別のオブジェクトの影になっているオブジェクトの特定のポイントなどの）あらゆる数の状態をテストする。
【０００６】
このような光線が、プリミティブ又は光源などのシーンオブジェクトと交差したことが確認されるまで、或いは光線がシーン境界まで追跡されるまでシーン内で追跡される。そして、別のプリミティブとの交差が存在する場合、その交点の状態に関する情報を収集するためにさらなる光線を発することができる。光源が交差された場合、この光源からの光エネルギーを光線の起点にぶつかるように定めることができる。色及び強度などの様々な光の属性を考慮することができる。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上記は全て、エネルギー源を有するシーンを介して導かれるエネルギー伝播のコンピュータベースのモデル、及び異なる質感、色、回折、及び反射特性などの質の異なり得る様々なオブジェクトについて説明したものである。従って、このようなモデルから得られる結果が望ましいものであるかどうかは、ハードウェア、及びソフトウェアがハードウェアをどのように使用するかを含む、モデルを実現するために使用する計算リソースの的確さ及び精度に依存する。一定量の的確さ及び精度からいずれかのより良い結果を得られる、或いは少ない計算で所望の結果を得られる方法及びシステムが望まれており、以下のいくつかの態様は、レイトレーシングシステムにおけるこのような目標及びその他の改善に取り組むものである。
【課題を解決するための手段】
【０００８】
態様は、３−Ｄシーンの２−Ｄ表現を描画するためのレイトレーシングなどのレイトレーシングの方法を含む。方法は、シーンのプリミティブ及び形状加速データの要素を含む幾何学的オブジェクトとの交差をテストするために複数の光線をインスタンス化するステップを含む。方法は、個々の関連する光線を追跡すべきそれぞれの起点からの最大距離を示すそれぞれのクリッピング情報を複数の光線の各々に関連付けるステップを含む。方法はまた、クリッピング情報により特定される最大距離内で幾何学的オブジェクトとのみ交差する個々の複数の光線をテストするステップも含む。方法はまた、個々の光線といずれかのテストされるシーンプリミティブとの間のいずれかの最も近い識別された交差のそれぞれの指示を出力するステップも含む。
【０００９】
態様は、レイトレーシングを使用して３−Ｄシーンの２−Ｄ表現を描画するためのシステムも含み、このシステムは、シェーダルーチンのためのコンピュータ可読命令とともに構成された第１の処理リソースを含む。シェーダルーチンは、複数の幾何学形状で構成された３−Ｄシーンの交差テスト中に識別された幾何学形状に関連付けられ、シェーダルーチンのための命令が、実行時に、光線定義データを有するデータ構造をインスタンス化する。光線定義データは、光線の交差テストを制限すべき３−Ｄシーンのサブポーションを定めるデータを含む。システムはまた、データ構造を受信し、３−Ｄシーンのサブポーション内に存在する３−Ｄシーンを構成する幾何学形状との交差に関して光線をテストし、光線とシーンを構成する形状との間に最も近い交差が存在する場合にはこの交差の指示を与える交差テストリソースも含む。
【００１０】
さらなる態様は、レイトレーシングを使用して３−Ｄシーンから２−Ｄ画像を描画するのに有用な交差テスト演算を実施するための計算リソースを含む。この計算リソースは、３−Ｄシーン内で交差テストを受ける光線を表すデータと、光線固有のクリッピング情報とを取得する１又はそれ以上のインターフェイスも含む。光線固有のクリッピング情報は、光線の起点を使用して、その光線の交差テストを制限すべき範囲を定める。インターフェイスは、光線との交差をテストする形状を定めるデータを取得するためのものでもある。
【００１１】
計算リソースはまた、この形状がテストする光線の範囲内に存在するかどうかを、取得したクリッピング情報に基づいて判定するように構成された交差テスト制限回路と、形状がその範囲内に存在すると制限回路が判定したことに応答して光線との交差に関して形状をテストし、形状と光線の間の検出された交差の指示を出力するように構成された交差テスト回路とを含む。この回路は、ソフトウェアをプログラムされた汎用ハードウェア、カスタマイズされた又は部分的にカスタマイズされたハードウェア、並びにこれらの組み合わせを含むことができる。いずれかの所与の実施構成に望ましい場合、この回路を複数の物理的な位置の間で分散することもできる。
【００１２】
さらなる態様は、レイトレーシングを使用して３−Ｄシーンの２−Ｄ表現を描画する方法を含み、この方法は、プリミティブで構成された３−Ｄシーン内で交差テストを受ける複数の光線をインスタンス化するステップを含む。方法は、それぞれのクリッピングデータを複数の光線の各々に関連付けるステップも含む。方法はまた、個々の光線をテストするためのプリミティブの最終グループに到達するために、次第に小さくなるプリミティブのグループをそれぞれ境界する形状加速データの要素の編成を光線ごとにトラバースするステップも含み、このトラバースするステップは、所与の要素が、クリッピングデータから取得できる最大テスト距離内に存在するかどうかを判定するステップを含む。方法は、そのプリミティブの最終グループとの交差に関して個々の光線をテストするステップと、光線ごとの最も近い検出した交差を含む交差テスト結果を報告するステップとをさらに含む。
【００１３】
さらなる態様は、レイトレーシングを使用して３−Ｄシーンの２−Ｄ表現を描画するのに有用な方法を含む。この方法は、３−Ｄシーンを構成する複数のプリミティブのうちの第１のプリミティブに第１の光線が交差したという指示を受け取るステップと、第１の光線と第１のプリミティブとの交差に近い起点を有する第２の光線のインスタンス化を引き起こすステップと、第２の光線にクリッピング距離及びデフォルト交差オブジェクトを関連付けるステップとを含む。方法は、第２の光線が、第２の光線の起点と第２の光線の方向に沿ったクリッピング距離内のポイントとの間で、シーンを構成するいずれのプリミティブとも交差しないと判定するステップと、この判定ステップに応答して、第２の光線がデフォルト交差オブジェクトに交差したという指示を戻すステップとをさらに含む。
【００１４】
さらなる態様は、３−Ｄ空間内に位置し、プリミティブの選択をそれぞれ境界するプリミティブと形状加速データの要素とを含む幾何学形状に基づいて、レイトレーシングベースの２−Ｄ表現の描画で使用する方法を含む。この方法は、起点データ及びシーンクリップ距離とは無関係な光線固有のクリップ距離により部分的に定められる光線のインスタンス化を引き起こすステップと、光線固有のクリップ距離よりも光線の起点に近い幾何学形状とのみの交差に関して光線をテストするステップを含む。
【００１５】
さらに別の態様は、レイトレーシングベースの３−Ｄシーン描画において光線と幾何学形状との間の検出された交差をシェーディングするのに有用な方法を実施するためのコンピュータ可読命令を記憶するコンピュータ可読媒体を含む。この方法は、第１の光線定義データを使用して、交差シェーディングのために構成された第１の計算リソース内で、幾何学形状で構成された３−Ｄシーン内の交差に関してテストされる第１の光線を定義するステップを含む。光線定義データは、第１の光線の起点と、１又はそれ以上のフラグと、交差に関して同時にテストできる他の光線から第１の光線を一意に識別する識別子とを含む。
【００１６】
方法は、第１の光線定義データを第１のメモリに記憶するステップと、幾何学形状との交差に関して光線をテストするように構成された第２の計算リソースに第１の光線の識別子を提供するステップとを含む。方法はまた、第２の計算リソースに対して、第１のメモリから第１の光線定義データを取り出すステップと、第１の光線を少なくとも１つの幾何学形状でテストするステップとを含む。方法はまた、第１の光線と幾何学形状のいずれかとの交差を検出したことに応答して、１又はそれ以上のフラグを使用して第２の計算リソースからの出力の内容を決定するステップも含む。
【００１７】
さらに別の態様は、レイトレーシングベースの３−Ｄシーン描画において光線と幾何学形状との間の検出された交差をシェーディングするのに有用な方法を実施するためのコンピュータ可読命令を記憶するコンピュータ可読媒体も含む。この方法は、３−Ｄシーン内で交差テストを受ける光線を識別するシェーダルーチンからの交差テスト要求を受け入れるステップを含む。方法はまた、交差テストを制限すべきシーンのサブポーションを示す情報を交差テスト要求から取得するステップと、シーンを構成するプリミティブの選択を識別するステップと、識別された光線とこれらの交差テストを設定する前に、このようなプリミティブの選択がシーンのサブポーション内に存在するかどうかを判定するステップとを含む。
【００１８】
さらに別の態様は、シェーダが方法を実施するためのコンピュータ可読命令を記憶するコンピュータ可読媒体を含む。この方法は、３−Ｄシーン内で交差テストを受ける光線を定義するステップと、この光線の光線固有のクリッピング距離を選択するステップとを含む。クリッピング距離は、３−Ｄシーンに関して定義されたグローバルクリッピング距離とは異なる。光線固有のクリッピング距離は、光線の交差テストを光線の起点とそのクリッピング距離との間に制限するように選択される。方法はまた、光線の交差テストを、この光線固有のクリッピング距離を使用して設定するステップも含む。
【００１９】
詳細な説明では以下の図を参照する。
【図面の簡単な説明】
【００２０】
【図１】現在開示している主題を使用することができるアーキテクチャ例であり、レイトレーシングのための他のシステムアーキテクチャにも応用することができる、レイトレーシングのためのシステムアーキテクチャを示す図である。
【図２】いくつかの実施構成において図１のシステムの部分をどのように結合できるかを示す図である。
【図３Ａ】図４〜図９の態様を説明するために使用するプリミティブ及び形状加速データ要素を含むシーンを示す図である。
【図３Ｂ】図４〜図９の態様を説明するために使用するプリミティブ及び形状加速データ要素を含むシーンを示す図である。
【図４】図３Ａの加速データ要素及びプリミティブの編成例を示す図である。
【図５】本明細書で開示する方法及びその他の態様を実現するためのデータを有する光線のデータ構造を示す図である。
【図６】方法のステップを示す図である。
【図７】図６の方法の一部を実施するために使用できる別の方法のステップを示す図である。
【図８】同様に図６の態様を実現できる別の方法のステップを示す図である。
【図９】開示する態様による、形状加速要素の編成のトラバースに関する別の方法のステップを示す図である。
【図１０】上述のあらゆる態様を実現できる、複数の処理要素を含むシステム実施構成例の態様を示す図である。
【発明を実施するための形態】
【００２１】
以下の説明は、当業者が本発明の様々な実施及び使用できるようにするために提示するものである。特定の技術、実施構成及び用途についての説明は、一例として行うものにすぎない。当業者には、本明細書で説明する例に対する様々な修正が明らかになると思われ、本発明の範囲から逸脱することなく、本明細書で定義する一般原理を他の例及び用途にも適用することができる。
【００２２】
説明を明確にするために、（三角形の３つの頂点の座標などの）プリミティブのような、ある種のオブジェクトに関するデータについては、オブジェクトに関するデータを示すのではなくオブジェクト自体として単純に説明する。例えば、「光線をインスタンス化する」という場合、この光線を物理的に実現することではなく、光線を表すデータを生成することであると理解されたい。
【００２３】
以下の図は、レイトレーシングを使用して３−Ｄシーンの２−Ｄ表現を描画するためのシステム及びその一部の例を示すものである。このような描画のための２つの主成分は、光線を追跡して交差を識別すること、及び識別した交差にシェーディングを行うことである。一般的には、機能ユニットのいずれかの機能又は義務のいずれかを複数のハードウェアユニット、又は複数のソフトウェア、ソフトウェアサブルーチンの形で実現することができ、異なるコンピュータ上で実行することもできる。場合によっては、このような実施構成がシステム機能に関連し得る場合、これについても詳細に説明する。
【００２４】
背景技術で述べたように、３−Ｄシーンを２−Ｄ画面上に表示するには、これを２−Ｄ表現に変換する必要がある。このような変換では、シーンを映すカメラ位置を選択することができる。カメラ位置は、シーンの視聴者の場所（ゲーマー、アニメ動画を観ている人、ホログラフィー画像のスライスの起点など）を表すことが多い。通常、２−Ｄ表現は、２−Ｄ表現が所望の解像度の画素の配列を含むようにカメラとシーンの間の平面の場所に存在する。個々の画素の色ベクトルは描画を通じて決定される。レイトレーシング中、最初にカメラ位置から光線を投じて２−Ｄ表現の平面に所望のポイントで交差させ、その後３−Ｄシーンへと続けることができる。
【００２５】
本明細書のいくつかの実施構成では、光線が２−Ｄ表現に交差する場所を、その光線に関連するデータ構造内に保存することができる。カメラ光線の交差が検出された場合、この交差の検出に応答してさらなる交差テストを行わなければならない。例えば、その交点にどの光が当たっているかを特定しなければならず、この特定は、光源が別のオブジェクトの陰になっているかどうかのテストを含むことができる。交差した形状の表面の質により、交差の検出に応答して何を行う必要があるかが少なくとも部分的に決定される。例えば、（ガラスなどの）透明な物質と交差した場合、不透明な物質と交差した場合とは異なる光線を発する必要があり得る。交差が検出されたときに何が起きるかは、（便宜的にそのオブジェクトのシェーダと呼ぶ）コンピュータコード、及びオブジェクトの交差に関連するその他のデータにより大部分が決定される。
【００２６】
図１は、プリミティブで構成されたシーンをレイトレーシングする際に使用するシステムの態様を示している。図１に示す要素は、いずれもハードウェア及び／又はソフトウェアの１又はそれ以上の異なる部分として実現することができる。
【００２７】
システム１００が、ジオメトリユニット１０１、交差テストユニット１０９、交差処理ユニット１０２、及びサンプル処理リソース１１０を含み、必要に応じてこれらをハードウェア及び／又はソフトウェアの形で実現することができる。ジオメトリユニット１０１、交差テストユニット１０９、交差処理ユニット１０２、及びサンプル処理ユニット１１０の各々を、ビデオカード、又はその他の外部又は内部コンピュータシステム周辺機器上で具体化することもできる。リンク１１８が、光線データ１０５と交差テストユニット１０９との間の通信を実現する。交差テストユニット１０９は、リンク１１２によりプリミティブ及びＧＡＤストレージ１０３から幾何学形状データを受け取る。場合によっては、プリミティブ及びＧＡＤストレージ１０３を、サンプルデータ、（シェーダルーチンなどの）光線シェーディングデータ１０７、及びテクスチャデータ１０８などのその他のデータを記憶するメインメモリの形で実現して、光線データストレージ１０５と分離することができる。
【００２８】
図１では、説明するユニットのいずれかを、ユニット機能を表すソフトウェア、コンピュータ実行可能命令の形で少なくとも部分的に実現する実施形態を、例えば、磁気又は光学ディスク、フラッシュメモリ、ＵＳＢデバイスなどの記録可能な種類のコンピュータ可読に記憶することができる。識別されたユニットの性質に応じて、リンク１１８及び１１２などの図１のその他の機能を様々な方法で実現することができる。例えば、交差テストユニット１０９が、１又はそれ以上のＣＰＵで実行される複数のスレッドを含む場合、リンク１１８が、光線データストレージ１０５へのアクセスを提供するための、このような（単複の）ＣＰＵ及び適当なメモリコントローラハードウェア／ファームウェア／ソフトウェアの物理的メモリアクセスリソースを含むことができる。
【００２９】
交差テストユニット１０９は、光線に対して幾何学形状をテストできる１又はそれ以上の（テストセルとしても知られる）個別のテストリソースを含む。個々のテストセルは、所与の光線が所与のプリミティブに交差したかどうかの指示を含むことができるテスト結果を生むことができる。一般的には、システムコンポーネントは、所与の特定の光線テストの未知の完了までの時間をサポートするように設計される。要約すれば、交差テストユニット１０９は、ジオメトリメモリへのアクセスを読み取り、光線を参照する待ち行列を入力として有する。交差テストの出力通りに、個々の光線を最初に交差した形状に関連付けることができる。
【００３０】
図２は、図１の交差処理リソース１０２及び交差テストリソース１０９を含むハイレベルのアーキテクチャを示している。交差処理リソース１０２及び交差テストリソース１０９は、交差処理１０２から交差テスト１０９へ送信される光線／光線ＩＤのための待ち行列、及び交差テスト結果の指示を交差テスト１０９から交差処理１０２へ送信するための待ち行列２０３に結合される。待ち行列２０２は、交差処理１０２で実行されるシェーダによってインスタンス化される光線又は光線識別子を提供し、待ち行列２０３は、光線識別子及び最初に交差された幾何学形状（例えば、プリミティブ）を含む指示を与える。
【００３１】
図３Ａは、三角形プリミティブ（場合によっては、三角形プリミティブ片）で構成される２−Ｄシーン例、及び三角形プリミティブの選択が（「ＧＡＤ」とも呼ばれる）形状加速データの要素により境界される場所を示している。明確にするために図３Ａを２−Ｄで示しているが、開示する原理は一般に３−Ｄシーンにも適用される。
【００３２】
プリミティブの（何十万又は何百万又はそれ以上などの）多くでシーンを構成できるので、ＧＡＤの要素を使用して、シーン内の１又はそれ以上のプリミティブ（又はアブストラクティング）の境界を近似させ、プリミティブのグループをさらなるテストのために識別（或いはさらなるテストのために除外）できるようにすることにより交差テストを加速化することができる。
【００３３】
一般に、ＧＡＤ要素は、３−Ｄ空間内でそれぞれのプリミティブの一群を囲む幾何学形状を含み、これにより幾何学形状の表面が光線と交差しなければ、光線が、形状により境界されるいずれのプリミティブとも交差しないことも示すようになる。ＧＡＤ要素は、球体、軸合わせしたバウンディングボックス、ｋｄ−ツリー、オクトリー、及びその他の種類のバウンディングボリューム階層を含むことができる。ＧＡＤ要素は、主に光線とプリミティブの交差をより迅速に識別するためにプリミティブを抽象化するのに有用であるため、これらは光線との交差を容易にテストできる形状であることが好ましい。
【００３４】
図３Ａの例では、一般化するために、大まかに球状（２−Ｄでは円）のＧＡＤ要素３４０がプリミティブ３０５、３０６、及び３０７を境界するように示しているのに対し、大まかに球状の要素３４３は、以下で説明する他のＧＡＤ要素のグループを境界しており、これらがさらにプリミティブの一部を直接境界する。これに続き、要素３１５が、三角形のストリップ並びにＧＡＤ要素３４４及び３６８からプリミティブ３１８を境界する。さらに、ＧＡＤ要素３４４が三角形のストリップ３３１及びＧＡＤ要素３６９を境界し、これがさらに三角形のストリップ３６７を境界する。ＧＡＤ要素３６８は、三角形のストリップ３３２を境界する。ある意味、ＧＡＤ要素３４３は、要素３４４、３６８などを介入させることにより境界されたプリミティブを全て境界する。しかしながら、一般に本明細書では、境界とは、ＧＡＤの要素をさらに介入させることのない直接的な境界のことを意味する。
【００３５】
図３Ｂは、プリミティブ３１８を有する他の個々の三角形ストリップのプリミティブを示している。従って、図３Ｂは、図示の他の三角形ストリップも別々に列挙されるプリミティブを有することができる例を示している。図３Ａのシーンは、一般化した２−Ｄの例として意図するものであり、この例から、実際に関心のあるシーンは何倍も複雑であることが明らかとなろう。
【００３６】
上述したように、ＧＡＤ要素は互いに相関付けることができる。図４は、図３ＡのプリミティブとＧＡＤ要素とのこのような相関関係を、図３ＡのＧＡＤの要素を表すノードを図３Ａの他のＧＡＤ要素に境界線によって接続したグラフ４００で示しており、これらが最終的に図３Ａのプリミティブを境界する。特に、図３Ａから明らかなように、シーンの範囲を暗黙的に境界することができる（すなわち、シーン内の全てのプリミティブを境界するように見える）ルートノード４０５をシーン内で明示的に定める必要はない。ルート４０５は、境界線によりＧＡＤ要素３４０及び３４１（ノード）に接続される。さらに、ノード３４０は、プリミティブ３０５、３０６、及び３０７を境界する。ノード３４１に戻ると、ノード３４１はノード３１５に接続され、これがさらにノード３４４及び３６８に接続される。プリミティブ３１８がノード３１５（すなわち、ＧＡＤ要素３１５）により直接境界される一方で、ストリップ３３１はノード３４４により境界され、ストリップ３３０はノード３６８により境界される。ノード３４４はノード３６９を境界し、これがストリップ３６７を境界する。
【００３７】
図から分かるように、グラフ４００は、図３Ａのプリミティブを境界するために使用されるＧＡＤ要素間の関係を示しており、ルート４０５から開始して、グラフの異なるポイントにおけるＧＡＤ要素との交差に関して光線をテストすることにより、１又は複数の光線との交差を最終的にテストする必要があるプリミティブを絞ることができるようになる。
【００３８】
従って、１対の要素が境界線により接続されている場合、この境界線は、ノードの一方の相対粒度が他方のノードのものと異なることを示すことができ、このことは、その境界線により接続されたノードの一方が境界するプリミティブが他方のノードのプリミティブよりも多いか又は少ないことを意味することができる。場合によっては、グラフを階層的にして、グラフに方向性が存在するようにし、グラフを親ノードから子ノードへの順序でトラバースし、経路に沿って残りの境界されたプリミティブを絞ることができる。
【００３９】
場合によっては、グラフが一様なＧＡＤ要素を有するようにして、所与のＧＡＤ要素が他のＧＡＤ要素を境界する場合には（たとえこのグラフが非一様なものであっても）、この所与のＧＡＤ要素がプリミティブを直接境界しないようにすることもできる（すなわち、所与のＧＡＤ要素により境界されるいずれかのプリミティブは、所与のプリミティブにより境界されるＧＡＤ要素の１つによっても境界されるようになる）。別のＧＡＤ要素により境界されるいくつかの要素及び／又はプリミティブにおいて何らかの均一性を保持することを目標にしてＧＡＤ要素のグラフを構成することができる。このような目標を達成できるまで所与のシーンを細分化することができる。
【００４０】
通常、光線は、３−Ｄ空間における光線の起点及び方向ベクトルを使用して定義される。しかしながら、他のメカニズムを使用して同等の光線データを表すこともでき、例えば様々な数学的変換を使用して、このような起点及び方向情報を別の変数の組にマップすることができる。
【００４１】
いずれにせよ、光線が、いくつかの種類の光線のためにシーン内のどこかに存在できる所与の起点から概念的に発せられる場合でも、多くの場合、交差テストを光線の起点から開始しないことが好ましい。１つには、いくつかの加速構造を使用する場合、どのＧＡＤ要素において起点が見つかるかが容易に明らかにならない可能性があるからである。
【００４２】
従って、多くの場合、光線テストは加速構造の先頭（ルート）から開始して構造内へと進む。このことは、光線が概念的にその起点からシーンをトラバースするという順序から外れて光線をプリミティブに対してテストできることを意味する。そこで、以下の説明では、所与のＧＡＤ要素と交差すると判定されている光線に基づき、これに応じて次にいずれの他のＧＡＤ要素をテストすべきかを判定するためのメカニズムを提供する。階層的グラフの例では、一般に、次にテストされる要素は、テストされるノードの子ノードである。しかしながら、他の好適な方法を提供することもでき、例えば、厳密には階層的ではないが、グラフを方向付けることができる。
【００４３】
ここで図５を参照すると、１つの光線をシステム内で現在テストされている他の光線と識別／区別するために使用できる光線識別子（５０５）を含む光線を定義するためのデータ構造５００の例を示している。データ構造５００は、起点５０６、方向５０７、クリップ距離５０８、デフォルトオブジェクト５０９及び１又はそれ以上のフラグ（５１０）も含む。以下、データ構造５００のこれらの成分に関するさらなる詳細を示す。
【００４４】
図６は、光線データ構造５００の成分を提供及び使用することに関する第１の方法６００を示しており、この方法をシェーダ（シェーディングプロセスなど）が実行して、図７〜図９に示す方法で使用できる入力を生成することができる。また、図７〜図９に開示する態様による方法を実施する交差テストリソースから取得される光線／プリミティブ交差の指示を受け取ったことに応答して方法６００を実施することもできる（すなわち、交差テストとシェーディングの間にループが存在することができる）。
【００４５】
方法６００は、交差テストのための光線をインスタンス化する（６０５）という最初のステップを含む。従って、シェーダコードが実行できる方法６００のステップは、光線をインスタンス化するステップ（６０５）と、それぞれのクリップ距離を個々の光線に関連付けるステップ（６１０）とを含むことができる（シェーダはクリップ距離を設定することができ（６１０）、或いは光線をテストしようとするシーンの範囲又はサブポーションを別様に決定する）。
【００４６】
ここで言うクリップ距離とは、例えばシーン全体の範囲などの、一般的に適用できる追跡限界とは無関係に設定可能な所与の光線のクリップ距離のことである。クリップ距離は、様々な方法で指定することができる。１つの方法は、３−Ｄ空間内の終点を提供することである（例えば、別の３つ組が終点を指定する）。光線をパラメータで指定する場合、最大パラメータサイズを指定することができる。光線に関わる交差テストをどこで中止すべきか、或いは別様に制限すべきかを決定できる限り、関連するクリップ距離を有する個々の光線にこのようなクリップ距離のための他の方法を提供することもできる。
【００４７】
従って、光線データ構造５００は、このデータ構造により指定される光線の交差テストを制限すべきシーンのサブポーションを定義する。光線が２−Ｄである場合、このようなサブポーションはラインセグメントであってもよい。例えば、ラインセグメントは、光線の起点及びシーン内の第２の３−Ｄポイントにより定義されるシーンのサブポーションであってもよい。このようにして、交差テストリソースがデータ構造内のデータを解釈して、このシーンのサブポーション内に存在しない加速要素及び／又はプリミティブなどの幾何学的オブジェクトに交差テストを行わないようにすることができる。本明細書では、便宜上、「クリップ距離」又は「クリッピング距離」という用語を一般に使用するが、この用語はまた、シーンの範囲又はサブポーションを定義し、この定義された範囲又はサブポーションを使用して、関連する光線がこの範囲又はサブポーション内でのみ、或いはこれらを使用しない場合にのみテストすべきかどうかに関して判別を行うという、より一般的な概念も意味する。
【００４８】
場合によっては、データ構造は、複数の光線を定義する情報を含むことができる。例えば、状況によっては、光源による影に関してプリミティブ内のいくつかのポイントをテストするようにシェーダをプログラムすることができる。このため、このシェーダは、起点は異なるが目標は類似するいくつかの光線を発することができる。例えば、シェーダは、いくつかの光線をパラメータで定義して、例えば（モンテカルロプロセスなどで）いくつかのポイントを統計的にサンプリングすることができ、従ってこれらの状況では、データ構造が、起点は異なるが目標は類似するいくつかの光線を定義する際に使用できるパラメータを含むことができる。これらの状況では、全ての光線に同じデフォルトオブジェクトを提供することができる。さらに他の状況では、データ構造が、起点は類似するが目標が異なる複数の光線を定義することができる。これらの種類の状況では、個々の異なる目標に異なるデフォルトオブジェクトを提供することができる。これらは、３−Ｄシーン内の光線に関する交差テストの範囲を制限するための異なるデータの組み合わせをどのように実現できるかについての例にすぎす、また異なる条件下で交差したと報告され得る１又はそれ以上のデフォルトオブジェクトを提供するさらなる拡張にすぎない。
【００４９】
別個のクリッピング距離の使用、又は所与の光線に関するテストの範囲を制限する別の方法から、クリッピング距離を有しておらずシーン内で完全にテストされる光線を定義できることが明らかになるはずである。このように、これらの例及びその他の態様によるシステム及び方法との関連では、それぞれのクリッピング距離を有するシステム内でインスタンス化される光線、及び（恐らくは、一般化されたシーンクリップ距離以外の）それぞれの距離を有していないその他の光線が存在してもよい。従って、交差テストの実施構成は、それぞれのクリップ距離を有する光線及び有さない光線を判定するための機能を提供することができる。
【００５０】
いくつかの実施構成では、データ構造５００の一部を具体化する異なるデータ構造を提供する必要がないことも明らかになるはずである。むしろ、データ構造５００の一部のいずれかを、いずれかの適当なメカニズムにより提供することができる。例えば、実施構成は、シェーダがクリップ距離内のみの特定の光線（より一般的には、シーンのサブポーション）のレイトレーシングを要求できるようにする（手続き呼び出し、関数呼び出しなどの）ユーティリティを提供することができる。データ構造５００内に示すデフォルトオブジェクト及びフラグなどの、シェーダから提供されるその他のパラメータを受け入れるためにこのユーティリティを提供することもできる。当然ながら、このようなユーティリティは、このようなユーティリティをインスタンス化するシェーダからの呼び出しにおけるデータ構造５００の場所のためのメモリ位置参照などの参照を受け取ることができる。データ構造５００内に示すデータのいくつかを他のデータから推測するようにユーティリティをプログラムすることもできる。例えば、シェーダは、デフォルトオブジェクト識別子を提供することができ、ユーティリティを実施するプログラムは、デフォルトオブジェクトからクリップ距離を推測することができる。クリップ距離は、テストされる光線の起点に対してデフォルトオブジェクトよりも近く、またいくつかの状況ではわずかに近くなる。
【００５１】
光線はクリップ距離とは別の定義データを有することができるが、場合によっては、例えば２つのポイントを接続するラインセグメントに沿ったテストの起点及び最大範囲を定める空間内の２つの異なるポイントを指定することにより、光線をクリップ距離で定義することもできる。任意に（破線で示すように）、シェーダは、デフォルト形状を指定して（６１５）１又はそれ以上のフラグを設定することができる（６２０）。前述の図に関して説明したように、クリップ距離内に交差されたプリミティブが存在しない場合、及びいずれかのフラグが設定されたというさらなる解釈に基づいて、交差テスタが、交差されたものとしてデフォルト形状を戻すことができる。シェーダは、交差テストリソースが所定の状況下でのみデフォルト形状の交差を報告し、或いは他の状況下でデフォルト形状の交差以外の何かを報告するフラグを設定するように決定することができる。次に、シェーダは、テストのために二次光線（又はあらゆる数のインスタンス化された光線）を提出（通信として識別される６２１）することができる。いくつかの例では、光線をクリッピング間隔に関連付けることができ、この場合テストのために、光線がこの通常の光線の範囲の一部として指定される間隔内又は間隔外のいずれかに制限される。
【００５２】
図７は、交差テストのための方法６００の要素６２５を実施する方法７００を示しており、光線をそれぞれのクリッピング距離に関連付けることができる実施構成では、この方法を、光線をテストするための交差テストリソースにより実施することができる。方法６２５では、光線識別子を受け取ること７０５により、交差テストリソース内で交差テストをトリガすることができる。例えば、交差テストリソースをローカルなメモリに結合して光線のいくつかのデータ構造（図５を参照）を記憶することができ、その後、この交差テストリソースに、識別済みの光線を定義するデータを取り出して（７１０）光線をテストすべきであることをテストリソースに示す、ローカルなメモリに記憶された光線の識別子を別の計算リソースから提供することができる。光線識別子は、幾何学形状の識別子、又は幾何学形状を定義するデータを伴うことができる（７１５）。
【００５３】
方法６２５は、光線がそれぞれのクリップ距離に関連しているかどうかを判定するステップ（７２０）へ続き、関連している場合、このようなクリップ距離内にテストされる形状が存在するかどうかが判定される（７２５）。クリップ距離が存在しない場合、或いは形状がクリップ距離内にある場合、この形状がテストされる（７４０）。形状がクリップ距離外にある場合、光線のデフォルト形状が存在するかどうかが判定され（７３０）、存在する場合、光線が交差したものとしてこのデフォルト形状を戻すことができる（７３５）。デフォルト形状が存在しない場合、形状がクリップ距離外にありデフォルト形状も定義されなかったので、方法６２５は交差を報告せずに戻る７６０。フラグなどの他の特徴を提供することもでき、このような他のデータの存在に基づいて行動を変えることができるという点で、これらのステップの他の変形も可能である。また、光線が常にクリップ距離及び／又は定義されたデフォルトオブジェクトを有している実施構成では、このような判定ステップを除外することができる（例えば、このようなフィールドは、これらを制限のないクリップ距離として、或いは例えばヌル形状として解釈するように定義することができる）。
【００５４】
形状をテストした場合（７４０）、プリミティブとの交差が検出されたかどうかが判定される（７４５）。換言すれば、方法６２５は、一般的には所与のテストされる形状がプリミティブであるか、又は加速要素であるかに関するものであるが、一般に、シェーダは加速要素との交差の指示を必要とせず、これらの要素は、交差されたプリミティブの識別のみを加速させるためのものであるので、これらの２つの形状の種類の交差を区別する何らかの方法が提供される。
【００５５】
また、ほとんどのレイトレーシングの実施構成では、最も近いプリミティブ交差後に光線が終了するので、これらの実施構成では、検出された最も近い交差のみを追跡すればよい。従って、７５０では、検出した交差が、以前に検出したいずれの交差よりも近いかどうかを判定する。そうである場合、このような交差の指示が記憶され（７５５）、このような指示は、交差されたプリミティブの識別子を含むことができ、及び／又はこれを光線を定義するデータ構造とともにローカルなメモリに記憶し、中間処理などを介してシェーダへ送信することができる。そして、交差が検出されなかった場合（７４５）、検出した交差が最も近いものでなかった場合、或いは７５５の後で、方法６２５は７６０へ戻る。
【００５６】
方法６２５は、加速構造及びプリミティブのために使用される形状を含む様々な形状のいずれかを交差テストするために計算リソースを再構成できる実施構成に適していると考えられる。例えば、加速構造及びプリミティブの三角形に球又はバウンディングボックスを使用することができる。しかしながら、通常は、テストで何らかのプリミティブの選択が識別されるまで、加速構造のいくつかの要素が所与の光線に関してトラバースされる（例えば、ｋｄツリーの場合、３−Ｄ空間の容量が、テストするのに十分小さなプリミティブの容量又は数を含むようになるまで、３−Ｄ空間の３軸細分を継続することができる）。
【００５７】
従って、加速構造の別のトラバースを示す別の方法例８００を示す。方法８００には、例えばステップ６２０から入ることができ、光線識別子を受信するステップ８０５から開始することができる（図７を参照）。方法８００はまた、テストするプリミティブを識別するために加速構造をトラバースするステップ８１０、その後、交差に関してプリミティブをテストするステップ８１５を含むこともできる（以下の方法９００では、トラバース８１０の例をより詳細に示す）。次に、プリミティブが交差されたかどうかを判定し（８２０）、交差されていない場合には、さらなるテスト（８２５）が必要かどうかを判定する。プリミティブの交差があった場合、この交差を記録し（８１７）、或いは検出された最も近い交差であるかどうかを少なくともチェックし、その後さらなるテストが必要かどうかのチェック（８２５）を行う。
【００５８】
光線がまだ加速構造の全体をトラバースしていない場合、さらなるテストが必要となり得る。例えば、ｋｄツリーでは、プリミティブの選択を境界する個々の最終的な細分が、チェックを必要とする他の兄弟ノードを有するようになり、同様にトラバースされるのを待っているｋｄツリーの他の部分が存在する可能性がある。従って、最終的な交差判定を報告する前に（すなわち、シーン全体の交差テストが完了する前に）、交差テストを行うべきかどうか、或いはシーンの個々のプリミティブに関して交差テストを行うかどうかが判定される必要がある。
【００５９】
テストが終了した場合、記録されたプリミティブ交差が存在するかどうかを判定することができ（８２８）、プリミティブ交差が存在しなかった場合、デフォルト形状の交差を報告すべきかどうかを判定することができる（８２９）。この措置は、デフォルト形状が指定されているかどうか、及びデフォルト形状との交差を報告すべきかどうかを示すフラグ（図５を参照）が存在するかどうかを明らかにするステップを含むことができる。この判定により、デフォルト形状を交差されたものとして戻すべきであることが示される場合には、このような指示を戻すことができ（８３０）、そうでない場合には、その光線に関する交差テストを終了する（８５０）。プリミティブが交差していた場合には、この交差を報告するかどうかの判定（８３５）を行うこともできる。例えば、どのような条件でフラグを報告すべきかを示すフラグを光線のデータ構造内に提供することができる。交差を報告すべき場合、最も近い交差（一般には追跡される交差のみ）が戻される（８４０）。その後、或いは交差を報告すべきでない場合、テストは終了する（８５０）。方法８００のフラグベースの決定を方法６２５において行うこともできる。
【００６０】
図９は、図４の構造に似た加速構造をトラバースする方法９００を示している。これらの開示は例示的なものであり、これらの例に関して開示する態様を当業者が適用又は別様に適合させることができる多くの異なる種類の加速構造が存在する。方法９００は、図８の８０５の後に開始することができ、加速構造のルートノードから開始することができる（ここでは「ノード」という用語を使用しているが、これらの開示はあらゆる加速構造に適用できるので、プリセットしたグラフが必要であるという意味ではない）。むしろ、ルートとは開始ポイントのことを意味し、ルートがシーンを境界する場合、いずれかの光線がルートと交差することを意味することができ、従って次のステップは、ルートノードの次にどの要素／ノードがくるかを判定すること（９１０）である。例えば、グラフ４００は、境界線によりノード３４０及び３４１に接続されたルート４０５を示しており、従ってステップ９１０は、ルート４０５の次にテストされるノードとしてノード３４０及び３４１を識別するようになる。次に、これらの次の要素に関して、テストされる光線に対して指定されたクリップ距離内に各々が存在するかどうかが判定され（９１５）、そうでないものに関しては、そのブランチ又は経路が終了する（９２０）。そうであるものに関しては、その要素が交差についてテストされる（９３０）。交差が存在する場合、その要素が、テストの準備ができたいずれかのプリミティブを境界するかどうかを判定することができ（９２５）、境界する場合には、例えばこのプリミティブを境界する加速構造の別の要素が存在しないことを意味することができる。テストのためのプリミティブが存在する場合、方法９００は図８の８１５へ進む。方法９００は、テストされた加速要素との交差を収集するステップ（９３５）を含むこともできる（例えば、この要素が他の加速要素も境界する場合、或いは他の加速要素のみを境界する場合）。換言すれば、方法９００は、加速構造における交差テストの繰り延べをサポートすることができる。次に、テストする次の現在の要素が選択され（９４０）、このステップは、テストされる要素を現在の要素として設定し、その後、この現在の要素に関する要素の識別（９１０）を再び行うステップを含むことができる。図３Ａ及び図４を参照すると、例えば、光線のクリップ距離が要素３１５に対するテストを許容する場合、プリミティブ３１８がテストされ（クリッピングテストも含むことができる）、最終的に要素３４４及び３６８が、クリッピングテストを適用する次のノードとして選択されるようになる。
【００６１】
図６〜図９に示す方法の概要について説明したが、より図３Ａ及び図４に具体的に関連する例について説明する。カメラ光線３８８がシーン３０２に入る。図４では、ルート４０５に光線３８８を有することによりこれを表している。次に、光線３８８を、加速要素３４０及び３４３との（図６〜図９の方法のクリップ距離の実施構成との）交差についてテストすることができ、この例では、クリップ距離がこのようなテストを許容し、３４０との交差は存在しないが、３４３との交差が存在する。従って、次に光線３８８が要素３１５との交差に関してテストされ、交差することが判明する。次に、三角形を有する三角形ストリップ３１８が要素３１５により境界されると判定され、これがテストされ、光線３８８により交差されることが判明する。交差が報告され、プリミティブ３１８に関連するシェーダが呼び出される。シェーダは、シーン内の光線３４１をテストすることを決定し、クリップ距離３８９を設定する。光線３４１がシーンを介して再度トラバースされ、最終的にストリップ３３１のプリミティブとの交差がテストされ、交差することが判明する。従って、光線３４１に関してはクリップ距離に到達しなかった。なお、ここでは実施構成及びテストの順序に応じて、要素３６９、又は要素３６９とストリップ３６７をテストすることもできる。
【００６２】
プリミティブ３１８と交差しておらず、代わりに光線３８８が３３０でストリップ３３２と交差している場合、シェーダは、光線３４２をクリップ距離３９２でインスタンス化することができる。光線３４２に関するトラバースを、ルート４０５、要素３４３、要素３１５、要素３４４及び要素３６９及び３６８の順序で再度行うことができる。しかしながら、この場合には交差が見つからず、クリップ距離３９２に到達する。クリップ距離３９２に到達するので、光と交差したことを明確にチェックする必要はない。従って、光線３４２が影光線であったとすると、光線３４２の起点は光の影にないと仮定される。いくつかの態様では、この光又はそのプリミティブを交差されたデフォルトオブジェクトとして戻すことができる。
【００６３】
従って、光線固有のクリップ距離を設定すること、或いは光線をテストするためにシーンのサブポーションを指定する別の方法により、このようなクリッピングを指定しておくためにテストするシーン空間を狭めることができるようになる。このような特徴が有用となり得る状況例には、所与のポイントが点光源の影になっているかどうかをテストする状況がある。このようなシャドーイングをテストするために光線を指定できるので、この用途は特に有用となり得るが、機械の不正確さにより、光線が他のいずれかのプリミティブに当たらなかったとしても、光線が光を失ったと判定することができる（すなわち、光源から影を判定するつもりであったとしても、交点が影になっていない場合でも影になっていると判断される）。そこで、光に近いクリップ距離を提供することにより、光線が近づいたら、交点をシャドウイングするプリミティブが存在しないと判定することができる。また、このようなクリップ距離のより積極的な使用を望む通りに使用することもできる。
【００６４】
上述したように、光線の交差をシェーディングするために提供されるコードのモジュールは、交差をシェーディングする際に、遮断テストなどの様々なテストを行うために二次光線を発することができる。これらの例では、このような光線の放出が、１又はそれ以上の光線の特別なクリップ距離を設定するステップと、光線のグループに対して、交差されるデフォルトオブジェクト又はデフォルトオブジェクトのグループを設定するステップなどを含むことができる。このようなシェーダが使用するためのアプリケーションプログラミングインターフェイス（ＡＰＩ）を提供して、このようなクリッピング機能の使用を容易にすることができる。例えば、光線の放出機能の呼び出しは、クリップ距離の定義、及びデフォルトオブジェクトの識別を受け入れることができる。さらなる例により、光線の放出機能の呼び出しは、各々のクリップ距離が異なる発光される光線束の定義、又はデフォルトオブジェクトを受け入れることができる（及びオブジェクトからのクリップ距離を推測することができる）。例えば、ＡＰＩは、シーン内の光の場所などの状態を維持することができ、影光線を発するシェーダは、影光線を発したときに、影光線として指定された光線にどのデフォルトオブジェクトを割り当てるべきかをＡＰＩに判断させることができる。ＡＰＩにより、或いはＡＰＩを介して提供されるデータを交差テスト中に使用して、交差テストをどのように行うかを制御することができる。引用により本明細書に組み入れられている米国仮出願第６１／０９９，１５２号、６１／１０１，８５４号、及び６１／１７２，４５３号には、これらの開示とともに使用できる他の様々なＡＰＩに関する態様が開示されており、これには、本明細書で説明する光線固有のクリッピング機能及びオプションにアクセスするためのＡＰＩを提供するために使用することもできるＡＰＩを提供するシステム及び方法が含まれる。
【００６５】
図１０はシステム１０００の例を示しており、このシステムは上述した態様を利用することができ、また図１のシステムのより具体的な例と考えることができる。システム１０００は、プロセス、スレッド、コア、異なるプロセッサ、グラフィクスプロセッサ、特定用途向け回路、ＦＰＧＡなどのうちの１又はそれ以上とすることができる複数の計算リソース（１００５〜１００８）を含む。システム１０００は、このような異なる種類の計算リソースの異種の組み合わせを含むことができる。例えば、計算リソース１００４は、レイトレーシングレンダリングサービスを必要とするアプリケーション、及びこのようなサービスを提供する他の計算リソースにアプリケーションを結合させるためのドライバをホストすることができ、計算リソース１００４を、その計算負荷に起因して汎用プロセッサとして実現されるようにより良く適合させることができる。同様に、シェーダプロセス１０１１をホストするように示している計算リソース１００５も、少なくとも何らかの一般的プログラミング能力を有する計算リソースとともに実現されるようにより良く適合させることができるが、グラフィクスハードウェアが、汎用プロセッサからそれほど制御を受けなくてもますますより高度なシェーディングアルゴリズムを実行できるようになってきている。通信リンク１００１は、計算リソース１００５〜１００８を接続するとともに、ポイントツーポイント接続のメッシュ、１又はそれ以上の共有バス、メモリマップＩ／Ｏなどを含むことができ、或いはスレッドツースレッド又はプロセスツープロセス通信の場合には、リンク１００１は、このような情報をこれらのエンティティ間で受け渡すために使用されるいずれかの技術を含むことができ、また特定の実施構成で利用できるオペレーティングシステム及びその他のプラットフォームソフトウェアにより提供されるサービスに依拠することができる。
【００６６】
計算リソース１００４〜１００８は、キャッシュ１０２５ａ〜１０２５ｎと通信する（一般に、システム１０００で提供される個々の計算リソースのためのプライベートな又はセミプライベートなキャッシュが存在できるという概念で示している）。個々のこのようなキャッシュは、同様に示す光線データ１０１０ａ〜１０１０ｎを記憶することができる。個々のキャッシュ１０２５〜１０２５ｎは、二次キャッシュ１０２５、１０３０、及び１０３５から供給することができ、これらの二次キャッシュは、キャッシュ１０２５ａ〜１０２５ｎよりも少ない数であってもよく、またプライベートなもの又は共有されるものであってもよい。システム１０００の例では、形状データ１０１５及び光線データ１０１０の両方を記憶できるＬ３キャッシュ及び／又はメインメモリ３４０からＬ２キャッシュを供給することができる。
【００６７】
要約すると、本明細書で説明した機能、特徴、及びその他の論理は、いずれも様々な計算リソースにより実現することができる。計算リソースは、スレッド、コア、プロセッサ、固定関数処理要素などであってもよい。また、主に本発明の対象ではないその他の機能も、１つの計算リソースに限局できる、又は（複数の物理計算リソース間で分散される複数のスレッドなどの）複数の計算リソース間で分散できるプロセス、スレッド又はタスクとして提供又は実現することができる。
【００６８】
同様に、交差テストに使用する計算リソースが、検出された交差をシェーディングするために使用されるシェーディング処理などの他の処理をホストすることもできる。さらなる例により、コアが複数のスレッドをサポートできる場合、１つのスレッドをシェーディング専用にして、別のスレッドを交差処理専用にすることができる。
【００６９】
あらゆる方法のためのコードを、固体ドライブ、ハードドライブ、ＣＤ−ＲＯＭ及びその他の光学記憶手段などのコンピュータ可読媒体に、及びＳＲＡＭ及びＤＲＡＭ技術メモリなどの揮発性及び不揮発性メモリに記憶することができる。
【００７０】
コンピュータ実行可能命令は、例えば、汎用コンピュータ、特定用途向けコンピュータ、又は特定用途向け処理装置に特定の機能又は機能のグループを実行させる、或いは実行するように別様に構成する命令及びデータを含む。このコードを、ＦＰＧＡのモジュールをプログラミングする際に、或いはＡＳＩＣのレイアウトを決定する際に使用することができる。コンピュータ実行可能命令は、例えば、バイナリ、アセンブリ言語などの中間フォーマット命令、又はソースコードであってもよい。
【符号の説明】
【００７１】
６２５  要素
７０５  光線識別子を受け取り
７１０  光線データ構造を取り出し
７１５  テストのために幾何学的形状を取得
７２０  光線固有のクリップ距離か？
７２５  クリップ距離内にある形状か？
７３０  デフォルト形状か？
７３５  デフォルト形状交差を戻す
７４０  形状をテスト
７４５  プリミティブとの交差を検出したか？
７５０  最も近い交差がまだ存在するか？
７５５  指示を記憶
７６０  戻る
【図１】
0005271416.tif 000002
【図２】
0005271416.tif 000003
【図３Ａ】
0005271416.tif 000004
【図３Ｂ】
0005271416.tif 000005
【図４】
0005271416.tif 000006
【図５】
0005271416.tif 000007
【図６】
0005271416.tif 000008
【図７】
0005271416.tif 000009
【図８】
0005271416.tif 000010
【図９】
0005271416.tif 000011
【図１０】
0005271416.tif 000012