Порівняльні характеристики трьох найбільш ефективних алгоритмів малювання відрізка

Вступ

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

Автоматизація проектно-конструкторських робіт (САПР). Це традиційна галузь застосування, з якої починалося використання машинної графіки.

Автоматизація наукових досліджень (АСНІ).

Графічні інформаційні дозволяють отримувати високоякісні Тополя-геодезичні, географічні карта, карти для буріння, погодні карти і т.п.

Автоматизація процесів навчання.

Видавнича діяльність, реклама, комп'ютерні ігри, мультиплікація.

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

Об'єктом дослідження в нашій роботі будуть методи генерації відрізків.

Мета нашої роботи - розглянути методи генерації відрізків, виділити їх основні характеристики, зробити висновок про їх ефективності, швидкодії.

Для досягнення поставленої мети визначені наступні завдання:

1. На основі аналізу літератури розглянути алгоритми генерації відрізків, виділити їхні переваги та недоліки.

2. Розробити програму, що реалізує три методи генерації відрізків і створює всі умови для роботи з даними алгоритмами

3. Продемонструвати різні алгоритми генерації відрізків.

4. Порівняти швидкодію використовуваних алгоритмів.

5. Зробити висновок про ефективність різних алгоритмів генерації відрізків.

Методи дослідження: теоретичний, експериментальний.

В даній програмі реалізовано три алгоритму креслення відрізків: Цифровий диференціальний аналізатор (ЦБА), алгоритм Брезенхема і процедуру LineTo.

1. Теоретична частина

1.1. Комп'ютерна графіка

Розрізняють три види комп'ютерної графіки: растрова графіка, векторна графіка і фрактальна графіка. Вони відрізняються принципами формування зображення при відображенні на екрані монітора або при друці на папері.

растрову графіку застосовують при розробці електронних (мультимедійних) і поліграфічних видань. Ілюстрації, виконані засобами растрової графіки, рідко створюють вручну за допомогою комп'ютерних програм. Для цієї мети сканують ілюстрації, підготовлені художником на папері, або фотографії. Останнім часом для вводу растрових зображень в комп'ютер знайшли широке застосування цифрові фото - і відеокамери. В Інтернеті поки застосовуються тільки растрові ілюстрації.

Програмні засоби для роботи з векторною графікою, навпаки, призначені для створення ілюстрацій і в меншій мірі для їх обробки. Такі засоби широко використовують в рекламних агентствах, дизайнерських бюро, редакціях і видавництвах. Оформлювальні роботи, засновані на застосуванні шрифтів і найпростіших геометричних елементів, вирішуються засобами векторної графіки простіше. Є приклади високохудожніх творів, створених засобами векторної графіки, але вони скоріше виключення, ніж правило.

Програмні засоби для роботи з графікою фрактальної призначені для автоматичної створення зображень шляхом математичних розрахунків. Створення фрактальної художньої композиції полягає не в малюванні або оформленні, & в програмуванні. Фрактальну графіком частіше використовують у розважальних програмах.

1.2 Растрова графіка

В растрової графіку основним елементом є крапка. При екранному зображення ця точка називається пікселем.

Основна проблема і недолік при використанні растрових зображень - це великі обсяги даних. Для робіт з великорозмірного ілюстраціями типу журнальної смуги вимагаються комп'ютери з великими розмірами оперативної пам'яті (128 Мбайт і більше). Такі комп'ютери, природно, повинні при цьому мати і високопродуктивні процесори.

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

Будь-яке зображення, в тому числі і тривимірне, складається з графічних примітивів, тому необхідно знати спеціальні методи створення зображення, креслення прямих і кривих ліній, зафарбовування багатокутників, що створює враження суцільних об'єктів. Розглянемо деякі з цих методів.

Алгоритми креслення відрізків. Екран дисплея можна розглядати як матрицю дискретних елементів (пікселів), кожен з яких може бути підсвічується. У зв'язку з цим не можна безпосередньо провести відрізок з однієї точки в іншу. Процес визначення крапок, найкращим чином апроксимуючих заданий відрізок, називається розкладом в растр. Для горизонтальних, вертикальних і нахилених під кутом 45 ° відрізків вибір растрових елементів очевидний. При будь-який інший орієнтації вибрати потрібні пікселі важче. Існують різні алгоритми виконують це завдання, наприклад, цифровий диференціальний аналізатор і алгоритм Брезенхема.

