Интернет магазин китайских планшетных компьютеров



Компьютеры - Marching squares

11 мая 2011





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

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

Применение

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

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

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

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

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

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



Просмотров: 795


<<< Khronos Group