Różnica między DDA a algorytmem Bresenhama

Cyfrowy algorytm różnicowy (DDA) i algorytm Bresenhamsa są cyfrowymi algorytmami rysującymi linie i są używane w grafice komputerowej do rysowania obrazów. Wcześniej używaliśmy analizatorów analitycznych do obliczania pikseli, dzięki czemu możliwe było rysowanie linii. Ale te metody analityczne nie są tak dokładne, jak metody cyfrowe, które przy użyciu tych algorytmów cyfrowych teraz i jak w każdej dziedzinie, wymyśliliśmy również metody wyższej jakości w grafice komputerowej. Wynalezienie tych algorytmów jest doskonałym przykładem. Zanim przejdziemy dalej, spójrzmy na koncepcję tych algorytmów. Chociaż wydaje się to poza zakresem naszej dyskusji, należy wskazać podstawowe różnice między nimi. Jeśli naprawdę znasz algorytmy, możesz przejść do faktycznych różnic znajdujących się na końcu tej strony.

Co to jest cyfrowy algorytm różnicowy (DDA)?

DDA służy głównie do rysowania linii w grafice komputerowej i wykorzystuje rzeczywiste wartości, jednocześnie przewidując kolejne wartości pikseli. Załóżmy, że początkowa wartość piksela to (X0, Y0) (X0, Y0), a piksel docelowy to (X1, Y1) (X1, Y1). Dowiemy się, jak obliczyć docelowe wartości pikseli na podstawie znanej wartości pikseli (X0, Y0) (X0, Y0), jak poniżej.

Jak obliczyć wartość punktu docelowego za pomocą DDA?

Krok 1: Tutaj mamy dane wejściowe (X0, Y0) (X0, Y0) i powinniśmy ustalić, czy linia biegnie równolegle do osi x czy osi y. Aby to znaleźć, obliczmy teraz różnicę między początkową a docelową wartością pikseli.

dx = X1 - X0

dy = Y1 - Y0

Krok 2: Teraz zidentyfikowaliśmy różnicę i powinniśmy narysować linię wzdłuż osi x, jeśli „dx” wynosi zero, w przeciwnym razie powinniśmy narysować linię równoległą do osi y. Oto rzeczywiste obliczenia dotyczące języka komputera.

if (bezwzględny (dx)> bezwzględny (dy))

Kroki = absolut (dx);

jeszcze

Kroki = absolut (dy);

Krok 3: Teraz nadszedł czas na określenie rzeczywistej współrzędnej „x” lub współrzędnych „y” w pikselach w celu narysowania linii.

Przyrost X = kroki dx / (zmiennoprzecinkowe);

Przyrost Y = kroki dy / (zmiennoprzecinkowe);

Krok 4: Należy to obliczyć, aż dotrzemy do docelowego piksela. Algorytm DDA zaokrągla wartość piksela do najbliższej wartości całkowitej podczas wykonywania obliczeń. Oto przykładowy kod tego, co omówiliśmy teraz.

Dla (int v = 0; v < Steps; v++)

przyrost x = x + X;

y = y + przyrost Y;

putpixel (Round (x), Round (y));

Skończyliśmy rysować linię za pomocą DDA i przejdźmy teraz do Bresenham's!

Czym jest algorytm Bresenhama?

Jest to również cyfrowy algorytm rysowania linii, który został wynaleziony przez Bresenhama w 1962 roku i dlatego ma taką samą nazwę. Algorytm ten jest dokładniejszy i wykorzystywał odejmowanie i dodawanie do obliczania wartości piksela podczas rysowania linii. Dokładność algorytmu Bresenhama jest niezawodna również podczas rysowania krzywych i okręgów. Zobaczmy, jak działa ten algorytm.

Krok 1: Algorytmy Bresenhama przyjmują początkową współrzędną pikselową jako (x_{a + 1}, y_za).

