Різниця між DDA і алгоритмом Брезенхама

Цифровий диференціальний алгоритм (DDA) та алгоритм Брезенхамса є алгоритмами малювання цифрових ліній і використовуються в комп'ютерній графіці для малювання зображень. Раніше ми використовували аналітичні аналізатори для обчислення пікселів, і таким чином були можливі малюнки ліній. Але ці аналітичні методи не такі точні, як цифрові методи, що, використовуючи ці цифрові алгоритми зараз, як і у кожному полі, ми винайшли методи більш високої якості і в комп'ютерній графіці. Винахід цих алгоритмів є прекрасним прикладом. Перш ніж ми продовжимо, розглянемо концепцію цих алгоритмів. Хоча це виглядає поза рамками нашої дискусії, важливо вказати на основні відмінності між ними. Якщо ви дійсно знайомі з алгоритмами, ви можете перейти до фактичних відмінностей, розташованих в кінці цієї сторінки.

Що таке цифровий диференціальний алгоритм (DDA)?

DDA використовується в основному для малювання ліній в комп'ютерній графіці і використовує реальні значення при прогнозуванні наступних значень пікселів. Припустимо початкове значення пікселя як (X0, Y0) (X0, Y0), а піксельне призначення як (X1, Y1) (X1, Y1). Ми дізнаємось, як обчислити значення пікселів призначення з відомого значення пікселя (X0, Y0) (X0, Y0), як показано нижче.

Як обчислити значення точки призначення за допомогою DDA?

Крок 1: Тут ми маємо вхід (X0, Y0) (X0, Y0) і нам слід визначити, чи пряма лінія проходить паралельно осі x або осі y. Щоб знайти це, давайте тепер обчислимо різницю між початковим та кінцевим значенням пікселя.

dx = X1 - X0

dy = Y1 - Y0

Крок 2: Тепер ми визначили різницю і нам слід провести лінію вздовж осі x, якщо 'dx' дорівнює нулю, інакше слід провести лінію, паралельну осі y. Ось власне обчислення з точки зору комп'ютерної мови.

якщо (абсолютний (dx)> абсолютний (dy))

Кроки = абсолютні (dx);

ще

Кроки = абсолютні (dy);

Крок 3: Тепер настав час визначити фактичні координати 'x' або значення пікселів 'y', щоб намалювати лінію.

Приріст X = dx / (float) кроки;

Інкремент Y = dy / (float) кроки;

Крок 4: Це потрібно обчислити, поки ми не досягнемо пікселя призначення. Алгоритм DDA округляє значення пікселя до найближчого цілого значення під час обчислення. Ось зразок коду того, що ми обговорювали зараз.

Для (int v = 0; v < Steps; v++)

х = х + X приріст;

y = y + Y приріст;

путпіксель (Round (x), Round (y));

Ми закінчилися з нанесенням лінії за допомогою DDA і перейдемо до Bresenham's зараз!

Що таке алгоритм Брезенама?

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

Крок 1: Алгоритми Брезенама передбачають початкову координату пікселів як (x)_{a + 1}, у_а).

Крок 2: Він автоматично обчислює наступне значення пікселя як (x)_{a + 1}, у_{a + 1}), Тут 'a' - додаткове значення, і алгоритм обчислює його, додаючи або віднімаючи рівняння, що утворилися.

Цей алгоритм обчислює точні значення без округлення, а також виглядає простіше!

Числовий приклад алгоритму Брезенама:

Розглянемо тепер точки (0,0) та (-8, -4) та проведемо лінію між цими точками, використовуючи алгоритм Брезена.

Наведені дані (x1, y1) = (0, 0) і (x2, y2) = (-8, -4).

Давайте тепер обчислимо диференційні значення, як показано нижче.

∆x = x2-x1 = -8-0 = 8

Тому додаткове значення для x = ∆x / x2 = 8 / -8 = -1.

∆y = y2-y1 = -4-0 = 4

Тому додаткове значення для y = ∆y / y2 = 4 / -4 = -1.

Змінна рішення = e = 2 * (∆y) - (∆x)

Тому e = 2 * (4) - (8) = 8-8 = 0

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

Піксель	х	у	Змінна рішення
(0,0)	0	0	0
(-1,0)	-1	0	Значення
(-2, -1)	-2	-1	0
(-3, -1)	-3	-1	Значення
(-4, -2)	-4	-2	0
(-5, -2)	-5	-2	Значення
(-6, -3)	-6	-3	0
(-7, -3)	-7	-3	Значення
(-8, -4)	-8	-4	0

Відмінності між алгоритмом DDA і алгоритмом Брезена:

Арифметичний розрахунок:

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

Приріст X = dx / (float) кроки

Приріст Y = dy / (float) кроки

