(57)【特許請求の範囲】
【請求項１】
光線追跡に使われる加速構造を生成する方法において、
三次元空間に含まれたオブジェクトをバウンディングボックスに区分する段階と、
ノードを利用して、前記バウンディングボックスの包含関係を示す加速構造を生成する段階と、
前記ノードのうちオーバーラップされるノードをマーキングする段階と、を含み、
前記マーキングする段階は、
前記ノードにフラグを追加し、各ノードの子ノードがオーバーラップされるか否かを、前記フラグで表示し、及び／又は、
前記オーバーラップされるバウンディングボックスを示すノードの最近接上位ノードに、オーバーラップ情報を保存する、
加速構造を生成する方法。
【請求項２】
請求項１記載の方法で生成された加速構造を探索する方法において、
（ａ）前記加速構造において、光線データと交差するリーフノードを探索する段階と、
（ｂ）前記交差されたリーフノードの上位ノードのうちオーバーラップされる子ノードを含むノードがなければ、探索を終了し、オーバーラップされる子ノードを含むノードがあれば、オーバーラップされる子ノードをさらに探索する段階と、を含む加速構造を探索する方法。
【請求項３】
前記（ｂ）段階は、
ノードのオーバーラップフラグを介して、ノードがオーバーラップされる子ノードを含むか否かを確認することを特徴とする請求項２に記載の加速構造を探索する方法。
【請求項４】
前記（ａ）段階は、探索されていないノードは、スタックにプッシュして保存する段階を含むことを特徴とする請求項２又は３に記載の加速構造を探索する方法。
【請求項５】
前記（ｂ）段階でオーバーラップされる子ノードをさらに探索するとき、前記スタックに保存されたノードを順次にポップし、オーバーラップされる子ノードをさらに探索することを特徴とする請求項４に記載の加速構造を探索する方法。
【請求項６】
前記（ｂ）段階は、
前記スタックからポップされたノードのうちオーバーラップされる子ノードを含まないノードを、探索しないことを特徴とする請求項５に記載の加速構造を探索する方法。
【請求項７】
光線追跡に使われる加速構造を生成する装置において、
三次元空間に含まれたオブジェクトをバウンディングボックスに区分し、ノードを利用して、前記バウンディングボックスの包含関係を示す加速構造を生成する加速構造生成部と、
前記ノードのうちオーバーラップされるノードをマーキングするオーバーラップマーカーと、を含み、
前記オーバーラップマーカーは、
前記ノードにフラグを追加し、かつ、各ノードの子ノードがオーバーラップされるか否かを、前記フラグで表示し、及び／又は、
前記オーバーラップされるバウンディングボックスを示すノードの最近接上位ノードに、オーバーラップ情報を保存する
加速構造生成装置。
【請求項８】
請求項１記載の方法で生成された加速構造を探索するレイトレーシング・コアにおいて、
前記加速構造において、光線データと交差するリーフノードを探索し、前記交差されたリーフノードの上位ノードのうちオーバーラップされる子ノードを含むノードがなければ、探索を終了し、オーバーラップされる子ノードを含むノードがあれば、オーバーラップされる子ノードをさらに探索するＴＲＶユニットを含み、
前記ＴＲＶユニットは、ノードを保存するスタックを含むレイトレーシング・コア。
【請求項９】
前記ＴＲＶユニットは、ノードのオーバーラップフラグを介して、ノードがオーバーラップされる子ノードを含むか否かを確認することを特徴とする請求項８に記載のレイトレーシング・コア。
【請求項１０】
前記ＴＲＶユニットは、探索されていないノードを、前記スタックにプッシュして保存することを特徴とする請求項８又は９に記載のレイトレーシング・コア。
【請求項１１】
前記ＴＲＶユニットは、オーバーラップされる子ノードをさらに探索するとき、前記スタックに保存されたノードを順次にポップし、オーバーラップされる子ノードをさらに探索することを特徴とする請求項１０に記載のレイトレーシング・コア。
【請求項１２】
前記ＴＲＶユニットは、前記スタックからポップされたノードのうちオーバーラップされるノードではないノードは、探索しないことを特徴とする請求項１１に記載のレイトレーシング・コア。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、加速構造の生成及び探索を行う方法並びに装置に関する。
【背景技術】
【０００２】
３Ｄ（three-dimensional）レンダリングは、三次元客体データを、与えられたカメラの視点（view  point）から見える映像に合成（synthesis）する映像処理過程である。光線追跡方法は、レンダリングの対象になるシーンオブジェクト（scene  object）と光線とが交差する地点を追跡する過程である。光線追跡（ray-tracing）は、加速構造（acceleration  structure）の探索（traversal）と光線・プリミティブ（ray-primitive）との交差検査（intersection  test）過程を含む。このとき、探索過程及び交差検査過程で、多くの演算量（computation）及び広いメモリ帯域幅（memory  bandwidth）を必要とする。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
本発明が解決しようとする課題は、さらなる探索を減らし、加速構造の探索を早期に終了するための方法及び装置を提供することである。
【０００４】
本発明が解決しようとする課題はまた、前記方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体を提供することでもある。
【０００５】
なお、本実施形態がなすべき技術的課題は、前述のような技術的課題に限定されるものではなく、以下の実施形態から他の技術的課題も類推される。
【課題を解決するための手段】
【０００６】
前記課題を解決するために、本発明の一実施形態による加速構造生成方法は、三次元空間に含まれたオブジェクトをバウンディングボックス（bounding  box）に区分する段階と、ノードを利用して、前記バウンディングボックスの包含関係を示す加速構造を生成する段階と、前記ノードのうちオーバーラップされるノードを表示（mark）する段階と、を含む。
【０００７】
前記課題を解決するために本発明の一実施形態による加速構造探索方法は、（ａ）前記加速構造において光線データと交差するリーフノードを探索する段階と、（ｂ）前記交差されたリーフノードの上位ノードのうちオーバーラップされる子ノードを含むノードがなければ、探索を終了し、オーバーラップされる子ノードを含むノードがあれば、オーバーラップされる子ノードをさらに探索する段階と、を含む。
【発明の効果】
【０００８】
本発明によれば、フラグを利用して、バウンディングボックスのオーバーラップを表示する加速構造を生成することができる。
【０００９】
本発明によれば、また、バウンディングボックスのオーバーラップの有無によって、追加探索を行うのか否かを決定し、加速構造の探索過程を減らすことができる。
【図面の簡単な説明】
【００１０】
【図１】光線追跡について説明するための図面である。
【図２】レイトレーシング・コアについて説明するための図面である。
【図３】レイトレーシング・コアが光線追跡を行う動作について説明するための図面である。
【図４】光線追跡を加速させるための方法について説明するための図面である。
【図５】図４の光線追跡を加速させるための方法について説明するための図面である。
【図６】一実施形態による加速構造を生成する方法について説明するためのフローチャートである。
【図７】オブジェクトをバウンディングボックスに分割することについて説明するための図面である。
【図８】一実施形態による加速構造について説明するための図面である。
【図９】一実施形態による加速構造探索方法について説明するためのフローチャートである。
【図１０】探索過程について説明するための図面である。
【図１１】一実施形態による加速構造を探索する方法について説明するための図面である。
【図１２】探索過程について説明するための図面である。
【図１３】一実施形態による加速構造を探索する方法について説明するための図面である。
【図１４】一実施形態による加速構造生成装置及びレイトレーシング・コアについて説明するための構成図である。
【発明を実施するための形態】
【００１１】
以下、図面を参照しつつ実施形態について詳細に説明する。
【００１２】
図１は、光線追跡について説明するための図面である。図１を参照すれば、三次元モデリングで、レイトレーシング・コア（ray  tracing  core）は、視点（view  point）１０を決定し、視点によって、画面（image）２０を決定する。視点１０と画面２０とが決定されれば、レイトレーシング・コアは、視点１０から、画面２０の各ピクセル（pixel）に対して光線を生成する。
【００１３】
図１の構成について説明すれば、視点１０から、一次光線（primary  ray）３０が生成される。一次光線３０は、画面２０を経て、シーンオブジェクト（scene  object）７０と交差する。一次光線３０とシーンオブジェクト７０との交差点では、反射光線（reflection  ray）４０及び屈折光線（refraction  ray）５０が生成される。また、交差点において、光源８０の方向に、シャドー光線（shadow  ray）６０が生成される。このとき、反射光線４０、屈折光線５０、シャドー光線６０は二次光線と呼ばれる。シーンオブジェクト７０は、画面２０に対するレンダリングの対象になるオブジェクトを示す。シーンオブジェクト７０は、複数のプリミティブを含む。
【００１４】
レイトレーシング・コアは、一次光線３０、二次光線（反射光線４０、屈折光線５０、シャドー光線６０）、及び二次光線から派生する光線を分析する。レイトレーシング・コアは、分析結果に基づいて、画面２０を構成するピクセルの色相値を決定する。このとき、レイトレーシング・コアは、シーンオブジェクト７０の特性を考慮し、ピクセルの色相値を決定する。
【００１５】
図２は、レイトレーシング・コア１００について説明するための図面である。図２を参照すれば、レイトレーシング・コア１００は、光線生成ユニット１１０、ＴＲＶ（traverse）ユニット１２０、ＩＳＴ（intersection  test）ユニット１３０及びシェーディング・ユニット１４０を含む。図２では、ＴＲＶユニット１２０、ＩＳＴユニット１３０が、レイトレーシング・コア１００に含まれるように図示されているが、ＴＲＶユニット１２０、ＩＳＴユニット１３０は、別途のハードウェアで具現されてもよい。図２に図示されたレイトレーシング・コア１００は、本実施形態と係わる構成要素だけが図示されている。従って、図２に図示された構成要素以外に、他の汎用的な構成要素がさらに含まれてもよいということは、本実施形態に係る技術分野の当業者であるならば、理解できるであろう。
【００１６】
レイトレーシング・コア１００は、生成された光線と、三次元空間に位置したオブジェクトの交差点を追跡し、画面を構成するピクセルの色相値を決定する。言い替えれば、レイトレーシング・コア１００は、光線とオブジェクトとの交差点を求め、交差点でのオブジェクトの特性によって二次光線を生成し、交差点の色相の値を決定する。
【００１７】
レイトレーシング・コア１００は、加速構造を探索して交差検査を行うとき、過去の探索の結果、及び過去の交差の検査の結果を利用することができる。言い換えれば、レイトレーシング・コア１００は、過去のレンダリング過程で遂行された結果を、現在のレンダリング過程に適用することにより、現在のレンダリングをさらに迅速に行う。
【００１８】
光線生成ユニット１１０は、一次光線及び二次光線を生成する。光線生成ユニット１１０は、視点から一次光線を生成し、一次光線とオブジェクトとの交差点において、反射、屈折またはシャドーの二次光線を生成する。光線生成ユニット１１０は、二次光線とオブジェクトとの交差点において、他の二次光線を生成することができる。光線生成ユニット１１０は、一定の回数内において、反射光線、屈折光線、シャドー光線を生成したり、あるいはオブジェクトの特性によって、反射光線、屈折光線、シャドー光線の生成回数を決定することができる。
【００１９】
ＴＲＶユニット１２０は、光線生成ユニット１１０から生成された光線に関する情報を受信する。生成された光線は、一次光線、二次光線、及び二次光線から派生する光線のいずれも含む。例えば、一次光線の場合、ＴＲＶユニット１２０は、生成された光線の視点及び方向に関する情報を受信することができる。また、二次光線の場合、ＴＲＶユニット１２０は、二次光線の出発点及び方向に関する情報を受信することができる。二次光線の出発点は、一次光線がヒット（hit）した地点を示す。視点または出発点は、座標によっても表現され、方向は、ベクトルによっても表現される。
【００２０】
ＴＲＶユニット１２０は、外部メモリ２５０から、加速構造に関する情報を読み取る（read）。加速構造は、加速構造生成装置２００によって生成され、生成された加速構造は、外部メモリ２５０に保存される。該加速構造は、三次元空間のオブジェクトの位置情報を含んでいる構造を示す。例えば、加速構造は、Ｋ次元ツリー（Ｋ−dimensional  tree）、ＢＶＨ（bounding  volume  hierarchy）などが適用されてもよい。
【００２１】
ＴＲＶユニット１２０は、加速構造を探索し、光線がヒットしたオブジェクトまたはリーフノード（leaf  node）を出力する。例えば、ＴＲＶユニット１２０は、加速構造に含まれたノードを探索し、ノードのうち最下位ノードであるリーフノードのうち、光線がヒットしたリーフノードを、ＩＳＴユニット１３０に出力する。言い替えれば、ＴＲＶユニット１２０は、加速構造を構成するバウンディングボックス（bounding  box）のうちいずれのバウンディングボックスに光線がヒットしたかということを判断し、バウンディングボックスに含まれたオブジェクトのうちいずれのオブジェクトに光線がヒットしたかということを判断する。ヒットしたオブジェクトに関する情報は、ＴＲＶキャッシュに保存される。バウンディングボックスは、複数のオブジェクトまたはプリミティブを含む単位を示し、加速構造によって、他の形態で表現されてもよい。ＴＲＶキャッシュは、ＴＲＶユニット１２０が探索過程で使用するデータを一時的に保存するためのメモリを示す。
【００２２】
ＴＲＶユニット１２０は、過去のレンダリングの結果を利用して、加速構造を探索することができる。ＴＲＶユニット１２０は、ＴＲＶキャッシュに保存された過去のレンダリングの結果を利用して、過去のレンダリングと同一経路において、加速構造を探索することができる。例えば、ＴＲＶユニット１２０が入力された光線に関する加速構造を探索するとき、ＴＲＶユニット１２０は、入力された光線と同一の視点及び方向を有する過去の光線がヒットしたバウンディングボックスに対する探索を優先的に行う。また、ＴＲＶユニット１２０は、過去の光線に関する探索経路を参照し、加速構造を探索することができる。
【００２３】
ＩＳＴユニット１３０は、ＴＲＶユニット１２０から、光線がヒットしたオブジェクトまたはリーフノードを受信し、外部メモリ２５０から、ヒットしたオブジェクトに含まれたプリミティブに関する情報を読み取る。読み取られたプリミティブに関する情報は、ＩＳＴキャッシュに保存される。ＩＳＴキャッシュは、交差検索過程において、ＩＳＴユニット１３０が使用するデータを一時的に保存するためのメモリを示す。
【００２４】
ＩＳＴユニット１３０は、光線とプリミティブとの交差検査を行い、光線がヒットしたプリミティブ及び交差点を出力する。ＴＲＶユニット１２０から、光線がヒットしたオブジェクトが何であるかということを受信したＩＳＴユニット１３０は、ヒットしたオブジェクトに含まれた複数のプリミティブのうちいずれのプリミティブに光線がヒットしたのかを検査する。光線がヒットしたプリミティブを求めた後、ＩＳＴユニット１３０は、ヒットしたプリミティブのどの地点と光線が交差したかということを示す交差点を出力する。該交差点は、座標形態でシェーディング・ユニット１４０に出力される。
【００２５】
ＩＳＴユニット１３０は、過去のレンダリングの結果を利用して、交差検査を行う。ＩＳＴユニット１３０は、ＩＳＴキャッシュに保存された過去のレンダリングの結果を利用して、過去のレンダリングと同一のプリミティブに対して優先的に交差検査を行う。例えば、入力された光線及びプリミティブに対する交差検査を行うとき、ＩＳＴユニット１３０は、入力された光線と同一の視点及び方向を有する過去の光線がヒットしたプリミティブに対する交差検査を優先的に行う。
シェーディング・ユニット１４０は、ＩＳＴユニット１３０から受信された交差点に関する情報、及び交差点の物質特性に基づいて、ピクセルの色相値を決定する。シェーディング・ユニット１４０は、交差点の物質の基本色相及び光源による効果などを考慮し、ピクセルの色相値を決定する。
【００２６】
レイトレーシング・コア１００は、外部メモリ２５０から、光線追跡に必要なデータを受信する。外部メモリ２５０には、加速構造生成装置２００によって生成された加速構造、またはプリミティブに関する情報を示す幾何データ（geometry  data）が保存される。プリミティブは、三角形、四角形などの多角形でもあり、幾何データは、オブジェクトに含まれたプリミティブの頂点及び位置に関する情報を示すことができる。
【００２７】
加速構造生成装置２００は、三次元空間上のオブジェクトの位置情報を含む加速構造を生成する。加速構造生成装置２００は、さまざまな形態の加速構造を生成することができる。例えば、該加速構造は、三次元空間が階層的ツリーに分割された形態でもあり、加速構造生成装置２００は、ＢＶＨまたはＫ次元ツリーを適用し、三次元空間上のオブジェクトの関係を示す構造を生成することができる。加速構造生成装置２００は、リーフノードの最大プリミティブの数及びツリー深さ（tree  depth）を決定し、決定に基づいて、加速構造を生成することができる。
【００２８】
図３は、レイトレーシング・コアが、光線追跡を行う動作について説明するための図面である。レイトレーシング・コアは、例えば、図２に図示されたレイトレーシング・コア１００の構造を有することができる。従って、以下で省略された内容であるとしても、レイトレーシング・コア１００について、以上で記述された内容は、図３の光線追跡方法にも適用される。
【００２９】
段階３１０において、レイトレーシング・コア１００は、光線を生成する。レイトレーシング・コア１００は、一次光線、二次光線、及び二次光線から派生した光線を生成する。
【００３０】
段階３２０において、レイトレーシング・コア１００は、外部メモリ２５０から読み取られた加速構造を探索する。レイトレーシング・コア１００は、生成された光線の視点及び方向に基づいて、加速構造２５１を探索し、光線がヒットしたバウンディングボックスを検出し、ヒットしたバウンディングボックスに含まれたオブジェクトのうち光線がヒットしたオブジェクトを検出する。レイトレーシング・コア１００は、ヒットしたオブジェクトを検出するまで、加速構造２５１の探索を反復（iteration）して行う。例えば、レイトレーシング・コア１００は、いずれか１つの経路に沿って加速構造を探索し、探索された経路上のリーフノードに光線がヒットしていないのであるならば、他の経路で加速構造を探索する。
【００３１】
レイトレーシング・コア１００は、全ての経路を順次に探索することができるが、過去の光線の探索情報に基づいて、特定経路を優先的に探索することができる。例えば、過去の光線の視点及び方向が、現在の光線の視点及び方向と同一であるか、あるいはそれらと類似している場合、レイトレーシング・コア１００は、過去の光線でヒットしたリーフノードが含まれた経路を優先的に探索することができる。
【００３２】
段階３３０において、レイトレーシング・コア１００は、交差検査を行う。レイトレーシング・コア１００は、外部メモリ２５０から読み取られたプリミティブの幾何データ２５２に基づいて交差検査を行う。レイトレーシング・コア１００は、ヒットしたプリミティブを検出するまで、交差検査を反復して行う。例えば、レイトレーシング・コア１００は、いずれか１つのプリミティブに対する交差検査を行い、プリミティブに光線がヒットしていないのであるならば、他のプリミティブに対する交差検査を行う。
【００３３】
レイトレーシング・コア１００は、全てのプリミティブを順次に交差検査することができるが、過去の光線の交差検査情報に基づいて、特定プリミティブを優先的に交差検査することができる。例えば、過去の光線及び現在の光線の視点及び方向が同一であるか、あるいはそれらと類似している場合、レイトレーシング・コア１００は、過去の光線でヒットしたプリミティブに対する交差検査を優先的に行う。
【００３４】
段階３４０において、レイトレーシング・コア１００は、交差検査に基づいて、ピクセルのシェーディングを行う。レイトレーシング・コア１００は、段階３４０が終了すれば、段階３１０に進む。レイトレーシング・コア１００は、段階３１０ないし段階３４０を、画面を構成する全てのピクセルに対して反復的に遂行する。
【００３５】
図４は、光線追跡を加速させるための方法について説明するための図面である。図４を参照すれば、第１画面４１２は、ｔ＝０でレンダリングされた画面を示し、第２画面４２２は、ｔ＝１でレンダリングされた画面を示す。第１画面４１２及び第２画面４２２から、ウサギ４３３だけが移動し、四角形４３１と三角形４３２は、動きがないから、第１画面４１２及び第２画面４２２は、ほぼ類似している。従って、レイトレーシング・コア１００は、第１画面４１２に対するレンダリング結果を利用して、第２画面４２１に対するレンダリングを行う。例えば、第１視点４１０と第２視点４２０との位置が同一であり、第１光線４１１と第２光線４２１との方向が同一であるならば、レイトレーシング・コア１００は、第１光線４１１に対する光線追跡の結果を、第２光線４２１の光線追跡に適用し、第２光線４２１の光線追跡を加速させることができる。例えば、レイトレーシング・コア１００のＴＲＶユニット１２０は、第２光線４２１に対する探索を行うとき、第１光線４１１がヒットしたバウンディングボックスを優先的に探索することができる。また、レイトレーシング・コア１００のＩＳＴユニット１３０は、第２光線４２１に対する交差検査を行う、第１光線４１１がヒットした三角形４３２に対して優先的に交差検査を行う。
【００３６】
図５は、図４の光線追跡を加速させるための方法について説明するための図面である。図５を参照すれば、加速構造は、５個のノード１乃至５を含み、ノード３乃至ノード５は、リーフノードを示す。
【００３７】
ＴＲＶユニット１２０は、３種経路に沿って加速構造を探索することができる。第一に、ＴＲＶユニット１２０は、第１経路であるノード１・ノード２及びノード３に沿って、加速構造を探索することができる。第二に、ＴＲＶユニット１２０は、第２経路であるノード１・ノード２及びノード４に沿って、加速構造を探索することができる。第三に、ＴＲＶユニット１２０は、第３経路であるノード１及びノード５に沿って、加速構造を探索することができる。このとき、ＴＲＶユニット１２０が、第２光線４２１に対する探索を行うとき、ＴＲＶユニット１２０は、第１光線４１１がヒットした三角形４３２を探索する第２経路を優先的に探索する。従って、ＴＲＶユニット１２０が、第１経路または第３経路を探索する過程を省略することができる。
【００３８】
図６は、一実施形態による加速構造を生成する方法について説明するためのフローチャートである。図６を参照すれば、加速構造生成装置２００は、オーバーラップされるノードが表示された加速構造を生成することができる。
【００３９】
段階６１０において、加速構造生成装置２００は、ノードをルートノード（root  node）に設定する。
【００４０】
段階６２０において、加速構造生成装置２００は、ノードの子ノード（child  node）がオーバーラップされるか否かを判断する。子ノードは、ノードの最近接下位ノードを示す。ノードがオーバーラップされるということは、ノードが示すバウンディングボックスが互いにオーバーラップされるということを意味する。もしノードの子ノードがオーバーラップされれば、段階６３０に進み、そうではなければ、段階６４０に進む。
【００４１】
段階６３０において、加速構造生成装置２００は、ノードのオーバーラップフラグ（overlap  flag）を０に設定する。オーバーラップフラグが０に設定されたノードは、オーバーラップされた子ノードを含む。
【００４２】
段階６４０において、加速構造生成装置２００は、ノードのオーバーラップフラグを１に設定する。オーバーラップフラグが１に設定されたノードは、オーバーラップされていない子ノードを含む。
【００４３】
段階６５０において、加速構造生成装置２００は、ノードを次のノードに設定する。加速構造生成装置２００は、全てのノードに対して、順次に段階６２０ないし段階６５０を遂行する。
【００４４】
段階６６０において、加速構造生成装置２００は、ノードが最後のノードであるか否かを判断する。もしノードが最後のノードであるならば、加速構造の生成を終了する。そうではなければ、段階６２０に進む。
【００４５】
図７は、オブジェクトをバウンディングボックスに分割することについて説明するための図面である。図７を参照すれば、バウンディングボックスROOTは、最上位バウンディングボックスを示す。バウンディングボックスROOTは、全てのバウンディングボックスを含み、最近接下位バウンディングボックスにおいて、バウンディングボックスＲ１及びバウンディングボックスＬ１を含む。バウンディングボックスＲ１及びバウンディングボックスＬ１は、オーバーラップされていないので、バウンディングボックスROOTを示すノードのオーバーラップフラグは、１に設定される。
【００４６】
バウンディングボックスＬ１は、バウンディングボックスＲ２及びバウンディングボックスＬ２を含む。バウンディングボックスＲ２及びバウンディングボックスＬ２は、オーバーラップされていないので、バウンディングボックスＬ１を示すノードのオーバーラップフラグは、１に設定される。
【００４７】
バウンディングボックスＬ２は、バウンディングボックスＲ４及びＬ４を含む。バウンディングボックスＲ４及びＬ４は、互いにオーバーラップされるので、バウンディングボックスＬ２を示すノードのオーバーラップフラグは、０に設定される。
【００４８】
バウンディングボックスＲ１は、バウンディングボックスＲ３及びバウンディングボックスＬ３を含む。バウンディングボックスＲ３及びバウンディングボックスＬ３は、オーバーラップされていないので、バウンディングボックスＲ１を示すノードのオーバーラップフラグは、１に設定される。
【００４９】
バウンディングボックスは、三次元空間に位置したオブジェクトを含む六面体でもある。ＢＶＨを利用して空間を分割する方法を利用すれば、図７のように、バウンディングボックスの間に、オーバーラップが発生しうる。
【００５０】
加速構造生成装置２００は、バウンディングボックスのオーバーラップが表示（mark）された加速構造を生成することができる。
【００５１】
図８は、一実施形態による加速構造について説明するための図面である。図８を参照すれば、加速構造生成装置２００は、オーバーラップの有無が表示された加速構造を生成することができる。図８の加速構造は、図７のバウンディングボックスの関係を示し、加速構造は、各ノードごとに、オーバーラップフラグを含む。オーバーラップフラグは、各ノードの左側に数字で表示されている。
【００５２】
ノードＲはROOTノードを示し、図７のバウンディングボックスROOTを示す。ノードＲは、最上位ノードであり、子ノードＲ１及び子ノードＬ１を含む。ノードＲ１及びノードＬ１がオーバーラップされていないので、ノードＲのオーバーラップフラグは、１である。
【００５３】
ノードＬ１は、子ノードＲ２及び子ノードＬ２を含む。ノードＲ２及びノードＬ２は、オーバーラップされていないので、ノードＬ１のオーバーラップフラグは、１である。
【００５４】
ノードＬ２は、子ノードＲ４及び子ノードＬ４を含む。ノードＲ４及びノードＬ４は、互いにオーバーラップされるので、ノードＬ２のオーバーラップフラグは、０である。加速構造生成装置２００は、ノードＬ２のオーバーラップフラグを０に設定し、子ノードが互いにオーバーラップされるということを表示する。
【００５５】
ノードＲ１は、子ノードＲ３及び子ノードＬ３を含む。ノードＲ３及びノードＬ３は、オーバーラップされていないので、ノードＲ１のオーバーラップフラグは、１である。
【００５６】
図９は、一実施形態による加速構造探索方法について説明するためのフローチャートである。図９を参照すれば、レイトレーシング・コア１００は、ノードのオーバーラップの有無を参照し、加速構造を探索することができる。
【００５７】
段階９１０において、レイトレーシング・コア１００は、加速構造において、光線データと交差するリーフノードを探索する。リーフノードは、ツリー形態の加速構造において、最下位ノードを示す。レイトレーシング・コア１００は、交差されたリーフノードに属したオブジェクトのうち、光線データと交差されたオブジェクトを探索することもできる。
【００５８】
レイトレーシング・コア１００は、ルートノードからリーフノードに、経路に沿って順次に探索する。レイトレーシング・コア１００は、ツリー形態の加速構造を探索するとき、近接ノード（near  node）から探索し、ファーノード（far  node）については、スタックにプッシュ（push）し、近接ノードを探索した後、ファーノードを探索する。
【００５９】
段階９２０において、レイトレーシング・コア１００は、交差されたリーフノードの上位ノードのうち、オーバーラップされる子ノードを含むノードがあるか否かを判断する。言い替えれば、レイトレーシング・コア１００は、探索されたノードのうち、オーバーラップフラグが０に設定されているノードがあるか否かを検索する。オーバーラップフラグが０に設定されたノードは、オーバーラップされた子ノードを含む。探索されたノードのうち、オーバーラップフラグが０に設定されているノードがあれば、段階９３０に進み、そうではなく、探索された経路のノードが、いずれもオーバーラップフラグが１に設定されており、最終リーフノードに属したオブジェクトのうち、光線と交差したオブジェクトがあるならば、該視点での加速構造探索を早期に終了する。
【００６０】
段階９３０において、レイトレーシング・コア１００は、オーバーラップされる子ノードをさらに探索する。レイトレーシング・コア１００は、交差されたリーフノードを探索する過程で探索されていない子ノードに対しても、さらに探索を行う。
【００６１】
図１０は、探索過程について説明するための図面である。第１光線データ１０００は、三次元空間上で、バウンディングボックス及びオブジェクトと交差する。図１０の場合、第１光線データ１０００は、バウンディングボックスROOT、バウンディングボックスＬ１、バウンディングボックスＲ１、バウンディングボックスＲ２、バウンディングボックスＬ３と交差する。また、第１光線データ１０００は、オブジェクトＤ及びオブジェクトＩと交差する。
【００６２】
図１１は、一実施形態による加速構造を探索する方法について説明するための図面である。図１１を参照すれば、レイトレーシング・コア１００は、オーバーラップフラグを参照し、加速構造の探索を早期に終了することができる。図１１のノードは、図１０のバウンディングボックスを示す。
【００６３】
レイトレーシング・コア１００は、ルートノードＲと、第１光線データ１０００との交差の有無を判断する。レイトレーシング・コア１００は、バウンディングボックスROOTと、第１光線データ１０００との交差の有無を判断し、ルートノードＲと、第１光線データ１０００との交差の有無を判断することができる。図１０を参照すれば、バウンディングボックスROOTと第１光線データ１０００は、交差する。
【００６４】
ルートノードの子ノードＲ１，Ｌ１がオーバーラップしていないので、ルートノードのオーバーラップフラグは、１に設定される。レイトレーシング・コア１００は、ルートノードからの近接ノードであるノードＬ１に探索を進める。レイトレーシング・コア１００は、ノードＲ１をスタックにプッシュして保存する。その後、レイトレーシング・コア１００は、スタックに保存されたノードＲ１をポップ（pop）し、ノードＲ１に対する探索を行う。スタックに保存されたノードＲ１をポップするということは、スタックに保存されたデータを読み取って削除するということを意味する。言い替えれば、スタックにおいてデータが削除されるが、データ処理ユニットは、データを受信して処理する。
【００６５】
レイトレーシング・コア１００は、ノードＬ１と、第１光線データ１０００との交差の有無を判断する。レイトレーシング・コア１００は、バウンディングボックスＬ１と、第１光線データ１０００との交差の有無を判断し、ノードＬ１と、第１光線データ１０００との交差の有無を判断することができる。図１０を参照すれば、バウンディングボックスＬ１と第１光線データ１０００は、交差する。
【００６６】
ノードＬ１の子ノードＲ２，Ｌ２がオーバーラップしていないので、ノードＬ１のオーバーラップフラグは、１に設定される。レイトレーシング・コア１００は、ノードＬ１からの近接ノードであるノードＲ２に探索を進める。レイトレーシング・コア１００は、ノードＬ２をスタックにプッシュして保存する。その後、レイトレーシング・コア１００は、スタックに保存されたノードＬ２をポップし、ノードＬ２に対する探索を行う。
【００６７】
レイトレーシング・コア１００は、ノードＲ２と、第１光線データ１０００との交差の有無を判断する。レイトレーシング・コア１００は、バウンディングボックスＲ２と、第１光線データ１０００との交差の有無を判断し、ノードＲ２と、第１光線データ１０００との交差の有無を判断することができる。
【００６８】
レイトレーシング・コア１００は、オブジェクトＡ及びオブジェクトＤと、第１光線データ１０００との交差の有無を判断する。図１０を参照すれば、オブジェクトＤと、第１光線データ１０００は、交差する。
【００６９】
レイトレーシング・コア１００は、交差されたリーフノードＲ２及び交差されたオブジェクトＤを探索したので、上位ノードのうちオーバーラップされる子ノードを含むノードがあるか否かを判断する。リーフノードＲ２の上位ノードは、ノードＲ及びノードＬ１である。レイトレーシング・コア１００は、オーバーラップフラグが０であるノードを検索することにより、オーバーラップされる子ノードを含むノードを検索することができる。ノードＲ及びノードＬ１のオーバーラップフラグは、いずれも１であるので、リーフノードＲ２の上位ノードのうちには、オーバーラップされる子ノードを含むノードはない。従って、レイトレーシング・コア１００は、それ以上ノードを探索せず、第１光線データ１０００に対する探索を終了することができる。レイトレーシング・コア１００は、第１光線データ１０００に対する探索を終了するとき、スタックに保存されたノードをポップするが、探索は行わない。
【００７０】
図１２は、探索過程について説明するための図面である。第２光線データ１２００は、三次元空間上で、バウンディングボックス及びオブジェクトと交差する。図１２の場合、第２光線データ１２００は、バウンディングボックスROOT、バウンディングボックスＬ１、バウンディングボックスＲ１、バウンディングボックスＲ３、バウンディングボックスＲ４、バウンディングボックスＬ２及びバウンディングボックスＬ４と交差する。また、第２光線データ１２００は、オブジェクトＥと交差する。
【００７１】
図１３は、一実施形態による加速構造を探索する方法について説明するための図面である。図１３を参照すれば、レイトレーシング・コア１００は、オーバーラップフラグを参照し、オーバーラップされたノードをさらに探索することができる。図１３のノードは、図１２のバウンディングボックスを示す。
【００７２】
レイトレーシング・コア１００は、ルートノードＲ、ノードＬ１、ノードＬ２を経て、リーフノードＲ４と、第２光線データ１２００との交差の有無を判断する。探索されていないノードは、スタックに保存される。第２光線データ１２００は、ルートノードＲ、ノードＬ１、ノードＬ２及びノードＲ４といずれも交差する。レイトレーシング・コア１００は、リーフノードＲ４に属したオブジェクトＣ及びオブジェクトＥと、第２光線データ１２００との交差の有無を検討する。第２光線データ１２００は、オブジェクトＥと交差する。
【００７３】
レイトレーシング・コア１００は、交差されたリーフノードＲ４の上位ノードのうち、オーバーラップされる子ノードを含むノードを探索する。レイトレーシング・コア１００は、リーフノードＲ４の上位ノードのオーバーラップフラグを介して、オーバーラップの有無を判断することができる。リーフノードＲ４の上位ノードは、ノードＬ２、ノードＬ１、ノードＲである。上位ノードのうち、ノードＬ２のオーバーラップフラグが０であるので、ノードＬ２の子ノードＲ４及びＬ４がオーバーラップされる。従って、レイトレーシング・コア１００は、リーフノードＬ４と、第２光線データ１２００との交差の有無を判断する。第２光線データ１２００と、バウンディングボックスＬ４は、交差するが、第２光線データ１２００と、オブジェクトＢは、交差しない。それ以上オーバーラップされたノードはないので、レイトレーシング・コア１００は、探索を終了する。
【００７４】
レイトレーシング・コア１００は、各ノードのオーバーラップフラグを介して、さらに探索するノードがあるか否かを判断することができ、さらに探索するノードがなかったりするか、あるいはさらに探索するノードをいずれも探索したりした後、第２光線データ１２００に対する探索を終了することができる。
【００７５】
図１４は、一実施形態による加速構造生成装置及びレイトレーシング・コアについて説明するための構成図である。図１４を参照すれば、加速構造生成装置２００は、加速構造生成部２１０及びオーバーラップ表示部２２０を含む。
【００７６】
加速構造生成部２１０は、三次元空間に含まれたオブジェクトをバウンディングボックスに区分し、ノードを利用して、バウンディングボックスの包含関係を示す加速構造を生成する。オブジェクトをバウンディングボックスに区分するということは、少なくとも１つのオブジェクトを含むバウンディングボックスを生成し、少なくとも１つのバウンディングボックスを含む上位バウンディングボックスを生成するということを意味する。バウンディングボックスは、六面体の形態に生成されてもよい。加速構造は、バウンディングボックスの包含関係をツリー形態に示したものを意味する。
【００７７】
オーバーラップ表示部２２０は、ノードのうちオーバーラップされるノードを表示(mark)する。オーバーラップ表示部２２０は、生成された加速構造の各ノードに対して、フラグをさらに付与する。オーバーラップ表示部２２０は、ノードの子ノードがオーバーラップされるか否かをフラグに表示する。言い替えれば、オーバーラップ表示部２２０は、オーバーラップされるバウンディングボックスを示すノードの最近接上位ノードに、オーバーラップ情報を表示する。
【００７８】
レイトレーシング・コア１００は、ＴＲＶユニット１２０を含み、ＴＲＶユニット１２０は、スタックを含む。
【００７９】
ＴＲＶユニット１２０は、加速構造において、光線データと交差するリーフノードを探索し、交差されたリーフノードの上位ノードのうちオーバーラップされる子ノードを含むノードがなければ、探索を終了し、オーバーラップされる子ノードを含むノードがあれば、オーバーラップされる子ノードをさらに探索する。
【００８０】
ＴＲＶユニット１２０は、ノードのオーバーラップフラグを介して、ノードがオーバーラップされる子ノードを含むか否かを確認することができる。、
ＴＲＶユニット１２０は、オーバーラップされる子ノードをさらに探索するとき、スタック１２１に保存されたノードを順次にポップし、オーバーラップされる子ノードをさらに探索することができる。ＴＲＶユニット１２０は、スタック１２１からポップされるノードのうちオーバーラップされるノードではないノードは、探索しない。言い替えれば、ＴＲＶユニット１２０が交差されたリーフノードを求めた後、スタック１２１からポップされるノードのうちオーバーラップされるノードではないノードに対しては、探索せずに探索を早期に終了する。
【００８１】
ＴＲＶユニット１２０は、探索されていないノードをスタック１２１にプッシュして保存する。ＴＲＶユニット１２０は、ツリー形態の加速構造を探索するとき、第１経路を選択することによって探索されていない第２経路のノードをスタック１２１に保存する。第１経路のノードに対する探索結果、及び第１経路のノードのオーバーラップの有無により、ＴＲＶユニット１２０は、スタック１２１に保存されたノードに対してさらに探索したり、あるいは探索を終了することができる。
【００８２】
スタック１２１は、ノードを保存する。スタック１２１は、ＴＲＶユニット１２０の要請により、ノードを保存したり、あるいは保存されたノードを出力する。スタック１２１がノードを保存するということは、ノードに該当するデータを保存するということを意味する。ノードは、各ノードに対応するバウンディングボックスに関するデータを含む。
【００８３】
一方、前述の方法は、コンピュータで実行されるプログラムで作成可能であり、コンピュータで読み取り可能な記録媒体を利用して、前記プログラムを動作させる汎用デジタルコンピュータで具現されてもよい。また、前述の方法で使用されたデータの構造は、コンピュータで読み取り可能な記録媒体に多くの手段を介して記録される。前記コンピュータで読み取り可能な記録媒体は、マグネチック記録媒体（例えば、ＲＯＭ（read  only  memory）、ＲＡＭ（random  access  memory）、ＵＳＢ（universal  serial  bus）、フロッピー（登録商標）ディスク、ハードディスクなど）、光学的判読媒体（例えば、ＣＤ（compact  disc）−ＲＯＭ、ＤＶＤ（digital  versatile  disc）など）を含む。
【産業上の利用可能性】
【００８４】
本発明の加速構造の生成及び探索を行う方法は、例えば、映像処理関連の技術分野に効果的に適用可能である。
【符号の説明】
【００８５】
１０        視点
２０        画面
３０        一次光線
４０        反射光線
５０        屈折光線
６０        シャドー光線
７０        シーンオブジェクト
１００      レイトレーシング・コア
１１０      光線生成ユニット
１２０      ＴＲＶユニット
１２１      スタック
１３０      ＩＳＴユニット
１４０      シェーディング・ユニット
２００      加速構造生成装置
２１０      加速構造生成部
２２０      オーバーラップ表示部
２５０      外部メモリ
２５１      加速構造
２５２      幾何データ
４１０      第１視点
４１１      第１光線
４１２      第１画面
４２０      第２視点
４２１      第２光線
４２２      第２画面
４３１      四角形
４３２      三角形
４３３      ウサギ
１０００    第１光線データ
１２００    第２光線データ
【図１】
0006476090.tif 000002
【図２】
0006476090.tif 000003
【図３】
0006476090.tif 000004
【図４】
0006476090.tif 000005
【図５】
0006476090.tif 000006
【図６】
0006476090.tif 000007
【図７】
0006476090.tif 000008
【図８】
0006476090.tif 000009
【図９】
0006476090.tif 000010
【図１０】
0006476090.tif 000011
【図１１】
0006476090.tif 000012
【図１２】
0006476090.tif 000013
【図１３】
0006476090.tif 000014
【図１４】
0006476090.tif 000015