(57)【特許請求の範囲】
【請求項１】
メッシングの対象となる形状を入力するステップと、
コンピュータの演算処理により前記メッシングの対象となる形状の領域内に複数のバブルを前記コンピュータのメモリ中に生成するステップと、
バブルに設定されたポテンシャル場により規定される力で前記メモリ中の前記バブルを移動させ且つバブル個数を制御することにより、前記バブルの安定した配置を決定するステップであって、前記力が、バブル周辺でポテンシャルが極小となる点と当該点に隣接するバブルとの間に、当該点と隣接するバブルとの間の距離の関数として定義される、安定配置決定ステップと、
コンピュータの演算処理により前記安定配置されたバブルについて隣接するバブルの中心を接続してメッシュを生成するメッシュ生成ステップと、
を含むメッシング方法。
【請求項２】
前記ポテンシャル場が、バブル周辺の４点で極小となることを特徴とする請求項１記載のメッシング方法。
【請求項３】
前記ポテンシャル場が、バブル周辺の６点で極小となることを特徴とする請求項１記載のメッシング方法。
【請求項４】
前記ポテンシャル場が、バブル周辺であって、メッシュの整列方向における点及び当該整列方向に対して垂直な方向における点で極小となることを特徴とする請求項１記載のメッシング方法。
【請求項５】
前記ポテンシャル場は、バブル周辺であって且つメッシュの整列方向の線上の２点及び当該整列方向に対して垂直な方向の線上の４点でポテンシャルが極小となり、前記安定配置決定ステップが、ポテンシャルが極小となる点ごとに、当該極小となる点に隣接するバブルを登録するステップを含み、前記メッシュ生成ステップが、第１バブルの前記極小となる点に登録されたバブルを用いて、当該第１バブルに接続すべきバブルを選択する選択ステップと、を含む請求項１記載のメッシング方法。
【請求項６】
前記選択ステップを、最初に前記メッシングの対象となる形状の境界面上に配置されたバブルを前記第１バブルとして実施し、ついで前記メッシングの対象となる形状の内部のバブルを前記第１バブルとして実施することを特徴とする請求項５記載のメッシング方法。
【請求項７】
メッシングの対象となる形状を入力する手段と、
コンピュータの演算処理により前記メッシングの対象となる形状の領域内に複数のバブルを前記コンピュータのメモリ中に生成する手段と、
バブルに設定されたポテンシャル場により規定される力で前記メモリ中の前記バブルを移動させ且つバブル個数を制御することにより、前記バブルの安定した配置を決定する手段あって、前記力が、バブル周辺でポテンシャルが極小となる点と当該点に隣接するバブルとの間に、当該点と隣接するバブルとの間の距離の関数として定義される、安定配置決定手段と、
コンピュータの演算処理により前記安定配置されたバブルについて隣接するバブルの中心を接続してメッシュを生成するメッシュ生成手段と、
を含むメッシング装置。
【請求項８】
前記ポテンシャル場が、バブル周辺の４点で極小となることを特徴とする請求項７記載のメッシング装置。
【請求項９】
前記ポテンシャル場が、バブル周辺の６点で極小となることを特徴とする請求項７記載のメッシング装置。
【請求項１０】
前記ポテンシャル場が、バブル周辺であって、メッシュの整列方向における点及び当該整列方向に対して垂直な方向における点で極小となることを特徴とする請求項７記載のメッシング装置。
【請求項１１】
前記ポテンシャル場は、バブル周辺であって且つメッシュの整列方向の線上の２点及び当該整列方向に対して垂直な方向の線上の４点でポテンシャルが極小となり、前記安定配置決定手段は、ポテンシャルが極小となる点ごとに、当該極小となる点に隣接するバブルを登録し、前記メッシュ生成手段は、第１バブルの前記極小となる点に登録されたバブルを用いて、当該第１バブルに接続すべきバブルを選択する、ことを特徴とする請求項７記載のメッシング装置。
【請求項１２】
前記メッシュ生成手段のバブル選択処理を、最初に前記メッシングの対象となる形状の境界面上に配置されたバブルを前記第１バブルとして実施し、ついで前記メッシングの対象となる形状の内部のバブルを前記第１バブルとして実施することを特徴とする請求項１１記載のメッシング装置。
【請求項１３】
メッシングのためのプログラムを格納した記憶媒体であって、前記プログラムが、
メッシングの対象となる形状を入力するステップと、
コンピュータの演算処理により前記メッシングの対象となる形状の領域内に複数のバブルを前記コンピュータのメモリ中に生成するステップと、
バブルに設定されたポテンシャル場により規定される力で前記メモリ中の前記バブルを移動させ且つバブル個数を制御することにより、前記バブルの安定した配置を決定するステップであって、前記力が、バブル周辺でポテンシャルが極小となる点と当該点に隣接するバブルとの間に、当該点と隣接するバブルとの間の距離の関数として定義される、安定配置決定ステップと、
コンピュータの演算処理により前記安定配置されたバブルについて隣接するバブルの中心を接続してメッシュを生成するメッシュ生成ステップと、
をコンピュータに実行させる、前記プログラムを格納した記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、メッシング方法に関し、より詳しくは、バブルを用いたメッシング方法に関する。
【０００２】
【従来の技術】
メッシング又はメッシュ生成とは、ＣＡＤ等で生成された形状を小さな要素の集合に分割する処理である。二次元メッシュには主に三角形メッシュと四角形メッシュがあるが、車の衝突解析等に代表される計算機シミュレーションでは、三角形メッシュでは信頼性のある解が得られない。このため、四角形メッシュが用いられることが多い。ところが、三角形メッシュの自動生成については、例えば、特開平７−２３０４８７号、特開平８−３１５１８３号に記載されたバブルメッシュ法等の技術が確立しているのに対し、四角形メッシュの自動生成は実用に耐えるようなものが少ない。よって、多くの解析者は、例えば車一台のＣＡＤデータに数カ月といった膨大な手作業を伴う手法を用いて四角形メッシュを生成している。
【０００３】
また、三次元形状に対するメッシュ生成機能は、熱・流体解析の分野で需要が大きいが、三次元形状に拡張可能な四角形メッシュ（三次元では六面体メッシュ）の自動生成方法が望まれている。
【０００４】
このように四角形メッシュの自動生成手法の需要は大きいが、自動生成のみが要求ではなく、以下のような要求にも応じられることが望まれている。
（１）生成される四角形要素の歪みが少ないこと
計算力学による解析では、極端に細長い要素や、角度の極端に大きい（又は小さい）角を持つ要素は、解析結果に悪影響を及ぼす。よって、理想的には、全ての四角形要素の形状は正方形に近いことが望ましい。
（２）生成される四角形要素の整列方向が制御できること
計算力学による解析では、応力などの物理量の方向、又は形状領域の境界の方向等に要素が整列していることが望ましい場合が多い。よって、利用者が指定する整列方向に沿って、多くの要素がその方向に規則的に整列したメッシュが生成されることが望ましい。
（３）要素の大きさの分布が制御できること
重要な部分には細かいメッシュ要素を、そうでない部分には粗いメッシュ要素を生成することが計算量低減の観点から望ましい。但し、いきなりメッシュの大きさを変えると、Ｔ構造（隣接要素の節点が弦の上に載る状態）が生じ、解析に悪影響を及ぼす。よって、各要素の接続は互いの共有する節点＋弦で行われることを保証したまま、メッシュの大きさに分布を与えることが重要である。
（４）複雑な曲面形状を対象とできること
ＣＡＤ等で設計される形状には、曲面領域の一部分を切除して得られるトリム曲面や、非常に曲がりくねった曲面形状等、様々な曲面がある。このような曲面形状においても、自動的に四角形メッシュを生成できることが望ましい。
（５）三次元に拡張できること
現在の計算力学を用いた解析は、計算能力の向上に合わせて、二次元から三次元へその対象を広げている。ところが、三次元を対象とした四角形メッシュ（六面体メッシュ）はまだ、非常に少ない。同じ動作原理で、二次元から三次元に拡張可能な手法が望ましい。
【０００５】
先に述べたバブルメッシュ法は、メッシングを行う形状の領域内にバブルを生成し、そのバブルを安定した位置に移動させ、そのバブルの中心点を接続することにより三角形メッシュを作成する。このように三角形メッシュから四角形メッシュを作成するには、主に以下のような方法がある。
（１）２つの隣接する三角形をつなぎ、１つの四角形にする方法
三角形をつなぐ際のペアリングが難しい。また、数が合わないと、三角形が残ってしまう。さらに、三角形２つからできる四角形は、通常平行四辺形であり、メッシュとして好ましい正方形・長方形にはならない。
（２）三角形を３つに分割する手法
異方向性を有する四角形を生成することが難しくなる。
いずれの方法も方向性を考慮した四角形生成には難しい問題を抱えており、この問題に対して位相的にヒューリスティックなルールを適用して解いているのが現状である。また、このように三角形メッシュを四角形に変換する方法では、三次元に拡張することは理論的には可能であっても実用性には欠ける。
【０００６】
四角形メッシュ生成の従来の手法には以下のようなものがある。
（１）ユーザによる領域分割を利用した方法
いわゆる「マップドメッシュ」と呼ばれる手法であり、予めマウス操作等の手作業を三辺又は四辺の領域に分割しておき、分割された各領域を格子状に分割するものである（Ho-Le K., Finite Element Mesh Generation Method: a Review and Classification, Computer Aided Designing, Vol.20, No.1,1988, pp27-38.参照のこと)。この手法では、領域分割が手作業であるため、自動生成という要件に反する。例えば、車一台分の全ての部品にメッシュを生成する場合には、作業が膨大なものになる。また、前処理である、この領域分割の結果はユーザに依存するため、メッシュ生成結果に個人差が生ずるという問題もある。
【０００７】
（２）形状領域の境界から四角形要素を順次生成する方法
いわゆる「アドバンシング・フロント・メッシュ」と言われている手法である（Blacker T.D.,Paving: A New Approach to Automated Quadrilateral Mesh Generation, International Journal for Numerical Methods in Engineering, Vol.32, pp.811-847, 1991参照のこと）。この手法では、領域の境界線に沿って一列に四角形要素を生成し、その内側に一列に四角形要素を生成する処理を、領域が四角形要素で埋め尽くされるまで反復する。このようにすると、領域の内部の要素に歪みが生じやすいので、上で述べた要件（１）を満たすことができない。また、要素の整列方向は領域の境界線方向に制限されるので、要件（２）についても必ずしも十分ではない。
【０００８】
（３）平方／立方格子を領域内部に埋め込む方法
領域の内部に平方格子や立方格子を埋め込み、領域の境界周辺を例外処理によって連結してメッシュを生成する手法である。境界周辺のメッシュの質が非常に悪くなることがあり、解析の精度に影響が出る事が多いので、要件（１）を満たさない。また、要素サイズの制御は困難であるので、要件（３）も満たす事ができない。
【０００９】
【発明が解決しようとする課題】
よって、本発明の目的は、自動的に四角形メッシュを作成可能なメッシング方法を提供することである。
【００１０】
また他の目的は、歪みの少ない四角形メッシュを生成可能なメッシング方法を提供することである。
【００１１】
さらに他の目的は、生成される四角形メッシュの整列方向を指定可能なメッシング方法を提供することである。
【００１２】
さらに他の目的は、二次元空間で実施された方法をそのまま三次元空間で実施できる六面体メッシュ生成方法を提供することである。
【００１３】
さらに他の目的は、複雑な形状にも適用可能な四角形メッシュ生成方法を提供することである。
【００１４】
さらに他の目的は、生成されるメッシュ要素の大きさを制御できる四角形メッシュ生成方法を提供することである。
【００１５】
さらに他の目的は、バブルを用いたメッシングにおいてポテンシャルという概念を用いた新たな方法を提供することである。
【００１６】
【課題を解決するための手段】
従来のバブル・メッシュ法（例えば、特開平７−２３０４８７号、特開平８−３１５１８３号）では、隣接する２個のバブルの分子間力を想定し、バブルの中心に向かって引力や斥力を持たせることで、バブルが六方最密となる状態を求めている。この状態におけるバブルの配列は、正三角形に近い良質な三角形メッシュを生成するのに適している。一方、六方最密でなく正方や六方に整列した分子構造の例に金属結合がある。金属結合では、隣接した分子が電子を共有すると、分子周辺のポテンシャルに異方性が生じ、そのポテンシャルが極小となる方向（電子を共有した分子と９０度の角度をなす方向）に別の分子を引き付ける。本発明では、この金属結合の分子の整列に類似したバブルの整列を実現するために、バブル間力の影響を表すポテンシャル場を仮定し、バブル間力の働く方向を隣接バブルの中心方向に限定せずにその近隣の方向に適応的に仮定することで、バブルが六方最密でない状態でバブル間力を算出する。四角形メッシュを生成する場合及び六角形メッシュを生成する場合には、本発明ではポテンシャルが極小となる隣接点を、４点又は６点それぞれのバブルに設け、その隣接点の方向に隣接バブルに対する引力を働かせることで処理を簡素化する。
【００１７】
以上をまとめると、メッシングの対象となる形状を入力するステップと、メッシングの対象となる形状の領域内に複数のバブルを生成するステップと、バブルに設定されたポテンシャル場により規定される力でバブルを移動させ且つバブル個数を制御することにより、バブルの安定した配置を決定する安定配置決定ステップと、隣接するバブルの中心を接続することにより、メッシュを生成するメッシュ生成ステップとを含む。このように、各バブルにポテンシャル場を設けると、そのポテンシャル場に従うようにバブルを配置することができ、このバブルの配置により所望のメッシュのノードを得る事ができる。
【００１８】
その際に、ポテンシャル場が、バブル周辺の４点で極小となれば、四角形メッシュ用のノードを得ることができ、バブル周辺の６点で極小となれば、六面体メッシュ用のノードを得ることができる。このポテンシャル場が、バブル周辺であって、メッシュの整列方向における点及び当該整列方向に対して垂直な方向における点で極小となるようにすれば、より正方形又は立方体に近いメッシュを得ることができる。
【００１９】
また、ポテンシャル場により規定される力は、バブル周辺でポテンシャルが極小となる点と当該点に隣接するバブルとの間に当該点と隣接するバブルとの間の距離の関数として定義される場合もある。距離の関数とすると力の計算が簡単になるが、これに限定されるものではない。
【００２０】
さらに、ポテンシャル場は、バブル周辺であって且つメッシュの整列方向の線上の２点及び当該整列方向に対して垂直な方向の線上の４点でポテンシャルが極小となり、安定配置決定ステップが、ポテンシャルが極小となる点ごとに、当該極小となる点に隣接するバブルを登録するステップを含み、メッシュ生成ステップが、第１バブルの当該極小となる点に登録されたバブルを用いて、当該第１バブルに接続すべきバブルを選択する選択ステップとを含むようにすることも考えられる。このようにすれば、六面体メッシュを得ることができる。
【００２１】
また、この選択ステップが、最初に、メッシングの対象となる形状の境界面上に配置されたバブルの前記極小となる点に登録されたバブルを用いて、当該バブルに接続すべきバブルを選択するステップと、次いでメッシングの対象となる形状の内部のバブルの前記極小となる点に登録されたバブルを用いて、当該バブルに接続すべきバブルを選択する処理を、メッシングの対象となる形状の内部のバブルに順次実行するステップを含むようにすることも可能である。アドバンシング・フロントの拡張である。
【００２２】
以上述べた処理のフローは、専用の装置として実施することも、また、コンピュータのプログラムとして実施することも可能である。さらに、このコンピュータのプログラムは、ＣＤ−ＲＯＭやフロッピー・ディスク、ＭＯ（Magneto-optic）ディスクなどの記憶媒体に記憶されて流通する。
【００２３】
【発明の実施の形態】
本実施例では、非多様体データ構造のメッシングの例を説明する。図１に非多様体データ構造にて表されるオブジェクトの例を表す。この図１のオブジェクトは、３次元オブジェクトである四面体の立体６００２に、稜線６００５を境界線として２次元オブジェクトである三角形６００４が接している。また、三角形６００４に一次元オブジェクトである直線６００８が点６００７を共有して接している。さらに、立体６００２の１つの側面には一次元オブジェクトである「×」形状の図形が張り付いている。加えて、立体６００２は自身を分ける境界線６０１２を内在している。
【００２４】
では、図１のようなオブジェクトをメッシングする場合の処理フローを図２に示す。最初に、メッシングするオブジェクトと、メッシュの整列方向とを入力する（ステップ１１０）。メッシングするオブジェクトは図１に示したようなオブジェクトである。メッシュの整列方向は、入力されたオブジェクト内部の各メッシュ要素の向きを表すもので、ベクトルで与えられる。三次元形状に対してはテンソル場が与えられる。例えば、平面をメッシングする際には、図３に示すようにメッシュ要素をそろえる方向（図３に描かれた線の方向）を入力する。但し、このような細かさで入力する必要はないし、入力しなくともよい。さらに、この整列方向は自動生成することも可能である。
【００２５】
自動生成する際には、図４（ａ）に示すように、形状領域を覆う直交格子形状を仮想する。そして、この直交格子を形成するそれぞれの格子点について、最も距離の近い境界線を選択し、そのベクトル方向を格子点に与える。そうすると、図４（ｂ）のようにベクトルが各格子点に与えられる。個々のバブルの整列方向は、バブルを囲む４つの格子点に与えられたベクトルを線形補間することで決定する。三次元形状でも、形状領域を覆う直行格子形状を仮想する。そして、この直行格子を形成するそれぞれの格子点について、最も距離の近い境界ノードを選択し、そのノード付近における境界面上のメッシュの整列方向を格子点に与える。これにて三次元への拡張が可能となる。
【００２６】
次に、入力されたオブジェクトの頂点及び稜線にメッシュ・ノードを配置する（ステップ１２０）。この頂点及び稜線の取扱いは、従来のバブル・メッシュ法と変わらない。また、別の方法で実施することも可能である。頂点及び稜線では、本発明を用いる効果がないためである。例えば、特開平７−２３０４８７号に記載されている方法では、（１）頂点にバブルを配置し、（２）稜線上にバブルを配置し、（３）所定の法則で定義されたバブル間力によりバブルを移動させ且つバブルの粗密を検査することによりバブル個数を制御することにより、バブルの安定配置を決定し、（３）バブルの中心をメッシュ・ノードとす。以上で、頂点及び稜線の処理を終了する。
【００２７】
次に、入力されたオブジェクトの面にバブルを初期配置する（ステップ１３０）。本実施例では、このバブルの初期配置で特別なことを実施する必要はない。バブルの大きさについては別途指定する。なお、ベクトルで指定される大きさのバブルを生成し、面内に配置することもできる。
【００２８】
面には上で述べたように平面及び曲面がある。平面については問題は特にないが、曲面については、曲面に対応するパラメータ空間にてバブルを配置し、この配置を曲面にマッピングすることにより、初期配置を実施する方法もある。
【００２９】
次に、バブルの安定配置を決定する（ステップ１４０）。この処理をさらに詳しくすると、以下のようになる。
【表１】
0003963334.tif 000002
【００３０】
以下、この擬似コードを説明する。ここでは、第１０行から第１７０行までを、各バブルの移動距離の中で最大のものが、しきい値以下になるまで繰り返す。全バブルの移動距離の平均値でもよいが、バブルがあまり移動しなくなるまで行う。しきい値により繰り返し回数は制御できるが、大きな値を設定すると、安定しないうちにしきい値以下となって処理が終了してしまう。
【００３１】
第１０行から第１７０行は、大きく３つの部分に分けられる。第１の部分は、第１５行の三角形分割であり、第２の部分はバブル間力及びバブルの移動を計算する第２０行から第７０行、第３の部分はバブル個数の制御を行う第８０行から第１６０行までである。
【００３２】
この第１の部分である第１５行は、バブル間の隣接関係を把握するための三角形分割である。三角形分割の方法としては、例えばDelaunay三角形分割を用いればよい。なお、バブルとバブルがどのように接続しているかを判断するために三角形分割を実施するので、三角形分割しないで隣接関係がわかるのであれば、三角形分割しなくともよい。
【００３３】
第２の部分である第３０行から７０行は、さらに３つの部分に分けられる。第４０行は、計算対象のバブルに隣接するバブルを特定して、そのバブルに、ポテンシャル場を設定する。このポテンシャル場は、四角形メッシュの場合、例えば、図５のようなポテンシャル場とすることが可能である。但し、図５のように広がりのある場を規定し、それに従う力を計算することとすると、計算量が膨大になる。よって、本実施例では、図６のような、１つのバブルの周辺であって、バブル中心を通り且つ直行する２本の線分上の４点に、ポテンシャル極小の点を定義する。なお、本実施例では、図２のステップ１１０で、整列方向がベクトルとして入力されているので、このベクトルの方向とそれに直行する方向が、図６における直行する２本の線分となる。
【００３４】
次に、第５０行で、隣接するバブルのポテンシャル場からの力の和を計算する。バブルは、本実施例では円（二次元の場合、三次元では球）であり、質量ｍを有する仮想的な物体である。全てのバブルは同一の質量を持つようにしてもよいし、バブルの大きさ等によって異なる質量を設定することも可能である。このような物体間に働く力を図７を用いて説明する。隣接するバブルＡの中心点をｘA、半径ｒAとし、入力されたベクトルｖA、その法線方向ＮとベクトルｖAの外積によって得られるベクトルをｖBとする（ｖA及びｖBは単位ベクトル）。この時、ポテンシャル極小点の位置ｘA1，ｘA2，ｘA3，ｘA4は以下のようになる。
ｘA1＝ｘA＋２ｒAｖA
ｘA2＝ｘA−２ｒAｖA
ｘA3＝ｘA＋２ｒAｖB
ｘA4＝ｘA−２ｒAｖB
【００３５】
そして、計算対象バブルＢは、隣接バブルＡのポテンシャル極小点のうち最も距離の短い点ＡCから力を受ける事とする。このバブルＡの中心とバブルＢの中心の距離ｄABを用いると、ＡＢ間の力ＦABは以下のようになる。
【数１】
0003963334.tif 000003
なお、バブルＢの半径をｒBとする。また、ｆ（ｘ）を図８のような関数とする。但し、本実施例ではこのｆ（ｘ）の絶対値を用いているので、実際は図９のような関数となる。
【００３６】
このＦABを、計算対象バブルＢに隣接する全てのバブルについて計算し、加算する。図１０にバブル間力計算の処理フローを示す。
【００３７】
なお、ここでバブルの中心点を接続するための情報を記憶しておくとよい。すなわち、ポテンシャル極小点に最も近いバブルを、ポテンシャル極小点に対応して記憶するのである。例えば、図７においてバブルＢはバブルＡのｘA4を最も距離の短い点ＡCなので、このｘA4にバブルＢを登録する。この登録の意味は、メッシュ要素の辺の意味である。すなわち、このようにバブルを移動させながら、要素の辺を動的に接続するという意味である。なお、境界線上のバブルについては、境界線に垂直な方向にポテンシャル極小点を設けることとする。
【００３８】
続いて第６０行は、実際にバブルを移動させる処理である。これは、どれだけバブルが移動するのかということを計算すればよい。ここでは、個々のバブルを質量ｍの質点とみなし（慣性モーメントを有しない）、上記のバブル間力と粘性を考慮して二階の常微分方程式を解くことによって、バブルの位置を変化させる。ニュートン方程式は次のようになる。
【数２】
0003963334.tif 000004
ここで、ｘiはｉ番目のバブルのｘ座標、ｍiはｉ番目のバブルの質量、ｙiはｉ番目のバブルのｙ座標、ｚiはｉ番目のバブルのｚ座標である。一階微分の項は粘性係数ｃiを含み、粘性を考慮した項である。この粘性係数は、各バブルごとに、またｘ、ｙ、ｚ方向で、それぞれ違う値を設定することができるが、全て一定の値ｃとすることも可能である。数２の右辺のｆxi（ｔ），ｆyi（ｔ）及びｆzi（ｔ）は、それぞれ時間ｔにおけるｉ番目のバブルに対する、隣接バブルからの力の、ｘ成分の和とｙ成分の和とｚ成分の和である。
【００３９】
この数２をRunge-Kutta法などの周知の常微分方程式の数値解析技法により、時間ｔを△ｔだけ増分して、個々のバブルの座標値を計算する。先に述べたように、擬似コードの第１０行から第１７０行の繰り返しは、移動距離がしきい値以下であるか判断して決定されるものであるから、移動距離（△x,△y,△z）も計算する。元の座標値は分かっているから、移動距離（△x,△y,△z）のみ計算してもよい。なお、常微分方程式の数値解析技法としては、Runge-Kutta法に限定されず、Adamsの方法、Eulerの方法などを用いてもよい。例えば、洲之内 治男著、サイエンス社、理工系の数学１５、「数値計算」、１９７８年９月などを参照のこと。
【００４０】
このような擬似コード第４０行及び第６０行の処理を、全てのバブルについて実行する。ここまでの処理で、微小時間△ｔ後の各バブルの座標（及び又は移動距離（△x,△y,△z））が計算できた。
【００４１】
なお、移動させると面内にとどまらないバブルも存在する。曲面の場合には、このようなバブルについては、面内に引き戻す処理を実施する。これには、例えば面の法線方向にバブルを面上に引き戻す等の処理が考えられが、その他の方法でもよい。また、平面の場合そのようなバブルを破壊する。
【００４２】
次に、第３の部分である第８０行から第１６０行までの、バブルの追加又は削除に関する処理について説明する。第９０行は、各三角形の辺ごとに以下の処理を繰り返すとなっているが、この三角形は、先に述べた擬似コード第１５行の三角形分割によって生成されたメッシュの三角形である。但し、擬似コード第１５行の処理の後に、バブルは移動しているので、もう一度、第８０行の前で三角形分割を実行してもよいが、実行するか否かは任意である。そして第１１０行では、三角形の辺と交点を有する２つのバブルの半径の和に対する、当該三角形の辺の長さの比が、第１のしきい値以下であるか判断する。すなわち、バブルとバブルの間に隙間が空き過ぎているか判断する。これにより、第１のしきい値以下であると判断された場合には、当該三角形の辺の中点にバブルを１つ生成する（擬似コード第１２０行）。
【００４３】
一方、求められた比が、第２のしきい値以上であると判断された場合（擬似コード第１３０行）には、三角形の辺の両端のいずれかのバブルを消滅させる（同第１４０行）。これは、バブルが詰り過ぎているということを示している。もし、どちらの条件にも合致しないような辺については、何も実施しない。このようにして、バブル個数の適応的制御が実施される。
【００４４】
ここでは、三角形の辺を中心としたバブル個数制御を説明したが、本発明はこの方法に限定されず、例えば従来技術の欄で示した特開平８−３１５１８３号に記載された重複度による方法を用いることもできる。なお、この後の処理のため、ここで再度三角形分割を実施することが好ましい。
【００４５】
処理が第１０行に戻ると、第６０行で計算されたバブルの移動距離の最大がしきい値を越えているかの判断が行われる。移動距離は、（△x2+△y2+△z2)0.5を用いてもよいし、単純に｜△x｜+｜△y｜+｜△z｜として用いることも可能である。もし、最大の移動距離がしきい値を越えている場合には、再度第１０行乃至第１７０行の処理を実施し、しきい値を越えていない場合には、後の処理に移行する。しきい値を越えていない場合には、バブルは安定的に配置されたと見なされる。
【００４６】
以上の処理が、図２におけるステップ１４０の処理である。次に、四角形メッシュを生成する（図２，ステップ１５０）。バブルの中心点を接続するわけであるが、これは従来のアドバンシング・フロント（従来技術の欄で示した技術）や、三角形メッシュからの変換などの手法によって実現できる。
【００４７】
このアドバンシング・フロントは、領域の境界線上に設けられた隣接２ノードを接続した線分を１つ選択し、隣接２ノードの各々から指定された距離に近い距離離れたノードを選択し、隣接２ノード及び選択されたノードを接続することによって、三角形要素又は四角形要素を生成する。しかし、所定距離離れたノードを選択するのは、処理が大変であるから、本実施例では、上述のように各バブルのポテンシャル極小点に登録されたバブルをもちいて、接続すべきノードを選択する。
【００４８】
図１１に処理の概要を示す。初めに、境界線上の隣接する２ノードを選択する（ステップ１０１０）。この隣接２ノードのポテンシャル極小点のうち、境界線の法線方向であって隣接２ノードの中点からの半直線となす角が最小の点を、隣接２ノードのそれぞれについて検出する（ステップ１０２０）。検出された点に登録されたバブルのうち半直線から最も距離の短いバブルの中心を、隣接２ノードともにメッシュの１要素を形成するノードとして接続する（ステップ１０３０）。この処理を境界線上のすべてのノードについて処理（ステップ１０４０）。このようにすると、図１２に示すように境界から１段領域内のメッシュ要素が生成できたことになる。
【００４９】
そして、全てのノードを処理するまで、上に述べた「境界線」を「新たに接続した隣接ノード間の辺」としてステップ１０１０に戻る（ステップ１０５０）。そして、全てのノードについて処理すれば、処理を終了する（ステップ１０７０）。
【００５０】
また、三角形分割する方法では、例えば Delaunay三角メッシュ生成法などの既存の三角メッシュ生成法によって、バブルの中心点を結んで三角メッシュを生成し、この三角メッシュを形成する三角形要素をできるだけ多くペアにして四角形要素に変換する。本発明によって２次元領域に生成されたバブルを用いることで、三角メッシュからの変換手法をそのまま適用して四角メッシュを生成することができる。この時、本発明によって生成されたバブルを用いて生成された三角メッシュは、正三角形に近い良質なメッシュではなく、正方形に近い四角形を対角線で２個に割った三角形（直角二等辺三角形）に近いメッシュになる。この三角形をペアにして四角形に変換すれば、自ずから大半の要素は正方形に近い四角形要素となるので、従来における欠点は除去されている。
【００５１】
なお、どちらの手法を用いても、本発明で生成したバブルから、大半の要素は四角形要素であるメッシュを生成することが出来る。ただし、本発明では、すべての要素が四角形要素になることは保証せず、三角形要素が混入する可能性がある。しかし、解析の現場では若干の三角形要素が混入したメッシュを四角メッシュとして用いていることが多いので問題はない。また、すべての要素が四角形要素になることを保証するには、例えば、特許番号２６４２０７０号に示す手法のように、三角メッシュを生成してからそれを四角メッシュに変換し、さらにそれを半分の要素サイズの四角メッシュに変換すればよい。
【００５２】
以上のようにすると、面についてのメッシングが終了する。
【００５３】
次に、３次元の空間に六面体メッシュを生成する。最初に、空間にバブルを初期配置する（図２、ステップ１６０）。ここまでの処理で、頂点、稜線及び面についてはバブルの安定的な配置を計算しているので、頂点、稜線及び面についてはそれらを用い、例えば図１の立体６００２の内部にのみバブルを配置する。
【００５４】
そして、バブルの安定配置を計算する（ステップ１７０）。この計算は、面についての処理とほぼ同じである。但し、差異は以下の通りである。（１）ポテンシャル極小点は、図１３に示すように、４点でなく６点となる。これらの点の位置ｘA1，ｘA2，ｘA3，ｘA4、ｘA5、ｘA6は以下のようになる。
ｘA1＝ｘA＋２ｒAｖA
ｘA2＝ｘA−２ｒAｖA
ｘA3＝ｘA＋２ｒAｖB
ｘA4＝ｘA−２ｒAｖB
ｘA5＝ｘA＋２ｒAｖC
ｘA6＝ｘA−２ｒAｖC
ここで、ｖCは、ｖAに垂直な別の単位ベクトルである。
【００５５】
また、（２）アドバンシング・フロントの応用でノードを接続し、メッシュ要素を形成する際には、隣接２ノードではなく、既に生成された四角形要素を構成する４ノードについて処理を行う。さらに、半直線の起点は、四角形要素の重心である。図１４に境界面上の四角形メッシュ要素ＡＢＣＤの場合の例を示す。点線矢印は、ＡＢＣＤの重心からの半直線である。この方向となす角度が小さく且つ半直線から距離の近い登録されたバブルＥＦＧＨが選択されている。Ａ及びＢから点線で連結されている点線バブルは、Ｅ及びＦよりも半直線となす角度が大きいために選択されなかったものである。
【００５６】
（３）この図１４の場合、ＡＢＣＤの各々にＥＦＧＨがそれぞれ対応しているが、もし、ＥＦＧＨに重複が存在する場合には、四角形２個及び三角形２個に囲まれる要素、三角柱、四角錐、四角形２個及び三角形２個に囲まれる要素が生成される。四角形２個及び三角形２個に囲まれる要素、四角形２個及び三角形２個に囲まれる要素が生成された場合には、四面体に分割することができ、他の形状であっても、必要に応じて六面体を生成することができる。また、これらの形状の要素が混入していても影響が少ない場合も多い。
【００５７】
（４）面から外れたバブルを面上に引き戻す処理に触れたが、空間から外れたバブルは単に削除するのみである。このような変更を考慮すれば、面についての処理は、容易に空間についての処理に拡張可能である。
【００５８】
以上、四角形メッシュ及び六面体メッシュ生成の実施例を説明した。しかし、本発明は以上の実施例に限定されるものではない。たとえば、アドバンシング・フロントの一拡張例を示したが、アドバンシング・フロントをさらに他の態様に変形して適用することもできる。また、アドバンシング・フロントを時間をかけておこなうことも可能である。さらに、ノードの接続方法で、Delaunay三角形メッシュ方法が示されているが、これだけでなく他の方法であってもよい。また、ここではバブルの形は円形又は球形を前提にして説明したが、正方形でなく長方形のメッシュを必要とする場合には、楕円バブルを用いればよい。メッシングの対象形状が曲面を有する場合には、パラメータ空間でバブル（円又は楕円）を移動させ、もとの曲面にマッピングするようなことも可能である。
【００５９】
これまで述べた処理は、通常のコンピュータ・プログラムとして具現化することができる。そして、例えば図１５で示すようなコンピュータ・システムにおいて実行可能である。この場合、コンピュータ・プログラム及び必要なデータはハードディスク・ドライブＨＤＤに格納されており、必要に応じてメインメモリに呼び出され、ＣＰＵにて実行される。データは、キーボードやフロッピー・ディスク・ドライブＦＤＤその他の記憶媒体、また、モデム等の通信機器によって接続された通信回線から供給され得る。コンピュータ・プログラムも他のコンピュータ・システムから送られてくるようにしてもよい。同様に、コンピュータ・プログラムはＦＤやＣＤ−ＲＯＭその他の記憶媒体にて提供される場合がある。本発明の処理結果は、ＨＤＤなどに記憶された他のコンピュータ・プログラムによって数値解析等に用いられる。さらに、表示装置や印刷装置によってユーザに提示することも可能である。
【００６０】
さらに、本発明は専用の装置にて実施することも可能である。例えば、上記処理の各ステップを実行するようなモジュールを作成して、それらのモジュールのデータのやり取りによって最終結果を出力するように構成することできる。また、上記実施例では三角形分割処理を何回も実施するようになっているので、この三角形分割処理のみを実行するモジュールを作成し、そのモジュールを共用するような構成を作ることも可能である。
【００６１】
【効果】
自動的に四角形メッシュを作成可能なメッシング方法を提供することができた。
【００６２】
歪みの少ない四角形メッシュを生成可能なメッシング方法を提供することができた。
【００６３】
生成される四角形メッシュの整列方向を指定可能なメッシング方法を提供することができた。
【００６４】
二次元空間で実施された方法をそのまま三次元空間で実施できる六面体メッシュ生成方法を提供することができた。
【００６５】
複雑な形状にも適用可能な四角形メッシュ生成方法を提供することができた。
【００６６】
生成されるメッシュ要素の大きさを制御できる四角形メッシュ生成方法を提供することができた。
【００６７】
バブルを用いたメッシングにおいてポテンシャルという概念を用いた新たな方法を提供することができた。
【図面の簡単な説明】
【図１】入力されたオブジェクトの例を説明するための図である。
【図２】本発明の処理フローを示した図である。
【図３】整列方向の例を説明するための図である。
【図４】整列方向の自動生成を説明するための図である。
【図５】バブルに設定されるポテンシャル場の一例を示すための図である。
【図６】バブルに設定されるポテンシャル場の一例を示すための図である。
【図７】バブルに設定されるポテンシャル極小点を説明するための図である。
【図８】本実施例におけるバブル間力定義中の関数ｆ（ｘ）を説明するための図である。
【図９】｜ｆ（ｘ）｜を示す図である。
【図１０】バブル間力計算処理フローを示した図である。
【図１１】二次元におけるアドバンシング・フロントの応用の処理フローを説明するための図である。
【図１２】二次元におけるアドバンシング・フロントの応用を説明するための図である。
【図１３】球バブルに設定されるポテンシャル極小点の位置を説明するための図である。
【図１４】三次元におけるアドバンシング・フロント法の応用を説明するための図である。
【図１５】通常のコンピュータ・システムを説明するための図である。
【符号の説明】
１００−１９０  処理ステップ
【図１】
0003963334.tif 000005
【図２】
0003963334.tif 000006
【図３】
0003963334.tif 000007
【図４】
0003963334.tif 000008
【図５】
0003963334.tif 000009
【図６】
0003963334.tif 000010
【図７】
0003963334.tif 000011
【図８】
0003963334.tif 000012
【図９】
0003963334.tif 000013
【図１０】
0003963334.tif 000014
【図１１】
0003963334.tif 000015
【図１２】
0003963334.tif 000016
【図１３】
0003963334.tif 000017
【図１４】
0003963334.tif 000018
【図１５】
0003963334.tif 000019