Комп'ютерна графіка · Алгоритми · 3D-рендеринг
📅 Квітень 2026 ⏱ ≈ 12 хв читання 🎯 Середній · Останнє оновлення: 28 травня 2026 р.

Marching Cubes — виділення ізоповерхонь з об'ємних даних

МРТ-скани, симуляції рідин на основі множин рівня, метакулі та процедурні ландшафти мають спільне представлення: тривимірне скалярне поле, де цікава поверхня — це множина точок, у яких поле дорівнює пороговому значенню (ізоповерхня). Marching Cubes, винайдений Лоренсеном і Клайном у GE 1987 року, перетворює будь-яку таку неявну поверхню на трикутну сітку, придатну для растеризованого рендерингу, — і попри те, що йому майже 40 років, він лишається алгоритмом першого вибору в програмах медичної візуалізації, 3D-ігрових рушіях і рендерерах рідин реального часу по всьому світу.

Автор: Команда MySimulator · Редакційна перевірка: Редакція MySimulator

1. Ізоповерхні та неявні представлення

Скалярне поле F: ℝ³ → ℝ приписує дійсне значення кожній точці 3D-простору. Ізоповерхня на ізозначенні c — це множина S = {(x, y, z) : F(x,y,z) = c}. Приклади:

Усі вони породжують ізоповерхні, які не можна растеризувати напряму — їх спершу треба перетворити на явну трикутну сітку.

2. Воксельна сітка

Marching Cubes семплює скалярне поле на регулярній 3D-сітці з вокселів (об'ємних пікселів). Кожен воксель — це куб із 8 кутовими семплами. Алгоритм обробляє по одному кубу за раз — «марширує» крізь кожен куб у сітці:

Для куба з кутами c_0 … c_7 та скалярними значеннями v_0 … v_7: 1. Класифікуйте кожен кут як ВСЕРЕДИНІ (v_i < ізозначення) чи ЗЗОВНІ (v_i > ізозначення) 2. Сформуйте 8-бітний індекс: cubeIndex = Σ (v_i < ізозначення ? 1 : 0) << i 3. Знайдіть edgeTable[cubeIndex]: які з 12 ребер перетинаються 4. Для кожного перетнутого ребра інтерполюйте точну позицію перетину 5. Знайдіть triTable[cubeIndex]: як з'єднати середини ребер у трикутники Результат: від 0 до 5 трикутників на куб, безшовно з'єднаних через межі кубів.

3. Таблиця пошуку на 256 випадків

За 8 кутів, кожен з яких можна класифікувати як всередині чи зовні, існує 2⁸ = 256 унікальних конфігурацій кутів. Проте комплементарність та обертальна симетрія зводять їх лише до 15 принципово різних випадків:

  1. Усі зовні: жодного трикутника.
  2. Один кут усередині: 1 трикутник.
  3. Одне ребро всередині: 1 трикутник (інша орієнтація).
  4. Два сусідні кути: 2 трикутники.
  5. Два протилежні кути на одній грані: 2 трикутники (S-подібна форма).
  6. Два діагонально протилежні кути: 2 трикутники (з перетином).
  7. Три кути на одній грані: 2 трикутники + 1.
  8. Три кути L-подібно: 3 трикутники.
  9. Уся грань усередині: 2 трикутники, що утворюють чотирикутник.
  10. Грань + сусідній кут: 3 трикутники.
  11. Дві грані: 4 трикутники.
  12. S-подібна діагональ: 4 трикутники.
  13. Три грані: 4 трикутники.
  14. Майже повний (7 кутів): 1 трикутник.
  15. Усі всередині: жодного трикутника.

Усі 256 випадків породжуються застосуванням 15 базових випадків під обертаннями та відображеннями. Отримана triTable[256][16] кодує, які ребра утворюють кожен трикутник (індекси ребер 0–11; −1 завершує список).

4. Трилінійна інтерполяція

Marching Cubes розміщує вершини трикутників не у кутах сітки, а в інтерпольованих точках перетину на кожному ребрі. Для ребра між кутами i та j зі скалярними значеннями vᵢ та vⱼ:

t = (ізозначення - v_i) / (v_j - v_i) // лінійний параметр t ∈ [0, 1] p = p_i + t * (p_j - p_i) // інтерпольована 3D-позиція Без інтерполяції (t = 0.5) виходять «кубічні» поверхні в стилі Minecraft. Трилінійна інтерполяція дає гладкі викривлені поверхні, що відповідають полю. 
function interpolateEdge(p1, p2, v1, v2, iso) {
  if (Math.abs(v1 - iso) < 1e-5) return p1;
  if (Math.abs(v2 - iso) < 1e-5) return p2;
  const t = (iso - v1) / (v2 - v1);
  return {
    x: p1.x + t * (p2.x - p1.x),
    y: p1.y + t * (p2.y - p1.y),
    z: p1.z + t * (p2.z - p1.z)
  };
}

5. Неоднозначні випадки та MC33

Оригінальний marching cubes 1987 року має неоднозначні конфігурації граней: коли протилежні кути однієї грані обидва всередині (або обидва зовні), існує два топологічно різні способи тріангулювати куб, і наївна таблиця пошуку може обрати неузгоджено — спричиняючи дірки в кінцевій сітці.

6 неоднозначних випадків граней із 15 базових конфігурацій. Якщо сусідні куби розв'язують одну й ту саму неоднозначну грань по-різному, отримана сітка має шов — топологічну дірку, що порушує герметичність і спричиняє артефакти рендерингу.

MC33 (Черняєв, 1995) розширює таблицю пошуку до 33 різних випадків, задаючи узгоджену стратегію усунення неоднозначності граней. Він гарантує топологічно коректну сітку без дірок. Більшість промислових реалізацій (OpenVDB, VTK, Three.js MarchingCubes) використовують таблиці MC33.

6. Обчислення нормалей поверхні

Гладкі нормалі критично важливі для затінення. Два підходи:

Нормалі на основі градієнта

Нормаль до ізоповерхні в точці p пропорційна градієнту скалярного поля: n̂ = ∇F / |∇F|. Наближайте градієнт центральними різницями на воксельній сітці:

∂F/∂x ≈ (F(x+h, y, z) - F(x-h, y, z)) / (2h) Покутові градієнти потім інтерполюються до вершин трикутників із тим самим параметром t, що й інтерполяція позиції, даючи гладкі нормалі, незалежні від щільності трикутників.

Плоскі нормалі граней

Візьміть векторний добуток двох ребер трикутника: n = (v₁ − v₀) × (v₂ − v₀). Швидко, але дає гранчастий вигляд на сітках низької роздільної здатності.

7. Застосування

Продуктивність: воксельна сітка 256³ містить 16 мільйонів кубів. Проста реалізація Marching Cubes на CPU обробляє приблизно 50–100 мільйонів кубів за секунду на сучасному ядрі. Реалізації на GPU (обчислювальні шейдери з префіксними сумами робочих груп для ущільнення вихідних трикутників) досягають прискорення у 10–100 разів, уможливлюючи marching cubes у реальному часі в ігрових рушіях.
💧 Спробуйте симуляцію рідини →