Wykonywanie Obramowań z Konturami Kwadratów: Rysowanie Linii Konturowych Przez Siatkę Liczb

Od liczb na siatce do linii na ekranie

Izobary map klimatycznych, kontury wysokości na mapach topograficznych oraz miękkie, kropkowate "metabale" w grach wideo są wszystkim tym tego samego podmiotu: masz pole skalarne – jedno liczbowe w każdym punkcie siatki – i chcesz narysować krzywą, gdzie to pole przekracza wybranego progu. Algorytm marching squares jest standardowym rozwiązaniem tego problemu, działającym krok po kroku dla małej 2x2 komórki siatki.

Cztery rogi, szesnaście przypadków

Każda komórka siatki ma cztery rogi, a każdy z nich jest albo powyżej progu ("wewnątrz", bit = 1), albo poniżej niego ("na zewnątrz", bit = 0). Czterech bitów daje dokładnie 16 możliwych konfiguracji, i każda z nich posiada ustaloną, wstępnie obliczoną linię, która pokazuje, jak kontur przecina komórkę – prosta tabela, nie potrzeba żadnej logiki rozgałęziającej poza budowanie indeksu 4-bitowego.

index = (górnyLewy >= próg ? 8 : 0) | (prawyGórny >= próg ? 4 : 0) | (dolnyPrawy >= próg ? 2 : 0) | (lewyDolny >= próg ? 1 : 0) // indeks 0 i 15 → brak linii (wszystkie rogi po tej samej stronie) // indeks 1, 2, 4, 8 i ich komplementy → jeden z rogów przecięty linią // indeks 3, 6, 9, 12 → dwa sąsiadujące rogi przecięte, jedna linia prostopadle przezroczysta // indeks 5, 10 → dwa przypadki SADDLE, patrz niżej Aby uzyskać gładki wynik linii zamiast zawsze przecinającej dokładną środkową część krawędzi, punkt przecięcia jest umieszczany poprzez interpolację liniową między wartościami rogów: jeśli jeden z rogów jest znacznie powyżej progu, a jego sąsiad ledwo powyżej, punkt przecięcia znajduje się blisko drugiego rogu, nie w połowie między nimi. Ta pojedyncza korekta przekształca blokowy schodowaty wzór w kontur, który wygląda jakby został narysowany ręką.

index = (topLeft >= threshold ? 8 : 0)
      | (topRight >= threshold ? 4 : 0)
      | (bottomRight >= threshold ? 2 : 0)
      | (bottomLeft >= threshold ? 1 : 0)

// index 0 and 15  → no line  (all corners on the same side)
// index 1, 2, 4, 8 and their complements → one corner cut off by a line
// index 3, 6, 9, 12 → two adjacent corners cut off, one line straight across
// index 5, 10       → the two SADDLE cases, see below

Dwałowość siodełka

Dwóch spośród szesnaściu przypadków jest rzeczywiście niejednoznaczny: indeks 5 i indeks 10, gdzie oba przeciwległe rogi przekątne są jednocześnie "wewnątrz" a druga para przekątnych jest jednocześnie "na zewnątrz". Cztery przecięcia krawędzi są jednoznaczne samodzielnie, ale istnieje dwa różne, równie poprawne sposoby połączenia ich w linie – jedna interpretacja rysuje dwie oddzielne małe łuki odcinające każdy wewnętrzny róg, a druga rysuje dwie długie łuki przechodzące blisko siebie bez nigdy się nie stykania. Obie są lokalnie spójne z wartościami narożnymi; siatka sama w sobie nie może powiedzieć, która jest prawidłowa.

Dwałowość przypadku (indeks 5 lub 10): środek = średnia z czterech wartości narożnych // albo próbkowanie bilinearyczne jeśli środek >= próg: połącz przecięcia jako JEDNA przejście przekątne (połączone rogi wewnętrzne) w przeciwnym razie: połącz przecięcia jako DWA oddzielne cięcia narożnych Standardowe rozwiązanie pobiera dodatkową wartość w środku komórki – średnia z czterech narożnych jest tanią przybliżoną wartością, a prawidłowe próbkowanie bilinearyczne jest dokładniejsze — i wykorzystuje ją do określenia, która z dwóch topologii jest zgodna z zachowaniem pola w środku komórki. Jest to mały fragment położony na szczycie innej, trivialnej tabeli wyszukiwania, a to szczegół, który oddziela prawidłową implementację marching-squares od tej, która sporadycznie generuje kontur z niemożliwym przecięciem.

saddle case (index 5 or 10):
    center = average of the four corner values      // or bilinear sample
    if center >= threshold:
        connect the crossings as ONE diagonal pass   (inside corners joined)
    else:
        connect the crossings as TWO separate cut corners

Poza prostymi liniami: marszowanie sześcianów i podwójne konturowanie

Naturalnym uogólnieniem w trzech wymiarach jest marszowanie sześcianów (Lorensen i Cline, 1987), które wyodrębnia triangulowaną powierzchnię izosuryfcyjną z pola skalarniego 3D w ten sam sposób komórka po komórce, wykorzystując 8 wierzchołków zamiast 4 oraz 256 konfiguracji surowych, które redukują się do 15 unikalnych przypadków ze względu na symetrię. Dziedziczy ono jeszcze bardziej skomplikowaną wersję dwukształtności (saddle ambiguity), ponieważ pojedyncza ściana sześcianu może sama być przypadkiem dwukształtności, a uzyskanie każdej kombinacji szczelnej zajmowało społeczność grafików lata na całkowite rozwiązanie. Nowszą alternatywą jest podwójne konturowanie, które umieszcza jeden wierzchołek wewnątrz każdej aktywnej komórki zamiast na jej krawędziach i może reprezentować ostre narożniki, które marszowanie sześcianów wygładza – przydatne do wydobywania powierzchni z modeli CSG i terenu voxelowego, gdzie twarde krawędzie mają znaczenie.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Marching Squares i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.