(57)【要約】　　　（修正有）【課題】２つの凸図形間の高速・高精度な判定方法を提供する手段を提供する．【解決手段】請求項１は２図形の近似交点から次回の近似交点を決定する手段と収束可否判定をする手段よりなる．請求項２はメッシュ構成手段と，メッシュと稜線（面）の対応手段と手段と，質問情報から特定したメッシュに対応する稜線（面）を出力する手段よりなる．【選択図】図１
2004054860.tif 000002
【特許請求の範囲】
【請求項１】
２つの２（３）次元凸図形Ｑｍ（ｍ＝１，２）の間で交差部分が存在するかどうかを判定するシステムにおいて，まずｊ＝１とし，近似交差稜曲線（面）Ｓｍ，ｊと該稜曲線（面）上の近似交点Ｐｍ，ｊをＱｍから１組ずつ適当に選び，点Ｐｍ，ｊ間の距離が予め指定した誤差距離ε（＞０）以下であるかどうかの検査を行い，ε以下であれば２つの図形は交差すると判断して処理を終了し，そうでない場合，かつｊ≠１の場合はＱ１とＱ２は交差する可能性が残っているかどうかを検査し，交差する可能性が残っていないと判断した場合は処理を終了し，そうでない場合はＰｍ，ｊにおけるＳｍ，ｊの接線（平面）の交点（交線上の適当に選んだ点）を求め，ｊ＝ｊ＋１とし，該点をＫｊとし，Ｋｊの近傍にある稜曲線（面）Ｓｍ，ｊを検索し，求めた該稜曲線（面）Ｓｍ，ｊ上の点Ｐｍ，ｊを適当に定め，上記に述べた処理を繰り返すことを特徴とする図形交差判定システム．
【請求項２】
２（３）次元図形Ｑの稜線（面）Ｓの部分集合が与えられた時，該部分集合を内包する２（３）次元空間をメッシュに分割して，各メッシュと各Ｓとの間に対して，対応関係を該メッシュと該Ｓとの間の位置関係が予め定めた一定条件を満たす時に対応関係を与え，メッシュを直接的に，あるいは間接的に特定できる質問情報が与えられた時，特定されたメッシュをキーワードにして該メッシュに対応つけられたＳを出力する図形検索システムにおいて，Ｒの中にＱに対応して適当に定めた点Ｏを座標原点とする極座標系を定め，２次元偏角φ−動径ρ座標系（２次元偏角φ−天頂角θ−動径ρ座標系）空間を，適当に定めた幅Δφ（Δφ，Δθ）を持つ１（２）組の偏角（偏角−天頂角）座標軸平行等間隔格子で区切って，動径ρ座標軸方向に無限の領域を持った凸錐形状のメッシュに分割し，得た各メッシュ毎に必要性に応じて，該メッシュを，適当に定めたより細かなΔφ（Δφ，Δθ）の幅を持つ１（２）組の偏角φ（偏角φ，天頂角θ）座標軸平行等間隔格子でさらに分割することを下方に繰り返すことにより，不均等な大きさを持つメッシュに分割して得た多階層構造を持つメッシュ群の各メッシュｍに対し，あるいは各メッシュｍに一様に，必要に応じて，数列ρｉ（ｉ＝１，２，・・・，ρｍａｘ，ρｉ＜ρｉ＋１（ｉ＜ρｍａｘ））を与え，中心をＯとし，半径ρｉの同心円によってｍを細分して得たメッシュを用いることを特徴とする図形検索システム．
【発明の詳細な説明】
【０００１】
【発明の所属する技術分野】
本発明は２凸図形間の交差判定をするシステムの実現技術に関する．
【０００２】
【従来の技術】
請求項１に関しての従来の技術についてまず述べる．２物体間の交差判定手法は，ＣＡＤ／ＣＡＭ，ロボット制御，コンピュータグラフィックス，その他数多くの局面で必要とされる基本的な図形処理ツールである．近年，計算機を用いたシミュレーションやアニメーションが頻繁に行われ，ダイナミックに位置が変動する物体間には交差判定処理が繰り返し用いられている．この際，図形が曲面の場合は交差判定の前に多数の多面体に近似して，交差判定に用いる事が広く行われているが，形状モデリング精度向上の要求が高い場合，近似多面体の頂点数ｎを増加させる必要があり，その結果，交差判定性能の大幅な劣化を招くことになる．そのため，長年研究者の間で高速交差判定手法の開発が競われ，多くの手法が提案されてきた．
【０００３】
しかしながら，２つの２次元凸多角形の交差する可能性のある候補稜線（面）群を逐次的に限定して，候補数を絞り込み，最後に交差する稜線（面）を見つける手法〔Ｂ．Ｃｈａｚｅｌｌｅ　ａｎｄ　Ｄ．Ｄｏｂｋｉｎ　：ＤＥＴＣＴＩＯＮ　ＩＳ　ＥＡＳＩＥＲ　ＴＨＡＮ　ＣＯＭ　Ｐ　ＵＴＡＴＩＯＮ；ＡＣＭ０−８７９１−０１７−６，１９８０〕はｌｏｇ（ｎ）（ｎは２凸多角形の頂点数の合計）の手法として１９８０年に発表されて以来，現在まで，これより速い手法は開発されていない．また，Ｂ．Ｃｈａｚｅｌｌｅらの手法は稜線を直線に限定している．
【０００４】
交差判定研究の究極目標は，性能が稜線（面）数に依存せず，図形の各稜曲線（面）を近似図形を用いずに曲線（面）のまま用いて交差判定を行うことが可能な高速・高精度な判定方法を実現することである．
【０００５】
次に請求項２に関しての従来の技術について述べる．請求項２は，請求項１において，一点Ｋｊが与えられた時，Ｋｊの最近傍にある図形Ｑｍの稜曲線（面）Ｓｍ，ｊの検索に要する記憶容量を削減する目的のために提供される．
【０００６】
請求項２の類似技術として，予め，３次元多面体Ｑの表面の近傍空間を３次元格子で分割し，得られたメッシュ毎に，該メッシュの内点から最短距離にあるＱの稜面の集合を該メッシュに対応つけておき，質問点Ｋが与えられた時，Ｋを含むメッシュをまず特定し，特定したメッシュに対応つけた稜面の集合を検索結果として出力する方法が公知（Ｋ．Ｋａｗａｃｈｉ　ａｎｄ　Ｈ．ｓｕｚｕｋｉ；Ｄｉｓｔａｎｃｅ　Ｃｏｍｐｕｔａｔｉｏｎ　ｂｅｔｗｅｅｎ　Ｎｏｎ−ｃｏｎｖｅｘ　Ｐｏｌｙｈｅｄｒａ　ａｔ　ｓｈｏｒｔ　Ｒａｎｇｅ　Ｂａｓｅｄ　ｏｎ　Ｄｉｓｃｒｅｔｅ　Ｖｏｒｏｎｏｉ　Ｒｅｇｉｏｎ）となっている．該公知例では，Ｑの周辺の３次元空間Ｒを３次元ｘ−ｙ−ｚＣａｒｔｅｓｉａｎ直交座標系の座標軸に平行な等間隔格子で分割している．
【０００７】
しかし，一般的には図形Ｑの各稜面ＳとＳの周辺の空間点Ｋとの相対位置関係は，該稜面Ｓの任意の点における法線ベクトル上の任意の点Ｐと各稜面Ｓとの相対位置関係とは相関関係がある場合がある．たとえば，Ｑを内点Ｏを適当に選び，原点Ｏを始点とし，任意の点Ｋを通る半直線Ｌと，該半直線Ｌの持つ偏角−天頂角の値に近い偏角−天頂角を持った始点をＯとする他の半直線との間では，両半直線が交差するＱの稜曲面は同一である可能性が高い．また，Ｑの外部の任意の一点Ｋから最も近いＱの稜面の集合は，Ｏを始点としＫを通る半直線ＯＫ上のＫとは異なる任意の点ＫＫから最も近いＱの稜面の集合と共通集合を持つ可能性が高い．しかし，該公知例のようにメッシュに区切るための格子としてｘ−ｙ−ｚＣａｒｔｅｓｉａｎ直交座標軸に平行の格子を用いると，各メッシュに対応させる稜面の数が大きくなりがちであり，１つのメッシュ当たりに対応させる稜曲面数の最大値を小さくしようとすると，メッシュ数を大きくする必要が生じる．
【０００８】
一方，図形Ｑが２次元の場合，一点Ｋが与えられた時，図形Ｑに対応して定めた点Ｏを始点としＫを通る半直線と交差する図形の稜線（面）候補を高速に検索するための検索機能を実現しようとすると，Ｏを始点とし，該図形の稜線Ｓ上を移動する点Ｐを通る半直線の偏角を座標軸とする１次元座標空間上で描く軌跡図形ＳＳにＳを１対１に対応させ，該図形Ｑの各稜線に対応するＳＳが分布する空間ＲＲ内に位置する任意の値の偏角φを持つ質問点Ｋが与えられたとき，Ｋを含む領域ＳＳを特定するための領域検索を行う問題に対しては，図形Ｑの各稜線Ｓｉ（ｉ＝１，２，・・・，Ｓｍａｘ）の始点と終点の偏角をそれぞれφｓｉ，φｅｉ（φｓｉ＜φｓｉ＋１，φｅｉ＜φｅｉ＋１）としたとき，φｅｉを昇順に並べた表を用いて，φｅｊ−１＜φ≦φｅｊを満足させるようなφｅｊを検索する手法として，公知の２分探索法が利用でき，その処理時間はＯ（ｌｏｇ（Ｓｍａｘ））となる．しかし，処理時間は必ずＳｍａｘに依存してしまう．
【０００９】
一方，特に図形Ｑが３次元の場合，一点Ｋが与えられた時，図形Ｑに対応して定めた点Ｏを始点としＫを通る半直線と交差する図形の稜線（面）候補を高速に検索するための検索機能を実現しようとする場合，図形Ｑ毎に対応して定めた点Ｏを始点とし，該図形の稜線（面）Ｓ上を移動する点Ｐを通る半直線の偏角と天頂角を座標軸とする２次元直交座標空間上で描く軌跡図形ＳＳにＳを１対１に対応させ，該図形Ｑの各稜線（面）に対応するＳＳが分布する空間ＲＲ内に位置する指定された偏角と天頂角を座標値として持つ質問点Ｋが与えられたとき，Ｋを含む領域ＳＳを特定するための領域検索を行う問題に対しては，この問題を点位置決定問題として見なすことができ，すべてのＳＳを多角形近似したときの稜点数の合計をｄとすると，Ｓａｒｎａｋ−Ｔａｒｊａｎの方法〔譚学厚，平田富雄；計算幾何学入門，森北出版〕により，Ｏ（ｄ）のメモリを用いて，Ｏ（ｌｏｇｄ）の時間で計算できることが公知となっている．しかし，処理時間はｄに依存する．
【００１０】
【発明が解決しようとする課題】
２つの２（３）次元凸図形間Ｑｍ（ｍ＝１，２）の交差判定処理を行う際，Ｑｍを多角形に近似することなく，稜線（面）を曲線（面）のまま交差判定が可能な高速・高精度な判定方法を提供すること，および，図形Ｑの稜曲線（面）Ｓの集合を内包する２（３）次元空間Ｒをメッシュに分割して，各メッシュとＳとの位置関係で定まる対応関係を与え，メッシュをキーワードにして，Ｓを検索する図形検索システムにおいて，メッシュ管理に必要な記憶容量を削減することを可能にするメッシュ構成手段を提供すること，およびこの手段の利用によって，請求項１が必要とする図形検索機能，すなわち，質問点Ｋが与えられた時，Ｋの近くに存在する図形Ｑの稜線（面）Ｓを検索するために要する必要記憶容量を圧縮する．
【００１１】
【課題を解決するための手段】
請求項１は，Ｑｍ間の第ｊ回目の交点収束計算段階に用いた近似交差稜曲線（面）Ｓｍ，ｊとその上の近似交点Ｐｍ，ｊを用いて次回の近似交差稜曲線（面）Ｓｍ，ｊ＋１とその上の近似交点Ｐｍ，ｊ＋１を求める手段と，交点収束計算の収束性判定手段より構成される．
【００１２】
請求項２は，２（３）次元図形Ｑの稜線（面）Ｓの部分集合を内包する２（３）次元空間Ｒをメッシュに分割する手段と，各メッシュと各Ｓとの対応関係を与える手段と，質問情報から特定メッシュに対応したＳを出力とする手段より構成される．
【００１３】
【作用】
請求項１において，２図形Ｑｍ（ｍ＝１，２）から選んだ近似交差稜曲線（面）Ｓｍ，ｊとＳｍ，ｊの上の近似交点Ｐｍ，ｊの対を用いて，Ｐｍ，ｊにおける稜曲線（面）Ｓｍ，ｊの接線（面）の間の交点（交線の上の適当に選んだ点）Ｋｊ＋１の近傍内に，次回の稜曲線（面）Ｓｍ，ｊ＋１対を選びなおすことによって，前回のＳｍ，ｊ対とは近隣関係になく遠くに存在するＳｍ，ｊを選ぶこともあるので，収束速度がＱｍの稜線（面）の総和に依存せず，真の交点Ｔに高速に近づくことができる．この収束原理は，関数ｆ（ｘ）の根を求めるニュートン法の収束原理と類似性を持つ．
【００１４】
一般的には２（３）次元図形Ｑの各稜面ＳとＳの近傍にある周辺の空間点Ｋとの相対位置関係は，Ｑに対応して選んだ内点Ｏを始点とし，Ｋを通る半直線ＯＫがもしＱの稜曲線（面）Ｓと交差するならば，Ｏを始点とする半直線Ｌの偏角と天頂角が，半直線ＯＫの偏角（偏角と天頂角）に近い値を持つならば，Ｌも該Ｓと交差する可能性が高い．したがって，Ｌの任意の点ＰとＳとの相対位置関係は，点ＫとＳとの相対位置関係と相関関係を持つ可能性がある．また，Ｑの外部の任意の一点Ｋから最も近いＱの稜面の集合は，Ｏを通り，Ｋを通る半直線ＯＫの上の他の任意の点から最も近いＱの稜面の集合との間では共通集合を持つ可能性が高い．
【００１５】
したがって，極座標系の座標軸に平行な面を持ち，かつ多階層構造を持つメッシュを構成する手段を提供する請求項２は，稜曲線（面）に対応させるべきメッシュの大きさを大きくすることができ，結果的にメッシュ数を少なくすることが可能になり，メッシュの管理に必要な記憶容量を削減する．
【００１６】
特に，各メッシュｍと稜線（面）との間に与える対応関係を，該メッシュｍ内の点Ｋを通りＯを始点とする半直線と稜線（面）の間の交点Ｋが存在する関係と定義すれば，極座標の偏角（偏角−天頂角）の軸に沿って平行で等間隔格子で座標空間を分割して生成した動径方向に無限の長さを持った凸錐形状のメッシュｍを動径軸に沿ってさらに細分する必要がなくなり，実質的には１（２）次元偏角（偏角−天頂角）直交座標系空間を偏角（偏角，天頂角）座標軸に平行な境界を持ったメッシュで分割していることになり，分割対象空間が２（３）次元から１（２）次元空間となり，次元を１だけ下げることができるので，メッシュ数も大幅に削減できる．
【００１７】
この場合，請求項２において，Ｋｊに近い図形Ｑｍの稜線（面）Ｓｍ，ｊの候補を直接に検索するのではなく，代わりに，図形Ｑｍに対応して定めたＯｍを始点とし，Ｋｊを通る半直線が交差するか，あるいは半直線の近傍にある稜線（面）の候補を検索することになるが，図形Ｑｍが凸であれば，Ｋｊに近い図形Ｑｍの稜線（面）の候補と，図形Ｑｍに対応して定めたＯｍを始点とし，Ｋｊを通る半直線が交差するか，あるいは半直線の近傍にある稜線（面）の候補とは一致するので問題はない．
【００１８】
また，一般に，稜線（面）の持つ偏角−動径（偏角−天頂角−動径）の極座標系空間における分布は不均一であるので，請求項２における多階層メッシュの大きさは，メッシュ分割に用いる各格子の幅の大きさを分布密度の高い場合は細かく，低い場合は大きくすることによって調整できるので，多階層化せずに一律にメッシュ分割する場合に比べ，メッシュ数を削減できる．
【００１９】
また，各階層におけるメッシュ幅を小さくすれば，該階層のメッシュが管理すべき稜線（面）の数を小さくでき，かつ，その階層の深さを浅くできるので，検索処理時間を短くすることができるが，その半面，必要記憶容量が大きくなる．したがって，検索処理時間を短くすることと，必要記憶容量を大きくするというトレードオフを行うことが可能となっており，交差判定の所要時間設計も可能となっている．
【００２０】
また，請求項２の検索時間は図形の稜線（面）数の総和とは無関係であり，トレードオフを行った事による処理時間の変化は，稜線（面）数の総和とは本質的に無関係であるため，結果的に請求項１の２図形の交差判定に要する時間は，２図形の稜線（面）数の総和とは無関係とすることができる．
【００２１】
【発明の実施の形態】
本発明は，図形間の交差判定を必要とするプログラムに本発明を組み込む形態で実施される．
【００２２】
【実施例】
まず，請求項１にかかわる２次元凸図形の交差判定システムの実施例を説明する．まず，用語の定義をおこなう．凸図形をＱｍ（ｍ＝１，２）とし，その稜曲線をＳｍ，ｉ（ｉ＝１，２，・・・，Ｓｍａｘ）と表す．各稜曲線Ｓｍ，ｉは，｛（ｘ，ｙ）｜ｘ＝ｘｉ（ｔ），ｙ＝ｙｉ（ｔ）（０≦ｔ≦１）｝で定義され，境界はパラメータｔの値のとりうる範囲の両端で決定されるとする．Ｑｍの内部が左側に存在するように各稜線の端点（ｘｉ（０），ｙｉ（０））を始点，（ｘｉ（１），ｙｉ（１））を終点とするように定める．ｘｉ（ｔ），ｙｉ（ｔ）は１階微分が可能な関数であるとする．
【００２３】
図形Ｑｍに対応してＱｍの内点Ｏｍを適当に定め，Ｏｍを極座標系の原点とし，稜曲線Ｓｍ，ｉの始点の偏角をφｍ，ｉ，始点の偏角をθｍ，ｉとする．ＯｍはＱｍの境界を除く内部に自由に定めてよい．しかし，すべてのｉについてのθｍ，ｉ−φｍ，ｉの最小値を可能な限り大きくするようにＯｍを定めるのが望ましい．なお，以下では，ｍが指定された場合はｍ＝１とｍ＝２の処理を行うこととする．
（１）ｊ＝１とする．
（２）ＫｊをＯ１とＯ２を結ぶ線分の中点とする．
（３）Ｏｍを始点とし，Ｋｊを通る半直線ＯｍＫｊと交わる稜曲線Ｓｍ，ｊをＱｍの稜線群からそれぞれ１つずつ検索し，該半直線ＯｍＫｊとＳｍ，ｊとの交点Ｐｍ，ｊをニュートン法で計算して求め，２つのＰｍ，ｊ間の距離が予め指定した誤差距離ε（＞０）以下であれば，Ｑｍは交差すると判断して処理を終了する．
【００２４】
Ｏｍを始点とし，Ｋｊを通る半直線ＯｍＫｊと交わる稜曲線（面）Ｓｍ，ｊを検索する方法の実施例を以下に述べる．まず，Ｏｍを始点とし各稜曲線Ｓｍ，ｉの終点を通るベクトルの偏角θｍ，ｊ（θｍ，ｉ−１＜θｍ，ｊ，２≦ｉ）とすると，第ｉ行にはθｍ，ｊを記憶した偏角−稜曲線辞書テーブルを作成しておく．半直線ＯｍＫｊの偏角θを求め，該テーブルに対し２分探索を行えば，θｍ，ｉ−１＜θ＜θｍ，ｊとなるようなｉを処理時間Ｏ（ｌｏｇＳｍａｘ）で特定できる．
（４）ｊ＝１であれば，Ｏ１とＰ１，ｊの間の距離とＯ２とＰ２，ｊの間の距離との和がＯ１とＯ２の間の距離よりも大きい場合は交差すると判定し処理を終了する．
（５）稜曲線Ｓｍ，ｊ上の点Ｐｍ，ｊにおける接線Ｌｍ，ｉの交点を求め，ｊ＝ｊ＋１とし，該交点をＫｊとする．
（６）ｊ＞１であれば，過去に求めたＬｍ，ｉの対（ｉ＝１，２，・・・，ｊ）を用いて，Ｑｍが交差する可能性が残されているかどうかを判断し，交差する可能性がないと判断した場合は処理を終了し，そうでない場合はｊが予め定めた繰り返し制限回数を越した場合は交差しないとして処理を終了し，そうでない場合は（３）に戻る．
【００２５】
Ｌｍ，ｉの対（ｉ＝１，２，・・・，ｊ）を用いて，Ｑｍが交差する可能性が残されているかどうかを判断する際の実施手順例は下記のとおりである．接線Ｌｍ，ｉがｘ−ｙＣａｒｔｅｓｉａｎ直交座標空間を２分するうち，Ｑｍが属する半平面をＨＱｍ，ｉとすると，２つのＨＱｍ，ｉ（ｍ＝１，２）の共通集合である凸錐をＵＨＱｉとしたとき，任意の２つのＵＨＱｉ，ＵＨＱｋ（１≦ｉ≦ｊ，１≦ｋ≦ｊ，ｉ≠ｋ）の共通集合が空であるようなｉとｋの組み合わせが１つでもある場合，Ｑｍは交差しないと判断する．もうひとつの方法は，ＵＨＱｊとＵＨＱｊ−１だけを取り上げて，その共通集合が空であるかどうかによって，Ｑｍは交差しないと判断するという簡略手法がある．
【００２６】
次に，３次元凸図形の交差判定システムの実施例を説明する．まず，用語の定義をおこなう．凸図形をＱｍ（ｍ＝１，２）とし，その稜曲面をＳｍ，ｉ（ｉ＝１，２，・・・，Ｓｍａｘｍ，ｉ）とし，各Ｓｍ，ｉを｛ｘ，ｙ，ｚ｜ｘ＝ｘｉ（ｔ，ｕ），ｙ＝ｙｉ（ｔ，ｕ），ｚ＝ｚｉ（ｔ，ｕ），０≦ｔ≦１，０≦ｕ≦１，ｘｉ（ｔ，ｕ），ｙｉ（ｔ，ｕ），ｚｉ（ｔ，ｕ）は１階の微分が可能な関数｝とする．各稜曲面Ｓｍ，ｉの稜曲線ＳＬｍ，ｉ，ｇ（ｇ＝１，２，・・・，ＳＬｍａｘｍ，ｉ）の始点と終点は，稜曲線ＳＬｍ，ｉ，ｇの左側がＱｍの内部となるように定め，稜曲線の番号ｇに対しても，稜曲線の左側がＱｍの内部となるように昇順に番号をつける．
【００２７】
図形Ｑｍに対応してＱｍの内点Ｏｍを適当に定める．ＯｍはＱｍの境界を除く内部に自由に定めてよい．しかし，稜曲線Ｓｍ，ｉの上の点Ｐが該稜曲面内を自由に移動したとき，ベクトルＯｍＰの偏角φ，天頂角θの変動域幅をそれぞれφｍ，ｉ，θｍ，ｉとすると，すべてのｉについてのφｍ，ｉ，θｍ，ｉの最小値を可能な限り大きくするようにＯｍを定めるのが望ましい．なお，以下では，ｍが指定された場合はｍ＝１とｍ＝２の処理を行うこととする．下記に手順を述べる．なお，以下では，ｍが指定された場合はｍ＝１とｍ＝２の処理を行うこととする．
【００２８】
（１）ｊ＝１とする．
（２）ＫｊをＯ１とＯ２を結ぶ線分の中点とする．
（３）Ｏｍを始点とし，Ｋｊを通る半直線ＯｍＫｊと交わる稜曲面Ｓｍ，ｊをＱｍの稜面群からそれぞれ１つずつを検索し，該半直線ＯｍＫｊとＳｍ，ｊとの交点Ｐｍ，ｊをニュートン法で計算して求め，２つのＰｍ，ｊ間の距離が指定した誤差距離ε（＞０）以下であれば，Ｑｍは交差すると判断して処理を終了する．
【００２９】
Ｏｍを始点とし，Ｋｊを通る半直線ＯｍＫｊと交わる稜曲線（面）Ｓｍ，ｊを検索する方法の実施例を以下に述べる．まず，Ｑｍ毎に横軸を偏角φ，縦軸を天頂角θとするφθ直交座標系をひとつ用意し，その座標系の中で，Ｓｍ，ｉの上の点ＰがＳｍ，ｉの内部を自由に移動する時のベクトルＯｍＰの偏角φ，天頂角θの軌跡が作る図形をＳφθｍ，ｉとする．すべてのＳφθｍ，ｉは，左下稜点が（０，０），右上稜点が（２π，π）とする矩形ＲＲを隙間なく分割する図形地図を構成する．矩形ＲＲの対辺同士は同一とみなす．図形Ｓφθｍ，ｉはＳｍ，ｉと１対１に対応する．今，外部から偏角φ，天頂角θが与えられたとき，質問点（φ，θ）はどのＳφθｍ，ｉに属するかは，Ｓφθｍ，ｉを多角形近似すれば，点位置決定問題として解決することができ，Ｓａｒｎａｋ−Ｔａｒｊａｎの方法により，その処理時間はＯ（ｌｏｇｄ）（ｄをＳφｍ，ｉを多角形近似した時の全多角形の稜点の数の合計とする）で行える．このようにして検索したＳφθｍ，ｉに１対１に対応するＳｍ，ｉが求める稜面となる．なお，各Ｓφθｍ，ｉは多角形近似を行っているので，始点をＯｍを始点とし，Ｋを通る半直線は検索したＳｍ，ｉと交点Ｐｍ，ｊを持つとは必ずしも保証できない．そこで，交点を持たない場合は，Ｏｍを始点とし該Ｓｍ，ｉに予め適当に定めた内点ＳＯｍ，ｉを通る半直線と，Ｏｍを始点とし質問点Ｋを通る半直線との間に挟まれる凸錐と該Ｓｍ，ｉの稜曲線の交点をＰｍ，ｊとする．
（４）ｊ＝１であれば，Ｏ１とＰ１，ｊの間の距離とＯ２とＰ２，ｊの間の距離との和がＯ１とＯ２の間の距離よりも大きい場合は交差すると判定し処理を終了する．
（５）稜曲面Ｓｍ，ｊ上のＰｍ，ｊにおける接平面Ｌｍ，ｉ間の交線Ｌを求め，Ｐｍ，ｊからＬｍ，ｊへ下ろして得た２つの垂点の中点を求め，ｊ＝ｊ＋１とし，該中点をＫｊとする．
（６）ｊ＞１であれば，Ｌｍ，ｉの対（ｉ＝１，２，・・・，ｊ）を用いて，Ｑｍが交差する可能性が残されているかどうかを判断し，交差する可能性がないと判断した場合は処理を終了し，そうでない場合はｊが予め定めた繰り返し制限回数を越した場合は交差しないとして処理を終了し，そうでない場合は（３）に戻る．
【００３０】
Ｌｍ，ｉの対（ｉ＝１，２，・・・，ｊ）を用いて．Ｑｍが交差する可能性が残されているかどうかを判断する際の実施手順例は下記のとおりである．接平面Ｌｍ，ｉがｘ−ｙ−ｚＣａｒｔｅｓｉａｎ直交座標空間を２分するうち，Ｑｍが属する半空間をＨＱｍ，ｉとすると，２つのＨＱｍ，ｉ（ｍ＝１，２）の共通集合である凸錐をＵＨＱｉとしたとき，任意の２つのＵＨＱｉ，ＵＨＱｋ（１≦ｉ≦ｊ，１≦ｋ≦ｊ，ｉ≠ｋ）の共通集合が空であるようなｉとｋの組み合わせが１つでもある場合，Ｑｍは交差しないと判断する．もうひとつの方法は，ＵＨＱｊとＵＨＱｊ−１だけを取り上げて，その共通集合が空であるかどうかによって，Ｑｍは交差しないと判断するという簡略手法がある．
以上が，請求項１の実施例である．
【００３１】
本方式は，２次元凸図形の稜曲線を線分に限定した場合は２次元凸多角形を扱うことになり，また３次元凸図形の稜曲面を平面に限定した場合は３次元凸多面体を扱うことになり，処理の対象が広範囲であるという特長を有する．
【００３２】
本方式は，２次元凸図形の稜線として直線タイプと曲線タイプのものが混合した凸図形，あるいは３次元凸図形の稜曲面として，平面タイプと曲面タイプのものが混合した凸図形を取り扱うことができ，処理の対象が広範囲であるという特長を有する．
【００３３】
本方式は，２次元凸図形の隣り合う２稜曲線が接合点で接線連続であることを必要とせず，あるいは３次元凸図形の隣り合う２稜曲面が接合稜線で接線連続であることを必要とせず，しかも，２図形間の交点を収束計算で求める際，２つのＳｍ，ｊが大きく離れているために，２つのＳｍ，ｊの組み合わせが頻繁に入れ替わる初期の段階と，Ｓｍ，ｊの組み合わせが固定され，ただＰｍ，ｊの位置が変更されるだけの交点計算収束直前の最終段階とで，交点計算の処理手順の違いがまったくなく，交点計算処理手順が統一的に処理されるという特長，すなわち，互いに接線不連続でつながった稜曲線（面）よりなる図形をあたかも一体の微分可能な曲線（面）として交点計算を行う方式を可能にしているという特徴を有する．
【００３４】
本方式は，交差判定を可能とするだけでなく，交差する場合の稜線（面）番号と交点をも決定しうるという特長を有する．
【００３５】
本方式は，交差判定を可能とするだけでなく，交差しないと判断したときに用いた稜線（面）上の接線（平面）を２図形間の分離線（平面）として提供しうるという特長を有する．
【００３６】
本方式は，２次元においては，偏角から稜線を検索する偏角−稜曲線辞書テーブルを一度作成しておけば，以降は図形が回転・移動を行っても再作成する必要がなく，また，３次元においては偏角−天頂角直交座標系でのＳφθｍ，ｉの図形地図は，Ｑｍが移動・回転しても変化しないので再作成する必要がないため，高速移動する２図形間の交差判定をダイナミックなシミュレーション環境下で高速に実行できるという特徴を有する．
【００３７】
本方式は，交点計算収束回数はＱｍの稜線（面）数に依存しないという特長を有する．
【００３８】
本方式は図形の曲面式をそのまま用いるため，高精度の判定チェックが行えるという特長を有する．
【００３９】
次に，請求項２にかかわる２次元図形検索システムの実施例を説明する．検索対象を２次元凸図形Ｑの稜曲線Ｓｉ（ｉ＝１，２，・・・，Ｓｍａｘ）とし，Ｑに対応して適当に定めたＯを始点とし，質問点Ｋを通る半直線が交差するＳｉを検索する稜線検索システムを例に取り上げる．ＯはＱの境界を除く内部に点を定めるのが望ましい．さらに，すべてのｉについてのθｉ−φｉの最小値が最大となるようなＯを選ぶのが望ましい．この対策は，後で述べる各メッシュに対応させる稜線Ｓｉの最大数を小さくするのに効果がある．
【００４０】
各稜曲線Ｓｉは｛（ｘ，ｙ）｜ｘ＝ｘｉ（ｔ），ｙ＝ｙｉ（ｔ），０≦ｔ≦１｝で定義され，境界はパラメータｔの値のとりうる範囲の両端で決定されるとする．Ｑの内部が左側に存在するように各稜面の端点（ｘｉ（０），ｙｉ（０））を始点，（ｘｉ（１），ｙｉ（１））を終点とするように定める．Ｏを原点と見なした時，Ｓｉ上の始点の偏角をφｉ，終点の偏角をθｉとする．したがってφｉとθｉではさまれた１次元領域〔φｉ，θｉ〕はＳｉに１対１に対応する．すべての〔φｉ，θｉ〕は，０から２πまでの１次元偏角座標領域ＲＲを隙間なく被覆し，互いの重なりはない．
【００４１】
θｉはすでに昇順に並べられているとする．γを適当に定め，長さ２πの１次元領域を幅γで等間隔に細分する．たとえばγ＝２π／Ｓｍａｘとする．このメッシュ分割を第１階層メッシュ分割と呼ぶ．第１階層メッシュ分割では，γ×（ｉ−１）＜θｉ≦γ×ｉ（２≦ｉ）となるようなθｊを番号ｉの第１階層メッシュに対応させて管理する．番号ｉが与えられたメッシュがカバーする偏角領域は［γ×（ｉ−１），γ×ｉ］となる．これによって，質問点Ｋの偏角θを指定すれば高速に，γ（ｉ−１）＜θ≦γｉとなるような稜曲線の候補が検索できる．これらの候補の中から，真に半直線と交わる稜曲線を選択すればよい．しかし，θｉは不均等に分布するので，特定の第１階層メッシュには，多くの稜曲線を管理しなければならない場合が発生する．
【００４２】
そのような第１階層メッシュには子の階層メッシュ分割を設ける．設けるかどうかの判断は，自身の階層の第１階層メッシュからの深さをａとし，第ｉ階層メッシュ分割のメッシュが管理すべき稜曲線の個数の合計をｎｉすると，ａ＋ｎｉ＜Ｍ（予め指定した正の整数）を満足するかどうかで判断し，その不等式を満足する場合は子階層を設けることにし，その不等式を満足しない場合は不等式が成立するようになるまで自身のメッシュ幅を小さくする．この際，メッシュ幅が小さくなりすぎて，全体の必要記憶容量が予め定めた制限を越える場合は，上位の階層のメッシュ幅を広くし，また，別の樹木系統の下にある階層のメッシュの幅を狭くすることにより，必要記憶容量を調整する．
【００４３】
なお，子階層でのメッシュ切りする際の座標軸平行等間隔格子幅の調整前の初期値は，親階層のメッシュの幅をｂとすれば，ｂ／ｎｉ（ｎｉは，当該第ｉ階層のすべてのメッシュが管理すべき稜曲線の個数）にする．
【００４４】
なお，上記に述べた実施例では，検索対象を２次元凸図形Ｑの稜曲線Ｓｉとし，Ｏを始点とし，質問点Ｋを通る半直線が交差するＳｉを検索する稜曲線検索システムを例に取り上げた．そのため，偏角−動径を座標軸とする極座標系においては，凸錐となる各メッシュをさらにρ座標軸に平行な同心円で分割する必要がなかった．
【００４５】
しかし，質問点Ｋに最も近いＳｉを検索する稜線検索システムの場合，かつＱを凹図形とする場合は，Ｏを頂点とする凸錐である各メッシュｍをさらにρ座標軸に平行な同心円で分割する必要がある．なぜなら，Ｑが凹図形の場合，Ｏを始点としＫを通る半直線ＯＫ上の任意の点をＰとすると，Ｐから最短となる稜曲線の数はＰに依存するようになる．その場合，同心円によって細分されるメッシュに対応させる稜曲線の数の最大数を小さくするために，該メッシュに対応して，分割に用いる同心円の半径の数列ρ，（ｉ＝１，２，・・・，ρｍａｘ，ρｉ＜ρｉ＋１（ｉ＜ρｍａｘ））を調整し，動径−稜曲線辞書テーブルを設ける．
【００４６】
Ｋが与えられたときのメッシュの特定方法としては，まず，Ｋを含むφ軸に平行の凸錐であるメッシュｍを特定し，次に特定できた該メッシュｍに対応して設けた動径−稜曲線辞書テーブルを対象に２分探索法で，ρｊ＜ρρ≦ρｊ＋１（ｊ＜ρｍａｘ）となるｊを特定すればよい．ただし，ρρはＯとＫの間の距離とする．
【００４７】
なお，このケースにおいては，各メッシュに管理させる稜曲線の個数は，メッシュの細かさ調整することによって意図的に少なくすることに限界があり，図形Ｑの形状の複雑さ，およびＱの稜曲線数の大きさに依存する．
【００４８】
請求項２にかかわる３次元図形検索システムの実施例を説明する．検索対象を３次元凸図形Ｑの稜曲面Ｓｉ（ｉ＝１，２，・・・，Ｓｍａｘ）とし，Ｑに対応して適当に定めたＯを始点とし，質問点Ｋを通る半直線が交差するＳｉの候補を検索する稜線検索システムを例に取り上げる．
【００４９】
稜曲面Ｓｉは｛ｘ，ｙ，ｚ｜ｘ＝ｘｉ（ｔ，ｕ），ｙ＝ｙｉ（ｔ，ｕ），ｚ＝ｚｉ（ｔ，ｕ），０≦ｔ≦１，０≦ｕ≦１｝で定義される．まず，Ｑに横軸を偏角φ，縦軸を天頂角θとするφθ直交座標系をひとつ用意し，その座標系の中で，Ｓｉの上の点ＰがＳｉの内部を自由に移動するときのベクトルＯＰの偏角φ，天頂角θの軌跡が作る図形をＳφθｉとする．すべてのＳφθｉは，左下の稜点が（０，０），右上の稜点が（２π，π）となる矩形ＲＲを隙間なく分割する．矩形ＲＲの対辺同士は同一とみなす．図形ＳφθｉはＳｉと１対１に対応する．
【００５０】
まず，ＲＲをメッシュ分割するために，第１階層メッシュのメッシュ幅γ，δを適当に定める．たとえばγを２π／Ｓｍａｘ，δをπ／Ｓｍａｘとする．偏角範囲が〔γ×（ｉ−１），γ×ｉ〕で，かつ天頂角範囲が〔δ×（ｊ−１），δ×ｊ〕をもつメッシュにはメッシュ番号（ｉ＋（ｊ−１）×Ｓｍａｘ）を与えるように番号つけたとき，偏角範囲が〔γ×（ｉ−１），γ×ｉ〕で，かつ天頂角範囲が〔δ×（ｊ−１），δ×ｊ〕の領域と共通点を持つような稜面を番号（ｉ＋（ｊ−１）×Ｓｍａｘ）のメッシュに対応させて管理する．これによって，質問点Ｋの偏角φ，天頂角θを指定すれば，Ｏを始点とし，稜面の内部の点Ｐを通過する半直線が該メッシュ領域と交わるような複数の稜面を高速に検索できる．これらの候補の中から，真に半直線と交わる稜曲線を選択すればよい．
【００５１】
しかし，ＳφθｉはＲＲ上に不均等に分布するので，特定の第１階層メッシュには，多くの稜曲面を管理しなければならない場合が発生する．
【００５２】
そのような第１階層メッシュには子の階層メッシュ分割を設ける．設けるかどうかの判断は，自身の階層の第１階層メッシュからの階層の深さをａとし，第ｉ階層メッシュ分割のメッシュが管理すべき稜面の数をｎｊすると，ａ＋ｎｉ＜Ｍ（予め指定した正の整数）を満足するかどうかで判断し，その不等式を満足する場合は子階層を設けることにし，その不等式を満足しない場合は不等式が成立するようになるまで自身のメッシュ幅を小さくする．なお，ｎｊは，図形Ｑの同一頂点を共有する稜線の最大数以下にはできない．
【００５３】
この際，メッシュ幅が小さくなりすぎて，全体の必要記憶容量が予め定めた制限を越える場合は，上位の階層のメッシュ幅を広くし，また，別の樹木系統の下にある階層のメッシュの幅を狭くすることにより，必要記憶容量を調整する．なお，子階層でのメッシュ切りする際の座標軸平行等間隔格子幅の調整前の初期値は，親階層のメッシュの偏角，天頂角方向の幅をそれぞれｂ，ｃとすれば，それぞれｂ／ｎｉ，ｃ／ｎｉ（ｎｉは，第ｉ階層のすべてのメッシュが管理すべき稜面の個数）にする．
【００５４】
なお，上記に述べた実施例では，検索対象を３次元凸図形Ｑの稜曲面Ｓｉとし，Ｏを始点とし，質問点Ｋを通る半直線が交差するＳｉを検索する稜曲面検索システムを例に取り上げた．そのため，偏角−天頂角−動径を座標軸とする極座標系においては凸錐となる各メッシュをさらにρ座標軸に平行な同心円で分割する必要がなかった．
【００５５】
しかし，質問点Ｋに最も近いＳｉを検索する稜曲面検索システムの場合，かつＱを凹図形とする場合は，Ｏを頂点とする凸錐である各メッシュｍをさらにρ座標軸に平行な同心円で分割する必要がある．なぜなら，Ｑが凹図形の場合，Ｏを始点としＫを通る半直線ＯＫ上の任意の点をＰとすると，Ｐから最短となる稜面の数はＰに依存するようになるからである．その場合，同心円によって細分されるメッシュに対応させる稜面の数の最大数を小さくするために，該メッシュに対応して分割に用いる同心円の半径の数列ρｉ（ｉ＝１，２，・・・，ρｍａｘ，ρｉ＜ρｉ＋１（ｉ＜ρｍａｘ））を調整し，動径−稜曲面辞書テーブルを設ける．
【００５６】
Ｋが与えられたときのメッシュの特定方法としては，まず，Ｋを含むφ，θ軸に平行の凸錐であるメッシュｍを特定し，次に特定できた該メッシュｍに対応して設けた動径−稜曲面辞書テーブルを対象に２分探索法で，ρｊ＜ρρ≦ρｊ＋１（ｉ＜ρｍａｘ）となるｊを特定すればよい．ただし，ρρはＯとρの間の距離とする．なお，このケースにおいては，各メッシュに管理させる稜曲面の個数は，メッシュの細かさ調整することによって意図的に少なくすることに限界があり，図形Ｑの形状の複雑さ，およびＱの稜曲面数の大きさに依存する．
以上が，請求項２に関する実施例である．
【００５７】
本特許によれば，２（３）次元凸図形の周辺の質問点Ｋに最も近い稜曲線（面）を検索するためには，２次元図形処理においては長さがπの１次元線分を，３次元図形処理においては縦がπ，横が２πの長さを持った２次元矩形をメッシュ分割すればよく，メッシュ分割対象空間の次元を１つ下げることができ，メッシュの数を少なくすることができる．
【００５８】
本特許によれば，図形Ｑに対応して定めた点Ｏを始点とし，質問点Ｋを通る半直線と交わる稜線（面）を，図形の稜線（面）数に依存しない処理時間で検索できるので，請求項１に適用すれば，図形の交差判定を交差判定対象の２図形の稜線（面）数の総和に依存しない処理時間で実現できる．
【００５９】
本特許によれば，質問点Ｋの最も近い稜線（面）の候補を少ないメッシュ数を用いて検索できる．
【００６０】
本特許によれば，質問点Ｋの最も近い稜線（面）の候補を検索する際，メッシュ幅を調整することにより，メッシュの階層数と，メッシュが管理すべき稜線（面）数を調整できるので，稜線（面）の検索所要時間を制御できる．
【００６１】
本特許によれば，２次元図形処理システムの場合は質問点Ｋの偏角を０，πを指定することにより，図形のとりうるｘ軸方向の座標値の最大値，最小値をもつ可能性のある稜線を高速に検索でき，π／２，３π／２を指定することにより，図形のとりうるｙ軸方向の座標値の最大値，最小値をもつ可能性のある稜線を高速に検索できるので，図形の存在領域を高速に計算することができる．また３次元図形処理システムの場合は質問点の（偏角，天頂角）を（０，π／２），（π，π／２）として指定することにより，図形のとりうるｘ軸方向の座標値の最大値，最小値をもつ可能性のある稜線を高速に検索でき，（π／２，π／２），（３π／２，π／２）として指定することにより，図形のとりうるｙ軸方向の座標値の最大値，最小値をもつ可能性のある稜線を高速に検索でき，（０，０），（０，π）として指定することにより，図形のとりうるｚ軸方向の座標値の最大値，最小値をもつ可能性のある稜線を高速に検索できるので，図形の存在領域を高速に計算することができる．
【００６２】
同様に，図形Ｑに対する指定された法線ベクトルを持つ支持線（面）を求める問題において，該支持線（面）に最も平行稜線（面）の集合を高速に検索できる特徴を有する．
【００６３】
【発明の効果】
２つの２（３）次元凸図形間の交差判定処理を行う際，処理性能が図形の稜曲線（面）数の増加につれて劣化することを判定精度を落とさずに回避できる．
【図面の簡単な説明】
【図１】請求項１における２次元図形間の交差判定処理の実施例において，第１，２回目の稜曲線（面）Ｓｍ，ｊ上の点Ｐｍ，ｊにおける接線Ｌｍ，ｊ間の交点計算結果により得られたＫｊ＋１の近傍にある稜曲線（面）Ｓｍ，ｊ＋１とその上の点Ｐｍ，ｊ＋１を選び直す際の状況図である．
【図２】請求項２の実施例において，３次元図形の稜面の上の点Ｐが該稜面内を自由に移動したときに描かれる偏角−天頂角座標系における移動軌跡図形と，各階層のメッシュが管理すべき稜曲面の数を４に制限した場合の多階層メッシュ分割結果により得られたメッシュと稜曲面の対応状況を示す図である．
【符号の説明】
１．Ｑｍ：交差判定対称図形（ｍ＝１，２）
２．Ｏｍ：Ｑｍに対応して定めたＱｍの内点
３．Ｋｊ：稜曲線Ｓｍ，ｊの上の点Ｐｍ，ｊにおける接線Ｌｍ，ｊの交点
４．Ｓｍ，ｊ：Ｑｍの稜曲線
５．Ｐｍ，ｊ：Ｓｍ，ｊと半直線ＯｍＫｊとの交点
６．Ｌｍ，ｊ：Ｓｍ，ｊのＰｍ，ｊとの交点稜曲線
７．メッシュ
８．両曲面の軌跡図形
【図１】
2004054860.tif 000003
【図２】
2004054860.tif 000004