図面 (/)

技術 階層融合

出願人 イマジネイションテクノロジーズリミテッド
発明者 マシューハリソンジョンハウソンルークピーターソンスティーヴンクロウゼット
出願日 2017年3月21日 (3年10ヶ月経過) 出願番号 2017-054465
公開日 2017年10月12日 (3年4ヶ月経過) 公開番号 2017-188098
状態 未査定
技術分野 イメージ生成
主要キーワード トレーシングシステム プログラマブルチップ 入力階層 光線処理 分割平面 ハードウエア論理 水平リンク 累積バッファ
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2017年10月12日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (20)

課題

階層融合の技術を提供する。

解決手段

階層は、ノードマルチレベルリンク構造であり、階層は、処理されることになる1又は2以上の項目のセットに関連するデータを表す。複数の入力階層がある場合に、それは、入力階層を融合して融合階層を形成するための項目の処理の効率を改善することができる。階層は、融合されることになる入力階層内の2又は3以上の下位階層識別し、かつ識別された下位階層のノードを参照する融合階層の1又は2以上のノードを決定することによって融合される。融合階層の決定されたノードは格納され、融合階層の決定されたノードと識別された下位階層の参照されたノードとの間のリファレンスの表示も格納される。このようにして、融合階層は、項目の処理に使用するために形成される。

概要

背景

階層の形態のデータ構造データ項目の処理に有用とすることができる多くのシナリオが存在する。本発明の開示では、「階層」という語は、処理されることになる1又は2以上の項目のそれぞれのセットに関連するデータを表すノードマルチレベルリンク構造を指す。階層は、データ項目のグループが、条件が満足されたことに依存して類似の方式で処理されることになるデータを表すのに有用な方法とすることができる。この場合に、階層は、データ項目のグループを参照する1又は2以上のより高いレベルのノードを含むことができ、より高いレベルのノードは、項目のグループを処理するか否か及び/又はその方法を決定するために処理することができる。実行されている処理のタイプに依存して、これは、これらの項目を処理するか否か及び/又はその方法をグループの項目の各々に対して別々に決定するよりも効率的とすることができる。

階層が特に有用になる一例は、例えば、光線トレーシングを実行することによってグラフィックス処理ユニットで3次元(3D)シーンレンダリングする場合である。光線トレーシング方法は、典型的には、シーンに存在する形状との光線に対する交差試験を実施する段階を伴う。シーンの形状は、シーン内の構造の面を説明し、形状は、プリミティブによって表すことができる。プリミティブは、多角形、典型的には三角形であることが多いが、点、線、又はパッチのような他の形態を有することができる。シーン内の物体は、1又は2以上のそのようなプリミティブから構成することができ、一部の場合では、物体は、数千又は数百万のそのようなプリミティブから構成される場合がある。シーンは、典型的には多くの物体を含有する。光線トレーシング方法は、典型的には、シーン内の光線をトレースすることによってシーン内のプリミティブと光がどのように相互作用するかをモデル化する段階を伴う。光線は、起点と方向とを有する仮想光ベクトルと考えることができる。光線トレーシングレンダリング器の交差試験ユニットは、もしあるとすればプリミティブのどれに光線が交差することになるかを各光線に対して決定することができる。1又は2以上のシェーダーを実行して、例えば、プリミティブの材料特性及びプリミティブの面法線のようなファクタに基づいて、交差したプリミティブと光線がどのように相互作用するかを決定することができる。シェーダーの実行結果は、レンダリングされているシーンの画像のサンプル点の値を表すように累積バッファに格納することができる。シェーダーの実行は、シーン内の反射外観を決定するのに使用することができる交差プリミティブから放出されている1又は2以上の2次光線をもたらすことができる。各2次光線に対して、交差試験及びシェーディングを実行することができ、このシェーディングの結果は、累積バッファに既に格納された結果と結合して反射を含むように画像のピクセルを精緻化することができる。本方法は、多くの光線の反射に対して何度も繰り返すことができる。考えられる光線の反射の最大数が存在する場合がある。

上述のように、光線トレーシングシステムにおける交差試験は、どのプリミティブが光線の経路に沿って位置するかを決定する段階を伴う。プリミティブの各々に対して光線を試験するのではなく、シーン内のプリミティブを表すために階層(又は「加速構造」)を生成することができ、次に、階層に対して光線を試験することができる。加速構造は、3次元格子、kdツリーのような分割平面のツリー、軸位置合わせ境界ボックス階層のような境界容積の階層、又はオクト−ツリーのような幾何学的に定義された構造の形態を取る場合がある。例えば、階層は、階層の異なるレベルでのノードを有することができ、ノードは、レンダリングされているシーンの3D広がり内の特定の解像度での空間の領域を表すことができる。階層の最上位でのノードは、シーンを表す空間の大きい領域を表し、階層のより低いレベルでのノードは、シーンを表す空間内のより小さい領域を表す。階層内の第1のノードは、第1のノードと共に収容されている階層内の他のより低いレベルのノードへのリファレンス(すなわち、リンク)を有する。階層がツリー状構造を形成し、それによってリーフノードがより低いノードへのリファレンスを持たないように、階層の異なるレベルでのノード間にリファレンスがある。階層に存在するノードは、プリミティブが存在する領域を表す。例えば、境界容積階層(BVH)は、異なるサイズのノードを含み、一部のノードは、他のノードを境界付けし(シーン内のノード間の空間的関係を表す)、それらはまた、親−子接続、すなわち、リンクを有する(階層内のトポロジー関係を表す)。交差試験は、階層の最上位ノードを最初に試験することによって実行することができる。光線が特定のノードを逃した場合に、この光線は、階層内の特定のノードによって参照される(直接又は間接的に)より低いレベルのノードの全てを逃すことになるとこれらのより低いレベルのノードに交差試験を実施する必要なく推測される。光線が特定のノードに衝突した場合に、交差試験が、特定のノードによって参照されたノードに対して実行される。交差試験は、どのプリミティブが光線によって交差されるかを決定するために階層の適切なノードに対して繰り返される。交差試験は、次に、例えば、(プリミティブとの光線の)交差点のどれが光線の起点に最も近いかを決定することにより、交差プリミティブのどれが光線によって最初に交差されることになるかを決定することができる。個々のプリミティブに対して直ちにではなく、階層に対して交差試験を実施することにより、実行する必要がある交差試験の数を有意に低減することができることを認めることができる。

概要

階層融合の技術を提供する。階層は、ノードのマルチレベルリンク構造であり、階層は、処理されることになる1又は2以上の項目のセットに関連するデータを表す。複数の入力階層がある場合に、それは、入力階層を融合して融合階層を形成するための項目の処理の効率を改善することができる。階層は、融合されることになる入力階層内の2又は3以上の下位階層識別し、かつ識別された下位階層のノードを参照する融合階層の1又は2以上のノードを決定することによって融合される。融合階層の決定されたノードは格納され、融合階層の決定されたノードと識別された下位階層の参照されたノードとの間のリファレンスの表示も格納される。このようにして、融合階層は、項目の処理に使用するために形成される。

目的

この「発明の概要」は、「発明を実施するための形態」で以下に更に説明する選択した概念単純化された形式紹介するために提供する

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

複数の入力階層を融合して融合階層を形成する方法であって、該入力階層の各々が、ノードマルチレベルリンク構造であり、該入力階層の各々が、処理される1又は2以上の項目のそれぞれのセットに関連するデータを表し、融合されることになる前記入力階層内の2又は3以上の下位階層識別する段階と、前記識別された下位階層のノードを参照する前記融合階層の1又は2以上のノードを決定する段階であって、該識別された下位階層のうちの少なくとも1つの内部の該参照されたノードのうちの少なくとも1つが、該識別された下位階層のうちの該少なくとも1つの内部の1又は2以上のより低いレベルのノードを参照する前記決定する段階と、前記融合階層の前記1又は2以上の決定されたノードを格納し、かつ該融合階層の該決定されたノードと前記識別された下位階層の前記参照されたノードとの間のリファレンスの表示を格納し、それによって前記項目の処理に使用するための該融合階層を形成する段階と、を含むことを特徴とする方法。

請求項2

前記融合階層の前記決定されたノードに基づいて、該融合階層の該決定されたノードの上方に該融合階層のノードの1又は2以上のレベルを構築する段階を更に含むことを特徴とする請求項1に記載の方法。

請求項3

前記決定されたノードの上方の前記融合階層の前記1又は2以上のレベルは、ボトムアップ方式で構築されることを特徴とする請求項2に記載の方法。

請求項4

前記融合階層の最上位レベルが、単一ノードを有することを特徴とする請求項1から請求項3のいずれか1項に記載の方法。

請求項5

融合されることになる前記入力階層内の前記2又は3以上の下位階層は、該2又は3以上の下位階層の空間重複の量に基づいて識別されることを特徴とする請求項1から請求項4のいずれか1項に記載の方法。

請求項6

融合されることになる前記入力階層内の2又は3以上の下位階層を識別する前記段階は、該入力階層内の融合レベルでノードを識別する段階を含み、前記下位階層は、前記融合レベルで前記識別されたノードから下降する、ことを特徴とする請求項1から請求項5のいずれか1項に記載の方法。

請求項7

前記入力階層内の前記融合レベルを決定する段階を更に含むことを特徴とする請求項6に記載の方法。

請求項8

前記融合レベルは、異なるレベルでの前記入力階層からのノードの空間重複の量に基づいて決定されることを特徴とする請求項7に記載の方法。

請求項9

前記融合レベルは、前記入力階層からのノードの空間重複の前記量が閾値よりも上である最も低いレベルであるように決定されることを特徴とする請求項8に記載の方法。

請求項10

前記融合レベルは、前記入力階層の最上位レベルからの予め決められた数のレベル、前記入力階層の前記最上位レベルからの該入力階層内の総数の予め決められた割合のレベル、又はユーザ指定のレベル、であるように決定される、ことを特徴とする請求項7に記載の方法。

請求項11

最上位レベルと前記融合レベルの間の前記入力階層を構文解析して該入力階層のそれらのレベルに存在するリーフノードを識別する段階と、前記識別されたリーフノードを前記融合階層に含める段階と、を更に含むことを特徴とする請求項6から請求項10のいずれか1項に記載の方法。

請求項12

前記識別されたリーフノードを前記融合階層に含める前記段階は、入力階層の該リーフノードに平行移動を適用する段階を含むことを特徴とする請求項11に記載の方法。

請求項13

前記融合階層は、シーンレンダリングするのに使用するためのものであり、前記入力階層の各々が、前記シーン内でレンダリングされる1又は2以上の物体のそれぞれのセットの空間位置を表す、ことを特徴とする請求項1から請求項12のいずれか1項に記載の方法。

請求項14

前記シーンは、フレームシーケンスのうちの現在のフレームであり、前記入力階層の少なくとも1つが、1又は2以上の静的物体のセットの空間位置を表して以前のフレームから再使用される静的階層であり、前記入力階層の少なくとも別の1つが、1又は2以上の動的物体のセットの空間位置を表して前記現在のフレームをレンダリングするために構築される動的階層である、ことを特徴とする請求項13に記載の方法。

請求項15

前記入力階層の前記ノードのうちの1又は2以上に平行移動を適用する段階を更に含むことを特徴とする請求項13又は請求項14に記載の方法。

請求項16

光線トレーシングが、前記シーンをレンダリングするために前記融合階層を使用して実施され、前記光線トレーシングは、前記融合階層のノードに対して光線の交差試験を実施する段階を含む、ことを特徴とする請求項13から請求項15のいずれか1項に記載の方法。

請求項17

