(57)【要約】【課題】コンピュータ支援設計（ＣＡＤ）又はコンピュータ支援エンジニアリング（ＣＡＥ）システムにおいてＣＡＤドメインをメッシュ化するうえで使用する方法。【解決手段】上記方法は、予め選択されたメッシュ品質メトリックを満たさないメッシュ要素を、先行して生成されたメッシュの内部要素についてメッシュ要素最適化を経たＣＡＤドメインの先行して生成されたメッシュから抽出することにより、メッシュ要素の組を得る工程と、メッシュ要素の組を接続サブメッシュに分解する工程と、サブメッシュの境界ノードを移動させないという条件で、別個に、かつ並列に各サブメッシュについて直列メッシュ要素最適化プロセスを行って、最適化サブメッシュを得る工程と、最適化サブメッシュを先行して生成されたメッシュに一体化させることにより、ＣＡＤドメインの最適化メッシュを得る工程とを含む手順を行う工程を含む。【選択図】図５
2015149052.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータ支援設計（ＣＡＤ）又はコンピュータ支援エンジニアリング（ＣＡＥ）システムにおいてＣＡＤドメインをメッシュ化するうえで使用する方法であって、前記方法は、
予め選択されたメッシュ品質メトリックを満たさないメッシュ要素を、前記ＣＡＤドメインの先行して生成されたメッシュの内部要素についてメッシュ要素最適化を経た前記先行して生成されたメッシュから抽出することにより、メッシュ要素の組を得る工程と、
前記メッシュ要素の組を接続サブメッシュに分解する工程と、
サブメッシュの境界ノードを移動させないという条件で、別個に、かつ並列に各サブメッシュについて直列メッシュ要素最適化プロセスを行って、最適化サブメッシュを得る工程と、
前記最適化サブメッシュを前記先行して生成されたメッシュに一体化させることにより、前記ＣＡＤドメインの最適化メッシュを得る工程と
を含む手順を行う工程を含む方法。
【請求項２】
請求項１記載の方法であって、メッシュ要素の組を得る工程は、更に、前記予め選択されたメッシュ品質メトリックを満たさないメッシュ要素を抽出した後、前記抽出されたメッシュ要素についてメッシュ要素接続性を使用して、前記組におけるメッシュ要素の数が所要レベルに拡張されるように前記組に含めるための更なるメッシュ要素を特定する工程を含む方法。
【請求項３】
請求項１又は２に記載の方法であって、前記ＣＡＤドメインを複数のサブドメインに分離し、各サブドメインについてサブドメイン・メッシュを作成し、各サブドメイン・メッシュの内部要素を最適化し、結果として生じるサブドメイン・メッシュをマージして前記メッシュを形成することにより、前記手順において使用するためのメッシュを、前記手順を行う前に生成する工程を更に含む方法。
【請求項４】
請求項３記載の方法であって、前記サブメッシュは、並列分離メッシュ化プロセスを使用して作成される方法。
【請求項５】
請求項３又は４に記載の方法であって、各サブドメイン・メッシュの内部要素は、直列メッシュ要素最適化プロセスを使用して最適化される方法。
【請求項６】
請求項５記載の方法であって、前記直列メッシュ要素最適化プロセスがそれぞれのサブメッシュに対して別個にかつ並列に行われる方法。
【請求項７】
コンピュータ支援設計（ＣＡＤ）又はコンピュータ支援エンジニアリング（ＣＡＥ）システムにおいてＣＡＤドメインをメッシュ化するうえで使用する装置であって、前記装置は、
予め選択されたメッシュ品質メトリックを満たさないメッシュ要素を、前記ＣＡＤドメインの先行して生成されたメッシュの内部要素についてメッシュ要素最適化を経た前記先行して生成されたメッシュから抽出することにより、メッシュ要素の組を得るよう構成された組抽出手段と、
前記メッシュ要素の組を接続サブメッシュに分解するよう構成されたサブメッシュ作成手段と、
サブメッシュの境界ノードを移動させないという条件で、別個に、かつ並列に各サブメッシュについて直列メッシュ要素最適化プロセスを行って、最適化サブメッシュを得るよう構成されたサブメッシュ最適化手段と、
前記最適化サブメッシュを前記先行して生成されたメッシュに一体化させることにより、前記ＣＡＤドメインの最適化メッシュを得るよう構成されたメッシュ一体化手段とを備える装置。
【請求項８】
請求項７記載の装置であって、前記組抽出手段は、
前記予め選択されたメッシュ品質メトリックを満たさない前記先行して生成されたメッシュからメッシュ要素を抽出するよう動作可能な要素抽出手段と、
前記抽出されたメッシュ要素についてメッシュ要素接続性を使用して、前記組に含めるための更なるメッシュ要素を特定することにより、前記組における前記メッシュ要素の数を所要のレベルに拡張させるよう動作可能な組拡張手段とを備える装置。
【請求項９】
請求項７又は８に記載の装置であって、前記組抽出手段に対する供給のためのメッシュを生成するよう構成されたメッシュ化手段を更に備え、前記メッシュ化手段は、
前記ＣＡＤドメインを複数のサブドメインに分離するよう構成された切断手段と、
各サブドメインについてサブドメイン・メッシュを作成するよう構成されたサブドメイン・メッシュ化手段と、
各サブドメイン・メッシュの内部要素を最適化するよう構成されたサブドメイン・メッシュ最適化手段と、
結果として生じるサブドメイン・メッシュをマージして前記メッシュを形成するよう構成されたメッシュ・マージ手段と
を備える装置。
【請求項１０】
請求項９記載の装置であって、前記サブドメイン・メッシュ化手段は、並列分離メッシュ化プロセスを使用して前記サブメッシュを作成するよう動作可能な装置。
【請求項１１】
請求項９又は１０に記載の装置であって、前記サブドメイン最適化手段は、直列メッシュ要素最適化プロセスを使用して各サブドメイン・メッシュの前記内部要素を最適化するよう動作可能な装置。
【請求項１２】
請求項１１記載の装置であって、前記サブドメイン最適化手段は、別個に、かつ並列に、それぞれのサブメッシュに対して前記メッシュ最適化プロセスを行うよう動作可能である装置。
【請求項１３】
コンピュータ・プログラムであって、前記コンピュータ・プログラムは、コンピュータ上、又はコンピュータのネットワーク上で実行されると、請求項１乃至６の何れか一項に記載の方法を前記コンピュータ又は前記ネットワークに行わせるか、又は、前記コンピュータ又は前記ネットワークを、請求項７乃至１２の何れか一項に記載の装置にするコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータ支援エンジニアリングにおけるメッシュ品質改善に関する。
【背景技術】
【０００２】
コンピュータ支援エンジニアリング（ＣＡＥ）、すなわち、製品の品質を改善するための製品の挙動のモデリング及びシミュレーションの目的でのコンピュータ・ソフトウェアの使用は、製造業においてほぼいたるところで見られるようになっている。ＣＡＥが包含する領域は、限定列挙でないが、応力及び熱解析、流体力学、及び運動学を含む。
【０００３】
一般的なＣＡＥプロセスは、解析されるオブジェクトの幾何モデルを表すコンピュータ支援設計（ＣＡＤ）ファイルで始まる。専門ＣＡＤソフトウェアを使用して作成されるＣＡＤファイルは、まず、メッシュと呼ばれるものを形成する非常に多くの数の要素に幾何形状が区分化（メッシュ化）される前処理ステップを経る。計算メッシュの例は添付図面の図１に示す。境界条件を伴うメッシュは、次いで、解析の結果を計算するために標準的な数値手法を使用する解析器に送出される。
【０００４】
現在利用可能なメッシャ（メッシュ化器）は、２つのカテゴリ（すなわち、直列及び並列）に分けることが可能である。直列メッシャは、１つのプロセッサに接続されたメモリと、１つのプロセッサのみの計算能力に制限される。約１百万の要素を含むメッシュは、作成するために約１ＧＢのメモリを必要とし、メモリが前述のコードに対する厳しい制約であることは明らかである。並列メッシャは、一コンピュータに、又はより多くの場合、ネットワークによって接続されたいくつかのコンピュータにみられるいくつかのプロセッサに作業負荷を分散させることにより、ずっと大きなメッシュをずっと短い時間で作成することができる。メッシュ化中にプロセッサ間で行われる通信の量に応じて、並列メッシュ生成器は更に、３つのカテゴリ（すなわち、密結合、疎結合、及び分離）に分けることが可能である。直列結合又は並列結合の場合、単一のメッシュを作成するために１つ又は複数のプロセッサが動作する。前述のメッシュの品質は一般に、分離のケースよりもよい。しかし、前述のタイプのメッシュ化はスケーラブルでないので、メッシュ化時間は一般に、特に、産業ＣＡＤモデルにおいて存在しているものなどの複雑なモデルの場合、非常に長くなる。（別々の処理パート間の通信又は同期化を必要としない）分離並列メッシャのみが、直列メッシュ化コードの１００％の再利用を実現することが可能であり、真にスケーラブルである。
【０００５】
スケーラビリティは、ドメインを区分化することによって実現され、上記ドメインは、いくつかの独立サブドメインにメッシュ化され、上記独立サブドメインは次いで別個にメッシュ化され、よってメッシュ化時間はずっと短い。前述のスケーラブルな並列分離メッシャは最近、欧州出願第１２１７３４６９．３号（西暦２０１４年１月１６日付けで公表された特開２０１４‐００６９０８号）において提案されている。しかし、不適切な位置においてＣＡＤモデルを切断することにより、ドメイン間のインタフェースにおいて人工的に小さな要素を作成することが考えられる。この場合、メッシュの全体的な品質は一般的に低い。これは特に、切断面が小さなＣＡＤ特徴と交差する場合に可能性が高い。
【０００６】
高品質メッシュの作成は、解析器において費やされる時間を削減し、解決策の精度を増加させることが可能であるので、非常に重要である。メッシュの品質は、単純なラプラシアン平滑化（「四面体メッシュの改善」、カリフォルニア大学バークレイ校電気工学及び計算機科学、西暦２００８年、第２1頁参照）から、メッシュ・ノード及び要素に対する高度な演算手順を行う、ＳＴＥＬＬＡＲ（「ステラー（Ｓｔｅｌｌａｒ）−四面メッシュ改善プログラム）」、ｈｔｔｐ：／／ｗｗｗ．ｃｓ．ｂｅｒｋｅｌｅｙ．ｅｄｕ／〜ｊｒｓ／ｓｔｅｌｌａｒ／＃ａｂｏｕｔを参照されたい）のような高度な最適化ツールに及ぶ専用ツールによって改善することが可能である。高度な最適化ツールの使用は通常、単純なものと比較してずっと高い品質のメッシュをもたらすが、ずっと高価でもある。更に、高品質メッシュ最適化コードは非常に時間がかかる。ＳＴＥＬＬＡＲなどの高品質メッシュ最適化ツールはメッシュ生成よりも最大１０倍の時間を要し得る。これは、前述のコードを日常の本番作業に使用することが可能でないことを意味する。前述の課題を解決する自然なやり方は、現代のコンピュータ及びコンピュータ・クラスタにおいて利用可能なマルチコアＣＰＵを利用することである。しかし、これは現在、可能でない。前述のコードの多く（例えば、ＳＴＥＬＬＡＲ）は性質上、直列であり、並列化することは単純でないからである。
【０００７】
Ｚａｖａｔｔｉｅｒｉ，Ｐ．、Ｄａｒｉ，  Ｅ．、及びＢｕｓｃａｇｌｉａ，Ｇ．による「構造化されていないメッシュ生成における最適化戦略」（西暦１９９６年、エンジニアリングにおける数値手法の国際ジャーナル、３９（１２）、第２０５５乃至２０７１頁）は、構造化されていない３Ｄ有限要素メッシュの最適化方法を開示している。上記文書には、平滑化アルゴリズムを含む全体メッシュ品質を改善するための種々のアルゴリズムが開示されているが、スケーラビリティに対処していない。
【０００８】
「メスキト（Ｍｅｓｑｕｉｔｅ）・メッシュ最適化ツールキット」（サンディア国立研究所、，ｈｔｔｐ：／／ｔｒｉｌｉｎｏｓ．ｓａｎｄｉａ．ｇｏｖ／ｐａｃｋａｇｅｓ／ｍｅｓｑｕｉｔｅ／）と呼ばれるメッシュ最適化ソフトウェアは、並列に平滑化演算を行うが、容易にスケーラブルである訳でない。
【発明の概要】
【発明が解決しようとする課題】
【０００９】
分離され、かつスケーラブルな態様で高品質計算メッシュを生成する方法を提供することが望ましい。
【課題を解決するための手段】
【００１０】
本発明の第１の局面の実施例によれば、コンピュータ支援設計（ＣＡＤ）又はコンピュータ支援エンジニアリング（ＣＡＥ）システムにおいてＣＡＤドメインをメッシュ化するうえで使用する方法を提供し、上記方法は、予め選択されたメッシュ品質メトリックを満たさないメッシュ要素を、先行して生成されたメッシュの内部要素についてメッシュ要素最適化プロセスを経たＣＡＤドメインの先行して生成されたメッシュから抽出することにより、メッシュ要素の組を得る工程と、メッシュ要素の組を接続サブメッシュに分解する工程と、サブメッシュの境界ノードを移動させないという条件下で、別個に、かつ並列に各サブメッシュについて直列メッシュ要素最適化プロセスを行って、最適化されたサブメッシュを得る工程と、最適化されたサブメッシュを、先行して生成されたメッシュに一体化させることにより、ＣＡＤドメインの最適化されたメッシュを得る工程とを含む手順を行う。
【００１１】
本発明を実施する方法は、直列メッシュ最適化コードを使用しながらも、効率的なやり方で並列処理を利用して、既存の方法よりも高速であり、かつ、スケーラブルなやり方で高品質メッシュを作成することができる。
【００１２】
特に、本発明の実施例は、ドメイン間のインタフェースにおいて低品質要素を作成することが可能な分離メッシュ化手法に対する改善を提供することが可能である。更に、並列でないことがあり得るメッシュ最適化コードを使用して、分離並列メッシュ最適化を行う方法を提供することが可能である。
【００１３】
本発明を実施する方法では、メッシュ要素の組を得る工程は、更に、予め選択されたメッシュ品質メトリックを満たさないメッシュ要素を抽出した後、抽出されたメッシュ要素についてメッシュ要素接続性を使用して、組におけるメッシュ要素の数が所要レベルに拡張されるように組に含めるための更なるメッシュ要素を特定する工程を含み得る。
【００１４】
本発明を実施する方法は、ＣＡＤドメインを複数のサブドメインに分離し、各サブドメインについてサブドメイン・メッシュを作成し、各サブドメイン・メッシュの内部要素を最適化し、結果として生じるサブドメイン・メッシュをマージしてメッシュを形成することにより、手順において使用するためのメッシュを、手順を行う前に生成する工程を更に含み得る。サブメッシュは望ましくは、並列分離メッシュ化プロセスを使用して作成し得る。各サブドメイン・メッシュの内部要素は好ましくは、直列メッシュ要素最適化プロセスを使用して最適化される。メッシュ最適化プロセスは望ましくは、別個に、かつ並列にそれぞれのサブメッシュに対して行い得る。
【００１５】
本発明の第２の局面の実施例によれば、コンピュータ支援設計（ＣＡＤ）又はコンピュータ支援エンジニアリング（ＣＡＥ）システムにおいてＣＡＤドメインをメッシュ化するうえで使用する装置を提供し、上記装置は、予め選択されたメッシュ品質メトリックを満たさないメッシュ要素を、先行して生成されたメッシュの内部要素についてメッシュ要素最適化プロセスを経たＣＡＤドメインの先行して生成されたメッシュから抽出することにより、メッシュ要素の組を得るよう構成された組抽出手段と、メッシュ要素の組を接続サブメッシュに分解するよう構成されたサブメッシュ作成手段と、サブメッシュの境界ノードを移動させないという条件下で、別個に、かつ並列に各サブメッシュについて直列メッシュ要素最適化プロセスを行って、最適化されたサブメッシュを得るよう構成されたサブメッシュ最適化手段と、最適化されたサブメッシュを、先行して生成されたメッシュに一体化させることにより、ＣＡＤドメインの最適化されたメッシュを得るよう構成されたメッシュ一体化手段とを備える。
【００１６】
本発明を実施する装置は、直列メッシュ最適化コードを使用しながらも、効率的なやり方で並列処理を利用して、既存の装置よりも高速であり、かつ、スケーラブルなやり方で高品質メッシュを作成することを容易にし、ドメイン間のインタフェースにおいて低品質要素を作成することが可能な分離メッシュ化装置に対する改善を提供することが可能であり、更に、並列でないことがあり得るメッシュ最適化コードを使用して、分離並列メッシュ最適化を行うことが可能である。
【００１７】
本発明を実施する装置では、組抽出手段は、予め選択されたメッシュ品質メトリックを満たさない先行して生成されたメッシュからメッシュ要素を抽出するよう動作可能な要素抽出手段と、抽出されたメッシュ要素についてメッシュ要素接続性を使用して組内に含めるための更なるメッシュ要素を特定することにより、組内のメッシュ要素の数を所要のレベルに拡張するよう動作可能な組拡張手段とを備え得る。
【００１８】
本発明を実施する装置は、組抽出手段に対する供給のためのメッシュを生成するよう構成されたメッシュ化手段を更に備え得、メッシュ化手段は、ＣＡＤドメインを複数のサブドメインに分離するよう構成された切断手段と、各サブドメインについてサブドメイン・メッシュを作成するよう構成されたサブドメイン・メッシュ化手段と、各サブドメイン・メッシュの内部要素を最適化するよう構成されたサブドメイン・メッシュ最適化手段と、結果として生じるサブドメイン・メッシュをマージしてメッシュを形成するよう構成されたメッシュ・マージ手段とを備える。サブドメイン・メッシュ化手段は好ましくは、並列分離メッシュ化プロセスを使用してサブメッシュを作成するよう動作可能である。望ましくは、サブドメイン最適化手段は、直列メッシュ要素最適化プロセスを使用して各サブドメイン・メッシュの内部要素を最適化するよう動作可能であり得る。好ましくは、サブドメイン最適化手段は、別個に、かつ並列に、それぞれのサブメッシュに対してメッシュ最適化プロセスを行うよう動作可能である。
【００１９】
本発明の第３の局面の実施例によれば、コンピュータ上、又はコンピュータのネットワーク上で実行されると、上記コンピュータ又は上記ネットワークに本発明の第１の局面を実施する方法を行わせるか、又は、上記コンピュータ又は上記ネットワークを本発明の第２の局面を実施する装置とするコンピュータ・プログラムが提供される。
【００２０】
次に、例として、添付図面を参照する。
【図面の簡単な説明】
【００２１】
【図１】３Ｄ計算メッシュの例を示す図である。
【図２】本発明を実施するメッシュ化装置を使用することが可能なＣＡＤシステムの例を示す図である。
【図３】本発明を実施するメッシュ化装置を示す図である。
【図４】本発明の実施例において使用する分離メッシュ化及び内部最適化モジュールを示す図である。
【図５】本発明の実施例において使用する分離インタフェース最適化モジュールを示す図である。
【図６】本発明において使用するＣＡＤ切断モジュールを示す図である。
【図７】本発明において使用するＣＡＤメッシュ化プロセスを示すフローチャートである。
【図８】本発明において使用する並列分離メッシュ最適化プロセスを示すフローチャートである。
【図９】本発明において使用するメッシュ・マージ・プロセスを示すフローチャートである。
【図１０】本発明において使用する低品質要素抽出プロセスを示すフローチャートである。
【図１１】拡張された要素の組を得るためのプロセスを示すフローチャートである。
【図１２】低品質要素の最適化を容易にする要素の組の拡張の例を示す図である。
【図１３】種々の拡張レベル間のメッシュ品質最適化後における変動を示す図である。
【図１４】拡張された要素の組を、接続サブメッシュに分解するプロセスを示すフローチャートである。
【図１５】サブメッシュの分離並列最適化を行うプロセスを示すフローチャートである。
【図１６】初期メッシュに最適化サブメッシュを一体化させるプロセスを示すフローチャートである。
【図１７】先行して提案されている分離並列メッシュ化システムを使用したメッシュ最適化を示す図である。
【図１８Ａ】本発明を実施するメッシュ化システムを使用したメッシュ最適化を示す図である。
【図１８Ｂ】本発明を実施するメッシュ化システムを使用したメッシュ最適化を示す図である。
【発明を実施するための形態】
【００２２】
[実施例]
図２は、市販のＣＡＤエンジン、市販のメッシャ、及び市販の最適化器を備えるＣＡＤシステムにおいて利用することが可能である。
【００２３】
ＣＡＤエンジンによってサポートされたデータ形式においてＣＡＤモデルが記憶されているとすれば、本発明の実施例は以下の既存の構成部分を使用する。
【００２４】
ＣＡＤモデルを考慮すれば、初期の（元の）３Ｄ計算メッシュを作成することができるメッシュ化コード。
【００２５】
ＣＡＤファイルから読み出すことが可能であり、ＣＡＤファイルに対する修正を行うことが可能なＣＡＤエンジン（ＣＡＤカーネルとも呼ばれる）。
【００２６】
メッシュ・ファイルを読み出し、当該技術分野において知られている最適化手法を適用した後、初期の３Ｄの（元の）計算メッシュよりも良好な品質を有するメッシュを出力する。
【００２７】
従来技術に対する改善を提供するために必須でないが、例えば欧州特許出願第１２１７３４６９．３号において提案されているものなどの、分離並列メッシュ化システムを使用して初期メッシュを生成することが望ましい。初期メッシュを生成するために、欧州特許出願第１２１７３４６９．３号の分離並列メッシュ化システムを使用する本発明の実施例を以下に説明する。
【００２８】
アセンブリ・モデルは、互いに物理的に接触していてもいなくてもよい複数のソリッドを含むＣＡＤモデルである。本出願を通して、パートという語は、アセンブリ・モデルの単一のソリッド構成部分の意味を有する。首尾一貫性のために、入力ＣＡＤファイルが単一のソリッドを含む場合、一パートを有するアセンブリとしてこれを表す。ソリッドは、いくつかのセクションに分離／区分化し得る。２Ｄメッシュ化演算は、三角形や四角形などの２Ｄ要素による、ソリッドの面の離散化である。３Ｄメッシュ化演算は、四面体や六面体などの３Ｄ要素による、ソリッドのボリューム全体の離散化である。メッシュ・マージ演算は、パートの個々のセクションの３Ｄメッシュの、前述のパートの１つのコヒーレントな３Ｄメッシュへの結合である。コヒーレントなメッシュは、セクション間のインタフェース上の重複ノードがない単一の接続メッシュ１つとして定義される。メッシュ・アセンブリ演算は、１つ又は複数の個々のパートのメッシュの、アセンブリ・モデルの１つの単一のメッシュへの集約である。メッシュ・アセンブリとメッシュ・マージとの間の差は、アセンブルされたメッシュは、１つの単一の接続メッシュにならないという点である。すなわち、２つのパートのメッシュが物理的に接触していても、インタフェースは、２つのノード及び要素の組を含み、メッシュ毎に１つの組を含む。より公式的には、２つ以上のパートのメッシュに属するノードを有するアセンブルされたメッシュにおいて要素は存在しない。
【００２９】
図３に示すように、提案されたシステムの実施例は、２つのモジュールと、分離されたメッシュ化及び内部最適化モジュール１００（メッシュ化手段）と、分離インタフェース最適化モジュール２００とを備える。
【００３０】
図４に示すように、更に詳細に以下に説明する分離メッシュ化及び内部最適化モジュール１００は、ＣＡＤ切断装置１１０，メッシュ化装置１２０、メッシュ最適化装置１３０、及びメッシュ・マージ装置１４０を備える。分離メッシュ化及び内部最適化モジュール１００は、メッシュ最適化プロセスで、欧州特許出願第１２１７３４６９．３号に開示されたものなどの、分離メッシュ化プロセスを増強するよう動作可能である。メッシュ最適化プロセスは、各メッシュ・セクション内の要素の品質が好適になるということを保証する。高度なメッシュ最適化は、一般に非常に高価である一方、各メッシュ・セクションに別個に、かつ並列に適用されるということは、プロセスのスケーラビリティを保証する。メッシュ最適化プロセスが、図４に示すようにメッシュ化セクションそれぞれに対して並列に行われることは必須でないが、これは効果的である。
【００３１】
分離メッシュ化及び内部最適化モジュール１００の出力は、部分的に最適化されたメッシュであり、大多数の要素は良好な品質を有する。しかし、上述のように、一般に、メッシュ・セクション間のインタフェースにおいて低品質要素が存在する。
【００３２】
メッシュ最適化装置１３０によって行われるプロセスは、劣悪な品質の要素を有する領域が分離されることを保証し、よって、前述の要素は、並列最適化のために容易にかつ自然に分離することが可能である。
【００３３】
図５に示すように、以下に更に詳細に説明する分離インタフェース最適化モジュール２００は要素抽出装置２１０と、組拡張装置２２０と、サブメッシュ作成装置２３０と、サブメッシュ最適化装置２４０と、メッシュ一体化装置２５０とを備える。分離インタフェース最適化モジュール２００は、やはり効率的であり、かつスケーラブルなやり方で、残りの低品質要素を除外するために分離メッシュ化及び内部最適化モジュール１００から出力された部分的に最適化されたメッシュ出力に対して最適化プロセスを行うよう動作可能である。最適化プロセスは、低品質要素の組の抽出で始まる。前述の組は、初期メッシュ（元のメッシュ）のサブメッシュを形成する。メッシュ・セクションが互いに貼り付けられた領域にのみ低品質要素が現れ得るように初期メッシュが作成され、よって、この組における要素の数は初期メッシュにおける要素の数よりもずっと小さい。これに続き、要素接続性情報を用いて、メッシュ最適化ソフトウェアに利用可能なデータの量を増加させる目的で、前述の組を特定の回数、拡張する。拡張された組は次いで、メッシュ最適化ソフトウェアを使用して、並列分離されたやり方で、最適化された別個の接続構成部分（元のメッシュのサブメッシュと呼ばれる）いくつかに分解される。最後に、最適化されたサブメッシュは初期メッシュに一体化され、これは、低品質要素なしで高品質メッシュをもたらす。
【００３４】
図５に表すように、分離インタフェース最適化モジュール２００の入力は、部分最適化メッシュである。前述のメッシュは、次に更に詳細に説明する、図４に示すような分離並列メッシュ化システムを使用して分離メッシュ化及び内部最適化モジュール１００によって生成し得る。
【００３５】
図４のＣＡＤ切断装置１１０は、市販のＣＡＤカーネルを使用して１つのＣＡＤソリッドを複数のＣＡＤソリッドに区分化する。切断を行うやり方の１つはグリッドに整合させたやり方であり、ＣＡＤモデルが、座標軸に平行した平面を介してスライスされる。スライシングは、ＣＡＤカーネルに存在するブーリアン演算（例えば、ＯｐｅｎＣＡＳＣＡＤＥ  ＣＡＤカーネルの場合におけるＣＵＴ演算）を使用して行うことが可能である。しかし、スライシングを行うことが可能な別々のやり方がいくつか存在している。一例を図６に示す。
【００３６】
メッシュ化装置１２０（サブドメインメッシュ化手段）は、市販のメッシャを使用して、３Ｄメッシュを各ＣＡＤセクションから生成する。メッシュ化プロセスは、図７のフローチャートに示すように欧州特許出願第１２１７３４６９．３号に記載された手法を使用し得る。この場合、並列のＣＡＤセクション毎に、市販の直列メッシャを使用して、表面メッシュを作成する（ステップ１）。これに続き、隣接セクション間のインタフェースにおいてみられるメッシュのゾーンが識別され、メッシュ情報が交換される（ステップ２）。情報を交換する１つのやり方は単に、（ソースとしてセットされる）一方のセクションから（デスティネーションとしてセットされる）他方のセクションにメッシュ・データを複製する。表面メッシュが修正された後、修正された表面メッシュの内部が３Ｄにおいてメッシュ化され、よって、ＣＡＤセクション毎に３Ｄボリューム・メッシュを作成する（ステップ３）。
【００３７】
図８のフローチャートに示すように、メッシュ最適化装置１３０（サブドメイン・メッシュ最適化手段）は、セクション間のインタフェース上のメッシュが変えられないようなやり方で、ＳＴＥＬＬＡＲなどの市販の直列最適化ソフトウェアを使用してメッシュ・セクション毎にメッシュ最適化プロセスを行う（ステップ４）。
【００３８】
図９のフローチャートに示すように、メッシュ・マージ装置１４０は、ＣＡＤソリッド全体について１つのメッシュにメッシュ・セクションを結合するようメッシュ・マージ・プロセスを行う。これは、インタフェース上のメッシュが同一であるようにメッシュ・セクションが修正されているので、効率的に行うことが可能である。そういうものとして、重複ノードを除去し、結果として生じるメッシュの番号を再設定することに演算が縮減される。
【００３９】
メッシュ・セクションは全て、完全に最適化されているが、結合されたメッシュは部分的に最適化されているに過ぎない。隣接セクション間のインタフェースにおいて低品質要素が作成されていることが考えられるからである。前述の部分的に最適化されたメッシュは、次に説明するような分離インタフェース最適化モジュール２００によって処理される。
【００４０】
図１０のフローチャートにおいて示すように、入力としての図９の部分最適化メッシュで始めて、品質メトリックが、メッシュ内の要素毎の要素抽出装置２１０によって計算される（ステップ６）。四面体要素のメッシュ品質メトリックの一例は、四面体の最小二面角のｓｉｎｅ（最小ｓｉｎｅ尺度）である。バイアス最小ｓｉｎｅ尺度、体積・長さの尺度、半径比等などの要素の品質を測定する他の多くの方法が存在している。メトリックが要素毎に計算された後、品質が、設定された閾値未満である要素のみが抽出のために選択される（ステップ７）。最小ｓｉｎｅ品質メトリックを使用する場合の閾値の一例は１０度である。選択された要素のＩＤは、要素品質尺度を使用して、部分的に最適化されたメッシュから分離されている低品質要素の組を形成する。
【００４１】
最適化された領域をもう一度、ソリッド・メッシュに効率的に挿入することができるために、境界に接触しない状態を保つことが必要である。しかし、前述の制約を備えた比較的少数の要素（低品質要素の組についてもあてはまる）は、最適以下の結果につながり得る。メッシュ最適化ソフトウェアは、動作するために十分な自由度を十分有していないからである。この理由で、サブメッシュ最適化装置２４０に送出される対象のサブメッシュは、隣接要素を含めるよう組拡張装置２２０によって拡張され、境界を修正しないための条件が前述のより大きな組に適用される。図１１のフローチャートは、組拡張装置２２０の動作を示し、組拡張プロセスの例を図１２に示す。まず、要素接続性情報が部分最適化メッシュから抽出される（ステップ８）。次いで、組拡張プロセスがＮ回、行われているか否かを判定するために検査が行われる（ステップ９）。「はい」の場合、拡張された要素が完了する。さもなければ、拡張された要素の組内に現在ある要素全てについて（ステップ１０）、接続性情報に応じた隣接要素のリストが得られ（ステップ１１）、拡張された要素の組に既にある訳でない隣接要素が前述の組に追加される（ステップ１２）。前述のプロセスは、図１３に示すように、最適化の品質を改善するためにＮ回（通常、Ｎ＝２又は３）繰り返される。
【００４２】
次の段階は、サブメッシュ作成装置２３０による、接続サブメッシュへの要素の組の分解である。低品質要素はこの場合、隣接セクション間のインタフェースにおいてのみ存在し得、前述が、別個のいくつかのサブ領域にグループ化される確率は高い。図１４のフローチャートに示すように、前述の別個の接続領域は、要素接続性情報を使用して見つけられ、接続要素のそれぞれの組として特定される（ステップ１３）。前述の組が特定された後、サブメッシュが各組から作成される（ステップ１４）。サブメッシュ・サイズは、規定された閾値を超えた場合、メッシュ区分化アルゴリズムを使用して更なるサブメッシュに区分化し得る。
【００４３】
図１５のフローチャートに示すように、メッシュ最適化装置１３０の動作と同様に、接続サブメッシュはそれぞれ、次いで、好ましくは、ステップ４で使用された同じ市販の最適化ソフトウェアを使用して、サブメッシュ最適化装置２４０によって別個に最適化される（ステップ１５）。全体的に、これは、直列メッシュ最適化ソフトウェアが使用されても、分離並列最適化となる。最適化ソフトウェアに課される唯一の制約は、サブメッシュそれぞれの境界上のメッシュを修正すべきでなく、よって、結果として生じる最適化された複数のサブメッシュを初期の（元の）メッシュにマージすることが考えられる。
【００４４】
図１６に示すプロセスの最後の段階は、メッシュ一体化装置２５０が、別個に最適化されたサブメッシュをもう一度、初期メッシュに一体化させるためである（ステップ１６及び１７）。境界領域が修正されていないので、境界ノードのマッチングは効率的に行うことが可能である。
【００４５】
従来技術に対する本発明の実施例の利点を次いで、比較例を参照して説明する。説明した実施例、及び比較例は何れも、欧州特許出願第１２１７３４６９．３号に開示された分離並列メッシュ化システムを使用する。
【００４６】
比較例では、ＣＡＤモデルはセクションに区分され、前述のセクションは次いで、並列にメッシュ化される。出力メッシュは次いで、全て、単一のメッシュにもう一度、マージされ、これは、劣悪な要素を全て除去するよう後に最適化される。メッシュ最適化は、現在入手可能な最善のメッシュ最適化プログラムの１つであるＳＴＥＬＬＡＲソフトウェアを使用して行われる。しかし、大半の高性能最適化ソフトウェアと同様に、ＳＴＥＬＬＡＲは直列でのみ、実行することが可能である。
【００４７】
図１７は、ＣＡＤモデルが３つのセクションに区分化された前述の手順のケース・スタディを示す。モデルの合計メッシュ化時間は２９．８１９ｓであった。例証のために、区分内のボリュームが等しくなるようにＣＡＤモデルが区分化されると仮定する。前述の仮定で、モデルのメッシュ化時間は、９．９４０ｓ（１／３＊  完全なモデルのメッシュ化時間）とみなし得る。合計最適化時間は６１．６５０ｓであった。よって、メッシュ化及び最適化の合計時間は７１．５９０ｓ（９．９４０ｓ＋６１．６５０ｓ）である。
【００４８】
対照的に、本発明の実施例では、欧州特許出願第１２１７３４６９．３号に開示された分離メッシュ化プロセスを、初期メッシュ・マージ段階の前に最適化ステップと組み合わせ、低品質要素が「切断インタフェース」において導入されている場合に更なる最適化段階が次いで行われる。図１８は、初期メッシュ（元のメッシュ）にもう一度、前述の低品質要素を分離し、最適化し、マージする更なる最適化段階を示す。前述の実施例は更に、メッシュ最適化のためにＳＴＥＬＬＡＲを利用する。しかし、本発明を使用する方法を使用して、メッシュ最適化を分離された態様で並列に実行することが可能である。これは、性能の向上につながる。
【００４９】
本発明の前述の実施例では、メッシュ化及び最適化時間は以下の通りであった。
【００５０】
メッシュ生成：  ９．９４０ｓ
分離メッシュ最適化：  ２０．５５０ｓ  （１／３  ＊  ６１．６５０ｓ）
インタフェースにおける低品質要素のメッシュ最適化：  ６．９５８ｓ（並列において最適化されたセクション全てにわたる最適化の最大時間）
メッシュ生成時間は９．９４０ｓで同じ状態に留まる。分離メッシュ最適化の場合、メッシュ・マージング前にこれが行われるので、完全なメッシュの最適化に要した時間の１／３の時間を要するとみなし得る（メッシュが３つのパートに分離され、並列に最適化されるからである）。更に、インタフェースにおける低品質要素の最適化時間は、並列に最適化されている低品質要素領域全てにわたって最大になる。図１８Ａ及び図１８Ｂに表すように、プロセッサ２において最適化されている低品質要素の組は、最適化時間が、６．２８２ｓであったプロセッサ１の最適化時間よりも大きい６．９５８ｓであった。したがって、切断インタフェースにおける低品質要素の最適化の合計時間が６．９５８ｓであるとみなす。
【００５１】
本発明の実施例を使用したメッシュ化及び最適化の合計時間は３７．４４８ｓであった。これを比較例における処理時間７１．５９０ｓと比較すれば、提案しているシステムがメッシュ最適化の合計時間において４７．６９１％の削減となっている。
【００５２】
よって、本発明の実施例は、使用された最適化ソフトウェアが並列でなくても、分離され、並列なやり方で、よりすばやく高品質メッシュを生成することが可能である。
【００５３】
本発明の実施例は、１つ又は複数のプロセッサ上で実行するソフトウェア・モジュールとして、ハードウェアにおいて、又は前述の組み合わせで実現し得る。すなわち、マイクロプロセッサ又はディジタル信号プロセッサ（ＤＳＰ）は、実際には、上記機能の一部又は全部を実現するために使用し得るということを当業者は認識するであろう。
【００５４】
本発明は、更に、本明細書及び特許請求の範囲記載の方法の一部又は全部を行うために１つ又は複数のデバイス又は装置のプログラム（例えば、コンピュータのプログラム、及びコンピュータ・プログラム・プロダクト）として実施し得る。本発明を実施する前述のプログラムはコンピュータ読み取り可能な媒体上に記憶し得るか、又は、例えば、１つ又は複数の信号の形式を有し得る。前述の信号は、インターネット・ウェブサイトからダウンロード可能であるか、キャリア信号上で供給されるか、又は、何れかの他の形式を有するデータ信号であり得る。
【符号の説明】
【００５５】
１００  メッシュ化手段
【図１】
2015149052.tif 000003
【図２】
2015149052.tif 000004
【図３】
2015149052.tif 000005
【図４】
2015149052.tif 000006
【図５】
2015149052.tif 000007
【図６】
2015149052.tif 000008
【図７】
2015149052.tif 000009
【図８】
2015149052.tif 000010
【図９】
2015149052.tif 000011
【図１０】
2015149052.tif 000012
【図１１】
2015149052.tif 000013
【図１２】
2015149052.tif 000014
【図１３】
2015149052.tif 000015
【図１４】
2015149052.tif 000016
【図１５】
2015149052.tif 000017
【図１６】
2015149052.tif 000018
【図１７】
2015149052.tif 000019
【図１８Ａ】
2015149052.tif 000020
【図１８Ｂ】
2015149052.tif 000021