Pochodové čtverce - Marching squares - Wikipedia

Pochodové čtverce je počítačová grafika algoritmus který generuje obrysy pro dvourozměrný skalární pole (obdélníkový pole jednotlivých číselných hodnot). Podobnou metodu lze použít pro konturování 2D trojúhelníkové sítě.

Obrysy mohou být dvou druhů:

  • Izoliny - řádky sledující jednu datovou úroveň, nebo - hodnota.
  • Isobands - vyplněné oblasti mezi izolovanými liniemi.

Mezi typické aplikace patří vrstevnice na topografických mapách nebo generování izobarů pro mapy počasí.

Pochodové čtverce zaujímají podobný přístup jako 3D pochodové kostky algoritmus:

  • Zpracujte každou buňku v mřížce samostatně.
  • Vypočítejte index buněk pomocí srovnání úrovní vrstev s datovými hodnotami v rozích buněk.
  • Použijte předem připravený vyhledávací tabulka, zadané do indexu buňky, k popisu výstupní geometrie pro buňku.
  • Aplikovat lineární interpolace podél hranic buňky pro výpočet přesné polohy obrysu.

Základní algoritmus

Tady jsou kroky algoritmu:

Aplikujte práh na 2D pole a vytvořte binární obrázek obsahující:

  • 1, kde je datová hodnota výše hodnota
  • 0, kde je datová hodnota níže hodnota

Každý blok 2x2 pixelů v binárním obrazu tvoří konturovací buňku, takže celý obraz je reprezentován mřížkou takových buněk (na obrázku níže zeleně). Všimněte si, že tato konturovací mřížka je o jednu buňku menší v každém směru než původní 2D pole.

Pro každou buňku v konturovací mřížce:

  1. Vytvořte 4 bity v rozích buňky k vytvoření binárního indexu: projděte buňku v a ve směru hodinových ručiček směr připojující bit do indexu pomocí bitové NEBO a levý Shift, z nejvýznamnější bit vlevo nahoře do nejméně významný bit vlevo dole. Výsledný 4bitový index může mít 16 možných hodnot v rozsahu 0–15.
  2. Pomocí indexu buněk získáte přístup k předem vytvořenému vyhledávací tabulka se 16 položkami se seznamem okrajů potřebných k reprezentaci buňky (zobrazeno v pravé dolní části obrázku níže).
  3. Aplikovat lineární interpolace mezi původními hodnotami dat pole najít přesnou polohu vrstevnice podél okrajů buňky.

Ilustrace algoritmu pochodové čtverce.

Rozcestník sedlových bodů

Obrys je nejednoznačný sedlové body. Nejasnost je možné vyřešit pomocí průměrný datová hodnota pro střed buňky pro výběr mezi různými spoji interpolovaných bodů:

Pochodové čtverce

Isobands

Podobný algoritmus lze vytvořit pro vyplněná obrysová pásma v rámci horní a dolní prahové hodnoty:

Pochodové čtverce v případě izobandu

Tvarovací trojúhelníkové sítě

Lze použít stejný základní algoritmus trojúhelníkové sítě, které se skládají ze spojených trojúhelníků s daty přiřazenými k vrcholům. Například rozptýlenou sadu datových bodů lze připojit k a Delaunayova triangulace umožnit konturování datového pole. Trojúhelníková buňka je vždy rovinný, protože to je 2-simplexní (tj. určené n + 1 vrcholy v n-dimenzionálním prostoru). Vždy existuje jedinečný lineární interpolant přes trojúhelník a žádná možnost nejednoznačného sedla.

Izoliny

Analýza pro isoliny přes trojúhelníky je obzvláště jednoduchý: existují 3 binární číslice, takže 8 možností:

Pouzdra pochodových trojúhelníků, pouzdro isoline

Isobands

Analýza pro isobands přes trojúhelníky vyžaduje 3 ternární triky, takže 27 možností:

Pochodové případy trojúhelníků, izobandový případ

Rozměry a mezery

