stringtranslate.com

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

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

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

История

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

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

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

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

Marching Cubes 33, предложенный Черняевым [8] в 1995 году, является одним из первых алгоритмов выделения изоповерхностей, предназначенных для сохранения топологии трилинейного интерполянта. В своей работе Черняев расширяет число случаев в справочной таблице триангуляции до 33. Затем он предлагает другой подход к решению внутренних неоднозначностей, основанный на асимптотическом решателе. Позже, в 2003 году, Нильсон [9] доказал, что справочная таблица Черняева является полной и может отражать все возможные варианты поведения трилинейного интерполянта, а Левинер и др. [10] предложили реализацию алгоритма. Также в 2003 г. Лопес и Бродли [11] расширили тесты, предложенные Натараджан. [7] В 2013 году Custodio et al. [12] отметили и исправили алгоритмические неточности, ставившие под угрозу топологическую корректность сетки, созданной алгоритмом Marching Cubes 33, предложенным Черняевым. [8]

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

Алгоритм

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

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

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

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

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

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

Источники

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

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

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

Викискладе есть медиафайлы, связанные с марширующими кубиками .