(57)【要約】【課題】  ツリーを探索する装置及びその方法を提供する。【解決手段】  複数の子ノードが有効な探索対象である場合、複数の子ノードのうちいずれか１つの子ノードをターゲットノードに決定する段階と、経路コードをキー値として利用し、残りの子ノードに係わる情報をメモリに保存する段階と、を含むツリー探索方法である。【選択図】      図６
2017062787.tif 000002
【特許請求の範囲】
【請求項１】
ツリー探索を使用するシステムにおいてツリーを探索する方法において、
複数の子ノードが有効な探索対象である場合、前記複数の子ノードのうちいずれか１つの子ノードをターゲットノードに決定する段階と、
経路コードをキー値として利用し、残りの子ノードに係わる情報をメモリに保存する段階と、を含むツリー探索方法。
【請求項２】
前記メモリは、複数のツリー探索ユニットによって共有されることを特徴とする
請求項１に記載のツリー探索方法。
【請求項３】
前記メモリは、キャッシュメモリであることを特徴とする
請求項１または２に記載のツリー探索方法。
【請求項４】
前記ターゲットノードを決定する段階は、
現在ターゲットノードの経路情報と、次のターゲットノードの相対的な位置とを利用して、前記次のターゲットノードを決定することを特徴とする
請求項１ないし３いずれか一項に記載のツリー探索方法。
【請求項５】
前記ターゲットノードを決定する段階は、
有効な探索対象である子ノードが存在しない場合、現在ターゲットノードの経路情報と、ビットスタックの値とを利用して、探索を終了するか、あるいは次のターゲットノードの経路コードを決定し、前記決定された経路コードをキー値として利用して、前記メモリから次のターゲットノードの情報を獲得することを特徴とする
請求項１ないし４いずれか一項に記載のツリー探索方法。
【請求項６】
前記次のターゲットノードの情報は、前記次のターゲットノードのアドレス及びデコーディング情報を含むことを特徴とする
請求項５に記載のツリー探索方法。
【請求項７】
交差検査を介して、前記複数の子ノードのうちいずれの子ノードが有効な探索対象であるかということを決定する段階をさらに含むことを特徴とする
請求項１ないし６いずれか一項に記載のツリー探索方法。
【請求項８】
前記ツリーは、トレーシングシステムにおいて使用されることを特徴とする
請求項１ないし７いずれか一項に記載のツリー探索方法。
【請求項９】
前記保存する段階は、
前記ツリーの深さごとに、前記残りの子ノードに係わる情報を、前記メモリに保存したか否かということをビットスタックに保存する段階を含むことを特徴とする
請求項１ないし８いずれか一項に記載のツリー探索方法。
【請求項１０】
コンピュータに請求項１ないし９のうちいずれか１項に記載の方法を実行させるコンピュータプログラム。
【請求項１１】
複数の子ノードが有効な探索対象である場合、前記複数の子ノードのうちいずれか１つのノードをターゲットノードに決定するツリー探索ユニットと、
経路コードをキー値として利用し、残りの子ノードに係わる情報を保存するメモリと、を含む
ツリー探索装置。
【請求項１２】
前記メモリは、前記ツリー探索ユニットによって共有されることを特徴とする
請求項１１に記載のツリー探索装置。
【請求項１３】
前記メモリは、キャッシュメモリであることを特徴とする
請求項１１または１２に記載のツリー探索装置。
【請求項１４】
前記ツリー探索ユニットは、現在ターゲットノードの経路情報と、次のターゲットノードの相対的な位置とを利用して、前記次のターゲットノードを決定することを特徴とする
請求項１１ないし１３いずれか一項に記載のツリー探索装置。
【請求項１５】
前記ツリー探索ユニットは、有効な探索対象である子ノードが存在しない場合、現在ターゲットノードの経路情報と、ビットスタックの値とを利用して、探索を終了するか、あるいは次のターゲットノードの経路コードを決定し、前記決定された経路コードをキー値として利用して、前記メモリから次のターゲットノードの情報を獲得することを特徴とする
請求項１１ないし１４いずれか一項に記載のツリー探索装置。
【請求項１６】
前記次のターゲットノードの情報は、前記次のターゲットノードのアドレス及びデコーディング情報を含むことを特徴とする
請求項１５に記載のツリー探索装置。
【請求項１７】
前記ツリー探索ユニットは、交差検査を介して、前記複数の子ノードのうちいずれの子ノードが有効な探索対象であるかということを決定することを特徴とする
請求項１１ないし１６いずれか一項に記載のツリー探索装置。
【請求項１８】
前記ツリーは、レイトレーシングシステムに使用されることを特徴とする
請求項１１ないし１７いずれか一項に記載のツリー探索装置。
【請求項１９】
前記ツリー探索ユニットは、前記ツリーの深さごとに、前記残りの子ノードに係わる情報を、前記メモリに保存したか否かということをビットスタックに保存することを特徴とする
請求項１１ないし１８いずれか一項に記載のツリー探索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ツリーを探索する装置及びその方法に関する。
【背景技術】
【０００２】
三次元（３Ｄ：３−dimensional）レンダリングは、三次元オブジェクトデータを与えられたカメラの視点（view  point）から見える映像に合成（synthesis）する映像処理過程である。レイトレーシング方法は、レンダリングの対象になるシーンオブジェクト（scene  object）と光線とが交差する地点を追跡する過程である。レイトレーシング（ray-tracing）は、加速構造（acceleration  structure）の探索（traversal）と、光線・プリミティブ（ray-primitive）間の交差検査（intersection  test）との過程を含む。このとき、探索と交差検査との過程で多くの演算量（computation）、及び広いメモリ帯域幅（memory  bandwidth）を必要とする。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
本発明が解決しようとする課題は、ツリーを探索する装置及びその方法を提供するところにある。
【０００４】
本発明が解決しようとする課題はまた、前記方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体を提供するところにある。
【課題を解決するための手段】
【０００５】
一実施形態によるツリー探索方法は、複数の子ノードが有効な探索対象である場合、前記複数の子ノードのうちいずれか１つの子ノードをターゲットノードに決定する段階と、経路コードをキー（key）値として利用し、残りの子ノードに係わる情報をメモリに保存する段階と、を含む。
【０００６】
また、前記メモリは、複数のツリー探索ユニットによって共有される。
【０００７】
また、前記メモリは、キャッシュメモリであることを特徴とする。
【０００８】
また、前記ターゲットノードを決定する段階は、現在ターゲットノードの経路情報と、次のターゲットノードの相対的な位置とを利用して、前記次のターゲットノードを決定することを特徴とする。
【０００９】
また、前記ターゲットノードを決定する段階は、有効な探索対象である子ノードが存在しない場合、現在ターゲットノードの経路情報と、ビットスタックの値とを利用して、探索を終了するか、あるいは次のターゲットノードの経路コードを決定し、前記決定された経路コードをキー値として利用して、前記メモリから次のターゲットノードの情報を獲得することを特徴とする。
【００１０】
また、前記次のターゲットノードの情報は、前記次のターゲットノードのアドレス及びデコーディング情報を含むことを特徴とする。
【００１１】
また、交差検査を介して、前記複数の子ノードのうちいずれの子ノードが有効な探索対象であるかということを決定する段階をさらに含む。
【００１２】
また、前記ツリーは、トレーシングシステムで使用されることを特徴とする。
【００１３】
また、前記保存する段階は、前記ツリーの深さごとに、前記残りの子ノードに係わる情報を、前記メモリに保存したか否かということをビットスタックに保存する段階を含むことを特徴とする。
【００１４】
一実施形態によるツリー探索装置は、複数の子ノードが有効な探索対象である場合、前記複数の子ノードのうちいずれか１つのノードをターゲットノードに決定するツリー探索ユニットと、経路コードをキー（key）値として利用し、残りの子ノードに係わる情報を保存するメモリと、を含む。
【００１５】
また、前記メモリは、前記ツリー探索ユニットによって共有される。
【００１６】
また、前記メモリは、キャッシュメモリであることを特徴とする。
【００１７】
また、前記ツリー探索ユニットは、現在ターゲットノードの経路情報と、次のターゲットノードの相対的な位置とを利用して、前記次のターゲットノードを決定することを特徴とする。
【００１８】
また、前記ツリー探索ユニットは、有効な探索対象である子ノードが存在しない場合、現在ターゲットノードの経路情報と、ビットスタックの値とを利用して、探索を終了するか、あるいは次のターゲットノードの経路コードを決定し、前記決定された経路コードをキー値として利用して、前記メモリから次のターゲットノードの情報を獲得することを特徴とする。
【００１９】
また、前記次のターゲットノードの情報は、前記次のターゲットノードのアドレス及びデコーディング情報を含むことを特徴とする。
【００２０】
また、前記ツリー探索ユニットは、交差検査を介して、前記複数の子ノードのうちいずれの子ノードが有効な探索対象であるかということを決定することを特徴とする。
【００２１】
また、前記ツリーは、レイトレーシングシステムに使用されることを特徴とする。
【００２２】
また、前記ツリー探索ユニットは、前記ツリーの深さごとに、前記残りの子ノードに係わる情報を、前記メモリに保存したか否かということをビットスタックに保存することを特徴とする。
【発明の効果】
【００２３】
本発明によれば、探索ユニットが共有するメモリに、ノードに係わる情報を保存することができる。
【００２４】
本発明によれば、探索ユニットが経路コードをキー（key）値として利用して、メモリに接続することができる。
【００２５】
本発明によれば、探索ユニットは、経路コードをキー値として利用して、ツリーを探索することができる。
【図面の簡単な説明】
【００２６】
【図１】レイトレーシングについて説明するための図面である。
【図２】レイトレーシングコアについて説明するための図面である。
【図３】レイトレーシングコアがレイトレーシングを行う動作について説明するための図面である。
【図４】レイトレーシングを加速させるための方法について説明するための図面である。
【図５】図４のレイトレーシングを加速させるための方法について説明するための図面である。
【図６】一実施形態によるツリー探索装置を示す構成図である。
【図７】一実施形態によるツリー探索方法について説明するフローチャートである。
【図８】ツリー探索ユニットがツリーを探索する方法を示すフローチャートである。
【図９】一実施形態によって、ツリーを探索する方法について説明するための図面である。
【図１０】一実施形態によって、ツリーを探索する方法について説明するための図面である。
【図１１】一実施形態によって、ツリーを探索する方法について説明するための図面である。
【図１２】一実施形態によって、ツリーを探索する方法について説明するための図面である。
【図１３】一実施形態によって、ツリーを探索する方法について説明するための図面である。
【図１４】一実施形態によって、ツリーを探索する方法について説明するための図面である。
【図１５】一実施形態によって、ツリーを探索する方法について説明するための図面である。
【図１６】一実施形態によって、ツリーを探索する方法について説明するための図面である。
【図１７】一実施形態によって、ツリーを探索する方法について説明するための図面である。
【図１８】一実施形態によって、ツリーを探索する方法について説明するための図面である。
【図１９】一実施形態によって、ツリーを探索する方法について説明するための図面である。
【図２０】一実施形態によって、ツリーを探索する方法について説明するための図面である。
【図２１】一実施形態によって、ツリーを探索する方法について説明するための図面である。
【図２２】一実施形態によって、ツリーを探索する方法について説明するための図面である。
【発明を実施するための形態】
【００２７】
以下、添付した図面を参照し、本開示が属する技術分野で当業者が容易に実施することができるように、本開示の実施形態について詳細に説明する。しかし、本開示は、さまざまに異なる形態に具現され、ここで説明する実施形態に限定されるものではない。また、図面において、本開示について明確に説明するために、説明と関係ない部分は省略し、明細書全体を通じて、類似した部分については、類似図面符号を付した。
【００２８】
本開示で使用される用語は、本開示で言及される機能を考慮し、現在使用される一般的な用語で記載したが、それは、当分野の当業者の意図または判例、新たな技術の出現などによって、多様な他の用語を意味することもある。従って、本開示で使用される用語は、用語の名称だけで解釈されてはならず、用語が有する意味と、本開示の全般にわたった内容とを基に解釈されなければならない。
【００２９】
また、第１、第２のような用語は、多様な構成要素についての説明に使用されるが、構成要素は、該用語によって限定されるものではない。該用語は、１つの構成要素を他の構成要素から区別する目的で使用される。
【００３０】
また、本開示で使用された用語は、ただ特定実施形態についての説明のために使用されたものであり、本開示を限定する意図で使用されるものではない。単数の表現は、文脈上明白に単数を意味しない限り、複数の意味を含む。また、明細書全体で、ある部分が他の部分と「連結」されているとするとき、それは、「直接連結」されている場合だけではなく、その中間に、他の素子を挟んで、「電気的に連結」されている場合も含む。また、ある部分がある構成要素を「含む」とするとき、それは、特別に反対になる記載がない限り、他の構成要素を除くものではなく、他の構成要素をさらに含んでもよいということを意味する。
【００３１】
本明細書（特に、特許請求の範囲で）で使用された「前記」、及びそれと類似した指示語は、単数及び複数のいずれも指示するものである。また、本開示による方法について説明する段階の順序を明白に指定する記載がなければ、記載された段階は、適切な順序で遂行される。記載された段階の記載順序によって、本開示が限定されるものではない。
【００３２】
本明細書で多様なところに登場する「一部実施形態で」または「一実施形態で」というような語句は、必ずしもいずれも同一の実施形態を示すものではない。
【００３３】
本開示の一実施形態は、機能的なブロック構成、及び多様な処理段階で示される。かような機能ブロックの一部または全部は、特定機能を実行する多様な個数のハードウェア構成及び／またはソフトウェア構成によって具現される。例えば、本開示の機能ブロックは、１以上のマイクロプロセッサによって具現されるか、あるいは所定の機能のための回路構成によっても具現される。また、例えば、本開示の機能ブロックは、多様なプログラミング言語またはスクリプティング言語によって具現される。機能ブロックは、１以上のプロセッサで実行されるアルゴリズムによって具現される。また、本開示は、電子的な環境設定、信号処理及び／またはデータ処理などのために、従来技術を採用することができる。「メカニズム」、「要素」、「手段」及び「構成」のような用語は、広く使用され、機械的であって物理的な構成として限定されるものではない。
【００３４】
また、図面に図示された構成要素間の連結線または連結部材は、機能的な連結、及び／または物理的または回路的な連結を例示的に示したものであるのみである。実際の装置では、代替可能であったり、追加されたりする多様な機能的な連結、物理的な連結または回路連結によって、構成要素間の連結が示される。
【００３５】
以下、添付された図面を参照し、本開示について詳細に説明する。
【００３６】
図１は、レイトレーシング（ray  tracing）について説明するための図面である。図１を参照すれば、三次元モデリングにおいて、レイトレーシングコア（ray  tracing  core）は、視点（view  point）１０を決定し、視点によって、画面（image）２０を決定する。視点１０と画面２０とが決定されれば、レイトレーシングコアは、視点１０から、画面２０の各ピクセル（pixel）に対して光線を生成する。
【００３７】
図１の構成について説明すれば、視点１０から、一次光線（primary  ray）３０が生成される。一次光線３０は、画面２０を経て、シーンオブジェクト（scene  object）７０と交差する。一次光線３０とシーンオブジェクト７０との交差点では、反射光線（reflection  ray）、４０及び屈折光線（refraction  ray）５０が生成される。また、交差点において、光源８０の方向に、シャドー光線（shadow  ray）６０が生成される。このとき、反射光線４０、屈折光線５０、シャドー光線６０を二次光線という。シーンオブジェクト７０は、画面２０に対するレンダリングの対象になるオブジェクトを示す。シーンオブジェクト７０は、複数のプリミティブを含む。
【００３８】
レイトレーシングコアは、一次光線３０、二次光線（反射光線４０、屈折光線５０、シャドー光線６０）、及び二次光線から派生される光線を分析する。レイトレーシングコアは、分析結果に基づいて、画面２０を構成するピクセルの色相値を決定する。このとき、レイトレーシングコアは、シーンオブジェクト７０の特性を考慮し、ピクセルの色相値を決定する。
【００３９】
図２は、レイトレーシングコア１００について説明するための図面である。図２を参照すれば、レイトレーシングコア１００は、光線生成ユニット１１０、ＴＲＶ（traversal）ユニット１２０、ＩＳＴ（intersection  test）ユニット１３０及びシェーディングユニット１４０を含む。図２では、ＴＲＶユニット１２０、ＩＳＴユニット１３０がレイトレーシングコア１００に含まれるように図示されているが、ＴＲＶユニット１２０、ＩＳＴユニット１３０は、別途のハードウェアによっても具現される。図２に図示されているレイトレーシングコア１００は、本実施形態と係わる構成要素だけが図示されている。従って、図２に図示されている構成要素以外に、他の汎用的な構成要素がさらに含まれてもよいということは、本実施形態と係わる技術分野で当業者であるならば、理解することができるであろう。
【００４０】
レイトレーシングコア１００は、生成された光線と、三次元空間に位置したオブジェクトとの交差点を追跡し、画面を構成するピクセルの色相値を決定する。言い替えれば、レイトレーシングコア１００は、光線とオブジェクトとの交差点を探し出し、交差点でのオブジェクトの特性によって二次光線を生成し、交差点の色相値を決定する。
【００４１】
レイトレーシングコア１００は、加速構造を探索して交差検査を行うとき、以前探索の結果、及び以前交差検査の結果を利用することができる。言い換えれば、レイトレーシングコア１００は、以前レンダリング過程で遂行された結果を、現在レンダリング過程に適用することにより、現在レンダリングをさらに迅速に行うことができる。
【００４２】
光線生成ユニット１１０は、一次光線及び二次光線を生成する。光線生成ユニット１１０は、視点から一次光線を生成し、一次光線とオブジェクトとの交差点で反射、屈折またはシャドーの二次光線を生成する。光線生成ユニット１１０は、また二次光線とオブジェクトとの交差点において、他の二次光線を生成することができる。光線生成ユニット１１０は、決定された回数内で、反射光線、屈折光線、シャドー光線を生成するか、あるいはオブジェクトの特性によって、反射光線、屈折光線、シャドー光線の生成回数を決定することができる。
【００４３】
ＴＲＶユニット１２０は、光線生成ユニット１１０から生成された光線に係わる情報を受信する。生成された光線は、一次光線、二次光線、及び二次光線によって派生された光線をいずれも含む。例えば、一次光線の場合、ＴＲＶユニット１２０は、生成された光線の視点及び方向に係わる情報を受信することができる。また、二次光線の場合、ＴＲＶユニット１２０は、二次光線の出発点及び方向に係わる情報を受信することができる。二次光線の出発点は、一次光線がヒットされた地点を示す。視点または出発点は、座標によって表現され、方向は、ベクトルによって表現される。
【００４４】
ＴＲＶユニット１２０は、外部メモリ２５０から、加速構造に係わる情報を読み取る。加速構造は、加速構造生成装置２００によって生成され、生成された加速構造は、外部メモリ２５０に保存される。加速構造は、三次元空間のオブジェクトの位置情報を含んでいる構造を示す。例えば、加速構造は、ＫＤ−tree（Ｋ−dimensional  tree）、ＢＶＨ（bounding  volume  hierarchy）などが適用される。
【００４５】
ＴＲＶユニット１２０は、加速構造を探索し、光線がヒットされたオブジェクトまたはリーフノード（leaf  node）を出力する。例えば、ＴＲＶユニット１２０は、加速構造に含まれたノードを探索し、ノードのうち最下位ノードであるリーフノードのうち、光線がヒットされたリーフノードをＩＳＴユニット１３０に出力する。言い替えれば、ＴＲＶユニット１２０は、加速構造を構成するバウンディングボックス（bounding  box）のうちいずれのバウンディングボックスに光線がヒットされたかということを判断し、バウンディングボックスに含まれたオブジェクトのうち、いずれのオブジェクトに光線がヒットされたかということを判断する。ヒットされたオブジェクトに係わる情報は、ＴＲＶキャッシュに保存される。バウンディングボックスは、複数のオブジェクトまたはプリミティブを含む単位を示し、加速構造によって他の形態に表現される。ＴＲＶキャッシュは、ＴＲＶユニット１２０が探索過程で使用するデータを一時的に保存するためのメモリを示す。
【００４６】
ＴＲＶユニット１２０は、以前レンダリングの結果を利用して、加速構造を探索することができる。ＴＲＶユニット１２０は、ＴＲＶキャッシュに保存された以前レンダリングの結果を利用して、以前レンダリングと同一経路で加速構造を探索することができる。例えば、ＴＲＶユニット１２０が、入力された光線に対する加速構造を探索するとき、ＴＲＶユニット１２０は、入力された光線と同一の視点及び方向を有する以前光線がヒットされたバウンディングボックスに対する探索を優先的に行うことができる。また、ＴＲＶユニット１２０は、以前光線に対する探索経路を参照し、加速構造を探索することができる。
【００４７】
ＩＳＴユニット１３０は、ＴＲＶユニット１２０から、光線がヒットされたオブジェクトまたはリーフノードを受信し、外部メモリ２５０からヒットされたオブジェクトに含まれたプリミティブに係わる情報を読み取る。読み取られたプリミティブに係わる情報は、ＩＳＴキャッシュに保存される。ＩＳＴキャッシュは、交差検索過程において、ＩＳＴユニット１３０が使用するデータを一時的に保存するためのメモリを示す。
【００４８】
ＩＳＴユニット１３０は、光線とプリミティブとの交差検査を行い、光線がヒットされたプリミティブ及び交差点を出力する。ＴＲＶユニット１２０から光線がヒットされたオブジェクトが何であるかということを受信したＩＳＴユニット１３０は、ヒットされたオブジェクトに含まれた複数のプリミティブのうちいずれのプリミティブに光線がヒットされたかということを検査する。光線がヒットされたプリミティブを探した後、ＩＳＴユニット１３０は、ヒットされたプリミティブのいずれの地点と光線が交差したかということを示す交差点を出力する。交差点は、座標形態でシェーディングユニット１４０に出力される。
【００４９】
ＩＳＴユニット１３０は、以前レンダリングの結果を利用して、交差検査を行うことができる。ＩＳＴユニット１３０は、ＩＳＴキャッシュに保存された以前レンダリングの結果を利用して、以前レンダリングと同一プリミティブに対して、優先的に交差検査を行うことができる。例えば、入力された光線及びプリミティブに対する交差検査を行うとき、ＩＳＴユニット１３０は、入力された光線と同一の視点及び方向を有する以前光線がヒットされたプリミティブに対する交差検査を優先的に行うことができる。
【００５０】
シェーディングユニット１４０は、ＩＳＴユニット１３０から受信された交差点に係わる情報、及び交差点の物質特性に基づいて、ピクセルの色相値を決定する。シェーディングユニット１４０は、交差点の物質基本色相、及び光源による効果などを考慮し、ピクセルの色相値を決定する。
【００５１】
レイトレーシングコア１００は、外部メモリ２５０から、レイトレーシングに必要なデータを受信する。外部メモリ２５０には、加速構造生成装置２００によって生成された加速構造、またはプリミティブに係わる情報を示す幾何データ（geometry  data）が保存される。プリミティブは、三角形、四角形などの多角形でもあり、幾何データは、オブジェクトに含まれたプリミティブの頂点及び位置に係わる情報を示すことができる。
【００５２】
加速構造生成装置２００は、三次元空間上のオブジェクトの位置情報を含む加速構造を生成する。加速構造生成装置２００は、さまざまな形態の加速構造を生成することができる。例えば、加速構造は、三次元空間が、階層的ツリーに分割された形態でもあり、加速構造生成装置２００は、ＢＶＨまたはＫＤ−treeを適用し、三次元空間上のオブジェクトの関係を示す構造を生成することができる。加速構造生成装置２００は、リーフノードの最大プリミティブの数及びツリー深さを決定し、決定に基づいて加速構造を生成することができる。
【００５３】
図３は、レイトレーシングコアがレイトレーシングを行う動作について説明するための図面である。レイトレーシングコアは、例えば、図２に図示されているレイトレーシングコア１００の構造を有することができる。従って、以下で省略された内容であるとしても、レイトレーシングコア１００について、以上で記述された内容は、図３のレイトレーシング方法にも適用される。
【００５４】
３１０段階において、レイトレーシングコア１００は、光線を生成する。レイトレーシングコア１００は、一次光線、二次光線、及び二次光線によって派生された光線を生成する。
【００５５】
３２０段階において、レイトレーシングコア１００は、外部メモリ２５０から読み取られた加速構造を探索する。レイトレーシングコア１００は、生成された光線の視点及び方向に基づいて、加速構造２５１を探索し、光線がヒットされたバウンディングボックスを検出し、ヒットされたバウンディングボックスに含まれたオブジェクトのうち光線がヒットされたオブジェクトを検出する。レイトレーシングコア１００は、ヒットされたオブジェクトを検出するまで、加速構造２５１の探索を反復して行う。例えば、レイトレーシングコア１００は、いずれか１つの経路に沿って加速構造を探索し、探索された経路上のリーフノードに光線がヒットされないのであるならば、他の経路で加速構造を探索する。
【００５６】
レイトレーシングコア１００は、全ての経路を順次に探索することができるが、以前光線の探索情報に基づいて、特定経路を優先的に探索することができる。例えば、以前光線の視点及び方向が、現在光線の視点及び方向と同一であるか、あるいは類似している場合、レイトレーシングコア１００は、以前光線でヒットされたリーフノードが含まれた経路を優先的に探索することができる。
【００５７】
３３０段階において、レイトレーシングコア１００は、交差検査を行う。レイトレーシングコア１００は、外部メモリ２５０から読み取られたプリミティブの幾何データ２５２に基づいて交差検査を行う。レイトレーシングコア１００は、ヒットされたプリミティブを検出するまで、交差検査を反復して行う。例えば、レイトレーシングコア１００は、いずれか１つのプリミティブに対する交差検査を行い、プリミティブに光線がヒットされなかったならば、他のプリミティブに対する交差検査を行う。
【００５８】
レイトレーシングコア１００は、全てのプリミティブを順次に交差検査することができるが、以前光線の交差検査情報に基づいて、特定プリミティブを優先的に交差検査することができる。例えば、以前光線及び現在光線の視点及び方向が同一であるか、あるいは類似している場合、レイトレーシングコア１００は、以前光線でヒットされたプリミティブに対する交差検査を優先的に行うことができる。
【００５９】
３４０段階において、レイトレーシングコア１００は、交差検査に基づいて、ピクセルのシェーディングを行う。レイトレーシングコア１００は、３４０段階が終了すれば、３１０段階に進む。レイトレーシングコア１００は、３１０段階ないし３４０段階を画面を構成する全てのピクセルに対して反復的に遂行する。
【００６０】
図４は、レイトレーシングを加速させるための方法について説明するための図面である。図４を参照すれば、第１画面４１２は、ｔ＝０であるとき、レンダリングされた画面を示し、第２画面４２２は、ｔ＝１であるとき、レンダリングされた画面を示す。第１画面４１２及び第２画面４２２から、ウサギ４３３だけが移動し、四角形４３１と三角形４３２は、動きがないために、第１画面４１２と第２画面４２２は、ほぼ類似している。従って、レイトレーシングコア１００は、第１画面４１２に対するレンダリング結果を利用して、第２画面４２２に対するレンダリングを行うことができる。例えば、第１視点４１０と第２視点４２０との位置が同一であり、第１光線４１１と第２光線４２１との方向が同一であれば、レイトレーシングコア１００は、第１光線４１１に対するレイトレーシングの結果を、第２光線４２１のレイトレーシングに適用し、第２光線４２１のレイトレーシングを加速させることができる。例えば、レイトレーシングコア１００のＴＲＶユニット１２０は、第２光線４２１に対する探索を行うとき、第１光線４１１がヒットされたバウンディングボックスを優先的に探索することができる。また、レイトレーシングコア１００のＩＳＴユニット１３０は、第２光線４２１に対する交差検査を行うとき、第１光線４１１がヒットされた三角形４３２に対して優先的に交差検査を行うことができる。
【００６１】
図５は、図４のレイトレーシングを加速させるための方法について説明するための図面である。図５を参照すれば、加速構造は、５個のノード（１ないし５）を含み、ノード３ないしノード５は、リーフノードを示す。
【００６２】
ＴＲＶユニット１２０は、３通りの経路に沿って加速構造を探索することができる。第一に、ＴＲＶユニット１２０は、第１経路であるノード１、ノード２及びノード３に沿って、加速構造を探索することができる。第二に、ＴＲＶユニット１２０は、第２経路であるノード１、ノード２及びノード４に沿って加速構造を探索することができる。第三に、ＴＲＶユニット１２０は、第３経路であるノード１及びノード５に沿って加速構造を探索することができる。このとき、ＴＲＶユニット１２０が第２光線４２１に対する探索を行うとき、ＴＲＶユニット１２０は、第１光線４１１がヒットされた三角形４３２を探索する第２経路を優先的に探索する。従って、ＴＲＶユニット１２０が、第１経路または第３経路を探索する過程を省略することができる。
【００６３】
図６は、一実施形態によるツリー探索装置（tree  traversal  apparatus）を示す構成図である。ツリー探索装置６００は、複数のツリー探索ユニット６１０及びメモリ６２０を含む。
ツリーは、複数のノードを含み、ツリー探索装置６００は、ノードを探索する。ツリー探索装置６００は、ノードの子ノードが有効な探索対象であるか否かということを決定するために交差検査を行う。
【００６４】
複数のツリー探索ユニット６１０は、独立してツリーを探索することができる。また、複数のツリー探索ユニット６１０は、独立してメモリ６２０に接続することができる。
【００６５】
ツリー探索ユニット６１０は、ツリーを探索するとき、メモリ６２０を利用する。ツリー探索ユニット６１０は、メモリ６２０に、探索するノードに係わる情報を保存することができる。ノードに係わる情報は、ノードのアドレスまたはデコーディング情報を含んでもよい。デコーディング情報は、圧縮されたバウンディングボックスに係わる情報をデコーディングするためのパラメータを含んでもよい。階層的に（hierarchy）連結されたツリー構造において、ランダムにノードのデータを獲得するためには、デコーディング情報が要求される。従って、ツリー探索ユニット６１０は、メモリ６２０に保存されたデコーディング情報を利用して、圧縮されたノードのデータをデコーディングすることができる。
【００６６】
ツリー探索ユニット６１０は、メモリ６２０を共有する。例えば、メモリ６２０は、キャッシュメモリでもある。
【００６７】
ツリー探索ユニット６１０は、複数の子ノードのうちいずれか１つのノードをターゲットノードに決定する。ツリー構造の場合、いずれか１つのノードは、２個の子ノードを含んでもよい。ツリー探索ユニット６１０は、現在ノードの経路情報と、決定されたターゲットノードの相対的な位置とを利用して、ターゲットノードの経路情報を決定することができる。
【００６８】
ツリー探索ユニット６１０は、ターゲットノードのノードデータを獲得し、ノードデータに対する演算を行う。例えば、ツリー探索ユニット６１０は、ノードデータを利用して、ターゲットノードの子ノードと光線とが交差したか否かということを検査することができる。言い替えれば、ツリー探索ユニット６１０は、交差検査を介して、いずれの子ノードが有効な探索対象であるかということを決定する。光線と交差した子ノードが有効な探索対象になる。２個の子ノードがいずれも有効な探索対象である場合、ツリー探索ユニット６１０は、いずれか１つのノードをターゲットノードに決定し、残りの子ノードに係わる情報は、メモリ６２０に保存する。
【００６９】
ツリー探索ユニット６１０は、経路コードをキー（key）値として利用し、残りの子ノードに係わる情報を保存する。ツリー探索ユニット６１０は、残りの子ノードの経路情報をキー値としてメモリ６２０のアドレスを決定し、決定されたアドレスに、残りの子ノードに係わる情報を保存する。ツリー探索ユニット６１０が、メモリ６２０のアドレスを決定する方法については、図９以下で詳細に説明する。
【００７０】
ツリー探索ユニット６１０は、経路コードを利用して、メモリ６２０に接続することができる。ツリー探索ユニット６１０は、メモリ６２０に、ノードに係わる情報を保存するか、あるいはノードに係わる情報を読み取るとき、経路コードを利用することができる。
【００７１】
経路コードは、ツリーに含まれたノードの相対的な位置を示すコードである。経路コードは、二進コードでもある。例えば、左側ノードの経路は、０と示し、右側ノードの経路は、１と示すことができる。ルートノードから２番目の深さに位置した左側ノードは、００で示すことができる。前述のところのように、探索経路をコードで示すことは、一例であるのみ、多様な方法で探索経路をコードで示すことができる。
【００７２】
ツリー探索ユニット６１０は、複数の子ノードが有効な探索対象である場合、現在ノードに保存されている子ノードのアドレスを使用してターゲットノードを決定する。また、ツリー探索ユニット６１０は、有効な探索対象になる子ノードがない場合、メモリ６２０からノードに係わる情報を読み取り、ターゲットノードを決定する。ツリー探索ユニット６１０が、次のターゲットノードを決定する方法については、図９以下で詳細に説明する。
【００７３】
ツリーは、レイトレーシングシステムに使用される。レイトレーシングシステムは、光線がバウンディングボックスと交差するか否かということを判断するために、ツリーを使用する。例えば、ツリー探索ユニット６１０は、それぞれの光線が、ノードと交差するか否かということを検査することができる。ツリー探索ユニット６１０は、個別的に光線を受光し、受光された光線が、いずれのノードと交差するかということを探索する。ツリー探索ユニット６１０は、ターゲットノードの子ノードと光線が交差するか否かということを判断し、ターゲットノードを変更し、変更されたターゲットノードの子ノードと光線とが交差する否かということを判断する過程を反復して遂行する。
【００７４】
ツリー探索ユニット６１０は、ツリーの深さごとに、残りの子ノードに係わる情報をメモリ６２０に保存したか否かということをビットスタックに保存する。ツリーの深さは、ルートノードから何番目の子ノードであるかということを示す。例えば、ツリー探索ユニット６１０は、メモリ６２０に、残りの子ノードに係わる情報を保存し、ビットスタックに１を記録することができる（write）。
【００７５】
図７は、一実施形態によるツリー探索方法について説明するフローチャートである。
【００７６】
段階７１０において、ツリー探索ユニット６１０は、複数の子ノードが有効な探索対象である場合、複数の子ノードのうちいずれか１つのノードをターゲットノードに決定する。例えば、ツリー探索ユニット６１０は、ルートノードの子ノードのうちいずれか一つをターゲットノードに決定することもできる。
【００７７】
段階７２０において、ツリー探索ユニット６１０は、残りの子ノードの経路コードをキー値として利用し、残りの子ノードに係わる情報をメモリ６２０に保存する。
【００７８】
ツリー探索ユニット６１０は、ターゲットノードに対する演算を行い、次のターゲットノードを決定する。有効な探索対象である子ノードが存在する場合、ツリー探索ユニット６１０は、子ノードを次のターゲットノードに決定する。有効な探索対象である子ノードが存在しない場合、ツリー探索ユニット６１０は、現在ターゲットノードの経路情報及びビットスタック値を利用して、次のターゲットノードを決定することができる。ツリー探索ユニット６１０は、現在ターゲットノードの経路コードと、ビットスタック値とを利用して、メモリ６２０のアドレスを獲得し、獲得されたアドレスに保存されたターゲットノードの情報を読み取る。ツリー探索ユニット６１０は、次のターゲットノードに対する演算を行う。次のターゲットノードの情報は、次のターゲットノードのアドレス及びデコーディング情報を含む。
【００７９】
次のターゲットノードがない場合、ツリー探索ユニット６１０は、探索を終了することができる。
【００８０】
図８は、ツリー探索ユニットがツリーを探索する方法を示すフローチャートである。
【００８１】
段階８０１において、ツリー探索ユニット６１０は、ノードをプッシュ（push）またはポップ（pop）するか否かということを判断する。ノードのプッシュとは、ノードに係わる情報をメモリ６２０に保存することを意味する。ノードのポップとは、メモリ６２０に保存されたノードに係わる情報を読み取ることを意味する。ツリー探索ユニット６１０は、有効な探索対象であるノードであるが、後で探索するノードをメモリ６２０にプッシュすることができる。また、ツリー探索ユニット６１０は、有効な探索対象であるノードが存在しない場合、メモリ６２０に保存されたノードをポップすることができる。
【００８２】
段階８０２において、ツリー探索ユニット６１０は、ノードをプッシュするか否かということを判断する。
【００８３】
段階８０３において、ツリー探索ユニット６１０は、プッシュ経路コードを獲得し、経路コードをアップデートする。プッシュするノードによって、プッシュ経路コードが異なることになる。プッシュ経路コードは、プッシュするノードの経路を示す。
【００８４】
段階８０４において、ツリー探索ユニット６１０は、プッシュ経路コードに、ノードに係わる情報を記録する。言い替えれば、ツリー探索ユニット６１０は、プッシュ経路コードをキー値としてメモリ６２０のアドレスを決定し、決定されたアドレスに、プッシュするノードに係わる情報を記録する。
【００８５】
段階８０５において、ツリー探索ユニット６１０は、ポップ経路コードを獲得する。ポップ経路コードはポップするノードの経路を示す。
【００８６】
段階８０６において、ツリー探索ユニット６１０は、ポップ経路コードから、ノードに係わる情報を読み取る。言い替えれば、ツリー探索ユニット６１０は、ポップ経路コードをキー値としてメモリ６２０のアドレスを決定し、決定されたアドレスに保存されたノードに係わる情報を読み取る。
【００８７】
段階８０７において、ツリー探索ユニット６１０は、メモリ６２０から、ノードに係わる情報の読み取りに失敗したかいなかということを判断する。例えば、メモリ６２０がキャッシュメモリである場合、キャッシュミスが発生したか否かということを判断する。
【００８８】
段階８０８において、ツリー探索ユニット６１０は、探索を改めて始め、経路コードを初期化する。
【００８９】
段階８０９において、ツリー探索ユニット６１０は、経路コードをアップデートする。ツリー探索ユニット６１０は、メモリ６２０に保存されたノードに係わる情報を読み取り、読み取られたノードに係わる情報によって、経路コードをアップデートする。
【００９０】
段階８１０において、ツリー探索ユニット６１０は、経路コードをアップデートする。
【００９１】
図９ないし図２２は、一実施形態によって、ツリーを探索する方法について説明するための図面である。図９ないし図２２を参照すれば、ツリー探索ユニット６１０は、ルートノード０からリーフノード８までを探索することができる。図９ないし図２２でにおいて、左側に位置した子ノードを経路コード０で示し、右側に位置した子ノードは、経路コード１で示した。反対に、経路コードを付与することも可能であり、０または１ではない他のコードを付与することも可能である。
【００９２】
図９は、ツリー探索ユニット６１０がツリー探索を始めることを示す。ツリー探索ユニット６１０は、ルートノード０から探索を始める。メモリ６２０は、アドレス（address）とノードデータ（node  data）とを保存することができる。経路（path）は、現在（current）、次（next）、プッシュ（push）などで示すことができる。ビットスタック（bit  stack）は、ツリーの深さごとに、プッシュが行われたか否かということを示す。Currentは、現在ノードの経路を示し、nextは、次のノードの経路を示し、pushは、メモリ６２０にプッシュされたノードの経路を示す。
【００９３】
図１０は、ルートノード０の左側子ノード１を次に探索するノードと決定した場合を示す。図１０は、ノード１及びノード６がいずれも有効な探索対象であり、左側子ノード１をターゲットノードと決定した場合を示す。次に探索するノードが、ルートノード０の左側子ノード１であるので、ツリー探索ユニット６１０は、next＝０と設定する。
【００９４】
また、右側子ノード６は、後で探索するノードであるので、ツリー探索ユニット６１０は、push＝１と設定する。また、ツリーのルートノードでヒットされたので、ツリー探索ユニット６１０は、bit  stack＝１に設定する。ツリー探索ユニット６１０は、ノード６を後で探索するので、ノード６の経路をキー値として利用し、メモリ６２０にノード６に係わる情報を保存する。例えば、ツリー探索ユニット６１０は、ノード６の経路は１であり、経路の終了を示すコード１を利用して、４桁二進コード１１００をノード６の経路コードとして生成することができる。言い替えれば、１１００において、最も左側の１は、経路を示し、２番目の１は、経路の終了を示す。ツリー探索ユニット６１０は、１１００に対応するメモリ６２０のアドレスに、ノード６に係わる情報を保存する。
【００９５】
図１１は、ツリー探索ユニット６１０がノード１を探索することを示す。ツリー探索ユニット６１０は、current＝０と設定する。
【００９６】
図１２は、ツリー探索ユニット６１０がノード５をメモリ６２０にプッシュすることを示す。ノード１の次に探索するノードが右側子ノード２であるので、ツリー探索ユニット６１０は、next＝（０，１）と設定する。
【００９７】
また、左側子ノード５は、後で探索するノードであるので、ツリー探索ユニット６１０は、push＝（０，０）と設定する。また、ノード１からヒットされたので、ツリー探索ユニット６１０は、bit  stack＝（１，１）と設定する。ツリー探索ユニット６１０は、ノード５を後で探索するので、ノード５の経路をキー値として利用し、メモリ６２０にノード５に係わる情報を保存する。例えば、ツリー探索ユニット６１０は、ノード５の経路が（０，０）であり、経路の終了を示すコード１を利用して、４桁二進コード００１０をノード５の経路コードとして生成することができる。言い替えれば、００１０において、左側の００は、ノード５の経路を示し、１は、経路の終了を示す。ツリー探索ユニット６１０は、００１０に対応するメモリ６２０のアドレスに、ノード５に係わる情報を保存する。
【００９８】
図１３は、ツリー探索ユニット６１０がノード２を探索する過程を示す。ノード２が探索されるために、ツリー探索ユニット６１０は、current＝（０，１）と設定する。
【００９９】
図１４は、ツリー探索ユニット６１０がノード４をメモリ６２０にプッシュすることを示す。ノード２の次に探索するノードがノード２の左側子ノード３であるので、ツリー探索ユニット６１０は、next＝（０，１，０）と設定する。
【０１００】
また、ノード２の右側子ノード３は、後で探索するノードであるので、ツリー探索ユニット６１０は、push＝（０，１，１）と設定する。また、ノード２からヒットされたので、ツリー探索ユニット６１０は、bit  stack＝（１，１，１）と設定する。ツリー探索ユニット６１０は、ノード４を後で探索するので、ノード４の経路をキー値として利用し、メモリ６２０に、ノード４に係わる情報を保存する。例えば、ツリー探索ユニット６１０は、ノード４の経路が（０，１，１）であり、経路の終了を示すコード１を利用して、４桁二進コード０１１１をノード４の経路コードとして生成することができる。言い替えれば、０１１１において、左側の０１１は、ノード４の経路を示し、１は、経路の終了を示す。ツリー探索ユニット６１０は、０１１１に対応するメモリ６２０のアドレスに、ノード４に係わる情報を保存する。
【０１０１】
図１５は、ツリー探索ユニット６１０がノード３を探索する過程を示す。ノード３が探索されるために、ツリー探索ユニット６１０は、current＝（０，１，０）と設定する。
【０１０２】
図１６は、ツリー探索ユニット６１０がリーフ（leaf）ノード３を探索した以後の動作について説明するための図面である。ノード３がリーフノードであるので、ノード３は、子ノードを有さない。ツリー探索ユニット６１０は、bit  stackを参照し、反転させるビットを決定する。bit  stack＝（１，１，１）であるので、ツリー探索ユニット６１０は、現在経路コードの３番目ビットを反転させ、bit  stackの最も右側ビットを削除する。ツリー探索ユニット６１０は、ノード３の経路コードの３番目ビットを反転させ、次に探索するノードの経路を獲得する。ノード３の経路コードが（０，１，０）であるので、次に探索するノードの経路は、（０，１，１）になる。bit  stack＝（１，１，１）において、右側ビットが削除され、bit  stack＝（１，１）になる。
【０１０３】
図１７は、ツリー探索ユニット６１０がノード４を探索する過程を示す。図１６において、ツリー探索ユニット６１０が探索する次の経路コードとして（０，１，１）を獲得したので、ツリー探索ユニット６１０は、０１１１をキー値としてメモリ６２０のアドレスを獲得し、０１１１に保存されたノードデータを獲得する。０１１１に保存されたノードデータは、ノード４に係わる情報であるので、ツリー探索ユニット６１０は、ノード４に係わる情報を利用して、ノード４を探索することができる。
【０１０４】
図１８は、ツリー探索ユニット６１０がリーフノード４を探索した以後の動作について説明するための図面である。ノード４がリーフノードであるので、ノード４は、子ノードを有さない。従って、bit  stack＝（１，１）であるので、ツリー探索ユニット６１０は、ノード４の経路コードの２番目ビットを反転させ、次に探索するノードの経路を獲得する。ノード４の経路コードが（０，１，１）であるので、次に探索するノードの経路は、（０，０）になる。また、ツリー探索ユニット６１０は、ビットスタックの最後のビットを削除する。従って、bit  stack＝（１，１）において、右側ビットが削除され、bit  stack＝１になる。
【０１０５】
図１９は、ツリー探索ユニット６１０がノード５を探索する過程を示す。図１８において、ツリー探索ユニット６１０が探索する次の経路コードとして（０，０）を獲得したので、ツリー探索ユニット６１０は、００１０をキー値としてメモリ６２０のアドレスを獲得し、００１０に保存されたノードデータを獲得する。００１０に保存されたノードデータは、ノード５に係わる情報であるので、ツリー探索ユニット６１０は、ノード５に係わる情報を利用して、ノード５を探索することができる。
【０１０６】
図２０は、ツリー探索ユニット６１０がリーフノード５を探索した以後の動作について説明するための図面である。ノード５がリーフノードであるので、ノード５は、子ノードを有さない。従って、bit  stack＝１であるので、ツリー探索ユニット６１０は、ノード５の経路コードの最初ビットを反転させ、次に探索するノードの経路を獲得する。ノード５の経路コードが（０，０）であるので、次に探索するノードの経路は、１になる。また、ツリー探索ユニット６１０は、ビットスタックの最後ビットを削除する。従って、bit  stack＝１において１が削除される。
【０１０７】
図２１は、ツリー探索ユニット６１０がノード６を探索する過程を示す。図２１において、ツリー探索ユニット６１０が探索する次の経路コードとして１を獲得したので、ツリー探索ユニット６１０は、１１００をキー値としてメモリ６２０のアドレスを獲得し、１１００に保存されたノードデータを獲得する。１１００に保存されたノードデータは、ノード６に係わる情報であるので、ツリー探索ユニット６１０は、ノード６に係わる情報を利用して、ノード６を探索することができる。
【０１０８】
図２２は、ツリー探索ユニット６１０が探索を終了する過程を示す。ノード６がヒットされず（not  hit）、bit  stackに保存された値がないので、ツリー探索ユニット６１０は、ツリー探索を終了する。
【０１０９】
一方、前述の実施形態は、コンピュータで実行されるプログラムによって作成可能であり、コンピュータによって判読可能な媒体を利用して、前記プログラムを動作させる汎用デジタルコンピュータで具現される。また、前述の実施形態で使用されたデータの構造は、コンピュータ判読可能媒体に、多くの手段を介して記録される。また、前述の実施形態は、コンピュータによって実行されるプログラムモジュールのような、コンピュータによって実行可能な命令語を含む記録媒体の形態によって具現される。例えば、ソフトウェアモジュールまたはアルゴリズムによって具現される方法は、コンピュータが読み取って実行することができるコードまたはプログラム命令でもってコンピュータが読み取り可能な記録媒体に保存される。
【０１１０】
コンピュータ判読可能媒体は、コンピュータによってアクセスされる任意の記録媒体でもあり、揮発性及び不揮発性の媒体、分離型及び非分離型の媒体を含んでもよい。例えば、コンピュータ判読可能媒体は、マグネチック記録媒体（例えば、ＲＯＭ（read  only  memory）、フロッピーディスク、ハードディスクなど）及び光学的判読媒体（例えば、ＣＤ（compact  disc）−ＲＯＭ、ＤＶＤ（digital  versatile  disc）など）のような記録媒体を含んでもよいが、それらに制限されるものではない。また、コンピュータ判読可能媒体は、コンピュータ記録媒体及び通信媒体を含んでもよい。
【０１１１】
また、コンピュータで読み取り可能な複数の記録媒体が、ネットワークに連結されたコンピュータシステムに分散され、分散された記録媒体に保存されたデータ（例：プログラム命令語及びコード）が少なくとも１つのコンピュータによって実行される。
【０１１２】
本開示で説明された特定実行は、一実施形態であるのみ、いかなる方法によっても、本開示の範囲を限定するものではない。明細書の簡潔のために、従来の電子的な構成、制御システム、ソフトウェア、及び前記システムの他の機能的な側面の記載は省略する。
【０１１３】
前述の本開示の説明は、例示のためのものであり、本開示が属する技術分野の当業者であるならば、本開示の技術的思想や必須な特徴を変更せずとも、他の具体的な形態に容易に変形が可能であるということを理解することができるであろう。従って、以上で記述した実施形態は、全ての面において例示的なものであり、限定的ではないということが理解されなければならない。例えば、単一型と説明されている各構成要素は、分散されて実施されもし、同様に、分散されていると説明されている構成要素も、結合された形態でもっても実施される。
【０１１４】
本開示において、全ての例または例示的な用語（例えば、など）の使用は、単に本開示について詳細に説明するためのものであり、特許請求の範囲によって限定されるものではない以上、前記例、または例示的な用語によって、本開示の範囲が限定されるものではない。
【０１１５】
また、「必須な」、「重要に」のように具体的な言及がなければ、本開示に記載された構成要素は、本開示の実行のために必ずしも必要な構成要素ではないこともある。
【０１１６】
本開示の実施形態と係わる技術分野において当業者であるならば、前述の本質的な特性から外れない範囲で変形された形態に具現されるということを理解することができるであろう。
【０１１７】
本開示は、多様な変換を加えることができ、さまざまな実施形態を有することができるが、本開示は、明細書に記載された特定の実施形態によって限定されるものではなく、本開示の思想及び技術範囲に含まれる全ての変換、均等物ないし代替物が、本開示に含まれるものであると理解されなければならない。従って、開示された実施形態は、限定的な観点ではない説明的観点から理解されなければならない。
【０１１８】
本開示の範囲は、発明の詳細な説明よりは、特許請求の範囲によって示され、特許請求の範囲の意味及び範囲、そしてその均等概念から導き出される全ての変更または変形された形態は、本開示の範囲に含まれるものであると解釈されなければならない。
【０１１９】
本明細書に記載された「…部」、「モジュール」のような用語は、少なくとも１つの機能や動作を処理する単位を意味し、それらは、ハードウェアまたはソフトウェアによって具現されるか、あるいはハードウェアとソフトウェアとの結合によっても具現される。
【０１２０】
「部」、「モジュール」は、アドレッシングされる記録媒体に保存され、プロセッサによって実行されるプログラムによっても具現される。
【０１２１】
例えば、「部」、「モジュール」は、ソフトウェア構成要素、オブジェクト指向ソフトウェア構成要素、クラス構成要素及びタスク構成要素のような構成要素；プロセス、関数、属性、プロシージャ、サブルーチン、プログラムコードのセグメント、ドライバ、ファームウエア、マイクロコード、回路、データ、データベース、データ構造、テーブル、アレイ及び変数によっても具現される。
【０１２２】
本明細書において、「Ａは、ａ１、ａ２及びａ３のうち一つを含んでもよい」という記載は、Ａというエレメント（element）に含まれる例示的なエレメントが、ａ１、ａ２またはａ３であるという広い意味である。
【０１２３】
前記記載によって、エレメントＡを構成することができるエレメントが、必ずしもａ１、ａ２またはａ３に限られるというものではない。従って、Ａを構成することができるエレメントが、ａ１、ａ２及びａ３以外に例示されていない他のエレメントを排除するという意味に、排他的に解釈されるものではないということに留意しなければならない。
【０１２４】
また、前記記載は、Ａは、ａ１を含むか、ａ２を含むか、あるいはａ３を含んでもよいという意味である。前記記載がＡを構成するエレメントが、必ずしも所定集合内で選択的に決定されるということを意味するものではない。例えば、前記記載が、必ずａ１、ａ２及びａ３を含む集合から選択されたａ１、ａ２、またはａ３がコンポーネントＡを構成すると、制限的に解釈されるものではないということに留意しなければならない。
【０１２５】
また、本明細書において、「ａ１、ａ２または（及び）ａ３のうち少なくとも一つ」という記載は、「ａ１」、「ａ２」、「ａ３」、「ａ１及びａ２」、「ａ１及びａ３」、「ａ２及びａ３」、並びに「ａ１、ａ２及びａ３」のうち一つを示す。
【０１２６】
従って、「ａ１のうち少なくとも一つ、ａ２のうち少なくとも一つ、または（及び）ａ３のうち少なくとも一つ」と明示上に記載されていない以上、「ａ１、ａ２または（及び）ａ３のうち少なくとも一つ」という記述が「ａ１のうち少なくとも一つ」、「ａ２のうち少なくとも一つ」または（及び）「ａ３のうち少なくとも一つ」と解釈されるものではないということに留意しなければならない。
【産業上の利用可能性】
【０１２７】
本発明のツリーを探索する装置及びその方法は、例えば、グラフィックス関連の技術分野に効果的に適用可能である。
【符号の説明】
【０１２８】
６００：ツリー探索装置
６１０：ツリー探索ユニット
６２０：メモリ
【図３】
2017062787.tif 000003
【図５】
2017062787.tif 000004
【図１】
2017062787.tif 000005
【図２】
2017062787.tif 000006
【図４】
2017062787.tif 000007
【図６】
2017062787.tif 000008
【図７】
2017062787.tif 000009
【図８】
2017062787.tif 000010
【図９】
2017062787.tif 000011
【図１０】
2017062787.tif 000012
【図１１】
2017062787.tif 000013
【図１２】
2017062787.tif 000014
【図１３】
2017062787.tif 000015
【図１４】
2017062787.tif 000016
【図１５】
2017062787.tif 000017
【図１６】
2017062787.tif 000018
【図１７】
2017062787.tif 000019
【図１８】
2017062787.tif 000020
【図１９】
2017062787.tif 000021
【図２０】
2017062787.tif 000022
【図２１】
2017062787.tif 000023
【図２２】
2017062787.tif 000024