Марширующие площади
 | Эта статья включает список литературы , связанную литературу или внешние ссылки , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . ( февраль 2022 г. ) |
В компьютерной графике марширующие квадраты — это алгоритм , генерирующий контуры для двумерного скалярного поля (прямоугольного массива отдельных числовых значений). Подобный метод можно использовать для контурирования 2D- треугольных сеток .
Контуры могут быть двух видов:
- Изолинии — линии, следующие за одним уровнем данных или изозначением .
- Изобанды – закрашенные области между изолиниями.
Типичные применения включают контурные линии на топографических картах или создание изобар для карт погоды .
Марширующие квадраты используют аналогичный подход к алгоритму марширующих кубов в 3D :
- Обрабатывайте каждую ячейку сетки независимо.
- Рассчитайте индекс ячейки, сравнивая уровень(и) контура со значениями данных в углах ячейки.
- Используйте предварительно созданную таблицу поиска , основанную на индексе ячейки, чтобы описать выходную геометрию ячейки.
- Примените линейную интерполяцию вдоль границ ячейки, чтобы вычислить точное положение контура.
Основной алгоритм
[ редактировать ]Вот этапы алгоритма:
Примените порог к 2D-полю, чтобы создать двоичное изображение, содержащее:
- 1, где значение данных превышает изозначение
- 0, где значение данных ниже изозначения
Примечание. Данные, равные изозначению, следует рассматривать как выше или ниже последовательно .
Каждый блок пикселей 2х2 в бинарном изображении образует контурную ячейку, поэтому все изображение представлено сеткой таких ячеек (показано зеленым на рисунке ниже). Обратите внимание, что эта контурная сетка на одну ячейку меньше в каждом направлении, чем исходное 2D-поле.
Для каждой ячейки контурной сетки:
- Составьте 4 бита в углах ячейки, чтобы построить двоичный индекс: обойдите ячейку по часовой стрелке, добавляя бит к индексу, используя побитовое ИЛИ и сдвиг влево , от наиболее значимого бита в левом верхнем углу до наименьшего. значащий бит внизу слева. Результирующий 4-битный индекс может иметь 16 возможных значений в диапазоне 0–15.
- Используйте индекс ячейки для доступа к предварительно созданной таблице поиска с 16 записями, в которых перечислены ребра, необходимые для представления ячейки (показано в правой нижней части рисунка ниже).
- Примените линейную интерполяцию между исходными значениями данных поля, чтобы найти точное положение контурной линии по краям ячейки.
Разрешение неоднозначности седловых точек
[ редактировать ]контур неоднозначен В седловых точках . Можно устранить неоднозначность, используя среднее значение данных для центра ячейки для выбора между различными соединениями интерполируемых точек (четыре изображения в правом нижнем углу):
Изобанды
[ редактировать ]Аналогичный алгоритм можно создать и для закрашенных контурных полос в пределах верхнего и нижнего пороговых значений:
Контурные треугольные сетки
[ редактировать ]Тот же базовый алгоритм можно применить к треугольным сеткам , которые состоят из связанных треугольников, вершинам которых присвоены данные. Например, разбросанный набор точек данных можно соединить с помощью триангуляции Делоне , чтобы можно было контурировать поле данных.
Треугольная ячейка всегда плоская , поскольку она является 2-симплексом (т. е. задана n +1 вершиной в n -мерном пространстве). В треугольнике всегда существует уникальный линейный интерполянт и нет возможности неоднозначного седла.
Изолинии
[ редактировать ]Анализ изолиний над треугольниками особенно прост: имеется 3 двоичных цифры, поэтому существует 8 возможностей:
Изобанды
[ редактировать ]Анализ изобанд над треугольниками требует 3 тройных тритов, поэтому существует 27 возможностей:
Размеры и пространство
[ редактировать ]Пространство данных для алгоритма «Марширующие квадраты» является двумерным, поскольку вершины, которым присвоено значение данных, соединены со своими соседями в двумерной топологической сетке, но пространственные координаты, присвоенные вершинам, могут быть в двухмерных, трехмерных или более высоких измерениях.
Например, треугольная сетка может представлять собой двумерную поверхность данных, встроенную в трехмерное пространство, где пространственные положения вершин и интерполированных точек вдоль контура будут иметь три координаты. Обратите внимание, что случай квадратов снова неоднозначен, поскольку четырехугольник, встроенный в трехмерное пространство, не обязательно является плоским, поэтому существует выбор схемы геометрической интерполяции для рисования полосатых поверхностей в трехмерном пространстве.
Вопросы производительности
[ редактировать ]Алгоритм до неприличия параллельный , поскольку все ячейки обрабатываются независимо. Легко написать параллельный алгоритм, предполагая:
- Общее входное скалярное поле, доступное только для чтения.
- Общий выходной поток геометрии, предназначенный только для добавления.
Простая реализация Marching Squares, которая обрабатывает каждую ячейку независимо, будет выполнять каждую линейную интерполяцию дважды (изолиния) или четыре раза (изолиния). Аналогично, выходные данные будут содержать 2 копии 2D-вершин для непересекающихся линий (изолиний) или 4 копии для полигонов (изобанды). [При предположении, что: сетка большая, поэтому большинство ячеек являются внутренними; и создается полный непрерывный набор изобанд.]
Уменьшить вычислительные затраты можно за счет кэширования результатов интерполяции. Например, однопоточной последовательной версии потребуется кэшировать интерполированные результаты только для одной строки входной сетки.
Также возможно уменьшить размер вывода, используя индексированные геометрические примитивы, т.е. создать массив 2D вершин и указать линии или многоугольники с короткими целочисленными в массиве смещениями.
Ссылки
[ редактировать ]- Мэйпл, К. (2003). «Геометрическое проектирование и планирование пространства с использованием алгоритмов марширующих квадратов и марширующего куба». 2003 Международная конференция по геометрическому моделированию и графике, 2003. Материалы . стр. 90–95. дои : 10.1109/GMAG.2003.1219671 . ISBN 978-0-7695-1985-2 . S2CID 11320513 .
{{cite book}}:|journal=игнорируется ( помогите ) - Бэнкс, округ Колумбия (2004). «Подсчет случаев в алгоритмах подститопов». IEEE Транс. Визуальный. Комп. Графика . 10 (4): 371–384. CiteSeerX 10.1.1.582.7221 . дои : 10.1109/TVCG.2004.6 . ПМИД 18579966 . S2CID 2450480 .
- Лагуардия, Джей-Джей; Куэто, Э.; Добларе, М. (2005). «Естественный соседский метод Галёркина со структурой квадродерева» . Межд. Дж. Нумер. Методы англ . 63 (6): 789–812. Бибкод : 2005IJNME..63..789L . дои : 10.1002/nme.1297 . S2CID 122746298 .
- Шефер, Скотт; Уоррен, Джо (2005). «Двойные марширующие кубы: первичное контурирование двойных сеток». Форум компьютерной графики . 24 (2): 195–201. дои : 10.1111/j.1467-8659.2005.00843.x . S2CID 10015045 .
- Манц, Хубер; Джейкобс, Карин; Мекке, Клаус (2008). «Использование функционалов Минковского для анализа изображений: алгоритм марширующего квадрата». Дж. Стат. Механика: Теория Exp . 2008 (12): 12015. Бибкод : 2008JSMTE..12..015M . дои : 10.1088/1742-5468/2008/12/P12015 . S2CID 122873298 .
- Чиполлетти, Марина П.; Дельрье, Клаудио А.; Перилло, Херардо МЭ; Пикколо, М. Синтия (2012). «Сегментация и измерение границ сверхвысокого разрешения на изображениях дистанционного зондирования». Комп. Геоски . 40 : 87–97. Бибкод : 2012CG.....40...87C . дои : 10.1016/j.cageo.2011.07.015 .
Внешние ссылки
[ редактировать ]- Алгоритм Matlab «Марширующий квадрат» — простой для понимания алгоритм марширующего квадрата с открытым исходным кодом.
- реализация на Java
- Код Marching Squares на Java. Учитывая набор двумерных данных и пороговые значения, возвращает GeneralPath[] для упрощения построения графиков.
- Объяснение извилистых треугольников и пример реализации Python.
- Код Marching Squares на C — единая библиотека заголовков для марширующих квадратов, которая может экспортировать треугольные сетки для упрощения рендеринга.