Маршевые кубики - Marching cubes

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

Идущие кубы является компьютерной графикой алгоритмом , опубликованным в 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-битном целом числе. Если значение скаляра выше, чем изо-значение (т. Е. Оно находится внутри поверхности), то соответствующий бит устанавливается в единицу, а если он ниже (снаружи), он устанавливается в ноль. Конечное значение после проверки всех восьми скаляров является фактическим индексом массива индексов многоугольника.

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

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

Источники

  1. ^ Лоренсен, Уильям Э .; Клайн, Харви Э. (1 августа 1987 г.). «Марширующие кубики: алгоритм построения трехмерной поверхности высокого разрешения». ACM SIGGRAPH Компьютерная графика . 21 (4): 163–169. CiteSeerX  10.1.1.545.613 . DOI : 10.1145 / 37402.37422 .
  2. ^ «Система и метод отображения поверхностных структур, содержащихся во внутренней области твердого тела» . 5 июня 1985 г. Цитировать журнал требует |journal=( помощь )
  3. ^ Дюрст, Мартин Дж. (1988-10-01). «Буквы: дополнительная ссылка на походные кубики». ACM SIGGRAPH Компьютерная графика . 22 (5): 243. DOI : 10,1145 / 378267,378271 . ISSN  0097-8930 . S2CID  36741734 .
  4. ^ де Араужо, Бруно; Лопес, Даниэль; Джепп, Полина; Хорхе, Хоаким; Уивилл, Брайан (2015). «Обзор неявной полигонизации поверхности». ACM Computing Surveys . 47 (4): 60: 1–60: 39. DOI : 10.1145 / 2732197 . S2CID  14395359 .
  5. ^ Вивилл, Джефф; Уивилл, Брайан; Макфитерс, Крейг (1986). «Структуры данных для мягких объектов». Визуальный компьютер . 2 (4): 227–234. DOI : 10.1007 / BF01900346 . S2CID  18993002 .
  6. ^ Нильсон, GM; Хаманн, Б. (1991). «Асимптотический решающий фактор: разрешение неоднозначности в маршевых кубах». Продолжающаяся визуализация '91 . С. 83–91. DOI : 10.1109 / visual.1991.175782 . ISBN 978-0818622458. S2CID  35739150 .
  7. ^ a b Натараджан, Б.К. (январь 1994 г.). «О построении топологически непротиворечивых изоповерхностей из однородных образцов». Визуальный компьютер . 11 (1): 52–62. DOI : 10.1007 / bf01900699 . ISSN  0178-2789 . S2CID  526698 .
  8. ^ а б В., Черняев Э. (1995). Маршевые кубы 33: построение топологически правильных изоповерхностей: представлена ​​на выставке GRAPHICON '95, Санкт-Петербург, Россия, 03-07.07.1995 . ЦЕРН. Подразделение вычислительной техники и сетей. OCLC  897851506 .
  9. Перейти ↑ Nielson, GM (2003). «По походным кубам». IEEE Transactions по визуализации и компьютерной графике . 9 (3): 283–297. DOI : 10.1109 / TVCG.2003.1207437 .
  10. ^ Левинер, Томас; Лопес, Элио; Виейра, Антониу Вильсон; Таварес, Джеован (январь 2003 г.). «Эффективная реализация корпусов маршевых кубов с топологическими гарантиями». Журнал графических инструментов . 8 (2): 1–15. DOI : 10.1080 / 10867651.2003.10487582 . ISSN  1086-7651 . S2CID  6195034 .
  11. ^ Lopes, A .; Бродли, К. (2003). «Повышение устойчивости и точности алгоритма марширующих кубов для изоповерхностей» (PDF) . IEEE Transactions по визуализации и компьютерной графике . 9 : 16–29. DOI : 10.1109 / tvcg.2003.1175094 . ЛВП : 10316/12925 .
  12. ^ Кастодио, Лис; Этьен, Тьяго; Песко, Синезио; Сильва, Клаудио (ноябрь 2013 г.). «Практические соображения по топологической корректности Marching Cubes 33». Компьютеры и графика . 37 (7): 840–850. CiteSeerX  10.1.1.361.3074 . DOI : 10.1016 / j.cag.2013.04.004 . ISSN  0097-8493 .

Смотрите также

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