(57)【要約】  この発明は、カメラからの風景の合成画像を準備するための方法に関する。上記風景は、データベースに記憶された基本メッシュによって定められる複数のオブジェクトを含み、上記方法は、中央処理装置により、観察された風景に向かって上記カメラから出てくる複数の光線を定めるステップ（ａ）と、上記複数の光線を処理するステップ（ｂ）とを含み、上記処理するステップ（ｂ）は、光線をビームに編成するサブステップ（ｂ４）を含み、上記方法はさらに、上記ビームを伝搬するステップ（ｃ）と、上記伝搬されたビームの各々のために、上記伝搬されたビームが交差するすべてのメッシュ要素のサブセットを決定する第１のステップ（ｄ）と、グラフィックス処理装置を介し、上記伝搬されたビームの各々のために、上記サブセットのメッシュ要素と伝搬されたビームの光線との交差を計算する第２のステップ（Ｃ２）と、伝搬ステップの後に風景の上記画像を生成するステップ（ｄ）とを含む。
2009525526.tif 000002
【特許請求の範囲】
【請求項１】
カメラからの風景のコンピュータ生成画像を準備するための方法であって、前記風景は、データベースに記憶された基本メッシュによって定められる複数のオブジェクトを含み、前記方法は、
（ａ）中央処理装置により、前記観察された風景に向かって前記カメラから生成される複数の光線を定めるステップと、
（ｂ）前記複数の光線を処理するステップとを含み、前記処理するステップは、
・光線をビームに編成するためのサブステップ（ｂ４）を含み、このビームの光線は、メッシュ要素との空間的にコヒーレントな交差点を有し、前記方法はさらに、
（ｃ）前記ビームを伝搬するステップを含み、前記伝搬するステップは、
（ｃ１）各々の伝搬されたビームのために、前記伝搬されたビームが交差するすべてのメッシュ要素のサブセットを決定する第１のステップと、
（ｃ２）グラフィックス処理装置により、各々の前記伝搬されたビームのために、前記サブセットのメッシュ要素と伝搬されたビーム光線との交差を計算する第２のステップとを含み、前記方法はさらに、
前記伝搬するステップの後に風景の前記画像を生成するステップを含む、方法。
【請求項２】
前記サブセットを決定する前記ステップ（ｃ１）は、前記データベースに接続された中央処理装置ＣＰＵによって実現される、請求項１に記載の、コンピュータ生成画像を準備するための方法。
【請求項３】
メッシュ要素のサブセットを決定する前記ステップ（ｃ１）は、前記交差されたメッシュ要素の加速および決定構造に従ってビームを伝搬するサブステップを含み、前記加速構造は、風景の空間の単純な空間的分解であり、
前記サブセットは、加速構造に沿ってビームが交差する前記メッシュ要素の組を含む、請求項１または２に記載の、コンピュータ生成画像を準備するための方法。
【請求項４】
複数の画素によって表わされるコンピュータ生成画像のために、この画素を横断する画素ごとに多くても１つの光線が光線を生成する前記ステップ（ａ）中に生成される、請求項１から３のいずれかに記載の、コンピュータ生成画像を準備するための方法。
【請求項５】
複数の画素によって表わされるコンピュータ生成画像のために、画素ごとに１組の光線が、すべてこの画素を横断するように、光線を生成する前記ステップ（ａ）中に生成される、請求項１から３のいずれかに記載の、コンピュータ生成画像を準備するための方法。
【請求項６】
光線を処理する前記ステップ（ｂ）は、サブステップ（ｂ４）に加えて、および前記サブステップ（ｂ４）に先立って、
−  前記グラフィックス処理装置により、風景の識別子画像を生成するサブステップ（ｂ１）を含み、前記識別子画像は、
・コンピュータ生成画像を表わす前記複数の画素に合致する複数の画素と、
・各々の画素において、コンピュータ生成画像に対応する画素のための、可視の１つまたはいくつかのメッシュ要素の識別データとを含み、前記ステップ（ｂ）はさらに、
−  少なくとも１つの光線が横断する識別子画像の各々の画素のために、識別データが前記画像の画素座標に記録されている前記メッシュ要素で、このような識別データが画素のために存在している場合、画素を横断する前記一次レイのうち少なくとも１つの交差点を決定するサブステップ（ｂ２）と、
−  予め決定された前記交差点が空間的にコヒーレントである場合、画素を編成するサブステップ（ｂ３）とを含み、
ビームを編成する前記サブステップ（ｂ４）は、前記サブステップ（ｂ３）中に編成さ
れた画素に関連する光線を同じビーム内において編成することを含む、請求項４または５に記載の、コンピュータ生成画像を準備するための方法。
【請求項７】
前記伝搬されたビームは、伝送されたビームおよび／または反射されたビームおよび／または影ビームを含む、請求項１に記載の、コンピュータ生成画像を準備するための方法。
【請求項８】
前記ビームを伝搬する前記ステップ（ｃ）は、前記伝送されたビームおよび／または反射されたビームの各々に再帰的に適用される、請求項１から７のいずれかに記載の、コンピュータ生成画像を準備するための方法。
【請求項９】
前記中央装置を介し、ステップ（ｂ）に従って伝搬された光線を、ビームに編成する（ｂ４）よう処理するステップと、ステップ（ｃ１）および（ｃ２）に従ってビームを伝搬するステップとを各々の新たな伝搬時に再帰的に含む、請求項７に記載の、コンピュータ生成画像を準備するための方法。
【請求項１０】
前記計算するステップ（ｃ２）中に計算された前記交差が空間的にコヒーレントでない場合、ステップ（ｃ２）において計算された交差が空間的にコヒーレントである光線を編成することによって、伝搬されたビームを伝搬されたサブビームに分割するステップ（ｃ３）を含む、請求項７または８に記載の、コンピュータ生成画像を準備するための方法。
【請求項１１】
サブビームにおける非コヒーレントな光線を表わす伝送または反射された伝搬されたビームを分割するステップ（ｃ３′）を付加的に含む、請求項７から１０のいずれかに記載の、コンピュータ生成画像を準備するための方法。
【請求項１２】
コンピュータ上で実行可能な複数の命令を含み、請求項１から１１のいずれかに記載のコンピュータ生成画像を実現することのできる、コンピュータソフトウェア。
【請求項１３】
コンピュータ上で実行可能な複数の数値命令を含み、請求項１から１１のいずれかに記載のコンピュータ生成画像を実現することのできる、コンピュータ記憶媒体。
【請求項１４】
請求項１から１１のいずれかに記載の方法を実現するためのシステムであって、
少なくとも１つの記憶メモリにリンクされた少なくとも１つの中央処理装置と、バスによって前記中央処理装置にリンクされた少なくとも１つのグラフィックス処理装置とを含み、
−  前記中央処理装置は、前記観察された風景に向かって前記カメラが発生させる光線を生成し（ａ）、メッシュ要素との交差点が空間的にコヒーレントである前記光線をビームに編成し（ｂ４）、前記ビームの伝搬を決定し（ｃ）、伝搬された各々のビームのために、前記伝搬されたビームと交差するすべてのメッシュ要素のサブセットを決定する（ｃ１）ことを可能にする手段を含み、
−  前記グラフィックス処理装置は、前記伝搬されたビームの各々のために、前記サブセットのメッシュ要素と前記伝搬された光線との交差を計算し（ｃ２）、前記伝搬されたビームのサポートを用いて風景の画像を生成する（ｄ）ことを可能にする手段を含む、システム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、三次元の風景、特に、コンピュータ支援による設計（ＣＡＤ）のアプリケーション、ビデオゲーム、シミュレーションまたは映画撮影後の編集のための、リアルなコンピュータ生成画像の作成に関する。
【背景技術】
【０００２】
図１に示されるような三次元の風景は、当該風景において多数の３Ｄオブジェクトを定めるメッシュで、コンピュータにより生成される。視点からのこのような風景のレンダリングは画像（画素マトリックス）として生成され、オブジェクト照明または性質（反射コート、透過的材料、…）などの多数のパラメータを考慮に入れることを必要とする。このようなレンダリングの実現は複雑になる。
【０００３】
このようなコンピュータ生成画像におけるオブジェクト照明および影を計算するためのレイトレーシングの使用は、１９７０年代後半より公知であった。図２および図３に図示のとおり、レイトレーシングは、画像の各画素のゾーンに向かって風景の視点１（カメラ）から生成される光線Ａをトレースし（カメラの開口と最終画像を作り出す画素の数とに従った計算）、風景に含まれるさまざまなオブジェクト上でのこの光線の伝搬の全てまたは一部を調べて画素の色を決定することにある。実際には、カメラ１から出てくるすべての一次レイは、反射Ｃによって、伝送（図示せず）によって、または、光源に向かう拡散（シャドウレイＢ）によって伝搬される。反射または伝送によって伝搬された各々の光線は、その風景の別のオブジェクトに遭遇すると、再び伝搬される。これらは、光線の複数回の伝搬となる。光線が当たるオブジェクトをなす材料の性質のために、そして、影が存在していることにより、上記光線は、単純な複数の伝送および反射によって見られるオブジェクトの材料と投影された影（光線Ｂ）とを考慮に入れて、各々の画素に対して表示されるべき色を評価することを可能にする。考慮された反射、伝送または光源の数にしたがって、概して、１画素当たり１０本の光線が算出される。したがって、全体画像について算出されるべき光線の数が非常に大きくなることが分かる。
【０００４】
何年もの間、特許ＵＳ５０３１１１７に記載のとおり、このアルゴリズムは中央処理装置（ＣＰＵ：central processing units）上でのみ実現されてきたが、しばしば並行して非常にリアルなレンダリングを生成する。レイトレーシングのアルゴリズムがもつ固有の性質とＣＰＵの多価性とのために、この技術では多くの計算時間が必要となる。
【０００５】
他方では、ｚバッファマトリックス（以下に規定）を用いて、いくつかの画素を同時に処理するのにグラフィックカードまたはグラフィックス処理装置（ＧＰＵ：graphics processing units）が有効である。これらのカードの最近の開発では、特許出願ＵＳ２００５／００４１０２４または科学出版物「ストリームプロセッサ上でのレイトレーシング（Ray tracing on a stream processor）」（ティモシー・ジョン・パーセル（Timothy John Purcell）、スタンフォード大学、学位論文、２００４年３月）に記載されるような直接的なＧＰＵレイトレーシングの応用例がもたらされた。しかしながら、これらの性能は、得られるレンダリングについては制限されたままであり、ＣＰＵ上で実行される同等の処理時間について期待されるものよりも劣ったものとなる。
【０００６】
科学出版物「多角形のオブジェクトのビームトレーシング（Beam tracing polygonal objects）」（ポール・エス・ヘックバート（Paul S. Heckbert）、ＳＩＧＧＲＡＰＨ′８４、１１９〜１２７頁、１９８４年７月）と、ヘックバートによる先の出版物について特に言及している「レイトレーシングとビームトレーシング変形例との合成（Une synthese
des variantes du lancer de rayons et du lancer de faisceaux）」（J-M Hasenfratz, Revue internationale de CFAO、第１３巻３号、１９９８年９月、２３５〜２６４頁）とに記載されるビームを使用することで従来のレイトレーシングに対する改善がなされた。採用されたいわゆる「ペンシル」アプローチは、１回の射程においてより広いゾーンをカバーするように軸方向の光線にその隣接する近軸光線を接合することを含む。しかしながら、実験により、ビームトレーシング技術は費用効果が低いにもかかわらず多くの問題を生じさせると判断されたために、このアプローチは除外された。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、コンピュータ生成画像（設計センタ、ビデオゲーム、撮影後の編集）におけるプレーヤが画像計算時間により一層関連していることは確かである。したがって、現在の計算構成要素に依拠しつつ、このような計算時間を減らすための解決策が大いに必要とされる。ある解決策が、エヌ・カー（N. Carr）、ジェイ・ホール（J. Hall）、ジェイ・ハート（J. Hart）等（イリノイ大学）により、彼らの出版物である「光線エンジン（The ray engine）」（グラフィックス・ハードウェア（Graphics Hardware）、２００２年、１〜１０頁）において紹介されている。ここでは、統合されたＣＰＵ−ＧＰＵのアーキテクチャが用いられる。ＣＰＵは一般的なレイトレーシングアルゴリズムを駆動するのに用いられ、要求をＧＰＵに送信し、当該ＧＰＵが、オブジェクトメッシュにおける三角形と光線との交差計算を一般化するよう動作する。得られた結果は、レイトレーシング専用の最適なＣＰＵに匹敵するものとなる。改善されたＧＰＵの性能により、これらの性能全体が一層明確に高められるはずである。
【０００８】
ＧＰＵが過負荷状態のままであれば、システム性能が制限されてしまうと考えられる。仮想画像生成に対する現在の要求によれば、双方向性を最小限にする必要がある（少なくとも１つの画像が数秒ごとに生成される）。現在の低コストのＧＰＵでは複雑な風景（設計、撮影後の編集）のためにこのような性能を得ることはできない。したがって、このようなアーキテクチャのためにレイトレーシングのアプリケーションを最適化することが根本的に必要とされる。
【課題を解決するための手段】
【０００９】
この発明は、先行技術の限定に対して解決策を示すことを目的としている。この発明が依拠している統合されたＣＰＵ−ＧＰＵアーキテクチャにおいては、効率的な光線を用い、そして、ＣＰＵとＧＰＵとの間の計算負荷を、メモリ（ＣＰＵ）にアクセスするかまたは多数のグラフィカルデータ（ＧＰＵ）を並行に処理するそれら自体の能力に従って分散させることにより、レイトレーシングが最適化される。この発明は、伝搬モデルを光線の総数よりもはるかに少ない数のビームにまで低減させるために、空間近接基準に従って光線をビームとしてグループ化することを可能にする。これは、先験的に「近接」している光線が同じオブジェクトに遭遇し、このため、風景において「ともに」伝搬する可能性があるという原理に依拠している。
【００１０】
この発明の最適化とは、風景全体上ではなく、その一部上でこのような伝搬されたビームの相互作用を解消することである。この目的のために、ＣＰＵは、ビームが交差する風景要素のラフ集合を決定するよう当該ビームを前処理し、この集合をＧＰＵに伝送する。したがって、ＧＰＵによって実行される計算動作の必要数が、風景のうちのすべての要素と１本のビームとの交差、または、風景のうちのすべての要素とすべての光線との交差の処理に比べて、明らかに低減する。
【００１１】
このために、この発明は、まず、オブジェクトのために、カメラからの風景のコンピュータ生成画像を精緻化するための手順を含み、上述の風景は、データベースに記憶された
基本のメッシュによって定められる複数のオブジェクトを含み、当該手順は、
（ａ）中央処理装置により、上記観察された風景に向かって上記カメラから生成される複数の光線を定めるステップと、
（ｂ）上記複数の光線を処理するステップとを含み、当該処理するステップは、
・最終的に上記中央装置により、光線をビームにグループ化するサブステップ（ｂ４）を含み、当該手順はさらに、
（ｃ）当該ビームを伝搬するステップを含み、当該伝搬するステップは、
・（ｃ１）上記伝搬されたビームの各々のために、上記伝搬されたビームが交差するすべてのメッシュ要素のサブセットを決定する第１のステップと、
・（ｃ２）グラフィックス処理装置により、上記伝搬されたビームの各々のために、上記サブセットメッシュ要素と伝搬されたビーム光線との交差を計算する第２のステップとを含み、当該手順はさらに、
（ｄ）上記伝搬するステップの後に上記風景画像を生成するステップを含む。
【００１２】
「カメラ」は、視点および風景のレンダリングを意味する一般的な用語として理解される。これは、観察者の目、ビデオカメラのセンサまたはフォトカメラのセンサであり得る。
【００１３】
同様に、「メッシュ」は、平面要素、たとえば三角形もしくは四辺形からの３Ｄ形状、または、ＮＵＲＢＳ（Nonuniform Rational B-Spline surface：非一様有理Bスプライン面）、ベジェ面および多項面などの面からの３Ｄ形状の表現を含む。
【００１４】
「定められる」とは、データベースに記憶された各々のメッシュ要素の座標を意味する。オブジェクトは三角形で表わすことができ、この場合、風景空間における三角形の頂点の座標がデータベースに記憶される。
【００１５】
光線の定義は、主に、予めカバーされているレイトレーシングの概念に依拠している。光線の定義は、寸法が設定されている画素のマトリックスとして最終的なコンピュータ生成画像の定義に同化される。実際には、光線は、一般に、視点および最終画像の画素に合致する。この対（視点、画素方向）は、光線の例を定める。この事実から、ＣＰＵが風景視覚化パラメータ、すなわち、カメラの位置、視覚化方向、垂直なカメラ、視覚化開口角などを再グループ化すると、生成されるべき画像の寸法によって複数の光線が直接定められる。
【００１６】
レイトレーシングを適用する際に、光線、より具体的にはこの発明のビームは、可視の（影、反射効果などから減衰する場合には部分的に可視である）メッシュ要素を決定し、ここから最終画像における画素の色特徴を推測することを可能にする。
【００１７】
「伝搬された光線またはビーム」という語は、場合によっては、光の軌道を管理する光学原理に由来して、カメラから直接生じる光線またはビーム（一次レイ）、（反射の後であろうとなかろうと）シャドウレイまたはビーム、反射された光線またはビーム（１つまたはいくつかの反射）、伝送された光線またはビーム、メッシュ要素間のエネルギ交換を計算またはサンプリングするのに用いられる光線またはビーム、と理解されるべきである。
【００１８】
上述のとおり、「ＧＰＵ」またはグラフィックス処理装置は、図形基本要素（点、三角形など）からの幾何学的形状のトレーシングを処理するよう接続されたコンピュータシステムによって用いられる特化されたコンピュータ構成要素である。ＧＰＵは、多くのデータに対して同じ計算を実行するのに有効である。これは、この発明においては、メモリアクセスおよび特定のタスク処理に有効であるか、または、データを構造に編成するのに有
効である万能な構成要素である「ＣＰＵ」または中央処理装置とは対照的である。
【００１９】
この発明によって提案される解決策においては、メッシュ要素の設定されたサブセットは、いずれの場合にも、ビームのすべての光線に交差するメッシュ要素を含む（以下、三角形またはメッシュ要素と区別せずに言及される）。このように、このサブセットについてＧＰＵによって実行される計算では、すべてのメッシュ要素についての計算に比べてスキューは発生しない。このような要素はさらに顕著に最適化される。というのも、関連のないメッシュ要素についての多数の要求が回避されるからである。こうして、計算についての１０の加速係数を容易に得ることができる。
【００２０】
最終的なコンピュータ生成画像の生成は、各々の画素の色決定に存する。伝搬されたビームは、画像のうちの一画素における１つの可視のオブジェクトについて、主に影または反射または伝送として含まれる風景の要素を決定することを可能にする。
【００２１】
一実施例においては、上記サブセットを決定する上記ステップ（ｃ１）は、上記データベースに接続された上記中央処理装置ＣＰＵによって実行される。ＣＰＵは、データベースを格納するメモリへのアクセス能力と、中間データが記憶されるランダムアクセスメモリへのアクセス能力とに従って動作する。これにより効率が上がる。実際には、ＣＰＵ／ＧＰＵ並列性と、メモリにおける三角形データへの高速アクセスを用いてサブセットを決定するためのＣＰＵ処理速度と、三角形のサブセットを処理することによるＧＰＵ負荷の低減とを組合せることにより、コンピュータ生成画像の回復が確実に１０倍以上に加速される。
【００２２】
上述のとおり、メッシュ要素サブセットの構成により、ＣＰＵとＧＰＵとの間の計算負荷の最適化がもたらされる。ＣＰＵメモリアクセス能力を利用するために、ビームが、伝搬方向に沿ってビーム区画に構築される。これらの区画は加速構造によってサポートされる。このことは、先行技術、特に「レイトレーシングのための幾何学的データ構造の調査（A survey of geometric data structures for ray tracing）」（アレン・ワイ・チャン（Allen Y. Chang）、２００１年１０月１３日、博士論文、ポリテクニック大学、ニューヨーク州（New York）ブルックリン（Brooklyn））に既に記載されているとおりである。さらに、メッシュ要素サブセットを決定する上記ステップ（ｃ１）は、加速構造に従ってビームを伝搬するサブステップと、上記交差されたメッシュ要素の加速構造に沿った各々の上記区画についての決定とを含む。さらに、上記メッシュ要素のサブセットは、加速構造に沿ってビームが交差する上記メッシュ要素のセットによって構成される。
【００２３】
加速構造は、たとえば、規則的な階層型のボクセル（体積のあるピクセル）の基準、または、空間を分離するプランの階層基準（ｋｄツリー）を用いて風景空間を単純に分解したものである。ビーム区画は、ビーム伝搬方向に沿ってボクセル境界によって決定される。各々のビーム区画のために、ビームを切断するメッシュ三角形が決定される。
【００２４】
他方では、光線のセットをトレースするために実行されるべき計算の数を減らすための解決策は、光線の数を最小限にすることで最適化される。このようにして、画素のマトリックスによって表わされるコンピュータ生成画像のために、多くても１本の光線が、光線を生成する上記ステップ（ａ）中にこの画素を横断する画素ごとに生成される（すなわち、画素数を上回る光線数の割合として計算される）。
【００２５】
特にアンチエイリアシングに関して、主により優れたレンダリングを目的とした変形例においては、画素のマトリックスによって表わされるコンピュータ生成画像のために、１画素当たり１組の光線を、上記光線生成ステップ（ａ）中に、すべてが上記画素を横断する状態で生成することが可能となる。この変形例は計算時間を犠牲にして実現される。
【００２６】
１画素当たりに光線がいくつか存在することにより、特に、風景上の画素サンプリングによって導入されるエイリアシングに対抗することが可能となる。また、画素を横断する光線を画素形状に多少とも合致する円錐形のビームと置き換えることも検討され得る。これは、特許出願ＰＣＴ  Ｗ０９３／０１５６１または上述の科学出版物Hasenfratz９８（９頁、図３）において既に示唆されているとおりである。
【００２７】
この発明の効率性についての重要な部分は、最適化された光線ビームを用いることにある。したがって、このようなビームを生成するための効率的な方法を提供することが重要であると考えられる。この目的のために、光線を処理する上記ステップ（ｂ）は、サブステップ（ｂ４）の前に、
−  上記グラフィックス処理装置により、風景の識別子画像を生成するサブステップ（ｂ１）を含み、この場合、各々の画素内において、この画素において可視の１つまたはいくつかのメッシュ要素についての識別データが記録され、上記ステップ（ｂ）はさらに、
−  識別子画像の各画素のために、上記メッシュ要素を有する画素を横断する上記一次レイのうちの少なくとも１つの交差点を決定するサブステップ（ｂ２）を含み、その識別データは、上記画素についてこのような識別データが存在する場合、上記画像の画素座標において記録され、上記ステップ（ｂ）はさらに、
−  最終的に、識別子画像の各画素のために、上記メッシュ要素を有する画素を横断する上記一次レイのうちの少なくとも１つの再放出方向を決定するサブステップ（ｂ２′）を含み、その識別データは、上記画素についてこのような識別データが存在する場合、上記画素内にあり、上記ステップ（ｂ）はさらに、
−  画素を編成するサブステップ（ｂ３）を含み、この場合、予め決定された上記交差点が空間的にコヒーレントである。
【００２８】
加えて、ビームを編成する上記サブステップ（ｂ４）は、上記サブステップ（ｂ３）中に編成された画素に関連付けられる光線を同じビーム内で編成することを含む。
【００２９】
識別子画像（主にこれらがカメラから直接出てくる光線であれば）は、概して、我々が生成することを意図する最終的なコンピュータ生成画像と同じ寸法を有する。しかしながら、我々は、エイリアシングなどの処理上の問題についてより多くの情報を得るために、最終画像（および、これにより識別子画像のサイズ）を調べることができるよう光線の数を増やすことを検討している。
【００３０】
たとえば、画像の画素マトリックスを構成するすべての画素に与えられる色が有するＲＧＢ（赤−緑−青）コードの値は、この画素において可視のメッシュ要素の識別データに等しくなる。この画像は、すべての画素において可視であるメッシュ要素の各々を合成的に有し、こうして、第１の障害物のメッシュ要素の識別データを迅速に収集してレイトレーシングまたはビームトレーシングの分析を開始することを可能にする。グラフィックスカードによる一次画像のこのようなトレーシングは、光のことを考慮しなければ極めて効率的になる。ＧＰＵグラフィックカードは、ベースに記憶されたすべてのメッシュ三角形の座標をＣＰＵから受取り、特に、その用途のために利用可能なＺマトリックスを用いる従来の方法によって画像をトレースし始める（ｚバッファ：各々の画素のために表示されるべき三角形識別子を記憶するのに用いられ、カメラに最も近接している三角形だけを維持するよう更新されるメモリ）。透過的な要素面のためのこのトレーシングパスから利点を得るために、たとえば、メッシュ要素についての識別データを、当該メッシュ要素が交差される順に連続的に画素色成分に記憶することにより、光線が交差するメッシュ要素、すなわち、直接可視である要素や、場合によっては透過的であることにより可視の要素、を各々の画素のために記憶することも容認され得る。
【００３１】
各々の画素については、衝突されるメッシュ要素が、画像におけるその識別データと、これによりデータベースに記憶されたその定義パラメータとにより既知であることで、画素（線）を横断する光線とメッシュ要素（面）との交差点を容易に計算する（ｂ２）ことが可能となる。これは、線−面の交差についての簡単な解である。
【００３２】
代替例としては、グラフィックスカードＧＰＵに光線とメッシュ要素との交差の計算を直接的に実行させ、かつ、識別子画像の画素ＲＧＢ色成分にメッシュ要素との光線の交差座標を直接含ませることであり得る。この場合、ステップｂ２がグラフィックスカードによって実行される。
【００３３】
別の代替例としては、グラフィックスカードＧＰＵに、カメラから、最も近接するメッシュ要素の交差点までの光線長さの計算を実行させ、かつ、識別子画像画素の色成分にこの値（ｚバッファの深さの画像）を含ませることであり得る。この場合、ステップｂ２は、識別子画像において読出された距離における光線上の点を計算することによりＣＰＵによって実行される。
【００３４】
「空間的にコヒーレントな光線」という語は、実質的に平行な光線に関連しており、カメラに最も近接しているメッシュ三角形とのその交差点は空間的に近接している。空間的にコヒーレントな光線を編成することにより、共通の処理として、風景の空間において同じピッチ角（ほぼ平行な光線）で同じオブジェクトに多少とも接する（近接する交差点）光線をグループ化することが可能となる。「実質的に平行」とは、カメラから、実質的に同様の方向に生じる光線を意味する。画素からなる数値画像の場合、これらの光線は、画像のうち定められたゾーンに向かってカメラから生成されるものとして見ることができる（たとえば、３２×３２の画素平方）。風景メッシュ要素との交差点を有する定められたゾーンのうち、距離がしきい値（たとえば、ボクセルのサイズ）未満である光線は、たとえば、空間的にコヒーレントであると考えられてもよい。加えて、このような光線の中でも、角度がしきい値（たとえば１０度）未満である方向を有するものは、実質的に平行であると考えられてもよい。このようにして、ビームは、定形（正方形、三角形）または不定形（対象となる光線に従った任意の形状）をもとにして円錐形を作り出す。
【００３５】
画像全体にわたって均一なサイズの光線を最適化するために、全体画像を、光線が内部で編成されているたとえば３２×３２画素の一次ゾーンに再分割することも提示される。
【００３６】
また、これらの編成を最適化するために、伝送または反射（ステップｂ２′の再放出方向）情報を考慮に入れて、空間的にコヒーレントなビームをより効率的なビームに再分割することもできる。
【００３７】
コンピュータ生成画像の画素色についての決定の原因となる光線伝搬のさまざまな法則に従うと、上述の伝搬されたビームは、伝送されたおよび／もしくは反射されたおよび／もしくは影のビーム、ならびに／または、拡散相互作用のビーム、ならびに／または、光伝搬に関連するエネルギ現象であるサンプリングビームを含む。
【００３８】
所望のレンダリングの精度のレベルと、これによりその現実感とに従って、風景のさまざまなオブジェクトに対する光線およびビームの複数の反射および／または伝送の寄与について分析することも興味深いだろう。実際には、高反射性の表面が存在する場合、ビームは、当該ビームが無視されるのに十分に減衰されるまで何回も反射される。このようにして、上記ビームを伝搬するステップ（ｃ）を、伝送されたおよび／または反射されたおよび／または影のおよび／または相互作用のおよび／またはサンプリングの上記ビームの各々に再帰的に適用することもできる。最終的に、ビームを生成する上記ステップ（ｂ）はまた、これらのビームの各々またはそれらすべてのために再現することができる。
【００３９】
このアプローチに対し最適化を行なうこともできる。特に、ビーム減衰率に達すると直ちに、伝搬が停止される。上流のビームにより、考慮されている画素ゾーンの最終的なレンダリングについての色情報が十分に提供されると考えられる。他のビームは、同じ減衰しきい値に達するまで伝搬され得る。
【００４０】
他方では、レンダリングに勝る計算速度が好ましく、これにより、伝送されたおよび／または反射された光線の伝搬を１回、２回または３回の反復にまで制限することが有利になるだろう。
【００４１】
具体的には、当該手順は、各々の新しい伝搬時に、ステップ（ｂ）に従って伝搬された光線を、上記中心装置を通じてビームに編成する（ｂ４）よう処理するステップと、ステップ（ｃ１）および（ｃ２）に従ってビームを伝搬するステップとを再帰的に含み得る。これにより、適切なビームを用いることによって各々の計算ステップにおいて最適化を行うことが可能となる。
【００４２】
ビームは、同じオブジェクトによって数回伝搬された場合、ｎ回目の伝搬中にいくつかの障害物（オブジェクトメッシュ要素）に遭遇する可能性がある。その後の処理の効率を向上させるために、さまざまな障害物に遭遇するサブビームを別々に考慮することが容認され得る。このようにして、当該手順は、上記計算ステップ（ｃ２）中に計算された上記交差が空間的にコヒーレントでない場合、ステップ（ｃ２）において計算された交差が空間的にコヒーレントである光線を編成することによって、伝搬されたビームを伝搬されたサブビームに分割するステップ（ｃ３）を含む。サブビームへのこのビーム分割は、分割基準に関してはビームにおける光線の編成（ステップｂ３）に極めて類似している。
【００４３】
また、複数の伝搬後、たとえば伝送または反射の後、伝搬の問題に遭遇する可能性がある。たとえば、ビームが壁の隅部に当たると、光線の一方の部分が壁側面によってある方向に反射され、光線の他方の部分が他方の壁側面によって完全に異なる方向に反射されてしまう。したがって、当該手順はまた、サブビームにおける非コヒーレントな光線を呈する伝送または反射されている伝搬されたビームを分割するステップ（ｃ３′）を含む。
【００４４】
ここで「非コヒーレントな光線」は、その方向ベクトルが実質的に平行ではない光線を意味する。すなわち、それらの角度がたとえばしきい値を上回っているか、またはそれらの開始点が互いから空間的に離れている。これはまた、起伏のあるテクスチャの場合にも当てはまり、その上ではビームの反射が非常に乱されてしまい、ビームをサブビームに再分割することがしばしば必要となり得る。
【００４５】
この発明はまた、上述のとおり、オブジェクトのために、コンピュータ生成画像を精緻化するための手順を実現することを可能にする複数の命令を含むコンピュータソフトウェアを有する。
【００４６】
この発明はまた、オブジェクトのために、上記コンピュータソフトウェアを含む記憶媒体を有する。この発明はまた、オブジェクトのために、当該手順を実現するシステムを有する。当該システムは、少なくとも１つの記憶メモリにリンクされた少なくとも１つの中央処理装置と、バスを介して上記中央処理装置に接続された少なくとも１つのグラフィックス処理装置とを有する。
【００４７】
−  上記中央処理装置は、上記観察された風景に向けた上記カメラによってもたらされる光線を生成して（ａ）、上記光線をビームに編成し（ｂ４）、上記ビームの伝搬を決定し（ｃ）、各々の伝搬されたビームのために、上記伝搬されたビームが交差するすべての
メッシュ要素のサブセットを決定する（ｃ１）ための手段を含む。
【００４８】
−  上記グラフィックス処理装置は、上記伝搬されたビームの各々のために、上記サブセットのメッシュ要素と上記伝搬された光線との交差を計算し（ｃ２）、上記伝搬されたビームを用いて風景の画像を生成する（ｄ）ための手段を含む。
【発明を実施するための最良の形態】
【００４９】
この発明はまた、添付の図面によりさらに明らかにされる。
プレート１／１０、３／１０および１０／１０に対応する色プレートはまた、本願の出願時に提供されたものであり、この発明をより理解するために書類に含まれている。
【００５０】
図４を参照すると、この発明を実現するためのシステムは、
・汎用の処理モジュール１０を含み、当該処理モジュール１０は、ここに含まれる情報にアクセスし連続的に変更するために、いわゆるランダムアクセスメモリ（ＲＡＭ）１２で汎用タスクを解決することを可能にする。このブロックは、１つまたはいくつかのプロセッサ１４（ＣＰＵ）を含み、一体化されたメモリに基づいていてもまたは基づいていなくてもよい。当該システムはさらに、
・特化されたタスクを並行に実行することを可能にする特化された処理２０またはＧＰＵ（グラフィックスカード）の別のモジュールを含む。転送バス（２２）を介してこのブロックによって受信されたデータは、処理装置２４を介して、モジュール２０自体上のメモリ２６に書込まれた結果を生成する。当該システムはさらに、
・汎用のブロックからコプロセッサにコマンドを伝送し、これらによって計算された結果を読出すための、２つの上述のエンティティ間における双方向転送バス２２を含む。
【００５１】
典型的には、最近の平均的なマシンは、１つまたはいくつかのＣＰＵ、一体化されたメモリベースのシステム（各々のプロセッサのＬ１およびＬ２のメモリキャッシュを除いて）を含み、１つまたはいくつかのＧＰＵと通信するためのＡＧＰまたはＰＣＩ−Ｅ転送バスを含む。ＧＰＵは、頂点またはピクセルシェーダーを介してこれらに送信されるトレーシング命令を並行して計算し、ビデオメモリにおいて生成される結果を書込む。このビデオメモリは、必要に応じてＣＰＵメモリにコピーされてもよく、または、表示のために直接用いられてもよい。
【００５２】
以後、ＣＰＵ１０は、汎用の計算モジュールおよびＧＰＵ２０の特化されたモジュールと称される。
【００５３】
ＧＰＵは、処理されるべき画像の画素処理および計算のために一般にプログラミングされ得る要素と、特に、
・頂点シェーダーとを含み、当該頂点シェーダーは、オブジェクトの多角形頂点（すなわち、頂点属性）を変更し、こうしてその写像を画像に転送するグラフィック機能を実現することを可能にし、当該ＧＰＵはさらに、
・ピクセルシェーダーを含み、当該ピクセルシェーダーは、オブジェクトの多角形を表示することに起因する照明および表面効果（たとえばテクスチャ）を変更するグラフィック機能を実現することを可能にする。ピクセルシェーダーは、各々の画素の成分（色、透明性、ｚバッファの深さ）に対し、他の画素とは無関係に作用し、現実により近いレンダリングを得るためにオブジェクトの外観を変更することを可能にし、キャッシュまたはｚバッファは、画素色を記憶するのに用いられるものに対する付加的なメモリであり、正規化されたＺ座標を各々の画素に関連付けることを可能にする。これは、すなわち、可視のメッシュオブジェクトまたは三角形（すなわち、視点に最も近いもの）を各々の画素に記憶するためにこの発明において用いられる。
【００５４】
ＣＰＵは、対象としている空間における３つの頂点座標と各々の三角形の識別データをリンクさせるデータベースの形式で、風景オブジェクトのメッシュ三角形を定めるデータをＲＡＭメモリ１２に配置する。最終的に、これらのデータは、データベースから読出専用メモリに戻すことができる。
【００５５】
ＣＰＵはまた、以下に記載される手順のステップを実行するための命令として応用プログラムを実行する。これらの命令は、特定のＧＰＵ計算に起因する画像の生成時に存在する、ＧＰＵへの「レンダリングパス」または要求において編成される。「レンダリングパス」の各サイクルは、
・ＣＰＵによって実行される計算、
・概してすべての画素上における、すべてのビームのための並列計算についての要求をＧＰＵに送信すること、
・トレーシング命令の要求についての、ＧＰＵによる解、
・最終的には、計算結果についての、ＣＰＵによる読出、
・最終的には、さまざまなレンダリングパス中に計算されたすべての画素色データを統合した最終画像の構成についての１つまたはいくつかの命令、および
・ＧＰＵによる最終的なコンピュータ生成画像の表示、を含む。
【００５６】
いくつかのレンダリングパスは、たとえば、ＧＰＵが以前のパスの画像を計算している間にＣＰＵが新しいパスを計算することから始めて、処理を最適化するためにフレーム化されてもよい。ＣＰＵおよびＧＰＵがこうして並行にされる。
【００５７】
図５はこの発明の間に計算されるレイツリーを示す。このツリーは、予め定められており、たとえば、カメラによって直接生成される一次レイ、第１の障害物におけるシャドウレイ（光源の数に応じた数）、伝送された光線、反射された光線、および、光線が接触する各々の障害物のレベルに対応するシャドウレイを含む。
【００５８】
従来のレイトレーシングプログラムでは、概して、放出された一次レイによってレイツリーが計算される。ツリー全体は一定の深さを有しており、その下位区分だけがベースにおける光線の軌道に従って評価される。この発明に関しては、これによりレンダリングパスが生成され、風景全体に対してレベルごとに全体的にレイツリーの解を勧めることが可能となる。
【００５９】
この発明は、深さごとにこのレイツリーの解に取組んでいる。このため、これは、ツリー深さの各々のために光線ビームを再度計算するよう設計することもできる。
【００６０】
図６を参照すると、この発明を含むさまざまなステップがさらに詳細に説明される。
一次レイの計算
【００６１】
【表１】
2009525526.tif 000003
【００６２】
ＣＰＵ１０は、ＲＡＭメモリ１２においてメッシュ三角形のデータにアクセスする（各々の三角形については、固有の識別番号および３つの頂点の座標）。次いで、これが、三角形のリストを含むトレーシング要求をバス２２を介してＧＰＵ２０に伝送する。このトレーシング命令は、Direct３ＤまたはOpenＧＬ（商品名）などの通常のグラフィックＡＰＩ（application program interfaces：アプリケーション・プログラム・インターフェイス）を用いて送信される。これらは、ボードによるジオメトリプリミティブについてのトレーシング命令であり、これは、トレーシング命令を三角形だけに制限するものではない。加えて、ほとんどの場合、ボードにまでトレースされるべきオブジェクトは、事前にボードにロードされているものであるが、直接的に指示される。
【００６３】
このトレーシング解は、（たとえば、視点から最も近く、このため、各々の画素について表示されるべき三角形を決定するために）ｚバッファメモリを用いることに依拠しているハードウェアレンダリングによって実現される（ハードウェアレンダリング：プログラムによってではなく並行化された材料構成要素によって、典型的にはグラフィックスカードにおいて実行される計算）。この解決策においては、ＧＰＵは、たとえば、画素（ｉ，ｊ）が三角形ｘを表示しなければならず、この画素に割当てられた色値がｘである場合、画像の各画素のために表示されるべき各々の三角形についての識別番号を書込む。これらの画素の色は、一般に、Ｒ８Ｇ８Ｂ８Ａ８フォーマット（赤８ビット、緑８ビット、青８ビット、アルファ８ビット）に従って符号化されて、多数の三角形の指標付けを可能にする。図７に図示される得られた画像は、こうして、画素の各々に色を割当てる。この色は、風景のオブジェクトの実際の色とは無関係であるが、この画素において表示されるべき三角形の識別番号を表わしている。
【００６４】
概してスクリーンと同じ解像度であるこの一次識別子３０の画像は、ＧＰＵビデオメモリに記憶され、次いでＣＰＵに転送される。当該ＣＰＵは、各々の画素のために、各々の
一次レイが最初に遭遇する三角形を有する。
【００６５】
再び図５を参照すると、他の同様の識別子画像が、ＧＰＵに伝送されたトレーシングシーケンス結果から生成される。レイツリーにおける異なる深さにおいて生成された２種類の識別子画像が識別される。
【００６６】
・一次レイの伝搬の解を求めることによって生成される識別子画像３０。
・二次レイとジオメトリとの間の交差計算の解を求めることによって生成される識別子画像４０。
【００６７】
これらの識別子画像を用いてビームを設定し、レイツリーにおいて与えられる深さにおいて風景全体についてのレイトレーシングの状態を構成する。ビームトレーシングの計算の解を求めることにより、風景についてのレイツリーにおける次の識別子画像が生成される。
【００６８】
なお、シャドウレイは、光線の樹枝状部分における葉である限りにおいては付加的な画像を生成しない。
【００６９】
交差点の計算１１０
三角形の識別子が既知であれば、一次レイの式（視点１＋光線方向付けベクトル）について、光線−三角形の交差が容易に計算される（線−面の交差に制限される）。こうして、一次レイと風景のジオメトリとの交差点が利用可能となる。
【００７０】
代替例が検討されてもよい。ＣＰＵは、トレースされるべきオブジェクトの三角形のリストをＧＰＵに伝送する。ＧＰＵトレーシングの解を求めることにより、直接的に、この画素においてトレースされた三角形と各画素とが合致する光線交差点が計算される。次いで、各々の画素の色成分が、より多数のビット、たとえばＲ３２Ｇ３２Ｂ３２、Ｒ２４Ｇ２４Ｂ２４またはＲ１６Ｇ１６Ｂ１６にわたって、色成分により交差点の浮動座標で符号化される。次いで、ＣＰＵが結果を読出す。各々の画素のために、光線が接触する交差点が利用可能となる。この代替例では、数値の精度が失われるが、これは、ＣＰＵ上のベースストレージのフォーマットが概して３２または６４ビットで符号化された浮動値を用いるのであれば、色成分が数ビットで符号化されるので、一層重要となる。加えて、この代替例は、バス２２からのより高い性能を明らかに必要とする点で最適化されない。
【００７１】
ビーム構成１２０
ビームは、或る数の光線をグループ化するのに用いられる。この最初の編成は一次識別子３０の予め計算された画像から計算される。
【００７２】
概して、図８を参照すると、ビームは、含まれている光線の始点を含む空間のゾーン５０と、既知であれば、光線の実現可能な到達点を含む空間のゾーン５２とによって、または、光線の実現可能な終点を含むゾーンによって定められる単純な切頭角錐である。ビームによってカバーされる全体的な空間ゾーンは以下の計画によって範囲が定められる。
【００７３】
・ナビゲーション軸（ａａ）に従った最小／最大値、たとえば、カメラから、空間において遭遇した第１のオブジェクトまでの距離（最小）、および、カメラから、最も離れたメッシュ要素までの距離（最大）、
・垂直軸（ｐａ）に対して平行な左右の面５４、ならびに
・水平軸（ｑａ）に対して平行な上方および下方の面５６、である。
【００７４】
ビームがいくつかのナビゲーション軸をカバーする場合、いくつかのビームが、図９に
示されるように定められる。
【００７５】
識別子画像３０は、画素をビームに編成するための基準としての役割を果たす長方形ゾーン（ｎ×ｍの画素）に任意に切断される。この切断サイズを選択することにより、最終的に生成されるビームの数を調節することが可能となる。ビームのナビゲーション性能に対し、開始ビーム体積が大きすぎるのであれば生成されない方がよい。たとえば、３２×３２の画素ゾーンが用いられる。図１０ａを参照すると、この３２×３２のゾーンは、ビーム開始ゾーンを定める。この画像上の３２×３２の画素グループでは、ＣＰＵは、ビーム開始体積を定めるためにそのジオメトリとの交差が空間的に隣接している光線に合致するすべての点を再度グループ化する。
【００７６】
たとえば、我々は、対象となるゾーンの第１の点を選択し、これと、予め定められた距離（たとえば、加速構造要素すなわちボクセルのサイズに実質的に等しい距離）の範囲内にあるすべての点とを編成する。当該手順は、このように空間的に編成されていないすべての点について、これらの隣接するもの同士が編成基準に適合することなく、すべてがグループ化されるかまたは分離されるまで、繰返される。
【００７７】
図１０ｂは、このｎ×ｍの画素基本ゾーン上での３つのビームＡ、ＢおよびＣの生成を表わす。適用された基準に従うと、はるかに多くの数のビームを生成することができる。図１０ｂの例においては、ビームＣを２つのビームに再分割して、ばねワイヤ面の主要な２つの向きをなし得る。これを行なうために、ＣＰＵが、これらの基準に従って光線をグループ化するように、交差点におけるのと同時に、再放出方向（伝送、反射など）を決定することが容認され得る。
【００７８】
ビーム伝搬
ビーム伝搬の計算１３０
したがって、ＣＰＵが各々のビーム伝搬を決定することが適切である。２つのビーム伝搬挙動は、それらの性質に従って識別される。
【００７９】
・影の計算の解を求める際に介入するビームと、
・他の光線に対応するビーム（反射、伝送、…）とである。
【００８０】
図１１を参照すると、影を計算するのに用いられるビームについては、当該ビームの伝搬は、単に、ビームの光線がすべて到達するはずである光源の体積自体に向かうそのビームの集束によって定められる。
【００８１】
他の光線（反射、透明性、全体照明）のために用いられるビームの場合、ビーム終端ゾーンは、その構成要素となる光線の各々の伝搬方向からのみ定められ得る。大抵の場合、ＣＰＵは、識別子画像３０の可視のメッシュ要素を定める面に対する法線を計算するようＧＰＵに要求を送信する。これに対し、これらの面法線をビーム光線と遭遇させるＣＰＵは、各々の伝搬された光線（異なる伝搬指数媒体における単純な反射または伝送）を決定し、こうして、伝搬された光線を含むビームトレーシングを計算し得る。たとえば、反射された光線２は、入射する一次ビームＡの最も極端に反射された光線によって定められる。
【００８２】
代替例は、原因となる表面に対する法線ではなく光線再放出方向を計算するための要求をＧＰＵに送信することを含む。これに対し、ＣＰＵは、所望される伝搬の種類についての光線伝搬方向を有する。
【００８３】
風景を含む体積が（典型的には、先に定められた最大値を用いて）定められると想定し
て、このような体積とビーム２の境界光線との交差により、ビーム内に含まれる光線についての起こり得る平面衝突区域が定められる。このような区域は、加速構造を位置決めする際に終端区域５２としての役割を果たす。
【００８４】
特定の特性を有するオブジェクトの表面またはテクスチャ、たとえば、起伏のあるテクスチャ（図１２）の場合、反射光線の分布は、ビーム開始区域を作り出す画素上で妨害される。実際には、妨害されるのは表面法線である。方向の分布が（法線を通じて、または直接的に）ＧＰＵの計算後にＣＰＵ上で読出されると、反射されたビームまたは伝送されたビームの角錐のエッジを定めるよう「極値的な」方向を選択することができる。これは対象とされているすべての方向の包絡線である。最終的に、極端な光線が分岐しすぎている場合、ビームをコヒーレントな光線ビームに再分割することを考慮に入れてもよい。
【００８５】
シャドウレイの計算１５０
これにより、我々は、カメラを通じて見られるものが照らされているかどうか判断することに関心をもつこととなる。これを行なうためには、シャドウレイを計算する（１５０）必要がある。これにより、一次ビームによって交差される三角形の画素色の計算に光源が寄与するかどうかを判断することが可能となる。このステップ１５０は、図１４を参照してさらに詳細に説明される。
【００８６】
交差された三角形の決定１５００
或る数の空間的に近接する光線を編成する各々のビームについては、ビームが交差する三角形は加速構造を用いて計算される。これは、ＣＰＵについては、加速構造を図１１のビーム１に対し適用し、次いで、交差された三角形のビーム区画の各々について増分計算を行なうことを含む。
【００８７】
加速構造に関するさらなる詳細について、加速構造の例が、エム・チャン（M. Chang）による上述の科学出版物において提示されている。
【００８８】
図１３を参照すると、風景空間は、好ましくは標準的な階層に従ってボクセル（体積のあるピクセル）６０に分割される。
【００８９】
ナビゲーション軸（ａａ，ｐａ）および（ａａ，ｑａ）を含む２つの面については、基礎をなすビーム区画はボクセル境界においてクレセント（ａａ）の後に計算される。これは、図１３における４つの点Ｐ１〜Ｐ４によって具体化される。両方の面上の区画により、ｖａとｖａ＋１との間におけるビームが横断するボクセル区域の範囲が定められる（基礎をなすビームスライド［ｖａ，ｖａ＋１］）。さらに、ＣＰＵは、風景要素とのビームの交差を（区画ごとにビーム伝搬方向に沿って）増分的に計算するために加速構造を用いている。この構造は、すべての伝搬されたビーム（影、反射など）に適用される。
【００９０】
仮想画像の精密化サイクル全体を通じて、このような加速構造は、風景の変更（すなわち、移動するオブジェクト）を考慮に入れて更新される。このような変更は、加速構造の再規定および／または或るボクセルの内容の再設定を招く可能性があり、これにより、含まれるメッシュ要素が変化することとなる。
【００９１】
こうして、加速構造によるビームの処理から回復して、各々のビームが遭遇する三角形の識別番号が記憶され、ビームを定める役割を果たす画像区域に関連付けられる。影を写す各々の三角形は、一次レイが交差する三角形上で始まる光線から生成されるビームによって発見された。影を写す各々の三角形は、三角形を受ける影の識別番号にリンクされており、画素についてのみ三角形の投影を有効にトレースするようにし、これにより、影を写す三角形が正確なレセプタ上に影を投影する。これにより、投影区域を、影を受ける必
要のある画素に制限することが可能となる。
【００９２】
この非常に効率的な方法は、最も近接する交差を決定することを目的とした先行技術に反するものであり、その内部において光線が発見されるセルは、光線を最初に横断する三角形を確実に発見するために全体が走査されている。この発明においては、最も近接する交差だけではなく、他のすべてのもの、すなわち、ビームの軌道に「隠されている」三角形も利用可能となる。これらの三角形は、すなわち、影投影を計算する役割を果たすこととなる。
【００９３】
【表２】
2009525526.tif 000004
【００９４】
次いで、ＣＰＵは、一次レイの影画像をトレースするための要求をＧＰＵに送信するが、この目的のために、三角形と、加速構造における各々の影伝搬ビームのための交差された三角形の識別番号と、交差された三角形の頂点とを含むリストを送信する。
【００９５】
影画素の計算１５２０
図１５を参照すると、ＧＰＵは、一次レイによって交差され最終的なコンピュータ生成画像上で認識可能である三角形上における影を写す三角形（すなわち、影ビームによって交差され、加速構造によって決定されるもの）の投影を実現する。この目的のために、以下のステップが実行される。
【００９６】
・概して、影を受けるスクリーンサイズ画像が白色である（影なし）。
・影を写す三角形６２がその元の空間においてトレースされ、ＧＰＵボードが点の位置を、ビームを受ける影の面上に頂点シェーダーで投影することによって変換する。この影
を受けるビームの面は、同一平面上にある一組の一次レイ交差点である、すなわち、影が投影され得る面６４を構成するものであると理解される。したがって、計算手順は、すべてのビーム面、すなわち一次ビーム交差点を形成するすべての面、に対して繰返されることとなる。
【００９７】
・問題となっている画素において三角形投影を受ける三角形６２の識別番号が、三角形が影を投影していることを判別するためのビーム面６４の識別番号（一次識別子画像に含まれる画素の識別番号）と同じである場合に限り、トレースされた画素の色は黒色となる（図１５における事例ａ）。そうでない場合、画素色は元のままである（図１５における事例ｂ）。
【００９８】
識別番号についての同等性テストにより、影の「クリッピング」が可能となる。これにより、各々の画素のために、一方では、ビームを算出するのに用いられた識別子画像と、他方では、これらのビームの伝搬により編成された三角形とが提供される。識別番号についての同等性テストにより、実際に影の中にある画素だけに有効に色を付けること、すなわち、影を付けるべき実際の区域に「満ちあふれた」投影、が可能となる。というのも、これは、非常に大きな受面について計算されるからである。
【００９９】
このように、光線と三角形との交差を明確に計算することは必ずしも必要ではなかった。ビームは、グラフィックスカードによって実行される一連の三角形投影における光線ごとの影計算の変換を可能にした。さらに、三角形のトレーシングシーケンスへの影計算の変換は、当然、現代のＧＰＵアーキテクチャに融合することとなる。したがって、トレーシング性能が優れたものとなり、従来のレイトレーシング技術に比べて、１００倍のオーダでの加速係数に到達することを可能にする。
【０１００】
画像記憶１５３０
次に、このような光源についての各画素に適用されるべき影を含む画像がＧＰＵによって記憶される。
【０１０１】
ステップ１５０は、風景に存在する光源の数だけ繰返される。
図１６に示されるテクスチャ加工されたオブジェクト影の場合、より一般的な解を用いて影の程度を明らかにすることができる。以下のステップが実現される。
【０１０２】
・影を受けるスクリーンサイズの画像が白に着色される（影なし）。
・ビーム面の画素をカバーする区域７０が影を写す各々の三角形６２のためにトレースされる。
【０１０３】
・頂点シェーダーが、ビーム面上における入射する光線７４の交差点７２を計算する。
・ピクセルシェーダーが三角形６２とシャドウレイ７８との交差７６を計算する。交差された三角形６２と加速構造によって計算された影を写す三角形との間の識別番号同等性テストにより、従来の方法と同様に、影を有効に受ける画素についての交差計算だけを有効にすることが可能となる。
【０１０４】
・最終的に、影値は、影を写す三角形６２の伝達特性に従って陰影が付けられる。
一次画像のための照明計算１５４０
上述のステップにより、画像の各々の画素において、影が適用されるべきか否かを決定することが可能となる。実際には、影を適用することは、画素を照明しないことに相当する。先に計算された影画像は、影を受けない画素だけを照明するようにマスクとしてこのパスにおいて用いられる。
【０１０５】
【表３】
2009525526.tif 000005
【０１０６】
コンピュータ生成画像のトレーシング中、ＧＰＵは、ステップ１５３０中に記憶された影を考慮に入れる。これにより、トレースの結果でビデオレンダリングメモリが初期設定され、ＩＭＡＧＥ１となる。
【０１０７】
さらに、これにより、影を考慮に入れ、シェーダーを用いて画素の各々の色が計算される。
【０１０８】
この段階では、風景は、存在している各々の照明に対する影でトレースされる（画素色）。画像は、「直接的な」影および色については、すなわち、たとえば反射または伝送成分を考慮に入れずに、既に完成している。以下のステップで結果を完成させる。たとえば、反射または透明性の追加、全体照明などである。
【０１０９】
二次レイ１６０、１７０
反射された光線および伝送された光線は、それらの伝搬特性（伝送に対する反射）が異なっているだけなので、同様の方法で処理することができる。
【０１１０】
したがって、我々は、図１７を参照して、図１８に図示のとおり、反射された光線（図１１、ビーム２）に焦点を当てる。後者は、一次レイＡの反射によって伝搬された光線Ｃを示している。すなわち、上記光線Ｃは、伝搬による２つのシャドウレイＢ３およびＢ４を有する。
【０１１１】
反射された光線によってどのオブジェクトが発見されるかを決定するために、それらの伝搬方向を予め計算する（１６００）ことが必要である。
【０１１２】
【表４】
2009525526.tif 000006
【０１１３】
ＣＰＵは、各々の画素において可視の三角形を伝送することにより、反射方向を計算する要求をＧＰＵに送信する。画像の各画素については、ＧＰＵは、接触しているオブジェクトの表面特性を考慮に入れて、入射する光線の反射方向を計算する。
【０１１４】
これらのデータが画像として記憶される。各々の画素については、画素の色成分において記憶される三次元方向と、さらに最終的には開始反射点（ビーム交差点）とに対応する。
【０１１５】
ＣＰＵに戻されたデータがこれに記憶される。
さらに、ビームを計算し、それらの伝搬を加速構造において実現することが可能となる（１６１０）。我々は、シャドウレイについて事前に計算されたものと同じビームを再使用することができる。しかしながら、いくつかの反射により、ビームが分離していくつかのサブビームになる可能性がある（同じビームが壁の隅部に衝突し、これが、光線再放出方向の視点から２つに切断される場合）。したがって、このようなステップ１６１０により、必要に応じて上記ビームを再度定めることが可能となる。
【０１１６】
ビームは、コヒーレントな再放出方向（たとえば、反射方向）を考慮に入れることにより、空間的に近接した交差点を考慮に入れることを可能にする予め読出されている画像から、必要に応じて、計算することができる。
【０１１７】
次いで、ステップ１５００の場合と同様に、加速構造がＣＰＵによって各々のビームに適用されて、反射されたビームが交差する三角形が決定される。このような三角形は、第２ランクの交差された三角形と称され得る。こうして、各々のビームのために、第２ランクの交差された三角形の組が登録される。
【０１１８】
最終的に、各々の反射された光線が交差する最も近接する三角形はどれかについて、反
射された光線が計算される（１６２０）。
【０１１９】
【表５】
2009525526.tif 000007
【０１２０】
これは、ＧＰＵによる新たなレンダリングパスである。
ＣＰＵは、反射された光線と第２ランクの交差された三角形との交差を計算する要求をＧＰＵに送信する。
【０１２１】
この要求の解決は、ＧＰＵシェーダーによって実現される。この目的のために、光線上の交差距離はｚバッファについての深さとして用いられ、これにより、各々の画素において交差した最も近接する三角形だけを維持することが可能となる。用いられるトレーシング方法は、非間接的なトレーシング方法であり、テストされるべき各々の三角形は、この三角形に衝突し得る光線の画素を含む箱上でトレースされる。これらの結果をこの箱のうちのいくつかの画素だけに適用するために、三角形に関連付けられるエミッタ識別子が用いられ、さらに、一次識別子画像が用いられ、これにより、各々の画素において、２つの識別子が同一である場合にのみ計算を有効なものとみなすことが可能となる。
【０１２２】
・影を受けるスクリーンサイズの画像が黒に着色され（ｉｄなし）、関連するｚバッファの深さが１．０ｆに設定される（最大深さ）。
【０１２３】
・ビーム面の画素をカバーする区域が、反射の際に可視となる各々の三角形のためにトレースされる。
【０１２４】
・「頂点シェーダー」が、ビーム面上における入射光線の交差点と、反射方向とを計算する。
【０１２５】
・「ピクセルシェーダー」は、実際の交差が存在する場合、三角形と、各々の画素に対応する光線との交差点を計算する。風景に対するその最大限の長さに比較した光線の長さ（通常、視点から最も遠い要素によって定められる風景を含む球体の寸法）がｚバッファに書込まれる。したがって、反射された光線を横断する最初の三角形だけが識別子画像に
とどまる。
【０１２６】
光線開始点を含み、それらの方向を含む画像が解のために用いられる。トレーシング結果は三角形の識別子画像となる。これは反射された画像４０である（図５）。
【０１２７】
この二次識別子画像はＧＰＵメモリに記憶され、次いで、ＣＰＵに転送される。当該ＣＰＵは、ここでは、画像の画素の各々における反射によって可視となる三角形の識別番号を有している。
【０１２８】
反射された画像におけるシャドウレイの計算１６３０
レンダリングにおいてさらなる定義が必要であれば、反射された画像におけるシャドウレイを計算することができる。
【０１２９】
これを行なうために、たとえば、２つのＧＰＵレンダリングパスにおいて容易に計算できる以下の情報が利用可能であれば、ステップ１５０からの手順に追従することができる。
【０１３０】
・反射された光線の交差点。
・反射された光線の識別画像。
【０１３１】
交差点はいくつかの方法で決定可能である。
・反射された方向の画像を最大解像度で読出すこと、および、一次レイと全く同じ方法で、各々の光線についての線−面の交差を計算することによる。
【０１３２】
・反射された光線が衝突する点の交差座標を計算するために付加的なトレーシングパスを用いること、および、ＣＰＵにおいてこの情報を読出すことによる。
【０１３３】
なお、識別子画像が、反射または伝送の場合に、前のビーム伝搬中に既に計算されていることに留意されたい。
【０１３４】
このようにして、反射時に見られる三角形の影情報が計算される。これは、反射時に見られる三角形の色を元に戻すのに用いられることとなる一種の光マスクである。
【０１３５】
反射された画像についての照明の計算１６４０
上述のステップ１５４０に関して、このステップは、可能であれば反射時に見られるこのような画素が受ける影を考慮に入れつつ、反射時に見られる画素の色を計算することを含む。これは、反射（または伝送）があるために間接的な照明タスクとなる。
【０１３６】
このステップは、ＧＰＵにより、間接照明を計算するために実現される。当該ＧＰＵは、
・（予め計算された）光線の開始点画像と、
・（予め計算された）光線の直接画像と、
・反射時に可視である三角形の識別子画像に対応する、受光三角形の識別子画像と、を認識していなければならない。
【０１３７】
この情報では、ＧＰＵシェーダーは、反射時に可視であるオブジェクトの材料の特性を用いて照明の計算を行なう。
【０１３８】
二次識別子画像から始めて、反射時に可視である要素の色が、影および間接照明光線を考慮に入れて決定される。図１８の例は光線Ｂ３およびＢ４のトレーシングを示す。当該
手順は、影をトレースするのに用いられるものに類似している。
【０１３９】
・反射された色を受けるスクリーンサイズの画像が黒に着色される。
・反射されたｉｄ画像において可視である各々の三角形の画素をカバーするゾーンが上記三角形のためにトレースされる。
【０１４０】
・「頂点シェーダー」が、ビーム面に入射する光線の反射方向と交差点とを計算する。
・「ピクセルシェーダー」が、反射された光線と三角形との交差を計算する。交差の衝突点により、Ｂ３およびＢ４の計算が可能となる。識別子の同等性テストは、照明が計算されている三角形であり、かつトレースされた四辺形の画素すべてについて必ずしも可視ではない三角形に合致する画素についてのみ、交差の計算を有効にすることを可能にする。
【０１４１】
こうして得られた画像は、可視の画素の各々のために、（影を考慮に入れて）反射時に見られる要素の色を含む。
【０１４２】
反射された光線についてのこの計算手順は、伝送された光線と、より上のランクの反射された光線（すなわち、受けている多数の反射または伝送）とに適用可能であることが理解される。この発明は、光線の樹枝状部分において深さごとに機能するので、各々の伝搬のために、伝搬に最も合致する新しいビームを計算し（識別子画像の生成および再放出方向）、調査されるべきメッシュ三角形の空間を制限するよう加速構造をビームに適用し、さらに、最終的に、伝搬されたビームとこの制限された組との交差を計算することが適切である。再帰性の原理は、深さごと、および、伝搬の種類ごとに適用される。
【０１４３】
このようにして、（一次または結果となる）反射、伝送についての画素色成分を含む風景の画像の組が得られる。たとえば、２つの反射および伝送の深さについては、このステップにおいて生成される画像は、
−影を考慮に入れた第１の反射画像、
−第１の反射の後に続く第２の反射画像、
−第１の反射の後に続く伝送画像、
−影を考慮に入れた第１の伝送画像、
−第１の伝送の後に続く反射画像、
−第１の反射の後に続く第２の伝送画像、である。
【０１４４】
最終レンダリング１８０
ＧＰＵは、これらの画像の各々を合計しかつ調整することにより、上述のステップ中に計算されるさまざまな画像から最終画像のコンピュータ生成を実行する。
【０１４５】
・ステップ１５４０は、これらの要素の影および色を考慮に入れて、風景の要素であるカメラによって直接的に可視となる結果を含む画像を生成した。
【０１４６】
・再帰的なステップ１６４０の各々は、このレベルでの影を考慮に入れて、風景のために伝搬された光線の樹枝状部分における対象となる光線についての可視の結果を含む画像を生成する。
【０１４７】
これらの画像は、風景の要素を構成する材料の特性に従って、それら画像の間で画素ごとに追加され、調整される（より正確なレンダリングのために反射または伝送係数を考慮に入れる）。
【０１４８】
この発明は、先行技術の他の技術に比べて顕著な性能を提供する。この発明と市販され
ているメンタルレイ（Mental Ray）のソリューション（http:www.mentalimages.comを参照）との間の、図１９における画像についての計算性能を以下の表にまとめる。
【０１４９】
【表６】
2009525526.tif 000008
【０１５０】
この発明は、等しい品質レベルで既存の技術よりも高速でより複雑な画像を計算することを可能にすることにより、画像レンダリングに適用される。これにより、品質と速度とを制御して、いくつかの分野における必要性を満たすことが可能となる。
【０１５１】
特に、以下の分野では、トレードの中核としてコンピュータ生成画像、すなわち、シミュレーション（たとえば、飛行シミュレーション）、コンピュータ支援による設計（設計センタ）、ビデオゲーム、映画の撮影後の編集（特殊効果）、または、コンピュータ生成動画など、が用いられる。
【図面の簡単な説明】
【０１５２】
【図１】この発明を通じてコンピュータ生成画像を合成することが所望されており、オブジェクトを表現するための５０００のメッシュ三角形を含む仮想風景を示す図である。
【図２】レイトレーシングプロセスにおける光線伝搬を示す図である。
【図３】レイトレーシングプロセスにおける光線伝搬を示す図である。
【図４】この発明を実現するためのアーキテクチャシステムの例を示す図である。
【図５】光線伝搬を合成するグラフを示す図である。
【図６】この発明のフローチャートである。
【図７】可視のメッシュ三角形を得るための、グラフィックスカードによるグラフィックレンダリングを示す図である。
【図８】この発明に従ったビームの構造を示す図である。
【図９】この発明に従ったビームの構造を示す図である。
【図１０】この発明に従ったビームの構造を示す図である。
【図１１】この発明に従ったビーム伝搬を示す図である。
【図１２】起伏のあるテクスチャ面の場合の光線反射を示す図である。
【図１３】この発明を実現するための通常の加速構造の例を示す図である。
【図１４】図６におけるシャドウレイを計算するためのフローチャートである。
【図１５】この発明についての影計算を示す図である。
【図１６】この発明についての影計算を示す図である。
【図１７】図６における反射された光線または伝送された光線を計算するためのフローチャートである。
【図１８】レイトレーシングの二次レイを示す図である。
【図１９】この発明の性能と先行技術の性能とを比較するためのトーラスを示す図である。
【図１】
2009525526.tif 000009
【図２】
2009525526.tif 000010
【図３】
2009525526.tif 000011
【図４】
2009525526.tif 000012
【図５】
2009525526.tif 000013
【図６】
2009525526.tif 000014
【図７】
2009525526.tif 000015
【図８】
2009525526.tif 000016
【図９】
2009525526.tif 000017
【図１０】
2009525526.tif 000018
【図１１】
2009525526.tif 000019
【図１２】
2009525526.tif 000020
【図１３】
2009525526.tif 000021
【図１４】
2009525526.tif 000022
【図１５】
2009525526.tif 000023
【図１６】
2009525526.tif 000024
【図１７】
2009525526.tif 000025
【図１８】
2009525526.tif 000026
【図１９】
2009525526.tif 000027
【国際調査報告】
2009525526.tif 000028
2009525526.tif 000029
2009525526.tif 000030
2009525526.tif 000031
2009525526.tif 000032
2009525526.tif 000033