(57)【要約】      （修正有）【課題】加速構造を構築するための、優れた、システム、方法及びコンピュータプログラムプロダクトを提供する。【解決手段】シーンに関連する複数のプリミティブが識別される（動作１０２）。一実施形態では、シーンは、レンダリングされるプロセス中のシーンを含んでもよい。他の実施形態では、複数のプリミティブは、シーンの中に含まれてもよく、複数の三角形を含んでもよい。さらに、プリミティブを利用して加速構造が構築される（動作１０４）。一実施形態では、加速構造は、バウンディングボリューム階層（ＢＶＨ）を含んでもよい。他の実施形態では、加速構造は、線形化バウンディングボリューム階層（ＬＢＶＨ）を含んでもよく、階層型線形化バウンディングボリューム階層（ＨＬＢＶＨ）を含んでもよい。【選択図】図１
2013037691.tif 000002
【特許請求の範囲】
【請求項１】
シーンに関連する複数のプリミティブを識別するステップと、
前記プリミティブを利用して、加速構造を構築するステップと、
を含む方法。
【請求項２】
前記シーンが前記複数のプリミティブから構成される、請求項１に記載の方法。
【請求項３】
グラフィックス処理ユニット（ＧＰＵ）が、前記加速構造を構築するステップ全体を実行する、請求項１に記載の方法。
【請求項４】
前記加速構造が階層型線形化バウンディングボリューム階層（ＨＬＢＶＨ）を含む、請求項１に記載の方法。
【請求項５】
前記加速構造が複数のノードを含む、請求項１に記載の方法。
【請求項６】
前記加速構造がノードの階層を含み、子ノードがそれぞれの親ノードバウンディングボックスの中にあるバウンディングボックスを表し、葉ノードがそれぞれの親バウンディングボックスの中にある１つ又は複数のプリミティブを表す、請求項５に記載の方法。
【請求項７】
前記加速構造を構築するステップが、前記プリミティブをソーティングするサブステップを含む、請求項１に記載の方法。
【請求項８】
前記プリミティブが、前記シーンのバウンディングボックスを埋める空間充填曲線に沿ってソーティングされる、請求項７に記載の方法。
【請求項９】
前記空間充填曲線が、前記シーン内の各プリミティブの重心のモートンコードを計算することにより決定される、請求項８に記載の方法。
【請求項１０】
ソーティングは、最小有効桁基数ソーティングアルゴリズムを利用して実行される、請求項１に記載の方法。
【請求項１１】
前記加速構造を構築するステップが、前記シーンの中でプリミティブのクラスタを形成するサブステップを含む、請求項１に記載の方法。
【請求項１２】
前記クラスタがランレングス符号化圧縮アルゴリズムを利用して形成される、請求項１１に記載の方法。
【請求項１３】
前記加速構造を構築するステップが、形成された各クラスタの中のプリミティブをパーティショニングするサブステップを含む、請求項１１に記載の方法。
【請求項１４】
前記加速構造を構築するステップが、空間中央分割を使用して各クラスタの中の全プリミティブをパーティショニングするサブステップを含む、請求項１１に記載の方法。
【請求項１５】
前記加速構造を構築するステップが、前記クラスタを利用して木を生成するサブステップを含む、請求項１１に記載の方法。
【請求項１６】
前記加速構造を構築するステップが、前記クラスタをパーティショニングすることによりトップレベルツリーを生成するサブステップを含む、請求項１４に記載の方法。
【請求項１７】
前記プリミティブ及び前記クラスタをパーティショニングする処理は、１つ又は複数のタスク待ち行列を利用して実行される、請求項１６に記載の方法。
【請求項１８】
コンピュータ読取り可能媒体に記憶されたコンピュータプログラムプロダクトであって、
シーンに関連する複数のプリミティブを識別するためのコードと、
前記プリミティブを利用して加速構造を構築するためのコードと、
を備えるコンピュータプログラムプロダクト。
【請求項１９】
シーンに関連する複数のプリミティブを識別し、前記プリミティブを利用して加速構造を構築するためのグラフィックス処理ユニット（ＧＰＵ）、
を備えるシステム。
【請求項２０】
バスを介して前記ＧＰＵに結合されたメモリ、をさらに備える請求項１９に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
[0001]本発明は、画像をレンダリングすることに関し、より詳細にはレイトレーシングを実行することに関する。
【背景技術】
【０００２】
[0002]従来、レイトレーシングは表示されたシーンの中で画像を生成するために使用されている。例えば、プリミティブに関連する画像をレンダリングするために、表示されたシーンの複数のレイと複数のプリミティブとの間の交点を決定することができる。しかし、レイトレーシングを実行するための現在の技法は、様々な限界を伴っている。
【０００３】
[0003]例えば、レイトレーシングを実行するための現在の方法は、レイトレーシングと共に使用される加速構造（ａｃｃｅｌｅｒａｔｉｏｎ  ｓｔｒｕｃｔｕｒｅ）を効率よく構築することができない。その結果、大量のプリミティブに関連する加速構造の構築に時間がかかることになる。
【０００４】
[0004]したがって、従来技術に関連するこれらの及び／又は他の問題に対処する必要がある。
【発明の概要】
【０００５】
[0005]加速構造を構築するためのシステム、方法、及びコンピュータプログラムプロダクトが提供される。使用中に、シーンに関連する複数のプリミティブが識別される。さらに、プリミティブを利用して加速構造が構築される。
【図面の簡単な説明】
【０００６】
【図１】一実施形態による、加速構造を構築するための方法を示す図である。
【図２】他の実施形態による、加速構造の構築中にパーティションを実行する際に使用されるタスク待ち行列システムを示す図である。
【図３】他の実施形態による、モートンコードを使用した一群のプリミティブのソーティングを示す図である。
【図４】他の実施形態による、図３において実行されるソーティングに対応する複数の中央分割待ち行列を示す図である。
【図５】他の実施形態による、ＳＡＨビニング手順のデータの流れ図である。
【図６】上記の様々な実施形態の様々なアーキテクチャ及び／又は機能が実行されることが可能である例示的システムを示す図である。
【発明を実施するための形態】
【０００７】
[0012]図１は、一実施形態による、加速構造を構築するための方法１００を示す。動作１０２に示されているように、シーンに関連する複数のプリミティブが識別される。一実施形態では、シーンは、レンダリングされるプロセス中のシーンを含んでもよい。例えば、シーンは、レイトレーシングを使用してレンダリングされるプロセス中であってもよい。他の実施形態では、複数のプリミティブは、シーンの中に含まれてもよい。例えば、シーンは、複数のプリミティブから構成されてもよい。他の実施形態では、複数のプリミティブは、複数の三角形を含んでもよい。しかしもちろん、複数のプリミティブは、レイトレーシングを実行するために使用される任意のプリミティブを含んでもよい。
【０００８】
[0013]さらに、動作１０４に示されているように、プリミティブを利用して加速構造が構築される。一実施形態では、加速構造は、バウンディングボリューム階層（ＢＶＨ）を含んでもよい。他の実施形態では、加速構造は、線形化バウンディングボリューム階層（ＬＢＶＨ）を含んでもよい。他の実施形態では、加速構造は、階層型線形化バウンディングボリューム階層（ＨＬＢＶＨ）を含んでもよい。
【０００９】
[0014]他の実施形態では、加速構造は、複数のノードを含んでもよい。例えば、加速構造は、ノードの階層を含んでもよく、この場合、子ノードは、それぞれの親ノードバウンディングボックスの中にあるバウンディングボックスを表し、葉ノードは、それぞれの親バウンディングボックスの中にある１つ又は複数のプリミティブを表す。このようにして、加速構造は、レイトレーシング中に使用されるべきプリミティブを複数の階層型ボックスに編成することができるバウンディングボリューム階層を含んでもよい。
【００１０】
[0015]さらに、一実施形態では、加速構造を構築するステップは、プリミティブをソーティングするサブステップを含んでもよい。例えば、プリミティブは、シーンのバウンディングボックスを埋める空間充填曲線（例えば、モートン曲線、ヒルベルト曲線など）に沿ってソーティングされてもよい。他の実施形態では、空間充填曲線は、シーン内の各プリミティブの重心のモートンコードを計算することにより決定されてもよい（例えば、プリミティブの中央における平均位置が、三次元（３Ｄ）座標から帰納的に設計されたモートン曲線などに関連する一次元座標に変換されてもよい）。
【００１１】
[0016]他の実施例では、ソーティングは、最小有効桁基数ソーティングアルゴリズムを利用して実行されてもよい。他の実施形態では、加速構造を構築するステップは、シーンの中でプリミティブのクラスタ（例えば、プリミティブの粗クラスタなど）を形成するサブステップを含んでもよい。例えば、クラスタは、ランレングス符号化圧縮アルゴリズムを利用して形成されてもよい。
【００１２】
[0017]さらに、一実施形態では、加速構造を構築するステップは、形成された各クラスタの中のプリミティブをパーティショニングするサブステップを含んでもよい。例えば、加速構造を構築するステップは、空間中央分割（例えば、ＬＢＶＨ式空間中央分割など）を使用して各クラスタの中の全てのプリミティブをパーティショニングするサブステップを含んでもよい。他の実施例では、加速構造を構築するステップは、クラスタを利用して木（例えば、トップレベルツリーなど）を生成するサブステップを含んでもよい。例えば、加速構造を構築するステップは、クラスタをパーティショニングすることにより（例えば、ビニングされた表面積ヒューリスティック（ＳＡＨ）、ＳＡＨ最適化木構築アルゴリズムなどを利用することにより）、トップレベルツリーを生成するサブステップを含んでもよい。他の実施形態では、ＳＡＨは、パラレルビニング方式を利用することができる。
【００１３】
[0018]さらに、一実施形態では、プリミティブ及びクラスタをパーティショニングするステップは、１つ又は複数のタスク待ち行列を利用して実行されてもよい。例えば、タスク待ち行列システムは、（例えば、パイプラインを生成することなどにより）加速構造の構築中に作業を並列化するために使用されてもよい。他の実施形態では、加速構造は、１つ又は複数のアルゴリズムを利用して構築されてもよい。例えば、プリミティブをソーティングするステップと、プリミティブのクラスタを形成するステップと、プリミティブをパーティショニングするステップと、木を生成するステップとは全て、１つ又は複数のアルゴリズムを利用して実行されてもよい。
【００１４】
[0019]さらに、一実施形態では、加速構造を構築するステップは、グラフィックス処理ユニット（ＧＰＵ）を利用して実行されてもよい。例えば、ＧＰＵは、加速構造の構築全体を実行することができる。このようにして、ＧＰＵと中央処理装置（ＣＰＵ）に関連するシステムメモリとの間のデータの伝送を回避することができ、それによって、加速構造を構築するために必要な時間を低減することができる。
【００１５】
[0020]次に、ユーザの所望に応じて、上記のフレームワークが実施されてもされなくてもよい様々な任意選択のアーキテクチャ及び特徴に関してさらに多くの例示的情報が説明される。以下の情報は例示的な目的のために記述され、決して限定として解釈されるべきではないことに強く留意されたい。以下の特徴はいずれも、記載されている他の特徴を除外して又は除外することなく、任意選択で組み込まれてもよい。
【００１６】
[0021]図２は、他の実施形態による、加速構造の構築中にパーティショニングを実行する際に使用されるタスク待ち行列システム２００を示す。オプションとして、このタスク待ち行列システム２００は、図１の機能の文脈で実行されてもよい。しかしもちろん、タスク待ち行列システム２００は、任意の所望の環境において実施されてもよい。上記の定義は、本説明中に適用されてもよいことにも留意されたい。
【００１７】
[0022]図示されているように、タスク待ち行列システム２００は、それぞれ処理するべきタスクのセットを（例えば、入力待ち行列などから）フェッチする複数のワープ２０２Ａ及び２０２Ｂを含む。一実施形態では、複数のワープ２０２Ａ及び２０２Ｂはそれぞれ、作業のユニット（例えば、ＧＰＵ上の作業の物理ＳＩＭＴユニットなど）を含んでもよい。他の実施形態では、個々のタスクはそれぞれ、加速構造の構築中に単一のノードを処理するステップに対応することができる。
【００１８】
[0023]さらに、一実施形態では、実行時に、複数のワープ２０２Ａ及び２０２Ｂはそれぞれ、入力待ち行列から処理するべきタスクのセットをフェッチし続けることができ、この場合、各セットはスレッドごとに１つのタスクを含んでもよい。さらに、複数のワープ２０２Ａ及び２０２Ｂはそれぞれ、ワープごとに単一のグローバルメモリアトミック加算を使用して待ち行列ヘッドを更新することができる。さらに、複数のワープ２０２Ａ及び２０２Ｂそれぞれ内の各スレッドは、各スレッドが生成する出力タスクの数２０４を計算する。
【００１９】
[0024]さらに、複数のワープ２０２Ａ及び２０２Ｂそれぞれ内の各スレッドは、各スレッドが生成する出力タスクの数２０４を計算した後に、複数のワープ２０２Ａ及び２０２Ｂそれぞれ内の全てのスレッドは、ワープワイドプレフィックス和２０６に関与して、複数のワープ２０２Ａ及び２０２Ｂそれぞれの共通ベースに関連するそれらの出力タスクのオフセットを計算する。一実施形態では、複数のワープ２０２Ａ及び２０２Ｂそれぞれ内の第１のスレッドは、単一のグローバルメモリアトミック加算を実行して、複数のワープ２０２Ａ及び２０２Ｂの出力待ち行列内のベースアドレスを計算することができる。さらに、一実施形態では、レベルごとに別々の待ち行列が使用されてもよく、それによって単一のカーネルコールの中で全ての処理を実行することができるようにすることができ、幅優先探索木レイアウトを同時に生成する。
【００２０】
[0025]一実施形態では、加速構造を構築するステップは、１つ又は複数のアルゴリズムを使用して標準的なＬＢＶＨ及びより高品質のＳＡＨハイブリッドの両方を生成するサブステップを含んでもよい。例えば、参照によりその全体が本明細書に組み込まれており、ＬＢＶＨ及びＨＬＢＶＨを構築するための方法を説明している、「ＨＬＢＶＨ：Ｈｉｅｒａｒｃｈｉｃａｌ  ＬＢＶＨ  ｃｏｎｓｔｒｕｃｔｉｏｎ  ｆｏｒ  ｒｅａｌ−ｔｉｍｅ  ｒａｙ  ｔｒａｃｉｎｇ  ｏｆ  ｄｙｎａｍｉｃ  ｇｅｏｍｅｔｒｙ」、（Ｐａｎｔａｌｅｏｎｉら、Ｈｉｇｈ−Ｐｅｒｆｏｒｍａｎｃｅ  Ｇｒａｐｈｉｃｓ  ２０１０、ＡＣＭ  Ｓｉｇｇｒａｐｈ  ／  Ｅｕｒｏｇｒａｐｈｉｃｓ  Ｓｙｍｐｏｓｉｕｍ  Ｐｒｏｃｅｅｄｉｎｇｓ、Ｅｕｒｏｇｒａｐｈｉｃｓ、８７〜９５）を参照されたい。
【００２１】
[0026]さらに、他の実施形態では、加速構造を構築するステップは、シーンのバウンディングボックスを埋める３０ビットモートン曲線に沿ってプリミティブをソーティングするサブステップを含んでもよい。例えば、参照によりその全体が本明細書に組み込まれており、プリミティブをソーティングし、ＢＶＨを構築するための方法を説明している、「Ｆａｓｔ  ｂｖｈ  ｃｏｎｓｔｒｕｃｔｉｏｎ  ｏｎ  ＣＰＵｓ」、（Ｌａｕｔｅｒｂａｃｈら、Ｃｏｍｐｕｔ．Ｇｒａｐｈ．Ｆｏｒｕｍ  ２８、２、３７５〜３８４）を参照されたい。他の実施形態では、プリミティブは、ブルートフォースアルゴリズム（例えば、最小有効桁基数ソーティングアルゴリズムなど）を利用してソーティングされてもよい。
【００２２】
[0027]他の実施形態では、モートンコードが階層グリッドを定義するという観察結果を利用すると、各３ｎビットコードが面ごとに２ｎエントリを有する正規グリッド内の一意のボクセルを識別し、一実施形態では、コードの最初の３ｍビットが、面ごとに２ｍ細分割を有するより粗いグリッド内の親ボクセルを識別し、各３ｍビットビンに入るオブジェクトの粗クラスタが形成されてもよい。他の実施形態では、一意のボクセルが識別されるグリッドが、面ごとに様々な量のエントリを含んでもよい。他の実施形態では、オブジェクトの粗クラスタを形成するステップは、ランレングス符号化圧縮アルゴリズムのインスタンスを利用して実行されてもよく、単一の圧縮動作で実行されてもよい。
【００２３】
[0028]さらに、一実施形態では、クラスタが識別された後に、全てのプリミティブが各クラスタの中で（例えば、ＬＢＶＨ式空間中央分割などを使用して）パーティショニングされてもよい。他の実施形態では、次いで、トップレベルツリーが生成されてもよく、この場合、クラスタはビニングされたＳＡＨビルダでパーティショニングされてもよい。例えば、参照によりその全体が本明細書に組み込まれており、クラスタをパーティショニングするための方法を説明している、「Ｏｎ  ｆａｓｔ  Ｃｏｎｓｔｒｕｃｔｉｏｎ  ｏｆ  ＳＡＨ  ｂａｓｅｄ  Ｂｏｕｎｄｉｎｇ  Ｖｏｌｕｍｅ  Ｈｉｅｒａｒｃｈｉｅｓ」、（Ｗａｌｄ、Ｉ．、Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２００７  Ｅｕｒｏｇｒａｐｈｉｃｓ／ＩＥＥＥ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｉｎｔｅｒａｃｔｉｖｅ  Ｒａｙ  Ｔｒａｃｉｎｇ、Ｅｕｒｏｇｒａｐｈｉｃｓ）を参照されたい。
【００２４】
[0029]さらに、一実施形態では、空間中央分割パーティショニング及びＳＡＨビルダは両方とも、出力階層の個々のノード全てにわたって作業を並列化することができる効率のよいタスク待ち行列システム（例えば、タスク待ち行列システム２００など）に依拠してもよい。
【００２５】
[0030]さらに、一実施形態では、中央分割階層エミッションが実行されてもよい。例えば、階層内の各ノードは、それらのモートンコードによってソーティングされた連続した範囲のプリミティブに対応してもよく、ノードを分割するステップはそのコードが前の要素とは異なる範囲内の第１の要素を見つけるサブステップを必要としてもよいことに留意されたい。さらに、他の実施形態では、シリアルデバイス上で使用されてもよい標準的なオーダリングに戻ることにより、複雑な機械が回避されることが可能である。例えば、各ノードは単一のスレッドにマッピングされてもよく、各スレッドはそれ自体の分割面を見つけることができるようにされてもよい。
【００２６】
[0031]他の実施形態では、ノード内の範囲全体をループするのではなく、問題を簡単な二分探索として再公式化することが可能であることに留意されたい。例えば、ノードがレベルｌにある場合は、ノードのプリミティブのモートンコードはハイｌ−１ビットの正確に同じセットを有してもよいと決定されてもよい。他の実施形態では、最初のビットｐ≧ｌであり、それによって、ノードの範囲差内の最初の及び最後のモートンコードが決定されてもよい。他の実施形態では、二分探索が、ビットｐにおいて１を含む最初のモートンコードを見つけ出すために実行されてもよい。
【００２７】
[0032]このようにして、Ｎのプリミティブを含むノードでは、アルゴリズムは、Ｎのモートンコードの全セットの代わりに、Ｏ（ｌｏｇ２（Ｎ））のメモリセルのみをタッチすることにより分割面を見つけることができる。
【００２８】
[0033]さらに、一実施形態では、中央分割は時々できないことがあり、これは時々大きな葉につながることがある。他の実施形態では、そのような障害が検出された場合、葉はオブジェクトメディアンによって分割されてもよい。他の実施形態では、ＢＨＶのトポロジが計算された後に、ボトムアップ再フィッティング手順が木内の各ノードのバウンディングボックスを計算するために実行されてもよい。このプロセスは、ＢＶＨが幅優先順で記憶されるということによって簡略化されることが可能である。他の実施形態では、木レベルごとに１つのカーネル起動が使用されてもよく、そのレベルにおけるノードごとに１つのスレッドが使用されてもよい。
【００２９】
[0034]図３は、他の実施形態による、モートンコードを使用した一群のプリミティブのソーティング３００を示す。オプションとして、このソーティング３００は、図１〜図２の機能の文脈で実行されてもよい。しかしもちろん、ソーティング３００は、任意の所望の環境で実行されてもよい。前述の定義はこの説明中に適用されてもよいことにも留意されたい。
【００３０】
[0035]図示されているように、二次元投影図の中にある複数の境界内のプリミティブ３０２Ａ〜Ｊの重心はそれぞれ、モートンコード（例えば４ビットモートンコードなど）を割り当てられる。さらに、複数の境界内のプリミティブ３０２Ａ〜Ｊは、行３０６Ａ〜Ｊのシーケンスにソーティングされ、割り当てられたモートンコードはキーとして使用される。例えば、シーケンス３０６Ａ〜Ｊそれぞれのプリミティブごとに、モートンコードビットが個別の行３０８に示されている。さらに、二分探索パーティション３１０が行のシーケンス３０６Ａ〜Ｊに対して作成される。さらに、図４は、他の実施形態による、図３において実行されるソーティング３００に対応する、複数の中央分割待ち行列４０２Ａ〜Ｅを示す。
【００３１】
[0036]さらに、一実施形態では、ＳＡＨ最適化木構造アルゴリズムが、モートン曲線の最初の３ｍビットによって定義された全ての粗クラスタにわたって実行されてもよい。一実施形態では、ｍは５から７までの間にあってもよい。しかしもちろん、ｍは任意の整数を含んでもよい。他の実施形態では、構築アルゴリズムは、限られたメモリフットプリントで実行することができる。例えば、Ｎｃのクラスタが処理される場合、空間は（２Ｎｃ−１）のノードにのみ予め割り当てられてもよい。
【００３２】
[0037]表１は、最適化木構造アルゴリズムに関連するＳＡＨビニング手順のための擬似コードを例示する。もちろん、表１に示されている擬似コードは、例示的な目的のためにのみ記述されるものであって、決して限定として解釈されるべきではないことに留意されたい。
【表１】
2013037691.tif 000003
【００３３】
[0038]一実施形態では、パスにおいて、（集合バウンディングボックスを有する）前のパスからのクラスタは、プリミティブとみなされてもよい。他の実施形態では、計算は、単一の入力待ち行列及び単一の出力待ち行列において編成された分割タスクに分割されてもよい。他の実施形態では、各タスクは、分割される必要があるノードに対応してもよく、３つの入力フィールド（例えば、ノードのバウンディングボックス、ノードの中のクラスタの数、及びノードＩＤ）によって示されてもよい。
【００３４】
[0039]さらに、一実施形態では、２つの追加のノード（例えば、ベスト分割面及び最初の子分割タスクのＩＤ）が動作中に計算されてもよい。他の実施形態では、これらのフィールドは、タスクＩＤによってインデックスされた個別のアレイの数（例えば、５など）を保持することができるアレイ（ＳＯＡ）フォーマットの構造に記憶されてもよい。他の実施形態では、各クラスタをそれが所属する現在のノード（すなわち、分割タスクなど）にマッピングするアレイ（例えば、ｃｌｕｓｔｅｒ＿ｓｐｌｉｔ＿ｉｄなど）が保持されてもよく、アレイは分割動作ごとに更新されてもよい。
【００３５】
[0040]さらに、一実施形態では、表１におけるループは、全てのクラスタを、分割タスク０を形成することができるルートノードに割当てることから開始してもよい。次いで、ループの繰返しごとに、ビニングステップ、ＳＡＨ評価ステップ、及びクラスタ分配ステップが実行されてもよい。例えば、各ノードのバウンディングボックスは、各次元においてＭ（例えば、８などの整数を含むＭ）のスラブ形のビンに分割されてもよい。例えば、参照によりその全体が本明細書に組み込まれており、ノードバウンディングボックスを分割するための方法を説明している、「Ｒａｙ  Ｔｒａｃｉｎｇ  Ｄｅｆｏｒｍａｂｌｅ  Ｓｃｅｎｅｓ  ｕｓｉｎｇ  Ｄｙｎａｍｉｃ  Ｂｏｕｎｄｉｎｇ  Ｖｏｌｕｍｅ  Ｈｉｅｒａｒｃｈｉｅｓ」、（Ｗａｌｄら、ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｇｒａｐｈｉｃｓ  ２６、１、４８５〜４９３）を参照されたい。
【００３６】
[0041]さらに、他の実施形態では、ビンは、最初は空のバウンディングボックス及びカウントを記憶することができる。他の実施形態では、各クラスタバウンディングボックスは、その重心を含むビンに蓄積されてもよく、ビンの中に入るクラスタの数のカウントは、自動的にインクリメントされてもよい。他の実施形態では、この手順は、全クラスタにまたがって平行して実行されてもよく、各スレッドは、単一のクラスタを調べることができ、ビンのバウンディングボックスを大きくするためにアトミック最小／最大（ａｔｏｍｉｃ  ｍｉｎ／ｍａｘ）を使用して、そのバウンディングボックスを対応する分割タスクの中の対応するビンに集積することができる。
【００３７】
[0042]さらに、一実施形態では、入力待ち行列内の分割タスクごとに、一様に分配されたビン間の各次元における全分割面の表面積メトリックが評価されてもよく、ベストの１つが選択されてもよい。他の実施形態では、分割タスクが単一のクラスタを含む場合は、細分割は停止されてもよく、又はそうでなければ、２つの出力分割タスクが生成されてもよく、左の及び右の部分空間に対応するバウンディングボックスがＳＡＨ分割によって決定されてもよい。
【００３８】
[0043]さらに、一実施形態では、クラスタと分割タスクとの間のマッピングが更新されてもよく、各クラスタは、その前のオーナによって生成された２つの出力分割タスクの１つにマッピングされてもよい。新しい分割タスクＩＤを決定するために、ｉ番目のクラスタのビンＩＤが、対応する分割タスクのベスト分割フィールドに記憶されている値と比較されてもよい。表２は、ｉ番目のクラスタのビンＩＤの対応する分割タスクのベスト分割フィールドに記憶されている値との比較のための擬似コードを例示する。もちろん、表２に示されている擬似コードは、例示的な目的のためにのみ記述され、決して限定として解釈されるべきではないことに留意されたい。
【表２】
2013037691.tif 000004
【００３９】
[0044]さらに、一実施形態では、アルゴリズムフェーズの順序にいくらかの柔軟性があってもよい。例えば、再フィッティングが、クラスタバウンディングボックス精密度を類似性とトレードオフするためにボトムレベルフェーズ及びトップレベルフェーズに対して別々に実行されてもよい。
【００４０】
[0045]図５は、他の実施形態による、ＳＡＨビニング手順のデータフロー可視化図５００である。オプションとして、このデータフロー可視化図５００は、図１〜４の機能の文脈で実行されてもよい。しかしもちろん、データフロー可視化図５００は、任意の所望の環境で実行されてもよい。前述の定義はこの説明中に適用されてもよいことにも留意されたい。
【００４１】
[0046]図示されているように、クラスタ５０２Ａ及び５０２Ｂは、それらの親ノードのビン統計値５０４を形成することに寄与する。さらに、入力タスク待ち行列５０６内のノードは分割され、出力待ち行列５１０の中に２つのエントリ５０８Ａ及び５０８Ｂを生成する。
【００４２】
[0047]さらに、一実施形態では、微細で入り組んだ形状（例えば、髪、毛、葉など）のクラスタのための専用ビルダは統合されてもよい。他の実施形態では、この作業は、三角分割法と容易に統合されることが可能である。例えば、参照によりその全体が本明細書に組み込まれており、三角分割法を説明している、「Ｅａｒｌｙ  ｓｐｌｉｔ  ｃｌｉｐｐｉｎｇ  ｆｏｒ  ｂｏｕｎｄｉｎｇ  ｖｏｌｕｍｅ  ｈｉｅｒａｒｃｈｉｅｓ」、（Ｅｒｎｓｔら、Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｉｎｔｅｒａｃｔｉｖｅ  Ｒａｙ  Ｔｒａｃｉｎｇ  ０、７３〜７８）を参照されたい。他の実施形態では、圧縮−ソート−解凍技法が、メッシュの内部のコヒーレンスを利用するために再組み込みされてもよい。
【００４３】
[0048]このようにして、ＨＬＢＶＨは、簡単で速いパラレルアルゴリズムを構築するために使用されてもよい作業ディスパッチングの柔軟なパラダイムを含んでもよい汎用タスク待ち行列に基づいて実施されてもよい。さらに、一実施形態では、同じ機構が高品質ＨＬＢＶＨ変形形態のための大量にパラレルビニングされたＳＡＨビルダを実装するために使用されてもよい。他の実施形態では、ＨＬＢＶＨ実装は、全体にＧＰＵ上で実行されてもよい。このようにして、ＣＰＵとＧＰＵとの間の同期化及びメモリコピーが排除されることが可能である。例えば、これらのオーバヘッドの排除を考慮すると、結果としてのビルダは、前の技法より速い（例えば、５〜１０倍速いなどの）可能性がある。他の実施例では、カーネル時間のみを考慮するだけでも、やはり前の技法より速い（例えば、最大３倍まで速いなどの）可能性がある。
【００４４】
[0049]さらに、一実施形態では、高品質のバウンディングボリューム階層が、中くらいに複雑なモデルのためにでもリアルタイムで生成されることが可能である。他の実施形態では、アルゴリズムは、前のＨＬＢＶＨ実装より速い可能性がある。これは、作業待ち行列の採用によって提供される全体的な簡略化のおかげで可能であり、これは、長い待ち時間のカーネル起動の数をかなり低減することを可能し、データ変換パスを低減することができる。
【００４５】
[0050]さらに、一実施形態では、階層型線形バウンディングボリューム階層（ＨＬＢＶＨ）は、数百万の十分に動的な三角形の前ででも、リアルタイムでのレイトレーシングのために必要とされる空間インデックスを再構築することが可能であってもよい。他の実施形態では、前述のアルゴリズムは、ＨＬＢＶＨのより簡単で速い変形形態を可能にしてもよく、空間パーティショニングのために必要とされるプレフィックス和の複雑な簿記、圧縮、及び部分的幅優先探索木トラバーサルは全て、効率のよい作業待ち行列及び二分探索に加えて構築されるエレガントなパイプラインと取り替えられてもよい。他の実施形態では、新しいアルゴリズムは、より速くて、よりメモリ効率のよい可能性があり、これは中間計算に関する形状データの一時的記憶の必要を除去することができる。さらに、一実施形態では、同じパイプラインが、ＧＰＵ上のトップレベルＳＡＨ最適化木の構築を並列化するために拡張されてもよく、これはＣＰＵへの往復を排除し、それによって構築速度全体を（例えば、５〜１０倍など）加速することができる。
【００４６】
[0051]他の実施形態では、一般化するのが簡単で、速くて、容易な、階層型線形バウンディングボリューム階層（ＨＬＢＶＨ）の新規の変形形態（ＨＬＢＶＨ）が提供されてもよい。一実施形態では、アドホックで複雑なプレフィックス和の混合、圧縮、及び実際のオブジェクトパーティショニングステップを実行するために使用される部分的幅優先探索木トラバーサルプリミティブは、効率のよい作業待ち行列に基づく単一のエレガントなパイプラインと取り替えられてもよい。このようにして、元のＨＬＢＶＨアルゴリズムは簡略化されることが可能であり、より速い速度が提供されることが可能である。さらに、一実施形態では、新しいパイプラインはまた、前には必要とされたことがある全ての追加の一時的記憶の必要を除去することができる。
【００４７】
[0052]さらに、一実施形態では、表面積ヒューリスティック（ＳＡＨ）最適化ＨＬＢＶＨハイブリッドが並列化されてもよい。例えば、タスクベースのパイプラインの追加された柔軟性は、パラレルビニング機構の効率のよさと組み合わされてもよい。このようにして、従来の方法の１０倍までのスピードアップが達成されることが可能である。さらに、パイプライン全体を並列化することにより、全加速構造構築がＧＰＵ上で実行されることが可能であり、これはＣＰＵメモリ空間とＧＰＵメモリ空間との間の費用のかかるコピーを排除することができる。
【００４８】
[0053]さらに、一実施形態では、加速構造を構築するために使用される全てのアルゴリズムがＣＵＤＡ並列計算アーキテクチャを使用して実行されてもよい。例えば、参照によりその全体が本明細書に組み込まれており、ＣＵＤＡでの並列計算の実行を説明している、「Ｓｃａｌａｂｌｅ  ｐａｒａｌｌｅｌ  ｐｒｏｇｒａｍｍｉｎｇ  ｗｉｔｈ  ｃｕｄａ」、（Ｎｉｃｋｏｌｌｓら、ＡＣＭ  Ｑｕｅｕｅ  ６、２、４０〜５３）を参照されたい。さらに、加速構造の構築は、効率のよいソーティングプリミティブを利用して実行されてもよい。例えば、参照によりその全体が本明細書に組み込まれており、効率のよいソーティングプリミティブを説明している、「Ｒｅｖｉｓｉｔｉｎｇ  ｓｏｒｔｉｎｇ  ｆｏｒ  ＧＰＧＰＵ  ｓｔｒｅａｍ  ａｒｃｈｉｔｅｃｔｕｒｅｓ」、（Ｍｅｒｒｉｌｌら、Ｔｅｃｈ．Ｒｅｐ．ＣＳ２０１０−０３、Ｄｅｐａｒｔｍｅｎｔ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ、Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｖｉｒｇｉｎｉａ、Ｆｅｂｒｕａｒｙ）を参照されたい。
【００４９】
[0054]さらに、一実施形態では、加速構造は、ＢＶＨを構築するステップを含んでもよい。例えば、シーンの３Ｄ範囲が次元ごとにｎビットを使用して離散化されてもよく、各点が、（離散化座標の２進数をインタリーブすることにより計算されてもよい）ｎ次の空間充填モートン曲線に沿って線形座標を割り当てられてもよい。他の実施形態では、プリミティブは、次いで、それらの重心のモートンコードに従ってソーティングされてもよい。他の実施形態では、階層は、完全な木が構築されるまで、プリミティブを同じ３ｎビットコードを有するクラスタにグループ化し、次いで同じ３（ｎ−１）高次ビットを有するクラスタをグループ化し、以下同様にすることにより構築されてもよい。他の実施形態では、モートンコードの３ｍ高次ビットは、面ごとに２ｍ分割を有する粗グリッド内の親ボクセルを識別することができ、その結果、このプロセスは、上から下に、空間中央において帰納的にプリミティブを分割するステップに対応することができる。
【００５０】
[0055]さらに、一実施形態では、ＨＬＢＶＨは、複数の方法で基本アルゴリズムに改良を加えることができる。例えば、ＨＬＢＶＨは、入力メッシュにおいて空間及び時間コヒーレンスを利用するために圧縮−ソート−解凍法を利用して、より速い構築アルゴリズムを提供することができる。他の実施例では、ＨＬＢＶＨは、階層の最上位がレベルｍにおいてボクセライゼーションによって定義されたクラスタにわたって表面積ヒューリスティック（ＳＡＨ）スイープビルダを使用して構築される、高品質のハイブリッドビルダを導入することができる。例えば、参照によりその全体が本明細書に組み込まれており、例示的ＳＡＨを説明している、「Ａｕｔｏｍａｔｉｃ  ｃｒｅａｔｉｏｎ  ｏｆ  ｏｂｊｅｃｔ  ｈｉｅｒａｒｃｈｉｅｓ  ｆｏｒ  ｒａｙ  ｔｒａｃｉｎｇ」、（Ｇｏｌｄｓｍｉｔｈら、ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  Ｇｒａｐｈｉｃｓ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ  ７、５、１４〜２０）を参照されたい。
【００５１】
[0056]他の実施形態では、カスタムスケジューラが軽量スレッディングモデルを実施するためにタスク待ち行列に基づいて構築されてもよく、これはビルトインハードウェアスレッドサポートのオーバヘッドを回避することができる。例えば、参照によりその全体が本明細書に組み込まれており、プロトタイプ多コアアーキテクチャのために最適化されたパラレルビニングされたＳＡＨ  ＢＶＨビルダを説明している、「Ｆａｓｔ  Ｃｏｎｓｔｒｕｃｔｉｏｎ  ｏｆ  ＳＡＨ  ＢＶＨｓ  ｏｎ  ｔｈｅ  Ｉｎｔｅｌ  Ｍａｎｙ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｏｒｅ  （ＭＩＣ）  Ａｒｃｈｉｔｅｃｔｕｒｅ」、（Ｗａｌｄ，Ｉ．、ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｖｉｓｕａｌｉｚａｔｉｏｎ  ａｎｄ  Ｃｏｍｐｕｔｅｒ  Ｇｒａｐｈｉｃｓ）を参照されたい。
【００５２】
[0057]図６は、上記の様々な実施形態の様々なアーキテクチャ及び／又は機能が実行されることが可能である例示的システム６００を例示する。図示されているように、通信バス６０２に接続された少なくとも１つのホストプロセッサ６０１を含むシステム６００が提供される。システム６００はまた、メインメモリ６０４を含む。制御ロジック（ソフトウェア）及びデータが、ランダムアクセスメモリ（ＲＡＭ）の形を取ってもよいメインメモリ６０４に記憶されている。
【００５３】
[0058]システム６００はまた、グラフィックスプロセッサ６０６及びディスプレイ６０８すなわちコンピュータモニタを含む。一実施形態では、グラフィックスプロセッサ６０６は、複数のシェーダモジュール、ラスタ化モジュールなどを含んでもよい。上記のモジュールはそれぞれ、単一の半導体プラットフォーム上に配置されてグラフィックス処理ユニット（ＧＰＵ）を形成してもよい。
【００５４】
[0059]本明細書では、単一の半導体プラットフォームは、唯一の単体半導体ベースの集積回路又はチップを指してもよい。単一の半導体プラットフォームという用語はまた、オンチップ動作をシミュレートし、従来の中央処理装置（ＣＰＵ）及びバス実装の利用を大幅に改善する、向上した接続性を有するマルチチップモジュールを指してもよいことに留意されたい。もちろん、これらの様々なモジュールはまた、別々に、又はユーザそれぞれの所望に応じて半導体プラットフォームの様々な組合せで配置されてもよい。
【００５５】
[0060]システム６００はまた、二次記憶装置６１０を含んでもよい。二次記憶装置６１０は、例えば、ハードディスクドライブ、及び／又はフレキシブルディスクドライブ、磁気テープドライブ、コンパクトディスクドライブなどを表す取外し可能なストレージドライブを含む。取外し可能なストレージドライブは、よく知られている方法で、取外し可能なストレージユニットから読み出す、及び／又はそこに書き込む。
【００５６】
[0061]コンピュータプログラム又はコンピュータ制御ロジックアルゴリズムは、メインメモリ６０４及び／又は二次記憶装置６１０に記憶されてもよい。そのようなコンピュータプログラムは、実行された場合、システム６００が様々な機能を実行することができるようにする。メモリ６０４、記憶装置６１０、及び／又は任意の他の記憶装置は、コンピュータ読取り可能媒体の可能な例である。
【００５７】
[0062]一実施形態では、上記の様々な図のアーキテクチャ及び／又は機能は、ホストプロセッサ６０１、グラフィックスプロセッサ６０６、ホストプロセッサ６０１とグラフィックスプロセッサ６０６の両方の機能の少なくとも一部の機能を有する集積回路（図示せず）、チップセット（すなわち、関連機能を実行するためのユニットとして動作するように設計され販売される一群の集積回路など）、及び／又はそのことに関する任意の他の集積回路の文脈で実装されてもよい。
【００５８】
[0063]さらに、上記の様々な図のアーキテクチャ及び／又は機能は、汎用コンピュータシステム、回路基板システム、エンタテインメント専用のゲームコンソールシステム、特定用途向けシステム、及び／又は任意の他の所望のシステムの文脈で実行されてもよい。例えば、システム６００は、デスクトップコンピュータ、ラップトップコンピュータ、及び／又は任意の他のタイプのロジックの形を取ってもよい。さらに、システム６００は、携帯情報端末（ＰＤＡ）デバイス、モバイルフォンデバイス、テレビジョンなどを含むがそれらに限定されない様々な他のデバイスの形を取ってもよい。
【００５９】
[0064]さらに、図示されていないが、システム６００は、通信目的のためにネットワーク（例えば、電気通信ネットワーク、ローカルエリアネットワーク（ＬＡＮ）、無線ネットワーク、インターネットなどの広域ネットワーク（ＷＡＮ）、ピアツーピアネットワーク、ケーブルネットワークなど）に結合されてもよい。
【００６０】
[0065]様々な実施形態が上記で説明されてきたが、それらは、例としてのみ、限定としてではなく、提示されていることを理解されたい。したがって、好ましい実施形態の幅及び範囲は、前述の例示的実施形態のいずれにも限定されるべきではなく、添付の特許請求の範囲の請求項及びそれらの同等物によってのみ定義されるべきである。
【符号の説明】
【００６１】
１０２  動作
１０４  動作
２００  タスク待ち行列システム
２０２Ａ  ワープ［０］
２０２Ｂ  ワープ［１］
２０４  出力要素の数
２０６  ワーププレフィックス和
３０２Ａ〜Ｊ  プリミティブ
３０６Ａ〜Ｊ  シーケンス
３０８  行
３１０  二分探索パーティション
４０２Ａ〜Ｅ  中央分割待ち行列
５０２Ａ〜Ｂ  クラスタ
５０４  ビン統計値
５０６  入力タスク待ち行列
５０８Ａ〜Ｂ  エントリ
５１０  出力待ち行列
６０１  中央プロセッサ
６０２  通信バス
６０４  メインメモリ
６０６  グラフィックスプロセッサ
６０８  ディスプレイ
６１０  二次記憶装置
【図１】
2013037691.tif 000005
【図２】
2013037691.tif 000006
【図３】
2013037691.tif 000007
【図４】
2013037691.tif 000008
【図５】
2013037691.tif 000009
【図６】
2013037691.tif 000010
【外国語明細書】
2013037691000001.pdf