Марширующие кубики

Структуры головы и головного мозга (скрыты) извлечены из 150 срезов МРТ с использованием марширующих кубов (около 150 000 треугольников).

Марширующие кубы — это компьютерной графики алгоритм , опубликованный SIGGRAPH 1987 года. Лоренсеном и Клайном в журнале для извлечения полигональной сетки изоповерхности ( из трехмерного дискретного скалярного поля элементы которого иногда называют вокселями ). Приложения этого алгоритма в основном связаны с медицинской визуализацией, такой как изображения данных КТ и МРТ , а также со специальными эффектами или трехмерным моделированием с использованием того, что обычно называют меташарами или другими метаповерхностями. Алгоритм марширующих кубов предназначен для использования в 3D; двумерная версия этого алгоритма называется алгоритмом марширующих квадратов .

История

Алгоритм был разработан Уильямом Э. Лоренсеном (1946-2019) и Харви Э. Клайном в результате их исследований для General Electric . В General Electric они работали над способом эффективной визуализации данных с устройств КТ и МРТ.

Суть алгоритма состоит в том, чтобы разделить входной объем на дискретный набор кубов. Если предположить, что фильтрация линейной реконструкции каждый куб, содержащий часть заданной изоповерхности позволяет легко идентифицировать , поскольку значения выборки в вершинах куба должны охватывать целевое значение изоповерхности. Для каждого куба, содержащего участок изоповерхности, треугольная сетка, аппроксимирующая поведение трилинейного интерполянта создается во внутреннем кубе.

Первая опубликованная версия алгоритма использовала вращательную и отражательную симметрию, а также изменения знаков для построения таблицы с 15 уникальными случаями. Однако из-за существования неоднозначностей в поведении трилинейного интерполянта на гранях и внутри куба сетки, извлеченные с помощью Marching Cubes, представляли собой разрывы и топологические проблемы. Учитывая куб сетки, неоднозначность грани возникает, когда вершины его грани имеют чередующиеся знаки. То есть вершины одной диагонали на этой грани положительны, а вершины другой – отрицательны. Заметим, что в этом случае знаков вершин грани недостаточно для определения правильного способа триангуляции изоповерхности. Аналогично, внутренняя неоднозначность возникает, когда знаки вершин куба недостаточны для определения правильной триангуляции поверхности , т. е. когда для одной и той же конфигурации куба возможны множественные триангуляции.

Популярность Marching Cubes и его широкое распространение привели к нескольким улучшениям в алгоритме, позволяющим справиться с неоднозначностью и правильно отслеживать поведение интерполянта. Дерст в 1988 году первым заметил, что таблица триангуляции, предложенная Лоренсеном и Клайном, была неполной и что некоторые случаи марширующих кубов допускают множественную триангуляцию. «Дополнительная ссылка» Дерста была на более раннюю, более эффективную (см. де Араужо) ) алгоритм полигонизации изоповерхностей Уайвилла, Уивилла и Макфитерса. Позже Нильсон и Хаманн в 1991 году наблюдал существование неоднозначностей в поведении интерполянта на грани куба. Они предложили тест под названием «Асимптотический решатель», позволяющий правильно отслеживать интерполянт на гранях куба. Фактически, как заметил Натараджан в 1994 году эта проблема неоднозначности возникает и внутри куба. В своей работе автор предложил тест устранения неоднозначности, основанный на интерполянтных критических точках, и добавил четыре новых случая в таблицу триангуляции Marching Cubes (подслучаи случаев 3, 4, 6 и 7). На этом этапе, даже несмотря на все улучшения, предложенные в алгоритме и его таблице триангуляции, сетки, созданные Марширующими кубами, все еще имели топологическую некогерентность.

The Marching Cubes 33, proposed by Chernyaev в 1995 году это один из первых алгоритмов извлечения изоповерхностей, предназначенный для сохранения топологии трилинейного интерполянта. В своей работе Черняев расширяет число случаев в справочной таблице триангуляции до 33. Затем он предлагает другой подход к решению внутренних неоднозначностей, основанный на асимптотическом решателе. Позже, в 2003 году, Нильсон доказали, что справочная таблица Черняева является полной и может отражать все возможные варианты поведения трилинейного интерполянта, а Левинер и др. предложил реализацию алгоритма. Также в 2003 году Лопес и Бродли расширил тесты, предложенные Натараджаном. В 2013 году Кустодио и др. отметил и исправил алгоритмические неточности, ставившие под угрозу топологическую корректность сетки, созданной алгоритмом Marching Cubes 33, предложенным Черняевым.

