Введение

Алгоритм генерации контурных линий на 2D скалярном поле

В компьютерной графике алгоритм «марширующие квадраты» генерирует контуры для двухмерного скалярного поля (прямоугольная сетка отдельных числовых значений). Аналогичный метод может быть использован для построения контуров на 2D-треугольных сетях. Контуры могут быть двух типов:
Изолинии – линии, соответствующие одному уровню данных, или изозначению. Изополосы – заполненные области между изолиниями. Типичные области применения включают контурные линии на топографических картах или генерацию изобар для карт погоды. Алгоритм «марширующие квадраты» использует подход, аналогичный алгоритму «марширующие кубы» в 3D:
Обрабатывать каждую ячейку сетки независимо. Вычислить индекс ячейки, сравнивая уровень контура со значениями данных в углах ячейки. Использовать предварительно созданную таблицу поиска, индексированную по индексу ячейки, для описания выходной геометрии ячейки. Применить линейную интерполяцию вдоль границ ячейки для вычисления точного положения контура.

Уточнение о точках седла

Контур неоднозначен в седловых точках. Эту неоднозначность можно устранить, используя среднее значение данных в центре ячейки для выбора между различными способами соединения интерполированных точек (четыре изображения в правом нижнем углу).

Контурные треугольные сетки

Тот же базовый алгоритм может быть применен к треугольным сетям, которые состоят из соединенных треугольников, к вершинам которых привязаны данные. Например, разрозненный набор точек данных можно соединить с помощью триангуляции Делоне, чтобы построить линии равных значений поля данных. Треугольная ячейка всегда плоская, поскольку является 2-симплексом (то есть определяется n+1 вершинами в n-мерном пространстве). Для треугольника всегда существует единственный линейный интерполянт, и исключена возможность неоднозначного седла.

Размеры и пространства

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

Оценка эффективности

Алгоритм обладает тривиальной распараллеливаемостью, поскольку все ячейки обрабатываются независимо. Легко разработать параллельный алгоритм, исходя из следующих предположений:
Общее скалярное поле ввода, доступное только для чтения. Общий выходной поток геометрии, предназначенный только для добавления данных. Наивная реализация алгоритма Marching Squares, обрабатывающая каждую ячейку независимо, будет выполнять каждую линейную интерполяцию дважды (для изолиний) или четыре раза (для изопасок). Соответственно, выходные данные будут содержать 2 копии 2D-вершин для несвязанных линий (изолиний) или 4 копии для полигонов (изопасок). [При условии, что: сетка достаточно велика, чтобы большинство ячеек были внутренними; и создается полный непрерывный набор изопасок.] Возможно уменьшить вычислительные затраты за счет кэширования результатов интерполяции. Например, однопоточной последовательной версии потребуется кэшировать интерполированные результаты только для одной строки входной сетки. Также можно уменьшить размер выходных данных, используя индексированные геометрические примитивы, то есть создать массив 2D-вершин и задавать линии или полигоны с помощью коротких целочисленных смещений в этом массиве.