レイトレース・レンダリングのための並列化された交差テストおよびシェーディングのアーキテクチャ

专利摘要:
レイトレース・レンダリングのための並列化された交差テストおよびシェーディングのアーキテクチャを提供する。 実施例では、シーンのレイトレーシングは、リンク／キューを介して全体として通信する複数のシェーディング資源と連結された複数の交差テスト資源を使用する工程を含む。テストからシェーディングへのキューは、レイ識別子を含むそれぞれのレイ／プリミティブ交差指標を含む。シェーディングからテストへのキューは、テストされる新しいレイの識別子を含み、レイを定義するデータは交差テスト資源の間に分散させられたメモリに別個に格納される。レイ定義データは、レイ識別子に基づいて複数回に亘りテストのため選択可能である場合、レイが交差テストを終了するまで、分散メモリの中で維持することが可能である。アクセラレイション形状の構造が使用可能である。レイ識別子および形状データのパケットは、交差テスト資源の間を循環可能であり、各交差テスト資源はパケットの中で特定されたレイをテスト可能であり、そのレイのための定義データが交差テスト資源のメモリの中に存在する。アクセラレイション形状テスト結果は、交差した形状に基づいてレイのコレクションを可能にさせ、最近傍検出レイ／プリミティブ交差はシェーディングのためのレイ識別子をキューイングすることによって指示される。
公开号:JP2011515766A
申请号:JP2011500994
申请日:2009-03-20
公开日:2011-05-19
发明作者:サルスバリー、ライアン、アール．；パーセル、スティーブン；ピーターソン、ルーク、ティルマン；マコーム、ジェームス、アレキサンダー
申请人:コースティック グラフィックス、インク．；
IPC主号:G06T15-06

专利说明:

[0001] （関連出願の相互参照）
本願は、２００９年３月２０日付けで出願された米国特許出願第１２，４０８，４７８号による優先権、２００８年３月２１日付けで出願された、発明の名称が「Ｃｏｕｐｌｉｎｇ Ｒａｙ Ｓｔｏｒａｇｅ ａｎｄ Ｃｏｍｐｕｔｅ ｆｏｒ Ｍｅｍｏｒｙ−Ｅｆｆｉｃｉｅｎｔ Ｒａｙ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｔｅｓｔ Ｓｃａｌｉｎｇ」である米国仮出願第６１／０３８，７３１号による優先権、および、２００８年９月１０日付けで出願された、発明の名称が「Ａｒｃｈｉｔｅｃｔｕｒｅｓ ｆｏｒ Ｐａｒａｌｌｅｌｉｚｅｄ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｔｅｓｔｉｎｇ ａｎｄ Ｓｈａｄｉｎｇ ｆｏｒ Ｒａｙ−Ｔｒａｃｉｎｇ Ｒｅｎｄｅｒｉｎｇ」である米国仮出願第６１／０９５，８９０号による優先権を主張し、これらのすべては全体としてこの参照により、すべての目的のため、本明細書に組み込まれるものである。]
[0002] 本発明は、３次元シーン（ｓｃｅｎｅｓ）からの２次元表現のレンダリングに関し、より詳細には、シーンのフォトリアリスティック（ｐｈｏｔｏ−ｒｅａｌｉｓｔｉｃ）な２次元表現の高速化レンダリングのためのレイトレーシング（ｒａｙ ｔｒａｃｉｎｇ）の使用に関する。]
背景技術

[0003] レイトレーシングによるフォトリアリスティックな画像のレンダリングはコンピュータ・グラフィックス・アートにおいて周知である。レイトレーシングは、シーンの要素と相互に作用する光の物理的な挙動をモデル化することができるので、写実的な影および照明効果を含むフォトリアリスティックな画像を生成することが知られている。しかし、レイトレーシングは計算集約的であることでも知られ、現在のところ、アート・グラフィックス・ワークステーションの状況であってもレイトレーシングを使用して複雑なシーンをレンダリングするためかなりの時間を要する。]
[0004] レイトレーシングは、通常、カメラから始まり、シーン物体との多数の潜在的な相互作用を介して、光源で終端するか、または、光源と交差することなくシーンから出るまで光線を追跡することにより、シーンの中の構造体の表面を記述する三角形のような幾何学的プリミティブ（ｇｅｏｍｅｔｒｉｃ ｐｒｉｍｉｔｉｖｅ）で構成されたシーン記述を取得することと、どのようにして光がシーンの中のプリミティブと相互に作用するかをモデル化することとを含む。]
[0005] 例えば、シーンは両側に建物がある街路上の車を含むことができる。このようなシーンの中の車は、連続的な表面を近似する多数の三角形（例えば、１００万の三角形）によって定義されることができる。シーンを観察するカメラ位置が定義される。カメラから放たれたレイ（光線）は、多くの場合に１次レイと呼ばれ、例えば、反射を可能にするため一方の物体から別の物体へ放たれたレイは、多くの場合に２次レイと呼ばれる。選択された解像度（例えば、ＳＶＧＡディスプレイの場合に１０２４×７６８）をもつ画像平面がカメラとシーンとの間の選択された位置に配置される。]
[0006] 最も簡単なレイ・トレーシング・アルゴリズムは、カメラから画像の各画素を介してシーンの中へ１若しくはそれ以上のレイを放つことを含む。各レイは、その後に、シーンを構成する各プリミティブに対してテストされてレイが交差するプリミティブの特定が行われ、次に、プリミティブがレイに及ぼす影響、例えば、レイを反射および／または屈折させるかどうかが決定される。このような反射および／または屈折は、レイを異なる方向へ伝播させ、および／または、レイを異なる経路をとることができる複数の２次レイに分割させる。これらの２次レイのすべては、その後に、シーンプリミティブに対しテストされて交差するプリミティブが決定され、この過程は、２次（そして、３次、以下同様に続く）レイが、例えば、シーンを離れることによって、または、光源に達することによって終端するまで再帰的に続く。これらのレイ／プリミティブ交差のすべてが決定されている間に、交差をマップするツリーが作成される。レイが終端した後、光源の寄与度がツリーを介してトレースバックされ、シーンの画素に対する光源の影響が決定される。容易に理解されるように、何百万もの三角形との交差に関して、（例えば）１０２４×７６８のレイをテストするという複雑な計算は計算集約的であり、しかも、このようなレイの数は、交差するレイとの物質の相互作用の結果として生じる付加的なレイの全部を算入していない。）]
[0007] レイトレーシングによるシーンのレンダリングは、生成されている画像の各画素のため蓄積されたカラー情報が画像の他の画素とは独立に蓄積可能であるので、「厄介な並列問題」と称されている。よって、最終画像を出力する前に、何らかのフィルタリング、補間または他の画素処理が存在することがあるが、画像の画素のカラー情報は並列に決定可能である。従って、レンダリングされるべき画素を処理資源の間で分割し、これらの画素のレンダリングを並列に実行することにより所定の処理資源の組に関する画像のレイトレーシングのタスクをセグメント化することは容易である。]
[0008] ある場合には、処理資源はマルチスレッド化をサポートするコンピューティングプラットフォームでもよいが、他の場合は、ＬＡＮを介してリンクされたコンピュータのクラスタ、または、コンピュータコアのクラスタを伴うことができる。これらのタイプのシステムに対し、所定の処理資源、例えば、スレッドは、交差テストおよびシェーディングの終了によって割り当てられたレイまたはレイのグループを処理するためインスタンス化可能である。換言すると、画素は互いに独立にレンダリング可能であるという特性を使用して、異なる画素に寄与することが知られているレイは、交差テストされるべきスレッドまたは処理資源の間で分割可能であり、その後に、このようなシェーディング計算の結果を処理または表示のため画面バッファへ書き込み、これらの交差をシェード可能である。]
[0009] この種の問題を対象にするいくつかのアルゴリズム的アプローチが提案されている。１つのこのようなアプローチは、Ｍａｔｔ Ｐｈａｒｒ，ｅｔ ａｌ．により「Ｒｅｎｄｅｒｉｎｇ Ｃｏｍｐｌｅｘ Ｓｃｅｎｅｓ ｗｉｔｈ Ｍｅｍｏｒｙ−Ｃｏｈｅｒｅｎｔ Ｒａｙ Ｔｒａｃｉｎｇ」Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＳｉｇＧｒａｐｈ（１９９７）（本明細書では、「文献Ｐｈａｒｒ」と称する）に開示されている。文献Ｐｈａｒｒは、各幾何学的ボクセルがシーンプリミティブ（例えば、三角形）を内包する立方体であるとして、レイトレーシングされるべきシーンを幾何学的ボクセルに分割することを開示する。文献Ｐｈａｒｒは、スケジューリンググリッドの各要素が幾何学的ボクセルのいくらかの部分に重なることが可能であるスケジューリングボクセルであるとして（すなわち、スケジューリングボクセルが、幾何学的ボクセルの立方体とは異なるサイズにされることが可能であるシーンの中の体積をもつ立方体でもあるとして）、スケジューリンググリッドを重畳することをさらに開示する。各スケジューリングボクセルは、現在のところ内側にあるレイ、すなわち、そのスケジューリングボクセルの内部に内包されたレイを含む関連付けられたレイキューと、どちらの幾何学的ボクセルがそのスケジューリングボクセルに重なるかに関する情報とを有する。]
[0010] 文献Ｐｈａｒｒは、スケジューリングボクセルが処理されるとき、関連付けられたキューの中のレイが、スケジューリングボクセルによって内包された幾何学的ボクセルの中のプリミティブとの交差に関してテストされることを開示している。レイとプリミティブとの間の交差が見出された場合、シェーディング（陰影付け）計算が実行され、その結果レイキューに追加されるレイが増加することが可能である。そのスケジューリングボクセルの中に交差が見出されなかった場合、レイは次の空でないスケジューリングボクセルへ進み、そのスケジューリングボクセルのレイキューの中に収容される。]
[0011] 文献Ｐｈａｒｒは、このアプローチによる利点は、各スケジューリングボクセルの中のシーンジオメトリがキャッシュ内に収まることができる場合、キャッシュがシーンジオメトリとのレイの交差テスト中にトラッシングをあまり起こさないように、シーンジオメトリを通常の汎用プロセッサに設けられたキャッシュ内に収めるのに役立つことであることを開示している。]
[0012] さらに、文献Ｐｈａｒｒは、テストのためのレイをスケジューリングボクセルの中にキュー入れすることによって、プリミティブがジオメトリキャッシュにフェッチされたとき、それ以上の作業がプリミティブに関して実行できることを開示している。複数のスケジューリングボクセルが次に処理できる状況では、スケジューリングアルゴリズムは、ジオメトリキャッシュにロードされるべきジオメトリの量を最小限に抑えることになるスケジューリングボクセルを選定可能である。]
[0013] 文献Ｐｈａｒｒは、特定のシーンが一様でない複雑性を有する場合、すなわち、シーンのいくつかの部分でプリミティブの密度が高い場合、提案された規則的なスケジューリンググリッドが十分に機能しないことがあることを認めている。文献Ｐｈａｒｒは、オクツリー（ｏｃｔｒｅｅ）のような適応的データ構造が規則的なスケジューリンググリッドの代わりに使用できると仮定している。オクツリーは、階層の各レベルで、オクツリー分割が８つのより小さいサブボリュームを生じ、その８つのより小さいボリュームが８つのさらに小さいサブボリュームに分割可能であり、以下同様に続くような、シーンの各主軸（すなわち、ｘ、ｙ、およびｚ軸）に沿った分割を引き起こすことにより、３次元シーンの中に空間分割を導入する。各サブボリュームにおいて、そのサブボリュームがさらに分割されることになるかどうかを決定する分割／非分割フラグがセットされる。このようなサブボリュームは、そのサブボリュームの中のプリミティブの数がテストのため十分に少なくなるまで、分割のため指示される。このように、オクツリーに関して、分割の量は、シーンの特定の部分に存在するプリミティブの数に応じて制御可能である。したがって、オクツリーはレンダリングされるべきボリュームの種々の程度の分割を可能にする。]
[0014] 類似したアプローチがＰｆｉｓｔｅｒの米国特許第６，５５６，２００号（「文献Ｐｆｉｓｔｅｒ」）に開示されている。文献Ｐｆｉｓｔｅｒもまた複数のスケジューリングブロックへのシーンの区分化を開示している。レイキューが各ブロックに設けられ、各キューの中のレイが依存グラフを使用して時空間的に順序付けられる。レイは依存グラフに定義された順序に従って各スケジューリングブロックの中で追跡される。文献Ｐｆｉｓｔｅｒは、文献Ｐｈａｒｒ論文を参照し、文献Ｐｆｉｓｔｅｒが２若しくはそれ以上（例えば、三角形だけでない）のシングルタイプのグラフィカルプリミティブをレンダリングすることと、スケジューリングブロックのためのより複雑なスケジューリングアルゴリズムを工夫することとを要望することを補足している。文献Ｐｆｉｓｔｅｒはメモリ階層における複数のキャッシュレベルでシーンジオメトリの中間サブポーションをさらに検討している。]
[0015] さらに別のアプローチは、パケットトレーシングと呼ばれ、このようなパケットトレーシングの一般的な参考文献は、Ｉｎｇｏ Ｗａｌｄ，Ｐｈｉｌｌｉｐ Ｓｌｕｓａｌｌｅｋ，Ｃａｒｓｔｅｎ Ｂｅｎｔｈｉｎ，ｅｔ ａｌ．による「Ｉｎｔｅｒａｃｔｉｖｅ Ｒｅｎｄｅｒｉｎｇ ｔｈｒｏｕｇｈ Ｃｏｈｅｒｅｎｔ Ｒａｙ Ｔｒａｃｉｎｇ」，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＥＵＲＯＧＲＡＰＨＩＣＳ ２００１，ｐｐ １５３−１６４，２０（３），Ｍａｎｃｈｅｔｅｒ，Ｕｎｉｔｅｄ Ｋｉｎｇｄｏｍ（Ｓｅｐ．２００１）である。この参考文献では、パケットトレーシングは、グリッドを通る類似した始点および方向を有するレイのパケットの追跡を含む。レイは、殆どのレイが共通のグリッドロケーションを通過するように、実質的に共通のグリッドロケーションから発し、実質的に類似した方向に進行する。このように、パケットトレーシングは、類似した始点から、類似した方向に進行するレイを特定することが必要である。このようなパケットトレーシングに関する別の変形は、錐台レイがどのボクセルが交差するかを決定し、所定のレイパケットのための計算の回数の削減に役立つ（すなわち、すべてのレイが交差に関してテストされるのではなく、パケットの外側エッジにあるレイだけがテストされる）ように、レイのパケットのエッジの境界を定めるために錐台レイを使用することである。パケットトレーシングは、類似した場所から発し、類似した方向に進むレイの特定を依然として必要とする。このようなレイは、レイがレイトレーシング中に反射され、屈折させられ、および／または、発生するとき、特定することが益々難しくなることが可能である。]
[0016] さらに他のアプローチがレイトレーシングを加速する分野に存在し、１つのアプローチは、レイ状態のより能動的な管理によって改良されたキャッシュ利用を試行する。Ｎａｖｒａｔｉｌ ｅｔ ａｌ．による「Ｄｙｎａｍｉｃ Ｒａｙ Ｓｃｈｅｄｕｌｉｎｇ ｆｏｒ Ｉｍｐｒｏｖｅｄ Ｓｙｓｔｅｍ Ｐｅｒｆｏｒｍａｎｃｅ」，２００７ＩＥＥＥ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｉｎｔｅｒａｃｔｉｖｅ Ｒａｙ Ｔｒａｃｉｎｇ，（Ｓｅｐ．２００７）（文献Ｎａｖｒａｔｉｌ）は、文献Ｐｈａｒｒを参照し、ＰｈａｒｒのアルゴリズムがＰｈａｒｒ文献をプロセッサ・キャッシュ・トラフィックへの主メモリのため不適切にする「レイ状態爆発」の弱点を有することを記載している。これに対処するため、文献Ｎａｖｒａｔｉｌは、レイトレーシング中に、レイ状態およびジオメトリ状態を「能動的に管理」するように設計された制限を設けることにより、「レイ状態爆発」を回避することを提案する。１つの提案はレイの生成を別々にトレースすることであり、従って、文献Ｎａｖｒａｔｉｌは、最初に１次レイをトレースし、次に、１次レイを終了した後、２次レイをトレースし、以下同様に続くことを開示している。]
[0017] 上述の背景は、レイトレーシングに基づくレンダリングを加速化する分野において普及し続けている思想およびアプローチの多様性を示している。同様に、これらの参考文献は、さらなる進歩がレイトレーシングの分野に残っていることを示している。しかし、これらの参考文献および手法のうちのいずれかの説明は、いずれかの参考文献または参考文献中の主題が本願に開示されたいずれの主題に対しても先行技術であるという承認または示唆ではない。それどころか、これらの参考文献は、レイトレーシングを用いるレンダリングへのアプローチにおける相違点を示すのに役立つように記載されている。さらに、これらの参考文献のうちのいずれかの取り扱いは、明瞭さのため必然的に省略され、網羅的ではない。]
課題を解決するための手段

