複雑な動的３次元シーンをレイトレーシング法により写真現実的に表示する装置
本発明は、複雑な動的３次元シーンをレイトレーシング法により写真現実的に表示する装置に関する。該装置は少なくとも１つのプログラム可能レイトレーシングプロセッサを有しており、該プロセッサにおいては、
・専用のトラバース命令、及び／又は
・ベクトル算術命令、及び／又は
・レイトレーシング加速構造を形成するための命令、及び／又は
・レイトレーシング法を実行する際、光線の射出時に、既に光線が交差したオブジェクト又は三角形を前記光線が何度も交差するのを抑制するために用いられる少なくとも１つの判定ユニット（メールボックス）が実施され、
前記装置は、複数のスレッドを並列処理することができ、且つ、複数のスレッドを自動的に同期して処理することができるように構成されており、
前記装置は、ｎレベルのキャッシュ階層及び／又は仮想メモリ管理及び／又はメインメモリとの直接接続を使用することができる。
・専用のトラバース命令、及び／又は
・ベクトル算術命令、及び／又は
・レイトレーシング加速構造を形成するための命令、及び／又は
・レイトレーシング法を実行する際、光線の射出時に、既に光線が交差したオブジェクト又は三角形を前記光線が何度も交差するのを抑制するために用いられる少なくとも１つの判定ユニット（メールボックス）が実施され、
前記装置は、複数のスレッドを並列処理することができ、且つ、複数のスレッドを自動的に同期して処理することができるように構成されており、
前記装置は、ｎレベルのキャッシュ階層及び／又は仮想メモリ管理及び／又はメインメモリとの直接接続を使用することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、リアルタイムレイトレーシングハードウェアアーキテクチャを用いて、複雑な動的３次元シーンを高い画像リフレッシュレートで２次元ディスプレイに表示することのできる装置に関する。動的シーンとは、カメラ位置の他に、表示すべきオブジェクトのジオメトリもフレームごとに変化しうるシーンである。本発明は、とりわけ、オブジェクトの階層構造をサポートしている、すなわち、主シーンが各々別のオブジェクトから構成された複数のオブジェクトから成っており、この入れ子を任意に続けることができるという点で優れている。階層の個々のレベルに存在しているオブジェクトは個別にも合同でも動くことができる。これにより、高い動特性をもつ複雑なシーンを生成することができ、シーンの複数の位置において同じオブジェクトを使用することにより、メモリ内でのシーンの表現を小さく保つことができる。
【０００２】
本発明に従ってこの入れ子になったオブジェクトレベルを実現するためには、公知のレイトレーシングパイプラインのハードウェアによる実施が、光線をオブジェクト内へ変換するハードウェア的に実現された変換ユニットで拡張される。このユニットはハードウェア資源の最適利用のために１つだけ設けられており、オブジェクト空間変換の他に、光線と三角形との交点の計算、一次光線の生成、及び二次光線の生成のために使用される。
【０００３】
本発明に従って、標準的なプロセッサカーネルと１つ又は複数のレイトレーシング命令の組合せとから成る新式のプロセッサアーキテクチャを使用することにより、レイトレーシング専用に設計されたプロセッサの使用を通して、本発明はユーザにシステムの完全なプログラム可能性を提供する。このレイトレーシングプロセッサの使用はさまざまなレイトレーシング法のプログラミングを可能にする。シーンの原始オブジェクトはプログラム可能に構成されているので、今日のグラフィックスカードとは違って、光線とスプライン曲面との交点を計算する専用のアルゴリズムをプログラムすることにより、スプライン曲面の使用も可能である。今日のラスタ化ハードウェアの場合と同様に、通常、表面のさまざまなシェーディングモデルをプログラムすることができる。
【０００４】
ディスプレイに画像データを出力するために、共通のフレームバッファとＺバッファを使用することにより本発明を従来の技術によるラスタ化ハードウェアと組み合わせることもできる。
【０００５】
背景技術
現在、３次元シーンの表示に関する背景技術は、ラスタ化法とレイトレーシング法の２つの主要セクターに分けられる（Computer Graphics / Addison-Wesley ISBN 020 1848406参照）。
【０００６】
とりわけコンピュータグラフィックスカードにおいて使用される公知のラスタ化法は、シーンの各ジオメトリをフレームバッファとＺバッファに投影するという原理に基づいている。このために、ピクセルの色値及び輝度値がフレームバッファに記憶され、幾何学的な深度値はＺバッファに記憶されるが、それはＺバッファ内にある直前の幾何学値が新たな値よりも大きい（観察者からより離れている）場合に限る。これにより、より近いオブジェクトがより遠いオブジェクトに上書きされ、プロセスの進行に従って実際に可視のオブジェクトしかフレームバッファ内に写し取られないことが保証される。
【０００７】
しかしながら、この方法は、数百万のオブジェクトを持つような費用のかかるシーンの場合には、今までに知られているハードウェアではシーンをリアルタイムに表示することができないという決定的な欠点を有している。というのも、通常は、シーンのすべての三角形（オブジェクト）を投影することが必要となるからである。さらには、秒単位で数十億の書込み動作が行われるフレームバッファとＺバッファが必要となる。この書込みの際、画像形成のために、大部分のピクセルは１フレームにつき何度も上書きされる。観察者にとってより遠いピクセルをより近いオブジェクトのピクセルによって上書きすることの結果として、既に計算されたデータが捨てられるため、最適なシステム性能を実現することができない。
【０００８】
影は今日のラスタ化ハードウェア上で費用のかかる技術を用いれば計算することができるが、複雑なシーンの場合には、正確性に関して問題を生じる。曲面での反射及び光の屈折の計算はこの技術では物理的に正しく実現することができない。
【０００９】
第２の方法であるレイトレーシング法によれば、性能を向上させるような改善が達成される。レイトレーシング法はその写真現実的な画像で知られるが、計算が複雑であることでも知られている。レイトレーシングの基本的な考え方は物理的な光分布モデルと親近性がある（Computer Graphics / Addison-Wesley ISBN 020 1848406参照）。
【００１０】
現実の環境においては、光は光源から放射され、物理法則に従ってシーン内に分布する。周囲環境の画像はカメラによって捕らえることができる。レイトレーシングは、それとは逆に、観察者位置を表すカメラから光源へと光を追跡する。このために、画像の各ピクセルに対して、ピクセルを照明する方向に仮想的な光線が射出される。この光線の射出はレイキャスティングと呼ばれる。光線がオブジェクトに当たると、ピクセルの色が、とりわけ、光線の当たったオブジェクトの色と表面の法線と衝突点から見える光源とから計算される。衝突点から見えるこれらの光源は、各光源から衝突点へ射出される二次光線を追跡することによって求めることができる。この影光線が光源と衝突点の間のオブジェクトに当たれば、点は光源に対して影の中にある。
【００１１】
この方法は、上記の影の計算の他に、反射光又は屈折した二次光線を計算することにより、光の反射及び屈折の計算も可能にする。さらに、ほぼ任意のサイズのシーンを処理し、表示することができる。その理由は加速構造の使用にある。これは、仮想光線で迅速にシーンを「射つ」又はトラバースすることのできる適切なデータ構造を用いた特別な方法である。途中で、命中候補となりうる幾つかのオブジェクトが選択され、これにより衝突点が迅速に見つけ出される。理論的な研究によれば、レイトレーシング法の計算量は平均してシーンのサイズに対して対数的に成長することが示されている。つまり、シーンのオブジェクトの個数が２乗されても、計算コストは２倍にしかならないことを意味している。
【００１２】
典型的な加速構造は、例えば、正則グリッド、ｋ−Ｄツリー、オクツリー、バウンディングボリューム階層である（Computer Graphics / Addison-Wesley ISBN 020 1848406参照）。これらすべての方法は、空間を多数の部分空間に分割し、このような各部分空間に関してこの部分空間におけるジオメトリを記憶するという考えに基づいている。そして、トラバース法は部分空間から部分空間へと光線を追跡し、光線はつねにちょうどその部分空間内にあるオブジェクトと交差する。４つの方法は部分空間の配列の仕方が異なっているだけである。正則グリッドでは、空間は同じサイズのサイコロ形の部分空間に分割されている。具体的には、図７の図を参照されたい。他の３つの方法は空間の再帰的な分割に基づいている。ｋ−Ｄツリー法では、開始空間が任意の場所で再帰的に軸平行に分割される。具体的には、図８を参照されたい。この空間の分割は再帰的データ構造（バイナリツリー）に記憶される。オクツリーと呼ばれる第３の方法も同様に再帰的であるが、観察される部分空間はつねに同サイズの８つの長方形部分空間に分割される。具体的には、図９を参照されたい。バウンディングボリューム階層は空間をｎ個の任意のボリュームに分割する。それどころか、このｎ個のボリュームはオーバーラップしてもよい。これは他の方法では許されないことである。
【００１３】
ラスタ化法とは違って、現在のところ、レイトレーシング法を実現するハードウェア解決手段は存在しておらず、比較的高い計算能力と多くの計算時間とを要するソフトウェアベースのシステムしか存在していない。計算の時間的規模を分かり易くするために、次のことに注意されたい。すなわち、この方法に従って個々の静止画像を生成するには、画像の複雑度と、今のところ従来技術によるＰＣハードウェアと共に使用されているソフトウェアとによっては、数秒から数時間までの計算時間が必要となる。動画像の計算には、相応して多くの計算時間及び／又は専用の大型計算機の使用が必要となる。
【００１４】
ザールラント大学のコンピュータグラフィックス講座は、２０台を超す計算機のクラスタを使用するソフトウェアベースのリアルタイムレイトレーシングシステムを開発した。
【００１５】
アメリカ合衆国特許第６，５９７，３５９Ｂ１号には、レイトレーシング法のためのハードウェア解決手段が記載されているが、静的なシーンに限定されている。
【００１６】
アメリカ合衆国特許第５，９３３，１４６号にも、レイトレーシング法のためのハードウェア解決手段が記載されているが、これも静的なシーンに限定されている。
【００１７】
ザールラント大学のコンピュータグラフィックス講座の論文"SaarCOR - A Hardware Architecture for Ray-Tracing"には、レイトレーシングのためのハードウェアアーキテクチャが記載されているが、これもまた静的なシーンに限定されている。
【００１８】
ザールラント大学のコンピュータグラフィックス講座の論文"A Simple and Practical Method for Interactive Ray-Tracing of Dynamic Scenes"には、レイトレーサにおいて動的シーンをサポートするソフトウェア手法が記載されている。しかしながら、このソフトウェア方法はオブジェクトの１つのレベルしか使用しておらず、したがって複数のレベルへの入れ子を実施することができない。
【００１９】
上記の背景技術は、今のところ、複雑な動的シーンをリアルタイムで表示することのできるソフトウェア解決手段もハードウェア解決手段も提供していない。公知のラスタ化法では、能力の限界は表示すべきオブジェクトの個数にある。
【００２０】
レイトレーシングシステムはたしかに多くの三角形を表示することができるが、必要とされる事前計算のゆえに、限定的にしか位置を変えることができないという点で制限されている。数十億の三角形から成るシーンは非常に高い計算能力と多くのメモリを必要とし、高速で複雑な大型計算機又はクラスタ解決手段でしか処理することができない。
【００２１】
それゆえ、既存のパーソナルコンピュータハードウェアでは、動的なリアルタイムレイトレーシングシステムを実現することはできない。上記のクラスタ解決手段はコスト上の理由から特別用途に限定されることもあり得る。
【００２２】
これに対して、本発明の課題は、写真現実的な表示が得られるように、複雑な動的３次元シーンにおいてレイトレーシング法をより迅速に−有利にはリアルタイムでも−実行することのできる装置を提供することである。
【００２３】
この課題は、請求項１による装置、すなわち、装置が少なくとも１つのプログラム可能レイトレーシングプロセッサを有しており、該プロセッサにおいて、
・専用のトラバース命令、及び／又は
・ベクトル算術命令、及び／又は
・レイトレーシング加速構造を形成するための命令、及び／又は
・レイトレーシング法を実行する際、光線の射出時に、既に光線が交差したオブジェクト又は三角形を前記光線が何度も交差するのを抑制するために用いられる少なくとも１つの判定ユニット（メールボックス）が実施されるように構成された装置によって解決される。
【００２４】
上記装置の構造は、複数のスレッドを並列処理することができ、且つ、複数のスレッドを自動的に同期して処理することができるように構成されている。さらに、上記装置はｎレベルのキャッシュ階層及び／又は仮想メモリ管理及び／又はメインメモリとの直接接続を使用することができる。この装置は、有利には、ＦＰＧＡとして、及び／又はＡＳＩＣ技術及び／又は他の論理ベースの半導体技術又は離散集積論理回路において、又はこれらの技術の組合せにおいて実現することができる。
【００２５】
判定ユニットをより詳細に論じるために、図２を参照されたい。図２からは、リストユニットがメールボックスで拡張されることが見て取れる。このメールボックスは、既に光線と交差したオブジェクト又は三角形をマークすることにより、光線の射出の際に三角形又はオブジェクトが光線と何度も交差するのを防ぐ。これにより、非常に多くの光線オブジェクト交点又は光線三角形交点の計算をしなくても済み、計算が加速する。メールボックスは、メモリキャッシュとは違って、メモリへのメモリ問合せを防ぐのではなく、交点計算を防ぐ一種の交点計算キャッシュと見なすことができる。メールボックスの実施には、４ウェイキャッシュのような標準的なキャッシュ法を使用することができる。
【００２６】
請求項２は、複雑な動的３次元シーンをレイトレーシング法により写真現実的に表示する装置に関しており、該装置は、少なくとも１つの専用トラバースユニット、少なくとも１つのリストユニット、レイトレーシング法を実行する際、光線の射出時に、既に光線が交差したオブジェクト又は三角形を前記光線が何度も交差するのを抑制するために用いられる少なくとも１つの判定ユニット（メールボックス）、少なくとも１つの交点計算ユニット、加速構造を形成するための少なくとも１つのユニット、少なくとも１つの変換ユニット、及び／又は、線形方程式系を解くための少なくとも１つのユニットを有しており、複数の光線又はスレッドを並列処理することができ、複数の光線又はスレッドを自動的に同期して処理することができ、動的オブジェクト内に動的オブジェクトの任意個数のレベルを実現することができ、前記装置は、ｎレベルのキャッシュ階層及び／又は仮想メモリ管理及び／又はメインメモリとの直接接続を使用することができる。
【００２７】
請求項３による実施形態では、請求項２による実施形態との相違点として、請求項２の少なくとも１つの変換ユニット、及び／又は、線形方程式系を解くための少なくとも１つのユニット、及び／又は少なくとも１つの交点計算ユニットが、請求項３では、既に請求項１で説明されたレイトレーシングプロセッサで補完されている。
【００２８】
ソフトウェア的に定義された加速構造及び方法を相応するハードウェア構造において実施する、このレイトレーシング法に基づいた３次元動的シーンを写真現実的に表示するための装置は、優先的にリアルタイムで使用するためのものである。
【００２９】
シーン内に任意の無秩序な動きを実現するには、画像列の各画像について、加速構造を新たに計算しなければならない。このことは、大きなシーンの場合には、シーンの全体的なジオメトリを扱わなければならないため、莫大な計算コストを意味する。その際には、シーンのサイズに対して対数的な計算量という利点が消えてしまう。
【００３０】
前記論文"A Simple and Practical Method for Interactive Ray-Tracing"に記載されているこの問題に対する解決手段は、シーンをオブジェクトに分割し、専らこのオブジェクトの動きを全体として許可することである。この場合には、シーンのオブジェクト全体にわたるトップレベル加速構造と各オブジェクトに対するそれぞれ１つのボトムレベル加速構造の２つの加速構造が必要となる。この場合、オブジェクトはシーン内のオブジェクトのインスタンスという形で位置測定される。
【００３１】
オブジェクトとオブジェクトのインスタンスとの違いは、オブジェクトのインスタンスはオブジェクトと変換とから構成されているという点にある。この変換は、オブジェクトをシーンの任意の位置に移すアフィン関数である。アフィン変換はさらにオブジェクトのスケーリング、回転、及び剪断（英語では、ｓｈｅａｒｉｎｇ）を可能にする。以下では、簡単のため、混同の可能性がない場合には、オブジェクトのインスタンスに対してもオブジェクトという概念を使用する。
【００３２】
光線は、可能な命中オブジェクト（光線が当たるオブジェクト）が見つかるまで、まずトップレベル加速構造を通ってトラバースする（光線がシーン中を追跡する）。つぎに、光線はオブジェクトの局所座標系内へ変換され、さらに原始オブジェクトとの衝突点が見つかるまで、オブジェクトのボトムレベル加速構造内をトラバースする。原始オブジェクトは、さらなる構造を有していないオブジェクトである。レイトレーサの場合、原始オブジェクトは通常は三角形と球である。
【００３３】
この方法は実用において非常に良好に機能するが、それもオブジェクトの個数があまり大きくない間だけに限られている。なぜならば、各画像のトップレベル加速構造は新たに構築されなければならないからである。この加速構造の新たな構築は、この加速構造内のオブジェクトが動いた場合に必要となる。
【００３４】
本発明は、上述したオブジェクトへのシーンの分割を再帰的にサポートするハードウェア解決手段である。つまり、本発明は原始オブジェクトから成るオブジェクトに限定されず、このオブジェクトがそれ自体複数のオブジェクトから構成され得る複数のオブジェクトから再び合成されることも許す。図１は、どのようにしてオブジェクトの複数のレベルから木が生成され得るかを示している。まず、レベル１のオブジェクトとして葉がモデル化される。この葉は何倍にもインスタンシングされ、枝に配置される。これにより、さらなるオブジェクトが発生するが、今はレベル２のオブジェクトが発生する。これらの小さな枝は再びレベル３のオブジェクトであるより大きな枝又は木などへと何倍にもインスタンシングされる。ここではオブジェクト内にオブジェクトの複数のレベルが存在しており、同一のジオメトリを何度も使用しているため、シーンの表現が小さいということに注意されたい。
【００３５】
請求項２に従って本発明において使用されるレイキャスティングの方法は、以下の通りである。
【００３６】
光線は、可能な命中オブジェクトが見つかるまで、トップレベルの加速構造をトラバースする。このオブジェクトが原始オブジェクトであれば、光線とオブジェクトの交点が計算される。オブジェクトが原始オブジェクトでなければ、光線はオブジェクトの局所座標系へ変換され、そこでトラバースを再帰的に継続する。
【００３７】
この方法の重要な部分は光線をオブジェクトの局所座標系内へ変換するところである。これにより、原則的に、オブジェクトの位置測定はアフィン変換によって逆行して行われる。つまり、変換された光線はオブジェクトをもはや変換されたものとして見ない。この変換ステップは光線の始点と光線の方向のかなりコストのかかるアフィン変換を必要とする。しかしながら、このために必要な高価なハードウェアユニットはさらに別のタスクにも使用することができる。変換ユニットは、様々な種類の原始オブジェクトとの交点の計算にも、一次光線の計算にも、また様々な種類の二次光線の計算にも使用することができる。
【００３８】
一次光線を計算するために、公知のラスタ化法の場合に似たカメラ変換行列が用いられる。まず、Ｒ＝（（０，０，０），（ｘ，ｙ，１））という形のプレ一次光線、すなわち、始点（０，０，０）と方向（ｘ，ｙ，１）を有する光線が定義される。ここで、ｘ及びｙはピクセルの座標を表しており、一次光線はこの座標に対して計算されなければならない。各カメラ位置と向きとに対して、光線Ｒがカメラのピクセル（ｘ，ｙ）の入射方向に正確に一致するように光線Ｒを変換するアフィン変換が存在する。
【００３９】
原始オブジェクトとの交点を計算するために、光線は、中に正規化された原始オブジェクトを有する空間内へ変換される。原始オブジェクトが三角形である場合には、光線は、例えば、三角形がΔnorm＝（（１，０，０），（０，０，０），（０，１，０））の形を有するように、空間内へ変換される。具体的には、図１０を参照されたい。この変換はアフィン変換によって生じる。それに続く正規三角形との交点の計算は、一般的な場合とは違って、ハードウェアにおいて非常に簡単に解決することができる。三角形の法線が三角形空間内のベクトル（０，０，１）に変換されるように変換が選ばれた場合、光線と三角形の法線とのスカラー積は非常に簡単に三角形空間内で計算される。というのも、光線方向（ｘｔ，ｙｔ，ｚｔ）と三角形法線（０，０，１）とのスカラー積はまさに０*ｘｔ＋０*ｙｔ＋１*ｚｔ＝ｚｔだからである。
【００４０】
さらに、三角形法線を正規三角形空間内の適切な法線に写像することにより、それを表現するのに９つの浮動小数点数しか要さないように変換を選ぶことができる。しかしながら、これは、スカラー積が正規三角形空間内で計算されうる可能性を妨げてしまう。
【００４１】
この正規オブジェクト変換が、例えば、球、平面、平行六面体、円筒、及び他の多くの幾何学形状のような他の種類のオブジェクトにも使用可能であることは、明らかである。それにはそのつどただ１つの別の交点計算ユニットを用意するだけである。
【００４２】
これに関連した大きな利点は、各種類の原始オブジェクトがメモリ内で同一の表現を、つまり、オブジェクト正規空間内への変換を行うアフィン変換を、有していることである。このオブジェクト正規空間内への変換を正規空間変換と呼ぶ。
【００４３】
影光線と反射は、変換ユニットによって適切な変換と適切な光線を計算することにより効率的に計算される。
【００４４】
さらに、変換ユニットを用いて法線（表面に対して垂直なベクトル）を変換することも可能である。いくつかのシェーディングモデルは衝突点におけるジオメトリの法線を必要とするので、この法線変換は必要である。しかしながら、この法線は世界座標系内になければならない。このことは上記の方法においては必ずしも成り立っていない。むしろ、法線は衝突したオブジェクトの局所座標系内で初めて現れる。この法線はこの局所座標系から再び世界座標系内へと変換されなければならない。
【００４５】
しかしながら、この変換ユニットは欠点も有している。アフィン変換は、行列として記憶することができるが、三角形に対してもシーンのオブジェクトに対しても事前計算されなければならないので、三角形の頂点の位置をフレームごとに効率的に変化させることが直ちにはできない。これは今日のグラフィックスカードにおいては頂点シェーダで可能である。頂点シェーダは、空間内の点の動きの計算に最適化されたプログラム可能な専用ユニットである。
【００４６】
これを可能にするためには、データの事前計算から解放されなければならない。したがって、三角形との交点の計算のために、未知数を３つもつ線形方程式系を解く必要がある。これを陽的に解くには確かにより多くの浮動小数点演算を必要とするが、頂点シェーダとの関連では不可欠である。それゆえ、上記の変換ユニットを、線形方程式系を解くユニットで置き換えることが適切である。このユニットは、とりわけ、三角形との交差、又は、光線をオブジェクトの局所座標系へ変換することに使用することができる。
【００４７】
本発明において請求項１に従って使用されるレイトレーシング方法は、請求項２に記載された発明と類似に構成されているが、変換及び交点計算がレイトレーシングプロセッサに対する適切な指示で実施される点で異なっている。これに伴って、特に、オブジェクト光線交点計算のための代替的な方法の使用が可能になる。例えば、プリュッカー光線三角形テストの使用は頂点シェーダの効率的な使用を可能にする。
【００４８】
ディテールの豊富なシーンにおける問題は、特にある方向におけるオブジェクト密度が非常に高い場合に生じる不所望なエイリアシング効果である。その場合、例えば黒い三角形に当たった光線がカメラの最小の動きで突然白い三角形に当たってしまうということが起き得る。このような効果は画像内に時間的及び局部的な雑音を生じさせる。その理由は、レイトレーシングが通常は無限に細い光線を使用しており、ピクセルに影響を与える光は角錐状に拡がり、光線は距離とともに拡がるということを考慮していないことにある。したがって、本来、ピクセルの色を計算するには、この光角錐内にあるすべてのオブジェクトを考慮しなければならないが、それはリアルタイムシステムでは不可能である。そこで、単純化された新しい形態のコーントレーシングが救済策となる。任意に細い光線を考える代わりに、付加的に光線のビーム拡がり角が評価される。したがって、カメラまでの距離に応じて、相応する光線幅を計算することができる。トラバースの際に、光線によってその大部分を覆われる部分空間に遭遇した場合、さらにトラバースすることは状況によっては意味がない。有利には、この箇所で、計算のためにボリューム内部の簡単なジオメトリを使用することができる。その場合、ボリューム内におよそ１００万の三角形があることは無視してよい。これらの三角形は、場合によっては、山脈の壁を形成しているに過ぎず、これは光線の大きさゆえに色平面によっても近似することができる。
【００４９】
しかしながら、三角形が例えばエッフェル塔のような穴だらけの建物をモデル化する場合には、近似として、むしろ構成要素の格子の色と透明度を選ぶべきである。
【００５０】
有利には、このような簡略化されたジオメトリ表現が加速構造においてサポートされる。図６には、そのコンセプトがオクツリーの例で示されている。加速構造内の１つのノードが属している太線で縁取られたボリュームに関して、簡略化されたジオメトリが描かれている。光線はほぼノードの全ボリュームとオーバーラップしているので、この簡略化されたジオメトリが交点計算に使用される。
【００５１】
代替的な方法は、様々なディテールレベルを有するシーンのオブジェクトを保管しておくことである。つまり、様々な解像度又は三角形の個数を有するオブジェクトをモデル化し、さらに、オブジェクトからカメラまでの距離に応じて、ディテールの豊富な又は単純化されたオブジェクトを使用する。
【００５２】
上述の固定的に有線接続されたハードウェアベースのレイトレーシングパイプラインの場合、このレイトレーシングパイプラインをプログラム可能に構成するには費用がかかるということが不利と見なされるかもしれない。ソフトウェアレイトレーシングアプローチに比べると、ハードウェアベースのパイプラインは非常に融通性がなく、専門的である。
【００５３】
そこで、レイトレーシング法に特化させたＣＰＵの開発が救済策となる。この専用レイトレーシングプロセッサは、例えばＲＩＳＣプロセッサのような標準ＣＰＵから構成され、その命令セットは専用命令で拡張される。特に、加速構造を光線でトラバースさせるトラバース命令は重要である。さらに、この方法のいくつかの箇所では、主に３次元空間内で行われるコストのかかる算術演算が必要とされる。それゆえ、今日よく用いられているＳＳＥ２命令セットに似たベクトル算術ユニットをＣＰＵに備え付けることが有効である。
【００５４】
ＣＰＵのさらなる最適化は、方法の並列化の可能性を利用することによって達成することができる。これによれば、ＣＰＵ上で複数のスレッド（プログラムの流れ）を非常に効果的に走らせることができ、このことがＣＰＵの活用度と有効性を明らかに高める。このことはとりわけメモリ待ち時間に関して当てはまる。あるスレッドがメモリ問合せをした場合、問合せの間、別のスレッドを実行することができる。図５には、このようなＣＰＵの構造の一例を見ることができる。
【００５５】
動的シーンでは、各フレームについて加速構造の再計算をしなければならないため、加速構造を形成するための専用命令でＣＰＵの命令セットを拡張する必要がある。加速構造を形成する際、オブジェクトが属すべき所与の部分空間内にあるのか否かを判定しなければならない場合がしばしばある。加速構造の形成を最適化する専用ユニットは、非常に簡単に計算される事前判定を下すことによって、必要な計算を加速することができる。部分空間として、ｘ、ｙ、及びｚ軸に対して垂直な６つの境界面をもつボックスがよく使用される。このようなボックスはその頂点によって特徴付けることができる。それどころか、２つの点を定義するだけで十分である。三角形がこのボックスの中にあるのか否かの確認／判定は、多くの場合、単純に点の座標を比較することにより行われる。三角形が例えばＸ軸方向にボックスのずっと左側にある場合、三角形の３つの頂点のＸ座標はすべてボックスの頂点の最小Ｘ座標よりも小さい（図１３参照）。また、別の多くの配置も、例えば、三角形が完全にボックス内にあるのか否かも、同様に判定することができる。判定が可能でない場合には、ＳＡＰ（Separating Axis Theorem）のようなコストのかかる数学上の式を適用しなければならない。ボックスが別のボックスとオーバーラップするか否かの判定も同様に頂点比較によって判定することができる。
【００５６】
さらなる最適化のために、レイトレーシング法を実行する際、光線の射出時に、既に光線が交差したオブジェクト又は三角形を光線が何度も交差するのを防ぐ判定ユニットが使用される。これは、図２に見られるようなリストユニットをメールボックスで拡張することによって行われる。このメールボックスは、既に光線と交差したオブジェクト又は三角形をマークすることにより、光線の射出の際に三角形又はオブジェクトが光線と何度も交差するのを防ぐ。これにより、あまりに多くの光線オブジェクト交点又は光線三角形交点の計算を実行しなくてもよくなり、計算が加速される。このメールボックスは、メモリキャッシュとは違って、メモリへのメモリ問合せを防ぐのではなく、交点計算を防ぐ一種の交点計算キャッシュと見なすことができる。メールボックスの実施には、４ウェイキャッシュのような標準的なキャッシュ法を使用してよい。
【００５７】
レイトレーシングアーキテクチャのユニットは非常に大きなメモリ帯域幅を要する、つまり、単位時間当たりに非常に多くのデータが伝送されなければならない。通常、これは非常に多くのメモリチップを並列接続することによってのみ実現される。しかし、必要なメモリ帯域幅は複数のキャッシュレベル（ｎレベルキャッシュ）を適切に接続することによっても保証することができる。ここで、重要なのは、コヒーレンスと呼ばれるレイトレーシング法の特性である。コヒーレンスは、３Ｄ空間の同様の領域を通過する光線はまた加速構造内のほぼ同じデータにアクセスし、それに応じて同じオブジェクトにもアクセスするという事実を指している。この特性を利用すれば、高いキャッシュヒット率を達成することができる。つまり、必要なデータが高い確率でキャッシュ内に再び見つかり、時間をかけてメインメモリからロードする必要がない。キャッシュ自体は、複数のレイトレーシングユニットを賄うために、図４における図示に従って、例えばバイナリツリー内に配置されている。
【００５８】
本発明による装置は、３Ｄディスプレイと接続されれば、もちろん複雑な動くシーンの写真現実的な３次元リアルタイム表示にも使用することができる。これに関して、使用されるディスプレイの技術に応じて、画像出力の３つの実施形態を区別することができる。
【００５９】
第１には、立体感を含んだ２つの画像を時分割多重で水平方向にずらして交互にディスプレイに表示する実施形態。
【００６０】
第２には、立体感を表現する水平方向にずらした２つの画像を、これら２つの画像の画像情報を含んだ交互に現れる垂直のストライプの形でディスプレイに表示する実施形態。
【００６１】
第３には、２つの水平方向にずらした画像を２つの分割されたディスプレイに同時に又は時分割多重で表示する実施形態。
【００６２】
それぞれ右目又は左目に割り振られた２つの水平方向にずらした画像は、ディスプレイの相応する空間的配置によって又は画像分割装置（例えば、シャッター眼鏡、ストライプ状のフレネルプリズム／レンズ、偏光フィルタ）の使用によって、それぞれ一方の目にだけ見える。使用される３Ｄディスプレイとこの３Ｄディスプレイのビデオ信号制御の必要条件は従来の技術に従っており、より詳細には説明しない。３Ｄディスプレイの従来の技術に関する別の実施形態は、例として挙げた以下の文献から知ることができる：Computer Graphics / Addison-Wesley ISBN 020 1848406, DE 4417664, DE 19753040, DE 19827590, DE 19737449。
【００６３】
３次元動的シーンと画像のコンピュータアニメーションによる写真現実的なリアルタイム表示の使用は、３次元ＣＡＤデータの表示、医学的及び技術的分析的データの表示、フィルムアニメーション、飛行及び走行シミュレーションでの使用、ならびに、高価なリアルタイムグラフィックスを備えたコンピュータゲームにおけるいわゆるホームユースまでにわたっている。
【００６４】
さらに、この同じ方法を機能の実施に変更を加えることなく非写真現実的な画像生成（例えば、線画又はコミックスタイルの表示）にも使用することができる。同様に、技術的な変更を加えることなく、通常は画像計算には直接関係しない計算も実行可能である。例えば、幾何学的オブジェクト間の衝突検出（英語では、Ｃｏｌｌｉｓｉｏｎ Ｄｅｔｅｃｔｉｏｎ）と数値計算問題の離散的解法とがこのような計算に属している。上記のすべての用途はインタラクティブな領域に限定されるものではなく、方法又は装置に変更を加えずに、オフライン領域でも、例えば、映画フィルムの計算や非常にコストのかかる物理的シミュレーションにおいても、使用することができる。
【００６５】
レイトレーシング法の機能の実現とハードウェアによる実施は、複雑で高速の論理技術によって行われる。この論理技術は、単独の標準ＩＣから成る離散ディジタル論理回路の形態をとった有線接続のディジタル論理回路としても、又は、例えばＡＳＩＣのような特定の顧客もしくは用途向けに製造されたＩＣとしても、又は、例えばＣＰＵカーネルを用いたもしくは用いないＣＰＬＤもしくはＦＰＧＡ技術のような、複雑なプログラム可能論理素子／論理回路としても、又はこれらの技術の組合せとしても実施される。
【００６６】
以下に述べる本発明の実施例は、コンピュータグラフィックスカードのレイトレーシングユニットを説明したものである。このレイトレーシングユニットは、ハードウェアによるレイトレーシング法の実施を、例えば、自由プログラミング可能論理素子ＦＰＧＡ、ＡＳＩＣ技術、又は有線接続の専用チップにおいて実現することができる。
【００６７】
方法及び機能の流れを記述するのであれば、これらは純粋にハードウェア的に実現されなければならない。つまり、相応する論理ユニットとハードウェア的に実現された算術ユニットが形成されなければならない。
【００６８】
従来の技術による、データディスレプイ（陰極線管、ＴＦＴ、ＬＣＤ、又はプラズマモニタ）を制御する制御電子回路の標準機能とそのタイミングは周知のものと前提され、説明の対象とはならない。この標準機能の画像メモリと本発明によるレイトレーシング法の実現との間のインタフェースを説明する。
【００６９】
説明は２つの部分に分かれる。まずは、レイキャスティングパイプライン、略してＲＣＰが説明される。ここでは、光線がシーンをトラバースし、衝突点を返すことが、設計の核である。
【００７０】
第２部では、レイキャスティングパイプラインのために、これらレイキャスティングパイプラインのうちの複数をまとめて処理する最適化されたレイトレーシングアーキテクチャが説明される。
【００７１】
図２は、複数のサブユニットから成るレイキャスティングパイプラインユニット（ＲＣＰ）を示している。トラバースユニットは適切な加速構造、有利にはｋ−Ｄツリーを光線でトラバースする。光線は、命中オブジェクトとなりうるオブジェクトが存在するシーンの領域に至るまで、トラバースを続ける。この領域のオブジェクトは、リストユニットによって処理されるリストに記憶されている。リストユニットは、既に光線と交差したオブジェクト又は三角形をマークすることにより、光線の射出の際に三角形又はオブジェクトが光線と何度も交差するのを防ぐメールボックスも含んでいる。これにより、あまりに多くの光線オブジェクト交点又は光線三角形交点の計算を行わずに済み、計算が加速する。
【００７２】
つぎに、これらのオブジェクトを可能な交点に基づいて検査しなければならない。妥当な交点が存在しない場合には、トラバースを継続しなければならない。リストユニットは、オブジェクトに属するアフィン変換をロードするマトリクスロードユニットに、まだ処理されていない可能な命中オブジェクトを次々と送る。このアフィン変換は４×３行列によって表現することができる。この行列は、オブジェクト空間変換行列、又は、原始オブジェクトの正規空間内への変換を行う行列であってよい。マトリクスロードユニットが変換ユニットに行列を記憶した後、変換ユニットにより光線ユニットから光線が送られる。
【００７３】
変換後には２つのシナリオが考えられうる。１つには、オブジェクトはさらに別のオブジェクトを含んでいる場合がある。この場合、光線は再びトラバースユニット内に戻り、変換された光線がオブジェクト内でさらにトラバースを続ける。しかしならが、このオブジェクトが原始オブジェクトである場合には、光線は直接さらに交点計算ユニットに進み、交点計算ユニットは光線を正規オブジェクトと交差させる。交点計算ユニットは、前に説明したように、複数の正規オブジェクト（三角形、球など）をサポートすることができる。
【００７４】
計算された交点データは交点ユニットに集められる。交点ユニットがトラバースユニットへのフィードバックチャネルを提供しているため、トラバースユニットは、妥当な交点データが既に存しているか否かを知ることができる。
【００７５】
トラバースユニット、リストユニット、及びマトリクスロードユニットは、外部メモリにアクセスするレイキャスティングパイプラインの唯一のユニットである。トラバースユニットは加速構造にアクセスし、リストユニットはオブジェクトアドレスのリストにアクセスし、マトリクスロードユニットは行列の形態をとったアフィン変換にアクセスする。これら３つのユニットのすべては、メモリ帯域幅を確保するため、各自のキャッシュを介してメインメモリと接続されている。
【００７６】
図１２には、レイキャスティングパイプラインの簡易版が示されている。図１２では、最重要のユニット、すなわち、加速構造を光線でトラバースさせるトラバースユニット、リストを処理するリストユニット、ロードした変換を光線に適用する変換ユニット、及び、変換された光線を正規オブジェクトと交差させる交点計算ユニットしか描かれていない。
【００７７】
レイキャスティングパイプラインは、図３の表現に従って、適切なレイトレーシングアーキテクチャに埋め込まれている。図には、それぞれ３つのキャッシュを有する４つのレイキャスティングパイプラインユニットが示されている。ここで、これらのユニットの２つずつが１つのシェーディングユニットに接続されている。これらのシェーディングユニットは、画像のピクセルの色を計算するために、レイキャスティングパイプラインユニットを使用する。このために、シェーディングユニットは一次光線を射出し、レイキャスティングパイプラインが返す衝突点を処理し、二次光線を例えば光源へ射出する。シェーディングユニットは、有線接続されたハードウェア、又は後で説明するプログラム可能レイトレーシングプロセッサであってよい。
【００７８】
シェーディングユニットはレイキャスティングパイプラインの変換ユニットへのチャネルを有している。このチャネルは、カメラ行列と二次光線用の行列をロードし、それによりシェーディングユニットの計算コストを最小化するために使用される。シェーディングユニットがそれぞれ別々のテクスチャキャッシュとシェーディングキャッシュを有していると有利である。シェーディングキャッシュは、例えば色や材質データのような、シーンのジオメトリに関するシェーディング情報を収容している。テクスチャキャッシュはテクスチャメモリと接続されており、シェーディングユニットがテクスチャにアクセスするのを可能にする。各シェーディングユニットが各自のローカルフレームバッファを有していると有利である。このローカルフレームバッファには、処理／計算されたばかりのピクセルの色と輝度値が格納される。さらに、Ｚバッファがあると有利である。というのも、Ｚバッファは、以下で説明する標準ラスタ化ハードウェアとの結合で必要とされるからである。
【００７９】
ピクセルの色がシェーディングユニットにより完全に計算されているならば、この色をオプションの色調マッピングユニットを介してグローバルフレームバッファに書き込んでよい。色調マッピングユニットは、２４ビットのＲＧＢ空間に色を写像する単純な関数を色に適用する。また、オプションのローカルＺバッファに記憶されている幾何学的深度値（Ｚ値）を、オプションのグローバルＺバッファに伝送してもよい。
【００８０】
しかし、色又は新たなＺ値は、以前にＺバッファ内に存在したＺ値の方が大きい場合にのみ、フレームバッファ又はＺバッファに書き込まれる。これにより、既にラスタ化ハードウェア又は他のレイトレーシングパスによって計算された値よりもピクセルが幾何学的に前にある場合にのみ、ピクセルが書き込まれることが保証される。したがって、レイトレーシングハードウェアを同じフレームバッファ又はＺバッファ上で動作する標準ラスタ化ハードウェアと組み合わせることが可能である。この場合、フレームバッファ又はＺバッファはこの標準ラスタ化ハードウェアへのインタフェースでもある。
【００８１】
システム性能をさらに向上させるために、オプションとして、さらに別のシェーディングユニットを付属のレイキャスティングパイプラインとキャッシュとに並列接続させてもよい。この場合、性能向上効果はデータ構造及び処理構造の拡大にある。
【００８２】
シーン全体がレイトレーシングチップのローカルメインメモリに入ると期待することはできない。この問題を解決するために、ローカルメインメモリを、シーンのより大きなブロックをキャッシュするより大きなキャッシュとして使用してよい。本来のシーンは別の場所にあり、必要なときにＤＭＡを介してダウンロードされる。仮想的なメモリ使用のためのこの方法により、レイトレーシングチップのメインメモリには入らない非常に大きなシーンを視覚化することが可能になる。
【００８３】
フォトンマッピングは、仮想光子を光源からシーンへ射出し、シーンの表面に集める標準的方法である。これにより、シーンの光分布をシミュレートすることができる。このことは特に火面についても当てはまる。光子が射出されると、光子によって加速構造が形成される。この加速構造は、例えば、ｋ−ｄツリーであってよい。今や、標準的なレイトレーシング法によりシーンを視覚化し、各衝突点において、そこに入射する光の輝度を色計算に算入する際に、この点の近傍に衝突するすべての光子のエネルギーが合計されるようにすることにより、この計算された光子最終分布の描写を行うことができる。このためには、光子の加速構造において隣接するすべての光子を探さなければならない。このタスクはトラバースユニットによりサポートされる。トラバースユニットは、そのために、光線に沿ってではなく、ボリュームをトラバースする。このようにして、隣接するすべての光子は、例えばそのエネルギーを合計することによって、処理される。
【００８４】
通常、レイトレーシング法は無限に細い光線を用いるが、これはサンプルアーチファクト（エイリアシング）を生じさせてしまう。遥かに良好な近似は光線の代わりに光円錐を使用することで得られる。カメラのピクセルを照明する光は、ばらばらの方向からではなく、光円錐によって非常に良く近似することのできる一種の角錐から来る。光円錐又は光角錐によって記述される、この空間ボリュームの前から後ろへのトラバースもまた、トラバースユニットによって専用機能として実行することができる。図６には、光円錐の２次元描写が示されている。
【００８５】
ディスプレイを制御するための信号処理とディスプレイ又はモニタに対するタイミングの発生は、周知のように、オプションのラスタ化ハードウェアによって行う、又は、所望の用途にとって有利な場合には、適切な機能ユニットで実施してよい。こうして、ハードウェア的に実施されたレイトレーシング法と機能とを備えた標準ラスタ化ハードウェアの基本機能を、非常に性能のよいリアルタイムハードウェアアーキテクチャに結合することができる。
【００８６】
本発明の第２の別の実施例は、本発明により説明された専用のレイトレーシング機能及び方法をプログラム制御により実施する自由にプログラム可能なレイトレーシングＣＰＵ又はレイトレーシングプロセッサの構成と使用に基づいている。この実施例では、適切な論理及び機能の並列性により、個々の機能を片付けるのに、ＣＰＵの数サイクル、有利には、１又は２サイクルしか必要としない。
【００８７】
レイトレーシングプロセッサの内部アルゴリズム、方法、及び機能の流れを記述するのであれば、これらはハードウェア記述言語、例えば、ＨＤＬ、ＶＨＤＬ、又はＪＨＤＬを用いて書かれ、相応するハードウェアへ移されなければならない。実施される方法及び機能と共に、レイトレーシングプロセッサのハードウェア的実施は、例えば、自由プログラム可能論理素子ＦＰＧＡ、ＡＳＩＣ技術、ＦＰＧＡ／ＡＳＩＣを備えたディジタル信号プロセッサの組合せ、又は、有線接続された専用チップにより行うことができる。
【００８８】
このことは、個々の機能をプログラム制御により呼び出すことのできる適切な論理ユニット及びハードウェア的に実現された算術ユニットを形成しなければならないことを意味している。使用されるハードウェア技術の複雑さに応じて、チップごとに、別の論理機能を備えた又は備えていない１つ又は複数のプロセッサを実現してもよい。
【００８９】
レイトレーシングプロセッサは、ベクトル算術命令と「トラバース」や「加速構造の形成」のような専用レイトレーシング命令とを実行するように設計された完全にプログラム可能な計算ユニットである。これに関して、設計は機能ユニットを追加して行ってもよいが、既にある機能ユニットを用いて、場合によっては少数の論理素子を追加して、行ってもよい。例えば、トラバースは専用の機能ユニットによって行ってもよいし、又は既にある算術機能ユニットを少数の論理機能ユニットで拡張することによって行ってもよい。
【００９０】
図１１に見られるように、図５に示されている複数のレイトレーシングプロセッサが並列に接続される。メモリインタフェースは、必要なメモリ帯域幅を用意するキャッシュ階層から形成される。このプロセスは、隣接する光線の強いコヒーレンスのため、効率的に可能である。レイトレーシングプロセッサのコンセプトでは、各レイトレーシングプロセッサは画像の正確に１つのピクセルを処理するか、又は複数のピクセルから成るパケットを処理する。その際、個々のそれぞれのピクセルの計算が１つの計算スレッドに相当する。これらのスレッドのうちの複数は１つのパケットに束ねられ、全体として同期して処理される。同期して処理されたスレッドは、つねに共通して同じ命令を実行するという点で優れている。これにより、効率的なハードウェアの構築と、各スレッドに対して個別にではなく、パケット全体ごとにメモリ問合せを行うことが可能になる。とりわけ、このメモリ問合せの減少は、スレッド処理に対するパケット処理の重要な利点である。
【００９１】
図１１のスレッドジェネレータは、レイトレーシングプロセッサ上で実行されるスレッドを生成する。スレッドジェネレータはレイトレーシングプロセッサによってもプログラムすることができる。画像のピクセルをキャッシュコヒーレントな方法（例えば、ヒルベルト曲線）でスキャンする専用機能により、レイトレーシングプロセッサにコヒーレントなスレッドを最適に供給することが可能になる。これにより、必要なメモリ問合せが減少する。スレッドジェネレータはまたＤＭＡインタフェースを介してメインメモリにアクセスすることもできる。したがって、個々のスレッドの開始値を前の処理ステップにおいて生成し、後にこれらのデータから再び新しいスレッドを生成するために、メモリに書き込んでおいてもよい。
【００９２】
ピクセルの処理はレイトレーシングプロセッサ上で動作するソフトウェアプログラムによって行われる。このソフトウェアプログラムは、ハードウェアが光線のパケット上で動作する場合でもピクセルの色値を計算する再帰的な方法の流れを記述したものである。したがって、パケット管理はプログラミングモデルに対して透過的である。
【００９３】
図５はレイトレーシングプロセッサの構造の一例を示している。見るべきことは、２つの専用コプロセッサに並列接続された標準プロセッサカーネル（ＲＩＳＣカーネル）である。これらのコプロセッサはそれぞれ各自のレジスタを有している。しかしながら、専用命令により一方のコプロセッサのレジスタ内容を他方のコプロセッサに移動させることも可能である。トラバースカーネルは、光線によって加速構造を効率的にトラバースさせることのできる専用コプロセッサである。この加速構造のトラバースのために、トラバースカーネルは加速構造のノード（ノード-キャッシュ）への専用メモリインタフェースを必要とする。ベクトル算術カーネルは、３Ｄ空間内で効率的に演算を実行することのできる専用コプロセッサである。それぞれのレイトレーシングソフトウェアが必要とするベクトル加算、スカラー乗算、クロス積、及びベクトル積は、このユニットによって迅速に計算することができる。ベクトル算術ユニットは、全ベクトルを１サイクル内でロードすることのできる専用キャッシュへのアクセスを必要とする。
【００９４】
トラバース命令のセマンティクスは以下のようにしてよい。レイトレーシングＣＰＵは、光線の光源と方向及びトラバースされるべき加速構造のアドレスによって専用レジスタを記述する。専用命令が呼び出されると、専用トラバースユニットが始動する。このユニットは加速構造をトラバースし、オブジェクトを含むすべてのノードをリストユニットに送る。このリストユニットは、既に本発明の第１の実施例で説明したメールボックス機構を含んでいてよい。各オブジェクトについて、光線をこのオブジェクトと交差させる小さなプログラムがＣＰＵ上で実行される。光線とオブジェクトの妥当な交点が見つかれば、光線と交差したオブジェクトがプログラムに返される。
【００９５】
レイトレーシングプロセッサ内にハードウェア的に実施されている個々の命令又は論理機能は、有線接続された本発明の第１の実施形態において既に説明した同一のアルゴリズムを内容としている。しかし、これを補足して、この命令セットを、同じくプログラム制御により活動化させることのできる有線接続された別の命令及び機能で補ってもよい。専用トラバース動作と、ベクトル算術と、レイトレーシングプロセッサ上での複数のスレッドの並列処理とにより、リアルタイムアプリケーションに必要な計算能力が提供され、同時に、システム速度に対するメモリレイテンシー（メモリ問合せの待ち時間）の影響が最小化又は無効化さえされる。
【００９６】
ピクセルの色が完全に計算されていれば、この色をフレームバッファに書き込むことができる。場合によっては、さらに距離をＺバッファに書き込んでもよい。これにより、ラスタ化ハードウェアとの結合とディスプレイへの適切な表示が可能になる。
【００９７】
請求項１０には、幾何学的オブジェクトを記憶又は参照せず、むしろ空間影響量又は材質変更パラメータを含む付加的な空間分解データ構造の使用が記載されている。この空間影響量は、例えば、霧、霞、塵粒、又は熱煙であってよい。ここで、例えば熱煙は煙のボリュームを通して見えるシーンの変化を結果としてもたらすこともありうる。別の空間影響量は、例えば空想上の存在を表現する際に使用されるような、光源、又は、材質を変化させる背光である。ここで、空間分解データ構造の使用により計算コストを著しく低減することが可能である。なぜならば、空間的に影響を持ちうるような位置にある影響量のみを考慮すればよいからである。
【００９８】
請求項１１には、三角形から構成されているのではない又は三角形だけから構成されているのではない３次元シーンの処理を可能にし、必要ならば、他の幾何学的要素を三角形又は簡単に処理できる中間的表現に変える拡張が記載されている。これについては、ハードウェアを機能ユニットで拡張する、又は既にあるユニットが機能を実施することにより、付加的な機能が達成される。
【００９９】
請求項１２には、光線処理の結果として、光線ごとに、最も近いオブジェクト光線交点だけでなく、さらにより遠いオブジェクト光線交点も計算することができるようにする拡張が記載されている。これについては、光線源からの距離に応じて結果を分類すると有利である。結果ごとの交点の最大数を定数として固定してもよいし、光線ごとに交差したオブジェクトのパラメータに応じて行ってもよい。この技法は透明なオブジェクトを通過した光線を計算するために使用することができる。
【０１００】
請求項１３には、付加的な又は既にある機能ユニットを用いて、画像の計算において所定の要素が何度使用されたかをカウントすることができるようにする拡張が記載されている。これについては、カウントされる要素は非常に様々であってよく、要素の考えられうる分類はメモリ内でのアドレス又は要素のＩＤを介して行うことができる。これらの要素には以下のものが属する：
動的及び幾何学的オブジェクト、部分的又は完全な材質記述、空間記述データ構造の要素又はサブグループ、プログラム又はプログラム機能、個々のメモリセル、ならびに、メモリページ全体又はメモリ領域全体。
【０１０１】
請求項１４には、空間記述データ構造を部分ごとに計算すること又は完全な３次元シーンを計算する機能の拡張が記載されている。ここで、動的オブジェクト又は動的部分オブジェクト又は幾何学的オブジェクトごとの付加的なパラメータが空間記述データ構造の計算法に対して影響を有している。このような影響は、例えば、所定の空間ボリューム内に幾何学的オブジェクトを有さないオブジェクトを特定するようなものであってよい。これにより、空間記述データ構造をより効率的に計算し、さらに１画像当たりの計算コストをさらに低減することが可能になる。
【０１０２】
図面の説明
図１は、どのようにしてオブジェクトの複数のレベルから木が生成され得るかを示している。まず、レベル１のオブジェクト１０１として葉がモデル化される。この葉１０１は何倍にもインスタンシングされ、枝１０２に配置される。これにより、さらなるオブジェクトが発生するが、今はレベル２のオブジェクトが発生する。これらの小さな枝１０２は再びレベル３のオブジェクトである木１０３へと何倍にもインスタンシングされる。
【０１０３】
図２は、最も重要なデータパスとキャッシュへのインタフェースとを備えたレイキャスティングパイプラインユニット２００を示している。矢印２０１はシェーディングユニットの方へ向かい、矢印２０２はシェーディングユニットから来ている。さらに以下のものが示されている：
２０３：トラバースユニット
２０４：メールボックスを含んだリストユニット
２０５：マトリクスロードユニット
２０６：光線ユニット
２０７：変換ユニット
２０８：交点計算ユニット
２０９：交点ユニット
２１０：ノードキャッシュ
２１１：リストキャッシュ
２１２：マトリクスキャッシュ
【０１０４】
図３は、本発明の実施例のトップレベルの線図を示している。４つのレイキャスティングパイプライン（ＲＣＰ）は、キャッシュ階層を介して、ノード用、リスト用、及び行列用の別個のメモリに接続されている。この設計例では、ＲＣＰの２つずつが１つのシェーディングユニットに接続されており、シェーディングユニットはローカルフレームバッファとローカルＺバッファへのアクセスを有している。これらのバッファを介して、色値は色調マッピングユニットによりグローバルフレームバッファに書き込まれ、インド値は直接グローバルＺバッファに送られる。このＺバッファとフレームバッファに、従来の技術によるラスタ化ハードウェア（ラスタ化パイプライン）を接続してもよい。
図中には、以下のものが示されている：
３０１：ラスタ化ハードウェア
３０２：フレームバッファ
３０３：ビデオ出力
３０４：色調マッピングユニット
３０５：Ｚバッファ
３０６：フレームバッファ１
３０７：Ｚバッファ１
３０８：テクスチャキャッシュ１
３０９：シェーディングキャッシュ１
３１０：シェーディングユニット１
３１１：ノードキャッシュ１
３１２：リストキャッシュ１
３１３：マトリクスキャッシュ１
３１４：ＲＣＰ１
３１５：ノードキャッシュ２
３１６：リストキャッシュ２
３１７：マトリクスキャッシュ２
３１８：ＲＣＰ２
３１９：フレームバッファ２
３２０：Ｚバッファ２
３２１：テクスチャキャッシュ２
３２２：シェーディングキャッシュ２
３２３：シェーディングユニット２
３２４：ノードキャッシュ３
３２５：リストキャッシュ３
３２６：マトリクスキャッシュ３
３２７：ＲＣＰ３
３２８：ノードキャッシュ４
３２９：リストキャッシュ４
３３０：マトリクスキャッシュ４
３３１：ＲＣＰ４
【０１０５】
図４は、チップ内で必要な内部メモリ帯域幅を提供するキャッシュ下部構造を示している。図中では、ｎレベルのバイナリキャッシュであるが、他の階層構造も考えられる。
図中には、以下のものが示されている：
４０１：ノードキャッシュ１
４０２：ノードキャッシュ２
４０３：ノードキャッシュ３
４０４：ノードキャッシュ４
４０５：ノードキャッシュ５
４０６：ノードキャッシュ６
４０７：ノードキャッシュ７
４０８：ノードメモリ
４０９：リストキャッシュ１
４１０：リストキャッシュ２
４１１：リストキャッシュ３
４１２：リストキャッシュ４
４１３：リストキャッシュ５
４１４：リストキャッシュ６
４１５：リストキャッシュ７
４１６：リストメモリ
４１７：マトリクスキャッシュ１
４１８：マトリクスキャッシュ２
４１９：マトリクスキャッシュ３
４２０：マトリクスキャッシュ４
４２１：マトリクスキャッシュ５
４２２：マトリクスキャッシュ６
４２３：マトリクスキャッシュ７
４２４：マトリクスメモリ
４２５：テクスチャキャッシュ１
４２６：テクスチャキャッシュ２
４２７：テクスチャメモリ
４２８：シェーディングキャッシュ１
４２９：シェーディングキャッシュ２
４３０：シェーディングキャッシュ３
４３１：シェーディングメモリ
【０１０６】
図５はレイトレーシングＣＰＵの実施例を示している。ここで、ブロックは以下の意味を有している：
５０１：命令ロード
５０２：命令メモリ
５０３：ＲＩＳＣカーネル
５０４：キャッシュ
５０５：トラバースカーネル
５０６：ノードキャッシュ
５０７：ベクトル算術カーネル
５０８：ベクトルキャッシュ
【０１０７】
図６はオクツリーノードにおける簡略化されたジオメトリの例を示している。この例では、参照番号６０１は光円錐を表しており、参照番号６０２は「簡略化されたジオメトリ」を表している。
【０１０８】
図７は、単純なシーンにおける正則グリッド加速構造の例を示している。空間は簡単のため２Ｄでのみ示されている。参照番号７０１は光線を表している。
【０１０９】
図８は、単純なシーンにおけるｋ−Ｄツリー加速構造の例を示している。空間は簡単のため２Ｄでのみ示されている。参照番号８０１は光線を表している。
【０１１０】
図９は、単純なシーンにおけるオクツリー加速構造の例を示している。空間は簡単のため２Ｄでのみ示されている。参照番号９０１は光線を表している。
【０１１１】
図１０は、グローバル空間から正規三角形空間への三角形の変換を示している。光線１００１と三角形１００２が見られる。矢印１００３によって表されたアフィン変換により、変換された光線１００４と正規三角形１００５が生じる。グローバル空間は左側の座標系で表され、正規三角形空間は右側の座標系で表される。
【０１１２】
図１１は、専用レイトレーシングプロセッサに基づいた本発明の実施例を示している。ここで、ブロックは以下の意味を有している：
１１０１：ラスタ化ハードウェア
１１０２：スレッドジェネレータ
１１０３：Ｚバッファ／フレームバッファ
１１０４：ビデオ出力
１１０５：レイトレーシングプロセッサ１
１１０６：レイトレーシングプロセッサ２
１１０７：レイトレーシングプロセッサ３
１１０８：レイトレーシングプロセッサ４
１１０９：キャッシュ１
１１１０：キャッシュ２
１１１１：キャッシュ３
１１１２：キャッシュ４
１１１３：キャッシュ５
１１１４：キャッシュ６
１１１５：キャッシュ７
１１１６：メインメモリ
【０１１３】
図１２は、図２に示されているレイキャスティングパイプラインの簡易版を示している。ここで、ブロックは以下の意味を有している：
１２０１：トラバースユニット
１２０２：ノードキャッシュ
１２０３：リストユニット
１２０４：リストキャッシュ
１２０５：変換ユニット
１２０６：マトリクスキャッシュ
１２０７：交点計算ユニット
矢印１２０８はシェーディングユニットから来ている。
【０１１４】
図１３は、三角形の頂点とボックスの頂点の比較により、三角形がボックスにオーバーラップしているか否かを判定することのできる簡単なケースを示している。三角形のＸ座標がボックスの最小Ｘ座標よりも小さければ、三角形はボックスの外にある。三角形は参照番号１３０１で表され、ボックスは参照番号１３０２で表されている。
【図面の簡単な説明】
【０１１５】
【図１】どのようにしてオブジェクトの複数のレベルから木が生成され得るかを示す。
【図２】最も重要なデータパスとキャッシュへのインタフェースとを備えたレイキャスティングパイプラインユニット２００を示す。
【図３】本発明の実施例のトップレベルの線図を示す。
【図４】チップ内で必要な内部メモリ帯域幅を提供するキャッシュ下部構造を示す。
【図５】レイトレーシングＣＰＵの実施例を示す。
【図６】オクツリーノードにおける簡略化されたジオメトリの例を示す。
【図７】単純なシーンにおける正則グリッド加速構造の例を示す。
【図８】単純なシーンにおけるｋ−Ｄツリー加速構造の例を示す。
【図９】単純なシーンにおけるオクツリー加速構造の例を示す。
【図１０】グローバル空間から正規三角形空間への三角形の変換を示す。
【図１１】専用レイトレーシングプロセッサに基づいた本発明の実施例を示す。
【図１２】図２に示されているレイキャスティングパイプラインの簡易版を示す。
【図１３】三角形の頂点とボックスの頂点の比較により、三角形がボックスにオーバーラップしているか否かを判定することのできる簡単なケースを示す。
【技術分野】
【０００１】
本発明は、リアルタイムレイトレーシングハードウェアアーキテクチャを用いて、複雑な動的３次元シーンを高い画像リフレッシュレートで２次元ディスプレイに表示することのできる装置に関する。動的シーンとは、カメラ位置の他に、表示すべきオブジェクトのジオメトリもフレームごとに変化しうるシーンである。本発明は、とりわけ、オブジェクトの階層構造をサポートしている、すなわち、主シーンが各々別のオブジェクトから構成された複数のオブジェクトから成っており、この入れ子を任意に続けることができるという点で優れている。階層の個々のレベルに存在しているオブジェクトは個別にも合同でも動くことができる。これにより、高い動特性をもつ複雑なシーンを生成することができ、シーンの複数の位置において同じオブジェクトを使用することにより、メモリ内でのシーンの表現を小さく保つことができる。
【０００２】
本発明に従ってこの入れ子になったオブジェクトレベルを実現するためには、公知のレイトレーシングパイプラインのハードウェアによる実施が、光線をオブジェクト内へ変換するハードウェア的に実現された変換ユニットで拡張される。このユニットはハードウェア資源の最適利用のために１つだけ設けられており、オブジェクト空間変換の他に、光線と三角形との交点の計算、一次光線の生成、及び二次光線の生成のために使用される。
【０００３】
本発明に従って、標準的なプロセッサカーネルと１つ又は複数のレイトレーシング命令の組合せとから成る新式のプロセッサアーキテクチャを使用することにより、レイトレーシング専用に設計されたプロセッサの使用を通して、本発明はユーザにシステムの完全なプログラム可能性を提供する。このレイトレーシングプロセッサの使用はさまざまなレイトレーシング法のプログラミングを可能にする。シーンの原始オブジェクトはプログラム可能に構成されているので、今日のグラフィックスカードとは違って、光線とスプライン曲面との交点を計算する専用のアルゴリズムをプログラムすることにより、スプライン曲面の使用も可能である。今日のラスタ化ハードウェアの場合と同様に、通常、表面のさまざまなシェーディングモデルをプログラムすることができる。
【０００４】
ディスプレイに画像データを出力するために、共通のフレームバッファとＺバッファを使用することにより本発明を従来の技術によるラスタ化ハードウェアと組み合わせることもできる。
【０００５】
背景技術
現在、３次元シーンの表示に関する背景技術は、ラスタ化法とレイトレーシング法の２つの主要セクターに分けられる（Computer Graphics / Addison-Wesley ISBN 020 1848406参照）。
【０００６】
とりわけコンピュータグラフィックスカードにおいて使用される公知のラスタ化法は、シーンの各ジオメトリをフレームバッファとＺバッファに投影するという原理に基づいている。このために、ピクセルの色値及び輝度値がフレームバッファに記憶され、幾何学的な深度値はＺバッファに記憶されるが、それはＺバッファ内にある直前の幾何学値が新たな値よりも大きい（観察者からより離れている）場合に限る。これにより、より近いオブジェクトがより遠いオブジェクトに上書きされ、プロセスの進行に従って実際に可視のオブジェクトしかフレームバッファ内に写し取られないことが保証される。
【０００７】
しかしながら、この方法は、数百万のオブジェクトを持つような費用のかかるシーンの場合には、今までに知られているハードウェアではシーンをリアルタイムに表示することができないという決定的な欠点を有している。というのも、通常は、シーンのすべての三角形（オブジェクト）を投影することが必要となるからである。さらには、秒単位で数十億の書込み動作が行われるフレームバッファとＺバッファが必要となる。この書込みの際、画像形成のために、大部分のピクセルは１フレームにつき何度も上書きされる。観察者にとってより遠いピクセルをより近いオブジェクトのピクセルによって上書きすることの結果として、既に計算されたデータが捨てられるため、最適なシステム性能を実現することができない。
【０００８】
影は今日のラスタ化ハードウェア上で費用のかかる技術を用いれば計算することができるが、複雑なシーンの場合には、正確性に関して問題を生じる。曲面での反射及び光の屈折の計算はこの技術では物理的に正しく実現することができない。
【０００９】
第２の方法であるレイトレーシング法によれば、性能を向上させるような改善が達成される。レイトレーシング法はその写真現実的な画像で知られるが、計算が複雑であることでも知られている。レイトレーシングの基本的な考え方は物理的な光分布モデルと親近性がある（Computer Graphics / Addison-Wesley ISBN 020 1848406参照）。
【００１０】
現実の環境においては、光は光源から放射され、物理法則に従ってシーン内に分布する。周囲環境の画像はカメラによって捕らえることができる。レイトレーシングは、それとは逆に、観察者位置を表すカメラから光源へと光を追跡する。このために、画像の各ピクセルに対して、ピクセルを照明する方向に仮想的な光線が射出される。この光線の射出はレイキャスティングと呼ばれる。光線がオブジェクトに当たると、ピクセルの色が、とりわけ、光線の当たったオブジェクトの色と表面の法線と衝突点から見える光源とから計算される。衝突点から見えるこれらの光源は、各光源から衝突点へ射出される二次光線を追跡することによって求めることができる。この影光線が光源と衝突点の間のオブジェクトに当たれば、点は光源に対して影の中にある。
【００１１】
この方法は、上記の影の計算の他に、反射光又は屈折した二次光線を計算することにより、光の反射及び屈折の計算も可能にする。さらに、ほぼ任意のサイズのシーンを処理し、表示することができる。その理由は加速構造の使用にある。これは、仮想光線で迅速にシーンを「射つ」又はトラバースすることのできる適切なデータ構造を用いた特別な方法である。途中で、命中候補となりうる幾つかのオブジェクトが選択され、これにより衝突点が迅速に見つけ出される。理論的な研究によれば、レイトレーシング法の計算量は平均してシーンのサイズに対して対数的に成長することが示されている。つまり、シーンのオブジェクトの個数が２乗されても、計算コストは２倍にしかならないことを意味している。
【００１２】
典型的な加速構造は、例えば、正則グリッド、ｋ−Ｄツリー、オクツリー、バウンディングボリューム階層である（Computer Graphics / Addison-Wesley ISBN 020 1848406参照）。これらすべての方法は、空間を多数の部分空間に分割し、このような各部分空間に関してこの部分空間におけるジオメトリを記憶するという考えに基づいている。そして、トラバース法は部分空間から部分空間へと光線を追跡し、光線はつねにちょうどその部分空間内にあるオブジェクトと交差する。４つの方法は部分空間の配列の仕方が異なっているだけである。正則グリッドでは、空間は同じサイズのサイコロ形の部分空間に分割されている。具体的には、図７の図を参照されたい。他の３つの方法は空間の再帰的な分割に基づいている。ｋ−Ｄツリー法では、開始空間が任意の場所で再帰的に軸平行に分割される。具体的には、図８を参照されたい。この空間の分割は再帰的データ構造（バイナリツリー）に記憶される。オクツリーと呼ばれる第３の方法も同様に再帰的であるが、観察される部分空間はつねに同サイズの８つの長方形部分空間に分割される。具体的には、図９を参照されたい。バウンディングボリューム階層は空間をｎ個の任意のボリュームに分割する。それどころか、このｎ個のボリュームはオーバーラップしてもよい。これは他の方法では許されないことである。
【００１３】
ラスタ化法とは違って、現在のところ、レイトレーシング法を実現するハードウェア解決手段は存在しておらず、比較的高い計算能力と多くの計算時間とを要するソフトウェアベースのシステムしか存在していない。計算の時間的規模を分かり易くするために、次のことに注意されたい。すなわち、この方法に従って個々の静止画像を生成するには、画像の複雑度と、今のところ従来技術によるＰＣハードウェアと共に使用されているソフトウェアとによっては、数秒から数時間までの計算時間が必要となる。動画像の計算には、相応して多くの計算時間及び／又は専用の大型計算機の使用が必要となる。
【００１４】
ザールラント大学のコンピュータグラフィックス講座は、２０台を超す計算機のクラスタを使用するソフトウェアベースのリアルタイムレイトレーシングシステムを開発した。
【００１５】
アメリカ合衆国特許第６，５９７，３５９Ｂ１号には、レイトレーシング法のためのハードウェア解決手段が記載されているが、静的なシーンに限定されている。
【００１６】
アメリカ合衆国特許第５，９３３，１４６号にも、レイトレーシング法のためのハードウェア解決手段が記載されているが、これも静的なシーンに限定されている。
【００１７】
ザールラント大学のコンピュータグラフィックス講座の論文"SaarCOR - A Hardware Architecture for Ray-Tracing"には、レイトレーシングのためのハードウェアアーキテクチャが記載されているが、これもまた静的なシーンに限定されている。
【００１８】
ザールラント大学のコンピュータグラフィックス講座の論文"A Simple and Practical Method for Interactive Ray-Tracing of Dynamic Scenes"には、レイトレーサにおいて動的シーンをサポートするソフトウェア手法が記載されている。しかしながら、このソフトウェア方法はオブジェクトの１つのレベルしか使用しておらず、したがって複数のレベルへの入れ子を実施することができない。
【００１９】
上記の背景技術は、今のところ、複雑な動的シーンをリアルタイムで表示することのできるソフトウェア解決手段もハードウェア解決手段も提供していない。公知のラスタ化法では、能力の限界は表示すべきオブジェクトの個数にある。
【００２０】
レイトレーシングシステムはたしかに多くの三角形を表示することができるが、必要とされる事前計算のゆえに、限定的にしか位置を変えることができないという点で制限されている。数十億の三角形から成るシーンは非常に高い計算能力と多くのメモリを必要とし、高速で複雑な大型計算機又はクラスタ解決手段でしか処理することができない。
【００２１】
それゆえ、既存のパーソナルコンピュータハードウェアでは、動的なリアルタイムレイトレーシングシステムを実現することはできない。上記のクラスタ解決手段はコスト上の理由から特別用途に限定されることもあり得る。
【００２２】
これに対して、本発明の課題は、写真現実的な表示が得られるように、複雑な動的３次元シーンにおいてレイトレーシング法をより迅速に−有利にはリアルタイムでも−実行することのできる装置を提供することである。
【００２３】
この課題は、請求項１による装置、すなわち、装置が少なくとも１つのプログラム可能レイトレーシングプロセッサを有しており、該プロセッサにおいて、
・専用のトラバース命令、及び／又は
・ベクトル算術命令、及び／又は
・レイトレーシング加速構造を形成するための命令、及び／又は
・レイトレーシング法を実行する際、光線の射出時に、既に光線が交差したオブジェクト又は三角形を前記光線が何度も交差するのを抑制するために用いられる少なくとも１つの判定ユニット（メールボックス）が実施されるように構成された装置によって解決される。
【００２４】
上記装置の構造は、複数のスレッドを並列処理することができ、且つ、複数のスレッドを自動的に同期して処理することができるように構成されている。さらに、上記装置はｎレベルのキャッシュ階層及び／又は仮想メモリ管理及び／又はメインメモリとの直接接続を使用することができる。この装置は、有利には、ＦＰＧＡとして、及び／又はＡＳＩＣ技術及び／又は他の論理ベースの半導体技術又は離散集積論理回路において、又はこれらの技術の組合せにおいて実現することができる。
【００２５】
判定ユニットをより詳細に論じるために、図２を参照されたい。図２からは、リストユニットがメールボックスで拡張されることが見て取れる。このメールボックスは、既に光線と交差したオブジェクト又は三角形をマークすることにより、光線の射出の際に三角形又はオブジェクトが光線と何度も交差するのを防ぐ。これにより、非常に多くの光線オブジェクト交点又は光線三角形交点の計算をしなくても済み、計算が加速する。メールボックスは、メモリキャッシュとは違って、メモリへのメモリ問合せを防ぐのではなく、交点計算を防ぐ一種の交点計算キャッシュと見なすことができる。メールボックスの実施には、４ウェイキャッシュのような標準的なキャッシュ法を使用することができる。
【００２６】
請求項２は、複雑な動的３次元シーンをレイトレーシング法により写真現実的に表示する装置に関しており、該装置は、少なくとも１つの専用トラバースユニット、少なくとも１つのリストユニット、レイトレーシング法を実行する際、光線の射出時に、既に光線が交差したオブジェクト又は三角形を前記光線が何度も交差するのを抑制するために用いられる少なくとも１つの判定ユニット（メールボックス）、少なくとも１つの交点計算ユニット、加速構造を形成するための少なくとも１つのユニット、少なくとも１つの変換ユニット、及び／又は、線形方程式系を解くための少なくとも１つのユニットを有しており、複数の光線又はスレッドを並列処理することができ、複数の光線又はスレッドを自動的に同期して処理することができ、動的オブジェクト内に動的オブジェクトの任意個数のレベルを実現することができ、前記装置は、ｎレベルのキャッシュ階層及び／又は仮想メモリ管理及び／又はメインメモリとの直接接続を使用することができる。
【００２７】
請求項３による実施形態では、請求項２による実施形態との相違点として、請求項２の少なくとも１つの変換ユニット、及び／又は、線形方程式系を解くための少なくとも１つのユニット、及び／又は少なくとも１つの交点計算ユニットが、請求項３では、既に請求項１で説明されたレイトレーシングプロセッサで補完されている。
【００２８】
ソフトウェア的に定義された加速構造及び方法を相応するハードウェア構造において実施する、このレイトレーシング法に基づいた３次元動的シーンを写真現実的に表示するための装置は、優先的にリアルタイムで使用するためのものである。
【００２９】
シーン内に任意の無秩序な動きを実現するには、画像列の各画像について、加速構造を新たに計算しなければならない。このことは、大きなシーンの場合には、シーンの全体的なジオメトリを扱わなければならないため、莫大な計算コストを意味する。その際には、シーンのサイズに対して対数的な計算量という利点が消えてしまう。
【００３０】
前記論文"A Simple and Practical Method for Interactive Ray-Tracing"に記載されているこの問題に対する解決手段は、シーンをオブジェクトに分割し、専らこのオブジェクトの動きを全体として許可することである。この場合には、シーンのオブジェクト全体にわたるトップレベル加速構造と各オブジェクトに対するそれぞれ１つのボトムレベル加速構造の２つの加速構造が必要となる。この場合、オブジェクトはシーン内のオブジェクトのインスタンスという形で位置測定される。
【００３１】
オブジェクトとオブジェクトのインスタンスとの違いは、オブジェクトのインスタンスはオブジェクトと変換とから構成されているという点にある。この変換は、オブジェクトをシーンの任意の位置に移すアフィン関数である。アフィン変換はさらにオブジェクトのスケーリング、回転、及び剪断（英語では、ｓｈｅａｒｉｎｇ）を可能にする。以下では、簡単のため、混同の可能性がない場合には、オブジェクトのインスタンスに対してもオブジェクトという概念を使用する。
【００３２】
光線は、可能な命中オブジェクト（光線が当たるオブジェクト）が見つかるまで、まずトップレベル加速構造を通ってトラバースする（光線がシーン中を追跡する）。つぎに、光線はオブジェクトの局所座標系内へ変換され、さらに原始オブジェクトとの衝突点が見つかるまで、オブジェクトのボトムレベル加速構造内をトラバースする。原始オブジェクトは、さらなる構造を有していないオブジェクトである。レイトレーサの場合、原始オブジェクトは通常は三角形と球である。
【００３３】
この方法は実用において非常に良好に機能するが、それもオブジェクトの個数があまり大きくない間だけに限られている。なぜならば、各画像のトップレベル加速構造は新たに構築されなければならないからである。この加速構造の新たな構築は、この加速構造内のオブジェクトが動いた場合に必要となる。
【００３４】
本発明は、上述したオブジェクトへのシーンの分割を再帰的にサポートするハードウェア解決手段である。つまり、本発明は原始オブジェクトから成るオブジェクトに限定されず、このオブジェクトがそれ自体複数のオブジェクトから構成され得る複数のオブジェクトから再び合成されることも許す。図１は、どのようにしてオブジェクトの複数のレベルから木が生成され得るかを示している。まず、レベル１のオブジェクトとして葉がモデル化される。この葉は何倍にもインスタンシングされ、枝に配置される。これにより、さらなるオブジェクトが発生するが、今はレベル２のオブジェクトが発生する。これらの小さな枝は再びレベル３のオブジェクトであるより大きな枝又は木などへと何倍にもインスタンシングされる。ここではオブジェクト内にオブジェクトの複数のレベルが存在しており、同一のジオメトリを何度も使用しているため、シーンの表現が小さいということに注意されたい。
【００３５】
請求項２に従って本発明において使用されるレイキャスティングの方法は、以下の通りである。
【００３６】
光線は、可能な命中オブジェクトが見つかるまで、トップレベルの加速構造をトラバースする。このオブジェクトが原始オブジェクトであれば、光線とオブジェクトの交点が計算される。オブジェクトが原始オブジェクトでなければ、光線はオブジェクトの局所座標系へ変換され、そこでトラバースを再帰的に継続する。
【００３７】
この方法の重要な部分は光線をオブジェクトの局所座標系内へ変換するところである。これにより、原則的に、オブジェクトの位置測定はアフィン変換によって逆行して行われる。つまり、変換された光線はオブジェクトをもはや変換されたものとして見ない。この変換ステップは光線の始点と光線の方向のかなりコストのかかるアフィン変換を必要とする。しかしながら、このために必要な高価なハードウェアユニットはさらに別のタスクにも使用することができる。変換ユニットは、様々な種類の原始オブジェクトとの交点の計算にも、一次光線の計算にも、また様々な種類の二次光線の計算にも使用することができる。
【００３８】
一次光線を計算するために、公知のラスタ化法の場合に似たカメラ変換行列が用いられる。まず、Ｒ＝（（０，０，０），（ｘ，ｙ，１））という形のプレ一次光線、すなわち、始点（０，０，０）と方向（ｘ，ｙ，１）を有する光線が定義される。ここで、ｘ及びｙはピクセルの座標を表しており、一次光線はこの座標に対して計算されなければならない。各カメラ位置と向きとに対して、光線Ｒがカメラのピクセル（ｘ，ｙ）の入射方向に正確に一致するように光線Ｒを変換するアフィン変換が存在する。
【００３９】
原始オブジェクトとの交点を計算するために、光線は、中に正規化された原始オブジェクトを有する空間内へ変換される。原始オブジェクトが三角形である場合には、光線は、例えば、三角形がΔnorm＝（（１，０，０），（０，０，０），（０，１，０））の形を有するように、空間内へ変換される。具体的には、図１０を参照されたい。この変換はアフィン変換によって生じる。それに続く正規三角形との交点の計算は、一般的な場合とは違って、ハードウェアにおいて非常に簡単に解決することができる。三角形の法線が三角形空間内のベクトル（０，０，１）に変換されるように変換が選ばれた場合、光線と三角形の法線とのスカラー積は非常に簡単に三角形空間内で計算される。というのも、光線方向（ｘｔ，ｙｔ，ｚｔ）と三角形法線（０，０，１）とのスカラー積はまさに０*ｘｔ＋０*ｙｔ＋１*ｚｔ＝ｚｔだからである。
【００４０】
さらに、三角形法線を正規三角形空間内の適切な法線に写像することにより、それを表現するのに９つの浮動小数点数しか要さないように変換を選ぶことができる。しかしながら、これは、スカラー積が正規三角形空間内で計算されうる可能性を妨げてしまう。
【００４１】
この正規オブジェクト変換が、例えば、球、平面、平行六面体、円筒、及び他の多くの幾何学形状のような他の種類のオブジェクトにも使用可能であることは、明らかである。それにはそのつどただ１つの別の交点計算ユニットを用意するだけである。
【００４２】
これに関連した大きな利点は、各種類の原始オブジェクトがメモリ内で同一の表現を、つまり、オブジェクト正規空間内への変換を行うアフィン変換を、有していることである。このオブジェクト正規空間内への変換を正規空間変換と呼ぶ。
【００４３】
影光線と反射は、変換ユニットによって適切な変換と適切な光線を計算することにより効率的に計算される。
【００４４】
さらに、変換ユニットを用いて法線（表面に対して垂直なベクトル）を変換することも可能である。いくつかのシェーディングモデルは衝突点におけるジオメトリの法線を必要とするので、この法線変換は必要である。しかしながら、この法線は世界座標系内になければならない。このことは上記の方法においては必ずしも成り立っていない。むしろ、法線は衝突したオブジェクトの局所座標系内で初めて現れる。この法線はこの局所座標系から再び世界座標系内へと変換されなければならない。
【００４５】
しかしながら、この変換ユニットは欠点も有している。アフィン変換は、行列として記憶することができるが、三角形に対してもシーンのオブジェクトに対しても事前計算されなければならないので、三角形の頂点の位置をフレームごとに効率的に変化させることが直ちにはできない。これは今日のグラフィックスカードにおいては頂点シェーダで可能である。頂点シェーダは、空間内の点の動きの計算に最適化されたプログラム可能な専用ユニットである。
【００４６】
これを可能にするためには、データの事前計算から解放されなければならない。したがって、三角形との交点の計算のために、未知数を３つもつ線形方程式系を解く必要がある。これを陽的に解くには確かにより多くの浮動小数点演算を必要とするが、頂点シェーダとの関連では不可欠である。それゆえ、上記の変換ユニットを、線形方程式系を解くユニットで置き換えることが適切である。このユニットは、とりわけ、三角形との交差、又は、光線をオブジェクトの局所座標系へ変換することに使用することができる。
【００４７】
本発明において請求項１に従って使用されるレイトレーシング方法は、請求項２に記載された発明と類似に構成されているが、変換及び交点計算がレイトレーシングプロセッサに対する適切な指示で実施される点で異なっている。これに伴って、特に、オブジェクト光線交点計算のための代替的な方法の使用が可能になる。例えば、プリュッカー光線三角形テストの使用は頂点シェーダの効率的な使用を可能にする。
【００４８】
ディテールの豊富なシーンにおける問題は、特にある方向におけるオブジェクト密度が非常に高い場合に生じる不所望なエイリアシング効果である。その場合、例えば黒い三角形に当たった光線がカメラの最小の動きで突然白い三角形に当たってしまうということが起き得る。このような効果は画像内に時間的及び局部的な雑音を生じさせる。その理由は、レイトレーシングが通常は無限に細い光線を使用しており、ピクセルに影響を与える光は角錐状に拡がり、光線は距離とともに拡がるということを考慮していないことにある。したがって、本来、ピクセルの色を計算するには、この光角錐内にあるすべてのオブジェクトを考慮しなければならないが、それはリアルタイムシステムでは不可能である。そこで、単純化された新しい形態のコーントレーシングが救済策となる。任意に細い光線を考える代わりに、付加的に光線のビーム拡がり角が評価される。したがって、カメラまでの距離に応じて、相応する光線幅を計算することができる。トラバースの際に、光線によってその大部分を覆われる部分空間に遭遇した場合、さらにトラバースすることは状況によっては意味がない。有利には、この箇所で、計算のためにボリューム内部の簡単なジオメトリを使用することができる。その場合、ボリューム内におよそ１００万の三角形があることは無視してよい。これらの三角形は、場合によっては、山脈の壁を形成しているに過ぎず、これは光線の大きさゆえに色平面によっても近似することができる。
【００４９】
しかしながら、三角形が例えばエッフェル塔のような穴だらけの建物をモデル化する場合には、近似として、むしろ構成要素の格子の色と透明度を選ぶべきである。
【００５０】
有利には、このような簡略化されたジオメトリ表現が加速構造においてサポートされる。図６には、そのコンセプトがオクツリーの例で示されている。加速構造内の１つのノードが属している太線で縁取られたボリュームに関して、簡略化されたジオメトリが描かれている。光線はほぼノードの全ボリュームとオーバーラップしているので、この簡略化されたジオメトリが交点計算に使用される。
【００５１】
代替的な方法は、様々なディテールレベルを有するシーンのオブジェクトを保管しておくことである。つまり、様々な解像度又は三角形の個数を有するオブジェクトをモデル化し、さらに、オブジェクトからカメラまでの距離に応じて、ディテールの豊富な又は単純化されたオブジェクトを使用する。
【００５２】
上述の固定的に有線接続されたハードウェアベースのレイトレーシングパイプラインの場合、このレイトレーシングパイプラインをプログラム可能に構成するには費用がかかるということが不利と見なされるかもしれない。ソフトウェアレイトレーシングアプローチに比べると、ハードウェアベースのパイプラインは非常に融通性がなく、専門的である。
【００５３】
そこで、レイトレーシング法に特化させたＣＰＵの開発が救済策となる。この専用レイトレーシングプロセッサは、例えばＲＩＳＣプロセッサのような標準ＣＰＵから構成され、その命令セットは専用命令で拡張される。特に、加速構造を光線でトラバースさせるトラバース命令は重要である。さらに、この方法のいくつかの箇所では、主に３次元空間内で行われるコストのかかる算術演算が必要とされる。それゆえ、今日よく用いられているＳＳＥ２命令セットに似たベクトル算術ユニットをＣＰＵに備え付けることが有効である。
【００５４】
ＣＰＵのさらなる最適化は、方法の並列化の可能性を利用することによって達成することができる。これによれば、ＣＰＵ上で複数のスレッド（プログラムの流れ）を非常に効果的に走らせることができ、このことがＣＰＵの活用度と有効性を明らかに高める。このことはとりわけメモリ待ち時間に関して当てはまる。あるスレッドがメモリ問合せをした場合、問合せの間、別のスレッドを実行することができる。図５には、このようなＣＰＵの構造の一例を見ることができる。
【００５５】
動的シーンでは、各フレームについて加速構造の再計算をしなければならないため、加速構造を形成するための専用命令でＣＰＵの命令セットを拡張する必要がある。加速構造を形成する際、オブジェクトが属すべき所与の部分空間内にあるのか否かを判定しなければならない場合がしばしばある。加速構造の形成を最適化する専用ユニットは、非常に簡単に計算される事前判定を下すことによって、必要な計算を加速することができる。部分空間として、ｘ、ｙ、及びｚ軸に対して垂直な６つの境界面をもつボックスがよく使用される。このようなボックスはその頂点によって特徴付けることができる。それどころか、２つの点を定義するだけで十分である。三角形がこのボックスの中にあるのか否かの確認／判定は、多くの場合、単純に点の座標を比較することにより行われる。三角形が例えばＸ軸方向にボックスのずっと左側にある場合、三角形の３つの頂点のＸ座標はすべてボックスの頂点の最小Ｘ座標よりも小さい（図１３参照）。また、別の多くの配置も、例えば、三角形が完全にボックス内にあるのか否かも、同様に判定することができる。判定が可能でない場合には、ＳＡＰ（Separating Axis Theorem）のようなコストのかかる数学上の式を適用しなければならない。ボックスが別のボックスとオーバーラップするか否かの判定も同様に頂点比較によって判定することができる。
【００５６】
さらなる最適化のために、レイトレーシング法を実行する際、光線の射出時に、既に光線が交差したオブジェクト又は三角形を光線が何度も交差するのを防ぐ判定ユニットが使用される。これは、図２に見られるようなリストユニットをメールボックスで拡張することによって行われる。このメールボックスは、既に光線と交差したオブジェクト又は三角形をマークすることにより、光線の射出の際に三角形又はオブジェクトが光線と何度も交差するのを防ぐ。これにより、あまりに多くの光線オブジェクト交点又は光線三角形交点の計算を実行しなくてもよくなり、計算が加速される。このメールボックスは、メモリキャッシュとは違って、メモリへのメモリ問合せを防ぐのではなく、交点計算を防ぐ一種の交点計算キャッシュと見なすことができる。メールボックスの実施には、４ウェイキャッシュのような標準的なキャッシュ法を使用してよい。
【００５７】
レイトレーシングアーキテクチャのユニットは非常に大きなメモリ帯域幅を要する、つまり、単位時間当たりに非常に多くのデータが伝送されなければならない。通常、これは非常に多くのメモリチップを並列接続することによってのみ実現される。しかし、必要なメモリ帯域幅は複数のキャッシュレベル（ｎレベルキャッシュ）を適切に接続することによっても保証することができる。ここで、重要なのは、コヒーレンスと呼ばれるレイトレーシング法の特性である。コヒーレンスは、３Ｄ空間の同様の領域を通過する光線はまた加速構造内のほぼ同じデータにアクセスし、それに応じて同じオブジェクトにもアクセスするという事実を指している。この特性を利用すれば、高いキャッシュヒット率を達成することができる。つまり、必要なデータが高い確率でキャッシュ内に再び見つかり、時間をかけてメインメモリからロードする必要がない。キャッシュ自体は、複数のレイトレーシングユニットを賄うために、図４における図示に従って、例えばバイナリツリー内に配置されている。
【００５８】
本発明による装置は、３Ｄディスプレイと接続されれば、もちろん複雑な動くシーンの写真現実的な３次元リアルタイム表示にも使用することができる。これに関して、使用されるディスプレイの技術に応じて、画像出力の３つの実施形態を区別することができる。
【００５９】
第１には、立体感を含んだ２つの画像を時分割多重で水平方向にずらして交互にディスプレイに表示する実施形態。
【００６０】
第２には、立体感を表現する水平方向にずらした２つの画像を、これら２つの画像の画像情報を含んだ交互に現れる垂直のストライプの形でディスプレイに表示する実施形態。
【００６１】
第３には、２つの水平方向にずらした画像を２つの分割されたディスプレイに同時に又は時分割多重で表示する実施形態。
【００６２】
それぞれ右目又は左目に割り振られた２つの水平方向にずらした画像は、ディスプレイの相応する空間的配置によって又は画像分割装置（例えば、シャッター眼鏡、ストライプ状のフレネルプリズム／レンズ、偏光フィルタ）の使用によって、それぞれ一方の目にだけ見える。使用される３Ｄディスプレイとこの３Ｄディスプレイのビデオ信号制御の必要条件は従来の技術に従っており、より詳細には説明しない。３Ｄディスプレイの従来の技術に関する別の実施形態は、例として挙げた以下の文献から知ることができる：Computer Graphics / Addison-Wesley ISBN 020 1848406, DE 4417664, DE 19753040, DE 19827590, DE 19737449。
【００６３】
３次元動的シーンと画像のコンピュータアニメーションによる写真現実的なリアルタイム表示の使用は、３次元ＣＡＤデータの表示、医学的及び技術的分析的データの表示、フィルムアニメーション、飛行及び走行シミュレーションでの使用、ならびに、高価なリアルタイムグラフィックスを備えたコンピュータゲームにおけるいわゆるホームユースまでにわたっている。
【００６４】
さらに、この同じ方法を機能の実施に変更を加えることなく非写真現実的な画像生成（例えば、線画又はコミックスタイルの表示）にも使用することができる。同様に、技術的な変更を加えることなく、通常は画像計算には直接関係しない計算も実行可能である。例えば、幾何学的オブジェクト間の衝突検出（英語では、Ｃｏｌｌｉｓｉｏｎ Ｄｅｔｅｃｔｉｏｎ）と数値計算問題の離散的解法とがこのような計算に属している。上記のすべての用途はインタラクティブな領域に限定されるものではなく、方法又は装置に変更を加えずに、オフライン領域でも、例えば、映画フィルムの計算や非常にコストのかかる物理的シミュレーションにおいても、使用することができる。
【００６５】
レイトレーシング法の機能の実現とハードウェアによる実施は、複雑で高速の論理技術によって行われる。この論理技術は、単独の標準ＩＣから成る離散ディジタル論理回路の形態をとった有線接続のディジタル論理回路としても、又は、例えばＡＳＩＣのような特定の顧客もしくは用途向けに製造されたＩＣとしても、又は、例えばＣＰＵカーネルを用いたもしくは用いないＣＰＬＤもしくはＦＰＧＡ技術のような、複雑なプログラム可能論理素子／論理回路としても、又はこれらの技術の組合せとしても実施される。
【００６６】
以下に述べる本発明の実施例は、コンピュータグラフィックスカードのレイトレーシングユニットを説明したものである。このレイトレーシングユニットは、ハードウェアによるレイトレーシング法の実施を、例えば、自由プログラミング可能論理素子ＦＰＧＡ、ＡＳＩＣ技術、又は有線接続の専用チップにおいて実現することができる。
【００６７】
方法及び機能の流れを記述するのであれば、これらは純粋にハードウェア的に実現されなければならない。つまり、相応する論理ユニットとハードウェア的に実現された算術ユニットが形成されなければならない。
【００６８】
従来の技術による、データディスレプイ（陰極線管、ＴＦＴ、ＬＣＤ、又はプラズマモニタ）を制御する制御電子回路の標準機能とそのタイミングは周知のものと前提され、説明の対象とはならない。この標準機能の画像メモリと本発明によるレイトレーシング法の実現との間のインタフェースを説明する。
【００６９】
説明は２つの部分に分かれる。まずは、レイキャスティングパイプライン、略してＲＣＰが説明される。ここでは、光線がシーンをトラバースし、衝突点を返すことが、設計の核である。
【００７０】
第２部では、レイキャスティングパイプラインのために、これらレイキャスティングパイプラインのうちの複数をまとめて処理する最適化されたレイトレーシングアーキテクチャが説明される。
【００７１】
図２は、複数のサブユニットから成るレイキャスティングパイプラインユニット（ＲＣＰ）を示している。トラバースユニットは適切な加速構造、有利にはｋ−Ｄツリーを光線でトラバースする。光線は、命中オブジェクトとなりうるオブジェクトが存在するシーンの領域に至るまで、トラバースを続ける。この領域のオブジェクトは、リストユニットによって処理されるリストに記憶されている。リストユニットは、既に光線と交差したオブジェクト又は三角形をマークすることにより、光線の射出の際に三角形又はオブジェクトが光線と何度も交差するのを防ぐメールボックスも含んでいる。これにより、あまりに多くの光線オブジェクト交点又は光線三角形交点の計算を行わずに済み、計算が加速する。
【００７２】
つぎに、これらのオブジェクトを可能な交点に基づいて検査しなければならない。妥当な交点が存在しない場合には、トラバースを継続しなければならない。リストユニットは、オブジェクトに属するアフィン変換をロードするマトリクスロードユニットに、まだ処理されていない可能な命中オブジェクトを次々と送る。このアフィン変換は４×３行列によって表現することができる。この行列は、オブジェクト空間変換行列、又は、原始オブジェクトの正規空間内への変換を行う行列であってよい。マトリクスロードユニットが変換ユニットに行列を記憶した後、変換ユニットにより光線ユニットから光線が送られる。
【００７３】
変換後には２つのシナリオが考えられうる。１つには、オブジェクトはさらに別のオブジェクトを含んでいる場合がある。この場合、光線は再びトラバースユニット内に戻り、変換された光線がオブジェクト内でさらにトラバースを続ける。しかしならが、このオブジェクトが原始オブジェクトである場合には、光線は直接さらに交点計算ユニットに進み、交点計算ユニットは光線を正規オブジェクトと交差させる。交点計算ユニットは、前に説明したように、複数の正規オブジェクト（三角形、球など）をサポートすることができる。
【００７４】
計算された交点データは交点ユニットに集められる。交点ユニットがトラバースユニットへのフィードバックチャネルを提供しているため、トラバースユニットは、妥当な交点データが既に存しているか否かを知ることができる。
【００７５】
トラバースユニット、リストユニット、及びマトリクスロードユニットは、外部メモリにアクセスするレイキャスティングパイプラインの唯一のユニットである。トラバースユニットは加速構造にアクセスし、リストユニットはオブジェクトアドレスのリストにアクセスし、マトリクスロードユニットは行列の形態をとったアフィン変換にアクセスする。これら３つのユニットのすべては、メモリ帯域幅を確保するため、各自のキャッシュを介してメインメモリと接続されている。
【００７６】
図１２には、レイキャスティングパイプラインの簡易版が示されている。図１２では、最重要のユニット、すなわち、加速構造を光線でトラバースさせるトラバースユニット、リストを処理するリストユニット、ロードした変換を光線に適用する変換ユニット、及び、変換された光線を正規オブジェクトと交差させる交点計算ユニットしか描かれていない。
【００７７】
レイキャスティングパイプラインは、図３の表現に従って、適切なレイトレーシングアーキテクチャに埋め込まれている。図には、それぞれ３つのキャッシュを有する４つのレイキャスティングパイプラインユニットが示されている。ここで、これらのユニットの２つずつが１つのシェーディングユニットに接続されている。これらのシェーディングユニットは、画像のピクセルの色を計算するために、レイキャスティングパイプラインユニットを使用する。このために、シェーディングユニットは一次光線を射出し、レイキャスティングパイプラインが返す衝突点を処理し、二次光線を例えば光源へ射出する。シェーディングユニットは、有線接続されたハードウェア、又は後で説明するプログラム可能レイトレーシングプロセッサであってよい。
【００７８】
シェーディングユニットはレイキャスティングパイプラインの変換ユニットへのチャネルを有している。このチャネルは、カメラ行列と二次光線用の行列をロードし、それによりシェーディングユニットの計算コストを最小化するために使用される。シェーディングユニットがそれぞれ別々のテクスチャキャッシュとシェーディングキャッシュを有していると有利である。シェーディングキャッシュは、例えば色や材質データのような、シーンのジオメトリに関するシェーディング情報を収容している。テクスチャキャッシュはテクスチャメモリと接続されており、シェーディングユニットがテクスチャにアクセスするのを可能にする。各シェーディングユニットが各自のローカルフレームバッファを有していると有利である。このローカルフレームバッファには、処理／計算されたばかりのピクセルの色と輝度値が格納される。さらに、Ｚバッファがあると有利である。というのも、Ｚバッファは、以下で説明する標準ラスタ化ハードウェアとの結合で必要とされるからである。
【００７９】
ピクセルの色がシェーディングユニットにより完全に計算されているならば、この色をオプションの色調マッピングユニットを介してグローバルフレームバッファに書き込んでよい。色調マッピングユニットは、２４ビットのＲＧＢ空間に色を写像する単純な関数を色に適用する。また、オプションのローカルＺバッファに記憶されている幾何学的深度値（Ｚ値）を、オプションのグローバルＺバッファに伝送してもよい。
【００８０】
しかし、色又は新たなＺ値は、以前にＺバッファ内に存在したＺ値の方が大きい場合にのみ、フレームバッファ又はＺバッファに書き込まれる。これにより、既にラスタ化ハードウェア又は他のレイトレーシングパスによって計算された値よりもピクセルが幾何学的に前にある場合にのみ、ピクセルが書き込まれることが保証される。したがって、レイトレーシングハードウェアを同じフレームバッファ又はＺバッファ上で動作する標準ラスタ化ハードウェアと組み合わせることが可能である。この場合、フレームバッファ又はＺバッファはこの標準ラスタ化ハードウェアへのインタフェースでもある。
【００８１】
システム性能をさらに向上させるために、オプションとして、さらに別のシェーディングユニットを付属のレイキャスティングパイプラインとキャッシュとに並列接続させてもよい。この場合、性能向上効果はデータ構造及び処理構造の拡大にある。
【００８２】
シーン全体がレイトレーシングチップのローカルメインメモリに入ると期待することはできない。この問題を解決するために、ローカルメインメモリを、シーンのより大きなブロックをキャッシュするより大きなキャッシュとして使用してよい。本来のシーンは別の場所にあり、必要なときにＤＭＡを介してダウンロードされる。仮想的なメモリ使用のためのこの方法により、レイトレーシングチップのメインメモリには入らない非常に大きなシーンを視覚化することが可能になる。
【００８３】
フォトンマッピングは、仮想光子を光源からシーンへ射出し、シーンの表面に集める標準的方法である。これにより、シーンの光分布をシミュレートすることができる。このことは特に火面についても当てはまる。光子が射出されると、光子によって加速構造が形成される。この加速構造は、例えば、ｋ−ｄツリーであってよい。今や、標準的なレイトレーシング法によりシーンを視覚化し、各衝突点において、そこに入射する光の輝度を色計算に算入する際に、この点の近傍に衝突するすべての光子のエネルギーが合計されるようにすることにより、この計算された光子最終分布の描写を行うことができる。このためには、光子の加速構造において隣接するすべての光子を探さなければならない。このタスクはトラバースユニットによりサポートされる。トラバースユニットは、そのために、光線に沿ってではなく、ボリュームをトラバースする。このようにして、隣接するすべての光子は、例えばそのエネルギーを合計することによって、処理される。
【００８４】
通常、レイトレーシング法は無限に細い光線を用いるが、これはサンプルアーチファクト（エイリアシング）を生じさせてしまう。遥かに良好な近似は光線の代わりに光円錐を使用することで得られる。カメラのピクセルを照明する光は、ばらばらの方向からではなく、光円錐によって非常に良く近似することのできる一種の角錐から来る。光円錐又は光角錐によって記述される、この空間ボリュームの前から後ろへのトラバースもまた、トラバースユニットによって専用機能として実行することができる。図６には、光円錐の２次元描写が示されている。
【００８５】
ディスプレイを制御するための信号処理とディスプレイ又はモニタに対するタイミングの発生は、周知のように、オプションのラスタ化ハードウェアによって行う、又は、所望の用途にとって有利な場合には、適切な機能ユニットで実施してよい。こうして、ハードウェア的に実施されたレイトレーシング法と機能とを備えた標準ラスタ化ハードウェアの基本機能を、非常に性能のよいリアルタイムハードウェアアーキテクチャに結合することができる。
【００８６】
本発明の第２の別の実施例は、本発明により説明された専用のレイトレーシング機能及び方法をプログラム制御により実施する自由にプログラム可能なレイトレーシングＣＰＵ又はレイトレーシングプロセッサの構成と使用に基づいている。この実施例では、適切な論理及び機能の並列性により、個々の機能を片付けるのに、ＣＰＵの数サイクル、有利には、１又は２サイクルしか必要としない。
【００８７】
レイトレーシングプロセッサの内部アルゴリズム、方法、及び機能の流れを記述するのであれば、これらはハードウェア記述言語、例えば、ＨＤＬ、ＶＨＤＬ、又はＪＨＤＬを用いて書かれ、相応するハードウェアへ移されなければならない。実施される方法及び機能と共に、レイトレーシングプロセッサのハードウェア的実施は、例えば、自由プログラム可能論理素子ＦＰＧＡ、ＡＳＩＣ技術、ＦＰＧＡ／ＡＳＩＣを備えたディジタル信号プロセッサの組合せ、又は、有線接続された専用チップにより行うことができる。
【００８８】
このことは、個々の機能をプログラム制御により呼び出すことのできる適切な論理ユニット及びハードウェア的に実現された算術ユニットを形成しなければならないことを意味している。使用されるハードウェア技術の複雑さに応じて、チップごとに、別の論理機能を備えた又は備えていない１つ又は複数のプロセッサを実現してもよい。
【００８９】
レイトレーシングプロセッサは、ベクトル算術命令と「トラバース」や「加速構造の形成」のような専用レイトレーシング命令とを実行するように設計された完全にプログラム可能な計算ユニットである。これに関して、設計は機能ユニットを追加して行ってもよいが、既にある機能ユニットを用いて、場合によっては少数の論理素子を追加して、行ってもよい。例えば、トラバースは専用の機能ユニットによって行ってもよいし、又は既にある算術機能ユニットを少数の論理機能ユニットで拡張することによって行ってもよい。
【００９０】
図１１に見られるように、図５に示されている複数のレイトレーシングプロセッサが並列に接続される。メモリインタフェースは、必要なメモリ帯域幅を用意するキャッシュ階層から形成される。このプロセスは、隣接する光線の強いコヒーレンスのため、効率的に可能である。レイトレーシングプロセッサのコンセプトでは、各レイトレーシングプロセッサは画像の正確に１つのピクセルを処理するか、又は複数のピクセルから成るパケットを処理する。その際、個々のそれぞれのピクセルの計算が１つの計算スレッドに相当する。これらのスレッドのうちの複数は１つのパケットに束ねられ、全体として同期して処理される。同期して処理されたスレッドは、つねに共通して同じ命令を実行するという点で優れている。これにより、効率的なハードウェアの構築と、各スレッドに対して個別にではなく、パケット全体ごとにメモリ問合せを行うことが可能になる。とりわけ、このメモリ問合せの減少は、スレッド処理に対するパケット処理の重要な利点である。
【００９１】
図１１のスレッドジェネレータは、レイトレーシングプロセッサ上で実行されるスレッドを生成する。スレッドジェネレータはレイトレーシングプロセッサによってもプログラムすることができる。画像のピクセルをキャッシュコヒーレントな方法（例えば、ヒルベルト曲線）でスキャンする専用機能により、レイトレーシングプロセッサにコヒーレントなスレッドを最適に供給することが可能になる。これにより、必要なメモリ問合せが減少する。スレッドジェネレータはまたＤＭＡインタフェースを介してメインメモリにアクセスすることもできる。したがって、個々のスレッドの開始値を前の処理ステップにおいて生成し、後にこれらのデータから再び新しいスレッドを生成するために、メモリに書き込んでおいてもよい。
【００９２】
ピクセルの処理はレイトレーシングプロセッサ上で動作するソフトウェアプログラムによって行われる。このソフトウェアプログラムは、ハードウェアが光線のパケット上で動作する場合でもピクセルの色値を計算する再帰的な方法の流れを記述したものである。したがって、パケット管理はプログラミングモデルに対して透過的である。
【００９３】
図５はレイトレーシングプロセッサの構造の一例を示している。見るべきことは、２つの専用コプロセッサに並列接続された標準プロセッサカーネル（ＲＩＳＣカーネル）である。これらのコプロセッサはそれぞれ各自のレジスタを有している。しかしながら、専用命令により一方のコプロセッサのレジスタ内容を他方のコプロセッサに移動させることも可能である。トラバースカーネルは、光線によって加速構造を効率的にトラバースさせることのできる専用コプロセッサである。この加速構造のトラバースのために、トラバースカーネルは加速構造のノード（ノード-キャッシュ）への専用メモリインタフェースを必要とする。ベクトル算術カーネルは、３Ｄ空間内で効率的に演算を実行することのできる専用コプロセッサである。それぞれのレイトレーシングソフトウェアが必要とするベクトル加算、スカラー乗算、クロス積、及びベクトル積は、このユニットによって迅速に計算することができる。ベクトル算術ユニットは、全ベクトルを１サイクル内でロードすることのできる専用キャッシュへのアクセスを必要とする。
【００９４】
トラバース命令のセマンティクスは以下のようにしてよい。レイトレーシングＣＰＵは、光線の光源と方向及びトラバースされるべき加速構造のアドレスによって専用レジスタを記述する。専用命令が呼び出されると、専用トラバースユニットが始動する。このユニットは加速構造をトラバースし、オブジェクトを含むすべてのノードをリストユニットに送る。このリストユニットは、既に本発明の第１の実施例で説明したメールボックス機構を含んでいてよい。各オブジェクトについて、光線をこのオブジェクトと交差させる小さなプログラムがＣＰＵ上で実行される。光線とオブジェクトの妥当な交点が見つかれば、光線と交差したオブジェクトがプログラムに返される。
【００９５】
レイトレーシングプロセッサ内にハードウェア的に実施されている個々の命令又は論理機能は、有線接続された本発明の第１の実施形態において既に説明した同一のアルゴリズムを内容としている。しかし、これを補足して、この命令セットを、同じくプログラム制御により活動化させることのできる有線接続された別の命令及び機能で補ってもよい。専用トラバース動作と、ベクトル算術と、レイトレーシングプロセッサ上での複数のスレッドの並列処理とにより、リアルタイムアプリケーションに必要な計算能力が提供され、同時に、システム速度に対するメモリレイテンシー（メモリ問合せの待ち時間）の影響が最小化又は無効化さえされる。
【００９６】
ピクセルの色が完全に計算されていれば、この色をフレームバッファに書き込むことができる。場合によっては、さらに距離をＺバッファに書き込んでもよい。これにより、ラスタ化ハードウェアとの結合とディスプレイへの適切な表示が可能になる。
【００９７】
請求項１０には、幾何学的オブジェクトを記憶又は参照せず、むしろ空間影響量又は材質変更パラメータを含む付加的な空間分解データ構造の使用が記載されている。この空間影響量は、例えば、霧、霞、塵粒、又は熱煙であってよい。ここで、例えば熱煙は煙のボリュームを通して見えるシーンの変化を結果としてもたらすこともありうる。別の空間影響量は、例えば空想上の存在を表現する際に使用されるような、光源、又は、材質を変化させる背光である。ここで、空間分解データ構造の使用により計算コストを著しく低減することが可能である。なぜならば、空間的に影響を持ちうるような位置にある影響量のみを考慮すればよいからである。
【００９８】
請求項１１には、三角形から構成されているのではない又は三角形だけから構成されているのではない３次元シーンの処理を可能にし、必要ならば、他の幾何学的要素を三角形又は簡単に処理できる中間的表現に変える拡張が記載されている。これについては、ハードウェアを機能ユニットで拡張する、又は既にあるユニットが機能を実施することにより、付加的な機能が達成される。
【００９９】
請求項１２には、光線処理の結果として、光線ごとに、最も近いオブジェクト光線交点だけでなく、さらにより遠いオブジェクト光線交点も計算することができるようにする拡張が記載されている。これについては、光線源からの距離に応じて結果を分類すると有利である。結果ごとの交点の最大数を定数として固定してもよいし、光線ごとに交差したオブジェクトのパラメータに応じて行ってもよい。この技法は透明なオブジェクトを通過した光線を計算するために使用することができる。
【０１００】
請求項１３には、付加的な又は既にある機能ユニットを用いて、画像の計算において所定の要素が何度使用されたかをカウントすることができるようにする拡張が記載されている。これについては、カウントされる要素は非常に様々であってよく、要素の考えられうる分類はメモリ内でのアドレス又は要素のＩＤを介して行うことができる。これらの要素には以下のものが属する：
動的及び幾何学的オブジェクト、部分的又は完全な材質記述、空間記述データ構造の要素又はサブグループ、プログラム又はプログラム機能、個々のメモリセル、ならびに、メモリページ全体又はメモリ領域全体。
【０１０１】
請求項１４には、空間記述データ構造を部分ごとに計算すること又は完全な３次元シーンを計算する機能の拡張が記載されている。ここで、動的オブジェクト又は動的部分オブジェクト又は幾何学的オブジェクトごとの付加的なパラメータが空間記述データ構造の計算法に対して影響を有している。このような影響は、例えば、所定の空間ボリューム内に幾何学的オブジェクトを有さないオブジェクトを特定するようなものであってよい。これにより、空間記述データ構造をより効率的に計算し、さらに１画像当たりの計算コストをさらに低減することが可能になる。
【０１０２】
図面の説明
図１は、どのようにしてオブジェクトの複数のレベルから木が生成され得るかを示している。まず、レベル１のオブジェクト１０１として葉がモデル化される。この葉１０１は何倍にもインスタンシングされ、枝１０２に配置される。これにより、さらなるオブジェクトが発生するが、今はレベル２のオブジェクトが発生する。これらの小さな枝１０２は再びレベル３のオブジェクトである木１０３へと何倍にもインスタンシングされる。
【０１０３】
図２は、最も重要なデータパスとキャッシュへのインタフェースとを備えたレイキャスティングパイプラインユニット２００を示している。矢印２０１はシェーディングユニットの方へ向かい、矢印２０２はシェーディングユニットから来ている。さらに以下のものが示されている：
２０３：トラバースユニット
２０４：メールボックスを含んだリストユニット
２０５：マトリクスロードユニット
２０６：光線ユニット
２０７：変換ユニット
２０８：交点計算ユニット
２０９：交点ユニット
２１０：ノードキャッシュ
２１１：リストキャッシュ
２１２：マトリクスキャッシュ
【０１０４】
図３は、本発明の実施例のトップレベルの線図を示している。４つのレイキャスティングパイプライン（ＲＣＰ）は、キャッシュ階層を介して、ノード用、リスト用、及び行列用の別個のメモリに接続されている。この設計例では、ＲＣＰの２つずつが１つのシェーディングユニットに接続されており、シェーディングユニットはローカルフレームバッファとローカルＺバッファへのアクセスを有している。これらのバッファを介して、色値は色調マッピングユニットによりグローバルフレームバッファに書き込まれ、インド値は直接グローバルＺバッファに送られる。このＺバッファとフレームバッファに、従来の技術によるラスタ化ハードウェア（ラスタ化パイプライン）を接続してもよい。
図中には、以下のものが示されている：
３０１：ラスタ化ハードウェア
３０２：フレームバッファ
３０３：ビデオ出力
３０４：色調マッピングユニット
３０５：Ｚバッファ
３０６：フレームバッファ１
３０７：Ｚバッファ１
３０８：テクスチャキャッシュ１
３０９：シェーディングキャッシュ１
３１０：シェーディングユニット１
３１１：ノードキャッシュ１
３１２：リストキャッシュ１
３１３：マトリクスキャッシュ１
３１４：ＲＣＰ１
３１５：ノードキャッシュ２
３１６：リストキャッシュ２
３１７：マトリクスキャッシュ２
３１８：ＲＣＰ２
３１９：フレームバッファ２
３２０：Ｚバッファ２
３２１：テクスチャキャッシュ２
３２２：シェーディングキャッシュ２
３２３：シェーディングユニット２
３２４：ノードキャッシュ３
３２５：リストキャッシュ３
３２６：マトリクスキャッシュ３
３２７：ＲＣＰ３
３２８：ノードキャッシュ４
３２９：リストキャッシュ４
３３０：マトリクスキャッシュ４
３３１：ＲＣＰ４
【０１０５】
図４は、チップ内で必要な内部メモリ帯域幅を提供するキャッシュ下部構造を示している。図中では、ｎレベルのバイナリキャッシュであるが、他の階層構造も考えられる。
図中には、以下のものが示されている：
４０１：ノードキャッシュ１
４０２：ノードキャッシュ２
４０３：ノードキャッシュ３
４０４：ノードキャッシュ４
４０５：ノードキャッシュ５
４０６：ノードキャッシュ６
４０７：ノードキャッシュ７
４０８：ノードメモリ
４０９：リストキャッシュ１
４１０：リストキャッシュ２
４１１：リストキャッシュ３
４１２：リストキャッシュ４
４１３：リストキャッシュ５
４１４：リストキャッシュ６
４１５：リストキャッシュ７
４１６：リストメモリ
４１７：マトリクスキャッシュ１
４１８：マトリクスキャッシュ２
４１９：マトリクスキャッシュ３
４２０：マトリクスキャッシュ４
４２１：マトリクスキャッシュ５
４２２：マトリクスキャッシュ６
４２３：マトリクスキャッシュ７
４２４：マトリクスメモリ
４２５：テクスチャキャッシュ１
４２６：テクスチャキャッシュ２
４２７：テクスチャメモリ
４２８：シェーディングキャッシュ１
４２９：シェーディングキャッシュ２
４３０：シェーディングキャッシュ３
４３１：シェーディングメモリ
【０１０６】
図５はレイトレーシングＣＰＵの実施例を示している。ここで、ブロックは以下の意味を有している：
５０１：命令ロード
５０２：命令メモリ
５０３：ＲＩＳＣカーネル
５０４：キャッシュ
５０５：トラバースカーネル
５０６：ノードキャッシュ
５０７：ベクトル算術カーネル
５０８：ベクトルキャッシュ
【０１０７】
図６はオクツリーノードにおける簡略化されたジオメトリの例を示している。この例では、参照番号６０１は光円錐を表しており、参照番号６０２は「簡略化されたジオメトリ」を表している。
【０１０８】
図７は、単純なシーンにおける正則グリッド加速構造の例を示している。空間は簡単のため２Ｄでのみ示されている。参照番号７０１は光線を表している。
【０１０９】
図８は、単純なシーンにおけるｋ−Ｄツリー加速構造の例を示している。空間は簡単のため２Ｄでのみ示されている。参照番号８０１は光線を表している。
【０１１０】
図９は、単純なシーンにおけるオクツリー加速構造の例を示している。空間は簡単のため２Ｄでのみ示されている。参照番号９０１は光線を表している。
【０１１１】
図１０は、グローバル空間から正規三角形空間への三角形の変換を示している。光線１００１と三角形１００２が見られる。矢印１００３によって表されたアフィン変換により、変換された光線１００４と正規三角形１００５が生じる。グローバル空間は左側の座標系で表され、正規三角形空間は右側の座標系で表される。
【０１１２】
図１１は、専用レイトレーシングプロセッサに基づいた本発明の実施例を示している。ここで、ブロックは以下の意味を有している：
１１０１：ラスタ化ハードウェア
１１０２：スレッドジェネレータ
１１０３：Ｚバッファ／フレームバッファ
１１０４：ビデオ出力
１１０５：レイトレーシングプロセッサ１
１１０６：レイトレーシングプロセッサ２
１１０７：レイトレーシングプロセッサ３
１１０８：レイトレーシングプロセッサ４
１１０９：キャッシュ１
１１１０：キャッシュ２
１１１１：キャッシュ３
１１１２：キャッシュ４
１１１３：キャッシュ５
１１１４：キャッシュ６
１１１５：キャッシュ７
１１１６：メインメモリ
【０１１３】
図１２は、図２に示されているレイキャスティングパイプラインの簡易版を示している。ここで、ブロックは以下の意味を有している：
１２０１：トラバースユニット
１２０２：ノードキャッシュ
１２０３：リストユニット
１２０４：リストキャッシュ
１２０５：変換ユニット
１２０６：マトリクスキャッシュ
１２０７：交点計算ユニット
矢印１２０８はシェーディングユニットから来ている。
【０１１４】
図１３は、三角形の頂点とボックスの頂点の比較により、三角形がボックスにオーバーラップしているか否かを判定することのできる簡単なケースを示している。三角形のＸ座標がボックスの最小Ｘ座標よりも小さければ、三角形はボックスの外にある。三角形は参照番号１３０１で表され、ボックスは参照番号１３０２で表されている。
【図面の簡単な説明】
【０１１５】
【図１】どのようにしてオブジェクトの複数のレベルから木が生成され得るかを示す。
【図２】最も重要なデータパスとキャッシュへのインタフェースとを備えたレイキャスティングパイプラインユニット２００を示す。
【図３】本発明の実施例のトップレベルの線図を示す。
【図４】チップ内で必要な内部メモリ帯域幅を提供するキャッシュ下部構造を示す。
【図５】レイトレーシングＣＰＵの実施例を示す。
【図６】オクツリーノードにおける簡略化されたジオメトリの例を示す。
【図７】単純なシーンにおける正則グリッド加速構造の例を示す。
【図８】単純なシーンにおけるｋ−Ｄツリー加速構造の例を示す。
【図９】単純なシーンにおけるオクツリー加速構造の例を示す。
【図１０】グローバル空間から正規三角形空間への三角形の変換を示す。
【図１１】専用レイトレーシングプロセッサに基づいた本発明の実施例を示す。
【図１２】図２に示されているレイキャスティングパイプラインの簡易版を示す。
【図１３】三角形の頂点とボックスの頂点の比較により、三角形がボックスにオーバーラップしているか否かを判定することのできる簡単なケースを示す。
【特許請求の範囲】
【請求項１】
複雑な動的３次元シーンをレイトレーシング法により写真現実的に表示する装置であって、該装置は少なくとも１つのプログラム可能レイトレーシングプロセッサを有しており、該プロセッサにおいては、
・専用のトラバース命令、及び／又は
・ベクトル算術命令、及び／又は
・レイトレーシング加速構造を形成するための命令、及び／又は
・レイトレーシング法を実行する際、光線の射出時に、既に光線が交差したオブジェクト又は三角形を前記光線が何度も交差するのを抑制するために用いられる少なくとも１つの判定ユニット（メールボックス）が実施され、
前記装置は、複数のスレッドを並列処理することができ、且つ、複数のスレッドを自動的に同期して処理することができるように構成されており、
前記装置は、ｎレベルのキャッシュ階層及び／又は仮想メモリ管理及び／又はメインメモリとの直接接続を使用することができる、ことを特徴とする複雑な動的３次元シーンをレイトレーシング法により写真現実的に表示する装置。
【請求項２】
複雑な動的３次元シーンをレイトレーシング法により写真現実的に表示する装置であって、該装置は、少なくとも１つの専用トラバースユニット、少なくとも１つのリストユニット、レイトレーシング法を実行する際、光線の射出時に、既に光線が交差したオブジェクト又は三角形を前記光線が何度も交差するのを抑制するために用いられる少なくとも１つの判定ユニット（メールボックス）、少なくとも１つの交点計算ユニット、加速構造を形成するための少なくとも１つのユニット、少なくとも１つの変換ユニット、及び／又は、線形方程式系を解くための少なくとも１つのユニットを有しており、複数の光線又はスレッドを並列処理することができ、複数の光線又はスレッドを自動的に同期して処理することができ、動的オブジェクト内に動的オブジェクトの任意個数のレベルを実現することができ、前記装置は、ｎレベルのキャッシュ階層及び／又は仮想メモリ管理及び／又はメインメモリとの直接接続を使用することができる、ことを特徴とする複雑な動的３次元シーンをレイトレーシング法により写真現実的に表示する装置。
【請求項３】
少なくとも１つの専用トラバースユニット、少なくとも１つのリストユニット、レイトレーシング法を実行する際、光線の射出時に、既に光線が交差したオブジェクト又は三角形を前記光線が何度も交差するのを抑制するために用いられる少なくとも１つの判定ユニット（メールボックス）、少なくとも１つの交点計算ユニット、加速構造を形成するための少なくとも１つのユニット、及び、少なくとも１つのレイトレーシングプロセッサを有する、請求項１記載の装置。
【請求項４】
加速構造を形成するための少なくとも１つのユニットが専用のハードウェアにより又はプログラム可能なユニットもしくはレイトレーシングプロセッサにより実現され、前記加速構造のデータ構造構築のため、ならびに、ある三角形又はあるボックスが別のボックスとオーバーラップしているか否かの判定のために、機能的なプロセスが実行され、その際、前記判定は、前記少なくとも１つのユニットが前記三角形又はボックスの角と前記第２のボックスの角の頂点比較に依存して判定を行うことにより実行され、判定が可能でない場合には、保守的な判定が下されるか、又は、この場合、正確な判定を下すプログラムが前記プログラム可能レイトレーシングプロセッサ上で開始されるか、又は、別の専用ハードウェアユニットが正確な判定を下すか、又は全計算が前記レイトレーシングプロセッサ上で行われる、請求項１から３のいずれか１項記載の装置。
【請求項５】
前記少なくとも１つの変換ユニット及び／又は線形方程式系を解くための前記少なくとも１つの論理ユニットが、一次光線生成及び／又はオブジェクト空間変換及び／又は三角形正規空間変換及び／又は反射光線計算及び／又は透過光線計算及び／又は影光線計算及び／又は法線変換のために機能的に使用される、請求項３又は４記載の装置。
【請求項６】
前記少なくとも１つのトラバースユニット又は前記トラバース命令は、光線に沿ってだけでなくボリュームに沿ってもトラバースすることができ、そのため、前記ボリューム内のすべてのオブジェクトを処理することができる、請求項１から５のいずれか１項記載の装置。
【請求項７】
前記少なくとも１つのトラバースユニット又は前記トラバース命令は、光線に沿ってだけでなく光円錐又は光角錐に沿ってもトラバースすることができ、そのため、前記光円錐又は光角錐内にあるすべてのオブジェクトを前から後ろへ処理することができる、請求項１から６のいずれか１項記載の装置。
【請求項８】
前記少なくとも１つのトラバースユニットの機能と前記トラバース命令のハードウェアによる実施は、ｋ−Ｄツリー法又はオクツリー法又は正則グリッド法又はバウンディングボリューム階層法に基づいた加速構造により光線をトラバースすることに基づいており、各々の加速構造ノードには簡略化されたジオメトリデータが記憶されており、該ジオメトリデータは、考察される光円錐が前記ノードに属するボリュームの大部分を通過するとすぐに使用される、請求項１から７のいずれか１項記載の装置。
【請求項９】
複数のレイトレーシングユニットが複数のチップ及び／又は複数のボード上で並列して動作する、請求項１から６のいずれか１項記載の装置。
【請求項１０】
前記レイトレーシングハードウェアはさらに、既存の及び／又は付加的な機能ユニットにより評価される空間影響量及び／又は材質変更パラメータが記憶された空間分解データ構造を使用する、請求項１から９のいずれか１項記載の装置。
【請求項１１】
前記レイトレーシングハードウェアは、専ら三角形から形成されているのではなく、他の幾何学的オブジェクトも含む３次元シーンを処理し、該幾何学的オブジェクトは、必要ならば他の幾何学的オブジェクトに変えられる、及び／又は、付加的な及び／又は既存の機能ユニットにより及び／又は前記プログラム可能レイトレーシングプロセッサにより直接処理される、請求項１から１０のいずれか１項記載の装置。
【請求項１２】
前記レイトレーシングハードウェアは３次元シーンを処理し、１つの光線について、０個の、１つの、又は複数のオブジェクト光線交点を、距離に応じて分類して又は分類せずに計算し、その際、計算されたオブジェクト光線交点の個数は定数として固定される及び／又はオブジェクトの付加的パラメータにより記述されるようにしてよい、請求項１から１１のいずれか１項記載の装置。
【請求項１３】
前記レイトレーシングハードウェアは、画像の計算において、動的及び／又は幾何学的オブジェクト、及び／又は、材質記述、及び／又は、空間記述データ構造の要素及び／又はサブグループ、及び／又は、プログラム、及び／又は、メモリセル、及び／又は、メモリページが何回使用されたかを、付加的な及び／又は既存の機能ユニットによりカウントする、請求項１から１２のいずれか１項記載の装置。
【請求項１４】
前記レイトレーシングハードウェアは、付加的な及び／又は既存の機能ユニットにより、空間記述データ構造を部分ごとに計算すること又は完全な３次元シーンを計算することができ、その際、動的オブジェクト及び／又は動的部分オブジェクト及び／又は幾何学的オブジェクトごとに付加的なパラメータが前記空間記述データ構造の計算法に対して影響を有している、請求項１から１３のいずれか１項記載の装置。
【請求項１５】
前記レイトレーシングハードウェアは、共通のＺバッファ及びフレームバッファを介して、同一のチップ上に又は前記レイトレーシングハードウェアのように別個のチップ上にあるラスタ化ハードウェアに接続されている、請求項１から１４のいずれか１項記載の装置。
【請求項１６】
複数のレイトレーシングユニットが並列に動作し、計算に必要なデータは該レイトレーシングユニットのメモリ上に分散しており、必要なときにそのつど、必要なデータを記憶している前記ユニットからダウンロードされる、請求項１から１５のいずれか１項記載の装置。
【請求項１】
複雑な動的３次元シーンをレイトレーシング法により写真現実的に表示する装置であって、該装置は少なくとも１つのプログラム可能レイトレーシングプロセッサを有しており、該プロセッサにおいては、
・専用のトラバース命令、及び／又は
・ベクトル算術命令、及び／又は
・レイトレーシング加速構造を形成するための命令、及び／又は
・レイトレーシング法を実行する際、光線の射出時に、既に光線が交差したオブジェクト又は三角形を前記光線が何度も交差するのを抑制するために用いられる少なくとも１つの判定ユニット（メールボックス）が実施され、
前記装置は、複数のスレッドを並列処理することができ、且つ、複数のスレッドを自動的に同期して処理することができるように構成されており、
前記装置は、ｎレベルのキャッシュ階層及び／又は仮想メモリ管理及び／又はメインメモリとの直接接続を使用することができる、ことを特徴とする複雑な動的３次元シーンをレイトレーシング法により写真現実的に表示する装置。
【請求項２】
複雑な動的３次元シーンをレイトレーシング法により写真現実的に表示する装置であって、該装置は、少なくとも１つの専用トラバースユニット、少なくとも１つのリストユニット、レイトレーシング法を実行する際、光線の射出時に、既に光線が交差したオブジェクト又は三角形を前記光線が何度も交差するのを抑制するために用いられる少なくとも１つの判定ユニット（メールボックス）、少なくとも１つの交点計算ユニット、加速構造を形成するための少なくとも１つのユニット、少なくとも１つの変換ユニット、及び／又は、線形方程式系を解くための少なくとも１つのユニットを有しており、複数の光線又はスレッドを並列処理することができ、複数の光線又はスレッドを自動的に同期して処理することができ、動的オブジェクト内に動的オブジェクトの任意個数のレベルを実現することができ、前記装置は、ｎレベルのキャッシュ階層及び／又は仮想メモリ管理及び／又はメインメモリとの直接接続を使用することができる、ことを特徴とする複雑な動的３次元シーンをレイトレーシング法により写真現実的に表示する装置。
【請求項３】
少なくとも１つの専用トラバースユニット、少なくとも１つのリストユニット、レイトレーシング法を実行する際、光線の射出時に、既に光線が交差したオブジェクト又は三角形を前記光線が何度も交差するのを抑制するために用いられる少なくとも１つの判定ユニット（メールボックス）、少なくとも１つの交点計算ユニット、加速構造を形成するための少なくとも１つのユニット、及び、少なくとも１つのレイトレーシングプロセッサを有する、請求項１記載の装置。
【請求項４】
加速構造を形成するための少なくとも１つのユニットが専用のハードウェアにより又はプログラム可能なユニットもしくはレイトレーシングプロセッサにより実現され、前記加速構造のデータ構造構築のため、ならびに、ある三角形又はあるボックスが別のボックスとオーバーラップしているか否かの判定のために、機能的なプロセスが実行され、その際、前記判定は、前記少なくとも１つのユニットが前記三角形又はボックスの角と前記第２のボックスの角の頂点比較に依存して判定を行うことにより実行され、判定が可能でない場合には、保守的な判定が下されるか、又は、この場合、正確な判定を下すプログラムが前記プログラム可能レイトレーシングプロセッサ上で開始されるか、又は、別の専用ハードウェアユニットが正確な判定を下すか、又は全計算が前記レイトレーシングプロセッサ上で行われる、請求項１から３のいずれか１項記載の装置。
【請求項５】
前記少なくとも１つの変換ユニット及び／又は線形方程式系を解くための前記少なくとも１つの論理ユニットが、一次光線生成及び／又はオブジェクト空間変換及び／又は三角形正規空間変換及び／又は反射光線計算及び／又は透過光線計算及び／又は影光線計算及び／又は法線変換のために機能的に使用される、請求項３又は４記載の装置。
【請求項６】
前記少なくとも１つのトラバースユニット又は前記トラバース命令は、光線に沿ってだけでなくボリュームに沿ってもトラバースすることができ、そのため、前記ボリューム内のすべてのオブジェクトを処理することができる、請求項１から５のいずれか１項記載の装置。
【請求項７】
前記少なくとも１つのトラバースユニット又は前記トラバース命令は、光線に沿ってだけでなく光円錐又は光角錐に沿ってもトラバースすることができ、そのため、前記光円錐又は光角錐内にあるすべてのオブジェクトを前から後ろへ処理することができる、請求項１から６のいずれか１項記載の装置。
【請求項８】
前記少なくとも１つのトラバースユニットの機能と前記トラバース命令のハードウェアによる実施は、ｋ−Ｄツリー法又はオクツリー法又は正則グリッド法又はバウンディングボリューム階層法に基づいた加速構造により光線をトラバースすることに基づいており、各々の加速構造ノードには簡略化されたジオメトリデータが記憶されており、該ジオメトリデータは、考察される光円錐が前記ノードに属するボリュームの大部分を通過するとすぐに使用される、請求項１から７のいずれか１項記載の装置。
【請求項９】
複数のレイトレーシングユニットが複数のチップ及び／又は複数のボード上で並列して動作する、請求項１から６のいずれか１項記載の装置。
【請求項１０】
前記レイトレーシングハードウェアはさらに、既存の及び／又は付加的な機能ユニットにより評価される空間影響量及び／又は材質変更パラメータが記憶された空間分解データ構造を使用する、請求項１から９のいずれか１項記載の装置。
【請求項１１】
前記レイトレーシングハードウェアは、専ら三角形から形成されているのではなく、他の幾何学的オブジェクトも含む３次元シーンを処理し、該幾何学的オブジェクトは、必要ならば他の幾何学的オブジェクトに変えられる、及び／又は、付加的な及び／又は既存の機能ユニットにより及び／又は前記プログラム可能レイトレーシングプロセッサにより直接処理される、請求項１から１０のいずれか１項記載の装置。
【請求項１２】
前記レイトレーシングハードウェアは３次元シーンを処理し、１つの光線について、０個の、１つの、又は複数のオブジェクト光線交点を、距離に応じて分類して又は分類せずに計算し、その際、計算されたオブジェクト光線交点の個数は定数として固定される及び／又はオブジェクトの付加的パラメータにより記述されるようにしてよい、請求項１から１１のいずれか１項記載の装置。
【請求項１３】
前記レイトレーシングハードウェアは、画像の計算において、動的及び／又は幾何学的オブジェクト、及び／又は、材質記述、及び／又は、空間記述データ構造の要素及び／又はサブグループ、及び／又は、プログラム、及び／又は、メモリセル、及び／又は、メモリページが何回使用されたかを、付加的な及び／又は既存の機能ユニットによりカウントする、請求項１から１２のいずれか１項記載の装置。
【請求項１４】
前記レイトレーシングハードウェアは、付加的な及び／又は既存の機能ユニットにより、空間記述データ構造を部分ごとに計算すること又は完全な３次元シーンを計算することができ、その際、動的オブジェクト及び／又は動的部分オブジェクト及び／又は幾何学的オブジェクトごとに付加的なパラメータが前記空間記述データ構造の計算法に対して影響を有している、請求項１から１３のいずれか１項記載の装置。
【請求項１５】
前記レイトレーシングハードウェアは、共通のＺバッファ及びフレームバッファを介して、同一のチップ上に又は前記レイトレーシングハードウェアのように別個のチップ上にあるラスタ化ハードウェアに接続されている、請求項１から１４のいずれか１項記載の装置。
【請求項１６】
複数のレイトレーシングユニットが並列に動作し、計算に必要なデータは該レイトレーシングユニットのメモリ上に分散しており、必要なときにそのつど、必要なデータを記憶している前記ユニットからダウンロードされる、請求項１から１５のいずれか１項記載の装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公表番号】特表２００７−５２２５６７（Ｐ２００７−５２２５６７Ａ）
【公表日】平成１９年８月９日（２００７．８．９）
【国際特許分類】
【出願番号】特願２００６−５５２４６０（Ｐ２００６−５５２４６０）
【出願日】平成１７年２月１６日（２００５．２．１６）
【国際出願番号】ＰＣＴ／ＤＥ２００５／０００２６６
【国際公開番号】ＷＯ２００５／０７８６６５
【国際公開日】平成１７年８月２５日（２００５．８．２５）
【出願人】（５０５０７１６２０）
【氏名又は名称原語表記】Ｕｎｉｖｅｒｓｉｔａｅｔ ｄｅｓ Ｓａａｒｌａｎｄｅｓ
【住所又は居所原語表記】Ｄ−６６０４１ Ｓａａｒｂｒｕｅｃｋｅｎ， Ｇｅｒｍａｎｙ
【Ｆターム（参考）】
【公表日】平成１９年８月９日（２００７．８．９）
【国際特許分類】
【出願日】平成１７年２月１６日（２００５．２．１６）
【国際出願番号】ＰＣＴ／ＤＥ２００５／０００２６６
【国際公開番号】ＷＯ２００５／０７８６６５
【国際公開日】平成１７年８月２５日（２００５．８．２５）
【出願人】（５０５０７１６２０）
【氏名又は名称原語表記】Ｕｎｉｖｅｒｓｉｔａｅｔ ｄｅｓ Ｓａａｒｌａｎｄｅｓ
【住所又は居所原語表記】Ｄ−６６０４１ Ｓａａｒｂｒｕｅｃｋｅｎ， Ｇｅｒｍａｎｙ
【Ｆターム（参考）】
[ Back to top ]