(57)【特許請求の範囲】
【請求項１】
多面体を定義する複数の特徴項によってそれぞれ表現された少なくとも２つのオブジェクトの間の最短の特徴項を決定するシステムであって、
前記２つのオブジェクトである第１多面体及び第２多面体から第１特徴項及び第２特徴項をそれぞれ選択する特徴項選択手段と、
前記第１特徴項に対応する第１ボロノイ領域及び前記第２特徴項に対応する第２ボロノイ領域を決定するボロノイ領域決定手段と、
前記第１特徴項の第１最短ポイントが前記第２ボロノイ領域に存在するか否かを決定するために前記第１特徴項を前記第２ボロノイ領域と照合する第１照合手段と、
前記第２特徴項の第２最短ポイントが前記第１ボロノイ領域に存在するか否かを決定するために前記第２特徴項を前記第１ボロノイ領域と照合する第２照合手段と、
前記第２ボロノイ領域に関連する前記第１特徴項の位置及び前記第１ボロノイ領域に関連する前記第２特徴項の位置に基づき、新第１特徴項及び新第２特徴項を選択する新特徴項選択手段と
前記エッジが前記ボロノイ領域を出る出口ポイント及び前記ボロノイ領域に前記エッジが入る入口ポイントを決定するために、エッジタイプ特徴項を他の特徴項のボロノイ領域に対してクリップする手段と、
前記エッジタイプ特徴項及び前記他の特徴項の間の距離を前記入口ポイントにおける入口符号及び前記出口ポイントにおける出口符号として表現する関数の導関数符号を決定する手段と、
前記入口ポイントに対応する前記ボロノイ領域の平面を定める入口特徴項を決定し、前記出口ポイントに対応する前記ボロノイ領域の平面を定める出口特徴項を決定する手段と、
前記新特徴項選択手段に含まれ、前記第１特徴項あるいは第２特徴項がエッジタイプ特徴項のとき、新第１特徴項あるいは新第２特徴項を前記入口符号、出口符号、入口特徴項、及び出口特徴項に基づいて選択する手段と
を有することを特徴とする多面衝突検出システム。
【請求項２】
前記第１照合手段及び前記第２照合手段は、特徴項間相互関係決定プロセスを識別するステート装置を含み、
該ステート装置の各ステートは第１特徴項のタイプ及び第２特徴項のタイプに基づくことを特徴とする請求項１記載の多面衝突検出システム。
【請求項３】
前記特徴項選択手段は、
前記第１ボロノイ領域あるいは第２ボロノイ領域をそれぞれ確定する複数平面と、前記第１特徴項あるいは前記第２特徴項とを照合する手段と、
前記第１特徴項あるいは前記第２特徴項による前記複数の平面のうち少なくとも１平面の侵害を決定する侵害決定手段と、
侵害された前記複数の平面のうち少なくとも１つの平面に対して、前記第１特徴項及び第２特徴項に対応する前記第１最短ポイント及び第２最短ポイントのうち１つの相対位置を決定する手段と、
前記第１最短ポイント及び第２最短ポイントのうち前記１つの相対位置に基づき、侵害された複数平面のうち少なくとも１つを確定する特徴項を選択する選択手段と
を含むことを特徴とする請求項１記載の多面衝突検出システム。
【請求項４】
前記第１特徴項及び前記第２特徴項が各々エッジの特徴項のとき、
前記侵害決定手段は、対応するボロノイ領域のフェース平面の侵害を決定する前に、対応するボロノイ領域のバーテックス平面の侵害を決定することを特徴とする請求項３記載の多面衝突検出システム。
【請求項５】
少なくとも前記第１最短ポイントが前記第２ボロノイ領域内に存在せず且つ前記第２最短ポイントが前記第１ボロノイ領域内に存在していないとき、前記第１オブジェクト及び前記第２オブジェクトが透過しているか否かを決定する手段を更に含むことを特徴とする請求項１記載の多面衝突検出システム。
【請求項６】
前記少なくとも２つのオブジェクトからオブジェクトペアの選択を制御する手段、前記特徴項選択手段、ボロノイ領域決定手段、第１照合手段、第２照合手段、及び各オブジェクトペア間において最短特徴項が検出されるまで新第１特徴項及び新第２特徴項のうち１つが選択される選択手段の制御オペレーション手段を更に含むことを特徴とする請求項１記載の多面衝突検出システム。
【請求項７】
前記少なくとも２つのオブジェクトと該２つのオブジェクトの最短特徴項を表示する表示手段を更に含むことを特徴とする請求項６記載の多面衝突検出システム。
【請求項８】
前記少なくとも２つのオブジェクト間の最短特徴項及び前記最短特徴項間の距離をアウトプットするアウトプット手段を更に含むことを特徴とする請求項６記載の多面衝突検出システム。
【請求項９】
前記オブジェクトを動作させる手段を更に含み、
前記制御手段は、前記オブジェクトの各動作後の各オブジェクトペア間の最短特徴項を決定するために作動することを特徴とする請求項６記載の多面衝突検出システム。
【請求項１０】
ボロノイ領域決定手段によって決定するボロノイ領域を格納する手段と、
対応オブジェクトの動作に基づく前記格納済ボロノイ領域を調整する手段と
を更に含むことを特徴とする請求項９記載の多面衝突検出システム。
【請求項１１】
各オブジェクトペア間の最短特徴項を格納する手段を更に含み、
この手段によって、前記オブジェクトの動作後、前記格納手段で格納された各最短特徴項が前記第１特徴項及び前記第２特徴項として選択されることを特徴とする請求項９記載の多面衝突検出システム。
【請求項１２】
メモリに記憶された多面体データに基づいて、多面体を定義する複数の特徴項によって表現された少なくとも２つのオブジェクトの間の最短の特徴項を演算処理手段で決定する方法であって、
前記演算処理手段は、
（ａ）記憶部に記憶された第１多面体及び第２多面体を読み出し、前記第１多面体から第１特徴項を選択し、前記第２多面体から第２特徴項を選択するステップと、
（ｂ）前記第１特徴項に対応する第１ボロノイ領域を決定し、前記第２特徴項に対応する第２ボロノイ領域を決定するステップと、
（ｃ）前記第１ボロノイ領域を前記第１特徴項と照合し、前記第２ボロノイ領域を前記第２特徴項と照合するステップと、
（ｄ）前記第２ボロノイ領域に関連する前記第２特徴項に最短の前記第１特徴項の第１ポイントの位置、及び前記第１ボロノイ領域に関連する前記第１特徴項に最短の前記第２特徴項の第２ポイントの位置に基づき、新第１特徴項あるいは新第２特徴項を選択するステップと、
（ｅ）前記第１ポイントが前記第２ボロノイ領域内に存在し、前記第２ポイントが前記第１ボロノイ領域内に存在するまでステップ（ｂ）乃至（ｄ）を繰り返すステップと
を有し、
ステップ（ｃ）は、
前記エッジが前記ボロノイ領域に入る入口ポイント及び前記エッジが前記ボロノイ領域から出る出口ポイントを決定するために、エッジタイプ特徴項を他の特徴項のボロノイ領域に対してクリップするステップと、
前記エッジタイプ特徴項及び前記他の特徴項との間の距離を前記入口ポイントにおける入口符号及び前記出口ポイントにおける出口符号として表現する関数の導関数符号を決定するステップと、
前記入口ポイントに対応する前記ボロノイ領域の平面を定める入口特徴項を決定し、前記出口ポイントに対応する前記ボロノイ領域の平面を定める出口特徴項を決定するステップと、
ステップ（ｃ）に含まれ、前記第１特徴項あるいは第２特徴項がエッジタイプ特徴項のとき、新第１特徴項あるいは新第２特徴項を前記入口符号、出口符号、入口特徴項、及び出口特徴項に基づいて選択するステップと
を含むことを特徴とする多面衝突検出方法。
【請求項１３】
ステップ（ｄ）は、
前記第１特徴項あるいは前記第２特徴項を、前記第１ボロノイ領域あるいは前記第２ボロノイ領域をそれぞれ確定する複数平面の各平面と照合するステップと、
前記第１ポイントあるいは前記第２ポイントによって侵害された複数平面のうち１つを確定する特徴項が、前記新第１特徴項又は前記新第２特徴項として選択されるステップ
を更に含むことを特徴とする請求項１２記載の多面衝突検出方法。
【請求項１４】
前記第１特徴項及び前記第２特徴項が各々エッジタイプ特徴項であるとき、前記照合ステップは、特徴項を対応するボロノイ領域のバーテックス平面と照合するステップと、前記特徴項を前記バーテックス平面と照合した後、該特徴項を対応するボロノイ領域のフェース平面と照合するステップを含むことを特徴とする請求項１２記載の多面衝突検出方法。
【請求項１５】
前記少なくとも２つのオブジェクトは、少なくとも３つのオブジェクトが含まれ、
前記ステップ（ａ）の前に、少なくとも３つのオブジェクトからオブジェクトペアを選択するステップと、
前記ステップ（ｅ）の後に、少なくとも３つのオブジェクトからの各オブジェクトペアに対するステップ（ａ）乃至（ｅ）を繰り返すステップと
を更に含むことを特徴とする請求項１２記載の多面衝突検出方法。
【請求項１６】
前記オブジェクトのうち少なくとも１つのオブジェクトの位置あるいは方位を変更するステップと、
動作した前記オブジェクトの新最短特徴項を決定するステップ（ａ）乃至（ｅ）を繰り返すステップ
を更に含むことを特徴とする請求項１２記載の多面衝突検出方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はコンピュータで表現する動オブジェクト間の衝突の検出に関するものであり、具体的には、基本的な特徴項によって表現される多面体オブジェクト間の距離及び衝突に関するものである。
【０００２】
【従来の技術】
コンピュータグラフィックスシステムの多くは、例えばコンピュータゲーム、バーチャルリアリティシステム、アニメーション、及びシミュレーションの諸プログラムであるが、独立動作するオブジェクトを表現するものである。このようなシステムでは、相異なるオブジェクトの相互作用、例えば接触時点などを決定しなければならない。例を挙げると、２つのオブジェクトが衝突（collide）するとき、オブジェクト間に生じる力によって後続モーションが決定されることがある。この相互作用の決定を行うためこれまで様々なプロシージャが開発されてきたのである。
【０００３】
衝突検出、これはモーションプロセスの主要部であるが、多くのコンピュータグラフィックスのアプリケーションにおける主要課題である。衝突検出は、バーチャルリアリティ、アニメーション、及び実体指向アニメーション等の新アプリケーションの増加に伴い、その重要性は益々高まりつつある。境界表現によって定義された多面体モデルの場合、アルゴリズムは２つの主要カテゴリに分類されるが、１つは特徴項型で、もう１つは単一型である。両者の場合、オブジェクトがスペース内で連続動作を行うとき、コヒーレンスを用いて亜線形性能を得る。
【０００４】
多面体（polyhedron）の特徴項は境界を形成するエッジ［端］、バーテックス［頂点］、エッジ［端］、及びフェース［面］である。特徴項型アルゴリズムではこれらの要素に関し幾何学的計算が行われるが、この計算によって多面体ペアが分離しているか否か及び多面体間の距離計測の可能性を決定する。１つの例としてバラフ（Baraff）のアルゴリズムが挙げられるが、このことについてはD．Baraff, ″Curved Surfaces and Coherence For Non‐Penetrating Right Body Simulation,″ Computer Graphics, p. 19‐28（Aug. 1990）に記載されており、該アルゴリズムでは任意の１多面体の１フェース又は各多面体の1エッジをはめ込む分離状態の平面が維持されている。
【０００５】
リン・キャニー（Lin‐Canny）の最短特徴項アルゴリズム（記載文献： Ming C. Lin, ¨Efficient Collision Detection for Animation and Robotics,¨ PhD Thesis, University of California, Berkeley, December 1993）は、分離多面体間の距離を計測可能とする、より洗練された特徴項型アルゴリズムである。このアルゴリズムは最も速い該問題の解法の１つとして考えられており、Ｉコライド（I‐Collide）の名で知られているソフトウェアパッケージに収録されている。Ｉコライド衝突検出パッケージでは、リン・キャニーアルゴリズムを用いて低レベル衝突チェックを行う。リン・キャニーアルゴリズムでは、凸状多面体間の最短特徴項を追跡しキャッシュに記憶する。これらの特徴項は一端認識されると、該特徴項間の最短ポイントつまり多面体間の最短ポイントが決定される。
【０００６】
【発明が解決しようとする課題】
リン・キャニーアルゴリズムには重大な欠点が２つある。１つは多面体透過（penetrating）ケースを扱わないことである。仮にそのようなインスタンスが課されると、終了条件が満たされることがないので永久サイクルの状態に陥ってしまうのである。この状態を防止するには、反復回数が最大値に達した時点でリン・キャニーアルゴリズムを実行することである。該反復回数は一定のしきい値だが、必要となる特定構造体と厳密には関連しない。満足な結果を得るには、通常該しきい値は試行錯誤をしながら設定しなければならない。正確性を得るには、多サイクル状態の測定が終了出来るように反復回数値を十分高くしておかなければならない。高い反復回数値では、無限サイクルの決定プロセスは遅い。また、システムはいかなる透過深度も返さない。このように、リン・キャニー法の有効性には、ルート発見法による正確な衝突回数の決定及び標準階層技術を取り入れた非凸状多面体衝突検出の点で限界がある。もう１つの欠点は、リン・キャニーアルゴリズムの活性を欠いているということである。サイクル性状もまた幾何学的退化状態で起こり、サイクル検出は透過保証にはならない。アルゴリズムは、微妙に相互依存する多様な数値許容値を変更することによって調整することが出来る。不可能ではないにしても、すべてのアプリケーションに適値を採用するのは至難なことである。
【０００７】
リン・キャニー法が有する難しさは複雑性のコード化によって図解され、リン・キャニーアルゴリズム実行プログラムではその大部分が退化状態処理の修正に向けられている。このような問題があるにも拘らず、リン・キャニーアルゴリズムの持つ相対速度、及び該アルゴリズムを実行するＩコライドパッケージの持つ総合的な有効性は、各種の衝突検出アプリケーションで広く採用されようになったのである。
【０００８】
単体プロセスには別の限界がある。多面体特徴項に焦点を絞るより、単体型アルゴリズムではむしろポイント集合の凸包の処理を行い、これらのポイントのサブセットによって確定した単体の処理を行う。ギルバート（Gilbert）、ジョンソン（Johnson）、及びケアシ（Keerthi）によって設計され、¨A Fast Procedure for Computing the Distance  Between Complex Objects in Three‐Dimensional Space,¨ IEEE Journal of Robotics and Automation, p. 193‐203, April 1988に記載されている アルゴリズムが、単体型アルゴリズムとしては最古例の１つである。２つの多面体が指定され、ＧＪＫアルゴリズムでは、原点を囲んでいるか或いは原点に最短の、ミノコワスキ（Minokowski）差分多面体によって確定された単体の検索が行われる。ただしもし原点が囲まれていない場合は、原点と差分多面体の最短単体との間の距離は元の多面体間距離に同じである。原点が囲まれている場合は、両多面体が相透過して状態にあり透過測定が可能である。
【０００９】
ＧＪＫアルゴリズムはラビッツ リッチ（Rich Rabbitz）のアルゴリズム（記載文献： ¨Fast Collision Detection of Moving Convex Polyhedron,¨ Graphic Gems IV [Heckbert, ed.], p. 83‐109 [1991]）の実質的コアであるが、このアルゴリズムではコヒーレンスをより有効に利用して現物を進める。Qコライド（Q‐Collide）はＩコライドから生じた衝突検出ライブラリの１つだが、このライブラリによって低レベル衝突検出の面でリン・キャニーアルゴリズムがラビッツアルゴリズムに取って代わられている。大量オブジェクトを管理するためのQコライドのコード及びデータ構造すべてがＩコライドから直接移入されているのである。キャメロン スティーブン（Stephen Cameron）は最近ＧＪＫの最速の後継アルゴリズムを開発した（記載文献： ¨Enhancing GJK: Computing Minimum Penetration Distances Between Convex Polyhedra,¨ International Conference on Robotics and Automation, IEEE [April 1997] ）。このアルゴリズムにはコヒーレンスを活用するメカニズムが組み込まれており、またカレント単体が終了条件を満たすことに失敗したとき、より精確に代替の新単体を選択する位相バーテックス情報を用いている。これ等の改善によって、前記アルゴリズムではリン・キャニーアルゴリズム同等の概一定タイム複雑性が達成されている。
【００１０】
この発明は、上記のような課題を解決するためになされたもので、多面体間の衝突を決定するための現行方法における多くの欠陥を克服する多面衝突検出システム及び方法を得ることを目的とする。
【００１１】
【課題を解決するための手段】
この発明に係る多面衝突検出システムは、多面体を定義する複数の特徴項によってそれぞれ表現された少なくとも２つのオブジェクトの間の最短の特徴項を決定するシステムであって、２つのオブジェクトである第１多面体及び第２多面体から第１特徴項及び第２特徴項をそれぞれ選択する特徴項選択手段と、第１特徴項に対応する第１ボロノイ領域及び第２特徴項に対応する第２ボロノイ領域を決定するボロノイ領域決定手段と、第１特徴項の第１最短ポイントが第２ボロノイ領域に存在するか否かを決定するために第１特徴項を第２ボロノイ領域と照合する第１照合手段と、第２特徴項の第２最短ポイントが第１ボロノイ領域に存在するか否かを決定するために第２特徴項を第１ボロノイ領域と照合する第２照合手段と、第２ボロノイ領域に関連する第１特徴項の位置及び第１ボロノイ領域に関連する第２特徴項の位置に基づき、新第１特徴項及び新第２特徴項を選択する新特徴項選択手段と、エッジがボロノイ領域を出る出口ポイント及びボロノイ領域にエッジが入る入口ポイントを決定するために、エッジタイプ特徴項を他の特徴項のボロノイ領域に対してクリップする手段と、エッジタイプ特徴項及び他の特徴項の間の距離を入口ポイントにおける入口符号及び出口ポイントにおける出口符号として表現する関数の導関数符号を決定する手段と、入口ポイントに対応するボロノイ領域の平面を定める入口特徴項を決定し、出口ポイントに対応するボロノイ領域の平面を定める出口特徴項を決定する手段と、新特徴項選択手段に含まれ、第１特徴項あるいは第２特徴項がエッジタイプ特徴項のとき、新第１特徴項あるいは新第２特徴項を入口符号、出口符号、入口特徴項、及び出口特徴項に基づいて選択する手段とを有する。
【００１２】
また、第１照合手段及び第２照合手段は、特徴項間相互関係決定プロセスを識別するステート装置を含み、ステート装置の各ステートは第１特徴項のタイプ及び第２特徴項のタイプに基づく。
【００１３】
また、特徴項選択手段は、第１ボロノイ領域あるいは第２ボロノイ領域をそれぞれ確定する複数平面と、第１特徴項あるいは第２特徴項とを照合する手段と、第１特徴項あるいは第２特徴項による複数の平面のうち少なくとも１平面の侵害を決定する侵害決定手段と、侵害された複数の平面のうち少なくとも１つの平面に対して、第１特徴項及び第２特徴項に対応する第１最短ポイント及び第２最短ポイントのうち１つの相対位置を決定する手段と、第１最短ポイント及び第２最短ポイントのうち１つの相対位置に基づき、侵害された複数平面のうち少なくとも１つを確定する特徴項を選択する選択手段とを含む。
【００１４】
また、第１特徴項及び第２特徴項が各々エッジの特徴項のとき、侵害決定手段は、対応するボロノイ領域のフェース平面の侵害を決定する前に、対応するボロノイ領域のバーテックス平面の侵害を決定する。
【００１５】
また、少なくとも第１最短ポイントが第２ボロノイ領域内に存在せず且つ第２最短ポイントが第１ボロノイ領域内に存在していないとき、第１オブジェクト及び第２オブジェクトが透過しているか否かを決定する手段を更に含む。
【００１７】
また、少なくとも２つのオブジェクトからオブジェクトペアの選択を制御する手段、特徴項選択手段、ボロノイ領域決定手段、第１照合手段、第２照合手段、及び各オブジェクトペア間において最短特徴項が検出されるまで新第１特徴項及び新第２特徴項のうち１つが選択される選択手段の制御オペレーション手段を更に含む。
【００１８】
また、少なくとも２つのオブジェクトと２つのオブジェクトの最短特徴項を表示する表示手段を更に含む。
【００１９】
また、少なくとも２つのオブジェクト間の最短特徴項及び最短特徴項間の距離をアウトプットするアウトプット手段を更に含む。
【００２０】
また、オブジェクトを動作させる手段を更に含み、制御手段は、オブジェクトの各動作後の各オブジェクトペア間の最短特徴項を決定するために作動する。
【００２１】
また、ボロノイ領域決定手段によって決定するボロノイ領域を格納する手段と、対応オブジェクトの動作に基づく格納済ボロノイ領域を調整する手段とを更に含む。
【００２２】
また、各オブジェクトペア間の最短特徴項を格納する手段を更に含み、この手段によって、オブジェクトの動作後、格納手段で格納された各最短特徴項が第１特徴項及び第２特徴項として選択される。
【００２３】
また、この発明に係る多面衝突検出方法は、記憶部に記憶された第１多面体及び第２多面体を読み出し、多面体を定義する複数の特徴項によって表現された少なくとも２つのオブジェクトの間の最短の特徴項を演算処理手段で決定する方法であって、演算処理手段は、（ａ）第１多面体から第１特徴項を選択し、第２多面体から第２特徴項を選択するステップと、（ｂ）第１特徴項に対応する第１ボロノイ領域を決定し、第２特徴項に対応する第２ボロノイ領域を決定するステップと、（ｃ）第１ボロノイ領域を第１特徴項と照合し、第２ボロノイ領域を第２特徴項と照合するステップと、（ｄ）第２ボロノイ領域に関連する第２特徴項に最短の第１特徴項の第１ポイントの位置、及び第１ボロノイ領域に関連する第１特徴項に最短の第２特徴項の第２ポイントの位置に基づき、新第１特徴項あるいは新第２特徴項を選択するステップと、（ｅ）第１ポイントが第２ボロノイ領域内に存在し、第２ポイントが第１ボロノイ領域内に存在するまでステップ（ｂ）乃至（ｄ）を繰り返すステップとを有し、ステップ（ｃ）は、エッジがボロノイ領域に入る入口ポイント及びエッジがボロノイ領域から出る出口ポイントを決定するために、エッジタイプ特徴項を他の特徴項のボロノイ領域に対してクリップするステップと、エッジタイプ特徴項及び他の特徴項との間の距離を入口ポイントにおける入口符号及び出口ポイントにおける出口符号として表現する関数の導関数符号を決定するステップと、入口ポイントに対応するボロノイ領域の平面を定める入口特徴項を決定し、出口ポイントに対応するボロノイ領域の平面を定める出口特徴項を決定するステップと、ステップ（ｃ）に含まれ、第１特徴項あるいは第２特徴項がエッジタイプ特徴項のとき、新第１特徴項あるいは新第２特徴項を入口符号、出口符号、入口特徴項、及び出口特徴項に基づいて選択するステップとを含む。
【００２４】
また、ステップ（ｄ）は、第１特徴項あるいは第２特徴項を、第１ボロノイ領域あるいは第２ボロノイ領域をそれぞれ確定する複数平面の各平面と照合するステップと、第１ポイントあるいは第２ポイントによって侵害された複数平面のうち１つを確定する特徴項が、新第１特徴項又は新第２特徴項として選択されるステップを更に含む。
【００２５】
また、第１特徴項及び第２特徴項が各々エッジタイプ特徴項であるとき、照合ステップは、特徴項を対応するボロノイ領域のバーテックス平面と照合するステップと、特徴項をバーテックス平面と照合した後、特徴項を対応するボロノイ領域のフェース平面と照合するステップを含む。
【００２７】
また、少なくとも２つのオブジェクトは、少なくとも３つのオブジェクトが含まれ、ステップ（ａ）の前に、少なくとも３つのオブジェクトからオブジェクトペアを選択するステップと、ステップ（ｅ）の後に、少なくとも３つのオブジェクトからの各オブジェクトペアに対するステップ（ａ）乃至（ｅ）を繰り返すステップとを更に含む。
【００２８】
また、オブジェクトのうち少なくとも１つのオブジェクトの位置あるいは方位を変更するステップと、動作したオブジェクトの新最短特徴項を決定するステップ（ａ）乃至（ｅ）を繰り返すステップを更に含む。
【００２９】
【発明の実施の形態】
実施の形態１．
図１は本発明を実現するために使用可能なコンピュータシステム１を示す。もちろん、以下で説明する必要なデータの格納、それにデータ処理を行うことの出来るコンピュータ又はプロセッサであるならばいかなる型であっても使用することが出来る。図１では、中央演算処理装置（以降では「ＣＰＵ」とよぶ）１０によって、該ＣＰＵ１０に接続するメモリ２０に記憶された命令が実行されている。メモリ２０は処理対象となるデータをも記憶する。そのデータは、多面体（polyhedra）、多面体特徴項に対応するボロノイ（Voronoi）領域又はスペースの表現、照合の現状、及び最近接特徴項の表現を含む。本実施の形態においては、多面体は特徴項（エッジ［端］、バーテックス［頂点］、フェース［面］）で表現される。ＣＰＵ１０によって処理された命令は各オブジェクトの動き方を決定する。オブジェクトは多用な条件に基づいて動くことが可能である。その動き自体は本発明には含まれない。本発明はむしろ、指定するポイントと時間で動くオブジェクト間の相互関係に方向づけられる。一方、オブジェクト間の相互関係はモーションを決定するために使うことが出来る。例えば、各オブジェクトは衝突（collide）すると前のモーション又は衝突具合に順じた速度で逐次互いに離れていく。
【００３０】
ＣＰＵ１０にはディスプレイ３０も接続されており、該ＣＰＵが処理するデータを表現する。ディスプレイ３０ではいかなるタイプのデータの表現も可能である。例えば、オブジェクト及びそのモーションを表現することが出来る。図２では、処理及び表示の可能なオブジェクトを示す。オブジェクト１００、１２０、１３０はスクリーン上のパースペクティブビューとして表現されている。また、最短距離も最近接特徴項間のライン１２５で表示されている。仮に移動プロセスによって透過（penetration）することが可能であるならば、透過オブジェクト１００、１１０は透過状態で表現することが可能であり、そして透過程度１３０の表現が可能である。さらに、透過オブジェクトの表現の調整、例えばカラーの変更などを行い透過を表現することも可能である。
【００３１】
多様な入力装置４０や出力装置５０をＣＰＵ１０に接続してシステムとの情報交換が可能である。このように、オブジェクト間の相互関係は、出力装置５０を介して出力し、他の様々な装置やプロセスにおいて使用することが可能である。入力装置４０は、オブジェクトに関するデータを提供するために使用出来る。あるいは、オブジェクトのモーションはシステム１に対して外部的に決定することが出来る。モーションを入力装置４０を介して提供し、そしてシステムによって決定したオブジェクト間の相互関係を出力装置５０を介して出力するのである。
【００３２】
本発明のプロセスはオブジェクト表現を適用した理論を関連づけて理解するのがベストである。もちろん、本発明は技術スキルによって他の様々なオブジェクト表現に変更することが可能である。１つの表現によれば、Ｒ3の凸状多面体の境界はバーテックス、エッジ、それにフェースを有している。これらの特徴項が凸集合である。多面のエッジはテイルポイントからヘッドポイントに至るベクトルで表現する。エッジに沿ったポイントは、０と１との間のスカラ値によってパラメータ化し、テイル・ヘッド間のユニット化した距離を表すことが可能である。
【００３３】
近傍特徴項とは隣接する特徴項のことである。近傍関係はシンメトリックである。１つのバーテックスの近傍項はそのバーテックスに付帯する。フェースの近傍項はフェースを境界づけるエッジである。１つのエッジには厳密に言うと４つの近傍項、つまりエンドポイント部の２つバーテックス、及びエッジが境界づける２つのフェースがある。多面の特徴項は閉集合として扱われる。したがって、１つのフェースは境界づけるエッジを含み、１つのエッジはバーテックスのエンドポイントを含むことになる。
【００３４】
ボロノイ領域及び平面は本発明の運用にとって中核をなすものである。凸状多面体の特徴項では、ボロノイ領域は多面体外側のポイント集合であり、それは他のどの多面体特徴項の場合も同じ程度に近接している。近傍特徴項ＸＹ間のボロノイ平面は、Ｘ及びＹ上のボロノイ領域を有する。ボロノイ領域はすべてボロノイ平面によって境界づけられ、そしてオブジェクトの特徴項はすべて多面体外側の全体のスペースを集合的に包含する。近傍特徴項間のボロノイ平面は、バーテックス・エッジ平面及びフェース・エッジ平面の２種類に分類される。バーテックス・エッジ平面はバーテックスを有しエッジに対して垂直であるが、フェース・エッジ平面はエッジを有し垂直なフェースに平行である。バーテックスＶのボロノイ領域は同質平面集合によって境界づけられ、各平面はＶとその近傍エッジとの間のバーテックス・エッジ平面である。エッジＥのボロノイ領域は４つの平面によって境界づけられている。つまり、２つのバーテックス・エッジ平面及び２つのフェース・エッジ平面である。ｓ側フェースＦのボロノイ領域はｓ＋ 1平面によって境界づけられている。つまり、Ｆを境界づけている各エッジ、Ｆ自体のサポート平面であり、ＶＲ（Ｆ）は半無限多面プリズムである。図３乃至図５はそれぞれ立法体オブジェクトのバーテックス、エッジ、及びフェースのボロノイ領域を示す。
【００３５】
本発明はボロノイ領域に関する基本法則に基づくものである。仮にＸとＹが分離凸状多面体から選択された特徴項ペアである場合、ｘとｙはＸＹ間の最近接である。仮にＹのボロノイ領域にｘが存在し、Ｘのボロノイ領域にｙが存在する場合、ｘとｙは大局的に多面体間ポイントの最近接ペアになる。この法則では、ｘとｙ上の最近接ポイントの特異性は問われないが、退化状態ではこの限りではない。しかしこの法則の条件に合致すれば、ｘとｙに少しでもより近く接する２つの多面体からのポイントペアは１つも無いことになる。リン・キャニーアルゴリズムのように、本発明では基本法則の条件を満たす２つの特徴項を探求する。各反復において、本発明ではカレント特徴項ペアが条件に合致するかをテストする。もし合致しない場合は、1つの特徴項は通常近傍の特徴項に更新する。旧特徴項よりも高次元の新特徴項への更新処理においては、特徴項間の距離が短縮するだけである。新特徴項が旧特徴項よりも低次元である場合は特徴項間の距離は変わらないが、それは旧特徴項は新特徴項を含むことになり新特徴項は接近不可となるからである。しかしそのような更新は最短ポイントの局所化の改善することはなく、しかも特徴項間距離の短縮を余儀なくする更新を次々に誘発する可能性がある。そのようなリン・キャニーアルゴリズムとは対照的で、本発明では特徴項の最短ポイントを計算することなど皆無である。このことによって、退化現象に際しアルゴリズムに活性を与えるのである。更に本発明では分離多面体に依存することはなく、透過に際しての適切な特徴項ペアに焦点を絞る。
【００３６】
図６はステートダイアグラムであるが、任意に選択した特徴項に基づいて最短ポイントを決定するアルゴリズムオペレーションを示す。２１０乃至２１４の各ステート（state）は、構成可能な特徴項タイプの組み合わせ、照合される各多面体の代表である。例えば、Ｖ−Ｆ２１０ステートでは、一方の特徴項がバーテックスであり他方の特徴項がフェースである。矢線２２０，２３０は１つのステートから別のステートへ更新可能な更新ステップを示す。実線矢線２２０は特徴項間距離を短縮する更新を示し、破線矢線２３０は特徴項間距離を変更しない更新を示す。アルゴリズムの４つの一次ステートはＶ−Ｖ，Ｖ−Ｅ，Ｅ−Ｅ，それにＶ−Ｆであり、これらのうち任意の１つのステートでアルゴリズムは終了する可能性がある。第５ステート２１１即ちＥ−Ｆは特別で、多面体の透過がない限りアルゴリズムは該ステートで終了することはない。先行技術のアルゴリズムと異なり、本発明のアルゴリズムは終了することが必須である。図６に示すように、破線矢線のみを含むサイクルはない。グラフを通していかなる無限パスも実線矢線の無限ナンバを有し、その各々が特徴項間距離の短縮を示している。特徴項ペアの有限ナンバのみを有しているので、距離の無限短縮はありえないのである。
【００３７】
図７は最短２つの多面体の最短特徴項を決定する全体的プロセスを示す。先ずステップ３００において２つの特徴項を選択する。初めは特徴項をランダムに選択することが可能である。後続する反復では前回の最短特徴項を初期の照合特徴項として使うことが可能である。ステップ３０５ではテストを行い、２つの特徴項間の各最短ポイントが他方の特徴項のボロノイ領域内に存在しているかを確認する。両ポイントが対応する領域内に存在している場合、それは定理に準じておりカレント特徴項が最短特徴項である。そしてプロセスはステップ３２０で終了する。もちろん、その最短特徴項は出力することが可能であり、例えば表示用としてシステムで利用することが可能である。両最短ポイントが他方の特徴項のボロノイ領域内に存在していない場合、一方の特徴項は同多面体の新特徴項を使用して更新する必要がある。先ずステップ３０７において、システムによってどちらの特徴項が透過されているか確認される。透過されていなければ、ステップ１０において、どちらのボロノイ平面が侵害（violate）されているか、つまり最短ポイントがボロノイ平面に関係する方向が確認される。ステップ３１５においては、侵害されたボロノイ平面に対応する特徴項を照合用の新特徴項として選択する。そしてプロセスはステップ３０５に返る。プロセスは最短特徴項が発見されるまでループすることになる。
【００３８】
実際のプロセスではステップ３０５、３１０、及び３１５は照合している特徴項タイプに依存する。図６に示すように、５つの可能なステート２１０乃至２１４が存在し、異なる照合に関連づけられている。図８乃至図１２は前記各ステートにおける実際のプロセスステップに関連する。これらの各ステートにおける関数は次の３種のうちの１つの値を返す：〔終了（DONE）〕は定理条件に適合したことを意味し、ステップ３０５の真レスポンスに対応する；〔透過〕（PENETRATION）は透過ウィットネス（witnesses）が発見されたことを意味する；〔続行（CONTINUE）〕は、定理条件に適合せず、特徴項が１つ更新され、そしてプロセスが続行する必要のあることを意味する。
【００３９】
図８はバーテックス・バーテックスステート２１３に対応する。ステップ４００においては、バーテックスＶ１の１つを他方のバーテックスＶ２のボロノイ領域と照合する。バーテックス特徴項は、ポイント１つのみを有する、このことは他方の特徴項のボロノイ領域に存在する構成メンバとして簡単にテストされる。Ｖ１がＶ２の近傍エッジＥに対応するボロノイ領域の平面外に存在している場合、Ｖ１のほうが間違いなくＶ２よりもＥに近い、つまり平面はステップ４０２において侵害されたのである。この場合は新特徴項（ステップ４０３）としてＥを選択し、そして主プロセスを続行する（ステップ４０４）。もしＶ１がＶ２のボロノイ領域内に存在する場合、Ｖ２をＶ１のボロノイ領域と照合する。同様に、Ｖ２が１つのＶ１ボロノイ平面外に存在する場合、近傍エッジＥを新特徴項として選択する（ステップ４０９）。もしいずれのバーテックスもエッジに更新しない場合は、Ｖ１及びＶ２は相互のボロノイ領域に存在しており、プロセスは終了する（プロセス４１０）。
【００４０】
図９はバーテックス・エッジステート２１２のプロセスを示す。上述のように、１つのバーテックスがボロノイ領域に存在するか否かを確認するのは単純である。バーテックスをエッジの各ボロノイ平面と照合するのである。もし平面１つでも侵害されていれば、Ｅを新特徴項に、つまり侵害された平面に対応するバーテックスかフェースのいずれかに更新し（ステップ４２３）、そしてプロセスを新ステートで続行する（ステップ４２４）。もしバーテックスがエッジのボロノイ領域内に存在する場合、エッジをバーテックスのボロノイ領域と照合する。エッジとフェースをボロノイ領域と照合するのはエッジの場合よりも難しい。平面が侵害されているかを確認するには、その平面に対してエッジをクリップする。クリッピングプロセスを図１３及び図１４に示し以下で説明する。
【００４１】
図１３はフェースに対するボロノイ領域に対するクリッピングプロセスを示す。クリッピングプロセスによってボロノイ領域におけるエッジの入出口を決定する。エッジは方向性があるのでテイルｔとヘッドｈを有する。エッジの任意ポイントは０と１との間の値λによって表すことが可能である。そしてエッジはパラメトリック方程式ｅ（λ）で表す。クリッピングプロセスによってλの値を決められるが、エッジはボロノイ領域λ１に入りボロノイ領域λ２から出ることになる。ボロノイ平面に対応し交差する近傍特徴項Ｎ１、Ｎ２はこのプロセスによって決定する。
【００４２】
ステップ４２７（図９）では近傍特徴項の照合を行う。エッジが全体的にバーテックスのボロノイ平面の外に存在する場合、つまりＮ１＝Ｎ２≠０の場合、該平面に対応するエッジはバーテックスに代わって新特徴項となる。エッジがバーテックスのボロノイ領域に入り又それから離れることによってボロノイ平面と交差する場合、つまりＮ１≠Ｎ２の場合、該平面に対応するエッジは該バーテックスに代わって新特徴項になる。エッジがバーテックスのボロノイ領域に入り又その領域から離れることによってボロノイ平面と交差する場合、つまりＮ１≠Ｎ２の場合は、エッジ・バーテックス間の距離を表す距離関数の導関数値はステップ４３０においてλ１及びλ２との照合が行われる。また、導関数が負の場合、Ｎ２は新特徴項である。このことは、もちろん、Ｎ１及びＮ２がヌルであることを否定するものではない。導関数の確認において新特徴項を選んだ場合、プロセスは続行する（ステップ４３３）。そうでなければ、エッジ上の最短ポイントがボロノイ領域内に存在する理由でプロセスは終了する（ステップ４４４）。
【００４３】
図１０はバーテックス・フェースステート２１０におけるプロセスを示す。最初に、バーテックスとフェースのボロノイ平面との照合を行う。しかし、ＶをＦのボロノイ平面に対するテストにおいては、最初の侵害されたボロノイ平面ではアルゴリズムは停止せず最大限に侵害された平面を検索する。このことによって、バーテックスがフェースのエッジの反対側に存在しフェースの異なる部分又はエッジにより近くに存在するという状態は無効になる。このようにして、Ｆが更新される場合は特徴項間の距離の拡大は起こらないのである。バーテックスがフェースのボロノイ領域内に存在する場合は、フェースはバーテックスのボロノイ領域と照合しなければならない。これはバーテックスの近傍エッジをフェースと照合することによって可能になる。ステップ４５５における検索はＦ方位のＶ付帯のエッジに対して行う。これはＦからＶへの最短ポイントがバーテックスのボロノイ領域内に存在することの確認と同等である。もしフェースに向かうエッジが発見された場合、該エッジが新特徴項になる。そのようなエッジが発見されない場合は、ステップ４６０においてバーテックス・フェース間の距離の確認を行う。バーテックス・フェース間の距離が正の場合、最短特徴項ポイントが発見されることになる（ステップ４６２）。しかし、前記距離がゼロ又は負の場合、多面体が透過しているか或いは局所極小が存在する可能性がある。透過と局所極小については以下で説明する。
【００４４】
図１１はバーテックス・バーテックスステート２１４におけるプロセスを示す。先ず、重要なことは２つのバーテックス・エッジ間ボロノイ平面を扱うことにある。ステップ４７０ではＥ２エッジの１つを他のＥ１エッジのバーテックスボロノイ平面にクリップする。Ｅ２を完全にクリップした場合、つまりＥ２全体をボロノイ領域外に位置づけた場合は侵害された平面の対応するバーテックスがＥ２に代わって新特徴項になる（ステップ４７３）。さもなければ、距離関数の導関数をクリップポイントにおいて確認しなければならない。上述のように、もし導関数がλ１において正、或いはλ２において負の場合は対応するバーテックスは新特徴項になりプロセスは続行する（ステップ４７８）。次に、ステップ４８０において、Ｅ１のフェースのボロノイ平面に対してクリップする。繰り返すけれども、もしＥ２全体が他の平面によってクリップされた場合は対応するフェースは新特徴項になる（ステップ４８３）。さもなければ、交差ポイントの導関数を再確認する。もし新特徴項がＥ２とＥ１ボロノイ領域との照合において未選択の場合、エッジは相互交換され（ステップ４９５）、Ｅ１とＥ２ボロノイ領域との照合を行う。その照合の後、もし新特徴項が１つも形成されない場合（ステップ４９０）は最短特徴項が発見されたことになりプロセスは終了する。
【００４５】
最後に、図１２はエッジ・フェースステート２１１におけるプロセスを示す。上述したように、プロセスは該ステートでは終了不可能である。プロセスは、多面体が透過していることで終了するか、或いは特徴項間距離を変えることなく特徴項を低次元近傍項に更新する。先ず、ステップ５００において、係るフェースのボロノイ平面に対してエッジをクリップする。Ｅを完全にクリップし全体を係るフェースのボロノイ領域外に位置づけた場合、最短の近傍エッジ或いはエッジＥに対するフェースのバーテックスは新特徴項になる（ステップ５０３）。もしＥが領域と交差する場合、Ｅの交差ポイントからＦの平面への距離Ｄ１、Ｄ２を計算する。もし両距離が正でなく負の場合（ステップ５０７）、エッジＥはＦに貫入し〔透過〕（PENETRATION）が返る。さもなければ、特徴項間の距離を変更せずＦをその境界エッジ更新するか或いはＥをそのエンドポイントに更新する。特徴項の更新は、導関数ｄ１、ｄ２及びクリッピングプロセスによって決定した交差ポイントλ１、λ２の対応する近傍特徴項に基づいて行う。もしＤ１が非負であり（ステップ５１２）Ｎ１がヌルでない（ステップ５１４）場合、Ｎ１がフェースの新特徴項になる（ステップ５１５）。もしＤ１が非負でありＮ１がヌルである場合、エッジのテイルバーテックスが新特徴項になる（ステップ５１８）。もしＤ１が負でありＮ２がヌルでない場合（ステップ５２０）、Ｎ２がフェースの新特徴項になる（ステップ５２１）。もしＤ１が負でありＮ２がヌルである場合（ステップ５２０）、ヘッドバーテックスが新特徴項になる（ステップ５２５）。
【００４６】
上述したように、本発明の主部はボロノイ領域に対するエッジのクリッピングプロセスを採用することにある。図１３はフェースのボロノイ領域に対するクリッピングプロセスを示す。クリッピングプロセスによってボロノイ領域におけるエッジの入出口を決定する。エッジには方向性があるのでテイルｔとヘッドｈを有する。エッジの任意ポイントは０と１との間の値λによって表すことが可能である。そしてエッジはパラメトリック方程式ｅ（λ）で表す。クリッピングプロセスによっての値を決められるが、エッジはボロノイ領域λ１に入りボロノイ領域λ２から出ることになる。このプロセスを図１４に示す。
【００４７】
ＳはＸのボロノイ領域を境界づける定方位平面セットのサブセットである。Ｓ内の各平面は該領域内で必要な１次不等式の制約条件に合致したものでなければならない。集合的に、Ｓ内の平面によって凸状領域Ｋを決定する。もしＥがエッジの場合、Ｅと領域Ｋの交差部は空か或いはλ１からλ２へ向かうＥに沿ったラインセグメントかのいすれかである。また、交差部が空でない場合、Ｘの近傍特徴項Ｎ１、Ｎ２はＥをクリップする平面に対応する。Ｅは、Ｎ１のボロノイ平面と交差するのでＫに入り、Ｎ２のボロノイ平面と交差するので出ることになる。
【００４８】
ステップ６００ではボロノイ平面Ｐの１つを選択する。平面すべてを処理するので、初期に選択した平面は問題とはならない。ステップ６０２では初期パラメータを設定する。λ１及びλ２は各々０及び１に設定するが、これらはエッジのテイル及びヘッドに対応する。Ｎ１及びＮ２は両者ともゼロに設定するが、これらは近傍平面も交差平面も表すものではない。もし両距離ｄｔ、ｄｈが負の場合、Ｎ１、Ｎ２の両者とも選択した平面の近傍項に設定し、完全にボロノイ領域外に存在するという理由でエッジ全体がクリップされたものと見なされる（ステップ６０８）。もしｄｔが負（ｄｈは正）の場合、ステップ６１２乃至６２０の処理を行う。一方では、もしｄｈが負（ｄｔは正）の場合、ステップ６２４乃至６３２の処理を行う。処理するステップは相似する。先ず、パラメータλはｄｔ及びｄｈに基づいて決定する（ステップ６１２、６２４）。これらのステップにおける除算はステップ全体で唯一のものである。除算子の絶対値としては非ゼロで且つ被除数の絶対値より小さくない値をとる。そうすればオーバーフローは起こらない。もしλ及びＮ１がλより大きい場合（ステップ６１４）は、ステップ６１６においてλにλ１を再設定し選択した平面Ｎの近傍特徴項にはＮ１を設定する。ステップ６１８ではλ１をλ２と照合する。もしλ１がλ２を超している場合は交差ポイントがボロノイ領域外に存在し、エッジ全体がクリップされることになる（ステップ６２０）。
【００４９】
同様に、ステップ６２４においてλをλ２と照合する。もしλがλ２より小さい場合、λ２がλになりＮ２がＮになる。このステップにおいてもλ１がλ２を超している場合（ステップ６３０）はエッジ全体が領域によってクリップされることになる（ステップ６３２）。
【００５０】
１つの平面を処理すると、別の平面がステップ６４０において選択される。このプロセスは平面全数を認識し終えるまで繰り返される。平面全数を一度認識すると、エッジは完全にクリップされていないと見なされるが（ステップ６３６）、これは少なくともエッジが部分的にボロノイ領域に存在していることを意味する。λ１、λ２、Ｎ１、及びＮ２の最終値は交差ポイント及び交差平面の近傍項に対応する。これらの値は、上述したように、新特徴項の認識に使われる。
【００５１】
エッジが完全にクリップされない場合は、該エッジと特徴項との相互関係に関する一定の情報を決定することが出来る。具体的には、上述したように、適切な新特徴項を決定するためにエッジと別の特徴項との距離の導関数を必要とする。しかし、実際には或る一定のポイントにおける導関数符号を決定しなければするならない。その符号は厳密に導関数計算することなく簡単に決定することが可能である。エッジ距離関数は、距離とはｅ（λ）とＸとの間の距離であるが、次のように決定する。
【００５２】
【数１】
0004115005.tif 000002
【００５３】
このエッジ距離関数は連続関数であり凸関数である。また、ｅ（λ0）がＸの一部でない場合、λ0における微分は不可能である。選択する近傍特徴項を決定するには、エッジ距離関数の極小値がエッジのクリップ部であるかが問題になる。その問題の答えはλ１及びλ２における導関数符号を調べるだけで得ることが出来る。極小は、区間［０、λ１］で起こるのはＤ’(λ1） >０の場合のみであり、区間［０、λ２］で起こるのはＤ’(λ2) <  0の場合のみである。これはステップ４３０（図９）、４８５（図１１）、及び５１０（図１２）の基礎になる。Ｘを近傍特徴項に更新した場合しても特徴項間距離は変化しないが、それは該近傍特徴項がＸよりも低次元のときであり、また該距離が短縮するしかない該近傍特徴項がＸよりも高次元のときである。若しＸが更新されない場合は、ＥからＸへの最短ポイントはＫ内に存在する。エッジの距離関数符号を求める式は基本幾何学に基づく。ｕをＥ方位、つまりテイルからヘッドに向かうベクトル化する。若しＸが位置ｖにおいてバーテックスの場合、sign [Ｄ(λ)] = sign [u・(e(λ) ‐ v)]である。同様に、Ｘが外向き法線ｎの平面Ｐ内のフェースである場合は次の式になる。
【００５４】
【数２】
0004115005.tif 000003
【００５５】
Ｘがエッジである場合の式は不要である。この場合の導関数は、関連する近傍特徴項に関する評価が可能でありバーテックス或いはフェースでなければならない。この近傍特徴項に関する導関数は、Ｅの交差するボロノイ平面のポイントに関する導関数と同じである。
【００５６】
導関数方程式は、距離関数がｅ（λ）において微分化不可能な一定の退化状態では無効にすることが可能である。ただしこの場合は、エッジＥが別の特徴項と交差する理由で、アルゴリズムでは単純な透過報告を行うことが可能である。
【００５７】
エッジを完全にクリップすると、特徴項は更に更新されることがある。２つの状況においてＥが完全にボロノイ領域の外に存在する。１つは、Ｅの両エンドポイントが単一ボロノイ領域の「外」に存在することが発見された時点で単純排他という事象が検出された状況である。もう１つは、複合排他という事象がλ１がλ２を超えた時点で複合排他という事象が検出された状況であるが、これはＥの何れのポイントもボロノイ平面によって課された制約条件を同時に満たしていないことを意味する。この２つの状況はＮ１＝Ｎ２であるか否かによって区別する。何れの場合もＸは更新されなければならない。注意を要するのは、バーテックス・エッジボロノイ平面とフェース・エッジボロノイ平面との間に差が若干あることである。バーテックス・エッジボロノイ平面によって半スペースを２つ決定される。一方の半スペース内のポイントはエッジにより接近しているが、他方の半スペース内のポイントはエッジ又はバーテックスから同距離である。このようにしてバーテックス・エッジボロノイ平面平面はスペースを区切らないのである。ボロノイ平面の何れかの側にあるポイントはエッジよりもフェースの方により接近している可能性がある。これらの結果として、エッジがバーテックス・エッジのボロノイ平面に交差するか否かに関係なく、又たとえ対応のボロノイ領域間の境界において交差していなくても、導関数チェックプロセスが有効となるのである。対照的であるが、もしエッジがフェース・エッジボロノイ平面と交差している場合、導関数によってボロノイ領域間境界で交差しているときに限り各ステップが有効になることのチェックと更新が行われる。
【００５８】
もしＥが完全にバーテックスＶのボロノイ領域外に存在している場合、更新は問題なく行われる。単純排他の場合はエッジＥ全体がバーテックス・エッジボロノイ平面のエッジ側に存在する。Ｅの各ポイントはＶよりも近傍エッジの方により接近する。複合排他では、両平面交差がバーテックス・エッジのボロノイ平面に対して行われるために、導関数チェックプロセスの手段がとられるのである。
【００５９】
すでに上述したように、多面体透過は特殊なケースである。本発明では基準があるために更新特徴項を用いるが、多面体透過は特に苦労することなく効率よく行うことが出来る。エッジをフェースに対してクリップするときは、エッジ上の交差ポイントに対して、Ｆの平面に対する面方位相対性テストを行う。もしそれらの交差ポイントが反対側に存在する場合、ＥはＦに貫入しているはずでアルゴリズムは透過ウィットネスとして２つの該特徴項と共に終了する。
【００６０】
しかし、特徴項の更新プロセス中にバーテックス・フェースステートにおける局所極小内でロッジ現象が起こる可能性がある。これは透過が要因となって起こるもの推定される。このロッジ現象が起こるのは、バーテックスがフェースのボロノイ領域のフェース・エッジ平面制約条件に合致する場合、バーテックスがＦの平面の「下」に存在する場合、そしてバーテックスがＦ起点に方位づけられたエッジを擁する場合である。この状況では、いかなる近傍特徴項への更新であっても特徴項間の距離を拡大するか或いは特徴項間の距離は一定化するが、特徴項サイズを拡大することになるである。これらは何れも有効な更新ではない。アルゴリズムがそのような状態になった場合は、多面体が透過するのか否かは多面体の別の特徴項に依存することになる。それらの多面体が透過している場合はアルゴリズムは終了しその旨通知するべきである。さもなければ、局所極小を避ける別の新特徴項ペアが発見されなければならない。図１５は透過または局所極小の有無を確認するプロシジャを示す。バーテックスＶはフェースＦを含む多面体の各平面に対してテストされる。もしＶがすべての該平面の負側に存在する場合、Ｖは多面体内に存在し透過フラグが返される（ステップ７３５）。さもなければ、Ｖ起点の最大符号化距離を有するフェースが新特徴項になる。もし該フェースが更新されていれば、Ｖは少なくとも他のＦの多面体の何れのフェースに対する場合と同等の位置に接近しているはずである。本発明によって次の２つの何れかの状態における透過が検出される。それは、エッジ・フェースステート（ステップ５０９）においてエッジがフェースに貫入している状態、或いはバーテックス・フェースのステート（ステップ７４０）において１つのバーテックスが他方の多面体内に存在する状態である。多面体がそのサイズに応じて少量透過している場合は、ウィットネスペアはエッジ・フェースになる。１つの多面体がほぼ完全に他方の多面体を通過する場合のみバーテックス・フェース透過ウィットネスが生じる可能性があるのである。
【００６１】
本発明のプロセスは多面体表現及びボロノイ領域表現から独立したものである。システムは関連するボロノイ平面を単純に決定出来るものでなければならない。またシステムによって単に最短の特徴項を決定するだけである。それらの特徴項は多様な方法で表現オブジェクトの表示又は制御に用いられる可能性がある。本発明は動オブジェクトの場合も利用することが可能なので、最短の特徴項はオブジェクト動作の点で異なる反復数で繰り返される。コヒーレンスはプロセス間に最短特徴項ペアをキャッシュに順次記憶させることによって活用される。このことによって動作する特徴項の更新プロセスを促進する。特徴項ペアの始動する手段は、アルゴリズムによって任意の始動ペアから１つの最短特徴項に収束されるので決定的なことではない。同様に、各特徴項のためのボロノイ平面及びその領域を表現するデータは記憶しておくことが出来る。この手段によれば、オブジェクト動作が現ポジションから新ポジションへの変形として表現する場合、同じ変形を使用して簡単にボロノイ平面及びその領域も表現することが可能である。
【００６２】
本発明のプロセスを先行技術システムと比較することによって相対速度を決定した。異なる衝突検出アルゴリズム間の速度の照合は難しいものであるが、この文献は非矛盾クレイムというものではではない。アルゴリズムの速度は報告されている結果の中でも可変的な多くの要因に大きく依存する。具体的な問題インスタンスとしては、どのようにしてオブジェクトを形成するか、またどのようにしてオブジェクトを収集するかである。さらに、実施上の問題点としては、言語、コンパイラ、オプティマイザ、浮動小数点数フォーマット、インラインコード及びハンドコードアッセンブリ命令の量、等が挙げられる。
【００６３】
最初の一連のテストは、コヒーレンスの可変レベルにおける多様な問題の中で性能を測定するために設計した。テストを設計するタスクは単純なものにしたが、それはテストするアルゴリズムには数千のオブジェクトを扱う、Ｉコライドのような完全衝突検出パッケージとして意味をなすものは１つもなく、本件のようなシステムではむしろ最低レベルの衝突検出ルーチンをアルゴリズムだからである。このような観点では、該タスクはオブジェクト２つのみが関係するシステムのアルゴリズムをテストするのに十分なものである。各テストにおいては、オブジェクト１を起点に固定し、それに同形のオブジェクト２を周囲のスペースを通して連続する方向に置いた。それがまた軸の周囲を回転したのでオブジェクト２の中心の３つの座標は正弦状に変形した。テストは４つの異なるオブジェクトに対して行った。普通の立方体を最初のテスト対象形として採用したが、それは衝突検出の応用では通常境界づける直方体が使われるからである。中位複雑性モデルとしては通常の二十面体（２０三角フェース）を採用した。３番目のテスト対象形として多面平円盤（polygonized disk）を採用した。平円盤の厚さに対するアスペクト比率は１０：１であった。このテスト対象形の識別特徴は、高位複雑性のフェースを有し、２つのフェースが６０辺ポリゴンであるということである。最後に、高位オーバーロール複雑性モデルとして６４２個のバーテックス、１９２０個のエッジ、及び１２８０個の三角フェースを有するモザイク模様の球体を採用した。各アルゴリズムは同一セットの問題インスタンス上を動作したのでる。
【００６４】
コンピュータ処理速度のベンチマークとしては小数点演算回数が用いられた。小数点演算はアルゴリズムすべてにおいて優性コストであり、言語、コンパイラ、オプティマイザから独立したものである。加算（減算及び照合処理を含む）は最も共通した小数点演算であり、次いで共通であったのが乗算である。全アルゴリズムでは、これら２つのカテゴリの比率は大体同じで、両方で全小数点演算の少なくとも９８％を占めた。テスト結果は、立方体、二十面体、球体、及び平円盤の各々について図１６乃至図１９に示されている。リン・カニーのアルゴリズムと本発明のアルゴリズムに関して、報告された集計には最短ポイントのコンピュータ処理コストを含んでいるが、該アルゴリズムではそれを除いては距離計算が不可能だからである。拡張ＧＪＫではそれが可能であるが、各テストでは最短ポイントを必要としない。各テストにおいて、既存システムによる本発明が高性能であることが示されたのである。
【００６５】
上述のテストにおいてアルゴリズムの精度に関するデータを収集する機会も得ることが出来た。これら３つのアルゴリズムによって報告された距離は各プロセスの後に統一性に関してチェックした。各アルゴリズムの結果は３つうち任意のアルゴリズムによって返された極小結果に対して照合され、差分が前決定許容値１０‐6を超えた場合は警告フラグが立てられた。本発明は最高の性能を発揮し、１００万回のプロセスにおいて警告が１つも生成されなかったのである。拡張ＧＪＫはほぼパーフェクトで、警告は１１件だけ生成され、距離偏差値は最大で１．６×１０‐4であった。これらの警告は、実施において主要数値許容値を１０‐5から１０‐7に下げた時点ですべて消滅した。リン・キャニー方式の場合は最悪の性能結果で、警告が２０８件も生成され、距離偏差値は１０‐2にもなった。リン・キャニー数値許容値を変える試行を数回行うことによって警告件数は８８まで減少した。
【００６６】
２番目のテストでは退化状態にあるアルゴリズムの活性の検証を行った。各テストにおける１０，０００回にわたるトライアルでは、２球体の間における衝突検出の実行中、境界ケースの検索も必要とした。第一オブジェクトを原点に置いた状態で、第二オブジェクトのポーズを接近（ｎｅａｒ）平行エッジ及びフェースを選ぶディストリビューションからランダム選択したポーズ２つの間に内挿する。アルゴリズムによって返されたコヒーレンスデバイスをセーブするが、これらのものが本発明及びリン・キャニー方式の最短特徴項ペアでありＥＧＪＫの場合の単体ペアなのである。２進検索法を用い誘導したものはこれらの変更した特徴項又は単体である。そのような境界ケースは恐らく不規則性状になる部分なのである。
【００６７】
このテストによってすぐ判明したのがリン・キャニーアルゴリズムの退化現象問題である。前回の実験において警告メッセージ件数を極小化したような数値許容値を設定することによって、サイクリング性状を４４８９回のトライアルで観察した。許容値を変えてこの回数を３７に減少させたが、報告された距離の精度が著しく低下し、リン・キャニーアルゴリズムによって返された大変な異常距離が２２トライアルにおいて生じた。拡張ＧＪＫでは１０‐7に設定した主要許容値ではいかなるサイクリングも異常距離も示さなかった。しかし、１０‐8に設定した許容値では、球体間の実際の距離が４−２√３より減少することは全くなかったにも拘らず、拡張ＧＪＫでは１７５回のトライアルにおいてゼロ距離（透過）が報告されたのである。本発明では、調整する許容値を用いない状態で、いかなるサイクリングも示すことなく、検出可能な異常距離が１つも報告されなかったのである。
【００６８】
本発明の実施例を幾つか説明してきたこの時点では、当業者にとっては本説明は単に例証的であり限定するものではないことが明らかであろうが、それは例としてのみ提示してきたからである。多くの変形及び他実施例が技術面の通常スキルの範疇に属し、又上記の特許請求の範囲において決定した本発明の範疇に属するものと考えるのである。
【００６９】
【発明の効果】
本発明の多面衝突検出システム及び多面衝突検出方法によれば、最短特徴項アルゴリズムは、ボロノイ平面及びその領域を利用するが、多面体間距離の決定基盤をシステムに提供するものである。システムは多面体の特徴項に対応するボロノイ領域を決定する。もし２つの多面体からの２つの特徴項間の最短ポイント２つが相互のボロノイ領域内に存在している場合、該特徴項が最短特徴項になる。この条件に合う２つの特徴項を決定することによって最短特徴項が配置される。
【００７０】
また、本発明の多面衝突検出システム及び多面衝突検出方法によれば、対応する他の特徴項は、照合されているカレント特徴項の結合及び２つの特徴項の近接度に基づいて認識される。隣接の特徴項がより近いものとして選ばれるが、これは、距離を拡大することなく、一方の特徴項のサイズが縮小する場合或いは該距離が該サイズの拡大のために縮小するだけの場合に限られる。この方法によって、リン・キャニーアルゴリズムにおいて両特徴項が等距離に存在するときに起こるようなシステムのサイクル現象を免れるのである。
【００７１】
また、本発明の多面衝突検出システム及び多面衝突検出方法によれば、第１多面体のエッジ特徴項と第２多面体の特徴項を擁するボロノイ領域の相互関係はクリッピングプロセスを行うことによって決定する。このクリッピングプロセスでは、第２多面体の別の特徴項が第１多面体のエッジ特徴項に比較的より近いか否かを識別する。このステップ得た情報は、潜在的により接近している特徴項として照合する別の特徴項を選択するために使われる。
【００７２】
さらに、多面体の透過はクリッピングプロシジャを用いて決定される。対応する多面体のフェースのボロノイ領域に対するエッジ特徴項のクリッピングロケーションが照合され、該ロケーションが該フェースの反対側に存在していれば、そこで透過が行われるのである。
【図面の簡単な説明】
【図１】  本発明を実現するために使用可能なコンピュータシステムを示す図である。
【図２】  多面体及び多面体間の距離相互関係を示す図である。
【図３】  特徴項のボロノイ領域を示す図である。
【図４】  相異なる特徴項のボロノイ領域を示す図である。
【図５】  さらに相異なる特徴項のボロノイ領域を示す図である。
【図６】  本発明によって最短特徴項を発見する際の照合ステート間動作を示す図である。
【図７】  本発明のオペレーションフローチャートを示す図である。
【図８】  異なる照合ステートにおける本発明のオペレーションを示すフローチャートを示す図である。
【図９】  異なる照合ステートにおける本発明のオペレーションを示すフローチャートを示す図である。
【図１０】  異なる照合ステートにおける本発明のオペレーションを示すフローチャートを示す図である。
【図１１】  異なる照合ステートにおける本発明のオペレーションを示すフローチャートを示す図である。
【図１２】  異なる照合ステートにおける本発明のオペレーションを示すフローチャートを示す図である。
【図１３】  フェースに対するボロノイ領域に対するクリッピングを示す図である。
【図１４】  本発明におけるクリッピングのオペレーションフローチャートを示す図である。
【図１５】  本発明における局所極小を避けるオペレーションフローチャートを示す図である。
【図１６】  他アルゴリズムと本発明の相対的処理性能を示す図である。
【図１７】  他アルゴリズムと本発明の相対的処理性能を示す図である。
【図１８】  他アルゴリズムと本発明の相対的処理性能を示す図である。
【図１９】  他アルゴリズムと本発明の相対的処理性能を示す図である。
【符号の説明】
１  コンピュータシステム、１０  ＣＰＵ、２０  メモリー、３０  デイスプレー、４０  入力装置、５０  出力装置、３００  特徴項選択手段、３０５  ボロノイ領域決定手段、３１５  新特徴項選択手段、４２２，４５２  第１照合手段，第１照合手段。
【図１】
0004115005.tif 000004
【図２】
0004115005.tif 000005
【図３】
0004115005.tif 000006
【図４】
0004115005.tif 000007
【図５】
0004115005.tif 000008
【図６】
0004115005.tif 000009
【図７】
0004115005.tif 000010
【図８】
0004115005.tif 000011
【図９】
0004115005.tif 000012
【図１０】
0004115005.tif 000013
【図１１】
0004115005.tif 000014
【図１２】
0004115005.tif 000015
【図１３】
0004115005.tif 000016
【図１４】
0004115005.tif 000017
【図１５】
0004115005.tif 000018
【図１６】
0004115005.tif 000019
【図１７】
0004115005.tif 000020
【図１８】
0004115005.tif 000021
【図１９】
0004115005.tif 000022