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

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

Серед способів завдання відрізків прямих в машинній графіці найбільшого поширення набули наступні:

*  координатами початкової та кінцевої точки (рис.1.1 ,а);

*  приростами координат ( рис. 1.1,б).

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

В другому способі вектор задається початковою точкою та приростами ΔХ та ΔУ вектора, які визначають кінцеву точку.

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

Більшість методів лінійного інтерполювання орієнтовано для формування траєкторії в одному з квадрантів прямокутної системи координат. При формуванні траєкторії в будь-якому квадранті використовують спеціальні прийоми переключення знаків змінних.

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

Рис. 1.2. Функціональна схема двійкового помножувача

Серед методів формування відрізків прямих найбільшого поширення знайшли метод симетричного інтегратора, “прямий” метод, метод цифрового диференційного аналізатору, метод оцінювальної функції. Згідно “прямого” методу координати точок траєкторії знаходять з відомого рівняння прямої:

При ΔX≥ΔY в приведене рівняння підставляють поточну координату Х і знаходять координату Y, а при DХ<DY – навпаки. Погрішність інтерполяції при реалізації методу визначається обраним способом округлення.

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

При використанні методу ЦДА відношення Р=DY/DХ знаходять в циклі підготовки , а операцію множення на Х заміняють накопичуючим підсумовуванням . Очевидно, що при DХ≥DY значение Р≤0. Якщо в результаті накопичуючого підсумовування операнда DY/DХ має місце сигнал переповнення для цілої частини числа, то до поточного значення Y добавляють одиницю. Поточне значення Х збільшують на одиницю в кожному такті.

При DХ<DY знаходять відношення DХ/DY і виконують раніше перераховані дії , але вже зі зміною координат.

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

де КК – значення керуючого коду, n – розрядність помножувача, f_вх, f_вих – значення відповідно вхідної та вихідної частоти опорної імпульсної послідовності.

Спрощена функціональна схема двійкового помножувача приведена на рис.1.2. Двійковий помножувач ДУ забезпечує перетворення управляючого коду КК в кількість імпульсів, які формуються на його виході за Т=2ⁿ тактів лічби.

Двійковий помножувач включає двійковий лічильник СТ2 та логічну схему, до складу якої входять елементи І та елемент АБО. За цикл перерахунку лічильника СТ2 на його виходах буде сформовані імпульсні послідовності(рис. 1.3), кількість імпульсів в яких дорівнюють степеням двійок( утворюють двійкові розряди).

Рис. 1.3. Часова діаграма роботи трьохрозрядного двійкового лічильника

Одиничні значення розрядів керуючого коду КК дозволяють роботу відповідних елементів І, що обумовлює проходження на їх вихід імпульсних послідовностей , які генеруються на виходах лічильника. Елемент АБО забезпечує об’єднання імпульсних послідовностей в вихідний потік F_вих за Т=2ⁿ тактів на виході двійкового помножувача буде сформовано КК імпульсів.

В даному підході використовується допоміжна змінна - час Т, який визначається циклом перерахунку двійкового помножувача. СТ2. Оскільки реалізується рівняння прямої, заданої в параметричній формі, то лінійні інтерполятори тікого класу часто називають параметричними.

Структурна схема параметричного лінійного інтерполятора приведена на рис.1.4.

Рис. 1.4. Структурна схема параметричного лінейного інтерполятора.

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

На рис.1.5 приведений приклад формування параметричним лінійним інтерполятором відрізка прямої з DХ=5, DY=3.

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

Рис. 1.5. Приклад формування відрізка прямої параметричним лінійним інтерполятором.

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

Згідно алгоритму симетричного інтегратора обчислення інтегралу виконується приблизно, шляхом додавання ( наприклад по методу Ейлера) . При цьому обчислюються:

Значення N повинно бути вибрано таким, щоб кроки по DХ(iDt) і DY(iDt) були менше розміру піксела , оскільки лише в цьому випадку вектор буде виглядати як суцільна лінія. Дана умова задовольняється, якщо розмір кроку менше однієї одиниці растра. Звідси можна одержати умову для визначення N: DХ/N<1і DY/N<1, або N>max( |DX|, |DY|).