(57)【要約】【課題】より高精度の沿面距離をより短時間で求めることができる沿面距離算出装置、沿面距離算出方法及びプログラムを提供する。【解決手段】ステップＳ４〜Ｓ７において、ステップＳ３で求めた初期経路の部分的な改善を繰り返し、より短い経路を探索的に求めていく。例えば、ステップＳ４及びＳ５では、部分経路の局所的な展開面を利用することによって、その部分経路の始点及び終点を繋ぐ厳密な最短経路を求め、部分経路をその最短経路で置き換えていくことによって、より短い経路を求めていく。この結果、各部品上の経路を次第に短いものとすることができる。また、ステップＳ６は複数の部品からなる組立品に対して必要なステップであり、組立品に対する探索経路のうち、各部品上の経路を繋ぐ部分の部分経路をより短縮していくことによって、より短い経路を算出する。【選択図】図４
2008134948.tif 000002
【特許請求の範囲】
【請求項１】
対象物の表面上の固定通過点及び制御点を受け付ける受付手段と、
前記対象物の三角形メッシュモデルに対し、前記制御点を参照しながら前記固定通過点を通る単一の初期経路を求める初期経路探索手段と、
前記固定通過点同士を結ぶ経路のうちで、前記初期経路よりも短い経路を求める短縮経路探索手段と、
前記短縮経路探索手段により求められた経路が収束しているかを判定する判定手段と、
を有することを特徴とする沿面経路探索装置。
【請求項２】
前記対象物が複数の部品から構成されている場合に、
前記初期経路探索手段は、前記複数の部品間のレイアウト情報も参照しながら、前記初期経路を求め、
前記短縮経路探索手段は、前記レイアウト情報も参照しながら、前記初期経路よりも短い経路を求めることを特徴とする請求項１に記載の沿面経路探索装置。
【請求項３】
前記判定手段は、前記短縮経路探索手段により求められた経路を、その直近に得られた経路と比較し、その短くなった量又は割合が、予め定められた値以下となった場合に経路が収束したと判定することを特徴とする請求項１又は２に記載の沿面経路探索装置。
【請求項４】
前記三角形メッシュモデルの既頂点以外の点が前記固定通過点又は制御点として指定された場合に、当該固定通過点又は制御点を頂点とする三角形メッシュモデルを作成するモデル作成手段を有することを特徴とする請求項１乃至３のいずれか１項に記載の沿面経路探索装置。
【請求項５】
前記判定手段により経路が収束したと判定された後に、当該経路の承認を使用者に求める承認手段を有することを特徴とする請求項１乃至４のいずれか１項に記載の沿面経路探索装置。
【請求項６】
前記受付手段は、前記固定通過点及び制御点の並び順も受け付けることを特徴とする請求項１乃至５のいずれか１項に記載の沿面経路探索装置。
【請求項７】
初期経路探索手段は、
前記三角形メッシュモデル上の経路モデルを近似する重み付きグラフを作成し、
前記固定通過点及び制御点のうちから、その並び順に２点を抽出し、最初の点を始点とし、次の点を終点として、前記重み付きグラフ上での最短経路を探索し、
前記最短経路を、前記固定通過点及び制御点のすべてについて、合成して前記初期経路とすることを特徴とする請求項６に記載の沿面経路探索装置。
【請求項８】
前記短縮経路探索手段は、
直近に求められた経路の各通過点に対して近接する三角形メッシュモデルの頂点を求め、
前記頂点が存在すると共に、当該頂点が固定通過点でない場合に、当該頂点回りの局所的な最短経路を求め、
前記直近に求められた経路の当該頂点回りの経路を、前記局所的な最短経路で置き換えることを特徴とする請求項１乃至７のいずれか１項に記載の沿面経路探索装置。
【請求項９】
前記短縮経路探索手段は、
直近に求められた経路が通過する三角形メッシュモデル上の複合稜線列を取得し、
前記複合稜線列を複数の単純稜線列に分解し、
前記単純稜線列の各々を横切る経路のうちで最短の経路を単位最短経路として求め、
前記単位最短経路を結合して前記複合稜線列に対する最短経路を求めることを特徴とする請求項１乃至８のいずれか１項に記載の沿面経路探索装置。
【請求項１０】
前記短縮経路探索手段は、
前記複数の部品間を結ぶ部品間接続アークの端点となる２個のノードのうち三角形メッシュモデルの稜線上にあるノードを着目ノードと定義し、
前記２個のノードのうちの他方を面内ノードと定義し、
直近に求められた経路上で前記着目ノードと隣り合う２個のノードのうちで前記面内ノードとは異なるものを前通過ノードと定義し、
前記直近に求められた経路上で前記面内ノードと隣り合う２個のノードのうちで前記着目ノードとは異なるものを次通過ノードと定義し、
前記着目ノードとそれが位置する三角形メッシュモデル内のいずれかの頂点との距離が予め定められた距離以上である場合に、前記着目ノードが位置する稜線を着目稜線と定義し、前記着目ノードと前記いずれかの頂点との距離が予め定められた距離未満である場合に、前記着目ノード及び前記前通過ノードが位置する三角形メッシュモデル内の稜線であって、前記前通過ノードが位置していない２つの稜線を着目稜線と定義し、
前記着目稜線上の任意の第１の点と前記前通過ノードとの距離をＬ１とし、
前記第１の点と前記第１の点から前記次通過ノードの存在する三角形メッシュモデルに対して最短距離をとったときの最短線の足を第２の点との距離をＬ２とし、
前記第２の点と前記次通過ノードとの距離をＬ３としたときに、
距離の和「Ｌ１＋Ｌ２＋Ｌ３」が最短となる第１の点を求め、
前記着目ノードを前記第１の点に変更し、
前記面内ノードを前記第２の点に変更することを特徴とする請求項２乃至９のいずれか１項に記載の沿面経路探索装置。
【請求項１１】
前記三角形メッシュモデル上の頂点を前記固定通過点又は制御点として使用者に指定させる第１の手段、
前記三角形メッシュモデル上の稜線及び当該稜線上の内分パラメータを特定させることにより、前記固定通過点又は制御点を使用者に指定させる第２の手段、
前記三角形メッシュモデル上の三角形パッチ及び当該三角形パッチにおける重心座標を特定させることにより、前記固定通過点又は制御点として使用者に指定させる第３の手段と、
既に指定された固定通過点又は制御点の前後に他の固定通過点又は制御点を使用者に挿入させる第４の手段と、
既に指定された固定通過点又は制御点を使用者に削除させる第５の手段と、
既に指定された固定通過点又は制御点の位置を使用者に変更させる第６の手段と、
からなる群から選択された少なくとも１種の手段を有することを特徴とする請求項１乃至１０のいずれか１項に記載の沿面経路探索装置。
【請求項１２】
前記短縮経路探索手段により求められた経路及びそれまでに求められている経路を、これらの経路に対応する固定通過点及び制御点と共に表示する手段を有することを特徴とする請求項１乃至１１のいずれか１項に記載の沿面経路探索装置。
【請求項１３】
前記短縮経路探索手段により求められた経路及びそれまでに求められている経路を、これらの長さと共に表示する手段を有することを特徴とする請求項１乃至１２のいずれか１項に記載の沿面経路探索装置。
【請求項１４】
対象物の表面上の固定通過点及び制御点を受け付ける受付ステップと、
前記対象物の三角形メッシュモデルに対し、前記制御点を参照しながら前記固定通過点を通る単一の初期経路を求める初期経路探索ステップと、
前記固定通過点同士を結ぶ経路のうちで、前記初期経路よりも短い経路を求める短縮経路探索ステップと、
前記短縮経路探索ステップにおいて求めた経路が収束しているかを判定する判定ステップと、
を有することを特徴とする沿面経路探索方法。
【請求項１５】
コンピュータに、対象物の表面上の沿面経路を探索させるためのプログラムであって、
前記コンピュータに、
前記対象物の表面上の固定通過点及び制御点を受け付ける受付手順と、
前記対象物の三角形メッシュモデルに対し、前記制御点を参照しながら前記固定通過点を通る単一の初期経路を求める初期経路探索手順と、
前記固定通過点同士を結ぶ経路のうちで、前記初期経路よりも短い経路を求める短縮経路探索手順と、
前記短縮経路探索ステップにおいて求めた経路が収束しているかを判定する判定手順と、
を実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＣＧ、ＣＡＤ／ＣＡＭ等の計算機を使って形状情報を処理する情報処理プログラムの作成に好適な沿面経路探索装置、沿面経路探索方法及びプログラムに関する。
【背景技術】
【０００２】
製品設計の過程で、製品表面に沿った二点間の最短距離（沿面距離と呼ばれる）を算出することがしばしば必要となる。そのような処理が必要な具体的な例として、製品の絶縁検証がある。絶縁検証とは製品上の各電気回路間に規格で定められた十分な絶縁距離が確保されているかを検証する作業のことである。この検証を行うためには製品表面に沿った部品間の最短距離、つまり沿面距離を算出する必要がある。
【０００３】
従来の製品設計において沿面距離を算出する方法の一つとして、実際に作成する製品と同じ形状を持った試作機を作り、試作機上で沿面経路と思われる経路を人間が判断して、その長さを測定することが行われている。この方法では、沿面経路と思われる経路を連続する複数の線分列に近似して、ノギス等の計測器具を使い、各線分の距離を測定し、その和を求めている。
【０００４】
また、計算機を使って、多面体上の沿面経路を求めるアルゴリズムについて、計算幾何学の分野で数多くの研究がなされている。そのような沿面経路を求めるアルゴリズムには厳密な解を求めるものと近似的な解を求めるものがある。しかし、厳密な解を求めるアルゴリズムでは、複雑度が高い製品形状に対しては、現実的な時間で沿面経路を求めることは不可能な場合が多い。
【０００５】
一方、現実的な時間で近似解を求める方法としては、以下のようなものがある。
【０００６】
第１の方法は、多面体表面に沿った経路モデルを離散的な重み付きグラフを使って近似的に表現し、その最短経路を求めることにより近似的な沿面経路を求める方法である。経路の精度を上げるために、前の段階で求めた重み付きグラフの最短経路の近辺により詳細なグラフを作って、そのグラフの沿面経路を求め直すという処理を、経路の改善値が指定した閾値以下になるまで繰り返すという方法である。この方法によれば、近似的な沿面距離が求められる。
【０００７】
第２の方法は、経路を近似した重み付きグラフの探索により初期の沿面経路を求める方法の一つであり、経路が通過する連続した三角形パッチ内の最短経路を求めることにより経路の精度を上げる方法である。
【０００８】
第３の方法は、初期の沿面経路を求めた後、経路の精度を向上するために、探索経路と多面体の稜線又は頂点が交差する通過点毎の局所的な展開面を利用する方法である。具体的には、通過点が存在する三角形パッチを局所的に２次元上に展開して、この局所的な展開面上でのショートカットを求めて、元の経路の展開面上の部分経路を置き換えることにより、より短い沿面経路を求めている。この処理を各通過点で繰り返し行うことにより、上記の方法では見付けることのできない、より経路長の小さい沿面経路を見付けることができる。
【０００９】
第４の方法は、離散化した重み付きグラフの探索と、局所的な展開面を利用した最適化を利用して沿面経路を探索する方法である。但し、複数部品からなる組立品の沿面経路を求めることができるよう、近接した各部品上の重み付きグラフを結合した探索グラフを作成することにより、組立品の沿面経路を探索している（特許文献１参照）。
【００１０】
また、第３及び第４の方法では、初期経路を求めるグラフ探索において、最短の経路でなく短い順に上位いくつかの経路を求めて、それらの経路すべてを探索の初期経路として使うことにより、より経路長の短い沿面経路を見付けている。
【００１１】
【特許文献１】特開２００５−１０８３５号公報
【発明の開示】
【発明が解決しようとする課題】
【００１２】
しかしながら、試作機を作成して人間が沿面距離を測る方法では、試作機を作るために費用及び時間がかかり、また、測定する手間がかかる。更に、ノギス等の計測装置では直線の距離しか測れないので、連続する空間的な曲線となる物体表面の経路を測定することが困難であり、複雑な３次元形状に対して人間が沿面経路を推定することも困難である。
【００１３】
これに対し、上述の従来の方法では、試作機を作らなくても計算機上で沿面距離を計算できるので、試作機を作る手間及び費用、測定する手間及び費用を省くことができる。但し、第１及び第２の方法では、探索の初期経路を得るために、部品形状の表面に部品表面の経路モデルを近似する重み付きグラフを作成する。このとき、重み付きグラフのノードとして、部品表面上の点をサンプリングしたものを使用するが、このサンプリングした点間の距離が大きく、重み付きグラフが粗い場合、その重み付きグラフに対する最短経路は、本来の沿面距離から大きく離れたものになる。この結果、その最短経路を探索の初期経路として、経路を改善していっても十分精度の高い経路を得にくい。図３３に、最初の重み付きグラフの密度が低いため、精度の高い沿面経路が得られなかった例を示す。この場合、最初の重み付きグラフが、入力された部品形状を表現する三角形メッシュモデルと同じ形で作成されている。しかし、これでは重み付きグラフの密度が粗すぎて、最初の探索経路が真の沿面経路と離れすぎているため、最終的に得られた精度の低い経路が得られることになる。
【００１４】
また、第１〜第３の方法では、単体の部品上の沿面距離しか算出することができず、絶縁検証等で必要な組立品上の部品を跨るような沿面距離を求めることはできない。
【００１５】
また、第３及び第４の方法では、沿面距離経路の探索の初期経路として、物体表面上に作成した重み付きグラフに対する最短の経路だけでなく、指定した本数の複数の最短経路を探索の初期経路として使用している。これにより、真の沿面経路に近い経路である経路が見付かる可能性が向上している。しかし、このような方法で、解の精度を上げるために、初期経路の数を多くとると、計算時間が非常に長くなってしまい、現実的な時間で精度のよい解が求められないことがある。
【００１６】
本発明の目的は、より高精度の沿面距離をより短時間で求めることができる沿面距離算出装置、沿面距離算出方法及びプログラムを提供することにある。
【課題を解決するための手段】
【００１７】
本願発明者は、前記課題を解決すべく鋭意検討を重ねた結果、以下に示す発明の諸態様に想到した。
【００１８】
本発明に係る沿面経路探索装置は、対象物の表面上の固定通過点及び制御点を受け付ける受付手段と、前記対象物の三角形メッシュモデルに対し、前記制御点を参照しながら前記固定通過点を通る単一の初期経路を求める初期経路探索手段と、前記固定通過点同士を結ぶ経路のうちで、前記初期経路よりも短い経路を求める短縮経路探索手段と、前記短縮経路探索手段により求められた経路が収束しているかを判定する判定手段と、を有することを特徴とする。
【００１９】
本発明に係る沿面経路探索方法は、対象物の表面上の固定通過点及び制御点を受け付ける受付ステップと、前記対象物の三角形メッシュモデルに対し、前記制御点を参照しながら前記固定通過点を通る単一の初期経路を求める初期経路探索ステップと、前記固定通過点同士を結ぶ経路のうちで、前記初期経路よりも短い経路を求める短縮経路探索ステップと、前記短縮経路探索ステップにおいて求めた経路が収束しているかを判定する判定ステップと、を有することを特徴とする。
【発明の効果】
【００２０】
本発明によれば、人間が試作機を作ってノギス等で測るのに比べ、安い費用で、より精度よく、より速く沿面距離を算出することができる。また、計算機を使って従来の手法で算出するのに比べ、より経路長の短い沿面経路を高速に算出することができる。
【発明を実施するための最良の形態】
【００２１】
以下、本発明の実施形態について添付の図面を参照して具体的に説明する。
【００２２】
（第１の実施形態）
先ず、本発明の第１の実施形態について説明する。図１は、本発明の第１の実施形態に係る沿面距離算出装置を示すブロック図である。
【００２３】
図１に示すように、この沿面距離算出装置では、ＣＰＵ（中央演算装置）２、ＲＯＭ３、ＲＡＭ４、入力インタフェース５、出力インタフェース７及び外部記憶装置インタフェース８がデータバス１を介して互いに接続されている。また、入力インタフェース５にキーボード、マウス等の入力装置６が接続され、出力インタフェース７に出力装置８が接続され、外部記憶装置インタフェース９にハードディスク、フレキシブルディスク、ＣＤＲＯＭ、ＭＤ、ＭＯ等の記憶装置１０が接続されている。ＲＯＭ３には、ＣＰＵ２が実行する処理プログラム３ａが格納されている。ＲＡＭ４には、図形要素格納領域４ａ、属性情報４ｂ及び検索条件４ｃが割り当てられている。出力装置８には、ＣＲＴ及び液晶ディスプレイ等の表示装置８ａ、並びに印刷装置及びプロッタ８ｂが含まれている。記憶装置１０には、処理の対象及び結果となるデータが格納され、保存される。なお、データバス１は、外部の装置にも接続可能である。
【００２４】
沿面距離を算出すべき２点（始点及び終点）の設定等のユーザからの指示は、入力装置６を介してＣＰＵ２により検出される。また、途中の処理状況及び最終的な結果の出力は出力装置７を通じて行われる。処理上必要なデータは、データバス１を通して、ネットワーク上及び同一の装置上の入力装置６や記憶装置１０からインタフェース５や９を通じて、ＲＡＭ４に格納され、ＣＰＵ２がＲＯＭ３に格納されたプログラムの手順に従って処理を行う。処理の段階に応じて、一時的に必要なデータは高速な記憶装置ＲＡＭ４、出力されて保存の必要なデータは記憶装置１０に格納され、最終的な出力は、例えば、データバス１を通じてネットワーク上の必要なサーバ（図示せず）に格納される。
【００２５】
次に、処理プログラム３ａの内容及び処理プログラム３ａに基づく沿面距離算出装置の動作、即ち沿面距離算出方法について説明する。
【００２６】
なお、本実施形態では、対象物である各部品形状は三角形メッシュで表現されている三角形多面体（又は三角形メッシュモデル）であるとして処理を行う。つまり、構成面はすべて三角形パッチであり、各三角形パッチ間の隣接情報は予め取得されているものとする。各三角形パッチの稜線は二つのパッチにより共有されているので、隣接情報が設定されていれば、稜線を指定することにより、その稜線で隣り合う三角形パッチを得ることができる。また、頂点もその頂点を持つ三角形パッチ間で共有されており、頂点を指定することによって、その頂点を持つ三角形パッチを列挙することができる。
【００２７】
一般に、部品形状の構成面は幾何形状、及びその幾何形状が表現する領域のうち、どの部分が構成面になっているかを表現するループ情報等の境界情報を用いて表現される。ここで、幾何形状には、平面、円筒面、球面、円錐面、トーラス面、Coons曲面、Bezier曲面、Rational Bezier曲面、B-Spline曲面、NURBS曲面等の自由曲面等が含まれる。しかし、構成面が曲面を含む任意の構成面である場合に比べて、三角形多面体の場合は、形状の表現及び形状に対する処理が著しく簡単となるので、本実施形態例では主に三角形多面体に近似して、その上での沿面経路を算出する。
【００２８】
なお、多面体の場合も、各構成面は多角形となるが、図２に示すように、任意の多角形は複数の三角形を用いて表現することができる。従って、各構成面である多角形を分割してすべての構成面を三角形パッチに変換することにより三角形多面体に変換することは可能である。また、図３に示すように、曲面等の任意の構成面よりなる立体も、形状を多面体に近似した後、三角形多面体に変換することにより、曲面モデルを三角形メッシュモデルに変換することができる。市販されている３次元ＣＡＤの多くはＶＲＭＬやＳＴＬ等の形式の近似多面体を出力することができる。従って、曲面モデルに対しても本実施形態によって、近似的な沿面経路を求めることが可能である。
【００２９】
そして、本実施形態では、対象物である各部品の形状を構成する各三角形メッシュの幾何情報及び位相情報は、事前にＲＡＭ４又は記憶装置１０等に格納しておく。部品の幾何情報は各三角形メッシュを構成する各三角形パッチの頂点の座標情報を示し、位相情報は各三角形パッチがどの頂点から構成されているか、物体の表側はどちらにあるか、各三角形パッチがどのような隣接関係にあるかを示す。各三角形パッチがどの頂点から構成されているかは、各頂点にＩＤを付して、各三角形パッチと各三角形パッチの頂点ＩＤのリストとを互いに対応付けることによって表現される。また、このリストの順番に意味を持たせ、並んでいる３つの頂点の回り向きが半時計回りになるように見える側を物体の表側と規則づけることにより、物体の表側がどちらにあるかを表現することができる。また、各三角形パッチの隣接関係については、各三角形パッチの各頂点に対して、その頂点を通らない稜線を共有して隣り合う三角形パッチを関連付けることによって、各三角形パッチ間の隣接関係を表現することができる。これらの情報は、例えば、キーボード又はマウス等の入力装置６を用い、出力装置８で確認しながら入力しておけばよい。また、予め格納した一般の多面体モデルデータ及び／又は曲面モデルデータからＣＰＵ２が三角形パッチに変換したデータをＲＡＭ４又は記憶装置１０等に格納しておいてもよい。
【００３０】
また、組立品のレイアウト情報も事前にＲＡＭ４又は記憶装置１０等に格納しておく。組立品のレイアウト情報は、上記各部品の頂点の幾何情報をすべて同一の大域的な座標系で表現していれば特に必要ない。各部品が夫々に固有の局所的な座標系で定義されている場合は、各部品の局所的座標系と製品全体で共有する大域的な座標系との変換方法を表現する情報をレイアウト情報として格納する。部品間の近接関係は、この大域的座標系に基づいて検出する。
【００３１】
図４は、本発明の第１の実施形態における沿面距離算出処理を実行するＣＰＵ２の動作処理フローチャートである。
【００３２】
本実施形態では、先ず、ステップＳ１において、ＣＰＵ２は、ユーザ（使用者）により入力装置６を介して入力された固定通過点、制御点及びその並び順に関するデータを入力インタフェース５及びデータバス１を介してＲＡＭ４又は外部記憶装置１０に保存する。ここで、固定通過点とは、沿面経路が必ず通過すべき点である。一方、制御点とは沿面経路を算出するに当たり、経路探索の手がかりとして参照する点であり、沿面経路が必ずしも通過する必要はない点である。本実施形態では、後述のように、最初に求める仮の沿面経路（初期経路）に制御点を通過させる。例えば、図５に示すように、ユーザにより、固定通過点Ｆ１、Ｆ２及びＦ３、並びに制御点Ｃ１及びＣ２が入力される。また、ユーザにより、例えば、これらの並び順として、「Ｆ１→Ｃ１→Ｆ２→Ｃ２→Ｆ３が入力される。
【００３３】
なお、入力された固定通過点、制御点及びその並び順を表示装置８ａに表示することによって、ユーザが、入力した固定通過点、制御点及びその並び順の確認を容易に行えるようにする。
【００３４】
固定通過点及び制御点の入力は、部品形状を表現する三角形メッシュの既存の頂点を指示するか、又は部品形状を構成する稜線若しくは三角形パッチ上の任意の点を指示することによって行われる。この入力は、例えば、既存の頂点のＩＤをキーボードで入力するか、又は出力装置８ａに部品形状（三角形メッシュ）を表示している状態（図５では省略している）で、マウス等を使って既存の頂点を指示することによって実行される。
【００３５】
なお、ユーザが、固定通過点又は制御点を既存の頂点とは異なる点（既頂点以外の点）にしたいと考える場合も想定される。そこで、本実施形態では、出力表示８ａに表示した部品形状に対して、入力装置６を使って指定しようとする固定通過点又は制御点の位置をもＣＰＵ２が受け付ける。例えば、ＣＰＵ２は、三角形メッシュモデルの稜線をマウスで指示したことを検出した後に、当該稜線を内分するパラメータを入力することによって、当該稜線上の点を厳密に分析して特定することが可能である。ＣＰＵ２は、稜線のＩＤをキーボードで入力して稜線を指定したことを検出した場合にも、同様の特定を行うことが可能である。また、ＣＰＵ２は、三角形メッシュモデルの三角形パッチをマウスで指示したことを検出した後に、パラメータ等を入力することによって、当該三角形パッチ内の点を厳密に分析して特定することが可能である。ＣＰＵ２は、三角形パッチのＩＤをキーボードで入力して三角形パッチを指定したことを検出した場合にも、同様の特定を行うことが可能である。パラメータとしては、例えば、固定通過点又は制御点の当該三角形パッチにおける重心座標が挙げられる。
【００３６】
そして、本実施形態では、処理の簡素化のために、既存の頂点以外の点が指示された場合、図６又は図７に示すように、指定された固定通過点又は制御点が三角形パッチの頂点となるように、三角形パッチの分割を行う修正処理をＣＰＵ２が行う。その後、修正後の三角形メッシュモデルをＲＡＭ４又は記憶装置１０に格納する。そして、ステップＳ２以降の処理を実行する。なお、図６は、固定通過点又は制御点が稜線上にある場合の三角形パッチ分割の処理方法を示す図であり、図７は、固定通過点又は制御点が三角形パッチの面内にある場合の三角形パッチ分割の処理方法を示す図である。
【００３７】
ステップＳ２では、ステップＳ１において入力された固定通過点、制御点及び並び順に基づいて、ＣＰＵ２は、三角形メッシュモデルに対して、メッシュ上の経路モデルを近似する重み付きグラフを作成する。
【００３８】
重み付きグラフの作成に当たり、先ず、図８に示すように、ＣＰＵ２は、三角形メッシュの各稜線に内挿点を挿入する。この内挿点及び三角形メッシュの頂点が重み付きグラフの頂点となる。均一なグラフを作成するために各稜線上になるべく一定の間隔になるよう内挿点が配置される。このとき、稜線に挿入する内挿点の数ｍは、例えば、内挿点を挿入する稜線の長さをＬ、所定の基準配置間隔をｄとしたとき、「ｍ＝ｃｅｉｌ（ｌ／ｄ）−１」を満たすものとする。ここで、関数ｃｅｉｌ（ｘ）はｘ以上で最小の整数を返す関数である。ｄの値はユーザが入力装置６から指定してもよく、また、物体の全体の大きさに対する比率等を予め与えたりすることによりＣＰＵ２が計算してもよい。
【００３９】
重み付きグラフのアークは、図８に示すように、三角形メッシュを構成する三角形パッチごとに以下の規則でノードを結んだものとする。また、アークの重みはアークの端点となる２個のノード間の距離とする。
（１）同一稜線上の隣り合うノード間にアーク（稜線アークとよぶ）を作成する。
（２）同一稜線上にないノード間にアーク（面上アークとよぶ）を作成する。
【００４０】
このような処理の結果、部品形状を表現する三角形メッシュモデルの頂点及び稜線上の内挿点がノード、各三角形パッチでそれらのノードを結ぶ線分がアーク、ノード間の距離が対応するアークの重みとなる重み付きグラフが得られる。例えば、部品の形状が立方体の場合には、図９に示すような重み付きグラフが得られる。また、図５に示す固定通過点及び制御点が入力されている場合には、図１０に示すような重み付きグラフが得られる。
【００４１】
なお、複数の部品からなる組立品に対する重み付きグラフを作成する場合は、上述のようにして各部品に対する重み付きグラフの作成を行った後、ＣＰＵ２は、必要に応じて、図１１に示すような部品間接続アークを作成する。そして、ＣＰＵ２は、組立品全体で１個の重み付きグラフを作成する。
【００４２】
部品間接続アークの作成に当たり、各部品上の重み付きグラフの各ノードに対して、ある閾値以内の距離に他の部品が存在する場合、ＣＰＵ２は、注目しているノードから近接する部品に対する最短線の足の位置を算出する。その最短線の足が、近接部品上の既に存在するノードとある閾値以内の距離にあるときには、ＣＰＵ２は、注目ノードとその近接部品上の当該既存のノードとを繋ぐ部品間接続アークを作成する。一方、最短線の足が、近接部品上の既存のノードから閾値を超えて離れているときには、ＣＰＵ２は、新たに近接部品上に面上ノードを作成する。新たに作成したノードは、近接部品の稜線上又は三角形パッチの面内に位置することとなる。
【００４３】
そして、新たに作成したノードが稜線上にある場合は、ＣＰＵ２は、当該新たに作成したノードとその稜線上で隣り合う各ノードとを繋ぐアークを作成する。一方、新たに作成したノードが三角形パッチの面内にある場合は、ＣＰＵ２は、当該新たに作成したノードとその三角形パッチの稜線及び頂点上にある各ノードとを繋ぐアークを作成する。
【００４４】
図１１に示す例は、新たに作成したノードが近接部品の三角形パッチの面内にある場合を示している。即ち、図１１に示す例では、部品Ａのある三角形パッチの稜線上内挿点の位置に作成したノードを着目ノードとして、着目ノードに近接する部品Ｂの三角形パッチの面内に、着目ノードから降ろした最短線の足の位置に面内ノードを作成している。更に、着目ノードと面内ノードとの間に部品間接続アークを作成している。このグラフの作成方法は、従来の第４の方法と同様である。
【００４５】
重み付きグラフを作成した後には、ステップＳ３において、重み付きグラフの最短経路探索を行うことにより、沿面経路探索のための初期経路を求める。経路の探索には、Ｄｉｊｋｓｔｒａ法又はＡ*等の方法を採用することができる。例えば、従来の第１の方法を採用することもできる。
【００４６】
具体的には、ＣＰＵ２は、初期経路探索手段として、ステップＳ１において指定された固定通過点及び制御点に対して、その並び順に従って連続する２点を順番に抽出する。抽出された前の点を始点、後の点を終点として、ＣＰＵ２は、上記の物体表面上の重み付きグラフに対する最短経路を求める。これらの経路をすべて繋げた経路、即ち、合成した経路を沿面経路探索の単一の初期経路とする。部品の形状が立方体であり、その結果図９に示すような重み付きグラフが得られている場合、図１２に示すような初期経路が得られる。また、図１０に示すような重み付きグラフが得られている場合は、先ず、ＣＰＵ２は、始点及び終点の組み合わせを夫々（Ｆ１、Ｃ１）、（Ｃ１、Ｆ２）、（Ｆ２、Ｃ２）、（Ｃ２、Ｆ３）としたグラフ上の最短経路を個別に求める。そして、これらの最短経路をすべて繋げた経路を初期経路とする。この結果、図１３に示すような単一の初期経路が得られる。
【００４７】
その後、ステップＳ４〜Ｓ７において、ステップＳ３で求めた初期経路の部分的な改善を繰り返し、ＣＰＵ２は、短縮経路探索手段として、固定通過点同士を結ぶ経路のうちで、より短い経路を探索的に求めていく。例えば、ステップＳ４及びＳ５では、部分経路の局所的な展開面を利用することによって、ＣＰＵ２は、その部分経路の始点及び終点を繋ぐ厳密な最短経路を求め、部分経路をその最短経路で置き換えていくことによって、より短い経路を求めていく。この結果、各部品上の経路を次第に短いものとすることができる。また、ステップＳ６は複数の部品からなる組立品に対して必要なステップであり、ＣＰＵ２は、組立品に対する探索経路のうち、各部品上の経路を繋ぐ部分の部分経路をより短縮していくことによって、より短い経路を算出する。これらのステップＳ４、Ｓ５及びＳ６の処理内容は単純な処理であるため、ＣＰＵ２は高速に安定的に実行できる。そして、ＣＰＵ２は、これらのステップを繰り返し行い、ステップＳ７で経路の改善が指定した閾値以上行われなかったと判断したら、探索経路改善の処理を終える。
【００４８】
ここで、図１４を参照しながら、ステップＳ４の処理について説明する。ステップＳ４では、ＣＰＵ２は、主に、頂点回りのショートカットを探索する。図１４は、ステップＳ４の処理の内容を示す図である。
【００４９】
先ず、ＣＰＵ２は、着目している頂点を頂点として持つ入力三角形メッシュの三角形パッチをすべて取り出す。図１４の例では、着目している頂点通過点をＶとすると、図１４（ａ）に示すＴ１〜Ｔ５の三角形パッチが取得される。ここで、通過点とは、探索経路と入力三角形メッシュの頂点若しくは稜線と交わる点、又は経路が部品間に跨るとき一方の部品上の通過点から他の部品に最短線を降ろしたときに最短線の足になる点である。特に、頂点通過点は三角形メッシュの頂点上にあるノードを通過する点であり、内挿通過点は三角形メッシュの稜線上に内挿されたノードを通過する点である。
【００５０】
次に、ＣＰＵ２は、直近の探索経路が、取得したＴ１〜Ｔ５の三角形パッチ群と最初に交差するときの通過点、及び最後に交差するときの通過点を抽出し、それらを夫々部分経路の開始点Ｉｓ及び終了点Ｉｔとする。
【００５１】
次に、図１４（ｂ）に示すように、ＣＰＵ２は、取得した三角形パッチを展開する。具体的には、ＣＰＵ２は、取得した三角形パッチを着目頂点Ｖと開始点Ｉｓとを結ぶ線分（開始線分）から、着目頂点Ｖと終了点Ｉｔとを結ぶ方向（終了線分）まで、着目頂点Ｖを中心として時計回り及び反時計回りに２次元平面上に放射上に展開する。そして、ＣＰＵ２は、この展開面を利用して、頂点通過点Ｖ回りの部分経路に対してショートカットが存在するか否かを判定する。この判定では、図１４（ｂ）に示すように、開始線分から終了線分に対して、展開方向に沿って隣り合う稜線間の角度の総和とπとを比較すればよい。即ち、図１４（ｂ）の反時計回りに展開した場合のように、角度の総和がπより小さいときは、展開面上で開始点Ｉｓから終了点Ｉｔまでの間にＴ１〜Ｔ５の三角形パッチを通過する線分を引くことができる。このことは、図１４（ａ）に示す経路よりも短いショートカットが存在することを意味している。一方、図１４（ｂ）の時計回りに展開した場合のように、角度の総和がπを超えるときは、三角形パッチ内を通過するショートカットは存在せず、このことは、開始点Ｉｓ、着目通過点Ｖ、終了点Ｉｔを順に結ぶ線分列が一番短い経路ということになる。
【００５２】
図１５は、図１４（ｂ）の反時計回りに展開した場合の図をより詳細に示したものである。図１５に示すように、開始線分から終了線分までの間に、回り向きに沿って順に稜線Ｅ１及びＥ２が存在している。また、ＣＰＵ２は、隣り合う線分又は稜線間の角度は、回り向きに沿って順にα１、α２、α３である。従って、その総計であるα＝α１＋α２＋α３がπより小さいか否かに基づいてショートカットが存在するか否かを判定できる。なお、αの値は開始線分、終了線分及びその間に挟まれる稜線の位置が判明されていれば、展開面を作成せずに求めることもできる。
【００５３】
そして、反時計回り、時計回りのいずれにおいてもショートカットが存在しない場合は、開始通過点Ｉｓ、着目通過点Ｖ、終了通過点Ｉｔが一直線上に位置することになり、これらを結ぶ線分列を局所的な最短経路とする。一方、反時計回り又は時計回りの少なくとも一方の回り向きに展開した場合に、ショートカットが存在するときには、ＣＰＵ２は、ショートカットが存在すると判定した回り向き毎に図１４（ｂ）、図１５に示すような展開図を作成する。展開図の作成に当たり、本実施形態では、開始線分、終了線分及びその間に挟まれた稜線の長さと隣り合う線分又は稜線の角度という局所的な幾何学的なデータのみを用いる。図１５に示す例では、開始線分をＸ軸方向に配置すれば、他の稜線及び終了線分は長さと開始線分とのなす角度がすべて得られるので２次元上に容易に配置することができる。次に、展開面で開始点Ｉｓと終了点Ｉｔとを結ぶ線分を作成することにより、図１４（ｃ）に示すように、ショートカットが作成される。
【００５４】
また、このショートカットを探索経路の部分経路とするために、図１４（ｂ）の星印の点のように、ＣＰＵ２は、各稜線との交点を求めて通過点を求める。但し、この処理も２次元の局所的な展開面上で簡単に計算することができる。
【００５５】
そして、２次元の局所的な展開面で求められたショートカットの経路は容易に三角形メッシュ上の経路に復元することが可能である。この処理では、図１６に示すように、展開面上で三角形メッシュの稜線上の通過点である内挿点の、その内挿点の乗っている稜線及び、その稜線上の長さｌに対する始点Ｖ１’と内挿Ｉ’点との距離ｄとの比であるパラメータ値ｔ（＝ｄ／ｌ）を用いる。つまり、稜線の始点、終点を夫々Ｖ１、Ｖ２としたとき、数式「Ｉ＝Ｖ１＋Ｔ×（Ｖ２−Ｖ１）」により展開図上の内挿点を三角形多面体上の内挿点に変換すればよい。
【００５６】
但し、ステップＳ４の処理は、着目している頂点通過点又は通過点に近接している頂点が固定通過点として指定されている場合は、その定義により経路の改善は行わない。探索経路の内挿通過点が入力三角形メッシュのある頂点に近接しているかどうかの判定は、例えば、条件式「ｄ／ｌ＜ｅｐｓ」が満たされているか否かに基づいて行う。ここでは、内挿通過点の存在する三角形メッシュの稜線の長さをｌ、その内挿通過点と稜線の端点の頂点との距離をｄ、所定の誤差比率をｅｐｓとしている。そして、上記条件式が満たされていれば、近接していると判断できる。なお、誤差比率ｅｐｓは、例えば、予めＲＡＭ４又は記憶装置１０に格納しておけばよい。探索経路の通過点が三角形メッシュの頂点を通るときだけでなく、その頂点に近接する内挿点を通過する場合でも、上記で説明した処理を行うことにより、図１７に示すような場合も探索経路の改善を行うことができる。図１７に示す例では、探索経路はＶを通っていないが、破線で示すような部分経路が存在するのである。
【００５７】
また、図１８に破線で示すような頂点回りの局所的な経路が存在する場合も、三角形メッシュモデルの頂点の周りに、その頂点を頂点として持つ三角形パッチ群の展開図を作って、その三角形パッチ群を通過する探索経路のショートカットを得ることができる。ショートカットは、実線で表してある。
【００５８】
なお、展開図の作成は、上記の着目通過点を持つ三角形パッチが同一平面になるように、隣り合うパッチの共有稜線を軸としてパッチを回転していくという操作を繰り返すことによっても行うことができる。しかしながら、この方法では計算コストが高く、展開するときの誤差が集積していく虞がある。また、３次元の座標変換計算が必要なので、本実施形態と比較すると、計算コストも高くなる。
【００５９】
次に、図１９を参照しながら、ステップＳ５の処理について説明する。ステップＳ５では、主に、経路を単純経路に分解して、各単純経路での最適化を図る。つまり、最短単純経路を求める。ここで、単純経路とは、探索経路を、探索経路が通過する始点、終点及び頂点通過点が端点となるような部分経路に分解していったときの各部分経路のことである。また、単純経路をつなげたものを複合経路とする。一般に、探索経路は、始点及び終点の他に複数の頂点通過点を通過するので、複合経路となっている。各単純経路は、単純経路の始点及び終点以外は頂点通過点を通らないので、各通過点が存在する稜線列に従って一意に展開面を得ることが可能となり、この展開面上における最短経路を算出することが可能になる。なお、ステップＳ５の処理は、ステップＳ４の処理と類似している。
【００６０】
先ず、ＣＰＵ２は、着目している単純経路に通過稜線があるかどうかを判定する。そして、通過稜線があると判定した場合、例えば図１９（ａ）に示すような探索経路について処理する場合は、図１９（ｂ）に示すように、ＣＰＵ２は、この通過稜線に沿って経路が通過する通過三角形パッチを２次元上に展開する。展開の方法としては、頂点回りの展開面の作成法と同様に、隣り合う三角形パッチの共有稜線を軸として同一平面になるように三角形パッチを回転していくという方法があるが、この方法は、計算コストが高く、展開するときの誤差が集積していくという問題がある。
【００６１】
そこで、本実施形態において、ＣＰＵ２は、三角形メッシュモデルの局所的な幾何データのみを使うことにより展開図を作成する。ここで利用するデータは、開始点を通る稜線のいずれか、及び通過稜線の長さ、隣り合う稜線のなす角度、隣り合う稜線がその２つの稜線を持つ三角形パッチにおいてどのような位置関係になっているかという情報である。図１９（ａ）に示す例では、開始点を通る稜線はＥｓであり、通過稜線はＥ１、Ｅ２、Ｅ３及びＥ４である。隣り合う稜線の位置関係に関する情報には、具体的には図２０のように経路の通過する稜線の順番に従って、ある稜線を着目稜線、次の稜線を次着目稜線とすると、次のものが含まれる。先ず、着目稜線の長さ、次着目稜線の長さ、着目稜線と次着目稜線とのなす角度（図２０のθ）が含まれる。また、着目稜線及び次着目稜線の両方を稜線として持つ着目パッチにおいて、次着目稜線が着目稜線の時計回り側にあるか（図２０の左側の図）、反時計回り側にあるかの情報（図２０の右側の図）という情報も含まれる。これらの情報があれば、展開面上に順番に通過パッチ列を再現していくことができる。
【００６２】
最初の稜線（例えば図１９（ａ）のＥｓ）は、例えば、２次元のＸ軸上に配置すればよい。このように通過パッチ列が２次元上に展開した後、ＣＰＵ２は、次に開始点と終了点とを結び通過パッチ列の内部を通る最短線分列を求める。図１９に示す例では、図１９（ｂ）中の太い実線が最短線分列（単位最短経路）になる。比較のため、図１９（ｂ）では改善を行う前の探索経路の展開図上での経路を点線で表示している。
【００６３】
最短線分列を求めた後には、ＣＰＵ２は、この最短線分列を経路表現に変換する。線分列を経路表現するためには、ＣＰＵ２は、線分列を構成する各線分と交差する稜線との交点を内挿点として求める。例えば、図２１に示す例では、内挿点Ｉ１、Ｉ２が経路表現を得るために求める通過点である。
【００６４】
そして、上記の最短線分列を構成する各線分と交差する稜線は、次のように表される。即ち、各線分の始点を頂点として持つ三角形パッチのうち最後に展開されるパッチから、各線分の終点を頂点として持つ三角形パッチのうち最初に展開される三角形パッチを辿っていくときに出現するパッチ間の共有稜線である。図２１に示す例においては、「各線分の始点を頂点として持つ三角形パッチのうち最後に展開されるパッチ」は、Ｖｓを始点とする線分ではＴ１であり、Ｖｍを始点とする線分ではＴ６である。また、「各線分の終点を頂点として持つ三角形パッチのうち最初に展開される三角形パッチ」は、Ｖｍを終点とする線分ではＴ３であり、Ｖｅを終点とする線分ではＴ６である。従って、図２１の例では、最短線分列を構成する２つの線分のうち、Ｖｓを始点としてＶｍを終点とする線分ではＴ１からＴ３を辿る上で出現する共有稜線Ｅ１、Ｅ２が存在する。一方、Ｖｍを始点としてＶｅを終点とする線分では、開始パッチ及び終了パッチの双方がＴ６なので、出現する共有線分はなく、交差する稜線はない。
【００６５】
経路表現への変換を終えた後には、ステップＳ４と同様の方法で、ＣＰＵ２は、最短線分列と各共有稜線との交点の稜線上におけるパラメータを求め、展開面上の経路が通過する交点を求めて、図１９（ｃ）に示すように、最短経路を多面体上に復元する。
【００６６】
なお、上述のように、単純経路は頂点通過点を開始点、終了点とし、その間に内挿通過点があるという構造をしている。このため、これらの間に内挿通過点がない場合は、最適化をするまでもなく開始点及び終了点を結ぶ線分（稜線になっている）が最短であるので、この線分を最短経路とすればよい。
【００６７】
即ち、ステップＳ５の処理では、ＣＰＵ２は、図２２に破線で示すような探索経路が存在する場合、単純経路が横切る稜線列（単純稜線列とよぶ）に沿って通過する三角形パッチ（単純通過パッチ列とよぶ）を平面上に展開した展開図を作成する。そして、その展開図上で最短経路を探索して探索経路をより短縮するのである。なお、単純稜線列は、複合稜線列を分解することにより得られたものである。
【００６８】
ここで、上述のステップＳ４及びＳ５の処理を立方体上の経路に適用した場合の結果について、図２３を参照しながら、説明する。ここでは、図２３（ａ）に示すように、部品形状を表現する三角形メッシュモデル上に作成した重み付きグラフを探索して沿面経路探索の初期探索経路が算出されたとする。
【００６９】
このような場合、ステップＳ４において、図２３（ｂ）に示すように、ＣＰＵ２は、初期探索経路が通過する頂点通過点Ｖの回りにある三角形パッチＴ２、Ｔ３、Ｔ４及びＴ５を展開した展開面を作成し、このパッチ列を通過する探索経路の部分経路の改善を行う。上記の展開面上では、この展開面を通過する部分経路の始点から終点を結ぶ直線を引くことができるので、これにより最短経路を算出することが可能となる。そして、この例では、上記の直線と入力した三角形メッシュの稜線との交点を求めることにより、ＣＰＵ２は、新たに内挿通過点Ｉ３及びＩ４を算出し、頂点Ｖを通らない経路をこの展開面上の最短経路として算出する。
【００７０】
次いで、ステップＳ５において、図２３（ｃ）に示すように、ＣＰＵ２は、経路が横切る単純通過パッチ列Ｔ１，Ｔ２，Ｔ３，Ｔ４を平面上に展開する。そして、ＣＰＵ２は、展開面上でこの単純通過パッチ列の内部を通る最短経路を算出し、その経路と入力三角形メッシュモデルの稜線との交線を求めることにより、内挿通過点Ｉ１’、Ｉ３’及びＩ４’を算出し、元の内挿通過点Ｉ１、Ｉ３及びＩ４を夫々更新する。なお、この例では、始点から終点を結ぶ経路は、始点及び終点の他に頂点通過点がなく単純経路となっているので探索経路の分解を行う必要はない。
【００７１】
このように、ステップＳ４では、探索経路の各通過点が三角形メッシュの頂点であるとき、又はある頂点の近辺を通過するときに、ＣＰＵ２は、その頂点を頂点として持つ三角形メッシュ群の展開面を作成する。そして、その三角形メッシュ群を通過する探索経路の部分経路に対して、現在の部分経路より短い経路（ショートカット）が存在する場合は、ＣＰＵ２は、その経路を算出してこの部分経路を置き換える。この処理では、探索経路の改善を行う前の直近の探索経路が横切る稜線列とは異なる稜線列を横切る経路を得ることができるので、ステップＳ５だけの処理では算出することのできない経路を算出することが可能になる。但し、上述のように、ステップＳ４の処理は、着目している頂点通過点又は通過点に近接している頂点が固定通過点として指定されている場合は、その定義により経路の改善は行わない。
【００７２】
次に、ステップＳ４及びＳ５について、図２４に示す仮想の例を参照しながら、より一般化して説明する。ここでは、ステップＳ３において、図２４（ａ）に示すような沿面経路探索のための初期探索経路が得られたとする。この例では、始点及び終点以外の通過点として、頂点通過点Ｙ１及びＹ２、並びに内挿通過点Ｘ１〜Ｘ７が存在する。
【００７３】
このような場合、ステップＳ４において、頂点回りの部分経路の局所的な改善を行うため、図２４（ｂ）に示すような結果が得られる。即ち、Ｙ１、Ｙ２の頂点回りの部分経路が改善され、Ｙ１がなくなると共に、内挿通過点Ｉ８が新たに挿入されている。なお、Ｙ２の頂点回りの部分経路にはショートカットが存在しなかったのでＹ２の頂点回りの部分経路は変化していない。
【００７４】
次に、ステップＳ５において、ＣＰＵ２は、図２４（ｃ）に示すように、図２４（ｂ）の複合経路を単純経路Ｅ１及びＥ２に分解する。
【００７５】
次いで、同じくステップＳ５において、図２４（ｄ）に示すように、ＣＰＵ２は、各単純経路Ｅ１、Ｅ２に対して、最適化された最短経路Ｅ１’、Ｅ２’を算出し、元の単純経路Ｅ１及びＥ２をＥ１’、Ｅ２’に置き換える。具体的には、算出した結果に基づき、ＣＰＵ２は、内挿通過点の更新、削除、新たに通過する頂点通過点、内挿通過点の挿入を行う。
【００７６】
そして、同じくステップＳ５において、図２４（ｅ）に示すように、ＣＰＵ２は、各単純経路に対して最短経路に置き換えたものを統合して、全体の探索経路を更新する。
【００７７】
ステップＳ３において図１３に示すような初期経路が得られている場合、このようなステップＳ４及びＳ５の処理の結果、図２５に示すような経路が得られる。
【００７８】
ステップＳ５の後には、ステップＳ６において、各部品上のグラフを接続する部品間接続アークの前後の部分経路を最適化することによって、探索経路の改善を行う。つまり、ステップＳ６は、対象が複数の部品からなる組立品の場合に必要な処理である。
【００７９】
具体的には、先ず、次のような定義付けを行う。即ち、部品間接続アークの端点となるノードのうち三角形メッシュの稜線上にあるノードを着目ノードとする。また、部品間接続アークの端点となるノードのうち着目ノードでない、着目ノードと別の部品上にある他方のノードを面内ノードとする。また、探索経路上で着目ノードに隣接するノードのうち面内ノードでない、着目ノードと同一部品にあるノードを前通過ノードとする。また、探索経路上で面内ノードに隣接するノードのうち着目ノードでない、面内ノードと同一部品上にあるノードを次通過ノードとする。
【００８０】
このような定義づけの後に、着目ノードが存在する稜線を着目稜線とし、前通過ノードと次通過ノードを固定して、着目ノードを着目稜線上で動かし、それにあわせて面内ノードを移動することによって部品間を接続する部分経路を最短にする経路を求める。そして、求めた最短経路に置き換える。
【００８１】
最短にする部分経路は、図２６における「Ｌ１＋Ｌ２＋Ｌ３」が最小となる着目ノードの位置を求めれば得ることができる。ここで、Ｌ１は、着目ノードと前通過ノードとを結ぶ線分の長さである。また、Ｌ２は、部品接続アークの長さである。また、Ｌ３は、面上ノードと次通過ノードとを結ぶ線分の長さである。着目ノードの位置Ｐは、着目稜線が決まれば、着目稜線の始点、終点の位置を夫々Ｓ、Ｅと表したとき、数式「Ｐ（ｔ）＝Ｓ＋ｔ（Ｅ−Ｓ）  但し、（０≦ｔ≦１）」と、１変数のパラメータｔで表現することができる。このとき、パラメータの下限値及び上限値が決まっているため、はさみうち法等を用いて簡単に最適化が可能である。
【００８２】
また、着目稜線は、最適化前の着目ノードが入力三角形メッシュの頂点に近接してない場合、即ち、予め定められた所定の距離以上の場合は、最適化前の着目ノードが存在している稜線とする。また、図２７に示す例のように、着目ノードが入力三角形メッシュの頂点又は頂点に十分近い場合、即ち所定の距離未満の場合は、最適化前の直近の着目ノード及び前通過ノードが存在する三角形パッチの稜線のうち、前通過ノードが存在しない２稜線とする。また、面上ノードは、次通過ノードの存在する稜線を持つ三角形パッチ上にあるとする。
【００８３】
ステップＳ６の後のステップＳ７では、経路長が収束しているか判定する。即ち、ステップＳ４〜Ｓ６によって短縮された経路の経路長と、短縮される前の経路長（直近に得られた経路長）とを比較して、短縮された長さ（量又は割合）が所定の閾値以下であれば、経路長が収束したとして、処理を終了する。一方、短縮された長さが所定の閾値を超えている場合には、短縮の余地があるとして、ステップＳ４に戻り経路の短縮処理を繰り返す。
【００８４】
このような本実施形態によれば、設定された固定通過点・制御点に基づき算出された初期探索経路を部分的に短縮していくことによって、精度の高い沿面経路を安定的に短時間で求めることができる。また、人間が実際の製品試作機で沿面距離を測定するのに比べて、手間がかからずにすむ。
【００８５】
更に、本実施形態では、制御点を用いた処理を行っているので、部品の表面に穴等があっても適切な処理を行うことができる。図２８は、実固定通過点として始点及び終点の２点並びに２個の制御点を用いた場合の沿面経路の例を示す図である。この例では、穴を回避しながら沿面経路を求めることができているが、制御点が入力されていない場合には、メッシュ形状及び重み付きグラフの粗さによっては、穴の上側を通る、間違った経路を算出してしまう可能性がある。即ち、本実施形態によれば、制御点を用いることにより、確実に穴の下側を通る精度のよい沿面経路を算出することができる。
【００８６】
そして、本実施形態によれば、始点、終点及び制御点が指定されると、図２９に示すように、部品表面上の最短と考えられる経路を求めることができ、図３０に示すように、複数の部材からなる組立品の製品表面上の最短と考えられる経路を求めることができる。
【００８７】
（第２の実施形態）
次に、本発明の第２の実施形態について説明する。第２の実施形態では、固定通過点及び制御点の編集を可能とし、いくつかの固定通過点及び制御点の組み合わせに対して沿面経路算出の処理を連続して行うことを可能としている。図３１は、本発明の第２の実施形態における沿面距離算出方法を示すフローチャートである。
【００８８】
ステップＳ１からステップＳ７までの処理は、第１の実施形態と同様である。
【００８９】
ステップＳ７において、線路長が収束している場合、ステップＳ８において、ＣＰＵ２は、ステップＳ１からステップＳ７までの処理によって得られた結果を出力装置８から出力する。つまり、ＣＰＵ２は、承認手段として、ユーザに経路の承認を求める。このとき、既に求めた沿面経路並びにその沿面経路に対する固定通過点、制御点及び経路長等を、新たに求めた沿面経路並びにその沿面経路に対する固定通過点、制御点及び経路長と比較しやすいように出力装置８から出力する。出力装置８から出力することにより、本装置のユーザが、算出された沿面経路が妥当であるかが判断しやすくなる。出力装置８からの出力として、例えば表示装置８ａに結果を表示する。
【００９０】
次に、ステップＳ９において、ＣＰＵ２は、ユーザの入力を受付、算出結果が妥当であると入力された場合、即ち、承認された場合は、処理を終え、結果並びに設定した固定通過点及び制御点を記憶装置であるＲＡＭ４及び／又は外部記憶装置１０に保存する。この結果、後に結果を参照したり、新規探索を行ったりすることが可能となる。
【００９１】
一方、算出結果が妥当でないと入力された場合、ステップＳ１０において、出力装置８に対話的に結果を示しながら、ユーザに入力装置６から固定通過点及び制御点の追加及び削除、並びに既存固定通過点及び制御点の位置変更を行わせる。図３２に、このような出力の例を示す。
【００９２】
この例では、先ず、図３２（ａ）に示すように、始点及び終点となる固定通過点Ｆ１及びＦ２並びに制御点Ｃ１が指定されていたものとする。そして、これらの条件に対して、沿面経路Ｒ１が得られているとする。
【００９３】
ここで、図３２（ｂ）に示すように、ユーザの入力を検出することにより、ＣＰＵ２が新たに制御点Ｃ２を挿入すると、新たに算出された沿面経路Ｒ２が得られ、これを表示装置８ａが表示する。逆に、最初に図３２（ｂ）に示す固定通過点及び制御点が指定され、沿面経路Ｒ２が得られているのに対し、制御点Ｃ２が削除されると、図３２（ａ）に示す沿面経路Ｒ１が得られる。
【００９４】
また、図３２（ｃ）に示すように、ユーザの入力の検出に応じて制御点Ｃ１が移動されると、新たに沿面経路Ｒ３が得られ、これを表示装置８ａが表示する。
【００９５】
本実施形態では、このような挿入、削除及び変更を、直前に設定した固定通過点及び制御点に対してだけでなく、以前に設定した固定通過点及び制御点の組み合わせのすべてに対して可能にしてある。このため、ステップＳ１で指定した固定通過点及び制御点、並びにステップＳ２からＳ７までの処理で算出された沿面経路及び経路長は、関連づけていつでも取り出せるように必要な情報を外部記憶装置１０に保存してある。このように、既に求めた沿面経路等を、新たに求めた沿面経路等と比較しやすいように表示することにより、どのように固定通過点及び制御点等を設定すれば適切な沿面経路を得られるかをユーザが判断しやすくなる。
【００９６】
これらの入力は入力装置６を使って行われ、変更した結果は表示装置８ａに逐次、表示され対話的に行われる。また、ステップＳ１と同様、これらの設定した情報はＲＡＭ４又は外部記憶装置１０に保存されて、沿面経路探索の計算に使われる。このステップで固定通過点及び制御点の再設定が行われると、ステップＳ２からステップＳ９までの処理が繰り返され、沿面経路の探索が継続される。
【００９７】
このような第２の実施形態によれば、ユーザが固定通過点及び制御点等を修正することができるので、ユーザの意図を汲み取りながら、より一層、正確な結果を得ることができる。
【００９８】
なお、本発明の実施形態は、例えばコンピュータがプログラムを実行することによって実現することができる。また、プログラムをコンピュータに供給するための手段、例えばかかるプログラムを記録したＣＤ−ＲＯＭ等のコンピュータ読み取り可能な記録媒体又はかかるプログラムを伝送するインターネット等の伝送媒体も本発明の実施形態として適用することができる。また、上記のプログラムも本発明の実施形態として適用することができる。上記のプログラム、記録媒体、伝送媒体及びプログラムプロダクトは、本発明の範疇に含まれる。
【図面の簡単な説明】
【００９９】
【図１】本発明の第１の実施形態に係る沿面距離算出装置を示すブロック図である。
【図２】任意の多角形は複数の三角形を用いて表現する方法を示す図である。
【図３】曲面モデルを三角形メッシュモデルに変換する方法を示す図である。
【図４】本発明の第１の実施形態における沿面距離算出方法を示すフローチャートである。
【図５】固定通過点Ｆ１、Ｆ２及びＦ３、並びに制御点Ｃ１及びＣ２の入力例を示す図である。
【図６】固定通過点又は制御点が稜線上にある場合の三角形パッチ分割の処理方法を示す図である。
【図７】固定通過点又は制御点が三角形パッチの面内にある場合の三角形パッチ分割の処理方法を示す図である。
【図８】内挿点の挿入結果を示す図である。
【図９】部品の形状が立方体の場合の重み付きグラフを示す図である。
【図１０】図５に対する重み付きグラフを示す図である。
【図１１】部品間接続アークを示す図である。
【図１２】部品の形状が立方体の場合の初期経路を示す図である。
【図１３】図５に対する初期経路を示す図である。
【図１４】ステップＳ４の処理内容を示す図である。
【図１５】図１４（ｂ）の反時計回りに展開した場合の図をより詳細に示す図である。
【図１６】三角形メッシュ上の経路に復元する方法を示す図である。
【図１７】探索経路の通過点が三角形メッシュの頂点に近接する内挿点を通過する場合のショートカットを示す図である。
【図１８】頂点回りの局所的な経路が存在する場合のショートカットを示す図である。
【図１９】ステップＳ５の処理内容を示す図である。
【図２０】隣り合う稜線の位置関係に関する情報を示す図である。
【図２１】線分列を構成する各線分と交差する稜線との交点（内挿点）を示す図である。
【図２２】ステップＳ５において作成する展開図を示す図である。
【図２３】ステップＳ４及びＳ５の処理内容を示す図である。
【図２４】一般化したステップＳ４及びＳ５の内容を示す図である。
【図２５】図５に対する探索結果を示す図である。
【図２６】Ｌ１、Ｌ２及びＬ３を示す図である。
【図２７】着目ノードが入力三角形メッシュの頂点又は頂点に十分近い場合の処理内容を示す図である。
【図２８】実固定通過点として始点及び終点の２点並びに２個の制御点を用いた場合の沿面経路の例を示す図である。
【図２９】本発明の第１の実施形態により得られる沿面経路の例を示す図である。
【図３０】本発明の第１の実施形態により得られる沿面経路の他の例を示す図である。
【図３１】本発明の第２の実施形態における沿面距離算出方法を示すフローチャートである。
【図３２】本発明の第２の実施形態の作用を示す図である。
【図３３】従来の沿面経路探索方法を示す図である。
【符号の説明】
【０１００】
１：データバス
２：ＣＰＵ
３：ＲＯＭ
４：ＲＡＭ
５：入力装置用インタフェース
６：入力装置
７：出力装置用インタフェース
８：出力装置
９：外部記憶装置用インタフェース
１０：外部記憶装置
【図１】
2008134948.tif 000003
【図２】
2008134948.tif 000004
【図３】
2008134948.tif 000005
【図４】
2008134948.tif 000006
【図５】
2008134948.tif 000007
【図６】
2008134948.tif 000008
【図７】
2008134948.tif 000009
【図８】
2008134948.tif 000010
【図９】
2008134948.tif 000011
【図１０】
2008134948.tif 000012
【図１１】
2008134948.tif 000013
【図１２】
2008134948.tif 000014
【図１３】
2008134948.tif 000015
【図１４】
2008134948.tif 000016
【図１５】
2008134948.tif 000017
【図１６】
2008134948.tif 000018
【図１７】
2008134948.tif 000019
【図１８】
2008134948.tif 000020
【図１９】
2008134948.tif 000021
【図２０】
2008134948.tif 000022
【図２１】
2008134948.tif 000023
【図２２】
2008134948.tif 000024
【図２３】
2008134948.tif 000025
【図２４】
2008134948.tif 000026
【図２５】
2008134948.tif 000027
【図２６】
2008134948.tif 000028
【図２７】
2008134948.tif 000029
【図２８】
2008134948.tif 000030
【図２９】
2008134948.tif 000031
【図３０】
2008134948.tif 000032
【図３１】
2008134948.tif 000033
【図３２】
2008134948.tif 000034
【図３３】
2008134948.tif 000035