Krok 2: Automatycznie oblicza następną wartość piksela jako (x_{a + 1}, y_{a + 1}), Tutaj „a” jest wartością przyrostową, a algorytm oblicza ją, dodając lub odejmując utworzone równania.

Ten algorytm oblicza dokładne wartości bez zaokrąglania i wygląda również łatwiej!

Numeryczny przykład algorytmu Bresenhama:

Rozważmy teraz punkty (0,0) i (-8, -4) i narysujmy linię między tymi punktami za pomocą algorytmu Bresenhama.

Biorąc pod uwagę dane, (x1, y1) = (0, 0) i (x2, y2) = (-8, -4).

Obliczmy teraz wartości różnicowe jak poniżej.

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

Dlatego wartość przyrostowa dla x = ∆x / x2 = 8 / -8 = -1.

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

Dlatego wartość przyrostowa dla y = ∆y / y2 = 4 / -4 = -1.

Zmienna decyzyjna = e = 2 * (∆y) - (∆x)

Dlatego e = 2 * (4) - (8) = 8-8 = 0

Z powyższym obliczeniem, zestawmy wynikowe wartości. Wartości współrzędnej y są korygowane w oparciu o zmienną decyzyjną i tutaj ignorujemy jej obliczenia.

Piksel	x	y	Zmienna decyzyjna
(0,0)	0	0	0
(-1,0)	-1	0	Wartość
(-2, -1)	-2)	-1	0
(-3, -1)	-3)	-1	Wartość
(-4, -2)	-4	-2)	0
(-5, -2)	-5	-2)	Wartość
(-6, -3)	-6	-3)	0
(-7, -3)	-7	-3)	Wartość
(-8, -4)	-8	-4	0

Różnice między DDA a algorytmem Bresenhama:

Obliczanie arytmetyczne:

DDA używa rzeczywistych wartości w swoich obliczeniach z wykorzystaniem zmiennoprzecinkowych. Kolejne wartości pikseli lub punktów są określane za pomocą równań różniczkowych

Przyrost X = kroki dx / (zmiennoprzecinkowe)

Przyrost Y = kroki dy / (zmiennoprzecinkowe)

Tutaj nie stosuje się stałych stałych, ale w algorytmie Bresenhama punkty stałe są używane w obliczeniach arytmetycznych. Algorytm Bresenhama wykorzystuje arytmetykę liczb całkowitych, w przeciwieństwie do DDA.

Rodzaj zastosowanej operacji:

DDA rozwiązuje równania różniczkowe za pomocą operacji mnożenia i dzielenia. Można to zauważyć tutaj, X przyrostów = dx / (liczba zmiennoprzecinkowa). Algorytm Bresenhama wykorzystuje operacje dodawania i odejmowania i możesz to zauważyć tutaj w kolejnym równaniu obliczania wartości pikseli (x_{a + 1}, y_{a + 1}). Arytmetyka jest prostsza w Bresenham w porównaniu do DDA.

Wydajność:

Jak omówiliśmy wcześniej, algorytm Bresenhama wykorzystuje prostszą arytmetykę niż DDA i daje efektywne wyniki.

Prędkość: Ponieważ DDA korzysta z liczb całkowitych zmiennoprzecinkowych wraz z operacjami mnożenia i dzielenia, jest względnie wolniejszy, podczas gdy algorytm Bresenhama wykorzystuje tylko arytmetykę liczb całkowitych wraz z samym dodawaniem i odejmowaniem. To znacznie skraca czas obliczeń, a tym samym jest szybszy niż DDA.
Precyzja: Chociaż DDA wykorzystuje wartości zmiennoprzecinkowe, dokładność DDA nie jest tak lepsza jak w przypadku Bresenhama. Różnorodność czynników wpływa na tę koncepcję i dlatego Bresenham's jest dokładniejszy niż DDA.
Zaokrąglenie: Wystarczy spojrzeć na obliczenia DDA tutaj.

Przyrost X = kroki dx / (zmiennoprzecinkowe)