Тут не використовуються фіксовані константи, але в алгоритмі Брезенама фіксовані точки використовуються в арифметичних обчисленнях. Алгоритм Брезенама використовує арифметику Integer, на відміну від DDA.

Тип використовуваної операції:

DDA розв'язує диференціальні рівняння за допомогою операцій множення та ділення. Ви можете помітити те саме тут, кроком X = dx / (float). Алгоритм Брезена використовує операції додавання і віднімання, і ви можете помітити те саме тут, у наступному рівнянні обчислення значення пікселя (x_{a + 1}, у_{a + 1}). Арифметика простіша у Бресенхемі порівняно з ДДА.

Ефективність:

Як ми вже обговорювали раніше, алгоритм Брезена використовує простішу арифметику, ніж DDA, і це призводить до ефективних результатів.

Швидкість: Оскільки DDA використовує цілі числа з плаваючою комою разом з операціями множення і ділення, він порівняно повільніше, тоді як алгоритм Брезенама використовує лише цілу арифметику разом з додаваннями і відніманнями. Це значно скорочує час, витрачений на його обчислення, а значить, швидше, ніж DDA.
Точність: Хоча DDA використовує значення з плаваючою комою, точність DDA не настільки краща, як у Брезенхема. Різноманітність факторів впливає на цю концепцію, тому Bresenham є більш точним, ніж DDA.
Закруглення: Просто подивіться на обчислення DDA тут.

Приріст X = dx / (float) кроки

Ви можете помітити "float", і тому він не округляє значення, тоді як алгоритм Брезена закріплює значення до найближчого цілого числа. Тому використовувані значення простіші в алгоритмі Брезена.

Що це малює?

DDA здатний малювати кола і криві, крім малювання ліній. Алгоритм Брезенама також здатний намалювати всі згадані вище, і його точність дійсно вище, ніж у DDA. Аналогічно, алгоритм Брезенама міг би створити ефективніші криві, ніж ті, які виробляє DDA. Обидва алгоритми можуть також малювати трикутники та багатокутники.

Що дорого?

Оскільки DDA включає також округлення, це дорого, ніж використання алгоритму Брезенама.

Що є оптимізованим алгоритмом?

З нашого вище обговорення ясно, що алгоритм Брезена є оптимізованим в частині швидкості, вартості та використання операцій.

Давайте розглянемо відмінності в табличній формі.

S.No	Відмінності в	Цифровий диференціальний алгоритм	Алгоритм Брезена
1.	Чому назва?	Тільки тому, що це була цифрова реалізація рівнянь, вона отримала назву.	Він був винайдений Дж. Е. Брезенем у 1962 році, звідси і назва.
2.	Обчислення	Він передбачає більш жорсткі обчислення.	Використовувані обчислення дійсно простіші.
3.	Види використовуваних операцій	Він використовував множення та ділення. Вибіркові диференціальні рівняння, що використовуються тут, є кроками Xincrement = dx / (float), Посилення = dy / (float) кроки.	Він використовує додавання та віднімання. Вибірковий розрахунок тут можна позначати як (x_{a + 1}, у_{a + 1}).
4.	Арифметичні значення обчислення	Він використовує значення з плаваючою комою.	Він використовує лише цілі значення.
5.	Ефективність	Складна арифметика призводить до меншої ефективності.	Простіша арифметика призводить до більшої ефективності.
6.	Швидкість	Використання операцій множення та ділення потребує багато часу для його обчислювальних процесів.	Використання операцій додавання та віднімання займає менше часу, ніж DDA.
7.	Точність	Він менший за точністю.	Це точніше.
8.	Закруглення	Він використовує реальні значення і ніколи не округляє значення.	Він округляє значення до найближчих цілих значень.
9.	Можливість малювання	Він здатний малювати лінії, кола та криві, але з меншою точністю. За допомогою цього алгоритму ми можемо навіть намалювати трикутники та багатокутники.	Він здатний малювати лінії, кола та криві з більшою ефективністю. За допомогою цього алгоритму також можна намалювати трикутники та багатокутники.
10.	Вартість обчислень	Це дорого, оскільки передбачає також округлення.	Використання алгоритму Брезенама дешевше, ніж DDA.
11.	Оптимізований алгоритм	Це не оптимізований алгоритм	Це оптимізований алгоритм.

Ми розібралися з усіма можливими різницями між DDA і алгоритмом Брезена. Це може здатися повторюваним, але є певна причина для того, щоб згадати ці моменти ще раз, і ви дізнаєтесь, коли повністю зрозумієте це. Якщо ви все ще відчуваєте, що існує двозначність, будь ласка, залиште нам коментар. Навчимось разом, поділившись належними знаннями!

Протоколи та формати