(57)【特許請求の範囲】
【請求項１】
トーラスと線分との交点の算出において、前記線分と交差し前記トーラスに内接する内接球を取得する内接球取得手段と、
前記内接球と前記線分とが交差する交点を算出する算出手段と、
新たな内接球の位置を、該新たな内接球と前記トーラスとの接触位置である接触円が前記交点に近づくように取得する再取得手段と、
前記新たな内接球と前記線分との交点を算出する再算出手段と、
前記再取得手段により取得された前記新たな内接球と前記線分との交点を前記再算出手段に算出させることを１回または複数回行うことにより得られた、前記内接球と前記線分との交点に基づいて前記トーラスと前記線分との交点を出力する交点出力手段と、
を含む画像処理装置。
【請求項２】
請求項１に記載の画像処理装置において、
前記内接球取得手段は、前記線分と交差する内接円を含むそれぞれ前記トーラスに内接する複数の内接球を取得し、
前記算出手段は、前記複数の内接球のうちいずれかと前記線分とが交差する交点を算出する、
画像処理装置。
【請求項３】
請求項１または２に記載の画像処理装置において、
前記内接球取得手段は、前記トーラスを包含する物体と前記線分との交点に基づいて前記トーラスに内接する内接球を取得する、
画像処理装置。
【請求項４】
請求項３に記載の画像処理装置において、
前記トーラスに外接する円柱と前記線分との交点を求める仮交点算出手段をさらに含み、
前記内接球取得手段は、前記トーラスを囲む円柱と前記線分との交点に基づいて前記トーラスに内接する内接球を取得する、
画像処理装置。
【請求項５】
コンピュータが、
トーラスと線分との交点の算出において、前記線分と交差し前記トーラスに内接する内接球を取得し、
前記内接球と前記線分とが交差する交点を算出し、
新たな内接球の位置を、該新たな内接球と前記トーラスとの接触位置である接触円が前記交点に近づくように取得し、
前記新たな内接球と前記線分との交点を算出し、
前記新たな内接球を取得し前記新たな内接球と前記線分との交点を算出することを１回または複数回行うことにより得られた、前記内接球と前記線分との交点に基づいて前記トーラスと前記線分との交点を出力する、
画像処理方法。
【請求項６】
トーラスと線分との交点の算出において、前記線分と交差し前記トーラスに内接する内接球を取得する内接球取得手段、
前記内接球と前記線分とが交差する交点を算出する算出手段、
新たな内接球の位置を、該新たな内接球と前記トーラスとの接触位置である接触円が前記交点に近づくように取得する再取得手段、
前記新たな内接球と前記線分との交点を算出する再算出手段、
前記再取得手段により取得された前記新たな内接球と前記線分との交点を前記再算出手段に算出させることを１回または複数回行うことにより得られた、前記内接球と前記線分との交点に基づいて前記トーラスと前記線分との交点を出力する交点出力手段、
としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は画像処理装置、画像処理方法、およびプログラムに関する。
【背景技術】
【０００２】
球と他の物体とが衝突する位置を求めたい場合がある。この位置を求めるために、他の物体の外形を球の半径だけ膨らませた仮想物体と、移動する球の中心点の軌跡を示す線分とが交差する位置を求め、その位置を球と他の物体とが衝突する場合の球の中心の位置として出力する。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
例えば円柱と球とが衝突する位置を求める場合、円柱を球の半径だけ膨らませた形状は、元の円柱よりより太い円柱と、円板とトーラスとを組み合わせた形状になる。円柱や円板と線分とが交差する点を算出する方法は既知である。一方、トーラスと線分とが交差する点を求めることは、解析的に解くことが難しい高次元の方程式を解く必要があるために現実的でなかった。
【０００４】
本発明は上記課題を鑑みてなされたものであって、その目的は、トーラスと線分とが交差する点を求めることのできる現実的な技術を提供することにある。
【課題を解決するための手段】
【０００５】
上記課題を解決するために、本発明にかかる画像処理装置は、トーラスと線分との交点の算出において、前記線分と交差し前記トーラスに内接する内接球を取得する内接球取得手段と、前記内接球と前記線分とが交差する交点を算出する算出手段と、新たな内接球の位置を、該新たな内接球と前記トーラスとの接触位置である接触円が前記交点に近づくように取得する再取得手段と、前記新たな内接球と前記線分との交点を算出する再算出手段と、前記再取得手段により取得された前記新たな内接球と前記線分との交点を前記再算出手段に算出させることを１回または複数回行うことにより得られた、前記内接球と前記線分との交点に基づいて前記トーラスと前記線分との交点を出力する交点出力手段と、を含む。
【０００６】
また、本発明にかかる画像処理方法は、トーラスと線分との交点の算出において、前記線分と交差し前記トーラスに内接する内接球を取得し、前記内接球と前記線分とが交差する交点を算出し、新たな内接球の位置を、該新たな内接球と前記トーラスとの接触位置である接触円が前記交点に近づくように取得し、前記新たな内接球と前記線分との交点を算出し、前記再取得手段により取得された前記新たな内接球と前記線分との交点を前記再算出手段に算出させることを１回または複数回行うことにより得られた、前記内接球と前記線分との交点に基づいて前記トーラスと前記線分との交点を出力する。
【０００７】
また、本発明にかかるプログラムは、トーラスと線分との交点の算出において、前記線分と交差し前記トーラスに内接する内接球を取得する内接球取得手段、前記内接球と前記線分とが交差する交点を算出する算出手段、新たな内接球の位置を、該新たな内接球と前記トーラスとの接触位置である接触円が前記交点に近づくように取得する再取得手段、前記新たな内接球と前記線分との交点を算出する再算出手段、前記再取得手段により取得された前記新たな内接球と前記線分との交点を前記再算出手段に算出させることを１回または複数回行うことにより得られた、前記内接球と前記線分との交点に基づいて前記トーラスと前記線分との交点を出力する交点出力手段、としてコンピュータを機能させる。
【０００８】
また、本発明にかかるコンピュータ読取り可能な情報記憶媒体は、上記プログラムを格納する。
【０００９】
本発明によれば、トーラスと線分とが交差する点を容易に求めることができる。
【００１０】
本発明の一態様では、前記内接球取得手段は、前記線分と交差する内接円を含むそれぞれ前記トーラスに内接する複数の内接球を取得し、前記算出手段は、前記複数の内接球のうちいずれかと前記線分とが交差する交点を算出してもよい。
【００１１】
本発明の一態様では、前記内接球取得手段は、前記トーラスを包含する物体と前記線分との交点に基づいて前記トーラスに内接する内接球を取得してもよい。
【００１２】
本発明の一態様では、画像処理装置は前記トーラスに外接する円柱と前記線分との交点を求める仮交点算出手段をさらに含み、前記内接球取得手段は、前記トーラスを囲む円柱と前記線分との交点に基づいて前記トーラスに内接する内接球を取得してもよい。
【図面の簡単な説明】
【００１３】
【図１】本発明の実施形態にかかる画像処理装置のハードウェア構成の一例を示す図である。
【図２】画像処理装置が実現する機能を示すブロック図である。
【図３】画像処理装置の処理フローの一例を示す図である。
【図４】衝突判定の対象となる対象球と対象円柱の一例を示す図である。
【図５】衝突判定に用いる膨張オブジェクトと軌跡との一例を示す図である。
【図６】膨張オブジェクトを構成する要素を示す図である。
【図７】球と円柱との衝突の検出に関する衝突処理部の処理フローの一例を示す図である。
【図８】膨張オブジェクト３４の中心軸を通る断面図である。
【図９】トーラスに内接する球の一例を示す図である。
【図１０】仮円柱と線分との仮交点と、内接球との一例を示す図である。
【図１１】図１０のＸＩ−ＸＩ切断線における断面図である。
【図１２】仮円柱と線分との仮交点と、複数の内接球との一例を示す図である。
【図１３】内接球と線分との交点と新たな内接球との一例を示す図である。
【図１４】図１３のXIV−XIV切断線における断面図である。
【図１５】順に取得された仮交点および複数の交点を説明する図である。
【発明を実施するための形態】
【００１４】
以下では、本発明の実施形態について図面に基づいて説明する。出現する構成要素のうち同一機能を有するものには同じ符号を付し、その説明を省略する。
【００１５】
図１は、本発明の実施形態にかかる画像処理装置１のハードウェア構成の一例を示す図である。画像処理装置１は、パーソナルコンピュータや家庭用ゲーム機、または携帯情報端末である。画像処理装置１は、プロセッサ１１、記憶部１２、通信部１３、操作入力部１４、表示制御部１５を含む。
【００１６】
プロセッサ１１は、記憶部１２に格納されているプログラムに従って動作し、通信部１３や操作入力部１４、表示制御部１５等を制御する。なお、上記プログラムは、フラッシュメモリ等のコンピュータで読み取り可能な記憶媒体に格納されて提供されるものであってもよいし、インターネット等のネットワークを介して提供されるものであってもよい。
【００１７】
記憶部１２は、ＤＲＡＭやフラッシュメモリ等のメモリ素子によって構成されている。記憶部１２は、上記プログラムを格納する。また、記憶部１２は、プロセッサ１１や通信部１３等から入力される情報や演算結果を格納する。
【００１８】
通信部１３は有線ＬＡＮや無線ＬＡＮを構成する集積回路やコネクタ、アンテナなどにより構成されている。通信部１３は、ネットワークを介して他の装置と通信する機能を有する。通信部１３は、プロセッサ１１の制御に基づいて、他の装置から受信した情報をプロセッサ１１や記憶部１２に入力し、他の装置に情報を送信する。
【００１９】
操作入力部１４は、ユーザの操作を検出するハードウェアからの入力を取得する回路である。操作入力部１４は、例えばタッチパネルやコントローラ、キーボード等からの入力を取得し、検出された情報をプロセッサ１１や記憶部１２に入力する。
【００２０】
表示制御部１５はディスプレイ等の表示出力デバイスを制御する回路を含んでいる。表示制御部１５は、プロセッサ１１の制御に基づいて、表示出力デバイスに画像を表示させる。
【００２１】
図２は、本発明の実施形態にかかる画像処理装置１が実現する機能を示すブロック図である。画像処理装置１は機能的に、移動情報取得部５１、衝突処理部５２、画像描画部５３を含む。また、衝突処理部５２は、仮交点算出部５４、内接球取得部５５、交点算出部５６、内接球再取得部５７、交点再算出部５８、交点出力部５９、位置設定部６０を含む。これらは、プロセッサ１１が記憶部１２に格納されるプログラムを実行し、操作入力部１４や表示制御部１５等を制御することで実現される。
【００２２】
移動情報取得部５１は、主にプロセッサ１１、記憶部１２により実現される。移動情報取得部５１は、３次元コンピュータグラフィックスの画像を構成するオブジェクトの、仮想空間内における移動の向きや量を示す情報を取得する。オブジェクトの移動の向きや量を示す情報は、オブジェクトの速度ベクトルであってもよいし、前のフレームから今回描画する現在のフレームまでの間の移動量および向きを示すベクトルであってもよい。また、移動情報取得部５１は、記憶部１２に格納されたオブジェクトの動作に関する情報に基づいてそのオブジェクトの移動の向きや量を示す情報を取得してもよいし、操作入力部１４から入力されるユーザの操作に基づいて、オブジェクトの移動の向きや量を示す情報を取得してもよい。
【００２３】
衝突処理部５２は、主にプロセッサ１１、記憶部１２により実現される。衝突処理部５２は、複数のオブジェクトが互いに衝突するか否かを判定する。また、衝突処理部５２は、互いに衝突するオブジェクトについて、その衝突位置を出力する。そして、衝突処理部５２はオブジェクトが衝突するか否かと、衝突する場合の衝突位置とに基づいて、現在のフレームにおける複数のオブジェクトのそれぞれの位置を決定する。
【００２４】
画像描画部５３は、主にプロセッサ１１、記憶部１２、表示制御部１５により実現される。画像描画部５３は、衝突処理部５２により決定された仮想空間内の複数のオブジェクトの位置に基づいて、その複数のオブジェクトを描画し、オブジェクトが描画された画像を表示出力デバイスに表示させる。
【００２５】
図３は、画像処理装置１の処理フローの一例を示す図である。ここで、図３に示す処理は複数のオブジェクトを含むフレームの画像が描画されるごとに繰返し行われる。
【００２６】
はじめに、移動情報取得部５１は、複数のオブジェクトのそれぞれの移動方向および速度を示す情報を取得する（ステップＳ１０１）。次に、衝突処理部５２は複数のオブジェクトが互いに衝突するか否かと、互いに衝突するオブジェクトの衝突位置とを取得する（ステップＳ１０２）。
【００２７】
また、衝突処理部５２に含まれる位置設定部６０は、現在のフレームにおける複数のオブジェクトの位置を決定する（ステップＳ１０３）。より具体的には、位置設定部６０は位置を決定する対象となるオブジェクト（対象オブジェクト）が他のオブジェクトと衝突しない場合には、移動情報取得部５１が取得した情報が示す移動方向および移動量だけ対象オブジェクトが移動したものとして対象オブジェクトの位置を決定する。位置設定部６０は対象オブジェクトが他のオブジェクトと衝突した場合には、衝突位置へ移動したものとして対象オブジェクトの位置を決定するか、あるいは衝突位置から跳ね返る方向と移動量とを算出し、その算出された跳ね返る方向と移動量とが示す位置を対象オブジェクトの位置として決定する。
【００２８】
そして、画像描画部５３は、決定された複数のオブジェクトの位置に基づいて、その複数のオブジェクトの画像を描画し、描画された画像を表示出力デバイスに表示させる（ステップＳ１０４）。
【００２９】
次に、複数のオブジェクトが互いに衝突するか否かと、互いに衝突するオブジェクトの衝突位置とを取得する処理について説明する。この処理は、衝突処理部５２の特にステップＳ１０２に相当する。ここでは、特に、衝突の検出の対象となる２つのオブジェクトが球と円柱（シリンダ）とである場合の処理について説明する。球と球との衝突や、球とカプセルとの衝突、球と箱との衝突については公知の手法で検出できるため説明を省略する。
【００３０】
図４は、衝突判定の対象となる対象球３１と対象円柱３２との一例を示す図である。対象球３１、対象円柱３２は、それぞれ、衝突を検出する対象となる球および円柱である。以下の説明では、対象円柱３２が静止しているものとする。しかし、対象円柱３２が移動している場合でも、対象円柱３２に対する対象球３１の相対速度から求められる対象球３１の相対的な移動方向および移動量を、対象球３１の単なる移動方向および移動量の代わりに用いれば同様の手法で衝突を検出することができる。
【００３１】
図５は、衝突判定に用いる膨張オブジェクト３４と始点３３との一例を示す図である。膨張オブジェクト３４の表面は、対象円柱３２の表面からの距離が対象球３１の半径となる面であり、膨張オブジェクト３４の表面は対象円柱３２の外側に存在する。また、前のフレームにおける対象球３１の中心が線分３５の始点３３であり、線分３５の終点は始点３３から対象球３１の移動方向に移動量だけ離れた位置にある。膨張オブジェクト３４は中心軸４７を対称軸とする軸対称である。以下では、説明の容易のため、中心軸４７の方向が上下方向であるとして説明する。
【００３２】
膨張オブジェクト３４と線分３５との交点が存在することは、対象円柱３２と対象球３１とが衝突することと等価である。また、膨張オブジェクト３４と線分３５との交点は、対象円柱３２と対象球３１とが衝突する際の対象球３１の中心の位置と等価である。本実施形態では、衝突処理部５２は、膨張オブジェクト３４と線分３５との交点を探すことにより、対象円柱３２と対象球３１とが衝突するか否かと、対象円柱３２に対象球３１が衝突する場合の衝突位置とを求める。
【００３３】
図６は、膨張オブジェクト３４を構成する要素を示す図である。図６は、膨張オブジェクト３４を構成する要素を分解して示す図である。膨張オブジェクト３４の表面は、図６の上方から順に、円板４１と、トーラス４２と、拡張円柱４３と、トーラス４４と、円板４５との表面を組み合わせることにより表現される。拡張円柱４３は、対象円柱３２の半径を対象球３１の半径だけ増加させた円柱であり、拡張円柱４３の高さは対象円柱３２の高さと同じである。対象円柱３２の半径をＲ、対象球３１の半径をｒとすると、拡張円柱４３の半径はＲ＋ｒであり、対象円柱３２の対称軸（中心軸４７）と拡張円柱４３の対称軸は重なっている。
【００３４】
トーラス４２，４４は、それぞれリング状のチューブを有する。トーラス４２のチューブの断面の中心の集合は、対象円柱３２の上端を構成する円板の外周である。トーラス４４チューブの断面の中心の集合は、対象円柱３２の下端を構成する円板の外周である。トーラス４２，４４は軸対称である。トーラス４２，４４の対称軸はリングの中心にあり、その対称軸は中心軸４７と重なっている。軸を通る平面で切断されたトーラス４２，４４の断面は、中心軸４７からの距離がＲである点を中心とする半径ｒの円を有する。トーラス４２，４４を軸方向でみて上半分と下半分とに分けた場合、トーラス４２の下半分とトーラス４４の上半分とは拡張円柱４３と重なっている。なお、図６においては、形状の認識を容易にするため、トーラス４２，４４を８等分する断面の円を線で示している。
【００３５】
円板４１はトーラス４２の最も高い部分を結んだ円で囲まれた平面上の領域であり、円板４５はトーラス４４の最も低い部分を結んだ円で囲まれた平面上の領域である。円板４１，４５の中心は中心軸４７上にあり、半径は対象円柱３２と同じ（Ｒ）である。
【００３６】
膨張オブジェクト３４と線分３５との交点を探す処理は、衝突処理部５２に含まれる、仮交点算出部５４、内接球取得部５５、交点算出部５６、内接球再取得部５７、交点再算出部５８、交点出力部５９により実行される。
【００３７】
仮交点算出部５４は、膨張オブジェクト３４に外接する仮円柱４８と線分３５との交点（仮交点Ｐ０）を求める。仮円柱４８は、トーラス４２，４４を囲んでいる。また、仮交点算出部５４は、仮円柱４８と線分３５との仮交点Ｐ０がトーラス４２または４４との交差の判定を必要とする領域にあるかを判定する。内接球取得部５５は、仮交点Ｐ０がトーラス４２または４４との交差の判定を必要とする領域にある場合に、仮円柱４８と線分３５との仮交点Ｐ０に基づいてトーラス４２または４４に内接する１または複数の内接球Ｂを取得する。なお、以下では内接球Ｂは、内接球取得部５５や内接球再取得部５７により取得されるいずれかの内接球を指すものとするが、どの内接球か具体的に特定できる場合は内接球Ｂ１，Ｂ２等と記載する。線分３５とトーラス４２または４４とが交差する場合のほとんどでは、この内接球Ｂと線分３５とが交差する。
【００３８】
交点算出部５６は、内接球Ｂと線分３５とが交差する交点Ｐを算出する。内接球再取得部５７は、新たな内接球Ｂとトーラス４２または４４との接触位置である接触円が、算出された交点Ｐに近づくように新たな内接球Ｂの位置を取得する。交点再算出部５８は、新たな内接球Ｂと線分３５との交点Ｐを算出する。交点出力部５９は、内接球再取得部５７により取得された新たな内接球Ｂと線分３５との交点を交点再算出部５８に算出させることを１回または複数回行うことにより得られた、内接球Ｂと線分３５との交点Ｐに基づいてトーラス４２または４５と線分３５との交点を出力する。
【００３９】
次に、ステップＳ１０２の処理の詳細について説明する。図７は、球と円柱との衝突の検出に関する衝突処理部５２の処理フローの一例を示す図である。はじめに、衝突処理部５２は、対象球３１と対象円柱３２とが、始点３３で衝突しているかを判定する（ステップＳ２０１）。より具体的には、衝突処理部５２は、前のフレームにおける対象球３１の中心の点（始点３３）が、対象円柱３２内に存在するか否かを判定し、始点３３が対象円柱３２内にある場合には対象球３１と対象円柱３２とが既に衝突していると判定する。対象球３１と対象円柱３２とが衝突していると判定された場合には（ステップＳ２０１のＹ）、衝突処理部５２の交点出力部５９は、衝突していると判定されたことを示す情報と、衝突位置が検出できないことを示す情報とを出力し、ステップＳ１０３の処理へ進む。
【００４０】
対象球３１と対象円柱３２とが衝突していないと判定された場合には（ステップＳ２０１のＮ）、前のフレームからステップＳ１０１で取得された移動方向および量だけ対象球３１を移動させた場合の中心点の軌跡である線分３５と、対象円柱３２が膨らんだ形状を有する膨張オブジェクト３４との交点を求めるためにステップＳ２０２以降の処理が実行される。
【００４１】
ステップＳ２０２では、仮交点算出部５４は、対象円柱３２が膨らんだ膨張オブジェクト３４を内包する仮円柱４８を決定する。図８は、膨張オブジェクト３４の中心軸４７を通る断面図である。図８には、仮円柱４８も図示されている。仮交点算出部５４は、仮円柱４８の対称軸は膨張オブジェクト３４の中心軸４７であり、半径が（Ｒ＋ｒ）であり、中心軸４７の方向の長さが（Ｄ＋２ｒ）であり、仮円柱４８の側面と拡張円柱４３とが接し、仮円柱４８の上面および下面の円板が円板４１，４５に接するように、仮円柱４８の大きさと位置とを決定する。ここで、Ｄは対象円柱３２の高さ、Ｒは対象円柱３２の半径とする。
【００４２】
次に、仮交点算出部５４は対象球３１の中心の軌跡の線分３５が仮円柱４８と交差するかを判定する（ステップＳ２０３）。より具体的には、仮交点算出部５４は線分３５の始点３３を中心軸４７に投影した点Ｍと線分３５の始点３３を仮円柱４８の上面の円板を含む平面に投影した点Ｎとを取得する。ここでは中心軸４７の方向が上下方向であるとしている。そして、点Ｍが仮円柱４８の内部にある場合には、始点３３が仮円柱４８の側面のボロノイ領域にあると判定し、仮円柱４８の側面と線分３５との交点を探す。点Ｍが仮円柱４８の上側にあり、点Ｎが仮円柱４８の上面の円板内にある場合には、仮交点算出部５４は始点３３が上面の円のボロノイ領域にあると判定し、仮円柱４８の上面と線分３５との交点を探す。また点Ｍが仮円柱４８の下側にあり、点Ｎが仮円柱４８の上面の円板内にある場合には、仮交点算出部５４は始点３３が下面の円のボロノイ領域にあると判定し、仮円柱４８の下面と線分３５との交点を探す。点Ｍが仮円柱４８の上側にあり、点Ｎが仮円柱４８の上面の円板より外側にある場合には、仮交点算出部５４は始点３３が上面の円周のボロノイ領域にあると判定し、仮円柱４８の上面と線分３５との交点、仮円柱４８の側面と線分３５との交点を探す。これらの処理により交点がみつからない場合には、線分３５が仮円柱４８と交差せず、かつ、対象球３１が対象円柱３２と衝突しないとして（ステップＳ２０３のＮ）、ステップＳ１０３の処理へ進む。一方、線分３５と仮円柱４８の側面、上面、下面のいずれかとの交点がみつかった場合には、線分３５と仮円柱４８とが交差し、その交点が仮交点Ｐ０であるとして（ステップＳ２０３のＹ）、ステップＳ２０４の処理に進む。
【００４３】
ステップＳ２０４では、仮交点算出部５４は仮交点Ｐ０がトーラス４２または４４との交差の判定を必要とする領域にあるか否かを判定する。より具体的には、仮交点算出部５４は仮交点Ｐ０の中心軸４７からの距離Ｌ１が、Ｒ＜Ｌ１＜（Ｒ＋ｒ）を満たし、かつ、仮交点Ｐ０を中心軸４７に投影した点と仮円柱４８の下端との距離Ｌ２が、０＜＝Ｌ２＜ｒまたはＤ＋ｒ＜Ｌ２＜＝Ｄ＋２ｒを満たす場合（例えば図８において仮交点Ｐ０が範囲ＡＲかつ範囲ＡＺにある場合）に、仮交点Ｐ０がトーラス４２または４４との交差の判定を必要とする領域にあると判定する（ステップＳ２０４のＹ）。また、交差の判定を必要とする領域にあると判定された場合、仮交点算出部５４は、０＜＝Ｌ２＜ｒの場合はトーラス４４との交差の判定が必要であり、Ｄ＋ｒ＜Ｌ２＜＝Ｄ＋２ｒの場合はトーラス４２との交差の判定が必要であると判定する。一方、仮交点Ｐ０がトーラス４２または４４との交差の判定を必要とする領域にあると判定されなかった場合（ステップＳ２０４のＮ）は、仮交点Ｐ０は拡張円柱４３の円周の上または円板４１，４５の上にあるため、その仮交点Ｐ０をそのまま線分３５と膨張オブジェクト３４との交点、かつ対象球３１が対象円柱３２に衝突する位置とし、ステップＳ１０３の処理へ進む。
【００４４】
仮交点Ｐ０がトーラス４２または４４との交差の判定を必要とする領域にある場合には（ステップＳ２０４のＹ）、内接球取得部５５は、仮交点Ｐ０に基づいて、トーラス４２または４４のうち交差の判定が必要とされたもの（以下では「判定トーラスＴ」と記載する）に内接する１または複数の内接球Ｂを設定する（ステップＳ２０５）。
【００４５】
図９は、判定トーラスＴに内接する内接球Ｂ１の一例を示す図である。本図では、形状の認識を容易にするため、判定トーラスＴを８等分する断面の円を線で示し、また内接球Ｂ１により隠される線のみを破線で示している。図示していないが、判定トーラスＴは仮円柱４８に囲まれている。また、判定トーラスＴの中心軸４７から最も遠い点の集合となる円を外周円ＴＣとし、判定トーラスＴの中心軸４７の方向を上下方向とした場合に最も高い点を繋いだ線を上端円、最も低い点を繋いだ線を下端円とすると、外周円ＴＣと、上端円および下端円のうち一方とは仮円柱４８に接している。
【００４６】
図１０は、仮円柱４８と線分３５との仮交点Ｐ０と、内接球Ｂ１との一例を示す図である。図１０は、中心軸４７の一方の側から仮円柱４８等を見た図である。また図１１は、図１０のＸＩ−ＸＩ切断線における断面図である。図１０，１１は、判定トーラスＴと線分３５とが交差する交点を求める処理の一部において設定される１つの内接球Ｂ１を示している。図１０の例では、内接球取得部５５は、仮交点Ｐ０と中心軸４７とを含む平面上かつ対象円柱３２の上端または下端の円板のうち仮交点Ｐ０に近い円板の円周上に内接球Ｂ１の中心Ｃ１が位置し、かつ内接球Ｂ１が判定トーラスＴに内接するように１つの内接球Ｂ１を設定する。こうすると、内接球Ｂ１と判定トーラスＴとが接触する位置の集合は、仮交点Ｐ０と中心軸４７とを含む平面上にある円になる。以下ではこの円を接触円を記載する。接触円は、仮円柱４８の円周と、上下端のうち一方の円板とに接する。
【００４７】
なお、図９から１１の例では内接球取得部５５により取得される内接球Ｂの数は１つであるが、内接球Ｂの数は２以上であってもよい。図１２は、仮円柱４８と線分３５との仮交点Ｐ０と、複数の内接球Ｂ１，Ｂ１２，Ｂ１３との一例を示す図である。内接球Ｂ１は図１０の例と同様の方法で仮交点Ｐ０に応じて設定されている。この場合、内接球取得部５５は、内接球Ｂ１の他に、内接球Ｂ１の隣に位置するように配置されている内接球Ｂ１２，Ｂ１３を取得する。また、内接球取得部５５は、内接球Ｂ１，Ｂ１２，Ｂ１３のそれぞれが、他の内接球Ｂの少なくとも１つと重なるように内接球Ｂ１，Ｂ１２，Ｂ１３を取得する。こうすると、後述の交点算出部５６の処理において、実際は判定トーラスＴと線分３５とが交わる場合であっても内接球Ｂ１と線分３５との交点Ｐが見つからないために判定トーラスＴと線分３５とが交わらないと判定される現象の発生を減らすことができる。
【００４８】
次に、交点算出部５６は、１または複数の内接球Ｂと軌跡の線分３５との交点Ｐ１を求める（ステップＳ２０６）。例えば、交点算出部５６は、内接球Ｂ１と線分３５との交点Ｐ１を、内接球Ｂ１を示す数式と線分３５を示す数式とから導出される２次方程式を解くことにより求める。１つの内接球Ｂ１と線分３５との２つの交点が求められる場合には、交点算出部５６は、線分３５の始点３３に最も近い交点Ｐ１を以下の処理の対象として求める。図１０や図１１には、交点Ｐ１の例を示している。
【００４９】
また複数の内接球Ｂと線分３５とについて複数の交点が求められる場合は、その交点のうち始点３３に最も近いものを以下の処理の対象となる交点Ｐ１として求める。一方、２次方程式に実数解がなく、交点Ｐ１を求めることができない場合には（ステップＳ２０７のＮ）、交点出力部５９は、判定トーラスＴと線分３５との交点が存在せず、また対象球３１と対象円柱３２とが衝突しないと判定されたことを示す情報を出力し、ステップＳ１０３の処理へ進む。
【００５０】
２次方程式に実数解があり、交点Ｐ１を求めることができた場合には（ステップＳ２０７のＹ）、内接球再取得部５７は、直近に求められた交点Ｐに基づいて新たな内接球Ｂを取得する（ステップＳ２０８）。この際、内接球再取得部５７は、新たな内接球Ｂと判定トーラスＴとの接触位置である接触円が、直近に求められた交点Ｐに近づくように新たな内接球Ｂの位置を取得する。内接球再取得部５７が設定する新たな内接球Ｂの数は１である。
【００５１】
図１３は、交点Ｐ１と新たな内接球Ｂ２との一例を示す図である。図１４は、図１３のXIV−XIV切断線における断面図である。図１２、図１３の対象円柱３２は、図１０，１１の対象円柱３２と同じものであり、図１２、図１３には、図１０，１１のように仮円柱４８も記載されている。交点Ｐ１は内接球Ｂ１と線分３５との交点であり、内接球Ｂ２は交点Ｐ１に応じて新たに設定される。図１４は、中心軸４７と交点Ｐ１とを含む断面を示す。例えば、内接球再取得部５７は、交点Ｐ１と中心軸４７とを含む平面上かつ対象円柱３２の上端または下端のうち交点Ｐ１に近い方の円周上に新たな内接球Ｂ２の中心Ｃ２が位置し、かつ新たな内接球Ｂが判定トーラスＴに内接するように新たな内接球Ｂ２を設定する。
【００５２】
そして、交点再算出部５８は、新たな内接球Ｂと線分３５との交点Ｐを算出する（ステップＳ２０９）。新たな内接球Ｂと線分３５との交点Ｐを算出する手法は、交点算出部５６と同じであり、例えば、新たな内接球Ｂと線分３５との交点Ｐを、新たな内接球Ｂを示す数式と線分３５を示す数式とから導出される２次方程式を解くことにより求める。また、新たな内接球Ｂと線分３５との２つの交点が求められる場合には、交点再算出部５８は、線分３５の始点３３に最も近いものを以下の処理の対象となる交点Ｐとして求める。図１０や図１１には、内接球Ｂ２と線分３５との交点Ｐ２の例を示している。
【００５３】
新たな内接球Ｂと線分３５との交点Ｐを求めることができない場合には（ステップＳ２１０のＮ）、交点出力部５９は、判定トーラスＴと線分３５との交点が存在せず、また対象球３１と対象円柱３２とが衝突しないと判定されたことを示す情報を出力し、ステップＳ１０３の処理へ進む。
【００５４】
一方、新たな内接球Ｂと線分３５との交点Ｐを求めることができた場合には（ステップＳ２１０のＹ）、交点出力部５９は収束条件を満たすかを判定する（ステップＳ２１１）。収束条件は、前回求められた交点Ｐと今回求められた交点Ｐとの距離が所定の閾値より小さいことであってもよいし、ステップＳ２０８からステップＳ２１０の処理が所定の回数だけ繰返されたことであってもよい。収束条件を満たさない場合には（ステップＳ２１１のＮ）、ステップＳ２０８以降の処理を繰返す。なお、繰返された後のステップＳ２０８ではもちろんステップＳ２０９で求められた交点Ｐを用いて内接球Ｂを取得する。
【００５５】
交点算出部５６、交点再算出部５８は内接球Ｂと線分３５との交点Ｐを算出するが、新たに算出される交点Ｐほど、実際の判定トーラスＴと線分３５との交点に近づく。図１５は、順に取得された仮交点Ｐ０および複数の交点Ｐ１，Ｐ２，Ｐ３を説明する図である。内接球Ｂ１，Ｂ２，Ｂ３は、それぞれ仮交点Ｐ０、交点Ｐ１，Ｐ２に基づいて取得され、交点Ｐ１からＰ３は、それぞれ内接球Ｂ１からＢ３と線分３５との交点である。図１５に示すように、ある交点Ｐとその直前に求められた交点Ｐとの距離は、交点Ｐが新しくなるにつれ小さくなる。
【００５６】
一方、収束条件を満たす場合には（ステップＳ２１１のＹ）、対象球３１と対象円柱３２とが衝突すると判定し、ステップＳ２０９で求められた交点Ｐを、判定トーラスＴと線分３５との交点をして出力する（ステップＳ２１２）。算出される交点Ｐの位置が収束すると、交点Ｐは判定トーラスＴと内接球Ｂとの接触円上に存在するため、その交点Ｐは実際の判定トーラスＴと線分３５との交点となる。したがって、収束条件を満たす交点Ｐは、膨張オブジェクト３４と線分３５との交点の十分に精度の高い近似解であり、また対象球３１と対象円柱３２とが衝突する際の対象球３１の中心の位置の近似解である。この出力された交点は、ステップＳ１０３以降の処理で用いられる。
【００５７】
これまでに説明した手法により、衝突処理部５２は、高次の方程式を直接的に解くことなしに、トーラスと線分との交点を求めることができ、その計算量を現実的なものにすることもできる。また、球と円柱との衝突を判定することも可能になる。
【符号の説明】
【００５８】
１  画像処理装置、１１  プロセッサ、１２  記憶部、１３  通信部、１４  操作入力部、１５  表示制御部、３１  対象球、３２  対象円柱、３３  始点、３４  膨張オブジェクト、３５  線分、４１，４５  円板、４２，４４  トーラス、４３  拡張円柱、４７  中心軸、４８  仮円柱、５１  移動情報取得部、５２  衝突処理部、５３  画像描画部、５４  仮交点算出部、５５  内接球取得部、５６  交点算出部、５７  内接球再取得部、５８  交点再算出部、５９  交点出力部、６０  位置設定部、Ｂ，Ｂ１，Ｂ２，Ｂ３，Ｂ１２，Ｂ１３  内接球、Ｃ１，Ｃ２  中心、Ｐ，Ｐ１，Ｐ２，Ｐ３  交点、Ｐ０  仮交点、Ｔ  判定トーラス、ＴＣ  外周円。
【図１】
0006314114.tif 000002
【図２】
0006314114.tif 000003
【図３】
0006314114.tif 000004
【図４】
0006314114.tif 000005
【図５】
0006314114.tif 000006
【図６】
0006314114.tif 000007
【図７】
0006314114.tif 000008
【図８】
0006314114.tif 000009
【図９】
0006314114.tif 000010
【図１０】
0006314114.tif 000011
【図１１】
0006314114.tif 000012
【図１２】
0006314114.tif 000013
【図１３】
0006314114.tif 000014
【図１４】
0006314114.tif 000015
【図１５】
0006314114.tif 000016