TOP > 国内特許検索 > 四面体メッシュ生成方法およびプログラム > 明細書

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

発行国 日本国特許庁(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)
FI G06F 17/50 612J
請求項の数または発明の数 9
全頁数 15
出願番号 特願2004-252444 (P2004-252444)
出願日 平成16年8月31日(2004.8.31)
新規性喪失の例外の表示 特許法第30条第1項適用 平成16年3月1日 社団法人精密工学会発行の「2004年度精密工学会春季大会 学術講演会講演論文集」に発表
審査請求日 平成19年3月29日(2007.3.29)
特許権者または実用新案権者 【識別番号】504173471
【氏名又は名称】国立大学法人北海道大学
【識別番号】000005108
【氏名又は名称】株式会社日立製作所
発明者または考案者 【氏名】金井 理
【氏名】伊達 宏昭
【氏名】岸浪 建史
【氏名】西垣 一朗
個別代理人の代理人 【識別番号】100098017、【弁理士】、【氏名又は名称】吉岡 宏嗣
【識別番号】100066979、【弁理士】、【氏名又は名称】鵜沼 辰之
審査官 【審査官】加舎 理紅子
参考文献・文献 特開2003-345837(JP,A)
特開平11-096399(JP,A)
特開2005-242647(JP,A)
特開2005-242651(JP,A)
伊達宏昭 他,細分化と簡略化に基づくメッシュ品質向上手法,2003年度精密工学会北海道支部学術講演会講演論文集,2003年 9月 6日,p.41-42
伊達宏昭 他,有限要素解析用多重解像度メッシュ生成に関する研究-高密度四面体メッシュからの解析用メッシュ生成-,第66回(平成16年)全国大会講演論文集(4),2004年 3月 9日,p.4-59~4-60
Oliver G. Staadt,Markus H. Gross,Progressive Tetrahedralizations,Proceedings of the IEEE Visualization 98,1998年10月24日,p.397-402
調査した分野 G06F 17/50
CiNii
JSTPlus(JDreamII)
特許請求の範囲 【請求項1】
物品の表面に生成された三角形メッシュのデータをコンピュータに取り込み、該コンピュータにより、表面三角形メッシュに基づいて四面体メッシュを逐次生成する第1ステップと、第1ステップで生成された四面体メッシュのデータを取り込み、四面体メッシュを分割して細分化する第2ステップと、第2ステップで生成された四面体メッシュのデータを取り込み、四面体メッシュの数を減らして簡略化する第3ステップとを含んでなり、
第1ステップは、前記表面三角形メッシュの頂点が少なくとも凹んでいない凸頂点を抽出し、該抽出した凸頂点に隣接する他の複数の頂点で囲まれる多角形を複数の三角形に分割し、該分割された各三角形と前記凸頂点を接続して四面体メッシュを逐次生成し、
第2ステップは、第1ステップで生成された四面体メッシュの稜線長が予め定められた閾値以上の稜線を少なくとも2つに分割し、該稜線に接続された四面体メッシュを該稜線の分割点によって分割して細分化し、
第3ステップは、第2ステップで生成された四面体メッシュを構成する稜線の両端の頂点を1つに統合するための新頂点を算出するステップと、該ステップにより算出された前記新頂点に基づいて前記四面体メッシュの数を減らして簡略化するステップとを含んでなる四面体メッシュ生成方法。
【請求項2】
第2ステップは、前記閾値以上の稜線を、当該稜線の中点によって分割することを特徴とする請求項に記載の四面体メッシュ生成方法。
【請求項3】
前記新頂点算出ステップは、前記稜線の中点を前記新頂点として算出することを特徴とする請求項に記載の四面体メッシュ生成方法。
【請求項4】
前記新頂点算出ステップは、前記稜線の一方の頂点が表面メッシュ上に在るとき、当該一方の頂点を前記新頂点として算出することを特徴とする請求項に記載の四面体メッシュ生成方法。
【請求項5】
前記新頂点算出ステップは、前記稜線が表面メッシュ上に在るとき、該稜線に接続する表面メッシュ上の面分との自乗距離を最小化する頂点位置を前記新頂点として算出することを特徴とする請求項に記載の四面体メッシュ生成方法。
【請求項6】
第3ステップは、前記新頂点算出ステップにより算出された前記新頂点に接続する稜線について、前記簡略化ステップを適用することが有効か否か判定して有効稜線を抽出するステップを有し、
該有効稜線抽出ステップは、前記簡略化ステップを適用した場合に、形状近似誤差が予め定められた閾値以下であること、表面三角形メッシュの裏返りおよび四面体要素の干渉を回避できること、および非多様体表面メッシュを回避できることの少なくとも1つの判定条件を満たす稜線を有効稜線として抽出することを特徴とする請求項3乃至5のいずれか1項に記載の四面体メッシュ生成方法。
【請求項7】
第3ステップは、前記有効稜線抽出ステップにより抽出された有効稜線について、前記簡略化ステップを適用することによりメッシュ品質を評価するステップを有し、
該品質評価ステップは、前記有効稜線について、前記簡略化ステップを適用した場合に生成される四面体要素形状のストレッチ、前記簡略化ステップを適用した場合に前後で変化する要素集合の品質勾配による品質改善度、および該品質改善度を最短稜線長の平均値で重み付けした稜線の評価値の少なくとも1つで評価し、
前記簡略化ステップは、前記品質評価ステップの品質評価値が高い前記有効稜線から順に前記簡略化を実行することを特徴とする請求項に記載の四面体メッシュ生成方法。
【請求項8】
前記簡略化ステップは、簡略化後の四面体メッシュの目標要素数に係るパラメータを入力する操作画面を表示画面に表示し、該操作画面から入力された目標要素数に係るパラメータを満たすように四面体メッシュの簡略化処理を実行することを特徴とする請求項またはに記載の四面体メッシュ生成方法。
【請求項9】
請求項1乃至のいずれか1項に記載の四面体メッシュ生成方法をコンピュータにより実行可能に記述してなる四面体メッシュ生成プログラム。
発明の詳細な説明 【技術分野】
【0001】
本発明は、有限要素解析に用いられる四面体メッシュ生成方法およびプログラムに係り、具体的には、コンピュータを用いて低品質の三角形メッシュから高品質の四面体メッシュを生成する技術に関する。
【背景技術】
【0002】
物品の強度や熱変形等の物理的な性質を有限要素法により解析する際、その物品を例えばコンピュータグラフィックス(CG)化したソリッドモデルを、細かい面分要素(メッシュ)の集合として表現したメッシュモデルが用いられる。特に、有限要素法解析においては、高品質メッシュ生成がCAE(FEA)の効率化に要求される。
【0003】
従来、ソリッドモデルのメッシュ生成には、FEMメッシャ、CADやCGモデラのテセレータが代表的である。FEMメッシャは、比較的高品質な表面三角形メッシュ(表面メッシュモデル)や四面体メッシュ(ボリュームメッシュモデル)を生成可能である。しかし、FEMメッシャは、処理が低速で、複雑な形状に対しては処理が不安定であり、経験や知識を要するマニュアル操作が必要となる場合が多い。
【0004】
一方、CADやCGのテセレータは、高速かつ確実に表面三角形メッシュを生成できるが、要素歪や要素サイズの不均一度などの品質が低い。
【0005】
また、従来のメッシュモデルの生成法としては、例えば、非特許文献1~5に開示されたものが知られている。
【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】
上記課題を解決するため、本発明の四面体メッシュ生成方法は、物品の表面に生成された三角形メッシュデータをコンピュータに取り込み、該コンピュータを用いて、表面三角形メッシュに基づいて四面体メッシュを逐次生成する第1ステップと、第1ステップで生成された四面体メッシュのデータを取り込み、四面体メッシュを分割して細分化する第2ステップと、第2ステップで生成された四面体メッシュのデータを取り込み、四面体メッシュの数を減らして簡略化する第3ステップとを実行することを特徴とする。
【0010】
すなわち、本発明は、高密度メッシュの位相操作の自由度の高さに注目し、メッシュ品質は第3ステップの四面体メッシュの簡略化処理で考慮することにした。その結果、第1および第2のステップでは、品質を考慮することなく、低品質の三角形メッシュから四面体メッシュを生成した後、四面体メッシュを細分化して高密度化することができる。したがって、単純な手法で高密度化できる。次いで、高密度化した四面体メッシュの操作の自由度を利用して、品質を考慮しながら四面体メッシュの数を減らして簡略化することにより、所望のメッシュサイズを有する高品質の四面体メッシュを生成することができる。また、メッシュの数(要素数)の制御が容易である。さらに、メッシュ簡略化の結果、四面体メッシュの多重解像度表現が生成でき、様々なアプリケーションでの効率的なメッシュ利用が可能となる。
【0011】
ここで、第1ステップは、前記表面三角形メッシュの頂点が少なくとも凹んでいない凸頂点を抽出し、該抽出した凸頂点に隣接する他の複数の頂点で囲まれる多角形を複数の三角形に分割し、該分割された各三角形と前記凸頂点を接続して四面体メッシュを逐次生成することができる。つまり、表面三角形メッシュ形状は、物品の形状に起因して突出したり凹んだりしている。しかし、四面体メッシュを生成するのは物品の内部であるから、表面三角形メッシュ形状の凸部分または比較的平坦な部分から四面体メッシュを生成するため、表面三角形メッシュの頂点が少なくとも凹んでいない凸頂点を要件とする。
【0012】
また、第2ステップは、各四面体メッシュの稜線長が予め定められた閾値以上の稜線を少なくとも2つに分割し、該稜線に接続された四面体メッシュを該稜線の分割点によって分割して細分化することができる。この場合において、前記閾値以上の稜線を、当該稜線の中点によって分割することにより、高密度化処理を単純化して高速化できる。
【0013】
また、第3ステップは、第2ステップで生成された高密度の四面体メッシュを構成する稜線の両端の頂点を1つに統合するための新頂点を算出するステップと、該ステップにより算出された前記新頂点に基づいて前記四面体メッシュの数を減らして簡略化するステップとを含んで構成することができる。この場合、新頂点算出ステップは、前記稜線の中点を前記新頂点として算出すること、前記稜線の一方の頂点が表面メッシュ上に在るとき、当該一方の頂点を前記新頂点として算出すること、あるいは前記稜線が表面メッシュ上に在るとき、該稜線に接続する表面メッシュ上の面分との自乗距離を最小化する頂点位置を前記新頂点として算出することを適宜採用することができる。
【0014】
また、第3ステップは、前記新頂点算出ステップにより算出された前記新頂点に接続する稜線について、前記簡略化ステップを適用することが有効か否か判定して有効稜線を抽出するステップを有し、該有効稜線抽出ステップは、前記簡略化ステップを適用した場合に、形状近似誤差が予め定められた閾値以下であること、表面三角形メッシュの裏返りおよび四面体要素の干渉を回避できること、および非多様体表面メッシュを回避できることの少なくとも1つの判定条件を満たす稜線を有効稜線として抽出することができる。
【0015】
さらに、第3ステップは、前記有効稜線抽出ステップにより抽出された有効稜線について、前記簡略化ステップを適用することによりメッシュ品質を評価するステップを有し、該品質評価ステップは、前記有効稜線について、前記簡略化ステップを適用した場合に生成される四面体要素形状のストレッチ、前記簡略化ステップを適用した場合に前後で変化する要素集合の品質勾配による品質改善度、および該品質改善度を最短稜線長の平均値で重み付けした稜線の評価値の少なくとも1つで評価し、前記簡略化ステップは、前記品質評価ステップの品質評価値が高い前記有効稜線から順に前記簡略化を実行する構成とすることができる。
【0016】
また、本発明の四面体メッシュ生成プログラムは、上記の四面体メッシュ生成方法をコンピュータにより実行可能に記述して形成できる。
【発明の効果】
【0017】
上述したように、本発明によれば、高品質の四面体メッシュ生成処理を高速化でき、かつ複雑な形状に対しても安定な処理を実現することができる。
【発明を実施するための最良の形態】
【0018】
以下、本発明を実施形態に基づいて説明する。図1に、本発明の一実施の形態の高品質四面体メッシュ生成方法の基本フローチャートを示す。図2に、本発明の四面体メッシュ生成方法の概念図を示す。
【0019】
図2の三次元グラフに示すように、本発明は、要素数が少ない低品質の三角形メッシュから四面体メッシュを生成して細分化して、品質は低いが操作の自由度が高い高密度メッシュを一旦生成した後、その高密度メッシュを簡略化して要素数が少なく、かつ高品質の四面体メッシュを生成することを特徴とする。
【0020】
具体的には、図1のフローチャートに示すように、まず、CADテセレータなどにより物品の表面に生成された低品質の表面三角形メッシュのデータを取り込む(S1)。次いで、取り込んだ表面三角形メッシュのデータに基づいて四面体メッシュを逐次生成し(S2)、その生成された四面体メッシュを分割して細分化する(S3)。最後に、細分化された高密度の四面体メッシュを簡略化して、所望の要素サイズ、所望の高品質および所望の要素数を有する四面体メッシュを生成する(S4)。
【0021】
ここで、ステップ4の簡略化処理は、各四面体メッシュを構成する稜線の両端の頂点を1つの新頂点に統合することにより簡略化する処理であり、いわゆるEC(Edge Collapse)として知られている手法を用い、後述するように品質を考慮しながら簡略化する。また、図1の各ステップの処理は、コンピュータおよびコンピュータを駆動するプログラムにより実現できる。また、必要に応じて、物品の三角形メッシュのデータおよび生成された四面体メッシュのデータを格納する記憶装置が設けられる。
【0022】
したがって、図1に示したステップS1~S4の処理を有する本実施形態によれば、高品質の四面体メッシュの生成処理を高速化でき、かつ複雑な形状に対しても安定な処理を実現することができる。すなわち、メッシュ品質はステップS4の四面体メッシュの簡略化処理で考慮することにし、ステップS2、S3では、品質を考慮することなく、低品質の三角形メッシュから四面体メッシュを生成した後、四面体メッシュを細分化して高密度化する。これらの処理は、単純な手法であるから高速に実行できる。このようにして生成された高密度化した四面体メッシュの操作の自由度の高さを利用して、ステップS4において、品質を考慮しながら高密度の四面体メッシュを簡略化して、所望のメッシュサイズおよび高品質の四面体メッシュを生成する。これにより、高品質の四面体メッシュを高速で生成することができる。
【0023】
また、本実施形態によれば、メッシュの要素数を容易に制御できる。さらに、メッシュ簡略化の結果、四面体メッシュの多重解像度表現が生成でき、様々なアプリケーションでの効率的なメッシュ利用が可能となる。
【0024】
以下、図1の各ステップS2~S4の処理を、具体的に説明する。
[S2]四面体メッシュ逐次生成
図3に、ステップS2の詳細な処理手順のフローチャートを示す。
【0025】
(S21:凸頂点抽出)
四面体メッシュ逐次生成処理では、物品の表面に生成された入力される低品質の表面三角形メッシュのデータに基づいて、表面三角形メッシュ形状の凸部分であって、かつ比較的平坦な部分から、逐次的に四面体を構築する。このため、図4に示すように、三角形メッシュの凸頂点を抽出する。つまり、三角形メッシュの各頂点iの法線niと、頂点iに隣接する複数の隣接頂点j∈ν(i)との差分ベクトル(pj-pi)間の内積値cijを次式(1)により求める。ここで、ν(i)は、頂点iの隣接頂点jの集合を表す。
【0026】
【数1】
JP0004714444B2_000002t.gif

