(57)【特許請求の範囲】
【請求項１】
モデル化の対象となる物体の表面を、メッシュ分割するとともに、メッシュ分割された各メッシュの全ての辺の長さを予め設定した最下位階層の球の直径以下に設定し、メッシュ分割により発生した各節点を中心として最下位階層の球体を生成し、次いで、全節点に基づいて定まる立方体領域を含む最小の球体を生成して最上位階層の球体とし、その後、直前の階層の球体の中心を通る平面で全節点を２分割し、分割された各区分に属する全節点に基づいて定まる立方体領域を含む最小の球体を生成して、分割前の階層の次の階層の球体とし、その後、全節点の２分割処理および各区分に属する全節点に基づいて定まる立方体領域を含む最小の球体を生成して次の階層の球体とする処理を、分割後の節点数が１になるまで反復することを特徴とする階層球体モデル生成方法。
【請求項２】
全節点を２分割する平面が、全節点の最大分散方向を法線とする平面であり、立方体領域を含む最小の球体を生成する処理に代えて、全節点を含む最小の球体を生成する処理を採用する請求項１に記載の階層球体モデル作成方法。
【請求項３】
モデル化の対象となる物体の表面を、メッシュ分割するとともに、メッシュ分割された各メッシュの全ての辺の長さを予め設定した最下位階層の球の直径以下に設定するメッシュ分割手段（３）と、メッシュ分割により発生した各節点を中心として最下位階層の球体を生成する最下位階層球体生成手段（９）と、全節点に基づいて定まる立方体領域を含む最小の球体を生成して最上位階層の球体とする最上位階層球体生成手段（５）と、直前の階層の球体の中心を通る平面で全節点を２分割する分割手段（６）と、分割された各区分に属する全節点に基づいて定まる立方体領域を含む最小の球体を生成して、分割前の階層の次の階層の球体とする中間階層球体生成手段（８）と、分割手段（６）による処理および中間階層球体生成手段（８）による処理を、分割後の節点数が１になるまで反復させる反復制御手段とを含むことを特徴とする階層球体モデル生成装置。
【請求項４】
分割手段（６）が、全節点の最大分散方向を法線とする平面で全節点を２分割するものであり、最上位階層球体生成手段（５）および中間階層球体生成手段（８）が、立方体領域を含む最小の球体を生成する処理に代えて、全節点を含む最小の球体を生成する処理を行うものである請求項３に記載の階層球体モデル作成装置。
【請求項５】
請求項１または請求項２の方法によりそれぞれ階層球体が生成された第１物体、第２物体どうしが交差しているか否かを判定する干渉チェック方法であって、第１物体、第２物体の最上位階層の球体の中心座標、半径を得て両球体どうしが交差しているか否かを判定し、交差していると判定されたことに応答して、一方の物体の次の階層の球体のそれぞれと他方の物体の元の階層の球体とが交差しているか否かを両球体の中心座標値、半径に基づいて判定し、交差していると判定されたことに応答して、該当する球体を元の階層の球体として選択して、一方の物体の次の階層の球体のそれぞれと他方の物体の元の階層の球体とが交差しているか否かの判定を最下位階層の球体まで反復し、最下位階層の球体どうしが交差していることを条件として第１物体、第２物体どうしが干渉していると判定し、何れかの階層に属する全ての球体どうしが交差していないことを条件として第１物体、第２物体どうしが干渉していないと判定することを特徴とする干渉チェック方法。
【請求項６】
請求項３または請求項４の装置によりそれぞれ階層球体が生成された第１物体、第２物体どうしが交差しているか否かを判定する干渉チェック装置であって、第１物体、第２物体の最上位階層の球体の中心座標、半径を得て両物体どうしが交差しているか否かを判定する第１判定手段（１５）と、第１判定手段（１５）により交差していると判定されたことに応答して、一方の物体の次の階層の球体のそれぞれと他方の物体の元の階層の球体とが交差しているか否かを両球体の中心座標値、半径に基づいて判定する第２判定手段（１５）と、第２判定手段（１５）により交差していると判定されたことに応答して、該当する球体を元の階層の球体として選択して、一方の物体の次の階層の球体のそれぞれと他方の物体の元の階層の球体とが交差しているか否かの判定を最下位階層の球体まで反復させる反復制御手段（２１）と、最下位階層の球体どうしが交差していることを条件として第１物体、第２物体どうしが干渉していることを示す判定結果を出力する第１出力手段（２２）と、何れかの階層に属する全ての球体どうしが交差していないことを条件として第１物体、第２物体どうしが干渉していないことを示す判定結果を出力する第２出力手段（１７）とを含むことを特徴とする干渉チェック装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
この発明は階層球体モデル生成方法、干渉チェック方法およびこれらの装置に関し、さらに詳細にいえば、物体の表面をモデル化するために、階層構造の球体を生成する方法およびその装置と、２つの物体のそれぞれを階層球体でモデル化した場合に、各球体どうしが交差するか否かに基づいて物体どうしが干渉するか否かを判定する方法およびその装置とに関する。
【０００２】
【従来の技術】
従来から、産業用ロボット、人工現実感などの分野において、少なくとも一方が移動する物体どうしの間の干渉チェックを高速に行うためのモデルとして階層球体モデルを採用することが提案されている。もちろん、階層球体モデルによる干渉チェックを行うために、物体の形状データに基づいて階層球体モデルを作成することが必要である。
【０００３】
従来から提案されている階層球体モデルの作成方法として、物体が存在する空間（立方体空間、直方体空間など）を均等に分割して多数の立方体空間を得、しかも、この立方体空間を階層的に得、各階層の立方体空間に外接する球体を生成し、生成された球体の物体に対する内外判定を行って、少なくとも一部に物体の内部を含む球体のみを残す方法がある（特開平２−２２４００４号公報参照）。
【０００４】
この方法を採用すれば、各階層に属する球体は全てサイズが等しく、階層化を簡単に達成することができる。
また、このようにして得られた階層球体モデルに基づいて、２つの物体のそれぞれに対応する階層球体モデルを構成する各球体どうしが交差するか否かを判定することにより、物体どうしの干渉チェックを行うことができる。
【０００５】
【発明が解決しようとする課題】
しかし、上記の方法により作成された階層球体モデルにおいて、物体の形状を最も精度よく表現できる最下位階層の球体の集合体として表現された物体形状は、最下位階層の球体の直径を上限とする誤差を含むという不都合がある。そして、この階層球体モデルを用いて干渉チェックを行えば、物体どうしの干渉が生じないにも拘らず、物体どうしが干渉すると判定される確率が増加してしまうことになる。
【０００６】
この不都合を解消するためには、最下位階層の球体の直径を小さくすればよいが、この場合には、階層球体モデルを構成する球体の数が著しく多くなってしまうという新たな不都合を生じることになる。そして、球体の数が著しく増加すれば、干渉チェックにおいて処理の対象となる球体の組合せの数がいちじるしく多くなってしまい、干渉チェックの所要時間が著しく長くなってしまうことになる。
【０００７】
また、処理対象となる球体の数を減少させるために、物体の表面のみの情報を有する階層球体モデルを作成することも考えられるが、この場合には、物体に完全に内包される球体を検出し、検出された球体を除去する処理が必要になるので、階層球体モデルを作成するための処理が複雑化するとともに、所要時間が長くなってしまうという新たな不都合を生じてしまう。
【０００８】
さらに、上記の方法により作成された階層球体モデルは、物体が存在する空間を基準として各階層の球体を生成することにより作成されるのであるから、生成された球体内における物体占有率を余り高めることができないという不都合もある。
【０００９】
【発明の目的】
この発明は上記の問題点に鑑みてなされたものであり、最下位階層の球体により表現される物体の形状が有する誤差を小さくすることができるとともに、球体の除去処理を不要にして、物体表面のみの情報を有する球体を生成して、全球体数を減少させることができる階層球体モデル作成方法およびその装置を提供することを第１の目的とし、上記階層球体モデル作成方法またはその装置により作成された階層球体モデルを用いて物体どうしの干渉チェックを行うための方法およびその装置を提供することを第２の目的としている。
【００１０】
【課題を解決するための手段】
請求項１の階層球体モデル作成方法は、モデル化の対象となる物体の表面を、メッシュ分割するとともに、メッシュ分割された各メッシュの全ての辺の長さを予め設定した最下位階層の球の直径以下に設定し、メッシュ分割により発生した各節点を中心として最下位階層の球体を生成し、次いで、全節点に基づいて定まる立方体領域を含む最小の球体を生成して最上位階層の球体とし、その後、直前の階層の球体の中心を通る平面で全節点を２分割し、分割された各区分に属する全節点に基づいて定まる立方体領域を含む最小の球体を生成して、分割前の階層の次の階層の球体とし、その後、全節点の２分割処理および各区分に属する全節点に基づいて定まる立方体領域を含む最小の球体を生成して次の階層の球体とする処理を、分割後の節点数が１になるまで反復する方法である。
【００１１】
請求項２の階層球体モデル作成方法は、全節点を２分割する平面として、全節点の最大分散方向を法線とする平面を採用し、立方体領域を含む最小の球体を生成する処理に代えて、全節点を含む最小の球体を生成する処理を採用する方法である。
請求項３の階層球体モデル生成装置は、モデル化の対象となる物体の表面を、メッシュ分割するとともに、メッシュ分割された各メッシュの全ての辺の長さを予め設定した最下位階層の球の直径以下に設定するメッシュ分割手段と、メッシュ分割により発生した各節点を中心として最下位階層の球体を生成する最下位階層球体生成手段と、次いで、全節点に基づいて定まる立方体領域を含む最小の球体を生成して最上位階層の球体とする最上位階層球体生成手段と、直前の階層の球体の中心を通る平面で全節点を２分割する分割手段と、分割された各区分に属する全節点に基づいて定まる立方体領域を含む最小の球体を生成して、分割前の階層の次の階層の球体とする中間階層球体生成手段と、分割手段による処理および中間階層球体生成手段による処理を、分割後の節点数が１になるまで反復させる反復制御手段とを含んでいる。
【００１２】
請求項４の階層球体モデル作成装置は、分割手段として、全節点の最大分散方向を法線とする平面で全節点を２分割するものを採用し、最上位階層球体生成手段および中間階層球体生成手段として、立方体領域を含む最小の球体を生成する処理に代えて、全節点を含む最小の球体を生成する処理を行うものを採用している。
【００１３】
請求項５の干渉チェック方法は、請求項１の方法によりそれぞれ階層球体が生成された第１物体、第２物体どうしが交差しているか否かを判定する干渉チェック方法であって、第１物体、第２物体の最上位階層の球体の中心座標、半径を得て両球体どうしが交差しているか否かを判定し、交差していると判定されたことに応答して、一方の物体の次の階層の球体のそれぞれと他方の物体の元の階層の球体とが交差しているか否かを両球体の中心座標値、半径に基づいて判定し、交差していると判定されたことに応答して、該当する球体を元の階層の球体として選択して、一方の物体の次の階層の球体のそれぞれと他方の物体の元の階層の球体とが交差しているか否かの判定を最下位階層の球体まで反復し、最下位階層の球体どうしが交差していることを条件として第１物体、第２物体どうしが干渉していると判定し、何れかの階層に属する全ての球体どうしが交差していないことを条件として第１物体、第２物体どうしが干渉していないと判定する方法である。
【００１４】
請求項６の干渉チェック装置は、請求項３の装置によりそれぞれ階層球体が生成された第１物体、第２物体どうしが交差しているか否かを判定する干渉チェック装置であって、第１物体、第２物体の最上位階層の球体の中心座標、半径を得て両球体どうしが交差しているか否かを判定する第１判定手段と、第１判定手段により交差していると判定されたことに応答して、一方の物体の次の階層の球体のそれぞれと他方の物体の元の階層の球体とが交差しているか否かを両球体の中心座標値、半径に基づいて判定する第２判定手段と、第２判定手段により交差していると判定されたことに応答して、該当する球体を元の階層の球体として選択して、一方の物体の次の階層の球体のそれぞれと他方の物体の元の階層の球体とが交差しているか否かの判定を最下位階層の球体まで反復させる反復制御手段と、最下位階層の球体どうしが交差していることを条件として第１物体、第２物体どうしが干渉していることを示す判定結果を出力する第１出力手段と、何れかの階層に属する全ての球体どうしが交差していないことを条件として第１物体、第２物体どうしが干渉していないことを示す判定結果を出力する第２出力手段とを含むんでいる。
【００１５】
【作用】
請求項１の階層球体モデル作成方法であれば、モデル化の対象となる物体の表面を、メッシュ分割するとともに、メッシュ分割された各メッシュの全ての辺の長さを予め設定した最下位階層の球の直径以下に設定し、メッシュ分割により発生した各節点を中心として最下位階層の球体を生成し、次いで、全節点に基づいて定まる立方体領域を含む最小の球体を生成して最上位階層の球体とし、その後、直前の階層の球体の中心を通る平面で全節点を２分割し、分割された各区分に属する全節点に基づいて定まる立方体領域を含む最小の球体を生成して、分割前の階層の次の階層の球体とし、その後、全節点の２分割処理および各区分に属する全節点に基づいて定まる立方体領域を含む最小の球体を生成して次の階層の球体とする処理を、分割後の節点数が１になるまで反復するのであるから、最下位階層の球体により表現される物体形状の誤差を球体の半径以下にすることができる。また、当初から物体の表面のみをメッシュ分割して球体を生成するのであるから、物体に内包される球体はもともと生成されず、処理の複雑化を伴なうことなく、生成される球体の数を減少させることができる。
【００１６】
請求項２の階層球体モデル作成方法であれば、全節点を２分割する平面として、全節点の最大分散方向を法線とする平面を採用し、立方体領域を含む最小の球体を生成する処理に代えて、全節点を含む最小の球体を生成する処理を採用するのであるから、最上位階層の球体内の物体占有率を大きくすることができ、中間階層の球体内の物体占有率を大きくすることができる確率を高めることができる。
【００１７】
請求項３の階層球体モデル生成装置であれば、メッシュ分割手段により、モデル化の対象となる物体の表面を、メッシュ分割するとともに、メッシュ分割された各メッシュの全ての辺の長さを予め設定した最下位階層の球の直径以下に設定し、最下位階層球体生成手段により、メッシュ分割により発生した各節点を中心として最下位階層の球体を生成し、最上位階層球体生成手段により、全節点に基づいて定まる立方体領域を含む最小の球体を生成して最上位階層の球体とする。そして、分割手段により、直前の階層の球体の中心を通る平面で全節点を２分割し、中間階層球体生成手段により、分割された各区分に属する全節点に基づいて定まる立方体領域を含む最小の球体を生成して、分割前の階層の次の階層の球体とする。その後、反復制御手段により、分割手段による処理および中間階層球体生成手段による処理を、分割後の節点数が１になるまで反復させることにより、最終的に階層球体モデルを作成することができる。したがって、最下位階層の球体により表現される物体形状の誤差を球体の半径以下にすることができる。また、当初から物体の表面のみをメッシュ分割して球体を生成するのであるから、物体に内包される球体はもともと生成されず、処理の複雑化を伴なうことなく、生成される球体の数を減少させることができる。
【００１８】
請求項４の階層球体モデル作成装置であれば、分割手段として、全節点の最大分散方向を法線とする平面で全節点を２分割するものを採用し、最上位階層球体生成手段および中間階層球体生成手段として、立方体領域を含む最小の球体を生成する処理に代えて、全節点を含む最小の球体を生成する処理を行うものを採用しているので、最上位階層の球体内の物体占有率を大きくすることができ、中間階層の球体内の物体占有率を大きくすることができる確率を高めることができる。
【００１９】
請求項５の干渉チェック方法であれば、請求項１の方法によりそれぞれ階層球体が生成された第１物体、第２物体どうしが交差しているか否かを判定するに当って、第１物体、第２物体の最上位階層の球体の中心座標、半径を得て両球体どうしが交差しているか否かを判定し、交差していると判定されたことに応答して、一方の物体の次の階層の球体のそれぞれと他方の物体の元の階層の球体とが交差しているか否かを両球体の中心座標値、半径に基づいて判定し、交差していると判定されたことに応答して、該当する球体を元の階層の球体として選択して、一方の物体の次の階層の球体のそれぞれと他方の物体の元の階層の球体とが交差しているか否かの判定を最下位階層の球体まで反復し、最下位階層の球体どうしが交差していることを条件として第１物体、第２物体どうしが干渉していると判定し、何れかの階層に属する全ての球体どうしが交差していないことを条件として第１物体、第２物体どうしが干渉していないと判定するのであるから、高速に、かつ高精度に干渉チェックを行うことができる。
【００２０】
請求項６の干渉チェック装置であれば、請求項３の装置によりそれぞれ階層球体が生成された第１物体、第２物体どうしが交差しているか否かを判定するに当って、第１判定手段により、第１物体、第２物体の最上位階層の球体の中心座標、半径を得て両球体どうしが交差しているか否かを判定し、第１判定手段により交差していると判定されたことに応答して、第２判定手段により、一方の物体の次の階層の球体のそれぞれと他方の物体の元の階層の球体とが交差しているか否かを両球体の中心座標値、半径に基づいて判定し、第２判定手段により交差していると判定されたことに応答して、第３判定手段により、該当する球体を元の階層の球体として選択して、一方の物体の次の階層の球体のそれぞれと他方の物体の元の階層の球体とが交差しているか否かの判定を最下位階層の球体まで反復させる。そして、これらの一連の処理の結果、最下位階層の球体どうしが交差していることを条件として第１出力手段により第１物体、第２物体どうしが干渉していることを示す判定結果を出力、逆に、何れかの階層に属する全ての球体どうしが交差していないことを条件として第２出力手段により第１物体、第２物体どうしが干渉していないことを示す判定結果を出力する。
【００２１】
したがって、高速に、かつ高精度に干渉チェックを行うことができる。
【００２２】
【実施例】
以下、実施例を示す添付図面によってこの発明を詳細に説明する。
図１、図２はこの発明の階層球体モデル作成方法の一実施例を説明するフローチャートである。
図１のフローチャートにおいては、ステップＳＰ１において最下位階層の球体の直径を設定し、ステップＳＰ２においてＤｅｌａｕｎａｙ三角分割法など、従来公知の方法により処理対象となる物体の表面をメッシュ分割し、メッシュ分割により発生した節点群を記憶し、ステップＳＰ３において図２のフローチャートの処理（球体モデル作成処理）を行い、そのまま一連の処理を終了する。なお、ステップＳＰ２におけるメッシュ分割は、各メッシュの各辺の長さが最下位階層の球体の半径以下になるように設定される。
【００２３】
図２のフローチャートにおいては、ステップＳＰ１において複数個の節点が存在しているか否かを判定する。そして、節点の数が複数であると判定された場合には、ステップＳＰ２において、該当する全ての節点を基に立方体領域（全節点を含む直方体または立方体）を発生し、立方体領域を内包する最小半径の球体（以下、最小球と略称する）を生成し｛図３中（Ａ）参照、ただし、図３中（Ａ）において、ａが物体を、ｂが立方体領域を、ｃが最小球をそれぞれ示している。｝、ステップＳＰ３において、分割により節点群が発生したか否か（即ち、該当する節点群が後述する分割処理により発生させられたものであるか否か）を判定する。そして、節点群が分割により発生したのではないと判定された場合には、ステップＳＰ４において、ステップＳＰ２で生成された最小球を最上位階層の球体として保存する。逆に、節点群が分割により発生したと判定された場合には、ステップＳＰ５において、ステップＳＰ２で生成された最小球を、先に行われた図２のフローチャートの処理のステップＳＰ４またはステップＳＰ５において保存された最小球の下位の階層の球体として保存する。
【００２４】
ステップＳＰ４またはステップＳＰ５の処理が行われた後は、ステップＳＰ６において、直前に保存された最小球の中心を通り、かつ立方体領域の長手方向を法線とする平面で全節点を２分割し｛図３中（Ｂ）参照、ただし、図３中（Ｂ）において、ａが物体を、ｂが立方体領域を、ｃが上記平面をそれぞれ示している。｝、ステップＳＰ７において、分割された一方の節点群に対して図２のフローチャートの処理を行い、ステップＳＰ８において、分割された残余の節点群に対して図２のフローチャートの処理を行い、そのまま元の処理に戻る。
【００２５】
上記ステップＳＰ１において節点の数が１つであると判定された場合には、ステップＳＰ９において、分割により節点群が発生したか否か（即ち、該当する節点群が前述する分割処理により発生させられたものであるか否か）を判定する。そして、節点群が分割により発生したのではないと判定された場合には、ステップＳＰ１０において、最下位階層の球体を、その中心を節点と一致させた状態で保存する。逆に、節点群が分割により発生したと判定された場合には、ステップＳＰ１１において、最下位階層の球体を、その中心を節点と一致させた状態で、かつ先に行われた図２のフローチャートの処理のステップＳＰ４またはステップＳＰ５において保存された最小球の下位の階層の球体として保存する。ステップＳＰ１０またはステップＳＰ１１の処理が行なわれた後は、そのまま元の処理に戻る。
【００２６】
したがって、最下位階層の球体は、図４中（Ａ）に示すように物体の表面のメッシュ分割が行われた場合において、例えば、物体の表面の１辺に対して図４中（Ｂ）に示すように配置される。したがって、最下位階層の球体により表現される物体形状の誤差は最下位階層の球体の半径以下になる。なお、図４中（Ｂ）において最下位階層の球体の直径を２ｎで示している。
【００２７】
また、最下位階層以外の階層の球体は、その上位の階層の球体の中心を通り、かつ立方体領域の長手方向を法線とする平面で節点群を２分割し、各区分に属する全ての節点に基づいて定まる立方体領域を含む最小半径の球体として生成されるのであるから、球体の生成処理を簡単化できる。    さらに、物体表面のみを対象として球体を生成するのであるから、物体に内包される球体はもともと生成されない。したがって、無駄な球体を削除する処理が不要であり、しかも無駄な球体が生成されないので、球体の数を少なくすることができる。
【００２８】
図５は図１および図２のフローチャートの処理を行うことにより作成された階層構造球体モデルの一例を示す図である。なお、階層の数は、最下位階層の球体の直径および対象となる物体のサイズ、形状により自動的に定まる。
ただし、図２のフローチャートにおいて、全ての節点に基づいて定まる立方体領域を含む最小半径の球体を生成する処理に代えて、全ての節点を含む最小半径の球体を生成する処理を採用することが好ましく、球体内における物体占有率を高めることができる。
【００２９】
また、図２のフローチャートにおいて、立方体領域の長手方向を法線とする平面に代えて、全節点の最大分散方向を法線とする平面を採用することが好ましく、分割された各節点群を含む球体内における物体占有率が大なる確率を大きくすることができる。
【００３０】
【実施例２】
図６はこの発明の階層構造球体モデル作成装置の一実施例を示すブロック図である。
この階層構造球体モデル作成装置は、対象物体の形状データを保持する形状データ保持部１と、最下位階層の球体の直径の設定値を保持する直径保持部２と、対象物体の形状データおよび最下位階層の球体の直径を入力として、従来公知の方法により対象物体の表面をメッシュ分割し、各メッシュの各辺の長さを上記直径以下に設定するメッシュ分割部３と、メッシュ分割により得られた節点群を保持する（例えば、各節点の座標値などを保持する）メッシュデータ保持部４と、全ての節点に基づいて定まる立方体領域を含む最小の球体を生成し、最上位階層の球体として割当てる最上位階層球体生成部５と、最も新たに生成され、かつ未処理の球体に含まれる節点の数が複数であることを条件として、この節点群を、この球体の中心を通り、かつ立方体領域の長手方向を法線とする平面で２分割する分割部６と、分割部６により分割された各区分に属する節点の数が複数か否かを判定する節点数判定部７と、節点数が複数であることを条件として、分割部６により分割された各区分に属する全ての節点に基づいて定まる立方体領域を含む最小の球体を生成し、次の階層の球体として割当てる中間階層球体生成部８と、節点数が１であることを条件として、該当する節点と中心とを一致させた状態で最下位階層球体を配置する最下位階層球体配置部９とを有している。
【００３１】
なお、構成各部の作用は図１、図２のフローチャートの該当するステップの処理と同様であるから、詳細な説明を省略する。もちろん、これら構成各部は、ハードウェアで構成されてもよいが、図１、図２に示す処理を行うプログラムが組み込まれたコンピュータで構成することが好ましい。また、節点数が１になるまで分割部６による分割処理、中間階層球体生成部７の処理を反復させる制御部は図示を省略してある。また、２分割された各節点群を保持する保持部も図示を省略してある。
【００３２】
したがって、最下位階層の球体は、図４中（Ａ）に示すように物体の表面のメッシュ分割が行われた場合において、例えば、物体の表面の１辺に対して図４中（Ｂ）に示すように配置される。したがって、最下位階層の球体により表現される物体形状の誤差は最下位階層の球体の半径以下になる。
また、最下位階層以外の階層の球体は、その上位の階層の球体の中心を通り、かつ立方体領域の長手方向を法線とする平面で節点群を２分割し、各区分に属する全ての節点に基づいて定まる立方体領域を含む最小半径の球体として生成されるのであるから、球体の生成処理を簡単化できる。    さらに、物体表面のみを対象として球体を生成するのであるから、物体に内包される球体はもともと生成されない。したがって、無駄な球体を削除する処理が不要であり、しかも無駄な球体が生成されないので、球体の数を少なくすることができる。
【００３３】
ただし、図６のブロック図において、最上位階層球体生成部５、中間階層球体生成部７として、全ての節点に基づいて定まる立方体領域を含む最小半径の球体を生成する処理に代えて、全ての節点を含む最小半径の球体を生成する処理を行うものを採用することが好ましく、球体内における物体占有率を高めることができる。
【００３４】
また、図６のブロック図において、分割部６として、立方体領域の長手方向を法線とする平面に代えて、全節点の最大分散方向を法線とする平面を採用して分割処理を行うものを採用することが好ましく、分割された各節点群を含む球体内における物体占有率が大なる確率を大きくすることができる。
【００３５】
【実施例３】
図７、図８は、この発明の干渉チェック方法の一実施例を説明するフローチャートである。なお。これらのフローチャートの処理は、図１、図２のフローチャートの処理を行って階層球体モデルが作成された２つの物体について行われる。図７のフローチャートにおいては、ステップＳＰ１において、物体ごとの座標系を共通の座標系（例えば、ワールド座標系）に変換するための変換マトリクスを計算し、ステップＳＰ２において、一方の物体の最上位階層の球体と他方の物体の最上位階層の球体とについて図８のフローチャートの処理を行い、ステップＳＰ３において両物体が交差していないと判断し、そのまま一連の処理を終了する。
【００３６】
図８のフローチャートにおいては、半径が大きい方の球体をＡ、半径が小さい方の球体をＢでそれぞれ表している。
ステップＳＰ１において、それぞれの球体のグローバル値（中心座標および半径）を計算する。ただし、既に計算されている場合には、この処理を省略してもよい。そして、ステップＳＰ２において、球体Ａ，Ｂの中心間距離を計算し、中心間距離と両球体の半径の和との大小を判定することにより、両球体の交差を判定する。そして、交差していないと判定された場合には、そのまま元の処理に戻る。ステップＳＰ２において交差していると判定された場合には、ステップＳＰ３において、球体Ａに子供（球体Ａよりも下位の階層の球体）が有るか否かを判定し、子供が有ると判定された場合には、ステップＳＰ４において、球体Ａの子供Ａｉ（ｉ＝１，２，・・・）の何れかを選択し、ステップＳＰ５において球体Ａｉと球体Ｂについて図８のフローチャートの処理を行い、ステップＳＰ６において球体Ａの全ての子供Ａｉについて図８のフローチャートの処理が行われたか否かを判定し、図８のフローチャートの処理が行われていない子供が存在すると判定された場合には再びステップＳＰ４の処理を行う。逆に、ステップＳＰ６において全ての子供Ａｉに対して図８のフローチャートの処理が行われたと判定された場合には、元の処理に戻る。
【００３７】
ステップＳＰ３において球体Ａに子供がないと判定された場合には、ステップＳＰ７において、球体Ｂに子供（球体Ｂよりも下位の階層の球体）が有るか否かを判定し、子供が有ると判定された場合には、ステップＳＰ８において、球体Ｂの子供Ｂｉ（ｉ＝１，２，・・・）の何れかを選択し、ステップＳＰ９において球体Ｂｉと球体Ａについて図８のフローチャートの処理を行い、ステップＳＰ１０において球体Ｂの全ての子供Ｂｉについて図８のフローチャートの処理が行われたか否かを判定し、図８のフローチャートの処理が行われていない子供が存在すると判定された場合には再びステップＳＰ８の処理を行う。逆に、ステップＳＰ１０において全ての子供Ｂｉに対して図８のフローチャートの処理が行われたと判定された場合には、元の処理に戻る。
【００３８】
ステップＳＰ７において球体Ｂに子供がないと判定された場合には、ステップＳＰ１１において両物体が交差していると判定し、一連の処理を終了する。
したがって、両物体の最上位階層の球体どうしが交差していない場合には、直ちに両物体が交差していないと判定することができる。逆に、最上位階層の球体どうしが交差している場合には、順次下位の階層の球体との交差を判定し、途中において該当する全ての球体どうしが交差していないと判定された場合には、両物体が交差していないと判定することができる。また、最下位階層の球体どうしが交差していると判定された場合にのみ両物体が交差していると判定することができ、干渉チェックの高速化、高精度化を達成することができる。
【００３９】
特に、この実施例では、図１、図２のフローチャートにより作成された階層球体モデルを採用している関係上、最下位階層の球体により表現される物体形状の誤差が、最下位階層の球体の半径以下になるので、高精度の干渉チェックを達成することができる。また、各球体における物体の占有率が高いのであるから、この面からも干渉チェックの高精度化を達成することができる。
【００４０】
【実施例４】
図９はこの発明の干渉チェック装置の一実施例を示すブロック図である。
この干渉チェック装置は、図６の装置により作成された階層球体モデルを保持する階層球体モデル保持部１１と、両物体それぞれの座標系から共通の座標系への変換を行うための変換マトリクスを算出する変換マトリクス算出部１２と、階層球体モデル保持部１１に保持されているそれぞれの物体の階層球体モデルから、未処理の階層のうち最上位の階層の球体を抽出する第１抽出部１３と、第１抽出部１３により抽出された球体のそれぞれに対して該当する変換マトリクスに基づく座標変換を行う第１座標変換部１４と、第１座標変換部１４により座標変換が行われた両球体どうしの交差判定を行う交差判定部１５と、両球体どうしが交差していないことを示す交差判定部１５の判定結果に応答して、該当する階層に属する全ての球体についての処理が行われたか否かを判定する処理終了判定部１６と、該当する階層に属する全ての球体についての処理が行われたことを示す処理終了判定部１６の判定結果に応答して、両物体が交差していないことを示す干渉チェック結果を出力する第１干渉チェック結果出力部１７と、両球体どうしが交差していることを示す交差判定部１５の判定結果に応答して、該当する両球体が共に最下位階層の球体であるか否かを判定する最下位階層球体判定部２０と、該当する球体の少なくとも一方が最下位階層の球体でないことを示す最下位階層球体判定部２０の判定結果に応答して、第１抽出部１３を反復動作させる反復制御部２１と、該当する両球体が共に最下位階層の球体であることを示す最下位階層球体判定部２０の判定結果に応答して、両物体が交差していることを示す干渉チェック結果を出力する第２干渉チェック結果出力部２２とを有している。
【００４１】
上記交差判定部１５は、最も最初に第１抽出部１３により抽出された球体どうしの交差判定を行う場合に第１判定手段として機能し、２回目以降に第１抽出部１３により抽出された球体どうしの交差判定を行う場合に第２判定手段として機能する。
なお、第１抽出部１３においては、両階層球体モデルにおいて同時に次の階層の球体を抽出するのではなく、一方の球体として元の球体をそのまま採用し、他方の球体として次の階層の球体を抽出する。また、上記の構成各部における処理は図７、図８のフローチャートの該当するステップの処理と同様であるから詳細な説明を省略する。もちろん、これら構成各部は、ハードウェアで構成されてもよいが、図７、図８に示す処理を行うプログラムが組み込まれたコンピュータで構成することが好ましい。
【００４２】
したがって、両物体の最上位階層の球体どうしが交差していない場合には、直ちに両物体が交差していないと判定することができる。逆に、最上位階層の球体どうしが交差している場合には、順次下位の階層の球体との交差を判定し、途中において該当する全ての球体どうしが交差していないと判定された場合には、両物体が交差していないと判定することができる。また、最下位階層の球体どうしが交差していると判定された場合にのみ両物体が交差していると判定することができ、干渉チェックの高速化、高精度化を達成することができる。
【００４３】
特に、この実施例では、図６のブロック図に示す装置により作成された階層球体モデルを採用している関係上、最下位階層の球体により表現される物体形状の誤差が、最下位階層の球体の半径以下になるので、高精度の干渉チェックを達成することができる。また、各球体における物体の占有率が高いのであるから、この面からも干渉チェックの高精度化を達成することができる。
【００４４】
【具体例】
２次元平面上で、Ｌ字型形状と斜めの線分に対し、従来方法と本発明の方法を手作業で適用した。｛ただし精度は、０．５とした。最小円（最下位階層球体に対応する円）の半径は、従来方法の場合０．２５、本発明方法の場合０．５にそれぞれ設定した。｝この結果を表１に示す。
【００４５】
【表１】
0003612781.tif 000002
【００４６】
２次元から３次元への拡張を考えてみると、円の数について２次元形状では、辺（１次元）上に配置しているのを３次元形状では、面（２次元）上に配置することになる。したがって、（３次元形状での球の数比）＝（２次元形状での円の数比）の２乗になる。円の面積合計について、２次元形状では、面積（半径の２乗）であったのが３次元形状では、体積（半径の３乗）になる。したがって、（３次元形状での球の平均体積比）＝（２次元形状での円の平均面積比）の３／２乗、（３次元形状での球の体積合計比）＝（３次元形状での球の平均体積比）×（３次元形状での球の数比）になる。
【００４７】
なお、Ｌ字型形状について、従来方法により階層球体モデルを作成した場合を図１１に、本発明方法により作成した場合を図１０に、斜めの線分について、従来方法により階層球体モデルを作成した場合を図１３に、本発明方法により作成した場合を図１２にそれぞれ示している。したがって、従来方法に対する本発明の比率は表２の通りになる。
【００４８】
【表２】
0003612781.tif 000003
【００４９】
表２において球の数が干渉チェック時の交差判定回数を表わし、球の体積合計比が物体占有率を表わしていると考える。干渉チェック時の２つの球の交差判定において、交差していると判断される確率は球の体積に比例する。交差していると判断された場合は、さらに下位の球の交差判定に入ってしまうため、干渉チェック全体の所要時間は、球の体積に比例することになる。
【００５０】
したがって、（干渉チェックの所要時間比）＝（交差判定回数比）×（交差している確率比）＝（球の数比）×（球の体積合計比）になる。これの具体的な値は表３に示す通りである。
【００５１】
【表３】
0003612781.tif 000004
【００５２】
【発明の効果】
請求項１の発明は、最下位階層の球体により表現される物体形状の誤差を球体の半径以下にすることができ、また、当初から物体の表面のみをメッシュ分割して球体を生成するのであるから、物体に内包される球体はもともと生成されず、処理の複雑化を伴なうことなく、生成される球体の数を減少させることができるという特有の効果を奏する。
【００５３】
請求項２の発明は、最上位階層の球体内の物体占有率を大きくすることができ、中間階層の球体内の物体占有率を大きくすることができる確率を高めることができるという特有の効果を奏する。
請求項３の発明は、最下位階層の球体により表現される物体形状の誤差を球体の半径以下にすることができ、また、当初から物体の表面のみをメッシュ分割して球体を生成するのであるから、物体に内包される球体はもともと生成されず、処理の複雑化を伴なうことなく、生成される球体の数を減少させることができるという特有の効果を奏する。
【００５４】
請求項４の発明は、最上位階層の球体内の物体占有率を大きくすることができ、中間階層の球体内の物体占有率を大きくすることができる確率を高めることができるという特有の効果を奏する。
請求項５の発明は、高速に、かつ高精度に干渉チェックを行うことができるという特有の効果を奏する。
【００５５】
請求項６の発明は、高速に、かつ高精度に干渉チェックを行うことができるという特有の効果を奏する。
【図面の簡単な説明】
【図１】この発明の階層球体モデル作成方法の一実施例を説明するフローチャートである。
【図２】この発明の階層球体モデル作成方法の一実施例を説明するフローチャートである。
【図３】球体の生成処理および全節点の２分割処理を説明する概略図である。
【図４】メッシュ分割の一例および最下位階層の球体の配置例を示す概略図である。
【図５】階層構造球体モデルの一例を示す図である。
【図６】この発明の階層構造球体モデル作成装置の一実施例を示すブロック図である。
【図７】この発明の干渉チェック方法の一実施例を説明するフローチャートである。
【図８】この発明の干渉チェック方法の一実施例を説明するフローチャートである。
【図９】この発明の干渉チェック装置の一実施例を示すブロック図である。
【図１０】この発明の階層球体モデル作成方法により作成された階層球体モデルの一例を示す図である。
【図１１】従来方法により作成された階層球体モデルの一例を示す図である。
【図１２】この発明の階層球体モデル作成方法により作成された階層球体モデルの他の例を示す図である。
【図１３】従来方法により作成された階層球体モデルの他の例を示す図である。
【符号の説明】
３    メッシュ分割部        ５    最上位階層球体生成部
６    分割部        ７    中間階層球体生成部
１５    交差判定部        １７    第１干渉チェック結果出力部
２１    第２干渉チェック結果出力部        ２２    反復制御部
【図１】
0003612781.tif 000005
【図２】
0003612781.tif 000006
【図３】
0003612781.tif 000007
【図４】
0003612781.tif 000008
【図５】
0003612781.tif 000009
【図６】
0003612781.tif 000010
【図７】
0003612781.tif 000011
【図８】
0003612781.tif 000012
【図９】
0003612781.tif 000013
【図１０】
0003612781.tif 000014
【図１１】
0003612781.tif 000015
【図１２】
0003612781.tif 000016
【図１３】
0003612781.tif 000017