(57)【要約】【課題】ビームトレーシングのコンピュータ実行方法を提供する。【解決手段】ビームトレーシングのコンピュータ実行方法であり、一式のビームは物理的波動現象を表すものであり、その方法は以下のステップを含む：ビーム及び交差する可能性のあるオブジェクトに関する情報を受け取る、ビーム・トライアングル交差テストを実行する、交差テストがネガティブである要素を放棄する、ビームをより小さい部分ビームに分割する、並列プロセスのためにデータを提供する、部分ビームに関して三角形を放棄する、部分ビームをより小さい部分ビームに分割する、より小さい部分ビームを光線に近似させる、各光線に一番近い三角形が存在する場合はその三角形を探す、区切られたより小さい部分ビームを生成する、以前区切られたより小さい部分ビームに選択的に合流させる。【選択図】図１
2015108703.tif 000002
【特許請求の範囲】
【請求項１】
ビームトレーシングのコンピュータ実行方法であり、一式のビームは物理的な波動現象を表すものであり、その方法は以下のステップを含む：
ビーム及び交差する可能性のあるオブジェクトに関する情報を受け取る（３０１）
ビーム・トライアングル交差テストを実行する（３０２）
交差テストがネガティブである要素を放棄する（３０３）
ビームをより小さい部分ビームに分割する（３０４）
並列プロセスのためにデータを提供する（３０５）
部分ビームに関して三角形を放棄する（３０６）
部分ビームをより小さい部分ビームに分割する（３０７）
より小さい部分ビームを光線に近似させる（３０８）
各光線に一番近い三角形が存在する場合はその三角形を探す（３０９）
区切られたより小さい部分ビームを生成する（３１０）
以前区切られたより小さい部分ビームに選択的に合併させる（３１１）。
【請求項２】
交差する可能性のあるオブジェクトに関する情報は、好ましくはシーンツリーなど、オブジェクトにより構成されるシーンの階層あるいは階層的ではない表現として入力される、請求項１に記載の方法。
【請求項３】
部分ビーム及びそれらの部分ビームに関連するそれぞれの三角形の並列プロセスのためのデータを提供すること（３０５）を更に含む、請求項１に記載の方法。
【請求項４】
部分ビームに関する三角形を放棄すること（３０６）は、部分ビームと交差するかに関するテストの結果に基づいて実行され、交差テストがネガティブの場合は実行されない、請求項１に記載の方法。
【請求項５】
区切られたより小さな部分ビームを生成するステップ（３１０）は、この特定のより小さな部分ビームに近似する光線の始まりに一番近い位置にあるオブジェクトでビームを区切ることを含む、請求項１に記載の方法。
【請求項６】
この特定のより小さい部分ビームに近似する光線の始まりに一番近い位置にあるオブジェクトは、レイ・トライアングル交差テストに基づいて決定される、請求項５に記載の方法。
【請求項７】
レイ・トライアングル交差テストはＩｎｇｏ  Ｗａｌｄ氏によるテストである、請求項６に記載の方法。
【請求項８】
レイ・トライアングル交差テストは、ＳＳＥあるいはＡＶＸの指示を使って並行に行われる、請求項６に記載の方法。
【請求項９】
より小さい部分ビームの合流（３１１）は、三角形を一致させることで区切られるより小さい部分ビームに行われる、請求項１に記載の方法。
【請求項１０】
一致する三角形は、同じ面に位置し同じ材料の同一あるいは二つの三角形あるいは同様の面及び同様の特徴を持つ吸音材の面に位置する三角形である、請求項１に記載の方法。
【請求項１１】
一式のビームは音波を表すものである、請求項１に記載の方法。
【請求項１２】
一式のビームが物理的波動現象を表すビームトレーシングのシステムであり、そのシステムは以下を含む：
シーン表現を記憶する階層モデルメモリ（５０７）
レイ・トライアングル及びビームトライアングルタイプの交差テストを行うための専用のシグナルプロセッサ（５０５）
以下のステップを実行するように設定されたバスによりプロセッサ（５０５）に接続されるコントローラ（５０２）；
Ｉ／Ｏコントローラ（５０６）により、ビーム及び交差する可能性のあるオブジェクトに関する情報を受け取る（３０１）
ビーム・トライアングル交差テストを実行する（３０２）
交差テストがネガティブである要素を放棄する（３０３）
ビームをより小さい部分ビームに分割する（３０４）
並列プロセスのためにデータを提供する（３０５）
部分ビームに関して三角形を放棄する（３０６）
部分ビームをより小さい部分ビームに分割する（３０７）
より小さい部分ビームを光線に近似させる（３０８）
各光線に一番近い三角形が存在する場合はその三角形を探す（３０９）
区切られたより小さい部分ビームを生成する（３１０）
以前区切られたより小さい部分ビーム（３１０）に選択的に合併させる（３１１
【請求項１３】
交差する可能性のあるオブジェクトに関する情報は、好ましくはシーンツリーなど、オブジェクトにより構成されるシーンの階層あるいは階層的ではない表現として入力される、請求項１２に記載のシステム。
【請求項１４】
部分ビーム及びそれらの部分ビームに関連するそれぞれの三角形の並列プロセスのためのデータを提供すること（３０５）を更に含む、請求項１２に記載のシステム。
【請求項１５】
部分ビームに関する三角形を放棄すること（３０６）は、部分ビームと交差するかに関するテストの結果に基づいて実行され、交差テストがネガティブの場合は実行されない、請求項１２に記載のシステム。
【請求項１６】
区切られたより小さな部分ビームを生成するステップ（３１０）は、この特定のより小さな部分ビームに近似する光線の始まりに一番近い位置にあるオブジェクトでビームを区切ることを含む、請求項１２に記載のシステム。
【請求項１７】
この特定のより小さい部分ビームに近似する光線の始まりに一番近い位置にあるオブジェクトは、レイ・トライアングル交差テストに基づいて決定される、請求項１６に記載のシステム。
【請求項１８】
レイ・トライアングル交差テストはＩｎｇｏ  Ｗａｌｄ氏によるテストである、請求項１７に記載のシステム。
【請求項１９】
レイ・トライアングル交差テストは、ＳＳＥあるいはＡＶＸの指示を使って並行に行われる、請求項１７に記載のシステム。
【請求項２０】
より小さい部分ビームの合流（３１１）は、三角形を一致させることで区切られるより小さい部分ビームに行われる、請求項１２に記載のシステム。
【請求項２１】
一致する三角形は、同じ面に位置し同じ材料の同一あるいは二つの三角形あるいは同様の面及び同様の特徴を持つ吸音材をの面に位置する三角形である、請求項１２に記載のシステム。
【請求項２２】
一式のビームは音波を表すものである、請求項１２に記載のシステム。
【請求項２３】
コンピュータで実行された場合、請求項１に記載のコンピュータ実行方法の全てのステップを実行する、コンピュータで実行可能な指示を記憶するコンピュータで可読の固定記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、概ねビームトレーシングの分野に関するものであり、特に例えばリアルタイムで音響効果をシミュレートするサウンドトレーシングに関するものである。
【背景技術】
【０００２】
現在、上記の解決法は、リアルタイムレジームを必要としないため計算に時間がかかるアニメ映画及び／又は漫画（カートゥーン）に主に使われている。同じくビデオゲーム業界においては、通常、音の多様な変化のアクテイベーショントリガーを構成するジオメトリー領域が存在する。
【０００３】
「適応フラスタム（Ａｄａｐｔｉｖｅ  Ｆｒｕｓｔｕｍ）」と題する文献において説明される先行技術であるアルゴリズムｈｔｔｐ：／／ｇａｍｍａ．ｃｓ．ｕｎｃ．ｅｄｕ／ＳＯＵＮＤ／ｄａｔａ／ｖｉｓ２００８．ｐｄｆ；（ＡＤ−Ｆｒｕｓｔｕｎ：  Ａｄａｐｔｉｖｅ  Ｆｒｕｓｔｕｍ  Ｔｒａｃｉｎｇ  ｆｏｒ  Ｉｎｔｅｒａｃｔｉｖｅ  Ｓｏｕｎｄ  Ｐｒｏｐａｇａｔｉｏｎ；  Ａｎｉｓｈ  Ｃａｎｄａｋ，  Ｃｈｒｉｓｔｉａｎ  Ｌａｕｔｅｒｂａｃｈ，  Ｍｉｃａｈ  Ｔａｙｌｏｒ，  Ｚｈｉｍｉｎ  Ｒｅｎ，  Ｄｉｎｅｓｈ  Ｍａｎｏｃｈａ，  Ｍｅｍｂｅｒ，  ＩＥＥＥ）及びｈｔｔｐ：／／ｈａｌ．ｉｎｒｉａ．ｆｒ／ｄｏｃｓ／００／５０／９９／８１／ＰＤＦ／ＣＧ９８．ｐｄｆ  （Ａ  Ｂｅａｍ  Ｔｒａｃｉｎｇ  Ｍｅｔｈｏｄ  ｗｉｔｈ  Ｐｒｅｃｉｓｅ  Ａｎｔｉａｌｉａｓｉｎｇ  ｆｏｒ  Ｐｏｌｙｈｅｄｒａｌ  シーン；  Ｄｊａｍｃｈｉｄ  ＧＨＡＺＡＮＦＡＲＰＯＵＲ  ａｎｄ  Ｊｅａｎ−Ｍａｒｃ  ＨＡＳＥＮＦＲＡＴＺ；  Ｌａｂｏｒａｔｏｉｒｅ  ＭＳＩ−  Ｕｎｉｖｅｒｓｉｔｅ  ｄｅ  Ｌｉｍｏｇｅｓ）は、多面体を探知するために適応ビームのサブディビジョンを使用する。理論上、それらの方法によりビームを制限するオブジェクト（他のものに遮断されないビームの範囲のオブジェクト）を素早く見つけることが可能になるが、実際、アルゴリズムに使用される構造はリアルタイムの解決法として使うには高額すぎる（それらを使用するには時間がかかる）。特定のケース、ツリー構造、及び限られた正確さ及び遅いビーム合流アルゴリズムを含む高額な交差テストは、現代的なプロセッサを最大限に利用しない。これらの問題によりアルゴリズムを実施するのは難しく活用の拡大の可能性も低くなる。
【０００４】
「リアルタイム音響合成における光線トレーシングの使用（Ｕｓｉｎｇ  ｒａｙ  ｔｒａｃｉｎｇ  ｆｏｒ  ｒｅａｌ  ｔｉｍｅ  ａｕｄｉｏ  ｓｙｎｔｈｅｓｉｓ）」と題するもう一つの先行技術文献米国特許第８１３９７８０Ｂ２号公報は、サウンドエンジンにより、三次元のシーン内で音波をエミュレートすることで聞き手の位置で最終的な音を測定する可能性を開示するものである。サウンドエンジンは、音の起こる位置から光線を出して三次元のシーンを通してその光線をトレースすることで音波をエミュレートしてもよい。光線は、音の変更の要因がある三次元シーン内でオブジェクトと交差しても良い。聞き手が聞いた最終的な音を測定するために、音の変更の要因及び他の要因（例えば、光線が移動した距離、オブジェクトとの交差の角度等）がサウンドイベントに適用されることもある。
【０００５】
「ＩＥＥＥ  ＴＲＡＮＳＡＣＴＩＮＯＳ  ＯＮ  ＶＩＳＵＡＬＩＺＡＴＩＯＮ  ＡＮＤ  ＣＯＭＰＵＴＥＲ  ＧＲＡＰＨＩＣＳ，  ＶＯＬ．  １３，  ＮＯ．  ６，  ＮＯＶＥＭＢＥＲ／ＤＥＣＥＭＢＥＲ  ２００７年」において出版されたＣｈｒｉｓｔｉａｎ  Ｌａｕｔｅｒｂａｃｈ及びＤｉｎｅｓｈ  Ｍａｎｏｃｈａによる「Ｉｎｔｅｒａｃｔｉｖｅ  Ｓｏｕｎｄ  Ｒｅｎｄｅｒｉｎｇ  ｉｎ  Ｃｏｍｐｌｅｘ  ａｎｄ  Ｄｙｎａｍｉｃ  ｓｃｅｎｅｓ  ｕｓｉｎｇ  Ｆｒｕｓｔｕｍ  Ｔｒａｃｉｎｇ」と題する別の先行技術文献は、動的なソース及びオブジェクトの複雑及び仮想的なシーンにおけるリアルタイムのサウンドレンダリングの方法を開示する。同方法は、インタラクティブな光線トレーシングの有効性と立体表現のトレーシングの正確さを組み合わせたものである。その方法では、凸状の四角錐台が使用され、レイパケットトレーシングを使ってクリッピング及び交差テストを行う。単純で能率的な方式を使用して二次的な角錐台を計算し階層トラバーサルを行う。しかしながら、アルゴリズムはリアルタイムのシミュレーション及びハイエンドなＰＣでレンダリングを行えない。この方法は、とても複雑であるため現在のハードウェアの解決法でのゲームにおいてリアルタイムで実行するには不可能である。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】米国特許第８１３９７８０Ｂ２号公報
【非特許文献】
【０００７】
【非特許文献１】ＡＤ−Ｆｒｕｓｔｕｍ：  Ａｄａｐｔｉｖｅ  Ｆｒｕｓｔｕｍ  Ｔｒａｃｉｎｇ  ｆｏｒ  Ｉｎｔｅｒａｃｔｉｖｅ  Ｓｏｕｎｄ  Ｐｒｏｐａｇａｔｉｏｎ；  Ａｎｉｓｈ  Ｃｈａｎｄａｋ，  Ｃｈｒｉｓｔｉａｎ  Ｌａｕｔｅｒｂａｃｈ，  Ｍｉｃａｈ  Ｔａｙｌｏｒ，  Ｚｈｉｍｉｎ  Ｒｅｎ，  Ｄｉｎｅｓｈ  Ｍａｎｏｃｈａ，  Ｍｅｍｂｅｒ，  ＩＥＥＥ
【非特許文献２】Ａ  Ｂｅａｍ  Ｔｒａｃｉｎｇ  Ｍｅｔｈｏｄ  ｗｉｔｈ  Ｐｒｅｃｉｓｅ  Ａｎｔｉａｌｉａｓｉｎｇ  ｆｏｒ  Ｐｏｌｙｈｅｄｒａｌ  シｓｃｅｎｅｓ；  Ｄｊａｍｃｈｉｄ  ＧＨＡＺＡＮＦＡＲＰＯＵＲ  ａｎｄ  Ｊｅａｎ−Ｍａｒｃ  ＨＡＳＥＮＦＲＡＴＺ；  Ｌａｂｏｒａｔｏｉｒｅ  ＭＳＩ−  Ｕｎｉｖｅｒｓｉｔｅ  ｄｅ  Ｌｉｍｏｇｅｓ
【非特許文献３】ＩＥＥＥ  ＴＲＡＮＳＡＣＴＩＯＮＳ  ＯＮ  ＶＩＳＵＡＬＩＺＡＴＩＯＮ  ＡＮＤ  ＣＯＭＰＵＴＥＲ  ＧＲＡＰＨＩＣＳ，  ＶＯＬ．  １３，  ＮＯ．  ６，  ＮＯＶＥＭＢＥＲ／ＤＥＣＥＭＢＥＲ  ２００７において出版された「Ｉｎｔｅｒａｃｔｉｖｅ  Ｓｏｕｎｄ  Ｒｅｎｄｅｒｉｎｇ  ｉｎ  Ｃｏｍｐｌｅｘ  ａｎｄ  Ｄｙｎａｍｉｃ  ｓｃｅｎｅｓ  ｕｓｉｎｇ  Ｆｒｕｓｔｕｍ  Ｔｒａｃｉｎｇ」  ｂｙ  Ｃｈｒｉｓｔｉａｎ  Ｌａｕｔｅｒｂａｃｈ，  Ａｎｉｓｈ  Ｃｈａｎｄａｋ，  ａｎｄ  Ｄｉｎｅｓｈ  Ｍａｎｏｃｈａ
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明の目的は、リソースを計算することに関してより能率的であり、必要な結果を得る時間を短くすることでリアルタイムのサウンドトレーサーを作成することを可能にする、ビームトレーシングで可視性を決定するコンピュータ実行方法を提供することである。
【課題を解決するための手段】
【０００９】
本発明の対象は、ビームトレーシングのコンピュータ実行方法であり、一連のビームは物理的な波動現象を表すものであり、その方法は以下のステップを含む、
ビーム及び交差する可能性のあるオブジェクトに関する情報を受け取る、
ビーム・トライアングル交差テストを実行する、
交差テストがネガティブである要素を放棄する、
ビームをより小さい部分ビームに分割する、
並列プロセスのためにデータを提供する、
部分ビームに関して三角形を放棄する、
部分ビームをより小さい部分ビームに分割する、
より小さい部分ビームを光線に近似させる、
各光線に一番近い三角形が存在する場合はその三角形を探す、
区切られたより小さい部分ビームを生成する、
以前区切られたより小さい部分ビームに選択的に合併させる。
【００１０】
本発明の他の対象は、一連のビームが物理的波動現象を表すビームトレーシングのシステムであり、そのシステムは以下を含む、
シーン表現を記憶する階層モデルメモリ、
レイ・トライアングル及びビームトライアングルタイプの交差テストを行うための専用のシグナルプロセッサ、
以下のステップを実行するように設定されたバスによりプロセッサに接続されたコントローラ、
Ｉ／Ｏコントローラを介して、ビーム及び交差する可能性のあるオブジェクトに関する情報を受け取る、
ビーム・トライアングル交差テストを実行する、
交差テストがネガティブである要素を放棄する、
ビームをより小さい部分ビームに分割する、
並列プロセスのためにデータを提供する、
部分ビームに関して三角形を放棄する、
部分ビームをより小さい部分ビームに分割する、
より小さい部分ビームを光線に近似させる、
各光線に一番近い三角形が存在する場合はその三角形を探す、
区切られたより小さい部分ビームを生成する、
以前区切られたより小さい部分ビームに選択的に合併させる。
【００１１】
本発明のもう一つの目的は、コンピュータで実行された場合、本発明に係るコンピュータ実行方法の全てのステップを実行する、コンピュータで実行可能な指示を記憶するコンピュータで読みとり可能な固定記憶媒体を提供することである。
【００１２】
好ましくは、交差する可能性のあるオブジェクトに関する情報は、好ましくはシーンツリーなど、オブジェクトにより構成されるシーンの階層あるいは階層的ではない表現として入力される。
【００１３】
好ましくは、同方法は、更に部分ビーム及びそれらの部分ビームに関連するそれぞれの三角形の並列プロセスのためのデータを提供する。
【００１４】
好ましくは、部分ビームに関する三角形を放棄することは、部分ビームと交差するかに関するテストの結果に基づいて実行され、交差テストがネガティブの場合は実行されない。
【００１５】
好ましくは、区切られたより小さな部分ビームを生成するステップは、この特定のより小さな部分ビームに近似する光線の始まりに一番近い位置にあるオブジェクトでビームを区切ることを含む。
【００１６】
好ましくは、この特定のより小さい部分ビームに近似する光線の始まりに一番近い位置にあるオブジェクトは、レイ・トライアングル交差テストに基づいて決定される。
【００１７】
好ましくは、レイ・トライアングル交差テストは、Ｉｎｇｏ  Ｗａｌｄ氏によるテストである。
【００１８】
好ましくは、レイ・トライアングル交差テストは、ＳＳＥあるいはＡＶＸの指示を使って並行に行われる。
【００１９】
好ましくは、より小さい部分ビームの合流は、三角形を一致させることで区切られるより小さい部分ビームに行われる。
【００２０】
好ましくは、一致する三角形は、同じ面に位置し同じ材料の同一あるいは二つの三角形あるいは類似又は同様の特徴を持つ吸音材を有する面に位置する三角形である。
【００２１】
好ましくは、一連のビームは音波を表すものである。
【図面の簡単な説明】
【００２２】
本発明の対象は、以下の図面の例示的な実施形態において説明される。
【図１】図１は、レイ・トライアングル方法の使用法を表す４つの例を示す図である。
【図２】図２は、ビームの予め決められた数のセクションへの分割と、それぞれのセクションの別の光線との近似を表す図である。
【図３】図３は、適応レイ・フラスタムのプロセスを示す図である。
【図４Ａ】図４Ａは、例示的なシーンにおける本発明に係る方法を示す図である。
【図４Ｂ】図４Ｂは、例示的なシーンにおける本発明に係る方法を示す図である。
【図４Ｃ】図４Ｃは、例示的なシーンにおける本発明に係る方法を示す図である。
【図４Ｄ】図４Ｄは、例示的なシーンにおける本発明に係る方法を示す図である。
【図４Ｅ】図４Ｅは、例示的なシーンにおける本発明に係る方法を示す図である。
【図４Ｆ】図４Ｆは、例示的なシーンにおける本発明に係る方法を示す図である。
【図４Ｇ】図４Ｇは、例示的なシーンにおける本発明に係る方法を示す図である。
【図４Ｈ】図４Ｈは、例示的なシーンにおける本発明に係る方法を示す図である。
【図４Ｉ】図４Ｉは、例示的なシーンにおける本発明に係る方法を示す図である。
【図５】図５は、本発明に係るシステムのブロック図である。
【発明を実施するための形態】
【００２３】
表記と名称
【００２４】
以下の詳細な説明の幾つかの部分は、データ処理手順、ステップあるいはコンピュータメモリ上で実行可能なデータビットの操作の他の象徴として示されている。従って、コンピュータはそれらの論理的ステップを実行するため物理量の物理的な操作が必要になる。
【００２５】
通常、それらの物理量は、コンピュータシステムで保存、転送、組み合わせ、比較及び操作することが可能な電気あるいは磁気信号という形をとる。一般的な使用法の理由で、これらの信号は、ビット、パケット、メッセージ、値、要素、記号、文字、用語、数字等と称される。
【００２６】
また、それら及び同様の用語の全ては、適当な物理量と関連付けられ、それらの物理量に適用される便利な呼び名にすぎない。「処理」、「作成」、「転送」、「実行」、「測定」、「検出」、「取得」、「選択」、「計算」、「生成」、あるいは同様の用語は、コンピュータのレジスタ及びメモリ内に物理（電子的）量として表されるデータを操作し、同様にメモリ、レジスタあるいは他の情報記憶装置内などに物理量として表される他のデータに変換するコンピュータシステムの処置およびプロセスのことを示す。
【００２７】
ここにビームは多角形の底面を持つ三次元のオブジェクト（しばしば面に位置する）であり、定められた範囲及び底面の項点から生じるエッジベクトルを有する（それらの全てのベクトルは、半面に向けられているはずである）。
【００２８】
エッジベクトルの延長が特定の点で交差する場合、その点は頂点と呼ばれる。例えば、四角形の底面を持つビームの場合、４つのうち２つのベクトルが一つの点で交差し、他の２つが２つ目の点で交差することがある。そのような場合、ビームは実質的にはエッジにおいて始まる。
【００２９】
最適な底面は三角形及び四角形であるが、本方法は如何なる多角形にも使用できる。四角形の底面を持つビームはしばしば角錐台と呼ばれる。
【００３０】
本発明は、適応レイフラスタムと呼ばれる新たな方法であり、適応フラスタムアルゴリズムを拡張するための反復的な試み及び拡張が性能にどう影響を与えるかについてテストを行った後考案された。
【００３１】
この方法は、少ない数の複雑なテストをより多い数のより単純なテストに代えることが有利であるとする見解に基づく。実際、適応フラスタムアルゴリズムにおいてビーム細分を管理するのに使用される四分木構造の大部分は少ない数の三角形を足すと最大レベルの細分に達する。多くの場合、適応レイフラスタムにおいて使用された単純なテストの数は、適応フラスタム(Adaptive Ray-Frustum)において使用された複雑なテストの数を下回ることができることが判明した。
【００３２】
本発明に係る方法は、十分に小さいビームは光線で近似することが可能であるという仮定に基づく。例えば、上記のように音のシミュレーションに使用されたシーンにおけるオブジェクトは、シーンにおける相当するグラフィックオブジェクトに比べてずっと単純である。それは、小さなサイズのビームが光線で近似された場合、エラーの可能性が低いことを意味する。また、ビームのほとんどは、完全に遮断されているか、まったく遮断されていない。
【００３３】
ビームとの交差に関してテスト済みの三角形が、ビームの全ての部分について交差テストを実行する必要があるほど十分に大きいと仮定する場合（ビームのｋ回目のクリッピングの後、部分の数は４ｋ）、４ｋ＋１−１回のテストが行われる。
【００３４】
本発明は、４ｋまでのより単純なテスト及び４ｐ−１までの複雑なビーム・トライアングルテストを導入する。ｐおよびｋのパラメータの適当な選択により処理速度をかなり上げることができるため実行時間が大幅に短くなる。
【００３５】
ビームを光線で近似
【００３６】
ビームを幾つかに分ける細分化は、三角形がビームの適当に小さい部分と交差するか否かのバイナリ判定を可能にする。交差している場合、ビームが交差する三角形の一部はビームを完全に遮断すると推測される。これは、とても小さいビームだけに当てはまる。
【００３７】
そのような単純化された方法が利用されることが決定したため、ビーム及び三角形間で高額な交差テストを利用する必要はないと見てよい。この高額なテストは、ビームの中心を通った光線が三角形と交差したか否かの単純な確認法と置き換えても良い。
【００３８】
その一方で、より大きいビームが光線で近似されるとエラーが多発し適切な三角形が拒絶される場合がある。以下は解決法の個々の要素の説明である。
【００３９】
大きいビームと小さいビームの違いは、所定のシーンを考慮した適切な分割にある。多数の三角形を探知するのを可能にする分割からは小さいビームが得られ、多数のオブジェクトの探知を可能にしない分割では大きいビームが得られる。これは定量的アプローチである。例えば、音に一点の源がある場合、その源の六角形の異なる側面から起因する６つのビームが放射される。
【００４０】
ビームが部分ビームに分割されない場合、それぞれに１つの側面が探知され、音は多くても６つの異なる側面から反射される。各ビームが一回分割される場合、２４の部分ビームが発生し、それは音が反射するオブジェクトの数は多くて２４であることを意味する。２回の分割の場合、最大９６個のオブジェクトが探知され、３回の分割の場合は最大３８４個のオブジェクトがあり、４回の分割の場合は最大１５３６個のオブジェクトが探知される。
【００４１】
従って、大きいビームは、シーンに関して十分に分割されていなく多数のオブジェクト（三角形）を探知することができないビームを意味する。この問題は、ビームが分割されていないうえ光線が三角形を外したため大きい三角形が全く探知されなかった図１Ｃに部分的に示されている。図１Ｄに示されるように、小さい三角形が大きい三角形を遮断し、ビームの分割が不十分であった場合（大きいビーム）、より大きな三角形は探知されない。
【００４２】
以上の記述定義は、方程式により定量的に定義されてもよい。即ち、この方法は、ｈは所定のオブジェクトへの距離でありｐは分割の数である場合、（２＾（ｐ−１））／ｈより小さいオブジェクトは探知しない。例えば、分割が４回行われて、オブジェクトが１０メートル離れている場合、同方法による解答は１．２５メートルであり、この数字よりも大きいオブジェクトしか確実に探知されない。より小さいオブジェクトが探知される可能性はある程度だけあるが、確実性はない。
【００４３】
適応フラスタムにおけるレイ・トライアングル交差テストの使用
【００４４】
適応フラスタムアルゴリズムの性能テストによると、同テストの計算的に最も高額な部分は交差テストである。そのテストは頻繁に実行され、毎回大量の計算が必要なだけでなく所定のサブビームに関する情報をメモリにロードすることを必要とする。
【００４５】
交差アルゴリズムをスピードアップさせる望ましい方法は、上記のテスト実行の必要性をなくすことである。しかしながら、全ての三角形について可能ではない。交差テストを簡素化することでビームの処理を大幅にスピードアップさせることができる。更に改善するには、「ビーム・トライアングル」交差テストを「レイ・トライアングル」テストに置き換える。
【００４６】
残念ながら、ビームを光線で近似することは、大きいビームには不正確である。この場合、場合によっては制限されるため、ビームの中心を通る光線と交差するオブジェクトだけが考慮される。この方法は、大きいビームには無効である。そのような簡素化テストを適切なレベルのビーム細分化と合わせて大きいビームに使用するとアルゴリズムの正確さは大幅に下がる。
【００４７】
図１は、レイ・トライアングル方法を使用する４つの例を示す。例（ａ）は、ビームのスタート面１０３から始まるビーム１０２を近似する光線１０１を示す。
【００４８】
例（ｂ）は、三角形１０４と交差する光線を示す。三角形１０４は、そのためビームと交差すると分類される。
【００４９】
例（ｃ）は、ビームと交差する大きい三角形１０５を示すが、ビームを近似する光線１０１は三角形１０５と交差しない。その結果、三角形１０５は、ビームと交差しないと誤って分類される。
【００５０】
例（ｄ）は、ビーム１０２と交差する２つの三角形１０４及び１０６を示す。近似する光線１０１は、両方の三角形と交差し、小さいほうの三角形１０６は、光線の始まりにより近い。より小さい三角形１０６は、ビーム１０２の全ての面をカバーすると分類されるが、大きい三角形１０４のほうがよい対象である。
【００５１】
光線のグリッドを利用するアルゴリズム
【００５２】
大きいビームを光線で近似する問題を解決するには、図２に示されるようにビームを予め決められたの数の区分に均一に分割し、それらの各区分を別々の光線と近似する。
【００５３】
図２の例（ａ）は、ビームが４つの光線と近似される可能性を示す。この方法により４倍の正確さが可能となる。分割がない場合、ビームと交差する三角形のうち１つの三角形が探知される可能性を意味する。４つの部分ビームに分割することで４つの三角形の探知が可能になる。更に分割することで正確さが向上するが計算力も増大する。
【００５４】
４つの光線のテストはＳＳＥ（Ｓｔｒｅａｍｉｎｇ  ＳＩＭＤ  Ｅｘｔｅｎｓｉｏｎｓ）指示を使用することで効果的に早められる。例（ｂ）は、ビームの三回の分割に相当する、１６の光線とのビームの近似を示す。
【００５５】
また、ＡＶＸ（Ａｄｖａｎｃｅｄ  Ｖｅｃｔｏｒ  Ｅｘｔｅｎｓｉｏｎｓ）の指示を使用することで、２回のテストで所定の三角形で全ての光線の交差テストを実行することが可能になり（ベクトル指示なしでの１６回に代わる）、更にスピードアップされる（使用された指示及びメモリへのアクセス数によって３から４倍の範囲）。
【００５６】
ＳＳＥを使用することで４回で１つの三角形と１６の光線の交差テストを行うことを可能になり、４倍まで速度が上がる。ＡＶＸがＳＳＥと主に異なるのは、ＡＶＸはデータ処理中に２倍の計算を実行することである。
【００５７】
光線のグリッドを作成した後、光線の始まりから三角形の面の方向ベクトルの距離が最短である三角形が各光線について見い出されなければならない。
【００５８】
それは処理されるビームの部分を制限する三角形であるとみなされる。区切るオブジェクトからの反射により作成されるビームの数を減少するためには、一致する三角形により制限されるビームの部分を合流する追加的ステップが導入される（一致する三角形は、同じ三角形、あるいは同じ面に位置し同じ材料の２つの異なる三角形、および同様の垂直及び面接触、及び同様の特性の音響材料を持つ面に位置する三角形である）。
【００５９】
このアプローチにおいて、制限する三角形を見出すステップの間、アルゴリズムの適合性は処理の効果的に最終段階に押される。
【００６０】
上記の解決法は適応フラスタムアルゴリズムにおいて提案されるものよりもかなり単純である。上記の解決法は、ツリー構造を必要とせず、保持されたビームの部分の半分までを除去し、ビーム部分の説明に必要なデータのサイズを大幅に減らす。
【００６１】
実際、（全ての三角形をスキャンして光線との交差テストを実行することで）各光線に一番近い三角形が見つかった場合、アルゴリズムのその部分におけるメモリ使用量を大幅に減らすことが可能である。
【００６２】
ここに記載のアプローチの問題は、テストされたレイ・トライアングルの交差点が多数あることである。ビームと交差する可能性のある三角形の数は多いが、これらの三角形の多くは最終的にはビームを制限しないことがわかる。それでも、小さい値の最大のビーム細分化には提示されるこの方法が適応フラスタムに基づくアプローチよりも効率的である。
【００６３】
ビーム・トライアングル及びレイ・トライアングルを組み合わせた解決法
【００６４】
ビームに直接作用するアルゴリズム及び光線だけに作用するアルゴリズムには重大な欠点がある。一つ目のアルゴリズムは、コストが高いテストの条件によりされるが、階層的処理が早い三角形の排除を可能にする。二つ目のアルゴリズムでは一つの三角形をより早く処理することができるが、確認された三角形の数が多すぎる。
【００６５】
この問題の解決法は、両方のアルゴリズムの利点を組み合わせることである。「ビーム・トライアングル」交差テストは大きいビームに適するため、ビームと確実に交差しない三角形を粗く除外する速く不正確なテストを効率をよくするため使用しても良い。ビーム交差テストにより減らされた所定のシーンにおいて処理される三角形の数は、単純な「レイ・トライアングル」交差テストの数を大きく減らす。これにより性能が良くなる。
【００６６】
上記の方法を改良するもう一つの方法は、最大数の三角形を破棄する「ビーム・トライアングル」テストの応用でビームをｐ倍分割する方法である。このステップを実行した後、所定のビームの区分がｋ−ｐ倍分割され、得られた区分は光線と近似される。
【００６７】
実用的なテストは最良の結果を示すｐの値は、適用された「レイ・トライアングル」交差テスト及び実行するにあたって使用されたベクトル指示によってｋ／４からｋ／２の間であることを示す。ｋ／４からｋ／２の間の値の選択はシーンによるため、所定のシーンのテストを行うのが最も良い。デフォルトの値が適用されてもよい。
【００６８】
Ｉｎｇｏ  Ｗａｌｄテスト
【００６９】
このテストは光線の三角形の面との交差点の重心座標を計算するための事前に計算された値の使用に基づくものである。このアルゴリズムは、一つの三角形との交差があるかに関していくつかの光線が同時にテストされる、ベクトル指示を使った実施によく適している。
【００７０】
図４は、部分ビームが特定の数の光線と近似することを示す。その後、所定の部分ビームと交差する各三角形には、それらの部分ビームと近似する光線との交差が実行される。この時点でＩｎｇｏ  Ｗａｌｄテストなどの交差テストが必要となる。テストは、Ｍｏｌｌｅｒ−Ｔｒｕｍｂｏｒｅに定義される座標（Ｐｌｕｃｋｅｒ  ｃｏｏｒｄｉｎａｔｅｓ）テストあるいは以下の他の如何なる交差テストでもよい：
−Ｍｏｌｌｅｒ  Ｔｏｍａｓ  ｉ  Ｔｒｕｍｂｏｒｅ  Ｂｅｎ．  Ｆａｓｔ，  ｍｉｎｉｍｕｍ  ｓｔｏｒａｇｅ  ｒａｙ−ｔｒｉａｎｇｌｅ  ｉｎｔｅｒｓｅｃｔｉｏｎ．    Ｊｏｕｒｎａｌ  ｏｆ  Ｇｒａｐｈｉｃｓ  Ｔｏｏｌｓ  ２（１）．  １９９７，  ｓ．  ２１−２８；
−Ｓｈｅｖｔｓｏｖ  Ｍａｘｉｍ，  Ｓｏｕｐｉｋｏｖ  Ａｌｅｘｅｉ  ｉ  Ｋａｐｕｓ  Ａｌｅｘａｎｄｅｒ；  Ｒａｙ−Ｔｒｉａｎｇｌｅ  Ｉｎｔｅｒｓｅｃｔｉｏｎ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ｍｏｄｅｒｎ  ＣＰＵ  Ａｒｃｈｔｉｅｃｔｕｒｅｓ．    Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＧｒａｐｈｉＣｏｎ’２００７  ｃｏｎｆｅｒｅｎｃｅ，  ２００７；
−Ｗａｌｄ  Ｉｎｇｏ；  ｒｅａｌｔｉｍｅ  Ｒａｙ  Ｔｒａｃｉｎｇ  ａｎｄ  Ｉｎｔｅｒａｃｔｉｖｅ  Ｇｌｏｂａｌ  Ｉｌｌｕｍｉｎａｔｉｏｎ．  ＰｈＤ  Ｔｈｅｓｉｓ．  Ｓａａｒｂｒｕｃｋｅｎ：  Ｍａｘ−Ｐｌａｎｃｋ−Ｉｎｓｔｉｔｕｔ  ｆｕｒ  Ｉｎｆｏｒｍａｔｉｋ，  ２００４．
【００７１】
アルゴリズムの実施には３つのバージョンが考えられる。
ベクトル指示を使わない実施、
ＳＳＥ指示を使う実施、これは１つの三角形に対し、一度に４つの光線の交差テストを行うことが可能である、
ＡＶＸ指示を使う実施、これは１つの三角形に対し、一度に８つの光線の交差テストを行うことが可能である。
【００７２】
また、１つの光線での複数の三角形の交差、及び１つの三角形での１つの光線の交差の促進が実施される可能性もある。ＡＶＸ及び／又はＳＳＥの使用、及び一度における複数の光線のテストが通常のＰＣにおいて最も効率的であると証明されたが、他のバージョンが他のプラットフォームではより効率的、あるいは特定のハードウェアにおいて実施しやすい可能性がある。
【００７３】
適応レイフラスタムアルゴリズム
【００７４】
適応レイフラスタムアルゴリズムは、前の段階で作られた「レイ・トライアングル」テストの数を減らすために２段階の三角形処理を使用する。同処理の最初の段階においてビームあるいはその一部と確実に交差しない三角形を排除する。また、ビームと交差する近似する一連の三角形を提供するためにシーン・ツリーが使用される。それらのオブジェクトは、階層あるいは非階層的構造と定義され、シーンの空間分割を提供することが可能である。
【００７５】
アルゴリズムのこの部分の分割の最大のデプスはｐに設定されている。ビームと交差している可能性のある三角形のリストから、「ビーム・トライアングル」テストが肯定的な結果を返すものが選択される。次に、そのリストはビームの４つの部分のそれぞれで同様に処理される。そして、ｐステップの後、結果として生じるビームを制限する可能性のある三角形のリストはアルゴリズムの２つ目の部分に渡される。
【００７６】
適応レイフラスタムアルゴリズムの２段階目の処理において、ビームは区分にｋ−ｐフォール度に分割され、ビームの各区分は光線に近似される。最初の段階で得られたそれぞれの三角形にはビームのその部分を近似する全ての光線との交差テストが実行される。
【００７７】
それぞれの光線の状態はその光線と交差する三角形及び交差点への距離により説明される。テストされた三角形が、光線の現在の状態よりで記録されたものよりも近く、交差テストが肯定的である場合、光線の状態は更新される。
【００７８】
アルゴリズムの最後のステップは、アルゴリズムに記憶されるビームの数を減らすために一致するビームの合流を試みることである。
【００７９】
上記の方法は疑似コードとして以下の方法で公式化される：
【００８０】
「適応レイフラスタム方法」
【数１】
2015108703.tif 000003
【００８１】
「ビーム処理方法」
【数２】
2015108703.tif 000004
【００８２】
「一連の光線を処理する方法」
【数３】
2015108703.tif 000005
【００８３】
一番近い三角形を見出いプロセスは、オブジェクトのリストをスキャンし、光線と交差し、光線の源から交差点の距離が最短であるものを選択するほど単純でもよい（その時点でレイ・トライアングル交差テストが適用される）。
【００８４】
代わりに、ビームのソース面から１つの頂点の距離により三角形を分類してもよい（時々、まだスキャンされていない三角形の最短距離よりも近い一番近い三角形が見つかった場合、処理は止められてもよく、一番近い三角形の探知を早く完了する）。
【００８５】
ビームを合流するアルゴリズム
【００８６】
ビームを幾つかの部分に均一に分割することで一致する部分の合流をかなり単純化することができる。一致する部分は、隣接し、同一の三角形あるいは同じ物質で同じ面に位置する三角形により制限される部分である。スイープアルゴリズムは、部分ビームのグリッドを検索し、一致する三角形により制限される領域を探すために使用される（一致する部分ビームは一致する三角形により制限される）。そして、それらの領域は、ビームトレーシングのためのアルゴリズムで処理されるビームの数を減らすために合流される。
【００８７】
ビーム合流は、ビームはｋ回分割されると４ｋ部分になり、反射されたビームが４ｋ生成されることを意味し、有利である。反射されたそれぞれのビームは、４ｋ部分にｋ回分割され、最大４ｋ＊４ｋ＝４２ｋのビームが得られる。例えば、反射だけが可能なサウンドトレーシングエンジンにおいて源が６つのビームを放射すると仮定すると、アルゴリズムにおいて生成されるビームの最終の最大数は、６＊（１＋４ｋ＋４２ｋ＋４４ｋ）である。ｋ＝０の場合、ビームの数は最大２４、ｋ＝１の場合、ビームの最大数は１６６２、ｋ＝２の場合、ビームの最大数は３９４８５４、そしてｋ＝３の場合、ビームの最大数は１００６８８２６２である。それぞれのビームが６４部分に分割されると１億以上になり容認できない数となる。
【００８８】
ビームの数を制限することは、これらのビームが更に処理されるため、一度目及び２度目の反射においては特に有利である。例えば、例示的テストモデルにおいて通常のアルゴリズムにおいて１．３５秒で１４２５３８３のビームが生成されたのに対し、ビームを合流させる新しいアルゴリズムを使用した後は、その数は４５５９に減り、実行時間は０．０４秒だった。
【００８９】
図３は、適応レイフラスタムのプロセスを示す。ステップ３０１において音波ビーム及び交差し得るオブジェクトに関する情報が受け取られる（シーン・ツリーを使用）。疑似コードとして以前示された適応レイフラスタム方法において、このステップは１行目に相当する。そして、ステップ３０２において、「ビーム・トライアングル」交差テストが実行される。以前に疑似コードにおいて示されたビーム処理方法において、このステップは２行目に相当する。交差テストが否定的であるこれらの要素は、ステップ３０３破棄される。
【００９０】
同方法の最初の大部分が完了した後、ステップ３０４においてビームをより小さい部分ビームに分割する手順に進む。疑似コードとして以前示されたビーム処理方法において、このステップは３−４行目に相当する。続いて、ステップ３０５において、例えば、２つの部分ビーム及び部分ビームに関して更に処理されるそれぞれの三角形など、並列処理のためのデータが提供される。以前、疑似コードとして示されたビーム処理方法において、このステップは３−４行目に相当する。
【００９１】
次に、ステップ３０６において、部分ビームに対して三角形の破棄が実行される。シーン要素は、部分ビームと交差するか確認される。交差テストが否定的であるものは破棄される。以前、疑似コードにおいて示されたビーム処理方法において、このステップは２行目に相当する。
【００９２】
次に、ステップ３０７において、部分ビームは、より小さい部分ビームに分割される。以前、疑似コードとして示された一連の光線の処理方法において、このステップは一行目に相当する。その後、ステップ３０８において、ステップ３０７の部分ビームは光線で近似される。以前、疑似コードにおいて示された一連の光線の処理方法において、このステップは２行目に相当する。次に、ステップ３０９において、存在する場合、それぞれの光線に一番近い三角形が探知される。以前、疑似コードにおいて示された一連の光線の処理方法において、このステップは３行目に相当する。その後、ステップ３１０において、区切られた部分ビームが生成される。前のステップにおけるそれぞれの光線は、一つの部分ｔ系ビームに相当する。その部分ビームは、ステップ３０７のこの特定の部分ビームを近似する光線の始めに一番近く位置するオブジェクトにより区切られる。以前疑似コードにおいて示された一連の光線を処理する方法において、このステップは、４行目に相当する。
【００９３】
方法３１１の最終ステップでは、以前区切られた部分ビームに選択的に合流を行う。このステップは、処理の結果を制限するために実行される。疑似コードにおいて以前示された適応レイフラスタムにおいて、このステップは６行目に相当する。
【００９４】
図４Ａから４Ｉは、例示的シーンにおいて本発明に係る方法を示す。シーンは、一つのビームを構成する図４Ａに示すように、１つのビーム及び５つの障害物Ｐ１からＰ５を構成する。図４Ｂは、ステップ３０２及び３０３を実行した結果を示すものであり、Ｐ５の全体とＰ１オブジェクトの一部が、初期メインビームと交差しないとして破棄されている。図４Ｃは、例としてビームが２つの部分ビームに分割された方法のステップ３０４の結果を示す。図４Ｄは、同方法のステップ３０５及び３０６の結果を示す。左の部分ビーム及び右の部分ビームの並列処理のデータが提供され、以前に定義された部分ビームに関しオブジェクトが破棄される。
【００９５】
図４Ｅは、同方法のステップ３０７に従った左の部分ビーム及び右の部分ビームの更なる分割を示す。図４Ｆは、部分ビームが光線と近似された方法のステップ３０８を示す。図４Ｇは、それぞれのビームに一番近い三角形が見つけられる同方法のステップ３０９を示す。図４Ｈは、同方法のステップ３１０及び結果として区切られた部分ビームを示す（この段階では、部分ビームの処理が再開されているため、光線ではない）。
【００９６】
最後に、図４Ｉは、部分ビームの合流が行われたステップ３１１の最終結果を示すものである。この場合、Ｐ３オブジェクトにより区切られた２つの部分ビームを合流することが可能であった。部分ビームを合流するＰＳオブジェクトの側面が異なる面に位置するため、Ｐ２の部分ビームを合流することはできない。その結果を最適な結果と比較することで、係数の適当な選択により正確な結果の許容範囲の近似が得られることを確定することが可能である。部分ビームを合流する段階は、この場合、部分ビームの最終的な数を８から７に減らすことができる。実際、合流アルゴリズムを使用した後、ビームの最終的な数が何度も減る状況が頻繁に起こる。
【００９７】
図４における全ての例は、二次元で描写されている。表示されているオブジェクトは、三次元のスペースにおいてはピラーである（図４のように、上面図ではなく正面図）。ピラーの斜視図のそれぞれの縁は、三角形により三次元に表されている。
【００９８】
図５は本発明に係るシステムのブロック図である。本発明に係るシステム５０１は既存のＧＰＵユニットと同様の役割を果たす専用のハードウェアモジュールとして作られても良い。そのようなモジュールは、ビームとシーンツリーを保存する階層モデルメモリ５０７及び交差テスト（レイ・トライアングル及びビーム・トライアングルの両方）を行う専用の信号プロセッサ５０５の２つの中心的な部分に分けられる。モジュールは、シーン表現を使うことでソース及びレシーバーの位置によりＧＰＵ（グラフィック処理装置）が画像をレンダリングするように使用されるのと同様の方法で音を生成するリアルタイムサウンドトレーシングを行うハードウェアの一部でもよい。
【００９９】
また、Ｉ／Ｏコントローラ５０６及びメモリ５０３と協力してリアルタイムサウンドトレーシングを行う上記の方法のステップを実行する多目的コントローラ５０２がある。
【０１００】
内部回路は上記のアルゴリズムのハードウェア実装から成る。ソフトウェアからハードウェアへの変換を行うためにＶＨＤＬ言語などの既存の業界標準のソリューションを使用することができる。
【０１０１】
本発明は、好ましくは拡張カードなど、オブジェクトを探知する専用のハードウェアモジュールの形で実装されてもよい。この専用のハードウェアモジュールは完全なビームトレーシングあるいはサウンドレンダリングモジュールを作成するために他のモジュールと接続されてもよい。
【０１０２】
そのような拡張カードのプロセッサは、ベクトル命令を利用して独立した一連のビームトライアングル交差テストを並行に処理されるマルチスレッドの論理ユニットを構成する。
【０１０３】
また、そのようなプロセッサは、ベクトル命令を利用して独立した一連のレイ・トライアングル交差テストを並行に処理するマルチスレッドの論理ユニットを構成する。                     
【０１０４】
拡張カードはアイドル状態の論理ユニットに一連のテストを割り当てる専用のディスパッチャ回路も構成する。
【０１０５】
拡張カードは、更にシーンモデルを保存する階層モデルを有するメモリを構成する。階層モデルメモリは、バスを介してプロセッサに接続されている。読み取り書き込みバッファは正規化された方向ベクトルの形で光線を構成してもよい。
【０１０６】
シーンツリーは、初期化の段階で階層モデルメモリにロードされる。拡張カードを使用するソフトウェアは、見えるオブジェクトが見つけられなければ成らない一連のビームをカードに送る。それに応じて、ソフトウェアはビームが分割された異なる光線と交差する三角形を受け取る。このような拡張カードはＳｙｓｔｅｍ  ｏｎ  Ｃｈｉｐ（ＳｏＣ）技術に実装され、ビデオゲーム機あるいはコンピュータ及び他のマルチメディア及び波動現象シミュレーション用の専用のハードウェアであってもよい。
【０１０７】
ハードウェア実装は効率を上げるため、パフォーマンスが常に優先されるゲームの環境において有利である。
【０１０８】
説明されたアルゴリズムは音の伝播をシミュレートするビームトレーシングのアプリケーション及びビームトレーシングが使用される他のアプリケーションの処理を大幅にスピードアップする。ビーム処理及び光線処理のハイブリッドの組み合わせを使用することで適応フラスタムアルゴリズムの欠点が除去される。ビームを制限するオブジェクトを探知する結果的な方法は実装するのがより簡単で、ビームを合流するより効率の良いアルゴリズムの使用を可能にする。効率性においてかなりの改良があった一方でそれと同時に出力ビームの数が減った。
【０１０９】
適応フラスタムトレーシング(Adaptive Frustum Tracing)及びユニフォームフラスタムトレーシング(Uniform Frustum Tracing)が混合され両方が適当に応用されたものである。１つ目のアルゴリズムは範囲外の三角形を早い破棄を可能にし、他のものは単純なテストを使用する。この解決法は複雑な破棄テストの実行を可能にし、光線に一連の簡単なテストとして実行される。
【０１１０】
当該方法は、マルチパス構造のため、最初にシーンツリーからビームと交差するセルを抽出し、続いてそれらのセルから所定の時間実行される破棄及びビーム分割アルゴリズムにパスされ、最後に部分ビームは光線と近似され、残った三角形はそれらの光線の交差される。必要がある場合、例えばセルをシーンツリーから抽出してそれらから三角形を得るなど、その後の段階は組み合わされても良い。
【０１１１】
本発明の異なる実施例は、ソース・エミッタビームから全方向に放射する代わりに予め決められた数の光線を放射し、完全な三角形から反射を実行する（それぞれの三角形につき一回）：
最初に、光線が全方向に放射され、それらが交差する三角形が見つけられ、
次に、それらの全ての三角形に反射ビームが生成され、続いて通常の処理が行われる。
【０１１２】
当業者であれば、上記のサウンドトレーシングの方法は１つ以上のコンピュータプログラムにより実行及び／又は制御されることが可能であることは簡単に認識できる。そのようなコンピュータプログラムは、通常、パーソナルコンピュータ、パーソナルデジタルアシスタント、携帯電話、デジタルテレビのレシーバー及びデコーダーあるいは同様のものなどのコンピューティング装置におけるコンピューティングリソースを利用することで実行される。アプリケーションは固定媒体に保存される。固定媒体の例は、例えば、ＲＡＭなどのフラッシュメモリあるいは揮発性メモリなどの不発揮性メモリである。コンピュータの指示はプロセッサにより実行される。これらのメモリは本文において開示される技術的概念に係るコンピュータ実行方法の全てのステップを実行するコンピュータ実行可能な指示を構成するコンピュータプログラムを保存する例示的記録媒体である。
【０１１３】
上述の発明は、特定の好ましい実施例に関して記載、説明及び定義されたが、本明細書における実施の参考及び例は、本発明を制限するものではない。当該技術的概念のより幅広い範囲から逸脱しないように多様な修正及び変更を行うことが可能なことは明らかである。上記の好ましい実施例は、単に例示的なものであり、上記の技術的概念の範囲を完全に示すものではない。
【０１１４】
当業者であれば、上記のビーム及び特にサウンドトレーシングトレーシングの方法は、光波、電波及び衝撃波などの他の物理的な波動現象をシミュレートするために実行されてもよいことは簡単に認識される。その結果、本方法はサウンドトレーサー以外のマルチメディア及びシミュレーションシステムにおいて使用できる。
【０１１５】
従って、保護される範囲は、本明細書において説明される好ましい実施例に限られるものではないが、以下のクレームによってのみ限定される。
【図１】
2015108703.tif 000006
【図２】
2015108703.tif 000007
【図３】
2015108703.tif 000008
【図４Ａ】
2015108703.tif 000009
【図４Ｂ】
2015108703.tif 000010
【図４Ｃ】
2015108703.tif 000011
【図４Ｄ】
2015108703.tif 000012
【図４Ｅ】
2015108703.tif 000013
【図４Ｆ】
2015108703.tif 000014
【図４Ｇ】
2015108703.tif 000015
【図４Ｈ】
2015108703.tif 000016
【図４Ｉ】
2015108703.tif 000017
【図５】
2015108703.tif 000018
【外国語明細書】
2015108703000001.pdf