そして、j∈ν(i)に対する内積値cij(凸度)の最大値が負の頂点を凸頂点と判定する。つまり、(1)式における凸度が正の頂点は、表面三角形メッシュ形状の凹部分の頂点であり、製品の内部に四面体メッシュを生成する目的から外れるからである。
【0027】
(S22:候補頂点の選択)
S21で抽出した凸頂点のうち、j∈ν(i)に対するcijの最小値が最大の頂点を、四面体生成の候補頂点として選択する。
【0028】
(S23:三角形の分割)
選択された候補頂点の一近傍境界(ring)を三角形分割する。つまり、図5(a)、(b)に示すように、候補頂点iに隣接する複数(図示例では5つ)の隣接頂点jで囲まれる多角形領域を、複数の三角形に分割する。
【0029】
(S24:四面体要素の生成)
分割された各々の三角形と、現在の表面メッシュとの間に干渉がないならば、各々の三角形と頂点iを接続することによって、四面体要素を生成する(図5(c))。これによって、最終的に得られる四面体メッシュの四面体要素と四面体要素との間に干渉がないことを保証する。図5(d)は、部分的な四面体要素を取り除いた後の新しい表面三角形メッシュを表す。
【0030】
(S25:生成した四面体要素を四面体メッシュに追加)
生成された四面体要素を四面体メッシュに追加するとともに、四面体要素を除去したことによって変わる表面メッシュを更新する。
【0031】
(S26:繰返し処理)
全ての頂点iについてステップS21~S25の処理が終了したか否か判断し、終了していなければステップS21に戻って処理を繰り返す。
【0032】
これによって、低品質の表面三角形メッシュのデータに基づいて、四面体メッシュを逐次的に生成できる。
[S3]四面体メッシュの細分化
メッシュを簡略化による品質改善の自由度を高めるために、ステップS3において、ステップS2で生成された逐次四面体メッシュを細分化する。このプロセスでは、全ての稜線長len(e)がユーザ指定の閾値(細分化パラメータ)τlen以下のメッシュを生成する。
【0033】
(S31:各稜線に中点生成)
図6のフローチャートに示すように、ステップS31で、ユーザが指定した閾値τlen以上の長さの稜線があれば、その稜線に中点を設定する。
【0034】
(S32:中点を用いて細分化)
次いで、ステップS32において、稜線eに接続された四面体要素を、中点を用いて、図7に示すように細分化する。
【0035】
(S33:繰返し処理)
ステップS33において、全ての稜線eについての細分化処理が終了したか否か判断し、全ての稜線長がτlen以下になるまで、S31~S32を繰り返す。これにより、全ての稜線長がユーザ指定の閾値τlen未満の四面体メッシュを生成する。
[S4]四面体メッシュの簡略化
ここでは、ステップS3で細分化して得られた高密度の四面体メッシュに対し、形状近似誤差を一定値内に抑え、メッシュ品質を改善するメッシュ簡略化処理を行って、品質が向上した粗いメッシュを生成する。
【0036】
図8に、ステップS4の詳細な一実施の形態のフローチャートを示す。本実施形態のメッシュ簡略化のためのメッシュ要素数の削減方法として、稜線を構成する2頂点(i,j)を、1頂点kに統合する周知のEC(Edge Collapse)処理を用いる。このEC法は、例えば、Oliver G. Staadt and Markus H. Gross: Progressive Tetrahedralizations, proc. Of IEEE Visualization 98, 379-402, 1998 に開示されている。また、本実施形態では、EC適用稜線決定を適切に行うことにより、メッシュ品質改善効果を簡略化処理に持たせていることが特徴である。
【0037】
図8に示すように、ステップS4は、新頂点算出(S41)と、EC適用有効稜線抽出(S42)および有効稜線評価値算出(S43)からなる有効稜線決定と、EC処理(S44)の各処理ステップを含んで構成される。
【0038】
(S41:新頂点算出)
図9に示すように、稜線(i,j)に対するEC適用後の新頂点kの位置pkは、端点iとjの中点を第一候補として算出する(図9のケースI,III)。ここで、表面形状を保存するために、形状内部の稜線に対しては、一端点iが表面メッシュ上の場合にはpk=piとするHalf-EC(Edge Collapse)を採用する(図9のケースII)。ここで、Half-ECとは、頂点対を1つに統合する際に、頂点対の一方の頂点を新たな頂点とするEC法である。つまり、表面上の端点は位置を変えないようにして、表面形状を保存する。また、両端点が表面メッシュ上にある場合は2ケース考えられる。第1のケースは、稜線が形状表面にある場合、第2のケースは、両端点が薄板の表面と裏面とにあり稜線自体は形状内部にある場合である。第1のケースのときは、普通にEC法を適用する(図9のケースI)が、第2のケースのときは、EC適用不可とする。
【0039】
第1のケースの表面上の稜線に対しては、さらに、稜線(i,j)に接続する表面メッシュ上の面分(メッシュ)との自乗距離(QEM)を最小化する頂点位置を第二候補として算出し、有効稜線評価結果に応じて順次利用する(図9のケースI)。ここで、自乗距離を最小化する頂点位置については、前述の非特許文献4に記載されている。
【0040】
(S42:EC適用有効稜線の抽出)
ステップS41で求めた新頂点kに接続する稜線について、ECを適用することが有効か否かを判定して、有効稜線を抽出する。この判定条件は、次の3条件である。
【0041】
条件1:形状近似誤差dij(k)≦閾値τtolを満たす
条件2:表面三角形メッシュの裏返りおよび四面体要素の干渉回避
条件3:非多様体表面メッシュの回避
条件1は、EC処理で生ずる形状表面面分(メッシュ)-頂点間の自乗距離誤差QEM(Quadric Error Metrics: 非特許文献4参照)が、ユーザが指定する簡略化パラメータである閾値τtol以下のメッシュ表面上の稜線のみを、EC処理適用可能と判定する。このQEMは、図10の概念図に示すように、元の形状表面面分の張る平面と新頂点間の自乗距離dij(k)と表現することができ、次式(2) により求める。
【0042】
【数2】
JP0004714444B2_000003t.gif

