(57)【要約】      （修正有）【課題】光線追跡法を用いて画像をレンダリングするための、改善された方法を提供する。【解決手段】変化する視点に応じてフレーム間のアクセラレーション・データ構造体を更新又は再使用することができる。ツリー及び画像構成品質は、カメラ視野の急速な変化に応じて調整することができる。代替的に又は付加的に、ツリー構築サイクルをスキップすることができる。ツリー構造体の全て又は部分は、間隔を置いて、例えば、既定数のフレームの後で、構築することができる。変化速度の増加に応じて、より多くの幾何学的画像データをツリーのリーフ・ノード毎に加えることができる。レンダリング・アルゴリズムの品質をさらに下げることができる。光線追跡アルゴリズムは、再帰の深さを減らすことができ、より少ない投射２次光線を生成することができる。【選択図】図２
2010176663.tif 000002
【特許請求の範囲】
【請求項１】
光線追跡法を用いて画像をレンダリングする方法であって、
各々が画像データを含む複数のフレームの、各々の中の複数の光線投射のそれぞれの光線起点の間の差異を決定することと、
前記決定された差異によって、画像をレンダリングするのに用いる処理リソース量を減らすことと、
を含む方法。
【請求項２】
既定数の前記複数のフレームに対してアクセラレーション・データ構造体を再使用することにより、前記用いる処理リソース量を減らすことをさらに含む、請求項１に記載の方法。
【請求項３】
既定数の前記複数のフレームに対するアクセラレーション・データ構造体の構築をスキップすることにより、前記用いる処理リソース量を減らすことをさらに含む、請求項１に記載の方法。
【請求項４】
前記レンダリングされた画像の視覚明瞭度を減らすことにより、前記用いる処理リソース量を減らすことをさらに含む、請求項１に記載の方法。
【請求項５】
アクセラレーション・データ構造体のノード毎に含まれる基本要素の数を増すことにより、前記用いる処理リソース量を減らすことをさらに含む、請求項１に記載の方法。
【請求項６】
前記複数のフレームのうちの１つに関連付けられるアクセラレーション・データ構造体の生成に影響を及ぼすことにより、前記用いる処理リソース量を減らすことをさらに含む、請求項１に記載の方法。
【請求項７】
発生させる２次光線の数を減らすことにより、前記処理リソース量を減らすことをさらに含む、請求項１に記載の方法。
【請求項８】
前記複数の光線投射の数を減らすことにより、前記用いる処理リソース量を減らすことをさらに含む、請求項１に記載の方法。
【請求項９】
前記複数の光線投射の再帰の深さを減らすことにより、前記用いる処理リソース量を減らすことをさらに含む、請求項１に記載の方法。
【請求項１０】
ソフトシャドウ品質を下げることにより、前記用いる処理リソース量を減らすことをさらに含む、請求項１に記載の方法。
【請求項１１】
多重サンプリング・アンチエイリアス処理サンプルを減らすことにより、前記用いる処理リソース量を減らすことをさらに含む、請求項１に記載の方法。
【請求項１２】
前記複数の光線に関連する優先権指示を減らすことにより、前記用いる処理リソース量を減らすことをさらに含む、請求項１に記載の方法。
【請求項１３】
前記差異を決定することは、前記それぞれの光線起点に関連するフレーム間の変化速度を決定することをさらに含む、請求項１に記載の方法。
【請求項１４】
前記決定された変化速度を閾値変化速度と比較することをさらに含む、請求項１３に記載の方法。
【請求項１５】
前記変化速度を、前記複数のフレームのうちの以前のフレームに関連する変化速度に基づいて決定することをさらに含む、請求項１３に記載の方法。
【請求項１６】
前記変化速度を、前記複数のフレームの前記光線起点の間の前記変化速度の増加を起す可能性のある将来のプログラム・イベントに基づいて決定することをさらに含む、請求項１３に記載の方法。
【請求項１７】
前記差異を決定することは、基準点に対する位置変化を決定することをさらに含む、請求項１に記載の方法。
【請求項１８】
前記差異を決定することは、少なくとも１つの画素及び物体に対する位置変化を決定することをさらに含む、請求項１に記載の方法。
【請求項１９】
前記差異を決定することは、ベクトルの方向変化を決定することをさらに含む、請求項１に記載の方法。
【請求項２０】
前記用いる処理リソース量を減らすことは、別のアプリケーションの処理要件によって前記処理リソース量を減らすことをさらに含む、請求項１に記載の方法。
【請求項２１】
前記用いる処理リソース量を減らすことは、モーション・ブラーに対する検出された要件によって、前記処理リソース量を減らすことをさらに含む、請求項１に記載の方法。
【請求項２２】
前記減らした量に等しい別の処理リソース量を別のアプリケーションに割り当てることをさらに含む、請求項１に記載の方法。
【請求項２３】
画像データ、及び、各々が前記画像データの一部分に対応する複数のノードを含むアクセラレーション・データ構造体を含むフレーム情報と、光線追跡を実行し、複数のフレームのそれぞれの光線起点の間の差異を決定し、そして前記決定された差異によって画像をレンダリングするのに用いる処理リソース量を減らすように構成されたプログラム・コードとをストアするように構成されたメモリと、
前記メモリと通信し、前記決定された差異によって前記画像をレンダリングするのに用いる処理リソース量を減らすための前記プログラム・コードを実行するように構成されたプロセッサと
を備える装置。
【請求項２４】
バウンディング・ボリュームに論理的に分割された画像データと、前記バウンディング・ボリュームに対応するノードを含むアクセラレーション・データ構造体とを含むフレームをストアするように構成されたメモリと、
前記メモリと通信し、３次元の前記画像データを含む複数のフレームを受け取り、視野及び処理パラメータにより定められるプログラム視点を含む光線起点から、前記３次元の画像データを通して伝わる光線を生成するように構成されたプロセッサと
を含み、
前記プロセッサは、フレーム間の前記光線起点の相対位置の変化に応じて、前記アクセラレーション・データ構造体を変更するようにさらに構成される、
装置。
【請求項２５】
光線追跡を実行し、複数のフレームのそれぞれの光線起点の間の差異を決定し、そして、前記決定された差異によって画像をレンダリングするのに用いる処理リソース量を減らすように構成されたプログラム・コードを含むプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に画像処理に関し、より具体的には、光線追跡操作のフレーム間での視点の変化に応じてアクセラレーション・データ構造体（ＡＤＳ）を更新することに関する。
【背景技術】
【０００２】
光線追跡法はビデオゲーム・アニメーション、動画及び他のメディア・アプリケーションにおいて主流になってきた。光線追跡法は光源とカメラをつなぐ経路を識別し加え合わせることにより写実的画像を合成する技術を表す。光線を視線に沿って追跡して可視性が決定され、また光源からの光線を追跡して照度が決定される。
【０００３】
光線は無限長の半直線から構成される。空間のある一点で発生する光線は位置ベクトル及び方向ベクトルに沿った行程によって表される。光線追跡法はコンピュータ・グラフィックスにおいて、光線を起点から、方向ベクトルによって表される視線に沿って方向付けることにより可視性を決定するように用いられる。光線は仮想シーン内の幾何学的構造物に対する交差に関してテストされ、その視線に沿った最も近い可視表面が決定される。
【０００４】
光線追跡法は、光線を平面内の画素を通して追跡することにより画像を生成する。この技術は、通常、典型的な走査線レンダリング法によるより高い、非常に高度な写実性を生ずることができる。光線追跡法は、反射及び屈折、並びに散乱及び色収差のような種々様々な光学的効果をシミュレートすることができる。シーンにはデジタル写真で捕捉された画像及びモデルのデータを組み込むことができる。
【０００５】
光線追跡法におけるそのようなシーンは、プログラマ又は視覚アーチストにより中間ツールを用いて数学的に記述される。例えば、大部分の光線追跡プロセスは、ＡＤＳ、例えばｋ次元木（ｋｄ木）を用いて３次元画像を生成する。ｋｄ木は、３次元空間内の空のバウンディング・ボリュームに対応する空のリーフ・ノードを含むことができる。バウンディング・ボリュームは論理的に分割されたシーンの一部分を含むことができる。光線追跡アルゴリズムは、シーンを軸整列平面で再帰的に分割することができる。初めにシーンはそのような平面で２つに分割され得る。結果として得られる各半分は、他の何れかの平面に沿って再び分割される。これは、ｋｄ木構造の階層的組織化に帰着する。この構造の各レベルを再帰的にトラバースして木の次のレベルを見出せる場所を決定することができる。
【０００６】
ｋｄ木のリーフ・ノードは、幾つかの多角形又は基本要素を含む小さな軸整列セルを含むことができる。木を昇った次のレベルにおいて、各ノードは、幾つかの既定数のリーフ・ノードで完全に満たされた軸整列ボックスを表す。従って、分割平面はより大きなボリュームをより小さなリーフ・セルに分割する。次のレベルにおいて、各ノードは、より低レベルのノードで完全に満たされた軸整列ボックスを、同様の分割面を用いて表す。何れの所与のレベルにおいても、光線をバウンディング・ボリュームに交差させ、光線が物体に当らないか、当るか、物体から屈折及び／又は反射するかどうかを決定することができる。
【０００７】
各光線は、通常、シーン内の全ての物体のある部分集合との交差に関してテストされる。ひとたび最近接の物体が識別されると、アルゴリズムは交差点における入射光を推定し物体の材料特性を調べる。この情報を組み合せて画素の最終的な色を算出することができる。ある特定の照明アルゴリズム及び物体の材料は、シーンに作り直すより多くの光線を必要とする可能性がある。
【０００８】
光線追跡法の有用性にもかかわらず、現在の光線追跡技術は多くの既知の制限及び弱点を有する。例えば、ＡＤＳを構築するのに用いられるアルゴリズムはＡＤＳの遅いセットアップを経験する可能性があり、また、比較的大量の処理及びメモリを必要とする可能性がある。これらの計算リソースは、従ってシーン・レンダリング・プロセスの他の局面には利用できなくなる。幾つかの場合には、画像をレンダリングするよりも木を構築するのにより多くの時間がかかる可能性がある。その結果、ＡＤＳのインテリジェントな構築の収穫逓減が生じる。そのような問題は、システムが一シーンを作成するのに一連のフレームを取り扱う必要がある場合に悪化する。画像データのオブジェクトの変化に加えて、物体に対するビューワの視野がフレーム毎に変化する可能性がある。そのようなことは、カメラがオブジェクトの一シーンを横切ってパンニング又は移動する場合に起る可能性がある。そのような変化は、通常はＡＤＳの迅速な再構成を必要とし、これがシステムの重い負担になる可能性がある。
【発明の概要】
【発明が解決しようとする課題】
【０００９】
従って、光線追跡プロセスを用いて画像をレンダリングする改善された方法の必要性が存在する。
【課題を解決するための手段】
【００１０】
本発明は、光線追跡法を用いて画像をレンダリングするための、改善されたコンピュータ実施の方法、装置及びプログラムを提供する。本発明と整合する実施形態は、各々が画像データを含む複数のフレームの各々における複数の光線投射に関するそれぞれの光線起点の間の差異を決定することができる。画像のレンダリングに用いる処理リソースは決定された差分によって減らすことができる。
【００１１】
本発明の態様は、用いる処理リソース量を、既定数の複数のフレームに対してアクセラレーション・データ構造体を再使用することにより、減らすことができる。一実施形態は、既定数の複数のフレームに対してアクセラレーション・データ構造体の構築をスキップすることができる。プロセスは、一般にレンダリングされた画像の視覚明瞭度を減らすことができる。そのように構成された場合、フレーム間の変化の速さ又は他の差異は、複数のフレームのうちの１つに関連するアクセラレーション・データ構造体の生成に影響を及ぼし得る。
【００１２】
処理要件は、アクセラレーション・データ構造体のノード毎に含まれる基本要素の数を増すことによってされに減らすことができる。同じ又は別の実施形態において、生成される２次光線及び／又は元の投射光線の数を減らすことができる。再帰の深さもソフトシャドウ品質と同様に減らすことができる。光線に割り当てられる優先権はアンチエイリアス処理サンプルの多重サンプリングの数と共に減らすことができる。
【００１３】
そのように構成された場合、画像をレンダリングするのに用いる処理リソースは、他のアプリケーションの処理要件、及び／又はモーション・ブラーの必要性によって減らすことができる。節約された処理リソースは、別のアプリケーションに割り当てることができる。
【００１４】
一実施形態において、フレーム間の差異は、基準に対する位置変化によって決定することができる。例示的な基準は画素又は物体を含むことができる。差異はベクトルの方向変化を含むことができる
【００１５】
フレーム間の差異は、それぞれの光線起点に関連する変化の速度を検出することにより決定することができる。一実施形態において決定された変化速度は閾値変化速度と比較することができる。変化の速度は、複数のフレームのうちの以前のフレームに関連する変化速度に基づくものとすることができる。代替的に又は付加的に、変化の速度は、フレームの光線起点の間の変化速度の増加を起す可能性のある将来のプログラム・イベントに基づくものとすることができる。
【００１６】
本発明の態様は、画像データ、及び各々が画像データの一部分に対応する複数のノードを含むアクセラレーション・データ構造体を含むフレーム情報と、光線追跡を実行して複数のフレームのそれぞれの光線起点の間の差異を決定するように構成されたプログラム・コードとをストアするように構成されたメモリを含むことができる。プログラム・コードは、決定された差異によって、画像をレンダリングするのに用いる処理リソース量を減らすことができる。メモリと通信し、プログラム・コードを実行するように構成されたプロセッサは、決定された差異によって、画像をレンダリングするのに用いる処理リソース量を減らすことができる。
【００１７】
実施形態は、論理的にバウンディング・ボリュームに分割された画像と、バウンディング・ボリュームに対応するノードを含むアクセラレーション・データ構造体とを含むフレームをストアするように構成されたメモリを含むことができる。メモリと通信するプロセッサは、３次元画像データを含む複数のフレームを受け取り、光線起点から進む光線を生成するように構成することができる。プロセッサはさらに、フレーム間の光線起点の相対位置の変化に応じてアクセラレーション・データ構造体を変更するように構成することができる。
【００１８】
本発明の態様は、光線追跡を実行して複数のフレームのそれぞれの光線起点の間の差異を決定し、そして決定された差異によって画像をレンダリングするのに用いる処理リソース量を減らすように構成されたプログラム・コードを備えたプログラムを含むことができる。
【００１９】
本発明を特徴付けるこれら及び他の利点及び特徴は、本明細書に添付され、さらに別の部分を形成する特許請求の範囲の中に示される。しかし、本発明並びにその利点及びその使用により達成される目的をより良く理解するために、本発明の例示的な実施形態を説明する図面及び付随の記述事項を参照されたい。
【図面の簡単な説明】
【００２０】
【図１】本発明の基礎原理による、変化する視点に応じて画像フレーム間のＡＤＳを更新するように構成された、ネットワーク接続されたコンピュータ・システムのブロック図を示す。
【図２】本発明の基礎原理による、一連のフレームにわたる光線投射操作及び仮想環境の論理的な表示を示す。
【図３】図２の環境に対応する図２の光線投射操作構造体を用いて生成することができるＡＤＳを示す。
【図４】フレーム間のビューワの視野の変化速度によって画像データをレンダリングするための、図１のシステムのプロセスにより実行可能なステップを有するフローチャートである。
【発明を実施するための形態】
【００２１】
本発明の原理に整合する実施形態は、フレーム間の視野の変化に基づいて計算要件を減らすような画像レンダリング法を提供する。光線追跡操作の計算要件は、視点の急速な変化に応じて減らすことができる。態様は比較的速い変化速度の認識を利用して、視覚明瞭度を代えることにより処理電力及び他のリソースを節約することができる。
【００２２】
実施形態は、変化する視点に応じてＡＤＳがフレーム間で更新される光線追跡操作を含むことができる。本発明の態様は、ユーザの「注視点（look at）」の急速な変化に応じてツリー構築の品位を調整することができる。代替的に又は付加的に、ＡＤＳ構築サイクルをスキップすることができる。ＡＤＳの全て又は幾つかは、間隔をおいて、例えば既定数のフレームの後で構築することができる。
【００２３】
本発明の態様は、フレーム間のカメラの視野角の変化速度を決定することができる。この決定された変化速度は、モデル視野マトリクスに対する任意の等価な変化を含むことができる。モデル視野マトリクスは全体的なスケーリング、並進及び回転操作を説明することができる。
【００２４】
十分な検出された変化速度の増加に応じてツリー内のリーフ・ノード毎に、より多くの幾何学的画像データを加えることができる。レンダリング・アルゴリズムの品質はさらに下げることができる。光線追跡アルゴリズムは再帰の深さを減らすことができ、より少数の反射及び発生光線を生成することができる。光線トレーサは、他の品質パラメータの中でも、ソフトシャドウ及び全体照明サンプルの品質を下げることができる。別の又は同じ実施形態において、解像度を下げることができ、また多重サンプル・アンチエイリアス処理（ＭＳＡＡ）サンプルの数を減らすことができる。この品質の削減にはリーフ毎の付加的な画像データを利用することができる。
【００２５】
代替的に又は付加的に、本発明の態様は高カメラ変化速度に応じて、ツリーの再構築を全くスキップすることができる。関連するプロセスがフレーム間の所望のモーション・ブラーを生成することができる。別の実施形態は自動的にツリーをスキップして特定の数のフレームの後で１つ又は複数のフレームを再バランスさせることができるが、適切な場合にはやはり、画像データ幾何学構造をノードに挿入することができる。
【００２６】
本発明の原理はその形態又は用途を限定しないが、画像を分割する一実施形態は図１に例示されたシステム１０を通じて利用可能な構造体を利用する。図１は一般に、変化する視点に応じて画像フレーム間のＡＤＳを更新するように構成された、ネットワーク接続されたコンピュータ・システム１０のブロック図を示す。より具体的にはシステム１０は、ネットワーク３８に結合された１つ又は複数のクライアント・コンピュータ３０を備える。ネットワーク３８は、それらに限定されないが、ローカル・エリア、ワイド・エリア、無線、及び公共ネットワーク（例えば、インターネット）を含むネットワーク化相互接続を表す。さらに、任意の数のコンピュータ及び他のデバイスを、ネットワーク３８を通じてネットワーク化し、例えば複数サーバにすることができる。
【００２７】
コンピュータ・システムは、以後「装置」、「コンピュータ」、「ツール」、「デバイス」、又は単に「システム」とも呼ぶが、これらの用語はそれぞれ多くの他のコントローラ構成を含むことができることを認識されたい。さらに図１には１つのネットワーク・インタフェース・デバイスだけを示すが、任意の数のコンピュータ及び他のデバイスをネットワーク３８を通じてネットワーク化することができる。さらに別の実施形態において、システム１０は、スタンドアローン構成、即ち別のコンピュータ又はコンピュータ・ネットワークから接続を切った構成で実施することができる。
【００２８】
コンピュータ３０は典型的には、メモリ３２に結合された少なくとも１つのプロセッサ１２を含む。プロセッサ１２は１つ又は複数のプロセッサ（例えば、中央処理装置、マイクロプロセッサ）を表すことができる。より具体的には、図１のプロセッサ１２は複数のコア処理要素を含む。メモリ３２は、コンピュータ・デバイス３０の主記憶装置４２、及び、任意の補助レベルのメモリ、例えば、キャッシュ・メモリ、不揮発又はバックアップ・メモリ（例えば、プログラム可能又はフラッシュ・メモリ）、読取り専用メモリなどを含むＳＲＡＭデバイスを表すことができる。さらにメモリ３２は、コンピュータ・デバイス３０内の別の場所に物理的に配置されたメモリ記憶装置、例えば、プロセッサ１２内に存在する任意のキャッシュ・メモリ、並びに、例えばデータベース内にストアされた仮想メモリとして用いられる任意の記憶容量、又は、ネットワーク３８を介してコンピュータ・デバイス３０に結合された別のコンピュータ上のメモリを含むものと考えることができる。
【００２９】
コンピュータ・デバイス３０はまた、外部と情報を伝達するための多くの入力及び出力を受け取ることができる。ユーザとのインタフェースに対して、コンピュータ・デバイス３０は典型的には１つ又は複数の入力デバイス３３（例えば、特に、キーボード、マウス、トラックボール、ジョイスティック、タッチパッド、虹彩／指紋スキャナ、及び／又はマイクロフォン）を含む。さらにコンピュータ・デバイス３０はディスプレイ３９（例えば、特に、ＣＲＴモニタ、ＬＣＤディスプレイ・パネル、及び／又はスピーカ）を含む。しかし、コンピュータ・デバイス３０の幾つかの実施により、直接的なユーザ入力及び出力をコンピュータによりサポートしないようにすることができ、コンピュータ・デバイス３０とネットワーク接続されたコンピュータ又はワークステーションを通して、サーバ・コンピュータ・デバイス３０とのインタフェースを実現することができることを認識されたい。図１に示すように、本システムは、光線追跡操作の対象を含む画像を捕捉するのに使用できるカメラ３１を含む。
【００３０】
付加的な記憶装置として、システム１０はまた、例えば、映画、動画又は他の画像データをストアするように構成された１つ又は複数の大容量記憶デバイス３６を含むことができる。例示的なデバイス３６は、特に、フロッピー又は他のリムーバブル・ディスク・ドライブ、フラッシュ・ドライブ、ハードディスク・ドライブ、直接アクセス記憶デバイス（ＤＡＳＤ）、光学式ドライブ（例えば、ＣＤドライブ、ＤＶＤドライブなど）、及び／又はテープ・ドライブを含むことができる。さらにコンピュータ・デバイス３０は、ネットワーク３８に結合された他のコンピュータとの情報の伝達を可能にする１つ又は複数のネットワーク（例えば、特に、ＬＡＮ、ＷＡＮ、無線ネットワーク、及び／又はインターネット）とのインタフェースを含むことができる。コンピュータ・デバイス３０は通常、プロセッサ１２と、コンポーネント３２、３３、３６、３８及び３９の各々との間の適切なアナログ及び／又はデジタル・インタフェースを含むことを認識されたい。
【００３１】
コンピュータ・デバイス３０は、オペレーティング・システム４０の制御下で動作することができ、種々のコンピュータ・ソフトウェア及びハードウェアのアプリケーション、コンポーネント、プログラム、又はモジュールを実行することができる。例えば、システム１０は、主メモリ記憶装置４２、画像レンダリング・アルゴリズム４３及び光線追跡プログラム４４を含むことができる。他のプログラム・コードはＡＤＳ構成アルゴリズム４５、変化決定プログラム４６、グラフィックスカード・プログラム・コード４７、及び物理エンジン４８を含むことができる。画像レンダリング・プログラム４３は、一般に画像を生成するのに用いることができ、シャドウ品質、再帰の深さ及びサンプリング速度のような変数に作用することができる。光線追跡プログラム４４は、一般に、画像面内の画素を通して光路を追跡することにより画像生成を支援することができる。グラフィックスカード・プログラム・コード４７は、典型的には、グラフィックス・アクセラレータ・カード、ディスプレイ・アダプタ、又はグラフィックス・カードとも呼ばれるビデオ・カードによって実行され、画像を生成してディスプレイに出力するように機能する。
【００３２】
ＡＤＳ構成アルゴリズム４５は、画像レンダリング・プログラム及び／又は光線追跡プログラム４３、４４が用いる空間的指標又は他のＡＤＳを生成するのに用いることができる。空間的指標は一般に空間的データベースにより空間的クエリを最適化するように用いられる。非空間的データベースにより用いられる指標は、２つの点がどれほど異なるか、及び点が関心のある空間領域に入るかどうかのような特徴を効果的に取り扱うことができなくてもよい。通常の空間的指標の方法には、グリッド、ｚオーダ、４分木、８分木、ＵＢ木、Ｒ木、及びｋｄ木が含まれる。
【００３３】
変化決定プログラム４６は、フレーム間のカメラ視点、即ち注視点の変化速度及び又は視野変化、を決定することができる。ここで論じるように、フレームは単一の瞬間的画像、即ち３次元写真を含む。従って、フレームは画素のグリッドに対応する。映画及びビデオゲーム業界において、フレームは、カメラの単一の連続的なロールと定義することができ、及び／又はそれに類似したものである。複数のフレームを一緒に編集して一シーン又はシーケンスを形成することができる。完成された映画脚本又は映画は一連のシーンから作成される。従って、複数のフレームは連結されて、人間の目には連続的に動く画像として見えるものを形成する。
【００３４】
物理エンジン４８は、３次元シーン内の物体に適用されるとき、実世界の物理現象をシミュレートするアプリケーションを含むことができる。物理エンジン４８はフレーム・ツー・フレームのベースで物理現象の影響をシミュレートして予測するのに用いることができる。例えば、物理エンジン４８は、物体が移動する場合には物体の位置の更新を行うことができ、物体が３次元シーン内の任意の他の物体と衝突するかどうかを決定する衝突検出テストを行うことができる。本発明の一実施形態により、物理エンジン４８は、複数コア処理要素上の複数のスレッドを用いて物理学関連の計算を実行することができる。
【００３５】
プロセッサ１２、例えば複数コア処理要素は、複数の基本スループット・エンジン（ＢＴＥ）を含むことができる。ＢＴＥは、複数の処理スレッド及びコア・キャッシュ、例えば、レベル１（Ｌ１）キャッシュを備えることができる。図１に示すように、ＢＴＥのスレッドは、作業負荷マネージャ１４、１５及びベクトル・スループット・エンジン１６、１７、１８、１９、２０、２１に割り当てるか又は別様に含める。作業負荷マネージャ１４、１５は一般にシステム１０により発生される光線でＡＤＳをトラバースする。ここで説明するように、ＡＤＳは、比較的大きな３次元シーンをより小さなバウンディング・ボリュームに分割するのに用いられるツリー型データ構造体として実施することができる。システム１０は光線追跡及びＡＤＳを用いて光線−バウンディング・ボリューム交差を迅速に決定することができる。本発明の一実施形態において、作業負荷マネージャは、ＡＤＳを用いて光線−バウンディング・ボリューム交差テストを実行することができる。
【００３６】
ベクトル・スループット・エンジン１６、１７、１８、１９、２０、２１は一般に、光線がバウンディング・ボリューム内に含まれる基本要素と交差するかどうかを決定する。作業負荷マネージャ１４，１５が光線−バウンディング・ボリューム交差を決定した後で、作業負荷マネージャ１４，１５は受信箱２２、２３を用いて光線をベクトル・スループット・エンジン１６、１７、１８、１９、２０、２１に送ることができる。次いでベクトル・スループット・エンジン１６、１７、１８、１９、２０、２１は、光線がバウンディング・ボリューム内に含まれる基本要素と交差するかどうかを決定することができる。ベクトル・スループット・エンジン１６、１７、１８、１９、２０、２１はまた、光線が通過する画素の色を決定することに関する動作を実行することができる。作業負荷マネージャ１４、１５及びベクトル・スループット・エンジン１６、１７、１８、１９、２０、２１に割り当てられる処理スレッドは、共用複数コア処理要素のメモリ・キャッシュ２４、２５にアクセスすることができる。メモリ・キャッシュ２４、２５はレベル２（Ｌ２）のキャッシュを含むことができる。
【００３７】
ここで論じるように、作業負荷マネージャ１４、１５及びベクトル・スループット・エンジン１６、１７、１８、１９、２０、２１はまた受信箱２２、２３にアクセスすることができる。受信箱２２、２３はメモリ・マップ型アドレス空間を含むことができる。従って、受信箱２２、２３はＢＴＥのそれぞれ１つの中に配置された処理スレッドにマッピングすることができる。作業負荷マネージャ１４、１５及びベクトル・スループット・エンジン１６、１７、１８、１９、２０、２１の各々のスレッドは、メモリ・マップ型受信箱を含むことができ、他のメモリ・マップ型受信箱２２、２３の全てにアクセスすることができる。受信箱２２、２３は、作業負荷マネージャ１４、１５及びベクトル・スループット・エンジン１６、１７、１８、１９、２０、２１によって用いられる低遅延及び高帯域通信ネットワークを含むことができる。
【００３８】
作業負荷マネージャ１４、１５及びベクトル・スループット・エンジン１６、１７、１８、１９、２０、２１は、受信箱２２、２３を互いに通信し相互にデータ処理作業を再配分するためのネットワークとして用いることができる。別の実施形態においては、通信ネットワーク内に別個の送信箱を用いることができる。例えば処理結果は別個の送信箱により受け取ることができる。そのように構成される場合、受信箱２２、２３はまた送信箱として機能することができる。例えば、作業負荷マネージャ１４、１５は処理機能の結果を、その結果を用いることになるベクトル・スループット・エンジン１６、１７、１８、１９、２０、２１の受信箱２２、２３に直接書き込むことができる。
【００３９】
作業負荷マネージャ１４、１５及びベクトル・スループット・エンジン１６、１７、１８、１９、２０、２１は、作業を分配し、再配分して全体的なシステム性能を向上させることができる。プロセッサ１２内には２つのユニットだけを示すが、フレーム毎に数百万の基本要素をレンダリングするシステム１０は多数のそのようなユニットを含むことができる。
【００４０】
図１はまた、作業負荷マネージャ１４、１５が、画像処理関連タスクを収集し、それらを他の作業負荷マネージャ１４、１５及び／又は他のユニットのベクトル・スループット・エンジン１６、１７、１８、１９、２０、２１に対して分配するのを可能にする高速バス２６を示す。同様にバス２６は、ベクトル・スループット・エンジン１６、１７、１８、１９、２０、２１の各々が他のベクトル・スループット・エンジン１６、１７、１８、１９、２０、２１又は作業負荷マネージャ１４、１５と通信できるようにすることができる。
【００４１】
バス２６を用いる通信は、キャッシュ２４、２５にデータ・パケットを負担させずに実行することができる。キャッシュ２４、２５によるメモリ空間は受信箱２２、２３に割り当てることができる。受信箱２２、２３はスレッドに割り当てることができる。必要な場合には、受信箱メモリは独占的にスレッドに割り当てることができる。受信箱２２、２３は、キャッシュ２４、２５の割り当てられた受信箱部分内にスレッドのデータ及び命令を保持することができる。スレッドは受信箱２２、２３を用いて互いに通信することができる。１つのスレッドが、受信箱２２、２３の別のスレッドに供給されるデータ及び／又は命令を有する場合、他方のスレッドはデータ及び／又は命令を受信箱２２、２３に送ることができる。本発明の一実施形態において、受信箱２２、２３内のメモリ空間はグローバルメモリ・アドレスにマッピングすることができる。
【００４２】
実施形態は、キャッシュ２４、２５の部分を受信箱２２、２３に割り当てて、低遅延で高帯域の通信ネットワークを作成することができる。キャッシュ２４、２５の残りの部分は割り当てずに情報をストアするのに用いることができる。そのような情報は、光線追跡に用いられ、別様には処理スレッド間の通信に関連させる必要のない、幾何学及びデータ構造体を含むことができる。処理スレッド間の通信に受信箱２２、２３を用い、そしてキャッシュ２４、２５の残り部分を幾何学及びデータ構造体をストアするのに用いることにより、次の光線を追跡するか又は次のフレームをレンダリングするときに再使用される可能性のあるデータはキャッシュ２４、２５内に存続することができる。次の光線を追跡するか又は次のフレームをレンダリングするときに再使用される可能性のないデータは、キャッシュ２４、２５内に存続する必要がない。
【００４３】
ここで論じるように、本発明と整合する特定の実施形態は、複数のスレッドを並列に実行するマイクロプロセッサを含み、複数のマイクロプロセッサの使用により達成可能な多くの同じ性能利得を効率的にもたらすことができる。実施形態はさらに、多数のコンピュータ・ソフトウェア及びハードウェア技術を含んで付加的な並列処理を促進することができる。ソフトウェアの観点からは、コンピュータ・プログラムがマルチスレッド内で同時に実行して複数のタスクを同時に実行することを可能にするマルチスレッド型オペレーティング・システム及びカーネルが開発されている。スレッドは一般にプログラムの実行の独立なパスを表す。
【００４４】
一般に、本発明の実施形態を実施するための、ハードウェアにおいて実施されてもされなくても、オペレーティング・システムの部分として、又は特定のアプリケーション、コンポーネント、プログラム、エンジン、プロセス、プログラム・ツール、オブジェクト、モジュール、又は命令シーケンス、又はそれらのサブセットとして、実行されるルーチンは、本明細書では、「アルゴリズム」、「関数」、「プログラム・コード」、又は単に「プログラム」と呼ぶことができる。プログラム・コードは、典型的には、１つ又は複数の命令を含み、これらの命令は、コンピュータ内の種々のメモリ及び記憶デバイス内に様々な時に常駐し、そしてコンピュータ内の１つ又は複数のプロセスにより読み出され実行されるとき、本発明の種々の態様を具体化する実ステップ又は要素を実行するのに必要なステップをコンピュータに実行させる。当業者であれば、本発明の原理と整合する実施形態においては、それでもなお、１つだけ又は任意の数の位置に常駐するプログラム・コードを用いることができることを認識されたい。
【００４５】
さらに、本発明はこれ以降、完全に機能するコンピュータ・システムの文脈で説明するが、当業者であれば、本発明の種々の実施形態は種々の形態のプログラムとして配布できること、及び本発明は、実際に配布するのに用いられるコンピュータ可読の信号支持媒体の特定の型には関わらず、等しく適用できることを認識するであろう。信号支持コンピュータ可読媒体の例には、それらに限定されないが、特に、揮発又は不揮発メモリ・デバイス、フロッピー及び他のリムーバブル・ディスク、ハードディスク・ドライブ、磁気テープ、光ディスク（例えば、ＣＤＲＯＭ，ＤＶＤなど）のような有形の記録可能型媒体、並びに、デジタル及びアナログ通信リンクのような伝送型媒体が含まれる。
【００４６】
さらに、本明細書で説明する種々のプログラム・コードは、それが本発明の特定の実施形態において実行されるアプリケーション又はエンジンに基づいて識別することができる。しかし、付随する任意の特定のプログラム述語は単に便宜上用いるものであり、本発明は、それら述語によって識別及び／又は示される任意の特定のアプリケーション又はエンジンにだけ用いることに限定されないことを認識されたい。
【００４７】
さらに、コンピュータ・プログラムをルーチン、プロシージャ、メソッド、モジュール、オブジェクトなどに編成することができる通常は無数の方式、並びに、プログラムの機能を、典型的なコンピュータ内に常駐する種々のソフトウェア層（例えば、オペレーティング・システム、ライブラリ、ＡＰＩ、アプリケーション、アプレットなど）の間に割り当てることができる様々な方式が与えられるので、本発明は、本明細書で説明するプログラム機能の特定の編成及び割り当てに限定されないことを認識されたい。
【００４８】
図１に示す種々のソフトウェア・コンポーネント及びリソースは種々の様式で実施することができ、それらの様式は、種々のコンピュータ・ソフトウェア・アプリケーション、ルーチン、コンポーネント、プログラム、オブジェクト、モジュール、データ構造体及びプログラムの使用を含む。当業者であれば、図１に示した例示的な環境は本発明を限定することを意図したものではないことをさらに認識するであろう。実際に、当業者であれば、他の代替的なハードウェア及び／又はソフトウェア環境を本発明の範囲から逸脱せずに用いることができることを認識するであろう。
【００４９】
図２は、本発明の基礎原理による、光線投射操作の論理的表示及び仮想環境５０を示す。環境５０はより具体的には一連のフレームにわたり変化する視点（例えば、視野、注視点、カメラ視野角）を示す。環境５０は、光線起点５４ａで表される観察者の目が見る物体５２を含む。従って、起点５４ａは所与のフレームに対するカメラ視点に関連付けることができる。破線の視点５４ｂ及び５４ｃは２つの連続するフレームにわたる視点の進行を表すことができる。
【００５０】
光線起点５４ａから延びる光線５６は、物体５２の透視図を表すことができる。光線５６は光の光線に類似した性質及び行動特性を有することができる。光線５６は複数の画素を含んだ画素平面５８に交差することができる。画素又は画像要素は、一般に画像内の情報の最小片を含む。画素は普通２次元グリッドに配置される。各画素は元の画像のサンプルであり、色成分を含むことができる。３次元仮想環境５０は、画像処理システム１０により２次元画像にレンダリングすることができる。得られる２次元画像をモニタ・ディスプレイ３９の上に投影することができる。ディスプレイ３９は種々の色の多数の画素を用いて最終的な２次元画像をレンダリングすることができる。
【００５１】
図２に示すように、光線５６は仮想環境５０及び画素平面５８をトラバースすることができ、この画素平面５８において最終的な２次元画像が画像処理システム１０によりレンダリングされることになる。図２に示すように、画素６０、６２、６４は光線起点５４ａからの光線５６の第１のフレームの交差を表す。
【００５２】
角度５９は、光線起点５４ａと５４ｂの間の相対的視野の変化に対応する。他の計測プロセスを用いることはできるが、本発明の実施形態に整合する計測技術は、環境５０内の基準点５７に対する起点５４ａからの計測を含むことができる。例示的な基準点５７は図２の画素平面５８に含まれる。図２の実施形態において、基準点５７は画素平面５８の中心付近にある。計測される変化はベクトルの成分、例えば、大きさ及び方向の成分を含むことができる。この変化の程度は、本発明の実施形態により、光線処理操作を調整するように用いることができる。
【００５３】
角度６１は起点５４ａと５４ｃの間の視野変化を示す。一実施形態において、ベクトルの変化は複数のフレームにわたるビューワのベクトル変化を用いて計測される。例えば、この変化は、ビューワが向いている方向の変化、並びに、ビデオゲーム又は映画シーケンスの間の基準からのそれらの距離の変化を説明することができる。適切な基準は基準点５７を含むことができるが、代替的に環境５０内の物体又は他のプログラム関数とすることができる。図２に示すように、異なるフレームの起点５４ａ、５４ｃの変化は、環境５０の基準点５７に対して計測することができる。当業者であれば、代替的に、任意の角度計測値を光線起点５４ａ、５４ｂ、５４ｃの近傍で示すことができることを認識するであろう。フレーム及び起点５４ｂ及び５４ｃの位置の相対的移動は、別々のフレームにわたり既知の時間間隔での移動に従って起り得る。計測に用いられる起点５４ａ、５４ｂ、５４ｃは、次のフレームから取得することができるが、他の実施形態においてはフレームをスキップすることができる。
【００５４】
物体５２は、画像処理システム１０によってレンダリングされる例示的な３次元シーンの部分を含む。図２には教示上の目的で一つの球のみを示すが、物体は典型的には多数あり、種々異なる幾何学的形状を含む。物体は、より小さな幾何学的形状（例えば、正方形、円、３角形など）に分割されることが多い。従って、大きな物体は、多数の小さく単純な幾何学的形状で表される。これらの小さな幾何学的形状は基本要素と呼ばれることが多い。
【００５５】
図２に示すように、物体５２及び周囲の空間は１つ又は複数のバウンディング・ボリュームに分割することができる。ここで論じるように、大きなバウンディング・ボリューム６８はＡＤＳの第１のノードに対応させることができる。ここで論じるように、空間はより小さい部分に分割することができる。例えば、バウンディング・ボリューム７０及び７２はバウンディング・ボリューム６８を再分割することができる。再分割ボリューム７０、７２は、元の立方体の４分の１に概ね対応する他のバウンディング・ボリューム７４、７６、７８、８０にさらに分割することができる。図２に示すように、それらのバウンディング・ボリュームの１つ７４は、より小さい区画８２、８４、８６、８８、９０、９２、９４、９６、９８にさらに論理的に再分割することができる。当業者であれば、仮想空間は任意の既知のスキーム又はＡＤＳアルゴリズムにより任意の比で分割することができることを認識するであろう。
【００５６】
図２はまた、光源６６を示す。光源６６は物体５２を照明する。光源６６及び物体５２の位置に依存して、光源６６はシーン内の他の物体（図示せず）に投影される影を生じることができる。
【００５７】
画素平面５８は数百万の画素を含むことができる。個々の画素の各々は、異なる色を表示して最終の複合２次元画像をディスプレイ上にレンダリングすることができる。光線追跡アルゴリズム４４は、発生された光線５６が環境５０内で出合う色を算定することができる。画像処理システム１０は、光線が出合った色を、光線５６が起点５４ａから物体５２に、又は３次元シーン内の別の部分に至る途中で通過する画素６０、６２、６４に割り当てることができる。多数の光線が画素に交差する場合、画素の色は、その画素にたいして発せされた全ての光線からの各々の色の寄与によって決定することができる。他の画素は、２次元画像内の画素の結果として生じた色を決定するように発生された単一の光線を有するだけであり得る。幾つかの画素は画像処理システムによって発生された光線をなにも有さない可能性があり、この場合それらの色は、画像処理システム内のアルゴリズムにより決定、近似、又は割り当てることができる。例えば、光線がシーン内の物体に交差しない場合、その物体にはデフォルトの背景色、例えば空の色を近似する色を割り当てることができる。
【００５８】
光線５６が当たる物体の色には多くのファクタが寄与する可能性がある。例えば、３次元シーン内の光源は物体を照明することができる。さらに、物体の物理的特性が物体の色に寄与する可能性がある。例えば、物体が反射性又は透過性である場合、他の非光源物体が物体の色に寄与する可能性がある。
【００５９】
３次元環境内の他の物体からの影響を決定するために、２次光線を、元の光線５６が物体５２と交差する点から発生させることができる。例えば、１つの型の２次光線は影光線とすることができる。影光線は、元の光線５６が物体と交差する点への光の寄与を決定するのに用いることができる。
【００６０】
別の型の２次光線は透過光線とすることができる。透過光線は、どの色又は光が物体５２を透過できるかを決定するのに用いることができる。透過光線は、元の光線が交差する物体が透明又は半透明である場合に画像システム１０によって発生させることができる。例えば、遮蔽物体はガラスを含むことができる。透過光線は、元の光線が物体に当る角度に相対的な角度で物体を通してトラバースする。
【００６１】
さらに第３の型の２次光線は反射光線とすることができる。反射光線はどの色又は光が物体上で反射されるかを決定するのに用いることができる。元の光線が交差する物体が金属のような反射特性を有する場合、反射光線はどの色又は光線が物体によって反射され得るか決定するために発生させることができる。反射光線は、元の光線が物体と交差する角度に相対的な角度で物体から離れてトラバースする。
【００６２】
影光線は、元の光線５６と物体５２の交差点から光源６６に向けて追跡することができる。光線が光源に達する前に別の物体に遭遇せずに光線が光源に達したとすると、光源６６は、元の光線が物体５２に当った点において元の光線５６が当った物体５２を照明することができる。他の影光線は、元の光線が物体に当った点と光源の間に別の物体（図示せず）で遮断される経路を有する可能性がある。遮蔽物体が不透明である場合、光源は、元の光線が物体に当った点において物体を照明しないことになる。従って、光源は元の光線の色に寄与することはできない。しかし、物体が半透明又は透明である場合、光源は、元の光線が物体に当った点において物体を照明することができる。
【００６３】
全ての２次光線（例えば、影光線、透過光線、反射光線など）の色及び光の全体の寄与は、元の光線が透過した画素の最終的な色に寄与することができる。
【００６４】
図３は、図２の光線投射操作構造体を用いて生成することができるものに概ね対応するＡＤＳ１２０を示す。より具体的にはＡＤＳ１２０のノード１２２は、一般に図２のバウンディング・ボリューム６８に対応する。図２のバウンディング・ボリューム７０、７２は一般に図３のノード１２４、１２６によって表すことができる。従って、図３のノード１２８、１３０、１３２、１３４はそれぞれ、図２のバウンディング・ボリューム７４、７６、７８、８０に対応する。図３に示すように、リーフ・ノード１３６、１３８、１４０、１４２、１４４、１４６、１４８、１５０は、図２の最小のバウンディング・ボリューム８２、８４、８６、８８、９０、９２、９４、９６に概ね対応する。
【００６５】
ＡＤＳ１２０は、発生された光線５６が、レンダリングされるシーン内の任意の物体と交差するかどうかを迅速且つ効率的に決定するのに有用であり得る。ＡＤＳ１２０は、３次元シーン又は世界を、基本要素を含んでも含まなくてもよい相対的により小さなボリュームに分割することができる。画像処理システム１０は、次にこれら小さなボリュームの既知の境界を用いて、光線が小さなボリューム内に含まれる基本要素と交差し得るかどうかを決定することができる。光線５６が基本要素を含むボリュームと交差する場合、そのボリューム内に含まれる基本要素の既知の位置及び寸法に対する光線５６の軌跡を用いて光線交差テストを実行することができる。
【００６６】
或いは、光線５６が特定のボリュームと交差しない場合、そのボリューム内に含まれる基本要素に対して光線−基本要素交差テストを実行する必要はない。さらに光線が、基本要素を含まないバウンディング・ボリュームと交差する場合、そのバウンディング・ボリュームに対して光線−基本要素交差テストを実行する必要はない。このように、必要となり得る光線−基本要素交差テストの回数を減らすことにより、空間的指標の使用は、光線追跡画像処理システム１０の性能を著しく向上させる。種々の空間的指標ＡＤＳの幾つかの例には、８分木、ｋｄ木、及び２元空間分割木（ＢＳＰ木）が含まれる。幾つかの異なったＡＤＳが存在するが、本発明の実施形態の説明を容易にするために、以下の実施例では、ｋｄ木を用いることになる。しかし、当業者であれば、本発明の実施形態は、他のＡＤＳの種々の型のいずれにも適用できることを認識されたい、
【００６７】
ある費用関数をｋｄ木の中で用いて、シーンを再帰的に軸整列平面により分割することができる。初めにシーンは平面によって２つに分割することができる。半分の各々は次にどれか他の平面にそって再び分割することができる。この技術は構造体の階層的構成を生じることができる。ｋｄ木の各レベルは、再帰的にトラバースして構造体の次のレベルを見出すことができる場所を決定することができる。これらの構造体の構成段階で費用関数を注意深く選んで、これの木をトラバースしながら最適の性能を達成することができる。
【００６８】
別様に説明すれば、ｋｄ木は全空間を小さいボリュームに分割するのに軸整列型バウンディング・ボリュームを用いる。即ち、ｋｄ木は分割平面を用いて３次元空間を小さいバウンディング・ボリュームに分割する。小さいバウンディング・ボリュームは全体としてシーン内の全空間を形成する。大きなバウンディング・ボリュームを２つのより小さなバウンディング・ボリュームに分割又は分離することの決定は、画像処理システム１０によりＡＤＳ構成アルゴリズム４５を用いてなされる。
【００６９】
本発明の実施形態は、複数のフレームにわたる視点の変化に関連する変化決定情報を用いて、いつ分割するかを決定することができる。いつバウンディング・ボリュームをより小さなボリュームに分割するかを決定するための１つの基準は、そのバウンディング・ボリューム内に含まれる基本要素の数とすることができる。即ち、バウンディング・ボリュームが所定のリーフ・ノード閾値より多くの基本要素を含む限り、ＡＤＳ構成アルゴリズム４５は、より多くの分割平面を描いてボリュームの分割を続ける。いつバウンディング・ボリュームをより小さなボリュームに分割するかを決定するための別の基準は、そのバウンディング・ボリューム内に含まれる空間の量とすることができる。さらに、バウンディング・ボリュームの分割を続けることの判断はまた、幾つの基本要素がバウンディング・ボリュームを生成する平面により交差され得るかに基づくことができる。
【００７０】
より詳しく図３を見ると、ＡＤＳ１２０は、シーン／環境５０の分割を表す２分木構造体を含むことができる。ＡＤＳ１２０の２分木構造体は、ノード、ブランチ及びリーフを含むことができる。例えば、ＡＤＳ１２０の中間ノード１２６は、比較的大きなバウンディング・ボリューム７２を表すことができる。ノード１２６はサブノード１２８、１３０、１３２、１３４へのブランチを含むことができ、これらサブノードはそれぞれ、４つの比較的小さな分割ボリューム７４、７６、７８、８０を表すことができる。これらのバウンディング・ボリューム７４、７６、７８、８０は、比較的大きなバウンディング・ボリューム７２を分割平面で分割した後に生じる。
【００７１】
軸整列型ｋｄ木において、各中間ノードは他のノードへのブランチを含むことができる。中間ノードは、リーフ・ノードへのポインタ、並びに、分割平面がそれに沿って描かれた軸の場所、のような情報をストアすることができる。一配置において、中間ノードはリーフ・ノードへのブランチ（ポインタ）を含むことができる。リーフ・ノード１３６は、より小さいボリュームにさらには再分割されない、基本要素へのポインタを含むノードである。中間ノードはまた、さらに再分割される他の中間ノードへのブランチを含むことができる。中間ノードはまた、どの軸に沿って分割平面が描かれたか、及びその軸に沿ってどこに分割平面が描かれたかを判断するのに必要な情報を含むことができる。
【００７２】
ＡＤＳ構成アルゴリズム４５は、バウンディング・ボリューム７７が所定のリーフ・ノード閾値より多くの基本要素を含む限り、バウンディング・ボリューム７７の分割を続けることができる。例えば、一実施形態は２個の基本要素の閾値を用いることができる。従って、ＡＤＳ構成アルゴリズム４５は、閾値に関連付けられた基本要素の数に等しいか又はそれ以下の基本要素を含むバウンディング・ボリューム９０の分割を停止することができる。そのようなノード１４４は、さらに再分割はされないのでリーフ・ノードを含むことができる。
【００７３】
結果として得られるｋｄ木又は他の空間的指標構造体は、共用メモリ・キャッシュ２４にストアすることができる。ｋｄ木、及びそのｋｄ木を備えた対応するデータのサイズは、共用メモリ・キャッシュ２４内での記憶のために最適化することができる。図３は３次元環境５０に対応するＡＤＳ１２０を示すが、本発明と整合する別のｋｄ木の実施形態は、画像処理システムによりレンダリングされる２次元シーンに対応することができる。
【００７４】
図１乃至図３を一緒に参照すると、一実施形態のシステム１０は、画素平面５８の上から始まる発生光線のパターンを追跡し、そして、画素毎に１光線で、光線の発生を続け、平面５８内の各画素に対して光線が発生されるまで画素のグリッドを下に移動することができる。最終的に複数の光線を、選択したピクセルを通して発生させることができる。
【００７５】
作業負荷マネージャ１４は、ＡＤＳ１２０を通しての光線５６のトラバースに関連する操作を実行することができる。例えば、作業負荷マネージャ１４は、光線５６が交差するバウンディング・ボリューム６８、７２、７４を定めるノード１２２、１２６、１２８へのブランチを辿ってリーフ・ノード１５０に達するまで、ＡＤＳ１２０を通して光線をトラバースすることができる。言い換えれば、作業負荷マネージャ１４は、発生された光線５６の座標及び軌跡を用いて、この光線が、ＡＤＳ１２０内のノード１２２、１６、１２８によって定められるバウンディング・ボリューム６８、７２、７４と交差するかどうか決定することができる。作業負荷マネージャ１４は、光線５６が基本要素のみを含むバウンディング・ボリューム９６（即ち、リーフ・ノード）と交差するまでＡＤＳ１２０をトラバースし続けることができる。光線５６をリーフ・ノード１５０までトラバースした後、作業負荷マネージャ１４は、光線５６及び交差された画素６４を定める情報、並びに、交差されたノード１２４情報をベクトル・スループット・エンジン１８に送ることができる。
【００７６】
作業負荷マネージャ１４は、光線情報をベクトル・スループット・エンジン１８に送った後、ＡＤＳ１２０を通しての別の光線５６のトラバースを開始することができる。従って、作業負荷マネージャ１４は、ＡＤＳ１２０を通して光線５６を連続的にトラバースすることができ、その間にベクトル・スループット・エンジン１６、１７、１８、１９、２０、２１は光線５６が環境５０内の物体５２に交差するかどうかを判断する。即ち、ベクトル・スループット・エンジン１６、１７、１８、１９、２０、２１は、光線５６及びバウンディング・ボリュームを定める情報を受け取った後で、光線−基本要素交差テストを実行することができる。ベクトル・スループット・エンジン１６、１７、１８、１９、２０、２１は、光線５６が交差した点における物体５２の色を決定することができる。交差点における物体の色を決定した後、ベクトル・スループット・エンジン１６は、光線５６が通過した画素６０の色を更新することができる。例えば、ベクトル・スループット・エンジン１６は、画素６０に対応するフレーム・バッファ・メモリ位置に書き込むことができる。
【００７７】
ベクトル・スループット・エンジン１６、１７、１８、１９、２０、２１は２次光線を発生させることができる。例えば、ベクトル・スループット・エンジン１６は反射光線及び透過／屈折光線を発生させることができる。両方の２次光線は、元の光線５６が物体５２と交差する点から発することができる。ここで説明するように、２次光線は、光線５６が物体５２と交差する点における物体５２に対する付加的な色の寄与を決定するのに用いることができる。そのような２次光線の発生は、それら各々の軌跡を決定すること、及び、それらにタグを付けて、２次光線からの付加的な色の寄与を用いて元の光線５６が通過する画素６０の色を更新できるようにすることを含む。ベクトル・スループット・エンジン１６は、受信箱２２を用いて２次光線を定める情報を作業負荷マネージャ１４に送ることができる。２次光線情報を受け取った作業負荷マネージャ１４は、軌跡及び他の情報を用いてＡＤＳ１２０をトラバースすることができる。
【００７８】
図４は、フレーム間のビューワの視野の変化速度によって画像データをレンダリングするための図１のシステム１０のプロセスにより実行可能なステップを有するフローチャートである。より具体的には、図４のプロセスは、本発明の基礎原理による、フレーム間のカメラ視野の変化速度に基づいてレンダリングの計算要件に影響を及ぼすことができる。一実施形態において、計算要件は視野の急激な変化に応じて減らすことができる。本発明の態様は、変化する視点に応じてフレーム間のＡＤＳ１２０が更新される光線追跡操作を含むことができる。本発明の態様は、ユーザの注視点の急激な変化に応じて、ツリー構築の品質レベルを調整することができる。一態様において、フローチャート２００は、多くの処理基準に基づいてＡＤＳ１２０を選択的に構成するステップ又は再使用するステップを示す。
【００７９】
図４のステップをより詳細に見ると、システム１０はブロック２１０において新しいフレームを受け取る。ここで論じるように、フレームは、単一の瞬間的な画像、即ち、画素平面５８に対応する３次元シーン５０を含むことができる。ブロック２１２において、システム１０は、光線起点５４ａ、５４ｂを古いフレームと新しいフレームとの間で比較することができる。一実施形態において、光線起点５４ａ、５４ｂ及び関連するベクトル計測値は、画素平面５８の中心又は他の位置にある基準点５７に対して比較することができる。
【００８０】
システム１０は、ブロック２１４において、変化速度がある所定の閾値変化速度より大きいかどうかを判断することができる。この閾値変化速度は望ましい場合には比較的高い変化速度に設定することができる。そのような高い変化速度は、ビューワがシーンを素早くパンニングする場合のような、モーション・ブラーが自然に予期される場合に対応させることができる。所定の閾値はまた、タイムリー且つ完全にＡＤＳを更新するためには効率が悪いか又はさもなければ望ましくない処理量が要求されることになる事例に適合させることができる。
【００８１】
ブロック２１４において、所定の閾値変化速度に出合わないか又はそれを越えない場合には、システム１０はブロック２１６において新しいＡＤＳを構築することができる。新しいＡＤＳの構築は、本明細書で説明する光線トラバース及び関連する交差決定を含むことができる。
【００８２】
或いは、ブロック２１４において決定された変化速度が閾値を越えた場合には、システム１０はブロック２１８において、既存のＡＤＳ１２０に関連するデータを保持及び表示するべきかどうかを判断する。このブロック２１８における判断は多くのファクタを含むことができる。例えば、システム１０は、どこか他所での処理／計算リソースに対する現在及び将来の必要性を認識することができる。この認識は、システム１０に、新しいフレームに対して以前のＡＤＳ１２０を再使用することにより処理を持続するように促す又は作用することができる。
【００８３】
別の実施例において、システム１０は、例えば、視点の変化を直ちに引き起こし得るシーン外の爆発又はクラッシュのような、注意を引くイベントを有する別のフレームに対するフレームの近接性に基づいて古いＡＤＳ１２０を用いるべきであると判断する。システム１０は、ビューワの注意及び焦点が変更されることになることを認識するので、新しいフレームに対するＡＤＳの幾何学的構造は殆ど同じであろうと想定する。従って、新しいＡＤＳの構築は無効化となり得る。
【００８４】
ここで論じるように、カメラの方向の変化は、システム１０に古いＡＤＳ１２０を再使用させる可能性がある。古いＡＤＳ１２０はまた、物体がシーン内を非常に速く移動する場合に用いることができる。ＡＤＳ１２０の再使用によりシミュレートされるブラー（blur）のレベルは、高速移動物体への迅速な焦点合せに対するビューワの自然な不可能性に基づいて適切なものとすることができる。
【００８５】
同じＡＤＳ１２０は、ある特定のレベルのブラーが所望される場合に用いることができる。古いＡＤＳのパターンを選択的に再使用することにより、自然に生じるブラーをシミュレートすることができる。新しいフレームに対するＡＤＳの構築は、以前のフレームに関連する視点の変化速度に基づいてスキップする（そして古いＡＤＳ１２０を用いる）ことができる。システム１０は、以前の速度から視野が急速にパンニングすることを自動的に推測することができる。視野は、高速度で変化しているとき、突然停止する可能性は低い。視野は減速して停止するまでに幾つかのフレームを取る可能性がある。この状況は、新しいＡＤＳを構築する代わりに、ブロック２２０において古いＡＤＳ１２０を再使用するのに適した機会である。最後にシステム１０はデータの履歴を調べて、データの中で特に、視野が比較的高速で変化したフレームが幾つあるかを決定することができる。
【００８６】
ブロック２１８において、古いＡＤＳ１２０が保持される場合、システム１０は新しいフレームに対する新しいＡＤＳの構築を基本的にスキップすることができる。このことはフレーム毎に遂行することができるが、その代りにシステム１０は、既定数のフレーム、例えば、ｎ番目毎のフレームをスキップすることができる。
【００８７】
ブロック２１８において、その代りに、システム１０が古いＡＤＳ１２０を保持すべきではないと判断した場合、システム１０はそれでも処理要件を最適化するステップを行うことができる。ブロック２１８において古いＡＤＳ１２０を保持するかどうかの判断により、ブロック２２２における最適化は視野変化の速度に基づくものとすることができる。より具体的には、ブロック２２２においてシステム１０は、リーフ・ノード閾値への寄与の新しい変数を決定することができる。ここで論じるように、新しい変数は各リーフ・ノード内に許容される基本要素の数を増加させることができる。この特徴は、新しいＡＤＳがブロック２１６において構築されるとき、生成されるリーフ・ノード、ブランチ、ポインタの数、及び関連する計算要件を減らすことができる。
【００８８】
一実施形態は、ブロック２２４においてツリー構成情報を同時に設定することができる。ブロック２２４における新しい設定には、ブロック２２２において設定されたノード毎の多数の基本要素を利用することができる。この情報は画像レンダリング品質の所望のレベルを示すことができ、それゆえに、ブロック２２６において光線追跡アルゴリズム４４の動作に影響を及ぼすことができる。上述のように、その情報はブロック２１２において決定された変化速度に基づくものとすることができる。その情報が、変化速度が比較的高いことを示す場合、新しいＡＤＳの全体的な品質は効率を考慮して下げられる可能性がある。即ち、ツリー構成情報は準最適ツリーのみが必要であることを示す可能性がある。例えば、再帰の深さを減らすことができ、同じく、発生される２次光線の数を減らすことができる。ソフトシャドウの品質を下げ、全体照明サンプルの数を投射光線の数と共に減らすことができる。ＭＳＡＡサンプル及び解像度を減らすことができ、ある特定の光線又は特定の型の光線の優先レベルを下げることができる。これらの作業は単独で又は組み合せて実行し、光線追跡及び画像レンダリングに関連する全体の計算要件を減らすことができる。
【００８９】
本発明は種々の実施形態の記述により説明され、これら実施形態はかなり詳細に説明されたが、添付の特許請求の範囲をそれら詳細事項に限定するか又はなんらかの制限をすることは出願人の意図するところではない。例えば、古いＡＤＳ全体を保持するのではなく、一実施形態においては、データの幾つかを保持し、そして古いＡＤＳの部分を置き換え／更新することができる。従って、本発明はそのより広い態様において、図示し説明した特定の細部、代表的な装置及び方法、並びに例証的な実施例に限定されない。従って、出願人の一般的な発明概念の趣旨又は範囲から逸脱せずに、それら細部から離れることはできる。
【符号の説明】
【００９０】
１０：画像処理システム（コンピュータ・システム）
１２：プロセッサ
１４、１５：作業負荷マネージャ
１６、１７、１８、１９、２０、２１：ベクトル・スループット・エンジン
２２、２３：受信箱
２４、２５：メモリ・キャッシュ
２６：高速バス
３０：コンピュータ
３１：カメラ
３２：メモリ
３３：入力デバイス
３６：大容量記憶装置
３８：ネットワーク
３９：ディスプレイ
４０：オペレーティング・システム
４２：主記憶装置
４３：画像レンダリング・アルゴリズム
４４：光線追跡プログラム
４５：ＡＤＳ構成アルゴリズム
４６：変化決定プログラム
４７：グラフィックス・カード・プログラムコード
４８：物理エンジン
５０：仮想環境
５２：物体
５４ａ、５４ｂ、５４ｃ：光線起点
５６：光線
５７：基準点
５８：画素平面
５９：角度
６０、６２、６４：画素
６６：光源
６８、７０、７２、７４、７６、７８、８０：バウンディング・ボリューム
８０、８２、８４、８６、８８、９０、９２、９４、９６、９８：より小さい区画（バウンディング・ボリューム）
１２０：アクセラレーション・データ構造体（ＡＤＳ）
１２２、１２４、１２６、１２８、１３０、１３２、１３４：ノード
１３６、１３８、１４０、１４２、１４４、１４６、１４８、１５０：リーフ・ノード
【図１】
2010176663.tif 000003
【図２】
2010176663.tif 000004
【図３】
2010176663.tif 000005
【図４】
2010176663.tif 000006