Марширующие площади - Википедия - Marching squares

Маршевые площади это компьютерная графика алгоритм что порождает контуры для двумерного скалярное поле (прямоугольный множество индивидуальных числовых значений). Аналогичный метод можно использовать для контурной 2D треугольные сетки.

Контуры могут быть двух видов:

  • Изолинии - строки, следующие за одним уровнем данных, или isvalue.
  • Изобанды - залитые области между изолиниями.

Типичные приложения включают контурные линии на топографических картах или построение изобар для карт погоды.

Маршевые квадраты используют аналогичный подход к 3D маршевые кубики алгоритм:

  • Обработка каждой ячейки в сетке независимо.
  • Вычислите индекс ячейки, сравнивая уровень (уровни) контура со значениями данных в углах ячейки.
  • Используйте готовый Справочная таблица, привязанный к индексу ячейки, чтобы описать выходную геометрию ячейки.
  • Подать заявление линейная интерполяция по границам ячейки для расчета точного положения контура.

Базовый алгоритм

Вот шаги алгоритма:

Примените порог к 2D-полю, чтобы двоичный изображение, содержащее:

  • 1, где значение данных над значение
  • 0, где значение данных ниже значение

Каждый блок пикселей 2x2 в двоичном изображении образует контурную ячейку, поэтому все изображение представлено сеткой таких ячеек (показано зеленым на рисунке ниже). Обратите внимание, что эта контурная сетка на одну ячейку меньше в каждом направлении, чем исходное 2D-поле.

Для каждой ячейки контурной сетки:

  1. Составьте 4 биты по углам ячейки для построения двоичного индекса: обойдите ячейку в по часовой стрелке направление добавления кусочек в индекс, используя побитовое ИЛИ и левый "шифт, из старший бит вверху слева, чтобы младший бит внизу слева. Результирующий 4-битный индекс может иметь 16 возможных значений в диапазоне 0–15.
  2. Используйте индекс ячейки, чтобы получить доступ к предварительно созданной Справочная таблица с 16 записями, в которых перечислены края, необходимые для представления ячейки (показано в нижней правой части рисунка ниже).
  3. Подать заявление линейная интерполяция между исходными значениями данных поля, чтобы найти точное положение контурной линии по краям ячейки.

Иллюстрация алгоритма маршевых квадратов.

Устранение неоднозначности седловых точек

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

Маршевые площади

Изобанды

Аналогичный алгоритм может быть создан для закрашенных контурных полос в пределах верхнего и нижнего пороговых значений:

Марширующие квадраты в корпусе изобанды

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

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

Изолинии

Анализ для изолинии над треугольниками особенно просто: есть 3 двоичных цифры, поэтому 8 вариантов:

Случай марширующих треугольников, случай изолинии

Изобанды

Анализ для изобанды над треугольниками требует 3 троичных трита, поэтому 27 возможностей:

Футляры марширующих треугольников, футляры изобанд

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

В пространство данных для алгоритма Marching Squares - это 2D, потому что вершинам, которым присвоено значение данных, подключены их соседи в 2D топологический сетка, но пространственные координаты, назначенные вершинам, могут быть в 2D, 3D или более высоких измерениях.

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

Соображения производительности

Алгоритм такой смущающе параллельный, потому что все ячейки обрабатываются независимо. Легко написать параллельный алгоритм предполагая:

  • Общее скалярное поле ввода только для чтения.
  • Общий выходной поток геометрии только для добавления.

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

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

Также можно уменьшить размер вывода, используя индексированные геометрические примитивы, т.е. создать множество 2D-вершин и укажите линии или многоугольники с короткое целое число смещения в массив.

Рекомендации

  • Мэйпл, К. (2003). Геометрический дизайн и планирование пространства с использованием алгоритмов маршевых квадратов и маршевых кубов. Proc. 2003 г. Конф. Геометрическое моделирование и графика. С. 90–95. Дои:10.1109 / GMAG.2003.1219671. ISBN  978-0-7695-1985-2.
  • Бэнкс, Д. С. (2004). «Подсчет случаев в алгоритмах подстановки». IEEE Trans. Визуальный. Комп. Графика. 10 (4): 371–384. CiteSeerX  10.1.1.582.7221. Дои:10.1109 / TVCG.2004.6. PMID  18579966.
  • Laguardia, J. J .; Cueto, E .; Добларе, М. (2005). «Метод естественного соседа Галеркина со структурой дерева квадрантов». Int. J. Numer. Meth. Инженер. 63 (6): 789–812. Bibcode:2005IJNME..63..789L. Дои:10.1002 / nme.1297.
  • Шефер, Скотт; Уоррен, Джо (2005). «Двойные маршевые кубы: контурирование прима и двойные сетки». Комп. График. Форум. 24 (2): 195–201. Дои:10.1111 / j.1467-8659.2005.00843.x.
  • Манц, Хубер; Джейкобс, Карин; Меке, Клаус (2008). «Использование функционалов Минковского для анализа изображений: алгоритм маршевого квадрата». J. Stat. Механизм .: Theory Exp. 2008 (12): P12015. Bibcode:2008JSMTE..12..015M. Дои:10.1088 / 1742-5468 / 2008/12 / P12015.
  • Cipolletti, Marina P .; Delrieux, Claudio A .; Перилло, Херардо М. Э .; Пикколо, М. Синтия (2012). «Сегментация границ сверхвысокого разрешения и измерения в изображениях дистанционного зондирования». Комп. Geosci. 40: 87–97. Bibcode:2012CG ..... 40 ... 87C. Дои:10.1016 / j.cageo.2011.07.015.

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