UK 
EnglishТипова
Polski〰️ Маршируючі квадрати
Витягуйте контурні лінії зі скалярного поля за 16-кейсовою таблицею маршируючих квадратів. Перетягуйте метакулі, перемикайте на шум або малювання та розв'язуйте відому неоднозначність сідла.
Про Маршируючі квадрати
Маршируючі квадрати (Marching Squares) — це алгоритм комп'ютерної графіки для виділення ізоконтурів (ліній сталого значення) зі скалярного 2D-поля, вибраного на регулярній сітці. Кожен квадрат 2×2 клітинок сітки має чотири кутові значення; порівняння кожного кута з ізозначенням дає 4-бітний індекс (0–15), тобто 16 можливих конфігурацій. Таблиця пошуку зіставляє кожну конфігурацію з одним або двома відрізками лінії, що приблизно показують, де контур перетинає клітинку, а лінійна інтерполяція на ребрі дає точність на рівні підклітинки. Алгоритм є 2D-попередником 3D-методу Маршируючих кубів (Лоренсен і Клайн, 1987), який використовується в медичній візуалізації для реконструкції поверхонь із даних КТ/МРТ.
Симуляція дозволяє перетягувати метакулі (джерела потенційного поля) полотном, змінювати поріг ізозначення й спостерігати в реальному часі, як 16-кейсова таблиця пошуку генерує гладкі контурні лінії. Два випадки сідлових клітинок (індекси 5 і 10) є неоднозначними; симулятор розв'язує їх білінійною інтерполяцією центрального значення, щоб обрати правильну топологію.
Часті запитання
Чому в таблиці пошуку Маршируючих квадратів рівно 16 випадків?
Кожен із чотирьох кутів клітинки незалежно класифікується як вище (1) або нижче (0) ізозначення, даючи 2⁴ = 16 можливих бітових комбінацій. Через симетрію багато випадків є поворотами чи відображеннями одне одного, зменшуючи кількість окремих геометрій приблизно до 4 унікальних форм. Повна 16-записова таблиця пошуку зберігає наперед визначені пари перетинів ребер для кожного шаблону, дозволяючи реалізацію без розгалужень, придатну до векторизації.
Що таке неоднозначність сідлової точки і як вона розв'язується?
Випадки 5 (0101) і 10 (1010) мають два діагонально протилежні «внутрішні» кути, створюючи неоднозначність щодо того, чи контур з'єднується як X-подібна форма, чи як дві окремі дуги. Стандартне розв'язання — вибрати значення скалярного поля в центрі клітинки: якщо центральне значення перевищує ізозначення, два внутрішні кути з'єднуються; інакше вони залишаються окремими. Ця білінійна дизамбіґуація дає топологічно узгоджені контури.
Як лінійна інтерполяція покращує точність контуру?
Без інтерполяції відрізки контуру прив'язувалися б до середин ребер клітинки, створюючи «сходинковий» вигляд. Лінійна інтерполяція розміщує точку перетину при t = (iso − v₀) / (v₁ − v₀) уздовж ребра між кутовими значеннями v₀ і v₁, тож лінійний відрізок точно відстежує, де скалярне поле дорівнює ізозначенню. Для гладких полів це значно зменшує візуальний аліасинг без додаткових витрат на вибірку.
Що таке Маршируючі куби і як вони пов'язані з Маршируючими квадратами?
Маршируючі куби — це 3D-узагальнення: кожна кубічна клітинка має 8 кутів, даючи 2⁸ = 256 випадків (зведених до 15 канонічних за симетрією). Алгоритм виділяє тріангульовані ізоповерхні з об'ємних даних, таких як медичні КТ-скани та змодельовані поля рідини. Представлений Лоренсеном і Клайном на SIGGRAPH 1987 року, він став однією з найцитованіших статей у комп'ютерній графіці, а реконструкція поверхонь МРТ у медичній візуалізації стала його «вбивчим застосуванням».
Які типи скалярних полів можуть контуруватися Маршируючими квадратами?
Підходить будь-яке 2D-скалярне поле: температура з погодної моделі, тиск у симуляції рідини, відстань до найближчої перешкоди (для рендерингу поля зі знаковою відстанню), електростатичний потенціал, висота рельєфу або сума радіальних базисних функцій (метакуль). Алгоритм не залежить від типу поля і потребує лише значень, вибраних на регулярній сітці.
Як метакулі пов'язані з цією симуляцією?
Метакулі — це точкові джерела, чий внесок у поле спадає з відстанню: f(x, y) = Σ rᵢ² / ((x−xᵢ)² + (y−yᵢ)²). Підсумовування кількох метакуль створює гладке «блобоподібне» скалярне поле, яке зливається й розділяється під час руху джерел. Маршируючі квадрати виділяють ізоконтур при обраному порозі, утворюючи характерні органічні форми «блобів», популяризовані в комп'ютерно-графічних демо 1980-х років.
Яка часова складність Маршируючих квадратів?
Для сітки з M × N клітинок алгоритм обробляє кожну клітинку рівно один раз: O(MN) часу і O(MN) пам'яті для значень сітки. Виділення контуру на клітинку — O(1) через таблицю пошуку. На практиці вузьким місцем часто є обчислення скалярного поля (наприклад, підсумовування k внесків метакуль на клітинку коштує O(kMN)), тому для розпаралелювання обчислення поля в інтерактивних застосунках реального часу використовуються обчислювальні шейдери GPU.
Чи можуть Маршируючі квадрати обробляти анімовані або змінні в часі поля?
Так — алгоритм широко використовується для рендерингу поверхні рідини в реальному часі, обрисів симуляції вогню та інтерактивних редакторів метакуль. Оскільки кожна клітинка незалежна, алгоритм ідеально розпаралелюється на GPU. Реалізації зазвичай виконують обчислення поля та виділення контуру як проходи обчислювальних/фрагментних шейдерів, досягаючи тисяч кадрів на секунду на сучасному обладнанні для сіток помірного розміру (наприклад, 256×256).
Чи існує двоїстий алгоритм до Маршируючих квадратів?
Подвійне контурування (Dual Contouring) — це альтернатива, яка розміщує вершини контуру всередині кожної клітинки, а не на ребрах, використовуючи як скалярні значення, так і інформацію про градієнт (нормалі) для позиціонування вершин. Він краще зберігає гострі особливості (кути, гребені), які Маршируючі квадрати згладжують, ціною потреби в даних градієнта та складнішого відстеження топології. Його переважно використовують для механічних CAD-моделей і гостроконтурних поверхонь рівня.
Про цю симуляцію
Це інтерактивна реалізація алгоритму контурування Маршируючих квадратів, який виділяє ізолінії — криві сталого значення — зі скалярного 2D-поля на сітці. Чотири кути кожної клітинки порівнюються з ізозначенням, утворюючи 4-бітний індекс, що обирає одну з 16 конфігурацій ліній із таблиці пошуку, з інтерполяцією ребер для гладких контурів.
🔬 Що це показує
Полотно відображає живу теплову карту скалярного поля з ізолініями поверх неї. Увімкнення індексів клітинок позначає кожну активну клітинку її 4-бітною конфігурацією і підсвічує два неоднозначні сідлові випадки бурштиновим кольором.
🎮 Як користуватися
Оберіть тип поля (Метакулі, Шум, Синусоїдальне або Малювання), потім налаштуйте Роздільну здатність сітки та повзунок Ізозначення. Перетягуйте метакулі на полотні, увімкніть Багаторівневий режим для п'яти ізоліній, Показати теплову карту або Показати індекси клітинок для діагностики, і Розв'язати сідла, щоб усунути неоднозначність випадків 5 і 10.
💡 А чи знали ви?
Маршируючі квадрати — прямий 2D-предок Маршируючих кубів (Лоренсен і Клайн, 1987), які використовуються для реконструкції 3D-поверхонь із медичних КТ- і МРТ-сканів — однієї з найцитованіших статей комп'ютерної графіки.
Поширені запитання
Чому рівно 16 випадків у таблиці пошуку?
Кожен кут клітинки класифікується вище або нижче ізозначення, даючи 24 = 16 бітових шаблонів. Таблиця пошуку зберігає правильні сегменти для кожного випадку, тож геометрію ніколи не потрібно обчислювати на льоту.
Що таке неоднозначність сідлової точки, яку виправляє «Розв'язати сідла»?
Випадки 5 і 10 мають два діагонально протилежні кути вище ізозначення, тож контур міг би з'єднатися як X або як дві дуги. Розв'язати сідла вибирає центр клітинки й обирає ту топологію, яка залишається узгодженою з навколишнім полем.
Чому повзунок Ізозначення так сильно змінює контури?
Ізозначення — це поріг, що перевіряється в кожному куті, тож переміщення повзунка перерізає поле на іншій висоті. Поблизу центру метакулі поле високе, тож високе ізозначення дає малі щільні петлі, а низьке — великі злиті блоби.
Що робить Багаторівневий режим?
Він малює п'ять ізоліній, розташованих навколо поточного ізозначення, як контурні лінії на карті, роблячи загальну форму поля та його крутизну легшими для сприйняття, ніж один поріг.
Чим режим Малювання відрізняється від інших?
Малювання замінює процедурне поле тим, яке ви ліпите, перетягуючи по полотну м'яким пензлем, показуючи, що Маршируючі квадрати працюють на будь-якому скалярному полі, а не лише на математичних, як метакулі.