Można zauważyć „liczbę zmiennoprzecinkową” i dlatego nie zaokrągla wartości, podczas gdy algorytm Bresenhama zaokrągla wartości do najbliższej liczby całkowitej. Dlatego zastosowane wartości są prostsze w algorytmie Bresenhama.

Co to rysuje?

DDA jest w stanie rysować koła i krzywe oprócz rysowania linii. Algorytm Bresenhama jest również w stanie narysować wszystkie wymienione powyżej, a jego dokładność jest naprawdę wyższa niż w przypadku DDA. Podobnie, algorytm Bresenhama mógłby wymyślić wydajne krzywe niż te opracowane przez DDA. Oba algorytmy mogą również rysować trójkąty i wielokąty.

Co jest drogie?

Ponieważ DDA obejmuje również zaokrąglanie, jest kosztowne niż użycie algorytmu Bresenhama.

Który jest zoptymalizowanym algorytmem?

Z naszej powyższej dyskusji jasno wynika, że algorytm Bresenhama jest zoptymalizowany pod względem szybkości, kosztów i wykorzystania operacji.

Spójrzmy na różnice w formie tabelarycznej.

S.Nie	Różnice w	Cyfrowy algorytm różnicowy	Algorytm Bresenhama
1.	Skąd ta nazwa??	Tylko dlatego, że była cyfrową implementacją równań, ma swoją nazwę.	Został wynaleziony przez J.E. Bresenhama w 1962 roku i stąd nazwa.
2).	Obliczenia	Obejmuje trudniejsze obliczenia.	Zastosowane obliczenia są naprawdę prostsze.
3).	Rodzaje zastosowanych operacji	Wykorzystywał mnożenia i podziały. Przykładowe równania różniczkowe użyte tutaj to kroki Xincrement = dx / (zmiennoprzecinkowe), Krok Yincrement = dy / (zmiennoprzecinkowy).	Wykorzystuje dodawanie i odejmowanie. Przykładowe obliczenia można tutaj oznaczyć jak (x_{a + 1}, y_{a + 1}).
4.	Wartości obliczeń arytmetycznych	Wykorzystuje wartości zmiennoprzecinkowe.	Wykorzystuje tylko wartości całkowite.
5.	Wydajność	Złożona arytmetyka powoduje mniejszą wydajność.	Prostsza arytmetyka skutkuje większą wydajnością.
6.	Prędkość	Użycie operacji mnożenia i dzielenia zajmuje dużo czasu na ich procesy obliczeniowe.	Użycie operacji dodawania i odejmowania zajmuje mniej czasu niż DDA.
7.	Precyzja	Ma mniejszą dokładność.	To jest bardziej dokładne.
8.	Zaokrąglenie	Wykorzystuje rzeczywiste wartości i nigdy nie zaokrągla wartości.	Zaokrągla wartości do najbliższych wartości całkowitych.
9.	Możliwość rysowania	Jest w stanie rysować linie, koła i krzywe, ale z mniejszą dokładnością. Za pomocą tego algorytmu możemy nawet rysować trójkąty i wielokąty.	Jest w stanie rysować linie, koła i krzywe z większą wydajnością. Za pomocą tego algorytmu można również rysować trójkąty i wielokąty.
10.	Koszt obliczeń	Jest drogi, ponieważ wymaga również zaokrąglenia.	Wykorzystanie algorytmu Bresenhama jest tańsze niż DDA.
11.	Zoptymalizowany algorytm	To nie jest zoptymalizowany algorytm	Jest to zoptymalizowany algorytm.

Zajęliśmy się każdą możliwą różnicą między DDA a algorytmem Bresenhama. Może to nawet wydawać się powtarzalne, ale istnieje jakiś uzasadniony powód, aby wspomnieć o tych punktach ponownie i dowiesz się, kiedy całkowicie je zrozumiesz. Jeśli nadal uważasz, że istnieje niejasność, zostaw nam komentarz. Uczmy się razem, dzieląc się odpowiednią wiedzą!

Protokoły i formaty