(57)【要約】      （修正有）【課題】機械部品の編集可能な骨格の表現をコンピュータによって設計する方法を提供する。【解決手段】機械部品を表す有限要素メッシュＦＥＭの部分集合を提供するＳ２０と、ＦＥＭの部分集合に基づいて、機械部品の骨格の表現を決定するＳ３０とを含む。骨格は、分岐と分岐接合部を有し、各分岐接合部が分岐を接合することを特徴とする。【選択図】図１
2018077830.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータによって実施される、機械部品を設計するための方法であって、
前記機械部品を表す有限要素メッシュ（ＦＥＭ）の部分集合を提供するステップ（Ｓ２０）と、
前記ＦＥＭの前記部分集合に基づいて、前記機械部品の骨格の表現を決定するステップ（Ｓ３０）と
を含み、前記骨格は分岐と分岐接合部を有し、各分岐接合部が分岐を接合する
ことを特徴とする方法。
【請求項２】
前記骨格の表現は、前記部分集合に間引き処理を適用した結果と同じトポロジを有する
ことを特徴とする請求項１に記載の方法。
【請求項３】
前記間引き処理を適用した結果は、それぞれが分岐の末端に対応する前記ＦＥＭの要素と、それぞれが分岐接合部に対応する前記ＦＥＭの要素とを含み、それぞれが分岐の末端に対応する前記ＦＥＭの各要素は、それぞれが分岐接合部に対応する前記ＦＥＭの各要素と、面を共有する
ことを特徴とする請求項２に記載の方法。
【請求項４】
前記間引き処理は、局所的な非多様体の面ジオメトリの作成を禁止する
ことを特徴とする請求項３の方法。
【請求項５】
前記部分集合はトポロジ最適化処理の結果得られ、前記トポロジ最適化処理の境界条件に対応する要素を有しており、前記間引き処理は、前記トポロジ最適化処理の前記境界条件に対応する前記部分集合の要素の除去を禁止する
ことを特徴とする請求項３または４に記載の方法。
【請求項６】
前記間引き処理は、前記部分集合の要素の除去を繰り返すステップを含み、繰り返しのそれぞれで除去される前記部分集合の要素は、各繰り返しにおいて除去が禁止されていない、前記部分集合の全ての境界要素である
ことを特徴とする請求項３〜５のいずれかに記載の方法。
【請求項７】
各繰り返しにおいて、前記間引き処理は、前記部分集合の境界要素を、前記部分集合の別の要素と共有する隣接面の数が最も少ないものから最も多いものへと、順に除去する
ことを特徴とする請求項６に記載の方法。
【請求項８】
前記骨格の表現に基づいて設計を行うステップ（Ｓ４０）をさらに含む
ことを特徴とする請求項１〜７のいずれかに記載の方法。
【請求項９】
前記ＦＥＭの前記部分集合を提供する前に、トポロジ最適化処理を実行（Ｓ１０）して、ＦＥＭの前記部分集合を決定するステップをさらに含む
ことを特徴とする請求項１〜８のいずれかに記載の方法。
【請求項１０】
請求項１〜９のいずれかに記載の方法で設計された機械部品を製造するための方法。
【請求項１１】
請求項１〜９のいずれかに記載の方法を実行するための命令を含むコンピュータプログラム。
【請求項１２】
請求項１１のコンピュータプログラムを記録したコンピュータ読み取り可能な記憶媒体。
【請求項１３】
請求項１１のコンピュータプログラムを記録したメモリに接続されたプロセッサと、グラフィカル・ユーザ・インターフェースとを備えるシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータプログラムおよびシステムの分野に関し、より詳細には、機械部品を設計するための方法、システム、およびプログラムに関する。
【背景技術】
【０００２】
オブジェクトの設計、エンジニアリング、製造のため、多数のシステムおよびプログラムが市場に提供されている。ＣＡＤは、コンピュータ支援設計（Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｄｅｓｉｇｎ）の略語であり、例えば、オブジェクトを設計するためのソフトウェア・ソリューションに関する。ＣＡＥは、コンピュータ支援エンジニアリング（Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｅｎｇｉｎｅｅｒｉｎｇ）の略語であり、例えば、将来の製品の物理的挙動をシミュレーションするためのソフトウェア・ソリューションに関する。ＣＡＭは、コンピュータ支援製造（Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｍａｎｕｆａｃｔｕｒｉｎｇ）の略語であり、例えば、製造工程および動作を定義するためのソフトウェア・ソリューションに関する。このようなコンピュータ支援設計システムにおいて、グラフィカル・ユーザ・インターフェースは、技術の効率に関して、重要な役割を果たす。これらの技術は、製品ライフサイクル管理（Ｐｒｏｄｕｃｔ  Ｌｉｆｅｃｙｃｌｅ  Ｍａｎａｇｅｍｅｎｔ：  ＰＬＭ）システムに組み込むことができる。ＰＬＭとは、企業が、拡張エンタープライズの概念全体にわたって、製品データを共有し、共通の工程を適用し、構想に始まり製品寿命の終わりに至る製品開発のための企業知識を活用するのを支援するビジネス戦略を指す。ダッソー・システムズが提供するＰＬＭソリューション（製品名ＣＡＴＩＡ、ＥＮＯＶＩＡ、ＤＥＬＭＩＡ）は、製品エンジニアリング知識をオーガナイズするエンジニアリング・ハブ、製品エンジニアリング知識を管理する製造ハブ、およびエンジニアリング・ハブと製造ハブの両方に対するエンタープライズ統合と接続を可能にするエンタープライズ・ハブを提供する。全てのシステムは、製品、工程、リソースを結ぶオープンなオブジェクトモデルを提供し、最適化された製品定義、製造準備、生産およびサービスを推進する、動的な知識ベースの製品作成および意思決定支援を可能にする。
【０００３】
この分野で公知の設計技術に「トポロジ最適化」技術と呼ばれるものがある。この技術により、機械部品を有限要素メッシュ（ＦＥＭ）の部分集合で表すことが可能になる。正確には、メッシュの部分集合は、有限要素解析（ＦＥＡ）処理によって算出された最適化トポロジである。論文「Ｗａｑａｓ  Ｓａｌｅｅｍ，Ｈｕ  Ｌｕ，Ｆａｎ  Ｙｕｑｉｎｇ，Ｔｏｐｏｌｏｇｙ  Ｏｐｔｉｍｉｚａｔｉｏｎ．Ｐｒｏｂｌｅｍ  Ｆｏｒｍｕｌａｔｉｏｎ  ａｎｄ  Ｐｒａｇｍａｔｉｃ  Ｏｕｔｃｏｍｅｓ  ｂｙ  ｉｎｔｅｇｒａｔｉｏｎ  ｏｆ  ＴＯＳＣＡ  ａｎｄ  ＣＡＥ  ｔｏｏｌｓ，ＷＣＥＣＳ  ２００８，Ｏｃｔｏｂｅｒ  ２２−２４，２００８，Ｓａｎ  Ｆｒａｎｃｉｓｃｏ，ＵＳＡ」および「Ｈａｕｅｓｓｌｅｒ，Ｐ，Ｅｍｍｒｉｃｈ，Ｄ，Ｍｕｅｌｌｅｒ，Ｏ，Ｉｌｚｈｏｅｆｅｒ，Ｂ，Ｎｏｗｉｃｋｉ，Ｌ，Ａｌｂｅｒｓ，Ａ，Ａｕｔｏｍａｔｅｄ  ｔｏｐｏｌｏｇｙ  ｏｐｔｉｍｉｚａｔｉｏｎ  ｏｆ  ｆｌｅｘｉｂｌｅ  ｃｏｍｐｏｎｅｎｔｓ  ｉｎ  ｈｙｂｒｉｄ  ｆｉｎｉｔｅ  ｅｌｅｍｅｎｔｓ  ｍｕｌｔｉｂｏｄｙ  ｓｙｓｔｅｍｓ  ｕｓｉｎｇ  Ａｄａｍｓ／Ｆｌｅｘ  ａｎｄ  ＭＳＣ．Ｃｏｎｓｔｒｕｃｔ，１６ｔｈ  Ｅｕｒｏｐｅａｎ  ＡＤＡＭＳ  ｕｓｅｒｓ’Ｃｏｎｆｅｒｅｎｃｅ  ２００１」が、この技術を提示している。トポロジ最適化により設計工程の高度な自動化が可能であるが、結果として得られるメッシュ化トポロジは、設計される機械部品の完全に正確かつ包括的な表現ではない。したがって、機械設計者は、従来のコンピュータ支援設計（ＣＡＤ）システムにおいて、さらに、例えば手動で、このメッシュ化トポロジを編集する必要がある。しかし、このような編集は、現在のシステムでは容易ではなく、エルゴノミクス的でもない。
【０００４】
こうした文脈において、機械部品を設計するための改良された解決策が依然として必要とされている。
【発明の概要】
【０００５】
したがって、機械部品を設計するための、コンピュータによって実施される方法が提供される。当該方法は、前記機械部品を表す有限要素メッシュ（ＦＥＭ）の部分集合を提供することと、前記ＦＥＭの前記部分集合に基づいて、前記機械部品の骨格の表現を決定することとを含み、前記骨格は、分岐と分岐接合部を有し、各分岐接合部が分岐を接合する。
【０００６】
本方法は、以下のうちの１つまたは複数を含んでいてもよい。
・骨格の表現は、部分集合に間引き処理を適用した結果と同じトポロジを有する。
・間引き処理を適用した結果は、それぞれが分岐の末端に対応するＦＥＭの要素と、それぞれが分岐接合部に対応するＦＥＭの要素とを含み、それぞれが分岐の末端に対応するＦＥＭの各要素は、それぞれが分岐接合部に対応するＦＥＭの各要素と面を共有する。
・間引き処理は、局所的な非多様体の面ジオメトリの作成を禁止する。
・前記部分集合はトポロジ最適化処理の結果得られ、前記トポロジ最適化処理の境界条件に対応する要素を有しており、前記間引き処理は、前記トポロジ最適化処理の前記境界条件に対応する前記部分集合の要素の除去を禁止する。
・前記間引き処理は、前記部分集合の要素の除去を繰り返すことを含み、繰り返しのそれぞれで除去される前記部分集合の要素は、各繰り返しにおいて除去が禁止されていない、前記部分集合の全ての境界要素である。
・各繰り返しにおいて、前記間引き処理は、前記部分集合の境界要素を、前記部分集合の別の要素と共有する隣接面の数が最も少ないものから最も多いものへと、順に除去する。
・本方法は、さらに、前記骨格の表現に基づいて設計を行うこと含み、かつ／あるいは、
・本方法はさらに、前記ＦＥＭの前記部分集合を提供する前に、トポロジ最適化処理を実行して、ＦＥＭの前記部分集合を決定することを含む。
【０００７】
さらには、前記方法を実行するための命令を含むコンピュータプログラムが提供される。
さらには、前記コンピュータプログラムを記録したコンピュータ読み取り可能な記憶媒体が提供される。
さらには、当該コンピュータプログラムを記録したメモリに接続されたプロセッサと、グラフィカル・ユーザ・インターフェースとを備えるシステムが提供される。
さらには、上記方法によって設計された機械部品を製造するための方法が提供される。
【図面の簡単な説明】
【０００８】
【図１】本方法の一例のフローチャートを示す。
【図２】本システムのグラフィカル・ユーザ・インターフェースの一例を示す。
【図３】本システムの一例を示す。
【図４】本方法を説明する図である。
【図５】本方法を説明する図である。
【図６】本方法を説明する図である。
【図７】本方法を説明する図である。
【図８】本方法を説明する図である。
【図９】本方法を説明する図である。
【図１０】本方法を説明する図である。
【図１１】本方法を説明する図である。
【図１２】本方法を説明する図である。
【図１３】本方法を説明する図である。
【図１４】本方法を説明する図である。
【図１５】本方法を説明する図である。
【図１６】本方法を説明する図である。
【図１７】本方法を説明する図である。
【図１８】本方法を説明する図である。
【図１９】本方法を説明する図である。
【図２０】本方法を説明する図である。
【図２１】本方法を説明する図である。
【図２２】本方法を説明する図である。
【図２３】本方法を説明する図である。
【図２４】本方法を説明する図である。
【図２５】本方法を説明する図である。
【図２６】本方法を説明する図である。
【図２７】本方法を説明する図である。
【図２８】本方法を説明する図である。
【図２９】本方法を説明する図である。
【図３０】本方法を説明する図である。
【図３１】本方法を説明する図である。
【図３２】本方法を説明する図である。
【図３３】本方法を説明する図である。
【図３４】本方法を説明する図である。
【図３５】本方法を説明する図である。
【図３６】本方法を説明する図である。
【図３７】本方法を説明する図である。
【図３８】本方法を説明する図である。
【図３９】本方法を説明する図である。
【図４０】本方法を説明する図である。
【図４１】本方法を説明する図である。
【図４２】本方法を説明する図である。
【図４３】本方法を説明する図である。
【図４４】本方法を説明する図である。
【図４５】本方法を説明する図である。
【図４６】本方法を説明する図である。
【図４７】本方法を説明する図である。
【図４８】本方法を説明する図である。
【図４９】本方法を説明する図である。
【図５０】本方法を説明する図である。
【図５１】本方法を説明する図である。
【図５２】本方法を説明する図である。
【図５３】本方法を説明する図である。
【図５４】本方法を説明する図である。
【図５５】本方法を説明する図である。
【図５６】本方法を説明する図である。
【図５７】本方法を説明する図である。
【図５８】本方法を説明する図である。
【図５９】本方法を説明する図である。
【図６０】本方法を説明する図である。
【図６１】本方法を説明する図である。
【図６２】本方法を説明する図である。
【図６３】本方法を説明する図である。
【図６４】本方法を説明する図である。
【図６５】本方法を説明する図である。
【図６６】本方法を説明する図である。
【図６７】本方法を説明する図である。
【図６８】本方法を説明する図である。
【発明を実施するための形態】
【０００９】
図１のフローチャートを参照して、機械部品を設計するための、コンピュータにより実施される方法を提案する。本方法は、有限要素メッシュ（ＦＥＭ）の部分集合を提供すること（Ｓ２０）を含む。ＦＥＭの部分集合は、機械部品を表す。本方法はまた、ＦＥＭの部分集合に基づいて、機械部品の骨格の表現を決定すること（Ｓ３０）を含む。「骨格」の定義上、骨格は、分岐（すなわち、材料の一次元拡張部分）と分岐接合部（すなわち、材料における分岐が接合する箇所）を有し、分岐接合部は、それぞれ、分岐を接合する。このような方法により、機械部品の設計が改善する。
【００１０】
特に本方法は、Ｓ２０において、機械部品のメッシュ表現が提供され、また本方法は、Ｓ３０において、機械部品に関連する別の表現、すなわち機械部品の骨格の表現を決定する。したがって、本方法は、Ｓ２０で提供された機械部品を表すデータを、Ｓ３０で決定されたデータで充実させることができ、それにより、ユーザに提供される新しい設計機能を伴う、機械部品の新しいタイプの表現を追加する。さらに、Ｓ３０で決定されるデータは、機械部品の骨格の表現である。このように、Ｓ２０においてメッシュの部分集合を提供するときに機械部品が最初に非常に粗いレベルでのみ表される場合、本方法はＳ３０においてより高いレベルの表現、すなわち機械部品の骨格の表現を決定する。これにより、新しい設計能力、および比較的高いレベルの設計作業が可能になる。実際、本方法は、Ｓ３０で決定されたデータのおかげで、機械部品の骨格レベルでの設計を可能にする。特に骨格レベルは、機械設計の分野でとりわけ関連する設計レベルである。それは、多くの状況において、機械部品は、機械設計者により、骨格という観点から見られるからである。骨格レベルの設計を可能にすることは、このように、特に機械設計においてエルゴノミクス的である。
【００１１】
本方法は、コンピュータにより実施される。すなわち、本方法のステップ（あるいは略全てのステップ）が少なくとも１つのコンピュータ、または類似の任意のシステムによって実行される。よって本方法のステップは、コンピュータにより、完全に自動的に、あるいは半自動的に実行される可能性がある。例えば、後述するステップＳ１０およびＳ４０は、ユーザとの対話操作を介して実行されてもよく、ステップＳ２０はユーザによって（例えばユーザによってのみ）起動されてもよく、ステップＳ３０はＳ２０が起動されると、完全に自動的に実行されてもよい。求められるユーザとコンピュータの対話レベルは、想定される自動性のレベルに応じたものであって、ユーザの要望を実装する必要性との間でバランスをとるものとしてもよい。例えば、このレベルは、ユーザが設定し、かつ／あるいは、予め定義されていてもよい。
【００１２】
本方法のコンピュータによる実施の典型的な例は、この目的に適したシステムを用いて本方法を実行することである。当該システムは、本方法を実行するための命令を含むコンピュータプログラムを記録したメモリに接続されたプロセッサ、および、グラフィカル・ユーザ・インターフェイス（ＧＵＩ）を備えていてもよい。また、メモリはデータベースを記憶していてもよい。メモリは、そのような記憶に適した任意のハードウェアであり、場合により、物理的に区別可能ないくつかの部分（例えば、プログラム用に１つ、場合によりデータベース用に１つ）を含む。
【００１３】
本方法は、一般に、部分集合を有するＦＥＭを含むモデル化オブジェクトと骨格の表現とを操作する。モデル化オブジェクトは、例えばデータベースに格納されたデータによって定義される任意のオブジェクトである。さらには、「モデル化オブジェクト」という表現は、データそのものも指す。システムの種類に応じて、異なる種類のデータによってモデル化オブジェクトが定義されてもよい。実際、システムは、ＣＡＤシステム、ＣＡＥシステム、ＣＡＭシステム、ＰＤＭシステム、および／またはＰＬＭシステムのうちの任意の組み合わせであってもよい。それら異なるシステムにおいて、モデル化オブジェクトは、対応するデータによって定義される。したがって、ＣＡＤオブジェクト、ＰＬＭオブジェクト、ＰＤＭオブジェクト、ＣＡＥオブジェクト、ＣＡＭオブジェクト、ＣＡＤデータ、ＰＬＭデータ、ＰＤＭデータ、ＣＡＭデータ、ＣＡＥデータについて言及することがある。しかしながら、モデル化オブジェクトは、これらのシステムの任意の組み合わせに対応するデータによって定義されてもよいため、これらのシステムは、互いに排他的なものではない。したがって、以下に示すこのようなシステムの定義から明らかなように、システムは、ＣＡＤ兼ＰＬＭシステムであってもよい。
【００１４】
ＣＡＤシステムは、少なくとも、ＣＡＴＩＡのようなモデル化オブジェクトのグラフィック表現に基づくモデル化オブジェクトの設計に適した任意のシステムをも意味する。この場合、モデル化オブジェクトを定義するデータは、モデル化オブジェクトを表現可能にするデータを含む。ＣＡＤシステムは、例えば、辺や線を用い、また、場合により面や曲面を用いて、ＣＡＤモデル化オブジェクトの表現を提供してもよい。線、辺、あるいは面は、例えば、非一様有理Ｂスプライン（ＮＵＲＢＳ）など、様々な様式で表現されてもよい。具体的には、ＣＡＤファイルは仕様を含み、その仕様に基づきジオメトリが生成可能であり、よって表現が生成可能となる。モデル化オブジェクトの仕様は１つまたは複数のＣＡＤファイルに格納されていてもよい。ＣＡＤシステムでモデル化オブジェクトを表現するファイルの典型的なサイズは、一部分あたり１メガバイトの範囲である。また、モデル化オブジェクトは、典型的には、数千の部分の集合体であってもよい。
【００１５】
ＣＡＤの文脈において、モデル化オブジェクトは、典型的には、３Ｄモデル化オブジェクト、例えば、一つの部品や部品の集合体などの製品、あるいは製品の集合体を表現するものであってもよい。「３Ｄモデル化オブジェクト」は、３Ｄ表現が可能なデータによってモデル化される任意のオブジェクトを意味する。３Ｄ表現は、その部品をすべての角度から見ることを可能にする。たとえば、３Ｄで表現された３Ｄモデル化オブジェクトは、その軸のうちの任意の軸、あるいは、その表現が表示された画面中の任意の軸を中心に、処理して回転させることが可能である。これは、特に、３Ｄモデル化されていない２Ｄアイコンについては除外される。３Ｄ表現の表示は、設計を容易にする（すなわち、設計者が作業を達成するスピードを統計的に速める）。製品の設計は製造工程の一部であるから、これによって当該産業における製造工程が迅速化する。
【００１６】
３Ｄモデル化オブジェクトは、ＣＡＤソフトウェア・ソリューションやＣＡＤシステム等を用いた仮想的デザインの完了後に実世界において製造される製品、すなわち（例えば機械）部品や、部品の集合体（あるいは同様に部品の集合体。なぜなら部品の集合体は本方法の観点では一つの部品としてみることができ、また、本方法は集合体における各部品に独立して適用することができるからである）など、より一般的には任意の剛体の集合体（例えば移動機構）などの製品のジオメトリを表現してもよい。ＣＡＤソフトウェア・ソリューションは、航空宇宙、建築、建設、消費財、ハイテク機器、産業機器、輸送、海洋、および／または海洋石油／ガス生産、または交通を含む、限定されることのない様々な産業分野において製品の設計を可能にする。本方法により設計される機械部品は、このように、地上車両の部品（例えば、自動車および軽トラック機器、レーシングカー、オートバイ、トラックおよびモーター機器、トラック、バス、電車を含む）、航空車両の部品（例えば、航空機体機器、航空宇宙機器、推進機器、防衛製品、航空路線機器、宇宙機器を含む）、海軍車両の部品（例えば、海軍用機器、商業用船舶、オフショア機器、ヨットおよび作業船、船舶用機器を含む）、一般的な機械部品（例えば、工業用製造機械、大型移動機械または機器、設置機器、産業機器製品、加工金属製品、タイヤ製造製品を含む）、または電気機械部品（例えば、家電、セキュリティおよび／または制御および／または計装製品、コンピューティングおよび通信機器、半導体、医療装置および設備を含む）などのように、任意の機械部品であり得る工業製品を表してもよい。「機械部品」という表現は、消費者製品（例えば、家具、家庭用および庭用製品、レジャー用品、ファッション用品、耐久消費財小売用品、織物類小売用品を含む）、包装（例えば、食品および飲料およびたばこ、美容およびパーソナルケア、家庭用製品包装を含む）を示してもよい（あるいはまた、示さなくてもよい）。
【００１７】
ＣＡＤシステムは、履歴ベースのものであってもよい。この場合、モデル化オブジェクトは、さらに、ジオメトリ的特徴の履歴を含むデータによって定義される。モデル化オブジェクトは、標準的なモデリング機能（例えば押し出し、回転、切断、および／または丸め）および／または標準的な面モデリング機能（例えば、スイープ、ブレンド、ロフト、塗りつぶし、変形、および／または平滑化）を用いて、人間（例えば設計者／ユーザ）によって設計されてもよい。このようなモデル化機能をサポートするＣＡＤシステムの多くは、履歴ベースのシステムである。これは、設計機能の作成履歴が、典型的には、入力および出力リンクを介して上記ジオメトリ機能を互いに連結する非循環データフローで保存されることを意味する。履歴に基づくモデル化のパラダイムは、８０年代初頭からよく知られている。モデル化オブジェクトは、２つの永続的なデータ表現によって表すことができる。すなわち、履歴とＢ−ｒｅｐ（すなわち境界表現）である。Ｂ−ｒｅｐは、履歴に定義された演算の結果である。モデル化オブジェクトが表現されるときにコンピュータのスクリーン上に表示される部品の形状は、Ｂ−ｒｅｐ（例えばそのテッセレーション）である。その部品の履歴とは、設計意図である。基本的に、履歴とは、モデル化オブジェクトに対して行われた操作に関する情報を収集したものである。複雑な部品の表示を容易にするため、Ｂ−ｒｅｐを履歴とともに保存してもよい。設計意図に従って部品の設計変更ができるように、履歴をＢ−ｒｅｐとともに保存してもよい。
【００１８】
ＰＬＭシステムは、物理的な、製造された製品（または製造される予定の製品）を表すモデル化オブジェクトの管理に適した任意のシステムをも指す。ＰＬＭシステムでは、モデル化オブジェクトは、このように、物理的な物体の製造に適したデータによって定義される。これらは、典型的には、寸法の値および／または公差の値であってもよい。物体を正しく製造するために、実際、このような値を用いるのが望ましい。
【００１９】
ＣＡＭソリューションとは、製品の製造データを管理するのに適した、ハードウェアのソフトウェアである、あらゆるソリューションをも指す。製造データは、一般に、製造する製品、製造工程、および必要なリソースに関するデータを含む。ＣＡＭソリューションは、製品の製造工程全体を計画し最適化するのに用いられる。例えば、実現可能性、製造工程の期間、または製造工程における特定のステップで使用され得るリソース、例えば特定のロボットの数に関する情報をＣＡＭユーザに提供することができる。これにより、管理や必要な投資についての決定を可能にする。ＣＡＭは、ＣＡＤ工程、および、場合によりＣＡＥ工程に続く工程である。このようなＣＡＭソリューションは、ダッソー・システムズにより、ＤＥＬＭＩＡ（登録商標）として提供されている。
【００２０】
ＣＡＥソリューションとは、モデル化オブジェクトの物理的挙動の分析に適した、ハードウェアのソフトウェアである、あらゆるソリューションをも指す。よく知られており広く用いられているＣＡＥ技術は有限要素法（Ｆｉｎｉｔｅ  Ｅｌｅｍｅｎｔ  Ｍｅｔｈｏｄ：ＦＥＭ）であり、これは、典型的には、モデル化オブジェクトを、物理的挙動を方程式によって計算しシミュレーションできる要素に分割することを含む。このようなＣＡＥソリューションは、ダッソー・システムズにより、ＳＩＭＵＬＩＡ（登録商標）として提供されている。成長するＣＡＥ技術のもう１つは、ＣＡＤジオメトリデータを使用せずに異なる物理分野の複数の要素で構成される複雑なシステムのモデリングと解析を行うことを含む。ＣＡＥソリューションはシミュレーションを可能にし、それにより、製造する製品の最適化、改善および検証を可能にする。このようなＣＡＥソリューションは、ダッソー・システムズにより、ＤＹＭＯＬＡ（登録商標）として提供されている。
【００２１】
ＰＤＭはＰｒｏｄｕｃｔ  Ｄａｔａ  Ｍａｎａｇｅｍｅｎｔ（生産データ管理）の略である。ＰＤＭソリューションとは、特定の製品に関するすべての種類のデータを管理するのに適した、ハードウェアのソフトウェアである、あらゆるソリューションを指す。ＰＤＭソリューションは、製品のライフサイクルにかかわるすべての関係者によって使用されてもよい。これには、主として技術者のほか、プロジェクトマネージャー、財務担当者、営業担当者、およびバイヤーも含まれる。ＰＤＭソリューションは、一般に、製品指向のデータベースに基づく。これにより、関係者が製品に関する一貫したデータを共有することが可能になり、これにより、関係者が異なるデータを用いるのを防止する。このようなＰＤＭソリューションは、ダッソー・システムズにより、ＥＮＯＶＩＡ（登録商標）として提供されている。
【００２２】
図２は、本方法を実施するために用い得るシステムのＧＵＩの一例を示しており、ここでのシステムはＣＡＤシステムである。
【００２３】
ＧＵＩ２１００は、標準的なメニューバー２１１０，２１２０、ならびに底部および側面のツールバー２１４０，２１５０を有する典型的なＣＡＤのようなインターフェースであってもよい。このようなメニューバーおよびツールバーは、ユーザが選択可能なアイコンのセットを含み、各アイコンは、当技術分野で知られているように、１つまたは複数の操作または機能に関連付けられている。これらのアイコンのいくつかは、ＧＵＩ２１００に表示された３Ｄモデル化オブジェクト２０００の編集および／または作業に適合したソフトウェアツールに関連付けられており、これは、図１の方法の結果（例えばＳ３０またはＳ４０の実行後）であってもよい。ソフトウェアツールはワークベンチに分類することができる。各ワークベンチは、ソフトウェアツールのサブセットを含む。特に、ワークベンチの１つは、モデル化製品２０００のジオメトリ的特徴を編集するのに適した編集ワークベンチである。操作中、設計者は、例えば、オブジェクト２０００の一部を予め選択し、次いで、適切なアイコンを選択することによって、操作を開始する（例えば、寸法、色などを変更する）か、ジオメトリ的制約を編集することができる。例えば、典型的なＣＡＤ操作は、スクリーン上に表示された３Ｄモデル化オブジェクトのパンチングまたは折り畳みのモデリングである。ＧＵＩは、例えば、表示された製品２０００に関連するデータ２５００を表示してもよい。図２の例では、「特徴ツリー」として表示されたデータ２５００およびそれらの３Ｄ表現２０００は、ブレーキキャリパおよびディスクを含むブレーキ部品に関するものである。ＧＵＩは、編集された製品の動作のシミュレーションを起動するため、または表示された製品２０００の様々な属性を描画するために、例えばオブジェクトの３Ｄ定位を容易にするための様々なタイプのグラフィックツール２１３０，２０７０，２０８０をさらに示してもよい。カーソル２０６０は、ユーザがグラフィックツールを用いて対話操作ができるように、触覚デバイスによって制御されてもよい。
【００２４】
図３は、本システムの一例を示すものであって、当該システムは、クライアントコンピュータシステム、例えばユーザのワークステーションである。
【００２５】
本例のクライアントコンピュータは、内部通信バス１０００に接続された中央演算処理装置（ＣＰＵ）１０１０、および同じくバスに接続されたランダムアクセスメモリ（ＲＡＭ）１０７０とを備える。クライアントコンピュータは、さらに、バスに接続されたビデオランダムアクセスメモリ１１００と関連付けられたグラフィックス処理装置（ＧＰＵ）１１１０を備える。ビデオＲＡＭ１１００は、当該技術分野において、フレームバッファとしても知られる。大容量記憶装置コントローラ１０２０は、ハードドライブ１０３０などの大容量記憶装置へのアクセスを管理する。コンピュータプログラムの命令及びデータを具体的に実現するのに適した大容量メモリ装置は、例として、ＥＰＲＯＭ、ＥＥＰＲＯＭ及びフラッシュメモリ装置のような半導体メモリ装置、内蔵ハードディスクやリムーバブルディスクなどの磁気ディスク、光磁気ディスク、およびＣＤ−ＲＯＭディスク１０４０を含む、全ての形式の不揮発性メモリを含む。前述のいずれも、特別に設計されたＡＳＩＣ（特定用途向け集積回路）によって補完されてもよいし、組み入れられてもよい。ネットワークアダプタ１０５０は、ネットワーク１０６０へのアクセスを管理する。クライアントコンピュータはまた、カーソル制御装置、キーボードなどの触覚装置１０９０を含んでいてもよい。カーソル制御装置は、ユーザがディスプレイ１０８０上の任意の所望の位置にカーソルを選択的に位置させることを可能にするために、クライアントコンピュータ内で使用される。さらに、カーソル制御デバイスは、ユーザが様々なコマンドを選択し、制御信号を入力することを可能にする。カーソル制御装置は、システムに制御信号を入力するための多数の信号生成装置を含む。典型的には、カーソル制御装置はマウスであってもよく、マウスのボタンは信号を生成するために使用される。あるいは、または追加的に、クライアントコンピュータシステムは、感知パッドおよび／または感知スクリーンを備えてもよい。
【００２６】
コンピュータプログラムは、コンピュータによって実行可能な命令を含んでいてもよく、命令は、上記システムに方法を実行させるための手段を含む。プログラムは、システムのメモリを含む任意のデータ記憶媒体に記録可能であってもよい。プログラムは、例えば、デジタル電子回路、またはコンピュータハードウェア、ファームウェア、ソフトウェア、またはそれらの組み合わせで実装されてもよい。プログラムは、例えばプログラマブルプロセッサによる実行のための機械読み取り可能な記憶装置に具体的に実現された製品のような装置として実装されてもよい。方法ステップは、プログラム可能なプロセッサが命令のプログラムを実行し、入力データを操作して出力を生成することによって方法の機能を実行することによって実行されてもよい。したがって、プロセッサは、データ記憶システム、少なくとも１つの入力デバイス、および少なくとも１つの出力デバイスからデータおよび命令を受信し、また、それらにデータおよび命令を送信するようにプログラム可能であってもよく、またそのように接続されていてもよい。アプリケーションプログラムは、高水準の手続き型またはオブジェクト指向のプログラミング言語で、または必要に応じてアセンブリ言語または機械語で実装されていてもよい。いずれの場合も、言語はコンパイラ型言語またはインタープリタ型言語であってもよい。プログラムは、フルインストールプログラムまたは更新プログラムであってもよい。いずれの場合も、プログラムをシステムに適用すると、本方法を実行するための指示が得られる。
【００２７】
機械部品を表すモデル化オブジェクトのような「モデル化オブジェクトの設計」（「機械部品の設計」とも呼ぶ）とは、モデル化オブジェクトを作り上げる工程の少なくとも一部である任意の行為あるいは一連の行為を指す。
【００２８】
本方法は、本方法を実行した後に、モデル化オブジェクトにジオメトリ的に対応する物理的製品を生産する工程を含み得る製造工程に含まれていてもよい。いずれの場合も、本方法によって設計されたモデル化オブジェクトは、機械部品を表し、したがって製造オブジェクトを表す。したがって、モデル化オブジェクトは、モデル化立体（すなわち、立体を表すモデル化オブジェクト）であってもよい。製造オブジェクトは、部品などの製品であってもよいし、または部品の集合体であってもよい。本方法は、モデル化オブジェクトの設計を改善するので、本方法はまた、製品の製造を改善し、したがって、製造工程の生産性を高める。
【００２９】
ここで、図１の方法について詳述する。
【００３０】
Ｓ２０で提供されるデータは、機械部品を表すＦＥＭの部分集合である。図１の例では、このデータ構造は、機械部品を表すＦＥＭの上記部分集合を決定するトポロジ最適化処理を実行することを本質とする、先のステップＳ１０の結果として得られる（これに続いて、Ｓ２０および／またはＳ３０の前に、例えば、傷、ひび割れ、および／または小さな空洞（例えば１つのＦＥＭ要素程度のサイズのもの。例えば５要素未満。）を除去するためのクリーニング処理が実行されてもよい）。同じタイプのデータ構造が他の方法で得られてもよく、かつ／あるいは、トポロジ最適化が別の時間および／またはシステムで（例えば、別の人によって）実行されてもよく、また、Ｓ２０において機械部品を表す部分集合を有するＦＥＭが提供される限り、残りのステップ（Ｓ３０を含む）が実行されてもよい。
【００３１】
このように、図１の方法は、「トポロジ最適化」技術を用いて得られた機械部品を後処理することを扱う。ユーザが結果を編集できるようにすることにメリットがある理由は、いくつか存在する。第一に、トポロジ最適化処理（例えば、流体力学、美学および／または製造を含む）によってすべての制約が考慮されるわけではなく、部品は、再加工によって改善され得る。より一般的には、既存のトポロジ最適化処理は、何らかの理由で改善可能な結果を提供する。熟練したユーザは、その構造設計スキルのおかげで、例えば分岐の追加または除去、分岐のセクションの変更、および／またはスティフナーによる分岐の置き換えを含む操作によって、結果として得られた部品を、より軽量でより耐性のある部品に再加工することができる。実際、「最適化された」部品は、熟練したユーザの出発点またはインスピレーションの基準であり得る。
【００３２】
トポロジ最適化処理は、ＦＥＭの部分集合を、部分集合が機械部品を表すように決定するための、広く知られた、コンピュータにより実施する方法である。トポロジの最適化は、機械部品の元のトポロジを自動的に作成する方法である。トポロジ最適化処理は、最初にＦＥＭを提供することを含んでいてもよい。ＦＥＭは、機械部品が占有することを意図した空間の区画を表すデータ構造である。言い換えると、ＦＥＭは、例えば接続された、かつ／あるいは、凸状の空間を表し、機械部品は、そのような空間に局在化され、したがって、そのような空間の部分集合によって定義可能な、立体である。ＦＥＭは、メッシュ構造（例えば、四面体状、角錐状、または立方体状のメッシュ構造）であり、例えば２Ｄまたは３Ｄであり、ＦＥＭの要素（すなわちメッシュの単位、例えば、基本となる四面体、角錐、または立方体）は、それぞれ、空間のセルを表す。
【００３３】
トポロジ最適化処理は、その後、境界条件をＦＥＭに設定することを含んでいてもよい。境界条件の設定は、ＦＥＭの対応する要素に対して、機械的制約を定義することを含んでもよく、またはそのことにより構成されていてもよい。その結果、それぞれの境界条件に対応するＦＥＭの要素は、トポロジの最適化によって生じる部分集合に含まれる。すべての境界条件の集合は、機械部品に対する所定の機械的制約（言い換えると、機械部品が受ける機械的制約）の適用を表す。
【００３４】
トポロジ最適化処理は、その後、機械部品を表すジオメトリを形成するＦＥＭの部分集合（例えば、厳密に言えば、すなわち、厳密にＦＥＭよりも小さい）を決定することを含んでいてもよい。この決定では、境界条件および希薄さに対する抵抗に報酬を与えることができる。言い換えると、決定は、境界条件に対して低い抵抗を示す部分集合に含まれるＦＥＭの要素の配置にペナルティを科し、また部分集合に含まれるＦＥＭの要素の数が多いことにペナルティを科す最適化プログラムを介して実行されてもよい。そのような決定は、境界条件に関するＦＥＭの各要素のスカラ寄与度を自動的に計算し、次にフィルタリングを実行することによって（例えば、所定の固定または可変の閾値を用いて、または閾値を設定／選択するユーザとのユーザ対話操作を介して）実行されてもよい。
【００３５】
例では、入力データは、強度、荷重、制約境界条件が定義された「設計空間」と名付けられた均質材料（材料密度ρがあらゆる場所で１に等しいことを意味する）からなる厚いブロックを表してもよい。設計空間の形状および境界条件は、ユーザが定義してもよい。そして、有限要素四面体メッシュを提供するために、設計空間をメッシュ化してもよい。これは、任意の最先端のメッシュ化アルゴリズムで実行することができる。次に、反復処理を以下のように実行することができる。第１のステップでは、これらの入力データを用いて有限要素解析を実行する。古典的には、構造力学の偏微分方程式を解く。一般に、制約領域の近くに高い応力が集中する。従って、設計空間内には、ほとんど応力がかからない拡張領域が存在する。これは、全体的な動作を保ちつつ、「応力なし」領域の材料密度を減少させるトポロジ最適化を行う機会である。材料密度が変更されるため、新たな有限要素解析を実行して新たな応力構成を算出する。これは停止テストに達するまで繰り返し実行される。停止テストは、次の条件のいずれか、または組み合わせが満たされるとき実施される。密度場を最適化することができず、繰り返しが所定回数に達している、かつ／あるいは所定の重量比に達している（例えば、得られた質量が、２０％または３０％を超える割合だけ軽い、例えば４５％程度軽い）。
【００３６】
例では、メッシュの各四面体は、間隔［０，１］内の実数、すなわち最終密度場に関連付けることができる。値０は、四面体内に材料がないことを意味してもよい。値１は、四面体が初期均質材料で満たされていることを意味してもよい。他の密度値は、四面体において必要な材料が「より少ない」ことを意味してもよい。可変密度材料は製造の観点からは非現実的であるため、密度が小さい四面体は空の四面体として解釈されてもよい。結果として、四面体は、数値閾値０＜ρ0＜１に従って初期メッシュから除去することができる。密度値がρ０より小さいことを特徴とする四面体は、メッシュから除去することができる。この動作は、一般に、隆起、間隙、および分岐を生成し、したがって、初期設計空間のトポロジに大きな影響を及ぼす。これにより、いわゆる最適化トポロジが得られる。
【００３７】
図４〜図６は、上記のようなトポロジ最適化を２Ｄに適用した例を示す：すなわち、表現された制約４４を有する設計空間４２と、メッシュ化設計空間５２と、部品の機能に実際に寄与する材料の量（メッシュの黒い要素６２）である。境界条件４４は自明である。なお、現実の場合、解決策は、熟練した機械設計者の力の及ばないところにある。
【００３８】
図１の方法によってＳ１０で実行されるトポロジ処理は、上述のように、例えば、先に述べた論文のいずれかに記載されている：「Ｗａｑａｓ  Ｓａｌｅｅｍ，Ｈｕ  Ｌｕ，Ｆａｎ  Ｙｕｑｉｎｇ，Ｔｏｐｏｌｏｇｙ  Ｏｐｔｉｍｉｚａｔｉｏｎ．Ｐｒｏｂｌｅｍ  Ｆｏｒｍｕｌａｔｉｏｎ  ａｎｄ  Ｐｒａｇｍａｔｉｃ  Ｏｕｔｃｏｍｅｓ  ｂｙ  ｉｎｔｅｇｒａｔｉｏｎ  ｏｆ  ＴＯＳＣＡ  ａｎｄ  ＣＡＥ  ｔｏｏｌｓ，ＷＣＥＣＳ  ２００８，Ｏｃｔｏｂｅｒ  ２２−２４，２００８，Ｓａｎ  Ｆｒａｎｃｉｓｃｏ，ＵＳＡ」および「Ｈａｕｅｓｓｌｅｒ，Ｐ，Ｅｍｍｒｉｃｈ，Ｄ，Ｍｕｅｌｌｅｒ，Ｏ，Ｉｌｚｈｏｅｆｅｒ，Ｂ，Ｎｏｗｉｃｋｉ，Ｌ，Ａｌｂｅｒｓ，Ａ，Ａｕｔｏｍａｔｅｄ  ｔｏｐｏｌｏｇｙ  ｏｐｔｉｍｉｚａｔｉｏｎ  ｏｆ  ｆｌｅｘｉｂｌｅ  ｃｏｍｐｏｎｅｎｔｓ  ｉｎ  ｈｙｂｒｉｄ  ｆｉｎｉｔｅ  ｅｌｅｍｅｎｔｓ  ｍｕｌｔｉｂｏｄｙ  ｓｙｓｔｅｍｓ  ｕｓｉｎｇ  Ａｄａｍｓ／Ｆｌｅｘ  ａｎｄ  ＭＳＣ．Ｃｏｎｓｔｒｕｃｔ，１６ｔｈ  Ｅｕｒｏｐｅａｎ  ＡＤＡＭＳ  ｕｓｅｒｓ’Ｃｏｎｆｅｒｅｎｃｅ  ２００１」。
【００３９】
ここで、前述のように、トポロジ最適化の結果得られる四面体メッシュは、少なくとも、骨格の解像度で簡単に編集することはできない。再設計と製造準備のためには編集する必要があるため、これは課題である。したがって、図１の方法は、メッシュ化トポロジの編集可能なフォーマットを提供することによってエルゴノミクスを増加させる。これは、図１の方法が、ＦＥＭの部分集合に基づいて、機械部品の骨格の表現を（例えば自動的に）決定すること（Ｓ３０）を含むためである。ユーザは、望むならば（図１の例ではＳ４０）、骨格の表現に基づく設計操作を実行することができる。このような設計操作は、骨格を編集すること、すなわち、機械部品を表す（例えば、３Ｄ）モデル化オブジェクトを骨格レベルで編集することを含んでいてもよい。これは、ユーザが、例えば、分岐の追加または除去、分岐のセクション、位置、長さ、および／または形状の変更、および／または分岐を補強材で置き換えることを含む操作により、骨格のパラメータに直接作用することができることを意味する。
【００４０】
骨格は実際には、定義上、分岐接合部に接続された分岐の配列であり、各分岐接合部はそれぞれの分岐につながっている。分岐は、一次元状に広がる材料の配列である。骨格を表すデータ構造は、それぞれが分岐を表す複数のデータを含む限り、任意の形式であり得る。分岐を表すこれらのデータは、例えば、後述する例のように、セクション分布に関連する案内（例えば、スプライン）曲線をそれぞれ有する、掃引された立体であってもよい。その他の任意の種類の（例えばジオメトリの）データが分岐を表してもよい。分岐を表すこれらのデータは、それぞれ、データ構造内で明確に定義され、したがって個別にアクセス可能であり、ユーザは、Ｓ４０で、分岐を表すこれらのデータの任意の組合せを入力とする設計操作を実行することができる。これにより、ユーザは、例えば、分岐の追加、および／または除去、分岐の位置、長さ、形状、および／またはセクションの変更を含む、分岐パラメータの変更を行うことができる。
【００４１】
データ構造は、分岐の接合点を表すデータ、および／または分岐間の配置に関するデータ、例えば、どの分岐が接合されるか、および／またはどの分岐接合部がどの分岐に接合するかに関するデータを含んでいてもよい。このような場合、Ｓ４０における設計が、より精密になり得る。このような骨格レベルでの編集は、例えば、ユーザが、機械部品のグラフィック表示に対して対話操作を行って分岐全体を選択し、次に選択した分岐を操作して分岐の編集を一括して行うように（例えば、一度のユーザ操作で、例えば、ドラッグ・アンド・ドロップを含むカーソル制御動作のようなグラフィカルなユーザ操作で）、グラフィカルに行うことができる。
【００４２】
例えば、本方法は、Ｓ３０の後に、掃引された立体を含む特徴の履歴（例えば、各掃引立体は、案内曲線と関連付けられており、データは、案内曲線に沿って、各掃引立体のセクションの分布を表す）、および、フィレットなど、可能性のあるその他の特徴や、その他の任意の特徴を得るものとしてもよい。このような場合、本方法は、部分集合における１００万個を超える数の要素を出力する可能性のあるトポロジ最適化の結果とは対照的に、例えば、大きなモデルの場合で、１００個未満の特徴間の履歴のリストまたは表現を、機械設計者に提供することができる。
【００４３】
このように、本方法は、個々の分岐（および場合によっては個々の分岐接合部）を表すデータを導き、そのようなデータは、その部品を形成する局所的なジオメトリの単なる集合（例えば初期のＦＥＭの部分集合）よりも高いレベル（または同等に、より次元が低い表現）のデータである。また、この表現は、各分岐接合部が少なくとも３つの分岐に接合するようなものであってもよいが、代わりに少なくとも１つの分岐接合部が２つの分岐にのみ接合するような表現であってもよい（設計意図に依存する）。したがって、トポロジの各分岐は単一の特徴（例えば、掃引立体）であるため、本方法は、編集に適切な意味レベルを自動的に提供することができる。これは、輪郭形状、および／または、スプライン曲線形状を変更することによって編集することができる。先行技術と比較して、より容易かつ迅速に編集を行うことができ、再設計フェーズと製造準備が削減される。
【００４４】
本方法がなければ、トポロジ最適化の出力を再加工するための解決策は、ユーザに、市販のＣＡＤシステムを使用して、立体またはサーフェスを再設計させることを含むかもしれない。この再設計は一から実行され、メッシュ化トポロジはインスピレーションを与える背景形状である。しかしながら、メッシュ化トポロジが非常に複雑である可能性があるため、一から立体を再設計するのは面倒で時間がかかる。また、この場合、結果を分岐レベルで編集できるとは限らない。本本法は、このような課題に関してエルゴノミクスを改善する。
【００４５】
本方法は、市販のＣＡＤシステムを用いて立体を構築するための入力として用いることができる骨格を提供する。たとえば、分岐を掃引特徴の案内曲線として使用できる。
【００４６】
Ｓ３０で決定した骨格の表現は、部分集合に間引き処理を適用した結果と同じトポロジを有していてもよい。これは、決定Ｓ３０が、部分集合を入力とする間引き処理を行い、その後、場合によってはトポロジを維持する他の操作（例えば、後述の例では掃引ボリュームの算出）、あるいは結果として得られるトポロジの観点から等価なスキームを実行することを本質とすることを意味する。先行技術の間引き処理は、論文「Ｌｉｕ，Ｌ，３Ｄ  ｔｈｉｎｎｉｎｇ  ｏｎ  ｃｅｌｌ  ｃｏｍｐｌｅｘｅｓ  ｆｏｒ  ｃｏｍｐｕｔｉｎｇ  ｃｕｒｖｅ  ａｎｄ  ｓｕｒｆａｃｅ  ｓｋｅｌｅｔｏｎｓ，Ｍａｓｔｅｒ  ｏｆ  Ｓｃｉｅｎｃｅ，Ｓａｉｎｔ  Ｌｏｕｉｓ，Ｍｉｓｓｏｕｒｉ，２００９」および「Ｓｔａｎｇｌ，Ｌ，Ｗａｒｔｚａｃｋ，Ｓ，Ｆｅａｔｕｒｅ  ｂａｓｅｄ  ｉｎｔｅｒｐｒｅｔａｔｉｏｎ  ａｎｄ  ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ  ｏｆ  ｓｔｒｕｃｔｕｒａｌ  ｔｏｐｏｌｏｇｙ  ｏｐｔｉｍｉｚａｔｉｏｎ  ｒｅｓｕｌｔｓ，ＩＣＥＤ１５，２７−３０  Ｊｕｌｙ  ２０１５，Ｐｏｌｉｔｅｃｎｉｃｏ  ｄｉ  Ｍｉｌａｎｏ，Ｉｔａｌｙ」に開示されている。本方法の場合、間引き処理は、部分集合のサイズを、例えば部分集合の要素を繰り返し除去する（すなわち、部分集合の１以上の要素の除去を繰り返す）ことによって、例えば可能な限り（すなわち要素がある限り）、繰り返し縮小し、一方、トポロジが保存されないこと（しかし、例えば、そのように保存されないことを厳密には禁じていない）にペナルティを科し、例えば、部分集合によって定義される形状の内部のトポロジが保存されないことを禁止する処理である（「内部」という概念は後で定義する）。後述の例で説明するような間引き処理を実行することは、特に効率的に決定Ｓ３０を実行する方法である。
【００４７】
間引き処理を適用した結果は、Ｓ２０で提供された部分集合の部分集合に含まれ、よって、それ自体ＦＥＭの部分集合でもある。間引き処理を適用した結果の要素は、それぞれ、骨格の分岐、および／または、分岐接合部に対応する（すなわち、表す、または属する）。骨格の分岐のそれぞれに対応する、間引き処理を適用した結果の要素のうち、要素は、分岐のそれぞれの末端（すなわち端部）に対応し、例えば、四面体の（１次元配列の場合には、各末端にちょうど１つの要素が対応する（すなわち分岐の「最後」の要素）。例では、結果の各要素は、各分岐または各分岐接合部に対応する。分岐の末端に対応する各要素は、分岐点に対応するＦＥＭの各要素、具体的には、分岐の末端が到達する分岐接合部とぶつかる（すなわち接続する）。
【００４８】
例においては、結果には、分岐接合部に対応する要素以外に、他の要素と厳密に２つより多くの面を共有する要素は存在しない。言い換えると、分岐接合に対応する要素のみが、間引き処理を適用した最終的な結果において、厳密に２つより多くの面を、他の要素と共有することができる。両方の要素がそれぞれジオメトリ的に一致する面（すなわち、平面外側）を有する場合、２つの要素が面を共有すると言える。例えば、四面体メッシュの場合、要素は最大で４つの面を他の要素と共有することができ、その場合、それらの面はすべて「完全」である。これにより、間引き処理では、ある意味、Ｓ２０において提供された部分集合を、可能な限り間引く。
【００４９】
そのような例では、間引き処理を適用した結果は、隣接する要素の１次元配列のネットワークに対応し得るので、それぞれ線形に閲覧することができる。このように、決定すること（Ｓ３０）は、間引き処理の結果を閲覧すること（例えば、深さ優先探索または同等の閲覧を用いる）と、閲覧中に分岐に対応する要素（例えば、分岐が可能でないことが検出されている間）と分岐接合部に対応する要素（例えば、分岐が可能であると検出された場合、例えば、厳密に２つより多い数の面を他の要素と共有する要素に遭遇した場合）とを自動的に識別することと、同じ分岐接合部（例えば、分岐接合の第１の検出から、分岐が可能でないことを検出するまで）または同じ分岐に対応する要素（例えば、分岐接合部に対応する要素の２つの連続した検出の間）を自動的にグループ化することとを、その本質としてもよい。この識別およびグループ化は、骨格の表現をそのように提供することができる。しかし、例では、決定すること（Ｓ３０）は、前述および後述の詳細な掃引ボリューム算出例など、さらなるステップを含んでいてもよい。
【００５０】
ここで、間引き処理を適用した結果の、分岐の末端に対応する各要素は、間引き処理を適用した結果の、分岐接合部に対応する各要素と面を共有する。これは、間引き処理を適用した結果の、分岐の末端に対応すると定義することができる要素だけが、間引き処理を適用した結果の、分岐接合部に対応するそれぞれの要素と、面を共有すること意味するだけでなく、分岐の末端と分岐接合部との間の各接続点において、そのような面共有が存在することを意味する（なぜなら、分岐の末端は、間引き処理を適用した結果、対応する少なくとも１つの要素を必然的に有するからである。例えば、可能な限り間引いた四面体ＦＥＭの例では、ちょうど１つ）。「面を共有する」という表現は、ここでも、前者の要素の面が、後者の要素の面に重ね合わされる（または混合される、さらにはジオメトリ的に同一である）ことを意味する。
【００５１】
言い換えると、間引き処理は、結果として、局所的な非多様体の面ジオメトリ（例えば、間引き処理を適用した結果の境界面に対する非多様体の辺）を形成することによって、分岐が分岐接合部に到達するのを禁止するように構成することができる。所与のオブジェクトの局所的な非多様体の面ジオメトリは、上記境界面に対して非多様体である所与のオブジェクトの境界面上に位置するジオメトリ（すなわち、辺などのジオメトリ的実体）である。非多様体の概念はそれ自体公知であるが、後に定義する。同様に、分岐接合部が、結果における厳密に２つ以上の要素に対応する場合、間引き処理は、そのような分岐接合部が、結果において、局所的な非多様体の面ジオメトリを含むことを禁止するように構成されてもよい。また、間引き処理は、局所的な非多様体の面ジオメトリの作成を禁止してもよい。言い換えると、間引き処理の各動作ステップは、局所的な非多様体の面ジオメトリを生じさせないように制約される。より一般的には、本方法の任意のステップは、局所的な非多様体の面ジオメトリの作成を禁止してもよい（すなわち、ステップは、局所的な非多様体が作成されないように実行されるように構成される）。この局所的な非多様体の面ジオメトリの回避は、結果の精度を高める。
【００５２】
これにより、先行技術の間引き処理（先に述べたものなど）を改善する。実際、先行技術の間引き処理は、閉じた初期オブジェクトの正確なトポロジを保存し、そのような目的のために必要であれば局所的な非多様体の面ジオメトリを作成または維持する。これは、機械設計とトポロジ最適化の結果という文脈においては、関連するトポロジが初期のオブジェクトの内部にあるため、適切ではない。これについては後で詳述する。
【００５３】
例では、本方法の入力は、トポロジ最適化の結果として得られる四面体メッシュ化トポロジである。出力は、履歴ベースの特徴で作成された立体部品であり、主に、それぞれが骨格の分岐を表す掃引立体である。履歴ベースの特徴の算出には、以下のステップが含まれていてもよい。まず、傷、ひび割れ、および小さな空洞を除去するために、入力四面体メッシュにクリーニングを施す。次に、侵食のような処理（すなわち、間引き処理）によって、トポロジの間引きしたバージョンに達するまで、四面体が繰り返し除去される：すなわち「間引きメッシュ」。この間引きメッシュは、例えば線分の骨格とは対照的に、四面体からなる。次に、分岐四面体、ノード四面体用いて、接続された滑らかな曲線からなるワイヤーフレームグラフが間引きメッシュ上に構築される。このグラフは、入力された四面体メッシュの関連トポロジを捉えたものである。最後に、滑らかな曲線をスパイン曲線として用いて、編集可能な掃引立体が各分岐上に構築される。すべての掃引立体を足し合わせ、その結果として編集可能な立体が得られる。
【００５４】
例では、Ｓ２０で提供されるＦＥＭの部分集合は、トポロジ最適化処理の境界条件に対応する要素を有する。間引き処理は、トポロジ最適化処理の境界条件に対応する部分集合の要素の除去を禁止してもよい。言い換えると、間引き処理は、境界条件が定義された部分集合の要素を、例えばＳ１０の時点で除去しないように構成してもよい。例えば、上記要素は、それらを除去すべきでないという事実を表すデータによってマーク付けまたはタグ付けしてもよい。このように、本方法は、処理のいちばん最初に固定の四面体を設定することによって、従来技術の間引きアルゴリズムの課題を飛び超える。当該間引きアルゴリズムではそれらを除去することはできないため、間引きした形状は、最初の形状に準拠する。これにより、開始モデルからの距離を含む複雑な基準を実装する先行技術の間引きプロセスとは対照的に、簡単な方法で、意図された骨格を得ることが可能になる。
【００５５】
次に、上記の説明に従った図１の方法の例について、図７〜６８を参照して説明する。
【００５６】
ここでは四面体メッシュの例について説明する。Ｓ１０の入力、Ｓ１０の出力、Ｓ２０の入力、および／またはＳ２０の出力は、この例の本方法において、このタイプとすることができる。
【００５７】
四面体メッシュＭは、そのジオメトリ、およびその組み合わせ構造によって定義される。ジオメトリは３Ｄ点の有限集合である。組み合わせ構造は複数の四面体を含み、四面体は複数の三角形と複数の頂点を定義する。頂点は３Ｄ点に対する基準となる。辺は２つの頂点で定義される。三角形は３つの頂点で定義され、よって３つの辺を定義する。四面体は４つの頂点で定義され、４つの三角形と６つの辺を定義する。四面体の３Ｄ形状（三角形、辺）は、その３Ｄ点の凸包である。これは
【数１】
2018077830.tif 000003
の閉じた部分集合である。
【００５８】
四面体は、３Ｄ領域を定義するためにメッシュ構造に配置される。メッシュ構造は、以下の意味で有効である。すなわち、任意の２つの四面体は分離されているか、またはそれらはちょうど１つの頂点を共有しているか、またはちょうど１つの辺を共有しているか、またはちょうど１つの三角形を共有している。定義上、２つの四面体は、三角形を共有する場合に隣接している。言い換えると、四面体は重ならない。
【００５９】
図７〜９は、頂点共有（図７）、辺共有（図８）、および三角形共有（図９）を示す。図１０は、２つの隣接する四面体Ｔ1およびＴ2を示す。明確にするため、これらはわずかに離してある。図１１〜１３は、それぞれ、四面体Ｔ1およびＴ2に関連する、三角形ｆ1、・・・、ｆ7、辺ｅ1、・・・、ｅ9、および頂点ｖ1、・・・、ｖ5を示す。図１４は、上述の隣接する四面体に関連する組み合わせ構造を示す。これは「〜が〜の境界となる」という関係を捉えている。
【００６０】
メッシュは有効であり、各三角形は最大２つの四面体によって共有される。２つの四面体によって共有される三角形は、内部三角形と呼ばれる。１つの四面体だけの境界となる三角形は、境界三角形と呼ばれる。メッシュＭの境界は、すべての境界三角形によって定義される、三角形の閉じた面である。これは境界面と呼ばれ、∂Ｍと表される。境界三角形を境界とする四面体は、境界四面体と呼ばれる。
【００６１】
図１５〜１６は、６つの四面体（図１６）によってメッシュ化された矩形ブロック（図１５）を示す。図１７は、内部三角形を示している。図１８は、境界面を定義する境界三角形を示す。
【００６２】
Ｓｈａｐｅ（Ｍ）で表されている四面体メッシュの形状は、その四面体のすべての形状の和集合である。これは
【数２】
2018077830.tif 000004
の閉じた部分集合である。数学的観点では、Ｓｈａｐｅ（Ｍ）の内部は、Ｓｈａｐｅ（Ｍ）に含まれる最大の開集合である。これはＩｎｔ（Ｓｈａｐｅ（Ｍ））と表される。図１９は、Ｍ、∂Ｍ、Ｓｈａｐｅ（Ｍ）、およびＩｎｔ（Ｓｈａｐｅ（Ｍ））の２Ｄバージョンを示す。
【００６３】
ここで、前述の多様体および非多様体の頂点および辺の概念について説明する。
Ｓを
【数３】
2018077830.tif 000005
の閉じた面とし、ＸをＳ上の点とする。定義上、すべての半径値０＜ｒ≦ｒ0に対して、半径ｒ0＞０が存在する場合、点Ｘ∈Ｓは多様体であり、集合Ｓは、Ｘを中心とする半径ｒの開いたボールをちょうど２つに分割する。形式上、図２０〜２１に示すように、集合Ｂａｌｌ（Ｘ，ｒ）−Ｓが、すべてのｒ∈］０，ｒ0］についてちょうど２つの接続成分を含む場合、Ｓは点Ｘで多様体である。
【００６４】
上に定義した規則的なメッシュＭが与えられれば、多様体の概念を用いて、境界面∂Ｍの規則性を定義することができる。この文脈では、∂Ｍの非多様体は頂点または辺のいずれかである。
【００６５】
図２２は、一辺を共有する６つの３Ｄ点と２つの四面体からなるメッシュＭを示している。その境界面∂Ｍは８つの三角形を含む。十分に小さいすべてのｒについて、図２３に示すように、集合Ｂａｌｌ（Ｘ，ｒ）−∂Ｍは４つの成分、すなわち、右の四面体の内側Ａ、左の四面体の内側Ｂ、周囲空間の上辺Ｃ、および周囲空間の下辺Ｄからなるため、共有された辺の内側の任意の点Ｘは非多様体である。
【００６６】
図２４は、頂点を共有する７つの３Ｄ点と２つの四面体からなるメッシュＭを示している。その境界面∂Ｍは８つの三角形を含む。十分に小さいすべてのｒについて、集合Ｂａｌｌ（Ｘ，ｒ）−∂Ｍは３つの成分、すなわち、右の四面体の内側、左の四面体の内側、および周囲空間からなるため、共有点Ｘ∈∂Ｍは非多様体である。
【００６７】
ここで、グローバルメッシュとアクティブメッシュの概念について説明する。例における本方法を便利に実装するために、この概念を利用することができる。しかし、他の実装法も考えられる。
【００６８】
例における本方法は、処理の開始時に算出され、かつ、変化することのない、グローバル四面体メッシュＧを、このグローバルメッシュのサブ部分（または部分集合）と共に扱うことができる。グローバルメッシュＧのサブ部分Ｍは、Ｇの四面体を選択したものである。Ｍに四面体を追加することは、Ｇ−Ｍの四面体を「アクティブ」に設定することである。同様に、Ｍから四面体Ｔを除去することは、それを「非アクティブ」に設定することである。したがって、隣接関係の概念は、コンテキストを定義して使用する必要がある。四面体Ｔが与えられると、符号Ａｄｊ（Ｔ）は、Ｔと三角形を共有するグローバルメッシュＧのすべての四面体の集合である。符号ＡｄｊM（Ｔ）は、Ｔと三角形を共有するメッシュＭのすべての四面体の集合である。なお、ＡｄｊM（Ｔ）は、ＴがＭに属しているかどうかにかかわらず有意である。
【００６９】
ここで、Ｓ１０の例について説明する。
【００７０】
この例では、ユーザは、（まだ知られていない）機械部品を含む材料の量である、いわゆる「設計空間」を作成する。境界条件は、伝統的な有限要素解析処理のように、設計空間上に定義される。次に、設計空間をメッシュ化し、境界条件の種類に応じて固定要素を特定する。メッシュ化された設計空間をＧと表す。図２５は、境界条件と共に設計空間を示す。図２６はメッシュ化された設計空間である。固定要素２６２は太線内にある。
【００７１】
専用のアルゴリズムが有限要素問題を解き、密度場を算出する。これは、スカラ値Ｆ（Ｔ）がＧの各メッシュＴに関連付けられることを意味する。ここからは、便宜上、メッシュは四面体メッシュであるとする。非四面体メッシュを四面体メッシュに変更することが常に可能である。
【００７２】
大まかに言えば、小さな密度場の値Ｆ（Ｔ）は、四面体Ｔが実際には解に寄与せず、除去できることを意味する。逆に、高い密度値Ｆ（Ｔ）は、四面体Ｔが実際に解に寄与し、保持されるべきであることを意味する。最適化メッシュＭは、所与の閾値より高い密度値Ｆ（Ｔ）を特徴とするＧのすべての四面体Ｔを含む。
【００７３】
図２７は、メッシュ化された設計空間Ｇ（白い三角形２７４）および固定要素（黒色の三角形２７６）とともに、最適化メッシュＭ（灰色の三角形２７２）を示す。
【００７４】
ここで、決定すること（Ｓ３０）の例を、特に、図２８によって示される本方法の例のフローチャートを特に参照して説明する。
【００７５】
例において、本方法は、Ｓ２０および／またはＳ３０の前に、最適化メッシュにクリーニングを施すことを含んでいてもよい。これについてここで説明する。
【００７６】
トポロジ最適化の結果として生じるメッシュは、望ましくない特異性を特徴とすることがある。この現象は、孤立した四面体を除去する可能性のある密度場に適用された閾値によって引き起こされる。これにより、材料内に小さな空隙ができる。
【００７７】
この問題を解決するための第１の方法は、各四面体の密度場値を隣接する値と平均することによって密度場を平滑化することである。四面体Ｔの密度場値をＦ（Ｔ）とすると、その平滑化された密度場値はＦ*（Ｔ）と表され、以下により定義される。
【数４】
2018077830.tif 000006
ここで、Ａｄｊ（Ｔ）はＴに隣接する四面体の集合であり、混合パラメータの典型的な値はα＝０．８である。
【００７８】
第２の（代替的または追加的な）解決策は、四面体メッシュを連続的に拡張し、侵食させることである。論文「Ｈ．Ｊ．Ａ．Ｍ．Ｈｅｉｊｍａｎｓ，Ｍａｔｈｅｍａｔｉｃａｌ  ｍｏｒｐｈｏｌｏｇｙ：ａ  ｇｅｏｍｅｔｒｉｃａｌ  ａｐｐｒｏａｃｈ  ｉｎ  ｉｍａｇｅ  ｐｒｏｃｅｓｓｉｎｇ，Ｎｉｅｕｗ  Ａｒｃｈｉｅｆ  ｖｏｏｒ  Ｗｉｓｋｕｎｄｅ，Ｓｅｒ．４，Ｖｏｌ．１０，ｎｏ．３，ｐｐ．２３７−２７６（Ｎｏｖ．１９９２）」で説明されているように、先行技術から、これにより有意な大きな空洞を保存しつつ、無意味な小さな空洞を自然に排除できることが公知である。
【００７９】
本方法の文脈において、拡張操作は、最適化メッシュＭに対して、Ｍの境界三角形に隣接するＧ−Ｍの全ての四面体を加えることであってもよい。結果として生じるメッシュはδ（Ｍ）で表される。侵食操作は、所与のメッシュから、境界三角形に隣接する全ての四面体を除去することであってもよい。これはε（Ｍ）で表される。正規化はε（δ（Ｍ））である。正規化したメッシュＭ’＝ε（δ（Ｍ））は、以下の意味で安定している。す
なわち、Ｍ’＝ε（δ（Ｍ’））であり、これは正規メッシュを正規化すると同じメッシ
ュが得られることを意味する。
【００８０】
図２９は、空洞（灰色の三角形の内側の白い三角形２９２）を特徴とする初期メッシュＭ（灰色の三角形２７２および黒色の三角形２７６）を示す。図３０は、対応する拡張メッシュδ（Ｍ）を示す。なお、小さな空洞が埋められている。図３１は、拡張メッシュε（δ（Ｍ））の侵食を示す。明らかに、小さな空洞は埋められ、大きな空洞３１２を含む概形は全体的に維持される。
【００８１】
実際には、拡張／侵食処理は以下のように実施することができる。拡張ステップが算出されるが、侵食ステップは、以下に説明する間引き処理の第１の繰り返しに含まれる。
【００８２】
ここで、機械設計の文脈に合ったメッシュＭの関連トポロジの概念について説明する。例における本方法では、そのような関連性に到達することができる。
【００８３】
理論的には、Ｓｈａｐｅ（Ｍ）は物理的なオブジェクトを表すことを意図しているので、メッシュＭの境界面∂Ｍは多様体の面であると考えられる。残念ながら、この仮説は、グローバルメッシュＧ内の膨大な数の四面体のため、また密度場における不可避の閾値副作用のため、現実的ではない。メッシュＭは、非多様体の辺、および／または、非多様体の頂点を有することができ、本発明はこれに対処するように設計されている。
【００８４】
特異点をどのように考慮するか決定しなければならない。非多様体の辺（または頂点）は、理論上、厚みがゼロのゾーンであり、これは物理的な観点からは意味をなさない。厚みがゼロであることは、図３２に示すように、用途に応じて、「材料がない」または「材料が非常に少ない」と解釈される。
【００８５】
本方法の文脈において、決定は、特異性が「材料がない」状況であるということであってもよい。この理由から、メッシュＭの関連トポロジは、その内部のものであり、これは前に定義され、Ｉｎｔ（Ｓｈａｐｅ（Ｍ））で表される。この原理に従って、本方法のさらなるアルゴリズムを設計することができる。
【００８６】
ここで、Ｓ３０における最適化メッシュの間引きの例について説明する。
【００８７】
メッシュＭの間引きの目的は、Ｉｎｔ（Ｓｈａｐｅ（Ｍ））と同じトポロジを有する骨格構造を明らかにするために、可能な限り少ない数の四面体を特徴とするメッシュＫを得ることである。これが、閉じた集合Ｓｈａｐｅ（Ｍ）のトポロジを保存する他の間引きアルゴリズムと比較した際の、本方法の特異性である。さらに、境界条件をサポートする四面体は固定されていてもよい。これはすなわち、それらは除去されず、すべて、最終的なメッシュＫに属することを意味する。
【００８８】
ここで、上述の例に従って、本方法の全体的なアルゴリズムの一例について説明する。
【００８９】
原理は、適切な基準（以下の擬似コードのステップ０５）に従って、（固定されていない）境界四面体を繰り返し除去することである。言い換えると、間引き処理の繰り返しのそれぞれで除去される部分集合の要素は、すべて、除去が禁止されていない繰り返しのそれぞれにおける部分集合の境界要素である。
【００９０】
また、各繰り返しにおいて、上記間引き工程は、上記部分集合の境界要素を、上記部分集合の別の要素と共有される隣接面の数に従って、最も低い数から最も高い数の順で除去してもよい。言い換えると、隣接する三角形の数が最小であること（すなわち、面共有隣接関係の意味において）を特徴とする四面体は、優先的に除去される（以下のステップ０３）。繰り返しにおけるこのような特定の順序は、関連形状（典型的には突起）が間引き中に完全に侵食され失われる従来技術の間引きとは異なり、この現象を回避するには不十分なチューニングパラメータおよび発見的方法が含まれている場合であっても、関連形状を除去しない結果に到達することを可能にする。
【００９１】
したがって、アルゴリズムは、以下の擬似コードとすることができる。
【数５】
2018077830.tif 000007
【００９２】
境界四面体が除去されないとき、アルゴリズムは終了する。結果として得られるメッシュＫは最小だが、一意ではない。その形状はＫ0における四面体の順序に依存する。テストはこれが問題ではないことを示している。
【００９３】
ここで、ステップ０３で境界四面体の集合を選択するための例を示す。
【００９４】
メッシュＫの四面体Ｔの隣接四面体の数は｜ＡｄｊK（Ｔ）｜で表される。明らかに０≦｜ＡｄｊK（Ｔ）｜≦４である。｜ＡｄｊK（Ｔ）｜＝４のとき、四面体ＴはＫの境界四面体ではない。その他の場合、Ｋの境界四面体である。集合Ｋ0は、隣接四面体の数が最小であることを特徴とする（固定されていない）四面体を集めることによって算出される。
【００９５】
したがって、この選択は、以下の擬似コードとすることができる。
【数６】
2018077830.tif 000008
【００９６】
ここで、ステップ０５で実行される論理テストの一例について説明する。
【００９７】
入力メッシュＭの境界面∂Ｍは、非多様体の辺および／または頂点を特徴してもよいことが理解されなければならない。原理は、追加の非多様体の辺または頂点が作成されない限り、（固定されていない）境界四面体を削除することである。それにもかかわらず、Ｉｎｔ（Ｓｈａｐｅ（Ｍ））のトポロジが保存される限り、いくつかの既存の非多様体の状況が除去され、切断を引き起こすことがある。専用のセクションがこの現象を示す。
【００９８】
集合Ｋ0に集められた四面体Ｔが与えられ、その辺Ｅの１つが与えられると、第１の分析は以下のように実行されてもよい。辺Ｅを共有するＧの全ての四面体には、四面体Ｔ自体と、Ｔに隣接する最大２つの四面体と、Ｔに隣接しない他の四面体が含まれる。
【００９９】
解析は、以下の論理関数の擬似コードに従って実行することができる。
【数７】
2018077830.tif 000009
【０１００】
「ｉｆ・・・ｔｈｅｎ」命令では、辺ＥがメッシュＧの境界辺である場合、濃度テスト（｜Ａ｜＝２，｜Ｂ｜＝０）が重要である。この場合、集合Ａは空でもよいし、あるいは１つの四面体のみを含んでいてもよく、集合Ｂも同様に空でもよい。濃度テストは、メッシュＧの外側が、Ｋに属さない四面体のように振る舞うように設計されている。
【０１０１】
Ｇの境界辺ではない辺Ｅを考慮して、図３３〜３４は、関数ＣａｎＢｅＲｅｍｏｖｅｄ＿１（Ｋ，Ｔ，Ｅ）がＴＲＵＥを返す、すべての状況を示す。四面体で共有される辺Ｅ（ドット）は、描画面に対して垂直である。値１（または値０）を持つ三角形はＫに属する（またはＫに属さない）。符号Ａ、Ｂは、関数によって構築された四面体の集合を指す。
【０１０２】
また、Ｇの境界辺ではない辺Ｅを考慮して、図３５は、関数ＣａｎＢｅＲｅｍｏｖｅｄ＿１（Ｋ，Ｔ，Ｅ）がＦＡＬＳＥを返す、すべての状況を示す。Ｔを除去すると、非多様体の辺が作成される。
【０１０３】
除去すべき四面体Ｔが与えられ、その頂点Ｖの１つが与えられるとき、第２の解析が以下のように実行される。頂点Ｖを共有する全ての四面体には、四面体Ｔ自体と、Ｔに隣接する最大３つの四面体と、Ｔに隣接しない他の四面体が含まれる。
【０１０４】
解析は、以下の論理関数の擬似コードに従って実行することができる。
【数８】
2018077830.tif 000010
【０１０５】
ここでも、「ｉｆ・・・ｔｈｅｎ」命令は、頂点ＶがメッシュＧの境界辺である場合に重要な、濃度テスト（｜Ａ｜＝３，｜Ｂ｜＝０）を特徴とする。この場合、集合Ａは空でもよいし、あるいは１つまたは２つの四面体のみを含んでいてもよく、集合Ｂも同様に空でもよい。濃度テストは、メッシュＧの外側が、Ｋに属さない四面体のように振る舞うように設計されている。
【０１０６】
アルゴリズムのステップ０５である最終テストは、候補となる四面体のすべての辺および頂点に上述の関数を適用することによって実行することができる。これは、以下の擬似コードに従って実行することができる。
【数９】
2018077830.tif 000011
【０１０７】
そのような間引き処理について、図３６〜４４を参照して説明する。
【０１０８】
図３６〜３８は、例示的な２Ｄメッシュ上の間引き処理の第１の繰り返しを示す。図３６は、初期メッシュＫ＝Ｍである。間引き処理では、白い三角形で示すように、隣接する三角形の数が最も少ない三角形を除去する。図３７で除去した三角形には、隣接する三角形が１つだけある。図３８で除去した三角形には、隣接する三角形が１つだけある。
【０１０９】
繰り返しにより、図３９〜４４に示される、メッシュＫの中間バージョンが得られる。図３９で除去した三角形には、隣接する三角形が２つある。図４０で除去した三角形には、隣接する三角形が１つだけある。図４４は、骨格メッシュ、すなわちＫの最終バージョンである。Ｋから除去できる三角形はない。
【０１１０】
これは、間引き処理の前に境界条件を用いて定義した固定四面体の利点を表す。これらすべての、固定され、ぶら下がっている分岐が除去されると、中央のループだけになる。
【０１１１】
間引き処理が分かったところで、図４５〜５１は、内部トポロジの保存を示す。図４５に示す２ＤメッシュＭ’を考える。これは、２つの空洞の接合部に非多様体の頂点がある
ことを特徴としている。
【０１１２】
Ｍ’のオブジェクトＳｈａｐｅ（Ｍ’）は、閉集合であり、図４６に示すように、実際
には２つの空洞を特徴とする。逆に、開集合Ｉｎｔ（Ｓｈａｐｅ（Ｍ’））は、図４７に
示すように１つの空洞のみを特徴とする。これは、空洞間の点状の接続が、内部集合を考慮して、「開かれている」ためである。
【０１１３】
区間に関しては、閉集合Ｓｈａｐｅ（Ｍ’）の２つの空洞は開集合であり、それらは互
いに素の（開いた）２つの区間からなる］ａ，ｂ［∪］ｂ，ｃ［のように振る舞う。開集合Ｉｎｔ（Ｓｈａｐｅ（Ｍ’））の空洞は閉集合であり、単一の（閉じた）区間である［
ａ，ｂ］∪［ｂ，ｃ］のように振舞う。このように、開いたＩｎｔ（Ｓｈａｐｅ（Ｍ’）
）には空洞が１つしかない。
【０１１４】
予想されるように、間引きアルゴリズムは、図４８に示すように、１つの空洞を有するメッシュＫ’を生成する。上で詳述したように、図４９に示す構成によって、特異点の除
去が可能である。これは図５０〜５１に示されている。
【０１１５】
ここで、Ｓ３０において決定された骨格の表現の例を、上記の間引き処理の例によって得られる結果から開始して説明する。
【０１１６】
ここでは、ワイヤフレームの骨格の例について説明する。
【０１１７】
ここで、線分からなるワイヤフレームの骨格を算出するために実際に骨格メッシュＫを用いてもよい。最初のバージョンでは、このワイヤフレームの骨格は、一般的に、鋭い点を特徴とするが、後のステップで平滑化される場合がある。Ｋの各四面体は、分岐四面体またはノード四面体のいずれかである。定義上、分岐四面体はちょうど２つの四面体に隣接しており、ノード四面体は３つまたは４つの四面体に隣接し、端の四面体は１つの四面体のみに隣接している。図５２は、ノード四面体Ｔに接合する３つの分岐を局所的に示す。
【０１１８】
分岐の認識は、以下のように行うことができる。ワイヤフレームの骨格の定義には、固定ノード四面体、非固定ノード四面体、および非固定分岐四面体のみが関与する。Ｋ*をそのような四面体の集合とする。各分岐は、最初の未巡回（ｎｏｎ−ｖｉｓｉｔｅｄ）の分岐四面体Ｔ0の位置を特定し、Ｔ0から、ノード四面体、または巡回済み（ｖｉｓｉｔｅｄ）の四面体まで、両側における隣接関係の伝播によって認識される。アルゴリズムを開始する前に、すべての四面体は「未巡回」に設定される。
【０１１９】
これは、以下の擬似コードに従って実行することができる。
【数１０】
2018077830.tif 000012
【０１２０】
アルゴリズムは、すべての分岐四面体が巡回されたときに終了する。これは、各分岐四面体は一意の分岐に関連付けられていることを意味する。
【０１２１】
同一のノード四面体で開始し終了する分岐は破棄される。ノード四面体を含まない分岐は孤立したループであり、それらも破棄される。そのような分岐を破棄すると、新たに除去可能な境界四面体が作成される可能性がある。このため、間引き処理が再度実行される。図５３〜５４は、廃棄された閉じた分岐を点線で示す。
【０１２２】
図５５は、分岐三角形５５２（薄い輪郭を有する灰色）及びノード三角形５５４（太い輪郭を有する黒色または灰色）によって定義されるＫ*を示す。固定分岐と端部の三角形は図示されていない。
【０１２３】
各ノード四面体の重心に３Ｄ点を作成することができる。次に、図５６に示すように、隣接する分岐四面体を辿ることで、これらの点の間にポリラインを作成することができる。
【０１２４】
そして、図５７に示すように、端点および中間点を通るスプライン曲線を算出することによって各ポリラインを平滑化することができる。もちろん、それより多くの点がスプライン曲線の定義に含まれることがある。
【０１２５】
ここで、前述のＳ３０の例における掃引ボリュームの作成について説明する。
【０１２６】
滑らかな分岐は、それぞれ、掃引立体のスプライン曲線として用いることができる。スプライン曲線に沿って掃引される外形は、可変半径円である。その中心点はスプライン曲線上にあり、半径変動は、最適化メッシュＭの局所サイズを近似することによって算出される。
【０１２７】
形式上、
【数１１】
2018077830.tif 000013
をスプライン曲線とする。目標は、例えば、半径変動
【数１２】
2018077830.tif 000014
のかたちでセクション分布を算出することであり得る。パラメータｔ∈［０，１］において、掃引ボリュームのセクションは、Ｑ（ｔ）を中心とし、Ｑ（ｔ）を通りベクトルＱ’
（ｔ）に垂直な平面内で半径ｒ（ｔ）を有する円である。
【０１２８】
ここで、どのように局所サイズの近似を実行するかについての例を説明する。この情報（例えば、先に、間引き中に得られる）は、セクション分布の算出に用いることができる。
【０１２９】
間引き処理の間、四面体の除去に関する、ある論理情報を、この目的のために格納することができる。最初に、メッシュＭの各境界四面体が、識別子および一組の識別子に関連付けられてもよい。各四面体の組は、上記四面体の識別子で開始させることができる。すべての非境界四面体は、｛｝で表される空集合と関連付けられていてもよい。図５８は、初期状態を示す。境界四面体は、０から９までの数字によって記号的に識別される。
【０１３０】
次に、境界四面体が削除されるたびに、その集合が、それに隣接するすべての四面体の集合に追加されてもよい。図５９は境界四面体０と１の除去を示す。隣接四面体の空でない集合に注目する。
【０１３１】
間引き処理が終了すると、結果として得られる各分岐四面体Ｔは、一組の境界四面体識別子Ｌ（Ｔ）＝｛ｉ1，・・・，ｉb(T)｝に関連付けられる。ここで、ｂ（Ｔ）は集合Ｌ（Ｔ）における要素の数である。図６０は最終的な状態を表す。
【０１３２】
分岐四面体Ｔを含む分岐の、近似された局所半径ｒ（Ｔ）は、四面体Ｔからその集合における四面体への平均距離である。２つの四面体の間の距離は、それぞれの平均点の間の距離である。
【数１３】
2018077830.tif 000015
【０１３３】
例えば、集合｛６，７，８｝に関連付けられた分岐四面体Ｔ（図６１における太線の輪郭６１２）の局所半径は、図６１に示すように、Ｔと境界四面体６、７、および８の平均距離である。
【０１３４】
局所サイズの近似は、境界四面体を除去する順序に依存する。しかしながら、テストでは、これが結果として得られる形状に重大な影響は与えないことが示されている。
【０１３５】
ここで、掃引ボリュームを構成する例について説明する。
【０１３６】
図６２を参照すると、スプライン曲線６２２が与えられたとき、可変半径変動は、スプライン曲線の端点および中間点での近似局所サイズを補間することによって定義される。ここでも、より多くの点が関与してもよい。結果として得られる掃引立体は、ここでは明確に定義されている。
【０１３７】
この立体のＢ−Ｒｅｐは、回転最小化フレーム演算を用いて作成された、パラメータ化された面である。これは論文「Ｗａｎｇ，Ｗ．，Ｊuｔｔｌｅｒ，Ｂ．，Ｚｈｅｎｇ，Ｄ．，ａｎｄ  Ｌｉｕ，Ｙ．２００８．Ｃｏｍｐｕｔａｔｉｏｎ  ｏｆ  ｒｏｔａｔｉｏｎ  ｍｉｎｉｍｉｚｉｎｇ  ｆｒａｍｅ．ＡＣＭ  Ｔｒａｎｓ．Ｇｒａｐｈ．２７，１，Ａｒｔｉｃｌｅ  ２（Ｍａｒｃｈ  ２００８）」に記載されているように実行できる。図６３〜６４は、滑らかな半径変化と共に、３Ｄスパライン曲線を示す。図６５は、対応する掃引面を示す。編集可能な立体は、古典的な履歴特徴リストに取り込まれたすべての掃引立体のブール和集合である。最終形状を滑らかにするために、自動的にフィレットを追加することができる。
【０１３８】
図６６〜６８は、現実の３Ｄの例において、骨格構造（図６６）、平滑化されたワイヤフレーム構造（図６７）、および掃引ボリュームを組み合わせた最終的な立体（図６８）の、局所形状を示す。
【０１３９】
ここで、Ｓ４０で実行可能な立体編集の例について説明する。
【０１４０】
結果として得られる立体を編集するには、２つの方法がある。第１の方法は、掃引ボリュームとフィレットの古典的な履歴ツリーを扱うことである。第２の方法は、立体の面、辺、および頂点と、骨格の分岐との間のリンクを維持することである。ユーザが立体の面、辺、または頂点を選択すると、関連付けられた分岐、および場合によっては残りの骨格に対して、ユーザ操作を実行することができる（例えば、分岐を移動させたり除去したりして、隣接する分岐に影響を与える）。次に、掃引ボリュームの生成、ブール演算、およびフィレットが再実行される。あるいは、いくつかのユーザ操作では、骨格構造は変更されない。たとえば、分岐のセクションが変更された場合（円形セクションから楕円形セクションに変更された場合）、掃引ボリュームとその後の演算だけが再実行される。
【図１】
2018077830.tif 000016
【図２】
2018077830.tif 000017
【図３】
2018077830.tif 000018
【図４】
2018077830.tif 000019
【図５】
2018077830.tif 000020
【図６】
2018077830.tif 000021
【図７】
2018077830.tif 000022
【図８】
2018077830.tif 000023
【図９】
2018077830.tif 000024
【図１０】
2018077830.tif 000025
【図１１】
2018077830.tif 000026
【図１２】
2018077830.tif 000027
【図１３】
2018077830.tif 000028
【図１４】
2018077830.tif 000029
【図１５】
2018077830.tif 000030
【図１６】
2018077830.tif 000031
【図１７】
2018077830.tif 000032
【図１８】
2018077830.tif 000033
【図１９】
2018077830.tif 000034
【図２０】
2018077830.tif 000035
【図２１】
2018077830.tif 000036
【図２２】
2018077830.tif 000037
【図２３】
2018077830.tif 000038
【図２４】
2018077830.tif 000039
【図２５】
2018077830.tif 000040
【図２６】
2018077830.tif 000041
【図２７】
2018077830.tif 000042
【図２８】
2018077830.tif 000043
【図２９】
2018077830.tif 000044
【図３０】
2018077830.tif 000045
【図３１】
2018077830.tif 000046
【図３２】
2018077830.tif 000047
【図３３】
2018077830.tif 000048
【図３４】
2018077830.tif 000049
【図３５】
2018077830.tif 000050
【図３６】
2018077830.tif 000051
【図３７】
2018077830.tif 000052
【図３８】
2018077830.tif 000053
【図３９】
2018077830.tif 000054
【図４０】
2018077830.tif 000055
【図４１】
2018077830.tif 000056
【図４２】
2018077830.tif 000057
【図４３】
2018077830.tif 000058
【図４４】
2018077830.tif 000059
【図４５】
2018077830.tif 000060
【図４６】
2018077830.tif 000061
【図４７】
2018077830.tif 000062
【図４８】
2018077830.tif 000063
【図４９】
2018077830.tif 000064
【図５０】
2018077830.tif 000065
【図５１】
2018077830.tif 000066
【図５２】
2018077830.tif 000067
【図５３】
2018077830.tif 000068
【図５４】
2018077830.tif 000069
【図５５】
2018077830.tif 000070
【図５６】
2018077830.tif 000071
【図５７】
2018077830.tif 000072
【図５８】
2018077830.tif 000073
【図５９】
2018077830.tif 000074
【図６０】
2018077830.tif 000075
【図６１】
2018077830.tif 000076
【図６２】
2018077830.tif 000077
【図６３】
2018077830.tif 000078
【図６４】
2018077830.tif 000079
【図６５】
2018077830.tif 000080
【図６６】
2018077830.tif 000081
【図６７】
2018077830.tif 000082
【図６８】
2018077830.tif 000083
【外国語明細書】
2018077830.tif 000084
2018077830.tif 000085
2018077830.tif 000086
2018077830.tif 000087
2018077830.tif 000088
2018077830.tif 000089
2018077830.tif 000090
2018077830.tif 000091
2018077830.tif 000092
2018077830.tif 000093
2018077830.tif 000094
2018077830.tif 000095
2018077830.tif 000096
2018077830.tif 000097
2018077830.tif 000098
2018077830.tif 000099
2018077830.tif 000100
2018077830.tif 000101
2018077830.tif 000102
2018077830.tif 000103
2018077830.tif 000104
2018077830.tif 000105
2018077830.tif 000106
2018077830.tif 000107
2018077830.tif 000108
2018077830.tif 000109
2018077830.tif 000110
2018077830.tif 000111
2018077830.tif 000112
2018077830.tif 000113
2018077830.tif 000114
2018077830.tif 000115
2018077830.tif 000116
2018077830.tif 000117
2018077830.tif 000118
2018077830.tif 000119
2018077830.tif 000120
【図１】
2018077830.tif 000121
【図２】
2018077830.tif 000122
【図３】
2018077830.tif 000123
【図４】
2018077830.tif 000124
【図５】
2018077830.tif 000125
【図６】
2018077830.tif 000126
【図７】
2018077830.tif 000127
【図８】
2018077830.tif 000128
【図９】
2018077830.tif 000129
【図１０】
2018077830.tif 000130
【図１１】
2018077830.tif 000131
【図１２】
2018077830.tif 000132
【図１３】
2018077830.tif 000133
【図１４】
2018077830.tif 000134
【図１５】
2018077830.tif 000135
【図１６】
2018077830.tif 000136
【図１７】
2018077830.tif 000137
【図１８】
2018077830.tif 000138
【図１９】
2018077830.tif 000139
【図２０】
2018077830.tif 000140
【図２１】
2018077830.tif 000141
【図２２】
2018077830.tif 000142
【図２３】
2018077830.tif 000143
【図２４】
2018077830.tif 000144
【図２５】
2018077830.tif 000145
【図２６】
2018077830.tif 000146
【図２７】
2018077830.tif 000147
【図２８】
2018077830.tif 000148
【図２９】
2018077830.tif 000149
【図３０】
2018077830.tif 000150
【図３１】
2018077830.tif 000151
【図３２】
2018077830.tif 000152
【図３３】
2018077830.tif 000153
【図３４】
2018077830.tif 000154
【図３５】
2018077830.tif 000155
【図３６】
2018077830.tif 000156
【図３７】
2018077830.tif 000157
【図３８】
2018077830.tif 000158
【図３９】
2018077830.tif 000159
【図４０】
2018077830.tif 000160
【図４１】
2018077830.tif 000161
【図４２】
2018077830.tif 000162
【図４３】
2018077830.tif 000163
【図４４】
2018077830.tif 000164
【図４５】
2018077830.tif 000165
【図４６】
2018077830.tif 000166
【図４７】
2018077830.tif 000167
【図４８】
2018077830.tif 000168
【図４９】
2018077830.tif 000169
【図５０】
2018077830.tif 000170
【図５１】
2018077830.tif 000171
【図５２】
2018077830.tif 000172
【図５３】
2018077830.tif 000173
【図５４】
2018077830.tif 000174
【図５５】
2018077830.tif 000175
【図５６】
2018077830.tif 000176
【図５７】
2018077830.tif 000177
【図５８】
2018077830.tif 000178
【図５９】
2018077830.tif 000179
【図６０】
2018077830.tif 000180
【図６１】
2018077830.tif 000181
【図６２】
2018077830.tif 000182
【図６３】
2018077830.tif 000183
【図６４】
2018077830.tif 000184
【図６５】
2018077830.tif 000185
【図６６】
2018077830.tif 000186
【図６７】
2018077830.tif 000187
【図６８】
2018077830.tif 000188