Loading article…
メッシュ生成とは、連続的な幾何学的空間を離散的な幾何学的セルと位相的セルに分割したメッシュを作成する手法です。 [ 1 ] これらのセルは単体複体を形成することがよくあります。通常、セルは幾何学的入力領域を分割します。メッシュセルは、より大きな領域の離散的な局所近似として使用されます。メッシュは、領域の複雑さと必要なメッシュの種類に応じて、コンピュータアルゴリズムによって、多くの場合GUIを介した人間のガイダンスによって作成されます。典型的な目標は、入力領域の形状を正確に捉え、高品質（形状が適切）なセルを持ち、後続の計算が扱いにくくなるほどセルの数が多くないメッシュを作成することです。また、後続の計算にとって重要な領域では、メッシュは細かく（要素が小さい）する必要があります。
メッシュは、コンピュータ画面へのレンダリングや、有限要素解析や計算流体力学などの物理シミュレーションに使用されます。[ 2 ]メッシュは、三角形などの単純なセルで構成されています。たとえば、三角形に対して有限要素計算（工学）やレイトレーシング（コンピュータグラフィックス）などの操作を実行する方法はわかっていますが、道路橋のような複雑な空間や形状に対してこれらの操作を直接実行する方法はわかりません。各三角形に対して計算を実行し、三角形間の相互作用を計算することで、橋の強度をシミュレートしたり、コンピュータ画面に描画したりできます。
主な違いは、構造化メッシュと非構造化メッシュの違いです。構造化メッシュでは、メッシュは配列などの規則的な格子であり、要素間の接続が暗黙的に保証されています。非構造化メッシュでは、要素は不規則なパターンで互いに接続される可能性があり、より複雑な領域を捉えることができます。このページは主に非構造化メッシュについて説明しています。メッシュは三角形分割である可能性がありますが、メッシュ作成のプロセスは、入力に存在しない頂点を追加する自由度がある点で、点集合三角形分割とは異なります。製図用のCADモデルを「ファセット化」（三角形分割）する場合も、頂点を追加する自由度は同じですが、目標は、できるだけ少ない三角形を使用して形状を正確に表現することであり、個々の三角形の形状は重要ではありません。テクスチャやリアルな照明条件のコンピュータグラフィックスレンダリングでは、代わりにメッシュが使用されます。
多くのメッシュ生成ソフトウェアは、入力を定義するCADシステムと、出力を取得するシミュレーションソフトウェアと連携しています。入力は多岐にわたりますが、一般的な形式としては、ソリッドモデリング、ジオメトリックモデリング、NURBS、B-rep、STL 、または点群などがあります。
「メッシュ生成」、「グリッド生成」、「メッシング」、「グリッディング」という用語はしばしば同義語として使われますが、厳密に言えば後者の2つはより広義で、メッシュの改善、つまり、その上で実行される数値計算の速度や精度を向上させる目的でメッシュを変更することを含みます。コンピュータグラフィックスのレンダリングや数学では、メッシュはテッセレーションと呼ばれることもあります。
メッシュの面（セル、エンティティ）は、その次元とメッシュが使用されるコンテキストによって異なる名称を持ちます。有限要素法では、最も次元の高いメッシュエンティティは「要素」と呼ばれ、1次元は「エッジ」、0次元は「ノード」と呼ばれます。要素が3次元の場合、2次元のエンティティは「面」と呼ばれます。計算幾何学では、0次元の点は頂点と呼ばれます。正四面体はしばしば「テット」、三角形は「トリス」、四角形は「クワッド」、正六面体（トポロジカルキューブ）は「ヘックス」と略されます。
多くのメッシュ生成手法は、ドロネー三角形分割の原理と、ルパートのアルゴリズムなどの頂点を追加するルールに基づいて構築されています。特徴的なのは、まず空間全体の粗い初期メッシュが形成され、次に頂点と三角形が追加されることです。対照的に、前進フロントアルゴリズムはドメイン境界から開始し、要素を段階的に追加して内部を埋めていきます。ハイブリッド手法は両方を行います。前進フロント手法の特殊なクラスは、流体の流れに対して要素の薄い境界層を作成します。構造化メッシュ生成では、メッシュ全体が正方形の規則的なグリッドなどの格子グラフになります。ブロック構造化メッシュでは、ドメインは大きなサブ領域に分割され、それぞれが構造化メッシュになります。いくつかの直接法は、ブロック構造化メッシュから開始し、入力に適合するようにメッシュを移動します。ポリキューブに基づく自動六角形メッシュ生成[ 3 ]を参照してください。別の直接法は、ドメイン境界で構造化セルをカットすることです。マーチングキューブに基づくスカルプトを参照してください。[ 4 ]
メッシュの種類によっては、作成が他の種類よりもはるかに難しいものがあります。単体メッシュは立方体メッシュよりも作成しやすい傾向があります。重要なカテゴリの1つは、固定された四角形サーフェスメッシュに準拠した六角形メッシュを生成することです。研究のサブエリアでは、正方台形多面体などの特定の小さな構成のメッシュの存在と生成を研究しています。この問題の難しさから、組み合わせ六角形メッシュの存在は、良好な幾何学的実現を生成する問題とは別に研究されてきました。六面体メッシュ生成のための組み合わせ的手法を参照してください。既知のアルゴリズムは、保証された最小品質で単体メッシュを生成しますが、立方体メッシュではそのような保証はまれであり、多くの一般的な実装では、一部の入力から反転した（裏返しの）六角形が生成されます。
メッシュは、後続の計算がスーパーコンピュータ上で並列に行われる場合でも、ワークステーション上で直列に作成されることがよくあります。これは、ほとんどのメッシュ生成ツールが対話型であるという制約と、メッシュ生成の実行時間がソルバーの実行時間に比べて通常ごくわずかであるためです。ただし、メッシュが大きすぎて単一の直列マシンのメモリに収まらない場合、またはシミュレーション中にメッシュを変更（適応）する必要がある場合は、メッシュ生成は並列で行われます。
代数的手法によるグリッド生成は、数学的補間関数に基づいています。これは、任意の形状の領域を取り、1次元、2次元、または3次元の既知の関数を使用して行われます。計算領域は長方形ではないかもしれませんが、簡略化のために、領域は長方形であると仮定します。この方法の主な利点は、物理的なグリッドの形状と間隔を明示的に制御できることです。境界に適合した計算メッシュを生成するために使用できる最も単純な手順は、正規化変換です。[ 5 ]
ノズルの場合、記述関数グリッドは、 y方向の均一な分割とx方向の等間隔の増分を使用して簡単に生成できます。
どこはノズル壁の y 座標を表します。 の値が与えられた場合 (、) の値 (、)は簡単に復元できます。
代数的手法と同様に、微分方程式法もグリッド生成に用いられます。偏微分方程式（PDE）を用いる利点は、グリッド生成方程式の解を利用してメッシュを生成できる点にあります。グリッド構築は、3種類の偏微分方程式すべてを用いて行うことができます。
楕円型偏微分方程式は一般的に非常に滑らかな解を持ち、滑らかな等高線が得られます。その滑らかさを利点として、調和関数の最大値原理の結果としてヤコビアンが正になることがわかっているラプラス方程式が好ましいです。Crowley (1962) と Winslow (1966) [ 6 ]がポアソン方程式を用いてマッピングしながら物理領域を計算平面に変換する偏微分方程式に関する広範な研究を行った後、Thompson ら (1974) [ 7 ]は楕円型偏微分方程式を用いてグリッドを生成する研究を広範に行いました。ポアソングリッドジェネレータでは、目的のグリッド点をマークすることによってマッピングが行われます。物理領域の境界上において、内部の点分布は、以下の式を解くことによって決定される。
どこ、は計算領域内の座標であり、PとQはD内の点間隔を表します。上記の式を計算空間に変換すると、次の形式の2つの楕円型偏微分方程式が得られます。
どこ
これらの連立方程式は、等間隔のグリッド上の計算平面で解かれ、物理空間内の各点の座標。楕円型偏微分方程式を使用する利点は、それに関連する解が滑らかであり、結果として得られるグリッドが滑らかであることです。しかし、PとQの指定が困難になるため、欠点も加わります。さらに、グリッドは各時間ステップ後に計算する必要があり、計算時間が長くなります。[ 8 ]
このグリッド生成スキームは、物理的問題を記述する偏微分方程式のタイプと一致する開領域を持つ問題に一般的に適用可能です。双曲型偏微分方程式の利点は、グリッド生成のために支配方程式を一度だけ解けばよいことです。初期点分布と近似境界条件が必要な入力となり、解はその後外側に向かって進みます。StegerとSorenson（1980）[ 9 ]は、メッシュ生成に双曲型偏微分方程式を使用する体積直交法を提案しました。2次元問題の場合、計算空間は次のように与えられます。ヤコビ行列の逆行列は次のように与えられる。
どここれは、計算空間内の特定の領域に対する物理空間内の領域を表します。2番目の式は、物理空間の境界におけるグリッド線の直交性を関連付けており、次のように記述できます。
のためにそして面が垂直になるようにすると、方程式は次のようになります。
このような方程式系に関連する問題は、選択が不十分衝撃や、メッシュ全体への情報の不連続な伝播につながる可能性があります。一方、メッシュは直交しているため非常に迅速に生成され、この方法の利点となります。
解法は双曲型偏微分方程式の解法と似ており、初期データ面から解を進めて、最後に境界条件を満たすようにする。中村（1982）とエドワーズ（1985）は放物線格子生成の基本概念を開発した。この概念はラプラス方程式またはポアソン方程式のいずれかを使用し、特に楕円挙動を制御する部分を扱っている。初期値は、表面に沿った点の座標として与えられる。境界条件を満たす物体の外面への解の進展端。
これまで、グリッド間隔の制御については提案されてこなかった。中村とエドワーズは、不均一な間隔を用いることでグリッド制御を実現した。放物線状のグリッド生成は、双曲状のグリッド生成に比べて、衝撃や不連続性がなく、比較的滑らかなグリッドが得られるという利点がある。ただし、初期値の指定やステップサイズの選択によるグリッド点の制御には時間がかかるが、習熟と経験を積めば、これらの手法は効果的となる。
この手法は、グリッドの滑らかさ、直交性、および体積変動を最小化する技術を含んでいます。この手法は、グリッド生成問題を解決するための数学的基盤を形成します。この手法では、各反復後に新しいメッシュによって代替グリッドが生成され、後方差分法を使用してグリッド速度が計算されます。この技術は強力ですが、グリッドに関連する方程式を解くのに労力が必要となるという欠点があります。CPU時間を短縮するために、積分を最小化するためのさらなる研究が必要です。
この方式の主な重要性は、グリッドを自動的に生成する方法を提供することです。この方法を使用すると、グリッドは要素の表面に応じてブロックに分割され、適切な接続性を確保するための構造が提供されます。データフローを解釈するためにソルバーが使用されます。非構造化方式が採用される場合、主な関心はユーザーの要求を満たすことであり、このタスクを実行するためにグリッドジェネレータが使用されます。構造化方式では、グリッド間ではなくセル間で情報が格納されるため、より多くのメモリ領域が必要になります。ランダムなセル位置のため、非構造化方式のソルバーの効率は、構造化方式と比較して低くなります。[ 10 ]
グリッド構築時には、いくつかの点に留意する必要があります。高解像度のグリッドポイントは、構造化グリッドと非構造化グリッドの両方で困難を引き起こします。たとえば、境界層の場合、構造化スキームでは流れの方向に細長いグリッドが生成されます。一方、非構造化グリッドでは、誤差を避けるためにセルが可能な限り正三角形である必要があるため、境界層でより高いセル密度が必要になります。[ 11 ]
計算メッシュ内のセルとそのすべての隣接セルを識別するために必要な情報を特定する必要があります。非構造格子では、任意の点を任意の場所に配置できます。点挿入スキームを使用して点を個別に挿入し、セルの接続性を決定します。これは、点が挿入される際に識別される必要があることを示唆しています。
新たな接続を確立するためのロジックは、点が挿入された時点で決定されます。グリッドセルを識別するグリッド点を形成するデータが必要です。各セルが形成されると、番号が付けられ、点がソートされます。さらに、隣接セルの情報も必要です。
従来の方法で偏微分方程式を解く際の問題点は、解の詳細が判明する前にグリッドが構築され、物理領域に点が配置されることです。そのため、グリッドが与えられた問題に対して最適であるとは限りません。[ 12 ]
適応法は、解の精度を向上させるために使用されます。適応法は、メッシュ細分化を使用する場合は「h」法、グリッド点の数が固定されていて再分配されない場合は「r」法、有限要素理論で解法の次数を上げる場合は「p」法と呼ばれます。等分布スキームを使用した多次元問題は、いくつかの方法で解決できます。最も理解しやすいのは、拡散を目的のセル体積の倍数として設定し、重み関数の等分布に基づく制御関数を備えたポアソングリッドジェネレータです。等分布スキームは、非構造化問題にも適用できます。問題は、メッシュ点の移動が非常に大きい場合、接続性が阻害されることです。
この適応法を用いることで、定常流と時間精度の高い流量計算の両方を解くことができます。定常流問題では、グリッドを細分化し、所定の反復回数後にグリッドを適応させます。解が収束すると、グリッドは変化への適応を停止します。時間精度の高いケースでは、物理問題の偏微分方程式とグリッドの動きを記述する偏微分方程式の結合が必要となります。
画像ベースメッシュ生成とは、磁気共鳴画像法（MRI）、コンピュータ断層撮影法（CT） 、マイクロトモグラフィーなどの3D画像データから、計算流体力学（CFD）や有限要素解析（FEA）用のコンピュータモデルを自動的に作成するプロセスです。現在、さまざまなメッシュ生成技術が利用可能ですが、これらは通常、コンピュータ支援設計（CAD）からモデルを生成するために開発されたものであり、3D画像データからのメッシュ生成には困難が伴います。
人工知能 (AI) と機械学習 (ML) の最近の進歩は、メッシュ生成に大きな影響を与え、従来は労働集約的だったプロセスを自動化し、計算シミュレーションの精度を向上させています。[ 13 ]ニューラルネットワークや強化学習などの AI 駆動技術は、最適なメッシュ構成を予測し、メッシュを適応的に細分化し、有限要素解析 (FEA) や計算流体力学 (CFD) における手動介入を減らすことができます。[ 14 ] [ 15 ]
NVIDIA、Ansys、Siemensなどの企業は、AIベースのメッシュ生成ツールをシミュレーションソフトウェアに統合し、航空宇宙、自動車、生物医学工学のワークフローを加速させている。[ 16 ] [ 17 ]
通常、セルは多角形または多面体であり、領域を分割するメッシュを形成します。 [ 18 ] 2 次元要素の重要なクラスには、三角形 (単体) と四角形 (位相正方形) があります。3 次元では、最も一般的なセルは四面体 (単体) と六面体 (位相立方体) です。 単体メッシュは任意の次元を持つことができ、重要な例として三角形 (2D) と四面体 (3D) が含まれます。 立方体メッシュは、四角形 (2D) と六面体 (3D) を含む全次元カテゴリです。3D では、4 面ピラミッドと 3 面プリズムが混合セルタイプの適合メッシュに現れます。
メッシュは、通常は2 次元または3 次元の幾何学的空間に埋め込まれますが、時間次元を追加することで次元が 1 つ増える場合もあります。[ 19 ]ニッチなコンテキストでは、より高次元のメッシュが使用されます。[ 20 ] 1 次元のメッシュも有用です。重要なカテゴリはサーフェス メッシュで、これは曲面を表すために 3D に埋め込まれた 2D メッシュです。
双対グラフはメッシュ生成においていくつかの役割を果たします。ドロネー三角形分割単体メッシュを双対化することで、多面体ボロノイ図メッシュを作成できます。サーフェスの配置を生成し、交差グラフを双対化することで、立方体メッシュを作成できます（空間ツイスト連続体を参照）。場合によっては、元のメッシュとその双対メッシュの両方が同じシミュレーションで使用されます（ホッジスター演算子を参照）。これは、フラックスと渦度、電気と磁気など、発散演算子と回転演算子を含む物理現象から生じます。これらの物理現象では、一方の変数が元の面に存在し、その対応する変数が双対面に存在します。
有限要素解析用に作成される 3 次元メッシュは、四面体、ピラミッド、プリズム、または六面体で構成される必要があります。[ 21 ]有限体積法で使用されるメッシュは、任意の多面体で構成されます。有限差分法で使用されるメッシュは、マルチブロック構造メッシュとして知られる、六面体の区分的構造配列で構成されます。4 面ピラミッドは、六面体を四面体に適合的に接続するのに役立ちます。3 面プリズムは、オブジェクトの奥深くの四面体メッシュに適合する境界層に使用されます。
表面メッシュは、物体の表面が光を反射する（表面下散乱も含む）コンピュータグラフィックスにおいて、完全な3Dメッシュが不要な場合に有用です。表面メッシュは、自動車製造における板金や建築における建物の外装など、薄い物体をモデル化するためにも使用されます。高次元（例えば17次元）の立方体メッシュは、天体物理学や弦理論でよく用いられます。
メッシュの正確な定義とは何でしょうか？すべての文脈に適用できる普遍的に受け入れられた数学的記述はありません。しかし、いくつかの数学的対象は明らかにメッシュです。単体複体は単体から構成されるメッシュです。ほとんどの多面体（例えば立方体）メッシュは等角メッシュであり、単体複体の一般化であるCW複体のセル構造を持っています。メッシュは単体である必要はありません。セルの任意のノードのサブセットが必ずしもセルであるとは限らないからです。例えば、四角形の3つのノードはセルを定義しません。しかし、2つのセルはセルで交差します。例えば、四角形の内部にはノードがありません。2つのセルの交差は複数のセルになる場合があります。例えば、2つの四角形は2つの辺を共有する場合があります。交差が複数のセルになることは、場合によっては禁止されており、望ましくないことです。メッシュ改善手法（例えばピローイング）の目的は、これらの構成を取り除くことです。場合によっては、トポロジーメッシュと、埋め込みが特定の品質基準を満たす幾何学的メッシュとを区別することがある。
CW 複合体ではない重要なメッシュのバリアントには、セルが厳密に面と面を合わせないが、それでもセルが領域を分割する非適合メッシュがあります。その例として、要素の面が隣接する要素の面によって分割されるオクツリーがあります。このようなメッシュは、フラックスベースのシミュレーションに役立ちます。オーバーセット グリッドでは、幾何学的に重なり合い、領域を分割しない複数の適合メッシュがあります。たとえば、OVERset グリッド FLOW ソルバーである Overflow を参照してください。いわゆるメッシュレスまたはメッシュフリーの方法では、多くの場合、領域のメッシュのような離散化が使用され、重なり合うサポートを持つ基底関数があります。各シミュレーションの自由度点の近くにローカル メッシュが作成されることがあり、これらのメッシュは重なり合い、互いに非適合になる場合があります。
暗黙的な三角形分割はデルタ複合体に基づいています。各三角形について、その辺の長さと、面の辺間の接着マップが定義されます。（詳細を記述してください）
多くのメッシュでは線形要素が使用され、抽象要素から実現要素へのマッピングは線形であり、メッシュのエッジは直線セグメントです。高次の多項式マッピング、特に二次多項式が一般的です。高次要素の主な目的は、領域境界をより正確に表現することですが、メッシュ内部でも精度上の利点があります。立方体メッシュの動機の1つは、線形立方体要素が二次単体要素と同様の数値的利点をいくつか持っていることです。等幾何解析シミュレーション手法では、領域境界を含むメッシュセルは、線形または多項式近似の代わりにCAD表現を直接使用します。
メッシュを改善するには、離散的な接続性、セルの連続的な幾何学的位置、またはその両方を変更します。離散的な変更の場合、単体要素ではエッジを交換し、ノードを挿入/削除します。立方体（四角形/六面体）メッシュでも同様の操作が行われますが、可能な操作は少なく、局所的な変更が全体的な影響を及ぼします。たとえば、六面体メッシュの場合、2つのノードをマージすると六面体ではないセルが作成されますが、四角形の対角線上のノードをマージし、これが六面体の面接続列全体を縮退するように伝播すると、残りのすべてのセルは依然として六面体になります。適応型メッシュ細分化では、計算対象の関数の勾配が大きい領域で要素が分割されます（h細分化）。効率化のために要素が削除され、メッシュが粗大化されます。マルチグリッド法は、メッシュを実際に変更することなく、細分化と粗大化に似た処理を行い、数値計算を高速化します。
連続的な変化に対応するため、ノードを移動したり、要素の多項式の次数を変更して高次元の面を移動したりします。ノードを移動して品質を向上させることを「平滑化」または「r-リファインメント」と呼び、要素の次数を上げることを「p-リファインメント」と呼びます。また、オブジェクトの形状が時間とともに変化するシミュレーションでもノードを移動します。これにより、要素の形状が劣化します。オブジェクトが十分に変形すると、オブジェクト全体が再メッシュされ、現在の解が古いメッシュから新しいメッシュにマッピングされます。
この分野は学際性が非常に高く、数学、コンピュータサイエンス、工学の分野から貢献が見られます。メッシュ生成の研究開発は、計算幾何学と同様に、離散数学と連続数学、計算に等しく重点を置いている点が特徴ですが、グラフ理論（離散）や数値解析（連続）とは対照的です。メッシュ生成は見た目以上に難しいものです。人間は与えられたオブジェクトのメッシュを作成する方法を容易に理解できますが、任意の入力に対して事前に適切な判断を下すようにコンピュータをプログラムするのは困難です。自然界や人工物には無限の種類の幾何学が存在します。多くのメッシュ生成研究者は、メッシュの最初のユーザーでした。メッシュ生成は、メッシュを作成するのにかかる人間の時間と、メッシュが完成した後に計算を設定して解く時間を比較すると、はるかに長い時間を要するため、引き続き広く注目され、支援と資金提供を受けています。これは、数値シミュレーションとコンピュータグラフィックスが発明されて以来ずっと続いてきた状況です。コンピュータハードウェアと単純な方程式解法ソフトウェアが向上するにつれて、人々はより高い忠実度、科学的洞察、芸術的表現を求めて、より大規模で複雑な幾何学的モデルに惹きつけられてきたからです。
メッシュ生成に関する研究は、幅広い分野の学術誌に掲載されています。これは、研究の進歩に必要な学際的な性質と、メッシュを利用する多様なアプリケーションを反映しています。年間約150件のメッシュ生成に関する論文が20誌の学術誌に掲載され、1誌あたりの掲載数は最大でも20件です。メッシュ生成を主要テーマとする学術誌はありません。年間10件以上のメッシュ生成論文を掲載する学術誌は太字で示しています。
（メッシュ生成を主要テーマとする会議は太字で示しています。）
メッシュ構造を主なテーマとするワークショップは太字で表示しています。
多くの市販製品の説明では、シミュレーションを可能にするメッシュ生成技術よりも、シミュレーションそのものが強調されている。
これらのツールは、マルチマテリアル有限要素モデリングに必要な分割メッシュを生成します。
メッシュ生成アルゴリズムとメッシュを比較するための有用なモデル（入力）とメッシュ（出力）。
モデリングエンジンは、メッシュ生成ソフトウェアと連携して、ドメインの形状を表現する。
メッシュを記述するための一般的な（出力）ファイル形式。