複数の入力階層を融合して融合階層を形成するように構成された階層融合モジュールであって、該入力階層の各々が、ノードのマルチレベルリンク構造であり、該入力階層の各々が、処理される1又は2以上の項目のそれぞれのセットに関連するデータを表し、階層融合モジュールが、融合されることになる前記入力階層内の2又は3以上の下位階層を識別し、かつ前記識別された下位階層のノードを参照する前記融合階層の1又は2以上のノードを決定し、該識別された下位階層のうちの少なくとも1つの内部の該参照されたノードのうちの少なくとも1つが、該識別された下位階層のうちの該少なくとも1つの内部の1又は2以上のより低いレベルのノードを参照する、ように構成された融合決ユニット、を含み、階層融合モジュールが、前記融合階層の前記1又は2以上の決定されたノードと、該融合階層の前記決定されたノードと前記識別された下位階層の前記参照されたノードとの間のリファレンスの表示とのストレージを引き起こすように構成される、ことを特徴とする階層融合モジュール。

請求項18

前記融合決定ユニットは、前記2又は3以上の下位階層の空間重複の量に基づいて、融合されることになる前記入力階層内の該2又は3以上の下位階層を識別するように構成されることを特徴とする請求項17に記載の階層融合モジュール。

請求項19

前記融合階層は、シーンをレンダリングするのに使用されるものであり、前記入力階層の各々が、前記シーン内でレンダリングされる1又は2以上の物体のそれぞれのセットの空間位置を表し、シーンをレンダリングする前記段階は、光線トレーシングを実施する段階を含む、ことを特徴とする請求項17又は請求項18に記載の階層融合モジュール。

請求項20

符号化されたコンピュータ可読コードを有するコンピュータ可読ストレージ媒体であって、前記コンピュータ可読コードは、該コードがコンピュータ上で実行された時に請求項1から請求項16のいずれか1項に記載の方法が実施されるようになっている、ことを特徴とするコンピュータ可読ストレージ媒体。

請求項21

集積回路製造システム内で処理された時に請求項17から請求項19のいずれか1項に記載の階層融合モジュールを製造するように該システムを構成する集積回路定義データセットが格納されたコンピュータ可読ストレージ媒体。

背景技術

0001

階層の形態のデータ構造データ項目の処理に有用とすることができる多くのシナリオが存在する。本発明の開示では、「階層」という語は、処理されることになる1又は2以上の項目のそれぞれのセットに関連するデータを表すノードマルチレベルリンク構造を指す。階層は、データ項目のグループが、条件が満足されたことに依存して類似の方式で処理されることになるデータを表すのに有用な方法とすることができる。この場合に、階層は、データ項目のグループを参照する1又は2以上のより高いレベルのノードを含むことができ、より高いレベルのノードは、項目のグループを処理するか否か及び/又はその方法を決定するために処理することができる。実行されている処理のタイプに依存して、これは、これらの項目を処理するか否か及び/又はその方法をグループの項目の各々に対して別々に決定するよりも効率的とすることができる。

0002

階層が特に有用になる一例は、例えば、光線トレーシングを実行することによってグラフィックス処理ユニットで3次元(3D)シーンレンダリングする場合である。光線トレーシング方法は、典型的には、シーンに存在する形状との光線に対する交差試験を実施する段階を伴う。シーンの形状は、シーン内の構造の面を説明し、形状は、プリミティブによって表すことができる。プリミティブは、多角形、典型的には三角形であることが多いが、点、線、又はパッチのような他の形態を有することができる。シーン内の物体は、1又は2以上のそのようなプリミティブから構成することができ、一部の場合では、物体は、数千又は数百万のそのようなプリミティブから構成される場合がある。シーンは、典型的には多くの物体を含有する。光線トレーシング方法は、典型的には、シーン内の光線をトレースすることによってシーン内のプリミティブと光がどのように相互作用するかをモデル化する段階を伴う。光線は、起点と方向とを有する仮想光ベクトルと考えることができる。光線トレーシングレンダリング器の交差試験ユニットは、もしあるとすればプリミティブのどれに光線が交差することになるかを各光線に対して決定することができる。1又は2以上のシェーダーを実行して、例えば、プリミティブの材料特性及びプリミティブの面法線のようなファクタに基づいて、交差したプリミティブと光線がどのように相互作用するかを決定することができる。シェーダーの実行結果は、レンダリングされているシーンの画像のサンプル点の値を表すように累積バッファに格納することができる。シェーダーの実行は、シーン内の反射外観を決定するのに使用することができる交差プリミティブから放出されている1又は2以上の2次光線をもたらすことができる。各2次光線に対して、交差試験及びシェーディングを実行することができ、このシェーディングの結果は、累積バッファに既に格納された結果と結合して反射を含むように画像のピクセルを精緻化することができる。本方法は、多くの光線の反射に対して何度も繰り返すことができる。考えられる光線の反射の最大数が存在する場合がある。

0003

上述のように、光線トレーシングシステムにおける交差試験は、どのプリミティブが光線の経路に沿って位置するかを決定する段階を伴う。プリミティブの各々に対して光線を試験するのではなく、シーン内のプリミティブを表すために階層(又は「加速構造」)を生成することができ、次に、階層に対して光線を試験することができる。加速構造は、3次元格子、kdツリーのような分割平面のツリー、軸位置合わせ境界ボックス階層のような境界容積の階層、又はオクト−ツリーのような幾何学的に定義された構造の形態を取る場合がある。例えば、階層は、階層の異なるレベルでのノードを有することができ、ノードは、レンダリングされているシーンの3D広がり内の特定の解像度での空間の領域を表すことができる。階層の最上位でのノードは、シーンを表す空間の大きい領域を表し、階層のより低いレベルでのノードは、シーンを表す空間内のより小さい領域を表す。階層内の第1のノードは、第1のノードと共に収容されている階層内の他のより低いレベルのノードへのリファレンス(すなわち、リンク)を有する。階層がツリー状構造を形成し、それによってリーフノードがより低いノードへのリファレンスを持たないように、階層の異なるレベルでのノード間にリファレンスがある。階層に存在するノードは、プリミティブが存在する領域を表す。例えば、境界容積階層(BVH)は、異なるサイズのノードを含み、一部のノードは、他のノードを境界付けし(シーン内のノード間の空間的関係を表す)、それらはまた、親−子接続、すなわち、リンクを有する(階層内のトポロジー関係を表す)。交差試験は、階層の最上位ノードを最初に試験することによって実行することができる。光線が特定のノードを逃した場合に、この光線は、階層内の特定のノードによって参照される(直接又は間接的に)より低いレベルのノードの全てを逃すことになるとこれらのより低いレベルのノードに交差試験を実施する必要なく推測される。光線が特定のノードに衝突した場合に、交差試験が、特定のノードによって参照されたノードに対して実行される。交差試験は、どのプリミティブが光線によって交差されるかを決定するために階層の適切なノードに対して繰り返される。交差試験は、次に、例えば、(プリミティブとの光線の)交差点のどれが光線の起点に最も近いかを決定することにより、交差プリミティブのどれが光線によって最初に交差されることになるかを決定することができる。個々のプリミティブに対して直ちにではなく、階層に対して交差試験を実施することにより、実行する必要がある交差試験の数を有意に低減することができることを認めることができる。

先行技術

0004

US8717357

発明が解決しようとする課題

0005

階層は、光線トレーシングシステムにおける交差試験の性能を改善するが、階層の生成は、有意な処理を必要とし、従って、例えば、処理電力及び時間に関してコストを生じる。光線トレーシングレンダリング器がリアルタイムフレームシーケンスをレンダリングする場合に、各フレームに対する新しい階層の生成は、画像をレンダリングすることができる速度及び品質に関してレンダリング器の性能に有意な悪影響を有する可能性がある。

課題を解決するための手段

0006

この「発明の概要」は、「発明を実施するための形態」で以下に更に説明する選択した概念単純化された形式紹介するために提供するものである。この「発明の概要」は、特許請求する主題の重要な特徴又は本質的な特徴を識別するように意図しておらず、特許請求する主題の範囲を制限するのに使用されるようにも意図していない。

0007

本明細書に説明する一部の実施例において、複数の入力階層は、融合階層を形成するために融合される。階層の融合は、多くの異なるシナリオにおいて有用である場合がある。本明細書の実施例に詳しく説明するように、光線トレーシングレンダリング器に使用するために階層を融合することができる。これらの実施例では、階層の融合は、光線の交差試験をより少ない階層に対して実行することができ、これが交差試験の一部として実行される処理の量を低減することができることを意味する。更に、複数の階層を融合する処理は、複数の階層のリーフノードの全ての統一された階層をゼロから再生成することよりも単純である場合がある。

0008

例えば、複数の入力階層を融合して融合階層を形成する方法を提供することができ、入力階層の各々は、ノードのマルチレベルリンク構造であり、入力階層の各々は、処理されることになる1又は2以上の項目のそれぞれのセットに関連するデータを表し、本方法は、融合されることになる入力階層内の2又は3以上の下位階層を識別する段階と、識別された下位階層のノードを参照する融合階層の1又は2以上のノードを決定する段階であって、識別された下位階層のうちの少なくとも1つの内部の参照されたノードのうちの少なくとも1つが、識別された下位階層のうちの少なくとも1つの内部の1又は2以上のより低いレベルのノードを参照する上記決定する段階と、融合階層の1又は2以上の決定されたノードを格納し、かつ融合階層の決定されたノードと識別された下位階層の参照されたノードとの間のリファレンスの表示を格納し、それによって項目の処理に使用するための融合階層を形成する段階とを含む。

0009

本方法は、光線トレーシングレンダリングシステムのようなレンダリングシステムに使用するのに特に適する場合がある。しかし、階層融合方法は、一部の例を与えると、画像又はビデオ処理システム(例えば、カメラパイプラインにおける使用に対して)又は音声処理システム内のレンダリングシステムの他のタイプ(例えば、光線トレーシング以外のラスター化に基づくレンダリングシステム)のような他の目的にも同様に使用することができる。本明細書に説明する階層融合方法は、より広範囲に使用することができ、例えば、階層融合方法は、いくつか名前を挙げると、物理シミュレーション衝突検出見通し線計算、放射輝度伝達、音響伝播液体及び粒子システム、及び光子マッピングのような以前の作動から空間情報の抽出を要求する方法に使用することができる。

0010

更に一般的には、階層は、表された空間にデータ点が均等に分布しないあらゆる種類のルックアップを実行するのに最も一般的に使用されるインデックス構造である。これは、多次元空間を含む。例えば、データが、点を説明する多次元ベクトルパラメータ化され、この点に対するデータがデータベースに格納される場合に、本明細書に説明する階層融合方法は、このデータを効率よく検索するのに有用であると考えられる。これは、パターン認識、並びに多次元クラスター化が実行されるか又は最も近い隣接クエリが使用される他の視覚及び人工知能AIアルゴリズムに適用可能である。

0011

更に、複数の入力階層を融合して融合階層を形成するように構成された階層融合モジュールを提供することができ、入力階層の各々は、ノートのマルチレベルリンク構造であり、入力階層の各々は、処理されることになる1又は2以上の項目のそれぞれのセットに関連するデータを表し、階層融合モジュールは、融合されることになる入力階層内の2又は3以上の下位階層を識別し、かつ識別された下位階層のノードを参照する融合階層の1又は2以上のノードを決定し、識別された下位階層のうちの少なくとも1つの内部の参照されたノードのうちの少なくとも1つが、識別された下位階層のうちの少なくとも1つの内部の1又は2以上のより低いレベルのノードを参照するように構成された融合決定ユニットを含み、階層融合モジュールは、融合階層の1又は2以上の決定されたノードと、融合階層の決定されたノードと識別された下位階層の参照されたノードとの間のリファレンスの表示とのストレージを引き起こすように構成される。

0012

本明細書に説明する一部の実施例において、それぞれの平行移動又は追加の変形を階層に対して決定することができる。これは、階層によって表された物体の空間位置を値が浮動小数点フォーマットである時に値の精度を増すより小さい値によって表すことを可能にする。平行移動は、例えば、世界空間に対して又は他の階層に対して階層を正確に位置決めするように決定することができる。階層が正しく処理される(例えば、階層を融合する)ために、決定された平行移動の表示は格納することができる。平行移動は、平行移動による階層の分割を回避又は低減するために、階層の決定されたレベルでのノードに関連するボクセル粒度で決定することができる。

