(57)【特許請求の範囲】
【請求項１】
２次元または３次元形状処理における、干渉部分を有さない二つの閉領域の包含関係判定方法において、
データ処理部が、それぞれ一つまたは複数の境界で定義される二つの閉領域について、第１の閉領域の境界上から抽出したサンプリング点と第２の閉領域との位置関係を調べ、且つ前記サンプリング点が二つの閉領域の接点か否かを判定し、前記二つの閉領域のそれぞれの境界が接すると判定した場合、接点における境界の形状に基づいて包含関係を判定することを特徴とする閉領域の包含関係判定方法。
【請求項２】
請求項１記載の包含関係判定方法において、
前記データ処理部が、接点における二つの境界の接線または接平面に対して二つの閉領域の中心が同じ側であれば二つの閉領域が包含関係を有すると判定することを特徴とする閉領域の包含関係判定方法。
【請求項３】
請求項１または請求項２記載の包含関係判定方法において、
前記データ処理部が、第１の閉領域と第２の閉領域とが包含関係を有すると判定されたとき、第１の閉領域の境界上の接点以外のサンプリング点を端点とする半直線が第２の閉領域の境界と偶数箇所で交わるならば、第１の閉領域が第２の閉領域を包含すると判定することを特徴とする閉領域の包含関係判定方法。
【請求項４】
コンピュータに請求項１〜３のいずれか１項に記載の閉領域の包含関係判定方法を実現させるプログラムを記録したことを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ＣＡＤシステムなど２次元または３次元形状処理システムにおける二つの閉領域の包含関係判定方法に係わり、特に、二つの閉領域の包含関係を正確に判定することができる包含関係判定方法およびこの方法を実施するためのプログラムを記録したことを特徴とする記録媒体に関する。
【０００２】
【従来の技術】
従来より、グラフィクス表示装置とコンピュータとを用いたＣＡＤ／ＣＡＭシステムなど３次元形状処理システムでは、３次元形状を生成したり、生成されている３次元形状を変形させたり、３次元形状上で様々な判定を行ったりしている。なお、３次元形状（３次元立体）とは、境界表現形式のソリッドモデルデータとして生成された形状を指し、その境界表現形式のソリッドモデルとは、稜線や頂点や面というような要素により３次元空間上に閉じた領域を定義し、中身の詰まった立体を表現したものである。
本発明は、このような３次元形状処理システムや２次元形状処理システムにおいて、境界で囲まれた二つの閉領域の包含関係を判定しようとするものであるが、このような技術に係わる従来の技術では、二つの閉領域が干渉部分を有さない場合、二つの閉領域の包含関係を判定するために、一方の閉領域内の点と他方の閉領域との位置関係を調べる。つまり、二つの閉領域が干渉部分を有さない場合には、いずれか一方の閉領域内に求めたサンプリング点が必ず他方の閉領域内に位置している場合には、前者の閉領域全体が後者に包含されていると判定するのである。また、いずれの閉領域についてもサンプリング点が相手の閉領域外に位置している場合には、二つの閉領域が包含関係をもたないと判定する。
そして、この閉領域の包含関係判定のために行う前記のようなサンプリング点と閉領域の位置関係の判定は、サンプリング点を端点にもつ半直線と閉領域の境界を構成する形状要素（たとえば境界曲線）との交点の個数が奇数か偶数かを判定することにより判定する。
【０００３】
【発明が解決しようとする課題】
しかしながら、前記の従来技術においては、サンプリング点が二つの閉領域の接点である場合を考慮していなかったので、二つの閉領域の包含関係を誤って判定してしまうことがあった。本発明の課題は、このような従来技術の問題を解決し、二つの閉領域の包含関係を正確に判定することができる包含関係判定方法およびこの方法を実施するためのプログラムを記録した記録媒体を提供することにある。
【０００４】
【課題を解決するための手段】
前記の課題を解決するために、請求項１記載の発明では、２次元または３次元形状処理における、干渉部分を有さない二つの閉領域の包含関係判定方法において、データ処理部が、それぞれ一つまたは複数の境界で定義される二つの閉領域について、第１の閉領域の境界上から抽出したサンプリング点と第２の閉領域との位置関係を調べ、且つ前記サンプリング点が二つの閉領域の接点か否かを判定し、前記二つの閉領域のそれぞれの境界が接すると判定した場合、接点における境界の形状に基づいて包含関係を判定することを特徴とする。
また、請求項２記載の発明では、前記データ処理部が、接点における二つの境界の接線または接平面に対して二つの閉領域の中心が同じ側であれば二つの閉領域が包含関係を有すると判定することを特徴とする。
また、請求項３記載の発明では、請求項１または請求項２記載の包含関係判定方法において、前記データ処理部が、第１の閉領域と第２の閉領域とが包含関係を有すると判定されたとき、第１の閉領域の境界上の接点以外のサンプリング点を端点とする半直線が第２の閉領域の境界と偶数箇所で交わるならば、第１の閉領域が第２の閉領域を包含すると判定することを特徴とする。
また、請求項４記載の発明は、コンピュータ読み取り可能な記憶媒体に関するものであり、コンピュータに請求項１〜３のいずれか１項に記載の閉領域の包含関係判定方法を実現させるプログラムを記録したことを特徴とする。
【０００５】
【作用】
前記のような手段にしたので、請求項１記載の発明では、二つの閉領域のそれぞれの境界が接する場合、接点における境界の形状に基づいて包含関係が判定される。請求項２記載の発明では、請求項１記載の発明において、接点における二つの境界の接線または接平面に対して二つの閉領域の中心が同じ側であれば二つの閉領域が包含関係を有すると判定される。請求項３記載の発明では、請求項１または請求項２記載の発明において、第１の閉領域と第２の閉領域とが包含関係を有すると判定されたとき、第１の閉領域の境界上の接点以外のサンプリング点を端点とする半直線が第２の閉領域の境界と偶数箇所で交わるならば、第１の閉領域が第２の閉領域を包含すると判定される。請求項４記載の発明では、請求項１〜３記載の閉領域の包含関係判定方法に従ってプログラミングしたプログラムがたとえばＦＤ、ＣＤ−ＲＯＭ、ＭＯなど着脱可能な記録媒体（記憶媒体）に記録（記憶）される。
【０００６】
【発明の実施の形態】
以下、図面により本発明の実施の形態を詳細に説明する。
図１は本発明の実施の形態の一例を示す情報処理装置の構成ブロック図である。図示するように、この実施の形態の情報処理装置は、プログラムを記憶するメモリおよびそのプログラムに従って動作するＣＰＵを有してこの装置全体を制御・管理するシステム制御部１、同様にプログラムを記憶するメモリおよびそのプログラムに従って動作するＣＰＵを有して二つの閉領域の包含関係判定処理などを行うデータ処理部２、閉領域の境界を成す形状要素（たとえば境界曲線）の数値データなどを記憶しておく外部記憶装置（たとえばハードディスク装置）３、各種データを一時的に記憶するデータメモリ４、各種形状や包含関係判定処理結果などを表示する出力装置５などを備えている。
このような構成で、本発明では、包含関係を判定する対象として、次の要件を満たす二つの閉領域 Ｄ1, Ｄ2 を考える。
* 図２に示すように、閉領域は最外殻をなす境界Ｅとこれに囲まれる穴をなすｎ個の境界Ｉi (i = 1, 2, ...,n) から定義される。
* また、閉領域Ｄ1, Ｄ2の位置関係について、それぞれの境界をなす形状要素どうしは、交差する箇所のないことが事前に分かっているものとする。
そして、以下に説明するように、それぞれ一つまたは複数の境界で定義される二つの閉領域について、第１の閉領域の境界上から抽出したサンプリング点と第２の閉領域との位置関係を調べることにより二つの閉領域の包含関係を判定する。前記サンプリング点と第２の閉領域の位置関係は、前記サンプリング点を端点とする半直線と前記第２の閉領域の境界線との交点が偶数、奇数のいずれであるかで判断するのである。
【０００７】
図３に示すように、包含関係を有さない場合では、閉領域Ｄ1上のサンプリング点Ｐ1を端点とする半直線と閉領域Ｄ2の境界線とは、半直線の選び方に応じて実線矢印で示したように偶数(図示の例では４個)の交点をもつか、破線矢印で示したように交点を有さないかのいずれかとなる。閉領域Ｄ2上のサンプリング点Ｐ2と閉領域Ｄ1の関係についても同様である。
それに対して、包含関係を有する場合では状況が異なる。包含する側の閉領域の境界上のサンプリング点を端点とする半直線と包含される側の閉領域は、半直線の選び方に応じて交点を有さないか、偶数の交点を有するかのいずれかとなる。しかし、包含される側の閉領域の境界上のサンプリング点を端点とする半直線と包含する側の閉領域は、奇数の交点を有する。図４に閉領域Ｄ2が閉領域Ｄ1を包含する場合を示す。包含される側である閉領域Ｄ1の境界上のサンプリング点Ｐ1を端点とする半直線は、包含する側の閉領域Ｄ2の境界と奇数（図示の例では３個）の交点をもつ。なお、図４では、閉領域Ｄ2の穴をなす境界と交点を有する方向に半直線を選んだ例が示されているが、穴をなす境界とは交点を有さない方向（たとえば図示の例とは逆方向）に半直線を選んだ場合にも、最外殻を成す境界との交点のみで、奇数（境界の形状の凹凸が激しくなく滑らかであれば１個）となる。
【０００８】
図５に、この実施の形態の動作フローを示す。以下、図５などに従って、動作フローを説明する。
まず、データ処理部２がサンプリング点の座標を決める（Ｓ１）。閉領域の境界を構成する形状要素は一般に複数の要素で構成されることから、各要素つまり曲線または曲面は端点または境界線（境界曲線）の端点をもつので、閉領域 Ｄ1の境界を構成する形状要素上の点である前記のようなサンプリング点Ｐ1の座標はそのような端点として求めるのである。なお、境界を構成する形状要素が、このような端点を有さない一つの真円または球であれば、それらの上に載る任意の点を簡単な計算式から求め、それを端点とする。つまり、中心の座標値が(Ｃx,Ｃy,Ｃz)、半径がＲ (＞０) の球上の任意の点の座標値(Ｐx,Ｐy,ＰZ)は、ある単位ベクトル(Ｅx,Ｅy,Ｅz)を定めて、
(Ｐx,Ｐy,Ｐz) = Ｒ ×(Ｅx,Ｅy,Ｅz) + (Ｃx,Ｃy,Ｃz)
を解くことで得られる。
また、円の場合には、円の載る平面が決まり、その法線ベクトル(Ｎz,Ｎy,Ｎz)が与えられているので、この法線ベクトル(Ｎz,Ｎy,Ｎz)と直交するという条件を満たす単位ベクトル(Ｅx,Ｅy,Ｅz)を定め、球の場合と同一の前記計算式を用いて(Ｐx,Ｐy,Ｐz)を求める。
また、事前に行った二つの閉領域の干渉計算により、二つの閉領域が接する状態にあることが分かっており、既にその接点が得られている場合には、この点をサンプリング点にして、ステップＳ３へ進む。
次に、データ処理部２は閉領域Ｄ1 上のサンプリング点Ｐ1を端点とする半直線を、その通過点を決定することにより決定する。なお、通過点は、サンプリング点Ｐ1と異なる点でありさえすれば任意の位置でよい。
さらに、データ処理部２はたとえば閉領域Ｄ1上のサンプリング点 Ｐ1と前記通過点とを結ぶ直線を通過点側に延長して前記サンプリング点Ｐ1を端点とする半直線と、閉領域Ｄ2の境界との交点を求める（Ｓ３）。なお、その際、交点において半直線が閉領域Ｄ2の接線を成す場合は最終的な判別が困難であるため、通過点を変えることで別の半直線を求め、やり直す。
さらに、サンプリング点で二つの閉領域が接しているか否かを判定する（Ｓ４）。前記交点がサンプリング点 Ｐ1 の位置にある場合は、その点を接点として閉領域Ｄ1,Ｄ2 の境界どうしが接し合っていることを意味し、この場合（Ｓ４でＹｅｓ）、この接点の載る各閉領域の境界を成す形状要素について、その点における曲率方向を比較することで、包含関係を判定する（Ｓ５）。たとえば、接点における接線または接平面に対して、二つの閉領域の中心が異なる側にあれば、二つの閉領域は包含関係を有さないと判定し（図６参照）（Ｓ５でＮｏ）、ここで処理を終了させる。
【０００９】
また、二つの閉領域の中心が同じ側にあれば、二つの閉領域が包含関係を有すると判定する（図７参照）（Ｓ５でＹｅｓ）。ただし、この時点では、閉領域Ｄ１、Ｄ２のどちらが他方を包含するかまでは分からない。そのため、包含関係があることを示すフラグを立て（Ｓ６）、データメモリ４の所定領域に書き込んだ交点数を０にリセットした上で、ステップＳ１に戻り、別のサンプリング点を選んで処理を繰り返す。また、前記交点が端点（サンプリング点）とは異なる位置にある場合は、前記所定領域に書き込まれている交点数の値を１だけ増やし、他の交点の有無を調べ、あればその度に前記交点数を１づつ増やすことにより交点数を求め、その値が奇数か否かを判定する（Ｓ７）。そして、奇数の場合は（Ｓ７でＹｅｓ）、閉領域Ｄ１のサンプリング点Ｐ１が閉領域Ｄ２の内部にある、つまり、閉領域Ｄ２が閉領域Ｄ１を包含していると判定し（Ｓ８）、処理を終える。それに対して、偶数の場合は（Ｓ７でＮｏ）、閉領域Ｄ１のサンプリング点Ｐ１が閉領域Ｄ２の外部にあるならば、閉領域Ｄ１、Ｄ２が包含関係を有さずに離れて位置しているか、閉領域Ｄ１が閉領域Ｄ２を包含しているかである。そこで、フラグが立っているか否かを判定し（Ｓ９）（Ｓ６参照）、立っていれば（Ｓ９でＹｅｓ）、閉領域Ｄ１、Ｄ２が境界部分で接し合い、且つ包含関係をもつことを意味するので、閉領域Ｄ１が閉領域Ｄ２を包含していると判定し（Ｓ１０）、処理を終える。それに対して、フラグが立っていなければ（Ｓ９でＮｏ）、二つの可能性のいずれであるかを調べるため、閉領域Ｄ２上のサンプリング点Ｐ２と閉領域Ｄ１を対象にして、ステップＳ１から始まる前記と同様の処理を行う（Ｓ１１）。そして、交点数が奇数の場合は（Ｓ１２でＹｅｓ）、閉領域Ｄ１が閉領域Ｄ２を包含すると判定する（Ｓ１０）。また、偶数の場合は（Ｓ１２でＮｏ）、閉領域Ｄ２のサンプリング点Ｐ２が閉領域Ｄ１の外部にあり、前記の結果と合わせて、各閉領域上のサンプリング点がいずれも相手の閉領域内に位置しておらず、したがって、閉領域Ｄ１、Ｄ２は包含関係を有さないと判定する（Ｓ１３）。以上、図１に示した情報処理装置の場合で説明したが、このような本発明の包含関係判定方法に従ってプログラミングしたプログラムをＦＤ、ＣＤ−ＲＯＭ、ＭＯなど着脱可能な記録媒体（記憶媒体）に記録（記憶）させ、その記録媒体をそれまで本発明の包含関係判定方法を行えなかった情報処理装置に装填することにより、その情報処理装置においても本発明の包含関係判定を行うことができる。
【００１０】
【発明の効果】
以上説明したように、請求項１記載の発明では、２次元または３次元形状処理における、干渉部分を有さない二つの閉領域の包含関係判定方法において、データ処理部が、それぞれ一つまたは複数の境界で定義される二つの閉領域について、第１の閉領域の境界上から抽出したサンプリング点と第２の閉領域との位置関係を調べ、且つ前記サンプリング点が二つの閉領域の接点か否かを判定し、前記二つの閉領域のそれぞれの境界が接すると判定した場合、接点における境界の形状に基づいて包含関係を判定するので、単に、第１の閉領域内のサンプリング点を端点とする半直線が第２の閉領域の境界と交わる交点数が奇数か否かを判定して包含関係を判定する場合に比べて判定の精度が向上する。
また、請求項２記載の発明では、請求項１記載の発明において、データ処理部が、接点における二つの境界の接線または接平面に対して二つの閉領域の中心が同じ側であれば二つの閉領域が包含関係を有すると判定されるので、この判定を有効に活かして判定精度を向上させることができる。
また、請求項３記載の発明では、請求項１または請求項２記載の発明において、データ処理部が、第１の閉領域と第２の閉領域とが包含関係を有すると判定されたとき、第１の閉領域の境界上の接点以外のサンプリング点を端点とする半直線が第２の閉領域の境界線と偶数箇所で交わるならば、第１の閉領域が第２の閉領域を包含すると判定されるので、第１の閉領域が前記第２の閉領域を包含するという判定の精度が向上する。
また、請求項４記載の発明では、コンピュータに請求項１乃至請求項３記載の閉領域の包含関係判定方法に従ってプログラミングしたプログラムがたとえば着脱可能な記録媒体に記録されるので、その記録媒体をそれまで本発明の包含関係判定方法を行えなかった情報処理装置に装填することにより、その情報処理装置においても請求項１乃至請求項３記載の発明の効果を実現することができる。
【図面の簡単な説明】
【図１】本発明の実施の形態の一例を示す情報処理装置の構成ブロック図である。
【図２】本発明の実施の形態の一例を示す閉領域の包含関係判定方法の説明図である。
【図３】本発明の実施の形態の一例を示す閉領域の包含関係判定方法の他の説明図である。
【図４】本発明の実施の形態の一例を示す閉領域の包含関係判定方法の他の説明図である。
【図５】本発明の実施の形態の一例を示す閉領域の包含関係判定方法の動作フロー図である。
【図６】本発明の実施の形態の一例を示す閉領域の包含関係判定方法の他の説明図である。
【図７】本発明の実施の形態の一例を示す閉領域の包含関係判定方法の他の説明図である。
【符号の説明】
１：システム制御部
２：データ処理部
３：外部記憶装置
４：データメモリ
５：出力装置
【図１】
0004093440.tif 000002
【図２】
0004093440.tif 000003
【図３】
0004093440.tif 000004
【図４】
0004093440.tif 000005
【図５】
0004093440.tif 000006
【図６】
0004093440.tif 000007
【図７】
0004093440.tif 000008