Marschierende Plätze - Marching squares

Marching Squares ist eine Computergrafik - Algorithmus , der erzeugt Konturen für einen zweidimensionalen Skalarfeld (rectangular Array einzelner Zahlenwerte). Eine ähnliche Methode kann verwendet werden, um 2D- Dreiecksnetze zu konturieren .

Die Konturen können zweierlei sein:

  • Isolinien – Linien, die einer einzelnen Datenebene oder Isowert folgen .
  • Isobänder – gefüllte Bereiche zwischen Isolinien.

Typische Anwendungen sind die Höhenlinien auf topografischen Karten oder die Generierung von Isobaren für Wetterkarten.

Marching Squares verfolgt einen ähnlichen Ansatz wie der 3D- Marching-Cubes- Algorithmus:

  • Verarbeiten Sie jede Zelle im Raster unabhängig.
  • Berechnen Sie einen Zellenindex, indem Sie Vergleiche der Konturebene(n) mit den Datenwerten an den Zellenecken verwenden.
  • Verwenden Sie eine vorgefertigte Nachschlagetabelle , die auf dem Zellenindex basiert, um die Ausgabegeometrie für die Zelle zu beschreiben.
  • Wenden Sie eine lineare Interpolation entlang der Grenzen der Zelle an, um die genaue Konturposition zu berechnen.

Grundalgorithmus

Hier sind die Schritte des Algorithmus:

Wenden Sie einen Schwellenwert auf das 2D-Feld an, um ein binäres Bild zu erstellen, das Folgendes enthält:

  • 1, wobei der Datenwert über dem Isowert liegt
  • 0, wobei der Datenwert unter dem Isowert liegt

Jeder 2x2-Pixelblock im Binärbild bildet eine Konturierungszelle, sodass das gesamte Bild durch ein Gitter solcher Zellen dargestellt wird (im Bild unten grün dargestellt). Beachten Sie, dass dieses Konturierungsraster in jede Richtung eine Zelle kleiner ist als das ursprüngliche 2D-Feld.

Für jede Zelle im Konturierungsraster:

  1. Stellen Sie die 4 Bits an den Ecken der Zelle zusammen, um einen binären Index zu erstellen: Gehen Sie im Uhrzeigersinn um die Zelle herum und hängen Sie das Bit an den Index an, indem Sie bitweises ODER und Linksverschiebung verwenden , vom höchstwertigen Bit oben links zum kleinsten signifikantes Bit unten links. Der resultierende 4-Bit-Index kann 16 mögliche Werte im Bereich 0-15 haben.
  2. Verwenden Sie den Zellenindex, um auf eine vorgefertigte Nachschlagetabelle mit 16 Einträgen zuzugreifen, die die Kanten auflisten, die zur Darstellung der Zelle erforderlich sind (siehe unten rechts im Bild unten).
  3. Wenden Sie eine lineare Interpolation zwischen den ursprünglichen Felddatenwerten an, um die genaue Position der Höhenlinie entlang der Kanten der Zelle zu ermitteln.

Marching Squares Algorithmus Abbildung.

Begriffsklärung von Sattelpunkten

An Sattelpunkten ist die Kontur mehrdeutig . Es ist möglich, die Mehrdeutigkeit aufzulösen, indem man den durchschnittlichen Datenwert für die Mitte der Zelle verwendet, um zwischen verschiedenen Verbindungen der interpolierten Punkte zu wählen (vier Bilder in der unteren rechten Ecke):

Marschplätze

Isobänder

Ein ähnlicher Algorithmus kann für gefüllte Konturbänder innerhalb von oberen und unteren Schwellenwerten erstellt werden:

Marschquadrate im Isoband-Gehäuse

Konturierende Dreiecksnetze

Der gleiche Grundalgorithmus kann auf Dreiecksnetze angewendet werden , die aus verbundenen Dreiecken mit den Eckpunkten zugeordneten Daten bestehen. Beispielsweise könnte ein verstreuter Satz von Datenpunkten mit einer Delaunay-Triangulation verbunden werden , um eine Konturierung des Datenfelds zu ermöglichen. Eine dreieckige Zelle ist immer planar , weil sie ein 2-Simplex ist ( dh spezifiziert durch n+1 Ecken in einem n-dimensionalen Raum). Es gibt immer eine eindeutige lineare Interpolation über ein Dreieck und keine Möglichkeit eines mehrdeutigen Sattels.

Isolinien

Die Analyse für Isolinien über Dreiecken ist besonders einfach: Es gibt 3 Binärziffern, also 8 Möglichkeiten:

Marschdreiecke Fälle, Isolinien Fall

Isobänder