[0018] ある観点では、方法は、３次元シーンの２次元表現をレイトレーシングするのに複数のコンピューティング資源を使用する。この方法は、３次元シーンの中を進むレイで１若しくはそれ以上のプリミティブおよびジオメトリ・アクセラレイション要素を有する幾何学的形状を交差テストするためコンピューティング資源の第１のサブセットを使用する工程を含む。第１のサブセットのうちの各コンピューティング資源は、シーンの中を進むレイのそれぞれのサブセットを格納するそれぞれのローカライズされたメモリ資源と通信するため動作する。この方法は、コンピューティング資源の第１のサブセットからコンピューティング資源の第２のサブセットへレイとプリミティブとの間の交差の指標を通信する工程と、レイとプリミティブとの間の特定された交差と関連付けられたシェーディングルーチンを実行するコンピューティング資源の第２のサブセットを使用する工程とを含み、シェーディングルーチンからの出力は交差テストされるべき新しいレイを有する。サブセットの中のメンバーシップは、シーンまたは一連のシーンのいずれかのレンダリング中に、時間依存性であるか、または、システム構成時若しくは再構成ポイント中に統計的に決定される。]
[0019] この方法は、新しいレイを定義するデータをローカライズされたメモリ資源の間に分散させる工程と、レイ識別子のグルーピングを形状データと共に第１のサブセットのうちのコンピューティング資源へ伝える工程とをさらに有する。各レイ識別子は、そのレイに関するレイ定義データ以外のデータを有する。レイ識別子の伝達は、形状データによって指定された形状との特定されたレイの交差テストを作動させる。テストは、各コンピューティング資源によって、各コンピューティング資源のローカライズされたメモリに格納されている特定されたレイを定義するデータを取り出す工程と、取り出されたレイ定義データに基づいて交差に関して示された形状をテストする工程と、検出された交差の指標を通信のため出力する工程とを有する。]
[0020] 別の観点は、レイトレーシングを使用して、プリミティブで構成された３次元シーンの２次元表現をレンダリングするシステムを有する。このシステムは、それぞれのキャッシュメモリへアクセスできる複数の交差テスト資源を有し、それぞれのキャッシュメモリは、レイ定義データのマスターコピーのサブセットを格納し、各レイのレイ定義データは、そのレイのテストが終了するまで、キャッシュメモリに維持されている]
[0021] このシステムは、識別子を各レイに割り当て、それぞれのテスト資源のキャッシュメモリにおける各レイの定義データにアクセスできるそれぞれのテスト資源による各レイのテストを制御するため動作する制御ロジックをさらに有する。テスト制御は、レイ識別子をテストされるべきレイのデータを格納するそれぞれのテストセルに提供することによって達成される。このシステムは、交差テストを終了したレイと、交差したそれぞれのプリミティブとを特定する出力キューを有する。制御ロジックは、シェーディング計算から生じる新しいレイを割り当て、キャッシュメモリの中で交差テストを終了したレイを置き換える。]
[0022] ある観点では、制御ロジックが終了したレイの識別子を新しいレイの識別子として再使用することにより置き換えを行うこと、レイ識別子がそのレイを定義するそれぞれのデータを格納するメモリロケーションに関係すること、および、新しいレイを定義するデータが終了したレイのメモリロケーションに格納されているデータを置き換えることとのうちの１若しくはそれ以上が行われることが可能である。]
[0023] さらに別の観点は、レイトレーシングを使用して、プリミティブで構成された３次元シーンの２次元表現をレンダリングするシステムを有する。このシステムは、３次元シーンを構成するプリミティブを格納するメモリと、複数の交差テスト資源とを有する。各交差テスト資源は、シーンの中を進む少なくとも１つのレイを少なくとも１つのプリミティブとテストし、検出された交差の指標を出力するため動作する。システムは、各シェーダ資源が検出されたレイ／プリミティブ交差の指標からのプリミティブと関連付けられたシェーディングルーチンを実行するため動作する複数のシェーダ資源をさらに含む。このシステムは、検出された交差の指標をシェーダ資源へ出力する第１の通信リンクと、シェーディングルーチンの実行によって生じる新しいレイを交差テスト資源へ送信する第２の通信リンクとをさらに有し、新しいレイは交差テスト資源へ送信されることが可能であり、新しいレイが送信された相対的順序とは異なる順序で交差テストを終了する。両方の通信リンクは、ＦＩＦＯキューのようなキューとして達成可能である。]
[0024] さらに別の観点は、主メモリおよび計算資源間の分散メモリを有し、主メモリが分散メモリよりレイテンシが高い階層的なメモリ構造に連結された複数の計算資源を有するシステムにおいて、プリミティブで構成されたシーンをレイトレーシングする方法を含む。この方法は、レイのサブセットが分散メモリのうちの異なるメモリに格納されるように、シーンの中で交差テストされるべきレイを定義するデータを分散メモリの間に分散させることと、レイのグループを交差テストすることを決定することとを有し、グループのメンバが、１若しくはそれ以上の幾何学的形状と共に、複数の分散メモリに格納される。この方法は、主メモリから１若しくはそれ以上の幾何学的形状を定義するデータをフェッチすることと、幾何学的形状およびグループのレイの識別子を、グループの中のレイのデータを格納する各分散メモリと関連付けられた少なくとも１つの計算資源に提供することとを有する。この方法は、グループの各レイのデータを格納する分散メモリのうちの少なくとも１つと関連付けられた計算資源を用いてこのレイの交差をテストすることと、計算資源から生じる交差テスト結果を収集することとをさらに有する。]
[0025] さらに別の観点は、３次元シーンを構成するプリミティブとレイを交差テストするシステムを含む。このシステムは、各交差テスト資源が幾何学的形状との交差に関してそれぞれのレイをテストするため動作する複数の交差テスト資源を有する。１つずつのそれぞれのレイは、各交差テスト資源に提供された参照情報によって指定され、テスト資源は、レイと幾何学的形状との間の交差の指標を第１の出力または第２の出力のいずれかへ出力するため動作する。]
[0026] 一方の出力はプリミティブ交差用であり、もう一方の出力はジオメトリ・アクセラレイション要素交差用である。例えば、第１の出力は、複数のシェーディング資源に入力を提供可能であり、レイとプリミティブとの間の交差の指標用であることが可能であり、第２の出力は、レイ・コレクション・マネージャに入力を提供し、レイとジオメトリ・アクセラレイション要素との間の交差の指標を受信する。]
[0027] さらに別の観点は、３次元表現を構成するプリミティブ、および、プリミティブの選択の境界をそれぞれに定めるジオメトリ・アクセラレイション要素を主メモリ資源に格納する工程と、シーンの中で交差テストされるべきレイを定義する工程と、レイのそれぞれの識別子を定義する工程とを有するレイトレーシング方法を含む。この方法は、複数の別々にプログラム可能な処理資源を有するシステムにおいて、レイ始点および方向データの一部分を、処理資源の１つずつとそれぞれ関連付けられているローカライズされたメモリ資源に格納する工程を有する。この方法は、テストのためスケジュールに入れられたレイの識別子および幾何学的形状の指標を処理資源へ提供する工程により、交差テストに関するレイのスケジューリングを実施する工程をさらに有する。各処理資源は、ローカライズされたメモリ資源がいずれかの特定されたレイのためのレイ定義データを格納するかどうかを決定し、そうであるならば、指示された幾何学的形状との交差に関してこれらのレイをテストする。]
[0028] さらに別の観点は、３次元シーンの２次元表現をレンダリングするのに用いられる幾何学的形状とレイとの交差テストを達成するために複数の処理資源を制御するシステムのための機械読み取り可能な命令を有する、コンピュータ読み取り可能な媒体／メディアを含む。命令は、プリミティブの第１の選択の境界を定める第１のジオメトリ・アクセラレイション要素と交差していると決定されたレイの識別子のパケットにアクセスすることと、第１のジオメトリ・アクセラレイション要素によって境界を定められたプリミティブの一部分の境界を定める他のジオメトリ・アクセラレイション要素を決定することとを有する方法を実施するためのものである。この方法は、各パケットがレイ識別子を収容している複数のパケット、および、他のジオメトリ・アクセラレイション要素のうちの異なるジオメトリ・アクセラレイション要素のそれぞれの指標をインスタンス化する工程と、複数のパケットを各パケットの中で特定されたすべてのレイより少ない交差テストのためそれぞれに構成された複数のコンピューティング資源の１つずつへ提供する工程とをさらに有する。この方法は、複数のコンピューティング資源から検出された交差の指標を受信する工程と、スレッショルド個数の受信された指標より多くの次のジオメトリ・アクセラレイション要素を特定するまで、ジオメトリ・アクセラレイション要素に応じて、受信された指標を追跡し、次のパケットを用いるアクセスを繰り返す工程とをさらに有する。]
[0029] さらに別の観点は、形状をレイと交差テストするため構成された複数のコンピューティング資源と、コンピューティング資源の１つずつと連結され、シーンの中を進む複数のレイのうちのいくつかを定義するデータを格納するそれぞれのキャッシュと、複数のコンピューティング資源の間でメッセージを送るチャネルとを有し、１つずつのコンピューティング資源がこのコンピューティング資源によって受信されたメッセージの中のデータを複数のレイ識別子を収容するものとして解釈し、このコンピューティング資源のキャッシュがこのコンピューティング資源の中に格納された複数のレイのうちのいずれかを有するかどうかを決定し、格納されたレイを関連付けられている形状とテストするため構成されている、レイトレーシング・システムを含む。]
[0030] さらに別の観点は、３次元シーンを構成するプリミティブとレイを交差テストするシステムを含む。このシステムは、各交差テスト資源が幾何学的形状との交差に関してそれぞれのレイをテストするため動作する複数の交差テスト資源を有する。それぞれのレイは、各交差テスト資源に提供された参照情報によって指定される。各交差テスト資源は、レイとプリミティブとの間の交差の指標を第１の出力または第２の出力のいずれかへ出力するためさらに構成されている。システムは、検出された交差のためのシェーディングコードを実行するため動作する複数のシェーディング資源と、レイへの参照情報を維持し、テストされるべきレイを指示するためレイ参照情報を複数の交差テスト資源へ提供するため動作するレイ・コレクション・マネージャをさらに有する。第１の出力は入力を複数のシェーディング資源へ提供し、レイとプリミティブとの間の交差の指標を受信し、第２の出力は、入力をレイ・コレクション・マネージャへ提供し、レイとジオメトリ・アクセラレイション要素との間の交差の指標を受信する。]
[0031] さらに別の観点は、特定された幾何学的形状との交差がテストされるべき複数のレイを定義するデータを格納するため構成されたローカルキャッシュに連結されたプロセッサと、プロセッサによりサービスが提供される入力キューとを含み、入力キューに受信されたデータが、指定された幾何学的形状との交差に関してテストされるべきレイの複数の識別子を含むものとしてプロセッサによって解釈可能であり、プロセッサは、プロセッサのローカルキャッシュに格納されているデータが存在する入力キューの中で特定されたレイだけに対する定義データを取り出し、このようなレイを特定された幾何学的形状と交差テストし、検出された交差の指標を出力するため構成されている、並列レイトレーシングに基づいて３次元シーンの２次元表現をレンダリングするのに用いられるコンピューティング構成を含む。]
[0032] さらに別の観点は、プリミティブの選択の境界を定めるジオメトリ・アクセラレイション要素と交差していると決定されたレイの識別子のパケットにアクセスすることと、交差したジオメトリ・アクセラレイション要素によって境界を定められたプリミティブの一部分の境界を定める他のジオメトリ・アクセラレイション要素を決定することとを有するレイトレーシング方法を実施する機械読み取り可能な命令を含む、コンピュータ読み取り可能な媒体を含む。この方法は、各パケットがレイ識別子を収容している複数のパケット、および、他のジオメトリ・アクセラレイション要素のうちの異なるジオメトリ・アクセラレイション要素のそれぞれの指標をインスタンス化する工程と、複数のパケットを各パケットの中で特定されたすべてのレイの交差テストのためそれぞれに構成された複数のコンピューティング資源の１つずつへ提供する工程とをさらに有する。この方法は、複数のコンピューティング資源から検出された交差の指標を受信する工程と、ジオメトリ・アクセラレイション要素に応じて、受信された指標を追跡する工程とをさらに有する。]
[0033] さらに別の観点は、３次元シーンを構成するプリミティブとの交差に関してテストされるべき複数のレイを定義するレイ定義データを決定する工程を含む、レイトレーシングの方法を含む。この方法は、レイ定義データのサブセットを幾何学的形状とレイを交差テストするため構成された複数のコンピューティング資源のそれぞれのローカルメモリの間に分散させる工程と、管理モジュール内で、コンピューティング資源によって交差テストされるべき複数のレイからレイのコレクションを決定する工程とをさらに含む。コレクションは、各々がレイの定義データ以外のデータを含む複数のレイ識別子によって定義され、プリミティブの一部分の境界を定める境界形状と関連付けられている。この方法は、決定されたコレクションのためのレイ識別子をコンピューティング資源の間で伝えることにより、コンピューティング資源に決定されたコレクションのレイをテストさせる工程をさらに含み、定義データがコンピューティング資源のためのローカルメモリの中に格納されている特定されたレイを交差テストすることによって各コンピューティング資源がそれぞれに応答する。]
[0034] いずれの観点においても、ローカルキャッシュに格納されている複数のレイは、第２の複数のレイの互いに素なサブセットであることが可能であり、複数のレイ識別子のうちのいくつかは、ローカルキャッシュに格納されたレイを特定し、第２の複数のレイのうちのいくつかのレイはローカルキャッシュに格納されていない。]
[0035] 記載されている機能的観点は、適切なハードウェア資源を記載されているように入力および出力を生成するため動作できるように構成するコンピュータ実行可能なコードのモジュールのようなモジュールとして実施可能である。]
図面の簡単な説明

[0036] 本明細書中に開示された態様および実施例のより十分な理解のため、以下の記載において添付図面が参照される。
図１は、レイトレーシングを用いてシーンをレンダリングするシステムの第１の実施例を図示する。
図２は、図１の一部の付加的な態様を図示する。
図３は、レイトレーシング・レンダリング・システムの交差テスト部の別の実施を図示する。
図４は、図１〜３のシステムで用いられる交差テストのコンピューティング資源の実施例を図示する。
図５は、レイトレーシングで用いられる交差テスト・システム・アーキテクチャのさらなる実施例を図示する。
図６は、交差テストのアーキテクチャの別の実施例の態様を図示する。
図７は、キューによって連結された交差テスト資源およびシェーディング資源を含む図１〜６による開示内容の態様を実施するシステムアーキテクチャを図示する。
図８ａは、図１〜７によるシステムにおいてレイトレーシングを制御する際に使用可能であるレイの識別子を提供する態様を図示する。
図８ｂは、図１〜７によるシステムにおいてレイトレーシングを制御する際に使用可能であるレイの識別子を提供する態様を図示する。
図９ａは、図１〜７のいずれかの交差テスト資源に提供可能であるメモリ内のレイデータを特定するためにレイＩＤを使用する実施例を図示する。
図９ｂは、図１〜７のいずれかの交差テスト資源に提供可能であるメモリ内のレイデータを特定するためにレイＩＤを使用する実施例を図示する。
図１０は、図１〜７のシステムにおいて実施可能である複数の交差テスト資源の間での交差テスト制御および形状分散の態様を図示する。
図１１は、図１〜１０のシステムの態様がレイトレーシングのアーキテクチャを使用するときに実施可能であるマルチプロセッサアーキテクチャを図示する。
図１２は、図１〜１１による開示内容の実施を達成可能である資源間通信およびローカライズされたレイデータ記憶装置を用いる複数のコンピューティング資源の体系化を図示する。
図１３は、図１２のコンピューティング資源の一部として動作する複数のスレッドまたはコアの実施例を図示する。
図１４ａは、図１〜１３によるシステムおよびアーキテクチャのために役立つ様々なキューイングの実装を図示する。
図１４ｂは、図１〜１３によるシステムおよびアーキテクチャのために役立つ様々なキューイングの実装を図示する。
図１４ｃは、図１〜１３によるシステムおよびアーキテクチャのために役立つ様々なキューイングの実装を図示する。
図１５は、レイデータが複数のコンピューティング資源によって共有されるＬ２キャッシュからプライベートＬ１キャッシュの間に分散可能である様々な方法を図示するため使用される。
図１６は、これらの開示内容を通じてキューの中に存在可能であるパケットの中のデータの実施例を図示する。
図１７は、特有のコンピューティング資源が、交差テスト中にローカルに利用可能なレイデータを使用し、このテストの結果をライトバックして、パケットからのレイＩＤを処理する方法に関係する開示を行う。
図１８Ａは、レイＩＤ情報の例示的なＳＩＭＤアーキテクチャ処理パケットの態様を図示する。
図１８Ｂは、レイＩＤ情報の例示的なＳＩＭＤアーキテクチャ処理パケットの態様を図示する。
図１９は、レイ識別子を分散し、レイをテストし、テスト結果をさらなるテストのためさらなるパケットに融合する概念を図示する。
図２０は、データ構造との関連で、上述の図によるシステムに一般に適用可能である方法ステップを図示する。
図２１は、本開示内容によるさらなる方法の態様を図示する。] 図１ 図１０ 図１１ 図１２ 図１３ 図１４ａ 図１４ｂ 図１４ｃ 図１５ 図１６
実施例

