(57)【要約】【課題】  光線追跡法を実行するためのより効率的な技術及び装置を提供すること。【解決手段】  本発明の実施形態は、空間インデックス構造を通る光線のトラバース履歴を記録し、記録されたトラバース履歴を用いるための方法及び装置を提供する。画像処理システムは、最初に、光線が空間インデックスをトラバースするとき、光線がどのノードと交差するかを判定することができる。ノード交差判定の結果は、光線が空間インデックスをトラバースするときに記録することができ、記録された判定を光線と関連付けることができる。さらに、画像処理システムは、空間インデックスを構成するノードに対応するプリミティブに当たる何らかの確率に基づいて、トラバース経路を決定することができる。このトラバース経路を記録し、光線と関連付けることもできる。画像処理システムが、後に空間インデックスの再トラバースを必要とする場合、記録されたトラバース履歴を用いて、光線−ノード交差を再計算する必要性をなくし、正しくないトラバース経路の判定を排除することができる。【選択図】      図６
2009545044.tif 000002
【特許請求の範囲】
【請求項１】
３次元シーンの境界ボリュームを定めるノードを有する空間インデックスを用いる光線追跡方法であって、
前記シーン内に光線を生成するステップと、
葉ノードに到達するまで内部ノードから分岐を行なうことによって前記空間インデックスをトラバースするステップであって、前記光線が前記ノードによって定められる境界ボリュームと交差するか否かに基づいて分岐が行なわれる、ステップと、
前記光線が交差する境界ボリュームを定める１つ又は複数のノードと、前記空間インデックスをトラバースするときに行なわれる分岐とを示すトラバース履歴を記録するステップと、
前記光線が前記葉ノードによって定められる前記境界ボリューム内に含まれるプリミティブにヒットするか否かを判定するステップと、
前記光線が前記葉ノードによって定められる前記境界ボリューム内に含まれるプリミティブにヒットしない場合、前記記録されたトラバース履歴を用いて前記空間インデックスを再トラバースするステップと
を含む方法。
【請求項２】
前記空間インデックスは複数の内部ノード・レベルを含み、前記トラバース履歴は、各ノード・レベルについて記録される、請求項１に記載の方法。
【請求項３】
前記空間インデックスは複数の内部ノード・レベルを含み、前記トラバース履歴は、前記空間インデックスの各内部ノード・レベルについて４ビットを含む、請求項１に記載の方法。
【請求項４】
前記トラバース履歴ビットのうちの２つは、前記光線が、前記内部ノード・レベルの１つの中に配置されたノードによって定められる境界ボリュームと交差するか否かを示し、前記トラバース履歴ビットのうちの２つは、前記内部ノード・レベルの１つの前記ノードから前記空間インデックスをトラバースするときに行なわれる分岐を示す、請求項３に記載の方法。
【請求項５】
前記光線を定める情報を有する前記光線トラバース履歴を格納するステップと、
前記光線を定める情報及び前記トラバース履歴を、第１の処理要素上で実行されている作業負荷マネージャから、第２の処理要素上で実行されているベクトル・スループット・エンジンに伝送するステップであって、前記作業負荷マネージャ及び前記ベクトル・スループット・エンジンは、メモリマッピングされたアドレス空間を通して通信する、ステップと
をさらに含む、請求項１、請求項２、請求項３、又は請求項４に記載の方法。
【請求項６】
前記作業負荷マネージャは、前記光線が前記ノードによって定められる境界ボリュームと交差するか否かを判定し、かつ、前記トラバース履歴を記録し、前記ベクトル・スループット・エンジンは、前記光線が前記葉ノードによって定められる前記境界ボリューム内に含まれるプリミティブにヒットするか否かを判定する、請求項５に記載の方法。
【請求項７】
前記作業負荷マネージャ及び前記ベクトル・スループット・エンジンは、同じ処理要素上に配置される、請求項５又は請求項６に記載の方法。
【請求項８】
前記作業負荷マネージャ及び前記ベクトル・スループット・エンジンは、別個の処理要素上に配置される、請求項５又は請求項６に記載の方法。
【請求項９】
前記記録されたトラバース履歴を用いて前記空間インデックスを再トラバースするステップは、
前記光線がノードに対応する境界ボリュームと交差したが前記ノードから分岐が行なわれない、前記空間インデックスの最下位レベルを判定するステップと、
前記トラバース履歴内の行なわれ記録された前記分岐に基づいて、前記最下位レベルまで前記空間インデックスをトラバースするステップと、
まだ分岐が行なわれていない前記ノードから前記分岐を行なうステップと、
葉ノードに到達するまで内部ノードから分岐を行なうことによって、最下位レベルより下の前記空間インデックスをトラバースするステップであって、前記光線が前記ノードによって定められる境界ボリュームと交差するか否かに基づいて分岐が行なわれる、ステップと、
前記光線が交差する境界ボリュームを定める１つ又は複数のノードと、前記空間インデックスをトラバースするときに行なわれる分岐とを示す、前記最下位レベルより下のトラバース履歴を記録するステップと、
前記光線が、前記最下位レベルの下の前記境界ボリューム内に含まれ、かつ、前記葉ノードによって定められるプリミティブにヒットするか否かを判定するステップと
を含む、請求項１乃至請求項８のいずれかに記載の方法。
【請求項１０】
実行時に、３次元シーンの境界ボリュームを定めるノードを有する空間インデックスを用いる光線追跡のための操作を行なうプログラムを含むコンピュータ可読媒体であって、前記操作は、
前記シーン内に光線を生成するステップと、
葉ノードに到達するまで内部ノードから分岐を行なうことによって前記空間インデックスをトラバースするステップであって、前記光線が前記ノードによって定められる境界ボリュームと交差するか否かに基づいて分岐が行なわれる、ステップと、
前記光線が交差する境界ボリュームを定める１つ又は複数のノードと、前記空間インデックスをトラバースするときに行なわれる分岐とを示すトラバース履歴を記録するステップと、
前記光線が前記葉ノードによって定められる前記境界ボリューム内に含まれるプリミティブにヒットするか否かを判定するステップと、
前記光線が前記葉ノードによって定められる前記境界ボリューム内に含まれるプリミティブにヒットしない場合、前記記録されたトラバース履歴を用いて前記空間インデックスを再トラバースするステップと
を含む、コンピュータ可読媒体。
【請求項１１】
前記空間インデックスは複数の内部ノード・レベルを含み、前記トラバース履歴は、各ノード・レベルについて記録される、請求項１０に記載のコンピュータ可読媒体。
【請求項１２】
前記空間インデックスは複数の内部ノード・レベルを含み、前記トラバース履歴は、前記空間インデックスの各内部ノード・レベルについて４ビットを含み、前記トラバース履歴ビットのうちの２つは、前記光線が前記内部ノード・レベルの１つのノードによって定められる境界ボリュームと交差するか否かを示し、前記トラバース履歴ビットのうちの２つは、前記内部ノード・レベルの１つの前記ノードから前記空間インデックスをトラバースするときに行なわれる分岐を示す、請求項１０に記載のコンピュータ可読媒体。
【請求項１３】
前記操作は、
前記光線を定める情報を有する前記光線トラバース履歴を格納するステップと、
前記光線を定める情報及び前記トラバース履歴を、第１の処理要素上で実行されている作業負荷マネージャから第２の処理要素上で実行されているベクトル・スループット・エンジンに伝送するステップであって、前記作業負荷マネージャ及び前記ベクトル・スループット・エンジンは、メモリマッピングされた・アドレス空間を通して通信する、ステップと
をさらに含む、請求項１０に記載のコンピュータ可読媒体。
【請求項１４】
前記作業負荷マネージャは、前記光線が前記ノードによって定められる境界ボリュームと交差するか否かを判定し、かつ、前記トラバース履歴を記録し、前記ベクトル・スループット・エンジンは、前記光線が前記葉ノードによって定められる前記境界ボリューム内に含まれるプリミティブにヒットするか否かを判定する、請求項１３に記載のコンピュータ可読媒体。
【請求項１５】
前記記録されたトラバース履歴を用いて前記空間インデックスを再トラバースするステップは、
前記光線がノードに対応する境界ボリュームと交差したが前記ノードから分岐が行なわれない、前記空間インデックスの最下位レベルを判定するステップと、
前記トラバース履歴内の行なわれ記録された前記分岐に基づいて、前記最下位レベルまで前記空間インデックスをトラバースするステップと、
まだ分岐が行なわれていない前記ノードから前記分岐を行なうステップと、
葉ノードに到達するまで内部ノードから分岐を行なうことによって、最下位レベルより下の前記空間インデックスをトラバースするステップであって、前記光線が前記ノードによって定められる境界ボリュームと交差するか否かに基づいて分岐が行なわれる、ステップと
を含み、前記操作は、
前記光線が交差する境界ボリュームを定める１つ又は複数のノードと、前記空間インデックスをトラバースするときに行なわれる分岐とを示す、前記最下位レベルより下のトラバース履歴を記録するステップと、
前記光線が、前記最下位レベルの下の前記境界ボリューム内に含まれ、かつ、前記葉ノードによって定められるプリミティブにヒットするか否かを判定するステップと
をさらに含む、請求項１０に記載のコンピュータ可読媒体。
【請求項１６】
３次元シーンの境界ボリュームを定めるノードを有する空間インデックスと、
第１の処理要素であって、
前記シーン内に光線を生成し、
葉ノードに到達するまで内部ノードから分岐を行なうことによって前記空間インデックスをトラバースし、前記光線が前記ノードによって定められる境界ボリュームと交差するか否かに基づいて分岐が行なわれ、
前記光線が交差する境界ボリュームを定める１つ又は複数のノードと、前記空間インデックスをトラバースするときに行なわれる分岐とを示すトラバース履歴を記録し、
前記光線が前記葉ノードによって定められる前記境界ボリューム内に含まれるプリミティブにヒットするか否かを判定し、
前記光線が前記葉ノードによって定められる前記境界ボリューム内に含まれるプリミティブにヒットしない場合、前記記録されたトラバース履歴を用いて前記空間インデックスを再トラバースする、
ように構成された、第１の処理要素と
を備えるシステム。
【請求項１７】
前記空間インデックスは複数の内部ノード・レベルを含み、前記トラバース履歴は、各ノード・レベルについて記録される、請求項１６に記載のシステム。
【請求項１８】
前記空間インデックスは複数の内部ノード・レベルを含み、前記トラバース履歴は、前記空間インデックスの各内部ノード・レベルについて４ビットを含む、請求項１６に記載のシステム。
【請求項１９】
前記トラバース履歴ビットのうちの２つは、前記光線が前記内部ノード・レベルの１つの中に配置されたノードによって定められる境界ボリュームと交差するか否かを示し、前記トラバース履歴ビットのうちの２つは、前記内部ノード・レベルの１つの前記ノードから前記空間インデックスをトラバースするときに行なわれる分岐を示す、請求項１８に記載のシステム。
【請求項２０】
前記第１の処理要素は、
複数のスレッドと、
メモリマッピングされたアドレス空間と
をさらに備え、
前記第１の処理要素は、
前記光線を定める情報を有する前記光線トラバース履歴を格納し、
前記光線を定める情報及び前記トラバース履歴を、第１の処理要素スレッド上で実行されている作業負荷マネージャから第２の処理要素スレッド上で実行されているベクトル・スループット・エンジンに伝送し、前記作業負荷マネージャ及び前記ベクトル・スループット・エンジンは、メモリマッピングされたアドレス空間を通して通信する、
ようにさらに構成される、請求項１６、請求項１７、請求項１８、又は請求項１９に記載のシステム。
【請求項２１】
前記作業負荷マネージャは、前記光線が前記ノードによって定められる境界ボリュームと交差するか否かを判定し、かつ、前記トラバース履歴を記録し、前記ベクトル・スループット・エンジンは、前記光線が前記葉ノードによって定められる前記境界ボリューム内に含まれるプリミティブにヒットするか否かを判定する、請求項２０に記載のシステム。
【請求項２２】
前記システムは、
第２の複数のスレッドと、第２のメモリマッピングされたアドレス空間とを含む第２の処理要素と、
前記第１の処理要素を前記第２の処理要素に結合する高速バスと、
をさらに備え、
前記作業負荷マネージャは前記第１の処理要素上で実行され、前記ベクトル・スループット・エンジンは前記第２の処理要素上で実行され、前記作業負荷マネージャ及び前記ベクトル・スループット・エンジンは、前記高速バス及び前記メモリマッピングされたアドレス空間を通して通信する、請求項２０又は請求項２１に記載のシステム。
【請求項２３】
前記記録されたトラバース履歴を用いて前記空間インデックスを再トラバースするステップは、
前記光線がノードに対応する境界ボリュームと交差したが前記ノードから分岐が行なわれない、前記空間インデックスの最下位レベルを判定するステップと、
前記トラバース履歴内の行なわれ記録された前記分岐に基づいて、前記最下位レベルまで前記空間インデックスをトラバースするステップと、
まだ分岐が行なわれてない前記ノードから前記分岐を行なうステップと、
葉ノードに到達するまで内部ノードから分岐を行なうことによって、最下位レベルより下の前記空間インデックスをトラバースするステップであって、前記光線が前記ノードによって定められる境界ボリュームと交差するか否かに基づいて分岐が行なわれる、ステップと
を含み、前記システムは、
前記光線が交差する境界ボリュームを定める１つ又は複数のノードと、前記空間インデックスをトラバースするときに行なわれる分岐とを示す、前記最下位レベルより下のトラバース履歴を記録するステップと、
前記光線が、前記最下位レベルの下の前記境界ボリューム内に含まれ、かつ、前記葉ノードによって定められるプリミティブにヒットするか否かを判定するステップと
をさらに含む、前記請求項１６乃至請求項２２のいずれかに記載のシステム。
【請求項２４】
コンピュータ・プログラムであって、前記プログラムがコンピュータ上で動作する際に、請求項１乃至請求項８のいずれかの方法を実行するように適合されたプログラム・コード手段を備える、コンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、一般に、画像処理の分野に関する。
【背景技術】
【０００２】
３次元シーンから２次元画像をレンダリングするプロセスは、一般に、画像処理と呼ばれる。現代のコンピュータ産業が発展するに従い、画像処理もまた発展してきた。画像処理の発展における１つの特定の目標は、３次元シーンの２次元シミュレーション又は表現（rendition）をできる限り現実的なものにすることである。現実的な画像をレンダリングする際の１つの制限は、現代のモニタがピクセルの使用を通して画像を表示するということである。
【０００３】
ピクセルは、モニタ上で照射することができる最小の領域である。最新のコンピュータ・モニタは、ディスプレイ全体又はレンダリングされたシーンを構成するために、何十万又は何百万ものピクセルの組み合わせを使用する。個々のピクセルは、グリッド・パターン状に配列されており、モニタの表示領域全体を集合的に覆う。個々のピクセルを照射して、表示用の最終的なピクチャをレンダリングすることができる。
【０００４】
ピクセルを用いて２次元モニタ上に実世界の３次元シーンをレンダリングするための１つの技術は、ラスタ化（rasterization）と呼ばれる。ラスタ化とは、ベクトル形式（シーン内の幾何学的物体の数学的表現）で表される２次元画像を取得し、モニタ上に表示するために、その画像を個々のピクセルに変換するプロセスである。ラスタ化は、グラフィックスを速くレンダリングし、比較的少量の計算能力しか使用しないという点で有効であるが、このラスタ化は幾つかの欠点を抱えている。例えば、ラスタ化は、光の物理的性質に基づくものではなく、寧ろ、２次元平面上に投影されるシーンにおける３次元の幾何学的物体の形状に基づいているので、現実感が不足することが多い。さらに、ラスタ化を用いてシーンをレンダリングするのに必要な計算能力は、レンダリングされるシーンの複雑さが増すのに応じて直接的に拡張する。画像処理がより現実的になるに従い、レンダリングされるシーンもより複雑になる。従って、複雑さに伴ってラスタ化が直接的に拡張するので、画像処理が発展すると共に、ラスタ化は困難を抱える。
【０００５】
ピクセルを用いて２次元モニタ上に実世界の３次元シーンをレンダリングするための別の技術は、光線追跡法（ray tracing）と呼ばれる。光線追跡技術は、コンピュータ・スクリーン上にレンダリングされる３次元シーンへの、通常の光線と同様に振る舞う想像上の光線の伝搬を追跡する。これらの光線は、コンピュータ・スクリーンの後ろに位置する観察者の目から発し、コンピュータ・スクリーンを構成するピクセルを通過し、３次元シーンの方向に向かう。追跡される各光線はシーンに進入し、シーン内の物体と交差することがある。光線がシーン内の物体と交差した場合には、その物体の性質及び他の幾つかの寄与要因を用いて、光線が曝される色及び光の量、又はそれらの欠如を計算する。次いで、これらの計算を用いて、追跡される光線が通過したピクセルの最終的な色を決定する。
【０００６】
光線を追跡するプロセスは、単一の３次元シーンについて何度も行なわれる。例えば、ディスプレイ内の各ピクセルごとに単一の光線を追跡することができる。コンピュータ・スクリーンの２次元表示を構成する全てのピクセルの色を決定するのに十分な数の光線が追跡されると、観察者に対して、３次元シーンの２次元合成をコンピュータ・スクリーン上に表示することができる。
【０００７】
光線追跡法は、一般的に、ラスタ化よりも多くの現実感を伴って、実世界の３次元シーンをレンダリングする。これは、特に、光線追跡法が、ラスタ化を用いてなされるように単に３次元形状を２次元平面上に投影するのではなく、実世界の環境において光がどのように進み、振る舞うかをシミュレートするためである。従って、光線追跡法を用いてレンダリングされるグラフィックスは、我々の目が実世界で見慣れているものを、より正確にモニタ上に描写する。
【０００８】
さらに、光線追跡法はまた、シーンがより複雑になるにつれて、ラスタ化よりも良好にシーンの複雑さの増大に対応する。光線追跡法は、シーンの複雑さに応じて対数的に拡張する。これは、シーンがより複雑になったとしても、同じ数の光線をシーンに投射することができるためである。従って、光線追跡法は、シーンがより複雑になっても、ラスタ化のように計算能力の要件に関して問題を抱えることはない。
【０００９】
光線追跡法の１つの主要な欠点は、シーンのレンダリングに大量の計算、よって、大量の処理能力を必要とすることである。このことは、速いレンダリングを必要とするときに問題をもたらす。例えば、画像処理システムが、ゲーム機などにおけるように、アニメーション用のグラフィックスをレンダリングする場合である。光線追跡法に関する計算要件の増大に起因して、現実的に見えるのに十分な程アニメーションを速くレンダリングするのは困難である（現実的なアニメーションは、毎秒約２０〜２４フレームである）。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
従って、光線追跡法を実行するためのより効率的な技術及び装置に対する必要性が存在する。
【課題を解決するための手段】
【００１１】
本発明の実施形態は、一般に、光線追跡法を実行するための方法及び装置を提供する。
【００１２】
本発明の第１の態様によると、３次元シーンの境界ボリュームを定めるノードを有する空間インデックスを用いる光線追跡方法が提供される。この方法は、一般に、シーン内に光線を生成することと、葉ノードに到達するまで内部ノードから分岐することによって、空間インデックスをトラバースすることであって、光線がノードによって定められる境界ボリュームと交差するか否かに基づいて分岐が行なわれる、ことと、光線が交差する境界ボリュームを定める１つ又は複数のノードと、空間インデックスをトラバースするときに行なわれる分岐とを示すトラバース履歴を記録することと、光線が葉ノードによって定められる境界ボリューム内に含まれるプリミティブにヒットするか（hit）否かを判定することと、光線が葉ノードによって定められる境界ボリューム内に含まれるプリミティブにヒットしない場合、記録されたトラバース履歴を用いて空間インデックスを再トラバースすることとを含む。
【００１３】
本発明の第２の態様によると、実行時に、３次元シーンの境界ボリュームを定めるノードを有する空間インデックスを用いる光線追跡のための操作を行なうプログラムを含む、コンピュータ可読媒体が提供される。この操作は、一般に、シーン内に光線を生成することと、葉ノードに到達するまで内部ノードから分岐することによって空間インデックスをトラバースすることであって、光線がノードによって定められる境界ボリュームと交差するか否かに基づいて分岐が行なわれる、ことと、光線が交差する境界ボリュームを定める１つ又は複数のノードと、空間インデックスをトラバースするときに行なわれる分岐とを示すトラバース履歴を記録することと、光線が葉ノードによって定められる境界ボリューム内に含まれるプリミティブにヒットするか否かを判定することと、光線が葉ノードによって定められる境界ボリューム内に含まれるプリミティブにヒットしない場合、記録されたトラバース履歴を用いて空間インデックスを再トラバースすることとを含む。
【００１４】
本発明の第３の態様によると、システムが提供される。このシステムは、一般に、３次元シーンの境界ボリュームを定めるノードを有する空間インデックスと、第１の処理要素であって、一般に、シーン内に光線を生成させ、葉ノードに到達するまで内部ノードから分岐することによって空間インデックスをトラバースし、光線がノードによって定められる境界ボリュームと交差するか否かに基づいて分岐が行なわれ、光線が交差する境界ボリュームを定める１つ又は複数のノードと、空間インデックスをトラバースするときに行なわれる分岐とを示すトラバース履歴を記録し、光線が葉ノードによって定められる境界ボリューム内に含まれるプリミティブにヒットするか否かを判定し、光線が葉ノードによって定められる境界ボリューム内に含まれるプリミティブにヒットしない場合、記録されたトラバース履歴を用いて空間インデックスを再トラバースするように構成された第１の処理要素とを含む。
【発明を実施するための最良の形態】
【００１５】
ここで、本発明の好ましい実施形態が、ほんの一例として添付の図面を参照して説明される。
【００１６】
本発明の実施形態は、空間インデックス構造を通る光線のトラバース履歴を記録し、空間インデックスを通る光線の、記録されたトラバース履歴を用いるための技術及びシステムを提供する。画像処理システムは、最初に、光線が空間インデックスをトラバースするとき、光線がどのノードと交差するかを判定することができる。光線が空間インデックスをトラバースするとき、ノード交差判定の結果を記録することができ、記録された判定を光線と関連付けることができる。さらに、画像処理システムは、空間インデックスを構成するノードに対応するプリミティブに当たる何らかの確率に基づいて、トラバーサル経路を決定することができる。このトラバーサル経路を記録し、光線と関連付けることもできる。画像処理システムが、後に空間インデックスを再トラバースすることを必要とする場合に、記録されたトラバース履歴を使用して、光線−ノード交差を再計算する必要性をなくし、正しくないトラバーサル経路の判定を排除することができる。
【００１７】
以下において、本発明の実施形態を参照する。しかしながら、本発明は、説明される特定の実施形態に制限されるものではないことを理解すべきである。代わりに、異なる実施形態に関連しようとしまいと、以下の特徴及び要素のいずれの組み合わせも、本発明を実装し、実行するものと考えられる。さらに、種々の実施形態において、本発明は、従来技術に優る多数の利点を提供する。しかしながら、本発明の実施形態は、他の可能な解決法及び／又は従来技術に優る利点を達成できるが、所定の実施形態によって特定の利点が達成されるかどうかは、本発明の制限ではない。従って、以下の側面、特徴、実施形態及び利点は、単なる例証にすぎず、特許請求の範囲において明示的に列挙される場合を除いて、添付の特許請求の範囲の要素又は制限と考えられるものではない。同様に、「本発明」への言及は、ここに開示される本発明の何らかの主題の一般化として解釈されるものではなく、特許請求の範囲において明示的に列挙される場合を除いて、添付の特許請求の範囲の要素又は制限と考えられるものではない。
【００１８】
例示的なプロセッサ・レイアウト及び通信ネットワーク
図１は、本発明の一実施形態によるマルチコア処理要素１００を示す。マルチコア処理要素１００は、複数の基本的スループット・エンジン１０５（ＢＴＥ）を含む。ＢＴＥ１０５は、複数の処理スレッドと、コア・キャッシュ（例えば、Ｌ１キャッシュ）とを含むことができる。各々のＢＴＥ内に配置された処理スレッドは、共有されるマルチコア処理要素キャッシュ１１０（例えば、Ｌ２キャッシュ）にアクセスすることができる。
【００１９】
ＢＴＥ１０５はまた、複数のインボックス１１５にもアクセスすることができる。インボックス１１５は、メモリマッピングされたアドレス空間とすることができる。各ＢＴＥ１０５内に配置された処理スレッドにインボックス１１５をマッピングすることができる。ＢＴＥ内に配置された各スレッドは、メモリマッピングされたインボックスを有することができ、かつ、他の全てのメモリマッピングされたインボックス１１５にアクセスすることができる。インボックス１１５は、ＢＴＥ１０５が使用する低遅延、高帯域幅の通信ネットワークを構成する。
【００２０】
ＢＴＥは、互いに通信し、データ処理作業をＢＴＥ間で再配分するためのネットワークとして、インボックス１１５を用いることができる。幾つかの実施形態については、例えば、ＢＴＥ１０５による処理の結果を受信するために、通信ネットワーク内で別個のアウトボックスを使用することができる。他の実施形態については、インボックス１１５は、アウトボックスとして働くこともでき、例えば、１つのＢＴＥ１０５が処理機能の結果を別のＢＴＥ１０５のインボックスに直接的に書き込んだ場合、別のＢＴＥ１０５がその結果を使用することになる。
【００２１】
画像処理システムの総合性能は、ＢＴＥ１０５がどれくらい良好に作業を分割し、再配分できるかに関係し得る。インボックス１１５のネットワークを用いて、フレーム間コヒーレンシを有さないＢＴＥ通信情報パケットにより共有のマルチコア処理要素キャッシュ１１０を破損することなく、作業を収集し、これを他のＢＴＥ１０５に配分することができる。１フレーム当たり何百万もの三角形をレンダリングすることができる画像処理システムは、このように接続された多数のＢＴＥ１０５を含むことができる。
【００２２】
本発明の一実施形態においては、１つのＢＴＥ１０５のスレッドを、作業負荷マネージャ（workload manager）に割り当てることができる。画像処理システムは、種々のソフトウェア及びハードウェア・コンポーネントを用いて、３次元シーンから２次元画像をレンダリングすることができる。本発明の一実施形態によると、画像処理システムは、作業負荷マネージャを用いて、この画像処理システムにより出された光線を用いて空間インデックスをトラバース（traverse）することができる。図４に関して以下に更に説明されるように、比較的大きな３次元シーンをより小さな境界ボリューム（bounding volume）に分割するために、空間インデックスが使用される、ツリー型（tree  type）データ構造として実装することができる。画像処理のために光線追跡法を用いる画像処理システムは、空間インデックスを用いて、光線−境界ボリューム交差を速やかに判断することができる。本発明の一実施形態においては、作業負荷マネージャは、空間インデックスを用いて、光線−境界ボリューム交差テストを行なうことができる。
【００２３】
本発明の一実施形態においては、マルチコア処理要素１００上のマルチコア処理要素ＢＴＥ１０５の他のスレッドは、ベクトル・スループット・エンジンとすることができる。作業負荷マネージャは、光線−境界ボリューム交差を判定した後、インボックス１１５を介して複数のベクトル・スループット・エンジンのうちの１つに光線を出す（送る）ことができる。次いで、ベクトル・スループット・エンジンは、光線が境界ボリューム内に含まれるプリミティブと交差するか否かを判定することができる。ベクトル・スループット・エンジンはまた、光線が通過したピクセルの色の決定に関係する操作を行なうこともできる。
【００２４】
図２は、本発明の一実施形態によるマルチコア処理要素のネットワーク２００を示す。図２はまた、マルチコア処理要素１００のＢＴＥ１０５の１つのスレッドが作業負荷マネージャ２０５である、本発明の一実施形態も示す。本発明の一実施形態によると、マルチコア処理要素のネットワーク２００内の各マルチコア処理要素２２０１−Ｎは、１つの作業負荷マネージャ２０５１−Ｎを含むことができる。本発明の一実施形態によると、マルチコア処理要素のネットワーク２００内の各プロセッサ２２０はまた、複数のベクトル・スループット・エンジン２１０を含むこともできる。
【００２５】
本発明の一実施形態によると、作業負荷マネージャ２０５１−Ｎは、他の作業負荷マネージャ２０５１−Ｎ及び／又は他のマルチコア処理要素２２０のベクトル・スループット・エンジン２１０と通信するために、高速バス２２５を用いることができる。各ベクトル・スループット・エンジン２１０は、高速バス２２５を用いて、他のベクトル・スループット・エンジン２１０又は作業負荷マネージャ２０５と通信することができる。作業負荷マネージャ・プロセッサ２０５は、高速バス２２５を用いて、画像処理に関連するタスクを収集し、これを他の作業負荷マネージャ・プロセッサ２０５に配分し、及び／又はタスクを他のベクトル・スループット・エンジン２１０に配分することができる。高速バス２２５を用いることにより、作業負荷マネージャ２０５１−Ｎは、作業負荷マネージャ２０５の通信と関連したデータ・パケットでキャッシュ２３０に影響を与えることなく、通信することが可能になる。
【００２６】
例示的な３次元シーン
図３は、画像処理システムによってレンダリングされる例示的な３次元シーン３０５である。３次元シーン３０５内には、物体３２０が存在し得る。図３の物体３２０は、異なる幾何学的形状を有する。図３には４つの物体３２０だけ示されているが、典型的な３次元シーンにおける物体の数は、これより多いことも少ないこともある。一般に、３次元シーンは、図３に示されるよりもずっと多くの物体を有する。
【００２７】
図３に見られるように、物体は、様々な幾何学的形状及びサイズを有する。例えば、図３の１つの物体は、角錐３２０Ａである。図３の他の物体は、箱形３２０Ｂ−Ｄである。最近の多くの画像処理システムにおいては、物体は、より小さな幾何学的形状（例えば、正方形、円、三角形等）に分割されることが多い。次いで、多数のより小さく単純な幾何学的形状によって、より大きな物体が表される。これらのより小さな幾何学的形状は、多くの場合、プリミティブ（primitive）と呼ばれる。
【００２８】
シーン３０５内には、光源３２５Ａ−Ｂも示されている。これらの光源は、シーン３０５内に配置された物体３２０を照射することができる。さらに、シーン３０５内の光源３２５及び物体３２０の位置によって、これらの光源は、シーン３０５内の物体上に影を落とすことがある。
【００２９】
画像処理システムによって、３次元シーン３０５を２次元ピクチャにレンダリングすることができる。画像処理システムはまた、２次元ピクチャをモニタ３１０上に表示させることもできる。モニタ３１０は、最終的な２次元ピクチャをレンダリングするために、異なる色の多数のピクセル３３０を用いることができる。
【００３０】
３次元シーン３０５を２次元ピクチャにレンダリングするために画像処理システムによって用いられる１つの方法は、光線追跡法と呼ばれる。光線追跡法は、観察者の視点３１５から３次元シーン３０５に向けて光線を「出す（issuing）」又は「発射する（shooting）」画像処理システムによって達成される。これらの光線は、通常の光線と類似した特性及び振る舞いを有する。
【００３１】
図３において、観察者３１５の位置から発し、３次元シーン３０５を通過する１つの光線３４０を見ることができる。光線３４０が観察者３１５から３次元シーン３０５に進むとき、この光線３４０は、画像処理システムが最終的な２次元ピクチャをレンダリングする平面を通過する。図３では、この平面はモニタ３１０で表される。光線３４０がこの平面、即ちモニタ３１０を通過する点は、ピクセル３３５で表される。
【００３２】
上記に簡単に説明したように、大部分の画像処理システムは、モニタ３１０上に最終的なシーンをレンダリングするために、何十万（何百万でないとしても）ものピクセルのグリッド３３０を使用する。それぞれのピクセルは、モニタ３１０上に最終的な合成の２次元ピクチャをレンダリングするために、異なる色を表示することができる。３次元シーンから２次元ピクチャをレンダリングするために光線追跡による画像処理方法を用いる画像処理システムは、出された光線が３次元シーンにおいて遭遇する色を計算する。次いで、画像処理システムは、光線が観察者から３次元シーンに向かう途中で通過したピクセルに、光線が遭遇した色を割り当てる。
【００３３】
１ピクセル当たりに出される光線の数は、変化し得る。幾つかのピクセルは、レンダリングされる特定のシーンに対して出される多数の光線を有することができる。その場合、そのピクセルの最終的な色は、該ピクセルに対して出された光線の全てからの各色の寄与によって決定される。他のピクセルは、２次元ピクチャ内のピクセルの、結果的に得られる色を決定するために出された単一の光線だけを有することがある。幾つかのピクセルは、画像処理システムによって出された如何なる光線も有さず、その場合、画像処理システム内のアルゴリズムによって、それらのピクセルの色を決定し、近似させ、又は割り当てることができる。
【００３４】
２次元ピクチャ内のピクセル３３５の最終的な色を決定するために、画像処理システムは、光線３４０がシーン内の物体と交差するか否かを判定する必要がある。光線がシーン内の物体と交差しない場合には、それにはデフォルトの背景色（例えば、日中の空又は夜空を表す、青又は黒）を割り当てることができる。逆に、光線３４０が３次元シーンを通過する際に、光線３４０が物体に当たることがある。光線がシーン内の物体に当たる際、光線が通過するピクセルに対して、その物体の色を割り当てることができる。しかしながら、ピクセルに割り当てる前に、その物体の色を決定しなければならない。
【００３５】
元の光線３４０が当たった物体の色には、多くの要因が寄与し得る。例えば、３次元シーン内の光源が物体を照射することがある。さらに、物体の物理的性質が、その物体の色に寄与することがある。例えば、物体が反射性又は透明である場合には、他の非光源物体がこの物体の色に寄与することもある。
【００３６】
３次元シーン内の他の物体からの効果を判定するために、元の光線３４０が物体と交差した点から２次光線を出すことができる。例えば、１つのタイプの２次光線は、影光線（shadow ray）とすることができる。影光線を用いて、元の光線３４０が物体と交差した点への光の寄与を判定することができる。別のタイプの２次光線は、透過光線（transmitted ray）とすることができる。透過光線を用いて、どの色又は光が物体の本体を透過できるのかを判定することができる。さらに、第３のタイプの２次光線は、反射光線（reflected ray）とすることができる。反射光線を用いて、どの色又は光が物体上で反射されるのかを判定することができる。
【００３７】
上述されたように、１つのタイプの２次光線は、影光線とすることができる。各影光線は、元の光線と物体の交点から３次元シーン３０５内の光源まで追跡することができる。影光線が光源に到達する前に別の物体に遭遇することなく、光線が光源に到達する場合には、光源は、元の光線が物体に当たった点で、元の光線が当たった物体を照射するであろう。
【００３８】
例えば、影光線３４１Ａは、元の光線３４０が物体３２０Ａと交差した点から出て、光源３２５Ａに向かう方向に進むことができる。影光線３４１Ａは、シーン３０５内の他のいずれの物体にも遭遇せずに、光源３２５Ａに到達する。従って、光源３２５Ａは、元の光線３４０が物体３２０Ａと交差した点において物体３２０Ａを照射することになる。
【００３９】
他の影光線は、元の光線が物体に当たった点と、３次元シーン内の他の物体によって遮断される光源との間に、それらの経路を有することができる。元の光線が当たった物体上の点と光源との間の経路を妨げる物体が不透明である場合には、光源は、元の光線が物体に当たった点において物体を照射しない。従って、光源は、元の光線の色に寄与せず、その結果、２次元ピクチャ内のレンダリングされるピクセルの色にも寄与し得ない。しかしながら、物体が半透明であるか又は透明である場合には、光源は、元の光線が物体に当たった点において物体を照射することができる。
【００４０】
例えば、影光線３４１Ｂは、元の光線３４０が物体３２０Ａと交差した点から出て、光源３２５Ｂに向かう方向に進むことができる。この例では、影光線３４１Ｂの経路は、物体３２０Ｄによって遮断される。物体３２０Ｄが不透明である場合には、光源３２５Ｂは、元の光線３４０が物体３２０Ａと交差した点において物体３２０Ａを照射することはない。しかしながら、物体３２０Ｄが半透明又は透明である場合には、光源３２５Ｂは、元の光線３４０が物体３２０Ａと交差した点において物体３２０Ａを照射することができる。
【００４１】
別のタイプの２次光線は、透過光線である。元の光線３４０と交差した物体が透明又は半透明の特性を有する（例えば、ガラス）場合、画像処理システムによって、透過光線を出すことができる。透過光線は、元の光線が物体に当たった角度に対してある角度で物体を通過する。例えば、透過光線３４４は、元の光線３４０と交差した物体３２０Ａを通過するように見える。
【００４２】
別のタイプの２次光線は、反射光線である。元の光線と交差した物体が反射特性を有する場合には（例えば、金属仕上げ）、どの色又は光が物体に反射し得るかを判定するために、画像処理システムによって反射光線が出される。反射光線は、元の光線が物体と交差した角度に対してある角度で、物体から遠ざかるように進む。例えば、どの色又は光が、元の光線３４０が交差した物体３２０Ａに反射され得るかを判定するために、画像処理システムによって反射光線３４３を出すことができる。
【００４３】
全ての２次光線（例えば、影光線、透過光線、反射光線など）の色及び光の寄与全体により、元の光線が通過したピクセルの最終的な色がもたらされることになる。
【００４４】
例示的なｋｄ木
光線追跡法を実施する際に遭遇する１つの問題は、出された光線がレンダリングされるシーン内のいずれかの物体と交差するか否かを、速やかに且つ効率的に判定することである。光線の交差をより効率的に判定するための当業者には周知の１つの方法は、空間インデックスを使用するものである。空間インデックスは、３次元シーン又は世界を、プリミティブを含んでいることも含んでいないこともある、より小さなボリューム（３次元シーン全体に比べて小さな）に分ける。次いで、画像処理システムは、これらの小さなボリュームの既知の境界を用いて、光線が、これらの小さなボリューム内に含まれるプリミティブと交差するか否かを判定することができる。光線がプリミティブを含むボリュームと交差する場合には、そのボリューム内に含まれるプリミティブの既知の位置及び寸法に対して、光線の軌跡を用いて光線交差テストを行なうことができる。光線が特定のボリュームと交差しない場合には、そのボリューム内に含まれるプリミティブに対して光線−プリミティブ交差テストを行なう必要はない。さらに、光線が、プリミティブを含まない境界ボリュームと交差する場合には、その境界ボリュームに対して光線−プリミティブ交差テストを行なう必要はない。従って、必要となり得る光線−プリミティブ交差テスト数を低減させることで、空間インデックスを用いることにより、光線追跡を用いる画像処理システムの性能が大きく向上する。異なる空間インデックス加速データ構造の幾つかの例は、八分木（octree）、ｋ次元木（kd-Tree、ｋｄ木）及び二分空間分割木（binary space partioning tree、ＢＳＰ木）である。幾つかの異なる空間インデックス構造が存在するが、本発明の実施形態を説明する便宜上、以下の例においてはｋｄ木が用いられる。しかしながら、当業者であれば、本発明の実施形態は、異なるタイプの空間インデックスの任意のものにも適用し得ることを容易に理解するであろう。
【００４５】
ｋｄ木は、シーン全体又は空間をより小さなボリュームに分割するために、軸平行の（axis aligned）境界ボリュームを使用する。つまり、ｋｄ木は、既知の軸線と平行な分割用平面を用いて、シーンが含む３次元空間を分けることができる。分割用平面は、１つのより大きな空間をより小さな境界ボリュームに分割する。より小さな境界ボリュームは、協働してシーン内の空間全体を構成する。ｋｄ木構築アルゴリズムを用いて、画像処理システムにより、１つのより大きな境界ボリュームを２つのより小さな境界ボリュームに分割する（分ける）という決定を行なうことができる。
【００４６】
１つの境界ボリュームをより小さなボリュームにいつ分割するかを決定するための１つの基準は、境界ボリューム内に含まれるプリミティブの数とすることができる。つまり、１つの境界ボリュームが所定の閾値よりも多くのプリミティブを含む限り、木構築アルゴリズムは、より多くの分割用平面を引くことによってボリュームの分割を続行することができる。１つの境界ボリュームをより小さなボリュームにいつ分割するかを決定するための別の基準は、１つの境界ボリューム内に含まれる空間の量とすることができる。さらに、境界ボリュームの分割を続行するという決定はまた、境界ボリュームを生成する平面と交差することができるプリミティブの数に基づいてもよい。
【００４７】
シーンの分割は、ノード、岐及び葉から構成される２分木（binary tree）構造で表すことができる。この木の中の各内部ノードは、１つの比較的大きな境界ボリュームを表すことができ、ノードは、サブノードへの分岐を含むことができ、これは、比較的大きな境界ボリュームを分割用平面によって分割した後に結果として得られる２つの比較的小さな分割済みボリュームを表すことができる。軸平行のｋｄ木において、各々の内部ノードは、２つの他のノードへの分岐だけを含むことができる。内部ノードは、１つ又は２つの葉ノードへの分枝（即ち、ポインタ）を含むことができる。葉ノードとは、それ以上小さなボリュームに細分されないノードであり、プリミティブへのポインタを含む。内部ノードはまた、さらに細分される他の内部ノードへの分枝を含むこともできる。内部ノードはまた、どの軸線に沿って分割用平面が引かれたのか、及び軸線上のどの点において分割用平面が引かれたのかを決定するのに必要な情報を含むこともできる。
【００４８】
例示的な境界ボリューム
図４（Ａ）−図４（Ｃ）は、画像処理システムによってレンダリングされる２次元空間と、対応するｋｄ木とを示す。簡単にするために、ｋｄ木の構築を示すために、２次元シーンが用いられるが、ｋｄ木は、３次元シーンを表すのに用いることもできる。図４（Ａ）−図４（Ｃ）の２次元表示においては、３次元構造で用いられる分割用平面の代わりに分割線が用いられ、境界ボリュームの代わりに境界領域が示される。しかしながら、当業者であれば、この概念は、物体を含む３次元シーンにも容易に適用できることをすぐに理解するであろう。
【００４９】
図４（Ａ）は、モニタ３１０上に表示される最終的なピクチャ内でレンダリングされるプリミティブ４１０を含む２次元シーン４０５を示す。シーン全体量を表す最大のボリュームは、境界ボリューム１（ＢＶ１）に包含される。対応するｋｄ木において、これは、根ノード（root node）又はワールド・ノード（world node）とも呼ばれる最上位のノード４５０で表すことができる。画像処理システムの一実施形態においては、境界ボリュームが、例えば２つより多くのプリミティブを含む場合、画像処理システムは、境界ボリュームをより小さな境界ボリュームに分割し続けることができる。前述のように、境界ボリュームをより小さな境界ボリュームに分割し続けるという決定は、多くの要因に基づき得るが、この例においては説明を簡単にするために、境界ボリュームを分割し続けるという決定は、プリミティブの数だけに基づくものとする。図４（Ａ）に見られるように、ＢＶ１は６つのプリミティブを含み、よって、ｋｄ木構築アルゴリズムは、ＢＶ１をより小さな境界ボリュームに分割することができる。
【００５０】
図４（Ｂ）は、図４（Ａ）に示されたものと同じ２次元シーン４０５を示す。しかしながら、図４（Ｂ）では、木構築アルゴリズムは、ＢＶ１を２つのより小さな境界ボリュームＢＶ２及びＢＶ３に分割している。ＢＶ１の分割は、ｘ軸上の点ｘ１において分割用平面ＳＰ１４１５を引くことによって行なわれた。このＢＶ１の分割はまた、内部ノード即ち親ノードＢＶ１４５０の下にある、それぞれＢＶ２及びＢＶ３に対応する２つのノード４５５及び４６０として、ｋｄ木内にも反映されている。ここで、ＢＶ１を表す内部ノードは、これらに限定されるものではないが、ＢＶ１の下にある２つのノード（例えば、ＢＶ２及びＢＶ３）へのポインタ、どの軸線に沿って分割用平面が引かれたのか（例えば、ｘ軸）、及び軸線上のどの点において分割用平面が引かれたのか（例えば、点ｘ１において）といった情報を格納することができる。
【００５１】
ｋｄ木構築アルゴリズムは、境界ボリュームＢＶ３が所定の閾値より多いプリミティブ（例えば、２つより多いプリミティブ）を含むという理由で、境界ボリュームＢＶ３の分割を続けることができる。しかしながら、ｋｄ木構築アルゴリズムは、境界ボリュームＢＶ２が、ある数以下のプリミティブ（例えば、２つのプリミティブ４１０Ａだけ）を含んでいるという理由で、境界ボリュームＢＶ２の分割を続けることができない。ＢＶ２のように、それ以上分割又は細分されないノードは、葉ノードと呼ばれる。
【００５２】
図４（Ｃ）は、図４（Ｂ）に示されたものと同じ２次元シーン４０５を示す。しかしながら、図４（Ｃ）では、ｋｄ木構築アルゴリズムは、ＢＶ３を２つの小さな境界ボリュームＢＶ４及びＢＶ５に分割している。ｋｄ木構築アルゴリズムは、ｙ軸上の点ｙ１において分割用平面を用いてＢＶ３を分割した。ＢＶ３は２つのサブノードに分割されたので、今やＢＶ３を内部ノードと呼ぶことができる。ＢＶ３の分割はまた、それぞれＢＶ４及びＢＶ５に対応する、２つの葉ノード４６５及び４７０として、ｋｄ木内にも反映されている。ＢＶ４及びＢＶ５が表すボリュームは、これ以上小さな境界ボリュームに分割されないので、これらは、葉ノードである。２つの葉ノードＢＶ４及びＢＶ５は、ｋｄ木内で分割された境界ボリュームを表す内部ノードＢＶ３の下に位置する。
【００５３】
ＢＶ３を表す内部ノードは、これらに限定されるものではないが、２つのノード（即ち、ＢＶ４及びＢＶ５）へのポインタ、どの軸線に沿って分割用平面が引かれたのか（即ち、ｙ軸）、及び、軸線上のどの点において分割用平面が引かれたのか（即ち、点ｙ１において）といった情報を格納することができる。
【００５４】
ｋｄ木構築アルゴリズムは、今やシーン内に位置する全ての境界ボリュームが、境界ボリューム内に含み得る最大の所定数以下のプリミティブを含むという理由で、境界ボリュームの分割を停止することができる。葉ノードは、各葉が表す境界ボリューム内に含まれるプリミティブへのポインタを含むことができる。例えば、葉ノードＢＶ２はプリミティブ４１０Ａへのポインタを含み、葉ノードＢＶ４はプリミティブ４１０Ｂへのポインタを含み、葉ノードＢＶ５はプリミティブ４１０Ｃへのポインタを含むことができる。
【００５５】
光線追跡を用いる画像処理システムは、空間インデックス（ｋｄ木）をトラバースするために、作業負荷マネージャ２０５を用いることができる。ｋｄ木のトラバースは、行なうべき又は進むべきｋｄ木の下位レベルのノード（サブノード）への分岐を選択し、光線が、サブノード内に含まれるいずれかのプリミティブと交差するか否かを判定することを含むことができる。作業負荷マネージャ２０５は、出された光線の座標及び軌跡を使用して、ｋｄ木をトラバース又はナビゲートすることができる。作業負荷マネージャ２０５は、光線−境界ボリューム交差テストを実行することによって、光線がｋｄ木構造内のノードで表される境界ボリュームの１つの平面と交差するか否かを判定することができる。光線がプリミティブだけを含む境界ボリューム（即ち、葉ノード）と交差する場合には、作業負荷マネージャ２０５は、光線−プリミティブ交差テストのために、光線及び関連した情報をベクトル・スループット・エンジン（ＶＴＥ）２１０に送ることができる。光線がその境界ボリューム内のプリミティブと交差するか否かを判定するために、光線−プリミティブ交差テストを実行することができる。この方法は、シーン内に含まれるプリミティブの各々について光線−プリミティブ交差テストを実行するのに比べると、光線がシーン内の物体と交差するか否かを判定するのに必要な光線−プリミティブ交差テストの数が少なくなる。
【００５６】
結果として得られるｋｄ木構造又は他の空間インデックス構造は、プロセッサ・キャッシュ２３０内に格納することができる。プロセッサ・キャッシュ２３０内に格納するために、ｋｄ木、及びｋｄ木を含む対応するデータのサイズを最適化することができる。ｋｄ木をプロセッサ・キャッシュ２３０内に格納することにより、作業負荷マネージャ２０５は、画像処理システムが光線を出す度にメモリからｋｄ木を取り出す必要なしに、画像処理システムが出した光線を用いてｋｄ木をトラバースすることが可能になる。
【００５７】
例示的なｋｄ木及び対応するノード履歴データ構造
空間インデックス（例えば、ｋｄ木）内の内部ノードの深さの各レベルについて、ノード履歴を格納することができる。ノード・レベル履歴を用いて、境界ボリューム−光線交差テスト及びｋｄ木のトラバースに関する情報を格納することができる。前のテスト及びｋｄ木のトラバース結果を保存することによって、画像処理システムは、前のテスト結果を利用し、光線−プリミティブ交差を判定するのに必要な処理量を低減させることができる。本発明の一実施形態によると、光線について説明する情報と共に（例えば、これに添付して）送られるノード履歴データ構造のニブル内に、各レベルについてのノード履歴ビットを格納することができる。
【００５８】
図５は、本発明の一実施形態による、例示的なｋｄ木５５０及び対応する例示的なノード履歴データ構造５４５を示す。例示的なｋｄ木５５０は、８つのレベルの内部ノードの深さ（Ｌ１−Ｌ８）を含むものとして示される。本発明の一実施形態によると、対応するノード履歴５４５は、ｋｄ木５５０が含む内部ノード・レベル（Ｌ１−Ｌ８）と同じ数のニブルを含むことができる。従って、本発明の一実施形態によると、ノード履歴５４５は、８つのニブル（即ち、３２ビット）を含むことができ、これらのニブルは、光線−交差テスト及びｋｄ木のトラバース履歴を記録することができる。本発明の一実施形態によると、最上位（most significant）のニブルＬ１は、ｋｄ木５５０内の第１のレベルＬ１（即ち、根ノード又はワールド・ノード）に対応することができ、最下位（least significant）のニブルＬ８は、ｋｄ木５５０内の最下位レベルＬ８に対応することができる。
【００５９】
ノード履歴データ構造５４５内の各ニブルは、４ビットを含むことができる。各ニブルの２つの最上位ビット５２５は、内部ノードの左下に位置するノードに対応することができる。各ニブルの２つの最下位ビット５３０は、内部ノードの右下に位置するノードに関連することができる。光線−境界ボリューム交差テストを実行し、光線が、内部ノードの左下にあるノードで表される境界ボリュームと交差していた場合、各ニブルの最上位ビット５０５を（例えば、ハイ状態（high state）即ち「１」に）設定することができる。ｋｄ木をトラバースする間、作業負荷マネージャ２０５が、内部ノードの左下に位置するノードに「分岐した」又はトラバースした場合、最上位ビットから２番目の（second most significant）ビット５１０を設定することができる。ここで用いられる経路は、ｋｄ木をトラバースし、その経路に沿って内部ノード又は葉ノードに到達した場合に「採用された（taken）」と考えられる。
【００６０】
光線−境界ボリューム交差テストを実行し、光線が、内部ノードの右下に位置するノードで表される境界ボリュームと交差していた場合には、最上位ビットから３番目の（third most significant）ビット５１５を設定することができる。ｋｄ木をトラバースする間、作業負荷マネージャ２０５が、内部ノードの右下に位置するノードへの分岐を「行なった」又はこれをトラバースした場合、最下位ビット５２０を設定することができる。
【００６１】
従って、１レベル当たり１ニブルの履歴ビットが、光線−境界ボリューム交差テストの結果と、経路が採用されたか否かを記録するのに必要とされる全てである。勿論、任意の特定のレベルにおいてどのノードが到達したかを判定するために、先行するレベルにおける履歴ビットを調べる必要がある。従って、所定の光線と交差するプリミティブを有する葉ノードを探索するときに、特定のレベルにおける全ての経路が採用されると、そのレベルとそのレベルより下のノード履歴ビットを消去し、より上位のレベルからの異なる経路を採用する必要がある。
【００６２】
ノード履歴を用いる例示的なｋｄ木トラバースアルゴリズム
図６は、ｋｄ木をトラバースする方法６００を示すフローチャートである。この方法６００は、画像処理システムが、３次元シーン内に追跡される光線を出すステップ６０５で開始する。画像処理システムは、出された光線を用いてｋｄ木をトラバースすることに関連したタスクを実行するために、作業負荷マネージャ２０５を用いることができる。次に、ステップ６１０において、画像処理システムは、根ノード又はワールド・ノードで開始する。根ノードから、画像処理システムは、画像処理システムが分岐することを選択できるステップ６１５に進むことができる。
【００６３】
図７を参照して以下により詳細に説明されるように、ステップ６１５は、画像処理システム内で、ノード履歴ビットに従ってｋｄ木をトラバースするサブルーチンを開始することができる。
【００６４】
図７は、ノード履歴ビット５００に従ってｋｄ木をトラバースする方法を示すフローチャートである。この方法７００は、画像処理システムが内部ノード（即ち、サブノードへの分岐を含むノード）に到達するステップ７０５で開始する。次に、ステップ７１０において、画像処理システムは、出された光線に対応するノード・レベル履歴情報が存在するか否かを判定することができる。存在しない場合には、画像処理システムは、ステップ７１５に進むことができ、そこで、作業負荷マネージャ２０５は、現在トラバースされている内部ノードから分岐されたノードで表される境界ボリュームの各々について、光線−境界ボリューム交差テストを行なうことができる。次に、ステップ７２０において、画像処理システムは、ノード・レベルに対応するノード・レベル履歴ビットを更新することができる。具体的には、画像処理システムは、光線が、内部ノードから分岐されたノードの各々に対応する境界ボリュームと交差したか否かを表す「ヒット・ノード」ビット５０５及び５１５を更新することができる。次に、画像処理システムは、ステップ７２５に進むことができる。
【００６５】
ステップ７２５において、画像処理システムは、光線が、ノードによって分岐される、ノードで表わされる両方の境界ボリュームと交差したか否かを判定することができる。両方の境界ボリュームと交差した場合には、画像処理システムは、ステップ７２７に進み、そこで、光線の起点に最も近いノードへの経路を選択することができる。しかしながら、１つのノードだけとしか交差しなかった場合には、ステップ７２９において、画像処理システムは、交差したノードへの経路を選択することができる。ステップ７２７及び７２９の後、画像処理システムは、ステップ７３０に進むことができる。ステップ７３０において、画像処理システムは、ノード・レベル履歴内の取得されたビットを更新し、画像処理システムによって選択された経路／分岐を反映させる。ステップ７３０の後、ステップ７３５において、画像処理システムは、選択された経路を採用する／選択された分岐を行なう。
【００６６】
ステップ７１０において、画像処理システムが、光線がノード・レベル履歴情報を有していたと判断した場合には、画像処理システムは、ステップ７４０に進むことができる。ステップ７４０において、光線が境界ボリュームと交差したが、画像処理システムはその境界ボリュームへの経路を採用しなかった／分岐が行なわれかったと、画像処理システムが前に判断していた場合には、画像処理システムは最下位ノードの深さを判定することができる。
【００６７】
ノード・レベル履歴情報を格納した光線は、画像処理システムが空間インデックス（例えば、ｋｄ木）をトラバースした光線であるが、この光線は、光線−プリミティブ交差テストが実行された境界ボリューム内のプリミティブとは交差しなかった（即ち、ミスが発生した(miss)）。ミスの発生後、境界ボリュームと交差したが分岐が行なわれなかった最下位の内部ノード深さを判定するために、画像処理システムは、ノード・レベル履歴における「１０」の発生を詳細に探すことができる。画像処理システムは、ノード・レベル履歴の最上位の２ビットを構成する対、又はノード・レベル履歴の最下位の２ビットを構成する対のいずれかにおいて、「１０」を探すことができる。これら２つの対のいずれにおける「１０」も、光線がそのノードで表される境界ボリュームと交差したが、そのノード・レベルの下の境界ボリュームの１つについて、光線プリミティブ交差テストがまだ実行されていない（即ち、その対応する経路が採用されなかった）ことを表す。
【００６８】
例えば、ｋｄ木の特定のレベルにおいて、光線が、内部ノードの下にあるサブノードで表される両方の境界ボリュームと交差することがある。画像処理システムは、内部ノードの右下へのサブノードで表される境界ボリュームより前に、光線が、ｋｄ木の内部ノードの左下へのサブノードで表される境界ボリュームが交差したと、ｋｄ木の前のトラバース中に判断していた。画像処理システムは、左のサブノードを採用し、こうしたトラバースを示すように履歴ビットを更新していた。
【００６９】
一例として、本発明の一実施形態によると、各ノード・レベルがニブルで表される場合、この内部ノード・レベルに対応するノード履歴ビットは「１１１０」となり、これは、左のノードにヒットした、左のノードに分岐した、右のノードにヒットした、右のノードにまだ分岐されていない、と読むことができる。内部ノード・レベル履歴内に「１０」で表されるように、内部ノードの右下へのサブノードは、光線と交差したが、光線−プリミティブ交差についてテストされていない。
【００７０】
境界ボリュームと交差した分岐されていない最下位のノード・レベル履歴を判定した後、画像処理システムは、ステップ７４５に進むことができる。ステップ７４５において、画像処理システムは、境界ボリュームと交差したが分岐が行なわれない最下位のノード・レベルより下にある内部ノード・レベルについての、全てのノード・レベル履歴ビットを消去することができる。このステップは、画像処理システムがｋｄ木をトラバースするとき、正しくないトラバース経路の決定を行なった時点より下にある分岐、ノード、又は葉ノードについて前に記録されたあらゆる履歴が、そのｋｄ木の将来のトラバースに影響を与えないことを保証する。
【００７１】
次に、ステップ７５０において、画像処理システムは、ノード・レベル履歴に基づいて、根ノードから、境界ボリュームと交差したが分岐されていない最下位のノード深さまで、ｋｄ木をトラバースすることができる。ステップ７５０は、画像処理システムによって、下位にある内部ノード又は葉ノードへの適切なポインタが、キャッシュ２３０から取り出されることを保証することができる。次に、ステップ７５５において、画像処理システムは、画像処理システムにより分岐が行なわれていないノードへの経路／分岐（即ち、境界ボリュームと交差したが、分岐が行なわれていない最下位のノード・レベルについてのノード履歴において「１０」で表される経路）を選択する。ステップ７５５の後、画像処理システムは、ステップ７３０に進む。ステップ７３０において、画像処理システムは、ノード・レベル履歴内の取得されたビットを更新し、画像処理システムが選択した経路を反映させる。ステップ７３０の後、ステップ７３５において、画像処理システムは、選択された経路を採用する。
【００７２】
経路を採用した後、画像処理システムは、方法６００に戻る。ステップ６２０において、画像処理システムは、方法６００を再開する。ステップ６２０において、画像処理システムは、画像処理システムが、採用された経路によって葉ノードに到達したか否かを判定する。到達しなかった場合には、画像処理システムはステップ６１５に戻り、分岐することを選択する。
【００７３】
しかしながら、ステップ６２０において、作業負荷マネージャ２０５が、採用された経路によって画像処理システムが葉ノードに到達したと判定した場合には、作業負荷マネージャ２０５は、光線−プリミティブ交差テストのために、インボックス１１５又はネットワーク２２５を介して、光線、光線履歴データ構造及び葉ノード情報（例えば、葉ノードにより境界付けられるプリミティブへのポインタ）をベクトル・スループット・エンジン２１０に送ることができる。
【００７４】
ベクトル・スループット・エンジン２１０は、光線−プリミティブ・テストを実行し、葉ノードで表される境界ボリュームにヒットした光線が、その境界ボリューム内に含まれるプリミティブのいずれかに実際にヒットするか否かを判定することができる。光線が境界ボリューム内のプリミティブのいずれかにヒットした場合、ベクトル・スループット・エンジン２１０は、色（例えば、プリミティブの色）を光線に割り当てることができる。しかしながら、ベクトル・スループット・エンジン２１０はまた、光線が境界ボリューム内のプリミティブのいずれにもヒットしなかったと判断することもある。
【００７５】
しばらくして、ベクトル・スループット・エンジン２１０は、光線と、その光線が境界ボリューム内に含まれるプリミティブにヒットしたか又はミスしたかを示す表示とを戻す。次いで、ステップ６３０において、画像処理システムは、ベクトル・スループット・エンジン２１０によって戻された情報が、光線がプリミティブにヒットしたことを示すか否か、或いは、光線が境界ボリューム内に含まれるプリミティブの全てにミスしたか否かを判定することができる。
【００７６】
光線がプリミティブにヒットした場合、画像処理システムは、ベクトル・スループット・エンジン２１０から戻された色を、光線が通過したモニタ３１０上のピクセル３３５に割り当てることができる。次いで、画像処理システムは、続けて別の光線を出し、ｋｄ木をトラバースすること又は３次元シーンから２次元ピクチャをレンダリングすることに関連した他の操作を行なうことができる。
【００７７】
光線が境界ボリューム内に含まれるプリミティブにミスしたとベクトル・スループット・エンジン２１０が判定した場合、作業負荷マネージャ２０５は、ステップ６１０に戻ることができる。ステップ６１０において、作業負荷マネージャ２０５は、根ノードで開始するｋｄ木のトラバースを再開し、光線履歴は、不必要に光線−境界ボリューム交差テストを再実行するのを回避するのを助け、所定の光線と交差しなかったプリミティブを有する葉ノードに通じる経路へと木をトラバースするのを回避することができる。
【００７８】
ｋｄ木のトラバースの例
図８は、境界ボリューム（ＢＶ１−ＢＶ５）に分割された例示的なシーン８００を示す。図８は、ｋｄ木の構築を示すために図４に用いられたシーンと類似している。図８には、画像処理システムによって出された光線８０５も示される。光線８０５を用いて、ｋｄ木をトラバースすることができる。光線は、第１の点８１０においてＢＶ２と交差し、第２の点８１５においてＢＶ２を出る。光線は、第２の点８１５においてＢＶ３及びＢＶ４と交差し、第３の点８２０においてＢＶ３及びＢＶ４を出る。
【００７９】
図９（Ａ）は、図８における分割されたシーン８００に対応する例示的なｋｄ木９００である。図９（Ａ）はまた、光線８０５及びｋｄ木９００の第１のレベル（即ち、根ノードＢＶ１）と関連した例示的な内部ノード履歴データ構造の第１のニブル９０５も示す。さらに、光線８０５及びｋｄ木の第２のレベルと関連した例示的な内部ノード履歴データ構造の第２のニブル９１０も示される。図９（Ａ）は、作業負荷マネージャ２０５が光線８０５によってｋｄ木のトラバースを開始する前の、ノード履歴データ構造の最初の状態（全てのビットがアサートされていない）を示す。
【００８０】
図５の方法５００に関して説明されたように、画像処理システムによって光線８０５が出された後、作業負荷マネージャ２０５は、ｋｄ木９００のトラバースに関連する操作を行なうことができる、例えば、方法６００のステップ６１５に説明されたように、作業負荷マネージャ２０５は、光線−境界ボリューム交差テストを実行し、光線８０５が根ノードＢＶ１の子ノードＢＶ２及びＢＶ３に対応する境界ボリュームと交差するか否かを判断することができる。図８に見られるように、光線８０５は、子ノードＢＶ２及びＢＶ３に対応する境界ボリュームの両方と交差する。光線８０５は、第１の点８１０においてＢＶ２と交差し、第２の点８１５においてＢＶ２を出る。光線は、第２の点８１５においてＢＶ３と交差し、第３の点８２０においてＢＶ３を出る。
【００８１】
作業負荷マネージャ２０５が光線−境界ボリューム交差テストを実行した後、作業負荷マネージャ２０５は、根ノードＢＶ１レベルに対応するノード履歴ニブル９０５を更新し、光線−境界ボリューム交差テストの結果を反映させることができる。根ノード履歴ニブル９０５の更新が、図９（Ｂ）に示される。光線８０５が子ノードＢＶ２及びＢＶ３の両方と交差するという事実によって、作業負荷マネージャ２０５は、子ノードＢＶ２及びＢＶ３の各々に対応するノード・レベル履歴内の「ヒット・ノード」ビットをアサートすることができる。従って、作業負荷マネージャ２０５は、根ノード・レベル履歴９０５の最上位ビットをアサートし、光線８０５が左の子ノード（ＢＶ２）に対応する境界ボリュームにヒットしたことを表すことができる。さらに、作業負荷マネージャ２０５は、最上位ビットから３番目（third most significant bit）のビットをアサートし、光線８０５が右の子ノード（ＢＶ３）に対応する境界ボリュームにヒットしたことを表すことができる。
【００８２】
次に、作業負荷マネージャ２０５は、境界ボリューム交差テストに基づいて、ｋｄ木９００の下の採用すべき経路を決定することができる。図９（Ｃ）に示されるように、本発明の一実施形態においては、この場合は根ノードである親ノードＢＶ１の子ノードＢＶ２及びＢＶ３の両方が光線と交差していた場合、作業負荷マネージャ２０５は、光線と交差した第１の（例えば、最も近い）境界ボリュームに進むことができる。直近の例では、光線８０５は、最初にＢＶ２と交差する。従って、作業負荷マネージャ２０５は、ＢＶ２へのトラバースを行ない、根ノード・レベル履歴９０５を更新して、作業負荷マネージャ２０５がＢＶ２への分岐を「行なった」（即ち、左のノードを採用した）ことを示すことができる。根ノードについてのノード・レベル履歴の更新が、図９（Ｃ）に示される。
【００８３】
今や、作業負荷マネージャ２０５は、ＢＶ２が葉ノード（即ち、他のノードに分岐されないノード）であるか否かを判定することができる。ノードＢＶ２は葉ノードであるので、作業負荷マネージャ２０５は、図９（Ｄ）に示されるように、光線８０５、光線についてのノード履歴９０５及び９１０、並びに葉ノードＢＶ２内に含まれるプリミティブへのポインタをベクトル・スループット・エンジン２１０に送ることができる。次いで、ベクトル・スループット・エンジン２１０は、光線−プリミティブ交差テストを実行し、光線８０５がＢＶ２内に含まれるいずれかのプリミティブと交差するか（ヒットするか）否かを判定することができる。
【００８４】
図８に示されるように、光線８０５は、ＢＶ２内に位置するいずれのプリミティブとも交差しない。従って、ベクトル・スループット・エンジン２１０は、光線及び対応する履歴を作業負荷マネージャ２０５に戻し、光線８０５がＢＶ２内に位置するいずれのプリミティブとも交差しなかった（即ち、ミス）ことを示すことができる。
【００８５】
光線がベクトル・スループット・エンジン２１０から戻された後、作業負荷マネージャ２０５は、光線ノード・レベル履歴が情報を含んでいると判断することができる。作業負荷マネージャ２０５は、ｋｄ木のトラバースを容易にするために、その履歴を用いることができる。作業負荷マネージャ２０５は、光線履歴を用いて、境界ボリュームと交差したが、対応する分岐が行なわれないことを示す最下位レベルのノード履歴を判定することができる。このことは、ノード履歴内に「１０」を含む最下位ノード履歴を判定することによって達成することができる。従って、図９Ｅに示されるように、作業負荷マネージャ２０５は、ｋｄ木の根ノード・レベルが、境界ボリュームと交差したが分岐が行なわれていない、ｋｄ木における最下位レベルであると判断することができる。このことは、右の分岐に対応する境界ボリュームにおけるヒットを示すが、右への分岐が行なわれなかったことを示す「１０」を含む根ノード・レベル履歴９０５を調べることによって、判断することができる。根ノード・レベルが最下位レベルであると判断した後、作業負荷マネージャ２０５は、根ノードより下の全てのノード・レベルについてのノード・レベル履歴を消去することができる。
【００８６】
次に、作業負荷マネージャ２０５は、根ノードＢＶ１においてｋｄ木９００のトラバースを開始することができる。次いで、作業負荷マネージャ２０５は、ノード・レベル履歴９０５を用いて、ｋｄ木９００のトラバースを助けることができる。根ノードについてのノード・レベル履歴９０５に基づいて、作業負荷マネージャは、まだ行なわれていない分岐を行なうことを決定することができる。ノード・レベル履歴９０５を調べることによって、作業負荷マネージャ２０５は、左右両方のノードが光線８０５と交差したと判断することができる。このことは、根ノード・レベル履歴ニブル９０５の第１及び第３のビットを調べることによって判断することができる。これらのビットの両方がアサートされ（即ち「１」である）、よって、両方が前の光線−境界ボリューム交差テストにおいて交差したと判断された。さらに、作業負荷マネージャ２０５は、作業負荷マネージャが、前に左のサブノートへの分岐を「行なった」（即ち、ＢＶ２内に含まれるプリミティブに対して、テストされる光線を送った）と判断することができる。このことは、アサートされるノード・レベル履歴の第２のビットを調べることによって判断される。従って、作業負荷マネージャは、光線８０５と交差した右のノード（即ち、ＢＶ３）に進むことができない、又はこれへの他の分岐を行なうことができない。図９（Ｆ）に示されるように、作業負荷マネージャ２０５はまた、根ノード・レベル履歴ニブル９０５の取得された右のビットを更新し、ＢＶ３へのトラバースを示すことができる。
【００８７】
作業負荷マネージャ２０５は、ノードＢＶ３にトラバースされたノードが葉ノードであるか否かを判定することができる。図９Ｅに見られるように、ノードＢＶ３は葉ノードではなく、内部ノードである。従って、作業負荷マネージャ２０５は、光線−境界ボリューム交差テストを実行し、光線８０５が、ＢＶ３の下にあるノード又はこれより下位のノード（即ち、ＢＶ４及びＢＶ５）に対応する境界ボリュームと交差するか否かを判定することができる。
【００８８】
図８に示されるように、光線８０５は、点８１５においてＢＶ４と交差するが、この光線は、ＢＶ５とは交差しない。従って、光線−境界ボリューム交差テストの結果は、光線８０５がＢＶ５と交差しないことを示し得る。ここで作業負荷マネージャ２０５は、ＢＶ３のノード・レベル履歴９１０を更新し、光線−境界ボリューム交差テストの結果を反映させることができる。従って、図９（Ｆ）に示されるように、作業負荷マネージャ２０５は、ＢＶ３ノード・レベル履歴９１０内の最上位のビット位置に「１」を配置し、又はビットをアサートし、光線がＢＶ３と交差するという事実を反映させることができる。次に、作業負荷マネージャ２０５は、ＢＶ３ノード・レベル履歴９１０に基づいて、どの分岐／経路を「採用する」かを判断することができる。
【００８９】
ＢＶ３ノード・レベル履歴９１０を調べることによって、作業負荷マネージャ２０５は、ＢＶ３の下の１つのノードだけが光線８０５と交差することを判断することができ、よって、作業負荷マネージャ２０５は、交差したノードＢＶ４にトラバースすることができる。図９（Ｇ）に示されるように、作業負荷マネージャ２０５は、ＢＶ３ノード・レベル履歴９１０を更新し、ＢＶ３ノード・レベル履歴９１０内の最上位ビットから２番目のビットをアサートすることによって（左に分岐されたことを示す）、ノードＢＶ３からノードＢＶ４へのトラバースを反映させることができる。
【００９０】
ここで作業負荷マネージャ２０５は、左の子ノードＢＶ４が葉ノード（即ち、ノードが子を持たない）であるか否かを判定することができる。ノードＢＶ４は葉ノードであるので、今や作業負荷マネージャ２０５は、光線８０５、光線についてのノード・レベル履歴（９０５及び９１０）、並びに葉ノードＢＶ４内に含まれるプリミティブへのポインタをベクトル・スループット・エンジン２１０に送ることができる。次いで、ベクトル・スループット・エンジン２１０は、光線−プリミティブ交差テストを実行し、光線８０５がＢＶ４内に含まれるいずれかのプリミティブと交差する（ヒットする）か否かを判断することができる。図６に見られるように、光線８０５は、ＢＶ４内のプリミティブと交差する。従って、ベクトル・スループット・エンジン２１０は、光線８０５が通過したピクセルに色を割り当て、その情報を作業負荷マネージャ２０５に戻すことができる。
【００９１】
当業者であれば、光線が葉ノードのプリミティブと交差するとき、例えば、反射、透過、屈折等に対応する付加的な光線を生成できることを理解するであろう。このような光線を生成する反復プロセスは周知のものであるが、最終的なピクセル値を求めるために、ここに説明される技術を用いて、これらの光線の各々を効果的に追跡することができる。
【００９２】
結論
本発明の実施形態は、空間インデックス構造を通る光線のトラバース履歴を記録し、空間インデックスを通る光線の記録されたトラバース履歴を使用するための技術及びシステムを提供する。画像処理システムは、最初に、光線が空間インデックスをトラバースするとき、この光線がどのノードと交差するかを判断することができる。ノード交差判定の結果は、光線が空間インデックスをトラバースするときに記録することができ、記録された判定を光線と関連付けることができる。さらに、画像処理システムは、空間インデックスを構成するノードに対応するプリミティブに当たる何らかの確率に基づいて、トラバース経路を決定することができる。このトラバース経路を記録し、光線と関連付けることもできる。画像処理システムが、後に空間インデックスのトラバースを必要とする場合には、記録されたトラバース履歴を使用して、光線−ノード交差を再計算する必要性を排除し、正しくないトラバース経路の判定の反復を排除することができる。
【００９３】
上記は本発明の実施形態に向けられるが、その基本的な範囲から逸脱することなく、本発明の他の及び更に別の実施形態を考え出すことができ、その範囲は、上記の特許請求の範囲によって決定される。
【図面の簡単な説明】
【００９４】
【図１】本発明の一実施形態によるマルチコア処理要素を示す。
【図２】本発明の一実施形態によるマルチコア処理要素のネットワークを示す。
【図３】本発明の一実施形態による、画像処理システムによってレンダリングされる例示的な３次元シーンである。
【図４】（Ａ）本発明の一実施形態による、画像処理システムによってレンダリングされる２次元空間と、画像処理システムによって生成される対応する空間インデックスとを示す。（Ｂ）本発明の一実施形態による、画像処理システムによってレンダリングされる２次元空間と、画像処理システムによって生成される対応する空間インデックスとを示す。（Ｃ）本発明の一実施形態による、画像処理システムによってレンダリングされる２次元空間と、画像処理システムによって生成される対応する空間インデックスとを示す。
【図５】本発明の一実施形態による、空間インデックスと、空間インデックスを通る光線のトラバース履歴を格納するための対応するデータ構造とを示す。
【図６】本発明の一実施形態による、空間インデックスをトラバースする方法を示すフローチャートである。
【図７】本発明の一実施形態による、空間インデックスをトラバースする方法を示すフローチャートである。
【図８】本発明の一実施形態による、画像処理システムによってレンダリングされる例示的な２次元空間である。
【図９】（Ａ）本発明の一実施形態による、空間インデックスを通る光線のトラバースを示す。（Ｂ）本発明の一実施形態による、空間インデックスを通る光線のトラバースを示す。（Ｃ）本発明の一実施形態による、空間インデックスを通る光線のトラバースを示す。（Ｄ）本発明の一実施形態による、空間インデックスを通る光線のトラバースを示す。（Ｅ）本発明の一実施形態による、空間インデックスを通る光線のトラバースを示す。（Ｆ）本発明の一実施形態による、空間インデックスを通る光線のトラバースを示す。（Ｇ）本発明の一実施形態による、空間インデックスを通る光線のトラバースを示す。
【図１】
2009545044.tif 000003
【図２】
2009545044.tif 000004
【図３】
2009545044.tif 000005
【図４】
2009545044.tif 000006
【図５】
2009545044.tif 000007
【図６】
2009545044.tif 000008
2009545044.tif 000009
【図７】
2009545044.tif 000010
【図８】
2009545044.tif 000011
【図９】
2009545044.tif 000012
【国際調査報告】
2009545044.tif 000013
2009545044.tif 000014
2009545044.tif 000015