(57)【要約】【課題】  加速構造を生成する方法及びその装置を提供する。【解決手段】  三次元空間に含まれた複数のプリミティブそれぞれの位置を示す線形コードを生成し、生成された線形コードにより、複数のプリミティブを整列し、整列された複数のプリミティブを順次にバウンディングボックスに入力しながら、バウンディングボックスのサイズ変化比率を決定し、バウンディングボックスのサイズ変化比率を基に、整列された複数のプリミティブのうちいずれか一つを選択し、選択されたプリミティブを基準に、整列された複数のプリミティブを複数のバウンディングボックスに区分する光線追跡に使用される加速構造を生成する方法。【選択図】      図７
2018073427.tif 000002
【特許請求の範囲】
【請求項１】
光線追跡に使用される加速構造を生成する方法において、
三次元空間に含まれた複数のプリミティブそれぞれの位置を示す線形コードを生成する段階と、
前記生成された線形コードにより、前記複数のプリミティブを整列させる段階と、
前記整列された複数のプリミティブを順次にバウンディングボックスに入力し、かつ、前記バウンディングボックスのサイズ変化比率を決定する段階と、
前記バウンディングボックスのサイズ変化比率を基に、前記整列された複数のプリミティブのうちいずれか一つを選択する段階と、
前記選択されたプリミティブを基準に、前記整列された複数のプリミティブを複数のバウンディングボックスに区分する段階と、
を含む方法。
【請求項２】
前記決定する段階は、
前記整列された複数のプリミティブのうち第１プリミティブが含まれたバウンディングボックスに、前記第１プリミティブの次の順に整列された第２プリミティブを入力する段階と、
前記第１プリミティブが含まれたバウンディングボックスに対する、前記第１プリミティブ及び前記第２プリミティブが含まれたバウンディングボックスの変化比率を決定する段階と、を含む
ことを特徴とする請求項１に記載の方法。
【請求項３】
前記選択する段階は、
前記整列された複数のプリミティブのうち、前記バウンディングボックスの変化比率が最大であるプリミティブを選択する、
ことを特徴とする請求項１に記載の方法。
【請求項４】
前記複数のプリミティブそれぞれの位置は、
前記三次元空間での前記複数のプリミティブそれぞれの中心の座標情報を基に決定される、
ことを特徴とする請求項１に記載の方法。
【請求項５】
前記区分する段階は、
前記整列された複数のプリミティブを、前記選択されたプリミティブの前の順に整列された少なくとも１つのプリミティブ、及び前記選択されたプリミティブが含まれた第１バウンディングボックスと、前記選択されたプリミティブの次の順に整列された少なくとも１つのプリミティブが含まれた第２バウンディングボックスと、に区分する、
ことを特徴とする請求項１に記載の方法。
【請求項６】
前記第１バウンディングボックスに対応する第１ノード、及び前記第２バウンディングボックスに対応する第２ノードを生成する段階と、
前記第１ノード及び前記第２ノードを、前記加速構造の子ノードとして追加する段階と、をさらに含む、
ことを特徴とする請求項５に記載の方法。
【請求項７】
前記複数のプリミティブの整列順によって加重値を設定する段階をさらに含み、
前記選択する段階は、
前記設定された加重値、及び前記バウンディングボックスのサイズ変化比率を基に、前記整列された複数のプリミティブのうちいずれか一つを選択する、
ことを特徴とする請求項１に記載の方法。
【請求項８】
前記加重値は、
前記複数のプリミティブそれぞれの整列順序が、前記整列順序の中心から遠くなるほど低く設定される、
ことを特徴とする請求項７に記載の方法。
【請求項９】
前記線形コードは、
モートンコードを含む、
ことを特徴とする請求項１に記載の方法。
【請求項１０】
前記バウンディングボックスのサイズ変化比率は、前記バウンディングボックスの表面積の変化である、
ことを特徴とする請求項１に記載の方法。
【請求項１１】
光線追跡に使用される加速構造を生成する装置において、
三次元空間に含まれた複数のプリミティブそれぞれの位置に関する情報及び前記加速構造を保存するメモリと、
前記複数のプリミティブそれぞれの位置に関する情報を基に、生成された線形コードにより、前記複数のプリミティブを整列させ、前記整列された複数のプリミティブを順次にバウンディングボックスに入力し、かつ、前記バウンディングボックスのサイズ変化比率を決定し、前記バウンディングボックスのサイズ変化比率を基に、前記整列された複数のプリミティブのうちいずれか一つを選択し、前記選択されたプリミティブを基準に、前記整列された複数のプリミティブを複数のバウンディングボックスに区分するプロセッサと、
を含む装置。
【請求項１２】
前記プロセッサは、
前記整列された複数のプリミティブのうち第１プリミティブが含まれたバウンディングボックスに、前記第１プリミティブの次の順に整列された第２プリミティブを入力し、前記第１プリミティブが含まれたバウンディングボックスに対する、前記第１プリミティブ及び前記第２プリミティブが含まれたバウンディングボックスの変化比率を決定する、
ことを特徴とする請求項１１に記載の装置。
【請求項１３】
前記プロセッサは、
前記整列された複数のプリミティブのうち、前記バウンディングボックスの変化比率が最大であるプリミティブを選択する、
ことを特徴とする請求項１１に記載の装置。
【請求項１４】
前記複数のプリミティブそれぞれの位置は、
前記三次元空間での前記複数のプリミティブそれぞれの中心の座標情報を基に決定される、
ことを特徴とする請求項１１に記載の装置。
【請求項１５】
前記プロセッサは、
前記整列された複数のプリミティブを、前記選択されたプリミティブの前の順に整列された少なくとも１つのプリミティブ、及び前記選択されたプリミティブが含まれた第１バウンディングボックスと、前記選択されたプリミティブの次の順に整列された少なくとも１つのプリミティブが含まれた第２バウンディングボックスと、に区分する、
ことを特徴とする請求項１１に記載の装置。
【請求項１６】
前記プロセッサは、
前記第１バウンディングボックスに対応する第１ノード、及び前記第２バウンディングボックスに対応する第２ノードを生成し、前記第１ノード及び前記第２ノードを、前記加速構造の子ノードとして追加する、
ことを特徴とする請求項１５に記載の装置。
【請求項１７】
前記プロセッサは、
前記複数のプリミティブの整列順によって加重値を設定し、前記設定された加重値、及び前記バウンディングボックスのサイズ変化比率を基に、前記整列された複数のプリミティブのうちいずれか一つを選択する、
ことを特徴とする請求項１１に記載の装置。
【請求項１８】
前記加重値は、
前記複数のプリミティブそれぞれの整列順序が、前記整列順序の中心から遠くなるほど低く設定される、
ことを特徴とする請求項１７に記載の装置。
【請求項１９】
前記線形コードは、
モートンコードを含む、
ことを特徴とする請求項１１に記載の装置。
【請求項２０】
請求項１ないし１０のうちいずれか１項に記載の方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、光線追跡に使用される加速構造を生成する方法及びその装置に関する。
【背景技術】
【０００２】
三次元（３Ｄ：3-dimensional）レンダリングは、三次元客体データを与えられたカメラの視点（view  point）から見える映像に合成（synthesis）する映像処理過程（process）である。三次元レンダリング時、客体を、さらに臨場感あるように表現するために、既定の光源から出た光線が、物体で反射する様子を基に、客体に関するデータを決定する光線追跡方法が使用される。
【０００３】
該光線追跡方法においては、レンダリングの対象になる客体と光線とが交差する地点を追跡するために、客体を空間的に区分した加速構造（acceleration  structure）を生成し、生成された加速構造を探索し、光線とプリミティブとの交差（ray-primitive  intersection）いかんを確認することができる。一方、光線追跡方法での探索と交差検査との過程は、客体で反射した全ての光線を追跡することにより、多くの演算量（computation）及び広いメモリ帯域幅（memory  bandwidth）を必要とする。そのため、光線追跡方法での探索と交差検査との過程をさらに効率的に遂行するための加速構造を生成する方法が持続的に研究されている。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明が解決しようとする課題は、光線追跡に使用される加速構造を生成する方法及びその装置において、加速構造の品質を維持しながら、迅速に加速構造を生成することができる方法及びその装置を提供することである。
【課題を解決するための手段】
【０００５】
一実施形態による、光線追跡に使用される加速構造を生成する方法は、三次元空間に含まれた複数のプリミティブそれぞれの位置を示す線形コードを生成させる段階と、生成された線形コードにより、複数のプリミティブを整列する段階と、整列された複数のプリミティブを順次にバウンディングボックスに入力し、かつ、バウンディングボックスのサイズ変化比率を決定する段階と、バウンディングボックスのサイズ変化比率を基に、整列された複数のプリミティブのうちいずれか一つを選択する段階と、選択されたプリミティブを基準に、整列された複数のプリミティブを複数のバウンディングボックスに区分する段階と、を含む。
【０００６】
また、決定する段階は、整列された複数のプリミティブのうち第１プリミティブが含まれたバウンディングボックスに、第１プリミティブの次の順に整列された第２プリミティブを入力する段階と、第１プリミティブが含まれたバウンディングボックスに対する、第１プリミティブ及び前記第２プリミティブが含まれたバウンディングボックスの変化比率を決定する段階と、を含む。
【０００７】
また、選択する段階は、整列された複数のプリミティブのうちバウンディングボックスの変化比率が最大であるプリミティブを選択する。
【０００８】
また、複数のプリミティブそれぞれの位置は、三次元空間での複数のプリミティブそれぞれの中心の座標情報を基に決定される。
【０００９】
また、区分する段階は、整列された複数のプリミティブを、選択されたプリミティブの前の順に整列された少なくとも１つのプリミティブ、及び選択されたプリミティブが含まれた第１バウンディングボックスと、選択されたプリミティブの次の順に整列された少なくとも１つのプリミティブが含まれた第２バウンディングボックスと、に区分する。
【００１０】
また、光線追跡に使用される加速構造を生成する方法は、第１バウンディングボックスに対応する第１ノード、及び第２バウンディングボックスに対応する第２ノードを生成する段階と、第１ノード及び第２ノードを加速構造の子ノードとして追加する段階をさらに含む。
【００１１】
また、光線追跡に使用される加速構造を生成する方法は、複数のプリミティブの整列順によって加重値を設定する段階をさらに含み、選択する段階は、設定された加重値、及びバウンディングボックスのサイズ変化比率を基に、整列された複数のプリミティブのうちいずれか一つを選択する。
【００１２】
また、該加重値は、複数のプリミティブそれぞれの整列順序が、整列順序の中心から遠くなるほど低く設定される。
【００１３】
また、該線形コードは、モートンコードを含む。
【００１４】
一実施形態による光線追跡に使用される加速構造を生成する装置は、三次元空間に含まれた複数のプリミティブそれぞれの位置に関する情報及び加速構造を保存するメモリと、複数のプリミティブそれぞれの位置に関する情報を基に、生成された線形コードにより、複数のプリミティブを整列させ、整列された複数のプリミティブを順次にバウンディングボックスに入力し、かつ、バウンディングボックスのサイズ変化比率を決定し、バウンディングボックスのサイズ変化比率を基に、整列された複数のプリミティブのうちいずれか一つを選択し、選択されたプリミティブを基準に、整列された複数のプリミティブを複数のバウンディングボックスに区分するプロセッサと、を含む。
【００１５】
また、該プロセッサは、整列された複数のプリミティブのうち第１プリミティブが含まれたバウンディングボックスに、第１プリミティブの次の順に整列された第２プリミティブを入力し、第１プリミティブが含まれたバウンディングボックスに対する、第１プリミティブ及び前記第２プリミティブが含まれたバウンディングボックスの変化比率を決定する。
【００１６】
また、該プロセッサは、整列された複数のプリミティブのうちバウンディングボックスの変化比率が最大であるプリミティブを選択する。
【００１７】
また、複数のプリミティブそれぞれの位置は、三次元空間での前記複数のプリミティブそれぞれの中心の座標情報を基に決定される。
【００１８】
また、該プロセッサは、整列された複数のプリミティブを、選択されたプリミティブの前の順に整列された少なくとも１つのプリミティブ、及び選択されたプリミティブが含まれた第１バウンディングボックスと、選択されたプリミティブの次の順に整列された少なくとも１つのプリミティブが含まれた第２バウンディングボックスと、に区分する。
【００１９】
また、該プロセッサは、第１バウンディングボックスに対応する第１ノード、及び第２バウンディングボックスに対応する第２ノードを生成し、第１ノード及び第２ノードを加速構造の子ノードとして追加する。
【００２０】
また、該プロセッサは、複数のプリミティブの整列順によって加重値を設定し、設定された加重値、及びバウンディングボックスのサイズ変化比率を基に、整列された複数のプリミティブのうちいずれか一つを選択する。
【００２１】
また、該加重値は、複数のプリミティブそれぞれの整列順序が、整列順序の中心から遠くなるほど低く設定される。
【００２２】
また、該線形コードは、モートンコードを含む。
【００２３】
一実施形態による加速構造生成方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読取り可能な記録媒体が提供される。
【図面の簡単な説明】
【００２４】
【図１】光線追跡について説明するための図面である。
【図２】レイトレーシングコアについて説明するための図面である。
【図３】レイトレーシングコアが光線追跡を行う動作について説明するための図面である。
【図４】光線追跡を加速させるための方法について説明するための図面である。
【図５】図４の光線追跡を加速させるための方法について説明するための図面である。
【図６】一実施形態による、加速構造生成装置について説明するためのブロック図である。
【図７】一実施形態による、加速構造を生成する方法を示したフローチャートである。
【図８】一実施形態による、モートンコードを生成する方法について説明するための図面である。
【図９】一実施形態による、加速構造生成装置が、複数のプリミティブを、線形コードによって整列させる方法について説明するための図面である。
【図１０】一実施形態による、加速構造生成装置が、整列された複数のプリミティブのうちバウンディングボックスのサイズ変化比率が最大であるプリミティブを選択する方法について説明するための図面である。
【図１１】一実施形態による、加速構造生成装置が、複数のプリミティブそれぞれに設定された加重値を利用して、複数のプリミティブをバウンディングボックスに区分する方法について説明するためのフローチャートである。
【図１２】一実施形態による、加速構造生成装置が、複数のプリミティブそれぞれに設定された加重値を利用して、複数のプリミティブをバウンディングボックスに区分する方法について説明するための図面である。
【発明を実施するための形態】
【００２５】
以下では、図面を参照し、実施形態について詳細に説明する。
【００２６】
図１は、光線追跡について説明するための図面である。図１を参照すれば、三次元モデリングにおいて、レイトレーシングコア（ray  tracing  core）は、視点（view  point）１０を決定し、視点によって、画面（image）２０を決定する。視点１０と画面２０とが決定されれば、レイトレーシングコアは、視点１０から、画面２０の各ピクセル（pixel）に対して光線を生成する。
【００２７】
図１の構成について説明すれば、視点１０から一次光線（primary  ray）３０が生成される。一次光線３０は、画面２０を経て、シーンオブジェクト（scene  object）７０と交差する。一次光線３０とシーンオブジェクト７０との交差点では、反射光線（reflection  ray）４０及び屈折光線（refraction  ray）５０が生成される。また、交差点において、光源８０の方向にシャドー光線（shadow  ray）６０が生成される。このとき、反射光線４０、屈折光線５０、シャドー光線６０を二次光線という。シーンオブジェクト７０は、画面２０に関するレンダリングの対象になるオブジェクトを示す。シーンオブジェクト７０は、複数のプリミティブを含む。
【００２８】
レイトレーシングコアは、一次光線３０、二次光線（反射光線４０、屈折光線５０、シャドー光線６０）、及び二次光線から派生される光線を分析する。レイトレーシングコアは、分析結果に基づいて、画面２０を構成するピクセルの色相値を決定する。このとき、該レイトレーシングコアは、シーンオブジェクト７０の特性を考慮し、ピクセルの色相値を決定する。
【００２９】
図２は、レイトレーシングコア１００について説明するための図面である。図２を参照すれば、レイトレーシングコア１００は、光線生成ユニット１１０、ＴＲＶ（traversal）ユニット１２０、ＩＳＴ（intersection  test）ユニット１３０及びシェーディングユニット１４０を含む。図２では、ＴＲＶユニット１２０、ＩＳＴユニット１３０がレイトレーシングコア１００に含まれるように図示されているが、ＴＲＶユニット１２０、ＩＳＴユニット１３０は、別途のハードウェアによっても具現される。図２に図示されたレイトレーシングコア１００は、本実施形態に関する構成要素だけが図示されている。従って、図２に図示された構成要素以外に、他の汎用的な構成要素がさらに含まれてもよいということは、本実施形態に関する技術分野における当業者であれば、理解することができるであろう。
【００３０】
レイトレーシングコア１００は、生成された光線と、三次元空間に位置したオブジェクトとの交差点を追跡し、画面を構成するピクセルの色相値を決定する。言い替えれば、レイトレーシングコア１００は、光線とオブジェクトとの交差点を求め、交差点でのオブジェクトの特性によって、二次光線を生成し、交差点の色相の値を決定する。
【００３１】
レイトレーシングコア１００は、加速構造を探索して交差検査を行うとき、以前の探索の結果、及び以前の交差検査の結果を利用することができる。言い換えれば、レイトレーシングコア１００は、以前のレンダリング過程で遂行された結果を、現在のレンダリング過程に適用することにより、現在のレンダリングをさらに迅速に行うことができる。
【００３２】
光線生成ユニット１１０は、一次光線及び二次光線を生成する。光線生成ユニット１１０は、視点から一次光線を生成し、一次光線とオブジェクトとの交差点において、反射、屈折またはシャドーの二次光線を生成する。光線生成ユニット１１０は、また二次光線とオブジェクトとの交差点において、他の二次光線を生成することができる。光線生成ユニット１１０は、決められた回数内において、反射光線、屈折光線、シャドー光線を生成したり、オブジェクトの特性によって、反射光線、屈折光線、シャドー光線の生成回数を決定することができる。
【００３３】
ＴＲＶユニット１２０は、光線生成ユニット１１０から生成された光線に関する情報を受信する。生成された光線は、一次光線、二次光線、及び二次光線によって派生した光線をいずれも含む。例えば、一次光線の場合、ＴＲＶユニット１２０は、生成された光線の視点及び方向に関する情報を受信することができる。また、二次光線の場合、ＴＲＶユニット１２０は、二次光線の出発点及び方向に関する情報を受信することができる。二次光線の出発点は、一次光線がヒット（hit）された地点を示す。視点または出発点は、座標で表現され、方向は、ベクトルによっても表現される。
【００３４】
ＴＲＶユニット１２０は、外部メモリ２５０から、加速構造に関する情報を読み取る（read）。該加速構造は、加速構造生成装置２００によって生成され、生成された加速構造は、外部メモリ２５０に保存される。該加速構造は、三次元空間のオブジェクトの位置情報を含んでいる構造を示す。例えば、該加速構造は、ＫＤ−ｔｒｅｅ（K-dimensional  tree）、ＢＶＨ（bounding  volume  hierarchy）などが適用される。
【００３５】
ＴＲＶユニット１２０は、該加速構造を探索し、光線がヒットされたオブジェクトまたはリーフノード（leaf  node）を出力する。例えば、ＴＲＶユニット１２０は、加速構造に含まれたノードを探索し、該ノードのうち最下位ノードであるリーフノードのうち光線がヒットされたリーフノードをＩＳＴユニット１３０に出力する。言い替えれば、ＴＲＶユニット１２０は、加速構造を構成するバウンディングボックス（bounding  box）のうち、いずれのバウンディングボックスに光線がヒットされたかを判断し、該バウンディングボックスに含まれたオブジェクトのうち、いずれのオブジェクトに光線がヒットされたかを判断する。ヒットされたオブジェクトに関する情報は、ＴＲＶキャッシュに保存される。該バウンディングボックスは、複数のオブジェクトまたはプリミティブを含む単位を示し、加速構造によって、異なる形態にも表現される。ＴＲＶキャッシュは、ＴＲＶユニット１２０が探索過程で使用するデータを一時的に保存するためのメモリを示す。
【００３６】
ＴＲＶユニット１２０は、以前のレンダリングの結果を利用して、加速構造を探索することができる。ＴＲＶユニット１２０は、ＴＲＶキャッシュに保存された以前のレンダリング結果を利用して、以前のレンダリングと同一経路で加速構造を探索することができる。例えば、ＴＲＶユニット１２０が、入力された光線に関する加速構造を探索するとき、ＴＲＶユニット１２０は、入力された光線と同一視点及び同一方向を有する以前の光線がヒットされたバウンディングボックスに対する探索を優先的に行う。また、ＴＲＶユニット１２０は、以前の光線に関する探索経路を参照し、加速構造を探索することができる。
【００３７】
ＩＳＴユニット１３０は、ＴＲＶユニット１２０から、光線がヒットされたオブジェクトまたはリーフノードを受信し、外部メモリ２５０から、ヒットされたオブジェクトに含まれたプリミティブに関する情報を読み取る。読み取られたプリミティブに関する情報は、ＩＳＴキャッシュに保存される。該ＩＳＴキャッシュは、交差検索過程において、ＩＳＴユニット１３０が使用するデータを一時的に保存するためのメモリを示す。
【００３８】
ＩＳＴユニット１３０は、光線とプリミティブとの交差検査を行い、光線がヒットされたプリミティブ及び交差点を出力する。ＴＲＶユニット１２０から、光線がヒットされたオブジェクトが何であるか受信したＩＳＴユニット１３０は、ヒットされたオブジェクトに含まれた複数のプリミティブのうち、いずれのプリミティブに光線がヒットされたかを検査する。光線がヒットされたプリミティブを求めた後、ＩＳＴユニット１３０は、ヒットされたプリミティブのいずれの地点と光線とが交差したかを示す交差点を出力する。該交差点は、座標形態でシェーディングユニット１４０に出力される。
【００３９】
ＩＳＴユニット１３０は、以前のレンダリングの結果を利用して、交差検査を行うことができる。ＩＳＴユニット１３０は、ＩＳＴキャッシュに保存された以前のレンダリングの結果を利用して、以前のレンダリングと同一プリミティブに対して、優先的に交差検査を行う。例えば、入力された光線とプリミティブとに関する交差検査を行うとき、ＩＳＴユニット１３０は、入力された光線と同一視点及び同一方向を有する以前の光線がヒットされたプリミティブに対する交差検査を優先的に行う。
【００４０】
シェーディングユニット１４０は、ＩＳＴユニット１３０から受信された交差点に関する情報及び交差点の物質特性に基づいて、ピクセルの色相値を決定する。シェーディングユニット１４０は、交差点の物質基本色相、及び光源による効果などを考慮し、ピクセルの色相値を決定する。
【００４１】
レイトレーシングコア１００は、外部メモリ２５０から、光線追跡に必要なデータを受信する。外部メモリ２５０には、加速構造生成装置２００によって生成された加速構造、またはプリミティブに関する情報を示す幾何データ（geometry  data）が保存される。該プリミティブは、三角形、四角形などの多角形でもあり、該幾何データは、オブジェクトに含まれたプリミティブの頂点及び位置に関する情報を示すことができる。
【００４２】
加速構造生成装置２００は、三次元空間上のオブジェクトの位置情報を含む加速構造を生成する。加速構造生成装置２００は、さまざまな形態の加速構造を生成することができる。例えば、該加速構造は、三次元空間が、階層的ツリーに分割された形態でもあり、加速構造生成装置２００は、ＢＶＨまたはＫＤ−treeを適用し、三次元空間上のオブジェクトの関係を示す構造を生成することができる。加速構造生成装置２００は、リーフノードの最大プリミティブの数及びツリー深さ（tree  depth）を決定し、該決定に基づいて、加速構造を生成することができる。
【００４３】
図３は、レイトレーシングコアが光線追跡を行う動作について説明するための図面である。該レイトレーシングコアは、例えば、図２に図示されたレイトレーシングコア１００の構造を有することができる。従って、以下で省略された内容であるとしても、レイトレーシングコア１００について、上述された内容は、図３の光線追跡方法にも適用される。
【００４４】
３１０段階において、レイトレーシングコア１００は、光線を生成する。レイトレーシングコア１００は、一次光線、二次光線、及び二次光線によって派生した光線を生成する。
【００４５】
３２０段階において、レイトレーシングコア１００は、外部メモリ２５０から読み取られた加速構造を探索する。レイトレーシングコア１００は、生成された光線の視点及び方向に基づいて加速構造２５１を探索し、光線がヒットされたバウンディングボックスを検出し、ヒットされたバウンディングボックスに含まれるオブジェクトのうち、光線がヒットされたオブジェクトを検出する。段階３２５において、レイトレーシングコア１００は、ヒットされたオブジェクトを検出するまで、加速構造２５１探索を反復して行う。例えば、レイトレーシングコア１００は、いずれか１つの経路に沿って加速構造を探索し、探索された経路上のリーフノードに光線がヒットされない場合に、他の経路で加速構造を探索する。
【００４６】
レイトレーシングコア１００は、全ての経路を順次に探索することができるが、以前の光線探索情報に基づいて、特定経路を優先的に探索することができる。例えば、以前の光線視点と方向とが現在の光線視点及び方向と同一または類似している場合、レイトレーシングコア１００は、以前の光線でヒットされたリーフノードが含まれた経路を優先的に探索することができる。
【００４７】
３３０段階において、レイトレーシングコア１００は、交差検査を行う。レイトレーシングコア１００は、外部メモリ２５０から読み取られたプリミティブの幾何データ２５２に基づいて交差検査を行う。段階３３５において、レイトレーシングコア１００は、ヒットされたプリミティブを検出するまで、交差検査を反復して行う。例えば、レイトレーシングコア１００は、いずれか１つのプリミティブに対する交差検査を行い、プリミティブに光線がヒットされない場合には、他のプリミティブに対する交差検査を行う。
【００４８】
レイトレーシングコア１００は、全てのプリミティブを順次に交差検査することができるが、以前の光線の交差検査情報に基づいて、特定プリミティブを優先的に交差検査することができる。例えば、以前の光線と現在の光線との視点及び方向が同一であるか、あるいは類似している場合、レイトレーシングコア１００は、以前の光線でヒットされたプリミティブに対する交差検査を優先的に行うことができる。
【００４９】
３４０段階において、レイトレーシングコア１００は、交差検査に基づいて、ピクセルのシェーディングを行う。レイトレーシングコア１００は、３４０段階が終了すれば、３１０段階に進む。レイトレーシングコア１００は、３１０段階ないし３４０段階を、画面を構成する全てのピクセルに対して反復に遂行する。
【００５０】
図４は、光線追跡を加速させるための方法について説明するための図面である。図４を参照すれば、第１画面４１２は、ｔ＝０であるとき、レンダリングされた画面を示し、第２画面４２２は、ｔ＝１であるとき、レンダリングされた画面を示す。第１画面４１２と第２画面４２２とにおいて、兎４３３だけが移動し、四角形４３１と三角形４３２は、動きがないから、第１画面４１２と第２画面４２２は、ほぼ類似している。従って、レイトレーシングコア１００は、第１画面４１２に対するレンダリング結果を利用して、第２画面４２２に対するレンダリングを行うことができる。例えば、第１視点４１０と第２視点４２０との位置が同一であり、第１光線４１１と第２光線４２１との方向が同一であれば、レイトレーシングコア１００は、第１光線４１１に対する光線追跡の結果を、第２光線４２１の光線追跡に適用し、第２光線４２１の光線追跡を加速させることができる。例えば、レイトレーシングコア１００のＴＲＶユニット１２０は、第２光線４２１に対する探索を行うとき、第１光線４１１がヒットされたバウンディングボックスを優先的に探索することができる。また、レイトレーシングコア１００のＩＳＴユニット１３０は、第２光線４２１に対する交差検査を行うとき、第１光線４１１がヒットされた三角形４３２に対して、優先的に交差検査を行うことができる。
【００５１】
図５は、図４の光線追跡を加速させるための方法について説明するための図面である。図５を参照すれば、該加速構造は、５個のノード（ノード１ないしノード５）を含み、ノード３ないしノード５は、リーフノードを示す。
【００５２】
ＴＲＶユニット１２０は、３種の経路に沿って加速構造を探索することができる。第一に、ＴＲＶユニット１２０は、第１経路であるノード１、ノード２及びノード３に沿って加速構造を探索することができる。第二に、ＴＲＶユニット１２０は、第２経路であるノード１、ノード２及びノード４に沿って加速構造を探索することができる。第三に、ＴＲＶユニット１２０は、第３経路であるノード１及びノード５に沿って加速構造を探索することができる。このとき、ＴＲＶユニット１２０が第２光線４２１に対する探索を行うとき、ＴＲＶユニット１２０は、第１光線４１１がヒットされた三角形４３２を探索する第２経路を優先的に探索する。従って、ＴＲＶユニット１２０が、第１経路または第３経路を探索する過程を省略することができる。
【００５３】
図６は、一実施形態による加速構造生成装置２００について説明するためのブロック図である。
【００５４】
図６を参照すれば、加速構造生成装置２００は、プロセッサ２１０及びメモリ２２０を含む。ここで、加速構造生成装置２００は、ＧＰＵ（graphics  processing  unit）でもあるが、それは、一つの実施形態であるにすぎず、加速構造生成装置２００は、ＧＰＵに限定されるものではない。
【００５５】
プロセッサ２１０は、三次元空間に含まれたプリミティブの位置を決定する。一実施形態によるプロセッサ２１０は、三次元空間を複数のグリッド（grid）に分割して生成された座標を基に、プリミティブの位置を示すことができる。例えば、プロセッサ２１０は、三次元空間を、ｘ軸、ｙ軸及びｚ軸方向の均一な間隔に分割することができる。ここで、該プリミティブの位置は、プリミティブが含まれたグリッドの位置によって表現される。該プリミティブが複数のグリッドに含まれている場合、プリミティブの位置は、プリミティブの中心点が含まれるグリッドの位置によっても表現される。プリミティブの位置を決定して表現する具体的な方法は、図８で後述する。
【００５６】
一方、プロセッサ２１０は、プリミティブの三次元空間内において、二進数で構成されたｘ軸座標、ｙ軸座標及びｚ軸座標を決定することができる。例えば、プロセッサ２１０は、プリミティブの位置を示すｘ軸座標、ｙ軸座標及びｚ軸座標をそれぞれ二進数に含まれた１つ以上の二進ビットで決定することができる。
【００５７】
プロセッサ２１０は、プリミティブのｘ軸座標を示す二進数に含まれた１つ以上の二進ビット、プリミティブのｙ軸座標を示す二進数に含まれた１つ以上の二進ビット、及びプリミティブのｚ軸座標を示す二進数に含まれた１つ以上の二進ビットを、既定の順によって組み合わせ、線形コードを生成することができる。ここで、該線形コードには、モートン（Morton）コードが含まれてもよい。以下では、説明の便宜上、線形コードに対して、モートンコードを例として挙げて説明する。
【００５８】
プロセッサ２１０は、三次元空間に含まれるプリミティブの分布によって、モートンコードを生成するために、二進ビットを組み合わせる順序を決定することができる。また、プロセッサ２１０は、モートンコード生成に利用されるｘ軸座標、ｙ軸座標及びｚ軸座標の二進ビット数をそれぞれ異なるように設定することができる。
【００５９】
プロセッサ２１０は、生成された線形コードにより、複数のプリミティブを整列させる。例えば、プロセッサ２１０は、生成された線形コードの値の大きさによって、線形コードの値が小さいプリミティブが、線形コードの値が大きいプリミティブの前の順に位置するように、複数のプリミティブを整列させることができる。
【００６０】
また、プロセッサ２１０は、整列された複数のプリミティブを、順次にバウンディングボックスに入力しながら、バウンディングボックスのサイズ変化比率（例えば、増大比率）を決定する。例えば、プロセッサ２１０は、全てのプリミティブが、バウンディングボックスに含まれるまで、整列された複数のプリミティブを順次にバウンディングボックスに入力することができる。プロセッサ２１０は、整列された複数のプリミティブそれぞれが、バウンディングボックスに含まれることによって増大するバウンディングボックスサイズを比較することにより、複数のプリミティブそれぞれに関するバウンディングボックスの大きさの増大比率を決定することができる。例えば、プロセッサ２１０は、第１バウンディングボックスに対して順次に入力されるプリミティブと関連するバウンディングボックスと、第１バウンディングボックスとの大きさ変化を決定することができる。
【００６１】
プロセッサ２１０は、バウンディングボックスサイズの増大比率を基に、整列された複数のプリミティブのうちいずれか一つを選択する。例えば、プロセッサ２１０は、整列された複数のプリミティブのうちバウンディングボックスサイズの増大比率が最大であるプリミティブを選択することができる。ただし、それは、一つの実施形態であるにすぎず、他の例によって、プロセッサ２１０は、バウンディングボックスサイズの増大比率、及び複数のプリミティブそれぞれに対して既定の加重値に基づいて整列された複数のプリミティブのうちいずれか一つを選択することもできる。
【００６２】
プロセッサ２１０は、選択されたプリミティブを基準に、整列された複数のプリミティブを、複数のバウンディングボックスに区分する。また、プロセッサ２１０は、区分されたバウンディングボックスそれぞれに含まれたプリミティブに対して、バウンディングボックスサイズの増大比率を基に、他のバウンディングボックスに区分する過程を反復的に遂行することができる。
【００６３】
また、プロセッサ２１０は、バウンディングボックスの包含関係を示す加速構造を生成することができる。それぞれのバウンディングボックスは、加速構造に含まれたそれぞれのノードに対応する。例えば、プロセッサ２１０は、第１バウンディングボックスに対応する第１ノードを生成し、第２バウンディングボックスに対応する第２ノードを生成することができる。
【００６４】
それぞれのノードは、構造体（struct）、ユニオン（union）、クラス（class）などの資料構造でも構成されるが、それらに制限されるものではない。
【００６５】
プロセッサ２１０は、第１ノード及び第２ノードを、三次元空間に対応する第３ノードの子ノードとして加速構造に追加することができる。
【００６６】
該加速構造において、親ノードに対応するバウンディングボックスは、子ノードに対応するバウンディングボックスを含んでもよい。それぞれのバウンディングボックスは、２つのバウンディングボックスに区分される。従って、一般的に、該加速構造は、二進ツリー形態に生成される。
【００６７】
メモリ２２０は、三次元空間に含まれた複数のプリミティブそれぞれの位置に関する情報、及び加速構造に関する情報を保存することができる。該加速構造に関する情報は、加速構造が示す三次元空間に関する情報を含んでもよい。
【００６８】
図７は、一実施形態による、加速構造を生成する方法を示したフローチャートである。一実施形態による、加速構造を生成する方法は、図６で説明した一実施形態による加速構造生成装置２００を介して遂行され、加速構造生成装置２００の動作と同一動作を遂行することができる。
【００６９】
７１０段階において、加速構造生成装置２００は、三次元空間に含まれた複数のプリミティブそれぞれの位置を示す線形コードを生成する。
【００７０】
一実施形態による加速構造生成装置２００は、三次元空間内での複数のプリミティブそれぞれの位置に関する情報を獲得することができる。ここで、該位置に関する情報には、例えば、複数のプリミティブそれぞれの中心点の座標が含まれてもよい。一方、該位置に関する情報には、他の例によって、複数のプリミティブそれぞれが含まれたグリッドの中心点の座標が含まれてもよい。
【００７１】
また、加速構造生成装置２００は、三次元空間内でのプリミティブの中心点のｘ軸座標、ｙ軸座標及びｚ軸座標を示す線形コードを生成することができる。ここで、該線形コードは、モートンコードを含んでもよい。例えば、加速構造生成装置２００は、ｘ軸座標を示す二進数に含まれた１つ以上の二進ビット、ｙ軸座標を示す二進数に含まれた１つ以上の二進ビット、及びｚ軸座標を示す二進数に含まれた１つ以上の二進ビットを既定の順によって組み合わせ、モートンコードを生成することができる。加速構造生成装置２００がモートンコードを生成する方法については、図８を参照して具体的に説明する。
【００７２】
ただし、それは、一つの実施形態であるにすぎず、本実施形態の線形コードは、モートンコードに限定されるものではない。
【００７３】
段階７２０において、加速構造生成装置２００は、生成された線形コードにより、複数のプリミティブを整列させる。例えば、加速構造生成装置２００は、生成された線形コードの値の大きさによって、線形コードの値が小さいプリミティブが、線形コードの値が大きいプリミティブの前の順に位置するように、複数のプリミティブを整列させることができる。ただし、それは、一つの実施形態であるにすぎず、加速構造生成装置２００が複数のプリミティブを整列させる方法は、上述の例に限定されるものではない。
【００７４】
７３０段階において、加速構造生成装置２００は、整列された複数のプリミティブを、順次にバウンディングボックスに入力しながら、バウンディングボックスサイズの増大比率を決定する。
【００７５】
一実施形態による加速構造生成装置２００は、複数のプリミティブを、整列された順によって、一つずつバウンディングボックスに入力することができる。例えば、加速構造生成装置２００は、整列された複数のプリミティブのうち第１プリミティブを、バウンディングボックスに入力し、第１プリミティブの次の順に整列された第２バウンディングボックスを、第１プリミティブが含まれたバウンディングボックスに追加して入力することができる。
【００７６】
また、加速構造生成装置２００は、整列された複数のプリミティブそれぞれがバウンディングボックスに入力されるたびに、バウンディングボックスサイズを決定することができる。例えば、加速構造生成装置２００は、第１プリミティブが入力されたバウンディングボックスサイズと、第１プリミティブ及び第２プリミティブが入力されたバウンディングボックスサイズとをそれぞれ決定することができる。
【００７７】
一方、加速構造生成装置２００は、バウンディングボックスサイズが決定されることにより、第１プリミティブが含まれたバウンディングボックスサイズと、第１プリミティブ及び第２プリミティブが含まれたバウンディングボックスサイズとを比較することができる。加速構造生成装置２００は、該比較結果に基づいて、第２プリミティブがバウンディングボックスに入力されることによるバウンディングボックスサイズの増大比率を決定することができる。
【００７８】
一実施形態による加速構造生成装置２００は、最終的に全てのプリミティブがバウンディングボックスに含まれるまで、整列された複数のプリミティブを順次にバウンディングボックスに入力することができる。また、加速構造生成装置２００は、整列された複数のプリミティブそれぞれが、バウンディングボックスに入力されることによるバウンディングボックスサイズを比較することにより、複数のプリミティブそれぞれに関するバウンディングボックスサイズの増大比率を決定することができる。
【００７９】
７４０段階において、加速構造生成装置２００は、バウンディングボックスサイズの増大比率を基に、整列された複数のプリミティブのうちいずれか一つを選択する。
【００８０】
一実施形態による加速構造生成装置２００は、整列された複数のプリミティブそれぞれに関するバウンディングボックスの増大比率を比較することができる。また、加速構造生成装置２００は、比較結果に基づいて、整列された複数のプリミティブのうちバウンディングボックスの増大比率が最大であるプリミティブを選択することができる。加速構造生成装置２００は、バウンディングボックスの増大比率が最大であるプリミティブを選択することにより、整列された複数のプリミティブのうち表面積が最大であるプリミティブを選択することができる。
【００８１】
ただし、それは、一つの実施形態であるにすぎず、加速構造生成装置２００は、増大比率、及び複数のプリミティブそれぞれに対して既定の加重値に基づいて整列された複数のプリミティブのうちいずれか一つを選択することができる。それについては、図１１及び図１２を参照し、さらに具体的に説明する。
【００８２】
７５０段階において、加速構造生成装置２００は、選択されたプリミティブを基準に、整列された複数のプリミティブを複数のバウンディングボックスに区分する。
【００８３】
加速構造生成装置２００は、整列された複数のプリミティブを、選択されたプリミティブの前の順に整列された少なくとも１つのプリミティブ、及び選択されたプリミティブが含まれた第１バウンディングボックスと、選択されたプリミティブの次の順に整列された少なくとも１つのプリミティブが含まれた第２バウンディングボックスと、に区分することができる。
【００８４】
また、一実施形態による加速構造生成装置２００は、第１バウンディングボックスに対応する第１ノード、及び第２バウンディングボックスに対応する第２ノードを生成することができる。加速構造生成装置２００は、第１ノード及び第２ノードを三次元空間に対応する第３ノードの子ノードとして加速構造に追加することができる。ここで、第３ノードは、ルートノードでもあり、ルートノードに追加されている子ノードのうち一つであってもよい。
【００８５】
一方、加速構造生成装置２００は、第１バウンディングボックス及び第２バウンディングボックスにそれぞれ含まれたプリミティブを、他のバウンディングボックスに区分することもできる。例えば、第１バウンディングボックスに３個のプリミティブが含まれている場合、加速構造生成装置２００は、３個のプリミティブをそれぞれバウンディングボックスに入力しながら、バウンディングボックスサイズの増大比率が最大であるプリミティブを選択することができる。加速構造生成装置２００は、選択されたプリミティブを基準に、第１バウンディングボックスを、第１ａバウンディングボックス及び第１ｂバウンディングボックスに区分することができる。また、加速構造生成装置２００は、第１ａバウンディングボックス及び第１ｂバウンディングボックスに対応するノードを、第１ノードの子ノードとして加速構造に追加することができる。
【００８６】
加速構造生成装置２００は、前述の７４０段階及び７５０段階を反復的に遂行しながら、整列された複数のプリミティブを、複数のバウンディングボックスに区分することができる。
【００８７】
図８は、一実施形態による、モートンコードを生成する方法について説明するための図面である。説明の便宜のために、三次元空間８００は、二次元に単純化して図示した。
【００８８】
加速構造生成装置２００は、モートンコードを利用して、三次元空間に含まれたプリミティブの位置を線形的に示すことができる。
【００８９】
図８を参照すれば、加速構造生成装置２００は、三次元空間８００のｘ軸及びｙ軸をそれぞれ４個に均一に分割することができる。従って、加速構造生成装置２００は、総１６個のグリッドに分割される。また、加速構造生成装置２００は、ｘ軸及びｙ軸のそれぞれのグリッドに対して二進ビットを割り当て、座標を生成することができる。例えば、加速構造生成装置２００は、ｘ軸の４個のグリッドに対して、それぞれ００、０１、１０、１１の座標を割り当て、ｙ軸の４個のグリッドに対して、それぞれ００、０１、１０、１１の座標を割り当てることができる。
【００９０】
加速構造生成装置２００は、プリミティブが含まれたグリッドの座標を利用して、プリミティブの位置を示すことができる。一方、他の例によって、加速構造生成装置２００は、プリミティブの中心点が含まれたグリッドの座標を利用して、プリミティブの位置を示すことができる。本実施形態においては、加速構造生成装置２００がプリミティブの中心点が含まれたグリッドの座標を利用して、プリミティブの位置を示すものと仮定する。
【００９１】
また、加速構造生成装置２００は、プリミティブが含まれたグリッドの座標情報を組み合わせ、モートンコードを生成することができる。一実施形態によって、プリミティブのｘ軸座標がＸ１Ｘ２と表現され、ｙ軸座標がＹ１Ｙ２と表現された場合、プリミティブのモートンコードは、Ｘ１Ｙ１Ｘ２Ｙ２とも表現される。ここで、Ｘ１、Ｘ２、Ｙ１及びＹ２は、ｘ軸座標及びｙ軸座標を二進数で示した値の各桁数を示す二進ビットでもある。
【００９２】
例えば、第１プリミティブ８１１の場合、ｘ軸座標が００であり、ｙ軸座標が００であるので、Ｘ１＝０、Ｘ２＝０、Ｙ１＝０、Ｙ２＝０である。加速構造生成装置２００は、第１プリミティブ８１１のｘ軸座標である００、及びｙ軸座標である００を組み合わせることにより、第１プリミティブ８１１のモートンコードを００００に生成することができる。
【００９３】
他の例によって、第２プリミティブ８１２の場合、ｘ軸座標が００であり、ｙ軸座標が０１であるので、Ｘ１＝０、Ｘ２＝０、Ｙ１＝０、Ｙ２＝１である。加速構造生成装置２００は、第２プリミティブ８１２のｘ軸座標である００、及びｙ軸座標である０１を組み合わせることにより、第２プリミティブ８１２のモートンコードを０００１に生成することができる。
【００９４】
前述の方法によって、加速構造生成装置２００は、三次元空間８００内に存在する複数のプリミティブそれぞれに対して、モートンコードを生成することができる。それにより、三次元空間８００内に存在する第１プリミティブ８１１ないし第１１プリミティブ８２１には、それぞれ００００、０００１、００１１、０１００、０１１１、１０００、１０００、１０１０、１１００、１１０１、１１１０、１１１１のモートンコードが割り当てられる。
【００９５】
一方、他の実施形態によって、プリミティブのｚ軸座標がＺ１Ｚ２で表現される場合、三次元空間において、プリミティブのモートンコードは、Ｘ１Ｙ１Ｚ１Ｘ２Ｙ２Ｚ２で表現される。Ｚ１及びＺ２は、プリミティブのｚ軸座標を二進数で示した値の各桁数を示す二進ビットでもある。
【００９６】
図９は、一実施形態による加速構造生成装置２００が、複数のプリミティブ８１１−８２１を、線形コードによって整列させる方法について説明するための図面である。
【００９７】
図９を参照すれば、加速構造生成装置２００は、線形コードが割り当てられた複数のプリミティブ８１１−８２１を整列させることができる。例えば、加速構造生成装置２００は、線形コードの値の大きさにより、複数のプリミティブ８１１−８２１を整列することができる。加速構造生成装置２００が、線形コードの値が小さいプリミティブを優先的に整列する場合、図９に図示されているように、複数のプリミティブ８１１−８２１は、第１プリミティブ８１１、第２プリミティブ８１２、第３プリミティブ８１３、第４プリミティブ８１４、第５プリミティブ８１５、第６プリミティブ８１６、第７プリミティブ８１７、第８プリミティブ８１８、第９プリミティブ８１９、第１０プリミティブ８２０及び第１１プリミティブ８２１の順にも整列される。
【００９８】
一方、加速構造生成装置２００は、整列された複数のプリミティブ８１１−８２１を順次にバウンディングボックスに含めながら、整列された複数のプリミティブ８１１−８２１を、複数のバウンディングボックスに区分するための基準プリミティブを選択することができる。例えば、加速構造生成装置２００は、整列された複数のプリミティブ８１１−８２１を順次にバウンディングボックスに入力しながら、入力されたプリミティブそれぞれに関するバウンディングボックスサイズの増大比率を算出することができる。
【００９９】
加速構造生成装置２００は、算出された増大比率を基に、増大比率が最大であるプリミティブを選択することができる。例えば、第１プリミティブが選択された場合、加速構造生成装置２００は、整列された複数のプリミティブを、第１プリミティブが含まれた第１バウンディングボックスと、第２プリミティブないし第１１プリミティブが含まれた第２バウンディングボックスとに区分することができる。また、加速構造生成装置２００は、第２バウンディングボックス内に含まれた複数のプリミティブ８１２−８２１に対しても、前述の過程を反復的に遂行することにより、第２バウンディングボックスに含まれた複数のプリミティブ８１２−８２１を、他のバウンディングボックスに区分することができる。
【０１００】
図１０は、一実施形態による加速構造生成装置２００が、整列された複数のプリミティブ８１１−８２１のうち、バウンディングボックスサイズの増大比率が最大であるプリミティブを選択する方法について説明するための図面である。
【０１０１】
図１０においては、説明の便宜のために、図９において、線形コードによって整列された複数のプリミティブ８１１−８２１のうち、第１プリミティブ８１１、第２プリミティブ８１２及び第３プリミティブ８１３のみを図示した。
【０１０２】
一実施形態による加速構造生成装置２００は、整列された複数のプリミティブ８１１−８２１のうち、最初に位置した第１プリミティブ８１１が含まれたバウンディングボックス１０１０の大きさを決定することができる。また、加速構造生成装置２００は、第１プリミティブ８１１が含まれたバウンディングボックス１０１０に、第１プリミティブ８１１の次の順に整列された第２プリミティブ８１２を入力することができる。加速構造生成装置２００は、第１プリミティブ８１１及び第２プリミティブ８１２が含まれたバウンディングボックス１０２０と、第１プリミティブ８１１が含まれたバウンディングボックス１０１０との大きさを比較し、第２プリミティブ８１２に対するバウンディングボックスサイズの増大比率を決定することができる。
【０１０３】
また、加速構造生成装置２００は、第１プリミティブ８１１及び第２プリミティブ８１２が含まれたバウンディングボックス１０２０に、第３プリミティブ８１３を入力することができる。加速構造生成装置２００は、第１プリミティブ８１１、第２プリミティブ８１２及び第３プリミティブ８１３が含まれたバウンディングボックス１０３０と、第１プリミティブ８１１及び第２プリミティブ８１２が含まれたバウンディングボックス１０２０とのサイズを比較し、第３プリミティブ８１３に関するバウンディングボックスサイズの増大比率を決定することができる。
【０１０４】
加速構造生成装置２００は、整列された複数のプリミティブ８１１−８２１のうち残りのプリミティブ８１４−８２１それぞれについても、バウンディングボックスにプリミティブを入力し、バウンディングボックスサイズの増大比率を決定する過程を反復的に遂行することができる。
【０１０５】
一方、加速構造生成装置２００は、複数のプリミティブ８１１−８２１それぞれの増大比率を比較し、増大比率が最大であるプリミティブを選択することができる。本実施形態においては、第１プリミティブ８１１の増大比率が最大であると仮定する。それにより、加速構造生成装置２００は、第１プリミティブ８１１が含まれた第１バウンディングボックス、及び第２プリミティブ８１２ないし第１１プリミティブ８２１が含まれた第２バウンディングボックスに複数のプリミティブを区分することができる。
【０１０６】
また、加速構造生成装置２００は、バウンディングボックスそれぞれに含まれたプリミティブに対して、バウンディングボックスサイズの増大比率を基に区分する過程を反復的に遂行することができる。例えば、加速構造生成装置２００は、第２バウンディングボックスに含まれた第２プリミティブ８１２ないし第１１プリミティブ８２１のうち、増大比率が最大であるプリミティブを選択することができる。加速構造生成装置２００は、選択されたプリミティブを基準に、第２プリミティブ８１２ないし第１１プリミティブ８２１を、第３バウンディングボックス及び第４バウンディングボックスに区分することができる。
【０１０７】
図１１は、一実施形態による加速構造生成装置２００が、複数のプリミティブそれぞれに設定された加重値を利用して、複数のプリミティブをバウンディングボックスに区分する方法について説明するためのフローチャートである。
【０１０８】
１１１０段階において、加速構造生成装置２００は、三次元空間に含まれた複数のプリミティブそれぞれの位置を示す線形コードを生成することができる。
【０１０９】
一方、１１１０段階は、図７を参照して説明した７１０段階と対応する。
【０１１０】
１１２０段階において、加速構造生成装置２００は、生成された線形コードにより、複数のプリミティブを整列することができる。
【０１１１】
一方、１１２０段階は、図７を参照して説明した７２０段階と対応する。
【０１１２】
１１３０段階において、加速構造生成装置２００は、複数のプリミティブの整列順により、加重値を設定することができる。
【０１１３】
一実施形態による加速構造生成装置２００は、複数のプリミティブの個数を基に、整列順序の中心を決定することができる。例えば、加速構造生成装置２００は、複数のプリミティブの個数がＮである場合、整列順序の中心をＮ／２に決定することができる。
【０１１４】
加速構造生成装置２００は、整列順序の中心に近く整列されたプリミティブに対し、さらに高い加重値を設定することができる。例えば、整列順序の中心であるＮ／２をＭと仮定し、複数のプリミティブそれぞれの整列順序をｉと仮定した場合、加速構造生成装置２００は、ｉが１からＭまでであるプリミティブについては、加重値をｉ／Ｍと設定し、ｉがＭ＋１からＮまでであるプリミティブについては、加重値を（Ｎ−ｉ）／Ｍと設定することができる。
【０１１５】
ただし、それは、一つの実施形態であるにすぎず、加速構造生成装置２００において整列された複数のプリミティブ８１１−８２１それぞれに対して加重値を設定する方法は、それに限定されるものではない。
【０１１６】
１１４０段階において、加速構造生成装置２００は、整列された複数のプリミティブを順次にバウンディングボックスに入力しながら、バウンディングボックスサイズの増大比率を決定することができる。
【０１１７】
一方、１１４０段階は、図７を参照して説明した７３０段階と対応する。
【０１１８】
１１５０段階において、加速構造生成装置２００は、設定された加重値、及びバウンディングボックスサイズの増大比率を基に、整列された複数のプリミティブのうちいずれか一つを選択することができる。
【０１１９】
一実施形態による加速構造生成装置２００は、複数のプリミティブそれぞれについて、加重値、及びバウンディングボックスサイズの増大比率が組み合わされた値を比較することができる。例えば、加速構造生成装置２００は、整列された複数のプリミティブそれぞれについて、加重値と、バウンディングボックスサイズの増大比率とを乗じた値を比較することができる。また、加速構造生成装置２００は、整列された複数のプリミティブのうち、加重値と、バウンディングボックスサイズの増大比率とを乗じた値が最大であるプリミティブを選択することができる。
【０１２０】
ただし、それは、一つの実施形態であるにすぎず、加速構造生成装置２００において、加重値と、バウンディングボックスサイズの増大比率とを基にプリミティブを選択する方法は、前述の例に限定されるものではない。
【０１２１】
１１６０段階において、加速構造生成装置２００は、選択されたプリミティブを基準に、整列された複数のプリミティブを、複数のバウンディングボックスに区分することができる。
【０１２２】
一方、１１６０段階は、図７を参照して説明した７５０段階と対応する。
【０１２３】
図１２は、一実施形態による加速構造生成装置２００が、複数のプリミティブ８１１−８２１それぞれに設定された加重値を利用して、複数のプリミティブをバウンディングボックスに区分する方法について説明するための図面である。
【０１２４】
図１２を参照すれば、加速構造生成装置２００は、線形コードにより、複数のプリミティブ８１１−８２１を整列させることができる。一方、図１２において、複数のプリミティブ８１１−８２１は、図９で説明した方法と同一方法によって整列されると仮定する。
【０１２５】
一方、加速構造生成装置２００は、整列された複数のプリミティブ８１１−８２１それぞれに対して、整列順によって加重値を決定することができる。例えば、加速構造生成装置２００は、整列順序の中心に近く整列されたプリミティブの加重値が、整列順序の中心から遠く整列されたプリミティブの加重値より大きい値を有するように、複数のプリミティブ８１１−８２１の加重値を決定することができる。
【０１２６】
加速構造生成装置２００は、複数のプリミティブの個数がＮである場合、整列順序の中心をＮ／２に決定することができる。一方、本実施形態において、整列順序の中心は、複数のプリミティブ８１１−８２１の個数である１１を２で割った値である５．５であると仮定する。
【０１２７】
加速構造生成装置２００は、最初から５番目まで整列されたプリミティブについては、加重値を、それぞれｉ／５．５と設定することができる。ここで、ｉは、整列順序を示す。それにより、第１プリミティブ８１１ないし第５プリミティブ８１５の加重値であるｗ１、ｗ２、ｗ３、ｗ４、ｗ５は、それぞれ１／５．５、２／５．５、３／５．５、４／５．５、５／５．５と設定される。また、加速構造生成装置２００は、６番目から１１番目まで整列されたプリミティブについては、加重値を（Ｎ−ｉ）／Ｍと設定することができる。それにより、第６プリミティブ８１６ないし第１１プリミティブ８２１の加重値であるｗ６、ｗ７、ｗ８、ｗ９、ｗ１０、ｗ１１は、それぞれ５／５．５、４／５．５、３／５．５、２／５．５、１／５．５、０に設定される。
【０１２８】
一実施形態による加速構造生成装置２００は、複数のプリミティブ８１１−８２１それぞれに対して、加重値、及びバウンディングボックスサイズの増大比率が組み合わされた値を比較することができる。例えば、加速構造生成装置２００は、整列された複数のプリミティブそれぞれの加重値と、バウンディングボックスサイズの増大比率とを乗じた値を比較することができる。また、加速構造生成装置２００は、整列された複数のプリミティブのうち加重値と、バウンディングボックスサイズの増大比率とを乗じた値が最大であるプリミティブを選択することができる。例えば、複数のプリミティブ８１１−８２１のうち第１プリミティブ８１１の増大比率が最大である値を有し得るが、第５プリミティブ８１５のバウンディングボックスサイズの増大比率と加重値とを乗じた値が最大である場合には、第５プリミティブ８１５が選択される。
【０１２９】
加速構造生成装置２００は、第５プリミティブ８１５が選択された場合、第１プリミティブ８１１ないし第５プリミティブ８１５が含まれた第１バウンディングボックス１２１０と、第６プリミティブ８１６ないし第１１プリミティブ８２１が含まれた第２バウンディングボックス１２２０とに、複数のプリミティブ８１１−８２１を区分することができる。また、加速構造生成装置２００は、バウンディングボックスサイズの増大比率と加重値とを基に、プリミティブを区分する過程を、第１バウンディングボックス１２１０及び第２バウンディングボックス１２２０それぞれに含まれたプリミティブに反復的に遂行する。
【０１３０】
一実施形態による加速構造生成装置２００は、複数のプリミティブ８１１−８２１の整列順によって決定された加重値を、バウンディングボックスサイズの増大比率と共に複数のプリミティブ８１１−８２１を区分するところに利用することにより、加速構造の深さ（depth）値が大きくなることを緩和したり防止したりすることができる。
【０１３１】
一方、前述の方法は、コンピュータで実行されるプログラムに作成可能であり、コンピュータで読取り可能な記録媒体を利用してプログラムを動作させる汎用デジタルコンピュータでも具現される。また、前述の方法で使用されたデータの構造は、コンピュータで読取り可能な記録媒体に、多くの手段を介して記録される。コンピュータで読取り可能な記録媒体は、磁気記録媒体（例えば、ＲＯＭ（read-only  memory）、ＲＡＭ（random  access  memory）、ＵＳＢ（universal  serial  bus）、フロッピーディスク、ハードディスクなど）、光学的判読媒体（例えば、ＣＤ−ＲＯＭ、ＤＶＤ（digital  versatile  disc）など）を含む。
【産業上の利用可能性】
【０１３２】
本発明の、加速構造を生成する方法及びその装置は、例えば、グラフィックス関連の技術分野に効果的に適用可能である。
【符号の説明】
【０１３３】
１０    視点
２０    画面
３０    一次光線
４０    反射光線
５０    屈折光線
６０    シャドー光線
７０    シーンオブフェクト
１００  レイトレーシングコア
１１０  光線生成ユニット
１２０  ＴＲＶユニット
１３０  ＩＳＴユニット
１４０  シェーディングユニット
２００  加速構造生成装置
２１０  加速構造生成部
２１０  プロセッサ
２２０  メモリ
２５０  外部メモリ
２５１  加速構造
２５２  幾何データ
８００  三次元空間
【図１】
2018073427.tif 000003
【図２】
2018073427.tif 000004
【図３】
2018073427.tif 000005
【図４】
2018073427.tif 000006
【図５】
2018073427.tif 000007
【図６】
2018073427.tif 000008
【図７】
2018073427.tif 000009
【図８】
2018073427.tif 000010
【図９】
2018073427.tif 000011
【図１０】
2018073427.tif 000012
【図１１】
2018073427.tif 000013
【図１２】
2018073427.tif 000014