Алгоритм «Marching Cubes» для извлечения изоповерхностей

Введение

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

История

Алгоритм был разработан Уильямом Э. Лоренсеном (1946–2019) и Харви Э. Клайн в результате их исследований для General Electric. В General Electric они работали над способом эффективной визуализации данных, полученных с устройств КТ и МРТ. В основе алгоритма лежит разделение входного объема на дискретный набор кубов. При условии линейной реконструкции фильтрации, каждый куб, содержащий фрагмент заданной изоповерхности, может быть легко идентифицирован, поскольку значения выборки в вершинах куба должны охватывать значение целевой изоповерхности. Для каждого куба, содержащего часть изоповерхности, генерируется треугольная сетка, аппроксимирующая поведение трилинейного интерполянта внутри куба. Первая опубликованная версия алгоритма использовала вращательную и зеркальную симметрию, а также внесла изменения в таблицу, содержащую 15 уникальных случаев. Однако, из-за неоднозначности поведения трилинейного интерполянта на гранях и внутри кубов, сетки, полученные с помощью Marching Cubes, демонстрировали разрывы и топологические проблемы. Для куба сетки неоднозначность грани возникает, когда знаки его вершин чередуются: вершины одной диагонали на этой грани положительны, а вершины на другой – отрицательны. Следует отметить, что в этом случае знаков вершин грани недостаточно для определения правильного способа триангуляции изоповерхности. Аналогично, внутренняя неоднозначность возникает, когда знаков вершин куба недостаточно для определения корректной триангуляции поверхности, то есть, когда для одной и той же конфигурации куба возможны несколько вариантов триангуляции. Популярность Marching Cubes и его широкое распространение привели к ряду улучшений алгоритма, направленных на устранение неоднозначностей и корректное отслеживание поведения интерполянта. Дёрст в 1988 году первым отметил, что таблица триангуляции, предложенная Лоренсеном и Клайном, была неполной, и что некоторые случаи Marching Cubes допускают множественные триангуляции. "Дополнительная ссылка" Дёрста относилась к более раннему, более эффективному (см. де Араухо) алгоритму изополигонизации поверхности, разработанному Уайвиллом, Уайвиллом и Макфитерсом. Позже, Нильсон и Хаманн в 1991 году обнаружили неоднозначность поведения интерполянта на гранях куба и предложили тест, названный "Асимптотический решатель", для корректного отслеживания интерполянта на гранях куба. Фактически, как заметил Натараджан в 1994 году, эта проблема неоднозначности возникает и внутри куба. В своей работе автор предложил тест устранения неоднозначности, основанный на критических точках интерполянта, и добавил четыре новых случая в таблицу триангуляции Marching Cubes (подслучаи случаев 3, 4, 6 и 7). Даже после всех предложенных улучшений алгоритма и его таблицы триангуляции, сетки, генерируемые Marching Cubes, все еще содержали топологические несоответствия. Marching Cubes 33, предложенный Черняевым в 1995 году, является одним из первых алгоритмов извлечения изоповерхности, предназначенных для сохранения топологии трилинейного интерполянта. В своей работе Черняев расширил число случаев в таблице поиска триангуляции до 33 и предложил иной подход к решению внутренних неоднозначностей, основанный на Асимптотическом решателе. Позднее, в 2003 году, Нильсон доказал, что таблица поиска Черняева полна и может представлять все возможные варианты поведения трилинейного интерполянта, а Левинер и др. предложили реализацию алгоритма. Также в 2003 году Лопес и Бродли расширили тесты, предложенные Натараджаном, выявили и исправили алгоритмические неточности, которые нарушали топологическую корректность сетки, сгенерированной алгоритмом Marching Cubes 33, предложенным Черняевым.

The algorithm was developed by William E. Lorensen (1946 2019) and Harvey E. Cline as a result of their research for General Electric. At General Electric they worked on a way to efficiently visualize data from CT and MRI devices. The premise of the algorithm is to divide the input volume into a discrete set of cubes. By assuming linear reconstruction filtering, each cube, which contains a piece of a given isosurface, can easily be identified because the sample values at the cube vertices must span the target isosurface value. For each cube containing a section of the isosurface, a triangular mesh that approximates the behavior of the trilinear interpolant in the interior cube is generated. The first published version of the algorithm exploited rotational and reflective symmetry and also sign changes to build the table with 15 unique cases. However, due to the existence of ambiguities in the trilinear interpolant behavior in the cube faces and interior, the meshes extracted by the Marching Cubes presented discontinuities and topological issues. Given a cube of the grid, a face ambiguity occurs when its face vertices have alternating signs. That is, the vertices of one diagonal on this face are positive and the vertices on the other are negative. Observe that in this case, the signs of the face vertices are insufficient to determine the correct way to triangulate the isosurface. Similarly, an interior ambiguity occurs when the signs of the cube vertices are insufficient to determine the correct surface triangulation, i. e., when multiple triangulations are possible for the same cube configuration. The popularity of the Marching Cubes and its widespread adoption resulted in several improvements in the algorithm to deal with the ambiguities and to correctly track the behavior of the interpolant. Durst in 1988 was the first to note that the triangulation table proposed by Lorensen and Cline was incomplete, and that certain Marching Cubes cases allow multiple triangulations. Durst's 'additional reference' was to an earlier, more efficient (see de Araujo) isosurface polygonization algorithm by Wyvill, Wyvill and McPheeters. Later, Nielson and Hamann in 1991 observed the existence of ambiguities in the interpolant behavior on the face of the cube. They proposed a test called Asymptotic Decider to correctly track the interpolant on the faces of the cube. In fact, as observed by Natarajan in 1994, this ambiguity problem also occurs inside the cube. In his work, the author proposed a disambiguation test based on the interpolant critical points, and added four new cases to the Marching Cubes triangulation table (subcases of the cases 3, 4, 6 and 7). At this point, even with all the improvements proposed to the algorithm and its triangulation table, the meshes generated by the Marching Cubes still had topological incoherencies. The Marching Cubes 33, proposed by Chernyaev in 1995, is one of the first isosurface extraction algorithms intended to preserve the topology of the trilinear interpolant. In his work, Chernyaev extends to 33 the number of cases in the triangulation lookup table. He then proposes a different approach to solve the interior ambiguities, which is based on the Asymptotic Decider. Later, in 2003, Nielson proved that Chernyaev's lookup table is complete and can represent all the possible behaviors of the trilinear interpolant, and Lewiner et al. proposed an implementation to the algorithm. Also in 2003 Lopes and Brodlie extended the tests proposed by Natarajan. noted and corrected algorithmic inaccuracies that compromised the topological correctness of the mesh generated by the Marching Cubes 33 algorithm proposed by Chernyaev.

Алгоритм

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

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

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