(57)【要約】【課題】３次元モデル化オブジェクトを圧縮するためのコンピュータ実施方法を提供する。【解決手段】方法は、モデル化オブジェクトの境界表現を提供するステップと、基準関数の値域から別の関数の値域への写像を記述する第１のデータ、ならびに基準関数および基準関数の値域から別の関数の値域への写像が合成された場合、別の関数を適用したのと同じ結果をもたらす、別の関数の定義域から基準関数の定義域への写像を記述する第２のデータを決定するステップと、幾何学データにおいて、別の関数を、第１のデータ、第２のデータ、および基準関数を指すポインタによって置き換えるステップとを含む。  そのような方法は、３Ｄモデル化オブジェクトの圧縮を改善する。【選択図】図１
2014232534.tif 000002
【特許請求の範囲】
【請求項１】
３次元（３Ｄ）モデル化オブジェクトを圧縮するためのコンピュータ実施方法であって、
前記モデル化オブジェクトの境界表現を提供するステップ（Ｓ１０）であって、前記境界表現は、幾何学データを含み、前記幾何学データは、各々がそれぞれの幾何学的実体に対応する関数を含み、各関数は、定義域および値域を有する、ステップと、
基準関数の前記値域から別の関数の前記値域への写像を記述する第１のデータ、ならびに前記基準関数および前記基準関数の前記値域から前記別の関数の前記値域への前記写像が合成された場合、前記別の関数を適用したのと同じ結果をもたらす、前記別の関数の前記定義域から前記基準関数の前記定義域への写像を記述する第２のデータを決定するステップ（Ｓ４０）と、
前記幾何学データにおいて、前記別の関数を、前記第１のデータ、前記第２のデータ、および前記基準関数を指すポインタによって置き換えるステップ（Ｓ５０）と
を含むことを特徴とするコンピュータ実施方法。
【請求項２】
互いのコピーである幾何学的実体に対応する関数の組を決定するステップ（Ｓ２０）と、
各組内で前記組の基準関数を決定するステップ（Ｓ３０）と、
各組および前記組の前記基準関数以外の前記組の各関数について、前記第１のデータおよび前記第２のデータを決定する前記ステップ（Ｓ４０）ならびに置き換える前記ステップ（Ｓ５０）を繰り返すステップであって、前記第１のデータおよび前記第２のデータを決定する前記ステップ（Ｓ４０）の前記基準関数は、各回とも前記組の前記基準関数である、ステップと
を含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記関数は、パラメトリック関数を含み、前記基準関数の前記値域から前記別の関数の前記値域への前記写像、および前記別の関数の前記定義域から前記基準関数の前記定義域への前記写像は、アフィン写像であることを特徴とする請求項２に記載の方法。
【請求項４】
前記関数は、曲面定義を含み、前記基準関数の前記値域から前記別の関数の前記値域への前記写像は、前記基準関数に対応する曲面を前記別の関数に対応する曲面に変換する剛体運動であり、前記別の関数の前記定義域から前記基準関数の前記定義域への前記写像は、２Ｄ局所写像であることを特徴とする請求項３に記載の方法。
【請求項５】
前記関数は、それぞれの曲面定義の前記定義域内に含まれる値域を有するｐ曲線をさらに含み、前記基準関数の前記値域から前記別の関数の前記値域への前記写像は、前記別の関数の前記値域から前記基準関数の前記値域への２Ｄ局所写像の逆写像であり、前記別の関数の前記定義域から前記基準関数の前記定義域への前記写像は、１Ｄ局所写像であることを特徴とする請求項４に記載の方法。
【請求項６】
前記関数は、１つの基準曲面定義と、少なくとも１つの他の曲面定義と、前記基準曲面定義の前記定義域内に含まれる値域を有する少なくとも１つのｐ曲線の基準組と、前記他の曲面定義の前記定義域内にある値域を有し、前記基準組のそれぞれのものに対応する少なくとも１つのｐ曲線の別の組とを用いて、互いのコピーである面分を定義し、前記置き換えるステップ（Ｓ５０）は、前記他の曲面定義および前記別の組を、前記基準曲面定義を指すポインタと、前記別の組の各々のものについて、前記基準組の対応するものを指すポインタと、前記基準曲面定義に対応する曲面を前記他の曲面定義に対応する曲面に変換する剛体運動と、前記他の曲面定義の前記定義域と前記基準曲面定義の前記定義域との間の２Ｄ局所写像と、前記別の組の各々のものの前記定義域と前記基準組の対応するものの前記定義域との間の１Ｄ局所写像とを記述するデータによって置き換えるステップを含むことを特徴とする請求項５に記載の方法。
【請求項７】
請求項１乃至６のいずれかに記載の方法によって獲得可能なことを特徴とする３次元モデル化オブジェクト。
【請求項８】
請求項７に記載の３次元モデル化オブジェクトを記憶することを特徴とするデータファイル。
【請求項９】
請求項７に記載の３次元モデル化オブジェクトを展開するためのコンピュータ実施方法であって、
前記基準関数を指す前記ポインタを用いて前記基準関数を識別するステップと、
前記別の関数の前記定義域から前記基準関数の前記定義域への前記写像を前記基準関数と合成し、次いで前記基準関数の前記値域から前記別の関数の前記値域への前記写像と合成するステップと
を含むことを特徴とするコンピュータ実施方法。
【請求項１０】
請求項１乃至６および９のいずれかに記載の方法を実行するための命令を含むことを特徴とするコンピュータプログラム。
【請求項１１】
請求項１０に記載のコンピュータプログラムを記録していることを特徴とするデータ記憶媒体。
【請求項１２】
メモリに結合されたプロセッサと、グラフィカルユーザインタフェースとを備え、前記メモリは、請求項１０に記載のコンピュータプログラムを記録していることを特徴とするＣＡＤシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータプログラムおよびシステムの分野に関し、より詳細には、３次元（３Ｄ）モデル化オブジェクトを圧縮および／または展開するための方法、システム、ならびにプログラムと、圧縮方法によって獲得可能な３Ｄモデル化オブジェクト、３Ｄモデル化オブジェクトを記述するデータ構造と、データ構造を記憶するデータファイルとに関する。
【背景技術】
【０００２】
オブジェクトの設計、エンジニアリング、および製造のための数々のシステムおよびプログラムが、市場で提供されている。ＣＡＤは、コンピュータ支援設計（Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｄｅｓｉｇｎ）の頭字語であり、例えば、オブジェクトを設計するためのソフトウェアソリューションに関する。ＣＡＥは、コンピュータ支援エンジニアリング（Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｅｎｇｉｎｅｅｒｉｎｇ）の頭字語であり、例えば、将来の製品の物理的挙動をシミュレートするためのソフトウェアソリューションに関する。ＣＡＭは、コンピュータ支援製造（Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｍａｎｕｆａｃｔｕｒｉｎｇ）の頭字語であり、例えば、製造プロセスおよび操作を定義するためのソフトウェアソリューションに関する。そのようなシステムでは、技法の効率性に関して、グラフィカルユーザインタフェース（ＧＵＩ）が重要な役割を演じる。これらの技法は、製品ライフサイクル管理（ＰＬＭ：Ｐｒｏｄｕｃｔ  Ｌｉｆｅｃｙｃｌｅ  Ｍａｎａｇｅｍｅｎｔ）システム内に組み込むことができる。ＰＬＭとは、製品の開発のために、構想から耐用期限が尽きるまで、拡大された事業という考え方の全般にわたって、製品データを共有し、共通プロセスを適用し、企業知識を活用する際に企業の助けとなるビジネス戦略のことである。
【０００３】
（ＣＡＴＩＡ、ＥＮＯＶＩＡ、およびＤＥＬＭＩＡという商標の下で）ダッソー・システムズによって提供されるＰＬＭソリューションは、製品エンジニアリング知識を組織するエンジニアリングハブ（Ｅｎｇｉｎｅｅｒｉｎｇ  Ｈｕｂ）、製造エンジニアリング知識を管理するマニュファクチャリングハブ（Ｍａｎｕｆａｃｔｕｒｉｎｇ  Ｈｕｂ）、ならびに事業統合およびエンジニアリングハブおよびマニュファクチャリングハブ両方との接続を可能にするエンタープライズハブ（Ｅｎｔｅｒｐｒｉｓｅ  Ｈｕｂ）を提供する。すべてが一緒になって、システムは、最適化された製品定義、製造準備、生産、およびサービスを推進する、動的な知識ベースの製品創造および決定支援を可能にするための、製品、プロセス、リソースを結び付けるオープンオブジェクトモデルを提供する。
【０００４】
現在、多くのＣＡＤシステムは、ユーザが、３Ｄモデル化オブジェクトを、ユーザに提供されるモデル化オブジェクトの境界表現（ｂｏｕｎｄａｒｙ  ｒｅｐｒｅｓｅｎｔａｔｉｏｎ）（Ｂ−Ｒｅｐ）に基づいて設計することを可能にする。Ｂ−Ｒｅｐは、各々がそれぞれのサポート曲面（ｓｕｐｐｏｒｔｉｎｇ  ｓｕｒｆａｃｅ）の有界な部分として定義される１組の面分を含む、データ形式である。ユーザは、既存の面分を変更すること、新しい面分を生成すること、いくつかの面分を削除すること、ならびに／または面分に対する制約および／もしくは面分の間の制約を定義すること、あるいは使用するＣＡＤシステムによって提供される任意のアクションなどによって、１組の面分に働きかけることができる。
【０００５】
Ｂ−Ｒｅｐは、大量のデータを含意することができる。特に、Ｂ−Ｒｅｐは、現在の設計では、ますます多くの要素を含むことができ、Ｂ−Ｒｅｐによってモデル化される３Ｄモデル化オブジェクトを記述するデータ構造のサイズ増加をもたらす。大きなサイズのＢ−Ｒｅｐは、多くのメモリ空間を必要とし、送信が困難である。これは、特に、共同設計の場面で問題になる。したがって、Ｂ−Ｒｅｐのサイズを減少させるための圧縮方法が開発されてきた。
【０００６】
Ｂ−Ｒｅｐモデルの既存のデータ圧縮方法は、いくつかのカテゴリに分類され得る。第１のものは、主に三角形の、多角形メッシュを扱う。多くの研究論文および特許文献が、この技術に関係している。特許文献１が、典型的な一例である。三角形の論理配置ばかりでなく、点座標、法線ベクトル、テクスチャコード、および他の属性などの数値データも圧縮される。第２のカテゴリは、近似データではなく、正確なデータを扱う。正確なデータの圧縮は、Ｂ−Ｒｅｐモデルの基本構成要素として、ナーブス曲線および曲面を扱う。ナーブス曲面の制御多角形（ｃｏｎｔｒｏｌ  ｐｏｌｙｇｏｎ）は、点座標の増分定義（ｉｎｃｒｅｍｅｎｔａｌ  ｄｅｆｉｎｉｔｉｏｎ）により圧縮される。産業用途に関わるナーブス曲面の滑らかさのため、付近の制御点の座標の変化は、「小さく」、より少ない数字を用いて符号化され得る。典型的な一例は、特許文献２である。他の解決策は、既存の圧縮技法をより効率的にするために、データ構造の前処理を含む。特許文献３が、一例である。
【０００７】
しかし、これらの既存のデータ圧縮方法の少なくともいくつかは、場合によっては、正常に機能しないことがある。いずれの場合でも、既存の技法とは異なる動作を行う新しい圧縮技法によって、圧縮比が増加され得る。
【０００８】
したがって、本発明は、３Ｄモデル化オブジェクトの圧縮を改善することを目的とする。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】欧州特許出願公開第０９６４３６４号明細書
【特許文献２】欧州特許出願公開第２３８７００４号明細書
【特許文献３】国際公開第２０１１／１０３０３１Ａ１号パンフレット
【特許文献４】欧州特許出願公開第１２３０６７２０．９号明細書
【特許文献５】欧州特許出願公開第１２３０６７２１．７号明細書
【発明の概要】
【００１０】
一態様によれば、したがって、３次元モデル化オブジェクトを圧縮するためのコンピュータ実施方法が提供される。方法は、モデル化オブジェクトの境界表現を提供するステップを含む。境界表現は、幾何学データを含む。幾何学データは、各々がそれぞれの幾何学的実体に対応する関数を含む。各関数は、定義域および値域を有する。方法は、基準関数の値域から別の関数の値域への写像を記述する第１のデータと、基準関数および基準関数の値域から別の関数の値域への写像が合成された場合、別の関数を適用したのと同じ結果をもたらす、別の関数の定義域から基準関数の定義域への写像を記述する第２のデータとを決定するステップも含む。方法は、幾何学データにおいて、別の関数を、第１のデータ、第２のデータ、および基準関数を指すポインタによって置き換えるステップも含む。
【００１１】
方法は、以下のうちの１または複数を含むことができ、すなわち、
−  方法は、互いのコピーである幾何学的実体に対応する関数の組を決定するステップと、各組内で組の基準関数を決定するステップと、各組および組の基準関数以外の組の各関数について、第１のデータおよび第２のデータを決定するステップならびに置き換えるステップを繰り返すステップであって、第１のデータおよび第２のデータを決定するステップの基準関数は、各回とも組の基準関数である、ステップとを含み、
−  関数は、パラメトリック関数を含み、基準関数の値域から別の関数の値域への写像、および別の関数の定義域から基準関数の定義域への写像は、アフィン写像であり、
−  関数は、曲面定義を含み、基準関数の値域から別の関数の値域への写像は、基準関数に対応する曲面を別の関数に対応する曲面に変換する剛体運動であり、別の関数の定義域から基準関数の定義域への写像は、２Ｄ局所写像であり、
−  関数は、それぞれの曲面定義の定義域内に含まれる値域を有するｐ曲線をさらに含み、基準関数の値域から別の関数の値域への写像は、別の関数の値域から基準関数の値域への２Ｄ局所写像の逆写像であり、別の関数の定義域から基準関数の定義域への写像は、１Ｄ局所写像であり、ならびに／または
−  関数は、１つの基準曲面定義と、少なくとも１つの他の曲面定義と、基準曲面定義の定義域内に含まれる値域を有する少なくとも１つのｐ曲線の基準組と、他の曲面定義の定義域内にある値域を有し、基準組のそれぞれのものに対応する少なくとも１つのｐ曲線の別の組とを用いて、互いのコピーである面分を定義し、置き換えるステップは、他の曲面定義および別の組を、基準曲面定義を指すポインタと、別の組の各々のものについて、基準組の対応するものを指すポインタと、基準曲面定義に対応する曲面を他の曲面定義に対応する曲面に変換する剛体運動と、他の曲面定義の定義域と基準曲面定義の定義域との間の２Ｄ局所写像と、別の組の各々のものの定義域と基準組の対応するものの定義域との間の１Ｄ局所写像とを記述するデータによって置き換えるステップを含む。
【００１２】
圧縮を行うための上述の方法によって獲得可能な３次元モデル化オブジェクトがさらに提案される。
【００１３】
上述の３次元モデル化オブジェクトを記憶するデータファイルがさらに提案される。
【００１４】
前記３次元モデル化オブジェクトを展開するためのコンピュータ実施方法がさらに提案される。展開方法は、基準関数を指すポインタを用いて基準関数を識別するステップと、別の関数の定義域から基準関数の定義域への写像を基準関数と合成し、次いで基準関数の値域から別の関数の値域への写像と合成するステップとを含む。
【００１５】
圧縮を行うための上述の方法および／または展開を行うための上述の方法を実行するための命令を含むコンピュータプログラムがさらに提案される。コンピュータプログラムは、コンピュータ可読記憶媒体に記録されるように適合される。
【００１６】
上述のコンピュータプログラムを記録しているコンピュータ可読記憶媒体がさらに提案される。
【００１７】
メモリに結合されたプロセッサと、グラフィカルユーザインタフェースとを備えるＣＡＤシステムがさらに提案され、メモリは、上述のコンピュータプログラムを記録している。
【図面の簡単な説明】
【００１８】
次に、本発明の実施形態が、非限定的な例によって、添付の図面を参照しながら説明される。
【図１】方法の一例のフローチャートである。
【図２】グラフィカルユーザインタフェースの一例を示す図である。
【図３】クライアントコンピュータシステムの一例を示す図である。
【図４】方法の例を示す図である。
【図５】方法の例を示す図である。
【図６】方法の例を示す図である。
【図７】方法の例を示す図である。
【図８】方法の例を示す図である。
【図９】方法の例を示す図である。
【図１０】方法の例を示す図である。
【図１１】方法の例を示す図である。
【図１２】方法の例を示す図である。
【図１３】方法の例を示す図である。
【図１４】方法の例を示す図である。
【図１５】方法の例を示す図である。
【図１６】方法の例を示す図である。
【図１７】方法の例を示す図である。
【図１８】方法の例を示す図である。
【図１９】方法の例を示す図である。
【図２０】方法の例を示す図である。
【図２１】方法の例を示す図である。
【図２２】方法の例を示す図である。
【図２３】方法の例を示す図である。
【図２４】方法の例を示す図である。
【図２５】方法の例を示す図である。
【図２６】方法の例を示す図である。
【図２７】方法の例を示す図である。
【発明を実施するための形態】
【００１９】
図１は、３Ｄモデル化オブジェクトを圧縮するためのコンピュータ実施方法の例をフローチャートで示している。方法は、モデル化オブジェクトのＢ−Ｒｅｐを提供するステップＳ１０を含む。Ｂ−Ｒｅｐは、幾何学データを含む。幾何学データは、関数を含む。各関数は、それぞれの幾何学的実体に対応する。各関数は、定義域および値域を有する。方法は、第１のデータおよび第２のデータを決定するステップＳ４０をさらに含む。第１のデータは、基準関数の値域から別の関数の値域への写像を記述する。第２のデータは、別の関数の定義域から基準関数の定義域への写像を記述する。第２のデータは、第２のデータによって記述される別の関数の定義域から基準関数の定義域への写像を基準関数と合成し、次いで第１のデータによって記述される基準関数の値域から別の関数の値域への写像と合成することが、別の関数を適用するのと同じ結果をもたらすようなものである。方法は、幾何学データにおいて、別の関数を、第１のデータ、第２のデータ、および基準関数を指すポインタによって置き換えるステップＳ５０をさらに含む。
【００２０】
そのような方法は、３Ｄモデル化オブジェクトを圧縮するための改善された解決策を構成する。実際に、おそらくは複雑で、したがって、相対的に大きなデータによって形成され得る関数を、単純で、したがって、相対的に小さいデータである、第１の関数の値域から第２の関数の値域（または第２の関数の定義域から第１の関数の定義域）への写像と、ポインタ（例えば、コンピュータサイエンスの分野で知られている、データの一部を指す任意の種類のポインタ）とを記述するデータによって置き換えることによって、方法は、幾何学データの圧縮を達成する。さらに、この圧縮は、決定Ｓ４０および後続の置き換えＳ５０を可能にする、基準関数と別の関数との間の幾何学的結び付きのＳ４０における認識に基づいている。実際に、基準関数と別の関数は、それらがコピーされた幾何学的実体に対応するという事実によって結び付けられる。方法は、この幾何学的結び付きを利用して、幾何学データにおいて、したがって別の関数を（すなわち、残りの関数とは独立に）形成するデータを、基準関数および基準関数を指すポインタを形成するデータに基づいて別の関数の計算を可能にする、より小さいデータによって置き換える。したがって、方法は、いかなる干渉も受けずに、従来技術において知られている他の圧縮技法と組み合わせることができ、方法は、幾何学的結び付きが存在する限り、圧縮を達成する。これはすべて、以下の説明において詳述される。
【００２１】
さらに、そのように圧縮された３Ｄモデル化オブジェクトは、基準関数を指すポインタを用いて基準関数を識別するステップを含む展開を行うための方法によって、容易に展開され得る。言い換えると、圧縮されたデータにおいて、方法は、ポインタのおかげで、基準関数を取り出す。次に、展開を行うための方法は、（それを記述する第２のデータのおかげで）別の関数の定義域から基準関数の定義域への写像を基準関数と合成し、次いで（それを記述する第１のデータのおかげで）基準関数の値域から別の関数の値域への写像と合成するステップを含む。言い換えると、展開を行うための方法は、別の関数の定義域から基準関数の定義域への写像と基準関数との、次いで基準関数の値域から別の関数の値域への写像との連続的合成（これら３つの関数は前述の連続的順序で適用される）から成る関数を決定／計算する。この合成関数は、圧縮を行うための方法によって圧縮された別の関数と同じ幾何学的結果を提供し、したがって、前述の別の関数と幾何学的に同一である。
【００２２】
モデル化オブジェクトは、データファイル（すなわち、特定のフォーマットを有するコンピュータデータの一部）内および／またはコンピュータシステムのメモリ上に記憶され得る構造化データによって定義／記述される任意のオブジェクトである。拡大解釈すれば、「モデル化オブジェクト」という表現は、データ構造自体を指すことができる。方法は、３Ｄモデル化オブジェクトを、それを記述するデータ構造を圧縮することによって、３Ｄモデル化オブジェクトの初期状態から３Ｄモデル化オブジェクトの圧縮状態に処理する。したがって、方法は、置き換えるステップＳ５０によって、特定の構造を有する圧縮された３Ｄモデル化オブジェクトを「生成」または出力する。特に、方法によって獲得される３Ｄモデル化オブジェクトは、圧縮された幾何学データを含むＢ−Ｒｅｐを含む。圧縮された幾何学データは、各々がそれぞれの幾何学的実体に対応する関数を含み、各関数は、定義域および値域を有する。関数は、「基準」関数と呼ばれる、したがって（すなわち、別の関数とは独立に）記憶された少なくとも１つの関数を含む（すなわち、基準関数は、他のデータを参照することなく、それを定義するデータによって、その定義域上で適用可能である）。圧縮されたデータは、基準関数の値域から別の関数の値域への写像を記述するいくつかのデータ（すなわち、第１のデータ）、別の関数の定義域から先に述べた基準関数の定義域への写像を記述するいくつかのデータ（すなわち、第２のデータ）、および基準関数を指すポインタも含む。したがって、別の関数は、基準関数を定義するデータを参照することによって適用され得る。そのような圧縮された３Ｄモデル化オブジェクト、またはそのような３Ｄモデル化オブジェクトを記述するデータ構造、またはそのようなデータ構造を記憶するデータファイルは、最初の３Ｄモデル化オブジェクトと同じ幾何学的情報を、より僅かなメモリ空間を用いて保持する。
【００２３】
方法は、３Ｄモデル化オブジェクトを定義するための方法の一部とすることができ、例えば、方法は、そのような設計方法の最終ステップを構成する。「３Ｄモデル化オブジェクトを設計する」とは、３Ｄモデル化オブジェクトを精巧に作り上げるプロセスの少なくとも一部である、任意のアクションまたは一連のアクションのことを指す。したがって、方法は、３Ｄモデル化オブジェクトをゼロから作成するステップを含むことができる。あるいは、方法は、先に生成された３Ｄモデル化オブジェクトを提供するステップと、その後、その３Ｄモデル化オブジェクトを変更するステップとを含むことができる。
【００２４】
３Ｄモデル化オブジェクトは、ＣＡＤモデル化オブジェクト、またはＣＡＤモデル化オブジェクトの一部とすることができる。いずれの場合も、方法によって設計される３Ｄモデル化オブジェクトは、例えば、ＣＡＤモデル化オブジェクトによって占有される３Ｄ空間など、ＣＡＤモデル化オブジェクトまたは少なくともそれの一部を表すことができる。ＣＡＤモデル化オブジェクトは、ＣＡＤシステムのメモリ内に記憶されたデータによって定義される、任意のオブジェクトである。システムのタイプによって、モデル化オブジェクトは、異なる種類のデータによって定義することができる。ＣＡＤシステムは、ＣＡＴＩＡなど、モデル化オブジェクトのグラフィカル表現に基づいて少なくともモデル化オブジェクトを設計するのに適した任意のシステムである。したがって、ＣＡＤモデル化オブジェクトを定義するデータは、モデル化オブジェクトの表現を可能にするデータ（例えば、空間内の相対位置を含む幾何学データ）を含む。
【００２５】
方法は、製造プロセスに含めることができ、製造プロセスは、方法を実行した後、モデル化オブジェクトに対応する物理的製品を生産することを含むことができる。いずれの場合も、方法によって設計されたモデル化オブジェクトは、製造オブジェクトを表すことができる。したがって、モデル化オブジェクトは、モデル化立体（すなわち、立体を表すモデル化オブジェクト）とすることができる。製造オブジェクトは、部品または部品の組立品などの、製品とすることができる。方法は、より良い圧縮を可能にすることでモデル化オブジェクトの設計を改善するので、製品の製造も改善し、したがって、製造プロセスの生産性を向上させる。方法は、ＤＥＬＭＩＡなどの、ＣＡＭシステムを使用して実施することができる。ＣＡＭシステムは、少なくとも製造プロセスおよび操作の定義、シミュレーション、および制御を行うのに適した、任意のシステムである。
【００２６】
方法は、コンピュータで実施される。これは、方法が、少なくとも１つのコンピュータ、または任意の同様のシステム上で実行されることを意味する。例えば、方法は、ＣＡＤシステム上で実施することができる。したがって、方法のステップ（例えば、ユーザによってトリガされるステップ、および／もしくはユーザ対話を伴うステップ）は、おそらくは完全に自動的に、または半自動的にコンピュータによって実行される。特に、提供ステップＳ１０および／または決定ステップＳ２０（後で説明）は、ユーザがトリガすることができる。方法の他のステップは、自動的に（すなわち、いかなるユーザ介入もなしに）、または半自動的に（すなわち、例えば、結果を確認するための、僅かなユーザ介入などを伴って）、実行することができる。
【００２７】
方法のコンピュータ実施の典型的な例は、この目的に適したシステムを用いて方法を実行することである。システムは、方法を実行するための命令を記録したメモリを備えることができる。言い換えると、ソフトウェアは、直ちに使用できるように、メモリ上にすでに準備されている。したがって、システムは、他のいかなるソフトウェアもインストールすることなしに、方法を実行するのに適している。そのようなシステムは、メモリに結合された、命令を実行するための少なくとも１つのプロセッサも備えることができる。言い換えると、システムは、プロセッサに結合されたメモリ上に符号化された命令であって、方法を実行するための手段を提供する命令を含む。そのようなシステムは、３Ｄモデル化オブジェクトを設計するための効率的なツールである。
【００２８】
そのようなシステムは、ＣＡＤシステムとすることができる。システムは、ＣＡＥおよび／またはＣＡＭシステムとすることもでき、ＣＡＤモデル化オブジェクトは、ＣＡＥモデル化オブジェクトおよび／またはＣＡＭモデル化オブジェクトとすることもできる。実際、モデル化オブジェクトは、これらのシステムの任意の組合せに対応するデータによって定義できるので、ＣＡＤ、ＣＡＥ、およびＣＡＭシステムは、一方が他方にとって排他的とはならない。
【００２９】
システムは、例えば、ユーザによって、命令の実行を開始するための少なくとも１つのＧＵＩを備えることができる。特に、ＧＵＩは、後で提供される一例では、提供するステップＳ１０をユーザがトリガし、その後、例えば、（例えば、「圧縮」と呼ばれる）特定の機能を開始することによって、ユーザがそうすることを決定した場合、例えば、決定するステップＳ２０を含む、方法の残りをトリガすることを可能にすることができる。
【００３０】
３Ｄモデル化オブジェクトは、３Ｄ（すなわち３次元）である。これは、モデル化オブジェクトが３Ｄ表現を可能にするデータによって定義されることを意味する。特に、Ｂ−Ｒｅｐの関数が対応する幾何学的実体は、３Ｄである（すなわち、それらは、すべての幾何学的実体の合併が非平面的になり得るように、３Ｄで定義される）。３Ｄ表現は、すべての角度から表現物を見ることを可能にする。例えば、モデル化オブジェクトは、３Ｄ表現された場合、その軸のいずれかの周りで、または表現が表示された画面内の任意の軸の周りで処理し、回転させることができる。これは、特に、３Ｄモデル化されていない２Ｄアイコンを、それらが２Ｄパースペクティブにおいて何かを表現する場合であっても、除外する。３Ｄ表現の表示は、設計を容易にする（すなわち、設計者が統計的に仕事を成し遂げるスピードを速める）。製品の設計は製造プロセスの一部であるので、これは、製造業における製造プロセスをスピードアップする。
【００３１】
図２は、典型的なＣＡＤシステムのＧＵＩの一例を示している。
【００３２】
ＧＵＩ２１００は、標準的なメニューバー２１１０、２１２０、ならびに下部および側部ツールバー２１４０、２１５０を有する、典型的なＣＡＤタイプのインタフェースとすることができる。そのようなメニューおよびツールバーは、１組のユーザ選択可能なアイコンを含み、各アイコンは、当技術分野で知られるように、１または複数の操作または機能に関連付けられる。これらのアイコンのいくつかは、ＧＵＩ２１００内に表示された３Ｄモデル化オブジェクト２０００に対して編集および／または作業を行うように適合された、ソフトウェアツールに関連付けられる。ソフトウェアツールは、ワークベンチにグループ化することができる。各ワークベンチは、ソフトウェアツールのサブセットを含む。特に、ワークベンチの１つは、モデル化製品２０００の幾何学的特徴を編集するのに適した、編集ワークベンチである。操作中、設計者は、例えば、オブジェクト２０００の一部を事前選択し、その後、適切なアイコンを選択することによって、操作（例えば、造形操作、もしくは寸法、色などの変更などの他の任意の操作）を開始すること、または幾何学的制約を編集することができる。例えば、典型的なＣＡＤ操作は、画面上に表示された３Ｄモデル化オブジェクトの穴開けまたは折り曲げのモデル化である。
【００３３】
ＧＵＩは、例えば、表示された製品２０００に関連するデータ２５００を表示することができる。図２の例では、「特徴ツリー」として表示されたデータ２５００と、それらの３Ｄ表現２０００は、ブレーキキャリパ（ｂｒａｋｅ  ｃａｌｉｐｅｒ）およびディスクを含むブレーキ組立体に関する。ＧＵＩは、例えば、オブジェクトの３Ｄ方向付けを容易にするための、編集された製品の動作のシミュレーションをトリガするための、または表示された製品２０００の様々な属性を表すための、様々なタイプのグラフィックツール２１３０、２０７０、２０８０をさらに示すことができる。カーソル２０６０は、触覚デバイスによってコントロールすることができ、ユーザがグラフィックツールと対話することを可能にする。
【００３４】
図３は、例えば、ユーザのワークステーションなど、クライアントコンピュータシステムとしてのシステムのアーキテクチャの一例を示している。
【００３５】
クライアントコンピュータは、内部通信バス１０００に接続された中央処理装置（ＣＰＵ）１０１０と、やはりバスに接続されたランダムアクセスメモリ（ＲＡＭ）１０７０とを備える。クライアントコンピュータには、バスに接続されたビデオランダムアクセスメモリ１１００に関連付けられた、グラフィックス処理ユニット（ＧＰＵ）１１１０がさらに設けられる。ビデオＲＡＭ１１００は、当技術分野において、フレームバッファとしても知られている。大容量記憶デバイスコントローラ１０２０は、ハードドライブ１０３０などの大容量メモリデバイスへのアクセスを管理する。コンピュータプログラム命令およびデータを有形に具体化するのに適した大容量メモリデバイスは、例を挙げると、ＥＰＲＯＭ、ＥＥＰＲＯＭ、およびフラッシュメモリデバイスなどの半導体メモリデバイス、内蔵ハードディスクおよび着脱可能ディスクなどの磁気ディスク、光磁気ディスク、ならびにＣＤ−ＲＯＭディスク１０４０を始めとする、すべての形態の不揮発性メモリを含む。上記のいずれも、特別に設計されたＡＳＩＣ（特定用途向け集積回路）によって補うこと、またはその中に組み込むことができる。ネットワークアダプタ１０５０は、ネットワーク１０６０へのアクセスを管理する。クライアントコンピュータは、カーソル制御デバイスまたはキーボードなどの、触覚デバイス１０９０も含むことができる。カーソル制御デバイスは、図２を参照して言及されたように、画面１０８０上の任意の所望の位置にユーザがカーソルを選択的に配置することを可能にするために、クライアントコンピュータにおいて使用される。画面によって、コンピュータモニタなど、その上で表示が実行され得る任意のサポートが意味される。加えて、カーソル制御デバイスは、ユーザが、様々なコマンドを選択し、制御信号を入力することを可能にする。カーソル制御デバイスは、制御信号をシステムに入力するための、数々の信号発生デバイスを含む。典型的には、カーソル制御デバイスは、マウスとすることができ、信号を発生させるために、マウスのボタンが使用される。
【００３６】
システムに方法を実行させるため、コンピュータによって実行するための命令を含むコンピュータプログラムが提供され、命令は、この目的のための手段を含む。プログラムは、例えば、デジタル電子回路で、もしくはコンピュータハードウェア、ファームウェア、ソフトウェアで、またはそれらの組合せで実施することができる。本発明の装置は、プログラム可能プロセッサによって実行するための、機械可読記憶デバイスに有形に具体化されるコンピュータプログラム製品で実施することができ、本発明の方法ステップは、入力データの操作および出力の生成によって本発明の機能を実行するために、命令からなるプログラムを実行するプログラム可能プロセッサによって実行することができる。命令は、データ記憶システムからデータおよび命令を受け取り、データ記憶システムにデータおよび命令を送るように結合された、少なくとも１つのプログラム可能プロセッサと、少なくとも１つの入力デバイスと、少なくとも１つの出力デバイスとを含む、プログラム可能システムにおいて実行可能な、１または複数のコンピュータプログラムで有利に実施することができる。アプリケーションプログラムは、高水準手続き型もしくはオブジェクト指向プログラミング言語で、または望ましければアセンブリ言語もしくは機械語で実施することができ、いずれの場合も、言語は、コンパイル言語またはインタプリタ言語とすることができる。プログラムは、完全インストールプログラムまたは更新プログラムとすることができる。後者の場合、プログラムは、方法を実行するのに適したシステムになった状態に、既存のＣＡＤシステムを更新する。
【００３７】
提供ステップＳ１０が、次に説明される。
【００３８】
方法は、モデル化オブジェクトのＢ−Ｒｅｐを提供するステップＳ１０を含む。提供ステップＳ１０は、モデル化オブジェクト（この場合、その境界表現）上で作業する設計者に起因し、または例えば既存のライブラリ内で検索された、すでに存在するＢ−Ｒｅｐに方法を適用できるということに起因することができる。いずれの場合も、モデル化オブジェクトは、Ｓ１０においてＢ−Ｒｅｐとして提供される。境界表現は、３Ｄオブジェクトをそのエンベロープ（すなわち、その外表面）の観点からモデル化するための、広く知られた形式である。したがって、Ｂ−Ｒｅｐは、幾何学データおよび位相データを含むことができる、特定の形式のデータを指す。幾何学データは、３Ｄ位置の観点から記述される実体である、幾何学的実体を提供するデータである。位相データは、幾何学的実体との関連性、および／または例えば相対的な位置決めなど、他の位相的実体との関係の観点から記述される実体である、位相的実体を提供するデータである。典型的には、関係は、位相的実体を他の位相的実体に関連付ける、「によって境界付けされる（ｉｓ  ｂｏｕｎｄｅｄ  ｂｙ）」関係を含むことができ、それによって、それは、位相的に境界付けされる。
【００３９】
位相データは、面分、稜線、および／または頂点を含むことができる。幾何学データは、曲面定義、ｐ曲線、および／またはｐ頂点などの関数を含むことができる。幾何学データは、曲線、および／または頂点も含むことができる。（簡潔に、その像によって、「曲面」とも呼ばれる）曲面定義は、２Ｄ定義域から３Ｄ空間への関数である。曲線は、１Ｄ定義域から３Ｄ空間への関数である。頂点は、３Ｄ空間の特定の１組の座標である。数学的な観点からは、ｐ曲線は、曲面上に存在する曲線である。したがって、ｐ曲線は、１Ｄ定義域から曲面定義の２Ｄ定義域への関数である。Ｂ−Ｒｅｐモデルの観点からは、ｐ曲線は、面分の境界を実現するために使用される。数学的な観点からは、ｐ頂点は、ｐ曲線または曲面上に存在する点である。したがって、ｐ頂点は、ｐ曲線の１Ｄ定義域の特定のパラメータ、または曲面の２Ｄ定義域の特定の１組のパラメータである。Ｂ−Ｒｅｐモデルの観点からは、ｐ頂点は、稜線の境界を実現するために使用される。以下では、「曲面」という語は、平面ばかりでなく、非平面的な曲面に対しても使用され得る。同様に、「ｐ曲線」という語は、直線ばかりでなく、非直線的なｐ曲線に対しても使用され得る。
【００４０】
定義によって、面分は、サポート曲面と呼ばれる曲面の有界な部分である。したがって、面分は、面分の記述に参加するすべての幾何学的実体を含む幾何学要素（すなわち、１組の少なくとも１つの幾何学的実体）に対応する。そのような幾何学要素は、簡潔に、「面分」とも呼ばれ得る。面分の境界は、稜線を含む。そのような各稜線は、サポートｐ曲線と呼ばれるｐ曲線の有界な部分であり、面分のサポート曲面上に存在する。稜線の境界は、２つの頂点を含む。各頂点は、稜線上に存在する点である。定義によって、２つの面分は、それらが少なくとも１つの稜線を共有する場合、隣接する。同様に、２つの稜線は、それらが少なくとも１つの頂点を共有する場合、隣接する。機械部品のＢ−Ｒｅｐソリッドモデルでは、すべての稜線は、正確に２つの面分によって共有される。反対に、スキン（ｓｋｉｎ）のＢ−Ｒｅｐモデルでは、いくつかの稜線は、２つの面分によって共有されるが、他のいくつかは、境界稜線であり、正確に１つの面分に属する。
【００４１】
位相的観点からは、２つの面分Ｆ１およびＦ２によって共有される稜線ｅは、単一のオブジェクトであることが理解されなければならない。反対に、幾何学的観点からは、そのような稜線は、以下の実体、すなわち、面分Ｆ１のサポート曲面Ｓ１上で定義されたｐ曲線と、面分Ｆ２のサポート曲面Ｓ２上で定義された別のｐ曲線とを集めた合成オブジェクトである。同様に、位相的観点からは、稜線ｅ１、ｅ２、…、ｅｎによって共有される頂点ｖは、単一のオブジェクトである。反対に、幾何学的観点からは、そのような頂点は、各稜線ｅｉのすべてのｐ曲線上で定義されたｐ頂点を集めた合成オブジェクトである。
【００４２】
したがって、幾何学データは、各々がそれぞれの幾何学的実体に対応する関数（例えば、上で説明された定義域および値域を有する、曲面もしくは「曲面定義」、ｐ曲線、および／または曲線）を含む。実際に、曲面定義は、曲面関数の像から成る幾何学的曲面に対応する。同様に、曲線は、曲線関数の像から成る幾何学的曲線に対応する。ｐ曲線は、ｐ曲線関数と、曲線がその上に存在する曲面関数とを、この順序で合成した関数の像から成る曲線に対応する。これは、例を用いて後で説明される。
【００４３】
これらの関数は、典型的には、ナーブスなどの、パラメトリック関数とすることができる。例えばサポート曲面は、典型的には、ＮＵＲＢＳ曲面（ＮＵＲＢＳ  ｓｕｒｆａｃｅ）とすることができるが、平面、標準曲面（ｃａｎｏｎｉｃａｌ  ｓｕｒｆａｃｅ）、または手続き型曲面（ｐｒｏｃｅｄｕｒａｌ  ｓｕｒｆａｃｅ）とすることもできる。（例えば位相）データは、少なくとも１組の面分を含むことができ、各面分は、（幾何学データで提供される）それぞれのサポート曲面の有界な部分として定義される。したがって、面分は、切り取られた曲面に対応する。したがって、サポート曲面は、何らかの切り取り操作によって面分がその上に定められる（それによって面分を「サポート」する）曲面である。
【００４４】
Ｂ−Ｒｅｐの概念は、広く知られているが、Ｓ１０において提供され得るモデル化オブジェクトの一例を通して、次にさらに説明される。しかし、例えば、少なくともいくつかの位相的実体に対して、「によって境界付けされる」関係とは異なる関係を用いる、Ｂ−Ｒｅｐの他の例も、方法によって企図され得る。
【００４５】
すでに言及したように、モデル化オブジェクトのＢ−Ｒｅｐは、位相的実体および幾何学的実体を含むことができる。幾何学的実体は、曲面（例えば平面）、曲線（例えば直線）、および／または点である、３Ｄオブジェクトを含むことができる。曲面は、２つのパラメータの関数として提供することができる。曲線は、単純に１つのパラメータの関数として提供することができる。点は、３Ｄ位置として提供することができる。位相的実体は、面分、稜線、および／または頂点を含むことができる。その定義によって、面分は、サポート曲面と呼ばれる、それぞれの曲面の有界な部分に対応する。したがって、「面分」という用語は、曲面のそのような有界な部分、または２Ｄ領域の対応する有界な部分を区別せずに指すことができる。同様に、稜線は、例えばサポート曲線（ｓｕｐｐｏｒｔｉｎｇ  ｃｕｒｖｅ）と呼ばれる、曲線の有界な部分に対応する。したがって、「稜線」という用語は、曲線またはその領域のそのような有界な部分を指すことができる。頂点は、３Ｄ空間内の点との結び付きとして定義することができる。これらの実体は、以下のように互いに関連する。曲線の有界な部分は、曲線上にある２つの点（頂点）によって定義される。曲面の有界な部分は、その境界によって定義され、この境界は、曲面上にある１組の稜線である。面分の境界の稜線は、共有する頂点によって一緒に接続される。面分は、共有する稜線によって一緒に接続される。定義によって、２つの面分は、それらが稜線を共有する場合、隣接する。同様に、２つの稜線は、それらが頂点を共有する場合、隣接する。曲面、曲線、および点は、それらのパラメータ化を介して、一緒に結び付けることができる。例えば、境界の頂点を定義するために、曲線を定義するパラメトリック関数のパラメータの値が提供され得る。同様に、境界の稜線を定義するために、曲線のパラメータを曲面の２つのパラメータに結び付ける関数が提供され得る。しかし、Ｂ−Ｒｅｐのそのような位相データの非常に詳細な構造は、本説明の範囲外にある。
【００４６】
図４および図５は、Ｓ１０において提供されるモデル化オブジェクトとすることができ、図において１、２の番号が付された２つの隣接する面分、すなわち、上部平面面分１と、側面円筒面分２とから作成される、部分的な円筒スロット８０のＢ−ｒｅｐモデルを示している。図４は、スロット８０の斜視図を示している。図５は、面分の分解図を示している。重複する番号は、共有の稜線および頂点を示している。面分１は、平面の有界な部分である。面分１の境界は、稜線３、４を含み、それらの各々は、頂点８と頂点９によって境界付けされる。面分２は、すべて無限円筒曲面上に存在する稜線３、５、６、７によって境界付けられる。面分１、２は、それらが稜線３を共有するので、隣接している。
【００４７】
図６は、スロット８０のＢ−ｒｅｐモデルの「によって境界付けされる」位相関係を示している。高位レイヤ１０１のノードは、面分であり、中位レイヤ１０３のノードは、稜線であり、低位レイヤ１０５のノードは、頂点である。図７は、位相的実体（面分１、２、稜線３、４、頂点８）と、曲面、ｐ曲線に対応する曲線、およびｐ頂点に対応する頂点である、幾何学的実体との間の関係を部分的に示している。図７において、位相的オブジェクトから幾何学的オブジェクトへの右向き矢印は、「によってサポートされる（ｉｓ  ｓｕｐｐｏｒｔｅｄ  ｂｙ）」関係を捉えている。幾何学的オブジェクトをより高い次元の幾何学的オブジェクトに結び付ける上向き矢印は、「内に埋め込まれる（ｉｓ  ｅｍｂｅｄｄｅｄ  ｉｎ）」関係を捉えている。図８に示されるようにｘｙｚ軸を設定することによって、幾何学モデルの関数（すなわち、式）は、以下の表に明示的に与えられ得る。円筒の半径は、ｒで表され、平面の高さは、ｚ０で表される。
【００４８】
【表１】
2014232534.tif 000003
【００４９】
モデルの一貫性は、以下の特性によって捉えられる。
【００５０】
【数１】
2014232534.tif 000004
【００５１】
および
【００５２】
【数２】
2014232534.tif 000005
【００５３】
によって定義される３次元曲線は、稜線３に対応する同じ幾何学的実体（半円）を表す。このようにして、稜線共有が実現される。Ｐ（ｃ１（ｖ１））、Ｐ（ｃ３（ｖ３））、Ｃ（ｃ２（ｖ２））によって定義される３次元点は、頂点８の空間位置に対応する同じ点
【００５４】
【数３】
2014232534.tif 000006
【００５５】
を表す。このようにして、頂点共有が実現される。
【００５６】
次に、図１の方法の例についての他のアクション（すなわち、ステップＳ２０〜Ｓ４０）が説明される。
【００５７】
方法は、第１のデータおよび第２のデータを決定するステップＳ４０と、圧縮を達成するために別の関数を形成するデータを置き換えるステップＳ５０とを目的とする。先に説明されたように、基準関数と別の関数は、それらが互いにコピーである幾何学的実体に対応するという事実によって幾何学的に結び付けられる。これら２つの関数は、任意の方法で決定され得る。
【００５８】
本例の場合、方法は、互いのコピーである幾何学的実体に対応する関数の組を決定する（Ｓ２０）。その後、圧縮が、組ごとに実行される。具体的には、本例の方法は、各組内の組の基準関数を決定する（Ｓ３０）。言い換えると、各組について、組の１つの関数が、任意の方法で選択され、その後、決定するステップＳ４０および置き換えるステップＳ５０のための基準として使用される関数を構成する。その後、各組について、本例の方法は、基準関数とは異なる、組の各関数に対して、決定するステップＳ４０および置き換えるステップＳ５０を繰り返す。「コピーである（ｉｓ  ａ  ｃｏｐｙ  ｏｆ）」関係は、同値関係（ｅｑｕｉｖａｌｅｎｃｅ  ｒｅｌａｔｉｏｎ）を構成する一例によって、後で説明される。したがって、Ｓ２０において決定された関数の組は、全関数の区分を構成することができる。したがって、本例の方法は、各組について、また各組内では、組に対してＳ３０において決定された基準関数とは異なる各関数について、決定するステップＳ４０および置き換えるステップＳ５０を繰り返す。したがって、本例の方法は、各組について幾何学的実体のコピーに対応する関数の各組を網羅的に圧縮することによって、Ｂ−Ｒｅｐのデータを網羅的に圧縮する。
【００５９】
次に、互いのコピーである幾何学的実体に対応する関数の組を決定するステップＳ２０の一例が説明される。
【００６０】
２つの幾何学的実体（例えば、曲面または曲線）は、それらを幾何学的重複と見なす所定の（コンピュータ化された）基準をそれらが満たす場合、互いのコピーであると言われる。幾何学的実体は、面分などの幾何学要素を形成することができる。面分が曲線によって境界付けられた曲面に対応することは上で説明された。そのおかげで、方法は、任意のパターン認識方法と、例えば、参照によって本明細書に組み込まれる、特許文献４および／または特許文献５の特許出願の方法と、有利に組み合わされ得る。実際に、これらの特許出願はともに、互いのコピーである幾何学要素（例えば、面分）の組に基づいたパターン認識方法を説明している。以下でより詳細に説明されるように、方法は、これら２つの特許出願に従った、および／またはこれら２つの特許出願の方法のいずれか、もしくは両方と組み合わされた、決定するステップＳ２０を実行することができ、決定するステップＳ２０は、効率的に一度だけ実行され、本発明の圧縮方法およびパターン認識方法の両方のために使用され、それによって、相乗効果を達成する。
【００６１】
開発下にあるそのような３Ｄ設計の側面の１つは、「パターン認識」として知られている。「パターン」という用語は、同じ幾何学的特徴の規則的なレイアウトのコピーを指している。パターンの認識は、設計中にそのようなパターンを単一の要素として処理することを可能にし、それによって、一連の設計の可能性を広げる。例えば、パターンの要素を１つずつ変更する代わりに、パターンの事前認識のおかげで、ユーザは、パターンの変更を、例えば単一のアクションで、全体的に実行することができる。パターン認識は、機械設計、消費財、建造物建築、航空宇宙、または他の領域など、ＣＡＤの様々な領域に関連する。パターン認識は、特徴認識に関連することができる。特徴認識は、所与の３Ｄオブジェクト（通常は機械部品を表す立体）における特徴的な形状を認識するのに有益である。機械設計において関心のある特徴的な形状は、例えば、ホール（ｈｏｌｅ）、押出パッド（ｅｘｔｒｕｄｅｄ  ｐａｄ）、押出ポケット（ｅｘｔｒｕｄｅｄ  ｐｏｃｋｅｔ）、フィレット（ｆｉｌｌｅｔ）もしくはラウンド（ｒｏｕｎｄ）、外旋パッド（ｒｅｖｏｌｕｔｅ  ｐａｄ）、および／または外旋ポケット（ｒｅｖｏｌｕｔｅ  ｐｏｃｋｅｔ）を含む。特徴的な形状の認識は、例えば、押出もしくは外旋形状の輪郭、外旋形状の回転軸、ラウンドおよびフィレットの半径値、押出方向、ならびに／または押出深さなど、その仕様を、より良い意味レベルで識別することに帰着する。この情報は、例えば押出の輪郭を編集することによって、形状を変更するために、または例えば機械加工プロセスなど、下流のプロセスに供給するために使用される。
【００６２】
特許文献４および／または特許文献５の特許出願はともに、互いのコピーである面分の組を決定するステップを含む、パターン認識を実行するための方法を記述する。決定するステップＳ２０は、そのような１組の面分のそのような決定、および潜在的にそのようなアクションの反復を含むことができる。その後、そのように決定された互いのコピーである面分の各組について、決定するステップＳ２０は、任意の方法で同数の組において、互いに位相的に一致する面分の幾何学的実体を収集し、それによって、互いのコピーである幾何学的実体に対応する関数の組を獲得するステップを単に含むことができる。言い換えると、後で説明されるように、剛体運動に従って、互いのコピーである面分が決定される。剛体運動は、１つの面分の実体の各々（例えば、曲面および／または境界曲線）を、他の面分の唯一の対応する実体に変換する。
【００６３】
したがって、本例の決定するステップＳ２０は、互いのコピーである、または言い換えると、互いに幾何学的に同一である、もしくは互いの幾何学的レプリカである、面分の組を決定するステップを含む。面分の組は、当業者が望む任意の実装形態に従って、Ｓ２０において決定することができる。例えば、方法は、面分のペアの間で比較を実行するステップを含むことができ、面分は、任意の順序に従ってブラウズされる。そのような比較は、任意の方法で実行することができる。例が、後で提供される。また、ＣＡＤの分野から分かるように、数値計算を伴う任意の決定は、システムによって適用される必要な数値近似の影響を受ける。本ケースでは、面分は、それらが理論的には僅かに異なるとしても、Ｓ２０において、互いのコピーであると決定されることがある。したがって、方法は、実際には、Ｓ２０において、実質的に互いのコピーである面分の組を決定することができる。しかし、近似が実施される方法は、本説明の主題ではないので、以下では、「実質的に互いのコピー」と「互いのコピー」とは区別されない。実際のところ、方法は、２つの面分が互いのコピーであるかどうかを判別するための所定の基準に従うとしか見なされない。
【００６４】
面分は、点集合と見ることができ（それによって、そのようなものとして方法によって処理することができ）、すなわち、３次元空間
【００６５】
【数４】
2014232534.tif 000007
【００６６】
の部分集合と見ることができる。剛体運動は、Ｄ（ｘ）＝Ｒｘ＋Ｔによって、２つの点集合の間で定義される写像
【００６７】
【数５】
2014232534.tif 000008
【００６８】
であり、ここで、Ｒは、回転であり、Ｔは、並進ベクトルである（ゼロの可能性あり）。ｙ＝Ｄ（ｘ）は、ｘ＝Ｄ−１（ｙ）と等価であり、ここで、Ｄ−１（ｙ）＝Ｒ−１ｙ−Ｒ−１Ｔであるので、剛体運動は、可逆的である。組の面分は、互いのコピーであるので、組の２つの面分が与えられた場合、剛体運動を適用することによって、一方を他方から導出することができる。
【００６９】
点集合Ｘを与えた場合、簡潔にはＹ＝Ｄ（Ｘ）と表記される、Ｙ＝｛Ｄ（ｘ），ｘ∈Ｘ｝であるような、剛体運動Ｄが存在する場合、点集合Ｙは、Ｘの「レプリカ」である。
【００７０】
「方向付けされた点集合（ｏｒｉｅｎｔｅｄ  ｐｏｉｎｔ−ｓｅｔ）」は、２つ組（Ｘ，ｕＸ）であり、ここで、
【００７１】
【数６】
2014232534.tif 000009
【００７２】
は、点集合であり、ｕＸは、写像ｕＸ：Ｘ→Ｓ２であり、ここで、Ｓ２は、
【００７３】
【数７】
2014232534.tif 000010
【００７４】
の１組の単位ベクトルである。言い換えると、任意の点ｘ∈Ｘにおいて、単位ベクトルｕＸ（ｘ）が定義される。
【００７５】
方向付けされた点集合（Ｙ，ｕＹ）は、Ｙが方向付けを保ったＸのレプリカである場合、方向付けされた点集合（Ｘ，ｕＸ）の「コピー」である。より正確には、すべてのｘ∈Ｘについて、レプリカ上の対応する点Ｄ（ｘ）の単位ベクトルは、点ｘにおけるＸの単位ベクトルを回転したものである。形式的に、すべてのｘ∈Ｘについて、ｕＹ（Ｄ（ｘ））＝ＲｕＸ（ｘ）であり、これは、以下のダイアグラムが可換であることを意味する。
【００７６】
【数８】
2014232534.tif 000011
【００７７】
決定ステップＳ２０が依存する、点集合上の関係「コピーである」は、同値関係である。それを証明するには、以下の特性をチェックすれば十分であり、それは難しくない。（１）点集合はそれ自体のコピーである、（２）ＹがＸのコピーであるならば、ＸはＹのコピーである、（３）ＹがＸのコピーであり、ＺがＹのコピーであるならば、ＺはＸのコピーである。
【００７８】
基本的な代数によれば、点集合の有限集合Ｇ（すなわち、Ｇの要素が点集合である）が与えられた場合、同値関係「コピーである」は、Ｇを、コピーからなる互いに素かつ最大の集合Ｇｉに分類する。これは、ｉ≠ｊならば、Ｇｉ∩Ｇｊ＝φであること、Ｇ＝∪ｉＧｉであること、Ｘ、Ｙ∈Ｇｉならば、ＹはＸのコピーであること、およびＸ∈Ｇｉかつ
【００７９】
【数９】
2014232534.tif 000012
【００８０】
ならば、ＹはＸのコピーでないことを意味する。集合Ｇｉは、実際、同値関係の同値類を参照することによって、点集合の「類」となる。
【００８１】
先の理論は、立体（すなわち、この例におけるモデル化オブジェクトは立体である）の面分に適用される（しかし、それに限定されない）。面分は、点集合の役割を演じ、立体のＢ−Ｒｅｐは、集合Ｇである。言い換えると、決定ステップＳ２０を実施するために、当業者は、面分を点集合として、またＳ１０において提供されるＢ−Ｒｅｐを上で定義されたような集合Ｇとして表すことができる。
【００８２】
決定ステップＳ２０において、コピーの面分から成る組の決定の例が、次に説明される。
【００８３】
例えば、立体を表すモデル化オブジェクトを与えた場合、Ｓ１０において提供される立体のＢ−Ｒｅｐは、１組の独立した面分と見なされる。すなわち、Ｇ＝｛ｆ１、…、ｆｎ｝であり、ここで、ｆｉは、立体の第ｉの面分である。まさに最初のステップは、「コピーである」関係に従って、Ｇの集合を計算することである（すなわち、決定ステップＳ２０）。全体的なアルゴリズムは、以下の通りである。
For i = 1 to n do begin
If fi is not already used in a set then
Create a new set Gi := {fi}
For j := i + 1 to n do begin
If fj is not already used in a set then
If fj is a copy of fj then
Gi := Gi∪{fｊ}
Store the rigid motion that
changes fi into fｊ
End if
End if
End for
End if
End for
分かるように、したがって、最初に、コピーから成るすべての組が決定され、後で説明されるように、決定された組に変更を施すことも可能である。
【００８４】
面分に対して「コピーである」関係をいかに実施するかについての例が、次に説明される。
【００８５】
先に説明したように、立体の面分は、サポート曲面（例えば平面）と、境界稜線とによって定義される。一例では、面分は、立体の外向きの法線ベクトルを備える。境界稜線は、この法線ベクトルに従って方向付けされる。境界稜線は、共有頂点によって接続される。
【００８６】
比較を実行して、剛体運動を見つけるため、各面分は、いくつかの軸系（ａｘｉｓ  ｓｙｓｔｅｍ）を備える。面分の各頂点ｖでは、軸系は、以下のように生成される。原点Ｐの座標は、頂点ｖの座標である。Ｕで表される第１のベクトルは、ｖの入力境界稜線の接線であり、−Ｕは、境界稜線と同じに方向付けされる。Ｖで表される第２のベクトルは、ｖの出力境界稜線の接線であり、境界稜線の方向に方向付けされる。「入力」および「出力」という語は、面分の法線ベクトルに従った、境界稜線の位相的方向付けに関連する。第３のベクトルは、頂点ｖにおいて計算される、面分の外向きの法線ベクトルＮである。Ｎは常にＵおよびＶに対して垂直であるにも係わらず、軸系（Ｐ，Ｕ，Ｖ，Ｎ）は、概して、有向でなく、直交しないことに留意されたい。
【００８７】
図９〜図１１は、半円筒面分９０の軸系を示している。図９は、面分９０と、その法線ベクトル９２とを示している。図１０は、法線ベクトル９２によって誘導される境界稜線９４の位相的方向付けを示している。境界稜線ａは、頂点ｖの入力稜線である。境界稜線ｂは、頂点ｖの出力稜線である。図１１は、各境界頂点における軸系のベクトルＵ、Ｖ、Ｎを表示している。
【００８８】
ここで、方法は、一例では、決定ステップＳ２０内において、２つの面分が互いのコピーであるかどうかを、存在するならば、それらの間の剛体運動を探索することによって判定することができる。ｆ、ｇを、（同数の）局所軸系
【００８９】
【数１０】
2014232534.tif 000013
【００９０】
および
【００９１】
【数１１】
2014232534.tif 000014
【００９２】
をそれぞれ備える、２つの面分とする。面分ｆ、ｇが、同数の局所軸系を有さない場合、それは、それらが、同数の境界頂点を有さないことを意味し、そのため、それらは互いのコピーではないと判定され、剛体運動探索は開始されない。方法はそのような条件をテストし得る。
【００９３】
第１のステップは、面分ｆの第ｉの軸系を面分ｇの第ｊの軸系に変更する剛体運動Ｄｉ，ｊをそれぞれ計算することである。ｉ、ｊ＝１、…、ｍであるので、最大でｍ２個のそのような剛体運動が存在する。形式的に、剛体運動は、
【００９４】
【数１２】
2014232534.tif 000015
【００９５】
のようになる。
【００９６】
【数１３】
2014232534.tif 000016
【００９７】
、
【００９８】
【数１４】
2014232534.tif 000017
【００９９】
、およびＤｉ，ｊ（ｘ）＝Ｒｉ，ｊｘ＋Ｔｉ，ｊであり、これは、未知数が、行列Ｒｉ，ｊの係数と、ベクトルＴｉ，ｊの座標であることに留意して、最初に、以下の線形システムを解くことによって獲得されることに留意されたい。
【０１００】
【数１５】
2014232534.tif 000018
【０１０１】
第２に、行列Ｒｉ，ｊが回転であることを保証するために、以下の２つの条件が、チェックされなければならない。
【０１０２】
Ｒｉ，ｊＲｉ，ｊＴ＝Ｉ
ｄｅｔ（Ｒｉ，ｊ）＝１
これらが満たされない場合、Ｒｉ，ｊは回転ではないので、Ｄｉ，ｊは剛体運動ではない。
【０１０３】
その後、ｆをｇに変更する剛体運動Ｄ＊が、存在するならば、先に計算されたＤｉ，ｊの中から見出される。ここでの問題は、ｆ、ｇ、および剛体運動Ｄが与えられた場合、Ｄ（ｆ）＝ｇは真か？という質問に答えることである。これは、３Ｄ点ｘｋ、ｋ＝１、…、ｑの集まりで面分ｆをサンプリングし、点Ｄ（ｘｋ）と面分ｇの間の距離が、同一のオブジェクトについての所定の閾値数値と比較して、十分に小さいことをチェックすることによって、行うことができる。Ｄｉ，ｊの中のいくつかの剛体運動がｆをｇに変更できる場合、可能なときは、純粋な並進が選択される。これは、決定ステップＳ２０を実行する効率的な方法であり、ユーザの意図に沿った結果をもたらす。
【０１０４】
次に、上で説明された例の反復に従ってＳ２０において決定された組のためのデータ構造の一例が説明される。
【０１０５】
剛体運動および関連する点集合は、（所与の面分に対応する）所与の点集合のコピーと、関連する剛体運動とを取り出すために、次に説明される適切なデータ構造内に記憶することができる。概念的に、このデータ構造は、有向グラフＷ＝（Ｐ，Ａ，α，ω）を含み、ここで、ノードＰは、点集合であり、弧Ａは、剛体運動によってラベル付けされる。ラベル付けは、写像ｍ：Ａ→ＳＥ（３）であり、ここで、ＳＥ（３）は、３次元剛体運動のグループである。より正確には、弧ｕ∈Ａは、ノードα（ｕ）＝ｘ∈Ｐで開始し、ノードω（ｕ）＝ｙ∈Ｐで終了するという記述は、点集合ｘと点集合ｙが、互いのコピーであること、および剛体運動ｍ（ｕ）が、ｘをｙに変更し、それは、ｙ＝ｍ（ｕ）ｘと表記されることを意味する。ここで、弧ｖ∈Ａが、ｘとｚ∈Ｐとを接続し、それが、α（ｖ）＝ｘ、ω（ｖ）＝ｚと記述されると仮定する。ｘをｚに変更する剛体運動は、ｚ＝ｍ（ｖ）ｘである。その場合、ｚは、ｙのコピーでもあり、ｙをｚに変更する剛体運動は、ｚ＝ｍ（ｖ）ｍ（ｕ）−１ｙである。反対に、ｚをｙに変更する剛体運動は、ｙ＝ｍ（ｕ）ｍ（ｖ）−１ｚである。この情報はすべて、データ構造によって保存することができる。
【０１０６】
性質上、初期サブセットを計算するアルゴリズムは、それらの各々がサブセットである、深度１の木グラフから作成される、グラフを生成する。定義上、深度１の木は、入力弧のない１つのノード（根ノード）と、出力弧のない他のすべてのノード（葉ノード）とを有する木グラフである。言い換えると、すべての非根ノードは、根ノードに接続される。結果として、深度１の木グラフ内の任意の２つのノードを与えた場合、それらを連結する弧からなる経路がただ１つ存在し、この一意的な経路は、ただ２つの弧を含む。
【０１０７】
図１２〜図１３は、初期のコピーされた面分の組を計算するアルゴリズムからもたらされる、グラフデータ構造を示している。図１２は、面分に１から１２までの番号が付された、一列に並んだ４つの円筒スロットから成る、モデル化オブジェクトのＢ−Ｒｅｐ１２０を示している。それらには、位相的データ構造内におけるある任意の記憶に従って、番号が付されている。図１３は、２つの深度１の木１３２を含む、グラフ１３０を示している。
【０１０８】
したがって、１つの点集合を他の任意の点集合に変更する剛体運動は、２つの点集合を連結する弧からなる経路に沿って剛体運動を組み合わせることによって計算される。この経路は２つの弧を含むので、ただ２つの剛体運動が組み合わされる。サブセット内の任意の２つの点集合に関連する剛体運動を計算するこの機能は、方法のこの例において広く使用される。
【０１０９】
次に、第１のデータおよび第２のデータを決定するステップＳ４０が説明される。
【０１１０】
基準関数および別の関数は、ナーブスまたは先に説明された他の種類の関数など、任意のタイプの関数とすることができ、したがって、大量のデータを必要とすることがある。方法は、第１のデータおよび第２のデータを決定し、それらは、ポインタと一緒になって、概して、圧縮された「別の」関数よりも小さいデータを形成する。
【０１１１】
方法では、「写像」という用語は、概して、関数と比較して相対的に少ないデータしか必要としない特定の種類の関数を指す。具体的には、「写像」という用語は、正準関数（ｃａｎｏｎｉｃａｌ  ｆｕｎｃｔｉｏｎ）（すなわち、単純な正準式を用いて表現される関数）を指すことができる。例えば、方法の写像は、３Ｄ空間（すなわち、値域）のペアの間、もしくは３Ｄ空間とそれ自体との間の剛体運動、および／または２Ｄ空間（すなわち、定義域）のペアの間、もしくは２Ｄ空間とそれ自体との間の２Ｄ局所写像などの、アフィン写像とすることができる。いずれの場合も、写像は、例えば、後の展開方法に知られた、所定の形式を有することができる。このように、第１のデータおよび第２のデータは、（写像の性質に関するいかなる情報も排除して）写像のパラメータのみを含むことができる。このように、置き換えるステップＳ５０において使用されるデータは、可能な限り小さい。
【０１１２】
ここで、方法は、Ｓ４０において、写像を記述するデータを決定する。これは、第１のデータおよび／または第２のデータが、検討中の写像の式自体、（例えば、写像がアフィン写像であると事前に決定された場合には）上で説明されたような写像のパラメータの値のみ、または例えば、写像の逆写像の式もしくは値もしくはパラメータによって、前記写像を間接的に記述するための方法を含み得ることを意味する。さらに、方法が、幾何学的実体のコピーの組について、そのような各組内で反復する場合、決定するステップＳ４０の異なる反復において写像が偶然互いに関係し得ることに留意されたい。これは、例えば、サポート曲面および境界曲線を含む面分のコピーが検討される場合である。そのような場合、曲面のコピーに対応する関数（例えば、曲面定義）の定義域間の写像は、同じとすることができ、または境界曲線（例えば、ｐ曲線）のコピーに対応する関数の値域間の写像の逆写像とすることができる。そのような場合、第１のデータおよび／または第２のデータは、（例えば、決定するステップＳ４０の先行する反復において）先に決定された第１のデータおよび／または第２のデータを指すポインタ、ならびに少なくとも決定するステップＳ４０の１つの反復における、２つの写像間の関係の性質についての１つの情報を含むことができる。これは、決定するステップＳ４０および置き換えるステップＳ５０の異なる反復における写像の「再利用」によって、さらなる圧縮を可能にする。
【０１１３】
関数は、パラメトリック関数を含むことができる。そのような場合、基準関数の値域から別の関数の値域への写像（すなわち、第１のデータによって記述される写像）、および別の関数の定義域から基準関数の定義域への写像（すなわち、第２のデータによって記述される写像）は、アフィン写像である。これは、これらの写像が、１または複数のパラメータの線形表現として定式化される関数であることを意味する。アフィン写像は簡単に表現され得るので、これは、高い圧縮率を可能にする。
【０１１４】
具体的には、関数は、曲面定義（すなわち、曲面に対応する関数）を含むことができる。そのような場合、検討中の基準関数と別の関数が、互いのコピーである曲面に対応するような曲面定義であるとき、基準関数の値域から別の関数の値域への写像は、基準関数に対応する曲面を別の関数に対応する曲面に変換する剛体運動である。そのような剛体運動は、都合のよいことに、上で説明されたように、面分をコピー面分の組に区分するときに事前に決定され得る。したがって、方法は、高速に実行され得る。別の関数の定義域から基準関数の定義域への写像は、後で説明されるように、２Ｄ局所写像である。
【０１１５】
さらに、関数は、ｐ曲線（すなわち、曲線に対応し、曲面定義の２Ｄ定義域内に像を有する１つのパラメータの関数として提供される関数）を含むことができる。そのような場合、検討中の基準関数と別の関数が、互いのコピーである曲線に対応するようなｐ曲線であるとき、基準関数の値域から別の関数の値域への写像は、基準関数の値域から別の関数の値域への２Ｄ局所写像であり、別の関数の定義域から基準関数の定義域への写像は、１Ｄ局所写像である。前述の２Ｄ局所写像は、関数（基準関数および別の関数）が、現在の反復のｐ曲線が関連する曲面定義である、反復において先に決定され得た、別の関数の値域から基準関数の値域への２Ｄ局所写像の逆写像である。これは、後で説明される。これは、先に決定された情報が再利用され得るので、方法を高速化し、圧縮を高める。実際に、現在の反復の第１のデータは、２Ｄ局所写像の前述の逆写像が検討されることを指定することによって、問題の先の反復の第２のデータを単純に参照することができる。
【０１１６】
先に説明されたように、関数は、互いのコピーである面分を定義することができる。各面分は、１つの基準曲面定義、少なくとも１つの他の曲面定義、基準曲面定義の定義域内に含まれる値域を有する少なくとも１つのｐ曲線の基準組、および他の曲面定義の定義域内に値域を有し、基準組のそれぞれのものに対応する少なくとも１つのｐ曲線の別の組（すなわち、各「他の」ｐ曲線は、「基準」面分の、すなわち、基準曲面定義およびｐ曲線によって定義されるもののコピーである面分の境界曲線に対応し、前述の境界曲線は、基準面分のそれぞれの境界曲線のコピーである）によって定義され得る。
【０１１７】
そのような場合、置き換えるステップＳ５０は、他の曲面定義および（ｐ曲線の）別の組を、すべてが異なる要素を記述するデータを形成する、先に説明されたようなＳ４０のいくつかの反復によって決定される、第１のデータおよび第２のデータによって置き換えるステップを含む。これらの要素は、基準曲面定義を指すポインタを含む。これらの要素は、（ｐ曲線の）別の組の各々のものについて、基準組の対応するもの（基準ｐ曲線）を指すポインタも含む。これらの要素は、基準曲面定義に対応する曲面を他の曲面定義に対応する曲面に変換する剛体運動、他の曲面定義の定義域から基準曲面定義の定義域への２Ｄ局所写像、および別の組の各々のものの定義域から基準組の対応するものの定義域への１Ｄ局所写像も含む。そのような場合、方法は、圧縮比に関して、特に効率的である。
【０１１８】
次に、方法によって使用され得る２Ｄ局所写像の定義が説明される。
【０１１９】
【数１６】
2014232534.tif 000019
【０１２０】
および
【０１２１】
【数１７】
2014232534.tif 000020
【０１２２】
を、２つの３次元のパラメータ化された曲面（すなわち、パラメトリック曲面定義）とする。定義域ＡおよびＢは、
【０１２３】
【数１８】
2014232534.tif 000021
【０１２４】
（の部分集合）である。定義によって、曲面ＰおよびＱの値域は、
【０１２５】
【数１９】
2014232534.tif 000022
【０１２６】
の部分集合である。
【０１２７】
Ｒ（Ｐ）＝｛Ｐ（ｕ，ｖ）；（ｕ，ｖ）∈Ａ｝
および
Ｒ（Ｑ）＝｛Ｑ（ｓ，ｔ）；（ｓ，ｔ）∈Ｂ｝
である。
【０１２８】
曲面Ｑが曲面Ｐからの複製（すなわち、コピー）であると言う場合、それは、曲面Ｐの値域の移動がそれを曲面Ｑに一致させるような、（先に説明されたように、面分を区分するときに、決定され得る）剛体運動
【０１２９】
【数２０】
2014232534.tif 000023
【０１３０】
が存在することを意味する。
【０１３１】
Ｄ（Ｒ（Ｐ））＝Ｒ（Ｑ）
言い換えると、これは、すべての（ｕ，ｖ）∈Ａに対して、
Ｄ（Ｐ（ｕ，ｖ））＝Ｑ（ｓ，ｔ）
であるような、（ｓ，ｔ）∈Ｂが存在すること、その反対も成り立つことを意味する。先の等式は、パラメータの定義域ＡとＢの間の対応を暗黙的に定義している。２Ｄ局所写像の目標は、この対応を明示的にすることである。定義によって、剛体運動Ｄと一緒に曲面ＰおよびＱに関連付けられた２Ｄ局所写像は、すべての（ｓ，ｔ）∈Ｂに対して、
Ｄ（Ｐ（ｑ（ｓ，ｔ）））＝Ｑ（ｓ，ｔ）
であるような、写像ｑ：Ｂ→Ａである。
【０１３２】
これは、等価的に
【０１３３】
【数２１】
2014232534.tif 000024
【０１３４】
と書いてもよい。
【０１３５】
写像ｑおよびその逆写像の座標を扱うことが有益なことがある。そのため、以下の記法が、有益なことがある。
【０１３６】
ｑ（ｓ，ｔ）＝（ｆ（ｓ，ｔ），ｇ（ｓ，ｔ））
および
ｑ−１（ｕ，ｖ）＝（ｆ＊（ｕ，ｖ），ｇ＊（ｕ，ｖ））
次に、方法によって使用される１Ｄ局所写像の定義が説明される。
【０１３７】
先の幾何学的オブジェクトに加えて、ｐ曲線
【０１３８】
【数２２】
2014232534.tif 000025
【０１３９】
が、曲面Ｐ上で定義され、ｐ曲線
【０１４０】
【数２３】
2014232534.tif 000026
【０１４１】
が、曲面Ｑ上で定義される。定義域ＩおよびＪは、
【０１４２】
【数２４】
2014232534.tif 000027
【０１４３】
（の区間）である。定義によって、これらのｐ曲線の値域は、それぞれ
【０１４４】
【数２５】
2014232534.tif 000028
【０１４５】
の以下の部分集合
【０１４６】
【数２６】
2014232534.tif 000029
【０１４７】
および
【０１４８】
【数２７】
2014232534.tif 000030
【０１４９】
である。
【０１５０】
剛体運動Ｄが、ｐ曲線
【０１５１】
【数２８】
2014232534.tif 000031
【０１５２】
の値域をｐ曲線
【０１５３】
【数２９】
2014232534.tif 000032
【０１５４】
の値域に変更する、すなわち、
【０１５５】
【数３０】
2014232534.tif 000033
【０１５６】
つまり、すべてのμ∈Ｊに対して、
【０１５７】
【数３１】
2014232534.tif 000034
【０１５８】
であるような、λ∈Ｉが存在すると仮定する。
【０１５９】
これは、定義域ＩとＪの間の対応を暗黙的に定義している。ここでもやはり、１Ｄ局所写像は、この対応を明示的にする。定義によって、曲面Ｐ、Ｑ、ｐ曲線
【０１６０】
【数３２】
2014232534.tif 000035
【０１６１】
、および剛体運動Ｄに関連付けられた１Ｄ局所写像は、すべてのμ∈Ｊに対して、
【０１６２】
【数３３】
2014232534.tif 000036
【０１６３】
であるような、写像ｒ：Ｊ→Ｉである。
【０１６４】
しかし、すべての（ｓ，ｔ）∈Ｂに対して、Ｄ（Ｐ（ｑ（ｓ，ｔ）））＝Ｑ（ｓ，ｔ）である、局所写像ｑのおかげで、そのため、すべてのμ∈Ｊに対して、
【０１６５】
【数３４】
2014232534.tif 000037
【０１６６】
であり、その場合、
【０１６７】
【数３５】
2014232534.tif 000038
【０１６８】
である。
【０１６９】
剛体運動Ｄは可逆であるので、また曲面Ｐは単射であるので、これは、
【０１７０】
【数３６】
2014232534.tif 000039
【０１７１】
であることを暗示し、最後に、逆２Ｄ局所写像ｑ−１を使用することによって、
【０１７２】
【数３７】
2014232534.tif 000040
【０１７３】
である。
【０１７４】
これは、等価的に、
【０１７５】
【数３８】
2014232534.tif 000041
【０１７６】
または
【０１７７】
【数３９】
2014232534.tif 000042
【０１７８】
と書くことができる。
【０１７９】
この関係は、曲面Ｑ上のｐ曲線を、局所写像と合成された曲面Ｐ上のｐ曲線と結び付けるので、方法のこの例の主要な特徴である。
【０１８０】
完全を期して、０Ｄ局所写像の定義も説明されるが、提供される圧縮の例では必要とされない。
【０１８１】
先の幾何学的オブジェクトに加えて、ｐ頂点λ０が、ｐ曲線
【０１８２】
【数４０】
2014232534.tif 000043
【０１８３】
上で定義され、ｐ頂点μ０が、ｐ曲線
【０１８４】
【数４１】
2014232534.tif 000044
【０１８５】
上で定義される。これらのｐ頂点の値域は、それぞれ、それらの３Ｄ座標
【０１８６】
【数４２】
2014232534.tif 000045
【０１８７】
である。
である。さらに、剛体運動Ｄが、ｐ頂点λ０（の値域）をｐ頂点μ０（の値域）に変更し、つまり、
【０１８８】
【数４３】
2014232534.tif 000046
【０１８９】
である。
【０１９０】
０Ｄ局所写像は、値ｒ（μ０）であり、ここで、ｒ（−）は、ｐ曲線の１Ｄ局所写像である。その場合、λ０＝ｒ（μ０）であるので、ｐ曲線
【０１９１】
【数４４】
2014232534.tif 000047
【０１９２】
上で定義されたｐ頂点μ０および適切な１Ｄ局所写像を使用することによって、ｐ曲線
【０１９３】
【数４５】
2014232534.tif 000048
【０１９４】
上で定義されたｐ頂点λ０を計算することが可能である。
【０１９５】
次に、２Ｄ局所写像およびその決定の一例が提供される。
【０１９６】
曲面Ｐを、図１４に示された、
【０１９７】
【数４６】
2014232534.tif 000049
【０１９８】
によってパラメータ化されたｚ軸方向の円筒とする。
【０１９９】
曲面Ｑを、図１５に示された、
【０２００】
【数４７】
2014232534.tif 000050
【０２０１】
によってパラメータ化されたｘ軸方向の円筒とする。
【０２０２】
明らかに、ｙ軸の周りのπ／２回転による曲面Ｐの値域の移動は、それを曲面Ｑの値域と一致させる。前記回転の行列は、
【０２０３】
【数４８】
2014232534.tif 000051
【０２０４】
である。
【０２０５】
その後、定義
【０２０６】
【数４９】
2014232534.tif 000052
【０２０７】
から開始する単純な計算によって、以下の２Ｄ局所写像
【０２０８】
【数５０】
2014232534.tif 000053
【０２０９】
が得られる。
【０２１０】
それは、すべての（ｓ，ｔ）に対して、Ｄ（Ｐ（ｆ（ｓ，ｔ），ｇ（ｓ，ｔ）））＝Ｑ（ｓ，ｔ）であるようにする。
【０２１１】
逆２Ｄ局所写像は、
【０２１２】
【数５１】
2014232534.tif 000054
【０２１３】
である。
【０２１４】
それは、すべての（ｕ，ｖ）に対して、Ｄ（Ｐ（ｕ，ｖ））＝Ｑ（ｆ＊（ｕ，ｖ），ｇ＊（ｕ，ｖ））であるようにする。
【０２１５】
次に、１Ｄ局所写像およびその決定の一例が提供される。
【０２１６】
曲面Ｐ上のｐ曲線
【０２１７】
【数５２】
2014232534.tif 000055
【０２１８】
（図１６の点線１６０）は、
【０２１９】
【数５３】
2014232534.tif 000056
【０２２０】
において
【０２２１】
【数５４】
2014232534.tif 000057
【０２２２】
によってパラメータ化された曲線を定義する。
【０２２３】
この曲線は、中心が（０，０，ｂｖ０）で、半径がａの、ｚ軸と直交する円（図１７の点線１７０）である。
【０２２４】
曲面Ｑ上のｐ曲線
【０２２５】
【数５５】
2014232534.tif 000058
【０２２６】
（図１８の点線１８０）は、中心が（ｂｖ０，０，０）で、半径がａの、ｘ軸と直交する円（図１９の点線１９０）を定義する。それは、
【０２２７】
【数５６】
2014232534.tif 000059
【０２２８】
によってパラメータ化される。
【０２２９】
剛体運動Ｄによる曲面Ｐ上の円の移動が、曲面Ｑ上の円を（値域の観点から）もたらす。１Ｄ局所写像
【０２３０】
【数５７】
2014232534.tif 000060
【０２３１】
は、
【０２３２】
【数５８】
2014232534.tif 000061
【０２３３】
から開始することによって、定義に従って計算され得る。これは、以下の１Ｄ局所写像
【０２３４】
【数５９】
2014232534.tif 000062
【０２３５】
をもたらす。
【０２３６】
それは、すべてのμに対して、
【０２３７】
【数６０】
2014232534.tif 000063
【０２３８】
であるようにする。
【０２３９】
次に、方法を用いてどのように圧縮が実行され得るかを示す一例が説明される。
【０２４０】
例では、入力データは、ソリッドモデルのＢ−Ｒｅｐである。第１のステップは、すべての重複する曲面およびｐ曲線をＢ−Ｒｅｐ上で認識することである。これは、先に説明されたように、コピー面分を認識することによって実行され得る。先に説明されたアルゴリズムは、重複するサポート曲面および重複する境界稜線を識別することによって、重複する面分を認識する。この情報から、方法は、重複する曲面のグラフＧと、重複するｐ曲線のグラフＨとを容易に出力することができる。グラフＧ（またはグラフＨ）のノードは、曲面（またはｐ曲線）であり、グラフの弧は、剛体運動によってラベル付けされる。グラフＧ（またはＨ）の連結された各構成要素は、同じ共通の基準の複製である曲面（またはｐ曲線）のグループである。連結された各構成要素では、本例の方法は、基準ノードである１つのノードを任意に選択する。
【０２４１】
曲面の値域
【０２４２】
【数６１】
2014232534.tif 000064
【０２４３】
を、曲面の値域
【０２４４】
【数６２】
2014232534.tif 000065
【０２４５】
に変更する適切な剛体運動Ｄを見出すために、先に説明され、ここでも使用され得るアルゴリズムが、１つの曲面の点から他のものへのいくつかの射影を実行することが分かる。特に、これは、Ｄ（Ｐ（ｕｉ，ｖｉ））＝（ｓｉ，ｔｉ）であるような、パラメータ（ｕｉ，ｖｉ）と（ｓｉ，ｔｉ）のいくつかの対をもたらす。それらは、都合のよいことに、以下で再利用され得る。
【０２４６】
例における第２のステップは、局所写像を計算することである。例は、アフィン局所写像のみを扱う。これは、アフィン局所写像が僅かな計算時間および僅かな記憶空間しか必要としないので有利である。さらに、産業界の経験は、立体を用いて機械部品をモデル化する場合、非アフィン局所写像は不必要のように思えることを示している。非基準曲面Ｑ（「他の」曲面）が基準曲面Ｐから複製されるたびに、２Ｄアフィン局所写像が計算される。２Ｄアフィン局所写像は、
【０２４７】
【数６３】
2014232534.tif 000066
【０２４８】
と書くことができ、そのため、６つの係数ｑｉ、ｉ＝１、…、６が識別されなければならない。これは、都合がよいことに、ｊ＝１、２、３に対して、
【０２４９】
【数６４】
2014232534.tif 000067
【０２５０】
を第１の認識ステップから収集することによって行われ得る。これは、未知数ｑｉ、ｉ＝１、…、６に対して、標準的な線形代数学を使用することによって解かれる、３×２＝６個の線型方程式をもたらす。この（候補）アフィン局所写像が曲面全体において効率的であることを保証するために、いくつかの特別な検証が実行され得る。これは、アフィン局所写像検証に関して、後で詳述される。
【０２５１】
非基準ｐ曲線が基準ｐ曲線から複製されるたびに、１Ｄアフィン局所写像が計算される。それは、
ｒ（μ）＝ｒ１μ＋ｒ０
によって定義される。
【０２５２】
未知係数ｒｉ，ｉ＝０、１は、ｊ＝１、２に対して、
ｒ（μｊ）＝λｊ
を第１の認識ステップから収集することによって獲得される。これは、未知数ｒｉ，ｉ＝０、１に対して、標準的な線形代数学を使用することによって解かれる、２個の線型方程式をもたらす。
【０２５３】
最終ステップは、圧縮自体である。圧縮は、非基準幾何学形状を、局所写像、剛体運動、および基準幾何学形状を指すポインタによって置き換える。より正確には、非基準曲面Ｑは、以下の３つ組によって置き換えられる：
・  基準曲面Ｐを指すポインタ
・  剛体運動Ｄ
・  ２Ｄアフィン局所写像ｑ
（その基準曲面がＰである）非基準曲面Ｑ上で定義された非基準ｐ曲線
【０２５４】
【数６５】
2014232534.tif 000068
【０２５５】
は、以下の３つ組によって置き換えられる：
・  基準曲面Ｐ上で定義された基準ｐ曲線
【０２５６】
【数６６】
2014232534.tif 000069
【０２５７】
を指すポインタ
・  ２Ｄアフィン局所写像ｑ
・  １Ｄアフィン局所写像ｒ
圧縮解除は、以下のように実行される。非基準曲面Ｑの数学的定義は、以下の式
【０２５８】
【数６７】
2014232534.tif 000070
【０２５９】
に従って、その基準曲面Ｐ、関連する剛体運動Ｄ、および２Ｄアフィン局所写像ｑを取り出すことによって回復される。
【０２６０】
非基準ｐ曲線
【０２６１】
【数６８】
2014232534.tif 000071
【０２６２】
の数学的定義は、以下の式（ｑの逆写像ｑ−１は実行中に容易に計算され得る）に従って、局所写像ｑおよびｒ、ならびに基準ｐ曲線
【０２６３】
【数６９】
2014232534.tif 000072
【０２６４】
を取り出すことによって回復される。
【０２６５】
【数７０】
2014232534.tif 000073
【０２６６】
明らかに、圧縮解除を高速で安全なものにする、ごく単純な評価が必要とされる。
【０２６７】
本例の決定するステップＳ４０は、アフィン局所写像検証をさらに含むことができる。これが、以下で説明される。
【０２６８】
ｉ＝１、２、３に対して、
Ｄ（Ｐ（ｑ（ｓｉ，ｔｉ）））＝Ｑ（ｓｉ，ｔｉ）
であるような２Ｄアフィン局所写像ｑを計算することが、必ずしも、すべての（ｓ，ｔ）に対して、
Ｄ（Ｐ（ｑ（ｓ，ｔ）））−Ｑ（ｓ，ｔ）＝０
をもたらすとは限らない。
【０２６９】
特別なチェックが有利である。原理は、曲面ＰおよびＱの次数に応じて、十分に多くの数々の点（ｓｉ，ｔｉ）について、先の関係をチェックすることである。曲面ＰおよびＱが、平面またはＢスプラインである場合、以下の関数は、多項式である。
【０２７０】
ｆ（ｓ，ｔ）＝Ｄ（Ｐ（ｑ（ｓ，ｔ）））−Ｑ（ｓ，ｔ）
ＰまたはＱが、（正準曲面および自由形式曲面を含む）ナーブス曲面である場合、関数ｆ（ｓ，ｔ）は、有理関数であるが、基本的な代数操作が、それを多項式関数に変更し得る。いずれにせよ、ポイントは、すべての（ｓ，ｔ）に対して、多項式関数ｆ（ｓ，ｔ）がゼロになるかどうかをチェックすることである。それは、
【０２７１】
【数７１】
2014232534.tif 000074
【０２７２】
と書くことができ、ここで、ｇｊは、多項式である。ｔのｄｔ＋１個の値に対して、ｆ（ｓ１，ｔ）＝０であることのチェックは、ｊ＝０、…、ｄｔに対して、ｇｊ（ｓ１）＝０であることを暗示する。ｄｓが多項式ｇｊの最大の次数である場合、このプロセスをｄｓ＋１回繰り返すことは、ｊ＝０、…、ｄｔに対して、またすべてのｓに対して、ｇｊ（ｓ）＝０であることを保証する。これは、関数ｆがゼロ関数であり、そのため、すべての（ｓ，ｔ）に対して、アフィン局所写像ｑが有効であることを意味する。多項式関数ｆは明示的である必要はなく、曲面ＰおよびＱの次数を検討することによって獲得され得る、その次数のみが関連することに留意されたい。
【０２７３】
検証が失敗した場合、曲面Ｑは圧縮されない。
【０２７４】
既存の圧縮技法は、データの低レベルの意味、すなわち、メッシュ三角形、データ構造（ポインタ、配列）、および幾何学的座標を扱う。そのため、ソリッドモデルが正確な幾何学形状から作成される場合、メッシュベースの圧縮技法は、正常に機能しない。さらに、ソリッドモデルが、同一形状の多くの発生を必要とする場合、各発生は、独立に圧縮され、したがって、データ削減の大きな可能性を失う。
【０２７５】
反対に、説明された方法は、機械部品の形状に非常に頻繁に発生する、繰り返される特徴を利用する。第１のステップにおいて、方法は、すべての類似の幾何学形状を認識する。考慮される幾何学形状は、Ｂ−Ｒｅｐモデルにおいて広く使用される、曲面およびｐ曲線である。この認識ステップは、コピーの空間位置および局所写像をもたらす。局所写像は、２つの重複する幾何学形状のパラメータ定義域を橋渡しする。次いで、方法は、重複する各幾何学形状ごとに、剛体運動および局所写像と一緒に、基準幾何学形状を指すポインタから成る、繰り返される幾何学形状のディクショナリを作成する。入力されたＢ−Ｒｅｐの圧縮されたバージョンは、圧縮された幾何学形状のみを含み、位相的データは、変更されない。
【０２７６】
本例の方法の第１の利点は、幾何学形状の圧縮が、Ｂ−Ｒｅｐデータの量をかなり削減することである。実際に、ダッソー・システムズにおいて機械ＣＡＤモデルの代表的なデータベース上で実行された工業実験は、メモリの７４％が幾何学形状によって占められ、対照的にトポロジによって占められるのは２５％であることを示している。したがって、幾何学形状の圧縮は、データ記憶のためのメモリを節約し、ネットワーク環境におけるデータ伝送を高速化する。
【０２７７】
第２の利点は、本明細書で説明される方法から得られるＢ−Ｒｅｐモデルを圧縮するために、既存の圧縮技法が使用され得ることである。言い換えると、本発明は、既存の圧縮技法に対するプリプロセッサとして使用され得る。
【０２７８】
第３の利点は、圧縮解除方法がどのような数値計算も実行しないことである。圧縮解除は、基準曲面およびｐ曲線を剛体運動および局所写像と組み合わせることによって、曲面およびｐ曲線の元のフォーマットを回復する。局所写像なしの場合、圧縮解除される非基準幾何学形状のパラメータ化が変化し、数値射影または共通部分を不可避にし、それは潜在的に安全ではない。
【０２７９】
次に、方法によって提供される結果が説明される。
【０２８０】
メモリサイズの観点から、剛体運動は、軸ベクトル、角度値、および並進ベクトルによって定義され、そのため、剛体運動を記憶するためのメモリサイズは、７つの実数である。２Ｄ局所写像は、６つの実数によって定義され、１Ｄ局所写像は、２つの実数によって定義される。圧縮比は、幾何学形状の性質に依存する。ナーブス幾何学形状は、（メモリサイズに関して）任意の大きさとすることができ、前述の幾何学形状は、一定のサイズのデータによって置き換えられるので、そのため、圧縮比も、同様に任意の大きさとすることができる。正準な幾何学形状（平面、円筒、円錐、球、トーラス）も、それらが一定のサイズを有するにも係わらず、同様に圧縮され得る。以下は、圧縮比に関する出願人の実験である。
【０２８１】
【表２】
2014232534.tif 000075
【０２８２】
次に、方法による圧縮の全体的な例が図２０〜図２７を参照して説明される。
【０２８３】
本例のＢ−Ｒｅｐモデルは、曲面Ｓ上で定義され、ｎ個のｐ曲線ｐｉ、ｉ＝１、…、ｎによって境界付けされた、面分Ｆを含む。それは、図２０に示されるように、空間内の別個の位置に配置された、面分Ｆのｍ個のコピーＦｊ、ｊ＝１、…、ｍも含み、ここで、ｎ＝４、ｍ＝２である。
【０２８４】
コピーされた面分の曲面は、Ｓｊ、ｊ＝１、…、ｍで表され、面分Ｆｊを境界付けるｐ曲線は、
【０２８５】
【数７２】
2014232534.tif 000076
【０２８６】
、ｉ＝１、…、ｎで表され、それらは、それらのサポート曲面を指し示す。
【０２８７】
各幾何学要素は、図２２〜図２４の概略図に示されるように、独自の数学的記述２２０を備える。
【０２８８】
アルゴリズムは、面分Ｆｊが、それぞれ、剛体運動Ｄｊを介する面分Ｆのコピーであることを認識する。その結果、ｊ＝１、…、ｍに対して、Ｄｊ○Ｓ○ｑｊ＝Ｓｊであるような、２Ｄ局所写像ｑｊが提供され、同じく、ｉ＝１、…、ｍおよびｊ＝１、…、ｎに対して、
【０２８９】
【数７３】
2014232534.tif 000077
【０２９０】
であるような、１Ｄ局所写像
【０２９１】
【数７４】
2014232534.tif 000078
【０２９２】
が提供される。ｎ＝４およびｍ＝２の場合の、圧縮されたモデルを表すデータ構造が、図２５〜図２７に示されている。各２Ｄ局所写像が、同じ曲面上のすべてのｐ曲線によって共有されることに留意されたい。各曲面Ｓｊの数学的記述は、（基準曲面Ｓを指す）ポインタ、剛体運動（７個の実数）、および２Ｄ局所写像（６個の実数）を含むデータ２６０の一定のサイズのブロックによって置き換えられる。各ｐ曲線
【０２９３】
【数７５】
2014232534.tif 000079
【０２９４】
の数学的記述は、（基準ｐ曲線ｐｉを指す）ポインタ、および１Ｄ局所写像
【０２９５】
【数７６】
2014232534.tif 000080
【０２９６】
（２個の実数）を含むデータ２６０の一定のサイズのブロックによって置き換えられる。
【図１】
2014232534.tif 000081
【図２】
2014232534.tif 000082
【図３】
2014232534.tif 000083
【図４】
2014232534.tif 000084
【図５】
2014232534.tif 000085
【図６】
2014232534.tif 000086
【図７】
2014232534.tif 000087
【図８】
2014232534.tif 000088
【図９】
2014232534.tif 000089
【図１０】
2014232534.tif 000090
【図１１】
2014232534.tif 000091
【図１２】
2014232534.tif 000092
【図１３】
2014232534.tif 000093
【図１４】
2014232534.tif 000094
【図１５】
2014232534.tif 000095
【図１６】
2014232534.tif 000096
【図１７】
2014232534.tif 000097
【図１８】
2014232534.tif 000098
【図１９】
2014232534.tif 000099
【図２０】
2014232534.tif 000100
【図２１】
2014232534.tif 000101
【図２２】
2014232534.tif 000102
【図２３】
2014232534.tif 000103
【図２４】
2014232534.tif 000104
【図２５】
2014232534.tif 000105
【図２６】
2014232534.tif 000106
【図２７】
2014232534.tif 000107
【外国語明細書】
2014232534000001.pdf