Atšķirība starp DDA un Bresenham algoritmu

Digitālais diferenciālais algoritms (DDA) un Bresenhams's algoritms ir digitālo līniju zīmēšanas algoritmi, un tos izmanto datoru grafikā attēlu zīmēšanai. Iepriekš pikseļu aprēķināšanai mēs izmantojām analītiskos analizatorus, un tādējādi bija iespējama līniju zīmēšana. Bet šīs analītiskās metodes nav tik precīzas kā digitālās metodes, ka, izmantojot šos digitālos algoritmus tagad un tāpat kā katrā jomā, mēs arī esam izgudrojuši augstākas kvalitātes metodes arī datorgrafikā. Šo algoritmu izgudrojums ir lielisks piemērs. Pirms turpināt, apskatīsim šo algoritmu pamatā esošo jēdzienu. Lai arī tas šķiet ārpus mūsu diskusijas jomas, ir svarīgi norādīt uz galvenajām atšķirībām starp abām. Ja jūs patiešām esat pazīstams ar algoritmiem, varat pāriet uz faktiskajām atšķirībām, kas atrodas šīs lapas beigās.

Kas ir digitālais diferenciālais algoritms (DDA)?

DDA lielākoties izmanto līniju vilkšanai datorgrafikā un izmanto reālās vērtības, prognozējot nākamās pikseļu vērtības. Pieņemsim, ka sākotnējā pikseļa vērtība ir (X0, Y0) (X0, Y0) un mērķa pikselis ir (X1, Y1) (X1, Y1). Mēs iemācīsimies, kā aprēķināt mērķa pikseļu vērtības no zināmās pikseļu vērtības (X0, Y0) (X0, Y0), kā norādīts zemāk.

Kā aprēķināt mērķa punkta vērtību, izmantojot DDA?

1. darbība: Šeit mums ir ievads (X0, Y0) (X0, Y0), un mums vajadzētu noteikt, vai līnija iet paralēli x asij vai y asij. Lai to uzzinātu, tagad aprēķināsim starpību starp sākotnējo un mērķa pikseļu vērtībām.

dx = X1 - X0

dy = Y1 - Y0

2. darbība: Tagad mēs esam identificējuši atšķirību un mums vajadzētu novilkt līniju gar x asi, ja 'dx' ir nulle, pretējā gadījumā līnija jānovelk paralēli y asij. Šeit ir faktiskais aprēķins datora valodas izteiksmē.

ja (absolūts (dx)> absolūts (dy))

Soļi = absolūts (dx);

cits

Soļi = absolūts (dy);

3. darbība: Tagad ir laiks noteikt faktisko “x” koordinātu vai “y” koordinātu pikseļu vērtības, lai novilktu līniju.

X pieaugums = dx / (pludiņa) pakāpes;

Y pieaugums = dy / (pludiņa) pakāpieni;

4. solis: Tas jāaprēķina, līdz mēs sasniedzam mērķa pikseļu. Veicot aprēķinu, DDA algoritms noapaļo pikseļa vērtību līdz tuvākajai veselajai vērtībai. Šeit ir koda paraugs tam, ko mēs tagad apspriedām.

Priekš (int v = 0; v < Steps; v++)

x = x + X pieaugums;

y = y + Y pieaugums;

putpikselis (apaļa (x), apaļa (y));

Mēs esam pabeiguši līnijas novilkšanu, izmantojot DDA, un ļaujiet mums pāriet uz Bresenham's tagad!

Kāds ir Bresenham algoritms?

Tas ir arī digitālu līniju zīmēšanas algoritms, kuru 1962. gadā izgudroja Bresenham, un tāpēc tam ir tāds pats nosaukums. Šis algoritms ir precīzāks, un līnijas vilkšanai tas izmantoja atņemšanu un papildinājumu pikseļa vērtības aprēķināšanai. Bresenhema algoritma precizitāte ir uzticama, zīmējot arī līknes un apļus. Apskatīsim, kā darbojas šis algoritms.

1. darbība: Bresenhama algoritmi sākotnējā pikseļa koordinātu pieņem kā (x_{a + 1}, y_a).