0013

本発明の一実施形態は、シーンの複数の構成要素を部分的に定める幾何学的プリミティブ形状がAPIを通して提供される光線トレーシングシステムであり、プリミティブが表される座標系は、シーンの各構成要素に固有である。個々の変形又は平行移動は、各シーン構成要素に対して順番に提供することができ、シーンに対する視点又は他に指定された起点を更に提供することができる。光線トレーシングシステムは、次に、光線トレーシングをその内部で実行する指定された起点の回りのシーン構成要素のうちの1又は2以上を含む融合階層を構成することができる。

0014

上述の特徴は、当業者には明らかであろうが適切な場合に組み合わせることができ、かつ本明細書に説明する実施例の態様のいずれとも組み合わせることができる。

0015

ここで実施例を添付図面を参照して詳細に以下に説明する。

0016

添付図面は、様々な実施例を示している。当業者は、図面内に図示の要素境界(例えば、ボックス、ボックスのグループ、又は他の形状)が境界の一例を表すことを認めるであろう。一部の実施例では、1つの要素が複数の要素として描かれる場合があり、又は複数の要素が1つの要素として描かれる場合がある。共通参照番号は、適切な場合に図を通して類似の特徴を示すのに使用される。

図面の簡単な説明

0017

プリミティブが存在する3D空間の一部の例を示す図である。
図1に示す領域を表す階層のノードを示す図である。
光線トレーシングレンダリングシステムの構成要素を示すブロック図である。
光線トレーシングレンダリングシステム内で実行される作動を示す流れ図である。
光線トレーシングレンダリングシステム内の階層処理モジュールの構成要素を示す図である。
複数の入力階層を融合して融合階層を形成する方法を示す流れ図である。
2つの入力階層内のノードによって表される領域の例を示す図である。
図7に示す領域を表す2つの入力階層を示す図である。
2つの入力階層を融合するための融合階層のノードの追加を示す図である。
融合階層内でバイパスされる入力階層のノードを示していない図9aの概略図である。
図9bに示す融合階層のノードによって表されるボクセルを示す図である。
ボクセルの格子内の平行移動を示す図である。
図11に示す平行移動の前の階層のノードを示す図である。
図11に示す平行移動の後の階層のノードを示す図である。
ボクセルの格子内の最上位レベルボクセルの粒度での平行移動を示す図である。
図13に示す平行移動の後の階層のノードを示す図である。
階層に対する平行移動を決定する方法を示す流れ図である。
階層融合モジュールが実施されるコンピュータシステムを示す図である。
階層融合モジュールを具現化する集積回路を発生させるための集積回路製造システムを示す図である。

実施例

0018

ここで実施形態を単に例示的に以下に説明する。

0019

上述のように、階層を融合する方法を本明細書に説明する。本明細書に説明する実施例の多くは、シーンをレンダリングするために光線トレーシングを実行するための階層を使用するという関連であるが、階層を融合するための対応する方法は、他の適切な状況でも使用することができる。

0020

図1は、レンダリングされることになる領域102によって表されるシーンの一部の2D表現を示している。図1に明確に示していないシーン内の他の類似の領域も存在することができる。領域は、シーンのボクセルに位置合わせすることができ、又は位置合わせしなくてもよい。ボクセルは、シーン内のアドレス可能な位置を有する均一の大きさにされた空間容積である。ボクセルは高密度に詰めることができ、立方体であることが多いが、一部の実施例では他の形状を有することができる。一部の実施例において、領域は、例えば、空間内の位置及びサイズにより、又はボックスのサイズを推測することができる2又は3以上の位置によって説明される立方形の形状を有するボックスである。ボックスのいくつかの同等の表現が存在する。この2Dの実施例において、ボックス102は、ボクセルに位置合わせされ、シーン内の低解像度ボクセルに位置合わせされた4つの小さいボックス1040、1041、1042、及び1043に分割される。3Dの実施例では、例えば、ボクセルは、ボクセルを各軸に沿って半分に分割することによって8つのより小さいボクセルに分割することができ、従って、1つのレベルのボクセルに対応するように位置合わせされたボックスは、より低いレベルのボクセルに位置合わせされた8つのより小さいボックスに分割することができる。図1に示すシーンの一部の内部には5つのプリミティブが存在し、図1では1060から1064と示されている。これらのプリミティブの各々は、1080から1084と示されたそれぞれのボックスによって境界付けられる。この実施例では、ボックス108は、それぞれのプリミティブ106の軸位置合わせ境界ボックス(AABB)であるが、これらは必ずしもあらゆる特定のボクセル位置に対応するわけではない。ボックス102及び1040、1041、1042、及び1043も軸位置合わせ境界ボックスであるが、これらのボックスも、この実施例ではボクセル位置に対応する。

0021

図2は、図1に示すボックスを表すために生成することができる階層の実施例を示している。図2は、異なるレベルでのノードのリンクデータ構造としての階層を示している。階層のより高いレベルは、レンダリングされているシーン内の空間の大きいボックスを表すノードを含む。例えば、図2に示す最高レベルでのノード202は図1に示すボックス102を表している。ボックス102は4つのノード(1040−1043)を境界付けるが、これらのノードの2つ(1041及び1042)はいずれのプリミティブも含まない。ノード202の下のレベルでは、階層は、図1に示すボックス1040及び1043をそれぞれ表す2つのノード、すなわち、ノード2040及び2043を含む。ボックス1040は、2つのノード(1080及び1081)を境界付けて、ノード2040の下のレベルで、階層は、図1に示すボックス1080及び1081をそれぞれ表す2つのノード、すなわち、ノード2080及び2081を含む。同様にボックス1043は3つのノード(1082、1083、及び1084)を境界付けて、ノード2043の下のレベルで、階層は、図1に示すボックス1082、1083、及び1084をそれぞれ表す3つのノード、ノード2082、2083、及び2084を含む。階層のノードの各々は、レンダリングされているシーン内の対応するボックスの空間位置を表すデータを含む。階層のリーフノードではないノードも、階層のより低いレベルでのノードへのリファレンスを含む。これらのリファレンスは、各ノードに描かれた正方形セクションによって図2に表され、矢印は、これらのリファレンスが表すノード間のリンクを示している。図2に(及び以下に説明する図8、9a、及び9bの階層の類似の図に)より高いレベルでのノードから下のレベルのより低いレベルのノードの各々への矢印、例えば、ノード202からノード2040及び2043の両方に示す矢印を備えたリファレンスが示されている。階層は理解し易いようにこのように表されるが、一部の実施例では、これは、これらがメモリに格納される方式で階層のノード間のリンクを厳密に反映しない場合がある。例えば、より高いレベルでのノード(例えば、ノード202)から下のレベルでのノードの1つ(例えば、ノード2040)へのリンクが格納され、次に、このレベルの参照されたノード間の水平リンクを格納することができるように、例えば、ノード2040と2043の間のリンクを格納することができるように階層の構造をメモリに格納することができる。このようにして、ノード202とノード2043の間の直接リンクはないが、ノード202からノード2043へのリファレンスをノード202と2040の間のリンクとノード2040と2043の間のリンクとの組合せから推測することができる。これらのリンクは、階層のノードに対して実行される交差試験の順序を反映することができるので、この方式でリンクを格納することで交差試験の効率を改善することができる。このリンク構造に従って一部の実施例では、サブツリーの浅い部分を最初に、すなわち、階層の深い部分の前に試験することができる。

0022

階層は、オクトツリーのレベルのボクセルを有する疎らなオクトツリーを使用して構築することができ、リーフノードのボクセルを縮小して形状が密に境界付けられたボックス表現を提供することができる。単純にするために、図2に示す例示的階層は、3つのレベルだけを有するが、他の実施例では、階層は、異なる数のレベル、例えば、3つよりも多いレベルを有することができる。例えば、階層は、32レベルを有することができる。例示的に、階層のレベルを下に下げることは、各ボクセルが各軸に沿って2つに分割されることを意味し、それによって各ボクセルは、階層の次に下のレベルの8つのボクセルを境界付けて、ボックスがオクトツリーのボクセルに対応する場合に、階層の各ボックスは、階層の次に下のレベルの8つのボックスを境界付けることができる。従って、実施例では、最高レベル(LOD0)がシーンの3D空間に1つのボックスアドレスだけを有し、次に下のレベル(LOD1)は最大8ボックスを有し、次に下のレベル(LOD2)は最大64ボックスを有する等々である。

0023

階層は、トップダウン方式又はボトムアップ方式で構築することができる。本明細書に説明する実施例では、ボトムアップ方式が階層を構築するのに使用され、これは、ボトムアップ階層構築アルゴリズムが少ない反復(例えば、1通過だけ)でシーン形状を処理することができるからであるが、トップダウン階層構築アルゴリズムは、シーン形状を何度も反復しなければならない。ボトムアップ階層構築アルゴリズムは以下のように作動させることができる。
1.シーンプリミティブを反復して、条件が満足された時に、プリミティブの部分集合を含有するように境界領域を生成する。これは、シーン内のプリミティブを含有するリーフノードを生成する。
2.段階1で生成されたリーフノードを反復して、条件が満足された時に、ノードの部分集合を含有するように境界領域を生成する。これらのノードは、関わっているノードよりも増大し、階層の次に高いレベルを含むことになる。
3.ツリーの根が構築されるまで段階2を繰り返す。一部の実施例では、ツリーの根は単一ノードであるが、他の実施例ではツリーは複数の根ノードを有することができる。

0024

図3は、シーンをレンダリングするための光線トレーシングを実行するのに使用することができるグラフィックス処理システム300の高レベルブロック図を示している。グラフィックス処理システム300は、階層処理モジュール302、交差試験ユニット304、1又は2以上のシェーダー306、及びメモリ308を含む。メモリ308は、階層ストア310及び累積バッファ312を含む。グラフィックス処理システム300は他の構成要素を含むことができるが、明確にするためにこれらを図3には示していない。階層処理モジュール302、交差試験ユニット304、及びシェーダー306の各々は、ハードウエアソフトウエア、又はその組合せに実施することができる。一例では、階層処理モジュール302及び交差試験ユニット304は、専用ハードウエアに実施することができ、例えば、特定のタスクを実行するように構成された固定機能回路として実施することができる。ソフトウエアではなくハードウエアでこれらのブロックを実施することで、高処理速度、低処理電力、及び/又は低オンチップ面積の点からこれらのブロックの性能を改善することができる。この実施例では、シェーダー306は、グラフィックス処理ユニット(GPU)又は中央演算処理装置(CPU)のような処理ハードウエアで実行するように構成されたソフトウエアに実施することができる。ハードウエアではなくソフトウエアでシェーダー306を実施することで、シェーダー306の機能を適応化及び調節するという点で高い柔軟性を提供する。

0025

シーンをレンダリングするためのグラフィックス処理システム300の作動の概要を図4の流れ図に関して説明する。

0026

グラフィックスデータがグラフィックス処理システム300で受信される。特にグラフィックスデータは階層処理モジュール302で受信され、グラフィックスデータはシーン内でレンダリングされる物体のプリミティブを含む。階層処理モジュール302は、段階S402からS408に説明するようにグラフィックスデータのプリミティブを表すために階層を構築する。一部の実施例で階層がどのように構築されるかという詳細は、米国特許番号US8717357に説明されている。

0027

