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

Головные и церебральные структуры (скрытые) извлечены из 150 МРТ нарезки маршевыми кубиками (около 150 000 треугольников)

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

История

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

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

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

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

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

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

Алгоритм

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

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

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

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

Источники

  1. ^ Lorensen, William E .; Клайн, Харви Э. (1 августа 1987 г.). «Марширующие кубики: алгоритм построения трехмерной поверхности высокого разрешения». ACM SIGGRAPH Компьютерная графика. 21 (4): 163–169. CiteSeerX  10.1.1.545.613. Дои:10.1145/37402.37422.
  2. ^ «Система и метод отображения поверхностных структур, содержащихся во внутренней области твердого тела». 5 июня 1985 г. Цитировать журнал требует | журнал = (помощь)
  3. ^ Дюрст, Мартин Дж. (1988-10-01). «Буквы: дополнительная ссылка на походные кубики». ACM SIGGRAPH Компьютерная графика. 22 (5): 243. Дои:10.1145/378267.378271. ISSN  0097-8930.
  4. ^ де Араужо, Бруно; Лопес, Даниэль; Джепп, Полина; Хорхе, Хоаким; Уивилл, Брайан (2015). «Обзор неявной полигонизации поверхности». Опросы ACM Computing. 47 (4): 60:1–60:39. Дои:10.1145/2732197.
  5. ^ Уивилл, Джефф; Уивилл, Брайан; Макфитерс, Крейг (1986). «Структуры данных для мягких объектов». Springer the Visual Computer. 2 (4): 227–234. Дои:10.1007 / BF01900346.
  6. ^ Nielson, G.M .; Хаманн, Б. (1991). «Асимптотический решающий фактор: разрешение неоднозначности в маршевых кубах». Продолжение визуализации '91. С. 83–91. Дои:10.1109 / visual.1991.175782. ISBN  978-0818622458.
  7. ^ а б Натараджан, Б. К. (январь 1994 г.). «О построении топологически непротиворечивых изоповерхностей из однородных образцов». Визуальный компьютер. 11 (1): 52–62. Дои:10.1007 / bf01900699. ISSN  0178-2789.
  8. ^ а б В., Черняев Э. (1995). Маршевые кубы 33: построение топологически правильных изоповерхностей: презентация на ГРАФИКОНЕ '95, Санкт-Петербург, Россия, 03-07.07.1995. ЦЕРН. Подразделение вычислительной техники и сетей. OCLC  897851506.
  9. ^ Нильсон, Г. (2003). «По походным кубам». IEEE Transactions по визуализации и компьютерной графике. 9 (3): 283–297. Дои:10.1109 / TVCG.2003.1207437.
  10. ^ Левинер, Томас; Лопес, Элио; Виейра, Антониу Вильсон; Таварес, Джеован (январь 2003 г.). «Эффективная реализация корпусов маршевых кубов с топологическими гарантиями». Журнал графических инструментов. 8 (2): 1–15. Дои:10.1080/10867651.2003.10487582. ISSN  1086-7651.
  11. ^ Lopes, A .; Бродли, К. (2003). «Повышение устойчивости и точности алгоритма маршевых кубов для изоповерхностей» (PDF). IEEE Transactions по визуализации и компьютерной графике. 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.

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

внешняя ссылка