Marching Cubes

Marching Cubes — это алгоритм компьютерной графики для построения трёхмерной изоповерхности (поверхности постоянного значения) на основе трёхмерного массива скалярных данных (воксельной сетки). Алгоритм относится к классу методов изоповерхностной экстракции и широко применяется в научной визуализации, медицинской томографии (КТ, МРТ), компьютерном моделировании и компьютерных играх.

История

Алгоритм Marching Cubes был впервые опубликован в 1987 году исследователями Уильямом Лоренсеном (William Lorensen) и Харви Клайном (Harvey Kline) из компании General Electric. Изначально он разрабатывался для визуализации данных медицинской компьютерной томографии, где необходимо было быстро и точно строить трёхмерные модели внутренних органов по набору двумерных срезов. Первая реализация была запатентована, и патент действовал до 2005 года, что ограничивало использование алгоритма в открытом программном обеспечении. После истечения срока патента алгоритм стал свободно доступен и получил широкое распространение.

Принцип работы

Алгоритм Marching Cubes обрабатывает трёхмерную скалярную сетку, где каждому узлу (вокселю) приписано числовое значение. Задача — построить полигональную поверхность, проходящую через точки, где значение поля равно заданному изозначению (порогу). Алгоритм работает пошагово, «проходя» через каждый куб (воксель) сетки.

Основные шаги

1. Определение конфигурации куба. Для каждого куба сетки, образованного восемью соседними узлами, сравнивается значение в каждом узле с изозначением. Если значение узла больше или равно изозначению, узел считается «внутренним» (1), иначе — «внешним» (0). Таким образом, для каждого куба получается 8-битный код (от 0 до 255), описывающий, какие вершины находятся внутри изоповерхности.

1. Выбор треугольной сетки. По коду конфигурации из заранее вычисленной таблицы (lookup table) выбирается набор треугольников, аппроксимирующих изоповерхность внутри данного куба. Таблица содержит 256 возможных конфигураций, с учётом симметрии и инверсий. Для каждой конфигурации определено, какие рёбра куба пересекает изоповерхность и как соединить точки пересечения.

1. Интерполяция вершин. Точное положение вершин треугольников на рёбрах куба вычисляется методом линейной интерполяции между значениями в узлах. Это позволяет получить гладкую поверхность, а не ступенчатую.

1. Вычисление нормалей. Для корректного освещения поверхности вычисляются векторы нормалей в каждой вершине. Обычно нормаль вычисляется как градиент скалярного поля в данной точке (например, методом центральных разностей).

1. Сборка полигональной модели. Все треугольники, полученные из всех кубов сетки, объединяются в единую трёхмерную модель (обычно в формате списка треугольников с вершинами и нормалями).

Разрешение и производительность

Качество и детализация изоповерхности напрямую зависят от разрешения исходной сетки. Чем мельче шаг сетки, тем больше кубов обрабатывается и тем более гладкой получается поверхность, но растёт вычислительная нагрузка. Для сетки размером N×N×N число обрабатываемых кубов равно (N-1)³. Современные реализации используют оптимизации:

• Отсечение невидимых кубов — кубы, все вершины которых находятся с одной стороны от изозначения, не обрабатываются.
• Параллельные вычисления — обработка каждого куба независима, что позволяет эффективно использовать GPU (графические процессоры) или многопоточные CPU.
• Адаптивные сетки — в областях с малыми градиентами используется более грубая сетка.

Применение

Медицинская визуализация

Marching Cubes является стандартом для построения трёхмерных моделей органов по данным КТ и МРТ. Врачи и хирурги используют такие модели для планирования операций, диагностики и обучения. Например, алгоритм применяется в системах 3D Slicer, ITK-SNAP и многих коммерческих пакетах.

Научная визуализация

В физике, химии и геологии алгоритм используется для визуализации изоповерхностей скалярных полей: распределения температуры, давления, плотности, магнитного поля, концентрации вещества. Примеры: построение изоповерхностей электронной плотности в молекулах, визуализация данных сейсморазведки.

Компьютерные игры и VR

В игровых движках (например, Unity, Unreal Engine) Marching Cubes применяется для генерации процедурного ландшафта, пещер, воксельных миров (игры типа Minecraft, но с гладкими поверхностями). Алгоритм позволяет создавать разрушаемое окружение и динамически изменяемую геометрию.

3D-печать и моделирование

Алгоритм используется для преобразования скалярных данных (например, из медицинских сканов) в полигональные модели, пригодные для 3D-печати. Также применяется в системах реконструкции поверхностей по облакам точек.

Варианты и улучшения

За десятилетия существования алгоритма было предложено множество модификаций:

• Marching Tetrahedra — разбиение каждого куба на тетраэдры для устранения неоднозначностей в конфигурациях куба.
• Dual Marching Cubes — альтернативный подход, строящий вершины в центрах кубов, что даёт более качественную сетку на адаптивных сетках.
• Adaptive Marching Cubes — использование октодеревьев для локального изменения разрешения сетки.
• GPU-реализации — алгоритм полностью перенесён на графические процессоры (например, в библиотеке OpenGL или CUDA), что позволяет обрабатывать миллионы вокселей в реальном времени.

Ограничения и критика

Несмотря на широкое распространение, Marching Cubes имеет ряд недостатков:

• Неоднозначности — в некоторых конфигурациях куба (например, при чередовании внутренних и внешних вершин) возможны топологические неоднозначности, приводящие к разрывам или неправильным соединениям. Решается использованием дополнительных таблиц или разбиением на тетраэдры.
• Избыточная полигональность — на однородных участках поверхности генерируется много мелких треугольников, что увеличивает размер модели. Требуется последующее упрощение (децимация) сетки.
• Чувствительность к шуму — при наличии шума в исходных данных поверхность может содержать артефакты. Требуется предварительная фильтрация.

Интересные факты

• Название «Marching Cubes» (марширующие кубы) отражает идею последовательного «прохода» по всем кубам сетки.
• Алгоритм является одним из первых примеров использования таблиц заранее вычисленных конфигураций (lookup tables) в компьютерной графике.
• В 1995 году алгоритм был включён в список «10 самых влиятельных алгоритмов в компьютерной графике» по версии журнала IEEE Computer Graphics and Applications.

Источники

• Lorensen W., Kline H. Marching Cubes: A High Resolution 3D Surface Construction Algorithm // ACM SIGGRAPH Computer Graphics, 1987.
• Bloomenthal J. Polygonization of Implicit Surfaces // Computer Aided Geometric Design, 1988.
• Nielson G. M., Hamann B. The Asymptotic Decider: Resolving the Ambiguity in Marching Cubes // Proceedings of IEEE Visualization, 1991.
• Bourke P. Polygonising a Scalar Field (Marching Cubes), 1994.
• Botsch M. et al. Polygon Mesh Processing, CRC Press, 2010.