段階S402の前にいくつかの前処理をプリミティブに実行することができる。例えば、レンダリグされるシーンの広がりの外側にあるプリミティブを除くために切り取り及び選抜を実行することができる。段階S402で階層処理モジュール302は、プリミティブの各々の分割レベル(LOD)を選択する。LODは、プリミティブを存在させなくてはならない疎らなオクトツリーのレベル(階層のレベルが表す)を説明する整数(例えば、0と31の間)とすることができる。プリミティブに対するLODの選択は、異なる実施例で異なるものとすることができるヒューリスティックに基づく場合がある。プリミティブに対する適切なLODの選択の正確な詳細は、本発明の開示の範囲外であるが、概要として、その目的は、過度の空の空間なしに完全なプリミティブを含有するのに十分大きい1つのボックス(又は複数のボックス)にプリミティブを含有することである。例えば、これらの境界ボックスは、軸位置合わせとすることができる。プリミティブが大きい縦横比を有する及び/又は軸を外れる場合では(例えば、プリミティブが長く薄い三角形である場合)、その目的は、プリミティブの面をまとめて覆っている複数のより小さいボックスを選択することであり、それによって階層のリーフノードがプリミティブに密なフィットを形成しない場合を避ける。しかし、プリミティブが小さい縦横比を有する場合では(例えば、プリミティブが等辺プリミティブである場合)、プリミティブは、選択されたLODの単一ボックス(例えば、軸位置合わせ境界ボックス(AABB))内に含有することができる。

0028

段階S404で、プリミティブは、段階S402で選択されたLODのボックスを表す1又は2以上のリーフノードに加えられる。プリミティブがボックスの中心を通過しない場合でも、プリミティブは、プリミティブが交差する選択されたLODのいずれのボックス内にも存在すると考えられる。プリミティブが部分的にのみボクセルに重なる場合に、プリミティブによって覆われたボックスの量を示すための情報を格納することができる。このようにして、階層のリーフノードは、シーンの形状のプリミティブに密に適合することができる。

0029

リーフノードが決定された後に、段階S406で階層のより高いレベルが、例えば、ボトムアップ方式で構築される。このようにして、第1のレベルでのノードを一緒グループ分けすることができ、第1のレベルでのノードのグループを参照する次に上のレベルでのノードを生成することができる。この処理は、特定のレベルでのノードの全てに対して反復することができ、処理を生成されたノードに対して反復することができ、それによって階層全体が構築されるまで次のより高いレベルでのノードを生成する等々である。階層の最上位レベルは、単一ノードを含むことができる。他の実施例では、階層の最上位レベルは、単一ノードを含むことができるレベルの下の1つのレベルであるレベルとすることができる。すなわち、一部の実施例では、階層は、単一ノードを含む最上位レベルを有する必要はなく、階層の最上位が、単一統一ノードを含むことができるレベルよりも低い1つのレベルである場合に、効率的な交差試験をもたらすことができる。

0030

段階S408で、階層処理モジュール302は、階層を階層ストア310の格納のためのメモリ308に渡す。理解し易いように、メモリ308は、メモリの統一されたブロックとして図3に示されているが、一部の実施例では、メモリ308は、メモリの複数の異なるブロックとして実施することができ、例えば、これらの一部をシステムメモリとして実施することができ(例えば、動的ランダムアクセスメモリDRAM))及びこれらの一部をオンチップメモリとして実施することができる。例えば、メモリ308の階層ストア310は、オンチップメモリとして、すなわち、階層処理モジュール302、交差試験ユニット304、及びシェーダー306と同じチップに実施することができる。

0031

段階S410で、交差試験ユニット304は、階層に対して交差試験を実施して、レンダリングされる画像のピクセル位置を通過する光線によって交差されるプリミティブを決定する。上述のように、光線は、起点及び方向によって定義されるベクトルである。光線は、起点から光線の最大距離を設定する切り取り距離を有することができる。

0032

交差試験は、階層の最上位ノードを最初に試験することによって実行される。光線が特定のノードを逃した場合に、光線は、これらのより低いレベルのノードに交差試験を実施する必要なしに階層のこの特定のノードによって囲まれた(又は「境界付けられた」)より低いレベルのノードの全てを逃すと推測される。このようにして、下位階層の他の(より低い)ノードに交差試験を実施することなく、特定のノードに交差試験を実施することによって階層内の下位階層の根として特定のノードを有する全体の下位階層を光線が逃すと決定することができる。しかし、光線が特定のノードに衝突した場合に、交差試験は、特定のノードによって参照されたノードに対して、すなわち、特定のノードの下の下位階層のノードに対して行われる。交差試験は、どのプリミティブが光線によって交差されるかを決定するために階層の適切なノードに対して行われる。交差試験は、例えば、プリミティブとの光線の交差点のどれが光線の起点に最も近いかを決定することにより、交差されるプリミティブのどれが最初に光線によって交差されるかを決定することができる。交差試験の正確な詳細は、異なる例において異なる場合がある。

0033

段階S412で、光線が交差するプリミティブとどのように光線が相互作用すべきかを決定するために1又は2以上のシェーダー306を実行することができる。プリミティブとの光線の相互作用は、プリミティブの特性、例えば、プリミティブの材料特性及びプリミティブの面法線のような他のファクタに基づく場合がある。シェーダー306は、メモリ308からプリミティブの特性を検索することができる。シェーダー306は、例えば、グラフィックス処理システム300で処理ユニット上で実行されるソフトウエアプログラムとして実施することができる。これは、シェーダープログラムの適応を容易にし、それによってハードウエアの変更を必要とすることなく光線とプリミティブの間の相互作用に異なる効果を使用することができる。

0034

段階S414で、シェーダー306の実行の結果は、レンダリングされている画像のサンプル点の値を表すために累積バッファ312に格納される。

0035

更に、シェーダー306の実行は、シーン内の反射のような照明効果の外観を決定するのに使用することができるプリミティブから放出される1又は2以上の2次光線をもたらすことができる。これらの2次光線は、交差試験ユニット304に戻される(図3及び4の破線で示す)。各2次光線に対して、交差試験及びシェーディングを実行することができ、このシェーディングの結果は、累積バッファに既に格納された結果と結合され、例えば、シーンの反射の効果を含むように画像のサンプル点値を精緻化する。本方法は、光線の多くの反射に対して何度も繰り返すことができる。考えられる光線の反射の最大数が存在する場合がある。更に、上述のように、光線は、光線が切り取り距離までも遠くに移動した時に、例えば、更に別の反射のための光線処理の更に別の反復を中止するように切り取るような切り取り距離を有することができる。

0036

従って、図4に示す方法の最後で、累積バッファ312は、画像のピクセル値を表すのに使用することができる光線トレーシングの結果を格納する。画像は、次に、必要に応じて使用することができ、例えば、ディスプレイ上に光線に表示するか又はメモリに格納するか又は例えばインターネットのような通信ネットワーク上で別のデバイスに送信することができる。

0037

一例では、レンダリングされているシーンは、フレームのシーケンスのうちの現在のフレームである。例えば、フレームのシーケンスは、リアルタイムアニメーションに使用することができ、例えば、リアルタイムでユーザがゲームアプリケーションと相互作用する場合にゲームアプリケーションと共に使用することができ、相互作用の結果は、リアルタイムで表示される。そのようなシナリオでは、グラフィックス処理システムは、効率よく、例えば、ユーザがレンダリングにおける遅延に気付かないように十分迅速に、かつ移動デバイス、例えば、コスト、大きさ、重量、バッテリ寿命のような制約のためにかなり限定された処理リソースしか持たない場合があるスマートフォン又はタブレットのようなデバイスに多くの処理を実施する必要なくフレームをレンダリングするように適応させることができる。

0038

シーン内のプリミティブの階層の構築は、光線トレーシング方法を実施するのに必要な時間の有意な部分を必要とする場合がある。フレームのシーケンスからのフレームは、先行フレームから動かなかった一部の物体を含むことが多い。フレームのシーケンスのうちのフレームをレンダリングするのに必要な時間を低減するために、先行フレームと現在のフレームの間で静的な物体の階層を再使用することができ、従って、現在のフレームに対して階層が再構成されることはない。しなし、先行フレームと現在のフレームの間で動いた物体では(すなわち、「動的」物体では)、階層が、現在のフレームの動的物体に対して構築される。従って、現在のフレームの物体を表す1つよりも多い階層が存在する場合がある。現在のフレームの物体のそれぞれのセットを表す複数の階層を有するための他の理由も存在する可能性がある。例えば、以下に詳しく説明するように、物体(例えば、ゲーム内自動車又は建物)は、常にプリミティブの特定のセットによって表すことができる。この場合に、階層を1又は2以上の物体の異なるセットに対して別々に事前決定することができ、それによって物体がフレームに現れる度に階層を再構成するのではなく、これらの物体を容易にシーンに追加することができる。この場合に、以下に詳細に説明するように、平行移動を階層に適用することができ、それによって現在のフレームの階層の全ての空間位置は、共通の軸のセットに対して定義され、例えば、これらが全て世界空間の点で定義される。

0039

複数の階層を有することは、シーンの階層を生成するのに使用される時間及び処理電力の点で有用とすることができるが、複数の階層を有することは、光線トレーシングレンダリング器での交差試験の効率に悪影響を及ぼす場合がある。特に、交差試験は、シーンに定義された階層の各々に適用しなければならない。これは、単一階層がシーン内の物体に対して構築された場合に実行される交差試験の数が多くなる場合があることを意味する。点を示すための非常に単純な例として、シーンの形状の全てを逃す方向の光線では、単一階層が定義された場合に、光線は階層の根ノードに対して試験され、交差試験に失敗することがあり、この場合に、更に別の交差試験はこの光線に実行されず、光線がシーン内のプリミティブの全てを逃したことが既知である。しかし、複数の階層が存在する場合に、実行することができる最少数の交差試験は、階層の根ノードの各々に対して光線を試験するためのものである。

0040

本明細書に説明する実施例では、複数の階層は、融合階層を形成するために一緒に融合される。これは、交差試験の効率を改善する傾向があるシーンの個別の階層の数を低減するが、シーンの形状からの階層の全再構成を必要としない。

0041

図5はシステム300を示しているが、図3に示されていなかった一部の更に別の構成要素が図5には示されている。階層処理モジュール302は、階層発生ユニット502及び階層融合モジュール504を含む。階層融合モジュール504は、融合決定ユニット506及び融合レベル決定ユニット508を含む。本発明のシステムはまた、平行移動ユニット510を含む。本明細書に説明する実施例において、階層処理モジュール302の構成要素(すなわち、構成要素502、504、506、及び508)及び平行移動ユニット510は、ハードウエアに、例えば、階層処理モジュール302を効率的にする固定機能回路として実施される。他の実施例では、階層処理モジュール302の構成要素の1又は2以上又は平行移動ユニット510は、ソフトウエアに実施することができる。

0042

階層処理モジュール302の作動を図6に示す流れ図を参照して説明する。段階S602で、レンダリングされているシーンのデータが階層処理モジュール302の階層発生ユニット502で受信される。このデータは、シーン内の物体を説明する形状データ(例えば、プリミティブ)である。

0043

段階S604で、階層発生ユニット502がシーンの1又は2以上の階層を構築し、及び/又は階層処理モジュール302がシーンの1又は2以上の階層を受信する。例えば、上述のように、シーンがフレームのシーケンスの1つのフレームである場合に、階層発生ユニット502は、シーンの動的コンテンツの階層を構築することができ、シーンの静的コンテンツの階層は、以前のフレーム(例えば、すぐ前の先行フレーム又は他の以前のフレーム)から再使用することができ、従って、階層ストア310から検索することができる。階層は、いくつかのソースから来ることができ、最も一般的なものは以前のフレームであるが、オフラインで構築することができ、ゲームアセットを含むことができ、又は分散階層構築システムの一部として別の階構築モジュールで構成することができる。階層発生ユニット502によって構築された階層は、次の使用ために階層ストア310に格納することができる。

0044

段階S604に続いて、階層処理モジュール302は、複数の階層(例えば、ユニット502によって生成及び/又はメモリ308から検索)へのアクセスを有し、段階S606でこれらの階層が階層融合モジュール504に入力される。階層融合モジュール504は、融合階層を形成するために入力階層を融合するように作動する。

