PL 
EnglishDomyślny
Українська〰️ Marching Squares
Wyznaczaj izolinie w dwuwymiarowym polu skalarnym metodą marching squares z tablicą 16 przypadków. Przeciągaj metakule, przełącz się na szum lub malowanie i rozstrzygnij słynną niejednoznaczność siodła.
O algorytmie Marching Squares
Marching Squares to algorytm grafiki komputerowej do wyodrębniania izokonturów (linii stałej wartości) z dwuwymiarowego pola skalarnego próbkowanego na regularnej siatce. Każdy kwadrat 2×2 komórek siatki ma cztery wartości narożne; progowanie każdego narożnika względem izowartości tworzy 4-bitowy indeks (0–15), dający 16 możliwych konfiguracji. Tabela przeglądowa mapuje każdą konfigurację na jeden lub dwa odcinki linii przybliżające miejsce przecięcia konturu z komórką, a interpolacja liniowa na krawędzi daje dokładność podkomórkową. Algorytm jest dwuwymiarowym poprzednikiem trójwymiarowej metody Marching Cubes (Lorensen i Cline, 1987), używanej w obrazowaniu medycznym do rekonstrukcji powierzchni z danych CT/MRI.
Symulacja pozwala przeciągać metakule (źródła pola potencjału) po płótnie, przesuwać próg izowartości i obserwować w czasie rzeczywistym, jak 16-przypadkowa tabela przeglądowa generuje gładkie linie konturowe. Dwa przypadki komórek siodłowych (indeksy 5 i 10) są niejednoznaczne; symulator rozstrzyga je poprzez bilinearną interpolację wartości środkowej, by wybrać poprawną topologię.
Najczęściej zadawane pytania
Dlaczego w tabeli przeglądowej Marching Squares jest dokładnie 16 przypadków?
Każdy z czterech narożników komórki jest niezależnie klasyfikowany jako powyżej (1) lub poniżej (0) izowartości, co daje 2⁴ = 16 możliwych wzorców bitowych. Dzięki symetrii wiele przypadków to obroty lub odbicia innych, redukując odrębne geometrie do około 4 unikalnych kształtów. Pełna 16-wpisowa tabela przeglądowa przechowuje predefiniowane pary przecięć krawędzi dla każdego wzorca, umożliwiając implementację bez rozgałęzień, wektoryzowaną.
Czym jest niejednoznaczność punktu siodłowego i jak jest rozstrzygana?
Przypadki 5 (0101) i 10 (1010) mają dwa przeciwległe po przekątnej narożniki „wewnątrz”, tworząc niejednoznaczność co do tego, czy kontur łączy się w kształt X, czy jako dwa oddzielne łuki. Standardowym rozwiązaniem jest próbkowanie pola skalarnego w środku komórki: jeśli wartość środkowa przekracza izowartość, dwa narożniki wewnętrzne są połączone; w przeciwnym razie są oddzielne. Ta bilinearna dezambiguacja daje topologicznie spójne kontury.
Jak interpolacja liniowa poprawia dokładność konturu?
Bez interpolacji odcinki konturu przyciągałyby się do środków krawędzi komórki, tworząc wygląd schodkowy. Interpolacja liniowa umieszcza punkt przecięcia w t = (iso − v₀) / (v₁ − v₀) wzdłuż krawędzi między wartościami narożnymi v₀ i v₁, dzięki czemu odcinek linii dokładnie śledzi miejsce, gdzie pole skalarne równa się izowartości. Dla gładkich pól dramatycznie redukuje to wizualny aliasing bez dodatkowego kosztu próbkowania.
Czym jest Marching Cubes i jak wiąże się z Marching Squares?
Marching Cubes to trójwymiarowe uogólnienie: każda komórka sześcienna ma 8 narożników, dając 2⁸ = 256 przypadków (zredukowanych do 15 kanonicznych dzięki symetrii). Wyodrębnia triangulowane izopowierzchnie z danych wolumetrycznych, takich jak medyczne skany CT i symulowane pola płynów. Wprowadzony przez Lorensena i Cline'a na SIGGRAPH 1987, stał się jednym z najczęściej cytowanych artykułów w grafice komputerowej, z obrazowaniem medycznym (rekonstrukcja powierzchni MRI) jako kluczowym zastosowaniem.
Jakie typy pól skalarnych może konturować Marching Squares?
Działa dowolne pole skalarne 2D: temperatura z modelu pogodowego, ciśnienie w symulacji płynów, odległość do najbliższej przeszkody (dla renderowania pól odległości ze znakiem), potencjał elektrostatyczny, wysokość terenu lub suma funkcji bazowych radialnych (metakule). Algorytm jest niezależny od typu pola i wymaga jedynie wartości próbkowanych na regularnej siatce.
Jak metakule wiążą się z tą symulacją?
Metakule to źródła punktowe, których wkład w pole maleje wraz z odległością: f(x, y) = Σ rᵢ² / ((x−xᵢ)² + (y−yᵢ)²). Sumowanie kilku metakul tworzy gładkie, bryłowate pole skalarne, które łączy się i rozdziela w miarę ruchu źródeł. Marching Squares wyodrębnia izokontur przy wybranym progu, tworząc charakterystyczne organiczne kształty „bryłek” spopularyzowane w demach grafiki komputerowej lat 80.
Jaka jest złożoność czasowa Marching Squares?
Dla siatki M × N komórek algorytm przetwarza każdą komórkę dokładnie raz: czas O(MN) i pamięć O(MN) na wartości siatki. Wyodrębnienie konturu na komórkę ma złożoność O(1) dzięki tabeli przeglądowej. W praktyce wąskim gardłem jest często obliczanie pola skalarnego (np. sumowanie k wkładów metakul na komórkę kosztuje O(kMN)), więc do zrównoleglenia obliczeń pola dla zastosowań interaktywnych w czasie rzeczywistym używa się shaderów obliczeniowych GPU.
Czy Marching Squares obsługuje pola animowane lub zmienne w czasie?
Tak — jest powszechnie używany do renderowania powierzchni płynów w czasie rzeczywistym, konturów symulacji ognia oraz interaktywnych edytorów metakul. Ponieważ każda komórka jest niezależna, algorytm idealnie zrównolegla się na GPU. Implementacje zwykle uruchamiają obliczanie pola i wyodrębnianie konturu jako przebiegi shaderów obliczeniowych/fragmentowych, osiągając tysiące klatek na sekundę na nowoczesnym sprzęcie dla umiarkowanych rozmiarów siatki (np. 256×256).
Czy istnieje algorytm dualny do Marching Squares?
Dual Contouring to alternatywa, która umieszcza wierzchołki konturu wewnątrz każdej komórki zamiast na krawędziach, wykorzystując zarówno wartości skalarne, jak i informację o gradiencie (normalne) do pozycjonowania wierzchołków. Lepiej zachowuje ostre cechy (narożniki, grzbiety), które Marching Squares zaokrągla, kosztem konieczności posiadania danych gradientowych i bardziej złożonego śledzenia topologii. Jest preferowany dla mechanicznych modeli CAD i powierzchni poziomicowych o ostrych cechach.
O tej symulacji
To interaktywna implementacja algorytmu konturowania Marching Squares, który wyodrębnia izolinie — krzywe stałej wartości — z dwuwymiarowego pola skalarnego na siatce. Cztery narożniki każdej komórki są porównywane z izowartością, tworząc 4-bitowy indeks wybierający jedną z 16 konfiguracji linii z tabeli przeglądowej, z krawędziami interpolowanymi dla gładkich konturów.
🔬 Co pokazuje
Płótno renderuje mapę cieplną pola skalarnego na żywo z izoliniami na wierzchu. Włączenie indeksów komórek etykietuje każdą aktywną komórkę jej 4-bitową konfiguracją i podświetla dwa niejednoznaczne przypadki siodłowe na bursztynowo.
🎮 Jak korzystać
Wybierz typ pola (Metakule, Szum, Sinusoidalne lub Malowanie), a następnie dostosuj Rozdzielczość siatki i suwak Izowartość. Przeciągaj metakule na płótnie, zaznacz Wielopoziomowy dla pięciu izolinii, Pokaż mapę cieplną lub Pokaż indeksy komórek dla diagnostyki oraz Rozstrzygaj siodła, by rozwiązać niejednoznaczność przypadków 5 i 10.
💡 Czy wiesz, że?
Marching Squares to bezpośredni dwuwymiarowy przodek Marching Cubes (Lorensen i Cline, 1987), używanego do rekonstrukcji powierzchni 3D z medycznych skanów CT i MRI — jednego z najczęściej cytowanych artykułów w grafice komputerowej.
Najczęściej zadawane pytania
Dlaczego dokładnie 16 przypadków w tabeli przeglądowej?
Każdy z czterech narożników komórki jest klasyfikowany powyżej lub poniżej izowartości, dając 24 = 16 wzorców bitowych. Tabela przeglądowa przechowuje poprawne odcinki dla każdego przypadku, więc geometria nigdy nie wymaga obliczania w locie.
Czym jest niejednoznaczność punktu siodłowego, którą naprawia „Rozstrzygaj siodła”?
Przypadki 5 i 10 mają dwa przeciwległe po przekątnej narożniki powyżej izowartości, więc kontur mógłby łączyć się jako X lub jako dwa łuki. Rozstrzyganie siodeł próbkuje środek komórki i wybiera topologię spójną z otaczającym polem.
Dlaczego suwak izowartości tak mocno zmienia kontury?
Izowartość to próg testowany na każdym narożniku, więc jej przesuwanie „kroi” pole na innej wysokości. Blisko środka metakuli pole jest wysokie, więc wysoka izowartość daje małe ciasne pętle, a niska — duże, połączone bryły.
Co robi tryb Wielopoziomowy?
Rysuje pięć izolinii rozłożonych wokół bieżącej izowartości, podobnie do linii poziomic na mapie, ułatwiając odczytanie ogólnego kształtu i stromości pola w porównaniu z pojedynczym progiem.
Czym tryb Malowanie różni się od pozostałych?
Malowanie zastępuje pole proceduralne polem, które rzeźbisz, przeciągając po płótnie miękkim pędzlem, pokazując, że Marching Squares działa na dowolnym polu skalarnym, nie tylko matematycznym, jak metakule.