Алгоритм Брезенхема для генерації кіл. У растр потрібно розкладати не тільки лінійні, але й інші, більш складні функції. Розкладання конічних перерізів, тобто кіл, еліпсів, парабол, гіпербол, присвячено значну кількість робіт. Найбільшу увагу приділено кола. Один з найбільш ефективних і простих для розуміння алгоритмів генерації кола належить Брезенхему.

Спочатку необхідно згенерувати лише одну восьму частину кола. Решта її частини можуть бути отримані послідовними відбитками. Якщо згенерований перший Октант (від 0 ° до 45 ° проти годинникової стрілки), то другий Октант можна отримати дзеркальним відображенням відносно прямої у = х, що дає в сукупності перший квадрант. Перший квадрант відбивається відносно прямої х = 0 для отримання відповідної частини кола у другому квадранті. Верхня півколо відбивається відносно прямої у = О для завершення побудови.

Растрова розгортка суцільних областей. Можливість подання суцільних областей в растровому графічному пристрої є його унікальною характеристикою. Генерація суцільних областей з простих описів ребер або вершин називається растрової розгорткою суцільних областей, заповненням багатокутників або заповненням контурів. Для цього можна використовувати різні способи, які зазвичай поділяються на дві широкі категорії: растрова развертка і початковий заповнення.

В методи растрової розгортки намагаються визначити в порядку сканування рядків, чи лежить точка всередині багатокутника або контуру. Ці алгоритми зазвичай йдуть від "верху" багатокутника або контуру до "низу".

В методах початковий заповнення передбачається, що відома деяка точка (запал) всередині замкнутого контуру. В алгоритмах шукають точки, сусідні з початковий і розташовані всередині контура. Якщо сусідня точка розташована не всередині, значить, виявлена межа контуру. Якщо ж точка опинилася всередині контуру, то вона стає новою початковий точкою і пошук триває рекурсивно.

Растрова розгортка багатокутників. Можна розробити ефективний метод растрової розгортки багатокутників, якщо скористатися тим фактом, що сусідні пікселі, ймовірно, мають однакові характеристики (крім пікселів граничних ребер). Ця властивість називається просторової когерентністю.

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

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

Алгоритми заповнення з затравкою. У розглянутих алгоритмах заповнення відбувається в порядку сканування. Інший підхід використовується в алгоритмах заповнення з затравкою. У них передбачається, що відомий хоча б один піксель з внутрішній області багатокутника. Алгоритм намагається знайти і зафарбувати все інші пікселі, що належать внутрішній області. Області можуть бути або внутрішні, або гранично-визначені. Якщо область відноситься до внутрішньо-визначеним, то всі пікселі, що належать внутрішньої частини, мають один і той же колір або інтенсивність, а всі пікселі, зовнішні по відношенню до області, мають інший колір. Якщо область відноситься до гранично-визначеним, то всі пікселі на межі області мають вибраного значення або колір. Алгоритми, заповнюють внутрішньо-певні області, називаються внутрішньо-за-виконуваних, а алгоритми для гранично-певних областей - гранично-заповнюють.

1.3 Векторна графіка

Як в растрової графіку основним елементом зображення є точка, так в векторну графіку основним елементом зображення є лінія, при цьому не важливо, це пряма лінія крива.

В растрової графіку теж існують лінії, але там вони розглядаються як комбінації точок. Для кожної точки лінії в растрової графіку відводиться одна або кілька комірок пам'яті (чим більше кольорів можуть мати точки, тим більше клітинок їм виділяється). Відповідно, чим довше растрова лінія, тим більше пам'яті вона займає. У векторну графіку обсяг пам'яті, який займає лінією, не залежить від розмірів лінії, оскільки лінія представляється у вигляді формули, а точніше кажучи, у вигляді декількох параметрів. Щоб не робили з цією лінією, змінюються тільки її параметри, що зберігаються в комірках пам'яті. Кількість же осередків залишається незмінним для будь-якої лінії.

Лінія - Це елементарний об'єкт векторної графіки. Все, що є в векторної ілюстрації, складається з ліній. Найпростіші об'єкти об'єднуються в більш складні, наприклад, об'єкт чотирикутник можна розглядати як чотири пов'язані лінії, а об'єкт куб ще більш складний: його можна розглядати або як дванадцять пов'язаних ліній, або як шість пов'язаних чотирикутників. Через такого підходу векторну графіку часто називають об'єктно-орієнтованої графікою.

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