0045

理解し易いように、階層融合モジュール504の作動を2つの入力階層が融合される単純な例に関して図7から図10を参照して説明するが、同じ原理を2つよりも多い入力階層を融合するために他の実施例で使用することもできる。

0046

図7は、2つの入力階層内のノードによって表されるボックスを示し、図8は、図7に示すボックスを表す2つの入力階層を示している。特に図7は、実線で第1の階層に関連するボックスを示している。これらのボックスは、高レベルボックス702、2つの中間レベルボックス7040及び7041及び5つの低レベルボックス7060、7061、7062、7063、及び7064を含む。光線がボックス702に交差しない場合に、ボックス7040又は7041に対して具体的に交差試験を実施することなく光線がボックス7040又は7041に交差しないことが既知であるように、ボックス702は、ボックス7040及び7041を完全に境界付ける。同様に、光線がボックス7040に交差しない場合に、ボックス7060又は7061に交差試験を実施することなく光線がボックス7060又は7061に交差しないことが既知であるように、ボックス7040は、ボックス7060及び7061を完全に境界付ける。同様に、ボックス7041は、ボックス7062、7063、及び7064を完全に境界付ける。この第1の階層は、図8に示すノードの左手セクションによって表される。特に、ノード802、8040、8041、8060、8061、8062、8063、及び8064は、図7に示すボックス702、7040、7041、7060、7061、7062、7063、及び7064をそれぞれ表している。

0047

図7は、破線で第2の階層に関連するボックスを示している。これらのボックスは、高レベルボックス712、2つの中間レベルボックス7140、及び7141、及び2つの低レベルボックス7160及び7161を含む。光線がボックス712に交差しない場合に、ボックス7140又は7141に具体的に交差試験を実施することなく光線がボックス7140又は7141に交差しないことが既知であるように、ボックス712は、ボックス7140及び7141を完全に境界付ける。同様に、光線がボックス7140に交差しない場合に、ボックス7160又は7161に交差試験を実施することなく光線がボックス7160又は7161に交差しないことが既知であるように、ボックス7140は、ボックス7160及び7161を完全に境界付ける。この第2の階層は、図8に示すノードの右手側セクションによって表される。特にノード812、8140、8141、8160、及び8161は、図7に示すボックス712、7140、7141、7160、及び7161をそれぞれ表している。

0048

一例として、図8に示す階層の1つは、シーン内の静的物体のためのものとすることができ、以前のフレームから再使用することができ、階層のもう1つは、シーン内の動的物体のためのものとすることができる。階層を別々に構築する他の理由が存在する可能性がある。2つの階層が最高レベルの高程度の空間重複を有し、すなわち、ボクセル702及び712が高程度の空間重複を有することが図7を見ることができる。

0049

2つの階層は、階層融合モジュール504に入力される。段階S608で、階層融合モジュール504は、融合される入力階層内の下位階層を識別する。例えば、下位階層は、入力階層からの下位階層の空間重複の量に基づいて識別することができる。各下位階層は、階層のサブセクションである。これらの実施例では、下位階層が、高程度の空間重複を有する入力階層から見出される(例えば、下位階層の最上位レベルのボックスの空間重複は、下位階層のこれらのボックスの合計容積閾値(50%など)よりも大きい)。これは、下位階層が融合に適切であるという表示を提供する。図5及び6に示す実施例では、下位階層を識別するために、融合レベル決定ユニット508が、融合される下位階層の融合レベルを決定し、それによって融合レベルの下位階層の根ノードを識別する。融合レベルは、階層のノードによって表されるボックスが定義されるオクトツリーのレベルの点で定めることができる。融合レベルの決定は、異なるレベルの入力階層からのノードの空間重複の量に基づく場合がある。例えば、融合レベルは、入力階層からのノードの空間重複の量が閾値よりも上である最低レベルである、例えば、特定のレベルの入力階層からのノードに関連のボックスは、50%以上互いに重なる時に決定することができる。下位階層は、融合レベルの識別されたノードから下降する。図7及び8に示す実施例では、融合レベル決定ユニット508は、融合レベルが図8に示す3つのレベルの最上位であると決定する。この理由は、最上位レベルノード802及び812が、高程度の空間重複を有するボックス702及び712に関連するためであり、一方、入力階層のより低いレベルのノードに関連のボックスは互いに重なり合わない。決定された融合レベルは、融合決定ユニット506に提供される。

0050

他の実施例では、融合レベルを入力階層からのボックスの空間重複に基づかない方式で決定することができる。例えば、融合レベルは、入力階層の最上位レベルから予め決められた数のレベルになると決定することができる。他の実施例では、融合レベルを入力階層の最上位レベルから入力階層のレベルの総数の予め決められた比率になると決定することができる。更に別の実施例では、融合レベルがユーザ指定のレベルに決定されるように、融合レベルをユーザによって指定することができる。

0051

更に、一部の実施例では、融合レベルが必ずしも決定されず、融合される下位階層のノードは、必ずしも入力階層内の同じレベルではない。この場合に、下位階層の根ノードをこれらのノードが階層に存在するレベルにかかわらず、異なる階層からのノードの空間重複に基づいて決定することができる。これは、異なる入力階層内の異なるレベルからの下位階層の融合を可能にするための柔軟な方法を提供する。

0052

段階S610で、融合決定ユニット506は、(例えば、融合レベルの)識別された下位階層の最上位レベルと根の間の入力階層を構文解析し、入力階層のこれらのレベルに存在するリーフノードを識別する。いずれの識別されたリーフノードも、融合階層に含まれる。

0053

階層は、軸の異なるセットに点で定義された空間位置を有することができる。例えば、動的物体のセットの階層は、物体のセットの中心位置に対して定義された空間位置を有することができる。この物体のセットをシーン空間(又は「世界空間」)に配置するために、融合決定ユニット506は、以下に詳細に説明するように、平行移動ユニット510によって階層に対して決定された平行移動に従って階層の空間位置に平行移動を適用することができる。階層のノードがシーン空間に平行移動された状態で、これをこの空間で定義された空間位置を有する他の階層と融合することができる。階層に対する平行移動の表示は、平行移動ユニット510によって入力階層の各々に決定することができる。

0054

段階S612で、平行移動が入力階層に示された場合に、融合決定ユニット506は、段階S610で識別されたいずれのリーフノードにも及び入力階層の融合レベルのいずれのノードにも平行移動を適用する。このようにして、異なる入力階層からのノードに関連するボックスの空間位置が、これらが正確に融合されるように軸の同じセットの点で定義される。一部の入力階層が平行移動を必要とせず、一部の場合では、入力階層のどれも平行移動を必要とせず、これらの場合では段階612が実行されないことに注意されたい。

0055

段階S614で、融合決定ユニット506は、融合階層の1又は2以上のノードを決定する。融合階層の決定されたノードは、例えば、融合レベルよりの1つ下のレベルで入力階層の識別された下位階層のノードを参照する。例えば、図9aは、図8に示す2つの入力階層を融合すると決定されたノード902を示している。この単純な実施例では、1つのノードだけが段階S614で決定されるが、他の実施例では融合階層の多くのノードを段階S614で決定することができることを認めることができる。上述のように、融合レベルは、ノード802及び812が入力階層に存在するレベルであると決定されたものである。従って、決定されたノード902は、入力階層の融合レベルよりも1つ下のレベルに存在するノード8040、8041、8140、及び8141を参照する。これらのリファレンスは、図9aにノード902からの矢印によって示されている。

0056

段階S616で、融合階層のより高いレベルが構築される場合に、階層融合モジュール504は、融合階層の決定されたノードを階層発生ユニット502に提供し、階層発生ユニット502が、段階S614で決定されたノードの上に融合階層のノードの1又は2以上のレベルを構築する。融合階層のより高いレベルの構築は、階層発生ユニット502が動的データの階層を例えばボトムアップ方式で構築するのと同じ方法で実行することができる。得られる融合階層の最上位レベルは、単一ノードを含むことができる。これに代えて、融合階層の最上位レベルは、1つよりも多いノードを含むことができる。階層の最上位レベルに単一ノードを有することは、融合階層に対して光線を試験するために実行される交差試験の最小数が1つであることを意味するが、融合階層の最上位レベルが1つよりも多いノードを含む場合に、融合階層に対して光線を試験するために実行される交差試験の最小数は、1よりも多くなる。しかし、光線のほとんど全てを融合階層の最上位レベルの単一ノードに対する交差試験に渡す場合に、階層に対して実行される交差試験の総数は、単一ノードが融合階層に含まれるレベルよりも1つ低いレベルで階層の最上位を有するのではなく最上位レベルを含むことによって増加することがある。従って、融合階層のノードがシーンの非常に大きい割合に拡散する場合に、単一ノードを含む融合階層のレベルは、シーンの非常に大きい割合を覆うボックスに対応することになる。従って、光線の非常に大きい割合が、この単一ノードに対する交差試験にパスし、それによって融合階層にこの単一ノードを含むことによって多くの情報は獲得されず、実際には、単一ノードが含まれるレベルよりも1又は2以上下のレベルで融合階層セットの最上位レベルを有することが有利になる(融合階層に対して実行される交差試験の数の点で)。

0057

図9aに示す単純な実施例では、融合階層の1つのノード(ノード902)だけが段階S614で決定され、それによって段階S616でノード902の上に構築する融合階層のレベルはなくなる。

0058

融合レベル、又は融合レベルの上の入力階層のノードは、融合階層に対する交差試験をする必要がない。融合階層の概略図が図9bに示されている。ノード902からのリファレンスが、融合レベル又は融合レベルの上の入力階層のノードをバイパスする。従って、交差試験が実行される時に、光線が交差に関して試験される階層構造図9bに示されている。光線がノード902に対する交差試験に失敗した場合に、図9bに示す他のノードのいずれに対しても光線に交差試験を実施する必要はない。

0059

図10は、図9bに示す融合階層のノードによって表されるボックスを示している。ボックス1002は、融合階層のノード902に対応する。図10に示す他のボックスは、図7に示す対応するボックスと同じである。交差試験が図9bに示す融合階層に対して確実に実行されるように、ボックス1002が図10に示す他のボックスの全てを境界付けることを見ることができる。

0060

段階S618で、階層融合モジュール504は、段階S614又は段階S616で決定されていた融合階層の1又は2以上の決定されたノードを階層ストア310に格納させる。更に、階層融合モジュール504は、融合階層の決定されたノードと入力階層の参照されたノード間のリファレンスの表示(並びに融合階層の複数のレベルが構築された場合の融合階層のノード間のリファレンス)を階層ストア310に格納させる。図7から10に示す実施例に関して、段階S618は、ノード902及びノード902からノード8040、8041、8140、及び8141へのリファレンスを階層ストア310に格納する段階を伴う。ノードのデータは、ノードによって表されるボックスの空間位置を定めるデータを含む。ノードがリーフノードである場合に、低ノードへのリファレンスは格納されないが(これは、階層に低参照ノードがないためである)、1又は2以上のプリミティブの表示は、リーフノードによって表されたボックスに存在するプリミティブを示すためにリーフノードと共に格納される。

0061

融合階層が階層ストア310に格納された状態で、シーンをレンダリングするために融合階層を使用して、例えば、融合階層のノードに対して光線に対する交差試験を実施する段階を含む上述して図4に示す段階S410、S412、及びS414に従って光線トレーシングを実行することができる。

0062

上述のように、融合レベル又は融合レベルの上の入力階層のノード(例えば、ノード802及び812)は、融合階層に対して交差試験の必要はないが、入力階層は、次のフレームに使用することができるのでメモリ308の階層ストア310に保持することができる。従って、入力階層はメモリに格納され、加えて融合階層の決定されたノード及びそのリファレンスがメモリに格納される。

0063