[0037] 以下の説明は、当業者が本発明の様々な態様を構成し、使用することを可能にさせるため提示されている。具体的な技術、実施、および用途の説明は単に実施例として与えられている。本明細書中に記載された実施例に対する種々の変更は当業者に明白であり、本明細書中に記載された一般的な原理は、本発明の範囲から逸脱することなく他の実施例および用途に適用される。本説明は、最初に、図２の実施例の場合と同様に、ジオメトリ・アクセラレイション・データを使って抽出できる３次元（３−Ｄ）シーン（図１）の実施例に関係する態様を紹介することにより進む。このような３次元シーンは、図示され説明された実施例によるシステムおよび方法を使って２次元表現としてレンダリングできる。] 図１ 図２
[0038] 背景技術の欄に紹介されているように、３次元シーンは、表示用の２次元表現に変換されるべきである。このような変換は、シーンが観察されるカメラ位置を選択することを必要とする。カメラ位置は、シーンの観察者（例えば、ゲームをする人、動画を見る人など）の位置を示すことがよくある。２次元表現は、通常は、２次元表現が所望の解像度で画素のアレイを含むように、カメラとシーンとの間の平面位置にある。各画素の色ベクトルはレンダリングを通じて決定される。レイトレーシング中に、レイは、所望の点で２次元表現の平面と交差するように、最初にカメラ位置から放たれることが可能であり、その後に３次元シーンに続く。レイが２次元表現と交差する位置は、そのレイと関連付けられたデータ構造体の中に保持される。]
[0039] カメラ位置は、必ずしも空間内に定義された単一の点でなくてもよく、その代わりに、カメラ位置は、レイがカメラ位置の範囲内であるとみなされる数の点から放たれるように、拡散してもよい。各レイは、サンプルと呼ばれることもある画素の範囲内で２次元表現と交差する。いくつかの実施では、レイが画素と交差するロケーションのより正確な位置が記録され、色のより正確な補間および混合を可能にする。]
[0040] 説明を明確にするため、ある一定のタイプの物体のデータ、例えば、プリミティブ（例えば、三角形の３頂点の座標）は、物体のデータを参照するのではなく、物体自体として簡単に記載されることがよくある。例えば、「プリミティブをフェッチする」というとき、そのプリミティブの物理的な実現ではなく、そのプリミティブを表すデータがフェッチされると理解されるべきである。しかし、特にレイに関して、本開示は、レイの識別子とレイ自体を定義するデータとを区別し、用語「レイ」が使用されるとき、文脈がそうではないことを明らかにしない限り、レイＩＤとレイを定義するデータとの両方の総称であるとみなされる。]
[0041] ３次元シーンの中の現実的、かつ、精細な物体の輪郭の表現は、通常は、物体の表面を近似する多数の小さい幾何学的プリミティブを設けることによって行われる（すなわち、ワイヤ・フレーム・モデル）。したがって、より複雑な物体は、より単純な物体より多くのプリミティブおよび小さいプリミティブを使って表現されることが必要である。より高い解像度という利点を与えるが、特に、複雑なシーンは多数のオブジェクトを有することができるので、（上述のように、および下記にさらに詳細に示される）レイと多数のプリミティブとの間で交差テストを実行することは計算集約的である。交差テストのためシーンに何らかの外部からの体系化を加えることなく、各レイは各プリミティブとの交差をテストされるべきことになり、非常に遅い交差テストをもたらすことになる。したがって、レイ毎に必要とされるレイ／プリミティブ交差テストの回数を削減する方法は、シーンの中のレイ交差テストを加速するために役立つ。このような交差テストの回数を削減する一つの方法は、ある程度の数のプリミティブの表面を抽出する過剰なバウンディング面を設けることである。レイは、各レイと交差テストするプリミティブのより小さいサブセットを特定するため、最初にバウンディング面に対して交差テスト可能である。このようなバウンディング面形状は種々の形状で設けることが可能である。本開示では、このようなバウンディング面要素のコレクションはジオメトリ・アクセラレイション・データ（以下、ＧＡＤと称される）と称される。]
[0042] ＧＡＤ体系化、要素、および用途のより広範囲にわたる取り扱いは、２００７年９月１７日付で出願され、参照により本明細書に組み込まれる米国特許出願第１１／８５６，６１２号に見られる。よって、ＧＡＤのより簡便な取り扱いが前後関係のためここに記載され、これらの問題に関するさらなる詳細は上述の参照された出願から入手できる。]
[0043] 紹介されているように、ＧＡＤ要素は、一般に、幾何学的形状の表面とレイとが交差しないことが、レイがその形状によって境界を定められたいずれのプリミティブとも交差しないことを示すように、３次元空間の中で、プリミティブのそれぞれのコレクションを囲む幾何学的形状を含む。ＧＡＤ要素は、球体、軸方向整列バウンディングボックス、ｋｄツリー、オクツリー、および他の種類のバウンディングボリューム階層を含むことが可能であり、したがって、本開示による実施は、ｋｄツリーのカッティングプレーン法、または、１若しくはそれ以上のシーンプリミティブの境界を定めるバウンディング面を見出し、バウンディング面の広がりを特定する別の方法のようなバウンディングスキームを使用可能である。要約すると、ＧＡＤ要素は、主に、レイとプリミティブとの間の交差をより迅速に特定するためプリミティブの抽出に役立つので、ＧＡＤ要素は、好ましくは、レイとの交差を容易にテストできる形状である。]
[0044] ＧＡＤ要素は互いに相互に関係付け可能である。ＧＡＤ要素の相互関係付けは、本明細書中では、ＧＡＤ要素を表現するノードと、２つのＧＡＤ要素の間の相互関係付けを表現するエッジとを含むグラフであることが可能である。１対の要素がエッジによって接続される場合、エッジは、ノードのうちの一方がもう一方とは異なる相対的な粒度を有することを示すことがあり、すなわち、そのエッジによって接続されたノードのうちの一方はもう一方のノードより多いまたは少ないプリミティブの境界を定めるエッジによって接続されることを意味することが可能である。いくつかの場合、グラフは、グラフに方向付きであるように階層的であることが可能であり、グラフは親ノードから子ノードの順序にトラバース可能であり、残りの境界が定められたプリミティブを途中で狭小化する。いくつかの場合、グラフは、所定のＧＡＤ要素が他のＧＡＤ要素の境界を定める場合に、その所定のＧＡＤ要素がプリミティブの境界を直接的に定めることがないように（すなわち、均一なＧＡＤ構造では、プリミティブがリーフノードＧＡＤ要素によって直接的に境界を定められ、非リーフノードがプリミティブではなく他のＧＡＤ要素の境界を直接的に定めるように）均一なＧＡＤ要素を有することが可能である。]
[0045] ＧＡＤ要素のグラフは、各ＧＡＤ要素によって境界を定められたある程度の数の要素および／またはプリミティブにおいてある均一性を維持することを目標として構築可能である。所定のシーンは、このような目標が達成できるまで細分可能である。]
[0046] 以下の説明中、所定のＧＡＤ要素と交差することが決定されたレイに基づいて、他のどのＧＡＤ要素が呼応して次にテストされるべきであるかを決定する仕組みが存在するとされる。階層グラフの実施例では、したがって、次にテストされる要素は、一般に、テストされたノードの子ノードである。]
[0047] ある程度の数の実施例において実施されるＧＡＤの一用法は、本明細書中では、レイが所定のＧＡＤ要素と交差することが見出されたとき、このレイが同様にこの要素と交差することが決定されている他のレイと共に収集されることである。ある程度の数のレイが収集されたとき、この要素に接続されているＧＡＤ要素のストリームは、主メモリからフェッチされ、各テスタが異なる収集されたレイを有するテスタを通じてストリーム化される。したがって、各テスタは、各テスタのレイをローカル高速メモリの中に固定的に維持し、一方、ジオメトリは、必要とされるときに、遅いメモリからフェッチされ、書き換えが許可される。より一般的には、この説明は、コンピューティング資源が、このようなレイと幾何学的形状（ＧＡＤ要素およびプリミティブ）との交差を検出するためレイを処理し、最終的に、どのレイがどのプリミティブにヒットするかを特定するように体系化可能である方法についての一連の実施例を提供する。]
[0048] これらの実施例が実施可能である他の態様は、（１）交差テストからシェーディングへの出力のためのキューが設けられていること、（２）そのレイデータが計算資源にある程度までローカライズされ、ある一定のレイを幾何学的形状とテストすることが決定されたときにそれらの幾何学的形状がより遅いメモリからフェッチされること、および、（３）その交差テストが交差テストを実行する計算資源へのレイを（レイ識別子を使用して）特定することにより駆動され、各計算資源に各計算資源のローカライズされた（複数の）メモリから特定された（複数の）レイに対応するデータをフェッチさせることと、のうちのいずれかを含む。]
[0049] 以下の説明は、レイトレーシングを使用して３次元シーンの２次元表現をレンダリングするシステムおよびシステムの一部の実施例を提示する。このようなシステムの２つの主な機能コンポーネントは、（１）交差を特定するレイをトレーシングすること、および、（２）特定された交差をシェーディングすることである。]
[0050] 図１は、プリミティブで構成されたシーンをレイトレーシングする際に用いられるシステムの態様を図示する。一般に、図１および他の図におけるいずれかの機能ユニットのいずれかの機能または役目は、複数のハードウェアユニット、または、ソフトウェア部品、ソフトウェアサブルーチンで実施されることがあり、異なるコンピュータで実行されることさえある。いくつかの場合、このような実施は、システム機能および性能に影響を与えることが可能であるので、より具体的に記載されている。] 図１
[0051] 図１は、ジオメトリユニット１０１と、交差処理ユニット１０２と、サンプル処理資源１１０と、フレームバッファ１１１と、ＧＡＤ要素およびプリミティブを含むジオメトリ形状（プリミティブおよびＧＡＤ記憶装置１０３）、サンプル１０６、レイ・シェーディング・データ１０７、および、テクスチャデータ１０８を格納するため動作可能であるか、若しくは、構成され、または、格納しているメモリ資源１３９と、を図示する。ジオメトリユニット１０１は、レンダリングされるべきシーンの記述を入力し、プリミティブ、および、プリミティブの境界を定めるＧＡＤ要素を含むアクセラレイション構造を出力する。交差処理１０２は、レイとプリミティブとの間の特定された交差をシェードし、テクスチャ、シェーディングコード、および、図示されたデータ源から取得される他のサンプル情報のような入力を使用する。交差処理１０２の出力は、レンダリングされているシーンの２次元表現を生成する際に使用される新しいレイ（後述される）およびカラー情報を含む。これらの機能コンポーネントのすべては、破線１８５によって全体的に指定された１若しくはそれ以上のホスト処理資源で実施可能である。] 図１
[0052] 上述されているように、特定されたレイ／プリミティブ交差のシェーディング中に、交差処理１０２は、交差テストされるべき新しいレイを発生可能である。ドライバ１８８は、交差処理１０２とインターフェイスをとって、これらの新しいレイを受信し、交差処理資源１０２と、レイデータ記憶装置１０５および交差テストユニット１０９を含むローカライズされた交差テスト領域１４０との間の通信を管理する。交差テスト領域１４０は、交差に関してレイをテストし、インターフェイス１１２を介して、プリミティブおよびＧＡＤ記憶装置１０３へのリードアクセス権を有し、結果インターフェイス１２１を介して特定された交差の指標を交差処理１０２へ出力する。ローカル・レイ・データ記憶装置１０５は、比較的小さいサイズであることが可能な比較的高速なメモリで実施されることが好ましいが、プリミティブおよびアクセラレイション構造記憶装置は、ホスト１８５の主ダイナミックメモリであることが可能である比較的大規模かつ遅い主メモリ１３９で実施される。]
[0053] レイトレーシング高解像度シーンの一態様は、膨大な量のレイデータおよび形状データが含まれている。例えば、毎秒３０フレームでフルＨＤ解像度フィルムをレンダリングすることは、１秒間に６０００万画素（１９２０×１０８０>２Ｍ、３０回毎秒）以上の色を決定することを必要とする。さらに、各画素色を決定するため、多数のレイが必要とされることがある。したがって、数億のレイが毎秒処理されるべきことがあり、あらゆるレイが数バイトの格納場所を必要とする場合、フルＨＤシーンのレイトレーシングは、毎秒数ギガバイト以上のレイデータを必要とすることが可能である。さらに、いずれかの所定の時間に、多数のレイデータがメモリに格納されるべきである。アクセス速度とメモリサイズとの間には、費用対効果のよい大規模メモリは比較的低速であるという程度に、殆ど常にトレードオフの状況が存在する。さらに、大規模メモリは、十分に大規模なデータのブロックがアクセス可能かつ使用可能でない限りメモリが効率的に使用されないように構築される。したがって、１つの難問は、メモリから効率的にアクセスするため十分に大規模なレイのグループを一貫して特定できるようにすることである。しかし、類似した始点および方向をもつレイの検出およびグループテストのようなアプローチによってわかるように、このようなレイを特定する際に、処理オーバーヘッドが存在し、場合によっては非常に高い処理オーバーヘッドが存在することが可能である。一態様では、以下の例示的なアーキテクチャは、シーンレンダリングのためレイ交差テストおよびシェーディングのスループットを高めるために、複数のコンピューティング資源と、高速で高価なメモリと、低速で大規模なメモリとを体系化し使用する方法を開示する。]
[0054] 図１は、このように、ＧＡＤ要素およびプリミティブとの交差に関してレイをテストする計算資源１０９にローカライズされた高速メモリに格納されているレイ定義データを含むデータのフローによって、特定された交差のシェーディングからの交差テストの分離を図示する。交差テスト１０９の出力は、特定されたプリミティブと交差する特定されたレイの指標を含む。交差処理１０２は、これらの指標を受け取り、これらの交差に従ってシェーディングを実行し、テストのため、最終的に高速レイ・データ・メモリ１０５に格納される新しいレイをインスタンス化可能である。このような分離は、使用される処理資源に応じて選択された通信手段と共に、１若しくはそれ以上の固定機能ハードウェアおよびこの説明に応じたソフトウェアでプログラムされた汎用コンピュータを使用する種々の実施において行われることが可能である。しかし、これらの実施における一つの反復性のある態様は、レイとの交差に関してテストされた形状データがレイ定義データと比較すると交差テスト領域１４０において一過性であるということである。換言すると、適用できる場合には、高速メモリが主としてレイデータに割り当てられ、一方、形状はテスタを通じてストリーム化されるが、このような形状データのキャッシュ化を最適化するため計算資源は殆ど使用されない。種々の以下の図は、このような分離、データフロー、レイデータ記憶装置、および、交差テスト資源との結び付きのより具体的な実施例を図示する。] 図１
[0055] 図１は、最終的にフレームバッファ１１１の出力がディスプレイ１９７を駆動するため使用可能であることをさらに図示する。しかし、これは、便宜上レンダリングと称されることがある交差テストおよびシェーディング操作から生じることが可能である出力の単なる実施例である。例えば、出力はさらに、後で表示するため、若しくは、有形的なコンピュータ読み取り可能な媒体で配布するため、レンダリングされた画像の系列のようなレンダリング生成物を含むコンピュータ読み取り可能な媒体に書き込まれるか、または、通信リンクによって相互接続されたコンピューティング資源を含むネットワークを介して伝送されることが可能である。いくつかの場合に、レンダリングされる３次元シーンは、没入型の仮想現実会議の場合、または、３次元ＣＡＤモデルの斜視図を含む画像のレンダリングの場合のように、現実の世界の３次元シーンを表すことが可能である。そのような場合、レンダリングの方法が、物理的な物体を表すデータに影響を及ぼす、または別の方法でデータを変換する。他の場合に、３次元シーンは、物理的な物体および物理的でない他の物体を表すいくつかの物体を有することができる。さらに別の３次元シーンでは、シーンの全体は、ビデオゲームなどの場合と同様に、架空であることがある。最終的には、しかし、一般的に、これらの方法は、メモリ、ディスプレイ、および／または、コンピュータ読み取り可能な媒体の物の変形である。] 図１
[0056] さらに、１９７９年以来、レイトレーシングを用いるレンダリングが実施され、種々の手法が交差テストおよびレイトレーシングを用いるレンダリングを実施するため必要とされる他の機能のため開発されている。したがって、本明細書中に記載されている具体的なアーキテクチャおよび方法は、３次元シーンを２次元表現にレンダリングする際に用いられるレイトレーシングの基本的原理の占有権を行使しない。]
[0057] 図２は、交差テスト領域１４０の交差テストユニット１０９が、レイに対して幾何学的形状をテスト可能である１若しくはそれ以上の個別のテスト資源（別名テストセル）を含むことを図示する。領域１４０は、それぞれがレイデータ記憶装置１０５からレイデータを受信し、メモリ１３９から幾何学的形状データを受信するテストセル２０５ａから２０５ｎを含む。各テストセル２０５ａ〜２０５ｎは、結果インターフェイス１２１を介した交差処理１０２への通信のための、所定のレイが所定のプリミティブに交差したかどうかの指標を含むことが可能である結果を生成する。それに反して、ＧＡＤ要素とレイとの交差テストの結果はロジック２０３に提供される。ロジック２０３は、レイをレイが交差していると決定されたＧＡＤ要素に関係付けるレイへの参照情報のコレクション２１０を維持する。] 図２
[0058] 一般に、システムコンポーネントは、所定の特定のレイテストの未知の終了までの時間をサポートするように設計される。交差テストユニット１０９は、ジオメトリメモリへのリードアクセス権を有し、入力としてレイへの参照情報のキューを有する。交差テストの出力として、各レイは、各レイが最初に交差したジオメトリの部分（便宜上本開示ではプリミティブと称される）と関連付けられる。他のジオメトリの部分（すなわち、複数のプリミティブ）は無関係であると見なすことができる。]
[0059] 上述されているように、領域１４０は、テストセル２０５ａ〜２０５ｎにおいてテストされるべきレイコレクションのリスト２１０を維持するレイ参照情報バッファおよび関連付けられたマネージメントロジック２０３を含む。バッファ・マネージメント・ロジック２０３は、固定機能処理資源、または、コンピュータ読み取り可能な媒体から取得された命令を使って構成されたハードウェアで実施可能である。このような命令は、本明細書中ではロジック２０３に帰属させられた機能およびタスクに応じたモジュールの中に体系化可能である。当業者は、これらの開示内容に基づいてロジック２０３のさらなる実施を提供することも可能である。]
[0060] ロジック２０３は、レイおよびジオメトリをテストセルに割り当て可能であり、設計の中の他のユニットとの通信を取り扱い可能である。一態様では、リスト２１０の中の各レイコレクションは、１若しくはそれ以上の幾何学的形状との交差をテストされるべき複数のレイ識別子だけを含み、ロジック２０３はこのようなレイコレクションを維持する。より具体的な実施例では、複数のレイ識別子は、コレクションの中に特定されたＧＡＤ要素と交差することが決定され、複数のレイとの交差をテストされるべき次のＧＡＤ要素は、ＧＡＤ要素のグラフの中のその交差したＧＡＤ要素に関係付けられる。所定のコレクションに対し関係付けられた要素は、これらの要素との交差テストが開始されるときにメモリ１３９からフェッチされる。]
[0061] 換言すると、ロジック２０３は、一時的なレイ参照情報バッファの中のそれぞれの子ノードに対応するジオメトリデータの小部分と交差するレイを表す参照情報を保持可能であり、このようなレイのさらなる処理の延期を可能にする。階層的に配置されたＧＡＤの実施例では、このような延期は、子ノードのジオメトリの小部分と交差するレイの累積数がさらなる処理のため適当であることが判明するその後の時点まで、子ノードより下位にあるジオメトリ・アクセラレイション・データの小部分に対する処理を延期可能である。]
[0062] ロジック２０３は、テスト用の幾何学的形状をテストセル２０５ａ〜２０５ｎへ提供するメモリトランザクションをセットアップするためメモリ１３９とさらに通信可能である。ロジック２０３は、レイデータ記憶装置１０５とさらに通信し、そこにデータが格納されているレイを決定する。いくつかの実施では、ロジック２０３は、メモリ１３９または交差処理ユニット１０２の中で実行するシェーディングプロセスからレイを取得または受信し、スペースが利用可能であるとき、交差テスト中の格納および使用のためこれらのレイをメモリ１０５へ提供する。]
[0063] よって、ロジック２０３は、ＧＡＤ形状の識別子とのレイ識別子の関連性を含む一時的なレイ参照情報バッファを維持可能である。実施では、ＧＡＤ要素のための識別子は、そのＧＡＤ要素と関連付けられた所定のコレクションを格納するバッファの中の位置を特定するためハッシュ化可能である。関連性は、このようなデータのメモリへの格納または収集を記述するとき、本明細書中ではコレクションと総称され、本願のいくつかの場所では、一般に、テスト中のコレクションデータの移動と、交差テストからの結果の返送を意味するために、用語「パケット」が使用される。このような返送された結果は、後述されるように、ＧＡＤ形状と関連付けられているメモリ内に格納されたコレクションに融合可能である。]
[0064] 要約すると、図２は、レイ定義データが高速メモリ１０５に格納され、このようなレイとの交差に関してテストされるべき形状データがメモリ１３９から到来することを引き続き図示する。上記開示は、複数の次にテストされるべき形状が同時にメモリ１３９からフェッチされ、「親」ＧＡＤ要素と交差していることが既知であるレイのグループとの交差に関して順次にテストされることが好ましいということをさらに明らかにする。] 図２
[0065] 今度は、図３は、３次元シーンの２次元表現をレイトレーシングするレンダリングシステムで使用可能である領域１４０（図１）の交差テストユニット（ＩＴＵ）３５０による実施の実施例のブロック図を含む。ＩＴＵ３５０は、複数のテストセル３１０ａ〜３１０ｎおよび３４０ａ〜３４０ｎを含む。ＧＡＤ要素は、ＧＡＤデータ記憶装置１０３ｂから提供されるものとして図示され、プリミティブデータはプリミティブデータ記憶装置１０３ａから提供される。] 図１ 図３
[0066] テストセル３１０ａ〜３１０ｎは、ＧＡＤ要素、および、これらのＧＡＤ要素とテストされるレイデータを受信する（すなわち、これらのテストセルがＧＡＤ要素をテストする）。テストセル３４０ａ〜３４０ｎは、プリミティブデータ、および、これらのプリミティブとテストされるレイデータを受信する（すなわち、これらのテストセルがプリミティブをテストする）。よって、ＩＴＵ３５０は、プリミティブとの交差に関してレイのコレクションをテスト可能であり、ＧＡＤ要素との交差に関して別個のレイのコレクションをテスト可能である。]
[0067] ＩＴＵ３５０は、コレクション・マネージメント・ロジック２０３ａおよびコレクションバッファ２０３ｂをさらに含む。コレクションバッファ２０３ｂおよびレイデータ１０５は、（例えば）メモリ１３９からレイデータを受信可能であるメモリ３４０に格納可能である。コレクションバッファ２０３ｂは、ＧＡＤ要素と関連付けられたレイ参照情報を維持する。コレクション・マネージメント２０３ａは、テストセルからの交差情報に基づいてこれらのコレクションを維持する。コレクション・マネージメント２０３ａは、レイコレクションをテストするためメモリ１３９からのプリミティブおよびＧＡＤ要素のフェッチを開始することもできる。]
[0068] ＩＴＵ３５０は、結果インターフェイス１２１を介して交差処理１０２へ最終的に提供するため出力バッファ３７５に一時記憶可能である特定された交差の指標を返送する。指標情報は、レイと、所定の精度の範囲内でレイが交差すると決定されたプリミティブとを特定するために十分である。]
[0069] ＩＴＵ３５０は、ＩＴＵ３５０にレイと、レイが交差に関してテストされることになる幾何学的形状とを与える制御プロセスまたはドライバ（例えば、ドライバ１８８）を通じて呼び出すことができる関数またはユーティリティであるとみなすことができる。例えば、ＩＴＵ３５０は、ドライバ１８８を介して、すなわち、ＩＴＵ３５０をシェーディングのような他のレンダリングプロセスおよび初期レイ生成関数とインターフェイス接続するプロセスを介して情報を提供されることが可能である。ＩＴＵ３５０の観点から、ＩＴＵ３５０は、領域１４０が、提供されるか、または、提供された他の情報に基づいて取得されるレイ、ＧＡＤ、およびプリミティブ（または、より一般的にはシーンジオメトリ）を使用して交差テストを実行できるので、提供された情報の基点に気付く必要がない。]
[0070] 上述されているように、ＩＴＵ３５０は、ＩＴＵ３５０が受動的でないように、どのように、いつ、そして、どのようなデータがＩＴＵ３５０に提供されるかを制御し、そして、例えば、交差テストのため必要に応じて、レイ、または、ジオメトリデータ、または、アクセラレイションデータをフェッチすることができる。例えば、ＩＴＵ３５０は、レイがテストされるべきシーンを特定するために十分な情報と共に、交差テストのための多数のレイを提供されることができる。例えば、ＩＴＵ３５０は、所定の時点に交差テストのため１００００より多くのレイを提供されることができ、そして、これらのレイのテストが終了するとき、後述されるように、（交差処理１０２によって発生させられた）新しいレイがＩＴＵ３５０の中で処理されているレイの数をおおよそ初期数に保つために提供されることができる。ＩＴＵ３５０は、その後、処理中に（レイ・コレクション・バッファ２０３ｂにおいて（図３を参照のこと）、レイの一時的格納を制御し（ロジック２０３ａにおいて（図３を参照のこと））、処理中に必要に応じてプリミティブおよびＧＡＤの要素のフェッチを開始することができる。] 図３
[0071] 上述されているように、レイを定義するデータがレイデータ１０５に維持されている間に、レイ識別子はバッファ２０３ｂの中に維持され、ＧＡＤ要素に関して体系化されるので、ＧＡＤ要素およびプリミティブは、レイと比べるとＩＴＵ３５０において一時的である。バッファ２０３ｂおよびレイデータ１０５のそれぞれは、ＳＲＡＭキャッシュの１若しくはそれ以上のバンクのような様々な方法で物理的に実施でき、メモリ３４０に維持することができる。]
[0072] 上述されているように、ロジック２０３ａは、メモリ３４０に格納されたレイコレクションの状態を追跡し、処理の準備ができているコレクションを決定する。図３に示されているように、ロジック２０３ａは、メモリ３４０に通信的に連結され、テストのため接続されたテストセルの１つずつへのレイの分散を開始できる。ＧＡＤ要素が、ＧＡＤ要素およびプリミティブの組み合わせではなく、ＧＡＤ要素だけ、または、プリミティブだけの境界を定める状況では、ロジック２０３ａは、特有のコレクションがプリミティブまたは他のＧＡＤ要素の境界を定めるＧＡＤ要素と関連付けられているかどうかに依存して、テストセル３４０ａ〜３４０ｎまたはテストセル３１０ａ〜３１０ｎのいずれかにレイを割り当てることが可能である。] 図３
[0073] 特有のＧＡＤ要素が他のＧＡＤ要素およびプリミティブの両方の境界を定めることができる実施例では、ＩＴＵ３５０は、レイと共に、ＧＡＤ要素およびプリミティブの両方を各テストセルへ提供するデータ経路を有することになるので、ロジック２０３ａは、テスト資源の間でコレクションのテスト用レイを準備することになる。このような実施例では、ＧＡＤ要素とプリミティブとの間の形状の典型的な差（例えば、球体対三角形）のため、テストロジックを切り替えるか、または、テストされる形状のため最適化された交差テストアルゴリズムをロードする指標がロジック２０３ａから提供されることができる。]
[0074] ロジック２０３ａは、テストセル３１０ａ〜３１０ｎおよびテストセル３４０ａ〜３４０ｎへの情報の提供を直接的または間接的に引き起こすことができる。間接的な状況では、ロジック２０３ａは、各テストセルがメモリ３４０からテスト用のレイデータのフェッチを開始するように、各テストセルに情報を提供可能である。ロジック２０３ａは、説明を簡単にするため、メモリ３４０とは別個に図示されているが、ロジック２０３ａによって実行されるマネージメント機能はメモリ３４０に格納されたデータに主として関係するので、ロジック２０３ａはメモリ３４０の回路の内部に組み込まれることができる。]
[0075] 交差テスト資源によるメモリ３４０へのアクセスの並列化を高める能力は、本明細書中に記載されているいくつかの態様の利点である。したがって、好ましくは、テストセル１つ当たりに少なくとも１つまでメモリ３４０へのアクセスポートの数を増加することは有利である。このような並列化に関係付けられた例示的な編成はさらに後述される。]
[0076] さらに、ＩＴＵ３５０は、入力データをＩＴＵへ提供するか、または、ＩＴＵから出力を受信するユニットに関して非同期式に動作することができる。ここで、「非同期」は、交差テストが前に受信されたレイに対して継続している間に、ＩＴＵが付加的なレイを受信し、付加的なレイの交差テストを開始することを含むことができる。さらに、「非同期」は、ＩＴＵ３５０がレイを受信した順序にレイが交差テストを終了しなくてもよいことを含むことができる。非同期は、ＩＴＵ３５０の中の交差テスト資源が、３次元シーンの中のレイの位置、または、シーンに重畳されたスケジューリンググリッドを考慮することなく、交差テストの割り当てまたはスケジューリングのため、または、親レイおよび少数の親レイから生み出された子レイのような世代間関係を有するテスト専用レイ、あるいは、特殊な世代のレイ、例えば、カメラレイ若しくは２次レイだけをテストするために利用できることをさらに含む。]
[0077] ＩＴＵ３５０は、プリミティブおよびプリミティブと交差したレイの特定された交差の指標を受信する出力バッファ３７５をさらに含む。実施例では、指標は、プリミティブと交差したレイを特定するために十分な情報とペアにされたプリミティブの特定情報を含む。レイの特定情報は、ホストプロセッサが利用できる資源の中に維持されているレイのリストの中の特定のレイを特定するインデックスのような参照情報を含むことができる。例えば、リストは、ホストプロセッサ上で動くドライバ１８８によって維持されることができ、リストはメモリ１３９の中に維持されることができる。好ましくは、メモリ１３９は、メモリ３４０の中にすべてのレイの定義データを含むことができる。しかし、レイ特定情報は、レイを再構成するために十分な、レイの始点および方向のような情報を含むことができる。通常の場合には、より少数のビットが参照情報に合格することが必要とされることになり、有利である。]
[0078] 図４は、ワーキングメモリ４１０およびテストロジック４２０を含むテストセル３１０ａの実施例を図示している。ワーキングメモリ４１０は、表面との交差に関して線分をテストするために十分な情報を収容する数個のレジスタであることができ、または、他の実施ではより複雑であることができる。例えば、ワーキングメモリ４１０は、交差に関して受信された特定の形状をテストするためテストロジック４２０を構成する命令を格納することができ、そして、どのような形状が受信されたかを受信されたデータに基づいて検出することができる。ワーキングメモリ４１０は、さらに検出されたヒットをキャッシュすることができ、各テストセルは幾何学的形状に対し一連のレイをテストするため構成され、または、逆もまた同様であり、したがって、キャッシュされたヒットはグループとして出力されることができる。ワーキングメモリは記憶装置１０３ｂから着信する形状データを受信することもできる。] 図４
[0079] テストロジック４２０は利用可能または選択可能な解像度で交差テストを実行し、交差が検出されたかどうかを示すバイナリ値を返すことができる。バイナリ値は、ＧＡＤ要素テストのためのメモリ３４０におけるリードサイクルのようなリードサイクル中のラッチングのための読み出し、キャッシュ化、または、出力のためワーキングメモリの中に格納可能である。]
[0080] 図５は、例示的なメモリ編成により詳細に重点を置いて、交差テストユニット５００の実施の態様を図示している。ＩＴＵ５００において、テストセル５１０ａ〜５１０ｎおよび５４０ａ〜５４０ｎが現れ、本実施例では、３１０ａ〜３１０ｎおよび５４０ａ〜５４０ｎと対応する。これは、テストセルの数に関する何らかの要件を意味するものではない。よって、ＩＴＵ５００において、プリミティブとＧＡＤ要素の両方が並列にテストされることができる。しかし、１種類または別の種類のそれ以上のテストセルが必要であると決定された場合、どのようなテストセルでも必要に応じて再構成可能である（ハードウェアの場合に再割り当てされ、ソフトウェアの場合に再プログラムされる）。トランジスタ密度が増加し続けると共に、それ以上のこのようなセルをハードウェア実施に（または、ソフトウェアを実行するため利用可能な資源として）収容することができる。記載されるように、テストセルの一部は、共通形状（すなわち、プリミティブまたはＧＡＤ要素）に対してレイをテストするので、オペレーショナル・グループとして取り扱うことができる。テストセル５４０ａ〜５４０ｎは、指定された精度レベル（例えば、１６ビット）でプリミティブとの交差を示すバイナリ値を返すことができ、より大きいプリミティブの場合に役立つことができる、レイが交差したプリミティブ上の場所のより正確な指標を返すこともできる。] 図５
[0081] ＩＴＵ５００において、メモリ５４０は、それぞれが２ポート（特定されたバンク５１５のポート５３１および５３２）を有する複数の独立した演算バンク５１０〜５１５を含む。一方のポートはＧＡＤテストロジック５０５を介してアクセスされ、もう一方はプリミティブ・テスト・ロジック５３０を介してアクセスされる。ＧＡＤテストロジック５０５およびプリミティブ・テスト・ロジック５３０のそれぞれは、それぞれのワーキングバッファ５６０〜５６５と５７０〜５７５との間でデータのフローを管理し、それぞれにＧＡＤ記憶装置１０３ａおよびプリミティブ記憶装置１０３ｂからテストのためのＧＡＤ要素を取得するため動作する。]
[0082] バンク５１０〜５１５は、大部分は、ＧＡＤテストロジック５０５およびプリミティブ・テスト・ロジック５３０によるレイデータへの非競合アクセスをできるようにするため動作するように意図され、その結果、各テストセル５１０ａ〜５１０ｎおよびテストセル５４０ａ〜５４０ｎは別個のバンク５１０〜５１５からレイが提供され得る。このような非競合アクセスは、これらの開示内容から理解されることであるが、例えば、別個のキャッシュバンクによって実施可能であり、同様に、クロス・バー・アーキテクチャはポートによるメモリの異なる物理的部分へのアクセスを可能にする。１若しくはそれ以上のテストセルによるバンクの中に格納されたレイのテストが許可される場合、競合はテストされるべき２つのレイが同じバンクに存在する場合に発生し、このような場合に、アクセスはテストロジック５０５および５３０によって順次に取り扱うことが可能である。いくつかの場合に、ワーキングバッファ５６０〜５６５および５７０〜５７５は、他の処理が完了している間に次の処理のためロードされる。ＩＴＵ５００はさらに領域に編成可能である。例えば、領域５７８は、ＧＡＤテスタ５１０ａおよびメモリバンク５１０を含むので、ＧＡＤ要素のためのテスト領域を構成し、領域５７９は、テスタ５１０ａおよび５４０ａ（ＧＡＤおよびプリミティブのそれぞれに対し１つずつ）と、領域５７８および５７９のテストセルに関係するテストで使用されるべきレイデータを格納するメモリバンク５１０へのアクセスとを含むので、ＧＡＤ要素とプリミティブの両方のためのテスト領域を構成する。]
[0083] 一貫性のある配置でレイをテストすることにより、どのレイがどのテストセルに割り当てられているかの追跡を軽減することが可能である。例えば、各コレクションは、３２レイを有することができ、３２のテストセル３１０ａ〜３１０ｎ（５１０ａ〜５１０ｎ）が存在することができる。例えば、コレクションの中の４番目のレイをテストセル３１０ｄへ一貫して提供することにより、テストセル３１０ｄは、提供されたレイに関する情報を維持する必要はなく、交差の指標を返すことだけが必要である。明らかなように、テストセルの間にレイ識別子のパケットを伝え、テストセルが交差結果をパケットに書き込むことを可能にすることを含む、一貫性を維持する他の実施が提供できる。]
[0084] レイコレクションの格納は、所定のレイコレクションがレイ・コレクション・バッファ２０３ｂまたは５２０のｎ箇所のうちの１つに格納されることができるように、レイコレクションのためのｎウェイ・インターリーブ・キャッシュとして実施されることができる。レイ・コレクション・バッファ２０３ｂまたは５２０は、したがって、バッファのｎ箇所のそれぞれに格納されたレイコレクションのリストを維持することができる。レイ・コレクション・バッファ２０３ｂまたは５２０の実施は、レイコレクションと関連付けられたＧＡＤの要素の識別用特性を使用することを含むことができ、例えば、シーンをレンダリングする際にしようされるＧＡＤの要素の間で一意である識別子文字列が使用できる。英数文字列は、数字、ハッシュなどでもよい。例えば、ハッシュは、レイ・コレクション・バッファ２０３ｂおよび５２０のｎ箇所のうちの１つを参照可能である。]
[0085] 他の実施では、ＧＡＤの要素は、レイ・コレクション・バッファ２０３ｂおよび５２０の所定の箇所への格納を予定されることができ、例えば、使用される英数文字列のセグメントをこのようなバッファの（複数の）箇所へマッピングする。プリミティブ／レイ交差出力５８０は、潜在的なプリミティブ／レイ交差を特定する出力を表現し、出力５８０は直列または並列であることが可能である。例えば、３２のプリミティブ・テスト・セル５４０ａ〜５４０ｎが存在する場合、出力５８０は、直前にテストされたプリミティブに対する各レイの交差の有無を指定する３２ビットを含むことが可能である。当然ながら、出力は、例えば、パケット実施のような他の実施の場合のテストセルから直接的に来ることがある。出力は直列であることが可能であり、テストセルによってパケットの中に直列に格納されることが可能である。]
[0086] レイデータは、シェーダのような光線源からメモリ３４０（５２０）に受け取られる。コレクション・マネージメント・ロジック（例えば、図２および３の２０３ａ）は、各コレクションがＧＡＤの要素と関連付けられている場合、レイをコレクションに初期的に割り当てるため動作する。例えば、ＧＡＤの要素は、グラフのルートノードであることができ、受け取られたすべてのレイは、ルートノードと関連付けられた１若しくはそれ以上のコレクションに初期的に割り当てられる。レイの受け取りは、例えば、入力キューから完全なコレクションになるサイズにされたグループで行われることもでき、各コレクションは、例えば、レイ・コレクション・バッファ２０３ｂの中で特定されたコレクションのように取り扱われることが可能である。] 図２
[0087] ある程度の数のコレクションが並列にテストされることができるという理解の下で、１コレクションの処理に重点を置くと、テストノードと関連付けられたコレクションのレイをメモリ３４０から取り出すことは、例えば、コレクションの中にデータとして格納された、メモリ３４０からの、または、図５の実施例によって、テストセル（例えば、テストセル５６０〜５６５）による受信のため複数の出力ポート上にレイデータを提供するバンク５１０〜５１５からの、このようなレイの取り出しを可能にするこのようなレイのアドレス（レイ識別子）の提供によってコレクション・マネージメント・ロジック２０３ａによって開始される。] 図５
[0088] テストのため選択されたノードによって境界を定められたＧＡＤ要素のテストに関して（すなわち、選択されたノードと関連付けられたＧＡＤ要素が他のＧＡＤ要素の境界を定める）、テスト中のコレクションのレイに関するレイデータの分散が終了し、境界を定められたＧＡＤ要素のフェッチもまた実行される（このようなフェッチは必ずしもレイ分散の次に行われなくてもよい）。このようなフェッチのため、ロジック２０３ａはアドレス指定情報をＧＡＤ記憶装置１０３ｂへ入力可能であり（または、どのようなメモリマネージメント手段が設けられているかとは無関係であり）、ＧＡＤ記憶装置は、アドレス指定された（複数の）ＧＡＤ要素をテストセル３１０ａ〜３１０ｎへ出力する。通常のとおり多数のＧＡＤ要素の境界が定められる場合、要素は、多数のＧＡＤ要素のブロック読み出しを可能にするように、例えば、シリアル化バッファを用いて、テストセルへ直列ストリーム化されるように配置される。]
[0089] テストセル（たとえば、３１０ａ〜３１０ｎ）において、コレクションのレイは、直列に提供されたＧＡＤ要素との交差に関してテストすることが可能である（例えば、各テストセルにおいて異なるレイ）。レイが交差すると決定された場合、交差したＧＡＤ要素に関するコレクションが存在するかどうかが決定され、存在するならば、レイが余地を許すそのコレクションに追加され、存在しないならば、コレクションが作成され、レイが追加される。既存のコレクションに余地がない場合、新しいコレクションが作成される。]
[0090] いくつかの実施では、コレクションのすべてのレイが所定のＧＡＤ要素に対し並列にテストできるように、コレクションの中のレイの最大数対テストセル３１０ａ〜３１０ｎの数の１：１の対応関係が与えられ、この実施は、スループットが概ねレイ対テストセルの１：１の対応関係を用いて取得できる程度であるアーキテクチャを含むことが可能であるが、しかし、所定のコレクションのうちのレイ全体が並列にテスト可能であると見なされるとしても、異なるテストセルが異なるパケットからのレイをテストできるように、異なるテストセルの間でパケット（例えば、上述されているようにコレクションを表す情報）の逐次的な受け渡しを行うことが可能である。]
[0091] その後、レイは、テストセルに提供されたプリミティブとの交差に関してテストされ（すなわち、本実施例では、各テストセルは異なるレイを有し、そのレイと共通プリミティブとをテストする）。テスト後、各テストセルは検出された交差を知らせる。]
[0092] コレクションのうちの各レイは、テストセルに提供されたＧＡＤ要素との交差に関してそのテストセルでテストされる（例えば、図５の複数のバックの実施例（図示されている領域５７８および５７９）では、レイは、例えば、バンクが各種の１若しくはそれ以上のテスタにレイデータを提供するように、ＧＡＤ要素テスト領域および／またはプリミティブテスト領域にローカライズされていると見なされる）。] 図５
[0093] ＧＡＤ要素との交差に関するレイのテストからの出力はプリミティブ交差に関して同じレイをテストする場合と異なるので（すなわち、ＧＡＤ要素との交差はそのＧＡＤ要素のためのコレクションの中への収集を生じるが、プリミティブとの交差はそのプリミティブとの最近接交差の決定と、このような交差の出力とを生じるので）、特定のレイが偶然に並行してテストされている２つのコレクションの中に存在するとしても、コレクションデータまたは出力された交差についてのライトバックへの競合が通常は起こるべきではない。さらなる並列化が、例えば、テストセル３４０ａ〜３４０ｎの複数のインスタンス化においてプリミティブ交差に関してレイの複数のコレクションをテストすることにより実施されるならば、複数の交差の格納のようなこのようなテストの順序正しい終了を強制する、ビットをロックするなどのように特徴が実施されることもできる。そして、図５の実施例では、所定のレイのためのデータが唯一のバンクから１つのテスタタイプに提供可能である場合（すなわち、所定のレイが１つのメモリバンクに位置している場合）、複数のＧＡＤテスタは、例えば、同時に同じレイをテストすることがないので、ライトバック競合の問題を回避する。] 図５
[0094] 要約すると、方法は、レイを受信する工程と、レイをコレクションに割り当てる工程と、準備状況がアルゴリズム的に決定可能である場合にテストの準備ができているコレクションを選択する工程と、選択されたコレクションの中のレイを適切なテストセルに割り当てる工程と、交差テストのため適切なジオメトリをテストセルの中でストリーム化する工程とを含む。出力は、ジオメトリがシーンプリミティブであるか、または、ＧＡＤ要素であるかに依存する。ＧＡＤ要素に対してテストされたレイの場合、ＧＡＤ要素はテスト中のコレクションと関連付けられたノードとのグラフ接続に基づいて特定され、レイはテスト中のＧＡＤ要素と関連付けられたコレクションに追加される。コレクションは準備状況に関して見直され、テストの準備ができたとき選択される。プリミティブとのレイ交差に関して、最近接交差がレイを用いて追跡される。レイは準備完了コレクションと関連付けられたときにテストされるので、暗黙のうちに、特定のレイのための交差テストは、特定のレイが関連付けられたコレクションがテストの準備ができていると決定されるまで延期される。レイは、このようなレイがシーンジオメトリの異なる部分に対しテストされることを可能にする複数のコレクションへ同時に収集可能である（すなわち、レイはトラバースの順序にテストされなくてもよい）。]
[0095] 上述されているように、ＩＴＵは、レイ入力から前に受信されたレイを表す情報をメモリに格納する。ＩＴＵは、これらのレイに対し、各レイと複数のコレクションのうちの１若しくはそれ以上のレイコレクションとの関連性を維持する。ＩＴＵは、メモリに格納された複数のコレクションに関するコレクションフルネスの指標をさらに維持する。これらの指標は、フルコレクションを指定するそれぞれのフラグであること、または、所定のコレクションと関連付けられたある程度の数のレイを表現する数字であることができる。実施のさらなる詳細および他の実施例と、テストアルゴリズムの実施に関係した変形とは、前述の参照された関連出願に記載され、ここで文字通りに提示されている情報がそれらの排他的な取り扱いでないことを明らかにしている。]
[0096] ここまでの開示内容から明らかであるように、レイは、レイのコレクションの中に設けられた情報に基づいてメモリからロード（またはメモリの中でアクセス）される。したがって、このようなローディングは、各レイを表すデータが格納されるそれぞれのメモリロケーションを決定することを含むことができる。このようなデータはそのレイコレクションの中に含まれることができ、たとえば、レイコレクションは、それらのレイのためのレイデータがそのコレクションの中で格納されているメモリロケーション、または、格納場所への他の参照情報のリストを含むことができる。例えば、レイコレクションは、メモリ、例えば、メモリ３４０、または、メモリのバンク（例えば、バンク５１０）におけるロケーションへの参照情報を含むことができ、または、他の実施では、これらの参照情報は、絶対値、ベースからのオフセット、または、このようなデータを参照するための別の適当な方式であることができる。しかし、いくつかの実施では、レイ・コレクション・データおよびレイデータが、例えば、内容連想データベースとして維持されることが可能であるので。その分離は、それほど明示的または明白であることは必要でなく、コレクションとレイとの間の関連性、および、コレクションとＧＡＤの要素との間の関連性が維持され、テストのためコレクションと関連付けられたレイ、および、同様にコレクションと関連付けられたＧＡＤの要素を特定するため使用される。]
[0097] 同様に、プリミティブまたはＧＡＤ要素のいずれかがテストサイクルの中を循環させられているので、レイデータがテストセルの中で「静止」しているということは明白である。関連出願に記載されているように、他の実施が可能であるが、これらの開示内容の主な焦点は、ローカライズされるか、または、そうでなければ、セルに関して静止するようにレイを準備し、その間に、ジオメトリがフェッチされテストされることである。]
[0098] このような実施の態様は図６に関連して提案される。特に、交差テストロジックの別の実施は、メモリインターフェイス６２５に連結するフェッチユニット６２０を含む（図２のテストロジック２０３に類似した）テスト制御ロジック６０３と、命令キャッシュ６３０と、命令デコーダ６４５と、データキャッシュ６５０とを含むプロセッサ６０５を含むことが可能である。データキャッシュ６５０はテストセル６１０ａ〜６１０ｎにデータを入力する。命令デコーダ６４５は、入力をテストセル６１０ａ〜６１０ｎへさらに提供する。命令ジェネレータ６６５は、命令入力を命令デコーダ６４５へ提供する。テストセルは検出された交差の指標をライトバックユニット６６０へ出力し、ライトバックユニットは次にデータをデータキャッシュ６５０に格納可能である。ライトバックユニット６６からの出力は、命令を生成するとき命令ジェネレータ６６５への入力としても使用される。このようなプロセッサ６０５で使用される命令は単一データ複数命令の系統でもよく、テストセルの中で処理される命令が定義された面（たとえば、プリミティブおよびＧＡＤ要素）とレイとの間の交差テストであると考えられる。] 図２ 図６
[0099] 実施例では、「命令」は、プリミティブ、または、ＧＡＤの要素のような幾何学的形状を定義するデータを含むことができ、複数のデータ要素は、「命令」として提供された幾何学的形状に対するテストを行う別個のレイの参照情報を含むことができる。したがって、幾何学的形状と複数のレイ参照情報との組み合わせは、複数の図示されたテストセルに分散可能である別々の情報のパケットであると考えられる。いくつかの場合に、パケット分散は順次に進行することが可能であり、その結果、複数のパケットが複数のテストセルの間で「衝突」する。]
[0100] このようなテストセルは、大規模命令セットをもつフル機能プロセッサとの関連で存在することが可能であり、各パケットは、その場合、パケットの目的を識別するために十分な他の情報を含むことができる。例えば、交差テストのため作成されたパケットを他の演算が実行されるための他の目的のため存在するパケットと区別するためにある程度の数のビットが含まれることが可能である。同様に、種々の交差テスト命令が、異なるプリミティブ形状および異なるＧＡＤ要素形状と、さらに、必要に応じて、異なるテストアルゴリズムとを含む目的のため、提供されることができる。]
[0101] 典型的な実施例では、各交差テストパケットは、最初に、ＧＡＤの要素またはプリミティブへの参照情報のいずれかであるジオメトリ要素への参照情報またはジオメトリ要素のためのデータと、ジオメトリ要素との交差に関してテストされるある程度の数のレイへの参照情報（すなわち、前述の「パケット」）とを収容することが可能である。]
[0102] デコーダ６４５は、ジオメトリ要素への参照情報を決定するため命令を解釈し、フェッチ６２０（メモリインターフェイス６２５のようなメモリインターフェイスのための制御）を介して要素のフェッチを開始できる。いくつかの実施では、デコーダ６４５は、将来に必要とされるジオメトリ要素のフェッチを開始するためにある程度の数の命令に備えることができる。ジオメトリ要素はフェッチ６２０によってデコーダ６４５へ提供でき、デコーダ６４５はジオメトリ要素をテストセル６１０ａ〜６１０ｎへ提供する。]
[0103] デコーダ６４５は、関数アドレスとして命令からのレイ参照情報をデータキャッシュ６５０へさらに提供し、データキャッシュは、各レイの交差テストのため十分なそれぞれのデータをテストセル６１０ａ〜６１０ｎのそれぞれに提供する。交差テストのため必要とされないレイと関連付けられたデータは提供される必要がない。したがって、データキャッシュ６５０は、交差セルテストとして動作する１若しくはそれ以上のコンピューティング資源のためのローカライズされたレイデータ記憶設備としての役割を果たすことができる。]
[0104] ジオメトリ要素は、各テストセル６１０ａ〜６１０ｎにおいてそれぞれのレイとの交差に関してテストされ、交差の指標がライトバック６６０による受信のため各テストセル６１０ａ〜６１０ｎから出力される。テストされるジオメトリ要素の性質に依存して、ライトバック６６０は、２つの異なる機能のうちの一方を実行する。テストセル６１０ａ〜６１０ｎが交差に関してプリミティブをテストしている場合、ライトバック６６０はテストされているプリミティブと交差した各レイの指標を出力する。テストセル６１０ａ〜６１０ｎがＧＡＤの要素をテストしている場合、ライトバックはテストセル６１０ａ〜６１０ｎの出力を命令ユニット６６５へ提供する。]
[0105] 命令ユニット６６５は、さらなる交差テスト中にテストセルに指令することになる将来の命令を組み立てるため動作する。命令ユニット６６５は、以下の通り、ＧＡＤの所定の要素と交差したレイを指定するテストセル６１０ａ〜６１０ｎの入力と、命令キャッシュ６３０と、ＧＡＤ入力６７０からの入力を使って動作する。テストセル６１０ａ〜６１０ｎからの入力を使って、命令ユニット６６５は、ＧＡＤ入力に基づいて、テストセル６１０ａ〜６１０ｎからの入力の中で指定されたＧＡＤの要素に接続されたＧＡＤの要素を決定する（すなわち、命令ユニット６６５は、所定のＧＡＤ要素に対して指示された交差に基づいて次にテストされるべき要素を決定する）。]
[0106] 命令ユニット６６５は、命令キャッシュ６３０に格納された命令が交差した要素に接続しているとして特定されたＧＡＤの要素毎に既に存在するかどうかと、命令がさらなるレイ参照情報を許容するかどうか（すなわち、命令のすべてのデータスロットが満たされているか？）と、を決定する。命令ユニット６６５は、テストセル入力の中で交差しているとして特定されたレイと同数をその命令に加え、残りのレイ参照情報を受信するため十分な他の命令を作成する。命令ユニット６６５は、テストセル入力の中で特定された要素と接続しているとして特定されたＧＡＤの要素毎にこれを実行する。このように、テストセル入力（交差指標）を処理した後、同じＧＡＤ要素と交差しているとして特定されたレイはそれぞれがその同じＧＡＤ要素に接続されたＧＡＤの要素に対するレイのテストを指定する命令に加えられる。このようにして作成された命令は命令キャッシュ６３０に格納されることができる。]
[0107] 命令は、ＧＡＤ入力６７０から受信されたＧＡＤの要素の編成に基づいて命令キャッシュ６３０の中に編成されることができる。命令ユニット６６５は、ロジック２０３ａおよび命令ユニット６６５の両方がどのレイがどの要素にヒットしたかの指標を受信し、このようなレイを将来のテストのためグルーピングするので、ロジック２０３ａと類似した機能を実行する。図６のシステムは、テストされるレイのパケットが異なる機能を達成する複数のタイプのうちのある種のパケットであることが可能であるので、より汎用的であることが意図されている。] 図６
[0108] 例えば、ＧＡＤ入力６７０はＧＡＤのグラフを提供することができ、グラフのノードはＧＡＤの要素を表現し、ノードのペアはエッジによって接続されている。エッジは、どのノードが他のどのノードに接続されているかを特定し、命令ユニット６６５は、ＧＡＤの所定の要素のためキャッシュの中に既に存在する命令と、新しいレイが追加される場所とを特定するために、ノードを接続するエッジを辿ることにより命令キャッシュ６３０を探索する。複数の命令が所定のＧＡＤ要素に対し存在する場合、複数の命令はリストの中でリンクされるか、または、そうでなければ、順序付けられるか、若しくは、互いに関連付けられることができる。関連した命令が見出されることがある命令キャッシュ６３０の中の潜在的なロケーションを特定するためのＧＡＤ要素ＩＤのハッシングのようなその他の方法が同様に実施できる。]
[0109] 命令は、（接続された各ノードのための命令を格納するのに反して）発行され復号化された命令に応答して、命令がＧＡＤの接続されたノードのフェッチを引き起こすように、テスト中のＧＡＤのノードをさらに参照できる。このような接続された要素のそれぞれは、各テストセルの中に維持されているそれぞれのレイとのテストのためテストセル６１０ａ〜６１０ｎの中へストリーム可能である（すなわち、レイデータは、複数のＧＡＤ要素がそれぞれのテストセルに提供され、各テストセルがそのレイを各ＧＡＤ要素と順々にテストする間、テストセルの中で静止し続ける）。]
[0110] よって、これらの実施例にしたがって実施されたプロセッサは、接続されたノードに対する交差テストのための第１のノードとの交差に関して特定されたレイを収集する命令を取得するか、そうでなければ作成するために機能を提供することになる。上述された実施例と同様に、プロセッサ６０５に提供されたＧＡＤが階層的である場合、ＧＡＤのグラフは階層的な順序でトラバースされることがある。]
[0111] ＧＡＤの例示的な接続および供給源は典型的であり、他の配置も考えられる。例えば、メモリ６１５は、ＧＡＤ要素の供給源であるかもしれないが、好ましくは、所定の処理アーキテクチャが許可する場合、ジオメトリデータではなく、レイ（すなわち、レイを定義するデータ、および、見出された現在の最近傍プリミティブ交差のような他のデータ）を高速メモリに格納し続ける。同様に、上記実施例では、テスト結果に基づいてテストされるべき次のノード（すなわち、次のアクセラレイション要素、またはプリミティブ）が決定され、パケットが幾何学的形状毎にそれぞれにインスタンス化された。上記開示内容から明らかである他の実施は、所定のノードの子のテストを開始することを決定し次第に、「子」ノード毎にパケットをインスタンス化することを含むことができ、後の時点で子命令／コレクションを作成する。]
[0112] 図７は、交差テストと、カメラレイといった新しいレイの生成を含むレイシェーディングとの動作を分離するためキューを使用できるレイトレーシング・システム（例えば、システム７００）の態様をさらに図示する。システム７００は、交差テストのためのレイのサブミッションと、交差テストの完了とを可能にさせ、図１〜６のシステムと同様に、異なる順序でシェーディングのための出力を生じる。同様に、交差テスト資源は、前に特定された交差のシェーディング解決のため停滞することなく、レイの交差テストを進めることが可能である。] 図１ 図２ 図３ 図４ 図５ 図６ 図７
[0113] 図７は、交差に関してテストされるべきレイを定義するデータを交差テスト資源に格納するレイデータ記憶装置７６６ａ〜７６６ｎにそれぞれが連結された複数の交差テスト資源（ＩＴＲ）７０５ａ〜７０５ｎを図示する。ＩＴＲの各グループおよびレイデータ記憶装置（例えば、レイデータ７６６およびＩＴＲ７０５ａ）は、テスト資源およびレイデータ記憶装置のローカライズされたグルーピング、例えば、前のグルーピング、例えば、図５のグルーピング５７８および５７９に類似している図示されたグルーピング７０４と見なすことができる。] 図５ 図７
[0114] レイデータ記憶装置７６６ａ〜７６６ｎは、プライベートＬ１キャッシュ、Ｌ２の共有部分またはマップ部分などのようなメモリであることが可能である。上述の実施例では、高速メモリを幾何学的データではなく、特定の処理資源にローカルであるレイデータの格納に当てるのが好ましい。レイデータのローカライズされた格納は、ここで使用される交差テストアルゴリズムによって簡単化され、レイがローカライズされた高速メモリに格納されることが可能である期間を増大させ、この小規模メモリのスラッシングの量を削減する。したがって、このレイ格納は、所定のレイのためのデータがシーンの中の交差テストを完了するまで通常は同じローカルメモリに格納されるので、準静的であると見なすことができる。]
[0115] レイを定義するデータは、（上述の図におけるロジック２０３ｂなどに類似した）テスト制御７０３から出力７４３を介してロードされる。テスト制御７０３は、レイ終了キュー７３０を介して、ＩＴＲ７０ａ〜７０５ｎにおいて交差テストを終了したレイの識別子を含む入力を受信する。]
[0116] キュー７３０はレイ識別子を格納する（いくつかの例示的なレイＩＤ１、１８、１０および４８０が図示されている）。キュー７３０は、ＩＴＲ７０５ａ〜７０５ｎから、交差した最近傍交差を特定するためにテストされ、シーン内のテストを終了するレイを表現する入力を取得する。したがって、キュー７３０は、ＩＴＲ７０５ａ〜７０５ｎからの所定の出力がＧＡＤ要素の情報、または、最近傍と思われるプリミティブ交差（ＩＴＲ７０５ａ〜７０５ｎが両方のタイプの形状をテスト可能である場合に役立つ）を表現するかどうかを決定可能である決定ポイント７５１からデータ入力されることが可能である。]
[0117] 決定ポイント７５１は、したがって、上述された２種類の交差制御機能を表現する。一方の交差制御機能では、ＧＡＤ／レイ交差が交差テスタの近くで維持／管理され、もう一方では、最近傍の検出されたプリミティブ／レイ交差だけがシェーディングのため出力される。いくつかの上述のアーキテクチャにおいて、別個のテストセルがそれぞれに使用される場合、決定ポイントは、最近傍と思われるプリミティブ交差が見出されたときだけを追跡することができる。]
[0118] 決定ポイント７５１から、ＧＡＤ結果は、レイ制御７０３から提供され、そして、入力７４２から受信されたレイＩＤを格納するキュー７２５からレイＩＤ入力も受信するマルチプレクサ７５２に入る。レイ制御７０３は、テスト制御７０３から出力７４３を介してレイデータ７６６ａ〜７６６ｎに提供されているレイ情報に対応するレイ識別子と共に入力７４２を投入する。よって、（レイ識別子（レイＩＤ））によってキュー７２５の中で特定されたレイを定義するデータは、出力７４３を介して、レイデータ７６６ａ〜７６６ｎに提供され、これらのメモリに格納される。レイＩＤがどのように形成されるかについての実施例は後述される。]
[0119] 両方のキュー７３０および７２５は、レイの一連の識別子（レイＩＤ）を図示する。しかし、後述されるように、レイは、一般に、所定の幾何学的形状に対して並行にテストされる。よって、このような場合、キュー７２５は、好ましくは、レイＩＤのパケットのためのレイＩＤを格納することになるので、キュー７３０は、各エントリが所定の形状と関連付けられたある程度の数のレイＩＤを有する一連のエントリを表現できる。]
[0120] 特有の実施例として、このアーキテクチャを駆動するアルゴリズムは、ある程度の数のレイが所定の形状に対してテストされるべきであると決定されるまで一般に待機するので、多数のレイがほぼ同時にテストを終了し、そして、テストを開始すると一般に考えられる。有利な点として、これらの終了レイは、最初にインスタンス化された方法または時点に関して、または、これらの終了レイがどの経路を使ってアクセラレイション階層をトラバースしたかに関して、互いに完全に無関係にできる。逆に、キュー７２５は、シーンのデフォルトＧＡＤ要素、たとえば、ＧＡＤ要素の階層の中のルートノードに対してテストされるべき新しいレイのグループまたはパケットを収容すると考えることができる。]
[0121] このような新しいレイは、カメラシェーダ７３５および他のシェーダ７１０ａ〜７１０ｎを含む光線源に由来する。カメラシェーダ７３５は、シーンの中でテストされるべき１次レイを生成するので、別個に特定される。シェーダ７１０ａ〜７１０ｎは、例えば、スレッドの形でコンピューティング資源の上で、および／または、１若しくはそれ以上のプロセッサのコアの上で動き、レイとプリミティブとの間で特定された交差に適切な応答を指定する命令または他のロジックの実行を表現する。通常は、このような応答は、プリミティブと関連付けられたコードをシェードすることにより少なくとも部分的に決定され、様々な他の影響および考慮事項を明らかにすることができる。]
[0122] シェーダ７１０ａ〜７１０ｎは、テスト制御７０３の出力７４５からこのようなレイデータを受信する分散ポイント７７２を介して（図８ａを参照のこと）、交差したレイおよびプリミティブの識別子を受信する。分散ポイント７７２は、このようなレイデータを所定のプリミティブのためのコードを実行する利用可能性を有する計算資源へ提供するために使用できるので、このような利用可能性決定手段は、負荷測定、計算資源によってセットされるフラグ、フルネス指標を使うＦＩＦＯ分離、または、ラウンドロビン若しくは疑似ランダム分散スキームを含むこのような分散を制御するため使用可能である。] 図８ａ
[0123] これらのシェーダ７１０ａ〜７１０ｎの出力は、便宜上２次レイと呼ばれる他のレイを含むことが可能である（カメラ７３５からの出力もレイを含む）。本実施例では、このようなレイは、この時点で、レイを定義する始点および方向を少なくとも含むが、この時点で、好ましくは、テスト制御７０３によって提供されるレイＩＤが関連付けられている必要はない。]
[0124] 識別できるように、テスト制御７０３は、交差テスト資源におけるレイ状態を監視可能であり、図８〜９に関連してより詳細に記載されるように、新しいレイがレイデータ７６６ａ〜７６６ｎの中の終了したレイを置き換えることを可能にする。レイＩＤのＩＴＲ７０５ａ〜７０５ｎへの分散は、図１０に関して詳述されるディストリビュータ７８０によって実行される。このような分散は、レイデータ７６６ａ〜７６６ｎのメモリが所定の識別子によって特定されたレイを定義するデータを格納することによって主として制御される。同様に、ディストリビュータ７８０は、図１０に関してさらに後述されるように、コレクション準備完了のような考慮事項に基づいて、レイＩＤがキュー７２５から取得される時点を制御する。] 図１０
[0125] 今度は、図８ａを参照すると、レイデータ７６６ａ〜７６６ｎのそれぞれと関連付けられたメモリのバンクを含み、各バンクがレイデータで占められているスロットを有し、メモリアドレスによってアドレス指定可能である、テスト制御７０３の一部分が図示されている。図８ａは、レイ終了キュー７３０からの出力７４４がレイ識別子１、１８、１０６および４８０を含み、各識別子がメモリ８０３の中にスペースを割り付けられていることを図示している。このようなスペースは、出力７４４からのこれらのレイ識別子の受信に応答して上書き／記入されることが許可される。分散ポイント７２２への出力７４５は、シェーディングの際に用いられるレイデータを含む。出力７４５は他のデータをさらに含むことができる。実際には、メモリ８０３は、シェーダ７１０ａ〜７１０ｎを実行するプロセスのような他のプロセスによっても使用されるメモリで実施されることができる。このような場合、出力７４５は、計算資源によるメモリ８０３からのこのようなデータの取り出しを表現可能である（または、取り出しによって実施可能である）。] 図８ａ
[0126] リンク７４１、７４２、７４３、７４４、７４５、７５０、７９０のような種々の通信リンクは図７において特定され、これらのリンクのうちのいずれかが全体的なアーキテクチャ実施に従って実施可能であり、共有メモリ領域、物理リンク、拡張バスの上に確立された仮想チャネル、共有レジスタスペースなどを含むことが可能である。] 図７
[0127] 図８ｂは、新しいデータのためのデータは、（例えば、カメラシェーダ７３５のようなシェーディング動作からの）出力７４１から到来する。このようなレイデータは、レイ始点および方向情報を少なくとも含む。次に、テスト制御７０３は、これらの新しいレイをメモリ８０３の中で様々なレイデータ７６６ａ〜７６６ｎのためのロケーションに割り当てる。各レイ始点および方向と関連付けられた識別子は、それぞれが格納された場所に依存する。よって、入力７４２（キュー７２５に関する入力）はそれに基づいて決定されたレイ識別子を受信する。同様に、出力７４３は、レイ識別子と、それらと関連付けられ、メモリ８０３に格納された始点および方向情報との両方を含む。レイＩＤは関連データを特定するためメモリをインデックス付けするため使用できるが、ＩＴＲ７０５ａ〜７０５ｎおよびメモリ８０３の中のレイデータの特定がレイ識別データを使用して実行できる限り、レイのための他の種類の識別子も使用できるので、図８ａおよび８ｂに図示されたレイＩＤの割り当ては便宜的である。] 図８ａ 図８ｂ
[0128] 図９ａは、内容連想メモリ９１０がそれぞれ異なるレイデータと関連付けられているキー９０５を維持するこのような代替案の実施例を図示する。] 図９ａ
[0129] 図９ｂは、各レイデータ７６６ａ〜７６６ｎの内部において、スロットがテスト制御７０３からインターフェイス７４３を介してレイデータを受け入れるため設けられていることを図示する。これらのスロットは、複数のバンクにさらに細分すること、または、インターリーブ化することが可能であり、および／または、キャッシュからのデータのより簡単な取り出しを可能にする他のキャッシュ編成メカニズムであることが可能である。レイは、ここでは、格納のため分散されることが必要であり、このような分散は、レイＩＤの最下位ビット、若しくは、レイＩＤのハッシュに基づいて、または、分散が行われるバンクの数によるモジュロ除算を用いて、ラウンド・ロビン・キューイングを用いて、もしくは、レイデータをメモリへ分散するため使用できる他の分散メカニズムを用いて進むことができる。所定の部分の範囲内で、レイデータはレイＩＤに基づいてソートされることも可能である。] 図９ｂ
[0130] 要約すると、図７〜９ｂは、テストされるべきレイが制御ロジックによって収集され、好ましくは、レイ定義データが異なる交差テスト資源に連結されたそれぞれのキャッシュに格納されるメモリロケーションに基づいている識別子が割り当てられるアーキテクチャを図示する。プリミティブ交差テスト結果は、テストが終了したときにこれらのテスト資源から到来し、テスト制御ロジックは、その後に、これらの終了したレイのメモリロケーションをテストされることを必要とする新しいレイに再割り当て可能である。終了したレイは、テストされるべきさらなるレイを生成可能である複数の異なる交差処理／シェーディング資源のいずれかで共用可能である。レイは、一般に、アクセラレイション構造のトラバースの間中、かつ、最近傍プリミティブ交差が特定されるまで（または、レイがシーン背景以外と交差しないことが決定されるまで）交差テスト資源の中を循環させられる。] 図７ 図８ａ 図８ｂ 図９ａ 図９ｂ
[0131] 図１０を参照すると、レンダリングシステムのさらなるアーキテクチャ態様が図示されている。図１０における一態様は、レイデータが交差テストのため構成されたプロセッサに連結されたそれぞれのキャッシュメモリに格納できることである。別の態様は、ディストリビュータ７８０がＩＴＲ７０５ａ〜７０５ｎとインターフェイスをとることができる方法である。図示されているさらなる態様は、テスト用の形状データが交差テスタへ提供できる方法である。] 図１０
[0132] ディストリビュータ７８０は、（ハードウェア、プロセス間またはスレッド間通信などとして実施された）通信リンク７９０を介してマルチプレクサ７５２（図７）からレイ識別子を受信する。これらのレイＩＤのそれぞれは、レイＩＤと、次にテストされるべきそれぞれのＧＡＤ要素バウンディング物体との間の関連性が維持されているコレクション・マネージメント１０７５へ送信される。レイＩＤは、決定１０１３、１０１４および１０１５によって、レイＩＤがそれらのコレクションをテストするためコレクション・マネージメントおよび記憶装置１０７５からの決定を待つ場所であるキュー１０２１、１０２２、および１０２３の間にさらに分散されることが可能である。例えば、コレクション１０４５は、テストする準備が整っていると決定され、レイＩＤは、キャッシュ１０６５ａ〜１０６５ｎがこのようなレイＩＤのそれぞれのためのデータを収容しているそれぞれのＩＴＲ７０５ａ〜７０５ｎへ送出される。コレクション・マネージメント１０７５は、テストのため必要とされる幾何学的形状の取り出しを開始するため、ＧＡＤ要素データおよび／またはプリミティブデータを格納するメモリへのインターフェイスを有することもできる。] 図７
[0133] これらの形状は、（例えば）リンク１１２を介して記憶装置１０３（図１）からキュー１０４０に達する。これらの形状は、所定のコレクションと関連付けられたＧＡＤの要素との関連性に基づいて特定されている。例えば、階層ＧＡＤの場合、これらの形状は、親ＧＡＤ要素の子であることが可能である。各ＩＴＲは、キュー１０４０からの形状に対してそれぞれのレイを順次にテスト可能である。よって、所定のコレクションのレイがキャッシュ１０６５ａ〜１０６５ｎの間に均等に分散しているとき、最高スループットが実現され、コレクション・マネージメント１０７５は、所定のレイコレクションをテストした結果に基づいて最も簡単にコレクションを更新できる。所定のコレクションの中の複数のレイが１つのキャッシュにあるとき、他の交差テスタはストールすることが可能であるか、または、次のコレクションからのレイをテストすることが可能である。コレクションテスト同期が再び必要とされる前に、順序が乱れているテストの最大数が受け入れられる。] 図１
[0134] 出力は、出力７５０ａ〜７５０ｎ（リンク７５０（図７）のコンポーネントであることが可能である）で生成され、決定ポイント７５１（図７）に提供される。上述の通り、このアーキテクチャは、どのような形状でも（すなわち、プリミティブまたはＧＡＤ要素のいずれかを）テストするＩＴＲを提供する。さらに、コレクション・マネージメント１０７５と連結された決定ポイント７５１は、ＧＡＤ交差テストの結果が、所定のレイが所定のＧＡＤ要素にヒットする決定を含むことを表し、特定されたレイをそのＧＡＤ要素に対応するコレクションに追加させる。よって、別の実施は、ＧＡＤテスト結果をコレクション・マネージメント１０７５へ直接的に提供することを含むことができる。より一般的には、上記実施例は、潜在的な情報のフローを例示し、他のフローがそこから明白である。] 図７
[0135] 注意すべき他の態様は、所定のレイコレクションの１若しくはそれ以上のレイＩＤがキュー１０２１、１０２２、１０２３（コレクション１０４７によって示されている）のいずれかに格納できることである。このような場合、そのキューのためのＩＴＲは両方のレイをテスト可能であり、利用可能になるとき２回目のテスト（または、多数の後続のテスト）の結果を出力する。決定ポイント７５１は、組み立てられるべきコレクションのすべての結果を待つことができ、または、「散在する」結果が利用できる限りで伝搬させられる。]
[0136] 要約すると、図１０は、１若しくはそれ以上の形状と関連付けられたレイ識別子のパケットが複数のテスト資源のためのキューに分散されることを可能にさせ、各キューがレイデータのサブセットを格納するシステム編成を図示する。各テスト資源は、テスト資源にロードされた形状に対して各レイ識別子によって特定されたレイデータをフェッチする。好ましくは、形状は並行してすべてのテスト資源の中で順次にストリーム化可能である。形状は、主メモリの中のアドレスから始まる一連の子として特定することができる。よって、図１０は、形状が一般に複数のレイに対して並行してテストされるシステム編成を図示する。] 図１０
[0137] しかし、他の実施例は一連の異なる交差テスト資源の中の形状を順次にテストし、形状データおよびレイ識別子のパケットが交差テスト資源の間を進む。複数のパケットを進行させることにより、テストのスループットが増加する。本アプローチによる実施例は後述される。]
[0138] 図１１は、複数の計算資源１１０４〜１１０８のリングバス配置が実施可能であるコンピュータアーキテクチャの第１の実施例を図示する。各計算資源は、交差テストのため使用される計算資源のため、メモリ３４０の中の形状データ記憶装置１１１５からそのコンピューティング資源へ提供された幾何学的形状と交差テストされるべきレイデータを収容するプライベートＬ１キャッシュ１１２５ａ〜１１２５ｎにアクセス可能である。計算資源１１０４〜１１０８の間の通信は、複数のポイント・ツー・ポイント、または、このようなプロセッサ間通信のため利用可能である他のアーキテクチャを含むことができるバス１１０６によって行うことが可能である。] 図１１
[0139] 計算資源がＬ２キャッシュ１１３０および１１３５のようなある一定のメモリ構造を共有する場合、これらの計算資源、例えば、Ｌ２キャッシュ１１３０を共有する計算資源１１０７および１１０６の間の通信は、ある目的のためそのキャッシュを介して互いに通信することができる。付加的に、システムの中でテストされているレイのためのデータのコピーは、レイデータ１１０１ａ〜１１１０ｎの間でのデータのサブセットの分散のため、レイデータ１１１０に維持されることができ、（後述されるように）これらのＬ２キャッシュに格納されることもできる。形状データ１１１５は、メモリ３４０に存在することもでき、Ｌ２ １１３０、１１３５のうちの１若しくはそれ以上と、キャッシュ１１２５ａ〜１１２５ｎのうちのいずれかに一時的に存在することもできる。しかし、このようなキャッシュに格納されたレイデータは、このような形状データによって上書きされることから保護され、このような形状のため割り付けられたスペースの大きさは、一般に、テストにおいて次に使用される時点についての指標がない場合に形状データを周りに維持しようとすることなく、形状データ１１１５へのレイテンシを遮断するため足りるように、テストの準備ができているとして現在特定されているパケットのために使える大きさに制限される。換言すると、レイデータのため、最大未使用置換のような、典型的なキャッシュ・マネージメント・アルゴリズムの使用を回避することが好ましい。]
[0140] 図１１は、アプリケーションおよび／またはドライバ１１２０が交差テストに加えて計算資源１１０４上で実行可能であることをさらに図示する。同様に、レイプロセス１１２１は計算資源１１０８上で実行可能であり、パケットデータ１１１６はパケットプロセス１１２１によって用いるためキャッシュ１１２５ａに格納可能である。他のパケットデータはＬ２ １１２９に格納可能であるが、レイデータと同様に、パケットデータを最高速であると考えられるメモリに格納することが好ましい。パケットプロセスは、コレクションおよび他のマネージメントロジックが上述の図面において実行した同じ機能のうちの大半を実行し、すなわち、どのレイがどのＧＡＤ要素と交差したかを記録し、そして、例えば、交差したＧＡＤ要素の子に対してテストされる準備ができている十分なレイを有することによって、例えば、テストの準備ができているＧＡＤ要素を選択する。] 図１１
[0141] 本実施例では、パケットプロセス１１２１は集中化されているので、複数のレイ識別子と、特定されたレイとの交差に関してテストされるべき（複数の）形状への参照情報または複数の形状のデータのいずれかと、を収容するパケットを発行することにより、動作することになる。交差テストを実行する各計算資源１１０４〜１１０７はパケットを受信する。例えば、複数のポイント・ツー・ポイント・リンクにおいて順番に（さらに後述される）、または、共有バス型の媒体においてほぼ同時に（図１０のアーキテクチャに類似することが可能である）。各計算資源１１０４〜１１０７は、それぞれのローカライズされたレイデータ１１１０ａ〜１１１０ｎがパケットの中で特定されたレイに関するデータを格納するかどうかを決定し、格納する場合、そのレイに関するデータを取り出し、テストし、結果を出力する。] 図１０
[0142] ＧＡＤ要素交差の結果はパケットプロセス１１２１によって追跡されるので、このような結果をパケットプロセス１１２１へ戻す通信メカニズムが許容できる。このようなメカニズムは、システムの全体的なアーキテクチャに基づいて選択できる。いくつかの例示的なアプローチは後述され、見出された交差毎に別個の指標を含むことができるか、または、各テスト資源が循環するパケットに交差結果を投入することを可能にする。]
[0143] 図１２は、レイデータ１２６６ａ〜１２６６ｎおよびパケットデータ１２１６ａ〜１２１６ｎをそれぞれ格納するキャッシュ１２８１〜１２８４が付随した計算資源１２０５〜１２０８の編成のさらなる実施例を図示する。各計算資源１２０５〜１２０８は、キュー１２５１〜１２５４によって少なくとも１つの他の計算資源に接続される。レイプロセス１２１０は、キュー１２５０を介して計算資源１２０５へ入力を提供する。レイプロセス１２１０はアプリケーション／ドライバ１２０２と通信する。計算資源１２０８からの出力１２５５はレイプロセス１２１０と通信する。別の出力１２５６は計算資源１２０５と通信する。プリミティブおよびＧＡＤ記憶装置１０３は、計算資源１２０５〜１２０８のためその形状データへのリードアクセスを提供する。] 図１２
[0144] レイプロセス１２１０は、テストのためのレイを受信または作成し、特定されたレイのレイ識別子およびレイデータを収容するパケットを形成する。パケットは、キュー１２５０〜１２５４を介して計算資源１２０５〜１２０８のそれぞれへ伝えられる。各計算資源１２０５〜１２０８は、所定のパケットの中のレイの一部分、いくつかの実施例では、１つのレイを要し、レイのその部分を計算資源のレイデータ１２６６ａ〜１２６６ｎの中に格納する。他の実施例は、特有の計算資源１２０５〜１２０８へ向けられたパケットを送信することを含むことができ、レイプロセス１２１０はどのレイデータがどのローカライズされたレイデータ１２６６ａ〜１２６６ｎに格納されるかを決定することになる。]
[0145] レイがローカライズされた記憶装置にロードされた後、レイは、次に、始点および方向データをもたずに、レイＩＤだけを収容するパケットによって特定される。このようなパケットは、そのパケットの中で特定されたレイに対してテストされるべき形状への参照情報または形状のデータのいずれかをさらに収容する。いくつかの実施例では、このようなパケットを形成するデータは、計算資源１２０５〜１２０８のローカライズされたメモリ１２８１〜１２８４の間に分散される。よって、計算資源１２０５〜１２０８のそれぞれは、どのレイがどの形状に対して次にテストされるべきかに関する情報が分散されるように、所定の時刻にシステムの中でテストされているレイのためのパケットデータの一部分を維持する。かくして、各計算資源１２０５〜１２０８は、テストの準備ができているコレクションのテストを開始するため、レイＩＤおよび形状情報のパケットを発行可能である。]
[0146] 各パケットは、キューおよび計算資源を一周し、次に、パケットの中に投入された交差テストの結果と共に発信元の計算資源へ返送される。一実施では、各計算資源１２０５〜１２０８は、各計算資源が発行するパケットのための形状データをフェッチする。例えば、計算資源１２０５は、テストのための準備が整ったパケット（たとえば、所定のＧＡＤ要素のためのレイのコレクション）を有し、次に、計算資源は、このような関連性（例えば、ＧＡＤ要素の子）によってテストされるべき形状をフェッチし、各形状のためのデータを有するパケットを作り、キュー１２５１から各パケットを送出することが可能である。]
[0147] 順番に、計算資源１２０５は、パケットが他の計算資源の中を移動した後、この計算資源が送出した各パケットを受信する。受信されたとき、各パケットは、他の計算資源１２０６〜１２０８に格納された／格納されるパケットの中の特定されたレイとの交差に関してそのパケットの中の形状をテストした結果（参照情報または定義データ）が投入される。計算資源１２０５は、他の計算資源がそれぞれのテストを実行する前または後のいずれかに、計算資源がレイデータ１２６６ａの中にローカルに保有しているいずれかの特定されたレイをテスト可能である。よって、レイ定義データは、交差テスト資源に連結された複数の高速メモリの間に分散させることができ、テスト結果は分散された方式で収集可能である。]
[0148] 図１２に従ってアーキテクチャを実施することは、使用されている物理的なシステムの種々の特性を考慮に入れることができる。例えば、キューは、パケットを一方向へ送信するものとして表されている。しかし、利益はパケットを両方向へ送信することによって実現されることができる（双方向キューまたは複数のキュー）。同様に、図１２は、パケットデータが計算資源の間に分散され、より多くのＬ２キャッシュへのより分散したメモリアクセスと、潜在的に主メモリ１０３のようなより大規模なメモリへの他のポートのアクセスとを可能にすることを図示する。] 図１２
[0149] パケットが集中化される場合、データ参照情報と共に一方向に送信されたパケットは、例えば、計算資源１２０５によってフェッチされたデータを有することができ、データ参照情報と共にもう一方の方向へ送信されたパケットは、計算資源１２０８によってフェッチされたデータを有することができる。この状況は、このようなリングバス・アーキテクチャ（一方向または双方向）にエントリポイントを設けるため一般化が可能である。]
[0150] 開示内容から明白であるように、上記キューは、交差テストのための新しいレイを複数の交差テスト資源を含むシステムに導入するための１若しくはそれ以上のキューと、交差テスト資源を互いに相互接続するキューとを含むことができる。いくつかの場合に、新しいレイを導入するキューはレイ定義データを収容可能である（例えば、交差テスト資源に接続されたキャッシュにデータを格納するのを待機するキュー）。このようなキューは、レイ定義データを格納する主メモリの中にリストとして実施可能である。パケットを伝える交差テスト資源を相互接続するキューは、好ましくは、レイ識別子だけを含み、レイ定義データを含まないことができる。]
[0151] 図１３は、計算資源１２０５が一方のコアであり、計算資源１２０６が別のコアであるように、計算資源がチップのコアを用いて実施されることができ、そして、キュー１２５１がコア間通信であるシステム１２００の潜在的な実施の一部分を図示する。同様に図示するのは、レイデータを形状データと共に格納可能である中間Ｌ２キャッシュ１３０５である。前述の図に関して説明されているように、Ｌ２キャッシュ１３０５は、シーンジオメトリおよびアクセラレイションデータのいくつかの部分を格納することができ、このようなデータを格納する限りは、レイデータのスラッシュ化の増加はない（すなわち、レイデータは、好ましくは、キャッシュ格納において優先される）。] 図１３
[0152] 図１４ａ〜１４ｃは、それぞれが、例示的なシステムの種々の実施によるキューが取ることができる種々の関係を図示する。一般に、計算資源間の通信は、直列または１：１であることが必要とされない。例えば、図１４ａは、１入力１４０４が、１つの計算１４０７および１４０８にそれぞれに専用である両方のキュー１４０５および１４０６にデータ入力可能であることを図示する。例えば、計算１４０７および１４０８が単一の物理的なチップで実施される場合、入力１４０４はチップレベル入力であることが可能であり、各キュー１４０５、１４０６は特有のコアのため使われることが可能である。] 図１４ａ 図１４ｂ 図１４ｃ
[0153] 図１４ｂは、単一入力が複数のコアにデータ入力可能であり、複数のコアのそれぞれが計算１４０７、１４０８にデータ入力可能であり、計算のそれぞれが同様にデータを反対側のキュー１４０６、１４０５へそれぞれに送信可能であることを図示する。図１４ｃは、キュー１４１１が入力１４１０を受信可能であり、出力を両方の計算１４０７および１４０８へ提供可能であることを図示する。よって、図１４ａ〜１４ｃは、種々のキューイング戦略がこれらの態様に従ってパケットを伝達するため実施可能であることを図示する。] 図１４ａ 図１４ｂ 図１４ｃ
[0154] 図１５は、複数のキャッシュ階層のレベルが存在すること（例えば、レベル１のキャッシュ１５０２および１５０３と、レベル２のキャッシュ１５０４と、レイデータの種々の組み合わせを設けることができること）を図示する。例えば、レイデータ１５０７は、レイデータ１５０５と１５０６との互いに素な部分集合と、１５０５または１５０６のいずれにも存在しないレイデータとを含むことが可能である。レイデータ１５０５および１５０６は、動的に変化することが可能であり、例えば、一方のキューが１若しくはそれ以上の計算資源（図１４ｃ）にデータ入力する場合、レイデータは、いずれかのレイデータ１５０５または１５０６へのレイデータ１５０７に格納されたレイの動的な割り当てを反映することができる。] 図１４ｃ 図１５