Die Analyse für Isobänder über Dreiecken erfordert 3 ternäre Trits, also 27 Möglichkeiten:

Marschdreiecke Koffer, Isoband Koffer

Abmessungen und Abstände

Der Datenraum für den Marching Squares-Algorithmus ist 2D, da die einem Datenwert zugewiesenen Scheitelpunkte mit ihren Nachbarn in einem topologischen 2D- Gitter verbunden sind, die den Scheitelpunkten zugewiesenen Raumkoordinaten jedoch in 2D, 3D oder höheren Dimensionen sein können.

Ein dreieckiges Netz kann beispielsweise eine 2D-Datenoberfläche darstellen, die in einen 3D-Raum eingebettet ist, wobei die räumlichen Positionen der Scheitelpunkte und interpolierten Punkte entlang einer Kontur alle 3 Koordinaten aufweisen. Beachten Sie, dass der Fall von Quadraten wieder mehrdeutig ist, da ein Viereck, das in einen dreidimensionalen Raum eingebettet ist, nicht unbedingt planar ist. Daher gibt es eine Auswahl des geometrischen Interpolationsschemas, um die gebänderten Oberflächen in 3D zu zeichnen.

Leistungsüberlegungen

Der Algorithmus ist peinlich parallel , weil alle Zellen unabhängig voneinander verarbeitet werden. Es ist einfach, einen parallelen Algorithmus zu schreiben, vorausgesetzt:

  • Gemeinsames schreibgeschütztes Eingabeskalarfeld.
  • Geteilter Ausgabestream für Geometrie nur zum Anhängen.

Eine naive Implementierung von Marching Squares, die jede Zelle unabhängig verarbeitet, führt jede lineare Interpolation zweimal (Isoline) oder viermal (Isoband) durch. Ebenso enthält die Ausgabe 2 Kopien der 2D-Scheitelpunkte für disjunkte Linien (Isolinie) oder 4 Kopien für Polygone (Isobänder). [Unter der Annahme, dass: das Gitter groß ist, so dass die meisten Zellen intern sind; und ein vollständiger zusammenhängender Satz von Isobändern wird erstellt.]

Es ist möglich , den Rechenaufwand zu reduzieren , indem das Zwischenspeichern der Ergebnisse der Interpolation. Beispielsweise müsste eine serielle Singlethread-Version nur interpolierte Ergebnisse für eine Zeile des Eingaberasters zwischenspeichern.

Es ist auch möglich, die Größe der Ausgabe durch indizierte geometrische Primitive zu reduzieren, dh ein Array von 2D-Scheitelpunkten zu erstellen und Linien oder Polygone mit kurzen ganzzahligen Offsets in das Array zu spezifizieren .

Verweise

  • Ahorn, C. (2003). Geometrisches Design und Raumplanung mit den Marschquadraten und Marschwürfelalgorithmen . Proz. 2003 Intl. Konf. Geometrische Modellierung und Grafiken . S. 90–95. doi : 10.1109/GMAG.2003.1219671 . ISBN 978-0-7695-1985-2.
  • Banken, DC (2004). „Fälle in Substitopen-Algorithmen zählen“. IEEE-Trans. Visuell. Komp. Grafiken . 10 (4): 371–384. CiteSeerX  10.1.1.582.7221 . doi : 10.1109/TVCG.2004.6 . PMID  18579966 .
  • Laguardia, JJ; Cueto, E.; Doblaré, M. (2005). „Ein natürlicher Nachbar Galerkin-Methode mit Quadtree-Struktur“. Int. J. Nummer. Meth. Ingenieur . 63 (6): 789–812. Bibcode : 2005IJNME..63..789L . doi : 10.1002/nme.1297 .
  • Schäfer, Scott; Warren, Joe (2005). "Dual Marching Cubes: Prima Contouring und Dual Grids". Forum für Computergrafik . 24 (2): 195–201. doi : 10.1111/j.1467-8659.2005.00843.x .
  • Mantz, Huber; Jacobs, Karin; Mecke, Klaus (2008). „Verwendung von Minkowski-Funktionalen für die Bildanalyse: ein Marschquadrat-Algorithmus“. J.Stat. Mech.: Theorie Exp . 2008 (12): P12015. Bibcode : 2008JSMTE..12..015M . doi : 10.1088/1742-5468/2008/12/P12015 .
  • Cipolletti, Marina P.; Delrieux, Claudio A.; Perillo, Gerardo ME; Piccolo, M. Cintia (2012). "Superauflösende Grenzsegmentierung und Messung in Fernerkundungsbildern". Komp. Geosci . 40 : 87–97. Bibcode : 2012CG.....40...87C . doi : 10.1016/j.cageo.2011.07.015 .

Externe Links