条件2は、表面面分の裏返り、または四面体要素の干渉が起こる稜線を判定し、条件2を満たさない場合はEC処理の適用外とする。言い換えれば、EC処理の前後における対応する表面面分の法線の変化量が一定値以内であること、要素内部に対する頂点順序が変わらないことを条件とする。要素内部に対する頂点順序が変わらないことは、簡略化後の頂点kに隣接する四面体要素の稜線ベクトルのスカラー三重積の符号が変わらないことで判定する。
【0043】
条件3は、形状表面上の頂点同士を接続する内部稜線ではないことで判定する。
【0044】
(S43:有効稜線の評価値算出)
本実施形態では、EC処理が適用可能な有効稜線と判定された稜線のうち、EC処理によるメッシュ品質の改善度の高いものから順に処理を実行する。そのために、ステップS43において、品質評価値を算出する。品質評価の手法としては、要素形状品質、品質改善度、稜線の評価の少なくとも1つを適用する。
[要素形状の評価]
四面体要素形状の品質評価指標として、有限要素解析の分野でよく用いられるストレッチを用いる。これは、√6×要素内接球の直径/要素の最長辺長さとして定義され、次式(3)で求められる。
【0045】
【数3】
JP0004714444B2_000004t.gif

ここで、V、Sは四面体要素hの体積と表面積、lは稜線eの長さである。St(h)の値は、図11に示すように、正四面体で1、要素形状が歪むにつれて0に近づく。式(3)を用いて稜線e=(i,j)へのEC処理適用による品質改善度を式(4)で評価する。
【0046】
【数4】
JP0004714444B2_000005t.gif

