is_реклам:

пошук, категорії та ін. показати ▼

Алгоритми відсікання в графіці

Алгоритми відсікання в графіці
автор опубліковано

Многокутники особливо важливі в растровій графіці, як засіб задання поверхонь. Процес виділення тієї частини геометричного об’єкта, яка лежить поза видимою областю (вікном), називається відсіканням (clipping) . Задачі відсікання видимого зображення по границях деякої області в комп’ютерній графіці зустрічаються досить часто. Вони є головними геометричними задачами при візуалізації геометричних об’єктів.

Відсікання може проводитися прямокутним або многокутним вікном. Відомо, що часто графічні зображення складаються із сукупності відрізків. Для задачі відсікання, обчислюючи точки перетину відрізків, можна було б розрахувати ті частини відрізків, які знаходяться зовні вікна. Але це потребує виконання великої кількості обчислень.

Задачу відсікання можна розв’язувати різними методами. За способом розв’язування цієї задачі всі алгоритми поділяються на два класи:

aлгоритми, що використовують координати кінців відрізка або самого відрізка;

  • Сазерленда-Коена
  • FC-алгоритм

aлгоритми, що використовують параметричне задання самих відрізків і сторін вікна:

  • алгоритми Кіруса-Бека
  • Ейлера-Азертона

Перша група алгоритмів, з координатами кінців відрізка, застосовуються до прямокутних вікон, сторони яких паралельні осям координат, інша ж, алгоритми з параметричним заданням – до будь-яких вікон.

Алгоритм Сазерленда-Коена

при клацанні на зображення, можна скачати цю програму

достатньо просто й ефективно дозволяє прийняти або відсікти цілком відносно довільного прямокутного вікна. У цьому алгоритмі для кінців відрізка будуються 4-бітні коди, які визначають чи точка знаходиться справа-зліва-зверху-знизу вікна. Тобто площина з вікном розбивається на 9 областей, у кожній з яких є свій код. Аналізуючи значення кодів, визначаємо, де знаходиться відрізок, і, вже знаючи з якими ребрами вікна буде відбуватися перетин – шукаємо точки перетину і показуємо видиму частину відрізка.

FC-алгоритм

при клацанні на зображення, можна скачати цю програму
в даному методі кодуються не кінці відрізка, а сам відрізок. Площина з вікном розбивається на 9 областей, і вони кодуються цифрами від 1 до 9. Відрізок кодується наступним чином

             LineCode(ab)=Code(a)*10+Code(b),
де
     Code(a)         – код області з початковою точкою відрізка,
     Code(b)         – код області з кінцевою точкою відрізка,
     LineCode(ab)    – код відрізка.

Існує 81 можливий варіант розміщення відрізка, але серед них можна виділити 6 основних випадків, решта будуть симетричні їм. Щоб виділити 6 основних випадків, потрібно розглянути різні варіанти розміщення відрізка для некутових та кутових областей.

Для більш швидкої роботи алгоритму, можна використовувати коди в шістнадцядковій системі числення, що визначаються зі співвідношення

             LineCode(ab)=Code(a) shl 4+Code(b)
.

Алгоритм Кіруса-Бека

при клацанні на зображення, можна скачати цю програму
використовується в алгоритмах усунення невидимих частин сцени, коли потрібне відсікання довільним многокутником. Алгоритм базується на методі визначення орієнтації лінії, яка містить відрізок, що відсікається, по відношенню до сторони многокутника, а також на методі визначення місцезнаходження точки відрізка відносно вікна – всередині, на границі або зовні. Для цього в алгоритмі Кіруса-Бека використовується вектор внутрішньої нормалі до ребра вікна.

Алгоритм Вейлера-Азертона

при клацанні на зображення, можна скачати цю програму

використовується для відсікання довільних областей многокутним вікном. На відміну від інших алгоритмів, алгоритм Вейлера-Азертона дозволяє відсікти довільний неопуклий многокутник з дірками іншим неопуклим многокутником з дірками, причому можливе як зовнішнє, так і внутрішнє відсікання.

Кожен з многокутників в цьому алгоритмі задається циклічним списком вершин, причому вершини зовнішньої границі кожного многокутника обходяться за годинниковою стрілкою, а внутрішня границя (дірки) – проти годинникової стрілки. Якщо границі вікна і об’єкта перетинаються, то виникають вхідні і вихідні точки перетину ребер. Ці точки заносяться в циклічні списки вершин, щоб не порушити правила обходу границі многокутників. І відповідно обходячи ці точки, отримаємо частину видимого зображення.

P.S. Всі програми розроблені автором, тому за необхідності Ви можете використати коментарі або пишіть через форму зворотнього звязку, щоб отримати додаткову інформацію, наприклад: код прикладів, що наведено на рисунках .

схоже за тегами

Коментарів 4

  1. Ірина пише: Відповіcти

    у мене у лабораторній роботі попався алгоритм Сазерлена-Коена! у блозі досить детально описано сам алгоритм відсікання і добре, що є скріншот, можна глянути як то все виглядатиме! дуже круто!

    • Ангелина пише:

      Ірка, дякую! В інтернеті багато де є описаний сам метод, і детально його робота, але картинок майже немає. Сама в свій час шукала, тому і вирішила, що цей пост буде оригінальним доповненням тієї інформації, яка вже є!

  2. Ігор пише: Відповіcти

    Гарно Дякую!, по теорії все зрозуміло тепер треба взятись за практику.

    • Ангелина пише:

      Ігор, якщо клікнути на картинку, можна буде завантажити програму (правда без коду) і протестувати її на інших даних. Спробуйте!

Залишити коментар:

Яндекс цитирования UA TOP Bloggers