Sự khác biệt giữa thuật toán của DDA và Bresenham

Thuật toán vi phân số (DDA) và Thuật toán của Bresenhams là thuật toán vẽ đường kỹ thuật số và được sử dụng trong đồ họa máy tính để vẽ tranh. Trước đây, chúng tôi đã sử dụng các máy phân tích phân tích để tính toán các pixel và do đó có thể vẽ các đường thẳng. Nhưng các phương pháp phân tích này không chính xác như các phương pháp kỹ thuật số mà với việc sử dụng các thuật toán kỹ thuật số này hiện nay và như với mọi lĩnh vực, chúng tôi cũng đã phát minh ra các phương pháp chất lượng cao hơn trong đồ họa máy tính. Việc phát minh ra các thuật toán này là một ví dụ hoàn hảo. Trước khi chúng ta tiến hành, chúng ta hãy xem xét khái niệm đằng sau các thuật toán này. Mặc dù có vẻ như ngoài phạm vi thảo luận của chúng tôi, điều cần thiết là chỉ ra những khác biệt cơ bản giữa hai bên. Nếu bạn thực sự quen thuộc với các thuật toán, bạn có thể chuyển sang các khác biệt thực tế nằm ở cuối trang này.

Thuật toán vi phân số (DDA) là gì?

Một DDA chủ yếu được sử dụng để vẽ các đường trong đồ họa máy tính và sử dụng các giá trị thực trong khi dự đoán các giá trị pixel tiếp theo. Giả sử giá trị pixel ban đầu là (X0, Y0) (X0, Y0) và pixel đích là (X1, Y1) (X1, Y1). Chúng ta sẽ tìm hiểu cách tính các giá trị pixel đích từ giá trị pixel đã biết (X0, Y0) (X0, Y0) như dưới đây.

Cách tính giá trị điểm đích bằng DDA?

Bước 1: Ở đây chúng ta có đầu vào (X0, Y0) (X0, Y0) và chúng ta nên xác định xem dòng chạy song song với trục x hay trục y. Để tìm ra điều đó, bây giờ chúng ta hãy tính toán sự khác biệt giữa các giá trị pixel ban đầu và pixel đích.

dx = X1 - X0

dy = Y1 - Y0

Bước 2: Bây giờ, chúng ta đã xác định sự khác biệt và chúng ta nên vẽ đường dọc theo trục x nếu 'dx' bằng 0, chúng ta nên vẽ đường thẳng song song với trục y. Đây là tính toán thực tế về ngôn ngữ máy tính.

if (tuyệt đối (dx)> tuyệt đối (dy))

Các bước = tuyệt đối (dx);

khác

Các bước = tuyệt đối (dy);

Bước 3: Bây giờ, đã đến lúc xác định tọa độ 'x' thực tế hoặc các giá trị pixel tọa độ 'y' để vẽ đường thẳng.

Các bước tăng X = dx / (float);

Các bước tăng Y = dy / (float);

Bước 4: Điều này phải được tính toán cho đến khi chúng ta đạt đến pixel đích. Thuật toán DDA làm tròn giá trị pixel thành giá trị nguyên gần nhất trong khi thực hiện tính toán. Đây là mẫu mã của những gì chúng ta đã thảo luận bây giờ.

Với (int v = 0; v < Steps; v++)

x = x + X gia tăng;

y = y + Y tăng;

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

Chúng tôi đã hoàn thành việc vẽ đường bằng DDA và bây giờ chúng ta hãy chuyển sang Bresenham!

Thuật toán của Bresenham là gì?

Nó cũng là một thuật toán vẽ đường kỹ thuật số và được phát minh bởi Bresenham vào năm 1962 và đó là lý do tại sao nó có cùng tên. Thuật toán này chính xác hơn và nó đã sử dụng phép trừ & thêm vào để tính toán giá trị pixel trong khi vẽ đường thẳng. Độ chính xác của thuật toán của Bresenham là đáng tin cậy trong khi vẽ các đường cong và vòng tròn. Chúng ta hãy xem thuật toán này hoạt động như thế nào.

Bước 1: Các thuật toán của Bresenham giả sử tọa độ pixel ban đầu là (x_{a + 1}, y_một).

