行進する四角形

コンピュータグラフィックスにおいて、マーチングスクエアは、2次元スカラー場（個々の数値の長方形配列）の輪郭を生成するアルゴリズムです。同様の方法を使用して、2D三角形メッシュの輪郭を描くことができます。

輪郭には 2 種類あります。

• 等値線– 単一のデータ レベル、または等値に従う線。
• 等値線– 等値線間の塗りつぶされた領域。

代表的な用途としては、地形図上の等高線や天気図の等圧線の生成などがあります。

マーチング スクエアは、3Dマーチング キューブアルゴリズムと同様のアプローチを採用しています。

• グリッド内の各セルを個別に処理します。
• 等高線レベルとセルコーナーのデータ値を比較して、セルインデックスを計算します。
• セル インデックスをキーとする事前に構築されたルックアップ テーブルを使用して、セルの出力ジオメトリを記述します。
• セルの境界に沿って線形補間を適用して、正確な輪郭の位置を計算します。

アルゴリズムの手順は次のとおりです。

2D フィールドにしきい値を適用して、次の内容を含むバイナリイメージを作成します。

• 1 データ値が等値より上である
• データ値が等値より下の場合0

注意: 等値に等しいデータは、一貫して 上または下として扱う必要があります。

バイナリ画像内の 2x2 ピクセル ブロックごとに輪郭セルが形成されるため、画像全体はこのようなセルのグリッドで表されます (下の図では緑色で表示)。この輪郭グリッドは、元の 2D フィールドよりも各方向に 1 セル小さくなっていることに注意してください。

等高線グリッド内の各セルについて:

1. セルの角にある4ビットを組み合わせてバイナリ インデックスを構築します。セルを時計回りに巡回して、左上の最上位ビットから左下の最下位ビットまで、ビット単位の ORと左シフトを使用して、ビットをインデックスに追加します。結果として得られる 4 ビットのインデックスには、0 ～ 15 の範囲で 16 個の値を指定できます。
2. セル インデックスを使用して、セルを表すために必要なエッジをリストする 16 個のエントリを含む事前に構築されたルックアップ テーブルにアクセスします(下の図の右下部分に表示)。
3. 元のフィールド データ値間に線形補間を適用して、セルのエッジに沿った等高線の正確な位置を見つけます。

等高線は鞍点では曖昧です。セルの中心の 平均データ値を使用して補間点の異なる接続を選択することにより、この曖昧さを解決することができます(右下隅の 4 つの画像)。

上限と下限のしきい値内の塗りつぶされた等高線バンドに対しても同様のアルゴリズムを作成できます。

同じ基本アルゴリズムは、頂点にデータが割り当てられた接続された三角形で構成される三角形メッシュにも適用できます。たとえば、散在するデータ ポイントのセットをDelaunay 三角形分割で接続して、データ フィールドを輪郭付けすることができます。

三角形のセルは2 単体(つまり、 n次元空間のn +1 頂点で指定される)であるため、常に平面です。三角形全体には常に一意の線形補間があり、あいまいな鞍点が存在する可能性はありません。

三角形上の等値線の解析は特に簡単です。2進数が3つあるので、8つの可能性があります。

三角形上の等値帯の解析には3 つの三元トリットが必要なので、27 通りの可能性があります。

Marching Squares アルゴリズムのデータ空間は2D です。これは、データ値が割り当てられた頂点が 2Dトポロジグリッド内の隣接頂点に接続されているためです。ただし、頂点に割り当てられる空間座標は 2D、3D、またはそれ以上の次元にすることができます。

たとえば、三角形のメッシュは、3D 空間に埋め込まれた 2D データ サーフェスを表すことができます。この場合、頂点の空間位置と輪郭に沿った補間ポイントはすべて 3 つの座標を持ちます。正方形の場合も、 3 次元空間に埋め込まれた四辺形は必ずしも平面ではないため、あいまいになります。そのため、3D で帯状のサーフェスを描画するための幾何学的補間スキームを選択できます。