一部の実施例では、シーン内の入力階層の全てを融合階層に融合することができる。他の実施例では、シーン内の入力階層の部分集合を融合階層に融合することができる。更に、一部の実施例では、シーンの入力階層を1つよりも多い融合階層に融合することができる。1又は2以上の融合階層は、フレームのシーケンスのうちの各フレームに対して決定することができる。

0064

図6の流れ図に関して上述した方法は、2又は3以上の入力階層の融合階層を形成させ、かつ階層ストア310に格納させる。融合階層の決定されたノードによって参照される入力階層のノードのうちの少なくとも1つが、それ自体が入力階層内の1又は2以上のより低いレベルのノードを参照する場合に、階層の融合は、入力階層のリーフノードの全てから階層を再構成するよりも少ない処理を伴う可能性は低い。すなわち、入力階層の識別された下位階層の低い構造が、融合階層に維持され、再計算する必要はない。

0065

上述の実施例では、階層のノードがそれぞれのボックスを表すように階層はボックス階層であり、上述の実施例では、ノードは、例えば、オクトツリー構造のレベルに対応する異なるレベルでの軸位置合わせ境界ボックス(AABB)を表している。オクトツリー構造では、レベルを下に動くことは、オクトツリーのレベルの各ボックスが次に下のレベルで8つのボックスを境界付けるように各軸に沿って(例えば、x、y、及びz軸に沿って)ボックスを半分に分割することを意味する。他の実施例では、ノードによって表されるボックスの構造は、オクトツリーでなくてもよく、代わりにより柔軟性を持たせて定めることができるが、階層は、階層内の第1のレベルの第1のノードがより低いレベルの1又は2以上のノードを参照する場合に、第1のノードによって表されるボックスがより低いレベルでのノードのボックスを完全に境界付ける特性を有する。このようにして、試験(例えば、交差試験)を第1のレベルの第1のノードに対して実行することができ、試験の結果を使用して、より低いレベルの参照されたノードの結果を推測することができる。

0066

上述の方法は、シーンをレンダリングするための光線トレーシングレンダリング器での階層の使用に関するものである。しかし、対応する方法を2又は3以上の入力階層を融合するために有用とすることができる他の関連に使用することができる。例えば、階層の融合は、光線トレーシングレンダリング器以外のレンダリングシステムに使用することができ、又は音声処理システム内に、又は処理されることになる1又は2以上の項目のそれぞれのセットに関連するデータを表すために階層を使用することができるあらゆる他の処理システムに使用することができ、それによって階層のノードのマルチレベルリンク構造を使用して、項目の処理を単純化することができる。上記に与えられた実施例の空間位置、又は周波数空間カラー空間、又は4D空間時間のような何らかの他の「空間」における位置のようなデータ項目のある一定の特性に基づいてデータ項目をグループ分けすることができる場合に階層は有用とすることができる。階層は、トップダウン方式で階層のノードを処理することによってデータ項目の特性に基づくデータ項目の階層処理を可能にする。例えば、階層のノードにグループ分けされるカメラピクセル値が、カラー空間(例えば、RGB空間又はYUB空間など)のピクセル値の位置に基づく場合に、処理作動が、カラー空間の異なるセクションからのピクセルを様々に処理するように意図する場合に、ピクセルがどのように処理されるかを迅速に決定するために階層は有用とすることができる。データ項目を階層構造にグループ分けするのに使用することができるデータ項目の適切な特性の多くの例がある。更に、複数の階層が存在することができ、更に階層を融合する処理効率を改善することができる多くの異なるシナリオが存在し、入力階層を融合するための本明細書に説明する方法を使用することができる。一般的に、上述の方法は、光線トレーシングの関連から抜粋した時に、入力階層の各々が処理されることになる1又は2以上の項目のそれぞれのセットに関連するデータを表す融合階層を形成するために複数の入力階層を融合する段階を提供し、入力階層の各々は、ノードのマルチレベルリンク構造である。形成される融合階層は、項目の処理に使用するためとすることができる。少ない階層を形成するための(例えば、単一融合階層を形成するための)複数の階層の融合は、項目が処理される効率を改善することができる。

0067

上述の実施例では、個別の物体のセットに対して個別の階層を定めることができ、例えば、ゲームの異なるキャラクター又は物体は、異なるそれぞれの予め決められた階層を有することができる。物体の空間位置は、浮動小数点フォーマットで定めることができる。物体の位置が世界空間軸の点で定義される場合に精度の問題が発生することがある。これは、世界空間軸の起点からの物体の距離が、物体のサイズよりも有意に大きい場合があるためであり、それによって物体の位置を表す浮動小数点値は物体のサイズよりも有意に大きい場合があり、それによって物体の位置を表す浮動小数点値は、物体のサイズに比べて大きい場合がある。浮動小数点数が境界の2のべき乗を超えて増加する度に精度は半分になり、位置を表すために大きい浮動小数点数を使用することは、これらの位置が定義される精度を低減する。

0068

単純な例として、ゲームアプリケーションにおいて、2つのキャラクターを世界空間の起点から直線に沿って同じ速度で3メートル離れて移動することができる(0.0f、0.0f、0.0f)。キャラクターが起点から離れて移動する時に位置値が交差する各々の2のべき乗の境界により、位置を表す浮動小数点数の精度は降下する(特に精度は交差された各々の2のべき乗境界の半分である)。最終的には、2つのキャラクターの位置は、精度誤差のために見分けがつかなくなる。これは極端な実施例であるが、物体が起点から離れた時に世界空間軸の点で定義される位置のために発生することがある精度誤差を示している。これが問題を引き起こす場合がある別の例は、2つの三角形プリミティブが単一クワッドを説明する場合である。この場合に、2つのプリミティブの間の共有される縁部の間に間隙が見られるように精度が劣化する場合に、クワッドの錯覚は、2つの独立した三角形が明らかになる場合に直ちに失われる。精度での誤差は、他の例における他の問題を引き起こす場合がある。

0069

発生する精度誤差を低減するために、シーン内の位置を定めることができる位置値に対する上限が存在するように世界空間のサイズを規制することができる。換言すると、シーンの広がりを設定することができ、それによって形状がシーンの広がり内に留まる。物体が許容できないほど世界空間起点から離れる場合に発生する精度誤差を低減する別の方法は、物体の位置値が小さい(及び従って正確な)浮動小数点数によって定義されるように起点を移動することである。

0070

レンダリングされているシーンがフレームのシーケンスからの現在のフレームであり、かつシーン内の形状の一部が静的形状である時に、静的形状が以前のフレームの起点の点で定義された位置データを有するので現在のフレームの起点を移動することは問題が多くなる。従って、現在のフレームの起点が移動する場合に、静的及び動的物体は、例えば、シーン内の物体のプリミティブに交差試験を実施する時に、問題を引き起こす場合がある異なる起点の点で定義された位置を有することがある。

0071

現在のフレームの起点を移動するのではなく、オフセット(すなわち、平行移動)を各階層に、すなわち、物体の各セットに決定することができる。これは、平行移動された起点に関して物体の位置値が定義されることを可能にし(すなわち、物体のセットの位置値に「流体」起点が存在する場合がある)、それによって小さい(及び従って正確な)浮動小数点数を使用して、物体の空間位置を定めることができる。階層のための平行移動の表示が格納される。次に、階層を処理することができ、階層によって表された物体の空間位置が処理される場合に、階層のための平行移動の表示を相応に使用することができる。各階層が決定されたそれぞれの平行移動を有することができるので、各階層の位置値の精度を維持することができるが、階層は、それぞれの階層に決定された平行移動の知識に基づいて共に処理(例えば、融合)することができる。

0072

平行移動ユニット510は、階層の平行移動を決定することができる。特に、図15に示す流れ図に従って段階S1502で平行移動ユニット510は、階層の平行移動を決定する。次に、段階S1504で、平行移動ユニット510は、階層に対して決定された平行移動の表示を次の使用ために、例えば、平行移動ユニット510内の表に又はメモリ308に格納させる。

0073

階層の平行移動は、階層の決定されたレベルでのノードに関連するボクセルの粒度で段階S1502で決定される。決定された階層のレベルは、例えば、階層が別の階層に融合される階層の最上位又は階層のレベル(上記で「融合レベル」と呼ぶ)とすることができる。これは、階層内の成長を(平行移動による階層のノードの数に関して)低減することを助けることができる。ボクセル位置合わせ表現を有するための平行移動の決定は、平行移動を決定する場合の複雑さを低減し、かつ加えられた平行移動を示すのに使用されるデータの量を低減することを助けることができる。例えば、LODレベル及びx、y、及びz方向におけるLODレベルの粒度のシフトの表示が平行移動を定めることができる。

0074

図11は、平行移動が階層の物体に使用される位置値での最適低減を提供するように、最低の可能性のレベルで(例えば、ピクセルレベルで)平行移動が決定される例を示している。図11は、単純にするために2Dで示されているが、同じ原理を更に別の次元に適用することができる。特に、図11は、レンダリングされているシーン内の空間を表すボクセル格子1102の4x4セクションを示している。階層に関連する形状は、形状を含むより低いレベルのボクセル1106を境界付けるボクセル1104内に収容されている。図12aは、ボクセル1104を表すためのノード1204とボクセル1106を表すためのより低いレベルのノード1206とを含む階層の一部を示している。ノード1204はノード1206のリファレンスを有する。矢印1108によって表される平行移動が、階層を位置1110に移動する階層に対して決定される。平行移動1108は、階層の空間位置を表すのに使用される値の優良な低減を可能にすることができ、それによって空間位置を高精度で定めることができる。しかし、位置1110はボクセル格子に位置合わせされないことを見ることができる。従って、位置1110は、元のボクセル1104を含む階層のレベルの4つのボクセルに跨がっている。すなわち、ボックス1104は1つのボクセル格子位置だけを覆うが、位置1110のボックスは、図11の11140、11141、11142、及び11143で示された4つのボクセル格子位置を覆う。換言すると、平行移動により、ボックス1110はボクセル格子1102に確実に位置合わせしていない。3次元平行移動では、ボックスが平行移動される時に最大8つのボクセルを覆うことがある。

0075

図12bは得られる階層を示している。ノード12140から12143は、ボクセル11140から11143内のボックスを表している。これらのノードの各々は、位置1112に平行移動された低レベルボックス1106に対応する子ノード1212のリファレンスを有する。この平行移動が階層を拡大している(すなわち、階層のノードの数を増加させた)ことを見ることができる。階層の拡大の結果として多くの交差試験が実行される場合があるのでこれは損失になることがある。例えば、光線試験が子ノード1212の複数の親に対してパスした場合に、ノード1212に対する複数の同一の交差試験が予定されることがある。これは、光線トレーシングレンダリングシステム内では非効率的になり、階層を通過する複製を感知及び阻止するようにハードウエアを設計することは、処理電力、時間、及び/又はシリコン面積の点からコスト的に法外である場合がある。

0076

この問題を阻止するために、平行移動は、決定されたレベルのボクセル格子の粒度で決定される。これは、平行移動された起点に対する位置値が小さくならないように僅差最適平行移動が実行されることを意味することができるが、平行移動による階層の拡大は、低減又は阻止される。図13は、図12aに示す階層に対応する同じより低いレベルのボクセル位置合わせボックス1206を含有する同じボクセル位置合わせボックス1204を示している。しかし、この時に、平行移動されたボックスがボックス1310の位置のボクセル格子に位置合わせされるように異なる平行移動(矢印1308によって図示)が実行される。ボクセル位置合わせボックス1310は、平行移動されていないボックス1206に対応するより低いレベルのボクセル位置合わせ1312を含む。図14は平行移動されたボックスの階層を示している。ノード1410はボックス1310を表し、ノード1412はボックス1312を表している。ノード1410は、ノード1412のリファレンスを有する。平行移動がボクセル格子に位置合わせされるので平行移動のために階層が拡大されていないことを見ることができる。

0077

