Квадратний хід: побудова контурних ліній через сітку чисел

Від чисел на сітці до лінії на екрані

Ізобари погодного мапу, контури висот топографічної карти та пухкенькі "метаболи" з відеоігор – все це одна й та сама основна задача: у вас є поле скалярів – одне число в кожній точці сітки, і ви хочете намалювати криву, де це поле перетинає обраний поріг. Маршування квадратів – це стандартний алгоритм для її вирішення, і він працює поетапно, починаючи з невеликої 2x2 клітинки сітки.

Чотири куточки, шістнадцять випадків

Кожна клітинка сітки має чотири кути, і кожен кут або знаходиться над порогом ("всередині", біт = 1), або нижче нього ("зовні", біт = 0). Чотири біти забезпечують рівно 16 можливих конфігурацій, і кожна з них має фіквований, попередньо обчислений малюнок лінії, що показує, як контур перетинає клітинку — простий вигляд у таблиці пошуку, не потрібної логіки розгалуження, окрім побудови індексу 4-бітів.

індекс = (верхнійЛівий >= поріг ? 8 : 0) | (верхнійПравый >= поріг ? 4 : 0) | (нижнійПравый >= поріг ? 2 : 0) | (нижнійЛівий >= поріг ? 1 : 0)

// індекс 0 і 15 → без лінії (всі кути з одного боку) // індекс 1, 2, 4, 8 та їхні комплементи → один кут відірваний лінією // індекс 3, 6, 9, 12 → два сусідніх кути відірвані, одна пряма лінія через них // індекс 5, 10 → два випадки SADDLE, див. нижче Щоб зробити отриману лінію гладкою замість того, щоб завжди перетинати точкову середину краю, точка перетину розміщується за допомогою лінійної інтерполяції між двома кутовими значеннями: якщо один кут значно вищий за поріг, а його сусід майже не вищий за нього, точка перетину знаходиться близько до другого кута, а не посередині між ними. Ця єдина корекція перетворює блокову сходинку в контур, який виглядає так, ніби його намічували вручну.

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

Сідловий амбігуність

Два з шістнадцяти випадків є справді неоднозначними: індекс 5 та індекс 10, де обидва кутові елементи, що діагонально протилежні один одному, знаходяться "всередині", а інша пара діагоналей знаходиться "зовні". Чотири перетини мають однозначну інтерпретацію само по собі, але є два різних, рівноцінних способи їх з’єднати лініями — одна інтерпретація малює дві окремі невеликі дуги, що відрізають кожен внутрішній кут, а інша малює дві довгі дуги, які проходять близько один одного, ніколи не торкаючись. Обидва локально узгоджуються з чотирма кутовими значеннями; сітка сама по собі не може сказати, який з них правильний.

сідловий випадок (індекс 5 або 10): центр = середнє арифметичне чотирьох кутових значень // або білінійна зразка якщо центр >= порогове значення: з’єднайте перетини як ОДИН діагональний прохід (внутрішні кути об’єднані) інакше: з’єднайте перетини як ДВІ окремі кути відрізання Стандартне рішення зраховує додаткове значення в центрі комірки — середнє арифметичне чотирьох кутів є дешевою апроксимацією, білінійна інтерполяція більш точна — і використовує його для визначення того, яка з двох топологій узгоджується з поведінкою поля посередині комірки. Це невеликий плащ на тлі іншого тривіального виклику таблиці, і це деталі, які відрізняють правильну реалізацію marching-squares від такої, яка випадково генерує контур із неможливим перетином.

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

За межами площин: маршування кубів та подвійне контурування

Природний розвиток у тривимірному просторі – це маршування кубів (Lorensen and Cline, 1987), яке видобуває триангольовану ізоповерхню з 3D скалярного поля таким самим способом клітин за клітиною, використовуючи 8 кутів замість 4 та 256 початкових конфігурацій, які зменшуються до 15 унікальних випадків завдяки симетрії. Воно успадковує ще більш складну версію амбігуальності зів’ялого, оскільки окремий куб обличчя може сам бути зів’ялим випадком, і повне вирішення всіх комбінацій, що забезпечують водонепроникність, потребувало графічного співтовариства багато років. Новіша альтернатива – подвійне контурування, розміщує один вершину всередині кожної активної клітини замість на її краях і може представляти гострі кути, які маршування кубів згладжує – корисне для видобутку поверхонь із моделей CSG та воксельного рельєфу, де важливі чіткі краї.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Marching Squares і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.