Sự khác biệt giữa DDA và thuật toán của Bresenham Sự khác biệt giữa
Thuật toán Phân số Nhị phân (DDA) Thuật toán của Bresenhams là các thuật toán vẽ đường kẻ số và được sử dụng trong đồ họa máy tính để vẽ hình. 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 điểm ảnh và do đó bản vẽ đường đã được thực hiện. Nhưng những 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 số hiện nay và như mọi lĩnh vực khác, chúng tôi đã 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 tiến hành, chúng ta hãy nhìn vào khái niệm đằng sau những thuật toán này. Mặc dù có vẻ ngoài phạm vi của cuộc thảo luận của chúng tôi, nhưng cần phải chỉ ra những sự 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 sự khác biệt thực sự được đặt ở cuối trang này.
Thuật toán phân số số (DDA) là gì?
DDA hầu hết được sử dụng để vẽ đường trong đồ họa máy tính và sử dụng 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à điểm ảnh điểm đến là (X1, Y1) (X1, Y1). Chúng ta sẽ học cách tính giá trị điểm ảnh điểm đến từ giá trị pixel đã biết (X0, Y0) (X0, Y0) như dưới đây.
- Cách tính điểm điểm đến bằng cách sử dụng DDA?
Bước 1: Ở đây chúng ta có đầu vào (X0, Y0) (X0, Y0) và chúng ta cần xác định đường chạy song song với trục x hay trục y. Để tìm ra điều đó, chúng ta hãy tính toán sự khác biệt giữa giá trị điểm ban đầu và điểm ảnh điểm đến.
dx = X1 - X0
dy = Y1 - Y0
Bước -2: Bây giờ, chúng ta đã nhận ra 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 nếu không, chúng ta sẽ vẽ đườ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 (absolute (dx)> absolute (dy))
Các bước = tuyệt đối (dx);
khá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 'y' để xác định các giá trị pixel để vẽ đường kẻ.
bước tăng X = dx / (float);
Bước Y increment = dy / (float);
Bước-4: Điều này phải được tính cho tới khi chúng tôi đạt đến điểm ảnh đích. Thuật toán DDA làm tròn giá trị pixel thành giá trị số 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 tôi đã thảo luận bây giờ.
Đối với (int v = 0; v (x = x + tăng X; y = y + tăng Y; putpixel (Vòng (x), Vòng (y)); } Chúng tôi đã hoàn thành việc vẽ đường bằng DDA và chúng ta hãy chuyển sang Bresenham ngay bây giờ! Đây cũng là một thuật toán vẽ đường dây kỹ thuật số và được Bresenham phát minh ra vào năm 1962 và đó là lý do tại sao nó có cùng tên. Thuật toán này là chính xác hơn và sử dụng phép trừ và tính thêm vào việc tính toán giá trị pixel trong khi vẽ đường. Tính chính xác của thuật toán của Bresenham là đáng tin cậy trong khi vẽ đường cong và hình tròn. Chúng ta hãy xem thuật toán này làm việc như thế nào. Bước-1: Các thuật toán của Bresenham giả sử tọa độ điểm ảnh ban đầu là (x a + 1 , y a ). Bước 2: Nó tự động tính 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 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 các giá trị chính xác mà không làm tròn ra và trông cũng dễ dàng hơn! 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 giữa các điểm này bằng thuật toán của Bresenham. Cho dữ liệu, (x1, y1) = (0, 0) và (x2, y2) = (-8, -4). Bây giờ chúng ta tính toán 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. Quyết định Biến = e = 2 * (Δy) - (Δx) Do đó, e = 2 * (4) - (8) = 8-8 = 0 Với tính toán trên, hãy chúng tôi lập bảng các 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 ta chỉ bỏ qua tính toán của nó ở đây. bước tăng Y = dy / (float) Ở đây không có hằng số cố định nào được sử dụng nhưng trong thuật toán Bresenham được sử dụng trong 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 hoạt động được sử dụng: DDA giải quyết các phương trình vi phân với phép nhân và phân chia. Bạn có thể nhận thấy cùng một ở đây, tăng X = dx / (float) bước. Thuật toán Bresenham sử dụng phép cộng và phép trừ và bạn có thể nhận thấy cùng một điểm ở phương trình tính toán giá trị điểm tiếp theo của nó (x , 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 so với DDA và nó mang lại kết quả hiệu quả. Vì DDA sử dụng các số nguyên điểm nổi cùng với các phép toán nhân và phân chia, 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 phép cộng và phép trừ. Điều này giảm đáng kể thời gian tính toán của nó và do đó nó nhanh hơn so với DDA. Nó rút ra? DDA có khả năng vẽ vòng tròn và đường cong ngoài đường vẽ. Các thuật toán của Bresenham cũng có khả năng vẽ tất cả những đề cập ở trên và độ chính xác của nó là thực sự cao hơn của DDA. Tương tự, thuật toán của Bresenham có thể đưa ra các đường cong hiệu quả hơn so với DDA đã tạo ra. Cả hai thuật toán cũng có thể vẽ tam giác và đa giác. Do DDA bao gồm cả việc làm tròn, nó đắt hơn việc sử dụng thuật toán của Bresenham. Từ cuộc thảo luận ở trên, rất rõ ràng 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. S. Không Sự khác biệtThuật toán của Bresenham là gì?
Pixel
x
y
Biến quyết định
(0, 0)
0
0
0
(- 1, 0)
1
0
Giá trị
(-2, -1)
-2
-1
0
(- 3, -1)
-3 < -1
Giá trị
(- 4, -2)
-4
-2
0
(- 5, -2)
-5 > -2
Giá trị
(- 6, -3)
-6
-3
0
(- 7, -3)
-7
-3
Một giá trị
(- 8, -4)
-8
-4
0
Khác biệt giữa thuật toán DDA và Bresenham
:
Tính toán số học: DDA sử dụng các giá trị thực trong tính toán của nó với việc sử dụng các điểm nổi. Các điểm tiếp theo hoặc các giá trị điểm được xác định bằng các phương trình vi phân
