Marching squares

Marching squares
Схематическое изображение алгоритма: цвет квадрата обозначает значение в данной клетке регулярной сетки, чем темнее - тем значение ближе к изолиниям. Красным показаны полученные изолинии.

Marching Squares (англ. движущиеся квадраты) – алгоритм в компьютерной графике, который генерирует изолинии на двухмерном скалярном поле.

Применение

Алгоритм используется при визуализации изобар на картах погоды и горизонталей на географических картах. Является упрощением алгоритма marching cubes для плоского случая.

Принцип работы

На вход алгоритм получает регулярную сетку, в каждом узле которой известно значение поля. Выходная сетка (на рисунке обозначена синим цветом) может иметь меньшее разрешение (в этом случае теряется точность, но уменьшается ступенчатость). Далее для каждого узла выходной сетки проверяется, выше ли значение в нем, чем на изоповерхности. Всем узлам, которые выше, приписывается "+", остальным "–". Далее рассматриваются квадратики выходной сетки, вершины которых лежат в отмеченных узлах. Всего получается 16 различных случаев, которые с учетом симметрий и поворотов можно свести к четырем:

  • Случай 1: все вершины имеют один знак
  • Случай 2: у одной вершины знак отличается
  • Случай 3: вершины с одинаковыми знаками имеют общее ребро
  • Случай 4: вершины с одинаковыми знаками не имеют общего ребра

В четвертом случае невозможно однозначно определить форму сегмента изолинии, поэтому дополнительно просматривается значение в центре квадрата (если входные данные это позволяют). При невозможности узнать значение в центре квадрата принятое решение может повлиять на связность изолинии.

  • Случай 1: все вершины находятся выше (или ниже) изоповерхности.

  • Случай 2: за исключением одной, все вершины находятся выше (или ниже) изоповерхности.

  • Случай 3: две вершины на одном ребре находятся выше (или ниже) изоповерхности.

  • Случай 4: две вершины, не имеющие общего ребра, находятся выше (или ниже) изоповерхности.

  • Решение Случая 4 при положительном значении в ячейке.

  • Решение Случая 4 при отрицательном значении в ячейке.

Для улучшения качества получаемой изолинии применяется линейная интерполяция. В таком случае конец сегмента изолинии на ребре квадрата делит ребро в отношении \frac{f_1-c}{c-f_2}, где f_1, f_2 - значения на концах ребра квадрата, c - значение изолинии. Фактически, конец сегмента изолинии "подтягивается" к тому концу ребра, который ближе к реальной изолинии.

Ссылки


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Полезное


Смотреть что такое "Marching squares" в других словарях:

  • Marching squares — is a computer graphics algorithm that generates contours for a two dimensional scalar field (rectangular array of individual numerical values). A similar method can be used to contour 2D triangle meshes. The contours can be of two kinds: Isolines …   Wikipedia

  • Marching Squares — Les Marching squares designent un algorithme de reconstruction de surface implicites (ou isosurfaces) en deux dimensions. Le principe est le même que pour les Marching cubes, mais fonctionnant sur un plan, utilisant donc des carrés au lieux de… …   Wikipédia en Français

  • Marching Squares — Schematische Darstellung des Algorithmus: Die grauen Quadrate sind Datenwerte auf einem Gitter. Rot dargestellt ist die Isolinie für einen Isowert im dunklen Grauwertbereich. Marching Squares (von englisch „marschierende Quadrate“) ist ein… …   Deutsch Wikipedia

  • Marching squares — Les marching squares désignent un algorithme de reconstruction de surface implicites (ou isosurfaces) en deux dimensions. Le principe est le même que pour les Marching cubes, mais fonctionnant sur un plan, utilisant donc des carrés au lieu de… …   Wikipédia en Français

  • Marching Cubes — Tête et structures cérébrales (cachées) obtenues par l application des marching cubes sur 150 tranches provenant d un IRM (env. 150 000 triangles) Les « marching cubes » désignent un algorithme d infographie publié à la conférence… …   Wikipédia en Français

  • Marching cubes — Head and cerebral structures (hidden) extracted from 150 MRI slices using marching cubes (about 150,000 triangles) Marching cubes is a computer graphics algorithm, published in the 1987 SIGGRAPH proceedings by Lorensen and Cline,[1] …   Wikipedia

  • Marching cubes — Модель, построенная из 150 слоев с МРТ с использованием алгоритма marching cubes. Под поверхностью находятся около 150 000 полигонов и скрытых объектов. Размер сетки составляет 64 × 64 × 150 вокселей, кодированных 8 ю… …   Википедия

  • Marching cubes — Tête et structures cérébrales (cachées) obtenues par l application des marching cubes sur 150 tranches provenant d un IRM (env. 150 000 triangles) Les « marching cubes » désignent un algorithme d infographie publié à la conférence… …   Wikipédia en Français

  • List of mathematics articles (M) — NOTOC M M estimator M group M matrix M separation M set M. C. Escher s legacy M. Riesz extension theorem M/M/1 model Maass wave form Mac Lane s planarity criterion Macaulay brackets Macbeath surface MacCormack method Macdonald polynomial Machin… …   Wikipedia

  • Metaball — Metaballs Deux metaballs Les metaballs sont une technique utilisée en infographie pour créer des formes organiques ou représenter des fluides. En français, on trouve également la dénomination « objets mous ». Les metaballs sont une… …   Wikipédia en Français


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»