Як і всі об'єкти, лінії мають властивості. До цих властивостей відносяться: форма лінії, її товщина, колір, характер лінії (суцільна, пунктирна і т.п.). Замкнені лінії мають властивість заповнення. Внутрішня область замкнутого контуру може бути заповнена кольором, текстурою, картою. Найпростіша лінія, якщо вона не замкнута, має дві вершини, які називаються вузлами. Вузли теж мають властивості, від яких залежить, як виглядає вершина лінії і як дві лінії сполучаються між собою.

1.4 Алгоритми креслення відрізків

Оскільки екран растрового дисплея з електронно-променевою трубкою (ЕПТ) можна розглядати як матрицю дискретних елементів (пікселів), кожен з яких може бути підсвічений, не можна безпосередньо провести відрізок з однієї точки в іншу. Процес визначення пікселів, найкращим чином апроксимуючих заданий відрізок, називається розкладом в растр. У поєднанні з процесом порядкової візуалізації зображення він відомий як перетворення растрової розгортки. Для горизонтальних, вертикальних і нахилених під кутом 45 ° відрізків вибір растрових елементів очевидний. При будь-якій іншій орієнтації вибрати потрібні пікселі важче, що показано на рис. 1.1.

Рис. 1.1 Розкладання в растр відрізків прямих

Перш ніж приступати до обговорення конкретних алгоритмів малювання відрізків, корисно розглянути загальні вимоги до таких алгоритмів і визначити бажані характеристики зображення. Очевидно, що відрізки повинні виглядати прямими, починатися і закінчуватися в заданих точках. Яскравість вздовж відрізка повинна бути постійною і не залежати від довжини і нахилу. Нарешті, треба малювати швидко. Як це часто буває, не всі з перерахованих критеріїв можуть бути повністю задоволені. Сама природа растрового дисплея виключає генерацію абсолютно прямих ліній (окрім декількох спеціальних випадків), так само як і точний збіг початку і кінця відрізка із заданими точками. Проте при достатньо високому дозвіл дисплея можна отримати прийнятне зображення.

Постійна уздовж всього відрізка яскравість досягається лише при проведенні горизонтальних, вертикальних і нахилених під кутом 45 ° прямих. Для всіх інших орієнтації розкладання в растр призведе до нерівномірного яскравості, як це показано на рис. 2.1. Навіть для окремих випадків яскравість залежить від нахилу: зауважимо, наприклад, що відстань між центрами сусідніх пікселів для відрізка під кутом 45 ° більше, ніж для вертикальних і горизонтальних прямих. Тому вертикальні і горизонтальні відрізки будуть виглядати яскравіше, ніж похилі. Забезпечення однакової яскравості вздовж відрізків різних довжин і орієнтації вимагає витягання квадратного кореня, а це сповільнить обчислення. Звичайним компромісом є знаходження наближеною довжини відрізка, зведення обчислень до мінімуму, переважне використання цілої арифметики, а також реалізація алгоритмів на апаратному або мікропрограмного рівні.

2 Алгоритми генерації відрізків

2.1 Цифровий Диференціальний аналізатор

Один з методів розкладання відрізка в растр полягає у вирішенні диференціального рівняння, що описує цей процес. Для прямої лінії маємо

Рішення представляється у вигляді

де x1, y1 і x2, y2 - кінці розкладаного відрізка і yi - початкове значення для чергового кроку вздовж відрізка. Фактично рівняння [1] являє собою рекурентное співвідношення для послідовних значень y уздовж потрібного відрізка. Цей метод, що використовується для розкладання в растр відрізків, називається цифровим диференціальних аналізатором (ЦБА). Впрост ЦБА або Dx, або Dy (більше з збільшень) вибирається в якості одиниці растру. Нижче наводиться простий алгоритм, що працює у всіх квадрантах:

Процедура розкладання в растр відрізка за методом цифрового диференціального аналізатора (ЦБА)

передбачається, що кінці відрізка (x1, y1) та (x2, y2) не збігаються

Integer - Функція перетворення дійсного числа в ціле.

Sign - Функція, що повертає -1, 0, 1 для негативного, нульового та позитивного аргументу відповідно

Апроксимуємо довжину відрізка

if abs (x2 - x1)> = abs (y2 - y1) then

Довжина = abs (x2 - x1) else

Довжина = abs (y2 - y1) end

вважаємо більше з збільшень