明細書 :四面体メッシュ生成方法およびプログラム

発行国	日本国特許庁(JP)
公報種別	特許公報(B2)
特許番号	特許第4714444号 (P4714444)
公開番号	特開2006-072490 (P2006-072490A)
登録日	平成23年4月1日(2011.4.1)
発行日	平成23年6月29日(2011.6.29)
公開日	平成18年3月16日(2006.3.16)
発明の名称または考案の名称	四面体メッシュ生成方法およびプログラム
国際特許分類	G06F  17/50        (2006.01)
ＦＩ	G06F 17/50 612J
請求項の数または発明の数	9
全頁数	15
出願番号	特願2004-252444 (P2004-252444)
出願日	平成16年8月31日(2004.8.31)
新規性喪失の例外の表示	特許法第３０条第１項適用 平成１６年３月１日 社団法人精密工学会発行の「２００４年度精密工学会春季大会 学術講演会講演論文集」に発表
審査請求日	平成19年3月29日(2007.3.29)
特許権者または実用新案権者	【識別番号】504173471 【氏名又は名称】国立大学法人北海道大学 【識別番号】000005108 【氏名又は名称】株式会社日立製作所
発明者または考案者	【氏名】金井 理 【氏名】伊達 宏昭 【氏名】岸浪 建史 【氏名】西垣 一朗
個別代理人の代理人	【識別番号】100098017、【弁理士】、【氏名又は名称】吉岡 宏嗣 【識別番号】100066979、【弁理士】、【氏名又は名称】鵜沼 辰之
審査官	【審査官】加舎 理紅子
参考文献・文献	特開２００３－３４５８３７（ＪＰ，Ａ） 特開平１１－０９６３９９（ＪＰ，Ａ） 特開２００５－２４２６４７（ＪＰ，Ａ） 特開２００５－２４２６５１（ＪＰ，Ａ） 伊達宏昭 他，細分化と簡略化に基づくメッシュ品質向上手法，２００３年度精密工学会北海道支部学術講演会講演論文集，２００３年 ９月 ６日，ｐ．４１－４２ 伊達宏昭 他，有限要素解析用多重解像度メッシュ生成に関する研究－高密度四面体メッシュからの解析用メッシュ生成－，第６６回（平成１６年）全国大会講演論文集（４），２００４年 ３月 ９日，ｐ．４－５９～４－６０ Oliver G. Staadt,Markus H. Gross，Progressive Tetrahedralizations，Proceedings of the IEEE Visualization 98，１９９８年１０月２４日，p.397-402
調査した分野	Ｇ０６Ｆ １７／５０ ＣｉＮｉｉ ＪＳＴＰｌｕｓ（ＪＤｒｅａｍＩＩ）
特許請求の範囲	【請求項1】 物品の表面に生成された三角形メッシュのデータをコンピュータに取り込み、該コンピュータにより、表面三角形メッシュに基づいて四面体メッシュを逐次生成する第１ステップと、第１ステップで生成された四面体メッシュのデータを取り込み、四面体メッシュを分割して細分化する第２ステップと、第２ステップで生成された四面体メッシュのデータを取り込み、四面体メッシュの数を減らして簡略化する第３ステップとを含んでなり、 第１ステップは、前記表面三角形メッシュの頂点が少なくとも凹んでいない凸頂点を抽出し、該抽出した凸頂点に隣接する他の複数の頂点で囲まれる多角形を複数の三角形に分割し、該分割された各三角形と前記凸頂点を接続して四面体メッシュを逐次生成し、 第２ステップは、第１ステップで生成された四面体メッシュの稜線長が予め定められた閾値以上の稜線を少なくとも２つに分割し、該稜線に接続された四面体メッシュを該稜線の分割点によって分割して細分化し、 第３ステップは、第２ステップで生成された四面体メッシュを構成する稜線の両端の頂点を１つに統合するための新頂点を算出するステップと、該ステップにより算出された前記新頂点に基づいて前記四面体メッシュの数を減らして簡略化するステップとを含んでなる四面体メッシュ生成方法。 【請求項2】 第２ステップは、前記閾値以上の稜線を、当該稜線の中点によって分割することを特徴とする請求項１に記載の四面体メッシュ生成方法。 【請求項3】 前記新頂点算出ステップは、前記稜線の中点を前記新頂点として算出することを特徴とする請求項１に記載の四面体メッシュ生成方法。 【請求項4】 前記新頂点算出ステップは、前記稜線の一方の頂点が表面メッシュ上に在るとき、当該一方の頂点を前記新頂点として算出することを特徴とする請求項１に記載の四面体メッシュ生成方法。 【請求項5】 前記新頂点算出ステップは、前記稜線が表面メッシュ上に在るとき、該稜線に接続する表面メッシュ上の面分との自乗距離を最小化する頂点位置を前記新頂点として算出することを特徴とする請求項１に記載の四面体メッシュ生成方法。 【請求項6】 第３ステップは、前記新頂点算出ステップにより算出された前記新頂点に接続する稜線について、前記簡略化ステップを適用することが有効か否か判定して有効稜線を抽出するステップを有し、 該有効稜線抽出ステップは、前記簡略化ステップを適用した場合に、形状近似誤差が予め定められた閾値以下であること、表面三角形メッシュの裏返りおよび四面体要素の干渉を回避できること、および非多様体表面メッシュを回避できることの少なくとも１つの判定条件を満たす稜線を有効稜線として抽出することを特徴とする請求項３乃至５のいずれか１項に記載の四面体メッシュ生成方法。 【請求項7】 第３ステップは、前記有効稜線抽出ステップにより抽出された有効稜線について、前記簡略化ステップを適用することによりメッシュ品質を評価するステップを有し、 該品質評価ステップは、前記有効稜線について、前記簡略化ステップを適用した場合に生成される四面体要素形状のストレッチ、前記簡略化ステップを適用した場合に前後で変化する要素集合の品質勾配による品質改善度、および該品質改善度を最短稜線長の平均値で重み付けした稜線の評価値の少なくとも１つで評価し、 前記簡略化ステップは、前記品質評価ステップの品質評価値が高い前記有効稜線から順に前記簡略化を実行することを特徴とする請求項６に記載の四面体メッシュ生成方法。 【請求項8】 前記簡略化ステップは、簡略化後の四面体メッシュの目標要素数に係るパラメータを入力する操作画面を表示画面に表示し、該操作画面から入力された目標要素数に係るパラメータを満たすように四面体メッシュの簡略化処理を実行することを特徴とする請求項６または７に記載の四面体メッシュ生成方法。 【請求項9】 請求項１乃至８のいずれか１項に記載の四面体メッシュ生成方法をコンピュータにより実行可能に記述してなる四面体メッシュ生成プログラム。
発明の詳細な説明	【技術分野】 【0001】 本発明は、有限要素解析に用いられる四面体メッシュ生成方法およびプログラムに係り、具体的には、コンピュータを用いて低品質の三角形メッシュから高品質の四面体メッシュを生成する技術に関する。 【背景技術】 【0002】 物品の強度や熱変形等の物理的な性質を有限要素法により解析する際、その物品を例えばコンピュータグラフィックス（ＣＧ）化したソリッドモデルを、細かい面分要素（メッシュ）の集合として表現したメッシュモデルが用いられる。特に、有限要素法解析においては、高品質メッシュ生成がＣＡＥ（ＦＥＡ）の効率化に要求される。 【0003】 従来、ソリッドモデルのメッシュ生成には、ＦＥＭメッシャ、ＣＡＤやＣＧモデラのテセレータが代表的である。ＦＥＭメッシャは、比較的高品質な表面三角形メッシュ（表面メッシュモデル）や四面体メッシュ（ボリュームメッシュモデル）を生成可能である。しかし、ＦＥＭメッシャは、処理が低速で、複雑な形状に対しては処理が不安定であり、経験や知識を要するマニュアル操作が必要となる場合が多い。 【0004】 一方、ＣＡＤやＣＧのテセレータは、高速かつ確実に表面三角形メッシュを生成できるが、要素歪や要素サイズの不均一度などの品質が低い。 【0005】 また、従来のメッシュモデルの生成法としては、例えば、非特許文献１～５に開示されたものが知られている。 【0006】 【非特許文献1】Luebke Reddy, Cohen Varshney and Watson Huebner: LEVEL of DET AIL FOR 3D GRAPHICS, Morgan Kaufman, 2003 【非特許文献2】E. Bechet, J.C. Cuilliere and F. Trochu: Generation of a finite element MESH from stereolithography (STL) files，Computer Aided Design, 34, pp. 1-17, 2002 【非特許文献3】A. LEE, Sweldents, P. Schroder, L Cowsar, and D. Dobkin. Maps: Multiresolution adaptive parameterization of surfaces Computer Graphics (SIGGRAPH ’98 Proceedings)，pp. 95-104, 1998 【非特許文献4】M. Garland and P. S. Heckbert: Surface Simplification Using Quadric Error Metrics, proc. Of SIGRAPH 97, pp. 209-216, 1997 【非特許文献5】H．Hoppe: Progressive Meshes, Computer Graphics (SIGGRAPH ’96), pp. 98-108, 1996 【発明の開示】 【発明が解決しようとする課題】 【0007】 しかしながら、従来技術においては、高品質の四面体メッシュを生成する処理速度を高速化すること、および複雑な形状に対しても安定な処理を実現することについては改善の余地がある。ここで、高品質なメッシュとは、メッシュの歪が小さく、かつメッシュサイズの均一度が高いものをいう。他方、メッシュ生成処理が不安定な場合は、所望の品質を有するメッシュを得ることができなかったり、処理時間が長くなるなどの問題につながる。 【0008】 本発明の課題は、高品質の四面体メッシュ生成処理を高速化でき、かつ複雑な形状に対しても安定な処理を実現することにある。 【課題を解決するための手段】 【0009】 上記課題を解決するため、本発明の四面体メッシュ生成方法は、物品の表面に生成された三角形メッシュデータをコンピュータに取り込み、該コンピュータを用いて、表面三角形メッシュに基づいて四面体メッシュを逐次生成する第１ステップと、第１ステップで生成された四面体メッシュのデータを取り込み、四面体メッシュを分割して細分化する第２ステップと、第２ステップで生成された四面体メッシュのデータを取り込み、四面体メッシュの数を減らして簡略化する第３ステップとを実行することを特徴とする。 【0010】 すなわち、本発明は、高密度メッシュの位相操作の自由度の高さに注目し、メッシュ品質は第３ステップの四面体メッシュの簡略化処理で考慮することにした。その結果、第１および第２のステップでは、品質を考慮することなく、低品質の三角形メッシュから四面体メッシュを生成した後、四面体メッシュを細分化して高密度化することができる。したがって、単純な手法で高密度化できる。次いで、高密度化した四面体メッシュの操作の自由度を利用して、品質を考慮しながら四面体メッシュの数を減らして簡略化することにより、所望のメッシュサイズを有する高品質の四面体メッシュを生成することができる。また、メッシュの数（要素数）の制御が容易である。さらに、メッシュ簡略化の結果、四面体メッシュの多重解像度表現が生成でき、様々なアプリケーションでの効率的なメッシュ利用が可能となる。 【0011】 ここで、第１ステップは、前記表面三角形メッシュの頂点が少なくとも凹んでいない凸頂点を抽出し、該抽出した凸頂点に隣接する他の複数の頂点で囲まれる多角形を複数の三角形に分割し、該分割された各三角形と前記凸頂点を接続して四面体メッシュを逐次生成することができる。つまり、表面三角形メッシュ形状は、物品の形状に起因して突出したり凹んだりしている。しかし、四面体メッシュを生成するのは物品の内部であるから、表面三角形メッシュ形状の凸部分または比較的平坦な部分から四面体メッシュを生成するため、表面三角形メッシュの頂点が少なくとも凹んでいない凸頂点を要件とする。 【0012】 また、第２ステップは、各四面体メッシュの稜線長が予め定められた閾値以上の稜線を少なくとも２つに分割し、該稜線に接続された四面体メッシュを該稜線の分割点によって分割して細分化することができる。この場合において、前記閾値以上の稜線を、当該稜線の中点によって分割することにより、高密度化処理を単純化して高速化できる。 【0013】 また、第３ステップは、第２ステップで生成された高密度の四面体メッシュを構成する稜線の両端の頂点を１つに統合するための新頂点を算出するステップと、該ステップにより算出された前記新頂点に基づいて前記四面体メッシュの数を減らして簡略化するステップとを含んで構成することができる。この場合、新頂点算出ステップは、前記稜線の中点を前記新頂点として算出すること、前記稜線の一方の頂点が表面メッシュ上に在るとき、当該一方の頂点を前記新頂点として算出すること、あるいは前記稜線が表面メッシュ上に在るとき、該稜線に接続する表面メッシュ上の面分との自乗距離を最小化する頂点位置を前記新頂点として算出することを適宜採用することができる。 【0014】 また、第３ステップは、前記新頂点算出ステップにより算出された前記新頂点に接続する稜線について、前記簡略化ステップを適用することが有効か否か判定して有効稜線を抽出するステップを有し、該有効稜線抽出ステップは、前記簡略化ステップを適用した場合に、形状近似誤差が予め定められた閾値以下であること、表面三角形メッシュの裏返りおよび四面体要素の干渉を回避できること、および非多様体表面メッシュを回避できることの少なくとも１つの判定条件を満たす稜線を有効稜線として抽出することができる。 【0015】 さらに、第３ステップは、前記有効稜線抽出ステップにより抽出された有効稜線について、前記簡略化ステップを適用することによりメッシュ品質を評価するステップを有し、該品質評価ステップは、前記有効稜線について、前記簡略化ステップを適用した場合に生成される四面体要素形状のストレッチ、前記簡略化ステップを適用した場合に前後で変化する要素集合の品質勾配による品質改善度、および該品質改善度を最短稜線長の平均値で重み付けした稜線の評価値の少なくとも１つで評価し、前記簡略化ステップは、前記品質評価ステップの品質評価値が高い前記有効稜線から順に前記簡略化を実行する構成とすることができる。 【0016】 また、本発明の四面体メッシュ生成プログラムは、上記の四面体メッシュ生成方法をコンピュータにより実行可能に記述して形成できる。 【発明の効果】 【0017】 上述したように、本発明によれば、高品質の四面体メッシュ生成処理を高速化でき、かつ複雑な形状に対しても安定な処理を実現することができる。 【発明を実施するための最良の形態】 【0018】 以下、本発明を実施形態に基づいて説明する。図１に、本発明の一実施の形態の高品質四面体メッシュ生成方法の基本フローチャートを示す。図２に、本発明の四面体メッシュ生成方法の概念図を示す。 【0019】 図２の三次元グラフに示すように、本発明は、要素数が少ない低品質の三角形メッシュから四面体メッシュを生成して細分化して、品質は低いが操作の自由度が高い高密度メッシュを一旦生成した後、その高密度メッシュを簡略化して要素数が少なく、かつ高品質の四面体メッシュを生成することを特徴とする。 【0020】 具体的には、図１のフローチャートに示すように、まず、ＣＡＤテセレータなどにより物品の表面に生成された低品質の表面三角形メッシュのデータを取り込む（Ｓ１）。次いで、取り込んだ表面三角形メッシュのデータに基づいて四面体メッシュを逐次生成し（Ｓ２）、その生成された四面体メッシュを分割して細分化する（Ｓ３）。最後に、細分化された高密度の四面体メッシュを簡略化して、所望の要素サイズ、所望の高品質および所望の要素数を有する四面体メッシュを生成する（Ｓ４）。 【0021】 ここで、ステップ４の簡略化処理は、各四面体メッシュを構成する稜線の両端の頂点を１つの新頂点に統合することにより簡略化する処理であり、いわゆるＥＣ（Edge Collapse）として知られている手法を用い、後述するように品質を考慮しながら簡略化する。また、図１の各ステップの処理は、コンピュータおよびコンピュータを駆動するプログラムにより実現できる。また、必要に応じて、物品の三角形メッシュのデータおよび生成された四面体メッシュのデータを格納する記憶装置が設けられる。 【0022】 したがって、図１に示したステップＳ１～Ｓ４の処理を有する本実施形態によれば、高品質の四面体メッシュの生成処理を高速化でき、かつ複雑な形状に対しても安定な処理を実現することができる。すなわち、メッシュ品質はステップＳ４の四面体メッシュの簡略化処理で考慮することにし、ステップＳ２、Ｓ３では、品質を考慮することなく、低品質の三角形メッシュから四面体メッシュを生成した後、四面体メッシュを細分化して高密度化する。これらの処理は、単純な手法であるから高速に実行できる。このようにして生成された高密度化した四面体メッシュの操作の自由度の高さを利用して、ステップＳ４において、品質を考慮しながら高密度の四面体メッシュを簡略化して、所望のメッシュサイズおよび高品質の四面体メッシュを生成する。これにより、高品質の四面体メッシュを高速で生成することができる。 【0023】 また、本実施形態によれば、メッシュの要素数を容易に制御できる。さらに、メッシュ簡略化の結果、四面体メッシュの多重解像度表現が生成でき、様々なアプリケーションでの効率的なメッシュ利用が可能となる。 【0024】 以下、図１の各ステップＳ２～Ｓ４の処理を、具体的に説明する。 ［Ｓ２］四面体メッシュ逐次生成 図３に、ステップＳ２の詳細な処理手順のフローチャートを示す。 【0025】 （Ｓ２１：凸頂点抽出） 四面体メッシュ逐次生成処理では、物品の表面に生成された入力される低品質の表面三角形メッシュのデータに基づいて、表面三角形メッシュ形状の凸部分であって、かつ比較的平坦な部分から、逐次的に四面体を構築する。このため、図４に示すように、三角形メッシュの凸頂点を抽出する。つまり、三角形メッシュの各頂点ｉの法線ｎｉと、頂点ｉに隣接する複数の隣接頂点ｊ∈ν＊（ｉ）との差分ベクトル（pｊ－ｐｉ）間の内積値ｃｉｊを次式（１）により求める。ここで、ν＊（ｉ）は、頂点ｉの隣接頂点ｊの集合を表す。 【0026】 【数1】 そして、ｊ∈ν＊（ｉ）に対する内積値ｃｉｊ（凸度）の最大値が負の頂点を凸頂点と判定する。つまり、（１）式における凸度が正の頂点は、表面三角形メッシュ形状の凹部分の頂点であり、製品の内部に四面体メッシュを生成する目的から外れるからである。 【0027】 （Ｓ２２：候補頂点の選択） Ｓ２１で抽出した凸頂点のうち、ｊ∈ν＊（ｉ）に対するｃｉｊの最小値が最大の頂点を、四面体生成の候補頂点として選択する。 【0028】 （Ｓ２３：三角形の分割） 選択された候補頂点の一近傍境界（ｒｉｎｇ）を三角形分割する。つまり、図５（ａ）、（ｂ）に示すように、候補頂点ｉに隣接する複数（図示例では５つ）の隣接頂点ｊで囲まれる多角形領域を、複数の三角形に分割する。 【0029】 （Ｓ２４：四面体要素の生成） 分割された各々の三角形と、現在の表面メッシュとの間に干渉がないならば、各々の三角形と頂点ｉを接続することによって、四面体要素を生成する（図５（ｃ））。これによって、最終的に得られる四面体メッシュの四面体要素と四面体要素との間に干渉がないことを保証する。図５（ｄ）は、部分的な四面体要素を取り除いた後の新しい表面三角形メッシュを表す。 【0030】 （Ｓ２５：生成した四面体要素を四面体メッシュに追加） 生成された四面体要素を四面体メッシュに追加するとともに、四面体要素を除去したことによって変わる表面メッシュを更新する。 【0031】 （Ｓ２６：繰返し処理） 全ての頂点ｉについてステップＳ２１～Ｓ２５の処理が終了したか否か判断し、終了していなければステップＳ２１に戻って処理を繰り返す。 【0032】 これによって、低品質の表面三角形メッシュのデータに基づいて、四面体メッシュを逐次的に生成できる。 ［Ｓ３］四面体メッシュの細分化 メッシュを簡略化による品質改善の自由度を高めるために、ステップＳ３において、ステップＳ２で生成された逐次四面体メッシュを細分化する。このプロセスでは、全ての稜線長ｌｅｎ（ｅ）がユーザ指定の閾値（細分化パラメータ）τｌｅｎ以下のメッシュを生成する。 【0033】 （Ｓ３１：各稜線に中点生成） 図６のフローチャートに示すように、ステップＳ３１で、ユーザが指定した閾値τｌｅｎ以上の長さの稜線があれば、その稜線に中点を設定する。 【0034】 （Ｓ３２：中点を用いて細分化） 次いで、ステップＳ３２において、稜線ｅに接続された四面体要素を、中点を用いて、図７に示すように細分化する。 【0035】 （Ｓ３３：繰返し処理） ステップＳ３３において、全ての稜線ｅについての細分化処理が終了したか否か判断し、全ての稜線長がτｌｅｎ以下になるまで、Ｓ３１～Ｓ３２を繰り返す。これにより、全ての稜線長がユーザ指定の閾値τｌｅｎ未満の四面体メッシュを生成する。 ［Ｓ４］四面体メッシュの簡略化 ここでは、ステップＳ３で細分化して得られた高密度の四面体メッシュに対し、形状近似誤差を一定値内に抑え、メッシュ品質を改善するメッシュ簡略化処理を行って、品質が向上した粗いメッシュを生成する。 【0036】 図８に、ステップＳ４の詳細な一実施の形態のフローチャートを示す。本実施形態のメッシュ簡略化のためのメッシュ要素数の削減方法として、稜線を構成する２頂点（ｉ，ｊ）を、１頂点ｋに統合する周知のＥＣ（Edge Collapse）処理を用いる。このＥＣ法は、例えば、Oliver G. Staadt and Markus H. Gross: Progressive Tetrahedralizations, proc. Of IEEE Visualization 98, 379-402, 1998 に開示されている。また、本実施形態では、ＥＣ適用稜線決定を適切に行うことにより、メッシュ品質改善効果を簡略化処理に持たせていることが特徴である。 【0037】 図８に示すように、ステップＳ４は、新頂点算出（Ｓ４１）と、ＥＣ適用有効稜線抽出（Ｓ４２）および有効稜線評価値算出（Ｓ４３）からなる有効稜線決定と、ＥＣ処理（Ｓ４４）の各処理ステップを含んで構成される。 【0038】 （Ｓ４１：新頂点算出） 図９に示すように、稜線（ｉ，ｊ）に対するＥＣ適用後の新頂点ｋの位置ｐｋは、端点ｉとｊの中点を第一候補として算出する（図９のケースＩ，III）。ここで、表面形状を保存するために、形状内部の稜線に対しては、一端点ｉが表面メッシュ上の場合にはｐｋ＝ｐｉとするＨａｌｆ－ＥＣ（Edge Collapse）を採用する（図９のケースII）。ここで、Ｈａｌｆ－ＥＣとは、頂点対を1つに統合する際に、頂点対の一方の頂点を新たな頂点とするＥＣ法である。つまり、表面上の端点は位置を変えないようにして、表面形状を保存する。また、両端点が表面メッシュ上にある場合は２ケース考えられる。第１のケースは、稜線が形状表面にある場合、第２のケースは、両端点が薄板の表面と裏面とにあり稜線自体は形状内部にある場合である。第１のケースのときは、普通にＥＣ法を適用する（図９のケースI）が、第２のケースのときは、ＥＣ適用不可とする。 【0039】 第１のケースの表面上の稜線に対しては、さらに、稜線（ｉ，ｊ）に接続する表面メッシュ上の面分（メッシュ）との自乗距離（ＱＥＭ）を最小化する頂点位置を第二候補として算出し、有効稜線評価結果に応じて順次利用する（図９のケースI）。ここで、自乗距離を最小化する頂点位置については、前述の非特許文献４に記載されている。 【0040】 （Ｓ４２：ＥＣ適用有効稜線の抽出） ステップＳ４１で求めた新頂点ｋに接続する稜線について、ＥＣを適用することが有効か否かを判定して、有効稜線を抽出する。この判定条件は、次の３条件である。 【0041】 条件１：形状近似誤差ｄｉｊ(ｋ)≦閾値τｔｏｌを満たす 条件２：表面三角形メッシュの裏返りおよび四面体要素の干渉回避 条件３：非多様体表面メッシュの回避 条件１は、ＥＣ処理で生ずる形状表面面分(メッシュ)－頂点間の自乗距離誤差ＱＥＭ(Quadric Error Metrics: 非特許文献４参照)が、ユーザが指定する簡略化パラメータである閾値τｔｏｌ以下のメッシュ表面上の稜線のみを、ＥＣ処理適用可能と判定する。このＱＥＭは、図１０の概念図に示すように、元の形状表面面分の張る平面と新頂点間の自乗距離ｄｉｊ(ｋ)と表現することができ、次式(２) により求める。 【0042】 【数2】 条件２は、表面面分の裏返り、または四面体要素の干渉が起こる稜線を判定し、条件２を満たさない場合はＥＣ処理の適用外とする。言い換えれば、ＥＣ処理の前後における対応する表面面分の法線の変化量が一定値以内であること、要素内部に対する頂点順序が変わらないことを条件とする。要素内部に対する頂点順序が変わらないことは、簡略化後の頂点kに隣接する四面体要素の稜線ベクトルのスカラー三重積の符号が変わらないことで判定する。 【0043】 条件３は、形状表面上の頂点同士を接続する内部稜線ではないことで判定する。 【0044】 （Ｓ４３：有効稜線の評価値算出） 本実施形態では、ＥＣ処理が適用可能な有効稜線と判定された稜線のうち、ＥＣ処理によるメッシュ品質の改善度の高いものから順に処理を実行する。そのために、ステップＳ４３において、品質評価値を算出する。品質評価の手法としては、要素形状品質、品質改善度、稜線の評価の少なくとも１つを適用する。 ［要素形状の評価］ 四面体要素形状の品質評価指標として、有限要素解析の分野でよく用いられるストレッチを用いる。これは、√６×要素内接球の直径／要素の最長辺長さとして定義され、次式（３）で求められる。 【0045】 【数3】 ここで、Ｖｈ、Ｓｈは四面体要素ｈの体積と表面積、ｌｅは稜線ｅの長さである。Ｓｔ(ｈ)の値は、図１１に示すように、正四面体で１、要素形状が歪むにつれて０に近づく。式(３)を用いて稜線ｅ＝（ｉ，ｊ）へのＥＣ処理適用による品質改善度を式(４)で評価する。 【0046】 【数4】 ここで、ｈ＊(ｉ)は頂点ｉに接続する四面体集合である。式(４)の値大きな稜線は、ＥＣ処理適用による稜線近傍のメッシュのストレッチ下限値、平均値の改善度が高いと評価できる。さらに、メッシュ内の要素分布の一様化を計るために、式(４)の評価値に、モデルサイズでスケールした稜線（ｉ，ｊ）近傍要素の最小辺の長さの平均値の逆数を乗じ、これを稜線(ｉ，ｊ)に対する最終的な評価値とする。 ［品質改善度の評価］ 品質改善度は、次式（５）に示すＥＣ処理の前後で変化する要素集合の品質勾配Δｑｉｊにより評価する。つまり、図１２に示す概念図のように、有効稜線（ｉ，ｊ）の両端点ｐｉ，ｐｊを新頂点ｐｋに統合する、ＥＣ処理を施すことによる品質改善度を評価する。 【0047】 【数5】 ここで、ｑ(Ｈ)は次式(６)に示す要素集合の品質評価値であり、要素集合Ｈのストレッチの平均と最小値の積である。 【0048】 【数6】 ［稜線品質改善度の評価］ 稜線(ｉ，ｊ)の品質改善度の評価値εｉｊは、品質改善度Δｑｉｊを最短稜線長さの平均値で重み付けした品質改善度であり、次式(７)で表せる。 【0049】 【数7】 ここで、ｓｉｊは、次式(８)で表せる。 【0050】 【数8】 （Ｓ４４：ＥＣ処理） ステップＳ４３で求めた各稜線の評価値に従って、有効稜線の内から評価値が最も高い稜線(ｉ，ｊ)から順にＥＣを適用してメッシュの簡略化処理を実行する。 【0051】 ここで、高品質の四面体メッシュに要求されるメッシュ特性を次に示しておく。 【0052】 ・形状近似度：高いほどよいが、近似誤差が許容値以下であればよい。 【0053】 ・要素数（処理負荷）：少ないほどよいが、容易に変更できることが好ましい。 【0054】 ・要素歪：小さいほどよい。正三角形に近いほどよい。 【0055】 ・要素粗密分布：利用目的に適した粗密、容易に変更できることが望ましい。 【0056】 上述した実施形態を具体的な物品に適用した実施例のメッシュの変化を図１３および図１４に示す。図１３の物品は傾斜円柱の例であり、図１３の物品は直方体に円柱状の窪みを有する例である。要素数が少ない低品質の三角形メッシュに基づいて、図１３（ａ）、図１４（ａ）に示す逐次四面体メッシュが生成され、この逐次四面体メッシュを細分化して、それらの図１３（ｂ）または図１４（ｂ）に示す品質は低いが操作の自由度が高い高密度四面体メッシュが生成される。この高密度四面体メッシュに対し、品質改善を伴うメッシュ簡略化を施して、それらの図１３の（ｃ）、（ｄ）または図１４（ｃ）に示すように、要素数が少なく、かつ高品質の四面体メッシュが生成される。簡略化パラメータとしての閾値（τｌｅｎ，τｔｏｌ）は、図１３の例は（２．５、０．１）を用い、図１４の例は（２．０，０．１）を用いた。 【0057】 これらの実施例により、本発明の手法により、入力表面三角形メッシュから四面体メッシュの多重解像度表現が生成できることが確認された。図１５と図１６に、図１３と図１４の各々のメッシュのストレッチ分布評価の結果を示す。それらの図の横軸はストレッチを示し、縦軸は各々のストレッチの頻度（％）を示している。図から分かるように、本発明によれば、ストレッチに関する要素形状品質を簡略化の過程で改善できることが確認できる。 【0058】 また、本発明によれば、メッシュ簡略化を施して低密度メッシュに変換した後は、図１３の（ｃ）または（ｄ）に示すように、メッシュの粗密を簡単に制御することができる。また、目標要素数を指定することにより、目標要素数に近い要素数のメッシュに簡単に制御できる。したがって、ユーザは、所望の解析に適した密度あるいは要素数の四面体メッシュを容易に生成することができ、極めて使い勝手のよい生成法を実現できる。 【0059】 このメッシュ密度あるいは要素数を制御する低解像度化操作画面の一実施例を図１７に示す。図示のように、操作画面には、パラメータ設定領域１１、要素数指定領域１２、スクロールバー（ＬＯＤ）設定領域１３、メッシュ要素数表示領域１４が設けられ、画面の右側にスクロールバー１５が表示されている。例えば、ユーザがスクロールバー１５を操作すると、スクロールバー１５の操作位置に応じて要素数指定領域１２の数値を任意に指定することができる。これにより、ステップＳ４のメッシュ簡略化処理は、要素数指定領域１２に設定された簡略化後の四面体メッシュの目標要素数に近付けるようにメッシュ簡略化処理を実行する。このとき、メッシュ簡略化処理では、主として簡略化パラメータτｌｅｎ、τｔｏｌを変更しながら、目標要素数に近い要素数の四面体メッシュを生成する。また、生成された四面体メッシュの要素数のパラメータである面分、稜線および頂点の数が、リアルタイムでメッシュ要素数表示領域１４に表示される。さらに、図示していないが、生成された四面体メッシュの画像をリアルタイムで表示装置に表示することができる。その結果、ユーザは、目標要素寸法に関係する簡略化パラメータτｌｅｎ、τｔｏｌ等を設定することなく、スクロールバーを操作するだけで、品質の保証された所望の要素数の四面体メッシュを容易に生成することができる。なお、簡略化後の四面体メッシュの目標要素数に代えて、メッシュの密度などの要素数に係るパラメータを入力して操作するようにすることができる。 【図面の簡単な説明】 【0060】 【図1】本発明の一実施の形態の高品質四面体メッシュ生成方法の基本フローチャートである。 【図2】本発明の四面体メッシュ生成方法の特徴を説明する概念図である。 【図3】図１の四面体メッシュ逐次生成処理（Ｓ２）の詳細なフローチャートである。 【図4】表面三角形メッシュの凸頂点を抽出する方法を説明する図である。 【図5】表面三角形メッシュから四面体メッシュを逐次生成する方法を説明する図である。 【図6】図１の四面体メッシュ細分化処理（Ｓ３）の詳細なフローチャートである。 【図7】四面体メッシュの細分化処理を説明する図である。 【図8】図１の四面体メッシュ簡略化処理（Ｓ４）の詳細なフローチャートである。 【図9】メッシュ簡略化のための稜線の端点を統合する新頂点の算出法を説明する図である。 【図10】メッシュ簡略化に伴う品質評価のための元の形状表面面分の張る平面と新頂点間の自乗距離を説明する図である。 【図11】メッシュ簡略化に伴う品質評価のためのストレッチを説明する図である。 【図12】ＥＣ処理を施して有効稜線の両端点を新頂点に統合することによる品質改善度を評価する概念を説明する図である。 【図13】本発明の実施形態を傾斜円柱に適用した実施例のメッシュの変化を示す図である。 【図14】本発明の実施形態を円柱の窪みを有する直方体に適用した実施例のメッシュの変化を示す図である。 【図15】図１３の実施例のメッシュのストレッチ分布評価の結果を示す図である。 【図16】図１４の実施例のメッシュのストレッチ分布評価の結果を示す図である。 【図17】本発明のメッシュ密度あるいは要素数を制御する低解像度化操作画面の一例を示す図である。
図面	【図1】 【図2】 【図3】 【図4】 【図5】 【図6】 【図7】 【図8】 【図9】 【図10】 【図11】 【図12】 【図13】 【図14】 【図15】 【図16】 【図17】