Разлика между DDA и алгоритма на Bresenham

Цифровият диференциален алгоритъм (DDA) и алгоритъмът на Bresenhams са алгоритмите за рисуване на цифрови линии и се използват в компютърната графика за рисуване на снимки. Преди това използвахме аналитични анализатори, за да изчислим пикселите и по този начин бяха направени линии на чертежите. Но тези аналитични методи не са толкова точни, колкото дигиталните методи, че с използването на тези цифрови алгоритми сега и както във всяко поле, ние изобретяваме по-висококачествени методи и в компютърната графика. Изобретението на тези алгоритми е перфектен пример. Преди да продължим, нека разгледаме концепцията зад тези алгоритми. Въпреки че изглежда извън обхвата на нашата дискусия, е от съществено значение да се посочат основните разлики между двете. Ако наистина сте запознати с алгоритмите, можете да преминете към действителните разлики, разположени в края на тази страница.

Какво е цифров диференциален алгоритъм (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 = x + X прираст;

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

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

Ние приключваме с начертаването на линията с помощта на DDA и нека да преминем към Bresenham's сега!

Какво е алгоритъмът на Брезнъм?

Той също е алгоритъм за чертане на цифрови линии и е изобретен от Бресън през 1962 г. и затова е получил същото име. Този алгоритъм е по-точен и той използва изваждане и добавяне за изчисляване на стойността на пиксела, докато рисува линията. Точността на алгоритъма на Брезнъм е надеждна при чертане на криви и кръгове. Нека да разгледаме как работи този алгоритъм.

Етап 1: Алгоритмите на Брезнъм приемат началната пикселова координата като (x_{а + 1}, ш_а).

Стъпка 2: Той автоматично изчислява стойността на следващия пиксел като (x)_{а + 1}, ш_{а + 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 = Y 2-Y1 = -4-0 = 4

Следователно, инкременталната стойност за y = ∆y / y2 = 4 / -4 = -1.

Променлива за решение = e = 2 * (∆y) - (∆x)

Следователно, e = 2 * (4) - (8) = 8-8 = 0

С горното изчисление нека таблизираме получените стойности. Стойностите на y-координата се коригират въз основа на променлива за решение и ние просто игнорираме нейното изчисление тук.

Pixel	х	ш	Променлива решение
(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 и Bresenham:

Аритметично изчисление:

DDA използва реални стойности в своите изчисления с използването на плаващи точки. Следващите стойности на пиксел или точка се определят с диференциални уравнения

X стъпка = dx / (float) стъпки

Y инкремент = dy / (float) стъпки

Тук не се използват фиксирани константи, но в алгоритъма на Брезнъм фиксирани точки се използват при аритметични изчисления. Алгоритъмът на Bresenham използва аритметиката на Integer, за разлика от DDA.

Вид на използваната операция:

DDA решава диференциалните уравнения с операции на умножение и деление. Можете да забележите същото тук, X нарастване = dx / (float) стъпки. Алгоритъмът на Bresenham използва операции за събиране и изваждане и можете да забележите същото тук в следващото му уравнение за изчисляване на стойността на пиксела (x_{а + 1}, ш_{а + 1}). Аритметиката е по-проста в Bresenham's в сравнение с DDA.

Ефективност:

Както вече обсъждахме по-рано, алгоритъмът на Брезнъм използва по-проста аритметика от DDA и това води до ефективни резултати.

скорост: Тъй като DDA използва цели числа с плаваща запетая, заедно с операции за умножение и деление, той е сравнително по-бавен, докато алгоритъмът на Брезнъм използва само целочислена аритметика, заедно с добавянето и изваждането. Това значително намалява времето, необходимо за изчисленията му, а оттам и по-бързо от DDA.
Точност: Въпреки че DDA използва стойности с плаваща запетая, точността на DDA не е толкова по-добра като тази на Bresenham. Разнообразие от фактори влияят върху тази концепция и следователно, Bresenham е по-точен от DDA.
Закръгляне: Просто погледнете изчислението на DDA тук.

X стъпка = dx / (float) стъпки

Можете да забележите "float" и следователно той не закръгля стойностите, докато алгоритъмът на Bresenham закръгля стойностите до най-близкото цяло число. Следователно използваните стойности са по-прости в алгоритъма на Bresenham.

Какво рисува?

DDA е в състояние да начертава кръгове и криви освен чертане на линии. Алгоритъмът на Bresenham също е в състояние да извлече всички споменати по-горе и точността му наистина е по-висока от тази на DDA. По подобен начин алгоритъмът на Bresenham би могъл да излезе с ефективни криви от този, произведен от DDA. И двата алгоритъма могат да нарисуват триъгълници и многоъгълници.

Което е скъпо?

Тъй като DDA включва и закръгляне, това е скъпо от използването на алгоритъма на Bresenham.

Което е оптимизиран алгоритъм?

От горната ни дискусия става ясно, че алгоритъмът на Bresenham е оптимизиран по отношение на бързината, разходите и използването на операциите.

Нека разгледаме разликите в таблична форма.

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

Разбрахме се с всяка възможна разлика между DDA и алгоритъма на Bresenham. Може дори да изглежда повтарящо се, но има някаква валидна причина за споменаването на тези точки отново и вие ще знаете, когато го разберете напълно. Ако все още чувствате, че съществува неяснота, моля, оставете ни коментар. Нека да се учим заедно, като споделяме правилните знания!

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