【事件の表示】
　特許第２８２６１３８号「移動体の干渉チェック装置」の特許に対する特許異議の申立てについて、次のとおり決定する。
【結論】
　訂正を認める。
　特許第２８２６１３８号の特許を維持する。
【理由】
（Ａ）手続の経緯
　本件は平成１年１０月２１日（優先権主張日昭和６３年１１月１２日（特願昭６３−２８６３４７号））の出願であって、平成１０年９月１１日に特許第２８２６１３８号として登録され、その後、藤井外治より請求項１に係る発明に対して特許異議申立がなされたため取消理由通知が出された。これに対して、特許権者より指定期間内である平成１１年１０月５日に訂正請求がなされた。
（Ｂ）訂正の適否についての判断
（Ｂ−１）訂正明細書の請求項１に係る発明
　訂正明細書の請求項１に係る発明は、訂正請求書に添付された訂正明細書の特許請求の範囲請求項１に記載された次のとおりのものである。
「移動する物体を含む複数の物体に対し、物体相互の干渉をチェックする装置において、
　各物体の表面を表す面情報を記憶した面情報記憶手段と、
　ある階層の任意の１つの球体に対して、その球体に内包されるとともに１つ下位階層に属する複数の球体とで構成されるような内包関係により少なくとも２階層以上に階層化された球体を用い、前記面情報に基づいて前記各物体の表面を各々複数種類の半径からなる球体であって前記表面と交差する球体のみにより階層的に被覆してモデル化する階層球体モデル生成手段と、
　前記生成されたモデル化球体の位置を記憶する球体モデル記憶手段と、
　移動体に関する前記複数種類の半径のモデル化球体の位置を物体の移動に応じて更新して前記球体モデル記憶手段に出力する球体位置更新手段と、
　前記球体モデル記憶手段に記憶された任意時刻の２つの物体に関するモデル化球体における一方の物体に属する球体と他方の物体に属する球体との２つの球体において、それらの２つの球体の中心位置とそれらの球体の半径とに基づいて、中心間距離が半径の和以下の場合にその２つの球体が干渉し、中心間距離が半径の和よりも大きい場合にそれらの球体は非干渉として、相互に干渉する球体を検出し、その干渉すると判断された球体同士のみについてその相互に干渉する球体に属する下位階層の球体の中からさらに干渉する球体を検出するという手順を半径の大きい球体から順に半径の小さい球体へと階層的に実行し、干渉球が存在しない時点で干渉演算を中止すると共に、最終的に相互に干渉する最小半径の球体が存在するときに２つの物体は干渉すると判断しその相互に干渉する最小半径の球体の位置から２つの物体の干渉位置を求め、これらの演算結果を出力する球体干渉演算手段と
　を有することを特徴とする物体の干渉チェック装置。」
（Ｂ−２）訂正の目的の適否及び拡張・変更の存否
　上記訂正は、球体が「表面と交差する球体のみ」であるとするものであり、特許請求の範囲の減縮に相当し、実質的に特許請求の範囲を変更又は拡張するものではない。
（Ｂ−３）独立特許要件
　引用刊行物
　取消理由通知で引用された、日本ロボット学会第６回学術講演会予稿集（昭和６３年１０月２０日発行）第１０５頁〜第１０８頁「移動物体間の干渉が効率的にチェックできるソリッドモデルＨＳＭの提案」（以下「引用刊行物」という）には、「移動物体の干渉をチェックするソリッドモデルＨＳＭ」に関して以下のことが記載されている。
　「物体を囲む最小の球領域をＨＳＭのルートノードで表現する。次に、球領域を予め定義した個数（ここで１３個）のサブ球領域に分割し、サブ球領域をルートノードの子ノードで表現する。」
　「サブ球領域と物体の位置関係により子ノードのラベルをつける。すなわち、物体が存在しないサブ球領域（外側球）を白ノード、物体が占有するサブ球領域（内側球）を黒ノード、物体が存在するが占有しないサブ球領域（交差球）をミックスノードとする。」
　「アルゴリズムは黒ノードどうしの干渉をチェックするＢ＿ｂｌａｃｋ手続きと黒ノードとミックスノードの干渉をチェックするＢ＿ｍｉｘ手続きとミックスノードどうしの干渉をチェックするＭ＿ｍｉｘ手続きの３つの基本手続きからなっている（Ｆｉｇ．３）、これらの手続きはＦｉｇ．３のブロック図にしたがってアルゴリズムで再帰的に利用される。」
　上記各記載から、引用刊行物記載のソリッドモデルでは、１つの球体に内包される１下位階層に属する複数の球体は、外側球（白ノード）、内側球（黒ノード）、交差球（ミックスノード）からなり、二つの物体の干渉は内側球（黒ノード）及び交差球（ミックスノード）の関係から判断されている。これは、本件の下位階層に属する複数の球体を物体の表面と交差する球体、即ち引用刊行物の交差球（ミックスノード）のみとし、二つの物体の干渉は交差球（ミックスノード）の関係からのみ判断する構成とは相違する。また、引用刊行物記載のものでは、二つの物体の干渉の判断に内側球（黒ノード）の存在を必須の条件としており、引用刊行物記載のものから内側球（黒ノード）を必要とせず交差球（ミックスノード）の関係からのみ判断する本件の構成を得ることが当業者にとって容易に為し得たものとも認められない。本件の構成を採ることにより、二つの物体の衝突の判別を無駄なく行うことができるという効果を持つものである。
　したがって、訂正請求された明細書の請求項１に記載された発明は、引用刊行物１記載の事項に基づいて当業者が容易に発明することができたものとすることはできない。
（Ｂ−４）むすび
　以上のとおり、本件訂正請求は、特許法第１２０条の４第２項及び同第３項で準用する特許法第１２６条第２項乃至第４項の規定に適合するので、当該訂正請求は認める。
（Ｃ）特許異議申立てについて
（Ｃ−１）申立の理由の概要
　請求項１に係る発明は、甲第１号証（日本ロボット学会第６回学術講演会予稿集（昭和６３年１０月２０日発行）第１０５頁〜第１０８頁「移動物体間の干渉が効率的にチェックできるソリッドモデルＨＳＭの提案」）より容易に発明することができたものであり、特許法第２９条第２項の規定により、特許を受けることができないものであるから、特許を取り消すべきものである。
（Ｃ−２）判断
　訂正された本件請求項１に係る発明は、上記（Ｂ−３）で示したように、甲第１号証（日本ロボット学会第６回学術講演会予稿集（昭和６３年１０月２０日発行）第１０５頁〜第１０８頁「移動物体間の干渉が効率的にチェックできるソリッドモデルＨＳＭの提案」）より容易に発明することができたものとすることはできない。
　また、他にこれを取り消すべき理由を発見しない。
　よって、結論のとおり決定する。
【異議決定日】
平成１１年１１月２２日（１９９９．１１．２２）
【訂正の要旨】
（３）訂正の要旨
　▲１▼訂正事項１
　特許請求の範囲において、「複数種類の半径からなる球体により階層的に被覆して」を「複数種類の半径からなる球体
であって前記表面と交差する球体のみ
　▲２▼訂正事項２
　特許公報第４コラム第４９行〜第５０行の「複数種類の半径からなる球体により階層的に被覆して」を「複数種類の半径からなる球体
であって表面と交差する球体のみ
　▲３▼訂正事項３
　特許公報第５コラム第２６行目の「物体の表面を被覆する球体を発生し、」を「物体の表面を
、表面と交差する球体のみによって
　▲４▼訂正事項４
　特許公報第７コラム第３３行目の「立法体」を「立
方
（５４）【発明の名称】
移動体の干渉チェック装置
（５７）【特許請求の範囲】
　移動する物体を含む複数の物体に対し、物体相互の干渉をチェックする装置において、
　各物体の表面を表す面情報を記憶した面情報記憶手段と、
　ある階層の任意の１つの球体に対して、その球体に内包されるとともに１つ下位階層に属する複数の球体とで構成されるような内包関係により少なくとも２階層以上に階層化された球体を用い、前記面情報に基づいて前記各物体の表面を各々複数種類の半径からなる球体
であって前記表面と交差する球体のみ
　前記生成されたモデル化球体の位置を記憶する球体モデル記憶手段と、
　移動体に関する前記複数種類の半径のモデル化球体の位置を物体の移動に応じて更新して前記球体モデル記憶手段に出力する球体位置更新手段と、
　前記球体モデル記憶手段に記憶された任意時刻の２つの物体に関するモデル化球体における一方の物体に属する球体と他方の物体に属する球体との２つの球体において、それらの２つの球体の中心位置とそれらの球体の半径とに基づいて、中心間距離が半径の和以下の場合にその２つの球体が干渉し、中心間距離が半径の和よりも大きい場合にそれらの球体は非干渉として、相互に干渉する球体を検出し、その干渉すると判断された球体同士のみについてその相互に干渉する球体に属する下位階層の球体の中からさらに干渉する球体を検出するという手順を半径の大きい球体から順に半径の小さい球体へと階層的に実行し、干渉球が存在しない時点で干渉演算を中止すると共に、最終的に相互に干渉する最小半径の球体が存在するときに２つの物体は干渉すると判断しその相互に干渉する最小半径の球体の位置から２つの物体の干渉位置を求め、これらの演算結果を出力する球体干渉演算手段と
　を有することを特徴とする物体の干渉チェック装置。
【発明の詳細な説明】
　【産業上の利用分野】
　本発明は、移動物体の干渉を高速且つ高精度で判断する干渉チェック装置に関し、例えば、教示したロボットの動作の安全性をグラフィックシミュレータ等により確認する装置やロボット動作における物体との干渉をリアルタイムで判定したり、無人車におけるリアルタイムでの干渉判定装置等に応用できる。
　【従来技術】
　従来、例えば、ロボットの干渉判定においては、画面上で動作径路の各位置でロボットの姿勢を表示してロボットの連続動作を教示したり、プログラムされたロボットの動作を画面上に連続的に表示するグラフィックシミュレータが知られている。この装置では、ロボットの連続動作が実際の移動速度で表示されてその動作がシミュレートされるのであるが、移動するロボットアーム間やロボットアームと静止物体との干渉の有無を高精度且つ高速度で検出することが必要となっている。
　この干渉判定を行う手法は、各種のものが知られている。
　例えば、第１の方法として、特開昭６２−４３７０６号公報に見られるように、ロボット及び作業環境の各部材を多面体で被覆して、その多面体の射影図形から干渉の有無を判定する方法、第２の方法として、特開昭６０−９９５９１号公報に見られるように、ロボット及び作業環境の各部材を線分で表現し、それらの線分間の距離を演算して干渉の有無を判定する方法、第３の方法として、ロボット学会誌６巻１号３５頁に見られるように、ロボット又は環境物体の移動位置を時間関数として表現し、その関数から頂点が面と衝突したり、辺と辺とが衝突した時に干渉と判定する方法が知られている。
　又、第４の方法として、ロボット学会誌５巻３号２１頁に見られるように、ロボット及び環境物体を大きさの異なる立方体で階層的に近似して、２つの物体間の各立方体の包含関係を調べることにより干渉判定を行ったり、第５の方法として、第６回日本ロボット学会学術講演会予稿集１０５頁に見られるように、ロボット及び環境物体を半径の異なる球体で階層的に近似して、その半径の異なる球体の包含関係を調べることにより、物体の干渉判定を行う方法が知られている。
　【発明が解決しようとする課題】
　上記第１の方法では、例えば部材が凹立体であり形状を単なる円柱又は直方体で近似することが困難となるような場合に精度の高い干渉チェックができないし、第２の方法では、高速判定が可能であるが、モデル化が単純すぎて干渉判定の精度が良くないし、第３の方法では、面の数が多くなると計算量が増大し、処理速度が非常に遅くなるという問題がある。
　又、第４の方法は、所謂、オクトツリーの階層的構造による手法であるが、立方体近似であるため、連続する移動体を表現するための座標変換が複雑になり時間がかかるという問題がある。
　更に、第５の方法は、この座標変換を単純化するために、ロボット及び環境物体を半径の異なる球体で階層的に近似しているのであるが、下位階層の球体を発生させる方法が上位階層の球体に内接する正多面体を求め、その正多面体を構成する各面と外接し、その中心が多面体の重心と一致する球体として求めているため、下位階層の球体の発生機構が複雑となりモデル化に時間がかかるという問題がある。又、球体と球体との重複部分が多くなったり、上位階層の球体の外部を内部に包含する下位階層の球体が発生したり、同一球体が上位階層の異なる２つの球体に属したり、１階層上位の球体には属するが２階層以上上位の球体には属さない球体が発生されたりするため、モデル化効率が良くなくひいてはモデル化に時間がかかるという欠点がある。更に、モデル化する対象物体の形状を表現するのに不必要な物体の内部及び外部に対して、一様に階層構造の球体が発生されるため球体の数が多くなり、同様にモデル化効率が良くないという問題がある。又、精度は最小球の半径に依存し、干渉判定の演算速度は球体間の干渉判定回数、即ち、球体の階層化構造に依存する。しかし、各階層の球体の半径比が用いられる多面体の面数により固定的に決定されることから、半径比を要求される干渉判定精度に基づいて任意に設定することができない。従って、階層化構造と最小球の半径とを任意に変化させることが困難であり、精度と演算速度との調整が困難となる。又、ある階層に属する多面体は重なりを生じるが、次の下位の階層の球体を求める時に、多面体の重なりに関しては一切配慮されていないので、無駄に球体が発生されてしまい、探索速度が低下するという問題がある。
　本発明は、上記の課題を解決するために成されたものであり、その目的とするところは、物体のモデル化速度を向上させると共に球体の階層化構造を簡略化することにより球体間の干渉判定回数を減少させ、物体の干渉判定を高速且つ精度良く実行することにある。
　【課題を解決するための手段及び作用】
　上記課題を解決するための発明の構成は、第１図に示すように、各物体の表面を表す面情報を記憶した面情報記憶手段Ａと、ある階層の任意の１つの球体に対して、その球体に内包されるとともに１つ下位階層に属する複数の球体とで構成されるような内包関係よりも少なくとも２階層以上に階層化された球体を用い、面情報に基づいて各物体の表面を各々複数種類の半径からなる球体
であって表面と交差する球体のみ
　上記面情報記憶手段Ａは物体の表面を形成している平面、曲面に関する情報を記憶する手段であり、例えば、構成平面や構成曲面の関数を記憶した装置である。
　階層球体モデル生成手段Ｂは、上記面情報に基づいて決定される物体の表面を、
表面と交差する球体のみによって
　球体モデル記憶手段Ｃは生成された各階層の球体の位置、例えば、中心位置や半径を記憶する手段である。
　球体位置更新手段Ｄは物体の移動に応じて各階層の球体の位置を更新して、球体モデル記憶手段Ｃに記憶する手段である。例えば、物体の位置及び姿勢は物体に固定された座標系の平行移動及び回転移動で表されるが、この平行移動と回転移動とを同時に１つの行列で表すことができる。従って、移動後の各球体の絶対座標系から見た中心位置は、各物体に固定された座標系で見た中心位置に上記の変換行列をかけて求めることができる。
　球体干渉演算手段Ｅは物体の移動に際し、物体間の干渉の有無及びその位置を球体モデル記憶手段Ｃに記憶された各球体の位置から演算する手段である。より具体的には、先ず、２つの物体間で最大半径の球体、即ち、最上位階層の球体が干渉するか否が判定される。この干渉判定は、例えば、２つの球体の中心間の距離が各球体の半径の和より小さいか否かにより判定される。そして、干渉しないと判定された場合には、他の物体間の干渉判定が行われる。一方、干渉有りと判定されると、その球体に属する次に半径の小さな球体、即ち、下位階層の球体に対して、同様に干渉有無の判定が実行される。干渉有りと判定されると更に、その干渉する球体に属する更に下位階層の球体に対して干渉判定が順次実行される。一方、ある階層の球体で干渉する球体が存在しない場合には、１つ上位の階層に遡り、その階層で他に干渉する球体を検出する演算を実行し、干渉する球体が有れば、上記した手順により更に下位階層の球体について干渉判定を行い、干渉球が無ければ、更に、上位階層に遡り、同様に干渉する球体を検出するという演算が実行される。そして、最終的に相互に干渉する最小半径の球体が存在するときに２つの物体は干渉すると判断しその相互に干渉する最小半径の球体の位置から２つの物体の干渉位置が求められる。又、干渉球の階層的な検索において、ある階層での球体について相互に干渉する球体が存在しなくなれば、当然に、下位階層の球体の干渉はありえないので、その時点で干渉演算は停止される。
　【実施例】
　以下、本発明を具体的な実施例に基づいて説明する。
　第１実施例
　本第１実施例は、ロボットや作業環境に関する形状や位置のデータを入力して、ロボット及び作業環境をグラフィックディスプレイ上に表示し、ロボットの動作のシミュレーションを行う場合において、ロボット間又はロボットと物体間の干渉チェックを行う装置である。
　第２図に示すように、本装置はコンピュータ装置で構成されており、論理演算等を実行するＣＰＵ１とその処理手順を示すプログラムを記憶したＲＯＭ２と各種のデータを記憶するＲＡＭ３とロボットや作業環境の位置及び形状データを入力したりシミュレート開始指令等の各種の指令を与えるデータ入力装置４と経時変化するロボットの姿勢や作業環境を微小サンプリングタイム毎に表示するグラフィックディスプレイ５とデータ入力装置４及グラフィックディスプレイ５をＣＰＵ１と接続するための入出力インタフェース６，７とから構成されている。又、ＲＡＭ３にはロボットアームや作業環境の各構成部材毎にそれらの形状を表現する面や頂点、稜線の情報を記憶する形状データメモリ３１と、各構成部材の表面を階層化したときの各球体の中心位置と半径及び階層に関する情報を記憶する球体モデルメモリ３２と、ロボットの現在のジョイント座標を記憶する関節角メモリ３３と、ロボットや作業環境の各構成部材毎にそられの現在の位置を記憶する部材位置メモリ３４とが形成されている。
　次に、本装置の作用をＣＰＵ１の処理手順を示した第３図のフローチャートに従って説明する。ステップ１００では、まずロボットや作業環境の各構成部材毎にそれぞれの形状を生成するためのデータがデータ入力装置４から入力される。この入力により、各構成部材の形状を表す頂点、稜線、面等のデータが演算される。これらの形状データは形状データメモリ３１に記憶される。
　次に、ステップ１０２では、ロボットや作業環境の各構成部材に関して、それらの拘束関係や絶対座標での位置のデータがデータ入力装置４から入力される。この入力データが入力されるに連れてグラフィックディスプレイ５にロボットや作業環境を表示するようにしており、入力データの誤りの検出やデータ入力が容易に実行されるように構成されている。そして、ロボット及び作業環境の拘束関係や位置のデータは部材位置メモリ３４に記憶される。
　ステップ１０２での位置データの入力が完了すると、ステップ１０４でデータ入力装置４により干渉の対象となるロボット及び作業環境を指定するデータが入力される。
　次に、ステップ１０６において、ステップ１０４で指定されたロボットあるいは作業環境について各構成部材毎にその構成部材の各表面を大，中，小の３種類の球体により階層的に被覆して、表面の階層的な球体モデル化が行われる。この表面の球体モデル化は次のように実行される。
　第４図に示すように、１つの構成部材１１を内包する直方体形状の外包体１２をその構成部材１１の形状データメモリ３１から参照した面情報データより発生する。更に、その外包体１２に外接する球体を考え、その球体を大球１４とする。このように、最上位階層の大球１４は、構成部材１１を内包する球体として発生される。そして、構成部材１１にとられた基準座標から見た大球１４の中心位置とその半径が球体モデルメモリ３２に記憶される。
　次に、第５図（ａ）に示すように、外包体１２を中球１５の半径ｒｍに対して、１辺がｌ
　外包体１２の各辺の長さは必ずしもセル１７の辺の長さの倍数とはならないので、各セル１７はオーバーラップさせて配置される。次に、第５図（ｂ）に示すように、各セル１７に外接する球体２０を発生させ、その球体２０のうち、構成部材１１の表面１３と交差する球体のみを抽出し、その抽出された球体を中球１５とする。そして、構成部材１１にとられた基準座標から見た各中球１５の中心位置が球体モデルメモリ３２に記憶される。
　次に、第６図（ａ）に示すように、中球１５に内接するセル１７に注目し、その１つの
のセル１８に分割する。このとき各セル１８は中球の発生時と同様にオーバーラップするように配置されている。次に、この各セル１８に外接する各球体２１を発生させ、構成部材１１の表面１３と交差する球体のみを抽出し、その抽出された球体を小球１６とする。そして、構成部材１１にとられた基準座標から見た各小球１６の中心位置が球体モデルメモリ３２に記憶される。
　このようにして、第７図に示すように、構成部材１１は、全体を外包する大球１４と構成部材１１の表面１３を含むそれより小さい中球１５，更に小さい小球１６の半径の異なる３種類の球体により階層的にモデル化される。即ち、第８図によると、全ての小球は何れかの１つの中球にのみ属し、中球の全ては大球に属するというようにツリー状に階層化されることが分る。
　尚、小球１６の半径ｒｓは、干渉判定の精度を考慮して任意に設定される。次に中球１５の半径ｒｍは、大球の半径ｒｌと小球の半径ｒｓとから次式
により自動的に求める。本式によれば、小球と中球、中球と大球との体積比を等しくできる。このことにより干渉判定時の探索に効率の良い階層構造が得られる。
　又、例外として、構成部材１１の外寸が小さいため、大球１４の径が与えられた小球１６の径より小さくなる場合は小球１６の生成は行わず、大球１４のみのモデルとする。
　以上のように各構成部材の階層的球体モデル化が完了すると、処理はステップ１０８へ移行して、ロボットの動作指令をデータ入力装置４から入力する。次に、ステップ１１０へ移行して、補間点に対する微小移動動作に対応して、微小移動後のロボットのジョイント座標、即ち、関節角の演算を行い、その関節角データは関節角メモリ３３に記憶される。次に、関節角の演算が完了すると、ステップ１１２へ移行して、各構成部材にとられた基準座標系と絶対座標系とを関係づける変換行列Ｔが、その時の関節角から演算される。上記の変換行列Ｔは、ロボット或いは作業環境を構成する各構成部材にとられた基準座標の絶対座標から見た位置及び姿勢を３×４の行列で表したものである。そして、各構成部材にとられた基準座標から見た各球体の中心位置を表すベクトルをＰｒｅｌとすると、絶対座標から見た各球体の中心位置を表すベクトルＰａｂｓは次式
により求められる。ロボットなど各構成部材が動く物体については、動作するたびに各関節角から変換行列Ｔを計算し、構成部材をモデル化する全ての球体の中心位置の絶対座標を更新する必要がある。但し、この絶対座標の更新については、計算の効率化を図るため、干渉チェックの対象となる球体についてのみ行っても良い。
　このように、球体モデルメモリ３２には、各構成部材にとられた基準座標から見た各球体の中心位置Ｐｒｅｌと、現在時刻における各球体の絶対座標から見た中心位置Ｐａｂｓとが記憶されていることになる。
　次に、ステップ１１４へ移行して、以下の手順により干渉チェックの演算が実行される。
　ステップ１１４にて、大球，中球，小球の順で球体同士の干渉チェックを階層的に行い、ステップ１１６にて、最下位階層の球体（小球）同士で干渉有と判定された場合に、ステップ１１８へ移行して、干渉の発生及び干渉部位をその相互に干渉する小球の中心位置から求めて表示すると共に、ステップ１２０にて、干渉状態にあるロボットと作業環境との表示が行われ、本プログラムを終了する。
　次に、ステップ１１４における、大球，中球，小球による階層的なチェックの手順を以下に示す。ｓｔｅｐ１．　第９図（ａ）に示すように、大球１４ａ，１４ｂ　同士のチェックを行い、干渉するものが有れば
ｓｔｅｐ２．を実行する。なければチェック終了とする。従って、まず、各構成部材がある程度接近するまでは、大球同士の干渉判定となり、演算時間は極めて短い。
　ｓｔｅｐ２．　第９図（ｂ）に示すように、１つの大球１４ａと、相手の大球１４ｂに含まれる中球１５ｂ１〜１５ｂｎとの干渉チェックを実行し、干渉する中球１５ｂ１，
１５ｂ２，１５ｂ３を抽出する。又、逆に、大球１４ｂと相手の大球１４ａに含まれる中球１５ａ１〜１５ａｎとの干渉チェックを実行し、干渉する中球１５ａ１，１５ａ２を抽出する。干渉する中球が１つもなければ、２つの構成部材は干渉しないと判断し、演算を中断する。
　ｓｔｅｐ３．　第９図（ｃ）に示すように、抽出された中球１５ｂ１，１５ｂ２，１５ｂ３，１５ａ１，１５ａ２同士の干渉チェックを行い、相互に干渉する中球１５ｂ１，１５ｂ２，１５ａ１を抽出し、ｓｔｅｐ４を実行する。又、相互に干渉する中球が存在しない場合には、２つの構成部材は干渉しないと判断して、チェック演算を中断する。
　ｓｔｅｐ４．　第９図（ｄ）に示すように、干渉する１つの中球１５ｂ２と、相手の中球１５ａ１に含まれる小球１６ａ１１〜１６ａ１ｎ１との干渉チェックを行い、干渉する小球１６ａ１１，１６ａ１２を抽出する。そして、逆に、干渉する１つの中球１５ａ１と、相手の中球１５ｂ２に含まれる小球１６ｂ２１〜１６ｂ２ｎ２のなかから干渉する小球が抽出され、次のｓｔｅｐ５を実行する。また、干渉する小球が存在しない場合には、中球１５ｂ１と、相手の中球１５ａ１に属する小球１６ａ１１〜１６ａ１ｎ１との干渉判定が同様に実行される。干渉する小球が検出されない場合には、相互に干渉する他の中球について同様に実行し、相互に干渉する中球が存在しなくなると、２つの構成部材は干渉しないと判定される。
　ｓｔｅｐ５　．第９図（ｅ）に示すように、抽出された小球１６ａ１１，１６ａ１２，１６ｂ２１，１６ｂ２２，１６ｂ２３同士のチェックを行い、相互に干渉する小球１６ａ１１，１６ｂ２１を抽出する。そして、この場合には、２つの構成部材は小球１６ａ１１，１６ｂ２１の部位で干渉すると判断する。又、相互に干渉する小球が存在しない場合には、相互に干渉する他の中球の抽出ｓｔｅｐへ戻ることになる。
　結局、最終的に、最下位階層の小球同士の干渉が検出された時に、干渉有りと判定し、その小球の位置を干渉部位と判断する。小球同士の干渉が存在しない場合には、上位階層の他の相互に干渉する中球に対する処理が実行され、その相互に干渉する中球が存在しない場合には、最終的に、干渉無しと判定される。従って、第８図に示すツリー構造を干渉の可能性のある枝路に沿って、探索していくことになり、一様に全ての小球同士の干渉を同時に判定するより、数段、干渉判定の時間が短くなる。
　尚、球体の干渉判定は、二つの球の半径をそれぞれｒ１，ｒ２，中心位置をＰ１，Ｐ２とするとき、次式
　　ｒ１＋ｒ２≧‖Ｐ１−Ｐ２‖
を満足するか否かによって判定される。上式を満足すれば、その２つの球体は干渉するとする。
　以上のような、大球，中球，小球の階層的なチェックにより、干渉発生部を効率良く絞り込み、簡易且つ高速の干渉チェックを行うことができる。
　尚、ステップ１１６にて、最下位階層の球体で干渉が発生しないと判定されると、その構成部材間での干渉が発生してないのであるから、ステップ１２２へ移行して、全ての構成部材間の組合せに対して干渉チェックの演算が実行されたか否かが判定され、全ての部材の組合せについて演算が完了していない場合には、ステップ１１４へ戻り、その構成部材間での干渉チェックが同様に実行される。又、全ての構成部材の組合せについて干渉チェック演算が完了した場合には、ステップ１２４へ移行して全ての指定された物体について干渉チェック演算が完了したか否が判定され、完了していない場合には、他の物体間での干渉チェック判定が同様に実行される。
　ステップ１２４にて、全ての指定された物体の組合せについて干渉チェック演算が完了したと判定された場合には、ステップ１２６へ移行して、関節角メモリ３３に記憶されているその時の関節角からロボットの姿勢が演算され、その姿勢でロボットを表示すると共に作業環境の表示が行われる。次に、ステップ１２８へ移行して、全ての移動動作が完了したか否が判定される。移動未完了の場合には、ステップ１１０へ戻り次の移動点に対し上記の干渉判定処理が繰り返し実行される。又、移動完了と判定されると、本プログラムは終了する。
　以上説明したように、本発明に係る装置は、要請される精度と演算速度との両条件を容易に満足させることができるので、例えばロボットのラフ・モーション時における高速干渉チェックを行う場合に特に有効である。
　又、本発明の装置はいかなる形状の部材も同じ精度でモデル化できる他、実ロボットにもオフラインシミュレータにも適用可能な汎用性の高い装置である。
　
第２実施例
　本第２実施例は、物体の大きさや最小球の半径等を考慮し、干渉が発生する部位の探索効率が最適となるように球体モデルの階層数および各階層の球の半径を自動的に設定するものである。以下に前記第１実施例との相違点のみについて説明する。
　階層球体モデル生成手段Ｂにおいて，物体を内包する最大球の半径ｒ１、干渉チェックの精度を決定する最小球の半径ｒｎおよび下位の球との半径比ρｒを与えることにより、階層の深さ（階層数）ｎと各階層での球の半径ｒｉを、夫々次の（１）、（２）式で算出する。
　但し、ｎは四捨五入し整数とする。
　但し、ｉ＝１，２………ｎ
　ここで、（１）式の導出過程を示す。
各階層の球の半径をｒｉとすると、下位の球（半径ｒｉ＋１）との体積比ρｖは（３）式で表される。
ρｖが各階層で一定とすると、最大球の半径ｒ１と最小球の半径ｒｎとの関係は（４）式で表される。
　ここで、上位・下位の球の半径比をρｒとすると、（３）式よりρｖ＝ρｒ３であるので、（４）式は（５）式のように表される。
　ｒ１３＝ｒｎ３・ρｒ３（ｎ−１）　…（５）
　（５）式の両辺の対数をとることにより、（１）式が得られる。
　また、前記（３）式は（５）式より
ｒｉ３＝ｒｎ３・ρｒ３（ｎ−１）
の関係があるから両式より導出される。
　上述においては、上位・下位の球の体積比ρｖを一定、すなわち上位の球内に一定数の下位の球を含むという関係を規定することにより、各階層において各球が有する下位の球の数を全体にわたって均一化できるので、最大球から最小球に至る階層数および各階層における球の数を探索効率上最適に設定できる。
　さらに、上位・下位の球の面積比
ρｓ＝（ｒｉ／ｒｉ＋１）２
を一定としても、同様に上位・下位の球の半径比ρｒ一定の関係に帰着されることはいうまでもない。
　なお、半径比ρｒは物体の大きさ、形状に応じて設定されるものであるが、本実施例では約２としている。
　上述の如く決定された階層数ｎおよび各階層での球半径ｒｉを用いて、物体の球体モデルを次のよう生成する。
　ステップ１：物体を内包する直方体Ｒｅｃ１とその直方体Ｒｅｃ１を内包する球体Ｓｐｈを生成する。（階層レベル：ｋ＝１）
　ステップ２：階層レベルをｋ＝ｋ＋１とし、直方体Ｒｅｃｋ−１を半径ｒｋの球に内接する立方体セル
体Ｒｅｃｋ−１の各辺と各立方体の辺とを一致するように配置するので、第１０図（ａ）においてハッチング部で示すように、多くの場合各立方体セルは夫々隣接セルとオーバラップする。このオーバラップ部は、後述するように削除して直方体セルＲｅｃｋ，ｊとして再構成し、全てのセル（ｊ＝１，２……）についてステップ３を実行する。
　ステップ３：直方体セルＲｅｃｋ，ｊを包む球が物体の表面と交わっているかどうかを調べる。交わっている場合はその球を球体モデルのデータに加え、ｋ＜ｎ（すなわち、階層レベルｋが最下層レベルでない）ならば、直方体Ｒｅｃｋ＋１について更にステップ２を実行する。
　ここで、立方体セルのオーバラップ部の削除について説明する。
　上述のように各階層レベルにおいて、下位球（すなわち下位セル）が生成される順に優先的にオーバラップ部を加えていき、順序が後になるセルについてはオーバラップ部を除いた直方体セルとして定義するものである。すなわち、第１０図（ｂ）において立方体セルＲｅｃｋ−１を半径ｒｋの９つの球Ｓｐｈｋ，１〜Ｓｐｈｋ，９により各直方体セルＲｅｃｋ，１〜Ｒｅｃｋ，９に分割する場合、最初の球Ｓｐｈｋ，１に内接するように立方体セルＲｅｃｋ，１を決め、次の球Ｓｐｈｋ，２に対してはＳｐｈｋ，２に内接する立方体において前記Ｒｅｃｋ，１とのオーバラップ部を除く部分を直方体セルＲｅｃｋ，２と定義する。以下、Ｓｐｈｋ，３〜Ｓｐｈｋ，９に対し、順次同様の操作を行って、夫々オーバラップ部のない各直方体セルＲｅｃｋ，１〜Ｒｅｃｋ，９を定義する。次に、下位の球Ｓｐｈｋ＋１，ｉを生成する場合は、前記各直方体セルＲｅｃｋ，１〜Ｒｅｃｋ，９を前述と同様に分割するので、オーバラップしていた部分で生成される球Ｓｐｈｋ＋１，ｉの重複はなくなり、球データ数を必要最小限に減らすことができる。こうして、物体の表面を表現する（モデル化）するに際し、各階層での球の数を必要最小限にすることができるので、干渉チェックの際の探索効率が低下することがない。
　次に、上記のように生成された物体Ｘ，Ｙの夫々の階層数がｎｘ，ｎＹである階層球対モデルに対し、球体干渉演算手段Ｂにおいて階層的に干渉チェックする再帰的アルゴリズムを以下に示す。このアルゴリズムは、前記階層数が等しくない（ｎｘ≠ｎＹ）場合にも適用できるが、基本的には前記第１実施例の場合と同じである。なお、以下の各ステップにおいて「ｔｒｕｅ／ｆａｌｓｅを返す」とは、一つ前のステップにｔｒｕｅ／ｆａｌｓｅを返すことを意味する。
　ステップ１：二つの物体Ｘ，Ｙの各最上位（階層レベルｋ＝１）の球について、夫々の球データに干渉の可能性を表すマークを付け（フラグに１を立てる）ステップ２を実行する。ステップ２で真（ｔｒｕｅ）という結果が得られた場合は、物体ＸとＹは互いに干渉しているものとする。そうでない場合（偽（ｆａｌｓｅ）という結果が得られた場合）は、物体ＸとＹは互いに干渉していないものとする。
　ステップ２：物体Ｘ，Ｙに夫々属するチェック対象となる球の全ての組合せについてステップ３を実行する。ステップ３がｔｒｕｅならばｔｒｕｅを返す。また、ステップ３でｔｒｕｅとなる組合せが一つも存在しない場合はｆａｌｓｅを返す。
　ステップ３：一つの組合せの夫々物体Ｘ，Ｙに属す各球データのどちらにも干渉可能性を示すマークが付いているならば、それら球同士の干渉チェックを行う。そうでなければｆａｌｓｅを返す。上記チェックの結果、球同士が干渉している場合は、その二つの球についてステップ４を実行する。干渉していなければｆａｌｓｅを返す。また、ステップ４の結果がｔｒｕｅならばｔｒｕｅを、ｆａｌｓｅならばｆａｌｓｅを返す。
　ステップ４：二つの球が共に最下位階層（ｎｘ．ｎＹ）であれば、物体ＸとＹは互いに干渉している
ものと判定しｔｒｕｅを返す。そうでない場合、物体Ｘ，Ｙのどちらか一方に属する球のみが最下位階層ならばステップ５を、また、二つの球が共に最下位階層でない場合は、ステップ６を夫々実行する。ステップ５およびステップ６の夫々の結果がｔｒｕｅならばｔｒｕｅを、ｆａｌｓｅならばｆａｌｓｅを返す。
　ステップ５：物体Ｘ，Ｙの一方に属する最下位階層の球と、他方の物体に属する最下位でない階層の球の１階層下の階層の球との全ての組合せについて球同士の干渉チェックを行う。干渉が有る場合は、ステップ４を実行する。干渉有の球が一つもなければｆａｌｓｅを返す。ステップ４の結果がｔｒｕｅならばｔｒｕｅを、ｆａｌｓｅならばｆａｌｓｅを返す。なお、ここでマークを全てクリヤ（フラグを０にする）することによりセットし、次にまた物体間の干渉チェックをする際に、ステップ１から直ちに始められるようにしておく。
　ステップ６：物体Ｘに属する一つの球と、物体Ｙに属する一つの球の１階層下の階層の複数の球との全ての組合せについて、球同士の干渉チェックを行う。干渉が発生している場合は、前記物体Ｙに属する一つの球の１階層下の階層の球データにマークを付ける。マークの付いた球が一つも存在しない場合はｆａｌｓｅを返す。同様の処理を、物体Ｙに属する一つの球と、物体Ｘに属する一つの球の１階層下の階層の複数の球との全ての組合せについても行う。このようにして、物体Ｘ側の球および物体Ｙ側の球夫々について、階層のレベルを徐々に下げて上位階層の球との干渉の可能性のある球を選び出す。そして、マークの付いた球があれば、ステップ２を全ての組合せについて実行する。ステップ２の結果がｔｒｕｅならばｔｒｕｅを、ｆａｌｓｅならばｆａｌｓｅを返す。なお、ここでステップ５と同様に、マークを全てクリヤ（フラグを０にする）する。
　次に、上記アルゴリズムに従って干渉判定を行うためのＣＰＵ１の処理手順を第１２図（ａ），（ｂ）に基づいて説明する。
　（ａ）階層化されたＸ球とＹ球との階層数が同一である場合。
　ステップ２００において、物体Ｘの現探索階層ｉが１に、物体Ｙの現探索階層ｊが１の最上位階層に初期設定され、最上位球の干渉フラグがオンとされる。最上位球の干渉フラグをオンとすることで、下位階層への球対の探索が開始される。次に、ステップ２０２において、現探索階層（ｉ，ｊ）において、干渉フラグが共にオンの全球対の探索が終了したか否かが判定される。判定結果がＮＯの場合には、ステップ２０４以下のステップが実行され、判定結果がＹＥＳの場合には、ステップ２５０以下のステップが実行される。最上位球に関する最初の実行時には、全球対の探索が終了していないのであるから、ステップ２０２の判定結果は、当然に、ＮＯとなる。
　ステップ２０４では、干渉フラグがオンの球であって、階層ｉに属する１つのＸ球と、階層ｊに属する１つのＹ球とが選択され、未探索の１つの球対（ｉＸ，ｊＹ）が発生される。次のステップ２０６では、ステップ２０４で発生された球対（ｉＸ，ｊＹ）の干渉演算が実行され、次のステップ２０８で２つの球ｉＸとｊＹは干渉するか否かが判定される。尚、干渉演算は、第１実施例で示したように、２つの球の中心間の距離がその２つの球の半径の和よりも小さいか否かによって判定される。
　次に、ステップ２１０で、球対（ｉＸ，ｊＹ）は共に最下位階層に存在するか否かが判定され、判定結果がＮＯの場合には、ステップ２１２へ移行する。ステップ２１２では、球対（ｉＸ，ｊＹ）の一方の球は最下位階層に存在するか否かが判定され、判定結果がＮＯの場合には、ステップ２１４へ移行する。
　ステップ２１４では、球ｉＸと、球ｊＹに属する１階層下の下位球の全てに対して干渉判定が行われる。そして、干渉する場合には、その球ｊＹの下位球の干渉フラグがオンとされる。次に、ステップ２１６へ移行して、ステップ２１４の干渉判定の結果、球ｊＹの下位球のうち少なくとも１球が、球ｉＸと干渉しているか否かが判定され、判定結果がＹＥＳの場合には、ステップ２１８が実行される。
　ステップ２１８では、ステップ２１４と同様にして、球ｊＹと、球ｉＸに属する１階層下の下位球の全てに対して干渉判定が行われる。そして、干渉する場合には、その球ｉＸの下位球の干渉フラグがオンとされる。次に、ステップ２２０へ移行して、ステップ２１８の干渉判定の結果、球ｉＸの下位球のうち少なくとも１球が、球ｊＹと干渉しているか否かが判定され、判定結果がＹＥＳの場合には、ステップ２２２が実行される。
　次に、ステップ２２２において、現探索階層（ｉ，ｊ）における次の探索球対の選択が可能なように、現探索球対（ｉＸ，ｊＹ）が領域Ｄ（ｉ，ｊ）に記憶される。又、現探索階層（ｉ，ｊ）へ復帰後の処理の継続に必要な他のパラメータもスタックされる。
　次に、ステップ２２４において、現探索階層（ｉ，ｊ）が、それぞれ、１階層下げられる。
　尚、現探索階層（ｉ，ｊ）は、注目している球対（ｉＸ，ｊＹ）の存在する階層として定義される。即ち、親球ｉＸと、親球ｊＹに属する１階層下の下位球との干渉演算が実行されている場合の現探索階層（ｉ，ｊ）は、親球ｉＸ，ｊＹの属する階層として定義される。又、現探索球対（ｉＸ，ｊＹ）とは、注目されている親球ｉＸと親球ｊＹとの球対として定義される。
　このように、ステップ２２２，２２４にて、復帰のためのスタック処理と現探索階層の更新処理が完了すると、ステップ２０２へ戻り、現探索階層が次の下位階層となった状態で、上述の処理が繰り返される。
　上記のステップ２０２からステップ２２４が分岐することなく繰り返されると、干渉球対を探索する探索枝は、Ｘ球、Ｙ球共に、最短経路で下位階層へ伸びて行く。
　尚、上記のステップ２０２からステップ２２４のルーチンの中に、判断結果により処理ステップを分岐するステップが含まれているが、分岐されることにより、探索枝は、上位階層に戻りその上位階層で水平方向に伸びて又下位階層に伸びるというようにして進行して行く。
　上記の分岐ステップのうち、ステップ２０８で、球対（ｉＸ，ｊＹ）が干渉しないと判定されると、ステップ２０２へ戻り、ステップ２０４において、干渉フラグがオンに設定された球であって、現探索階層（ｉ，ｊ）に属する他の球対（ｉＸ，ｊＹ）が発生される。そして、ステップ２０６以下において、上述したように、同様にその球対（ｉＸ，ｊＹ）の干渉が判定され、干渉する場合には、親球ｉＸと、親球ｊＹに属する下位の子球との干渉判定と、親球ｊＹと、親球ｉＸに属する下位の子球との干渉判定とが実行され、その干渉する子球の干渉フラグがオンとされる。また、ステップ２１６で、親球ｊＹに属する親球ｉＸと干渉する子球が存在しないと判定された場合、又は、ステップ２２０で、親球ｉＸに属する親球ｉＹと干渉する子球が存在しないと判定された場合には、その親球ｉＸと親球ｊＹとは本来干渉しないのであるから、その球対（ｉＸ，ｊＹ）から下位階層へ向けて、探索枝を伸ばす必要がない。したがって、この場合には、ステップ２０２へ戻り、続くステップ２０４で現探索階層（ｉ，ｊ）に属する他の球対（ｉＸ，ｊＹ）が生成され、ステップ２０６以下の処理により、その球対（ｉＸ，ｊＹ）から探索枝が伸ばされる。
　又、ステップ２０２で現探索階層（ｉ，ｊ）に属する探索フラグオンの球対の全てが探索されたと判定された場合には、ステップ２５０へ移行する。
　ステップ２５０では、その現探索階層（ｉ，ｊ）が最上位階層（１，１）であるか否かが判定される。判定結果がＮＯの場合には、ステップ２５２へ移行して、現探索階層（ｉ，ｊ）に属する探索の対象となった全球対は干渉しないのであるから、その全球対を構成する球の干渉フラグがオフとされる。
　そして、ステップ２５４へ移行して、現探索階層（ｉ，ｊ）が１階層上にあげられる。これにより探索枝は上記階層に戻ることになる。
　探索枝がある上位階層から下位階層へ伸びるときに、ステップ２２２でその上位階層の現探索球対等のデータが記憶されたが、ステップ２５６では、下位階層からその上位階層へ戻る時に、その上位階層での現探索球対等のデータが復元される。従って、ステップ２０２へ戻ると、その上位階層において、次の未探索の球対から、干渉球の探索が継続されることになる。
　一方、ステップ２５０において、現探索階層（ｉ，ｊ）が最上位階層と判定された場合には、最上位球が干渉しないことを意味している。従って、この場合は、ステップ２５８へ移行して、物体Ｘと物体Ｙとは干渉しないという結論を出すことになる。
　これに対し、干渉球の探索が進行する過程において、ステップ２１０において、ステップ２０８で干渉すると判定された現探索球対（ｉＸ，ｊＹ）の球ｉＸと球ｊＹとが共に最下位階層であると判定された場合には、物体Ｘと物体Ｙとはその球対（ｉＸ，ｊＹ）の存在する部分で干渉していると判定することができる。よって、この場合には、ステップ２２６へ移行して、２物体は干渉するという結論を出すことができる。
　（ｂ）階層化されたＸ球とＹ球との階層数が異なる場合。
　現探索球対（ｉＸ，ｊＹ）のいずれか一方の球が、最下位階層になるまでは、上記したステップ２００〜２２４及びステップ２５０〜２５８が実行される。
　上記の処理過程において、ステップ２１２で、現探索球対（ｉＸ，ｊＹ）の一方の球が最下位階層であると判定されると、ステップ２８０以下が実行される。
　ステップ２８０では、現探索球対（ｉＸ，ｊＹ）のうち、最下位階層の球をＬ、相手球をＭとするとき、球Ｌと、相手球Ｍに属する１階層下の下位球、即ち、子球のうち１つの球ｋＭ（ｋは子球によって変化する変数）が選択され、未探索球対（Ｌ，ｋＭ）が発生される。そして、次のステップ２８２で、その球対（Ｌ，ｋＭ）の干渉演算が実行され、次のステップ２８４で、その球対（Ｌ，ｋＭ）は干渉するか否かが判定される。判定結果がＹＥＳの場合には、ステップ２８６へ移行して、将来、親球Ｌと親球Ｍの存在する階層として定義される現探索階層（ｉ，ｊ）に復帰する場合に、継続してその階層の干渉球の探索が実行されるように、親球Ｌと親球Ｍとの球対で定義される現探索球対（ｉＸ，ｊＹ）（＝（Ｌ，Ｍ））が領域Ｄ（ｉ，ｊ）に記憶される。又、その他の復帰に必要なパラメータがスタックされる。
　次に、ステップ２８８において、親球の存在する現探索階層（ｉ，ｊ）が１階層下げられる。この時、球ｉＸが最下位階層に存在する場合には、Ｙ球の階層ｊが１階層下げられる。これに対し、球ｉＹが最下位階層に存在する場合には、Ｘ球の階層ｉが１階層下げられる。
　次に、ステップ２９０へ移行して、現在の球Ｌと子球ｋＭが、次の干渉球の探索過程における新しい親球とみなされる。このために、親球の球対で定義される現探索球対（ｉＸ，ｊＹ）が球対（Ｌ，ｋＭ）として再定義される。そして、ステップ２１０へ戻り、次の干渉球の探索が進行される。
　このようにして、一方の球が最下位階層に属する場合には、他方の球だけが、下位階層に向かって探索される。
　又、ステップ２８４で、球対（Ｌ，ｋＭ）は非干渉と判定されると、ステップ２９２へ移行して、子球ｋＭは親球Ｍに属する最後の球か否かが判定される。判定結果がＮＯの場合には、ステップ２８０へ戻り、親球Ｍに属する他の子球ｋＭが選択される。そして、ステップ２８２以下で、上述と同様に、球対（Ｌ，ｋＭ）の干渉判定が実行される。
　ステップ２９２で、子球ｋＭは親球Ｍに属する最後の球であると判定された場合には、結果的に、親球Ｌと親球Ｍとは非干渉であることを意味するので、現探索球対（ｉＸ，ｊＹ）を変更する必要がある。ステップ２９４はそのために存在する。
　ステップ２９４では、現探索階層（ｉ，ｊ）において、Ｘ球の階層ｉとＹ球の階層ｊとが等しいか否かが判定される。判定結果がＹＥＳの場合には、同一階層に属する他の球対を発生すればよいので、ステップ２０２へ戻る。
　ステップ２９４の判定結果がＮＯの場合は、現探索球対（ｉＸ，ｊＹ）が、親球Ｌと、親球Ｍの属する１階層上の親球との球対に戻され、干渉球の探索はその状態から継続される必要がある。このために、次のステップ２９６で、現探索階層（ｉ，ｊ）が１階層上げられる。尚、この場合、球ｉＸが最下位階層に存在する場合には、Ｙ球の階層ｊが１階層上げられる。これに対し、球ｉＹが最下位階層に存在する場合には、Ｘ球の階層ｉが１階層上げられる。又、ステップ２９８で、更新された現探索階層（ｉ，ｊ）において、干渉球の探索を行っていた最後の探索球対が現探索球対（ｉＸ，ｊＹ）として復元される。尚、その球対は、以前に実行されたステップ２８６において、領域Ｄ（ｉ，ｊ）に記憶されている値である。
　そして、ステップ２１０へ戻り、ステップ２１２でＹＥＳと判定され、ステップ２８０に移行する。そして、ステップ２８０で、現探索球対（ｉＸ，ｊＹ）を親球として、次の新しい未探索の球対（Ｌ，ｋＭ）が発生され、その球対に対して干渉判定が行われる。
　以上、説明したようにして、干渉する可能性のある球についてのみ、下位階層に向けて、順次探索されていくので、探索速度が向上する。
　次に、上述の干渉球の探索アルゴリズム及びＣＰＵ１により実行される探索処理手順により、どの様に干渉球が求められるかを、第１１図に示す例に基づき説明する。
　第１１図には、物体Ｘが５階層、物体Ｙが３階層の階層球体モデルで表される場合について第８図と同様に、最上位の球（物体Ｙでは球ｘ，物体Ｙでは球ｙ）から最下位の球（物体Ｘでは球ｘ１１１１，…‥，ｘｍｍｍｍ、物体Ｙでは球ｙ１１，…‥，ｙｎｎ）に至る各階層の関係が示されている。なお、図中の▲１▼〜▲９▼は、物体間の球同士の干渉チェックの手順を示すもので、以下の記載に対応している。さらに、以下の記載において「（ｘ，ｙ）の干渉チェック」とは、球ｘと球ｙとの間の干渉チェックを行うことを意味する。まず、物体Ｘと物体Ｙとの間の干渉チェックを実行するにあたり、ｘ，ｙに夫々干渉可能性を示すマーク付けをする（干渉フラグをオン）。
　▲１▼（ｘ，ｙ）の干渉チェックにより干渉有のため、ｘ，ｙを夫々干渉有とする。
　▲２▼干渉有とされたｘとｙの下位階層のｙ１，ｙ２，…‥，ｙｎとの全ての組合せ（ｘ，ｙ１），（ｘ，ｙ２），…‥（ｘ，ｙｎ）の干渉チェックにより、ｘとｙ１およびｙ２との間で干渉有のため、ｙ１，ｙ２に夫々マーク付けをする。
　▲３▼同様に、ｙとＸの下位階層のｘ１，ｘ２，…‥，ｘｍ
との全ての組合せの干渉チェックにより、干渉有のｘ１，ｘ２に夫々マーク付けをする。
　▲４▼マークを付けられた球の組合せ全部（ｘ１，ｙ１），（ｘ１，ｙ２），（ｘ２，ｙ１），（ｘ２，ｙ２）の干渉チェックより、ｘ１とｙ１との間で干渉有のため、ｘ１，ｙ１を夫々干渉有とする。すなわち、マークを付けられていないｘ３，…‥，Ｘｍとｙ３，…‥，ｙｎとの間の干渉チェックは行わない。
　▲５▼　▲２▼と同様に、干渉有とされたｘ１，ｙ１に対し、ｘ１とｙ１の下位階層のｙ１１，ｙ１２，…‥，ｙ１ｎとの全ての組合せの干渉チェックにより、干渉有のｙ１１，ｙ１２に夫々マーク付けをする。
　▲６▼　▲３▼と同様に、干渉有とされたｘ１，ｙ１に対し、ｙ１とｘ１の下位階層のｘ１１，ｘ１２，…‥，ｘ１ｍとの全ての組合せの干渉チェックにより、干渉有のｘ１１，ｘ１２に夫々マーク付けをする。
　▲７▼マークを付けられた球の組合せ全部（ｘ１１，ｙ１１），（ｘ１１，ｙ１２），（ｘ１２，ｙ１１），（ｘ１２，ｙ１２）の干渉チェックより、ｘ１１とｙ１１との間で干渉有のため、ｘ１１，ｙ１１を夫々干渉有とする。なお、ｙ１１は物体Ｙの最下位階層の球であるため、これ以後は物体Ｙのチェック対象球は常にｙ１１となる。
　▲８▼干渉有とされたｘ１１，ｙ１１に対し、ｙ１１とｘ１１の下位階層のｘ１１１，ｘ１１２，…‥，ｘ１１ｍとの全ての組合せに対し順次、干渉チェックを行う。ｘ１１１とｙ１１とは干渉が無いので次に（ｘ１１２，ｙ１１）の干渉チェックを行う。その結果、ｘ１１２とｙ１１との間で干渉が発生しているためｘ１１２を干渉有とするとともに、チェック対象をｘ１１２からｘ１１２の下位階層の球へ変更する。
　▲９▼ｙ１１とｘ１１２の下位階層のｘ１１２１との干渉チェックにより干渉が無いため、次に（ｘ１１２２，ｙ１１）の干渉チェックを行う。この結果、ｘ１１２２とｙ１１との間で干渉が発生しているためｘ１１２２を干渉有とする。ｘ１１２２は最下位階層の球であるので、ここで処理を終了し、次のｘ１１２３に関しては干渉の有無に関係なく干渉チェックを行わない。
　こうして、物体Ｘと物体Ｙとは球ｘ１１２２と球ｙ１１の存在する部位で干渉していると直ちに判断される。
　但し、物体の全部位について干渉の有無を知りたい場合は、▲８▼においてチェック対象から外したｘ１１３，…‥，ｘ１１ｍ全てについても、ｙ１１との干渉チェックを行えば良い。
　以上説明したように、他の物体の上位階層の球との間でのチェックにより、干渉の可能性ありとしてマークを付けられた球同士に付いてのみ干渉チェックを行うため、チェック対象となる球の組合せの数を極めて少なくすることができるので、物体間の干渉チェックの効率を非常に高めることができる。
　【発明の効果】
　本発明は、上記したように、各物体の表面を被覆する球体でモデル化しており、物体内部及び外部はモデル化から除外しているので、球体の数が少なく階層構造が単純化されると共にモデル化速度が向上する。従って、干渉チェックの演算時間が短くなるという効果を有している。
　又、球体でモデル化しているので、物体の移動に伴う球体の移動は、その球体の中心位置の移動演算だけ行えば良く、移動に伴う球体の更新演算が簡略化される。
　更に、干渉判定の精度は最小球の半径に依存し、その最小球の半径を任意に設定できるので、干渉判定精度を任意に変化させることができる。
　更に、階層的にモデル化しているので、階層を深くすることにより演算時間の短縮化を図ることもできる。
　更に、球体の干渉判定を干渉の可能性の高い上位階層の球体から順次その干渉球体に属する下位階層の球体に対して階層的に実行しているので、干渉判定速度が向上するという効果がある。即ち、粗いチェックから詳細なチェックへ移る過程において干渉の可能性のない部分を除外していくことにより、干渉発生部を効率良く絞り込むことができる。
【図面の簡単な説明】
　第１図は本発明の全体の構成を示したブロックダイヤグラム、第２図は本発明の具体的な実施例に係る装置の構成を示したブロックダイヤグラム、第３図は同実施例の装置に使用されたＣＰＵの処理手順を示したフローチャート、第４図、第５図、第６図は、それぞれ、大球、中球、小球の発生方法を示した説明図、第７図、第８図は球体モデルの階層構造を示した説明図、第９図は干渉判定の論理を示した説明図、第１０図はオーバラップのある立方体セル及びオーバラップ部を削除した直方体セルとそれらを内包する球の関係を示した模式図、第１１図は階層数の異なる球体モデル間の干渉チェックを示した説明図、第１２図は干渉球の探索を行うＣＰＵの処理手順を示したフローチャートである。
１‥…ＣＰＵ　３‥…ＲＡＭ
３１…‥形状データメモリ
３２…‥球体モデルメモリ
３３…‥関節角メモリ
３４…‥部材位置メモリ