Bước 2: Nó tự động tính toán giá trị pixel tiếp theo là (x_{a + 1}, y_{a + 1}), Ở đây 'a' là giá trị gia tăng và thuật toán tính toán nó bằng cách thêm hoặc trừ các phương trình mà nó đã hình thành.

Thuật toán này tính toán các giá trị chính xác mà không làm tròn và trông cũng dễ dàng hơn!

Ví dụ số về thuật toán của Bresenham:

Bây giờ chúng ta hãy xem xét các điểm (0,0) và (-8, -4) và chúng ta hãy vẽ một đường thẳng giữa các điểm này bằng thuật toán của Bresenham.

Dữ liệu đã cho, (x1, y1) = (0, 0) và (x2, y2) = (-8, -4).

Bây giờ chúng ta hãy tính các giá trị vi phân như dưới đây.

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

Do đó, giá trị gia tăng cho x = x / x2 = 8 / -8 = -1.

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

Do đó, giá trị gia tăng cho y = y / y2 = 4 / -4 = -1.

Biến quyết định = e = 2 * (y) - (x)

Do đó, e = 2 * (4) - (8) = 8-8 = 0

Với tính toán trên, chúng ta hãy lập bảng giá trị kết quả. Các giá trị của tọa độ y được điều chỉnh dựa trên một biến quyết định và chúng tôi chỉ bỏ qua tính toán của nó ở đây.

Pixel	x	y	Biến quyết định
(0,0)	0	0	0
(-1,0)	-1	0	Một giá trị
(-2, -1)	-2	-1	0
(-3, -1)	-3	-1	Một giá trị
(-4, -2)	-4	-2	0
(-5, -2)	-5	-2	Một giá trị
(-6, -3)	-6	-3	0
(-7, -3)	-7	-3	Một giá trị
(-8, -4)	-số 8	-4	0

Sự khác biệt giữa Thuật toán của DDA & Bresenham:

Tính toán số học:

DDA sử dụng các giá trị thực trong các tính toán của nó với việc sử dụng các dấu phẩy động. Các giá trị pixel hoặc điểm tiếp theo được xác định bằng các phương trình vi phân

Các bước tăng X = dx / (float)

Các bước tăng Y = dy / (float)

Ở đây không có hằng số cố định được sử dụng nhưng trong thuật toán của Bresenham, các điểm cố định được sử dụng trong các tính toán số học. Thuật toán của Bresenham sử dụng số học Integer, không giống như DDA.

Loại hình hoạt động được sử dụng:

DDA giải các phương trình vi phân với các phép toán nhân và chia. Bạn có thể nhận thấy điều tương tự ở đây, các bước tăng X = dx / (float). Thuật toán của Bresenham sử dụng các phép toán cộng và trừ và bạn có thể nhận thấy điều tương tự ở đây trong phương trình tính toán giá trị pixel tiếp theo của nó (x_{a + 1}, y_{a + 1}). Số học đơn giản hơn ở Bresenham khi so sánh với DDA.

Hiệu quả:

Như chúng ta đã thảo luận trước đó, thuật toán của Bresenham sử dụng số học đơn giản hơn DDA và nó mang lại kết quả hiệu quả.

Tốc độ: Vì DDA sử dụng các số nguyên dấu phẩy động cùng với các phép toán nhân & chia, nên tương đối chậm hơn trong khi thuật toán của Bresenham chỉ sử dụng số học số nguyên cùng với các phép cộng và phép trừ. Điều này làm giảm đáng kể thời gian tính toán và do đó nhanh hơn DDA.
Sự chính xác: Mặc dù DDA sử dụng các giá trị dấu phẩy động, độ chính xác của DDA không tốt hơn Bresenham. Một loạt các yếu tố ảnh hưởng đến khái niệm này và do đó, Bresenham chính xác hơn DDA.
Làm tròn số: Chỉ cần nhìn vào tính toán của DDA ở đây.

Các bước tăng X = dx / (float)

Bạn có thể nhận thấy 'float' và do đó, nó không làm tròn các giá trị trong khi thuật toán của Bresenham làm tròn các giá trị thành số nguyên gần nhất. Do đó, các giá trị được sử dụng đơn giản hơn trong thuật toán của Bresenham.