Первоначально опубликованные 15 конфигураций куба.

Алгоритм

Алгоритм проходит через скалярное поле, одновременно беря восемь соседних местоположений (формируя таким образом воображаемый куб), а затем определяя многоугольник(и), необходимые для представления части изоповерхности , проходящей через этот куб. Отдельные полигоны затем объединяются в желаемую поверхность.

Это делается путем создания индекса предварительно рассчитанного массива из 256 возможных конфигураций полигонов (2 ⁸ =256) внутри куба, рассматривая каждое из 8 скалярных значений как бит 8-битного целого числа. Если значение скаляра выше, чем значение iso (т. е. оно находится внутри поверхности), тогда соответствующий бит устанавливается в единицу, а если оно ниже (снаружи), он устанавливается в ноль. Окончательное значение после проверки всех восьми скаляров является фактическим индексом массива индексов полигонов.

Наконец, каждая вершина сгенерированных многоугольников помещается в соответствующую позицию вдоль края куба путем линейной интерполяции двух скалярных значений, соединенных этим краем.

Градиент . скалярного поля в каждой точке сетки также является вектором нормали гипотетической изоповерхности, проходящей из этой точки Следовательно, эти нормали можно интерполировать по краям каждого куба, чтобы найти нормали сгенерированных вершин, которые необходимы для затенения результирующей сетки с помощью некоторой модели освещения .

Патентные вопросы

Реализация алгоритма марширующих кубов была запатентована как патент США № 4710876. Другой аналогичный алгоритм был разработан, названный марширующими тетраэдрами , чтобы обойти патент, а также решить небольшую проблему неоднозначности марширующих кубов с некоторыми конфигурациями кубов. Срок действия патента истек в 2005 году, и теперь графическому сообществу разрешено использовать его без лицензионных отчислений, поскольку с даты его выдачи (1 декабря 1987 г.) прошло более 20 лет. ).

См. также

• Создание сетки на основе изображений
• Марширующие тетраэдры

Внешние ссылки

• Лоренсен, МЫ; Клайн, Харви Э. (1987). «Марширующие кубы: алгоритм построения трехмерной поверхности высокого разрешения». Компьютерная графика ACM . 21 (4): 163–169. CiteSeerX   10.1.1.545.613 . дои : 10.1145/37402.37422 .
• Нильсон, генеральный менеджер; Хаманн, Б. (1991). «Асимптотический решатель: разрешение неоднозначности в маршевых кубах». Продолжается визуализация '91 . стр. 83–91. дои : 10.1109/VISUAL.1991.175782 . ISBN  9780818622458 . S2CID   35739150 .
• Монтани, Клаудио; Скатени, Риккардо; Скопиньо, Роберто (1994). «Модифицированная справочная таблица для неявного устранения неоднозначности марширующих кубов». Визуальный компьютер . 10 (6): 353–355. дои : 10.1007/BF01900830 . S2CID   31316542 .
• Нильсон, генеральный менеджер; Джунвон Сон (1997). «Интервальная объемная тетраэдризация». Слушания. Визуализация '97 (Кат. № 97CB36155) . стр. 221–228. дои : 10.1109/VISUAL.1997.663886 . ISBN  978-0-8186-8262-9 . S2CID   5575097 .
• Пол Бурк. «Обзор и исходный код» .
• Мэтью Уорд. «Обзор GameDev» .
• «Вводное описание с дополнительной графикой» .
• «Марширующие кубики» . . Немного из ранней истории Marching Cubes.
• Ньюман, Тимоти С.; Йи, Хонг (2006). «Обзор алгоритма марширующих кубиков». Компьютеры и графика . 30 (5): 854–879. CiteSeerX   10.1.1.413.7458 . дои : 10.1016/j.cag.2006.07.021 .
• Стефан Диль. «Специализированные алгоритмы визуализации» (PDF) .