2. darbība: Tas automātiski aprēķina nākamo pikseļa vērtību kā (x_{a + 1}, y_{a + 1}), Šeit 'a' ir pieaugošā vērtība, un algoritms to aprēķina, saskaitot vai atņemot vienādojumus, kurus tas izveidoja.

Šis algoritms aprēķina precīzas vērtības bez noapaļošanas un izskatās arī vienkāršāk!

Bresenhama algoritma skaitliskais piemērs:

Tagad apskatīsim punktus (0,0) un (-8, -4) un novilksim robežu starp šiem punktiem, izmantojot Bresenham algoritmu.

Sniegtie dati (x1, y1) = (0, 0) un (x2, y2) = (-8, -4).

Tagad aprēķināsim diferenciālās vērtības, kā norādīts zemāk.

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

Tāpēc pieaugošā vērtība x = ∆x / x2 = 8 / -8 = -1.

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

Tāpēc y = ∆y / y2 = 4 / -4 = -1 pieaugošā vērtība.

Lēmuma mainīgais = e = 2 * (∆y) - (∆x)

Tāpēc e = 2 * (4) - (8) = 8-8 = 0

Izmantojot iepriekš minēto aprēķinu, tabulēsim iegūtās vērtības. Y-koordinātu vērtības tiek koriģētas, pamatojoties uz lēmumu mainīgo lielumu, un mēs šeit vienkārši ignorējam tā aprēķināšanu.

Pikselis	x	y	Lēmuma mainīgais
(0,0)	0	0	0
(-1,0)	-1	0	Vērtība
(-2, -1)	-2	-1	0
(-3, -1)	-3	-1	Vērtība
(-4, -2)	-4	-2	0
(-5, -2)	-5	-2	Vērtība
(-6, -3)	-6	-3	0
(-7, -3)	-7	-3	Vērtība
(-8, -4)	-8	-4	0

Atšķirības starp DDA un Bresenham algoritmu:

Aritmētiskais aprēķins:

DDA aprēķinos izmanto reālās vērtības ar peldošo punktu izmantošanu. Nākamās pikseļu vai punktu vērtības tiek noteiktas ar diferenciālvienādojumiem

X pieaugums = dx / (pludiņa) soļi

Y palielinājums = dy / (pludiņa) soļi

Šeit netiek izmantotas fiksētas konstantes, bet Bresenham algoritmā fiksētie punkti tiek izmantoti aritmētiskajos aprēķinos. Bresenhama algoritms atšķirībā no DDA izmanto Integer aritmētiku.

Izmantotās operācijas veids:

DDA diferenciālvienādojumus atrisina ar reizināšanas un dalīšanas operācijām. Varētu pamanīt to pašu šeit, X solis = dx / (pludiņa) soļi. Bresenhama algoritms izmanto saskaitīšanas un atņemšanas operācijas, un to pašu varat pamanīt šeit nākamajā pikseļa vērtības aprēķināšanas vienādojumā (x_{a + 1}, y_{a + 1}). Bresenhama aritmētika ir vienkāršāka, salīdzinot ar DDA.

Efektivitāte:

Kā mēs jau iepriekš runājām, Bresenham algoritms izmanto vienkāršāku aritmētiku nekā DDA, un tas dod efektīvus rezultātus.

Ātrums: Tā kā DDA izmanto peldošā komata veselus skaitļus kopā ar reizināšanas un dalīšanas operācijām, tas ir salīdzinoši lēnāks, turpretī Bresenhama algoritms izmanto tikai vesela skaitļa aritmētiku kopā ar saskaitījumiem un atņemšanu vien. Tas ievērojami samazina aprēķinu veikšanai nepieciešamo laiku un līdz ar to ātrāk nekā DDA.
Precizitāte: Lai arī DDA izmanto mainīgā komata vērtības, DDA precizitāte nav tik laba kā Bresenham. Šo jēdzienu ietekmē dažādi faktori, tāpēc Bresenham's ir precīzāks nekā DDA.
Noapaļošana: Paskatieties šeit DDA aprēķinu.

X pieaugums = dx / (pludiņa) soļi

