(57)【要約】  本発明は、ＣＡＤシステムにおいて衝突のない配管経路を自動作成する方法、データ処理装置およびコンピュータプログラム製品に関する。本発明では、データ処理装置によって、ＣＡＤ環境における管の少なくとも１つの始点および終点と管の直径とを定義する入力を受け取り、始点と終点とのあいだの複数の標本点を決定し、複数の頂点としての標本点・始点・終点と各頂点を接続する複数の辺とを含むグラフを形成し、始点から終点までの経路を計算し、経路内の頂点ごとに、頂点に接続された各辺に沿って、ＣＡＤ環境における検査オブジェクトモデルと背景モデルジオメトリとの衝突が存在するか否かを検査し、衝突を有する辺をグラフから除去し、経路の辺に衝突が存在しない場合、当該の経路を有効な経路とし、これをユーザに表示する。
2011526389.tif 000002
【特許請求の範囲】
【請求項１】
データ処理装置によって、
ＣＡＤ環境における管の少なくとも１つの始点および終点と管の直径とを定義する入力を受け取るステップ、
前記始点と前記終点とのあいだの複数の標本点を決定するステップ、
複数の頂点としての前記標本点および前記始点および前記終点と、各頂点を接続する複数の辺とを含むグラフを形成するステップ、
前記始点から前記終点までの前記グラフを通る経路を計算するステップ、
該経路内の頂点ごとに、該頂点に接続された各辺に沿って、ＣＡＤ環境における検査オブジェクトモデルと背景モデルジオメトリとの衝突が存在するか否かを検査し、衝突を有する辺を前記グラフから除去するステップ、および
前記経路の辺に衝突が存在しない場合、当該の経路を有効な経路とし、該有効な経路をユーザに表示するステップ
を有する
ことを特徴とするＣＡＤシステムにおいて衝突のない配管経路を自動作成する方法。
【請求項２】
前記データ処理装置により、有効な最短経路を決定する、請求項１記載のＣＡＤシステムにおいて衝突のない配管経路を自動作成する方法。
【請求項３】
経路長さおよび経路内の継手の数に基づいて前記最短経路を決定する、請求項２記載のＣＡＤシステムにおいて衝突のない配管経路を自動作成する方法。
【請求項４】
選択された最小直線長さよりも小さい経路の線分の数および経路内の自己交差の数に基づいて前記最短経路を決定する、請求項２記載のＣＡＤシステムにおいて衝突のない配管経路を自動作成する方法。
【請求項５】
前記検査オブジェクトモデルは球体である、請求項１記載のＣＡＤシステムにおいて衝突のない配管経路を自動作成する方法。
【請求項６】
前記辺が衝突を有さない場合、少なくとも１つの辺を検査済のものとしてマークする、請求項１記載のＣＡＤシステムにおいて衝突のない配管経路を自動作成する方法。
【請求項７】
計算された経路に沿って複数の３Ｄ円柱を含む管を形成する、請求項１記載のＣＡＤシステムにおいて衝突のない配管経路を自動作成する方法。
【請求項８】
有効な経路が存在しない場合、前記計算ステップを反復する、請求項１記載のＣＡＤシステムにおいて衝突のない配管経路を自動作成する方法。
【請求項９】
プロセッサおよびアクセス可能メモリを備えており、ＣＡＤシステムにおいて衝突のない配管経路を自動作成する
データ処理装置であって、
ＣＡＤ環境における管の少なくとも１つの始点および終点と管の直径とを定義する入力を受け取る手段と、
前記始点と前記終点とのあいだの複数の標本点を決定する手段と、
複数の頂点としての前記標本点および前記始点および前記終点と各頂点を接続する複数の辺とを含むグラフを形成する手段と、
前記始点から前記終点までの前記グラフを通る経路を計算する手段と、
該経路内の頂点ごとに、該頂点に接続された各辺に沿って、ＣＡＤ環境における検査オブジェクトモデルと背景モデルジオメトリとの衝突が存在するか否かを検査し、衝突を有する辺を前記グラフから除去する手段と、
前記経路の辺に衝突が存在しない場合、当該の経路を有効な経路とし、該有効な経路をユーザに表示する手段と
を有する
ことを特徴とするデータ処理装置。
【請求項１０】
有効な最短経路を決定する手段を有する、請求項９記載のデータ処理装置。
【請求項１１】
前記最短経路を決定する手段は、経路長さおよび経路内の継手の数に基づいて前記最短経路を決定する、請求項１０記載のデータ処理装置。
【請求項１２】
前記最短経路を決定する手段は、選択された最小直線長さよりも小さい経路の線分の数および経路内の自己交差の数に基づいて前記最短経路を決定する、請求項１０記載のデータ処理装置。
【請求項１３】
前記検査オブジェクトモデルは入力された管の直径に等しいかまたはそれより大きい直径を有する球体である、請求項９記載のデータ処理装置。
【請求項１４】
前記辺が衝突を有さない場合、少なくとも１つの辺を検査済のものとしてマークする手段を有する、請求項９記載のデータ処理装置。
【請求項１５】
計算された経路に沿って複数の３Ｄ円柱を有する管を形成する手段を有する、請求項９記載のデータ処理装置。
【請求項１６】
有効な経路が存在しない場合、前記計算を反復する手段を有する、請求項９記載のデータ処理装置。
【請求項１７】
ＣＡＤシステムにおいて衝突のない配管経路を自動作成する方法を実行する命令、すなわち、
データ処理装置に、
ＣＡＤ環境における管の少なくとも１つの始点および終点と管の直径とを定義する入力を受け取るステップ、
前記始点と前記終点とのあいだの複数の標本点を決定するステップ、
複数の頂点としての前記標本点および前記始点および前記終点と各頂点を接続する複数の辺とを含むグラフを形成するステップ、
前記始点から前記終点までの前記グラフを通る経路を計算するステップ、
該経路内の頂点ごとに、該頂点に接続された各辺に沿って、ＣＡＤ環境における検査オブジェクトモデルと背景モデルジオメトリとの衝突が存在するか否かを検査し、衝突を有する辺を前記グラフから除去するステップ、および
前記経路の辺に衝突が存在しない場合、当該の経路を有効な経路とし、該有効な経路をユーザに表示するステップ
を実行させるコンピュータ実行可能命令
を記憶した機械読み取り可能な有形の記憶媒体を含む
コンピュータプログラム製品。
【請求項１８】
前記記憶媒体は、さらに、有効な最短経路を決定する命令を含む、請求項１７記載のコンピュータプログラム製品。
【請求項１９】
経路長さおよび経路内の継手の数に基づいて前記最短経路が決定される、請求項１８記載のコンピュータプログラム製品。
【請求項２０】
選択された最小直線長さよりも小さい経路の線分の数および経路内の自己交差数に基づいて前記最短経路が決定される、請求項１８記載のコンピュータプログラム製品。
【請求項２１】
前記検査オブジェクトモデルは入力された管の直径に等しいかまたはこれより大きい直径を有する球体である、請求項１７記載のコンピュータプログラム製品。
【請求項２２】
前記記憶媒体は、さらに、前記辺が衝突を有さない場合、少なくとも１つの辺を検査済のものとしてマークする命令を含む、請求項１７記載のコンピュータプログラム製品。
【請求項２３】
前記記憶媒体は、さらに、計算された経路に沿って複数の３Ｄ円柱を有する管を形成する命令を含む、請求項１７記載のコンピュータプログラム製品。
【請求項２４】
さらに、有効な経路が存在しない場合、前記計算ステップを反復する命令を含む、請求項１７記載のコンピュータプログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
他の出願とのクロスリファレンス
本願は、２００８年６月２６日に出願された米国特許仮出願第６１／０７５９２７号明細書の優先権を主張する。この文献は参照により本明細書に組み込まれる。
【０００２】
技術分野
本発明は全体的に、コンピュータ支援による設計、製造および視覚化システムに関する。本発明ではこれらを総称してＣＡＤシステムと称す。
【０００３】
発明の背景
ＣＡＤシステムは、単純なシステムおよび複雑なシステムを設計・視覚化・製造するために使用される。ＣＡＤシステムによって、ユーザは、物理的なアイテムを製造する前に、または、物理的なアイテムを製造する代わりに、オブジェクトおよびシステムのグラフィックモデルを設計することができる。
【０００４】
発明の概要
本発明には、ＣＡＤシステムにおいてパイプおよびチューブのための衝突の無い経路を自動的に作成するためのシステム、方法およびコンピュータプログラム製品が含まれている。本発明の方法では、データ処理システムにより、ＣＡＤ環境におけるパイプの少なくとも１つの始点および終点とパイプの直径とを定義する入力を受け取り、始点と終点との間の複数の標本点を決定し、標本点・始点・終点を複数の頂点として含み、さらにこれらの頂点を接続する複数の辺を含むグラフを形成し、始点と終点との間でグラフを通る経路を計算し、この経路内の頂点ごとに、この頂点に接続されている各辺を検査して、ＣＡＤ環境における検査オブジェクトモデルと背景モデルジオメトリとの間の衝突が各辺に沿って存在しているか否かを決定し、衝突を有している辺をこのグラフから除去し、経路の辺に沿って衝突が無い場合には、この経路を有効な経路とし、この有効な経路をデータ処理システムによってユーザに表示することを含む。
【０００５】
上記の記載は、当業者が後続の詳細な説明をより良く理解できるように、本発明の特徴および技術的な利点を述べたものである。以下では、特許請求の範囲の主題となる、本発明のその他の特徴および利点を説明する。当業者であれば、本明細書に開示した着想と特定の実施形態とを、変更または本発明と同じ目的を果たすための他の構造を設計するための基礎として容易に使用できることを理解するだろう。また、当業者であれば、このような等価構造はその最も広い形態においても本発明の趣旨および範囲を逸脱するものでないことを理解されるであろう。
【０００６】
以下で詳細な説明に着手する前に、本特許文献で使用されるいくつかの用語またはフレーズの定義を示すことが有利であろう。「含む」「〜成る」およびこれから派生した語は限定的でない包含を意味する；「または」という語は包含的であり、すなわち、および／またはを意味する；「関連した」「それと関連した」ならびにこれらから派生したフレーズは、含む、中に含まれる、相互に接続されている、包含する、中に包含されている、〜にまたは〜と接続する、〜にまたは〜と結合する、〜と通じている、協働する、交互配置する、並置する、近接している、〜とまたは〜に結び付けられている、有する、〜の性質を有する等を意味する；「コントローラ」という語は、ハードウェア、ファームウェア、ソフトウェア、またはこれらのうちの少なくとも２つの組み合わせのどれによって実施されていようと、少なくとも１つの動作をコントロールする任意のデバイス、システムまたはその一部を意味する。何か特定のコントローラに関連した機能は、局所的であれ遠隔的であれ、集中していてもよいし、分散していてもよいことに注意されたい。本特許文献全体を通じていくつかの語およびフレーズの定義が示されるが、当業者であれば、このような定義は、ほとんどではないにしろ、多くの場合、このように定義された語およびフレームの以前の例および将来の用法にも当てはまることを理解されるであろう。いくつかの語は非常に多様な実施形態を含んでいるが、添付された請求項はこれらの語を特定の実施形態に明示的に限定している。
【０００７】
本発明およびその利点をより完全に理解するために、添付した図面と共に後続の説明を参照されたい。図面では、同様の要素に同様の参照番号が付されている。
【図面の簡単な説明】
【０００８】
【図１】本発明のシステムおよび方法の実施形態が実現されるデータ処理システムのブロックダイアグラムである。
【図２】衝突の無い経路の例である。
【図３Ａ】２つの円柱の間の結合部での許容可能な交差である。
【図３Ｂ】無効な自己交差である。
【図４Ａ】２つのオブジェクト境界が重なっている場合の境界面である。
【図４Ｂ】１つのオブジェクトがもう１つの別のオブジェクト内に収容されている場合の閉じ込め状態である。
【図５】本発明の実施形態に従ったプロセスである。
【図６】前方拡張部の例である。
【図７】球体表現に接触している定義点と、円柱表現に接触していない定義点との例である。
【図８】前方拡張値または後方拡張値を有する、あるいは、前方拡張値および後方拡張値を有する定義点の例である。
【図９】背景ジオメトリに対する定義点間の衝突チェックである。
【図１０】最短経路上の衝突検査の例である。
【図１１】種々の選択条件によってモデリングされたパイプの例である。
【０００９】
詳細な説明
以下で論じる図１〜図１１と本明細書中の開示内容の原理を説明するために用いられる種々の実施形態は、単に説明のためのものであり、本発明の範囲を制限するものではない。当業者であれば、本発明の原理は適切に構成された任意のデバイスによって実現されることを理解されるであろう。以下では、説明のための実施例を参照しつつ、本出願の多くの革新的な思想を説明する。
【００１０】
定義
以下に、本特許出願において使用されている幾つかの技術用語の通常の意味を簡単に定義する（しかし、当分野の技術者であれば、コンテクストが別の意味を要しているか否か判別できるであろう）。さらなる定義は、標準的な技術辞典および機関誌において見出される。
【００１１】
ファセットデータ：ファセットデータは、幾つかのＣＡＤおよびＣＡＤ視覚化システムによって、ソリッドボディを記憶するまたはモデリングするために使用される。ファセットデータは三角形群（メッシュとも呼ばれる）から成る。これらの三角形が集合してファセットとなり、ソリッドボディに近似するサーフェスが形成される。
【００１２】
パイプ／チューブ：用語「パイプ」および「チューブ」は本明細書では全般的に相互交換可能に使用されており、どちらか一方の用語を使用することによって、他方の用語の使用も意図される。種々の実施形態では、パイプを、円柱の連続体としてモデリングおよび処理する。最終的にモデリングされたパイプはフィレット曲線を含むより詳細なモデルを含んでいてもよく、このフィレット曲線はパイプにおける継手、すなわち、曲がり継手または肘継手をモデリングする。以降の図面、殊に図１０は、種々の選択条件によってモデリングされたパイプの例を表している。非常にシンプルに実施される種々異なる実施形態では、全てのパイプは曲がり継手または肘継手を有していないものとして扱われている。
【００１３】
継手／結合部：継手または結合部は、パイプの方向変化を示す位置である。これらの用語は本明細書では全般的に相互交換可能に使用されている。有利な実施形態では、これらは、パイプラインどうしを結合する（端部と端部とを結合する）単なる点として扱われているが、他の実施形態では、顧客またはユーザはこの箇所で移行部を決めることができる。移行部がパイプ内の曲がり継手である場合には、このパイプは、曲げ機を用いて曲げられた配管材料部品である。また、別の可能な移行部として肘継手が挙げられるが、これはパイプの終端部上に挿入された別個の付属品である。
【００１４】
パイプおよびチューブは典型的に、ＣＡＤシステムにおいては、端と端とが接続された線と弧のセットとしてモデリングされる。ＣＡＤシステムのユーザはこれらの曲線を、種々のプロパティ（継手の半径およびパイプ材料等）およびこれらの曲線の定義点の位置を定義することによって作成する。パイプおよびチューブは或るアイテム（またはシステム）を、別のシステムまたはアイテムに接続する。これらのアイテムの例には、（支管を定めるための）Ｔ字管、ポンプまたはタンクが含まれる。
【００１５】
パイプの始点および終点は、終端アイテム（タンク上の注入口等）によって定義される。中間定義点の幾つかは、存在するエンティティ（隔壁を通るための弧状部分の中心等）を選択することによって特定される。他の中間定義点は、自由空間内で定められなければならない。基準ジオメトリがなく、ユーザがこの点の座標を「推測」しなければならない場合に、自由空間内で点を定めることは特に困難である。
【００１６】
さらにパイプの始めと終わりとの間に障害物がある場合には、ユーザが付加的な点を定義する必要がある。障害物を回避するために典型的に、障害物と接触または衝突しないパイプを定める定義点セットを得るまで、ユーザは繰り返し、こうした点を作成しなければならない。このプロセスでは、ユーザが配管経路を繰り返し修正および再検査する必要があるので、相当な量の労力を必要とする。
【００１７】
本発明は、衝突の無いパイプまたはチューブを生じさせる、自由空間にわたった中間定義点セットを自動的に定義するシステム、方法およびコンピュータプログラム製品を含む。本発明の方法は、これらの定義点を対話型環境において計算する。ここで時間量は、モデルの複雑さ（すなわち、障害物の数）に比例する。本発明の方法は、三次元ＣＡＤシステムにおけるＣＡＤファセットデータを使用して障害物を定義されたものとして処理する。
【００１８】
図１には、本発明のシステムおよび方法の実施形態を実現する、データ処理システムのブロックダイアグラムが示されている。図示されたデータ処理システムはレベル２キャッシュ／ブリッジ１０４に接続されたプロセッサ１０２を有しており、レベル２キャッシュ／ブリッジ１０４はローカルシステムバス１０６に接続されている。ローカルシステムバス１０６は例えば周辺機器相互接続（ＰＣＩ）アーキテクチャバスであってよい。また、図示の例では、メインメモリ１０８とグラフィックスアダプタ１１０もローカルシステムバスに接続されている。グラフィックスアダプタ１１０はディスプレイ１１１に接続されていてもよい。
【００１９】
ＬＡＮ／ＷＡＮ／ＷｉＦｉアダプタ１１２などの他の周辺機器もローカルシステムバス１０６に接続されていてよい。拡張バスインタフェース１１４はローカルシステムバス１０６をＩ／Ｏバス１１６に接続している。Ｉ／Ｏバス１１６はキーボード／マウスアダプタ１１８、ディスクコントローラ１２０およびＩ／Ｏアダプタ１２２に接続されている。ディスクコントローラ１２０をストレージ装置１２６に接続させることができる。ストレージ装置１２６は、あらゆる適切な機械によって使用可能なまたは読み取り可能な記憶媒体であってよい。この記憶媒体は、ＲＯＭまたはＥＥＰＲＯＭなどの不揮発性かつハードウェア記録型の媒体や、フロッピーディスク・ハードディスクドライブ・ＣＤＲＯＭまたはＤＶＤなどのユーザ記録型の媒体、ならびに、他の周知の光学的・電気的または磁気的媒体を含むが、これらに限定されない。
【００２０】
また、図示の例では、オーディオアダプタ１２４もＩ／Ｏバス１１６に接続されている。オーディオアダプタ１２４には、音声再生用にスピーカ（図示なし）を接続してもよい。キーボード／マウスアダプタ１１８は、マウス、トラックボール、トラックポインタなどのようなポインティングデバイス（図示なし）のための接続を提供する。
【００２１】
当業者は、図１に示されたハードウェアを特定の具現化に対して変更しうることを理解するであろう。例えば、光学ディスクドライブなどのような他の周辺デバイスを図示されたハードウェアに加えて、またはこれに代えて使用してもよい。図示された例は説明目的のためのみに与えられているものであり、本発明に関するアーキテクチャ上の限定を含意するものではない。
【００２２】
本発明の実施形態に従ったデータ処理システムはグラフィカルユーザインタフェースを用いたオペレーティングシステムを含んでいる。このオペレーティングシステムはグラフィカルユーザインタフェースに同時に複数のディスプレイウィンドウを提示することができ、各ディスプレイウィンドウは異なるアプリケーションまたは同じアプリケーションの異なるインスタンスへのインタフェースを提供する。ユーザはポインティングデバイスによってグラフィカルユーザインタフェース内のカーソルを操作することができる。所望の反応を起こさせるために、カーソルの位置を変えたり、および／または、マウスボタンのクリックのようなイベントを発生させたりしてもよい。
【００２３】
適切に修正するならば、様々な商用オペレーティングシステムのうちの１つ、例えばワシントン州レッドモンドのマイクロソフト社の製品であるマイクロソフトウィンドウズＴＭの１つのバージョンなどを使用してもよい。オペレーティングシステムは本発明に記載されている通りに修正または作成される。
【００２４】
ＬＡＮ／ＷＡＮ／ワイヤレスアダプタ１１２をネットワーク１３０（データ処理システム１００の一部ではない）に接続させることができる。ここでのネットワーク１３０は、公的もしくは私的なデータ処理システムネットワーク、または、インターネットを含む当業者に知られているネットワークの組み合わせであってよい。データ処理システム１００はネットワーク１３０を介してサーバシステム１４０と通信することができる。サーバシステム１４０もデータ処理システム１００の一部ではないが、例えば別個のデータ処理システム１００として実現することができる。
【００２５】
自由空間を通るパイプおよびチューブを定めるのは、非常に時間のかかる作業である。造船関連の顧客は殊に、配管システムを定めるのに長い時間を費やす。例えば船の重さの３分の１までが、配管システムから成る。狭い空間（エンジンブロック等）の場合には、ユーザが衝突の無い経路を定めるのは極めて困難である。本発明の実施形態には、パイプおよびチューブに対して衝突の無い経路を自動的に作成するツールが含まれる。
【００２６】
本発明の実施形態には、パイプまたはチューブに対して衝突の無い経路を見つけ出すシステムおよび方法が含まれる。このシステムおよび方法は、本発明において「クイックパス」とも称される。このプロセスは、幾つかの実施形態においてファセットジオメトリとしてモデリングされている障害物を検出し、このような障害物を回避する。また、特定の設計上の制約を最小化または充足することも試みる。したがって、本発明の実施形態は、パイプまたはチューブに対して有効な経路を作成する。得られる経路は、より広範囲のシステムとの関連においては全体的に最適ではないかもしれないが、そのような場合には、ユーザまたは設計者によって修正され、パイプを定めるために必要な労力が全般的に低減される。
【００２７】
幾つかの実施形態においてクイックパスは、有効な経路点セットを決定させる、２つの主要な制約セットを使用する。厳しい制約とは、得られる経路によって破られないことがクイックパスによって保証されている制約である。緩やかな制約とは、経路を探索している間、クイックパスが充足しようと試みるが、得られた経路によって充足されることが保証されていない制約である。またこれらの制約に対して付加的に、クイックパスは、得られるパイプ内の結合点の数ならびにパイプの全長を最小化することも試みる。
【００２８】
図２は、衝突の無い経路の例を示している。厳しい制約の１つは、得られる配管経路２００が障害物との衝突を有していない（無衝突経路である）ということである。障害物とは、３Ｄモデルで表される障害物２１０等である。クイックパスは、パイプを、円柱の連続体としてモデリングする。この円柱の直径は、ユーザによって特定された材料の直径と、ユーザによって定められたクリアランス値とを加算したものから成る。得られる経路は、これらの円柱と３Ｄモデルとの間に衝突を有していない。内側のソリッドボディはパイプ２２０の直径であり、外側のソリッドボディ２３０は、クリアランス値が足されたパイプの直径である。
【００２９】
厳しい制約のもう１つは、自己交差が無いということである。したがって、得られる経路は、連続している各円柱を結合する結合箇所を除いて、自身と交差しない。図３Ａは、２つの円柱間の結合部での許容される交差３１０を示している。図３Ｂは、経路点を定める際にクイックパスが許可しない自己交差３２０を示している。これは結合部で生じているのではない無効な自己交差である。
【００３０】
緩やかな制約には、パイプの各直線部分の最も短い長さである「最小直線長」と、得られるパイプにおいて許される継手または結合部の最大数である「継手の最大数」とが含まれる。
【００３１】
クイックパスは、得られる経路が３Ｄモデルで表されたあらゆるジオメトリと接触衝突しないことを確実にする衝突検出プロセスを使用する。この衝突検出プロセスは、接触および閉じ込めに対する衝突チェックをサポートする。閉じ込めとは、１つのオブジェクトが別のオブジェクト内に収容されている状態のことである。図４Ａは、２つのオブジェクト境界が４１０でオーバーラップする場合の接触を示しており、図４Ｂは、１つのオブジェクトが他方のオブジェクト内に収容されている場合の閉じ込めを示している。衝突検出システムは、ＣＡＤファセットデータに対する、円柱・球体・ブロックの衝突チェックをサポートする。
【００３２】
幾つかの実施形態では、衝突検出のためのデータ構造およびプロセスは、ＯＢＢツリーアルゴリズムに基づいている。このアルゴリズムは当業者には既知であり、例えばS.Gottschalk, M.Lin, D.Manocha, "OBB-Tree：A hierarchical structure for rapid interference detection" Proc.of ACM Siggraph'96, 1996の171頁〜180頁に記載されている。なお、上記文献は参照により本明細書に組み込まれる。ＯＢＢツリーは、ジオメトリを囲むボックスの階層を記憶する。ボックスによって囲まれる基本的なジオメトリは、ソリッド状のファセットデータのグループか、または球体や円柱等のベーシックな３Ｄ形状のグループのどちらでもよい。種々のクイックパスの実施形態は、その時点のモデルにおける全てのジオメトリを検査し、このジオメトリに対してＯＢＢツリー構造を作成することによって衝突検出システムを初期化する。このモデルにおけるジオメトリは「背景ジオメトリ」とされる。
【００３３】
衝突検出システムは、前景ジオメトリの各部分にわたって繰り返され、この前景ジオメトリと背景ジオメトリの各部分との間の衝突チェックを実施する。検査者は、この前景ジオメトリと背景ジオメトリの部分との間の衝突を見つけるとすぐに、この前景ジオメトリの全ての処理を停止する。
【００３４】
衝突チェックの第１の段階は、背景オブジェクトのセットにおいてジオメトリの各部分にわたって繰り返され、ＯＢＢツリーの階層を下ってＯＢＢ‐ＯＢＢ接触検査を実施することによって、前景ジオメトリと接触する可能性のあるオブジェクトを見つける。
【００３５】
第２の段階は、ＯＢＢ‐ＯＢＢ接触チェックによって除かれなかった、前景ジオメトリと背景ジオメトリとの間で低いレベルでの接触チェックを行う。この低いレベルでのジオメトリチェックは円柱‐円柱チェックおよび円柱‐三角形チェックを用いて実施される。このようなチェックは、例えば、M.Held, ERIT, "a collection of efficient and reliable intersection tests", Journal of Graphics Tools, Vol 2, issue 4:25-44, 1997に記載されている。この文献は当業者には公知であり、参照によって本明細書に組み込まれる。球体‐三角形検査は例えばE.Karabassi, G.Papaioannou, T.Theoharis "Intersection test for collision detection in particle sysytems", Journal of Graphics Tools, Vol 4, issue 1, 1999の25頁〜37頁における記載に従って実施される。この文献は当業者には公知であり、参照によって本明細書に組み込まれる。
【００３６】
次のステップでは、前景ジオメトリオブジェクトが背景オブジェクト内にあるか否か、または背景オブジェクトが前景ジオメトリオブジェクト内にあるか否かが判別される。このステップは、接触を有していない前景ジオメトリにおいてのみ実施される。すなわち、衝突無しで衝突検査をパスした前景ジオメトリである。閉じ込め検査では、単に、前景ジオメトリ内の幾つかの任意の点から幾つかの任意の方向へ向かう無限の放射が描かれる。この放射はその後、この前景ジオメトリを包含している可能性のある背景ジオメトリとの交差に対してチェックされる。この放射が奇数のアイテムと交差する場合には、前景ジオメトリは背景ジオメトリ内にある。その後、このチェックは背景ジオメトリ上の任意の箇所での点および前景ジオメトリと交差する放射によってのみ繰り返される。この簡単なチェックは、点が多角形内にあるか否かを求める、よく知られているレイキャスティングアルゴリズムに基づいている。このアルゴリムは例えばWikipediaの"Point in Polygon"に対する項目に記載されている。この記載は、出願の時点では、en.wikipedia.org/wiki/Point_in_polygonで見出される。
【００３７】
図５は、本発明の実施形態に従ったプロセスを示している。
【００３８】
クイックパスプロセスにおいて使用される幾つかの技術は、ロボットアプリケーションにおける経路計画用の幾つかのコンセプトと類似している。ロボット用に研究された種々の経路計画技術がある。これらは例えば、S.M.Lavalle "Planinng Algorithms " Cambridge University Press, Cambridge, UK , 1996に記載されている。この文献は当業者には公知であり、参照によって本明細書に組み込まれる。
【００３９】
クイックパスツールプロセスは、ロボット用の経路発見問題に対応可能である。ロボットは衝突を回避しながら、空間を通る自身の経路を見つけ出さなければならない。一般的なケースでは、ロボットはｄ次元の動きを有する（例えば１つの結合部を有するロボットの場合は９次元）。クイックパスプロセスにおいて、「ロボット」は３次元で自由な球体として考えられる。
【００４０】
本発明で使用される技術は、「確率的ロードマップ法：Probabilistic Roadmap Planners（PRM）」として知られているロボットアルゴリズムのサブセットに分類される技術に類似している。ＰＲＭシステムでは、モデルは連続空間から非連続空間へと変換される。多くのＰＲＭプランナーは、空間にわたって動かなければならないオブジェクト（「ロボット」）の種々の配向と位置を計算し、これらの配向と位置を動きによって接続することによってこれを行う。これによって、グラフの頂点はロボットの向きと位置とを頂点とし、各位置間のロボットの動きを辺としたグラフが形成される。その後、グラフ理論からの種々のアルゴリズムが使用されて、ロボットの初期の配置／位置から、ロボットの最終的な配置／位置までの有効な動きのセットが計算される。
【００４１】
クイックパスプロセスの幾つかの側面は、レイジーＰＲＭアルゴリズムの修正および特定を用いて実現される。このロードマップは、例えば、R.Bohlin, L.E.Kavraki "A lazy PRM for single query path planinng" Proc.of the IEEE Int.Conf.on Robotics and Automation, 2000に記載されている。この文献は当業者には既知であり、参照によって本明細書に組み込まれる。このレイジーＰＲＭアルゴリズムは、経路が見つかるまで単に（費用のかかる）衝突チェックを回避することによって、衝突チェックの数を最小化することを試みる。レイジーＰＲＭアルゴリズムは、まず、ロボットのランダムな配置のグラフを作成する。ここでは、これらの配置の間がランダムに接続されている。その後、レイジーＰＲＭアルゴリズムは経路を計算し、この経路に沿ってのみ衝突を検査し、この経路から、衝突を引き起こす配置を除去する。このプロセスは、衝突の無い経路が発見されるまで繰り返される。
【００４２】
衝突チェックが、有効経路の計算において最も費用のかかるステップであるときには、レイジーＰＲＭアルゴリズムの目標は、衝突チェックを回避することである。モデルが複雑な場合、レイジーＰＲＭアルゴリズムは、処理されたグラフを多数回繰り返して横切る。これによって衝突検出から経路横断までの計算が強いられる。本発明のクイックパスプロセスは、この問題を回避するために幾つかの発見法を使用し、全体的な計算時間を短くすることができる。
【００４３】
概略的に説明したように、本発明のプロセスは以下のようなステップを含む。すなわち
・少なくとも、パイプ直径に等しい球体を収容するのに充分な余地を周囲に有している、空間内の幾つかの点をサンプリングするステップ；
・これらの点を接続して、グラフを形成するステップ；
・始点から終点までのグラフを通る経路を見つけるステップ；
・始点から終点までこの経路に沿って衝突をチェックし、このグラフから、背景ジオメトリと衝突する（経路上の）辺を除去するステップ
を含む。衝突がある場合には、プロセスは新たな経路を見つけながら、繰り返される。
【００４４】
図５に示されたプロセス５００を参照されたい。クイックパスプロセスの第１のステップ５１０は、ユーザからの入力を受け取ることまたは設定ファイルからロードされた入力を受け取ることである。この入力によって、少なくとも、始点および終点、経路内に含めたいあらゆる中間点、および、パイプの直径が指定される。ユーザは、各点での前方拡張部または後方拡張部を指定するオプションを有している。拡張部により、衝突をチェックしなくてよい領域が定められる。得られる経路に接触するけれどもその接触が許容されている容器等の面との衝突に関して、クイックパスの探索が阻止されるので、これらの拡張部は有用である。
【００４５】
図６は、前方拡張部の例を示している。この図では、経路６２０の始点で拡張部６１０が定められている。この拡張部により、始点に配置されている容器６３０での接触が回避される。
【００４６】
種々の実施形態では、ユーザはクイックパスに対して以下のデータを定めることができる。
【００４７】
マークされるアイテム（必須）：少なくとも１つの実施形態において、プロセスの後続のステップを実行する前に、ユーザによって指定されなければならない。
【００４８】
定義点（必須）：ユーザは、同一でない少なくとも２つの点を指定しなければならない。しかし、所望の点全てを指定してもよい。
【００４９】
拡張方向および前方拡張部の長さまたは後方拡張部の長さ：ユーザはこれらを任意で、あらゆる定義点において指定することができる。
【００５０】
パイプの材料または直径（必須）：パイプの外径は、得られる経路が衝突を有していないように強制するために使用される。
【００５１】
クリアランス：クリアランスは、パイプの軸線周辺の領域のうち衝突があってはならない付加的な領域を定める。
【００５２】
最小直線長および継手の最大数：上述した通りである。
【００５３】
定義点に対する方向をユーザが指定しない場合には、クイックパスは自動的に、定義点を定めるためにユーザによって選択されたジオメトリに基づいて拡張方向を定める。例えばユーザが或る線を選択した場合には、自動拡張方向はこの線を軸線としたものとなる。ジオメトリが軸線を有していない場合（またはこの点が自由空間内にある場合）、クイックパスはこの定義点と次の定義点（最後の定義点に対する先行する定義点）との間の方向づけを使用する。自動拡張では、前方拡張値および後方拡張値に０が用いられる。
【００５４】
本発明のプロセスにおける次のステップ５２０では、全般的に始点と終点との間にある、付加的な中間定義点として使用されうる標本点が決定され、標本点の配置および配向の決定が経路計画に使用され、これらの標本点は、得られる経路、および、経路が見つけられるか否かに影響を与える。標本点の位置を選択するために使用される種々のサンプリング方法がある。クイックパスは、パイプ／チューブを作成するために特別に設計された幾つかの新たなサンプリングストラテジを使用する。
【００５５】
クイックパスの場合には、「ロボット」は球体としてモデリングされる。これによって、配向を考慮しなくてよいので、３Ｄ空間内の適切な点へのサンプリングが低減される。見つけるべき経路は衝突を有していない経路であるから、球体は、背景ジオメトリと接触することなく開始定義点から終端定義点まで動くことができるはずである。
【００５６】
有利には、レイジーＰＲＭアルゴリズムを用いて、このシステムはグラフを構築する。このグラフは標本点、始点および終点およびあらゆる他の定義点を頂点として含んでおり、さらに、これらの頂点を接続する複数の辺を含んでいる。ここで、標本点とこれらの標本点をつなぐ辺とは、衝突を有していないものとみなされる。密なモデルの場合には、グラフを見つけること、衝突を見つけること、グラフから辺を除去することを相当数繰り返すこととなる。クイックパスは、全ての標本点が無衝突であることを保証することによって、経路発見繰り返し数を低減させる。このアップフロント衝突チェックは、密なモデルにおける無効経路の数を格段に低減させる。ファセットデータと球体との衝突チェックが非常に迅速に行われるオペレーションであるとき、この衝突チェックは非常に迅速に行われる。
【００５７】
クイックパスサンプリングストラテジは、４つの段階において、空間内の無衝突標本球体（３Ｄ点として格納されている）のリストを作成することから成る。
【００５８】
初期の点のリストは、定義点から成る。球体が定義点で現存するモデルと接触しそうなときであっても、これらの点は無衝突であると定義される。この点で始まる、場合によって存在するパイプまたはチューブが球体よりはむしろ円柱の頭部であるような場合、実際には接触は存在しない。図７は、球体表現７１０に接触している定義点と、円柱表現７２０に接触していない定義点とを示している。
【００５９】
ユーザが定義点で前方拡張値または後方拡張値を定めると、この定義点は新たな点と置き換えられる。この新たな点は、拡張方向に沿って、ユーザによって特定された拡張距離だけ定義点からオフセットされている。クイックパスは、定義点と拡張点との間の円柱部分を、無衝突部分として扱う。
【００６０】
クイックパスは、入力定義点（またはこれと置き換えられた拡張点）の各対の間の経路を計算する。これは全般的に、始点と終点の間のグラフを通っている。図８は、前方拡張値または後方拡張値または前方拡張値および後方拡張値を伴う定義点の例を示している。この例では、ユーザは点Ａ，Ｂ，Ｃを選択し、前方拡張値８１０をＡおよびＢで定め、後方拡張値８２０をＢおよびＣで定めている。クイックパスは、点Ａ１と点Ｂ１との間の経路８３０、および、点Ｂ２と点Ｃ１との間の別の経路８４０を求める。
【００６１】
回復点はいくつかの異なった発見法を使用して計算される点である。これらの発見法は、テンプレート経路またはプロトタイプ経路のセットを定め、その後、クイックパスはこのテンプレート経路に沿って点をサンプリングする。クイックパスは、上述した各定義点と関連する拡張方向の対を使用して各テンプレート経路を計算する。
【００６２】
種々の実施形態で使用されるテンプレート経路には３つの基本的なタイプがあり、すなわち、直線テンプレート経路、交差テンプレート経路および基本テンプレート経路である。クイックパスは、各経路を、初期の点ｐ１，ｐ２、拡張方向ｖ１，ｖ２、オフセット値ｄの入力および入力方法を定めることによって計算する。各テンプレート経路は、まず、
ｏ１＝ｐ１＋ｄ＊ｖ１
ｏ２＝ｐ２＋ｄ＊ｖ２
のように、拡張方向に沿ったオフセット値を各入力点に加える。この方法はその後、オフセット点間の経路の計算にどのアルゴリズムが使用されるのかを求める。帰還テンプレート経路は、一致する点をまったく含んでいない。
【００６３】
直線テンプレート経路は、単に、オフセット位置どうしを直線でつなぐ。したがって、各直線経路はｐ１，ｏ１，ｏ２，ｐ２から成る。
【００６４】
交差テンプレート経路は、単に、２つの無限の線（ｏ１，ｖ１）および（ｏ２，ｖ２）の交点ｉ１，ｉ２を探索する。このテンプレート経路はこの場合にはｐ１，ｏ１，ｉ１，ｉ２，ｏ２，ｐ２から成る。２つの線の間に交点が無い場合にはクイックパスはこの経路を放棄する。交点は、線（ｏ１，ｖ１）と線（ｏ２，ｖ２）との間の最も短い線を定める点である。このような点を識別する１つの方法は、出願時に知られているかぎりでは、Paul Bourke,"The shortest line between two lines in 3D" local.wasp.uwa.edu.au/~pbourke/geometry/lineline3d/"に記載されている。この文献は当業者には公知であり、参照によって本明細書に組み込まれる。
【００６５】
基本テンプレート経路は、基本方向Ｘ，Ｙ，Ｚを用いて２つの新たな位置を計算し、各入力点のオフセット位置をつなぐ。このタイプのテンプレート経路には６個のサブプロセスが存在し、各サブプロセスは基本方向の適用される順序を定義している。例えば、サブプロセス"ＸＹＺ"の場合、最初にＸ方向、次にＹ方向、最後にＺ方向が適用される。計算されるテンプレート経路はｐ１，ｏ１，ｃ１，ｃ２，ｏ２，ｐ２であり、そのうちｃ１，ｃ２を次の表１に示す。
【００６６】
【表１】
2011526389.tif 000003
【００６７】
クイックパスは、種々の回復プロセスおよび回復サブプロセスを巡回することにより、回復経路を反復計算する。プロセスごとに、クイックパスは、拡張ベクトルの組み合わせ（ｖ１，ｖ２），（−ｖ１，ｖ２），（ｖ１，−ｖ２），（ｖ１，−ｖ２）を用いて回復経路を計算する。それぞれの組み合わせにつき、クイックパスは、ｐ１からｐ２までの距離に現在の反復回数ｋを乗算してこれを反復の最大数ｍで除算した値に等しい拡張値を用いて回復経路を計算する。このアルゴリズムを、次の表２のアルゴリズム２．１（擬似コード）に示す。
【００６８】
【表２】
2011526389.tif 000004
【００６９】
クイックパスは、テンプレート経路の位置に対して軸線方向に整合されたバウンディングボックスを計算し、衝突の検査を、当該のバウンディングボックスに交差するかまたは当該のバウンディングボックス内に含まれる背景ジオメトリのみに制限する。このステップにより、衝突を検査すべき背景ジオメトリの量が低減される。というのは、計算されたすべての経路がバウンディングボックス内に入る背景ジオメトリのみを検査すればよいからである。
【００７０】
クイックパスは、テンプレート経路にしたがって定義された線のそれぞれに沿って、固定数の標本点（この実施例では１００個の標本点）をサンプリングする。各標本点について球体としての背景ジオメトリに衝突するかどうか検査が行われ、衝突を有さない点のみが保持される。
【００７１】
グリッド方式の標本点：テンプレート経路に沿った標本点が求められ、その後、クイックパスが、定義点を中心とした３Ｄグリッドに沿って標本点を計算する。ここでのグリッドは、固定数の標本点を含み、Ｘ方向、Ｙ方向およびＺ方向での最大の広がりに基づく差Δを標本点の数の３乗根で除算した値を用いて計算される。
【００７２】
さらに、クイックパスは、回復経路の点に対して計算された各テンプレート経路の線がグリッドのＸＹ平面・ＸＺ平面・ＹＺ平面に交差する標本点を記憶する。
【００７３】
ランダム方式の標本点：先行のステップで多数の標本点が計算される。先行のステップの標本点は完全に決定論的である（つまり、同じ入力がつねに同じ標本点の組を生じさせる）。決定論的な標本点によりきわめて単純な経路（テンプレート経路に沿った直線、グリッド平面に沿った線など）が定義され、これらは直線的な配管経路を形成するのに役立つ。しかし、これらの標本点は、込み入ってごちゃごちゃしたモデル内で１つの経路を発見するには充分でない。標本点の収集が充分に密でない場合、あるいは、先行のステップで形成された標本点がほとんど有効でなくなるほど障害物にぶつかる場合には、帰還経路が最適でなく、つまり、計算された管があまりにも長く複雑であるかまたは経路が全く発見できないことを意味する。ランダムサンプリングプロセスの詳細およびランダム点を利用すると密なモデルで有利である理由は、当業者にはよく知られており、例えば、N.M.Amato, Y.Wu, "A randomized roadmap method for path and manipulation planning", IEEE Int.Conf.Robot.&Autom, 1996の113頁〜120頁に説明されている。この文献は参照により本明細書に組み込まれるものとする。
【００７４】
クイックパスは、上述のようにして計算されたバウンディングボックスの内側の多数のランダムな標本点を選択し、各標本点につきバウンディングボックス内の背景ジオメトリに衝突するか否かを検査する。別の実施例では、クイックパスにより、少なくとも２０００個の衝突のないランダムな標本点のリストが得られることが保証される。
【００７５】
図５に戻ると、ステップ５３０で、データ処理装置は標本点を接続するグラフを形成する。クイックパスは標本点をつないでグラフデータ構造を形成するために幾つかの発見法を利用している。このグラフは、メモリ利用量が過度に大きくなることを回避するために小さく保たれなければならず、また、最短経路探索に適するものでなければならない。
【００７６】
クイックパスは、第１の発見法によって、各標本点を近傍の別の標本点に接続することを試みる。各標本点は、近傍のｋ個（この実施例ではｋ＝５）の点に接続されるか、または、標本点を中心とし、管の直径（または、管の直径にクリアランスを加えた値）に等しい直径を有する球体内の全ての点に接続される。クイックパスは、標本点を、これら２つの組、すなわち、近傍のｋ個の点の組または球体内の全ての点の組のうち、数の大きいほうの組の点へ接続する。標本点をできるだけ密に接続することにより、クイックパスは、配管経路を求める際に小さなインクリメントステップを行うだけでよい。近傍のｋ個の点または球体内の点を探索するのに適したアルゴリズムは当業者にはよく知られており、例えば、D.Mount, S.Arya, ANN:A Library for Approximate Nearest Neighbor Searching, www.cs.umd.edu/~mount/ANN/に説明されているので参照されたい。
【００７７】
第２の発見法は、各標本点を少なくともｊ個（この実施例ではｊ＝１０）のランダムな標本点とつなぐ手法である。当該のランダムな点はこれまで標本点とつながれていなかった点である。ランダムな接続により、クイックパスは、距離の離れた標本点を発見するための大きなインクリメントステップを行って、僅かなステップ数で終点まで至る経路を発見できる。
【００７８】
ついで、クイックパスは、定義点の組をそれぞれつなぐ。定義点のあいだに障害物が存在しなければ、帰還経路は単純に、定義点をつないだ線となる。定義点のあいだの辺を加算していくことにより、グラフ全体を探索しなくとも、クイックパスが１つの線を発見することが保証される。
【００７９】
クイックパスが形成する辺の最後の組は、回復点のステップで計算された標本点とｍ個（この実施例ではｍ＝２０）のランダムな他の回復点とのあいだ、および、定義されたそれぞれの点までのあいだに存在する。これらの追加の接続により、クイックパスは、回復経路のステップで計算されたテンプレート経路にいっそう良く似た経路を探索することができる。
【００８０】
ステップ５３０でグラフが形成された後、ステップ５４０で、クイックパスは、定義点に接続された全ての辺を検査する。クイックパスは、管の直径にクリアランスを加えた値に等しい直径を有する円柱を定義点と辺によって定められる他の点とのあいだに形成することにより、この円柱が背景モデルジオメトリに衝突するかどうかを各エッジについて検査する。クイックパスは、定義点に接続された全ての辺についての衝突検査を行い、グラフを通る少なくとも１つの経路を発見しようとする。
【００８１】
１つまたは複数の定義点に接続された全ての辺について衝突が存在する場合、定義点のあいだに衝突のない経路を形成することができない。定義点に接続された全ての辺を検査することにより、ユーザが或る閉じた領域の完全な内部の或る点（例えば取り付け部品の中心または閉じた室内の中央）を選択してしまい、後続のステップで経路探索が反復されて検出に長い時間がかかってしまうことが迅速に検出されるので、有利である。
【００８２】
図９には衝突検査の実施例が示されている。この実施例では、データ処理装置は、背景ジオメトリボックスモデル９２０内の第１の定義点９１０から他の定義点までの経路に衝突が存在するか否かを検査する。図示されているように、定義点９３０へ至る経路９４０に沿って衝突が存在しており、これは経路９４０がボックス９２０に交差しているからである。また、他の定義点への経路にも同様に衝突を有するものがある。データ処理装置は、定義点９５０へ至る経路９６０が衝突のない有効な経路であることを発見する。このことはボックス９２０内で当該の経路９６０が穴９７０を通り抜けていることから明らかである。
【００８３】
或る定義点から出る辺のうち衝突のない辺が１つも存在しない場合、例えば、図９のボックス９２０に穴９７０が存在しない場合、可能な経路は存在しないことになり、ステップ５５０でデータ処理装置はユーザにその旨を報告し、それ以降の処理を停止する。これにより、さらなる利点として、クイックパスが検査してしまいかねない無効な潜在経路が低減される。
【００８４】
グラフ内の経路の探索
或る実施例では、グラフを通る最短経路を探索するため、周知のＡ＊アルゴリズムが用いられる。このＡ＊アルゴリズムは、出願時に知られているかぎりでは、ウィキペディアのA*Search Algorithm（en.wikipedia.org/wiki/A*_search_algorithm）に説明されている。この場合、最短経路とは、必ずしも最短長さを有する経路でなく、多くの緩やかな制約を満足する経路のうちできるかぎり短い経路のことである。最短経路探索の他の既知のアルゴリズム、例えばダイクストラアルゴリズム、ＩＤＡ＊，ＳＭＡ＊などのＡ＊アルゴリズムのバリエーションもクイックパスプロセスで利用することができる。
【００８５】
クイックパスの用いる発見法は、単純に、経路の最後の頂点が直接に標本点の終点に接続されていると見なして経路に適用される費用関数である。これを次に説明する。
【００８６】
或る経路の費用は、
・現在の経路の長さを２つの定義点間の距離で除算し、任意の重み値ｗ１を乗算した値
・現在の経路の継手の数を継手の最大数で除算し、任意の重み値ｗ２を乗算した値
［許容される継手の最大数が０のとき、継手の数は０として扱われる。］
・最小直線長よりも小さい長さを有する経路の線分の数と任意の誤り係数ｅ１とを乗算した値
［経路内に同一線上の点が存在する場合、線分は２つ以上の点を含んでよい。］
・上述した、経路内の自己交差の数と任意の誤り係数ｅ２とを乗算した値
の和である。
【００８７】
種々の実施例において、重み値ｗ１，ｗ２は双方を加算して１．０以下とならなければならない。これらの重み値により、経路が自己交差などの厳しい制約を破らなければ、経路の全費用が１．０以下となることが保証される。完全な経路とは、２つの定義点を直線でつないだ経路であり、費用０である。クイックパスプロセスの或る実施例ではｗ１＝ｗ２＝０．５であり、２つの重み値が等しい値へ近づくと、経路の長さおよび継手の数が低減される。
【００８８】
種々の実施例において、誤り係数ｅ１，ｅ２は１．０以上となる。これにより、経路が制約を破っていれば費用が１．０を上回る。誤りが大きくなるにつれて、経路の費用が大きくなり、より望ましくないものとなる。クイックパスプロセスの或る実施例ではｅ１＝ｅ２＝１．０である。
【００８９】
当該の費用関数には幾つかの重要な特徴がある。第１の特徴は、当該の費用関数が管の全長を最小化するように機能することである。管が短ければ短いほど、ふつう、製造にかかる費用も小さくなる。管の長さの最小化は、"完全な"管の長さ（直線状の管の長さ）を経路の長さで除算することによって得られる。経路が長くなるにつれてこの値は小さくなる。費用関数はこの値を１．０から減算して用いるので、この値が小さくなるにつれて、経路の値は１．０に近づくことになる。
【００９０】
長さを最小化するため、費用関数は継手の数の低減を試みる。経路内の継手の数がユーザの定義した継手の最大数よりも大きい場合、当該の項は（重み係数ｗ２が乗算されて）１．０よりも大きくなり、経路の費用は潜在的に１．０よりも大きくなりうる。
【００９１】
継手の最大数が超過されているのに費用が１．０より小さいケースもありうるが、このケースは上述したようにクイックパスアルゴリズムの許容可能条件である。
【００９２】
最小直線長の超過および自己交差の数のいずれか一方が０でない場合、経路の費用は自動的に１．０を上回る。これらの制約が破られると大きな費用が発生し、クイックパスがこうした経路を選択する確からしさが低下する。また、クイックパスは、グラフ内の頂点へ至る最短経路としての経路どうしが遭遇する場合、これらの経路をスキップすることによって、自己交差を有する経路を消去する（クイックパスは２番目に短い経路を選択する、など）。
【００９３】
最短経路の検査
クイックパスがいったん最短経路を発見すると、先行のステップにより、当該の経路が所望の定義点から始まって自己交差なしに所望の定義点で終わることが保証される。先行のステップ５４０で経路を全く発見できなかった場合、クイックパスはステップ５５０で処理を停止し、ユーザにエラーを報告する。
【００９４】
クイックパスは、最短経路における各線分を表す３Ｄの円柱を形成する。この場合、クイックパスは、ステップ５６０で、３Ｄの円柱の連続体と、他のオブジェクトモデルを含む背景ジオメトリとのあいだの衝突を検査する。衝突を有する辺は"無効"とマークされ、経路探索ステップで無視される。衝突を有さない辺は"検査済"とマークされ、衝突検査プロセスで２回検査されることはない。
【００９５】
最短経路の辺について衝突検査が終了した後、クイックパスは第２の衝突検査を行う。当該の第２の衝突検査はクイックパスが先行の衝突検査で衝突を見出した辺の各頂点につながる全ての辺に対して行われる。当該の追加的な第２の衝突検査により、最短経路探索アルゴリズムの続く経路探索で発見されうる行き止まりの経路が除去される。
【００９６】
或る頂点が最短経路上にあり、衝突が当該の頂点で起こっている場合、最短経路アルゴリズムは次の探索で当該の最短経路上の当該の頂点を見出す可能性が高い。第２の衝突検査により、ステップ５７０でグラフ内のもとの最短経路に近接する多数の無効な経路が除去され、クイックパスの検査すべき潜在経路の数がいちじるしく低減される。
【００９７】
図１０には追加的な第２の衝突検査による利点の例が示されている。ここでは、示された最短経路が衝突を有している。この場合、衝突を有する辺１０２０を除去すれば、最短経路探索アルゴリズムが破線で示された衝突を有する辺１０１０を下方へトラバースすることが回避される。図１０では、最短経路は実線で示されており、第２の経路は破線で示されている。
【００９８】
最短経路内のいずれかの辺が衝突を有する場合、クイックパスは、衝突検査の全てを実行した後、ステップ５４０に戻って最短経路探索アルゴリズムを再び開始する。このプロセスは、クイックパスが衝突のない経路を発見するか、または、最短経路探索アルゴルズムが経路を全く発見できないことが明らかとなるまで続けられる。
【００９９】
クイックパスプロセスの結果
クイックパスは発見されたエラーをユーザに報告する。種々の実施例において、２つのエラー条件、すなわち、或る定義点の周囲に充分な自由空間がないこと、および、定義点のあいだに経路が発見できなかったことのみがユーザに報告される。
【０１００】
データ処理装置は、ステップ５８０で、最短経路を求める個別のプロセスを実行する。クイックパスは、次に、ステップ５９０で、同一線上の点が除去されるよう、衝突のない経路を処理し、当該の経路を有効な径路と識別して、パイプまたはチューブをモデリングするためのＣＡＤ表示を作成する。管のＣＡＤ表示はＣＡＤシステムのユーザによって修正可能であり、必要に応じて、所望の管モデルを得ることができる。
【０１０１】
クイックパスは、パイプまたはチューブの定義のためにユーザに要求される労力の量を低減することにより、パイプまたはチューブの定義の問題を解決する。小さな労力で、ユーザは入力した制約（始点・終点・クリアランスなど）に適合する初期のチューブまたはパイプを得ることができる。多くのケースで、形成されたパイプまたはチューブがユーザに受け入れられる。形成されたパイプまたはチューブがユーザにとって受け入れがたいものである場合、ユーザは、編集用の既存のＣＡＤツールを用いてこれらのパイプまたはチューブを編集することができる。
【０１０２】
図１１には、種々の選択条件によってモデリングされたパイプの例が示されている。この図では、デフォルトの結合部を有するパイプ１１１０と、曲がり継手を有するパイプ１１２０と、肘継手を有するパイプ１１３０とがモデリングされている。
【０１０３】
米国特許第７４４４２６９号明細書には、大局的に適切な管を発見しようとするルーティング方法が説明されている。このルーティング方法は、障害物（例えばブロック）の限定されたセットしかサポートしておらず、ユーザにこれらの障害物の入力を要求する。しかも、この場合、障害物の数が大きくなるとアルゴリズムの動作時間はきわめて長くなってしまう。
【０１０４】
当業者であれば、上述した有利なクイックパスプロセスで使用しているレイジーＰＲＭアルゴリズムに代えて種々の経路計画アルゴリズムを利用できることは、容易に理解されるはずである。レイジーＰＲＭアルゴリズムを他のアルゴリズムに置換しても、クイックパスによって得られる結果（すなわち得られる経路）が必ず変化するというわけではない。ＰＲＭアルゴリズムには初期のグラフを形成するのに多くの時間を必要とするものが多い。なぜなら、辺をグラフ内に受け入れる前に当該の辺の有効性を確認しなければならないからである。
【０１０５】
他のＰＲＭアルゴリズムとして、S.M.LaValle, Rapidly-exploring random trees: A new tool for path planning., TR98-11, Computer Science Dept., IowaStateUniv., Oct.1998に道路地図のグラフをリアルタイムで形成する方法が説明されており、当業者によく知られている。この方法によれば、グラフ形成中に目立つ誤りが消去される。しかし、当該のアルゴリズムで得られる結果は費用や取り扱われる制約の低減に適さないことが多い。
【０１０６】
また、当業者は、"力ずくの"方法とされる他の経路探索法が存在することを容易に理解できるであろう。こうしたアルゴリズムは、大きな問題を個別のタスクへ分割して解を得ようとするものでなく、とにかく空間を連続的に探索して解を得るものである。これらの手法は、典型的には、何らかの手段によって（例えばランダムに、あるいは、決定論的に）仮定経路を形成し、当該の経路が衝突を有するかどうかを検査し、複数の基準を用いて、仮定経路の修正をさらに反復する必要がある。例えば、これらの手法のなかには、遺伝的アルゴリズムを利用して、１つまたは複数の検査経路をプロセス反復のたびに修正するものがある。また、単独の仮定経路を定義し、当該の仮定経路を反復しつつ修正して、反復のたびに制約を評価するものもある。これらのバリエーションはクイックパスプロセスよりも低い費用の経路を発見できる可能性を有してはいるが、小さなモデルであっても典型的にはきわめて多数の反復が必要であり、反復のたびにきわめて多数の計算（費用の評価、経路の衝突検査、次のステップの判別など）が必要となる。
【０１０７】
当業者は、簡単化のために、本発明での利用に適したデータ処理装置の構造および演算動作のすべてを図示し説明したわけでなく、むしろ、本発明独自の特徴または本発明の方法の理解にとって必須の特徴のみを図示し説明したことを理解されたい。データ処理装置１００の残りの構造および演算動作は従来のまたは現行のデータ処理装置に準じるものとする。
【０１０８】
本発明を機能的装置について説明したが、本発明の少なくとも一部の機能を機械またはコンピュータの利用可能な媒体または読み出し可能な媒体に記憶される種々の命令の形態で実現してもよいことを理解されたい。本発明の方法は、各ステップを実行するための命令や信号を記憶した媒体の特定のタイプに関係なく適用可能である。機械またはコンピュータの利用可能または読み出し可能な媒体の例として、ＲＯＭまたはＥＥＰＲＯＭなどの不揮発性かつハードウェア記録型の媒体や、フロッピーディスク・ハードディスクドライブ・ＣＤＲＯＭまたはＤＶＤなどのユーザ記録型の媒体が挙げられる。
【０１０９】
本発明を実施例に則して説明したが、当業者であれば、本発明の範囲から離れることなく、上述した実施例に対して種々の修正・代替・変更などを加えることができることは明らかである。
【０１１０】
上述した個々の要素・ステップ・機能は特定の要素・ステップ・機能への限定を意味するものではなく、特許請求の範囲の特徴をサポートするためのものである。本発明は特許請求の範囲によって定められる。また、特許請求の範囲のいずれの請求項も、分詞を用いた「〜するための手段」という表現を使わないかぎり、米国特許法第１１２条第６段落の問題を誘起するものではない。
【図１】
2011526389.tif 000005
【図２】
2011526389.tif 000006
【図３Ａ】
2011526389.tif 000007
【図３Ｂ】
2011526389.tif 000008
【図４Ａ】
2011526389.tif 000009
【図４Ｂ】
2011526389.tif 000010
【図５】
2011526389.tif 000011
【図６】
2011526389.tif 000012
【図７】
2011526389.tif 000013
【図８】
2011526389.tif 000014
【図９】
2011526389.tif 000015
【図１０】
2011526389.tif 000016
【図１１】
2011526389.tif 000017
【国際調査報告】
2011526389.tif 000018
2011526389.tif 000019