【手続補正書】
【提出日】平成21年11月27日(2009.11.27)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
対象物の表面上の固定点及び制御点を受け付ける受付手段と、
前記対象物の三角形メッシュモデルに対し、前記制御点を参照しながら前記固定点を通る初期経路を取得する初期経路取得手段と、
前記固定点同士を結ぶ経路のうちで、前記初期経路よりも短い経路を取得する短縮経路取得手段と、
を有することを特徴とする沿面経路取得装置。
【請求項２】
前記対象物が複数の部品から構成されている場合に、
前記初期経路取得手段は、前記複数の部品間のレイアウト情報も参照しながら、前記初期経路を取得し、
前記短縮経路取得手段は、前記レイアウト情報も参照しながら、前記初期経路よりも短い経路を取得することを特徴とする請求項１に記載の沿面経路取得装置。
【請求項３】
前記短縮経路取得手段により取得された経路を、その直近に得られた経路と比較し、その短くなった量又は割合が、予め定められた値以下となった場合に前記経路が収束したと判定する判定手段を有することを特徴とする請求項１又は２に記載の沿面経路取得装置。
【請求項４】
前記三角形メッシュモデルの既頂点以外の点が前記固定点又は制御点として指定された場合に、当該固定点又は制御点を頂点とする三角形メッシュモデルを作成するモデル作成手段を有することを特徴とする請求項１乃至３のいずれか１項に記載の沿面経路取得装置。
【請求項５】
前記判定手段により経路が収束したと判定された後に、当該経路の承認を使用者に求める承認手段を有することを特徴とする請求項３又は４に記載の沿面経路取得装置。
【請求項６】
前記受付手段は、前記固定点及び制御点の並び順も受け付けることを特徴とする請求項１乃至５のいずれか１項に記載の沿面経路取得装置。
【請求項７】
初期経路取得手段は、
前記三角形メッシュモデル上の経路モデルを近似する重み付きグラフを作成し、
前記固定点及び制御点のうちから、その並び順に２点を抽出し、最初の点を始点とし、次の点を終点として、前記重み付きグラフ上での最短経路を探索し、
前記最短経路を、前記固定点及び制御点のすべてについて、合成して前記初期経路とすることを特徴とする請求項６に記載の沿面経路取得装置。
【請求項８】
前記短縮経路取得手段は、
直近に求められた経路の各通過点に対して近接する三角形メッシュモデルの頂点を求め、
前記頂点が存在すると共に、当該頂点が固定点でない場合に、当該頂点回りの局所的な最短経路を求め、
前記直近に求められた経路の当該頂点回りの経路を、前記局所的な最短経路で置き換えることを特徴とする請求項１乃至７のいずれか１項に記載の沿面経路取得装置。
【請求項９】
前記短縮経路取得手段は、
直近に求められた経路が通過する三角形メッシュモデル上の複合稜線列を取得し、
前記複合稜線列を複数の単純稜線列に分解し、
前記単純稜線列の各々を横切る経路のうちで最短の経路を単位最短経路として求め、
前記単位最短経路を結合して前記複合稜線列に対する最短経路を求めることを特徴とする請求項１乃至８のいずれか１項に記載の沿面経路取得装置。
【請求項１０】
前記短縮経路取得手段は、
前記複数の部品間を結ぶ部品間接続アークの端点となる２個のノードのうち三角形メッシュモデルの稜線上にあるノードを着目ノードと定義し、
前記２個のノードのうちの他方を面内ノードと定義し、
直近に求められた経路上で前記着目ノードと隣り合う２個のノードのうちで前記面内ノードとは異なるものを前通過ノードと定義し、
前記直近に求められた経路上で前記面内ノードと隣り合う２個のノードのうちで前記着目ノードとは異なるものを次通過ノードと定義し、
前記着目ノードとそれが位置する三角形メッシュモデル内のいずれかの頂点との距離が予め定められた距離以上である場合に、前記着目ノードが位置する稜線を着目稜線と定義し、前記着目ノードと前記いずれかの頂点との距離が予め定められた距離未満である場合に、前記着目ノード及び前記前通過ノードが位置する三角形メッシュモデル内の稜線であって、前記前通過ノードが位置していない２つの稜線を着目稜線と定義し、
前記着目稜線上の任意の第１の点と前記前通過ノードとの距離をＬ１とし、
前記第１の点と前記第１の点から前記次通過ノードの存在する三角形メッシュモデルに対して最短距離をとったときの最短線の足を第２の点との距離をＬ２とし、
前記第２の点と前記次通過ノードとの距離をＬ３としたときに、
距離の和「Ｌ１＋Ｌ２＋Ｌ３」が最短となる第１の点を求め、
前記着目ノードを前記第１の点に変更し、
前記面内ノードを前記第２の点に変更することを特徴とする請求項２乃至９のいずれか１項に記載の沿面経路取得装置。
【請求項１１】
前記三角形メッシュモデル上の頂点を前記固定点又は制御点として使用者に指定させる第１の手段と、
前記三角形メッシュモデル上の稜線及び当該稜線上の内分パラメータを特定させることにより、前記固定点又は制御点を使用者に指定させる第２の手段と、
前記三角形メッシュモデル上の三角形パッチ及び当該三角形パッチにおける重心座標を特定させることにより、前記固定点又は制御点として使用者に指定させる第３の手段と、
既に指定された固定点又は制御点の前後に他の固定点又は制御点を使用者に挿入させる第４の手段と、
既に指定された固定点又は制御点を使用者に削除させる第５の手段と、
既に指定された固定点又は制御点の位置を使用者に変更させる第６の手段と、
からなる群から選択された少なくとも１種の手段を有することを特徴とする請求項１乃至１０のいずれか１項に記載の沿面経路取得装置。
【請求項１２】
前記短縮経路取得手段により求められた経路及びそれまでに求められている経路を、これらの経路に対応する固定点及び制御点と共に表示する手段を有することを特徴とする請求項１乃至１１のいずれか１項に記載の沿面経路取得装置。
【請求項１３】
前記短縮経路取得手段により求められた経路及びそれまでに求められている経路を、これらの長さと共に表示する手段を有することを特徴とする請求項１乃至１２のいずれか１項に記載の沿面経路取得装置。
【請求項１４】
対象物の表面上の固定点及び制御点を受け付ける受付ステップと、
前記対象物の三角形メッシュモデルに対し、前記制御点を参照しながら前記固定点を通る初期経路を取得する初期経路取得ステップと、
前記固定点同士を結ぶ経路のうちで、前記初期経路よりも短い経路を取得する短縮経路取得ステップと、
を有することを特徴とする沿面経路取得方法。
【請求項１５】
コンピュータに、対象物の表面上の沿面経路を取得させるためのプログラムであって、
前記コンピュータに、
前記対象物の表面上の固定点及び制御点を受け付ける受付手順と、
前記対象物の三角形メッシュモデルに対し、前記制御点を参照しながら前記固定点を通る初期経路を取得する初期経路取得手順と、
前記固定点同士を結ぶ経路のうちで、前記初期経路よりも短い経路を取得する短縮経路取得手順と、
を実行させることを特徴とするプログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】発明の名称
【補正方法】変更
【補正の内容】
【発明の名称】沿面経路取得装置及び沿面経路取得方法
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００１
【補正方法】変更
【補正の内容】
【０００１】
本発明は、ＣＧ、ＣＡＤ／ＣＡＭ等の計算機を使って形状情報を処理する情報処理プログラムの作成に好適な沿面経路取得装置、沿面経路取得方法及びプログラムに関する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１６
【補正方法】変更
【補正の内容】
【００１６】
本発明の目的は、より高精度の沿面距離をより短時間で求めることができる沿面経路取得装置、沿面経路取得方法及びプログラムを提供することにある。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００１８
【補正方法】変更
【補正の内容】
【００１８】
本発明に係る沿面経路取得装置は、対象物の表面上の固定点及び制御点を受け付ける受付手段と、前記対象物の三角形メッシュモデルに対し、前記制御点を参照しながら前記固定点を通る初期経路を取得する初期経路取得手段と、前記固定点同士を結ぶ経路のうちで、前記初期経路よりも短い経路を取得する短縮経路取得手段と、を有することを特徴とする。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００１９
【補正方法】変更
【補正の内容】
【００１９】
本発明に係る沿面経路取得方法は、対象物の表面上の固定点及び制御点を受け付ける受付ステップと、前記対象物の三角形メッシュモデルに対し、前記制御点を参照しながら前記固定点を通る初期経路を取得する初期経路取得ステップと、前記固定点同士を結ぶ経路のうちで、前記初期経路よりも短い経路を取得する短縮経路取得ステップと、を有することを特徴とする。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００２２
【補正方法】変更
【補正の内容】
【００２２】
（第１の実施形態）
先ず、本発明の第１の実施形態について説明する。図１は、本発明の第１の実施形態に係る沿面経路取得装置を示すブロック図である。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００２３
【補正方法】変更
【補正の内容】
【００２３】
図１に示すように、この沿面経路取得装置では、ＣＰＵ（中央演算装置）２、ＲＯＭ３、ＲＡＭ４、入力インタフェース５、出力インタフェース７及び外部記憶装置インタフェース８がデータバス１を介して互いに接続されている。また、入力インタフェース５にキーボード、マウス等の入力装置６が接続され、出力インタフェース７に出力装置８が接続され、外部記憶装置インタフェース９にハードディスク、フレキシブルディスク、ＣＤＲＯＭ、ＭＤ、ＭＯ等の記憶装置１０が接続されている。ＲＯＭ３には、ＣＰＵ２が実行する処理プログラム３ａが格納されている。ＲＡＭ４には、図形要素格納領域４ａ、属性情報４ｂ及び検索条件４ｃが割り当てられている。出力装置８には、ＣＲＴ及び液晶ディスプレイ等の表示装置８ａ、並びに印刷装置及びプロッタ８ｂが含まれている。記憶装置１０には、処理の対象及び結果となるデータが格納され、保存される。なお、データバス１は、外部の装置にも接続可能である。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００２５
【補正方法】変更
【補正の内容】
【００２５】
次に、処理プログラム３ａの内容及び処理プログラム３ａに基づく沿面経路取得装置の動作、即ち沿面経路取得方法について説明する。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００３１
【補正方法】変更
【補正の内容】
【００３１】
図４は、本発明の第１の実施形態における沿面経路取得処理を実行するＣＰＵ２の動作処理フローチャートである。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００４６
【補正方法】変更
【補正の内容】
【００４６】
具体的には、ＣＰＵ２は、初期経路取得手段として、ステップＳ１において指定された固定通過点及び制御点に対して、その並び順に従って連続する２点を順番に抽出する。抽出された前の点を始点、後の点を終点として、ＣＰＵ２は、上記の物体表面上の重み付きグラフに対する最短経路を求める。これらの経路をすべて繋げた経路、即ち、合成した経路を沿面経路探索の単一の初期経路とする。部品の形状が立方体であり、その結果図９に示すような重み付きグラフが得られている場合、図１２に示すような初期経路が得られる。また、図１０に示すような重み付きグラフが得られている場合は、先ず、ＣＰＵ２は、始点及び終点の組み合わせを夫々（Ｆ１、Ｃ１）、（Ｃ１、Ｆ２）、（Ｆ２、Ｃ２）、（Ｃ２、Ｆ３）としたグラフ上の最短経路を個別に求める。そして、これらの最短経路をすべて繋げた経路を初期経路とする。この結果、図１３に示すような単一の初期経路が得られる。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】００４７
【補正方法】変更
【補正の内容】
【００４７】
その後、ステップＳ４〜Ｓ７において、ステップＳ３で求めた初期経路の部分的な改善を繰り返し、ＣＰＵ２は、短縮経路取得手段として、固定通過点同士を結ぶ経路のうちで、より短い経路を探索的に求めていく。例えば、ステップＳ４及びＳ５では、部分経路の局所的な展開面を利用することによって、ＣＰＵ２は、その部分経路の始点及び終点を繋ぐ厳密な最短経路を求め、部分経路をその最短経路で置き換えていくことによって、より短い経路を求めていく。この結果、各部品上の経路を次第に短いものとすることができる。また、ステップＳ６は複数の部品からなる組立品に対して必要なステップであり、ＣＰＵ２は、組立品に対する探索経路のうち、各部品上の経路を繋ぐ部分の部分経路をより短縮していくことによって、より短い経路を算出する。これらのステップＳ４、Ｓ５及びＳ６の処理内容は単純な処理であるため、ＣＰＵ２は高速に安定的に実行できる。そして、ＣＰＵ２は、これらのステップを繰り返し行い、ステップＳ７で経路の改善が指定した閾値以上行われなかったと判断したら、探索経路改善の処理を終える。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】００８７
【補正方法】変更
【補正の内容】
【００８７】
（第２の実施形態）
次に、本発明の第２の実施形態について説明する。第２の実施形態では、固定通過点及び制御点の編集を可能とし、いくつかの固定通過点及び制御点の組み合わせに対して沿面経路算出の処理を連続して行うことを可能としている。図３１は、本発明の第２の実施形態における沿面経路取得方法を示すフローチャートである。
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】００９９
【補正方法】変更
【補正の内容】
【００９９】
【図１】本発明の第１の実施形態に係る沿面経路取得装置を示すブロック図である。
【図２】任意の多角形は複数の三角形を用いて表現する方法を示す図である。
【図３】曲面モデルを三角形メッシュモデルに変換する方法を示す図である。
【図４】本発明の第１の実施形態における沿面経路取得方法を示すフローチャートである。
【図５】固定通過点Ｆ１、Ｆ２及びＦ３、並びに制御点Ｃ１及びＣ２の入力例を示す図である。
【図６】固定通過点又は制御点が稜線上にある場合の三角形パッチ分割の処理方法を示す図である。
【図７】固定通過点又は制御点が三角形パッチの面内にある場合の三角形パッチ分割の処理方法を示す図である。
【図８】内挿点の挿入結果を示す図である。
【図９】部品の形状が立方体の場合の重み付きグラフを示す図である。
【図１０】図５に対する重み付きグラフを示す図である。
【図１１】部品間接続アークを示す図である。
【図１２】部品の形状が立方体の場合の初期経路を示す図である。
【図１３】図５に対する初期経路を示す図である。
【図１４】ステップＳ４の処理内容を示す図である。
【図１５】図１４（ｂ）の反時計回りに展開した場合の図をより詳細に示す図である。
【図１６】三角形メッシュ上の経路に復元する方法を示す図である。
【図１７】探索経路の通過点が三角形メッシュの頂点に近接する内挿点を通過する場合のショートカットを示す図である。
【図１８】頂点回りの局所的な経路が存在する場合のショートカットを示す図である。
【図１９】ステップＳ５の処理内容を示す図である。
【図２０】隣り合う稜線の位置関係に関する情報を示す図である。
【図２１】線分列を構成する各線分と交差する稜線との交点（内挿点）を示す図である。
【図２２】ステップＳ５において作成する展開図を示す図である。
【図２３】ステップＳ４及びＳ５の処理内容を示す図である。
【図２４】一般化したステップＳ４及びＳ５の内容を示す図である。
【図２５】図５に対する探索結果を示す図である。
【図２６】Ｌ１、Ｌ２及びＬ３を示す図である。
【図２７】着目ノードが入力三角形メッシュの頂点又は頂点に十分近い場合の処理内容を示す図である。
【図２８】実固定通過点として始点及び終点の２点並びに２個の制御点を用いた場合の沿面経路の例を示す図である。
【図２９】本発明の第１の実施形態により得られる沿面経路の例を示す図である。
【図３０】本発明の第１の実施形態により得られる沿面経路の他の例を示す図である。
【図３１】本発明の第２の実施形態における沿面経路取得方法を示すフローチャートである。
【図３２】本発明の第２の実施形態の作用を示す図である。
【図３３】従来の沿面経路探索方法を示す図である。