权利要求:

請求項1
３次元シーン内のレイを交差テストするシステムであって、各交差テスタが複数のレイを定義するレイ定義データのマスターコピーのそれぞれのサブセットを格納するためそれぞれのキャッシュメモリへのアクセス権を有する複数の交差テスタと、前記交差テスタの前記キャッシュメモリに格納された定義データによって定義された前記レイの少なくとも一部のそれぞれの識別子へのアクセス権を有し、複数のレイ識別子を、特定されたレイを使って交差テストされるべき前記３次元シーン内に位置している１若しくはそれ以上の形状を表す形状情報と関連付けることと、関連性を表すデータを前記複数の交差テスタで利用できるようにさせることと、によってレイ交差テストを制御するため動作可能であり、前記交差テスタのそれぞれが指示された１若しくはそれ以上の形状との交差に関して、交差テスタのキャッシュがレイ定義データを格納している特定されたレイをテストするため動作可能である、制御ロジックと、前記交差テスタから出力を受信するため連結され、出力が前記交差テストの結果を表すデータを含む出力バッファと、を含む、システム。
請求項2
請求項１記載のシステムにおいて、このシステムは、さらに、前記交差テスタからの出力によって特定され、前記出力バッファから取り出し可能であるプリミティブと関連付けられたシェーダ・コード・ルーチンを実行する複数の計算資源を含むものである。
請求項3
請求項２記載のシステムにおいて、前記シェーダ・コード・ルーチンの実行は交差テストされるべき新しいレイを生成するものであり、前記新しいレイを受け取るため前記複数の交差テスタへの入力キューをさらに含むものであり、前記制御ロジックは、他のレイが交差テストを終了したとき、前記新しいレイの交差テスタを開始するため動作可能であるものである。
請求項4
請求項１〜３のいずれか１つに記載のシステムにおいて、各交差テスタは、定義データにレイ識別子が設けられているか、または、メモリ参照情報が設けられている１若しくはそれ以上の形状との交差に関して特定されたレイをテストすることにより、それぞれのメモリに格納されたレイに対する識別子の受信に応答するように構成されているものである。
請求項5
請求項１〜４のいずれか１つに記載のシステムにおいて、前記交差テストは、レイと、ｋＤツリー、軸方向整列バウンディングボックス、および、球体の１若しくはそれ以上のカッティングプレーンから選択されたアクセラレイション構造要素を含む幾何学的形状との間で行われるものである。
請求項6
請求項１〜５のいずれか１つに記載のシステムにおいて、前記交差テスタは、前記交差テスタの間で、前記複数のレイ識別子とこれらの特定されたレイと交差テストされるべき前記１若しくはそれ以上の形状を表す前記形状情報との間の関連性を表すデータを順次に送り、前記データを前記交差テスタのすべてで利用できるようにするため構成されているものである。
請求項7
請求項６記載のシステムにおいて、各交差テスタがレイとの交差をテスト可能である前記形状は、ジオメトリ・アクセラレイション要素およびプリミティブを含むものであり、各交差テスタは、さらに、ジオメトリ・アクセラレイション要素との交差に関するレイのテストの結果を前記関連性を表す前記データと共に送り、プリミティブとの交差に関するレイのテストの結果を前記交差テスタの前記キャッシュメモリの中に維持するものである。
請求項8
請求項１〜７のいずれか１つに記載のシステムにおいて、前記複数の交差テスタは、１若しくはそれ以上の計算コア上で実行するコンピュータ実行可能な命令のスレッドとして実施されるものである。
請求項9
請求項１〜８のいずれか１つに記載のシステムにおいて、このシステムは、さらに、３次元シーンを構成するプリミティブを格納するメモリを含むものであり、前記プリミティブを格納するメモリは、１若しくはそれ以上の計算コアを含むコンピューティングシステムのための主メモリとしての機能をさらに果たすものであり、前記１若しくはそれ以上の計算コアは集団で、時間的変化に基づいて前記交差テスタの実施とシェーダ・コード・ルーチンの実行との間で前記システムによって割り付けられた複数のスレッドを並行して実行可能であるものである。
請求項10
各計算資源がそれぞれのローカルメモリおよび共有主メモリに連結されている複数の計算資源を有するシステムにおいてプリミティブで構成されたシーンのレイトレーシングを制御する方法であって、主メモリのレイテンシはローカルメモリよりも高く、前記シーンの中で交差テストされるべきレイのそれぞれのサブセットを定義するデータを、前記計算資源の前記ローカルメモリの間に分散させる工程と、幾何学的形状との交差に関して、グループのメンバが複数の前記ローカルメモリに集団で格納されている前記レイのグループをテストすることを決定する工程と、ローカルメモリが前記グループの中のレイのための定義データを格納する少なくとも１つの計算資源に前記幾何学的形状データおよび前記レイ識別子を受信させるため、前記幾何学的形状およびレイ識別子のためのデータを前記計算資源に提供する工程と、前記計算資源から、前記グループの中のレイと前記幾何学的形状との間で検出された、ローカルメモリが該レイのための定義データを格納していた少なくとも１つの計算資源において前記グループの中の各レイをテストすることにより生じる交差の指標を受信する工程と、を含む、方法。
請求項11
請求項１０に記載の方法において、この方法は、さらに、前記主メモリから前記形状を定義するデータをフェッチする工程を含むものであり、前記幾何学的形状のためのデータを提供する工程は、前記形状定義データを前記グループの中の前記レイ識別子と共に前記計算資源へ提供するものである。
請求項12
請求項１０〜１１のいずれか１つに記載の方法において、前記指標はジオメトリ・アクセラレイション要素とレイとの間の交差のためのデータを含むものであり、前記レイのグループは、同じジオメトリ・アクセラレイション要素と交差すると決定されたレイを収集することにより形成されるものであり、十分な数のレイが収集されるまで、前記ジオメトリ・アクセラレイション要素に関係したジオメトリ・アクセラレイション要素のさらなるテストを延期する工程をさらに含むものである。
請求項13
請求項１０〜１２のいずれか１つに記載の方法において、前記ローカルメモリはキャッシュメモリを含むものであり、所定のレイが交差テストを終了するまで、前記所定のレイを定義するデータをキャッシュメモリの中で上書きされることから保護する工程をさらに含むものである。
請求項14
請求項１０〜１３のいずれか１つに記載の方法において、この方法は、さらに、レイ定義データがそれぞれのローカルメモリに格納されているレイのそれぞれの現在の最近傍の検出された交差を前記それぞれのローカルメモリの中に保持する工程と、任意のプリミティブと所定のレイとの間で最近傍であると考えられる交差を特定することに応答して各交差指標を生成する工程とを含むものである。
請求項15
請求項１０〜１４のいずれか１つに記載の方法において、前記幾何学的形状のための前記データは、（１）テストされるべき１若しくはそれ以上の形状を特定する参照情報、および、（２）テストされるべき１若しくはそれ以上の形状を定義するデータの組からの選択を含むものである。
請求項16
請求項１０〜１５のいずれか１つに記載の方法において、提供する工程は、レイ識別子を前記計算資源が受信するため連結されている第１のキューの中へキューイングする工程を含むものであり、受信する工程は、第２のキューから前記交差指標を受信する工程を含むものである。
請求項17
請求項１０〜１６のいずれか１つに記載の方法において、この方法は、さらに、前記レイのマスターコピーを前記主メモリに維持する工程を含むものである。
請求項18
請求項１０〜１７のいずれか１つに記載の方法を１若しくはそれ以上の計算資源上で実施するコンピュータ実行可能なコードのモジュールを格納する、コンピュータ読み取り可能な媒体。
請求項19
レイトレーシングを使用してプリミティブで構成された３次元シーンの表現をレンダリングするシステムであって、３次元シーンを構成するプリミティブを格納するメモリと、複数のレイのための定義データを格納する１若しくはそれ以上のメモリと、各交差テスタが前記レイのうちの少なくとも１つを前記プリミティブのうちの少なくとも１つとテストし、交差テスト結果の出力を生じる複数の交差テスタと、各シェーダ計算ユニットが、前記結果によって指示された、検出されたレイ／プリミティブ交差のためのシェーディングルーチンを実行するため動作可能であり、前記シェーディンルーチンの実行が交差テストされるべき新しいレイと、前記複数のレイのための定義データを格納する前記１若しくはそれ以上のメモリに格納されるべき前記新しいレイのための定義データとを生じる、複数のシェーダ計算ユニットと、前記交差テスタからシェーダ資源に前記交差テスト結果を出力する第１の通信リンクと、前記シェーディングルーチンの実行から生じ、前記レイの交差テスト中に前記１若しくはそれ以上のメモリからそれぞれのレイのための定義データを取り出すことを目的とする新しいレイのための識別子を、前記交差テスタへ送信する第２の通信リンクと、を含む、システム。
請求項20
請求項１９に記載のシステムにおいて、このシステムは、さらに、前記複数の交差テスタの間にメッセージを送るチャネルを含むものであり、前記交差テスタのそれぞれは、前記交差テスタによって受信されたメッセージの中のデータを複数のレイ識別子を収容するものとして解釈し、前記メッセージの中で特定された選択済みのレイを交差テストするため構成されているものである。
請求項21
請求項１９に記載のシステムにおいて、前記交差テスタは、レイ識別子のパケットを前記交差テスタの間に送るためリング状に構成されているものである。
請求項22
請求項１９に記載のシステムにおいて、前記交差テスタのそれぞれは、前記交差テスタと関連付けられたキャッシュが前記交差テスタの間に送られたメッセージの中で特定された前記レイのいずれかのための定義データを格納するかどうかの決定に基づいて、テストされるそれぞれのレイを選択するため動作可能であるものである。
請求項23
請求項１９に記載のシステムにおいて、前記複数の交差テスタは、１若しくはそれ以上の計算コア上で実行するコンピュータ実行可能な命令のスレッドとして実施され、前記計算コアはシーン内を移動するレイのサブセットへのローカライズされたキャッシュ・メモリ・アクセスを有するものである。
請求項24
請求項１９に記載のシステムにおいて、３次元シーンを構成するプリミティブを記憶する前記メモリは、１若しくはそれ以上の計算コアのための主メモリとして実施されるものであり、前記１若しくはそれ以上のコアは集団で、時間的変化に基づいて前記交差テスタの実施と前記シェーダ計算ユニットの実施との間に割り付けられているある程度の数のスレッドを並列して実行可能であるものである。