(57)【要約】      （修正有）【課題】機械部品を表す３Ｄモデル化オブジェクトを含んだデータベースのクエリを実行するための方法、データベース、可読記憶媒体、システム、およびプログラムを提供する。【解決手段】機械部品を表す３Ｄモデル化オブジェクトを含むデータベースにクエリを実行するための、入力３Ｄモデル化オブジェクトのためのあらかじめ定められた形状記述子の値に対する類似性基準を含んだクエリを提供するステップＳ１と、クエリの結果として、それぞれの３Ｄモデル化オブジェクトのためのあらかじめ定められた形状記述子の値が類似性基準を関連する範囲に基づいて、データベースのそれぞれの３Ｄモデル化オブジェクトを返すステップＳ２とを含む。【選択図】図１
2016224944.tif 000002
【特許請求の範囲】
【請求項１】
機械部品を表す３Ｄモデル化オブジェクトを含むデータベースにクエリを実行するためのコンピュータにより実施される方法であって、
−  入力３Ｄモデル化オブジェクトのためのあらかじめ定められた形状記述子の値に対する類似性基準を含むクエリを提供するステップ（Ｓ１）と、
−  前記クエリの結果として、前記データベースのそれぞれの３Ｄモデル化オブジェクトを返すステップ（Ｓ２）であって、それぞれの３Ｄモデル化オブジェクトは、前記それぞれの３Ｄモデル化オブジェクトのための前記あらかじめ定められた形状記述子の前記値が前記類似性基準を関連する範囲に基づいて返される、ステップと
を含み、
・  前記データベースの前記３Ｄモデル化オブジェクトおよび前記入力３Ｄモデル化オブジェクトは、少なくとも３Ｄメッシュによってそれぞれ定義され、３Ｄモデル化オブジェクトの前記３Ｄメッシュは、頂点と、前記頂点を接続する辺とを有し、前記頂点および前記辺は、前記３Ｄモデル化オブジェクトによって表される前記機械部品のエンベロープを表す面を形成し、
・  それぞれの３Ｄモデル化オブジェクトのための前記あらかじめ定められた形状記述子の前記値は、三面体を有する軸系の集合を含み、軸系の前記集合は、前記それぞれの３Ｄモデル化オブジェクトの前記３Ｄメッシュのそれぞれの頂点と、前記それぞれの３Ｄモデル化オブジェクトの前記３Ｄメッシュのそれぞれの面とから成るペアの集合と全単射の関係であり、それぞれの軸系の軸は、前記それぞれの頂点における、前記それぞれの頂点に接続される前記辺の方向に、前記それぞれの頂点における、前記３Ｄモデル化オブジェクトによって表される前記機械部品の前記エンベロープに垂直な方向に、および前記機械部品の外側に対応する前記面の向きに基づいて方向付けされ、
・  前記あらかじめ定められた形状記述子の第２の値に対する前記あらかじめ定められた形状記述子の第１の値の類似性は、同じ相似変換を法として、前記あらかじめ定められた形状記述子の前記第２の値の軸系の前記集合が、前記あらかじめ定められた形状記述子の前記第１の値の軸系の前記集合に照合する範囲に次第に左右される
ことを特徴とする方法。
【請求項２】
前記あらかじめ定められた形状記述子の前記第２の値の軸系の前記集合が、前記あらかじめ定められた形状記述子の前記第１の値の軸系の前記集合に照合する前記範囲は、所与の相似変換型に対してあらかじめ定められた方法で評定されることを特徴とする請求項１に記載の方法。
【請求項３】
前記あらかじめ定められた形状記述子の前記第２の値のそれぞれの軸系に関連する前記面が、前記所与の相似変換を法として、前記あらかじめ定められた形状記述子の前記第１の値のそれぞれの軸系に関連する前記面に照合する場合に限り、前記あらかじめ定められた形状記述子の前記第２の値の前記それぞれの軸系は、前記あらかじめ定められた形状記述子の前記第２の値の前記軸系の前記集合が、前記あらかじめ定められた形状記述子の前記第１の値の軸系の前記集合に照合する前記範囲において、前記所与の相似変換重みを法として、前記あらかじめ定められた形状記述子の前記第１の値の前記それぞれの軸系に照合するということを特徴とする請求項２に記載の方法。
【請求項４】
前記あらかじめ定められた形状記述子の前記第２の値の軸系の前記集合が、前記あらかじめ定められた形状記述子の前記第１の値の軸系の前記集合に照合する前記範囲は、前記所与の相似変換を法として、前記あらかじめ定められた形状記述子の前記第１の値の軸系に関連する面に照合する前記あらかじめ定められた形状記述子の前記第２の値の軸系に関連する前記面の比率として所与の相似変換に対して評定されることを特徴とする請求項３に記載の方法。
【請求項５】
・  前記データベースの前記３Ｄモデル化オブジェクトおよび前記入力３Ｄモデル化オブジェクトはそれぞれ、支持曲面、ならびに前記３Ｄメッシュの前記頂点および前記辺によって形成される前記面を、関連する支持曲面の境界付けされた部分として定義するデータによってさらに定義され、前記３Ｄモデル化オブジェクトはそれによって境界表現によって定義され、
・  それぞれの３Ｄモデル化オブジェクトのための前記あらかじめ定められた形状記述子の前記値は、前記それぞれの３Ｄモデル化オブジェクトの各それぞれの面のために、前記それぞれの面によって定義される前記支持曲面の前記境界付けされた部分のサンプリングをさらに含み、
・  前記あらかじめ定められた形状記述子の第２の値に対する前記あらかじめ定められた形状記述子の第１の値の前記類似性はさらに、前記同じ相似変換を法として、前記あらかじめ定められた形状記述子の前記第２の値の前記サンプリングが、前記あらかじめ定められた形状記述子の前記第１の値の前記サンプリングに照合する範囲に次第に左右される
ことを特徴とする請求項１乃至４のいずれか一項に記載の方法。
【請求項６】
前記あらかじめ定められた形状記述子の第２の値に対する前記あらかじめ定められた形状記述子の第１の値の前記類似性は、各反復で、新しい候補相似変換を見つけること、次いで前記候補相似変換に従って前記類似性を評定することを含む方式の反復により評定され、新しい候補相似変換は、各反復で単に軸系情報に基づいて見つけられることを特徴とする請求項５に記載の方法。
【請求項７】
前記データベースの前記３Ｄモデル化オブジェクトおよび／または前記入力３Ｄモデル化オブジェクトは、機械設計工程によりユーザ定義であることを特徴とする請求項１乃至６のいずれか一項に記載の方法。
【請求項８】
請求項１乃至７のいずれか一項に記載の方法によりクエリが実行されるように構成されたデータベースであって、前記データベースは、機械部品を表し、少なくとも３Ｄメッシュによってそれぞれ定義される３Ｄモデル化オブジェクトを含み、３Ｄモデル化オブジェクトの前記３Ｄメッシュは、頂点と、前記頂点に接続する辺とを有し、前記頂点および前記辺は、前記３Ｄモデル化オブジェクトによって表される前記機械部品の前記エンベロープを表す面を形成し、前記データベースの各それぞれの３Ｄモデル化オブジェクトは、前記それぞれの３Ｄモデル化オブジェクトのためのあらかじめ定められた形状記述子の値に関連し、それぞれの３Ｄモデル化オブジェクトのための前記あらかじめ定められた形状記述子の前記値は、三面を有する軸系の集合を含み、軸系の前記集合は、前記それぞれの３Ｄモデル化オブジェクトの前記３Ｄメッシュのそれぞれの頂点と、前記それぞれの３Ｄモデル化オブジェクトの前記３Ｄメッシュのそれぞれの面とから成るペアの集合と全単射の関係であり、それぞれの軸系の前記軸は、前記それぞれの頂点における、前記それぞれの頂点に接続された前記辺の方向に、前記それぞれの頂点における、前記３Ｄモデル化オブジェクトによって表される前記機械部品の前記エンベロープに垂直な方向に、および前記機械部品の外側に対応する前記面の向きに基づいて方向付けされることを特徴とするデータベース。
【請求項９】
・  前記データベースの前記３Ｄモデル化オブジェクトはそれぞれ、支持曲面、ならびに前記３Ｄメッシュの前記頂点および前記辺によって形成される前記面を、関連する支持曲面の境界付けされた部分として定義するデータによってさらに定義され、前記３Ｄモデル化オブジェクトはそれによって境界表現によって定義され、
・  それぞれの３Ｄモデル化オブジェクトのための前記あらかじめ定められた形状記述子の前記値は、前記それぞれの３Ｄモデル化オブジェクトの各それぞれの面のために、前記それぞれの面によって定義される前記支持曲面の前記境界付けされた部分のサンプリングをさらに含む
ことを特徴とする請求項８に記載のデータベース。
【請求項１０】
前記データベースの前記３Ｄモデル化オブジェクトは、機械設計工程によるユーザ定義であることを特徴とする請求項８または９に記載のデータベース。
【請求項１１】
請求項８乃至１０のいずれか一項に記載のデータベースをそこに記録していることを特徴とするコンピュータ可読記憶媒体。
【請求項１２】
請求項８乃至１０のいずれか一項に記載のデータベースを構築するためであることを特徴とするコンピュータにより実施される方法。
【請求項１３】
請求項１乃至６および／または請求項１２のいずれか一項に記載の方法を実行するための命令を含むことを特徴とするコンピュータプログラム。
【請求項１４】
請求項１２に記載のコンピュータプログラムをそこに記録していることを特徴とするコンピュータ可読記憶媒体。
【請求項１５】
請求項１３に記載のコンピュータプログラムを記憶したメモリ、および／または請求項８乃至１０のいずれか一項に記載のデータベースに結合されたプロセッサを含むことを特徴とするシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータプログラムおよびシステムの分野に関し、より詳細には、機械部品を表す三次元モデル化オブジェクトを含んだデータベースにクエリを実行するための方法、システム、およびプログラムに関する。
【背景技術】
【０００２】
オブジェクトの設計、エンジニアリング、および製造のために、市場ではいくつかのシステムおよびプログラムが提供されている。ＣＡＤは、コンピュータ支援設計（Computer-Aided Design）の頭字語であり、例えばＣＡＤは、オブジェクトを設計するためのソフトウェアソリューションに関連する。ＣＡＥは、コンピュータ支援工学（Computer-Aided Engineering）の頭字語であり、例えばＣＡＥは、将来の製品の物理的挙動をシミュレートするためのソフトウェアソリューションに関連する。ＣＡＭは、コンピュータ支援製造（Computer-Aided Manufacturing）の頭字語であり、例えばＣＡＭは、製造工程および作業を定義するためのソフトウェアソリューションに関連する。そのようなコンピュータ支援設計システムにおいて、グラフィカルユーザインターフェースは、技術の効率性に関して重要な役割を果たす。こうした技術は、製品ライフサイクル管理（ＰＬＭ）システム内に組み込まれることが可能である。ＰＬＭは、拡大企業（extended enterprise）の概念から、会社が、製品データを共有し、共通の工程を適用し、構想から耐用期間の満了まで、製品の開発のための企業知識を活用するのに役立つビジネス戦略を指す。（ＣＡＴＩＡ、ＥＮＯＶＩＡ、およびＤＥＬＭＩＡの商標で）ダッソーシステムズ（Dassault Systemes）によって提供されるＰＬＭソリューションは、製品工学知識を整理するエンジニアリングハブ、製造工学知識を管理する製造ハブ、ならびにエンジニアリングハブと製造ハブの両方への企業統合および接続を可能にする企業ハブを提供する。すべてを組み合わせたシステムは、動的な、知識ベースの製品作成、ならびに最適化された製品定義、製造準備、生産、およびサービスを推進する決定サポートを可能にするための、製品、工程、資源を関連付けたオープンオブジェクトモデルを提供する。
【０００３】
これに関連して、別の立体に、例えば、ＣＡＤシステムを用いて設計される立体に、幾何学的に相似な既存の立体（solid）を探索する必要がある。この探索は、各立体に添付された、一般に「形状記述子」と呼ばれる専用の情報を比較することによって行われる。特にクライアント／サーバアーキテクチャの状況において相似なオブジェクトを探索することは、したがって、次のように行われ得る。クライアントコンピュータを使用することによって、設計者は、３ＤモデルＡ、一般的には立体を作成または編集する。問題は、設計されるものと相似な既存の立体を見つけることである。候補立体のデータベースは、サーバコンピュータによってホストされる。クライアントコンピュータは、立体Ａの形状記述子ｓ（Ａ）を計算する。この形状記述子は、ユーザ定義の類似性／相似性基準ｃとともに、サーバコンピュータに送られる。次いで、ある場合は、相似な立体（すなわち、類似性基準により探索される立体に「似ている」立体）を見つけるために、サーバコンピュータ上で探索アルゴリズムが実行される。この探索は、類似性基準ｃおよびデータベース中の立体のあらかじめ計算された形状記述子に関連する要求とともに、形状記述子ｓ（Ａ）を利用する。最終的に、相似な立体が、クライアントコンピュータに送り返される。２つの立体は、一般的な感覚（common sense）により、それらが「同じ形状」または「ほぼ同じ形状」を有するとき、一般的に、「相似である」または「似ている」と言われる。相似は、立体の鏡像が元の立体と相似であることを意味するミラーリングを含み得る。また相似は、スケール変更された立体が元の立体と相似であることを意味するスケール因子を含み得る。したがって相似立体探索の重要な特徴は、形状記述子である。形状記述子は、立体モデルから計算され、比較の目的で集中的に使用される、何らかの多次元の数値情報である。
【０００４】
一方では、動径（radial）関数および調和関数に基づく形状記述子技術が存在する。動径関数の目的は、一般的には回転不変量ではない３Ｄ形状を、回転不変量である数値情報にエンコードすることである。これは、テスト立体と候補立体との間の相対位置計測の問題を解消する。調和関数は、関数の基底であり、形状記述子は、ある意味では、調和関数の基底における動径関数の座標である。しかしながらこの技術は、多目的の形状比較のために設計されており、既存の製品は、出力される結果は常に関連があるとは限らないという点において、機械部品の状況では効率が不足している。一般的な参考文献は以下のとおりである：
１．文献ＥＰ  ２１６９５６７  Ａ２
２．Ｒｏｔａｔｉｏｎ  Ｉｎｖａｒｉａｎｔ  Ｓｐｈｅｒｉｃａｌ  Ｈａｒｍｏｎｉｃ  Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ  ｏｆ  ３Ｄ  Ｓｈａｐｅ  Ｄｅｓｃｒｉｐｔｏｒｓ。Ｍ．Ｋａｚｈｄａｎ、Ｔ．Ｆｕｎｋｈｏｕｓｅｒ、およびＳ．Ｒｕｓｉｎｋｉｅｗｉｃｚ、Ｅｕｒｏｇｒａｐｈｉｃｓ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｇｅｏｍｅｔｒｙ  Ｐｒｏｃｅｓｓｉｎｇ（２００３）、および
３．Ａ  ｓｅａｒｃｈ  ｅｎｇｉｎｅ  ｆｏｒ  ３Ｄ  ｍｏｄｅｌｓ、Ｔ．Ｆｕｎｋｈｏｕｓｅｒ、Ｐ．Ｍｉｎ、Ｍ．Ｋａｚｈｄａｎ、Ｊ．Ｃｈｅｎ、Ａ．Ｈａｌｄｅｒｍａｎ、Ｄ．Ｄｏｂｋｉｎ、Ｄ．Ｊａｃｏｂｓ、Ｄ．：ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｇｒａｐｈｉｃｓ  ２２（１）、８３−１０５（２００３）。
【０００５】
一方では、機械部品を表す立体モデルについて、別の技術が利用可能であることが知られている。形状記述子は、Ｂ−Ｒｅｐ表現から、より正確には立体モデルの面から、計算される。例えば、（下記に引用する）１つの従来技術は、面に関する幾何学的特徴を抽出し、２つのＢ−Ｒｅｐモデル間で等しい面と異なる面とを区別するために、それらを照合する。しかし、既存の製品は、関連性の観点からのみならず、取り入れるデータのサイズおよび速度の観点からも、依然として効率が不足している。この技術は、以下を含む：
１．Ｃｏｍｐａｒｉｎｇ  ３Ｄ  ＣＡＤ  Ｍｏｄｅｌｓ：Ｕｓｅｓ，Ｍｅｔｈｏｄｓ，Ｔｏｏｌｓ  ａｎｄ  Ｐｅｒｓｐｅｃｔｉｖｅｓ、Ａｎｔｏｉｎｅ  Ｂｒｉｅｒｅ−Ｃｏｔｅ、Ｌｏｕｉｓ  Ｒｉｖｅｓｔ  ａｎｄ  Ｒｏｌａｎｄ  Ｍａｒａｎｚａｎａ、Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｄｅｓｉｇｎ  ＆  Ａｐｐｌｉｃａｔｉｏｎｓ、９（６）、２０１２、７７１−７９４、および
２．Ｍｓａａｆ，Ｏ．、Ｍａｒａｎｚａｎａ，Ｒ．、Ｒｉｖｅｓｔ，Ｌ．、Ｐａｒｔ  ｄａｔａ  ｍｉｎｉｎｇ  ｆｏｒ  ｉｎｆｏｒｍａｔｉｏｎ  ｒｅ−ｕｓｅ  ｉｎ  ａ  ＰＬＭ  ｃｏｎｔｅｘｔ、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＧＴ２００７、Ｍａｙ  １４−１７、Ｍｏｎｔｒｅａｌ、Ｃａｎａｄａ、ＡＳＭＥ  Ｐａｐｅｒ：ＧＴ２００７−２７９６６、Ａｍｅｒｉｃａｎ  Ｓｏｃｉｅｔｙ  ｏｆ  Ｍｅｃｈａｎｉｃａｌ  Ｅｎｇｉｎｅｅｒｓ、Ｎｅｗ  Ｙｏｒｋ、ＮＹ、２００７。
【０００６】
この状況には、機械部品を表す３Ｄモデル化オブジェクトを含んだデータベースにクエリを実行するためのソリューションを改善する必要が依然としてある。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】欧州特許出願公開第２１６９５６７  Ａ２号明細書
【非特許文献】
【０００８】
【非特許文献１】Ｒｏｔａｔｉｏｎ  Ｉｎｖａｒｉａｎｔ  Ｓｐｈｅｒｉｃａｌ  Ｈａｒｍｏｎｉｃ  Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ  ｏｆ  ３Ｄ  Ｓｈａｐｅ  Ｄｅｓｃｒｉｐｔｏｒｓ。Ｍ．Ｋａｚｈｄａｎ、Ｔ．Ｆｕｎｋｈｏｕｓｅｒ、およびＳ．Ｒｕｓｉｎｋｉｅｗｉｃｚ、Ｅｕｒｏｇｒａｐｈｉｃｓ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｇｅｏｍｅｔｒｙ  Ｐｒｏｃｅｓｓｉｎｇ（２００３）
【非特許文献２】Ａ  ｓｅａｒｃｈ  ｅｎｇｉｎｅ  ｆｏｒ  ３Ｄ  ｍｏｄｅｌｓ、Ｔ．Ｆｕｎｋｈｏｕｓｅｒ、Ｐ．Ｍｉｎ、Ｍ．Ｋａｚｈｄａｎ、Ｊ．Ｃｈｅｎ、Ａ．Ｈａｌｄｅｒｍａｎ、Ｄ．Ｄｏｂｋｉｎ、Ｄ．Ｊａｃｏｂｓ、Ｄ．：ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｇｒａｐｈｉｃｓ  ２２（１）、８３−１０５（２００３）
【非特許文献３】Ｃｏｍｐａｒｉｎｇ  ３Ｄ  ＣＡＤ  Ｍｏｄｅｌｓ：Ｕｓｅｓ，Ｍｅｔｈｏｄｓ，Ｔｏｏｌｓ  ａｎｄ  Ｐｅｒｓｐｅｃｔｉｖｅｓ、Ａｎｔｏｉｎｅ  Ｂｒｉｅｒｅ−Ｃｏｔｅ、Ｌｏｕｉｓ  Ｒｉｖｅｓｔ  ａｎｄ  Ｒｏｌａｎｄ  Ｍａｒａｎｚａｎａ、Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｄｅｓｉｇｎ  ＆  Ａｐｐｌｉｃａｔｉｏｎｓ、９（６）、２０１２、７７１−７９４
【非特許文献４】Ｍｓａａｆ，Ｏ．、Ｍａｒａｎｚａｎａ，Ｒ．、Ｒｉｖｅｓｔ，Ｌ．、Ｐａｒｔ  ｄａｔａ  ｍｉｎｉｎｇ  ｆｏｒ  ｉｎｆｏｒｍａｔｉｏｎ  ｒｅ−ｕｓｅ  ｉｎ  ａ  ＰＬＭ  ｃｏｎｔｅｘｔ、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＧＴ２００７、Ｍａｙ  １４−１７、Ｍｏｎｔｒｅａｌ、Ｃａｎａｄａ、ＡＳＭＥ  Ｐａｐｅｒ：ＧＴ２００７−２７９６６、Ａｍｅｒｉｃａｎ  Ｓｏｃｉｅｔｙ  ｏｆ  Ｍｅｃｈａｎｉｃａｌ  Ｅｎｇｉｎｅｅｒｓ、Ｎｅｗ  Ｙｏｒｋ、ＮＹ、２００７
【発明の概要】
【課題を解決するための手段】
【０００９】
したがって、機械部品を表す３Ｄモデル化オブジェクトを含んだデータベースにクエリを実行するためのコンピュータにより実行される方法が提供される。方法は、入力３Ｄモデル化オブジェクトのためのあらかじめ定められた形状記述子の値に対する類似性基準を含むクエリを提供するステップを含む。また方法は、クエリの結果として、データベースのそれぞれの３Ｄモデル化オブジェクトを返すステップを含む。それぞれの３Ｄモデル化オブジェクトは、それぞれの３Ｄモデル化オブジェクトのためのあらかじめ定められた形状記述子の値が類似性基準に関連する（respect）範囲に基づいて返される。データベースの３Ｄモデル化オブジェクトおよび入力３Ｄモデル化オブジェクトは、少なくとも３Ｄメッシュによってそれぞれ定義され、３Ｄモデル化オブジェクトの３Ｄメッシュは、頂点と、頂点を接続する辺（edge）とを有し、頂点および辺は、３Ｄモデル化オブジェクトによって表される機械部品のエンベロープ（envelop）を表す面を形成する。それぞれの３Ｄモデル化オブジェクトのためのあらかじめ定められた形状記述子の値は、三面を有する軸系の集合を含む。軸系の集合は、それぞれの３Ｄモデル化オブジェクトの３Ｄメッシュのそれぞれの頂点と、それぞれの３Ｄモデル化オブジェクトの３Ｄメッシュのそれぞれの面とから成るペアの集合と全単射の関係である。それぞれの軸系の軸は、それぞれの頂点における、それぞれの頂点に接続される辺の方向、それぞれの頂点における、３Ｄモデル化オブジェクトによって表される機械部品のエンベロープに垂直な方向、および機械部品の外側に対応する面の向きに基づいて、方向付けされる。あらかじめ定められた形状記述子の第２の値に対するあらかじめ定められた形状記述子の第１の値の類似性は、あらかじめ定められた形状記述子の第２の値の軸系の集合が、同じ相似変換を法として、あらかじめ定められた形状記述子の第１の値の軸系の集合に照合する範囲に次第に左右される。
【００１０】
この方法は、次のステップのうちの１または複数を含むことができる：
−  あらかじめ定められた形状記述子の第２の値の軸系の集合が、あらかじめ定められた形状記述子の第１の値の軸系の集合に照合する範囲は、所与の相似変換型に対してあらかじめ定められた方法で評定される、
−  あらかじめ定められた形状記述子の第２の値のそれぞれの軸系に関連する面が、所与の相似変換を法として、あらかじめ定められた形状記述子の第１の値のそれぞれの軸系に関連する面に照合する場合に限り、あらかじめ定められた形状記述子の第２の値のそれぞれの軸系が、あらかじめ定められた形状記述子の第２の値の軸系の集合があらかじめ定められた形状記述子の第１の値の軸系の集合に照合する範囲において、所与の相似変換重みを法として、あらかじめ定められた形状記述子の第１の値のそれぞれの軸系に照合するということ、
−  あらかじめ定められた形状記述子の第２の値の軸系の集合が、あらかじめ定められた形状記述子の第１の値の軸系の集合に照合する範囲は、所与の相似変換を法として、あらかじめ定められた形状記述子の第１の値の軸系に関連する面に照合する、あらかじめ定められた形状記述子の第２の値の軸系に関連する面の比率として、所与の相似変換に対して評定される、
−  データベースの３Ｄモデル化オブジェクトおよび入力３Ｄモデル化オブジェクトは、それぞれ、支持曲面（supporting surface）および３Ｄメッシュの頂点および辺によって形成される面を定義するデータによって、関連する支持曲面の境界付けされた部分として、さらに定義され、それによって３Ｄモデル化オブジェクトは、境界表現によって定義され、それぞれの３Ｄモデル化オブジェクトのためのあらかじめ定められた形状記述子の値は、それぞれの３Ｄモデル化オブジェクトの各それぞれの面に対して、それぞれの面によって定義される支持曲面の境界付けされた部分のサンプリングをさらに含み、あらかじめ定められた形状記述子の第２の値に対するあらかじめ定められた形状記述子の第１の値の類似性はさらに、あらかじめ定められた形状記述子の第２の値のサンプリングが、同じ相似変換を法として、あらかじめ定められた形状記述子の第１の値のサンプリングに照合する範囲に次第に左右される、
−  あらかじめ定められた形状記述子の第２の値に対するあらかじめ定められた形状記述子の第１の値の類似性は、各反復において、新しい候補相似変換を見つけること、次いで候補相似変換に従って類似性を評定することを含む方式の反復により評定され、新しい候補相似変換は単に軸系情報に基づいて各反復で見つけられる、ならびに／または
−  データベースの３Ｄモデル化オブジェクトおよび／もしくは入力３Ｄモデル化オブジェクトは、機械設計工程によりユーザ定義である。
【００１１】
上記の方法によりクエリを実行するように構成されたデータベースがさらに提供される。データベースは、機械部品を表し、少なくとも３Ｄメッシュによってそれぞれ定義される３Ｄモデル化オブジェクトを含み、３Ｄモデル化オブジェクトの３Ｄメッシュは、頂点と、頂点を接続する辺とを有し、頂点および辺は、３Ｄモデル化オブジェクトによって表される機械部品のエンベロープを表す面を形成する。データベースの各それぞれの３Ｄモデル化オブジェクトは、それぞれの３Ｄモデル化オブジェクトのためのあらかじめ定められた形状記述子の値に関連している。それぞれの３Ｄモデル化オブジェクトのためのあらかじめ定められた形状記述子の値は、三面を有する軸系の集合を含む。軸系の集合は、それぞれの３Ｄモデル化オブジェクトの３Ｄメッシュのそれぞれの頂点と、それぞれの３Ｄモデル化オブジェクトの３Ｄメッシュのそれぞれの面とから成るペアの集合と全単射の関係である。それぞれの軸系の軸は、それぞれの頂点における、それぞれの頂点に接続される辺の方向、それぞれの頂点における、３Ｄモデル化オブジェクトによって表される機械部品のエンベロープに垂直な方向、および機械部品の外側に対応する面の向きに基づいて、方向付けされる。
【００１２】
一例では、データベースの３Ｄモデル化オブジェクトはそれぞれ、支持曲面、および３Ｄメッシュの頂点および辺によって形成される面を定義するデータによって、関連する支持曲面の境界付けされた部分としてさらに定義され、それによって３Ｄモデル化オブジェクトは、境界表現によって定義され、それぞれの３Ｄモデル化オブジェクトのためのあらかじめ定められた形状記述子の値は、それぞれの３Ｄモデル化オブジェクトの各それぞれの面に対して、それぞれの面によって定義される支持曲面の境界付けされた部分のサンプリングをさらに含む。
【００１３】
一例では、データベースの３Ｄモデル化オブジェクトは、機械設計工程によりユーザ定義である。
【００１４】
データベースが記録されたコンピュータ可読記憶媒体がさらに提供される。
【００１５】
そのようなデータベースを構築するためのコンピュータにより実行される方法がさらに提供される。
【００１６】
上記の２つの方法のいずれかまたは両方を実行するための命令を含んだコンピュータプログラムがさらに提供される。
【００１７】
コンピュータプログラムが記録されたコンピュータ可読記憶媒体がさらに提供される。
【００１８】
コンピュータプログラムおよび／またはデータベースが記録されたメモリに結合されたプロセッサを含んだシステムがさらに提供される。
【図面の簡単な説明】
【００１９】
次に、本発明の実施形態について、非限定的な例として、添付の図面を参照して述べる。
【図１】方法の一例のフローチャートである。
【図２】システムのグラフィカルユーザインターフェースの一例を示す図である。
【図３】システムの一例を示す図である。
【図４】方法の例を示す図である。
【図５】方法の例を示す図である。
【図６】方法の例を示す図である。
【図７】方法の例を示す図である。
【図８】方法の例を示す図である。
【図９】方法の例を示す図である。
【図１０】方法の例を示す図である。
【図１１】方法の例を示す図である。
【図１２】方法の例を示す図である。
【図１３】方法の例を示す図である。
【図１４】方法の例を示す図である。
【図１５】方法の例を示す図である。
【図１６】方法の例を示す図である。
【図１７】方法の例を示す図である。
【図１８】方法の例を示す図である。
【図１９】方法の例を示す図である。
【図２０】方法の例を示す図である。
【図２１】方法の例を示す図である。
【図２２】方法の例を示す図である。
【図２３】方法の例を示す図である。
【図２４】方法の例を示す図である。
【図２５】方法の例を示す図である。
【図２６】方法の例を示す図である。
【図２７】方法の例を示す図である。
【図２８】方法の例を示す図である。
【図２９】方法の例を示す図である。
【図３０】方法の例を示す図である。
【図３１】方法の例を示す図である。
【発明を実施するための形態】
【００２０】
図１のフローチャートを参照すると、機械部品を表す３Ｄモデル化オブジェクト（例えばそのデータ）を含むデータベースにクエリを実行するためのコンピュータにより実行される方法が提案されている（すなわち、データベースの各３Ｄモデル化オブジェクトが、それぞれの機械部品、少なくともその外形を表し、例えば「機械部品」という用語は、その組立品および／またはその一部もまた指す）。方法は、（例えば、クライアントコンピュータシステムにおいて、例えば、データベースに、またはそのようなデータベース上で動作するプラグイン／スクリプトに、またはサーバコンピュータシステムすなわちデータベースホストに、例えば、クライアントが例えば同じマシンによってホストされる場合にあり得る、クライアントが場合によりサーバと混同される）、（クエリを定義するデータの一部として、および例えば少なくとも、クエリを作成する可能性のあるいくつかの基準の１つとして、例えば、データベース探索の分野では非常に伝統的であるように、クエリは場合により他の基準を含み、オプションとして異なる基準に重みが割り当てられる）類似性基準を含んだクエリを提供するステップＳ１を含む。類似性基準は、入力３Ｄモデル化オブジェクトのためのあらかじめ定められた形状記述子の値に関連する（例えば、入力３Ｄモデル化オブジェクトは、したがってこのように、例えば入力と相似な／似ているオブジェクトがデータベースで探索されるように、探索されるオブジェクトである）。方法はまた、クエリの結果（すなわち、クエリおよび／または探索されるデータの内容によって、返されるデータは、１または複数のそのような結果を含む、または必ずしもいくつかの結果が返されないことを意味する、結果なし／ヌル（ｎｕｌｌ）結果さえも含み、総称表現であるとき複数形が使用される）として、データベースのそれぞれの３Ｄモデル化オブジェクトを（例えば、クライアントにまたはサーバで）返すステップＳ２を含む。それぞれの３Ｄモデル化オブジェクトのためのあらかじめ定められた形状記述子の値が類似性基準に関連する範囲に基づいて、それぞれの３Ｄモデル化オブジェクトが返される。
【００２１】
次に、データベースの３Ｄモデル化オブジェクトおよび入力３Ｄモデル化オブジェクトは、それぞれ少なくとも３Ｄメッシュによって定義される。３Ｄモデル化オブジェクトの３Ｄメッシュは、（「メッシュ」という用語の定義により）頂点と、頂点を接続する辺とを有する。頂点および辺は、３Ｄモデル化オブジェクトによって表される機械部品のエンベロープ（すなわち、外側の曲面の幾何学的形状）を表す面を形成する。また、それぞれの３Ｄモデル化オブジェクトのためのあらかじめ定められた形状記述子の値は、（そのデータの中から）３面（すなわち同じ起点から始まる３つのベクトル）を有する軸系の集合（すなわち、そのような集合を定義するデータ）を含み、軸系の集合は、それぞれの３Ｄモデル化オブジェクトの３Ｄメッシュのそれぞれの頂点（それぞれの軸系の起点はそれによってそのようなそれぞれの頂点に位置している）と、それぞれの３Ｄモデル化オブジェクトの３Ｄメッシュのそれぞれの面とから成るペアの集合と全単射（すなわち、１対１）の関係である（各軸系は、そのようなそれぞれの｛頂点、面｝ペアに関連し、それによって、頂点が２つ以上の面に属する場合、それぞれの頂点に２つ以上の軸系を関連付けることになる）。それぞれの軸系の軸は、以下に基づいて方向付けされる（すなわち、次のデータに基づくあらかじめ定められた方式が向きに適用される）：（ｉ）それぞれの頂点における、それぞれの頂点に接続された辺の方向（およびオプションとしてある場合はさらに向き）、（ｉｉ）それぞれの頂点における、（例えば）３Ｄモデル化オブジェクトによって表される機械部品のエンベロープに対する垂線（を表す）（例えば、データにあらかじめ定められた、またはオンザフライで計算される）方向、（ｉｉｉ）（例えば、参照の三面の標準的向きにより）機械部品の外側に対応する面の方向。あらかじめ定められた形状記述子の第２の値に対するあらかじめ定められた形状記述子の第１の値の類似性は、あらかじめ定められた形状記述子の第２の値の軸系の集合が、あらかじめ定められた形状記述子の第１の値の軸系の集合に照合する範囲に次第に左右され、これは同じ相似変換を法とする。
【００２２】
そのような方法は、機械部品を表す３Ｄモデル化オブジェクトを含んだデータベースのクエリを実行することを改善する。
【００２３】
特に、この方法は、ステップＳ１およびステップＳ２によって、ならびにそれぞれの３Ｄモデル化オブジェクトのためのあらかじめ定められた形状記述子の値の３Ｄ定義によって、データベースで３Ｄ形状に基づく探索を行うためのソリューションを提供する。軸系の集合が３Ｄメッシュの頂点のみならず、それぞれの３Ｄモデル化オブジェクトの３Ｄメッシュのそれぞれの頂点と、それぞれの３Ｄモデル化オブジェクトの３Ｄメッシュのそれぞれの面とから成るペアの集合と全単射の関係であることにより、形状記述子は、３Ｄモデル化オブジェクトを十分に記述し、（３Ｄ幾何学的形状類似性の観点から）クエリに返される結果の関連性を上げる。
【００２４】
ここで、「関連性」は、入力３Ｄ形状に対して返される結果３Ｄ形状の類似性が、例えば、入力３Ｄ形状のすべての考えられる相似変換にわたって、距離の積分の最小値（入力３Ｄ形状の曲面から、結果３Ｄ形状の曲面まで測定される最小距離）に対応し得るようなものである。別の例は、ＡおよびＢを、それぞれ３Ｄモデル化オブジェクト（例えば、機械部品のＢ−ｒｅｐ）を表す、
【００２５】
【数１】
2016224944.tif 000003
【００２６】
の２つのコンパクト部分集合と見なすことである。ＡとＢとの類似性は、よく知られているハウスドルフ（Hausdorff）距離を使用することによって定量化され得る。まず、
【００２７】
【数２】
2016224944.tif 000004
【００２８】
を定義し、ここでｄ（ａ，ｂ）は、点ａと点ｂとの間のユークリッド距離である。次いで、ＡとＢとの間のハウスドルフ距離は、Ｈ（Ａ，Ｂ）＝ｍａｘ｛ｐ（Ａ，Ｂ），ｐ（Ｂ，Ａ）｝である。Ｈ（Ａ，Ｄ（Ｂ））＝０のように相似変換Ｄが存在する場合、部分集合Ａおよび部分集合Ｂは、完全に相似である。これは、２つの形状間の３Ｄ相似性の自然な知覚を数量化する方法である。
【００２９】
また、定義は、データベースの３Ｄモデル化オブジェクトおよび入力３Ｄモデル化オブジェクトが３Ｄメッシュによって定義されることに適合され、機械部品の３Ｄ  ＣＡＤ設計の場合に多く、そのような定義を活用することになる。さらに、形状記述子に対して保持される特定の定義は、それは設計者が、設計される機械部品のエンベロープに注目する状況によく適合され、そのようなエンベロープを表す３Ｄメッシュを形成し、変更する漸進的方法であるので、機械設計によく適合される。この状況で、形状記述子は、（形状記述子を記憶するためのメモリ空間の観点から、また、類似性評定の簡略化、ひいてはこの方法の速度および／またはデータベース構築の速度に関連する、類似性を評定するときに処理するデータの量の観点から）サイズと、この方法によって出力される結果の関連性との間で優れた比率を達成する。この方法は実際に、（例えば、Ｂ−Ｒｅｐ全体を考えるのに対して）コンパクトな方法で形状を記述するために、３Ｄメッシュ（すなわち、面、辺の方向、頂点におけるエンベロープに垂直な方向、および面の向き）が存在するとき、機械部品設計工程において設計によって漸進的に追加される特定の細部を強調する。言い換えれば、この方法の形状記述子は、それが頂点における３Ｄ軸系を計算し、記憶するという問題であるので、計算が非常に高速である、隣接した軸系の同じベクトルはディクショナリを介して共有され得るので、大量のメモリを必要としない、比較プログラムは高速、単純であり、データアクセスが不可欠である大量の計算の状況でそれを効率的にする。テストは、この方法が一般的な状況では約２０ｍｓで実行できることを示した。
【００３０】
この方法は、コンピュータにより実行されるものである。これは、この方法のステップ（または実質的にはすべてのステップ）が、少なくとも１つのコンピュータ、または任意のシステムによって同様に実行されることを意味する。したがって、この方法のステップは、場合により完全に自動的に、または半自動的にコンピュータによって行われる。例では、この方法のステップの少なくともいくつかをトリガすることは、ユーザ−コンピュータのインタラクションにより行われ得る。例えば、Ｓ１は、ユーザが入力３Ｄモデル化オブジェクトを設計する、および／または探索／クエリソフトウェア機能を要求し、パラメータで表すことによりクエリが提供され得るので、ユーザのインタラクションを含み得る。要求されるユーザ−コンピュータのインタラクションのレベルは、予測される自動性のレベルに左右され、ユーザの希望を実現する必要性とのバランスをとり得る。例では、このレベルは、ユーザ定義および／または事前定義とすることができる。
【００３１】
この目的に適合されたシステムを用いて方法を実行することが、方法のコンピュータによる実行の典型的な例である。システムは、メモリおよびグラフィカルユーザインターフェース（ＧＵＩ）に結合されたプロセッサを備えることができ、メモリはそこに、方法を実行するための命令を含んだコンピュータプログラムを記録している。メモリは、データベースを記憶することもあり、例えばそこで、クエリが実行される。メモリは、そのような記憶のために適合された任意のハードウェアであり、場合によりいくつかの物理的個別部分（例えば、プログラム用の１つ、場合によりデータベース用の１つ）を含んでいる。システムはしたがって、クライアント−サーバシステム、または単にクライアントシステム（データベースはリモートサーバに記憶されており、それによって図１の方法は、そのような場合にクライアントの視点から見られる）、または単にサーバシステム（クエリはリモートクライアントシステムから発生し、それによって図１の方法は、そのような場合にサーバの視点から見られる）であり得る。図１の方法は、この方法を実行するためにクライアントとサーバの双方が通信するので、クライアントの視点から、および／またはサーバの視点から実行されるように、区別なく理解され得ることに留意されたい。返すことＳ２は、実際には能動的（データベース）、または受動的（クエリを要求するクライアント）であり得る。
【００３２】
「データベース」は、探索および検索のために整理されたデータ（すなわち、情報）の任意の集まり（例えば、あらかじめ定められた構造化言語、例えばＳＱＬに基づいた、例えば関係データベース）を意味する。メモリに記憶されるとき、データベースは、コンピュータによる迅速な探索および検索を可能にする。データベースは実際に、様々なデータ処理動作と連動して、データの記憶、検索、変更、および削除を容易にするように構成される。データベースは、そのそれぞれが１または複数のフィールドから成るレコードに分解され得るファイルまたはファイルの集合から成ることができる。フィールドは、データストレージの基本単位である。ユーザは、主としてクエリによりデータを検索することができる。キーワードを使用し、コマンドをソートすると、ユーザは、使用されているデータベース管理システムのルールに従ってデータの特定の集合体上でレポートを検索または作成するために、多くのレコード中のフィールドを迅速に探索、再配列、グループ化、および選択することができる。
【００３３】
この方法の場合、データベースは、機械部品を表す、少なくとも先に定義されたように３Ｄメッシュによってそれぞれ定義される、３Ｄモデル化オブジェクトを含む。データベースの各それぞれの３Ｄモデル化オブジェクトはさらに、それぞれの３Ｄモデル化オブジェクトのためのあらかじめ定められた形状記述子の値に（例えば、使用するデータベース技術に左右される、行または任意の他の型の関係で）関連付けられ、あらかじめ定められた形状記述子の値は、先に定義されるものである（およびそれは、データベースのフィールドの、またはいくつかのフィールドをカバーする値として定義されてもよく、これは、データベース最適化に関連する実施詳細であるので、本明細書ではさらに説明しない）。そのようなデータベースは、例えば、（データベースが適切に構成されている場合）図１のクエリ方法で使用されるように、新しい３Ｄモデル化オブジェクトで構築および／またはインクリメントされ得る。したがってデータベースは、いかなる方法でも構築され得、上述のようにシステムのメモリに、またはそのために適している任意の他の媒体に記憶され得る。そのようなデータベースは、図１の方法により３Ｄモデル化オブジェクトを検索することを可能にし、したがってそれは、例えば（設計者が関連のある結果を検索し、例えば、システムに再利用機能が設けられている場合、ゼロからすべてを再設計する代わりにそれらを再利用するのを助けることによって）ＣＡＤ設計を速めることができるツールである。
【００３４】
この方法は、一般的にモデル化オブジェクトを操作する。モデル化オブジェクトは、例えばデータベースに記憶されたデータによって定義される任意のオブジェクトである。拡張して、「モデル化オブジェクト」という表現は、データ自体を示す。システムの型により、モデル化オブジェクトは、様々な種類のデータによって定義され得る。システムは、実際には、ＣＡＤシステム、ＣＡＥシステム、ＣＡＭシステム、ＰＤＭシステム、および／またはＰＬＭシステムの任意の組合せとすることができる。これらの様々なシステムでは、モデル化オブジェクトが、対応するデータによって定義される。それに応じて、ＣＡＤオブジェクト、ＰＬＭオブジェクト、ＰＤＭオブジェクト、ＣＡＥオブジェクト、ＣＡＭオブジェクト、ＣＡＤデータ、ＰＬＭデータ、ＰＤＭデータ、ＣＡＭデータ、ＣＡＥデータについて述べることがある。しかしながら、これらのシステムは、モデル化オブジェクトが、これらのシステムの任意の組合せに対応するデータによって定義され得るとき、他のものを除外するものではない。したがってシステムが多分に、ＣＡＤとＰＬＭシステムの両方であり得ることは、以下に提供するそのようなシステムの定義から明らかとなろう。
【００３５】
ＣＡＤシステムは、少なくとも、ＣＡＴＩＡなど、モデル化オブジェクトのグラフィック表現に基づいてモデル化オブジェクトを設計するために適合された任意のシステムをさらに意味する。この場合、モデル化オブジェクトを定義するデータは、モデル化オブジェクトの表現を可能にするデータを含む。例えばＣＡＤシステムが、面または曲面を有するいくつかの場合に、辺または線を使用するＣＡＤモデル化オブジェクトの表現を提供し得る。線、辺、または曲面は、例えば、非一様有理Ｂスプライン（ＮＵＲＢＳ）など、様々な方法で表され得る。詳細には、ＣＡＤファイルが仕様を含み、この仕様から幾何学的形状が生成され得、その結果これが、表現の生成を可能にする。モデル化オブジェクトの仕様は、単一のＣＡＤファイルにまたは複数のＣＡＤファイルに記憶され得る。ＣＡＤシステムにおいてモデル化オブジェクトを表すファイルの一般的なサイズは、部品につき１メガバイトの範囲内である。また、モデル化オブジェクトが、一般的に何千もの部品の組立品であることがある。
【００３６】
ＣＡＤの状況では、一般的にモデル化オブジェクトが、例えば、部品もしくは部品の組立品などの製品、または場合により製品の組立品を表す、３Ｄモデル化オブジェクトであり得る。「３Ｄモデル化オブジェクト」は、その３Ｄ表現を可能にするデータによってモデル化される任意のオブジェクトを意味する。３Ｄ表現は、すべての角度から部品を見ることを可能にする。例えば、３Ｄで表されるとき、３Ｄモデル化オブジェクトが、その軸のいずれかを中心にして、または表現が表示される画面内のいずれかの軸を中心にして処理され、回転され得る。これは特に、３Ｄモデル化されていない２Ｄアイコンを除く。３Ｄ表現の表示は、設計を容易にする（すなわち、設計者が統計的に設計者のタスクを完了する速度を上げる）。製品の設計は、製造工程の一部であるので、これは、産業における製造工程を加速させる。
【００３７】
この方法によって検討されるいかなる３Ｄモデル化オブジェクトも、（例えば、機械の）部品または部品の組立品など、例えばＣＡＤソフトウェアソリューションまたはＣＡＤシステムを用いたその仮想設計の完成の後に、現実の世界で製造される製品の幾何学的形状を表すことができる。ＣＡＤソフトウェアソリューションが、航空宇宙、建築、建設、消費財、ハイテク装置、産業機器、交通、船舶、および／または海底油田／ガス産出または輸送など、様々な、制限のない産業分野における製品の設計を可能にする。この方法によって検討される３Ｄモデル化オブジェクトは、したがって、地上車両（例えば、車および軽トラック機器、レーシングカー、オートバイ、トラックおよびモーター機材、トラックおよびバス、列車など）の部品、航空車両（例えば、機体機器、航空宇宙機器、推進機器、防衛製品、航空機器、宇宙機器）の部品、海上車両（naval vehicle）（例えば、海上機器、商用船、洋上機器、ヨットおよび作業船、海洋機器など）の部品、一般的な機械部品（例えば、工業製造機械、移動式重機もしくは機器、設置機器、工業機器製品、金属加工製品、タイヤ製造製品、など）、電気機械または電子部品（例えば、家庭用電化製品、セキュリティおよび／もしくは制御および／もしくは計測製品、計算および通信機器、半導体、医療用具および機器など）、消費財（例えば、家具、家屋および庭製品、レジャー用品、ファッション製品、耐久消費財小売店の製品、非耐久消費財小売店の製品など）、ならびに／またはパッケージング（例えば、食品および飲料およびたばこ、美容およびパーソナルケア、家庭用品パッケージングなど）など、任意の機械部品であり得る、工業製品を表し得る。
【００３８】
ＰＬＭシステムは、物理的製造品（または製造される製品）を表すモデル化オブジェクトの管理に適合された任意のシステムをさらに意味する。ＰＬＭシステムでは、モデル化オブジェクトはしたがって、物理的オブジェクトの製造に好適なデータによって定義される。これらは一般的に、寸法値および／または許容値とすることができる。オブジェクトを正しく製造するために、実際にそのような値を有することがより望ましい。
【００３９】
ＣＡＭソリューションは、製品の製造データを管理するために適合された任意のソリューション、ハードウェアのソフトウェアをさらに意味する。製造データは、一般的に、製造する製品、製造工程、および必要な資源に関連するデータを含む。ＣＡＭソリューションは、製品の製造工程全体を計画し、最適化するために使用される。例えば、ＣＡＭソリューションはＣＡＭユーザに、実現可能性、製造工程の継続時間、または製造工程の特定のステップで使用され得る特定のロボットなどの資源の数に関する情報を提供することができ、したがって経営または必要とされる投資に関する決定を可能にする。ＣＡＭは、ＣＡＤ工程および潜在的なＣＡＥ工程の後の後続工程である。そのようなＣＡＭソリューションは、ＤＥＬＭＩＡ（登録商標）の商標で、ダッソーシステムズによって提供されている。
【００４０】
ＣＡＥソリューションは、モデル化オブジェクトの物理的挙動の分析のために適合された任意のソリューション、ハードウェアのソフトウェアをさらに意味する。よく知られ、広く使用されているＣＡＥ技術は、一般的に、物理的挙動が方程式により計算され、シミュレートされ得る要素へモデル化オブジェクトを分割することを含む、有限要素法（ＦＥＭ：Finite Element Method）である。そのようなＣＡＥソリューションは、ＳＩＭＵＬＩＡ（登録商標）の商標で、ダッソーシステムズによって提供されている。別の発展中のＣＡＥ技術は、ＣＡＤ幾何学的形状データのない、物理学の異なる分野からの複数の構成要素からなる複合システムのモデル化および分析を含む。ＣＡＥソリューションは、製造する製品の、シミュレーション、ひいては最適化、改善、および検証を可能にする。そのようなＣＡＥソリューションは、ＤＹＭＯＬＡ（登録商標）の商標で、ダッソーシステムズによって提供されている。
【００４１】
ＰＤＭは、製品データ管理（Product Data Management）を表す。ＰＤＭソリューションは、特定の製品に関連するすべての型のデータを管理するために適合された任意のソリューション、ハードウェアのソフトウェアを意味する。ＰＤＭソリューションは、主としてエンジニアであるがプロジェクトマネージャ、財務担当者、販売担当者、および購入者も含む、製品のライフサイクルに関与するすべての関係者によって使用され得る。ＰＤＭソリューションは、一般的には製品指向のデータベースに基づく。ＰＤＭソリューションは、関係者がその製品に関する整合性のあるデータを共有することを可能にし、したがって関係者が一致しないデータを使用するのを防止する。そのようなＰＤＭソリューションは、ＥＮＯＶＩＡ（登録商標）の商標で、ダッソーシステムズによって提供されている。
【００４２】
図２は、方法を実行するための（クライアント）システムのＧＵＩの一例を示し、ここではシステムは、ＣＡＤシステムである。
【００４３】
ＧＵＩ  ２１００は、標準的なメニューバー２１１０、２１２０、ならびにボタンおよびサイドツールバー２１４０、２１５０を有する、一般的なＣＡＤに適したインターフェースであってよい。そのようなメニューおよびツールバーは、ユーザが選択可能なアイコンの集合を含み、当技術分野で知られているように、各アイコンが、１または複数の操作または機能と関連付けられ、例えば、１つのそのような操作／機能は、（例えば、入力モデル化オブジェクト２０００に基づいて）図１の方法を起動するためのものであり、例えば、図１の方法は、あるいはバックグラウンドプロセスとして実行される。これらのアイコンのいくつかは、ソフトウェアツールと関連付けられ、ＧＵＩ  ２１００に表示される３Ｄモデル化オブジェクト２０００上での編集および／または作業に適合される。ソフトウェアツールは、ワークベンチにグループ分けされ得る。各ワークベンチは、ソフトウェアツールの部分集合を含む。詳細には、ワークベンチの１つが、モデル化された製品２０００の幾何学的特徴を編集するために適している、編集ワークベンチである。操作において、設計者が、例えばオブジェクト２０００の一部をあらかじめ選択し、次いで、適切なアイコンを選択することによって、操作を開始する（例えば寸法、色などを変える）または幾何学的制約を編集する。例えば、一般的なＣＡＤ操作は、画面上に表示された３Ｄモデル化オブジェクトの打ち抜き（punching）および折り畳み（folding）のモデル化である。ＧＵＩは、例えば、表示された製品２０００に関連するデータ２５００を表示することができる。図２の例では、「フィーチャーツリー（feature tree）」として表示されたデータ２５００、およびそれらの３Ｄ表現２０００は、ブレーキキャリパおよびディスクを含んだブレーキ組立品に関係する。ＧＵＩはさらに、例えば、編集される製品の操作のシミュレーションをトリガするために、オブジェクトの３Ｄ方向付けを容易にするために、様々な型のグラフィックツール２１３０、２０７０、２０８０をさらに示す、または表示される製品２０００の様々な属性をレンダリングすることができる。カーソル２０６０が、ハプティックデバイスによって制御されて、ユーザがグラフィックツールと対話することを可能にし得る。
【００４４】
図３は、システムの一例を示し、ここではシステムは、クライアントコンピュータシステム、例えばユーザのワークステーションである。
【００４５】
この例のクライアントコンピュータは、内部通信ＢＵＳ  １０００に接続された中央処理装置（ＣＰＵ）１０１０と、同じくＢＵＳに接続されたランダムアクセスメモリ（ＲＡＭ）１０７０とを含む。クライアントコンピュータにはさらに、ＢＵＳに接続されたビデオランダムアクセスメモリ１１００と関連付けられた画像演算処理装置（ＧＰＵ）１１１０が設けられる。ビデオＲＡＭ１１００もまた、フレームバッファとして、当技術分野で知られている。大容量記憶デバイスコントローラ１０２０が、ハードドライブ１０３０などの大容量メモリデバイスへのアクセスを管理する。コンピュータプログラム命令およびデータを実体的に包含するのに適している大容量メモリデバイスは、例として、ＥＰＲＯＭ、ＥＥＰＲＯＭ、およびフラッシュメモリデバイスなどの半導体メモリデバイス、内蔵ハードディスクおよびリムーバブルディスクなどの磁気ディスク、光磁気ディスク、ならびにＣＤ−ＲＯＭディスク１０４０など、あらゆる形態の不揮発性メモリを含む。前述のいずれも、特別に設計されたＡＳＩＣ（特定用途向け集積回路）によって補完される、またはこれに組み込まれることがある。ネットワークアダプタ１０５０が、ネットワーク１０６０へのアクセスを管理する。クライアントコンピュータは、カーソル制御デバイス、キーボードなどのハプティックデバイス１０９０を含むこともある。カーソル制御デバイスが、クライアントコンピュータで使用されて、ユーザがディスプレイ１０８０上の任意の所望の場所にカーソルを選択的に位置付けることを可能にする。さらに、カーソル制御デバイスは、ユーザが様々なコマンドを選択し、制御信号を入力することを可能にする。カーソル制御デバイスは、システムへの入力信号のためのいくつかの信号生成デバイスを含む。一般的には、カーソル制御デバイスは、マウスとすることができ、信号を生成するためにマウスのボタンが使用される。あるいはまたはさらに、クライアントコンピュータシステムは、感応型パッド（sensitive pad）および／または感応型画面（sensitive screen）を備えることができる。サーバシステム（先に述べたように場合によりクライアントシステムと混同される）は、図３のものと同様であってよく、クエリを実行するための、バス１０００に接続された、またはハードドライブ１０３０に位置する、データベースをさらに有し、場合によりビデオＲＡＭ１１００およびＧＰＵ１１１０および／またはディスプレイ１０８０および／またはハプティックデバイス１０９０がない。
【００４６】
コンピュータプログラムが、コンピュータによって実行可能な命令を含むことができ、命令は上記システムに、図１の方法を行わせるための、および／またはデータベースを構築するための手段を含む。プログラムは、システムのメモリなど、任意のデータ記憶媒体に記録可能であり得る。プログラムは、例えば、デジタル電子回路で、またはコンピュータハードウェア、ファームウェア、ソフトウェアで、またはこれらの組合せで、実装され得る。プログラムは、例えば、プログラム可能プロセッサによって実行されるように機械可読記憶デバイスに実体的に包含された製品など、装置として実装され得る。方法ステップは、プログラム可能プロセッサが、入力データ上で動作し、出力を生成することによって方法の機能を行う命令のプログラムを実行することによって行われ得る。プロセッサはしたがって、データストレージシステム、少なくとも１つの入力デバイス、および少なくとも１つの出力デバイスから、データおよび命令を受け取る、ならびにこれらにデータおよび命令を送るように、プログラム可能であり、結合され得る。アプリケーションプログラムは、ハイレベルな手続き指向もしくはオブジェクト指向プログラミング言語で、または必要に応じてアセンブリ言語もしくは機械言語で、実装され得る。いずれの場合も、言語は、コンパイル型言語またはインタプリタ型言語とすることができる。プログラムは、完全インストールプログラム、または更新プログラムとすることができる。システムでプログラムを適用することは、結果としていずれの場合も方法を実行するための命令となる。
【００４７】
方法は、３Ｄモデル化オブジェクトを設計するプロセスの一部であってよい、または方法は、そのようなプロセスの後に続いてよい。「３Ｄモデル化オブジェクトを設計すること」は、３Ｄモデル化オブジェクトを精巧に作り上げる工程の少なくとも一部であるいかなるアクションまたは一連のアクションも示す。したがって、方法は、例えばスケッチのような工程により、（ユーザによって）ゼロから第１の３Ｄモデル化オブジェクトを作成することを含み得る。次いで方法は、図１に従ってクエリを（ユーザコマンドで、または自動の、バックグラウンドプロセスとして）実行することを含み得る。次いで方法は、オプションとして結果をユーザに表示することと、（少なくとも１つの結果がある場合は）望ましい結果を（ユーザによって）選択することとを含み得る。最終的にユーザは、クエリ（例えば、選択されたもの）の結果を修正することによって設計を続けることができる。したがってこれは、設計者が以前に設計されたモデルを不必要に再び設計しないように、および代わりにそのような以前の設計を再利用するように支援するのに役立つことができる。しかしながら、図１によるクエリを実行するいかなる他の理由も検討され得る。例えば、方法は、（例えば、冗長をなくすことによってデータベースのサイズを縮小するために）データベースから重複する（またはほぼ重複する、すなわち非常に相似な）３Ｄモデル化オブジェクトを探し出す、および例えばこれを削除するために使用され得る。
【００４８】
この方法は、製造工程に含まれることが可能であり、製造工程は、この方法を行った後、モデル化オブジェクトに対応する物理的製品を生産することを含むことができる。いずれの場合も、この方法によって設計されるモデル化オブジェクトは、製造オブジェクトを表すことができる。モデル化オブジェクトは、したがってモデル化立体（すなわち、立体を表すモデル化オブジェクト）であり得る。製造オブジェクトは、部品、または部品の組立品などの、製品であり得る。この方法は、モデル化オブジェクトの設計を改善するので、この方法は、製品の製造もまた改善し、したがって製造工程の生産性を向上させる。
【００４９】
次に図１の方法についてより詳細に説明する。
【００５０】
この方法は、機械部品を表す３Ｄモデル化オブジェクトを含んだデータベースにクエリを実行するためのものである。データベースにクエリを実行することは、データベースエンジニアリングにおけるそのような式の伝統的な意味（classical meaning）によりデータベースでクエリが実行されることを意味し、データベースからの情報が、クエリの結果（場合により、ヌル）としてデータベースから抽出されることである。この方法の場合、データベースの３Ｄモデル化オブジェクト（すなわち、その任意の特徴データ）が返され、場合により、ダウンロードするさらなるデータをユーザが選択および／またはユーザがトリガする。これは、データベースエンジニアリングにおいて、特に３Ｄ相似性探索へのその適用において、本質的にすべて知られている。
【００５１】
知られているとおり、クエリは、任意の型の１つの基準または任意の型の複数の基準に従って行われ得る。次いで、データベース中のデータが、非常に伝統的である１つ／複数の基準に関連する範囲に基づいて、結果が提供される（１個、数個、またはヌル）。この方法の場合、クエリは、少なくともいわゆる類似性基準（場合により、類似性基準のみ）、言い換えれば類似性に関連する基準を含む。それは、定義により、潜在的結果（この時点では、データベースのデータ）がこの基準（これは伝統的に対処され得る実施の詳細であるので、例えばクエリに重みを用いて、いくつかの基準に対応するという問題は除外する）に照合する範囲が、情報が結果と考えられるべきかどうかを評価するために評定されることを意味する。この範囲がいかに正確に評定され得るかは、実施の問題である。この範囲は、２値（３Ｄモデル化オブジェクトの形状記述子値が、類似性基準に関連するかしないか）であってよい、またはこれは、漸進的なものとすることができる（２レベルの関連よりも厳密に、場合により最小値、例えばゼロから最大値、例えば１までの連続体、例えば、基準が入力と同一である結果であるとき、２つの同一の形状記述子値に対応する）。また、それぞれの３Ｄモデル化オブジェクトに対して評定される範囲に基づいて、それぞれの３Ｄモデル化オブジェクトが返される結果であるかないかがいかに正確に決定されるかも実施の問題である。例では、この方法は、あらかじめ定められた数の最も関連のある結果（例えば、他のものよりも類似性基準を「関連する」３Ｄモデル化オブジェクト）のみ、または１つ（例えば、「最も関連する（most respecting）」もの）のみを返し得る。後に説明する例では、類似性基準が関連する範囲は２値であり、その例では、方法は、すべての「関連する」３Ｄモデル化オブジェクトを返し得、これは、すべての結果がユーザに、少なくとも１度、表示されることを暗示するものであり、例えば、そのために、場合によりユーザからのスクロールアクションが必要とされる。
【００５２】
次に、類似性基準は、入力３Ｄオブジェクトに関連するデータベースの３Ｄオブジェクトの類似性に関連している。そのような類似性の定義は、以下に提供し、それは、すべての考えられる３Ｄモデル化オブジェクトのための方法の状況で決定された（例えば、計算された）、あらかじめ定められた形状記述子の定義に密接に結び付けられると言うことができる。方法における「類似性」（「相似性」とも呼ばれる）は、先に定義した現実の（ユーザによって観察される）３Ｄ相似性／類似性のプロキシ（proxy）／尺度（measure）である。定義により、あらかじめ定められた形状記述子の第２の値に対するあらかじめ定められた形状記述子の第１の値の類似性は、同じ相似変換を法として、あらかじめ定められた形状記述子の第２の値の軸系の集合が、あらかじめ定められた形状記述子の第１の値の軸系の集合に照合する範囲に次第に左右される（すなわち、それはその増加関数である）。この時点で、類似性はそのような任意の増加関数であり得ると言うことができる（後に例を提供する）。したがって類似性基準は、そのような尺度（例えば、達成されるもしくは達成されない閾値、または範囲）に関連する任意の基準である。照合する範囲がどのようにして正確に測定され得るかは、後に示すが、ここでは、あらかじめ定められた形状記述子は正確には、それが（特に）少なくとも３Ｄメッシュによってモデル化され、形状が似ている場合に概ね照合（almost matching）が存在する、方法の状況における３Ｄモデル化オブジェクトの３Ｄ形状の記述であるので、類似性値の関数は、３Ｄ幾何学的形状の曲面の観点から、および相似変換を法として、２つの３Ｄモデル化オブジェクトが互いにどのように似ているかを測定することであると言うことができる。
【００５３】
したがって類似性基準は、データベースの３Ｄモデル化オブジェクト（またはその一部またはその組立品、そのような一部または組立品は３Ｄモデル化オブジェクトそのものとして見られ得るためである）が、入力３Ｄモデル化オブジェクト（またはその一部、システムが適切な機能性を提供する場合、入力の一部が、入力そのものとして見られ得るからである）に似ているとき、いっそう関連付けられる。この類似性は、３Ｄオブジェクト間の幾何学的相似性（幾何演算である相似変換と混同してはならない）に対応する。したがって類似性基準は、以下では「相似性基準」と呼ばれることもある。
【００５４】
先に述べたように、データベースの３Ｄモデル化オブジェクトおよび入力３Ｄモデル化オブジェクトは、それぞれ少なくとも３Ｄメッシュによって定義される。しかしながらこの定義は、入力３Ｄモデル化オブジェクト（探索されるオブジェクト）の形状記述子値およびデータベースの３Ｄモデル化オブジェクト（それらが類似性基準により入力オブジェクトに似ている、または「相似である」場合、返される可能性のある、テストされるオブジェクト）の形状記述子値が提供され、正しく整理される限り、クエリは実行され得るので、純粋に固有であり得る（一例では、方法は、３Ｄメッシュ上にデータなしで行われ得る）。メッシュは、頂点（３Ｄ位置）と、頂点を２つずつ結ぶ辺（例えば、直線または曲線の線分）とで、任意のグラフ構造を示す。この方法の状況では、頂点および辺は、３Ｄモデル化オブジェクトによって表される機械部品のエンベロープ（すなわち、外側の曲面）を（幾何学的に）表す面を形成する。境界表現フォーマット（Ｂ−Ｒｅｐ）は、この方法によって検討される一般的な種類のメッシュであるが、他の型のメッシュ（テッセレーションまたはＣＧＲ−Catia Graphic Representationなど）も検討され得る。
【００５５】
この状況において、方法は、形状記述子を使用し、その値は、（少なくとも、後に説明する例のように、追加の記述データが可能であるので）三面軸系（すなわち、ベクトルの三重項（triplet）が三面体を形成する）の特定の集合を含むものと定義される。先に述べたように、軸系の集合は、頂点につき、および面につき（すなわち、頂点／面ペアにつき）、１つの軸系があるように定義される。また、各軸系は、あらかじめ定められた一貫性のある方式により定義される。特に、それぞれの軸系の軸は、特定の方法で方向付けされる。後に一例を提供する（例えば、一貫性のある並進および／または一貫性のある回転によって、同じ結果に至る単に数値上の変動（mathematical variation）に関して一般性を失うことはない）。ここで、向きは、少なくとも、それぞれの頂点に接続される（３Ｄメッシュの）辺の、それぞれの頂点における方向に、３Ｄモデル化オブジェクトによって表される機械部品のエンベロープに垂直な、それぞれの頂点における方向に（それぞれの頂点では、法線方向が３Ｄモデル化オブジェクトのデータ中で定義される、例えばそれぞれの頂点において、例えば３Ｄメッシュに関連付けられる、またはそのようなデータから検索可能もしくはプロキシ化可能である）、および機械部品の外側に対応する面の（先に定義された法線方向の）向きに、基づく（向きの規則（convention）が一貫して適用されることを意味する）と言うことができる（例えば、矢印は法線方向にそれぞれの頂点で機械部品によって定義される立体の外側に向いているが、計算の逆転を法として、向きは、機械部品の内側にも対応すると見られ得ることは明らかであり、実際に向きは、単にそのような「外側」および「内側」を指し、したがって方法は、任意の向きが選択されるという条件で、開いたスキンにも同じく適用可能である）。さらに、軸系は、（すべて）ノルムが定義されている、またはされていないことがある。後に提供する一例では、軸系は、ノルムが定義されていないが、それらは３Ｄモデル化オブジェクトのグローバルサイズを示す追加データを添付される。代替では、形状記述子値は、正確に軸系の集合から成ることができ、軸の長さが（例えば、所与の形状記述子値のすべての軸に対して同じである）グローバルサイズを伝える。
【００５６】
この幾何学的形状フレームワークによれば、第２のオブジェクトのためのあらかじめ定められた形状記述子の値の軸系の集合が、第１のオブジェクトのためのあらかじめ定められた形状記述子の値の軸系の集合に照合するとき、第２の３Ｄモデル化オブジェクトが、類似性の意味においていっそう相似したまたは似ている第１の３Ｄモデル化オブジェクトであり、（例えば、第２のオブジェクトは、データベースのテストされる３Ｄモデル化オブジェクトであり、入力として第１のオブジェクトに基づいてクエリが実行されるとき、テストされて結果として返されるまたは返されない）同じ相似変換を法とする。言い換えれば、方法は（事実上）、第２のオブジェクトの形状記述子からできる限り多くの（事実上またはほぼ「すべての」）軸系を、第２のオブジェクトの形状記述子のそれらに例えば正確に、またはあらかじめ定められた許容範囲で（幾何学的に）照合する軸系に変換する（単一の、「同じ」）相似変換（すなわち、本質的に知られているが、後に詳細に説明する所与の型の幾何学的変換）を探す。照合の範囲は、一般的に、それが幾何学的観点から妥当である限り、いかなる方法でも測定され得、完全照合（すなわち、最大範囲）は、軸系の一方の集合を正確に軸系の他方の集合に変換する相似変換がある状況に対応する。この測定において、「最良の」相似変換が検討され得ること（すなわち、照合の最大範囲を達成するもの）に留意されたい。言い換えれば、照合の範囲は、潜在的な相似変換の空間（例えば、一例ではすべての相似変換の空間）で照合の最大範囲であり得る。
【００５７】
一例では、あらかじめ定められた形状記述子の第２の値のそれぞれの軸系に関連する面が、所与の相似変換を法として、あらかじめ定められた形状記述子の第１の値のそれぞれの軸系に関連する面に照合する場合に限り、あらかじめ定められた形状記述子の第２の値のそれぞれの軸系が、あらかじめ定められた形状記述子の第２の値の軸系の集合があらかじめ定められた形状記述子の第１の値の軸系の集合に照合する範囲において、所与の相似変換重みを法として、あらかじめ定められた形状記述子の第１の値のそれぞれの軸系に照合するということ。言い換えれば、この例の方法は、単に面単位で、軸系照合と見なす（すなわち、入力の面に関連する軸系は、面間に照合がある場合、例外なく、結果のそれぞれの面に関連する軸系にすべて照合すると考えられ、そうでない場合、入力の面の軸系には全く照合がないと考えられる）。次に、第１の面の関連するすべての軸系が、（所与の相似変換を法として）第２の面に関連する軸系に照合する場合、第１の面が、第２の面に照合すると考えられ得る。さらなる条件（「完全な形状識別子」概念に関して後に一例を説明する）が、要求されることがある、または要求されないことがある。
【００５８】
そのような場合、あらかじめ定められた形状記述子の第２の値の軸系の集合が、あらかじめ定められた形状記述子の第１の値の軸系の集合に照合する範囲は、次いで、所与の相似変換を法として、あらかじめ定められた形状記述子の第１の値の軸系に関連する面に照合するあらかじめ定められた形状記述子の第２の値の軸系に関連する面の比率（例えば数の比率として、または面積の比率として、いずれかの方法で計算される）として所与の相似変換に対して簡単に評定され得る。
【００５９】
この例では、あらかじめ定められた形状記述子の（すなわち、データベースにあり、テストされる「第２の」３Ｄモデル化オブジェクトのための）第２の値に対するあらかじめ定められた形状記述子の（すなわち、「第１の」入力３Ｄモデル化オブジェクトのための）第１の値の類似性は、考えられる相似変換（場合によりすべての相似変換）のあらかじめ定められた空間にわたって、この方法で、空間の同じ所与の考えられる相似変換（すなわち、最適化プログラムの引数）を法として第２のオブジェクトの３Ｄメッシュの面に完全に照合すると評定される（第１のオブジェクトの３Ｄメッシュの面の総数における）第１のオブジェクトの３Ｄメッシュの面（の数）の比率の最大値に等しい（または、そのプロキシ）。オプションとして、比率計算（ratio calculus）に、面の面積に対応する重みが導入され得る。次に、第１の面と第２の面との間にそのような完全照合を有する必要条件は、第１の面に関連するすべての軸系が、所与の考えられる相似変換によって変換されるとき、第２の面のすべての軸系に完全に照合することであり得る。後にも説明するように、そのような必要条件は、十分であることもあるが、あるいは単に第１のフィルタとして機能し、次いで他の条件が評価されなければならないことがある。言い換えれば、この例では、完全照合が面単位で評価され、次いで完全照合する面の比率が評価される。この比率が、あらかじめ定められた閾値（テストされた実施の７０％）を超えている場合、第１のオブジェクトは、第２のオブジェクトに似ているまたは相似であると考えられる。あるいは、（例えば、厳密には３つ以上の値から、例えば連続体から採用される）類似性の漸進的レベルが、上述の比率に対応するものとして提供され得る。この面単位の分析は、照合する軸系の単なるグローバル比率（しかしながらこれは代替的に実施され得る）に比べて、（機械設計の観点から）より関連のある結果の出力を可能にする。
【００６０】
方法の特定の形状記述子の値は、したがってメモリサイズの点から比較的小さく（ベクトルのみ）、比較的速く決定され得る。所与の３Ｄモデル化オブジェクトのための形状記述子の値は、（局所軸系の向きにおける法線および向き情報の使用によって）３Ｄモデル化オブジェクトの幾何学的形状、およびその曲面についての局所情報を取り込む。その結果として２つの３Ｄモデルの類似性は、高速に評価され得る。形状記述子は、唯一の比較ツールとして使用され得るが、形状記述子は、（この方法がやはり含み得る別の精密な形状記述子との後の比較を少なくするために）第１のフィルタとして使用されることも可能である。使用する特定の数学的計算は、機械設計の分野において特に賢明であると思われ、（３Ｄ幾何学的相似性の観点から）関連のある結果が提供されることにつながる。また、類似性が保持されることは、比較における曲面の規範性（canonicity）を維持し、これは間接的に、曲面によって表される部品の機械的機能に、またはそれらの製造工程に関連する。言い換えれば、この方法によって検討される形状記述子は、機械設計の観点から重要である幾何学的情報に注目する。
【００６１】
一実装形態では、図１の方法は、以下により行われ得る：
−  Ｓ１：入力３Ｄモデル化オブジェクトの形状記述子値を含んだクエリが、閾値比率（あるいは比率の範囲）とともに提供される。形状記述子値は、少なくとも軸系と、頂点および面の関連付けデータ（したがって、何らかの位相的データ）とを含む。
−  Ｓ２：データベースの各３Ｄモデル化オブジェクトに対して行われる次の工程により、ヌル、１またはいくつかの結果を返す（考えられる事前順序付けおよび／または事前フィルタリングは、この説明の範囲外である）：
テスト入力３Ｄモデル化オブジェクトの各面について（後に述べるように、面の複雑さに基づいた事前順序付けが適用され得る）：
データベースの候補３Ｄモデル化オブジェクトの各面について（すでに適用されたように、同じ事前順序付け、またオプションとして、例えば同じ数の頂点および／またはナイフ（knife）／スムーズ（smooth）頂点の同じ構成など、同じ複雑さを有していない面をフィルタリングで除去することが、適用され得る）：
型のあらかじめ定められた集合の各相似変換型について（例えば、後の説明で述べるすべての型は、それらが後の説明に登場するときオプションとしてあらかじめ順序付けられている）
・  あらかじめ定められた方法で（後に例を示す）、テスト入力の面の形状記述子と候補の面の形状記述子との間の（例えば、完全）照合を保証する型の候補相似変換を探索する。ここで、一方の面のすべての軸系が、他方の面において照合を有することが検証され得る。また、ここで、関連寸法（relevant dimension）が、候補相似変換により（例えば、そのような変換のスケーリングを法として）互いに照合することが検証され得る。これは、後に述べる軽い形状記述子部分である。オプションとして、さらに（および先の検証が肯定的である場合）、テスト入力の面のサンプリングが、候補変換を法として候補のサンプリングに照合することが検証され得る（同じ型のサンプリングは、例えば単なる距離比較によって使用される）。
・  候補変換が見つからなかった場合、Ｆｏｒループを抜け出て、別の面に進む（すべての面が点検された場合、データベースの別のオブジェクトに進む）。
・  候補変換が見つかった場合：
○  それが閾値よりも高い面の比率に対して（候補変換を探索するときと同じように）照合を保証することを検証する
○  そうである場合、候補オブジェクトを結果として返す。
○  さもなければ、新しい候補変換を探す。
【００６２】
（上記のいずれかと、またそれらの間で組み合わせられ得る）図１の方法の他の例について、次に図４〜図３１を参照して説明する。
【００６３】
方法の実施の一般的な例について、次に図１８を参照して説明するが、これはＢ−Ｒｅｐによって定義されるオブジェクトに関して説明した例と組み合わせられ得る。
【００６４】
この一般的な例では、方法は、立体（またはスキン）モデルのための形状記述子の定義に基づく。この形状記述子は、上述の例のいずれかにおいて定義されるように、立体の頂点に添付された局所軸系に基づく。形状記述子は、３Ｄ変換の下で不変ではないが、この問題は、この例の方法のモジュールとして動作する比較アルゴリズムによって考慮される。
【００６５】
比較アルゴリズムの入力データは、テスト立体と、候補立体と、相似型と、相似性基準（すなわち類似性基準）とを含む。相似型は、剛体運動、鏡映、正のスケーリング、および負のスケーリングの中から、（アルゴリズムで、すなわちあらかじめ定められた方法で）選ばれ得る。この例の比較アルゴリズムは、２つのステップを反復して実行する。第１のステップは、テスト立体を候補立体に（部分的に）変換し得る候補相似変換を計算することである。このステップは、相似型を含むが、相似性／類似性基準は含まない。第２のステップは、候補相似変換が実際に、テスト立体の十分に大きな部分を候補立体に変換するかどうかをチェックする（先に述べた「比率」に対応する）。このステップは、この基準が閾値比率である場合、相似性／類似性基準を含む。答えが「はい（yes）」である場合、テスト立体および候補立体は、相似と考えられ、アルゴリズムは停止する。そうでない場合、新しい候補相似変換が探索される。図１８は、反復プロセスを示している。アルゴリズムがテスト立体および候補立体は相似ではないと出力する場合、別の相似型を使用して新しい探索が行われ得る。
【００６６】
一例では、候補相似変換をテストするステップにおいて、テストされる候補が、最も複雑な面を最初に見ることによって得られ得る（複雑さは、ナイフ／スムーズ頂点の数および／または面の頂点の数の増加関数である）。これは、そのような面において考えられる候補相似変換が（それらが複雑であり、ランダム相似変換との照合に至りそうにないので）より少なく、それによってある種のフィルタリングを実現するからである。
【００６７】
（Ｓ１において入力され、データベース中で探索され、Ｓ２において返される）一例の３Ｄモデル化オブジェクトについて、次に説明する。
【００６８】
この例では、モデル化オブジェクトのＢ−Ｒｅｐは、それらを定義する３Ｄメッシュと考えられる。境界表現は、３Ｄオブジェクトをそのエンベロープ（すなわち、その外側の曲面）に関してモデル化するための広く知られているフォーマットである。したがってＢ−Ｒｅｐは、幾何データおよび位相データを含み得る特定のフォーマットのデータを示す。幾何データは、３Ｄ位置に関して記述されるエンティティである、幾何エンティティを提供するデータである。位相データは、幾何エンティティへの参照および／または他の位相エンティティとの関係、例えば相対的位置付けに関して記述されるエンティティである、位相エンティティを提供するデータである。一般的に、関係は、位相エンティティを他の位相エンティティに関連付け、それによってそれらが位相的に境界付けされる、「によって境界付けされる」関係を含み得る。
【００６９】
この例の場合、（例えば、幾何）データは、少なくとも、いわゆる「支持曲面」、例えばパラメトリック曲面（すなわち、２Ｄ領域を定義するパラメータに関連する３Ｄ位置に関してモデル化された３Ｄ曲面）を含み得る。支持曲面は、一般的に、ＮＵＲＢＳ曲面とすることができるが、平面、標準曲面（canonical surface）、または手続き型曲面（procedural surface）とすることもできる。また（例えば、位相）データは、少なくとも面の集合を含み、各面は、（幾何データによって提供される）それぞれの支持曲面の境界付けされた部分として定義される。したがって、面が、切り取られた曲面に対応する。支持曲面はしたがって、面が切り取り動作によっていずれかの方法で定義される（それによって面を「支持する」）曲面である。
【００７０】
Ｂ−Ｒｅｐの概念は、広く知られているが、これについて、Ｓ１において提供され得るモデル化オブジェクトの一例を通して次にさらに説明する。しかしながら、例えば、少なくともいくつかの位相エンティティについて、「によって境界付けされる」関係とは異なる関係を有する、Ｂ−Ｒｅｐの他の例が、方法によって検討され得る。
【００７１】
すでに述べたように、モデル化オブジェクトのＢ−Ｒｅｐが、位相エンティティおよび幾何エンティティを含むことができる。幾何エンティティは、曲面（例えば、平面）、曲線（例えば、線）、および／または点である、３Ｄオブジェクトを含むことができる。曲面は、２つのパラメータの関数として提供され得る。曲線は、単に１つのパラメータの関数として提供され得る。また点は、３Ｄ座標として提供され得る。位相エンティティは、面、辺、および／または頂点を含むことができる。定義により、面は、支持曲面と名付けられる、それぞれの曲面の境界付けされた部分に対応する。「面」という用語は、したがって、曲面のそのような境界付けされた部分、または２Ｄ領域の対応する境界付けされた部分を区別なく示すことができる。同様に、辺は、例えば支持曲線と名付けられる、曲線の境界付けされた部分に対応する。「辺」という用語は、したがって、曲線の、またはその領域のそのような境界付けされた部分を示すことができる。頂点は、３Ｄ空間における点へのリンクと定義され得る。これらのエンティティは、次のように互いに関連している。曲線の境界付けされた部分は、曲線上にある２つの点（頂点）によって定義される。曲面の境界付けされた部分は、その境界によって定義され、この境界は、曲面上にある辺の集合である。面の境界の辺は、頂点を共有することによってともに接続される。面は、辺を共有することによってともに接続される。定義により、２つの面は、それらが辺を共有する場合、隣接している。同様に、２つの辺は、それらが頂点を共有する場合、隣接している。曲面、曲線、および点は、それらのパラメータ化により、ともに結び付けられ得る。例えば、曲線を定義するパラメトリック関数のパラメータの値が、境界頂点（bounding vertex）を定義するために提供され得る。同様に、曲線のパラメータを曲面の２つのパラメータに結び付ける関数が、境界辺（bounding edge）を定義するために提供され得る。しかしながら、Ｂ−Ｒｅｐのそのような位相データの非常に詳細な構造は、本説明の範囲外である。
【００７２】
図４および図５は、Ｓ１において提供されたモデル化オブジェクトであり得、図に１、２、および３という番号が付けられた３つの面：上の平面１および２つの円柱側面２および３で作られた円柱形スロット８０のＢ−ｒｅｐモデルを示す。図４は、スロット８０の斜視図を示す。図５は、すべての面の分解組立図を示す。重複番号は、辺および頂点の共有を示す。面１は、平面の境界付けされた部分である。面１の境界は、辺４および辺５を含み、それらのそれぞれが、頂点１０および頂点１１によって境界付けされる。それらはともに、同じ支持円を有する。面２は、すべて無限円柱曲面（すなわち、面２の支持曲面）にある辺６、８、５、および１３によって境界付けされる。面１および面２は、それらが辺５を共有するので隣接している。面２および面３は、それらが辺８および辺１３を共有するので隣接している。面１および面３は、それらが辺４を共有するので隣接している。
【００７３】
図６は、スロット８０のＢ−Ｒｅｐモデルの「によって境界付けされる」位相関係を示す。上位層１０１の節点は面であり、中間層１０３の節点は辺であり、下位層１０５の節点は頂点である。図７および図８は、位相エンティティ（面、辺、頂点）と支持幾何学的形状（無限円柱、無限平面、無限直線、点）との関係を示す。ＣＡＤシステムでは、Ｂ−ｒｅｐモデルは、「によって境界付けされる」関係および位相エンティティと支持幾何学的形状との関係と、支持幾何学的形状の数学的記述とを、適切なデータ構造で集める。言い換えれば、図６および図７に示すデータ構造は、幾何データの幾何エンティティへのリンク（これは図７である）、および位相エンティティ間のリンク（これは図６である）を含む、この例の位相データの一部である。
【００７４】
この例の方法に使用される様々な数学的概念、表記法、および定義について、次に説明する。
【００７５】
恒等写像
【００７６】
【数３】
2016224944.tif 000005
【００７７】
が
【００７８】
【数４】
2016224944.tif 000006
【００７９】
と示される。
【００８０】
点の集合は、三次元空間
【００８１】
【数５】
2016224944.tif 000007
【００８２】
の部分集合である。
【００８３】
定義により、３Ｄ変換（または略して変換）は、Ｌが線形写像であり、Ｔが並進ベクトルである場合Ｄ（ｘ）＝Ｌｘ＋Ｔによって定義される、写像Ｄ：
【００８４】
【数６】
2016224944.tif 000008
【００８５】
である。計算のために、変換Ｄは、行列Ｌと、並進ベクトルＴとを含む４×４行列によって有利に表される。以下のように示される：
【００８６】
【数７】
2016224944.tif 000009
【００８７】
４×４行列は、
【００８８】
【数８】
2016224944.tif 000010
【００８９】
これはまた、略して示される。
【００９０】
【数９】
2016224944.tif 000011
【００９１】
点
【００９２】
【数１０】
2016224944.tif 000012
【００９３】
の位置は、次のように計算される。４つ目の座標は常に１であるので、結果として生じる点の最初の３つの座標が意味を持つ。
【００９４】
【数１１】
2016224944.tif 000013
【００９５】
このように、４×４行列代数を使用して、変換の合成および逆転が行われる。実際に、
【００９６】
【数１２】
2016224944.tif 000014
【００９７】
および
【００９８】
【数１３】
2016224944.tif 000015
【００９９】
回転は、軸および角度によって定義される。鏡映は、点の集合を平面に対してその鏡像に変える。鏡映の行列は、Ｉ−２ＮＮTであり、ここでＮは、鏡面の単位法線ベクトルである。回転および鏡映は、スカラー積を保存するので、これらは等長である。式Ｄ（ｘ）＝Ｌｘ＋ＴにおいてＬが回転である場合、Ｄは剛体運動である。
【０１００】
均等スケーリングが、点の集合をより大きいまたはより小さい点の集合に変え、割合を保存する。より正確には、均等スケーリングＳが、距離に正の係数：‖Ｓｘ−Ｓｙ‖＝λ‖ｘ−ｙ‖、ここでλ＞０、を掛ける。均等スケーリングの行列Ｌは、λＩに相当する。
【０１０１】
反対に、不均等スケーリングは、そのＬ行列が
【０１０２】
【数１４】
2016224944.tif 000016
【０１０３】
に相当するので、割合を保存しない。ここでａ，ｂ，ｃ＞０は等しくない。この変換は、本発明の範囲外である。
【０１０４】
相似変換（または略して相似）は、回転、均等スケーリング、または鏡映の組合せである。正の相似は、ｄｅｔ（Ｌ）＞０のような変換である。負の相似は、ｄｅｔ（Ｌ）＜０のような変換である。剛体運動は、ｄｅｔ（Ｌ）＝１のような変換である。直観的に、正の相似は、鏡映を含まず、負の相似は、鏡映を含む。
【０１０５】
回転、均等スケーリング、および鏡映は可逆線形写像であるので、相似は、可逆である。次いで、ｙ＝Ｄ（ｘ）は、ｘ＝Ｄ-1（ｙ）、ここで（ｙ）＝Ｌ-1ｙ−Ｌ-1Ｔ、に相当する。
【０１０６】
Ｙ＝｛Ｄ（ｘ），ｘ∈Ｘ｝、略してＹ＝Ｄ（ｘ）と示されるような相似Ｄが存在する場合、２つの点の集合ＸおよびＹは、相似であると言われる。
【０１０７】
先の概念は、立体または３Ｄメッシュの面に当てはまる（ただし、これに限定されない）。立体のＢ−ｒｅｐの面は、点の集合の役割を果たす。
【０１０８】
立体の面は、支持平面または曲面によって、および境界辺によって定義される。面は、立体の外向き法線ベクトルを備えている。境界辺は、この法線ベクトルに従って方向付けされる。境界辺は、頂点を共有することによって接続される。
【０１０９】
Ｂ−Ｒｅｐ例に適合された、形状記述子、その値に含まれる軸系の集合、および、あらかじめ定められた形状記述子の第２の値の軸系の集合が、同じ相似変換を法として、あらかじめ定められた形状記述子の第１の値の軸系の集合に照合する範囲を評価するための（したがって、第１の値に対応する第１の３Ｄモデル化オブジェクトとともに第２の値に対応する第２の３Ｄモデル化オブジェクトの間の類似性を測定し、その結果として類似性基準が繰り返される範囲を測定するための）ツールの例について次に説明する。
【０１１０】
３Ｄモデル間の比較（すなわち、類似性の測定）を行う、および相似（すなわち、３Ｄモデルが幾何学的変換を用いて別の３Ｄモデルに変換され得るかどうかを事実上評価するとき考えられる幾何学的変換）を見つけるために、各面は、いくつかの軸系（すなわち、形状記述子）を備えている。面の各頂点ｖにおいて（この場合も、よくあることであるが、頂点がいくつかの面に属するとき、操作は繰り返される）、軸系が、（Ｓ１の前に、または初期ステップとしてデータベースを構築中に、図１の方法によって）次の例のように作成され得る。原点Ｐの座標は、頂点ｖの座標である。Ｕと示される、第１のベクトルは、ｖの入力境界辺に接しており、したがってＵは、境界辺と同じように方向付けされている。Ｖと示される、第２のベクトルは、ｖの出力境界辺に接しており、境界辺方向に方向付けされている。「入力」および「出力」という語は、面の法線ベクトルに従った境界辺の位相的向きに関連する。第３のベクトルは、頂点ｖで計算される面の外向きの法線ベクトルＮである。Ｎは常にＵおよびＶと垂直であるにもかかわらず、軸系（Ｐ、Ｕ、Ｖ、Ｎ）は、概して一直線（direct）および直交ではないことがわかる。それにもかかわらず、ベクトルＵ，Ｖ、Ｎは、（先にも述べた）一例では正規化され得、‖Ｕ‖＝‖Ｖ‖＝‖Ｎ‖＝１であることを意味する。
【０１１１】
図９〜図１１は、半円柱面９０の軸系を示している。図９は、面９０と、その法線ベクトル９２とを示している。図１０は、法線ベクトル９２によって誘導される境界辺９４の位相的向きを示している。境界辺ａは、頂点ｖの入力辺である。境界辺ｂは、頂点ｖの出力辺である。図１１は、各境界頂点における軸系のベクトルＵ、Ｖ、Ｎを表示している。
【０１１２】
（一般的な場合である）頂点に接合している（incident）辺が接していない、つまりベクトルＵおよびベクトルＶが同一線上にない限り、軸系（Ｐ，Ｕ，Ｖ，Ｎ）は、縮退され（degenerated）ない。接合している辺が反対方向で接している場合、Ｕ＝Ｖである。そのような頂点は、図１２〜図１３に示すように、ナイフ頂点と呼ばれ得る。図１２は、辺ａおよび辺ｂが頂点ｖに接合しており、反対方向で互いに接していることを示している。図１３は、ベクトルＵおよびベクトルＶが、Ｕ＝Ｖであるので、頂点ｖで縮退されることを示している。接合している辺が同じ方向で接している場合、Ｕ＝−Ｖであり、この頂点は、図１４〜図１５に示すように、スムーズ頂点と呼ばれる。図１４では、辺ａおよび辺ｂが頂点ｖに接合しており、同じ方向で互いに接している。図１５は、ベクトルＵおよびベクトルＶが、Ｕ＝−Ｖであるので、頂点ｖで縮退されることを示している。これらの２つの場合、縮退されない軸系が、あらかじめ定義されたようにＰ、Ｕ、Ｎを保つことによって、およびＵおよびＮのクロス積としてベクトルＶを設定することによって、有利に構築され得、すなわち図１６〜図１７に示すように、Ｖ＝Ｕ×Ｎである。縮退される頂点のこの特定の、例示的管理が、クエリ中により正確な／適切な結果を提供する。
【０１１３】
すべての面のすべての頂点がさらに、形状記述子値に「スムーズ」、「ナイフ」、または「シャープ」とラベル付けされ得る。定義により、シャープ頂点は、スムーズでもナイフでもない頂点である。この分類は、相似変換が所与の型の頂点を常に同じ型の別の頂点に変えると見られ得るので、一例では（類似性の評定中の）局所軸系対応を加速させるために使用され得る。その結果として、２つの頂点ｖ、ｗが同じ型を有していない場合、ｖの局所軸系（Ｐv，Ｕv，Ｖv，Ｎv）をｗの局所軸系（Ｐw，Ｕw，Ｖw，Ｎw）に変えることができる相似は存在しないと、この方法によって考えられ得る。同じ加速が、所与の頂点において２つの辺の接線間の角度で適用され得る。この角度は、いかなる検討される相似によっても不変であると考えられ得る。そこで、２つの頂点ｖ、ｗが同じ角度を有していない場合、ｖの局所軸系をｗの局所軸系に変えることができる相似は存在しないと、この方法によって考えられ得る。
【０１１４】
軸系が、照合され、それによって２つの３Ｄモデル間の幾何学的詳細の照合を（詳細が相似変換を通して保たれるように）置き換えるように設計される場合、相似変換が、割合を維持するが距離を変更するスケーリングを含み得ることを思い起こされなければならない。そのようなスケーリングは、相似変換を探知するとき、追跡されなければならない。
【０１１５】
これは、いわゆる「面の関連寸法」を介して行われ得る。定義により、面の関連寸法は、そのサイズに左右されるが、その位置には左右されない、面上で測定されるスカラー量である。均等スケーリングを探索するとき、サイズ変化に対処することに、専念される。面の面積は、その関連寸法とすることができる。同様に、面ｆの関連寸法λは、その頂点の集合の寸法とすることができる。より正確には、ｆの頂点の集合として｛Ｐi，ｉ＝１，…，ｐ｝と示すと、λ＝ｍａｘ｛||Ｐｉ−Ｐｊ||，ｉ，ｊ＝１，…．ｐ｝である。この関連寸法は、スカラー値として個別に形状記述子値に記憶され得る（これはそうすることの最も効率的な方法である）、またはこの関連寸法は、係数として使用されて、軸系ベクトル（もはやノルムが定義されない）に適用され得る。
【０１１６】
次に異方性について説明する。
【０１１７】
面ｆを考えると、その２つの異方性因子ａ１およびａ２が次のように定義される。まず、面ｆの慣性の行列Ｍが、標準軸系に関して計算される。次いで、特性方程式ｄｅｔ（Ｍ−ｖＩ）＝０を使用することによって、行列Ｍの固有値ｖ１、ｖ２、およびｖ３が、計算される。ｖiが３つの異なる数である場合、それらはｖ1＜ｖ2＜ｖ3のように順序付けられ、異方性因子は：
【０１１８】
【数１５】
2016224944.tif 000017
【０１１９】
少なくとも２つの固有値ｖiが等しい場合、異方性因子は意味を持たない。これは、この状況では、主慣性軸系が一意的に定義されないからである。面ｆの主慣性軸系は、（Ｇ，Ａ1，Ａ2，Ａ3）と示される。定義により、点Ｇは、面ｆの慣性の中心であり、ベクトルＡiは、それぞれ固有値ｖiと関連する慣性行列Ｍの固有ベクトルであり、ＭＡi＝ｖiＡiであることを意味する。ベクトルＡiは、正規化され、主慣性軸系が一直線であるように方向付けされる。
【０１２０】
形状記述子は、（３Ｄモデル化オブジェクトのすべての面に対して）その面形状記述子のリストとして見られることが可能であり、その面形状記述子自体はそれぞれ、それぞれの面のいわゆる「軽い形状記述子」または「完全な形状記述子」であり得る。軽い形状記述子は、メモリサイズに関してより軽く、より少ない情報を含んでいるので、より速い決定につながる。完全な形状記述子は、より正確な評定を可能にする。軽い形状記述子は、ネットワークに過重な負荷をかけることを避けるために、リモートクライアント−サーバ通信の状況において使用され得る。あるいはまたはさらに、軽い形状記述子は、方法において評価される相似変換の数を制限するために使用され得る（すなわち、軽い形状記述子は、第１のフィルタリングとして働くことができる）。
【０１２１】
定義により、面ｆの軽い形状記述子ｓ（ｆ）は、頂点で定義される局所軸系およびその関連寸法のリストと合わせた、その支持曲面（平面、円柱、球体、錐体、環状体、押出し（extrusion）、回転（revolute）、自由形状）の型であり、
ｓ（ｆ）＝（Ｔｙｐｅ，｛（Ｐi，Ｕi，Ｖi，Ｎi），ｉ＝１，…，ｐ｝，λ）
ここでｐは、面ｆの頂点の数であり、
型
∈｛平面，円柱，錐体，球体，環状体，押出し，回転，自由形状｝
この記述子は、（例では）異方性因子および主慣性軸系が意味を持つとき、それらを追加することによって改良され得る。
ｓ（ｆ）＝（ａ1，ａ2，（Ｇ，Ａ1，Ａ2，Ａ3），Ｔｙｐｅ，｛（Ｐi，Ｕi，Ｖi，Ｎi），ｉ＝１，…，ｐ｝，λ）
したがって、定義により、ｎ個の面｛ｆ1，…，ｆn｝を含んだ立体Ａの軽い形状記述子ｓ（Ａ）は、面の軽い形状記述子のリストである：
ｓ（Ａ）＝｛ｓ（ｆ1），…，ｓ（ｆn）｝
しかし、Ｂ−Ｒｅｐの場合、それぞれの３Ｄモデル化オブジェクトのためのあらかじめ定められた形状記述子の値は、それぞれの３Ｄモデル化オブジェクトの各それぞれの面のために、それぞれの面によって定義される支持曲面の境界付けされた部分のサンプリング（この場合は「完全な形状記述子」）をさらに含み得る。サンプリングは、任意のあらかじめ定められた方法で、例えば割合を維持する規則により、行われ得る。例えば、標準的なパラメータグリッドサンプリングが適用され得る。この状況では、あらかじめ定められた形状記述子の第２の値に対するあらかじめ定められた形状記述子の第１の値の類似性は、あらかじめ定められた形状記述子の第２の値のサンプリングが、同じ相似変換を法としてあらかじめ定められた形状記述子の第１の値のサンプリングに照合する範囲に（軸系の集合が別の相似変換を法として互いに照合される範囲にだけでなく）さらに次第に左右され得る。完全な形状記述子の「軽い形状記述子部分」は、そのような場合、有望な相似変換のみを保持するために使用される第１の評価の基準となり得、次いでサンプリング比較は、保持された相似変換が実際に関連があるかどうかを検証するために使用される。言い換えれば、あらかじめ定められた形状記述子の第２の値に対するあらかじめ定められた形状記述子の第１の値の類似性は、各反復において、新しい候補相似変換を見つけること、次いで候補相似変換に従って類似性を評定することを含む方式の反復により評定され、新しい候補相似変換は、各反復において、単に軸系情報に基づいて見つけられる。これは、速いフィルタリングが慎重に適用されるので、方法の高速な実行を可能にする。
【０１２２】
一例では、完全な形状記述子は実際に、面自体とともに軽い形状記述子を含み、（Ｂ−Ｒｅｐが通常利用可能であるとき、データベースなどにすでにあるデータである）その位相および幾何学的形状を含む。立体の完全な形状記述子は、面の完全な形状記述子のリストである。サンプリングは、次いで、面の位相および幾何学的形状情報からオンザフライで行われ得る。
【０１２３】
図１８の一般的な例の方法は、そのようなＢ−Ｒｅｐに適用され得、したがって２要素から成る。一方では、それは、３Ｄ立体モデルのための形状記述子を定義する。他方では、それは、形状記述子に基づいた比較アルゴリズムを提供する。方法は、その境界表現（Ｂ−ｒｅｐ）によってモデル化され、機械的機構を使用することによって設計される３Ｄオブジェクトに対処することができる。機械的機構は、特に機械部品に適合された立体モデリング特徴である。これらの概念はよく知られているにもかかわらず、明確にするために、定義および例示をここで再現する。
【０１２４】
次の説明は、データベースの３Ｄモデル化オブジェクトおよび／または入力３Ｄモデル化オブジェクトが、機械設計工程によりユーザ定義である場合に当てはまる。この設計工程は、それぞれ方法の前（例えば、方法の一部として）および／またはデータベースの構築の前（例えば、データベース構築工程の一部として）とすることができる。そのような機械設計工程は、様々な設計者を含むことがある。しかし機械設計の分野は、いくつかの共通ルールが適用されることになる。
【０１２５】
機械設計工程は、立体モデリング機械特徴の（増分の）定義を含み得る。機械設計の特に有用な立体モデリング特徴は、次のものである。したがって、システム、つまり特徴に基づいたＣＡＤシステムは、そのような特徴のいずれかまたはいくつかの定義を提供され得る。機械設計工程は、したがって、次の特徴のいずれかまたはいくつかの１またはいくつかの例を含み得る。
【０１２６】
スケッチに基づく特徴が、一方向に沿って押し出される、線の周りを回転される、またはガイド曲線に沿って掃引される（swept）平面輪郭によって定義される。それらは、それぞれ直線押出し、回転、および掃引立体と名付けられている。
【０１２７】
ブール演算（特徴）は、和集合（union）、減算（subtraction）、または共通部分（intersection）演算を使用して、２つの立体を組み合わせることによって、新しい立体を作成することである。曲面によって立体を切り取ることもまた有用である。
【０１２８】
ドレスアップ（dress-up）特徴は、立体上の局所変更である。それらは、製造工程に密接に関係している。これらの特徴は、シャープ辺にフィレットを付けること（filleting）または丸くすること、シャープ辺を面取りすること、抜き勾配および引っ張り方向に従って面を曲げること、および面を厚くすることである。
【０１２９】
シェル化（特徴）は、厚い立体から薄い立体を作成することである。それは、入力立体から面を除去し、結果として生じる開いたスキンを厚くすることである。
【０１３０】
これらの特徴は、値または入力幾何学的形状など、任意のパラメータでインスタンス化され得る。この方法によって検討される任意の３Ｄモデル化オブジェクトのＢ−Ｒｅｐは、機械設計者が一連のそのような特徴をインスタンス化することによって得られ得る。
【０１３１】
図１９は、ストリンガー（航空機の構造を強化するための航空宇宙部品）の設計の一例を示しており、これは、左から右に順番に、図１の方法の任意の例の入力３Ｄオブジェクトまたはデータベース３Ｄオブジェクトであり得る。特徴の順序は、以下のようである：押し出す１９２、垂直壁から材料を除去する１９４、および押出しに従ってこの除去を繰り返す１９６。次のステップが、図２０に示され、左から右に順番に：面取りする２０２、左水平面から材料を除去する２０４、垂直壁に対してこの除去をミラーリングする２０６。
【０１３２】
同様に、図２１〜図２２は、航空宇宙用クリートの一連の設計の一例である。第１の設計ステップは、長方形輪郭の押出し２１２、４つの穴２１４、三角形輪郭の押出し２１６、および再び穴２１８である。輪郭定義に丸み付け（round）が含まれていることに注意されたい。次のステップは、三角形輪郭の２つの押出し２２２による補強材を追加することである。クリート設計の最後のステップは、フィレット２２４である。それらは、最終立体が、切削工具を用いて原料を機械切削することによって得られる部品の形状の特徴とするように配置される。
【０１３３】
あらかじめ定められた形状記述子の第２の値の軸系の集合があらかじめ定められた形状記述子の第１の値の軸系の集合に照合する範囲の評定において、所与の相似変換を法として２つの面が互いに照合するかどうかを評定する方法の例を、次に提供する。一例では、この評定は、所与の相似変換型（先に述べた相似型を指す）のためのあらかじめ定められた方法で行われる。ソフトウェア／システムのこの内面的な特性が、相似型の様々な潜在的な型の精密な管理を可能にする。これについて、様々な候補相似を探索する方法の例に関して述べるとともに、以下に説明する。
【０１３４】
ｆ、ｇがそれぞれ（同じ数の）局所軸系
【０１３５】
【数１６】
2016224944.tif 000018
【０１３６】
および
【０１３７】
【数１７】
2016224944.tif 000019
【０１３８】
ならびに同じ型を有する支持曲面を備えた２つの面であるとする。面ｆ、面ｇが、同じ数の局所軸系を有していない場合、それらは同じ数の境界頂点を有していないことを意味し、したがってそれらは一例では、互いと相似ではないと考えられ得、相似探索は起動されない。
【０１３９】
相似探索の一例は、２つのステップを通して行われる。第１に、面ｆのｉ番目の軸系を面ｇのｊ番目の軸系にそれぞれ変える変換Ｄi,jを計算する。ｉ，ｊ＝１，…，ｍであるので、最大ｍ2個のそのような変換が存在する。この計算は、探索される変換の型に、すなわち剛体運動、鏡映、正のスケーリング、負のスケーリングに左右される。第２に、ｆをｇに変える相似Ｄ*は、ある場合は、すでに計算されたＤi,jの中で見つけられることになる。この第２のステップは、変換の性質に左右されない。
【０１４０】
剛体運動Ｄi,jを探索する一例について、次に説明する。
【０１４１】
【数１８】
2016224944.tif 000020
【０１４２】
が面ｆのｉ番目の軸系であり、
【０１４３】
【数１９】
2016224944.tif 000021
【０１４４】
が面ｇのｊ番目の軸系であるとする。
【０１４５】
【数２０】
2016224944.tif 000022
【０１４６】
を
【０１４７】
【数２１】
2016224944.tif 000023
【０１４８】
に変える変換
【０１４９】
【数２２】
2016224944.tif 000024
【０１５０】
は、次の積を計算することによって得られる。
【０１５１】
【数２３】
2016224944.tif 000025
【０１５２】
次いで、Ｒi,jＲi,jT＝Ｉの場合、行列Ｒi,jは、等長変換である。さらに、ｄｅｔ（Ｒi,j）＝１の場合、Ｒi,jは回転であり、Ｄi,jは剛体運動であることを意味する。そうでない場合、Ｄi,jは剛体運動ではない。
【０１５３】
正のスケーリングＤi,jを探索する一例について、次に説明する。
【０１５４】
次に、探索される変換は、剛体運動と均等スケーリングの組合せである正の相似である。それは、次のように面ｆおよび面ｇの関連寸法λfおよびλgを考慮に入れる。
【０１５５】
【数２４】
2016224944.tif 000026
【０１５６】
ｄｅｔ（Ｒi,j）＞０の場合、Ｄi,jは正の相似であり、そうでない場合、Ｄi,jは正の相似ではない。
【０１５７】
鏡映Ｄi,jを探索する一例について、次に説明する。
【０１５８】
鏡映は、軸系の向きを逆にすることが特異である。図２３は、最も左の点で描いた立体が、中央の平面によって定義される鏡映Ｌによる最も右の立体のイメージであるという現象を示している。最も右の立体の上面は、ｆと示される。ベクトルＬ（Ｕf）およびベクトルＬ（Ｖf）に注目する。
【０１５９】
図２４は、２つの対称な立体と、それらの上面の位相的向きを示している。最も左の立体の上面は、ｇと示される。先の図と比較することによって、Ｌ（Ｕf）＝ＶgおよびＬ（Ｖf）＝Ｕgに気付く。その結果として、鏡映を見つけるために、位相的逆転が予想されなければならず、Ｄi,jは次の公式により計算されることを意味する。
【０１６０】
【数２５】
2016224944.tif 000027
【０１６１】
および
【０１６２】
【数２６】
2016224944.tif 000028
【０１６３】
は、最も右の行列において交換されていることに注目する。
【０１６４】
【数２７】
2016224944.tif 000029
【０１６５】
Ｒi,jＲi,jT＝Ｉおよびｄｅｔ（Ｒi,j）＝−１の場合、Ｄi,jは鏡映であり、そうでない場合、Ｄi,jは鏡映ではない。
【０１６６】
負のスケーリングＤi,jを探索する一例について、次に説明する。
【０１６７】
負のスケーリングを探索するための計算は、次のように、面ｆおよび面ｇの関連寸法λfおよび関連寸法λgを含む。
【０１６８】
【数２８】
2016224944.tif 000030
【０１６９】
および
【０１７０】
【数２９】
2016224944.tif 000031
【０１７１】
は、最も右の行列において交換されていることに注目する。
【０１７２】
【数３０】
2016224944.tif 000032
【０１７３】
ｄｅｔ（Ｒi,j）＜０の場合、Ｄi,jは負のスケーリングであり、そうでない場合、Ｄi,jは負のスケーリングではない。
【０１７４】
上記の例に沿ったＤ*の探索の一例について、次に説明する。
【０１７５】
（先に計算したＤi,jの中から）ｆをｇに変える相似変換Ｄ*を見つけるために、問題は、ｆ、ｇ、および相似変換Ｄと仮定すると、Ｄ（ｆ）＝ｇはｔｒｕｅかということである。
【０１７６】
計算が、クライアントコンピュータ上で行われる場合、これは（比較的より正確な結果を求めて）、３Ｄ点ｘk、ｋ＝１、…、ｑの収集で面ｆをサンプリングすることによって、および点Ｄ（ｘk）と、面ｇとの距離が、同一オブジェクトの数値閾値に比べて十分小さいことをチェックすることによって、行われ得る。このステップは、完全な形状記述子を使用する。
【０１７７】
計算が、サーバコンピュータ上で行われる場合、相似Ｄ*は、面ｆのすべての軸系を面ｇのすべての軸系に変えるＤi,jの１つである。言い換えれば、アルゴリズムは、すべてのｉ∈｛１，…，ｍ｝に対して
【０１７８】
【数３１】
2016224944.tif 000033
【０１７９】
のように、１対１マッピングΦ：｛１，…，ｍ｝→｛１，…，ｍ｝を探す。このステップは、軽い形状記述子を使用する。このステップは、それらが利用可能であるとき、主軸系および異方性因子を使用することによって短縮され得る。
【０１８０】
Ｄi,jの中で、いくつかの相似変換がｆをｇに変えることができる場合、可能であれば純粋な並進が選択される。相似変換型のいかなる階層も検討され得る。
【０１８１】
次に、上記の例のいずれかと組み合わせることができる比較アルゴリズムの一例について次に説明する。
【０１８２】
ｎがテスト立体の面の数であり、ｍが候補立体の面の数であるとする。テスト立体の面の形状記述子は、｛ｓ（ｆ1），…，ｓ（ｆn）｝である。候補立体の面の形状記述子は、｛ｓ（ｇ1），…，ｓ（ｇm）｝である。
【０１８３】
このアルゴリズムは、図１８に関して先に述べた２つのステップ「候補相似探索」および「候補相似確認」を別々に実施する。概して、各ステップは、｛ｓ（ｆ1），…，ｓ（ｆn）｝および｛ｓ（ｇ1），…，ｓ（ｇm）｝についてダブルループである。
【０１８４】
１つの「ｆｏｒ」ループから別のものへ自由に誘導するためには、次のアドレッシング公式（addressing formula）が有用である。関数Ｑ（ｐ，ｍ）が、ｐおよびｍの整数商を求め、Ｑ（ｐ，ｍ）は、ｐ≧ｍＱ（ｐ，ｍ）のような最大の整数であることを意味する。関数Ｍ（ｐ，ｍ）が、ｐをｍで割った余りを求める。言い換えれば：
ｐ≧ｍＱ（ｐ，ｍ）＋Ｍ（ｐ，ｍ）
整数ｐが１からｎｍになるとき、整数
ｒｏｗ（ｐ，ｍ）＝１＋Ｑ（ｐ−１，ｍ）
および整数
ｃｏｌ（ｐ、ｍ）＝１＋Ｍ（ｐ−１，ｍ）
はそれぞれ、図２５に示すように、ｎ行およびｍ列の配列の行番号および列番号である。
【０１８５】
「候補相似探索（candidate similarity searching）」ＣＳＳプログラムは、一例では、探索される相似の入力型Ｙと、複数の呼出し目的のための入力／出力パラメータｐ0と、見つけられた型Ｙ相似である出力パラメータＤ0とを含み得る。この「候補相似探索」プログラムのまさに最初の実行は、ｐ0＝０で行われる。このステップは、ある場合は、型Ｙ相似Ｄ0と、対応するインデックスｐ0とを出力する。このインデックスは、この探索が「候補相似探索」プログラムへの新規の呼出しにより再び行われるとき、再使用される。プログラムの中核は、次のようなものとすることができる。
【０１８６】
【表１】
2016224944.tif 000034
【０１８７】
先のステップが相似Ｄ0を返さない場合、例の工程は、候補立体およびテスト立体が相似ではないことを出力することを終了する。そうではない場合、「候補相似確認（candidate similarity confirmation）」ＣＳＣステップは、次のように実行される。番号ｋが、相似Ｄ0により、テスト立体の面と相似な候補立体の面の総面積を蓄積する。
【０１８８】
【表２】
2016224944.tif 000035
【０１８９】
Ａが候補立体の境界の面積であるとする。比
【０１９０】
【数３２】
2016224944.tif 000036
【０１９１】
がユーザ定義の相似性基準ｃ∈］０，１］よりも大きい場合、工程は、候補立体がテスト立体と相似であることを出力することを終了する。そうでない場合、「候補相似探索」プログラムは、入力パラメータとしてｐ0を用いて再び実行される。これは、探索が先の候補相似検出から始まることを強制する。工程全体は、図２６に表現されている。
【０１９２】
先に述べたオプション、すなわち形状記述子の事前順序付けについて、次に説明する。
【０１９３】
実験は、面の頂点の数が減少するに従って形状記述子が順序付けされるとき、計算時間が非常に少なくなることを示す。このように、最大数の頂点を特徴とする面の形状記述子が、最初に比較される。相似変換が存在する場合、それは、複雑な面を比較することによってより迅速に見つけられる。
【０１９４】
この現象を、図２７〜図２８に示している。図２７の立体の前面１は、図２８の立体の前面２および背面３と相似である。図２７の立体の前面４は、図２８の立体の前面５および背面６と相似である。反対に、図２７の立体の面７は、図２８の立体の面８と相似であるにすぎない。面７および面８は、それらが、４個ではなく８個の頂点を特徴とするので、それぞれの立体の最も複雑な面である。面７および面８を用いて探索を開始すると、最初の試みで正確な相似変換がもたらされる。
【０１９５】
先に述べた、この方法は普遍性を失わずに部分的探索に使用され得るということもまた、説明するに値する。部分的探索は、テスト立体上の特徴を識別し、特徴を含んだ候補立体を探索することである。特徴は、ユーザによって選択された関連のある面の集合である。
【０１９６】
この方法は、閉じた（方向付けされた）スキンの場合に使用され得るが、開いたスキンの場合にも使用され得るということもまた説明するに値する。相似計算は、軸系比較に基づく。この方法のロバスト性は、立体の幾何学的形状および位相によって定義される、これらの軸系の一意性に基づく。一意性は、立体のＢ−Ｒｅｐが閉じたスキンであるので、一意の位相的向きが定義され得るということから生じる。規則として法線ベクトルは、立体の外側の方を指す。開いたスキンを扱うとき、「内側」または「外側」体積が存在しないので、位相的向きは、一意ではない。実際に、開いたスキンは、図２９〜図３０に示すように、２つの考えられる向きの中から任意に選ばれた１つの位相的向きを特徴とする。一方の向きから他方の向きへ切り換えると、（Ｐ，Ｕ，Ｖ，Ｎ）軸系が（Ｐ，Ｖ，Ｕ，−Ｎ）に変わる。このために、相似診断が、テストスキンの元の向きで否定（negative）であった場合、その逆の向きでもう１つの計算が行われなければならない。
【０１９７】
先に述べた、この方法はＢ−Ｒｅｐ以外の他のデータフォーマットに広げられ得るということもまた、説明するに値する。相似計算に使用される軸系は、立体のＢ−Ｒｅｐ上に構築される。実際には、軸系計算を可能にする任意の立体モデリング表現が、たとえそれが完全なＢ−Ｒｅｐではなくとも、相似に使用され得る。（倍精度浮動小数点数とは対照的に）単精度浮動小数点数でコード化された、三角形分割（triangulated）データフォーマットで行われるテストもまた、主慣性軸系を使用するとより正確な相似認識がもたらされることを示した。
【０１９８】
先に述べたように、行われたテストは、この方法が機械設計の状況において相似な機械部品を正確に見つけ得ることを示した。テストケースは、図３１に示すように２つの立体を含んだ。立体Ａは、円柱の上部のＬ字型角柱である。立体Ｂは、平行六面体の上部のＬ字型角柱である。Ｌ字形角柱は、比例しており、立体ＡのＬ字形角柱の寸法は、立体ＢのＬ字形角柱の寸法の半分であることを意味する。この方法は、立体ＡのＬ字形角柱が立体ＢのＬ字形角柱と相似であることを認識することができる。相似変換は、本明細書では鏡映と均等スケーリングの組合せである。
【図１】
2016224944.tif 000037
【図２】
2016224944.tif 000038
【図３】
2016224944.tif 000039
【図４】
2016224944.tif 000040
【図５】
2016224944.tif 000041
【図６】
2016224944.tif 000042
【図７】
2016224944.tif 000043
【図８】
2016224944.tif 000044
【図９】
2016224944.tif 000045
【図１０】
2016224944.tif 000046
【図１１】
2016224944.tif 000047
【図１２】
2016224944.tif 000048
【図１３】
2016224944.tif 000049
【図１４】
2016224944.tif 000050
【図１５】
2016224944.tif 000051
【図１６】
2016224944.tif 000052
【図１７】
2016224944.tif 000053
【図１８】
2016224944.tif 000054
【図１９】
2016224944.tif 000055
【図２０】
2016224944.tif 000056
【図２１】
2016224944.tif 000057
【図２２】
2016224944.tif 000058
【図２３】
2016224944.tif 000059
【図２４】
2016224944.tif 000060
【図２５】
2016224944.tif 000061
【図２６】
2016224944.tif 000062
【図２７】
2016224944.tif 000063
【図２８】
2016224944.tif 000064
【図２９】
2016224944.tif 000065
【図３０】
2016224944.tif 000066
【図３１】
2016224944.tif 000067
【外国語明細書】
2016224944000001.pdf