このアルゴリズムは、すべてのセルが独立して処理されるため、驚くほど並列です。次のことを前提とすると、並列アルゴリズムを簡単に記述できます。

• 共有の読み取り専用入力スカラー フィールド。
• 追加専用の共有ジオメトリ出力ストリーム。

各セルを独立して処理する Marching Squares の単純な実装では、各線形補間が 2 回 (等値線) または 4 回 (等値帯) 実行されます。同様に、出力には、分離した線 (等値線) の場合は 2D 頂点のコピーが 2 つ、ポリゴン (等値帯) の場合は 4 つ含まれます。[次の仮定のもとで: グリッドは大きく、ほとんどのセルは内部にあり、等値帯の完全な連続セットが作成されます。]

補間の結果をキャッシュすることで、計算オーバーヘッドを削減することができます。たとえば、シングルスレッドのシリアル バージョンでは、入力グリッドの 1 行の補間結果のみをキャッシュする必要があります。

インデックス付きジオメトリ プリミティブを使用して出力のサイズを縮小することもできます。つまり、 2D 頂点の配列を作成し、その配列に短い整数オフセットを持つ線またはポリゴンを指定します。

• Maple, C. (2003)。「マーチング スクエアとマーチング キューブ アルゴリズムを使用した幾何学的デザインと空間計画」。2003国際幾何学的モデリングおよびグラフィックス会議、2003 年。議事録。pp . 90–95。doi :10.1109 / GMAG.2003.1219671。ISBN 978-0-7695-1985-2.S2CID 11320513  。 {{cite book}}:|journal=無視されました (ヘルプ)
• Banks, DC (2004). 「サブスティトープアルゴリズムにおけるケースのカウント」. IEEE Trans. Visual. Comp. Graphics . 10 (4): 371–384. CiteSeerX  10.1.1.582.7221 . doi :10.1109/TVCG.2004.6. PMID  18579966. S2CID  2450480.
• Laguardia, JJ; Cueto, E.; Doblaré, M. (2005). 「四分木構造を持つ自然近傍ガラーキン法」. Int. J. Numer. Methods Eng . 63 (6): 789–812. Bibcode :2005IJNME..63..789L. doi : 10.1002/nme.1297 . S2CID  122746298.
• Schaefer, Scott; Warren, Joe (2005). 「デュアル マーチング キューブ: デュアル グリッドのプライマリ コンターリング」.コンピュータ グラフィックス フォーラム. 24 (2): 195–201. doi :10.1111/j.1467-8659.2005.00843.x. S2CID  10015045.
• マンツ、フーバー。ジェイコブス、カリン。メッケ、クラウス (2008)。 「画像解析のためのミンコフスキー汎関数の利用: マーチングスクエア アルゴリズム」。J.Stat.機械: 理論実験2008 (12): 12015。ビブコード:2008JSMTE..12..015M。土井：10.1088/1742-5468/2008/12/P12015。S2CID  122873298。
• Cipolletti, Marina P.; Delrieux, Claudio A.; Perillo, Gerardo ME; Piccolo, M. Cintia (2012). 「リモートセンシング画像における超解像度境界セグメンテーションと測定」。Comp . Geosci . 40 : 87–97. Bibcode :2012CG.....40...87C. doi :10.1016/j.cageo.2011.07.015.

• マーチング スクエア Matlab アルゴリズム – わかりやすいオープンソースのマーチング スクエア アルゴリズム。
• Javaでの実装
• Java の Marching Squares コード。2D データ セットとしきい値を指定すると、簡単にプロットできるように GeneralPath[] を返します。
• 蛇行する三角形の説明とサンプルの Python 実装。
• C 言語の Marching Squares コード – 三角形メッシュをエクスポートして簡単にレンダリングできる、Marching Squares 用の単一ヘッダー ライブラリ。