Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

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 - Значення ізолінії. Фактично, кінець сегмента ізолінії "підтягується" до того кінця ребра, який ближче до реальної ізолінії.


Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Marching cubes
© Усі права захищені
написати до нас
Рейтинг@Mail.ru