Идущие кубы является компьютерной графикой алгоритма , опубликованный в 1987 SIGGRAPH производства по Lorensen и Cline, [1] для извлечения полигональной сетки из с изоповерхностью из трехмерного дискретного скалярного поля (элементы которого иногда называют вокселями ). Применение этого алгоритма в основном связано с медицинской визуализацией, такой как изображения данных компьютерной томографии и МРТ , а также со специальными эффектами или трехмерным моделированием с помощью того, что обычно называется метабаллами.или другие метаповерхности. Алгоритм маршевых кубов предназначен для использования в 3-D, 2-D версия этого алгоритма называется алгоритмом маршевых квадратов .
История
Алгоритм был разработан Уильямом Э. Лоренсеном (1946-2019) и Харви Э. Клайном в результате их исследований для General Electric . В General Electric они работали над способом эффективной визуализации данных с устройств КТ и МРТ. [2]
Предпосылка алгоритма состоит в том, чтобы разделить входной объем на дискретный набор кубов. При использовании фильтрации с линейной реконструкцией каждый куб, который содержит часть заданной изоповерхности , может быть легко идентифицирован, поскольку значения выборки в вершинах куба должны охватывать целевое значение изоповерхности. Для каждого куба, содержащего часть изоповерхности, создается треугольная сетка, которая аппроксимирует поведение трилинейного интерполянта во внутреннем кубе.
В первой опубликованной версии алгоритма использовалась вращательная и отражающая симметрия, а также изменения знаков для построения таблицы с 15 уникальными случаями. Однако из-за существования неоднозначностей в поведении трилинейного интерполянта на гранях куба и внутри, сетки, извлеченные Марширующими кубами, представляли разрывы и топологические проблемы. Для куба сетки неоднозначность граней возникает, когда вершины граней имеют чередующиеся знаки. То есть вершины одной диагонали на этой грани положительны, а вершины на другой отрицательны. Обратите внимание, что в этом случае знаков вершин граней недостаточно для определения правильного способа триангуляции изоповерхности. Точно так же внутренняя неоднозначность возникает, когда знаки вершин куба недостаточны для определения правильной триангуляции поверхности , то есть когда для одной и той же конфигурации куба возможно несколько триангуляций.
Популярность Marching Cubes и его широкое распространение привели к нескольким улучшениям в алгоритме для устранения неоднозначностей и правильного отслеживания поведения интерполянта. Дерст [3] в 1988 г. был первым, кто заметил, что таблица триангуляции, предложенная Лоренсеном и Клайном, была неполной и что некоторые случаи Marching Cubes допускают множественные триангуляции. «Дополнительная ссылка» Дерста была на более ранний, более эффективный (см. De Araujo [4] ) алгоритм полигонизации изоповерхностей, разработанный Wyvill, Wyvill и McPheeters. [5] Позже Нильсон и Хаманн [6] в 1991 году наблюдали существование неоднозначности в поведении интерполянта на грани куба. Они предложили тест под названием Asymptotic Decider, чтобы правильно отслеживать интерполянт на гранях куба. Фактически, как заметил Натараджан [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]
Алгоритм
Алгоритм проходит через скалярное поле, выбирая одновременно восемь соседних местоположений (таким образом, формируя воображаемый куб), а затем определяет многоугольник (ы), необходимый для представления части изоповерхности, которая проходит через этот куб. Затем отдельные многоугольники объединяются в желаемую поверхность.
Это делается путем создания индекса для предварительно вычисленного массива из 256 возможных конфигураций многоугольника (2 8 = 256) внутри куба, обрабатывая каждое из 8 скалярных значений как бит в 8-битном целом числе. Если значение скаляра выше, чем изо-значение (т. Е. Оно находится внутри поверхности), то соответствующий бит устанавливается в единицу, а если он ниже (снаружи), он устанавливается в ноль. Конечное значение после проверки всех восьми скаляров является фактическим индексом массива индексов многоугольника.
Наконец, каждая вершина сгенерированных многоугольников помещается в соответствующую позицию вдоль ребра куба путем линейной интерполяции двух скалярных значений, связанных этим ребром.
Градиент скалярного поля в каждой точке сетки также является нормальным вектор гипотетической изоповерхности , проходящей от этой точки. Следовательно, эти нормали могут быть интерполированы по краям каждого куба, чтобы найти нормали сгенерированных вершин, которые необходимы для затенения результирующей сетки с некоторой моделью освещения .
Источники
- ^ Лоренсен, Уильям Э .; Клайн, Харви Э. (1 августа 1987 г.). «Марширующие кубики: алгоритм построения трехмерной поверхности высокого разрешения». ACM SIGGRAPH Компьютерная графика . 21 (4): 163–169. CiteSeerX 10.1.1.545.613 . DOI : 10.1145 / 37402.37422 .
- ^ «Система и метод отображения поверхностных структур, содержащихся во внутренней области твердого тела» . 5 июня 1985 г. Цитировать журнал требует
|journal=
( помощь ) - ^ Дюрст, Мартин Дж. (1988-10-01). «Буквы: дополнительная ссылка на походные кубики». ACM SIGGRAPH Компьютерная графика . 22 (5): 243. DOI : 10,1145 / 378267,378271 . ISSN 0097-8930 .
- ^ де Араужо, Бруно; Лопес, Даниэль; Джепп, Полина; Хорхе, Хоаким; Уивилл, Брайан (2015). «Обзор неявной полигонизации поверхности». ACM Computing Surveys . 47 (4): 60: 1–60: 39. DOI : 10.1145 / 2732197 .
- ^ Уивилл, Джефф; Уивилл, Брайан; Макфитерс, Крейг (1986). «Структуры данных для мягких объектов». Спрингер Визуальный компьютер . 2 (4): 227–234. DOI : 10.1007 / BF01900346 .
- ^ Нильсон, GM; Хаманн, Б. (1991). «Асимптотический решающий фактор: разрешение неоднозначности в маршевых кубах». Продолжающаяся визуализация '91 . С. 83–91. DOI : 10.1109 / visual.1991.175782 . ISBN 978-0818622458.
- ^ а б Натараджан, Б.К. (январь 1994 г.). «О построении топологически непротиворечивых изоповерхностей из однородных образцов». Визуальный компьютер . 11 (1): 52–62. DOI : 10.1007 / bf01900699 . ISSN 0178-2789 .
- ^ а б В., Черняев Э. (1995). Маршевые кубы 33: построение топологически правильных изоповерхностей: представлена на выставке GRAPHICON '95, Санкт-Петербург, Россия, 03-07.07.1995 . ЦЕРН. Подразделение вычислительной техники и сетей. OCLC 897851506 .
- ^ Нильсон, GM (2003). «По походным кубам». IEEE Transactions по визуализации и компьютерной графике . 9 (3): 283–297. DOI : 10.1109 / TVCG.2003.1207437 .
- ^ Левинер, Томас; Лопес, Элио; Виейра, Антониу Вильсон; Таварес, Джеован (январь 2003 г.). «Эффективная реализация корпусов маршевых кубов с топологическими гарантиями». Журнал графических инструментов . 8 (2): 1–15. DOI : 10.1080 / 10867651.2003.10487582 . ISSN 1086-7651 .
- ^ Lopes, A .; Бродли, К. (2003). «Повышение устойчивости и точности алгоритма марширующих кубов для изоповерхностей» (PDF) . IEEE Transactions по визуализации и компьютерной графике . 9 : 16–29. DOI : 10.1109 / tvcg.2003.1175094 . ЛВП : 10316/12925 .
- ^ Кастодио, Лис; Этьен, Тьяго; Песко, Синезио; Сильва, Клаудио (ноябрь 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 .
Смотрите также
- Создание сетки на основе изображений
- Марширующие тетраэдры
Внешние ссылки
- Lorensen, WE; Клайн, Харви Э. (1987). «Марширующие кубики: алгоритм построения трехмерной поверхности с высоким разрешением». Компьютерная графика ACM . 21 (4): 163–169. CiteSeerX 10.1.1.545.613 . DOI : 10.1145 / 37402.37422 .
- Нильсон, GM; Хаманн, Б. (1991). «Асимптотический решающий фактор: разрешение неоднозначности в маршевых кубах». Продолжающаяся визуализация '91 . С. 83–91. DOI : 10.1109 / VISUAL.1991.175782 . ISBN 9780818622458.
- Монтани, Клаудио; Скатени, Риккардо; Скопиньо, Роберто (1994). «Модифицированная справочная таблица для неявного устранения неоднозначности марширующих кубов». Визуальный компьютер . 10 (6): 353–355. DOI : 10.1007 / BF01900830 .
- Нильсон, GM; Чунвон Сон (1997). «Интервальная объемная тетраэдризация». Ход работы. Визуализация '97 (Кат. № 97CB36155) . С. 221–228. DOI : 10.1109 / VISUAL.1997.663886 . ISBN 978-0-8186-8262-9.
- Поль Бурк. «Обзор и исходный код» .
- Мэтью Уорд. «Обзор GameDev» .
- «Вводное описание с дополнительной графикой» .
- «Маршевые кубики» .. Немного из ранней истории Marching Cubes.
- Newman, Timothy S .; Йи, Хун (2006). «Обзор алгоритма походных кубов». Компьютеры и графика . 30 (5): 854–879. CiteSeerX 10.1.1.413.7458 . DOI : 10.1016 / j.cag.2006.07.021 .
- Стефан Диль. «Специализированные алгоритмы визуализации» (PDF) .