物体衝突処理方法および物体衝突処理プログラム、物体衝突処理装置
【課題】仮想物体の衝突処理の複数のプロセッサによる並列処理を効率化する。
【解決手段】並列化許否管理部２１０は、他のプロセッサの並列化許否管理部と協働して、部分空間の組合せごとに並列化の許否を管理する。具体的には、いずれかの仮想物体が第１および第２の部分空間の境界をまたいで存在するとき、第１の部分空間における仮想物体の衝突処理の任意のプロセッサによる実行と、第２の部分空間における仮想物体の衝突処理の他のプロセッサによる実行との並列化を禁止する。
【解決手段】並列化許否管理部２１０は、他のプロセッサの並列化許否管理部と協働して、部分空間の組合せごとに並列化の許否を管理する。具体的には、いずれかの仮想物体が第１および第２の部分空間の境界をまたいで存在するとき、第１の部分空間における仮想物体の衝突処理の任意のプロセッサによる実行と、第２の部分空間における仮想物体の衝突処理の他のプロセッサによる実行との並列化を禁止する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、仮想物体間の衝突を処理する技術に関する。
【背景技術】
【０００２】
例えばゲーム装置において、３Ｄ仮想物体の運動や挙動は、物理エンジンによって管理される。物理エンジンにおいては、仮想物体の衝突が起こったときに反発力を与える処理が欠かせない。反発力を与える処理は、仮想物体の速度の更新を伴う。一方、物理エンジンにおける処理は、高速化のため、複数のプロセッサによって並列化されることがある。いま、仮想物体Ａと仮想物体Ｂが衝突していて、かつ、仮想物体Ｂと仮想物体Ｃが衝突している場面を考える。この場面において、あるプロセッサが仮想物体Ａと仮想物体Ｂの衝突処理に伴って仮想物体Ｂの速度を更新し、これと同時に、他のプロセッサが仮想物体Ｂと仮想物体Ｃの衝突処理の伴って仮想物体Ｂの速度を更新したとする。そうすると、あるプロセッサによる仮想物体Ｂの速度の更新と、他のプロセッサによる仮想物体Ｂの速度の更新とが競合し、仮想物体Ｂの速度に不整合なデータが書き込まれる可能性がある。通常このような競合を回避するために、例えばセマフォ等を利用した排他制御が行われる。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
競合回避の観点において排他制御は一定の成果を上げているといえる。しかし、物理エンジンの管理する仮想物体の数が多いとき、個々の仮想物体について排他制御のための処理を実行するには相当な計算量が必要となり、並列処理による高速化の効果が十分に発揮されない事態も起こりうる。このような事態は、特に物理エンジンによる衝突処理のようなリアルタイム処理において大きな問題となる。
【０００４】
本発明はこうした状況を認識してなされたものであり、その目的は、仮想物体の衝突処理の複数のプロセッサによる並列処理を効率化することにある。
【課題を解決するための手段】
【０００５】
本発明のある態様の物体衝突処理方法は、複数の仮想物体が存在する仮想空間を複数の部分空間へ分割するステップと、いずれかの仮想物体が第１および第２の部分空間の境界をまたいで存在するとき、第１の部分空間における仮想物体の衝突処理の任意のプロセッサによる実行と、第２の部分空間における仮想物体の衝突処理の他のプロセッサによる実行との並列化を禁止するステップと、複数のプロセッサのそれぞれが複数の部分空間のいずれかにおける仮想物体の衝突処理を担当することにより、仮想物体の衝突処理を、部分空間を単位として並列化して実行するステップとを備える。
【０００６】
この態様によると、部分空間を単位として並列化の禁止が定められるため、個々の仮想物体については排他制御のための処理をする必要がない。このため、排他制御のための処理の計算量が減じられる。
【０００７】
本発明の別の態様の物体衝突処理方法は、複数の仮想物体を所定の規則で複数のグループへ分割するステップと、衝突している仮想物体ペアの一方が第１のグループに属し、他方が第２のグループに属するとき、この仮想物体ペアの衝突処理の任意のプロセッサによる実行と、第１もしくは第２のグループに属する仮想物体が関係する他の仮想物体ペアの衝突処理の他のプロセッサによる実行との並列化を禁止するステップと、複数のプロセッサのそれぞれがいずれかの仮想物体ペアの衝突処理を担当することにより、仮想物体の衝突処理を並列化して実行するステップとを備える。
【０００８】
この態様によると、衝突している仮想物体ペアの一方もしくは他方の所属グループによって並列化の禁止が定められるため、個々の仮想物体については排他制御のための処理をする必要がない。このため、排他制御のための処理の計算量が減じられる。
【０００９】
なお、本発明の表現を、装置あるいはシステム、コンピュータプログラム、記録媒体などの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１０】
本発明によれば、仮想物体の衝突処理の複数のプロセッサによる並列処理を効率化することができる。
【発明を実施するための最良の形態】
【００１１】
以下、図面を参照しながら本発明の好適な実施の形態を詳述する。なお、各図面に示される同一または同等の構成要素、部材、処理には、同一の符号を付し、適宜重複した説明は省略する。また、実施の形態は発明を限定するものではなく例示であり、実施の形態に記述されるすべての特徴やその組み合わせは必ずしも発明の本質的なものであるとは限らない。
【００１２】
（第１の実施の形態）
本実施の形態は、複数のプロセッサにより仮想物体の衝突処理を並列化して実行するものであり、その特徴の１つは、個々の仮想物体についての排他制御のための処理を不要とする工夫にある。
【００１３】
図１は、第１の実施の形態に係る物体衝突処理装置１００の例示的なハードウェア構成図である。ここに示される構成は、例えば、ゲーム装置などのコンピュータの物理エンジンとしての役割を担う。
物体衝突処理装置１００は、第１プロセッサ１１１と、第２プロセッサ１２２と、第３プロセッサ１３３と、メインメモリ１５０と、それらを接続するバス１８０とを備える。メインメモリ１５０は、本発明の「メモリ領域」の例示であり、第１プロセッサ１１１ないし第３プロセッサ１３３に共有とされる。第１プロセッサ１１１ないし第３プロセッサ１３３は、本発明における「複数のプロセッサ」の例示であり、命令をフェッチ、デコード、実行するなど、通常のプロセッサとしての機能を有する。
【００１４】
図２は、図１に示されるメインメモリ１５０の記憶領域のブロック図である。メインメモリ１５０は、空間情報バッファ１５２と、共有テーブル１５４とを有する。共有テーブル１５４は、並列化許否管理テーブル１５６と、動的管理テーブル１５８とを含む。
空間情報バッファ１５２は、ある時点における仮想空間の情報を記憶する。この情報には仮想物体の位置や速度なども含まれる。共有テーブル１５４は、本発明の「テーブル」の例示であり、衝突処理の並列化を管理するために設けられる。並列化許否管理テーブル１５６は、部分空間の組合せごとに並列化の許否を記憶するために設けられ、動的管理テーブル１５８は、現在なされている衝突処理と並列化が許可されている衝突処理を特定するために設けられる。これらテーブルの具体的な記憶内容については後述する。
【００１５】
図３は、図１に示される第１プロセッサ１１１の機能ブロック図である。この図に示される各ブロックは、第１プロセッサ１１１が物体衝突処理プログラムをメインメモリ１５０にロードして実行することにより実現される。あるいは、第１プロセッサ１１１がローカルメモリを内部に有する場合、図３に示される各ブロックは、第１プロセッサ１１１が物体衝突処理プログラムを当該ローカルメモリにロードして実行することにより実現されてもよい。なお、第２プロセッサ１２２および第３プロセッサ１３３（以下「他のプロセッサ」とも表記）も第１プロセッサ１１１と同様の機能を実現する。
【００１６】
第１プロセッサ１１１は、空間情報更新部２０２と、空間分割部２０６と、並列化許否管理部２１０と、衝突判定部２１４と、担当空間決定部２１８と、衝突処理部２２６とを備える。
空間情報更新部２０２は、他のプロセッサの空間情報更新部（図示せず）と協働して、空間情報バッファ１５２の記憶内容を更新する。すなわち、仮想空間における仮想物体の位置および速度を時間ステップで進める。この処理は、例えば外部のＰＩＴ（Programmable Interrupt Timer）からの信号を契機として行われる。時間ステップの幅は、特に限定されないが、想定される仮想物体の速度の最大値に応じて決められてもよい。なお、ＰＩＴは第１プロセッサ１１１に内蔵されてもよい。
【００１７】
空間分割部２０６は、他のプロセッサの空間分割部（図示せず）と協働して、複数の仮想物体が存在する仮想空間を複数の部分空間へ分割する。
図４は、第１の実施の形態における空間分割を例示する。この例では、８つの仮想物体が存在する仮想空間が６つの部分空間に分割される。以下、必要に応じて部分空間を「セル」と表記するとともに、６つの部分空間のそれぞれを、「セル０」ないし「セル５」と表記して区別する。なお、部分空間の数や形状、大きさは図４に限定されず、種々の変更が可能である。図３に戻り、並列化許否管理部２１０は、他のプロセッサの並列化許否管理部（図示せず）と協働して、部分空間の組合せごとに並列化の許否を管理する。これは、図２に示される並列化許否管理テーブル１５６を更新することによって行われる。以下、具体例を示す。
【００１８】
図５は、図２に示される並列化許否管理テーブル１５６の記憶内容を例示する。この例は、複数の部分空間と複数の仮想物体との位置関係が図４に示される状態にある場合に基づく。この場合、１つの仮想物体がセル０およびセル１の境界をまたいで存在するので、セル０とセル１の組合せに対応するアドレスには「１」が書き込まれる。いずれかのプロセッサの並列化許否管理部が書込みを実行する。「１」を書き込むことは禁止フラグを立てることに相当し、これにより、セル０における仮想物体の衝突処理の任意のプロセッサによる実行と、セル１における仮想物体の衝突処理の他のプロセッサによる実行との並列化が禁止される。上記と同様に、セル１とセル４、セル３とセル４、セル４とセル５の組合せに対応するアドレスにも「１」が書き込まれ、並列化が禁止される。このように禁止することにより、境界をまたぐ仮想物体の速度を複数のプロセッサが同時に更新することによるデータの不整合が防止される。
【００１９】
一方、図４に示される状態ではいずれの仮想物体もセル０とセル３の境界をまたいで存在しないので、セル０とセル３の組合せに対応するアドレスには「０」が書き込まれる。いずれかのプロセッサの並列化許否管理部が書込みを実行する。「０」を書き込むことは許可フラグを立てることに相当し、これにより、セル０における仮想物体の衝突処理の任意のプロセッサによる実行と、セル３における仮想物体の衝突処理の他のプロセッサによる実行との並列化が許可される。上記と同様に、境界をまたぐ仮想物体のないセルの組合せに対応するアドレスには「０」が書き込まれ、並列化が許可される。このように許可することにより、並列処理の効率化に資する。
【００２０】
仮想物体の数が多いとき、個々の仮想物体について排他制御のための処理を実行すると、その計算量は相当なものとなり、並列処理の非効率化およびコスト高を招く傾向にある。一方、部分空間を単位として並列化の許否を判定できれば、このような問題は軽減される。本発明者のこうした知見が本実施の形態の基礎となっている。
【００２１】
図３に戻り、衝突判定部２１４は、いずれかのセルにおける仮想物体の衝突の有無を判定する。第２プロセッサ１２２および第３プロセッサ１３３のそれぞれによって実現される衝突判定部（図示せず）も同様にいずれかのセルにおける仮想物体の衝突の有無を判定する。こうして仮想物体の衝突の有無が部分空間を単位として並列化して判定される。全てのセルについて衝突判定が終了し、いずれかのセルにおいて衝突ありと判定されると、次に衝突処理がなされる。なお、衝突処理は、仮想物体の衝突の前後で仮想物体の属性を示すパラメータを更新する処理を含む。属性とは速度や形状、色、音、重さ、粘性などの物理的な状態や性質をいうが、必ずしも物理法則に従う必要はない。衝突している仮想物体に衝突による例えば反発力を与える処理は、衝突処理に含まれる。その他、衝突による合体や消滅、形状の変化などを実現することもまた衝突処理に含まれる。なお、衝突処理は、物理法則に従うものであってもよいし、ゲームのルールのようなあらかじめ定められた定義に従うものであってもよい。
【００２２】
担当空間決定部２１８は、衝突処理部２２６が複数の部分空間のいずれにおける仮想物体の衝突処理を担当すべきかを、図２に示される動的管理テーブル１５８を参照して決定する。第２プロセッサ１２２および第３プロセッサ１３３のそれぞれによって実現される担当空間決定部（図示せず）も同様に、自己のプロセッサの衝突処理部が複数の部分空間のいずれにおける仮想物体の衝突処理を担当すべきかを決定する。動的管理テーブル１５８は、並列化許否管理部２１０の情報すなわち並列化許否管理テーブル１５６の記憶内容と、現在の衝突処理の状況とに基づいて記憶内容が定められる。以下、具体例を示す。
【００２３】
図６は、図２に示される動的管理テーブル１５８のある時点における記憶内容を例示する。図５と同様にこの例も、複数の部分空間と複数の仮想物体との位置関係が図４に示される状態にある場合に基づく。動的管理テーブル１５８は、大きく分けて以下の情報を記憶し、それらの情報は、現在の衝突処理の状況を反映するよう各プロセッサの担当空間決定部によって更新される。
・第１プロセッサ１１１ないし第３プロセッサ１３３のそれぞれによって現在衝突処理がなされているセルと、他のセルのそれぞれとの並列化の許否（「０」：許可、「１」：禁止）
・現在衝突処理がなされているセルおよび既に処理が完了したセルと、まだ処理が開始されていないセルとの区別（「０」：処理未開始、「１」：処理中もしくは処理済）
・上記データをセルごとに論理和演算した結果（「０」：処理可能、「１」：処理不可能）
【００２４】
論理和演算結果が「０」となるセルは、現在衝突処理がなされているセルとの並列化が禁止されてなく、かつ、まだ処理が開始されていないセルである。一方、論理和演算結果が「１」となるセルは、現在衝突処理がなされているセルとの並列化が禁止されている、あるいは、現在処理中もしくは既に処理済のセルである。
【００２５】
図６に示される記憶内容は下記の状況を反映している。
・第１プロセッサ１１１は仮想物体の衝突処理を実行していない。
・第２プロセッサ１２２はセル２における仮想物体の衝突処理を実行している。
・第３プロセッサ１３３はセル１における仮想物体の衝突処理を実行している。
・セル０ないしセル５における仮想物体の衝突処理はいずれも完了していない。
【００２６】
図６の４行目のデータを見ると、第３プロセッサ１３３が現在セル１における仮想物体の衝突処理を実行中で、この衝突処理と並列化が可能なのは、セル１ないしセル３、セル５である。このデータは、図５の３行目のものをコピーすればよい。なお、現在セル１における仮想物体の衝突処理がなされているのもかかわらず図６の４行目を見る限りはセル１の並列化は禁止されていないが、５行目のデータによってセル１の並列化は禁止される。図６の５行目を見ると、セル１およびセル２が衝突処理が現在実行中あるいは既に完了している。同６行目を見ると、上記の状況で衝突処理を実行可能なセルはセル３あるいはセル５である。したがって、衝突処理を現在実行していない第１プロセッサ１１１にはセル３あるいはセル５における仮想物体の衝突処理を割り当てることが可能である。
【００２７】
図３に戻り、担当空間決定部２１８は、動的管理テーブル１５８の例えば図６に示される記憶内容に基づいて、衝突処理部２２６にセル３あるいはセル５における仮想物体の衝突処理を割り当てる。例えばセル３における仮想物体の衝突処理を割り当てた場合、担当空間決定部２１８は、図６の２行目に図５の５行目のデータをコピーするとともに、図６の５行目のセル３のところに処理中フラグの意味で「１」を書き込む。
【００２８】
衝突処理部２２６は、担当空間決定部２１８から割り当てられたセルにおける衝突処理を実行する。本実施の形態では分散メモリ型、すなわち、各プロセッサが内部にローカルメモリ（図示せず）を有している場合を想定する。このため、衝突処理部２２６は、割り当てられたセルに存在する仮想物体の例えば速度データを空間情報バッファ１５２から第１プロセッサ１１１内のメモリに読み出し、衝突による反発力を与える計算をし、結果を空間情報バッファ１５２に書き戻す。第２プロセッサ１２２および第３プロセッサ１３３のそれぞれによって実現される衝突処理部（図示せず）も同様に、自己の担当空間決定部から割り当てられたセルにおける仮想物体の衝突処理を実行する。こうして仮想物体の衝突処理が部分空間を単位として並列化して実行される。なお、衝突処理部２２６は、割り当てられたセルにおける仮想物体の衝突処理が完了した際には、図６の２行目のデータをクリアして「０」にし、次の割当てを待つ。
【００２９】
図７は、図３に示される第１プロセッサ１１１の動作のフローチャートである。以下、図３も参照しながら説明する。
まず、時間を示すパラメータｔが０に初期化される（Ｓ５０２）。空間分割部２０６は、他のプロセッサの空間分割部と協働して、複数の仮想物体が存在する仮想空間を複数の部分空間へ分割する（Ｓ５０４）。並列化許否管理部２１０は、他のプロセッサの並列化許否管理部と協働して、図２に示される並列化許否管理テーブル１５６を更新する（Ｓ５０６）。衝突判定部２１４は、いずれかの部分空間における仮想物体の衝突の有無を判定する（Ｓ５０８）。衝突がなければ（Ｓ５１２のＮｏ）、終了判定（Ｓ５１４のＮｏ）の後、空間情報更新部２０２は仮想物体の位置、速度をΔｔだけ進める（Ｓ５１８）。その後、空間分割（Ｓ５０４）から衝突判定（Ｓ５０８）までが再度実行される。なお、例えばユーザにより中断が指示された場合などは、終了判定の後、衝突処理が終了される（Ｓ５１４のＹｅｓ）。
【００３０】
衝突があった場合（Ｓ５１２のＹｅｓ）、担当空間決定部２１８は、図２に示される動的管理テーブル１５８を参照することにより衝突処理部２２６がいずれの部分空間における衝突処理を担当すべきかを決定するとともに、決定に基づいて動的管理テーブル１５８を更新する（Ｓ５２２）。衝突処理部２２６は、担当空間決定部２１８により担当すべきと決定された部分空間における衝突処理を実行し、処理が終了すると、動的管理テーブル１５８を更新する（Ｓ５２６）。その後、まだ衝突処理が開始されていない部分空間（以下、「未処理空間」）があれば（Ｓ５３２のＹｅｓ）、担当空間の決定（Ｓ５２２）と衝突処理（Ｓ５２６）が再度実行される。未処理空間がなくなると（Ｓ５３２のＮｏ）、終了判定（Ｓ５１４のＮｏ）の後、空間情報更新部２０２は仮想物体の位置、速度をΔｔだけ進める（Ｓ５１８）。その後、空間分割（Ｓ５０４）から衝突処理（Ｓ５２６）までの一連の処理が再度実行される。
【００３１】
本実施の形態によれば、並列化許否管理部２１０は部分空間を単位として並列化の許否を並列化許否管理テーブル１５６に記憶し、担当空間決定部２１８はこれに従って衝突処理部２２６が担当すべき部分空間を決定する。これにより、衝突処理部２２６は個々の仮想物体について排他制御のための処理を行うことから解放され、結果として並列処理の効率化およびコスト安に資する。
【００３２】
また、動的管理テーブル１５８は各プロセッサの担当空間決定部および衝突処理部によって更新され、各プロセッサの担当空間決定部は動的管理テーブル１５８を参照することによって自己のプロセッサの衝突処理部に現在衝突処理が可能な部分空間を担当させる。したがって、並列処理の集中管理のために別途プロセッサを設ける必要がない。これは物体衝突処理装置１００のハードウェア構成の単純化に有利である。
【００３３】
また、各プロセッサの担当空間決定部および衝突処理部は現在の衝突処理の状況を反映するよう動的管理テーブル１５８を更新し、各プロセッサの担当空間決定部は最新の状態に基づいて自己のプロセッサの衝突処理部にいずれかの部分空間における衝突処理を割り当てる。このような動的管理により並列化の斑を最小限に抑えられるため、並列処理の効率がよい。
【００３４】
さらに、空間分割部２０６による空間分割によって得られた複数の部分空間を衝突判定に利用するとともに衝突処理並列化の単位としても利用するため、並列化許否のために格別計算量が増えることもない。
【００３５】
（第２の実施の形態）
本実施の形態では、第１の実施の形態とは異なる工夫によって個々の仮想物体についての排他制御のための処理を不要とする。第２の実施の形態にかかる物体衝突処理装置のハードウェア構成は、図１に示されるものと同様である。
【００３６】
以下、第１の実施の形態と異なる部分を中心に本実施の形態を説明する。
図８は、第２の実施の形態におけるメインメモリ１５０の記憶領域のブロック図である。この図において図２と異なるところは、共有テーブル１５４にペア振分けテーブル１５５が設けられた点である。ペア振分けテーブル１５５の記憶内容については後述する。
【００３７】
図９は、第２の実施の形態における第１プロセッサ１１１の機能ブロック図である。この図において図３と異なるところは、グループ分割部３０６が設けられた点および担当空間決定部２１８が担当ペア決定部３１８に変わった点である。なお、第２プロセッサ１２２および第３プロセッサ１３３も第１プロセッサ１１１と同様の機能を実現する。
【００３８】
本実施の形態では、複数の仮想物体のそれぞれはあらかじめ番号が付される。グループ分割部３０６は、その番号に基づいて複数の仮想物体を複数のグループに分割する。グループ分割部３０６は一例として、０〜９９の番号が付された仮想物体をグループＧ０、１００〜１９９の番号が付された仮想物体をグループＧ１、・・・、５００〜５９９の番号が付された仮想物体をグループＧ５に所属させる。なお、仮想物体に付された番号は本発明の「識別情報」の例示である。識別情報は、複数の仮想物体のそれぞれを特定しうるものであればよい。
【００３９】
衝突判定部２１４は、第１の実施の形態と同様に衝突判定をするとともに、本実施の形態では、衝突している仮想物体ペアが見つかるつど仮想物体ペアの所属グループに基づいて仮想物体ペアを振り分ける。これは、図８に示されるペア振分けテーブル１５５を更新することによってなされる。以下、具体例を示す。
【００４０】
図１０は、ある時点における仮想物体の衝突状態を例示する。以下、ｎの番号が付された仮想物体を「仮想物体ｎ」と表記する。図１１は、図１０の状態においてペア振分けテーブル１５５に記憶される内容を例示する。この記憶内容は、図９の衝突判定部２１４が図１０の状態において衝突判定し、衝突している仮想物体ペアを振り分けたものである。
【００４１】
以下、仮想物体ｍと仮想物体ｎが衝突しているとき、この仮想物体ペアを「仮想物体ペアｍ−ｎ」と表記する。仮想物体ペア１−４６は、一方および他方がグループＧ０に属するので、グループＧ０とグループＧ０の組合せに分類される。仮想物体ペア４６−５８も同様にグループＧ０とグループＧ０の組合せに分類される。仮想物体ペア５８−２５８は、一方がグループＧ０に属し他方がグループＧ２に属するので、グループＧ０とグループＧ２の組合せに分類される。他の仮想物体ペアも同様にいずれかのグループの組合せに分類される。以下、仮想物体ペアが分類されているグループの組合せを必要に応じて「セル」と表記し、仮想物体ペアが分類されている図１１中の６つのグループの組合せのそれぞれを「セル０」ないし「セル５」と表記して区別する。図９に戻り、並列化許否管理部２１０は、他のプロセッサの並列化許否管理部（図示せず）と協働して、セルの組合せごとに並列化の許否を管理する。これは、図８に示される並列化許否管理テーブル１５６を更新することによって行われる。以下、具体例を示す。
【００４２】
図１２は、図８に示される並列化許否管理テーブル１５６の記憶内容を例示する。この例は、衝突している仮想物体ペアが図１１に示されるように各セルに分類された場合に基づく。この場合、セル０とセル１は共にグループＧ０を含む、すなわちセル０とセル１は共通のグループを含むので、セル０とセル１の組合せに対応するアドレスには「１」が書き込まれる。いずれかのプロセッサの並列化許否管理部が書込みを実行する。「１」を書き込むことは禁止フラグを立てることに相当し、これにより、セル０に分類された仮想物体ペアの衝突処理の任意のプロセッサによる実行と、セル１に分類された仮想物体ペアの衝突処理の他のプロセッサによる実行との並列化が禁止される。上記と同様に、セル１とセル２、セル１とセル３、セル２とセル３、セル２とセル４、セル３とセル５、セル４とセル５の組合せに対応するアドレスにも「１」が書き込まれ、並列化が禁止される。このように禁止することにより、２つのセルに共通のグループに所属する１つの仮想物体の速度を複数のプロセッサが同時に更新することによるデータの不整合が防止される。
【００４３】
一方、セル０とセル２は共通のグループを含まないので、セル０とセル２の組合せに対応するアドレスには「０」が書き込まれる。いずれかのプロセッサの並列化許否管理部が書込みを実行する。「０」を書き込むことは許可フラグを立てることに相当し、これにより、セル０に分類された仮想物体ペアの衝突処理の任意のプロセッサによる実行と、セル２に分類された仮想物体ペアの衝突処理の他のプロセッサによる実行との並列化が許可される。上記と同様に、共通のグループを含まないセルの組合せに対応するアドレスには「０」が書き込まれ、並列化が許可される。このように許可することにより、並列処理の効率化に資する。
【００４４】
前述の第１の実施の形態では部分空間を単位として並列化の許否を判定したが、本実施の形態ではこのように仮想物体ペアの所属グループの組合せを単位として並列化の許否を判定する。この場合も、並列処理の非効率化およびコスト高の問題が軽減される。なお、仮想物体ペアの分類されていないグループの組合せも「セル」として並列化許否管理の対象としてもよい。
【００４５】
図９に戻り、担当ペア決定部３１８は、衝突処理部２２６がいずれのセルに分類された仮想物体ペアの衝突処理を担当すべきかを、図８に示される動的管理テーブル１５８を参照して決定する。第２プロセッサ１２２および第３プロセッサ１３３のそれぞれによって実現される担当ペア決定部（図示せず）も同様に、自己のプロセッサの衝突処理部がいずれのセルに分類された仮想物体ペアの衝突処理を担当すべきかを決定する。動的管理テーブル１５８は、第１の実施の形態と同様、並列化許否管理部２１０の情報すなわち並列化許否管理テーブル１５６の記憶内容と、現在の衝突処理の状況とに基づいて記憶内容が定められる。
【００４６】
衝突処理部２２６は、担当ペア決定部３１８から割り当てられたセルに分類されている仮想物体ペアの衝突処理を実行する。第２プロセッサ１２２および第３プロセッサ１３３のそれぞれによって実現される衝突処理部（図示せず）も同様に、自己の担当ペア決定部から割り当てられたセルに分類されている仮想物体の衝突処理を実行する。こうして仮想物体の衝突処理が並列化して実行される。
【００４７】
図１３は、図９に示される第１プロセッサ１１１の動作のフローチャートである。以下、図９も参照しながら説明する。
まず、時間を示すパラメータｔが０に初期化される（Ｓ６０２）。グループ分割部３０６は、各仮想物体に付された番号に基づいて複数の仮想物体を複数のグループに分割する（Ｓ６０３）。空間分割部２０６は、他のプロセッサの空間分割部と協働して、複数の仮想物体が存在する仮想空間を複数の部分空間へ分割する（Ｓ６０４）。衝突判定部２１４は、いずれかの部分空間における仮想物体の衝突の有無を判定し、衝突している仮想物体ペアが見つかるつど仮想物体ペアの所属グループに基づいて仮想物体ペアを振り分ける（Ｓ６０８）。衝突がなければ（Ｓ６１２のＮｏ）、終了判定（Ｓ６１４のＮｏ）の後、空間情報更新部２０２は仮想物体の位置、速度をΔｔだけ進める（Ｓ６１８）。その後、グループ分け（Ｓ６０３）から衝突判定（Ｓ６０８）までが再度実行される。なお、例えばユーザにより中断が指示された場合などは、終了判定の後、衝突処理が終了される（Ｓ６１４のＹｅｓ）。
【００４８】
衝突があった場合（Ｓ６１２のＹｅｓ）、並列化許否管理部２１０は、他のプロセッサの並列化許否管理部と協働して、図８に示される並列化許否管理テーブル１５６を更新する（Ｓ６２１）。担当ペア決定部３１８は、図８に示される動的管理テーブル１５８を参照することにより衝突処理部２２６がいずれのセルに分類された仮想物体ペアの衝突処理を担当すべきかを決定するとともに、決定に基づいて動的管理テーブル１５８を更新する（Ｓ６２２）。衝突処理部２２６は、担当ペア決定部３１８により担当すべきと決定された仮想物体ペアの衝突処理を実行し、処理が終了すると、動的管理テーブル１５８を更新する（Ｓ６２６）。その後、まだ衝突処理が開始されていないセル（以下、「未処理セル」）があれば（Ｓ６３２のＹｅｓ）、担当ペアの決定（Ｓ６２２）と衝突処理（Ｓ６２６）が再度実行される。未処理セルがなくなると（Ｓ６３２のＮｏ）、終了判定（Ｓ６１４のＮｏ）の後、空間情報更新部２０２は仮想物体の位置、速度をΔｔだけ進める（Ｓ６１８）。その後、グループ分け（Ｓ６０３）から衝突処理（Ｓ６２６）までの一連の処理が再度実行される。
【００４９】
本実施の形態によれば、並列化許否管理部２１０は仮想物体ペアの所属グループの組合せを単位として並列化の許否を並列化許否管理テーブル１５６に記憶し、担当ペア決定部３１８はこれに従って衝突処理部２２６が担当すべき仮想物体ペアを決定する。これにより、第１の実施の形態と同様に、衝突処理部２２６は個々の仮想物体について排他制御のための処理を行うことから解放され、結果として並列処理の効率化およびコスト安に資する。その他、物体衝突処理装置１００のハードウェア構成の単純化に有利であることおよび並列化の斑を最小限に抑えられるため並列処理の効率が良いこと等、第１の実施の形態と同様の効果を奏する。
【００５０】
上記実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。以下、変形例を列挙する。
【００５１】
実施の形態においては第１プロセッサ１１１ないし第３プロセッサ１３３は同様の機能を実現するとしたが、これには限定されず、衝突処理部以外の機能は第１プロセッサ１１１だけが有していても良い。この場合、第１プロセッサ１１１が他のプロセッサへの衝突処理の割当てを担当する。本変形例も、個々の仮想物体について排他制御のための処理を行う必要がないという点で実施の形態と同様に並列処理の効率化およびコスト安に資する。
【００５２】
また、第１プロセッサ１１１ないし第３プロセッサ１３３とは別に、これらプロセッサを制御する制御プロセッサを別に設けてもよく、並列化許否管理テーブル１５６や動的管理テーブル１５８の更新、あるいは各プロセッサへの衝突処理の割当てを制御プロセッサにより行ってもよい。本変形例も、個々の仮想物体について排他制御のための処理を行う必要がないという点で実施の形態と同様に並列処理の効率化およびコスト安に資する。
【００５３】
実施の形態では各プロセッサが内部にローカルメモリを有する分散メモリ型を説明したが、これには限定されず、共有メモリ型であってもよい。
【００５４】
第２の実施の形態においては仮想物体ペアの所属グループの組合せを単位として並列化の許否を決めるので、空間分割をしないことも考えられる。
【図面の簡単な説明】
【００５５】
【図１】第１の実施の形態に係る物体衝突処理装置の例示的なハードウェア構成図である。
【図２】図１に示されるメインメモリの記憶領域のブロック図である。
【図３】図１に示される第１プロセッサの機能ブロック図である。
【図４】第１の実施の形態における空間分割を例示する図である。
【図５】図２に示される並列化許否管理テーブルの記憶内容を例示する図である。
【図６】図２に示される動的管理テーブルのある時点における記憶内容を例示する図である。
【図７】図３に示される第１プロセッサの動作のフローチャートである。
【図８】第２の実施の形態におけるメインメモリの記憶領域のブロック図である。
【図９】第２の実施の形態における第１プロセッサの機能ブロック図である。
【図１０】ある時点における仮想物体の衝突状態を例示する図である。
【図１１】図１０の状態においてペア振分けテーブルに記憶される内容を例示する図である。
【図１２】図８に示される並列化許否管理テーブルの記憶内容を例示する図である。
【図１３】図９に示される第１プロセッサの動作のフローチャートである。
【符号の説明】
【００５６】
１００・・・物体衝突処理装置、１１１・・・第１プロセッサ、１２２・・・第２プロセッサ、１３３・・・第３プロセッサ、１５０・・・メインメモリ、１５２・・・空間情報バッファ、１５４・・・共有テーブル、１５５・・・ペア振分けテーブル、１５６・・・並列化許否管理テーブル、１５８・・・動的管理テーブル、１８０・・・バス、２０２・・・空間情報更新部、２０６・・・空間分割部、２１０・・・並列化許否管理部、２１４・・・衝突判定部、２１８・・・担当空間決定部、２２６・・・衝突処理部、３０６・・・グループ分割部、３１８・・・担当ペア決定部。
【技術分野】
【０００１】
本発明は、仮想物体間の衝突を処理する技術に関する。
【背景技術】
【０００２】
例えばゲーム装置において、３Ｄ仮想物体の運動や挙動は、物理エンジンによって管理される。物理エンジンにおいては、仮想物体の衝突が起こったときに反発力を与える処理が欠かせない。反発力を与える処理は、仮想物体の速度の更新を伴う。一方、物理エンジンにおける処理は、高速化のため、複数のプロセッサによって並列化されることがある。いま、仮想物体Ａと仮想物体Ｂが衝突していて、かつ、仮想物体Ｂと仮想物体Ｃが衝突している場面を考える。この場面において、あるプロセッサが仮想物体Ａと仮想物体Ｂの衝突処理に伴って仮想物体Ｂの速度を更新し、これと同時に、他のプロセッサが仮想物体Ｂと仮想物体Ｃの衝突処理の伴って仮想物体Ｂの速度を更新したとする。そうすると、あるプロセッサによる仮想物体Ｂの速度の更新と、他のプロセッサによる仮想物体Ｂの速度の更新とが競合し、仮想物体Ｂの速度に不整合なデータが書き込まれる可能性がある。通常このような競合を回避するために、例えばセマフォ等を利用した排他制御が行われる。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
競合回避の観点において排他制御は一定の成果を上げているといえる。しかし、物理エンジンの管理する仮想物体の数が多いとき、個々の仮想物体について排他制御のための処理を実行するには相当な計算量が必要となり、並列処理による高速化の効果が十分に発揮されない事態も起こりうる。このような事態は、特に物理エンジンによる衝突処理のようなリアルタイム処理において大きな問題となる。
【０００４】
本発明はこうした状況を認識してなされたものであり、その目的は、仮想物体の衝突処理の複数のプロセッサによる並列処理を効率化することにある。
【課題を解決するための手段】
【０００５】
本発明のある態様の物体衝突処理方法は、複数の仮想物体が存在する仮想空間を複数の部分空間へ分割するステップと、いずれかの仮想物体が第１および第２の部分空間の境界をまたいで存在するとき、第１の部分空間における仮想物体の衝突処理の任意のプロセッサによる実行と、第２の部分空間における仮想物体の衝突処理の他のプロセッサによる実行との並列化を禁止するステップと、複数のプロセッサのそれぞれが複数の部分空間のいずれかにおける仮想物体の衝突処理を担当することにより、仮想物体の衝突処理を、部分空間を単位として並列化して実行するステップとを備える。
【０００６】
この態様によると、部分空間を単位として並列化の禁止が定められるため、個々の仮想物体については排他制御のための処理をする必要がない。このため、排他制御のための処理の計算量が減じられる。
【０００７】
本発明の別の態様の物体衝突処理方法は、複数の仮想物体を所定の規則で複数のグループへ分割するステップと、衝突している仮想物体ペアの一方が第１のグループに属し、他方が第２のグループに属するとき、この仮想物体ペアの衝突処理の任意のプロセッサによる実行と、第１もしくは第２のグループに属する仮想物体が関係する他の仮想物体ペアの衝突処理の他のプロセッサによる実行との並列化を禁止するステップと、複数のプロセッサのそれぞれがいずれかの仮想物体ペアの衝突処理を担当することにより、仮想物体の衝突処理を並列化して実行するステップとを備える。
【０００８】
この態様によると、衝突している仮想物体ペアの一方もしくは他方の所属グループによって並列化の禁止が定められるため、個々の仮想物体については排他制御のための処理をする必要がない。このため、排他制御のための処理の計算量が減じられる。
【０００９】
なお、本発明の表現を、装置あるいはシステム、コンピュータプログラム、記録媒体などの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１０】
本発明によれば、仮想物体の衝突処理の複数のプロセッサによる並列処理を効率化することができる。
【発明を実施するための最良の形態】
【００１１】
以下、図面を参照しながら本発明の好適な実施の形態を詳述する。なお、各図面に示される同一または同等の構成要素、部材、処理には、同一の符号を付し、適宜重複した説明は省略する。また、実施の形態は発明を限定するものではなく例示であり、実施の形態に記述されるすべての特徴やその組み合わせは必ずしも発明の本質的なものであるとは限らない。
【００１２】
（第１の実施の形態）
本実施の形態は、複数のプロセッサにより仮想物体の衝突処理を並列化して実行するものであり、その特徴の１つは、個々の仮想物体についての排他制御のための処理を不要とする工夫にある。
【００１３】
図１は、第１の実施の形態に係る物体衝突処理装置１００の例示的なハードウェア構成図である。ここに示される構成は、例えば、ゲーム装置などのコンピュータの物理エンジンとしての役割を担う。
物体衝突処理装置１００は、第１プロセッサ１１１と、第２プロセッサ１２２と、第３プロセッサ１３３と、メインメモリ１５０と、それらを接続するバス１８０とを備える。メインメモリ１５０は、本発明の「メモリ領域」の例示であり、第１プロセッサ１１１ないし第３プロセッサ１３３に共有とされる。第１プロセッサ１１１ないし第３プロセッサ１３３は、本発明における「複数のプロセッサ」の例示であり、命令をフェッチ、デコード、実行するなど、通常のプロセッサとしての機能を有する。
【００１４】
図２は、図１に示されるメインメモリ１５０の記憶領域のブロック図である。メインメモリ１５０は、空間情報バッファ１５２と、共有テーブル１５４とを有する。共有テーブル１５４は、並列化許否管理テーブル１５６と、動的管理テーブル１５８とを含む。
空間情報バッファ１５２は、ある時点における仮想空間の情報を記憶する。この情報には仮想物体の位置や速度なども含まれる。共有テーブル１５４は、本発明の「テーブル」の例示であり、衝突処理の並列化を管理するために設けられる。並列化許否管理テーブル１５６は、部分空間の組合せごとに並列化の許否を記憶するために設けられ、動的管理テーブル１５８は、現在なされている衝突処理と並列化が許可されている衝突処理を特定するために設けられる。これらテーブルの具体的な記憶内容については後述する。
【００１５】
図３は、図１に示される第１プロセッサ１１１の機能ブロック図である。この図に示される各ブロックは、第１プロセッサ１１１が物体衝突処理プログラムをメインメモリ１５０にロードして実行することにより実現される。あるいは、第１プロセッサ１１１がローカルメモリを内部に有する場合、図３に示される各ブロックは、第１プロセッサ１１１が物体衝突処理プログラムを当該ローカルメモリにロードして実行することにより実現されてもよい。なお、第２プロセッサ１２２および第３プロセッサ１３３（以下「他のプロセッサ」とも表記）も第１プロセッサ１１１と同様の機能を実現する。
【００１６】
第１プロセッサ１１１は、空間情報更新部２０２と、空間分割部２０６と、並列化許否管理部２１０と、衝突判定部２１４と、担当空間決定部２１８と、衝突処理部２２６とを備える。
空間情報更新部２０２は、他のプロセッサの空間情報更新部（図示せず）と協働して、空間情報バッファ１５２の記憶内容を更新する。すなわち、仮想空間における仮想物体の位置および速度を時間ステップで進める。この処理は、例えば外部のＰＩＴ（Programmable Interrupt Timer）からの信号を契機として行われる。時間ステップの幅は、特に限定されないが、想定される仮想物体の速度の最大値に応じて決められてもよい。なお、ＰＩＴは第１プロセッサ１１１に内蔵されてもよい。
【００１７】
空間分割部２０６は、他のプロセッサの空間分割部（図示せず）と協働して、複数の仮想物体が存在する仮想空間を複数の部分空間へ分割する。
図４は、第１の実施の形態における空間分割を例示する。この例では、８つの仮想物体が存在する仮想空間が６つの部分空間に分割される。以下、必要に応じて部分空間を「セル」と表記するとともに、６つの部分空間のそれぞれを、「セル０」ないし「セル５」と表記して区別する。なお、部分空間の数や形状、大きさは図４に限定されず、種々の変更が可能である。図３に戻り、並列化許否管理部２１０は、他のプロセッサの並列化許否管理部（図示せず）と協働して、部分空間の組合せごとに並列化の許否を管理する。これは、図２に示される並列化許否管理テーブル１５６を更新することによって行われる。以下、具体例を示す。
【００１８】
図５は、図２に示される並列化許否管理テーブル１５６の記憶内容を例示する。この例は、複数の部分空間と複数の仮想物体との位置関係が図４に示される状態にある場合に基づく。この場合、１つの仮想物体がセル０およびセル１の境界をまたいで存在するので、セル０とセル１の組合せに対応するアドレスには「１」が書き込まれる。いずれかのプロセッサの並列化許否管理部が書込みを実行する。「１」を書き込むことは禁止フラグを立てることに相当し、これにより、セル０における仮想物体の衝突処理の任意のプロセッサによる実行と、セル１における仮想物体の衝突処理の他のプロセッサによる実行との並列化が禁止される。上記と同様に、セル１とセル４、セル３とセル４、セル４とセル５の組合せに対応するアドレスにも「１」が書き込まれ、並列化が禁止される。このように禁止することにより、境界をまたぐ仮想物体の速度を複数のプロセッサが同時に更新することによるデータの不整合が防止される。
【００１９】
一方、図４に示される状態ではいずれの仮想物体もセル０とセル３の境界をまたいで存在しないので、セル０とセル３の組合せに対応するアドレスには「０」が書き込まれる。いずれかのプロセッサの並列化許否管理部が書込みを実行する。「０」を書き込むことは許可フラグを立てることに相当し、これにより、セル０における仮想物体の衝突処理の任意のプロセッサによる実行と、セル３における仮想物体の衝突処理の他のプロセッサによる実行との並列化が許可される。上記と同様に、境界をまたぐ仮想物体のないセルの組合せに対応するアドレスには「０」が書き込まれ、並列化が許可される。このように許可することにより、並列処理の効率化に資する。
【００２０】
仮想物体の数が多いとき、個々の仮想物体について排他制御のための処理を実行すると、その計算量は相当なものとなり、並列処理の非効率化およびコスト高を招く傾向にある。一方、部分空間を単位として並列化の許否を判定できれば、このような問題は軽減される。本発明者のこうした知見が本実施の形態の基礎となっている。
【００２１】
図３に戻り、衝突判定部２１４は、いずれかのセルにおける仮想物体の衝突の有無を判定する。第２プロセッサ１２２および第３プロセッサ１３３のそれぞれによって実現される衝突判定部（図示せず）も同様にいずれかのセルにおける仮想物体の衝突の有無を判定する。こうして仮想物体の衝突の有無が部分空間を単位として並列化して判定される。全てのセルについて衝突判定が終了し、いずれかのセルにおいて衝突ありと判定されると、次に衝突処理がなされる。なお、衝突処理は、仮想物体の衝突の前後で仮想物体の属性を示すパラメータを更新する処理を含む。属性とは速度や形状、色、音、重さ、粘性などの物理的な状態や性質をいうが、必ずしも物理法則に従う必要はない。衝突している仮想物体に衝突による例えば反発力を与える処理は、衝突処理に含まれる。その他、衝突による合体や消滅、形状の変化などを実現することもまた衝突処理に含まれる。なお、衝突処理は、物理法則に従うものであってもよいし、ゲームのルールのようなあらかじめ定められた定義に従うものであってもよい。
【００２２】
担当空間決定部２１８は、衝突処理部２２６が複数の部分空間のいずれにおける仮想物体の衝突処理を担当すべきかを、図２に示される動的管理テーブル１５８を参照して決定する。第２プロセッサ１２２および第３プロセッサ１３３のそれぞれによって実現される担当空間決定部（図示せず）も同様に、自己のプロセッサの衝突処理部が複数の部分空間のいずれにおける仮想物体の衝突処理を担当すべきかを決定する。動的管理テーブル１５８は、並列化許否管理部２１０の情報すなわち並列化許否管理テーブル１５６の記憶内容と、現在の衝突処理の状況とに基づいて記憶内容が定められる。以下、具体例を示す。
【００２３】
図６は、図２に示される動的管理テーブル１５８のある時点における記憶内容を例示する。図５と同様にこの例も、複数の部分空間と複数の仮想物体との位置関係が図４に示される状態にある場合に基づく。動的管理テーブル１５８は、大きく分けて以下の情報を記憶し、それらの情報は、現在の衝突処理の状況を反映するよう各プロセッサの担当空間決定部によって更新される。
・第１プロセッサ１１１ないし第３プロセッサ１３３のそれぞれによって現在衝突処理がなされているセルと、他のセルのそれぞれとの並列化の許否（「０」：許可、「１」：禁止）
・現在衝突処理がなされているセルおよび既に処理が完了したセルと、まだ処理が開始されていないセルとの区別（「０」：処理未開始、「１」：処理中もしくは処理済）
・上記データをセルごとに論理和演算した結果（「０」：処理可能、「１」：処理不可能）
【００２４】
論理和演算結果が「０」となるセルは、現在衝突処理がなされているセルとの並列化が禁止されてなく、かつ、まだ処理が開始されていないセルである。一方、論理和演算結果が「１」となるセルは、現在衝突処理がなされているセルとの並列化が禁止されている、あるいは、現在処理中もしくは既に処理済のセルである。
【００２５】
図６に示される記憶内容は下記の状況を反映している。
・第１プロセッサ１１１は仮想物体の衝突処理を実行していない。
・第２プロセッサ１２２はセル２における仮想物体の衝突処理を実行している。
・第３プロセッサ１３３はセル１における仮想物体の衝突処理を実行している。
・セル０ないしセル５における仮想物体の衝突処理はいずれも完了していない。
【００２６】
図６の４行目のデータを見ると、第３プロセッサ１３３が現在セル１における仮想物体の衝突処理を実行中で、この衝突処理と並列化が可能なのは、セル１ないしセル３、セル５である。このデータは、図５の３行目のものをコピーすればよい。なお、現在セル１における仮想物体の衝突処理がなされているのもかかわらず図６の４行目を見る限りはセル１の並列化は禁止されていないが、５行目のデータによってセル１の並列化は禁止される。図６の５行目を見ると、セル１およびセル２が衝突処理が現在実行中あるいは既に完了している。同６行目を見ると、上記の状況で衝突処理を実行可能なセルはセル３あるいはセル５である。したがって、衝突処理を現在実行していない第１プロセッサ１１１にはセル３あるいはセル５における仮想物体の衝突処理を割り当てることが可能である。
【００２７】
図３に戻り、担当空間決定部２１８は、動的管理テーブル１５８の例えば図６に示される記憶内容に基づいて、衝突処理部２２６にセル３あるいはセル５における仮想物体の衝突処理を割り当てる。例えばセル３における仮想物体の衝突処理を割り当てた場合、担当空間決定部２１８は、図６の２行目に図５の５行目のデータをコピーするとともに、図６の５行目のセル３のところに処理中フラグの意味で「１」を書き込む。
【００２８】
衝突処理部２２６は、担当空間決定部２１８から割り当てられたセルにおける衝突処理を実行する。本実施の形態では分散メモリ型、すなわち、各プロセッサが内部にローカルメモリ（図示せず）を有している場合を想定する。このため、衝突処理部２２６は、割り当てられたセルに存在する仮想物体の例えば速度データを空間情報バッファ１５２から第１プロセッサ１１１内のメモリに読み出し、衝突による反発力を与える計算をし、結果を空間情報バッファ１５２に書き戻す。第２プロセッサ１２２および第３プロセッサ１３３のそれぞれによって実現される衝突処理部（図示せず）も同様に、自己の担当空間決定部から割り当てられたセルにおける仮想物体の衝突処理を実行する。こうして仮想物体の衝突処理が部分空間を単位として並列化して実行される。なお、衝突処理部２２６は、割り当てられたセルにおける仮想物体の衝突処理が完了した際には、図６の２行目のデータをクリアして「０」にし、次の割当てを待つ。
【００２９】
図７は、図３に示される第１プロセッサ１１１の動作のフローチャートである。以下、図３も参照しながら説明する。
まず、時間を示すパラメータｔが０に初期化される（Ｓ５０２）。空間分割部２０６は、他のプロセッサの空間分割部と協働して、複数の仮想物体が存在する仮想空間を複数の部分空間へ分割する（Ｓ５０４）。並列化許否管理部２１０は、他のプロセッサの並列化許否管理部と協働して、図２に示される並列化許否管理テーブル１５６を更新する（Ｓ５０６）。衝突判定部２１４は、いずれかの部分空間における仮想物体の衝突の有無を判定する（Ｓ５０８）。衝突がなければ（Ｓ５１２のＮｏ）、終了判定（Ｓ５１４のＮｏ）の後、空間情報更新部２０２は仮想物体の位置、速度をΔｔだけ進める（Ｓ５１８）。その後、空間分割（Ｓ５０４）から衝突判定（Ｓ５０８）までが再度実行される。なお、例えばユーザにより中断が指示された場合などは、終了判定の後、衝突処理が終了される（Ｓ５１４のＹｅｓ）。
【００３０】
衝突があった場合（Ｓ５１２のＹｅｓ）、担当空間決定部２１８は、図２に示される動的管理テーブル１５８を参照することにより衝突処理部２２６がいずれの部分空間における衝突処理を担当すべきかを決定するとともに、決定に基づいて動的管理テーブル１５８を更新する（Ｓ５２２）。衝突処理部２２６は、担当空間決定部２１８により担当すべきと決定された部分空間における衝突処理を実行し、処理が終了すると、動的管理テーブル１５８を更新する（Ｓ５２６）。その後、まだ衝突処理が開始されていない部分空間（以下、「未処理空間」）があれば（Ｓ５３２のＹｅｓ）、担当空間の決定（Ｓ５２２）と衝突処理（Ｓ５２６）が再度実行される。未処理空間がなくなると（Ｓ５３２のＮｏ）、終了判定（Ｓ５１４のＮｏ）の後、空間情報更新部２０２は仮想物体の位置、速度をΔｔだけ進める（Ｓ５１８）。その後、空間分割（Ｓ５０４）から衝突処理（Ｓ５２６）までの一連の処理が再度実行される。
【００３１】
本実施の形態によれば、並列化許否管理部２１０は部分空間を単位として並列化の許否を並列化許否管理テーブル１５６に記憶し、担当空間決定部２１８はこれに従って衝突処理部２２６が担当すべき部分空間を決定する。これにより、衝突処理部２２６は個々の仮想物体について排他制御のための処理を行うことから解放され、結果として並列処理の効率化およびコスト安に資する。
【００３２】
また、動的管理テーブル１５８は各プロセッサの担当空間決定部および衝突処理部によって更新され、各プロセッサの担当空間決定部は動的管理テーブル１５８を参照することによって自己のプロセッサの衝突処理部に現在衝突処理が可能な部分空間を担当させる。したがって、並列処理の集中管理のために別途プロセッサを設ける必要がない。これは物体衝突処理装置１００のハードウェア構成の単純化に有利である。
【００３３】
また、各プロセッサの担当空間決定部および衝突処理部は現在の衝突処理の状況を反映するよう動的管理テーブル１５８を更新し、各プロセッサの担当空間決定部は最新の状態に基づいて自己のプロセッサの衝突処理部にいずれかの部分空間における衝突処理を割り当てる。このような動的管理により並列化の斑を最小限に抑えられるため、並列処理の効率がよい。
【００３４】
さらに、空間分割部２０６による空間分割によって得られた複数の部分空間を衝突判定に利用するとともに衝突処理並列化の単位としても利用するため、並列化許否のために格別計算量が増えることもない。
【００３５】
（第２の実施の形態）
本実施の形態では、第１の実施の形態とは異なる工夫によって個々の仮想物体についての排他制御のための処理を不要とする。第２の実施の形態にかかる物体衝突処理装置のハードウェア構成は、図１に示されるものと同様である。
【００３６】
以下、第１の実施の形態と異なる部分を中心に本実施の形態を説明する。
図８は、第２の実施の形態におけるメインメモリ１５０の記憶領域のブロック図である。この図において図２と異なるところは、共有テーブル１５４にペア振分けテーブル１５５が設けられた点である。ペア振分けテーブル１５５の記憶内容については後述する。
【００３７】
図９は、第２の実施の形態における第１プロセッサ１１１の機能ブロック図である。この図において図３と異なるところは、グループ分割部３０６が設けられた点および担当空間決定部２１８が担当ペア決定部３１８に変わった点である。なお、第２プロセッサ１２２および第３プロセッサ１３３も第１プロセッサ１１１と同様の機能を実現する。
【００３８】
本実施の形態では、複数の仮想物体のそれぞれはあらかじめ番号が付される。グループ分割部３０６は、その番号に基づいて複数の仮想物体を複数のグループに分割する。グループ分割部３０６は一例として、０〜９９の番号が付された仮想物体をグループＧ０、１００〜１９９の番号が付された仮想物体をグループＧ１、・・・、５００〜５９９の番号が付された仮想物体をグループＧ５に所属させる。なお、仮想物体に付された番号は本発明の「識別情報」の例示である。識別情報は、複数の仮想物体のそれぞれを特定しうるものであればよい。
【００３９】
衝突判定部２１４は、第１の実施の形態と同様に衝突判定をするとともに、本実施の形態では、衝突している仮想物体ペアが見つかるつど仮想物体ペアの所属グループに基づいて仮想物体ペアを振り分ける。これは、図８に示されるペア振分けテーブル１５５を更新することによってなされる。以下、具体例を示す。
【００４０】
図１０は、ある時点における仮想物体の衝突状態を例示する。以下、ｎの番号が付された仮想物体を「仮想物体ｎ」と表記する。図１１は、図１０の状態においてペア振分けテーブル１５５に記憶される内容を例示する。この記憶内容は、図９の衝突判定部２１４が図１０の状態において衝突判定し、衝突している仮想物体ペアを振り分けたものである。
【００４１】
以下、仮想物体ｍと仮想物体ｎが衝突しているとき、この仮想物体ペアを「仮想物体ペアｍ−ｎ」と表記する。仮想物体ペア１−４６は、一方および他方がグループＧ０に属するので、グループＧ０とグループＧ０の組合せに分類される。仮想物体ペア４６−５８も同様にグループＧ０とグループＧ０の組合せに分類される。仮想物体ペア５８−２５８は、一方がグループＧ０に属し他方がグループＧ２に属するので、グループＧ０とグループＧ２の組合せに分類される。他の仮想物体ペアも同様にいずれかのグループの組合せに分類される。以下、仮想物体ペアが分類されているグループの組合せを必要に応じて「セル」と表記し、仮想物体ペアが分類されている図１１中の６つのグループの組合せのそれぞれを「セル０」ないし「セル５」と表記して区別する。図９に戻り、並列化許否管理部２１０は、他のプロセッサの並列化許否管理部（図示せず）と協働して、セルの組合せごとに並列化の許否を管理する。これは、図８に示される並列化許否管理テーブル１５６を更新することによって行われる。以下、具体例を示す。
【００４２】
図１２は、図８に示される並列化許否管理テーブル１５６の記憶内容を例示する。この例は、衝突している仮想物体ペアが図１１に示されるように各セルに分類された場合に基づく。この場合、セル０とセル１は共にグループＧ０を含む、すなわちセル０とセル１は共通のグループを含むので、セル０とセル１の組合せに対応するアドレスには「１」が書き込まれる。いずれかのプロセッサの並列化許否管理部が書込みを実行する。「１」を書き込むことは禁止フラグを立てることに相当し、これにより、セル０に分類された仮想物体ペアの衝突処理の任意のプロセッサによる実行と、セル１に分類された仮想物体ペアの衝突処理の他のプロセッサによる実行との並列化が禁止される。上記と同様に、セル１とセル２、セル１とセル３、セル２とセル３、セル２とセル４、セル３とセル５、セル４とセル５の組合せに対応するアドレスにも「１」が書き込まれ、並列化が禁止される。このように禁止することにより、２つのセルに共通のグループに所属する１つの仮想物体の速度を複数のプロセッサが同時に更新することによるデータの不整合が防止される。
【００４３】
一方、セル０とセル２は共通のグループを含まないので、セル０とセル２の組合せに対応するアドレスには「０」が書き込まれる。いずれかのプロセッサの並列化許否管理部が書込みを実行する。「０」を書き込むことは許可フラグを立てることに相当し、これにより、セル０に分類された仮想物体ペアの衝突処理の任意のプロセッサによる実行と、セル２に分類された仮想物体ペアの衝突処理の他のプロセッサによる実行との並列化が許可される。上記と同様に、共通のグループを含まないセルの組合せに対応するアドレスには「０」が書き込まれ、並列化が許可される。このように許可することにより、並列処理の効率化に資する。
【００４４】
前述の第１の実施の形態では部分空間を単位として並列化の許否を判定したが、本実施の形態ではこのように仮想物体ペアの所属グループの組合せを単位として並列化の許否を判定する。この場合も、並列処理の非効率化およびコスト高の問題が軽減される。なお、仮想物体ペアの分類されていないグループの組合せも「セル」として並列化許否管理の対象としてもよい。
【００４５】
図９に戻り、担当ペア決定部３１８は、衝突処理部２２６がいずれのセルに分類された仮想物体ペアの衝突処理を担当すべきかを、図８に示される動的管理テーブル１５８を参照して決定する。第２プロセッサ１２２および第３プロセッサ１３３のそれぞれによって実現される担当ペア決定部（図示せず）も同様に、自己のプロセッサの衝突処理部がいずれのセルに分類された仮想物体ペアの衝突処理を担当すべきかを決定する。動的管理テーブル１５８は、第１の実施の形態と同様、並列化許否管理部２１０の情報すなわち並列化許否管理テーブル１５６の記憶内容と、現在の衝突処理の状況とに基づいて記憶内容が定められる。
【００４６】
衝突処理部２２６は、担当ペア決定部３１８から割り当てられたセルに分類されている仮想物体ペアの衝突処理を実行する。第２プロセッサ１２２および第３プロセッサ１３３のそれぞれによって実現される衝突処理部（図示せず）も同様に、自己の担当ペア決定部から割り当てられたセルに分類されている仮想物体の衝突処理を実行する。こうして仮想物体の衝突処理が並列化して実行される。
【００４７】
図１３は、図９に示される第１プロセッサ１１１の動作のフローチャートである。以下、図９も参照しながら説明する。
まず、時間を示すパラメータｔが０に初期化される（Ｓ６０２）。グループ分割部３０６は、各仮想物体に付された番号に基づいて複数の仮想物体を複数のグループに分割する（Ｓ６０３）。空間分割部２０６は、他のプロセッサの空間分割部と協働して、複数の仮想物体が存在する仮想空間を複数の部分空間へ分割する（Ｓ６０４）。衝突判定部２１４は、いずれかの部分空間における仮想物体の衝突の有無を判定し、衝突している仮想物体ペアが見つかるつど仮想物体ペアの所属グループに基づいて仮想物体ペアを振り分ける（Ｓ６０８）。衝突がなければ（Ｓ６１２のＮｏ）、終了判定（Ｓ６１４のＮｏ）の後、空間情報更新部２０２は仮想物体の位置、速度をΔｔだけ進める（Ｓ６１８）。その後、グループ分け（Ｓ６０３）から衝突判定（Ｓ６０８）までが再度実行される。なお、例えばユーザにより中断が指示された場合などは、終了判定の後、衝突処理が終了される（Ｓ６１４のＹｅｓ）。
【００４８】
衝突があった場合（Ｓ６１２のＹｅｓ）、並列化許否管理部２１０は、他のプロセッサの並列化許否管理部と協働して、図８に示される並列化許否管理テーブル１５６を更新する（Ｓ６２１）。担当ペア決定部３１８は、図８に示される動的管理テーブル１５８を参照することにより衝突処理部２２６がいずれのセルに分類された仮想物体ペアの衝突処理を担当すべきかを決定するとともに、決定に基づいて動的管理テーブル１５８を更新する（Ｓ６２２）。衝突処理部２２６は、担当ペア決定部３１８により担当すべきと決定された仮想物体ペアの衝突処理を実行し、処理が終了すると、動的管理テーブル１５８を更新する（Ｓ６２６）。その後、まだ衝突処理が開始されていないセル（以下、「未処理セル」）があれば（Ｓ６３２のＹｅｓ）、担当ペアの決定（Ｓ６２２）と衝突処理（Ｓ６２６）が再度実行される。未処理セルがなくなると（Ｓ６３２のＮｏ）、終了判定（Ｓ６１４のＮｏ）の後、空間情報更新部２０２は仮想物体の位置、速度をΔｔだけ進める（Ｓ６１８）。その後、グループ分け（Ｓ６０３）から衝突処理（Ｓ６２６）までの一連の処理が再度実行される。
【００４９】
本実施の形態によれば、並列化許否管理部２１０は仮想物体ペアの所属グループの組合せを単位として並列化の許否を並列化許否管理テーブル１５６に記憶し、担当ペア決定部３１８はこれに従って衝突処理部２２６が担当すべき仮想物体ペアを決定する。これにより、第１の実施の形態と同様に、衝突処理部２２６は個々の仮想物体について排他制御のための処理を行うことから解放され、結果として並列処理の効率化およびコスト安に資する。その他、物体衝突処理装置１００のハードウェア構成の単純化に有利であることおよび並列化の斑を最小限に抑えられるため並列処理の効率が良いこと等、第１の実施の形態と同様の効果を奏する。
【００５０】
上記実施の形態は例示であり、それらの各構成要素や各処理プロセスの組合せにいろいろな変形が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。以下、変形例を列挙する。
【００５１】
実施の形態においては第１プロセッサ１１１ないし第３プロセッサ１３３は同様の機能を実現するとしたが、これには限定されず、衝突処理部以外の機能は第１プロセッサ１１１だけが有していても良い。この場合、第１プロセッサ１１１が他のプロセッサへの衝突処理の割当てを担当する。本変形例も、個々の仮想物体について排他制御のための処理を行う必要がないという点で実施の形態と同様に並列処理の効率化およびコスト安に資する。
【００５２】
また、第１プロセッサ１１１ないし第３プロセッサ１３３とは別に、これらプロセッサを制御する制御プロセッサを別に設けてもよく、並列化許否管理テーブル１５６や動的管理テーブル１５８の更新、あるいは各プロセッサへの衝突処理の割当てを制御プロセッサにより行ってもよい。本変形例も、個々の仮想物体について排他制御のための処理を行う必要がないという点で実施の形態と同様に並列処理の効率化およびコスト安に資する。
【００５３】
実施の形態では各プロセッサが内部にローカルメモリを有する分散メモリ型を説明したが、これには限定されず、共有メモリ型であってもよい。
【００５４】
第２の実施の形態においては仮想物体ペアの所属グループの組合せを単位として並列化の許否を決めるので、空間分割をしないことも考えられる。
【図面の簡単な説明】
【００５５】
【図１】第１の実施の形態に係る物体衝突処理装置の例示的なハードウェア構成図である。
【図２】図１に示されるメインメモリの記憶領域のブロック図である。
【図３】図１に示される第１プロセッサの機能ブロック図である。
【図４】第１の実施の形態における空間分割を例示する図である。
【図５】図２に示される並列化許否管理テーブルの記憶内容を例示する図である。
【図６】図２に示される動的管理テーブルのある時点における記憶内容を例示する図である。
【図７】図３に示される第１プロセッサの動作のフローチャートである。
【図８】第２の実施の形態におけるメインメモリの記憶領域のブロック図である。
【図９】第２の実施の形態における第１プロセッサの機能ブロック図である。
【図１０】ある時点における仮想物体の衝突状態を例示する図である。
【図１１】図１０の状態においてペア振分けテーブルに記憶される内容を例示する図である。
【図１２】図８に示される並列化許否管理テーブルの記憶内容を例示する図である。
【図１３】図９に示される第１プロセッサの動作のフローチャートである。
【符号の説明】
【００５６】
１００・・・物体衝突処理装置、１１１・・・第１プロセッサ、１２２・・・第２プロセッサ、１３３・・・第３プロセッサ、１５０・・・メインメモリ、１５２・・・空間情報バッファ、１５４・・・共有テーブル、１５５・・・ペア振分けテーブル、１５６・・・並列化許否管理テーブル、１５８・・・動的管理テーブル、１８０・・・バス、２０２・・・空間情報更新部、２０６・・・空間分割部、２１０・・・並列化許否管理部、２１４・・・衝突判定部、２１８・・・担当空間決定部、２２６・・・衝突処理部、３０６・・・グループ分割部、３１８・・・担当ペア決定部。
【特許請求の範囲】
【請求項１】
複数の仮想物体が存在する仮想空間を複数の部分空間へ分割するステップと、
いずれかの仮想物体が第１および第２の部分空間の境界をまたいで存在するとき、第１の部分空間における仮想物体の衝突処理の任意のプロセッサによる実行と、第２の部分空間における仮想物体の衝突処理の他のプロセッサによる実行との並列化を禁止するステップと、
複数のプロセッサのそれぞれが複数の部分空間のいずれかにおける仮想物体の衝突処理を担当することにより、仮想物体の衝突処理を、部分空間を単位として並列化して実行するステップと、
を備えることを特徴とする物体衝突処理方法。
【請求項２】
請求項１に記載の方法において、禁止するステップは、並列化が禁止された第１および第２の部分空間の組合せを、複数のプロセッサに共有とされるメモリ領域に設けられたテーブルに記憶するステップを含み、
実行するステップは、複数のプロセッサのいずれかが、前記テーブルを参照することにより、他のプロセッサによって現在なされている衝突処理と並列化が禁止されていない衝突処理を自己に割り当てるステップを含むことを特徴とする物体衝突処理方法。
【請求項３】
請求項１または２に記載の方法において、当該方法はさらに、実行するステップに先立ち、複数のプロセッサのそれぞれが複数の部分空間のいずれかにおける仮想物体の衝突の有無を判定することにより、仮想物体の衝突の有無を、部分空間を単位として並列化して判定するステップを備えることを特徴とする物体衝突処理方法。
【請求項４】
複数の仮想物体を所定の規則で複数のグループへ分割するステップと、
衝突している仮想物体ペアの一方が第１のグループに属し、他方が第２のグループに属するとき、この仮想物体ペアの衝突処理の任意のプロセッサによる実行と、第１もしくは第２のグループに属する仮想物体が関係する他の仮想物体ペアの衝突処理の他のプロセッサによる実行との並列化を禁止するステップと、
複数のプロセッサのそれぞれがいずれかの仮想物体ペアの衝突処理を担当することにより、仮想物体の衝突処理を並列化して実行するステップと、
を備えることを特徴とする物体衝突処理方法。
【請求項５】
請求項４に記載の方法において、複数の仮想物体のそれぞれには識別情報が割り当てられていて、その識別情報に応じて前記の分割が実行されることを特徴とする物体衝突処理方法。
【請求項６】
請求項４または５に記載の方法において、禁止するステップは、並列化が禁止された仮想物体ペアの組合せを、複数のプロセッサに共有とされるメモリ領域に設けられたテーブルに記憶するステップを含み、
実行するステップは、複数のプロセッサのいずれかが、前記テーブルを参照することにより、他のプロセッサによって現在なされている衝突処理と並列化が禁止されていない衝突処理を自己に割り当てるステップを含むことを特徴とする物体衝突処理方法。
【請求項７】
請求項１から６のいずれかに記載の方法において、衝突処理は、仮想物体の衝突の前後で仮想物体の属性を示すパラメータを更新する処理を含むことを特徴とする物体衝突処理方法。
【請求項８】
複数の仮想物体が存在する仮想空間を複数の部分空間へ分割する手順と、
いずれかの仮想物体が第１および第２の部分空間の境界をまたいで存在するとき、第１の部分空間における仮想物体の衝突処理の任意のプロセッサによる実行と、第２の部分空間における仮想物体の衝突処理の他のプロセッサによる実行との並列化を禁止する手順と、
複数のプロセッサのそれぞれが複数の部分空間のいずれかにおける仮想物体の衝突処理を担当することにより、仮想物体の衝突処理を、部分空間を単位として並列化して実行する手順と、
をコンピュータに実行させることを特徴とする物体衝突処理プログラム。
【請求項９】
請求項８に記載のプログラムにおいて、禁止する手順は、並列化が禁止された第１および第２の部分空間の組合せを、複数のプロセッサに共有とされるメモリ領域に設けられたテーブルに記憶する手順を含み、
実行する手順は、複数のプロセッサのいずれかが、前記テーブルを参照することにより、他のプロセッサによって現在なされている衝突処理と並列化が禁止されていない衝突処理を自己に割り当てる手順を含むことを特徴とする物体衝突処理プログラム。
【請求項１０】
請求項８または９に記載のプログラムにおいて、当該プログラムはさらに、実行する手順に先立ち、複数のプロセッサのそれぞれが複数の部分空間のいずれかにおける仮想物体の衝突の有無を判定することにより、仮想物体の衝突の有無を、部分空間を単位として並列化して判定する手順をコンピュータに実行させることを特徴とする物体衝突処理プログラム。
【請求項１１】
複数の仮想物体を所定の規則で複数のグループへ分割する手順と、
衝突している仮想物体ペアの一方が第１のグループに属し、他方が第２のグループに属するとき、この仮想物体ペアの衝突処理の任意のプロセッサによる実行と、第１もしくは第２のグループに属する仮想物体が関係する他の仮想物体ペアの衝突処理の他のプロセッサによる実行との並列化を禁止する手順と、
複数のプロセッサのそれぞれがいずれかの仮想物体ペアの衝突処理を担当することにより、仮想物体の衝突処理を並列化して実行する手順と、
をコンピュータに実行させることを特徴とする物体衝突処理プログラム。
【請求項１２】
請求項１１に記載のプログラムにおいて、禁止する手順は、並列化が禁止された仮想物体ペアの組合せを、複数のプロセッサに共有とされるメモリ領域に設けられたテーブルに記憶する手順を含み、
実行する手順は、複数のプロセッサのいずれかが、前記テーブルを参照することにより、他のプロセッサによって現在なされている衝突処理と並列化が禁止されていない衝突処理を自己に割り当てる手順を含むことを特徴とする物体衝突処理プログラム。
【請求項１３】
請求項８から１２のいずれかに記載のプログラムにおいて、衝突処理は、仮想物体の衝突の前後で仮想物体の属性を示すパラメータを更新する処理を含むことを特徴とする物体衝突処理プログラム。
【請求項１４】
複数のプロセッサと、
複数の仮想物体が存在する仮想空間を複数の部分空間へ分割する、複数のプロセッサのいずれかによって実現される分割部と、
いずれかの仮想物体が第１および第２の部分空間の境界をまたいで存在するとき、第１の部分空間における仮想物体の衝突処理のいずれかのプロセッサによる実行と、第２の部分空間における仮想物体の衝突処理の他のプロセッサによる実行との並列化を禁止するための情報を管理する、複数のプロセッサのいずれかによって実現される並列化許否管理部と、
複数のプロセッサのいずれかが複数の部分空間のいずれにおける仮想物体の衝突処理を担当すべきかを、並列化許否管理部の情報を利用して決定する、複数のプロセッサのいずれかによって実現される担当空間決定部と、
を備え、複数のプロセッサは、仮想物体の衝突処理を、担当空間決定部によって担当すべきと決定された部分空間を単位として実行することを特徴とする物体衝突処理装置。
【請求項１５】
請求項１４に記載の装置において、当該装置はさらに、複数のプロセッサに共有とされるメモリ領域に設けられ、並列化が禁止された第１および第２の部分空間の組合せを記憶する、並列化許否管理部によって管理されるテーブルを含み、
担当空間決定部は、複数のプロセッサのそれぞれに設けられ、
各プロセッサの担当空間決定部は、前記テーブルを参照することにより、他のプロセッサによって現在なされている衝突処理と並列化が禁止されていない衝突処理を自己のプロセッサの担当すべき衝突処理と決定することを特徴とする物体衝突処理装置。
【請求項１６】
請求項１４または１５に記載の装置において、当該装置はさらに、衝突処理の実行に先立ち、複数の部分空間のいずれかにおける仮想物体の衝突の有無を判定する、複数のプロセッサのいずれかによって実現される衝突判定部を含むことを特徴とする物体衝突処理装置。
【請求項１７】
複数のプロセッサと、
複数の仮想物体を所定の規則で複数のグループへ分割する、複数のプロセッサのいずれかによって実現される分割部と、
衝突している仮想物体ペアの一方が第１のグループに属し、他方が第２のグループに属するとき、この仮想物体ペアの衝突処理の任意のプロセッサによる実行と、第１もしくは第２のグループに属する仮想物体が関係する他の仮想物体ペアの衝突処理の他のプロセッサによる実行との並列化を禁止するための情報を管理する、複数のプロセッサのいずれかによって実現される並列化許否管理部と、
複数のプロセッサのいずれかがいずれの仮想物体ペアの衝突処理を担当すべきかを、並列化許否管理部の情報を利用して決定する、複数のプロセッサのいずれかによって実現される担当ペア決定部と、
を備え、複数のプロセッサは、担当ペア決定部によって担当すべきと決定された仮想物体ペアの衝突処理を実行することを特徴とする物体衝突処理装置。
【請求項１８】
請求項１７に記載の装置において、当該装置はさらに、複数のプロセッサに共有とされるメモリ領域に設けられ、並列化が禁止された仮想物体ペアの組合せを記憶する、並列化許否管理部によって管理されるテーブルを含み、
担当ペア決定部は、複数のプロセッサのそれぞれに設けられ、
各プロセッサの担当ペア決定部は、前記テーブルを参照することにより、他のプロセッサによって現在なされている衝突処理と並列化が禁止されていない衝突処理を自己のプロセッサの担当すべき衝突処理と決定することを特徴とする物体衝突処理装置。
【請求項１９】
請求項１４から１８のいずれかに記載の装置において、衝突処理は、仮想物体の衝突の前後で仮想物体の属性を示すパラメータを更新する処理を含むことを特徴とする物体衝突処理装置。
【請求項１】
複数の仮想物体が存在する仮想空間を複数の部分空間へ分割するステップと、
いずれかの仮想物体が第１および第２の部分空間の境界をまたいで存在するとき、第１の部分空間における仮想物体の衝突処理の任意のプロセッサによる実行と、第２の部分空間における仮想物体の衝突処理の他のプロセッサによる実行との並列化を禁止するステップと、
複数のプロセッサのそれぞれが複数の部分空間のいずれかにおける仮想物体の衝突処理を担当することにより、仮想物体の衝突処理を、部分空間を単位として並列化して実行するステップと、
を備えることを特徴とする物体衝突処理方法。
【請求項２】
請求項１に記載の方法において、禁止するステップは、並列化が禁止された第１および第２の部分空間の組合せを、複数のプロセッサに共有とされるメモリ領域に設けられたテーブルに記憶するステップを含み、
実行するステップは、複数のプロセッサのいずれかが、前記テーブルを参照することにより、他のプロセッサによって現在なされている衝突処理と並列化が禁止されていない衝突処理を自己に割り当てるステップを含むことを特徴とする物体衝突処理方法。
【請求項３】
請求項１または２に記載の方法において、当該方法はさらに、実行するステップに先立ち、複数のプロセッサのそれぞれが複数の部分空間のいずれかにおける仮想物体の衝突の有無を判定することにより、仮想物体の衝突の有無を、部分空間を単位として並列化して判定するステップを備えることを特徴とする物体衝突処理方法。
【請求項４】
複数の仮想物体を所定の規則で複数のグループへ分割するステップと、
衝突している仮想物体ペアの一方が第１のグループに属し、他方が第２のグループに属するとき、この仮想物体ペアの衝突処理の任意のプロセッサによる実行と、第１もしくは第２のグループに属する仮想物体が関係する他の仮想物体ペアの衝突処理の他のプロセッサによる実行との並列化を禁止するステップと、
複数のプロセッサのそれぞれがいずれかの仮想物体ペアの衝突処理を担当することにより、仮想物体の衝突処理を並列化して実行するステップと、
を備えることを特徴とする物体衝突処理方法。
【請求項５】
請求項４に記載の方法において、複数の仮想物体のそれぞれには識別情報が割り当てられていて、その識別情報に応じて前記の分割が実行されることを特徴とする物体衝突処理方法。
【請求項６】
請求項４または５に記載の方法において、禁止するステップは、並列化が禁止された仮想物体ペアの組合せを、複数のプロセッサに共有とされるメモリ領域に設けられたテーブルに記憶するステップを含み、
実行するステップは、複数のプロセッサのいずれかが、前記テーブルを参照することにより、他のプロセッサによって現在なされている衝突処理と並列化が禁止されていない衝突処理を自己に割り当てるステップを含むことを特徴とする物体衝突処理方法。
【請求項７】
請求項１から６のいずれかに記載の方法において、衝突処理は、仮想物体の衝突の前後で仮想物体の属性を示すパラメータを更新する処理を含むことを特徴とする物体衝突処理方法。
【請求項８】
複数の仮想物体が存在する仮想空間を複数の部分空間へ分割する手順と、
いずれかの仮想物体が第１および第２の部分空間の境界をまたいで存在するとき、第１の部分空間における仮想物体の衝突処理の任意のプロセッサによる実行と、第２の部分空間における仮想物体の衝突処理の他のプロセッサによる実行との並列化を禁止する手順と、
複数のプロセッサのそれぞれが複数の部分空間のいずれかにおける仮想物体の衝突処理を担当することにより、仮想物体の衝突処理を、部分空間を単位として並列化して実行する手順と、
をコンピュータに実行させることを特徴とする物体衝突処理プログラム。
【請求項９】
請求項８に記載のプログラムにおいて、禁止する手順は、並列化が禁止された第１および第２の部分空間の組合せを、複数のプロセッサに共有とされるメモリ領域に設けられたテーブルに記憶する手順を含み、
実行する手順は、複数のプロセッサのいずれかが、前記テーブルを参照することにより、他のプロセッサによって現在なされている衝突処理と並列化が禁止されていない衝突処理を自己に割り当てる手順を含むことを特徴とする物体衝突処理プログラム。
【請求項１０】
請求項８または９に記載のプログラムにおいて、当該プログラムはさらに、実行する手順に先立ち、複数のプロセッサのそれぞれが複数の部分空間のいずれかにおける仮想物体の衝突の有無を判定することにより、仮想物体の衝突の有無を、部分空間を単位として並列化して判定する手順をコンピュータに実行させることを特徴とする物体衝突処理プログラム。
【請求項１１】
複数の仮想物体を所定の規則で複数のグループへ分割する手順と、
衝突している仮想物体ペアの一方が第１のグループに属し、他方が第２のグループに属するとき、この仮想物体ペアの衝突処理の任意のプロセッサによる実行と、第１もしくは第２のグループに属する仮想物体が関係する他の仮想物体ペアの衝突処理の他のプロセッサによる実行との並列化を禁止する手順と、
複数のプロセッサのそれぞれがいずれかの仮想物体ペアの衝突処理を担当することにより、仮想物体の衝突処理を並列化して実行する手順と、
をコンピュータに実行させることを特徴とする物体衝突処理プログラム。
【請求項１２】
請求項１１に記載のプログラムにおいて、禁止する手順は、並列化が禁止された仮想物体ペアの組合せを、複数のプロセッサに共有とされるメモリ領域に設けられたテーブルに記憶する手順を含み、
実行する手順は、複数のプロセッサのいずれかが、前記テーブルを参照することにより、他のプロセッサによって現在なされている衝突処理と並列化が禁止されていない衝突処理を自己に割り当てる手順を含むことを特徴とする物体衝突処理プログラム。
【請求項１３】
請求項８から１２のいずれかに記載のプログラムにおいて、衝突処理は、仮想物体の衝突の前後で仮想物体の属性を示すパラメータを更新する処理を含むことを特徴とする物体衝突処理プログラム。
【請求項１４】
複数のプロセッサと、
複数の仮想物体が存在する仮想空間を複数の部分空間へ分割する、複数のプロセッサのいずれかによって実現される分割部と、
いずれかの仮想物体が第１および第２の部分空間の境界をまたいで存在するとき、第１の部分空間における仮想物体の衝突処理のいずれかのプロセッサによる実行と、第２の部分空間における仮想物体の衝突処理の他のプロセッサによる実行との並列化を禁止するための情報を管理する、複数のプロセッサのいずれかによって実現される並列化許否管理部と、
複数のプロセッサのいずれかが複数の部分空間のいずれにおける仮想物体の衝突処理を担当すべきかを、並列化許否管理部の情報を利用して決定する、複数のプロセッサのいずれかによって実現される担当空間決定部と、
を備え、複数のプロセッサは、仮想物体の衝突処理を、担当空間決定部によって担当すべきと決定された部分空間を単位として実行することを特徴とする物体衝突処理装置。
【請求項１５】
請求項１４に記載の装置において、当該装置はさらに、複数のプロセッサに共有とされるメモリ領域に設けられ、並列化が禁止された第１および第２の部分空間の組合せを記憶する、並列化許否管理部によって管理されるテーブルを含み、
担当空間決定部は、複数のプロセッサのそれぞれに設けられ、
各プロセッサの担当空間決定部は、前記テーブルを参照することにより、他のプロセッサによって現在なされている衝突処理と並列化が禁止されていない衝突処理を自己のプロセッサの担当すべき衝突処理と決定することを特徴とする物体衝突処理装置。
【請求項１６】
請求項１４または１５に記載の装置において、当該装置はさらに、衝突処理の実行に先立ち、複数の部分空間のいずれかにおける仮想物体の衝突の有無を判定する、複数のプロセッサのいずれかによって実現される衝突判定部を含むことを特徴とする物体衝突処理装置。
【請求項１７】
複数のプロセッサと、
複数の仮想物体を所定の規則で複数のグループへ分割する、複数のプロセッサのいずれかによって実現される分割部と、
衝突している仮想物体ペアの一方が第１のグループに属し、他方が第２のグループに属するとき、この仮想物体ペアの衝突処理の任意のプロセッサによる実行と、第１もしくは第２のグループに属する仮想物体が関係する他の仮想物体ペアの衝突処理の他のプロセッサによる実行との並列化を禁止するための情報を管理する、複数のプロセッサのいずれかによって実現される並列化許否管理部と、
複数のプロセッサのいずれかがいずれの仮想物体ペアの衝突処理を担当すべきかを、並列化許否管理部の情報を利用して決定する、複数のプロセッサのいずれかによって実現される担当ペア決定部と、
を備え、複数のプロセッサは、担当ペア決定部によって担当すべきと決定された仮想物体ペアの衝突処理を実行することを特徴とする物体衝突処理装置。
【請求項１８】
請求項１７に記載の装置において、当該装置はさらに、複数のプロセッサに共有とされるメモリ領域に設けられ、並列化が禁止された仮想物体ペアの組合せを記憶する、並列化許否管理部によって管理されるテーブルを含み、
担当ペア決定部は、複数のプロセッサのそれぞれに設けられ、
各プロセッサの担当ペア決定部は、前記テーブルを参照することにより、他のプロセッサによって現在なされている衝突処理と並列化が禁止されていない衝突処理を自己のプロセッサの担当すべき衝突処理と決定することを特徴とする物体衝突処理装置。
【請求項１９】
請求項１４から１８のいずれかに記載の装置において、衝突処理は、仮想物体の衝突の前後で仮想物体の属性を示すパラメータを更新する処理を含むことを特徴とする物体衝突処理装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２００８−１７１１７６（Ｐ２００８−１７１１７６Ａ）
【公開日】平成２０年７月２４日（２００８．７．２４）
【国際特許分類】
【出願番号】特願２００７−３３５９（Ｐ２００７−３３５９）
【出願日】平成１９年１月１１日（２００７．１．１１）
【出願人】（３９５０１５３１９）株式会社ソニー・コンピュータエンタテインメント (871)
【Ｆターム（参考）】
【公開日】平成２０年７月２４日（２００８．７．２４）
【国際特許分類】
【出願日】平成１９年１月１１日（２００７．１．１１）
【出願人】（３９５０１５３１９）株式会社ソニー・コンピュータエンタテインメント (871)
【Ｆターム（参考）】
[ Back to top ]