Jūs varētu pamanīt “pludiņu”, tāpēc tas vērtības nenoapaļo, turpretī Bresenham algoritms noapaļo vērtības līdz tuvākajam veselajam skaitlim. Tāpēc izmantotās vērtības Bresenhama algoritmā ir vienkāršākas.

Ko tas zīmē?

DDA spēj zīmēt apļus un līknes, izņemot līnijas. Bresenhama algoritms arī spēj uzzīmēt visus iepriekš minētos, un tā precizitāte tiešām ir augstāka nekā DDA. Līdzīgi, Bresenham algoritms varētu nākt klajā ar efektīvām līknēm nekā tas, ko rada DDA. Abi algoritmi var zīmēt arī trīsstūrus un daudzstūrus.

Kas ir dārgi?

Tā kā DDA ietver arī noapaļošanu, tas ir dārgi nekā Bresenham algoritma izmantošana.

Kas ir optimizēts algoritms?

No mūsu iepriekšminētās diskusijas ir ļoti skaidrs, ka Bresenham algoritms ir optimizēts, ņemot vērā ātrumu, izmaksas un operāciju lietojumu..

Apskatīsim atšķirības tabulas formā.

S.Nē	Atšķirības	Digitālais diferenciālais algoritms	Bresenham algoritms
1.	Kāpēc vārds?	Tieši tāpēc, ka tā bija vienādojumu digitālā ieviešana, tā ir ieguvusi nosaukumu.	To izgudroja J. E. Bresenham 1962. gadā, tātad arī nosaukums.
2.	Skaitļojumi	Tas ietver stingrākus aprēķinus.	Izmantotie aprēķini ir patiešām vienkāršāki.
3.	Izmantoto operāciju veidi	Tas izmantoja reizinājumus un dalījumus. Šeit izmantotie paraugu diferenciālvienādojumi ir Xincrement = dx / (pludiņa) pakāpes, Yincrement = dy / (pludiņa) pakāpieni.	Tas izmanto saskaitījumus un atņemumus. Parauga aprēķināšanu šeit var apzīmēt kā (x_{a + 1}, y_{a + 1}).
4.	Aritmētiskās aprēķina vērtības	Tas izmanto peldošā komata vērtības.	Tas izmanto tikai veselu skaitļu vērtības.
5.	Efektivitāte	Sarežģīta aritmētika nodrošina mazāku efektivitāti.	Vienkāršāka aritmētika nodrošina lielāku efektivitāti.
6.	Ātrums	Reizināšanas un dalīšanas operāciju izmantošana prasa daudz laika to aprēķināšanas procesiem.	Saskaitīšanas un atņemšanas darbību izmantošana prasa mazāk laika nekā DDA.
7.	Precizitāte	Tā precizitāte ir mazāka.	Tas ir precīzāks.
8.	Noapaļošana	Tas izmanto reālās vērtības un nekad nenoapaļo vērtības.	Tas noapaļo vērtības līdz tuvākajām veselajām vērtībām.
9.	Zīmēšanas iespējas	Tas spēj zīmēt līnijas, apļus un līknes, bet ar mazāku precizitāti. Ar šo algoritmu mēs varam uzzīmēt pat trīsstūrus un daudzstūri.	Tas ar lielāku efektivitāti var novilkt līnijas, apļus un līknes. Ar šo algoritmu ir iespējams novilkt arī trīsstūrus un daudzstūrus.
10.	Aprēķinu izmaksas	Tas ir dārgi, jo ietver arī noapaļošanu.	Bresenham algoritma izmantošana ir lētāka nekā DDA.
11.	Optimizēts algoritms	Tas nav optimizēts algoritms	Tas ir optimizēts algoritms.

Mēs esam apskatījuši visas iespējamās atšķirības starp DDA un Bresenham algoritmu. Varētu šķist, ka tas atkārtojas, bet ir kāds pamatots iemesls, lai šos punktus atkal pieminētu, un jūs zināt, kad jūs to pilnībā saprotat. Ja jums joprojām šķiet, ka pastāv neskaidrības, lūdzu, atstājiet mums komentāru. Mācīsimies kopā, daloties ar zināšanām!

Protokoli un formāti