Идущие кубы является компьютерной графикой алгоритмом, опубликованным в 1987 SIGGRAPH производства по Lorensen и Cline, для извлечения полигональной сетки из с изоповерхностью из трехмерного дискретного скалярного поля (элементы из которых иногда называют вокселями ). Применение этого алгоритма в основном связано с медицинской визуализацией, такой как изображения данных компьютерной томографии и МРТ, а также со специальными эффектами или трехмерным моделированием с помощью того, что обычно называется метабаллами. или другие метаповерхности. Алгоритм маршевых кубов предназначен для использования в 3-D, 2-мерная версия этого алгоритма называется алгоритмом маршевых квадратов.
Алгоритм был разработан Уильямом Э. Лоренсеном (1946-2019) и Харви Э. Клайном в результате их исследований для General Electric. В General Electric они работали над способом эффективной визуализации данных с устройств КТ и МРТ.
Предпосылка алгоритма состоит в том, чтобы разделить входной объем на дискретный набор кубов. При использовании фильтрации с линейной реконструкцией каждый куб, который содержит часть заданной изоповерхности, может быть легко идентифицирован, поскольку значения выборки в вершинах куба должны охватывать целевое значение изоповерхности. Для каждого куба, содержащего часть изоповерхности, создается треугольная сетка, которая аппроксимирует поведение трилинейного интерполянта во внутреннем кубе.
В первой опубликованной версии алгоритма использовалась вращательная и отражающая симметрия, а также изменения знаков для построения таблицы с 15 уникальными случаями. Однако из-за существования неоднозначностей в поведении трилинейного интерполянта на гранях куба и внутри, сетки, извлеченные Марширующими кубами, представляли разрывы и топологические проблемы. Для куба сетки неоднозначность граней возникает, когда вершины граней имеют чередующиеся знаки. То есть вершины одной диагонали на этой грани положительны, а вершины на другой отрицательны. Обратите внимание, что в этом случае знаков вершин граней недостаточно для определения правильного способа триангуляции изоповерхности. Точно так же внутренняя неоднозначность возникает, когда знаки вершин куба недостаточны для определения правильной триангуляции поверхности, то есть когда для одной и той же конфигурации куба возможно несколько триангуляций.
Популярность Marching Cubes и его широкое распространение привели к нескольким улучшениям в алгоритме для устранения неоднозначностей и правильного отслеживания поведения интерполянта. Дерст в 1988 г. был первым, кто заметил, что таблица триангуляции, предложенная Лоренсеном и Клайном, была неполной, и что некоторые случаи Marching Cubes допускают множественные триангуляции. «Дополнительная ссылка» Дерста была на более ранний, более эффективный (см. De Araujo) алгоритм полигонизации изоповерхности, разработанный Wyvill, Wyvill и McPheeters. Позже Нильсон и Хаманн в 1991 году наблюдали существование неоднозначности в поведении интерполянта на грани куба. Они предложили тест под названием Asymptotic Decider, чтобы правильно отслеживать интерполянт на гранях куба. Фактически, как заметил Натараджан в 1994 году, эта проблема неоднозначности также возникает внутри куба. В своей работе автор предложил тест разрешения неоднозначности, основанный на критических точках интерполянта, и добавил четыре новых случая в таблицу триангуляции Marching Cubes (подслучаи случаев 3, 4, 6 и 7). На данный момент, даже со всеми улучшениями, предложенными для алгоритма и его таблицы триангуляции, сетки, созданные марширующими кубами, по-прежнему имеют топологические несогласованности.
Marching Cubes 33, предложенный Черняевым в 1995 году, является одним из первых алгоритмов извлечения изоповерхностей, предназначенных для сохранения топологии трилинейного интерполянта. В своей работе Черняев расширяет до 33 количество наблюдений в справочной таблице триангуляции. Затем он предлагает другой подход к решению внутренних неоднозначностей, основанный на асимптотическом решении. Позже, в 2003 году, Нильсон доказал, что справочная таблица Черняева является полной и может отражать все возможные варианты поведения трилинейного интерполянта, а Левинер и др. предложил реализацию алгоритма. Также в 2003 году Лопес и Бродли расширили тесты, предложенные Натараджан. В 2013 году Custodio et al. отметил и исправил алгоритмические неточности, которые ставили под угрозу топологическую корректность сетки, сгенерированной алгоритмом Marching Cubes 33, предложенным Черняевым.
Изначально опубликовано 15 конфигураций кубаАлгоритм проходит через скалярное поле, выбирая одновременно восемь соседних местоположений (таким образом, формируя воображаемый куб), а затем определяет многоугольник (ы), необходимый для представления части изоповерхности, которая проходит через этот куб. Затем отдельные многоугольники объединяются в желаемую поверхность.
Это делается путем создания индекса для предварительно вычисленного массива из 256 возможных конфигураций многоугольника (2 8 = 256) внутри куба, обрабатывая каждое из 8 скалярных значений как бит в 8-битном целом числе. Если значение скаляра выше, чем изо-значение (т. Е. Оно находится внутри поверхности), то соответствующий бит устанавливается в единицу, а если он ниже (снаружи), он устанавливается в ноль. Конечное значение после проверки всех восьми скаляров является фактическим индексом массива индексов многоугольника.
Наконец, каждая вершина сгенерированных многоугольников помещается в соответствующую позицию вдоль ребра куба путем линейной интерполяции двух скалярных значений, связанных этим ребром.
Градиент скалярного поля в каждой точке сетки также является нормальным вектор гипотетической изоповерхности, проходящей от этой точки. Следовательно, эти нормали могут быть интерполированы по краям каждого куба, чтобы найти нормали сгенерированных вершин, которые необходимы для затенения результирующей сетки с некоторой моделью освещения.
|journal=
( помощь )