Różnica między algorytmem DDA i Bresenham

Cyfrowy algorytm różnicowy (DDA) i algorytm Bresenhams to algorytmy rysowania linii cyfrowych i są używane w grafice komputerowej do rysowania zdjęć. Wcześniej używaliśmy analiz analitycznych do obliczenia pikseli, a tym samym możliwe były rysunki linii. Ale te metody analityczne nie są tak dokładne, jak metody cyfrowe, że przy użyciu tych algorytmów cyfrowych i jak w każdym polu wymyślaliśmy również metody wyższej jakości w grafice komputerowej. Wynalazek tych algorytmów jest doskonałym przykładem.  Zanim przejdziemy, przyjrzyjmy się koncepcji tych algorytmów. Choć wydaje się, że jest to poza zakresem naszej dyskusji, konieczne jest wskazanie podstawowych różnic między nimi. Jeśli naprawdę znasz algorytmy, możesz przejść do rzeczywistych różnic znajdujących się na końcu tej strony.

Jaki jest cyfrowy algorytm różnicowy (DDA)?

DDA służy najczęściej do rysowania linii w grafice komputerowej i używa wartości rzeczywistych przy jednoczesnym przewidywaniu następnych wartości pikseli. Załóżmy początkową wartość piksela jako (x0, y0) (x0, y0) i piksel docelowy jako (x1, y1) (x1, y1). Dowiemy się, jak obliczyć wartości pikseli docelowych na podstawie znanej wartości piksela (x0, y0) (x0, y0) jak poniżej.

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

Krok 1: Tutaj mamy wejście (x0, y0) (x0, y0) i powinniśmy określić, czy linia działa równolegle do osi x czy osi y. Aby to znaleźć, obliczmy teraz różnicę między wartościami piksela początkowego i docelowego.

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 inaczej, powinniśmy narysować linię równoległą do osi y. Oto faktyczne obliczenia pod względem języka komputerowego.

if (absolutne (dx)> bezwzględne (dy))

Kroki = bezwzględny (dx);

w przeciwnym razie

Kroki = bezwzględny (dy);

Krok 3: Teraz nadszedł czas, aby zidentyfikować faktyczną współrzędną „x” lub współrzędne „y”, aby wytyczyć linię.

X increment = dx / (float) kroki;

Y inkrement = dy / (float) kroki;

Krok 4: Trzeba to obliczyć, dopóki nie dotrzemy do piksela docelowego. Algorytm DDA dopełnia wartość piksela do najbliższej wartości całkowitej podczas wykonywania obliczeń. Oto próbka kodu tego, co teraz omówiliśmy.

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

x = x + x przyrost;

y = y + y przyrost;

putpixel (okrągły (x), okrągły (y));

Skończyliśmy z rysowaniem linii za pomocą DDA i przejdźmy do Bresenham teraz!

Co to jest algorytm Bresenhama?

Jest to również algorytm rysowania linii cyfrowej i został wynaleziony przez Bresenham w 1962 roku i dlatego ma to samo imię. Ten algorytm jest dokładniejszy i zastosował odejmowanie i dodatek do obliczania wartości piksela podczas rysowania linii. Dokładność algorytmu Bresenhama jest niezawodna podczas rysowania krzywych i kręgów. Spójrzmy, jak działa ten algorytm.

Krok 1: Algorytmy Bresenhama zakładają początkową współrzędną pikseli AS (x_A+1, y_A).

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 granicę między tymi punktami za pomocą algorytmu Bresenhama.

Podano 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ższymi obliczeniami, tabulujmy się wynikowymi wartościami. Wartości współrzędnego Y są dostosowywane na podstawie zmiennej decyzyjnej i po prostu ignorujemy jej obliczenia tutaj.

Różnice między algorytmem DDA i Bresenham:

• Obliczenia arytmetyczne:

DDA używa rzeczywistych wartości w swoich obliczeniach z wykorzystaniem pływających punktów. Kolejne wartości piksela lub punktu są określane za pomocą równań różniczkowych

X increment = dx / (float) kroki

Y przyrost = dy / (float) kroki

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

• Zastosowany rodzaj operacji:

DDA rozwiązuje równania różniczkowe z operacjami mnożenia i podziału. Można to zauważyć tutaj, x increment = dx / (float) kroki. Algorytm Bresenhama wykorzystuje operacje dodawania i odejmowania i można 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 z DDA.

• Efektywność:

Jak omówiliśmy wcześniej, algorytm Bresenhama używa prostszej arytmetyki niż DDA i powoduje wydajne wyniki.

• Prędkość: Ponieważ DDA używa liczb całkowitych zmiennoprzecinkowych wraz z operacjami mnożenia i podziału, jest on stosunkowo wolniej. To znacznie skraca czas poświęcony jego obliczeniom, a zatem szybciej niż DDA.
• Dokładność: Chociaż DDA używa wartości pływających, dokładność DDA nie jest tak lepsza jak Bresenham. Różnorodne czynniki wpływają na tę koncepcję, a zatem Bresenham jest dokładniejszy niż DDA.
• Zaokrąglenie: Spójrz tylko na obliczenia DDA tutaj.

X increment = dx / (float) kroki

Można zauważyć „pływak” i dlatego nie zaokrąglał wartości, podczas gdy algorytm Bresenhama dopełnia 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ć kółka i krzywe oprócz linii rysunkowych. Algorytm Bresenhama jest również w stanie rysować wszystkie wymienione powyżej, a jego dokładność jest naprawdę wyższa niż w przypadku DDA. Podobnie algorytm Bresenhama może wymyślić wydajne krzywe niż te wytwarzane 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 drogie niż wykorzystanie algorytmu Bresenhama.

• Który jest zoptymalizowanym algorytmem?

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

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

Zajmowaliśmy się każdą możliwą różnicą między DDA a algorytmem Bresenhama. Może się to wydawać powtarzalne, ale istnieje pewien ważny powód, dla którego znów wspomina o tych punktach i dowiesz się, kiedy całkowicie to zrozumiesz. Jeśli nadal uważasz, że istnieje dwuznaczność, zostaw nam komentarz. Nauczmy się razem, dzieląc się właściwą wiedzą!