レイトレーシングコア及びこれを含むレイトレーシングチップ
【課題】
【解決手段】 レイトレーシングコアは、スクリーン座標値を含むアイレイの生成情報に基づいて少なくとも１つのアイレイを生成するレイ生成部及び前記少なくとも１つのアイレイをそれぞれ入力され、加速構造において前記入力されたアイレイと交差する三角形があるか否かをそれぞれチェックするＭＩＭＤ構造を持つ複数のＴ＆Ｉ部を含む。レイトレーシングコアはレイトレーシングの効率的処理のためのＭＩＭＤ並列構造を支援することができる。
【解決手段】 レイトレーシングコアは、スクリーン座標値を含むアイレイの生成情報に基づいて少なくとも１つのアイレイを生成するレイ生成部及び前記少なくとも１つのアイレイをそれぞれ入力され、加速構造において前記入力されたアイレイと交差する三角形があるか否かをそれぞれチェックするＭＩＭＤ構造を持つ複数のＴ＆Ｉ部を含む。レイトレーシングコアはレイトレーシングの効率的処理のためのＭＩＭＤ並列構造を支援することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は３Ｄグラフィック処理に係り、特にレイトレーシングコア及びこれを含むレイトレーシングチップに関するのである。
【背景技術】
【０００２】
３次元グラフィック技術はコンピュータに格納された幾何学的データ（ｇｅｏｍｅｔｒｉｃ ｄａｔａ）の３次元表現を使うグラフィック技術で、今日メディア産業とゲーム産業を含む多様な産業で広く使われている。一般に、３次元グラフィック技術は多くの演算量によって別個の高性能グラフィックプロセッサを要求する。
【０００３】
特に、近年プロセッサの発展によって非常に現実的な３次元グラフィックを生成することができるレイトレーシング（ｒａｙ ｔｒａｃｉｎｇ）技術が研究されている。特に、レイトレーシング技術は、反射、屈折、陰影を含む多様な光効果（ｏｐｔｉｃａｌ ｅｆｆｅｃｔｓ）をシミュレーションすることができる。
【図面の簡単な説明】
【０００４】
【図１】本発明の一実施例によるレイトレーシングコア（ｒａｙ ｔｒａｃｉｎｇ ｃｏｒｅ）を説明するブロック図である。
【図２】レイトレーシング過程を説明するための図である。
【図３】レイトレーシング過程を説明するための図である。
【図４】図１のセットアッププロセッシング部によるブロック基盤のレイの生成手順とこれを具現するハードウェアを説明するための図である。
【図５】図１の複数のＴ＆Ｉ部を説明するためのブロック図である。
【図６】図５のＴ＆Ｉパイプライン部を説明するための図である。
【図７】図５のＴ＆Ｉパイプライン部を説明するための図である。
【図８】図１のＴ＆Ｉ部のメモリシステムを説明するための図である。
【図９】図１のレイトレーシングチップで使われる加速構造と幾何学的データを説明するための図である。
【図１０】図１のレイトレーシングコアが含まれたレイトレーシングボード（ｒａｙ ｔｒａｃｉｎｇ ｂｏａｒｄ）を説明する図である。
【発明を実施するための形態】
【０００５】
実施例において、レイトレーシングコア（Ｒａｙ ｔｒａｃｉｎｇ ｃｏｒｅ）はスクリーン座標値を含むアイレイの生成情報に基づいて少なくとも１つのアイレイを生成するレイ生成部及び前記少なくとも１つのアイレイをそれぞれ入力され、加速構造（ＡＳ；Ａｃｃｅｌａｒａｔｉｏｎ Ｓｔｒｕｃｔｕｒｅ）において前記入力されたアイレイと交差する三角形（前記三角形は空間を構成する）があるか否かをそれぞれチェックするＭＩＭＤ構造（Ｍｕｌｔｉｐｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ Ａｒｃｈｉｔｅｃｔｕｒｅ）を持つ複数のＴ＆Ｉ部（ａ ｐｌｕｒａｌｉｔｙ ｏｆ Ｔｒａｖｅｒｓａｌ ＆ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｕｎｉｔｓ）を含む。
【０００６】
実施例において、レイトレーシングコア（Ｒａｙ ｔｒａｃｉｎｇ ｃｏｒｅ）はアイレイの生成情報（ｅｙｅ ｒａｙ ｇｅｎｅｒａｔｉｏｎ ｉｎｆｏｒｍａｔｉｏｎ）またはシェーディング情報（ｓｈａｄｉｎｇ ｉｎｆｏｒｍａｔｉｏｎ）（レイ−三角形ヒットポイントの座標値とカラー値及びシェーディングレイタイプを含む）の１つをマルチプレックシングするセットアッププロセッシング部、前記アイレイの生成情報またはシェーディング情報に基づいて少なくとも１つのアイレイまたはシェーディングレイを生成するかあるいは最終カラー値を決定するレイ生成部、及びＭＩＭＤ構造（Ｍｕｌｔｉｐｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ Ａｒｃｈｉｔｅｃｔｕｒｅ）を採択し、加速構造（ＡＳ；Ａｃｃｅｌｅｒａｔｉｏｎ Ｓｔｒｕｃｔｕｒｅ）において前記生成された少なくとも１つのアイレイまたはシェーディングレイと交差する三角形（前記三角形は空間を構成する）をそれぞれ決定する複数のＴ＆Ｉ部（ａ ｐｌｕｒａｌｉｔｙ ｏｆ Ｔｒａｖｅｒｓａｌ ＆ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｕｎｉｔｓ）を含む。
【０００７】
実施例において、レイトレーシングチップ（ｒａｙ ｔｒａｃｉｎｇ ｃｈｉｐ）は、複数のレイトレーシングコア、前記複数のレイトレーシングコアの中で適切なレイトレーシングコアにイメージの一部ブロックを割り当てるＸＹ生成器、及び前記複数のレイトレーシングコアのそれぞれから出力された最終カラー値を格納するメモリを含む。前記複数のレイトレーシングコアのそれぞれは、スクリーン座標値を含むアイレイの生成情報に基づいて少なくとも１つのアイレイを生成するレイ生成部、及び前記少なくとも１つのアイレイをそれぞれ入力され、加速構造（ＡＳ；Ａｃｃｅｌａｒａｔｉｏｎ Ｓｔｒｕｃｔｕｒｅ）において前記入力されたアイレイと交差する三角形（前記三角形は空間を構成する）があるか否かをそれぞれチェックするＭＩＭＤ構造（Ｍｕｌｔｉｐｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ Ａｒｃｈｉｔｅｃｔｕｒｅ）を持つ複数のＴ＆Ｉ部（ａ ｐｌｕｒａｌｉｔｙ ｏｆ Ｔｒａｖｅｒｓａｌ ＆ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｕｎｉｔｓ）を含む。
【０００８】
実施例において、レイトレーシングチップ（ｒａｙ ｔｒａｃｉｎｇ ｃｈｉｐ）は、複数のレイトレーシングコア、前記複数のレイトレーシングコアの中で適切なレイトレーシングコアにイメージの一部ブロックを割り当てるＸＹ生成器、及び前記複数のレイトレーシングコアのそれぞれから出力された最終カラー値を格納するメモリを含む。前記複数のレイトレーシングコアのそれぞれは、アイレイの生成情報（ｅｙｅ ｒａｙ ｇｅｎｅｒａｔｉｏｎ ｉｎｆｏｒｍａｔｉｏｎ）またはシェーディング情報（ｓｈａｄｉｎｇ ｉｎｆｏｒｍａｔｉｏｎ）（レイ−三角形ヒットポイントの座標値とカラー値及びシェーディングレイタイプを含む）の１つをマルチプレックシングするセットアッププロセッシング部、前記アイレイの生成情報またはシェーディング情報に基づいて少なくとも１つのアイレイまたはシェーディングレイを生成するかまたは最終カラー値を決定するレイ生成部、及びＭＩＭＤ構造（Ｍｕｌｔｉｐｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ Ａｒｃｈｉｔｅｃｔｕｒｅ）を採択し、加速構造（ＡＳ；Ａｃｃｅｌｅｒａｔｉｏｎ Ｓｔｒｕｃｔｕｒｅ）において前記生成された少なくとも１つのアイレイまたはシェーディングレイと交差する三角形（前記三角形は空間を構成する）をそれぞれ決定する複数のＴ＆Ｉ部（ａ ｐｌｕｒａｌｉｔｙ ｏｆ Ｔｒａｖｅｒｓａｌ ＆ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｕｎｉｔｓ）を含む。
【０００９】
本発明についての説明は構造的ないし機能的説明のための実施例に過ぎないので、本発明の権利範囲はこの明細書に説明された実施例によって制限されるものに解釈されてはいけない。すなわち、実施例は多様な変更が可能であり、さまざまな形態を持つことができるので、本発明の権利範囲は技術的思想を実現することができる均等物を含むものに理解されなければならない。
【００１０】
一方、本明細書に敍述される用語の意味は次のように理解されるべきであろう。
【００１１】
“第１”、“第２”などの用語は一構成要素を他の構成要素から区別するためのもので、これら用語によって権利範囲が限定されてはいけない。例えば、第１構成要素は第２構成要素に命名されることができ、同様に第２構成要素も第１構成要素に命名されることができる。
【００１２】
“及び／または”の用語は１つ以上の関連項目から提示可能なすべての組合せを含むものに理解されなければならない。例えば、“第１項目、第２項目及び／または第３項目”の意味は第１、第２または第３項目だけでなく、第１項目、第２項目または第３項目の中で２個以上から提示可能なすべての項目の組合せを意味する。
【００１３】
ある構成要素が他の構成要素に“連結されて”いると言及されたときには、その他の構成要素に直接連結されることもできるが、中間に他の構成要素が存在することもできると理解されなければならないであろう。一方、ある構成要素が他の構成要素に“直接連結されて”いると言及されたときには、中間に他の構成要素が存在しないものに理解されなければならないであろう。一方、構成要素間の関係を説明する他の表現、つまり“〜の間に”と“すぐ〜の間に”または“〜に隣り合う”と“〜に直接隣り合う”なども同様に解釈されなければならない。
【００１４】
単数の表現は文脈上明白に異なるように意味しない限り複数の表現を含むものに理解されなければならなく、“含む”または“持つ”などの用語は説示された特徴、数字、段階、動作、構成要素、部分品またはこれらを組み合わせたものが存在することを指定しようとするものであるばかり、１つまたはそれ以上の他の特徴、あるいは数字、段階、動作、構成要素、部分品またはこれらを組み合わせたものなどの存在または付加可能性を予め排除しないものに理解されなければならない。
【００１５】
各段階は文脈上明白に特定の手順を記載しない限り、明記された手順とは異なるように起こることができる。すなわち、各段階は明記された手順と同様に起こることもでき、実質的に同時に遂行されることもでき、反対の順に遂行されることもできる。
【００１６】
ここで使われるすべての用語は他の意味に定義されない限り、本発明が属する分野で通常の知識を持った者によって一般的に理解されるものと同一意味を持つ。一般的に使われる前もって定義されている用語は関連技術の文脈で有する意味と一致するものに解釈されなければならなく、本明細書で明白に定義しない限り、理想的にあるいは過度に形式的な意味を持つものに解釈されることができない。
【００１７】
図１は本発明の一実施例によるレイトレーシングコア（ｒａｙ ｔｒａｃｉｎｇ ｃｏｒｅ）を説明するブロック図である。
【００１８】
図１を参照すれば、レイトレーシングコア１００は、データパス部（ｄａｔａ ｐａｔｈｐａｒｔ）とメモリシステム部（ｍｅｍｏｒｙ ｓｙｓｔｅｍ ｐａｒｔ）に大別される。一実施例において、レイトレーシングコア１００はグラフィックプロセッサのようなチップに含まれることができ、他の一実施例において、レイトレーシングコア１００は単一チップとして具現されることができる。
【００１９】
データパス部は、セットアッププロセッシング部（ｓｅｔｕｐ ｐｒｏｃｅｓｓｉｎｇ ｕｎｉｔ）１１０、レイ生成部（ｒａｙ ｇｅｎｅｒａｔｉｏｎ ｕｎｉｔ）１２０、複数のＴ＆Ｉ部（Ｔｒａｖｅｒｓａｌ ＆ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｕｎｉｔ）１３０、ヒットポイント計算部（Ｈｉｔ Ｐｏｉｎｔ Ｃａｌｃｕｌａｔｉｏｎ Ｕｎｉｔ）１４０、シェーディング部（Ｓｈａｄｉｎｇ Ｕｎｉｔ）１５０及び制御部１６０を含む。メモリシステム部は、レジスタ（Ｒｅｇｉｓｔｅｒ）１６５、Ｌ１キャッシュ（Ｃａｃｈｅ）１７０、Ｌ２キャッシュ１７５、キャッシュ１８０、バッファ（Ｂｕｆｆｅｒ）１８５、スタック１９０、及びメモリ（Ｍｅｍｏｒｙ）１９５を含む。便宜上、図１のメモリシステム部の構成要素のそれぞれは別に具現されるものとして説明したが、必要によって構成要素の中で少なくとも一部は物理的に同等なメモリで具現できる。
【００２０】
また、レイトレーシングチップ１００は外部メモリ（Ｅｘｔｅｒｎａｌ Ｍｅｍｏｒｙ）１０００と連結されることができ、外部メモリ１０００は加速構造（ＡＳ；Ａｃｃｅｌｅｒａｔｉｏｎ Ｓｔｒｕｃｔｕｒｅ）格納部１１００、幾何学的データ（Ｇｅｏｍｅｔｒｙ Ｄａｔａ）格納部１２００、テクスチャイメージ（Ｔｅｘｔｕｒｅ Ｉｍａｇｅ）格納部１３００、及びフレーム（Ｆｒａｍｅ）格納部１４００を含む。
【００２１】
加速構造（ＡＳ）はレイトレーシングに一般的に使われるｋｄ−ｔｒｅｅ（ｋ−ｄｅｐｔｈ ｔｒｅｅ）またはＢＶＨ（Ｂｏｕｎｄｉｎｇ Ｖｏｌｕｍｅ Ｈｉｅｒａｒｃｈｙ）を含み、幾何学的データはレイトレーシングのための三角形に関する情報（以下、三角形情報）を含む。一実施例において、三角形情報は三角形の三点に対するテクスチャ座標（ｔｅｘｔｕｒｅ ｃｏｏｒｄｉｎａｔｅ）と法線ベクトル（ｎｏｒｍａｌ ｖｅｃｔｏｒ）を含むことができる。
【００２２】
図９は図１のレイトレーシングチップで使われる加速構造と幾何学的データの関係を説明するための図である。
【００２３】
図９において、加速構造（ＡＳ）はｋｄ−ｔｒｅｅを使うと仮定した。ｋｄ−ｔｒｅｅは空間分割ツリー（ｓｐａｔｉａｌ ｐａｒｔｉｔｉｏｎｉｎｇ ｔｒｅｅ）の一種で、レイ−三角形交差テスト（Ｒａｙ−Ｔｒｉａｎｇｌｅ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｔｅｓｔ）のために使われる。ｋｄ−ｔｒｅｅはボックスノード（Ｂｏｘ Ｎｏｄｅ）９１０、内部ノード（Ｉｎｎｅｒ Ｎｏｄｅ）９２０、及びリーフノード（ｌｅａｆ ｎｏｄｅ）９３０を含み、リーフノード９３０は幾何学的データに含まれた少なくとも１つの三角形情報をポインティングするための三角形リストを含む。一実施例において、幾何学的データに含まれた三角形情報が配列で具現された場合には、リーフノード９３０に含まれた三角形リストは配列インデックスに相応することができる。
【００２４】
図２及び図３はレイトレーシング過程を説明するための図である。図１〜図３を参照してレイトレーシングコア１００の全体的な動作を説明する。
【００２５】
セットアッププロセッシング部１１０はアイレイの生成情報（ｅｙｅ ｒａｙ ｇｅｎｅｒａｔｉｏｎ ｉｎｆｏｒｍａｔｉｏｎ）を準備し、準備されたアイレイの生成情報とシェーディング部１５０から出力されたシェーディング情報を選択する。アイレイの生成情報はアイレイの生成のためのスクリーン座標値を含む。シェーディング情報（ｓｈａｄｉｎｇ ｉｎｆｏｒｍａｔｉｏｎ）はスクリーン座標値を求めるためのレイインデックス（後述する）、レイ−三角形ヒットポイント（ｒａｙ−ｔｒｉａｎｇｌｅ ｈｉｔ ｐｏｉｎｔ）（後述する）の座標値とカラー値、及びシェーディングレイタイプを含み、シェーディングレイタイプによる付加情報をさらに含むことができる。シェーディングレイ（ｓｈａｄｉｎｇ ｒａｙ）はシャドーレイ（ｓｈａｄｏｗ ｒａｙ）、派生レイ（ｓｅｃｏｎｄａｒｙ ｒａｙ）またはナルレイ（ＮＵＬＬ ｒａｙ）を含み、派生レイは屈折レイ（ｒｅｆｒａｃｔｉｏｎ ｒａｙ）または反射レイ（ｒｅｆｌｅｃｔｉｏｎ ｒａｙ）を含む。屈折レイの場合、付加情報はレイ−三角形ヒットポイントの屈折率を含み、反射レイの場合、付加情報はレイ−三角形ヒットポイントの反射率をさらに含む。セットアッププロセッシング部１１０の動作方式は図４を参照して後述する。
【００２６】
レイ生成部１２０はアイレイの生成情報またはシェーディング情報に基づいて少なくとも１つのレイを生成することができる（段階Ｓ３１０またはＳ３４０）。図２に示すように、少なくとも１つのレイはアイレイＥ、シャドーレイＳ、屈折レイＦ、及び／または反射レイＲを含むことができる。生成された派生レイの個数が２以上の場合には、１つはＴ＆Ｉ部１３０に出力され、残りは派生レイスタック１９０に格納される。派生レイの場合、レイ生成部１２０は反射レイＲのヒットポイントまたは屈折レイＦのヒットポイントを考慮する必要があるからである。例えば、反射レイＦと屈折レイＲの両方が生成される場合には、反射レイＦはＴ＆Ｉ部１３０に出力されることができ、屈折レイＲは派生レイスタック１９０に格納されることができる。
【００２７】
シェーディングレイタイプがナルレイに相応する場合には、レイ生成部１２０は派生レイスタック１９０に格納された派生レイを取り入れ、取り出された派生レイをＴ＆Ｉ部１３０に出力する。シェーディングレイスタック１９０が空いている場合には、レイ生成部１２０はレイインデックス（後述する）に基づいてスクリーン座標値を収得し、スクリーン座標値とレイ−三角形ヒットポイント（後述する）のカラー値に基づいて最終カラー値をカラーバッファ１８５ｃに使う。
【００２８】
複数のＴ＆Ｉ部１３０は並列のＭＩＭＤ（Ｍｕｌｔｉｐｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ）構造を採択し、複数のＴ＆Ｉ部１３０のそれぞれはレイ生成部１２０から生成されたレイ（アイレイ、シャドーレイまたは派生レイ）を入力され、加速構造（ＡＳ；Ａｃｃｅｌａｒａｔｉｏｎ Ｓｔｒｕｃｔｕｒｅ）においてレイと交差する三角形があるか否かをチェックする。すなわち、複数のＴ＆Ｉ部１３０のそれぞれは加速構造（ＡＳ）を訪問（ｔｒａｖｅｒｓｅ）し、三角形（ｔｒｉａｎｇｌｅｓ）に対する交差テスティング（ｉｎｔｅｒｓｅｃｔｉｏｎ ｔｅｓｔｉｎｇ）を遂行する。複数のＴ＆Ｉ部１３０の動作方式は図５〜図１１を参照して後述する。
【００２９】
ヒットポイント計算部１４０は交差する三角形（ｉｎｔｅｒｓｅｃｔｅｄ ｔｒｉａｎｇｌｅ）に対してレイ−三角形ヒットポイント（ｒａｙ−ｔｒｉａｎｇｌｅ ｈｉｔ ｐｏｉｎｔ）（つまり、交差する三角形においてレイがヒットされるポイント）の座標値を計算し、シェーディング部１５０はレイ−三角形ヒットポイントに対してカラー値を計算する。一実施例において、シェーディング部１５０はレイ−三角形ヒットポイントに対するカラー値を得るためにフォーン照明（ｐｈｏｎｇ ｉｌｌｕｍｉｎａｔｉｏｎ）とテクスチャマッピング（ｔｅｘｔｕｒｅ ｍａｐｐｉｎｇ）を遂行することができる（段階Ｓ３４０）。また、シェーディング部１５０はレイ生成部１２０による最終カラー値の決定またはシェーディングレイの生成のためのシェーディング情報を生成し、シェーディング情報をセットアッププロセッシング部１１０に伝送する。それ以上のレイの生成が必要でない場合には、シェーディングレイタイプはナルレイ（Ｎｕｌｌ Ｒａｙ）に相応することができる。一実施例において、シェーディング部１５０は物質メモリ１９５ｃに格納されたレイ−三角形ヒットポイントに関する物質情報に基づいて派生レイの生成を決定することができる。以下、データパスに含まれた構成要素のそれぞれを説明する。
【００３０】
＜パイプライン制御構造＞
レイトレーシングアルゴリズムは再帰的に遂行され、（ｉ）アイレイの生成過程（段階Ｓ３１０）、（ｉｉ）加速構造訪問（ＡＳ Ｔｒａｖｅｒｓａｌ）過程（段階Ｓ３２０）、（ｉｉｉ）レイ−三角形交差テスト（ｒａｙ−Ｔｒｉａｎｇｌｅ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｔｅｓｔ）過程（段階Ｓ３３０）、（ｉｖ）シェーディング及びシェーディングレイの生成過程（段階Ｓ３４０）を含む。したがって、レイトレーシングアルゴリズムは一般的なストリーミングパイプライン構造（ｓｔｒｅａｍｉｎｇ ｐｉｐｅｌｉｎｅ ａｒｃｈｉｔｅｃｔｕｒｅ）を使うことが適切でないこともある。
【００３１】
本発明はレイトレーシングアルゴリズムに適切なパイプライン構造を導入し、制御部１６０はパイプライン（レジスタ）１６５のフラッグ（ｆｌａｇ）を介してパイプラインの動作を制御する。すなわち、本発明は、パイプラインの効率を高めるために、フラッグ（ｆｌａｇ）基盤の単純な制御構造を使う。一実施例において、パイプラインのレジスタ１６５のフラッグはオンまたはオフのための１ビット情報に相応することができ、フラッグがオンに相応する場合、レジスタ１６５は以前のステージで出力された情報を格納することができる。結果として、パイプラインはフラッグによって同期的（ｓｙｎｃｈｒｏｎｏｕｓ）に処理できるが、データパスを構成する構成要素のそれぞれは非動機的（ａｓｙｎｃｈｒｏｎｏｕｓ）に結果を出力することができる。
【００３２】
必要によって、データパスを構成する構成要素のそれぞれはロード不均衡（ｌｏａｄ ｉｍｂａｌａｎｃｅ）による待機時間を減らすためにバッファ１８５を使うことができる。例えば、複数のＴ＆Ｉ部１３０のそれぞれは性能向上とＭＩＭＤ構造支援のためにバッファ１８５を使うことができる。
【００３３】
＜セットアッププロセッシング部１１０＞
セットアッププロセッシング部１１０はアイレイの生成情報を初期化させる。初期化過程は、スクリーン座標値を決定し、決定されたスクリーン座標値をレイインデックスに変換する過程を含む。レイインデックスはパイプラインの各段階でレジスタ１６５のサイズを減少させるために使われる。セットアッププロセッシング部１１０はスクリーン座標値とレイインデックスをレイ生成部１２０に伝送する。
【００３４】
セットアッププロセッシング部１１０はアイレイの生成情報またはシェーディング情報をマルチプレックシングする。一実施例において、シェーディング情報はアイレイの生成情報に対して優先権（ｐｒｉｏｒｉｔｙ）を持つことができる。以前のスクリーン座標値を持つピクセルで生成されたレイに対する処理が先に行われることが好ましいからである。
【００３５】
図４は図１のセットアッププロセッシング部によるブロック基盤のレイの生成手順とこれを具現するハードウェアを説明するための図である。
【００３６】
スクリーンは複数のｍ×ｎ（ｍとｎは偶数）ピクセルブロック（以下、スーパーブロック）を含み、各スーパーブロックは同じ大きさのＮ個（Ｎは複数のＴ＆Ｉ部１３０の個数）のピクセルブロック（以下、サブブロック）を含む。
【００３７】
セットアッププロセッシング部１１０は、複数のＴ＆Ｉ部１３０ｍｐそれぞれでキャッシュヒット率（ｃａｃｈｅ ｈｉｔ ｒａｔｅ）を増加させるために、スクリーンを複数のブロック（つまり、サブブロック）に分割し、各ブロック基盤のアイレイの生成手順を決定することができる。例えば、スクリーンは１６×１６ピクセルブロックでそれぞれ構成された複数のスーパーブロックを含むことができ、スーパーブロックのそれぞれは４個の８×８ピクセルブロックでそれぞれ構成されたサブブロックを含むことができる。第１〜第４ピクセルブロック４１０〜４４０のそれぞれは第１〜第４Ｔ＆Ｉ部１３０ａ〜１３０ｄに割り当てられることができる。
【００３８】
以下、第１サブブロック４１０は図４（ｂ）に示す８×８ピクセルブロックに相応し、第１Ｔ＆Ｉ部１３０ａに割り当てられたと仮定する。
【００３９】
セットアッププロセッシング部１１０は線形のｎ−ビットカウンター４５０を使って第１Ｔ＆Ｉ部１３０ａのキャッシュヒット率を増加させるためのレイの生成手順を決定することができる。線形のｎ−ビットカウンター４５０の第１グループ（第１グループは連続しない少なくとも１つのビットを含むことができる）はサブブロックのｘ座標値を示し、線形のｎ−ビットカウンター４５０の第２グループ（第２グループは第１グループに属したビットを含まなく、連続しない少なくとも１つのビットを含むことができる）はサブブロックのｙ座標値を示す。
【００４０】
レイ生成部１２０は、図４（ｂ）及び図４（ｃ）に示すように、セットアッププロセッシング部１１０によって決定されたアイレイの生成手順にレイを生成する。一方、図４（ｂ）に示すピクセル（例えば、ピクセル０）はレイの生成のためのピクセルを意味する。例えば、６４個のピクセルの場合、セットアッププロセッシング部１１０は線形の６−ビットカウンター４５０を含むことができ、線形の６−ビットカウンター４５０の値Ｉ＝ｉ５ｉ４ｉ３ｉ２ｉ１ｉｉ０の場合には、ピクセルの座標（ｘ，ｙ）＝（ｉ５ｉ３ｉ１，ｉ４ｉ２ｉ０）に相応することができる。すなわち、図４（ｃ）の線形の６−ビットカウンター４５０はカウント数が増加するにつれて図４（ｂ）のピクセル座標が易しくマッピングされるように具現される。
【００４１】
＜レイ生成部１２０＞
レイ生成部１２０はセットアッププロセッシング部１１０から伝送されたスクリーン座標値とレイインデックスをレイインデックスマッピングテーブル（１９５ａ）に格納し、アイレイの生成情報またはシェーディング情報に基づいて少なくとも１つのレイを生成するかあるいは最終カラー値をカラーバッファ１８５ａに格納する。
【００４２】
アイレイの生成情報が入力された場合には、レイ生成部１２０はアイレイＥを生成する。シェーディング情報が入力された場合には、レイ生成部１２０はシェーディングレイタイプによってシェーディングレイＳ、Ｒ、Ｆを生成し、シェーディングレイタイプがナルレイに相応する場合には、レイ生成部１２０は派生レイスタック１９０に格納された派生レイを取り入れる。派生レイスタック１９０が空いている場合には、レイ生成部１２０はレイインデックスに基づいてスクリーン座標値を求め、求められたスクリーン座標値とレイ−三角形ヒットポイント（後述する）のカラー値をカラーバッファ１８５ｃに格納する。以下、レイ生成部１２０がレイを生成する過程を説明する。
【００４３】
アイレイの生成において、レイ生成部１２０はレイインデックスマッピングテーブル（１９５ａ）を用いてアイレイのスクリーン座標値を求め、スクリーン座標値に基づいてアイレイＥを生成する。一般に、アイレイはスクリーン座標値とカメラ位置（つまり、アイ位置）に基づいて生成できる。レイ生成部１２０は複数のＴ＆Ｉ部１３０の中で適切なＴ＆Ｉ部（例えば、１３０ａ）に生成されたアイレイを割り当てる。
【００４４】
シャドーレイの生成において、シェーディングレイタイプがシャドーレイに相応する場合には、レイ生成部１２０はレイ−三角形ヒットポイント（後述する）に基づいてシャドーレイを生成する。一般に、シャドーレイはスクリーン座標値と光位置（ｌｉｇｈｔ ｐｏｓｉｔｉｏｎ）に基づいて生成できる。一実施例において、演算量を減らすために、レイ生成部１２０は光源（ｌｉｇｈｔ ｓｏｕｒｃｅ）の数を制限することができる。
【００４５】
派生レイの生成において、シェーディングレイタイプが派生レイに相応する場合には、レイ生成部１２０は少なくとも１つの派生レイ（つまり、屈折レイ及び／または反射レイ）を生成する。派生レイの個数が２以上の場合には、レイ生成部１２０は１つを除いた派生レイを派生レイスタック１９０に格納する。レイ生成部１２０は複数のＴ＆Ｉ部１３０の中で適切なＴ＆Ｉ部（例えば、１３０ｂ）に格納されない派生レイを割り当てる。派生レイスタック１９０に格納された派生レイはスクリーン座標値、方向ベクトル値及びＲＧＢに対する加重値を含むことができる。一実施例において、演算量を減らすために、レイ生成部１２０はレイ深さ（ｒａｙ ｄｅｐｔｈ）を使って派生レイによる派生レイの無制限的な生成を防止することができる。
【００４６】
ナルレイの生成において、シェーディングレイタイプがナルレイに相応する場合には、レイ生成部１２０は派生レイスタック１９０に格納された派生レイを取り入れた後、複数のＴ＆Ｉ部１３０の中で適切なＴ＆Ｉ部（例えば、１３０ｃ）に取り入れた派生レイを割り当てる。派生レイスタック１９０が空いている場合には、レイ生成部１２０はレイインデックスに基づいてスクリーン座標値を求め、求められたスクリーン座標値とレイ−三角形ヒットポイント（後述する）のカラー値に基づいて最終カラー値をカラーバッファ１８５ｃに格納する。カラーバッファ１８５ｃに格納された最終カラー値は外部メモリ１０００に格納される。
【００４７】
＜Ｔ＆Ｉ部１３０＞
複数のＴ＆Ｉ部１３０は加速構造訪問（ＡＳ Ｔｒａｖｅｒｓａｌ）過程（段階Ｓ３２０）とレイ−三角形交差テスト（ｒａｙ−Ｔｒｉａｎｇｌｅ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｔｅｓｔ）過程を遂行する。
【００４８】
図５は図１の複数のＴ＆Ｉ部を説明するためのブロック図である。
【００４９】
図５を参照すれば、複数のＴ＆Ｉ部１３０のそれぞれはバッファ１８５、Ｌ１キャッシュ１７０及びＴ＆Ｉパイプライン部（Ｔｒａｖｅｒｓａｌ ＆ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｐｉｐｅｌｉｎｅ Ｕｎｉｔ）１３５を含む。
【００５０】
複数のＴ＆Ｉ部１３０はＴ＆Ｉパイプライン部１３５が独立的に実行されるＭＩＭＤ並列構造を採択する。周知のように、レイトレーシングアルゴリズムはＭＩＭＤ並列構造に適合するように各レイを独立的に処理することができる。ＳＩＭＤ（Ｓｉｎｇｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ）と比較し、ＭＩＭＤ並列構造はパイプラインをより効率よく使うことができる利点を持つ。
【００５１】
複数のＴ＆Ｉ部１３０のそれぞれは自体の入力バッファ１８５ａと出力バッファ１８５ｂを含む。同一ピクセルから生成されたレイ（アイレイ及びシェーディングレイ）は同一Ｔ＆Ｉ部１３０で処理されることが好ましいからである。また、複数のＴ＆Ｉ部１３０のそれぞれは自体のＬ１キャッシュ１７０を含む。ＭＩＭＤ構造は効率的なキャッシュメモリを要求するからである。
【００５２】
Ｔ＆Ｉパイプライン部１３５は、（ｉ）訪問（ｔｒａｖｅｒｓａｌ）過程、（ｉｉ）三角形リスト取り入れ（ｔｒｉａｎｇｌｅ ｌｉｓｔ ｆｅｔｃｈ）過程、及び（ｉｉｉ）レイ−三角形交差テスト（ｒａｙ−Ｔｒｉａｎｇｌｅ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｔｅｓｔ）過程を遂行する。加速構造（ＡＳ）はｋｄ−ｔｒｅｅに相応すると仮定した。
【００５３】
訪問過程において、Ｔ＆Ｉパイプライン部１３５は加速構造（ＡＳ）でノードを検索することで、レイと交差するリーフノード（ｌｅａｆ ｎｏｄｅ）を捜す。加速構造（ＡＳ）の訪問アルゴリズムは当業者によく知られているので、これについての説明は省略する。三角形リスト取り入れ過程で、Ｔ＆Ｉパイプライン部１３５は交差するリーフノードに含まれた三角形リストを読み取る。レイ−三角形交差テスト過程で、Ｔ＆Ｉパイプライン部１３５は三角形リストの座標情報を読み取り、与えられたレイに対して交差テストを遂行する。
【００５４】
図６及び図７は図５のＴ＆Ｉパイプライン部を説明するための図である。
【００５５】
［ＳＣＨＭＩＴＴＬＥＲ，Ｊ．， ＷＡＬＤ，Ｉ．， ＡＮＤ ＳＬＵＳＡＬＬＥＫ Ｐ． ２００２． Ｓａａｒｃｏｒ：ａ ｈａｒｄｗａｒｅ ａｒｃｈｉｔｅｃｔｕｒｅ ｆｏｒ ｒａｙ ｔｒａｃｉｎｇ． Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＳＩＧＧＲＡＰＨ／ＥＵＲＯＧＲＡＰＨＩＣＳ ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｇｒａｐｈｉｃｓ Ｈａｒｄｗａｒｅ］（以下、参照文献１）と［ＳＣＨＭＩＴＴＬＥＲ， Ｊ．， ＷＯＯＰ， Ｓ．， ＷＡＧＮＥＲ， Ｄ．， ＰＡＵＬ， Ｗ． Ｊ．， ＡＮＤ ＳＬＵＳＡＬＬＥＫ， Ｐ．， ２００４． Ｒｅａｌｔｉｍｅ ｒａｙ ｔｒａｃｉｎｇ ｏｆ ｄｙｎａｍｉｃ ｓｃｅｎｅｓ ｏｎ ａｎ ＦＰＧＡ ｃｈｉｐ． Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＳＩＧＧＲＡＰＨ／ＥＵＲＯＧＲＡＰＨＩＣＳ ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｇｒａｐｈｉｃｓ Ｈａｒｄｗａｒｅ］（以下、参照文献２）にあるレイトレーシング構造は訪問（ｔｒａｖｅｒｓａｌ）と交差テスト（ｉｎｔｅｒｓｅｃｔｉｏｎ ｔｅｓｔ）のために別個のハードウェアを使う。しかし、図５のＴ＆Ｉパイプライン部１３５は訪問（ｔｒａｖｅｒｓａｌ）と交差テスト（ｉｎｔｅｒｓｅｃｔｉｏｎｔｅｓｔ）の間のロード不均衡（ｌｏａｄ ｉｍｂａｌａｎｃｅ）を引き起こさず、加速構造（ＡＳ）を効率よく支援するように統合されたパイプライン構造を採択した。すなわち、図７のＴ＆Ｉパイプライン部１３５は訪問（ｔｒａｖｅｒｓａｌ）と交差テスト（ｉｎｔｅｒｓｅｃｔｉｏｎ ｔｅｓｔ）の各段階で同一ハードウェアを使うことができる。以下、前記参照文献１と参照文献２との相違点を主に説明する。
【００５６】
図６及び図７において、加速構造（ＡＳ）はｋｄ−ｔｒｅｅに相応すると仮定した。図６はＴ＆Ｉパイプライン部１３５で行われる訪問過程及びレイ−三角形交差テスト過程で使われる演算器と演算器の個数を説明する。訪問過程は大別してレイ−ボックス交差テスト（Ｒａｙ−Ｂｏｘ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｔｅｓｔ）と訪問（Ｔｒａｖｅｒｓａｌ）を含む。図９において、ｋｄ−ｔｒｅｅのトップノード９１０はＢｏｘノードに相応するからである。パイプライン制御部７１０はＴ＆Ｉパイプライン部１３５内のパイプラインを制御する。
【００５７】
レイ−ボックス交差テスト、訪問及びレイ−三角形交差テストにおける演算過程はＭＯＬＬＥＲ， Ｔ．， ＡＮＤ ＴＲＵＭＢＯＲＥ， Ｂ． １９９７ Ｆａｓｔ， ｍｉｎｉｍｕｍ ｓｔｏｒａｇｅ ｒａｙ−ｔｒｉａｎｇｌｅ ｉｎｔｅｒｓｅｃｔｉｏｎ， Ｊｏｕｒｎａｌ ｏｆ Ｇｒａｐｈｉｃｓ Ｔｏｏｌｓによく開示されているので、これについての説明は省略する。
【００５８】
図６に示すように、レイ−ボックス交差テストで順次必要な演算器は６個のフローティングポイント加算器（ＦＡＤＤ， Ｆｌｏａｔｉｎｇ Ｐｏｉｎｔ Ａｄｄｅｒ）、６個のフローティングポイント乗算器（ＦＭＵＬ， Ｆｌｏａｔｉｎｇ Ｐｏｉｎｔ Ｍｕｌｔｉｐｌｉｅｒ）、３個の第１フローティングポイント比較器（ＦＣＯＭＰ， Ｆｌｏａｔｉｎｇ Ｐｏｉｎｔ Ｃｏｍｐａｒａｔｏｒ）、２個の第２フローティングポイント比較器（ＦＣＯＭＰ）、及び１個の第３フローティングポイント比較器（ＦＣＯＭＰ）を含む。
【００５９】
図６に示すように、訪問において順次必要な演算器は１個のフローティングポイント加算器（ＦＡＤＤ）、１個のフローティングポイント乗算器（ＦＭＵＬ）、及び２個のフローティングポイント比較器（ＦＣＯＭＰ）を含む。また、訪問において順次必要な演算はスタックメモリ（１８５ｄ）へのスタック書き込み及びスタック読み取りを含む。
【００６０】
図６に示すように、レイ−三角形交差テストで順次必要な演算器は、９個の第１フローティングポイント加算器（ＦＡＤＤ）、１２個の第１フローティングポイント乗算器（ＦＭＵＬ）、６個の第２フローティングポイント加算器（ＦＡＤＤ）、１２個の第２フローティングポイント乗算器（ＦＭＵＬ）、４個のトリプル入力フローティングポイント加算器（ＴＦＡＤＤ， Ｔｒｉｐｐｌｅ Ｉｎｐｕｔ ＦＡＤＤ）、１個のフローティングポイント加算器（ＦＡＤＤ）、フローティングポイント除算器（ＦＤＩＶ）、及び２個のフローティングポイント比較器（ＦＣＯＭＰ）を含む。レイ−三角形交差テストは与えられたレイによって交差する最も近接した三角形と目の位置（またはカメラの位置）との交差点の間の距離を計算する。交差した三角形が存在する場合には、交差した三角形に関する情報はヒットポイント計算部１４０に伝送され、そうではない場合には、次の訪問段階が遂行される。一実施例において、レイ−三角形交差テストはＭＯＬＬＥＲ， Ｔ．， ＡＮＤ ＴＲＵＭＢＯＲＥ， Ｂ． １９９７． Ｆａｓｔ， ｍｉｎｉｍｕｍ ｓｔｏｒａｇｅ ｒａｙ−ｔｒｉａｎｇｌｅ ｉｎｔｅｒｓｅｃｔｉｏｎ． Ｊｏｕｒｎａｌ ｏｆ Ｇｒａｐｈｉｃｓ Ｔｏｏｌｓに開示されたアルゴリズムを用いることができる。
【００６１】
図７は訪問過程、三角形リスト取り入れ過程及びレイ−三角形交差テスト過程を遂行するためのＴ＆Ｉパイプライン部１３５の構成を説明する。図７のＴ＆Ｉパイプライン部１３５は統合された１つのパイプラインを使って図６のパイプラインの順に訪問過程、三角形取り入れ過程及びレイ−三角形交差テスト過程を遂行するようにパイプラインを構成する。すなわち、図７の７１０に含まれたパイプライン段階は訪問過程及びレイ−三角形交差テスト過程を遂行し、その以外の段階はキャッシュ接近または三角形リスト取り入れ段階を遂行する。図７に示すように、本発明は動作モードによって別個のハードウェアを使わずに統合されたパイプライン構造を採択する。
【００６２】
＜Ｔ＆Ｉ部１３０のメモリシステム＞
図８は図１のＴ＆Ｉ部のメモリシステムを説明するための図である。
【００６３】
Ｔ＆Ｉ部１３０においてメモリ接近はレイトレーシングでの全体メモリ接近の絶対的多数を占めるので、Ｔ＆Ｉ部１３０のメモリシステムは効率よくデザインされる必要がある。図１及び図５に示すように、複数のＴ＆Ｉ部１３０のそれぞれは３個のＬ１キャッシュを含み、共通のＬ２キャッシュを使う。キャッシュメモリの二重構造（ｔｗｏ−ｌｅｖｅｌ ｈｉｅｒａｒｃｈｙ）にもかかわらず、キャッシュミス（ｃａｃｈｅ ｍｉｓｓ）によるパイプラインストール時間（ｐｉｐｅｌｉｎｅ ｓｔａｌｌ ｔｉｍｅ）は依然として大きい。したがって、本発明はこれを解決するために次の２方案を使う。
【００６４】
第１方案はＬ１キャッシュミスに関するもので、Ｌ１キャッシュミスが発生した場合、Ｌ１キャッシュミスが次のループで解決されるように、Ｌ１キャッシュミスをストール（ｓｔａｌｌ）なしに飛ばすものである。図５において、パイプラインＰ１でキャッシュミスが発生した場合、パイプライン制御部７１０は次の段階のパイプラインＰ２にストールなしに続いて進む。キャッシュ制御部（図示せず）は、パイプラインＰ１の再処理のために、Ｌ２キャッシュ１７５または外部メモリ１０００からミスされたデータを取り入れる。パイプラインＰ１８の後にさらにパイプラインＰ１が再び進めば、Ｌ１キャッシュに対する接近が発生する。キャッシュミスが解決されれば、パイプライン制御部７１０は次の段階のパイプラインＰ２を正常に処理し、キャッシュミスがまた発生すれば、パイプライン制御部７１０はキャッシュミスが解決されるまで前記過程を繰り返す。結果として、キャッシュミスによるキャッシュミスペナルティはよほど緩和できる。
【００６５】
第２方案はＬ２キャッシュミスに関するもので、Ｌ２キャッシュミスが発生した場合、Ｌ２キャッシュミスをストールなしに飛ばすものである。現在のレイに対してＬ１キャッシュミスが発生した場合には、Ｌ２キャッシュ接近のための要求がＬ１ Ａｄｄｒ ＦＩＦＯ８１０に入力される。Ｌ１ Ａｄｄｒ ＦＩＦＯ８１０にある現在レイの要求によるＬ２キャッシュ接近がキャッシュヒットであると結論付けられれば、要求に対する住所とデータはＬ１ Ａｄｄｒ／Ｄａｔａ ＦＩＦＯ８２０に入力される。そうではない場合には、外部メモリ１０００に対する他の要求がＬ２ Ａｄｄｒ ＦＩＦＯ８１０に入力され、Ｌ１ Ａｄｄｒ ＦＩＦＯ６１０にある現在レイの要求は削除される。削除された要求に対するキャッシュ接近は次のループで再び発生する。次のループで発生したキャッシュ接近が発生すれば、前述した過程が繰り返される。前記過程はキャッシュ接近がヒットであると結論付けられるまで繰り返される。したがって、現在レイの要求によるＬ２キャッシュ接近でキャッシュミスが発生した場合であっても次のレイの要求によるＬ２キャッシュ接近は許容される。結果として、キャッシュミスによるキャッシュミスペナルティはよほど緩和できる。
【００６６】
図８はＮｏｄｅ Ｌ１ Ｃａｃｈｅ１７０を例としてあげたが、Ｌ１ Ｌｉｓｔ ＣａｃｈｅとＬ１ Ｔｒａｎｇｌｅ Ｃｏｏｒｄｉｎａｔｅ Ｃａｃｈｅも同様に動作することができる。
【００６７】
＜ヒットポイント計算部１４０及びシェーディング部１５０＞
ヒットポイント計算部１４０は、Ｔ＆Ｉ部１３０から出力されてレイによってヒット（ｈｉｔ）された三角形との距離と与えられたレイのベクトル値を用いてレイ−三角形ヒットポイントの座標値を計算する。レイ−三角形ヒットポイントはレイ当たり１つだけ発生するので、ヒットポイント計算部１４０は１つのパイプラインで具現できる。一実施例において、費用効率を考慮すれば、ヒットポイント計算部１４０はＴ＆Ｉ部１３０に具現できる。
【００６８】
シェーディング部１５０は物質メモリ（ｍａｔｅｒｉａｌ ｍｅｍｏｒｙ）１９５ｃと三角形情報キャッシュ（ｔｒｉａｎｇｌｅ ｉｎｆｏｒｍａｔｉｏｎ ｃａｃｈｅ）１８０に格納された情報を用いてレイ−三角形ヒットポイントのカラー値を計算する。物質メモリ１９５ｃは幾何学的データ格納部１２００にある三角形に関する物質情報を格納し、一実施例において、物質情報はテクスチャインデックス（ｔｅｘｔｕｒｅ ｉｎｄｅｘ）、環境定数（ａｍｂｉｅｎｔ ｃｏｎｓｔａｎｔ）、分散定数（ｄｉｆｆｕｓｅ ｃｏｎｓｔａｎｔ）、反射定数（ｓｐｅｃｕｌａｒ ｃｏｎｓｔａｎｔ）、屈折率（ｒｅｆｒａｃｔｉｏｎ ｒａｔｅ）（つまり、アルファ値）、屈折角（ｒｅｆｒａｃｔｉｏｎ ａｎｇｌｅ）などを含むことができる。三角形情報キャッシュ１８０は幾何学的データ格納部１２００のキャッシュで、シェーディング段階で要求される該当の三角形に対する三角形情報を格納し、三角形情報は物質メモリ１９５ｃの参照のための物質インデックス（ｍａｔｅｒｉａｌ ｉｎｄｅｘ）をさらに含むことができる。
【００６９】
シェーディング部１５０は、フォーン照明とテクスチャマッピングによってレイ−三角形ヒットポイントのカラー値を計算することができ、計算されたカラー値をシェーディングバッファ１８５ｅにある以前のカラーに計算されたカラーを加え、加えられたカラー値をシェーディングバッファ１８５ｅに格納する。シェーディングバッファ１８５ｅは与えられたピクセルから生成されたアイレイ、シャドーレイまたは派生レイによって累積したカラー値とシェーディング情報を格納する。
【００７０】
シェーディング情報は現在のレイに対する派生レイが生成されるか否かを決定するために使われる。シェーディング部１５０はヒットされた三角形に対する三角形情報に含まれた物質インデックスに基づいて物質メモリから物質情報（つまり、反射率と屈折率）を取り入れる。反射率が０に相応しない場合には、レイ生成部１２０は反射レイを生成することができ、屈折率が０に相応しない場合には、レイ生成部１２０は屈折レイを生成することができる。また、レイ生成部１２０は光源（ｌｉｇｈｔ ｓｏｕｒｃｅ）に対するシャドーレイを生成することができる。シェーディング部１５０はレイ−三角形ヒットポイントの座標値とカラー値及びシェーディングレイタイプを含むシェーディング情報をセットアッププロセッシング部１１０に伝送する。
【００７１】
一実施例において、フォーン照明は［ＨＡＲＲＩＳ， Ｄ． ２００４ Ａｎ ｅｘｐｏｎｅｎｔｉａｔｉｏｎ ｕｎｉｔ ｆｏｒ ａｎ ｏｐｅｎｇｌ ｌｉｇｈｔｉｎｇ ｅｎｇｉｎｅ． ＩＥＥＥＴ ｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｃｏｍｐｕｔｅｒｓ］にある構造を使うことができ、テクスチャマッピングはバイリニアフィルタリング構造（ｂｉｌｉｎｅａｒ ｆｉｌｔｅｒｉｎｇ ｓｃｈｅｍｅ）を支援し［ＨＡＫＵＲＡ， Ｚ． Ｓ．， ＡＮＤ ＧＵＰＴＡ， Ａ． １９９７． Ｔｈｅ ｄｅｓｉｇｎ ａｎｄ ａｎａｌｙｓｉｓ ｏｆ ａｃａｃｈｅ ａｒｃｈｉｔｅｃｔｕｒｅ ｆｏｒ ｔｅｘｔｕｒｅ ｍａｐｐｉｎｇ． ＳＩＧＡＲＣＨ Ｃｏｍｐｕｔｅｒ Ａｒｃｈｉｔｅｃｔｕｒｅ Ｎｅｗｓ］に開示されたキャッシュ構造を選択した。
【００７２】
図１０は図１のレイトレーシングコアが含まれたレイトレーシングボード（ｒａｙ ｔｒａｃｉｎｇ ｂｏａｒｄ）を説明する図である。
【００７３】
図１０を参照すれば、レイトレーシングボード２０００は、第１〜第２レイトレーシングサブボード２０１０ａ〜２０１０ｂを含み、第１レイトレーシングサブボード２０１０ａはレイトレーシングチップ２０２０ａ〜２０２０ｂを含み、第２レイトレーシングサブボード２０１０ｂはレイトレーシングチップ２０２０ｃ〜２０２０ｄを含む。
【００７４】
レイトレーシングコア２０２０は図１のレイトレーシングコア１００と実質的に同一であるので、その相違点を主に説明する。
【００７５】
ホストコンピュータの中央処理装置（ＣＰＵ）は場面管理ソフトウェア（Ｓｃｅｎｅ Ｍａｎａｇｅｍｅｎｔ Ｓｏｆｔｗａｒｅ）２００５を実行し、場面管理ソフトウェア２００５は加速構造（ＡＳ）を構築し、ＵＳＢインターフェースとＢＦＭ（Ｂｕｓ Ｆｕｎｃｔｉｏｎａｌ Ｍｏｄｅｌ）を介して加速構造（ＡＳ）、幾何学的データ、テクスチャデータをレイトレーシングチップ２０２０のそれぞれにあるメモリ（ＤＲＡＭ）２０３０ａ〜２０３０ｄに伝送する。その後、レイトレーシングコア２０２０は実行し始める。
【００７６】
第１レイトレーシングチップ２０１０ａはマスターとして動作する。第１レイトレーシングチップ２０１０ａにあるＸＹ生成器２０４０は適切なレイトレーシングコア（例えば、ひまなレイトレーシングチップ）２０２０にブロック住所（つまり、イメージの一部ブロック）を伝送する。ＸＹ生成器２０４０によって選択されたレイトレーシングコア２０２０はブロック住所を受けた後、所定のピクセルブロックに対してレンダリングを遂行する。例えば、所定のピクセルブロックは１６×１６ピクセルブロックに相応することができる。レンダリング完了の後、レイトレーシングコア２０２０はＸＹ生成器２０４０に次のブロック住所を要求することができる。レイトレーシングコア２０２０のそれぞれで生成された最終カラー値はＳＲＡＭ ＆ ＬＣＤ制御器２０５０によってＳＲＡＭ２０６０に格納される。
【００７７】
本発明は次の効果を持つことができる。ただ、特定の実施例が次の効果を全部含まなければならないかあるいは次の効果のみを含まなければならないという意味ではないので、本発明の権利範囲はこれによって制限されるものに理解されてはいけないであろう。
【００７８】
一実施例によるレイトレーシングコアは、レイトレーシングの効率的処理のためのＭＩＭＤ（Ｍｕｌｔｉｐｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ）並列構造を支援することができる。
【００７９】
一実施例によるレイトレーシングコアは、加速構造（ＡＳ）に適切に統合されたパイプライン構造を採択して、レイトレーシングで使われるレイ−ボックス交差、訪問、レイ−三角形交差テストを効率よく遂行することができる。
【００８０】
以上、本発明の好適な実施例を参照して説明したが、当該技術分野の熟練した当業者は下記の特許請求の範囲に記載された本発明の思想及び領域から逸脱しない範囲内で本発明を多様に修正及び変更することができることが理解可能であろう。
【符号の説明】
【００８１】
１００ レイトレーシングコア
１１０ セットアッププロセッシング部
１２０ レイ生成部
１３０ Ｔ＆Ｉ部
１４０ ヒットポイント計算部
１５０ シェーディング部
１６０ 制御部
１６５ レジスタ
１７０ Ｌ１キャッシュ
１７５ Ｌ２キャッシュ
１８０ キャッシュ
１８５ バッファ
１９０ スタック
１９５ メモリ
２０００ レイトレーシングボード
【技術分野】
【０００１】
本発明は３Ｄグラフィック処理に係り、特にレイトレーシングコア及びこれを含むレイトレーシングチップに関するのである。
【背景技術】
【０００２】
３次元グラフィック技術はコンピュータに格納された幾何学的データ（ｇｅｏｍｅｔｒｉｃ ｄａｔａ）の３次元表現を使うグラフィック技術で、今日メディア産業とゲーム産業を含む多様な産業で広く使われている。一般に、３次元グラフィック技術は多くの演算量によって別個の高性能グラフィックプロセッサを要求する。
【０００３】
特に、近年プロセッサの発展によって非常に現実的な３次元グラフィックを生成することができるレイトレーシング（ｒａｙ ｔｒａｃｉｎｇ）技術が研究されている。特に、レイトレーシング技術は、反射、屈折、陰影を含む多様な光効果（ｏｐｔｉｃａｌ ｅｆｆｅｃｔｓ）をシミュレーションすることができる。
【図面の簡単な説明】
【０００４】
【図１】本発明の一実施例によるレイトレーシングコア（ｒａｙ ｔｒａｃｉｎｇ ｃｏｒｅ）を説明するブロック図である。
【図２】レイトレーシング過程を説明するための図である。
【図３】レイトレーシング過程を説明するための図である。
【図４】図１のセットアッププロセッシング部によるブロック基盤のレイの生成手順とこれを具現するハードウェアを説明するための図である。
【図５】図１の複数のＴ＆Ｉ部を説明するためのブロック図である。
【図６】図５のＴ＆Ｉパイプライン部を説明するための図である。
【図７】図５のＴ＆Ｉパイプライン部を説明するための図である。
【図８】図１のＴ＆Ｉ部のメモリシステムを説明するための図である。
【図９】図１のレイトレーシングチップで使われる加速構造と幾何学的データを説明するための図である。
【図１０】図１のレイトレーシングコアが含まれたレイトレーシングボード（ｒａｙ ｔｒａｃｉｎｇ ｂｏａｒｄ）を説明する図である。
【発明を実施するための形態】
【０００５】
実施例において、レイトレーシングコア（Ｒａｙ ｔｒａｃｉｎｇ ｃｏｒｅ）はスクリーン座標値を含むアイレイの生成情報に基づいて少なくとも１つのアイレイを生成するレイ生成部及び前記少なくとも１つのアイレイをそれぞれ入力され、加速構造（ＡＳ；Ａｃｃｅｌａｒａｔｉｏｎ Ｓｔｒｕｃｔｕｒｅ）において前記入力されたアイレイと交差する三角形（前記三角形は空間を構成する）があるか否かをそれぞれチェックするＭＩＭＤ構造（Ｍｕｌｔｉｐｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ Ａｒｃｈｉｔｅｃｔｕｒｅ）を持つ複数のＴ＆Ｉ部（ａ ｐｌｕｒａｌｉｔｙ ｏｆ Ｔｒａｖｅｒｓａｌ ＆ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｕｎｉｔｓ）を含む。
【０００６】
実施例において、レイトレーシングコア（Ｒａｙ ｔｒａｃｉｎｇ ｃｏｒｅ）はアイレイの生成情報（ｅｙｅ ｒａｙ ｇｅｎｅｒａｔｉｏｎ ｉｎｆｏｒｍａｔｉｏｎ）またはシェーディング情報（ｓｈａｄｉｎｇ ｉｎｆｏｒｍａｔｉｏｎ）（レイ−三角形ヒットポイントの座標値とカラー値及びシェーディングレイタイプを含む）の１つをマルチプレックシングするセットアッププロセッシング部、前記アイレイの生成情報またはシェーディング情報に基づいて少なくとも１つのアイレイまたはシェーディングレイを生成するかあるいは最終カラー値を決定するレイ生成部、及びＭＩＭＤ構造（Ｍｕｌｔｉｐｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ Ａｒｃｈｉｔｅｃｔｕｒｅ）を採択し、加速構造（ＡＳ；Ａｃｃｅｌｅｒａｔｉｏｎ Ｓｔｒｕｃｔｕｒｅ）において前記生成された少なくとも１つのアイレイまたはシェーディングレイと交差する三角形（前記三角形は空間を構成する）をそれぞれ決定する複数のＴ＆Ｉ部（ａ ｐｌｕｒａｌｉｔｙ ｏｆ Ｔｒａｖｅｒｓａｌ ＆ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｕｎｉｔｓ）を含む。
【０００７】
実施例において、レイトレーシングチップ（ｒａｙ ｔｒａｃｉｎｇ ｃｈｉｐ）は、複数のレイトレーシングコア、前記複数のレイトレーシングコアの中で適切なレイトレーシングコアにイメージの一部ブロックを割り当てるＸＹ生成器、及び前記複数のレイトレーシングコアのそれぞれから出力された最終カラー値を格納するメモリを含む。前記複数のレイトレーシングコアのそれぞれは、スクリーン座標値を含むアイレイの生成情報に基づいて少なくとも１つのアイレイを生成するレイ生成部、及び前記少なくとも１つのアイレイをそれぞれ入力され、加速構造（ＡＳ；Ａｃｃｅｌａｒａｔｉｏｎ Ｓｔｒｕｃｔｕｒｅ）において前記入力されたアイレイと交差する三角形（前記三角形は空間を構成する）があるか否かをそれぞれチェックするＭＩＭＤ構造（Ｍｕｌｔｉｐｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ Ａｒｃｈｉｔｅｃｔｕｒｅ）を持つ複数のＴ＆Ｉ部（ａ ｐｌｕｒａｌｉｔｙ ｏｆ Ｔｒａｖｅｒｓａｌ ＆ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｕｎｉｔｓ）を含む。
【０００８】
実施例において、レイトレーシングチップ（ｒａｙ ｔｒａｃｉｎｇ ｃｈｉｐ）は、複数のレイトレーシングコア、前記複数のレイトレーシングコアの中で適切なレイトレーシングコアにイメージの一部ブロックを割り当てるＸＹ生成器、及び前記複数のレイトレーシングコアのそれぞれから出力された最終カラー値を格納するメモリを含む。前記複数のレイトレーシングコアのそれぞれは、アイレイの生成情報（ｅｙｅ ｒａｙ ｇｅｎｅｒａｔｉｏｎ ｉｎｆｏｒｍａｔｉｏｎ）またはシェーディング情報（ｓｈａｄｉｎｇ ｉｎｆｏｒｍａｔｉｏｎ）（レイ−三角形ヒットポイントの座標値とカラー値及びシェーディングレイタイプを含む）の１つをマルチプレックシングするセットアッププロセッシング部、前記アイレイの生成情報またはシェーディング情報に基づいて少なくとも１つのアイレイまたはシェーディングレイを生成するかまたは最終カラー値を決定するレイ生成部、及びＭＩＭＤ構造（Ｍｕｌｔｉｐｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ Ａｒｃｈｉｔｅｃｔｕｒｅ）を採択し、加速構造（ＡＳ；Ａｃｃｅｌｅｒａｔｉｏｎ Ｓｔｒｕｃｔｕｒｅ）において前記生成された少なくとも１つのアイレイまたはシェーディングレイと交差する三角形（前記三角形は空間を構成する）をそれぞれ決定する複数のＴ＆Ｉ部（ａ ｐｌｕｒａｌｉｔｙ ｏｆ Ｔｒａｖｅｒｓａｌ ＆ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｕｎｉｔｓ）を含む。
【０００９】
本発明についての説明は構造的ないし機能的説明のための実施例に過ぎないので、本発明の権利範囲はこの明細書に説明された実施例によって制限されるものに解釈されてはいけない。すなわち、実施例は多様な変更が可能であり、さまざまな形態を持つことができるので、本発明の権利範囲は技術的思想を実現することができる均等物を含むものに理解されなければならない。
【００１０】
一方、本明細書に敍述される用語の意味は次のように理解されるべきであろう。
【００１１】
“第１”、“第２”などの用語は一構成要素を他の構成要素から区別するためのもので、これら用語によって権利範囲が限定されてはいけない。例えば、第１構成要素は第２構成要素に命名されることができ、同様に第２構成要素も第１構成要素に命名されることができる。
【００１２】
“及び／または”の用語は１つ以上の関連項目から提示可能なすべての組合せを含むものに理解されなければならない。例えば、“第１項目、第２項目及び／または第３項目”の意味は第１、第２または第３項目だけでなく、第１項目、第２項目または第３項目の中で２個以上から提示可能なすべての項目の組合せを意味する。
【００１３】
ある構成要素が他の構成要素に“連結されて”いると言及されたときには、その他の構成要素に直接連結されることもできるが、中間に他の構成要素が存在することもできると理解されなければならないであろう。一方、ある構成要素が他の構成要素に“直接連結されて”いると言及されたときには、中間に他の構成要素が存在しないものに理解されなければならないであろう。一方、構成要素間の関係を説明する他の表現、つまり“〜の間に”と“すぐ〜の間に”または“〜に隣り合う”と“〜に直接隣り合う”なども同様に解釈されなければならない。
【００１４】
単数の表現は文脈上明白に異なるように意味しない限り複数の表現を含むものに理解されなければならなく、“含む”または“持つ”などの用語は説示された特徴、数字、段階、動作、構成要素、部分品またはこれらを組み合わせたものが存在することを指定しようとするものであるばかり、１つまたはそれ以上の他の特徴、あるいは数字、段階、動作、構成要素、部分品またはこれらを組み合わせたものなどの存在または付加可能性を予め排除しないものに理解されなければならない。
【００１５】
各段階は文脈上明白に特定の手順を記載しない限り、明記された手順とは異なるように起こることができる。すなわち、各段階は明記された手順と同様に起こることもでき、実質的に同時に遂行されることもでき、反対の順に遂行されることもできる。
【００１６】
ここで使われるすべての用語は他の意味に定義されない限り、本発明が属する分野で通常の知識を持った者によって一般的に理解されるものと同一意味を持つ。一般的に使われる前もって定義されている用語は関連技術の文脈で有する意味と一致するものに解釈されなければならなく、本明細書で明白に定義しない限り、理想的にあるいは過度に形式的な意味を持つものに解釈されることができない。
【００１７】
図１は本発明の一実施例によるレイトレーシングコア（ｒａｙ ｔｒａｃｉｎｇ ｃｏｒｅ）を説明するブロック図である。
【００１８】
図１を参照すれば、レイトレーシングコア１００は、データパス部（ｄａｔａ ｐａｔｈｐａｒｔ）とメモリシステム部（ｍｅｍｏｒｙ ｓｙｓｔｅｍ ｐａｒｔ）に大別される。一実施例において、レイトレーシングコア１００はグラフィックプロセッサのようなチップに含まれることができ、他の一実施例において、レイトレーシングコア１００は単一チップとして具現されることができる。
【００１９】
データパス部は、セットアッププロセッシング部（ｓｅｔｕｐ ｐｒｏｃｅｓｓｉｎｇ ｕｎｉｔ）１１０、レイ生成部（ｒａｙ ｇｅｎｅｒａｔｉｏｎ ｕｎｉｔ）１２０、複数のＴ＆Ｉ部（Ｔｒａｖｅｒｓａｌ ＆ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｕｎｉｔ）１３０、ヒットポイント計算部（Ｈｉｔ Ｐｏｉｎｔ Ｃａｌｃｕｌａｔｉｏｎ Ｕｎｉｔ）１４０、シェーディング部（Ｓｈａｄｉｎｇ Ｕｎｉｔ）１５０及び制御部１６０を含む。メモリシステム部は、レジスタ（Ｒｅｇｉｓｔｅｒ）１６５、Ｌ１キャッシュ（Ｃａｃｈｅ）１７０、Ｌ２キャッシュ１７５、キャッシュ１８０、バッファ（Ｂｕｆｆｅｒ）１８５、スタック１９０、及びメモリ（Ｍｅｍｏｒｙ）１９５を含む。便宜上、図１のメモリシステム部の構成要素のそれぞれは別に具現されるものとして説明したが、必要によって構成要素の中で少なくとも一部は物理的に同等なメモリで具現できる。
【００２０】
また、レイトレーシングチップ１００は外部メモリ（Ｅｘｔｅｒｎａｌ Ｍｅｍｏｒｙ）１０００と連結されることができ、外部メモリ１０００は加速構造（ＡＳ；Ａｃｃｅｌｅｒａｔｉｏｎ Ｓｔｒｕｃｔｕｒｅ）格納部１１００、幾何学的データ（Ｇｅｏｍｅｔｒｙ Ｄａｔａ）格納部１２００、テクスチャイメージ（Ｔｅｘｔｕｒｅ Ｉｍａｇｅ）格納部１３００、及びフレーム（Ｆｒａｍｅ）格納部１４００を含む。
【００２１】
加速構造（ＡＳ）はレイトレーシングに一般的に使われるｋｄ−ｔｒｅｅ（ｋ−ｄｅｐｔｈ ｔｒｅｅ）またはＢＶＨ（Ｂｏｕｎｄｉｎｇ Ｖｏｌｕｍｅ Ｈｉｅｒａｒｃｈｙ）を含み、幾何学的データはレイトレーシングのための三角形に関する情報（以下、三角形情報）を含む。一実施例において、三角形情報は三角形の三点に対するテクスチャ座標（ｔｅｘｔｕｒｅ ｃｏｏｒｄｉｎａｔｅ）と法線ベクトル（ｎｏｒｍａｌ ｖｅｃｔｏｒ）を含むことができる。
【００２２】
図９は図１のレイトレーシングチップで使われる加速構造と幾何学的データの関係を説明するための図である。
【００２３】
図９において、加速構造（ＡＳ）はｋｄ−ｔｒｅｅを使うと仮定した。ｋｄ−ｔｒｅｅは空間分割ツリー（ｓｐａｔｉａｌ ｐａｒｔｉｔｉｏｎｉｎｇ ｔｒｅｅ）の一種で、レイ−三角形交差テスト（Ｒａｙ−Ｔｒｉａｎｇｌｅ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｔｅｓｔ）のために使われる。ｋｄ−ｔｒｅｅはボックスノード（Ｂｏｘ Ｎｏｄｅ）９１０、内部ノード（Ｉｎｎｅｒ Ｎｏｄｅ）９２０、及びリーフノード（ｌｅａｆ ｎｏｄｅ）９３０を含み、リーフノード９３０は幾何学的データに含まれた少なくとも１つの三角形情報をポインティングするための三角形リストを含む。一実施例において、幾何学的データに含まれた三角形情報が配列で具現された場合には、リーフノード９３０に含まれた三角形リストは配列インデックスに相応することができる。
【００２４】
図２及び図３はレイトレーシング過程を説明するための図である。図１〜図３を参照してレイトレーシングコア１００の全体的な動作を説明する。
【００２５】
セットアッププロセッシング部１１０はアイレイの生成情報（ｅｙｅ ｒａｙ ｇｅｎｅｒａｔｉｏｎ ｉｎｆｏｒｍａｔｉｏｎ）を準備し、準備されたアイレイの生成情報とシェーディング部１５０から出力されたシェーディング情報を選択する。アイレイの生成情報はアイレイの生成のためのスクリーン座標値を含む。シェーディング情報（ｓｈａｄｉｎｇ ｉｎｆｏｒｍａｔｉｏｎ）はスクリーン座標値を求めるためのレイインデックス（後述する）、レイ−三角形ヒットポイント（ｒａｙ−ｔｒｉａｎｇｌｅ ｈｉｔ ｐｏｉｎｔ）（後述する）の座標値とカラー値、及びシェーディングレイタイプを含み、シェーディングレイタイプによる付加情報をさらに含むことができる。シェーディングレイ（ｓｈａｄｉｎｇ ｒａｙ）はシャドーレイ（ｓｈａｄｏｗ ｒａｙ）、派生レイ（ｓｅｃｏｎｄａｒｙ ｒａｙ）またはナルレイ（ＮＵＬＬ ｒａｙ）を含み、派生レイは屈折レイ（ｒｅｆｒａｃｔｉｏｎ ｒａｙ）または反射レイ（ｒｅｆｌｅｃｔｉｏｎ ｒａｙ）を含む。屈折レイの場合、付加情報はレイ−三角形ヒットポイントの屈折率を含み、反射レイの場合、付加情報はレイ−三角形ヒットポイントの反射率をさらに含む。セットアッププロセッシング部１１０の動作方式は図４を参照して後述する。
【００２６】
レイ生成部１２０はアイレイの生成情報またはシェーディング情報に基づいて少なくとも１つのレイを生成することができる（段階Ｓ３１０またはＳ３４０）。図２に示すように、少なくとも１つのレイはアイレイＥ、シャドーレイＳ、屈折レイＦ、及び／または反射レイＲを含むことができる。生成された派生レイの個数が２以上の場合には、１つはＴ＆Ｉ部１３０に出力され、残りは派生レイスタック１９０に格納される。派生レイの場合、レイ生成部１２０は反射レイＲのヒットポイントまたは屈折レイＦのヒットポイントを考慮する必要があるからである。例えば、反射レイＦと屈折レイＲの両方が生成される場合には、反射レイＦはＴ＆Ｉ部１３０に出力されることができ、屈折レイＲは派生レイスタック１９０に格納されることができる。
【００２７】
シェーディングレイタイプがナルレイに相応する場合には、レイ生成部１２０は派生レイスタック１９０に格納された派生レイを取り入れ、取り出された派生レイをＴ＆Ｉ部１３０に出力する。シェーディングレイスタック１９０が空いている場合には、レイ生成部１２０はレイインデックス（後述する）に基づいてスクリーン座標値を収得し、スクリーン座標値とレイ−三角形ヒットポイント（後述する）のカラー値に基づいて最終カラー値をカラーバッファ１８５ｃに使う。
【００２８】
複数のＴ＆Ｉ部１３０は並列のＭＩＭＤ（Ｍｕｌｔｉｐｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ）構造を採択し、複数のＴ＆Ｉ部１３０のそれぞれはレイ生成部１２０から生成されたレイ（アイレイ、シャドーレイまたは派生レイ）を入力され、加速構造（ＡＳ；Ａｃｃｅｌａｒａｔｉｏｎ Ｓｔｒｕｃｔｕｒｅ）においてレイと交差する三角形があるか否かをチェックする。すなわち、複数のＴ＆Ｉ部１３０のそれぞれは加速構造（ＡＳ）を訪問（ｔｒａｖｅｒｓｅ）し、三角形（ｔｒｉａｎｇｌｅｓ）に対する交差テスティング（ｉｎｔｅｒｓｅｃｔｉｏｎ ｔｅｓｔｉｎｇ）を遂行する。複数のＴ＆Ｉ部１３０の動作方式は図５〜図１１を参照して後述する。
【００２９】
ヒットポイント計算部１４０は交差する三角形（ｉｎｔｅｒｓｅｃｔｅｄ ｔｒｉａｎｇｌｅ）に対してレイ−三角形ヒットポイント（ｒａｙ−ｔｒｉａｎｇｌｅ ｈｉｔ ｐｏｉｎｔ）（つまり、交差する三角形においてレイがヒットされるポイント）の座標値を計算し、シェーディング部１５０はレイ−三角形ヒットポイントに対してカラー値を計算する。一実施例において、シェーディング部１５０はレイ−三角形ヒットポイントに対するカラー値を得るためにフォーン照明（ｐｈｏｎｇ ｉｌｌｕｍｉｎａｔｉｏｎ）とテクスチャマッピング（ｔｅｘｔｕｒｅ ｍａｐｐｉｎｇ）を遂行することができる（段階Ｓ３４０）。また、シェーディング部１５０はレイ生成部１２０による最終カラー値の決定またはシェーディングレイの生成のためのシェーディング情報を生成し、シェーディング情報をセットアッププロセッシング部１１０に伝送する。それ以上のレイの生成が必要でない場合には、シェーディングレイタイプはナルレイ（Ｎｕｌｌ Ｒａｙ）に相応することができる。一実施例において、シェーディング部１５０は物質メモリ１９５ｃに格納されたレイ−三角形ヒットポイントに関する物質情報に基づいて派生レイの生成を決定することができる。以下、データパスに含まれた構成要素のそれぞれを説明する。
【００３０】
＜パイプライン制御構造＞
レイトレーシングアルゴリズムは再帰的に遂行され、（ｉ）アイレイの生成過程（段階Ｓ３１０）、（ｉｉ）加速構造訪問（ＡＳ Ｔｒａｖｅｒｓａｌ）過程（段階Ｓ３２０）、（ｉｉｉ）レイ−三角形交差テスト（ｒａｙ−Ｔｒｉａｎｇｌｅ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｔｅｓｔ）過程（段階Ｓ３３０）、（ｉｖ）シェーディング及びシェーディングレイの生成過程（段階Ｓ３４０）を含む。したがって、レイトレーシングアルゴリズムは一般的なストリーミングパイプライン構造（ｓｔｒｅａｍｉｎｇ ｐｉｐｅｌｉｎｅ ａｒｃｈｉｔｅｃｔｕｒｅ）を使うことが適切でないこともある。
【００３１】
本発明はレイトレーシングアルゴリズムに適切なパイプライン構造を導入し、制御部１６０はパイプライン（レジスタ）１６５のフラッグ（ｆｌａｇ）を介してパイプラインの動作を制御する。すなわち、本発明は、パイプラインの効率を高めるために、フラッグ（ｆｌａｇ）基盤の単純な制御構造を使う。一実施例において、パイプラインのレジスタ１６５のフラッグはオンまたはオフのための１ビット情報に相応することができ、フラッグがオンに相応する場合、レジスタ１６５は以前のステージで出力された情報を格納することができる。結果として、パイプラインはフラッグによって同期的（ｓｙｎｃｈｒｏｎｏｕｓ）に処理できるが、データパスを構成する構成要素のそれぞれは非動機的（ａｓｙｎｃｈｒｏｎｏｕｓ）に結果を出力することができる。
【００３２】
必要によって、データパスを構成する構成要素のそれぞれはロード不均衡（ｌｏａｄ ｉｍｂａｌａｎｃｅ）による待機時間を減らすためにバッファ１８５を使うことができる。例えば、複数のＴ＆Ｉ部１３０のそれぞれは性能向上とＭＩＭＤ構造支援のためにバッファ１８５を使うことができる。
【００３３】
＜セットアッププロセッシング部１１０＞
セットアッププロセッシング部１１０はアイレイの生成情報を初期化させる。初期化過程は、スクリーン座標値を決定し、決定されたスクリーン座標値をレイインデックスに変換する過程を含む。レイインデックスはパイプラインの各段階でレジスタ１６５のサイズを減少させるために使われる。セットアッププロセッシング部１１０はスクリーン座標値とレイインデックスをレイ生成部１２０に伝送する。
【００３４】
セットアッププロセッシング部１１０はアイレイの生成情報またはシェーディング情報をマルチプレックシングする。一実施例において、シェーディング情報はアイレイの生成情報に対して優先権（ｐｒｉｏｒｉｔｙ）を持つことができる。以前のスクリーン座標値を持つピクセルで生成されたレイに対する処理が先に行われることが好ましいからである。
【００３５】
図４は図１のセットアッププロセッシング部によるブロック基盤のレイの生成手順とこれを具現するハードウェアを説明するための図である。
【００３６】
スクリーンは複数のｍ×ｎ（ｍとｎは偶数）ピクセルブロック（以下、スーパーブロック）を含み、各スーパーブロックは同じ大きさのＮ個（Ｎは複数のＴ＆Ｉ部１３０の個数）のピクセルブロック（以下、サブブロック）を含む。
【００３７】
セットアッププロセッシング部１１０は、複数のＴ＆Ｉ部１３０ｍｐそれぞれでキャッシュヒット率（ｃａｃｈｅ ｈｉｔ ｒａｔｅ）を増加させるために、スクリーンを複数のブロック（つまり、サブブロック）に分割し、各ブロック基盤のアイレイの生成手順を決定することができる。例えば、スクリーンは１６×１６ピクセルブロックでそれぞれ構成された複数のスーパーブロックを含むことができ、スーパーブロックのそれぞれは４個の８×８ピクセルブロックでそれぞれ構成されたサブブロックを含むことができる。第１〜第４ピクセルブロック４１０〜４４０のそれぞれは第１〜第４Ｔ＆Ｉ部１３０ａ〜１３０ｄに割り当てられることができる。
【００３８】
以下、第１サブブロック４１０は図４（ｂ）に示す８×８ピクセルブロックに相応し、第１Ｔ＆Ｉ部１３０ａに割り当てられたと仮定する。
【００３９】
セットアッププロセッシング部１１０は線形のｎ−ビットカウンター４５０を使って第１Ｔ＆Ｉ部１３０ａのキャッシュヒット率を増加させるためのレイの生成手順を決定することができる。線形のｎ−ビットカウンター４５０の第１グループ（第１グループは連続しない少なくとも１つのビットを含むことができる）はサブブロックのｘ座標値を示し、線形のｎ−ビットカウンター４５０の第２グループ（第２グループは第１グループに属したビットを含まなく、連続しない少なくとも１つのビットを含むことができる）はサブブロックのｙ座標値を示す。
【００４０】
レイ生成部１２０は、図４（ｂ）及び図４（ｃ）に示すように、セットアッププロセッシング部１１０によって決定されたアイレイの生成手順にレイを生成する。一方、図４（ｂ）に示すピクセル（例えば、ピクセル０）はレイの生成のためのピクセルを意味する。例えば、６４個のピクセルの場合、セットアッププロセッシング部１１０は線形の６−ビットカウンター４５０を含むことができ、線形の６−ビットカウンター４５０の値Ｉ＝ｉ５ｉ４ｉ３ｉ２ｉ１ｉｉ０の場合には、ピクセルの座標（ｘ，ｙ）＝（ｉ５ｉ３ｉ１，ｉ４ｉ２ｉ０）に相応することができる。すなわち、図４（ｃ）の線形の６−ビットカウンター４５０はカウント数が増加するにつれて図４（ｂ）のピクセル座標が易しくマッピングされるように具現される。
【００４１】
＜レイ生成部１２０＞
レイ生成部１２０はセットアッププロセッシング部１１０から伝送されたスクリーン座標値とレイインデックスをレイインデックスマッピングテーブル（１９５ａ）に格納し、アイレイの生成情報またはシェーディング情報に基づいて少なくとも１つのレイを生成するかあるいは最終カラー値をカラーバッファ１８５ａに格納する。
【００４２】
アイレイの生成情報が入力された場合には、レイ生成部１２０はアイレイＥを生成する。シェーディング情報が入力された場合には、レイ生成部１２０はシェーディングレイタイプによってシェーディングレイＳ、Ｒ、Ｆを生成し、シェーディングレイタイプがナルレイに相応する場合には、レイ生成部１２０は派生レイスタック１９０に格納された派生レイを取り入れる。派生レイスタック１９０が空いている場合には、レイ生成部１２０はレイインデックスに基づいてスクリーン座標値を求め、求められたスクリーン座標値とレイ−三角形ヒットポイント（後述する）のカラー値をカラーバッファ１８５ｃに格納する。以下、レイ生成部１２０がレイを生成する過程を説明する。
【００４３】
アイレイの生成において、レイ生成部１２０はレイインデックスマッピングテーブル（１９５ａ）を用いてアイレイのスクリーン座標値を求め、スクリーン座標値に基づいてアイレイＥを生成する。一般に、アイレイはスクリーン座標値とカメラ位置（つまり、アイ位置）に基づいて生成できる。レイ生成部１２０は複数のＴ＆Ｉ部１３０の中で適切なＴ＆Ｉ部（例えば、１３０ａ）に生成されたアイレイを割り当てる。
【００４４】
シャドーレイの生成において、シェーディングレイタイプがシャドーレイに相応する場合には、レイ生成部１２０はレイ−三角形ヒットポイント（後述する）に基づいてシャドーレイを生成する。一般に、シャドーレイはスクリーン座標値と光位置（ｌｉｇｈｔ ｐｏｓｉｔｉｏｎ）に基づいて生成できる。一実施例において、演算量を減らすために、レイ生成部１２０は光源（ｌｉｇｈｔ ｓｏｕｒｃｅ）の数を制限することができる。
【００４５】
派生レイの生成において、シェーディングレイタイプが派生レイに相応する場合には、レイ生成部１２０は少なくとも１つの派生レイ（つまり、屈折レイ及び／または反射レイ）を生成する。派生レイの個数が２以上の場合には、レイ生成部１２０は１つを除いた派生レイを派生レイスタック１９０に格納する。レイ生成部１２０は複数のＴ＆Ｉ部１３０の中で適切なＴ＆Ｉ部（例えば、１３０ｂ）に格納されない派生レイを割り当てる。派生レイスタック１９０に格納された派生レイはスクリーン座標値、方向ベクトル値及びＲＧＢに対する加重値を含むことができる。一実施例において、演算量を減らすために、レイ生成部１２０はレイ深さ（ｒａｙ ｄｅｐｔｈ）を使って派生レイによる派生レイの無制限的な生成を防止することができる。
【００４６】
ナルレイの生成において、シェーディングレイタイプがナルレイに相応する場合には、レイ生成部１２０は派生レイスタック１９０に格納された派生レイを取り入れた後、複数のＴ＆Ｉ部１３０の中で適切なＴ＆Ｉ部（例えば、１３０ｃ）に取り入れた派生レイを割り当てる。派生レイスタック１９０が空いている場合には、レイ生成部１２０はレイインデックスに基づいてスクリーン座標値を求め、求められたスクリーン座標値とレイ−三角形ヒットポイント（後述する）のカラー値に基づいて最終カラー値をカラーバッファ１８５ｃに格納する。カラーバッファ１８５ｃに格納された最終カラー値は外部メモリ１０００に格納される。
【００４７】
＜Ｔ＆Ｉ部１３０＞
複数のＴ＆Ｉ部１３０は加速構造訪問（ＡＳ Ｔｒａｖｅｒｓａｌ）過程（段階Ｓ３２０）とレイ−三角形交差テスト（ｒａｙ−Ｔｒｉａｎｇｌｅ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｔｅｓｔ）過程を遂行する。
【００４８】
図５は図１の複数のＴ＆Ｉ部を説明するためのブロック図である。
【００４９】
図５を参照すれば、複数のＴ＆Ｉ部１３０のそれぞれはバッファ１８５、Ｌ１キャッシュ１７０及びＴ＆Ｉパイプライン部（Ｔｒａｖｅｒｓａｌ ＆ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｐｉｐｅｌｉｎｅ Ｕｎｉｔ）１３５を含む。
【００５０】
複数のＴ＆Ｉ部１３０はＴ＆Ｉパイプライン部１３５が独立的に実行されるＭＩＭＤ並列構造を採択する。周知のように、レイトレーシングアルゴリズムはＭＩＭＤ並列構造に適合するように各レイを独立的に処理することができる。ＳＩＭＤ（Ｓｉｎｇｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ）と比較し、ＭＩＭＤ並列構造はパイプラインをより効率よく使うことができる利点を持つ。
【００５１】
複数のＴ＆Ｉ部１３０のそれぞれは自体の入力バッファ１８５ａと出力バッファ１８５ｂを含む。同一ピクセルから生成されたレイ（アイレイ及びシェーディングレイ）は同一Ｔ＆Ｉ部１３０で処理されることが好ましいからである。また、複数のＴ＆Ｉ部１３０のそれぞれは自体のＬ１キャッシュ１７０を含む。ＭＩＭＤ構造は効率的なキャッシュメモリを要求するからである。
【００５２】
Ｔ＆Ｉパイプライン部１３５は、（ｉ）訪問（ｔｒａｖｅｒｓａｌ）過程、（ｉｉ）三角形リスト取り入れ（ｔｒｉａｎｇｌｅ ｌｉｓｔ ｆｅｔｃｈ）過程、及び（ｉｉｉ）レイ−三角形交差テスト（ｒａｙ−Ｔｒｉａｎｇｌｅ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｔｅｓｔ）過程を遂行する。加速構造（ＡＳ）はｋｄ−ｔｒｅｅに相応すると仮定した。
【００５３】
訪問過程において、Ｔ＆Ｉパイプライン部１３５は加速構造（ＡＳ）でノードを検索することで、レイと交差するリーフノード（ｌｅａｆ ｎｏｄｅ）を捜す。加速構造（ＡＳ）の訪問アルゴリズムは当業者によく知られているので、これについての説明は省略する。三角形リスト取り入れ過程で、Ｔ＆Ｉパイプライン部１３５は交差するリーフノードに含まれた三角形リストを読み取る。レイ−三角形交差テスト過程で、Ｔ＆Ｉパイプライン部１３５は三角形リストの座標情報を読み取り、与えられたレイに対して交差テストを遂行する。
【００５４】
図６及び図７は図５のＴ＆Ｉパイプライン部を説明するための図である。
【００５５】
［ＳＣＨＭＩＴＴＬＥＲ，Ｊ．， ＷＡＬＤ，Ｉ．， ＡＮＤ ＳＬＵＳＡＬＬＥＫ Ｐ． ２００２． Ｓａａｒｃｏｒ：ａ ｈａｒｄｗａｒｅ ａｒｃｈｉｔｅｃｔｕｒｅ ｆｏｒ ｒａｙ ｔｒａｃｉｎｇ． Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＳＩＧＧＲＡＰＨ／ＥＵＲＯＧＲＡＰＨＩＣＳ ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｇｒａｐｈｉｃｓ Ｈａｒｄｗａｒｅ］（以下、参照文献１）と［ＳＣＨＭＩＴＴＬＥＲ， Ｊ．， ＷＯＯＰ， Ｓ．， ＷＡＧＮＥＲ， Ｄ．， ＰＡＵＬ， Ｗ． Ｊ．， ＡＮＤ ＳＬＵＳＡＬＬＥＫ， Ｐ．， ２００４． Ｒｅａｌｔｉｍｅ ｒａｙ ｔｒａｃｉｎｇ ｏｆ ｄｙｎａｍｉｃ ｓｃｅｎｅｓ ｏｎ ａｎ ＦＰＧＡ ｃｈｉｐ． Ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＳＩＧＧＲＡＰＨ／ＥＵＲＯＧＲＡＰＨＩＣＳ ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｇｒａｐｈｉｃｓ Ｈａｒｄｗａｒｅ］（以下、参照文献２）にあるレイトレーシング構造は訪問（ｔｒａｖｅｒｓａｌ）と交差テスト（ｉｎｔｅｒｓｅｃｔｉｏｎ ｔｅｓｔ）のために別個のハードウェアを使う。しかし、図５のＴ＆Ｉパイプライン部１３５は訪問（ｔｒａｖｅｒｓａｌ）と交差テスト（ｉｎｔｅｒｓｅｃｔｉｏｎｔｅｓｔ）の間のロード不均衡（ｌｏａｄ ｉｍｂａｌａｎｃｅ）を引き起こさず、加速構造（ＡＳ）を効率よく支援するように統合されたパイプライン構造を採択した。すなわち、図７のＴ＆Ｉパイプライン部１３５は訪問（ｔｒａｖｅｒｓａｌ）と交差テスト（ｉｎｔｅｒｓｅｃｔｉｏｎ ｔｅｓｔ）の各段階で同一ハードウェアを使うことができる。以下、前記参照文献１と参照文献２との相違点を主に説明する。
【００５６】
図６及び図７において、加速構造（ＡＳ）はｋｄ−ｔｒｅｅに相応すると仮定した。図６はＴ＆Ｉパイプライン部１３５で行われる訪問過程及びレイ−三角形交差テスト過程で使われる演算器と演算器の個数を説明する。訪問過程は大別してレイ−ボックス交差テスト（Ｒａｙ−Ｂｏｘ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｔｅｓｔ）と訪問（Ｔｒａｖｅｒｓａｌ）を含む。図９において、ｋｄ−ｔｒｅｅのトップノード９１０はＢｏｘノードに相応するからである。パイプライン制御部７１０はＴ＆Ｉパイプライン部１３５内のパイプラインを制御する。
【００５７】
レイ−ボックス交差テスト、訪問及びレイ−三角形交差テストにおける演算過程はＭＯＬＬＥＲ， Ｔ．， ＡＮＤ ＴＲＵＭＢＯＲＥ， Ｂ． １９９７ Ｆａｓｔ， ｍｉｎｉｍｕｍ ｓｔｏｒａｇｅ ｒａｙ−ｔｒｉａｎｇｌｅ ｉｎｔｅｒｓｅｃｔｉｏｎ， Ｊｏｕｒｎａｌ ｏｆ Ｇｒａｐｈｉｃｓ Ｔｏｏｌｓによく開示されているので、これについての説明は省略する。
【００５８】
図６に示すように、レイ−ボックス交差テストで順次必要な演算器は６個のフローティングポイント加算器（ＦＡＤＤ， Ｆｌｏａｔｉｎｇ Ｐｏｉｎｔ Ａｄｄｅｒ）、６個のフローティングポイント乗算器（ＦＭＵＬ， Ｆｌｏａｔｉｎｇ Ｐｏｉｎｔ Ｍｕｌｔｉｐｌｉｅｒ）、３個の第１フローティングポイント比較器（ＦＣＯＭＰ， Ｆｌｏａｔｉｎｇ Ｐｏｉｎｔ Ｃｏｍｐａｒａｔｏｒ）、２個の第２フローティングポイント比較器（ＦＣＯＭＰ）、及び１個の第３フローティングポイント比較器（ＦＣＯＭＰ）を含む。
【００５９】
図６に示すように、訪問において順次必要な演算器は１個のフローティングポイント加算器（ＦＡＤＤ）、１個のフローティングポイント乗算器（ＦＭＵＬ）、及び２個のフローティングポイント比較器（ＦＣＯＭＰ）を含む。また、訪問において順次必要な演算はスタックメモリ（１８５ｄ）へのスタック書き込み及びスタック読み取りを含む。
【００６０】
図６に示すように、レイ−三角形交差テストで順次必要な演算器は、９個の第１フローティングポイント加算器（ＦＡＤＤ）、１２個の第１フローティングポイント乗算器（ＦＭＵＬ）、６個の第２フローティングポイント加算器（ＦＡＤＤ）、１２個の第２フローティングポイント乗算器（ＦＭＵＬ）、４個のトリプル入力フローティングポイント加算器（ＴＦＡＤＤ， Ｔｒｉｐｐｌｅ Ｉｎｐｕｔ ＦＡＤＤ）、１個のフローティングポイント加算器（ＦＡＤＤ）、フローティングポイント除算器（ＦＤＩＶ）、及び２個のフローティングポイント比較器（ＦＣＯＭＰ）を含む。レイ−三角形交差テストは与えられたレイによって交差する最も近接した三角形と目の位置（またはカメラの位置）との交差点の間の距離を計算する。交差した三角形が存在する場合には、交差した三角形に関する情報はヒットポイント計算部１４０に伝送され、そうではない場合には、次の訪問段階が遂行される。一実施例において、レイ−三角形交差テストはＭＯＬＬＥＲ， Ｔ．， ＡＮＤ ＴＲＵＭＢＯＲＥ， Ｂ． １９９７． Ｆａｓｔ， ｍｉｎｉｍｕｍ ｓｔｏｒａｇｅ ｒａｙ−ｔｒｉａｎｇｌｅ ｉｎｔｅｒｓｅｃｔｉｏｎ． Ｊｏｕｒｎａｌ ｏｆ Ｇｒａｐｈｉｃｓ Ｔｏｏｌｓに開示されたアルゴリズムを用いることができる。
【００６１】
図７は訪問過程、三角形リスト取り入れ過程及びレイ−三角形交差テスト過程を遂行するためのＴ＆Ｉパイプライン部１３５の構成を説明する。図７のＴ＆Ｉパイプライン部１３５は統合された１つのパイプラインを使って図６のパイプラインの順に訪問過程、三角形取り入れ過程及びレイ−三角形交差テスト過程を遂行するようにパイプラインを構成する。すなわち、図７の７１０に含まれたパイプライン段階は訪問過程及びレイ−三角形交差テスト過程を遂行し、その以外の段階はキャッシュ接近または三角形リスト取り入れ段階を遂行する。図７に示すように、本発明は動作モードによって別個のハードウェアを使わずに統合されたパイプライン構造を採択する。
【００６２】
＜Ｔ＆Ｉ部１３０のメモリシステム＞
図８は図１のＴ＆Ｉ部のメモリシステムを説明するための図である。
【００６３】
Ｔ＆Ｉ部１３０においてメモリ接近はレイトレーシングでの全体メモリ接近の絶対的多数を占めるので、Ｔ＆Ｉ部１３０のメモリシステムは効率よくデザインされる必要がある。図１及び図５に示すように、複数のＴ＆Ｉ部１３０のそれぞれは３個のＬ１キャッシュを含み、共通のＬ２キャッシュを使う。キャッシュメモリの二重構造（ｔｗｏ−ｌｅｖｅｌ ｈｉｅｒａｒｃｈｙ）にもかかわらず、キャッシュミス（ｃａｃｈｅ ｍｉｓｓ）によるパイプラインストール時間（ｐｉｐｅｌｉｎｅ ｓｔａｌｌ ｔｉｍｅ）は依然として大きい。したがって、本発明はこれを解決するために次の２方案を使う。
【００６４】
第１方案はＬ１キャッシュミスに関するもので、Ｌ１キャッシュミスが発生した場合、Ｌ１キャッシュミスが次のループで解決されるように、Ｌ１キャッシュミスをストール（ｓｔａｌｌ）なしに飛ばすものである。図５において、パイプラインＰ１でキャッシュミスが発生した場合、パイプライン制御部７１０は次の段階のパイプラインＰ２にストールなしに続いて進む。キャッシュ制御部（図示せず）は、パイプラインＰ１の再処理のために、Ｌ２キャッシュ１７５または外部メモリ１０００からミスされたデータを取り入れる。パイプラインＰ１８の後にさらにパイプラインＰ１が再び進めば、Ｌ１キャッシュに対する接近が発生する。キャッシュミスが解決されれば、パイプライン制御部７１０は次の段階のパイプラインＰ２を正常に処理し、キャッシュミスがまた発生すれば、パイプライン制御部７１０はキャッシュミスが解決されるまで前記過程を繰り返す。結果として、キャッシュミスによるキャッシュミスペナルティはよほど緩和できる。
【００６５】
第２方案はＬ２キャッシュミスに関するもので、Ｌ２キャッシュミスが発生した場合、Ｌ２キャッシュミスをストールなしに飛ばすものである。現在のレイに対してＬ１キャッシュミスが発生した場合には、Ｌ２キャッシュ接近のための要求がＬ１ Ａｄｄｒ ＦＩＦＯ８１０に入力される。Ｌ１ Ａｄｄｒ ＦＩＦＯ８１０にある現在レイの要求によるＬ２キャッシュ接近がキャッシュヒットであると結論付けられれば、要求に対する住所とデータはＬ１ Ａｄｄｒ／Ｄａｔａ ＦＩＦＯ８２０に入力される。そうではない場合には、外部メモリ１０００に対する他の要求がＬ２ Ａｄｄｒ ＦＩＦＯ８１０に入力され、Ｌ１ Ａｄｄｒ ＦＩＦＯ６１０にある現在レイの要求は削除される。削除された要求に対するキャッシュ接近は次のループで再び発生する。次のループで発生したキャッシュ接近が発生すれば、前述した過程が繰り返される。前記過程はキャッシュ接近がヒットであると結論付けられるまで繰り返される。したがって、現在レイの要求によるＬ２キャッシュ接近でキャッシュミスが発生した場合であっても次のレイの要求によるＬ２キャッシュ接近は許容される。結果として、キャッシュミスによるキャッシュミスペナルティはよほど緩和できる。
【００６６】
図８はＮｏｄｅ Ｌ１ Ｃａｃｈｅ１７０を例としてあげたが、Ｌ１ Ｌｉｓｔ ＣａｃｈｅとＬ１ Ｔｒａｎｇｌｅ Ｃｏｏｒｄｉｎａｔｅ Ｃａｃｈｅも同様に動作することができる。
【００６７】
＜ヒットポイント計算部１４０及びシェーディング部１５０＞
ヒットポイント計算部１４０は、Ｔ＆Ｉ部１３０から出力されてレイによってヒット（ｈｉｔ）された三角形との距離と与えられたレイのベクトル値を用いてレイ−三角形ヒットポイントの座標値を計算する。レイ−三角形ヒットポイントはレイ当たり１つだけ発生するので、ヒットポイント計算部１４０は１つのパイプラインで具現できる。一実施例において、費用効率を考慮すれば、ヒットポイント計算部１４０はＴ＆Ｉ部１３０に具現できる。
【００６８】
シェーディング部１５０は物質メモリ（ｍａｔｅｒｉａｌ ｍｅｍｏｒｙ）１９５ｃと三角形情報キャッシュ（ｔｒｉａｎｇｌｅ ｉｎｆｏｒｍａｔｉｏｎ ｃａｃｈｅ）１８０に格納された情報を用いてレイ−三角形ヒットポイントのカラー値を計算する。物質メモリ１９５ｃは幾何学的データ格納部１２００にある三角形に関する物質情報を格納し、一実施例において、物質情報はテクスチャインデックス（ｔｅｘｔｕｒｅ ｉｎｄｅｘ）、環境定数（ａｍｂｉｅｎｔ ｃｏｎｓｔａｎｔ）、分散定数（ｄｉｆｆｕｓｅ ｃｏｎｓｔａｎｔ）、反射定数（ｓｐｅｃｕｌａｒ ｃｏｎｓｔａｎｔ）、屈折率（ｒｅｆｒａｃｔｉｏｎ ｒａｔｅ）（つまり、アルファ値）、屈折角（ｒｅｆｒａｃｔｉｏｎ ａｎｇｌｅ）などを含むことができる。三角形情報キャッシュ１８０は幾何学的データ格納部１２００のキャッシュで、シェーディング段階で要求される該当の三角形に対する三角形情報を格納し、三角形情報は物質メモリ１９５ｃの参照のための物質インデックス（ｍａｔｅｒｉａｌ ｉｎｄｅｘ）をさらに含むことができる。
【００６９】
シェーディング部１５０は、フォーン照明とテクスチャマッピングによってレイ−三角形ヒットポイントのカラー値を計算することができ、計算されたカラー値をシェーディングバッファ１８５ｅにある以前のカラーに計算されたカラーを加え、加えられたカラー値をシェーディングバッファ１８５ｅに格納する。シェーディングバッファ１８５ｅは与えられたピクセルから生成されたアイレイ、シャドーレイまたは派生レイによって累積したカラー値とシェーディング情報を格納する。
【００７０】
シェーディング情報は現在のレイに対する派生レイが生成されるか否かを決定するために使われる。シェーディング部１５０はヒットされた三角形に対する三角形情報に含まれた物質インデックスに基づいて物質メモリから物質情報（つまり、反射率と屈折率）を取り入れる。反射率が０に相応しない場合には、レイ生成部１２０は反射レイを生成することができ、屈折率が０に相応しない場合には、レイ生成部１２０は屈折レイを生成することができる。また、レイ生成部１２０は光源（ｌｉｇｈｔ ｓｏｕｒｃｅ）に対するシャドーレイを生成することができる。シェーディング部１５０はレイ−三角形ヒットポイントの座標値とカラー値及びシェーディングレイタイプを含むシェーディング情報をセットアッププロセッシング部１１０に伝送する。
【００７１】
一実施例において、フォーン照明は［ＨＡＲＲＩＳ， Ｄ． ２００４ Ａｎ ｅｘｐｏｎｅｎｔｉａｔｉｏｎ ｕｎｉｔ ｆｏｒ ａｎ ｏｐｅｎｇｌ ｌｉｇｈｔｉｎｇ ｅｎｇｉｎｅ． ＩＥＥＥＴ ｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｃｏｍｐｕｔｅｒｓ］にある構造を使うことができ、テクスチャマッピングはバイリニアフィルタリング構造（ｂｉｌｉｎｅａｒ ｆｉｌｔｅｒｉｎｇ ｓｃｈｅｍｅ）を支援し［ＨＡＫＵＲＡ， Ｚ． Ｓ．， ＡＮＤ ＧＵＰＴＡ， Ａ． １９９７． Ｔｈｅ ｄｅｓｉｇｎ ａｎｄ ａｎａｌｙｓｉｓ ｏｆ ａｃａｃｈｅ ａｒｃｈｉｔｅｃｔｕｒｅ ｆｏｒ ｔｅｘｔｕｒｅ ｍａｐｐｉｎｇ． ＳＩＧＡＲＣＨ Ｃｏｍｐｕｔｅｒ Ａｒｃｈｉｔｅｃｔｕｒｅ Ｎｅｗｓ］に開示されたキャッシュ構造を選択した。
【００７２】
図１０は図１のレイトレーシングコアが含まれたレイトレーシングボード（ｒａｙ ｔｒａｃｉｎｇ ｂｏａｒｄ）を説明する図である。
【００７３】
図１０を参照すれば、レイトレーシングボード２０００は、第１〜第２レイトレーシングサブボード２０１０ａ〜２０１０ｂを含み、第１レイトレーシングサブボード２０１０ａはレイトレーシングチップ２０２０ａ〜２０２０ｂを含み、第２レイトレーシングサブボード２０１０ｂはレイトレーシングチップ２０２０ｃ〜２０２０ｄを含む。
【００７４】
レイトレーシングコア２０２０は図１のレイトレーシングコア１００と実質的に同一であるので、その相違点を主に説明する。
【００７５】
ホストコンピュータの中央処理装置（ＣＰＵ）は場面管理ソフトウェア（Ｓｃｅｎｅ Ｍａｎａｇｅｍｅｎｔ Ｓｏｆｔｗａｒｅ）２００５を実行し、場面管理ソフトウェア２００５は加速構造（ＡＳ）を構築し、ＵＳＢインターフェースとＢＦＭ（Ｂｕｓ Ｆｕｎｃｔｉｏｎａｌ Ｍｏｄｅｌ）を介して加速構造（ＡＳ）、幾何学的データ、テクスチャデータをレイトレーシングチップ２０２０のそれぞれにあるメモリ（ＤＲＡＭ）２０３０ａ〜２０３０ｄに伝送する。その後、レイトレーシングコア２０２０は実行し始める。
【００７６】
第１レイトレーシングチップ２０１０ａはマスターとして動作する。第１レイトレーシングチップ２０１０ａにあるＸＹ生成器２０４０は適切なレイトレーシングコア（例えば、ひまなレイトレーシングチップ）２０２０にブロック住所（つまり、イメージの一部ブロック）を伝送する。ＸＹ生成器２０４０によって選択されたレイトレーシングコア２０２０はブロック住所を受けた後、所定のピクセルブロックに対してレンダリングを遂行する。例えば、所定のピクセルブロックは１６×１６ピクセルブロックに相応することができる。レンダリング完了の後、レイトレーシングコア２０２０はＸＹ生成器２０４０に次のブロック住所を要求することができる。レイトレーシングコア２０２０のそれぞれで生成された最終カラー値はＳＲＡＭ ＆ ＬＣＤ制御器２０５０によってＳＲＡＭ２０６０に格納される。
【００７７】
本発明は次の効果を持つことができる。ただ、特定の実施例が次の効果を全部含まなければならないかあるいは次の効果のみを含まなければならないという意味ではないので、本発明の権利範囲はこれによって制限されるものに理解されてはいけないであろう。
【００７８】
一実施例によるレイトレーシングコアは、レイトレーシングの効率的処理のためのＭＩＭＤ（Ｍｕｌｔｉｐｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ）並列構造を支援することができる。
【００７９】
一実施例によるレイトレーシングコアは、加速構造（ＡＳ）に適切に統合されたパイプライン構造を採択して、レイトレーシングで使われるレイ−ボックス交差、訪問、レイ−三角形交差テストを効率よく遂行することができる。
【００８０】
以上、本発明の好適な実施例を参照して説明したが、当該技術分野の熟練した当業者は下記の特許請求の範囲に記載された本発明の思想及び領域から逸脱しない範囲内で本発明を多様に修正及び変更することができることが理解可能であろう。
【符号の説明】
【００８１】
１００ レイトレーシングコア
１１０ セットアッププロセッシング部
１２０ レイ生成部
１３０ Ｔ＆Ｉ部
１４０ ヒットポイント計算部
１５０ シェーディング部
１６０ 制御部
１６５ レジスタ
１７０ Ｌ１キャッシュ
１７５ Ｌ２キャッシュ
１８０ キャッシュ
１８５ バッファ
１９０ スタック
１９５ メモリ
２０００ レイトレーシングボード
【特許請求の範囲】
【請求項１】
スクリーン座標値を含むアイレイの生成情報に基づいて少なくとも１つのアイレイを生成するレイ生成部；及び
前記少なくとも１つのアイレイをそれぞれ入力され、加速構造（ＡＳ；Ａｃｃｅｌａｒａｔｉｏｎ Ｓｔｒｕｃｔｕｒｅ）において前記入力されたアイレイと交差する三角形（前記三角形は空間を構成する）があるか否かをそれぞれチェックするＭＩＭＤ構造（Ｍｕｌｔｉｐｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ Ａｒｃｈｉｔｅｃｔｕｒｅ）を持つ複数のＴ＆Ｉ部（ａ ｐｌｕｒａｌｉｔｙ ｏｆ Ｔｒａｖｅｒｓａｌ ＆ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｕｎｉｔｓ）を含む、レイトレーシングコア（Ｒａｙ ｔｒａｃｉｎｇ ｃｏｒｅ）。
【請求項２】
前記レイトレーシングコア（Ｒａｙ ｔｒａｃｉｎｇ ｃｏｒｅ）は、前記入力されたアイレイと交差する三角形がある場合には、前記交差する三角形において前記アイレイがヒットされるヒットポイントに対してカラー値を計算するシェーディング部をさらに含むことを特徴とする、請求項１に記載のレイトレーシングコア。
【請求項３】
前記シェーディング部は、シェーディングレイが生成されるか可否を決定するために、前記ヒットポイントの座標値と前記計算されたカラー値及びシェーディングレイタイプを含み、前記シェーディングレイタイプによる付加情報を含むことができるシェーディング情報を生成することを特徴とする、請求項２に記載のレイトレーシングコア。
【請求項４】
前記レイ生成部は、前記生成されたシェーディング情報に基づいてシェーディングレイを生成するかまたは前記生成されたシェーディング情報に基づいて最終カラー値を格納することを特徴とする、請求項３に記載のレイトレーシングコア。
【請求項５】
レイトレーシングコアは派生レイを格納する派生レイスタックをさらに含み、
前記レイ生成部は、前記生成された派生レイの個数が２以上の場合には、１つの派生レイを前記複数のＴ＆Ｉ部の中で１つに割り当て、残りの派生レイを前記派生レイスタックに格納することを特徴とする、請求項４に記載のレイトレーシングコア。
【請求項６】
前記レイ生成部は、前記シェーディングレイタイプがナルレイに相応する場合には、前記派生レイスタックに格納された派生レイを取り入れて前記複数のＴ＆Ｉ部の中で１つに割り当てることを特徴とする、請求項５に記載のレイトレーシングコア。
【請求項７】
前記複数のＴ＆Ｉ部のそれぞれは、前記入力されたアイレイに基づいて前記加速構造（ＡＳ）に対する訪問過程（ｔｒａｖｅｒｓａｌ ｐｒｏｃｅｄｕｒｅ）、三角形リスト取り入れ過程（ｔｒｉａｎｇｌｅ ｌｉｓｔ ｆｅｔｃｈ ｐｒｏｃｅｄｕｒｅ）及びレイ−三角形交差テスト過程（ｒａｙ−Ｔｒｉａｎｇｌｅ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｔｅｓｔ ｐｒｏｃｅｄｕｒｅ）を行うＴ＆Ｉパイプライン部（Ｔｒａｖｅｒｓａｌ ＆ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｐｉｐｅｌｉｎｅ Ｕｎｉｔ）を含むことを特徴とする、請求項１に記載のレイトレーシングコア。
【請求項８】
前記複数のＴ＆Ｉ部それぞれは、前記ＭＩＭＤ構造を支援するための入力バッファと出力バッファをさらに含むことを特徴とする、請求項７に記載のレイトレーシングコア。
【請求項９】
前記レイトレーシングコアは、前記複数のＴ＆Ｉ部のそれぞれのキャッシュヒット率を増加させるために、スクリーンを複数のブロックに分割し、各ブロック基盤のアイレイの生成手順を決定するセットアッププロセッシング部をさらに含むことを特徴とする、請求項１に記載のレイトレーシングコア。
【請求項１０】
前記セットアッププロセッシング部は、前記スクリーンを複数のｍ×ｎ（ｍとｎは偶数）のピクセルブロック（以下、スーパーブロック）に分割し、各スーパーブロックを同一大きさのＮ個（Ｎは前記複数のＴ＆Ｉ部のそれぞれの個数）のピクセルブロック（サブブロック）に分割し、前記サブブロック基盤の前記アイレイの生成手順を決定することを特徴とする、請求項９に記載のレイトレーシングコア。
【請求項１１】
前記セットアッププロセッシング部は、前記アイレイの生成手順を決定するための線形のｎビットカウンターを含み、前記線形のｎビットカウンターの第１グループ（前記第１グループは連続しない少なくとも１つのビットを含むことができる）は前記サブブロックのｘ座標値を示し、前記線形のｎビットカウンターの第２グループ（前記第２グループは前記第１グループに属したビットを含まなく、連続しない少なくとも１つのビットを含むことができる）は前記サブブロックのｙ座標値を示すことを特徴とする、請求項１０に記載のレイトレーシングコア。
【請求項１２】
アイレイの生成情報（ｅｙｅ ｒａｙ ｇｅｎｅｒａｔｉｏｎ ｉｎｆｏｒｍａｔｉｏｎ）またはシェーディング情報（ｓｈａｄｉｎｇ ｉｎｆｏｒｍａｔｉｏｎ）（レイ−三角形ヒットポイントの座標値とカラー値及びシェーディングレイタイプを含み）の中で１つをマルチプレックシングするセットアッププロセッシング部；
前記アイレイの生成情報またはシェーディング情報に基づいて少なくとも１つのアイレイまたはシェーディングレイを生成するかまたは最終カラー値を決定するレイ生成部；及び
ＭＩＭＤ構造（Ｍｕｌｔｉｐｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ Ａｒｃｈｉｔｅｃｔｕｒｅ）を採択し、加速構造（ＡＳ；Ａｃｃｅｌｅｒａｔｉｏｎ Ｓｔｒｕｃｔｕｒｅ）において前記生成された少なくとも１つのアイレイまたはシェーディングレイと交差する三角形（前記三角形は空間を構成する）をそれぞれ決定する複数のＴ＆Ｉ部（ａ ｐｌｕｒａｌｉｔｙ ｏｆ Ｔｒａｖｅｒｓａｌ ＆ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｕｎｉｔｓ）を含む、レイトレーシングコア（Ｒａｙ ｔｒａｃｉｎｇ ｃｏｒｅ）。
【請求項１３】
前記レイトレーシングコアは、前記生成された少なくとも１つのアイレイまたはシェーディングレイに基づいて前記交差する三角形においてレイ−三角形ヒットポイントの座標値を計算するヒットポイント計算部をさらに含むことを特徴とする、請求項１２に記載のレイトレーシングコア。
【請求項１４】
前記レイトレーシングコアは、前記計算されたレイ−三角形ヒットポイントのカラー値を計算し、前記計算されたレイ−三角形ヒットポイントの座標値とカラー値及び前記シェーディングレイタイプを含む前記シェーディング情報を前記セットアッププロセッシング部に伝送するシェーディング部をさらに含むことを特徴とする、請求項１３に記載のレイトレーシングコア。
【請求項１５】
前記複数のＴ＆Ｉ部のそれぞれは、前記生成された少なくとも１つのアイレイまたはシェーディングレイに基づいて前記加速構造（ＡＳ）に対する訪問過程（ｔｒａｖｅｒｓａｌ ｐｒｏｃｅｄｕｒｅ）、三角形リスト取り入れ過程（ｔｒｉａｎｇｌｅ ｌｉｓｔ ｆｅｔｃｈ ｐｒｏｃｅｄｕｒｅ）及びレイ−三角形交差テスト過程（ｒａｙ−Ｔｒｉａｎｇｌｅ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｔｅｓｔ ｐｒｏｃｅｄｕｒｅ）を行うＴ＆Ｉパイプライン部（Ｔｒａｖｅｒｓａｌ ＆ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｐｉｐｅｌｉｎｅ Ｕｎｉｔ）を含むことを特徴とする、請求項１２に記載のレイトレーシングコア。
【請求項１６】
複数のレイトレーシングコア；
前記複数のレイトレーシングコアの中で適切なレイトレーシングコアにイメージの一部ブロックを割り当てるＸＹ生成器；及び
前記複数のレイトレーシングコアのそれぞれから出力された最終カラー値を格納するメモリを含み、
前記複数のレイトレーシングコアのそれぞれは、
スクリーン座標値を含むアイレイの生成情報に基づいて少なくとも１つのアイレイを生成するレイ生成部；及び
前記少なくとも１つのアイレイをそれぞれ入力され、加速構造（ＡＳ；Ａｃｃｅｌａｒａｔｉｏｎ Ｓｔｒｕｃｔｕｒｅ）において前記入力されたアイレイと交差する三角形（前記三角形は空間を構成する）があるか否かをそれぞれチェックするＭＩＭＤ構造（Ｍｕｌｔｉｐｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ Ａｒｃｈｉｔｅｃｔｕｒｅ）を持つ複数のＴ＆Ｉ部（ａ ｐｌｕｒａｌｉｔｙ ｏｆ Ｔｒａｖｅｒｓａｌ ＆ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｕｎｉｔｓ）を含む、レイトレーシングチップ（ｒａｙ ｔｒａｃｉｎｇ ｃｈｉｐ）。
【請求項１７】
複数のレイトレーシングコア；
前記複数のレイトレーシングコアの中で適切なレイトレーシングコアにイメージの一部ブロックを割り当てるＸＹ生成器；及び
前記複数のレイトレーシングコアのそれぞれから出力された最終カラー値を格納するメモリを含み、
前記複数のレイトレーシングコアのそれぞれは、
アイレイの生成情報（ｅｙｅ ｒａｙ ｇｅｎｅｒａｔｉｏｎ ｉｎｆｏｒｍａｔｉｏｎ）またはシェーディング情報（ｓｈａｄｉｎｇ ｉｎｆｏｒｍａｔｉｏｎ）（レイ−三角形ヒットポイントの座標値とカラー値及びシェーディングレイタイプを含み）の中で１つをマルチプレックシングするセットアッププロセッシング部；
前記アイレイの生成情報またはシェーディング情報に基づいて少なくとも１つのアイレイまたはシェーディングレイを生成するかまたは最終カラー値を決定するレイ生成部；及び
ＭＩＭＤ構造（Ｍｕｌｔｉｐｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ Ａｒｃｈｉｔｅｃｔｕｒｅ）を採択し、加速構造（ＡＳ；Ａｃｃｅｌｅｒａｔｉｏｎ Ｓｔｒｕｃｔｕｒｅ）において前記生成された少なくとも１つのアイレイまたはシェーディングレイと交差する三角形（前記三角形は空間を構成する）をそれぞれ決定する複数のＴ＆Ｉ部（ａ ｐｌｕｒａｌｉｔｙ ｏｆ Ｔｒａｖｅｒｓａｌ ＆ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｕｎｉｔｓ）を含む、レイトレーシングチップ（ｒａｙ ｔｒａｃｉｎｇ ｃｈｉｐ）。
【請求項１】
スクリーン座標値を含むアイレイの生成情報に基づいて少なくとも１つのアイレイを生成するレイ生成部；及び
前記少なくとも１つのアイレイをそれぞれ入力され、加速構造（ＡＳ；Ａｃｃｅｌａｒａｔｉｏｎ Ｓｔｒｕｃｔｕｒｅ）において前記入力されたアイレイと交差する三角形（前記三角形は空間を構成する）があるか否かをそれぞれチェックするＭＩＭＤ構造（Ｍｕｌｔｉｐｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ Ａｒｃｈｉｔｅｃｔｕｒｅ）を持つ複数のＴ＆Ｉ部（ａ ｐｌｕｒａｌｉｔｙ ｏｆ Ｔｒａｖｅｒｓａｌ ＆ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｕｎｉｔｓ）を含む、レイトレーシングコア（Ｒａｙ ｔｒａｃｉｎｇ ｃｏｒｅ）。
【請求項２】
前記レイトレーシングコア（Ｒａｙ ｔｒａｃｉｎｇ ｃｏｒｅ）は、前記入力されたアイレイと交差する三角形がある場合には、前記交差する三角形において前記アイレイがヒットされるヒットポイントに対してカラー値を計算するシェーディング部をさらに含むことを特徴とする、請求項１に記載のレイトレーシングコア。
【請求項３】
前記シェーディング部は、シェーディングレイが生成されるか可否を決定するために、前記ヒットポイントの座標値と前記計算されたカラー値及びシェーディングレイタイプを含み、前記シェーディングレイタイプによる付加情報を含むことができるシェーディング情報を生成することを特徴とする、請求項２に記載のレイトレーシングコア。
【請求項４】
前記レイ生成部は、前記生成されたシェーディング情報に基づいてシェーディングレイを生成するかまたは前記生成されたシェーディング情報に基づいて最終カラー値を格納することを特徴とする、請求項３に記載のレイトレーシングコア。
【請求項５】
レイトレーシングコアは派生レイを格納する派生レイスタックをさらに含み、
前記レイ生成部は、前記生成された派生レイの個数が２以上の場合には、１つの派生レイを前記複数のＴ＆Ｉ部の中で１つに割り当て、残りの派生レイを前記派生レイスタックに格納することを特徴とする、請求項４に記載のレイトレーシングコア。
【請求項６】
前記レイ生成部は、前記シェーディングレイタイプがナルレイに相応する場合には、前記派生レイスタックに格納された派生レイを取り入れて前記複数のＴ＆Ｉ部の中で１つに割り当てることを特徴とする、請求項５に記載のレイトレーシングコア。
【請求項７】
前記複数のＴ＆Ｉ部のそれぞれは、前記入力されたアイレイに基づいて前記加速構造（ＡＳ）に対する訪問過程（ｔｒａｖｅｒｓａｌ ｐｒｏｃｅｄｕｒｅ）、三角形リスト取り入れ過程（ｔｒｉａｎｇｌｅ ｌｉｓｔ ｆｅｔｃｈ ｐｒｏｃｅｄｕｒｅ）及びレイ−三角形交差テスト過程（ｒａｙ−Ｔｒｉａｎｇｌｅ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｔｅｓｔ ｐｒｏｃｅｄｕｒｅ）を行うＴ＆Ｉパイプライン部（Ｔｒａｖｅｒｓａｌ ＆ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｐｉｐｅｌｉｎｅ Ｕｎｉｔ）を含むことを特徴とする、請求項１に記載のレイトレーシングコア。
【請求項８】
前記複数のＴ＆Ｉ部それぞれは、前記ＭＩＭＤ構造を支援するための入力バッファと出力バッファをさらに含むことを特徴とする、請求項７に記載のレイトレーシングコア。
【請求項９】
前記レイトレーシングコアは、前記複数のＴ＆Ｉ部のそれぞれのキャッシュヒット率を増加させるために、スクリーンを複数のブロックに分割し、各ブロック基盤のアイレイの生成手順を決定するセットアッププロセッシング部をさらに含むことを特徴とする、請求項１に記載のレイトレーシングコア。
【請求項１０】
前記セットアッププロセッシング部は、前記スクリーンを複数のｍ×ｎ（ｍとｎは偶数）のピクセルブロック（以下、スーパーブロック）に分割し、各スーパーブロックを同一大きさのＮ個（Ｎは前記複数のＴ＆Ｉ部のそれぞれの個数）のピクセルブロック（サブブロック）に分割し、前記サブブロック基盤の前記アイレイの生成手順を決定することを特徴とする、請求項９に記載のレイトレーシングコア。
【請求項１１】
前記セットアッププロセッシング部は、前記アイレイの生成手順を決定するための線形のｎビットカウンターを含み、前記線形のｎビットカウンターの第１グループ（前記第１グループは連続しない少なくとも１つのビットを含むことができる）は前記サブブロックのｘ座標値を示し、前記線形のｎビットカウンターの第２グループ（前記第２グループは前記第１グループに属したビットを含まなく、連続しない少なくとも１つのビットを含むことができる）は前記サブブロックのｙ座標値を示すことを特徴とする、請求項１０に記載のレイトレーシングコア。
【請求項１２】
アイレイの生成情報（ｅｙｅ ｒａｙ ｇｅｎｅｒａｔｉｏｎ ｉｎｆｏｒｍａｔｉｏｎ）またはシェーディング情報（ｓｈａｄｉｎｇ ｉｎｆｏｒｍａｔｉｏｎ）（レイ−三角形ヒットポイントの座標値とカラー値及びシェーディングレイタイプを含み）の中で１つをマルチプレックシングするセットアッププロセッシング部；
前記アイレイの生成情報またはシェーディング情報に基づいて少なくとも１つのアイレイまたはシェーディングレイを生成するかまたは最終カラー値を決定するレイ生成部；及び
ＭＩＭＤ構造（Ｍｕｌｔｉｐｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ Ａｒｃｈｉｔｅｃｔｕｒｅ）を採択し、加速構造（ＡＳ；Ａｃｃｅｌｅｒａｔｉｏｎ Ｓｔｒｕｃｔｕｒｅ）において前記生成された少なくとも１つのアイレイまたはシェーディングレイと交差する三角形（前記三角形は空間を構成する）をそれぞれ決定する複数のＴ＆Ｉ部（ａ ｐｌｕｒａｌｉｔｙ ｏｆ Ｔｒａｖｅｒｓａｌ ＆ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｕｎｉｔｓ）を含む、レイトレーシングコア（Ｒａｙ ｔｒａｃｉｎｇ ｃｏｒｅ）。
【請求項１３】
前記レイトレーシングコアは、前記生成された少なくとも１つのアイレイまたはシェーディングレイに基づいて前記交差する三角形においてレイ−三角形ヒットポイントの座標値を計算するヒットポイント計算部をさらに含むことを特徴とする、請求項１２に記載のレイトレーシングコア。
【請求項１４】
前記レイトレーシングコアは、前記計算されたレイ−三角形ヒットポイントのカラー値を計算し、前記計算されたレイ−三角形ヒットポイントの座標値とカラー値及び前記シェーディングレイタイプを含む前記シェーディング情報を前記セットアッププロセッシング部に伝送するシェーディング部をさらに含むことを特徴とする、請求項１３に記載のレイトレーシングコア。
【請求項１５】
前記複数のＴ＆Ｉ部のそれぞれは、前記生成された少なくとも１つのアイレイまたはシェーディングレイに基づいて前記加速構造（ＡＳ）に対する訪問過程（ｔｒａｖｅｒｓａｌ ｐｒｏｃｅｄｕｒｅ）、三角形リスト取り入れ過程（ｔｒｉａｎｇｌｅ ｌｉｓｔ ｆｅｔｃｈ ｐｒｏｃｅｄｕｒｅ）及びレイ−三角形交差テスト過程（ｒａｙ−Ｔｒｉａｎｇｌｅ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｔｅｓｔ ｐｒｏｃｅｄｕｒｅ）を行うＴ＆Ｉパイプライン部（Ｔｒａｖｅｒｓａｌ ＆ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｐｉｐｅｌｉｎｅ Ｕｎｉｔ）を含むことを特徴とする、請求項１２に記載のレイトレーシングコア。
【請求項１６】
複数のレイトレーシングコア；
前記複数のレイトレーシングコアの中で適切なレイトレーシングコアにイメージの一部ブロックを割り当てるＸＹ生成器；及び
前記複数のレイトレーシングコアのそれぞれから出力された最終カラー値を格納するメモリを含み、
前記複数のレイトレーシングコアのそれぞれは、
スクリーン座標値を含むアイレイの生成情報に基づいて少なくとも１つのアイレイを生成するレイ生成部；及び
前記少なくとも１つのアイレイをそれぞれ入力され、加速構造（ＡＳ；Ａｃｃｅｌａｒａｔｉｏｎ Ｓｔｒｕｃｔｕｒｅ）において前記入力されたアイレイと交差する三角形（前記三角形は空間を構成する）があるか否かをそれぞれチェックするＭＩＭＤ構造（Ｍｕｌｔｉｐｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ Ａｒｃｈｉｔｅｃｔｕｒｅ）を持つ複数のＴ＆Ｉ部（ａ ｐｌｕｒａｌｉｔｙ ｏｆ Ｔｒａｖｅｒｓａｌ ＆ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｕｎｉｔｓ）を含む、レイトレーシングチップ（ｒａｙ ｔｒａｃｉｎｇ ｃｈｉｐ）。
【請求項１７】
複数のレイトレーシングコア；
前記複数のレイトレーシングコアの中で適切なレイトレーシングコアにイメージの一部ブロックを割り当てるＸＹ生成器；及び
前記複数のレイトレーシングコアのそれぞれから出力された最終カラー値を格納するメモリを含み、
前記複数のレイトレーシングコアのそれぞれは、
アイレイの生成情報（ｅｙｅ ｒａｙ ｇｅｎｅｒａｔｉｏｎ ｉｎｆｏｒｍａｔｉｏｎ）またはシェーディング情報（ｓｈａｄｉｎｇ ｉｎｆｏｒｍａｔｉｏｎ）（レイ−三角形ヒットポイントの座標値とカラー値及びシェーディングレイタイプを含み）の中で１つをマルチプレックシングするセットアッププロセッシング部；
前記アイレイの生成情報またはシェーディング情報に基づいて少なくとも１つのアイレイまたはシェーディングレイを生成するかまたは最終カラー値を決定するレイ生成部；及び
ＭＩＭＤ構造（Ｍｕｌｔｉｐｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ ｓｔｒｅａｍ Ｍｕｌｔｉｐｌｅ Ｄａｔａ ｓｔｒｅａｍ Ａｒｃｈｉｔｅｃｔｕｒｅ）を採択し、加速構造（ＡＳ；Ａｃｃｅｌｅｒａｔｉｏｎ Ｓｔｒｕｃｔｕｒｅ）において前記生成された少なくとも１つのアイレイまたはシェーディングレイと交差する三角形（前記三角形は空間を構成する）をそれぞれ決定する複数のＴ＆Ｉ部（ａ ｐｌｕｒａｌｉｔｙ ｏｆ Ｔｒａｖｅｒｓａｌ ＆ Ｉｎｔｅｒｓｅｃｔｉｏｎ Ｕｎｉｔｓ）を含む、レイトレーシングチップ（ｒａｙ ｔｒａｃｉｎｇ ｃｈｉｐ）。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公表番号】特表２０１２−５２８３７７（Ｐ２０１２−５２８３７７Ａ）
【公表日】平成２４年１１月１２日（２０１２．１１．１２）
【国際特許分類】
【出願番号】特願２０１２−５１２９５２（Ｐ２０１２−５１２９５２）
【出願日】平成２２年５月１９日（２０１０．５．１９）
【国際出願番号】ＰＣＴ／ＫＲ２０１０／００３１７３
【国際公開番号】ＷＯ２０１０／１３７８２２
【国際公開日】平成２２年１２月２日（２０１０．１２．２）
【出願人】（５１１２８２８１８）シリコンアーツ インコーポレイテッド (2)
【出願人】（５１１２８２８２９）
【Ｆターム（参考）】
【公表日】平成２４年１１月１２日（２０１２．１１．１２）
【国際特許分類】
【出願日】平成２２年５月１９日（２０１０．５．１９）
【国際出願番号】ＰＣＴ／ＫＲ２０１０／００３１７３
【国際公開番号】ＷＯ２０１０／１３７８２２
【国際公開日】平成２２年１２月２日（２０１０．１２．２）
【出願人】（５１１２８２８１８）シリコンアーツ インコーポレイテッド (2)
【出願人】（５１１２８２８２９）
【Ｆターム（参考）】
[ Back to top ]