ここで、h(i)は頂点iに接続する四面体集合である。式(4)の値大きな稜線は、EC処理適用による稜線近傍のメッシュのストレッチ下限値、平均値の改善度が高いと評価できる。さらに、メッシュ内の要素分布の一様化を計るために、式(4)の評価値に、モデルサイズでスケールした稜線(i,j)近傍要素の最小辺の長さの平均値の逆数を乗じ、これを稜線(i,j)に対する最終的な評価値とする。
[品質改善度の評価]
品質改善度は、次式(5)に示すEC処理の前後で変化する要素集合の品質勾配Δqijにより評価する。つまり、図12に示す概念図のように、有効稜線(i,j)の両端点pi,pjを新頂点pkに統合する、EC処理を施すことによる品質改善度を評価する。
【0047】
【数5】
JP0004714444B2_000006t.gif

ここで、q(H)は次式(6)に示す要素集合の品質評価値であり、要素集合Hのストレッチの平均と最小値の積である。
【0048】
【数6】
JP0004714444B2_000007t.gif

[稜線品質改善度の評価]
稜線(i,j)の品質改善度の評価値εijは、品質改善度Δqijを最短稜線長さの平均値で重み付けした品質改善度であり、次式(7)で表せる。
【0049】
【数7】
JP0004714444B2_000008t.gif

