(57)【要約】【課題】  問題領域すべてに対して、解こうとする問題を重み付きグラフにモデル化して最良優先探索によるグラフの最短経路探索のアルゴリズムを適用するとき、著しく処理時間および記憶容量が増大するのを防ぐ為の技術を提供すること。【解決手段】  以下の処理によりグラフを探索しながら、探索に必要な部分だけ動的にグラフを作成していく。まず（１）問題領域を分割し、（２）始点を含む領域だけグラフを作成し、（３）この領域から最短経路の探索を始め、領域の境界のノードに探索が進んだら隣接する領域のグラフを作る。また、同時に現探索領域と作成した隣接領域のグラフをマージする。そして（３）の処理を探索が終点に到達するまで繰り返す。【選択図】    図１
2006172318.tif 000002
【特許請求の範囲】
【請求項１】
重み付きグラフに対する最短経路を探索する処理を情報処理装置が行う情報処理方法であって、
重み付きグラフに対する最短経路を探索する際に、着目探索ノードが予め重み付きグラフが作成された部分領域の境界上のノードであるか否かを判定する第１の判定工程と、
前記着目探索ノードが前記境界上のノードであると前記第１の判定工程で判定された場合には、前記境界において隣接する部分領域に対して既に重み付きグラフが作成されているか否かを判定する第２の判定工程と、
前記隣接する部分領域について重み付きグラフが作成されていない場合には、当該部分領域に対して重み付きグラフを作成する作成工程と、
前記着目探索ノードの存在する部分領域上の重み付きグラフと前記作成工程において作成された隣接する部分領域上の重み付きグラフとを接続する接続工程と
を備えることを特徴とする情報処理方法。
【請求項２】
着目重み付きグラフに対して既に求まった最短経路の近隣にさらに詳細な新規重み付きグラフを作成する工程と、
前記新規重み付きグラフに対して新規最短経路を探索する工程と、
前記最短経路と前記新規最短経路との長さの差を最短経路の長さの改善値として求める工程と、
前記最短経路の長さの改善値が改善閾値より小さければ前記新規最短経路を最短経路として設定する工程と、
前記最短経路の長さの改善値が前記改善閾値より小さくなければ、前記新規重み付きグラフを着目重み付きグラフとして更新する工程と、
前記作成する工程、前記探索する工程、前記求める工程、前記設定する工程、前記更新する工程、のそれぞれの処理を所定回数繰り返した場合に得られる重み付きグラフに対する最短経路を最短経路として設定する工程と
を備えることを特徴とする請求項１に記載の情報処理方法。
【請求項３】
単一物体を三角形メッシュ分割して前記単一物体上の沿面経路探索を行う情報処理方法であって、
三角形メッシュ上の頂点群のうち経路を探索するための始点、終点の選択を検出する工程と、
重み付きグラフのノードを前記三角形メッシュの頂点または前記三角形メッシュのエッジ上の内挿点として設定する工程と、
前記始点に隣接する三角形パッチ上に重み付きグラフを作成する工程と、
前記作成された探索重み付きグラフに対する最短経路を探索する第１の工程と、
最短経路を探索する際に、着目探索ノードが前記終点であるか否かを判定する第１の判定工程と、
前記判定工程において前記着目探索ノードが前記終点ではない場合に、着目探索ノードが境界ノードであるか否かを判定する第２の判定工程と、
前記着目探索ノードが境界ノードであると判定された場合に、隣接三角形パッチを取得する取得工程と、
着目探索ノードの隣接三角形パッチを取得する場合に、前記着目探索ノードが前記三角形メッシュの頂点の場合には当該頂点を持つ三角形パッチを取得し、前記着目探索ノードが前記三角形メッシュのエッジ上の内挿点である場合には当該内挿点の乗っている三角形メッシュのエッジの両側の三角形パッチを取得する工程と、
取得した隣接三角形パッチに対して重み付きグラフを作成する工程と、
前記重み付きグラフに隣接三角形パッチに対して新たに作成した重み付きグラフを追加して検索する第２の探索工程とを有し、
前記第１の判定工程において着目探索ノードが終点であると判定されるまで前記第１の判定工程から前記第２の探索工程を繰り返し実行することを特徴とする情報処理方法。
【請求項４】
三角形メッシュの各エッジに対する内挿点を挿入する場合に、
前記三角形メッシュを包含する直方体を算出する工程と、
前記直方体の対角線の長さを算出する工程と、
前記対角線の長さと所定のサンプリングパラメータとの積をサンプリング長さとして求める工程と、
前記三角形メッシュの各エッジの長さを算出する工程と、
前記エッジの長さとサンプリング長との商を算出する工程と、
前記商から１引いた数と０とで大きい方をサンプリング個数として求める工程と、
前記サンプリング個数分の内挿点を前記エッジ上にノード間が等間隔に配置されるように挿入する工程と
を備えることを特徴とする請求項３に記載の情報処理方法。
【請求項５】
三角形メッシュの各頂点に処理フラグをオフに初期化して設定する工程と、
前記三角形メッシュの各エッジに処理フラグをオフに初期化して設定する工程と、
前記三角形メッシュの各三角形パッチに処理フラグをオフに初期化して設定する工程と、
各三角形パッチ上に対する重み付きグラフを作成する場合に、
前記三角形パッチの処理フラグがオフであり、
前記三角形パッチの各頂点に対して処理フラグがオフならば、
前記頂点に対する重み付きグラフの作成を行う工程と、
前記頂点の処理フラグをオンにする工程と、
前記三角形パッチの各エッジに対して処理フラグがオフならば、
前記エッジに対する重み付きグラフの作成を行う工程と、
前記エッジの処理フラグをオンにする工程と、
前記三角形パッチに対する重み付きグラフの作成を行う工程と、
各三角形パッチの処理フラグをオンにする工程と
を備えることを特徴とする請求項３に記載の情報処理方法。
【請求項６】
頂点に対する重み付きグラフを作成する場合、各頂点を重み付きグラフのノードとして登録し、
エッジに対する重み付きグラフの作成する場合、当該エッジ上に内挿点を作成し、当該内挿点を重み付きグラフのノードとして登録し、当該エッジ上で隣り合う２ノード間を結ぶアークを２ノード間の長さを重みとして当該重み付きグラフに登録し、
三角形パッチに対する重み付きグラフを作成する場合、
前記三角形パッチの各エッジ上のノードに対し、同一エッジ上にないすべての２ノード間を結ぶアークをノード間の長さを重みとして前記重み付きグラフに登録する
ことを特徴とする請求項５に記載の情報処理方法。
【請求項７】
着目重み付きグラフに対して既に求まった沿面経路の近隣にさらに詳細な新規重み付きグラフを作成する工程と、
前記新規重み付きグラフに対して最短経路を探索する工程と、
前記沿面経路と前記最短経路との長さの差を沿面経路の長さの改善値として求める工程と、
前記沿面経路の長さの改善値が改善閾値より小さければ前記最短経路を沿面経路として設定する工程と、
前記沿面経路の長さの改善値が前記改善閾値より小さくなければ、前記新規重み付きグラフを着目重み付きグラフとして更新する工程と、
前記作成する工程、前記探索する工程、前記求める工程、前記設定する工程、前記更新する工程による各処理を所定回数繰り返すことで得られる重み付きグラフに対する最短経路を沿面経路として設定する工程と
を備えることを特徴とする請求項３に記載の情報処理方法。
【請求項８】
着目重み付きグラフに対して既に求まった沿面経路の近隣にさらに詳細な新規重み付きグラフを作成する場合に、
着目重み付きグラフに対して既に求まった沿面経路が通過する各通過ノードを新規重み付きグラフのノードとして登録する工程と、
前記沿面経路が通過する前記通過ノードと同一エッジ上で隣接する着目グラフ上の各隣接ノードを前記新規重み付きグラフのノードとして登録する工程と、
エッジ上の前記通過ノードおよび前記隣接ノード間に内挿点を作成する工程と、
前記内挿点を前記新規重み付きグラフのノードとして登録する工程と、
各エッジにおいて、前記通過ノード、前記隣接ノード、及び前記内挿点に対応するノードのうち、前記エッジ上で隣り合う２ノード間を結ぶアークをその２ノード間の長さを重みとして前記新規重み付きグラフに登録する工程と、
各三角形パッチに対して、前記三角形パッチの各エッジ上の前記通過ノード、前記隣接ノード、及び前記内挿点に対応するノードに対し、同一エッジ上にないすべての２ノード間を結ぶアークをその２ノード間の長さを重みとして前記新規重み付きグラフに登録する工程と
を備えることを特徴とする請求項７に記載の情報処理方法。
【請求項９】
更に、多面体を三角メッシュに変換する工程を備えることを特徴とする請求項３に記載の情報処理方法。
【請求項１０】
曲面を多面体に近似する工程を備えることを特徴とする請求項３に記載の情報処理方法。
【請求項１１】
重み付きグラフに対する最短経路探索手法としてダイクストラ法を用いることを特徴とする請求項３に記載の情報処理方法。
【請求項１２】
重み付きグラフに対する最短経路探索手法として、３次元上の２点間の距離をヒューリステイック関数とするＡ＊を用いることを特徴とする請求項３に記載の情報処理方法。
【請求項１３】
各部品形状を表現する三角形メッシュの頂点または当該三角形メッシュのエッジ上の内挿点を重み付きグラフのノードとして設定する工程と、
前記三角形メッシュ上の頂点群のうち始点、終点の選択を検出する工程と、
前記第１の点に隣接する三角形パッチ上に重み付きグラフを作成する工程と、
前記探索重み付きグラフに対する最短経路を探索する工程と、
前記着目探索ノードが前記終点であるか否かを判定する工程と、
前記着目探索ノードが終点ではない場合、着目探索ノードが部品境界ノードであるか否かを判定する工程と、
前記着目探索ノードが部品境界ノードである場合、前記着目探索ノードの隣接三角形パッチを取得する工程と、
取得した各隣接三角形パッチに対して重み付きグラフを作成する工程と、
前記着目探索ノードの隣接三角形パッチとのブリッジアークを作成する工程と、
前記重み付きグラフに前記隣接三角形パッチに対して作成した重み付きグラフをマージする工程と
を備えることを特徴とする情報処理方法。
【請求項１４】
三角形メッシュで表現される部品形状よりなる組立品に対して各部品間の接続情報を作成する工程と、
着目部品に対して、隣接する部品上に作成される重み付きグラフのノードの当該着目部品上の近接点を求める工程と、
前記近接点を前記近接点の存在する前記着目部品の三角形パッチに登録する工程と、
前記近接点を前記近接点を持つ他部品上のグラフのノードに登録する工程と、
前記着目探索ノードの隣接三角形パッチを取得する場合は、
前記着目探索ノードが前記三角形メッシュの頂点のとき、その頂点を持つ三角形パッチを取得する工程と、
前記着目探索ノードが前記三角形メッシュのエッジ上の内挿点であるとき、当該内挿点の乗っている前記三角形メッシュのエッジの両側の三角形パッチを取得する工程と、
前記着目探索ノードが近接点のとき、
前記近接点を持つ他部品上のノードが三角形メッシュの頂点のとき、
前記頂点を持つ三角形パッチを取得する工程と、
前記近接点を持つ他部品上のノードが三角形メッシュのエッジ上の内挿点であるとき、当該内挿点の乗っている前記三角形メッシュのエッジの両側の三角形パッチを取得する工程と、
前記着目探索ノードが近接点を持つとき、
前記近接点が登録されている他部品上の近接パッチを取得する工程と、
着目探索ノードが近接点または近接点を持つとき部品境界ノードであると判定する工程と、
ブリッジアークを作成する場合は、
前記着目探索ノードが近接点のとき、
前記着目探索ノードと前記着目ノードを近接点に持つノードの２ノード間を結びノード間の長さを重みとするブリッジアークを作成する工程と、
前記着目探索ノードが近接点を持つとき、
前記着目探索ノードと前記近接点ノードの２ノード間を結びノード間の長さを重みとするブリッジアークを作成する工程と、
前記重み付きグラフに前記隣接三角形パッチに対して作成した重み付きグラフをマージする場合に、
前記探索重み付きグラフに前記隣接三角形パッチに対して作成した重み付きグラフのノード、エッジおよび前記ブリッジアークを追加してマージする工程と
を備えることを特徴とする請求項１３に記載の情報処理方法。
【請求項１５】
三角形メッシュの各エッジに対する内挿点を挿入する場合に、
組立品を包含する直方体を算出する工程と、
前記直方体の対角線の長さを算出する工程と、
前記対角線の長さと所定のサンプリングパラメータとの積をサンプリング長さとして求める工程と、
前記三角形メッシュのエッジの長さを算出する工程と、
前記エッジの長さと前記サンプリング長との商を算出する工程と、
前記商から１引いた数と０とで大きい方をサンプリング個数として設定する工程と、
前記サンプリング個数分の内挿点を前記エッジ上にノード間が等間隔に配置されるように挿入する工程と
を備えることを特徴とする請求項１３に記載の情報処理方法。
【請求項１６】
三角形メッシュの各頂点に処理フラグをオフに初期化して設定する工程と、
前記三角形メッシュの各エッジに処理フラグをオフに初期化して設定する工程と、
前記三角形メッシュの各三角形パッチに処理フラグをオフに初期化して設定する工程と、
各三角形パッチ上に対する重み付きグラフを作成する場合に、
三角形パッチの処理フラグがオフならば、
三角形パッチの各頂点に対して処理フラグがオフならば、
前記頂点に対する重み付きグラフの作成を行う工程と、
前記頂点の処理フラグをオンにする工程と、
前記三角形パッチの各エッジに対して処理フラグがオフならば、
前記エッジに対する重み付きグラフの作成を行う工程と、
前記エッジの処理フラグをオンにする工程と、
前記三角形パッチに対する重み付きグラフの作成を行う工程と、
各三角形パッチの処理フラグをオンにする工程と
を備えることを特徴とする請求項１４に記載の情報処理方法。
【請求項１７】
頂点に対する重み付きグラフを作成する場合に、各頂点を重み付きグラフのノードとして登録し、
エッジに対する重み付きグラフを作成する場合に、
当該エッジ上内挿点を作成する工程と、
前記内挿点を重み付きグラフのノードとして登録する工程と、
前記エッジ上で隣り合うノード間を結ぶアークをノード間の長さを重みとして前記重み付きグラフに登録する工程と、
三角形パッチに対する重み付きグラフを作成する場合に、
前記三角形パッチの各エッジ上のノードに対し、同一エッジ上にないすべての２ノード間を結ぶアークをノード間の長さを重みとして前記重み付きグラフに登録する工程と、
前記隣接パッチに登録されている近接点を重み付きグラフのノードとして登録する工程と、
前記隣接パッチに登録されている各近接点と、前記三角形パッチのエッジ上の２ノード間を結ぶアークをノード間の長さを重みとして重み付きグラフに登録する工程と
を備えることを特徴とする請求項１６に記載の情報処理方法。
【請求項１８】
各部品に対する近接点を求める処理を行う場合に、
各部品形状に対して近接点処理フラグをオフに初期化して設定する工程と、
着目部品の近接点処理フラグがオフならば、当該着目部品に対して、隣接する部品上に作成される重み付きグラフのノードの前記着目部品上の近接点を求め、近接点処理フラグをオンにする工程と
を備えることを特徴とする請求項１４に記載の情報処理方法。
【請求項１９】
着目重み付きグラフに対して既に求まった沿面経路の近隣にさらに詳細な新規重み付きグラフを作成する工程と、
前記新規重み付きグラフに対して最短経路を探索する工程と、
前記沿面経路と前記最短経路の長さの差を沿面経路の長さの改善値として設定する第１の工程と、
前記沿面経路の長さの改善値が改善閾値より小さければ前記最短経路を沿面経路として設定する第２の工程と、
前記沿面経路の長さの改善値が改善閾値より小さくなければ、前記新規重み付きグラフを着目重み付きグラフとして更新する工程と、
前記作成する工程、前記探索する工程、前記設定する第１の工程、前記設定する第２の工程、前記更新する工程による処理を所定回数繰り返した場合に得られる重み付きグラフに対する最短経路を沿面経路として設定する工程と
を備えることを特徴とする請求項１４に記載の情報処理方法。
【請求項２０】
着目重み付きグラフに対して既に求まった沿面経路の近隣にさらに詳細な新規重み付きグラフを作成する場合に、
着目重み付きグラフに対して既に求まった沿面経路が通過する各通過ノードのうち、近接点でないものを新規重み付きグラフのノードとして登録する工程と、
前記沿面経路が通過する近接点でない前記通過ノードと同一エッジ上で隣接する着目グラフ上の各隣接ノードを前記新規重み付きグラフのノードとして登録する工程と、
エッジ上の前記通過ノード、及び前記隣接ノード間に内挿点を作成する工程と、
前記内挿点を前記新規重み付きグラフのノードとして登録する工程と、
前記内挿点の近接点を求める工程と、
前記近接点を近接点の存在する三角形パッチに登録する工程と、
前記近接点を前記新規重み付きグラフのノードとして登録する工程と、
三角形メッシュの各エッジにおいて、前記通過ノード、前記隣接ノード、及び前記内挿点に対応するノードのうち、前記エッジ上で隣り合う２ノード間を結ぶアークをその２ノード間の長さを重みとして前記新規重み付きグラフに登録する工程と、
各三角形パッチに対して、
前記三角形パッチの各エッジ上の通過ノード、隣接ノード、及び内挿点に対応するノードに対し、同一エッジ上にないすべての２ノード間を結ぶアークをその２ノード間の長さを重みとして前記新規重み付きグラフに登録する工程と、
前記三角形パッチに登録されている各近接点と前記三角形パッチのエッジ上の各ノードを結ぶアークをその２ノード間の長さを重みとして前記新規重み付きグラフに登録する工程と
を備えることを特徴とする請求項１９に記載の情報処理方法。
【請求項２１】
更に、多面体を三角メッシュに変換する工程を備えることを特徴とする請求項１３に記載の情報処理方法。
【請求項２２】
曲面を多面体に近似する工程を備えることを特徴とする請求項２１に記載の情報処理方法。
【請求項２３】
重み付きグラフに対する最短経路探索手法としてダイクストラ法を用いることを特徴とする請求項１３に記載の情報処理方法。
【請求項２４】
重み付きグラフに対する最短経路探索手法として、３次元上の２点間の距離をヒューリステイック関数とするＡ＊を用いることを特徴とする請求項１３に記載の情報処理方法。
【請求項２５】
重み付きグラフに対する最短経路を探索するための情報処理装置であって、
前記重み付きグラフに対する最短経路を探索する際に、着目探索ノードが予め重み付きグラフが作成された部分領域の境界上のノードであるか否かを判定する第１の判定手段と、
前記着目探索ノードが前記境界上のノードであると前記第１の判定手段によって判定された場合には、前記境界において隣接する部分領域に対して既に重み付きグラフが作成されているか否かを判定する第２の判定手段と、
前記隣接する部分領域についてまだ重み付きグラフが作成されていない場合には、当該部分領域に対して重み付きグラフを作成する作成手段と、
前記着目探索ノードの存在する部分領域上の重み付きグラフと前記作成手段によって作成された隣接する部分領域上の重み付きグラフとを接続する接続手段と
を備えることを特徴とする情報処理装置。
【請求項２６】
単一物体を三角形メッシュ分割して前記単一物体上の沿面経路探索を行う情報処理装置であって、
三角形メッシュ上の頂点群のうち経路を探索するための始点、終点の選択を検出する手段と、
重み付きグラフのノードを前記三角形メッシュの頂点または前記三角形メッシュのエッジ上の内挿点として設定する手段と、
前記始点に隣接する三角形パッチ上に重み付きグラフを作成する手段と、
前記作成された探索重み付きグラフに対する最短経路を探索する第１の手段と、
最短経路を探索する際に、着目探索ノードが前記終点であるか否かを判定する第１の判定手段と、
前記第１の判定手段において前記着目探索ノードが前記終点ではない場合に、着目探索ノードが境界ノードであるか否かを判定する第２の判定手段と、
前記着目探索ノードが境界ノードであると判定された場合に、隣接三角形パッチを取得する取得手段と、
着目探索ノードの隣接三角形パッチを取得する場合に、前記着目探索ノードが前記三角形メッシュの頂点の場合には当該頂点を持つ三角形パッチを取得し、前記着目探索ノードが前記三角形メッシュのエッジ上の内挿点である場合には当該内挿点の乗っている三角形メッシュのエッジの両側の三角形パッチを取得する手段とと、
取得した隣接三角形パッチに対して重み付きグラフを作成する手段と、
前記重み付きグラフに隣接三角形パッチに対して新たに作成した重み付きグラフを追加して検索する第２の探索手段とを有し、
前記第１の判定手段において着目探索ノードが終点であると判定されるまで前記第１の判定手段から前記第２の探索手段を繰り返し実行する処理手段とを有することを特徴とする情報処理方法。
【請求項２７】
各部品形状を表現する三角形メッシュの頂点または当該三角形メッシュのエッジ上の内挿点を重み付きグラフのノードとして設定する手段と、
前記三角形メッシュ上の頂点群のうち始点、終点の選択を検出する手段と、
前記第１の点に隣接する三角形パッチ上に重み付きグラフを作成する手段と、
前記探索重み付きグラフに対する最短経路を探索する手段と、
前記着目探索ノードが前記終点であるか否かを判定する手段と、
前記着目探索ノードが終点ではない場合、着目探索ノードが部品境界ノードであるか否かを判定する手段と、
前記着目探索ノードが部品境界ノードである場合、前記着目探索ノードの隣接三角形パッチを取得する手段と、
取得した各隣接三角形パッチに対して重み付きグラフを作成する手段と、
前記着目探索ノードの隣接三角形パッチとのブリッジアークを作成する手段と、
前記重み付きグラフに前記隣接三角形パッチに対して作成した重み付きグラフをマージする手段と
を備えることを特徴とする情報処理装置。
【請求項２８】
コンピュータに請求項１乃至２４の何れか１項に記載の情報処理方法を実行させることを特徴とするプログラム。
【請求項２９】
請求項２８に記載のプログラムを格納することを特徴とする、コンピュータ読み取り可能な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、離散化した重み付きグラフで表現される経路モデルに対する最短経路算出技術に関するものである。
【背景技術】
【０００２】
従来の計算機を使った重み付きグラフの最短経路を探索する代表的な手法としては、ダイクストラ法（非特許文献１等参照）やＡ＊（非特許文献２等参照）がある。これらの方法は、始点と終点を与えたとき始点から一番短い経路を始点から波面を広げていくように探索していく代表的な方法である。一旦、解こうとする問題を離散化して重み付きグラフで表現できれば、これらのグラフ探索の手法を利用して効率よく最短経路を求めることができる。
【０００３】
ダイクストラ法、Ａ＊は、ともに最良優先探索手法の一種である。最良優先探索手法とは、重み付きグラフに対する経路探索問題の場合、現在着目している探索中のノード群（探索ノードと呼ぶ）に対して最短距離を見積もる為のある評価関数を定義し、この評価値が一番小さい（最短距離が一番短い）と思われるノード（着目探索ノードと呼ぶ）と隣接するノードのうち、まだ探索ノードになっていない、または着目探索ノードから辿った経路の方が既に探索ノードになったときの経路のときよりも始点からの距離が短くなるノードを探索ノードに加え、着目探索ノードを探索ノードからはずす。最初に始点を着目探索ノードとして、この処理を繰り返すことにより終点までの最短経路を見つけることができる。
【０００４】
ここで評価関数として、ダイクストラ法は始点からそのノードまでの最短距離を使い、Ａ＊は始点からそのノードまでの最短距離にそのノードから終点までの最短距離を見積もるあるヒューリステイック関数の値を加えたものを使う。ここで、ヒューリステイック関数はそのノードから終点までの真の最短距離よりも常に大きくないという制約を持つ。
【０００５】
またこれらのグラフ探索の方法を使って、多面体上の近似的な最短経路を求める手法が金井・鈴木の方法（非特許文献３等参照）である。金井・鈴木の方法は、多面体の頂点およびエッジ上にサンプリングした点をノード、多面体の各構成面上でノード同士を結ぶ線分をアークとする重み付きグラフで多面体上の経路モデルを近似し、その重み付きグラフの最短経路を探索することにより多面体上の近似的な最短経路を求めている。また、金井・鈴木の手法は既に求まった経路の近辺により詳細なグラフを作成し最短経路を求めるという処理を繰り返すことによりさらに精度のよい解を求めている。
【非特許文献１】E. W. Dijkstra, ”A note on two problems in connection with graphs,” Numerische Mathematik, vol. 1, pp. 269-271, 1959
【非特許文献２】P. E. Hart, N. J. Nilsson, and B. Raphael, ”A formal basis for the heuristic determination of minimum cost paths,” IEEE Transactions on Systems Science and Cybernetics, vol. 4, pp. 100-107, 1968
【非特許文献３】T. Kanai and H. Suzuki, ”Approximate shortest path on a polyhederal surface and its application,” Computer-Aided Design, vol. 33, pp. 801-811, 2001
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記のグラフ探索の手法では、解こうとする問題が既に重み付きグラフで表現された後は効率よく最短経路を求めることができるが、探索空間全域に対して問題をモデル化した重み付きグラフを作成すると、重み付きグラフのノードやアークの数が著しく多くなり、重み付きグラフを作成する処理時間の増大、必要とする記憶容量の増大を招くという問題があった。実際に計算機を使ってこのような問題を解く場合、経路探索の時間よりも探索する重み付きグラフを作成する時間の方がはるかに大きくなるので、この時間および使用する記憶容量を減少させることが処理の高速化のためには必須となる。また、実際の経路探索においては探索する領域はグラフの中の極一部であることも多くあるので、ほとんどの作成したグラフは無駄になる。
【０００７】
また、これらのグラフ探索の手法を応用して、物体表面に沿った最短距離、いわゆる沿面距離の近似解を求める金井・鈴木の方法では、詳細な解を求めるためにサンプリング密度を上げた場合初期グラフのサイズが著しく大きくなり、グラフを作成する時間が著しく増大するという問題があった。この場合も、作成したグラフの大半は探索に使われることなく無駄に使われる。例えば図１８は立方体上の面に沿った最短距離をグラフを使って求める例を示す図で、同図（ａ）に示すように初期グラフは直方体全域に作られるが、同図（ｂ）に示すように実際に探索に使われるグラフの領域は極一部である。また、金井・鈴木の方法では組立品に対する沿面経路を求めることもできない。
【０００８】
本発明は以上の問題に鑑みて成されたものであり、問題領域すべてに対して、解こうとする問題を重み付きグラフにモデル化して最良優先探索によるグラフの最短経路探索のアルゴリズムを適用するとき、著しく処理時間および記憶容量が増大するのを防ぐ為の技術を提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の目的を達成するために、例えば本発明の情報処理方法は以下の構成を備える。
【００１０】
即ち、重み付きグラフに対する最短経路を探索する処理を情報処理装置が行う情報処理方法であって、
重み付きグラフに対する最短経路を探索する際に、着目探索ノードが予め重み付きグラフが作成された部分領域の境界上のノードであるか否かを判定する第１の判定工程と、
前記着目探索ノードが前記境界上のノードであると前記第１の判定工程で判定された場合には、前記境界において隣接する部分領域に対して既に重み付きグラフが作成されているか否かを判定する第２の判定工程と、
前記隣接する部分領域について重み付きグラフが作成されていない場合には、当該部分領域に対して重み付きグラフを作成する作成工程と、
前記着目探索ノードの存在する部分領域上の重み付きグラフと前記作成工程において作成された隣接する部分領域上の重み付きグラフとを接続する接続工程と
を備えることを特徴とする。
【００１１】
本発明の目的を達成するために、例えば本発明の情報処理方法は以下の構成を備える。
【００１２】
即ち、単一物体を三角形メッシュ分割して前記単一物体上の沿面経路探索を行う情報処理方法であって、
三角形メッシュ上の頂点群のうち経路を探索するための始点、終点の選択を検出する工程と、
重み付きグラフのノードを前記三角形メッシュの頂点または前記三角形メッシュのエッジ上の内挿点として設定する工程と、
前記始点に隣接する三角形パッチ上に重み付きグラフを作成する工程と、
前記作成された探索重み付きグラフに対する最短経路を探索する第１の工程と、
最短経路を探索する際に、着目探索ノードが前記終点であるか否かを判定する第１の判定工程と、
前記判定工程において前記着目探索ノードが前記終点ではない場合に、着目探索ノードが境界ノードであるか否かを判定する第２の判定工程と、
前記着目探索ノードが境界ノードであると判定された場合に、隣接三角形パッチを取得する取得工程と、
着目探索ノードの隣接三角形パッチを取得する場合に、前記着目探索ノードが前記三角形メッシュの頂点の場合には当該頂点を持つ三角形パッチを取得し、前記着目探索ノードが前記三角形メッシュのエッジ上の内挿点である場合には当該内挿点の乗っている三角形メッシュのエッジの両側の三角形パッチを取得する工程と、
取得した隣接三角形パッチに対して重み付きグラフを作成する工程と、
前記重み付きグラフに隣接三角形パッチに対して新たに作成した重み付きグラフを追加して検索する第２の探索工程とを有し、
前記第１の判定工程において着目探索ノードが終点であると判定されるまで前記第１の判定工程から前記第２の探索工程を繰り返し実行することを特徴とする。
【００１３】
本発明の目的を達成するために、例えば本発明の情報処理方法は以下の構成を備える。
【００１４】
即ち、各部品形状を表現する三角形メッシュの頂点または当該三角形メッシュのエッジ上の内挿点を重み付きグラフのノードとして設定する工程と、
前記三角形メッシュ上の頂点群のうち始点、終点の選択を検出する工程と、
前記第１の点に隣接する三角形パッチ上に重み付きグラフを作成する工程と、
前記探索重み付きグラフに対する最短経路を探索する工程と、
前記着目探索ノードが前記終点であるか否かを判定する工程と、
前記着目探索ノードが終点ではない場合、着目探索ノードが部品境界ノードであるか否かを判定する工程と、
前記着目探索ノードが部品境界ノードである場合、前記着目探索ノードの隣接三角形パッチを取得する工程と、
取得した各隣接三角形パッチに対して重み付きグラフを作成する工程と、
前記着目探索ノードの隣接三角形パッチとのブリッジアークを作成する工程と、
前記重み付きグラフに前記隣接三角形パッチに対して作成した重み付きグラフをマージする工程と
を備えることを特徴とする。
【００１５】
本発明の目的を達成するために、例えば本発明の情報処理装置は以下の構成を備える。
【００１６】
即ち、重み付きグラフに対する最短経路を探索するための情報処理装置であって、
前記重み付きグラフに対する最短経路を探索する際に、着目探索ノードが予め重み付きグラフが作成された部分領域の境界上のノードであるか否かを判定する第１の判定手段と、
前記着目探索ノードが前記境界上のノードであると前記第１の判定手段によって判定された場合には、前記境界において隣接する部分領域に対して既に重み付きグラフが作成されているか否かを判定する第２の判定手段と、
前記隣接する部分領域についてまだ重み付きグラフが作成されていない場合には、当該部分領域に対して重み付きグラフを作成する作成手段と、
前記着目探索ノードの存在する部分領域上の重み付きグラフと前記作成手段によって作成された隣接する部分領域上の重み付きグラフとを接続する接続手段と
を備えることを特徴とする。
【００１７】
本発明の目的を達成するために、例えば本発明の情報処理装置は以下の構成を備える。
【００１８】
即ち、単一物体を三角形メッシュ分割して前記単一物体上の沿面経路探索を行う情報処理装置であって、
三角形メッシュ上の頂点群のうち経路を探索するための始点、終点の選択を検出する手段と、
重み付きグラフのノードを前記三角形メッシュの頂点または前記三角形メッシュのエッジ上の内挿点として設定する手段と、
前記始点に隣接する三角形パッチ上に重み付きグラフを作成する手段と、
前記作成された探索重み付きグラフに対する最短経路を探索する第１の手段と、
最短経路を探索する際に、着目探索ノードが前記終点であるか否かを判定する第１の判定手段と、
前記第１の判定手段において前記着目探索ノードが前記終点ではない場合に、着目探索ノードが境界ノードであるか否かを判定する第２の判定手段と、
前記着目探索ノードが境界ノードであると判定された場合に、隣接三角形パッチを取得する取得手段と、
着目探索ノードの隣接三角形パッチを取得する場合に、前記着目探索ノードが前記三角形メッシュの頂点の場合には当該頂点を持つ三角形パッチを取得し、前記着目探索ノードが前記三角形メッシュのエッジ上の内挿点である場合には当該内挿点の乗っている三角形メッシュのエッジの両側の三角形パッチを取得する手段とと、
取得した隣接三角形パッチに対して重み付きグラフを作成する手段と、
前記重み付きグラフに隣接三角形パッチに対して新たに作成した重み付きグラフを追加して検索する第２の探索手段とを有し、
前記第１の判定手段において着目探索ノードが終点であると判定されるまで前記第１の判定手段から前記第２の探索手段を繰り返し実行する処理手段とを有することを特徴とする。
【００１９】
本発明の目的を達成するために、例えば本発明の情報処理装置は以下の構成を備える。
【００２０】
即ち、各部品形状を表現する三角形メッシュの頂点または当該三角形メッシュのエッジ上の内挿点を重み付きグラフのノードとして設定する手段と、
前記三角形メッシュ上の頂点群のうち始点、終点の選択を検出する手段と、
前記第１の点に隣接する三角形パッチ上に重み付きグラフを作成する手段と、
前記探索重み付きグラフに対する最短経路を探索する手段と、
前記着目探索ノードが前記終点であるか否かを判定する手段と、
前記着目探索ノードが終点ではない場合、着目探索ノードが部品境界ノードであるか否かを判定する手段と、
前記着目探索ノードが部品境界ノードである場合、前記着目探索ノードの隣接三角形パッチを取得する手段と、
取得した各隣接三角形パッチに対して重み付きグラフを作成する手段と、
前記着目探索ノードの隣接三角形パッチとのブリッジアークを作成する手段と、
前記重み付きグラフに前記隣接三角形パッチに対して作成した重み付きグラフをマージする手段と
を備えることを特徴とする。
【発明の効果】
【００２１】
本発明の構成により、問題領域すべてに対して、解こうとする問題を重み付きグラフにモデル化して最良優先探索によるグラフの最短経路探索のアルゴリズムを適用するとき、著しく処理時間および記憶容量が増大するのを防ぐ為の技術を提供することを目的とする。
【発明を実施するための最良の形態】
【００２２】
以下添付図面を参照して、本発明を好適な実施形態に従って詳細に説明する。なお、本発明は以下に説明される実施形態に限定されるものではなく、本発明の主旨の範囲において適宜、変形組み合わせが可能であることはいうまでもない。
【００２３】
以下では、本実施形態に係るグラフの最短経路探索手法を用いて、図４に示すような組立品上の表面を通る最短経路４００、いわゆる沿面距離を通る経路（沿面経路）を探索する処理について説明する。図４は、組立品の例を示す図である。
【００２４】
図４の場合、各直方体が個々の部品であるとする。また、各部品形状は三角形メッシュで表現されているとする。つまり、構成面はすべて三角形パッチで表現されており、各三角形パッチ間の隣接関係情報はすでに得られているものとする。つまり、各三角形パッチの稜線は二つのパッチにより共有されており、各三角形パッチごとに稜線を指定すればその稜線で隣り合う三角形パッチを得ることができる。また、頂点はその頂点を含む三角形パッチの間で図６に示す如く共有されているものとする。図６は、４つの三角形メッシュとこれらを構成する頂点との関係を示す図である。
【００２５】
一般に構成面は平面、円筒面、球面、円錐面、トーラス面、Coons曲面、Bezier曲面、Rational  Bezier曲面、B-Spline曲面、NURBS曲面、などの自由曲面等の幾何形状および、その幾何形状が表現する領域のうちどの部分が構成面になっているかを表現するループ情報などの境界情報より表現される。これらの構成面より構成される任意の形状に関しても、各構成面上の隣接関係、各構成面上にグラフのアークを張る方法があれば以下説明する処理に適用可能である。
【００２６】
ただし、三角形メッシュの場合、構成面が上記のような曲面を含む任意の構成面である場合に比べて、上記のような計算は著しく簡単となるので、本実施形態では主に三角形メッシュ上の沿面経路を探索する手法について取り扱う。
【００２７】
また、構成面が平面のときは多面体となり、一般に各構成面は多角形となるが、各構成面である多角形を分割してすべての構成面を三角形パッチにすることが可能である。従って、この処理により以下説明する処理を任意の多面体に対して適用することは可能である。
【００２８】
また、曲面などの任意の構成面よりなる立体も多面体に近似することにより、図５に示すように、曲面モデルを三角形メッシュに変換することができる。従って、曲面モデルに対しても近似的に本実施形態による方法により沿面経路を求めることが可能となる。図５は、曲面モデル、及びこの曲面モデルを近似した多面体モデルを示す図である。
【００２９】
図３は、本実施形態に係るグラフの最短経路探索手法を用いて、図４に示すような組立品上の表面を通る最短経路４００、いわゆる沿面距離を通る経路（沿面経路）を探索する処理を実行するコンピュータの基本構成を示すブロック図である。このコンピュータとしては、例えば一般のＰＣ（パーソナルコンピュータ）やＷＳ（ワークステーション）等を用いることができる。
【００３０】
同図において２はＣＰＵで、ＲＯＭ３やＲＡＭ４に格納されているプログラムやデータを用いてコンピュータ全体の制御を行うと共に、後述する各処理を実行する。
【００３１】
３はＲＯＭで、コンピュータの設定データや、ブートプログラムなどを格納する。
【００３２】
４はＲＡＭで、記憶媒体１０からロードされたプログラムやデータを一時的に記憶するためのエリアを備えると共に、ＣＰＵ２が各種の処理を実行する際に使用するワークエリアも備える。
【００３３】
５は入力インターフェースで、キーボードやマウスなどにより構成されている入力装置６をバス１に接続するためのインターフェースとして機能するものである。入力装置６は、コンピュータの操作者が操作することで、各種の指示をＣＰＵ２に対して入力することができる。
【００３４】
７は出力インターフェースで、出力装置群８をバス１に接続するためのインターフェースとして機能するものである。出力装置群８は、ＣＲＴや液晶画面などにより構成されており、ＣＰＵ２による処理結果を画像や文字などでもって表示する為の表示装置８ａと、プリンタやプロッタなど、画像や文字などを紙などの記録媒体上に記録する印刷装置８ｂとで構成されているが、これに限定するものではない。
【００３５】
９は外部記憶装置インターフェースで、後述する外部記憶装置１０をバス１に接続するためのインターフェースとして機能するものである。外部記憶装置１０は、ハードディスクドライブ装置などの大容量情報記憶装置であって、ここにＯＳ（オペレーティングシステム）や、ＣＰＵ２にコンピュータが行う後述の各処理を実行させるためのプログラムやデータ等が保存されており、これらの一部若しくは全部はＣＰＵ２の制御に従ってＲＡＭ４にロードされ、ＣＰＵ２による処理対象となる。
【００３６】
なお、外部記憶装置１０に保存されているデータには、以下の説明において既知のデータとして説明されるものも含まれている。
【００３７】
１は上述のＣＰＵ２、ＲＯＭ３、ＲＡＭ４、入力インターフェース５，出力インターフェース７，外部記憶装置インターフェース９を繋ぐバスである。
【００３８】
なお、本コンピュータに更に、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭなどの記憶媒体に記録されたプログラムやデータを読み出し、外部記憶装置１０やＲＡＭ４に出力する記憶媒体ドライブ装置をバス１に接続するためのインターフェースを設け、これにこの記憶媒体ドライブ装置を接続するようにしても良い。
【００３９】
次に、このような構成を備えるコンピュータが行う、本実施形態に係るグラフの最短経路探索手法を用いて、図４に示すような組立品上の表面を通る最短経路４００、いわゆる沿面距離を通る経路（沿面経路）を探索する処理について、同処理のフローチャートを示す図１を用いて説明する。なお、同図のフローチャートに従った処理をＣＰＵ２に実行させるためのプログラムやデータは外部記憶装置１０からＲＡＭ４にロードされており、ＣＰＵ２はこれを用いて処理を実行することで、本実施形態に係るコンピュータは、以下説明する各処理を実行することになる。
【００４０】
まず、ステップＳ１では、組立品の部品形状が曲面で構成されている場合には、これを多面体に変換する処理を行う。もし構成面が平面のみからなる場合はステップＳ１における処理は省略することができる。
【００４１】
ステップＳ２では、多面体を三角形メッシュに変換する。
【００４２】
ステップＳ３では、組立品の部品間の接続関係を認識する。これは各部品のデータを参照することで成されるものである。
【００４３】
次にステップＳ４で始点・終点の設定を行う。これは、コンピュータの操作者が入力装置６を操作して視点、終点を入力する場合には、入力された視点、終点を示すデータを受け付けるようにしても良いし、予め決まっており、そのデータが外部記憶装置１０に保存されている場合には、これをＲＡＭ４にロードする。
【００４４】
始点・終点の選択が検出されると、次にステップＳ５で探索ノードキューの初期化を行い、始点をキューに入れる。また、始点を含む部品上に近接点を算出しておく。
【００４５】
ステップＳ６で実際の重み付きグラフを使って経路を探索していく。この処理については後述する。
【００４６】
ステップＳ７では、ステップＳ６で探索した結果を基に、始点から終点までの経路が存在するかどうかの判定を行い、経路が存在する場合は処理をステップＳ８に進め、最短経路を示すデータをＲＡＭ４上に取得し、経路が存在しない場合は処理をステップＳ９に進め、最短経路が存在しない旨のメッセージを表示装置８ａ上に表示する。なお、この旨のメッセージの通知形態についてはこれに限定するものではない。
【００４７】
次に、上記ステップＳ６における経路探索処理について、ステップＳ６における処理の詳細を示すフローチャートを示す図２を用いて以下説明する。
【００４８】
まずステップＳ６０１で探索キューが空かどうかを判定する。探索の途中でキューが空の場合は経路が存在しないので、経路が存在しないことを出力する。
【００４９】
一方、キューが空でない場合は処理をステップＳ６０２に進め、探索ノードキューの中から指定した評価値が一番高いノードを取り出し、これを着目探索ノードとして以下の処理対象とする。評価の方法により探索手法は変更可能である。また、評価値の高いノードを効率よく取り出すために、本実施形態では優先順位付きキュー（プライオリティーキュー）を使用している。優先順位付きキューの実装としてはヒープ構造を使用している。
【００５０】
次に、ステップＳ６０３では着目探索ノードが終点であるかどうかを判定し、終点であると判定した場合には経路が探索されたとして探索処理を終える。
【００５１】
一方、着目探索ノードが終点でない場合、処理をステップＳ６０４に進め、着目ノードが境界ノードであるかどうかを判定する。境界ノードというのは、他部品と近接するノードであって、他部品上の頂点または稜線上の内挿点の近接点であるかもしくは他部品上に近接点を持つ頂点または稜線上の内挿点のことである。
【００５２】
着目ノードが境界ノードであると判定された場合、その境界ノードに近接する部品上に探索が進むかもしれないので、処理をステップＳ６０５に進め、その隣接する部品上に既に近接点が求められているかどうか判定し、求められていないと判定された場合には処理をステップＳ６０６に進め、その隣接部品上の近接点を求める。
【００５３】
次に、ステップＳ６０７では着目探索ノードに隣接するパッチを求める。ここで、「隣接するパッチ」とは、着目探索ノードを境界上に持つ同一部品上のパッチ、または、着目探索ノードを近接点として持つノードを境界上に持つ他部品上のパッチ、または、着目探索ノードが近接点を持つとき、その近接点の存在する他部品上のパッチである。
【００５４】
次に、ステップＳ６０８では、上記ステップＳ６０７で得られた隣接パッチに対して、重み付きグラフの作成処理を行う。
【００５５】
ステップＳ６０９では着目探索ノードと近接する他部品上のノードを結ぶブリッジアークを作成する。
【００５６】
そしてステップＳ６１０では、ステップＳ６０９までの処理で探索に必要なところのグラフの作成が終わっているので、着目探索ノードを起点としてグラフの探索を行い、探索ノードキューの更新を行う。そして終点が見つかるまたは探索ノードキューが空になるまで再びステップＳ６０１からの処理を行う。
【００５７】
次に、図１に示した各ステップにおける処理についてより詳細に説明する。
【００５８】
ステップＳ１、Ｓ２では、沿面経路を求める組立品を構成する部品形状が一般の曲面モデルである場合、図５に示す如く三角形メッシュへの変換を行う。
【００５９】
ステップＳ１では、二次曲面や自由曲面などの幾何形状で表され、Ｂ−ＲｅｐやＣＳＧなどで表現されたソリッドモデルデータが入力の場合、多面体モデルに近似する変換を行う。多面体モデルは多角形を構成面とするモデルである。市販のＣＡＤモデラーでは、ＶＲＭＬやＳＴＬなどの出力機能をもっておりこのような多角形モデルを出力することができることから、このような機能により曲面モデルデータを多角形モデルへの変換を行う。
【００６０】
ステップＳ２では、ステップＳ１で多面体に変換されたモデルを三角形メッシュに変換する。三角形メッシュは構成面がすべて三角形パッチからなるモデルであり、多面体の構成面である各多角形を三角形に分解することにより変換を行うことができる（処理の例としてエム．アール．ギャレイ氏他の「三角形に分ける単純なポリゴン」（M. R. Garey, D. S. Johnson, F. P. Preparata, and R. E. Tarjan, ”Triangulating a simple polygon,” Information Processing Letters, vol. 7, pp. 175-9, 1978）がある。）。
【００６１】
本処理では最短経路を求めるために、特に、図６に示す如く、各三角形パッチの各辺でどの三角形パッチと接しているかという情報および、隣接する複数のパッチに共有される頂点を一つの頂点として持ついわゆる位相情報を持つものとする。上記ＶＲＭＬモデルでは、位相情報をもともと持っているので、各多角形面を三角形に分解するときこの位相情報を引き継ぐように再構成すればよい。
【００６２】
ＳＴＬで出力された場合は、構成面がすべて三角形パッチよりなるので三角形パッチに分解する必要はないが、位相情報を全く持っておらず、各三角形パッチの頂点の幾何情報しかないので、図７に示すように、まず同一の幾何データを持つ頂点を同一点として認識して、次に、同一の二点を端点とする各辺を共有辺として隣合う三角形パッチを認識するなどの位相認識処理が必要になる。
【００６３】
ステップＳ３では、各部品形状間で、指定して許容誤差以内で近接している部品を隣接部品として認識する。近接する部品間のペアは、AABB(Axis-Aligned Bounding Box) TreeやＯＢＢ(Oriented Bounding Box) Treeなど各部品を包含する矩形などの図形を葉とするツリー構造および各部品の構成面を包含する矩形などの図形を葉とするツリー構造を使って効率よく求めることができる。この処理は部品間の干渉を高速に見つける手法と基本的に同様である。（処理の一例としてゴシャーク氏等の「ＯＢＢツリー：高速干渉検出のための階層構造」（S.Gottschalk,M.C.Lin and D.Manocha, “OBB Tree: A Hierarchical Structure for Rapid Inference Detection”, In Proc. Of ACM Siggraph ’96,pages 171‐180,1996）がある。）。
【００６４】
例えば図８（ａ）に示すような接触状態の組立品がある場合、図８（ｂ）に示すようなグラフで隣接する部品の情報を表現することができる。
【００６５】
ステップＳ４では、探索する経路の始・終点を上述のように設定する。始・終点は、三角形メッシュの頂点が選ばれるものとするが、コンピュータの操作者が入力装置６を用いてメッシュの頂点以外を選んだ場合は、図９に示すように、指定した位置に新たに点を生成し、その点を含む三角形パッチをその点が三角形パッチの頂点となるように分割することにより、その点をメッシュの頂点とすることができる。
【００６６】
ステップＳ５では、探索するための空の重み付きグラフ、優先順位付きキューで実装した空の探索ノードキューを生成する。その後、始点に対応する重み付きグラフのノードを生成し、重み付きグラフへの登録、探索ノードキューへの登録を行う。その後、始点を含む部品を取り出して近接点処理を行う。近接点処理は経路探索処理のところで詳細に説明する。ここで、各頂点データには各頂点を含む部品のＩＤが登録されており、頂点を指定すればそれを含む部品データが取り出せるものとする。
【００６７】
ステップＳ６では、ステップＳ５までの初期処理が済んだ後、実際の経路探索処理を実行する。この処理の詳細については後で詳細に説明する。
【００６８】
ステップＳ７では、ステップＳ６における経路探索処理の結果、最短経路が見つかったかをチエックする。もし最短経路が見つかった場合は、ステップＳ８で重み付きグラフの経路探索の結果を使って始点から終点までの経路を取得し、表示装置８ａの表示画面上にこの経路を画像や文字などでもって表示したり、取得した経路を示すデータを外部記憶装置１０に保存したりする。
【００６９】
一方、最短経路が探索できなかった場合は、ステップＳ９で最短経路が発見できなかったとして、表示装置８ａの表示画面上にその旨を画像や文字などでもって表示したり、その旨を示すデータを外部記憶装置１０に保存したりする。
【００７０】
ここで、最短経路が発見できない場合は、装置の不具合の他、指定した始点と終点を含む部品どうしが部品の接続関係を利用してたどれない場合などがある。図８（ａ）に示したグラフを例に取ると、グラフが二つ以上に分離されているケースである。
【００７１】
ステップＳ８における最短経路の取得処理は、後述するように重み付きグラフを使って最短経路を探索していくとき、探索された各ノードにそのノードに到達する直前に到達している探索ノードを保存しているので、終点から経路の逆順に保存されたノードを取り出せば、終点から始点までの逆順の探索経路を得ることができる。この得られた結果を反転することで始点から終点までの最短経路を得ることができる。
【００７２】
次に、図２に示した各ステップにおける処理についてより詳細に説明する。
【００７３】
ステップＳ６０１では、探索ノードキューが空かどうかをチエックする。終点ノードが見つかる前に探索ノードが空になるのは経路が存在しないときであるから、もし空の場合は経路が存在しないという情報を処理の終了情報として返し、ステップＳ６の処理を終了する。
【００７４】
ステップＳ６０２では、探索ノードキューから探索ノードを一つ取り出し着目探索ノードとする。ここで探索ノードキューは優先順位付きキューで実現されており、常にキューの中の評価値が一番小さいノードが最初に得られるものとする。ここで評価値として視点から、このノードまでの距離とするとダイクストラ法となり、始点からこのノードまでの距離に加えて、このノードから終点までの距離を見積もるヒューリステイック関数の値を加えたものとするのがＡ＊である。
【００７５】
Ａ＊は、確実に最短経路を見つけるためにヒューリステイック関数は、実際のノードから終点までの経路より大きくない値を返すという条件を満たす必要がある。本実施形態では、このヒューリステイック関数として、そのノードから終点までの三次元的な最短距離を与えている。明らかに２つのノード間の三次元的な最短距離は、２つのノード間の沿面距離よりも大きくなることはないので、このヒューリステイック関数はＡ＊が求める条件をみたしている。
【００７６】
図１０において、Ａ，Ｂが探索ノードキューにはいっているとする。このときＡのダイクストラ法による評価値はＡまでの最短経路値で８、Ａ＊による評価値はノードＡと終点との間のユークリッド距離５を足して１３になる。同様にＢのダイクストラ法による評価値はＡまでの最短経路値で９、Ａ＊による評価値はユークリッド距離２を足して１１である。よって、図１０の場合ダイクストラ法によればノードＡがキューから最初に取り出され、Ａ＊によればノードＢがキューから最初に取り出される。
【００７７】
ステップＳ６０３では、ステップＳ６０２で取り出した着目探索ノードが終点であるかどうかを判定する。終点であればこれで探索は終了となるので、探索が終了したということを終了情報として返し、ステップＳ６の処理を終了する。
【００７８】
ステップＳ６０４では、着目探索ノードが境界ノードであるかどうか判定する。上述したように境界ノードとは、近接点または他部品に近接点を持つノードである。他部品と許容誤差以内で接触しているとき接触部分付近にあるノードである。図１１の場合、ある部品１１０１上のあるパッチに部品１１０２のあるパッチが近接しており、部品１１０１上のパッチの稜線上における内挿点Ａに部品１１０２のあるパッチ上の近接点Ｂが定義されているものとする。このときノードＡ，Ｂが境界ノードとなる。
【００７９】
ステップＳ６０５ではステップＳ６０４で着目探索ノードが境界ノードであるとき、その境界ノードに隣接する他部品に近接点処理がされているかどうかを判定する。近接点処理の詳細についてはステップＳ６０６の説明のところで詳細に説明する。ここで、この判定を行うために近接点処理をしたかどうかを判定するためのフラグ、近接点処理フラグを使用する。経路探索の処理が始まるときにこの処理は未処理のフラグが立っておりステップＳ６０６で近接点処理が行われると処理済みというフラグが立てられるものとする。よってステップＳ６０５ではこの近接点処理フラグを見てその内容を返すものとする。
【００８０】
ステップＳ６０６では、ステップＳ６０５で取り出された隣接部品上に近接点処理を行う。近接点処理は、所定の部品に隣接する各部品上に作成される重み付きグラフの各ノードの所定の部品上での近接点を求める処理である。ここで近接点というのは、指定した点から所定の部品への最短距離をとるときのその所定の部品上の点のうち、指定した許容誤差以内の距離にあるものである。図１１の場合の内挿点Ａに対してＢを求める処理が近接点処理になる。
【００８１】
求められた近接点は、近接点の存在する三角形パッチに登録される。ここで近接点処理を行うとき、隣接した部品に重み付きグラフが作成されているとは限らない。後述するように、重み付きグラフのノードになる点は、メッシュの頂点、稜線上の内挿点およびこの近接点であるが、近接点を持ち得る頂点および稜線は、部品が接触する付近にある、限られた領域にあるものなので、前述した包含図形のツリーなどを用いてあらかじめ他の部品に近接点を持ち得る頂点および稜線を効率よく求めておくことによって、この頂点、稜線上の内挿点に対応するグラフのノードのみを作成して、そのノードに対応する近接点のみを考えればよい。
【００８２】
ステップＳ６０７では、着目探索ノードに隣接する隣接パッチを取り出す。ここで隣接パッチには大きくわけて二つある。一つは、着目探索ノードの同一部品上でそのノードに対応する頂点もしくは内挿点を境界に持つ三角形パッチである。もう一つは、着目探索ノードが境界ノードであるとき、そのノードが近接点に対応するときはその近接点を持つ他部品上のノードを境界に持つ他部品上の三角形パッチである。例えば図１２（ａ）は、着目探索ノードが頂点の場合で、Ｔ１，Ｔ２，Ｔ３が隣接パッチとなる。図１２（ｂ）の場合は、着目探索ノードが内挿点の場合でＴ１，Ｔ２が探索パッチとなる。図１２（ｃ）の場合は、着目探索ノードが境界ノードのときで、着目探索ノードが内挿点の場合はＴ２が、着目探索ノードが近接点の場合はＴ１が隣接パッチに加わる。
【００８３】
ステップＳ６０８では、ステップＳ６０７で取り出された隣接パッチに対して重み付きグラフのノード、アークを作成して重み付きグラフに登録する。ここで既にノード、アークが作成されている場合はこの処理を行う。二重の処理を行わないようにするため、各三角形パッチにグラフエントリ作成フラグを持たせ、最初未作成に初期化しておく。ノード・アークが作成した後は作成済みのフラグを立てる。
【００８４】
ここで、ノードとなるのは各頂点、各稜線の内挿点、近接点である。各頂点はいくつかのパッチに共有されているので、パッチと同様に処理フラグをも持たせて二重に作成処理が行われないようにする。稜線も二つのパッチに共有されているので同様に処理フラグを持たせて二重に処理が行われないようにする。また、ステップＳ６０６の説明における近接点処理によりすでに頂点、稜線に対する内挿点が作成されているときも二重の作成処理を防ぐことができる。
【００８５】
稜線の内挿入点はシュタイナー点を呼ばれ、たとえば、一定の間隔で稜線に挿入される。この間隔は例えば組立品全部を包含する矩形を求めその対角線に対応する一定の比で求めることができる。間隔を小さくするほど詳細なグラフが作成でき、経路の近似度も上がるがその分処理の時間が遅くなる。
【００８６】
近接点は、ステップＳ６０６の処理で求められているもので、上記で説明したように各パッチに登録されている。またグラフのアークとしては、図１３に示す如く、パッチの各稜線で隣あうノードを結んだ稜線エッジ、パッチ上で同一稜線にない２つの頂点またはシュタイナー点を結んだ面上エッジ、近接点とすべての頂点およびシュタイナー点を結んだ近接点エッジの３種類がある。またアークの重みは両端のノード間のユークリッド距離であるとする。
【００８７】
ステップＳ６０９では、着目探索ノードが境界ノードであるとき、着目探索ノードと近接部品上の近接ノードを結ぶブリッジアークを作成して重み付きグラフに登録する。着目探索ノードが頂点またはシュタイナー点のときは対応する他部品上の近接点と、着目ノードが近接点のときは対応する他部品上の頂点またはシュタイナー点とを結ぶアークとする。アークの重みはステップＳ６０８と同様に両端のノード間のユークリッド距離であるとする。図１４の場合、着目探索ノードが部品Ａの内挿点であるとき同図のように部品Ｂ上の近接点とを両端点とするアークをブリッジアークとして重み付きグラフに登録する。着目探索ノードが部品Ｂの近接点であるときも同様にブリッジアークを登録する。
【００８８】
ステップＳ６１０では、着目探索ノードを起点として経路の探索を行い探索ノードキューの更新を行う。ステップＳ６０９までの処理で、着目探索ノードから探索すべきノードはすべて作成されているので、着目探索ノードからアークを介して隣接するノードのうちまだ未探索のものおよび、既に探索されているが着目探索ノードを通る経路の方が既に探索されたそのノードまでの経路よりも短くなるものを探索ノードキューにいれる。図１５の場合、着目探索ノードに結合されているノードＢ，Ｃはまだ未探索なのでキューにいれられる。ノードＡの場合、ノードＤを通る経路で既にキューに登録されている可能性があるが、着目ノードを通る経路の方が短いので後述する、前ノードと距離を更新してキューに再びいれる。同時にそのノードに前ノードとして着目探索ノードと、そのノードまでの距離を登録しておく。この前ノードが登録されているかどうかで、このノードが未探索かどうかわかる。そのノードまでの距離は着目探索ノードまでの距離に加えてそのノードまでのアークの長さを足すことにより求められる。以上の処理が終わったら再びステップＳ６０１からの処理を繰り返す。
【００８９】
なお、以上の処理は一回で終わらせるのではなく、一度求めた経路の付近にさらに詳細なグラフを作成しグラフを探索することによってさらに精度のよい解を得る。この処理を経路の長さの改善値が与えられた閾値より小さくなるまで繰り返すことにより、十分に精度のよい解を得られることができる。
【００９０】
例えば図１６は、立方体上の沿面の経路に対してこのような方法で精度よく解を求める前と後を示す図である。図１６（ａ）は初期の探索グラフを作成して最短経路を探索する様子を示す図である。図１６（ｂ）はこのようにして求めた最短経路の付近にさらに詳細な探索グラフを作成して、再び最短経路を探索した様子を示す図である。
【００９１】
詳細化した新規探索グラフは以下のように行われる。まず、前段階で求めた最短経路を通過するノードのうち近接点でないものを新しい新規グラフに登録する。次に最短経路が通過するノードと同一稜線上にある隣接ノードを新規グラフに登録する。次に、前述した最短経路が通過するノードとそれに隣接する同一稜線上のノードの間の稜線上に所定の個数のノードを挿入して新規グラフに登録する。その後、既に新規グラフに登録しているノードの近接点を求めてそれを新規グラフに登録する。そして、ステップＳ６０６と同様の方法でアークを作成して新規登録に登録する。
【００９２】
図１７の例では太線が左図のグラフに対して得られた最短経路であるがグレーのノードが太線の通過するノード、黒のノードが太線の通過するノードの隣接ノード、白いノードが新たに挿入されたノードである。ここでは、旧グラフのノード間に一つのノードを追加している。
【００９３】
以上の説明により、本実施形態によって、組立品表面に沿った沿面の最短経路を探索に必要なところのみのグラフを作っていくことによってグラフ作成処理にかかる時間や記憶容量などのコストを削減できて効率よく解を求めることができる。尚、部品境界上の着目探索ノードに関する処理や近接点処理、着目探索ノードと他部品上の近接点とのブリッジアークの作成処理など組立品固有の処理を除けば、単一部品上での沿面経路を求める処理として、グラフ作成処理にかかるコストを削減した効率のより沿面経路探索を求めることにも本発明は適用可能である。
【００９４】
また、本発明の効果については以下の通りである。
【００９５】
最短経路が通過する部分領域にのみ探索のための重み付きグラフをつくればよいので、グラフを作成する時間、必要とする記憶量を大幅に減少させることができるという効果を持つ。
【００９６】
また、実行時間と記憶容量の大半を使用する詳細な初期グラフを作ることなく精度のよい解を得ることができるので、同様な解の精度を得るために実行時間および記憶容量を大幅に減らせるという効果を持つ。
【００９７】
また、三角形メッシュで表現された部品形状に対する近似的な沿面経路を探索するときに、沿面経路が通過する三角形パッチ上のみに重み付きグラフを作成しながら探索することにより、グラフを作成する時間、必要とする記憶量を大幅に減少させるという効果を持つ。
【００９８】
また、モデルのサイズに応じて適当な解の精度を得られるようエッジに対する内挿点を作成できるという効果を持つ。
【００９９】
また、三角形メッシュを構成する頂点、エッジ、三角形パッチに対する重み付きグラフのノード、アークの作成処理を二重に行わず、しかも各パッチごとに処理を行えばよいので簡潔に処理が行えるというという効果を持つ。
【０１００】
また、各三角形パッチの頂点およびエッジの内挿点から、パッチの経路モデルを妥当に離散化して近似する重み付きグラフが作成されるという効果を持つ。
【０１０１】
また、三角形メッシュに対して、実行時間と記憶容量の大半を使用する詳細な初期グラフを作ることなく精度のよい沿面経路を得ることができるので、同様な解の精度を得るために実行時間および記憶容量を大幅に減らせるという効果を持つ。
【０１０２】
また、三角形メッシュに対して、より精度のよい沿面経路を求めるための重み付きグラフの更新を簡単に行え、実行時間と記憶容量の大半を使用する詳細な初期グラフを作ることなく精度のよい沿面経路を得ることができるので、同様な解の精度を得るために実行時間および記憶容量を大幅に減らせるという効果を持つ。
【０１０３】
また、多面体で表現された形状に対する沿面経路問題を三角形メッシュに対する沿面経路問題に帰着させることができるという効果を持つ。
【０１０４】
また、曲面で表現された形状に対する沿面経路問題を三角形メッシュに対する沿面経路問題に帰着させることができるという効果を持つ。
【０１０５】
また、三角形メッシュに対し、重み付きグラフを探索する手法としてダイクストラ法を使うことにより、実装が容易で比較的効率のよい探索を確実に行うことができるという効果を持つ。
【０１０６】
また、三角形メッシュに対し、重み付きグラフを探索する手法として３次元上の２点間の距離をヒューリステイック関数とするＡ＊を使うことにより大抵の場合に非常に効率のよい探索を行うことができるという効果を持つ。
【０１０７】
また、三角形メッシュで表現される部品形状よりなる組立品に対する近似的な沿面経路を探索するときに、沿面経路が通過する三角形パッチ上のみに重み付きグラフを作成しながら探索することにより、グラフを作成する時間、必要とする記憶量を大幅に減少させるという効果を持つ。
【０１０８】
また、三角形メッシュで表現される部品形状よりなる組立品に対する近似的な沿面経路を探索するときに、沿面経路が通過する三角形パッチ上のみに重み付きグラフを作成しながら探索することにより、グラフを作成する時間、必要とする記憶量を大幅に減少させるという処理を簡潔に実装できるという効果を持つ。
【０１０９】
また、三角形メッシュで表現される部品形状よりなる組立品に対する近似的な沿面経路を探索する処理において、モデルのサイズに応じて適当な解の精度を得られるようエッジに対する内挿点を作成できるという効果を持つ。
【０１１０】
また、三角形メッシュで表現される部品形状よりなる組立品に対する近似的な沿面経路を探索する処理において、三角形メッシュを構成する頂点、エッジ、三角形パッチに対する重み付きグラフのノード、アークの作成処理を二重に行わず、しかも各パッチごとに処理を行えばよいので簡潔に処理が行えるというという効果を持つ。
【０１１１】
また、三角形メッシュで表現される部品形状よりなる組立品に対する近似的な沿面経路を探索する処理において、各三角形パッチの頂点およびエッジの内挿点から、パッチの経路モデルを妥当に離散化して近似する重み付きグラフが作成されるという効果を持つ。
【０１１２】
また、三角形メッシュで表現される部品形状よりなる組立品に対する近似的な沿面経路を探索する処理において、各部品形状に対する近接点作成処理を二重に行わず、しかも各部品ごとに処理を行えばよいので簡潔に処理が行えるというという効果を持つ。
【０１１３】
また、三角形メッシュで表現される部品形状よりなる組立品に対する近似的な沿面経路を探索する処理において、実行時間と記憶容量の大半を使用する詳細な初期グラフを作ることなく精度のよい沿面経路を得ることができるので、同様な解の精度を得るために実行時間および記憶容量を大幅に減らせるという効果を持つ。
【０１１４】
また、三角形メッシュで表現される部品形状よりなる組立品に対する近似的な沿面経路を探索する処理において、より精度のよい沿面経路を求めるための重み付きグラフの更新を簡単に行え、実行時間と記憶容量の大半を使用する詳細な初期グラフを作ることなく精度のよい沿面経路を得ることができるので、同様な解の精度を得るために実行時間および記憶容量を大幅に減らせるという効果を持つ。
【０１１５】
また、多面体で表現される部品形状よりなる組立品に対する沿面経路を探索問題を、三角形メッシュで表現される部品形状よりなる組立品に対する沿面経路問題に帰着させることができるという効果を持つ。
【０１１６】
また、曲面で表現される部品形状よりなる組立品に対する沿面経路を探索問題を、三角形メッシュで表現される部品形状よりなる組立品に対する沿面経路問題に帰着させることができるという効果を持つ。
【０１１７】
また、三角形メッシュで表現される部品形状よりなる組立品に対する近似的な沿面経路を探索する処理において、重み付きグラフを探索する手法としてダイクストラ法を使うことにより、実装が容易で比較的効率のよい探索を確実に行うことができるという効果を持つ。
【０１１８】
また、三角形メッシュで表現される部品形状よりなる組立品に対する近似的な沿面経路を探索する処理において、重み付きグラフを探索する手法として３次元上の２点間の距離をヒューリステイック関数とするＡ＊を使うことにより大抵の場合に非常に効率のよい探索を行うことができるという効果を持つ。
【０１１９】
また、本発明の目的は、前述した実施形態の機能を実現するソフトウェアのプログラムコードを記録した記録媒体（または記憶媒体）を、システムあるいは装置に供給し、そのシステムあるいは装置のコンピュータ（またはＣＰＵやＭＰＵ）が記録媒体に格納されたプログラムコードを読み出し実行することによっても、達成されることは言うまでもない。この場合、記録媒体から読み出されたプログラムコード自体が前述した実施形態の機能を実現することになり、そのプログラムコードを記録した記録媒体は本発明を構成することになる。
【０１２０】
また、コンピュータが読み出したプログラムコードを実行することにより、前述した実施形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼働しているオペレーティングシステム（ＯＳ）などが実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【０１２１】
さらに、記録媒体から読み出されたプログラムコードが、コンピュータに挿入された機能拡張カードやコンピュータに接続された機能拡張ユニットに備わるメモリに書込まれた後、そのプログラムコードの指示に基づき、その機能拡張カードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【０１２２】
本発明を上記記録媒体に適用する場合、その記録媒体には、先に説明したフローチャートに対応するプログラムコードが格納されることになる。
【図面の簡単な説明】
【０１２３】
【図１】本発明の実施形態に係るグラフの最短経路探索手法を用いて、図４に示すような組立品上の表面を通る最短経路４００、いわゆる沿面距離を通る経路（沿面経路）を探索する処理のフローチャートである。
【図２】ステップＳ６における処理の詳細を示すフローチャートである。
【図３】本発明の実施形態に係るグラフの最短経路探索手法を用いて、図４に示すような組立品上の表面を通る最短経路４００、いわゆる沿面距離を通る経路（沿面経路）を探索する処理を実行するコンピュータの基本構成を示すブロック図である。
【図４】組立品の例を示す図である。
【図５】曲面モデル、及びこの曲面モデルを近似した多面体モデルを示す図である。
【図６】４つの三角形メッシュとこれらを構成する頂点との関係を示す図である。
【図７】同一の幾何データを持つ頂点を同一点として認識して、次に、同一の二点を端点とする各辺を共有辺として隣合う三角形パッチを認識するなどの位相認識処理を説明する図である。
【図８】接触状態の組立品、及びこの組立品に対するグラフを示す図である。
【図９】指定した位置に新たに点を生成し、その点を含む三角形パッチをその点が三角形パッチの頂点となるように分割することにより、その点をメッシュの頂点とする処理を説明する図である。
【図１０】ステップＳ６０２における処理を説明する図である。
【図１１】境界ノードを説明する図である。
【図１２】隣接パッチを説明する図である。
【図１３】グラフのアークを説明亜する図である。
【図１４】ステップＳ６０９における処理を説明する図である。
【図１５】ステップＳ６１０における処理を説明する図である。
【図１６】（ａ）は初期の探索グラフを作成して最短経路を探索する様子を示す図、（ｂ）は最短経路の付近にさらに詳細な探索グラフを作成して、再び最短経路を探索した様子を示す図である。
【図１７】新たに追加、挿入されるノードを説明する図である。
【図１８】立方体上の面に沿った最短距離をグラフを使って求める例を示す図である。
【図１】
2006172318.tif 000003
【図２】
2006172318.tif 000004
【図３】
2006172318.tif 000005
【図４】
2006172318.tif 000006
【図５】
2006172318.tif 000007
【図６】
2006172318.tif 000008
【図７】
2006172318.tif 000009
【図８】
2006172318.tif 000010
【図９】
2006172318.tif 000011
【図１０】
2006172318.tif 000012
【図１１】
2006172318.tif 000013
【図１２】
2006172318.tif 000014
【図１３】
2006172318.tif 000015
【図１４】
2006172318.tif 000016
【図１５】
2006172318.tif 000017
【図１６】
2006172318.tif 000018
【図１７】
2006172318.tif 000019
【図１８】
2006172318.tif 000020