可視衝突検出回路
【課題】ＣＧの物体間の衝突検出回路に関し、レンダラー側に衝突検出回路を設けてハードウエアにより衝突を検出し、アプリケーションプロセッサの軽減と描画の高速化を図る。
【解決手段】物体間の衝突を検出する手段として、対象映像表示空間を取り囲む６面体を定義し、それぞれの面の外部から空間内部を見た空間内部の静止物体を６面のそれぞれに投影し、投影された物体の有無フラグ、識別子、Ｚ値、法線を６面分生成・記憶する手段と、レンダリング段階において、動体の内挿補間時にレンダリング点を６面それぞれの座標系に変換し、前記６面内の静体のフラグ、識別子、Ｚ値、法線を読み出し、内挿補間点のオーバラップの有無、その点での静止物体の識別子、Ｚ値から内挿補間点の衝突を判定する手段と、動く物体の方向や法線、衝突される物体の法線から、衝突する物体の衝突後の動きを求めるための情報をアプリケーションプロセッサに出力する手段からなる。
【解決手段】物体間の衝突を検出する手段として、対象映像表示空間を取り囲む６面体を定義し、それぞれの面の外部から空間内部を見た空間内部の静止物体を６面のそれぞれに投影し、投影された物体の有無フラグ、識別子、Ｚ値、法線を６面分生成・記憶する手段と、レンダリング段階において、動体の内挿補間時にレンダリング点を６面それぞれの座標系に変換し、前記６面内の静体のフラグ、識別子、Ｚ値、法線を読み出し、内挿補間点のオーバラップの有無、その点での静止物体の識別子、Ｚ値から内挿補間点の衝突を判定する手段と、動く物体の方向や法線、衝突される物体の法線から、衝突する物体の衝突後の動きを求めるための情報をアプリケーションプロセッサに出力する手段からなる。
【発明の詳細な説明】
【技術分野】
【００１】
この発明は コンピュータグラフィックス技術において物体間の衝突を検出するための手段と、それを実現するための回路の実装に関する。
【背景技術】
【００２】
コンピュータグラフィックスのアプリケーションには、物体同士の衝突を含むアニメーションが多く制作されている。従来から衝突検出は、アプリケーションプロセッサ（以下ＡＰという）側のプログラミングによるバウンダリーボックスや物体のツリー構造法に基づき高速処理が図られてきた。実時間描画が必要なゲーム等のアニメーションでは、これら衝突検出の計算負荷は極めて大きい。このためＣＧ映像の現実感や実時間描画を得るためには、描画量の増加と物理モデル等の複雑系処理等が必須であり、ＡＰの負荷は今後一層深刻となる。正確な衝突検出をＡＰ側のソフトウエアで対応する限り、高速化とデータ量削減との相反する問題を解決しなければならない問題をこれまでに抱えていた。
【発明の開示】
【発明が解決しようとする課題】
【００３】
本発明はＡＰに実装されるプログラムを用いて物体間の衝突を検出するのではなく、ピクセルシェーダーあるいはラスタライザーと言われるレンダラー側のハードウエアで衝突を検出する。ＡＰ側から衝突検出処理を無くし、ＡＰは一般描画と同じ物体プリミティブ（ポリゴン）をレンダラーに出力するのみとし、ハードウエアによって衝突検出を行うことでＡＰの負荷の軽減と描画の高速化を図ることが本発明の課題である。
【課題を解決するための手段】
【００４】
レンダラーには通常、ポリゴン描画、テキスチャマッピング、環境マッピング、照明のためのシェーダー等がハードウエア実装されている。本発明はこれらグラフィックスプロセッサが具備する既存の機能群と同化した構造で物体間衝突検出回路を導入する。
【００５】
視覚的に物体が衝突しているか否かは、衝突箇所に遮蔽物体がなければ複数の視角から物体を眺めることで認知できる。このアルゴリズムとして描画空間全体を取り囲む６面体（立方体あるいは直方体のいずれかで、以下Ｃｕｂｅという）を設定し、これら６面からＣｕｂｅ内部を見て、動く物体（以下動体という）と他の物体（以下静体という）との接触の可否を検査することで衝突が認知できる。このため描画空間全体を仮想的にＣｕｂｅで囲み、Ｃｕｂｅのそれぞれの面にはＣｕｂｅ外部から内部を投影した画像を写像し、この６面分の写像図をＣｕｂｅパターンとして保存する。衝突箇所が完全に遮蔽された空間内でない限り、複数の面から見て、動体と静体とが重なり合っていれば衝突と見なすことができる。これは人間が視覚的に物体衝突を認知するプロセスと同じである。
【００６】
前記Ｃｕｂｅそれぞれの６面にＣｕｂｅ内部の映像を投影する手段として本発明では、６面それぞれに直交する座標軸上から並行投影でＣｕｂｅ内部画像を、隠面消去法を用い６面それぞれに描画する。投影中心がＣｕｂｅの内部と外部、あるいは透視投影と並行投影の違いを除くと、この方法はレンダリング前に予め作成される環境マッピング技術の環境Ｃｕｂｅ生成法と類似する。
【００７】
環境マッピング同様に動く物体が生じれば、その都度Ｃｕｂｅパターンは再生成しなければならない。これは６面分の描画となり負荷が大きい。本発明ではこれを避けるため全ての描画物体を、動体と静体とにそれぞれ分け、静体のみをＣｕｂｅ６面それぞれに予めパターンとして作成する。画像表示段階では、静体を先に、次に動体をレンダリングする。動体のポリゴンを内挿補間する段階で、補間点が静体と交差するか否かを、Ｃｕｂｅ６面それぞれのパターン（以下画像情報という）と比較し判定する。この判定には動体の内挿補間点を６面それぞれの座標系に変換し、面の画像と内挿補間点がオーバーラップするか否かのテストを行う。
【００８】
遮蔽物体がなければＣｕｂｅ画像情報と内挿補間点とのｘｙ座標の重なりテストのみであり、画像情報として記憶する情報は、環境マッピングのような色情報は必要ない。記憶される情報は画素あたり１ビットの画像の有無を示すフラグと静体の識別子のみとなる。衝突が検出された場合ＡＰに戻す値は、動体と静体それぞれの識別子と、衝突点の３次元座標値となる。これにより、衝突物体名と位置がＡＰ側で判断できる。動体と静体とを分離することによって、大半を占める静体のＣｕｂｅへの書き込みは前処理１回のみとなる。
【００９】
動体が複数存在した場合、動体間の衝突の検出も必要となる。本発明は複数の動体がある場合、動体専用の６面Ｃｕｂｅを別途用意し、内挿補間時に衝突検出処理と並行してこのＣｕｂｅに描画する。静体と動体Ｃｕｂｅそれぞれをテストすることで静体の再描画を不要とする。
【０１０】
動体のＣｕｂｅを定義する場合、複数の動体を纏めて１組のＣｕｂｅに書くか、動体毎にそれぞれ専用のＣｕｂｅを作成するかは同時に動く物体数あるいはハードウエア・コストに関係する。動体数が多く、一時的に動くものと、常時動くものがある場合には、それぞれの物体毎にＣｕｂｅを作成することによって効率を図ることができる。この場合は動体のためのＣｕｂｅは動体を取り囲む空間サイズでよい。
【０１１】
静体Ｃｕｂｅ画像情報を前処理で求めておくことは本発明の高速化の条件である。表示（レンダリング）段階では静体、動体のいずれの描画順でもよいが、静体を描画した後に動体を描画し、この動体描画時にのみ衝突検出処理を行うことで高速化が可能となる。実時間アニメーションでは１／３０秒あるいは１／６０秒以内で１フレームを描画するため、フレーム内で検出が可能となればよい。本発明では映像の描画中に、内挿補間処理の一つとして衝突を検出し、これをＡＰに戻すため（衝突が生じてから）１フレーム分の遅れをもって、ＡＰは次の映像を決定することになる。
【０１２】
レンダリング時の座標系は任意の視野方向をもつ視点座標系である。内挿補間点のＣｕｂｅ６面の画像情報とのオーバーラップ・テストは、内挿補間点座標値をＣｕｂｅ面それぞれの座標系に変換する。視点方向が任意角の場合は３次元回転が必要となる。内挿補間点毎の回転計算の負荷を避けるため、本発明ではＣｕｂｅをワールド座標で定義しＣｕｂｅの６面はそれぞれｘｙ、ｙｚ、ｘｚ面と平行とすることで回転計算を削減する。
【０１３】
また本発明では、動体のポリゴン頂点に視点系座標値と共に、ワールド座標値を付加し、これを同時にレンダリングし、視点座標値は描画に、一方ワールド座標値はＣｕｂｅ座標との衝突検出に用いることで面毎の回転計算処理を省き置換処理で対応する。
【０１４】
６面のいずれから見ても視点との間に遮蔽物がない場合は、互いに直交するＣｕｂｅ３面以上で交差していれば衝突の検出ができる。遮蔽物がある場合は追加情報が必要となる。本発明では複雑な形状同士の衝突を検出する手段として、静体のＺ値（Ｃｕｂｅ面からの距離）、静体の識別子および静体画像の有無を示すフラグをそれぞれＣｕｂｅ画像情報として記憶する。衝突判定は内挿補間点が、全てのＣｕｂｅ面で同一の識別子である静体とオーバーラップしている場合はその静体と衝突となる。また対面する面同士で動体が同一の識別子をもつ静体とオーバーラップし、いずれもＺ値比較において静体の後方に位置する場合も衝突と見なすことができる。Ｃｕｂｅ面によっては複数の物体が遮蔽する場合があり、内挿補間点でＣｕｂｅ面のそれぞれの識別子が異なる場合がある。この場合は動体のＺ値とオーバーラップする静体のＺ値と比較し、動体が静体に対してＣｕｂｅ面（手前）側に位置する場合は、静体とは衝突がないとする。一方、動体のＺ値が静体の内側（遠方）に位置するＣｕｂｅ面とそれぞれ直交する他のＣｕｂｅ４面でも動体が同一識別子（これを識別子Ａとする）をもつ物体の遠方でオーバーラップしている場合は衝突。さらに、多数の面で同一識別子Ａと遠方でオーバーラップするものの識別子の異なる物体（以下遮蔽体という）ともＣｕｂｅ面のいずれかでオーバーラップしていた場合、動体と遮蔽体とのそれぞれのＺ値を比較し、動体のＺ値が遮蔽体よりＣｕｂｅ面から遠方にある場合は、識別子Ａの物体とは衝突、手前にある場合は衝突していないものとする。
【０１５】
動体描画のリフレッショは映像表示のための走査フレーム単位で行われる。動体が静体（描画が終了した動体も静体と定義する）と衝突する場合は、Ｃｕｂｅ面から見て動体の一部が静体と交差した状態となる。動体が極めて高速に移動し１／６０秒以内で静体を通り抜ける場合は通常衝突検出不能となるが、互いの物体が交差状態にあれば動体と静体のＺ値とを動体の内挿補間時で画素毎に差分すれば、ある箇所で差分符号は背後から手前あるいはその逆に変化する。この変化時を捕えて衝突と見なすことができる。このために、動体の内挿補間段階で前記静体のＺ値および識別子を読み出し、内挿補間Ｚ値と前記読み出したＺ値をそれぞれ比較する。
【０１６】
衝突検出によるＡＰへの戻し情報として［００８］では、レンダラーは衝突それぞれの物体識別子と衝突位置を返すものとした。一方、衝突によって跳ね返りや静体が衝突によって移動する場合には、動体の動き方向、動体および静体それぞれの衝突点の面法線、質量や弾性等の物体の属性が必要となる。物体の速度や属性は識別子によってそれを所有し、制御しているＡＰ側で高速に判断できるが、衝突時点の動き方向や面法線はレンダラー側あるいはグラフィックス・エンジン内の中間処理段階で時系列的変化を伴って生成されている場合があり、これをＡＰ側で求めようとすると、衝突点から形状モデルの幾何学的展開が必要となる。この負荷は極めて大きい。本発明では、識別子や衝突位置に加えて、衝突点の動体および静体の面法線および動体の進行方向ベクトルをＡＰに返す。
【０１７】
前記手段として、動体の面法線は通常のシステムで多角形頂点データあるいは法線マップとして内挿補間処理に含まれており衝突検出段階で衝突点での面法線を得ることができる。また動体の動き方向は、これに基づきエンジン側で動体の次の座標値が決定されており、フレームサイクル毎のアップデートな情報として、レンダラーに動きベクトルを出力すれば、これをレンダラー側からＡＰに返すことができる。一方、静体の衝突点の面法線は、予め静体を記憶したＣｕｂｅ面情報として追加記憶する。以上から本発明ではＣｕｂｅ画像情報としてフラグ、識別子、ｚ座標値、面法線を記憶する手段をもつ。
【０１８】
静体の面法線は衝突の際にのみ必要であることから、Ｃｕｂｅ画像情報のような高速読み出しに２次元メモリ構造は必要がなく、低速１次元バッファでもよい。さらにＬＯＤ（Ｌｅｖｅｌ ｏｆ Ｄｅｔａｉｌ）については、衝突箇所を厳密に１画素単位で検出が必要であるかどうかの問題がある。本発明でもアプリケーションに対応した解像度対コストの最適化を考慮すると、Ｃｕｂｅ面静体情報としてはパターンサイズを表示解像度の１／４から１／１６程度とすることで、Ｃｕｂｅ面情報のメモリコストは大幅に削減可能となる。
【０１９】
以上から本発明は、物体間の衝突を検出する手段として、検出対象となる映像表示空間を取り囲む６面体を定義し、それぞれの面の外部から空間内部を見た空間内部の静止物体を６面のそれぞれに投影し、投影された物体の有無フラグ、識別子、Ｚ値、法線をそれぞれ画像情報として６面分レンダリング前に生成・記憶する手段と、映像を表示するレンダリング段階において、動体の内挿補間時に内挿補間点を６面それぞれの座標系に変換して、前記６面内にある静体のフラグ、識別子、Ｚ値、法線を読み出し、内挿補間点のオーバラップの有無や、その点での静止物体の識別子やＺ値から内挿補間点の衝突を判定する手段と、動く物体の方向や法線、また衝突される物体のそれぞれの法線から、衝突するそれぞれの物体の衝突後の動きを求めるための情報をＡＰに出力する手段のそれぞれからなる可視化衝突検出回路となる。
【発明の効果】
【０２０】
本発明により、コンピュータグラフィックスにおける物体間の衝突を、アプリケーションプロセッサ側のソフトウエアではなく、レンダラーのハードウエアあるいは組込ソフトウエアにより検出することで、アプリケーションプロセッサの演算負荷が低減し、描画の高速化が可能となり、実時間描画システムに有効となる。
【発明を実施するための最良の形態】
【０２１】
本発明の回路はグラフィックスＬＳＩに実装するか、ＩＰ（Ｉｎｔｅｌｌｉｇｅｎｔ Ｐｒｏｐｅｒｔｙ）としての形態で実施される。
【実施例】
【０２２】
以下、本発明の実施例を説明する。図１に本発明に係わるＣｕｂｅを示す。図１ＡではＣｕｂｅの６面をそれぞれ前面、後面、右面、左面、上面、下面と定義する。Ｃｕｂｅ面に投影される画像は、それぞれの面の外側から矢印で示す方向に内部を見た内部物体の画像であり、これら画像情報をそれぞれ記憶する。この画像は面に垂直な並行投影図とし、それぞれの面に最も近い物体の画素を隠面消去で描画する。またＣｕｂｅのそれぞれの面を平面上に展開すると図１Ｂの関係となる。本発明では、画像情報は色情報ではなく投影された物体の有無フラグ、識別子、Ｚ値、法線となる。
【０２３】
図２は本発明に係わる静止物体と動く物体との、Ｃｕｂｅ面２０における位置関係（６面図）を示したものである。図２Ａで灰色の球体２１は、すでにＣｕｂｅに記憶された静体、黒い小球体２２は動体を示す。球体２２はＣｕｂｅ面に描画した図形ではなく、レンダリング時の内挿点位置を示す。Ｃｕｂｅ上面の白い小球体は球体２２が物体（図では２１）の背後に位置することを示す。また図２Ａでは、静止物体２１と動体２２以外には物体がない状態となる。図２Ａにおいて全ての面で静止物体２１と動体２２の一部がオーバーラップしている。オーバーラップとはｘｙ座標軸上の重なりを意味するものとする。本発明の衝突の検出手順は以下となる。
動体２２の内挿補間毎に補間点をＣｕｂｅ６面の座標系に変換し、それぞれの面から静体の有無を示すフラグおよび識別子を読む。全ての面の識別子が同一で且つ、全ての面で動体２２がオーバーラップしていれば動体２２は静体２１と衝突しているとする。内挿点がワールド座標系で与えられている場合は、Ｃｕｂｅ６面の座標変換は簡素化される。
【０２４】
一つの面、例えばＣｕｂｅ下面において直交する４面、すなわち上面を除く全ての面で物体２２の内挿点が同じ識別子を持つ静体とそれぞれオーバーラップしている場合も衝突と見なすことが出来る。
一方、それぞれの対面する面（上下面、左右面あるいは前後面のいずれか）に対し、動体の内挿点のＺ値と、静体のＺ値とを比較する。対面する面の双方で物体２２の内挿点が、同一識別子となる静体２１で共に後方に位置した場合は内挿点は物体２１の内部の点と見なすことができ、衝突状態と判断される。
図２Ｂは物体２２と物体２１の別の関係図を示す。前記衝突判断の方法の一つとして、Ｚ値を用いない方法によれば衝突に該当しない。Ｚ値を用いる方法では、図２Ｂにおいて対面するＺ値の比較結果で物体２２が物体２１の遠方に共に位置しない。例えば後面では物体２２は物体２１の背後に位置するが、後面に対面する前面において物体２２は物体２１の前方に位置し、条件を満たさない。他の面では物体２１と物体２２とはオーバーラップをしている物体がない。この結果動体２２は衝突していないと判断できる。
【０２５】
図３は本発明に係わる遮蔽物体がある場合の関係を示す。図３ＡにおいてＣｕｂｅ面３０に記憶された静体は灰色球体３１と３角平面体３３で、動体（黒丸）を３２とする。動体３２の図形は前記同様に、Ｃｕｂｅ面に記憶されているのではなく静体との位置関係を示す。図３Ａにおいて、それぞれの物体はＣｕｂｅ前面を基準に調べれば、最も手前に３角形体３３があり、その背後に動く物体３２が、さらにその後方に球体３１がある。動体３２は静体３３とオーバーラップする。前面と直交する他の４面を調べると、上下、左右面ではいずれも３角形体３３と同一識別子をもつ物体とのオーバーラップがない。よって静体３３とは衝突はないものと判断される。また対面に位置する後面では、動体３２は３角形体３３とオーバーラップしている。しかしここではＺ値比較の結果、３角形体３３の手前に位置し衝突の条件を満たさない。
さらに後面では、動体３２は静体３１とオーバーラップする点があり、この点での識別子は３１となる。後面と直交する４面は左右、上下であるが、これらには３１と同一識別子でオーバーラップする面はない。よって動体３２は衝突する物体はないと判断される。
【０２６】
一方、図３Ｂでは図３Ａと同様に動体３２はＣｕｂｅ前面で、静体３３とオーバーラップしており、動体３２は３３の背後に位置する。読みだされる識別子は３角形体３３となる。次にこの面と直交する４面とテストすると、３角形体３３の識別子をもつ物体とのオーバーラップは他に検出されない。一方、Ｃｕｂｅ後面では静体３１とオーバーラップし、静体３１に対してＣｕｂｅ後面に直交する４面をテストする。動く物体３２の内挿点がこれら４面にある物体３１とすべてオーバーラップしていることが判定でき動体３２は、静体３１と衝突していると判断できる。これは左右あるいは上下のＣｕｂｅ対面でのテスト（それぞれの面で同一識別子をもち、且つ動体は背後に位置する）によっても検出できる。
【０２７】
図４は本発明に係る遮蔽物体に囲まれた場合のＣｕｂｅ面４０を示す。遮蔽物体４１は底面と前面のない立方体形状とする。遮蔽物体４１と、灰色球体４２は静体とし、動体４３が内挿補間されている。前面で動体４３は静体４２とオーバーラップしている。前面と直交する４面を調べると、動体４３は上面、左右面はいずれもＣｕｂｅ前面とは異なる識別子をもつ静体４１とのオーバーラップであり、静体４２の識別子と同じものは下面のみとなる。しかし動体４３は、上面、左右面でオーバーラップする静体４１に対し全て背後となる。Ｚ値との比較により、動体とオーバーラップする同一識別子をもつものが２つ以上あり、その位置はその識別子の物体の背後に位置し（図では４２）、且つ、それ以外の識別子をもつ物体（図では４１）とのオーバーラップにおいて、それらとは全て背後に位置している場合は衝突と見なす。一方、静体４１と動体４３との関係で、Ｃｕｂｅ後面を基にテストをした場合、動体４３は静体４１の背面にあり、それと対面するＣｕｂｅ前面、あるいはＣｕｂｅ後面に直交する４面に対してＺ値テストを行うと、動体４３はいずれか（前面あるいは下面）で静体４１の前方となり、衝突の条件を満たさない。一つでも同一識別子をもつ静止物体上で動体のＺ値が手前にあるとすれば、その識別子をもつ物体との衝突と見なさない。
【０２８】
本発明では、動体とオーバーラップする物体全てが同一識別子をもっており、また動体が全て、その背後に位置する場合、すなわち静止物体の内部に動体が位置する場合は衝突と見なしている。よって内部が空洞で動体がその中に浮かんで位置する場合は、衝突が内部で生じていなくても衝突と見なされる。このような幾何学的関係においては可視化方式であるかぎり対応はできない。一方、図４において静体４１は底面もあるとするとＣｕｂｅ下面の動体は静体４１の背後となり動体４３の黒丸は白丸となる。よって静体４２と動体４３の関係を示す面情報はＣｕｂｅ前面のみとなる。ここで動体４３を内挿補間する過程で動体４３のＺ値が最も手前に位置（可視化可能な位置）する一部の画素を有し、また一部の画素が物体４２の背後に移動する関係（あるいはその逆でも同じ）となった場合は、動体４３の一部が静体４２にのめり入り込んでいることを意味する。この結果物体４２と４３は衝突と見なすことができる。
【０２９】
図５は本発明の衝突検出システム図を示す。Ｃｕｂｅそれぞれの面から見た静止物体の投影画像情報は２次元のパターンとしてメモリ５２の０−５に予め記憶される。これら情報は、面に最も近い物体の識別子ＩＤ０−５、Ｚ値Ｚｄ０−５、面法線Ｎｄ０−５および静止物体有無フラグｆｄ０−５のそれぞれである。但し、面法線は２次元パターンでなくてもよい。
物体は通常、多数のポリゴンで構成されている。またポリゴンは頂点座標値列でデータ化されている。このポリゴン列から物体の映像を描画するために、まずポリゴン内部を塗りつぶすための内挿補間回路５０にポリゴン頂点列を与える。内挿補間回路５０ではポリゴン内部の内挿点座標値Ｘｓ，Ｙｓ，Ｚｓおよび面法線を順次、またＩＤｓは物体あるいはポリゴン毎に１度出力する。この座標値は視点座標系で求められており、この位置をＣｕｂｅ６面座標系のそれぞれへ座標変換回路５１で座標変換する。回路５１ではメモリ５２の６面のそれぞれのＸＹアドレスＸｄ０−５，Ｙｄ０−５を出力する。これらのアドレスでメモリ５２からは、メモリに記憶されている前記識別子ＩＤｄ０−５、Ｚ値Ｚｄ０−５、面法線Ｎｄ０−５および静止物体有無フラグｆｄ０−５を読みだす。ポリゴンの頂点座標値が視点座標系だけでなく、ワールド座標系の両方で定義し両者を同時に回路５０で内挿補間すれば座標変換回路５１ではＣｕｂｅ６面座標系変換は極めて簡素化される。これら情報は次に衝突検出回路５３に加わる。回路５３には座標変換回路５１で求めた内挿補間点のＣｕｂｅそれぞれの面に対応するＺ値Ｚ０−５も与えられる。衝突検出回路ではこれらの情報を基に［０２３］から［０２８］までの条件に対応した衝突の検出処理を行う。
【０３０】
前記図５の衝突検出回路５３の内部構成を図６に示す。前記図５のメモリ５２から読みだされたそれぞれ６組の識別子ＩＤｄ０−５、Ｚ値Ｚｄ０−５、面法線Ｎｄ０−５および静止物体有無フラグｆｄ０−５の内、有無フラグｆｄ０−５と識別子ＩＤｄ０−５は、有無フラグ・識別子選択回路６０に加えられる。ここでは有無フラグが立っている、すなわち静体が存在するメモリ５２の面０−５の識別子ＩＤｄ０−５をそれぞれ選択する。回路６０では０−５面それぞれに対応するレジスタを設け、ここに識別子と有効ビットを記憶する。有無フラグがなければレジスタには無効ビットがセットされる。前記図５において内挿点から６面座標に変換した座標値のうちＺ値Ｚ０−５と、メモリ５２から読みだしたＺ値Ｚｄ０−５はＺ値比較回路６１に与えられる。ここではＺ０−５がＺｄ０−５の手前にあるか、背後にあるかの差分符号をそれぞれ求め、その結果を衝突ＩＤ検出回路６２に出力する。回路６２では、前記選択回路６０での結果を受けて、有効ビットが立っている識別子のみを選択し、同一識別子同士で、また回路６１からのＺ値比較結果と合せて、衝突の有無を前記［０２４］から［０２８］のそれぞれの条件に沿って判定する。この判定には同一識別子が存在する面番号と、その面に対応するＺ値比較符号を判定テーブルに加える等の手段で容易に判断できる。すなわち、最大取りうる組み合わせとして、面情報が６ビット（このうち有効で且つ同一識別子のある面を１ビットとする）であり、またＺ値比較結果は６ビットであるため、組み合わせとして合計１２ビットとなる。テーブルは４０９６のアドレスと１ビットの衝突を示す出力をもつ容量でよい。この出力でテスト中の識別子を回路６２から出力する。同時にマルチプレクサ回路６３では、テスト中の識別子をもつ面番号の一つを回路６２から受け、それぞれの面の６種類の静止物体の衝突点の面法線から、所定の面の面法線Ｎｄを選択する。また内挿点の座標値ＸＹＺ、面法線Ｎｓ、物体の動き方向ベクトルＭｓを、マルチプレクサ回路を通して出力する。回路６２において、複数の識別子が存在した場合は、逐次それぞれの識別子毎に６面分を走査し、同一識別子を検出して、その面のフラグを立て、前記同様にテーブルに加えることで対応できる。
【０３１】
一方、識別子とＺ値判定からだけでは衝突の検出ができない場合がある。前記［０１５］の条件においては、動く物体を内挿補間している１画素前の情報（識別子とＺの差分結果）を６面それぞれに対応したバッファを用いて記憶し、Ｚ値が同一識別子上で前面から背後に変化した時点を検出する。図６の履歴回路６４では静止物体有無フラグ、識別子、Ｚ差分結果情報を受ける回路６２から、内挿補間毎に６面それぞれの静止物体有無フラグ、Ｚ値差分符号と、識別子を記憶し、新しく補間されて回路６２に入力し、さらに回路６４に送出される前記情報を比較し、動く物体の画素点が同一静止物体の前面から内部に移った場合を衝突として回路６２に信号を送り、その時点での前記［０２９］に記載の識別子や法線等を出力する。
【０３２】
一方、静止物体は予め表示のための描画を行う前に画像情報として記憶したが、動く物体が複数存在する場合は、表示描画段階で静止物体同様の６面Ｃｕｂｅを別途作成し、ここに動体をそれぞれの面に投影して記憶する。このため本発明では動体の６面Ｃｕｂｅ画像情報は静止物体の情報とは異なりフレーム毎にリフレッシュし再描画する。回路としては図５のメモリ５２にテンポラリなメモリが増設されることになり、衝突検出回路への出力信号も増加するが、衝突検出方式は静止物体との衝突と変わらず、何れか一方、あるいは双方で衝突が検出されれば、所定の情報を出力する。
以上のそれぞれの手段とから、本発明では物体間を６面から視覚的に捉え衝突の検出が可能な範囲で、衝突を検出するハードウエア化に適した方式となる。
【産業上の利用可能性】
【０３３】
本発明の回路はＩＰ（Ｉｎｔｅｌｌｉｇｅｎｔ ｐｒｏｐｅｒｔｙ）として提供したり、グラフィックスプロセッサＬＳＩに実装されることで、ＣＧ映像製作やアムーズメントシステムに利用される。
【図面の簡単な説明】
【０３４】
【図１】「本発明に係わる６面立方体Ａとその平面展開図Ｂを示す。」
【図２】「本発明に係わる静止物体と動体との衝突Ａ・非衝突Ｂの幾何学的関係を示す。」
【図３】「本発明に係わる複数の静止物体間での非衝突Ａ・衝突Ｂの幾何学的関係を示す。」
【図４】「本発明に係わる遮蔽物体内での衝突の幾何学的関係を示す。」
【図５】「本発明の衝突検出システムの回路構成を示す。」
【図６】「本発明の衝突検出回路を示す。」
【符号の説明】
図１
１０ 立方体
１１ 立方体平面展開図
図２
２０ 立方体平面展開図
２１ 静止球状物体
２２ 動体
図３
３０ 立方体平面展開図
３１ 静止球状物体
３２ 動体
３３ 静止３角形状物体
図４
４０ 立方体平面展開図
４１ 遮蔽物体
４２ 静止球状物体
４３ 動体
図５
５０ 内挿補間回路
５１ 座標変換回路
５２ 立方体６面画像情報メモリ
５３ 衝突検出回路
図６
６０ 有効フラグ・識別子選択回路
６１ Ｚ値比較回路
６２ 衝突識別子検出回路
６３ マルチプレクサ
６４ 履歴回路
【技術分野】
【００１】
この発明は コンピュータグラフィックス技術において物体間の衝突を検出するための手段と、それを実現するための回路の実装に関する。
【背景技術】
【００２】
コンピュータグラフィックスのアプリケーションには、物体同士の衝突を含むアニメーションが多く制作されている。従来から衝突検出は、アプリケーションプロセッサ（以下ＡＰという）側のプログラミングによるバウンダリーボックスや物体のツリー構造法に基づき高速処理が図られてきた。実時間描画が必要なゲーム等のアニメーションでは、これら衝突検出の計算負荷は極めて大きい。このためＣＧ映像の現実感や実時間描画を得るためには、描画量の増加と物理モデル等の複雑系処理等が必須であり、ＡＰの負荷は今後一層深刻となる。正確な衝突検出をＡＰ側のソフトウエアで対応する限り、高速化とデータ量削減との相反する問題を解決しなければならない問題をこれまでに抱えていた。
【発明の開示】
【発明が解決しようとする課題】
【００３】
本発明はＡＰに実装されるプログラムを用いて物体間の衝突を検出するのではなく、ピクセルシェーダーあるいはラスタライザーと言われるレンダラー側のハードウエアで衝突を検出する。ＡＰ側から衝突検出処理を無くし、ＡＰは一般描画と同じ物体プリミティブ（ポリゴン）をレンダラーに出力するのみとし、ハードウエアによって衝突検出を行うことでＡＰの負荷の軽減と描画の高速化を図ることが本発明の課題である。
【課題を解決するための手段】
【００４】
レンダラーには通常、ポリゴン描画、テキスチャマッピング、環境マッピング、照明のためのシェーダー等がハードウエア実装されている。本発明はこれらグラフィックスプロセッサが具備する既存の機能群と同化した構造で物体間衝突検出回路を導入する。
【００５】
視覚的に物体が衝突しているか否かは、衝突箇所に遮蔽物体がなければ複数の視角から物体を眺めることで認知できる。このアルゴリズムとして描画空間全体を取り囲む６面体（立方体あるいは直方体のいずれかで、以下Ｃｕｂｅという）を設定し、これら６面からＣｕｂｅ内部を見て、動く物体（以下動体という）と他の物体（以下静体という）との接触の可否を検査することで衝突が認知できる。このため描画空間全体を仮想的にＣｕｂｅで囲み、Ｃｕｂｅのそれぞれの面にはＣｕｂｅ外部から内部を投影した画像を写像し、この６面分の写像図をＣｕｂｅパターンとして保存する。衝突箇所が完全に遮蔽された空間内でない限り、複数の面から見て、動体と静体とが重なり合っていれば衝突と見なすことができる。これは人間が視覚的に物体衝突を認知するプロセスと同じである。
【００６】
前記Ｃｕｂｅそれぞれの６面にＣｕｂｅ内部の映像を投影する手段として本発明では、６面それぞれに直交する座標軸上から並行投影でＣｕｂｅ内部画像を、隠面消去法を用い６面それぞれに描画する。投影中心がＣｕｂｅの内部と外部、あるいは透視投影と並行投影の違いを除くと、この方法はレンダリング前に予め作成される環境マッピング技術の環境Ｃｕｂｅ生成法と類似する。
【００７】
環境マッピング同様に動く物体が生じれば、その都度Ｃｕｂｅパターンは再生成しなければならない。これは６面分の描画となり負荷が大きい。本発明ではこれを避けるため全ての描画物体を、動体と静体とにそれぞれ分け、静体のみをＣｕｂｅ６面それぞれに予めパターンとして作成する。画像表示段階では、静体を先に、次に動体をレンダリングする。動体のポリゴンを内挿補間する段階で、補間点が静体と交差するか否かを、Ｃｕｂｅ６面それぞれのパターン（以下画像情報という）と比較し判定する。この判定には動体の内挿補間点を６面それぞれの座標系に変換し、面の画像と内挿補間点がオーバーラップするか否かのテストを行う。
【００８】
遮蔽物体がなければＣｕｂｅ画像情報と内挿補間点とのｘｙ座標の重なりテストのみであり、画像情報として記憶する情報は、環境マッピングのような色情報は必要ない。記憶される情報は画素あたり１ビットの画像の有無を示すフラグと静体の識別子のみとなる。衝突が検出された場合ＡＰに戻す値は、動体と静体それぞれの識別子と、衝突点の３次元座標値となる。これにより、衝突物体名と位置がＡＰ側で判断できる。動体と静体とを分離することによって、大半を占める静体のＣｕｂｅへの書き込みは前処理１回のみとなる。
【００９】
動体が複数存在した場合、動体間の衝突の検出も必要となる。本発明は複数の動体がある場合、動体専用の６面Ｃｕｂｅを別途用意し、内挿補間時に衝突検出処理と並行してこのＣｕｂｅに描画する。静体と動体Ｃｕｂｅそれぞれをテストすることで静体の再描画を不要とする。
【０１０】
動体のＣｕｂｅを定義する場合、複数の動体を纏めて１組のＣｕｂｅに書くか、動体毎にそれぞれ専用のＣｕｂｅを作成するかは同時に動く物体数あるいはハードウエア・コストに関係する。動体数が多く、一時的に動くものと、常時動くものがある場合には、それぞれの物体毎にＣｕｂｅを作成することによって効率を図ることができる。この場合は動体のためのＣｕｂｅは動体を取り囲む空間サイズでよい。
【０１１】
静体Ｃｕｂｅ画像情報を前処理で求めておくことは本発明の高速化の条件である。表示（レンダリング）段階では静体、動体のいずれの描画順でもよいが、静体を描画した後に動体を描画し、この動体描画時にのみ衝突検出処理を行うことで高速化が可能となる。実時間アニメーションでは１／３０秒あるいは１／６０秒以内で１フレームを描画するため、フレーム内で検出が可能となればよい。本発明では映像の描画中に、内挿補間処理の一つとして衝突を検出し、これをＡＰに戻すため（衝突が生じてから）１フレーム分の遅れをもって、ＡＰは次の映像を決定することになる。
【０１２】
レンダリング時の座標系は任意の視野方向をもつ視点座標系である。内挿補間点のＣｕｂｅ６面の画像情報とのオーバーラップ・テストは、内挿補間点座標値をＣｕｂｅ面それぞれの座標系に変換する。視点方向が任意角の場合は３次元回転が必要となる。内挿補間点毎の回転計算の負荷を避けるため、本発明ではＣｕｂｅをワールド座標で定義しＣｕｂｅの６面はそれぞれｘｙ、ｙｚ、ｘｚ面と平行とすることで回転計算を削減する。
【０１３】
また本発明では、動体のポリゴン頂点に視点系座標値と共に、ワールド座標値を付加し、これを同時にレンダリングし、視点座標値は描画に、一方ワールド座標値はＣｕｂｅ座標との衝突検出に用いることで面毎の回転計算処理を省き置換処理で対応する。
【０１４】
６面のいずれから見ても視点との間に遮蔽物がない場合は、互いに直交するＣｕｂｅ３面以上で交差していれば衝突の検出ができる。遮蔽物がある場合は追加情報が必要となる。本発明では複雑な形状同士の衝突を検出する手段として、静体のＺ値（Ｃｕｂｅ面からの距離）、静体の識別子および静体画像の有無を示すフラグをそれぞれＣｕｂｅ画像情報として記憶する。衝突判定は内挿補間点が、全てのＣｕｂｅ面で同一の識別子である静体とオーバーラップしている場合はその静体と衝突となる。また対面する面同士で動体が同一の識別子をもつ静体とオーバーラップし、いずれもＺ値比較において静体の後方に位置する場合も衝突と見なすことができる。Ｃｕｂｅ面によっては複数の物体が遮蔽する場合があり、内挿補間点でＣｕｂｅ面のそれぞれの識別子が異なる場合がある。この場合は動体のＺ値とオーバーラップする静体のＺ値と比較し、動体が静体に対してＣｕｂｅ面（手前）側に位置する場合は、静体とは衝突がないとする。一方、動体のＺ値が静体の内側（遠方）に位置するＣｕｂｅ面とそれぞれ直交する他のＣｕｂｅ４面でも動体が同一識別子（これを識別子Ａとする）をもつ物体の遠方でオーバーラップしている場合は衝突。さらに、多数の面で同一識別子Ａと遠方でオーバーラップするものの識別子の異なる物体（以下遮蔽体という）ともＣｕｂｅ面のいずれかでオーバーラップしていた場合、動体と遮蔽体とのそれぞれのＺ値を比較し、動体のＺ値が遮蔽体よりＣｕｂｅ面から遠方にある場合は、識別子Ａの物体とは衝突、手前にある場合は衝突していないものとする。
【０１５】
動体描画のリフレッショは映像表示のための走査フレーム単位で行われる。動体が静体（描画が終了した動体も静体と定義する）と衝突する場合は、Ｃｕｂｅ面から見て動体の一部が静体と交差した状態となる。動体が極めて高速に移動し１／６０秒以内で静体を通り抜ける場合は通常衝突検出不能となるが、互いの物体が交差状態にあれば動体と静体のＺ値とを動体の内挿補間時で画素毎に差分すれば、ある箇所で差分符号は背後から手前あるいはその逆に変化する。この変化時を捕えて衝突と見なすことができる。このために、動体の内挿補間段階で前記静体のＺ値および識別子を読み出し、内挿補間Ｚ値と前記読み出したＺ値をそれぞれ比較する。
【０１６】
衝突検出によるＡＰへの戻し情報として［００８］では、レンダラーは衝突それぞれの物体識別子と衝突位置を返すものとした。一方、衝突によって跳ね返りや静体が衝突によって移動する場合には、動体の動き方向、動体および静体それぞれの衝突点の面法線、質量や弾性等の物体の属性が必要となる。物体の速度や属性は識別子によってそれを所有し、制御しているＡＰ側で高速に判断できるが、衝突時点の動き方向や面法線はレンダラー側あるいはグラフィックス・エンジン内の中間処理段階で時系列的変化を伴って生成されている場合があり、これをＡＰ側で求めようとすると、衝突点から形状モデルの幾何学的展開が必要となる。この負荷は極めて大きい。本発明では、識別子や衝突位置に加えて、衝突点の動体および静体の面法線および動体の進行方向ベクトルをＡＰに返す。
【０１７】
前記手段として、動体の面法線は通常のシステムで多角形頂点データあるいは法線マップとして内挿補間処理に含まれており衝突検出段階で衝突点での面法線を得ることができる。また動体の動き方向は、これに基づきエンジン側で動体の次の座標値が決定されており、フレームサイクル毎のアップデートな情報として、レンダラーに動きベクトルを出力すれば、これをレンダラー側からＡＰに返すことができる。一方、静体の衝突点の面法線は、予め静体を記憶したＣｕｂｅ面情報として追加記憶する。以上から本発明ではＣｕｂｅ画像情報としてフラグ、識別子、ｚ座標値、面法線を記憶する手段をもつ。
【０１８】
静体の面法線は衝突の際にのみ必要であることから、Ｃｕｂｅ画像情報のような高速読み出しに２次元メモリ構造は必要がなく、低速１次元バッファでもよい。さらにＬＯＤ（Ｌｅｖｅｌ ｏｆ Ｄｅｔａｉｌ）については、衝突箇所を厳密に１画素単位で検出が必要であるかどうかの問題がある。本発明でもアプリケーションに対応した解像度対コストの最適化を考慮すると、Ｃｕｂｅ面静体情報としてはパターンサイズを表示解像度の１／４から１／１６程度とすることで、Ｃｕｂｅ面情報のメモリコストは大幅に削減可能となる。
【０１９】
以上から本発明は、物体間の衝突を検出する手段として、検出対象となる映像表示空間を取り囲む６面体を定義し、それぞれの面の外部から空間内部を見た空間内部の静止物体を６面のそれぞれに投影し、投影された物体の有無フラグ、識別子、Ｚ値、法線をそれぞれ画像情報として６面分レンダリング前に生成・記憶する手段と、映像を表示するレンダリング段階において、動体の内挿補間時に内挿補間点を６面それぞれの座標系に変換して、前記６面内にある静体のフラグ、識別子、Ｚ値、法線を読み出し、内挿補間点のオーバラップの有無や、その点での静止物体の識別子やＺ値から内挿補間点の衝突を判定する手段と、動く物体の方向や法線、また衝突される物体のそれぞれの法線から、衝突するそれぞれの物体の衝突後の動きを求めるための情報をＡＰに出力する手段のそれぞれからなる可視化衝突検出回路となる。
【発明の効果】
【０２０】
本発明により、コンピュータグラフィックスにおける物体間の衝突を、アプリケーションプロセッサ側のソフトウエアではなく、レンダラーのハードウエアあるいは組込ソフトウエアにより検出することで、アプリケーションプロセッサの演算負荷が低減し、描画の高速化が可能となり、実時間描画システムに有効となる。
【発明を実施するための最良の形態】
【０２１】
本発明の回路はグラフィックスＬＳＩに実装するか、ＩＰ（Ｉｎｔｅｌｌｉｇｅｎｔ Ｐｒｏｐｅｒｔｙ）としての形態で実施される。
【実施例】
【０２２】
以下、本発明の実施例を説明する。図１に本発明に係わるＣｕｂｅを示す。図１ＡではＣｕｂｅの６面をそれぞれ前面、後面、右面、左面、上面、下面と定義する。Ｃｕｂｅ面に投影される画像は、それぞれの面の外側から矢印で示す方向に内部を見た内部物体の画像であり、これら画像情報をそれぞれ記憶する。この画像は面に垂直な並行投影図とし、それぞれの面に最も近い物体の画素を隠面消去で描画する。またＣｕｂｅのそれぞれの面を平面上に展開すると図１Ｂの関係となる。本発明では、画像情報は色情報ではなく投影された物体の有無フラグ、識別子、Ｚ値、法線となる。
【０２３】
図２は本発明に係わる静止物体と動く物体との、Ｃｕｂｅ面２０における位置関係（６面図）を示したものである。図２Ａで灰色の球体２１は、すでにＣｕｂｅに記憶された静体、黒い小球体２２は動体を示す。球体２２はＣｕｂｅ面に描画した図形ではなく、レンダリング時の内挿点位置を示す。Ｃｕｂｅ上面の白い小球体は球体２２が物体（図では２１）の背後に位置することを示す。また図２Ａでは、静止物体２１と動体２２以外には物体がない状態となる。図２Ａにおいて全ての面で静止物体２１と動体２２の一部がオーバーラップしている。オーバーラップとはｘｙ座標軸上の重なりを意味するものとする。本発明の衝突の検出手順は以下となる。
動体２２の内挿補間毎に補間点をＣｕｂｅ６面の座標系に変換し、それぞれの面から静体の有無を示すフラグおよび識別子を読む。全ての面の識別子が同一で且つ、全ての面で動体２２がオーバーラップしていれば動体２２は静体２１と衝突しているとする。内挿点がワールド座標系で与えられている場合は、Ｃｕｂｅ６面の座標変換は簡素化される。
【０２４】
一つの面、例えばＣｕｂｅ下面において直交する４面、すなわち上面を除く全ての面で物体２２の内挿点が同じ識別子を持つ静体とそれぞれオーバーラップしている場合も衝突と見なすことが出来る。
一方、それぞれの対面する面（上下面、左右面あるいは前後面のいずれか）に対し、動体の内挿点のＺ値と、静体のＺ値とを比較する。対面する面の双方で物体２２の内挿点が、同一識別子となる静体２１で共に後方に位置した場合は内挿点は物体２１の内部の点と見なすことができ、衝突状態と判断される。
図２Ｂは物体２２と物体２１の別の関係図を示す。前記衝突判断の方法の一つとして、Ｚ値を用いない方法によれば衝突に該当しない。Ｚ値を用いる方法では、図２Ｂにおいて対面するＺ値の比較結果で物体２２が物体２１の遠方に共に位置しない。例えば後面では物体２２は物体２１の背後に位置するが、後面に対面する前面において物体２２は物体２１の前方に位置し、条件を満たさない。他の面では物体２１と物体２２とはオーバーラップをしている物体がない。この結果動体２２は衝突していないと判断できる。
【０２５】
図３は本発明に係わる遮蔽物体がある場合の関係を示す。図３ＡにおいてＣｕｂｅ面３０に記憶された静体は灰色球体３１と３角平面体３３で、動体（黒丸）を３２とする。動体３２の図形は前記同様に、Ｃｕｂｅ面に記憶されているのではなく静体との位置関係を示す。図３Ａにおいて、それぞれの物体はＣｕｂｅ前面を基準に調べれば、最も手前に３角形体３３があり、その背後に動く物体３２が、さらにその後方に球体３１がある。動体３２は静体３３とオーバーラップする。前面と直交する他の４面を調べると、上下、左右面ではいずれも３角形体３３と同一識別子をもつ物体とのオーバーラップがない。よって静体３３とは衝突はないものと判断される。また対面に位置する後面では、動体３２は３角形体３３とオーバーラップしている。しかしここではＺ値比較の結果、３角形体３３の手前に位置し衝突の条件を満たさない。
さらに後面では、動体３２は静体３１とオーバーラップする点があり、この点での識別子は３１となる。後面と直交する４面は左右、上下であるが、これらには３１と同一識別子でオーバーラップする面はない。よって動体３２は衝突する物体はないと判断される。
【０２６】
一方、図３Ｂでは図３Ａと同様に動体３２はＣｕｂｅ前面で、静体３３とオーバーラップしており、動体３２は３３の背後に位置する。読みだされる識別子は３角形体３３となる。次にこの面と直交する４面とテストすると、３角形体３３の識別子をもつ物体とのオーバーラップは他に検出されない。一方、Ｃｕｂｅ後面では静体３１とオーバーラップし、静体３１に対してＣｕｂｅ後面に直交する４面をテストする。動く物体３２の内挿点がこれら４面にある物体３１とすべてオーバーラップしていることが判定でき動体３２は、静体３１と衝突していると判断できる。これは左右あるいは上下のＣｕｂｅ対面でのテスト（それぞれの面で同一識別子をもち、且つ動体は背後に位置する）によっても検出できる。
【０２７】
図４は本発明に係る遮蔽物体に囲まれた場合のＣｕｂｅ面４０を示す。遮蔽物体４１は底面と前面のない立方体形状とする。遮蔽物体４１と、灰色球体４２は静体とし、動体４３が内挿補間されている。前面で動体４３は静体４２とオーバーラップしている。前面と直交する４面を調べると、動体４３は上面、左右面はいずれもＣｕｂｅ前面とは異なる識別子をもつ静体４１とのオーバーラップであり、静体４２の識別子と同じものは下面のみとなる。しかし動体４３は、上面、左右面でオーバーラップする静体４１に対し全て背後となる。Ｚ値との比較により、動体とオーバーラップする同一識別子をもつものが２つ以上あり、その位置はその識別子の物体の背後に位置し（図では４２）、且つ、それ以外の識別子をもつ物体（図では４１）とのオーバーラップにおいて、それらとは全て背後に位置している場合は衝突と見なす。一方、静体４１と動体４３との関係で、Ｃｕｂｅ後面を基にテストをした場合、動体４３は静体４１の背面にあり、それと対面するＣｕｂｅ前面、あるいはＣｕｂｅ後面に直交する４面に対してＺ値テストを行うと、動体４３はいずれか（前面あるいは下面）で静体４１の前方となり、衝突の条件を満たさない。一つでも同一識別子をもつ静止物体上で動体のＺ値が手前にあるとすれば、その識別子をもつ物体との衝突と見なさない。
【０２８】
本発明では、動体とオーバーラップする物体全てが同一識別子をもっており、また動体が全て、その背後に位置する場合、すなわち静止物体の内部に動体が位置する場合は衝突と見なしている。よって内部が空洞で動体がその中に浮かんで位置する場合は、衝突が内部で生じていなくても衝突と見なされる。このような幾何学的関係においては可視化方式であるかぎり対応はできない。一方、図４において静体４１は底面もあるとするとＣｕｂｅ下面の動体は静体４１の背後となり動体４３の黒丸は白丸となる。よって静体４２と動体４３の関係を示す面情報はＣｕｂｅ前面のみとなる。ここで動体４３を内挿補間する過程で動体４３のＺ値が最も手前に位置（可視化可能な位置）する一部の画素を有し、また一部の画素が物体４２の背後に移動する関係（あるいはその逆でも同じ）となった場合は、動体４３の一部が静体４２にのめり入り込んでいることを意味する。この結果物体４２と４３は衝突と見なすことができる。
【０２９】
図５は本発明の衝突検出システム図を示す。Ｃｕｂｅそれぞれの面から見た静止物体の投影画像情報は２次元のパターンとしてメモリ５２の０−５に予め記憶される。これら情報は、面に最も近い物体の識別子ＩＤ０−５、Ｚ値Ｚｄ０−５、面法線Ｎｄ０−５および静止物体有無フラグｆｄ０−５のそれぞれである。但し、面法線は２次元パターンでなくてもよい。
物体は通常、多数のポリゴンで構成されている。またポリゴンは頂点座標値列でデータ化されている。このポリゴン列から物体の映像を描画するために、まずポリゴン内部を塗りつぶすための内挿補間回路５０にポリゴン頂点列を与える。内挿補間回路５０ではポリゴン内部の内挿点座標値Ｘｓ，Ｙｓ，Ｚｓおよび面法線を順次、またＩＤｓは物体あるいはポリゴン毎に１度出力する。この座標値は視点座標系で求められており、この位置をＣｕｂｅ６面座標系のそれぞれへ座標変換回路５１で座標変換する。回路５１ではメモリ５２の６面のそれぞれのＸＹアドレスＸｄ０−５，Ｙｄ０−５を出力する。これらのアドレスでメモリ５２からは、メモリに記憶されている前記識別子ＩＤｄ０−５、Ｚ値Ｚｄ０−５、面法線Ｎｄ０−５および静止物体有無フラグｆｄ０−５を読みだす。ポリゴンの頂点座標値が視点座標系だけでなく、ワールド座標系の両方で定義し両者を同時に回路５０で内挿補間すれば座標変換回路５１ではＣｕｂｅ６面座標系変換は極めて簡素化される。これら情報は次に衝突検出回路５３に加わる。回路５３には座標変換回路５１で求めた内挿補間点のＣｕｂｅそれぞれの面に対応するＺ値Ｚ０−５も与えられる。衝突検出回路ではこれらの情報を基に［０２３］から［０２８］までの条件に対応した衝突の検出処理を行う。
【０３０】
前記図５の衝突検出回路５３の内部構成を図６に示す。前記図５のメモリ５２から読みだされたそれぞれ６組の識別子ＩＤｄ０−５、Ｚ値Ｚｄ０−５、面法線Ｎｄ０−５および静止物体有無フラグｆｄ０−５の内、有無フラグｆｄ０−５と識別子ＩＤｄ０−５は、有無フラグ・識別子選択回路６０に加えられる。ここでは有無フラグが立っている、すなわち静体が存在するメモリ５２の面０−５の識別子ＩＤｄ０−５をそれぞれ選択する。回路６０では０−５面それぞれに対応するレジスタを設け、ここに識別子と有効ビットを記憶する。有無フラグがなければレジスタには無効ビットがセットされる。前記図５において内挿点から６面座標に変換した座標値のうちＺ値Ｚ０−５と、メモリ５２から読みだしたＺ値Ｚｄ０−５はＺ値比較回路６１に与えられる。ここではＺ０−５がＺｄ０−５の手前にあるか、背後にあるかの差分符号をそれぞれ求め、その結果を衝突ＩＤ検出回路６２に出力する。回路６２では、前記選択回路６０での結果を受けて、有効ビットが立っている識別子のみを選択し、同一識別子同士で、また回路６１からのＺ値比較結果と合せて、衝突の有無を前記［０２４］から［０２８］のそれぞれの条件に沿って判定する。この判定には同一識別子が存在する面番号と、その面に対応するＺ値比較符号を判定テーブルに加える等の手段で容易に判断できる。すなわち、最大取りうる組み合わせとして、面情報が６ビット（このうち有効で且つ同一識別子のある面を１ビットとする）であり、またＺ値比較結果は６ビットであるため、組み合わせとして合計１２ビットとなる。テーブルは４０９６のアドレスと１ビットの衝突を示す出力をもつ容量でよい。この出力でテスト中の識別子を回路６２から出力する。同時にマルチプレクサ回路６３では、テスト中の識別子をもつ面番号の一つを回路６２から受け、それぞれの面の６種類の静止物体の衝突点の面法線から、所定の面の面法線Ｎｄを選択する。また内挿点の座標値ＸＹＺ、面法線Ｎｓ、物体の動き方向ベクトルＭｓを、マルチプレクサ回路を通して出力する。回路６２において、複数の識別子が存在した場合は、逐次それぞれの識別子毎に６面分を走査し、同一識別子を検出して、その面のフラグを立て、前記同様にテーブルに加えることで対応できる。
【０３１】
一方、識別子とＺ値判定からだけでは衝突の検出ができない場合がある。前記［０１５］の条件においては、動く物体を内挿補間している１画素前の情報（識別子とＺの差分結果）を６面それぞれに対応したバッファを用いて記憶し、Ｚ値が同一識別子上で前面から背後に変化した時点を検出する。図６の履歴回路６４では静止物体有無フラグ、識別子、Ｚ差分結果情報を受ける回路６２から、内挿補間毎に６面それぞれの静止物体有無フラグ、Ｚ値差分符号と、識別子を記憶し、新しく補間されて回路６２に入力し、さらに回路６４に送出される前記情報を比較し、動く物体の画素点が同一静止物体の前面から内部に移った場合を衝突として回路６２に信号を送り、その時点での前記［０２９］に記載の識別子や法線等を出力する。
【０３２】
一方、静止物体は予め表示のための描画を行う前に画像情報として記憶したが、動く物体が複数存在する場合は、表示描画段階で静止物体同様の６面Ｃｕｂｅを別途作成し、ここに動体をそれぞれの面に投影して記憶する。このため本発明では動体の６面Ｃｕｂｅ画像情報は静止物体の情報とは異なりフレーム毎にリフレッシュし再描画する。回路としては図５のメモリ５２にテンポラリなメモリが増設されることになり、衝突検出回路への出力信号も増加するが、衝突検出方式は静止物体との衝突と変わらず、何れか一方、あるいは双方で衝突が検出されれば、所定の情報を出力する。
以上のそれぞれの手段とから、本発明では物体間を６面から視覚的に捉え衝突の検出が可能な範囲で、衝突を検出するハードウエア化に適した方式となる。
【産業上の利用可能性】
【０３３】
本発明の回路はＩＰ（Ｉｎｔｅｌｌｉｇｅｎｔ ｐｒｏｐｅｒｔｙ）として提供したり、グラフィックスプロセッサＬＳＩに実装されることで、ＣＧ映像製作やアムーズメントシステムに利用される。
【図面の簡単な説明】
【０３４】
【図１】「本発明に係わる６面立方体Ａとその平面展開図Ｂを示す。」
【図２】「本発明に係わる静止物体と動体との衝突Ａ・非衝突Ｂの幾何学的関係を示す。」
【図３】「本発明に係わる複数の静止物体間での非衝突Ａ・衝突Ｂの幾何学的関係を示す。」
【図４】「本発明に係わる遮蔽物体内での衝突の幾何学的関係を示す。」
【図５】「本発明の衝突検出システムの回路構成を示す。」
【図６】「本発明の衝突検出回路を示す。」
【符号の説明】
図１
１０ 立方体
１１ 立方体平面展開図
図２
２０ 立方体平面展開図
２１ 静止球状物体
２２ 動体
図３
３０ 立方体平面展開図
３１ 静止球状物体
３２ 動体
３３ 静止３角形状物体
図４
４０ 立方体平面展開図
４１ 遮蔽物体
４２ 静止球状物体
４３ 動体
図５
５０ 内挿補間回路
５１ 座標変換回路
５２ 立方体６面画像情報メモリ
５３ 衝突検出回路
図６
６０ 有効フラグ・識別子選択回路
６１ Ｚ値比較回路
６２ 衝突識別子検出回路
６３ マルチプレクサ
６４ 履歴回路
【特許請求の範囲】
【請求項１】
コンピュータグラフィックスシステムにおける表示物体の衝突検出回路に関し、図形表示空間を囲む仮想６面体を定義し、前記６面体の外部を視点として前記表示空間内に含まれる静止物体を前記６面体のそれぞれの面に投影する手段と、投影した画像情報には、静止物体の有無フラグ、識別子、面法線、面からの距離のそれぞれとして、これらを予めメモリに記憶する手段と、映像表示のために視点座標系で全ての物体を描画する段階において、静止物体から動きのある物体の順序で描画する手段と、前記動く物体を描画する際に、物体の座標値を視点座標系から前記６面体のそれぞれの面座標系に変換して、前記予め記憶された画像情報のそれぞれを前記メモリから読み出し、動く物体と静止物体との重なり状態を６面体の複数の面で検査して、物体間の重なり条件を基に動く物体と静止物体との衝突の有無を決定する衝突検出回路。
【請求項２】
請求項１の回路において、６面体はワールド座標系で、動く物体のポリゴン頂点列は視点座標値とワールド座標値の両方で定義し、前記ポリゴン頂点列からの内挿補間では前記視点座標値とワールド座標値を共に内挿補間して、内挿補間点のワールド座標値を用いて６面体のそれぞれの面座標系への変換処理を簡素化する手段をもつ衝突検出回路。
【請求項３】
請求項１の回路において、動く物体が複数ある場合、静止物体を記憶したメモリに加えて、動く物体を囲む６面体のメモリを複数組設け、６面それぞれの面を外部から見た、面に投影される動く物体の画像情報を、内挿補間段階で前記複数組からなるそれぞれのメモリに記憶する手段と、前記動く物体の画像情報を物体の有無フラグ、識別子、面法線、面からの距離のそれぞれとする手段と、予め記憶された請求項１の静止物体の画像情報と、前記動く物体の画像情報とを同時に読みだして、それぞれの情報を基に静止物体および動く物体それぞれとの衝突を検出する回路。
【請求項４】
請求項１および３の回路において、動く物体のポリゴンの描画段階において、ポリゴンの識別子を保有し、またポリゴンの表示段階では内挿点毎の座標値と共に面法線を求め、衝突が検出された場合、アプリケーションプロセッサには、衝突検出点座標値、静止物体画像情報から読みだされた識別子と面法線、また動く物体の前記保有する識別子と面法線のそれぞれを出力して、衝突した物体それぞれの識別子、衝突点座標値、および衝突面の面法線をアプリケーションプロセッサに知らせる衝突検出回路。
【請求項５】
請求項１から４までに記載のそれぞれの手段用いたコンピュータグラフィック画像装置。
【請求項１】
コンピュータグラフィックスシステムにおける表示物体の衝突検出回路に関し、図形表示空間を囲む仮想６面体を定義し、前記６面体の外部を視点として前記表示空間内に含まれる静止物体を前記６面体のそれぞれの面に投影する手段と、投影した画像情報には、静止物体の有無フラグ、識別子、面法線、面からの距離のそれぞれとして、これらを予めメモリに記憶する手段と、映像表示のために視点座標系で全ての物体を描画する段階において、静止物体から動きのある物体の順序で描画する手段と、前記動く物体を描画する際に、物体の座標値を視点座標系から前記６面体のそれぞれの面座標系に変換して、前記予め記憶された画像情報のそれぞれを前記メモリから読み出し、動く物体と静止物体との重なり状態を６面体の複数の面で検査して、物体間の重なり条件を基に動く物体と静止物体との衝突の有無を決定する衝突検出回路。
【請求項２】
請求項１の回路において、６面体はワールド座標系で、動く物体のポリゴン頂点列は視点座標値とワールド座標値の両方で定義し、前記ポリゴン頂点列からの内挿補間では前記視点座標値とワールド座標値を共に内挿補間して、内挿補間点のワールド座標値を用いて６面体のそれぞれの面座標系への変換処理を簡素化する手段をもつ衝突検出回路。
【請求項３】
請求項１の回路において、動く物体が複数ある場合、静止物体を記憶したメモリに加えて、動く物体を囲む６面体のメモリを複数組設け、６面それぞれの面を外部から見た、面に投影される動く物体の画像情報を、内挿補間段階で前記複数組からなるそれぞれのメモリに記憶する手段と、前記動く物体の画像情報を物体の有無フラグ、識別子、面法線、面からの距離のそれぞれとする手段と、予め記憶された請求項１の静止物体の画像情報と、前記動く物体の画像情報とを同時に読みだして、それぞれの情報を基に静止物体および動く物体それぞれとの衝突を検出する回路。
【請求項４】
請求項１および３の回路において、動く物体のポリゴンの描画段階において、ポリゴンの識別子を保有し、またポリゴンの表示段階では内挿点毎の座標値と共に面法線を求め、衝突が検出された場合、アプリケーションプロセッサには、衝突検出点座標値、静止物体画像情報から読みだされた識別子と面法線、また動く物体の前記保有する識別子と面法線のそれぞれを出力して、衝突した物体それぞれの識別子、衝突点座標値、および衝突面の面法線をアプリケーションプロセッサに知らせる衝突検出回路。
【請求項５】
請求項１から４までに記載のそれぞれの手段用いたコンピュータグラフィック画像装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２００９−１４６３６８（Ｐ２００９−１４６３６８Ａ）
【公開日】平成２１年７月２日（２００９．７．２）
【国際特許分類】
【出願番号】特願２００７−３４１７６６（Ｐ２００７−３４１７６６）
【出願日】平成１９年１２月１３日（２００７．１２．１３）
【出願人】（５９５０６１８７５）
【Ｆターム（参考）】
【公開日】平成２１年７月２日（２００９．７．２）
【国際特許分類】
【出願日】平成１９年１２月１３日（２００７．１２．１３）
【出願人】（５９５０６１８７５）
【Ｆターム（参考）】
[ Back to top ]