Nó vẽ gì?

DDA có khả năng vẽ các vòng tròn và đường cong ngoài việc vẽ các đường. Thuật toán của Bresenham cũng có khả năng vẽ tất cả những gì được đề cập ở trên và độ chính xác của nó thực sự cao hơn so với DDA. Tương tự, thuật toán của Bresenham có thể tạo ra các đường cong hiệu quả hơn so với thuật toán do DDA tạo ra. Cả hai thuật toán cũng có thể vẽ các hình tam giác và đa giác.

Cái nào đắt?

Vì DDA cũng bao gồm làm tròn, nó đắt hơn so với việc sử dụng thuật toán của Bresenham.

Đó là một thuật toán tối ưu hóa?

Từ cuộc thảo luận ở trên của chúng tôi, rõ ràng thuật toán của Bresenham là một thuật toán được tối ưu hóa về tốc độ, chi phí và cách sử dụng các hoạt động.

Chúng ta hãy nhìn vào sự khác biệt trong một hình thức bảng.

S.Không	Sự khác biệt trong	Thuật toán vi phân số	Thuật toán của Bresenham
1.	Tại sao tên?	Chỉ vì nó là sự thực hiện kỹ thuật số của các phương trình, nó đã có tên.	Nó được phát minh bởi J.E. Bresenham vào năm 1962 và do đó tên này.
2.	Tính toán	Nó liên quan đến các tính toán khó khăn hơn.	Các tính toán được sử dụng thực sự đơn giản hơn.
3.	Các loại hoạt động được sử dụng	Nó đã sử dụng phép nhân và chia. Các phương trình vi phân mẫu được sử dụng ở đây là các bước Xincrement = dx / (float), Các bước Yincrement = dy / (float).	Nó sử dụng các phép cộng và phép trừ. Tính toán mẫu ở đây có thể được ký hiệu là (x_{a + 1}, y_{a + 1}).
4.	Giá trị tính toán số học	Nó sử dụng các giá trị dấu phẩy động.	Nó chỉ sử dụng các giá trị nguyên.
5.	Hiệu quả	Kết quả số học phức tạp trong hiệu quả thấp hơn.	Kết quả số học đơn giản hơn hiệu quả hơn.
6.	Tốc độ	Việc sử dụng các phép nhân và phép chia làm mất nhiều thời gian cho các quá trình tính toán của nó.	Việc sử dụng các phép toán cộng và trừ mất ít thời gian hơn DDA.
7.	Sự chính xác	Nó kém chính xác hơn.	Nó chính xác hơn.
số 8.	Làm tròn số	Nó sử dụng các giá trị thực và không bao giờ làm tròn các giá trị.	Nó làm tròn các giá trị thành các giá trị nguyên gần nhất.
9.	Khả năng vẽ	Nó có khả năng vẽ các đường, vòng tròn và đường cong nhưng với độ chính xác thấp hơn. Chúng ta thậm chí có thể vẽ các hình tam giác và đa giác bằng thuật toán này.	Nó có khả năng vẽ các đường, vòng tròn và đường cong với hiệu quả cao hơn. Hình tam giác và đa giác cũng có thể được vẽ bằng thuật toán này.
10.	Chi phí tính toán	Nó là đắt tiền vì nó cũng liên quan đến làm tròn.	Việc sử dụng thuật toán của Bresenham rẻ hơn DDA.
11.	Thuật toán tối ưu hóa	Nó không phải là một thuật toán tối ưu hóa	Nó là một thuật toán tối ưu hóa.

Chúng tôi đã xử lý mọi khác biệt có thể có giữa thuật toán của DDA và Bresenham. Nó thậm chí có vẻ lặp đi lặp lại nhưng có một số lý do hợp lệ để đề cập đến những điểm đó một lần nữa và bạn sẽ biết khi bạn hiểu nó hoàn toàn. Nếu bạn vẫn cảm thấy có sự mơ hồ, vui lòng để lại bình luận cho chúng tôi. Chúng ta hãy cùng nhau học hỏi bằng cách chia sẻ kiến thức phù hợp!

Giao thức và định dạng