階層に適用される平行移動の表示は、階層の真の位置を必要とする時に決定されるように格納される。平行移動の表示を格納及び融合することができる異なる方法が存在する。例えば、平行移動ユニット510は管理ユニットとして使用することができ、各階層に適用される平行移動を追跡して表に平行移動の表示を格納することができる。次に、処理ユニット(例えば、交差試験ユニット304)が階層の空間位置に基づいて階層を処理する場合は必ず平行移動ユニット510は、階層の平行移動の表示を処理ユニットに提供することができ、それによって階層を正しく処理することができる。他の実施例では、平行移動の表示を個別の表ではなく階層のノードのデータと共に格納することができる。この場合に、平行移動表示には、階層のノードの空間位置が提供される。しかし、ノードに関連付けられたデータの量の増加が要求されないように、ノードデータが光線トレーシングレンダリング器で頻繁に使用されて格納される。これは実施の選択であり、一般的に、階層のノードの空間位置が使用される時に表示がアクセス可能である場合に、平行移動の表示を格納するあらゆる適切な方法を使用することができる。

0078

従って、階層の平行移動に関して、シーンをレンダリングする際に使用する階層を処理する方法を提供することができ、階層は、シーン内のボックスに関連するノードのマルチレベルリンク構造であり、階層は、シーンでレンダリングされる1又は2以上の物体のセットの空間位置を表し、空間位置は、階層の起点に対して定義され、本方法は、シーン内の階層を位置決めするための階層の平行移動を決定する段階であって、この平行移動が、階層の決定されたレベルでのノードに関連するボックスに対応するボクセルの粒度でのものであると決定される上記決定する段階と、階層に対して決定された平行移動の表示を格納する段階とを含む。

0079

上述のように、シーンのレンダリングは、階層を使用して光線トレーシングを実行する段階を含むことができる。光線トレーシングは、階層のノードに対して光線に対する交差試験を実施する段階を含むことができる。階層の平行移動の表示を使用して、階層によって表される1又は2以上の物体のセットの空間位置を平行移動することができ、交差試験は、平行移動された空間位置を使用して実行される。従って、交差試験は、平行移動された空間位置を使用して実行することができ、(あるとすれば)1又は2以上の物体のセットを説明するプリミティブに交差する光線を決定する。上述のように、ボックスは、オクトツリーのレベルを表すボクセルに対応することができ、ボックスは軸位置合わせ境界ボックスとすることができる。

0080

平行移動は、シーンの予め決められた空間広がり内に階層が留まるという条件に従って階層に対して決定することができる。平行移動ユニット(例えば、平行移動ユニット510)は、階層の平行移動を追跡し(例えば、表に階層に対して決定された平行移動の表示を格納することにより)、かつ階層によって表された空間位置に基づいて処理を実行する更に別の処理モジュールに(例えば、交差試験ユニット304に)階層の平行移動を示すように構成することができる。

0081

他の実施例では、階層に対して決定された平行移動の表示は、階層によって表される物体の空間位置と共に格納され、それによって更に別の処理モジュール(例えば、交差試験ユニット304)が階層によって表された空間位置に基づいて処理を実行する時に、決定された平行移動が考慮に入れられる。

0082

一部の実施例では、階層の決定されたレベル(平行移動の粒度が決定されるレベル)は階層の最上位レベルである。

0083

他の実施例では、階層が1又は2以上の他の階層に融合され、融合階層を形成し、階層の融合は、階層に対して決定された平行移動を使用して実行される。これらの実施例では、階層の決定されたレベル(平行移動の粒度が決定されるレベル)は、融合階層を形成するために階層が融合される融合レベルである。

0084

上述のように、シーンは、フレームのシーケンスのうちの現在のフレームとすることができる。更に、上述のように、階層の少なくとも1つは、1又は2以上の静的物体のセットの空間位置を表して以前のフレームから再使用される静的階層とすることができ、階層の少なくとも別の階層は、1又は2以上の動的物体のセットの空間位置を表して現在のフレームをレンダリングするために構築される動的階層とすることができる。

0085

階層の平行移動に関する上述の方法は、平行移動ユニット510のような平行移動ユニットによって実施することができるが、他の平行移動ユニットを一部の実施例に使用することができる。

0086

特に、シーンをレンダリングする際に使用する階層を処理するための平行移動ユニットを提供することができ、階層は、シーン内のボックスに関連するノードのマルチレベルリンク構造であり、階層は、シーンでレンダリングされる1又は2以上の物体のセットの空間位置を表し、空間位置は、階層の起点に対して定義され、平行移動ユニットは、シーン内の階層を位置決めするための階層の平行移動を決定し、平行移動が、階層の決定されたレベルでのノードに関連するボックスに対応するボクセルの粒度であり、かつ階層に対して決定された平行移動の表示を格納させるように構成される。

0087

例えば、平行移動ユニットは、決定された平行移動の表示を格納するように構成されたストアを含むことができる。他の実施例では、決定された平行移動の表示は、異なるユニットでの格納のために、例えば、メモリ308における格納のために平行移動ユニットから送信することができる。

0088

一部の他の実施例では、空間インデックス構造を組み立てるための論理ユニットを提供する。上述の例に関して、これらの他の方法は、データベース、及び特にプリミティブの3D空間データベースからデータを検索する処理を加速するためにツリー及びツリー状データ構造を生成することに関する。特に、光線トレーシングは、空間加速構造を使用することが多い。加速構造は、3次元格子の形態、kdツリーのような分割平面のツリー、軸位置合わせ境界ボックス階層のような境界容積の階層、又はオクトツリーのような幾何学的に定義された構造の形態を取ることができる。これらの加速構造の各々をまとめてグラフ一般化することができ、多くの特性が、全ての加速構造間で共有される。

0089

空間加速構造の代替のタイプは、符号付き距離フィールドである。符号付き距離フィールドは、それぞれのセル中心点から最も近い形状までの空間内の距離を示すスカラー値を含有する格子又は疎らなボクセル構造として格納されることが多い。

0090

加速構造の使用は、光線トレーシングに限定されない。加速構造は、光子マッピング又は点ベースレンダリングアルゴリズムで利用することができる1又は2以上の点の検索を含むデータベースクエリの他のタイプに使用されることが多い。

0091

加速構造の構成は、メモリ集中処理である。最高品質加速構造は、データベースに全ての物体を完全に格納することによって生成されるが、トレードオフが存在し、それによって有界選別作動が、低減されたコストで妥当な品質の構造を生成することができる。

0092

グラフィックレンダリング内に使用される空間クエリのためのシステムは、2つの構成要素、すなわち、加速構造の構築と指定されたクエリによる構造の横断とを含む。加速構造の構築は、シェーダーパイプラインが、API呼出しに応答して加速構造によってインデックス付けされたメモリ内の物体に意図された形状プリミティブを出力する時に発生する。横断は、シェーダープログラムが加速構造に関連付けられた1又は2以上のクエリを待ち行列に入れた時に発生する。追加のシェーダーを横断処理の結果に応答して待ち行列に入れることができる。

0093

APIを通じてプリミティブの記述を受信する段階と、各プリミティブに対して、プリミティブの特性を決定する段階、特性に基づいて能動グループのセットの中から1又は2以上のグループを選択する段階、及び各選択された能動グループを更新する段階と、各能動グループに対して、能動グループに関する情報を出力する段階、親能動グループを選択する段階、及び親能動グループを更新する段階とを含む加速構造を構成する方法を提供する。

0094

上述の方法では、プリミティブは、点、線、頂点、三角形、nurb、パッチ、粒子、光子、ボックス、ボクセル、ディスク球体パラメータ面、パラメータ容積のいずれかを含むことができる。

0095

上述の方法では、特性は、サイズ、空間位置、方向、縦横比、表面積容積比、1又は2以上の軸又はベクトルへの位置合わせ、プリミティブタイプ、標準ベクトルのいずれかを含むことができる。

0096

上述の方法では、能動グループは有限セットである。

0097

上述の方法では、能動グループは、オンチップメモリのような物理的に限定されたメモリに存在する。

0098

上述の方法では、能動グループのセットは、キャッシュ挙動を使用して管理される。

0099

上述の方法では、更新段階は、プリミティブのリファレンスを能動グループに添付する段階を含む。

0100

上述の方法では、更新段階は、能動グループに関連付けられた第2のプリミティブを修正してプリミティブを境界付ける段階を含む。

0101

上述の方法では、更新段階は、プリミティブと能動グループに関連付けられた空間位置との距離を計算する段階、計算された距離を能動グループに関連付けられた第2の距離と比較する段階、及び第2の距離を潜在的に更新する段階を含む。

0102

上述の方法では、情報は、プリミティブへのリファレンス、メモリアドレス、距離、形状、プリミティブデータを含むことができる。

0103

モートンコード選別器

0104

1又は2以上の加速構造を指定するクエリを待ち行列に入れるように各々が作動可能な複数のシェーダープログラムインスタンスを実行するための3Dレンダリングのためのコンピュータ実装方法及び装置であって、各クエリは、加速構造を検索するように作動可能であり、この検索挙動は、加速構造の特性及びクエリの特性によって命令され、各クエリは、検索の結果に応答して1又は2以上のシェーダープログラムインスタンスを呼び出すように作動可能である。

0105

上述の方法及び装置では、指定された加速構造は、より大きい加速構造内のノードである場合がある。

0106

上述の方法及び装置では、呼び出されたシェーダーは、既存のクエリに関連付けられたデータを最小単位で修正することができる。

0107

上述の方法及び装置では、呼び出されたシェーダーは、既存のクエリの横断を再開することができる。

0108

上述の方法及び装置では、クエリは光線を含むことができ、結果は光線の起点に最も近い光線によって交差される三角形を含むことができる。

0109

上述の方法及び装置では、クエリは光線を含むことができ、クエリ結果は、ボックス、球体、三角形、面、容積のいずれかとすることができる。

0110

上述の方法及び装置では、クエリは、点から外に向う放射検索を含むことができる。

0111

上述の方法及び装置では、クエリは容積を含むことができ、結果は点を含むことができる。

0112

上述の方法及び装置では、横断処理は、部分的に幅優先である。

0113

上述の方法及び装置では、横断処理は、シェーダー実行に対して非同期である。

0114

上述の方法及び装置では、クエリによって呼び出されるシェーダープログラムが最初に待ち行列に入れられ、与えられたクエリによって待ち行列に入れられた1つのシェーダーだけを同時に実行することができる。

0115

上述の方法及び装置では、シェーダー呼び出しは、適切性に関する判断条件に基づいて順序付けされる。

0116

上述の方法及び装置では、適切性の条件は、クエリの発生点からの距離を含むことができる。

0117

上述の方法及び装置では、クエリは、クエリに関する待ち行列に入れられたシェーダーの数を追跡するためにリファレンスカウンタを維持する。

0118

上述の方法及び装置では、クエリは、試験を必要とする加速構造のノードの数を追跡するためにリファレンスカウンタを維持する。

0119

上述の方法及び装置では、シェーダーは、クエリに関連付けられたリファレンスカウンタを修正するように作動可能である。

0120

上述のグラフィックス処理システム300は、例えば、移動電話又はタブレットのようなデバイス内のコンピュータシステムに実施することができる。例えば、図16は、CPU1602、GPU1604、及びメモリ1606を含むコンピュータシステムを示し、メモリ1606は、階層ストア310及び累積バッファ312を含む上述のメモリ308を含むことができる。コンピュータシステム1600はまた、ディスプレイ1610及びスピーカ1612のような他のデバイス1608を含む。コンピュータシステム1600の構成要素は、通信バス1614を通じて互いに通信することができる。1つのアプリケーションのためのコンピュータプログラムコードは、メモリ1606に格納することができ、例えば、CPU1602で実行することができる。アプリケーションが3Dシーンの画像のレンダリングを必要とする場合に、プリミティブをGPU1604に送信することができ、GPU1604がグラフィックス処理システム300を使用して上述したようにシーンをレンダリングすることができる。