ここで、sijは、次式(8)で表せる。
【0050】
【数8】
JP0004714444B2_000009t.gif

(S44:EC処理)
ステップS43で求めた各稜線の評価値に従って、有効稜線の内から評価値が最も高い稜線(i,j)から順にECを適用してメッシュの簡略化処理を実行する。
【0051】
ここで、高品質の四面体メッシュに要求されるメッシュ特性を次に示しておく。
【0052】
・形状近似度:高いほどよいが、近似誤差が許容値以下であればよい。
【0053】
・要素数(処理負荷):少ないほどよいが、容易に変更できることが好ましい。
【0054】
・要素歪:小さいほどよい。正三角形に近いほどよい。
【0055】
・要素粗密分布:利用目的に適した粗密、容易に変更できることが望ましい。
【0056】
上述した実施形態を具体的な物品に適用した実施例のメッシュの変化を図13および図14に示す。図13の物品は傾斜円柱の例であり、図13の物品は直方体に円柱状の窪みを有する例である。要素数が少ない低品質の三角形メッシュに基づいて、図13(a)、図14(a)に示す逐次四面体メッシュが生成され、この逐次四面体メッシュを細分化して、それらの図13(b)または図14(b)に示す品質は低いが操作の自由度が高い高密度四面体メッシュが生成される。この高密度四面体メッシュに対し、品質改善を伴うメッシュ簡略化を施して、それらの図13の(c)、(d)または図14(c)に示すように、要素数が少なく、かつ高品質の四面体メッシュが生成される。簡略化パラメータとしての閾値(τlen,τtol)は、図13の例は(2.5、0.1)を用い、図14の例は(2.0,0.1)を用いた。
【0057】
これらの実施例により、本発明の手法により、入力表面三角形メッシュから四面体メッシュの多重解像度表現が生成できることが確認された。図15と図16に、図13と図14の各々のメッシュのストレッチ分布評価の結果を示す。それらの図の横軸はストレッチを示し、縦軸は各々のストレッチの頻度(%)を示している。図から分かるように、本発明によれば、ストレッチに関する要素形状品質を簡略化の過程で改善できることが確認できる。
【0058】
また、本発明によれば、メッシュ簡略化を施して低密度メッシュに変換した後は、図13の(c)または(d)に示すように、メッシュの粗密を簡単に制御することができる。また、目標要素数を指定することにより、目標要素数に近い要素数のメッシュに簡単に制御できる。したがって、ユーザは、所望の解析に適した密度あるいは要素数の四面体メッシュを容易に生成することができ、極めて使い勝手のよい生成法を実現できる。
【0059】
このメッシュ密度あるいは要素数を制御する低解像度化操作画面の一実施例を図17に示す。図示のように、操作画面には、パラメータ設定領域11、要素数指定領域12、スクロールバー(LOD)設定領域13、メッシュ要素数表示領域14が設けられ、画面の右側にスクロールバー15が表示されている。例えば、ユーザがスクロールバー15を操作すると、スクロールバー15の操作位置に応じて要素数指定領域12の数値を任意に指定することができる。これにより、ステップS4のメッシュ簡略化処理は、要素数指定領域12に設定された簡略化後の四面体メッシュの目標要素数に近付けるようにメッシュ簡略化処理を実行する。このとき、メッシュ簡略化処理では、主として簡略化パラメータτlen、τtolを変更しながら、目標要素数に近い要素数の四面体メッシュを生成する。また、生成された四面体メッシュの要素数のパラメータである面分、稜線および頂点の数が、リアルタイムでメッシュ要素数表示領域14に表示される。さらに、図示していないが、生成された四面体メッシュの画像をリアルタイムで表示装置に表示することができる。その結果、ユーザは、目標要素寸法に関係する簡略化パラメータτlen、τtol等を設定することなく、スクロールバーを操作するだけで、品質の保証された所望の要素数の四面体メッシュを容易に生成することができる。なお、簡略化後の四面体メッシュの目標要素数に代えて、メッシュの密度などの要素数に係るパラメータを入力して操作するようにすることができる。
【図面の簡単な説明】
【0060】
【図1】本発明の一実施の形態の高品質四面体メッシュ生成方法の基本フローチャートである。
【図2】本発明の四面体メッシュ生成方法の特徴を説明する概念図である。
【図3】図1の四面体メッシュ逐次生成処理(S2)の詳細なフローチャートである。
【図4】表面三角形メッシュの凸頂点を抽出する方法を説明する図である。
【図5】表面三角形メッシュから四面体メッシュを逐次生成する方法を説明する図である。
【図6】図1の四面体メッシュ細分化処理(S3)の詳細なフローチャートである。
【図7】四面体メッシュの細分化処理を説明する図である。
【図8】図1の四面体メッシュ簡略化処理(S4)の詳細なフローチャートである。
【図9】メッシュ簡略化のための稜線の端点を統合する新頂点の算出法を説明する図である。
【図10】メッシュ簡略化に伴う品質評価のための元の形状表面面分の張る平面と新頂点間の自乗距離を説明する図である。
【図11】メッシュ簡略化に伴う品質評価のためのストレッチを説明する図である。
【図12】EC処理を施して有効稜線の両端点を新頂点に統合することによる品質改善度を評価する概念を説明する図である。
【図13】本発明の実施形態を傾斜円柱に適用した実施例のメッシュの変化を示す図である。
【図14】本発明の実施形態を円柱の窪みを有する直方体に適用した実施例のメッシュの変化を示す図である。
【図15】図13の実施例のメッシュのストレッチ分布評価の結果を示す図である。
【図16】図14の実施例のメッシュのストレッチ分布評価の結果を示す図である。
【図17】本発明のメッシュ密度あるいは要素数を制御する低解像度化操作画面の一例を示す図である。
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11
【図13】
12
【図14】
13
【図15】
14
【図16】
15
【図17】
16