The datový prostor pro algoritmus Marching Squares je 2D, protože vrcholy přiřazené datové hodnotě jsou spojeny s jejich sousedy ve 2D topologické mřížka, ale prostorové souřadnice přiřazené vrcholům mohou být ve 2D, 3D nebo vyšších rozměrech.

Například trojúhelníková síť může představovat 2D datový povrch vložený do 3D prostoru, kde prostorové polohy vrcholů a interpolovaných bodů podél obrysu budou mít všechny 3 souřadnice. Všimněte si, že případ čtverců je opět nejednoznačný, protože a čtyřúhelník vložený do 3-dimenzionálního prostoru nemusí být nutně rovinný, takže existuje možnost výběru geometrického interpolačního schématu pro kreslení páskovaných povrchů ve 3D.

Úvahy o výkonu

Algoritmus je trapně paralelní, protože všechny buňky jsou zpracovávány nezávisle. Je snadné napsat a paralelní algoritmus za předpokladu:

  • Sdílené skalární pole pouze pro čtení.
  • Sdílený výstupní proud geometrie pouze pro připojení.

Naivní implementace Marching Squares, která zpracovává každou buňku samostatně, provede každou lineární interpolace dvakrát (isoline) nebo čtyřikrát (isoband). Podobně bude výstup obsahovat 2 kopie 2D vrcholů pro disjunktní čáry (isoline) nebo 4 kopie pro polygony (isobands). [Za předpokladu, že: mřížka je velká, takže většina buněk je interních; a vytváří se celá souvislá sada izopásem.]

Je možné snížit výpočetní režii o ukládání do mezipaměti výsledky interpolace. Například sériová verze s jedním vláknem by potřebovala ukládat do mezipaměti interpolované výsledky pouze pro jeden řádek vstupní mřížky.

Je také možné zmenšit velikost výstupu pomocí indexovaných geometrických primitiv, tj. vytvořit pole 2D vrcholů a zadejte čáry nebo mnohoúhelníky pomocí krátké celé číslo posuny do pole.

Reference

  • Maple, C. (2003). Geometrický design a plánování prostoru pomocí algoritmů pochodových čtverců a pochodových krychlí. Proc. 2003 mezinárodní Konf. Geometrické modelování a grafika. str. 90–95. doi:10.1109 / GMAG.2003.1219671. ISBN  978-0-7695-1985-2.
  • Banks, D. C. (2004). Msgstr "Počítání případů v substitučních algoritmech". IEEE Trans. Vizuální. Comp. Grafika. 10 (4): 371–384. CiteSeerX  10.1.1.582.7221. doi:10.1109 / TVCG.2004.6. PMID  18579966.
  • Laguardia, J. J .; Cueto, E .; Doblaré, M. (2005). "Metoda Galerkinova přirozeného souseda se strukturou čtyřstromu". Int. J. Numer. Pervitin. Inženýr. 63 (6): 789–812. Bibcode:2005IJNME..63..789L. doi:10,1002 / nme.1297.
  • Schaefer, Scott; Warren, Joe (2005). "Duální pochodové kostky: kontury prima a duální mřížky". Comp. Graf. Fórum. 24 (2): 195–201. doi:10.1111 / j.1467-8659.2005.00843.x.
  • Mantz, Huber; Jacobs, Karin; Mecke, Klaus (2008). "Využití funkčních prvků Minkowski pro analýzu obrazu: algoritmus pochodového čtverce". J. Stat. Mech .: Theory Exp. 2008 (12): P12015. Bibcode:2008JSMTE..12..015M. doi:10.1088 / 1742-5468 / 2008/12 / P12015.
  • Cipolletti, Marina P .; Delrieux, Claudio A .; Perillo, Gerardo M. E .; Piccolo, M. Cintia (2012). Msgstr "Segmentace hranic a měření v rozlišeních vzdáleného průzkumu". Comp. Geosci. 40: 87–97. Bibcode:2012CG ..... 40 ... 87C. doi:10.1016 / j.cageo.2011.07.015.

externí odkazy