stringtranslate.com

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

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

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

История

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

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

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

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

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

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

Алгоритм

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

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

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

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

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

Реализация алгоритма marching cubes была запатентована как патент США 4,710,876. [2] Был разработан еще один похожий алгоритм, названный marching tetrahedras , чтобы обойти патент, а также решить небольшую проблему неоднозначности marching cubes с некоторыми конфигурациями кубов. Патент истек в 2005 году, и теперь графическое сообщество может законно использовать его без роялти, поскольку прошло более 20 лет с даты его выдачи (1 декабря 1987 года [2] ).

Источники

  1. ^ Лоренсен, Уильям Э.; Клайн, Харви Э. (1 августа 1987 г.). «Марширующие кубы: алгоритм построения трехмерной поверхности с высоким разрешением». ACM SIGGRAPH Computer Graphics . 21 (4): 163–169. CiteSeerX  10.1.1.545.613 . doi :10.1145/37402.37422.
  2. ^ abc US выдан US4710876A, Cline, Harvey & Lorensen, William, "Система и метод отображения поверхностных структур, содержащихся во внутренней области твердого тела", выдан 1987-12-01 
  3. ^ Дюрст, Мартин Дж. (1988-10-01). "Re: Дополнительная ссылка на "марширующие кубы"". ACM SIGGRAPH Computer Graphics . 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). «Структуры данных для мягких объектов». The Visual Computer . 2 (4): 227–234. doi :10.1007/BF01900346. S2CID  18993002.
  6. ^ Нильсон, GM; Хаманн, Б. (1991). «Асимптотический решатель: разрешение неоднозначности в марширующих кубах». Proceeding Visualization '91 . стр. 83–91. doi :10.1109/visual.1991.175782. ISBN 978-0818622458. S2CID  35739150.
  7. ^ ab Natarajan, BK (январь 1994). «О создании топологически согласованных изоповерхностей из однородных образцов». The Visual Computer . 11 (1): 52–62. doi :10.1007/bf01900699. ISSN  0178-2789. S2CID  526698.
  8. ^ ab V., Chernyaev, E. (1995). Marching Cubes 33 : построение топологически правильных изоповерхностей : представлено на GRAPHICON '95, Санкт-Петербург, Россия, 03-07.07.1995 . CERN. Computing and Networks Division. OCLC  897851506.{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
  9. ^ Нильсон, GM (2003). «О марширующих кубах». Труды IEEE по визуализации и компьютерной графике . 9 (3): 283–297. doi :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. doi :10.1109/tvcg.2003.1175094. hdl : 10316/12925 .
  12. ^ Custodio, Lis; Etiene, Tiago; Pesco, Sinesio; Silva, Claudio (ноябрь 2013 г.). «Практические соображения о топологической корректности Marching Cubes 33». Computers & Graphics . 37 (7): 840–850. CiteSeerX 10.1.1.361.3074 . doi :10.1016/j.cag.2013.04.004. ISSN  0097-8493. S2CID  1930192. 

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

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

На Викискладе есть медиафайлы по теме «Марширующие кубы» .