0121

上述の実施例では、階層処理モジュール302は、モジュール302の処理電力、時間、及びシリコン面積の点から階層を効率良く生成及び/又は融合することができるようにハードウエアに実施される。しかし、一般的に、上述の機能、方法、技術、又は構成要素(例えば、階層処理モジュール302及びその構成要素)のいずれも、ソフトウエア、ファームウエア、ハードウエア(例えば、固定論理回路)、又はこれらの実施のいずれの組合せも使用してモジュールに実施することができる。「モジュール」、「機能」、「構成要素」、「ブロック」、「ユニット」、及び「論理部」という語は、ソフトウエア、ファームウエア、ハードウエア、又はこれらのあらゆる組合せを一般的に表すのに使用される。本明細書に説明する階層処理モジュールは、集積回路のハードウエアに実施することができる。本明細書に説明する階層処理モジュールは、本明細書に説明する方法のいずれも実行するように構成することができる。

0122

図に示す階層処理モジュールは、いくつかの機能ブロックを含むように示されている。これは単に概略であり、そのようなエンティティの異なる論理要素間の厳密な分割を定めるように意図していない。各機能ブロックは、あらゆる適切な方法で提供することができる。階層処理モジュールによって形成される本明細書に説明する中間値は、あらゆる点で階層処理モジュールによって物理的に生成する必要はなく、単に入力と出力間で階層処理モジュールによって実行される処理を便宜上説明する論理値を表すことができることは理解されるものとする。

0123

階層処理モジュール302のソフトウエア実施の場合に、本明細書に実施されるユニット及びモジュールは、プロセッサで実行された時に指定されたタスクを実行するプログラムコードを表している。一例では、システム300のユニット及びモジュールは、コンピュータ可読媒体に格納された機械可読形態のソフトウエアによって構成されたコンピュータによって実施することができる。コンピュータ可読媒体の1つのそのような構成は、信号担持媒体であり、従って、ネットワークなどを通じてコンピュータデバイスに命令を送信するように構成される(例えば、搬送波として)。コンピュータ可読媒体は、非一時的コンピュータ可読ストレージ媒体としても構成することができ、従って、信号担持媒体ではない。コンピュータ可読ストレージ媒体の例には、ランダムアクセスメモリ(RAM)、読取専用メモリ(ROM)、光学ディスクフラッシュメモリハードディスクメモリ、及び磁気光学などの技術を使用することができる他のメモリデバイスが含まれ、命令又は他のデータを格納して、機械によってアクセス可能である。

0124

ソフトウエアは、説明した方法の構成部分を実行するようにコンピュータを構成するためのコンピュータプログラムコードを含むコンピュータプログラムの形態、又はプログラムがコンピュータで実行された時にかつコンピュータプログラムをコンピュータ可読媒体に実施することができる場合に本明細書に説明する方法のいずれの段階も全て実行するように適応されたコンピュータプログラムコード手段を含むコンピュータプログラムの形態とすることができる。プログラムコードは、1又は2以上のコンピュータ可読媒体に格納することができる。本明細書に説明する技術の特徴は、プラットフォーム独立型であり、この技術を異なるプロセッサを有する異なるコンピュータプラットフォームに実施することができることを意味する。

0125

当業者は、本明細書に説明する機能、技術、又は方法の全て又は一部分を専用回路特定用途向け集積回路プログラマブル論理アレイフィールドプログラマブルゲートアレイなどによって実行することができることを認めるであろう。例えば、モジュール、機能、構成要素、ユニット、又は論理部(例えば、階層処理モジュール302及びその構成要素)は、回路の形態のハードウエアを含むことができる。そのような回路は、製造工程で利用可能なトランジスタ及び/又は他のハードウエア要素を含むことができる。そのようなトランジスタ及び/又は他の要素を使用して、一例として、レジスタのようなメモリ、フリップフロップ、又はラッチブール演算加算器乗算器、又はシフタのような数値演算子のような論理演算子、及び相互接続を実施及び/又は含有する回路又は構造を形成することができる。そのような要素は、カスタム回路又は標準セルライブラリマクロ、又は他のレベルのアブストラクションとして提供することができる。そのような要素は、特定の配列で相互接続することができる。モジュール、機能、構成要素、ユニット、又は論理部(例えば、階層処理モジュール302及びその構成要素)は、固定機能である回路及び1又は複数の機能を実行するようにプログラムすることができる回路を含むことができ、そのようなプログラミングは、ファームウエア又はソフトウエア更新又は制御機構から提供することができる。一例では、ハードウエア論理部は、固定機能作動、状態機械又は処理を実施する回路を有する。

0126

望ましい機能を実行するために集積回路を設計するのに又はプログラマブルチップを構成するのに使用される場合に、HDLハードウエア記述言語)ソフトウエアのような本明細書に説明するハードウエアの構成を定めるソフトウエアを収容することも意図される。すなわち、集積回路製造システム内で処理された時に本明細書に説明する方法のいずれかを実行するように構成された階層融合モジュールを製造するように、又は本明細書に説明するあらゆる装置を含む階層融合モジュールを製造するようにシステムを構成する集積回路定義データセットの形態にコンピュータ可読プログラムコードが符号化されたコンピュータ可読ストレージ媒体を提供することができる。集積回路定義データセットは、例えば、集積回路記述とすることができる。

0127

集積回路定義データセットは、例えば、ネットリストレジスタ転送レベルRTL)コードとして、Verilog又はVHDLのようなハイレベル回路表現として、及びOASIS(RTM)及びGDSIIのようなより低いレベル回路表現として含むあらゆるレベルの集積回路を定めるハードウエア記述言語としてプログラマブルチップを構成するためのコードとしてのコンピュータコードの形態とすることができる。表現によって定義されるように集積回路の製造定義を生成するために、論理的に集積回路(RTLなど)を定めるハイレベル表現は、回路要素の定義及びこれらの要素を結合するための規則を含むソフトウエア環境の関連で集積回路の製造定義を生成するように構成されたコンピュータシステム内で処理することができる。機械を定めるためにコンピュータシステム内で実行するソフトウエアを備えた場合に一般的であるように、1又は2以上の中間ユーザ段階(例えば、指令変数などを提供)をこの集積回路の製造定義を生成するために集積回路を定めるコードを実行するための集積回路の製造定義を生成するように構成されたコンピュータシステムに対して要求することができる。

0128

階層融合モジュールを製造するように本発明のシステムを構成するために集積回路製造システム内で集積回路定義データセットを処理する実施例を図17に関してここで説明する。

0129

図17は、レイアウト処理システム1704及び集積回路発生システム1706を含む集積回路(IC)製造システム1702の実施例を示している。IC製造システム1702は、IC定義データセット(例えば、本明細書の実施例のいずれかで説明した階層融合モジュールを定める)を受信し、IC定義データセットを処理し、かつIC定義データセットに従ってICを発生させる(例えば、本明細書の実施例のいずれかに説明した階層融合モジュールを実施する)ように構成される。IC定義データセットの処理は、本明細書の実施例のいずれかで説明した階層融合モジュールを実施する集積回路を製造するようにIC製造システム1702を構成する。

0130

レイアウト処理システム1704は、IC定義データセットを受信及び処理して回路レイアウトを決定するように構成される。IC定義データセットから回路レイアウトを決定する方法は、当業技術で公知であり、例えば、論理構成要素(例えば、NANDNOR、AND、OR、MUX、及びFLIP−FLOP構成要素)の点で、発生される回路のゲートレベル表現を決定するためにRTLコードを合成する段階を収容することができる。回路レイアウトは、論理構成要素の位置情報を決定することによって回路のゲートレベル表現から決定することができる。これは、回路レイアウトを最適化するために自動的に又はユーザの介入により実行することができる。レイアウト処理システム804が回路レイアウトを決定した時に、レイアウト処理システム1704は、回路レイアウト定義をIC発生システム1706に出力することができる。回路レイアウト定義は、例えば、回路レイアウト記述とすることができる。

0131

IC発生システム1706は、当業技術で公知のように回路レイアウト定義に従ってICを発生させる。例えば、IC発生システム1706は、ICを発生させるための半導体素子製造工程を実施することができ、半導体素子製造工程は、半導体材料から構築されたウェーハ電子回路が徐々に生成されていく過程リソグラフィック及び化学的処理段階の複数段階シーケンスを収容することができる。回路レイアウト定義は、回路定義に従ってICを発生させるためのリソグラフィック処理に使用することができるマスクの形態とすることができる。これに代えて、IC発生システム1706に提供される回路レイアウト定義は、ICを発生させる場合に使用する適切なマスクを形成するためにIC発生システム1706を使用することができるコンピュータ可読コードの形態とすることができる。

0132

IC製造システム1702によって実行される異なる処理は、1つの位置で例えば1つの当事者によって全てを実施することができる。これに代えて、IC製造システム1702は、処理の一部が異なる位置で実行することができるように分散システムとすることができ、異なる当事者によって実行することができる。例えば、(i)発生される回路のゲートレベル表現を形成するためにIC定義データセットを表すRTLコードを合成する段階、(ii)ゲートレベル表現に基づいて回路レイアウトを発生させる段階、(iii)回路レイアウトに従ってマスクを形成する段階、及び(iv)マスクを使用して集積回路を製造する段階の一部は、異なる位置で及び/又は異なる当事者によって実行することができる。

0133

他の実施例では、集積回路製造システムにおける集積回路定義データセットの処理が、回路レイアウトを決定するためにIC定義データセットを処理する必要なく階層融合モジュールを製造するように本発明のシステムを構成することができる。例えば、集積回路定義データセットは、FPGAのような再構成可能プロセッサの構成を定めることができ、このデータセットの処理は、この定義された構成を有する再構成可能プロセッサを生成するように(例えば、FPGAに構成データをロードすることにより)IC製造システムを構成することができる。

0134

一部の実施形態において、集積回路製造定義データセットが、集積回路製造システム内で処理された時に、集積回路製造システムに本明細書に説明したデバイスを発生させることができる。例えば、集積回路製造定義データセットによる図17に関して上述した方法での集積回路製造システムの構成は、本明細書に説明したデバイスを製造させることができる。

0135

一部の実施例では、集積回路定義データセットは、データセットで定義されたハードウエア、又はデータセットで定義されたハードウエアと組み合わせて実行されるソフトウエアを含むことができる。図17に示す実施例では、集積回路の製造段階で、集積回路定義データセットで定義されたプログラムコードに従ってこの集積回路にファームウエアをロードするか、又は他に集積回路と共に使用するプログラムコードを集積回路に提供するようにIC発生システムを集積回路定義データセットによって更に構成することができる。

0136

用語「プロセッサ」及び「コンピュータ」は、命令を実行することができるような処理機能を備えたあらゆるデバイス又はその部分、又は機能又は方法の全て又は一部を実行することができる専用回路、又はそのあらゆる組合せを指すために本明細書に使用される。

0137

本発明の主題は、構造的特徴及び/又は方法論的行為に固有の言語で説明したが、特許請求の範囲で定義される主題は、必ずしも上述の特定の特徴又は行為に限定されないことは理解されるものとする。逆に、上述の特定の特徴及び行為は、特許請求の範囲を実施する例示的形態として開示している。上述の利益及び利点は、一例に関連付けることができ、又はいくつかの例に関連付けることができることは理解されるであろう。

0138

本明細書に与えられるあらゆる範囲又は値は、当業者に明らかなように求められる効果を失うことなく拡張又は変更することができる。本明細書に説明する方法の段階は、あらゆる適切な順序で又は必要に応じて同時に実行することができる。上述の実施例のいずれの態様も、求められる効果を失うことなく更に別の実施例を形成するために説明した他の例のいずれの態様とも組み合わせることができる。

0139

300グラフィックス処理システム
302階層処理モジュール
306シェーダー
308メモリ
504 階層融合ユニット

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